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