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(-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, -1, c->lscan_lnum,
170 (ubifs_lpt_scan_callback)scan_for_dirty_cb,
171 &data);
172 if (err)
173 return ERR_PTR(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, data.lnum);
177 if (IS_ERR(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(&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(&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(&c->space_lock);
267 exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs);
268 spin_unlock(&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(lp)) {
314 err = PTR_ERR(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 lp->flags | LPROPS_TAKEN, 0);
326 if (IS_ERR(lp)) {
327 err = PTR_ERR(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(-ENOSPC);
445 data.min_space = min_space;
446 data.pick_free = pick_free;
447 data.lnum = -1;
448 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
449 (ubifs_lpt_scan_callback)scan_for_free_cb,
450 &data);
451 if (err)
452 return ERR_PTR(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, data.lnum);
456 if (IS_ERR(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(&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(&c->space_lock);
527
528 lprops = do_find_free_space(c, min_space, pick_free, squeeze);
529 if (IS_ERR(lprops)) {
530 err = PTR_ERR(lprops);
531 goto out;
532 }
533
534 lnum = lprops->lnum;
535 flags = lprops->flags | LPROPS_TAKEN;
536
537 lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);
538 if (IS_ERR(lprops)) {
539 err = PTR_ERR(lprops);
540 goto out;
541 }
542
543 if (pick_free) {
544 spin_lock(&c->space_lock);
545 c->lst.taken_empty_lebs -= 1;
546 spin_unlock(&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(&c->space_lock);
571 c->lst.taken_empty_lebs -= 1;
572 spin_unlock(&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, -1, c->lscan_lnum,
629 (ubifs_lpt_scan_callback)scan_for_idx_cb,
630 &data);
631 if (err)
632 return ERR_PTR(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, data.lnum);
636 if (IS_ERR(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(lprops)) {
684 err = PTR_ERR(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, lprops, c->leb_size, 0, flags, 0);
703 if (IS_ERR(lprops)) {
704 err = PTR_ERR(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, 0,
718 LPROPS_TAKEN | LPROPS_INDEX, 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(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
757 (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, 1, &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, 1, &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, 1, &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, -1, c->lscan_lnum,
846 (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
847 &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, data.lnum);
854 if (IS_ERR(lprops))
855 return PTR_ERR(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, lprops, LPROPS_NC, LPROPS_NC,
865 lprops->flags | LPROPS_TAKEN, 0);
866 if (IS_ERR(lprops))
867 return PTR_ERR(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(lp))
891 return PTR_ERR(lp);
892 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
893 lp->flags | LPROPS_INDEX, -1);
894 if (IS_ERR(lp))
895 return PTR_ERR(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(lp))
917 return PTR_ERR(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 lp->flags | LPROPS_TAKEN, 0);
922 if (IS_ERR(lp))
923 return PTR_ERR(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 }