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