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