LCOV - code coverage report
Current view: top level - libubifs - gc.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 189 340 55.6 %
Date: 2024-06-05 20:10:43 Functions: 10 13 76.9 %
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 garbage collection. The procedure for garbage collection
      13             :  * is different depending on whether a LEB as an index LEB (contains index
      14             :  * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
      15             :  * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
      16             :  * nodes to the journal, at which point the garbage-collected LEB is free to be
      17             :  * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
      18             :  * dirty in the TNC, and after the next commit, the garbage-collected LEB is
      19             :  * to be reused. Garbage collection will cause the number of dirty index nodes
      20             :  * to grow, however sufficient space is reserved for the index to ensure the
      21             :  * commit will never run out of space.
      22             :  *
      23             :  * Notes about dead watermark. At current UBIFS implementation we assume that
      24             :  * LEBs which have less than @c->dead_wm bytes of free + dirty space are full
      25             :  * and not worth garbage-collecting. The dead watermark is one min. I/O unit
      26             :  * size, or min. UBIFS node size, depending on what is greater. Indeed, UBIFS
      27             :  * Garbage Collector has to synchronize the GC head's write buffer before
      28             :  * returning, so this is about wasting one min. I/O unit. However, UBIFS GC can
      29             :  * actually reclaim even very small pieces of dirty space by garbage collecting
      30             :  * enough dirty LEBs, but we do not bother doing this at this implementation.
      31             :  *
      32             :  * Notes about dark watermark. The results of GC work depends on how big are
      33             :  * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
      34             :  * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
      35             :  * have to waste large pieces of free space at the end of LEB B, because nodes
      36             :  * from LEB A would not fit. And the worst situation is when all nodes are of
      37             :  * maximum size. So dark watermark is the amount of free + dirty space in LEB
      38             :  * which are guaranteed to be reclaimable. If LEB has less space, the GC might
      39             :  * be unable to reclaim it. So, LEBs with free + dirty greater than dark
      40             :  * watermark are "good" LEBs from GC's point of view. The other LEBs are not so
      41             :  * good, and GC takes extra care when moving them.
      42             :  */
      43             : 
      44             : #include "linux_err.h"
      45             : #include "bitops.h"
      46             : #include "kmem.h"
      47             : #include "ubifs.h"
      48             : #include "defs.h"
      49             : #include "debug.h"
      50             : #include "key.h"
      51             : #include "misc.h"
      52             : 
      53             : /*
      54             :  * GC may need to move more than one LEB to make progress. The below constants
      55             :  * define "soft" and "hard" limits on the number of LEBs the garbage collector
      56             :  * may move.
      57             :  */
      58             : #define SOFT_LEBS_LIMIT 4
      59             : #define HARD_LEBS_LIMIT 32
      60             : 
      61             : /**
      62             :  * switch_gc_head - switch the garbage collection journal head.
      63             :  * @c: UBIFS file-system description object
      64             :  *
      65             :  * This function switch the GC head to the next LEB which is reserved in
      66             :  * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
      67             :  * and other negative error code in case of failures.
      68             :  */
      69           0 : static int switch_gc_head(struct ubifs_info *c)
      70             : {
      71           0 :         int err, gc_lnum = c->gc_lnum;
      72           0 :         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
      73             : 
      74           0 :         ubifs_assert(c, gc_lnum != -1);
      75           0 :         dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
      76             :                wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
      77             :                c->leb_size - wbuf->offs - wbuf->used);
      78             : 
      79           0 :         err = ubifs_wbuf_sync_nolock(wbuf);
      80           0 :         if (err)
      81             :                 return err;
      82             : 
      83             :         /*
      84             :          * The GC write-buffer was synchronized, we may safely unmap
      85             :          * 'c->gc_lnum'.
      86             :          */
      87           0 :         err = ubifs_leb_unmap(c, gc_lnum);
      88           0 :         if (err)
      89             :                 return err;
      90             : 
      91           0 :         err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
      92           0 :         if (err)
      93             :                 return err;
      94             : 
      95           0 :         c->gc_lnum = -1;
      96           0 :         err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0);
      97           0 :         return err;
      98             : }
      99             : 
     100             : /**
     101             :  * data_nodes_cmp - compare 2 data nodes.
     102             :  * @priv: UBIFS file-system description object
     103             :  * @a: first data node
     104             :  * @b: second data node
     105             :  *
     106             :  * This function compares data nodes @a and @b. Returns %1 if @a has greater
     107             :  * inode or block number, and %-1 otherwise.
     108             :  */
     109           3 : static int data_nodes_cmp(void *priv, const struct list_head *a,
     110             :                           const struct list_head *b)
     111             : {
     112             :         ino_t inuma, inumb;
     113           3 :         struct ubifs_info *c = priv;
     114             :         struct ubifs_scan_node *sa, *sb;
     115             : 
     116             :         cond_resched();
     117           3 :         if (a == b)
     118             :                 return 0;
     119             : 
     120           3 :         sa = list_entry(a, struct ubifs_scan_node, list);
     121           3 :         sb = list_entry(b, struct ubifs_scan_node, list);
     122             : 
     123           6 :         ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DATA_KEY);
     124           6 :         ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DATA_KEY);
     125           3 :         ubifs_assert(c, sa->type == UBIFS_DATA_NODE);
     126           3 :         ubifs_assert(c, sb->type == UBIFS_DATA_NODE);
     127             : 
     128           6 :         inuma = key_inum(c, &sa->key);
     129           6 :         inumb = key_inum(c, &sb->key);
     130             : 
     131           3 :         if (inuma == inumb) {
     132           0 :                 unsigned int blka = key_block(c, &sa->key);
     133           0 :                 unsigned int blkb = key_block(c, &sb->key);
     134             : 
     135           0 :                 if (blka <= blkb)
     136             :                         return -1;
     137           3 :         } else if (inuma <= inumb)
     138             :                 return -1;
     139             : 
     140             :         return 1;
     141             : }
     142             : 
     143             : /*
     144             :  * nondata_nodes_cmp - compare 2 non-data nodes.
     145             :  * @priv: UBIFS file-system description object
     146             :  * @a: first node
     147             :  * @a: second node
     148             :  *
     149             :  * This function compares nodes @a and @b. It makes sure that inode nodes go
     150             :  * first and sorted by length in descending order. Directory entry nodes go
     151             :  * after inode nodes and are sorted in ascending hash valuer order.
     152             :  */
     153       29637 : static int nondata_nodes_cmp(void *priv, const struct list_head *a,
     154             :                              const struct list_head *b)
     155             : {
     156             :         ino_t inuma, inumb;
     157       29637 :         struct ubifs_info *c = priv;
     158             :         struct ubifs_scan_node *sa, *sb;
     159             : 
     160             :         cond_resched();
     161       29637 :         if (a == b)
     162             :                 return 0;
     163             : 
     164       29637 :         sa = list_entry(a, struct ubifs_scan_node, list);
     165       29637 :         sb = list_entry(b, struct ubifs_scan_node, list);
     166             : 
     167       88911 :         ubifs_assert(c, key_type(c, &sa->key) != UBIFS_DATA_KEY &&
     168             :                      key_type(c, &sb->key) != UBIFS_DATA_KEY);
     169       29637 :         ubifs_assert(c, sa->type != UBIFS_DATA_NODE &&
     170             :                      sb->type != UBIFS_DATA_NODE);
     171             : 
     172             :         /* Inodes go before directory entries */
     173       29637 :         if (sa->type == UBIFS_INO_NODE) {
     174       10599 :                 if (sb->type == UBIFS_INO_NODE)
     175        8800 :                         return sb->len - sa->len;
     176             :                 return -1;
     177             :         }
     178       19038 :         if (sb->type == UBIFS_INO_NODE)
     179             :                 return 1;
     180             : 
     181       30194 :         ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DENT_KEY ||
     182             :                      key_type(c, &sa->key) == UBIFS_XENT_KEY);
     183       30194 :         ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DENT_KEY ||
     184             :                      key_type(c, &sb->key) == UBIFS_XENT_KEY);
     185       15097 :         ubifs_assert(c, sa->type == UBIFS_DENT_NODE ||
     186             :                      sa->type == UBIFS_XENT_NODE);
     187       15097 :         ubifs_assert(c, sb->type == UBIFS_DENT_NODE ||
     188             :                      sb->type == UBIFS_XENT_NODE);
     189             : 
     190       30194 :         inuma = key_inum(c, &sa->key);
     191       30194 :         inumb = key_inum(c, &sb->key);
     192             : 
     193       15097 :         if (inuma == inumb) {
     194          60 :                 uint32_t hasha = key_hash(c, &sa->key);
     195          60 :                 uint32_t hashb = key_hash(c, &sb->key);
     196             : 
     197          30 :                 if (hasha <= hashb)
     198             :                         return -1;
     199       15067 :         } else if (inuma <= inumb)
     200             :                 return -1;
     201             : 
     202             :         return 1;
     203             : }
     204             : 
     205             : /**
     206             :  * sort_nodes - sort nodes for GC.
     207             :  * @c: UBIFS file-system description object
     208             :  * @sleb: describes nodes to sort and contains the result on exit
     209             :  * @nondata: contains non-data nodes on exit
     210             :  * @min: minimum node size is returned here
     211             :  *
     212             :  * This function sorts the list of inodes to garbage collect. First of all, it
     213             :  * kills obsolete nodes and separates data and non-data nodes to the
     214             :  * @sleb->nodes and @nondata lists correspondingly.
     215             :  *
     216             :  * Data nodes are then sorted in block number order - this is important for
     217             :  * bulk-read; data nodes with lower inode number go before data nodes with
     218             :  * higher inode number, and data nodes with lower block number go before data
     219             :  * nodes with higher block number;
     220             :  *
     221             :  * Non-data nodes are sorted as follows.
     222             :  *   o First go inode nodes - they are sorted in descending length order.
     223             :  *   o Then go directory entry nodes - they are sorted in hash order, which
     224             :  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
     225             :  *     inode number go before direntry nodes with higher parent inode number,
     226             :  *     and direntry nodes with lower name hash values go before direntry nodes
     227             :  *     with higher name hash values.
     228             :  *
     229             :  * This function returns zero in case of success and a negative error code in
     230             :  * case of failure.
     231             :  */
     232          50 : static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
     233             :                       struct list_head *nondata, int *min)
     234             : {
     235             :         int err;
     236             :         struct ubifs_scan_node *snod, *tmp;
     237             : 
     238          50 :         *min = INT_MAX;
     239             : 
     240             :         /* Separate data nodes and non-data nodes */
     241       38326 :         list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
     242       38276 :                 ubifs_assert(c, snod->type == UBIFS_INO_NODE  ||
     243             :                              snod->type == UBIFS_DATA_NODE ||
     244             :                              snod->type == UBIFS_DENT_NODE ||
     245             :                              snod->type == UBIFS_XENT_NODE ||
     246             :                              snod->type == UBIFS_TRUN_NODE ||
     247             :                              snod->type == UBIFS_AUTH_NODE);
     248             : 
     249       76552 :                 if (snod->type != UBIFS_INO_NODE  &&
     250             :                     snod->type != UBIFS_DATA_NODE &&
     251       38276 :                     snod->type != UBIFS_DENT_NODE &&
     252             :                     snod->type != UBIFS_XENT_NODE) {
     253             :                         /* Probably truncation node, zap it */
     254         350 :                         list_del(&snod->list);
     255         175 :                         kfree(snod);
     256         175 :                         continue;
     257             :                 }
     258             : 
     259       76202 :                 ubifs_assert(c, key_type(c, &snod->key) == UBIFS_DATA_KEY ||
     260             :                              key_type(c, &snod->key) == UBIFS_INO_KEY  ||
     261             :                              key_type(c, &snod->key) == UBIFS_DENT_KEY ||
     262             :                              key_type(c, &snod->key) == UBIFS_XENT_KEY);
     263             : 
     264       38101 :                 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
     265             :                                          snod->offs, 0);
     266       38101 :                 if (err < 0)
     267             :                         return err;
     268             : 
     269       38101 :                 if (!err) {
     270             :                         /* The node is obsolete, remove it from the list */
     271       65266 :                         list_del(&snod->list);
     272       32633 :                         kfree(snod);
     273       32633 :                         continue;
     274             :                 }
     275             : 
     276        5468 :                 if (snod->len < *min)
     277          94 :                         *min = snod->len;
     278             : 
     279       10936 :                 if (key_type(c, &snod->key) != UBIFS_DATA_KEY)
     280        5450 :                         list_move_tail(&snod->list, nondata);
     281             :         }
     282             : 
     283             :         /* Sort data and non-data nodes */
     284          50 :         list_sort(c, &sleb->nodes, &data_nodes_cmp);
     285          50 :         list_sort(c, nondata, &nondata_nodes_cmp);
     286             : 
     287          50 :         err = dbg_check_data_nodes_order(c, &sleb->nodes);
     288             :         if (err)
     289             :                 return err;
     290          50 :         err = dbg_check_nondata_nodes_order(c, nondata);
     291             :         if (err)
     292             :                 return err;
     293             :         return 0;
     294             : }
     295             : 
     296             : /**
     297             :  * move_node - move a node.
     298             :  * @c: UBIFS file-system description object
     299             :  * @sleb: describes the LEB to move nodes from
     300             :  * @snod: the mode to move
     301             :  * @wbuf: write-buffer to move node to
     302             :  *
     303             :  * This function moves node @snod to @wbuf, changes TNC correspondingly, and
     304             :  * destroys @snod. Returns zero in case of success and a negative error code in
     305             :  * case of failure.
     306             :  */
     307        5468 : static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
     308             :                      struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf)
     309             : {
     310        5468 :         int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;
     311             : 
     312             :         cond_resched();
     313        5468 :         err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);
     314        5468 :         if (err)
     315             :                 return err;
     316             : 
     317        5468 :         err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
     318             :                                 snod->offs, new_lnum, new_offs,
     319             :                                 snod->len);
     320       10936 :         list_del(&snod->list);
     321        5468 :         kfree(snod);
     322             :         return err;
     323             : }
     324             : 
     325             : /**
     326             :  * move_nodes - move nodes.
     327             :  * @c: UBIFS file-system description object
     328             :  * @sleb: describes the LEB to move nodes from
     329             :  *
     330             :  * This function moves valid nodes from data LEB described by @sleb to the GC
     331             :  * journal head. This function returns zero in case of success, %-EAGAIN if
     332             :  * commit is required, and other negative error codes in case of other
     333             :  * failures.
     334             :  */
     335          50 : static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
     336             : {
     337             :         int err, min;
     338          50 :         LIST_HEAD(nondata);
     339          50 :         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
     340             : 
     341          50 :         if (wbuf->lnum == -1) {
     342             :                 /*
     343             :                  * The GC journal head is not set, because it is the first GC
     344             :                  * invocation since mount.
     345             :                  */
     346           0 :                 err = switch_gc_head(c);
     347           0 :                 if (err)
     348             :                         return err;
     349             :         }
     350             : 
     351          50 :         err = sort_nodes(c, sleb, &nondata, &min);
     352          50 :         if (err)
     353             :                 goto out;
     354             : 
     355             :         /* Write nodes to their new location. Use the first-fit strategy */
     356             :         while (1) {
     357          50 :                 int avail, moved = 0;
     358             :                 struct ubifs_scan_node *snod, *tmp;
     359             : 
     360             :                 /* Move data nodes */
     361          68 :                 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
     362          36 :                         avail = c->leb_size - wbuf->offs - wbuf->used -
     363          18 :                                         ubifs_auth_node_sz(c);
     364          18 :                         if  (snod->len > avail)
     365             :                                 /*
     366             :                                  * Do not skip data nodes in order to optimize
     367             :                                  * bulk-read.
     368             :                                  */
     369             :                                 break;
     370             : 
     371          36 :                         err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,
     372          18 :                                                  snod->node, snod->len);
     373          18 :                         if (err)
     374             :                                 goto out;
     375             : 
     376          18 :                         err = move_node(c, sleb, snod, wbuf);
     377          18 :                         if (err)
     378             :                                 goto out;
     379          18 :                         moved = 1;
     380             :                 }
     381             : 
     382             :                 /* Move non-data nodes */
     383        5500 :                 list_for_each_entry_safe(snod, tmp, &nondata, list) {
     384       10900 :                         avail = c->leb_size - wbuf->offs - wbuf->used -
     385        5450 :                                         ubifs_auth_node_sz(c);
     386        5450 :                         if (avail < min)
     387             :                                 break;
     388             : 
     389        5450 :                         if  (snod->len > avail) {
     390             :                                 /*
     391             :                                  * Keep going only if this is an inode with
     392             :                                  * some data. Otherwise stop and switch the GC
     393             :                                  * head. IOW, we assume that data-less inode
     394             :                                  * nodes and direntry nodes are roughly of the
     395             :                                  * same size.
     396             :                                  */
     397           0 :                                 if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||
     398             :                                     snod->len == UBIFS_INO_NODE_SZ)
     399             :                                         break;
     400           0 :                                 continue;
     401             :                         }
     402             : 
     403       10900 :                         err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,
     404        5450 :                                                  snod->node, snod->len);
     405        5450 :                         if (err)
     406             :                                 goto out;
     407             : 
     408        5450 :                         err = move_node(c, sleb, snod, wbuf);
     409        5450 :                         if (err)
     410             :                                 goto out;
     411             :                         moved = 1;
     412             :                 }
     413             : 
     414          50 :                 if (ubifs_authenticated(c) && moved) {
     415             :                         struct ubifs_auth_node *auth;
     416             : 
     417           0 :                         auth = kmalloc(ubifs_auth_node_sz(c), GFP_NOFS);
     418           0 :                         if (!auth) {
     419             :                                 err = -ENOMEM;
     420             :                                 goto out;
     421             :                         }
     422             : 
     423           0 :                         err = ubifs_prepare_auth_node(c, auth,
     424           0 :                                                 c->jheads[GCHD].log_hash);
     425             :                         if (err) {
     426             :                                 kfree(auth);
     427             :                                 goto out;
     428             :                         }
     429             : 
     430           0 :                         err = ubifs_wbuf_write_nolock(wbuf, auth,
     431             :                                                       ubifs_auth_node_sz(c));
     432           0 :                         if (err) {
     433             :                                 kfree(auth);
     434             :                                 goto out;
     435             :                         }
     436             : 
     437           0 :                         ubifs_add_dirt(c, wbuf->lnum, ubifs_auth_node_sz(c));
     438             :                 }
     439             : 
     440         150 :                 if (list_empty(&sleb->nodes) && list_empty(&nondata))
     441             :                         break;
     442             : 
     443             :                 /*
     444             :                  * Waste the rest of the space in the LEB and switch to the
     445             :                  * next LEB.
     446             :                  */
     447           0 :                 err = switch_gc_head(c);
     448           0 :                 if (err)
     449             :                         goto out;
     450             :         }
     451             : 
     452             :         return 0;
     453             : 
     454           0 : out:
     455           0 :         list_splice_tail(&nondata, &sleb->nodes);
     456             :         return err;
     457             : }
     458             : 
     459             : /**
     460             :  * gc_sync_wbufs - sync write-buffers for GC.
     461             :  * @c: UBIFS file-system description object
     462             :  *
     463             :  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
     464             :  * be in a write-buffer instead. That is, a node could be written to a
     465             :  * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
     466             :  * erased before the write-buffer is sync'd and then there is an unclean
     467             :  * unmount, then an existing node is lost. To avoid this, we sync all
     468             :  * write-buffers.
     469             :  *
     470             :  * This function returns %0 on success or a negative error code on failure.
     471             :  */
     472          51 : static int gc_sync_wbufs(struct ubifs_info *c)
     473             : {
     474             :         int err, i;
     475             : 
     476         204 :         for (i = 0; i < c->jhead_cnt; i++) {
     477         153 :                 if (i == GCHD)
     478          51 :                         continue;
     479         102 :                 err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
     480         102 :                 if (err)
     481             :                         return err;
     482             :         }
     483             :         return 0;
     484             : }
     485             : 
     486             : /**
     487             :  * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
     488             :  * @c: UBIFS file-system description object
     489             :  * @lp: describes the LEB to garbage collect
     490             :  *
     491             :  * This function garbage-collects an LEB and returns one of the @LEB_FREED,
     492             :  * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
     493             :  * required, and other negative error codes in case of failures.
     494             :  */
     495         272 : int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
     496             : {
     497             :         struct ubifs_scan_leb *sleb;
     498             :         struct ubifs_scan_node *snod;
     499         272 :         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
     500         272 :         int err = 0, lnum = lp->lnum;
     501             : 
     502         272 :         ubifs_assert(c, c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
     503             :                      c->need_recovery);
     504         272 :         ubifs_assert(c, c->gc_lnum != lnum);
     505         272 :         ubifs_assert(c, wbuf->lnum != lnum);
     506             : 
     507         272 :         if (lp->free + lp->dirty == c->leb_size) {
     508             :                 /* Special case - a free LEB  */
     509         222 :                 dbg_gc("LEB %d is free, return it", lp->lnum);
     510         222 :                 ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
     511             : 
     512         222 :                 if (lp->free != c->leb_size) {
     513             :                         /*
     514             :                          * Write buffers must be sync'd before unmapping
     515             :                          * freeable LEBs, because one of them may contain data
     516             :                          * which obsoletes something in 'lp->lnum'.
     517             :                          */
     518           1 :                         err = gc_sync_wbufs(c);
     519           1 :                         if (err)
     520             :                                 return err;
     521           1 :                         err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,
     522             :                                                   0, 0, 0, 0);
     523           1 :                         if (err)
     524             :                                 return err;
     525             :                 }
     526         222 :                 err = ubifs_leb_unmap(c, lp->lnum);
     527         222 :                 if (err)
     528             :                         return err;
     529             : 
     530         222 :                 if (c->gc_lnum == -1) {
     531         222 :                         c->gc_lnum = lnum;
     532         222 :                         return LEB_RETAINED;
     533             :                 }
     534             : 
     535             :                 return LEB_FREED;
     536             :         }
     537             : 
     538             :         /*
     539             :          * We scan the entire LEB even though we only really need to scan up to
     540             :          * (c->leb_size - lp->free).
     541             :          */
     542          50 :         sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
     543          50 :         if (IS_ERR(sleb))
     544           0 :                 return PTR_ERR(sleb);
     545             : 
     546         100 :         ubifs_assert(c, !list_empty(&sleb->nodes));
     547          50 :         snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
     548             : 
     549          50 :         if (snod->type == UBIFS_IDX_NODE) {
     550             :                 struct ubifs_gced_idx_leb *idx_gc;
     551             : 
     552           0 :                 dbg_gc("indexing LEB %d (free %d, dirty %d)",
     553             :                        lnum, lp->free, lp->dirty);
     554           0 :                 list_for_each_entry(snod, &sleb->nodes, list) {
     555           0 :                         struct ubifs_idx_node *idx = snod->node;
     556           0 :                         int level = le16_to_cpu(idx->level);
     557             : 
     558           0 :                         ubifs_assert(c, snod->type == UBIFS_IDX_NODE);
     559           0 :                         key_read(c, ubifs_idx_key(c, idx), &snod->key);
     560           0 :                         err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
     561             :                                                    snod->offs);
     562           0 :                         if (err)
     563             :                                 goto out;
     564             :                 }
     565             : 
     566           0 :                 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
     567           0 :                 if (!idx_gc) {
     568             :                         err = -ENOMEM;
     569             :                         goto out;
     570             :                 }
     571             : 
     572           0 :                 idx_gc->lnum = lnum;
     573           0 :                 idx_gc->unmap = 0;
     574           0 :                 list_add(&idx_gc->list, &c->idx_gc);
     575             : 
     576             :                 /*
     577             :                  * Don't release the LEB until after the next commit, because
     578             :                  * it may contain data which is needed for recovery. So
     579             :                  * although we freed this LEB, it will become usable only after
     580             :                  * the commit.
     581             :                  */
     582           0 :                 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
     583             :                                           LPROPS_INDEX, 1);
     584           0 :                 if (err)
     585             :                         goto out;
     586           0 :                 err = LEB_FREED_IDX;
     587             :         } else {
     588          50 :                 dbg_gc("data LEB %d (free %d, dirty %d)",
     589             :                        lnum, lp->free, lp->dirty);
     590             : 
     591          50 :                 err = move_nodes(c, sleb);
     592          50 :                 if (err)
     593             :                         goto out_inc_seq;
     594             : 
     595          50 :                 err = gc_sync_wbufs(c);
     596          50 :                 if (err)
     597             :                         goto out_inc_seq;
     598             : 
     599          50 :                 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
     600          50 :                 if (err)
     601             :                         goto out_inc_seq;
     602             : 
     603             :                 /* Allow for races with TNC */
     604          50 :                 c->gced_lnum = lnum;
     605             :                 smp_wmb();
     606          50 :                 c->gc_seq += 1;
     607             :                 smp_wmb();
     608             : 
     609          50 :                 if (c->gc_lnum == -1) {
     610          50 :                         c->gc_lnum = lnum;
     611          50 :                         err = LEB_RETAINED;
     612             :                 } else {
     613           0 :                         err = ubifs_wbuf_sync_nolock(wbuf);
     614           0 :                         if (err)
     615             :                                 goto out;
     616             : 
     617           0 :                         err = ubifs_leb_unmap(c, lnum);
     618           0 :                         if (err)
     619             :                                 goto out;
     620             : 
     621           0 :                         err = LEB_FREED;
     622             :                 }
     623             :         }
     624             : 
     625          50 : out:
     626          50 :         ubifs_scan_destroy(sleb);
     627          50 :         return err;
     628             : 
     629           0 : out_inc_seq:
     630             :         /* We may have moved at least some nodes so allow for races with TNC */
     631           0 :         c->gced_lnum = lnum;
     632             :         smp_wmb();
     633           0 :         c->gc_seq += 1;
     634             :         smp_wmb();
     635           0 :         goto out;
     636             : }
     637             : 
     638             : /**
     639             :  * ubifs_garbage_collect - UBIFS garbage collector.
     640             :  * @c: UBIFS file-system description object
     641             :  * @anyway: do GC even if there are free LEBs
     642             :  *
     643             :  * This function does out-of-place garbage collection. The return codes are:
     644             :  *   o positive LEB number if the LEB has been freed and may be used;
     645             :  *   o %-EAGAIN if the caller has to run commit;
     646             :  *   o %-ENOSPC if GC failed to make any progress;
     647             :  *   o other negative error codes in case of other errors.
     648             :  *
     649             :  * Garbage collector writes data to the journal when GC'ing data LEBs, and just
     650             :  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
     651             :  * commit may be required. But commit cannot be run from inside GC, because the
     652             :  * caller might be holding the commit lock, so %-EAGAIN is returned instead;
     653             :  * And this error code means that the caller has to run commit, and re-run GC
     654             :  * if there is still no free space.
     655             :  *
     656             :  * There are many reasons why this function may return %-EAGAIN:
     657             :  * o the log is full and there is no space to write an LEB reference for
     658             :  *   @c->gc_lnum;
     659             :  * o the journal is too large and exceeds size limitations;
     660             :  * o GC moved indexing LEBs, but they can be used only after the commit;
     661             :  * o the shrinker fails to find clean znodes to free and requests the commit;
     662             :  * o etc.
     663             :  *
     664             :  * Note, if the file-system is close to be full, this function may return
     665             :  * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
     666             :  * the function. E.g., this happens if the limits on the journal size are too
     667             :  * tough and GC writes too much to the journal before an LEB is freed. This
     668             :  * might also mean that the journal is too large, and the TNC becomes to big,
     669             :  * so that the shrinker is constantly called, finds not clean znodes to free,
     670             :  * and requests commit. Well, this may also happen if the journal is all right,
     671             :  * but another kernel process consumes too much memory. Anyway, infinite
     672             :  * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
     673             :  */
     674           0 : int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
     675             : {
     676           0 :         int i, err, ret, min_space = c->dead_wm;
     677             :         struct ubifs_lprops lp;
     678           0 :         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
     679             : 
     680           0 :         ubifs_assert_cmt_locked(c);
     681           0 :         ubifs_assert(c, !c->ro_media && !c->ro_mount);
     682             : 
     683           0 :         if (ubifs_gc_should_commit(c))
     684             :                 return -EAGAIN;
     685             : 
     686           0 :         mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
     687             : 
     688           0 :         if (c->ro_error) {
     689             :                 ret = -EROFS;
     690             :                 goto out_unlock;
     691             :         }
     692             : 
     693             :         /* We expect the write-buffer to be empty on entry */
     694           0 :         ubifs_assert(c, !wbuf->used);
     695             : 
     696           0 :         for (i = 0; ; i++) {
     697             :                 int space_before, space_after;
     698             : 
     699             :                 /* Maybe continue after find and break before find */
     700           0 :                 lp.lnum = -1;
     701             : 
     702             :                 cond_resched();
     703             : 
     704             :                 /* Give the commit an opportunity to run */
     705           0 :                 if (ubifs_gc_should_commit(c)) {
     706             :                         ret = -EAGAIN;
     707             :                         break;
     708             :                 }
     709             : 
     710           0 :                 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
     711             :                         /*
     712             :                          * We've done enough iterations. Indexing LEBs were
     713             :                          * moved and will be available after the commit.
     714             :                          */
     715           0 :                         dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
     716           0 :                         ubifs_commit_required(c);
     717           0 :                         ret = -EAGAIN;
     718             :                         break;
     719             :                 }
     720             : 
     721           0 :                 if (i > HARD_LEBS_LIMIT) {
     722             :                         /*
     723             :                          * We've moved too many LEBs and have not made
     724             :                          * progress, give up.
     725             :                          */
     726           0 :                         dbg_gc("hard limit, -ENOSPC");
     727             :                         ret = -ENOSPC;
     728             :                         break;
     729             :                 }
     730             : 
     731             :                 /*
     732             :                  * Empty and freeable LEBs can turn up while we waited for
     733             :                  * the wbuf lock, or while we have been running GC. In that
     734             :                  * case, we should just return one of those instead of
     735             :                  * continuing to GC dirty LEBs. Hence we request
     736             :                  * 'ubifs_find_dirty_leb()' to return an empty LEB if it can.
     737             :                  */
     738           0 :                 ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
     739           0 :                 if (ret) {
     740           0 :                         if (ret == -ENOSPC)
     741           0 :                                 dbg_gc("no more dirty LEBs");
     742             :                         break;
     743             :                 }
     744             : 
     745           0 :                 dbg_gc("found LEB %d: free %d, dirty %d, sum %d (min. space %d)",
     746             :                        lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty,
     747             :                        min_space);
     748             : 
     749           0 :                 space_before = c->leb_size - wbuf->offs - wbuf->used;
     750           0 :                 if (wbuf->lnum == -1)
     751           0 :                         space_before = 0;
     752             : 
     753           0 :                 ret = ubifs_garbage_collect_leb(c, &lp);
     754           0 :                 if (ret < 0) {
     755           0 :                         if (ret == -EAGAIN) {
     756             :                                 /*
     757             :                                  * This is not error, so we have to return the
     758             :                                  * LEB to lprops. But if 'ubifs_return_leb()'
     759             :                                  * fails, its failure code is propagated to the
     760             :                                  * caller instead of the original '-EAGAIN'.
     761             :                                  */
     762           0 :                                 err = ubifs_return_leb(c, lp.lnum);
     763           0 :                                 if (err) {
     764           0 :                                         ret = err;
     765             :                                         /*
     766             :                                          * An LEB may always be "taken",
     767             :                                          * so setting ubifs to read-only,
     768             :                                          * and then executing sync wbuf will
     769             :                                          * return -EROFS and enter the "out"
     770             :                                          * error branch.
     771             :                                          */
     772           0 :                                         ubifs_ro_mode(c, ret);
     773             :                                 }
     774             :                                 /*  Maybe double return LEB if goto out */
     775           0 :                                 lp.lnum = -1;
     776           0 :                                 break;
     777             :                         }
     778             :                         goto out;
     779             :                 }
     780             : 
     781           0 :                 if (ret == LEB_FREED) {
     782             :                         /* An LEB has been freed and is ready for use */
     783           0 :                         dbg_gc("LEB %d freed, return", lp.lnum);
     784           0 :                         ret = lp.lnum;
     785           0 :                         break;
     786             :                 }
     787             : 
     788           0 :                 if (ret == LEB_FREED_IDX) {
     789             :                         /*
     790             :                          * This was an indexing LEB and it cannot be
     791             :                          * immediately used. And instead of requesting the
     792             :                          * commit straight away, we try to garbage collect some
     793             :                          * more.
     794             :                          */
     795           0 :                         dbg_gc("indexing LEB %d freed, continue", lp.lnum);
     796           0 :                         continue;
     797             :                 }
     798             : 
     799           0 :                 ubifs_assert(c, ret == LEB_RETAINED);
     800           0 :                 space_after = c->leb_size - wbuf->offs - wbuf->used;
     801           0 :                 dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
     802             :                        space_after - space_before);
     803             : 
     804           0 :                 if (space_after > space_before) {
     805             :                         /* GC makes progress, keep working */
     806           0 :                         min_space >>= 1;
     807           0 :                         if (min_space < c->dead_wm)
     808           0 :                                 min_space = c->dead_wm;
     809           0 :                         continue;
     810             :                 }
     811             : 
     812           0 :                 dbg_gc("did not make progress");
     813             : 
     814             :                 /*
     815             :                  * GC moved an LEB bud have not done any progress. This means
     816             :                  * that the previous GC head LEB contained too few free space
     817             :                  * and the LEB which was GC'ed contained only large nodes which
     818             :                  * did not fit that space.
     819             :                  *
     820             :                  * We can do 2 things:
     821             :                  * 1. pick another LEB in a hope it'll contain a small node
     822             :                  *    which will fit the space we have at the end of current GC
     823             :                  *    head LEB, but there is no guarantee, so we try this out
     824             :                  *    unless we have already been working for too long;
     825             :                  * 2. request an LEB with more dirty space, which will force
     826             :                  *    'ubifs_find_dirty_leb()' to start scanning the lprops
     827             :                  *    table, instead of just picking one from the heap
     828             :                  *    (previously it already picked the dirtiest LEB).
     829             :                  */
     830           0 :                 if (i < SOFT_LEBS_LIMIT) {
     831           0 :                         dbg_gc("try again");
     832           0 :                         continue;
     833             :                 }
     834             : 
     835           0 :                 min_space <<= 1;
     836           0 :                 if (min_space > c->dark_wm)
     837           0 :                         min_space = c->dark_wm;
     838           0 :                 dbg_gc("set min. space to %d", min_space);
     839             :         }
     840             : 
     841           0 :         if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
     842           0 :                 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
     843           0 :                 ubifs_commit_required(c);
     844           0 :                 ret = -EAGAIN;
     845             :         }
     846             : 
     847           0 :         err = ubifs_wbuf_sync_nolock(wbuf);
     848           0 :         if (!err)
     849           0 :                 err = ubifs_leb_unmap(c, c->gc_lnum);
     850           0 :         if (err) {
     851             :                 ret = err;
     852             :                 goto out;
     853             :         }
     854           0 : out_unlock:
     855           0 :         mutex_unlock(&wbuf->io_mutex);
     856           0 :         return ret;
     857             : 
     858           0 : out:
     859           0 :         ubifs_assert(c, ret < 0);
     860           0 :         ubifs_assert(c, ret != -ENOSPC && ret != -EAGAIN);
     861           0 :         ubifs_wbuf_sync_nolock(wbuf);
     862           0 :         ubifs_ro_mode(c, ret);
     863           0 :         mutex_unlock(&wbuf->io_mutex);
     864           0 :         if (lp.lnum != -1)
     865           0 :                 ubifs_return_leb(c, lp.lnum);
     866             :         return ret;
     867             : }
     868             : 
     869             : /**
     870             :  * ubifs_gc_start_commit - garbage collection at start of commit.
     871             :  * @c: UBIFS file-system description object
     872             :  *
     873             :  * If a LEB has only dirty and free space, then we may safely unmap it and make
     874             :  * it free.  Note, we cannot do this with indexing LEBs because dirty space may
     875             :  * correspond index nodes that are required for recovery.  In that case, the
     876             :  * LEB cannot be unmapped until after the next commit.
     877             :  *
     878             :  * This function returns %0 upon success and a negative error code upon failure.
     879             :  */
     880        3427 : int ubifs_gc_start_commit(struct ubifs_info *c)
     881             : {
     882             :         struct ubifs_gced_idx_leb *idx_gc;
     883             :         const struct ubifs_lprops *lp;
     884        3427 :         int err = 0, flags;
     885             : 
     886             :         ubifs_get_lprops(c);
     887             : 
     888             :         /*
     889             :          * Unmap (non-index) freeable LEBs. Note that recovery requires that all
     890             :          * wbufs are sync'd before this, which is done in 'do_commit()'.
     891             :          */
     892             :         while (1) {
     893        5346 :                 lp = ubifs_fast_find_freeable(c);
     894        5346 :                 if (!lp)
     895             :                         break;
     896        1919 :                 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
     897        1919 :                 ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
     898        1919 :                 err = ubifs_leb_unmap(c, lp->lnum);
     899        1919 :                 if (err)
     900             :                         goto out;
     901        1919 :                 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
     902        1919 :                 if (IS_ERR(lp)) {
     903           0 :                         err = PTR_ERR(lp);
     904           0 :                         goto out;
     905             :                 }
     906        1919 :                 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
     907        1919 :                 ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
     908             :         }
     909             : 
     910             :         /* Mark GC'd index LEBs OK to unmap after this commit finishes */
     911        3427 :         list_for_each_entry(idx_gc, &c->idx_gc, list)
     912           0 :                 idx_gc->unmap = 1;
     913             : 
     914             :         /* Record index freeable LEBs for unmapping after commit */
     915             :         while (1) {
     916        3564 :                 lp = ubifs_fast_find_frdi_idx(c);
     917        3564 :                 if (IS_ERR(lp)) {
     918           0 :                         err = PTR_ERR(lp);
     919           0 :                         goto out;
     920             :                 }
     921        3564 :                 if (!lp)
     922             :                         break;
     923         137 :                 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
     924         137 :                 if (!idx_gc) {
     925             :                         err = -ENOMEM;
     926             :                         goto out;
     927             :                 }
     928         137 :                 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
     929         137 :                 ubifs_assert(c, lp->flags & LPROPS_INDEX);
     930             :                 /* Don't release the LEB until after the next commit */
     931         137 :                 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
     932         137 :                 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
     933         137 :                 if (IS_ERR(lp)) {
     934           0 :                         err = PTR_ERR(lp);
     935             :                         kfree(idx_gc);
     936             :                         goto out;
     937             :                 }
     938         137 :                 ubifs_assert(c, lp->flags & LPROPS_TAKEN);
     939         137 :                 ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
     940         137 :                 idx_gc->lnum = lp->lnum;
     941         137 :                 idx_gc->unmap = 1;
     942         137 :                 list_add(&idx_gc->list, &c->idx_gc);
     943             :         }
     944        3427 : out:
     945        3427 :         ubifs_release_lprops(c);
     946        3427 :         return err;
     947             : }
     948             : 
     949             : /**
     950             :  * ubifs_gc_end_commit - garbage collection at end of commit.
     951             :  * @c: UBIFS file-system description object
     952             :  *
     953             :  * This function completes out-of-place garbage collection of index LEBs.
     954             :  */
     955        3398 : int ubifs_gc_end_commit(struct ubifs_info *c)
     956             : {
     957             :         struct ubifs_gced_idx_leb *idx_gc, *tmp;
     958             :         struct ubifs_wbuf *wbuf;
     959        3398 :         int err = 0;
     960             : 
     961        3398 :         wbuf = &c->jheads[GCHD].wbuf;
     962        3398 :         mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
     963        3535 :         list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
     964         137 :                 if (idx_gc->unmap) {
     965         137 :                         dbg_gc("LEB %d", idx_gc->lnum);
     966         137 :                         err = ubifs_leb_unmap(c, idx_gc->lnum);
     967         137 :                         if (err)
     968             :                                 goto out;
     969         137 :                         err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
     970             :                                           LPROPS_NC, 0, LPROPS_TAKEN, -1);
     971         137 :                         if (err)
     972             :                                 goto out;
     973         274 :                         list_del(&idx_gc->list);
     974             :                         kfree(idx_gc);
     975             :                 }
     976        3398 : out:
     977        3398 :         mutex_unlock(&wbuf->io_mutex);
     978        3398 :         return err;
     979             : }
     980             : 
     981             : /**
     982             :  * ubifs_destroy_idx_gc - destroy idx_gc list.
     983             :  * @c: UBIFS file-system description object
     984             :  *
     985             :  * This function destroys the @c->idx_gc list. It is called when unmounting
     986             :  * so locks are not needed. Returns zero in case of success and a negative
     987             :  * error code in case of failure.
     988             :  */
     989        1951 : void ubifs_destroy_idx_gc(struct ubifs_info *c)
     990             : {
     991        5853 :         while (!list_empty(&c->idx_gc)) {
     992             :                 struct ubifs_gced_idx_leb *idx_gc;
     993             : 
     994           0 :                 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
     995             :                                     list);
     996           0 :                 c->idx_gc_cnt -= 1;
     997           0 :                 list_del(&idx_gc->list);
     998             :                 kfree(idx_gc);
     999             :         }
    1000        1951 : }
    1001             : 
    1002             : /**
    1003             :  * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
    1004             :  * @c: UBIFS file-system description object
    1005             :  *
    1006             :  * Called during start commit so locks are not needed.
    1007             :  */
    1008           0 : int ubifs_get_idx_gc_leb(struct ubifs_info *c)
    1009             : {
    1010             :         struct ubifs_gced_idx_leb *idx_gc;
    1011             :         int lnum;
    1012             : 
    1013           0 :         if (list_empty(&c->idx_gc))
    1014             :                 return -ENOSPC;
    1015           0 :         idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
    1016           0 :         lnum = idx_gc->lnum;
    1017             :         /* c->idx_gc_cnt is updated by the caller when lprops are updated */
    1018           0 :         list_del(&idx_gc->list);
    1019           0 :         kfree(idx_gc);
    1020           0 :         return lnum;
    1021             : }

Generated by: LCOV version 1.13