Lines Matching +full:non +full:- +full:empty
1 // SPDX-License-Identifier: GPL-2.0-only
5 * Copyright (C) 2006-2008 Nokia Corporation.
21 * struct scan_data - data provided to scan callback functions
23 * @pick_free: whether it is OK to scan for empty LEBs
35 * valuable - determine whether LEB properties are valuable.
36 * @c: the UBIFS file-system description object
44 int n, cat = lprops->flags & LPROPS_CAT_MASK; in valuable()
51 heap = &c->lpt_heap[cat - 1]; in valuable()
52 if (heap->cnt < heap->max_cnt) in valuable()
54 if (lprops->free + lprops->dirty >= c->dark_wm) in valuable()
58 n = c->lst.empty_lebs + c->freeable_cnt - in valuable()
59 c->lst.taken_empty_lebs; in valuable()
60 if (n < c->lsave_cnt) in valuable()
72 * scan_for_dirty_cb - dirty space scan callback.
73 * @c: the UBIFS file-system description object
90 if (lprops->flags & LPROPS_TAKEN) in scan_for_dirty_cb()
96 if (lprops->free + lprops->dirty < data->min_space) in scan_for_dirty_cb()
99 if (data->exclude_index && lprops->flags & LPROPS_INDEX) in scan_for_dirty_cb()
101 /* If specified, exclude empty or freeable LEBs */ in scan_for_dirty_cb()
102 if (lprops->free + lprops->dirty == c->leb_size) { in scan_for_dirty_cb()
103 if (!data->pick_free) in scan_for_dirty_cb()
105 /* Exclude LEBs with too little dirty space (unless it is empty) */ in scan_for_dirty_cb()
106 } else if (lprops->dirty < c->dead_wm) in scan_for_dirty_cb()
109 data->lnum = lprops->lnum; in scan_for_dirty_cb()
114 * scan_for_dirty - find a data LEB with free space.
115 * @c: the UBIFS file-system description object
134 heap = &c->lpt_heap[LPROPS_FREE - 1]; in scan_for_dirty()
135 for (i = 0; i < heap->cnt; i++) { in scan_for_dirty()
136 lprops = heap->arr[i]; in scan_for_dirty()
137 if (lprops->free + lprops->dirty < min_space) in scan_for_dirty()
139 if (lprops->dirty < c->dead_wm) in scan_for_dirty()
146 * so check the uncategorized list. N.B. neither empty nor freeable LEBs in scan_for_dirty()
148 * finite-sized heaps. in scan_for_dirty()
150 list_for_each_entry(lprops, &c->uncat_list, list) { in scan_for_dirty()
151 if (lprops->flags & LPROPS_TAKEN) in scan_for_dirty()
153 if (lprops->free + lprops->dirty < min_space) in scan_for_dirty()
155 if (exclude_index && (lprops->flags & LPROPS_INDEX)) in scan_for_dirty()
157 if (lprops->dirty < c->dead_wm) in scan_for_dirty()
162 if (c->pnodes_have >= c->pnode_cnt) in scan_for_dirty()
164 return ERR_PTR(-ENOSPC); in scan_for_dirty()
167 data.lnum = -1; in scan_for_dirty()
169 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, in scan_for_dirty()
174 ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); in scan_for_dirty()
175 c->lscan_lnum = data.lnum; in scan_for_dirty()
179 ubifs_assert(c, lprops->lnum == data.lnum); in scan_for_dirty()
180 ubifs_assert(c, lprops->free + lprops->dirty >= min_space); in scan_for_dirty()
181 ubifs_assert(c, lprops->dirty >= c->dead_wm || in scan_for_dirty()
183 lprops->free + lprops->dirty == c->leb_size)); in scan_for_dirty()
184 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); in scan_for_dirty()
185 ubifs_assert(c, !exclude_index || !(lprops->flags & LPROPS_INDEX)); in scan_for_dirty()
190 * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
191 * @c: the UBIFS file-system description object
195 * @pick_free: controls whether it is OK to pick empty or index LEBs
199 * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
218 * of success, %-ENOSPC if no dirty LEB was found and a negative error code in
233 spin_lock(&c->space_lock); in ubifs_find_dirty_leb()
234 lebs = c->lst.empty_lebs + c->idx_gc_cnt; in ubifs_find_dirty_leb()
235 lebs += c->freeable_cnt - c->lst.taken_empty_lebs; in ubifs_find_dirty_leb()
243 if (c->bi.min_idx_lebs >= c->lst.idx_lebs) { in ubifs_find_dirty_leb()
244 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; in ubifs_find_dirty_leb()
247 spin_unlock(&c->space_lock); in ubifs_find_dirty_leb()
251 /* OK, try to find an empty LEB */ in ubifs_find_dirty_leb()
266 spin_lock(&c->space_lock); in ubifs_find_dirty_leb()
267 exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs); in ubifs_find_dirty_leb()
268 spin_unlock(&c->space_lock); in ubifs_find_dirty_leb()
272 heap = &c->lpt_heap[LPROPS_DIRTY - 1]; in ubifs_find_dirty_leb()
273 idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; in ubifs_find_dirty_leb()
275 if (idx_heap->cnt && !exclude_index) { in ubifs_find_dirty_leb()
276 idx_lp = idx_heap->arr[0]; in ubifs_find_dirty_leb()
277 sum = idx_lp->free + idx_lp->dirty; in ubifs_find_dirty_leb()
282 * not the optimal boundary - this should be tested and in ubifs_find_dirty_leb()
284 * in-the-gaps to consolidate the index comparing to how much in ubifs_find_dirty_leb()
288 if (sum < min_space || sum < c->half_leb_size) in ubifs_find_dirty_leb()
292 if (heap->cnt) { in ubifs_find_dirty_leb()
293 lp = heap->arr[0]; in ubifs_find_dirty_leb()
294 if (lp->dirty + lp->free < min_space) in ubifs_find_dirty_leb()
300 if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty) in ubifs_find_dirty_leb()
306 ubifs_assert(c, lp->free + lp->dirty >= c->dead_wm); in ubifs_find_dirty_leb()
317 ubifs_assert(c, lp->dirty >= c->dead_wm || in ubifs_find_dirty_leb()
318 (pick_free && lp->free + lp->dirty == c->leb_size)); in ubifs_find_dirty_leb()
322 lp->lnum, lp->free, lp->dirty, lp->flags); in ubifs_find_dirty_leb()
325 lp->flags | LPROPS_TAKEN, 0); in ubifs_find_dirty_leb()
339 * scan_for_free_cb - free space scan callback.
340 * @c: the UBIFS file-system description object
357 if (lprops->flags & LPROPS_TAKEN) in scan_for_free_cb()
363 if (lprops->flags & LPROPS_INDEX) in scan_for_free_cb()
366 if (lprops->free < data->min_space) in scan_for_free_cb()
368 /* If specified, exclude empty LEBs */ in scan_for_free_cb()
369 if (!data->pick_free && lprops->free == c->leb_size) in scan_for_free_cb()
377 if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0) in scan_for_free_cb()
380 data->lnum = lprops->lnum; in scan_for_free_cb()
385 * do_find_free_space - find a data LEB with free space.
386 * @c: the UBIFS file-system description object
388 * @pick_free: whether it is OK to scan for empty LEBs
389 * @squeeze: whether to try to find space in a non-empty LEB first
406 if (lprops && lprops->free >= min_space) in do_find_free_space()
416 if (lprops && lprops->free >= min_space) in do_find_free_space()
420 heap = &c->lpt_heap[LPROPS_DIRTY - 1]; in do_find_free_space()
421 for (i = 0; i < heap->cnt; i++) { in do_find_free_space()
422 lprops = heap->arr[i]; in do_find_free_space()
423 if (lprops->free >= min_space) in do_find_free_space()
429 * so check the uncategorized list. N.B. neither empty nor freeable LEBs in do_find_free_space()
431 * finite-sized heaps. in do_find_free_space()
433 list_for_each_entry(lprops, &c->uncat_list, list) { in do_find_free_space()
434 if (lprops->flags & LPROPS_TAKEN) in do_find_free_space()
436 if (lprops->flags & LPROPS_INDEX) in do_find_free_space()
438 if (lprops->free >= min_space) in do_find_free_space()
442 if (c->pnodes_have >= c->pnode_cnt) in do_find_free_space()
444 return ERR_PTR(-ENOSPC); in do_find_free_space()
447 data.lnum = -1; in do_find_free_space()
448 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, in do_find_free_space()
453 ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); in do_find_free_space()
454 c->lscan_lnum = data.lnum; in do_find_free_space()
458 ubifs_assert(c, lprops->lnum == data.lnum); in do_find_free_space()
459 ubifs_assert(c, lprops->free >= min_space); in do_find_free_space()
460 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); in do_find_free_space()
461 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); in do_find_free_space()
466 * ubifs_find_free_space - find a data LEB with free space.
467 * @c: the UBIFS file-system description object
470 * @squeeze: whether to try to find space in a non-empty LEB first
473 * It tries to find an empty LEB if possible. If no empty LEBs are available,
474 * this function searches for a non-empty data LEB. The returned LEB is marked
477 * This function returns found LEB number in case of success, %-ENOSPC if it
490 /* Check if there are enough empty LEBs for commit */ in ubifs_find_free_space()
491 spin_lock(&c->space_lock); in ubifs_find_free_space()
492 if (c->bi.min_idx_lebs > c->lst.idx_lebs) in ubifs_find_free_space()
493 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; in ubifs_find_free_space()
496 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - in ubifs_find_free_space()
497 c->lst.taken_empty_lebs; in ubifs_find_free_space()
500 * OK to allocate an empty LEB, but we still don't want to go in ubifs_find_free_space()
503 if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { in ubifs_find_free_space()
521 * heavy-weight, and we want budgeting to be as fast as in ubifs_find_free_space()
524 c->lst.taken_empty_lebs += 1; in ubifs_find_free_space()
526 spin_unlock(&c->space_lock); in ubifs_find_free_space()
534 lnum = lprops->lnum; in ubifs_find_free_space()
535 flags = lprops->flags | LPROPS_TAKEN; in ubifs_find_free_space()
544 spin_lock(&c->space_lock); in ubifs_find_free_space()
545 c->lst.taken_empty_lebs -= 1; in ubifs_find_free_space()
546 spin_unlock(&c->space_lock); in ubifs_find_free_space()
549 *offs = c->leb_size - lprops->free; in ubifs_find_free_space()
554 * Ensure that empty LEBs have been unmapped. They may not have in ubifs_find_free_space()
564 dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs); in ubifs_find_free_space()
565 ubifs_assert(c, *offs <= c->leb_size - min_space); in ubifs_find_free_space()
570 spin_lock(&c->space_lock); in ubifs_find_free_space()
571 c->lst.taken_empty_lebs -= 1; in ubifs_find_free_space()
572 spin_unlock(&c->space_lock); in ubifs_find_free_space()
579 * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
580 * @c: the UBIFS file-system description object
597 if (lprops->flags & LPROPS_TAKEN) in scan_for_idx_cb()
603 if (lprops->flags & LPROPS_INDEX) in scan_for_idx_cb()
605 /* Exclude LEBs that cannot be made empty */ in scan_for_idx_cb()
606 if (lprops->free + lprops->dirty != c->leb_size) in scan_for_idx_cb()
613 data->lnum = lprops->lnum; in scan_for_idx_cb()
618 * scan_for_leb_for_idx - scan for a free LEB for the index.
619 * @c: the UBIFS file-system description object
627 data.lnum = -1; in scan_for_leb_for_idx()
628 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, in scan_for_leb_for_idx()
633 ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); in scan_for_leb_for_idx()
634 c->lscan_lnum = data.lnum; in scan_for_leb_for_idx()
638 ubifs_assert(c, lprops->lnum == data.lnum); in scan_for_leb_for_idx()
639 ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size); in scan_for_leb_for_idx()
640 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); in scan_for_leb_for_idx()
641 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); in scan_for_leb_for_idx()
646 * ubifs_find_free_leb_for_idx - find a free LEB for the index.
647 * @c: the UBIFS file-system description object
652 * Only empty LEBs are allocated. This is for two reasons. First, the commit
654 * will be empty. Secondly, free space at the end of an index LEB is not
655 * guaranteed to be empty because it may have been used by the in-the-gaps
658 * If no LEB is found %-ENOSPC is returned. For other failures another negative
664 int lnum = -1, err, flags; in ubifs_find_free_leb_for_idx()
679 if (c->in_a_category_cnt != c->main_lebs || in ubifs_find_free_leb_for_idx()
680 c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { in ubifs_find_free_leb_for_idx()
681 ubifs_assert(c, c->freeable_cnt == 0); in ubifs_find_free_leb_for_idx()
692 err = -ENOSPC; in ubifs_find_free_leb_for_idx()
696 lnum = lprops->lnum; in ubifs_find_free_leb_for_idx()
699 lnum, lprops->free, lprops->dirty, lprops->flags); in ubifs_find_free_leb_for_idx()
701 flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; in ubifs_find_free_leb_for_idx()
702 lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0); in ubifs_find_free_leb_for_idx()
711 * Ensure that empty LEBs have been unmapped. They may not have been, in ubifs_find_free_leb_for_idx()
735 return lpa->dirty + lpa->free - lpb->dirty - lpb->free; in cmp_dirty_idx()
739 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
740 * @c: the UBIFS file-system description object
744 * the in-the-gaps method of TNC commit.
752 c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; in ubifs_save_dirty_idx_lnums()
753 memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, in ubifs_save_dirty_idx_lnums()
754 sizeof(void *) * c->dirty_idx.cnt); in ubifs_save_dirty_idx_lnums()
756 sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *), in ubifs_save_dirty_idx_lnums()
758 dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt); in ubifs_save_dirty_idx_lnums()
759 if (c->dirty_idx.cnt) in ubifs_save_dirty_idx_lnums()
761 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, in ubifs_save_dirty_idx_lnums()
762 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, in ubifs_save_dirty_idx_lnums()
763 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); in ubifs_save_dirty_idx_lnums()
765 for (i = 0; i < c->dirty_idx.cnt; i++) in ubifs_save_dirty_idx_lnums()
766 c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; in ubifs_save_dirty_idx_lnums()
772 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
773 * @c: the UBIFS file-system description object
790 if (lprops->flags & LPROPS_TAKEN) in scan_dirty_idx_cb()
795 /* Exclude non-index LEBs */ in scan_dirty_idx_cb()
796 if (!(lprops->flags & LPROPS_INDEX)) in scan_dirty_idx_cb()
799 if (lprops->free + lprops->dirty < c->min_idx_node_sz) in scan_dirty_idx_cb()
802 data->lnum = lprops->lnum; in scan_dirty_idx_cb()
807 * find_dirty_idx_leb - find a dirty index LEB.
808 * @c: the UBIFS file-system description object
811 * failure. In particular, -ENOSPC is returned if a dirty index LEB is not
824 data.lnum = -1; in find_dirty_idx_leb()
825 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; in find_dirty_idx_leb()
826 for (i = 0; i < heap->cnt; i++) { in find_dirty_idx_leb()
827 lprops = heap->arr[i]; in find_dirty_idx_leb()
832 list_for_each_entry(lprops, &c->frdi_idx_list, list) { in find_dirty_idx_leb()
837 list_for_each_entry(lprops, &c->uncat_list, list) { in find_dirty_idx_leb()
842 if (c->pnodes_have >= c->pnode_cnt) in find_dirty_idx_leb()
844 return -ENOSPC; in find_dirty_idx_leb()
845 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, in find_dirty_idx_leb()
851 ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); in find_dirty_idx_leb()
852 c->lscan_lnum = data.lnum; in find_dirty_idx_leb()
856 ubifs_assert(c, lprops->lnum == data.lnum); in find_dirty_idx_leb()
857 ubifs_assert(c, lprops->free + lprops->dirty >= c->min_idx_node_sz); in find_dirty_idx_leb()
858 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); in find_dirty_idx_leb()
859 ubifs_assert(c, (lprops->flags & LPROPS_INDEX)); in find_dirty_idx_leb()
862 lprops->lnum, lprops->free, lprops->dirty, lprops->flags); in find_dirty_idx_leb()
865 lprops->flags | LPROPS_TAKEN, 0); in find_dirty_idx_leb()
869 return lprops->lnum; in find_dirty_idx_leb()
873 * get_idx_gc_leb - try to get a LEB number from trivial GC.
874 * @c: the UBIFS file-system description object
893 lp->flags | LPROPS_INDEX, -1); in get_idx_gc_leb()
897 lp->lnum, lp->dirty, lp->free, lp->flags); in get_idx_gc_leb()
902 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
903 * @c: the UBIFS file-system description object
911 if (!c->dirty_idx.cnt) in find_dirtiest_idx_leb()
912 return -ENOSPC; in find_dirtiest_idx_leb()
914 lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; in find_dirtiest_idx_leb()
918 if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) in find_dirtiest_idx_leb()
921 lp->flags | LPROPS_TAKEN, 0); in find_dirtiest_idx_leb()
926 dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty, in find_dirtiest_idx_leb()
927 lp->free, lp->flags); in find_dirtiest_idx_leb()
928 ubifs_assert(c, lp->flags & LPROPS_TAKEN); in find_dirtiest_idx_leb()
929 ubifs_assert(c, lp->flags & LPROPS_INDEX); in find_dirtiest_idx_leb()
934 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
935 * @c: the UBIFS file-system description object
954 if (err == -ENOSPC) in ubifs_find_dirty_idx_leb()
958 if (err == -ENOSPC) in ubifs_find_dirty_idx_leb()