1 /* 2 * Copyright (c) 2017 Christoph Hellwig. 3 * 4 * This program is free software; you can redistribute it and/or modify it 5 * under the terms and conditions of the GNU General Public License, 6 * version 2, as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 11 * more details. 12 */ 13 14 #include <linux/cache.h> 15 #include <linux/kernel.h> 16 #include <linux/slab.h> 17 #include "xfs.h" 18 #include "xfs_format.h" 19 #include "xfs_bit.h" 20 #include "xfs_log_format.h" 21 #include "xfs_inode.h" 22 #include "xfs_inode_fork.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_mount.h" 25 #include "xfs_trace.h" 26 27 /* 28 * In-core extent record layout: 29 * 30 * +-------+----------------------------+ 31 * | 00:53 | all 54 bits of startoff | 32 * | 54:63 | low 10 bits of startblock | 33 * +-------+----------------------------+ 34 * | 00:20 | all 21 bits of length | 35 * | 21 | unwritten extent bit | 36 * | 22:63 | high 42 bits of startblock | 37 * +-------+----------------------------+ 38 */ 39 #define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN) 40 #define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN) 41 #define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN) 42 43 struct xfs_iext_rec { 44 uint64_t lo; 45 uint64_t hi; 46 }; 47 48 /* 49 * Given that the length can't be a zero, only an empty hi value indicates an 50 * unused record. 51 */ 52 static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec) 53 { 54 return rec->hi == 0; 55 } 56 57 static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec) 58 { 59 rec->lo = 0; 60 rec->hi = 0; 61 } 62 63 static void 64 xfs_iext_set( 65 struct xfs_iext_rec *rec, 66 struct xfs_bmbt_irec *irec) 67 { 68 ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0); 69 ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0); 70 ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0); 71 72 rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK; 73 rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK; 74 75 rec->lo |= (irec->br_startblock << 54); 76 rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10)); 77 78 if (irec->br_state == XFS_EXT_UNWRITTEN) 79 rec->hi |= (1 << 21); 80 } 81 82 static void 83 xfs_iext_get( 84 struct xfs_bmbt_irec *irec, 85 struct xfs_iext_rec *rec) 86 { 87 irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK; 88 irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK; 89 90 irec->br_startblock = rec->lo >> 54; 91 irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10); 92 93 if (rec->hi & (1 << 21)) 94 irec->br_state = XFS_EXT_UNWRITTEN; 95 else 96 irec->br_state = XFS_EXT_NORM; 97 } 98 99 enum { 100 NODE_SIZE = 256, 101 KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)), 102 RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) / 103 sizeof(struct xfs_iext_rec), 104 }; 105 106 /* 107 * In-core extent btree block layout: 108 * 109 * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks. 110 * 111 * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each 112 * contain the startoffset, blockcount, startblock and unwritten extent flag. 113 * See above for the exact format, followed by pointers to the previous and next 114 * leaf blocks (if there are any). 115 * 116 * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed 117 * by an equal number of pointers to the btree blocks at the next lower level. 118 * 119 * +-------+-------+-------+-------+-------+----------+----------+ 120 * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr | 121 * +-------+-------+-------+-------+-------+----------+----------+ 122 * 123 * +-------+-------+-------+-------+-------+-------+------+-------+ 124 * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N | 125 * +-------+-------+-------+-------+-------+-------+------+-------+ 126 */ 127 struct xfs_iext_node { 128 uint64_t keys[KEYS_PER_NODE]; 129 #define XFS_IEXT_KEY_INVALID (1ULL << 63) 130 void *ptrs[KEYS_PER_NODE]; 131 }; 132 133 struct xfs_iext_leaf { 134 struct xfs_iext_rec recs[RECS_PER_LEAF]; 135 struct xfs_iext_leaf *prev; 136 struct xfs_iext_leaf *next; 137 }; 138 139 inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp) 140 { 141 return ifp->if_bytes / sizeof(struct xfs_iext_rec); 142 } 143 144 static inline int xfs_iext_max_recs(struct xfs_ifork *ifp) 145 { 146 if (ifp->if_height == 1) 147 return xfs_iext_count(ifp); 148 return RECS_PER_LEAF; 149 } 150 151 static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur) 152 { 153 return &cur->leaf->recs[cur->pos]; 154 } 155 156 static inline bool xfs_iext_valid(struct xfs_ifork *ifp, 157 struct xfs_iext_cursor *cur) 158 { 159 if (!cur->leaf) 160 return false; 161 if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp)) 162 return false; 163 if (xfs_iext_rec_is_empty(cur_rec(cur))) 164 return false; 165 return true; 166 } 167 168 static void * 169 xfs_iext_find_first_leaf( 170 struct xfs_ifork *ifp) 171 { 172 struct xfs_iext_node *node = ifp->if_u1.if_root; 173 int height; 174 175 if (!ifp->if_height) 176 return NULL; 177 178 for (height = ifp->if_height; height > 1; height--) { 179 node = node->ptrs[0]; 180 ASSERT(node); 181 } 182 183 return node; 184 } 185 186 static void * 187 xfs_iext_find_last_leaf( 188 struct xfs_ifork *ifp) 189 { 190 struct xfs_iext_node *node = ifp->if_u1.if_root; 191 int height, i; 192 193 if (!ifp->if_height) 194 return NULL; 195 196 for (height = ifp->if_height; height > 1; height--) { 197 for (i = 1; i < KEYS_PER_NODE; i++) 198 if (!node->ptrs[i]) 199 break; 200 node = node->ptrs[i - 1]; 201 ASSERT(node); 202 } 203 204 return node; 205 } 206 207 void 208 xfs_iext_first( 209 struct xfs_ifork *ifp, 210 struct xfs_iext_cursor *cur) 211 { 212 cur->pos = 0; 213 cur->leaf = xfs_iext_find_first_leaf(ifp); 214 } 215 216 void 217 xfs_iext_last( 218 struct xfs_ifork *ifp, 219 struct xfs_iext_cursor *cur) 220 { 221 int i; 222 223 cur->leaf = xfs_iext_find_last_leaf(ifp); 224 if (!cur->leaf) { 225 cur->pos = 0; 226 return; 227 } 228 229 for (i = 1; i < xfs_iext_max_recs(ifp); i++) { 230 if (xfs_iext_rec_is_empty(&cur->leaf->recs[i])) 231 break; 232 } 233 cur->pos = i - 1; 234 } 235 236 void 237 xfs_iext_next( 238 struct xfs_ifork *ifp, 239 struct xfs_iext_cursor *cur) 240 { 241 if (!cur->leaf) { 242 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); 243 xfs_iext_first(ifp, cur); 244 return; 245 } 246 247 ASSERT(cur->pos >= 0); 248 ASSERT(cur->pos < xfs_iext_max_recs(ifp)); 249 250 cur->pos++; 251 if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) && 252 cur->leaf->next) { 253 cur->leaf = cur->leaf->next; 254 cur->pos = 0; 255 } 256 } 257 258 void 259 xfs_iext_prev( 260 struct xfs_ifork *ifp, 261 struct xfs_iext_cursor *cur) 262 { 263 if (!cur->leaf) { 264 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); 265 xfs_iext_last(ifp, cur); 266 return; 267 } 268 269 ASSERT(cur->pos >= 0); 270 ASSERT(cur->pos <= RECS_PER_LEAF); 271 272 recurse: 273 do { 274 cur->pos--; 275 if (xfs_iext_valid(ifp, cur)) 276 return; 277 } while (cur->pos > 0); 278 279 if (ifp->if_height > 1 && cur->leaf->prev) { 280 cur->leaf = cur->leaf->prev; 281 cur->pos = RECS_PER_LEAF; 282 goto recurse; 283 } 284 } 285 286 static inline int 287 xfs_iext_key_cmp( 288 struct xfs_iext_node *node, 289 int n, 290 xfs_fileoff_t offset) 291 { 292 if (node->keys[n] > offset) 293 return 1; 294 if (node->keys[n] < offset) 295 return -1; 296 return 0; 297 } 298 299 static inline int 300 xfs_iext_rec_cmp( 301 struct xfs_iext_rec *rec, 302 xfs_fileoff_t offset) 303 { 304 uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK; 305 uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK; 306 307 if (rec_offset > offset) 308 return 1; 309 if (rec_offset + rec_len <= offset) 310 return -1; 311 return 0; 312 } 313 314 static void * 315 xfs_iext_find_level( 316 struct xfs_ifork *ifp, 317 xfs_fileoff_t offset, 318 int level) 319 { 320 struct xfs_iext_node *node = ifp->if_u1.if_root; 321 int height, i; 322 323 if (!ifp->if_height) 324 return NULL; 325 326 for (height = ifp->if_height; height > level; height--) { 327 for (i = 1; i < KEYS_PER_NODE; i++) 328 if (xfs_iext_key_cmp(node, i, offset) > 0) 329 break; 330 331 node = node->ptrs[i - 1]; 332 if (!node) 333 break; 334 } 335 336 return node; 337 } 338 339 static int 340 xfs_iext_node_pos( 341 struct xfs_iext_node *node, 342 xfs_fileoff_t offset) 343 { 344 int i; 345 346 for (i = 1; i < KEYS_PER_NODE; i++) { 347 if (xfs_iext_key_cmp(node, i, offset) > 0) 348 break; 349 } 350 351 return i - 1; 352 } 353 354 static int 355 xfs_iext_node_insert_pos( 356 struct xfs_iext_node *node, 357 xfs_fileoff_t offset) 358 { 359 int i; 360 361 for (i = 0; i < KEYS_PER_NODE; i++) { 362 if (xfs_iext_key_cmp(node, i, offset) > 0) 363 return i; 364 } 365 366 return KEYS_PER_NODE; 367 } 368 369 static int 370 xfs_iext_node_nr_entries( 371 struct xfs_iext_node *node, 372 int start) 373 { 374 int i; 375 376 for (i = start; i < KEYS_PER_NODE; i++) { 377 if (node->keys[i] == XFS_IEXT_KEY_INVALID) 378 break; 379 } 380 381 return i; 382 } 383 384 static int 385 xfs_iext_leaf_nr_entries( 386 struct xfs_ifork *ifp, 387 struct xfs_iext_leaf *leaf, 388 int start) 389 { 390 int i; 391 392 for (i = start; i < xfs_iext_max_recs(ifp); i++) { 393 if (xfs_iext_rec_is_empty(&leaf->recs[i])) 394 break; 395 } 396 397 return i; 398 } 399 400 static inline uint64_t 401 xfs_iext_leaf_key( 402 struct xfs_iext_leaf *leaf, 403 int n) 404 { 405 return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK; 406 } 407 408 static void 409 xfs_iext_grow( 410 struct xfs_ifork *ifp) 411 { 412 struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS); 413 int i; 414 415 if (ifp->if_height == 1) { 416 struct xfs_iext_leaf *prev = ifp->if_u1.if_root; 417 418 node->keys[0] = xfs_iext_leaf_key(prev, 0); 419 node->ptrs[0] = prev; 420 } else { 421 struct xfs_iext_node *prev = ifp->if_u1.if_root; 422 423 ASSERT(ifp->if_height > 1); 424 425 node->keys[0] = prev->keys[0]; 426 node->ptrs[0] = prev; 427 } 428 429 for (i = 1; i < KEYS_PER_NODE; i++) 430 node->keys[i] = XFS_IEXT_KEY_INVALID; 431 432 ifp->if_u1.if_root = node; 433 ifp->if_height++; 434 } 435 436 static void 437 xfs_iext_update_node( 438 struct xfs_ifork *ifp, 439 xfs_fileoff_t old_offset, 440 xfs_fileoff_t new_offset, 441 int level, 442 void *ptr) 443 { 444 struct xfs_iext_node *node = ifp->if_u1.if_root; 445 int height, i; 446 447 for (height = ifp->if_height; height > level; height--) { 448 for (i = 0; i < KEYS_PER_NODE; i++) { 449 if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0) 450 break; 451 if (node->keys[i] == old_offset) 452 node->keys[i] = new_offset; 453 } 454 node = node->ptrs[i - 1]; 455 ASSERT(node); 456 } 457 458 ASSERT(node == ptr); 459 } 460 461 static struct xfs_iext_node * 462 xfs_iext_split_node( 463 struct xfs_iext_node **nodep, 464 int *pos, 465 int *nr_entries) 466 { 467 struct xfs_iext_node *node = *nodep; 468 struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS); 469 const int nr_move = KEYS_PER_NODE / 2; 470 int nr_keep = nr_move + (KEYS_PER_NODE & 1); 471 int i = 0; 472 473 /* for sequential append operations just spill over into the new node */ 474 if (*pos == KEYS_PER_NODE) { 475 *nodep = new; 476 *pos = 0; 477 *nr_entries = 0; 478 goto done; 479 } 480 481 482 for (i = 0; i < nr_move; i++) { 483 new->keys[i] = node->keys[nr_keep + i]; 484 new->ptrs[i] = node->ptrs[nr_keep + i]; 485 486 node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID; 487 node->ptrs[nr_keep + i] = NULL; 488 } 489 490 if (*pos >= nr_keep) { 491 *nodep = new; 492 *pos -= nr_keep; 493 *nr_entries = nr_move; 494 } else { 495 *nr_entries = nr_keep; 496 } 497 done: 498 for (; i < KEYS_PER_NODE; i++) 499 new->keys[i] = XFS_IEXT_KEY_INVALID; 500 return new; 501 } 502 503 static void 504 xfs_iext_insert_node( 505 struct xfs_ifork *ifp, 506 uint64_t offset, 507 void *ptr, 508 int level) 509 { 510 struct xfs_iext_node *node, *new; 511 int i, pos, nr_entries; 512 513 again: 514 if (ifp->if_height < level) 515 xfs_iext_grow(ifp); 516 517 new = NULL; 518 node = xfs_iext_find_level(ifp, offset, level); 519 pos = xfs_iext_node_insert_pos(node, offset); 520 nr_entries = xfs_iext_node_nr_entries(node, pos); 521 522 ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0); 523 ASSERT(nr_entries <= KEYS_PER_NODE); 524 525 if (nr_entries == KEYS_PER_NODE) 526 new = xfs_iext_split_node(&node, &pos, &nr_entries); 527 528 /* 529 * Update the pointers in higher levels if the first entry changes 530 * in an existing node. 531 */ 532 if (node != new && pos == 0 && nr_entries > 0) 533 xfs_iext_update_node(ifp, node->keys[0], offset, level, node); 534 535 for (i = nr_entries; i > pos; i--) { 536 node->keys[i] = node->keys[i - 1]; 537 node->ptrs[i] = node->ptrs[i - 1]; 538 } 539 node->keys[pos] = offset; 540 node->ptrs[pos] = ptr; 541 542 if (new) { 543 offset = new->keys[0]; 544 ptr = new; 545 level++; 546 goto again; 547 } 548 } 549 550 static struct xfs_iext_leaf * 551 xfs_iext_split_leaf( 552 struct xfs_iext_cursor *cur, 553 int *nr_entries) 554 { 555 struct xfs_iext_leaf *leaf = cur->leaf; 556 struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS); 557 const int nr_move = RECS_PER_LEAF / 2; 558 int nr_keep = nr_move + (RECS_PER_LEAF & 1); 559 int i; 560 561 /* for sequential append operations just spill over into the new node */ 562 if (cur->pos == RECS_PER_LEAF) { 563 cur->leaf = new; 564 cur->pos = 0; 565 *nr_entries = 0; 566 goto done; 567 } 568 569 for (i = 0; i < nr_move; i++) { 570 new->recs[i] = leaf->recs[nr_keep + i]; 571 xfs_iext_rec_clear(&leaf->recs[nr_keep + i]); 572 } 573 574 if (cur->pos >= nr_keep) { 575 cur->leaf = new; 576 cur->pos -= nr_keep; 577 *nr_entries = nr_move; 578 } else { 579 *nr_entries = nr_keep; 580 } 581 done: 582 if (leaf->next) 583 leaf->next->prev = new; 584 new->next = leaf->next; 585 new->prev = leaf; 586 leaf->next = new; 587 return new; 588 } 589 590 static void 591 xfs_iext_alloc_root( 592 struct xfs_ifork *ifp, 593 struct xfs_iext_cursor *cur) 594 { 595 ASSERT(ifp->if_bytes == 0); 596 597 ifp->if_u1.if_root = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS); 598 ifp->if_height = 1; 599 600 /* now that we have a node step into it */ 601 cur->leaf = ifp->if_u1.if_root; 602 cur->pos = 0; 603 } 604 605 static void 606 xfs_iext_realloc_root( 607 struct xfs_ifork *ifp, 608 struct xfs_iext_cursor *cur) 609 { 610 size_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec); 611 void *new; 612 613 /* account for the prev/next pointers */ 614 if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF) 615 new_size = NODE_SIZE; 616 617 new = kmem_realloc(ifp->if_u1.if_root, new_size, KM_NOFS); 618 memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes); 619 ifp->if_u1.if_root = new; 620 cur->leaf = new; 621 } 622 623 void 624 xfs_iext_insert( 625 struct xfs_inode *ip, 626 struct xfs_iext_cursor *cur, 627 struct xfs_bmbt_irec *irec, 628 int state) 629 { 630 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 631 xfs_fileoff_t offset = irec->br_startoff; 632 struct xfs_iext_leaf *new = NULL; 633 int nr_entries, i; 634 635 if (ifp->if_height == 0) 636 xfs_iext_alloc_root(ifp, cur); 637 else if (ifp->if_height == 1) 638 xfs_iext_realloc_root(ifp, cur); 639 640 nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos); 641 ASSERT(nr_entries <= RECS_PER_LEAF); 642 ASSERT(cur->pos >= nr_entries || 643 xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0); 644 645 if (nr_entries == RECS_PER_LEAF) 646 new = xfs_iext_split_leaf(cur, &nr_entries); 647 648 /* 649 * Update the pointers in higher levels if the first entry changes 650 * in an existing node. 651 */ 652 if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) { 653 xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0), 654 offset, 1, cur->leaf); 655 } 656 657 for (i = nr_entries; i > cur->pos; i--) 658 cur->leaf->recs[i] = cur->leaf->recs[i - 1]; 659 xfs_iext_set(cur_rec(cur), irec); 660 ifp->if_bytes += sizeof(struct xfs_iext_rec); 661 662 trace_xfs_iext_insert(ip, cur, state, _RET_IP_); 663 664 if (new) 665 xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2); 666 } 667 668 static struct xfs_iext_node * 669 xfs_iext_rebalance_node( 670 struct xfs_iext_node *parent, 671 int *pos, 672 struct xfs_iext_node *node, 673 int nr_entries) 674 { 675 /* 676 * If the neighbouring nodes are completely full, or have different 677 * parents, we might never be able to merge our node, and will only 678 * delete it once the number of entries hits zero. 679 */ 680 if (nr_entries == 0) 681 return node; 682 683 if (*pos > 0) { 684 struct xfs_iext_node *prev = parent->ptrs[*pos - 1]; 685 int nr_prev = xfs_iext_node_nr_entries(prev, 0), i; 686 687 if (nr_prev + nr_entries <= KEYS_PER_NODE) { 688 for (i = 0; i < nr_entries; i++) { 689 prev->keys[nr_prev + i] = node->keys[i]; 690 prev->ptrs[nr_prev + i] = node->ptrs[i]; 691 } 692 return node; 693 } 694 } 695 696 if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) { 697 struct xfs_iext_node *next = parent->ptrs[*pos + 1]; 698 int nr_next = xfs_iext_node_nr_entries(next, 0), i; 699 700 if (nr_entries + nr_next <= KEYS_PER_NODE) { 701 /* 702 * Merge the next node into this node so that we don't 703 * have to do an additional update of the keys in the 704 * higher levels. 705 */ 706 for (i = 0; i < nr_next; i++) { 707 node->keys[nr_entries + i] = next->keys[i]; 708 node->ptrs[nr_entries + i] = next->ptrs[i]; 709 } 710 711 ++*pos; 712 return next; 713 } 714 } 715 716 return NULL; 717 } 718 719 static void 720 xfs_iext_remove_node( 721 struct xfs_ifork *ifp, 722 xfs_fileoff_t offset, 723 void *victim) 724 { 725 struct xfs_iext_node *node, *parent; 726 int level = 2, pos, nr_entries, i; 727 728 ASSERT(level <= ifp->if_height); 729 node = xfs_iext_find_level(ifp, offset, level); 730 pos = xfs_iext_node_pos(node, offset); 731 again: 732 ASSERT(node->ptrs[pos]); 733 ASSERT(node->ptrs[pos] == victim); 734 kmem_free(victim); 735 736 nr_entries = xfs_iext_node_nr_entries(node, pos) - 1; 737 offset = node->keys[0]; 738 for (i = pos; i < nr_entries; i++) { 739 node->keys[i] = node->keys[i + 1]; 740 node->ptrs[i] = node->ptrs[i + 1]; 741 } 742 node->keys[nr_entries] = XFS_IEXT_KEY_INVALID; 743 node->ptrs[nr_entries] = NULL; 744 745 if (pos == 0 && nr_entries > 0) { 746 xfs_iext_update_node(ifp, offset, node->keys[0], level, node); 747 offset = node->keys[0]; 748 } 749 750 if (nr_entries >= KEYS_PER_NODE / 2) 751 return; 752 753 if (level < ifp->if_height) { 754 /* 755 * If we aren't at the root yet try to find a neighbour node to 756 * merge with (or delete the node if it is empty), and then 757 * recurse up to the next level. 758 */ 759 level++; 760 parent = xfs_iext_find_level(ifp, offset, level); 761 pos = xfs_iext_node_pos(parent, offset); 762 763 ASSERT(pos != KEYS_PER_NODE); 764 ASSERT(parent->ptrs[pos] == node); 765 766 node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries); 767 if (node) { 768 victim = node; 769 node = parent; 770 goto again; 771 } 772 } else if (nr_entries == 1) { 773 /* 774 * If we are at the root and only one entry is left we can just 775 * free this node and update the root pointer. 776 */ 777 ASSERT(node == ifp->if_u1.if_root); 778 ifp->if_u1.if_root = node->ptrs[0]; 779 ifp->if_height--; 780 kmem_free(node); 781 } 782 } 783 784 static void 785 xfs_iext_rebalance_leaf( 786 struct xfs_ifork *ifp, 787 struct xfs_iext_cursor *cur, 788 struct xfs_iext_leaf *leaf, 789 xfs_fileoff_t offset, 790 int nr_entries) 791 { 792 /* 793 * If the neighbouring nodes are completely full we might never be able 794 * to merge our node, and will only delete it once the number of 795 * entries hits zero. 796 */ 797 if (nr_entries == 0) 798 goto remove_node; 799 800 if (leaf->prev) { 801 int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i; 802 803 if (nr_prev + nr_entries <= RECS_PER_LEAF) { 804 for (i = 0; i < nr_entries; i++) 805 leaf->prev->recs[nr_prev + i] = leaf->recs[i]; 806 807 if (cur->leaf == leaf) { 808 cur->leaf = leaf->prev; 809 cur->pos += nr_prev; 810 } 811 goto remove_node; 812 } 813 } 814 815 if (leaf->next) { 816 int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i; 817 818 if (nr_entries + nr_next <= RECS_PER_LEAF) { 819 /* 820 * Merge the next node into this node so that we don't 821 * have to do an additional update of the keys in the 822 * higher levels. 823 */ 824 for (i = 0; i < nr_next; i++) { 825 leaf->recs[nr_entries + i] = 826 leaf->next->recs[i]; 827 } 828 829 if (cur->leaf == leaf->next) { 830 cur->leaf = leaf; 831 cur->pos += nr_entries; 832 } 833 834 offset = xfs_iext_leaf_key(leaf->next, 0); 835 leaf = leaf->next; 836 goto remove_node; 837 } 838 } 839 840 return; 841 remove_node: 842 if (leaf->prev) 843 leaf->prev->next = leaf->next; 844 if (leaf->next) 845 leaf->next->prev = leaf->prev; 846 xfs_iext_remove_node(ifp, offset, leaf); 847 } 848 849 static void 850 xfs_iext_free_last_leaf( 851 struct xfs_ifork *ifp) 852 { 853 ifp->if_height--; 854 kmem_free(ifp->if_u1.if_root); 855 ifp->if_u1.if_root = NULL; 856 } 857 858 void 859 xfs_iext_remove( 860 struct xfs_inode *ip, 861 struct xfs_iext_cursor *cur, 862 int state) 863 { 864 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 865 struct xfs_iext_leaf *leaf = cur->leaf; 866 xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0); 867 int i, nr_entries; 868 869 trace_xfs_iext_remove(ip, cur, state, _RET_IP_); 870 871 ASSERT(ifp->if_height > 0); 872 ASSERT(ifp->if_u1.if_root != NULL); 873 ASSERT(xfs_iext_valid(ifp, cur)); 874 875 nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1; 876 for (i = cur->pos; i < nr_entries; i++) 877 leaf->recs[i] = leaf->recs[i + 1]; 878 xfs_iext_rec_clear(&leaf->recs[nr_entries]); 879 ifp->if_bytes -= sizeof(struct xfs_iext_rec); 880 881 if (cur->pos == 0 && nr_entries > 0) { 882 xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1, 883 leaf); 884 offset = xfs_iext_leaf_key(leaf, 0); 885 } else if (cur->pos == nr_entries) { 886 if (ifp->if_height > 1 && leaf->next) 887 cur->leaf = leaf->next; 888 else 889 cur->leaf = NULL; 890 cur->pos = 0; 891 } 892 893 if (nr_entries >= RECS_PER_LEAF / 2) 894 return; 895 896 if (ifp->if_height > 1) 897 xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries); 898 else if (nr_entries == 0) 899 xfs_iext_free_last_leaf(ifp); 900 } 901 902 /* 903 * Lookup the extent covering bno. 904 * 905 * If there is an extent covering bno return the extent index, and store the 906 * expanded extent structure in *gotp, and the extent cursor in *cur. 907 * If there is no extent covering bno, but there is an extent after it (e.g. 908 * it lies in a hole) return that extent in *gotp and its cursor in *cur 909 * instead. 910 * If bno is beyond the last extent return false, and return an invalid 911 * cursor value. 912 */ 913 bool 914 xfs_iext_lookup_extent( 915 struct xfs_inode *ip, 916 struct xfs_ifork *ifp, 917 xfs_fileoff_t offset, 918 struct xfs_iext_cursor *cur, 919 struct xfs_bmbt_irec *gotp) 920 { 921 XFS_STATS_INC(ip->i_mount, xs_look_exlist); 922 923 cur->leaf = xfs_iext_find_level(ifp, offset, 1); 924 if (!cur->leaf) { 925 cur->pos = 0; 926 return false; 927 } 928 929 for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) { 930 struct xfs_iext_rec *rec = cur_rec(cur); 931 932 if (xfs_iext_rec_is_empty(rec)) 933 break; 934 if (xfs_iext_rec_cmp(rec, offset) >= 0) 935 goto found; 936 } 937 938 /* Try looking in the next node for an entry > offset */ 939 if (ifp->if_height == 1 || !cur->leaf->next) 940 return false; 941 cur->leaf = cur->leaf->next; 942 cur->pos = 0; 943 if (!xfs_iext_valid(ifp, cur)) 944 return false; 945 found: 946 xfs_iext_get(gotp, cur_rec(cur)); 947 return true; 948 } 949 950 /* 951 * Returns the last extent before end, and if this extent doesn't cover 952 * end, update end to the end of the extent. 953 */ 954 bool 955 xfs_iext_lookup_extent_before( 956 struct xfs_inode *ip, 957 struct xfs_ifork *ifp, 958 xfs_fileoff_t *end, 959 struct xfs_iext_cursor *cur, 960 struct xfs_bmbt_irec *gotp) 961 { 962 /* could be optimized to not even look up the next on a match.. */ 963 if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) && 964 gotp->br_startoff <= *end - 1) 965 return true; 966 if (!xfs_iext_prev_extent(ifp, cur, gotp)) 967 return false; 968 *end = gotp->br_startoff + gotp->br_blockcount; 969 return true; 970 } 971 972 void 973 xfs_iext_update_extent( 974 struct xfs_inode *ip, 975 int state, 976 struct xfs_iext_cursor *cur, 977 struct xfs_bmbt_irec *new) 978 { 979 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 980 981 if (cur->pos == 0) { 982 struct xfs_bmbt_irec old; 983 984 xfs_iext_get(&old, cur_rec(cur)); 985 if (new->br_startoff != old.br_startoff) { 986 xfs_iext_update_node(ifp, old.br_startoff, 987 new->br_startoff, 1, cur->leaf); 988 } 989 } 990 991 trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_); 992 xfs_iext_set(cur_rec(cur), new); 993 trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_); 994 } 995 996 /* 997 * Return true if the cursor points at an extent and return the extent structure 998 * in gotp. Else return false. 999 */ 1000 bool 1001 xfs_iext_get_extent( 1002 struct xfs_ifork *ifp, 1003 struct xfs_iext_cursor *cur, 1004 struct xfs_bmbt_irec *gotp) 1005 { 1006 if (!xfs_iext_valid(ifp, cur)) 1007 return false; 1008 xfs_iext_get(gotp, cur_rec(cur)); 1009 return true; 1010 } 1011 1012 /* 1013 * This is a recursive function, because of that we need to be extremely 1014 * careful with stack usage. 1015 */ 1016 static void 1017 xfs_iext_destroy_node( 1018 struct xfs_iext_node *node, 1019 int level) 1020 { 1021 int i; 1022 1023 if (level > 1) { 1024 for (i = 0; i < KEYS_PER_NODE; i++) { 1025 if (node->keys[i] == XFS_IEXT_KEY_INVALID) 1026 break; 1027 xfs_iext_destroy_node(node->ptrs[i], level - 1); 1028 } 1029 } 1030 1031 kmem_free(node); 1032 } 1033 1034 void 1035 xfs_iext_destroy( 1036 struct xfs_ifork *ifp) 1037 { 1038 xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height); 1039 1040 ifp->if_bytes = 0; 1041 ifp->if_height = 0; 1042 ifp->if_u1.if_root = NULL; 1043 } 1044