1 /* 2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include "xfs.h" 19 #include "xfs_fs.h" 20 #include "xfs_shared.h" 21 #include "xfs_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_bit.h" 25 #include "xfs_mount.h" 26 #include "xfs_defer.h" 27 #include "xfs_inode.h" 28 #include "xfs_trans.h" 29 #include "xfs_inode_item.h" 30 #include "xfs_buf_item.h" 31 #include "xfs_btree.h" 32 #include "xfs_errortag.h" 33 #include "xfs_error.h" 34 #include "xfs_trace.h" 35 #include "xfs_cksum.h" 36 #include "xfs_alloc.h" 37 #include "xfs_log.h" 38 39 /* 40 * Cursor allocation zone. 41 */ 42 kmem_zone_t *xfs_btree_cur_zone; 43 44 /* 45 * Btree magic numbers. 46 */ 47 static const uint32_t xfs_magics[2][XFS_BTNUM_MAX] = { 48 { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, 0, XFS_BMAP_MAGIC, XFS_IBT_MAGIC, 49 XFS_FIBT_MAGIC, 0 }, 50 { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC, XFS_RMAP_CRC_MAGIC, 51 XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC, XFS_FIBT_CRC_MAGIC, 52 XFS_REFC_CRC_MAGIC } 53 }; 54 55 uint32_t 56 xfs_btree_magic( 57 int crc, 58 xfs_btnum_t btnum) 59 { 60 uint32_t magic = xfs_magics[crc][btnum]; 61 62 /* Ensure we asked for crc for crc-only magics. */ 63 ASSERT(magic != 0); 64 return magic; 65 } 66 67 /* 68 * Check a long btree block header. Return the address of the failing check, 69 * or NULL if everything is ok. 70 */ 71 xfs_failaddr_t 72 __xfs_btree_check_lblock( 73 struct xfs_btree_cur *cur, 74 struct xfs_btree_block *block, 75 int level, 76 struct xfs_buf *bp) 77 { 78 struct xfs_mount *mp = cur->bc_mp; 79 xfs_btnum_t btnum = cur->bc_btnum; 80 int crc = xfs_sb_version_hascrc(&mp->m_sb); 81 82 if (crc) { 83 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) 84 return __this_address; 85 if (block->bb_u.l.bb_blkno != 86 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL)) 87 return __this_address; 88 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) 89 return __this_address; 90 } 91 92 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) 93 return __this_address; 94 if (be16_to_cpu(block->bb_level) != level) 95 return __this_address; 96 if (be16_to_cpu(block->bb_numrecs) > 97 cur->bc_ops->get_maxrecs(cur, level)) 98 return __this_address; 99 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && 100 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib), 101 level + 1)) 102 return __this_address; 103 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && 104 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib), 105 level + 1)) 106 return __this_address; 107 108 return NULL; 109 } 110 111 /* Check a long btree block header. */ 112 static int 113 xfs_btree_check_lblock( 114 struct xfs_btree_cur *cur, 115 struct xfs_btree_block *block, 116 int level, 117 struct xfs_buf *bp) 118 { 119 struct xfs_mount *mp = cur->bc_mp; 120 xfs_failaddr_t fa; 121 122 fa = __xfs_btree_check_lblock(cur, block, level, bp); 123 if (unlikely(XFS_TEST_ERROR(fa != NULL, mp, 124 XFS_ERRTAG_BTREE_CHECK_LBLOCK))) { 125 if (bp) 126 trace_xfs_btree_corrupt(bp, _RET_IP_); 127 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp); 128 return -EFSCORRUPTED; 129 } 130 return 0; 131 } 132 133 /* 134 * Check a short btree block header. Return the address of the failing check, 135 * or NULL if everything is ok. 136 */ 137 xfs_failaddr_t 138 __xfs_btree_check_sblock( 139 struct xfs_btree_cur *cur, 140 struct xfs_btree_block *block, 141 int level, 142 struct xfs_buf *bp) 143 { 144 struct xfs_mount *mp = cur->bc_mp; 145 xfs_btnum_t btnum = cur->bc_btnum; 146 int crc = xfs_sb_version_hascrc(&mp->m_sb); 147 148 if (crc) { 149 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) 150 return __this_address; 151 if (block->bb_u.s.bb_blkno != 152 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL)) 153 return __this_address; 154 } 155 156 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) 157 return __this_address; 158 if (be16_to_cpu(block->bb_level) != level) 159 return __this_address; 160 if (be16_to_cpu(block->bb_numrecs) > 161 cur->bc_ops->get_maxrecs(cur, level)) 162 return __this_address; 163 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && 164 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib), 165 level + 1)) 166 return __this_address; 167 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && 168 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib), 169 level + 1)) 170 return __this_address; 171 172 return NULL; 173 } 174 175 /* Check a short btree block header. */ 176 STATIC int 177 xfs_btree_check_sblock( 178 struct xfs_btree_cur *cur, 179 struct xfs_btree_block *block, 180 int level, 181 struct xfs_buf *bp) 182 { 183 struct xfs_mount *mp = cur->bc_mp; 184 xfs_failaddr_t fa; 185 186 fa = __xfs_btree_check_sblock(cur, block, level, bp); 187 if (unlikely(XFS_TEST_ERROR(fa != NULL, mp, 188 XFS_ERRTAG_BTREE_CHECK_SBLOCK))) { 189 if (bp) 190 trace_xfs_btree_corrupt(bp, _RET_IP_); 191 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp); 192 return -EFSCORRUPTED; 193 } 194 return 0; 195 } 196 197 /* 198 * Debug routine: check that block header is ok. 199 */ 200 int 201 xfs_btree_check_block( 202 struct xfs_btree_cur *cur, /* btree cursor */ 203 struct xfs_btree_block *block, /* generic btree block pointer */ 204 int level, /* level of the btree block */ 205 struct xfs_buf *bp) /* buffer containing block, if any */ 206 { 207 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 208 return xfs_btree_check_lblock(cur, block, level, bp); 209 else 210 return xfs_btree_check_sblock(cur, block, level, bp); 211 } 212 213 /* Check that this long pointer is valid and points within the fs. */ 214 bool 215 xfs_btree_check_lptr( 216 struct xfs_btree_cur *cur, 217 xfs_fsblock_t fsbno, 218 int level) 219 { 220 if (level <= 0) 221 return false; 222 return xfs_verify_fsbno(cur->bc_mp, fsbno); 223 } 224 225 /* Check that this short pointer is valid and points within the AG. */ 226 bool 227 xfs_btree_check_sptr( 228 struct xfs_btree_cur *cur, 229 xfs_agblock_t agbno, 230 int level) 231 { 232 if (level <= 0) 233 return false; 234 return xfs_verify_agbno(cur->bc_mp, cur->bc_private.a.agno, agbno); 235 } 236 237 #ifdef DEBUG 238 /* 239 * Check that a given (indexed) btree pointer at a certain level of a 240 * btree is valid and doesn't point past where it should. 241 */ 242 static int 243 xfs_btree_check_ptr( 244 struct xfs_btree_cur *cur, 245 union xfs_btree_ptr *ptr, 246 int index, 247 int level) 248 { 249 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 250 XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, 251 xfs_btree_check_lptr(cur, 252 be64_to_cpu((&ptr->l)[index]), level)); 253 } else { 254 XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, 255 xfs_btree_check_sptr(cur, 256 be32_to_cpu((&ptr->s)[index]), level)); 257 } 258 259 return 0; 260 } 261 #endif 262 263 /* 264 * Calculate CRC on the whole btree block and stuff it into the 265 * long-form btree header. 266 * 267 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put 268 * it into the buffer so recovery knows what the last modification was that made 269 * it to disk. 270 */ 271 void 272 xfs_btree_lblock_calc_crc( 273 struct xfs_buf *bp) 274 { 275 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 276 struct xfs_buf_log_item *bip = bp->b_fspriv; 277 278 if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb)) 279 return; 280 if (bip) 281 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); 282 xfs_buf_update_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF); 283 } 284 285 bool 286 xfs_btree_lblock_verify_crc( 287 struct xfs_buf *bp) 288 { 289 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 290 struct xfs_mount *mp = bp->b_target->bt_mount; 291 292 if (xfs_sb_version_hascrc(&mp->m_sb)) { 293 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) 294 return false; 295 return xfs_buf_verify_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF); 296 } 297 298 return true; 299 } 300 301 /* 302 * Calculate CRC on the whole btree block and stuff it into the 303 * short-form btree header. 304 * 305 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put 306 * it into the buffer so recovery knows what the last modification was that made 307 * it to disk. 308 */ 309 void 310 xfs_btree_sblock_calc_crc( 311 struct xfs_buf *bp) 312 { 313 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 314 struct xfs_buf_log_item *bip = bp->b_fspriv; 315 316 if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb)) 317 return; 318 if (bip) 319 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); 320 xfs_buf_update_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF); 321 } 322 323 bool 324 xfs_btree_sblock_verify_crc( 325 struct xfs_buf *bp) 326 { 327 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 328 struct xfs_mount *mp = bp->b_target->bt_mount; 329 330 if (xfs_sb_version_hascrc(&mp->m_sb)) { 331 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) 332 return false; 333 return xfs_buf_verify_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF); 334 } 335 336 return true; 337 } 338 339 static int 340 xfs_btree_free_block( 341 struct xfs_btree_cur *cur, 342 struct xfs_buf *bp) 343 { 344 int error; 345 346 error = cur->bc_ops->free_block(cur, bp); 347 if (!error) { 348 xfs_trans_binval(cur->bc_tp, bp); 349 XFS_BTREE_STATS_INC(cur, free); 350 } 351 return error; 352 } 353 354 /* 355 * Delete the btree cursor. 356 */ 357 void 358 xfs_btree_del_cursor( 359 xfs_btree_cur_t *cur, /* btree cursor */ 360 int error) /* del because of error */ 361 { 362 int i; /* btree level */ 363 364 /* 365 * Clear the buffer pointers, and release the buffers. 366 * If we're doing this in the face of an error, we 367 * need to make sure to inspect all of the entries 368 * in the bc_bufs array for buffers to be unlocked. 369 * This is because some of the btree code works from 370 * level n down to 0, and if we get an error along 371 * the way we won't have initialized all the entries 372 * down to 0. 373 */ 374 for (i = 0; i < cur->bc_nlevels; i++) { 375 if (cur->bc_bufs[i]) 376 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); 377 else if (!error) 378 break; 379 } 380 /* 381 * Can't free a bmap cursor without having dealt with the 382 * allocated indirect blocks' accounting. 383 */ 384 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || 385 cur->bc_private.b.allocated == 0); 386 /* 387 * Free the cursor. 388 */ 389 kmem_zone_free(xfs_btree_cur_zone, cur); 390 } 391 392 /* 393 * Duplicate the btree cursor. 394 * Allocate a new one, copy the record, re-get the buffers. 395 */ 396 int /* error */ 397 xfs_btree_dup_cursor( 398 xfs_btree_cur_t *cur, /* input cursor */ 399 xfs_btree_cur_t **ncur) /* output cursor */ 400 { 401 xfs_buf_t *bp; /* btree block's buffer pointer */ 402 int error; /* error return value */ 403 int i; /* level number of btree block */ 404 xfs_mount_t *mp; /* mount structure for filesystem */ 405 xfs_btree_cur_t *new; /* new cursor value */ 406 xfs_trans_t *tp; /* transaction pointer, can be NULL */ 407 408 tp = cur->bc_tp; 409 mp = cur->bc_mp; 410 411 /* 412 * Allocate a new cursor like the old one. 413 */ 414 new = cur->bc_ops->dup_cursor(cur); 415 416 /* 417 * Copy the record currently in the cursor. 418 */ 419 new->bc_rec = cur->bc_rec; 420 421 /* 422 * For each level current, re-get the buffer and copy the ptr value. 423 */ 424 for (i = 0; i < new->bc_nlevels; i++) { 425 new->bc_ptrs[i] = cur->bc_ptrs[i]; 426 new->bc_ra[i] = cur->bc_ra[i]; 427 bp = cur->bc_bufs[i]; 428 if (bp) { 429 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, 430 XFS_BUF_ADDR(bp), mp->m_bsize, 431 0, &bp, 432 cur->bc_ops->buf_ops); 433 if (error) { 434 xfs_btree_del_cursor(new, error); 435 *ncur = NULL; 436 return error; 437 } 438 } 439 new->bc_bufs[i] = bp; 440 } 441 *ncur = new; 442 return 0; 443 } 444 445 /* 446 * XFS btree block layout and addressing: 447 * 448 * There are two types of blocks in the btree: leaf and non-leaf blocks. 449 * 450 * The leaf record start with a header then followed by records containing 451 * the values. A non-leaf block also starts with the same header, and 452 * then first contains lookup keys followed by an equal number of pointers 453 * to the btree blocks at the previous level. 454 * 455 * +--------+-------+-------+-------+-------+-------+-------+ 456 * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N | 457 * +--------+-------+-------+-------+-------+-------+-------+ 458 * 459 * +--------+-------+-------+-------+-------+-------+-------+ 460 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N | 461 * +--------+-------+-------+-------+-------+-------+-------+ 462 * 463 * The header is called struct xfs_btree_block for reasons better left unknown 464 * and comes in different versions for short (32bit) and long (64bit) block 465 * pointers. The record and key structures are defined by the btree instances 466 * and opaque to the btree core. The block pointers are simple disk endian 467 * integers, available in a short (32bit) and long (64bit) variant. 468 * 469 * The helpers below calculate the offset of a given record, key or pointer 470 * into a btree block (xfs_btree_*_offset) or return a pointer to the given 471 * record, key or pointer (xfs_btree_*_addr). Note that all addressing 472 * inside the btree block is done using indices starting at one, not zero! 473 * 474 * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing 475 * overlapping intervals. In such a tree, records are still sorted lowest to 476 * highest and indexed by the smallest key value that refers to the record. 477 * However, nodes are different: each pointer has two associated keys -- one 478 * indexing the lowest key available in the block(s) below (the same behavior 479 * as the key in a regular btree) and another indexing the highest key 480 * available in the block(s) below. Because records are /not/ sorted by the 481 * highest key, all leaf block updates require us to compute the highest key 482 * that matches any record in the leaf and to recursively update the high keys 483 * in the nodes going further up in the tree, if necessary. Nodes look like 484 * this: 485 * 486 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+ 487 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... | 488 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+ 489 * 490 * To perform an interval query on an overlapped tree, perform the usual 491 * depth-first search and use the low and high keys to decide if we can skip 492 * that particular node. If a leaf node is reached, return the records that 493 * intersect the interval. Note that an interval query may return numerous 494 * entries. For a non-overlapped tree, simply search for the record associated 495 * with the lowest key and iterate forward until a non-matching record is 496 * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by 497 * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in 498 * more detail. 499 * 500 * Why do we care about overlapping intervals? Let's say you have a bunch of 501 * reverse mapping records on a reflink filesystem: 502 * 503 * 1: +- file A startblock B offset C length D -----------+ 504 * 2: +- file E startblock F offset G length H --------------+ 505 * 3: +- file I startblock F offset J length K --+ 506 * 4: +- file L... --+ 507 * 508 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally, 509 * we'd simply increment the length of record 1. But how do we find the record 510 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return 511 * record 3 because the keys are ordered first by startblock. An interval 512 * query would return records 1 and 2 because they both overlap (B+D-1), and 513 * from that we can pick out record 1 as the appropriate left neighbor. 514 * 515 * In the non-overlapped case you can do a LE lookup and decrement the cursor 516 * because a record's interval must end before the next record. 517 */ 518 519 /* 520 * Return size of the btree block header for this btree instance. 521 */ 522 static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur) 523 { 524 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 525 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) 526 return XFS_BTREE_LBLOCK_CRC_LEN; 527 return XFS_BTREE_LBLOCK_LEN; 528 } 529 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) 530 return XFS_BTREE_SBLOCK_CRC_LEN; 531 return XFS_BTREE_SBLOCK_LEN; 532 } 533 534 /* 535 * Return size of btree block pointers for this btree instance. 536 */ 537 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur) 538 { 539 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? 540 sizeof(__be64) : sizeof(__be32); 541 } 542 543 /* 544 * Calculate offset of the n-th record in a btree block. 545 */ 546 STATIC size_t 547 xfs_btree_rec_offset( 548 struct xfs_btree_cur *cur, 549 int n) 550 { 551 return xfs_btree_block_len(cur) + 552 (n - 1) * cur->bc_ops->rec_len; 553 } 554 555 /* 556 * Calculate offset of the n-th key in a btree block. 557 */ 558 STATIC size_t 559 xfs_btree_key_offset( 560 struct xfs_btree_cur *cur, 561 int n) 562 { 563 return xfs_btree_block_len(cur) + 564 (n - 1) * cur->bc_ops->key_len; 565 } 566 567 /* 568 * Calculate offset of the n-th high key in a btree block. 569 */ 570 STATIC size_t 571 xfs_btree_high_key_offset( 572 struct xfs_btree_cur *cur, 573 int n) 574 { 575 return xfs_btree_block_len(cur) + 576 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2); 577 } 578 579 /* 580 * Calculate offset of the n-th block pointer in a btree block. 581 */ 582 STATIC size_t 583 xfs_btree_ptr_offset( 584 struct xfs_btree_cur *cur, 585 int n, 586 int level) 587 { 588 return xfs_btree_block_len(cur) + 589 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len + 590 (n - 1) * xfs_btree_ptr_len(cur); 591 } 592 593 /* 594 * Return a pointer to the n-th record in the btree block. 595 */ 596 union xfs_btree_rec * 597 xfs_btree_rec_addr( 598 struct xfs_btree_cur *cur, 599 int n, 600 struct xfs_btree_block *block) 601 { 602 return (union xfs_btree_rec *) 603 ((char *)block + xfs_btree_rec_offset(cur, n)); 604 } 605 606 /* 607 * Return a pointer to the n-th key in the btree block. 608 */ 609 union xfs_btree_key * 610 xfs_btree_key_addr( 611 struct xfs_btree_cur *cur, 612 int n, 613 struct xfs_btree_block *block) 614 { 615 return (union xfs_btree_key *) 616 ((char *)block + xfs_btree_key_offset(cur, n)); 617 } 618 619 /* 620 * Return a pointer to the n-th high key in the btree block. 621 */ 622 union xfs_btree_key * 623 xfs_btree_high_key_addr( 624 struct xfs_btree_cur *cur, 625 int n, 626 struct xfs_btree_block *block) 627 { 628 return (union xfs_btree_key *) 629 ((char *)block + xfs_btree_high_key_offset(cur, n)); 630 } 631 632 /* 633 * Return a pointer to the n-th block pointer in the btree block. 634 */ 635 union xfs_btree_ptr * 636 xfs_btree_ptr_addr( 637 struct xfs_btree_cur *cur, 638 int n, 639 struct xfs_btree_block *block) 640 { 641 int level = xfs_btree_get_level(block); 642 643 ASSERT(block->bb_level != 0); 644 645 return (union xfs_btree_ptr *) 646 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); 647 } 648 649 /* 650 * Get the root block which is stored in the inode. 651 * 652 * For now this btree implementation assumes the btree root is always 653 * stored in the if_broot field of an inode fork. 654 */ 655 STATIC struct xfs_btree_block * 656 xfs_btree_get_iroot( 657 struct xfs_btree_cur *cur) 658 { 659 struct xfs_ifork *ifp; 660 661 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, cur->bc_private.b.whichfork); 662 return (struct xfs_btree_block *)ifp->if_broot; 663 } 664 665 /* 666 * Retrieve the block pointer from the cursor at the given level. 667 * This may be an inode btree root or from a buffer. 668 */ 669 struct xfs_btree_block * /* generic btree block pointer */ 670 xfs_btree_get_block( 671 struct xfs_btree_cur *cur, /* btree cursor */ 672 int level, /* level in btree */ 673 struct xfs_buf **bpp) /* buffer containing the block */ 674 { 675 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 676 (level == cur->bc_nlevels - 1)) { 677 *bpp = NULL; 678 return xfs_btree_get_iroot(cur); 679 } 680 681 *bpp = cur->bc_bufs[level]; 682 return XFS_BUF_TO_BLOCK(*bpp); 683 } 684 685 /* 686 * Get a buffer for the block, return it with no data read. 687 * Long-form addressing. 688 */ 689 xfs_buf_t * /* buffer for fsbno */ 690 xfs_btree_get_bufl( 691 xfs_mount_t *mp, /* file system mount point */ 692 xfs_trans_t *tp, /* transaction pointer */ 693 xfs_fsblock_t fsbno, /* file system block number */ 694 uint lock) /* lock flags for get_buf */ 695 { 696 xfs_daddr_t d; /* real disk block address */ 697 698 ASSERT(fsbno != NULLFSBLOCK); 699 d = XFS_FSB_TO_DADDR(mp, fsbno); 700 return xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock); 701 } 702 703 /* 704 * Get a buffer for the block, return it with no data read. 705 * Short-form addressing. 706 */ 707 xfs_buf_t * /* buffer for agno/agbno */ 708 xfs_btree_get_bufs( 709 xfs_mount_t *mp, /* file system mount point */ 710 xfs_trans_t *tp, /* transaction pointer */ 711 xfs_agnumber_t agno, /* allocation group number */ 712 xfs_agblock_t agbno, /* allocation group block number */ 713 uint lock) /* lock flags for get_buf */ 714 { 715 xfs_daddr_t d; /* real disk block address */ 716 717 ASSERT(agno != NULLAGNUMBER); 718 ASSERT(agbno != NULLAGBLOCK); 719 d = XFS_AGB_TO_DADDR(mp, agno, agbno); 720 return xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock); 721 } 722 723 /* 724 * Check for the cursor referring to the last block at the given level. 725 */ 726 int /* 1=is last block, 0=not last block */ 727 xfs_btree_islastblock( 728 xfs_btree_cur_t *cur, /* btree cursor */ 729 int level) /* level to check */ 730 { 731 struct xfs_btree_block *block; /* generic btree block pointer */ 732 xfs_buf_t *bp; /* buffer containing block */ 733 734 block = xfs_btree_get_block(cur, level, &bp); 735 xfs_btree_check_block(cur, block, level, bp); 736 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 737 return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK); 738 else 739 return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK); 740 } 741 742 /* 743 * Change the cursor to point to the first record at the given level. 744 * Other levels are unaffected. 745 */ 746 STATIC int /* success=1, failure=0 */ 747 xfs_btree_firstrec( 748 xfs_btree_cur_t *cur, /* btree cursor */ 749 int level) /* level to change */ 750 { 751 struct xfs_btree_block *block; /* generic btree block pointer */ 752 xfs_buf_t *bp; /* buffer containing block */ 753 754 /* 755 * Get the block pointer for this level. 756 */ 757 block = xfs_btree_get_block(cur, level, &bp); 758 if (xfs_btree_check_block(cur, block, level, bp)) 759 return 0; 760 /* 761 * It's empty, there is no such record. 762 */ 763 if (!block->bb_numrecs) 764 return 0; 765 /* 766 * Set the ptr value to 1, that's the first record/key. 767 */ 768 cur->bc_ptrs[level] = 1; 769 return 1; 770 } 771 772 /* 773 * Change the cursor to point to the last record in the current block 774 * at the given level. Other levels are unaffected. 775 */ 776 STATIC int /* success=1, failure=0 */ 777 xfs_btree_lastrec( 778 xfs_btree_cur_t *cur, /* btree cursor */ 779 int level) /* level to change */ 780 { 781 struct xfs_btree_block *block; /* generic btree block pointer */ 782 xfs_buf_t *bp; /* buffer containing block */ 783 784 /* 785 * Get the block pointer for this level. 786 */ 787 block = xfs_btree_get_block(cur, level, &bp); 788 if (xfs_btree_check_block(cur, block, level, bp)) 789 return 0; 790 /* 791 * It's empty, there is no such record. 792 */ 793 if (!block->bb_numrecs) 794 return 0; 795 /* 796 * Set the ptr value to numrecs, that's the last record/key. 797 */ 798 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); 799 return 1; 800 } 801 802 /* 803 * Compute first and last byte offsets for the fields given. 804 * Interprets the offsets table, which contains struct field offsets. 805 */ 806 void 807 xfs_btree_offsets( 808 int64_t fields, /* bitmask of fields */ 809 const short *offsets, /* table of field offsets */ 810 int nbits, /* number of bits to inspect */ 811 int *first, /* output: first byte offset */ 812 int *last) /* output: last byte offset */ 813 { 814 int i; /* current bit number */ 815 int64_t imask; /* mask for current bit number */ 816 817 ASSERT(fields != 0); 818 /* 819 * Find the lowest bit, so the first byte offset. 820 */ 821 for (i = 0, imask = 1LL; ; i++, imask <<= 1) { 822 if (imask & fields) { 823 *first = offsets[i]; 824 break; 825 } 826 } 827 /* 828 * Find the highest bit, so the last byte offset. 829 */ 830 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) { 831 if (imask & fields) { 832 *last = offsets[i + 1] - 1; 833 break; 834 } 835 } 836 } 837 838 /* 839 * Get a buffer for the block, return it read in. 840 * Long-form addressing. 841 */ 842 int 843 xfs_btree_read_bufl( 844 struct xfs_mount *mp, /* file system mount point */ 845 struct xfs_trans *tp, /* transaction pointer */ 846 xfs_fsblock_t fsbno, /* file system block number */ 847 uint lock, /* lock flags for read_buf */ 848 struct xfs_buf **bpp, /* buffer for fsbno */ 849 int refval, /* ref count value for buffer */ 850 const struct xfs_buf_ops *ops) 851 { 852 struct xfs_buf *bp; /* return value */ 853 xfs_daddr_t d; /* real disk block address */ 854 int error; 855 856 if (!XFS_FSB_SANITY_CHECK(mp, fsbno)) 857 return -EFSCORRUPTED; 858 d = XFS_FSB_TO_DADDR(mp, fsbno); 859 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d, 860 mp->m_bsize, lock, &bp, ops); 861 if (error) 862 return error; 863 if (bp) 864 xfs_buf_set_ref(bp, refval); 865 *bpp = bp; 866 return 0; 867 } 868 869 /* 870 * Read-ahead the block, don't wait for it, don't return a buffer. 871 * Long-form addressing. 872 */ 873 /* ARGSUSED */ 874 void 875 xfs_btree_reada_bufl( 876 struct xfs_mount *mp, /* file system mount point */ 877 xfs_fsblock_t fsbno, /* file system block number */ 878 xfs_extlen_t count, /* count of filesystem blocks */ 879 const struct xfs_buf_ops *ops) 880 { 881 xfs_daddr_t d; 882 883 ASSERT(fsbno != NULLFSBLOCK); 884 d = XFS_FSB_TO_DADDR(mp, fsbno); 885 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); 886 } 887 888 /* 889 * Read-ahead the block, don't wait for it, don't return a buffer. 890 * Short-form addressing. 891 */ 892 /* ARGSUSED */ 893 void 894 xfs_btree_reada_bufs( 895 struct xfs_mount *mp, /* file system mount point */ 896 xfs_agnumber_t agno, /* allocation group number */ 897 xfs_agblock_t agbno, /* allocation group block number */ 898 xfs_extlen_t count, /* count of filesystem blocks */ 899 const struct xfs_buf_ops *ops) 900 { 901 xfs_daddr_t d; 902 903 ASSERT(agno != NULLAGNUMBER); 904 ASSERT(agbno != NULLAGBLOCK); 905 d = XFS_AGB_TO_DADDR(mp, agno, agbno); 906 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); 907 } 908 909 STATIC int 910 xfs_btree_readahead_lblock( 911 struct xfs_btree_cur *cur, 912 int lr, 913 struct xfs_btree_block *block) 914 { 915 int rval = 0; 916 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); 917 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); 918 919 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) { 920 xfs_btree_reada_bufl(cur->bc_mp, left, 1, 921 cur->bc_ops->buf_ops); 922 rval++; 923 } 924 925 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) { 926 xfs_btree_reada_bufl(cur->bc_mp, right, 1, 927 cur->bc_ops->buf_ops); 928 rval++; 929 } 930 931 return rval; 932 } 933 934 STATIC int 935 xfs_btree_readahead_sblock( 936 struct xfs_btree_cur *cur, 937 int lr, 938 struct xfs_btree_block *block) 939 { 940 int rval = 0; 941 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); 942 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); 943 944 945 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) { 946 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno, 947 left, 1, cur->bc_ops->buf_ops); 948 rval++; 949 } 950 951 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) { 952 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno, 953 right, 1, cur->bc_ops->buf_ops); 954 rval++; 955 } 956 957 return rval; 958 } 959 960 /* 961 * Read-ahead btree blocks, at the given level. 962 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA. 963 */ 964 STATIC int 965 xfs_btree_readahead( 966 struct xfs_btree_cur *cur, /* btree cursor */ 967 int lev, /* level in btree */ 968 int lr) /* left/right bits */ 969 { 970 struct xfs_btree_block *block; 971 972 /* 973 * No readahead needed if we are at the root level and the 974 * btree root is stored in the inode. 975 */ 976 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 977 (lev == cur->bc_nlevels - 1)) 978 return 0; 979 980 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev]) 981 return 0; 982 983 cur->bc_ra[lev] |= lr; 984 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); 985 986 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 987 return xfs_btree_readahead_lblock(cur, lr, block); 988 return xfs_btree_readahead_sblock(cur, lr, block); 989 } 990 991 STATIC xfs_daddr_t 992 xfs_btree_ptr_to_daddr( 993 struct xfs_btree_cur *cur, 994 union xfs_btree_ptr *ptr) 995 { 996 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 997 ASSERT(ptr->l != cpu_to_be64(NULLFSBLOCK)); 998 999 return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l)); 1000 } else { 1001 ASSERT(cur->bc_private.a.agno != NULLAGNUMBER); 1002 ASSERT(ptr->s != cpu_to_be32(NULLAGBLOCK)); 1003 1004 return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno, 1005 be32_to_cpu(ptr->s)); 1006 } 1007 } 1008 1009 /* 1010 * Readahead @count btree blocks at the given @ptr location. 1011 * 1012 * We don't need to care about long or short form btrees here as we have a 1013 * method of converting the ptr directly to a daddr available to us. 1014 */ 1015 STATIC void 1016 xfs_btree_readahead_ptr( 1017 struct xfs_btree_cur *cur, 1018 union xfs_btree_ptr *ptr, 1019 xfs_extlen_t count) 1020 { 1021 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, 1022 xfs_btree_ptr_to_daddr(cur, ptr), 1023 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops); 1024 } 1025 1026 /* 1027 * Set the buffer for level "lev" in the cursor to bp, releasing 1028 * any previous buffer. 1029 */ 1030 STATIC void 1031 xfs_btree_setbuf( 1032 xfs_btree_cur_t *cur, /* btree cursor */ 1033 int lev, /* level in btree */ 1034 xfs_buf_t *bp) /* new buffer to set */ 1035 { 1036 struct xfs_btree_block *b; /* btree block */ 1037 1038 if (cur->bc_bufs[lev]) 1039 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]); 1040 cur->bc_bufs[lev] = bp; 1041 cur->bc_ra[lev] = 0; 1042 1043 b = XFS_BUF_TO_BLOCK(bp); 1044 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 1045 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)) 1046 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; 1047 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)) 1048 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; 1049 } else { 1050 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK)) 1051 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; 1052 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK)) 1053 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; 1054 } 1055 } 1056 1057 bool 1058 xfs_btree_ptr_is_null( 1059 struct xfs_btree_cur *cur, 1060 union xfs_btree_ptr *ptr) 1061 { 1062 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 1063 return ptr->l == cpu_to_be64(NULLFSBLOCK); 1064 else 1065 return ptr->s == cpu_to_be32(NULLAGBLOCK); 1066 } 1067 1068 STATIC void 1069 xfs_btree_set_ptr_null( 1070 struct xfs_btree_cur *cur, 1071 union xfs_btree_ptr *ptr) 1072 { 1073 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 1074 ptr->l = cpu_to_be64(NULLFSBLOCK); 1075 else 1076 ptr->s = cpu_to_be32(NULLAGBLOCK); 1077 } 1078 1079 /* 1080 * Get/set/init sibling pointers 1081 */ 1082 void 1083 xfs_btree_get_sibling( 1084 struct xfs_btree_cur *cur, 1085 struct xfs_btree_block *block, 1086 union xfs_btree_ptr *ptr, 1087 int lr) 1088 { 1089 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB); 1090 1091 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 1092 if (lr == XFS_BB_RIGHTSIB) 1093 ptr->l = block->bb_u.l.bb_rightsib; 1094 else 1095 ptr->l = block->bb_u.l.bb_leftsib; 1096 } else { 1097 if (lr == XFS_BB_RIGHTSIB) 1098 ptr->s = block->bb_u.s.bb_rightsib; 1099 else 1100 ptr->s = block->bb_u.s.bb_leftsib; 1101 } 1102 } 1103 1104 STATIC void 1105 xfs_btree_set_sibling( 1106 struct xfs_btree_cur *cur, 1107 struct xfs_btree_block *block, 1108 union xfs_btree_ptr *ptr, 1109 int lr) 1110 { 1111 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB); 1112 1113 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 1114 if (lr == XFS_BB_RIGHTSIB) 1115 block->bb_u.l.bb_rightsib = ptr->l; 1116 else 1117 block->bb_u.l.bb_leftsib = ptr->l; 1118 } else { 1119 if (lr == XFS_BB_RIGHTSIB) 1120 block->bb_u.s.bb_rightsib = ptr->s; 1121 else 1122 block->bb_u.s.bb_leftsib = ptr->s; 1123 } 1124 } 1125 1126 void 1127 xfs_btree_init_block_int( 1128 struct xfs_mount *mp, 1129 struct xfs_btree_block *buf, 1130 xfs_daddr_t blkno, 1131 xfs_btnum_t btnum, 1132 __u16 level, 1133 __u16 numrecs, 1134 __u64 owner, 1135 unsigned int flags) 1136 { 1137 int crc = xfs_sb_version_hascrc(&mp->m_sb); 1138 __u32 magic = xfs_btree_magic(crc, btnum); 1139 1140 buf->bb_magic = cpu_to_be32(magic); 1141 buf->bb_level = cpu_to_be16(level); 1142 buf->bb_numrecs = cpu_to_be16(numrecs); 1143 1144 if (flags & XFS_BTREE_LONG_PTRS) { 1145 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK); 1146 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK); 1147 if (crc) { 1148 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno); 1149 buf->bb_u.l.bb_owner = cpu_to_be64(owner); 1150 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid); 1151 buf->bb_u.l.bb_pad = 0; 1152 buf->bb_u.l.bb_lsn = 0; 1153 } 1154 } else { 1155 /* owner is a 32 bit value on short blocks */ 1156 __u32 __owner = (__u32)owner; 1157 1158 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK); 1159 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK); 1160 if (crc) { 1161 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno); 1162 buf->bb_u.s.bb_owner = cpu_to_be32(__owner); 1163 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid); 1164 buf->bb_u.s.bb_lsn = 0; 1165 } 1166 } 1167 } 1168 1169 void 1170 xfs_btree_init_block( 1171 struct xfs_mount *mp, 1172 struct xfs_buf *bp, 1173 xfs_btnum_t btnum, 1174 __u16 level, 1175 __u16 numrecs, 1176 __u64 owner, 1177 unsigned int flags) 1178 { 1179 xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, 1180 btnum, level, numrecs, owner, flags); 1181 } 1182 1183 STATIC void 1184 xfs_btree_init_block_cur( 1185 struct xfs_btree_cur *cur, 1186 struct xfs_buf *bp, 1187 int level, 1188 int numrecs) 1189 { 1190 __u64 owner; 1191 1192 /* 1193 * we can pull the owner from the cursor right now as the different 1194 * owners align directly with the pointer size of the btree. This may 1195 * change in future, but is safe for current users of the generic btree 1196 * code. 1197 */ 1198 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 1199 owner = cur->bc_private.b.ip->i_ino; 1200 else 1201 owner = cur->bc_private.a.agno; 1202 1203 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, 1204 cur->bc_btnum, level, numrecs, 1205 owner, cur->bc_flags); 1206 } 1207 1208 /* 1209 * Return true if ptr is the last record in the btree and 1210 * we need to track updates to this record. The decision 1211 * will be further refined in the update_lastrec method. 1212 */ 1213 STATIC int 1214 xfs_btree_is_lastrec( 1215 struct xfs_btree_cur *cur, 1216 struct xfs_btree_block *block, 1217 int level) 1218 { 1219 union xfs_btree_ptr ptr; 1220 1221 if (level > 0) 1222 return 0; 1223 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE)) 1224 return 0; 1225 1226 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 1227 if (!xfs_btree_ptr_is_null(cur, &ptr)) 1228 return 0; 1229 return 1; 1230 } 1231 1232 STATIC void 1233 xfs_btree_buf_to_ptr( 1234 struct xfs_btree_cur *cur, 1235 struct xfs_buf *bp, 1236 union xfs_btree_ptr *ptr) 1237 { 1238 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 1239 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp, 1240 XFS_BUF_ADDR(bp))); 1241 else { 1242 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp, 1243 XFS_BUF_ADDR(bp))); 1244 } 1245 } 1246 1247 STATIC void 1248 xfs_btree_set_refs( 1249 struct xfs_btree_cur *cur, 1250 struct xfs_buf *bp) 1251 { 1252 switch (cur->bc_btnum) { 1253 case XFS_BTNUM_BNO: 1254 case XFS_BTNUM_CNT: 1255 xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF); 1256 break; 1257 case XFS_BTNUM_INO: 1258 case XFS_BTNUM_FINO: 1259 xfs_buf_set_ref(bp, XFS_INO_BTREE_REF); 1260 break; 1261 case XFS_BTNUM_BMAP: 1262 xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF); 1263 break; 1264 case XFS_BTNUM_RMAP: 1265 xfs_buf_set_ref(bp, XFS_RMAP_BTREE_REF); 1266 break; 1267 case XFS_BTNUM_REFC: 1268 xfs_buf_set_ref(bp, XFS_REFC_BTREE_REF); 1269 break; 1270 default: 1271 ASSERT(0); 1272 } 1273 } 1274 1275 STATIC int 1276 xfs_btree_get_buf_block( 1277 struct xfs_btree_cur *cur, 1278 union xfs_btree_ptr *ptr, 1279 int flags, 1280 struct xfs_btree_block **block, 1281 struct xfs_buf **bpp) 1282 { 1283 struct xfs_mount *mp = cur->bc_mp; 1284 xfs_daddr_t d; 1285 1286 /* need to sort out how callers deal with failures first */ 1287 ASSERT(!(flags & XBF_TRYLOCK)); 1288 1289 d = xfs_btree_ptr_to_daddr(cur, ptr); 1290 *bpp = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, 1291 mp->m_bsize, flags); 1292 1293 if (!*bpp) 1294 return -ENOMEM; 1295 1296 (*bpp)->b_ops = cur->bc_ops->buf_ops; 1297 *block = XFS_BUF_TO_BLOCK(*bpp); 1298 return 0; 1299 } 1300 1301 /* 1302 * Read in the buffer at the given ptr and return the buffer and 1303 * the block pointer within the buffer. 1304 */ 1305 STATIC int 1306 xfs_btree_read_buf_block( 1307 struct xfs_btree_cur *cur, 1308 union xfs_btree_ptr *ptr, 1309 int flags, 1310 struct xfs_btree_block **block, 1311 struct xfs_buf **bpp) 1312 { 1313 struct xfs_mount *mp = cur->bc_mp; 1314 xfs_daddr_t d; 1315 int error; 1316 1317 /* need to sort out how callers deal with failures first */ 1318 ASSERT(!(flags & XBF_TRYLOCK)); 1319 1320 d = xfs_btree_ptr_to_daddr(cur, ptr); 1321 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d, 1322 mp->m_bsize, flags, bpp, 1323 cur->bc_ops->buf_ops); 1324 if (error) 1325 return error; 1326 1327 xfs_btree_set_refs(cur, *bpp); 1328 *block = XFS_BUF_TO_BLOCK(*bpp); 1329 return 0; 1330 } 1331 1332 /* 1333 * Copy keys from one btree block to another. 1334 */ 1335 STATIC void 1336 xfs_btree_copy_keys( 1337 struct xfs_btree_cur *cur, 1338 union xfs_btree_key *dst_key, 1339 union xfs_btree_key *src_key, 1340 int numkeys) 1341 { 1342 ASSERT(numkeys >= 0); 1343 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len); 1344 } 1345 1346 /* 1347 * Copy records from one btree block to another. 1348 */ 1349 STATIC void 1350 xfs_btree_copy_recs( 1351 struct xfs_btree_cur *cur, 1352 union xfs_btree_rec *dst_rec, 1353 union xfs_btree_rec *src_rec, 1354 int numrecs) 1355 { 1356 ASSERT(numrecs >= 0); 1357 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len); 1358 } 1359 1360 /* 1361 * Copy block pointers from one btree block to another. 1362 */ 1363 STATIC void 1364 xfs_btree_copy_ptrs( 1365 struct xfs_btree_cur *cur, 1366 union xfs_btree_ptr *dst_ptr, 1367 union xfs_btree_ptr *src_ptr, 1368 int numptrs) 1369 { 1370 ASSERT(numptrs >= 0); 1371 memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur)); 1372 } 1373 1374 /* 1375 * Shift keys one index left/right inside a single btree block. 1376 */ 1377 STATIC void 1378 xfs_btree_shift_keys( 1379 struct xfs_btree_cur *cur, 1380 union xfs_btree_key *key, 1381 int dir, 1382 int numkeys) 1383 { 1384 char *dst_key; 1385 1386 ASSERT(numkeys >= 0); 1387 ASSERT(dir == 1 || dir == -1); 1388 1389 dst_key = (char *)key + (dir * cur->bc_ops->key_len); 1390 memmove(dst_key, key, numkeys * cur->bc_ops->key_len); 1391 } 1392 1393 /* 1394 * Shift records one index left/right inside a single btree block. 1395 */ 1396 STATIC void 1397 xfs_btree_shift_recs( 1398 struct xfs_btree_cur *cur, 1399 union xfs_btree_rec *rec, 1400 int dir, 1401 int numrecs) 1402 { 1403 char *dst_rec; 1404 1405 ASSERT(numrecs >= 0); 1406 ASSERT(dir == 1 || dir == -1); 1407 1408 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len); 1409 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len); 1410 } 1411 1412 /* 1413 * Shift block pointers one index left/right inside a single btree block. 1414 */ 1415 STATIC void 1416 xfs_btree_shift_ptrs( 1417 struct xfs_btree_cur *cur, 1418 union xfs_btree_ptr *ptr, 1419 int dir, 1420 int numptrs) 1421 { 1422 char *dst_ptr; 1423 1424 ASSERT(numptrs >= 0); 1425 ASSERT(dir == 1 || dir == -1); 1426 1427 dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur)); 1428 memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur)); 1429 } 1430 1431 /* 1432 * Log key values from the btree block. 1433 */ 1434 STATIC void 1435 xfs_btree_log_keys( 1436 struct xfs_btree_cur *cur, 1437 struct xfs_buf *bp, 1438 int first, 1439 int last) 1440 { 1441 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1442 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last); 1443 1444 if (bp) { 1445 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); 1446 xfs_trans_log_buf(cur->bc_tp, bp, 1447 xfs_btree_key_offset(cur, first), 1448 xfs_btree_key_offset(cur, last + 1) - 1); 1449 } else { 1450 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, 1451 xfs_ilog_fbroot(cur->bc_private.b.whichfork)); 1452 } 1453 1454 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1455 } 1456 1457 /* 1458 * Log record values from the btree block. 1459 */ 1460 void 1461 xfs_btree_log_recs( 1462 struct xfs_btree_cur *cur, 1463 struct xfs_buf *bp, 1464 int first, 1465 int last) 1466 { 1467 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1468 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last); 1469 1470 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); 1471 xfs_trans_log_buf(cur->bc_tp, bp, 1472 xfs_btree_rec_offset(cur, first), 1473 xfs_btree_rec_offset(cur, last + 1) - 1); 1474 1475 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1476 } 1477 1478 /* 1479 * Log block pointer fields from a btree block (nonleaf). 1480 */ 1481 STATIC void 1482 xfs_btree_log_ptrs( 1483 struct xfs_btree_cur *cur, /* btree cursor */ 1484 struct xfs_buf *bp, /* buffer containing btree block */ 1485 int first, /* index of first pointer to log */ 1486 int last) /* index of last pointer to log */ 1487 { 1488 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1489 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last); 1490 1491 if (bp) { 1492 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 1493 int level = xfs_btree_get_level(block); 1494 1495 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); 1496 xfs_trans_log_buf(cur->bc_tp, bp, 1497 xfs_btree_ptr_offset(cur, first, level), 1498 xfs_btree_ptr_offset(cur, last + 1, level) - 1); 1499 } else { 1500 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, 1501 xfs_ilog_fbroot(cur->bc_private.b.whichfork)); 1502 } 1503 1504 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1505 } 1506 1507 /* 1508 * Log fields from a btree block header. 1509 */ 1510 void 1511 xfs_btree_log_block( 1512 struct xfs_btree_cur *cur, /* btree cursor */ 1513 struct xfs_buf *bp, /* buffer containing btree block */ 1514 int fields) /* mask of fields: XFS_BB_... */ 1515 { 1516 int first; /* first byte offset logged */ 1517 int last; /* last byte offset logged */ 1518 static const short soffsets[] = { /* table of offsets (short) */ 1519 offsetof(struct xfs_btree_block, bb_magic), 1520 offsetof(struct xfs_btree_block, bb_level), 1521 offsetof(struct xfs_btree_block, bb_numrecs), 1522 offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib), 1523 offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib), 1524 offsetof(struct xfs_btree_block, bb_u.s.bb_blkno), 1525 offsetof(struct xfs_btree_block, bb_u.s.bb_lsn), 1526 offsetof(struct xfs_btree_block, bb_u.s.bb_uuid), 1527 offsetof(struct xfs_btree_block, bb_u.s.bb_owner), 1528 offsetof(struct xfs_btree_block, bb_u.s.bb_crc), 1529 XFS_BTREE_SBLOCK_CRC_LEN 1530 }; 1531 static const short loffsets[] = { /* table of offsets (long) */ 1532 offsetof(struct xfs_btree_block, bb_magic), 1533 offsetof(struct xfs_btree_block, bb_level), 1534 offsetof(struct xfs_btree_block, bb_numrecs), 1535 offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib), 1536 offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib), 1537 offsetof(struct xfs_btree_block, bb_u.l.bb_blkno), 1538 offsetof(struct xfs_btree_block, bb_u.l.bb_lsn), 1539 offsetof(struct xfs_btree_block, bb_u.l.bb_uuid), 1540 offsetof(struct xfs_btree_block, bb_u.l.bb_owner), 1541 offsetof(struct xfs_btree_block, bb_u.l.bb_crc), 1542 offsetof(struct xfs_btree_block, bb_u.l.bb_pad), 1543 XFS_BTREE_LBLOCK_CRC_LEN 1544 }; 1545 1546 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1547 XFS_BTREE_TRACE_ARGBI(cur, bp, fields); 1548 1549 if (bp) { 1550 int nbits; 1551 1552 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { 1553 /* 1554 * We don't log the CRC when updating a btree 1555 * block but instead recreate it during log 1556 * recovery. As the log buffers have checksums 1557 * of their own this is safe and avoids logging a crc 1558 * update in a lot of places. 1559 */ 1560 if (fields == XFS_BB_ALL_BITS) 1561 fields = XFS_BB_ALL_BITS_CRC; 1562 nbits = XFS_BB_NUM_BITS_CRC; 1563 } else { 1564 nbits = XFS_BB_NUM_BITS; 1565 } 1566 xfs_btree_offsets(fields, 1567 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? 1568 loffsets : soffsets, 1569 nbits, &first, &last); 1570 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); 1571 xfs_trans_log_buf(cur->bc_tp, bp, first, last); 1572 } else { 1573 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, 1574 xfs_ilog_fbroot(cur->bc_private.b.whichfork)); 1575 } 1576 1577 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1578 } 1579 1580 /* 1581 * Increment cursor by one record at the level. 1582 * For nonzero levels the leaf-ward information is untouched. 1583 */ 1584 int /* error */ 1585 xfs_btree_increment( 1586 struct xfs_btree_cur *cur, 1587 int level, 1588 int *stat) /* success/failure */ 1589 { 1590 struct xfs_btree_block *block; 1591 union xfs_btree_ptr ptr; 1592 struct xfs_buf *bp; 1593 int error; /* error return value */ 1594 int lev; 1595 1596 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1597 XFS_BTREE_TRACE_ARGI(cur, level); 1598 1599 ASSERT(level < cur->bc_nlevels); 1600 1601 /* Read-ahead to the right at this level. */ 1602 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); 1603 1604 /* Get a pointer to the btree block. */ 1605 block = xfs_btree_get_block(cur, level, &bp); 1606 1607 #ifdef DEBUG 1608 error = xfs_btree_check_block(cur, block, level, bp); 1609 if (error) 1610 goto error0; 1611 #endif 1612 1613 /* We're done if we remain in the block after the increment. */ 1614 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) 1615 goto out1; 1616 1617 /* Fail if we just went off the right edge of the tree. */ 1618 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 1619 if (xfs_btree_ptr_is_null(cur, &ptr)) 1620 goto out0; 1621 1622 XFS_BTREE_STATS_INC(cur, increment); 1623 1624 /* 1625 * March up the tree incrementing pointers. 1626 * Stop when we don't go off the right edge of a block. 1627 */ 1628 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { 1629 block = xfs_btree_get_block(cur, lev, &bp); 1630 1631 #ifdef DEBUG 1632 error = xfs_btree_check_block(cur, block, lev, bp); 1633 if (error) 1634 goto error0; 1635 #endif 1636 1637 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) 1638 break; 1639 1640 /* Read-ahead the right block for the next loop. */ 1641 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA); 1642 } 1643 1644 /* 1645 * If we went off the root then we are either seriously 1646 * confused or have the tree root in an inode. 1647 */ 1648 if (lev == cur->bc_nlevels) { 1649 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 1650 goto out0; 1651 ASSERT(0); 1652 error = -EFSCORRUPTED; 1653 goto error0; 1654 } 1655 ASSERT(lev < cur->bc_nlevels); 1656 1657 /* 1658 * Now walk back down the tree, fixing up the cursor's buffer 1659 * pointers and key numbers. 1660 */ 1661 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { 1662 union xfs_btree_ptr *ptrp; 1663 1664 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); 1665 --lev; 1666 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); 1667 if (error) 1668 goto error0; 1669 1670 xfs_btree_setbuf(cur, lev, bp); 1671 cur->bc_ptrs[lev] = 1; 1672 } 1673 out1: 1674 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1675 *stat = 1; 1676 return 0; 1677 1678 out0: 1679 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1680 *stat = 0; 1681 return 0; 1682 1683 error0: 1684 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 1685 return error; 1686 } 1687 1688 /* 1689 * Decrement cursor by one record at the level. 1690 * For nonzero levels the leaf-ward information is untouched. 1691 */ 1692 int /* error */ 1693 xfs_btree_decrement( 1694 struct xfs_btree_cur *cur, 1695 int level, 1696 int *stat) /* success/failure */ 1697 { 1698 struct xfs_btree_block *block; 1699 xfs_buf_t *bp; 1700 int error; /* error return value */ 1701 int lev; 1702 union xfs_btree_ptr ptr; 1703 1704 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1705 XFS_BTREE_TRACE_ARGI(cur, level); 1706 1707 ASSERT(level < cur->bc_nlevels); 1708 1709 /* Read-ahead to the left at this level. */ 1710 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); 1711 1712 /* We're done if we remain in the block after the decrement. */ 1713 if (--cur->bc_ptrs[level] > 0) 1714 goto out1; 1715 1716 /* Get a pointer to the btree block. */ 1717 block = xfs_btree_get_block(cur, level, &bp); 1718 1719 #ifdef DEBUG 1720 error = xfs_btree_check_block(cur, block, level, bp); 1721 if (error) 1722 goto error0; 1723 #endif 1724 1725 /* Fail if we just went off the left edge of the tree. */ 1726 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); 1727 if (xfs_btree_ptr_is_null(cur, &ptr)) 1728 goto out0; 1729 1730 XFS_BTREE_STATS_INC(cur, decrement); 1731 1732 /* 1733 * March up the tree decrementing pointers. 1734 * Stop when we don't go off the left edge of a block. 1735 */ 1736 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { 1737 if (--cur->bc_ptrs[lev] > 0) 1738 break; 1739 /* Read-ahead the left block for the next loop. */ 1740 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA); 1741 } 1742 1743 /* 1744 * If we went off the root then we are seriously confused. 1745 * or the root of the tree is in an inode. 1746 */ 1747 if (lev == cur->bc_nlevels) { 1748 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 1749 goto out0; 1750 ASSERT(0); 1751 error = -EFSCORRUPTED; 1752 goto error0; 1753 } 1754 ASSERT(lev < cur->bc_nlevels); 1755 1756 /* 1757 * Now walk back down the tree, fixing up the cursor's buffer 1758 * pointers and key numbers. 1759 */ 1760 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { 1761 union xfs_btree_ptr *ptrp; 1762 1763 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); 1764 --lev; 1765 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); 1766 if (error) 1767 goto error0; 1768 xfs_btree_setbuf(cur, lev, bp); 1769 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); 1770 } 1771 out1: 1772 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1773 *stat = 1; 1774 return 0; 1775 1776 out0: 1777 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1778 *stat = 0; 1779 return 0; 1780 1781 error0: 1782 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 1783 return error; 1784 } 1785 1786 int 1787 xfs_btree_lookup_get_block( 1788 struct xfs_btree_cur *cur, /* btree cursor */ 1789 int level, /* level in the btree */ 1790 union xfs_btree_ptr *pp, /* ptr to btree block */ 1791 struct xfs_btree_block **blkp) /* return btree block */ 1792 { 1793 struct xfs_buf *bp; /* buffer pointer for btree block */ 1794 int error = 0; 1795 1796 /* special case the root block if in an inode */ 1797 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 1798 (level == cur->bc_nlevels - 1)) { 1799 *blkp = xfs_btree_get_iroot(cur); 1800 return 0; 1801 } 1802 1803 /* 1804 * If the old buffer at this level for the disk address we are 1805 * looking for re-use it. 1806 * 1807 * Otherwise throw it away and get a new one. 1808 */ 1809 bp = cur->bc_bufs[level]; 1810 if (bp && XFS_BUF_ADDR(bp) == xfs_btree_ptr_to_daddr(cur, pp)) { 1811 *blkp = XFS_BUF_TO_BLOCK(bp); 1812 return 0; 1813 } 1814 1815 error = xfs_btree_read_buf_block(cur, pp, 0, blkp, &bp); 1816 if (error) 1817 return error; 1818 1819 /* Check the inode owner since the verifiers don't. */ 1820 if (xfs_sb_version_hascrc(&cur->bc_mp->m_sb) && 1821 !(cur->bc_private.b.flags & XFS_BTCUR_BPRV_INVALID_OWNER) && 1822 (cur->bc_flags & XFS_BTREE_LONG_PTRS) && 1823 be64_to_cpu((*blkp)->bb_u.l.bb_owner) != 1824 cur->bc_private.b.ip->i_ino) 1825 goto out_bad; 1826 1827 /* Did we get the level we were looking for? */ 1828 if (be16_to_cpu((*blkp)->bb_level) != level) 1829 goto out_bad; 1830 1831 /* Check that internal nodes have at least one record. */ 1832 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0) 1833 goto out_bad; 1834 1835 xfs_btree_setbuf(cur, level, bp); 1836 return 0; 1837 1838 out_bad: 1839 *blkp = NULL; 1840 xfs_trans_brelse(cur->bc_tp, bp); 1841 return -EFSCORRUPTED; 1842 } 1843 1844 /* 1845 * Get current search key. For level 0 we don't actually have a key 1846 * structure so we make one up from the record. For all other levels 1847 * we just return the right key. 1848 */ 1849 STATIC union xfs_btree_key * 1850 xfs_lookup_get_search_key( 1851 struct xfs_btree_cur *cur, 1852 int level, 1853 int keyno, 1854 struct xfs_btree_block *block, 1855 union xfs_btree_key *kp) 1856 { 1857 if (level == 0) { 1858 cur->bc_ops->init_key_from_rec(kp, 1859 xfs_btree_rec_addr(cur, keyno, block)); 1860 return kp; 1861 } 1862 1863 return xfs_btree_key_addr(cur, keyno, block); 1864 } 1865 1866 /* 1867 * Lookup the record. The cursor is made to point to it, based on dir. 1868 * stat is set to 0 if can't find any such record, 1 for success. 1869 */ 1870 int /* error */ 1871 xfs_btree_lookup( 1872 struct xfs_btree_cur *cur, /* btree cursor */ 1873 xfs_lookup_t dir, /* <=, ==, or >= */ 1874 int *stat) /* success/failure */ 1875 { 1876 struct xfs_btree_block *block; /* current btree block */ 1877 int64_t diff; /* difference for the current key */ 1878 int error; /* error return value */ 1879 int keyno; /* current key number */ 1880 int level; /* level in the btree */ 1881 union xfs_btree_ptr *pp; /* ptr to btree block */ 1882 union xfs_btree_ptr ptr; /* ptr to btree block */ 1883 1884 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 1885 XFS_BTREE_TRACE_ARGI(cur, dir); 1886 1887 XFS_BTREE_STATS_INC(cur, lookup); 1888 1889 /* No such thing as a zero-level tree. */ 1890 if (cur->bc_nlevels == 0) 1891 return -EFSCORRUPTED; 1892 1893 block = NULL; 1894 keyno = 0; 1895 1896 /* initialise start pointer from cursor */ 1897 cur->bc_ops->init_ptr_from_cur(cur, &ptr); 1898 pp = &ptr; 1899 1900 /* 1901 * Iterate over each level in the btree, starting at the root. 1902 * For each level above the leaves, find the key we need, based 1903 * on the lookup record, then follow the corresponding block 1904 * pointer down to the next level. 1905 */ 1906 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { 1907 /* Get the block we need to do the lookup on. */ 1908 error = xfs_btree_lookup_get_block(cur, level, pp, &block); 1909 if (error) 1910 goto error0; 1911 1912 if (diff == 0) { 1913 /* 1914 * If we already had a key match at a higher level, we 1915 * know we need to use the first entry in this block. 1916 */ 1917 keyno = 1; 1918 } else { 1919 /* Otherwise search this block. Do a binary search. */ 1920 1921 int high; /* high entry number */ 1922 int low; /* low entry number */ 1923 1924 /* Set low and high entry numbers, 1-based. */ 1925 low = 1; 1926 high = xfs_btree_get_numrecs(block); 1927 if (!high) { 1928 /* Block is empty, must be an empty leaf. */ 1929 ASSERT(level == 0 && cur->bc_nlevels == 1); 1930 1931 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; 1932 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1933 *stat = 0; 1934 return 0; 1935 } 1936 1937 /* Binary search the block. */ 1938 while (low <= high) { 1939 union xfs_btree_key key; 1940 union xfs_btree_key *kp; 1941 1942 XFS_BTREE_STATS_INC(cur, compare); 1943 1944 /* keyno is average of low and high. */ 1945 keyno = (low + high) >> 1; 1946 1947 /* Get current search key */ 1948 kp = xfs_lookup_get_search_key(cur, level, 1949 keyno, block, &key); 1950 1951 /* 1952 * Compute difference to get next direction: 1953 * - less than, move right 1954 * - greater than, move left 1955 * - equal, we're done 1956 */ 1957 diff = cur->bc_ops->key_diff(cur, kp); 1958 if (diff < 0) 1959 low = keyno + 1; 1960 else if (diff > 0) 1961 high = keyno - 1; 1962 else 1963 break; 1964 } 1965 } 1966 1967 /* 1968 * If there are more levels, set up for the next level 1969 * by getting the block number and filling in the cursor. 1970 */ 1971 if (level > 0) { 1972 /* 1973 * If we moved left, need the previous key number, 1974 * unless there isn't one. 1975 */ 1976 if (diff > 0 && --keyno < 1) 1977 keyno = 1; 1978 pp = xfs_btree_ptr_addr(cur, keyno, block); 1979 1980 #ifdef DEBUG 1981 error = xfs_btree_check_ptr(cur, pp, 0, level); 1982 if (error) 1983 goto error0; 1984 #endif 1985 cur->bc_ptrs[level] = keyno; 1986 } 1987 } 1988 1989 /* Done with the search. See if we need to adjust the results. */ 1990 if (dir != XFS_LOOKUP_LE && diff < 0) { 1991 keyno++; 1992 /* 1993 * If ge search and we went off the end of the block, but it's 1994 * not the last block, we're in the wrong block. 1995 */ 1996 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 1997 if (dir == XFS_LOOKUP_GE && 1998 keyno > xfs_btree_get_numrecs(block) && 1999 !xfs_btree_ptr_is_null(cur, &ptr)) { 2000 int i; 2001 2002 cur->bc_ptrs[0] = keyno; 2003 error = xfs_btree_increment(cur, 0, &i); 2004 if (error) 2005 goto error0; 2006 XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, i == 1); 2007 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2008 *stat = 1; 2009 return 0; 2010 } 2011 } else if (dir == XFS_LOOKUP_LE && diff > 0) 2012 keyno--; 2013 cur->bc_ptrs[0] = keyno; 2014 2015 /* Return if we succeeded or not. */ 2016 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) 2017 *stat = 0; 2018 else if (dir != XFS_LOOKUP_EQ || diff == 0) 2019 *stat = 1; 2020 else 2021 *stat = 0; 2022 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2023 return 0; 2024 2025 error0: 2026 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2027 return error; 2028 } 2029 2030 /* Find the high key storage area from a regular key. */ 2031 union xfs_btree_key * 2032 xfs_btree_high_key_from_key( 2033 struct xfs_btree_cur *cur, 2034 union xfs_btree_key *key) 2035 { 2036 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); 2037 return (union xfs_btree_key *)((char *)key + 2038 (cur->bc_ops->key_len / 2)); 2039 } 2040 2041 /* Determine the low (and high if overlapped) keys of a leaf block */ 2042 STATIC void 2043 xfs_btree_get_leaf_keys( 2044 struct xfs_btree_cur *cur, 2045 struct xfs_btree_block *block, 2046 union xfs_btree_key *key) 2047 { 2048 union xfs_btree_key max_hkey; 2049 union xfs_btree_key hkey; 2050 union xfs_btree_rec *rec; 2051 union xfs_btree_key *high; 2052 int n; 2053 2054 rec = xfs_btree_rec_addr(cur, 1, block); 2055 cur->bc_ops->init_key_from_rec(key, rec); 2056 2057 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2058 2059 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); 2060 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { 2061 rec = xfs_btree_rec_addr(cur, n, block); 2062 cur->bc_ops->init_high_key_from_rec(&hkey, rec); 2063 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) 2064 > 0) 2065 max_hkey = hkey; 2066 } 2067 2068 high = xfs_btree_high_key_from_key(cur, key); 2069 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); 2070 } 2071 } 2072 2073 /* Determine the low (and high if overlapped) keys of a node block */ 2074 STATIC void 2075 xfs_btree_get_node_keys( 2076 struct xfs_btree_cur *cur, 2077 struct xfs_btree_block *block, 2078 union xfs_btree_key *key) 2079 { 2080 union xfs_btree_key *hkey; 2081 union xfs_btree_key *max_hkey; 2082 union xfs_btree_key *high; 2083 int n; 2084 2085 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2086 memcpy(key, xfs_btree_key_addr(cur, 1, block), 2087 cur->bc_ops->key_len / 2); 2088 2089 max_hkey = xfs_btree_high_key_addr(cur, 1, block); 2090 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { 2091 hkey = xfs_btree_high_key_addr(cur, n, block); 2092 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) 2093 max_hkey = hkey; 2094 } 2095 2096 high = xfs_btree_high_key_from_key(cur, key); 2097 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); 2098 } else { 2099 memcpy(key, xfs_btree_key_addr(cur, 1, block), 2100 cur->bc_ops->key_len); 2101 } 2102 } 2103 2104 /* Derive the keys for any btree block. */ 2105 void 2106 xfs_btree_get_keys( 2107 struct xfs_btree_cur *cur, 2108 struct xfs_btree_block *block, 2109 union xfs_btree_key *key) 2110 { 2111 if (be16_to_cpu(block->bb_level) == 0) 2112 xfs_btree_get_leaf_keys(cur, block, key); 2113 else 2114 xfs_btree_get_node_keys(cur, block, key); 2115 } 2116 2117 /* 2118 * Decide if we need to update the parent keys of a btree block. For 2119 * a standard btree this is only necessary if we're updating the first 2120 * record/key. For an overlapping btree, we must always update the 2121 * keys because the highest key can be in any of the records or keys 2122 * in the block. 2123 */ 2124 static inline bool 2125 xfs_btree_needs_key_update( 2126 struct xfs_btree_cur *cur, 2127 int ptr) 2128 { 2129 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; 2130 } 2131 2132 /* 2133 * Update the low and high parent keys of the given level, progressing 2134 * towards the root. If force_all is false, stop if the keys for a given 2135 * level do not need updating. 2136 */ 2137 STATIC int 2138 __xfs_btree_updkeys( 2139 struct xfs_btree_cur *cur, 2140 int level, 2141 struct xfs_btree_block *block, 2142 struct xfs_buf *bp0, 2143 bool force_all) 2144 { 2145 union xfs_btree_key key; /* keys from current level */ 2146 union xfs_btree_key *lkey; /* keys from the next level up */ 2147 union xfs_btree_key *hkey; 2148 union xfs_btree_key *nlkey; /* keys from the next level up */ 2149 union xfs_btree_key *nhkey; 2150 struct xfs_buf *bp; 2151 int ptr; 2152 2153 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); 2154 2155 /* Exit if there aren't any parent levels to update. */ 2156 if (level + 1 >= cur->bc_nlevels) 2157 return 0; 2158 2159 trace_xfs_btree_updkeys(cur, level, bp0); 2160 2161 lkey = &key; 2162 hkey = xfs_btree_high_key_from_key(cur, lkey); 2163 xfs_btree_get_keys(cur, block, lkey); 2164 for (level++; level < cur->bc_nlevels; level++) { 2165 #ifdef DEBUG 2166 int error; 2167 #endif 2168 block = xfs_btree_get_block(cur, level, &bp); 2169 trace_xfs_btree_updkeys(cur, level, bp); 2170 #ifdef DEBUG 2171 error = xfs_btree_check_block(cur, block, level, bp); 2172 if (error) { 2173 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2174 return error; 2175 } 2176 #endif 2177 ptr = cur->bc_ptrs[level]; 2178 nlkey = xfs_btree_key_addr(cur, ptr, block); 2179 nhkey = xfs_btree_high_key_addr(cur, ptr, block); 2180 if (!force_all && 2181 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || 2182 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) 2183 break; 2184 xfs_btree_copy_keys(cur, nlkey, lkey, 1); 2185 xfs_btree_log_keys(cur, bp, ptr, ptr); 2186 if (level + 1 >= cur->bc_nlevels) 2187 break; 2188 xfs_btree_get_node_keys(cur, block, lkey); 2189 } 2190 2191 return 0; 2192 } 2193 2194 /* Update all the keys from some level in cursor back to the root. */ 2195 STATIC int 2196 xfs_btree_updkeys_force( 2197 struct xfs_btree_cur *cur, 2198 int level) 2199 { 2200 struct xfs_buf *bp; 2201 struct xfs_btree_block *block; 2202 2203 block = xfs_btree_get_block(cur, level, &bp); 2204 return __xfs_btree_updkeys(cur, level, block, bp, true); 2205 } 2206 2207 /* 2208 * Update the parent keys of the given level, progressing towards the root. 2209 */ 2210 STATIC int 2211 xfs_btree_update_keys( 2212 struct xfs_btree_cur *cur, 2213 int level) 2214 { 2215 struct xfs_btree_block *block; 2216 struct xfs_buf *bp; 2217 union xfs_btree_key *kp; 2218 union xfs_btree_key key; 2219 int ptr; 2220 2221 ASSERT(level >= 0); 2222 2223 block = xfs_btree_get_block(cur, level, &bp); 2224 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) 2225 return __xfs_btree_updkeys(cur, level, block, bp, false); 2226 2227 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2228 XFS_BTREE_TRACE_ARGIK(cur, level, keyp); 2229 2230 /* 2231 * Go up the tree from this level toward the root. 2232 * At each level, update the key value to the value input. 2233 * Stop when we reach a level where the cursor isn't pointing 2234 * at the first entry in the block. 2235 */ 2236 xfs_btree_get_keys(cur, block, &key); 2237 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { 2238 #ifdef DEBUG 2239 int error; 2240 #endif 2241 block = xfs_btree_get_block(cur, level, &bp); 2242 #ifdef DEBUG 2243 error = xfs_btree_check_block(cur, block, level, bp); 2244 if (error) { 2245 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2246 return error; 2247 } 2248 #endif 2249 ptr = cur->bc_ptrs[level]; 2250 kp = xfs_btree_key_addr(cur, ptr, block); 2251 xfs_btree_copy_keys(cur, kp, &key, 1); 2252 xfs_btree_log_keys(cur, bp, ptr, ptr); 2253 } 2254 2255 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2256 return 0; 2257 } 2258 2259 /* 2260 * Update the record referred to by cur to the value in the 2261 * given record. This either works (return 0) or gets an 2262 * EFSCORRUPTED error. 2263 */ 2264 int 2265 xfs_btree_update( 2266 struct xfs_btree_cur *cur, 2267 union xfs_btree_rec *rec) 2268 { 2269 struct xfs_btree_block *block; 2270 struct xfs_buf *bp; 2271 int error; 2272 int ptr; 2273 union xfs_btree_rec *rp; 2274 2275 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2276 XFS_BTREE_TRACE_ARGR(cur, rec); 2277 2278 /* Pick up the current block. */ 2279 block = xfs_btree_get_block(cur, 0, &bp); 2280 2281 #ifdef DEBUG 2282 error = xfs_btree_check_block(cur, block, 0, bp); 2283 if (error) 2284 goto error0; 2285 #endif 2286 /* Get the address of the rec to be updated. */ 2287 ptr = cur->bc_ptrs[0]; 2288 rp = xfs_btree_rec_addr(cur, ptr, block); 2289 2290 /* Fill in the new contents and log them. */ 2291 xfs_btree_copy_recs(cur, rp, rec, 1); 2292 xfs_btree_log_recs(cur, bp, ptr, ptr); 2293 2294 /* 2295 * If we are tracking the last record in the tree and 2296 * we are at the far right edge of the tree, update it. 2297 */ 2298 if (xfs_btree_is_lastrec(cur, block, 0)) { 2299 cur->bc_ops->update_lastrec(cur, block, rec, 2300 ptr, LASTREC_UPDATE); 2301 } 2302 2303 /* Pass new key value up to our parent. */ 2304 if (xfs_btree_needs_key_update(cur, ptr)) { 2305 error = xfs_btree_update_keys(cur, 0); 2306 if (error) 2307 goto error0; 2308 } 2309 2310 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2311 return 0; 2312 2313 error0: 2314 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2315 return error; 2316 } 2317 2318 /* 2319 * Move 1 record left from cur/level if possible. 2320 * Update cur to reflect the new path. 2321 */ 2322 STATIC int /* error */ 2323 xfs_btree_lshift( 2324 struct xfs_btree_cur *cur, 2325 int level, 2326 int *stat) /* success/failure */ 2327 { 2328 struct xfs_buf *lbp; /* left buffer pointer */ 2329 struct xfs_btree_block *left; /* left btree block */ 2330 int lrecs; /* left record count */ 2331 struct xfs_buf *rbp; /* right buffer pointer */ 2332 struct xfs_btree_block *right; /* right btree block */ 2333 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 2334 int rrecs; /* right record count */ 2335 union xfs_btree_ptr lptr; /* left btree pointer */ 2336 union xfs_btree_key *rkp = NULL; /* right btree key */ 2337 union xfs_btree_ptr *rpp = NULL; /* right address pointer */ 2338 union xfs_btree_rec *rrp = NULL; /* right record pointer */ 2339 int error; /* error return value */ 2340 int i; 2341 2342 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2343 XFS_BTREE_TRACE_ARGI(cur, level); 2344 2345 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 2346 level == cur->bc_nlevels - 1) 2347 goto out0; 2348 2349 /* Set up variables for this block as "right". */ 2350 right = xfs_btree_get_block(cur, level, &rbp); 2351 2352 #ifdef DEBUG 2353 error = xfs_btree_check_block(cur, right, level, rbp); 2354 if (error) 2355 goto error0; 2356 #endif 2357 2358 /* If we've got no left sibling then we can't shift an entry left. */ 2359 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 2360 if (xfs_btree_ptr_is_null(cur, &lptr)) 2361 goto out0; 2362 2363 /* 2364 * If the cursor entry is the one that would be moved, don't 2365 * do it... it's too complicated. 2366 */ 2367 if (cur->bc_ptrs[level] <= 1) 2368 goto out0; 2369 2370 /* Set up the left neighbor as "left". */ 2371 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 2372 if (error) 2373 goto error0; 2374 2375 /* If it's full, it can't take another entry. */ 2376 lrecs = xfs_btree_get_numrecs(left); 2377 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) 2378 goto out0; 2379 2380 rrecs = xfs_btree_get_numrecs(right); 2381 2382 /* 2383 * We add one entry to the left side and remove one for the right side. 2384 * Account for it here, the changes will be updated on disk and logged 2385 * later. 2386 */ 2387 lrecs++; 2388 rrecs--; 2389 2390 XFS_BTREE_STATS_INC(cur, lshift); 2391 XFS_BTREE_STATS_ADD(cur, moves, 1); 2392 2393 /* 2394 * If non-leaf, copy a key and a ptr to the left block. 2395 * Log the changes to the left block. 2396 */ 2397 if (level > 0) { 2398 /* It's a non-leaf. Move keys and pointers. */ 2399 union xfs_btree_key *lkp; /* left btree key */ 2400 union xfs_btree_ptr *lpp; /* left address pointer */ 2401 2402 lkp = xfs_btree_key_addr(cur, lrecs, left); 2403 rkp = xfs_btree_key_addr(cur, 1, right); 2404 2405 lpp = xfs_btree_ptr_addr(cur, lrecs, left); 2406 rpp = xfs_btree_ptr_addr(cur, 1, right); 2407 #ifdef DEBUG 2408 error = xfs_btree_check_ptr(cur, rpp, 0, level); 2409 if (error) 2410 goto error0; 2411 #endif 2412 xfs_btree_copy_keys(cur, lkp, rkp, 1); 2413 xfs_btree_copy_ptrs(cur, lpp, rpp, 1); 2414 2415 xfs_btree_log_keys(cur, lbp, lrecs, lrecs); 2416 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs); 2417 2418 ASSERT(cur->bc_ops->keys_inorder(cur, 2419 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); 2420 } else { 2421 /* It's a leaf. Move records. */ 2422 union xfs_btree_rec *lrp; /* left record pointer */ 2423 2424 lrp = xfs_btree_rec_addr(cur, lrecs, left); 2425 rrp = xfs_btree_rec_addr(cur, 1, right); 2426 2427 xfs_btree_copy_recs(cur, lrp, rrp, 1); 2428 xfs_btree_log_recs(cur, lbp, lrecs, lrecs); 2429 2430 ASSERT(cur->bc_ops->recs_inorder(cur, 2431 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); 2432 } 2433 2434 xfs_btree_set_numrecs(left, lrecs); 2435 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS); 2436 2437 xfs_btree_set_numrecs(right, rrecs); 2438 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS); 2439 2440 /* 2441 * Slide the contents of right down one entry. 2442 */ 2443 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); 2444 if (level > 0) { 2445 /* It's a nonleaf. operate on keys and ptrs */ 2446 #ifdef DEBUG 2447 int i; /* loop index */ 2448 2449 for (i = 0; i < rrecs; i++) { 2450 error = xfs_btree_check_ptr(cur, rpp, i + 1, level); 2451 if (error) 2452 goto error0; 2453 } 2454 #endif 2455 xfs_btree_shift_keys(cur, 2456 xfs_btree_key_addr(cur, 2, right), 2457 -1, rrecs); 2458 xfs_btree_shift_ptrs(cur, 2459 xfs_btree_ptr_addr(cur, 2, right), 2460 -1, rrecs); 2461 2462 xfs_btree_log_keys(cur, rbp, 1, rrecs); 2463 xfs_btree_log_ptrs(cur, rbp, 1, rrecs); 2464 } else { 2465 /* It's a leaf. operate on records */ 2466 xfs_btree_shift_recs(cur, 2467 xfs_btree_rec_addr(cur, 2, right), 2468 -1, rrecs); 2469 xfs_btree_log_recs(cur, rbp, 1, rrecs); 2470 } 2471 2472 /* 2473 * Using a temporary cursor, update the parent key values of the 2474 * block on the left. 2475 */ 2476 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2477 error = xfs_btree_dup_cursor(cur, &tcur); 2478 if (error) 2479 goto error0; 2480 i = xfs_btree_firstrec(tcur, level); 2481 XFS_WANT_CORRUPTED_GOTO(tcur->bc_mp, i == 1, error0); 2482 2483 error = xfs_btree_decrement(tcur, level, &i); 2484 if (error) 2485 goto error1; 2486 2487 /* Update the parent high keys of the left block, if needed. */ 2488 error = xfs_btree_update_keys(tcur, level); 2489 if (error) 2490 goto error1; 2491 2492 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 2493 } 2494 2495 /* Update the parent keys of the right block. */ 2496 error = xfs_btree_update_keys(cur, level); 2497 if (error) 2498 goto error0; 2499 2500 /* Slide the cursor value left one. */ 2501 cur->bc_ptrs[level]--; 2502 2503 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2504 *stat = 1; 2505 return 0; 2506 2507 out0: 2508 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2509 *stat = 0; 2510 return 0; 2511 2512 error0: 2513 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2514 return error; 2515 2516 error1: 2517 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR); 2518 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 2519 return error; 2520 } 2521 2522 /* 2523 * Move 1 record right from cur/level if possible. 2524 * Update cur to reflect the new path. 2525 */ 2526 STATIC int /* error */ 2527 xfs_btree_rshift( 2528 struct xfs_btree_cur *cur, 2529 int level, 2530 int *stat) /* success/failure */ 2531 { 2532 struct xfs_buf *lbp; /* left buffer pointer */ 2533 struct xfs_btree_block *left; /* left btree block */ 2534 struct xfs_buf *rbp; /* right buffer pointer */ 2535 struct xfs_btree_block *right; /* right btree block */ 2536 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 2537 union xfs_btree_ptr rptr; /* right block pointer */ 2538 union xfs_btree_key *rkp; /* right btree key */ 2539 int rrecs; /* right record count */ 2540 int lrecs; /* left record count */ 2541 int error; /* error return value */ 2542 int i; /* loop counter */ 2543 2544 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2545 XFS_BTREE_TRACE_ARGI(cur, level); 2546 2547 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 2548 (level == cur->bc_nlevels - 1)) 2549 goto out0; 2550 2551 /* Set up variables for this block as "left". */ 2552 left = xfs_btree_get_block(cur, level, &lbp); 2553 2554 #ifdef DEBUG 2555 error = xfs_btree_check_block(cur, left, level, lbp); 2556 if (error) 2557 goto error0; 2558 #endif 2559 2560 /* If we've got no right sibling then we can't shift an entry right. */ 2561 xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB); 2562 if (xfs_btree_ptr_is_null(cur, &rptr)) 2563 goto out0; 2564 2565 /* 2566 * If the cursor entry is the one that would be moved, don't 2567 * do it... it's too complicated. 2568 */ 2569 lrecs = xfs_btree_get_numrecs(left); 2570 if (cur->bc_ptrs[level] >= lrecs) 2571 goto out0; 2572 2573 /* Set up the right neighbor as "right". */ 2574 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 2575 if (error) 2576 goto error0; 2577 2578 /* If it's full, it can't take another entry. */ 2579 rrecs = xfs_btree_get_numrecs(right); 2580 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) 2581 goto out0; 2582 2583 XFS_BTREE_STATS_INC(cur, rshift); 2584 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 2585 2586 /* 2587 * Make a hole at the start of the right neighbor block, then 2588 * copy the last left block entry to the hole. 2589 */ 2590 if (level > 0) { 2591 /* It's a nonleaf. make a hole in the keys and ptrs */ 2592 union xfs_btree_key *lkp; 2593 union xfs_btree_ptr *lpp; 2594 union xfs_btree_ptr *rpp; 2595 2596 lkp = xfs_btree_key_addr(cur, lrecs, left); 2597 lpp = xfs_btree_ptr_addr(cur, lrecs, left); 2598 rkp = xfs_btree_key_addr(cur, 1, right); 2599 rpp = xfs_btree_ptr_addr(cur, 1, right); 2600 2601 #ifdef DEBUG 2602 for (i = rrecs - 1; i >= 0; i--) { 2603 error = xfs_btree_check_ptr(cur, rpp, i, level); 2604 if (error) 2605 goto error0; 2606 } 2607 #endif 2608 2609 xfs_btree_shift_keys(cur, rkp, 1, rrecs); 2610 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs); 2611 2612 #ifdef DEBUG 2613 error = xfs_btree_check_ptr(cur, lpp, 0, level); 2614 if (error) 2615 goto error0; 2616 #endif 2617 2618 /* Now put the new data in, and log it. */ 2619 xfs_btree_copy_keys(cur, rkp, lkp, 1); 2620 xfs_btree_copy_ptrs(cur, rpp, lpp, 1); 2621 2622 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1); 2623 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1); 2624 2625 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, 2626 xfs_btree_key_addr(cur, 2, right))); 2627 } else { 2628 /* It's a leaf. make a hole in the records */ 2629 union xfs_btree_rec *lrp; 2630 union xfs_btree_rec *rrp; 2631 2632 lrp = xfs_btree_rec_addr(cur, lrecs, left); 2633 rrp = xfs_btree_rec_addr(cur, 1, right); 2634 2635 xfs_btree_shift_recs(cur, rrp, 1, rrecs); 2636 2637 /* Now put the new data in, and log it. */ 2638 xfs_btree_copy_recs(cur, rrp, lrp, 1); 2639 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1); 2640 } 2641 2642 /* 2643 * Decrement and log left's numrecs, bump and log right's numrecs. 2644 */ 2645 xfs_btree_set_numrecs(left, --lrecs); 2646 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS); 2647 2648 xfs_btree_set_numrecs(right, ++rrecs); 2649 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS); 2650 2651 /* 2652 * Using a temporary cursor, update the parent key values of the 2653 * block on the right. 2654 */ 2655 error = xfs_btree_dup_cursor(cur, &tcur); 2656 if (error) 2657 goto error0; 2658 i = xfs_btree_lastrec(tcur, level); 2659 XFS_WANT_CORRUPTED_GOTO(tcur->bc_mp, i == 1, error0); 2660 2661 error = xfs_btree_increment(tcur, level, &i); 2662 if (error) 2663 goto error1; 2664 2665 /* Update the parent high keys of the left block, if needed. */ 2666 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2667 error = xfs_btree_update_keys(cur, level); 2668 if (error) 2669 goto error1; 2670 } 2671 2672 /* Update the parent keys of the right block. */ 2673 error = xfs_btree_update_keys(tcur, level); 2674 if (error) 2675 goto error1; 2676 2677 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 2678 2679 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2680 *stat = 1; 2681 return 0; 2682 2683 out0: 2684 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2685 *stat = 0; 2686 return 0; 2687 2688 error0: 2689 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2690 return error; 2691 2692 error1: 2693 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR); 2694 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 2695 return error; 2696 } 2697 2698 /* 2699 * Split cur/level block in half. 2700 * Return new block number and the key to its first 2701 * record (to be inserted into parent). 2702 */ 2703 STATIC int /* error */ 2704 __xfs_btree_split( 2705 struct xfs_btree_cur *cur, 2706 int level, 2707 union xfs_btree_ptr *ptrp, 2708 union xfs_btree_key *key, 2709 struct xfs_btree_cur **curp, 2710 int *stat) /* success/failure */ 2711 { 2712 union xfs_btree_ptr lptr; /* left sibling block ptr */ 2713 struct xfs_buf *lbp; /* left buffer pointer */ 2714 struct xfs_btree_block *left; /* left btree block */ 2715 union xfs_btree_ptr rptr; /* right sibling block ptr */ 2716 struct xfs_buf *rbp; /* right buffer pointer */ 2717 struct xfs_btree_block *right; /* right btree block */ 2718 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ 2719 struct xfs_buf *rrbp; /* right-right buffer pointer */ 2720 struct xfs_btree_block *rrblock; /* right-right btree block */ 2721 int lrecs; 2722 int rrecs; 2723 int src_index; 2724 int error; /* error return value */ 2725 #ifdef DEBUG 2726 int i; 2727 #endif 2728 2729 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2730 XFS_BTREE_TRACE_ARGIPK(cur, level, *ptrp, key); 2731 2732 XFS_BTREE_STATS_INC(cur, split); 2733 2734 /* Set up left block (current one). */ 2735 left = xfs_btree_get_block(cur, level, &lbp); 2736 2737 #ifdef DEBUG 2738 error = xfs_btree_check_block(cur, left, level, lbp); 2739 if (error) 2740 goto error0; 2741 #endif 2742 2743 xfs_btree_buf_to_ptr(cur, lbp, &lptr); 2744 2745 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 2746 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); 2747 if (error) 2748 goto error0; 2749 if (*stat == 0) 2750 goto out0; 2751 XFS_BTREE_STATS_INC(cur, alloc); 2752 2753 /* Set up the new block as "right". */ 2754 error = xfs_btree_get_buf_block(cur, &rptr, 0, &right, &rbp); 2755 if (error) 2756 goto error0; 2757 2758 /* Fill in the btree header for the new right block. */ 2759 xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0); 2760 2761 /* 2762 * Split the entries between the old and the new block evenly. 2763 * Make sure that if there's an odd number of entries now, that 2764 * each new block will have the same number of entries. 2765 */ 2766 lrecs = xfs_btree_get_numrecs(left); 2767 rrecs = lrecs / 2; 2768 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1) 2769 rrecs++; 2770 src_index = (lrecs - rrecs + 1); 2771 2772 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 2773 2774 /* Adjust numrecs for the later get_*_keys() calls. */ 2775 lrecs -= rrecs; 2776 xfs_btree_set_numrecs(left, lrecs); 2777 xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs); 2778 2779 /* 2780 * Copy btree block entries from the left block over to the 2781 * new block, the right. Update the right block and log the 2782 * changes. 2783 */ 2784 if (level > 0) { 2785 /* It's a non-leaf. Move keys and pointers. */ 2786 union xfs_btree_key *lkp; /* left btree key */ 2787 union xfs_btree_ptr *lpp; /* left address pointer */ 2788 union xfs_btree_key *rkp; /* right btree key */ 2789 union xfs_btree_ptr *rpp; /* right address pointer */ 2790 2791 lkp = xfs_btree_key_addr(cur, src_index, left); 2792 lpp = xfs_btree_ptr_addr(cur, src_index, left); 2793 rkp = xfs_btree_key_addr(cur, 1, right); 2794 rpp = xfs_btree_ptr_addr(cur, 1, right); 2795 2796 #ifdef DEBUG 2797 for (i = src_index; i < rrecs; i++) { 2798 error = xfs_btree_check_ptr(cur, lpp, i, level); 2799 if (error) 2800 goto error0; 2801 } 2802 #endif 2803 2804 /* Copy the keys & pointers to the new block. */ 2805 xfs_btree_copy_keys(cur, rkp, lkp, rrecs); 2806 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs); 2807 2808 xfs_btree_log_keys(cur, rbp, 1, rrecs); 2809 xfs_btree_log_ptrs(cur, rbp, 1, rrecs); 2810 2811 /* Stash the keys of the new block for later insertion. */ 2812 xfs_btree_get_node_keys(cur, right, key); 2813 } else { 2814 /* It's a leaf. Move records. */ 2815 union xfs_btree_rec *lrp; /* left record pointer */ 2816 union xfs_btree_rec *rrp; /* right record pointer */ 2817 2818 lrp = xfs_btree_rec_addr(cur, src_index, left); 2819 rrp = xfs_btree_rec_addr(cur, 1, right); 2820 2821 /* Copy records to the new block. */ 2822 xfs_btree_copy_recs(cur, rrp, lrp, rrecs); 2823 xfs_btree_log_recs(cur, rbp, 1, rrecs); 2824 2825 /* Stash the keys of the new block for later insertion. */ 2826 xfs_btree_get_leaf_keys(cur, right, key); 2827 } 2828 2829 /* 2830 * Find the left block number by looking in the buffer. 2831 * Adjust sibling pointers. 2832 */ 2833 xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB); 2834 xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB); 2835 xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 2836 xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB); 2837 2838 xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS); 2839 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 2840 2841 /* 2842 * If there's a block to the new block's right, make that block 2843 * point back to right instead of to left. 2844 */ 2845 if (!xfs_btree_ptr_is_null(cur, &rrptr)) { 2846 error = xfs_btree_read_buf_block(cur, &rrptr, 2847 0, &rrblock, &rrbp); 2848 if (error) 2849 goto error0; 2850 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB); 2851 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB); 2852 } 2853 2854 /* Update the parent high keys of the left block, if needed. */ 2855 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2856 error = xfs_btree_update_keys(cur, level); 2857 if (error) 2858 goto error0; 2859 } 2860 2861 /* 2862 * If the cursor is really in the right block, move it there. 2863 * If it's just pointing past the last entry in left, then we'll 2864 * insert there, so don't change anything in that case. 2865 */ 2866 if (cur->bc_ptrs[level] > lrecs + 1) { 2867 xfs_btree_setbuf(cur, level, rbp); 2868 cur->bc_ptrs[level] -= lrecs; 2869 } 2870 /* 2871 * If there are more levels, we'll need another cursor which refers 2872 * the right block, no matter where this cursor was. 2873 */ 2874 if (level + 1 < cur->bc_nlevels) { 2875 error = xfs_btree_dup_cursor(cur, curp); 2876 if (error) 2877 goto error0; 2878 (*curp)->bc_ptrs[level + 1]++; 2879 } 2880 *ptrp = rptr; 2881 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2882 *stat = 1; 2883 return 0; 2884 out0: 2885 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2886 *stat = 0; 2887 return 0; 2888 2889 error0: 2890 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2891 return error; 2892 } 2893 2894 struct xfs_btree_split_args { 2895 struct xfs_btree_cur *cur; 2896 int level; 2897 union xfs_btree_ptr *ptrp; 2898 union xfs_btree_key *key; 2899 struct xfs_btree_cur **curp; 2900 int *stat; /* success/failure */ 2901 int result; 2902 bool kswapd; /* allocation in kswapd context */ 2903 struct completion *done; 2904 struct work_struct work; 2905 }; 2906 2907 /* 2908 * Stack switching interfaces for allocation 2909 */ 2910 static void 2911 xfs_btree_split_worker( 2912 struct work_struct *work) 2913 { 2914 struct xfs_btree_split_args *args = container_of(work, 2915 struct xfs_btree_split_args, work); 2916 unsigned long pflags; 2917 unsigned long new_pflags = PF_MEMALLOC_NOFS; 2918 2919 /* 2920 * we are in a transaction context here, but may also be doing work 2921 * in kswapd context, and hence we may need to inherit that state 2922 * temporarily to ensure that we don't block waiting for memory reclaim 2923 * in any way. 2924 */ 2925 if (args->kswapd) 2926 new_pflags |= PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD; 2927 2928 current_set_flags_nested(&pflags, new_pflags); 2929 2930 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, 2931 args->key, args->curp, args->stat); 2932 complete(args->done); 2933 2934 current_restore_flags_nested(&pflags, new_pflags); 2935 } 2936 2937 /* 2938 * BMBT split requests often come in with little stack to work on. Push 2939 * them off to a worker thread so there is lots of stack to use. For the other 2940 * btree types, just call directly to avoid the context switch overhead here. 2941 */ 2942 STATIC int /* error */ 2943 xfs_btree_split( 2944 struct xfs_btree_cur *cur, 2945 int level, 2946 union xfs_btree_ptr *ptrp, 2947 union xfs_btree_key *key, 2948 struct xfs_btree_cur **curp, 2949 int *stat) /* success/failure */ 2950 { 2951 struct xfs_btree_split_args args; 2952 DECLARE_COMPLETION_ONSTACK(done); 2953 2954 if (cur->bc_btnum != XFS_BTNUM_BMAP) 2955 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); 2956 2957 args.cur = cur; 2958 args.level = level; 2959 args.ptrp = ptrp; 2960 args.key = key; 2961 args.curp = curp; 2962 args.stat = stat; 2963 args.done = &done; 2964 args.kswapd = current_is_kswapd(); 2965 INIT_WORK_ONSTACK(&args.work, xfs_btree_split_worker); 2966 queue_work(xfs_alloc_wq, &args.work); 2967 wait_for_completion(&done); 2968 destroy_work_on_stack(&args.work); 2969 return args.result; 2970 } 2971 2972 2973 /* 2974 * Copy the old inode root contents into a real block and make the 2975 * broot point to it. 2976 */ 2977 int /* error */ 2978 xfs_btree_new_iroot( 2979 struct xfs_btree_cur *cur, /* btree cursor */ 2980 int *logflags, /* logging flags for inode */ 2981 int *stat) /* return status - 0 fail */ 2982 { 2983 struct xfs_buf *cbp; /* buffer for cblock */ 2984 struct xfs_btree_block *block; /* btree block */ 2985 struct xfs_btree_block *cblock; /* child btree block */ 2986 union xfs_btree_key *ckp; /* child key pointer */ 2987 union xfs_btree_ptr *cpp; /* child ptr pointer */ 2988 union xfs_btree_key *kp; /* pointer to btree key */ 2989 union xfs_btree_ptr *pp; /* pointer to block addr */ 2990 union xfs_btree_ptr nptr; /* new block addr */ 2991 int level; /* btree level */ 2992 int error; /* error return code */ 2993 #ifdef DEBUG 2994 int i; /* loop counter */ 2995 #endif 2996 2997 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2998 XFS_BTREE_STATS_INC(cur, newroot); 2999 3000 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 3001 3002 level = cur->bc_nlevels - 1; 3003 3004 block = xfs_btree_get_iroot(cur); 3005 pp = xfs_btree_ptr_addr(cur, 1, block); 3006 3007 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 3008 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); 3009 if (error) 3010 goto error0; 3011 if (*stat == 0) { 3012 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3013 return 0; 3014 } 3015 XFS_BTREE_STATS_INC(cur, alloc); 3016 3017 /* Copy the root into a real block. */ 3018 error = xfs_btree_get_buf_block(cur, &nptr, 0, &cblock, &cbp); 3019 if (error) 3020 goto error0; 3021 3022 /* 3023 * we can't just memcpy() the root in for CRC enabled btree blocks. 3024 * In that case have to also ensure the blkno remains correct 3025 */ 3026 memcpy(cblock, block, xfs_btree_block_len(cur)); 3027 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { 3028 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 3029 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn); 3030 else 3031 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn); 3032 } 3033 3034 be16_add_cpu(&block->bb_level, 1); 3035 xfs_btree_set_numrecs(block, 1); 3036 cur->bc_nlevels++; 3037 cur->bc_ptrs[level + 1] = 1; 3038 3039 kp = xfs_btree_key_addr(cur, 1, block); 3040 ckp = xfs_btree_key_addr(cur, 1, cblock); 3041 xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock)); 3042 3043 cpp = xfs_btree_ptr_addr(cur, 1, cblock); 3044 #ifdef DEBUG 3045 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { 3046 error = xfs_btree_check_ptr(cur, pp, i, level); 3047 if (error) 3048 goto error0; 3049 } 3050 #endif 3051 xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock)); 3052 3053 #ifdef DEBUG 3054 error = xfs_btree_check_ptr(cur, &nptr, 0, level); 3055 if (error) 3056 goto error0; 3057 #endif 3058 xfs_btree_copy_ptrs(cur, pp, &nptr, 1); 3059 3060 xfs_iroot_realloc(cur->bc_private.b.ip, 3061 1 - xfs_btree_get_numrecs(cblock), 3062 cur->bc_private.b.whichfork); 3063 3064 xfs_btree_setbuf(cur, level, cbp); 3065 3066 /* 3067 * Do all this logging at the end so that 3068 * the root is at the right level. 3069 */ 3070 xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS); 3071 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); 3072 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); 3073 3074 *logflags |= 3075 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork); 3076 *stat = 1; 3077 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3078 return 0; 3079 error0: 3080 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3081 return error; 3082 } 3083 3084 /* 3085 * Allocate a new root block, fill it in. 3086 */ 3087 STATIC int /* error */ 3088 xfs_btree_new_root( 3089 struct xfs_btree_cur *cur, /* btree cursor */ 3090 int *stat) /* success/failure */ 3091 { 3092 struct xfs_btree_block *block; /* one half of the old root block */ 3093 struct xfs_buf *bp; /* buffer containing block */ 3094 int error; /* error return value */ 3095 struct xfs_buf *lbp; /* left buffer pointer */ 3096 struct xfs_btree_block *left; /* left btree block */ 3097 struct xfs_buf *nbp; /* new (root) buffer */ 3098 struct xfs_btree_block *new; /* new (root) btree block */ 3099 int nptr; /* new value for key index, 1 or 2 */ 3100 struct xfs_buf *rbp; /* right buffer pointer */ 3101 struct xfs_btree_block *right; /* right btree block */ 3102 union xfs_btree_ptr rptr; 3103 union xfs_btree_ptr lptr; 3104 3105 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3106 XFS_BTREE_STATS_INC(cur, newroot); 3107 3108 /* initialise our start point from the cursor */ 3109 cur->bc_ops->init_ptr_from_cur(cur, &rptr); 3110 3111 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 3112 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); 3113 if (error) 3114 goto error0; 3115 if (*stat == 0) 3116 goto out0; 3117 XFS_BTREE_STATS_INC(cur, alloc); 3118 3119 /* Set up the new block. */ 3120 error = xfs_btree_get_buf_block(cur, &lptr, 0, &new, &nbp); 3121 if (error) 3122 goto error0; 3123 3124 /* Set the root in the holding structure increasing the level by 1. */ 3125 cur->bc_ops->set_root(cur, &lptr, 1); 3126 3127 /* 3128 * At the previous root level there are now two blocks: the old root, 3129 * and the new block generated when it was split. We don't know which 3130 * one the cursor is pointing at, so we set up variables "left" and 3131 * "right" for each case. 3132 */ 3133 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); 3134 3135 #ifdef DEBUG 3136 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); 3137 if (error) 3138 goto error0; 3139 #endif 3140 3141 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 3142 if (!xfs_btree_ptr_is_null(cur, &rptr)) { 3143 /* Our block is left, pick up the right block. */ 3144 lbp = bp; 3145 xfs_btree_buf_to_ptr(cur, lbp, &lptr); 3146 left = block; 3147 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 3148 if (error) 3149 goto error0; 3150 bp = rbp; 3151 nptr = 1; 3152 } else { 3153 /* Our block is right, pick up the left block. */ 3154 rbp = bp; 3155 xfs_btree_buf_to_ptr(cur, rbp, &rptr); 3156 right = block; 3157 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 3158 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 3159 if (error) 3160 goto error0; 3161 bp = lbp; 3162 nptr = 2; 3163 } 3164 3165 /* Fill in the new block's btree header and log it. */ 3166 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); 3167 xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS); 3168 ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) && 3169 !xfs_btree_ptr_is_null(cur, &rptr)); 3170 3171 /* Fill in the key data in the new root. */ 3172 if (xfs_btree_get_level(left) > 0) { 3173 /* 3174 * Get the keys for the left block's keys and put them directly 3175 * in the parent block. Do the same for the right block. 3176 */ 3177 xfs_btree_get_node_keys(cur, left, 3178 xfs_btree_key_addr(cur, 1, new)); 3179 xfs_btree_get_node_keys(cur, right, 3180 xfs_btree_key_addr(cur, 2, new)); 3181 } else { 3182 /* 3183 * Get the keys for the left block's records and put them 3184 * directly in the parent block. Do the same for the right 3185 * block. 3186 */ 3187 xfs_btree_get_leaf_keys(cur, left, 3188 xfs_btree_key_addr(cur, 1, new)); 3189 xfs_btree_get_leaf_keys(cur, right, 3190 xfs_btree_key_addr(cur, 2, new)); 3191 } 3192 xfs_btree_log_keys(cur, nbp, 1, 2); 3193 3194 /* Fill in the pointer data in the new root. */ 3195 xfs_btree_copy_ptrs(cur, 3196 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1); 3197 xfs_btree_copy_ptrs(cur, 3198 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1); 3199 xfs_btree_log_ptrs(cur, nbp, 1, 2); 3200 3201 /* Fix up the cursor. */ 3202 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); 3203 cur->bc_ptrs[cur->bc_nlevels] = nptr; 3204 cur->bc_nlevels++; 3205 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3206 *stat = 1; 3207 return 0; 3208 error0: 3209 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3210 return error; 3211 out0: 3212 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3213 *stat = 0; 3214 return 0; 3215 } 3216 3217 STATIC int 3218 xfs_btree_make_block_unfull( 3219 struct xfs_btree_cur *cur, /* btree cursor */ 3220 int level, /* btree level */ 3221 int numrecs,/* # of recs in block */ 3222 int *oindex,/* old tree index */ 3223 int *index, /* new tree index */ 3224 union xfs_btree_ptr *nptr, /* new btree ptr */ 3225 struct xfs_btree_cur **ncur, /* new btree cursor */ 3226 union xfs_btree_key *key, /* key of new block */ 3227 int *stat) 3228 { 3229 int error = 0; 3230 3231 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 3232 level == cur->bc_nlevels - 1) { 3233 struct xfs_inode *ip = cur->bc_private.b.ip; 3234 3235 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { 3236 /* A root block that can be made bigger. */ 3237 xfs_iroot_realloc(ip, 1, cur->bc_private.b.whichfork); 3238 *stat = 1; 3239 } else { 3240 /* A root block that needs replacing */ 3241 int logflags = 0; 3242 3243 error = xfs_btree_new_iroot(cur, &logflags, stat); 3244 if (error || *stat == 0) 3245 return error; 3246 3247 xfs_trans_log_inode(cur->bc_tp, ip, logflags); 3248 } 3249 3250 return 0; 3251 } 3252 3253 /* First, try shifting an entry to the right neighbor. */ 3254 error = xfs_btree_rshift(cur, level, stat); 3255 if (error || *stat) 3256 return error; 3257 3258 /* Next, try shifting an entry to the left neighbor. */ 3259 error = xfs_btree_lshift(cur, level, stat); 3260 if (error) 3261 return error; 3262 3263 if (*stat) { 3264 *oindex = *index = cur->bc_ptrs[level]; 3265 return 0; 3266 } 3267 3268 /* 3269 * Next, try splitting the current block in half. 3270 * 3271 * If this works we have to re-set our variables because we 3272 * could be in a different block now. 3273 */ 3274 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); 3275 if (error || *stat == 0) 3276 return error; 3277 3278 3279 *index = cur->bc_ptrs[level]; 3280 return 0; 3281 } 3282 3283 /* 3284 * Insert one record/level. Return information to the caller 3285 * allowing the next level up to proceed if necessary. 3286 */ 3287 STATIC int 3288 xfs_btree_insrec( 3289 struct xfs_btree_cur *cur, /* btree cursor */ 3290 int level, /* level to insert record at */ 3291 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ 3292 union xfs_btree_rec *rec, /* record to insert */ 3293 union xfs_btree_key *key, /* i/o: block key for ptrp */ 3294 struct xfs_btree_cur **curp, /* output: new cursor replacing cur */ 3295 int *stat) /* success/failure */ 3296 { 3297 struct xfs_btree_block *block; /* btree block */ 3298 struct xfs_buf *bp; /* buffer for block */ 3299 union xfs_btree_ptr nptr; /* new block ptr */ 3300 struct xfs_btree_cur *ncur; /* new btree cursor */ 3301 union xfs_btree_key nkey; /* new block key */ 3302 union xfs_btree_key *lkey; 3303 int optr; /* old key/record index */ 3304 int ptr; /* key/record index */ 3305 int numrecs;/* number of records */ 3306 int error; /* error return value */ 3307 #ifdef DEBUG 3308 int i; 3309 #endif 3310 xfs_daddr_t old_bn; 3311 3312 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3313 XFS_BTREE_TRACE_ARGIPR(cur, level, *ptrp, &rec); 3314 3315 ncur = NULL; 3316 lkey = &nkey; 3317 3318 /* 3319 * If we have an external root pointer, and we've made it to the 3320 * root level, allocate a new root block and we're done. 3321 */ 3322 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 3323 (level >= cur->bc_nlevels)) { 3324 error = xfs_btree_new_root(cur, stat); 3325 xfs_btree_set_ptr_null(cur, ptrp); 3326 3327 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3328 return error; 3329 } 3330 3331 /* If we're off the left edge, return failure. */ 3332 ptr = cur->bc_ptrs[level]; 3333 if (ptr == 0) { 3334 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3335 *stat = 0; 3336 return 0; 3337 } 3338 3339 optr = ptr; 3340 3341 XFS_BTREE_STATS_INC(cur, insrec); 3342 3343 /* Get pointers to the btree buffer and block. */ 3344 block = xfs_btree_get_block(cur, level, &bp); 3345 old_bn = bp ? bp->b_bn : XFS_BUF_DADDR_NULL; 3346 numrecs = xfs_btree_get_numrecs(block); 3347 3348 #ifdef DEBUG 3349 error = xfs_btree_check_block(cur, block, level, bp); 3350 if (error) 3351 goto error0; 3352 3353 /* Check that the new entry is being inserted in the right place. */ 3354 if (ptr <= numrecs) { 3355 if (level == 0) { 3356 ASSERT(cur->bc_ops->recs_inorder(cur, rec, 3357 xfs_btree_rec_addr(cur, ptr, block))); 3358 } else { 3359 ASSERT(cur->bc_ops->keys_inorder(cur, key, 3360 xfs_btree_key_addr(cur, ptr, block))); 3361 } 3362 } 3363 #endif 3364 3365 /* 3366 * If the block is full, we can't insert the new entry until we 3367 * make the block un-full. 3368 */ 3369 xfs_btree_set_ptr_null(cur, &nptr); 3370 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { 3371 error = xfs_btree_make_block_unfull(cur, level, numrecs, 3372 &optr, &ptr, &nptr, &ncur, lkey, stat); 3373 if (error || *stat == 0) 3374 goto error0; 3375 } 3376 3377 /* 3378 * The current block may have changed if the block was 3379 * previously full and we have just made space in it. 3380 */ 3381 block = xfs_btree_get_block(cur, level, &bp); 3382 numrecs = xfs_btree_get_numrecs(block); 3383 3384 #ifdef DEBUG 3385 error = xfs_btree_check_block(cur, block, level, bp); 3386 if (error) 3387 return error; 3388 #endif 3389 3390 /* 3391 * At this point we know there's room for our new entry in the block 3392 * we're pointing at. 3393 */ 3394 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); 3395 3396 if (level > 0) { 3397 /* It's a nonleaf. make a hole in the keys and ptrs */ 3398 union xfs_btree_key *kp; 3399 union xfs_btree_ptr *pp; 3400 3401 kp = xfs_btree_key_addr(cur, ptr, block); 3402 pp = xfs_btree_ptr_addr(cur, ptr, block); 3403 3404 #ifdef DEBUG 3405 for (i = numrecs - ptr; i >= 0; i--) { 3406 error = xfs_btree_check_ptr(cur, pp, i, level); 3407 if (error) 3408 return error; 3409 } 3410 #endif 3411 3412 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); 3413 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); 3414 3415 #ifdef DEBUG 3416 error = xfs_btree_check_ptr(cur, ptrp, 0, level); 3417 if (error) 3418 goto error0; 3419 #endif 3420 3421 /* Now put the new data in, bump numrecs and log it. */ 3422 xfs_btree_copy_keys(cur, kp, key, 1); 3423 xfs_btree_copy_ptrs(cur, pp, ptrp, 1); 3424 numrecs++; 3425 xfs_btree_set_numrecs(block, numrecs); 3426 xfs_btree_log_ptrs(cur, bp, ptr, numrecs); 3427 xfs_btree_log_keys(cur, bp, ptr, numrecs); 3428 #ifdef DEBUG 3429 if (ptr < numrecs) { 3430 ASSERT(cur->bc_ops->keys_inorder(cur, kp, 3431 xfs_btree_key_addr(cur, ptr + 1, block))); 3432 } 3433 #endif 3434 } else { 3435 /* It's a leaf. make a hole in the records */ 3436 union xfs_btree_rec *rp; 3437 3438 rp = xfs_btree_rec_addr(cur, ptr, block); 3439 3440 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); 3441 3442 /* Now put the new data in, bump numrecs and log it. */ 3443 xfs_btree_copy_recs(cur, rp, rec, 1); 3444 xfs_btree_set_numrecs(block, ++numrecs); 3445 xfs_btree_log_recs(cur, bp, ptr, numrecs); 3446 #ifdef DEBUG 3447 if (ptr < numrecs) { 3448 ASSERT(cur->bc_ops->recs_inorder(cur, rp, 3449 xfs_btree_rec_addr(cur, ptr + 1, block))); 3450 } 3451 #endif 3452 } 3453 3454 /* Log the new number of records in the btree header. */ 3455 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS); 3456 3457 /* 3458 * If we just inserted into a new tree block, we have to 3459 * recalculate nkey here because nkey is out of date. 3460 * 3461 * Otherwise we're just updating an existing block (having shoved 3462 * some records into the new tree block), so use the regular key 3463 * update mechanism. 3464 */ 3465 if (bp && bp->b_bn != old_bn) { 3466 xfs_btree_get_keys(cur, block, lkey); 3467 } else if (xfs_btree_needs_key_update(cur, optr)) { 3468 error = xfs_btree_update_keys(cur, level); 3469 if (error) 3470 goto error0; 3471 } 3472 3473 /* 3474 * If we are tracking the last record in the tree and 3475 * we are at the far right edge of the tree, update it. 3476 */ 3477 if (xfs_btree_is_lastrec(cur, block, level)) { 3478 cur->bc_ops->update_lastrec(cur, block, rec, 3479 ptr, LASTREC_INSREC); 3480 } 3481 3482 /* 3483 * Return the new block number, if any. 3484 * If there is one, give back a record value and a cursor too. 3485 */ 3486 *ptrp = nptr; 3487 if (!xfs_btree_ptr_is_null(cur, &nptr)) { 3488 xfs_btree_copy_keys(cur, key, lkey, 1); 3489 *curp = ncur; 3490 } 3491 3492 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3493 *stat = 1; 3494 return 0; 3495 3496 error0: 3497 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3498 return error; 3499 } 3500 3501 /* 3502 * Insert the record at the point referenced by cur. 3503 * 3504 * A multi-level split of the tree on insert will invalidate the original 3505 * cursor. All callers of this function should assume that the cursor is 3506 * no longer valid and revalidate it. 3507 */ 3508 int 3509 xfs_btree_insert( 3510 struct xfs_btree_cur *cur, 3511 int *stat) 3512 { 3513 int error; /* error return value */ 3514 int i; /* result value, 0 for failure */ 3515 int level; /* current level number in btree */ 3516 union xfs_btree_ptr nptr; /* new block number (split result) */ 3517 struct xfs_btree_cur *ncur; /* new cursor (split result) */ 3518 struct xfs_btree_cur *pcur; /* previous level's cursor */ 3519 union xfs_btree_key bkey; /* key of block to insert */ 3520 union xfs_btree_key *key; 3521 union xfs_btree_rec rec; /* record to insert */ 3522 3523 level = 0; 3524 ncur = NULL; 3525 pcur = cur; 3526 key = &bkey; 3527 3528 xfs_btree_set_ptr_null(cur, &nptr); 3529 3530 /* Make a key out of the record data to be inserted, and save it. */ 3531 cur->bc_ops->init_rec_from_cur(cur, &rec); 3532 cur->bc_ops->init_key_from_rec(key, &rec); 3533 3534 /* 3535 * Loop going up the tree, starting at the leaf level. 3536 * Stop when we don't get a split block, that must mean that 3537 * the insert is finished with this level. 3538 */ 3539 do { 3540 /* 3541 * Insert nrec/nptr into this level of the tree. 3542 * Note if we fail, nptr will be null. 3543 */ 3544 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, 3545 &ncur, &i); 3546 if (error) { 3547 if (pcur != cur) 3548 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR); 3549 goto error0; 3550 } 3551 3552 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3553 level++; 3554 3555 /* 3556 * See if the cursor we just used is trash. 3557 * Can't trash the caller's cursor, but otherwise we should 3558 * if ncur is a new cursor or we're about to be done. 3559 */ 3560 if (pcur != cur && 3561 (ncur || xfs_btree_ptr_is_null(cur, &nptr))) { 3562 /* Save the state from the cursor before we trash it */ 3563 if (cur->bc_ops->update_cursor) 3564 cur->bc_ops->update_cursor(pcur, cur); 3565 cur->bc_nlevels = pcur->bc_nlevels; 3566 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR); 3567 } 3568 /* If we got a new cursor, switch to it. */ 3569 if (ncur) { 3570 pcur = ncur; 3571 ncur = NULL; 3572 } 3573 } while (!xfs_btree_ptr_is_null(cur, &nptr)); 3574 3575 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3576 *stat = i; 3577 return 0; 3578 error0: 3579 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3580 return error; 3581 } 3582 3583 /* 3584 * Try to merge a non-leaf block back into the inode root. 3585 * 3586 * Note: the killroot names comes from the fact that we're effectively 3587 * killing the old root block. But because we can't just delete the 3588 * inode we have to copy the single block it was pointing to into the 3589 * inode. 3590 */ 3591 STATIC int 3592 xfs_btree_kill_iroot( 3593 struct xfs_btree_cur *cur) 3594 { 3595 int whichfork = cur->bc_private.b.whichfork; 3596 struct xfs_inode *ip = cur->bc_private.b.ip; 3597 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork); 3598 struct xfs_btree_block *block; 3599 struct xfs_btree_block *cblock; 3600 union xfs_btree_key *kp; 3601 union xfs_btree_key *ckp; 3602 union xfs_btree_ptr *pp; 3603 union xfs_btree_ptr *cpp; 3604 struct xfs_buf *cbp; 3605 int level; 3606 int index; 3607 int numrecs; 3608 int error; 3609 #ifdef DEBUG 3610 union xfs_btree_ptr ptr; 3611 int i; 3612 #endif 3613 3614 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3615 3616 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 3617 ASSERT(cur->bc_nlevels > 1); 3618 3619 /* 3620 * Don't deal with the root block needs to be a leaf case. 3621 * We're just going to turn the thing back into extents anyway. 3622 */ 3623 level = cur->bc_nlevels - 1; 3624 if (level == 1) 3625 goto out0; 3626 3627 /* 3628 * Give up if the root has multiple children. 3629 */ 3630 block = xfs_btree_get_iroot(cur); 3631 if (xfs_btree_get_numrecs(block) != 1) 3632 goto out0; 3633 3634 cblock = xfs_btree_get_block(cur, level - 1, &cbp); 3635 numrecs = xfs_btree_get_numrecs(cblock); 3636 3637 /* 3638 * Only do this if the next level will fit. 3639 * Then the data must be copied up to the inode, 3640 * instead of freeing the root you free the next level. 3641 */ 3642 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) 3643 goto out0; 3644 3645 XFS_BTREE_STATS_INC(cur, killroot); 3646 3647 #ifdef DEBUG 3648 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); 3649 ASSERT(xfs_btree_ptr_is_null(cur, &ptr)); 3650 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 3651 ASSERT(xfs_btree_ptr_is_null(cur, &ptr)); 3652 #endif 3653 3654 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); 3655 if (index) { 3656 xfs_iroot_realloc(cur->bc_private.b.ip, index, 3657 cur->bc_private.b.whichfork); 3658 block = ifp->if_broot; 3659 } 3660 3661 be16_add_cpu(&block->bb_numrecs, index); 3662 ASSERT(block->bb_numrecs == cblock->bb_numrecs); 3663 3664 kp = xfs_btree_key_addr(cur, 1, block); 3665 ckp = xfs_btree_key_addr(cur, 1, cblock); 3666 xfs_btree_copy_keys(cur, kp, ckp, numrecs); 3667 3668 pp = xfs_btree_ptr_addr(cur, 1, block); 3669 cpp = xfs_btree_ptr_addr(cur, 1, cblock); 3670 #ifdef DEBUG 3671 for (i = 0; i < numrecs; i++) { 3672 error = xfs_btree_check_ptr(cur, cpp, i, level - 1); 3673 if (error) { 3674 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3675 return error; 3676 } 3677 } 3678 #endif 3679 xfs_btree_copy_ptrs(cur, pp, cpp, numrecs); 3680 3681 error = xfs_btree_free_block(cur, cbp); 3682 if (error) { 3683 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3684 return error; 3685 } 3686 3687 cur->bc_bufs[level - 1] = NULL; 3688 be16_add_cpu(&block->bb_level, -1); 3689 xfs_trans_log_inode(cur->bc_tp, ip, 3690 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork)); 3691 cur->bc_nlevels--; 3692 out0: 3693 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3694 return 0; 3695 } 3696 3697 /* 3698 * Kill the current root node, and replace it with it's only child node. 3699 */ 3700 STATIC int 3701 xfs_btree_kill_root( 3702 struct xfs_btree_cur *cur, 3703 struct xfs_buf *bp, 3704 int level, 3705 union xfs_btree_ptr *newroot) 3706 { 3707 int error; 3708 3709 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3710 XFS_BTREE_STATS_INC(cur, killroot); 3711 3712 /* 3713 * Update the root pointer, decreasing the level by 1 and then 3714 * free the old root. 3715 */ 3716 cur->bc_ops->set_root(cur, newroot, -1); 3717 3718 error = xfs_btree_free_block(cur, bp); 3719 if (error) { 3720 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3721 return error; 3722 } 3723 3724 cur->bc_bufs[level] = NULL; 3725 cur->bc_ra[level] = 0; 3726 cur->bc_nlevels--; 3727 3728 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3729 return 0; 3730 } 3731 3732 STATIC int 3733 xfs_btree_dec_cursor( 3734 struct xfs_btree_cur *cur, 3735 int level, 3736 int *stat) 3737 { 3738 int error; 3739 int i; 3740 3741 if (level > 0) { 3742 error = xfs_btree_decrement(cur, level, &i); 3743 if (error) 3744 return error; 3745 } 3746 3747 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3748 *stat = 1; 3749 return 0; 3750 } 3751 3752 /* 3753 * Single level of the btree record deletion routine. 3754 * Delete record pointed to by cur/level. 3755 * Remove the record from its block then rebalance the tree. 3756 * Return 0 for error, 1 for done, 2 to go on to the next level. 3757 */ 3758 STATIC int /* error */ 3759 xfs_btree_delrec( 3760 struct xfs_btree_cur *cur, /* btree cursor */ 3761 int level, /* level removing record from */ 3762 int *stat) /* fail/done/go-on */ 3763 { 3764 struct xfs_btree_block *block; /* btree block */ 3765 union xfs_btree_ptr cptr; /* current block ptr */ 3766 struct xfs_buf *bp; /* buffer for block */ 3767 int error; /* error return value */ 3768 int i; /* loop counter */ 3769 union xfs_btree_ptr lptr; /* left sibling block ptr */ 3770 struct xfs_buf *lbp; /* left buffer pointer */ 3771 struct xfs_btree_block *left; /* left btree block */ 3772 int lrecs = 0; /* left record count */ 3773 int ptr; /* key/record index */ 3774 union xfs_btree_ptr rptr; /* right sibling block ptr */ 3775 struct xfs_buf *rbp; /* right buffer pointer */ 3776 struct xfs_btree_block *right; /* right btree block */ 3777 struct xfs_btree_block *rrblock; /* right-right btree block */ 3778 struct xfs_buf *rrbp; /* right-right buffer pointer */ 3779 int rrecs = 0; /* right record count */ 3780 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 3781 int numrecs; /* temporary numrec count */ 3782 3783 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3784 XFS_BTREE_TRACE_ARGI(cur, level); 3785 3786 tcur = NULL; 3787 3788 /* Get the index of the entry being deleted, check for nothing there. */ 3789 ptr = cur->bc_ptrs[level]; 3790 if (ptr == 0) { 3791 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3792 *stat = 0; 3793 return 0; 3794 } 3795 3796 /* Get the buffer & block containing the record or key/ptr. */ 3797 block = xfs_btree_get_block(cur, level, &bp); 3798 numrecs = xfs_btree_get_numrecs(block); 3799 3800 #ifdef DEBUG 3801 error = xfs_btree_check_block(cur, block, level, bp); 3802 if (error) 3803 goto error0; 3804 #endif 3805 3806 /* Fail if we're off the end of the block. */ 3807 if (ptr > numrecs) { 3808 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3809 *stat = 0; 3810 return 0; 3811 } 3812 3813 XFS_BTREE_STATS_INC(cur, delrec); 3814 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); 3815 3816 /* Excise the entries being deleted. */ 3817 if (level > 0) { 3818 /* It's a nonleaf. operate on keys and ptrs */ 3819 union xfs_btree_key *lkp; 3820 union xfs_btree_ptr *lpp; 3821 3822 lkp = xfs_btree_key_addr(cur, ptr + 1, block); 3823 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); 3824 3825 #ifdef DEBUG 3826 for (i = 0; i < numrecs - ptr; i++) { 3827 error = xfs_btree_check_ptr(cur, lpp, i, level); 3828 if (error) 3829 goto error0; 3830 } 3831 #endif 3832 3833 if (ptr < numrecs) { 3834 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); 3835 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); 3836 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); 3837 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); 3838 } 3839 } else { 3840 /* It's a leaf. operate on records */ 3841 if (ptr < numrecs) { 3842 xfs_btree_shift_recs(cur, 3843 xfs_btree_rec_addr(cur, ptr + 1, block), 3844 -1, numrecs - ptr); 3845 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); 3846 } 3847 } 3848 3849 /* 3850 * Decrement and log the number of entries in the block. 3851 */ 3852 xfs_btree_set_numrecs(block, --numrecs); 3853 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS); 3854 3855 /* 3856 * If we are tracking the last record in the tree and 3857 * we are at the far right edge of the tree, update it. 3858 */ 3859 if (xfs_btree_is_lastrec(cur, block, level)) { 3860 cur->bc_ops->update_lastrec(cur, block, NULL, 3861 ptr, LASTREC_DELREC); 3862 } 3863 3864 /* 3865 * We're at the root level. First, shrink the root block in-memory. 3866 * Try to get rid of the next level down. If we can't then there's 3867 * nothing left to do. 3868 */ 3869 if (level == cur->bc_nlevels - 1) { 3870 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { 3871 xfs_iroot_realloc(cur->bc_private.b.ip, -1, 3872 cur->bc_private.b.whichfork); 3873 3874 error = xfs_btree_kill_iroot(cur); 3875 if (error) 3876 goto error0; 3877 3878 error = xfs_btree_dec_cursor(cur, level, stat); 3879 if (error) 3880 goto error0; 3881 *stat = 1; 3882 return 0; 3883 } 3884 3885 /* 3886 * If this is the root level, and there's only one entry left, 3887 * and it's NOT the leaf level, then we can get rid of this 3888 * level. 3889 */ 3890 if (numrecs == 1 && level > 0) { 3891 union xfs_btree_ptr *pp; 3892 /* 3893 * pp is still set to the first pointer in the block. 3894 * Make it the new root of the btree. 3895 */ 3896 pp = xfs_btree_ptr_addr(cur, 1, block); 3897 error = xfs_btree_kill_root(cur, bp, level, pp); 3898 if (error) 3899 goto error0; 3900 } else if (level > 0) { 3901 error = xfs_btree_dec_cursor(cur, level, stat); 3902 if (error) 3903 goto error0; 3904 } 3905 *stat = 1; 3906 return 0; 3907 } 3908 3909 /* 3910 * If we deleted the leftmost entry in the block, update the 3911 * key values above us in the tree. 3912 */ 3913 if (xfs_btree_needs_key_update(cur, ptr)) { 3914 error = xfs_btree_update_keys(cur, level); 3915 if (error) 3916 goto error0; 3917 } 3918 3919 /* 3920 * If the number of records remaining in the block is at least 3921 * the minimum, we're done. 3922 */ 3923 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { 3924 error = xfs_btree_dec_cursor(cur, level, stat); 3925 if (error) 3926 goto error0; 3927 return 0; 3928 } 3929 3930 /* 3931 * Otherwise, we have to move some records around to keep the 3932 * tree balanced. Look at the left and right sibling blocks to 3933 * see if we can re-balance by moving only one record. 3934 */ 3935 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 3936 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); 3937 3938 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { 3939 /* 3940 * One child of root, need to get a chance to copy its contents 3941 * into the root and delete it. Can't go up to next level, 3942 * there's nothing to delete there. 3943 */ 3944 if (xfs_btree_ptr_is_null(cur, &rptr) && 3945 xfs_btree_ptr_is_null(cur, &lptr) && 3946 level == cur->bc_nlevels - 2) { 3947 error = xfs_btree_kill_iroot(cur); 3948 if (!error) 3949 error = xfs_btree_dec_cursor(cur, level, stat); 3950 if (error) 3951 goto error0; 3952 return 0; 3953 } 3954 } 3955 3956 ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) || 3957 !xfs_btree_ptr_is_null(cur, &lptr)); 3958 3959 /* 3960 * Duplicate the cursor so our btree manipulations here won't 3961 * disrupt the next level up. 3962 */ 3963 error = xfs_btree_dup_cursor(cur, &tcur); 3964 if (error) 3965 goto error0; 3966 3967 /* 3968 * If there's a right sibling, see if it's ok to shift an entry 3969 * out of it. 3970 */ 3971 if (!xfs_btree_ptr_is_null(cur, &rptr)) { 3972 /* 3973 * Move the temp cursor to the last entry in the next block. 3974 * Actually any entry but the first would suffice. 3975 */ 3976 i = xfs_btree_lastrec(tcur, level); 3977 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3978 3979 error = xfs_btree_increment(tcur, level, &i); 3980 if (error) 3981 goto error0; 3982 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3983 3984 i = xfs_btree_lastrec(tcur, level); 3985 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3986 3987 /* Grab a pointer to the block. */ 3988 right = xfs_btree_get_block(tcur, level, &rbp); 3989 #ifdef DEBUG 3990 error = xfs_btree_check_block(tcur, right, level, rbp); 3991 if (error) 3992 goto error0; 3993 #endif 3994 /* Grab the current block number, for future use. */ 3995 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB); 3996 3997 /* 3998 * If right block is full enough so that removing one entry 3999 * won't make it too empty, and left-shifting an entry out 4000 * of right to us works, we're done. 4001 */ 4002 if (xfs_btree_get_numrecs(right) - 1 >= 4003 cur->bc_ops->get_minrecs(tcur, level)) { 4004 error = xfs_btree_lshift(tcur, level, &i); 4005 if (error) 4006 goto error0; 4007 if (i) { 4008 ASSERT(xfs_btree_get_numrecs(block) >= 4009 cur->bc_ops->get_minrecs(tcur, level)); 4010 4011 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 4012 tcur = NULL; 4013 4014 error = xfs_btree_dec_cursor(cur, level, stat); 4015 if (error) 4016 goto error0; 4017 return 0; 4018 } 4019 } 4020 4021 /* 4022 * Otherwise, grab the number of records in right for 4023 * future reference, and fix up the temp cursor to point 4024 * to our block again (last record). 4025 */ 4026 rrecs = xfs_btree_get_numrecs(right); 4027 if (!xfs_btree_ptr_is_null(cur, &lptr)) { 4028 i = xfs_btree_firstrec(tcur, level); 4029 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 4030 4031 error = xfs_btree_decrement(tcur, level, &i); 4032 if (error) 4033 goto error0; 4034 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 4035 } 4036 } 4037 4038 /* 4039 * If there's a left sibling, see if it's ok to shift an entry 4040 * out of it. 4041 */ 4042 if (!xfs_btree_ptr_is_null(cur, &lptr)) { 4043 /* 4044 * Move the temp cursor to the first entry in the 4045 * previous block. 4046 */ 4047 i = xfs_btree_firstrec(tcur, level); 4048 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 4049 4050 error = xfs_btree_decrement(tcur, level, &i); 4051 if (error) 4052 goto error0; 4053 i = xfs_btree_firstrec(tcur, level); 4054 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 4055 4056 /* Grab a pointer to the block. */ 4057 left = xfs_btree_get_block(tcur, level, &lbp); 4058 #ifdef DEBUG 4059 error = xfs_btree_check_block(cur, left, level, lbp); 4060 if (error) 4061 goto error0; 4062 #endif 4063 /* Grab the current block number, for future use. */ 4064 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB); 4065 4066 /* 4067 * If left block is full enough so that removing one entry 4068 * won't make it too empty, and right-shifting an entry out 4069 * of left to us works, we're done. 4070 */ 4071 if (xfs_btree_get_numrecs(left) - 1 >= 4072 cur->bc_ops->get_minrecs(tcur, level)) { 4073 error = xfs_btree_rshift(tcur, level, &i); 4074 if (error) 4075 goto error0; 4076 if (i) { 4077 ASSERT(xfs_btree_get_numrecs(block) >= 4078 cur->bc_ops->get_minrecs(tcur, level)); 4079 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 4080 tcur = NULL; 4081 if (level == 0) 4082 cur->bc_ptrs[0]++; 4083 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4084 *stat = 1; 4085 return 0; 4086 } 4087 } 4088 4089 /* 4090 * Otherwise, grab the number of records in right for 4091 * future reference. 4092 */ 4093 lrecs = xfs_btree_get_numrecs(left); 4094 } 4095 4096 /* Delete the temp cursor, we're done with it. */ 4097 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 4098 tcur = NULL; 4099 4100 /* If here, we need to do a join to keep the tree balanced. */ 4101 ASSERT(!xfs_btree_ptr_is_null(cur, &cptr)); 4102 4103 if (!xfs_btree_ptr_is_null(cur, &lptr) && 4104 lrecs + xfs_btree_get_numrecs(block) <= 4105 cur->bc_ops->get_maxrecs(cur, level)) { 4106 /* 4107 * Set "right" to be the starting block, 4108 * "left" to be the left neighbor. 4109 */ 4110 rptr = cptr; 4111 right = block; 4112 rbp = bp; 4113 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 4114 if (error) 4115 goto error0; 4116 4117 /* 4118 * If that won't work, see if we can join with the right neighbor block. 4119 */ 4120 } else if (!xfs_btree_ptr_is_null(cur, &rptr) && 4121 rrecs + xfs_btree_get_numrecs(block) <= 4122 cur->bc_ops->get_maxrecs(cur, level)) { 4123 /* 4124 * Set "left" to be the starting block, 4125 * "right" to be the right neighbor. 4126 */ 4127 lptr = cptr; 4128 left = block; 4129 lbp = bp; 4130 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 4131 if (error) 4132 goto error0; 4133 4134 /* 4135 * Otherwise, we can't fix the imbalance. 4136 * Just return. This is probably a logic error, but it's not fatal. 4137 */ 4138 } else { 4139 error = xfs_btree_dec_cursor(cur, level, stat); 4140 if (error) 4141 goto error0; 4142 return 0; 4143 } 4144 4145 rrecs = xfs_btree_get_numrecs(right); 4146 lrecs = xfs_btree_get_numrecs(left); 4147 4148 /* 4149 * We're now going to join "left" and "right" by moving all the stuff 4150 * in "right" to "left" and deleting "right". 4151 */ 4152 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 4153 if (level > 0) { 4154 /* It's a non-leaf. Move keys and pointers. */ 4155 union xfs_btree_key *lkp; /* left btree key */ 4156 union xfs_btree_ptr *lpp; /* left address pointer */ 4157 union xfs_btree_key *rkp; /* right btree key */ 4158 union xfs_btree_ptr *rpp; /* right address pointer */ 4159 4160 lkp = xfs_btree_key_addr(cur, lrecs + 1, left); 4161 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left); 4162 rkp = xfs_btree_key_addr(cur, 1, right); 4163 rpp = xfs_btree_ptr_addr(cur, 1, right); 4164 #ifdef DEBUG 4165 for (i = 1; i < rrecs; i++) { 4166 error = xfs_btree_check_ptr(cur, rpp, i, level); 4167 if (error) 4168 goto error0; 4169 } 4170 #endif 4171 xfs_btree_copy_keys(cur, lkp, rkp, rrecs); 4172 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs); 4173 4174 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs); 4175 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs); 4176 } else { 4177 /* It's a leaf. Move records. */ 4178 union xfs_btree_rec *lrp; /* left record pointer */ 4179 union xfs_btree_rec *rrp; /* right record pointer */ 4180 4181 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left); 4182 rrp = xfs_btree_rec_addr(cur, 1, right); 4183 4184 xfs_btree_copy_recs(cur, lrp, rrp, rrecs); 4185 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs); 4186 } 4187 4188 XFS_BTREE_STATS_INC(cur, join); 4189 4190 /* 4191 * Fix up the number of records and right block pointer in the 4192 * surviving block, and log it. 4193 */ 4194 xfs_btree_set_numrecs(left, lrecs + rrecs); 4195 xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB), 4196 xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB); 4197 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 4198 4199 /* If there is a right sibling, point it to the remaining block. */ 4200 xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB); 4201 if (!xfs_btree_ptr_is_null(cur, &cptr)) { 4202 error = xfs_btree_read_buf_block(cur, &cptr, 0, &rrblock, &rrbp); 4203 if (error) 4204 goto error0; 4205 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB); 4206 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB); 4207 } 4208 4209 /* Free the deleted block. */ 4210 error = xfs_btree_free_block(cur, rbp); 4211 if (error) 4212 goto error0; 4213 4214 /* 4215 * If we joined with the left neighbor, set the buffer in the 4216 * cursor to the left block, and fix up the index. 4217 */ 4218 if (bp != lbp) { 4219 cur->bc_bufs[level] = lbp; 4220 cur->bc_ptrs[level] += lrecs; 4221 cur->bc_ra[level] = 0; 4222 } 4223 /* 4224 * If we joined with the right neighbor and there's a level above 4225 * us, increment the cursor at that level. 4226 */ 4227 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || 4228 (level + 1 < cur->bc_nlevels)) { 4229 error = xfs_btree_increment(cur, level + 1, &i); 4230 if (error) 4231 goto error0; 4232 } 4233 4234 /* 4235 * Readjust the ptr at this level if it's not a leaf, since it's 4236 * still pointing at the deletion point, which makes the cursor 4237 * inconsistent. If this makes the ptr 0, the caller fixes it up. 4238 * We can't use decrement because it would change the next level up. 4239 */ 4240 if (level > 0) 4241 cur->bc_ptrs[level]--; 4242 4243 /* 4244 * We combined blocks, so we have to update the parent keys if the 4245 * btree supports overlapped intervals. However, bc_ptrs[level + 1] 4246 * points to the old block so that the caller knows which record to 4247 * delete. Therefore, the caller must be savvy enough to call updkeys 4248 * for us if we return stat == 2. The other exit points from this 4249 * function don't require deletions further up the tree, so they can 4250 * call updkeys directly. 4251 */ 4252 4253 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4254 /* Return value means the next level up has something to do. */ 4255 *stat = 2; 4256 return 0; 4257 4258 error0: 4259 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 4260 if (tcur) 4261 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 4262 return error; 4263 } 4264 4265 /* 4266 * Delete the record pointed to by cur. 4267 * The cursor refers to the place where the record was (could be inserted) 4268 * when the operation returns. 4269 */ 4270 int /* error */ 4271 xfs_btree_delete( 4272 struct xfs_btree_cur *cur, 4273 int *stat) /* success/failure */ 4274 { 4275 int error; /* error return value */ 4276 int level; 4277 int i; 4278 bool joined = false; 4279 4280 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 4281 4282 /* 4283 * Go up the tree, starting at leaf level. 4284 * 4285 * If 2 is returned then a join was done; go to the next level. 4286 * Otherwise we are done. 4287 */ 4288 for (level = 0, i = 2; i == 2; level++) { 4289 error = xfs_btree_delrec(cur, level, &i); 4290 if (error) 4291 goto error0; 4292 if (i == 2) 4293 joined = true; 4294 } 4295 4296 /* 4297 * If we combined blocks as part of deleting the record, delrec won't 4298 * have updated the parent high keys so we have to do that here. 4299 */ 4300 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { 4301 error = xfs_btree_updkeys_force(cur, 0); 4302 if (error) 4303 goto error0; 4304 } 4305 4306 if (i == 0) { 4307 for (level = 1; level < cur->bc_nlevels; level++) { 4308 if (cur->bc_ptrs[level] == 0) { 4309 error = xfs_btree_decrement(cur, level, &i); 4310 if (error) 4311 goto error0; 4312 break; 4313 } 4314 } 4315 } 4316 4317 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4318 *stat = i; 4319 return 0; 4320 error0: 4321 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 4322 return error; 4323 } 4324 4325 /* 4326 * Get the data from the pointed-to record. 4327 */ 4328 int /* error */ 4329 xfs_btree_get_rec( 4330 struct xfs_btree_cur *cur, /* btree cursor */ 4331 union xfs_btree_rec **recp, /* output: btree record */ 4332 int *stat) /* output: success/failure */ 4333 { 4334 struct xfs_btree_block *block; /* btree block */ 4335 struct xfs_buf *bp; /* buffer pointer */ 4336 int ptr; /* record number */ 4337 #ifdef DEBUG 4338 int error; /* error return value */ 4339 #endif 4340 4341 ptr = cur->bc_ptrs[0]; 4342 block = xfs_btree_get_block(cur, 0, &bp); 4343 4344 #ifdef DEBUG 4345 error = xfs_btree_check_block(cur, block, 0, bp); 4346 if (error) 4347 return error; 4348 #endif 4349 4350 /* 4351 * Off the right end or left end, return failure. 4352 */ 4353 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { 4354 *stat = 0; 4355 return 0; 4356 } 4357 4358 /* 4359 * Point to the record and extract its data. 4360 */ 4361 *recp = xfs_btree_rec_addr(cur, ptr, block); 4362 *stat = 1; 4363 return 0; 4364 } 4365 4366 /* Visit a block in a btree. */ 4367 STATIC int 4368 xfs_btree_visit_block( 4369 struct xfs_btree_cur *cur, 4370 int level, 4371 xfs_btree_visit_blocks_fn fn, 4372 void *data) 4373 { 4374 struct xfs_btree_block *block; 4375 struct xfs_buf *bp; 4376 union xfs_btree_ptr rptr; 4377 int error; 4378 4379 /* do right sibling readahead */ 4380 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); 4381 block = xfs_btree_get_block(cur, level, &bp); 4382 4383 /* process the block */ 4384 error = fn(cur, level, data); 4385 if (error) 4386 return error; 4387 4388 /* now read rh sibling block for next iteration */ 4389 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 4390 if (xfs_btree_ptr_is_null(cur, &rptr)) 4391 return -ENOENT; 4392 4393 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); 4394 } 4395 4396 4397 /* Visit every block in a btree. */ 4398 int 4399 xfs_btree_visit_blocks( 4400 struct xfs_btree_cur *cur, 4401 xfs_btree_visit_blocks_fn fn, 4402 void *data) 4403 { 4404 union xfs_btree_ptr lptr; 4405 int level; 4406 struct xfs_btree_block *block = NULL; 4407 int error = 0; 4408 4409 cur->bc_ops->init_ptr_from_cur(cur, &lptr); 4410 4411 /* for each level */ 4412 for (level = cur->bc_nlevels - 1; level >= 0; level--) { 4413 /* grab the left hand block */ 4414 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); 4415 if (error) 4416 return error; 4417 4418 /* readahead the left most block for the next level down */ 4419 if (level > 0) { 4420 union xfs_btree_ptr *ptr; 4421 4422 ptr = xfs_btree_ptr_addr(cur, 1, block); 4423 xfs_btree_readahead_ptr(cur, ptr, 1); 4424 4425 /* save for the next iteration of the loop */ 4426 xfs_btree_copy_ptrs(cur, &lptr, ptr, 1); 4427 } 4428 4429 /* for each buffer in the level */ 4430 do { 4431 error = xfs_btree_visit_block(cur, level, fn, data); 4432 } while (!error); 4433 4434 if (error != -ENOENT) 4435 return error; 4436 } 4437 4438 return 0; 4439 } 4440 4441 /* 4442 * Change the owner of a btree. 4443 * 4444 * The mechanism we use here is ordered buffer logging. Because we don't know 4445 * how many buffers were are going to need to modify, we don't really want to 4446 * have to make transaction reservations for the worst case of every buffer in a 4447 * full size btree as that may be more space that we can fit in the log.... 4448 * 4449 * We do the btree walk in the most optimal manner possible - we have sibling 4450 * pointers so we can just walk all the blocks on each level from left to right 4451 * in a single pass, and then move to the next level and do the same. We can 4452 * also do readahead on the sibling pointers to get IO moving more quickly, 4453 * though for slow disks this is unlikely to make much difference to performance 4454 * as the amount of CPU work we have to do before moving to the next block is 4455 * relatively small. 4456 * 4457 * For each btree block that we load, modify the owner appropriately, set the 4458 * buffer as an ordered buffer and log it appropriately. We need to ensure that 4459 * we mark the region we change dirty so that if the buffer is relogged in 4460 * a subsequent transaction the changes we make here as an ordered buffer are 4461 * correctly relogged in that transaction. If we are in recovery context, then 4462 * just queue the modified buffer as delayed write buffer so the transaction 4463 * recovery completion writes the changes to disk. 4464 */ 4465 struct xfs_btree_block_change_owner_info { 4466 uint64_t new_owner; 4467 struct list_head *buffer_list; 4468 }; 4469 4470 static int 4471 xfs_btree_block_change_owner( 4472 struct xfs_btree_cur *cur, 4473 int level, 4474 void *data) 4475 { 4476 struct xfs_btree_block_change_owner_info *bbcoi = data; 4477 struct xfs_btree_block *block; 4478 struct xfs_buf *bp; 4479 4480 /* modify the owner */ 4481 block = xfs_btree_get_block(cur, level, &bp); 4482 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { 4483 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) 4484 return 0; 4485 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); 4486 } else { 4487 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) 4488 return 0; 4489 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); 4490 } 4491 4492 /* 4493 * If the block is a root block hosted in an inode, we might not have a 4494 * buffer pointer here and we shouldn't attempt to log the change as the 4495 * information is already held in the inode and discarded when the root 4496 * block is formatted into the on-disk inode fork. We still change it, 4497 * though, so everything is consistent in memory. 4498 */ 4499 if (!bp) { 4500 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 4501 ASSERT(level == cur->bc_nlevels - 1); 4502 return 0; 4503 } 4504 4505 if (cur->bc_tp) { 4506 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) { 4507 xfs_btree_log_block(cur, bp, XFS_BB_OWNER); 4508 return -EAGAIN; 4509 } 4510 } else { 4511 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); 4512 } 4513 4514 return 0; 4515 } 4516 4517 int 4518 xfs_btree_change_owner( 4519 struct xfs_btree_cur *cur, 4520 uint64_t new_owner, 4521 struct list_head *buffer_list) 4522 { 4523 struct xfs_btree_block_change_owner_info bbcoi; 4524 4525 bbcoi.new_owner = new_owner; 4526 bbcoi.buffer_list = buffer_list; 4527 4528 return xfs_btree_visit_blocks(cur, xfs_btree_block_change_owner, 4529 &bbcoi); 4530 } 4531 4532 /** 4533 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format 4534 * btree block 4535 * 4536 * @bp: buffer containing the btree block 4537 * @max_recs: pointer to the m_*_mxr max records field in the xfs mount 4538 * @pag_max_level: pointer to the per-ag max level field 4539 */ 4540 bool 4541 xfs_btree_sblock_v5hdr_verify( 4542 struct xfs_buf *bp) 4543 { 4544 struct xfs_mount *mp = bp->b_target->bt_mount; 4545 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 4546 struct xfs_perag *pag = bp->b_pag; 4547 4548 if (!xfs_sb_version_hascrc(&mp->m_sb)) 4549 return false; 4550 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) 4551 return false; 4552 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) 4553 return false; 4554 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) 4555 return false; 4556 return true; 4557 } 4558 4559 /** 4560 * xfs_btree_sblock_verify() -- verify a short-format btree block 4561 * 4562 * @bp: buffer containing the btree block 4563 * @max_recs: maximum records allowed in this btree node 4564 */ 4565 bool 4566 xfs_btree_sblock_verify( 4567 struct xfs_buf *bp, 4568 unsigned int max_recs) 4569 { 4570 struct xfs_mount *mp = bp->b_target->bt_mount; 4571 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 4572 4573 /* numrecs verification */ 4574 if (be16_to_cpu(block->bb_numrecs) > max_recs) 4575 return false; 4576 4577 /* sibling pointer verification */ 4578 if (!block->bb_u.s.bb_leftsib || 4579 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks && 4580 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK))) 4581 return false; 4582 if (!block->bb_u.s.bb_rightsib || 4583 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks && 4584 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK))) 4585 return false; 4586 4587 return true; 4588 } 4589 4590 /* 4591 * Calculate the number of btree levels needed to store a given number of 4592 * records in a short-format btree. 4593 */ 4594 uint 4595 xfs_btree_compute_maxlevels( 4596 struct xfs_mount *mp, 4597 uint *limits, 4598 unsigned long len) 4599 { 4600 uint level; 4601 unsigned long maxblocks; 4602 4603 maxblocks = (len + limits[0] - 1) / limits[0]; 4604 for (level = 1; maxblocks > 1; level++) 4605 maxblocks = (maxblocks + limits[1] - 1) / limits[1]; 4606 return level; 4607 } 4608 4609 /* 4610 * Query a regular btree for all records overlapping a given interval. 4611 * Start with a LE lookup of the key of low_rec and return all records 4612 * until we find a record with a key greater than the key of high_rec. 4613 */ 4614 STATIC int 4615 xfs_btree_simple_query_range( 4616 struct xfs_btree_cur *cur, 4617 union xfs_btree_key *low_key, 4618 union xfs_btree_key *high_key, 4619 xfs_btree_query_range_fn fn, 4620 void *priv) 4621 { 4622 union xfs_btree_rec *recp; 4623 union xfs_btree_key rec_key; 4624 int64_t diff; 4625 int stat; 4626 bool firstrec = true; 4627 int error; 4628 4629 ASSERT(cur->bc_ops->init_high_key_from_rec); 4630 ASSERT(cur->bc_ops->diff_two_keys); 4631 4632 /* 4633 * Find the leftmost record. The btree cursor must be set 4634 * to the low record used to generate low_key. 4635 */ 4636 stat = 0; 4637 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat); 4638 if (error) 4639 goto out; 4640 4641 /* Nothing? See if there's anything to the right. */ 4642 if (!stat) { 4643 error = xfs_btree_increment(cur, 0, &stat); 4644 if (error) 4645 goto out; 4646 } 4647 4648 while (stat) { 4649 /* Find the record. */ 4650 error = xfs_btree_get_rec(cur, &recp, &stat); 4651 if (error || !stat) 4652 break; 4653 4654 /* Skip if high_key(rec) < low_key. */ 4655 if (firstrec) { 4656 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); 4657 firstrec = false; 4658 diff = cur->bc_ops->diff_two_keys(cur, low_key, 4659 &rec_key); 4660 if (diff > 0) 4661 goto advloop; 4662 } 4663 4664 /* Stop if high_key < low_key(rec). */ 4665 cur->bc_ops->init_key_from_rec(&rec_key, recp); 4666 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); 4667 if (diff > 0) 4668 break; 4669 4670 /* Callback */ 4671 error = fn(cur, recp, priv); 4672 if (error < 0 || error == XFS_BTREE_QUERY_RANGE_ABORT) 4673 break; 4674 4675 advloop: 4676 /* Move on to the next record. */ 4677 error = xfs_btree_increment(cur, 0, &stat); 4678 if (error) 4679 break; 4680 } 4681 4682 out: 4683 return error; 4684 } 4685 4686 /* 4687 * Query an overlapped interval btree for all records overlapping a given 4688 * interval. This function roughly follows the algorithm given in 4689 * "Interval Trees" of _Introduction to Algorithms_, which is section 4690 * 14.3 in the 2nd and 3rd editions. 4691 * 4692 * First, generate keys for the low and high records passed in. 4693 * 4694 * For any leaf node, generate the high and low keys for the record. 4695 * If the record keys overlap with the query low/high keys, pass the 4696 * record to the function iterator. 4697 * 4698 * For any internal node, compare the low and high keys of each 4699 * pointer against the query low/high keys. If there's an overlap, 4700 * follow the pointer. 4701 * 4702 * As an optimization, we stop scanning a block when we find a low key 4703 * that is greater than the query's high key. 4704 */ 4705 STATIC int 4706 xfs_btree_overlapped_query_range( 4707 struct xfs_btree_cur *cur, 4708 union xfs_btree_key *low_key, 4709 union xfs_btree_key *high_key, 4710 xfs_btree_query_range_fn fn, 4711 void *priv) 4712 { 4713 union xfs_btree_ptr ptr; 4714 union xfs_btree_ptr *pp; 4715 union xfs_btree_key rec_key; 4716 union xfs_btree_key rec_hkey; 4717 union xfs_btree_key *lkp; 4718 union xfs_btree_key *hkp; 4719 union xfs_btree_rec *recp; 4720 struct xfs_btree_block *block; 4721 int64_t ldiff; 4722 int64_t hdiff; 4723 int level; 4724 struct xfs_buf *bp; 4725 int i; 4726 int error; 4727 4728 /* Load the root of the btree. */ 4729 level = cur->bc_nlevels - 1; 4730 cur->bc_ops->init_ptr_from_cur(cur, &ptr); 4731 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); 4732 if (error) 4733 return error; 4734 xfs_btree_get_block(cur, level, &bp); 4735 trace_xfs_btree_overlapped_query_range(cur, level, bp); 4736 #ifdef DEBUG 4737 error = xfs_btree_check_block(cur, block, level, bp); 4738 if (error) 4739 goto out; 4740 #endif 4741 cur->bc_ptrs[level] = 1; 4742 4743 while (level < cur->bc_nlevels) { 4744 block = xfs_btree_get_block(cur, level, &bp); 4745 4746 /* End of node, pop back towards the root. */ 4747 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { 4748 pop_up: 4749 if (level < cur->bc_nlevels - 1) 4750 cur->bc_ptrs[level + 1]++; 4751 level++; 4752 continue; 4753 } 4754 4755 if (level == 0) { 4756 /* Handle a leaf node. */ 4757 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 4758 4759 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); 4760 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, 4761 low_key); 4762 4763 cur->bc_ops->init_key_from_rec(&rec_key, recp); 4764 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, 4765 &rec_key); 4766 4767 /* 4768 * If (record's high key >= query's low key) and 4769 * (query's high key >= record's low key), then 4770 * this record overlaps the query range; callback. 4771 */ 4772 if (ldiff >= 0 && hdiff >= 0) { 4773 error = fn(cur, recp, priv); 4774 if (error < 0 || 4775 error == XFS_BTREE_QUERY_RANGE_ABORT) 4776 break; 4777 } else if (hdiff < 0) { 4778 /* Record is larger than high key; pop. */ 4779 goto pop_up; 4780 } 4781 cur->bc_ptrs[level]++; 4782 continue; 4783 } 4784 4785 /* Handle an internal node. */ 4786 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); 4787 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); 4788 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); 4789 4790 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); 4791 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); 4792 4793 /* 4794 * If (pointer's high key >= query's low key) and 4795 * (query's high key >= pointer's low key), then 4796 * this record overlaps the query range; follow pointer. 4797 */ 4798 if (ldiff >= 0 && hdiff >= 0) { 4799 level--; 4800 error = xfs_btree_lookup_get_block(cur, level, pp, 4801 &block); 4802 if (error) 4803 goto out; 4804 xfs_btree_get_block(cur, level, &bp); 4805 trace_xfs_btree_overlapped_query_range(cur, level, bp); 4806 #ifdef DEBUG 4807 error = xfs_btree_check_block(cur, block, level, bp); 4808 if (error) 4809 goto out; 4810 #endif 4811 cur->bc_ptrs[level] = 1; 4812 continue; 4813 } else if (hdiff < 0) { 4814 /* The low key is larger than the upper range; pop. */ 4815 goto pop_up; 4816 } 4817 cur->bc_ptrs[level]++; 4818 } 4819 4820 out: 4821 /* 4822 * If we don't end this function with the cursor pointing at a record 4823 * block, a subsequent non-error cursor deletion will not release 4824 * node-level buffers, causing a buffer leak. This is quite possible 4825 * with a zero-results range query, so release the buffers if we 4826 * failed to return any results. 4827 */ 4828 if (cur->bc_bufs[0] == NULL) { 4829 for (i = 0; i < cur->bc_nlevels; i++) { 4830 if (cur->bc_bufs[i]) { 4831 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); 4832 cur->bc_bufs[i] = NULL; 4833 cur->bc_ptrs[i] = 0; 4834 cur->bc_ra[i] = 0; 4835 } 4836 } 4837 } 4838 4839 return error; 4840 } 4841 4842 /* 4843 * Query a btree for all records overlapping a given interval of keys. The 4844 * supplied function will be called with each record found; return one of the 4845 * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error 4846 * code. This function returns XFS_BTREE_QUERY_RANGE_ABORT, zero, or a 4847 * negative error code. 4848 */ 4849 int 4850 xfs_btree_query_range( 4851 struct xfs_btree_cur *cur, 4852 union xfs_btree_irec *low_rec, 4853 union xfs_btree_irec *high_rec, 4854 xfs_btree_query_range_fn fn, 4855 void *priv) 4856 { 4857 union xfs_btree_rec rec; 4858 union xfs_btree_key low_key; 4859 union xfs_btree_key high_key; 4860 4861 /* Find the keys of both ends of the interval. */ 4862 cur->bc_rec = *high_rec; 4863 cur->bc_ops->init_rec_from_cur(cur, &rec); 4864 cur->bc_ops->init_key_from_rec(&high_key, &rec); 4865 4866 cur->bc_rec = *low_rec; 4867 cur->bc_ops->init_rec_from_cur(cur, &rec); 4868 cur->bc_ops->init_key_from_rec(&low_key, &rec); 4869 4870 /* Enforce low key < high key. */ 4871 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) 4872 return -EINVAL; 4873 4874 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 4875 return xfs_btree_simple_query_range(cur, &low_key, 4876 &high_key, fn, priv); 4877 return xfs_btree_overlapped_query_range(cur, &low_key, &high_key, 4878 fn, priv); 4879 } 4880 4881 /* Query a btree for all records. */ 4882 int 4883 xfs_btree_query_all( 4884 struct xfs_btree_cur *cur, 4885 xfs_btree_query_range_fn fn, 4886 void *priv) 4887 { 4888 union xfs_btree_key low_key; 4889 union xfs_btree_key high_key; 4890 4891 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec)); 4892 memset(&low_key, 0, sizeof(low_key)); 4893 memset(&high_key, 0xFF, sizeof(high_key)); 4894 4895 return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv); 4896 } 4897 4898 /* 4899 * Calculate the number of blocks needed to store a given number of records 4900 * in a short-format (per-AG metadata) btree. 4901 */ 4902 xfs_extlen_t 4903 xfs_btree_calc_size( 4904 struct xfs_mount *mp, 4905 uint *limits, 4906 unsigned long long len) 4907 { 4908 int level; 4909 int maxrecs; 4910 xfs_extlen_t rval; 4911 4912 maxrecs = limits[0]; 4913 for (level = 0, rval = 0; len > 1; level++) { 4914 len += maxrecs - 1; 4915 do_div(len, maxrecs); 4916 maxrecs = limits[1]; 4917 rval += len; 4918 } 4919 return rval; 4920 } 4921 4922 static int 4923 xfs_btree_count_blocks_helper( 4924 struct xfs_btree_cur *cur, 4925 int level, 4926 void *data) 4927 { 4928 xfs_extlen_t *blocks = data; 4929 (*blocks)++; 4930 4931 return 0; 4932 } 4933 4934 /* Count the blocks in a btree and return the result in *blocks. */ 4935 int 4936 xfs_btree_count_blocks( 4937 struct xfs_btree_cur *cur, 4938 xfs_extlen_t *blocks) 4939 { 4940 *blocks = 0; 4941 return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper, 4942 blocks); 4943 } 4944 4945 /* Compare two btree pointers. */ 4946 int64_t 4947 xfs_btree_diff_two_ptrs( 4948 struct xfs_btree_cur *cur, 4949 const union xfs_btree_ptr *a, 4950 const union xfs_btree_ptr *b) 4951 { 4952 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 4953 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l); 4954 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); 4955 } 4956