LCOV - code coverage report
Current view: top level - libubifs - budget.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 118 166 71.1 %
Date: 2024-06-05 20:10:43 Functions: 6 9 66.7 %
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: Adrian Hunter
       8             :  *          Artem Bityutskiy (Битюцкий Артём)
       9             :  */
      10             : 
      11             : /*
      12             :  * This file implements the budgeting sub-system which is responsible for UBIFS
      13             :  * space management.
      14             :  *
      15             :  * Factors such as compression, wasted space at the ends of LEBs, space in other
      16             :  * journal heads, the effect of updates on the index, and so on, make it
      17             :  * impossible to accurately predict the amount of space needed. Consequently
      18             :  * approximations are used.
      19             :  */
      20             : 
      21             : #include "bitops.h"
      22             : #include "ubifs.h"
      23             : #include "defs.h"
      24             : #include "debug.h"
      25             : #include "misc.h"
      26             : 
      27             : /*
      28             :  * When pessimistic budget calculations say that there is no enough space,
      29             :  * UBIFS starts writing back dirty inodes and pages, doing garbage collection,
      30             :  * or committing. The below constant defines maximum number of times UBIFS
      31             :  * repeats the operations.
      32             :  */
      33             : #define MAX_MKSPC_RETRIES 3
      34             : 
      35             : /**
      36             :  * run_gc - run garbage collector.
      37             :  * @c: UBIFS file-system description object
      38             :  *
      39             :  * This function runs garbage collector to make some more free space. Returns
      40             :  * zero if a free LEB has been produced, %-EAGAIN if commit is required, and a
      41             :  * negative error code in case of failure.
      42             :  */
      43           0 : static int run_gc(struct ubifs_info *c)
      44             : {
      45             :         int lnum;
      46             : 
      47             :         /* Make some free space by garbage-collecting dirty space */
      48           0 :         down_read(&c->commit_sem);
      49           0 :         lnum = ubifs_garbage_collect(c, 1);
      50           0 :         up_read(&c->commit_sem);
      51           0 :         if (lnum < 0)
      52             :                 return lnum;
      53             : 
      54             :         /* GC freed one LEB, return it to lprops */
      55           0 :         dbg_budg("GC freed LEB %d", lnum);
      56           0 :         return ubifs_return_leb(c, lnum);
      57             : }
      58             : 
      59             : /**
      60             :  * make_free_space - make more free space on the file-system.
      61             :  * @c: UBIFS file-system description object
      62             :  *
      63             :  * This function is called when an operation cannot be budgeted because there
      64             :  * is supposedly no free space. But in most cases there is some free space:
      65             :  *   o budgeting is pessimistic, so it always budgets more than it is actually
      66             :  *     needed, so shrinking the liability is one way to make free space - the
      67             :  *     cached data will take less space then it was budgeted for;
      68             :  *   o GC may turn some dark space into free space (budgeting treats dark space
      69             :  *     as not available);
      70             :  *   o commit may free some LEB, i.e., turn freeable LEBs into free LEBs.
      71             :  *
      72             :  * So this function tries to do the above. Returns %-EAGAIN if some free space
      73             :  * was presumably made and the caller has to re-try budgeting the operation.
      74             :  * Returns %-ENOSPC if it couldn't do more free space, and other negative error
      75             :  * codes on failures.
      76             :  */
      77           0 : static int make_free_space(struct ubifs_info *c)
      78             : {
      79           0 :         int err, retries = 0;
      80             : 
      81             :         do {
      82           0 :                 dbg_budg("Run GC");
      83           0 :                 err = run_gc(c);
      84           0 :                 if (!err)
      85             :                         return -EAGAIN;
      86             : 
      87           0 :                 if (err != -EAGAIN && err != -ENOSPC)
      88             :                         /* Some real error happened */
      89             :                         return err;
      90             : 
      91           0 :                 dbg_budg("Run commit (retries %d)", retries);
      92           0 :                 err = ubifs_run_commit(c);
      93           0 :                 if (err)
      94             :                         return err;
      95           0 :         } while (retries++ < MAX_MKSPC_RETRIES);
      96             : 
      97             :         return -ENOSPC;
      98             : }
      99             : 
     100             : /**
     101             :  * ubifs_calc_min_idx_lebs - calculate amount of LEBs for the index.
     102             :  * @c: UBIFS file-system description object
     103             :  *
     104             :  * This function calculates and returns the number of LEBs which should be kept
     105             :  * for index usage.
     106             :  */
     107       11318 : int ubifs_calc_min_idx_lebs(struct ubifs_info *c)
     108             : {
     109             :         int idx_lebs;
     110             :         long long idx_size;
     111             : 
     112       11793 :         idx_size = c->bi.old_idx_sz + c->bi.idx_growth + c->bi.uncommitted_idx;
     113             :         /* And make sure we have thrice the index size of space reserved */
     114       11793 :         idx_size += idx_size << 1;
     115             :         /*
     116             :          * We do not maintain 'old_idx_size' as 'old_idx_lebs'/'old_idx_bytes'
     117             :          * pair, nor similarly the two variables for the new index size, so we
     118             :          * have to do this costly 64-bit division on fast-path.
     119             :          */
     120       23586 :         idx_lebs = div_u64(idx_size + c->idx_leb_size - 1, c->idx_leb_size);
     121             :         /*
     122             :          * The index head is not available for the in-the-gaps method, so add an
     123             :          * extra LEB to compensate.
     124             :          */
     125       11793 :         idx_lebs += 1;
     126       11793 :         if (idx_lebs < MIN_INDEX_LEBS)
     127           0 :                 idx_lebs = MIN_INDEX_LEBS;
     128       11318 :         return idx_lebs;
     129             : }
     130             : 
     131             : /**
     132             :  * ubifs_calc_available - calculate available FS space.
     133             :  * @c: UBIFS file-system description object
     134             :  * @min_idx_lebs: minimum number of LEBs reserved for the index
     135             :  *
     136             :  * This function calculates and returns amount of FS space available for use.
     137             :  */
     138           1 : long long ubifs_calc_available(const struct ubifs_info *c, int min_idx_lebs)
     139             : {
     140             :         int subtract_lebs;
     141             :         long long available;
     142             : 
     143         239 :         available = c->main_bytes - c->lst.total_used;
     144             : 
     145             :         /*
     146             :          * Now 'available' contains theoretically available flash space
     147             :          * assuming there is no index, so we have to subtract the space which
     148             :          * is reserved for the index.
     149             :          */
     150         239 :         subtract_lebs = min_idx_lebs;
     151             : 
     152             :         /* Take into account that GC reserves one LEB for its own needs */
     153         239 :         subtract_lebs += 1;
     154             : 
     155             :         /*
     156             :          * Since different write types go to different heads, we should
     157             :          * reserve one leb for each head.
     158             :          */
     159         239 :         subtract_lebs += c->jhead_cnt;
     160             : 
     161             :         /* We also reserve one LEB for deletions, which bypass budgeting */
     162         239 :         subtract_lebs += 1;
     163             : 
     164         239 :         available -= (long long)subtract_lebs * c->leb_size;
     165             : 
     166             :         /* Subtract the dead space which is not available for use */
     167         239 :         available -= c->lst.total_dead;
     168             : 
     169             :         /*
     170             :          * Subtract dark space, which might or might not be usable - it depends
     171             :          * on the data which we have on the media and which will be written. If
     172             :          * this is a lot of uncompressed or not-compressible data, the dark
     173             :          * space cannot be used.
     174             :          */
     175         239 :         available -= c->lst.total_dark;
     176             : 
     177             :         /*
     178             :          * However, there is more dark space. The index may be bigger than
     179             :          * @min_idx_lebs. Those extra LEBs are assumed to be available, but
     180             :          * their dark space is not included in total_dark, so it is subtracted
     181             :          * here.
     182             :          */
     183         239 :         if (c->lst.idx_lebs > min_idx_lebs) {
     184          66 :                 subtract_lebs = c->lst.idx_lebs - min_idx_lebs;
     185          66 :                 available -= subtract_lebs * c->dark_wm;
     186             :         }
     187             : 
     188             :         /* The calculations are rough and may end up with a negative number */
     189         239 :         return available > 0 ? available : 0;
     190             : }
     191             : 
     192             : /**
     193             :  * can_use_rp - check whether the user is allowed to use reserved pool.
     194             :  * @c: UBIFS file-system description object
     195             :  *
     196             :  * UBIFS has so-called "reserved pool" which is flash space reserved
     197             :  * for the superuser and for uses whose UID/GID is recorded in UBIFS superblock.
     198             :  * This function checks whether current user is allowed to use reserved pool.
     199             :  * Returns %1  current user is allowed to use reserved pool and %0 otherwise.
     200             :  */
     201             : static int can_use_rp(__unused struct ubifs_info *c)
     202             : {
     203             :         /* Fsck can always use reserved pool. */
     204          12 :         return c->program_type == FSCK_PROGRAM_TYPE;
     205             : }
     206             : 
     207             : /**
     208             :  * do_budget_space - reserve flash space for index and data growth.
     209             :  * @c: UBIFS file-system description object
     210             :  *
     211             :  * This function makes sure UBIFS has enough free LEBs for index growth and
     212             :  * data.
     213             :  *
     214             :  * When budgeting index space, UBIFS reserves thrice as many LEBs as the index
     215             :  * would take if it was consolidated and written to the flash. This guarantees
     216             :  * that the "in-the-gaps" commit method always succeeds and UBIFS will always
     217             :  * be able to commit dirty index. So this function basically adds amount of
     218             :  * budgeted index space to the size of the current index, multiplies this by 3,
     219             :  * and makes sure this does not exceed the amount of free LEBs.
     220             :  *
     221             :  * Notes about @c->bi.min_idx_lebs and @c->lst.idx_lebs variables:
     222             :  * o @c->lst.idx_lebs is the number of LEBs the index currently uses. It might
     223             :  *    be large, because UBIFS does not do any index consolidation as long as
     224             :  *    there is free space. IOW, the index may take a lot of LEBs, but the LEBs
     225             :  *    will contain a lot of dirt.
     226             :  * o @c->bi.min_idx_lebs is the number of LEBS the index presumably takes. IOW,
     227             :  *    the index may be consolidated to take up to @c->bi.min_idx_lebs LEBs.
     228             :  *
     229             :  * This function returns zero in case of success, and %-ENOSPC in case of
     230             :  * failure.
     231             :  */
     232         237 : static int do_budget_space(struct ubifs_info *c)
     233             : {
     234             :         long long outstanding, available;
     235             :         int lebs, rsvd_idx_lebs, min_idx_lebs;
     236             : 
     237             :         /* First budget index space */
     238         237 :         min_idx_lebs = ubifs_calc_min_idx_lebs(c);
     239             : 
     240             :         /* Now 'min_idx_lebs' contains number of LEBs to reserve */
     241         237 :         if (min_idx_lebs > c->lst.idx_lebs)
     242         169 :                 rsvd_idx_lebs = min_idx_lebs - c->lst.idx_lebs;
     243             :         else
     244             :                 rsvd_idx_lebs = 0;
     245             : 
     246             :         /*
     247             :          * The number of LEBs that are available to be used by the index is:
     248             :          *
     249             :          *    @c->lst.empty_lebs + @c->freeable_cnt + @c->idx_gc_cnt -
     250             :          *    @c->lst.taken_empty_lebs
     251             :          *
     252             :          * @c->lst.empty_lebs are available because they are empty.
     253             :          * @c->freeable_cnt are available because they contain only free and
     254             :          * dirty space, @c->idx_gc_cnt are available because they are index
     255             :          * LEBs that have been garbage collected and are awaiting the commit
     256             :          * before they can be used. And the in-the-gaps method will grab these
     257             :          * if it needs them. @c->lst.taken_empty_lebs are empty LEBs that have
     258             :          * already been allocated for some purpose.
     259             :          *
     260             :          * Note, @c->idx_gc_cnt is included to both @c->lst.empty_lebs (because
     261             :          * these LEBs are empty) and to @c->lst.taken_empty_lebs (because they
     262             :          * are taken until after the commit).
     263             :          *
     264             :          * Note, @c->lst.taken_empty_lebs may temporarily be higher by one
     265             :          * because of the way we serialize LEB allocations and budgeting. See a
     266             :          * comment in 'ubifs_find_free_space()'.
     267             :          */
     268         474 :         lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
     269         237 :                c->lst.taken_empty_lebs;
     270         237 :         if (unlikely(rsvd_idx_lebs > lebs)) {
     271           0 :                 dbg_budg("out of indexing space: min_idx_lebs %d (old %d), rsvd_idx_lebs %d",
     272             :                          min_idx_lebs, c->bi.min_idx_lebs, rsvd_idx_lebs);
     273             :                 return -ENOSPC;
     274             :         }
     275             : 
     276         237 :         available = ubifs_calc_available(c, min_idx_lebs);
     277         237 :         outstanding = c->bi.data_growth + c->bi.dd_growth;
     278             : 
     279         237 :         if (unlikely(available < outstanding)) {
     280           0 :                 dbg_budg("out of data space: available %lld, outstanding %lld",
     281             :                          available, outstanding);
     282             :                 return -ENOSPC;
     283             :         }
     284             : 
     285         249 :         if (available - outstanding <= c->rp_size && !can_use_rp(c))
     286             :                 return -ENOSPC;
     287             : 
     288         237 :         c->bi.min_idx_lebs = min_idx_lebs;
     289         237 :         return 0;
     290             : }
     291             : 
     292             : /**
     293             :  * calc_idx_growth - calculate approximate index growth from budgeting request.
     294             :  * @c: UBIFS file-system description object
     295             :  * @req: budgeting request
     296             :  *
     297             :  * For now we assume each new node adds one znode. But this is rather poor
     298             :  * approximation, though.
     299             :  */
     300             : static int calc_idx_growth(const struct ubifs_info *c,
     301             :                            const struct ubifs_budget_req *req)
     302             : {
     303             :         int znodes;
     304             : 
     305         474 :         znodes = req->new_ino + (req->new_page << UBIFS_BLOCKS_PER_PAGE_SHIFT) +
     306         237 :                  req->new_dent;
     307         237 :         return znodes * c->max_idx_node_sz;
     308             : }
     309             : 
     310             : /**
     311             :  * calc_data_growth - calculate approximate amount of new data from budgeting
     312             :  * request.
     313             :  * @c: UBIFS file-system description object
     314             :  * @req: budgeting request
     315             :  */
     316             : static int calc_data_growth(const struct ubifs_info *c,
     317             :                             const struct ubifs_budget_req *req)
     318             : {
     319             :         int data_growth;
     320             : 
     321         237 :         data_growth = req->new_ino  ? c->bi.inode_budget : 0;
     322         237 :         if (req->new_page)
     323           0 :                 data_growth += c->bi.page_budget;
     324         237 :         if (req->new_dent)
     325         232 :                 data_growth += c->bi.dent_budget;
     326         237 :         data_growth += req->new_ino_d;
     327             :         return data_growth;
     328             : }
     329             : 
     330             : /**
     331             :  * calc_dd_growth - calculate approximate amount of data which makes other data
     332             :  * dirty from budgeting request.
     333             :  * @c: UBIFS file-system description object
     334             :  * @req: budgeting request
     335             :  */
     336             : static int calc_dd_growth(const struct ubifs_info *c,
     337             :                           const struct ubifs_budget_req *req)
     338             : {
     339             :         int dd_growth;
     340             : 
     341         237 :         dd_growth = req->dirtied_page ? c->bi.page_budget : 0;
     342             : 
     343         237 :         if (req->dirtied_ino)
     344         232 :                 dd_growth += c->bi.inode_budget * req->dirtied_ino;
     345         237 :         if (req->mod_dent)
     346           0 :                 dd_growth += c->bi.dent_budget;
     347         237 :         dd_growth += req->dirtied_ino_d;
     348             :         return dd_growth;
     349             : }
     350             : 
     351             : /**
     352             :  * ubifs_budget_space - ensure there is enough space to complete an operation.
     353             :  * @c: UBIFS file-system description object
     354             :  * @req: budget request
     355             :  *
     356             :  * This function allocates budget for an operation. It uses pessimistic
     357             :  * approximation of how much flash space the operation needs. The goal of this
     358             :  * function is to make sure UBIFS always has flash space to flush all dirty
     359             :  * pages, dirty inodes, and dirty znodes (liability). This function may force
     360             :  * commit, garbage-collection or write-back. Returns zero in case of success,
     361             :  * %-ENOSPC if there is no free space and other negative error codes in case of
     362             :  * failures.
     363             :  */
     364         237 : int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req)
     365             : {
     366         237 :         int err, idx_growth, data_growth, dd_growth, retried = 0;
     367             : 
     368             :         ubifs_assert(c, req->new_page <= 1);
     369             :         ubifs_assert(c, req->dirtied_page <= 1);
     370             :         ubifs_assert(c, req->new_dent <= 1);
     371             :         ubifs_assert(c, req->mod_dent <= 1);
     372             :         ubifs_assert(c, req->new_ino <= 1);
     373         237 :         ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA);
     374         237 :         ubifs_assert(c, req->dirtied_ino <= 4);
     375         237 :         ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4);
     376         237 :         ubifs_assert(c, !(req->new_ino_d & 7));
     377         237 :         ubifs_assert(c, !(req->dirtied_ino_d & 7));
     378             : 
     379         237 :         data_growth = calc_data_growth(c, req);
     380         237 :         dd_growth = calc_dd_growth(c, req);
     381         237 :         if (!data_growth && !dd_growth)
     382             :                 return 0;
     383         237 :         idx_growth = calc_idx_growth(c, req);
     384             : 
     385             : again:
     386         237 :         spin_lock(&c->space_lock);
     387         237 :         ubifs_assert(c, c->bi.idx_growth >= 0);
     388         237 :         ubifs_assert(c, c->bi.data_growth >= 0);
     389         237 :         ubifs_assert(c, c->bi.dd_growth >= 0);
     390             : 
     391         237 :         if (unlikely(c->bi.nospace) && (c->bi.nospace_rp || !can_use_rp(c))) {
     392           0 :                 dbg_budg("no space");
     393           0 :                 spin_unlock(&c->space_lock);
     394           0 :                 return -ENOSPC;
     395             :         }
     396             : 
     397         237 :         c->bi.idx_growth += idx_growth;
     398         237 :         c->bi.data_growth += data_growth;
     399         237 :         c->bi.dd_growth += dd_growth;
     400             : 
     401         237 :         err = do_budget_space(c);
     402         237 :         if (likely(!err)) {
     403         237 :                 req->idx_growth = idx_growth;
     404         237 :                 req->data_growth = data_growth;
     405         237 :                 req->dd_growth = dd_growth;
     406         237 :                 spin_unlock(&c->space_lock);
     407         237 :                 return 0;
     408             :         }
     409             : 
     410             :         /* Restore the old values */
     411           0 :         c->bi.idx_growth -= idx_growth;
     412           0 :         c->bi.data_growth -= data_growth;
     413           0 :         c->bi.dd_growth -= dd_growth;
     414           0 :         spin_unlock(&c->space_lock);
     415             : 
     416           0 :         if (req->fast) {
     417           0 :                 dbg_budg("no space for fast budgeting");
     418             :                 return err;
     419             :         }
     420             : 
     421           0 :         err = make_free_space(c);
     422             :         cond_resched();
     423           0 :         if (err == -EAGAIN) {
     424           0 :                 dbg_budg("try again");
     425             :                 goto again;
     426           0 :         } else if (err == -ENOSPC) {
     427           0 :                 if (!retried) {
     428           0 :                         retried = 1;
     429           0 :                         dbg_budg("-ENOSPC, but anyway try once again");
     430             :                         goto again;
     431             :                 }
     432           0 :                 dbg_budg("FS is full, -ENOSPC");
     433           0 :                 c->bi.nospace = 1;
     434           0 :                 if (can_use_rp(c) || c->rp_size == 0)
     435           0 :                         c->bi.nospace_rp = 1;
     436             :                 smp_wmb();
     437             :         } else
     438           0 :                 ubifs_err(c, "cannot budget space, error %d", err);
     439             :         return err;
     440             : }
     441             : 
     442             : /**
     443             :  * ubifs_release_budget - release budgeted free space.
     444             :  * @c: UBIFS file-system description object
     445             :  * @req: budget request
     446             :  *
     447             :  * This function releases the space budgeted by 'ubifs_budget_space()'. Note,
     448             :  * since the index changes (which were budgeted for in @req->idx_growth) will
     449             :  * only be written to the media on commit, this function moves the index budget
     450             :  * from @c->bi.idx_growth to @c->bi.uncommitted_idx. The latter will be zeroed
     451             :  * by the commit operation.
     452             :  */
     453         237 : void ubifs_release_budget(struct ubifs_info *c, struct ubifs_budget_req *req)
     454             : {
     455             :         ubifs_assert(c, req->new_page <= 1);
     456             :         ubifs_assert(c, req->dirtied_page <= 1);
     457             :         ubifs_assert(c, req->new_dent <= 1);
     458             :         ubifs_assert(c, req->mod_dent <= 1);
     459             :         ubifs_assert(c, req->new_ino <= 1);
     460         237 :         ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA);
     461         237 :         ubifs_assert(c, req->dirtied_ino <= 4);
     462         237 :         ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4);
     463         237 :         ubifs_assert(c, !(req->new_ino_d & 7));
     464         237 :         ubifs_assert(c, !(req->dirtied_ino_d & 7));
     465         237 :         if (!req->recalculate) {
     466         237 :                 ubifs_assert(c, req->idx_growth >= 0);
     467         237 :                 ubifs_assert(c, req->data_growth >= 0);
     468         237 :                 ubifs_assert(c, req->dd_growth >= 0);
     469             :         }
     470             : 
     471         237 :         if (req->recalculate) {
     472           0 :                 req->data_growth = calc_data_growth(c, req);
     473           0 :                 req->dd_growth = calc_dd_growth(c, req);
     474           0 :                 req->idx_growth = calc_idx_growth(c, req);
     475             :         }
     476             : 
     477         237 :         if (!req->data_growth && !req->dd_growth)
     478             :                 return;
     479             : 
     480         237 :         c->bi.nospace = c->bi.nospace_rp = 0;
     481             :         smp_wmb();
     482             : 
     483         237 :         spin_lock(&c->space_lock);
     484         237 :         c->bi.idx_growth -= req->idx_growth;
     485         237 :         c->bi.uncommitted_idx += req->idx_growth;
     486         237 :         c->bi.data_growth -= req->data_growth;
     487         237 :         c->bi.dd_growth -= req->dd_growth;
     488         237 :         c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c);
     489             : 
     490         237 :         ubifs_assert(c, c->bi.idx_growth >= 0);
     491         237 :         ubifs_assert(c, c->bi.data_growth >= 0);
     492         237 :         ubifs_assert(c, c->bi.dd_growth >= 0);
     493         237 :         ubifs_assert(c, c->bi.min_idx_lebs < c->main_lebs);
     494         237 :         ubifs_assert(c, !(c->bi.idx_growth & 7));
     495         237 :         ubifs_assert(c, !(c->bi.data_growth & 7));
     496         237 :         ubifs_assert(c, !(c->bi.dd_growth & 7));
     497         237 :         spin_unlock(&c->space_lock);
     498             : }
     499             : 
     500             : /**
     501             :  * ubifs_reported_space - calculate reported free space.
     502             :  * @c: the UBIFS file-system description object
     503             :  * @free: amount of free space
     504             :  *
     505             :  * This function calculates amount of free space which will be reported to
     506             :  * user-space. User-space application tend to expect that if the file-system
     507             :  * (e.g., via the 'statfs()' call) reports that it has N bytes available, they
     508             :  * are able to write a file of size N. UBIFS attaches node headers to each data
     509             :  * node and it has to write indexing nodes as well. This introduces additional
     510             :  * overhead, and UBIFS has to report slightly less free space to meet the above
     511             :  * expectations.
     512             :  *
     513             :  * This function assumes free space is made up of uncompressed data nodes and
     514             :  * full index nodes (one per data node, tripled because we always allow enough
     515             :  * space to write the index thrice).
     516             :  *
     517             :  * Note, the calculation is pessimistic, which means that most of the time
     518             :  * UBIFS reports less space than it actually has.
     519             :  */
     520           0 : long long ubifs_reported_space(const struct ubifs_info *c, long long free)
     521             : {
     522             :         int divisor, factor, f;
     523             : 
     524             :         /*
     525             :          * Reported space size is @free * X, where X is UBIFS block size
     526             :          * divided by UBIFS block size + all overhead one data block
     527             :          * introduces. The overhead is the node header + indexing overhead.
     528             :          *
     529             :          * Indexing overhead calculations are based on the following formula:
     530             :          * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number
     531             :          * of data nodes, f - fanout. Because effective UBIFS fanout is twice
     532             :          * as less than maximum fanout, we assume that each data node
     533             :          * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes.
     534             :          * Note, the multiplier 3 is because UBIFS reserves thrice as more space
     535             :          * for the index.
     536             :          */
     537           1 :         f = c->fanout > 3 ? c->fanout >> 1 : 2;
     538           1 :         factor = UBIFS_BLOCK_SIZE;
     539           1 :         divisor = UBIFS_MAX_DATA_NODE_SZ;
     540           1 :         divisor += (c->max_idx_node_sz * 3) / (f - 1);
     541           1 :         free *= factor;
     542           2 :         return div_u64(free, divisor);
     543             : }
     544             : 
     545             : /**
     546             :  * ubifs_get_free_space_nolock - return amount of free space.
     547             :  * @c: UBIFS file-system description object
     548             :  *
     549             :  * This function calculates amount of free space to report to user-space.
     550             :  *
     551             :  * Because UBIFS may introduce substantial overhead (the index, node headers,
     552             :  * alignment, wastage at the end of LEBs, etc), it cannot report real amount of
     553             :  * free flash space it has (well, because not all dirty space is reclaimable,
     554             :  * UBIFS does not actually know the real amount). If UBIFS did so, it would
     555             :  * bread user expectations about what free space is. Users seem to accustomed
     556             :  * to assume that if the file-system reports N bytes of free space, they would
     557             :  * be able to fit a file of N bytes to the FS. This almost works for
     558             :  * traditional file-systems, because they have way less overhead than UBIFS.
     559             :  * So, to keep users happy, UBIFS tries to take the overhead into account.
     560             :  */
     561           1 : long long ubifs_get_free_space_nolock(struct ubifs_info *c)
     562             : {
     563             :         int rsvd_idx_lebs, lebs;
     564             :         long long available, outstanding, free;
     565             : 
     566           2 :         ubifs_assert(c, c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c));
     567           1 :         outstanding = c->bi.data_growth + c->bi.dd_growth;
     568           2 :         available = ubifs_calc_available(c, c->bi.min_idx_lebs);
     569             : 
     570             :         /*
     571             :          * When reporting free space to user-space, UBIFS guarantees that it is
     572             :          * possible to write a file of free space size. This means that for
     573             :          * empty LEBs we may use more precise calculations than
     574             :          * 'ubifs_calc_available()' is using. Namely, we know that in empty
     575             :          * LEBs we would waste only @c->leb_overhead bytes, not @c->dark_wm.
     576             :          * Thus, amend the available space.
     577             :          *
     578             :          * Note, the calculations below are similar to what we have in
     579             :          * 'do_budget_space()', so refer there for comments.
     580             :          */
     581           1 :         if (c->bi.min_idx_lebs > c->lst.idx_lebs)
     582           0 :                 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs;
     583             :         else
     584             :                 rsvd_idx_lebs = 0;
     585           2 :         lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
     586           1 :                c->lst.taken_empty_lebs;
     587           1 :         lebs -= rsvd_idx_lebs;
     588           1 :         available += lebs * (c->dark_wm - c->leb_overhead);
     589             : 
     590           1 :         if (available > outstanding)
     591           2 :                 free = ubifs_reported_space(c, available - outstanding);
     592             :         else
     593             :                 free = 0;
     594           1 :         return free;
     595             : }

Generated by: LCOV version 1.13