LCOV - code coverage report
Current view: top level - fsck.ubifs - rebuild_fs.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 612 655 93.4 %
Date: 2024-06-05 20:10:43 Functions: 30 30 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // SPDX-License-Identifier: GPL-2.0
       2             : /*
       3             :  * Copyright (C) 2024, Huawei Technologies Co, Ltd.
       4             :  *
       5             :  * Authors: Zhihao Cheng <chengzhihao1@huawei.com>
       6             :  */
       7             : 
       8             : #include <stdio.h>
       9             : #include <stdlib.h>
      10             : #include <getopt.h>
      11             : #include <sys/stat.h>
      12             : 
      13             : #include "linux_err.h"
      14             : #include "bitops.h"
      15             : #include "kmem.h"
      16             : #include "ubifs.h"
      17             : #include "defs.h"
      18             : #include "debug.h"
      19             : #include "key.h"
      20             : #include "misc.h"
      21             : #include "fsck.ubifs.h"
      22             : 
      23             : /**
      24             :  * scanned_info - nodes and files information from scanning.
      25             :  * @valid_inos: the tree of scanned inode nodes with 'nlink > 0'
      26             :  * @del_inos: the tree of scanned inode nodes with 'nlink = 0'
      27             :  * @valid_dents: the tree of scanned dentry nodes with 'inum > 0'
      28             :  * @del_dents: the tree of scanned dentry nodes with 'inum = 0'
      29             :  */
      30             : struct scanned_info {
      31             :         struct rb_root valid_inos;
      32             :         struct rb_root del_inos;
      33             :         struct rb_root valid_dents;
      34             :         struct rb_root del_dents;
      35             : };
      36             : 
      37             : /**
      38             :  * struct idx_entry - index entry.
      39             :  * @list: link in the list index entries for building index tree
      40             :  * @key: key
      41             :  * @name: directory entry name used for sorting colliding keys by name
      42             :  * @lnum: LEB number
      43             :  * @offs: offset
      44             :  * @len: length
      45             :  *
      46             :  * The index is recorded as a linked list which is sorted and used to create
      47             :  * the bottom level of the on-flash index tree. The remaining levels of the
      48             :  * index tree are each built from the level below.
      49             :  */
      50             : struct idx_entry {
      51             :         struct list_head list;
      52             :         union ubifs_key key;
      53             :         char *name;
      54             :         int name_len;
      55             :         int lnum;
      56             :         int offs;
      57             :         int len;
      58             : };
      59             : 
      60         425 : static int init_rebuild_info(struct ubifs_info *c)
      61             : {
      62             :         int err;
      63             : 
      64         425 :         c->sbuf = vmalloc(c->leb_size);
      65         425 :         if (!c->sbuf) {
      66           0 :                 log_err(c, errno, "can not allocate sbuf");
      67           0 :                 return -ENOMEM;
      68             :         }
      69         850 :         FSCK(c)->rebuild = kzalloc(sizeof(struct ubifs_rebuild_info),
      70             :                                    GFP_KERNEL);
      71         425 :         if (!FSCK(c)->rebuild) {
      72           0 :                 err = -ENOMEM;
      73           0 :                 log_err(c, errno, "can not allocate rebuild info");
      74           0 :                 goto free_sbuf;
      75             :         }
      76         425 :         FSCK(c)->scanned_files = RB_ROOT;
      77         850 :         FSCK(c)->used_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs),
      78             :                                      sizeof(unsigned long), GFP_KERNEL);
      79         425 :         if (!FSCK(c)->used_lebs) {
      80           0 :                 err = -ENOMEM;
      81           0 :                 log_err(c, errno, "can not allocate bitmap of used lebs");
      82           0 :                 goto free_rebuild;
      83             :         }
      84         850 :         FSCK(c)->lpts = kzalloc(sizeof(struct ubifs_lprops) * c->main_lebs,
      85             :                                 GFP_KERNEL);
      86         425 :         if (!FSCK(c)->lpts) {
      87           0 :                 err = -ENOMEM;
      88           0 :                 log_err(c, errno, "can not allocate lpts");
      89           0 :                 goto free_used_lebs;
      90             :         }
      91         425 :         FSCK(c)->rebuild->write_buf = vmalloc(c->leb_size);
      92         425 :         if (!FSCK(c)->rebuild->write_buf) {
      93           0 :                 err = -ENOMEM;
      94             :                 goto free_lpts;
      95             :         }
      96         425 :         FSCK(c)->rebuild->head_lnum = -1;
      97             : 
      98         425 :         return 0;
      99             : 
     100           0 : free_lpts:
     101           0 :         kfree(FSCK(c)->lpts);
     102           0 : free_used_lebs:
     103           0 :         kfree(FSCK(c)->used_lebs);
     104           0 : free_rebuild:
     105           0 :         kfree(FSCK(c)->rebuild);
     106           0 : free_sbuf:
     107           0 :         vfree(c->sbuf);
     108           0 :         return err;
     109             : }
     110             : 
     111         425 : static void destroy_rebuild_info(struct ubifs_info *c)
     112             : {
     113         425 :         vfree(FSCK(c)->rebuild->write_buf);
     114         850 :         kfree(FSCK(c)->lpts);
     115         850 :         kfree(FSCK(c)->used_lebs);
     116         850 :         kfree(FSCK(c)->rebuild);
     117         425 :         vfree(c->sbuf);
     118         425 : }
     119             : 
     120             : /**
     121             :  * insert_or_update_ino_node - insert or update inode node.
     122             :  * @c: UBIFS file-system description object
     123             :  * @new_ino: new inode node
     124             :  * @tree: a tree to record valid/deleted inode node info
     125             :  *
     126             :  * This function inserts @new_ino into the @tree, or updates inode node
     127             :  * if it already exists in the tree. Returns zero in case of success, a
     128             :  * negative error code in case of failure.
     129             :  */
     130    36934474 : static int insert_or_update_ino_node(struct ubifs_info *c,
     131             :                                      struct scanned_ino_node *new_ino,
     132             :                                      struct rb_root *tree)
     133             : {
     134             :         int cmp;
     135    36934474 :         struct scanned_ino_node *ino_node, *old_ino_node = NULL;
     136    36934474 :         struct rb_node **p, *parent = NULL;
     137             : 
     138    36934474 :         p = &tree->rb_node;
     139   625690457 :         while (*p) {
     140   609537641 :                 parent = *p;
     141   609537641 :                 ino_node = rb_entry(parent, struct scanned_ino_node, rb);
     142   609537641 :                 cmp = keys_cmp(c, &new_ino->key, &ino_node->key);
     143             :                 if (cmp < 0) {
     144   243264215 :                         p = &(*p)->rb_left;
     145   366273426 :                 } else if (cmp > 0) {
     146   345491768 :                         p = &(*p)->rb_right;
     147             :                 } else {
     148             :                         old_ino_node = ino_node;
     149             :                         break;
     150             :                 }
     151             :         }
     152    36934474 :         if (old_ino_node) {
     153    20781658 :                 if (old_ino_node->header.sqnum < new_ino->header.sqnum) {
     154     9423507 :                         size_t len = offsetof(struct scanned_ino_node, rb);
     155             : 
     156     9423507 :                         memcpy(old_ino_node, new_ino, len);
     157             :                 }
     158             :                 return 0;
     159             :         }
     160             : 
     161    16152816 :         ino_node = kmalloc(sizeof(struct scanned_ino_node), GFP_KERNEL);
     162    16152816 :         if (!ino_node)
     163             :                 return -ENOMEM;
     164             : 
     165    16152816 :         *ino_node = *new_ino;
     166    32305632 :         rb_link_node(&ino_node->rb, parent, p);
     167    16152816 :         rb_insert_color(&ino_node->rb, tree);
     168             : 
     169             :         return 0;
     170             : }
     171             : 
     172             : static int namecmp(const char *a, int la, const char *b, int lb)
     173             : {
     174     3898462 :         int cmp, len = min(la, lb);
     175             : 
     176     3898462 :         cmp = memcmp(a, b, len);
     177     3898462 :         if (cmp)
     178             :                 return cmp;
     179             : 
     180     3898462 :         return la - lb;
     181             : }
     182             : 
     183             : /**
     184             :  * insert_or_update_dent_node - insert or update dentry node.
     185             :  * @c: UBIFS file-system description object
     186             :  * @new_dent: new dentry node
     187             :  * @tree: a tree to record valid/deleted dentry node info
     188             :  *
     189             :  * This function inserts @new_dent into the @tree, or updates dent node
     190             :  * if it already exists in the tree. Returns zero in case of success, a
     191             :  * negative error code in case of failure.
     192             :  */
     193    21288069 : static int insert_or_update_dent_node(struct ubifs_info *c,
     194             :                                       struct scanned_dent_node *new_dent,
     195             :                                       struct rb_root *tree)
     196             : {
     197             :         int cmp;
     198    21288069 :         struct scanned_dent_node *dent_node, *old_dent_node = NULL;
     199    21288069 :         struct rb_node **p, *parent = NULL;
     200             : 
     201    21288069 :         p = &tree->rb_node;
     202   362322783 :         while (*p) {
     203   343196362 :                 parent = *p;
     204   343196362 :                 dent_node = rb_entry(parent, struct scanned_dent_node, rb);
     205   367387200 :                 cmp = keys_cmp(c, &new_dent->key, &dent_node->key);
     206             :                 if (cmp < 0) {
     207   152618247 :                         p = &(*p)->rb_left;
     208   190578115 :                 } else if (cmp > 0) {
     209   188416467 :                         p = &(*p)->rb_right;
     210             :                 } else {
     211     6484944 :                         cmp = namecmp(new_dent->name, new_dent->nlen,
     212     4323296 :                                       dent_node->name, dent_node->nlen);
     213     2161648 :                         if (cmp < 0) {
     214           0 :                                 p = &(*p)->rb_left;
     215     2161648 :                         } else if (cmp > 0) {
     216           0 :                                 p = &(*p)->rb_right;
     217             :                         } else {
     218             :                                 old_dent_node = dent_node;
     219             :                                 break;
     220             :                         }
     221             :                 }
     222             :         }
     223    21288069 :         if (old_dent_node) {
     224     2161648 :                 if (old_dent_node->header.sqnum < new_dent->header.sqnum) {
     225     1289045 :                         size_t len = offsetof(struct scanned_dent_node, rb);
     226             : 
     227     1289045 :                         memcpy(old_dent_node, new_dent, len);
     228             :                 }
     229             :                 return 0;
     230             :         }
     231             : 
     232    19126421 :         dent_node = kmalloc(sizeof(struct scanned_dent_node), GFP_KERNEL);
     233    19126421 :         if (!dent_node)
     234             :                 return -ENOMEM;
     235             : 
     236    19126421 :         *dent_node = *new_dent;
     237    38252842 :         rb_link_node(&dent_node->rb, parent, p);
     238    19126421 :         rb_insert_color(&dent_node->rb, tree);
     239             : 
     240             :         return 0;
     241             : }
     242             : 
     243             : /**
     244             :  * process_scanned_node - process scanned node.
     245             :  * @c: UBIFS file-system description object
     246             :  * @lnum: logical eraseblock number
     247             :  * @snod: scanned node
     248             :  * @si: records nodes and files information during scanning
     249             :  *
     250             :  * This function parses, checks and records scanned node information.
     251             :  * Returns zero in case of success, 1% if the scanned LEB doesn't hold file
     252             :  * data and should be ignored(eg. index LEB), a negative error code in case
     253             :  * of failure.
     254             :  */
     255   243980725 : static int process_scanned_node(struct ubifs_info *c, int lnum,
     256             :                                 struct ubifs_scan_node *snod,
     257             :                                 struct scanned_info *si)
     258             : {
     259             :         ino_t inum;
     260   243980725 :         int offs = snod->offs;
     261   243980725 :         void *node = snod->node;
     262   243980725 :         union ubifs_key *key = &snod->key;
     263             :         struct rb_root *tree;
     264             :         struct scanned_node *sn;
     265             :         struct scanned_ino_node ino_node;
     266             :         struct scanned_dent_node dent_node;
     267             :         struct scanned_data_node data_node;
     268             :         struct scanned_trun_node trun_node;
     269             : 
     270   243980725 :         switch (snod->type) {
     271    37683772 :         case UBIFS_INO_NODE:
     272             :         {
     273    37683772 :                 if (!parse_ino_node(c, lnum, offs, node, key, &ino_node))
     274             :                         return 0;
     275             : 
     276    36934474 :                 tree = &si->del_inos;
     277    36934474 :                 if (ino_node.nlink)
     278    35656309 :                         tree = &si->valid_inos;
     279    36934474 :                 return insert_or_update_ino_node(c, &ino_node, tree);
     280             :         }
     281    21288069 :         case UBIFS_DENT_NODE:
     282             :         case UBIFS_XENT_NODE:
     283             :         {
     284    21288069 :                 if (!parse_dent_node(c, lnum, offs, node, key, &dent_node))
     285             :                         return 0;
     286             : 
     287    21288069 :                 tree = &si->del_dents;
     288    21288069 :                 if (dent_node.inum)
     289    19484009 :                         tree = &si->valid_dents;
     290    21288069 :                 return insert_or_update_dent_node(c, &dent_node, tree);
     291             :         }
     292   184458321 :         case UBIFS_DATA_NODE:
     293             :         {
     294   184458321 :                 if (!parse_data_node(c, lnum, offs, node, key, &data_node))
     295             :                         return 0;
     296             : 
     297   368916642 :                 inum = key_inum(c, key);
     298   184458321 :                 sn = (struct scanned_node *)&data_node;
     299   184458321 :                 break;
     300             :         }
     301      327663 :         case UBIFS_TRUN_NODE:
     302             :         {
     303      327663 :                 if (!parse_trun_node(c, lnum, offs, node, key, &trun_node))
     304             :                         return 0;
     305             : 
     306      327663 :                 inum = le32_to_cpu(((struct ubifs_trun_node *)node)->inum);
     307      327663 :                 sn = (struct scanned_node *)&trun_node;
     308      327663 :                 break;
     309             :         }
     310      222900 :         default:
     311      222900 :                 dbg_fsck("skip node type %d, at %d:%d, in %s",
     312             :                          snod->type, lnum, offs, c->dev_name);
     313             :                 return 1;
     314             :         }
     315             : 
     316   184785984 :         tree = &FSCK(c)->scanned_files;
     317   369571968 :         return insert_or_update_file(c, tree, sn, key_type(c, key), inum);
     318             : }
     319             : 
     320             : /**
     321             :  * destroy_scanned_info - destroy scanned nodes.
     322             :  * @c: UBIFS file-system description object
     323             :  * @si: records nodes and files information during scanning
     324             :  *
     325             :  * Destroy scanned files and all data/dentry nodes attached to file, destroy
     326             :  * valid/deleted inode/dentry info.
     327             :  */
     328         425 : static void destroy_scanned_info(struct ubifs_info *c, struct scanned_info *si)
     329             : {
     330             :         struct scanned_ino_node *ino_node;
     331             :         struct scanned_dent_node *dent_node;
     332             :         struct rb_node *this;
     333             : 
     334         425 :         destroy_file_tree(c, &FSCK(c)->scanned_files);
     335             : 
     336         425 :         this = rb_first(&si->valid_inos);
     337        1264 :         while (this) {
     338         414 :                 ino_node = rb_entry(this, struct scanned_ino_node, rb);
     339         414 :                 this = rb_next(this);
     340             : 
     341         414 :                 rb_erase(&ino_node->rb, &si->valid_inos);
     342             :                 kfree(ino_node);
     343             :         }
     344             : 
     345         425 :         this = rb_first(&si->del_inos);
     346         957 :         while (this) {
     347         107 :                 ino_node = rb_entry(this, struct scanned_ino_node, rb);
     348         107 :                 this = rb_next(this);
     349             : 
     350         107 :                 rb_erase(&ino_node->rb, &si->del_inos);
     351             :                 kfree(ino_node);
     352             :         }
     353             : 
     354         425 :         this = rb_first(&si->valid_dents);
     355        1381 :         while (this) {
     356         531 :                 dent_node = rb_entry(this, struct scanned_dent_node, rb);
     357         531 :                 this = rb_next(this);
     358             : 
     359         531 :                 rb_erase(&dent_node->rb, &si->valid_dents);
     360             :                 kfree(dent_node);
     361             :         }
     362             : 
     363         425 :         this = rb_first(&si->del_dents);
     364         969 :         while (this) {
     365         119 :                 dent_node = rb_entry(this, struct scanned_dent_node, rb);
     366         119 :                 this = rb_next(this);
     367             : 
     368         119 :                 rb_erase(&dent_node->rb, &si->del_dents);
     369             :                 kfree(dent_node);
     370             :         }
     371         425 : }
     372             : 
     373             : /**
     374             :  * scan_nodes - scan node information from flash.
     375             :  * @c: UBIFS file-system description object
     376             :  * @si: records nodes and files information during scanning
     377             :  *
     378             :  * This function scans nodes from flash, all ino/dent nodes are split
     379             :  * into valid tree and deleted tree, all trun/data nodes are collected
     380             :  * into file, the file is inserted into @FSCK(c)->scanned_files.
     381             :  */
     382         425 : static int scan_nodes(struct ubifs_info *c, struct scanned_info *si)
     383             : {
     384         425 :         int lnum, err = 0;
     385             :         struct ubifs_scan_leb *sleb;
     386             :         struct ubifs_scan_node *snod;
     387             : 
     388      714832 :         for (lnum = c->main_first; lnum < c->leb_cnt; ++lnum) {
     389      714408 :                 dbg_fsck("scan nodes at LEB %d, in %s", lnum, c->dev_name);
     390             : 
     391      714408 :                 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1);
     392      714408 :                 if (IS_ERR(sleb)) {
     393        2099 :                         if (PTR_ERR(sleb) != -EUCLEAN)
     394           1 :                                 return PTR_ERR(sleb);
     395             : 
     396        2098 :                         sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, -1);
     397        2098 :                         if (IS_ERR(sleb)) {
     398        2098 :                                 if (PTR_ERR(sleb) != -EUCLEAN)
     399           0 :                                         return PTR_ERR(sleb);
     400             : 
     401             :                                 /* This LEB holds corrupted data, abandon it. */
     402        2098 :                                 continue;
     403             :                         }
     404             :                 }
     405             : 
     406   244470134 :                 list_for_each_entry(snod, &sleb->nodes, list) {
     407   243980725 :                         if (snod->sqnum > c->max_sqnum)
     408     6443344 :                                 c->max_sqnum = snod->sqnum;
     409             : 
     410   243980725 :                         err = process_scanned_node(c, lnum, snod, si);
     411   243980725 :                         if (err < 0) {
     412           0 :                                 log_err(c, 0, "process node failed at LEB %d, err %d",
     413             :                                         lnum, err);
     414           0 :                                 ubifs_scan_destroy(sleb);
     415           0 :                                 goto out;
     416   243980725 :                         } else if (err == 1) {
     417             :                                 err = 0;
     418             :                                 break;
     419             :                         }
     420             :                 }
     421             : 
     422      712309 :                 ubifs_scan_destroy(sleb);
     423             :         }
     424             : 
     425         424 : out:
     426             :         return err;
     427             : }
     428             : 
     429             : static struct scanned_ino_node *
     430     1119870 : lookup_valid_ino_node(struct ubifs_info *c, struct scanned_info *si,
     431             :                       struct scanned_ino_node *target)
     432             : {
     433             :         int cmp;
     434             :         struct scanned_ino_node *ino_node;
     435             :         struct rb_node *p;
     436             : 
     437     1119870 :         p = si->valid_inos.rb_node;
     438    17024788 :         while (p) {
     439    17018327 :                 ino_node = rb_entry(p, struct scanned_ino_node, rb);
     440    17018327 :                 cmp = keys_cmp(c, &target->key, &ino_node->key);
     441             :                 if (cmp < 0) {
     442     7725000 :                         p = p->rb_left;
     443     9293327 :                 } else if (cmp > 0) {
     444     8179918 :                         p = p->rb_right;
     445             :                 } else {
     446     1113409 :                         if (target->header.sqnum > ino_node->header.sqnum)
     447             :                                 return ino_node;
     448             :                         else
     449             :                                 return NULL;
     450             :                 }
     451             :         }
     452             : 
     453             :         return NULL;
     454             : }
     455             : 
     456             : static struct scanned_dent_node *
     457     1801595 : lookup_valid_dent_node(struct ubifs_info *c, struct scanned_info *si,
     458             :                        struct scanned_dent_node *target)
     459             : {
     460             :         int cmp;
     461             :         struct scanned_dent_node *dent_node;
     462             :         struct rb_node *p;
     463             : 
     464     1801595 :         p = si->valid_dents.rb_node;
     465    25699569 :         while (p) {
     466    25634788 :                 dent_node = rb_entry(p, struct scanned_dent_node, rb);
     467    27632767 :                 cmp = keys_cmp(c, &target->key, &dent_node->key);
     468             :                 if (cmp < 0) {
     469    12776255 :                         p = p->rb_left;
     470    12858533 :                 } else if (cmp > 0) {
     471    11121719 :                         p = p->rb_right;
     472             :                 } else {
     473     5210442 :                         cmp = namecmp(target->name, target->nlen,
     474     3473628 :                                       dent_node->name, dent_node->nlen);
     475     1736814 :                         if (cmp < 0) {
     476           0 :                                 p = p->rb_left;
     477     1736814 :                         } else if (cmp > 0) {
     478           0 :                                 p = p->rb_right;
     479             :                         } else {
     480     3473628 :                                 if (target->header.sqnum >
     481     1736814 :                                     dent_node->header.sqnum)
     482             :                                         return dent_node;
     483             :                                 else
     484             :                                         return NULL;
     485             :                         }
     486             :                 }
     487             :         }
     488             : 
     489             :         return NULL;
     490             : }
     491             : 
     492   138742761 : static void update_lpt(struct ubifs_info *c, struct scanned_node *sn,
     493             :                        bool deleted)
     494             : {
     495   138742761 :         int index = sn->lnum - c->main_first;
     496   138742761 :         int pos = sn->offs + ALIGN(sn->len, 8);
     497             : 
     498   277485522 :         set_bit(index, FSCK(c)->used_lebs);
     499   138742761 :         FSCK(c)->lpts[index].end = max_t(int, FSCK(c)->lpts[index].end, pos);
     500             : 
     501   138742761 :         if (deleted)
     502             :                 return;
     503             : 
     504   136700406 :         FSCK(c)->lpts[index].used += ALIGN(sn->len, 8);
     505             : }
     506             : 
     507             : /**
     508             :  * remove_del_nodes - remove deleted nodes from valid node tree.
     509             :  * @c: UBIFS file-system description object
     510             :  * @si: records nodes and files information during scanning
     511             :  *
     512             :  * This function compares sqnum between deleted node and corresponding valid
     513             :  * node, removes valid node from tree if the sqnum of deleted node is bigger.
     514             :  * Deleted ino/dent nodes will be removed from @si->del_inos/@si->del_dents
     515             :  * after this function finished.
     516             :  */
     517         424 : static void remove_del_nodes(struct ubifs_info *c, struct scanned_info *si)
     518             : {
     519             :         struct scanned_ino_node *del_ino_node, *valid_ino_node;
     520             :         struct scanned_dent_node *del_dent_node, *valid_dent_node;
     521             :         struct rb_node *this;
     522             : 
     523         424 :         this = rb_first(&si->del_inos);
     524     1120718 :         while (this) {
     525     1119870 :                 del_ino_node = rb_entry(this, struct scanned_ino_node, rb);
     526     1119870 :                 this = rb_next(this);
     527             : 
     528     1119870 :                 valid_ino_node = lookup_valid_ino_node(c, si, del_ino_node);
     529     1119870 :                 if (valid_ino_node) {
     530      147562 :                         update_lpt(c, &del_ino_node->header, true);
     531      147562 :                         rb_erase(&valid_ino_node->rb, &si->valid_inos);
     532             :                         kfree(valid_ino_node);
     533             :                 }
     534             : 
     535     1119870 :                 rb_erase(&del_ino_node->rb, &si->del_inos);
     536             :                 kfree(del_ino_node);
     537             :         }
     538             : 
     539         424 :         this = rb_first(&si->del_dents);
     540     1802443 :         while (this) {
     541     1801595 :                 del_dent_node = rb_entry(this, struct scanned_dent_node, rb);
     542     1801595 :                 this = rb_next(this);
     543             : 
     544     1801595 :                 valid_dent_node = lookup_valid_dent_node(c, si, del_dent_node);
     545     1801595 :                 if (valid_dent_node) {
     546     1731648 :                         update_lpt(c, &del_dent_node->header, true);
     547     1731648 :                         rb_erase(&valid_dent_node->rb, &si->valid_dents);
     548             :                         kfree(valid_dent_node);
     549             :                 }
     550             : 
     551     1801595 :                 rb_erase(&del_dent_node->rb, &si->del_dents);
     552             :                 kfree(del_dent_node);
     553             :         }
     554         424 : }
     555             : 
     556             : /**
     557             :  * add_valid_nodes_into_file - add valid nodes into file.
     558             :  * @c: UBIFS file-system description object
     559             :  * @si: records nodes and files information during scanning
     560             :  *
     561             :  * This function adds valid nodes into corresponding file, all valid ino/dent
     562             :  * nodes will be removed from @si->valid_inos/@si->valid_dents if the function
     563             :  * is executed successfully.
     564             :  */
     565         424 : static int add_valid_nodes_into_file(struct ubifs_info *c,
     566             :                                      struct scanned_info *si)
     567             : {
     568             :         int err, type;
     569             :         ino_t inum;
     570             :         struct scanned_node *sn;
     571             :         struct scanned_ino_node *ino_node;
     572             :         struct scanned_dent_node *dent_node;
     573             :         struct rb_node *this;
     574         424 :         struct rb_root *tree = &FSCK(c)->scanned_files;
     575             : 
     576         424 :         this = rb_first(&si->valid_inos);
     577    14885711 :         while (this) {
     578    14884863 :                 ino_node = rb_entry(this, struct scanned_ino_node, rb);
     579    14884863 :                 this = rb_next(this);
     580             : 
     581    14884863 :                 sn = (struct scanned_node *)ino_node;
     582    29769726 :                 type = key_type(c, &ino_node->key);
     583    29769726 :                 inum = key_inum(c, &ino_node->key);
     584    14884863 :                 err = insert_or_update_file(c, tree, sn, type, inum);
     585    14884863 :                 if (err)
     586             :                         return err;
     587             : 
     588    14884863 :                 rb_erase(&ino_node->rb, &si->valid_inos);
     589             :                 kfree(ino_node);
     590             :         }
     591             : 
     592         424 :         this = rb_first(&si->valid_dents);
     593    15593376 :         while (this) {
     594    15592528 :                 dent_node = rb_entry(this, struct scanned_dent_node, rb);
     595    15592528 :                 this = rb_next(this);
     596             : 
     597    15592528 :                 sn = (struct scanned_node *)dent_node;
     598    15592528 :                 inum = dent_node->inum;
     599    31185056 :                 type = key_type(c, &dent_node->key);
     600    15592528 :                 err = insert_or_update_file(c, tree, sn, type, inum);
     601    15592528 :                 if (err)
     602             :                         return err;
     603             : 
     604    15592528 :                 rb_erase(&dent_node->rb, &si->valid_dents);
     605             :                 kfree(dent_node);
     606             :         }
     607             : 
     608             :         return 0;
     609             : }
     610             : 
     611             : /**
     612             :  * filter_invalid_files - filter out invalid files.
     613             :  * @c: UBIFS file-system description object
     614             :  *
     615             :  * This function filters out invalid files(eg. inconsistent types between
     616             :  * inode and dentry node, or missing inode/dentry node, or encrypted inode
     617             :  * has no encryption related xattrs, etc.).
     618             :  */
     619         424 : static void filter_invalid_files(struct ubifs_info *c)
     620             : {
     621             :         struct rb_node *node;
     622             :         struct scanned_file *file;
     623         424 :         struct rb_root *tree = &FSCK(c)->scanned_files;
     624         424 :         LIST_HEAD(tmp_list);
     625             : 
     626             :         /* Add all xattr files into a list. */
     627    15086055 :         for (node = rb_first(tree); node; node = rb_next(node)) {
     628    15085631 :                 file = rb_entry(node, struct scanned_file, rb);
     629             : 
     630    15085631 :                 if (file->ino.is_xattr)
     631     4657973 :                         list_add(&file->list, &tmp_list);
     632             :         }
     633             : 
     634             :         /*
     635             :          * Round 1: Traverse xattr files, check whether the xattr file is
     636             :          * valid, move valid xattr file into corresponding host file's subtree.
     637             :          */
     638     4658397 :         while (!list_empty(&tmp_list)) {
     639     4657973 :                 file = list_entry(tmp_list.next, struct scanned_file, list);
     640             : 
     641     9315946 :                 list_del(&file->list);
     642     4657973 :                 rb_erase(&file->rb, tree);
     643     4657973 :                 if (!file_is_valid(c, file, tree, NULL)) {
     644      112115 :                         destroy_file_content(c, file);
     645             :                         kfree(file);
     646             :                 }
     647             :         }
     648             : 
     649             :         /* Round 2: Traverse non-xattr files. */
     650    10428082 :         for (node = rb_first(tree); node; node = rb_next(node)) {
     651    10427658 :                 file = rb_entry(node, struct scanned_file, rb);
     652             : 
     653    10427658 :                 if (!file_is_valid(c, file, tree, NULL))
     654      451261 :                         list_add(&file->list, &tmp_list);
     655             :         }
     656             : 
     657             :         /* Remove invalid files. */
     658      451685 :         while (!list_empty(&tmp_list)) {
     659      451261 :                 file = list_entry(tmp_list.next, struct scanned_file, list);
     660             : 
     661      902522 :                 list_del(&file->list);
     662      451261 :                 destroy_file_content(c, file);
     663      451261 :                 rb_erase(&file->rb, tree);
     664             :                 kfree(file);
     665             :         }
     666         424 : }
     667             : 
     668             : /**
     669             :  * extract_dentry_tree - extract reachable directory entries.
     670             :  * @c: UBIFS file-system description object
     671             :  *
     672             :  * This function iterates all directory entries and remove those
     673             :  * unreachable ones. 'Unreachable' means that a directory entry can
     674             :  * not be searched from '/'.
     675             :  */
     676         424 : static void extract_dentry_tree(struct ubifs_info *c)
     677             : {
     678             :         struct rb_node *node;
     679             :         struct scanned_file *file;
     680         424 :         struct rb_root *tree = &FSCK(c)->scanned_files;
     681         424 :         LIST_HEAD(unreachable);
     682             : 
     683     9976821 :         for (node = rb_first(tree); node; node = rb_next(node)) {
     684     9976397 :                 file = rb_entry(node, struct scanned_file, rb);
     685             : 
     686             :                 /*
     687             :                  * Since all xattr files are already attached to corresponding
     688             :                  * host file, there are only non-xattr files in the file tree.
     689             :                  */
     690     9976397 :                 ubifs_assert(c, !file->ino.is_xattr);
     691     9976397 :                 if (!file_is_reachable(c, file, tree))
     692     1920988 :                         list_add(&file->list, &unreachable);
     693             :         }
     694             : 
     695             :         /* Remove unreachable files. */
     696     1921412 :         while (!list_empty(&unreachable)) {
     697     1920988 :                 file = list_entry(unreachable.next, struct scanned_file, list);
     698             : 
     699     1920988 :                 dbg_fsck("remove unreachable file %lu, in %s",
     700             :                          file->inum, c->dev_name);
     701     3841976 :                 list_del(&file->list);
     702     1920988 :                 destroy_file_content(c, file);
     703     1920988 :                 rb_erase(&file->rb, tree);
     704             :                 kfree(file);
     705             :         }
     706         424 : }
     707             : 
     708           1 : static void init_root_ino(struct ubifs_info *c, struct ubifs_ino_node *ino)
     709             : {
     710             :         __le64 tmp_le64;
     711             : 
     712             :         /* Create default root inode */
     713           2 :         ino_key_init_flash(c, &ino->key, UBIFS_ROOT_INO);
     714           1 :         ino->ch.node_type = UBIFS_INO_NODE;
     715           1 :         ino->creat_sqnum = cpu_to_le64(++c->max_sqnum);
     716           1 :         ino->nlink = cpu_to_le32(2);
     717           1 :         tmp_le64 = cpu_to_le64(time(NULL));
     718           1 :         ino->atime_sec   = tmp_le64;
     719           1 :         ino->ctime_sec   = tmp_le64;
     720           1 :         ino->mtime_sec   = tmp_le64;
     721           1 :         ino->atime_nsec  = 0;
     722           1 :         ino->ctime_nsec  = 0;
     723           1 :         ino->mtime_nsec  = 0;
     724           1 :         ino->mode = cpu_to_le32(S_IFDIR | S_IRUGO | S_IWUSR | S_IXUGO);
     725           1 :         ino->size = cpu_to_le64(UBIFS_INO_NODE_SZ);
     726             :         /* Set compression enabled by default */
     727           1 :         ino->flags = cpu_to_le32(UBIFS_COMPR_FL);
     728           1 : }
     729             : 
     730             : /**
     731             :  * flush_write_buf - flush write buffer.
     732             :  * @c: UBIFS file-system description object
     733             :  *
     734             :  * This function flush write buffer to LEB @FSCK(c)->rebuild->head_lnum, then
     735             :  * set @FSCK(c)->rebuild->head_lnum to '-1'.
     736             :  */
     737       19469 : static int flush_write_buf(struct ubifs_info *c)
     738             : {
     739             :         int len, pad, err;
     740             : 
     741       19469 :         if (!FSCK(c)->rebuild->head_offs)
     742             :                 return 0;
     743             : 
     744       19469 :         len = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size);
     745       19469 :         pad = len - FSCK(c)->rebuild->head_offs;
     746       19469 :         if (pad)
     747       10902 :                 ubifs_pad(c, FSCK(c)->rebuild->write_buf +
     748        5451 :                           FSCK(c)->rebuild->head_offs, pad);
     749             : 
     750       19469 :         err = ubifs_leb_write(c, FSCK(c)->rebuild->head_lnum,
     751       19469 :                               FSCK(c)->rebuild->write_buf, 0, len);
     752       19469 :         if (err)
     753             :                 return err;
     754             : 
     755       19469 :         if (FSCK(c)->rebuild->need_update_lpt) {
     756       19468 :                 int index = FSCK(c)->rebuild->head_lnum - c->main_first;
     757             : 
     758       19468 :                 FSCK(c)->lpts[index].free = c->leb_size - len;
     759       19468 :                 FSCK(c)->lpts[index].dirty = pad;
     760       19468 :                 FSCK(c)->lpts[index].flags = LPROPS_INDEX;
     761             :         }
     762             : 
     763       19469 :         FSCK(c)->rebuild->head_lnum = -1;
     764             : 
     765       19469 :         return 0;
     766             : }
     767             : 
     768             : /**
     769             :  * reserve_space - reserve enough space to write data.
     770             :  * @c: UBIFS file-system description object
     771             :  * @len: the length of written data
     772             :  * @lnum: the write LEB number is returned here
     773             :  * @offs: the write pos in LEB is returned here
     774             :  *
     775             :  * This function finds target position <@lnum, @offs> to write data with
     776             :  * length of @len.
     777             :  */
     778    13782458 : static int reserve_space(struct ubifs_info *c, int len, int *lnum, int *offs)
     779             : {
     780             :         int err, new_lnum;
     781             : 
     782    13782458 :         if (FSCK(c)->rebuild->head_lnum == -1) {
     783         160 : get_new:
     784       19470 :                 new_lnum = get_free_leb(c);
     785       19470 :                 if (new_lnum < 0)
     786             :                         return new_lnum;
     787             : 
     788       19470 :                 err = ubifs_leb_unmap(c, new_lnum);
     789       19470 :                 if (err)
     790             :                         return err;
     791             : 
     792       19469 :                 FSCK(c)->rebuild->head_lnum = new_lnum;
     793       19469 :                 FSCK(c)->rebuild->head_offs = 0;
     794             :         }
     795             : 
     796    13801767 :         if (len > c->leb_size - FSCK(c)->rebuild->head_offs) {
     797       19310 :                 err = flush_write_buf(c);
     798       19310 :                 if (err)
     799             :                         return err;
     800             : 
     801             :                 goto get_new;
     802             :         }
     803             : 
     804    13782457 :         *lnum = FSCK(c)->rebuild->head_lnum;
     805    13782457 :         *offs = FSCK(c)->rebuild->head_offs;
     806    13782457 :         FSCK(c)->rebuild->head_offs += ALIGN(len, 8);
     807             : 
     808    13782457 :         return 0;
     809             : }
     810             : 
     811    13782457 : static void copy_node_data(struct ubifs_info *c, void *node, int offs, int len)
     812             : {
     813    13782457 :         memcpy(FSCK(c)->rebuild->write_buf + offs, node, len);
     814    13782457 :         memset(FSCK(c)->rebuild->write_buf + offs + len, 0xff, ALIGN(len, 8) - len);
     815    13782457 : }
     816             : 
     817             : /**
     818             :  * create_root - create root dir.
     819             :  * @c: UBIFS file-system description object
     820             :  *
     821             :  * This function creates root dir.
     822             :  */
     823           1 : static int create_root(struct ubifs_info *c)
     824             : {
     825             :         int err, lnum, offs;
     826             :         struct ubifs_ino_node *ino;
     827             :         struct scanned_file *file;
     828             : 
     829           2 :         ino = kzalloc(ALIGN(UBIFS_INO_NODE_SZ, c->min_io_size), GFP_KERNEL);
     830           1 :         if (!ino)
     831             :                 return -ENOMEM;
     832             : 
     833           1 :         c->max_sqnum = 0;
     834           1 :         c->highest_inum = UBIFS_FIRST_INO;
     835           1 :         init_root_ino(c, ino);
     836           1 :         err = ubifs_prepare_node_hmac(c, ino, UBIFS_INO_NODE_SZ, -1, 1);
     837           1 :         if (err)
     838             :                 goto out;
     839             : 
     840           1 :         err = reserve_space(c, UBIFS_INO_NODE_SZ, &lnum, &offs);
     841           1 :         if (err)
     842             :                 goto out;
     843             : 
     844           1 :         copy_node_data(c, ino, offs, UBIFS_INO_NODE_SZ);
     845             : 
     846           1 :         err = flush_write_buf(c);
     847           1 :         if (err)
     848             :                 goto out;
     849             : 
     850           1 :         file = kzalloc(sizeof(struct scanned_file), GFP_KERNEL);
     851           1 :         if (!file) {
     852             :                 err = -ENOMEM;
     853             :                 goto out;
     854             :         }
     855             : 
     856           1 :         file->inum = UBIFS_ROOT_INO;
     857           1 :         file->dent_nodes = RB_ROOT;
     858           1 :         file->data_nodes = RB_ROOT;
     859           2 :         INIT_LIST_HEAD(&file->list);
     860             : 
     861           1 :         file->ino.header.exist = true;
     862           1 :         file->ino.header.lnum = lnum;
     863           1 :         file->ino.header.offs = offs;
     864           1 :         file->ino.header.len = UBIFS_INO_NODE_SZ;
     865           1 :         file->ino.header.sqnum = le64_to_cpu(ino->ch.sqnum);
     866           2 :         ino_key_init(c, &file->ino.key, UBIFS_ROOT_INO);
     867           1 :         file->ino.is_xattr = le32_to_cpu(ino->flags) & UBIFS_XATTR_FL;
     868           1 :         file->ino.mode = le32_to_cpu(ino->mode);
     869           1 :         file->calc_nlink = file->ino.nlink = le32_to_cpu(ino->nlink);
     870           1 :         file->calc_xcnt = file->ino.xcnt = le32_to_cpu(ino->xattr_cnt);
     871           1 :         file->calc_xsz = file->ino.xsz = le32_to_cpu(ino->xattr_size);
     872           1 :         file->calc_xnms = file->ino.xnms = le32_to_cpu(ino->xattr_names);
     873           1 :         file->calc_size = file->ino.size = le64_to_cpu(ino->size);
     874             : 
     875           2 :         rb_link_node(&file->rb, NULL, &FSCK(c)->scanned_files.rb_node);
     876           1 :         rb_insert_color(&file->rb, &FSCK(c)->scanned_files);
     877             : 
     878           1 : out:
     879           1 :         kfree(ino);
     880           1 :         return err;
     881             : }
     882             : 
     883        3794 : static const char *get_file_name(struct ubifs_info *c, struct scanned_file *file)
     884             : {
     885             :         static char name[UBIFS_MAX_NLEN + 1];
     886             :         struct rb_node *node;
     887             :         struct scanned_dent_node *dent_node;
     888             : 
     889        3794 :         node = rb_first(&file->dent_nodes);
     890        3794 :         if (!node) {
     891          16 :                 ubifs_assert(c, file->inum == UBIFS_ROOT_INO);
     892             :                 return "/";
     893             :         }
     894             : 
     895        3778 :         if (c->encrypted && !file->ino.is_xattr)
     896             :                 /* Encrypted file name. */
     897             :                 return "<encrypted>";
     898             : 
     899             :         /* Get name from any one dentry. */
     900        3778 :         dent_node = rb_entry(node, struct scanned_dent_node, rb);
     901        3778 :         memcpy(name, dent_node->name, dent_node->nlen);
     902             :         /* @dent->name could be non '\0' terminated. */
     903        3778 :         name[dent_node->nlen] = '\0';
     904        3778 :         return name;
     905             : }
     906             : 
     907   136700406 : static int parse_node_info(struct ubifs_info *c, struct scanned_node *sn,
     908             :                            union ubifs_key *key, char *name, int name_len,
     909             :                            struct list_head *idx_list, int *idx_cnt)
     910             : {
     911             :         struct idx_entry *e;
     912             : 
     913   136863551 :         update_lpt(c, sn, idx_cnt == NULL);
     914             : 
     915   136700406 :         if (idx_cnt == NULL)
     916             :                 /* Skip truncation node. */
     917             :                 return 0;
     918             : 
     919   136700406 :         e = kmalloc(sizeof(struct idx_entry), GFP_KERNEL);
     920   136700406 :         if (!e)
     921             :                 return -ENOMEM;
     922             : 
     923   273400812 :         key_copy(c, key, &e->key);
     924   136700406 :         e->name = name;
     925   136700406 :         e->name_len = name_len;
     926   136700406 :         e->lnum = sn->lnum;
     927   136700406 :         e->offs = sn->offs;
     928   136700406 :         e->len = sn->len;
     929   273400812 :         list_add_tail(&e->list, idx_list);
     930   136700406 :         *idx_cnt = *idx_cnt + 1;
     931             : 
     932   136700406 :         return 0;
     933             : }
     934             : 
     935    13782457 : static int add_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx,
     936             :                         union ubifs_key *key, int child_cnt,
     937             :                         struct idx_entry *e)
     938             : {
     939             :         int err, lnum, offs, len;
     940             : 
     941    13782457 :         len = ubifs_idx_node_sz(c, child_cnt);
     942    13782457 :         ubifs_prepare_node(c, idx, len, 0);
     943             : 
     944    13782457 :         err = reserve_space(c, len, &lnum, &offs);
     945    13782457 :         if (err)
     946             :                 return err;
     947             : 
     948    13782456 :         copy_node_data(c, idx, offs, len);
     949             : 
     950    13782456 :         c->calc_idx_sz += ALIGN(len, 8);
     951             : 
     952             :         /* The last index node written will be the root */
     953    13782456 :         c->zroot.lnum = lnum;
     954    13782456 :         c->zroot.offs = offs;
     955    13782456 :         c->zroot.len = len;
     956             : 
     957    27564912 :         key_copy(c, key, &e->key);
     958    13782456 :         e->lnum = lnum;
     959    13782456 :         e->offs = offs;
     960    13782456 :         e->len = len;
     961             : 
     962    13782456 :         return err;
     963             : }
     964             : 
     965  1719058355 : static int cmp_idx(void *priv, const struct list_head *a,
     966             :                    const struct list_head *b)
     967             : {
     968             :         int cmp;
     969  1719058355 :         struct ubifs_info *c = priv;
     970             :         struct idx_entry *ia, *ib;
     971             : 
     972  1719058355 :         if (a == b)
     973             :                 return 0;
     974             : 
     975  1719058355 :         ia = list_entry(a, struct idx_entry, list);
     976  1719058355 :         ib = list_entry(b, struct idx_entry, list);
     977             : 
     978  1719058355 :         cmp = keys_cmp(c, &ia->key, &ib->key);
     979             :         if (cmp)
     980             :                 return cmp;
     981             : 
     982           0 :         return namecmp(ia->name, ia->name_len, ib->name, ib->name_len);
     983             : }
     984             : 
     985             : /**
     986             :  * build_tnc - construct TNC and write it into flash.
     987             :  * @c: UBIFS file-system description object
     988             :  * @lower_idxs: leaf entries of TNC
     989             :  * @lower_cnt: the count of @lower_idxs
     990             :  *
     991             :  * This function builds TNC according to @lower_idxs and writes all index
     992             :  * nodes into flash.
     993             :  */
     994         159 : static int build_tnc(struct ubifs_info *c, struct list_head *lower_idxs,
     995             :                      int lower_cnt)
     996             : {
     997         159 :         int i, j, err, upper_cnt, child_cnt, idx_sz, level = 0;
     998         159 :         struct idx_entry *pe, *tmp_e, *e = NULL;
     999             :         struct ubifs_idx_node *idx;
    1000             :         struct ubifs_branch *br;
    1001             :         union ubifs_key key;
    1002         159 :         LIST_HEAD(upper_idxs);
    1003             : 
    1004         318 :         idx_sz = ubifs_idx_node_sz(c, c->fanout);
    1005         159 :         idx = kmalloc(idx_sz, GFP_KERNEL);
    1006         159 :         if (!idx)
    1007             :                 return -ENOMEM;
    1008             : 
    1009         159 :         list_sort(c, lower_idxs, cmp_idx);
    1010         159 :         FSCK(c)->rebuild->need_update_lpt = true;
    1011             : 
    1012         159 :         ubifs_assert(c, lower_cnt != 0);
    1013             : 
    1014             :         do {
    1015         859 :                 upper_cnt = lower_cnt / c->fanout;
    1016         859 :                 if (lower_cnt % c->fanout)
    1017         776 :                         upper_cnt += 1;
    1018         859 :                 e = list_first_entry(lower_idxs, struct idx_entry, list);
    1019             : 
    1020    13783315 :                 for (i = 0; i < upper_cnt; i++) {
    1021    13782457 :                         if (i == upper_cnt - 1) {
    1022         858 :                                 child_cnt = lower_cnt % c->fanout;
    1023         858 :                                 if (child_cnt == 0)
    1024          83 :                                         child_cnt = c->fanout;
    1025             :                         } else
    1026    13781599 :                                 child_cnt = c->fanout;
    1027             : 
    1028    27564914 :                         key_copy(c, &e->key, &key);
    1029    13782457 :                         memset(idx, 0, idx_sz);
    1030    13782457 :                         idx->ch.node_type = UBIFS_IDX_NODE;
    1031    13782457 :                         idx->child_cnt = cpu_to_le16(child_cnt);
    1032    13782457 :                         idx->level = cpu_to_le16(level);
    1033   124038828 :                         for (j = 0; j < child_cnt; j++) {
    1034   110256371 :                                 ubifs_assert(c,
    1035             :                                     !list_entry_is_head(e, lower_idxs, list));
    1036   110256371 :                                 br = ubifs_idx_branch(c, idx, j);
    1037   220512742 :                                 key_write_idx(c, &e->key, &br->key);
    1038   110256371 :                                 br->lnum = cpu_to_le32(e->lnum);
    1039   110256371 :                                 br->offs = cpu_to_le32(e->offs);
    1040   110256371 :                                 br->len = cpu_to_le32(e->len);
    1041   110256371 :                                 e = list_next_entry(e, list);
    1042             :                         }
    1043             : 
    1044    13782457 :                         pe = kmalloc(sizeof(struct idx_entry), GFP_KERNEL);
    1045    13782457 :                         if (!pe) {
    1046             :                                 err = -ENOMEM;
    1047             :                                 goto out;
    1048             :                         }
    1049             : 
    1050    13782457 :                         err = add_idx_node(c, idx, &key, child_cnt, pe);
    1051    13782457 :                         if (err) {
    1052             :                                 kfree(pe);
    1053             :                                 goto out;
    1054             :                         }
    1055             : 
    1056    27564912 :                         list_add_tail(&pe->list, &upper_idxs);
    1057             :                 }
    1058             : 
    1059         858 :                 level++;
    1060   110257221 :                 list_for_each_entry_safe(e, tmp_e, lower_idxs, list) {
    1061   220512726 :                         list_del(&e->list);
    1062   110256363 :                         kfree(e);
    1063             :                 }
    1064         858 :                 list_splice_init(&upper_idxs, lower_idxs);
    1065         858 :                 lower_cnt = upper_cnt;
    1066         858 :         } while (lower_cnt > 1);
    1067             : 
    1068             :         /* Set the index head */
    1069         158 :         c->ihead_lnum = FSCK(c)->rebuild->head_lnum;
    1070         158 :         c->ihead_offs = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size);
    1071             : 
    1072             :         /* Flush the last index LEB */
    1073         158 :         err = flush_write_buf(c);
    1074         158 :         FSCK(c)->rebuild->need_update_lpt = false;
    1075             : 
    1076         159 : out:
    1077      184708 :         list_for_each_entry_safe(e, tmp_e, lower_idxs, list) {
    1078      369098 :                 list_del(&e->list);
    1079      184549 :                 kfree(e);
    1080             :         }
    1081         159 :         list_for_each_entry_safe(e, tmp_e, &upper_idxs, list) {
    1082           0 :                 list_del(&e->list);
    1083           0 :                 kfree(e);
    1084             :         }
    1085         159 :         kfree(idx);
    1086         159 :         return err;
    1087             : }
    1088             : 
    1089    10263462 : static int record_file_used_lebs(struct ubifs_info *c,
    1090             :                                  struct scanned_file *file,
    1091             :                                  struct list_head *idx_list, int *idx_cnt)
    1092             : {
    1093             :         int err;
    1094             :         struct rb_node *node;
    1095             :         struct scanned_file *xattr_file;
    1096             :         struct scanned_dent_node *dent_node;
    1097             :         struct scanned_data_node *data_node;
    1098             : 
    1099    10263462 :         dbg_fsck("recovered file(inum:%lu name:%s type:%s), in %s",
    1100             :                  file->inum, get_file_name(c, file),
    1101             :                  file->ino.is_xattr ? "xattr" :
    1102             :                  ubifs_get_type_name(ubifs_get_dent_type(file->ino.mode)),
    1103             :                  c->dev_name);
    1104    10263462 :         c->highest_inum = max_t(ino_t, c->highest_inum, file->inum);
    1105             : 
    1106    10263462 :         err = parse_node_info(c, &file->ino.header, &file->ino.key,
    1107             :                               NULL, 0, idx_list, idx_cnt);
    1108    10263462 :         if (err)
    1109             :                 return err;
    1110             : 
    1111    10263462 :         if (file->trun.header.exist) {
    1112      326290 :                 err = parse_node_info(c, &file->trun.header, NULL, NULL,
    1113             :                                       0, idx_list, NULL);
    1114             :                 if (err)
    1115             :                         return err;
    1116             :         }
    1117             : 
    1118   125833707 :         for (node = rb_first(&file->data_nodes); node; node = rb_next(node)) {
    1119   115570245 :                 data_node = rb_entry(node, struct scanned_data_node, rb);
    1120             : 
    1121   115570245 :                 err = parse_node_info(c, &data_node->header, &data_node->key,
    1122             :                                       NULL, 0, idx_list, idx_cnt);
    1123   115570245 :                 if (err)
    1124             :                         return err;
    1125             :         }
    1126             : 
    1127    21130161 :         for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) {
    1128    10866699 :                 dent_node = rb_entry(node, struct scanned_dent_node, rb);
    1129             : 
    1130    21733398 :                 err = parse_node_info(c, &dent_node->header, &dent_node->key,
    1131    21733398 :                                       dent_node->name, dent_node->nlen,
    1132             :                                       idx_list, idx_cnt);
    1133    10866699 :                 if (err)
    1134             :                         return err;
    1135             :         }
    1136             : 
    1137    13161758 :         for (node = rb_first(&file->xattr_files); node; node = rb_next(node)) {
    1138     2898296 :                 xattr_file = rb_entry(node, struct scanned_file, rb);
    1139             : 
    1140     2898296 :                 err = record_file_used_lebs(c, xattr_file, idx_list, idx_cnt);
    1141     2898296 :                 if (err)
    1142             :                         return err;
    1143             :         }
    1144             : 
    1145             :         return err;
    1146             : }
    1147             : 
    1148             : /**
    1149             :  * traverse_files_and_nodes - traverse all nodes from valid files.
    1150             :  * @c: UBIFS file-system description object
    1151             :  *
    1152             :  * This function traverses all nodes from valid files and does following
    1153             :  * things:
    1154             :  * 1. If there are no scanned files, create default empty filesystem.
    1155             :  * 2. Record all used LEBs which may hold useful nodes, then left unused
    1156             :  *    LEBs could be taken for storing new index tree.
    1157             :  * 3. Re-write data to prevent failed gc scanning in the subsequent mounting
    1158             :  *    process caused by corrupted data.
    1159             :  * 4. Build TNC.
    1160             :  */
    1161         366 : static int traverse_files_and_nodes(struct ubifs_info *c)
    1162             : {
    1163         366 :         int i, err = 0, idx_cnt = 0;
    1164             :         struct rb_node *node;
    1165             :         struct scanned_file *file;
    1166         366 :         struct rb_root *tree = &FSCK(c)->scanned_files;
    1167             :         struct idx_entry *ie, *tmp_ie;
    1168         366 :         LIST_HEAD(idx_list);
    1169             : 
    1170         366 :         if (rb_first(tree) == NULL) {
    1171             :                 /* No scanned files. Create root dir. */
    1172           1 :                 log_out(c, "No files found, create empty filesystem");
    1173           1 :                 err = create_root(c);
    1174           1 :                 if (err)
    1175             :                         return err;
    1176             :         }
    1177             : 
    1178         366 :         log_out(c, "Record used LEBs");
    1179     7365532 :         for (node = rb_first(tree); node; node = rb_next(node)) {
    1180     7365166 :                 file = rb_entry(node, struct scanned_file, rb);
    1181             : 
    1182     7365166 :                 err = record_file_used_lebs(c, file, &idx_list, &idx_cnt);
    1183     7365166 :                 if (err)
    1184             :                         goto out_idx_list;
    1185             :         }
    1186             : 
    1187             :         /* Re-write data. */
    1188         366 :         log_out(c, "Re-write data");
    1189      365085 :         for (i = 0; i < c->main_lebs; ++i) {
    1190             :                 int lnum, len, end;
    1191             : 
    1192      729852 :                 if (!test_bit(i, FSCK(c)->used_lebs))
    1193      204183 :                         continue;
    1194             : 
    1195      160743 :                 lnum = i + c->main_first;
    1196      160743 :                 dbg_fsck("re-write LEB %d, in %s", lnum, c->dev_name);
    1197             : 
    1198      160743 :                 end = FSCK(c)->lpts[i].end;
    1199      160743 :                 len = ALIGN(end, c->min_io_size);
    1200             : 
    1201      160743 :                 err = ubifs_leb_read(c, lnum, c->sbuf, 0, len, 0);
    1202      160743 :                 if (err && err != -EBADMSG)
    1203             :                         goto out_idx_list;
    1204             : 
    1205      160743 :                 if (len > end)
    1206       73328 :                         ubifs_pad(c, c->sbuf + end, len - end);
    1207             : 
    1208      160743 :                 err = ubifs_leb_change(c, lnum, c->sbuf, len);
    1209      160743 :                 if (err)
    1210             :                         goto out_idx_list;
    1211             :         }
    1212             : 
    1213             :         /* Build TNC. */
    1214         159 :         log_out(c, "Build TNC");
    1215         159 :         err = build_tnc(c, &idx_list, idx_cnt);
    1216             : 
    1217         573 : out_idx_list:
    1218    40042316 :         list_for_each_entry_safe(ie, tmp_ie, &idx_list, list) {
    1219    80083900 :                 list_del(&ie->list);
    1220    40041950 :                 kfree(ie);
    1221             :         }
    1222             :         return err;
    1223             : }
    1224             : 
    1225      294904 : static int calculate_lp(struct ubifs_info *c, int index, int *free, int *dirty,
    1226             :                         __unused int *is_idx)
    1227             : {
    1228      746938 :         if (!test_bit(index, FSCK(c)->used_lebs) ||
    1229      157130 :             c->gc_lnum == index + c->main_first) {
    1230      137932 :                 *free = c->leb_size;
    1231      137932 :                 *dirty = 0;
    1232      156972 :         } else if (FSCK(c)->lpts[index].flags & LPROPS_INDEX) {
    1233       19468 :                 *free = FSCK(c)->lpts[index].free;
    1234       19468 :                 *dirty = FSCK(c)->lpts[index].dirty;
    1235             :         } else {
    1236      137504 :                 int len = ALIGN(FSCK(c)->lpts[index].end, c->min_io_size);
    1237             : 
    1238      137504 :                 *free = c->leb_size - len;
    1239      137504 :                 *dirty = len - FSCK(c)->lpts[index].used;
    1240             : 
    1241      137504 :                 if (*dirty == c->leb_size) {
    1242          22 :                         *free = c->leb_size;
    1243          22 :                         *dirty = 0;
    1244             :                 }
    1245             :         }
    1246             : 
    1247      294904 :         return 0;
    1248             : }
    1249             : 
    1250             : /**
    1251             :  * clean_log - clean up log area.
    1252             :  * @c: UBIFS file-system description object
    1253             :  *
    1254             :  * This function cleans up log area, since there is no need to do recovery
    1255             :  * in next mounting.
    1256             :  */
    1257         158 : static int clean_log(struct ubifs_info *c)
    1258             : {
    1259             :         int lnum, err;
    1260             :         struct ubifs_cs_node *cs;
    1261             : 
    1262         854 :         for (lnum = UBIFS_LOG_LNUM; lnum <= c->log_last; lnum++) {
    1263         696 :                 err = ubifs_leb_unmap(c, lnum);
    1264         696 :                 if (err)
    1265             :                         return err;
    1266             :         }
    1267             : 
    1268         316 :         cs = kzalloc(ALIGN(UBIFS_CS_NODE_SZ, c->min_io_size), GFP_KERNEL);
    1269         158 :         if (!cs)
    1270             :                 return -ENOMEM;
    1271             : 
    1272         158 :         cs->ch.node_type = UBIFS_CS_NODE;
    1273         158 :         cs->cmt_no = cpu_to_le64(0);
    1274             : 
    1275         158 :         err = ubifs_write_node(c, cs, UBIFS_CS_NODE_SZ, UBIFS_LOG_LNUM, 0);
    1276         158 :         kfree(cs);
    1277         158 :         if (err)
    1278             :                 return err;
    1279             : 
    1280         158 :         return 0;
    1281             : }
    1282             : 
    1283             : /**
    1284             :  * write_master - write master nodes.
    1285             :  * @c: UBIFS file-system description object
    1286             :  *
    1287             :  * This function updates meta information into master node and writes master
    1288             :  * node into master area.
    1289             :  */
    1290         158 : static int write_master(struct ubifs_info *c)
    1291             : {
    1292             :         int err, lnum;
    1293             :         struct ubifs_mst_node *mst;
    1294             : 
    1295         316 :         mst = kzalloc(c->mst_node_alsz, GFP_KERNEL);
    1296         158 :         if (!mst)
    1297             :                 return -ENOMEM;
    1298             : 
    1299         158 :         mst->ch.node_type = UBIFS_MST_NODE;
    1300         158 :         mst->log_lnum     = cpu_to_le32(UBIFS_LOG_LNUM);
    1301         158 :         mst->highest_inum = cpu_to_le64(c->highest_inum);
    1302         158 :         mst->cmt_no       = 0;
    1303         158 :         mst->root_lnum    = cpu_to_le32(c->zroot.lnum);
    1304         158 :         mst->root_offs    = cpu_to_le32(c->zroot.offs);
    1305         158 :         mst->root_len     = cpu_to_le32(c->zroot.len);
    1306         158 :         mst->gc_lnum      = cpu_to_le32(c->gc_lnum);
    1307         158 :         mst->ihead_lnum   = cpu_to_le32(c->ihead_lnum);
    1308         158 :         mst->ihead_offs   = cpu_to_le32(c->ihead_offs);
    1309         158 :         mst->index_size   = cpu_to_le64(c->calc_idx_sz);
    1310         158 :         mst->lpt_lnum     = cpu_to_le32(c->lpt_lnum);
    1311         158 :         mst->lpt_offs     = cpu_to_le32(c->lpt_offs);
    1312         158 :         mst->nhead_lnum   = cpu_to_le32(c->nhead_lnum);
    1313         158 :         mst->nhead_offs   = cpu_to_le32(c->nhead_offs);
    1314         158 :         mst->ltab_lnum    = cpu_to_le32(c->ltab_lnum);
    1315         158 :         mst->ltab_offs    = cpu_to_le32(c->ltab_offs);
    1316         158 :         mst->lsave_lnum   = cpu_to_le32(c->lsave_lnum);
    1317         158 :         mst->lsave_offs   = cpu_to_le32(c->lsave_offs);
    1318         158 :         mst->lscan_lnum   = cpu_to_le32(c->main_first);
    1319         158 :         mst->empty_lebs   = cpu_to_le32(c->lst.empty_lebs);
    1320         158 :         mst->idx_lebs     = cpu_to_le32(c->lst.idx_lebs);
    1321         158 :         mst->leb_cnt      = cpu_to_le32(c->leb_cnt);
    1322         158 :         mst->total_free   = cpu_to_le64(c->lst.total_free);
    1323         158 :         mst->total_dirty  = cpu_to_le64(c->lst.total_dirty);
    1324         158 :         mst->total_used   = cpu_to_le64(c->lst.total_used);
    1325         158 :         mst->total_dead   = cpu_to_le64(c->lst.total_dead);
    1326         158 :         mst->total_dark   = cpu_to_le64(c->lst.total_dark);
    1327         158 :         mst->flags     |= cpu_to_le32(UBIFS_MST_NO_ORPHS);
    1328             : 
    1329         158 :         lnum = UBIFS_MST_LNUM;
    1330         158 :         err = ubifs_leb_unmap(c, lnum);
    1331         158 :         if (err)
    1332             :                 goto out;
    1333         158 :         err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0,
    1334             :                                     offsetof(struct ubifs_mst_node, hmac));
    1335         158 :         if (err)
    1336             :                 goto out;
    1337         158 :         lnum++;
    1338         158 :         err = ubifs_leb_unmap(c, lnum);
    1339         158 :         if (err)
    1340             :                 goto out;
    1341         158 :         err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0,
    1342             :                                     offsetof(struct ubifs_mst_node, hmac));
    1343             :         if (err)
    1344             :                 goto out;
    1345             : 
    1346         158 : out:
    1347         158 :         kfree(mst);
    1348             : 
    1349         158 :         return err;
    1350             : }
    1351             : 
    1352             : /**
    1353             :  * ubifs_rebuild_filesystem - Rebuild filesystem.
    1354             :  * @c: UBIFS file-system description object
    1355             :  *
    1356             :  * Scanning nodes from UBI volume and rebuild filesystem. Any inconsistent
    1357             :  * problems or corrupted data will be fixed.
    1358             :  */
    1359         425 : int ubifs_rebuild_filesystem(struct ubifs_info *c)
    1360             : {
    1361         425 :         int err = 0;
    1362             :         struct scanned_info si;
    1363             : 
    1364         425 :         si.valid_inos = si.del_inos = si.valid_dents = si.del_dents = RB_ROOT;
    1365         425 :         log_out(c, "Start rebuilding filesystem (Notice: dropping data/recovering deleted data can't be awared)");
    1366         425 :         FSCK(c)->mode = REBUILD_MODE;
    1367             : 
    1368         425 :         err = init_rebuild_info(c);
    1369         425 :         if (err) {
    1370           0 :                 exit_code |= FSCK_ERROR;
    1371           0 :                 return err;
    1372             :         }
    1373             : 
    1374             :         /* Step 1: Scan valid/deleted nodes from volume. */
    1375         425 :         log_out(c, "Scan nodes");
    1376         425 :         err = scan_nodes(c, &si);
    1377         425 :         if (err) {
    1378           1 :                 exit_code |= FSCK_ERROR;
    1379           1 :                 goto out;
    1380             :         }
    1381             : 
    1382             :         /* Step 2: Remove deleted nodes from valid node tree. */
    1383         424 :         log_out(c, "Remove deleted nodes");
    1384         424 :         remove_del_nodes(c, &si);
    1385             : 
    1386             :         /* Step 3: Add valid nodes into file. */
    1387         424 :         log_out(c, "Add valid nodes into file");
    1388         424 :         err = add_valid_nodes_into_file(c, &si);
    1389         424 :         if (err) {
    1390           0 :                 exit_code |= FSCK_ERROR;
    1391           0 :                 goto out;
    1392             :         }
    1393             : 
    1394             :         /* Step 4: Drop invalid files. */
    1395         424 :         log_out(c, "Filter invalid files");
    1396         424 :         filter_invalid_files(c);
    1397             : 
    1398             :         /* Step 5: Extract reachable directory entries. */
    1399         424 :         log_out(c, "Extract reachable files");
    1400         424 :         extract_dentry_tree(c);
    1401             : 
    1402             :         /* Step 6: Check & correct files' information. */
    1403         424 :         log_out(c, "Check & correct file information");
    1404         424 :         err = check_and_correct_files(c);
    1405         424 :         if (err) {
    1406          58 :                 exit_code |= FSCK_ERROR;
    1407          58 :                 goto out;
    1408             :         }
    1409             : 
    1410             :         /*
    1411             :          * Step 7: Record used LEBs.
    1412             :          * Step 8: Re-write data to clean corrupted data.
    1413             :          * Step 9: Build TNC.
    1414             :          */
    1415         366 :         err = traverse_files_and_nodes(c);
    1416         366 :         if (err) {
    1417         208 :                 exit_code |= FSCK_ERROR;
    1418         208 :                 goto out;
    1419             :         }
    1420             : 
    1421             :         /* Step 10. Build LPT. */
    1422         158 :         log_out(c, "Build LPT");
    1423         158 :         err = build_lpt(c, calculate_lp, true);
    1424         158 :         if (err) {
    1425           0 :                 exit_code |= FSCK_ERROR;
    1426           0 :                 goto out;
    1427             :         }
    1428             : 
    1429             :         /* Step 11. Clean up log & orphan. */
    1430         158 :         log_out(c, "Clean up log & orphan");
    1431         158 :         err = clean_log(c);
    1432         158 :         if (err) {
    1433           0 :                 exit_code |= FSCK_ERROR;
    1434           0 :                 goto out;
    1435             :         }
    1436         158 :         err = ubifs_clear_orphans(c);
    1437         158 :         if (err) {
    1438           0 :                 exit_code |= FSCK_ERROR;
    1439           0 :                 goto out;
    1440             :         }
    1441             : 
    1442             :         /* Step 12. Write master node. */
    1443         158 :         log_out(c, "Write master");
    1444         158 :         err = write_master(c);
    1445         158 :         if (err)
    1446           0 :                 exit_code |= FSCK_ERROR;
    1447             : 
    1448         583 : out:
    1449         425 :         destroy_scanned_info(c, &si);
    1450         425 :         destroy_rebuild_info(c);
    1451             : 
    1452         425 :         return err;
    1453             : }

Generated by: LCOV version 1.13