1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * This file is part of UBIFS. |
4 | * |
5 | * Copyright (C) 2006-2008 Nokia Corporation. |
6 | * |
7 | * Authors: Artem Bityutskiy (Битюцкий Артём) |
8 | * Adrian Hunter |
9 | */ |
10 | |
11 | /* |
12 | * This file contains functions for finding LEBs for various purposes e.g. |
13 | * garbage collection. In general, lprops category heaps and lists are used |
14 | * for fast access, falling back on scanning the LPT as a last resort. |
15 | */ |
16 | |
17 | #include <linux/sort.h> |
18 | #include "ubifs.h" |
19 | |
20 | /** |
21 | * struct scan_data - data provided to scan callback functions |
22 | * @min_space: minimum number of bytes for which to scan |
23 | * @pick_free: whether it is OK to scan for empty LEBs |
24 | * @lnum: LEB number found is returned here |
25 | * @exclude_index: whether to exclude index LEBs |
26 | */ |
27 | struct scan_data { |
28 | int min_space; |
29 | int pick_free; |
30 | int lnum; |
31 | int exclude_index; |
32 | }; |
33 | |
34 | /** |
35 | * valuable - determine whether LEB properties are valuable. |
36 | * @c: the UBIFS file-system description object |
37 | * @lprops: LEB properties |
38 | * |
39 | * This function return %1 if the LEB properties should be added to the LEB |
40 | * properties tree in memory. Otherwise %0 is returned. |
41 | */ |
42 | static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops) |
43 | { |
44 | int n, cat = lprops->flags & LPROPS_CAT_MASK; |
45 | struct ubifs_lpt_heap *heap; |
46 | |
47 | switch (cat) { |
48 | case LPROPS_DIRTY: |
49 | case LPROPS_DIRTY_IDX: |
50 | case LPROPS_FREE: |
51 | heap = &c->lpt_heap[cat - 1]; |
52 | if (heap->cnt < heap->max_cnt) |
53 | return 1; |
54 | if (lprops->free + lprops->dirty >= c->dark_wm) |
55 | return 1; |
56 | return 0; |
57 | case LPROPS_EMPTY: |
58 | n = c->lst.empty_lebs + c->freeable_cnt - |
59 | c->lst.taken_empty_lebs; |
60 | if (n < c->lsave_cnt) |
61 | return 1; |
62 | return 0; |
63 | case LPROPS_FREEABLE: |
64 | return 1; |
65 | case LPROPS_FRDI_IDX: |
66 | return 1; |
67 | } |
68 | return 0; |
69 | } |
70 | |
71 | /** |
72 | * scan_for_dirty_cb - dirty space scan callback. |
73 | * @c: the UBIFS file-system description object |
74 | * @lprops: LEB properties to scan |
75 | * @in_tree: whether the LEB properties are in main memory |
76 | * @data: information passed to and from the caller of the scan |
77 | * |
78 | * This function returns a code that indicates whether the scan should continue |
79 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree |
80 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop |
81 | * (%LPT_SCAN_STOP). |
82 | */ |
83 | static int scan_for_dirty_cb(struct ubifs_info *c, |
84 | const struct ubifs_lprops *lprops, int in_tree, |
85 | struct scan_data *data) |
86 | { |
87 | int ret = LPT_SCAN_CONTINUE; |
88 | |
89 | /* Exclude LEBs that are currently in use */ |
90 | if (lprops->flags & LPROPS_TAKEN) |
91 | return LPT_SCAN_CONTINUE; |
92 | /* Determine whether to add these LEB properties to the tree */ |
93 | if (!in_tree && valuable(c, lprops)) |
94 | ret |= LPT_SCAN_ADD; |
95 | /* Exclude LEBs with too little space */ |
96 | if (lprops->free + lprops->dirty < data->min_space) |
97 | return ret; |
98 | /* If specified, exclude index LEBs */ |
99 | if (data->exclude_index && lprops->flags & LPROPS_INDEX) |
100 | return ret; |
101 | /* If specified, exclude empty or freeable LEBs */ |
102 | if (lprops->free + lprops->dirty == c->leb_size) { |
103 | if (!data->pick_free) |
104 | return ret; |
105 | /* Exclude LEBs with too little dirty space (unless it is empty) */ |
106 | } else if (lprops->dirty < c->dead_wm) |
107 | return ret; |
108 | /* Finally we found space */ |
109 | data->lnum = lprops->lnum; |
110 | return LPT_SCAN_ADD | LPT_SCAN_STOP; |
111 | } |
112 | |
113 | /** |
114 | * scan_for_dirty - find a data LEB with free space. |
115 | * @c: the UBIFS file-system description object |
116 | * @min_space: minimum amount free plus dirty space the returned LEB has to |
117 | * have |
118 | * @pick_free: if it is OK to return a free or freeable LEB |
119 | * @exclude_index: whether to exclude index LEBs |
120 | * |
121 | * This function returns a pointer to the LEB properties found or a negative |
122 | * error code. |
123 | */ |
124 | static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c, |
125 | int min_space, int pick_free, |
126 | int exclude_index) |
127 | { |
128 | const struct ubifs_lprops *lprops; |
129 | struct ubifs_lpt_heap *heap; |
130 | struct scan_data data; |
131 | int err, i; |
132 | |
133 | /* There may be an LEB with enough dirty space on the free heap */ |
134 | heap = &c->lpt_heap[LPROPS_FREE - 1]; |
135 | for (i = 0; i < heap->cnt; i++) { |
136 | lprops = heap->arr[i]; |
137 | if (lprops->free + lprops->dirty < min_space) |
138 | continue; |
139 | if (lprops->dirty < c->dead_wm) |
140 | continue; |
141 | return lprops; |
142 | } |
143 | /* |
144 | * A LEB may have fallen off of the bottom of the dirty heap, and ended |
145 | * up as uncategorized even though it has enough dirty space for us now, |
146 | * so check the uncategorized list. N.B. neither empty nor freeable LEBs |
147 | * can end up as uncategorized because they are kept on lists not |
148 | * finite-sized heaps. |
149 | */ |
150 | list_for_each_entry(lprops, &c->uncat_list, list) { |
151 | if (lprops->flags & LPROPS_TAKEN) |
152 | continue; |
153 | if (lprops->free + lprops->dirty < min_space) |
154 | continue; |
155 | if (exclude_index && (lprops->flags & LPROPS_INDEX)) |
156 | continue; |
157 | if (lprops->dirty < c->dead_wm) |
158 | continue; |
159 | return lprops; |
160 | } |
161 | /* We have looked everywhere in main memory, now scan the flash */ |
162 | if (c->pnodes_have >= c->pnode_cnt) |
163 | /* All pnodes are in memory, so skip scan */ |
164 | return ERR_PTR(error: -ENOSPC); |
165 | data.min_space = min_space; |
166 | data.pick_free = pick_free; |
167 | data.lnum = -1; |
168 | data.exclude_index = exclude_index; |
169 | err = ubifs_lpt_scan_nolock(c, start_lnum: -1, end_lnum: c->lscan_lnum, |
170 | scan_cb: (ubifs_lpt_scan_callback)scan_for_dirty_cb, |
171 | data: &data); |
172 | if (err) |
173 | return ERR_PTR(error: err); |
174 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
175 | c->lscan_lnum = data.lnum; |
176 | lprops = ubifs_lpt_lookup_dirty(c, lnum: data.lnum); |
177 | if (IS_ERR(ptr: lprops)) |
178 | return lprops; |
179 | ubifs_assert(c, lprops->lnum == data.lnum); |
180 | ubifs_assert(c, lprops->free + lprops->dirty >= min_space); |
181 | ubifs_assert(c, lprops->dirty >= c->dead_wm || |
182 | (pick_free && |
183 | lprops->free + lprops->dirty == c->leb_size)); |
184 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); |
185 | ubifs_assert(c, !exclude_index || !(lprops->flags & LPROPS_INDEX)); |
186 | return lprops; |
187 | } |
188 | |
189 | /** |
190 | * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector. |
191 | * @c: the UBIFS file-system description object |
192 | * @ret_lp: LEB properties are returned here on exit |
193 | * @min_space: minimum amount free plus dirty space the returned LEB has to |
194 | * have |
195 | * @pick_free: controls whether it is OK to pick empty or index LEBs |
196 | * |
197 | * This function tries to find a dirty logical eraseblock which has at least |
198 | * @min_space free and dirty space. It prefers to take an LEB from the dirty or |
199 | * dirty index heap, and it falls-back to LPT scanning if the heaps are empty |
200 | * or do not have an LEB which satisfies the @min_space criteria. |
201 | * |
202 | * Note, LEBs which have less than dead watermark of free + dirty space are |
203 | * never picked by this function. |
204 | * |
205 | * The additional @pick_free argument controls if this function has to return a |
206 | * free or freeable LEB if one is present. For example, GC must to set it to %1, |
207 | * when called from the journal space reservation function, because the |
208 | * appearance of free space may coincide with the loss of enough dirty space |
209 | * for GC to succeed anyway. |
210 | * |
211 | * In contrast, if the Garbage Collector is called from budgeting, it should |
212 | * just make free space, not return LEBs which are already free or freeable. |
213 | * |
214 | * In addition @pick_free is set to %2 by the recovery process in order to |
215 | * recover gc_lnum in which case an index LEB must not be returned. |
216 | * |
217 | * This function returns zero and the LEB properties of found dirty LEB in case |
218 | * of success, %-ENOSPC if no dirty LEB was found and a negative error code in |
219 | * case of other failures. The returned LEB is marked as "taken". |
220 | */ |
221 | int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp, |
222 | int min_space, int pick_free) |
223 | { |
224 | int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0; |
225 | const struct ubifs_lprops *lp = NULL, *idx_lp = NULL; |
226 | struct ubifs_lpt_heap *heap, *idx_heap; |
227 | |
228 | ubifs_get_lprops(c); |
229 | |
230 | if (pick_free) { |
231 | int lebs, rsvd_idx_lebs = 0; |
232 | |
233 | spin_lock(lock: &c->space_lock); |
234 | lebs = c->lst.empty_lebs + c->idx_gc_cnt; |
235 | lebs += c->freeable_cnt - c->lst.taken_empty_lebs; |
236 | |
237 | /* |
238 | * Note, the index may consume more LEBs than have been reserved |
239 | * for it. It is OK because it might be consolidated by GC. |
240 | * But if the index takes fewer LEBs than it is reserved for it, |
241 | * this function must avoid picking those reserved LEBs. |
242 | */ |
243 | if (c->bi.min_idx_lebs >= c->lst.idx_lebs) { |
244 | rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; |
245 | exclude_index = 1; |
246 | } |
247 | spin_unlock(lock: &c->space_lock); |
248 | |
249 | /* Check if there are enough free LEBs for the index */ |
250 | if (rsvd_idx_lebs < lebs) { |
251 | /* OK, try to find an empty LEB */ |
252 | lp = ubifs_fast_find_empty(c); |
253 | if (lp) |
254 | goto found; |
255 | |
256 | /* Or a freeable LEB */ |
257 | lp = ubifs_fast_find_freeable(c); |
258 | if (lp) |
259 | goto found; |
260 | } else |
261 | /* |
262 | * We cannot pick free/freeable LEBs in the below code. |
263 | */ |
264 | pick_free = 0; |
265 | } else { |
266 | spin_lock(lock: &c->space_lock); |
267 | exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs); |
268 | spin_unlock(lock: &c->space_lock); |
269 | } |
270 | |
271 | /* Look on the dirty and dirty index heaps */ |
272 | heap = &c->lpt_heap[LPROPS_DIRTY - 1]; |
273 | idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; |
274 | |
275 | if (idx_heap->cnt && !exclude_index) { |
276 | idx_lp = idx_heap->arr[0]; |
277 | sum = idx_lp->free + idx_lp->dirty; |
278 | /* |
279 | * Since we reserve thrice as much space for the index than it |
280 | * actually takes, it does not make sense to pick indexing LEBs |
281 | * with less than, say, half LEB of dirty space. May be half is |
282 | * not the optimal boundary - this should be tested and |
283 | * checked. This boundary should determine how much we use |
284 | * in-the-gaps to consolidate the index comparing to how much |
285 | * we use garbage collector to consolidate it. The "half" |
286 | * criteria just feels to be fine. |
287 | */ |
288 | if (sum < min_space || sum < c->half_leb_size) |
289 | idx_lp = NULL; |
290 | } |
291 | |
292 | if (heap->cnt) { |
293 | lp = heap->arr[0]; |
294 | if (lp->dirty + lp->free < min_space) |
295 | lp = NULL; |
296 | } |
297 | |
298 | /* Pick the LEB with most space */ |
299 | if (idx_lp && lp) { |
300 | if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty) |
301 | lp = idx_lp; |
302 | } else if (idx_lp && !lp) |
303 | lp = idx_lp; |
304 | |
305 | if (lp) { |
306 | ubifs_assert(c, lp->free + lp->dirty >= c->dead_wm); |
307 | goto found; |
308 | } |
309 | |
310 | /* Did not find a dirty LEB on the dirty heaps, have to scan */ |
311 | dbg_find("scanning LPT for a dirty LEB" ); |
312 | lp = scan_for_dirty(c, min_space, pick_free, exclude_index); |
313 | if (IS_ERR(ptr: lp)) { |
314 | err = PTR_ERR(ptr: lp); |
315 | goto out; |
316 | } |
317 | ubifs_assert(c, lp->dirty >= c->dead_wm || |
318 | (pick_free && lp->free + lp->dirty == c->leb_size)); |
319 | |
320 | found: |
321 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x" , |
322 | lp->lnum, lp->free, lp->dirty, lp->flags); |
323 | |
324 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, |
325 | flags: lp->flags | LPROPS_TAKEN, idx_gc_cnt: 0); |
326 | if (IS_ERR(ptr: lp)) { |
327 | err = PTR_ERR(ptr: lp); |
328 | goto out; |
329 | } |
330 | |
331 | memcpy(ret_lp, lp, sizeof(struct ubifs_lprops)); |
332 | |
333 | out: |
334 | ubifs_release_lprops(c); |
335 | return err; |
336 | } |
337 | |
338 | /** |
339 | * scan_for_free_cb - free space scan callback. |
340 | * @c: the UBIFS file-system description object |
341 | * @lprops: LEB properties to scan |
342 | * @in_tree: whether the LEB properties are in main memory |
343 | * @data: information passed to and from the caller of the scan |
344 | * |
345 | * This function returns a code that indicates whether the scan should continue |
346 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree |
347 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop |
348 | * (%LPT_SCAN_STOP). |
349 | */ |
350 | static int scan_for_free_cb(struct ubifs_info *c, |
351 | const struct ubifs_lprops *lprops, int in_tree, |
352 | struct scan_data *data) |
353 | { |
354 | int ret = LPT_SCAN_CONTINUE; |
355 | |
356 | /* Exclude LEBs that are currently in use */ |
357 | if (lprops->flags & LPROPS_TAKEN) |
358 | return LPT_SCAN_CONTINUE; |
359 | /* Determine whether to add these LEB properties to the tree */ |
360 | if (!in_tree && valuable(c, lprops)) |
361 | ret |= LPT_SCAN_ADD; |
362 | /* Exclude index LEBs */ |
363 | if (lprops->flags & LPROPS_INDEX) |
364 | return ret; |
365 | /* Exclude LEBs with too little space */ |
366 | if (lprops->free < data->min_space) |
367 | return ret; |
368 | /* If specified, exclude empty LEBs */ |
369 | if (!data->pick_free && lprops->free == c->leb_size) |
370 | return ret; |
371 | /* |
372 | * LEBs that have only free and dirty space must not be allocated |
373 | * because they may have been unmapped already or they may have data |
374 | * that is obsolete only because of nodes that are still sitting in a |
375 | * wbuf. |
376 | */ |
377 | if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0) |
378 | return ret; |
379 | /* Finally we found space */ |
380 | data->lnum = lprops->lnum; |
381 | return LPT_SCAN_ADD | LPT_SCAN_STOP; |
382 | } |
383 | |
384 | /** |
385 | * do_find_free_space - find a data LEB with free space. |
386 | * @c: the UBIFS file-system description object |
387 | * @min_space: minimum amount of free space required |
388 | * @pick_free: whether it is OK to scan for empty LEBs |
389 | * @squeeze: whether to try to find space in a non-empty LEB first |
390 | * |
391 | * This function returns a pointer to the LEB properties found or a negative |
392 | * error code. |
393 | */ |
394 | static |
395 | const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c, |
396 | int min_space, int pick_free, |
397 | int squeeze) |
398 | { |
399 | const struct ubifs_lprops *lprops; |
400 | struct ubifs_lpt_heap *heap; |
401 | struct scan_data data; |
402 | int err, i; |
403 | |
404 | if (squeeze) { |
405 | lprops = ubifs_fast_find_free(c); |
406 | if (lprops && lprops->free >= min_space) |
407 | return lprops; |
408 | } |
409 | if (pick_free) { |
410 | lprops = ubifs_fast_find_empty(c); |
411 | if (lprops) |
412 | return lprops; |
413 | } |
414 | if (!squeeze) { |
415 | lprops = ubifs_fast_find_free(c); |
416 | if (lprops && lprops->free >= min_space) |
417 | return lprops; |
418 | } |
419 | /* There may be an LEB with enough free space on the dirty heap */ |
420 | heap = &c->lpt_heap[LPROPS_DIRTY - 1]; |
421 | for (i = 0; i < heap->cnt; i++) { |
422 | lprops = heap->arr[i]; |
423 | if (lprops->free >= min_space) |
424 | return lprops; |
425 | } |
426 | /* |
427 | * A LEB may have fallen off of the bottom of the free heap, and ended |
428 | * up as uncategorized even though it has enough free space for us now, |
429 | * so check the uncategorized list. N.B. neither empty nor freeable LEBs |
430 | * can end up as uncategorized because they are kept on lists not |
431 | * finite-sized heaps. |
432 | */ |
433 | list_for_each_entry(lprops, &c->uncat_list, list) { |
434 | if (lprops->flags & LPROPS_TAKEN) |
435 | continue; |
436 | if (lprops->flags & LPROPS_INDEX) |
437 | continue; |
438 | if (lprops->free >= min_space) |
439 | return lprops; |
440 | } |
441 | /* We have looked everywhere in main memory, now scan the flash */ |
442 | if (c->pnodes_have >= c->pnode_cnt) |
443 | /* All pnodes are in memory, so skip scan */ |
444 | return ERR_PTR(error: -ENOSPC); |
445 | data.min_space = min_space; |
446 | data.pick_free = pick_free; |
447 | data.lnum = -1; |
448 | err = ubifs_lpt_scan_nolock(c, start_lnum: -1, end_lnum: c->lscan_lnum, |
449 | scan_cb: (ubifs_lpt_scan_callback)scan_for_free_cb, |
450 | data: &data); |
451 | if (err) |
452 | return ERR_PTR(error: err); |
453 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
454 | c->lscan_lnum = data.lnum; |
455 | lprops = ubifs_lpt_lookup_dirty(c, lnum: data.lnum); |
456 | if (IS_ERR(ptr: lprops)) |
457 | return lprops; |
458 | ubifs_assert(c, lprops->lnum == data.lnum); |
459 | ubifs_assert(c, lprops->free >= min_space); |
460 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); |
461 | ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); |
462 | return lprops; |
463 | } |
464 | |
465 | /** |
466 | * ubifs_find_free_space - find a data LEB with free space. |
467 | * @c: the UBIFS file-system description object |
468 | * @min_space: minimum amount of required free space |
469 | * @offs: contains offset of where free space starts on exit |
470 | * @squeeze: whether to try to find space in a non-empty LEB first |
471 | * |
472 | * This function looks for an LEB with at least @min_space bytes of free space. |
473 | * It tries to find an empty LEB if possible. If no empty LEBs are available, |
474 | * this function searches for a non-empty data LEB. The returned LEB is marked |
475 | * as "taken". |
476 | * |
477 | * This function returns found LEB number in case of success, %-ENOSPC if it |
478 | * failed to find a LEB with @min_space bytes of free space and other a negative |
479 | * error codes in case of failure. |
480 | */ |
481 | int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs, |
482 | int squeeze) |
483 | { |
484 | const struct ubifs_lprops *lprops; |
485 | int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags; |
486 | |
487 | dbg_find("min_space %d" , min_space); |
488 | ubifs_get_lprops(c); |
489 | |
490 | /* Check if there are enough empty LEBs for commit */ |
491 | spin_lock(lock: &c->space_lock); |
492 | if (c->bi.min_idx_lebs > c->lst.idx_lebs) |
493 | rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; |
494 | else |
495 | rsvd_idx_lebs = 0; |
496 | lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - |
497 | c->lst.taken_empty_lebs; |
498 | if (rsvd_idx_lebs < lebs) |
499 | /* |
500 | * OK to allocate an empty LEB, but we still don't want to go |
501 | * looking for one if there aren't any. |
502 | */ |
503 | if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { |
504 | pick_free = 1; |
505 | /* |
506 | * Because we release the space lock, we must account |
507 | * for this allocation here. After the LEB properties |
508 | * flags have been updated, we subtract one. Note, the |
509 | * result of this is that lprops also decreases |
510 | * @taken_empty_lebs in 'ubifs_change_lp()', so it is |
511 | * off by one for a short period of time which may |
512 | * introduce a small disturbance to budgeting |
513 | * calculations, but this is harmless because at the |
514 | * worst case this would make the budgeting subsystem |
515 | * be more pessimistic than needed. |
516 | * |
517 | * Fundamentally, this is about serialization of the |
518 | * budgeting and lprops subsystems. We could make the |
519 | * @space_lock a mutex and avoid dropping it before |
520 | * calling 'ubifs_change_lp()', but mutex is more |
521 | * heavy-weight, and we want budgeting to be as fast as |
522 | * possible. |
523 | */ |
524 | c->lst.taken_empty_lebs += 1; |
525 | } |
526 | spin_unlock(lock: &c->space_lock); |
527 | |
528 | lprops = do_find_free_space(c, min_space, pick_free, squeeze); |
529 | if (IS_ERR(ptr: lprops)) { |
530 | err = PTR_ERR(ptr: lprops); |
531 | goto out; |
532 | } |
533 | |
534 | lnum = lprops->lnum; |
535 | flags = lprops->flags | LPROPS_TAKEN; |
536 | |
537 | lprops = ubifs_change_lp(c, lp: lprops, LPROPS_NC, LPROPS_NC, flags, idx_gc_cnt: 0); |
538 | if (IS_ERR(ptr: lprops)) { |
539 | err = PTR_ERR(ptr: lprops); |
540 | goto out; |
541 | } |
542 | |
543 | if (pick_free) { |
544 | spin_lock(lock: &c->space_lock); |
545 | c->lst.taken_empty_lebs -= 1; |
546 | spin_unlock(lock: &c->space_lock); |
547 | } |
548 | |
549 | *offs = c->leb_size - lprops->free; |
550 | ubifs_release_lprops(c); |
551 | |
552 | if (*offs == 0) { |
553 | /* |
554 | * Ensure that empty LEBs have been unmapped. They may not have |
555 | * been, for example, because of an unclean unmount. Also |
556 | * LEBs that were freeable LEBs (free + dirty == leb_size) will |
557 | * not have been unmapped. |
558 | */ |
559 | err = ubifs_leb_unmap(c, lnum); |
560 | if (err) |
561 | return err; |
562 | } |
563 | |
564 | dbg_find("found LEB %d, free %d" , lnum, c->leb_size - *offs); |
565 | ubifs_assert(c, *offs <= c->leb_size - min_space); |
566 | return lnum; |
567 | |
568 | out: |
569 | if (pick_free) { |
570 | spin_lock(lock: &c->space_lock); |
571 | c->lst.taken_empty_lebs -= 1; |
572 | spin_unlock(lock: &c->space_lock); |
573 | } |
574 | ubifs_release_lprops(c); |
575 | return err; |
576 | } |
577 | |
578 | /** |
579 | * scan_for_idx_cb - callback used by the scan for a free LEB for the index. |
580 | * @c: the UBIFS file-system description object |
581 | * @lprops: LEB properties to scan |
582 | * @in_tree: whether the LEB properties are in main memory |
583 | * @data: information passed to and from the caller of the scan |
584 | * |
585 | * This function returns a code that indicates whether the scan should continue |
586 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree |
587 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop |
588 | * (%LPT_SCAN_STOP). |
589 | */ |
590 | static int scan_for_idx_cb(struct ubifs_info *c, |
591 | const struct ubifs_lprops *lprops, int in_tree, |
592 | struct scan_data *data) |
593 | { |
594 | int ret = LPT_SCAN_CONTINUE; |
595 | |
596 | /* Exclude LEBs that are currently in use */ |
597 | if (lprops->flags & LPROPS_TAKEN) |
598 | return LPT_SCAN_CONTINUE; |
599 | /* Determine whether to add these LEB properties to the tree */ |
600 | if (!in_tree && valuable(c, lprops)) |
601 | ret |= LPT_SCAN_ADD; |
602 | /* Exclude index LEBS */ |
603 | if (lprops->flags & LPROPS_INDEX) |
604 | return ret; |
605 | /* Exclude LEBs that cannot be made empty */ |
606 | if (lprops->free + lprops->dirty != c->leb_size) |
607 | return ret; |
608 | /* |
609 | * We are allocating for the index so it is safe to allocate LEBs with |
610 | * only free and dirty space, because write buffers are sync'd at commit |
611 | * start. |
612 | */ |
613 | data->lnum = lprops->lnum; |
614 | return LPT_SCAN_ADD | LPT_SCAN_STOP; |
615 | } |
616 | |
617 | /** |
618 | * scan_for_leb_for_idx - scan for a free LEB for the index. |
619 | * @c: the UBIFS file-system description object |
620 | */ |
621 | static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c) |
622 | { |
623 | const struct ubifs_lprops *lprops; |
624 | struct scan_data data; |
625 | int err; |
626 | |
627 | data.lnum = -1; |
628 | err = ubifs_lpt_scan_nolock(c, start_lnum: -1, end_lnum: c->lscan_lnum, |
629 | scan_cb: (ubifs_lpt_scan_callback)scan_for_idx_cb, |
630 | data: &data); |
631 | if (err) |
632 | return ERR_PTR(error: err); |
633 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
634 | c->lscan_lnum = data.lnum; |
635 | lprops = ubifs_lpt_lookup_dirty(c, lnum: data.lnum); |
636 | if (IS_ERR(ptr: lprops)) |
637 | return lprops; |
638 | ubifs_assert(c, lprops->lnum == data.lnum); |
639 | ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size); |
640 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); |
641 | ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); |
642 | return lprops; |
643 | } |
644 | |
645 | /** |
646 | * ubifs_find_free_leb_for_idx - find a free LEB for the index. |
647 | * @c: the UBIFS file-system description object |
648 | * |
649 | * This function looks for a free LEB and returns that LEB number. The returned |
650 | * LEB is marked as "taken", "index". |
651 | * |
652 | * Only empty LEBs are allocated. This is for two reasons. First, the commit |
653 | * calculates the number of LEBs to allocate based on the assumption that they |
654 | * will be empty. Secondly, free space at the end of an index LEB is not |
655 | * guaranteed to be empty because it may have been used by the in-the-gaps |
656 | * method prior to an unclean unmount. |
657 | * |
658 | * If no LEB is found %-ENOSPC is returned. For other failures another negative |
659 | * error code is returned. |
660 | */ |
661 | int ubifs_find_free_leb_for_idx(struct ubifs_info *c) |
662 | { |
663 | const struct ubifs_lprops *lprops; |
664 | int lnum = -1, err, flags; |
665 | |
666 | ubifs_get_lprops(c); |
667 | |
668 | lprops = ubifs_fast_find_empty(c); |
669 | if (!lprops) { |
670 | lprops = ubifs_fast_find_freeable(c); |
671 | if (!lprops) { |
672 | /* |
673 | * The first condition means the following: go scan the |
674 | * LPT if there are uncategorized lprops, which means |
675 | * there may be freeable LEBs there (UBIFS does not |
676 | * store the information about freeable LEBs in the |
677 | * master node). |
678 | */ |
679 | if (c->in_a_category_cnt != c->main_lebs || |
680 | c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { |
681 | ubifs_assert(c, c->freeable_cnt == 0); |
682 | lprops = scan_for_leb_for_idx(c); |
683 | if (IS_ERR(ptr: lprops)) { |
684 | err = PTR_ERR(ptr: lprops); |
685 | goto out; |
686 | } |
687 | } |
688 | } |
689 | } |
690 | |
691 | if (!lprops) { |
692 | err = -ENOSPC; |
693 | goto out; |
694 | } |
695 | |
696 | lnum = lprops->lnum; |
697 | |
698 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x" , |
699 | lnum, lprops->free, lprops->dirty, lprops->flags); |
700 | |
701 | flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; |
702 | lprops = ubifs_change_lp(c, lp: lprops, free: c->leb_size, dirty: 0, flags, idx_gc_cnt: 0); |
703 | if (IS_ERR(ptr: lprops)) { |
704 | err = PTR_ERR(ptr: lprops); |
705 | goto out; |
706 | } |
707 | |
708 | ubifs_release_lprops(c); |
709 | |
710 | /* |
711 | * Ensure that empty LEBs have been unmapped. They may not have been, |
712 | * for example, because of an unclean unmount. Also LEBs that were |
713 | * freeable LEBs (free + dirty == leb_size) will not have been unmapped. |
714 | */ |
715 | err = ubifs_leb_unmap(c, lnum); |
716 | if (err) { |
717 | ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, flags_set: 0, |
718 | flags_clean: LPROPS_TAKEN | LPROPS_INDEX, idx_gc_cnt: 0); |
719 | return err; |
720 | } |
721 | |
722 | return lnum; |
723 | |
724 | out: |
725 | ubifs_release_lprops(c); |
726 | return err; |
727 | } |
728 | |
729 | static int cmp_dirty_idx(const struct ubifs_lprops **a, |
730 | const struct ubifs_lprops **b) |
731 | { |
732 | const struct ubifs_lprops *lpa = *a; |
733 | const struct ubifs_lprops *lpb = *b; |
734 | |
735 | return lpa->dirty + lpa->free - lpb->dirty - lpb->free; |
736 | } |
737 | |
738 | /** |
739 | * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos. |
740 | * @c: the UBIFS file-system description object |
741 | * |
742 | * This function is called each commit to create an array of LEB numbers of |
743 | * dirty index LEBs sorted in order of dirty and free space. This is used by |
744 | * the in-the-gaps method of TNC commit. |
745 | */ |
746 | int ubifs_save_dirty_idx_lnums(struct ubifs_info *c) |
747 | { |
748 | int i; |
749 | |
750 | ubifs_get_lprops(c); |
751 | /* Copy the LPROPS_DIRTY_IDX heap */ |
752 | c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; |
753 | memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, |
754 | sizeof(void *) * c->dirty_idx.cnt); |
755 | /* Sort it so that the dirtiest is now at the end */ |
756 | sort(base: c->dirty_idx.arr, num: c->dirty_idx.cnt, size: sizeof(void *), |
757 | cmp_func: (int (*)(const void *, const void *))cmp_dirty_idx, NULL); |
758 | dbg_find("found %d dirty index LEBs" , c->dirty_idx.cnt); |
759 | if (c->dirty_idx.cnt) |
760 | dbg_find("dirtiest index LEB is %d with dirty %d and free %d" , |
761 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, |
762 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, |
763 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); |
764 | /* Replace the lprops pointers with LEB numbers */ |
765 | for (i = 0; i < c->dirty_idx.cnt; i++) |
766 | c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; |
767 | ubifs_release_lprops(c); |
768 | return 0; |
769 | } |
770 | |
771 | /** |
772 | * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB. |
773 | * @c: the UBIFS file-system description object |
774 | * @lprops: LEB properties to scan |
775 | * @in_tree: whether the LEB properties are in main memory |
776 | * @data: information passed to and from the caller of the scan |
777 | * |
778 | * This function returns a code that indicates whether the scan should continue |
779 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree |
780 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop |
781 | * (%LPT_SCAN_STOP). |
782 | */ |
783 | static int scan_dirty_idx_cb(struct ubifs_info *c, |
784 | const struct ubifs_lprops *lprops, int in_tree, |
785 | struct scan_data *data) |
786 | { |
787 | int ret = LPT_SCAN_CONTINUE; |
788 | |
789 | /* Exclude LEBs that are currently in use */ |
790 | if (lprops->flags & LPROPS_TAKEN) |
791 | return LPT_SCAN_CONTINUE; |
792 | /* Determine whether to add these LEB properties to the tree */ |
793 | if (!in_tree && valuable(c, lprops)) |
794 | ret |= LPT_SCAN_ADD; |
795 | /* Exclude non-index LEBs */ |
796 | if (!(lprops->flags & LPROPS_INDEX)) |
797 | return ret; |
798 | /* Exclude LEBs with too little space */ |
799 | if (lprops->free + lprops->dirty < c->min_idx_node_sz) |
800 | return ret; |
801 | /* Finally we found space */ |
802 | data->lnum = lprops->lnum; |
803 | return LPT_SCAN_ADD | LPT_SCAN_STOP; |
804 | } |
805 | |
806 | /** |
807 | * find_dirty_idx_leb - find a dirty index LEB. |
808 | * @c: the UBIFS file-system description object |
809 | * |
810 | * This function returns LEB number upon success and a negative error code upon |
811 | * failure. In particular, -ENOSPC is returned if a dirty index LEB is not |
812 | * found. |
813 | * |
814 | * Note that this function scans the entire LPT but it is called very rarely. |
815 | */ |
816 | static int find_dirty_idx_leb(struct ubifs_info *c) |
817 | { |
818 | const struct ubifs_lprops *lprops; |
819 | struct ubifs_lpt_heap *heap; |
820 | struct scan_data data; |
821 | int err, i, ret; |
822 | |
823 | /* Check all structures in memory first */ |
824 | data.lnum = -1; |
825 | heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; |
826 | for (i = 0; i < heap->cnt; i++) { |
827 | lprops = heap->arr[i]; |
828 | ret = scan_dirty_idx_cb(c, lprops, in_tree: 1, data: &data); |
829 | if (ret & LPT_SCAN_STOP) |
830 | goto found; |
831 | } |
832 | list_for_each_entry(lprops, &c->frdi_idx_list, list) { |
833 | ret = scan_dirty_idx_cb(c, lprops, in_tree: 1, data: &data); |
834 | if (ret & LPT_SCAN_STOP) |
835 | goto found; |
836 | } |
837 | list_for_each_entry(lprops, &c->uncat_list, list) { |
838 | ret = scan_dirty_idx_cb(c, lprops, in_tree: 1, data: &data); |
839 | if (ret & LPT_SCAN_STOP) |
840 | goto found; |
841 | } |
842 | if (c->pnodes_have >= c->pnode_cnt) |
843 | /* All pnodes are in memory, so skip scan */ |
844 | return -ENOSPC; |
845 | err = ubifs_lpt_scan_nolock(c, start_lnum: -1, end_lnum: c->lscan_lnum, |
846 | scan_cb: (ubifs_lpt_scan_callback)scan_dirty_idx_cb, |
847 | data: &data); |
848 | if (err) |
849 | return err; |
850 | found: |
851 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
852 | c->lscan_lnum = data.lnum; |
853 | lprops = ubifs_lpt_lookup_dirty(c, lnum: data.lnum); |
854 | if (IS_ERR(ptr: lprops)) |
855 | return PTR_ERR(ptr: lprops); |
856 | ubifs_assert(c, lprops->lnum == data.lnum); |
857 | ubifs_assert(c, lprops->free + lprops->dirty >= c->min_idx_node_sz); |
858 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); |
859 | ubifs_assert(c, (lprops->flags & LPROPS_INDEX)); |
860 | |
861 | dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x" , |
862 | lprops->lnum, lprops->free, lprops->dirty, lprops->flags); |
863 | |
864 | lprops = ubifs_change_lp(c, lp: lprops, LPROPS_NC, LPROPS_NC, |
865 | flags: lprops->flags | LPROPS_TAKEN, idx_gc_cnt: 0); |
866 | if (IS_ERR(ptr: lprops)) |
867 | return PTR_ERR(ptr: lprops); |
868 | |
869 | return lprops->lnum; |
870 | } |
871 | |
872 | /** |
873 | * get_idx_gc_leb - try to get a LEB number from trivial GC. |
874 | * @c: the UBIFS file-system description object |
875 | */ |
876 | static int get_idx_gc_leb(struct ubifs_info *c) |
877 | { |
878 | const struct ubifs_lprops *lp; |
879 | int err, lnum; |
880 | |
881 | err = ubifs_get_idx_gc_leb(c); |
882 | if (err < 0) |
883 | return err; |
884 | lnum = err; |
885 | /* |
886 | * The LEB was due to be unmapped after the commit but |
887 | * it is needed now for this commit. |
888 | */ |
889 | lp = ubifs_lpt_lookup_dirty(c, lnum); |
890 | if (IS_ERR(ptr: lp)) |
891 | return PTR_ERR(ptr: lp); |
892 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, |
893 | flags: lp->flags | LPROPS_INDEX, idx_gc_cnt: -1); |
894 | if (IS_ERR(ptr: lp)) |
895 | return PTR_ERR(ptr: lp); |
896 | dbg_find("LEB %d, dirty %d and free %d flags %#x" , |
897 | lp->lnum, lp->dirty, lp->free, lp->flags); |
898 | return lnum; |
899 | } |
900 | |
901 | /** |
902 | * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array. |
903 | * @c: the UBIFS file-system description object |
904 | */ |
905 | static int find_dirtiest_idx_leb(struct ubifs_info *c) |
906 | { |
907 | const struct ubifs_lprops *lp; |
908 | int lnum; |
909 | |
910 | while (1) { |
911 | if (!c->dirty_idx.cnt) |
912 | return -ENOSPC; |
913 | /* The lprops pointers were replaced by LEB numbers */ |
914 | lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; |
915 | lp = ubifs_lpt_lookup(c, lnum); |
916 | if (IS_ERR(ptr: lp)) |
917 | return PTR_ERR(ptr: lp); |
918 | if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) |
919 | continue; |
920 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, |
921 | flags: lp->flags | LPROPS_TAKEN, idx_gc_cnt: 0); |
922 | if (IS_ERR(ptr: lp)) |
923 | return PTR_ERR(ptr: lp); |
924 | break; |
925 | } |
926 | dbg_find("LEB %d, dirty %d and free %d flags %#x" , lp->lnum, lp->dirty, |
927 | lp->free, lp->flags); |
928 | ubifs_assert(c, lp->flags & LPROPS_TAKEN); |
929 | ubifs_assert(c, lp->flags & LPROPS_INDEX); |
930 | return lnum; |
931 | } |
932 | |
933 | /** |
934 | * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit. |
935 | * @c: the UBIFS file-system description object |
936 | * |
937 | * This function attempts to find an untaken index LEB with the most free and |
938 | * dirty space that can be used without overwriting index nodes that were in the |
939 | * last index committed. |
940 | */ |
941 | int ubifs_find_dirty_idx_leb(struct ubifs_info *c) |
942 | { |
943 | int err; |
944 | |
945 | ubifs_get_lprops(c); |
946 | |
947 | /* |
948 | * We made an array of the dirtiest index LEB numbers as at the start of |
949 | * last commit. Try that array first. |
950 | */ |
951 | err = find_dirtiest_idx_leb(c); |
952 | |
953 | /* Next try scanning the entire LPT */ |
954 | if (err == -ENOSPC) |
955 | err = find_dirty_idx_leb(c); |
956 | |
957 | /* Finally take any index LEBs awaiting trivial GC */ |
958 | if (err == -ENOSPC) |
959 | err = get_idx_gc_leb(c); |
960 | |
961 | ubifs_release_lprops(c); |
962 | return err; |
963 | } |
964 | |