LCOV - code coverage report
Current view: top level - libubifs - tnc.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 814 1130 72.0 %
Date: 2024-06-05 20:10:43 Functions: 40 48 83.3 %
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 TNC (Tree Node Cache) which caches indexing nodes of
      13             :  * the UBIFS B-tree.
      14             :  *
      15             :  * At the moment the locking rules of the TNC tree are quite simple and
      16             :  * straightforward. We just have a mutex and lock it when we traverse the
      17             :  * tree. If a znode is not in memory, we read it from flash while still having
      18             :  * the mutex locked.
      19             :  */
      20             : 
      21             : #include "linux_err.h"
      22             : #include "bitops.h"
      23             : #include "kmem.h"
      24             : #include "crc32.h"
      25             : #include "ubifs.h"
      26             : #include "defs.h"
      27             : #include "debug.h"
      28             : #include "key.h"
      29             : #include "misc.h"
      30             : 
      31             : static int try_read_node(const struct ubifs_info *c, void *buf, int type,
      32             :                          struct ubifs_zbranch *zbr);
      33             : static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
      34             :                               struct ubifs_zbranch *zbr, void *node);
      35             : 
      36             : /*
      37             :  * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions.
      38             :  * @NAME_LESS: name corresponding to the first argument is less than second
      39             :  * @NAME_MATCHES: names match
      40             :  * @NAME_GREATER: name corresponding to the second argument is greater than
      41             :  *                first
      42             :  * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media
      43             :  *
      44             :  * These constants were introduce to improve readability.
      45             :  */
      46             : enum {
      47             :         NAME_LESS    = 0,
      48             :         NAME_MATCHES = 1,
      49             :         NAME_GREATER = 2,
      50             :         NOT_ON_MEDIA = 3,
      51             : };
      52             : 
      53     1738207 : static void do_insert_old_idx(struct ubifs_info *c,
      54             :                               struct ubifs_old_idx *old_idx)
      55             : {
      56             :         struct ubifs_old_idx *o;
      57     1738207 :         struct rb_node **p, *parent = NULL;
      58             : 
      59     1738207 :         p = &c->old_idx.rb_node;
      60    37207606 :         while (*p) {
      61    33731192 :                 parent = *p;
      62    33731192 :                 o = rb_entry(parent, struct ubifs_old_idx, rb);
      63    33731192 :                 if (old_idx->lnum < o->lnum)
      64    10360668 :                         p = &(*p)->rb_left;
      65    23370524 :                 else if (old_idx->lnum > o->lnum)
      66     7995386 :                         p = &(*p)->rb_right;
      67    15375138 :                 else if (old_idx->offs < o->offs)
      68      866900 :                         p = &(*p)->rb_left;
      69    14508238 :                 else if (old_idx->offs > o->offs)
      70    14508238 :                         p = &(*p)->rb_right;
      71             :                 else {
      72           0 :                         ubifs_err(c, "old idx added twice!");
      73             :                         kfree(old_idx);
      74             :                         return;
      75             :                 }
      76             :         }
      77     3476414 :         rb_link_node(&old_idx->rb, parent, p);
      78     1738207 :         rb_insert_color(&old_idx->rb, &c->old_idx);
      79             : }
      80             : 
      81             : /**
      82             :  * insert_old_idx - record an index node obsoleted since the last commit start.
      83             :  * @c: UBIFS file-system description object
      84             :  * @lnum: LEB number of obsoleted index node
      85             :  * @offs: offset of obsoleted index node
      86             :  *
      87             :  * Returns %0 on success, and a negative error code on failure.
      88             :  *
      89             :  * For recovery, there must always be a complete intact version of the index on
      90             :  * flash at all times. That is called the "old index". It is the index as at the
      91             :  * time of the last successful commit. Many of the index nodes in the old index
      92             :  * may be dirty, but they must not be erased until the next successful commit
      93             :  * (at which point that index becomes the old index).
      94             :  *
      95             :  * That means that the garbage collection and the in-the-gaps method of
      96             :  * committing must be able to determine if an index node is in the old index.
      97             :  * Most of the old index nodes can be found by looking up the TNC using the
      98             :  * 'lookup_znode()' function. However, some of the old index nodes may have
      99             :  * been deleted from the current index or may have been changed so much that
     100             :  * they cannot be easily found. In those cases, an entry is added to an RB-tree.
     101             :  * That is what this function does. The RB-tree is ordered by LEB number and
     102             :  * offset because they uniquely identify the old index node.
     103             :  */
     104     1738207 : static int insert_old_idx(struct ubifs_info *c, int lnum, int offs)
     105             : {
     106             :         struct ubifs_old_idx *old_idx;
     107             : 
     108     1738207 :         old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);
     109     1738207 :         if (unlikely(!old_idx))
     110             :                 return -ENOMEM;
     111     1738207 :         old_idx->lnum = lnum;
     112     1738207 :         old_idx->offs = offs;
     113     1738207 :         do_insert_old_idx(c, old_idx);
     114             : 
     115     1738207 :         return 0;
     116             : }
     117             : 
     118             : /**
     119             :  * insert_old_idx_znode - record a znode obsoleted since last commit start.
     120             :  * @c: UBIFS file-system description object
     121             :  * @znode: znode of obsoleted index node
     122             :  *
     123             :  * Returns %0 on success, and a negative error code on failure.
     124             :  */
     125     1770017 : int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode)
     126             : {
     127     1770017 :         if (znode->parent) {
     128             :                 struct ubifs_zbranch *zbr;
     129             : 
     130     1769993 :                 zbr = &znode->parent->zbranch[znode->iip];
     131     1769993 :                 if (zbr->len)
     132     1737971 :                         return insert_old_idx(c, zbr->lnum, zbr->offs);
     133             :         } else
     134          24 :                 if (c->zroot.len)
     135          24 :                         return insert_old_idx(c, c->zroot.lnum,
     136             :                                               c->zroot.offs);
     137             :         return 0;
     138             : }
     139             : 
     140             : /**
     141             :  * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.
     142             :  * @c: UBIFS file-system description object
     143             :  * @znode: znode of obsoleted index node
     144             :  *
     145             :  * Returns %0 on success, and a negative error code on failure.
     146             :  */
     147       12820 : static int ins_clr_old_idx_znode(struct ubifs_info *c,
     148             :                                  struct ubifs_znode *znode)
     149             : {
     150             :         int err;
     151             : 
     152       12820 :         if (znode->parent) {
     153             :                 struct ubifs_zbranch *zbr;
     154             : 
     155       12820 :                 zbr = &znode->parent->zbranch[znode->iip];
     156       12820 :                 if (zbr->len) {
     157         206 :                         err = insert_old_idx(c, zbr->lnum, zbr->offs);
     158         206 :                         if (err)
     159             :                                 return err;
     160         206 :                         zbr->lnum = 0;
     161         206 :                         zbr->offs = 0;
     162         206 :                         zbr->len = 0;
     163             :                 }
     164             :         } else
     165           0 :                 if (c->zroot.len) {
     166           0 :                         err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs);
     167           0 :                         if (err)
     168             :                                 return err;
     169           0 :                         c->zroot.lnum = 0;
     170           0 :                         c->zroot.offs = 0;
     171           0 :                         c->zroot.len = 0;
     172             :                 }
     173             :         return 0;
     174             : }
     175             : 
     176             : /**
     177             :  * destroy_old_idx - destroy the old_idx RB-tree.
     178             :  * @c: UBIFS file-system description object
     179             :  *
     180             :  * During start commit, the old_idx RB-tree is used to avoid overwriting index
     181             :  * nodes that were in the index last commit but have since been deleted.  This
     182             :  * is necessary for recovery i.e. the old index must be kept intact until the
     183             :  * new index is successfully written.  The old-idx RB-tree is used for the
     184             :  * in-the-gaps method of writing index nodes and is destroyed every commit.
     185             :  */
     186        5378 : void destroy_old_idx(struct ubifs_info *c)
     187             : {
     188             :         struct ubifs_old_idx *old_idx, *n;
     189             : 
     190     1727619 :         rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb)
     191     1722241 :                 kfree(old_idx);
     192             : 
     193        5378 :         c->old_idx = RB_ROOT;
     194        5378 : }
     195             : 
     196             : /**
     197             :  * copy_znode - copy a dirty znode.
     198             :  * @c: UBIFS file-system description object
     199             :  * @znode: znode to copy
     200             :  *
     201             :  * A dirty znode being committed may not be changed, so it is copied.
     202             :  */
     203           0 : static struct ubifs_znode *copy_znode(struct ubifs_info *c,
     204             :                                       struct ubifs_znode *znode)
     205             : {
     206             :         struct ubifs_znode *zn;
     207             : 
     208           0 :         zn = kmemdup(znode, c->max_znode_sz, GFP_NOFS);
     209           0 :         if (unlikely(!zn))
     210             :                 return ERR_PTR(-ENOMEM);
     211             : 
     212           0 :         zn->cnext = NULL;
     213           0 :         __set_bit(DIRTY_ZNODE, &zn->flags);
     214           0 :         __clear_bit(COW_ZNODE, &zn->flags);
     215             : 
     216           0 :         return zn;
     217             : }
     218             : 
     219             : /**
     220             :  * add_idx_dirt - add dirt due to a dirty znode.
     221             :  * @c: UBIFS file-system description object
     222             :  * @lnum: LEB number of index node
     223             :  * @dirt: size of index node
     224             :  *
     225             :  * This function updates lprops dirty space and the new size of the index.
     226             :  */
     227             : static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt)
     228             : {
     229     2264334 :         c->calc_idx_sz -= ALIGN(dirt, 8);
     230     2264334 :         return ubifs_add_dirt(c, lnum, dirt);
     231             : }
     232             : 
     233             : /**
     234             :  * replace_znode - replace old znode with new znode.
     235             :  * @c: UBIFS file-system description object
     236             :  * @new_zn: new znode
     237             :  * @old_zn: old znode
     238             :  * @zbr: the branch of parent znode
     239             :  *
     240             :  * Replace old znode with new znode in TNC.
     241             :  */
     242           0 : static void replace_znode(struct ubifs_info *c, struct ubifs_znode *new_zn,
     243             :                           struct ubifs_znode *old_zn, struct ubifs_zbranch *zbr)
     244             : {
     245           0 :         ubifs_assert(c, !ubifs_zn_obsolete(old_zn));
     246           0 :         __set_bit(OBSOLETE_ZNODE, &old_zn->flags);
     247             : 
     248           0 :         if (old_zn->level != 0) {
     249             :                 int i;
     250           0 :                 const int n = new_zn->child_cnt;
     251             : 
     252             :                 /* The children now have new parent */
     253           0 :                 for (i = 0; i < n; i++) {
     254           0 :                         struct ubifs_zbranch *child = &new_zn->zbranch[i];
     255             : 
     256           0 :                         if (child->znode)
     257           0 :                                 child->znode->parent = new_zn;
     258             :                 }
     259             :         }
     260             : 
     261           0 :         zbr->znode = new_zn;
     262           0 :         zbr->lnum = 0;
     263           0 :         zbr->offs = 0;
     264           0 :         zbr->len = 0;
     265             : 
     266           0 :         atomic_long_inc(&c->dirty_zn_cnt);
     267           0 : }
     268             : 
     269             : /**
     270             :  * dirty_cow_znode - ensure a znode is not being committed.
     271             :  * @c: UBIFS file-system description object
     272             :  * @zbr: branch of znode to check
     273             :  *
     274             :  * Returns dirtied znode on success or negative error code on failure.
     275             :  */
     276    37540205 : static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c,
     277             :                                            struct ubifs_zbranch *zbr)
     278             : {
     279    37540205 :         struct ubifs_znode *znode = zbr->znode;
     280             :         struct ubifs_znode *zn;
     281             :         int err;
     282             : 
     283    37540205 :         if (!ubifs_zn_cow(znode)) {
     284             :                 /* znode is not being committed */
     285    39804539 :                 if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) {
     286     4528668 :                         atomic_long_inc(&c->dirty_zn_cnt);
     287     4528668 :                         atomic_long_dec(&c->clean_zn_cnt);
     288     2264334 :                         atomic_long_dec(&ubifs_clean_zn_cnt);
     289     4528668 :                         err = add_idx_dirt(c, zbr->lnum, zbr->len);
     290     2264334 :                         if (unlikely(err))
     291           0 :                                 return ERR_PTR(err);
     292             :                 }
     293             :                 return znode;
     294             :         }
     295             : 
     296           0 :         zn = copy_znode(c, znode);
     297           0 :         if (IS_ERR(zn))
     298             :                 return zn;
     299             : 
     300           0 :         if (zbr->len) {
     301             :                 struct ubifs_old_idx *old_idx;
     302             : 
     303           0 :                 old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);
     304           0 :                 if (unlikely(!old_idx)) {
     305             :                         err = -ENOMEM;
     306             :                         goto out;
     307             :                 }
     308           0 :                 old_idx->lnum = zbr->lnum;
     309           0 :                 old_idx->offs = zbr->offs;
     310             : 
     311           0 :                 err = add_idx_dirt(c, zbr->lnum, zbr->len);
     312           0 :                 if (err) {
     313             :                         kfree(old_idx);
     314             :                         goto out;
     315             :                 }
     316             : 
     317           0 :                 do_insert_old_idx(c, old_idx);
     318             :         }
     319             : 
     320           0 :         replace_znode(c, zn, znode, zbr);
     321             : 
     322           0 :         return zn;
     323             : 
     324           0 : out:
     325           0 :         kfree(zn);
     326           0 :         return ERR_PTR(err);
     327             : }
     328             : 
     329             : /**
     330             :  * lnc_add - add a leaf node to the leaf node cache.
     331             :  * @c: UBIFS file-system description object
     332             :  * @zbr: zbranch of leaf node
     333             :  * @node: leaf node
     334             :  *
     335             :  * Leaf nodes are non-index nodes directory entry nodes or data nodes. The
     336             :  * purpose of the leaf node cache is to save re-reading the same leaf node over
     337             :  * and over again. Most things are cached by VFS, however the file system must
     338             :  * cache directory entries for readdir and for resolving hash collisions. The
     339             :  * present implementation of the leaf node cache is extremely simple, and
     340             :  * allows for error returns that are not used but that may be needed if a more
     341             :  * complex implementation is created.
     342             :  *
     343             :  * Note, this function does not add the @node object to LNC directly, but
     344             :  * allocates a copy of the object and adds the copy to LNC. The reason for this
     345             :  * is that @node has been allocated outside of the TNC subsystem and will be
     346             :  * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC
     347             :  * may be changed at any time, e.g. freed by the shrinker.
     348             :  */
     349         457 : static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr,
     350             :                    const void *node)
     351             : {
     352             :         int err;
     353             :         void *lnc_node;
     354         457 :         const struct ubifs_dent_node *dent = node;
     355             : 
     356         457 :         ubifs_assert(c, !zbr->leaf);
     357         457 :         ubifs_assert(c, zbr->len != 0);
     358         914 :         ubifs_assert(c, is_hash_key(c, &zbr->key));
     359             : 
     360         457 :         err = ubifs_validate_entry(c, dent);
     361         457 :         if (err) {
     362           0 :                 dump_stack();
     363           0 :                 ubifs_dump_node(c, dent, zbr->len);
     364           0 :                 return err;
     365             :         }
     366             : 
     367         457 :         lnc_node = kmemdup(node, zbr->len, GFP_NOFS);
     368         457 :         if (!lnc_node)
     369             :                 /* We don't have to have the cache, so no error */
     370             :                 return 0;
     371             : 
     372         457 :         zbr->leaf = lnc_node;
     373         457 :         return 0;
     374             : }
     375             : 
     376             :  /**
     377             :  * lnc_add_directly - add a leaf node to the leaf-node-cache.
     378             :  * @c: UBIFS file-system description object
     379             :  * @zbr: zbranch of leaf node
     380             :  * @node: leaf node
     381             :  *
     382             :  * This function is similar to 'lnc_add()', but it does not create a copy of
     383             :  * @node but inserts @node to TNC directly.
     384             :  */
     385      355867 : static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr,
     386             :                             void *node)
     387             : {
     388             :         int err;
     389             : 
     390      355867 :         ubifs_assert(c, !zbr->leaf);
     391      355867 :         ubifs_assert(c, zbr->len != 0);
     392             : 
     393      355867 :         err = ubifs_validate_entry(c, node);
     394      355867 :         if (err) {
     395           0 :                 dump_stack();
     396           0 :                 ubifs_dump_node(c, node, zbr->len);
     397             :                 return err;
     398             :         }
     399             : 
     400      355867 :         zbr->leaf = node;
     401             :         return 0;
     402             : }
     403             : 
     404             : /**
     405             :  * lnc_free - remove a leaf node from the leaf node cache.
     406             :  * @zbr: zbranch of leaf node
     407             :  */
     408             : static void lnc_free(struct ubifs_zbranch *zbr)
     409             : {
     410     3559691 :         if (!zbr->leaf)
     411             :                 return;
     412       37242 :         kfree(zbr->leaf);
     413       18621 :         zbr->leaf = NULL;
     414             : }
     415             : 
     416             : /**
     417             :  * tnc_read_hashed_node - read a "hashed" leaf node.
     418             :  * @c: UBIFS file-system description object
     419             :  * @zbr: key and position of the node
     420             :  * @node: node is returned here
     421             :  *
     422             :  * This function reads a "hashed" node defined by @zbr from the leaf node cache
     423             :  * (in it is there) or from the hash media, in which case the node is also
     424             :  * added to LNC. Returns zero in case of success or a negative error
     425             :  * code in case of failure.
     426             :  */
     427         881 : static int tnc_read_hashed_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
     428             :                                 void *node)
     429             : {
     430             :         int err;
     431             : 
     432        1762 :         ubifs_assert(c, is_hash_key(c, &zbr->key));
     433             : 
     434         881 :         if (zbr->leaf) {
     435             :                 /* Read from the leaf node cache */
     436         323 :                 ubifs_assert(c, zbr->len != 0);
     437         323 :                 memcpy(node, zbr->leaf, zbr->len);
     438         323 :                 return 0;
     439             :         }
     440             : 
     441         558 :         if (c->replaying) {
     442         519 :                 err = fallible_read_node(c, &zbr->key, zbr, node);
     443             :                 /*
     444             :                  * When the node was not found, return -ENOENT, 0 otherwise.
     445             :                  * Negative return codes stay as-is.
     446             :                  */
     447         519 :                 if (err == 0)
     448             :                         err = -ENOENT;
     449         418 :                 else if (err == 1)
     450             :                         err = 0;
     451             :         } else {
     452          39 :                 err = ubifs_tnc_read_node(c, zbr, node);
     453             :         }
     454          39 :         if (err)
     455             :                 return err;
     456             : 
     457             :         /* Add the node to the leaf node cache */
     458         457 :         err = lnc_add(c, zbr, node);
     459         457 :         return err;
     460             : }
     461             : 
     462             : /**
     463             :  * try_read_node - read a node if it is a node.
     464             :  * @c: UBIFS file-system description object
     465             :  * @buf: buffer to read to
     466             :  * @type: node type
     467             :  * @zbr: the zbranch describing the node to read
     468             :  *
     469             :  * This function tries to read a node of known type and length, checks it and
     470             :  * stores it in @buf. This function returns %1 if a node is present and %0 if
     471             :  * a node is not present. A negative error code is returned for I/O errors.
     472             :  * This function performs that same function as ubifs_read_node except that
     473             :  * it does not require that there is actually a node present and instead
     474             :  * the return code indicates if a node was read.
     475             :  *
     476             :  * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc
     477             :  * is true (it is controlled by corresponding mount option). However, if
     478             :  * @c->mounting or @c->remounting_rw is true (we are mounting or re-mounting to
     479             :  * R/W mode), @c->no_chk_data_crc is ignored and CRC is checked. This is
     480             :  * because during mounting or re-mounting from R/O mode to R/W mode we may read
     481             :  * journal nodes (when replying the journal or doing the recovery) and the
     482             :  * journal nodes may potentially be corrupted, so checking is required.
     483             :  */
     484      994190 : static int try_read_node(const struct ubifs_info *c, void *buf, int type,
     485             :                          struct ubifs_zbranch *zbr)
     486             : {
     487      994190 :         int len = zbr->len;
     488      994190 :         int lnum = zbr->lnum;
     489      994190 :         int offs = zbr->offs;
     490             :         int err, node_len;
     491      994190 :         struct ubifs_ch *ch = buf;
     492             :         uint32_t crc, node_crc;
     493             : 
     494      994190 :         dbg_io("LEB %d:%d, %s, length %d", lnum, offs, dbg_ntype(type), len);
     495             : 
     496      994190 :         err = ubifs_leb_read(c, lnum, buf, offs, len, 1);
     497      994190 :         if (err && err != -EBADMSG) {
     498           0 :                 ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d",
     499             :                           type, lnum, offs, err);
     500             :                 return err;
     501             :         }
     502             : 
     503      994190 :         if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
     504             :                 return 0;
     505             : 
     506      402346 :         if (ch->node_type != type)
     507             :                 return 0;
     508             : 
     509      359708 :         node_len = le32_to_cpu(ch->len);
     510      359708 :         if (node_len != len)
     511             :                 return 0;
     512             : 
     513      359380 :         if (type != UBIFS_DATA_NODE || !c->no_chk_data_crc || c->mounting ||
     514             :             c->remounting_rw) {
     515      718760 :                 crc = crc32(UBIFS_CRC32_INIT, buf + 8, node_len - 8);
     516      359380 :                 node_crc = le32_to_cpu(ch->crc);
     517      359380 :                 if (crc != node_crc)
     518             :                         return 0;
     519             :         }
     520             : 
     521      359380 :         err = ubifs_node_check_hash(c, buf, zbr->hash);
     522             :         if (err) {
     523             :                 ubifs_bad_hash(c, buf, zbr->hash, lnum, offs);
     524             :                 return 0;
     525             :         }
     526             : 
     527             :         return 1;
     528             : }
     529             : 
     530             : /**
     531             :  * fallible_read_node - try to read a leaf node.
     532             :  * @c: UBIFS file-system description object
     533             :  * @key:  key of node to read
     534             :  * @zbr:  position of node
     535             :  * @node: node returned
     536             :  *
     537             :  * This function tries to read a node and returns %1 if the node is read, %0
     538             :  * if the node is not present, and a negative error code in the case of error.
     539             :  */
     540      994190 : static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
     541             :                               struct ubifs_zbranch *zbr, void *node)
     542             : {
     543             :         int ret;
     544             : 
     545      994190 :         dbg_tnck(key, "LEB %d:%d, key ", zbr->lnum, zbr->offs);
     546             : 
     547     1988380 :         ret = try_read_node(c, node, key_type(c, key), zbr);
     548      994190 :         if (ret == 1) {
     549             :                 union ubifs_key node_key;
     550      359380 :                 struct ubifs_dent_node *dent = node;
     551             : 
     552             :                 /* All nodes have key in the same place */
     553      718760 :                 key_read(c, &dent->key, &node_key);
     554      715665 :                 if (keys_cmp(c, key, &node_key) != 0)
     555        3095 :                         ret = 0;
     556             :         }
     557      991095 :         if (ret == 0 && c->replaying)
     558      637905 :                 dbg_mntk(key, "dangling branch LEB %d:%d len %d, key ",
     559             :                         zbr->lnum, zbr->offs, zbr->len);
     560      994190 :         return ret;
     561             : }
     562             : 
     563             : /**
     564             :  * matches_name - determine if a direntry or xattr entry matches a given name.
     565             :  * @c: UBIFS file-system description object
     566             :  * @zbr: zbranch of dent
     567             :  * @nm: name to match
     568             :  *
     569             :  * This function checks if xentry/direntry referred by zbranch @zbr matches name
     570             :  * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by
     571             :  * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case
     572             :  * of failure, a negative error code is returned.
     573             :  */
     574           0 : static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr,
     575             :                         const struct fscrypt_name *nm)
     576             : {
     577             :         struct ubifs_dent_node *dent;
     578             :         int nlen, err;
     579             : 
     580             :         /* If possible, match against the dent in the leaf node cache */
     581           0 :         if (!zbr->leaf) {
     582           0 :                 dent = kmalloc(zbr->len, GFP_NOFS);
     583           0 :                 if (!dent)
     584             :                         return -ENOMEM;
     585             : 
     586           0 :                 err = ubifs_tnc_read_node(c, zbr, dent);
     587           0 :                 if (err)
     588             :                         goto out_free;
     589             : 
     590             :                 /* Add the node to the leaf node cache */
     591           0 :                 err = lnc_add_directly(c, zbr, dent);
     592           0 :                 if (err)
     593             :                         goto out_free;
     594             :         } else
     595             :                 dent = zbr->leaf;
     596             : 
     597           0 :         nlen = le16_to_cpu(dent->nlen);
     598           0 :         err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));
     599           0 :         if (err == 0) {
     600           0 :                 if (nlen == fname_len(nm))
     601             :                         return NAME_MATCHES;
     602           0 :                 else if (nlen < fname_len(nm))
     603             :                         return NAME_LESS;
     604             :                 else
     605           0 :                         return NAME_GREATER;
     606           0 :         } else if (err < 0)
     607             :                 return NAME_LESS;
     608             :         else
     609           0 :                 return NAME_GREATER;
     610             : 
     611           0 : out_free:
     612           0 :         kfree(dent);
     613           0 :         return err;
     614             : }
     615             : 
     616             : /**
     617             :  * get_znode - get a TNC znode that may not be loaded yet.
     618             :  * @c: UBIFS file-system description object
     619             :  * @znode: parent znode
     620             :  * @n: znode branch slot number
     621             :  *
     622             :  * This function returns the znode or a negative error code.
     623             :  */
     624             : static struct ubifs_znode *get_znode(struct ubifs_info *c,
     625             :                                      struct ubifs_znode *znode, int n)
     626             : {
     627             :         struct ubifs_zbranch *zbr;
     628             : 
     629 16294335069 :         zbr = &znode->zbranch[n];
     630 16294335069 :         if (zbr->znode)
     631             :                 znode = zbr->znode;
     632             :         else
     633      165528 :                 znode = ubifs_load_znode(c, zbr, znode, n);
     634             :         return znode;
     635             : }
     636             : 
     637             : /**
     638             :  * tnc_next - find next TNC entry.
     639             :  * @c: UBIFS file-system description object
     640             :  * @zn: znode is passed and returned here
     641             :  * @n: znode branch slot number is passed and returned here
     642             :  *
     643             :  * This function returns %0 if the next TNC entry is found, %-ENOENT if there is
     644             :  * no next entry, or a negative error code otherwise.
     645             :  */
     646    34970984 : static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
     647             : {
     648    34970984 :         struct ubifs_znode *znode = *zn;
     649    34970984 :         int nn = *n;
     650             : 
     651    34970984 :         nn += 1;
     652    34970984 :         if (nn < znode->child_cnt) {
     653    27956129 :                 *n = nn;
     654    27956129 :                 return 0;
     655             :         }
     656             :         while (1) {
     657             :                 struct ubifs_znode *zp;
     658             : 
     659     8005354 :                 zp = znode->parent;
     660     8005354 :                 if (!zp)
     661             :                         return -ENOENT;
     662     7999767 :                 nn = znode->iip + 1;
     663     7999767 :                 znode = zp;
     664     7999767 :                 if (nn < znode->child_cnt) {
     665     7009268 :                         znode = get_znode(c, znode, nn);
     666     7009268 :                         if (IS_ERR(znode))
     667           0 :                                 return PTR_ERR(znode);
     668     7956457 :                         while (znode->level != 0) {
     669      947189 :                                 znode = get_znode(c, znode, 0);
     670      947189 :                                 if (IS_ERR(znode))
     671           0 :                                         return PTR_ERR(znode);
     672             :                         }
     673     7009268 :                         nn = 0;
     674             :                         break;
     675             :                 }
     676             :         }
     677     7009268 :         *zn = znode;
     678     7009268 :         *n = nn;
     679     7009268 :         return 0;
     680             : }
     681             : 
     682             : /**
     683             :  * tnc_prev - find previous TNC entry.
     684             :  * @c: UBIFS file-system description object
     685             :  * @zn: znode is returned here
     686             :  * @n: znode branch slot number is passed and returned here
     687             :  *
     688             :  * This function returns %0 if the previous TNC entry is found, %-ENOENT if
     689             :  * there is no next entry, or a negative error code otherwise.
     690             :  */
     691    52043489 : static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
     692             : {
     693    52043489 :         struct ubifs_znode *znode = *zn;
     694    52043489 :         int nn = *n;
     695             : 
     696    52043489 :         if (nn > 0) {
     697    27893374 :                 *n = nn - 1;
     698    27893374 :                 return 0;
     699             :         }
     700             :         while (1) {
     701             :                 struct ubifs_znode *zp;
     702             : 
     703    28351110 :                 zp = znode->parent;
     704    28351110 :                 if (!zp)
     705             :                         return -ENOENT;
     706    28349292 :                 nn = znode->iip - 1;
     707    28349292 :                 znode = zp;
     708    28349292 :                 if (nn >= 0) {
     709    24148297 :                         znode = get_znode(c, znode, nn);
     710    24148297 :                         if (IS_ERR(znode))
     711           0 :                                 return PTR_ERR(znode);
     712    28340250 :                         while (znode->level != 0) {
     713     4191953 :                                 nn = znode->child_cnt - 1;
     714     4191953 :                                 znode = get_znode(c, znode, nn);
     715     4191953 :                                 if (IS_ERR(znode))
     716           0 :                                         return PTR_ERR(znode);
     717             :                         }
     718    24148297 :                         nn = znode->child_cnt - 1;
     719             :                         break;
     720             :                 }
     721             :         }
     722    24148297 :         *zn = znode;
     723    24148297 :         *n = nn;
     724    24148297 :         return 0;
     725             : }
     726             : 
     727             : /**
     728             :  * resolve_collision - resolve a collision.
     729             :  * @c: UBIFS file-system description object
     730             :  * @key: key of a directory or extended attribute entry
     731             :  * @zn: znode is returned here
     732             :  * @n: zbranch number is passed and returned here
     733             :  * @nm: name of the entry
     734             :  *
     735             :  * This function is called for "hashed" keys to make sure that the found key
     736             :  * really corresponds to the looked up node (directory or extended attribute
     737             :  * entry). It returns %1 and sets @zn and @n if the collision is resolved.
     738             :  * %0 is returned if @nm is not found and @zn and @n are set to the previous
     739             :  * entry, i.e. to the entry after which @nm could follow if it were in TNC.
     740             :  * This means that @n may be set to %-1 if the leftmost key in @zn is the
     741             :  * previous one. A negative error code is returned on failures.
     742             :  */
     743           0 : static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,
     744             :                              struct ubifs_znode **zn, int *n,
     745             :                              const struct fscrypt_name *nm)
     746             : {
     747             :         int err;
     748             : 
     749           0 :         err = matches_name(c, &(*zn)->zbranch[*n], nm);
     750           0 :         if (unlikely(err < 0))
     751             :                 return err;
     752           0 :         if (err == NAME_MATCHES)
     753             :                 return 1;
     754             : 
     755           0 :         if (err == NAME_GREATER) {
     756             :                 /* Look left */
     757             :                 while (1) {
     758           0 :                         err = tnc_prev(c, zn, n);
     759           0 :                         if (err == -ENOENT) {
     760           0 :                                 ubifs_assert(c, *n == 0);
     761           0 :                                 *n = -1;
     762           0 :                                 return 0;
     763             :                         }
     764           0 :                         if (err < 0)
     765             :                                 return err;
     766           0 :                         if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
     767             :                                 /*
     768             :                                  * We have found the branch after which we would
     769             :                                  * like to insert, but inserting in this znode
     770             :                                  * may still be wrong. Consider the following 3
     771             :                                  * znodes, in the case where we are resolving a
     772             :                                  * collision with Key2.
     773             :                                  *
     774             :                                  *                  znode zp
     775             :                                  *            ----------------------
     776             :                                  * level 1     |  Key0  |  Key1  |
     777             :                                  *            -----------------------
     778             :                                  *                 |            |
     779             :                                  *       znode za  |            |  znode zb
     780             :                                  *          ------------      ------------
     781             :                                  * level 0  |  Key0  |        |  Key2  |
     782             :                                  *          ------------      ------------
     783             :                                  *
     784             :                                  * The lookup finds Key2 in znode zb. Lets say
     785             :                                  * there is no match and the name is greater so
     786             :                                  * we look left. When we find Key0, we end up
     787             :                                  * here. If we return now, we will insert into
     788             :                                  * znode za at slot n = 1.  But that is invalid
     789             :                                  * according to the parent's keys.  Key2 must
     790             :                                  * be inserted into znode zb.
     791             :                                  *
     792             :                                  * Note, this problem is not relevant for the
     793             :                                  * case when we go right, because
     794             :                                  * 'tnc_insert()' would correct the parent key.
     795             :                                  */
     796           0 :                                 if (*n == (*zn)->child_cnt - 1) {
     797           0 :                                         err = tnc_next(c, zn, n);
     798           0 :                                         if (err) {
     799             :                                                 /* Should be impossible */
     800           0 :                                                 ubifs_assert(c, 0);
     801           0 :                                                 if (err == -ENOENT)
     802           0 :                                                         err = -EINVAL;
     803             :                                                 return err;
     804             :                                         }
     805           0 :                                         ubifs_assert(c, *n == 0);
     806           0 :                                         *n = -1;
     807             :                                 }
     808             :                                 return 0;
     809             :                         }
     810           0 :                         err = matches_name(c, &(*zn)->zbranch[*n], nm);
     811           0 :                         if (err < 0)
     812             :                                 return err;
     813           0 :                         if (err == NAME_LESS)
     814             :                                 return 0;
     815           0 :                         if (err == NAME_MATCHES)
     816             :                                 return 1;
     817           0 :                         ubifs_assert(c, err == NAME_GREATER);
     818             :                 }
     819             :         } else {
     820           0 :                 int nn = *n;
     821           0 :                 struct ubifs_znode *znode = *zn;
     822             : 
     823             :                 /* Look right */
     824             :                 while (1) {
     825           0 :                         err = tnc_next(c, &znode, &nn);
     826           0 :                         if (err == -ENOENT)
     827             :                                 return 0;
     828           0 :                         if (err < 0)
     829             :                                 return err;
     830           0 :                         if (keys_cmp(c, &znode->zbranch[nn].key, key))
     831             :                                 return 0;
     832           0 :                         err = matches_name(c, &znode->zbranch[nn], nm);
     833           0 :                         if (err < 0)
     834             :                                 return err;
     835           0 :                         if (err == NAME_GREATER)
     836             :                                 return 0;
     837           0 :                         *zn = znode;
     838           0 :                         *n = nn;
     839           0 :                         if (err == NAME_MATCHES)
     840             :                                 return 1;
     841           0 :                         ubifs_assert(c, err == NAME_LESS);
     842             :                 }
     843             :         }
     844             : }
     845             : 
     846             : /**
     847             :  * fallible_matches_name - determine if a dent matches a given name.
     848             :  * @c: UBIFS file-system description object
     849             :  * @zbr: zbranch of dent
     850             :  * @nm: name to match
     851             :  *
     852             :  * This is a "fallible" version of 'matches_name()' function which does not
     853             :  * panic if the direntry/xentry referred by @zbr does not exist on the media.
     854             :  *
     855             :  * This function checks if xentry/direntry referred by zbranch @zbr matches name
     856             :  * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr
     857             :  * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA
     858             :  * if xentry/direntry referred by @zbr does not exist on the media. A negative
     859             :  * error code is returned in case of failure.
     860             :  */
     861      995487 : static int fallible_matches_name(struct ubifs_info *c,
     862             :                                  struct ubifs_zbranch *zbr,
     863             :                                  const struct fscrypt_name *nm)
     864             : {
     865             :         struct ubifs_dent_node *dent;
     866             :         int nlen, err;
     867             : 
     868             :         /* If possible, match against the dent in the leaf node cache */
     869      995487 :         if (!zbr->leaf) {
     870      993671 :                 dent = kmalloc(zbr->len, GFP_NOFS);
     871      993671 :                 if (!dent)
     872             :                         return -ENOMEM;
     873             : 
     874      993671 :                 err = fallible_read_node(c, &zbr->key, zbr, dent);
     875      993671 :                 if (err < 0)
     876             :                         goto out_free;
     877      993671 :                 if (err == 0) {
     878             :                         /* The node was not present */
     879             :                         err = NOT_ON_MEDIA;
     880             :                         goto out_free;
     881             :                 }
     882      355867 :                 ubifs_assert(c, err == 1);
     883             : 
     884      355867 :                 err = lnc_add_directly(c, zbr, dent);
     885      355867 :                 if (err)
     886             :                         goto out_free;
     887             :         } else
     888             :                 dent = zbr->leaf;
     889             : 
     890      357683 :         nlen = le16_to_cpu(dent->nlen);
     891      357683 :         err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));
     892      357683 :         if (err == 0) {
     893       19303 :                 if (nlen == fname_len(nm))
     894             :                         return NAME_MATCHES;
     895         682 :                 else if (nlen < fname_len(nm))
     896             :                         return NAME_LESS;
     897             :                 else
     898         682 :                         return NAME_GREATER;
     899      338380 :         } else if (err < 0)
     900             :                 return NAME_LESS;
     901             :         else
     902      338351 :                 return NAME_GREATER;
     903             : 
     904           0 : out_free:
     905      637804 :         kfree(dent);
     906      637804 :         return err;
     907             : }
     908             : 
     909             : /**
     910             :  * fallible_resolve_collision - resolve a collision even if nodes are missing.
     911             :  * @c: UBIFS file-system description object
     912             :  * @key: key
     913             :  * @zn: znode is returned here
     914             :  * @n: branch number is passed and returned here
     915             :  * @nm: name of directory entry
     916             :  * @adding: indicates caller is adding a key to the TNC
     917             :  *
     918             :  * This is a "fallible" version of the 'resolve_collision()' function which
     919             :  * does not panic if one of the nodes referred to by TNC does not exist on the
     920             :  * media. This may happen when replaying the journal if a deleted node was
     921             :  * Garbage-collected and the commit was not done. A branch that refers to a node
     922             :  * that is not present is called a dangling branch. The following are the return
     923             :  * codes for this function:
     924             :  *  o if @nm was found, %1 is returned and @zn and @n are set to the found
     925             :  *    branch;
     926             :  *  o if we are @adding and @nm was not found, %0 is returned;
     927             :  *  o if we are not @adding and @nm was not found, but a dangling branch was
     928             :  *    found, then %1 is returned and @zn and @n are set to the dangling branch;
     929             :  *  o a negative error code is returned in case of failure.
     930             :  */
     931      676677 : static int fallible_resolve_collision(struct ubifs_info *c,
     932             :                                       const union ubifs_key *key,
     933             :                                       struct ubifs_znode **zn, int *n,
     934             :                                       const struct fscrypt_name *nm,
     935             :                                       int adding)
     936             : {
     937      676677 :         struct ubifs_znode *o_znode = NULL, *znode = *zn;
     938      676677 :         int err, cmp, o_n = 0, unsure = 0, nn = *n;
     939             : 
     940      676677 :         cmp = fallible_matches_name(c, &znode->zbranch[nn], nm);
     941      676677 :         if (unlikely(cmp < 0))
     942             :                 return cmp;
     943      676677 :         if (cmp == NAME_MATCHES)
     944             :                 return 1;
     945      658056 :         if (cmp == NOT_ON_MEDIA) {
     946      430410 :                 o_znode = znode;
     947      430410 :                 o_n = nn;
     948             :                 /*
     949             :                  * We are unlucky and hit a dangling branch straight away.
     950             :                  * Now we do not really know where to go to find the needed
     951             :                  * branch - to the left or to the right. Well, let's try left.
     952             :                  */
     953      430410 :                 unsure = 1;
     954      227646 :         } else if (!adding)
     955      227646 :                 unsure = 1; /* Remove a dangling branch wherever it is */
     956             : 
     957      658056 :         if (cmp == NAME_GREATER || unsure) {
     958             :                 /* Look left */
     959             :                 while (1) {
     960      865450 :                         err = tnc_prev(c, zn, n);
     961      865450 :                         if (err == -ENOENT) {
     962           0 :                                 ubifs_assert(c, *n == 0);
     963           0 :                                 *n = -1;
     964           0 :                                 break;
     965             :                         }
     966      865450 :                         if (err < 0)
     967             :                                 return err;
     968     1072844 :                         if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
     969             :                                 /* See comments in 'resolve_collision()' */
     970      658056 :                                 if (*n == (*zn)->child_cnt - 1) {
     971      157876 :                                         err = tnc_next(c, zn, n);
     972      157876 :                                         if (err) {
     973             :                                                 /* Should be impossible */
     974           0 :                                                 ubifs_assert(c, 0);
     975           0 :                                                 if (err == -ENOENT)
     976           0 :                                                         err = -EINVAL;
     977             :                                                 return err;
     978             :                                         }
     979      157876 :                                         ubifs_assert(c, *n == 0);
     980      157876 :                                         *n = -1;
     981             :                                 }
     982             :                                 break;
     983             :                         }
     984      207394 :                         err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm);
     985      207394 :                         if (err < 0)
     986             :                                 return err;
     987      207394 :                         if (err == NAME_MATCHES)
     988             :                                 return 1;
     989      207394 :                         if (err == NOT_ON_MEDIA) {
     990      207394 :                                 o_znode = *zn;
     991      207394 :                                 o_n = *n;
     992      207394 :                                 continue;
     993             :                         }
     994           0 :                         if (!adding)
     995           0 :                                 continue;
     996           0 :                         if (err == NAME_LESS)
     997             :                                 break;
     998             :                         else
     999             :                                 unsure = 0;
    1000             :                 }
    1001             :         }
    1002             : 
    1003      658056 :         if (cmp == NAME_LESS || unsure) {
    1004             :                 /* Look right */
    1005      658056 :                 *zn = znode;
    1006      658056 :                 *n = nn;
    1007             :                 while (1) {
    1008      658056 :                         err = tnc_next(c, &znode, &nn);
    1009      658056 :                         if (err == -ENOENT)
    1010             :                                 break;
    1011      654292 :                         if (err < 0)
    1012             :                                 return err;
    1013      765708 :                         if (keys_cmp(c, &znode->zbranch[nn].key, key))
    1014             :                                 break;
    1015      111416 :                         err = fallible_matches_name(c, &znode->zbranch[nn], nm);
    1016      111416 :                         if (err < 0)
    1017             :                                 return err;
    1018      111416 :                         if (err == NAME_GREATER)
    1019             :                                 break;
    1020           0 :                         *zn = znode;
    1021           0 :                         *n = nn;
    1022           0 :                         if (err == NAME_MATCHES)
    1023             :                                 return 1;
    1024           0 :                         if (err == NOT_ON_MEDIA) {
    1025           0 :                                 o_znode = znode;
    1026           0 :                                 o_n = nn;
    1027             :                         }
    1028             :                 }
    1029             :         }
    1030             : 
    1031             :         /* Never match a dangling branch when adding */
    1032      658056 :         if (adding || !o_znode)
    1033             :                 return 0;
    1034             : 
    1035      318994 :         dbg_mntk(key, "dangling match LEB %d:%d len %d key ",
    1036             :                 o_znode->zbranch[o_n].lnum, o_znode->zbranch[o_n].offs,
    1037             :                 o_znode->zbranch[o_n].len);
    1038      318994 :         *zn = o_znode;
    1039      318994 :         *n = o_n;
    1040      318994 :         return 1;
    1041             : }
    1042             : 
    1043             : /**
    1044             :  * matches_position - determine if a zbranch matches a given position.
    1045             :  * @zbr: zbranch of dent
    1046             :  * @lnum: LEB number of dent to match
    1047             :  * @offs: offset of dent to match
    1048             :  *
    1049             :  * This function returns %1 if @lnum:@offs matches, and %0 otherwise.
    1050             :  */
    1051             : static int matches_position(struct ubifs_zbranch *zbr, int lnum, int offs)
    1052             : {
    1053           0 :         if (zbr->lnum == lnum && zbr->offs == offs)
    1054             :                 return 1;
    1055             :         else
    1056             :                 return 0;
    1057             : }
    1058             : 
    1059             : /**
    1060             :  * resolve_collision_directly - resolve a collision directly.
    1061             :  * @c: UBIFS file-system description object
    1062             :  * @key: key of directory entry
    1063             :  * @zn: znode is passed and returned here
    1064             :  * @n: zbranch number is passed and returned here
    1065             :  * @lnum: LEB number of dent node to match
    1066             :  * @offs: offset of dent node to match
    1067             :  *
    1068             :  * This function is used for "hashed" keys to make sure the found directory or
    1069             :  * extended attribute entry node is what was looked for. It is used when the
    1070             :  * flash address of the right node is known (@lnum:@offs) which makes it much
    1071             :  * easier to resolve collisions (no need to read entries and match full
    1072             :  * names). This function returns %1 and sets @zn and @n if the collision is
    1073             :  * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the
    1074             :  * previous directory entry. Otherwise a negative error code is returned.
    1075             :  */
    1076           0 : static int resolve_collision_directly(struct ubifs_info *c,
    1077             :                                       const union ubifs_key *key,
    1078             :                                       struct ubifs_znode **zn, int *n,
    1079             :                                       int lnum, int offs)
    1080             : {
    1081             :         struct ubifs_znode *znode;
    1082             :         int nn, err;
    1083             : 
    1084           0 :         znode = *zn;
    1085           0 :         nn = *n;
    1086           0 :         if (matches_position(&znode->zbranch[nn], lnum, offs))
    1087             :                 return 1;
    1088             : 
    1089             :         /* Look left */
    1090             :         while (1) {
    1091           0 :                 err = tnc_prev(c, &znode, &nn);
    1092           0 :                 if (err == -ENOENT)
    1093             :                         break;
    1094           0 :                 if (err < 0)
    1095             :                         return err;
    1096           0 :                 if (keys_cmp(c, &znode->zbranch[nn].key, key))
    1097             :                         break;
    1098           0 :                 if (matches_position(&znode->zbranch[nn], lnum, offs)) {
    1099           0 :                         *zn = znode;
    1100           0 :                         *n = nn;
    1101           0 :                         return 1;
    1102             :                 }
    1103             :         }
    1104             : 
    1105             :         /* Look right */
    1106           0 :         znode = *zn;
    1107           0 :         nn = *n;
    1108             :         while (1) {
    1109           0 :                 err = tnc_next(c, &znode, &nn);
    1110           0 :                 if (err == -ENOENT)
    1111             :                         return 0;
    1112           0 :                 if (err < 0)
    1113             :                         return err;
    1114           0 :                 if (keys_cmp(c, &znode->zbranch[nn].key, key))
    1115             :                         return 0;
    1116           0 :                 *zn = znode;
    1117           0 :                 *n = nn;
    1118           0 :                 if (matches_position(&znode->zbranch[nn], lnum, offs))
    1119             :                         return 1;
    1120             :         }
    1121             : }
    1122             : 
    1123             : /**
    1124             :  * dirty_cow_bottom_up - dirty a znode and its ancestors.
    1125             :  * @c: UBIFS file-system description object
    1126             :  * @znode: znode to dirty
    1127             :  *
    1128             :  * If we do not have a unique key that resides in a znode, then we cannot
    1129             :  * dirty that znode from the top down (i.e. by using lookup_level0_dirty)
    1130             :  * This function records the path back to the last dirty ancestor, and then
    1131             :  * dirties the znodes on that path.
    1132             :  */
    1133       31437 : static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c,
    1134             :                                                struct ubifs_znode *znode)
    1135             : {
    1136             :         struct ubifs_znode *zp;
    1137       31437 :         int *path = c->bottom_up_buf, p = 0;
    1138             : 
    1139       31437 :         ubifs_assert(c, c->zroot.znode);
    1140       31437 :         ubifs_assert(c, znode);
    1141       31437 :         if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) {
    1142           0 :                 kfree(c->bottom_up_buf);
    1143           0 :                 c->bottom_up_buf = kmalloc_array(c->zroot.znode->level,
    1144             :                                                  sizeof(int),
    1145             :                                                  GFP_NOFS);
    1146           0 :                 if (!c->bottom_up_buf)
    1147             :                         return ERR_PTR(-ENOMEM);
    1148             :                 path = c->bottom_up_buf;
    1149             :         }
    1150       31437 :         if (c->zroot.znode->level) {
    1151             :                 /* Go up until parent is dirty */
    1152             :                 while (1) {
    1153             :                         int n;
    1154             : 
    1155       70845 :                         zp = znode->parent;
    1156       70845 :                         if (!zp)
    1157             :                                 break;
    1158       70777 :                         n = znode->iip;
    1159       70777 :                         ubifs_assert(c, p < c->zroot.znode->level);
    1160       70777 :                         path[p++] = n;
    1161      141554 :                         if (!zp->cnext && ubifs_zn_dirty(znode))
    1162             :                                 break;
    1163             :                         znode = zp;
    1164             :                 }
    1165             :         }
    1166             : 
    1167             :         /* Come back down, dirtying as we go */
    1168       39408 :         while (1) {
    1169             :                 struct ubifs_zbranch *zbr;
    1170             : 
    1171       70845 :                 zp = znode->parent;
    1172       70845 :                 if (zp) {
    1173       70777 :                         ubifs_assert(c, path[p - 1] >= 0);
    1174       70777 :                         ubifs_assert(c, path[p - 1] < zp->child_cnt);
    1175       70777 :                         zbr = &zp->zbranch[path[--p]];
    1176       70777 :                         znode = dirty_cow_znode(c, zbr);
    1177             :                 } else {
    1178          68 :                         ubifs_assert(c, znode == c->zroot.znode);
    1179          68 :                         znode = dirty_cow_znode(c, &c->zroot);
    1180             :                 }
    1181       70845 :                 if (IS_ERR(znode) || !p)
    1182             :                         break;
    1183       39408 :                 ubifs_assert(c, path[p - 1] >= 0);
    1184       39408 :                 ubifs_assert(c, path[p - 1] < znode->child_cnt);
    1185       39408 :                 znode = znode->zbranch[path[p - 1]].znode;
    1186             :         }
    1187             : 
    1188             :         return znode;
    1189             : }
    1190             : 
    1191             : /**
    1192             :  * ubifs_lookup_level0 - search for zero-level znode.
    1193             :  * @c: UBIFS file-system description object
    1194             :  * @key:  key to lookup
    1195             :  * @zn: znode is returned here
    1196             :  * @n: znode branch slot number is returned here
    1197             :  *
    1198             :  * This function looks up the TNC tree and search for zero-level znode which
    1199             :  * refers key @key. The found zero-level znode is returned in @zn. There are 3
    1200             :  * cases:
    1201             :  *   o exact match, i.e. the found zero-level znode contains key @key, then %1
    1202             :  *     is returned and slot number of the matched branch is stored in @n;
    1203             :  *   o not exact match, which means that zero-level znode does not contain
    1204             :  *     @key, then %0 is returned and slot number of the closest branch or %-1
    1205             :  *     is stored in @n; In this case calling tnc_next() is mandatory.
    1206             :  *   o @key is so small that it is even less than the lowest key of the
    1207             :  *     leftmost zero-level node, then %0 is returned and %0 is stored in @n.
    1208             :  *
    1209             :  * Note, when the TNC tree is traversed, some znodes may be absent, then this
    1210             :  * function reads corresponding indexing nodes and inserts them to TNC. In
    1211             :  * case of failure, a negative error code is returned.
    1212             :  */
    1213  3922941336 : int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,
    1214             :                         struct ubifs_znode **zn, int *n)
    1215             : {
    1216             :         int err, exact;
    1217             :         struct ubifs_znode *znode;
    1218  3922941336 :         time64_t time = ktime_get_seconds();
    1219             : 
    1220  3922941336 :         dbg_tnck(key, "search key ");
    1221  7845882672 :         ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);
    1222             : 
    1223  3922941336 :         znode = c->zroot.znode;
    1224  3922941336 :         if (unlikely(!znode)) {
    1225           1 :                 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
    1226           2 :                 if (IS_ERR(znode))
    1227           0 :                         return PTR_ERR(znode);
    1228             :         }
    1229             : 
    1230  3922941336 :         znode->time = time;
    1231             : 
    1232             :         while (1) {
    1233             :                 struct ubifs_zbranch *zbr;
    1234             : 
    1235 37930607858 :                 exact = ubifs_search_zbranch(c, znode, key, n);
    1236             : 
    1237 37930607858 :                 if (znode->level == 0)
    1238             :                         break;
    1239             : 
    1240 34007666522 :                 if (*n < 0)
    1241   212673895 :                         *n = 0;
    1242 34007666522 :                 zbr = &znode->zbranch[*n];
    1243             : 
    1244 34007666522 :                 if (zbr->znode) {
    1245 34007546935 :                         znode->time = time;
    1246 34007546935 :                         znode = zbr->znode;
    1247 34007546935 :                         continue;
    1248             :                 }
    1249             : 
    1250             :                 /* znode is not in TNC cache, load it from the media */
    1251      119587 :                 znode = ubifs_load_znode(c, zbr, znode, *n);
    1252      239174 :                 if (IS_ERR(znode))
    1253           0 :                         return PTR_ERR(znode);
    1254             :         }
    1255             : 
    1256  3922941336 :         *zn = znode;
    1257  4666526886 :         if (exact || !is_hash_key(c, key) || *n != -1) {
    1258  3905872132 :                 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
    1259             :                 return exact;
    1260             :         }
    1261             : 
    1262             :         /*
    1263             :          * Here is a tricky place. We have not found the key and this is a
    1264             :          * "hashed" key, which may collide. The rest of the code deals with
    1265             :          * situations like this:
    1266             :          *
    1267             :          *                  | 3 | 5 |
    1268             :          *                  /       \
    1269             :          *          | 3 | 5 |      | 6 | 7 | (x)
    1270             :          *
    1271             :          * Or more a complex example:
    1272             :          *
    1273             :          *                | 1 | 5 |
    1274             :          *                /       \
    1275             :          *       | 1 | 3 |         | 5 | 8 |
    1276             :          *              \           /
    1277             :          *          | 5 | 5 |   | 6 | 7 | (x)
    1278             :          *
    1279             :          * In the examples, if we are looking for key "5", we may reach nodes
    1280             :          * marked with "(x)". In this case what we have do is to look at the
    1281             :          * left and see if there is "5" key there. If there is, we have to
    1282             :          * return it.
    1283             :          *
    1284             :          * Note, this whole situation is possible because we allow to have
    1285             :          * elements which are equivalent to the next key in the parent in the
    1286             :          * children of current znode. For example, this happens if we split a
    1287             :          * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something
    1288             :          * like this:
    1289             :          *                      | 3 | 5 |
    1290             :          *                       /     \
    1291             :          *                | 3 | 5 |   | 5 | 6 | 7 |
    1292             :          *                              ^
    1293             :          * And this becomes what is at the first "picture" after key "5" marked
    1294             :          * with "^" is removed. What could be done is we could prohibit
    1295             :          * splitting in the middle of the colliding sequence. Also, when
    1296             :          * removing the leftmost key, we would have to correct the key of the
    1297             :          * parent node, which would introduce additional complications. Namely,
    1298             :          * if we changed the leftmost key of the parent znode, the garbage
    1299             :          * collector would be unable to find it (GC is doing this when GC'ing
    1300             :          * indexing LEBs). Although we already have an additional RB-tree where
    1301             :          * we save such changed znodes (see 'ins_clr_old_idx_znode()') until
    1302             :          * after the commit. But anyway, this does not look easy to implement
    1303             :          * so we did not try this.
    1304             :          */
    1305    17069204 :         err = tnc_prev(c, &znode, n);
    1306    17069204 :         if (err == -ENOENT) {
    1307        1818 :                 dbg_tnc("found 0, lvl %d, n -1", znode->level);
    1308        1818 :                 *n = -1;
    1309        1818 :                 return 0;
    1310             :         }
    1311    17067386 :         if (unlikely(err < 0))
    1312             :                 return err;
    1313    17067386 :         if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
    1314    17067386 :                 dbg_tnc("found 0, lvl %d, n -1", znode->level);
    1315    17067386 :                 *n = -1;
    1316    17067386 :                 return 0;
    1317             :         }
    1318             : 
    1319           0 :         dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
    1320           0 :         *zn = znode;
    1321           0 :         return 1;
    1322             : }
    1323             : 
    1324             : /**
    1325             :  * lookup_level0_dirty - search for zero-level znode dirtying.
    1326             :  * @c: UBIFS file-system description object
    1327             :  * @key:  key to lookup
    1328             :  * @zn: znode is returned here
    1329             :  * @n: znode branch slot number is returned here
    1330             :  *
    1331             :  * This function looks up the TNC tree and search for zero-level znode which
    1332             :  * refers key @key. The found zero-level znode is returned in @zn. There are 3
    1333             :  * cases:
    1334             :  *   o exact match, i.e. the found zero-level znode contains key @key, then %1
    1335             :  *     is returned and slot number of the matched branch is stored in @n;
    1336             :  *   o not exact match, which means that zero-level znode does not contain @key
    1337             :  *     then %0 is returned and slot number of the closed branch is stored in
    1338             :  *     @n;
    1339             :  *   o @key is so small that it is even less than the lowest key of the
    1340             :  *     leftmost zero-level node, then %0 is returned and %-1 is stored in @n.
    1341             :  *
    1342             :  * Additionally all znodes in the path from the root to the located zero-level
    1343             :  * znode are marked as dirty.
    1344             :  *
    1345             :  * Note, when the TNC tree is traversed, some znodes may be absent, then this
    1346             :  * function reads corresponding indexing nodes and inserts them to TNC. In
    1347             :  * case of failure, a negative error code is returned.
    1348             :  */
    1349     3887467 : static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,
    1350             :                                struct ubifs_znode **zn, int *n)
    1351             : {
    1352             :         int err, exact;
    1353             :         struct ubifs_znode *znode;
    1354     3887467 :         time64_t time = ktime_get_seconds();
    1355             : 
    1356     3887467 :         dbg_tnck(key, "search and dirty key ");
    1357             : 
    1358     3887467 :         znode = c->zroot.znode;
    1359     3887467 :         if (unlikely(!znode)) {
    1360         535 :                 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
    1361        1070 :                 if (IS_ERR(znode))
    1362           0 :                         return PTR_ERR(znode);
    1363             :         }
    1364             : 
    1365     3887467 :         znode = dirty_cow_znode(c, &c->zroot);
    1366     7774934 :         if (IS_ERR(znode))
    1367           0 :                 return PTR_ERR(znode);
    1368             : 
    1369     3887467 :         znode->time = time;
    1370             : 
    1371             :         while (1) {
    1372             :                 struct ubifs_zbranch *zbr;
    1373             : 
    1374    37469354 :                 exact = ubifs_search_zbranch(c, znode, key, n);
    1375             : 
    1376    37469354 :                 if (znode->level == 0)
    1377             :                         break;
    1378             : 
    1379    33581915 :                 if (*n < 0)
    1380         287 :                         *n = 0;
    1381    33581915 :                 zbr = &znode->zbranch[*n];
    1382             : 
    1383    33581915 :                 if (zbr->znode) {
    1384    31659043 :                         znode->time = time;
    1385    31659043 :                         znode = dirty_cow_znode(c, zbr);
    1386    63318086 :                         if (IS_ERR(znode))
    1387           0 :                                 return PTR_ERR(znode);
    1388    31659043 :                         continue;
    1389             :                 }
    1390             : 
    1391             :                 /* znode is not in TNC cache, load it from the media */
    1392     1922872 :                 znode = ubifs_load_znode(c, zbr, znode, *n);
    1393     3845744 :                 if (IS_ERR(znode))
    1394          56 :                         return PTR_ERR(znode);
    1395     1922844 :                 znode = dirty_cow_znode(c, zbr);
    1396     3845688 :                 if (IS_ERR(znode))
    1397           0 :                         return PTR_ERR(znode);
    1398             :         }
    1399             : 
    1400     3887439 :         *zn = znode;
    1401     4119961 :         if (exact || !is_hash_key(c, key) || *n != -1) {
    1402     3886927 :                 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
    1403             :                 return exact;
    1404             :         }
    1405             : 
    1406             :         /*
    1407             :          * See huge comment at 'lookup_level0_dirty()' what is the rest of the
    1408             :          * code.
    1409             :          */
    1410         512 :         err = tnc_prev(c, &znode, n);
    1411         512 :         if (err == -ENOENT) {
    1412           0 :                 *n = -1;
    1413           0 :                 dbg_tnc("found 0, lvl %d, n -1", znode->level);
    1414             :                 return 0;
    1415             :         }
    1416         512 :         if (unlikely(err < 0))
    1417             :                 return err;
    1418         512 :         if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
    1419         512 :                 *n = -1;
    1420         512 :                 dbg_tnc("found 0, lvl %d, n -1", znode->level);
    1421             :                 return 0;
    1422             :         }
    1423             : 
    1424           0 :         if (znode->cnext || !ubifs_zn_dirty(znode)) {
    1425           0 :                 znode = dirty_cow_bottom_up(c, znode);
    1426           0 :                 if (IS_ERR(znode))
    1427           0 :                         return PTR_ERR(znode);
    1428             :         }
    1429             : 
    1430           0 :         dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
    1431           0 :         *zn = znode;
    1432           0 :         return 1;
    1433             : }
    1434             : 
    1435             : /**
    1436             :  * ubifs_tnc_locate - look up a file-system node and return it and its location.
    1437             :  * @c: UBIFS file-system description object
    1438             :  * @key: node key to lookup
    1439             :  * @node: the node is returned here
    1440             :  * @lnum: LEB number is returned here
    1441             :  * @offs: offset is returned here
    1442             :  *
    1443             :  * This function looks up and reads node with key @key. The caller has to make
    1444             :  * sure the @node buffer is large enough to fit the node. Returns zero in case
    1445             :  * of success, %-ENOENT if the node was not found, and a negative error code in
    1446             :  * case of failure. The node location can be returned in @lnum and @offs.
    1447             :  */
    1448       82687 : int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,
    1449             :                      void *node, int *lnum, int *offs)
    1450             : {
    1451             :         int found, n, err;
    1452             :         struct ubifs_znode *znode;
    1453             :         struct ubifs_zbranch *zt;
    1454             : 
    1455       82687 :         mutex_lock(&c->tnc_mutex);
    1456       82687 :         found = ubifs_lookup_level0(c, key, &znode, &n);
    1457       82687 :         if (!found) {
    1458             :                 err = -ENOENT;
    1459             :                 goto out;
    1460       81910 :         } else if (found < 0) {
    1461             :                 err = found;
    1462             :                 goto out;
    1463             :         }
    1464       81910 :         zt = &znode->zbranch[n];
    1465       81910 :         if (lnum) {
    1466          53 :                 *lnum = zt->lnum;
    1467          53 :                 *offs = zt->offs;
    1468             :         }
    1469      163820 :         if (is_hash_key(c, key)) {
    1470             :                 /*
    1471             :                  * In this case the leaf node cache gets used, so we pass the
    1472             :                  * address of the zbranch and keep the mutex locked
    1473             :                  */
    1474          39 :                 err = tnc_read_hashed_node(c, zt, node);
    1475          39 :                 goto out;
    1476             :         }
    1477       81871 :         err = ubifs_tnc_read_node(c, zt, node);
    1478             : 
    1479       82687 : out:
    1480       82687 :         mutex_unlock(&c->tnc_mutex);
    1481       82687 :         return err;
    1482             : }
    1483             : 
    1484             : /**
    1485             :  * do_lookup_nm- look up a "hashed" node.
    1486             :  * @c: UBIFS file-system description object
    1487             :  * @key: node key to lookup
    1488             :  * @node: the node is returned here
    1489             :  * @nm: node name
    1490             :  *
    1491             :  * This function looks up and reads a node which contains name hash in the key.
    1492             :  * Since the hash may have collisions, there may be many nodes with the same
    1493             :  * key, so we have to sequentially look to all of them until the needed one is
    1494             :  * found. This function returns zero in case of success, %-ENOENT if the node
    1495             :  * was not found, and a negative error code in case of failure.
    1496             :  */
    1497           0 : static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
    1498             :                         void *node, const struct fscrypt_name *nm)
    1499             : {
    1500             :         int found, n, err;
    1501             :         struct ubifs_znode *znode;
    1502             : 
    1503           0 :         dbg_tnck(key, "key ");
    1504           0 :         mutex_lock(&c->tnc_mutex);
    1505           0 :         found = ubifs_lookup_level0(c, key, &znode, &n);
    1506           0 :         if (!found) {
    1507             :                 err = -ENOENT;
    1508             :                 goto out_unlock;
    1509           0 :         } else if (found < 0) {
    1510             :                 err = found;
    1511             :                 goto out_unlock;
    1512             :         }
    1513             : 
    1514           0 :         ubifs_assert(c, n >= 0);
    1515             : 
    1516           0 :         err = resolve_collision(c, key, &znode, &n, nm);
    1517           0 :         dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
    1518           0 :         if (unlikely(err < 0))
    1519             :                 goto out_unlock;
    1520           0 :         if (err == 0) {
    1521             :                 err = -ENOENT;
    1522             :                 goto out_unlock;
    1523             :         }
    1524             : 
    1525           0 :         err = tnc_read_hashed_node(c, &znode->zbranch[n], node);
    1526             : 
    1527           0 : out_unlock:
    1528           0 :         mutex_unlock(&c->tnc_mutex);
    1529           0 :         return err;
    1530             : }
    1531             : 
    1532             : /**
    1533             :  * ubifs_tnc_lookup_nm - look up a "hashed" node.
    1534             :  * @c: UBIFS file-system description object
    1535             :  * @key: node key to lookup
    1536             :  * @node: the node is returned here
    1537             :  * @nm: node name
    1538             :  *
    1539             :  * This function looks up and reads a node which contains name hash in the key.
    1540             :  * Since the hash may have collisions, there may be many nodes with the same
    1541             :  * key, so we have to sequentially look to all of them until the needed one is
    1542             :  * found. This function returns zero in case of success, %-ENOENT if the node
    1543             :  * was not found, and a negative error code in case of failure.
    1544             :  */
    1545         271 : int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
    1546             :                         void *node, const struct fscrypt_name *nm)
    1547             : {
    1548             :         int err, len;
    1549         271 :         const struct ubifs_dent_node *dent = node;
    1550             : 
    1551             :         /*
    1552             :          * We assume that in most of the cases there are no name collisions and
    1553             :          * 'ubifs_tnc_lookup()' returns us the right direntry.
    1554             :          */
    1555         271 :         err = ubifs_tnc_lookup(c, key, node);
    1556         271 :         if (err)
    1557             :                 return err;
    1558             : 
    1559          39 :         len = le16_to_cpu(dent->nlen);
    1560          39 :         if (fname_len(nm) == len && !memcmp(dent->name, fname_name(nm), len))
    1561             :                 return 0;
    1562             : 
    1563             :         /*
    1564             :          * Unluckily, there are hash collisions and we have to iterate over
    1565             :          * them look at each direntry with colliding name hash sequentially.
    1566             :          */
    1567             : 
    1568           0 :         return do_lookup_nm(c, key, node, nm);
    1569             : }
    1570             : 
    1571             : /**
    1572             :  * correct_parent_keys - correct parent znodes' keys.
    1573             :  * @c: UBIFS file-system description object
    1574             :  * @znode: znode to correct parent znodes for
    1575             :  *
    1576             :  * This is a helper function for 'tnc_insert()'. When the key of the leftmost
    1577             :  * zbranch changes, keys of parent znodes have to be corrected. This helper
    1578             :  * function is called in such situations and corrects the keys if needed.
    1579             :  */
    1580         589 : static void correct_parent_keys(const struct ubifs_info *c,
    1581             :                                 struct ubifs_znode *znode)
    1582             : {
    1583             :         union ubifs_key *key, *key1;
    1584             : 
    1585         589 :         ubifs_assert(c, znode->parent);
    1586         589 :         ubifs_assert(c, znode->iip == 0);
    1587             : 
    1588         589 :         key = &znode->zbranch[0].key;
    1589         589 :         key1 = &znode->parent->zbranch[0].key;
    1590             : 
    1591        1304 :         while (keys_cmp(c, key, key1) < 0) {
    1592         566 :                 key_copy(c, key, key1);
    1593         283 :                 znode = znode->parent;
    1594         283 :                 znode->alt = 1;
    1595         283 :                 if (!znode->parent || znode->iip)
    1596             :                         break;
    1597         126 :                 key1 = &znode->parent->zbranch[0].key;
    1598             :         }
    1599         589 : }
    1600             : 
    1601             : /**
    1602             :  * insert_zbranch - insert a zbranch into a znode.
    1603             :  * @c: UBIFS file-system description object
    1604             :  * @znode: znode into which to insert
    1605             :  * @zbr: zbranch to insert
    1606             :  * @n: slot number to insert to
    1607             :  *
    1608             :  * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in
    1609             :  * znode's array of zbranches and keeps zbranches consolidated, so when a new
    1610             :  * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
    1611             :  * slot, zbranches starting from @n have to be moved right.
    1612             :  */
    1613      624633 : static void insert_zbranch(struct ubifs_info *c, struct ubifs_znode *znode,
    1614             :                            const struct ubifs_zbranch *zbr, int n)
    1615             : {
    1616             :         int i;
    1617             : 
    1618      624633 :         ubifs_assert(c, ubifs_zn_dirty(znode));
    1619             : 
    1620      624633 :         if (znode->level) {
    1621      267405 :                 for (i = znode->child_cnt; i > n; i--) {
    1622      119379 :                         znode->zbranch[i] = znode->zbranch[i - 1];
    1623      119379 :                         if (znode->zbranch[i].znode)
    1624       18945 :                                 znode->zbranch[i].znode->iip = i;
    1625             :                 }
    1626       74013 :                 if (zbr->znode)
    1627       74013 :                         zbr->znode->iip = n;
    1628             :         } else
    1629     1339160 :                 for (i = znode->child_cnt; i > n; i--)
    1630      788540 :                         znode->zbranch[i] = znode->zbranch[i - 1];
    1631             : 
    1632      624633 :         znode->zbranch[n] = *zbr;
    1633      624633 :         znode->child_cnt += 1;
    1634             : 
    1635             :         /*
    1636             :          * After inserting at slot zero, the lower bound of the key range of
    1637             :          * this znode may have changed. If this znode is subsequently split
    1638             :          * then the upper bound of the key range may change, and furthermore
    1639             :          * it could change to be lower than the original lower bound. If that
    1640             :          * happens, then it will no longer be possible to find this znode in the
    1641             :          * TNC using the key from the index node on flash. That is bad because
    1642             :          * if it is not found, we will assume it is obsolete and may overwrite
    1643             :          * it. Then if there is an unclean unmount, we will start using the
    1644             :          * old index which will be broken.
    1645             :          *
    1646             :          * So we first mark znodes that have insertions at slot zero, and then
    1647             :          * if they are split we add their lnum/offs to the old_idx tree.
    1648             :          */
    1649      624633 :         if (n == 0)
    1650       24314 :                 znode->alt = 1;
    1651      624633 : }
    1652             : 
    1653             : /**
    1654             :  * tnc_insert - insert a node into TNC.
    1655             :  * @c: UBIFS file-system description object
    1656             :  * @znode: znode to insert into
    1657             :  * @zbr: branch to insert
    1658             :  * @n: slot number to insert new zbranch to
    1659             :  *
    1660             :  * This function inserts a new node described by @zbr into znode @znode. If
    1661             :  * znode does not have a free slot for new zbranch, it is split. Parent znodes
    1662             :  * are splat as well if needed. Returns zero in case of success or a negative
    1663             :  * error code in case of failure.
    1664             :  */
    1665      550620 : static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,
    1666             :                       struct ubifs_zbranch *zbr, int n)
    1667             : {
    1668             :         struct ubifs_znode *zn, *zi, *zp;
    1669      550620 :         int i, keep, move, appending = 0;
    1670      550620 :         union ubifs_key *key = &zbr->key, *key1;
    1671             : 
    1672      550620 :         ubifs_assert(c, n >= 0 && n <= c->fanout);
    1673             : 
    1674             :         /* Implement naive insert for now */
    1675      550620 : again:
    1676      624633 :         zp = znode->parent;
    1677      624633 :         if (znode->child_cnt < c->fanout) {
    1678      550620 :                 ubifs_assert(c, n != c->fanout);
    1679      550620 :                 dbg_tnck(key, "inserted at %d level %d, key ", n, znode->level);
    1680             : 
    1681      550620 :                 insert_zbranch(c, znode, zbr, n);
    1682             : 
    1683             :                 /* Ensure parent's key is correct */
    1684      550620 :                 if (n == 0 && zp && znode->iip == 0)
    1685         552 :                         correct_parent_keys(c, znode);
    1686             : 
    1687             :                 return 0;
    1688             :         }
    1689             : 
    1690             :         /*
    1691             :          * Unfortunately, @znode does not have more empty slots and we have to
    1692             :          * split it.
    1693             :          */
    1694       74013 :         dbg_tnck(key, "splitting level %d, key ", znode->level);
    1695             : 
    1696       74013 :         if (znode->alt)
    1697             :                 /*
    1698             :                  * We can no longer be sure of finding this znode by key, so we
    1699             :                  * record it in the old_idx tree.
    1700             :                  */
    1701       12820 :                 ins_clr_old_idx_znode(c, znode);
    1702             : 
    1703      148026 :         zn = kzalloc(c->max_znode_sz, GFP_NOFS);
    1704       74013 :         if (!zn)
    1705             :                 return -ENOMEM;
    1706       74013 :         zn->parent = zp;
    1707       74013 :         zn->level = znode->level;
    1708             : 
    1709             :         /* Decide where to split */
    1710      136092 :         if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
    1711             :                 /* Try not to split consecutive data keys */
    1712       32129 :                 if (n == c->fanout) {
    1713       16276 :                         key1 = &znode->zbranch[n - 1].key;
    1714       65096 :                         if (key_inum(c, key1) == key_inum(c, key) &&
    1715       16268 :                             key_type(c, key1) == UBIFS_DATA_KEY)
    1716             :                                 appending = 1;
    1717             :                 } else
    1718             :                         goto check_split;
    1719       41884 :         } else if (appending && n != c->fanout) {
    1720             :                 /* Try not to split consecutive data keys */
    1721             :                 appending = 0;
    1722       33591 : check_split:
    1723       17738 :                 if (n >= (c->fanout + 1) / 2) {
    1724       16543 :                         key1 = &znode->zbranch[0].key;
    1725       63600 :                         if (key_inum(c, key1) == key_inum(c, key) &&
    1726       13971 :                             key_type(c, key1) == UBIFS_DATA_KEY) {
    1727       12829 :                                 key1 = &znode->zbranch[n].key;
    1728       50496 :                                 if (key_inum(c, key1) != key_inum(c, key) ||
    1729       12009 :                                     key_type(c, key1) != UBIFS_DATA_KEY) {
    1730        2293 :                                         keep = n;
    1731        2293 :                                         move = c->fanout - keep;
    1732        2293 :                                         zi = znode;
    1733        2293 :                                         goto do_split;
    1734             :                                 }
    1735             :                         }
    1736             :                 }
    1737             :         }
    1738             : 
    1739       55495 :         if (appending) {
    1740       17147 :                 keep = c->fanout;
    1741       17147 :                 move = 0;
    1742             :         } else {
    1743       54573 :                 keep = (c->fanout + 1) / 2;
    1744       54573 :                 move = c->fanout - keep;
    1745             :         }
    1746             : 
    1747             :         /*
    1748             :          * Although we don't at present, we could look at the neighbors and see
    1749             :          * if we can move some zbranches there.
    1750             :          */
    1751             : 
    1752       71720 :         if (n < keep) {
    1753             :                 /* Insert into existing znode */
    1754       13608 :                 zi = znode;
    1755       13608 :                 move += 1;
    1756       13608 :                 keep -= 1;
    1757             :         } else {
    1758             :                 /* Insert into new znode */
    1759       58112 :                 zi = zn;
    1760       58112 :                 n -= keep;
    1761             :                 /* Re-parent */
    1762       58112 :                 if (zn->level != 0)
    1763        8692 :                         zbr->znode->parent = zn;
    1764             :         }
    1765             : 
    1766      123433 : do_split:
    1767             : 
    1768      148026 :         __set_bit(DIRTY_ZNODE, &zn->flags);
    1769      148026 :         atomic_long_inc(&c->dirty_zn_cnt);
    1770             : 
    1771       74013 :         zn->child_cnt = move;
    1772       74013 :         znode->child_cnt = keep;
    1773             : 
    1774       74013 :         dbg_tnc("moving %d, keeping %d", move, keep);
    1775             : 
    1776             :         /* Move zbranch */
    1777      236574 :         for (i = 0; i < move; i++) {
    1778      236574 :                 zn->zbranch[i] = znode->zbranch[keep + i];
    1779             :                 /* Re-parent */
    1780      236574 :                 if (zn->level != 0)
    1781       46030 :                         if (zn->zbranch[i].znode) {
    1782       17312 :                                 zn->zbranch[i].znode->parent = zn;
    1783       17312 :                                 zn->zbranch[i].znode->iip = i;
    1784             :                         }
    1785             :         }
    1786             : 
    1787             :         /* Insert new key and branch */
    1788       74013 :         dbg_tnck(key, "inserting at %d level %d, key ", n, zn->level);
    1789             : 
    1790       74013 :         insert_zbranch(c, zi, zbr, n);
    1791             : 
    1792             :         /* Insert new znode (produced by spitting) into the parent */
    1793       74013 :         if (zp) {
    1794       74013 :                 if (n == 0 && zi == znode && znode->iip == 0)
    1795          37 :                         correct_parent_keys(c, znode);
    1796             : 
    1797             :                 /* Locate insertion point */
    1798       74013 :                 n = znode->iip + 1;
    1799             : 
    1800             :                 /* Tail recursion */
    1801       74013 :                 zbr->key = zn->zbranch[0].key;
    1802       74013 :                 zbr->znode = zn;
    1803       74013 :                 zbr->lnum = 0;
    1804       74013 :                 zbr->offs = 0;
    1805       74013 :                 zbr->len = 0;
    1806       74013 :                 znode = zp;
    1807             : 
    1808       74013 :                 goto again;
    1809             :         }
    1810             : 
    1811             :         /* We have to split root znode */
    1812           0 :         dbg_tnc("creating new zroot at level %d", znode->level + 1);
    1813             : 
    1814           0 :         zi = kzalloc(c->max_znode_sz, GFP_NOFS);
    1815           0 :         if (!zi)
    1816             :                 return -ENOMEM;
    1817             : 
    1818           0 :         zi->child_cnt = 2;
    1819           0 :         zi->level = znode->level + 1;
    1820             : 
    1821           0 :         __set_bit(DIRTY_ZNODE, &zi->flags);
    1822           0 :         atomic_long_inc(&c->dirty_zn_cnt);
    1823             : 
    1824           0 :         zi->zbranch[0].key = znode->zbranch[0].key;
    1825           0 :         zi->zbranch[0].znode = znode;
    1826           0 :         zi->zbranch[0].lnum = c->zroot.lnum;
    1827           0 :         zi->zbranch[0].offs = c->zroot.offs;
    1828           0 :         zi->zbranch[0].len = c->zroot.len;
    1829           0 :         zi->zbranch[1].key = zn->zbranch[0].key;
    1830           0 :         zi->zbranch[1].znode = zn;
    1831             : 
    1832           0 :         c->zroot.lnum = 0;
    1833           0 :         c->zroot.offs = 0;
    1834           0 :         c->zroot.len = 0;
    1835           0 :         c->zroot.znode = zi;
    1836             : 
    1837           0 :         zn->parent = zi;
    1838           0 :         zn->iip = 1;
    1839           0 :         znode->parent = zi;
    1840           0 :         znode->iip = 0;
    1841             : 
    1842           0 :         return 0;
    1843             : }
    1844             : 
    1845             : /**
    1846             :  * ubifs_tnc_add - add a node to TNC.
    1847             :  * @c: UBIFS file-system description object
    1848             :  * @key: key to add
    1849             :  * @lnum: LEB number of node
    1850             :  * @offs: node offset
    1851             :  * @len: node length
    1852             :  * @hash: The hash over the node
    1853             :  *
    1854             :  * This function adds a node with key @key to TNC. The node may be new or it may
    1855             :  * obsolete some existing one. Returns %0 on success or negative error code on
    1856             :  * failure.
    1857             :  */
    1858     2784222 : int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,
    1859             :                   int offs, int len, const u8 *hash)
    1860             : {
    1861     2784222 :         int found, n, err = 0;
    1862             :         struct ubifs_znode *znode;
    1863             : 
    1864     2784222 :         mutex_lock(&c->tnc_mutex);
    1865     2784222 :         dbg_tnck(key, "%d:%d, len %d, key ", lnum, offs, len);
    1866     2784222 :         found = lookup_level0_dirty(c, key, &znode, &n);
    1867     2784222 :         if (!found) {
    1868             :                 struct ubifs_zbranch zbr;
    1869             : 
    1870      211355 :                 zbr.znode = NULL;
    1871      211355 :                 zbr.lnum = lnum;
    1872      211355 :                 zbr.offs = offs;
    1873      211355 :                 zbr.len = len;
    1874      211355 :                 ubifs_copy_hash(c, hash, zbr.hash);
    1875      422710 :                 key_copy(c, key, &zbr.key);
    1876      211355 :                 err = tnc_insert(c, znode, &zbr, n + 1);
    1877     2572867 :         } else if (found == 1) {
    1878     2572859 :                 struct ubifs_zbranch *zbr = &znode->zbranch[n];
    1879             : 
    1880     2572859 :                 lnc_free(zbr);
    1881     5145718 :                 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
    1882     2572859 :                 zbr->lnum = lnum;
    1883     2572859 :                 zbr->offs = offs;
    1884     2572859 :                 zbr->len = len;
    1885     2572859 :                 ubifs_copy_hash(c, hash, zbr->hash);
    1886             :         } else
    1887             :                 err = found;
    1888     2784222 :         if (!err)
    1889     2784214 :                 err = dbg_check_tnc(c, 0);
    1890     2784222 :         mutex_unlock(&c->tnc_mutex);
    1891             : 
    1892     2784222 :         return err;
    1893             : }
    1894             : 
    1895             : /**
    1896             :  * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
    1897             :  * @c: UBIFS file-system description object
    1898             :  * @key: key to add
    1899             :  * @old_lnum: LEB number of old node
    1900             :  * @old_offs: old node offset
    1901             :  * @lnum: LEB number of node
    1902             :  * @offs: node offset
    1903             :  * @len: node length
    1904             :  *
    1905             :  * This function replaces a node with key @key in the TNC only if the old node
    1906             :  * is found.  This function is called by garbage collection when node are moved.
    1907             :  * Returns %0 on success or negative error code on failure.
    1908             :  */
    1909        5468 : int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,
    1910             :                       int old_lnum, int old_offs, int lnum, int offs, int len)
    1911             : {
    1912        5468 :         int found, n, err = 0;
    1913             :         struct ubifs_znode *znode;
    1914             : 
    1915        5468 :         mutex_lock(&c->tnc_mutex);
    1916        5468 :         dbg_tnck(key, "old LEB %d:%d, new LEB %d:%d, len %d, key ", old_lnum,
    1917             :                  old_offs, lnum, offs, len);
    1918        5468 :         found = lookup_level0_dirty(c, key, &znode, &n);
    1919        5468 :         if (found < 0) {
    1920             :                 err = found;
    1921             :                 goto out_unlock;
    1922             :         }
    1923             : 
    1924        5468 :         if (found == 1) {
    1925        5468 :                 struct ubifs_zbranch *zbr = &znode->zbranch[n];
    1926             : 
    1927        5468 :                 found = 0;
    1928        5468 :                 if (zbr->lnum == old_lnum && zbr->offs == old_offs) {
    1929        5468 :                         lnc_free(zbr);
    1930       10936 :                         err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
    1931        5468 :                         if (err)
    1932             :                                 goto out_unlock;
    1933        5468 :                         zbr->lnum = lnum;
    1934        5468 :                         zbr->offs = offs;
    1935        5468 :                         zbr->len = len;
    1936        5468 :                         found = 1;
    1937           0 :                 } else if (is_hash_key(c, key)) {
    1938           0 :                         found = resolve_collision_directly(c, key, &znode, &n,
    1939             :                                                            old_lnum, old_offs);
    1940           0 :                         dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",
    1941             :                                 found, znode, n, old_lnum, old_offs);
    1942           0 :                         if (found < 0) {
    1943             :                                 err = found;
    1944             :                                 goto out_unlock;
    1945             :                         }
    1946             : 
    1947           0 :                         if (found) {
    1948             :                                 /* Ensure the znode is dirtied */
    1949           0 :                                 if (znode->cnext || !ubifs_zn_dirty(znode)) {
    1950           0 :                                         znode = dirty_cow_bottom_up(c, znode);
    1951           0 :                                         if (IS_ERR(znode)) {
    1952           0 :                                                 err = PTR_ERR(znode);
    1953           0 :                                                 goto out_unlock;
    1954             :                                         }
    1955             :                                 }
    1956           0 :                                 zbr = &znode->zbranch[n];
    1957           0 :                                 lnc_free(zbr);
    1958           0 :                                 err = ubifs_add_dirt(c, zbr->lnum,
    1959             :                                                      zbr->len);
    1960           0 :                                 if (err)
    1961             :                                         goto out_unlock;
    1962           0 :                                 zbr->lnum = lnum;
    1963           0 :                                 zbr->offs = offs;
    1964           0 :                                 zbr->len = len;
    1965             :                         }
    1966             :                 }
    1967             :         }
    1968             : 
    1969           0 :         if (!found)
    1970           0 :                 err = ubifs_add_dirt(c, lnum, len);
    1971             : 
    1972        5468 :         if (!err)
    1973        5468 :                 err = dbg_check_tnc(c, 0);
    1974             : 
    1975        5468 : out_unlock:
    1976        5468 :         mutex_unlock(&c->tnc_mutex);
    1977        5468 :         return err;
    1978             : }
    1979             : 
    1980             : /**
    1981             :  * ubifs_tnc_add_nm - add a "hashed" node to TNC.
    1982             :  * @c: UBIFS file-system description object
    1983             :  * @key: key to add
    1984             :  * @lnum: LEB number of node
    1985             :  * @offs: node offset
    1986             :  * @len: node length
    1987             :  * @hash: The hash over the node
    1988             :  * @nm: node name
    1989             :  *
    1990             :  * This is the same as 'ubifs_tnc_add()' but it should be used with keys which
    1991             :  * may have collisions, like directory entry keys.
    1992             :  */
    1993      350288 : int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
    1994             :                      int lnum, int offs, int len, const u8 *hash,
    1995             :                      const struct fscrypt_name *nm)
    1996             : {
    1997      350288 :         int found, n, err = 0;
    1998             :         struct ubifs_znode *znode;
    1999             : 
    2000      350288 :         mutex_lock(&c->tnc_mutex);
    2001      350288 :         dbg_tnck(key, "LEB %d:%d, key ", lnum, offs);
    2002      350288 :         found = lookup_level0_dirty(c, key, &znode, &n);
    2003      350288 :         if (found < 0) {
    2004             :                 err = found;
    2005             :                 goto out_unlock;
    2006             :         }
    2007             : 
    2008      350288 :         if (found == 1) {
    2009      329833 :                 if (c->replaying)
    2010      329833 :                         found = fallible_resolve_collision(c, key, &znode, &n,
    2011             :                                                            nm, 1);
    2012             :                 else
    2013           0 :                         found = resolve_collision(c, key, &znode, &n, nm);
    2014      329833 :                 dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n);
    2015      329833 :                 if (found < 0) {
    2016             :                         err = found;
    2017             :                         goto out_unlock;
    2018             :                 }
    2019             : 
    2020             :                 /* Ensure the znode is dirtied */
    2021      659666 :                 if (znode->cnext || !ubifs_zn_dirty(znode)) {
    2022           0 :                         znode = dirty_cow_bottom_up(c, znode);
    2023           0 :                         if (IS_ERR(znode)) {
    2024           0 :                                 err = PTR_ERR(znode);
    2025           0 :                                 goto out_unlock;
    2026             :                         }
    2027             :                 }
    2028             : 
    2029      329833 :                 if (found == 1) {
    2030       11023 :                         struct ubifs_zbranch *zbr = &znode->zbranch[n];
    2031             : 
    2032       11023 :                         lnc_free(zbr);
    2033       22046 :                         err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
    2034       11023 :                         zbr->lnum = lnum;
    2035       11023 :                         zbr->offs = offs;
    2036       11023 :                         zbr->len = len;
    2037       11023 :                         ubifs_copy_hash(c, hash, zbr->hash);
    2038             :                         goto out_unlock;
    2039             :                 }
    2040             :         }
    2041             : 
    2042      339265 :         if (!found) {
    2043             :                 struct ubifs_zbranch zbr;
    2044             : 
    2045      339265 :                 zbr.znode = NULL;
    2046      339265 :                 zbr.lnum = lnum;
    2047      339265 :                 zbr.offs = offs;
    2048      339265 :                 zbr.len = len;
    2049      339265 :                 ubifs_copy_hash(c, hash, zbr.hash);
    2050      678530 :                 key_copy(c, key, &zbr.key);
    2051      339265 :                 err = tnc_insert(c, znode, &zbr, n + 1);
    2052      339265 :                 if (err)
    2053             :                         goto out_unlock;
    2054      339265 :                 if (c->replaying) {
    2055             :                         /*
    2056             :                          * We did not find it in the index so there may be a
    2057             :                          * dangling branch still in the index. So we remove it
    2058             :                          * by passing 'ubifs_tnc_remove_nm()' the same key but
    2059             :                          * an unmatchable name.
    2060             :                          */
    2061      339033 :                         struct fscrypt_name noname = { .disk_name = { .name = "", .len = 1 } };
    2062             : 
    2063      339033 :                         err = dbg_check_tnc(c, 0);
    2064      339033 :                         mutex_unlock(&c->tnc_mutex);
    2065             :                         if (err)
    2066             :                                 return err;
    2067      339033 :                         return ubifs_tnc_remove_nm(c, key, &noname);
    2068             :                 }
    2069             :         }
    2070             : 
    2071       11255 : out_unlock:
    2072       11255 :         if (!err)
    2073             :                 err = dbg_check_tnc(c, 0);
    2074       11255 :         mutex_unlock(&c->tnc_mutex);
    2075       11255 :         return err;
    2076             : }
    2077             : 
    2078             : /**
    2079             :  * tnc_delete - delete a znode form TNC.
    2080             :  * @c: UBIFS file-system description object
    2081             :  * @znode: znode to delete from
    2082             :  * @n: zbranch slot number to delete
    2083             :  *
    2084             :  * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
    2085             :  * case of success and a negative error code in case of failure.
    2086             :  */
    2087      765529 : static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
    2088             : {
    2089             :         struct ubifs_zbranch *zbr;
    2090             :         struct ubifs_znode *zp;
    2091             :         int i, err;
    2092             : 
    2093             :         /* Delete without merge for now */
    2094      765529 :         ubifs_assert(c, znode->level == 0);
    2095      765529 :         ubifs_assert(c, n >= 0 && n < c->fanout);
    2096      765529 :         dbg_tnck(&znode->zbranch[n].key, "deleting key ");
    2097             : 
    2098      765529 :         zbr = &znode->zbranch[n];
    2099      765529 :         lnc_free(zbr);
    2100             : 
    2101     1531058 :         err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
    2102      765529 :         if (err) {
    2103           0 :                 ubifs_dump_znode(c, znode);
    2104           0 :                 return err;
    2105             :         }
    2106             : 
    2107             :         /* We do not "gap" zbranch slots */
    2108     1412297 :         for (i = n; i < znode->child_cnt - 1; i++)
    2109     1412297 :                 znode->zbranch[i] = znode->zbranch[i + 1];
    2110      765529 :         znode->child_cnt -= 1;
    2111             : 
    2112      765529 :         if (znode->child_cnt > 0)
    2113             :                 return 0;
    2114             : 
    2115             :         /* Different with linux kernel, TNC could become empty. */
    2116       90080 :         if (!znode->parent)
    2117             :                 return 0;
    2118             : 
    2119             :         /*
    2120             :          * This was the last zbranch, we have to delete this znode from the
    2121             :          * parent.
    2122             :          */
    2123             : 
    2124             :         do {
    2125      110689 :                 ubifs_assert(c, !ubifs_zn_obsolete(znode));
    2126      110689 :                 ubifs_assert(c, ubifs_zn_dirty(znode));
    2127             : 
    2128      110689 :                 zp = znode->parent;
    2129      110689 :                 n = znode->iip;
    2130             : 
    2131      221378 :                 atomic_long_dec(&c->dirty_zn_cnt);
    2132             : 
    2133      110689 :                 err = insert_old_idx_znode(c, znode);
    2134      110689 :                 if (err)
    2135             :                         return err;
    2136             : 
    2137      110689 :                 if (znode->cnext) {
    2138           0 :                         __set_bit(OBSOLETE_ZNODE, &znode->flags);
    2139           0 :                         atomic_long_inc(&c->clean_zn_cnt);
    2140             :                         atomic_long_inc(&ubifs_clean_zn_cnt);
    2141             :                 } else
    2142             :                         kfree(znode);
    2143      110689 :                 znode = zp;
    2144      110689 :         } while (znode->child_cnt == 1); /* while removing last child */
    2145             : 
    2146             :         /* Remove from znode, entry n - 1 */
    2147       90074 :         znode->child_cnt -= 1;
    2148       90074 :         ubifs_assert(c, znode->level != 0);
    2149      294767 :         for (i = n; i < znode->child_cnt; i++) {
    2150      204693 :                 znode->zbranch[i] = znode->zbranch[i + 1];
    2151      204693 :                 if (znode->zbranch[i].znode)
    2152      104670 :                         znode->zbranch[i].znode->iip = i;
    2153             :         }
    2154             : 
    2155             :         /*
    2156             :          * If this is the root and it has only 1 child then
    2157             :          * collapse the tree.
    2158             :          */
    2159       90074 :         if (!znode->parent) {
    2160          52 :                 while (znode->child_cnt == 1 && znode->level != 0) {
    2161           6 :                         zp = znode;
    2162           6 :                         zbr = &znode->zbranch[0];
    2163           6 :                         znode = get_znode(c, znode, 0);
    2164           6 :                         if (IS_ERR(znode))
    2165           0 :                                 return PTR_ERR(znode);
    2166           6 :                         znode = dirty_cow_znode(c, zbr);
    2167           6 :                         if (IS_ERR(znode))
    2168           0 :                                 return PTR_ERR(znode);
    2169           6 :                         znode->parent = NULL;
    2170           6 :                         znode->iip = 0;
    2171           6 :                         if (c->zroot.len) {
    2172           6 :                                 err = insert_old_idx(c, c->zroot.lnum,
    2173             :                                                      c->zroot.offs);
    2174           6 :                                 if (err)
    2175             :                                         return err;
    2176             :                         }
    2177           6 :                         c->zroot.lnum = zbr->lnum;
    2178           6 :                         c->zroot.offs = zbr->offs;
    2179           6 :                         c->zroot.len = zbr->len;
    2180           6 :                         c->zroot.znode = znode;
    2181           6 :                         ubifs_assert(c, !ubifs_zn_obsolete(zp));
    2182           6 :                         ubifs_assert(c, ubifs_zn_dirty(zp));
    2183          12 :                         atomic_long_dec(&c->dirty_zn_cnt);
    2184             : 
    2185           6 :                         if (zp->cnext) {
    2186           0 :                                 __set_bit(OBSOLETE_ZNODE, &zp->flags);
    2187           0 :                                 atomic_long_inc(&c->clean_zn_cnt);
    2188             :                                 atomic_long_inc(&ubifs_clean_zn_cnt);
    2189             :                         } else
    2190             :                                 kfree(zp);
    2191             :                 }
    2192             :         }
    2193             : 
    2194             :         return 0;
    2195             : }
    2196             : 
    2197             : /**
    2198             :  * ubifs_tnc_remove - remove an index entry of a node.
    2199             :  * @c: UBIFS file-system description object
    2200             :  * @key: key of node
    2201             :  *
    2202             :  * Returns %0 on success or negative error code on failure.
    2203             :  */
    2204           0 : int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)
    2205             : {
    2206           0 :         int found, n, err = 0;
    2207             :         struct ubifs_znode *znode;
    2208             : 
    2209           0 :         mutex_lock(&c->tnc_mutex);
    2210           0 :         dbg_tnck(key, "key ");
    2211           0 :         found = lookup_level0_dirty(c, key, &znode, &n);
    2212           0 :         if (found < 0) {
    2213             :                 err = found;
    2214             :                 goto out_unlock;
    2215             :         }
    2216           0 :         if (found == 1)
    2217           0 :                 err = tnc_delete(c, znode, n);
    2218           0 :         if (!err)
    2219             :                 err = dbg_check_tnc(c, 0);
    2220             : 
    2221           0 : out_unlock:
    2222           0 :         mutex_unlock(&c->tnc_mutex);
    2223           0 :         return err;
    2224             : }
    2225             : 
    2226             : /**
    2227             :  * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
    2228             :  * @c: UBIFS file-system description object
    2229             :  * @key: key of node
    2230             :  * @nm: directory entry name
    2231             :  *
    2232             :  * Returns %0 on success or negative error code on failure.
    2233             :  */
    2234      346835 : int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,
    2235             :                         const struct fscrypt_name *nm)
    2236             : {
    2237             :         int n, err;
    2238             :         struct ubifs_znode *znode;
    2239             : 
    2240      346835 :         mutex_lock(&c->tnc_mutex);
    2241      346835 :         dbg_tnck(key, "key ");
    2242      346835 :         err = lookup_level0_dirty(c, key, &znode, &n);
    2243      346835 :         if (err < 0)
    2244             :                 goto out_unlock;
    2245             : 
    2246      346815 :         if (err) {
    2247      346103 :                 if (c->replaying)
    2248      346103 :                         err = fallible_resolve_collision(c, key, &znode, &n,
    2249             :                                                          nm, 0);
    2250             :                 else
    2251           0 :                         err = resolve_collision(c, key, &znode, &n, nm);
    2252      346103 :                 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
    2253      346103 :                 if (err < 0)
    2254             :                         goto out_unlock;
    2255      346103 :                 if (err) {
    2256             :                         /* Ensure the znode is dirtied */
    2257      651702 :                         if (znode->cnext || !ubifs_zn_dirty(znode)) {
    2258           0 :                                 znode = dirty_cow_bottom_up(c, znode);
    2259           0 :                                 if (IS_ERR(znode)) {
    2260           0 :                                         err = PTR_ERR(znode);
    2261           0 :                                         goto out_unlock;
    2262             :                                 }
    2263             :                         }
    2264      325851 :                         err = tnc_delete(c, znode, n);
    2265             :                 }
    2266             :         }
    2267             : 
    2268      367819 : out_unlock:
    2269      346835 :         if (!err)
    2270      346815 :                 err = dbg_check_tnc(c, 0);
    2271      346835 :         mutex_unlock(&c->tnc_mutex);
    2272      346835 :         return err;
    2273             : }
    2274             : 
    2275             : /**
    2276             :  * key_in_range - determine if a key falls within a range of keys.
    2277             :  * @c: UBIFS file-system description object
    2278             :  * @key: key to check
    2279             :  * @from_key: lowest key in range
    2280             :  * @to_key: highest key in range
    2281             :  *
    2282             :  * This function returns %1 if the key is in range and %0 otherwise.
    2283             :  */
    2284             : static int key_in_range(struct ubifs_info *c, union ubifs_key *key,
    2285             :                         union ubifs_key *from_key, union ubifs_key *to_key)
    2286             : {
    2287      249555 :         if (keys_cmp(c, key, from_key) < 0)
    2288             :                 return 0;
    2289      249555 :         if (keys_cmp(c, key, to_key) > 0)
    2290             :                 return 0;
    2291             :         return 1;
    2292             : }
    2293             : 
    2294             : /**
    2295             :  * ubifs_tnc_remove_range - remove index entries in range.
    2296             :  * @c: UBIFS file-system description object
    2297             :  * @from_key: lowest key to remove
    2298             :  * @to_key: highest key to remove
    2299             :  *
    2300             :  * This function removes index entries starting at @from_key and ending at
    2301             :  * @to_key.  This function returns zero in case of success and a negative error
    2302             :  * code in case of failure.
    2303             :  */
    2304        9107 : int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,
    2305             :                            union ubifs_key *to_key)
    2306             : {
    2307        9107 :         int i, n, k, err = 0;
    2308             :         struct ubifs_znode *znode;
    2309             :         union ubifs_key *key;
    2310             : 
    2311        9107 :         mutex_lock(&c->tnc_mutex);
    2312             :         while (1) {
    2313             :                 /* Find first level 0 znode that contains keys to remove */
    2314       48131 :                 err = ubifs_lookup_level0(c, from_key, &znode, &n);
    2315       48131 :                 if (err < 0)
    2316             :                         goto out_unlock;
    2317             : 
    2318       48131 :                 if (err)
    2319             :                         key = from_key;
    2320             :                 else {
    2321       41241 :                         err = tnc_next(c, &znode, &n);
    2322       41241 :                         if (err == -ENOENT) {
    2323             :                                 err = 0;
    2324             :                                 goto out_unlock;
    2325             :                         }
    2326       40190 :                         if (err < 0)
    2327             :                                 goto out_unlock;
    2328       40190 :                         key = &znode->zbranch[n].key;
    2329       40190 :                         if (!key_in_range(c, key, from_key, to_key)) {
    2330             :                                 err = 0;
    2331             :                                 goto out_unlock;
    2332             :                         }
    2333             :                 }
    2334             : 
    2335             :                 /* Ensure the znode is dirtied */
    2336       78048 :                 if (znode->cnext || !ubifs_zn_dirty(znode)) {
    2337       31437 :                         znode = dirty_cow_bottom_up(c, znode);
    2338       62874 :                         if (IS_ERR(znode)) {
    2339           0 :                                 err = PTR_ERR(znode);
    2340           0 :                                 goto out_unlock;
    2341             :                         }
    2342             :                 }
    2343             : 
    2344             :                 /* Remove all keys in range except the first */
    2345      243836 :                 for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) {
    2346      209365 :                         key = &znode->zbranch[i].key;
    2347      209365 :                         if (!key_in_range(c, key, from_key, to_key))
    2348             :                                 break;
    2349      204812 :                         lnc_free(&znode->zbranch[i]);
    2350      409624 :                         err = ubifs_add_dirt(c, znode->zbranch[i].lnum,
    2351      204812 :                                              znode->zbranch[i].len);
    2352      204812 :                         if (err) {
    2353           0 :                                 ubifs_dump_znode(c, znode);
    2354           0 :                                 goto out_unlock;
    2355             :                         }
    2356      204812 :                         dbg_tnck(key, "removing key ");
    2357             :                 }
    2358       39024 :                 if (k) {
    2359       37666 :                         for (i = n + 1 + k; i < znode->child_cnt; i++)
    2360        3587 :                                 znode->zbranch[i - k] = znode->zbranch[i];
    2361       34079 :                         znode->child_cnt -= k;
    2362             :                 }
    2363             : 
    2364             :                 /* Now delete the first */
    2365       39024 :                 err = tnc_delete(c, znode, n);
    2366       39024 :                 if (err)
    2367             :                         goto out_unlock;
    2368             :         }
    2369             : 
    2370           0 : out_unlock:
    2371        9107 :         if (!err)
    2372        9107 :                 err = dbg_check_tnc(c, 0);
    2373        9107 :         mutex_unlock(&c->tnc_mutex);
    2374        9107 :         return err;
    2375             : }
    2376             : 
    2377             : /**
    2378             :  * ubifs_tnc_remove_ino - remove an inode from TNC.
    2379             :  * @c: UBIFS file-system description object
    2380             :  * @inum: inode number to remove
    2381             :  *
    2382             :  * This function remove inode @inum and all the extended attributes associated
    2383             :  * with the anode from TNC and returns zero in case of success or a negative
    2384             :  * error code in case of failure.
    2385             :  */
    2386        4747 : int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)
    2387             : {
    2388             :         union ubifs_key key1, key2;
    2389        4747 :         struct ubifs_dent_node *xent, *pxent = NULL;
    2390        4747 :         struct fscrypt_name nm = {0};
    2391             : 
    2392        4747 :         dbg_tnc("ino %lu", (unsigned long)inum);
    2393             : 
    2394             :         /*
    2395             :          * Walk all extended attribute entries and remove them together with
    2396             :          * corresponding extended attribute inodes.
    2397             :          */
    2398        4747 :         lowest_xent_key(c, &key1, inum);
    2399             :         while (1) {
    2400             :                 ino_t xattr_inum;
    2401             :                 int err;
    2402             : 
    2403        5488 :                 xent = ubifs_tnc_next_ent(c, &key1, &nm);
    2404        5488 :                 if (IS_ERR(xent)) {
    2405             :                         unsigned int reason;
    2406             : 
    2407        4747 :                         err = PTR_ERR(xent);
    2408        4747 :                         if (err == -ENOENT)
    2409             :                                 break;
    2410             : 
    2411           0 :                         reason = get_failure_reason_callback(c);
    2412           0 :                         if (reason & FR_DATA_CORRUPTED) {
    2413           0 :                                 test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED);
    2414           0 :                                 if (handle_failure_callback(c, FR_H_TNC_DATA_CORRUPTED, NULL)) {
    2415             :                                         /* Set %FR_LPT_INCORRECT for lpt status. */
    2416             :                                         set_lpt_invalid_callback(c, FR_LPT_INCORRECT);
    2417             :                                         /* Leave xattrs to be deleted by subsequent steps */
    2418             :                                         break;
    2419             :                                 }
    2420             :                         }
    2421           0 :                         kfree(pxent);
    2422           0 :                         return err;
    2423             :                 }
    2424             : 
    2425         741 :                 xattr_inum = le64_to_cpu(xent->inum);
    2426         741 :                 dbg_tnc("xent '%s', ino %lu", xent->name,
    2427             :                         (unsigned long)xattr_inum);
    2428             : 
    2429         741 :                 fname_name(&nm) = (const char *)xent->name;
    2430         741 :                 fname_len(&nm) = le16_to_cpu(xent->nlen);
    2431         741 :                 err = ubifs_tnc_remove_nm(c, &key1, &nm);
    2432         741 :                 if (err) {
    2433           0 :                         kfree(pxent);
    2434           0 :                         kfree(xent);
    2435           0 :                         return err;
    2436             :                 }
    2437             : 
    2438        1482 :                 lowest_ino_key(c, &key1, xattr_inum);
    2439        1482 :                 highest_ino_key(c, &key2, xattr_inum);
    2440         741 :                 err = ubifs_tnc_remove_range(c, &key1, &key2);
    2441         741 :                 if (err) {
    2442           0 :                         kfree(pxent);
    2443           0 :                         kfree(xent);
    2444           0 :                         return err;
    2445             :                 }
    2446             : 
    2447         741 :                 kfree(pxent);
    2448         741 :                 pxent = xent;
    2449         741 :                 key_read(c, &xent->key, &key1);
    2450             :         }
    2451             : 
    2452        4747 :         kfree(pxent);
    2453        9494 :         lowest_ino_key(c, &key1, inum);
    2454        9494 :         highest_ino_key(c, &key2, inum);
    2455             : 
    2456        4747 :         return ubifs_tnc_remove_range(c, &key1, &key2);
    2457             : }
    2458             : 
    2459             : /**
    2460             :  * ubifs_tnc_remove_node - remove an index entry of a node by given position.
    2461             :  * @c: UBIFS file-system description object
    2462             :  * @key: key of node
    2463             :  * @lnum: LEB number of node
    2464             :  * @offs: node offset
    2465             :  *
    2466             :  * Returns %0 on success or negative error code on failure.
    2467             :  */
    2468      400654 : int ubifs_tnc_remove_node(struct ubifs_info *c, const union ubifs_key *key,
    2469             :                           int lnum, int offs)
    2470             : {
    2471      400654 :         int found, n, err = 0;
    2472             :         struct ubifs_znode *znode;
    2473             : 
    2474      400654 :         mutex_lock(&c->tnc_mutex);
    2475      400654 :         dbg_tnck(key, "pos %d:%d, key ", lnum, offs);
    2476      400654 :         found = lookup_level0_dirty(c, key, &znode, &n);
    2477      400654 :         if (found < 0) {
    2478             :                 err = found;
    2479             :                 goto out_unlock;
    2480             :         }
    2481      400654 :         if (found == 1) {
    2482      400654 :                 struct ubifs_zbranch *zbr = &znode->zbranch[n];
    2483             : 
    2484      400654 :                 if (zbr->lnum == lnum && zbr->offs == offs) {
    2485      400654 :                         err = tnc_delete(c, znode, n);
    2486           0 :                 } else if (is_hash_key(c, key)) {
    2487           0 :                         found = resolve_collision_directly(c, key, &znode, &n,
    2488             :                                                            lnum, offs);
    2489           0 :                         if (found < 0) {
    2490             :                                 err = found;
    2491             :                                 goto out_unlock;
    2492             :                         }
    2493             : 
    2494           0 :                         if (found) {
    2495             :                                 /* Ensure the znode is dirtied */
    2496           0 :                                 if (znode->cnext || !ubifs_zn_dirty(znode)) {
    2497           0 :                                         znode = dirty_cow_bottom_up(c, znode);
    2498           0 :                                         if (IS_ERR(znode)) {
    2499           0 :                                                 err = PTR_ERR(znode);
    2500           0 :                                                 goto out_unlock;
    2501             :                                         }
    2502             :                                 }
    2503           0 :                                 err = tnc_delete(c, znode, n);
    2504             :                         } else {
    2505             :                                 goto not_found;
    2506             :                         }
    2507             :                 } else {
    2508             :                         goto not_found;
    2509             :                 }
    2510             :         } else {
    2511           0 : not_found:
    2512             :                 /* Impossible, the node has been found before being deleted. */
    2513           0 :                 ubifs_assert(c, 0);
    2514             :         }
    2515      400654 :         if (!err)
    2516             :                 err = dbg_check_tnc(c, 0);
    2517             : 
    2518           0 : out_unlock:
    2519      400654 :         mutex_unlock(&c->tnc_mutex);
    2520      400654 :         return err;
    2521             : }
    2522             : 
    2523             : /**
    2524             :  * ubifs_tnc_next_ent - walk directory or extended attribute entries.
    2525             :  * @c: UBIFS file-system description object
    2526             :  * @key: key of last entry
    2527             :  * @nm: name of last entry found or %NULL
    2528             :  *
    2529             :  * This function finds and reads the next directory or extended attribute entry
    2530             :  * after the given key (@key) if there is one. @nm is used to resolve
    2531             :  * collisions.
    2532             :  *
    2533             :  * If the name of the current entry is not known and only the key is known,
    2534             :  * @nm->name has to be %NULL. In this case the semantics of this function is a
    2535             :  * little bit different and it returns the entry corresponding to this key, not
    2536             :  * the next one. If the key was not found, the closest "right" entry is
    2537             :  * returned.
    2538             :  *
    2539             :  * If the fist entry has to be found, @key has to contain the lowest possible
    2540             :  * key value for this inode and @name has to be %NULL.
    2541             :  *
    2542             :  * This function returns the found directory or extended attribute entry node
    2543             :  * in case of success, %-ENOENT is returned if no entry was found, and a
    2544             :  * negative error code is returned in case of failure.
    2545             :  */
    2546        5488 : struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,
    2547             :                                            union ubifs_key *key,
    2548             :                                            const struct fscrypt_name *nm)
    2549             : {
    2550       10976 :         int n, err, type = key_type(c, key);
    2551             :         struct ubifs_znode *znode;
    2552             :         struct ubifs_dent_node *dent;
    2553             :         struct ubifs_zbranch *zbr;
    2554             :         union ubifs_key *dkey;
    2555             : 
    2556        5488 :         dbg_tnck(key, "key ");
    2557       10976 :         ubifs_assert(c, is_hash_key(c, key));
    2558             : 
    2559        5488 :         mutex_lock(&c->tnc_mutex);
    2560        5488 :         err = ubifs_lookup_level0(c, key, &znode, &n);
    2561        5488 :         if (unlikely(err < 0))
    2562             :                 goto out_unlock;
    2563             : 
    2564        5488 :         if (fname_len(nm) > 0) {
    2565         741 :                 if (err) {
    2566             :                         /* Handle collisions */
    2567         741 :                         if (c->replaying)
    2568         741 :                                 err = fallible_resolve_collision(c, key, &znode, &n,
    2569             :                                                          nm, 0);
    2570             :                         else
    2571           0 :                                 err = resolve_collision(c, key, &znode, &n, nm);
    2572         741 :                         dbg_tnc("rc returned %d, znode %p, n %d",
    2573             :                                 err, znode, n);
    2574         741 :                         if (unlikely(err < 0))
    2575             :                                 goto out_unlock;
    2576             :                 }
    2577             : 
    2578             :                 /* Now find next entry */
    2579         741 :                 err = tnc_next(c, &znode, &n);
    2580         741 :                 if (unlikely(err))
    2581             :                         goto out_unlock;
    2582             :         } else {
    2583             :                 /*
    2584             :                  * The full name of the entry was not given, in which case the
    2585             :                  * behavior of this function is a little different and it
    2586             :                  * returns current entry, not the next one.
    2587             :                  */
    2588        4747 :                 if (!err) {
    2589             :                         /*
    2590             :                          * However, the given key does not exist in the TNC
    2591             :                          * tree and @znode/@n variables contain the closest
    2592             :                          * "preceding" element. Switch to the next one.
    2593             :                          */
    2594        4747 :                         err = tnc_next(c, &znode, &n);
    2595        4747 :                         if (err)
    2596             :                                 goto out_unlock;
    2597             :                 }
    2598             :         }
    2599             : 
    2600        4716 :         zbr = &znode->zbranch[n];
    2601        4716 :         dent = kmalloc(zbr->len, GFP_NOFS);
    2602        4716 :         if (unlikely(!dent)) {
    2603             :                 err = -ENOMEM;
    2604             :                 goto out_unlock;
    2605             :         }
    2606             : 
    2607             :         /*
    2608             :          * The above 'tnc_next()' call could lead us to the next inode, check
    2609             :          * this.
    2610             :          */
    2611        4716 :         dkey = &zbr->key;
    2612       14990 :         if (key_inum(c, dkey) != key_inum(c, key) ||
    2613         842 :             key_type(c, dkey) != type) {
    2614             :                 err = -ENOENT;
    2615             :                 goto out_free;
    2616             :         }
    2617             : 
    2618         842 :         err = tnc_read_hashed_node(c, zbr, dent);
    2619         842 :         if (unlikely(err))
    2620             :                 goto out_free;
    2621             : 
    2622         741 :         mutex_unlock(&c->tnc_mutex);
    2623         741 :         return dent;
    2624             : 
    2625         101 : out_free:
    2626             :         kfree(dent);
    2627        5519 : out_unlock:
    2628        4747 :         mutex_unlock(&c->tnc_mutex);
    2629        9494 :         return ERR_PTR(err);
    2630             : }
    2631             : 
    2632             : /**
    2633             :  * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.
    2634             :  * @c: UBIFS file-system description object
    2635             :  *
    2636             :  * Destroy left-over obsolete znodes from a failed commit.
    2637             :  */
    2638        1951 : static void tnc_destroy_cnext(struct ubifs_info *c)
    2639             : {
    2640             :         struct ubifs_znode *cnext;
    2641             : 
    2642        1951 :         if (!c->cnext)
    2643             :                 return;
    2644          27 :         ubifs_assert(c, c->cmt_state == COMMIT_BROKEN);
    2645          27 :         cnext = c->cnext;
    2646             :         do {
    2647      141183 :                 struct ubifs_znode *znode = cnext;
    2648             : 
    2649      141183 :                 cnext = cnext->cnext;
    2650      141183 :                 if (ubifs_zn_obsolete(znode))
    2651             :                         kfree(znode);
    2652      141183 :                 else if (!ubifs_zn_cow(znode)) {
    2653             :                         /*
    2654             :                          * Don't forget to update clean znode count after
    2655             :                          * committing failed, because ubifs will check this
    2656             :                          * count while closing tnc. Non-obsolete znode could
    2657             :                          * be re-dirtied during committing process, so dirty
    2658             :                          * flag is untrustable. The flag 'COW_ZNODE' is set
    2659             :                          * for each dirty znode before committing, and it is
    2660             :                          * cleared as long as the znode become clean, so we
    2661             :                          * can statistic clean znode count according to this
    2662             :                          * flag.
    2663             :                          */
    2664       46754 :                         atomic_long_inc(&c->clean_zn_cnt);
    2665             :                         atomic_long_inc(&ubifs_clean_zn_cnt);
    2666             :                 }
    2667      141183 :         } while (cnext && cnext != c->cnext);
    2668             : }
    2669             : 
    2670             : /**
    2671             :  * ubifs_tnc_close - close TNC subsystem and free all related resources.
    2672             :  * @c: UBIFS file-system description object
    2673             :  */
    2674        1951 : void ubifs_tnc_close(struct ubifs_info *c)
    2675             : {
    2676        1951 :         tnc_destroy_cnext(c);
    2677        1951 :         ubifs_destroy_tnc_tree(c);
    2678        3902 :         kfree(c->gap_lebs);
    2679        3902 :         kfree(c->ilebs);
    2680        1951 :         destroy_old_idx(c);
    2681        1951 : }
    2682             : 
    2683             : /**
    2684             :  * left_znode - get the znode to the left.
    2685             :  * @c: UBIFS file-system description object
    2686             :  * @znode: znode
    2687             :  *
    2688             :  * This function returns a pointer to the znode to the left of @znode or NULL if
    2689             :  * there is not one. A negative error code is returned on failure.
    2690             :  */
    2691   102148990 : static struct ubifs_znode *left_znode(struct ubifs_info *c,
    2692             :                                       struct ubifs_znode *znode)
    2693             : {
    2694   102148990 :         int level = znode->level;
    2695             : 
    2696             :         while (1) {
    2697   130475114 :                 int n = znode->iip - 1;
    2698             : 
    2699             :                 /* Go up until we can go left */
    2700   130475114 :                 znode = znode->parent;
    2701   130475114 :                 if (!znode)
    2702             :                         return NULL;
    2703   130466649 :                 if (n >= 0) {
    2704             :                         /* Now go down the rightmost branch to 'level' */
    2705   102140525 :                         znode = get_znode(c, znode, n);
    2706   102140525 :                         if (IS_ERR(znode))
    2707             :                                 return znode;
    2708   130445143 :                         while (znode->level != level) {
    2709    28304618 :                                 n = znode->child_cnt - 1;
    2710    28304618 :                                 znode = get_znode(c, znode, n);
    2711    28304618 :                                 if (IS_ERR(znode))
    2712             :                                         return znode;
    2713             :                         }
    2714             :                         break;
    2715             :                 }
    2716             :         }
    2717             :         return znode;
    2718             : }
    2719             : 
    2720             : /**
    2721             :  * right_znode - get the znode to the right.
    2722             :  * @c: UBIFS file-system description object
    2723             :  * @znode: znode
    2724             :  *
    2725             :  * This function returns a pointer to the znode to the right of @znode or NULL
    2726             :  * if there is not one. A negative error code is returned on failure.
    2727             :  */
    2728    70001511 : static struct ubifs_znode *right_znode(struct ubifs_info *c,
    2729             :                                        struct ubifs_znode *znode)
    2730             : {
    2731    70001511 :         int level = znode->level;
    2732             : 
    2733             :         while (1) {
    2734    92967202 :                 int n = znode->iip + 1;
    2735             : 
    2736             :                 /* Go up until we can go right */
    2737    92967202 :                 znode = znode->parent;
    2738    92967202 :                 if (!znode)
    2739             :                         return NULL;
    2740    92906351 :                 if (n < znode->child_cnt) {
    2741             :                         /* Now go down the leftmost branch to 'level' */
    2742    69940660 :                         znode = get_znode(c, znode, n);
    2743    69940660 :                         if (IS_ERR(znode))
    2744             :                                 return znode;
    2745    92862633 :                         while (znode->level != level) {
    2746    22921973 :                                 znode = get_znode(c, znode, 0);
    2747    22921973 :                                 if (IS_ERR(znode))
    2748             :                                         return znode;
    2749             :                         }
    2750             :                         break;
    2751             :                 }
    2752             :         }
    2753             :         return znode;
    2754             : }
    2755             : 
    2756             : /**
    2757             :  * lookup_znode - find a particular indexing node from TNC.
    2758             :  * @c: UBIFS file-system description object
    2759             :  * @key: index node key to lookup
    2760             :  * @level: index node level
    2761             :  * @lnum: index node LEB number
    2762             :  * @offs: index node offset
    2763             :  *
    2764             :  * This function searches an indexing node by its first key @key and its
    2765             :  * address @lnum:@offs. It looks up the indexing tree by pulling all indexing
    2766             :  * nodes it traverses to TNC. This function is called for indexing nodes which
    2767             :  * were found on the media by scanning, for example when garbage-collecting or
    2768             :  * when doing in-the-gaps commit. This means that the indexing node which is
    2769             :  * looked for does not have to have exactly the same leftmost key @key, because
    2770             :  * the leftmost key may have been changed, in which case TNC will contain a
    2771             :  * dirty znode which still refers the same @lnum:@offs. This function is clever
    2772             :  * enough to recognize such indexing nodes.
    2773             :  *
    2774             :  * Note, if a znode was deleted or changed too much, then this function will
    2775             :  * not find it. For situations like this UBIFS has the old index RB-tree
    2776             :  * (indexed by @lnum:@offs).
    2777             :  *
    2778             :  * This function returns a pointer to the znode found or %NULL if it is not
    2779             :  * found. A negative error code is returned on failure.
    2780             :  */
    2781  2400723461 : static struct ubifs_znode *lookup_znode(struct ubifs_info *c,
    2782             :                                         union ubifs_key *key, int level,
    2783             :                                         int lnum, int offs)
    2784             : {
    2785             :         struct ubifs_znode *znode, *zn;
    2786             :         int n, nn;
    2787             : 
    2788  4801446922 :         ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);
    2789             : 
    2790             :         /*
    2791             :          * The arguments have probably been read off flash, so don't assume
    2792             :          * they are valid.
    2793             :          */
    2794  2400723461 :         if (level < 0)
    2795             :                 return ERR_PTR(-EINVAL);
    2796             : 
    2797             :         /* Get the root znode */
    2798  2400723461 :         znode = c->zroot.znode;
    2799  2400723461 :         if (!znode) {
    2800           0 :                 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
    2801           0 :                 if (IS_ERR(znode))
    2802             :                         return znode;
    2803             :         }
    2804             :         /* Check if it is the one we are looking for */
    2805  2400723461 :         if (c->zroot.lnum == lnum && c->zroot.offs == offs)
    2806             :                 return znode;
    2807             :         /* Descend to the parent level i.e. (level + 1) */
    2808  2400721929 :         if (level >= znode->level)
    2809             :                 return NULL;
    2810             :         while (1) {
    2811 17866782189 :                 ubifs_search_zbranch(c, znode, key, &n);
    2812 17866782189 :                 if (n < 0) {
    2813             :                         /*
    2814             :                          * We reached a znode where the leftmost key is greater
    2815             :                          * than the key we are searching for. This is the same
    2816             :                          * situation as the one described in a huge comment at
    2817             :                          * the end of the 'ubifs_lookup_level0()' function. And
    2818             :                          * for exactly the same reasons we have to try to look
    2819             :                          * left before giving up.
    2820             :                          */
    2821    16866989 :                         znode = left_znode(c, znode);
    2822    16866989 :                         if (!znode)
    2823             :                                 return NULL;
    2824    16862554 :                         if (IS_ERR(znode))
    2825             :                                 return znode;
    2826    16862554 :                         ubifs_search_zbranch(c, znode, key, &n);
    2827    16862554 :                         ubifs_assert(c, n >= 0);
    2828             :                 }
    2829 17866777754 :                 if (znode->level == level + 1)
    2830             :                         break;
    2831 30935628298 :                 znode = get_znode(c, znode, n);
    2832 15467814149 :                 if (IS_ERR(znode))
    2833             :                         return znode;
    2834             :         }
    2835             :         /* Check if the child is the one we are looking for */
    2836  2398963605 :         if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs)
    2837   566916431 :                 return get_znode(c, znode, n);
    2838             :         /* If the key is unique, there is nowhere else to look */
    2839  3664094348 :         if (!is_hash_key(c, key))
    2840             :                 return NULL;
    2841             :         /*
    2842             :          * The key is not unique and so may be also in the znodes to either
    2843             :          * side.
    2844             :          */
    2845             :         zn = znode;
    2846             :         nn = n;
    2847             :         /* Look left */
    2848             :         while (1) {
    2849             :                 /* Move one branch to the left */
    2850   361220610 :                 if (n)
    2851   275938609 :                         n -= 1;
    2852             :                 else {
    2853    85282001 :                         znode = left_znode(c, znode);
    2854    85282001 :                         if (!znode)
    2855             :                                 break;
    2856    85277971 :                         if (IS_ERR(znode))
    2857             :                                 return znode;
    2858    85277971 :                         n = znode->child_cnt - 1;
    2859             :                 }
    2860             :                 /* Check it */
    2861   365959787 :                 if (znode->zbranch[n].lnum == lnum &&
    2862     4743207 :                     znode->zbranch[n].offs == offs)
    2863           0 :                         return get_znode(c, znode, n);
    2864             :                 /* Stop if the key is less than the one we are looking for */
    2865   361216580 :                 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)
    2866             :                         break;
    2867             :         }
    2868             :         /* Back to the middle */
    2869   361220610 :         znode = zn;
    2870   361220610 :         n = nn;
    2871             :         /* Look right */
    2872             :         while (1) {
    2873             :                 /* Move one branch to the right */
    2874   361220610 :                 if (++n >= znode->child_cnt) {
    2875    70001511 :                         znode = right_znode(c, znode);
    2876    70001511 :                         if (!znode)
    2877             :                                 break;
    2878    69940660 :                         if (IS_ERR(znode))
    2879             :                                 return znode;
    2880    69940660 :                         n = 0;
    2881             :                 }
    2882             :                 /* Check it */
    2883   367590752 :                 if (znode->zbranch[n].lnum == lnum &&
    2884     6430993 :                     znode->zbranch[n].offs == offs)
    2885           0 :                         return get_znode(c, znode, n);
    2886             :                 /* Stop if the key is greater than the one we are looking for */
    2887   361159759 :                 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)
    2888             :                         break;
    2889             :         }
    2890             :         return NULL;
    2891             : }
    2892             : 
    2893             : /**
    2894             :  * is_idx_node_in_tnc - determine if an index node is in the TNC.
    2895             :  * @c: UBIFS file-system description object
    2896             :  * @key: key of index node
    2897             :  * @level: index node level
    2898             :  * @lnum: LEB number of index node
    2899             :  * @offs: offset of index node
    2900             :  *
    2901             :  * This function returns %0 if the index node is not referred to in the TNC, %1
    2902             :  * if the index node is referred to in the TNC and the corresponding znode is
    2903             :  * dirty, %2 if an index node is referred to in the TNC and the corresponding
    2904             :  * znode is clean, and a negative error code in case of failure.
    2905             :  *
    2906             :  * Note, the @key argument has to be the key of the first child. Also note,
    2907             :  * this function relies on the fact that 0:0 is never a valid LEB number and
    2908             :  * offset for a main-area node.
    2909             :  */
    2910  2400723461 : int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,
    2911             :                        int lnum, int offs)
    2912             : {
    2913             :         struct ubifs_znode *znode;
    2914             : 
    2915  2400723461 :         znode = lookup_znode(c, key, level, lnum, offs);
    2916  2400723461 :         if (!znode)
    2917             :                 return 0;
    2918   566917963 :         if (IS_ERR(znode))
    2919           0 :                 return PTR_ERR(znode);
    2920             : 
    2921   566917963 :         return ubifs_zn_dirty(znode) ? 1 : 2;
    2922             : }
    2923             : 
    2924             : /**
    2925             :  * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.
    2926             :  * @c: UBIFS file-system description object
    2927             :  * @key: node key
    2928             :  * @lnum: node LEB number
    2929             :  * @offs: node offset
    2930             :  *
    2931             :  * This function returns %1 if the node is referred to in the TNC, %0 if it is
    2932             :  * not, and a negative error code in case of failure.
    2933             :  *
    2934             :  * Note, this function relies on the fact that 0:0 is never a valid LEB number
    2935             :  * and offset for a main-area node.
    2936             :  */
    2937  3922805030 : static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,
    2938             :                                int lnum, int offs)
    2939             : {
    2940             :         struct ubifs_zbranch *zbr;
    2941             :         struct ubifs_znode *znode, *zn;
    2942             :         int n, found, err, nn;
    2943  7845610060 :         const int unique = !is_hash_key(c, key);
    2944             : 
    2945  3922805030 :         found = ubifs_lookup_level0(c, key, &znode, &n);
    2946  3922805030 :         if (found < 0)
    2947             :                 return found; /* Error code */
    2948  3922805030 :         if (!found)
    2949             :                 return 0;
    2950  3179266245 :         zbr = &znode->zbranch[n];
    2951  3179266245 :         if (lnum == zbr->lnum && offs == zbr->offs)
    2952             :                 return 1; /* Found it */
    2953   692037866 :         if (unique)
    2954             :                 return 0;
    2955             :         /*
    2956             :          * Because the key is not unique, we have to look left
    2957             :          * and right as well
    2958             :          */
    2959             :         zn = znode;
    2960             :         nn = n;
    2961             :         /* Look left */
    2962             :         while (1) {
    2963    34108323 :                 err = tnc_prev(c, &znode, &n);
    2964    34108323 :                 if (err == -ENOENT)
    2965             :                         break;
    2966    34108323 :                 if (err)
    2967             :                         return err;
    2968    34108323 :                 if (keys_cmp(c, key, &znode->zbranch[n].key))
    2969             :                         break;
    2970           0 :                 zbr = &znode->zbranch[n];
    2971           0 :                 if (lnum == zbr->lnum && offs == zbr->offs)
    2972             :                         return 1; /* Found it */
    2973             :         }
    2974             :         /* Look right */
    2975    34108323 :         znode = zn;
    2976    34108323 :         n = nn;
    2977             :         while (1) {
    2978    34108323 :                 err = tnc_next(c, &znode, &n);
    2979    34108323 :                 if (err) {
    2980           0 :                         if (err == -ENOENT)
    2981             :                                 return 0;
    2982           0 :                         return err;
    2983             :                 }
    2984    34108323 :                 if (keys_cmp(c, key, &znode->zbranch[n].key))
    2985             :                         break;
    2986           0 :                 zbr = &znode->zbranch[n];
    2987           0 :                 if (lnum == zbr->lnum && offs == zbr->offs)
    2988             :                         return 1; /* Found it */
    2989             :         }
    2990             :         return 0;
    2991             : }
    2992             : 
    2993             : /**
    2994             :  * ubifs_tnc_has_node - determine whether a node is in the TNC.
    2995             :  * @c: UBIFS file-system description object
    2996             :  * @key: node key
    2997             :  * @level: index node level (if it is an index node)
    2998             :  * @lnum: node LEB number
    2999             :  * @offs: node offset
    3000             :  * @is_idx: non-zero if the node is an index node
    3001             :  *
    3002             :  * This function returns %1 if the node is in the TNC, %0 if it is not, and a
    3003             :  * negative error code in case of failure. For index nodes, @key has to be the
    3004             :  * key of the first child. An index node is considered to be in the TNC only if
    3005             :  * the corresponding znode is clean or has not been loaded.
    3006             :  */
    3007  6321522230 : int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,
    3008             :                        int lnum, int offs, int is_idx)
    3009             : {
    3010             :         int err;
    3011             : 
    3012  6321522230 :         mutex_lock(&c->tnc_mutex);
    3013  6321522230 :         if (is_idx) {
    3014  2398717200 :                 err = is_idx_node_in_tnc(c, key, level, lnum, offs);
    3015  2398717200 :                 if (err < 0)
    3016             :                         goto out_unlock;
    3017  2398717200 :                 if (err == 1)
    3018             :                         /* The index node was found but it was dirty */
    3019             :                         err = 0;
    3020  2396602525 :                 else if (err == 2)
    3021             :                         /* The index node was found and it was clean */
    3022             :                         err = 1;
    3023             :                 else
    3024  1832144905 :                         BUG_ON(err != 0);
    3025             :         } else
    3026  3922805030 :                 err = is_leaf_node_in_tnc(c, key, lnum, offs);
    3027             : 
    3028  6321522230 : out_unlock:
    3029  6321522230 :         mutex_unlock(&c->tnc_mutex);
    3030  6321522230 :         return err;
    3031             : }
    3032             : 
    3033             : /**
    3034             :  * ubifs_dirty_idx_node - dirty an index node.
    3035             :  * @c: UBIFS file-system description object
    3036             :  * @key: index node key
    3037             :  * @level: index node level
    3038             :  * @lnum: index node LEB number
    3039             :  * @offs: index node offset
    3040             :  *
    3041             :  * This function loads and dirties an index node so that it can be garbage
    3042             :  * collected. The @key argument has to be the key of the first child. This
    3043             :  * function relies on the fact that 0:0 is never a valid LEB number and offset
    3044             :  * for a main-area node. Returns %0 on success and a negative error code on
    3045             :  * failure.
    3046             :  */
    3047           0 : int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,
    3048             :                          int lnum, int offs)
    3049             : {
    3050             :         struct ubifs_znode *znode;
    3051           0 :         int err = 0;
    3052             : 
    3053           0 :         mutex_lock(&c->tnc_mutex);
    3054           0 :         znode = lookup_znode(c, key, level, lnum, offs);
    3055           0 :         if (!znode)
    3056             :                 goto out_unlock;
    3057           0 :         if (IS_ERR(znode)) {
    3058           0 :                 err = PTR_ERR(znode);
    3059           0 :                 goto out_unlock;
    3060             :         }
    3061           0 :         znode = dirty_cow_bottom_up(c, znode);
    3062           0 :         if (IS_ERR(znode)) {
    3063           0 :                 err = PTR_ERR(znode);
    3064           0 :                 goto out_unlock;
    3065             :         }
    3066             : 
    3067           0 : out_unlock:
    3068           0 :         mutex_unlock(&c->tnc_mutex);
    3069           0 :         return err;
    3070             : }

Generated by: LCOV version 1.13