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