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