3579 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * This file is part of UBIFS.4 *5 * Copyright (C) 2006-2008 Nokia Corporation.6 *7 * Authors: Adrian Hunter8 * Artem Bityutskiy (Битюцкий Артём)9 */10 11/*12 * This file implements TNC (Tree Node Cache) which caches indexing nodes of13 * the UBIFS B-tree.14 *15 * At the moment the locking rules of the TNC tree are quite simple and16 * straightforward. We just have a mutex and lock it when we traverse the17 * tree. If a znode is not in memory, we read it from flash while still having18 * 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 second33 * @NAME_MATCHES: names match34 * @NAME_GREATER: name corresponding to the second argument is greater than35 * first36 * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media37 *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 47static void do_insert_old_idx(struct ubifs_info *c,48 struct ubifs_old_idx *old_idx)49{50 struct ubifs_old_idx *o;51 struct rb_node **p, *parent = NULL;52 53 p = &c->old_idx.rb_node;54 while (*p) {55 parent = *p;56 o = rb_entry(parent, struct ubifs_old_idx, rb);57 if (old_idx->lnum < o->lnum)58 p = &(*p)->rb_left;59 else if (old_idx->lnum > o->lnum)60 p = &(*p)->rb_right;61 else if (old_idx->offs < o->offs)62 p = &(*p)->rb_left;63 else if (old_idx->offs > o->offs)64 p = &(*p)->rb_right;65 else {66 ubifs_err(c, "old idx added twice!");67 kfree(old_idx);68 return;69 }70 }71 rb_link_node(&old_idx->rb, parent, p);72 rb_insert_color(&old_idx->rb, &c->old_idx);73}74 75/**76 * insert_old_idx - record an index node obsoleted since the last commit start.77 * @c: UBIFS file-system description object78 * @lnum: LEB number of obsoleted index node79 * @offs: offset of obsoleted index node80 *81 * Returns %0 on success, and a negative error code on failure.82 *83 * For recovery, there must always be a complete intact version of the index on84 * flash at all times. That is called the "old index". It is the index as at the85 * time of the last successful commit. Many of the index nodes in the old index86 * may be dirty, but they must not be erased until the next successful commit87 * (at which point that index becomes the old index).88 *89 * That means that the garbage collection and the in-the-gaps method of90 * committing must be able to determine if an index node is in the old index.91 * Most of the old index nodes can be found by looking up the TNC using the92 * 'lookup_znode()' function. However, some of the old index nodes may have93 * been deleted from the current index or may have been changed so much that94 * they cannot be easily found. In those cases, an entry is added to an RB-tree.95 * That is what this function does. The RB-tree is ordered by LEB number and96 * offset because they uniquely identify the old index node.97 */98static int insert_old_idx(struct ubifs_info *c, int lnum, int offs)99{100 struct ubifs_old_idx *old_idx;101 102 old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);103 if (unlikely(!old_idx))104 return -ENOMEM;105 old_idx->lnum = lnum;106 old_idx->offs = offs;107 do_insert_old_idx(c, old_idx);108 109 return 0;110}111 112/**113 * insert_old_idx_znode - record a znode obsoleted since last commit start.114 * @c: UBIFS file-system description object115 * @znode: znode of obsoleted index node116 *117 * Returns %0 on success, and a negative error code on failure.118 */119int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode)120{121 if (znode->parent) {122 struct ubifs_zbranch *zbr;123 124 zbr = &znode->parent->zbranch[znode->iip];125 if (zbr->len)126 return insert_old_idx(c, zbr->lnum, zbr->offs);127 } else128 if (c->zroot.len)129 return insert_old_idx(c, c->zroot.lnum,130 c->zroot.offs);131 return 0;132}133 134/**135 * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.136 * @c: UBIFS file-system description object137 * @znode: znode of obsoleted index node138 *139 * Returns %0 on success, and a negative error code on failure.140 */141static int ins_clr_old_idx_znode(struct ubifs_info *c,142 struct ubifs_znode *znode)143{144 int err;145 146 if (znode->parent) {147 struct ubifs_zbranch *zbr;148 149 zbr = &znode->parent->zbranch[znode->iip];150 if (zbr->len) {151 err = insert_old_idx(c, zbr->lnum, zbr->offs);152 if (err)153 return err;154 zbr->lnum = 0;155 zbr->offs = 0;156 zbr->len = 0;157 }158 } else159 if (c->zroot.len) {160 err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs);161 if (err)162 return err;163 c->zroot.lnum = 0;164 c->zroot.offs = 0;165 c->zroot.len = 0;166 }167 return 0;168}169 170/**171 * destroy_old_idx - destroy the old_idx RB-tree.172 * @c: UBIFS file-system description object173 *174 * During start commit, the old_idx RB-tree is used to avoid overwriting index175 * nodes that were in the index last commit but have since been deleted. This176 * is necessary for recovery i.e. the old index must be kept intact until the177 * new index is successfully written. The old-idx RB-tree is used for the178 * in-the-gaps method of writing index nodes and is destroyed every commit.179 */180void destroy_old_idx(struct ubifs_info *c)181{182 struct ubifs_old_idx *old_idx, *n;183 184 rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb)185 kfree(old_idx);186 187 c->old_idx = RB_ROOT;188}189 190/**191 * copy_znode - copy a dirty znode.192 * @c: UBIFS file-system description object193 * @znode: znode to copy194 *195 * A dirty znode being committed may not be changed, so it is copied.196 */197static struct ubifs_znode *copy_znode(struct ubifs_info *c,198 struct ubifs_znode *znode)199{200 struct ubifs_znode *zn;201 202 zn = kmemdup(znode, c->max_znode_sz, GFP_NOFS);203 if (unlikely(!zn))204 return ERR_PTR(-ENOMEM);205 206 zn->cnext = NULL;207 __set_bit(DIRTY_ZNODE, &zn->flags);208 __clear_bit(COW_ZNODE, &zn->flags);209 210 return zn;211}212 213/**214 * add_idx_dirt - add dirt due to a dirty znode.215 * @c: UBIFS file-system description object216 * @lnum: LEB number of index node217 * @dirt: size of index node218 *219 * This function updates lprops dirty space and the new size of the index.220 */221static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt)222{223 c->calc_idx_sz -= ALIGN(dirt, 8);224 return ubifs_add_dirt(c, lnum, dirt);225}226 227/**228 * replace_znode - replace old znode with new znode.229 * @c: UBIFS file-system description object230 * @new_zn: new znode231 * @old_zn: old znode232 * @zbr: the branch of parent znode233 *234 * Replace old znode with new znode in TNC.235 */236static void replace_znode(struct ubifs_info *c, struct ubifs_znode *new_zn,237 struct ubifs_znode *old_zn, struct ubifs_zbranch *zbr)238{239 ubifs_assert(c, !ubifs_zn_obsolete(old_zn));240 __set_bit(OBSOLETE_ZNODE, &old_zn->flags);241 242 if (old_zn->level != 0) {243 int i;244 const int n = new_zn->child_cnt;245 246 /* The children now have new parent */247 for (i = 0; i < n; i++) {248 struct ubifs_zbranch *child = &new_zn->zbranch[i];249 250 if (child->znode)251 child->znode->parent = new_zn;252 }253 }254 255 zbr->znode = new_zn;256 zbr->lnum = 0;257 zbr->offs = 0;258 zbr->len = 0;259 260 atomic_long_inc(&c->dirty_zn_cnt);261}262 263/**264 * dirty_cow_znode - ensure a znode is not being committed.265 * @c: UBIFS file-system description object266 * @zbr: branch of znode to check267 *268 * Returns dirtied znode on success or negative error code on failure.269 */270static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c,271 struct ubifs_zbranch *zbr)272{273 struct ubifs_znode *znode = zbr->znode;274 struct ubifs_znode *zn;275 int err;276 277 if (!ubifs_zn_cow(znode)) {278 /* znode is not being committed */279 if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) {280 atomic_long_inc(&c->dirty_zn_cnt);281 atomic_long_dec(&c->clean_zn_cnt);282 atomic_long_dec(&ubifs_clean_zn_cnt);283 err = add_idx_dirt(c, zbr->lnum, zbr->len);284 if (unlikely(err))285 return ERR_PTR(err);286 }287 return znode;288 }289 290 zn = copy_znode(c, znode);291 if (IS_ERR(zn))292 return zn;293 294 if (zbr->len) {295 struct ubifs_old_idx *old_idx;296 297 old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);298 if (unlikely(!old_idx)) {299 err = -ENOMEM;300 goto out;301 }302 old_idx->lnum = zbr->lnum;303 old_idx->offs = zbr->offs;304 305 err = add_idx_dirt(c, zbr->lnum, zbr->len);306 if (err) {307 kfree(old_idx);308 goto out;309 }310 311 do_insert_old_idx(c, old_idx);312 }313 314 replace_znode(c, zn, znode, zbr);315 316 return zn;317 318out:319 kfree(zn);320 return ERR_PTR(err);321}322 323/**324 * lnc_add - add a leaf node to the leaf node cache.325 * @c: UBIFS file-system description object326 * @zbr: zbranch of leaf node327 * @node: leaf node328 *329 * Leaf nodes are non-index nodes directory entry nodes or data nodes. The330 * purpose of the leaf node cache is to save re-reading the same leaf node over331 * and over again. Most things are cached by VFS, however the file system must332 * cache directory entries for readdir and for resolving hash collisions. The333 * present implementation of the leaf node cache is extremely simple, and334 * allows for error returns that are not used but that may be needed if a more335 * complex implementation is created.336 *337 * Note, this function does not add the @node object to LNC directly, but338 * allocates a copy of the object and adds the copy to LNC. The reason for this339 * is that @node has been allocated outside of the TNC subsystem and will be340 * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC341 * may be changed at any time, e.g. freed by the shrinker.342 */343static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr,344 const void *node)345{346 int err;347 void *lnc_node;348 const struct ubifs_dent_node *dent = node;349 350 ubifs_assert(c, !zbr->leaf);351 ubifs_assert(c, zbr->len != 0);352 ubifs_assert(c, is_hash_key(c, &zbr->key));353 354 err = ubifs_validate_entry(c, dent);355 if (err) {356 dump_stack();357 ubifs_dump_node(c, dent, zbr->len);358 return err;359 }360 361 lnc_node = kmemdup(node, zbr->len, GFP_NOFS);362 if (!lnc_node)363 /* We don't have to have the cache, so no error */364 return 0;365 366 zbr->leaf = lnc_node;367 return 0;368}369 370 /**371 * lnc_add_directly - add a leaf node to the leaf-node-cache.372 * @c: UBIFS file-system description object373 * @zbr: zbranch of leaf node374 * @node: leaf node375 *376 * This function is similar to 'lnc_add()', but it does not create a copy of377 * @node but inserts @node to TNC directly.378 */379static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr,380 void *node)381{382 int err;383 384 ubifs_assert(c, !zbr->leaf);385 ubifs_assert(c, zbr->len != 0);386 387 err = ubifs_validate_entry(c, node);388 if (err) {389 dump_stack();390 ubifs_dump_node(c, node, zbr->len);391 return err;392 }393 394 zbr->leaf = node;395 return 0;396}397 398/**399 * lnc_free - remove a leaf node from the leaf node cache.400 * @zbr: zbranch of leaf node401 */402static void lnc_free(struct ubifs_zbranch *zbr)403{404 if (!zbr->leaf)405 return;406 kfree(zbr->leaf);407 zbr->leaf = NULL;408}409 410/**411 * tnc_read_hashed_node - read a "hashed" leaf node.412 * @c: UBIFS file-system description object413 * @zbr: key and position of the node414 * @node: node is returned here415 *416 * This function reads a "hashed" node defined by @zbr from the leaf node cache417 * (in it is there) or from the hash media, in which case the node is also418 * added to LNC. Returns zero in case of success or a negative error419 * code in case of failure.420 */421static int tnc_read_hashed_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,422 void *node)423{424 int err;425 426 ubifs_assert(c, is_hash_key(c, &zbr->key));427 428 if (zbr->leaf) {429 /* Read from the leaf node cache */430 ubifs_assert(c, zbr->len != 0);431 memcpy(node, zbr->leaf, zbr->len);432 return 0;433 }434 435 if (c->replaying) {436 err = fallible_read_node(c, &zbr->key, zbr, node);437 /*438 * When the node was not found, return -ENOENT, 0 otherwise.439 * Negative return codes stay as-is.440 */441 if (err == 0)442 err = -ENOENT;443 else if (err == 1)444 err = 0;445 } else {446 err = ubifs_tnc_read_node(c, zbr, node);447 }448 if (err)449 return err;450 451 /* Add the node to the leaf node cache */452 err = lnc_add(c, zbr, node);453 return err;454}455 456/**457 * try_read_node - read a node if it is a node.458 * @c: UBIFS file-system description object459 * @buf: buffer to read to460 * @type: node type461 * @zbr: the zbranch describing the node to read462 *463 * This function tries to read a node of known type and length, checks it and464 * stores it in @buf. This function returns %1 if a node is present and %0 if465 * a node is not present. A negative error code is returned for I/O errors.466 * This function performs that same function as ubifs_read_node except that467 * it does not require that there is actually a node present and instead468 * the return code indicates if a node was read.469 *470 * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc471 * is true (it is controlled by corresponding mount option). However, if472 * @c->mounting or @c->remounting_rw is true (we are mounting or re-mounting to473 * R/W mode), @c->no_chk_data_crc is ignored and CRC is checked. This is474 * because during mounting or re-mounting from R/O mode to R/W mode we may read475 * journal nodes (when replying the journal or doing the recovery) and the476 * journal nodes may potentially be corrupted, so checking is required.477 */478static int try_read_node(const struct ubifs_info *c, void *buf, int type,479 struct ubifs_zbranch *zbr)480{481 int len = zbr->len;482 int lnum = zbr->lnum;483 int offs = zbr->offs;484 int err, node_len;485 struct ubifs_ch *ch = buf;486 uint32_t crc, node_crc;487 488 dbg_io("LEB %d:%d, %s, length %d", lnum, offs, dbg_ntype(type), len);489 490 err = ubifs_leb_read(c, lnum, buf, offs, len, 1);491 if (err) {492 ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d",493 type, lnum, offs, err);494 return err;495 }496 497 if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)498 return 0;499 500 if (ch->node_type != type)501 return 0;502 503 node_len = le32_to_cpu(ch->len);504 if (node_len != len)505 return 0;506 507 if (type != UBIFS_DATA_NODE || !c->no_chk_data_crc || c->mounting ||508 c->remounting_rw) {509 crc = crc32(UBIFS_CRC32_INIT, buf + 8, node_len - 8);510 node_crc = le32_to_cpu(ch->crc);511 if (crc != node_crc)512 return 0;513 }514 515 err = ubifs_node_check_hash(c, buf, zbr->hash);516 if (err) {517 ubifs_bad_hash(c, buf, zbr->hash, lnum, offs);518 return 0;519 }520 521 return 1;522}523 524/**525 * fallible_read_node - try to read a leaf node.526 * @c: UBIFS file-system description object527 * @key: key of node to read528 * @zbr: position of node529 * @node: node returned530 *531 * This function tries to read a node and returns %1 if the node is read, %0532 * if the node is not present, and a negative error code in the case of error.533 */534static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,535 struct ubifs_zbranch *zbr, void *node)536{537 int ret;538 539 dbg_tnck(key, "LEB %d:%d, key ", zbr->lnum, zbr->offs);540 541 ret = try_read_node(c, node, key_type(c, key), zbr);542 if (ret == 1) {543 union ubifs_key node_key;544 struct ubifs_dent_node *dent = node;545 546 /* All nodes have key in the same place */547 key_read(c, &dent->key, &node_key);548 if (keys_cmp(c, key, &node_key) != 0)549 ret = 0;550 }551 if (ret == 0 && c->replaying)552 dbg_mntk(key, "dangling branch LEB %d:%d len %d, key ",553 zbr->lnum, zbr->offs, zbr->len);554 return ret;555}556 557/**558 * matches_name - determine if a direntry or xattr entry matches a given name.559 * @c: UBIFS file-system description object560 * @zbr: zbranch of dent561 * @nm: name to match562 *563 * This function checks if xentry/direntry referred by zbranch @zbr matches name564 * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by565 * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case566 * of failure, a negative error code is returned.567 */568static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr,569 const struct fscrypt_name *nm)570{571 struct ubifs_dent_node *dent;572 int nlen, err;573 574 /* If possible, match against the dent in the leaf node cache */575 if (!zbr->leaf) {576 dent = kmalloc(zbr->len, GFP_NOFS);577 if (!dent)578 return -ENOMEM;579 580 err = ubifs_tnc_read_node(c, zbr, dent);581 if (err)582 goto out_free;583 584 /* Add the node to the leaf node cache */585 err = lnc_add_directly(c, zbr, dent);586 if (err)587 goto out_free;588 } else589 dent = zbr->leaf;590 591 nlen = le16_to_cpu(dent->nlen);592 err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));593 if (err == 0) {594 if (nlen == fname_len(nm))595 return NAME_MATCHES;596 else if (nlen < fname_len(nm))597 return NAME_LESS;598 else599 return NAME_GREATER;600 } else if (err < 0)601 return NAME_LESS;602 else603 return NAME_GREATER;604 605out_free:606 kfree(dent);607 return err;608}609 610/**611 * get_znode - get a TNC znode that may not be loaded yet.612 * @c: UBIFS file-system description object613 * @znode: parent znode614 * @n: znode branch slot number615 *616 * This function returns the znode or a negative error code.617 */618static struct ubifs_znode *get_znode(struct ubifs_info *c,619 struct ubifs_znode *znode, int n)620{621 struct ubifs_zbranch *zbr;622 623 zbr = &znode->zbranch[n];624 if (zbr->znode)625 znode = zbr->znode;626 else627 znode = ubifs_load_znode(c, zbr, znode, n);628 return znode;629}630 631/**632 * tnc_next - find next TNC entry.633 * @c: UBIFS file-system description object634 * @zn: znode is passed and returned here635 * @n: znode branch slot number is passed and returned here636 *637 * This function returns %0 if the next TNC entry is found, %-ENOENT if there is638 * no next entry, or a negative error code otherwise.639 */640static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n)641{642 struct ubifs_znode *znode = *zn;643 int nn = *n;644 645 nn += 1;646 if (nn < znode->child_cnt) {647 *n = nn;648 return 0;649 }650 while (1) {651 struct ubifs_znode *zp;652 653 zp = znode->parent;654 if (!zp)655 return -ENOENT;656 nn = znode->iip + 1;657 znode = zp;658 if (nn < znode->child_cnt) {659 znode = get_znode(c, znode, nn);660 if (IS_ERR(znode))661 return PTR_ERR(znode);662 while (znode->level != 0) {663 znode = get_znode(c, znode, 0);664 if (IS_ERR(znode))665 return PTR_ERR(znode);666 }667 nn = 0;668 break;669 }670 }671 *zn = znode;672 *n = nn;673 return 0;674}675 676/**677 * tnc_prev - find previous TNC entry.678 * @c: UBIFS file-system description object679 * @zn: znode is returned here680 * @n: znode branch slot number is passed and returned here681 *682 * This function returns %0 if the previous TNC entry is found, %-ENOENT if683 * there is no next entry, or a negative error code otherwise.684 */685static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n)686{687 struct ubifs_znode *znode = *zn;688 int nn = *n;689 690 if (nn > 0) {691 *n = nn - 1;692 return 0;693 }694 while (1) {695 struct ubifs_znode *zp;696 697 zp = znode->parent;698 if (!zp)699 return -ENOENT;700 nn = znode->iip - 1;701 znode = zp;702 if (nn >= 0) {703 znode = get_znode(c, znode, nn);704 if (IS_ERR(znode))705 return PTR_ERR(znode);706 while (znode->level != 0) {707 nn = znode->child_cnt - 1;708 znode = get_znode(c, znode, nn);709 if (IS_ERR(znode))710 return PTR_ERR(znode);711 }712 nn = znode->child_cnt - 1;713 break;714 }715 }716 *zn = znode;717 *n = nn;718 return 0;719}720 721/**722 * resolve_collision - resolve a collision.723 * @c: UBIFS file-system description object724 * @key: key of a directory or extended attribute entry725 * @zn: znode is returned here726 * @n: zbranch number is passed and returned here727 * @nm: name of the entry728 *729 * This function is called for "hashed" keys to make sure that the found key730 * really corresponds to the looked up node (directory or extended attribute731 * entry). It returns %1 and sets @zn and @n if the collision is resolved.732 * %0 is returned if @nm is not found and @zn and @n are set to the previous733 * entry, i.e. to the entry after which @nm could follow if it were in TNC.734 * This means that @n may be set to %-1 if the leftmost key in @zn is the735 * previous one. A negative error code is returned on failures.736 */737static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,738 struct ubifs_znode **zn, int *n,739 const struct fscrypt_name *nm)740{741 int err;742 743 err = matches_name(c, &(*zn)->zbranch[*n], nm);744 if (unlikely(err < 0))745 return err;746 if (err == NAME_MATCHES)747 return 1;748 749 if (err == NAME_GREATER) {750 /* Look left */751 while (1) {752 err = tnc_prev(c, zn, n);753 if (err == -ENOENT) {754 ubifs_assert(c, *n == 0);755 *n = -1;756 return 0;757 }758 if (err < 0)759 return err;760 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {761 /*762 * We have found the branch after which we would763 * like to insert, but inserting in this znode764 * may still be wrong. Consider the following 3765 * znodes, in the case where we are resolving a766 * collision with Key2.767 *768 * znode zp769 * ----------------------770 * level 1 | Key0 | Key1 |771 * -----------------------772 * | |773 * znode za | | znode zb774 * ------------ ------------775 * level 0 | Key0 | | Key2 |776 * ------------ ------------777 *778 * The lookup finds Key2 in znode zb. Lets say779 * there is no match and the name is greater so780 * we look left. When we find Key0, we end up781 * here. If we return now, we will insert into782 * znode za at slot n = 1. But that is invalid783 * according to the parent's keys. Key2 must784 * be inserted into znode zb.785 *786 * Note, this problem is not relevant for the787 * case when we go right, because788 * 'tnc_insert()' would correct the parent key.789 */790 if (*n == (*zn)->child_cnt - 1) {791 err = tnc_next(c, zn, n);792 if (err) {793 /* Should be impossible */794 ubifs_assert(c, 0);795 if (err == -ENOENT)796 err = -EINVAL;797 return err;798 }799 ubifs_assert(c, *n == 0);800 *n = -1;801 }802 return 0;803 }804 err = matches_name(c, &(*zn)->zbranch[*n], nm);805 if (err < 0)806 return err;807 if (err == NAME_LESS)808 return 0;809 if (err == NAME_MATCHES)810 return 1;811 ubifs_assert(c, err == NAME_GREATER);812 }813 } else {814 int nn = *n;815 struct ubifs_znode *znode = *zn;816 817 /* Look right */818 while (1) {819 err = tnc_next(c, &znode, &nn);820 if (err == -ENOENT)821 return 0;822 if (err < 0)823 return err;824 if (keys_cmp(c, &znode->zbranch[nn].key, key))825 return 0;826 err = matches_name(c, &znode->zbranch[nn], nm);827 if (err < 0)828 return err;829 if (err == NAME_GREATER)830 return 0;831 *zn = znode;832 *n = nn;833 if (err == NAME_MATCHES)834 return 1;835 ubifs_assert(c, err == NAME_LESS);836 }837 }838}839 840/**841 * fallible_matches_name - determine if a dent matches a given name.842 * @c: UBIFS file-system description object843 * @zbr: zbranch of dent844 * @nm: name to match845 *846 * This is a "fallible" version of 'matches_name()' function which does not847 * panic if the direntry/xentry referred by @zbr does not exist on the media.848 *849 * This function checks if xentry/direntry referred by zbranch @zbr matches name850 * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr851 * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA852 * if xentry/direntry referred by @zbr does not exist on the media. A negative853 * error code is returned in case of failure.854 */855static int fallible_matches_name(struct ubifs_info *c,856 struct ubifs_zbranch *zbr,857 const struct fscrypt_name *nm)858{859 struct ubifs_dent_node *dent;860 int nlen, err;861 862 /* If possible, match against the dent in the leaf node cache */863 if (!zbr->leaf) {864 dent = kmalloc(zbr->len, GFP_NOFS);865 if (!dent)866 return -ENOMEM;867 868 err = fallible_read_node(c, &zbr->key, zbr, dent);869 if (err < 0)870 goto out_free;871 if (err == 0) {872 /* The node was not present */873 err = NOT_ON_MEDIA;874 goto out_free;875 }876 ubifs_assert(c, err == 1);877 878 err = lnc_add_directly(c, zbr, dent);879 if (err)880 goto out_free;881 } else882 dent = zbr->leaf;883 884 nlen = le16_to_cpu(dent->nlen);885 err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));886 if (err == 0) {887 if (nlen == fname_len(nm))888 return NAME_MATCHES;889 else if (nlen < fname_len(nm))890 return NAME_LESS;891 else892 return NAME_GREATER;893 } else if (err < 0)894 return NAME_LESS;895 else896 return NAME_GREATER;897 898out_free:899 kfree(dent);900 return err;901}902 903/**904 * fallible_resolve_collision - resolve a collision even if nodes are missing.905 * @c: UBIFS file-system description object906 * @key: key907 * @zn: znode is returned here908 * @n: branch number is passed and returned here909 * @nm: name of directory entry910 * @adding: indicates caller is adding a key to the TNC911 *912 * This is a "fallible" version of the 'resolve_collision()' function which913 * does not panic if one of the nodes referred to by TNC does not exist on the914 * media. This may happen when replaying the journal if a deleted node was915 * Garbage-collected and the commit was not done. A branch that refers to a node916 * that is not present is called a dangling branch. The following are the return917 * codes for this function:918 * o if @nm was found, %1 is returned and @zn and @n are set to the found919 * branch;920 * o if we are @adding and @nm was not found, %0 is returned;921 * o if we are not @adding and @nm was not found, but a dangling branch was922 * found, then %1 is returned and @zn and @n are set to the dangling branch;923 * o a negative error code is returned in case of failure.924 */925static int fallible_resolve_collision(struct ubifs_info *c,926 const union ubifs_key *key,927 struct ubifs_znode **zn, int *n,928 const struct fscrypt_name *nm,929 int adding)930{931 struct ubifs_znode *o_znode = NULL, *znode = *zn;932 int o_n, err, cmp, unsure = 0, nn = *n;933 934 cmp = fallible_matches_name(c, &znode->zbranch[nn], nm);935 if (unlikely(cmp < 0))936 return cmp;937 if (cmp == NAME_MATCHES)938 return 1;939 if (cmp == NOT_ON_MEDIA) {940 o_znode = znode;941 o_n = nn;942 /*943 * We are unlucky and hit a dangling branch straight away.944 * Now we do not really know where to go to find the needed945 * branch - to the left or to the right. Well, let's try left.946 */947 unsure = 1;948 } else if (!adding)949 unsure = 1; /* Remove a dangling branch wherever it is */950 951 if (cmp == NAME_GREATER || unsure) {952 /* Look left */953 while (1) {954 err = tnc_prev(c, zn, n);955 if (err == -ENOENT) {956 ubifs_assert(c, *n == 0);957 *n = -1;958 break;959 }960 if (err < 0)961 return err;962 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {963 /* See comments in 'resolve_collision()' */964 if (*n == (*zn)->child_cnt - 1) {965 err = tnc_next(c, zn, n);966 if (err) {967 /* Should be impossible */968 ubifs_assert(c, 0);969 if (err == -ENOENT)970 err = -EINVAL;971 return err;972 }973 ubifs_assert(c, *n == 0);974 *n = -1;975 }976 break;977 }978 err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm);979 if (err < 0)980 return err;981 if (err == NAME_MATCHES)982 return 1;983 if (err == NOT_ON_MEDIA) {984 o_znode = *zn;985 o_n = *n;986 continue;987 }988 if (!adding)989 continue;990 if (err == NAME_LESS)991 break;992 else993 unsure = 0;994 }995 }996 997 if (cmp == NAME_LESS || unsure) {998 /* Look right */999 *zn = znode;1000 *n = nn;1001 while (1) {1002 err = tnc_next(c, &znode, &nn);1003 if (err == -ENOENT)1004 break;1005 if (err < 0)1006 return err;1007 if (keys_cmp(c, &znode->zbranch[nn].key, key))1008 break;1009 err = fallible_matches_name(c, &znode->zbranch[nn], nm);1010 if (err < 0)1011 return err;1012 if (err == NAME_GREATER)1013 break;1014 *zn = znode;1015 *n = nn;1016 if (err == NAME_MATCHES)1017 return 1;1018 if (err == NOT_ON_MEDIA) {1019 o_znode = znode;1020 o_n = nn;1021 }1022 }1023 }1024 1025 /* Never match a dangling branch when adding */1026 if (adding || !o_znode)1027 return 0;1028 1029 dbg_mntk(key, "dangling match LEB %d:%d len %d key ",1030 o_znode->zbranch[o_n].lnum, o_znode->zbranch[o_n].offs,1031 o_znode->zbranch[o_n].len);1032 *zn = o_znode;1033 *n = o_n;1034 return 1;1035}1036 1037/**1038 * matches_position - determine if a zbranch matches a given position.1039 * @zbr: zbranch of dent1040 * @lnum: LEB number of dent to match1041 * @offs: offset of dent to match1042 *1043 * This function returns %1 if @lnum:@offs matches, and %0 otherwise.1044 */1045static int matches_position(struct ubifs_zbranch *zbr, int lnum, int offs)1046{1047 if (zbr->lnum == lnum && zbr->offs == offs)1048 return 1;1049 else1050 return 0;1051}1052 1053/**1054 * resolve_collision_directly - resolve a collision directly.1055 * @c: UBIFS file-system description object1056 * @key: key of directory entry1057 * @zn: znode is passed and returned here1058 * @n: zbranch number is passed and returned here1059 * @lnum: LEB number of dent node to match1060 * @offs: offset of dent node to match1061 *1062 * This function is used for "hashed" keys to make sure the found directory or1063 * extended attribute entry node is what was looked for. It is used when the1064 * flash address of the right node is known (@lnum:@offs) which makes it much1065 * easier to resolve collisions (no need to read entries and match full1066 * names). This function returns %1 and sets @zn and @n if the collision is1067 * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the1068 * previous directory entry. Otherwise a negative error code is returned.1069 */1070static int resolve_collision_directly(struct ubifs_info *c,1071 const union ubifs_key *key,1072 struct ubifs_znode **zn, int *n,1073 int lnum, int offs)1074{1075 struct ubifs_znode *znode;1076 int nn, err;1077 1078 znode = *zn;1079 nn = *n;1080 if (matches_position(&znode->zbranch[nn], lnum, offs))1081 return 1;1082 1083 /* Look left */1084 while (1) {1085 err = tnc_prev(c, &znode, &nn);1086 if (err == -ENOENT)1087 break;1088 if (err < 0)1089 return err;1090 if (keys_cmp(c, &znode->zbranch[nn].key, key))1091 break;1092 if (matches_position(&znode->zbranch[nn], lnum, offs)) {1093 *zn = znode;1094 *n = nn;1095 return 1;1096 }1097 }1098 1099 /* Look right */1100 znode = *zn;1101 nn = *n;1102 while (1) {1103 err = tnc_next(c, &znode, &nn);1104 if (err == -ENOENT)1105 return 0;1106 if (err < 0)1107 return err;1108 if (keys_cmp(c, &znode->zbranch[nn].key, key))1109 return 0;1110 *zn = znode;1111 *n = nn;1112 if (matches_position(&znode->zbranch[nn], lnum, offs))1113 return 1;1114 }1115}1116 1117/**1118 * dirty_cow_bottom_up - dirty a znode and its ancestors.1119 * @c: UBIFS file-system description object1120 * @znode: znode to dirty1121 *1122 * If we do not have a unique key that resides in a znode, then we cannot1123 * dirty that znode from the top down (i.e. by using lookup_level0_dirty)1124 * This function records the path back to the last dirty ancestor, and then1125 * dirties the znodes on that path.1126 */1127static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c,1128 struct ubifs_znode *znode)1129{1130 struct ubifs_znode *zp;1131 int *path = c->bottom_up_buf, p = 0;1132 1133 ubifs_assert(c, c->zroot.znode);1134 ubifs_assert(c, znode);1135 if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) {1136 kfree(c->bottom_up_buf);1137 c->bottom_up_buf = kmalloc_array(c->zroot.znode->level,1138 sizeof(int),1139 GFP_NOFS);1140 if (!c->bottom_up_buf)1141 return ERR_PTR(-ENOMEM);1142 path = c->bottom_up_buf;1143 }1144 if (c->zroot.znode->level) {1145 /* Go up until parent is dirty */1146 while (1) {1147 int n;1148 1149 zp = znode->parent;1150 if (!zp)1151 break;1152 n = znode->iip;1153 ubifs_assert(c, p < c->zroot.znode->level);1154 path[p++] = n;1155 if (!zp->cnext && ubifs_zn_dirty(znode))1156 break;1157 znode = zp;1158 }1159 }1160 1161 /* Come back down, dirtying as we go */1162 while (1) {1163 struct ubifs_zbranch *zbr;1164 1165 zp = znode->parent;1166 if (zp) {1167 ubifs_assert(c, path[p - 1] >= 0);1168 ubifs_assert(c, path[p - 1] < zp->child_cnt);1169 zbr = &zp->zbranch[path[--p]];1170 znode = dirty_cow_znode(c, zbr);1171 } else {1172 ubifs_assert(c, znode == c->zroot.znode);1173 znode = dirty_cow_znode(c, &c->zroot);1174 }1175 if (IS_ERR(znode) || !p)1176 break;1177 ubifs_assert(c, path[p - 1] >= 0);1178 ubifs_assert(c, path[p - 1] < znode->child_cnt);1179 znode = znode->zbranch[path[p - 1]].znode;1180 }1181 1182 return znode;1183}1184 1185/**1186 * ubifs_lookup_level0 - search for zero-level znode.1187 * @c: UBIFS file-system description object1188 * @key: key to lookup1189 * @zn: znode is returned here1190 * @n: znode branch slot number is returned here1191 *1192 * This function looks up the TNC tree and search for zero-level znode which1193 * refers key @key. The found zero-level znode is returned in @zn. There are 31194 * cases:1195 * o exact match, i.e. the found zero-level znode contains key @key, then %11196 * is returned and slot number of the matched branch is stored in @n;1197 * o not exact match, which means that zero-level znode does not contain1198 * @key, then %0 is returned and slot number of the closest branch or %-11199 * is stored in @n; In this case calling tnc_next() is mandatory.1200 * o @key is so small that it is even less than the lowest key of the1201 * leftmost zero-level node, then %0 is returned and %0 is stored in @n.1202 *1203 * Note, when the TNC tree is traversed, some znodes may be absent, then this1204 * function reads corresponding indexing nodes and inserts them to TNC. In1205 * case of failure, a negative error code is returned.1206 */1207int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,1208 struct ubifs_znode **zn, int *n)1209{1210 int err, exact;1211 struct ubifs_znode *znode;1212 time64_t time = ktime_get_seconds();1213 1214 dbg_tnck(key, "search key ");1215 ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);1216 1217 znode = c->zroot.znode;1218 if (unlikely(!znode)) {1219 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);1220 if (IS_ERR(znode))1221 return PTR_ERR(znode);1222 }1223 1224 znode->time = time;1225 1226 while (1) {1227 struct ubifs_zbranch *zbr;1228 1229 exact = ubifs_search_zbranch(c, znode, key, n);1230 1231 if (znode->level == 0)1232 break;1233 1234 if (*n < 0)1235 *n = 0;1236 zbr = &znode->zbranch[*n];1237 1238 if (zbr->znode) {1239 znode->time = time;1240 znode = zbr->znode;1241 continue;1242 }1243 1244 /* znode is not in TNC cache, load it from the media */1245 znode = ubifs_load_znode(c, zbr, znode, *n);1246 if (IS_ERR(znode))1247 return PTR_ERR(znode);1248 }1249 1250 *zn = znode;1251 if (exact || !is_hash_key(c, key) || *n != -1) {1252 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);1253 return exact;1254 }1255 1256 /*1257 * Here is a tricky place. We have not found the key and this is a1258 * "hashed" key, which may collide. The rest of the code deals with1259 * situations like this:1260 *1261 * | 3 | 5 |1262 * / \1263 * | 3 | 5 | | 6 | 7 | (x)1264 *1265 * Or more a complex example:1266 *1267 * | 1 | 5 |1268 * / \1269 * | 1 | 3 | | 5 | 8 |1270 * \ /1271 * | 5 | 5 | | 6 | 7 | (x)1272 *1273 * In the examples, if we are looking for key "5", we may reach nodes1274 * marked with "(x)". In this case what we have do is to look at the1275 * left and see if there is "5" key there. If there is, we have to1276 * return it.1277 *1278 * Note, this whole situation is possible because we allow to have1279 * elements which are equivalent to the next key in the parent in the1280 * children of current znode. For example, this happens if we split a1281 * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something1282 * like this:1283 * | 3 | 5 |1284 * / \1285 * | 3 | 5 | | 5 | 6 | 7 |1286 * ^1287 * And this becomes what is at the first "picture" after key "5" marked1288 * with "^" is removed. What could be done is we could prohibit1289 * splitting in the middle of the colliding sequence. Also, when1290 * removing the leftmost key, we would have to correct the key of the1291 * parent node, which would introduce additional complications. Namely,1292 * if we changed the leftmost key of the parent znode, the garbage1293 * collector would be unable to find it (GC is doing this when GC'ing1294 * indexing LEBs). Although we already have an additional RB-tree where1295 * we save such changed znodes (see 'ins_clr_old_idx_znode()') until1296 * after the commit. But anyway, this does not look easy to implement1297 * so we did not try this.1298 */1299 err = tnc_prev(c, &znode, n);1300 if (err == -ENOENT) {1301 dbg_tnc("found 0, lvl %d, n -1", znode->level);1302 *n = -1;1303 return 0;1304 }1305 if (unlikely(err < 0))1306 return err;1307 if (keys_cmp(c, key, &znode->zbranch[*n].key)) {1308 dbg_tnc("found 0, lvl %d, n -1", znode->level);1309 *n = -1;1310 return 0;1311 }1312 1313 dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);1314 *zn = znode;1315 return 1;1316}1317 1318/**1319 * lookup_level0_dirty - search for zero-level znode dirtying.1320 * @c: UBIFS file-system description object1321 * @key: key to lookup1322 * @zn: znode is returned here1323 * @n: znode branch slot number is returned here1324 *1325 * This function looks up the TNC tree and search for zero-level znode which1326 * refers key @key. The found zero-level znode is returned in @zn. There are 31327 * cases:1328 * o exact match, i.e. the found zero-level znode contains key @key, then %11329 * is returned and slot number of the matched branch is stored in @n;1330 * o not exact match, which means that zero-level znode does not contain @key1331 * then %0 is returned and slot number of the closed branch is stored in1332 * @n;1333 * o @key is so small that it is even less than the lowest key of the1334 * leftmost zero-level node, then %0 is returned and %-1 is stored in @n.1335 *1336 * Additionally all znodes in the path from the root to the located zero-level1337 * znode are marked as dirty.1338 *1339 * Note, when the TNC tree is traversed, some znodes may be absent, then this1340 * function reads corresponding indexing nodes and inserts them to TNC. In1341 * case of failure, a negative error code is returned.1342 */1343static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,1344 struct ubifs_znode **zn, int *n)1345{1346 int err, exact;1347 struct ubifs_znode *znode;1348 time64_t time = ktime_get_seconds();1349 1350 dbg_tnck(key, "search and dirty key ");1351 1352 znode = c->zroot.znode;1353 if (unlikely(!znode)) {1354 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);1355 if (IS_ERR(znode))1356 return PTR_ERR(znode);1357 }1358 1359 znode = dirty_cow_znode(c, &c->zroot);1360 if (IS_ERR(znode))1361 return PTR_ERR(znode);1362 1363 znode->time = time;1364 1365 while (1) {1366 struct ubifs_zbranch *zbr;1367 1368 exact = ubifs_search_zbranch(c, znode, key, n);1369 1370 if (znode->level == 0)1371 break;1372 1373 if (*n < 0)1374 *n = 0;1375 zbr = &znode->zbranch[*n];1376 1377 if (zbr->znode) {1378 znode->time = time;1379 znode = dirty_cow_znode(c, zbr);1380 if (IS_ERR(znode))1381 return PTR_ERR(znode);1382 continue;1383 }1384 1385 /* znode is not in TNC cache, load it from the media */1386 znode = ubifs_load_znode(c, zbr, znode, *n);1387 if (IS_ERR(znode))1388 return PTR_ERR(znode);1389 znode = dirty_cow_znode(c, zbr);1390 if (IS_ERR(znode))1391 return PTR_ERR(znode);1392 }1393 1394 *zn = znode;1395 if (exact || !is_hash_key(c, key) || *n != -1) {1396 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);1397 return exact;1398 }1399 1400 /*1401 * See huge comment at 'lookup_level0_dirty()' what is the rest of the1402 * code.1403 */1404 err = tnc_prev(c, &znode, n);1405 if (err == -ENOENT) {1406 *n = -1;1407 dbg_tnc("found 0, lvl %d, n -1", znode->level);1408 return 0;1409 }1410 if (unlikely(err < 0))1411 return err;1412 if (keys_cmp(c, key, &znode->zbranch[*n].key)) {1413 *n = -1;1414 dbg_tnc("found 0, lvl %d, n -1", znode->level);1415 return 0;1416 }1417 1418 if (znode->cnext || !ubifs_zn_dirty(znode)) {1419 znode = dirty_cow_bottom_up(c, znode);1420 if (IS_ERR(znode))1421 return PTR_ERR(znode);1422 }1423 1424 dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);1425 *zn = znode;1426 return 1;1427}1428 1429/**1430 * maybe_leb_gced - determine if a LEB may have been garbage collected.1431 * @c: UBIFS file-system description object1432 * @lnum: LEB number1433 * @gc_seq1: garbage collection sequence number1434 *1435 * This function determines if @lnum may have been garbage collected since1436 * sequence number @gc_seq1. If it may have been then %1 is returned, otherwise1437 * %0 is returned.1438 */1439static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1)1440{1441 int gc_seq2, gced_lnum;1442 1443 gced_lnum = c->gced_lnum;1444 smp_rmb();1445 gc_seq2 = c->gc_seq;1446 /* Same seq means no GC */1447 if (gc_seq1 == gc_seq2)1448 return 0;1449 /* Different by more than 1 means we don't know */1450 if (gc_seq1 + 1 != gc_seq2)1451 return 1;1452 /*1453 * We have seen the sequence number has increased by 1. Now we need to1454 * be sure we read the right LEB number, so read it again.1455 */1456 smp_rmb();1457 if (gced_lnum != c->gced_lnum)1458 return 1;1459 /* Finally we can check lnum */1460 if (gced_lnum == lnum)1461 return 1;1462 return 0;1463}1464 1465/**1466 * ubifs_tnc_locate - look up a file-system node and return it and its location.1467 * @c: UBIFS file-system description object1468 * @key: node key to lookup1469 * @node: the node is returned here1470 * @lnum: LEB number is returned here1471 * @offs: offset is returned here1472 *1473 * This function looks up and reads node with key @key. The caller has to make1474 * sure the @node buffer is large enough to fit the node. Returns zero in case1475 * of success, %-ENOENT if the node was not found, and a negative error code in1476 * case of failure. The node location can be returned in @lnum and @offs.1477 */1478int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,1479 void *node, int *lnum, int *offs)1480{1481 int found, n, err, safely = 0, gc_seq1;1482 struct ubifs_znode *znode;1483 struct ubifs_zbranch zbr, *zt;1484 1485again:1486 mutex_lock(&c->tnc_mutex);1487 found = ubifs_lookup_level0(c, key, &znode, &n);1488 if (!found) {1489 err = -ENOENT;1490 goto out;1491 } else if (found < 0) {1492 err = found;1493 goto out;1494 }1495 zt = &znode->zbranch[n];1496 if (lnum) {1497 *lnum = zt->lnum;1498 *offs = zt->offs;1499 }1500 if (is_hash_key(c, key)) {1501 /*1502 * In this case the leaf node cache gets used, so we pass the1503 * address of the zbranch and keep the mutex locked1504 */1505 err = tnc_read_hashed_node(c, zt, node);1506 goto out;1507 }1508 if (safely) {1509 err = ubifs_tnc_read_node(c, zt, node);1510 goto out;1511 }1512 /* Drop the TNC mutex prematurely and race with garbage collection */1513 zbr = znode->zbranch[n];1514 gc_seq1 = c->gc_seq;1515 mutex_unlock(&c->tnc_mutex);1516 1517 if (ubifs_get_wbuf(c, zbr.lnum)) {1518 /* We do not GC journal heads */1519 err = ubifs_tnc_read_node(c, &zbr, node);1520 return err;1521 }1522 1523 err = fallible_read_node(c, key, &zbr, node);1524 if (err <= 0 || maybe_leb_gced(c, zbr.lnum, gc_seq1)) {1525 /*1526 * The node may have been GC'ed out from under us so try again1527 * while keeping the TNC mutex locked.1528 */1529 safely = 1;1530 goto again;1531 }1532 return 0;1533 1534out:1535 mutex_unlock(&c->tnc_mutex);1536 return err;1537}1538 1539/**1540 * ubifs_tnc_get_bu_keys - lookup keys for bulk-read.1541 * @c: UBIFS file-system description object1542 * @bu: bulk-read parameters and results1543 *1544 * Lookup consecutive data node keys for the same inode that reside1545 * consecutively in the same LEB. This function returns zero in case of success1546 * and a negative error code in case of failure.1547 *1548 * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function1549 * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares1550 * maximum possible amount of nodes for bulk-read.1551 */1552int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu)1553{1554 int n, err = 0, lnum = -1, offs;1555 int len;1556 unsigned int block = key_block(c, &bu->key);1557 struct ubifs_znode *znode;1558 1559 bu->cnt = 0;1560 bu->blk_cnt = 0;1561 bu->eof = 0;1562 1563 mutex_lock(&c->tnc_mutex);1564 /* Find first key */1565 err = ubifs_lookup_level0(c, &bu->key, &znode, &n);1566 if (err < 0)1567 goto out;1568 if (err) {1569 /* Key found */1570 len = znode->zbranch[n].len;1571 /* The buffer must be big enough for at least 1 node */1572 if (len > bu->buf_len) {1573 err = -EINVAL;1574 goto out;1575 }1576 /* Add this key */1577 bu->zbranch[bu->cnt++] = znode->zbranch[n];1578 bu->blk_cnt += 1;1579 lnum = znode->zbranch[n].lnum;1580 offs = ALIGN(znode->zbranch[n].offs + len, 8);1581 }1582 while (1) {1583 struct ubifs_zbranch *zbr;1584 union ubifs_key *key;1585 unsigned int next_block;1586 1587 /* Find next key */1588 err = tnc_next(c, &znode, &n);1589 if (err)1590 goto out;1591 zbr = &znode->zbranch[n];1592 key = &zbr->key;1593 /* See if there is another data key for this file */1594 if (key_inum(c, key) != key_inum(c, &bu->key) ||1595 key_type(c, key) != UBIFS_DATA_KEY) {1596 err = -ENOENT;1597 goto out;1598 }1599 if (lnum < 0) {1600 /* First key found */1601 lnum = zbr->lnum;1602 offs = ALIGN(zbr->offs + zbr->len, 8);1603 len = zbr->len;1604 if (len > bu->buf_len) {1605 err = -EINVAL;1606 goto out;1607 }1608 } else {1609 /*1610 * The data nodes must be in consecutive positions in1611 * the same LEB.1612 */1613 if (zbr->lnum != lnum || zbr->offs != offs)1614 goto out;1615 offs += ALIGN(zbr->len, 8);1616 len = ALIGN(len, 8) + zbr->len;1617 /* Must not exceed buffer length */1618 if (len > bu->buf_len)1619 goto out;1620 }1621 /* Allow for holes */1622 next_block = key_block(c, key);1623 bu->blk_cnt += (next_block - block - 1);1624 if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)1625 goto out;1626 block = next_block;1627 /* Add this key */1628 bu->zbranch[bu->cnt++] = *zbr;1629 bu->blk_cnt += 1;1630 /* See if we have room for more */1631 if (bu->cnt >= UBIFS_MAX_BULK_READ)1632 goto out;1633 if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)1634 goto out;1635 }1636out:1637 if (err == -ENOENT) {1638 bu->eof = 1;1639 err = 0;1640 }1641 bu->gc_seq = c->gc_seq;1642 mutex_unlock(&c->tnc_mutex);1643 if (err)1644 return err;1645 /*1646 * An enormous hole could cause bulk-read to encompass too many1647 * page cache pages, so limit the number here.1648 */1649 if (bu->blk_cnt > UBIFS_MAX_BULK_READ)1650 bu->blk_cnt = UBIFS_MAX_BULK_READ;1651 /*1652 * Ensure that bulk-read covers a whole number of page cache1653 * pages.1654 */1655 if (UBIFS_BLOCKS_PER_PAGE == 1 ||1656 !(bu->blk_cnt & (UBIFS_BLOCKS_PER_PAGE - 1)))1657 return 0;1658 if (bu->eof) {1659 /* At the end of file we can round up */1660 bu->blk_cnt += UBIFS_BLOCKS_PER_PAGE - 1;1661 return 0;1662 }1663 /* Exclude data nodes that do not make up a whole page cache page */1664 block = key_block(c, &bu->key) + bu->blk_cnt;1665 block &= ~(UBIFS_BLOCKS_PER_PAGE - 1);1666 while (bu->cnt) {1667 if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block)1668 break;1669 bu->cnt -= 1;1670 }1671 return 0;1672}1673 1674/**1675 * read_wbuf - bulk-read from a LEB with a wbuf.1676 * @wbuf: wbuf that may overlap the read1677 * @buf: buffer into which to read1678 * @len: read length1679 * @lnum: LEB number from which to read1680 * @offs: offset from which to read1681 *1682 * This functions returns %0 on success or a negative error code on failure.1683 */1684static int read_wbuf(struct ubifs_wbuf *wbuf, void *buf, int len, int lnum,1685 int offs)1686{1687 const struct ubifs_info *c = wbuf->c;1688 int rlen, overlap;1689 1690 dbg_io("LEB %d:%d, length %d", lnum, offs, len);1691 ubifs_assert(c, wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0);1692 ubifs_assert(c, !(offs & 7) && offs < c->leb_size);1693 ubifs_assert(c, offs + len <= c->leb_size);1694 1695 spin_lock(&wbuf->lock);1696 overlap = (lnum == wbuf->lnum && offs + len > wbuf->offs);1697 if (!overlap) {1698 /* We may safely unlock the write-buffer and read the data */1699 spin_unlock(&wbuf->lock);1700 return ubifs_leb_read(c, lnum, buf, offs, len, 0);1701 }1702 1703 /* Don't read under wbuf */1704 rlen = wbuf->offs - offs;1705 if (rlen < 0)1706 rlen = 0;1707 1708 /* Copy the rest from the write-buffer */1709 memcpy(buf + rlen, wbuf->buf + offs + rlen - wbuf->offs, len - rlen);1710 spin_unlock(&wbuf->lock);1711 1712 if (rlen > 0)1713 /* Read everything that goes before write-buffer */1714 return ubifs_leb_read(c, lnum, buf, offs, rlen, 0);1715 1716 return 0;1717}1718 1719/**1720 * validate_data_node - validate data nodes for bulk-read.1721 * @c: UBIFS file-system description object1722 * @buf: buffer containing data node to validate1723 * @zbr: zbranch of data node to validate1724 *1725 * This functions returns %0 on success or a negative error code on failure.1726 */1727static int validate_data_node(struct ubifs_info *c, void *buf,1728 struct ubifs_zbranch *zbr)1729{1730 union ubifs_key key1;1731 struct ubifs_ch *ch = buf;1732 int err, len;1733 1734 if (ch->node_type != UBIFS_DATA_NODE) {1735 ubifs_err(c, "bad node type (%d but expected %d)",1736 ch->node_type, UBIFS_DATA_NODE);1737 goto out_err;1738 }1739 1740 err = ubifs_check_node(c, buf, zbr->len, zbr->lnum, zbr->offs, 0, 0);1741 if (err) {1742 ubifs_err(c, "expected node type %d", UBIFS_DATA_NODE);1743 goto out;1744 }1745 1746 err = ubifs_node_check_hash(c, buf, zbr->hash);1747 if (err) {1748 ubifs_bad_hash(c, buf, zbr->hash, zbr->lnum, zbr->offs);1749 return err;1750 }1751 1752 len = le32_to_cpu(ch->len);1753 if (len != zbr->len) {1754 ubifs_err(c, "bad node length %d, expected %d", len, zbr->len);1755 goto out_err;1756 }1757 1758 /* Make sure the key of the read node is correct */1759 key_read(c, buf + UBIFS_KEY_OFFSET, &key1);1760 if (!keys_eq(c, &zbr->key, &key1)) {1761 ubifs_err(c, "bad key in node at LEB %d:%d",1762 zbr->lnum, zbr->offs);1763 dbg_tnck(&zbr->key, "looked for key ");1764 dbg_tnck(&key1, "found node's key ");1765 goto out_err;1766 }1767 1768 return 0;1769 1770out_err:1771 err = -EINVAL;1772out:1773 ubifs_err(c, "bad node at LEB %d:%d", zbr->lnum, zbr->offs);1774 ubifs_dump_node(c, buf, zbr->len);1775 dump_stack();1776 return err;1777}1778 1779/**1780 * ubifs_tnc_bulk_read - read a number of data nodes in one go.1781 * @c: UBIFS file-system description object1782 * @bu: bulk-read parameters and results1783 *1784 * This functions reads and validates the data nodes that were identified by the1785 * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success,1786 * -EAGAIN to indicate a race with GC, or another negative error code on1787 * failure.1788 */1789int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu)1790{1791 int lnum = bu->zbranch[0].lnum, offs = bu->zbranch[0].offs, len, err, i;1792 struct ubifs_wbuf *wbuf;1793 void *buf;1794 1795 len = bu->zbranch[bu->cnt - 1].offs;1796 len += bu->zbranch[bu->cnt - 1].len - offs;1797 if (len > bu->buf_len) {1798 ubifs_err(c, "buffer too small %d vs %d", bu->buf_len, len);1799 return -EINVAL;1800 }1801 1802 /* Do the read */1803 wbuf = ubifs_get_wbuf(c, lnum);1804 if (wbuf)1805 err = read_wbuf(wbuf, bu->buf, len, lnum, offs);1806 else1807 err = ubifs_leb_read(c, lnum, bu->buf, offs, len, 0);1808 1809 /* Check for a race with GC */1810 if (maybe_leb_gced(c, lnum, bu->gc_seq))1811 return -EAGAIN;1812 1813 if (err && err != -EBADMSG) {1814 ubifs_err(c, "failed to read from LEB %d:%d, error %d",1815 lnum, offs, err);1816 dump_stack();1817 dbg_tnck(&bu->key, "key ");1818 return err;1819 }1820 1821 /* Validate the nodes read */1822 buf = bu->buf;1823 for (i = 0; i < bu->cnt; i++) {1824 err = validate_data_node(c, buf, &bu->zbranch[i]);1825 if (err)1826 return err;1827 buf = buf + ALIGN(bu->zbranch[i].len, 8);1828 }1829 1830 return 0;1831}1832 1833/**1834 * do_lookup_nm- look up a "hashed" node.1835 * @c: UBIFS file-system description object1836 * @key: node key to lookup1837 * @node: the node is returned here1838 * @nm: node name1839 *1840 * This function looks up and reads a node which contains name hash in the key.1841 * Since the hash may have collisions, there may be many nodes with the same1842 * key, so we have to sequentially look to all of them until the needed one is1843 * found. This function returns zero in case of success, %-ENOENT if the node1844 * was not found, and a negative error code in case of failure.1845 */1846static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,1847 void *node, const struct fscrypt_name *nm)1848{1849 int found, n, err;1850 struct ubifs_znode *znode;1851 1852 dbg_tnck(key, "key ");1853 mutex_lock(&c->tnc_mutex);1854 found = ubifs_lookup_level0(c, key, &znode, &n);1855 if (!found) {1856 err = -ENOENT;1857 goto out_unlock;1858 } else if (found < 0) {1859 err = found;1860 goto out_unlock;1861 }1862 1863 ubifs_assert(c, n >= 0);1864 1865 err = resolve_collision(c, key, &znode, &n, nm);1866 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);1867 if (unlikely(err < 0))1868 goto out_unlock;1869 if (err == 0) {1870 err = -ENOENT;1871 goto out_unlock;1872 }1873 1874 err = tnc_read_hashed_node(c, &znode->zbranch[n], node);1875 1876out_unlock:1877 mutex_unlock(&c->tnc_mutex);1878 return err;1879}1880 1881/**1882 * ubifs_tnc_lookup_nm - look up a "hashed" node.1883 * @c: UBIFS file-system description object1884 * @key: node key to lookup1885 * @node: the node is returned here1886 * @nm: node name1887 *1888 * This function looks up and reads a node which contains name hash in the key.1889 * Since the hash may have collisions, there may be many nodes with the same1890 * key, so we have to sequentially look to all of them until the needed one is1891 * found. This function returns zero in case of success, %-ENOENT if the node1892 * was not found, and a negative error code in case of failure.1893 */1894int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,1895 void *node, const struct fscrypt_name *nm)1896{1897 int err, len;1898 const struct ubifs_dent_node *dent = node;1899 1900 /*1901 * We assume that in most of the cases there are no name collisions and1902 * 'ubifs_tnc_lookup()' returns us the right direntry.1903 */1904 err = ubifs_tnc_lookup(c, key, node);1905 if (err)1906 return err;1907 1908 len = le16_to_cpu(dent->nlen);1909 if (fname_len(nm) == len && !memcmp(dent->name, fname_name(nm), len))1910 return 0;1911 1912 /*1913 * Unluckily, there are hash collisions and we have to iterate over1914 * them look at each direntry with colliding name hash sequentially.1915 */1916 1917 return do_lookup_nm(c, key, node, nm);1918}1919 1920static int search_dh_cookie(struct ubifs_info *c, const union ubifs_key *key,1921 struct ubifs_dent_node *dent, uint32_t cookie,1922 struct ubifs_znode **zn, int *n, int exact)1923{1924 int err;1925 struct ubifs_znode *znode = *zn;1926 struct ubifs_zbranch *zbr;1927 union ubifs_key *dkey;1928 1929 if (!exact) {1930 err = tnc_next(c, &znode, n);1931 if (err)1932 return err;1933 }1934 1935 for (;;) {1936 zbr = &znode->zbranch[*n];1937 dkey = &zbr->key;1938 1939 if (key_inum(c, dkey) != key_inum(c, key) ||1940 key_type(c, dkey) != key_type(c, key)) {1941 return -ENOENT;1942 }1943 1944 err = tnc_read_hashed_node(c, zbr, dent);1945 if (err)1946 return err;1947 1948 if (key_hash(c, key) == key_hash(c, dkey) &&1949 le32_to_cpu(dent->cookie) == cookie) {1950 *zn = znode;1951 return 0;1952 }1953 1954 err = tnc_next(c, &znode, n);1955 if (err)1956 return err;1957 }1958}1959 1960static int do_lookup_dh(struct ubifs_info *c, const union ubifs_key *key,1961 struct ubifs_dent_node *dent, uint32_t cookie)1962{1963 int n, err;1964 struct ubifs_znode *znode;1965 union ubifs_key start_key;1966 1967 ubifs_assert(c, is_hash_key(c, key));1968 1969 lowest_dent_key(c, &start_key, key_inum(c, key));1970 1971 mutex_lock(&c->tnc_mutex);1972 err = ubifs_lookup_level0(c, &start_key, &znode, &n);1973 if (unlikely(err < 0))1974 goto out_unlock;1975 1976 err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err);1977 1978out_unlock:1979 mutex_unlock(&c->tnc_mutex);1980 return err;1981}1982 1983/**1984 * ubifs_tnc_lookup_dh - look up a "double hashed" node.1985 * @c: UBIFS file-system description object1986 * @key: node key to lookup1987 * @node: the node is returned here1988 * @cookie: node cookie for collision resolution1989 *1990 * This function looks up and reads a node which contains name hash in the key.1991 * Since the hash may have collisions, there may be many nodes with the same1992 * key, so we have to sequentially look to all of them until the needed one1993 * with the same cookie value is found.1994 * This function returns zero in case of success, %-ENOENT if the node1995 * was not found, and a negative error code in case of failure.1996 */1997int ubifs_tnc_lookup_dh(struct ubifs_info *c, const union ubifs_key *key,1998 void *node, uint32_t cookie)1999{2000 int err;2001 const struct ubifs_dent_node *dent = node;2002 2003 if (!c->double_hash)2004 return -EOPNOTSUPP;2005 2006 /*2007 * We assume that in most of the cases there are no name collisions and2008 * 'ubifs_tnc_lookup()' returns us the right direntry.2009 */2010 err = ubifs_tnc_lookup(c, key, node);2011 if (err)2012 return err;2013 2014 if (le32_to_cpu(dent->cookie) == cookie)2015 return 0;2016 2017 /*2018 * Unluckily, there are hash collisions and we have to iterate over2019 * them look at each direntry with colliding name hash sequentially.2020 */2021 return do_lookup_dh(c, key, node, cookie);2022}2023 2024/**2025 * correct_parent_keys - correct parent znodes' keys.2026 * @c: UBIFS file-system description object2027 * @znode: znode to correct parent znodes for2028 *2029 * This is a helper function for 'tnc_insert()'. When the key of the leftmost2030 * zbranch changes, keys of parent znodes have to be corrected. This helper2031 * function is called in such situations and corrects the keys if needed.2032 */2033static void correct_parent_keys(const struct ubifs_info *c,2034 struct ubifs_znode *znode)2035{2036 union ubifs_key *key, *key1;2037 2038 ubifs_assert(c, znode->parent);2039 ubifs_assert(c, znode->iip == 0);2040 2041 key = &znode->zbranch[0].key;2042 key1 = &znode->parent->zbranch[0].key;2043 2044 while (keys_cmp(c, key, key1) < 0) {2045 key_copy(c, key, key1);2046 znode = znode->parent;2047 znode->alt = 1;2048 if (!znode->parent || znode->iip)2049 break;2050 key1 = &znode->parent->zbranch[0].key;2051 }2052}2053 2054/**2055 * insert_zbranch - insert a zbranch into a znode.2056 * @c: UBIFS file-system description object2057 * @znode: znode into which to insert2058 * @zbr: zbranch to insert2059 * @n: slot number to insert to2060 *2061 * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in2062 * znode's array of zbranches and keeps zbranches consolidated, so when a new2063 * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th2064 * slot, zbranches starting from @n have to be moved right.2065 */2066static void insert_zbranch(struct ubifs_info *c, struct ubifs_znode *znode,2067 const struct ubifs_zbranch *zbr, int n)2068{2069 int i;2070 2071 ubifs_assert(c, ubifs_zn_dirty(znode));2072 2073 if (znode->level) {2074 for (i = znode->child_cnt; i > n; i--) {2075 znode->zbranch[i] = znode->zbranch[i - 1];2076 if (znode->zbranch[i].znode)2077 znode->zbranch[i].znode->iip = i;2078 }2079 if (zbr->znode)2080 zbr->znode->iip = n;2081 } else2082 for (i = znode->child_cnt; i > n; i--)2083 znode->zbranch[i] = znode->zbranch[i - 1];2084 2085 znode->zbranch[n] = *zbr;2086 znode->child_cnt += 1;2087 2088 /*2089 * After inserting at slot zero, the lower bound of the key range of2090 * this znode may have changed. If this znode is subsequently split2091 * then the upper bound of the key range may change, and furthermore2092 * it could change to be lower than the original lower bound. If that2093 * happens, then it will no longer be possible to find this znode in the2094 * TNC using the key from the index node on flash. That is bad because2095 * if it is not found, we will assume it is obsolete and may overwrite2096 * it. Then if there is an unclean unmount, we will start using the2097 * old index which will be broken.2098 *2099 * So we first mark znodes that have insertions at slot zero, and then2100 * if they are split we add their lnum/offs to the old_idx tree.2101 */2102 if (n == 0)2103 znode->alt = 1;2104}2105 2106/**2107 * tnc_insert - insert a node into TNC.2108 * @c: UBIFS file-system description object2109 * @znode: znode to insert into2110 * @zbr: branch to insert2111 * @n: slot number to insert new zbranch to2112 *2113 * This function inserts a new node described by @zbr into znode @znode. If2114 * znode does not have a free slot for new zbranch, it is split. Parent znodes2115 * are splat as well if needed. Returns zero in case of success or a negative2116 * error code in case of failure.2117 */2118static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,2119 struct ubifs_zbranch *zbr, int n)2120{2121 struct ubifs_znode *zn, *zi, *zp;2122 int i, keep, move, appending = 0;2123 union ubifs_key *key = &zbr->key, *key1;2124 2125 ubifs_assert(c, n >= 0 && n <= c->fanout);2126 2127 /* Implement naive insert for now */2128again:2129 zp = znode->parent;2130 if (znode->child_cnt < c->fanout) {2131 ubifs_assert(c, n != c->fanout);2132 dbg_tnck(key, "inserted at %d level %d, key ", n, znode->level);2133 2134 insert_zbranch(c, znode, zbr, n);2135 2136 /* Ensure parent's key is correct */2137 if (n == 0 && zp && znode->iip == 0)2138 correct_parent_keys(c, znode);2139 2140 return 0;2141 }2142 2143 /*2144 * Unfortunately, @znode does not have more empty slots and we have to2145 * split it.2146 */2147 dbg_tnck(key, "splitting level %d, key ", znode->level);2148 2149 if (znode->alt)2150 /*2151 * We can no longer be sure of finding this znode by key, so we2152 * record it in the old_idx tree.2153 */2154 ins_clr_old_idx_znode(c, znode);2155 2156 zn = kzalloc(c->max_znode_sz, GFP_NOFS);2157 if (!zn)2158 return -ENOMEM;2159 zn->parent = zp;2160 zn->level = znode->level;2161 2162 /* Decide where to split */2163 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {2164 /* Try not to split consecutive data keys */2165 if (n == c->fanout) {2166 key1 = &znode->zbranch[n - 1].key;2167 if (key_inum(c, key1) == key_inum(c, key) &&2168 key_type(c, key1) == UBIFS_DATA_KEY)2169 appending = 1;2170 } else2171 goto check_split;2172 } else if (appending && n != c->fanout) {2173 /* Try not to split consecutive data keys */2174 appending = 0;2175check_split:2176 if (n >= (c->fanout + 1) / 2) {2177 key1 = &znode->zbranch[0].key;2178 if (key_inum(c, key1) == key_inum(c, key) &&2179 key_type(c, key1) == UBIFS_DATA_KEY) {2180 key1 = &znode->zbranch[n].key;2181 if (key_inum(c, key1) != key_inum(c, key) ||2182 key_type(c, key1) != UBIFS_DATA_KEY) {2183 keep = n;2184 move = c->fanout - keep;2185 zi = znode;2186 goto do_split;2187 }2188 }2189 }2190 }2191 2192 if (appending) {2193 keep = c->fanout;2194 move = 0;2195 } else {2196 keep = (c->fanout + 1) / 2;2197 move = c->fanout - keep;2198 }2199 2200 /*2201 * Although we don't at present, we could look at the neighbors and see2202 * if we can move some zbranches there.2203 */2204 2205 if (n < keep) {2206 /* Insert into existing znode */2207 zi = znode;2208 move += 1;2209 keep -= 1;2210 } else {2211 /* Insert into new znode */2212 zi = zn;2213 n -= keep;2214 /* Re-parent */2215 if (zn->level != 0)2216 zbr->znode->parent = zn;2217 }2218 2219do_split:2220 2221 __set_bit(DIRTY_ZNODE, &zn->flags);2222 atomic_long_inc(&c->dirty_zn_cnt);2223 2224 zn->child_cnt = move;2225 znode->child_cnt = keep;2226 2227 dbg_tnc("moving %d, keeping %d", move, keep);2228 2229 /* Move zbranch */2230 for (i = 0; i < move; i++) {2231 zn->zbranch[i] = znode->zbranch[keep + i];2232 /* Re-parent */2233 if (zn->level != 0)2234 if (zn->zbranch[i].znode) {2235 zn->zbranch[i].znode->parent = zn;2236 zn->zbranch[i].znode->iip = i;2237 }2238 }2239 2240 /* Insert new key and branch */2241 dbg_tnck(key, "inserting at %d level %d, key ", n, zn->level);2242 2243 insert_zbranch(c, zi, zbr, n);2244 2245 /* Insert new znode (produced by spitting) into the parent */2246 if (zp) {2247 if (n == 0 && zi == znode && znode->iip == 0)2248 correct_parent_keys(c, znode);2249 2250 /* Locate insertion point */2251 n = znode->iip + 1;2252 2253 /* Tail recursion */2254 zbr->key = zn->zbranch[0].key;2255 zbr->znode = zn;2256 zbr->lnum = 0;2257 zbr->offs = 0;2258 zbr->len = 0;2259 znode = zp;2260 2261 goto again;2262 }2263 2264 /* We have to split root znode */2265 dbg_tnc("creating new zroot at level %d", znode->level + 1);2266 2267 zi = kzalloc(c->max_znode_sz, GFP_NOFS);2268 if (!zi)2269 return -ENOMEM;2270 2271 zi->child_cnt = 2;2272 zi->level = znode->level + 1;2273 2274 __set_bit(DIRTY_ZNODE, &zi->flags);2275 atomic_long_inc(&c->dirty_zn_cnt);2276 2277 zi->zbranch[0].key = znode->zbranch[0].key;2278 zi->zbranch[0].znode = znode;2279 zi->zbranch[0].lnum = c->zroot.lnum;2280 zi->zbranch[0].offs = c->zroot.offs;2281 zi->zbranch[0].len = c->zroot.len;2282 zi->zbranch[1].key = zn->zbranch[0].key;2283 zi->zbranch[1].znode = zn;2284 2285 c->zroot.lnum = 0;2286 c->zroot.offs = 0;2287 c->zroot.len = 0;2288 c->zroot.znode = zi;2289 2290 zn->parent = zi;2291 zn->iip = 1;2292 znode->parent = zi;2293 znode->iip = 0;2294 2295 return 0;2296}2297 2298/**2299 * ubifs_tnc_add - add a node to TNC.2300 * @c: UBIFS file-system description object2301 * @key: key to add2302 * @lnum: LEB number of node2303 * @offs: node offset2304 * @len: node length2305 * @hash: The hash over the node2306 *2307 * This function adds a node with key @key to TNC. The node may be new or it may2308 * obsolete some existing one. Returns %0 on success or negative error code on2309 * failure.2310 */2311int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,2312 int offs, int len, const u8 *hash)2313{2314 int found, n, err = 0;2315 struct ubifs_znode *znode;2316 2317 mutex_lock(&c->tnc_mutex);2318 dbg_tnck(key, "%d:%d, len %d, key ", lnum, offs, len);2319 found = lookup_level0_dirty(c, key, &znode, &n);2320 if (!found) {2321 struct ubifs_zbranch zbr;2322 2323 zbr.znode = NULL;2324 zbr.lnum = lnum;2325 zbr.offs = offs;2326 zbr.len = len;2327 ubifs_copy_hash(c, hash, zbr.hash);2328 key_copy(c, key, &zbr.key);2329 err = tnc_insert(c, znode, &zbr, n + 1);2330 } else if (found == 1) {2331 struct ubifs_zbranch *zbr = &znode->zbranch[n];2332 2333 lnc_free(zbr);2334 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);2335 zbr->lnum = lnum;2336 zbr->offs = offs;2337 zbr->len = len;2338 ubifs_copy_hash(c, hash, zbr->hash);2339 } else2340 err = found;2341 if (!err)2342 err = dbg_check_tnc(c, 0);2343 mutex_unlock(&c->tnc_mutex);2344 2345 return err;2346}2347 2348/**2349 * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.2350 * @c: UBIFS file-system description object2351 * @key: key to add2352 * @old_lnum: LEB number of old node2353 * @old_offs: old node offset2354 * @lnum: LEB number of node2355 * @offs: node offset2356 * @len: node length2357 *2358 * This function replaces a node with key @key in the TNC only if the old node2359 * is found. This function is called by garbage collection when node are moved.2360 * Returns %0 on success or negative error code on failure.2361 */2362int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,2363 int old_lnum, int old_offs, int lnum, int offs, int len)2364{2365 int found, n, err = 0;2366 struct ubifs_znode *znode;2367 2368 mutex_lock(&c->tnc_mutex);2369 dbg_tnck(key, "old LEB %d:%d, new LEB %d:%d, len %d, key ", old_lnum,2370 old_offs, lnum, offs, len);2371 found = lookup_level0_dirty(c, key, &znode, &n);2372 if (found < 0) {2373 err = found;2374 goto out_unlock;2375 }2376 2377 if (found == 1) {2378 struct ubifs_zbranch *zbr = &znode->zbranch[n];2379 2380 found = 0;2381 if (zbr->lnum == old_lnum && zbr->offs == old_offs) {2382 lnc_free(zbr);2383 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);2384 if (err)2385 goto out_unlock;2386 zbr->lnum = lnum;2387 zbr->offs = offs;2388 zbr->len = len;2389 found = 1;2390 } else if (is_hash_key(c, key)) {2391 found = resolve_collision_directly(c, key, &znode, &n,2392 old_lnum, old_offs);2393 dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",2394 found, znode, n, old_lnum, old_offs);2395 if (found < 0) {2396 err = found;2397 goto out_unlock;2398 }2399 2400 if (found) {2401 /* Ensure the znode is dirtied */2402 if (znode->cnext || !ubifs_zn_dirty(znode)) {2403 znode = dirty_cow_bottom_up(c, znode);2404 if (IS_ERR(znode)) {2405 err = PTR_ERR(znode);2406 goto out_unlock;2407 }2408 }2409 zbr = &znode->zbranch[n];2410 lnc_free(zbr);2411 err = ubifs_add_dirt(c, zbr->lnum,2412 zbr->len);2413 if (err)2414 goto out_unlock;2415 zbr->lnum = lnum;2416 zbr->offs = offs;2417 zbr->len = len;2418 }2419 }2420 }2421 2422 if (!found)2423 err = ubifs_add_dirt(c, lnum, len);2424 2425 if (!err)2426 err = dbg_check_tnc(c, 0);2427 2428out_unlock:2429 mutex_unlock(&c->tnc_mutex);2430 return err;2431}2432 2433/**2434 * ubifs_tnc_add_nm - add a "hashed" node to TNC.2435 * @c: UBIFS file-system description object2436 * @key: key to add2437 * @lnum: LEB number of node2438 * @offs: node offset2439 * @len: node length2440 * @hash: The hash over the node2441 * @nm: node name2442 *2443 * This is the same as 'ubifs_tnc_add()' but it should be used with keys which2444 * may have collisions, like directory entry keys.2445 */2446int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,2447 int lnum, int offs, int len, const u8 *hash,2448 const struct fscrypt_name *nm)2449{2450 int found, n, err = 0;2451 struct ubifs_znode *znode;2452 2453 mutex_lock(&c->tnc_mutex);2454 dbg_tnck(key, "LEB %d:%d, key ", lnum, offs);2455 found = lookup_level0_dirty(c, key, &znode, &n);2456 if (found < 0) {2457 err = found;2458 goto out_unlock;2459 }2460 2461 if (found == 1) {2462 if (c->replaying)2463 found = fallible_resolve_collision(c, key, &znode, &n,2464 nm, 1);2465 else2466 found = resolve_collision(c, key, &znode, &n, nm);2467 dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n);2468 if (found < 0) {2469 err = found;2470 goto out_unlock;2471 }2472 2473 /* Ensure the znode is dirtied */2474 if (znode->cnext || !ubifs_zn_dirty(znode)) {2475 znode = dirty_cow_bottom_up(c, znode);2476 if (IS_ERR(znode)) {2477 err = PTR_ERR(znode);2478 goto out_unlock;2479 }2480 }2481 2482 if (found == 1) {2483 struct ubifs_zbranch *zbr = &znode->zbranch[n];2484 2485 lnc_free(zbr);2486 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);2487 zbr->lnum = lnum;2488 zbr->offs = offs;2489 zbr->len = len;2490 ubifs_copy_hash(c, hash, zbr->hash);2491 goto out_unlock;2492 }2493 }2494 2495 if (!found) {2496 struct ubifs_zbranch zbr;2497 2498 zbr.znode = NULL;2499 zbr.lnum = lnum;2500 zbr.offs = offs;2501 zbr.len = len;2502 ubifs_copy_hash(c, hash, zbr.hash);2503 key_copy(c, key, &zbr.key);2504 err = tnc_insert(c, znode, &zbr, n + 1);2505 if (err)2506 goto out_unlock;2507 if (c->replaying) {2508 /*2509 * We did not find it in the index so there may be a2510 * dangling branch still in the index. So we remove it2511 * by passing 'ubifs_tnc_remove_nm()' the same key but2512 * an unmatchable name.2513 */2514 struct fscrypt_name noname = { .disk_name = { .name = "", .len = 1 } };2515 2516 err = dbg_check_tnc(c, 0);2517 mutex_unlock(&c->tnc_mutex);2518 if (err)2519 return err;2520 return ubifs_tnc_remove_nm(c, key, &noname);2521 }2522 }2523 2524out_unlock:2525 if (!err)2526 err = dbg_check_tnc(c, 0);2527 mutex_unlock(&c->tnc_mutex);2528 return err;2529}2530 2531/**2532 * tnc_delete - delete a znode form TNC.2533 * @c: UBIFS file-system description object2534 * @znode: znode to delete from2535 * @n: zbranch slot number to delete2536 *2537 * This function deletes a leaf node from @n-th slot of @znode. Returns zero in2538 * case of success and a negative error code in case of failure.2539 */2540static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)2541{2542 struct ubifs_zbranch *zbr;2543 struct ubifs_znode *zp;2544 int i, err;2545 2546 /* Delete without merge for now */2547 ubifs_assert(c, znode->level == 0);2548 ubifs_assert(c, n >= 0 && n < c->fanout);2549 dbg_tnck(&znode->zbranch[n].key, "deleting key ");2550 2551 zbr = &znode->zbranch[n];2552 lnc_free(zbr);2553 2554 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);2555 if (err) {2556 ubifs_dump_znode(c, znode);2557 return err;2558 }2559 2560 /* We do not "gap" zbranch slots */2561 for (i = n; i < znode->child_cnt - 1; i++)2562 znode->zbranch[i] = znode->zbranch[i + 1];2563 znode->child_cnt -= 1;2564 2565 if (znode->child_cnt > 0)2566 return 0;2567 2568 /*2569 * This was the last zbranch, we have to delete this znode from the2570 * parent.2571 */2572 2573 do {2574 ubifs_assert(c, !ubifs_zn_obsolete(znode));2575 ubifs_assert(c, ubifs_zn_dirty(znode));2576 2577 zp = znode->parent;2578 n = znode->iip;2579 2580 atomic_long_dec(&c->dirty_zn_cnt);2581 2582 err = insert_old_idx_znode(c, znode);2583 if (err)2584 return err;2585 2586 if (znode->cnext) {2587 __set_bit(OBSOLETE_ZNODE, &znode->flags);2588 atomic_long_inc(&c->clean_zn_cnt);2589 atomic_long_inc(&ubifs_clean_zn_cnt);2590 } else2591 kfree(znode);2592 znode = zp;2593 } while (znode->child_cnt == 1); /* while removing last child */2594 2595 /* Remove from znode, entry n - 1 */2596 znode->child_cnt -= 1;2597 ubifs_assert(c, znode->level != 0);2598 for (i = n; i < znode->child_cnt; i++) {2599 znode->zbranch[i] = znode->zbranch[i + 1];2600 if (znode->zbranch[i].znode)2601 znode->zbranch[i].znode->iip = i;2602 }2603 2604 /*2605 * If this is the root and it has only 1 child then2606 * collapse the tree.2607 */2608 if (!znode->parent) {2609 while (znode->child_cnt == 1 && znode->level != 0) {2610 zp = znode;2611 zbr = &znode->zbranch[0];2612 znode = get_znode(c, znode, 0);2613 if (IS_ERR(znode))2614 return PTR_ERR(znode);2615 znode = dirty_cow_znode(c, zbr);2616 if (IS_ERR(znode))2617 return PTR_ERR(znode);2618 znode->parent = NULL;2619 znode->iip = 0;2620 if (c->zroot.len) {2621 err = insert_old_idx(c, c->zroot.lnum,2622 c->zroot.offs);2623 if (err)2624 return err;2625 }2626 c->zroot.lnum = zbr->lnum;2627 c->zroot.offs = zbr->offs;2628 c->zroot.len = zbr->len;2629 c->zroot.znode = znode;2630 ubifs_assert(c, !ubifs_zn_obsolete(zp));2631 ubifs_assert(c, ubifs_zn_dirty(zp));2632 atomic_long_dec(&c->dirty_zn_cnt);2633 2634 if (zp->cnext) {2635 __set_bit(OBSOLETE_ZNODE, &zp->flags);2636 atomic_long_inc(&c->clean_zn_cnt);2637 atomic_long_inc(&ubifs_clean_zn_cnt);2638 } else2639 kfree(zp);2640 }2641 }2642 2643 return 0;2644}2645 2646/**2647 * ubifs_tnc_remove - remove an index entry of a node.2648 * @c: UBIFS file-system description object2649 * @key: key of node2650 *2651 * Returns %0 on success or negative error code on failure.2652 */2653int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)2654{2655 int found, n, err = 0;2656 struct ubifs_znode *znode;2657 2658 mutex_lock(&c->tnc_mutex);2659 dbg_tnck(key, "key ");2660 found = lookup_level0_dirty(c, key, &znode, &n);2661 if (found < 0) {2662 err = found;2663 goto out_unlock;2664 }2665 if (found == 1)2666 err = tnc_delete(c, znode, n);2667 if (!err)2668 err = dbg_check_tnc(c, 0);2669 2670out_unlock:2671 mutex_unlock(&c->tnc_mutex);2672 return err;2673}2674 2675/**2676 * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.2677 * @c: UBIFS file-system description object2678 * @key: key of node2679 * @nm: directory entry name2680 *2681 * Returns %0 on success or negative error code on failure.2682 */2683int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,2684 const struct fscrypt_name *nm)2685{2686 int n, err;2687 struct ubifs_znode *znode;2688 2689 mutex_lock(&c->tnc_mutex);2690 dbg_tnck(key, "key ");2691 err = lookup_level0_dirty(c, key, &znode, &n);2692 if (err < 0)2693 goto out_unlock;2694 2695 if (err) {2696 if (c->replaying)2697 err = fallible_resolve_collision(c, key, &znode, &n,2698 nm, 0);2699 else2700 err = resolve_collision(c, key, &znode, &n, nm);2701 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);2702 if (err < 0)2703 goto out_unlock;2704 if (err) {2705 /* Ensure the znode is dirtied */2706 if (znode->cnext || !ubifs_zn_dirty(znode)) {2707 znode = dirty_cow_bottom_up(c, znode);2708 if (IS_ERR(znode)) {2709 err = PTR_ERR(znode);2710 goto out_unlock;2711 }2712 }2713 err = tnc_delete(c, znode, n);2714 }2715 }2716 2717out_unlock:2718 if (!err)2719 err = dbg_check_tnc(c, 0);2720 mutex_unlock(&c->tnc_mutex);2721 return err;2722}2723 2724/**2725 * ubifs_tnc_remove_dh - remove an index entry for a "double hashed" node.2726 * @c: UBIFS file-system description object2727 * @key: key of node2728 * @cookie: node cookie for collision resolution2729 *2730 * Returns %0 on success or negative error code on failure.2731 */2732int ubifs_tnc_remove_dh(struct ubifs_info *c, const union ubifs_key *key,2733 uint32_t cookie)2734{2735 int n, err;2736 struct ubifs_znode *znode;2737 struct ubifs_dent_node *dent;2738 struct ubifs_zbranch *zbr;2739 2740 if (!c->double_hash)2741 return -EOPNOTSUPP;2742 2743 mutex_lock(&c->tnc_mutex);2744 err = lookup_level0_dirty(c, key, &znode, &n);2745 if (err <= 0)2746 goto out_unlock;2747 2748 zbr = &znode->zbranch[n];2749 dent = kmalloc(UBIFS_MAX_DENT_NODE_SZ, GFP_NOFS);2750 if (!dent) {2751 err = -ENOMEM;2752 goto out_unlock;2753 }2754 2755 err = tnc_read_hashed_node(c, zbr, dent);2756 if (err)2757 goto out_free;2758 2759 /* If the cookie does not match, we're facing a hash collision. */2760 if (le32_to_cpu(dent->cookie) != cookie) {2761 union ubifs_key start_key;2762 2763 lowest_dent_key(c, &start_key, key_inum(c, key));2764 2765 err = ubifs_lookup_level0(c, &start_key, &znode, &n);2766 if (unlikely(err < 0))2767 goto out_free;2768 2769 err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err);2770 if (err)2771 goto out_free;2772 }2773 2774 if (znode->cnext || !ubifs_zn_dirty(znode)) {2775 znode = dirty_cow_bottom_up(c, znode);2776 if (IS_ERR(znode)) {2777 err = PTR_ERR(znode);2778 goto out_free;2779 }2780 }2781 err = tnc_delete(c, znode, n);2782 2783out_free:2784 kfree(dent);2785out_unlock:2786 if (!err)2787 err = dbg_check_tnc(c, 0);2788 mutex_unlock(&c->tnc_mutex);2789 return err;2790}2791 2792/**2793 * key_in_range - determine if a key falls within a range of keys.2794 * @c: UBIFS file-system description object2795 * @key: key to check2796 * @from_key: lowest key in range2797 * @to_key: highest key in range2798 *2799 * This function returns %1 if the key is in range and %0 otherwise.2800 */2801static int key_in_range(struct ubifs_info *c, union ubifs_key *key,2802 union ubifs_key *from_key, union ubifs_key *to_key)2803{2804 if (keys_cmp(c, key, from_key) < 0)2805 return 0;2806 if (keys_cmp(c, key, to_key) > 0)2807 return 0;2808 return 1;2809}2810 2811/**2812 * ubifs_tnc_remove_range - remove index entries in range.2813 * @c: UBIFS file-system description object2814 * @from_key: lowest key to remove2815 * @to_key: highest key to remove2816 *2817 * This function removes index entries starting at @from_key and ending at2818 * @to_key. This function returns zero in case of success and a negative error2819 * code in case of failure.2820 */2821int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,2822 union ubifs_key *to_key)2823{2824 int i, n, k, err = 0;2825 struct ubifs_znode *znode;2826 union ubifs_key *key;2827 2828 mutex_lock(&c->tnc_mutex);2829 while (1) {2830 /* Find first level 0 znode that contains keys to remove */2831 err = ubifs_lookup_level0(c, from_key, &znode, &n);2832 if (err < 0)2833 goto out_unlock;2834 2835 if (err)2836 key = from_key;2837 else {2838 err = tnc_next(c, &znode, &n);2839 if (err == -ENOENT) {2840 err = 0;2841 goto out_unlock;2842 }2843 if (err < 0)2844 goto out_unlock;2845 key = &znode->zbranch[n].key;2846 if (!key_in_range(c, key, from_key, to_key)) {2847 err = 0;2848 goto out_unlock;2849 }2850 }2851 2852 /* Ensure the znode is dirtied */2853 if (znode->cnext || !ubifs_zn_dirty(znode)) {2854 znode = dirty_cow_bottom_up(c, znode);2855 if (IS_ERR(znode)) {2856 err = PTR_ERR(znode);2857 goto out_unlock;2858 }2859 }2860 2861 /* Remove all keys in range except the first */2862 for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) {2863 key = &znode->zbranch[i].key;2864 if (!key_in_range(c, key, from_key, to_key))2865 break;2866 lnc_free(&znode->zbranch[i]);2867 err = ubifs_add_dirt(c, znode->zbranch[i].lnum,2868 znode->zbranch[i].len);2869 if (err) {2870 ubifs_dump_znode(c, znode);2871 goto out_unlock;2872 }2873 dbg_tnck(key, "removing key ");2874 }2875 if (k) {2876 for (i = n + 1 + k; i < znode->child_cnt; i++)2877 znode->zbranch[i - k] = znode->zbranch[i];2878 znode->child_cnt -= k;2879 }2880 2881 /* Now delete the first */2882 err = tnc_delete(c, znode, n);2883 if (err)2884 goto out_unlock;2885 }2886 2887out_unlock:2888 if (!err)2889 err = dbg_check_tnc(c, 0);2890 mutex_unlock(&c->tnc_mutex);2891 return err;2892}2893 2894/**2895 * ubifs_tnc_remove_ino - remove an inode from TNC.2896 * @c: UBIFS file-system description object2897 * @inum: inode number to remove2898 *2899 * This function remove inode @inum and all the extended attributes associated2900 * with the anode from TNC and returns zero in case of success or a negative2901 * error code in case of failure.2902 */2903int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)2904{2905 union ubifs_key key1, key2;2906 struct ubifs_dent_node *xent, *pxent = NULL;2907 struct fscrypt_name nm = {0};2908 2909 dbg_tnc("ino %lu", (unsigned long)inum);2910 2911 /*2912 * Walk all extended attribute entries and remove them together with2913 * corresponding extended attribute inodes.2914 */2915 lowest_xent_key(c, &key1, inum);2916 while (1) {2917 ino_t xattr_inum;2918 int err;2919 2920 xent = ubifs_tnc_next_ent(c, &key1, &nm);2921 if (IS_ERR(xent)) {2922 err = PTR_ERR(xent);2923 if (err == -ENOENT)2924 break;2925 kfree(pxent);2926 return err;2927 }2928 2929 xattr_inum = le64_to_cpu(xent->inum);2930 dbg_tnc("xent '%s', ino %lu", xent->name,2931 (unsigned long)xattr_inum);2932 2933 ubifs_evict_xattr_inode(c, xattr_inum);2934 2935 fname_name(&nm) = xent->name;2936 fname_len(&nm) = le16_to_cpu(xent->nlen);2937 err = ubifs_tnc_remove_nm(c, &key1, &nm);2938 if (err) {2939 kfree(pxent);2940 kfree(xent);2941 return err;2942 }2943 2944 lowest_ino_key(c, &key1, xattr_inum);2945 highest_ino_key(c, &key2, xattr_inum);2946 err = ubifs_tnc_remove_range(c, &key1, &key2);2947 if (err) {2948 kfree(pxent);2949 kfree(xent);2950 return err;2951 }2952 2953 kfree(pxent);2954 pxent = xent;2955 key_read(c, &xent->key, &key1);2956 }2957 2958 kfree(pxent);2959 lowest_ino_key(c, &key1, inum);2960 highest_ino_key(c, &key2, inum);2961 2962 return ubifs_tnc_remove_range(c, &key1, &key2);2963}2964 2965/**2966 * ubifs_tnc_next_ent - walk directory or extended attribute entries.2967 * @c: UBIFS file-system description object2968 * @key: key of last entry2969 * @nm: name of last entry found or %NULL2970 *2971 * This function finds and reads the next directory or extended attribute entry2972 * after the given key (@key) if there is one. @nm is used to resolve2973 * collisions.2974 *2975 * If the name of the current entry is not known and only the key is known,2976 * @nm->name has to be %NULL. In this case the semantics of this function is a2977 * little bit different and it returns the entry corresponding to this key, not2978 * the next one. If the key was not found, the closest "right" entry is2979 * returned.2980 *2981 * If the fist entry has to be found, @key has to contain the lowest possible2982 * key value for this inode and @name has to be %NULL.2983 *2984 * This function returns the found directory or extended attribute entry node2985 * in case of success, %-ENOENT is returned if no entry was found, and a2986 * negative error code is returned in case of failure.2987 */2988struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,2989 union ubifs_key *key,2990 const struct fscrypt_name *nm)2991{2992 int n, err, type = key_type(c, key);2993 struct ubifs_znode *znode;2994 struct ubifs_dent_node *dent;2995 struct ubifs_zbranch *zbr;2996 union ubifs_key *dkey;2997 2998 dbg_tnck(key, "key ");2999 ubifs_assert(c, is_hash_key(c, key));3000 3001 mutex_lock(&c->tnc_mutex);3002 err = ubifs_lookup_level0(c, key, &znode, &n);3003 if (unlikely(err < 0))3004 goto out_unlock;3005 3006 if (fname_len(nm) > 0) {3007 if (err) {3008 /* Handle collisions */3009 if (c->replaying)3010 err = fallible_resolve_collision(c, key, &znode, &n,3011 nm, 0);3012 else3013 err = resolve_collision(c, key, &znode, &n, nm);3014 dbg_tnc("rc returned %d, znode %p, n %d",3015 err, znode, n);3016 if (unlikely(err < 0))3017 goto out_unlock;3018 }3019 3020 /* Now find next entry */3021 err = tnc_next(c, &znode, &n);3022 if (unlikely(err))3023 goto out_unlock;3024 } else {3025 /*3026 * The full name of the entry was not given, in which case the3027 * behavior of this function is a little different and it3028 * returns current entry, not the next one.3029 */3030 if (!err) {3031 /*3032 * However, the given key does not exist in the TNC3033 * tree and @znode/@n variables contain the closest3034 * "preceding" element. Switch to the next one.3035 */3036 err = tnc_next(c, &znode, &n);3037 if (err)3038 goto out_unlock;3039 }3040 }3041 3042 zbr = &znode->zbranch[n];3043 dent = kmalloc(zbr->len, GFP_NOFS);3044 if (unlikely(!dent)) {3045 err = -ENOMEM;3046 goto out_unlock;3047 }3048 3049 /*3050 * The above 'tnc_next()' call could lead us to the next inode, check3051 * this.3052 */3053 dkey = &zbr->key;3054 if (key_inum(c, dkey) != key_inum(c, key) ||3055 key_type(c, dkey) != type) {3056 err = -ENOENT;3057 goto out_free;3058 }3059 3060 err = tnc_read_hashed_node(c, zbr, dent);3061 if (unlikely(err))3062 goto out_free;3063 3064 mutex_unlock(&c->tnc_mutex);3065 return dent;3066 3067out_free:3068 kfree(dent);3069out_unlock:3070 mutex_unlock(&c->tnc_mutex);3071 return ERR_PTR(err);3072}3073 3074/**3075 * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.3076 * @c: UBIFS file-system description object3077 *3078 * Destroy left-over obsolete znodes from a failed commit.3079 */3080static void tnc_destroy_cnext(struct ubifs_info *c)3081{3082 struct ubifs_znode *cnext;3083 3084 if (!c->cnext)3085 return;3086 ubifs_assert(c, c->cmt_state == COMMIT_BROKEN);3087 cnext = c->cnext;3088 do {3089 struct ubifs_znode *znode = cnext;3090 3091 cnext = cnext->cnext;3092 if (ubifs_zn_obsolete(znode))3093 kfree(znode);3094 else if (!ubifs_zn_cow(znode)) {3095 /*3096 * Don't forget to update clean znode count after3097 * committing failed, because ubifs will check this3098 * count while closing tnc. Non-obsolete znode could3099 * be re-dirtied during committing process, so dirty3100 * flag is untrustable. The flag 'COW_ZNODE' is set3101 * for each dirty znode before committing, and it is3102 * cleared as long as the znode become clean, so we3103 * can statistic clean znode count according to this3104 * flag.3105 */3106 atomic_long_inc(&c->clean_zn_cnt);3107 atomic_long_inc(&ubifs_clean_zn_cnt);3108 }3109 } while (cnext && cnext != c->cnext);3110}3111 3112/**3113 * ubifs_tnc_close - close TNC subsystem and free all related resources.3114 * @c: UBIFS file-system description object3115 */3116void ubifs_tnc_close(struct ubifs_info *c)3117{3118 tnc_destroy_cnext(c);3119 ubifs_destroy_tnc_tree(c);3120 kfree(c->gap_lebs);3121 kfree(c->ilebs);3122 destroy_old_idx(c);3123}3124 3125/**3126 * left_znode - get the znode to the left.3127 * @c: UBIFS file-system description object3128 * @znode: znode3129 *3130 * This function returns a pointer to the znode to the left of @znode or NULL if3131 * there is not one. A negative error code is returned on failure.3132 */3133static struct ubifs_znode *left_znode(struct ubifs_info *c,3134 struct ubifs_znode *znode)3135{3136 int level = znode->level;3137 3138 while (1) {3139 int n = znode->iip - 1;3140 3141 /* Go up until we can go left */3142 znode = znode->parent;3143 if (!znode)3144 return NULL;3145 if (n >= 0) {3146 /* Now go down the rightmost branch to 'level' */3147 znode = get_znode(c, znode, n);3148 if (IS_ERR(znode))3149 return znode;3150 while (znode->level != level) {3151 n = znode->child_cnt - 1;3152 znode = get_znode(c, znode, n);3153 if (IS_ERR(znode))3154 return znode;3155 }3156 break;3157 }3158 }3159 return znode;3160}3161 3162/**3163 * right_znode - get the znode to the right.3164 * @c: UBIFS file-system description object3165 * @znode: znode3166 *3167 * This function returns a pointer to the znode to the right of @znode or NULL3168 * if there is not one. A negative error code is returned on failure.3169 */3170static struct ubifs_znode *right_znode(struct ubifs_info *c,3171 struct ubifs_znode *znode)3172{3173 int level = znode->level;3174 3175 while (1) {3176 int n = znode->iip + 1;3177 3178 /* Go up until we can go right */3179 znode = znode->parent;3180 if (!znode)3181 return NULL;3182 if (n < znode->child_cnt) {3183 /* Now go down the leftmost branch to 'level' */3184 znode = get_znode(c, znode, n);3185 if (IS_ERR(znode))3186 return znode;3187 while (znode->level != level) {3188 znode = get_znode(c, znode, 0);3189 if (IS_ERR(znode))3190 return znode;3191 }3192 break;3193 }3194 }3195 return znode;3196}3197 3198/**3199 * lookup_znode - find a particular indexing node from TNC.3200 * @c: UBIFS file-system description object3201 * @key: index node key to lookup3202 * @level: index node level3203 * @lnum: index node LEB number3204 * @offs: index node offset3205 *3206 * This function searches an indexing node by its first key @key and its3207 * address @lnum:@offs. It looks up the indexing tree by pulling all indexing3208 * nodes it traverses to TNC. This function is called for indexing nodes which3209 * were found on the media by scanning, for example when garbage-collecting or3210 * when doing in-the-gaps commit. This means that the indexing node which is3211 * looked for does not have to have exactly the same leftmost key @key, because3212 * the leftmost key may have been changed, in which case TNC will contain a3213 * dirty znode which still refers the same @lnum:@offs. This function is clever3214 * enough to recognize such indexing nodes.3215 *3216 * Note, if a znode was deleted or changed too much, then this function will3217 * not find it. For situations like this UBIFS has the old index RB-tree3218 * (indexed by @lnum:@offs).3219 *3220 * This function returns a pointer to the znode found or %NULL if it is not3221 * found. A negative error code is returned on failure.3222 */3223static struct ubifs_znode *lookup_znode(struct ubifs_info *c,3224 union ubifs_key *key, int level,3225 int lnum, int offs)3226{3227 struct ubifs_znode *znode, *zn;3228 int n, nn;3229 3230 ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);3231 3232 /*3233 * The arguments have probably been read off flash, so don't assume3234 * they are valid.3235 */3236 if (level < 0)3237 return ERR_PTR(-EINVAL);3238 3239 /* Get the root znode */3240 znode = c->zroot.znode;3241 if (!znode) {3242 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);3243 if (IS_ERR(znode))3244 return znode;3245 }3246 /* Check if it is the one we are looking for */3247 if (c->zroot.lnum == lnum && c->zroot.offs == offs)3248 return znode;3249 /* Descend to the parent level i.e. (level + 1) */3250 if (level >= znode->level)3251 return NULL;3252 while (1) {3253 ubifs_search_zbranch(c, znode, key, &n);3254 if (n < 0) {3255 /*3256 * We reached a znode where the leftmost key is greater3257 * than the key we are searching for. This is the same3258 * situation as the one described in a huge comment at3259 * the end of the 'ubifs_lookup_level0()' function. And3260 * for exactly the same reasons we have to try to look3261 * left before giving up.3262 */3263 znode = left_znode(c, znode);3264 if (!znode)3265 return NULL;3266 if (IS_ERR(znode))3267 return znode;3268 ubifs_search_zbranch(c, znode, key, &n);3269 ubifs_assert(c, n >= 0);3270 }3271 if (znode->level == level + 1)3272 break;3273 znode = get_znode(c, znode, n);3274 if (IS_ERR(znode))3275 return znode;3276 }3277 /* Check if the child is the one we are looking for */3278 if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs)3279 return get_znode(c, znode, n);3280 /* If the key is unique, there is nowhere else to look */3281 if (!is_hash_key(c, key))3282 return NULL;3283 /*3284 * The key is not unique and so may be also in the znodes to either3285 * side.3286 */3287 zn = znode;3288 nn = n;3289 /* Look left */3290 while (1) {3291 /* Move one branch to the left */3292 if (n)3293 n -= 1;3294 else {3295 znode = left_znode(c, znode);3296 if (!znode)3297 break;3298 if (IS_ERR(znode))3299 return znode;3300 n = znode->child_cnt - 1;3301 }3302 /* Check it */3303 if (znode->zbranch[n].lnum == lnum &&3304 znode->zbranch[n].offs == offs)3305 return get_znode(c, znode, n);3306 /* Stop if the key is less than the one we are looking for */3307 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)3308 break;3309 }3310 /* Back to the middle */3311 znode = zn;3312 n = nn;3313 /* Look right */3314 while (1) {3315 /* Move one branch to the right */3316 if (++n >= znode->child_cnt) {3317 znode = right_znode(c, znode);3318 if (!znode)3319 break;3320 if (IS_ERR(znode))3321 return znode;3322 n = 0;3323 }3324 /* Check it */3325 if (znode->zbranch[n].lnum == lnum &&3326 znode->zbranch[n].offs == offs)3327 return get_znode(c, znode, n);3328 /* Stop if the key is greater than the one we are looking for */3329 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)3330 break;3331 }3332 return NULL;3333}3334 3335/**3336 * is_idx_node_in_tnc - determine if an index node is in the TNC.3337 * @c: UBIFS file-system description object3338 * @key: key of index node3339 * @level: index node level3340 * @lnum: LEB number of index node3341 * @offs: offset of index node3342 *3343 * This function returns %0 if the index node is not referred to in the TNC, %13344 * if the index node is referred to in the TNC and the corresponding znode is3345 * dirty, %2 if an index node is referred to in the TNC and the corresponding3346 * znode is clean, and a negative error code in case of failure.3347 *3348 * Note, the @key argument has to be the key of the first child. Also note,3349 * this function relies on the fact that 0:0 is never a valid LEB number and3350 * offset for a main-area node.3351 */3352int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,3353 int lnum, int offs)3354{3355 struct ubifs_znode *znode;3356 3357 znode = lookup_znode(c, key, level, lnum, offs);3358 if (!znode)3359 return 0;3360 if (IS_ERR(znode))3361 return PTR_ERR(znode);3362 3363 return ubifs_zn_dirty(znode) ? 1 : 2;3364}3365 3366/**3367 * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.3368 * @c: UBIFS file-system description object3369 * @key: node key3370 * @lnum: node LEB number3371 * @offs: node offset3372 *3373 * This function returns %1 if the node is referred to in the TNC, %0 if it is3374 * not, and a negative error code in case of failure.3375 *3376 * Note, this function relies on the fact that 0:0 is never a valid LEB number3377 * and offset for a main-area node.3378 */3379static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,3380 int lnum, int offs)3381{3382 struct ubifs_zbranch *zbr;3383 struct ubifs_znode *znode, *zn;3384 int n, found, err, nn;3385 const int unique = !is_hash_key(c, key);3386 3387 found = ubifs_lookup_level0(c, key, &znode, &n);3388 if (found < 0)3389 return found; /* Error code */3390 if (!found)3391 return 0;3392 zbr = &znode->zbranch[n];3393 if (lnum == zbr->lnum && offs == zbr->offs)3394 return 1; /* Found it */3395 if (unique)3396 return 0;3397 /*3398 * Because the key is not unique, we have to look left3399 * and right as well3400 */3401 zn = znode;3402 nn = n;3403 /* Look left */3404 while (1) {3405 err = tnc_prev(c, &znode, &n);3406 if (err == -ENOENT)3407 break;3408 if (err)3409 return err;3410 if (keys_cmp(c, key, &znode->zbranch[n].key))3411 break;3412 zbr = &znode->zbranch[n];3413 if (lnum == zbr->lnum && offs == zbr->offs)3414 return 1; /* Found it */3415 }3416 /* Look right */3417 znode = zn;3418 n = nn;3419 while (1) {3420 err = tnc_next(c, &znode, &n);3421 if (err) {3422 if (err == -ENOENT)3423 return 0;3424 return err;3425 }3426 if (keys_cmp(c, key, &znode->zbranch[n].key))3427 break;3428 zbr = &znode->zbranch[n];3429 if (lnum == zbr->lnum && offs == zbr->offs)3430 return 1; /* Found it */3431 }3432 return 0;3433}3434 3435/**3436 * ubifs_tnc_has_node - determine whether a node is in the TNC.3437 * @c: UBIFS file-system description object3438 * @key: node key3439 * @level: index node level (if it is an index node)3440 * @lnum: node LEB number3441 * @offs: node offset3442 * @is_idx: non-zero if the node is an index node3443 *3444 * This function returns %1 if the node is in the TNC, %0 if it is not, and a3445 * negative error code in case of failure. For index nodes, @key has to be the3446 * key of the first child. An index node is considered to be in the TNC only if3447 * the corresponding znode is clean or has not been loaded.3448 */3449int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,3450 int lnum, int offs, int is_idx)3451{3452 int err;3453 3454 mutex_lock(&c->tnc_mutex);3455 if (is_idx) {3456 err = is_idx_node_in_tnc(c, key, level, lnum, offs);3457 if (err < 0)3458 goto out_unlock;3459 if (err == 1)3460 /* The index node was found but it was dirty */3461 err = 0;3462 else if (err == 2)3463 /* The index node was found and it was clean */3464 err = 1;3465 else3466 BUG_ON(err != 0);3467 } else3468 err = is_leaf_node_in_tnc(c, key, lnum, offs);3469 3470out_unlock:3471 mutex_unlock(&c->tnc_mutex);3472 return err;3473}3474 3475/**3476 * ubifs_dirty_idx_node - dirty an index node.3477 * @c: UBIFS file-system description object3478 * @key: index node key3479 * @level: index node level3480 * @lnum: index node LEB number3481 * @offs: index node offset3482 *3483 * This function loads and dirties an index node so that it can be garbage3484 * collected. The @key argument has to be the key of the first child. This3485 * function relies on the fact that 0:0 is never a valid LEB number and offset3486 * for a main-area node. Returns %0 on success and a negative error code on3487 * failure.3488 */3489int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,3490 int lnum, int offs)3491{3492 struct ubifs_znode *znode;3493 int err = 0;3494 3495 mutex_lock(&c->tnc_mutex);3496 znode = lookup_znode(c, key, level, lnum, offs);3497 if (!znode)3498 goto out_unlock;3499 if (IS_ERR(znode)) {3500 err = PTR_ERR(znode);3501 goto out_unlock;3502 }3503 znode = dirty_cow_bottom_up(c, znode);3504 if (IS_ERR(znode)) {3505 err = PTR_ERR(znode);3506 goto out_unlock;3507 }3508 3509out_unlock:3510 mutex_unlock(&c->tnc_mutex);3511 return err;3512}3513 3514/**3515 * dbg_check_inode_size - check if inode size is correct.3516 * @c: UBIFS file-system description object3517 * @inode: inode to check3518 * @size: inode size3519 *3520 * This function makes sure that the inode size (@size) is correct and it does3521 * not have any pages beyond @size. Returns zero if the inode is OK, %-EINVAL3522 * if it has a data page beyond @size, and other negative error code in case of3523 * other errors.3524 */3525int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode,3526 loff_t size)3527{3528 int err, n;3529 union ubifs_key from_key, to_key, *key;3530 struct ubifs_znode *znode;3531 unsigned int block;3532 3533 if (!S_ISREG(inode->i_mode))3534 return 0;3535 if (!dbg_is_chk_gen(c))3536 return 0;3537 3538 block = (size + UBIFS_BLOCK_SIZE - 1) >> UBIFS_BLOCK_SHIFT;3539 data_key_init(c, &from_key, inode->i_ino, block);3540 highest_data_key(c, &to_key, inode->i_ino);3541 3542 mutex_lock(&c->tnc_mutex);3543 err = ubifs_lookup_level0(c, &from_key, &znode, &n);3544 if (err < 0)3545 goto out_unlock;3546 3547 if (err) {3548 key = &from_key;3549 goto out_dump;3550 }3551 3552 err = tnc_next(c, &znode, &n);3553 if (err == -ENOENT) {3554 err = 0;3555 goto out_unlock;3556 }3557 if (err < 0)3558 goto out_unlock;3559 3560 ubifs_assert(c, err == 0);3561 key = &znode->zbranch[n].key;3562 if (!key_in_range(c, key, &from_key, &to_key))3563 goto out_unlock;3564 3565out_dump:3566 block = key_block(c, key);3567 ubifs_err(c, "inode %lu has size %lld, but there are data at offset %lld",3568 (unsigned long)inode->i_ino, size,3569 ((loff_t)block) << UBIFS_BLOCK_SHIFT);3570 mutex_unlock(&c->tnc_mutex);3571 ubifs_dump_inode(c, inode);3572 dump_stack();3573 return -EINVAL;3574 3575out_unlock:3576 mutex_unlock(&c->tnc_mutex);3577 return err;3578}3579