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