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