1 /* 2 * Copyright (C) International Business Machines Corp., 2000-2004 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 /* 20 * jfs_dtree.c: directory B+-tree manager 21 * 22 * B+-tree with variable length key directory: 23 * 24 * each directory page is structured as an array of 32-byte 25 * directory entry slots initialized as a freelist 26 * to avoid search/compaction of free space at insertion. 27 * when an entry is inserted, a number of slots are allocated 28 * from the freelist as required to store variable length data 29 * of the entry; when the entry is deleted, slots of the entry 30 * are returned to freelist. 31 * 32 * leaf entry stores full name as key and file serial number 33 * (aka inode number) as data. 34 * internal/router entry stores sufffix compressed name 35 * as key and simple extent descriptor as data. 36 * 37 * each directory page maintains a sorted entry index table 38 * which stores the start slot index of sorted entries 39 * to allow binary search on the table. 40 * 41 * directory starts as a root/leaf page in on-disk inode 42 * inline data area. 43 * when it becomes full, it starts a leaf of a external extent 44 * of length of 1 block. each time the first leaf becomes full, 45 * it is extended rather than split (its size is doubled), 46 * until its length becoms 4 KBytes, from then the extent is split 47 * with new 4 Kbyte extent when it becomes full 48 * to reduce external fragmentation of small directories. 49 * 50 * blah, blah, blah, for linear scan of directory in pieces by 51 * readdir(). 52 * 53 * 54 * case-insensitive directory file system 55 * 56 * names are stored in case-sensitive way in leaf entry. 57 * but stored, searched and compared in case-insensitive (uppercase) order 58 * (i.e., both search key and entry key are folded for search/compare): 59 * (note that case-sensitive order is BROKEN in storage, e.g., 60 * sensitive: Ad, aB, aC, aD -> insensitive: aB, aC, aD, Ad 61 * 62 * entries which folds to the same key makes up a equivalent class 63 * whose members are stored as contiguous cluster (may cross page boundary) 64 * but whose order is arbitrary and acts as duplicate, e.g., 65 * abc, Abc, aBc, abC) 66 * 67 * once match is found at leaf, requires scan forward/backward 68 * either for, in case-insensitive search, duplicate 69 * or for, in case-sensitive search, for exact match 70 * 71 * router entry must be created/stored in case-insensitive way 72 * in internal entry: 73 * (right most key of left page and left most key of right page 74 * are folded, and its suffix compression is propagated as router 75 * key in parent) 76 * (e.g., if split occurs <abc> and <aBd>, <ABD> trather than <aB> 77 * should be made the router key for the split) 78 * 79 * case-insensitive search: 80 * 81 * fold search key; 82 * 83 * case-insensitive search of B-tree: 84 * for internal entry, router key is already folded; 85 * for leaf entry, fold the entry key before comparison. 86 * 87 * if (leaf entry case-insensitive match found) 88 * if (next entry satisfies case-insensitive match) 89 * return EDUPLICATE; 90 * if (prev entry satisfies case-insensitive match) 91 * return EDUPLICATE; 92 * return match; 93 * else 94 * return no match; 95 * 96 * serialization: 97 * target directory inode lock is being held on entry/exit 98 * of all main directory service routines. 99 * 100 * log based recovery: 101 */ 102 103 #include <linux/fs.h> 104 #include <linux/quotaops.h> 105 #include "jfs_incore.h" 106 #include "jfs_superblock.h" 107 #include "jfs_filsys.h" 108 #include "jfs_metapage.h" 109 #include "jfs_dmap.h" 110 #include "jfs_unicode.h" 111 #include "jfs_debug.h" 112 113 /* dtree split parameter */ 114 struct dtsplit { 115 struct metapage *mp; 116 s16 index; 117 s16 nslot; 118 struct component_name *key; 119 ddata_t *data; 120 struct pxdlist *pxdlist; 121 }; 122 123 #define DT_PAGE(IP, MP) BT_PAGE(IP, MP, dtpage_t, i_dtroot) 124 125 /* get page buffer for specified block address */ 126 #define DT_GETPAGE(IP, BN, MP, SIZE, P, RC)\ 127 {\ 128 BT_GETPAGE(IP, BN, MP, dtpage_t, SIZE, P, RC, i_dtroot)\ 129 if (!(RC))\ 130 {\ 131 if (((P)->header.nextindex > (((BN)==0)?DTROOTMAXSLOT:(P)->header.maxslot)) ||\ 132 ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT)))\ 133 {\ 134 BT_PUTPAGE(MP);\ 135 jfs_error((IP)->i_sb, "DT_GETPAGE: dtree page corrupt");\ 136 MP = NULL;\ 137 RC = -EIO;\ 138 }\ 139 }\ 140 } 141 142 /* for consistency */ 143 #define DT_PUTPAGE(MP) BT_PUTPAGE(MP) 144 145 #define DT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \ 146 BT_GETSEARCH(IP, LEAF, BN, MP, dtpage_t, P, INDEX, i_dtroot) 147 148 /* 149 * forward references 150 */ 151 static int dtSplitUp(tid_t tid, struct inode *ip, 152 struct dtsplit * split, struct btstack * btstack); 153 154 static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split, 155 struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rxdp); 156 157 static int dtExtendPage(tid_t tid, struct inode *ip, 158 struct dtsplit * split, struct btstack * btstack); 159 160 static int dtSplitRoot(tid_t tid, struct inode *ip, 161 struct dtsplit * split, struct metapage ** rmpp); 162 163 static int dtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp, 164 dtpage_t * fp, struct btstack * btstack); 165 166 static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p); 167 168 static int dtReadFirst(struct inode *ip, struct btstack * btstack); 169 170 static int dtReadNext(struct inode *ip, 171 loff_t * offset, struct btstack * btstack); 172 173 static int dtCompare(struct component_name * key, dtpage_t * p, int si); 174 175 static int ciCompare(struct component_name * key, dtpage_t * p, int si, 176 int flag); 177 178 static void dtGetKey(dtpage_t * p, int i, struct component_name * key, 179 int flag); 180 181 static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp, 182 int ri, struct component_name * key, int flag); 183 184 static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key, 185 ddata_t * data, struct dt_lock **); 186 187 static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp, 188 struct dt_lock ** sdtlock, struct dt_lock ** ddtlock, 189 int do_index); 190 191 static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock); 192 193 static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock); 194 195 static void dtLinelockFreelist(dtpage_t * p, int m, struct dt_lock ** dtlock); 196 197 #define ciToUpper(c) UniStrupr((c)->name) 198 199 /* 200 * read_index_page() 201 * 202 * Reads a page of a directory's index table. 203 * Having metadata mapped into the directory inode's address space 204 * presents a multitude of problems. We avoid this by mapping to 205 * the absolute address space outside of the *_metapage routines 206 */ 207 static struct metapage *read_index_page(struct inode *inode, s64 blkno) 208 { 209 int rc; 210 s64 xaddr; 211 int xflag; 212 s32 xlen; 213 214 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); 215 if (rc || (xaddr == 0)) 216 return NULL; 217 218 return read_metapage(inode, xaddr, PSIZE, 1); 219 } 220 221 /* 222 * get_index_page() 223 * 224 * Same as get_index_page(), but get's a new page without reading 225 */ 226 static struct metapage *get_index_page(struct inode *inode, s64 blkno) 227 { 228 int rc; 229 s64 xaddr; 230 int xflag; 231 s32 xlen; 232 233 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); 234 if (rc || (xaddr == 0)) 235 return NULL; 236 237 return get_metapage(inode, xaddr, PSIZE, 1); 238 } 239 240 /* 241 * find_index() 242 * 243 * Returns dtree page containing directory table entry for specified 244 * index and pointer to its entry. 245 * 246 * mp must be released by caller. 247 */ 248 static struct dir_table_slot *find_index(struct inode *ip, u32 index, 249 struct metapage ** mp, s64 *lblock) 250 { 251 struct jfs_inode_info *jfs_ip = JFS_IP(ip); 252 s64 blkno; 253 s64 offset; 254 int page_offset; 255 struct dir_table_slot *slot; 256 static int maxWarnings = 10; 257 258 if (index < 2) { 259 if (maxWarnings) { 260 jfs_warn("find_entry called with index = %d", index); 261 maxWarnings--; 262 } 263 return NULL; 264 } 265 266 if (index >= jfs_ip->next_index) { 267 jfs_warn("find_entry called with index >= next_index"); 268 return NULL; 269 } 270 271 if (jfs_dirtable_inline(ip)) { 272 /* 273 * Inline directory table 274 */ 275 *mp = NULL; 276 slot = &jfs_ip->i_dirtable[index - 2]; 277 } else { 278 offset = (index - 2) * sizeof(struct dir_table_slot); 279 page_offset = offset & (PSIZE - 1); 280 blkno = ((offset + 1) >> L2PSIZE) << 281 JFS_SBI(ip->i_sb)->l2nbperpage; 282 283 if (*mp && (*lblock != blkno)) { 284 release_metapage(*mp); 285 *mp = NULL; 286 } 287 if (*mp == 0) { 288 *lblock = blkno; 289 *mp = read_index_page(ip, blkno); 290 } 291 if (*mp == 0) { 292 jfs_err("free_index: error reading directory table"); 293 return NULL; 294 } 295 296 slot = 297 (struct dir_table_slot *) ((char *) (*mp)->data + 298 page_offset); 299 } 300 return slot; 301 } 302 303 static inline void lock_index(tid_t tid, struct inode *ip, struct metapage * mp, 304 u32 index) 305 { 306 struct tlock *tlck; 307 struct linelock *llck; 308 struct lv *lv; 309 310 tlck = txLock(tid, ip, mp, tlckDATA); 311 llck = (struct linelock *) tlck->lock; 312 313 if (llck->index >= llck->maxcnt) 314 llck = txLinelock(llck); 315 lv = &llck->lv[llck->index]; 316 317 /* 318 * Linelock slot size is twice the size of directory table 319 * slot size. 512 entries per page. 320 */ 321 lv->offset = ((index - 2) & 511) >> 1; 322 lv->length = 1; 323 llck->index++; 324 } 325 326 /* 327 * add_index() 328 * 329 * Adds an entry to the directory index table. This is used to provide 330 * each directory entry with a persistent index in which to resume 331 * directory traversals 332 */ 333 static u32 add_index(tid_t tid, struct inode *ip, s64 bn, int slot) 334 { 335 struct super_block *sb = ip->i_sb; 336 struct jfs_sb_info *sbi = JFS_SBI(sb); 337 struct jfs_inode_info *jfs_ip = JFS_IP(ip); 338 u64 blkno; 339 struct dir_table_slot *dirtab_slot; 340 u32 index; 341 struct linelock *llck; 342 struct lv *lv; 343 struct metapage *mp; 344 s64 offset; 345 uint page_offset; 346 struct tlock *tlck; 347 s64 xaddr; 348 349 ASSERT(DO_INDEX(ip)); 350 351 if (jfs_ip->next_index < 2) { 352 jfs_warn("add_index: next_index = %d. Resetting!", 353 jfs_ip->next_index); 354 jfs_ip->next_index = 2; 355 } 356 357 index = jfs_ip->next_index++; 358 359 if (index <= MAX_INLINE_DIRTABLE_ENTRY) { 360 /* 361 * i_size reflects size of index table, or 8 bytes per entry. 362 */ 363 ip->i_size = (loff_t) (index - 1) << 3; 364 365 /* 366 * dir table fits inline within inode 367 */ 368 dirtab_slot = &jfs_ip->i_dirtable[index-2]; 369 dirtab_slot->flag = DIR_INDEX_VALID; 370 dirtab_slot->slot = slot; 371 DTSaddress(dirtab_slot, bn); 372 373 set_cflag(COMMIT_Dirtable, ip); 374 375 return index; 376 } 377 if (index == (MAX_INLINE_DIRTABLE_ENTRY + 1)) { 378 struct dir_table_slot temp_table[12]; 379 380 /* 381 * It's time to move the inline table to an external 382 * page and begin to build the xtree 383 */ 384 if (DQUOT_ALLOC_BLOCK(ip, sbi->nbperpage)) 385 goto clean_up; 386 if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) { 387 DQUOT_FREE_BLOCK(ip, sbi->nbperpage); 388 goto clean_up; 389 } 390 391 /* 392 * Save the table, we're going to overwrite it with the 393 * xtree root 394 */ 395 memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table)); 396 397 /* 398 * Initialize empty x-tree 399 */ 400 xtInitRoot(tid, ip); 401 402 /* 403 * Add the first block to the xtree 404 */ 405 if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) { 406 /* This really shouldn't fail */ 407 jfs_warn("add_index: xtInsert failed!"); 408 memcpy(&jfs_ip->i_dirtable, temp_table, 409 sizeof (temp_table)); 410 dbFree(ip, xaddr, sbi->nbperpage); 411 DQUOT_FREE_BLOCK(ip, sbi->nbperpage); 412 goto clean_up; 413 } 414 ip->i_size = PSIZE; 415 416 if ((mp = get_index_page(ip, 0)) == 0) { 417 jfs_err("add_index: get_metapage failed!"); 418 xtTruncate(tid, ip, 0, COMMIT_PWMAP); 419 memcpy(&jfs_ip->i_dirtable, temp_table, 420 sizeof (temp_table)); 421 goto clean_up; 422 } 423 tlck = txLock(tid, ip, mp, tlckDATA); 424 llck = (struct linelock *) & tlck->lock; 425 ASSERT(llck->index == 0); 426 lv = &llck->lv[0]; 427 428 lv->offset = 0; 429 lv->length = 6; /* tlckDATA slot size is 16 bytes */ 430 llck->index++; 431 432 memcpy(mp->data, temp_table, sizeof(temp_table)); 433 434 mark_metapage_dirty(mp); 435 release_metapage(mp); 436 437 /* 438 * Logging is now directed by xtree tlocks 439 */ 440 clear_cflag(COMMIT_Dirtable, ip); 441 } 442 443 offset = (index - 2) * sizeof(struct dir_table_slot); 444 page_offset = offset & (PSIZE - 1); 445 blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage; 446 if (page_offset == 0) { 447 /* 448 * This will be the beginning of a new page 449 */ 450 xaddr = 0; 451 if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) { 452 jfs_warn("add_index: xtInsert failed!"); 453 goto clean_up; 454 } 455 ip->i_size += PSIZE; 456 457 if ((mp = get_index_page(ip, blkno))) 458 memset(mp->data, 0, PSIZE); /* Just looks better */ 459 else 460 xtTruncate(tid, ip, offset, COMMIT_PWMAP); 461 } else 462 mp = read_index_page(ip, blkno); 463 464 if (mp == 0) { 465 jfs_err("add_index: get/read_metapage failed!"); 466 goto clean_up; 467 } 468 469 lock_index(tid, ip, mp, index); 470 471 dirtab_slot = 472 (struct dir_table_slot *) ((char *) mp->data + page_offset); 473 dirtab_slot->flag = DIR_INDEX_VALID; 474 dirtab_slot->slot = slot; 475 DTSaddress(dirtab_slot, bn); 476 477 mark_metapage_dirty(mp); 478 release_metapage(mp); 479 480 return index; 481 482 clean_up: 483 484 jfs_ip->next_index--; 485 486 return 0; 487 } 488 489 /* 490 * free_index() 491 * 492 * Marks an entry to the directory index table as free. 493 */ 494 static void free_index(tid_t tid, struct inode *ip, u32 index, u32 next) 495 { 496 struct dir_table_slot *dirtab_slot; 497 s64 lblock; 498 struct metapage *mp = NULL; 499 500 dirtab_slot = find_index(ip, index, &mp, &lblock); 501 502 if (dirtab_slot == 0) 503 return; 504 505 dirtab_slot->flag = DIR_INDEX_FREE; 506 dirtab_slot->slot = dirtab_slot->addr1 = 0; 507 dirtab_slot->addr2 = cpu_to_le32(next); 508 509 if (mp) { 510 lock_index(tid, ip, mp, index); 511 mark_metapage_dirty(mp); 512 release_metapage(mp); 513 } else 514 set_cflag(COMMIT_Dirtable, ip); 515 } 516 517 /* 518 * modify_index() 519 * 520 * Changes an entry in the directory index table 521 */ 522 static void modify_index(tid_t tid, struct inode *ip, u32 index, s64 bn, 523 int slot, struct metapage ** mp, u64 *lblock) 524 { 525 struct dir_table_slot *dirtab_slot; 526 527 dirtab_slot = find_index(ip, index, mp, lblock); 528 529 if (dirtab_slot == 0) 530 return; 531 532 DTSaddress(dirtab_slot, bn); 533 dirtab_slot->slot = slot; 534 535 if (*mp) { 536 lock_index(tid, ip, *mp, index); 537 mark_metapage_dirty(*mp); 538 } else 539 set_cflag(COMMIT_Dirtable, ip); 540 } 541 542 /* 543 * read_index() 544 * 545 * reads a directory table slot 546 */ 547 static int read_index(struct inode *ip, u32 index, 548 struct dir_table_slot * dirtab_slot) 549 { 550 s64 lblock; 551 struct metapage *mp = NULL; 552 struct dir_table_slot *slot; 553 554 slot = find_index(ip, index, &mp, &lblock); 555 if (slot == 0) { 556 return -EIO; 557 } 558 559 memcpy(dirtab_slot, slot, sizeof(struct dir_table_slot)); 560 561 if (mp) 562 release_metapage(mp); 563 564 return 0; 565 } 566 567 /* 568 * dtSearch() 569 * 570 * function: 571 * Search for the entry with specified key 572 * 573 * parameter: 574 * 575 * return: 0 - search result on stack, leaf page pinned; 576 * errno - I/O error 577 */ 578 int dtSearch(struct inode *ip, struct component_name * key, ino_t * data, 579 struct btstack * btstack, int flag) 580 { 581 int rc = 0; 582 int cmp = 1; /* init for empty page */ 583 s64 bn; 584 struct metapage *mp; 585 dtpage_t *p; 586 s8 *stbl; 587 int base, index, lim; 588 struct btframe *btsp; 589 pxd_t *pxd; 590 int psize = 288; /* initial in-line directory */ 591 ino_t inumber; 592 struct component_name ciKey; 593 struct super_block *sb = ip->i_sb; 594 595 ciKey.name = 596 (wchar_t *) kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t), 597 GFP_NOFS); 598 if (ciKey.name == 0) { 599 rc = -ENOMEM; 600 goto dtSearch_Exit2; 601 } 602 603 604 /* uppercase search key for c-i directory */ 605 UniStrcpy(ciKey.name, key->name); 606 ciKey.namlen = key->namlen; 607 608 /* only uppercase if case-insensitive support is on */ 609 if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) { 610 ciToUpper(&ciKey); 611 } 612 BT_CLR(btstack); /* reset stack */ 613 614 /* init level count for max pages to split */ 615 btstack->nsplit = 1; 616 617 /* 618 * search down tree from root: 619 * 620 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of 621 * internal page, child page Pi contains entry with k, Ki <= K < Kj. 622 * 623 * if entry with search key K is not found 624 * internal page search find the entry with largest key Ki 625 * less than K which point to the child page to search; 626 * leaf page search find the entry with smallest key Kj 627 * greater than K so that the returned index is the position of 628 * the entry to be shifted right for insertion of new entry. 629 * for empty tree, search key is greater than any key of the tree. 630 * 631 * by convention, root bn = 0. 632 */ 633 for (bn = 0;;) { 634 /* get/pin the page to search */ 635 DT_GETPAGE(ip, bn, mp, psize, p, rc); 636 if (rc) 637 goto dtSearch_Exit1; 638 639 /* get sorted entry table of the page */ 640 stbl = DT_GETSTBL(p); 641 642 /* 643 * binary search with search key K on the current page. 644 */ 645 for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) { 646 index = base + (lim >> 1); 647 648 if (p->header.flag & BT_LEAF) { 649 /* uppercase leaf name to compare */ 650 cmp = 651 ciCompare(&ciKey, p, stbl[index], 652 JFS_SBI(sb)->mntflag); 653 } else { 654 /* router key is in uppercase */ 655 656 cmp = dtCompare(&ciKey, p, stbl[index]); 657 658 659 } 660 if (cmp == 0) { 661 /* 662 * search hit 663 */ 664 /* search hit - leaf page: 665 * return the entry found 666 */ 667 if (p->header.flag & BT_LEAF) { 668 inumber = le32_to_cpu( 669 ((struct ldtentry *) & p->slot[stbl[index]])->inumber); 670 671 /* 672 * search for JFS_LOOKUP 673 */ 674 if (flag == JFS_LOOKUP) { 675 *data = inumber; 676 rc = 0; 677 goto out; 678 } 679 680 /* 681 * search for JFS_CREATE 682 */ 683 if (flag == JFS_CREATE) { 684 *data = inumber; 685 rc = -EEXIST; 686 goto out; 687 } 688 689 /* 690 * search for JFS_REMOVE or JFS_RENAME 691 */ 692 if ((flag == JFS_REMOVE || 693 flag == JFS_RENAME) && 694 *data != inumber) { 695 rc = -ESTALE; 696 goto out; 697 } 698 699 /* 700 * JFS_REMOVE|JFS_FINDDIR|JFS_RENAME 701 */ 702 /* save search result */ 703 *data = inumber; 704 btsp = btstack->top; 705 btsp->bn = bn; 706 btsp->index = index; 707 btsp->mp = mp; 708 709 rc = 0; 710 goto dtSearch_Exit1; 711 } 712 713 /* search hit - internal page: 714 * descend/search its child page 715 */ 716 goto getChild; 717 } 718 719 if (cmp > 0) { 720 base = index + 1; 721 --lim; 722 } 723 } 724 725 /* 726 * search miss 727 * 728 * base is the smallest index with key (Kj) greater than 729 * search key (K) and may be zero or (maxindex + 1) index. 730 */ 731 /* 732 * search miss - leaf page 733 * 734 * return location of entry (base) where new entry with 735 * search key K is to be inserted. 736 */ 737 if (p->header.flag & BT_LEAF) { 738 /* 739 * search for JFS_LOOKUP, JFS_REMOVE, or JFS_RENAME 740 */ 741 if (flag == JFS_LOOKUP || flag == JFS_REMOVE || 742 flag == JFS_RENAME) { 743 rc = -ENOENT; 744 goto out; 745 } 746 747 /* 748 * search for JFS_CREATE|JFS_FINDDIR: 749 * 750 * save search result 751 */ 752 *data = 0; 753 btsp = btstack->top; 754 btsp->bn = bn; 755 btsp->index = base; 756 btsp->mp = mp; 757 758 rc = 0; 759 goto dtSearch_Exit1; 760 } 761 762 /* 763 * search miss - internal page 764 * 765 * if base is non-zero, decrement base by one to get the parent 766 * entry of the child page to search. 767 */ 768 index = base ? base - 1 : base; 769 770 /* 771 * go down to child page 772 */ 773 getChild: 774 /* update max. number of pages to split */ 775 if (BT_STACK_FULL(btstack)) { 776 /* Something's corrupted, mark filesytem dirty so 777 * chkdsk will fix it. 778 */ 779 jfs_error(sb, "stack overrun in dtSearch!"); 780 BT_STACK_DUMP(btstack); 781 rc = -EIO; 782 goto out; 783 } 784 btstack->nsplit++; 785 786 /* push (bn, index) of the parent page/entry */ 787 BT_PUSH(btstack, bn, index); 788 789 /* get the child page block number */ 790 pxd = (pxd_t *) & p->slot[stbl[index]]; 791 bn = addressPXD(pxd); 792 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; 793 794 /* unpin the parent page */ 795 DT_PUTPAGE(mp); 796 } 797 798 out: 799 DT_PUTPAGE(mp); 800 801 dtSearch_Exit1: 802 803 kfree(ciKey.name); 804 805 dtSearch_Exit2: 806 807 return rc; 808 } 809 810 811 /* 812 * dtInsert() 813 * 814 * function: insert an entry to directory tree 815 * 816 * parameter: 817 * 818 * return: 0 - success; 819 * errno - failure; 820 */ 821 int dtInsert(tid_t tid, struct inode *ip, 822 struct component_name * name, ino_t * fsn, struct btstack * btstack) 823 { 824 int rc = 0; 825 struct metapage *mp; /* meta-page buffer */ 826 dtpage_t *p; /* base B+-tree index page */ 827 s64 bn; 828 int index; 829 struct dtsplit split; /* split information */ 830 ddata_t data; 831 struct dt_lock *dtlck; 832 int n; 833 struct tlock *tlck; 834 struct lv *lv; 835 836 /* 837 * retrieve search result 838 * 839 * dtSearch() returns (leaf page pinned, index at which to insert). 840 * n.b. dtSearch() may return index of (maxindex + 1) of 841 * the full page. 842 */ 843 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); 844 845 /* 846 * insert entry for new key 847 */ 848 if (DO_INDEX(ip)) { 849 if (JFS_IP(ip)->next_index == DIREND) { 850 DT_PUTPAGE(mp); 851 return -EMLINK; 852 } 853 n = NDTLEAF(name->namlen); 854 data.leaf.tid = tid; 855 data.leaf.ip = ip; 856 } else { 857 n = NDTLEAF_LEGACY(name->namlen); 858 data.leaf.ip = NULL; /* signifies legacy directory format */ 859 } 860 data.leaf.ino = *fsn; 861 862 /* 863 * leaf page does not have enough room for new entry: 864 * 865 * extend/split the leaf page; 866 * 867 * dtSplitUp() will insert the entry and unpin the leaf page. 868 */ 869 if (n > p->header.freecnt) { 870 split.mp = mp; 871 split.index = index; 872 split.nslot = n; 873 split.key = name; 874 split.data = &data; 875 rc = dtSplitUp(tid, ip, &split, btstack); 876 return rc; 877 } 878 879 /* 880 * leaf page does have enough room for new entry: 881 * 882 * insert the new data entry into the leaf page; 883 */ 884 BT_MARK_DIRTY(mp, ip); 885 /* 886 * acquire a transaction lock on the leaf page 887 */ 888 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY); 889 dtlck = (struct dt_lock *) & tlck->lock; 890 ASSERT(dtlck->index == 0); 891 lv = & dtlck->lv[0]; 892 893 /* linelock header */ 894 lv->offset = 0; 895 lv->length = 1; 896 dtlck->index++; 897 898 dtInsertEntry(p, index, name, &data, &dtlck); 899 900 /* linelock stbl of non-root leaf page */ 901 if (!(p->header.flag & BT_ROOT)) { 902 if (dtlck->index >= dtlck->maxcnt) 903 dtlck = (struct dt_lock *) txLinelock(dtlck); 904 lv = & dtlck->lv[dtlck->index]; 905 n = index >> L2DTSLOTSIZE; 906 lv->offset = p->header.stblindex + n; 907 lv->length = 908 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; 909 dtlck->index++; 910 } 911 912 /* unpin the leaf page */ 913 DT_PUTPAGE(mp); 914 915 return 0; 916 } 917 918 919 /* 920 * dtSplitUp() 921 * 922 * function: propagate insertion bottom up; 923 * 924 * parameter: 925 * 926 * return: 0 - success; 927 * errno - failure; 928 * leaf page unpinned; 929 */ 930 static int dtSplitUp(tid_t tid, 931 struct inode *ip, struct dtsplit * split, struct btstack * btstack) 932 { 933 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); 934 int rc = 0; 935 struct metapage *smp; 936 dtpage_t *sp; /* split page */ 937 struct metapage *rmp; 938 dtpage_t *rp; /* new right page split from sp */ 939 pxd_t rpxd; /* new right page extent descriptor */ 940 struct metapage *lmp; 941 dtpage_t *lp; /* left child page */ 942 int skip; /* index of entry of insertion */ 943 struct btframe *parent; /* parent page entry on traverse stack */ 944 s64 xaddr, nxaddr; 945 int xlen, xsize; 946 struct pxdlist pxdlist; 947 pxd_t *pxd; 948 struct component_name key = { 0, NULL }; 949 ddata_t *data = split->data; 950 int n; 951 struct dt_lock *dtlck; 952 struct tlock *tlck; 953 struct lv *lv; 954 int quota_allocation = 0; 955 956 /* get split page */ 957 smp = split->mp; 958 sp = DT_PAGE(ip, smp); 959 960 key.name = 961 (wchar_t *) kmalloc((JFS_NAME_MAX + 2) * sizeof(wchar_t), 962 GFP_NOFS); 963 if (key.name == 0) { 964 DT_PUTPAGE(smp); 965 rc = -ENOMEM; 966 goto dtSplitUp_Exit; 967 } 968 969 /* 970 * split leaf page 971 * 972 * The split routines insert the new entry, and 973 * acquire txLock as appropriate. 974 */ 975 /* 976 * split root leaf page: 977 */ 978 if (sp->header.flag & BT_ROOT) { 979 /* 980 * allocate a single extent child page 981 */ 982 xlen = 1; 983 n = sbi->bsize >> L2DTSLOTSIZE; 984 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ 985 n -= DTROOTMAXSLOT - sp->header.freecnt; /* header + entries */ 986 if (n <= split->nslot) 987 xlen++; 988 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr))) { 989 DT_PUTPAGE(smp); 990 goto freeKeyName; 991 } 992 993 pxdlist.maxnpxd = 1; 994 pxdlist.npxd = 0; 995 pxd = &pxdlist.pxd[0]; 996 PXDaddress(pxd, xaddr); 997 PXDlength(pxd, xlen); 998 split->pxdlist = &pxdlist; 999 rc = dtSplitRoot(tid, ip, split, &rmp); 1000 1001 if (rc) 1002 dbFree(ip, xaddr, xlen); 1003 else 1004 DT_PUTPAGE(rmp); 1005 1006 DT_PUTPAGE(smp); 1007 1008 if (!DO_INDEX(ip)) 1009 ip->i_size = xlen << sbi->l2bsize; 1010 1011 goto freeKeyName; 1012 } 1013 1014 /* 1015 * extend first leaf page 1016 * 1017 * extend the 1st extent if less than buffer page size 1018 * (dtExtendPage() reurns leaf page unpinned) 1019 */ 1020 pxd = &sp->header.self; 1021 xlen = lengthPXD(pxd); 1022 xsize = xlen << sbi->l2bsize; 1023 if (xsize < PSIZE) { 1024 xaddr = addressPXD(pxd); 1025 n = xsize >> L2DTSLOTSIZE; 1026 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ 1027 if ((n + sp->header.freecnt) <= split->nslot) 1028 n = xlen + (xlen << 1); 1029 else 1030 n = xlen; 1031 1032 /* Allocate blocks to quota. */ 1033 if (DQUOT_ALLOC_BLOCK(ip, n)) { 1034 rc = -EDQUOT; 1035 goto extendOut; 1036 } 1037 quota_allocation += n; 1038 1039 if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen, 1040 (s64) n, &nxaddr))) 1041 goto extendOut; 1042 1043 pxdlist.maxnpxd = 1; 1044 pxdlist.npxd = 0; 1045 pxd = &pxdlist.pxd[0]; 1046 PXDaddress(pxd, nxaddr) 1047 PXDlength(pxd, xlen + n); 1048 split->pxdlist = &pxdlist; 1049 if ((rc = dtExtendPage(tid, ip, split, btstack))) { 1050 nxaddr = addressPXD(pxd); 1051 if (xaddr != nxaddr) { 1052 /* free relocated extent */ 1053 xlen = lengthPXD(pxd); 1054 dbFree(ip, nxaddr, (s64) xlen); 1055 } else { 1056 /* free extended delta */ 1057 xlen = lengthPXD(pxd) - n; 1058 xaddr = addressPXD(pxd) + xlen; 1059 dbFree(ip, xaddr, (s64) n); 1060 } 1061 } else if (!DO_INDEX(ip)) 1062 ip->i_size = lengthPXD(pxd) << sbi->l2bsize; 1063 1064 1065 extendOut: 1066 DT_PUTPAGE(smp); 1067 goto freeKeyName; 1068 } 1069 1070 /* 1071 * split leaf page <sp> into <sp> and a new right page <rp>. 1072 * 1073 * return <rp> pinned and its extent descriptor <rpxd> 1074 */ 1075 /* 1076 * allocate new directory page extent and 1077 * new index page(s) to cover page split(s) 1078 * 1079 * allocation hint: ? 1080 */ 1081 n = btstack->nsplit; 1082 pxdlist.maxnpxd = pxdlist.npxd = 0; 1083 xlen = sbi->nbperpage; 1084 for (pxd = pxdlist.pxd; n > 0; n--, pxd++) { 1085 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr)) == 0) { 1086 PXDaddress(pxd, xaddr); 1087 PXDlength(pxd, xlen); 1088 pxdlist.maxnpxd++; 1089 continue; 1090 } 1091 1092 DT_PUTPAGE(smp); 1093 1094 /* undo allocation */ 1095 goto splitOut; 1096 } 1097 1098 split->pxdlist = &pxdlist; 1099 if ((rc = dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd))) { 1100 DT_PUTPAGE(smp); 1101 1102 /* undo allocation */ 1103 goto splitOut; 1104 } 1105 1106 if (!DO_INDEX(ip)) 1107 ip->i_size += PSIZE; 1108 1109 /* 1110 * propagate up the router entry for the leaf page just split 1111 * 1112 * insert a router entry for the new page into the parent page, 1113 * propagate the insert/split up the tree by walking back the stack 1114 * of (bn of parent page, index of child page entry in parent page) 1115 * that were traversed during the search for the page that split. 1116 * 1117 * the propagation of insert/split up the tree stops if the root 1118 * splits or the page inserted into doesn't have to split to hold 1119 * the new entry. 1120 * 1121 * the parent entry for the split page remains the same, and 1122 * a new entry is inserted at its right with the first key and 1123 * block number of the new right page. 1124 * 1125 * There are a maximum of 4 pages pinned at any time: 1126 * two children, left parent and right parent (when the parent splits). 1127 * keep the child pages pinned while working on the parent. 1128 * make sure that all pins are released at exit. 1129 */ 1130 while ((parent = BT_POP(btstack)) != NULL) { 1131 /* parent page specified by stack frame <parent> */ 1132 1133 /* keep current child pages (<lp>, <rp>) pinned */ 1134 lmp = smp; 1135 lp = sp; 1136 1137 /* 1138 * insert router entry in parent for new right child page <rp> 1139 */ 1140 /* get the parent page <sp> */ 1141 DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); 1142 if (rc) { 1143 DT_PUTPAGE(lmp); 1144 DT_PUTPAGE(rmp); 1145 goto splitOut; 1146 } 1147 1148 /* 1149 * The new key entry goes ONE AFTER the index of parent entry, 1150 * because the split was to the right. 1151 */ 1152 skip = parent->index + 1; 1153 1154 /* 1155 * compute the key for the router entry 1156 * 1157 * key suffix compression: 1158 * for internal pages that have leaf pages as children, 1159 * retain only what's needed to distinguish between 1160 * the new entry and the entry on the page to its left. 1161 * If the keys compare equal, retain the entire key. 1162 * 1163 * note that compression is performed only at computing 1164 * router key at the lowest internal level. 1165 * further compression of the key between pairs of higher 1166 * level internal pages loses too much information and 1167 * the search may fail. 1168 * (e.g., two adjacent leaf pages of {a, ..., x} {xx, ...,} 1169 * results in two adjacent parent entries (a)(xx). 1170 * if split occurs between these two entries, and 1171 * if compression is applied, the router key of parent entry 1172 * of right page (x) will divert search for x into right 1173 * subtree and miss x in the left subtree.) 1174 * 1175 * the entire key must be retained for the next-to-leftmost 1176 * internal key at any level of the tree, or search may fail 1177 * (e.g., ?) 1178 */ 1179 switch (rp->header.flag & BT_TYPE) { 1180 case BT_LEAF: 1181 /* 1182 * compute the length of prefix for suffix compression 1183 * between last entry of left page and first entry 1184 * of right page 1185 */ 1186 if ((sp->header.flag & BT_ROOT && skip > 1) || 1187 sp->header.prev != 0 || skip > 1) { 1188 /* compute uppercase router prefix key */ 1189 rc = ciGetLeafPrefixKey(lp, 1190 lp->header.nextindex-1, 1191 rp, 0, &key, 1192 sbi->mntflag); 1193 if (rc) { 1194 DT_PUTPAGE(lmp); 1195 DT_PUTPAGE(rmp); 1196 DT_PUTPAGE(smp); 1197 goto splitOut; 1198 } 1199 } else { 1200 /* next to leftmost entry of 1201 lowest internal level */ 1202 1203 /* compute uppercase router key */ 1204 dtGetKey(rp, 0, &key, sbi->mntflag); 1205 key.name[key.namlen] = 0; 1206 1207 if ((sbi->mntflag & JFS_OS2) == JFS_OS2) 1208 ciToUpper(&key); 1209 } 1210 1211 n = NDTINTERNAL(key.namlen); 1212 break; 1213 1214 case BT_INTERNAL: 1215 dtGetKey(rp, 0, &key, sbi->mntflag); 1216 n = NDTINTERNAL(key.namlen); 1217 break; 1218 1219 default: 1220 jfs_err("dtSplitUp(): UFO!"); 1221 break; 1222 } 1223 1224 /* unpin left child page */ 1225 DT_PUTPAGE(lmp); 1226 1227 /* 1228 * compute the data for the router entry 1229 */ 1230 data->xd = rpxd; /* child page xd */ 1231 1232 /* 1233 * parent page is full - split the parent page 1234 */ 1235 if (n > sp->header.freecnt) { 1236 /* init for parent page split */ 1237 split->mp = smp; 1238 split->index = skip; /* index at insert */ 1239 split->nslot = n; 1240 split->key = &key; 1241 /* split->data = data; */ 1242 1243 /* unpin right child page */ 1244 DT_PUTPAGE(rmp); 1245 1246 /* The split routines insert the new entry, 1247 * acquire txLock as appropriate. 1248 * return <rp> pinned and its block number <rbn>. 1249 */ 1250 rc = (sp->header.flag & BT_ROOT) ? 1251 dtSplitRoot(tid, ip, split, &rmp) : 1252 dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd); 1253 if (rc) { 1254 DT_PUTPAGE(smp); 1255 goto splitOut; 1256 } 1257 1258 /* smp and rmp are pinned */ 1259 } 1260 /* 1261 * parent page is not full - insert router entry in parent page 1262 */ 1263 else { 1264 BT_MARK_DIRTY(smp, ip); 1265 /* 1266 * acquire a transaction lock on the parent page 1267 */ 1268 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); 1269 dtlck = (struct dt_lock *) & tlck->lock; 1270 ASSERT(dtlck->index == 0); 1271 lv = & dtlck->lv[0]; 1272 1273 /* linelock header */ 1274 lv->offset = 0; 1275 lv->length = 1; 1276 dtlck->index++; 1277 1278 /* linelock stbl of non-root parent page */ 1279 if (!(sp->header.flag & BT_ROOT)) { 1280 lv++; 1281 n = skip >> L2DTSLOTSIZE; 1282 lv->offset = sp->header.stblindex + n; 1283 lv->length = 1284 ((sp->header.nextindex - 1285 1) >> L2DTSLOTSIZE) - n + 1; 1286 dtlck->index++; 1287 } 1288 1289 dtInsertEntry(sp, skip, &key, data, &dtlck); 1290 1291 /* exit propagate up */ 1292 break; 1293 } 1294 } 1295 1296 /* unpin current split and its right page */ 1297 DT_PUTPAGE(smp); 1298 DT_PUTPAGE(rmp); 1299 1300 /* 1301 * free remaining extents allocated for split 1302 */ 1303 splitOut: 1304 n = pxdlist.npxd; 1305 pxd = &pxdlist.pxd[n]; 1306 for (; n < pxdlist.maxnpxd; n++, pxd++) 1307 dbFree(ip, addressPXD(pxd), (s64) lengthPXD(pxd)); 1308 1309 freeKeyName: 1310 kfree(key.name); 1311 1312 /* Rollback quota allocation */ 1313 if (rc && quota_allocation) 1314 DQUOT_FREE_BLOCK(ip, quota_allocation); 1315 1316 dtSplitUp_Exit: 1317 1318 return rc; 1319 } 1320 1321 1322 /* 1323 * dtSplitPage() 1324 * 1325 * function: Split a non-root page of a btree. 1326 * 1327 * parameter: 1328 * 1329 * return: 0 - success; 1330 * errno - failure; 1331 * return split and new page pinned; 1332 */ 1333 static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split, 1334 struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rpxdp) 1335 { 1336 int rc = 0; 1337 struct metapage *smp; 1338 dtpage_t *sp; 1339 struct metapage *rmp; 1340 dtpage_t *rp; /* new right page allocated */ 1341 s64 rbn; /* new right page block number */ 1342 struct metapage *mp; 1343 dtpage_t *p; 1344 s64 nextbn; 1345 struct pxdlist *pxdlist; 1346 pxd_t *pxd; 1347 int skip, nextindex, half, left, nxt, off, si; 1348 struct ldtentry *ldtentry; 1349 struct idtentry *idtentry; 1350 u8 *stbl; 1351 struct dtslot *f; 1352 int fsi, stblsize; 1353 int n; 1354 struct dt_lock *sdtlck, *rdtlck; 1355 struct tlock *tlck; 1356 struct dt_lock *dtlck; 1357 struct lv *slv, *rlv, *lv; 1358 1359 /* get split page */ 1360 smp = split->mp; 1361 sp = DT_PAGE(ip, smp); 1362 1363 /* 1364 * allocate the new right page for the split 1365 */ 1366 pxdlist = split->pxdlist; 1367 pxd = &pxdlist->pxd[pxdlist->npxd]; 1368 pxdlist->npxd++; 1369 rbn = addressPXD(pxd); 1370 rmp = get_metapage(ip, rbn, PSIZE, 1); 1371 if (rmp == NULL) 1372 return -EIO; 1373 1374 /* Allocate blocks to quota. */ 1375 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) { 1376 release_metapage(rmp); 1377 return -EDQUOT; 1378 } 1379 1380 jfs_info("dtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp); 1381 1382 BT_MARK_DIRTY(rmp, ip); 1383 /* 1384 * acquire a transaction lock on the new right page 1385 */ 1386 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW); 1387 rdtlck = (struct dt_lock *) & tlck->lock; 1388 1389 rp = (dtpage_t *) rmp->data; 1390 *rpp = rp; 1391 rp->header.self = *pxd; 1392 1393 BT_MARK_DIRTY(smp, ip); 1394 /* 1395 * acquire a transaction lock on the split page 1396 * 1397 * action: 1398 */ 1399 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); 1400 sdtlck = (struct dt_lock *) & tlck->lock; 1401 1402 /* linelock header of split page */ 1403 ASSERT(sdtlck->index == 0); 1404 slv = & sdtlck->lv[0]; 1405 slv->offset = 0; 1406 slv->length = 1; 1407 sdtlck->index++; 1408 1409 /* 1410 * initialize/update sibling pointers between sp and rp 1411 */ 1412 nextbn = le64_to_cpu(sp->header.next); 1413 rp->header.next = cpu_to_le64(nextbn); 1414 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); 1415 sp->header.next = cpu_to_le64(rbn); 1416 1417 /* 1418 * initialize new right page 1419 */ 1420 rp->header.flag = sp->header.flag; 1421 1422 /* compute sorted entry table at start of extent data area */ 1423 rp->header.nextindex = 0; 1424 rp->header.stblindex = 1; 1425 1426 n = PSIZE >> L2DTSLOTSIZE; 1427 rp->header.maxslot = n; 1428 stblsize = (n + 31) >> L2DTSLOTSIZE; /* in unit of slot */ 1429 1430 /* init freelist */ 1431 fsi = rp->header.stblindex + stblsize; 1432 rp->header.freelist = fsi; 1433 rp->header.freecnt = rp->header.maxslot - fsi; 1434 1435 /* 1436 * sequential append at tail: append without split 1437 * 1438 * If splitting the last page on a level because of appending 1439 * a entry to it (skip is maxentry), it's likely that the access is 1440 * sequential. Adding an empty page on the side of the level is less 1441 * work and can push the fill factor much higher than normal. 1442 * If we're wrong it's no big deal, we'll just do the split the right 1443 * way next time. 1444 * (It may look like it's equally easy to do a similar hack for 1445 * reverse sorted data, that is, split the tree left, 1446 * but it's not. Be my guest.) 1447 */ 1448 if (nextbn == 0 && split->index == sp->header.nextindex) { 1449 /* linelock header + stbl (first slot) of new page */ 1450 rlv = & rdtlck->lv[rdtlck->index]; 1451 rlv->offset = 0; 1452 rlv->length = 2; 1453 rdtlck->index++; 1454 1455 /* 1456 * initialize freelist of new right page 1457 */ 1458 f = &rp->slot[fsi]; 1459 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) 1460 f->next = fsi; 1461 f->next = -1; 1462 1463 /* insert entry at the first entry of the new right page */ 1464 dtInsertEntry(rp, 0, split->key, split->data, &rdtlck); 1465 1466 goto out; 1467 } 1468 1469 /* 1470 * non-sequential insert (at possibly middle page) 1471 */ 1472 1473 /* 1474 * update prev pointer of previous right sibling page; 1475 */ 1476 if (nextbn != 0) { 1477 DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc); 1478 if (rc) { 1479 discard_metapage(rmp); 1480 return rc; 1481 } 1482 1483 BT_MARK_DIRTY(mp, ip); 1484 /* 1485 * acquire a transaction lock on the next page 1486 */ 1487 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK); 1488 jfs_info("dtSplitPage: tlck = 0x%p, ip = 0x%p, mp=0x%p", 1489 tlck, ip, mp); 1490 dtlck = (struct dt_lock *) & tlck->lock; 1491 1492 /* linelock header of previous right sibling page */ 1493 lv = & dtlck->lv[dtlck->index]; 1494 lv->offset = 0; 1495 lv->length = 1; 1496 dtlck->index++; 1497 1498 p->header.prev = cpu_to_le64(rbn); 1499 1500 DT_PUTPAGE(mp); 1501 } 1502 1503 /* 1504 * split the data between the split and right pages. 1505 */ 1506 skip = split->index; 1507 half = (PSIZE >> L2DTSLOTSIZE) >> 1; /* swag */ 1508 left = 0; 1509 1510 /* 1511 * compute fill factor for split pages 1512 * 1513 * <nxt> traces the next entry to move to rp 1514 * <off> traces the next entry to stay in sp 1515 */ 1516 stbl = (u8 *) & sp->slot[sp->header.stblindex]; 1517 nextindex = sp->header.nextindex; 1518 for (nxt = off = 0; nxt < nextindex; ++off) { 1519 if (off == skip) 1520 /* check for fill factor with new entry size */ 1521 n = split->nslot; 1522 else { 1523 si = stbl[nxt]; 1524 switch (sp->header.flag & BT_TYPE) { 1525 case BT_LEAF: 1526 ldtentry = (struct ldtentry *) & sp->slot[si]; 1527 if (DO_INDEX(ip)) 1528 n = NDTLEAF(ldtentry->namlen); 1529 else 1530 n = NDTLEAF_LEGACY(ldtentry-> 1531 namlen); 1532 break; 1533 1534 case BT_INTERNAL: 1535 idtentry = (struct idtentry *) & sp->slot[si]; 1536 n = NDTINTERNAL(idtentry->namlen); 1537 break; 1538 1539 default: 1540 break; 1541 } 1542 1543 ++nxt; /* advance to next entry to move in sp */ 1544 } 1545 1546 left += n; 1547 if (left >= half) 1548 break; 1549 } 1550 1551 /* <nxt> poins to the 1st entry to move */ 1552 1553 /* 1554 * move entries to right page 1555 * 1556 * dtMoveEntry() initializes rp and reserves entry for insertion 1557 * 1558 * split page moved out entries are linelocked; 1559 * new/right page moved in entries are linelocked; 1560 */ 1561 /* linelock header + stbl of new right page */ 1562 rlv = & rdtlck->lv[rdtlck->index]; 1563 rlv->offset = 0; 1564 rlv->length = 5; 1565 rdtlck->index++; 1566 1567 dtMoveEntry(sp, nxt, rp, &sdtlck, &rdtlck, DO_INDEX(ip)); 1568 1569 sp->header.nextindex = nxt; 1570 1571 /* 1572 * finalize freelist of new right page 1573 */ 1574 fsi = rp->header.freelist; 1575 f = &rp->slot[fsi]; 1576 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) 1577 f->next = fsi; 1578 f->next = -1; 1579 1580 /* 1581 * Update directory index table for entries now in right page 1582 */ 1583 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { 1584 s64 lblock; 1585 1586 mp = NULL; 1587 stbl = DT_GETSTBL(rp); 1588 for (n = 0; n < rp->header.nextindex; n++) { 1589 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; 1590 modify_index(tid, ip, le32_to_cpu(ldtentry->index), 1591 rbn, n, &mp, &lblock); 1592 } 1593 if (mp) 1594 release_metapage(mp); 1595 } 1596 1597 /* 1598 * the skipped index was on the left page, 1599 */ 1600 if (skip <= off) { 1601 /* insert the new entry in the split page */ 1602 dtInsertEntry(sp, skip, split->key, split->data, &sdtlck); 1603 1604 /* linelock stbl of split page */ 1605 if (sdtlck->index >= sdtlck->maxcnt) 1606 sdtlck = (struct dt_lock *) txLinelock(sdtlck); 1607 slv = & sdtlck->lv[sdtlck->index]; 1608 n = skip >> L2DTSLOTSIZE; 1609 slv->offset = sp->header.stblindex + n; 1610 slv->length = 1611 ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; 1612 sdtlck->index++; 1613 } 1614 /* 1615 * the skipped index was on the right page, 1616 */ 1617 else { 1618 /* adjust the skip index to reflect the new position */ 1619 skip -= nxt; 1620 1621 /* insert the new entry in the right page */ 1622 dtInsertEntry(rp, skip, split->key, split->data, &rdtlck); 1623 } 1624 1625 out: 1626 *rmpp = rmp; 1627 *rpxdp = *pxd; 1628 1629 return rc; 1630 } 1631 1632 1633 /* 1634 * dtExtendPage() 1635 * 1636 * function: extend 1st/only directory leaf page 1637 * 1638 * parameter: 1639 * 1640 * return: 0 - success; 1641 * errno - failure; 1642 * return extended page pinned; 1643 */ 1644 static int dtExtendPage(tid_t tid, 1645 struct inode *ip, struct dtsplit * split, struct btstack * btstack) 1646 { 1647 struct super_block *sb = ip->i_sb; 1648 int rc; 1649 struct metapage *smp, *pmp, *mp; 1650 dtpage_t *sp, *pp; 1651 struct pxdlist *pxdlist; 1652 pxd_t *pxd, *tpxd; 1653 int xlen, xsize; 1654 int newstblindex, newstblsize; 1655 int oldstblindex, oldstblsize; 1656 int fsi, last; 1657 struct dtslot *f; 1658 struct btframe *parent; 1659 int n; 1660 struct dt_lock *dtlck; 1661 s64 xaddr, txaddr; 1662 struct tlock *tlck; 1663 struct pxd_lock *pxdlock; 1664 struct lv *lv; 1665 uint type; 1666 struct ldtentry *ldtentry; 1667 u8 *stbl; 1668 1669 /* get page to extend */ 1670 smp = split->mp; 1671 sp = DT_PAGE(ip, smp); 1672 1673 /* get parent/root page */ 1674 parent = BT_POP(btstack); 1675 DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc); 1676 if (rc) 1677 return (rc); 1678 1679 /* 1680 * extend the extent 1681 */ 1682 pxdlist = split->pxdlist; 1683 pxd = &pxdlist->pxd[pxdlist->npxd]; 1684 pxdlist->npxd++; 1685 1686 xaddr = addressPXD(pxd); 1687 tpxd = &sp->header.self; 1688 txaddr = addressPXD(tpxd); 1689 /* in-place extension */ 1690 if (xaddr == txaddr) { 1691 type = tlckEXTEND; 1692 } 1693 /* relocation */ 1694 else { 1695 type = tlckNEW; 1696 1697 /* save moved extent descriptor for later free */ 1698 tlck = txMaplock(tid, ip, tlckDTREE | tlckRELOCATE); 1699 pxdlock = (struct pxd_lock *) & tlck->lock; 1700 pxdlock->flag = mlckFREEPXD; 1701 pxdlock->pxd = sp->header.self; 1702 pxdlock->index = 1; 1703 1704 /* 1705 * Update directory index table to reflect new page address 1706 */ 1707 if (DO_INDEX(ip)) { 1708 s64 lblock; 1709 1710 mp = NULL; 1711 stbl = DT_GETSTBL(sp); 1712 for (n = 0; n < sp->header.nextindex; n++) { 1713 ldtentry = 1714 (struct ldtentry *) & sp->slot[stbl[n]]; 1715 modify_index(tid, ip, 1716 le32_to_cpu(ldtentry->index), 1717 xaddr, n, &mp, &lblock); 1718 } 1719 if (mp) 1720 release_metapage(mp); 1721 } 1722 } 1723 1724 /* 1725 * extend the page 1726 */ 1727 sp->header.self = *pxd; 1728 1729 jfs_info("dtExtendPage: ip:0x%p smp:0x%p sp:0x%p", ip, smp, sp); 1730 1731 BT_MARK_DIRTY(smp, ip); 1732 /* 1733 * acquire a transaction lock on the extended/leaf page 1734 */ 1735 tlck = txLock(tid, ip, smp, tlckDTREE | type); 1736 dtlck = (struct dt_lock *) & tlck->lock; 1737 lv = & dtlck->lv[0]; 1738 1739 /* update buffer extent descriptor of extended page */ 1740 xlen = lengthPXD(pxd); 1741 xsize = xlen << JFS_SBI(sb)->l2bsize; 1742 #ifdef _STILL_TO_PORT 1743 bmSetXD(smp, xaddr, xsize); 1744 #endif /* _STILL_TO_PORT */ 1745 1746 /* 1747 * copy old stbl to new stbl at start of extended area 1748 */ 1749 oldstblindex = sp->header.stblindex; 1750 oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE; 1751 newstblindex = sp->header.maxslot; 1752 n = xsize >> L2DTSLOTSIZE; 1753 newstblsize = (n + 31) >> L2DTSLOTSIZE; 1754 memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex], 1755 sp->header.nextindex); 1756 1757 /* 1758 * in-line extension: linelock old area of extended page 1759 */ 1760 if (type == tlckEXTEND) { 1761 /* linelock header */ 1762 lv->offset = 0; 1763 lv->length = 1; 1764 dtlck->index++; 1765 lv++; 1766 1767 /* linelock new stbl of extended page */ 1768 lv->offset = newstblindex; 1769 lv->length = newstblsize; 1770 } 1771 /* 1772 * relocation: linelock whole relocated area 1773 */ 1774 else { 1775 lv->offset = 0; 1776 lv->length = sp->header.maxslot + newstblsize; 1777 } 1778 1779 dtlck->index++; 1780 1781 sp->header.maxslot = n; 1782 sp->header.stblindex = newstblindex; 1783 /* sp->header.nextindex remains the same */ 1784 1785 /* 1786 * add old stbl region at head of freelist 1787 */ 1788 fsi = oldstblindex; 1789 f = &sp->slot[fsi]; 1790 last = sp->header.freelist; 1791 for (n = 0; n < oldstblsize; n++, fsi++, f++) { 1792 f->next = last; 1793 last = fsi; 1794 } 1795 sp->header.freelist = last; 1796 sp->header.freecnt += oldstblsize; 1797 1798 /* 1799 * append free region of newly extended area at tail of freelist 1800 */ 1801 /* init free region of newly extended area */ 1802 fsi = n = newstblindex + newstblsize; 1803 f = &sp->slot[fsi]; 1804 for (fsi++; fsi < sp->header.maxslot; f++, fsi++) 1805 f->next = fsi; 1806 f->next = -1; 1807 1808 /* append new free region at tail of old freelist */ 1809 fsi = sp->header.freelist; 1810 if (fsi == -1) 1811 sp->header.freelist = n; 1812 else { 1813 do { 1814 f = &sp->slot[fsi]; 1815 fsi = f->next; 1816 } while (fsi != -1); 1817 1818 f->next = n; 1819 } 1820 1821 sp->header.freecnt += sp->header.maxslot - n; 1822 1823 /* 1824 * insert the new entry 1825 */ 1826 dtInsertEntry(sp, split->index, split->key, split->data, &dtlck); 1827 1828 BT_MARK_DIRTY(pmp, ip); 1829 /* 1830 * linelock any freeslots residing in old extent 1831 */ 1832 if (type == tlckEXTEND) { 1833 n = sp->header.maxslot >> 2; 1834 if (sp->header.freelist < n) 1835 dtLinelockFreelist(sp, n, &dtlck); 1836 } 1837 1838 /* 1839 * update parent entry on the parent/root page 1840 */ 1841 /* 1842 * acquire a transaction lock on the parent/root page 1843 */ 1844 tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY); 1845 dtlck = (struct dt_lock *) & tlck->lock; 1846 lv = & dtlck->lv[dtlck->index]; 1847 1848 /* linelock parent entry - 1st slot */ 1849 lv->offset = 1; 1850 lv->length = 1; 1851 dtlck->index++; 1852 1853 /* update the parent pxd for page extension */ 1854 tpxd = (pxd_t *) & pp->slot[1]; 1855 *tpxd = *pxd; 1856 1857 DT_PUTPAGE(pmp); 1858 return 0; 1859 } 1860 1861 1862 /* 1863 * dtSplitRoot() 1864 * 1865 * function: 1866 * split the full root page into 1867 * original/root/split page and new right page 1868 * i.e., root remains fixed in tree anchor (inode) and 1869 * the root is copied to a single new right child page 1870 * since root page << non-root page, and 1871 * the split root page contains a single entry for the 1872 * new right child page. 1873 * 1874 * parameter: 1875 * 1876 * return: 0 - success; 1877 * errno - failure; 1878 * return new page pinned; 1879 */ 1880 static int dtSplitRoot(tid_t tid, 1881 struct inode *ip, struct dtsplit * split, struct metapage ** rmpp) 1882 { 1883 struct super_block *sb = ip->i_sb; 1884 struct metapage *smp; 1885 dtroot_t *sp; 1886 struct metapage *rmp; 1887 dtpage_t *rp; 1888 s64 rbn; 1889 int xlen; 1890 int xsize; 1891 struct dtslot *f; 1892 s8 *stbl; 1893 int fsi, stblsize, n; 1894 struct idtentry *s; 1895 pxd_t *ppxd; 1896 struct pxdlist *pxdlist; 1897 pxd_t *pxd; 1898 struct dt_lock *dtlck; 1899 struct tlock *tlck; 1900 struct lv *lv; 1901 1902 /* get split root page */ 1903 smp = split->mp; 1904 sp = &JFS_IP(ip)->i_dtroot; 1905 1906 /* 1907 * allocate/initialize a single (right) child page 1908 * 1909 * N.B. at first split, a one (or two) block to fit new entry 1910 * is allocated; at subsequent split, a full page is allocated; 1911 */ 1912 pxdlist = split->pxdlist; 1913 pxd = &pxdlist->pxd[pxdlist->npxd]; 1914 pxdlist->npxd++; 1915 rbn = addressPXD(pxd); 1916 xlen = lengthPXD(pxd); 1917 xsize = xlen << JFS_SBI(sb)->l2bsize; 1918 rmp = get_metapage(ip, rbn, xsize, 1); 1919 if (!rmp) 1920 return -EIO; 1921 1922 rp = rmp->data; 1923 1924 /* Allocate blocks to quota. */ 1925 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) { 1926 release_metapage(rmp); 1927 return -EDQUOT; 1928 } 1929 1930 BT_MARK_DIRTY(rmp, ip); 1931 /* 1932 * acquire a transaction lock on the new right page 1933 */ 1934 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW); 1935 dtlck = (struct dt_lock *) & tlck->lock; 1936 1937 rp->header.flag = 1938 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; 1939 rp->header.self = *pxd; 1940 1941 /* initialize sibling pointers */ 1942 rp->header.next = 0; 1943 rp->header.prev = 0; 1944 1945 /* 1946 * move in-line root page into new right page extent 1947 */ 1948 /* linelock header + copied entries + new stbl (1st slot) in new page */ 1949 ASSERT(dtlck->index == 0); 1950 lv = & dtlck->lv[0]; 1951 lv->offset = 0; 1952 lv->length = 10; /* 1 + 8 + 1 */ 1953 dtlck->index++; 1954 1955 n = xsize >> L2DTSLOTSIZE; 1956 rp->header.maxslot = n; 1957 stblsize = (n + 31) >> L2DTSLOTSIZE; 1958 1959 /* copy old stbl to new stbl at start of extended area */ 1960 rp->header.stblindex = DTROOTMAXSLOT; 1961 stbl = (s8 *) & rp->slot[DTROOTMAXSLOT]; 1962 memcpy(stbl, sp->header.stbl, sp->header.nextindex); 1963 rp->header.nextindex = sp->header.nextindex; 1964 1965 /* copy old data area to start of new data area */ 1966 memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE); 1967 1968 /* 1969 * append free region of newly extended area at tail of freelist 1970 */ 1971 /* init free region of newly extended area */ 1972 fsi = n = DTROOTMAXSLOT + stblsize; 1973 f = &rp->slot[fsi]; 1974 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) 1975 f->next = fsi; 1976 f->next = -1; 1977 1978 /* append new free region at tail of old freelist */ 1979 fsi = sp->header.freelist; 1980 if (fsi == -1) 1981 rp->header.freelist = n; 1982 else { 1983 rp->header.freelist = fsi; 1984 1985 do { 1986 f = &rp->slot[fsi]; 1987 fsi = f->next; 1988 } while (fsi != -1); 1989 1990 f->next = n; 1991 } 1992 1993 rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n; 1994 1995 /* 1996 * Update directory index table for entries now in right page 1997 */ 1998 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { 1999 s64 lblock; 2000 struct metapage *mp = NULL; 2001 struct ldtentry *ldtentry; 2002 2003 stbl = DT_GETSTBL(rp); 2004 for (n = 0; n < rp->header.nextindex; n++) { 2005 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; 2006 modify_index(tid, ip, le32_to_cpu(ldtentry->index), 2007 rbn, n, &mp, &lblock); 2008 } 2009 if (mp) 2010 release_metapage(mp); 2011 } 2012 /* 2013 * insert the new entry into the new right/child page 2014 * (skip index in the new right page will not change) 2015 */ 2016 dtInsertEntry(rp, split->index, split->key, split->data, &dtlck); 2017 2018 /* 2019 * reset parent/root page 2020 * 2021 * set the 1st entry offset to 0, which force the left-most key 2022 * at any level of the tree to be less than any search key. 2023 * 2024 * The btree comparison code guarantees that the left-most key on any 2025 * level of the tree is never used, so it doesn't need to be filled in. 2026 */ 2027 BT_MARK_DIRTY(smp, ip); 2028 /* 2029 * acquire a transaction lock on the root page (in-memory inode) 2030 */ 2031 tlck = txLock(tid, ip, smp, tlckDTREE | tlckNEW | tlckBTROOT); 2032 dtlck = (struct dt_lock *) & tlck->lock; 2033 2034 /* linelock root */ 2035 ASSERT(dtlck->index == 0); 2036 lv = & dtlck->lv[0]; 2037 lv->offset = 0; 2038 lv->length = DTROOTMAXSLOT; 2039 dtlck->index++; 2040 2041 /* update page header of root */ 2042 if (sp->header.flag & BT_LEAF) { 2043 sp->header.flag &= ~BT_LEAF; 2044 sp->header.flag |= BT_INTERNAL; 2045 } 2046 2047 /* init the first entry */ 2048 s = (struct idtentry *) & sp->slot[DTENTRYSTART]; 2049 ppxd = (pxd_t *) s; 2050 *ppxd = *pxd; 2051 s->next = -1; 2052 s->namlen = 0; 2053 2054 stbl = sp->header.stbl; 2055 stbl[0] = DTENTRYSTART; 2056 sp->header.nextindex = 1; 2057 2058 /* init freelist */ 2059 fsi = DTENTRYSTART + 1; 2060 f = &sp->slot[fsi]; 2061 2062 /* init free region of remaining area */ 2063 for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++) 2064 f->next = fsi; 2065 f->next = -1; 2066 2067 sp->header.freelist = DTENTRYSTART + 1; 2068 sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1); 2069 2070 *rmpp = rmp; 2071 2072 return 0; 2073 } 2074 2075 2076 /* 2077 * dtDelete() 2078 * 2079 * function: delete the entry(s) referenced by a key. 2080 * 2081 * parameter: 2082 * 2083 * return: 2084 */ 2085 int dtDelete(tid_t tid, 2086 struct inode *ip, struct component_name * key, ino_t * ino, int flag) 2087 { 2088 int rc = 0; 2089 s64 bn; 2090 struct metapage *mp, *imp; 2091 dtpage_t *p; 2092 int index; 2093 struct btstack btstack; 2094 struct dt_lock *dtlck; 2095 struct tlock *tlck; 2096 struct lv *lv; 2097 int i; 2098 struct ldtentry *ldtentry; 2099 u8 *stbl; 2100 u32 table_index, next_index; 2101 struct metapage *nmp; 2102 dtpage_t *np; 2103 2104 /* 2105 * search for the entry to delete: 2106 * 2107 * dtSearch() returns (leaf page pinned, index at which to delete). 2108 */ 2109 if ((rc = dtSearch(ip, key, ino, &btstack, flag))) 2110 return rc; 2111 2112 /* retrieve search result */ 2113 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 2114 2115 /* 2116 * We need to find put the index of the next entry into the 2117 * directory index table in order to resume a readdir from this 2118 * entry. 2119 */ 2120 if (DO_INDEX(ip)) { 2121 stbl = DT_GETSTBL(p); 2122 ldtentry = (struct ldtentry *) & p->slot[stbl[index]]; 2123 table_index = le32_to_cpu(ldtentry->index); 2124 if (index == (p->header.nextindex - 1)) { 2125 /* 2126 * Last entry in this leaf page 2127 */ 2128 if ((p->header.flag & BT_ROOT) 2129 || (p->header.next == 0)) 2130 next_index = -1; 2131 else { 2132 /* Read next leaf page */ 2133 DT_GETPAGE(ip, le64_to_cpu(p->header.next), 2134 nmp, PSIZE, np, rc); 2135 if (rc) 2136 next_index = -1; 2137 else { 2138 stbl = DT_GETSTBL(np); 2139 ldtentry = 2140 (struct ldtentry *) & np-> 2141 slot[stbl[0]]; 2142 next_index = 2143 le32_to_cpu(ldtentry->index); 2144 DT_PUTPAGE(nmp); 2145 } 2146 } 2147 } else { 2148 ldtentry = 2149 (struct ldtentry *) & p->slot[stbl[index + 1]]; 2150 next_index = le32_to_cpu(ldtentry->index); 2151 } 2152 free_index(tid, ip, table_index, next_index); 2153 } 2154 /* 2155 * the leaf page becomes empty, delete the page 2156 */ 2157 if (p->header.nextindex == 1) { 2158 /* delete empty page */ 2159 rc = dtDeleteUp(tid, ip, mp, p, &btstack); 2160 } 2161 /* 2162 * the leaf page has other entries remaining: 2163 * 2164 * delete the entry from the leaf page. 2165 */ 2166 else { 2167 BT_MARK_DIRTY(mp, ip); 2168 /* 2169 * acquire a transaction lock on the leaf page 2170 */ 2171 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY); 2172 dtlck = (struct dt_lock *) & tlck->lock; 2173 2174 /* 2175 * Do not assume that dtlck->index will be zero. During a 2176 * rename within a directory, this transaction may have 2177 * modified this page already when adding the new entry. 2178 */ 2179 2180 /* linelock header */ 2181 if (dtlck->index >= dtlck->maxcnt) 2182 dtlck = (struct dt_lock *) txLinelock(dtlck); 2183 lv = & dtlck->lv[dtlck->index]; 2184 lv->offset = 0; 2185 lv->length = 1; 2186 dtlck->index++; 2187 2188 /* linelock stbl of non-root leaf page */ 2189 if (!(p->header.flag & BT_ROOT)) { 2190 if (dtlck->index >= dtlck->maxcnt) 2191 dtlck = (struct dt_lock *) txLinelock(dtlck); 2192 lv = & dtlck->lv[dtlck->index]; 2193 i = index >> L2DTSLOTSIZE; 2194 lv->offset = p->header.stblindex + i; 2195 lv->length = 2196 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - 2197 i + 1; 2198 dtlck->index++; 2199 } 2200 2201 /* free the leaf entry */ 2202 dtDeleteEntry(p, index, &dtlck); 2203 2204 /* 2205 * Update directory index table for entries moved in stbl 2206 */ 2207 if (DO_INDEX(ip) && index < p->header.nextindex) { 2208 s64 lblock; 2209 2210 imp = NULL; 2211 stbl = DT_GETSTBL(p); 2212 for (i = index; i < p->header.nextindex; i++) { 2213 ldtentry = 2214 (struct ldtentry *) & p->slot[stbl[i]]; 2215 modify_index(tid, ip, 2216 le32_to_cpu(ldtentry->index), 2217 bn, i, &imp, &lblock); 2218 } 2219 if (imp) 2220 release_metapage(imp); 2221 } 2222 2223 DT_PUTPAGE(mp); 2224 } 2225 2226 return rc; 2227 } 2228 2229 2230 /* 2231 * dtDeleteUp() 2232 * 2233 * function: 2234 * free empty pages as propagating deletion up the tree 2235 * 2236 * parameter: 2237 * 2238 * return: 2239 */ 2240 static int dtDeleteUp(tid_t tid, struct inode *ip, 2241 struct metapage * fmp, dtpage_t * fp, struct btstack * btstack) 2242 { 2243 int rc = 0; 2244 struct metapage *mp; 2245 dtpage_t *p; 2246 int index, nextindex; 2247 int xlen; 2248 struct btframe *parent; 2249 struct dt_lock *dtlck; 2250 struct tlock *tlck; 2251 struct lv *lv; 2252 struct pxd_lock *pxdlock; 2253 int i; 2254 2255 /* 2256 * keep the root leaf page which has become empty 2257 */ 2258 if (BT_IS_ROOT(fmp)) { 2259 /* 2260 * reset the root 2261 * 2262 * dtInitRoot() acquires txlock on the root 2263 */ 2264 dtInitRoot(tid, ip, PARENT(ip)); 2265 2266 DT_PUTPAGE(fmp); 2267 2268 return 0; 2269 } 2270 2271 /* 2272 * free the non-root leaf page 2273 */ 2274 /* 2275 * acquire a transaction lock on the page 2276 * 2277 * write FREEXTENT|NOREDOPAGE log record 2278 * N.B. linelock is overlaid as freed extent descriptor, and 2279 * the buffer page is freed; 2280 */ 2281 tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE); 2282 pxdlock = (struct pxd_lock *) & tlck->lock; 2283 pxdlock->flag = mlckFREEPXD; 2284 pxdlock->pxd = fp->header.self; 2285 pxdlock->index = 1; 2286 2287 /* update sibling pointers */ 2288 if ((rc = dtRelink(tid, ip, fp))) { 2289 BT_PUTPAGE(fmp); 2290 return rc; 2291 } 2292 2293 xlen = lengthPXD(&fp->header.self); 2294 2295 /* Free quota allocation. */ 2296 DQUOT_FREE_BLOCK(ip, xlen); 2297 2298 /* free/invalidate its buffer page */ 2299 discard_metapage(fmp); 2300 2301 /* 2302 * propagate page deletion up the directory tree 2303 * 2304 * If the delete from the parent page makes it empty, 2305 * continue all the way up the tree. 2306 * stop if the root page is reached (which is never deleted) or 2307 * if the entry deletion does not empty the page. 2308 */ 2309 while ((parent = BT_POP(btstack)) != NULL) { 2310 /* pin the parent page <sp> */ 2311 DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); 2312 if (rc) 2313 return rc; 2314 2315 /* 2316 * free the extent of the child page deleted 2317 */ 2318 index = parent->index; 2319 2320 /* 2321 * delete the entry for the child page from parent 2322 */ 2323 nextindex = p->header.nextindex; 2324 2325 /* 2326 * the parent has the single entry being deleted: 2327 * 2328 * free the parent page which has become empty. 2329 */ 2330 if (nextindex == 1) { 2331 /* 2332 * keep the root internal page which has become empty 2333 */ 2334 if (p->header.flag & BT_ROOT) { 2335 /* 2336 * reset the root 2337 * 2338 * dtInitRoot() acquires txlock on the root 2339 */ 2340 dtInitRoot(tid, ip, PARENT(ip)); 2341 2342 DT_PUTPAGE(mp); 2343 2344 return 0; 2345 } 2346 /* 2347 * free the parent page 2348 */ 2349 else { 2350 /* 2351 * acquire a transaction lock on the page 2352 * 2353 * write FREEXTENT|NOREDOPAGE log record 2354 */ 2355 tlck = 2356 txMaplock(tid, ip, 2357 tlckDTREE | tlckFREE); 2358 pxdlock = (struct pxd_lock *) & tlck->lock; 2359 pxdlock->flag = mlckFREEPXD; 2360 pxdlock->pxd = p->header.self; 2361 pxdlock->index = 1; 2362 2363 /* update sibling pointers */ 2364 if ((rc = dtRelink(tid, ip, p))) { 2365 DT_PUTPAGE(mp); 2366 return rc; 2367 } 2368 2369 xlen = lengthPXD(&p->header.self); 2370 2371 /* Free quota allocation */ 2372 DQUOT_FREE_BLOCK(ip, xlen); 2373 2374 /* free/invalidate its buffer page */ 2375 discard_metapage(mp); 2376 2377 /* propagate up */ 2378 continue; 2379 } 2380 } 2381 2382 /* 2383 * the parent has other entries remaining: 2384 * 2385 * delete the router entry from the parent page. 2386 */ 2387 BT_MARK_DIRTY(mp, ip); 2388 /* 2389 * acquire a transaction lock on the page 2390 * 2391 * action: router entry deletion 2392 */ 2393 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY); 2394 dtlck = (struct dt_lock *) & tlck->lock; 2395 2396 /* linelock header */ 2397 if (dtlck->index >= dtlck->maxcnt) 2398 dtlck = (struct dt_lock *) txLinelock(dtlck); 2399 lv = & dtlck->lv[dtlck->index]; 2400 lv->offset = 0; 2401 lv->length = 1; 2402 dtlck->index++; 2403 2404 /* linelock stbl of non-root leaf page */ 2405 if (!(p->header.flag & BT_ROOT)) { 2406 if (dtlck->index < dtlck->maxcnt) 2407 lv++; 2408 else { 2409 dtlck = (struct dt_lock *) txLinelock(dtlck); 2410 lv = & dtlck->lv[0]; 2411 } 2412 i = index >> L2DTSLOTSIZE; 2413 lv->offset = p->header.stblindex + i; 2414 lv->length = 2415 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - 2416 i + 1; 2417 dtlck->index++; 2418 } 2419 2420 /* free the router entry */ 2421 dtDeleteEntry(p, index, &dtlck); 2422 2423 /* reset key of new leftmost entry of level (for consistency) */ 2424 if (index == 0 && 2425 ((p->header.flag & BT_ROOT) || p->header.prev == 0)) 2426 dtTruncateEntry(p, 0, &dtlck); 2427 2428 /* unpin the parent page */ 2429 DT_PUTPAGE(mp); 2430 2431 /* exit propagation up */ 2432 break; 2433 } 2434 2435 if (!DO_INDEX(ip)) 2436 ip->i_size -= PSIZE; 2437 2438 return 0; 2439 } 2440 2441 #ifdef _NOTYET 2442 /* 2443 * NAME: dtRelocate() 2444 * 2445 * FUNCTION: relocate dtpage (internal or leaf) of directory; 2446 * This function is mainly used by defragfs utility. 2447 */ 2448 int dtRelocate(tid_t tid, struct inode *ip, s64 lmxaddr, pxd_t * opxd, 2449 s64 nxaddr) 2450 { 2451 int rc = 0; 2452 struct metapage *mp, *pmp, *lmp, *rmp; 2453 dtpage_t *p, *pp, *rp = 0, *lp= 0; 2454 s64 bn; 2455 int index; 2456 struct btstack btstack; 2457 pxd_t *pxd; 2458 s64 oxaddr, nextbn, prevbn; 2459 int xlen, xsize; 2460 struct tlock *tlck; 2461 struct dt_lock *dtlck; 2462 struct pxd_lock *pxdlock; 2463 s8 *stbl; 2464 struct lv *lv; 2465 2466 oxaddr = addressPXD(opxd); 2467 xlen = lengthPXD(opxd); 2468 2469 jfs_info("dtRelocate: lmxaddr:%Ld xaddr:%Ld:%Ld xlen:%d", 2470 (long long)lmxaddr, (long long)oxaddr, (long long)nxaddr, 2471 xlen); 2472 2473 /* 2474 * 1. get the internal parent dtpage covering 2475 * router entry for the tartget page to be relocated; 2476 */ 2477 rc = dtSearchNode(ip, lmxaddr, opxd, &btstack); 2478 if (rc) 2479 return rc; 2480 2481 /* retrieve search result */ 2482 DT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); 2483 jfs_info("dtRelocate: parent router entry validated."); 2484 2485 /* 2486 * 2. relocate the target dtpage 2487 */ 2488 /* read in the target page from src extent */ 2489 DT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc); 2490 if (rc) { 2491 /* release the pinned parent page */ 2492 DT_PUTPAGE(pmp); 2493 return rc; 2494 } 2495 2496 /* 2497 * read in sibling pages if any to update sibling pointers; 2498 */ 2499 rmp = NULL; 2500 if (p->header.next) { 2501 nextbn = le64_to_cpu(p->header.next); 2502 DT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc); 2503 if (rc) { 2504 DT_PUTPAGE(mp); 2505 DT_PUTPAGE(pmp); 2506 return (rc); 2507 } 2508 } 2509 2510 lmp = NULL; 2511 if (p->header.prev) { 2512 prevbn = le64_to_cpu(p->header.prev); 2513 DT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc); 2514 if (rc) { 2515 DT_PUTPAGE(mp); 2516 DT_PUTPAGE(pmp); 2517 if (rmp) 2518 DT_PUTPAGE(rmp); 2519 return (rc); 2520 } 2521 } 2522 2523 /* at this point, all xtpages to be updated are in memory */ 2524 2525 /* 2526 * update sibling pointers of sibling dtpages if any; 2527 */ 2528 if (lmp) { 2529 tlck = txLock(tid, ip, lmp, tlckDTREE | tlckRELINK); 2530 dtlck = (struct dt_lock *) & tlck->lock; 2531 /* linelock header */ 2532 ASSERT(dtlck->index == 0); 2533 lv = & dtlck->lv[0]; 2534 lv->offset = 0; 2535 lv->length = 1; 2536 dtlck->index++; 2537 2538 lp->header.next = cpu_to_le64(nxaddr); 2539 DT_PUTPAGE(lmp); 2540 } 2541 2542 if (rmp) { 2543 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckRELINK); 2544 dtlck = (struct dt_lock *) & tlck->lock; 2545 /* linelock header */ 2546 ASSERT(dtlck->index == 0); 2547 lv = & dtlck->lv[0]; 2548 lv->offset = 0; 2549 lv->length = 1; 2550 dtlck->index++; 2551 2552 rp->header.prev = cpu_to_le64(nxaddr); 2553 DT_PUTPAGE(rmp); 2554 } 2555 2556 /* 2557 * update the target dtpage to be relocated 2558 * 2559 * write LOG_REDOPAGE of LOG_NEW type for dst page 2560 * for the whole target page (logredo() will apply 2561 * after image and update bmap for allocation of the 2562 * dst extent), and update bmap for allocation of 2563 * the dst extent; 2564 */ 2565 tlck = txLock(tid, ip, mp, tlckDTREE | tlckNEW); 2566 dtlck = (struct dt_lock *) & tlck->lock; 2567 /* linelock header */ 2568 ASSERT(dtlck->index == 0); 2569 lv = & dtlck->lv[0]; 2570 2571 /* update the self address in the dtpage header */ 2572 pxd = &p->header.self; 2573 PXDaddress(pxd, nxaddr); 2574 2575 /* the dst page is the same as the src page, i.e., 2576 * linelock for afterimage of the whole page; 2577 */ 2578 lv->offset = 0; 2579 lv->length = p->header.maxslot; 2580 dtlck->index++; 2581 2582 /* update the buffer extent descriptor of the dtpage */ 2583 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize; 2584 #ifdef _STILL_TO_PORT 2585 bmSetXD(mp, nxaddr, xsize); 2586 #endif /* _STILL_TO_PORT */ 2587 /* unpin the relocated page */ 2588 DT_PUTPAGE(mp); 2589 jfs_info("dtRelocate: target dtpage relocated."); 2590 2591 /* the moved extent is dtpage, then a LOG_NOREDOPAGE log rec 2592 * needs to be written (in logredo(), the LOG_NOREDOPAGE log rec 2593 * will also force a bmap update ). 2594 */ 2595 2596 /* 2597 * 3. acquire maplock for the source extent to be freed; 2598 */ 2599 /* for dtpage relocation, write a LOG_NOREDOPAGE record 2600 * for the source dtpage (logredo() will init NoRedoPage 2601 * filter and will also update bmap for free of the source 2602 * dtpage), and upadte bmap for free of the source dtpage; 2603 */ 2604 tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE); 2605 pxdlock = (struct pxd_lock *) & tlck->lock; 2606 pxdlock->flag = mlckFREEPXD; 2607 PXDaddress(&pxdlock->pxd, oxaddr); 2608 PXDlength(&pxdlock->pxd, xlen); 2609 pxdlock->index = 1; 2610 2611 /* 2612 * 4. update the parent router entry for relocation; 2613 * 2614 * acquire tlck for the parent entry covering the target dtpage; 2615 * write LOG_REDOPAGE to apply after image only; 2616 */ 2617 jfs_info("dtRelocate: update parent router entry."); 2618 tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY); 2619 dtlck = (struct dt_lock *) & tlck->lock; 2620 lv = & dtlck->lv[dtlck->index]; 2621 2622 /* update the PXD with the new address */ 2623 stbl = DT_GETSTBL(pp); 2624 pxd = (pxd_t *) & pp->slot[stbl[index]]; 2625 PXDaddress(pxd, nxaddr); 2626 lv->offset = stbl[index]; 2627 lv->length = 1; 2628 dtlck->index++; 2629 2630 /* unpin the parent dtpage */ 2631 DT_PUTPAGE(pmp); 2632 2633 return rc; 2634 } 2635 2636 /* 2637 * NAME: dtSearchNode() 2638 * 2639 * FUNCTION: Search for an dtpage containing a specified address 2640 * This function is mainly used by defragfs utility. 2641 * 2642 * NOTE: Search result on stack, the found page is pinned at exit. 2643 * The result page must be an internal dtpage. 2644 * lmxaddr give the address of the left most page of the 2645 * dtree level, in which the required dtpage resides. 2646 */ 2647 static int dtSearchNode(struct inode *ip, s64 lmxaddr, pxd_t * kpxd, 2648 struct btstack * btstack) 2649 { 2650 int rc = 0; 2651 s64 bn; 2652 struct metapage *mp; 2653 dtpage_t *p; 2654 int psize = 288; /* initial in-line directory */ 2655 s8 *stbl; 2656 int i; 2657 pxd_t *pxd; 2658 struct btframe *btsp; 2659 2660 BT_CLR(btstack); /* reset stack */ 2661 2662 /* 2663 * descend tree to the level with specified leftmost page 2664 * 2665 * by convention, root bn = 0. 2666 */ 2667 for (bn = 0;;) { 2668 /* get/pin the page to search */ 2669 DT_GETPAGE(ip, bn, mp, psize, p, rc); 2670 if (rc) 2671 return rc; 2672 2673 /* does the xaddr of leftmost page of the levevl 2674 * matches levevl search key ? 2675 */ 2676 if (p->header.flag & BT_ROOT) { 2677 if (lmxaddr == 0) 2678 break; 2679 } else if (addressPXD(&p->header.self) == lmxaddr) 2680 break; 2681 2682 /* 2683 * descend down to leftmost child page 2684 */ 2685 if (p->header.flag & BT_LEAF) { 2686 DT_PUTPAGE(mp); 2687 return -ESTALE; 2688 } 2689 2690 /* get the leftmost entry */ 2691 stbl = DT_GETSTBL(p); 2692 pxd = (pxd_t *) & p->slot[stbl[0]]; 2693 2694 /* get the child page block address */ 2695 bn = addressPXD(pxd); 2696 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; 2697 /* unpin the parent page */ 2698 DT_PUTPAGE(mp); 2699 } 2700 2701 /* 2702 * search each page at the current levevl 2703 */ 2704 loop: 2705 stbl = DT_GETSTBL(p); 2706 for (i = 0; i < p->header.nextindex; i++) { 2707 pxd = (pxd_t *) & p->slot[stbl[i]]; 2708 2709 /* found the specified router entry */ 2710 if (addressPXD(pxd) == addressPXD(kpxd) && 2711 lengthPXD(pxd) == lengthPXD(kpxd)) { 2712 btsp = btstack->top; 2713 btsp->bn = bn; 2714 btsp->index = i; 2715 btsp->mp = mp; 2716 2717 return 0; 2718 } 2719 } 2720 2721 /* get the right sibling page if any */ 2722 if (p->header.next) 2723 bn = le64_to_cpu(p->header.next); 2724 else { 2725 DT_PUTPAGE(mp); 2726 return -ESTALE; 2727 } 2728 2729 /* unpin current page */ 2730 DT_PUTPAGE(mp); 2731 2732 /* get the right sibling page */ 2733 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 2734 if (rc) 2735 return rc; 2736 2737 goto loop; 2738 } 2739 #endif /* _NOTYET */ 2740 2741 /* 2742 * dtRelink() 2743 * 2744 * function: 2745 * link around a freed page. 2746 * 2747 * parameter: 2748 * fp: page to be freed 2749 * 2750 * return: 2751 */ 2752 static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p) 2753 { 2754 int rc; 2755 struct metapage *mp; 2756 s64 nextbn, prevbn; 2757 struct tlock *tlck; 2758 struct dt_lock *dtlck; 2759 struct lv *lv; 2760 2761 nextbn = le64_to_cpu(p->header.next); 2762 prevbn = le64_to_cpu(p->header.prev); 2763 2764 /* update prev pointer of the next page */ 2765 if (nextbn != 0) { 2766 DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc); 2767 if (rc) 2768 return rc; 2769 2770 BT_MARK_DIRTY(mp, ip); 2771 /* 2772 * acquire a transaction lock on the next page 2773 * 2774 * action: update prev pointer; 2775 */ 2776 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK); 2777 jfs_info("dtRelink nextbn: tlck = 0x%p, ip = 0x%p, mp=0x%p", 2778 tlck, ip, mp); 2779 dtlck = (struct dt_lock *) & tlck->lock; 2780 2781 /* linelock header */ 2782 if (dtlck->index >= dtlck->maxcnt) 2783 dtlck = (struct dt_lock *) txLinelock(dtlck); 2784 lv = & dtlck->lv[dtlck->index]; 2785 lv->offset = 0; 2786 lv->length = 1; 2787 dtlck->index++; 2788 2789 p->header.prev = cpu_to_le64(prevbn); 2790 DT_PUTPAGE(mp); 2791 } 2792 2793 /* update next pointer of the previous page */ 2794 if (prevbn != 0) { 2795 DT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc); 2796 if (rc) 2797 return rc; 2798 2799 BT_MARK_DIRTY(mp, ip); 2800 /* 2801 * acquire a transaction lock on the prev page 2802 * 2803 * action: update next pointer; 2804 */ 2805 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK); 2806 jfs_info("dtRelink prevbn: tlck = 0x%p, ip = 0x%p, mp=0x%p", 2807 tlck, ip, mp); 2808 dtlck = (struct dt_lock *) & tlck->lock; 2809 2810 /* linelock header */ 2811 if (dtlck->index >= dtlck->maxcnt) 2812 dtlck = (struct dt_lock *) txLinelock(dtlck); 2813 lv = & dtlck->lv[dtlck->index]; 2814 lv->offset = 0; 2815 lv->length = 1; 2816 dtlck->index++; 2817 2818 p->header.next = cpu_to_le64(nextbn); 2819 DT_PUTPAGE(mp); 2820 } 2821 2822 return 0; 2823 } 2824 2825 2826 /* 2827 * dtInitRoot() 2828 * 2829 * initialize directory root (inline in inode) 2830 */ 2831 void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot) 2832 { 2833 struct jfs_inode_info *jfs_ip = JFS_IP(ip); 2834 dtroot_t *p; 2835 int fsi; 2836 struct dtslot *f; 2837 struct tlock *tlck; 2838 struct dt_lock *dtlck; 2839 struct lv *lv; 2840 u16 xflag_save; 2841 2842 /* 2843 * If this was previously an non-empty directory, we need to remove 2844 * the old directory table. 2845 */ 2846 if (DO_INDEX(ip)) { 2847 if (!jfs_dirtable_inline(ip)) { 2848 struct tblock *tblk = tid_to_tblock(tid); 2849 /* 2850 * We're playing games with the tid's xflag. If 2851 * we're removing a regular file, the file's xtree 2852 * is committed with COMMIT_PMAP, but we always 2853 * commit the directories xtree with COMMIT_PWMAP. 2854 */ 2855 xflag_save = tblk->xflag; 2856 tblk->xflag = 0; 2857 /* 2858 * xtTruncate isn't guaranteed to fully truncate 2859 * the xtree. The caller needs to check i_size 2860 * after committing the transaction to see if 2861 * additional truncation is needed. The 2862 * COMMIT_Stale flag tells caller that we 2863 * initiated the truncation. 2864 */ 2865 xtTruncate(tid, ip, 0, COMMIT_PWMAP); 2866 set_cflag(COMMIT_Stale, ip); 2867 2868 tblk->xflag = xflag_save; 2869 } else 2870 ip->i_size = 1; 2871 2872 jfs_ip->next_index = 2; 2873 } else 2874 ip->i_size = IDATASIZE; 2875 2876 /* 2877 * acquire a transaction lock on the root 2878 * 2879 * action: directory initialization; 2880 */ 2881 tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag, 2882 tlckDTREE | tlckENTRY | tlckBTROOT); 2883 dtlck = (struct dt_lock *) & tlck->lock; 2884 2885 /* linelock root */ 2886 ASSERT(dtlck->index == 0); 2887 lv = & dtlck->lv[0]; 2888 lv->offset = 0; 2889 lv->length = DTROOTMAXSLOT; 2890 dtlck->index++; 2891 2892 p = &jfs_ip->i_dtroot; 2893 2894 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; 2895 2896 p->header.nextindex = 0; 2897 2898 /* init freelist */ 2899 fsi = 1; 2900 f = &p->slot[fsi]; 2901 2902 /* init data area of root */ 2903 for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++) 2904 f->next = fsi; 2905 f->next = -1; 2906 2907 p->header.freelist = 1; 2908 p->header.freecnt = 8; 2909 2910 /* init '..' entry */ 2911 p->header.idotdot = cpu_to_le32(idotdot); 2912 2913 return; 2914 } 2915 2916 /* 2917 * add_missing_indices() 2918 * 2919 * function: Fix dtree page in which one or more entries has an invalid index. 2920 * fsck.jfs should really fix this, but it currently does not. 2921 * Called from jfs_readdir when bad index is detected. 2922 */ 2923 static void add_missing_indices(struct inode *inode, s64 bn) 2924 { 2925 struct ldtentry *d; 2926 struct dt_lock *dtlck; 2927 int i; 2928 uint index; 2929 struct lv *lv; 2930 struct metapage *mp; 2931 dtpage_t *p; 2932 int rc; 2933 s8 *stbl; 2934 tid_t tid; 2935 struct tlock *tlck; 2936 2937 tid = txBegin(inode->i_sb, 0); 2938 2939 DT_GETPAGE(inode, bn, mp, PSIZE, p, rc); 2940 2941 if (rc) { 2942 printk(KERN_ERR "DT_GETPAGE failed!\n"); 2943 goto end; 2944 } 2945 BT_MARK_DIRTY(mp, inode); 2946 2947 ASSERT(p->header.flag & BT_LEAF); 2948 2949 tlck = txLock(tid, inode, mp, tlckDTREE | tlckENTRY); 2950 if (BT_IS_ROOT(mp)) 2951 tlck->type |= tlckBTROOT; 2952 2953 dtlck = (struct dt_lock *) &tlck->lock; 2954 2955 stbl = DT_GETSTBL(p); 2956 for (i = 0; i < p->header.nextindex; i++) { 2957 d = (struct ldtentry *) &p->slot[stbl[i]]; 2958 index = le32_to_cpu(d->index); 2959 if ((index < 2) || (index >= JFS_IP(inode)->next_index)) { 2960 d->index = cpu_to_le32(add_index(tid, inode, bn, i)); 2961 if (dtlck->index >= dtlck->maxcnt) 2962 dtlck = (struct dt_lock *) txLinelock(dtlck); 2963 lv = &dtlck->lv[dtlck->index]; 2964 lv->offset = stbl[i]; 2965 lv->length = 1; 2966 dtlck->index++; 2967 } 2968 } 2969 2970 DT_PUTPAGE(mp); 2971 (void) txCommit(tid, 1, &inode, 0); 2972 end: 2973 txEnd(tid); 2974 } 2975 2976 /* 2977 * Buffer to hold directory entry info while traversing a dtree page 2978 * before being fed to the filldir function 2979 */ 2980 struct jfs_dirent { 2981 loff_t position; 2982 int ino; 2983 u16 name_len; 2984 char name[0]; 2985 }; 2986 2987 /* 2988 * function to determine next variable-sized jfs_dirent in buffer 2989 */ 2990 static inline struct jfs_dirent *next_jfs_dirent(struct jfs_dirent *dirent) 2991 { 2992 return (struct jfs_dirent *) 2993 ((char *)dirent + 2994 ((sizeof (struct jfs_dirent) + dirent->name_len + 1 + 2995 sizeof (loff_t) - 1) & 2996 ~(sizeof (loff_t) - 1))); 2997 } 2998 2999 /* 3000 * jfs_readdir() 3001 * 3002 * function: read directory entries sequentially 3003 * from the specified entry offset 3004 * 3005 * parameter: 3006 * 3007 * return: offset = (pn, index) of start entry 3008 * of next jfs_readdir()/dtRead() 3009 */ 3010 int jfs_readdir(struct file *filp, void *dirent, filldir_t filldir) 3011 { 3012 struct inode *ip = filp->f_path.dentry->d_inode; 3013 struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab; 3014 int rc = 0; 3015 loff_t dtpos; /* legacy OS/2 style position */ 3016 struct dtoffset { 3017 s16 pn; 3018 s16 index; 3019 s32 unused; 3020 } *dtoffset = (struct dtoffset *) &dtpos; 3021 s64 bn; 3022 struct metapage *mp; 3023 dtpage_t *p; 3024 int index; 3025 s8 *stbl; 3026 struct btstack btstack; 3027 int i, next; 3028 struct ldtentry *d; 3029 struct dtslot *t; 3030 int d_namleft, len, outlen; 3031 unsigned long dirent_buf; 3032 char *name_ptr; 3033 u32 dir_index; 3034 int do_index = 0; 3035 uint loop_count = 0; 3036 struct jfs_dirent *jfs_dirent; 3037 int jfs_dirents; 3038 int overflow, fix_page, page_fixed = 0; 3039 static int unique_pos = 2; /* If we can't fix broken index */ 3040 3041 if (filp->f_pos == DIREND) 3042 return 0; 3043 3044 if (DO_INDEX(ip)) { 3045 /* 3046 * persistent index is stored in directory entries. 3047 * Special cases: 0 = . 3048 * 1 = .. 3049 * -1 = End of directory 3050 */ 3051 do_index = 1; 3052 3053 dir_index = (u32) filp->f_pos; 3054 3055 if (dir_index > 1) { 3056 struct dir_table_slot dirtab_slot; 3057 3058 if (dtEmpty(ip) || 3059 (dir_index >= JFS_IP(ip)->next_index)) { 3060 /* Stale position. Directory has shrunk */ 3061 filp->f_pos = DIREND; 3062 return 0; 3063 } 3064 repeat: 3065 rc = read_index(ip, dir_index, &dirtab_slot); 3066 if (rc) { 3067 filp->f_pos = DIREND; 3068 return rc; 3069 } 3070 if (dirtab_slot.flag == DIR_INDEX_FREE) { 3071 if (loop_count++ > JFS_IP(ip)->next_index) { 3072 jfs_err("jfs_readdir detected " 3073 "infinite loop!"); 3074 filp->f_pos = DIREND; 3075 return 0; 3076 } 3077 dir_index = le32_to_cpu(dirtab_slot.addr2); 3078 if (dir_index == -1) { 3079 filp->f_pos = DIREND; 3080 return 0; 3081 } 3082 goto repeat; 3083 } 3084 bn = addressDTS(&dirtab_slot); 3085 index = dirtab_slot.slot; 3086 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3087 if (rc) { 3088 filp->f_pos = DIREND; 3089 return 0; 3090 } 3091 if (p->header.flag & BT_INTERNAL) { 3092 jfs_err("jfs_readdir: bad index table"); 3093 DT_PUTPAGE(mp); 3094 filp->f_pos = -1; 3095 return 0; 3096 } 3097 } else { 3098 if (dir_index == 0) { 3099 /* 3100 * self "." 3101 */ 3102 filp->f_pos = 0; 3103 if (filldir(dirent, ".", 1, 0, ip->i_ino, 3104 DT_DIR)) 3105 return 0; 3106 } 3107 /* 3108 * parent ".." 3109 */ 3110 filp->f_pos = 1; 3111 if (filldir(dirent, "..", 2, 1, PARENT(ip), DT_DIR)) 3112 return 0; 3113 3114 /* 3115 * Find first entry of left-most leaf 3116 */ 3117 if (dtEmpty(ip)) { 3118 filp->f_pos = DIREND; 3119 return 0; 3120 } 3121 3122 if ((rc = dtReadFirst(ip, &btstack))) 3123 return rc; 3124 3125 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 3126 } 3127 } else { 3128 /* 3129 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6 3130 * 3131 * pn = index = 0: First entry "." 3132 * pn = 0; index = 1: Second entry ".." 3133 * pn > 0: Real entries, pn=1 -> leftmost page 3134 * pn = index = -1: No more entries 3135 */ 3136 dtpos = filp->f_pos; 3137 if (dtpos == 0) { 3138 /* build "." entry */ 3139 3140 if (filldir(dirent, ".", 1, filp->f_pos, ip->i_ino, 3141 DT_DIR)) 3142 return 0; 3143 dtoffset->index = 1; 3144 filp->f_pos = dtpos; 3145 } 3146 3147 if (dtoffset->pn == 0) { 3148 if (dtoffset->index == 1) { 3149 /* build ".." entry */ 3150 3151 if (filldir(dirent, "..", 2, filp->f_pos, 3152 PARENT(ip), DT_DIR)) 3153 return 0; 3154 } else { 3155 jfs_err("jfs_readdir called with " 3156 "invalid offset!"); 3157 } 3158 dtoffset->pn = 1; 3159 dtoffset->index = 0; 3160 filp->f_pos = dtpos; 3161 } 3162 3163 if (dtEmpty(ip)) { 3164 filp->f_pos = DIREND; 3165 return 0; 3166 } 3167 3168 if ((rc = dtReadNext(ip, &filp->f_pos, &btstack))) { 3169 jfs_err("jfs_readdir: unexpected rc = %d " 3170 "from dtReadNext", rc); 3171 filp->f_pos = DIREND; 3172 return 0; 3173 } 3174 /* get start leaf page and index */ 3175 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 3176 3177 /* offset beyond directory eof ? */ 3178 if (bn < 0) { 3179 filp->f_pos = DIREND; 3180 return 0; 3181 } 3182 } 3183 3184 dirent_buf = __get_free_page(GFP_KERNEL); 3185 if (dirent_buf == 0) { 3186 DT_PUTPAGE(mp); 3187 jfs_warn("jfs_readdir: __get_free_page failed!"); 3188 filp->f_pos = DIREND; 3189 return -ENOMEM; 3190 } 3191 3192 while (1) { 3193 jfs_dirent = (struct jfs_dirent *) dirent_buf; 3194 jfs_dirents = 0; 3195 overflow = fix_page = 0; 3196 3197 stbl = DT_GETSTBL(p); 3198 3199 for (i = index; i < p->header.nextindex; i++) { 3200 d = (struct ldtentry *) & p->slot[stbl[i]]; 3201 3202 if (((long) jfs_dirent + d->namlen + 1) > 3203 (dirent_buf + PAGE_SIZE)) { 3204 /* DBCS codepages could overrun dirent_buf */ 3205 index = i; 3206 overflow = 1; 3207 break; 3208 } 3209 3210 d_namleft = d->namlen; 3211 name_ptr = jfs_dirent->name; 3212 jfs_dirent->ino = le32_to_cpu(d->inumber); 3213 3214 if (do_index) { 3215 len = min(d_namleft, DTLHDRDATALEN); 3216 jfs_dirent->position = le32_to_cpu(d->index); 3217 /* 3218 * d->index should always be valid, but it 3219 * isn't. fsck.jfs doesn't create the 3220 * directory index for the lost+found 3221 * directory. Rather than let it go, 3222 * we can try to fix it. 3223 */ 3224 if ((jfs_dirent->position < 2) || 3225 (jfs_dirent->position >= 3226 JFS_IP(ip)->next_index)) { 3227 if (!page_fixed && !isReadOnly(ip)) { 3228 fix_page = 1; 3229 /* 3230 * setting overflow and setting 3231 * index to i will cause the 3232 * same page to be processed 3233 * again starting here 3234 */ 3235 overflow = 1; 3236 index = i; 3237 break; 3238 } 3239 jfs_dirent->position = unique_pos++; 3240 } 3241 } else { 3242 jfs_dirent->position = dtpos; 3243 len = min(d_namleft, DTLHDRDATALEN_LEGACY); 3244 } 3245 3246 /* copy the name of head/only segment */ 3247 outlen = jfs_strfromUCS_le(name_ptr, d->name, len, 3248 codepage); 3249 jfs_dirent->name_len = outlen; 3250 3251 /* copy name in the additional segment(s) */ 3252 next = d->next; 3253 while (next >= 0) { 3254 t = (struct dtslot *) & p->slot[next]; 3255 name_ptr += outlen; 3256 d_namleft -= len; 3257 /* Sanity Check */ 3258 if (d_namleft == 0) { 3259 jfs_error(ip->i_sb, 3260 "JFS:Dtree error: ino = " 3261 "%ld, bn=%Ld, index = %d", 3262 (long)ip->i_ino, 3263 (long long)bn, 3264 i); 3265 goto skip_one; 3266 } 3267 len = min(d_namleft, DTSLOTDATALEN); 3268 outlen = jfs_strfromUCS_le(name_ptr, t->name, 3269 len, codepage); 3270 jfs_dirent->name_len += outlen; 3271 3272 next = t->next; 3273 } 3274 3275 jfs_dirents++; 3276 jfs_dirent = next_jfs_dirent(jfs_dirent); 3277 skip_one: 3278 if (!do_index) 3279 dtoffset->index++; 3280 } 3281 3282 if (!overflow) { 3283 /* Point to next leaf page */ 3284 if (p->header.flag & BT_ROOT) 3285 bn = 0; 3286 else { 3287 bn = le64_to_cpu(p->header.next); 3288 index = 0; 3289 /* update offset (pn:index) for new page */ 3290 if (!do_index) { 3291 dtoffset->pn++; 3292 dtoffset->index = 0; 3293 } 3294 } 3295 page_fixed = 0; 3296 } 3297 3298 /* unpin previous leaf page */ 3299 DT_PUTPAGE(mp); 3300 3301 jfs_dirent = (struct jfs_dirent *) dirent_buf; 3302 while (jfs_dirents--) { 3303 filp->f_pos = jfs_dirent->position; 3304 if (filldir(dirent, jfs_dirent->name, 3305 jfs_dirent->name_len, filp->f_pos, 3306 jfs_dirent->ino, DT_UNKNOWN)) 3307 goto out; 3308 jfs_dirent = next_jfs_dirent(jfs_dirent); 3309 } 3310 3311 if (fix_page) { 3312 add_missing_indices(ip, bn); 3313 page_fixed = 1; 3314 } 3315 3316 if (!overflow && (bn == 0)) { 3317 filp->f_pos = DIREND; 3318 break; 3319 } 3320 3321 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3322 if (rc) { 3323 free_page(dirent_buf); 3324 return rc; 3325 } 3326 } 3327 3328 out: 3329 free_page(dirent_buf); 3330 3331 return rc; 3332 } 3333 3334 3335 /* 3336 * dtReadFirst() 3337 * 3338 * function: get the leftmost page of the directory 3339 */ 3340 static int dtReadFirst(struct inode *ip, struct btstack * btstack) 3341 { 3342 int rc = 0; 3343 s64 bn; 3344 int psize = 288; /* initial in-line directory */ 3345 struct metapage *mp; 3346 dtpage_t *p; 3347 s8 *stbl; 3348 struct btframe *btsp; 3349 pxd_t *xd; 3350 3351 BT_CLR(btstack); /* reset stack */ 3352 3353 /* 3354 * descend leftmost path of the tree 3355 * 3356 * by convention, root bn = 0. 3357 */ 3358 for (bn = 0;;) { 3359 DT_GETPAGE(ip, bn, mp, psize, p, rc); 3360 if (rc) 3361 return rc; 3362 3363 /* 3364 * leftmost leaf page 3365 */ 3366 if (p->header.flag & BT_LEAF) { 3367 /* return leftmost entry */ 3368 btsp = btstack->top; 3369 btsp->bn = bn; 3370 btsp->index = 0; 3371 btsp->mp = mp; 3372 3373 return 0; 3374 } 3375 3376 /* 3377 * descend down to leftmost child page 3378 */ 3379 if (BT_STACK_FULL(btstack)) { 3380 DT_PUTPAGE(mp); 3381 jfs_error(ip->i_sb, "dtReadFirst: btstack overrun"); 3382 BT_STACK_DUMP(btstack); 3383 return -EIO; 3384 } 3385 /* push (bn, index) of the parent page/entry */ 3386 BT_PUSH(btstack, bn, 0); 3387 3388 /* get the leftmost entry */ 3389 stbl = DT_GETSTBL(p); 3390 xd = (pxd_t *) & p->slot[stbl[0]]; 3391 3392 /* get the child page block address */ 3393 bn = addressPXD(xd); 3394 psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize; 3395 3396 /* unpin the parent page */ 3397 DT_PUTPAGE(mp); 3398 } 3399 } 3400 3401 3402 /* 3403 * dtReadNext() 3404 * 3405 * function: get the page of the specified offset (pn:index) 3406 * 3407 * return: if (offset > eof), bn = -1; 3408 * 3409 * note: if index > nextindex of the target leaf page, 3410 * start with 1st entry of next leaf page; 3411 */ 3412 static int dtReadNext(struct inode *ip, loff_t * offset, 3413 struct btstack * btstack) 3414 { 3415 int rc = 0; 3416 struct dtoffset { 3417 s16 pn; 3418 s16 index; 3419 s32 unused; 3420 } *dtoffset = (struct dtoffset *) offset; 3421 s64 bn; 3422 struct metapage *mp; 3423 dtpage_t *p; 3424 int index; 3425 int pn; 3426 s8 *stbl; 3427 struct btframe *btsp, *parent; 3428 pxd_t *xd; 3429 3430 /* 3431 * get leftmost leaf page pinned 3432 */ 3433 if ((rc = dtReadFirst(ip, btstack))) 3434 return rc; 3435 3436 /* get leaf page */ 3437 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); 3438 3439 /* get the start offset (pn:index) */ 3440 pn = dtoffset->pn - 1; /* Now pn = 0 represents leftmost leaf */ 3441 index = dtoffset->index; 3442 3443 /* start at leftmost page ? */ 3444 if (pn == 0) { 3445 /* offset beyond eof ? */ 3446 if (index < p->header.nextindex) 3447 goto out; 3448 3449 if (p->header.flag & BT_ROOT) { 3450 bn = -1; 3451 goto out; 3452 } 3453 3454 /* start with 1st entry of next leaf page */ 3455 dtoffset->pn++; 3456 dtoffset->index = index = 0; 3457 goto a; 3458 } 3459 3460 /* start at non-leftmost page: scan parent pages for large pn */ 3461 if (p->header.flag & BT_ROOT) { 3462 bn = -1; 3463 goto out; 3464 } 3465 3466 /* start after next leaf page ? */ 3467 if (pn > 1) 3468 goto b; 3469 3470 /* get leaf page pn = 1 */ 3471 a: 3472 bn = le64_to_cpu(p->header.next); 3473 3474 /* unpin leaf page */ 3475 DT_PUTPAGE(mp); 3476 3477 /* offset beyond eof ? */ 3478 if (bn == 0) { 3479 bn = -1; 3480 goto out; 3481 } 3482 3483 goto c; 3484 3485 /* 3486 * scan last internal page level to get target leaf page 3487 */ 3488 b: 3489 /* unpin leftmost leaf page */ 3490 DT_PUTPAGE(mp); 3491 3492 /* get left most parent page */ 3493 btsp = btstack->top; 3494 parent = btsp - 1; 3495 bn = parent->bn; 3496 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3497 if (rc) 3498 return rc; 3499 3500 /* scan parent pages at last internal page level */ 3501 while (pn >= p->header.nextindex) { 3502 pn -= p->header.nextindex; 3503 3504 /* get next parent page address */ 3505 bn = le64_to_cpu(p->header.next); 3506 3507 /* unpin current parent page */ 3508 DT_PUTPAGE(mp); 3509 3510 /* offset beyond eof ? */ 3511 if (bn == 0) { 3512 bn = -1; 3513 goto out; 3514 } 3515 3516 /* get next parent page */ 3517 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3518 if (rc) 3519 return rc; 3520 3521 /* update parent page stack frame */ 3522 parent->bn = bn; 3523 } 3524 3525 /* get leaf page address */ 3526 stbl = DT_GETSTBL(p); 3527 xd = (pxd_t *) & p->slot[stbl[pn]]; 3528 bn = addressPXD(xd); 3529 3530 /* unpin parent page */ 3531 DT_PUTPAGE(mp); 3532 3533 /* 3534 * get target leaf page 3535 */ 3536 c: 3537 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3538 if (rc) 3539 return rc; 3540 3541 /* 3542 * leaf page has been completed: 3543 * start with 1st entry of next leaf page 3544 */ 3545 if (index >= p->header.nextindex) { 3546 bn = le64_to_cpu(p->header.next); 3547 3548 /* unpin leaf page */ 3549 DT_PUTPAGE(mp); 3550 3551 /* offset beyond eof ? */ 3552 if (bn == 0) { 3553 bn = -1; 3554 goto out; 3555 } 3556 3557 /* get next leaf page */ 3558 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc); 3559 if (rc) 3560 return rc; 3561 3562 /* start with 1st entry of next leaf page */ 3563 dtoffset->pn++; 3564 dtoffset->index = 0; 3565 } 3566 3567 out: 3568 /* return target leaf page pinned */ 3569 btsp = btstack->top; 3570 btsp->bn = bn; 3571 btsp->index = dtoffset->index; 3572 btsp->mp = mp; 3573 3574 return 0; 3575 } 3576 3577 3578 /* 3579 * dtCompare() 3580 * 3581 * function: compare search key with an internal entry 3582 * 3583 * return: 3584 * < 0 if k is < record 3585 * = 0 if k is = record 3586 * > 0 if k is > record 3587 */ 3588 static int dtCompare(struct component_name * key, /* search key */ 3589 dtpage_t * p, /* directory page */ 3590 int si) 3591 { /* entry slot index */ 3592 wchar_t *kname; 3593 __le16 *name; 3594 int klen, namlen, len, rc; 3595 struct idtentry *ih; 3596 struct dtslot *t; 3597 3598 /* 3599 * force the left-most key on internal pages, at any level of 3600 * the tree, to be less than any search key. 3601 * this obviates having to update the leftmost key on an internal 3602 * page when the user inserts a new key in the tree smaller than 3603 * anything that has been stored. 3604 * 3605 * (? if/when dtSearch() narrows down to 1st entry (index = 0), 3606 * at any internal page at any level of the tree, 3607 * it descends to child of the entry anyway - 3608 * ? make the entry as min size dummy entry) 3609 * 3610 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) 3611 * return (1); 3612 */ 3613 3614 kname = key->name; 3615 klen = key->namlen; 3616 3617 ih = (struct idtentry *) & p->slot[si]; 3618 si = ih->next; 3619 name = ih->name; 3620 namlen = ih->namlen; 3621 len = min(namlen, DTIHDRDATALEN); 3622 3623 /* compare with head/only segment */ 3624 len = min(klen, len); 3625 if ((rc = UniStrncmp_le(kname, name, len))) 3626 return rc; 3627 3628 klen -= len; 3629 namlen -= len; 3630 3631 /* compare with additional segment(s) */ 3632 kname += len; 3633 while (klen > 0 && namlen > 0) { 3634 /* compare with next name segment */ 3635 t = (struct dtslot *) & p->slot[si]; 3636 len = min(namlen, DTSLOTDATALEN); 3637 len = min(klen, len); 3638 name = t->name; 3639 if ((rc = UniStrncmp_le(kname, name, len))) 3640 return rc; 3641 3642 klen -= len; 3643 namlen -= len; 3644 kname += len; 3645 si = t->next; 3646 } 3647 3648 return (klen - namlen); 3649 } 3650 3651 3652 3653 3654 /* 3655 * ciCompare() 3656 * 3657 * function: compare search key with an (leaf/internal) entry 3658 * 3659 * return: 3660 * < 0 if k is < record 3661 * = 0 if k is = record 3662 * > 0 if k is > record 3663 */ 3664 static int ciCompare(struct component_name * key, /* search key */ 3665 dtpage_t * p, /* directory page */ 3666 int si, /* entry slot index */ 3667 int flag) 3668 { 3669 wchar_t *kname, x; 3670 __le16 *name; 3671 int klen, namlen, len, rc; 3672 struct ldtentry *lh; 3673 struct idtentry *ih; 3674 struct dtslot *t; 3675 int i; 3676 3677 /* 3678 * force the left-most key on internal pages, at any level of 3679 * the tree, to be less than any search key. 3680 * this obviates having to update the leftmost key on an internal 3681 * page when the user inserts a new key in the tree smaller than 3682 * anything that has been stored. 3683 * 3684 * (? if/when dtSearch() narrows down to 1st entry (index = 0), 3685 * at any internal page at any level of the tree, 3686 * it descends to child of the entry anyway - 3687 * ? make the entry as min size dummy entry) 3688 * 3689 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) 3690 * return (1); 3691 */ 3692 3693 kname = key->name; 3694 klen = key->namlen; 3695 3696 /* 3697 * leaf page entry 3698 */ 3699 if (p->header.flag & BT_LEAF) { 3700 lh = (struct ldtentry *) & p->slot[si]; 3701 si = lh->next; 3702 name = lh->name; 3703 namlen = lh->namlen; 3704 if (flag & JFS_DIR_INDEX) 3705 len = min(namlen, DTLHDRDATALEN); 3706 else 3707 len = min(namlen, DTLHDRDATALEN_LEGACY); 3708 } 3709 /* 3710 * internal page entry 3711 */ 3712 else { 3713 ih = (struct idtentry *) & p->slot[si]; 3714 si = ih->next; 3715 name = ih->name; 3716 namlen = ih->namlen; 3717 len = min(namlen, DTIHDRDATALEN); 3718 } 3719 3720 /* compare with head/only segment */ 3721 len = min(klen, len); 3722 for (i = 0; i < len; i++, kname++, name++) { 3723 /* only uppercase if case-insensitive support is on */ 3724 if ((flag & JFS_OS2) == JFS_OS2) 3725 x = UniToupper(le16_to_cpu(*name)); 3726 else 3727 x = le16_to_cpu(*name); 3728 if ((rc = *kname - x)) 3729 return rc; 3730 } 3731 3732 klen -= len; 3733 namlen -= len; 3734 3735 /* compare with additional segment(s) */ 3736 while (klen > 0 && namlen > 0) { 3737 /* compare with next name segment */ 3738 t = (struct dtslot *) & p->slot[si]; 3739 len = min(namlen, DTSLOTDATALEN); 3740 len = min(klen, len); 3741 name = t->name; 3742 for (i = 0; i < len; i++, kname++, name++) { 3743 /* only uppercase if case-insensitive support is on */ 3744 if ((flag & JFS_OS2) == JFS_OS2) 3745 x = UniToupper(le16_to_cpu(*name)); 3746 else 3747 x = le16_to_cpu(*name); 3748 3749 if ((rc = *kname - x)) 3750 return rc; 3751 } 3752 3753 klen -= len; 3754 namlen -= len; 3755 si = t->next; 3756 } 3757 3758 return (klen - namlen); 3759 } 3760 3761 3762 /* 3763 * ciGetLeafPrefixKey() 3764 * 3765 * function: compute prefix of suffix compression 3766 * from two adjacent leaf entries 3767 * across page boundary 3768 * 3769 * return: non-zero on error 3770 * 3771 */ 3772 static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp, 3773 int ri, struct component_name * key, int flag) 3774 { 3775 int klen, namlen; 3776 wchar_t *pl, *pr, *kname; 3777 struct component_name lkey; 3778 struct component_name rkey; 3779 3780 lkey.name = kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t), 3781 GFP_KERNEL); 3782 if (lkey.name == NULL) 3783 return -ENOMEM; 3784 3785 rkey.name = kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t), 3786 GFP_KERNEL); 3787 if (rkey.name == NULL) { 3788 kfree(lkey.name); 3789 return -ENOMEM; 3790 } 3791 3792 /* get left and right key */ 3793 dtGetKey(lp, li, &lkey, flag); 3794 lkey.name[lkey.namlen] = 0; 3795 3796 if ((flag & JFS_OS2) == JFS_OS2) 3797 ciToUpper(&lkey); 3798 3799 dtGetKey(rp, ri, &rkey, flag); 3800 rkey.name[rkey.namlen] = 0; 3801 3802 3803 if ((flag & JFS_OS2) == JFS_OS2) 3804 ciToUpper(&rkey); 3805 3806 /* compute prefix */ 3807 klen = 0; 3808 kname = key->name; 3809 namlen = min(lkey.namlen, rkey.namlen); 3810 for (pl = lkey.name, pr = rkey.name; 3811 namlen; pl++, pr++, namlen--, klen++, kname++) { 3812 *kname = *pr; 3813 if (*pl != *pr) { 3814 key->namlen = klen + 1; 3815 goto free_names; 3816 } 3817 } 3818 3819 /* l->namlen <= r->namlen since l <= r */ 3820 if (lkey.namlen < rkey.namlen) { 3821 *kname = *pr; 3822 key->namlen = klen + 1; 3823 } else /* l->namelen == r->namelen */ 3824 key->namlen = klen; 3825 3826 free_names: 3827 kfree(lkey.name); 3828 kfree(rkey.name); 3829 return 0; 3830 } 3831 3832 3833 3834 /* 3835 * dtGetKey() 3836 * 3837 * function: get key of the entry 3838 */ 3839 static void dtGetKey(dtpage_t * p, int i, /* entry index */ 3840 struct component_name * key, int flag) 3841 { 3842 int si; 3843 s8 *stbl; 3844 struct ldtentry *lh; 3845 struct idtentry *ih; 3846 struct dtslot *t; 3847 int namlen, len; 3848 wchar_t *kname; 3849 __le16 *name; 3850 3851 /* get entry */ 3852 stbl = DT_GETSTBL(p); 3853 si = stbl[i]; 3854 if (p->header.flag & BT_LEAF) { 3855 lh = (struct ldtentry *) & p->slot[si]; 3856 si = lh->next; 3857 namlen = lh->namlen; 3858 name = lh->name; 3859 if (flag & JFS_DIR_INDEX) 3860 len = min(namlen, DTLHDRDATALEN); 3861 else 3862 len = min(namlen, DTLHDRDATALEN_LEGACY); 3863 } else { 3864 ih = (struct idtentry *) & p->slot[si]; 3865 si = ih->next; 3866 namlen = ih->namlen; 3867 name = ih->name; 3868 len = min(namlen, DTIHDRDATALEN); 3869 } 3870 3871 key->namlen = namlen; 3872 kname = key->name; 3873 3874 /* 3875 * move head/only segment 3876 */ 3877 UniStrncpy_from_le(kname, name, len); 3878 3879 /* 3880 * move additional segment(s) 3881 */ 3882 while (si >= 0) { 3883 /* get next segment */ 3884 t = &p->slot[si]; 3885 kname += len; 3886 namlen -= len; 3887 len = min(namlen, DTSLOTDATALEN); 3888 UniStrncpy_from_le(kname, t->name, len); 3889 3890 si = t->next; 3891 } 3892 } 3893 3894 3895 /* 3896 * dtInsertEntry() 3897 * 3898 * function: allocate free slot(s) and 3899 * write a leaf/internal entry 3900 * 3901 * return: entry slot index 3902 */ 3903 static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key, 3904 ddata_t * data, struct dt_lock ** dtlock) 3905 { 3906 struct dtslot *h, *t; 3907 struct ldtentry *lh = NULL; 3908 struct idtentry *ih = NULL; 3909 int hsi, fsi, klen, len, nextindex; 3910 wchar_t *kname; 3911 __le16 *name; 3912 s8 *stbl; 3913 pxd_t *xd; 3914 struct dt_lock *dtlck = *dtlock; 3915 struct lv *lv; 3916 int xsi, n; 3917 s64 bn = 0; 3918 struct metapage *mp = NULL; 3919 3920 klen = key->namlen; 3921 kname = key->name; 3922 3923 /* allocate a free slot */ 3924 hsi = fsi = p->header.freelist; 3925 h = &p->slot[fsi]; 3926 p->header.freelist = h->next; 3927 --p->header.freecnt; 3928 3929 /* open new linelock */ 3930 if (dtlck->index >= dtlck->maxcnt) 3931 dtlck = (struct dt_lock *) txLinelock(dtlck); 3932 3933 lv = & dtlck->lv[dtlck->index]; 3934 lv->offset = hsi; 3935 3936 /* write head/only segment */ 3937 if (p->header.flag & BT_LEAF) { 3938 lh = (struct ldtentry *) h; 3939 lh->next = h->next; 3940 lh->inumber = cpu_to_le32(data->leaf.ino); 3941 lh->namlen = klen; 3942 name = lh->name; 3943 if (data->leaf.ip) { 3944 len = min(klen, DTLHDRDATALEN); 3945 if (!(p->header.flag & BT_ROOT)) 3946 bn = addressPXD(&p->header.self); 3947 lh->index = cpu_to_le32(add_index(data->leaf.tid, 3948 data->leaf.ip, 3949 bn, index)); 3950 } else 3951 len = min(klen, DTLHDRDATALEN_LEGACY); 3952 } else { 3953 ih = (struct idtentry *) h; 3954 ih->next = h->next; 3955 xd = (pxd_t *) ih; 3956 *xd = data->xd; 3957 ih->namlen = klen; 3958 name = ih->name; 3959 len = min(klen, DTIHDRDATALEN); 3960 } 3961 3962 UniStrncpy_to_le(name, kname, len); 3963 3964 n = 1; 3965 xsi = hsi; 3966 3967 /* write additional segment(s) */ 3968 t = h; 3969 klen -= len; 3970 while (klen) { 3971 /* get free slot */ 3972 fsi = p->header.freelist; 3973 t = &p->slot[fsi]; 3974 p->header.freelist = t->next; 3975 --p->header.freecnt; 3976 3977 /* is next slot contiguous ? */ 3978 if (fsi != xsi + 1) { 3979 /* close current linelock */ 3980 lv->length = n; 3981 dtlck->index++; 3982 3983 /* open new linelock */ 3984 if (dtlck->index < dtlck->maxcnt) 3985 lv++; 3986 else { 3987 dtlck = (struct dt_lock *) txLinelock(dtlck); 3988 lv = & dtlck->lv[0]; 3989 } 3990 3991 lv->offset = fsi; 3992 n = 0; 3993 } 3994 3995 kname += len; 3996 len = min(klen, DTSLOTDATALEN); 3997 UniStrncpy_to_le(t->name, kname, len); 3998 3999 n++; 4000 xsi = fsi; 4001 klen -= len; 4002 } 4003 4004 /* close current linelock */ 4005 lv->length = n; 4006 dtlck->index++; 4007 4008 *dtlock = dtlck; 4009 4010 /* terminate last/only segment */ 4011 if (h == t) { 4012 /* single segment entry */ 4013 if (p->header.flag & BT_LEAF) 4014 lh->next = -1; 4015 else 4016 ih->next = -1; 4017 } else 4018 /* multi-segment entry */ 4019 t->next = -1; 4020 4021 /* if insert into middle, shift right succeeding entries in stbl */ 4022 stbl = DT_GETSTBL(p); 4023 nextindex = p->header.nextindex; 4024 if (index < nextindex) { 4025 memmove(stbl + index + 1, stbl + index, nextindex - index); 4026 4027 if ((p->header.flag & BT_LEAF) && data->leaf.ip) { 4028 s64 lblock; 4029 4030 /* 4031 * Need to update slot number for entries that moved 4032 * in the stbl 4033 */ 4034 mp = NULL; 4035 for (n = index + 1; n <= nextindex; n++) { 4036 lh = (struct ldtentry *) & (p->slot[stbl[n]]); 4037 modify_index(data->leaf.tid, data->leaf.ip, 4038 le32_to_cpu(lh->index), bn, n, 4039 &mp, &lblock); 4040 } 4041 if (mp) 4042 release_metapage(mp); 4043 } 4044 } 4045 4046 stbl[index] = hsi; 4047 4048 /* advance next available entry index of stbl */ 4049 ++p->header.nextindex; 4050 } 4051 4052 4053 /* 4054 * dtMoveEntry() 4055 * 4056 * function: move entries from split/left page to new/right page 4057 * 4058 * nextindex of dst page and freelist/freecnt of both pages 4059 * are updated. 4060 */ 4061 static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp, 4062 struct dt_lock ** sdtlock, struct dt_lock ** ddtlock, 4063 int do_index) 4064 { 4065 int ssi, next; /* src slot index */ 4066 int di; /* dst entry index */ 4067 int dsi; /* dst slot index */ 4068 s8 *sstbl, *dstbl; /* sorted entry table */ 4069 int snamlen, len; 4070 struct ldtentry *slh, *dlh = NULL; 4071 struct idtentry *sih, *dih = NULL; 4072 struct dtslot *h, *s, *d; 4073 struct dt_lock *sdtlck = *sdtlock, *ddtlck = *ddtlock; 4074 struct lv *slv, *dlv; 4075 int xssi, ns, nd; 4076 int sfsi; 4077 4078 sstbl = (s8 *) & sp->slot[sp->header.stblindex]; 4079 dstbl = (s8 *) & dp->slot[dp->header.stblindex]; 4080 4081 dsi = dp->header.freelist; /* first (whole page) free slot */ 4082 sfsi = sp->header.freelist; 4083 4084 /* linelock destination entry slot */ 4085 dlv = & ddtlck->lv[ddtlck->index]; 4086 dlv->offset = dsi; 4087 4088 /* linelock source entry slot */ 4089 slv = & sdtlck->lv[sdtlck->index]; 4090 slv->offset = sstbl[si]; 4091 xssi = slv->offset - 1; 4092 4093 /* 4094 * move entries 4095 */ 4096 ns = nd = 0; 4097 for (di = 0; si < sp->header.nextindex; si++, di++) { 4098 ssi = sstbl[si]; 4099 dstbl[di] = dsi; 4100 4101 /* is next slot contiguous ? */ 4102 if (ssi != xssi + 1) { 4103 /* close current linelock */ 4104 slv->length = ns; 4105 sdtlck->index++; 4106 4107 /* open new linelock */ 4108 if (sdtlck->index < sdtlck->maxcnt) 4109 slv++; 4110 else { 4111 sdtlck = (struct dt_lock *) txLinelock(sdtlck); 4112 slv = & sdtlck->lv[0]; 4113 } 4114 4115 slv->offset = ssi; 4116 ns = 0; 4117 } 4118 4119 /* 4120 * move head/only segment of an entry 4121 */ 4122 /* get dst slot */ 4123 h = d = &dp->slot[dsi]; 4124 4125 /* get src slot and move */ 4126 s = &sp->slot[ssi]; 4127 if (sp->header.flag & BT_LEAF) { 4128 /* get source entry */ 4129 slh = (struct ldtentry *) s; 4130 dlh = (struct ldtentry *) h; 4131 snamlen = slh->namlen; 4132 4133 if (do_index) { 4134 len = min(snamlen, DTLHDRDATALEN); 4135 dlh->index = slh->index; /* little-endian */ 4136 } else 4137 len = min(snamlen, DTLHDRDATALEN_LEGACY); 4138 4139 memcpy(dlh, slh, 6 + len * 2); 4140 4141 next = slh->next; 4142 4143 /* update dst head/only segment next field */ 4144 dsi++; 4145 dlh->next = dsi; 4146 } else { 4147 sih = (struct idtentry *) s; 4148 snamlen = sih->namlen; 4149 4150 len = min(snamlen, DTIHDRDATALEN); 4151 dih = (struct idtentry *) h; 4152 memcpy(dih, sih, 10 + len * 2); 4153 next = sih->next; 4154 4155 dsi++; 4156 dih->next = dsi; 4157 } 4158 4159 /* free src head/only segment */ 4160 s->next = sfsi; 4161 s->cnt = 1; 4162 sfsi = ssi; 4163 4164 ns++; 4165 nd++; 4166 xssi = ssi; 4167 4168 /* 4169 * move additional segment(s) of the entry 4170 */ 4171 snamlen -= len; 4172 while ((ssi = next) >= 0) { 4173 /* is next slot contiguous ? */ 4174 if (ssi != xssi + 1) { 4175 /* close current linelock */ 4176 slv->length = ns; 4177 sdtlck->index++; 4178 4179 /* open new linelock */ 4180 if (sdtlck->index < sdtlck->maxcnt) 4181 slv++; 4182 else { 4183 sdtlck = 4184 (struct dt_lock *) 4185 txLinelock(sdtlck); 4186 slv = & sdtlck->lv[0]; 4187 } 4188 4189 slv->offset = ssi; 4190 ns = 0; 4191 } 4192 4193 /* get next source segment */ 4194 s = &sp->slot[ssi]; 4195 4196 /* get next destination free slot */ 4197 d++; 4198 4199 len = min(snamlen, DTSLOTDATALEN); 4200 UniStrncpy_le(d->name, s->name, len); 4201 4202 ns++; 4203 nd++; 4204 xssi = ssi; 4205 4206 dsi++; 4207 d->next = dsi; 4208 4209 /* free source segment */ 4210 next = s->next; 4211 s->next = sfsi; 4212 s->cnt = 1; 4213 sfsi = ssi; 4214 4215 snamlen -= len; 4216 } /* end while */ 4217 4218 /* terminate dst last/only segment */ 4219 if (h == d) { 4220 /* single segment entry */ 4221 if (dp->header.flag & BT_LEAF) 4222 dlh->next = -1; 4223 else 4224 dih->next = -1; 4225 } else 4226 /* multi-segment entry */ 4227 d->next = -1; 4228 } /* end for */ 4229 4230 /* close current linelock */ 4231 slv->length = ns; 4232 sdtlck->index++; 4233 *sdtlock = sdtlck; 4234 4235 dlv->length = nd; 4236 ddtlck->index++; 4237 *ddtlock = ddtlck; 4238 4239 /* update source header */ 4240 sp->header.freelist = sfsi; 4241 sp->header.freecnt += nd; 4242 4243 /* update destination header */ 4244 dp->header.nextindex = di; 4245 4246 dp->header.freelist = dsi; 4247 dp->header.freecnt -= nd; 4248 } 4249 4250 4251 /* 4252 * dtDeleteEntry() 4253 * 4254 * function: free a (leaf/internal) entry 4255 * 4256 * log freelist header, stbl, and each segment slot of entry 4257 * (even though last/only segment next field is modified, 4258 * physical image logging requires all segment slots of 4259 * the entry logged to avoid applying previous updates 4260 * to the same slots) 4261 */ 4262 static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock) 4263 { 4264 int fsi; /* free entry slot index */ 4265 s8 *stbl; 4266 struct dtslot *t; 4267 int si, freecnt; 4268 struct dt_lock *dtlck = *dtlock; 4269 struct lv *lv; 4270 int xsi, n; 4271 4272 /* get free entry slot index */ 4273 stbl = DT_GETSTBL(p); 4274 fsi = stbl[fi]; 4275 4276 /* open new linelock */ 4277 if (dtlck->index >= dtlck->maxcnt) 4278 dtlck = (struct dt_lock *) txLinelock(dtlck); 4279 lv = & dtlck->lv[dtlck->index]; 4280 4281 lv->offset = fsi; 4282 4283 /* get the head/only segment */ 4284 t = &p->slot[fsi]; 4285 if (p->header.flag & BT_LEAF) 4286 si = ((struct ldtentry *) t)->next; 4287 else 4288 si = ((struct idtentry *) t)->next; 4289 t->next = si; 4290 t->cnt = 1; 4291 4292 n = freecnt = 1; 4293 xsi = fsi; 4294 4295 /* find the last/only segment */ 4296 while (si >= 0) { 4297 /* is next slot contiguous ? */ 4298 if (si != xsi + 1) { 4299 /* close current linelock */ 4300 lv->length = n; 4301 dtlck->index++; 4302 4303 /* open new linelock */ 4304 if (dtlck->index < dtlck->maxcnt) 4305 lv++; 4306 else { 4307 dtlck = (struct dt_lock *) txLinelock(dtlck); 4308 lv = & dtlck->lv[0]; 4309 } 4310 4311 lv->offset = si; 4312 n = 0; 4313 } 4314 4315 n++; 4316 xsi = si; 4317 freecnt++; 4318 4319 t = &p->slot[si]; 4320 t->cnt = 1; 4321 si = t->next; 4322 } 4323 4324 /* close current linelock */ 4325 lv->length = n; 4326 dtlck->index++; 4327 4328 *dtlock = dtlck; 4329 4330 /* update freelist */ 4331 t->next = p->header.freelist; 4332 p->header.freelist = fsi; 4333 p->header.freecnt += freecnt; 4334 4335 /* if delete from middle, 4336 * shift left the succedding entries in the stbl 4337 */ 4338 si = p->header.nextindex; 4339 if (fi < si - 1) 4340 memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1); 4341 4342 p->header.nextindex--; 4343 } 4344 4345 4346 /* 4347 * dtTruncateEntry() 4348 * 4349 * function: truncate a (leaf/internal) entry 4350 * 4351 * log freelist header, stbl, and each segment slot of entry 4352 * (even though last/only segment next field is modified, 4353 * physical image logging requires all segment slots of 4354 * the entry logged to avoid applying previous updates 4355 * to the same slots) 4356 */ 4357 static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock) 4358 { 4359 int tsi; /* truncate entry slot index */ 4360 s8 *stbl; 4361 struct dtslot *t; 4362 int si, freecnt; 4363 struct dt_lock *dtlck = *dtlock; 4364 struct lv *lv; 4365 int fsi, xsi, n; 4366 4367 /* get free entry slot index */ 4368 stbl = DT_GETSTBL(p); 4369 tsi = stbl[ti]; 4370 4371 /* open new linelock */ 4372 if (dtlck->index >= dtlck->maxcnt) 4373 dtlck = (struct dt_lock *) txLinelock(dtlck); 4374 lv = & dtlck->lv[dtlck->index]; 4375 4376 lv->offset = tsi; 4377 4378 /* get the head/only segment */ 4379 t = &p->slot[tsi]; 4380 ASSERT(p->header.flag & BT_INTERNAL); 4381 ((struct idtentry *) t)->namlen = 0; 4382 si = ((struct idtentry *) t)->next; 4383 ((struct idtentry *) t)->next = -1; 4384 4385 n = 1; 4386 freecnt = 0; 4387 fsi = si; 4388 xsi = tsi; 4389 4390 /* find the last/only segment */ 4391 while (si >= 0) { 4392 /* is next slot contiguous ? */ 4393 if (si != xsi + 1) { 4394 /* close current linelock */ 4395 lv->length = n; 4396 dtlck->index++; 4397 4398 /* open new linelock */ 4399 if (dtlck->index < dtlck->maxcnt) 4400 lv++; 4401 else { 4402 dtlck = (struct dt_lock *) txLinelock(dtlck); 4403 lv = & dtlck->lv[0]; 4404 } 4405 4406 lv->offset = si; 4407 n = 0; 4408 } 4409 4410 n++; 4411 xsi = si; 4412 freecnt++; 4413 4414 t = &p->slot[si]; 4415 t->cnt = 1; 4416 si = t->next; 4417 } 4418 4419 /* close current linelock */ 4420 lv->length = n; 4421 dtlck->index++; 4422 4423 *dtlock = dtlck; 4424 4425 /* update freelist */ 4426 if (freecnt == 0) 4427 return; 4428 t->next = p->header.freelist; 4429 p->header.freelist = fsi; 4430 p->header.freecnt += freecnt; 4431 } 4432 4433 4434 /* 4435 * dtLinelockFreelist() 4436 */ 4437 static void dtLinelockFreelist(dtpage_t * p, /* directory page */ 4438 int m, /* max slot index */ 4439 struct dt_lock ** dtlock) 4440 { 4441 int fsi; /* free entry slot index */ 4442 struct dtslot *t; 4443 int si; 4444 struct dt_lock *dtlck = *dtlock; 4445 struct lv *lv; 4446 int xsi, n; 4447 4448 /* get free entry slot index */ 4449 fsi = p->header.freelist; 4450 4451 /* open new linelock */ 4452 if (dtlck->index >= dtlck->maxcnt) 4453 dtlck = (struct dt_lock *) txLinelock(dtlck); 4454 lv = & dtlck->lv[dtlck->index]; 4455 4456 lv->offset = fsi; 4457 4458 n = 1; 4459 xsi = fsi; 4460 4461 t = &p->slot[fsi]; 4462 si = t->next; 4463 4464 /* find the last/only segment */ 4465 while (si < m && si >= 0) { 4466 /* is next slot contiguous ? */ 4467 if (si != xsi + 1) { 4468 /* close current linelock */ 4469 lv->length = n; 4470 dtlck->index++; 4471 4472 /* open new linelock */ 4473 if (dtlck->index < dtlck->maxcnt) 4474 lv++; 4475 else { 4476 dtlck = (struct dt_lock *) txLinelock(dtlck); 4477 lv = & dtlck->lv[0]; 4478 } 4479 4480 lv->offset = si; 4481 n = 0; 4482 } 4483 4484 n++; 4485 xsi = si; 4486 4487 t = &p->slot[si]; 4488 si = t->next; 4489 } 4490 4491 /* close current linelock */ 4492 lv->length = n; 4493 dtlck->index++; 4494 4495 *dtlock = dtlck; 4496 } 4497 4498 4499 /* 4500 * NAME: dtModify 4501 * 4502 * FUNCTION: Modify the inode number part of a directory entry 4503 * 4504 * PARAMETERS: 4505 * tid - Transaction id 4506 * ip - Inode of parent directory 4507 * key - Name of entry to be modified 4508 * orig_ino - Original inode number expected in entry 4509 * new_ino - New inode number to put into entry 4510 * flag - JFS_RENAME 4511 * 4512 * RETURNS: 4513 * -ESTALE - If entry found does not match orig_ino passed in 4514 * -ENOENT - If no entry can be found to match key 4515 * 0 - If successfully modified entry 4516 */ 4517 int dtModify(tid_t tid, struct inode *ip, 4518 struct component_name * key, ino_t * orig_ino, ino_t new_ino, int flag) 4519 { 4520 int rc; 4521 s64 bn; 4522 struct metapage *mp; 4523 dtpage_t *p; 4524 int index; 4525 struct btstack btstack; 4526 struct tlock *tlck; 4527 struct dt_lock *dtlck; 4528 struct lv *lv; 4529 s8 *stbl; 4530 int entry_si; /* entry slot index */ 4531 struct ldtentry *entry; 4532 4533 /* 4534 * search for the entry to modify: 4535 * 4536 * dtSearch() returns (leaf page pinned, index at which to modify). 4537 */ 4538 if ((rc = dtSearch(ip, key, orig_ino, &btstack, flag))) 4539 return rc; 4540 4541 /* retrieve search result */ 4542 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 4543 4544 BT_MARK_DIRTY(mp, ip); 4545 /* 4546 * acquire a transaction lock on the leaf page of named entry 4547 */ 4548 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY); 4549 dtlck = (struct dt_lock *) & tlck->lock; 4550 4551 /* get slot index of the entry */ 4552 stbl = DT_GETSTBL(p); 4553 entry_si = stbl[index]; 4554 4555 /* linelock entry */ 4556 ASSERT(dtlck->index == 0); 4557 lv = & dtlck->lv[0]; 4558 lv->offset = entry_si; 4559 lv->length = 1; 4560 dtlck->index++; 4561 4562 /* get the head/only segment */ 4563 entry = (struct ldtentry *) & p->slot[entry_si]; 4564 4565 /* substitute the inode number of the entry */ 4566 entry->inumber = cpu_to_le32(new_ino); 4567 4568 /* unpin the leaf page */ 4569 DT_PUTPAGE(mp); 4570 4571 return 0; 4572 } 4573