fs/ubifs/tnc.c

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