]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - fs/ubifs/find.c
2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
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.
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
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
19 * Authors: Artem Bityutskiy (Битюцкий Артём)
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.
29 #include <linux/sort.h>
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
47 * valuable - determine whether LEB properties are valuable.
48 * @c: the UBIFS file-system description object
49 * @lprops: LEB properties
51 * This function return %1 if the LEB properties should be added to the LEB
52 * properties tree in memory. Otherwise %0 is returned.
54 static int valuable(struct ubifs_info
*c
, const struct ubifs_lprops
*lprops
)
56 int n
, cat
= lprops
->flags
& LPROPS_CAT_MASK
;
57 struct ubifs_lpt_heap
*heap
;
61 case LPROPS_DIRTY_IDX
:
63 heap
= &c
->lpt_heap
[cat
- 1];
64 if (heap
->cnt
< heap
->max_cnt
)
66 if (lprops
->free
+ lprops
->dirty
>= c
->dark_wm
)
70 n
= c
->lst
.empty_lebs
+ c
->freeable_cnt
-
71 c
->lst
.taken_empty_lebs
;
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
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
95 static int scan_for_dirty_cb(struct ubifs_info
*c
,
96 const struct ubifs_lprops
*lprops
, int in_tree
,
97 struct scan_data
*data
)
99 int ret
= LPT_SCAN_CONTINUE
;
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
))
107 /* Exclude LEBs with too little space */
108 if (lprops
->free
+ lprops
->dirty
< data
->min_space
)
110 /* If specified, exclude index LEBs */
111 if (data
->exclude_index
&& lprops
->flags
& LPROPS_INDEX
)
113 /* If specified, exclude empty or freeable LEBs */
114 if (lprops
->free
+ lprops
->dirty
== c
->leb_size
) {
115 if (!data
->pick_free
)
117 /* Exclude LEBs with too little dirty space (unless it is empty) */
118 } else if (lprops
->dirty
< c
->dead_wm
)
120 /* Finally we found space */
121 data
->lnum
= lprops
->lnum
;
122 return LPT_SCAN_ADD
| LPT_SCAN_STOP
;
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
130 * @pick_free: if it is OK to return a free or freeable LEB
131 * @exclude_index: whether to exclude index LEBs
133 * This function returns a pointer to the LEB properties found or a negative
136 static const struct ubifs_lprops
*scan_for_dirty(struct ubifs_info
*c
,
137 int min_space
, int pick_free
,
140 const struct ubifs_lprops
*lprops
;
141 struct ubifs_lpt_heap
*heap
;
142 struct scan_data data
;
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
)
151 if (lprops
->dirty
< c
->dead_wm
)
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.
162 list_for_each_entry(lprops
, &c
->uncat_list
, list
) {
163 if (lprops
->flags
& LPROPS_TAKEN
)
165 if (lprops
->free
+ lprops
->dirty
< min_space
)
167 if (exclude_index
&& (lprops
->flags
& LPROPS_INDEX
))
169 if (lprops
->dirty
< c
->dead_wm
)
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
;
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
,
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
);
191 ubifs_assert(lprops
->lnum
== data
.lnum
);
192 ubifs_assert(lprops
->free
+ lprops
->dirty
>= min_space
);
193 ubifs_assert(lprops
->dirty
>= c
->dead_wm
||
195 lprops
->free
+ lprops
->dirty
== c
->leb_size
));
196 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
197 ubifs_assert(!exclude_index
|| !(lprops
->flags
& LPROPS_INDEX
));
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
207 * @pick_free: controls whether it is OK to pick empty or index LEBs
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.
214 * Note, LEBs which have less than dead watermark of free + dirty space are
215 * never picked by this function.
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.
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.
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.
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".
233 int ubifs_find_dirty_leb(struct ubifs_info
*c
, struct ubifs_lprops
*ret_lp
,
234 int min_space
, int pick_free
)
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
;
243 int lebs
, rsvd_idx_lebs
= 0;
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
;
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.
255 if (c
->min_idx_lebs
>= c
->lst
.idx_lebs
) {
256 rsvd_idx_lebs
= c
->min_idx_lebs
- c
->lst
.idx_lebs
;
259 spin_unlock(&c
->space_lock
);
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
);
268 /* Or a freeable LEB */
269 lp
= ubifs_fast_find_freeable(c
);
274 * We cannot pick free/freeable LEBs in the below code.
278 spin_lock(&c
->space_lock
);
279 exclude_index
= (c
->min_idx_lebs
>= c
->lst
.idx_lebs
);
280 spin_unlock(&c
->space_lock
);
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];
287 if (idx_heap
->cnt
&& !exclude_index
) {
288 idx_lp
= idx_heap
->arr
[0];
289 sum
= idx_lp
->free
+ idx_lp
->dirty
;
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.
300 if (sum
< min_space
|| sum
< c
->half_leb_size
)
306 if (lp
->dirty
+ lp
->free
< min_space
)
310 /* Pick the LEB with most space */
312 if (idx_lp
->free
+ idx_lp
->dirty
>= lp
->free
+ lp
->dirty
)
314 } else if (idx_lp
&& !lp
)
318 ubifs_assert(lp
->free
+ lp
->dirty
>= c
->dead_wm
);
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
);
329 ubifs_assert(lp
->dirty
>= c
->dead_wm
||
330 (pick_free
&& lp
->free
+ lp
->dirty
== c
->leb_size
));
333 dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
334 lp
->lnum
, lp
->free
, lp
->dirty
, lp
->flags
);
336 lp
= ubifs_change_lp(c
, lp
, LPROPS_NC
, LPROPS_NC
,
337 lp
->flags
| LPROPS_TAKEN
, 0);
343 memcpy(ret_lp
, lp
, sizeof(struct ubifs_lprops
));
346 ubifs_release_lprops(c
);
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
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
362 static int scan_for_free_cb(struct ubifs_info
*c
,
363 const struct ubifs_lprops
*lprops
, int in_tree
,
364 struct scan_data
*data
)
366 int ret
= LPT_SCAN_CONTINUE
;
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
))
374 /* Exclude index LEBs */
375 if (lprops
->flags
& LPROPS_INDEX
)
377 /* Exclude LEBs with too little space */
378 if (lprops
->free
< data
->min_space
)
380 /* If specified, exclude empty LEBs */
381 if (!data
->pick_free
&& lprops
->free
== c
->leb_size
)
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
389 if (lprops
->free
+ lprops
->dirty
== c
->leb_size
&& lprops
->dirty
> 0)
391 /* Finally we found space */
392 data
->lnum
= lprops
->lnum
;
393 return LPT_SCAN_ADD
| LPT_SCAN_STOP
;
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
403 * This function returns a pointer to the LEB properties found or a negative
407 const struct ubifs_lprops
*do_find_free_space(struct ubifs_info
*c
,
408 int min_space
, int pick_free
,
411 const struct ubifs_lprops
*lprops
;
412 struct ubifs_lpt_heap
*heap
;
413 struct scan_data data
;
417 lprops
= ubifs_fast_find_free(c
);
418 if (lprops
&& lprops
->free
>= min_space
)
422 lprops
= ubifs_fast_find_empty(c
);
427 lprops
= ubifs_fast_find_free(c
);
428 if (lprops
&& lprops
->free
>= min_space
)
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
)
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.
445 list_for_each_entry(lprops
, &c
->uncat_list
, list
) {
446 if (lprops
->flags
& LPROPS_TAKEN
)
448 if (lprops
->flags
& LPROPS_INDEX
)
450 if (lprops
->free
>= min_space
)
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
;
460 err
= ubifs_lpt_scan_nolock(c
, -1, c
->lscan_lnum
,
461 (ubifs_lpt_scan_callback
)scan_for_free_cb
,
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
);
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
));
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 * @free: contains amount of free space in the LEB on exit
482 * @squeeze: whether to try to find space in a non-empty LEB first
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
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.
493 int ubifs_find_free_space(struct ubifs_info
*c
, int min_space
, int *free
,
496 const struct ubifs_lprops
*lprops
;
497 int lebs
, rsvd_idx_lebs
, pick_free
= 0, err
, lnum
, flags
;
499 dbg_find("min_space %d", min_space
);
502 /* Check if there are enough empty LEBs for commit */
503 spin_lock(&c
->space_lock
);
504 if (c
->min_idx_lebs
> c
->lst
.idx_lebs
)
505 rsvd_idx_lebs
= c
->min_idx_lebs
- c
->lst
.idx_lebs
;
508 lebs
= c
->lst
.empty_lebs
+ c
->freeable_cnt
+ c
->idx_gc_cnt
-
509 c
->lst
.taken_empty_lebs
;
510 ubifs_assert(lebs
+ c
->lst
.idx_lebs
>= c
->min_idx_lebs
);
511 if (rsvd_idx_lebs
< lebs
)
513 * OK to allocate an empty LEB, but we still don't want to go
514 * looking for one if there aren't any.
516 if (c
->lst
.empty_lebs
- c
->lst
.taken_empty_lebs
> 0) {
519 * Because we release the space lock, we must account
520 * for this allocation here. After the LEB properties
521 * flags have been updated, we subtract one. Note, the
522 * result of this is that lprops also decreases
523 * @taken_empty_lebs in 'ubifs_change_lp()', so it is
524 * off by one for a short period of time which may
525 * introduce a small disturbance to budgeting
526 * calculations, but this is harmless because at the
527 * worst case this would make the budgeting subsystem
528 * be more pessimistic than needed.
530 * Fundamentally, this is about serialization of the
531 * budgeting and lprops subsystems. We could make the
532 * @space_lock a mutex and avoid dropping it before
533 * calling 'ubifs_change_lp()', but mutex is more
534 * heavy-weight, and we want budgeting to be as fast as
537 c
->lst
.taken_empty_lebs
+= 1;
539 spin_unlock(&c
->space_lock
);
541 lprops
= do_find_free_space(c
, min_space
, pick_free
, squeeze
);
542 if (IS_ERR(lprops
)) {
543 err
= PTR_ERR(lprops
);
548 flags
= lprops
->flags
| LPROPS_TAKEN
;
550 lprops
= ubifs_change_lp(c
, lprops
, LPROPS_NC
, LPROPS_NC
, flags
, 0);
551 if (IS_ERR(lprops
)) {
552 err
= PTR_ERR(lprops
);
557 spin_lock(&c
->space_lock
);
558 c
->lst
.taken_empty_lebs
-= 1;
559 spin_unlock(&c
->space_lock
);
562 *free
= lprops
->free
;
563 ubifs_release_lprops(c
);
565 if (*free
== c
->leb_size
) {
567 * Ensure that empty LEBs have been unmapped. They may not have
568 * been, for example, because of an unclean unmount. Also
569 * LEBs that were freeable LEBs (free + dirty == leb_size) will
570 * not have been unmapped.
572 err
= ubifs_leb_unmap(c
, lnum
);
577 dbg_find("found LEB %d, free %d", lnum
, *free
);
578 ubifs_assert(*free
>= min_space
);
583 spin_lock(&c
->space_lock
);
584 c
->lst
.taken_empty_lebs
-= 1;
585 spin_unlock(&c
->space_lock
);
587 ubifs_release_lprops(c
);
592 * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
593 * @c: the UBIFS file-system description object
594 * @lprops: LEB properties to scan
595 * @in_tree: whether the LEB properties are in main memory
596 * @data: information passed to and from the caller of the scan
598 * This function returns a code that indicates whether the scan should continue
599 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
600 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
603 static int scan_for_idx_cb(struct ubifs_info
*c
,
604 const struct ubifs_lprops
*lprops
, int in_tree
,
605 struct scan_data
*data
)
607 int ret
= LPT_SCAN_CONTINUE
;
609 /* Exclude LEBs that are currently in use */
610 if (lprops
->flags
& LPROPS_TAKEN
)
611 return LPT_SCAN_CONTINUE
;
612 /* Determine whether to add these LEB properties to the tree */
613 if (!in_tree
&& valuable(c
, lprops
))
615 /* Exclude index LEBS */
616 if (lprops
->flags
& LPROPS_INDEX
)
618 /* Exclude LEBs that cannot be made empty */
619 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
)
622 * We are allocating for the index so it is safe to allocate LEBs with
623 * only free and dirty space, because write buffers are sync'd at commit
626 data
->lnum
= lprops
->lnum
;
627 return LPT_SCAN_ADD
| LPT_SCAN_STOP
;
631 * scan_for_leb_for_idx - scan for a free LEB for the index.
632 * @c: the UBIFS file-system description object
634 static const struct ubifs_lprops
*scan_for_leb_for_idx(struct ubifs_info
*c
)
636 struct ubifs_lprops
*lprops
;
637 struct scan_data data
;
641 err
= ubifs_lpt_scan_nolock(c
, -1, c
->lscan_lnum
,
642 (ubifs_lpt_scan_callback
)scan_for_idx_cb
,
646 ubifs_assert(data
.lnum
>= c
->main_first
&& data
.lnum
< c
->leb_cnt
);
647 c
->lscan_lnum
= data
.lnum
;
648 lprops
= ubifs_lpt_lookup_dirty(c
, data
.lnum
);
651 ubifs_assert(lprops
->lnum
== data
.lnum
);
652 ubifs_assert(lprops
->free
+ lprops
->dirty
== c
->leb_size
);
653 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
654 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
659 * ubifs_find_free_leb_for_idx - find a free LEB for the index.
660 * @c: the UBIFS file-system description object
662 * This function looks for a free LEB and returns that LEB number. The returned
663 * LEB is marked as "taken", "index".
665 * Only empty LEBs are allocated. This is for two reasons. First, the commit
666 * calculates the number of LEBs to allocate based on the assumption that they
667 * will be empty. Secondly, free space at the end of an index LEB is not
668 * guaranteed to be empty because it may have been used by the in-the-gaps
669 * method prior to an unclean unmount.
671 * If no LEB is found %-ENOSPC is returned. For other failures another negative
672 * error code is returned.
674 int ubifs_find_free_leb_for_idx(struct ubifs_info
*c
)
676 const struct ubifs_lprops
*lprops
;
677 int lnum
= -1, err
, flags
;
681 lprops
= ubifs_fast_find_empty(c
);
683 lprops
= ubifs_fast_find_freeable(c
);
685 ubifs_assert(c
->freeable_cnt
== 0);
686 if (c
->lst
.empty_lebs
- c
->lst
.taken_empty_lebs
> 0) {
687 lprops
= scan_for_leb_for_idx(c
);
688 if (IS_ERR(lprops
)) {
689 err
= PTR_ERR(lprops
);
703 dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
704 lnum
, lprops
->free
, lprops
->dirty
, lprops
->flags
);
706 flags
= lprops
->flags
| LPROPS_TAKEN
| LPROPS_INDEX
;
707 lprops
= ubifs_change_lp(c
, lprops
, c
->leb_size
, 0, flags
, 0);
708 if (IS_ERR(lprops
)) {
709 err
= PTR_ERR(lprops
);
713 ubifs_release_lprops(c
);
716 * Ensure that empty LEBs have been unmapped. They may not have been,
717 * for example, because of an unclean unmount. Also LEBs that were
718 * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
720 err
= ubifs_leb_unmap(c
, lnum
);
722 ubifs_change_one_lp(c
, lnum
, LPROPS_NC
, LPROPS_NC
, 0,
723 LPROPS_TAKEN
| LPROPS_INDEX
, 0);
730 ubifs_release_lprops(c
);
734 static int cmp_dirty_idx(const struct ubifs_lprops
**a
,
735 const struct ubifs_lprops
**b
)
737 const struct ubifs_lprops
*lpa
= *a
;
738 const struct ubifs_lprops
*lpb
= *b
;
740 return lpa
->dirty
+ lpa
->free
- lpb
->dirty
- lpb
->free
;
743 static void swap_dirty_idx(struct ubifs_lprops
**a
, struct ubifs_lprops
**b
,
746 struct ubifs_lprops
*t
= *a
;
753 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
754 * @c: the UBIFS file-system description object
756 * This function is called each commit to create an array of LEB numbers of
757 * dirty index LEBs sorted in order of dirty and free space. This is used by
758 * the in-the-gaps method of TNC commit.
760 int ubifs_save_dirty_idx_lnums(struct ubifs_info
*c
)
765 /* Copy the LPROPS_DIRTY_IDX heap */
766 c
->dirty_idx
.cnt
= c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1].cnt
;
767 memcpy(c
->dirty_idx
.arr
, c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1].arr
,
768 sizeof(void *) * c
->dirty_idx
.cnt
);
769 /* Sort it so that the dirtiest is now at the end */
770 sort(c
->dirty_idx
.arr
, c
->dirty_idx
.cnt
, sizeof(void *),
771 (int (*)(const void *, const void *))cmp_dirty_idx
,
772 (void (*)(void *, void *, int))swap_dirty_idx
);
773 dbg_find("found %d dirty index LEBs", c
->dirty_idx
.cnt
);
774 if (c
->dirty_idx
.cnt
)
775 dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
776 c
->dirty_idx
.arr
[c
->dirty_idx
.cnt
- 1]->lnum
,
777 c
->dirty_idx
.arr
[c
->dirty_idx
.cnt
- 1]->dirty
,
778 c
->dirty_idx
.arr
[c
->dirty_idx
.cnt
- 1]->free
);
779 /* Replace the lprops pointers with LEB numbers */
780 for (i
= 0; i
< c
->dirty_idx
.cnt
; i
++)
781 c
->dirty_idx
.arr
[i
] = (void *)(size_t)c
->dirty_idx
.arr
[i
]->lnum
;
782 ubifs_release_lprops(c
);
787 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
788 * @c: the UBIFS file-system description object
789 * @lprops: LEB properties to scan
790 * @in_tree: whether the LEB properties are in main memory
791 * @data: information passed to and from the caller of the scan
793 * This function returns a code that indicates whether the scan should continue
794 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
795 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
798 static int scan_dirty_idx_cb(struct ubifs_info
*c
,
799 const struct ubifs_lprops
*lprops
, int in_tree
,
800 struct scan_data
*data
)
802 int ret
= LPT_SCAN_CONTINUE
;
804 /* Exclude LEBs that are currently in use */
805 if (lprops
->flags
& LPROPS_TAKEN
)
806 return LPT_SCAN_CONTINUE
;
807 /* Determine whether to add these LEB properties to the tree */
808 if (!in_tree
&& valuable(c
, lprops
))
810 /* Exclude non-index LEBs */
811 if (!(lprops
->flags
& LPROPS_INDEX
))
813 /* Exclude LEBs with too little space */
814 if (lprops
->free
+ lprops
->dirty
< c
->min_idx_node_sz
)
816 /* Finally we found space */
817 data
->lnum
= lprops
->lnum
;
818 return LPT_SCAN_ADD
| LPT_SCAN_STOP
;
822 * find_dirty_idx_leb - find a dirty index LEB.
823 * @c: the UBIFS file-system description object
825 * This function returns LEB number upon success and a negative error code upon
826 * failure. In particular, -ENOSPC is returned if a dirty index LEB is not
829 * Note that this function scans the entire LPT but it is called very rarely.
831 static int find_dirty_idx_leb(struct ubifs_info
*c
)
833 const struct ubifs_lprops
*lprops
;
834 struct ubifs_lpt_heap
*heap
;
835 struct scan_data data
;
838 /* Check all structures in memory first */
840 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
841 for (i
= 0; i
< heap
->cnt
; i
++) {
842 lprops
= heap
->arr
[i
];
843 ret
= scan_dirty_idx_cb(c
, lprops
, 1, &data
);
844 if (ret
& LPT_SCAN_STOP
)
847 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
848 ret
= scan_dirty_idx_cb(c
, lprops
, 1, &data
);
849 if (ret
& LPT_SCAN_STOP
)
852 list_for_each_entry(lprops
, &c
->uncat_list
, list
) {
853 ret
= scan_dirty_idx_cb(c
, lprops
, 1, &data
);
854 if (ret
& LPT_SCAN_STOP
)
857 if (c
->pnodes_have
>= c
->pnode_cnt
)
858 /* All pnodes are in memory, so skip scan */
860 err
= ubifs_lpt_scan_nolock(c
, -1, c
->lscan_lnum
,
861 (ubifs_lpt_scan_callback
)scan_dirty_idx_cb
,
866 ubifs_assert(data
.lnum
>= c
->main_first
&& data
.lnum
< c
->leb_cnt
);
867 c
->lscan_lnum
= data
.lnum
;
868 lprops
= ubifs_lpt_lookup_dirty(c
, data
.lnum
);
870 return PTR_ERR(lprops
);
871 ubifs_assert(lprops
->lnum
== data
.lnum
);
872 ubifs_assert(lprops
->free
+ lprops
->dirty
>= c
->min_idx_node_sz
);
873 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
874 ubifs_assert((lprops
->flags
& LPROPS_INDEX
));
876 dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
877 lprops
->lnum
, lprops
->free
, lprops
->dirty
, lprops
->flags
);
879 lprops
= ubifs_change_lp(c
, lprops
, LPROPS_NC
, LPROPS_NC
,
880 lprops
->flags
| LPROPS_TAKEN
, 0);
882 return PTR_ERR(lprops
);
888 * get_idx_gc_leb - try to get a LEB number from trivial GC.
889 * @c: the UBIFS file-system description object
891 static int get_idx_gc_leb(struct ubifs_info
*c
)
893 const struct ubifs_lprops
*lp
;
896 err
= ubifs_get_idx_gc_leb(c
);
901 * The LEB was due to be unmapped after the commit but
902 * it is needed now for this commit.
904 lp
= ubifs_lpt_lookup_dirty(c
, lnum
);
905 if (unlikely(IS_ERR(lp
)))
907 lp
= ubifs_change_lp(c
, lp
, LPROPS_NC
, LPROPS_NC
,
908 lp
->flags
| LPROPS_INDEX
, -1);
909 if (unlikely(IS_ERR(lp
)))
911 dbg_find("LEB %d, dirty %d and free %d flags %#x",
912 lp
->lnum
, lp
->dirty
, lp
->free
, lp
->flags
);
917 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
918 * @c: the UBIFS file-system description object
920 static int find_dirtiest_idx_leb(struct ubifs_info
*c
)
922 const struct ubifs_lprops
*lp
;
926 if (!c
->dirty_idx
.cnt
)
928 /* The lprops pointers were replaced by LEB numbers */
929 lnum
= (size_t)c
->dirty_idx
.arr
[--c
->dirty_idx
.cnt
];
930 lp
= ubifs_lpt_lookup(c
, lnum
);
933 if ((lp
->flags
& LPROPS_TAKEN
) || !(lp
->flags
& LPROPS_INDEX
))
935 lp
= ubifs_change_lp(c
, lp
, LPROPS_NC
, LPROPS_NC
,
936 lp
->flags
| LPROPS_TAKEN
, 0);
941 dbg_find("LEB %d, dirty %d and free %d flags %#x", lp
->lnum
, lp
->dirty
,
942 lp
->free
, lp
->flags
);
943 ubifs_assert(lp
->flags
| LPROPS_TAKEN
);
944 ubifs_assert(lp
->flags
| LPROPS_INDEX
);
949 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
950 * @c: the UBIFS file-system description object
952 * This function attempts to find an untaken index LEB with the most free and
953 * dirty space that can be used without overwriting index nodes that were in the
954 * last index committed.
956 int ubifs_find_dirty_idx_leb(struct ubifs_info
*c
)
963 * We made an array of the dirtiest index LEB numbers as at the start of
964 * last commit. Try that array first.
966 err
= find_dirtiest_idx_leb(c
);
968 /* Next try scanning the entire LPT */
970 err
= find_dirty_idx_leb(c
);
972 /* Finally take any index LEBs awaiting trivial GC */
974 err
= get_idx_gc_leb(c
);
976 ubifs_release_lprops(c
);