LCOV - code coverage report
Current view: top level - libubifs - find.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 211 346 61.0 %
Date: 2024-06-05 20:10:43 Functions: 13 17 76.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13