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 block = NULL; 1818 keyno = 0; 1819 1820 /* initialise start pointer from cursor */ 1821 cur->bc_ops->init_ptr_from_cur(cur, &ptr); 1822 pp = &ptr; 1823 1824 /* 1825 * Iterate over each level in the btree, starting at the root. 1826 * For each level above the leaves, find the key we need, based 1827 * on the lookup record, then follow the corresponding block 1828 * pointer down to the next level. 1829 */ 1830 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { 1831 /* Get the block we need to do the lookup on. */ 1832 error = xfs_btree_lookup_get_block(cur, level, pp, &block); 1833 if (error) 1834 goto error0; 1835 1836 if (diff == 0) { 1837 /* 1838 * If we already had a key match at a higher level, we 1839 * know we need to use the first entry in this block. 1840 */ 1841 keyno = 1; 1842 } else { 1843 /* Otherwise search this block. Do a binary search. */ 1844 1845 int high; /* high entry number */ 1846 int low; /* low entry number */ 1847 1848 /* Set low and high entry numbers, 1-based. */ 1849 low = 1; 1850 high = xfs_btree_get_numrecs(block); 1851 if (!high) { 1852 /* Block is empty, must be an empty leaf. */ 1853 ASSERT(level == 0 && cur->bc_nlevels == 1); 1854 1855 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; 1856 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1857 *stat = 0; 1858 return 0; 1859 } 1860 1861 /* Binary search the block. */ 1862 while (low <= high) { 1863 union xfs_btree_key key; 1864 union xfs_btree_key *kp; 1865 1866 XFS_BTREE_STATS_INC(cur, compare); 1867 1868 /* keyno is average of low and high. */ 1869 keyno = (low + high) >> 1; 1870 1871 /* Get current search key */ 1872 kp = xfs_lookup_get_search_key(cur, level, 1873 keyno, block, &key); 1874 1875 /* 1876 * Compute difference to get next direction: 1877 * - less than, move right 1878 * - greater than, move left 1879 * - equal, we're done 1880 */ 1881 diff = cur->bc_ops->key_diff(cur, kp); 1882 if (diff < 0) 1883 low = keyno + 1; 1884 else if (diff > 0) 1885 high = keyno - 1; 1886 else 1887 break; 1888 } 1889 } 1890 1891 /* 1892 * If there are more levels, set up for the next level 1893 * by getting the block number and filling in the cursor. 1894 */ 1895 if (level > 0) { 1896 /* 1897 * If we moved left, need the previous key number, 1898 * unless there isn't one. 1899 */ 1900 if (diff > 0 && --keyno < 1) 1901 keyno = 1; 1902 pp = xfs_btree_ptr_addr(cur, keyno, block); 1903 1904 #ifdef DEBUG 1905 error = xfs_btree_check_ptr(cur, pp, 0, level); 1906 if (error) 1907 goto error0; 1908 #endif 1909 cur->bc_ptrs[level] = keyno; 1910 } 1911 } 1912 1913 /* Done with the search. See if we need to adjust the results. */ 1914 if (dir != XFS_LOOKUP_LE && diff < 0) { 1915 keyno++; 1916 /* 1917 * If ge search and we went off the end of the block, but it's 1918 * not the last block, we're in the wrong block. 1919 */ 1920 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 1921 if (dir == XFS_LOOKUP_GE && 1922 keyno > xfs_btree_get_numrecs(block) && 1923 !xfs_btree_ptr_is_null(cur, &ptr)) { 1924 int i; 1925 1926 cur->bc_ptrs[0] = keyno; 1927 error = xfs_btree_increment(cur, 0, &i); 1928 if (error) 1929 goto error0; 1930 XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, i == 1); 1931 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1932 *stat = 1; 1933 return 0; 1934 } 1935 } else if (dir == XFS_LOOKUP_LE && diff > 0) 1936 keyno--; 1937 cur->bc_ptrs[0] = keyno; 1938 1939 /* Return if we succeeded or not. */ 1940 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) 1941 *stat = 0; 1942 else if (dir != XFS_LOOKUP_EQ || diff == 0) 1943 *stat = 1; 1944 else 1945 *stat = 0; 1946 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 1947 return 0; 1948 1949 error0: 1950 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 1951 return error; 1952 } 1953 1954 /* Find the high key storage area from a regular key. */ 1955 STATIC union xfs_btree_key * 1956 xfs_btree_high_key_from_key( 1957 struct xfs_btree_cur *cur, 1958 union xfs_btree_key *key) 1959 { 1960 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); 1961 return (union xfs_btree_key *)((char *)key + 1962 (cur->bc_ops->key_len / 2)); 1963 } 1964 1965 /* Determine the low (and high if overlapped) keys of a leaf block */ 1966 STATIC void 1967 xfs_btree_get_leaf_keys( 1968 struct xfs_btree_cur *cur, 1969 struct xfs_btree_block *block, 1970 union xfs_btree_key *key) 1971 { 1972 union xfs_btree_key max_hkey; 1973 union xfs_btree_key hkey; 1974 union xfs_btree_rec *rec; 1975 union xfs_btree_key *high; 1976 int n; 1977 1978 rec = xfs_btree_rec_addr(cur, 1, block); 1979 cur->bc_ops->init_key_from_rec(key, rec); 1980 1981 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 1982 1983 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); 1984 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { 1985 rec = xfs_btree_rec_addr(cur, n, block); 1986 cur->bc_ops->init_high_key_from_rec(&hkey, rec); 1987 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) 1988 > 0) 1989 max_hkey = hkey; 1990 } 1991 1992 high = xfs_btree_high_key_from_key(cur, key); 1993 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); 1994 } 1995 } 1996 1997 /* Determine the low (and high if overlapped) keys of a node block */ 1998 STATIC void 1999 xfs_btree_get_node_keys( 2000 struct xfs_btree_cur *cur, 2001 struct xfs_btree_block *block, 2002 union xfs_btree_key *key) 2003 { 2004 union xfs_btree_key *hkey; 2005 union xfs_btree_key *max_hkey; 2006 union xfs_btree_key *high; 2007 int n; 2008 2009 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2010 memcpy(key, xfs_btree_key_addr(cur, 1, block), 2011 cur->bc_ops->key_len / 2); 2012 2013 max_hkey = xfs_btree_high_key_addr(cur, 1, block); 2014 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { 2015 hkey = xfs_btree_high_key_addr(cur, n, block); 2016 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) 2017 max_hkey = hkey; 2018 } 2019 2020 high = xfs_btree_high_key_from_key(cur, key); 2021 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); 2022 } else { 2023 memcpy(key, xfs_btree_key_addr(cur, 1, block), 2024 cur->bc_ops->key_len); 2025 } 2026 } 2027 2028 /* Derive the keys for any btree block. */ 2029 STATIC void 2030 xfs_btree_get_keys( 2031 struct xfs_btree_cur *cur, 2032 struct xfs_btree_block *block, 2033 union xfs_btree_key *key) 2034 { 2035 if (be16_to_cpu(block->bb_level) == 0) 2036 xfs_btree_get_leaf_keys(cur, block, key); 2037 else 2038 xfs_btree_get_node_keys(cur, block, key); 2039 } 2040 2041 /* 2042 * Decide if we need to update the parent keys of a btree block. For 2043 * a standard btree this is only necessary if we're updating the first 2044 * record/key. For an overlapping btree, we must always update the 2045 * keys because the highest key can be in any of the records or keys 2046 * in the block. 2047 */ 2048 static inline bool 2049 xfs_btree_needs_key_update( 2050 struct xfs_btree_cur *cur, 2051 int ptr) 2052 { 2053 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; 2054 } 2055 2056 /* 2057 * Update the low and high parent keys of the given level, progressing 2058 * towards the root. If force_all is false, stop if the keys for a given 2059 * level do not need updating. 2060 */ 2061 STATIC int 2062 __xfs_btree_updkeys( 2063 struct xfs_btree_cur *cur, 2064 int level, 2065 struct xfs_btree_block *block, 2066 struct xfs_buf *bp0, 2067 bool force_all) 2068 { 2069 union xfs_btree_bigkey key; /* keys from current level */ 2070 union xfs_btree_key *lkey; /* keys from the next level up */ 2071 union xfs_btree_key *hkey; 2072 union xfs_btree_key *nlkey; /* keys from the next level up */ 2073 union xfs_btree_key *nhkey; 2074 struct xfs_buf *bp; 2075 int ptr; 2076 2077 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); 2078 2079 /* Exit if there aren't any parent levels to update. */ 2080 if (level + 1 >= cur->bc_nlevels) 2081 return 0; 2082 2083 trace_xfs_btree_updkeys(cur, level, bp0); 2084 2085 lkey = (union xfs_btree_key *)&key; 2086 hkey = xfs_btree_high_key_from_key(cur, lkey); 2087 xfs_btree_get_keys(cur, block, lkey); 2088 for (level++; level < cur->bc_nlevels; level++) { 2089 #ifdef DEBUG 2090 int error; 2091 #endif 2092 block = xfs_btree_get_block(cur, level, &bp); 2093 trace_xfs_btree_updkeys(cur, level, bp); 2094 #ifdef DEBUG 2095 error = xfs_btree_check_block(cur, block, level, bp); 2096 if (error) { 2097 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2098 return error; 2099 } 2100 #endif 2101 ptr = cur->bc_ptrs[level]; 2102 nlkey = xfs_btree_key_addr(cur, ptr, block); 2103 nhkey = xfs_btree_high_key_addr(cur, ptr, block); 2104 if (!force_all && 2105 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || 2106 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) 2107 break; 2108 xfs_btree_copy_keys(cur, nlkey, lkey, 1); 2109 xfs_btree_log_keys(cur, bp, ptr, ptr); 2110 if (level + 1 >= cur->bc_nlevels) 2111 break; 2112 xfs_btree_get_node_keys(cur, block, lkey); 2113 } 2114 2115 return 0; 2116 } 2117 2118 /* Update all the keys from some level in cursor back to the root. */ 2119 STATIC int 2120 xfs_btree_updkeys_force( 2121 struct xfs_btree_cur *cur, 2122 int level) 2123 { 2124 struct xfs_buf *bp; 2125 struct xfs_btree_block *block; 2126 2127 block = xfs_btree_get_block(cur, level, &bp); 2128 return __xfs_btree_updkeys(cur, level, block, bp, true); 2129 } 2130 2131 /* 2132 * Update the parent keys of the given level, progressing towards the root. 2133 */ 2134 STATIC int 2135 xfs_btree_update_keys( 2136 struct xfs_btree_cur *cur, 2137 int level) 2138 { 2139 struct xfs_btree_block *block; 2140 struct xfs_buf *bp; 2141 union xfs_btree_key *kp; 2142 union xfs_btree_key key; 2143 int ptr; 2144 2145 ASSERT(level >= 0); 2146 2147 block = xfs_btree_get_block(cur, level, &bp); 2148 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) 2149 return __xfs_btree_updkeys(cur, level, block, bp, false); 2150 2151 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2152 XFS_BTREE_TRACE_ARGIK(cur, level, keyp); 2153 2154 /* 2155 * Go up the tree from this level toward the root. 2156 * At each level, update the key value to the value input. 2157 * Stop when we reach a level where the cursor isn't pointing 2158 * at the first entry in the block. 2159 */ 2160 xfs_btree_get_keys(cur, block, &key); 2161 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { 2162 #ifdef DEBUG 2163 int error; 2164 #endif 2165 block = xfs_btree_get_block(cur, level, &bp); 2166 #ifdef DEBUG 2167 error = xfs_btree_check_block(cur, block, level, bp); 2168 if (error) { 2169 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2170 return error; 2171 } 2172 #endif 2173 ptr = cur->bc_ptrs[level]; 2174 kp = xfs_btree_key_addr(cur, ptr, block); 2175 xfs_btree_copy_keys(cur, kp, &key, 1); 2176 xfs_btree_log_keys(cur, bp, ptr, ptr); 2177 } 2178 2179 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2180 return 0; 2181 } 2182 2183 /* 2184 * Update the record referred to by cur to the value in the 2185 * given record. This either works (return 0) or gets an 2186 * EFSCORRUPTED error. 2187 */ 2188 int 2189 xfs_btree_update( 2190 struct xfs_btree_cur *cur, 2191 union xfs_btree_rec *rec) 2192 { 2193 struct xfs_btree_block *block; 2194 struct xfs_buf *bp; 2195 int error; 2196 int ptr; 2197 union xfs_btree_rec *rp; 2198 2199 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2200 XFS_BTREE_TRACE_ARGR(cur, rec); 2201 2202 /* Pick up the current block. */ 2203 block = xfs_btree_get_block(cur, 0, &bp); 2204 2205 #ifdef DEBUG 2206 error = xfs_btree_check_block(cur, block, 0, bp); 2207 if (error) 2208 goto error0; 2209 #endif 2210 /* Get the address of the rec to be updated. */ 2211 ptr = cur->bc_ptrs[0]; 2212 rp = xfs_btree_rec_addr(cur, ptr, block); 2213 2214 /* Fill in the new contents and log them. */ 2215 xfs_btree_copy_recs(cur, rp, rec, 1); 2216 xfs_btree_log_recs(cur, bp, ptr, ptr); 2217 2218 /* 2219 * If we are tracking the last record in the tree and 2220 * we are at the far right edge of the tree, update it. 2221 */ 2222 if (xfs_btree_is_lastrec(cur, block, 0)) { 2223 cur->bc_ops->update_lastrec(cur, block, rec, 2224 ptr, LASTREC_UPDATE); 2225 } 2226 2227 /* Pass new key value up to our parent. */ 2228 if (xfs_btree_needs_key_update(cur, ptr)) { 2229 error = xfs_btree_update_keys(cur, 0); 2230 if (error) 2231 goto error0; 2232 } 2233 2234 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2235 return 0; 2236 2237 error0: 2238 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2239 return error; 2240 } 2241 2242 /* 2243 * Move 1 record left from cur/level if possible. 2244 * Update cur to reflect the new path. 2245 */ 2246 STATIC int /* error */ 2247 xfs_btree_lshift( 2248 struct xfs_btree_cur *cur, 2249 int level, 2250 int *stat) /* success/failure */ 2251 { 2252 struct xfs_buf *lbp; /* left buffer pointer */ 2253 struct xfs_btree_block *left; /* left btree block */ 2254 int lrecs; /* left record count */ 2255 struct xfs_buf *rbp; /* right buffer pointer */ 2256 struct xfs_btree_block *right; /* right btree block */ 2257 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 2258 int rrecs; /* right record count */ 2259 union xfs_btree_ptr lptr; /* left btree pointer */ 2260 union xfs_btree_key *rkp = NULL; /* right btree key */ 2261 union xfs_btree_ptr *rpp = NULL; /* right address pointer */ 2262 union xfs_btree_rec *rrp = NULL; /* right record pointer */ 2263 int error; /* error return value */ 2264 int i; 2265 2266 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2267 XFS_BTREE_TRACE_ARGI(cur, level); 2268 2269 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 2270 level == cur->bc_nlevels - 1) 2271 goto out0; 2272 2273 /* Set up variables for this block as "right". */ 2274 right = xfs_btree_get_block(cur, level, &rbp); 2275 2276 #ifdef DEBUG 2277 error = xfs_btree_check_block(cur, right, level, rbp); 2278 if (error) 2279 goto error0; 2280 #endif 2281 2282 /* If we've got no left sibling then we can't shift an entry left. */ 2283 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 2284 if (xfs_btree_ptr_is_null(cur, &lptr)) 2285 goto out0; 2286 2287 /* 2288 * If the cursor entry is the one that would be moved, don't 2289 * do it... it's too complicated. 2290 */ 2291 if (cur->bc_ptrs[level] <= 1) 2292 goto out0; 2293 2294 /* Set up the left neighbor as "left". */ 2295 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 2296 if (error) 2297 goto error0; 2298 2299 /* If it's full, it can't take another entry. */ 2300 lrecs = xfs_btree_get_numrecs(left); 2301 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) 2302 goto out0; 2303 2304 rrecs = xfs_btree_get_numrecs(right); 2305 2306 /* 2307 * We add one entry to the left side and remove one for the right side. 2308 * Account for it here, the changes will be updated on disk and logged 2309 * later. 2310 */ 2311 lrecs++; 2312 rrecs--; 2313 2314 XFS_BTREE_STATS_INC(cur, lshift); 2315 XFS_BTREE_STATS_ADD(cur, moves, 1); 2316 2317 /* 2318 * If non-leaf, copy a key and a ptr to the left block. 2319 * Log the changes to the left block. 2320 */ 2321 if (level > 0) { 2322 /* It's a non-leaf. Move keys and pointers. */ 2323 union xfs_btree_key *lkp; /* left btree key */ 2324 union xfs_btree_ptr *lpp; /* left address pointer */ 2325 2326 lkp = xfs_btree_key_addr(cur, lrecs, left); 2327 rkp = xfs_btree_key_addr(cur, 1, right); 2328 2329 lpp = xfs_btree_ptr_addr(cur, lrecs, left); 2330 rpp = xfs_btree_ptr_addr(cur, 1, right); 2331 #ifdef DEBUG 2332 error = xfs_btree_check_ptr(cur, rpp, 0, level); 2333 if (error) 2334 goto error0; 2335 #endif 2336 xfs_btree_copy_keys(cur, lkp, rkp, 1); 2337 xfs_btree_copy_ptrs(cur, lpp, rpp, 1); 2338 2339 xfs_btree_log_keys(cur, lbp, lrecs, lrecs); 2340 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs); 2341 2342 ASSERT(cur->bc_ops->keys_inorder(cur, 2343 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); 2344 } else { 2345 /* It's a leaf. Move records. */ 2346 union xfs_btree_rec *lrp; /* left record pointer */ 2347 2348 lrp = xfs_btree_rec_addr(cur, lrecs, left); 2349 rrp = xfs_btree_rec_addr(cur, 1, right); 2350 2351 xfs_btree_copy_recs(cur, lrp, rrp, 1); 2352 xfs_btree_log_recs(cur, lbp, lrecs, lrecs); 2353 2354 ASSERT(cur->bc_ops->recs_inorder(cur, 2355 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); 2356 } 2357 2358 xfs_btree_set_numrecs(left, lrecs); 2359 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS); 2360 2361 xfs_btree_set_numrecs(right, rrecs); 2362 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS); 2363 2364 /* 2365 * Slide the contents of right down one entry. 2366 */ 2367 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); 2368 if (level > 0) { 2369 /* It's a nonleaf. operate on keys and ptrs */ 2370 #ifdef DEBUG 2371 int i; /* loop index */ 2372 2373 for (i = 0; i < rrecs; i++) { 2374 error = xfs_btree_check_ptr(cur, rpp, i + 1, level); 2375 if (error) 2376 goto error0; 2377 } 2378 #endif 2379 xfs_btree_shift_keys(cur, 2380 xfs_btree_key_addr(cur, 2, right), 2381 -1, rrecs); 2382 xfs_btree_shift_ptrs(cur, 2383 xfs_btree_ptr_addr(cur, 2, right), 2384 -1, rrecs); 2385 2386 xfs_btree_log_keys(cur, rbp, 1, rrecs); 2387 xfs_btree_log_ptrs(cur, rbp, 1, rrecs); 2388 } else { 2389 /* It's a leaf. operate on records */ 2390 xfs_btree_shift_recs(cur, 2391 xfs_btree_rec_addr(cur, 2, right), 2392 -1, rrecs); 2393 xfs_btree_log_recs(cur, rbp, 1, rrecs); 2394 } 2395 2396 /* 2397 * Using a temporary cursor, update the parent key values of the 2398 * block on the left. 2399 */ 2400 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2401 error = xfs_btree_dup_cursor(cur, &tcur); 2402 if (error) 2403 goto error0; 2404 i = xfs_btree_firstrec(tcur, level); 2405 XFS_WANT_CORRUPTED_GOTO(tcur->bc_mp, i == 1, error0); 2406 2407 error = xfs_btree_decrement(tcur, level, &i); 2408 if (error) 2409 goto error1; 2410 2411 /* Update the parent high keys of the left block, if needed. */ 2412 error = xfs_btree_update_keys(tcur, level); 2413 if (error) 2414 goto error1; 2415 2416 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 2417 } 2418 2419 /* Update the parent keys of the right block. */ 2420 error = xfs_btree_update_keys(cur, level); 2421 if (error) 2422 goto error0; 2423 2424 /* Slide the cursor value left one. */ 2425 cur->bc_ptrs[level]--; 2426 2427 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2428 *stat = 1; 2429 return 0; 2430 2431 out0: 2432 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2433 *stat = 0; 2434 return 0; 2435 2436 error0: 2437 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2438 return error; 2439 2440 error1: 2441 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR); 2442 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 2443 return error; 2444 } 2445 2446 /* 2447 * Move 1 record right from cur/level if possible. 2448 * Update cur to reflect the new path. 2449 */ 2450 STATIC int /* error */ 2451 xfs_btree_rshift( 2452 struct xfs_btree_cur *cur, 2453 int level, 2454 int *stat) /* success/failure */ 2455 { 2456 struct xfs_buf *lbp; /* left buffer pointer */ 2457 struct xfs_btree_block *left; /* left btree block */ 2458 struct xfs_buf *rbp; /* right buffer pointer */ 2459 struct xfs_btree_block *right; /* right btree block */ 2460 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 2461 union xfs_btree_ptr rptr; /* right block pointer */ 2462 union xfs_btree_key *rkp; /* right btree key */ 2463 int rrecs; /* right record count */ 2464 int lrecs; /* left record count */ 2465 int error; /* error return value */ 2466 int i; /* loop counter */ 2467 2468 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2469 XFS_BTREE_TRACE_ARGI(cur, level); 2470 2471 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 2472 (level == cur->bc_nlevels - 1)) 2473 goto out0; 2474 2475 /* Set up variables for this block as "left". */ 2476 left = xfs_btree_get_block(cur, level, &lbp); 2477 2478 #ifdef DEBUG 2479 error = xfs_btree_check_block(cur, left, level, lbp); 2480 if (error) 2481 goto error0; 2482 #endif 2483 2484 /* If we've got no right sibling then we can't shift an entry right. */ 2485 xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB); 2486 if (xfs_btree_ptr_is_null(cur, &rptr)) 2487 goto out0; 2488 2489 /* 2490 * If the cursor entry is the one that would be moved, don't 2491 * do it... it's too complicated. 2492 */ 2493 lrecs = xfs_btree_get_numrecs(left); 2494 if (cur->bc_ptrs[level] >= lrecs) 2495 goto out0; 2496 2497 /* Set up the right neighbor as "right". */ 2498 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 2499 if (error) 2500 goto error0; 2501 2502 /* If it's full, it can't take another entry. */ 2503 rrecs = xfs_btree_get_numrecs(right); 2504 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) 2505 goto out0; 2506 2507 XFS_BTREE_STATS_INC(cur, rshift); 2508 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 2509 2510 /* 2511 * Make a hole at the start of the right neighbor block, then 2512 * copy the last left block entry to the hole. 2513 */ 2514 if (level > 0) { 2515 /* It's a nonleaf. make a hole in the keys and ptrs */ 2516 union xfs_btree_key *lkp; 2517 union xfs_btree_ptr *lpp; 2518 union xfs_btree_ptr *rpp; 2519 2520 lkp = xfs_btree_key_addr(cur, lrecs, left); 2521 lpp = xfs_btree_ptr_addr(cur, lrecs, left); 2522 rkp = xfs_btree_key_addr(cur, 1, right); 2523 rpp = xfs_btree_ptr_addr(cur, 1, right); 2524 2525 #ifdef DEBUG 2526 for (i = rrecs - 1; i >= 0; i--) { 2527 error = xfs_btree_check_ptr(cur, rpp, i, level); 2528 if (error) 2529 goto error0; 2530 } 2531 #endif 2532 2533 xfs_btree_shift_keys(cur, rkp, 1, rrecs); 2534 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs); 2535 2536 #ifdef DEBUG 2537 error = xfs_btree_check_ptr(cur, lpp, 0, level); 2538 if (error) 2539 goto error0; 2540 #endif 2541 2542 /* Now put the new data in, and log it. */ 2543 xfs_btree_copy_keys(cur, rkp, lkp, 1); 2544 xfs_btree_copy_ptrs(cur, rpp, lpp, 1); 2545 2546 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1); 2547 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1); 2548 2549 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, 2550 xfs_btree_key_addr(cur, 2, right))); 2551 } else { 2552 /* It's a leaf. make a hole in the records */ 2553 union xfs_btree_rec *lrp; 2554 union xfs_btree_rec *rrp; 2555 2556 lrp = xfs_btree_rec_addr(cur, lrecs, left); 2557 rrp = xfs_btree_rec_addr(cur, 1, right); 2558 2559 xfs_btree_shift_recs(cur, rrp, 1, rrecs); 2560 2561 /* Now put the new data in, and log it. */ 2562 xfs_btree_copy_recs(cur, rrp, lrp, 1); 2563 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1); 2564 } 2565 2566 /* 2567 * Decrement and log left's numrecs, bump and log right's numrecs. 2568 */ 2569 xfs_btree_set_numrecs(left, --lrecs); 2570 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS); 2571 2572 xfs_btree_set_numrecs(right, ++rrecs); 2573 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS); 2574 2575 /* 2576 * Using a temporary cursor, update the parent key values of the 2577 * block on the right. 2578 */ 2579 error = xfs_btree_dup_cursor(cur, &tcur); 2580 if (error) 2581 goto error0; 2582 i = xfs_btree_lastrec(tcur, level); 2583 XFS_WANT_CORRUPTED_GOTO(tcur->bc_mp, i == 1, error0); 2584 2585 error = xfs_btree_increment(tcur, level, &i); 2586 if (error) 2587 goto error1; 2588 2589 /* Update the parent high keys of the left block, if needed. */ 2590 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2591 error = xfs_btree_update_keys(cur, level); 2592 if (error) 2593 goto error1; 2594 } 2595 2596 /* Update the parent keys of the right block. */ 2597 error = xfs_btree_update_keys(tcur, level); 2598 if (error) 2599 goto error1; 2600 2601 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 2602 2603 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2604 *stat = 1; 2605 return 0; 2606 2607 out0: 2608 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2609 *stat = 0; 2610 return 0; 2611 2612 error0: 2613 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2614 return error; 2615 2616 error1: 2617 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR); 2618 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 2619 return error; 2620 } 2621 2622 /* 2623 * Split cur/level block in half. 2624 * Return new block number and the key to its first 2625 * record (to be inserted into parent). 2626 */ 2627 STATIC int /* error */ 2628 __xfs_btree_split( 2629 struct xfs_btree_cur *cur, 2630 int level, 2631 union xfs_btree_ptr *ptrp, 2632 union xfs_btree_key *key, 2633 struct xfs_btree_cur **curp, 2634 int *stat) /* success/failure */ 2635 { 2636 union xfs_btree_ptr lptr; /* left sibling block ptr */ 2637 struct xfs_buf *lbp; /* left buffer pointer */ 2638 struct xfs_btree_block *left; /* left btree block */ 2639 union xfs_btree_ptr rptr; /* right sibling block ptr */ 2640 struct xfs_buf *rbp; /* right buffer pointer */ 2641 struct xfs_btree_block *right; /* right btree block */ 2642 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ 2643 struct xfs_buf *rrbp; /* right-right buffer pointer */ 2644 struct xfs_btree_block *rrblock; /* right-right btree block */ 2645 int lrecs; 2646 int rrecs; 2647 int src_index; 2648 int error; /* error return value */ 2649 #ifdef DEBUG 2650 int i; 2651 #endif 2652 2653 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2654 XFS_BTREE_TRACE_ARGIPK(cur, level, *ptrp, key); 2655 2656 XFS_BTREE_STATS_INC(cur, split); 2657 2658 /* Set up left block (current one). */ 2659 left = xfs_btree_get_block(cur, level, &lbp); 2660 2661 #ifdef DEBUG 2662 error = xfs_btree_check_block(cur, left, level, lbp); 2663 if (error) 2664 goto error0; 2665 #endif 2666 2667 xfs_btree_buf_to_ptr(cur, lbp, &lptr); 2668 2669 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 2670 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); 2671 if (error) 2672 goto error0; 2673 if (*stat == 0) 2674 goto out0; 2675 XFS_BTREE_STATS_INC(cur, alloc); 2676 2677 /* Set up the new block as "right". */ 2678 error = xfs_btree_get_buf_block(cur, &rptr, 0, &right, &rbp); 2679 if (error) 2680 goto error0; 2681 2682 /* Fill in the btree header for the new right block. */ 2683 xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0); 2684 2685 /* 2686 * Split the entries between the old and the new block evenly. 2687 * Make sure that if there's an odd number of entries now, that 2688 * each new block will have the same number of entries. 2689 */ 2690 lrecs = xfs_btree_get_numrecs(left); 2691 rrecs = lrecs / 2; 2692 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1) 2693 rrecs++; 2694 src_index = (lrecs - rrecs + 1); 2695 2696 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 2697 2698 /* Adjust numrecs for the later get_*_keys() calls. */ 2699 lrecs -= rrecs; 2700 xfs_btree_set_numrecs(left, lrecs); 2701 xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs); 2702 2703 /* 2704 * Copy btree block entries from the left block over to the 2705 * new block, the right. Update the right block and log the 2706 * changes. 2707 */ 2708 if (level > 0) { 2709 /* It's a non-leaf. Move keys and pointers. */ 2710 union xfs_btree_key *lkp; /* left btree key */ 2711 union xfs_btree_ptr *lpp; /* left address pointer */ 2712 union xfs_btree_key *rkp; /* right btree key */ 2713 union xfs_btree_ptr *rpp; /* right address pointer */ 2714 2715 lkp = xfs_btree_key_addr(cur, src_index, left); 2716 lpp = xfs_btree_ptr_addr(cur, src_index, left); 2717 rkp = xfs_btree_key_addr(cur, 1, right); 2718 rpp = xfs_btree_ptr_addr(cur, 1, right); 2719 2720 #ifdef DEBUG 2721 for (i = src_index; i < rrecs; i++) { 2722 error = xfs_btree_check_ptr(cur, lpp, i, level); 2723 if (error) 2724 goto error0; 2725 } 2726 #endif 2727 2728 /* Copy the keys & pointers to the new block. */ 2729 xfs_btree_copy_keys(cur, rkp, lkp, rrecs); 2730 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs); 2731 2732 xfs_btree_log_keys(cur, rbp, 1, rrecs); 2733 xfs_btree_log_ptrs(cur, rbp, 1, rrecs); 2734 2735 /* Stash the keys of the new block for later insertion. */ 2736 xfs_btree_get_node_keys(cur, right, key); 2737 } else { 2738 /* It's a leaf. Move records. */ 2739 union xfs_btree_rec *lrp; /* left record pointer */ 2740 union xfs_btree_rec *rrp; /* right record pointer */ 2741 2742 lrp = xfs_btree_rec_addr(cur, src_index, left); 2743 rrp = xfs_btree_rec_addr(cur, 1, right); 2744 2745 /* Copy records to the new block. */ 2746 xfs_btree_copy_recs(cur, rrp, lrp, rrecs); 2747 xfs_btree_log_recs(cur, rbp, 1, rrecs); 2748 2749 /* Stash the keys of the new block for later insertion. */ 2750 xfs_btree_get_leaf_keys(cur, right, key); 2751 } 2752 2753 /* 2754 * Find the left block number by looking in the buffer. 2755 * Adjust sibling pointers. 2756 */ 2757 xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB); 2758 xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB); 2759 xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 2760 xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB); 2761 2762 xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS); 2763 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 2764 2765 /* 2766 * If there's a block to the new block's right, make that block 2767 * point back to right instead of to left. 2768 */ 2769 if (!xfs_btree_ptr_is_null(cur, &rrptr)) { 2770 error = xfs_btree_read_buf_block(cur, &rrptr, 2771 0, &rrblock, &rrbp); 2772 if (error) 2773 goto error0; 2774 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB); 2775 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB); 2776 } 2777 2778 /* Update the parent high keys of the left block, if needed. */ 2779 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { 2780 error = xfs_btree_update_keys(cur, level); 2781 if (error) 2782 goto error0; 2783 } 2784 2785 /* 2786 * If the cursor is really in the right block, move it there. 2787 * If it's just pointing past the last entry in left, then we'll 2788 * insert there, so don't change anything in that case. 2789 */ 2790 if (cur->bc_ptrs[level] > lrecs + 1) { 2791 xfs_btree_setbuf(cur, level, rbp); 2792 cur->bc_ptrs[level] -= lrecs; 2793 } 2794 /* 2795 * If there are more levels, we'll need another cursor which refers 2796 * the right block, no matter where this cursor was. 2797 */ 2798 if (level + 1 < cur->bc_nlevels) { 2799 error = xfs_btree_dup_cursor(cur, curp); 2800 if (error) 2801 goto error0; 2802 (*curp)->bc_ptrs[level + 1]++; 2803 } 2804 *ptrp = rptr; 2805 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2806 *stat = 1; 2807 return 0; 2808 out0: 2809 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2810 *stat = 0; 2811 return 0; 2812 2813 error0: 2814 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 2815 return error; 2816 } 2817 2818 struct xfs_btree_split_args { 2819 struct xfs_btree_cur *cur; 2820 int level; 2821 union xfs_btree_ptr *ptrp; 2822 union xfs_btree_key *key; 2823 struct xfs_btree_cur **curp; 2824 int *stat; /* success/failure */ 2825 int result; 2826 bool kswapd; /* allocation in kswapd context */ 2827 struct completion *done; 2828 struct work_struct work; 2829 }; 2830 2831 /* 2832 * Stack switching interfaces for allocation 2833 */ 2834 static void 2835 xfs_btree_split_worker( 2836 struct work_struct *work) 2837 { 2838 struct xfs_btree_split_args *args = container_of(work, 2839 struct xfs_btree_split_args, work); 2840 unsigned long pflags; 2841 unsigned long new_pflags = PF_FSTRANS; 2842 2843 /* 2844 * we are in a transaction context here, but may also be doing work 2845 * in kswapd context, and hence we may need to inherit that state 2846 * temporarily to ensure that we don't block waiting for memory reclaim 2847 * in any way. 2848 */ 2849 if (args->kswapd) 2850 new_pflags |= PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD; 2851 2852 current_set_flags_nested(&pflags, new_pflags); 2853 2854 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, 2855 args->key, args->curp, args->stat); 2856 complete(args->done); 2857 2858 current_restore_flags_nested(&pflags, new_pflags); 2859 } 2860 2861 /* 2862 * BMBT split requests often come in with little stack to work on. Push 2863 * them off to a worker thread so there is lots of stack to use. For the other 2864 * btree types, just call directly to avoid the context switch overhead here. 2865 */ 2866 STATIC int /* error */ 2867 xfs_btree_split( 2868 struct xfs_btree_cur *cur, 2869 int level, 2870 union xfs_btree_ptr *ptrp, 2871 union xfs_btree_key *key, 2872 struct xfs_btree_cur **curp, 2873 int *stat) /* success/failure */ 2874 { 2875 struct xfs_btree_split_args args; 2876 DECLARE_COMPLETION_ONSTACK(done); 2877 2878 if (cur->bc_btnum != XFS_BTNUM_BMAP) 2879 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); 2880 2881 args.cur = cur; 2882 args.level = level; 2883 args.ptrp = ptrp; 2884 args.key = key; 2885 args.curp = curp; 2886 args.stat = stat; 2887 args.done = &done; 2888 args.kswapd = current_is_kswapd(); 2889 INIT_WORK_ONSTACK(&args.work, xfs_btree_split_worker); 2890 queue_work(xfs_alloc_wq, &args.work); 2891 wait_for_completion(&done); 2892 destroy_work_on_stack(&args.work); 2893 return args.result; 2894 } 2895 2896 2897 /* 2898 * Copy the old inode root contents into a real block and make the 2899 * broot point to it. 2900 */ 2901 int /* error */ 2902 xfs_btree_new_iroot( 2903 struct xfs_btree_cur *cur, /* btree cursor */ 2904 int *logflags, /* logging flags for inode */ 2905 int *stat) /* return status - 0 fail */ 2906 { 2907 struct xfs_buf *cbp; /* buffer for cblock */ 2908 struct xfs_btree_block *block; /* btree block */ 2909 struct xfs_btree_block *cblock; /* child btree block */ 2910 union xfs_btree_key *ckp; /* child key pointer */ 2911 union xfs_btree_ptr *cpp; /* child ptr pointer */ 2912 union xfs_btree_key *kp; /* pointer to btree key */ 2913 union xfs_btree_ptr *pp; /* pointer to block addr */ 2914 union xfs_btree_ptr nptr; /* new block addr */ 2915 int level; /* btree level */ 2916 int error; /* error return code */ 2917 #ifdef DEBUG 2918 int i; /* loop counter */ 2919 #endif 2920 2921 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 2922 XFS_BTREE_STATS_INC(cur, newroot); 2923 2924 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 2925 2926 level = cur->bc_nlevels - 1; 2927 2928 block = xfs_btree_get_iroot(cur); 2929 pp = xfs_btree_ptr_addr(cur, 1, block); 2930 2931 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 2932 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); 2933 if (error) 2934 goto error0; 2935 if (*stat == 0) { 2936 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 2937 return 0; 2938 } 2939 XFS_BTREE_STATS_INC(cur, alloc); 2940 2941 /* Copy the root into a real block. */ 2942 error = xfs_btree_get_buf_block(cur, &nptr, 0, &cblock, &cbp); 2943 if (error) 2944 goto error0; 2945 2946 /* 2947 * we can't just memcpy() the root in for CRC enabled btree blocks. 2948 * In that case have to also ensure the blkno remains correct 2949 */ 2950 memcpy(cblock, block, xfs_btree_block_len(cur)); 2951 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { 2952 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 2953 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn); 2954 else 2955 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn); 2956 } 2957 2958 be16_add_cpu(&block->bb_level, 1); 2959 xfs_btree_set_numrecs(block, 1); 2960 cur->bc_nlevels++; 2961 cur->bc_ptrs[level + 1] = 1; 2962 2963 kp = xfs_btree_key_addr(cur, 1, block); 2964 ckp = xfs_btree_key_addr(cur, 1, cblock); 2965 xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock)); 2966 2967 cpp = xfs_btree_ptr_addr(cur, 1, cblock); 2968 #ifdef DEBUG 2969 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { 2970 error = xfs_btree_check_ptr(cur, pp, i, level); 2971 if (error) 2972 goto error0; 2973 } 2974 #endif 2975 xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock)); 2976 2977 #ifdef DEBUG 2978 error = xfs_btree_check_ptr(cur, &nptr, 0, level); 2979 if (error) 2980 goto error0; 2981 #endif 2982 xfs_btree_copy_ptrs(cur, pp, &nptr, 1); 2983 2984 xfs_iroot_realloc(cur->bc_private.b.ip, 2985 1 - xfs_btree_get_numrecs(cblock), 2986 cur->bc_private.b.whichfork); 2987 2988 xfs_btree_setbuf(cur, level, cbp); 2989 2990 /* 2991 * Do all this logging at the end so that 2992 * the root is at the right level. 2993 */ 2994 xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS); 2995 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); 2996 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); 2997 2998 *logflags |= 2999 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork); 3000 *stat = 1; 3001 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3002 return 0; 3003 error0: 3004 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3005 return error; 3006 } 3007 3008 /* 3009 * Allocate a new root block, fill it in. 3010 */ 3011 STATIC int /* error */ 3012 xfs_btree_new_root( 3013 struct xfs_btree_cur *cur, /* btree cursor */ 3014 int *stat) /* success/failure */ 3015 { 3016 struct xfs_btree_block *block; /* one half of the old root block */ 3017 struct xfs_buf *bp; /* buffer containing block */ 3018 int error; /* error return value */ 3019 struct xfs_buf *lbp; /* left buffer pointer */ 3020 struct xfs_btree_block *left; /* left btree block */ 3021 struct xfs_buf *nbp; /* new (root) buffer */ 3022 struct xfs_btree_block *new; /* new (root) btree block */ 3023 int nptr; /* new value for key index, 1 or 2 */ 3024 struct xfs_buf *rbp; /* right buffer pointer */ 3025 struct xfs_btree_block *right; /* right btree block */ 3026 union xfs_btree_ptr rptr; 3027 union xfs_btree_ptr lptr; 3028 3029 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3030 XFS_BTREE_STATS_INC(cur, newroot); 3031 3032 /* initialise our start point from the cursor */ 3033 cur->bc_ops->init_ptr_from_cur(cur, &rptr); 3034 3035 /* Allocate the new block. If we can't do it, we're toast. Give up. */ 3036 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); 3037 if (error) 3038 goto error0; 3039 if (*stat == 0) 3040 goto out0; 3041 XFS_BTREE_STATS_INC(cur, alloc); 3042 3043 /* Set up the new block. */ 3044 error = xfs_btree_get_buf_block(cur, &lptr, 0, &new, &nbp); 3045 if (error) 3046 goto error0; 3047 3048 /* Set the root in the holding structure increasing the level by 1. */ 3049 cur->bc_ops->set_root(cur, &lptr, 1); 3050 3051 /* 3052 * At the previous root level there are now two blocks: the old root, 3053 * and the new block generated when it was split. We don't know which 3054 * one the cursor is pointing at, so we set up variables "left" and 3055 * "right" for each case. 3056 */ 3057 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); 3058 3059 #ifdef DEBUG 3060 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); 3061 if (error) 3062 goto error0; 3063 #endif 3064 3065 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 3066 if (!xfs_btree_ptr_is_null(cur, &rptr)) { 3067 /* Our block is left, pick up the right block. */ 3068 lbp = bp; 3069 xfs_btree_buf_to_ptr(cur, lbp, &lptr); 3070 left = block; 3071 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 3072 if (error) 3073 goto error0; 3074 bp = rbp; 3075 nptr = 1; 3076 } else { 3077 /* Our block is right, pick up the left block. */ 3078 rbp = bp; 3079 xfs_btree_buf_to_ptr(cur, rbp, &rptr); 3080 right = block; 3081 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); 3082 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 3083 if (error) 3084 goto error0; 3085 bp = lbp; 3086 nptr = 2; 3087 } 3088 3089 /* Fill in the new block's btree header and log it. */ 3090 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); 3091 xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS); 3092 ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) && 3093 !xfs_btree_ptr_is_null(cur, &rptr)); 3094 3095 /* Fill in the key data in the new root. */ 3096 if (xfs_btree_get_level(left) > 0) { 3097 /* 3098 * Get the keys for the left block's keys and put them directly 3099 * in the parent block. Do the same for the right block. 3100 */ 3101 xfs_btree_get_node_keys(cur, left, 3102 xfs_btree_key_addr(cur, 1, new)); 3103 xfs_btree_get_node_keys(cur, right, 3104 xfs_btree_key_addr(cur, 2, new)); 3105 } else { 3106 /* 3107 * Get the keys for the left block's records and put them 3108 * directly in the parent block. Do the same for the right 3109 * block. 3110 */ 3111 xfs_btree_get_leaf_keys(cur, left, 3112 xfs_btree_key_addr(cur, 1, new)); 3113 xfs_btree_get_leaf_keys(cur, right, 3114 xfs_btree_key_addr(cur, 2, new)); 3115 } 3116 xfs_btree_log_keys(cur, nbp, 1, 2); 3117 3118 /* Fill in the pointer data in the new root. */ 3119 xfs_btree_copy_ptrs(cur, 3120 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1); 3121 xfs_btree_copy_ptrs(cur, 3122 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1); 3123 xfs_btree_log_ptrs(cur, nbp, 1, 2); 3124 3125 /* Fix up the cursor. */ 3126 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); 3127 cur->bc_ptrs[cur->bc_nlevels] = nptr; 3128 cur->bc_nlevels++; 3129 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3130 *stat = 1; 3131 return 0; 3132 error0: 3133 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3134 return error; 3135 out0: 3136 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3137 *stat = 0; 3138 return 0; 3139 } 3140 3141 STATIC int 3142 xfs_btree_make_block_unfull( 3143 struct xfs_btree_cur *cur, /* btree cursor */ 3144 int level, /* btree level */ 3145 int numrecs,/* # of recs in block */ 3146 int *oindex,/* old tree index */ 3147 int *index, /* new tree index */ 3148 union xfs_btree_ptr *nptr, /* new btree ptr */ 3149 struct xfs_btree_cur **ncur, /* new btree cursor */ 3150 union xfs_btree_key *key, /* key of new block */ 3151 int *stat) 3152 { 3153 int error = 0; 3154 3155 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 3156 level == cur->bc_nlevels - 1) { 3157 struct xfs_inode *ip = cur->bc_private.b.ip; 3158 3159 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { 3160 /* A root block that can be made bigger. */ 3161 xfs_iroot_realloc(ip, 1, cur->bc_private.b.whichfork); 3162 *stat = 1; 3163 } else { 3164 /* A root block that needs replacing */ 3165 int logflags = 0; 3166 3167 error = xfs_btree_new_iroot(cur, &logflags, stat); 3168 if (error || *stat == 0) 3169 return error; 3170 3171 xfs_trans_log_inode(cur->bc_tp, ip, logflags); 3172 } 3173 3174 return 0; 3175 } 3176 3177 /* First, try shifting an entry to the right neighbor. */ 3178 error = xfs_btree_rshift(cur, level, stat); 3179 if (error || *stat) 3180 return error; 3181 3182 /* Next, try shifting an entry to the left neighbor. */ 3183 error = xfs_btree_lshift(cur, level, stat); 3184 if (error) 3185 return error; 3186 3187 if (*stat) { 3188 *oindex = *index = cur->bc_ptrs[level]; 3189 return 0; 3190 } 3191 3192 /* 3193 * Next, try splitting the current block in half. 3194 * 3195 * If this works we have to re-set our variables because we 3196 * could be in a different block now. 3197 */ 3198 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); 3199 if (error || *stat == 0) 3200 return error; 3201 3202 3203 *index = cur->bc_ptrs[level]; 3204 return 0; 3205 } 3206 3207 /* 3208 * Insert one record/level. Return information to the caller 3209 * allowing the next level up to proceed if necessary. 3210 */ 3211 STATIC int 3212 xfs_btree_insrec( 3213 struct xfs_btree_cur *cur, /* btree cursor */ 3214 int level, /* level to insert record at */ 3215 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ 3216 union xfs_btree_rec *rec, /* record to insert */ 3217 union xfs_btree_key *key, /* i/o: block key for ptrp */ 3218 struct xfs_btree_cur **curp, /* output: new cursor replacing cur */ 3219 int *stat) /* success/failure */ 3220 { 3221 struct xfs_btree_block *block; /* btree block */ 3222 struct xfs_buf *bp; /* buffer for block */ 3223 union xfs_btree_ptr nptr; /* new block ptr */ 3224 struct xfs_btree_cur *ncur; /* new btree cursor */ 3225 union xfs_btree_bigkey nkey; /* new block key */ 3226 union xfs_btree_key *lkey; 3227 int optr; /* old key/record index */ 3228 int ptr; /* key/record index */ 3229 int numrecs;/* number of records */ 3230 int error; /* error return value */ 3231 #ifdef DEBUG 3232 int i; 3233 #endif 3234 xfs_daddr_t old_bn; 3235 3236 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3237 XFS_BTREE_TRACE_ARGIPR(cur, level, *ptrp, &rec); 3238 3239 ncur = NULL; 3240 lkey = (union xfs_btree_key *)&nkey; 3241 3242 /* 3243 * If we have an external root pointer, and we've made it to the 3244 * root level, allocate a new root block and we're done. 3245 */ 3246 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 3247 (level >= cur->bc_nlevels)) { 3248 error = xfs_btree_new_root(cur, stat); 3249 xfs_btree_set_ptr_null(cur, ptrp); 3250 3251 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3252 return error; 3253 } 3254 3255 /* If we're off the left edge, return failure. */ 3256 ptr = cur->bc_ptrs[level]; 3257 if (ptr == 0) { 3258 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3259 *stat = 0; 3260 return 0; 3261 } 3262 3263 optr = ptr; 3264 3265 XFS_BTREE_STATS_INC(cur, insrec); 3266 3267 /* Get pointers to the btree buffer and block. */ 3268 block = xfs_btree_get_block(cur, level, &bp); 3269 old_bn = bp ? bp->b_bn : XFS_BUF_DADDR_NULL; 3270 numrecs = xfs_btree_get_numrecs(block); 3271 3272 #ifdef DEBUG 3273 error = xfs_btree_check_block(cur, block, level, bp); 3274 if (error) 3275 goto error0; 3276 3277 /* Check that the new entry is being inserted in the right place. */ 3278 if (ptr <= numrecs) { 3279 if (level == 0) { 3280 ASSERT(cur->bc_ops->recs_inorder(cur, rec, 3281 xfs_btree_rec_addr(cur, ptr, block))); 3282 } else { 3283 ASSERT(cur->bc_ops->keys_inorder(cur, key, 3284 xfs_btree_key_addr(cur, ptr, block))); 3285 } 3286 } 3287 #endif 3288 3289 /* 3290 * If the block is full, we can't insert the new entry until we 3291 * make the block un-full. 3292 */ 3293 xfs_btree_set_ptr_null(cur, &nptr); 3294 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { 3295 error = xfs_btree_make_block_unfull(cur, level, numrecs, 3296 &optr, &ptr, &nptr, &ncur, lkey, stat); 3297 if (error || *stat == 0) 3298 goto error0; 3299 } 3300 3301 /* 3302 * The current block may have changed if the block was 3303 * previously full and we have just made space in it. 3304 */ 3305 block = xfs_btree_get_block(cur, level, &bp); 3306 numrecs = xfs_btree_get_numrecs(block); 3307 3308 #ifdef DEBUG 3309 error = xfs_btree_check_block(cur, block, level, bp); 3310 if (error) 3311 return error; 3312 #endif 3313 3314 /* 3315 * At this point we know there's room for our new entry in the block 3316 * we're pointing at. 3317 */ 3318 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); 3319 3320 if (level > 0) { 3321 /* It's a nonleaf. make a hole in the keys and ptrs */ 3322 union xfs_btree_key *kp; 3323 union xfs_btree_ptr *pp; 3324 3325 kp = xfs_btree_key_addr(cur, ptr, block); 3326 pp = xfs_btree_ptr_addr(cur, ptr, block); 3327 3328 #ifdef DEBUG 3329 for (i = numrecs - ptr; i >= 0; i--) { 3330 error = xfs_btree_check_ptr(cur, pp, i, level); 3331 if (error) 3332 return error; 3333 } 3334 #endif 3335 3336 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); 3337 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); 3338 3339 #ifdef DEBUG 3340 error = xfs_btree_check_ptr(cur, ptrp, 0, level); 3341 if (error) 3342 goto error0; 3343 #endif 3344 3345 /* Now put the new data in, bump numrecs and log it. */ 3346 xfs_btree_copy_keys(cur, kp, key, 1); 3347 xfs_btree_copy_ptrs(cur, pp, ptrp, 1); 3348 numrecs++; 3349 xfs_btree_set_numrecs(block, numrecs); 3350 xfs_btree_log_ptrs(cur, bp, ptr, numrecs); 3351 xfs_btree_log_keys(cur, bp, ptr, numrecs); 3352 #ifdef DEBUG 3353 if (ptr < numrecs) { 3354 ASSERT(cur->bc_ops->keys_inorder(cur, kp, 3355 xfs_btree_key_addr(cur, ptr + 1, block))); 3356 } 3357 #endif 3358 } else { 3359 /* It's a leaf. make a hole in the records */ 3360 union xfs_btree_rec *rp; 3361 3362 rp = xfs_btree_rec_addr(cur, ptr, block); 3363 3364 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); 3365 3366 /* Now put the new data in, bump numrecs and log it. */ 3367 xfs_btree_copy_recs(cur, rp, rec, 1); 3368 xfs_btree_set_numrecs(block, ++numrecs); 3369 xfs_btree_log_recs(cur, bp, ptr, numrecs); 3370 #ifdef DEBUG 3371 if (ptr < numrecs) { 3372 ASSERT(cur->bc_ops->recs_inorder(cur, rp, 3373 xfs_btree_rec_addr(cur, ptr + 1, block))); 3374 } 3375 #endif 3376 } 3377 3378 /* Log the new number of records in the btree header. */ 3379 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS); 3380 3381 /* 3382 * If we just inserted into a new tree block, we have to 3383 * recalculate nkey here because nkey is out of date. 3384 * 3385 * Otherwise we're just updating an existing block (having shoved 3386 * some records into the new tree block), so use the regular key 3387 * update mechanism. 3388 */ 3389 if (bp && bp->b_bn != old_bn) { 3390 xfs_btree_get_keys(cur, block, lkey); 3391 } else if (xfs_btree_needs_key_update(cur, optr)) { 3392 error = xfs_btree_update_keys(cur, level); 3393 if (error) 3394 goto error0; 3395 } 3396 3397 /* 3398 * If we are tracking the last record in the tree and 3399 * we are at the far right edge of the tree, update it. 3400 */ 3401 if (xfs_btree_is_lastrec(cur, block, level)) { 3402 cur->bc_ops->update_lastrec(cur, block, rec, 3403 ptr, LASTREC_INSREC); 3404 } 3405 3406 /* 3407 * Return the new block number, if any. 3408 * If there is one, give back a record value and a cursor too. 3409 */ 3410 *ptrp = nptr; 3411 if (!xfs_btree_ptr_is_null(cur, &nptr)) { 3412 xfs_btree_copy_keys(cur, key, lkey, 1); 3413 *curp = ncur; 3414 } 3415 3416 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3417 *stat = 1; 3418 return 0; 3419 3420 error0: 3421 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3422 return error; 3423 } 3424 3425 /* 3426 * Insert the record at the point referenced by cur. 3427 * 3428 * A multi-level split of the tree on insert will invalidate the original 3429 * cursor. All callers of this function should assume that the cursor is 3430 * no longer valid and revalidate it. 3431 */ 3432 int 3433 xfs_btree_insert( 3434 struct xfs_btree_cur *cur, 3435 int *stat) 3436 { 3437 int error; /* error return value */ 3438 int i; /* result value, 0 for failure */ 3439 int level; /* current level number in btree */ 3440 union xfs_btree_ptr nptr; /* new block number (split result) */ 3441 struct xfs_btree_cur *ncur; /* new cursor (split result) */ 3442 struct xfs_btree_cur *pcur; /* previous level's cursor */ 3443 union xfs_btree_bigkey bkey; /* key of block to insert */ 3444 union xfs_btree_key *key; 3445 union xfs_btree_rec rec; /* record to insert */ 3446 3447 level = 0; 3448 ncur = NULL; 3449 pcur = cur; 3450 key = (union xfs_btree_key *)&bkey; 3451 3452 xfs_btree_set_ptr_null(cur, &nptr); 3453 3454 /* Make a key out of the record data to be inserted, and save it. */ 3455 cur->bc_ops->init_rec_from_cur(cur, &rec); 3456 cur->bc_ops->init_key_from_rec(key, &rec); 3457 3458 /* 3459 * Loop going up the tree, starting at the leaf level. 3460 * Stop when we don't get a split block, that must mean that 3461 * the insert is finished with this level. 3462 */ 3463 do { 3464 /* 3465 * Insert nrec/nptr into this level of the tree. 3466 * Note if we fail, nptr will be null. 3467 */ 3468 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, 3469 &ncur, &i); 3470 if (error) { 3471 if (pcur != cur) 3472 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR); 3473 goto error0; 3474 } 3475 3476 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3477 level++; 3478 3479 /* 3480 * See if the cursor we just used is trash. 3481 * Can't trash the caller's cursor, but otherwise we should 3482 * if ncur is a new cursor or we're about to be done. 3483 */ 3484 if (pcur != cur && 3485 (ncur || xfs_btree_ptr_is_null(cur, &nptr))) { 3486 /* Save the state from the cursor before we trash it */ 3487 if (cur->bc_ops->update_cursor) 3488 cur->bc_ops->update_cursor(pcur, cur); 3489 cur->bc_nlevels = pcur->bc_nlevels; 3490 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR); 3491 } 3492 /* If we got a new cursor, switch to it. */ 3493 if (ncur) { 3494 pcur = ncur; 3495 ncur = NULL; 3496 } 3497 } while (!xfs_btree_ptr_is_null(cur, &nptr)); 3498 3499 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3500 *stat = i; 3501 return 0; 3502 error0: 3503 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3504 return error; 3505 } 3506 3507 /* 3508 * Try to merge a non-leaf block back into the inode root. 3509 * 3510 * Note: the killroot names comes from the fact that we're effectively 3511 * killing the old root block. But because we can't just delete the 3512 * inode we have to copy the single block it was pointing to into the 3513 * inode. 3514 */ 3515 STATIC int 3516 xfs_btree_kill_iroot( 3517 struct xfs_btree_cur *cur) 3518 { 3519 int whichfork = cur->bc_private.b.whichfork; 3520 struct xfs_inode *ip = cur->bc_private.b.ip; 3521 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork); 3522 struct xfs_btree_block *block; 3523 struct xfs_btree_block *cblock; 3524 union xfs_btree_key *kp; 3525 union xfs_btree_key *ckp; 3526 union xfs_btree_ptr *pp; 3527 union xfs_btree_ptr *cpp; 3528 struct xfs_buf *cbp; 3529 int level; 3530 int index; 3531 int numrecs; 3532 int error; 3533 #ifdef DEBUG 3534 union xfs_btree_ptr ptr; 3535 int i; 3536 #endif 3537 3538 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3539 3540 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 3541 ASSERT(cur->bc_nlevels > 1); 3542 3543 /* 3544 * Don't deal with the root block needs to be a leaf case. 3545 * We're just going to turn the thing back into extents anyway. 3546 */ 3547 level = cur->bc_nlevels - 1; 3548 if (level == 1) 3549 goto out0; 3550 3551 /* 3552 * Give up if the root has multiple children. 3553 */ 3554 block = xfs_btree_get_iroot(cur); 3555 if (xfs_btree_get_numrecs(block) != 1) 3556 goto out0; 3557 3558 cblock = xfs_btree_get_block(cur, level - 1, &cbp); 3559 numrecs = xfs_btree_get_numrecs(cblock); 3560 3561 /* 3562 * Only do this if the next level will fit. 3563 * Then the data must be copied up to the inode, 3564 * instead of freeing the root you free the next level. 3565 */ 3566 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) 3567 goto out0; 3568 3569 XFS_BTREE_STATS_INC(cur, killroot); 3570 3571 #ifdef DEBUG 3572 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); 3573 ASSERT(xfs_btree_ptr_is_null(cur, &ptr)); 3574 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); 3575 ASSERT(xfs_btree_ptr_is_null(cur, &ptr)); 3576 #endif 3577 3578 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); 3579 if (index) { 3580 xfs_iroot_realloc(cur->bc_private.b.ip, index, 3581 cur->bc_private.b.whichfork); 3582 block = ifp->if_broot; 3583 } 3584 3585 be16_add_cpu(&block->bb_numrecs, index); 3586 ASSERT(block->bb_numrecs == cblock->bb_numrecs); 3587 3588 kp = xfs_btree_key_addr(cur, 1, block); 3589 ckp = xfs_btree_key_addr(cur, 1, cblock); 3590 xfs_btree_copy_keys(cur, kp, ckp, numrecs); 3591 3592 pp = xfs_btree_ptr_addr(cur, 1, block); 3593 cpp = xfs_btree_ptr_addr(cur, 1, cblock); 3594 #ifdef DEBUG 3595 for (i = 0; i < numrecs; i++) { 3596 error = xfs_btree_check_ptr(cur, cpp, i, level - 1); 3597 if (error) { 3598 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3599 return error; 3600 } 3601 } 3602 #endif 3603 xfs_btree_copy_ptrs(cur, pp, cpp, numrecs); 3604 3605 error = xfs_btree_free_block(cur, cbp); 3606 if (error) { 3607 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3608 return error; 3609 } 3610 3611 cur->bc_bufs[level - 1] = NULL; 3612 be16_add_cpu(&block->bb_level, -1); 3613 xfs_trans_log_inode(cur->bc_tp, ip, 3614 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork)); 3615 cur->bc_nlevels--; 3616 out0: 3617 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3618 return 0; 3619 } 3620 3621 /* 3622 * Kill the current root node, and replace it with it's only child node. 3623 */ 3624 STATIC int 3625 xfs_btree_kill_root( 3626 struct xfs_btree_cur *cur, 3627 struct xfs_buf *bp, 3628 int level, 3629 union xfs_btree_ptr *newroot) 3630 { 3631 int error; 3632 3633 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3634 XFS_BTREE_STATS_INC(cur, killroot); 3635 3636 /* 3637 * Update the root pointer, decreasing the level by 1 and then 3638 * free the old root. 3639 */ 3640 cur->bc_ops->set_root(cur, newroot, -1); 3641 3642 error = xfs_btree_free_block(cur, bp); 3643 if (error) { 3644 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 3645 return error; 3646 } 3647 3648 cur->bc_bufs[level] = NULL; 3649 cur->bc_ra[level] = 0; 3650 cur->bc_nlevels--; 3651 3652 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3653 return 0; 3654 } 3655 3656 STATIC int 3657 xfs_btree_dec_cursor( 3658 struct xfs_btree_cur *cur, 3659 int level, 3660 int *stat) 3661 { 3662 int error; 3663 int i; 3664 3665 if (level > 0) { 3666 error = xfs_btree_decrement(cur, level, &i); 3667 if (error) 3668 return error; 3669 } 3670 3671 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3672 *stat = 1; 3673 return 0; 3674 } 3675 3676 /* 3677 * Single level of the btree record deletion routine. 3678 * Delete record pointed to by cur/level. 3679 * Remove the record from its block then rebalance the tree. 3680 * Return 0 for error, 1 for done, 2 to go on to the next level. 3681 */ 3682 STATIC int /* error */ 3683 xfs_btree_delrec( 3684 struct xfs_btree_cur *cur, /* btree cursor */ 3685 int level, /* level removing record from */ 3686 int *stat) /* fail/done/go-on */ 3687 { 3688 struct xfs_btree_block *block; /* btree block */ 3689 union xfs_btree_ptr cptr; /* current block ptr */ 3690 struct xfs_buf *bp; /* buffer for block */ 3691 int error; /* error return value */ 3692 int i; /* loop counter */ 3693 union xfs_btree_ptr lptr; /* left sibling block ptr */ 3694 struct xfs_buf *lbp; /* left buffer pointer */ 3695 struct xfs_btree_block *left; /* left btree block */ 3696 int lrecs = 0; /* left record count */ 3697 int ptr; /* key/record index */ 3698 union xfs_btree_ptr rptr; /* right sibling block ptr */ 3699 struct xfs_buf *rbp; /* right buffer pointer */ 3700 struct xfs_btree_block *right; /* right btree block */ 3701 struct xfs_btree_block *rrblock; /* right-right btree block */ 3702 struct xfs_buf *rrbp; /* right-right buffer pointer */ 3703 int rrecs = 0; /* right record count */ 3704 struct xfs_btree_cur *tcur; /* temporary btree cursor */ 3705 int numrecs; /* temporary numrec count */ 3706 3707 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 3708 XFS_BTREE_TRACE_ARGI(cur, level); 3709 3710 tcur = NULL; 3711 3712 /* Get the index of the entry being deleted, check for nothing there. */ 3713 ptr = cur->bc_ptrs[level]; 3714 if (ptr == 0) { 3715 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3716 *stat = 0; 3717 return 0; 3718 } 3719 3720 /* Get the buffer & block containing the record or key/ptr. */ 3721 block = xfs_btree_get_block(cur, level, &bp); 3722 numrecs = xfs_btree_get_numrecs(block); 3723 3724 #ifdef DEBUG 3725 error = xfs_btree_check_block(cur, block, level, bp); 3726 if (error) 3727 goto error0; 3728 #endif 3729 3730 /* Fail if we're off the end of the block. */ 3731 if (ptr > numrecs) { 3732 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3733 *stat = 0; 3734 return 0; 3735 } 3736 3737 XFS_BTREE_STATS_INC(cur, delrec); 3738 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); 3739 3740 /* Excise the entries being deleted. */ 3741 if (level > 0) { 3742 /* It's a nonleaf. operate on keys and ptrs */ 3743 union xfs_btree_key *lkp; 3744 union xfs_btree_ptr *lpp; 3745 3746 lkp = xfs_btree_key_addr(cur, ptr + 1, block); 3747 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); 3748 3749 #ifdef DEBUG 3750 for (i = 0; i < numrecs - ptr; i++) { 3751 error = xfs_btree_check_ptr(cur, lpp, i, level); 3752 if (error) 3753 goto error0; 3754 } 3755 #endif 3756 3757 if (ptr < numrecs) { 3758 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); 3759 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); 3760 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); 3761 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); 3762 } 3763 } else { 3764 /* It's a leaf. operate on records */ 3765 if (ptr < numrecs) { 3766 xfs_btree_shift_recs(cur, 3767 xfs_btree_rec_addr(cur, ptr + 1, block), 3768 -1, numrecs - ptr); 3769 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); 3770 } 3771 } 3772 3773 /* 3774 * Decrement and log the number of entries in the block. 3775 */ 3776 xfs_btree_set_numrecs(block, --numrecs); 3777 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS); 3778 3779 /* 3780 * If we are tracking the last record in the tree and 3781 * we are at the far right edge of the tree, update it. 3782 */ 3783 if (xfs_btree_is_lastrec(cur, block, level)) { 3784 cur->bc_ops->update_lastrec(cur, block, NULL, 3785 ptr, LASTREC_DELREC); 3786 } 3787 3788 /* 3789 * We're at the root level. First, shrink the root block in-memory. 3790 * Try to get rid of the next level down. If we can't then there's 3791 * nothing left to do. 3792 */ 3793 if (level == cur->bc_nlevels - 1) { 3794 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { 3795 xfs_iroot_realloc(cur->bc_private.b.ip, -1, 3796 cur->bc_private.b.whichfork); 3797 3798 error = xfs_btree_kill_iroot(cur); 3799 if (error) 3800 goto error0; 3801 3802 error = xfs_btree_dec_cursor(cur, level, stat); 3803 if (error) 3804 goto error0; 3805 *stat = 1; 3806 return 0; 3807 } 3808 3809 /* 3810 * If this is the root level, and there's only one entry left, 3811 * and it's NOT the leaf level, then we can get rid of this 3812 * level. 3813 */ 3814 if (numrecs == 1 && level > 0) { 3815 union xfs_btree_ptr *pp; 3816 /* 3817 * pp is still set to the first pointer in the block. 3818 * Make it the new root of the btree. 3819 */ 3820 pp = xfs_btree_ptr_addr(cur, 1, block); 3821 error = xfs_btree_kill_root(cur, bp, level, pp); 3822 if (error) 3823 goto error0; 3824 } else if (level > 0) { 3825 error = xfs_btree_dec_cursor(cur, level, stat); 3826 if (error) 3827 goto error0; 3828 } 3829 *stat = 1; 3830 return 0; 3831 } 3832 3833 /* 3834 * If we deleted the leftmost entry in the block, update the 3835 * key values above us in the tree. 3836 */ 3837 if (xfs_btree_needs_key_update(cur, ptr)) { 3838 error = xfs_btree_update_keys(cur, level); 3839 if (error) 3840 goto error0; 3841 } 3842 3843 /* 3844 * If the number of records remaining in the block is at least 3845 * the minimum, we're done. 3846 */ 3847 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { 3848 error = xfs_btree_dec_cursor(cur, level, stat); 3849 if (error) 3850 goto error0; 3851 return 0; 3852 } 3853 3854 /* 3855 * Otherwise, we have to move some records around to keep the 3856 * tree balanced. Look at the left and right sibling blocks to 3857 * see if we can re-balance by moving only one record. 3858 */ 3859 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 3860 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); 3861 3862 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { 3863 /* 3864 * One child of root, need to get a chance to copy its contents 3865 * into the root and delete it. Can't go up to next level, 3866 * there's nothing to delete there. 3867 */ 3868 if (xfs_btree_ptr_is_null(cur, &rptr) && 3869 xfs_btree_ptr_is_null(cur, &lptr) && 3870 level == cur->bc_nlevels - 2) { 3871 error = xfs_btree_kill_iroot(cur); 3872 if (!error) 3873 error = xfs_btree_dec_cursor(cur, level, stat); 3874 if (error) 3875 goto error0; 3876 return 0; 3877 } 3878 } 3879 3880 ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) || 3881 !xfs_btree_ptr_is_null(cur, &lptr)); 3882 3883 /* 3884 * Duplicate the cursor so our btree manipulations here won't 3885 * disrupt the next level up. 3886 */ 3887 error = xfs_btree_dup_cursor(cur, &tcur); 3888 if (error) 3889 goto error0; 3890 3891 /* 3892 * If there's a right sibling, see if it's ok to shift an entry 3893 * out of it. 3894 */ 3895 if (!xfs_btree_ptr_is_null(cur, &rptr)) { 3896 /* 3897 * Move the temp cursor to the last entry in the next block. 3898 * Actually any entry but the first would suffice. 3899 */ 3900 i = xfs_btree_lastrec(tcur, level); 3901 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3902 3903 error = xfs_btree_increment(tcur, level, &i); 3904 if (error) 3905 goto error0; 3906 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3907 3908 i = xfs_btree_lastrec(tcur, level); 3909 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3910 3911 /* Grab a pointer to the block. */ 3912 right = xfs_btree_get_block(tcur, level, &rbp); 3913 #ifdef DEBUG 3914 error = xfs_btree_check_block(tcur, right, level, rbp); 3915 if (error) 3916 goto error0; 3917 #endif 3918 /* Grab the current block number, for future use. */ 3919 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB); 3920 3921 /* 3922 * If right block is full enough so that removing one entry 3923 * won't make it too empty, and left-shifting an entry out 3924 * of right to us works, we're done. 3925 */ 3926 if (xfs_btree_get_numrecs(right) - 1 >= 3927 cur->bc_ops->get_minrecs(tcur, level)) { 3928 error = xfs_btree_lshift(tcur, level, &i); 3929 if (error) 3930 goto error0; 3931 if (i) { 3932 ASSERT(xfs_btree_get_numrecs(block) >= 3933 cur->bc_ops->get_minrecs(tcur, level)); 3934 3935 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 3936 tcur = NULL; 3937 3938 error = xfs_btree_dec_cursor(cur, level, stat); 3939 if (error) 3940 goto error0; 3941 return 0; 3942 } 3943 } 3944 3945 /* 3946 * Otherwise, grab the number of records in right for 3947 * future reference, and fix up the temp cursor to point 3948 * to our block again (last record). 3949 */ 3950 rrecs = xfs_btree_get_numrecs(right); 3951 if (!xfs_btree_ptr_is_null(cur, &lptr)) { 3952 i = xfs_btree_firstrec(tcur, level); 3953 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3954 3955 error = xfs_btree_decrement(tcur, level, &i); 3956 if (error) 3957 goto error0; 3958 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3959 } 3960 } 3961 3962 /* 3963 * If there's a left sibling, see if it's ok to shift an entry 3964 * out of it. 3965 */ 3966 if (!xfs_btree_ptr_is_null(cur, &lptr)) { 3967 /* 3968 * Move the temp cursor to the first entry in the 3969 * previous block. 3970 */ 3971 i = xfs_btree_firstrec(tcur, level); 3972 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3973 3974 error = xfs_btree_decrement(tcur, level, &i); 3975 if (error) 3976 goto error0; 3977 i = xfs_btree_firstrec(tcur, level); 3978 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, error0); 3979 3980 /* Grab a pointer to the block. */ 3981 left = xfs_btree_get_block(tcur, level, &lbp); 3982 #ifdef DEBUG 3983 error = xfs_btree_check_block(cur, left, level, lbp); 3984 if (error) 3985 goto error0; 3986 #endif 3987 /* Grab the current block number, for future use. */ 3988 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB); 3989 3990 /* 3991 * If left block is full enough so that removing one entry 3992 * won't make it too empty, and right-shifting an entry out 3993 * of left to us works, we're done. 3994 */ 3995 if (xfs_btree_get_numrecs(left) - 1 >= 3996 cur->bc_ops->get_minrecs(tcur, level)) { 3997 error = xfs_btree_rshift(tcur, level, &i); 3998 if (error) 3999 goto error0; 4000 if (i) { 4001 ASSERT(xfs_btree_get_numrecs(block) >= 4002 cur->bc_ops->get_minrecs(tcur, level)); 4003 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 4004 tcur = NULL; 4005 if (level == 0) 4006 cur->bc_ptrs[0]++; 4007 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4008 *stat = 1; 4009 return 0; 4010 } 4011 } 4012 4013 /* 4014 * Otherwise, grab the number of records in right for 4015 * future reference. 4016 */ 4017 lrecs = xfs_btree_get_numrecs(left); 4018 } 4019 4020 /* Delete the temp cursor, we're done with it. */ 4021 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 4022 tcur = NULL; 4023 4024 /* If here, we need to do a join to keep the tree balanced. */ 4025 ASSERT(!xfs_btree_ptr_is_null(cur, &cptr)); 4026 4027 if (!xfs_btree_ptr_is_null(cur, &lptr) && 4028 lrecs + xfs_btree_get_numrecs(block) <= 4029 cur->bc_ops->get_maxrecs(cur, level)) { 4030 /* 4031 * Set "right" to be the starting block, 4032 * "left" to be the left neighbor. 4033 */ 4034 rptr = cptr; 4035 right = block; 4036 rbp = bp; 4037 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); 4038 if (error) 4039 goto error0; 4040 4041 /* 4042 * If that won't work, see if we can join with the right neighbor block. 4043 */ 4044 } else if (!xfs_btree_ptr_is_null(cur, &rptr) && 4045 rrecs + xfs_btree_get_numrecs(block) <= 4046 cur->bc_ops->get_maxrecs(cur, level)) { 4047 /* 4048 * Set "left" to be the starting block, 4049 * "right" to be the right neighbor. 4050 */ 4051 lptr = cptr; 4052 left = block; 4053 lbp = bp; 4054 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp); 4055 if (error) 4056 goto error0; 4057 4058 /* 4059 * Otherwise, we can't fix the imbalance. 4060 * Just return. This is probably a logic error, but it's not fatal. 4061 */ 4062 } else { 4063 error = xfs_btree_dec_cursor(cur, level, stat); 4064 if (error) 4065 goto error0; 4066 return 0; 4067 } 4068 4069 rrecs = xfs_btree_get_numrecs(right); 4070 lrecs = xfs_btree_get_numrecs(left); 4071 4072 /* 4073 * We're now going to join "left" and "right" by moving all the stuff 4074 * in "right" to "left" and deleting "right". 4075 */ 4076 XFS_BTREE_STATS_ADD(cur, moves, rrecs); 4077 if (level > 0) { 4078 /* It's a non-leaf. Move keys and pointers. */ 4079 union xfs_btree_key *lkp; /* left btree key */ 4080 union xfs_btree_ptr *lpp; /* left address pointer */ 4081 union xfs_btree_key *rkp; /* right btree key */ 4082 union xfs_btree_ptr *rpp; /* right address pointer */ 4083 4084 lkp = xfs_btree_key_addr(cur, lrecs + 1, left); 4085 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left); 4086 rkp = xfs_btree_key_addr(cur, 1, right); 4087 rpp = xfs_btree_ptr_addr(cur, 1, right); 4088 #ifdef DEBUG 4089 for (i = 1; i < rrecs; i++) { 4090 error = xfs_btree_check_ptr(cur, rpp, i, level); 4091 if (error) 4092 goto error0; 4093 } 4094 #endif 4095 xfs_btree_copy_keys(cur, lkp, rkp, rrecs); 4096 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs); 4097 4098 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs); 4099 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs); 4100 } else { 4101 /* It's a leaf. Move records. */ 4102 union xfs_btree_rec *lrp; /* left record pointer */ 4103 union xfs_btree_rec *rrp; /* right record pointer */ 4104 4105 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left); 4106 rrp = xfs_btree_rec_addr(cur, 1, right); 4107 4108 xfs_btree_copy_recs(cur, lrp, rrp, rrecs); 4109 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs); 4110 } 4111 4112 XFS_BTREE_STATS_INC(cur, join); 4113 4114 /* 4115 * Fix up the number of records and right block pointer in the 4116 * surviving block, and log it. 4117 */ 4118 xfs_btree_set_numrecs(left, lrecs + rrecs); 4119 xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB), 4120 xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB); 4121 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 4122 4123 /* If there is a right sibling, point it to the remaining block. */ 4124 xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB); 4125 if (!xfs_btree_ptr_is_null(cur, &cptr)) { 4126 error = xfs_btree_read_buf_block(cur, &cptr, 0, &rrblock, &rrbp); 4127 if (error) 4128 goto error0; 4129 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB); 4130 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB); 4131 } 4132 4133 /* Free the deleted block. */ 4134 error = xfs_btree_free_block(cur, rbp); 4135 if (error) 4136 goto error0; 4137 4138 /* 4139 * If we joined with the left neighbor, set the buffer in the 4140 * cursor to the left block, and fix up the index. 4141 */ 4142 if (bp != lbp) { 4143 cur->bc_bufs[level] = lbp; 4144 cur->bc_ptrs[level] += lrecs; 4145 cur->bc_ra[level] = 0; 4146 } 4147 /* 4148 * If we joined with the right neighbor and there's a level above 4149 * us, increment the cursor at that level. 4150 */ 4151 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || 4152 (level + 1 < cur->bc_nlevels)) { 4153 error = xfs_btree_increment(cur, level + 1, &i); 4154 if (error) 4155 goto error0; 4156 } 4157 4158 /* 4159 * Readjust the ptr at this level if it's not a leaf, since it's 4160 * still pointing at the deletion point, which makes the cursor 4161 * inconsistent. If this makes the ptr 0, the caller fixes it up. 4162 * We can't use decrement because it would change the next level up. 4163 */ 4164 if (level > 0) 4165 cur->bc_ptrs[level]--; 4166 4167 /* 4168 * We combined blocks, so we have to update the parent keys if the 4169 * btree supports overlapped intervals. However, bc_ptrs[level + 1] 4170 * points to the old block so that the caller knows which record to 4171 * delete. Therefore, the caller must be savvy enough to call updkeys 4172 * for us if we return stat == 2. The other exit points from this 4173 * function don't require deletions further up the tree, so they can 4174 * call updkeys directly. 4175 */ 4176 4177 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4178 /* Return value means the next level up has something to do. */ 4179 *stat = 2; 4180 return 0; 4181 4182 error0: 4183 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 4184 if (tcur) 4185 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 4186 return error; 4187 } 4188 4189 /* 4190 * Delete the record pointed to by cur. 4191 * The cursor refers to the place where the record was (could be inserted) 4192 * when the operation returns. 4193 */ 4194 int /* error */ 4195 xfs_btree_delete( 4196 struct xfs_btree_cur *cur, 4197 int *stat) /* success/failure */ 4198 { 4199 int error; /* error return value */ 4200 int level; 4201 int i; 4202 bool joined = false; 4203 4204 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 4205 4206 /* 4207 * Go up the tree, starting at leaf level. 4208 * 4209 * If 2 is returned then a join was done; go to the next level. 4210 * Otherwise we are done. 4211 */ 4212 for (level = 0, i = 2; i == 2; level++) { 4213 error = xfs_btree_delrec(cur, level, &i); 4214 if (error) 4215 goto error0; 4216 if (i == 2) 4217 joined = true; 4218 } 4219 4220 /* 4221 * If we combined blocks as part of deleting the record, delrec won't 4222 * have updated the parent high keys so we have to do that here. 4223 */ 4224 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { 4225 error = xfs_btree_updkeys_force(cur, 0); 4226 if (error) 4227 goto error0; 4228 } 4229 4230 if (i == 0) { 4231 for (level = 1; level < cur->bc_nlevels; level++) { 4232 if (cur->bc_ptrs[level] == 0) { 4233 error = xfs_btree_decrement(cur, level, &i); 4234 if (error) 4235 goto error0; 4236 break; 4237 } 4238 } 4239 } 4240 4241 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 4242 *stat = i; 4243 return 0; 4244 error0: 4245 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 4246 return error; 4247 } 4248 4249 /* 4250 * Get the data from the pointed-to record. 4251 */ 4252 int /* error */ 4253 xfs_btree_get_rec( 4254 struct xfs_btree_cur *cur, /* btree cursor */ 4255 union xfs_btree_rec **recp, /* output: btree record */ 4256 int *stat) /* output: success/failure */ 4257 { 4258 struct xfs_btree_block *block; /* btree block */ 4259 struct xfs_buf *bp; /* buffer pointer */ 4260 int ptr; /* record number */ 4261 #ifdef DEBUG 4262 int error; /* error return value */ 4263 #endif 4264 4265 ptr = cur->bc_ptrs[0]; 4266 block = xfs_btree_get_block(cur, 0, &bp); 4267 4268 #ifdef DEBUG 4269 error = xfs_btree_check_block(cur, block, 0, bp); 4270 if (error) 4271 return error; 4272 #endif 4273 4274 /* 4275 * Off the right end or left end, return failure. 4276 */ 4277 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { 4278 *stat = 0; 4279 return 0; 4280 } 4281 4282 /* 4283 * Point to the record and extract its data. 4284 */ 4285 *recp = xfs_btree_rec_addr(cur, ptr, block); 4286 *stat = 1; 4287 return 0; 4288 } 4289 4290 /* Visit a block in a btree. */ 4291 STATIC int 4292 xfs_btree_visit_block( 4293 struct xfs_btree_cur *cur, 4294 int level, 4295 xfs_btree_visit_blocks_fn fn, 4296 void *data) 4297 { 4298 struct xfs_btree_block *block; 4299 struct xfs_buf *bp; 4300 union xfs_btree_ptr rptr; 4301 int error; 4302 4303 /* do right sibling readahead */ 4304 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); 4305 block = xfs_btree_get_block(cur, level, &bp); 4306 4307 /* process the block */ 4308 error = fn(cur, level, data); 4309 if (error) 4310 return error; 4311 4312 /* now read rh sibling block for next iteration */ 4313 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); 4314 if (xfs_btree_ptr_is_null(cur, &rptr)) 4315 return -ENOENT; 4316 4317 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); 4318 } 4319 4320 4321 /* Visit every block in a btree. */ 4322 int 4323 xfs_btree_visit_blocks( 4324 struct xfs_btree_cur *cur, 4325 xfs_btree_visit_blocks_fn fn, 4326 void *data) 4327 { 4328 union xfs_btree_ptr lptr; 4329 int level; 4330 struct xfs_btree_block *block = NULL; 4331 int error = 0; 4332 4333 cur->bc_ops->init_ptr_from_cur(cur, &lptr); 4334 4335 /* for each level */ 4336 for (level = cur->bc_nlevels - 1; level >= 0; level--) { 4337 /* grab the left hand block */ 4338 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); 4339 if (error) 4340 return error; 4341 4342 /* readahead the left most block for the next level down */ 4343 if (level > 0) { 4344 union xfs_btree_ptr *ptr; 4345 4346 ptr = xfs_btree_ptr_addr(cur, 1, block); 4347 xfs_btree_readahead_ptr(cur, ptr, 1); 4348 4349 /* save for the next iteration of the loop */ 4350 lptr = *ptr; 4351 } 4352 4353 /* for each buffer in the level */ 4354 do { 4355 error = xfs_btree_visit_block(cur, level, fn, data); 4356 } while (!error); 4357 4358 if (error != -ENOENT) 4359 return error; 4360 } 4361 4362 return 0; 4363 } 4364 4365 /* 4366 * Change the owner of a btree. 4367 * 4368 * The mechanism we use here is ordered buffer logging. Because we don't know 4369 * how many buffers were are going to need to modify, we don't really want to 4370 * have to make transaction reservations for the worst case of every buffer in a 4371 * full size btree as that may be more space that we can fit in the log.... 4372 * 4373 * We do the btree walk in the most optimal manner possible - we have sibling 4374 * pointers so we can just walk all the blocks on each level from left to right 4375 * in a single pass, and then move to the next level and do the same. We can 4376 * also do readahead on the sibling pointers to get IO moving more quickly, 4377 * though for slow disks this is unlikely to make much difference to performance 4378 * as the amount of CPU work we have to do before moving to the next block is 4379 * relatively small. 4380 * 4381 * For each btree block that we load, modify the owner appropriately, set the 4382 * buffer as an ordered buffer and log it appropriately. We need to ensure that 4383 * we mark the region we change dirty so that if the buffer is relogged in 4384 * a subsequent transaction the changes we make here as an ordered buffer are 4385 * correctly relogged in that transaction. If we are in recovery context, then 4386 * just queue the modified buffer as delayed write buffer so the transaction 4387 * recovery completion writes the changes to disk. 4388 */ 4389 struct xfs_btree_block_change_owner_info { 4390 __uint64_t new_owner; 4391 struct list_head *buffer_list; 4392 }; 4393 4394 static int 4395 xfs_btree_block_change_owner( 4396 struct xfs_btree_cur *cur, 4397 int level, 4398 void *data) 4399 { 4400 struct xfs_btree_block_change_owner_info *bbcoi = data; 4401 struct xfs_btree_block *block; 4402 struct xfs_buf *bp; 4403 4404 /* modify the owner */ 4405 block = xfs_btree_get_block(cur, level, &bp); 4406 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 4407 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); 4408 else 4409 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); 4410 4411 /* 4412 * If the block is a root block hosted in an inode, we might not have a 4413 * buffer pointer here and we shouldn't attempt to log the change as the 4414 * information is already held in the inode and discarded when the root 4415 * block is formatted into the on-disk inode fork. We still change it, 4416 * though, so everything is consistent in memory. 4417 */ 4418 if (bp) { 4419 if (cur->bc_tp) { 4420 xfs_trans_ordered_buf(cur->bc_tp, bp); 4421 xfs_btree_log_block(cur, bp, XFS_BB_OWNER); 4422 } else { 4423 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); 4424 } 4425 } else { 4426 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); 4427 ASSERT(level == cur->bc_nlevels - 1); 4428 } 4429 4430 return 0; 4431 } 4432 4433 int 4434 xfs_btree_change_owner( 4435 struct xfs_btree_cur *cur, 4436 __uint64_t new_owner, 4437 struct list_head *buffer_list) 4438 { 4439 struct xfs_btree_block_change_owner_info bbcoi; 4440 4441 bbcoi.new_owner = new_owner; 4442 bbcoi.buffer_list = buffer_list; 4443 4444 return xfs_btree_visit_blocks(cur, xfs_btree_block_change_owner, 4445 &bbcoi); 4446 } 4447 4448 /** 4449 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format 4450 * btree block 4451 * 4452 * @bp: buffer containing the btree block 4453 * @max_recs: pointer to the m_*_mxr max records field in the xfs mount 4454 * @pag_max_level: pointer to the per-ag max level field 4455 */ 4456 bool 4457 xfs_btree_sblock_v5hdr_verify( 4458 struct xfs_buf *bp) 4459 { 4460 struct xfs_mount *mp = bp->b_target->bt_mount; 4461 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 4462 struct xfs_perag *pag = bp->b_pag; 4463 4464 if (!xfs_sb_version_hascrc(&mp->m_sb)) 4465 return false; 4466 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) 4467 return false; 4468 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) 4469 return false; 4470 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) 4471 return false; 4472 return true; 4473 } 4474 4475 /** 4476 * xfs_btree_sblock_verify() -- verify a short-format btree block 4477 * 4478 * @bp: buffer containing the btree block 4479 * @max_recs: maximum records allowed in this btree node 4480 */ 4481 bool 4482 xfs_btree_sblock_verify( 4483 struct xfs_buf *bp, 4484 unsigned int max_recs) 4485 { 4486 struct xfs_mount *mp = bp->b_target->bt_mount; 4487 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 4488 4489 /* numrecs verification */ 4490 if (be16_to_cpu(block->bb_numrecs) > max_recs) 4491 return false; 4492 4493 /* sibling pointer verification */ 4494 if (!block->bb_u.s.bb_leftsib || 4495 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks && 4496 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK))) 4497 return false; 4498 if (!block->bb_u.s.bb_rightsib || 4499 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks && 4500 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK))) 4501 return false; 4502 4503 return true; 4504 } 4505 4506 /* 4507 * Calculate the number of btree levels needed to store a given number of 4508 * records in a short-format btree. 4509 */ 4510 uint 4511 xfs_btree_compute_maxlevels( 4512 struct xfs_mount *mp, 4513 uint *limits, 4514 unsigned long len) 4515 { 4516 uint level; 4517 unsigned long maxblocks; 4518 4519 maxblocks = (len + limits[0] - 1) / limits[0]; 4520 for (level = 1; maxblocks > 1; level++) 4521 maxblocks = (maxblocks + limits[1] - 1) / limits[1]; 4522 return level; 4523 } 4524 4525 /* 4526 * Query a regular btree for all records overlapping a given interval. 4527 * Start with a LE lookup of the key of low_rec and return all records 4528 * until we find a record with a key greater than the key of high_rec. 4529 */ 4530 STATIC int 4531 xfs_btree_simple_query_range( 4532 struct xfs_btree_cur *cur, 4533 union xfs_btree_key *low_key, 4534 union xfs_btree_key *high_key, 4535 xfs_btree_query_range_fn fn, 4536 void *priv) 4537 { 4538 union xfs_btree_rec *recp; 4539 union xfs_btree_key rec_key; 4540 __int64_t diff; 4541 int stat; 4542 bool firstrec = true; 4543 int error; 4544 4545 ASSERT(cur->bc_ops->init_high_key_from_rec); 4546 ASSERT(cur->bc_ops->diff_two_keys); 4547 4548 /* 4549 * Find the leftmost record. The btree cursor must be set 4550 * to the low record used to generate low_key. 4551 */ 4552 stat = 0; 4553 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat); 4554 if (error) 4555 goto out; 4556 4557 while (stat) { 4558 /* Find the record. */ 4559 error = xfs_btree_get_rec(cur, &recp, &stat); 4560 if (error || !stat) 4561 break; 4562 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); 4563 4564 /* Skip if high_key(rec) < low_key. */ 4565 if (firstrec) { 4566 firstrec = false; 4567 diff = cur->bc_ops->diff_two_keys(cur, low_key, 4568 &rec_key); 4569 if (diff > 0) 4570 goto advloop; 4571 } 4572 4573 /* Stop if high_key < low_key(rec). */ 4574 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); 4575 if (diff > 0) 4576 break; 4577 4578 /* Callback */ 4579 error = fn(cur, recp, priv); 4580 if (error < 0 || error == XFS_BTREE_QUERY_RANGE_ABORT) 4581 break; 4582 4583 advloop: 4584 /* Move on to the next record. */ 4585 error = xfs_btree_increment(cur, 0, &stat); 4586 if (error) 4587 break; 4588 } 4589 4590 out: 4591 return error; 4592 } 4593 4594 /* 4595 * Query an overlapped interval btree for all records overlapping a given 4596 * interval. This function roughly follows the algorithm given in 4597 * "Interval Trees" of _Introduction to Algorithms_, which is section 4598 * 14.3 in the 2nd and 3rd editions. 4599 * 4600 * First, generate keys for the low and high records passed in. 4601 * 4602 * For any leaf node, generate the high and low keys for the record. 4603 * If the record keys overlap with the query low/high keys, pass the 4604 * record to the function iterator. 4605 * 4606 * For any internal node, compare the low and high keys of each 4607 * pointer against the query low/high keys. If there's an overlap, 4608 * follow the pointer. 4609 * 4610 * As an optimization, we stop scanning a block when we find a low key 4611 * that is greater than the query's high key. 4612 */ 4613 STATIC int 4614 xfs_btree_overlapped_query_range( 4615 struct xfs_btree_cur *cur, 4616 union xfs_btree_key *low_key, 4617 union xfs_btree_key *high_key, 4618 xfs_btree_query_range_fn fn, 4619 void *priv) 4620 { 4621 union xfs_btree_ptr ptr; 4622 union xfs_btree_ptr *pp; 4623 union xfs_btree_key rec_key; 4624 union xfs_btree_key rec_hkey; 4625 union xfs_btree_key *lkp; 4626 union xfs_btree_key *hkp; 4627 union xfs_btree_rec *recp; 4628 struct xfs_btree_block *block; 4629 __int64_t ldiff; 4630 __int64_t hdiff; 4631 int level; 4632 struct xfs_buf *bp; 4633 int i; 4634 int error; 4635 4636 /* Load the root of the btree. */ 4637 level = cur->bc_nlevels - 1; 4638 cur->bc_ops->init_ptr_from_cur(cur, &ptr); 4639 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); 4640 if (error) 4641 return error; 4642 xfs_btree_get_block(cur, level, &bp); 4643 trace_xfs_btree_overlapped_query_range(cur, level, bp); 4644 #ifdef DEBUG 4645 error = xfs_btree_check_block(cur, block, level, bp); 4646 if (error) 4647 goto out; 4648 #endif 4649 cur->bc_ptrs[level] = 1; 4650 4651 while (level < cur->bc_nlevels) { 4652 block = xfs_btree_get_block(cur, level, &bp); 4653 4654 /* End of node, pop back towards the root. */ 4655 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { 4656 pop_up: 4657 if (level < cur->bc_nlevels - 1) 4658 cur->bc_ptrs[level + 1]++; 4659 level++; 4660 continue; 4661 } 4662 4663 if (level == 0) { 4664 /* Handle a leaf node. */ 4665 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 4666 4667 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); 4668 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, 4669 low_key); 4670 4671 cur->bc_ops->init_key_from_rec(&rec_key, recp); 4672 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, 4673 &rec_key); 4674 4675 /* 4676 * If (record's high key >= query's low key) and 4677 * (query's high key >= record's low key), then 4678 * this record overlaps the query range; callback. 4679 */ 4680 if (ldiff >= 0 && hdiff >= 0) { 4681 error = fn(cur, recp, priv); 4682 if (error < 0 || 4683 error == XFS_BTREE_QUERY_RANGE_ABORT) 4684 break; 4685 } else if (hdiff < 0) { 4686 /* Record is larger than high key; pop. */ 4687 goto pop_up; 4688 } 4689 cur->bc_ptrs[level]++; 4690 continue; 4691 } 4692 4693 /* Handle an internal node. */ 4694 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); 4695 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); 4696 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); 4697 4698 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); 4699 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); 4700 4701 /* 4702 * If (pointer's high key >= query's low key) and 4703 * (query's high key >= pointer's low key), then 4704 * this record overlaps the query range; follow pointer. 4705 */ 4706 if (ldiff >= 0 && hdiff >= 0) { 4707 level--; 4708 error = xfs_btree_lookup_get_block(cur, level, pp, 4709 &block); 4710 if (error) 4711 goto out; 4712 xfs_btree_get_block(cur, level, &bp); 4713 trace_xfs_btree_overlapped_query_range(cur, level, bp); 4714 #ifdef DEBUG 4715 error = xfs_btree_check_block(cur, block, level, bp); 4716 if (error) 4717 goto out; 4718 #endif 4719 cur->bc_ptrs[level] = 1; 4720 continue; 4721 } else if (hdiff < 0) { 4722 /* The low key is larger than the upper range; pop. */ 4723 goto pop_up; 4724 } 4725 cur->bc_ptrs[level]++; 4726 } 4727 4728 out: 4729 /* 4730 * If we don't end this function with the cursor pointing at a record 4731 * block, a subsequent non-error cursor deletion will not release 4732 * node-level buffers, causing a buffer leak. This is quite possible 4733 * with a zero-results range query, so release the buffers if we 4734 * failed to return any results. 4735 */ 4736 if (cur->bc_bufs[0] == NULL) { 4737 for (i = 0; i < cur->bc_nlevels; i++) { 4738 if (cur->bc_bufs[i]) { 4739 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); 4740 cur->bc_bufs[i] = NULL; 4741 cur->bc_ptrs[i] = 0; 4742 cur->bc_ra[i] = 0; 4743 } 4744 } 4745 } 4746 4747 return error; 4748 } 4749 4750 /* 4751 * Query a btree for all records overlapping a given interval of keys. The 4752 * supplied function will be called with each record found; return one of the 4753 * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error 4754 * code. This function returns XFS_BTREE_QUERY_RANGE_ABORT, zero, or a 4755 * negative error code. 4756 */ 4757 int 4758 xfs_btree_query_range( 4759 struct xfs_btree_cur *cur, 4760 union xfs_btree_irec *low_rec, 4761 union xfs_btree_irec *high_rec, 4762 xfs_btree_query_range_fn fn, 4763 void *priv) 4764 { 4765 union xfs_btree_rec rec; 4766 union xfs_btree_key low_key; 4767 union xfs_btree_key high_key; 4768 4769 /* Find the keys of both ends of the interval. */ 4770 cur->bc_rec = *high_rec; 4771 cur->bc_ops->init_rec_from_cur(cur, &rec); 4772 cur->bc_ops->init_key_from_rec(&high_key, &rec); 4773 4774 cur->bc_rec = *low_rec; 4775 cur->bc_ops->init_rec_from_cur(cur, &rec); 4776 cur->bc_ops->init_key_from_rec(&low_key, &rec); 4777 4778 /* Enforce low key < high key. */ 4779 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) 4780 return -EINVAL; 4781 4782 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 4783 return xfs_btree_simple_query_range(cur, &low_key, 4784 &high_key, fn, priv); 4785 return xfs_btree_overlapped_query_range(cur, &low_key, &high_key, 4786 fn, priv); 4787 } 4788