fs/jfs/jfs_dtree.c

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