fs/ubifs/find.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * This file is part of UBIFS.
0004  *
0005  * Copyright (C) 2006-2008 Nokia Corporation.
0006  *
0007  * Authors: Artem Bityutskiy (Битюцкий Артём)
0008  *          Adrian Hunter
0009  */
0010
0011 /*
0012  * This file contains functions for finding LEBs for various purposes e.g.
0013  * garbage collection. In general, lprops category heaps and lists are used
0014  * for fast access, falling back on scanning the LPT as a last resort.
0015  */
0016
0017 #include <linux/sort.h>
0018 #include "ubifs.h"
0019
0020 /**
0021  * struct scan_data - data provided to scan callback functions
0022  * @min_space: minimum number of bytes for which to scan
0023  * @pick_free: whether it is OK to scan for empty LEBs
0024  * @lnum: LEB number found is returned here
0025  * @exclude_index: whether to exclude index LEBs
0026  */
0027 struct scan_data {
0028     int min_space;
0029     int pick_free;
0030     int lnum;
0031     int exclude_index;
0032 };
0033
0034 /**
0035  * valuable - determine whether LEB properties are valuable.
0036  * @c: the UBIFS file-system description object
0037  * @lprops: LEB properties
0038  *
0039  * This function return %1 if the LEB properties should be added to the LEB
0040  * properties tree in memory. Otherwise %0 is returned.
0041  */
0042 static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)
0043 {
0044     int n, cat = lprops->flags & LPROPS_CAT_MASK;
0045     struct ubifs_lpt_heap *heap;
0046
0047     switch (cat) {
0048     case LPROPS_DIRTY:
0049     case LPROPS_DIRTY_IDX:
0050     case LPROPS_FREE:
0051         heap = &c->lpt_heap[cat - 1];
0052         if (heap->cnt < heap->max_cnt)
0053             return 1;
0054         if (lprops->free + lprops->dirty >= c->dark_wm)
0055             return 1;
0056         return 0;
0057     case LPROPS_EMPTY:
0058         n = c->lst.empty_lebs + c->freeable_cnt -
0059             c->lst.taken_empty_lebs;
0060         if (n < c->lsave_cnt)
0061             return 1;
0062         return 0;
0063     case LPROPS_FREEABLE:
0064         return 1;
0065     case LPROPS_FRDI_IDX:
0066         return 1;
0067     }
0068     return 0;
0069 }
0070
0071 /**
0072  * scan_for_dirty_cb - dirty space scan callback.
0073  * @c: the UBIFS file-system description object
0074  * @lprops: LEB properties to scan
0075  * @in_tree: whether the LEB properties are in main memory
0076  * @data: information passed to and from the caller of the scan
0077  *
0078  * This function returns a code that indicates whether the scan should continue
0079  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
0080  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
0081  * (%LPT_SCAN_STOP).
0082  */
0083 static int scan_for_dirty_cb(struct ubifs_info *c,
0084                  const struct ubifs_lprops *lprops, int in_tree,
0085                  struct scan_data *data)
0086 {
0087     int ret = LPT_SCAN_CONTINUE;
0088
0089     /* Exclude LEBs that are currently in use */
0090     if (lprops->flags & LPROPS_TAKEN)
0091         return LPT_SCAN_CONTINUE;
0092     /* Determine whether to add these LEB properties to the tree */
0093     if (!in_tree && valuable(c, lprops))
0094         ret |= LPT_SCAN_ADD;
0095     /* Exclude LEBs with too little space */
0096     if (lprops->free + lprops->dirty < data->min_space)
0097         return ret;
0098     /* If specified, exclude index LEBs */
0099     if (data->exclude_index && lprops->flags & LPROPS_INDEX)
0100         return ret;
0101     /* If specified, exclude empty or freeable LEBs */
0102     if (lprops->free + lprops->dirty == c->leb_size) {
0103         if (!data->pick_free)
0104             return ret;
0105     /* Exclude LEBs with too little dirty space (unless it is empty) */
0106     } else if (lprops->dirty < c->dead_wm)
0107         return ret;
0108     /* Finally we found space */
0109     data->lnum = lprops->lnum;
0110     return LPT_SCAN_ADD | LPT_SCAN_STOP;
0111 }
0112
0113 /**
0114  * scan_for_dirty - find a data LEB with free space.
0115  * @c: the UBIFS file-system description object
0116  * @min_space: minimum amount free plus dirty space the returned LEB has to
0117  *             have
0118  * @pick_free: if it is OK to return a free or freeable LEB
0119  * @exclude_index: whether to exclude index LEBs
0120  *
0121  * This function returns a pointer to the LEB properties found or a negative
0122  * error code.
0123  */
0124 static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,
0125                          int min_space, int pick_free,
0126                          int exclude_index)
0127 {
0128     const struct ubifs_lprops *lprops;
0129     struct ubifs_lpt_heap *heap;
0130     struct scan_data data;
0131     int err, i;
0132
0133     /* There may be an LEB with enough dirty space on the free heap */
0134     heap = &c->lpt_heap[LPROPS_FREE - 1];
0135     for (i = 0; i < heap->cnt; i++) {
0136         lprops = heap->arr[i];
0137         if (lprops->free + lprops->dirty < min_space)
0138             continue;
0139         if (lprops->dirty < c->dead_wm)
0140             continue;
0141         return lprops;
0142     }
0143     /*
0144      * A LEB may have fallen off of the bottom of the dirty heap, and ended
0145      * up as uncategorized even though it has enough dirty space for us now,
0146      * so check the uncategorized list. N.B. neither empty nor freeable LEBs
0147      * can end up as uncategorized because they are kept on lists not
0148      * finite-sized heaps.
0149      */
0150     list_for_each_entry(lprops, &c->uncat_list, list) {
0151         if (lprops->flags & LPROPS_TAKEN)
0152             continue;
0153         if (lprops->free + lprops->dirty < min_space)
0154             continue;
0155         if (exclude_index && (lprops->flags & LPROPS_INDEX))
0156             continue;
0157         if (lprops->dirty < c->dead_wm)
0158             continue;
0159         return lprops;
0160     }
0161     /* We have looked everywhere in main memory, now scan the flash */
0162     if (c->pnodes_have >= c->pnode_cnt)
0163         /* All pnodes are in memory, so skip scan */
0164         return ERR_PTR(-ENOSPC);
0165     data.min_space = min_space;
0166     data.pick_free = pick_free;
0167     data.lnum = -1;
0168     data.exclude_index = exclude_index;
0169     err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
0170                     (ubifs_lpt_scan_callback)scan_for_dirty_cb,
0171                     &data);
0172     if (err)
0173         return ERR_PTR(err);
0174     ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt);
0175     c->lscan_lnum = data.lnum;
0176     lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
0177     if (IS_ERR(lprops))
0178         return lprops;
0179     ubifs_assert(c, lprops->lnum == data.lnum);
0180     ubifs_assert(c, lprops->free + lprops->dirty >= min_space);
0181     ubifs_assert(c, lprops->dirty >= c->dead_wm ||
0182              (pick_free &&
0183               lprops->free + lprops->dirty == c->leb_size));
0184     ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
0185     ubifs_assert(c, !exclude_index || !(lprops->flags & LPROPS_INDEX));
0186     return lprops;
0187 }
0188
0189 /**
0190  * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
0191  * @c: the UBIFS file-system description object
0192  * @ret_lp: LEB properties are returned here on exit
0193  * @min_space: minimum amount free plus dirty space the returned LEB has to
0194  *             have
0195  * @pick_free: controls whether it is OK to pick empty or index LEBs
0196  *
0197  * This function tries to find a dirty logical eraseblock which has at least
0198  * @min_space free and dirty space. It prefers to take an LEB from the dirty or
0199  * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
0200  * or do not have an LEB which satisfies the @min_space criteria.
0201  *
0202  * Note, LEBs which have less than dead watermark of free + dirty space are
0203  * never picked by this function.
0204  *
0205  * The additional @pick_free argument controls if this function has to return a
0206  * free or freeable LEB if one is present. For example, GC must to set it to %1,
0207  * when called from the journal space reservation function, because the
0208  * appearance of free space may coincide with the loss of enough dirty space
0209  * for GC to succeed anyway.
0210  *
0211  * In contrast, if the Garbage Collector is called from budgeting, it should
0212  * just make free space, not return LEBs which are already free or freeable.
0213  *
0214  * In addition @pick_free is set to %2 by the recovery process in order to
0215  * recover gc_lnum in which case an index LEB must not be returned.
0216  *
0217  * This function returns zero and the LEB properties of found dirty LEB in case
0218  * of success, %-ENOSPC if no dirty LEB was found and a negative error code in
0219  * case of other failures. The returned LEB is marked as "taken".
0220  */
0221 int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp,
0222              int min_space, int pick_free)
0223 {
0224     int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0;
0225     const struct ubifs_lprops *lp = NULL, *idx_lp = NULL;
0226     struct ubifs_lpt_heap *heap, *idx_heap;
0227
0228     ubifs_get_lprops(c);
0229
0230     if (pick_free) {
0231         int lebs, rsvd_idx_lebs = 0;
0232
0233         spin_lock(&c->space_lock);
0234         lebs = c->lst.empty_lebs + c->idx_gc_cnt;
0235         lebs += c->freeable_cnt - c->lst.taken_empty_lebs;
0236
0237         /*
0238          * Note, the index may consume more LEBs than have been reserved
0239          * for it. It is OK because it might be consolidated by GC.
0240          * But if the index takes fewer LEBs than it is reserved for it,
0241          * this function must avoid picking those reserved LEBs.
0242          */
0243         if (c->bi.min_idx_lebs >= c->lst.idx_lebs) {
0244             rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;
0245             exclude_index = 1;
0246         }
0247         spin_unlock(&c->space_lock);
0248
0249         /* Check if there are enough free LEBs for the index */
0250         if (rsvd_idx_lebs < lebs) {
0251             /* OK, try to find an empty LEB */
0252             lp = ubifs_fast_find_empty(c);
0253             if (lp)
0254                 goto found;
0255
0256             /* Or a freeable LEB */
0257             lp = ubifs_fast_find_freeable(c);
0258             if (lp)
0259                 goto found;
0260         } else
0261             /*
0262              * We cannot pick free/freeable LEBs in the below code.
0263              */
0264             pick_free = 0;
0265     } else {
0266         spin_lock(&c->space_lock);
0267         exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs);
0268         spin_unlock(&c->space_lock);
0269     }
0270
0271     /* Look on the dirty and dirty index heaps */
0272     heap = &c->lpt_heap[LPROPS_DIRTY - 1];
0273     idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
0274
0275     if (idx_heap->cnt && !exclude_index) {
0276         idx_lp = idx_heap->arr[0];
0277         sum = idx_lp->free + idx_lp->dirty;
0278         /*
0279          * Since we reserve thrice as much space for the index than it
0280          * actually takes, it does not make sense to pick indexing LEBs
0281          * with less than, say, half LEB of dirty space. May be half is
0282          * not the optimal boundary - this should be tested and
0283          * checked. This boundary should determine how much we use
0284          * in-the-gaps to consolidate the index comparing to how much
0285          * we use garbage collector to consolidate it. The "half"
0286          * criteria just feels to be fine.
0287          */
0288         if (sum < min_space || sum < c->half_leb_size)
0289             idx_lp = NULL;
0290     }
0291
0292     if (heap->cnt) {
0293         lp = heap->arr[0];
0294         if (lp->dirty + lp->free < min_space)
0295             lp = NULL;
0296     }
0297
0298     /* Pick the LEB with most space */
0299     if (idx_lp && lp) {
0300         if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty)
0301             lp = idx_lp;
0302     } else if (idx_lp && !lp)
0303         lp = idx_lp;
0304
0305     if (lp) {
0306         ubifs_assert(c, lp->free + lp->dirty >= c->dead_wm);
0307         goto found;
0308     }
0309
0310     /* Did not find a dirty LEB on the dirty heaps, have to scan */
0311     dbg_find("scanning LPT for a dirty LEB");
0312     lp = scan_for_dirty(c, min_space, pick_free, exclude_index);
0313     if (IS_ERR(lp)) {
0314         err = PTR_ERR(lp);
0315         goto out;
0316     }
0317     ubifs_assert(c, lp->dirty >= c->dead_wm ||
0318              (pick_free && lp->free + lp->dirty == c->leb_size));
0319
0320 found:
0321     dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
0322          lp->lnum, lp->free, lp->dirty, lp->flags);
0323
0324     lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
0325                  lp->flags | LPROPS_TAKEN, 0);
0326     if (IS_ERR(lp)) {
0327         err = PTR_ERR(lp);
0328         goto out;
0329     }
0330
0331     memcpy(ret_lp, lp, sizeof(struct ubifs_lprops));
0332
0333 out:
0334     ubifs_release_lprops(c);
0335     return err;
0336 }
0337
0338 /**
0339  * scan_for_free_cb - free space scan callback.
0340  * @c: the UBIFS file-system description object
0341  * @lprops: LEB properties to scan
0342  * @in_tree: whether the LEB properties are in main memory
0343  * @data: information passed to and from the caller of the scan
0344  *
0345  * This function returns a code that indicates whether the scan should continue
0346  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
0347  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
0348  * (%LPT_SCAN_STOP).
0349  */
0350 static int scan_for_free_cb(struct ubifs_info *c,
0351                 const struct ubifs_lprops *lprops, int in_tree,
0352                 struct scan_data *data)
0353 {
0354     int ret = LPT_SCAN_CONTINUE;
0355
0356     /* Exclude LEBs that are currently in use */
0357     if (lprops->flags & LPROPS_TAKEN)
0358         return LPT_SCAN_CONTINUE;
0359     /* Determine whether to add these LEB properties to the tree */
0360     if (!in_tree && valuable(c, lprops))
0361         ret |= LPT_SCAN_ADD;
0362     /* Exclude index LEBs */
0363     if (lprops->flags & LPROPS_INDEX)
0364         return ret;
0365     /* Exclude LEBs with too little space */
0366     if (lprops->free < data->min_space)
0367         return ret;
0368     /* If specified, exclude empty LEBs */
0369     if (!data->pick_free && lprops->free == c->leb_size)
0370         return ret;
0371     /*
0372      * LEBs that have only free and dirty space must not be allocated
0373      * because they may have been unmapped already or they may have data
0374      * that is obsolete only because of nodes that are still sitting in a
0375      * wbuf.
0376      */
0377     if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0)
0378         return ret;
0379     /* Finally we found space */
0380     data->lnum = lprops->lnum;
0381     return LPT_SCAN_ADD | LPT_SCAN_STOP;
0382 }
0383
0384 /**
0385  * do_find_free_space - find a data LEB with free space.
0386  * @c: the UBIFS file-system description object
0387  * @min_space: minimum amount of free space required
0388  * @pick_free: whether it is OK to scan for empty LEBs
0389  * @squeeze: whether to try to find space in a non-empty LEB first
0390  *
0391  * This function returns a pointer to the LEB properties found or a negative
0392  * error code.
0393  */
0394 static
0395 const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,
0396                           int min_space, int pick_free,
0397                           int squeeze)
0398 {
0399     const struct ubifs_lprops *lprops;
0400     struct ubifs_lpt_heap *heap;
0401     struct scan_data data;
0402     int err, i;
0403
0404     if (squeeze) {
0405         lprops = ubifs_fast_find_free(c);
0406         if (lprops && lprops->free >= min_space)
0407             return lprops;
0408     }
0409     if (pick_free) {
0410         lprops = ubifs_fast_find_empty(c);
0411         if (lprops)
0412             return lprops;
0413     }
0414     if (!squeeze) {
0415         lprops = ubifs_fast_find_free(c);
0416         if (lprops && lprops->free >= min_space)
0417             return lprops;
0418     }
0419     /* There may be an LEB with enough free space on the dirty heap */
0420     heap = &c->lpt_heap[LPROPS_DIRTY - 1];
0421     for (i = 0; i < heap->cnt; i++) {
0422         lprops = heap->arr[i];
0423         if (lprops->free >= min_space)
0424             return lprops;
0425     }
0426     /*
0427      * A LEB may have fallen off of the bottom of the free heap, and ended
0428      * up as uncategorized even though it has enough free space for us now,
0429      * so check the uncategorized list. N.B. neither empty nor freeable LEBs
0430      * can end up as uncategorized because they are kept on lists not
0431      * finite-sized heaps.
0432      */
0433     list_for_each_entry(lprops, &c->uncat_list, list) {
0434         if (lprops->flags & LPROPS_TAKEN)
0435             continue;
0436         if (lprops->flags & LPROPS_INDEX)
0437             continue;
0438         if (lprops->free >= min_space)
0439             return lprops;
0440     }
0441     /* We have looked everywhere in main memory, now scan the flash */
0442     if (c->pnodes_have >= c->pnode_cnt)
0443         /* All pnodes are in memory, so skip scan */
0444         return ERR_PTR(-ENOSPC);
0445     data.min_space = min_space;
0446     data.pick_free = pick_free;
0447     data.lnum = -1;
0448     err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
0449                     (ubifs_lpt_scan_callback)scan_for_free_cb,
0450                     &data);
0451     if (err)
0452         return ERR_PTR(err);
0453     ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt);
0454     c->lscan_lnum = data.lnum;
0455     lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
0456     if (IS_ERR(lprops))
0457         return lprops;
0458     ubifs_assert(c, lprops->lnum == data.lnum);
0459     ubifs_assert(c, lprops->free >= min_space);
0460     ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
0461     ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
0462     return lprops;
0463 }
0464
0465 /**
0466  * ubifs_find_free_space - find a data LEB with free space.
0467  * @c: the UBIFS file-system description object
0468  * @min_space: minimum amount of required free space
0469  * @offs: contains offset of where free space starts on exit
0470  * @squeeze: whether to try to find space in a non-empty LEB first
0471  *
0472  * This function looks for an LEB with at least @min_space bytes of free space.
0473  * It tries to find an empty LEB if possible. If no empty LEBs are available,
0474  * this function searches for a non-empty data LEB. The returned LEB is marked
0475  * as "taken".
0476  *
0477  * This function returns found LEB number in case of success, %-ENOSPC if it
0478  * failed to find a LEB with @min_space bytes of free space and other a negative
0479  * error codes in case of failure.
0480  */
0481 int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs,
0482               int squeeze)
0483 {
0484     const struct ubifs_lprops *lprops;
0485     int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags;
0486
0487     dbg_find("min_space %d", min_space);
0488     ubifs_get_lprops(c);
0489
0490     /* Check if there are enough empty LEBs for commit */
0491     spin_lock(&c->space_lock);
0492     if (c->bi.min_idx_lebs > c->lst.idx_lebs)
0493         rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;
0494     else
0495         rsvd_idx_lebs = 0;
0496     lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
0497            c->lst.taken_empty_lebs;
0498     if (rsvd_idx_lebs < lebs)
0499         /*
0500          * OK to allocate an empty LEB, but we still don't want to go
0501          * looking for one if there aren't any.
0502          */
0503         if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
0504             pick_free = 1;
0505             /*
0506              * Because we release the space lock, we must account
0507              * for this allocation here. After the LEB properties
0508              * flags have been updated, we subtract one. Note, the
0509              * result of this is that lprops also decreases
0510              * @taken_empty_lebs in 'ubifs_change_lp()', so it is
0511              * off by one for a short period of time which may
0512              * introduce a small disturbance to budgeting
0513              * calculations, but this is harmless because at the
0514              * worst case this would make the budgeting subsystem
0515              * be more pessimistic than needed.
0516              *
0517              * Fundamentally, this is about serialization of the
0518              * budgeting and lprops subsystems. We could make the
0519              * @space_lock a mutex and avoid dropping it before
0520              * calling 'ubifs_change_lp()', but mutex is more
0521              * heavy-weight, and we want budgeting to be as fast as
0522              * possible.
0523              */
0524             c->lst.taken_empty_lebs += 1;
0525         }
0526     spin_unlock(&c->space_lock);
0527
0528     lprops = do_find_free_space(c, min_space, pick_free, squeeze);
0529     if (IS_ERR(lprops)) {
0530         err = PTR_ERR(lprops);
0531         goto out;
0532     }
0533
0534     lnum = lprops->lnum;
0535     flags = lprops->flags | LPROPS_TAKEN;
0536
0537     lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);
0538     if (IS_ERR(lprops)) {
0539         err = PTR_ERR(lprops);
0540         goto out;
0541     }
0542
0543     if (pick_free) {
0544         spin_lock(&c->space_lock);
0545         c->lst.taken_empty_lebs -= 1;
0546         spin_unlock(&c->space_lock);
0547     }
0548
0549     *offs = c->leb_size - lprops->free;
0550     ubifs_release_lprops(c);
0551
0552     if (*offs == 0) {
0553         /*
0554          * Ensure that empty LEBs have been unmapped. They may not have
0555          * been, for example, because of an unclean unmount.  Also
0556          * LEBs that were freeable LEBs (free + dirty == leb_size) will
0557          * not have been unmapped.
0558          */
0559         err = ubifs_leb_unmap(c, lnum);
0560         if (err)
0561             return err;
0562     }
0563
0564     dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs);
0565     ubifs_assert(c, *offs <= c->leb_size - min_space);
0566     return lnum;
0567
0568 out:
0569     if (pick_free) {
0570         spin_lock(&c->space_lock);
0571         c->lst.taken_empty_lebs -= 1;
0572         spin_unlock(&c->space_lock);
0573     }
0574     ubifs_release_lprops(c);
0575     return err;
0576 }
0577
0578 /**
0579  * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
0580  * @c: the UBIFS file-system description object
0581  * @lprops: LEB properties to scan
0582  * @in_tree: whether the LEB properties are in main memory
0583  * @data: information passed to and from the caller of the scan
0584  *
0585  * This function returns a code that indicates whether the scan should continue
0586  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
0587  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
0588  * (%LPT_SCAN_STOP).
0589  */
0590 static int scan_for_idx_cb(struct ubifs_info *c,
0591                const struct ubifs_lprops *lprops, int in_tree,
0592                struct scan_data *data)
0593 {
0594     int ret = LPT_SCAN_CONTINUE;
0595
0596     /* Exclude LEBs that are currently in use */
0597     if (lprops->flags & LPROPS_TAKEN)
0598         return LPT_SCAN_CONTINUE;
0599     /* Determine whether to add these LEB properties to the tree */
0600     if (!in_tree && valuable(c, lprops))
0601         ret |= LPT_SCAN_ADD;
0602     /* Exclude index LEBS */
0603     if (lprops->flags & LPROPS_INDEX)
0604         return ret;
0605     /* Exclude LEBs that cannot be made empty */
0606     if (lprops->free + lprops->dirty != c->leb_size)
0607         return ret;
0608     /*
0609      * We are allocating for the index so it is safe to allocate LEBs with
0610      * only free and dirty space, because write buffers are sync'd at commit
0611      * start.
0612      */
0613     data->lnum = lprops->lnum;
0614     return LPT_SCAN_ADD | LPT_SCAN_STOP;
0615 }
0616
0617 /**
0618  * scan_for_leb_for_idx - scan for a free LEB for the index.
0619  * @c: the UBIFS file-system description object
0620  */
0621 static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
0622 {
0623     const struct ubifs_lprops *lprops;
0624     struct scan_data data;
0625     int err;
0626
0627     data.lnum = -1;
0628     err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
0629                     (ubifs_lpt_scan_callback)scan_for_idx_cb,
0630                     &data);
0631     if (err)
0632         return ERR_PTR(err);
0633     ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt);
0634     c->lscan_lnum = data.lnum;
0635     lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
0636     if (IS_ERR(lprops))
0637         return lprops;
0638     ubifs_assert(c, lprops->lnum == data.lnum);
0639     ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);
0640     ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
0641     ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
0642     return lprops;
0643 }
0644
0645 /**
0646  * ubifs_find_free_leb_for_idx - find a free LEB for the index.
0647  * @c: the UBIFS file-system description object
0648  *
0649  * This function looks for a free LEB and returns that LEB number. The returned
0650  * LEB is marked as "taken", "index".
0651  *
0652  * Only empty LEBs are allocated. This is for two reasons. First, the commit
0653  * calculates the number of LEBs to allocate based on the assumption that they
0654  * will be empty. Secondly, free space at the end of an index LEB is not
0655  * guaranteed to be empty because it may have been used by the in-the-gaps
0656  * method prior to an unclean unmount.
0657  *
0658  * If no LEB is found %-ENOSPC is returned. For other failures another negative
0659  * error code is returned.
0660  */
0661 int ubifs_find_free_leb_for_idx(struct ubifs_info *c)
0662 {
0663     const struct ubifs_lprops *lprops;
0664     int lnum = -1, err, flags;
0665
0666     ubifs_get_lprops(c);
0667
0668     lprops = ubifs_fast_find_empty(c);
0669     if (!lprops) {
0670         lprops = ubifs_fast_find_freeable(c);
0671         if (!lprops) {
0672             /*
0673              * The first condition means the following: go scan the
0674              * LPT if there are uncategorized lprops, which means
0675              * there may be freeable LEBs there (UBIFS does not
0676              * store the information about freeable LEBs in the
0677              * master node).
0678              */
0679             if (c->in_a_category_cnt != c->main_lebs ||
0680                 c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
0681                 ubifs_assert(c, c->freeable_cnt == 0);
0682                 lprops = scan_for_leb_for_idx(c);
0683                 if (IS_ERR(lprops)) {
0684                     err = PTR_ERR(lprops);
0685                     goto out;
0686                 }
0687             }
0688         }
0689     }
0690
0691     if (!lprops) {
0692         err = -ENOSPC;
0693         goto out;
0694     }
0695
0696     lnum = lprops->lnum;
0697
0698     dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
0699          lnum, lprops->free, lprops->dirty, lprops->flags);
0700
0701     flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
0702     lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
0703     if (IS_ERR(lprops)) {
0704         err = PTR_ERR(lprops);
0705         goto out;
0706     }
0707
0708     ubifs_release_lprops(c);
0709
0710     /*
0711      * Ensure that empty LEBs have been unmapped. They may not have been,
0712      * for example, because of an unclean unmount. Also LEBs that were
0713      * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
0714      */
0715     err = ubifs_leb_unmap(c, lnum);
0716     if (err) {
0717         ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
0718                     LPROPS_TAKEN | LPROPS_INDEX, 0);
0719         return err;
0720     }
0721
0722     return lnum;
0723
0724 out:
0725     ubifs_release_lprops(c);
0726     return err;
0727 }
0728
0729 static int cmp_dirty_idx(const struct ubifs_lprops **a,
0730              const struct ubifs_lprops **b)
0731 {
0732     const struct ubifs_lprops *lpa = *a;
0733     const struct ubifs_lprops *lpb = *b;
0734
0735     return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
0736 }
0737
0738 /**
0739  * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
0740  * @c: the UBIFS file-system description object
0741  *
0742  * This function is called each commit to create an array of LEB numbers of
0743  * dirty index LEBs sorted in order of dirty and free space.  This is used by
0744  * the in-the-gaps method of TNC commit.
0745  */
0746 int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
0747 {
0748     int i;
0749
0750     ubifs_get_lprops(c);
0751     /* Copy the LPROPS_DIRTY_IDX heap */
0752     c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
0753     memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
0754            sizeof(void *) * c->dirty_idx.cnt);
0755     /* Sort it so that the dirtiest is now at the end */
0756     sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
0757          (int (*)(const void *, const void *))cmp_dirty_idx, NULL);
0758     dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
0759     if (c->dirty_idx.cnt)
0760         dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
0761              c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
0762              c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
0763              c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
0764     /* Replace the lprops pointers with LEB numbers */
0765     for (i = 0; i < c->dirty_idx.cnt; i++)
0766         c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
0767     ubifs_release_lprops(c);
0768     return 0;
0769 }
0770
0771 /**
0772  * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
0773  * @c: the UBIFS file-system description object
0774  * @lprops: LEB properties to scan
0775  * @in_tree: whether the LEB properties are in main memory
0776  * @data: information passed to and from the caller of the scan
0777  *
0778  * This function returns a code that indicates whether the scan should continue
0779  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
0780  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
0781  * (%LPT_SCAN_STOP).
0782  */
0783 static int scan_dirty_idx_cb(struct ubifs_info *c,
0784                const struct ubifs_lprops *lprops, int in_tree,
0785                struct scan_data *data)
0786 {
0787     int ret = LPT_SCAN_CONTINUE;
0788
0789     /* Exclude LEBs that are currently in use */
0790     if (lprops->flags & LPROPS_TAKEN)
0791         return LPT_SCAN_CONTINUE;
0792     /* Determine whether to add these LEB properties to the tree */
0793     if (!in_tree && valuable(c, lprops))
0794         ret |= LPT_SCAN_ADD;
0795     /* Exclude non-index LEBs */
0796     if (!(lprops->flags & LPROPS_INDEX))
0797         return ret;
0798     /* Exclude LEBs with too little space */
0799     if (lprops->free + lprops->dirty < c->min_idx_node_sz)
0800         return ret;
0801     /* Finally we found space */
0802     data->lnum = lprops->lnum;
0803     return LPT_SCAN_ADD | LPT_SCAN_STOP;
0804 }
0805
0806 /**
0807  * find_dirty_idx_leb - find a dirty index LEB.
0808  * @c: the UBIFS file-system description object
0809  *
0810  * This function returns LEB number upon success and a negative error code upon
0811  * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
0812  * found.
0813  *
0814  * Note that this function scans the entire LPT but it is called very rarely.
0815  */
0816 static int find_dirty_idx_leb(struct ubifs_info *c)
0817 {
0818     const struct ubifs_lprops *lprops;
0819     struct ubifs_lpt_heap *heap;
0820     struct scan_data data;
0821     int err, i, ret;
0822
0823     /* Check all structures in memory first */
0824     data.lnum = -1;
0825     heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
0826     for (i = 0; i < heap->cnt; i++) {
0827         lprops = heap->arr[i];
0828         ret = scan_dirty_idx_cb(c, lprops, 1, &data);
0829         if (ret & LPT_SCAN_STOP)
0830             goto found;
0831     }
0832     list_for_each_entry(lprops, &c->frdi_idx_list, list) {
0833         ret = scan_dirty_idx_cb(c, lprops, 1, &data);
0834         if (ret & LPT_SCAN_STOP)
0835             goto found;
0836     }
0837     list_for_each_entry(lprops, &c->uncat_list, list) {
0838         ret = scan_dirty_idx_cb(c, lprops, 1, &data);
0839         if (ret & LPT_SCAN_STOP)
0840             goto found;
0841     }
0842     if (c->pnodes_have >= c->pnode_cnt)
0843         /* All pnodes are in memory, so skip scan */
0844         return -ENOSPC;
0845     err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
0846                     (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
0847                     &data);
0848     if (err)
0849         return err;
0850 found:
0851     ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt);
0852     c->lscan_lnum = data.lnum;
0853     lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
0854     if (IS_ERR(lprops))
0855         return PTR_ERR(lprops);
0856     ubifs_assert(c, lprops->lnum == data.lnum);
0857     ubifs_assert(c, lprops->free + lprops->dirty >= c->min_idx_node_sz);
0858     ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
0859     ubifs_assert(c, (lprops->flags & LPROPS_INDEX));
0860
0861     dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
0862          lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
0863
0864     lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
0865                  lprops->flags | LPROPS_TAKEN, 0);
0866     if (IS_ERR(lprops))
0867         return PTR_ERR(lprops);
0868
0869     return lprops->lnum;
0870 }
0871
0872 /**
0873  * get_idx_gc_leb - try to get a LEB number from trivial GC.
0874  * @c: the UBIFS file-system description object
0875  */
0876 static int get_idx_gc_leb(struct ubifs_info *c)
0877 {
0878     const struct ubifs_lprops *lp;
0879     int err, lnum;
0880
0881     err = ubifs_get_idx_gc_leb(c);
0882     if (err < 0)
0883         return err;
0884     lnum = err;
0885     /*
0886      * The LEB was due to be unmapped after the commit but
0887      * it is needed now for this commit.
0888      */
0889     lp = ubifs_lpt_lookup_dirty(c, lnum);
0890     if (IS_ERR(lp))
0891         return PTR_ERR(lp);
0892     lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
0893                  lp->flags | LPROPS_INDEX, -1);
0894     if (IS_ERR(lp))
0895         return PTR_ERR(lp);
0896     dbg_find("LEB %d, dirty %d and free %d flags %#x",
0897          lp->lnum, lp->dirty, lp->free, lp->flags);
0898     return lnum;
0899 }
0900
0901 /**
0902  * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
0903  * @c: the UBIFS file-system description object
0904  */
0905 static int find_dirtiest_idx_leb(struct ubifs_info *c)
0906 {
0907     const struct ubifs_lprops *lp;
0908     int lnum;
0909
0910     while (1) {
0911         if (!c->dirty_idx.cnt)
0912             return -ENOSPC;
0913         /* The lprops pointers were replaced by LEB numbers */
0914         lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
0915         lp = ubifs_lpt_lookup(c, lnum);
0916         if (IS_ERR(lp))
0917             return PTR_ERR(lp);
0918         if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
0919             continue;
0920         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
0921                      lp->flags | LPROPS_TAKEN, 0);
0922         if (IS_ERR(lp))
0923             return PTR_ERR(lp);
0924         break;
0925     }
0926     dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
0927          lp->free, lp->flags);
0928     ubifs_assert(c, lp->flags & LPROPS_TAKEN);
0929     ubifs_assert(c, lp->flags & LPROPS_INDEX);
0930     return lnum;
0931 }
0932
0933 /**
0934  * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
0935  * @c: the UBIFS file-system description object
0936  *
0937  * This function attempts to find an untaken index LEB with the most free and
0938  * dirty space that can be used without overwriting index nodes that were in the
0939  * last index committed.
0940  */
0941 int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
0942 {
0943     int err;
0944
0945     ubifs_get_lprops(c);
0946
0947     /*
0948      * We made an array of the dirtiest index LEB numbers as at the start of
0949      * last commit.  Try that array first.
0950      */
0951     err = find_dirtiest_idx_leb(c);
0952
0953     /* Next try scanning the entire LPT */
0954     if (err == -ENOSPC)
0955         err = find_dirty_idx_leb(c);
0956
0957     /* Finally take any index LEBs awaiting trivial GC */
0958     if (err == -ENOSPC)
0959         err = get_idx_gc_leb(c);
0960
0961     ubifs_release_lprops(c);
0962     return err;
0963 }