1 /* 2 * Copyright (C) International Business Machines Corp., 2000-2005 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See 12 * the 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 to the Free Software 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 */ 18 /* 19 * jfs_xtree.c: extent allocation descriptor B+-tree manager 20 */ 21 22 #include <linux/fs.h> 23 #include <linux/quotaops.h> 24 #include "jfs_incore.h" 25 #include "jfs_filsys.h" 26 #include "jfs_metapage.h" 27 #include "jfs_dmap.h" 28 #include "jfs_dinode.h" 29 #include "jfs_superblock.h" 30 #include "jfs_debug.h" 31 32 /* 33 * xtree local flag 34 */ 35 #define XT_INSERT 0x00000001 36 37 /* 38 * xtree key/entry comparison: extent offset 39 * 40 * return: 41 * -1: k < start of extent 42 * 0: start_of_extent <= k <= end_of_extent 43 * 1: k > end_of_extent 44 */ 45 #define XT_CMP(CMP, K, X, OFFSET64)\ 46 {\ 47 OFFSET64 = offsetXAD(X);\ 48 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\ 49 ((K) < OFFSET64) ? -1 : 0;\ 50 } 51 52 /* write a xad entry */ 53 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\ 54 {\ 55 (XAD)->flag = (FLAG);\ 56 XADoffset((XAD), (OFF));\ 57 XADlength((XAD), (LEN));\ 58 XADaddress((XAD), (ADDR));\ 59 } 60 61 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot) 62 63 /* get page buffer for specified block address */ 64 /* ToDo: Replace this ugly macro with a function */ 65 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\ 66 {\ 67 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\ 68 if (!(RC))\ 69 {\ 70 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\ 71 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\ 72 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\ 73 {\ 74 jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\ 75 BT_PUTPAGE(MP);\ 76 MP = NULL;\ 77 RC = -EIO;\ 78 }\ 79 }\ 80 } 81 82 /* for consistency */ 83 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP) 84 85 #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \ 86 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot) 87 /* xtree entry parameter descriptor */ 88 struct xtsplit { 89 struct metapage *mp; 90 s16 index; 91 u8 flag; 92 s64 off; 93 s64 addr; 94 int len; 95 struct pxdlist *pxdlist; 96 }; 97 98 99 /* 100 * statistics 101 */ 102 #ifdef CONFIG_JFS_STATISTICS 103 static struct { 104 uint search; 105 uint fastSearch; 106 uint split; 107 } xtStat; 108 #endif 109 110 111 /* 112 * forward references 113 */ 114 static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp, 115 struct btstack * btstack, int flag); 116 117 static int xtSplitUp(tid_t tid, 118 struct inode *ip, 119 struct xtsplit * split, struct btstack * btstack); 120 121 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split, 122 struct metapage ** rmpp, s64 * rbnp); 123 124 static int xtSplitRoot(tid_t tid, struct inode *ip, 125 struct xtsplit * split, struct metapage ** rmpp); 126 127 #ifdef _STILL_TO_PORT 128 static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp, 129 xtpage_t * fp, struct btstack * btstack); 130 131 static int xtSearchNode(struct inode *ip, 132 xad_t * xad, 133 int *cmpp, struct btstack * btstack, int flag); 134 135 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp); 136 #endif /* _STILL_TO_PORT */ 137 138 /* 139 * xtLookup() 140 * 141 * function: map a single page into a physical extent; 142 */ 143 int xtLookup(struct inode *ip, s64 lstart, 144 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check) 145 { 146 int rc = 0; 147 struct btstack btstack; 148 int cmp; 149 s64 bn; 150 struct metapage *mp; 151 xtpage_t *p; 152 int index; 153 xad_t *xad; 154 s64 next, size, xoff, xend; 155 int xlen; 156 s64 xaddr; 157 158 *paddr = 0; 159 *plen = llen; 160 161 if (!no_check) { 162 /* is lookup offset beyond eof ? */ 163 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >> 164 JFS_SBI(ip->i_sb)->l2bsize; 165 if (lstart >= size) { 166 jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)", 167 (ulong) lstart, (ulong) size); 168 return 0; 169 } 170 } 171 172 /* 173 * search for the xad entry covering the logical extent 174 */ 175 //search: 176 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) { 177 jfs_err("xtLookup: xtSearch returned %d", rc); 178 return rc; 179 } 180 181 /* 182 * compute the physical extent covering logical extent 183 * 184 * N.B. search may have failed (e.g., hole in sparse file), 185 * and returned the index of the next entry. 186 */ 187 /* retrieve search result */ 188 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 189 190 /* is xad found covering start of logical extent ? 191 * lstart is a page start address, 192 * i.e., lstart cannot start in a hole; 193 */ 194 if (cmp) { 195 if (next) 196 *plen = min(next - lstart, llen); 197 goto out; 198 } 199 200 /* 201 * lxd covered by xad 202 */ 203 xad = &p->xad[index]; 204 xoff = offsetXAD(xad); 205 xlen = lengthXAD(xad); 206 xend = xoff + xlen; 207 xaddr = addressXAD(xad); 208 209 /* initialize new pxd */ 210 *pflag = xad->flag; 211 *paddr = xaddr + (lstart - xoff); 212 /* a page must be fully covered by an xad */ 213 *plen = min(xend - lstart, llen); 214 215 out: 216 XT_PUTPAGE(mp); 217 218 return rc; 219 } 220 221 222 /* 223 * xtLookupList() 224 * 225 * function: map a single logical extent into a list of physical extent; 226 * 227 * parameter: 228 * struct inode *ip, 229 * struct lxdlist *lxdlist, lxd list (in) 230 * struct xadlist *xadlist, xad list (in/out) 231 * int flag) 232 * 233 * coverage of lxd by xad under assumption of 234 * . lxd's are ordered and disjoint. 235 * . xad's are ordered and disjoint. 236 * 237 * return: 238 * 0: success 239 * 240 * note: a page being written (even a single byte) is backed fully, 241 * except the last page which is only backed with blocks 242 * required to cover the last byte; 243 * the extent backing a page is fully contained within an xad; 244 */ 245 int xtLookupList(struct inode *ip, struct lxdlist * lxdlist, 246 struct xadlist * xadlist, int flag) 247 { 248 int rc = 0; 249 struct btstack btstack; 250 int cmp; 251 s64 bn; 252 struct metapage *mp; 253 xtpage_t *p; 254 int index; 255 lxd_t *lxd; 256 xad_t *xad, *pxd; 257 s64 size, lstart, lend, xstart, xend, pstart; 258 s64 llen, xlen, plen; 259 s64 xaddr, paddr; 260 int nlxd, npxd, maxnpxd; 261 262 npxd = xadlist->nxad = 0; 263 maxnpxd = xadlist->maxnxad; 264 pxd = xadlist->xad; 265 266 nlxd = lxdlist->nlxd; 267 lxd = lxdlist->lxd; 268 269 lstart = offsetLXD(lxd); 270 llen = lengthLXD(lxd); 271 lend = lstart + llen; 272 273 size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >> 274 JFS_SBI(ip->i_sb)->l2bsize; 275 276 /* 277 * search for the xad entry covering the logical extent 278 */ 279 search: 280 if (lstart >= size) 281 return 0; 282 283 if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0))) 284 return rc; 285 286 /* 287 * compute the physical extent covering logical extent 288 * 289 * N.B. search may have failed (e.g., hole in sparse file), 290 * and returned the index of the next entry. 291 */ 292 //map: 293 /* retrieve search result */ 294 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 295 296 /* is xad on the next sibling page ? */ 297 if (index == le16_to_cpu(p->header.nextindex)) { 298 if (p->header.flag & BT_ROOT) 299 goto mapend; 300 301 if ((bn = le64_to_cpu(p->header.next)) == 0) 302 goto mapend; 303 304 XT_PUTPAGE(mp); 305 306 /* get next sibling page */ 307 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 308 if (rc) 309 return rc; 310 311 index = XTENTRYSTART; 312 } 313 314 xad = &p->xad[index]; 315 316 /* 317 * is lxd covered by xad ? 318 */ 319 compare: 320 xstart = offsetXAD(xad); 321 xlen = lengthXAD(xad); 322 xend = xstart + xlen; 323 xaddr = addressXAD(xad); 324 325 compare1: 326 if (xstart < lstart) 327 goto compare2; 328 329 /* (lstart <= xstart) */ 330 331 /* lxd is NOT covered by xad */ 332 if (lend <= xstart) { 333 /* 334 * get next lxd 335 */ 336 if (--nlxd == 0) 337 goto mapend; 338 lxd++; 339 340 lstart = offsetLXD(lxd); 341 llen = lengthLXD(lxd); 342 lend = lstart + llen; 343 if (lstart >= size) 344 goto mapend; 345 346 /* compare with the current xad */ 347 goto compare1; 348 } 349 /* lxd is covered by xad */ 350 else { /* (xstart < lend) */ 351 352 /* initialize new pxd */ 353 pstart = xstart; 354 plen = min(lend - xstart, xlen); 355 paddr = xaddr; 356 357 goto cover; 358 } 359 360 /* (xstart < lstart) */ 361 compare2: 362 /* lxd is covered by xad */ 363 if (lstart < xend) { 364 /* initialize new pxd */ 365 pstart = lstart; 366 plen = min(xend - lstart, llen); 367 paddr = xaddr + (lstart - xstart); 368 369 goto cover; 370 } 371 /* lxd is NOT covered by xad */ 372 else { /* (xend <= lstart) */ 373 374 /* 375 * get next xad 376 * 377 * linear search next xad covering lxd on 378 * the current xad page, and then tree search 379 */ 380 if (index == le16_to_cpu(p->header.nextindex) - 1) { 381 if (p->header.flag & BT_ROOT) 382 goto mapend; 383 384 XT_PUTPAGE(mp); 385 goto search; 386 } else { 387 index++; 388 xad++; 389 390 /* compare with new xad */ 391 goto compare; 392 } 393 } 394 395 /* 396 * lxd is covered by xad and a new pxd has been initialized 397 * (lstart <= xstart < lend) or (xstart < lstart < xend) 398 */ 399 cover: 400 /* finalize pxd corresponding to current xad */ 401 XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr); 402 403 if (++npxd >= maxnpxd) 404 goto mapend; 405 pxd++; 406 407 /* 408 * lxd is fully covered by xad 409 */ 410 if (lend <= xend) { 411 /* 412 * get next lxd 413 */ 414 if (--nlxd == 0) 415 goto mapend; 416 lxd++; 417 418 lstart = offsetLXD(lxd); 419 llen = lengthLXD(lxd); 420 lend = lstart + llen; 421 if (lstart >= size) 422 goto mapend; 423 424 /* 425 * test for old xad covering new lxd 426 * (old xstart < new lstart) 427 */ 428 goto compare2; 429 } 430 /* 431 * lxd is partially covered by xad 432 */ 433 else { /* (xend < lend) */ 434 435 /* 436 * get next xad 437 * 438 * linear search next xad covering lxd on 439 * the current xad page, and then next xad page search 440 */ 441 if (index == le16_to_cpu(p->header.nextindex) - 1) { 442 if (p->header.flag & BT_ROOT) 443 goto mapend; 444 445 if ((bn = le64_to_cpu(p->header.next)) == 0) 446 goto mapend; 447 448 XT_PUTPAGE(mp); 449 450 /* get next sibling page */ 451 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 452 if (rc) 453 return rc; 454 455 index = XTENTRYSTART; 456 xad = &p->xad[index]; 457 } else { 458 index++; 459 xad++; 460 } 461 462 /* 463 * test for new xad covering old lxd 464 * (old lstart < new xstart) 465 */ 466 goto compare; 467 } 468 469 mapend: 470 xadlist->nxad = npxd; 471 472 //out: 473 XT_PUTPAGE(mp); 474 475 return rc; 476 } 477 478 479 /* 480 * xtSearch() 481 * 482 * function: search for the xad entry covering specified offset. 483 * 484 * parameters: 485 * ip - file object; 486 * xoff - extent offset; 487 * nextp - address of next extent (if any) for search miss 488 * cmpp - comparison result: 489 * btstack - traverse stack; 490 * flag - search process flag (XT_INSERT); 491 * 492 * returns: 493 * btstack contains (bn, index) of search path traversed to the entry. 494 * *cmpp is set to result of comparison with the entry returned. 495 * the page containing the entry is pinned at exit. 496 */ 497 static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp, 498 int *cmpp, struct btstack * btstack, int flag) 499 { 500 struct jfs_inode_info *jfs_ip = JFS_IP(ip); 501 int rc = 0; 502 int cmp = 1; /* init for empty page */ 503 s64 bn; /* block number */ 504 struct metapage *mp; /* page buffer */ 505 xtpage_t *p; /* page */ 506 xad_t *xad; 507 int base, index, lim, btindex; 508 struct btframe *btsp; 509 int nsplit = 0; /* number of pages to split */ 510 s64 t64; 511 s64 next = 0; 512 513 INCREMENT(xtStat.search); 514 515 BT_CLR(btstack); 516 517 btstack->nsplit = 0; 518 519 /* 520 * search down tree from root: 521 * 522 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of 523 * internal page, child page Pi contains entry with k, Ki <= K < Kj. 524 * 525 * if entry with search key K is not found 526 * internal page search find the entry with largest key Ki 527 * less than K which point to the child page to search; 528 * leaf page search find the entry with smallest key Kj 529 * greater than K so that the returned index is the position of 530 * the entry to be shifted right for insertion of new entry. 531 * for empty tree, search key is greater than any key of the tree. 532 * 533 * by convention, root bn = 0. 534 */ 535 for (bn = 0;;) { 536 /* get/pin the page to search */ 537 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 538 if (rc) 539 return rc; 540 541 /* try sequential access heuristics with the previous 542 * access entry in target leaf page: 543 * once search narrowed down into the target leaf, 544 * key must either match an entry in the leaf or 545 * key entry does not exist in the tree; 546 */ 547 //fastSearch: 548 if ((jfs_ip->btorder & BT_SEQUENTIAL) && 549 (p->header.flag & BT_LEAF) && 550 (index = jfs_ip->btindex) < 551 le16_to_cpu(p->header.nextindex)) { 552 xad = &p->xad[index]; 553 t64 = offsetXAD(xad); 554 if (xoff < t64 + lengthXAD(xad)) { 555 if (xoff >= t64) { 556 *cmpp = 0; 557 goto out; 558 } 559 560 /* stop sequential access heuristics */ 561 goto binarySearch; 562 } else { /* (t64 + lengthXAD(xad)) <= xoff */ 563 564 /* try next sequential entry */ 565 index++; 566 if (index < 567 le16_to_cpu(p->header.nextindex)) { 568 xad++; 569 t64 = offsetXAD(xad); 570 if (xoff < t64 + lengthXAD(xad)) { 571 if (xoff >= t64) { 572 *cmpp = 0; 573 goto out; 574 } 575 576 /* miss: key falls between 577 * previous and this entry 578 */ 579 *cmpp = 1; 580 next = t64; 581 goto out; 582 } 583 584 /* (xoff >= t64 + lengthXAD(xad)); 585 * matching entry may be further out: 586 * stop heuristic search 587 */ 588 /* stop sequential access heuristics */ 589 goto binarySearch; 590 } 591 592 /* (index == p->header.nextindex); 593 * miss: key entry does not exist in 594 * the target leaf/tree 595 */ 596 *cmpp = 1; 597 goto out; 598 } 599 600 /* 601 * if hit, return index of the entry found, and 602 * if miss, where new entry with search key is 603 * to be inserted; 604 */ 605 out: 606 /* compute number of pages to split */ 607 if (flag & XT_INSERT) { 608 if (p->header.nextindex == /* little-endian */ 609 p->header.maxentry) 610 nsplit++; 611 else 612 nsplit = 0; 613 btstack->nsplit = nsplit; 614 } 615 616 /* save search result */ 617 btsp = btstack->top; 618 btsp->bn = bn; 619 btsp->index = index; 620 btsp->mp = mp; 621 622 /* update sequential access heuristics */ 623 jfs_ip->btindex = index; 624 625 if (nextp) 626 *nextp = next; 627 628 INCREMENT(xtStat.fastSearch); 629 return 0; 630 } 631 632 /* well, ... full search now */ 633 binarySearch: 634 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART; 635 636 /* 637 * binary search with search key K on the current page 638 */ 639 for (base = XTENTRYSTART; lim; lim >>= 1) { 640 index = base + (lim >> 1); 641 642 XT_CMP(cmp, xoff, &p->xad[index], t64); 643 if (cmp == 0) { 644 /* 645 * search hit 646 */ 647 /* search hit - leaf page: 648 * return the entry found 649 */ 650 if (p->header.flag & BT_LEAF) { 651 *cmpp = cmp; 652 653 /* compute number of pages to split */ 654 if (flag & XT_INSERT) { 655 if (p->header.nextindex == 656 p->header.maxentry) 657 nsplit++; 658 else 659 nsplit = 0; 660 btstack->nsplit = nsplit; 661 } 662 663 /* save search result */ 664 btsp = btstack->top; 665 btsp->bn = bn; 666 btsp->index = index; 667 btsp->mp = mp; 668 669 /* init sequential access heuristics */ 670 btindex = jfs_ip->btindex; 671 if (index == btindex || 672 index == btindex + 1) 673 jfs_ip->btorder = BT_SEQUENTIAL; 674 else 675 jfs_ip->btorder = BT_RANDOM; 676 jfs_ip->btindex = index; 677 678 return 0; 679 } 680 /* search hit - internal page: 681 * descend/search its child page 682 */ 683 if (index < le16_to_cpu(p->header.nextindex)-1) 684 next = offsetXAD(&p->xad[index + 1]); 685 goto next; 686 } 687 688 if (cmp > 0) { 689 base = index + 1; 690 --lim; 691 } 692 } 693 694 /* 695 * search miss 696 * 697 * base is the smallest index with key (Kj) greater than 698 * search key (K) and may be zero or maxentry index. 699 */ 700 if (base < le16_to_cpu(p->header.nextindex)) 701 next = offsetXAD(&p->xad[base]); 702 /* 703 * search miss - leaf page: 704 * 705 * return location of entry (base) where new entry with 706 * search key K is to be inserted. 707 */ 708 if (p->header.flag & BT_LEAF) { 709 *cmpp = cmp; 710 711 /* compute number of pages to split */ 712 if (flag & XT_INSERT) { 713 if (p->header.nextindex == 714 p->header.maxentry) 715 nsplit++; 716 else 717 nsplit = 0; 718 btstack->nsplit = nsplit; 719 } 720 721 /* save search result */ 722 btsp = btstack->top; 723 btsp->bn = bn; 724 btsp->index = base; 725 btsp->mp = mp; 726 727 /* init sequential access heuristics */ 728 btindex = jfs_ip->btindex; 729 if (base == btindex || base == btindex + 1) 730 jfs_ip->btorder = BT_SEQUENTIAL; 731 else 732 jfs_ip->btorder = BT_RANDOM; 733 jfs_ip->btindex = base; 734 735 if (nextp) 736 *nextp = next; 737 738 return 0; 739 } 740 741 /* 742 * search miss - non-leaf page: 743 * 744 * if base is non-zero, decrement base by one to get the parent 745 * entry of the child page to search. 746 */ 747 index = base ? base - 1 : base; 748 749 /* 750 * go down to child page 751 */ 752 next: 753 /* update number of pages to split */ 754 if (p->header.nextindex == p->header.maxentry) 755 nsplit++; 756 else 757 nsplit = 0; 758 759 /* push (bn, index) of the parent page/entry */ 760 if (BT_STACK_FULL(btstack)) { 761 jfs_error(ip->i_sb, "stack overrun in xtSearch!"); 762 XT_PUTPAGE(mp); 763 return -EIO; 764 } 765 BT_PUSH(btstack, bn, index); 766 767 /* get the child page block number */ 768 bn = addressXAD(&p->xad[index]); 769 770 /* unpin the parent page */ 771 XT_PUTPAGE(mp); 772 } 773 } 774 775 /* 776 * xtInsert() 777 * 778 * function: 779 * 780 * parameter: 781 * tid - transaction id; 782 * ip - file object; 783 * xflag - extent flag (XAD_NOTRECORDED): 784 * xoff - extent offset; 785 * xlen - extent length; 786 * xaddrp - extent address pointer (in/out): 787 * if (*xaddrp) 788 * caller allocated data extent at *xaddrp; 789 * else 790 * allocate data extent and return its xaddr; 791 * flag - 792 * 793 * return: 794 */ 795 int xtInsert(tid_t tid, /* transaction id */ 796 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp, 797 int flag) 798 { 799 int rc = 0; 800 s64 xaddr, hint; 801 struct metapage *mp; /* meta-page buffer */ 802 xtpage_t *p; /* base B+-tree index page */ 803 s64 bn; 804 int index, nextindex; 805 struct btstack btstack; /* traverse stack */ 806 struct xtsplit split; /* split information */ 807 xad_t *xad; 808 int cmp; 809 s64 next; 810 struct tlock *tlck; 811 struct xtlock *xtlck; 812 813 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen); 814 815 /* 816 * search for the entry location at which to insert: 817 * 818 * xtFastSearch() and xtSearch() both returns (leaf page 819 * pinned, index at which to insert). 820 * n.b. xtSearch() may return index of maxentry of 821 * the full page. 822 */ 823 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT))) 824 return rc; 825 826 /* retrieve search result */ 827 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 828 829 /* This test must follow XT_GETSEARCH since mp must be valid if 830 * we branch to out: */ 831 if ((cmp == 0) || (next && (xlen > next - xoff))) { 832 rc = -EEXIST; 833 goto out; 834 } 835 836 /* 837 * allocate data extent requested 838 * 839 * allocation hint: last xad 840 */ 841 if ((xaddr = *xaddrp) == 0) { 842 if (index > XTENTRYSTART) { 843 xad = &p->xad[index - 1]; 844 hint = addressXAD(xad) + lengthXAD(xad) - 1; 845 } else 846 hint = 0; 847 if ((rc = DQUOT_ALLOC_BLOCK(ip, xlen))) 848 goto out; 849 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) { 850 DQUOT_FREE_BLOCK(ip, xlen); 851 goto out; 852 } 853 } 854 855 /* 856 * insert entry for new extent 857 */ 858 xflag |= XAD_NEW; 859 860 /* 861 * if the leaf page is full, split the page and 862 * propagate up the router entry for the new page from split 863 * 864 * The xtSplitUp() will insert the entry and unpin the leaf page. 865 */ 866 nextindex = le16_to_cpu(p->header.nextindex); 867 if (nextindex == le16_to_cpu(p->header.maxentry)) { 868 split.mp = mp; 869 split.index = index; 870 split.flag = xflag; 871 split.off = xoff; 872 split.len = xlen; 873 split.addr = xaddr; 874 split.pxdlist = NULL; 875 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) { 876 /* undo data extent allocation */ 877 if (*xaddrp == 0) { 878 dbFree(ip, xaddr, (s64) xlen); 879 DQUOT_FREE_BLOCK(ip, xlen); 880 } 881 return rc; 882 } 883 884 *xaddrp = xaddr; 885 return 0; 886 } 887 888 /* 889 * insert the new entry into the leaf page 890 */ 891 /* 892 * acquire a transaction lock on the leaf page; 893 * 894 * action: xad insertion/extension; 895 */ 896 BT_MARK_DIRTY(mp, ip); 897 898 /* if insert into middle, shift right remaining entries. */ 899 if (index < nextindex) 900 memmove(&p->xad[index + 1], &p->xad[index], 901 (nextindex - index) * sizeof(xad_t)); 902 903 /* insert the new entry: mark the entry NEW */ 904 xad = &p->xad[index]; 905 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); 906 907 /* advance next available entry index */ 908 le16_add_cpu(&p->header.nextindex, 1); 909 910 /* Don't log it if there are no links to the file */ 911 if (!test_cflag(COMMIT_Nolink, ip)) { 912 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 913 xtlck = (struct xtlock *) & tlck->lock; 914 xtlck->lwm.offset = 915 (xtlck->lwm.offset) ? min(index, 916 (int)xtlck->lwm.offset) : index; 917 xtlck->lwm.length = 918 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; 919 } 920 921 *xaddrp = xaddr; 922 923 out: 924 /* unpin the leaf page */ 925 XT_PUTPAGE(mp); 926 927 return rc; 928 } 929 930 931 /* 932 * xtSplitUp() 933 * 934 * function: 935 * split full pages as propagating insertion up the tree 936 * 937 * parameter: 938 * tid - transaction id; 939 * ip - file object; 940 * split - entry parameter descriptor; 941 * btstack - traverse stack from xtSearch() 942 * 943 * return: 944 */ 945 static int 946 xtSplitUp(tid_t tid, 947 struct inode *ip, struct xtsplit * split, struct btstack * btstack) 948 { 949 int rc = 0; 950 struct metapage *smp; 951 xtpage_t *sp; /* split page */ 952 struct metapage *rmp; 953 s64 rbn; /* new right page block number */ 954 struct metapage *rcmp; 955 xtpage_t *rcp; /* right child page */ 956 s64 rcbn; /* right child page block number */ 957 int skip; /* index of entry of insertion */ 958 int nextindex; /* next available entry index of p */ 959 struct btframe *parent; /* parent page entry on traverse stack */ 960 xad_t *xad; 961 s64 xaddr; 962 int xlen; 963 int nsplit; /* number of pages split */ 964 struct pxdlist pxdlist; 965 pxd_t *pxd; 966 struct tlock *tlck; 967 struct xtlock *xtlck; 968 969 smp = split->mp; 970 sp = XT_PAGE(ip, smp); 971 972 /* is inode xtree root extension/inline EA area free ? */ 973 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) && 974 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) && 975 (JFS_IP(ip)->mode2 & INLINEEA)) { 976 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT); 977 JFS_IP(ip)->mode2 &= ~INLINEEA; 978 979 BT_MARK_DIRTY(smp, ip); 980 /* 981 * acquire a transaction lock on the leaf page; 982 * 983 * action: xad insertion/extension; 984 */ 985 986 /* if insert into middle, shift right remaining entries. */ 987 skip = split->index; 988 nextindex = le16_to_cpu(sp->header.nextindex); 989 if (skip < nextindex) 990 memmove(&sp->xad[skip + 1], &sp->xad[skip], 991 (nextindex - skip) * sizeof(xad_t)); 992 993 /* insert the new entry: mark the entry NEW */ 994 xad = &sp->xad[skip]; 995 XT_PUTENTRY(xad, split->flag, split->off, split->len, 996 split->addr); 997 998 /* advance next available entry index */ 999 le16_add_cpu(&sp->header.nextindex, 1); 1000 1001 /* Don't log it if there are no links to the file */ 1002 if (!test_cflag(COMMIT_Nolink, ip)) { 1003 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW); 1004 xtlck = (struct xtlock *) & tlck->lock; 1005 xtlck->lwm.offset = (xtlck->lwm.offset) ? 1006 min(skip, (int)xtlck->lwm.offset) : skip; 1007 xtlck->lwm.length = 1008 le16_to_cpu(sp->header.nextindex) - 1009 xtlck->lwm.offset; 1010 } 1011 1012 return 0; 1013 } 1014 1015 /* 1016 * allocate new index blocks to cover index page split(s) 1017 * 1018 * allocation hint: ? 1019 */ 1020 if (split->pxdlist == NULL) { 1021 nsplit = btstack->nsplit; 1022 split->pxdlist = &pxdlist; 1023 pxdlist.maxnpxd = pxdlist.npxd = 0; 1024 pxd = &pxdlist.pxd[0]; 1025 xlen = JFS_SBI(ip->i_sb)->nbperpage; 1026 for (; nsplit > 0; nsplit--, pxd++) { 1027 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr)) 1028 == 0) { 1029 PXDaddress(pxd, xaddr); 1030 PXDlength(pxd, xlen); 1031 1032 pxdlist.maxnpxd++; 1033 1034 continue; 1035 } 1036 1037 /* undo allocation */ 1038 1039 XT_PUTPAGE(smp); 1040 return rc; 1041 } 1042 } 1043 1044 /* 1045 * Split leaf page <sp> into <sp> and a new right page <rp>. 1046 * 1047 * The split routines insert the new entry into the leaf page, 1048 * and acquire txLock as appropriate. 1049 * return <rp> pinned and its block number <rpbn>. 1050 */ 1051 rc = (sp->header.flag & BT_ROOT) ? 1052 xtSplitRoot(tid, ip, split, &rmp) : 1053 xtSplitPage(tid, ip, split, &rmp, &rbn); 1054 1055 XT_PUTPAGE(smp); 1056 1057 if (rc) 1058 return -EIO; 1059 /* 1060 * propagate up the router entry for the leaf page just split 1061 * 1062 * insert a router entry for the new page into the parent page, 1063 * propagate the insert/split up the tree by walking back the stack 1064 * of (bn of parent page, index of child page entry in parent page) 1065 * that were traversed during the search for the page that split. 1066 * 1067 * the propagation of insert/split up the tree stops if the root 1068 * splits or the page inserted into doesn't have to split to hold 1069 * the new entry. 1070 * 1071 * the parent entry for the split page remains the same, and 1072 * a new entry is inserted at its right with the first key and 1073 * block number of the new right page. 1074 * 1075 * There are a maximum of 3 pages pinned at any time: 1076 * right child, left parent and right parent (when the parent splits) 1077 * to keep the child page pinned while working on the parent. 1078 * make sure that all pins are released at exit. 1079 */ 1080 while ((parent = BT_POP(btstack)) != NULL) { 1081 /* parent page specified by stack frame <parent> */ 1082 1083 /* keep current child pages <rcp> pinned */ 1084 rcmp = rmp; 1085 rcbn = rbn; 1086 rcp = XT_PAGE(ip, rcmp); 1087 1088 /* 1089 * insert router entry in parent for new right child page <rp> 1090 */ 1091 /* get/pin the parent page <sp> */ 1092 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); 1093 if (rc) { 1094 XT_PUTPAGE(rcmp); 1095 return rc; 1096 } 1097 1098 /* 1099 * The new key entry goes ONE AFTER the index of parent entry, 1100 * because the split was to the right. 1101 */ 1102 skip = parent->index + 1; 1103 1104 /* 1105 * split or shift right remaining entries of the parent page 1106 */ 1107 nextindex = le16_to_cpu(sp->header.nextindex); 1108 /* 1109 * parent page is full - split the parent page 1110 */ 1111 if (nextindex == le16_to_cpu(sp->header.maxentry)) { 1112 /* init for parent page split */ 1113 split->mp = smp; 1114 split->index = skip; /* index at insert */ 1115 split->flag = XAD_NEW; 1116 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]); 1117 split->len = JFS_SBI(ip->i_sb)->nbperpage; 1118 split->addr = rcbn; 1119 1120 /* unpin previous right child page */ 1121 XT_PUTPAGE(rcmp); 1122 1123 /* The split routines insert the new entry, 1124 * and acquire txLock as appropriate. 1125 * return <rp> pinned and its block number <rpbn>. 1126 */ 1127 rc = (sp->header.flag & BT_ROOT) ? 1128 xtSplitRoot(tid, ip, split, &rmp) : 1129 xtSplitPage(tid, ip, split, &rmp, &rbn); 1130 if (rc) { 1131 XT_PUTPAGE(smp); 1132 return rc; 1133 } 1134 1135 XT_PUTPAGE(smp); 1136 /* keep new child page <rp> pinned */ 1137 } 1138 /* 1139 * parent page is not full - insert in parent page 1140 */ 1141 else { 1142 /* 1143 * insert router entry in parent for the right child 1144 * page from the first entry of the right child page: 1145 */ 1146 /* 1147 * acquire a transaction lock on the parent page; 1148 * 1149 * action: router xad insertion; 1150 */ 1151 BT_MARK_DIRTY(smp, ip); 1152 1153 /* 1154 * if insert into middle, shift right remaining entries 1155 */ 1156 if (skip < nextindex) 1157 memmove(&sp->xad[skip + 1], &sp->xad[skip], 1158 (nextindex - 1159 skip) << L2XTSLOTSIZE); 1160 1161 /* insert the router entry */ 1162 xad = &sp->xad[skip]; 1163 XT_PUTENTRY(xad, XAD_NEW, 1164 offsetXAD(&rcp->xad[XTENTRYSTART]), 1165 JFS_SBI(ip->i_sb)->nbperpage, rcbn); 1166 1167 /* advance next available entry index. */ 1168 le16_add_cpu(&sp->header.nextindex, 1); 1169 1170 /* Don't log it if there are no links to the file */ 1171 if (!test_cflag(COMMIT_Nolink, ip)) { 1172 tlck = txLock(tid, ip, smp, 1173 tlckXTREE | tlckGROW); 1174 xtlck = (struct xtlock *) & tlck->lock; 1175 xtlck->lwm.offset = (xtlck->lwm.offset) ? 1176 min(skip, (int)xtlck->lwm.offset) : skip; 1177 xtlck->lwm.length = 1178 le16_to_cpu(sp->header.nextindex) - 1179 xtlck->lwm.offset; 1180 } 1181 1182 /* unpin parent page */ 1183 XT_PUTPAGE(smp); 1184 1185 /* exit propagate up */ 1186 break; 1187 } 1188 } 1189 1190 /* unpin current right page */ 1191 XT_PUTPAGE(rmp); 1192 1193 return 0; 1194 } 1195 1196 1197 /* 1198 * xtSplitPage() 1199 * 1200 * function: 1201 * split a full non-root page into 1202 * original/split/left page and new right page 1203 * i.e., the original/split page remains as left page. 1204 * 1205 * parameter: 1206 * int tid, 1207 * struct inode *ip, 1208 * struct xtsplit *split, 1209 * struct metapage **rmpp, 1210 * u64 *rbnp, 1211 * 1212 * return: 1213 * Pointer to page in which to insert or NULL on error. 1214 */ 1215 static int 1216 xtSplitPage(tid_t tid, struct inode *ip, 1217 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp) 1218 { 1219 int rc = 0; 1220 struct metapage *smp; 1221 xtpage_t *sp; 1222 struct metapage *rmp; 1223 xtpage_t *rp; /* new right page allocated */ 1224 s64 rbn; /* new right page block number */ 1225 struct metapage *mp; 1226 xtpage_t *p; 1227 s64 nextbn; 1228 int skip, maxentry, middle, righthalf, n; 1229 xad_t *xad; 1230 struct pxdlist *pxdlist; 1231 pxd_t *pxd; 1232 struct tlock *tlck; 1233 struct xtlock *sxtlck = NULL, *rxtlck = NULL; 1234 int quota_allocation = 0; 1235 1236 smp = split->mp; 1237 sp = XT_PAGE(ip, smp); 1238 1239 INCREMENT(xtStat.split); 1240 1241 pxdlist = split->pxdlist; 1242 pxd = &pxdlist->pxd[pxdlist->npxd]; 1243 pxdlist->npxd++; 1244 rbn = addressPXD(pxd); 1245 1246 /* Allocate blocks to quota. */ 1247 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) { 1248 rc = -EDQUOT; 1249 goto clean_up; 1250 } 1251 1252 quota_allocation += lengthPXD(pxd); 1253 1254 /* 1255 * allocate the new right page for the split 1256 */ 1257 rmp = get_metapage(ip, rbn, PSIZE, 1); 1258 if (rmp == NULL) { 1259 rc = -EIO; 1260 goto clean_up; 1261 } 1262 1263 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp); 1264 1265 BT_MARK_DIRTY(rmp, ip); 1266 /* 1267 * action: new page; 1268 */ 1269 1270 rp = (xtpage_t *) rmp->data; 1271 rp->header.self = *pxd; 1272 rp->header.flag = sp->header.flag & BT_TYPE; 1273 rp->header.maxentry = sp->header.maxentry; /* little-endian */ 1274 rp->header.nextindex = cpu_to_le16(XTENTRYSTART); 1275 1276 BT_MARK_DIRTY(smp, ip); 1277 /* Don't log it if there are no links to the file */ 1278 if (!test_cflag(COMMIT_Nolink, ip)) { 1279 /* 1280 * acquire a transaction lock on the new right page; 1281 */ 1282 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW); 1283 rxtlck = (struct xtlock *) & tlck->lock; 1284 rxtlck->lwm.offset = XTENTRYSTART; 1285 /* 1286 * acquire a transaction lock on the split page 1287 */ 1288 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW); 1289 sxtlck = (struct xtlock *) & tlck->lock; 1290 } 1291 1292 /* 1293 * initialize/update sibling pointers of <sp> and <rp> 1294 */ 1295 nextbn = le64_to_cpu(sp->header.next); 1296 rp->header.next = cpu_to_le64(nextbn); 1297 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); 1298 sp->header.next = cpu_to_le64(rbn); 1299 1300 skip = split->index; 1301 1302 /* 1303 * sequential append at tail (after last entry of last page) 1304 * 1305 * if splitting the last page on a level because of appending 1306 * a entry to it (skip is maxentry), it's likely that the access is 1307 * sequential. adding an empty page on the side of the level is less 1308 * work and can push the fill factor much higher than normal. 1309 * if we're wrong it's no big deal - we will do the split the right 1310 * way next time. 1311 * (it may look like it's equally easy to do a similar hack for 1312 * reverse sorted data, that is, split the tree left, but it's not. 1313 * Be my guest.) 1314 */ 1315 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) { 1316 /* 1317 * acquire a transaction lock on the new/right page; 1318 * 1319 * action: xad insertion; 1320 */ 1321 /* insert entry at the first entry of the new right page */ 1322 xad = &rp->xad[XTENTRYSTART]; 1323 XT_PUTENTRY(xad, split->flag, split->off, split->len, 1324 split->addr); 1325 1326 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1); 1327 1328 if (!test_cflag(COMMIT_Nolink, ip)) { 1329 /* rxtlck->lwm.offset = XTENTRYSTART; */ 1330 rxtlck->lwm.length = 1; 1331 } 1332 1333 *rmpp = rmp; 1334 *rbnp = rbn; 1335 1336 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp); 1337 return 0; 1338 } 1339 1340 /* 1341 * non-sequential insert (at possibly middle page) 1342 */ 1343 1344 /* 1345 * update previous pointer of old next/right page of <sp> 1346 */ 1347 if (nextbn != 0) { 1348 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc); 1349 if (rc) { 1350 XT_PUTPAGE(rmp); 1351 goto clean_up; 1352 } 1353 1354 BT_MARK_DIRTY(mp, ip); 1355 /* 1356 * acquire a transaction lock on the next page; 1357 * 1358 * action:sibling pointer update; 1359 */ 1360 if (!test_cflag(COMMIT_Nolink, ip)) 1361 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK); 1362 1363 p->header.prev = cpu_to_le64(rbn); 1364 1365 /* sibling page may have been updated previously, or 1366 * it may be updated later; 1367 */ 1368 1369 XT_PUTPAGE(mp); 1370 } 1371 1372 /* 1373 * split the data between the split and new/right pages 1374 */ 1375 maxentry = le16_to_cpu(sp->header.maxentry); 1376 middle = maxentry >> 1; 1377 righthalf = maxentry - middle; 1378 1379 /* 1380 * skip index in old split/left page - insert into left page: 1381 */ 1382 if (skip <= middle) { 1383 /* move right half of split page to the new right page */ 1384 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle], 1385 righthalf << L2XTSLOTSIZE); 1386 1387 /* shift right tail of left half to make room for new entry */ 1388 if (skip < middle) 1389 memmove(&sp->xad[skip + 1], &sp->xad[skip], 1390 (middle - skip) << L2XTSLOTSIZE); 1391 1392 /* insert new entry */ 1393 xad = &sp->xad[skip]; 1394 XT_PUTENTRY(xad, split->flag, split->off, split->len, 1395 split->addr); 1396 1397 /* update page header */ 1398 sp->header.nextindex = cpu_to_le16(middle + 1); 1399 if (!test_cflag(COMMIT_Nolink, ip)) { 1400 sxtlck->lwm.offset = (sxtlck->lwm.offset) ? 1401 min(skip, (int)sxtlck->lwm.offset) : skip; 1402 } 1403 1404 rp->header.nextindex = 1405 cpu_to_le16(XTENTRYSTART + righthalf); 1406 } 1407 /* 1408 * skip index in new right page - insert into right page: 1409 */ 1410 else { 1411 /* move left head of right half to right page */ 1412 n = skip - middle; 1413 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle], 1414 n << L2XTSLOTSIZE); 1415 1416 /* insert new entry */ 1417 n += XTENTRYSTART; 1418 xad = &rp->xad[n]; 1419 XT_PUTENTRY(xad, split->flag, split->off, split->len, 1420 split->addr); 1421 1422 /* move right tail of right half to right page */ 1423 if (skip < maxentry) 1424 memmove(&rp->xad[n + 1], &sp->xad[skip], 1425 (maxentry - skip) << L2XTSLOTSIZE); 1426 1427 /* update page header */ 1428 sp->header.nextindex = cpu_to_le16(middle); 1429 if (!test_cflag(COMMIT_Nolink, ip)) { 1430 sxtlck->lwm.offset = (sxtlck->lwm.offset) ? 1431 min(middle, (int)sxtlck->lwm.offset) : middle; 1432 } 1433 1434 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1435 righthalf + 1); 1436 } 1437 1438 if (!test_cflag(COMMIT_Nolink, ip)) { 1439 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) - 1440 sxtlck->lwm.offset; 1441 1442 /* rxtlck->lwm.offset = XTENTRYSTART; */ 1443 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) - 1444 XTENTRYSTART; 1445 } 1446 1447 *rmpp = rmp; 1448 *rbnp = rbn; 1449 1450 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp); 1451 return rc; 1452 1453 clean_up: 1454 1455 /* Rollback quota allocation. */ 1456 if (quota_allocation) 1457 DQUOT_FREE_BLOCK(ip, quota_allocation); 1458 1459 return (rc); 1460 } 1461 1462 1463 /* 1464 * xtSplitRoot() 1465 * 1466 * function: 1467 * split the full root page into original/root/split page and new 1468 * right page 1469 * i.e., root remains fixed in tree anchor (inode) and the root is 1470 * copied to a single new right child page since root page << 1471 * non-root page, and the split root page contains a single entry 1472 * for the new right child page. 1473 * 1474 * parameter: 1475 * int tid, 1476 * struct inode *ip, 1477 * struct xtsplit *split, 1478 * struct metapage **rmpp) 1479 * 1480 * return: 1481 * Pointer to page in which to insert or NULL on error. 1482 */ 1483 static int 1484 xtSplitRoot(tid_t tid, 1485 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp) 1486 { 1487 xtpage_t *sp; 1488 struct metapage *rmp; 1489 xtpage_t *rp; 1490 s64 rbn; 1491 int skip, nextindex; 1492 xad_t *xad; 1493 pxd_t *pxd; 1494 struct pxdlist *pxdlist; 1495 struct tlock *tlck; 1496 struct xtlock *xtlck; 1497 1498 sp = &JFS_IP(ip)->i_xtroot; 1499 1500 INCREMENT(xtStat.split); 1501 1502 /* 1503 * allocate a single (right) child page 1504 */ 1505 pxdlist = split->pxdlist; 1506 pxd = &pxdlist->pxd[pxdlist->npxd]; 1507 pxdlist->npxd++; 1508 rbn = addressPXD(pxd); 1509 rmp = get_metapage(ip, rbn, PSIZE, 1); 1510 if (rmp == NULL) 1511 return -EIO; 1512 1513 /* Allocate blocks to quota. */ 1514 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) { 1515 release_metapage(rmp); 1516 return -EDQUOT; 1517 } 1518 1519 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp); 1520 1521 /* 1522 * acquire a transaction lock on the new right page; 1523 * 1524 * action: new page; 1525 */ 1526 BT_MARK_DIRTY(rmp, ip); 1527 1528 rp = (xtpage_t *) rmp->data; 1529 rp->header.flag = 1530 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; 1531 rp->header.self = *pxd; 1532 rp->header.nextindex = cpu_to_le16(XTENTRYSTART); 1533 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE); 1534 1535 /* initialize sibling pointers */ 1536 rp->header.next = 0; 1537 rp->header.prev = 0; 1538 1539 /* 1540 * copy the in-line root page into new right page extent 1541 */ 1542 nextindex = le16_to_cpu(sp->header.maxentry); 1543 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART], 1544 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE); 1545 1546 /* 1547 * insert the new entry into the new right/child page 1548 * (skip index in the new right page will not change) 1549 */ 1550 skip = split->index; 1551 /* if insert into middle, shift right remaining entries */ 1552 if (skip != nextindex) 1553 memmove(&rp->xad[skip + 1], &rp->xad[skip], 1554 (nextindex - skip) * sizeof(xad_t)); 1555 1556 xad = &rp->xad[skip]; 1557 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr); 1558 1559 /* update page header */ 1560 rp->header.nextindex = cpu_to_le16(nextindex + 1); 1561 1562 if (!test_cflag(COMMIT_Nolink, ip)) { 1563 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW); 1564 xtlck = (struct xtlock *) & tlck->lock; 1565 xtlck->lwm.offset = XTENTRYSTART; 1566 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) - 1567 XTENTRYSTART; 1568 } 1569 1570 /* 1571 * reset the root 1572 * 1573 * init root with the single entry for the new right page 1574 * set the 1st entry offset to 0, which force the left-most key 1575 * at any level of the tree to be less than any search key. 1576 */ 1577 /* 1578 * acquire a transaction lock on the root page (in-memory inode); 1579 * 1580 * action: root split; 1581 */ 1582 BT_MARK_DIRTY(split->mp, ip); 1583 1584 xad = &sp->xad[XTENTRYSTART]; 1585 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn); 1586 1587 /* update page header of root */ 1588 sp->header.flag &= ~BT_LEAF; 1589 sp->header.flag |= BT_INTERNAL; 1590 1591 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1); 1592 1593 if (!test_cflag(COMMIT_Nolink, ip)) { 1594 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW); 1595 xtlck = (struct xtlock *) & tlck->lock; 1596 xtlck->lwm.offset = XTENTRYSTART; 1597 xtlck->lwm.length = 1; 1598 } 1599 1600 *rmpp = rmp; 1601 1602 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp); 1603 return 0; 1604 } 1605 1606 1607 /* 1608 * xtExtend() 1609 * 1610 * function: extend in-place; 1611 * 1612 * note: existing extent may or may not have been committed. 1613 * caller is responsible for pager buffer cache update, and 1614 * working block allocation map update; 1615 * update pmap: alloc whole extended extent; 1616 */ 1617 int xtExtend(tid_t tid, /* transaction id */ 1618 struct inode *ip, s64 xoff, /* delta extent offset */ 1619 s32 xlen, /* delta extent length */ 1620 int flag) 1621 { 1622 int rc = 0; 1623 int cmp; 1624 struct metapage *mp; /* meta-page buffer */ 1625 xtpage_t *p; /* base B+-tree index page */ 1626 s64 bn; 1627 int index, nextindex, len; 1628 struct btstack btstack; /* traverse stack */ 1629 struct xtsplit split; /* split information */ 1630 xad_t *xad; 1631 s64 xaddr; 1632 struct tlock *tlck; 1633 struct xtlock *xtlck = NULL; 1634 1635 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen); 1636 1637 /* there must exist extent to be extended */ 1638 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT))) 1639 return rc; 1640 1641 /* retrieve search result */ 1642 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 1643 1644 if (cmp != 0) { 1645 XT_PUTPAGE(mp); 1646 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent"); 1647 return -EIO; 1648 } 1649 1650 /* extension must be contiguous */ 1651 xad = &p->xad[index]; 1652 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) { 1653 XT_PUTPAGE(mp); 1654 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous"); 1655 return -EIO; 1656 } 1657 1658 /* 1659 * acquire a transaction lock on the leaf page; 1660 * 1661 * action: xad insertion/extension; 1662 */ 1663 BT_MARK_DIRTY(mp, ip); 1664 if (!test_cflag(COMMIT_Nolink, ip)) { 1665 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 1666 xtlck = (struct xtlock *) & tlck->lock; 1667 } 1668 1669 /* extend will overflow extent ? */ 1670 xlen = lengthXAD(xad) + xlen; 1671 if ((len = xlen - MAXXLEN) <= 0) 1672 goto extendOld; 1673 1674 /* 1675 * extent overflow: insert entry for new extent 1676 */ 1677 //insertNew: 1678 xoff = offsetXAD(xad) + MAXXLEN; 1679 xaddr = addressXAD(xad) + MAXXLEN; 1680 nextindex = le16_to_cpu(p->header.nextindex); 1681 1682 /* 1683 * if the leaf page is full, insert the new entry and 1684 * propagate up the router entry for the new page from split 1685 * 1686 * The xtSplitUp() will insert the entry and unpin the leaf page. 1687 */ 1688 if (nextindex == le16_to_cpu(p->header.maxentry)) { 1689 /* xtSpliUp() unpins leaf pages */ 1690 split.mp = mp; 1691 split.index = index + 1; 1692 split.flag = XAD_NEW; 1693 split.off = xoff; /* split offset */ 1694 split.len = len; 1695 split.addr = xaddr; 1696 split.pxdlist = NULL; 1697 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) 1698 return rc; 1699 1700 /* get back old page */ 1701 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 1702 if (rc) 1703 return rc; 1704 /* 1705 * if leaf root has been split, original root has been 1706 * copied to new child page, i.e., original entry now 1707 * resides on the new child page; 1708 */ 1709 if (p->header.flag & BT_INTERNAL) { 1710 ASSERT(p->header.nextindex == 1711 cpu_to_le16(XTENTRYSTART + 1)); 1712 xad = &p->xad[XTENTRYSTART]; 1713 bn = addressXAD(xad); 1714 XT_PUTPAGE(mp); 1715 1716 /* get new child page */ 1717 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 1718 if (rc) 1719 return rc; 1720 1721 BT_MARK_DIRTY(mp, ip); 1722 if (!test_cflag(COMMIT_Nolink, ip)) { 1723 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); 1724 xtlck = (struct xtlock *) & tlck->lock; 1725 } 1726 } 1727 } 1728 /* 1729 * insert the new entry into the leaf page 1730 */ 1731 else { 1732 /* insert the new entry: mark the entry NEW */ 1733 xad = &p->xad[index + 1]; 1734 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr); 1735 1736 /* advance next available entry index */ 1737 le16_add_cpu(&p->header.nextindex, 1); 1738 } 1739 1740 /* get back old entry */ 1741 xad = &p->xad[index]; 1742 xlen = MAXXLEN; 1743 1744 /* 1745 * extend old extent 1746 */ 1747 extendOld: 1748 XADlength(xad, xlen); 1749 if (!(xad->flag & XAD_NEW)) 1750 xad->flag |= XAD_EXTENDED; 1751 1752 if (!test_cflag(COMMIT_Nolink, ip)) { 1753 xtlck->lwm.offset = 1754 (xtlck->lwm.offset) ? min(index, 1755 (int)xtlck->lwm.offset) : index; 1756 xtlck->lwm.length = 1757 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; 1758 } 1759 1760 /* unpin the leaf page */ 1761 XT_PUTPAGE(mp); 1762 1763 return rc; 1764 } 1765 1766 #ifdef _NOTYET 1767 /* 1768 * xtTailgate() 1769 * 1770 * function: split existing 'tail' extent 1771 * (split offset >= start offset of tail extent), and 1772 * relocate and extend the split tail half; 1773 * 1774 * note: existing extent may or may not have been committed. 1775 * caller is responsible for pager buffer cache update, and 1776 * working block allocation map update; 1777 * update pmap: free old split tail extent, alloc new extent; 1778 */ 1779 int xtTailgate(tid_t tid, /* transaction id */ 1780 struct inode *ip, s64 xoff, /* split/new extent offset */ 1781 s32 xlen, /* new extent length */ 1782 s64 xaddr, /* new extent address */ 1783 int flag) 1784 { 1785 int rc = 0; 1786 int cmp; 1787 struct metapage *mp; /* meta-page buffer */ 1788 xtpage_t *p; /* base B+-tree index page */ 1789 s64 bn; 1790 int index, nextindex, llen, rlen; 1791 struct btstack btstack; /* traverse stack */ 1792 struct xtsplit split; /* split information */ 1793 xad_t *xad; 1794 struct tlock *tlck; 1795 struct xtlock *xtlck = 0; 1796 struct tlock *mtlck; 1797 struct maplock *pxdlock; 1798 1799 /* 1800 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n", 1801 (ulong)xoff, xlen, (ulong)xaddr); 1802 */ 1803 1804 /* there must exist extent to be tailgated */ 1805 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT))) 1806 return rc; 1807 1808 /* retrieve search result */ 1809 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 1810 1811 if (cmp != 0) { 1812 XT_PUTPAGE(mp); 1813 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent"); 1814 return -EIO; 1815 } 1816 1817 /* entry found must be last entry */ 1818 nextindex = le16_to_cpu(p->header.nextindex); 1819 if (index != nextindex - 1) { 1820 XT_PUTPAGE(mp); 1821 jfs_error(ip->i_sb, 1822 "xtTailgate: the entry found is not the last entry"); 1823 return -EIO; 1824 } 1825 1826 BT_MARK_DIRTY(mp, ip); 1827 /* 1828 * acquire tlock of the leaf page containing original entry 1829 */ 1830 if (!test_cflag(COMMIT_Nolink, ip)) { 1831 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 1832 xtlck = (struct xtlock *) & tlck->lock; 1833 } 1834 1835 /* completely replace extent ? */ 1836 xad = &p->xad[index]; 1837 /* 1838 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n", 1839 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad)); 1840 */ 1841 if ((llen = xoff - offsetXAD(xad)) == 0) 1842 goto updateOld; 1843 1844 /* 1845 * partially replace extent: insert entry for new extent 1846 */ 1847 //insertNew: 1848 /* 1849 * if the leaf page is full, insert the new entry and 1850 * propagate up the router entry for the new page from split 1851 * 1852 * The xtSplitUp() will insert the entry and unpin the leaf page. 1853 */ 1854 if (nextindex == le16_to_cpu(p->header.maxentry)) { 1855 /* xtSpliUp() unpins leaf pages */ 1856 split.mp = mp; 1857 split.index = index + 1; 1858 split.flag = XAD_NEW; 1859 split.off = xoff; /* split offset */ 1860 split.len = xlen; 1861 split.addr = xaddr; 1862 split.pxdlist = NULL; 1863 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) 1864 return rc; 1865 1866 /* get back old page */ 1867 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 1868 if (rc) 1869 return rc; 1870 /* 1871 * if leaf root has been split, original root has been 1872 * copied to new child page, i.e., original entry now 1873 * resides on the new child page; 1874 */ 1875 if (p->header.flag & BT_INTERNAL) { 1876 ASSERT(p->header.nextindex == 1877 cpu_to_le16(XTENTRYSTART + 1)); 1878 xad = &p->xad[XTENTRYSTART]; 1879 bn = addressXAD(xad); 1880 XT_PUTPAGE(mp); 1881 1882 /* get new child page */ 1883 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 1884 if (rc) 1885 return rc; 1886 1887 BT_MARK_DIRTY(mp, ip); 1888 if (!test_cflag(COMMIT_Nolink, ip)) { 1889 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); 1890 xtlck = (struct xtlock *) & tlck->lock; 1891 } 1892 } 1893 } 1894 /* 1895 * insert the new entry into the leaf page 1896 */ 1897 else { 1898 /* insert the new entry: mark the entry NEW */ 1899 xad = &p->xad[index + 1]; 1900 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr); 1901 1902 /* advance next available entry index */ 1903 le16_add_cpu(&p->header.nextindex, 1); 1904 } 1905 1906 /* get back old XAD */ 1907 xad = &p->xad[index]; 1908 1909 /* 1910 * truncate/relocate old extent at split offset 1911 */ 1912 updateOld: 1913 /* update dmap for old/committed/truncated extent */ 1914 rlen = lengthXAD(xad) - llen; 1915 if (!(xad->flag & XAD_NEW)) { 1916 /* free from PWMAP at commit */ 1917 if (!test_cflag(COMMIT_Nolink, ip)) { 1918 mtlck = txMaplock(tid, ip, tlckMAP); 1919 pxdlock = (struct maplock *) & mtlck->lock; 1920 pxdlock->flag = mlckFREEPXD; 1921 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen); 1922 PXDlength(&pxdlock->pxd, rlen); 1923 pxdlock->index = 1; 1924 } 1925 } else 1926 /* free from WMAP */ 1927 dbFree(ip, addressXAD(xad) + llen, (s64) rlen); 1928 1929 if (llen) 1930 /* truncate */ 1931 XADlength(xad, llen); 1932 else 1933 /* replace */ 1934 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr); 1935 1936 if (!test_cflag(COMMIT_Nolink, ip)) { 1937 xtlck->lwm.offset = (xtlck->lwm.offset) ? 1938 min(index, (int)xtlck->lwm.offset) : index; 1939 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - 1940 xtlck->lwm.offset; 1941 } 1942 1943 /* unpin the leaf page */ 1944 XT_PUTPAGE(mp); 1945 1946 return rc; 1947 } 1948 #endif /* _NOTYET */ 1949 1950 /* 1951 * xtUpdate() 1952 * 1953 * function: update XAD; 1954 * 1955 * update extent for allocated_but_not_recorded or 1956 * compressed extent; 1957 * 1958 * parameter: 1959 * nxad - new XAD; 1960 * logical extent of the specified XAD must be completely 1961 * contained by an existing XAD; 1962 */ 1963 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad) 1964 { /* new XAD */ 1965 int rc = 0; 1966 int cmp; 1967 struct metapage *mp; /* meta-page buffer */ 1968 xtpage_t *p; /* base B+-tree index page */ 1969 s64 bn; 1970 int index0, index, newindex, nextindex; 1971 struct btstack btstack; /* traverse stack */ 1972 struct xtsplit split; /* split information */ 1973 xad_t *xad, *lxad, *rxad; 1974 int xflag; 1975 s64 nxoff, xoff; 1976 int nxlen, xlen, lxlen, rxlen; 1977 s64 nxaddr, xaddr; 1978 struct tlock *tlck; 1979 struct xtlock *xtlck = NULL; 1980 int newpage = 0; 1981 1982 /* there must exist extent to be tailgated */ 1983 nxoff = offsetXAD(nxad); 1984 nxlen = lengthXAD(nxad); 1985 nxaddr = addressXAD(nxad); 1986 1987 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT))) 1988 return rc; 1989 1990 /* retrieve search result */ 1991 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0); 1992 1993 if (cmp != 0) { 1994 XT_PUTPAGE(mp); 1995 jfs_error(ip->i_sb, "xtUpdate: Could not find extent"); 1996 return -EIO; 1997 } 1998 1999 BT_MARK_DIRTY(mp, ip); 2000 /* 2001 * acquire tlock of the leaf page containing original entry 2002 */ 2003 if (!test_cflag(COMMIT_Nolink, ip)) { 2004 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 2005 xtlck = (struct xtlock *) & tlck->lock; 2006 } 2007 2008 xad = &p->xad[index0]; 2009 xflag = xad->flag; 2010 xoff = offsetXAD(xad); 2011 xlen = lengthXAD(xad); 2012 xaddr = addressXAD(xad); 2013 2014 /* nXAD must be completely contained within XAD */ 2015 if ((xoff > nxoff) || 2016 (nxoff + nxlen > xoff + xlen)) { 2017 XT_PUTPAGE(mp); 2018 jfs_error(ip->i_sb, 2019 "xtUpdate: nXAD in not completely contained within XAD"); 2020 return -EIO; 2021 } 2022 2023 index = index0; 2024 newindex = index + 1; 2025 nextindex = le16_to_cpu(p->header.nextindex); 2026 2027 #ifdef _JFS_WIP_NOCOALESCE 2028 if (xoff < nxoff) 2029 goto updateRight; 2030 2031 /* 2032 * replace XAD with nXAD 2033 */ 2034 replace: /* (nxoff == xoff) */ 2035 if (nxlen == xlen) { 2036 /* replace XAD with nXAD:recorded */ 2037 *xad = *nxad; 2038 xad->flag = xflag & ~XAD_NOTRECORDED; 2039 2040 goto out; 2041 } else /* (nxlen < xlen) */ 2042 goto updateLeft; 2043 #endif /* _JFS_WIP_NOCOALESCE */ 2044 2045 /* #ifdef _JFS_WIP_COALESCE */ 2046 if (xoff < nxoff) 2047 goto coalesceRight; 2048 2049 /* 2050 * coalesce with left XAD 2051 */ 2052 //coalesceLeft: /* (xoff == nxoff) */ 2053 /* is XAD first entry of page ? */ 2054 if (index == XTENTRYSTART) 2055 goto replace; 2056 2057 /* is nXAD logically and physically contiguous with lXAD ? */ 2058 lxad = &p->xad[index - 1]; 2059 lxlen = lengthXAD(lxad); 2060 if (!(lxad->flag & XAD_NOTRECORDED) && 2061 (nxoff == offsetXAD(lxad) + lxlen) && 2062 (nxaddr == addressXAD(lxad) + lxlen) && 2063 (lxlen + nxlen < MAXXLEN)) { 2064 /* extend right lXAD */ 2065 index0 = index - 1; 2066 XADlength(lxad, lxlen + nxlen); 2067 2068 /* If we just merged two extents together, need to make sure the 2069 * right extent gets logged. If the left one is marked XAD_NEW, 2070 * then we know it will be logged. Otherwise, mark as 2071 * XAD_EXTENDED 2072 */ 2073 if (!(lxad->flag & XAD_NEW)) 2074 lxad->flag |= XAD_EXTENDED; 2075 2076 if (xlen > nxlen) { 2077 /* truncate XAD */ 2078 XADoffset(xad, xoff + nxlen); 2079 XADlength(xad, xlen - nxlen); 2080 XADaddress(xad, xaddr + nxlen); 2081 goto out; 2082 } else { /* (xlen == nxlen) */ 2083 2084 /* remove XAD */ 2085 if (index < nextindex - 1) 2086 memmove(&p->xad[index], &p->xad[index + 1], 2087 (nextindex - index - 2088 1) << L2XTSLOTSIZE); 2089 2090 p->header.nextindex = 2091 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 2092 1); 2093 2094 index = index0; 2095 newindex = index + 1; 2096 nextindex = le16_to_cpu(p->header.nextindex); 2097 xoff = nxoff = offsetXAD(lxad); 2098 xlen = nxlen = lxlen + nxlen; 2099 xaddr = nxaddr = addressXAD(lxad); 2100 goto coalesceRight; 2101 } 2102 } 2103 2104 /* 2105 * replace XAD with nXAD 2106 */ 2107 replace: /* (nxoff == xoff) */ 2108 if (nxlen == xlen) { 2109 /* replace XAD with nXAD:recorded */ 2110 *xad = *nxad; 2111 xad->flag = xflag & ~XAD_NOTRECORDED; 2112 2113 goto coalesceRight; 2114 } else /* (nxlen < xlen) */ 2115 goto updateLeft; 2116 2117 /* 2118 * coalesce with right XAD 2119 */ 2120 coalesceRight: /* (xoff <= nxoff) */ 2121 /* is XAD last entry of page ? */ 2122 if (newindex == nextindex) { 2123 if (xoff == nxoff) 2124 goto out; 2125 goto updateRight; 2126 } 2127 2128 /* is nXAD logically and physically contiguous with rXAD ? */ 2129 rxad = &p->xad[index + 1]; 2130 rxlen = lengthXAD(rxad); 2131 if (!(rxad->flag & XAD_NOTRECORDED) && 2132 (nxoff + nxlen == offsetXAD(rxad)) && 2133 (nxaddr + nxlen == addressXAD(rxad)) && 2134 (rxlen + nxlen < MAXXLEN)) { 2135 /* extend left rXAD */ 2136 XADoffset(rxad, nxoff); 2137 XADlength(rxad, rxlen + nxlen); 2138 XADaddress(rxad, nxaddr); 2139 2140 /* If we just merged two extents together, need to make sure 2141 * the left extent gets logged. If the right one is marked 2142 * XAD_NEW, then we know it will be logged. Otherwise, mark as 2143 * XAD_EXTENDED 2144 */ 2145 if (!(rxad->flag & XAD_NEW)) 2146 rxad->flag |= XAD_EXTENDED; 2147 2148 if (xlen > nxlen) 2149 /* truncate XAD */ 2150 XADlength(xad, xlen - nxlen); 2151 else { /* (xlen == nxlen) */ 2152 2153 /* remove XAD */ 2154 memmove(&p->xad[index], &p->xad[index + 1], 2155 (nextindex - index - 1) << L2XTSLOTSIZE); 2156 2157 p->header.nextindex = 2158 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 2159 1); 2160 } 2161 2162 goto out; 2163 } else if (xoff == nxoff) 2164 goto out; 2165 2166 if (xoff >= nxoff) { 2167 XT_PUTPAGE(mp); 2168 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff"); 2169 return -EIO; 2170 } 2171 /* #endif _JFS_WIP_COALESCE */ 2172 2173 /* 2174 * split XAD into (lXAD, nXAD): 2175 * 2176 * |---nXAD---> 2177 * --|----------XAD----------|-- 2178 * |-lXAD-| 2179 */ 2180 updateRight: /* (xoff < nxoff) */ 2181 /* truncate old XAD as lXAD:not_recorded */ 2182 xad = &p->xad[index]; 2183 XADlength(xad, nxoff - xoff); 2184 2185 /* insert nXAD:recorded */ 2186 if (nextindex == le16_to_cpu(p->header.maxentry)) { 2187 2188 /* xtSpliUp() unpins leaf pages */ 2189 split.mp = mp; 2190 split.index = newindex; 2191 split.flag = xflag & ~XAD_NOTRECORDED; 2192 split.off = nxoff; 2193 split.len = nxlen; 2194 split.addr = nxaddr; 2195 split.pxdlist = NULL; 2196 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) 2197 return rc; 2198 2199 /* get back old page */ 2200 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2201 if (rc) 2202 return rc; 2203 /* 2204 * if leaf root has been split, original root has been 2205 * copied to new child page, i.e., original entry now 2206 * resides on the new child page; 2207 */ 2208 if (p->header.flag & BT_INTERNAL) { 2209 ASSERT(p->header.nextindex == 2210 cpu_to_le16(XTENTRYSTART + 1)); 2211 xad = &p->xad[XTENTRYSTART]; 2212 bn = addressXAD(xad); 2213 XT_PUTPAGE(mp); 2214 2215 /* get new child page */ 2216 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2217 if (rc) 2218 return rc; 2219 2220 BT_MARK_DIRTY(mp, ip); 2221 if (!test_cflag(COMMIT_Nolink, ip)) { 2222 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); 2223 xtlck = (struct xtlock *) & tlck->lock; 2224 } 2225 } else { 2226 /* is nXAD on new page ? */ 2227 if (newindex > 2228 (le16_to_cpu(p->header.maxentry) >> 1)) { 2229 newindex = 2230 newindex - 2231 le16_to_cpu(p->header.nextindex) + 2232 XTENTRYSTART; 2233 newpage = 1; 2234 } 2235 } 2236 } else { 2237 /* if insert into middle, shift right remaining entries */ 2238 if (newindex < nextindex) 2239 memmove(&p->xad[newindex + 1], &p->xad[newindex], 2240 (nextindex - newindex) << L2XTSLOTSIZE); 2241 2242 /* insert the entry */ 2243 xad = &p->xad[newindex]; 2244 *xad = *nxad; 2245 xad->flag = xflag & ~XAD_NOTRECORDED; 2246 2247 /* advance next available entry index. */ 2248 p->header.nextindex = 2249 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1); 2250 } 2251 2252 /* 2253 * does nXAD force 3-way split ? 2254 * 2255 * |---nXAD--->| 2256 * --|----------XAD-------------|-- 2257 * |-lXAD-| |-rXAD -| 2258 */ 2259 if (nxoff + nxlen == xoff + xlen) 2260 goto out; 2261 2262 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */ 2263 if (newpage) { 2264 /* close out old page */ 2265 if (!test_cflag(COMMIT_Nolink, ip)) { 2266 xtlck->lwm.offset = (xtlck->lwm.offset) ? 2267 min(index0, (int)xtlck->lwm.offset) : index0; 2268 xtlck->lwm.length = 2269 le16_to_cpu(p->header.nextindex) - 2270 xtlck->lwm.offset; 2271 } 2272 2273 bn = le64_to_cpu(p->header.next); 2274 XT_PUTPAGE(mp); 2275 2276 /* get new right page */ 2277 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2278 if (rc) 2279 return rc; 2280 2281 BT_MARK_DIRTY(mp, ip); 2282 if (!test_cflag(COMMIT_Nolink, ip)) { 2283 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 2284 xtlck = (struct xtlock *) & tlck->lock; 2285 } 2286 2287 index0 = index = newindex; 2288 } else 2289 index++; 2290 2291 newindex = index + 1; 2292 nextindex = le16_to_cpu(p->header.nextindex); 2293 xlen = xlen - (nxoff - xoff); 2294 xoff = nxoff; 2295 xaddr = nxaddr; 2296 2297 /* recompute split pages */ 2298 if (nextindex == le16_to_cpu(p->header.maxentry)) { 2299 XT_PUTPAGE(mp); 2300 2301 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT))) 2302 return rc; 2303 2304 /* retrieve search result */ 2305 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0); 2306 2307 if (cmp != 0) { 2308 XT_PUTPAGE(mp); 2309 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed"); 2310 return -EIO; 2311 } 2312 2313 if (index0 != index) { 2314 XT_PUTPAGE(mp); 2315 jfs_error(ip->i_sb, 2316 "xtUpdate: unexpected value of index"); 2317 return -EIO; 2318 } 2319 } 2320 2321 /* 2322 * split XAD into (nXAD, rXAD) 2323 * 2324 * ---nXAD---| 2325 * --|----------XAD----------|-- 2326 * |-rXAD-| 2327 */ 2328 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */ 2329 /* update old XAD with nXAD:recorded */ 2330 xad = &p->xad[index]; 2331 *xad = *nxad; 2332 xad->flag = xflag & ~XAD_NOTRECORDED; 2333 2334 /* insert rXAD:not_recorded */ 2335 xoff = xoff + nxlen; 2336 xlen = xlen - nxlen; 2337 xaddr = xaddr + nxlen; 2338 if (nextindex == le16_to_cpu(p->header.maxentry)) { 2339 /* 2340 printf("xtUpdate.updateLeft.split p:0x%p\n", p); 2341 */ 2342 /* xtSpliUp() unpins leaf pages */ 2343 split.mp = mp; 2344 split.index = newindex; 2345 split.flag = xflag; 2346 split.off = xoff; 2347 split.len = xlen; 2348 split.addr = xaddr; 2349 split.pxdlist = NULL; 2350 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) 2351 return rc; 2352 2353 /* get back old page */ 2354 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2355 if (rc) 2356 return rc; 2357 2358 /* 2359 * if leaf root has been split, original root has been 2360 * copied to new child page, i.e., original entry now 2361 * resides on the new child page; 2362 */ 2363 if (p->header.flag & BT_INTERNAL) { 2364 ASSERT(p->header.nextindex == 2365 cpu_to_le16(XTENTRYSTART + 1)); 2366 xad = &p->xad[XTENTRYSTART]; 2367 bn = addressXAD(xad); 2368 XT_PUTPAGE(mp); 2369 2370 /* get new child page */ 2371 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2372 if (rc) 2373 return rc; 2374 2375 BT_MARK_DIRTY(mp, ip); 2376 if (!test_cflag(COMMIT_Nolink, ip)) { 2377 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); 2378 xtlck = (struct xtlock *) & tlck->lock; 2379 } 2380 } 2381 } else { 2382 /* if insert into middle, shift right remaining entries */ 2383 if (newindex < nextindex) 2384 memmove(&p->xad[newindex + 1], &p->xad[newindex], 2385 (nextindex - newindex) << L2XTSLOTSIZE); 2386 2387 /* insert the entry */ 2388 xad = &p->xad[newindex]; 2389 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); 2390 2391 /* advance next available entry index. */ 2392 p->header.nextindex = 2393 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1); 2394 } 2395 2396 out: 2397 if (!test_cflag(COMMIT_Nolink, ip)) { 2398 xtlck->lwm.offset = (xtlck->lwm.offset) ? 2399 min(index0, (int)xtlck->lwm.offset) : index0; 2400 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - 2401 xtlck->lwm.offset; 2402 } 2403 2404 /* unpin the leaf page */ 2405 XT_PUTPAGE(mp); 2406 2407 return rc; 2408 } 2409 2410 2411 /* 2412 * xtAppend() 2413 * 2414 * function: grow in append mode from contiguous region specified ; 2415 * 2416 * parameter: 2417 * tid - transaction id; 2418 * ip - file object; 2419 * xflag - extent flag: 2420 * xoff - extent offset; 2421 * maxblocks - max extent length; 2422 * xlen - extent length (in/out); 2423 * xaddrp - extent address pointer (in/out): 2424 * flag - 2425 * 2426 * return: 2427 */ 2428 int xtAppend(tid_t tid, /* transaction id */ 2429 struct inode *ip, int xflag, s64 xoff, s32 maxblocks, 2430 s32 * xlenp, /* (in/out) */ 2431 s64 * xaddrp, /* (in/out) */ 2432 int flag) 2433 { 2434 int rc = 0; 2435 struct metapage *mp; /* meta-page buffer */ 2436 xtpage_t *p; /* base B+-tree index page */ 2437 s64 bn, xaddr; 2438 int index, nextindex; 2439 struct btstack btstack; /* traverse stack */ 2440 struct xtsplit split; /* split information */ 2441 xad_t *xad; 2442 int cmp; 2443 struct tlock *tlck; 2444 struct xtlock *xtlck; 2445 int nsplit, nblocks, xlen; 2446 struct pxdlist pxdlist; 2447 pxd_t *pxd; 2448 s64 next; 2449 2450 xaddr = *xaddrp; 2451 xlen = *xlenp; 2452 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx", 2453 (ulong) xoff, maxblocks, xlen, (ulong) xaddr); 2454 2455 /* 2456 * search for the entry location at which to insert: 2457 * 2458 * xtFastSearch() and xtSearch() both returns (leaf page 2459 * pinned, index at which to insert). 2460 * n.b. xtSearch() may return index of maxentry of 2461 * the full page. 2462 */ 2463 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT))) 2464 return rc; 2465 2466 /* retrieve search result */ 2467 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 2468 2469 if (cmp == 0) { 2470 rc = -EEXIST; 2471 goto out; 2472 } 2473 2474 if (next) 2475 xlen = min(xlen, (int)(next - xoff)); 2476 //insert: 2477 /* 2478 * insert entry for new extent 2479 */ 2480 xflag |= XAD_NEW; 2481 2482 /* 2483 * if the leaf page is full, split the page and 2484 * propagate up the router entry for the new page from split 2485 * 2486 * The xtSplitUp() will insert the entry and unpin the leaf page. 2487 */ 2488 nextindex = le16_to_cpu(p->header.nextindex); 2489 if (nextindex < le16_to_cpu(p->header.maxentry)) 2490 goto insertLeaf; 2491 2492 /* 2493 * allocate new index blocks to cover index page split(s) 2494 */ 2495 nsplit = btstack.nsplit; 2496 split.pxdlist = &pxdlist; 2497 pxdlist.maxnpxd = pxdlist.npxd = 0; 2498 pxd = &pxdlist.pxd[0]; 2499 nblocks = JFS_SBI(ip->i_sb)->nbperpage; 2500 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) { 2501 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) { 2502 PXDaddress(pxd, xaddr); 2503 PXDlength(pxd, nblocks); 2504 2505 pxdlist.maxnpxd++; 2506 2507 continue; 2508 } 2509 2510 /* undo allocation */ 2511 2512 goto out; 2513 } 2514 2515 xlen = min(xlen, maxblocks); 2516 2517 /* 2518 * allocate data extent requested 2519 */ 2520 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen))) 2521 goto out; 2522 2523 split.mp = mp; 2524 split.index = index; 2525 split.flag = xflag; 2526 split.off = xoff; 2527 split.len = xlen; 2528 split.addr = xaddr; 2529 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) { 2530 /* undo data extent allocation */ 2531 dbFree(ip, *xaddrp, (s64) * xlenp); 2532 2533 return rc; 2534 } 2535 2536 *xaddrp = xaddr; 2537 *xlenp = xlen; 2538 return 0; 2539 2540 /* 2541 * insert the new entry into the leaf page 2542 */ 2543 insertLeaf: 2544 /* 2545 * allocate data extent requested 2546 */ 2547 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen))) 2548 goto out; 2549 2550 BT_MARK_DIRTY(mp, ip); 2551 /* 2552 * acquire a transaction lock on the leaf page; 2553 * 2554 * action: xad insertion/extension; 2555 */ 2556 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); 2557 xtlck = (struct xtlock *) & tlck->lock; 2558 2559 /* insert the new entry: mark the entry NEW */ 2560 xad = &p->xad[index]; 2561 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); 2562 2563 /* advance next available entry index */ 2564 le16_add_cpu(&p->header.nextindex, 1); 2565 2566 xtlck->lwm.offset = 2567 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index; 2568 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - 2569 xtlck->lwm.offset; 2570 2571 *xaddrp = xaddr; 2572 *xlenp = xlen; 2573 2574 out: 2575 /* unpin the leaf page */ 2576 XT_PUTPAGE(mp); 2577 2578 return rc; 2579 } 2580 #ifdef _STILL_TO_PORT 2581 2582 /* - TBD for defragmentaion/reorganization - 2583 * 2584 * xtDelete() 2585 * 2586 * function: 2587 * delete the entry with the specified key. 2588 * 2589 * N.B.: whole extent of the entry is assumed to be deleted. 2590 * 2591 * parameter: 2592 * 2593 * return: 2594 * ENOENT: if the entry is not found. 2595 * 2596 * exception: 2597 */ 2598 int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag) 2599 { 2600 int rc = 0; 2601 struct btstack btstack; 2602 int cmp; 2603 s64 bn; 2604 struct metapage *mp; 2605 xtpage_t *p; 2606 int index, nextindex; 2607 struct tlock *tlck; 2608 struct xtlock *xtlck; 2609 2610 /* 2611 * find the matching entry; xtSearch() pins the page 2612 */ 2613 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0))) 2614 return rc; 2615 2616 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 2617 if (cmp) { 2618 /* unpin the leaf page */ 2619 XT_PUTPAGE(mp); 2620 return -ENOENT; 2621 } 2622 2623 /* 2624 * delete the entry from the leaf page 2625 */ 2626 nextindex = le16_to_cpu(p->header.nextindex); 2627 le16_add_cpu(&p->header.nextindex, -1); 2628 2629 /* 2630 * if the leaf page bocome empty, free the page 2631 */ 2632 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART)) 2633 return (xtDeleteUp(tid, ip, mp, p, &btstack)); 2634 2635 BT_MARK_DIRTY(mp, ip); 2636 /* 2637 * acquire a transaction lock on the leaf page; 2638 * 2639 * action:xad deletion; 2640 */ 2641 tlck = txLock(tid, ip, mp, tlckXTREE); 2642 xtlck = (struct xtlock *) & tlck->lock; 2643 xtlck->lwm.offset = 2644 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index; 2645 2646 /* if delete from middle, shift left/compact the remaining entries */ 2647 if (index < nextindex - 1) 2648 memmove(&p->xad[index], &p->xad[index + 1], 2649 (nextindex - index - 1) * sizeof(xad_t)); 2650 2651 XT_PUTPAGE(mp); 2652 2653 return 0; 2654 } 2655 2656 2657 /* - TBD for defragmentaion/reorganization - 2658 * 2659 * xtDeleteUp() 2660 * 2661 * function: 2662 * free empty pages as propagating deletion up the tree 2663 * 2664 * parameter: 2665 * 2666 * return: 2667 */ 2668 static int 2669 xtDeleteUp(tid_t tid, struct inode *ip, 2670 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack) 2671 { 2672 int rc = 0; 2673 struct metapage *mp; 2674 xtpage_t *p; 2675 int index, nextindex; 2676 s64 xaddr; 2677 int xlen; 2678 struct btframe *parent; 2679 struct tlock *tlck; 2680 struct xtlock *xtlck; 2681 2682 /* 2683 * keep root leaf page which has become empty 2684 */ 2685 if (fp->header.flag & BT_ROOT) { 2686 /* keep the root page */ 2687 fp->header.flag &= ~BT_INTERNAL; 2688 fp->header.flag |= BT_LEAF; 2689 fp->header.nextindex = cpu_to_le16(XTENTRYSTART); 2690 2691 /* XT_PUTPAGE(fmp); */ 2692 2693 return 0; 2694 } 2695 2696 /* 2697 * free non-root leaf page 2698 */ 2699 if ((rc = xtRelink(tid, ip, fp))) { 2700 XT_PUTPAGE(fmp); 2701 return rc; 2702 } 2703 2704 xaddr = addressPXD(&fp->header.self); 2705 xlen = lengthPXD(&fp->header.self); 2706 /* free the page extent */ 2707 dbFree(ip, xaddr, (s64) xlen); 2708 2709 /* free the buffer page */ 2710 discard_metapage(fmp); 2711 2712 /* 2713 * propagate page deletion up the index tree 2714 * 2715 * If the delete from the parent page makes it empty, 2716 * continue all the way up the tree. 2717 * stop if the root page is reached (which is never deleted) or 2718 * if the entry deletion does not empty the page. 2719 */ 2720 while ((parent = BT_POP(btstack)) != NULL) { 2721 /* get/pin the parent page <sp> */ 2722 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); 2723 if (rc) 2724 return rc; 2725 2726 index = parent->index; 2727 2728 /* delete the entry for the freed child page from parent. 2729 */ 2730 nextindex = le16_to_cpu(p->header.nextindex); 2731 2732 /* 2733 * the parent has the single entry being deleted: 2734 * free the parent page which has become empty. 2735 */ 2736 if (nextindex == 1) { 2737 if (p->header.flag & BT_ROOT) { 2738 /* keep the root page */ 2739 p->header.flag &= ~BT_INTERNAL; 2740 p->header.flag |= BT_LEAF; 2741 p->header.nextindex = 2742 cpu_to_le16(XTENTRYSTART); 2743 2744 /* XT_PUTPAGE(mp); */ 2745 2746 break; 2747 } else { 2748 /* free the parent page */ 2749 if ((rc = xtRelink(tid, ip, p))) 2750 return rc; 2751 2752 xaddr = addressPXD(&p->header.self); 2753 /* free the page extent */ 2754 dbFree(ip, xaddr, 2755 (s64) JFS_SBI(ip->i_sb)->nbperpage); 2756 2757 /* unpin/free the buffer page */ 2758 discard_metapage(mp); 2759 2760 /* propagate up */ 2761 continue; 2762 } 2763 } 2764 /* 2765 * the parent has other entries remaining: 2766 * delete the router entry from the parent page. 2767 */ 2768 else { 2769 BT_MARK_DIRTY(mp, ip); 2770 /* 2771 * acquire a transaction lock on the leaf page; 2772 * 2773 * action:xad deletion; 2774 */ 2775 tlck = txLock(tid, ip, mp, tlckXTREE); 2776 xtlck = (struct xtlock *) & tlck->lock; 2777 xtlck->lwm.offset = 2778 (xtlck->lwm.offset) ? min(index, 2779 xtlck->lwm. 2780 offset) : index; 2781 2782 /* if delete from middle, 2783 * shift left/compact the remaining entries in the page 2784 */ 2785 if (index < nextindex - 1) 2786 memmove(&p->xad[index], &p->xad[index + 1], 2787 (nextindex - index - 2788 1) << L2XTSLOTSIZE); 2789 2790 le16_add_cpu(&p->header.nextindex, -1); 2791 jfs_info("xtDeleteUp(entry): 0x%lx[%d]", 2792 (ulong) parent->bn, index); 2793 } 2794 2795 /* unpin the parent page */ 2796 XT_PUTPAGE(mp); 2797 2798 /* exit propagation up */ 2799 break; 2800 } 2801 2802 return 0; 2803 } 2804 2805 2806 /* 2807 * NAME: xtRelocate() 2808 * 2809 * FUNCTION: relocate xtpage or data extent of regular file; 2810 * This function is mainly used by defragfs utility. 2811 * 2812 * NOTE: This routine does not have the logic to handle 2813 * uncommitted allocated extent. The caller should call 2814 * txCommit() to commit all the allocation before call 2815 * this routine. 2816 */ 2817 int 2818 xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */ 2819 s64 nxaddr, /* new xaddr */ 2820 int xtype) 2821 { /* extent type: XTPAGE or DATAEXT */ 2822 int rc = 0; 2823 struct tblock *tblk; 2824 struct tlock *tlck; 2825 struct xtlock *xtlck; 2826 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */ 2827 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */ 2828 xad_t *xad; 2829 pxd_t *pxd; 2830 s64 xoff, xsize; 2831 int xlen; 2832 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn; 2833 cbuf_t *cp; 2834 s64 offset, nbytes, nbrd, pno; 2835 int nb, npages, nblks; 2836 s64 bn; 2837 int cmp; 2838 int index; 2839 struct pxd_lock *pxdlock; 2840 struct btstack btstack; /* traverse stack */ 2841 2842 xtype = xtype & EXTENT_TYPE; 2843 2844 xoff = offsetXAD(oxad); 2845 oxaddr = addressXAD(oxad); 2846 xlen = lengthXAD(oxad); 2847 2848 /* validate extent offset */ 2849 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize; 2850 if (offset >= ip->i_size) 2851 return -ESTALE; /* stale extent */ 2852 2853 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx", 2854 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr); 2855 2856 /* 2857 * 1. get and validate the parent xtpage/xad entry 2858 * covering the source extent to be relocated; 2859 */ 2860 if (xtype == DATAEXT) { 2861 /* search in leaf entry */ 2862 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0); 2863 if (rc) 2864 return rc; 2865 2866 /* retrieve search result */ 2867 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); 2868 2869 if (cmp) { 2870 XT_PUTPAGE(pmp); 2871 return -ESTALE; 2872 } 2873 2874 /* validate for exact match with a single entry */ 2875 xad = &pp->xad[index]; 2876 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) { 2877 XT_PUTPAGE(pmp); 2878 return -ESTALE; 2879 } 2880 } else { /* (xtype == XTPAGE) */ 2881 2882 /* search in internal entry */ 2883 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0); 2884 if (rc) 2885 return rc; 2886 2887 /* retrieve search result */ 2888 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); 2889 2890 if (cmp) { 2891 XT_PUTPAGE(pmp); 2892 return -ESTALE; 2893 } 2894 2895 /* xtSearchNode() validated for exact match with a single entry 2896 */ 2897 xad = &pp->xad[index]; 2898 } 2899 jfs_info("xtRelocate: parent xad entry validated."); 2900 2901 /* 2902 * 2. relocate the extent 2903 */ 2904 if (xtype == DATAEXT) { 2905 /* if the extent is allocated-but-not-recorded 2906 * there is no real data to be moved in this extent, 2907 */ 2908 if (xad->flag & XAD_NOTRECORDED) 2909 goto out; 2910 else 2911 /* release xtpage for cmRead()/xtLookup() */ 2912 XT_PUTPAGE(pmp); 2913 2914 /* 2915 * cmRelocate() 2916 * 2917 * copy target data pages to be relocated; 2918 * 2919 * data extent must start at page boundary and 2920 * multiple of page size (except the last data extent); 2921 * read in each page of the source data extent into cbuf, 2922 * update the cbuf extent descriptor of the page to be 2923 * homeward bound to new dst data extent 2924 * copy the data from the old extent to new extent. 2925 * copy is essential for compressed files to avoid problems 2926 * that can arise if there was a change in compression 2927 * algorithms. 2928 * it is a good strategy because it may disrupt cache 2929 * policy to keep the pages in memory afterwards. 2930 */ 2931 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize; 2932 assert((offset & CM_OFFSET) == 0); 2933 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize; 2934 pno = offset >> CM_L2BSIZE; 2935 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE; 2936 /* 2937 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) - 2938 (offset >> CM_L2BSIZE) + 1; 2939 */ 2940 sxaddr = oxaddr; 2941 dxaddr = nxaddr; 2942 2943 /* process the request one cache buffer at a time */ 2944 for (nbrd = 0; nbrd < nbytes; nbrd += nb, 2945 offset += nb, pno++, npages--) { 2946 /* compute page size */ 2947 nb = min(nbytes - nbrd, CM_BSIZE); 2948 2949 /* get the cache buffer of the page */ 2950 if (rc = cmRead(ip, offset, npages, &cp)) 2951 break; 2952 2953 assert(addressPXD(&cp->cm_pxd) == sxaddr); 2954 assert(!cp->cm_modified); 2955 2956 /* bind buffer with the new extent address */ 2957 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize; 2958 cmSetXD(ip, cp, pno, dxaddr, nblks); 2959 2960 /* release the cbuf, mark it as modified */ 2961 cmPut(cp, true); 2962 2963 dxaddr += nblks; 2964 sxaddr += nblks; 2965 } 2966 2967 /* get back parent page */ 2968 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0))) 2969 return rc; 2970 2971 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); 2972 jfs_info("xtRelocate: target data extent relocated."); 2973 } else { /* (xtype == XTPAGE) */ 2974 2975 /* 2976 * read in the target xtpage from the source extent; 2977 */ 2978 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc); 2979 if (rc) { 2980 XT_PUTPAGE(pmp); 2981 return rc; 2982 } 2983 2984 /* 2985 * read in sibling pages if any to update sibling pointers; 2986 */ 2987 rmp = NULL; 2988 if (p->header.next) { 2989 nextbn = le64_to_cpu(p->header.next); 2990 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc); 2991 if (rc) { 2992 XT_PUTPAGE(pmp); 2993 XT_PUTPAGE(mp); 2994 return (rc); 2995 } 2996 } 2997 2998 lmp = NULL; 2999 if (p->header.prev) { 3000 prevbn = le64_to_cpu(p->header.prev); 3001 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc); 3002 if (rc) { 3003 XT_PUTPAGE(pmp); 3004 XT_PUTPAGE(mp); 3005 if (rmp) 3006 XT_PUTPAGE(rmp); 3007 return (rc); 3008 } 3009 } 3010 3011 /* at this point, all xtpages to be updated are in memory */ 3012 3013 /* 3014 * update sibling pointers of sibling xtpages if any; 3015 */ 3016 if (lmp) { 3017 BT_MARK_DIRTY(lmp, ip); 3018 tlck = txLock(tid, ip, lmp, tlckXTREE | tlckRELINK); 3019 lp->header.next = cpu_to_le64(nxaddr); 3020 XT_PUTPAGE(lmp); 3021 } 3022 3023 if (rmp) { 3024 BT_MARK_DIRTY(rmp, ip); 3025 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckRELINK); 3026 rp->header.prev = cpu_to_le64(nxaddr); 3027 XT_PUTPAGE(rmp); 3028 } 3029 3030 /* 3031 * update the target xtpage to be relocated 3032 * 3033 * update the self address of the target page 3034 * and write to destination extent; 3035 * redo image covers the whole xtpage since it is new page 3036 * to the destination extent; 3037 * update of bmap for the free of source extent 3038 * of the target xtpage itself: 3039 * update of bmap for the allocation of destination extent 3040 * of the target xtpage itself: 3041 * update of bmap for the extents covered by xad entries in 3042 * the target xtpage is not necessary since they are not 3043 * updated; 3044 * if not committed before this relocation, 3045 * target page may contain XAD_NEW entries which must 3046 * be scanned for bmap update (logredo() always 3047 * scan xtpage REDOPAGE image for bmap update); 3048 * if committed before this relocation (tlckRELOCATE), 3049 * scan may be skipped by commit() and logredo(); 3050 */ 3051 BT_MARK_DIRTY(mp, ip); 3052 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */ 3053 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW); 3054 xtlck = (struct xtlock *) & tlck->lock; 3055 3056 /* update the self address in the xtpage header */ 3057 pxd = &p->header.self; 3058 PXDaddress(pxd, nxaddr); 3059 3060 /* linelock for the after image of the whole page */ 3061 xtlck->lwm.length = 3062 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; 3063 3064 /* update the buffer extent descriptor of target xtpage */ 3065 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize; 3066 bmSetXD(mp, nxaddr, xsize); 3067 3068 /* unpin the target page to new homeward bound */ 3069 XT_PUTPAGE(mp); 3070 jfs_info("xtRelocate: target xtpage relocated."); 3071 } 3072 3073 /* 3074 * 3. acquire maplock for the source extent to be freed; 3075 * 3076 * acquire a maplock saving the src relocated extent address; 3077 * to free of the extent at commit time; 3078 */ 3079 out: 3080 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for 3081 * free PXD of the source data extent (logredo() will update 3082 * bmap for free of source data extent), and update bmap for 3083 * free of the source data extent; 3084 */ 3085 if (xtype == DATAEXT) 3086 tlck = txMaplock(tid, ip, tlckMAP); 3087 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record 3088 * for the source xtpage (logredo() will init NoRedoPage 3089 * filter and will also update bmap for free of the source 3090 * xtpage), and update bmap for free of the source xtpage; 3091 * N.B. We use tlckMAP instead of tlkcXTREE because there 3092 * is no buffer associated with this lock since the buffer 3093 * has been redirected to the target location. 3094 */ 3095 else /* (xtype == XTPAGE) */ 3096 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE); 3097 3098 pxdlock = (struct pxd_lock *) & tlck->lock; 3099 pxdlock->flag = mlckFREEPXD; 3100 PXDaddress(&pxdlock->pxd, oxaddr); 3101 PXDlength(&pxdlock->pxd, xlen); 3102 pxdlock->index = 1; 3103 3104 /* 3105 * 4. update the parent xad entry for relocation; 3106 * 3107 * acquire tlck for the parent entry with XAD_NEW as entry 3108 * update which will write LOG_REDOPAGE and update bmap for 3109 * allocation of XAD_NEW destination extent; 3110 */ 3111 jfs_info("xtRelocate: update parent xad entry."); 3112 BT_MARK_DIRTY(pmp, ip); 3113 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW); 3114 xtlck = (struct xtlock *) & tlck->lock; 3115 3116 /* update the XAD with the new destination extent; */ 3117 xad = &pp->xad[index]; 3118 xad->flag |= XAD_NEW; 3119 XADaddress(xad, nxaddr); 3120 3121 xtlck->lwm.offset = min(index, xtlck->lwm.offset); 3122 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) - 3123 xtlck->lwm.offset; 3124 3125 /* unpin the parent xtpage */ 3126 XT_PUTPAGE(pmp); 3127 3128 return rc; 3129 } 3130 3131 3132 /* 3133 * xtSearchNode() 3134 * 3135 * function: search for the internal xad entry covering specified extent. 3136 * This function is mainly used by defragfs utility. 3137 * 3138 * parameters: 3139 * ip - file object; 3140 * xad - extent to find; 3141 * cmpp - comparison result: 3142 * btstack - traverse stack; 3143 * flag - search process flag; 3144 * 3145 * returns: 3146 * btstack contains (bn, index) of search path traversed to the entry. 3147 * *cmpp is set to result of comparison with the entry returned. 3148 * the page containing the entry is pinned at exit. 3149 */ 3150 static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */ 3151 int *cmpp, struct btstack * btstack, int flag) 3152 { 3153 int rc = 0; 3154 s64 xoff, xaddr; 3155 int xlen; 3156 int cmp = 1; /* init for empty page */ 3157 s64 bn; /* block number */ 3158 struct metapage *mp; /* meta-page buffer */ 3159 xtpage_t *p; /* page */ 3160 int base, index, lim; 3161 struct btframe *btsp; 3162 s64 t64; 3163 3164 BT_CLR(btstack); 3165 3166 xoff = offsetXAD(xad); 3167 xlen = lengthXAD(xad); 3168 xaddr = addressXAD(xad); 3169 3170 /* 3171 * search down tree from root: 3172 * 3173 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of 3174 * internal page, child page Pi contains entry with k, Ki <= K < Kj. 3175 * 3176 * if entry with search key K is not found 3177 * internal page search find the entry with largest key Ki 3178 * less than K which point to the child page to search; 3179 * leaf page search find the entry with smallest key Kj 3180 * greater than K so that the returned index is the position of 3181 * the entry to be shifted right for insertion of new entry. 3182 * for empty tree, search key is greater than any key of the tree. 3183 * 3184 * by convention, root bn = 0. 3185 */ 3186 for (bn = 0;;) { 3187 /* get/pin the page to search */ 3188 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3189 if (rc) 3190 return rc; 3191 if (p->header.flag & BT_LEAF) { 3192 XT_PUTPAGE(mp); 3193 return -ESTALE; 3194 } 3195 3196 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART; 3197 3198 /* 3199 * binary search with search key K on the current page 3200 */ 3201 for (base = XTENTRYSTART; lim; lim >>= 1) { 3202 index = base + (lim >> 1); 3203 3204 XT_CMP(cmp, xoff, &p->xad[index], t64); 3205 if (cmp == 0) { 3206 /* 3207 * search hit 3208 * 3209 * verify for exact match; 3210 */ 3211 if (xaddr == addressXAD(&p->xad[index]) && 3212 xoff == offsetXAD(&p->xad[index])) { 3213 *cmpp = cmp; 3214 3215 /* save search result */ 3216 btsp = btstack->top; 3217 btsp->bn = bn; 3218 btsp->index = index; 3219 btsp->mp = mp; 3220 3221 return 0; 3222 } 3223 3224 /* descend/search its child page */ 3225 goto next; 3226 } 3227 3228 if (cmp > 0) { 3229 base = index + 1; 3230 --lim; 3231 } 3232 } 3233 3234 /* 3235 * search miss - non-leaf page: 3236 * 3237 * base is the smallest index with key (Kj) greater than 3238 * search key (K) and may be zero or maxentry index. 3239 * if base is non-zero, decrement base by one to get the parent 3240 * entry of the child page to search. 3241 */ 3242 index = base ? base - 1 : base; 3243 3244 /* 3245 * go down to child page 3246 */ 3247 next: 3248 /* get the child page block number */ 3249 bn = addressXAD(&p->xad[index]); 3250 3251 /* unpin the parent page */ 3252 XT_PUTPAGE(mp); 3253 } 3254 } 3255 3256 3257 /* 3258 * xtRelink() 3259 * 3260 * function: 3261 * link around a freed page. 3262 * 3263 * Parameter: 3264 * int tid, 3265 * struct inode *ip, 3266 * xtpage_t *p) 3267 * 3268 * returns: 3269 */ 3270 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p) 3271 { 3272 int rc = 0; 3273 struct metapage *mp; 3274 s64 nextbn, prevbn; 3275 struct tlock *tlck; 3276 3277 nextbn = le64_to_cpu(p->header.next); 3278 prevbn = le64_to_cpu(p->header.prev); 3279 3280 /* update prev pointer of the next page */ 3281 if (nextbn != 0) { 3282 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc); 3283 if (rc) 3284 return rc; 3285 3286 /* 3287 * acquire a transaction lock on the page; 3288 * 3289 * action: update prev pointer; 3290 */ 3291 BT_MARK_DIRTY(mp, ip); 3292 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK); 3293 3294 /* the page may already have been tlock'd */ 3295 3296 p->header.prev = cpu_to_le64(prevbn); 3297 3298 XT_PUTPAGE(mp); 3299 } 3300 3301 /* update next pointer of the previous page */ 3302 if (prevbn != 0) { 3303 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc); 3304 if (rc) 3305 return rc; 3306 3307 /* 3308 * acquire a transaction lock on the page; 3309 * 3310 * action: update next pointer; 3311 */ 3312 BT_MARK_DIRTY(mp, ip); 3313 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK); 3314 3315 /* the page may already have been tlock'd */ 3316 3317 p->header.next = le64_to_cpu(nextbn); 3318 3319 XT_PUTPAGE(mp); 3320 } 3321 3322 return 0; 3323 } 3324 #endif /* _STILL_TO_PORT */ 3325 3326 3327 /* 3328 * xtInitRoot() 3329 * 3330 * initialize file root (inline in inode) 3331 */ 3332 void xtInitRoot(tid_t tid, struct inode *ip) 3333 { 3334 xtpage_t *p; 3335 3336 /* 3337 * acquire a transaction lock on the root 3338 * 3339 * action: 3340 */ 3341 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag, 3342 tlckXTREE | tlckNEW); 3343 p = &JFS_IP(ip)->i_xtroot; 3344 3345 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; 3346 p->header.nextindex = cpu_to_le16(XTENTRYSTART); 3347 3348 if (S_ISDIR(ip->i_mode)) 3349 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR); 3350 else { 3351 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT); 3352 ip->i_size = 0; 3353 } 3354 3355 3356 return; 3357 } 3358 3359 3360 /* 3361 * We can run into a deadlock truncating a file with a large number of 3362 * xtree pages (large fragmented file). A robust fix would entail a 3363 * reservation system where we would reserve a number of metadata pages 3364 * and tlocks which we would be guaranteed without a deadlock. Without 3365 * this, a partial fix is to limit number of metadata pages we will lock 3366 * in a single transaction. Currently we will truncate the file so that 3367 * no more than 50 leaf pages will be locked. The caller of xtTruncate 3368 * will be responsible for ensuring that the current transaction gets 3369 * committed, and that subsequent transactions are created to truncate 3370 * the file further if needed. 3371 */ 3372 #define MAX_TRUNCATE_LEAVES 50 3373 3374 /* 3375 * xtTruncate() 3376 * 3377 * function: 3378 * traverse for truncation logging backward bottom up; 3379 * terminate at the last extent entry at the current subtree 3380 * root page covering new down size. 3381 * truncation may occur within the last extent entry. 3382 * 3383 * parameter: 3384 * int tid, 3385 * struct inode *ip, 3386 * s64 newsize, 3387 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE} 3388 * 3389 * return: 3390 * 3391 * note: 3392 * PWMAP: 3393 * 1. truncate (non-COMMIT_NOLINK file) 3394 * by jfs_truncate() or jfs_open(O_TRUNC): 3395 * xtree is updated; 3396 * 2. truncate index table of directory when last entry removed 3397 * map update via tlock at commit time; 3398 * PMAP: 3399 * Call xtTruncate_pmap instead 3400 * WMAP: 3401 * 1. remove (free zero link count) on last reference release 3402 * (pmap has been freed at commit zero link count); 3403 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file): 3404 * xtree is updated; 3405 * map update directly at truncation time; 3406 * 3407 * if (DELETE) 3408 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient); 3409 * else if (TRUNCATE) 3410 * must write LOG_NOREDOPAGE for deleted index page; 3411 * 3412 * pages may already have been tlocked by anonymous transactions 3413 * during file growth (i.e., write) before truncation; 3414 * 3415 * except last truncated entry, deleted entries remains as is 3416 * in the page (nextindex is updated) for other use 3417 * (e.g., log/update allocation map): this avoid copying the page 3418 * info but delay free of pages; 3419 * 3420 */ 3421 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag) 3422 { 3423 int rc = 0; 3424 s64 teof; 3425 struct metapage *mp; 3426 xtpage_t *p; 3427 s64 bn; 3428 int index, nextindex; 3429 xad_t *xad; 3430 s64 xoff, xaddr; 3431 int xlen, len, freexlen; 3432 struct btstack btstack; 3433 struct btframe *parent; 3434 struct tblock *tblk = NULL; 3435 struct tlock *tlck = NULL; 3436 struct xtlock *xtlck = NULL; 3437 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */ 3438 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */ 3439 s64 nfreed; 3440 int freed, log; 3441 int locked_leaves = 0; 3442 3443 /* save object truncation type */ 3444 if (tid) { 3445 tblk = tid_to_tblock(tid); 3446 tblk->xflag |= flag; 3447 } 3448 3449 nfreed = 0; 3450 3451 flag &= COMMIT_MAP; 3452 assert(flag != COMMIT_PMAP); 3453 3454 if (flag == COMMIT_PWMAP) 3455 log = 1; 3456 else { 3457 log = 0; 3458 xadlock.flag = mlckFREEXADLIST; 3459 xadlock.index = 1; 3460 } 3461 3462 /* 3463 * if the newsize is not an integral number of pages, 3464 * the file between newsize and next page boundary will 3465 * be cleared. 3466 * if truncating into a file hole, it will cause 3467 * a full block to be allocated for the logical block. 3468 */ 3469 3470 /* 3471 * release page blocks of truncated region <teof, eof> 3472 * 3473 * free the data blocks from the leaf index blocks. 3474 * delete the parent index entries corresponding to 3475 * the freed child data/index blocks. 3476 * free the index blocks themselves which aren't needed 3477 * in new sized file. 3478 * 3479 * index blocks are updated only if the blocks are to be 3480 * retained in the new sized file. 3481 * if type is PMAP, the data and index pages are NOT 3482 * freed, and the data and index blocks are NOT freed 3483 * from working map. 3484 * (this will allow continued access of data/index of 3485 * temporary file (zerolink count file truncated to zero-length)). 3486 */ 3487 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >> 3488 JFS_SBI(ip->i_sb)->l2bsize; 3489 3490 /* clear stack */ 3491 BT_CLR(&btstack); 3492 3493 /* 3494 * start with root 3495 * 3496 * root resides in the inode 3497 */ 3498 bn = 0; 3499 3500 /* 3501 * first access of each page: 3502 */ 3503 getPage: 3504 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3505 if (rc) 3506 return rc; 3507 3508 /* process entries backward from last index */ 3509 index = le16_to_cpu(p->header.nextindex) - 1; 3510 3511 3512 /* Since this is the rightmost page at this level, and we may have 3513 * already freed a page that was formerly to the right, let's make 3514 * sure that the next pointer is zero. 3515 */ 3516 if (p->header.next) { 3517 if (log) 3518 /* 3519 * Make sure this change to the header is logged. 3520 * If we really truncate this leaf, the flag 3521 * will be changed to tlckTRUNCATE 3522 */ 3523 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); 3524 BT_MARK_DIRTY(mp, ip); 3525 p->header.next = 0; 3526 } 3527 3528 if (p->header.flag & BT_INTERNAL) 3529 goto getChild; 3530 3531 /* 3532 * leaf page 3533 */ 3534 freed = 0; 3535 3536 /* does region covered by leaf page precede Teof ? */ 3537 xad = &p->xad[index]; 3538 xoff = offsetXAD(xad); 3539 xlen = lengthXAD(xad); 3540 if (teof >= xoff + xlen) { 3541 XT_PUTPAGE(mp); 3542 goto getParent; 3543 } 3544 3545 /* (re)acquire tlock of the leaf page */ 3546 if (log) { 3547 if (++locked_leaves > MAX_TRUNCATE_LEAVES) { 3548 /* 3549 * We need to limit the size of the transaction 3550 * to avoid exhausting pagecache & tlocks 3551 */ 3552 XT_PUTPAGE(mp); 3553 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize; 3554 goto getParent; 3555 } 3556 tlck = txLock(tid, ip, mp, tlckXTREE); 3557 tlck->type = tlckXTREE | tlckTRUNCATE; 3558 xtlck = (struct xtlock *) & tlck->lock; 3559 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1; 3560 } 3561 BT_MARK_DIRTY(mp, ip); 3562 3563 /* 3564 * scan backward leaf page entries 3565 */ 3566 for (; index >= XTENTRYSTART; index--) { 3567 xad = &p->xad[index]; 3568 xoff = offsetXAD(xad); 3569 xlen = lengthXAD(xad); 3570 xaddr = addressXAD(xad); 3571 3572 /* 3573 * The "data" for a directory is indexed by the block 3574 * device's address space. This metadata must be invalidated 3575 * here 3576 */ 3577 if (S_ISDIR(ip->i_mode) && (teof == 0)) 3578 invalidate_xad_metapages(ip, *xad); 3579 /* 3580 * entry beyond eof: continue scan of current page 3581 * xad 3582 * ---|---=======-------> 3583 * eof 3584 */ 3585 if (teof < xoff) { 3586 nfreed += xlen; 3587 continue; 3588 } 3589 3590 /* 3591 * (xoff <= teof): last entry to be deleted from page; 3592 * If other entries remain in page: keep and update the page. 3593 */ 3594 3595 /* 3596 * eof == entry_start: delete the entry 3597 * xad 3598 * -------|=======-------> 3599 * eof 3600 * 3601 */ 3602 if (teof == xoff) { 3603 nfreed += xlen; 3604 3605 if (index == XTENTRYSTART) 3606 break; 3607 3608 nextindex = index; 3609 } 3610 /* 3611 * eof within the entry: truncate the entry. 3612 * xad 3613 * -------===|===-------> 3614 * eof 3615 */ 3616 else if (teof < xoff + xlen) { 3617 /* update truncated entry */ 3618 len = teof - xoff; 3619 freexlen = xlen - len; 3620 XADlength(xad, len); 3621 3622 /* save pxd of truncated extent in tlck */ 3623 xaddr += len; 3624 if (log) { /* COMMIT_PWMAP */ 3625 xtlck->lwm.offset = (xtlck->lwm.offset) ? 3626 min(index, (int)xtlck->lwm.offset) : index; 3627 xtlck->lwm.length = index + 1 - 3628 xtlck->lwm.offset; 3629 xtlck->twm.offset = index; 3630 pxdlock = (struct pxd_lock *) & xtlck->pxdlock; 3631 pxdlock->flag = mlckFREEPXD; 3632 PXDaddress(&pxdlock->pxd, xaddr); 3633 PXDlength(&pxdlock->pxd, freexlen); 3634 } 3635 /* free truncated extent */ 3636 else { /* COMMIT_WMAP */ 3637 3638 pxdlock = (struct pxd_lock *) & xadlock; 3639 pxdlock->flag = mlckFREEPXD; 3640 PXDaddress(&pxdlock->pxd, xaddr); 3641 PXDlength(&pxdlock->pxd, freexlen); 3642 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP); 3643 3644 /* reset map lock */ 3645 xadlock.flag = mlckFREEXADLIST; 3646 } 3647 3648 /* current entry is new last entry; */ 3649 nextindex = index + 1; 3650 3651 nfreed += freexlen; 3652 } 3653 /* 3654 * eof beyond the entry: 3655 * xad 3656 * -------=======---|---> 3657 * eof 3658 */ 3659 else { /* (xoff + xlen < teof) */ 3660 3661 nextindex = index + 1; 3662 } 3663 3664 if (nextindex < le16_to_cpu(p->header.nextindex)) { 3665 if (!log) { /* COMMIT_WAMP */ 3666 xadlock.xdlist = &p->xad[nextindex]; 3667 xadlock.count = 3668 le16_to_cpu(p->header.nextindex) - 3669 nextindex; 3670 txFreeMap(ip, (struct maplock *) & xadlock, 3671 NULL, COMMIT_WMAP); 3672 } 3673 p->header.nextindex = cpu_to_le16(nextindex); 3674 } 3675 3676 XT_PUTPAGE(mp); 3677 3678 /* assert(freed == 0); */ 3679 goto getParent; 3680 } /* end scan of leaf page entries */ 3681 3682 freed = 1; 3683 3684 /* 3685 * leaf page become empty: free the page if type != PMAP 3686 */ 3687 if (log) { /* COMMIT_PWMAP */ 3688 /* txCommit() with tlckFREE: 3689 * free data extents covered by leaf [XTENTRYSTART:hwm); 3690 * invalidate leaf if COMMIT_PWMAP; 3691 * if (TRUNCATE), will write LOG_NOREDOPAGE; 3692 */ 3693 tlck->type = tlckXTREE | tlckFREE; 3694 } else { /* COMMIT_WAMP */ 3695 3696 /* free data extents covered by leaf */ 3697 xadlock.xdlist = &p->xad[XTENTRYSTART]; 3698 xadlock.count = 3699 le16_to_cpu(p->header.nextindex) - XTENTRYSTART; 3700 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP); 3701 } 3702 3703 if (p->header.flag & BT_ROOT) { 3704 p->header.flag &= ~BT_INTERNAL; 3705 p->header.flag |= BT_LEAF; 3706 p->header.nextindex = cpu_to_le16(XTENTRYSTART); 3707 3708 XT_PUTPAGE(mp); /* debug */ 3709 goto out; 3710 } else { 3711 if (log) { /* COMMIT_PWMAP */ 3712 /* page will be invalidated at tx completion 3713 */ 3714 XT_PUTPAGE(mp); 3715 } else { /* COMMIT_WMAP */ 3716 3717 if (mp->lid) 3718 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK; 3719 3720 /* invalidate empty leaf page */ 3721 discard_metapage(mp); 3722 } 3723 } 3724 3725 /* 3726 * the leaf page become empty: delete the parent entry 3727 * for the leaf page if the parent page is to be kept 3728 * in the new sized file. 3729 */ 3730 3731 /* 3732 * go back up to the parent page 3733 */ 3734 getParent: 3735 /* pop/restore parent entry for the current child page */ 3736 if ((parent = BT_POP(&btstack)) == NULL) 3737 /* current page must have been root */ 3738 goto out; 3739 3740 /* get back the parent page */ 3741 bn = parent->bn; 3742 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3743 if (rc) 3744 return rc; 3745 3746 index = parent->index; 3747 3748 /* 3749 * child page was not empty: 3750 */ 3751 if (freed == 0) { 3752 /* has any entry deleted from parent ? */ 3753 if (index < le16_to_cpu(p->header.nextindex) - 1) { 3754 /* (re)acquire tlock on the parent page */ 3755 if (log) { /* COMMIT_PWMAP */ 3756 /* txCommit() with tlckTRUNCATE: 3757 * free child extents covered by parent [); 3758 */ 3759 tlck = txLock(tid, ip, mp, tlckXTREE); 3760 xtlck = (struct xtlock *) & tlck->lock; 3761 if (!(tlck->type & tlckTRUNCATE)) { 3762 xtlck->hwm.offset = 3763 le16_to_cpu(p->header. 3764 nextindex) - 1; 3765 tlck->type = 3766 tlckXTREE | tlckTRUNCATE; 3767 } 3768 } else { /* COMMIT_WMAP */ 3769 3770 /* free child extents covered by parent */ 3771 xadlock.xdlist = &p->xad[index + 1]; 3772 xadlock.count = 3773 le16_to_cpu(p->header.nextindex) - 3774 index - 1; 3775 txFreeMap(ip, (struct maplock *) & xadlock, 3776 NULL, COMMIT_WMAP); 3777 } 3778 BT_MARK_DIRTY(mp, ip); 3779 3780 p->header.nextindex = cpu_to_le16(index + 1); 3781 } 3782 XT_PUTPAGE(mp); 3783 goto getParent; 3784 } 3785 3786 /* 3787 * child page was empty: 3788 */ 3789 nfreed += lengthXAD(&p->xad[index]); 3790 3791 /* 3792 * During working map update, child page's tlock must be handled 3793 * before parent's. This is because the parent's tlock will cause 3794 * the child's disk space to be marked available in the wmap, so 3795 * it's important that the child page be released by that time. 3796 * 3797 * ToDo: tlocks should be on doubly-linked list, so we can 3798 * quickly remove it and add it to the end. 3799 */ 3800 3801 /* 3802 * Move parent page's tlock to the end of the tid's tlock list 3803 */ 3804 if (log && mp->lid && (tblk->last != mp->lid) && 3805 lid_to_tlock(mp->lid)->tid) { 3806 lid_t lid = mp->lid; 3807 struct tlock *prev; 3808 3809 tlck = lid_to_tlock(lid); 3810 3811 if (tblk->next == lid) 3812 tblk->next = tlck->next; 3813 else { 3814 for (prev = lid_to_tlock(tblk->next); 3815 prev->next != lid; 3816 prev = lid_to_tlock(prev->next)) { 3817 assert(prev->next); 3818 } 3819 prev->next = tlck->next; 3820 } 3821 lid_to_tlock(tblk->last)->next = lid; 3822 tlck->next = 0; 3823 tblk->last = lid; 3824 } 3825 3826 /* 3827 * parent page become empty: free the page 3828 */ 3829 if (index == XTENTRYSTART) { 3830 if (log) { /* COMMIT_PWMAP */ 3831 /* txCommit() with tlckFREE: 3832 * free child extents covered by parent; 3833 * invalidate parent if COMMIT_PWMAP; 3834 */ 3835 tlck = txLock(tid, ip, mp, tlckXTREE); 3836 xtlck = (struct xtlock *) & tlck->lock; 3837 xtlck->hwm.offset = 3838 le16_to_cpu(p->header.nextindex) - 1; 3839 tlck->type = tlckXTREE | tlckFREE; 3840 } else { /* COMMIT_WMAP */ 3841 3842 /* free child extents covered by parent */ 3843 xadlock.xdlist = &p->xad[XTENTRYSTART]; 3844 xadlock.count = 3845 le16_to_cpu(p->header.nextindex) - 3846 XTENTRYSTART; 3847 txFreeMap(ip, (struct maplock *) & xadlock, NULL, 3848 COMMIT_WMAP); 3849 } 3850 BT_MARK_DIRTY(mp, ip); 3851 3852 if (p->header.flag & BT_ROOT) { 3853 p->header.flag &= ~BT_INTERNAL; 3854 p->header.flag |= BT_LEAF; 3855 p->header.nextindex = cpu_to_le16(XTENTRYSTART); 3856 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) { 3857 /* 3858 * Shrink root down to allow inline 3859 * EA (otherwise fsck complains) 3860 */ 3861 p->header.maxentry = 3862 cpu_to_le16(XTROOTINITSLOT); 3863 JFS_IP(ip)->mode2 |= INLINEEA; 3864 } 3865 3866 XT_PUTPAGE(mp); /* debug */ 3867 goto out; 3868 } else { 3869 if (log) { /* COMMIT_PWMAP */ 3870 /* page will be invalidated at tx completion 3871 */ 3872 XT_PUTPAGE(mp); 3873 } else { /* COMMIT_WMAP */ 3874 3875 if (mp->lid) 3876 lid_to_tlock(mp->lid)->flag |= 3877 tlckFREELOCK; 3878 3879 /* invalidate parent page */ 3880 discard_metapage(mp); 3881 } 3882 3883 /* parent has become empty and freed: 3884 * go back up to its parent page 3885 */ 3886 /* freed = 1; */ 3887 goto getParent; 3888 } 3889 } 3890 /* 3891 * parent page still has entries for front region; 3892 */ 3893 else { 3894 /* try truncate region covered by preceding entry 3895 * (process backward) 3896 */ 3897 index--; 3898 3899 /* go back down to the child page corresponding 3900 * to the entry 3901 */ 3902 goto getChild; 3903 } 3904 3905 /* 3906 * internal page: go down to child page of current entry 3907 */ 3908 getChild: 3909 /* save current parent entry for the child page */ 3910 if (BT_STACK_FULL(&btstack)) { 3911 jfs_error(ip->i_sb, "stack overrun in xtTruncate!"); 3912 XT_PUTPAGE(mp); 3913 return -EIO; 3914 } 3915 BT_PUSH(&btstack, bn, index); 3916 3917 /* get child page */ 3918 xad = &p->xad[index]; 3919 bn = addressXAD(xad); 3920 3921 /* 3922 * first access of each internal entry: 3923 */ 3924 /* release parent page */ 3925 XT_PUTPAGE(mp); 3926 3927 /* process the child page */ 3928 goto getPage; 3929 3930 out: 3931 /* 3932 * update file resource stat 3933 */ 3934 /* set size 3935 */ 3936 if (S_ISDIR(ip->i_mode) && !newsize) 3937 ip->i_size = 1; /* fsck hates zero-length directories */ 3938 else 3939 ip->i_size = newsize; 3940 3941 /* update quota allocation to reflect freed blocks */ 3942 DQUOT_FREE_BLOCK(ip, nfreed); 3943 3944 /* 3945 * free tlock of invalidated pages 3946 */ 3947 if (flag == COMMIT_WMAP) 3948 txFreelock(ip); 3949 3950 return newsize; 3951 } 3952 3953 3954 /* 3955 * xtTruncate_pmap() 3956 * 3957 * function: 3958 * Perform truncate to zero length for deleted file, leaving the 3959 * the xtree and working map untouched. This allows the file to 3960 * be accessed via open file handles, while the delete of the file 3961 * is committed to disk. 3962 * 3963 * parameter: 3964 * tid_t tid, 3965 * struct inode *ip, 3966 * s64 committed_size) 3967 * 3968 * return: new committed size 3969 * 3970 * note: 3971 * 3972 * To avoid deadlock by holding too many transaction locks, the 3973 * truncation may be broken up into multiple transactions. 3974 * The committed_size keeps track of part of the file has been 3975 * freed from the pmaps. 3976 */ 3977 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size) 3978 { 3979 s64 bn; 3980 struct btstack btstack; 3981 int cmp; 3982 int index; 3983 int locked_leaves = 0; 3984 struct metapage *mp; 3985 xtpage_t *p; 3986 struct btframe *parent; 3987 int rc; 3988 struct tblock *tblk; 3989 struct tlock *tlck = NULL; 3990 xad_t *xad; 3991 int xlen; 3992 s64 xoff; 3993 struct xtlock *xtlck = NULL; 3994 3995 /* save object truncation type */ 3996 tblk = tid_to_tblock(tid); 3997 tblk->xflag |= COMMIT_PMAP; 3998 3999 /* clear stack */ 4000 BT_CLR(&btstack); 4001 4002 if (committed_size) { 4003 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1; 4004 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0); 4005 if (rc) 4006 return rc; 4007 4008 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 4009 4010 if (cmp != 0) { 4011 XT_PUTPAGE(mp); 4012 jfs_error(ip->i_sb, 4013 "xtTruncate_pmap: did not find extent"); 4014 return -EIO; 4015 } 4016 } else { 4017 /* 4018 * start with root 4019 * 4020 * root resides in the inode 4021 */ 4022 bn = 0; 4023 4024 /* 4025 * first access of each page: 4026 */ 4027 getPage: 4028 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 4029 if (rc) 4030 return rc; 4031 4032 /* process entries backward from last index */ 4033 index = le16_to_cpu(p->header.nextindex) - 1; 4034 4035 if (p->header.flag & BT_INTERNAL) 4036 goto getChild; 4037 } 4038 4039 /* 4040 * leaf page 4041 */ 4042 4043 if (++locked_leaves > MAX_TRUNCATE_LEAVES) { 4044 /* 4045 * We need to limit the size of the transaction 4046 * to avoid exhausting pagecache & tlocks 4047 */ 4048 xad = &p->xad[index]; 4049 xoff = offsetXAD(xad); 4050 xlen = lengthXAD(xad); 4051 XT_PUTPAGE(mp); 4052 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize; 4053 } 4054 tlck = txLock(tid, ip, mp, tlckXTREE); 4055 tlck->type = tlckXTREE | tlckFREE; 4056 xtlck = (struct xtlock *) & tlck->lock; 4057 xtlck->hwm.offset = index; 4058 4059 4060 XT_PUTPAGE(mp); 4061 4062 /* 4063 * go back up to the parent page 4064 */ 4065 getParent: 4066 /* pop/restore parent entry for the current child page */ 4067 if ((parent = BT_POP(&btstack)) == NULL) 4068 /* current page must have been root */ 4069 goto out; 4070 4071 /* get back the parent page */ 4072 bn = parent->bn; 4073 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 4074 if (rc) 4075 return rc; 4076 4077 index = parent->index; 4078 4079 /* 4080 * parent page become empty: free the page 4081 */ 4082 if (index == XTENTRYSTART) { 4083 /* txCommit() with tlckFREE: 4084 * free child extents covered by parent; 4085 * invalidate parent if COMMIT_PWMAP; 4086 */ 4087 tlck = txLock(tid, ip, mp, tlckXTREE); 4088 xtlck = (struct xtlock *) & tlck->lock; 4089 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1; 4090 tlck->type = tlckXTREE | tlckFREE; 4091 4092 XT_PUTPAGE(mp); 4093 4094 if (p->header.flag & BT_ROOT) { 4095 4096 goto out; 4097 } else { 4098 goto getParent; 4099 } 4100 } 4101 /* 4102 * parent page still has entries for front region; 4103 */ 4104 else 4105 index--; 4106 /* 4107 * internal page: go down to child page of current entry 4108 */ 4109 getChild: 4110 /* save current parent entry for the child page */ 4111 if (BT_STACK_FULL(&btstack)) { 4112 jfs_error(ip->i_sb, "stack overrun in xtTruncate_pmap!"); 4113 XT_PUTPAGE(mp); 4114 return -EIO; 4115 } 4116 BT_PUSH(&btstack, bn, index); 4117 4118 /* get child page */ 4119 xad = &p->xad[index]; 4120 bn = addressXAD(xad); 4121 4122 /* 4123 * first access of each internal entry: 4124 */ 4125 /* release parent page */ 4126 XT_PUTPAGE(mp); 4127 4128 /* process the child page */ 4129 goto getPage; 4130 4131 out: 4132 4133 return 0; 4134 } 4135 4136 #ifdef CONFIG_JFS_STATISTICS 4137 int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length, 4138 int *eof, void *data) 4139 { 4140 int len = 0; 4141 off_t begin; 4142 4143 len += sprintf(buffer, 4144 "JFS Xtree statistics\n" 4145 "====================\n" 4146 "searches = %d\n" 4147 "fast searches = %d\n" 4148 "splits = %d\n", 4149 xtStat.search, 4150 xtStat.fastSearch, 4151 xtStat.split); 4152 4153 begin = offset; 4154 *start = buffer + begin; 4155 len -= begin; 4156 4157 if (len > length) 4158 len = length; 4159 else 4160 *eof = 1; 4161 4162 if (len < 0) 4163 len = 0; 4164 4165 return len; 4166 } 4167 #endif 4168