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