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