1 // SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0
2 /*
3 * Copyright (C) 2018-2019 HUAWEI, Inc.
4 * http://www.huawei.com/
5 * Created by Miao Xie <miaoxie@huawei.com>
6 * with heavy changes by Gao Xiang <gaoxiang25@huawei.com>
7 */
8 #include <stdlib.h>
9 #include <erofs/cache.h>
10 #include "erofs/io.h"
11 #include "erofs/print.h"
12
13 static struct erofs_buffer_block blkh = {
14 .list = LIST_HEAD_INIT(blkh.list),
15 .blkaddr = NULL_ADDR,
16 };
17 static erofs_blk_t tail_blkaddr, erofs_metablkcnt;
18
19 /* buckets for all mapped buffer blocks to boost up allocation */
20 static struct list_head mapped_buckets[META + 1][EROFS_MAX_BLOCK_SIZE];
21 /* last mapped buffer block to accelerate erofs_mapbh() */
22 static struct erofs_buffer_block *last_mapped_block = &blkh;
23
erofs_bh_flush_drop_directly(struct erofs_buffer_head * bh)24 static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
25 {
26 return erofs_bh_flush_generic_end(bh);
27 }
28
29 const struct erofs_bhops erofs_drop_directly_bhops = {
30 .flush = erofs_bh_flush_drop_directly,
31 };
32
erofs_bh_flush_skip_write(struct erofs_buffer_head * bh)33 static bool erofs_bh_flush_skip_write(struct erofs_buffer_head *bh)
34 {
35 return false;
36 }
37
38 const struct erofs_bhops erofs_skip_write_bhops = {
39 .flush = erofs_bh_flush_skip_write,
40 };
41
42 /* return buffer_head of erofs super block (with size 0) */
erofs_buffer_init(void)43 struct erofs_buffer_head *erofs_buffer_init(void)
44 {
45 int i, j;
46 struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
47
48 if (IS_ERR(bh))
49 return bh;
50
51 bh->op = &erofs_skip_write_bhops;
52
53 for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
54 for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
55 init_list_head(&mapped_buckets[i][j]);
56 return bh;
57 }
58
erofs_bupdate_mapped(struct erofs_buffer_block * bb)59 static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
60 {
61 struct list_head *bkt;
62
63 if (bb->blkaddr == NULL_ADDR)
64 return;
65
66 bkt = mapped_buckets[bb->type] +
67 (bb->buffers.off & (erofs_blksiz(&sbi) - 1));
68 list_del(&bb->mapped_list);
69 list_add_tail(&bb->mapped_list, bkt);
70 }
71
72 /* return occupied bytes in specific buffer block if succeed */
__erofs_battach(struct erofs_buffer_block * bb,struct erofs_buffer_head * bh,erofs_off_t incr,unsigned int alignsize,unsigned int extrasize,bool dryrun)73 static int __erofs_battach(struct erofs_buffer_block *bb,
74 struct erofs_buffer_head *bh,
75 erofs_off_t incr,
76 unsigned int alignsize,
77 unsigned int extrasize,
78 bool dryrun)
79 {
80 const unsigned int blksiz = erofs_blksiz(&sbi);
81 const unsigned int blkmask = blksiz - 1;
82 const erofs_off_t alignedoffset = roundup(bb->buffers.off, alignsize);
83 const int oob = cmpsgn(roundup(((bb->buffers.off - 1) & blkmask) + 1,
84 alignsize) + incr + extrasize, blksiz);
85 bool tailupdate = false;
86 erofs_blk_t blkaddr;
87
88 if (oob >= 0) {
89 /* the next buffer block should be NULL_ADDR all the time */
90 if (oob && list_next_entry(bb, list)->blkaddr != NULL_ADDR)
91 return -EINVAL;
92
93 blkaddr = bb->blkaddr;
94 if (blkaddr != NULL_ADDR) {
95 tailupdate = (tail_blkaddr == blkaddr +
96 DIV_ROUND_UP(bb->buffers.off, blksiz));
97 if (oob && !tailupdate)
98 return -EINVAL;
99 }
100 }
101
102 if (!dryrun) {
103 if (bh) {
104 bh->off = alignedoffset;
105 bh->block = bb;
106 list_add_tail(&bh->list, &bb->buffers.list);
107 }
108 bb->buffers.off = alignedoffset + incr;
109 /* need to update the tail_blkaddr */
110 if (tailupdate)
111 tail_blkaddr = blkaddr +
112 DIV_ROUND_UP(bb->buffers.off, blksiz);
113 erofs_bupdate_mapped(bb);
114 }
115 return ((alignedoffset + incr - 1) & blkmask) + 1;
116 }
117
erofs_bh_balloon(struct erofs_buffer_head * bh,erofs_off_t incr)118 int erofs_bh_balloon(struct erofs_buffer_head *bh, erofs_off_t incr)
119 {
120 struct erofs_buffer_block *const bb = bh->block;
121
122 /* should be the tail bh in the corresponding buffer block */
123 if (bh->list.next != &bb->buffers.list)
124 return -EINVAL;
125
126 return __erofs_battach(bb, NULL, incr, 1, 0, false);
127 }
128
erofs_bfind_for_attach(int type,erofs_off_t size,unsigned int required_ext,unsigned int inline_ext,unsigned int alignsize,struct erofs_buffer_block ** bbp)129 static int erofs_bfind_for_attach(int type, erofs_off_t size,
130 unsigned int required_ext,
131 unsigned int inline_ext,
132 unsigned int alignsize,
133 struct erofs_buffer_block **bbp)
134 {
135 const unsigned int blksiz = erofs_blksiz(&sbi);
136 struct erofs_buffer_block *cur, *bb;
137 unsigned int used0, used_before, usedmax, used;
138 int ret;
139
140 used0 = ((size + required_ext) & (blksiz - 1)) + inline_ext;
141 /* inline data should be in the same fs block */
142 if (used0 > blksiz)
143 return -ENOSPC;
144
145 if (!used0 || alignsize == blksiz) {
146 *bbp = NULL;
147 return 0;
148 }
149
150 usedmax = 0;
151 bb = NULL;
152
153 /* try to find a most-fit mapped buffer block first */
154 if (size + required_ext + inline_ext >= blksiz)
155 goto skip_mapped;
156
157 used_before = rounddown(blksiz -
158 (size + required_ext + inline_ext), alignsize);
159 for (; used_before; --used_before) {
160 struct list_head *bt = mapped_buckets[type] + used_before;
161
162 if (list_empty(bt))
163 continue;
164 cur = list_first_entry(bt, struct erofs_buffer_block,
165 mapped_list);
166
167 /* last mapped block can be expended, don't handle it here */
168 if (list_next_entry(cur, list)->blkaddr == NULL_ADDR) {
169 DBG_BUGON(cur != last_mapped_block);
170 continue;
171 }
172
173 DBG_BUGON(cur->type != type);
174 DBG_BUGON(cur->blkaddr == NULL_ADDR);
175 DBG_BUGON(used_before != (cur->buffers.off & (blksiz - 1)));
176
177 ret = __erofs_battach(cur, NULL, size, alignsize,
178 required_ext + inline_ext, true);
179 if (ret < 0) {
180 DBG_BUGON(1);
181 continue;
182 }
183
184 /* should contain all data in the current block */
185 used = ret + required_ext + inline_ext;
186 DBG_BUGON(used > blksiz);
187
188 bb = cur;
189 usedmax = used;
190 break;
191 }
192
193 skip_mapped:
194 /* try to start from the last mapped one, which can be expended */
195 cur = last_mapped_block;
196 if (cur == &blkh)
197 cur = list_next_entry(cur, list);
198 for (; cur != &blkh; cur = list_next_entry(cur, list)) {
199 used_before = cur->buffers.off & (blksiz - 1);
200
201 /* skip if buffer block is just full */
202 if (!used_before)
203 continue;
204
205 /* skip if the entry which has different type */
206 if (cur->type != type)
207 continue;
208
209 ret = __erofs_battach(cur, NULL, size, alignsize,
210 required_ext + inline_ext, true);
211 if (ret < 0)
212 continue;
213
214 used = ((ret + required_ext) & (blksiz - 1)) + inline_ext;
215
216 /* should contain inline data in current block */
217 if (used > blksiz)
218 continue;
219
220 /*
221 * remaining should be smaller than before or
222 * larger than allocating a new buffer block
223 */
224 if (used < used_before && used < used0)
225 continue;
226
227 if (usedmax < used) {
228 bb = cur;
229 usedmax = used;
230 }
231 }
232 *bbp = bb;
233 return 0;
234 }
235
erofs_balloc(int type,erofs_off_t size,unsigned int required_ext,unsigned int inline_ext)236 struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
237 unsigned int required_ext,
238 unsigned int inline_ext)
239 {
240 struct erofs_buffer_block *bb;
241 struct erofs_buffer_head *bh;
242 unsigned int alignsize;
243
244 int ret = get_alignsize(type, &type);
245
246 if (ret < 0)
247 return ERR_PTR(ret);
248
249 DBG_BUGON(type < 0 || type > META);
250 alignsize = ret;
251
252 /* try to find if we could reuse an allocated buffer block */
253 ret = erofs_bfind_for_attach(type, size, required_ext, inline_ext,
254 alignsize, &bb);
255 if (ret)
256 return ERR_PTR(ret);
257
258 if (bb) {
259 bh = malloc(sizeof(struct erofs_buffer_head));
260 if (!bh)
261 return ERR_PTR(-ENOMEM);
262 } else {
263 /* get a new buffer block instead */
264 bb = malloc(sizeof(struct erofs_buffer_block));
265 if (!bb)
266 return ERR_PTR(-ENOMEM);
267
268 bb->type = type;
269 bb->blkaddr = NULL_ADDR;
270 bb->buffers.off = 0;
271 init_list_head(&bb->buffers.list);
272 if (type == DATA)
273 list_add(&bb->list, &last_mapped_block->list);
274 else
275 list_add_tail(&bb->list, &blkh.list);
276 init_list_head(&bb->mapped_list);
277
278 bh = malloc(sizeof(struct erofs_buffer_head));
279 if (!bh) {
280 free(bb);
281 return ERR_PTR(-ENOMEM);
282 }
283 }
284
285 ret = __erofs_battach(bb, bh, size, alignsize,
286 required_ext + inline_ext, false);
287 if (ret < 0) {
288 free(bh);
289 return ERR_PTR(ret);
290 }
291 return bh;
292 }
293
erofs_battach(struct erofs_buffer_head * bh,int type,unsigned int size)294 struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
295 int type, unsigned int size)
296 {
297 struct erofs_buffer_block *const bb = bh->block;
298 struct erofs_buffer_head *nbh;
299 unsigned int alignsize;
300 int ret = get_alignsize(type, &type);
301
302 if (ret < 0)
303 return ERR_PTR(ret);
304 alignsize = ret;
305
306 /* should be the tail bh in the corresponding buffer block */
307 if (bh->list.next != &bb->buffers.list)
308 return ERR_PTR(-EINVAL);
309
310 nbh = malloc(sizeof(*nbh));
311 if (!nbh)
312 return ERR_PTR(-ENOMEM);
313
314 ret = __erofs_battach(bb, nbh, size, alignsize, 0, false);
315 if (ret < 0) {
316 free(nbh);
317 return ERR_PTR(ret);
318 }
319 return nbh;
320 }
321
__erofs_mapbh(struct erofs_buffer_block * bb)322 static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
323 {
324 erofs_blk_t blkaddr;
325
326 if (bb->blkaddr == NULL_ADDR) {
327 bb->blkaddr = tail_blkaddr;
328 last_mapped_block = bb;
329 erofs_bupdate_mapped(bb);
330 }
331
332 blkaddr = bb->blkaddr + BLK_ROUND_UP(&sbi, bb->buffers.off);
333 if (blkaddr > tail_blkaddr)
334 tail_blkaddr = blkaddr;
335
336 return blkaddr;
337 }
338
erofs_mapbh(struct erofs_buffer_block * bb)339 erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
340 {
341 struct erofs_buffer_block *t = last_mapped_block;
342
343 if (bb && bb->blkaddr != NULL_ADDR)
344 return bb->blkaddr;
345 do {
346 t = list_next_entry(t, list);
347 if (t == &blkh)
348 break;
349
350 DBG_BUGON(t->blkaddr != NULL_ADDR);
351 (void)__erofs_mapbh(t);
352 } while (t != bb);
353 return tail_blkaddr;
354 }
355
erofs_bfree(struct erofs_buffer_block * bb)356 static void erofs_bfree(struct erofs_buffer_block *bb)
357 {
358 DBG_BUGON(!list_empty(&bb->buffers.list));
359
360 if (bb == last_mapped_block)
361 last_mapped_block = list_prev_entry(bb, list);
362
363 list_del(&bb->mapped_list);
364 list_del(&bb->list);
365 free(bb);
366 }
367
erofs_bflush(struct erofs_buffer_block * bb)368 bool erofs_bflush(struct erofs_buffer_block *bb)
369 {
370 const unsigned int blksiz = erofs_blksiz(&sbi);
371 struct erofs_buffer_block *p, *n;
372 erofs_blk_t blkaddr;
373
374 list_for_each_entry_safe(p, n, &blkh.list, list) {
375 struct erofs_buffer_head *bh, *nbh;
376 unsigned int padding;
377 bool skip = false;
378
379 if (p == bb)
380 break;
381
382 /* check if the buffer block can flush */
383 list_for_each_entry(bh, &p->buffers.list, list)
384 if (bh->op->preflush && !bh->op->preflush(bh))
385 return false;
386
387 blkaddr = __erofs_mapbh(p);
388
389 list_for_each_entry_safe(bh, nbh, &p->buffers.list, list) {
390 /* flush and remove bh */
391 if (!bh->op->flush(bh))
392 skip = true;
393 }
394
395 if (skip)
396 continue;
397
398 padding = blksiz - (p->buffers.off & (blksiz - 1));
399 if (padding != blksiz)
400 dev_fillzero(&sbi, erofs_pos(&sbi, blkaddr) - padding,
401 padding, true);
402
403 if (p->type != DATA)
404 erofs_metablkcnt += BLK_ROUND_UP(&sbi, p->buffers.off);
405 erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
406 erofs_bfree(p);
407 }
408 return true;
409 }
410
erofs_bdrop(struct erofs_buffer_head * bh,bool tryrevoke)411 void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
412 {
413 struct erofs_buffer_block *const bb = bh->block;
414 const erofs_blk_t blkaddr = bh->block->blkaddr;
415 bool rollback = false;
416
417 /* tail_blkaddr could be rolled back after revoking all bhs */
418 if (tryrevoke && blkaddr != NULL_ADDR &&
419 tail_blkaddr == blkaddr + BLK_ROUND_UP(&sbi, bb->buffers.off))
420 rollback = true;
421
422 bh->op = &erofs_drop_directly_bhops;
423 erofs_bh_flush_generic_end(bh);
424
425 if (!list_empty(&bb->buffers.list))
426 return;
427
428 if (!rollback && bb->type != DATA)
429 erofs_metablkcnt += BLK_ROUND_UP(&sbi, bb->buffers.off);
430 erofs_bfree(bb);
431 if (rollback)
432 tail_blkaddr = blkaddr;
433 }
434
erofs_total_metablocks(void)435 erofs_blk_t erofs_total_metablocks(void)
436 {
437 return erofs_metablkcnt;
438 }
439