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