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