fs/jfs/jfs_dtree.c

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