Lines Matching +full:xlen +full:- +full:1
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) International Business Machines Corp., 2000-2004
7 * jfs_dtree.c: directory B+-tree manager
9 * B+-tree with variable length key directory:
11 * each directory page is structured as an array of 32-byte
28 * directory starts as a root/leaf page in on-disk inode
31 * of length of 1 block. each time the first leaf becomes full,
41 * case-insensitive directory file system
43 * names are stored in case-sensitive way in leaf entry.
44 * but stored, searched and compared in case-insensitive (uppercase) order
46 * (note that case-sensitive order is BROKEN in storage, e.g.,
47 * sensitive: Ad, aB, aC, aD -> insensitive: aB, aC, aD, Ad
55 * either for, in case-insensitive search, duplicate
56 * or for, in case-sensitive search, for exact match
58 * router entry must be created/stored in case-insensitive way
66 * case-insensitive search:
70 * case-insensitive search of B-tree:
74 * if (leaf entry case-insensitive match found)
75 * if (next entry satisfies case-insensitive match)
77 * if (prev entry satisfies case-insensitive match)
118 if (((P)->header.nextindex > \
119 (((BN) == 0) ? DTROOTMAXSLOT : (P)->header.maxslot)) || \
120 ((BN) && (((P)->header.maxslot > DTPAGEMAXSLOT) || \
121 ((P)->header.stblindex >= DTPAGEMAXSLOT)))) { \
123 jfs_error((IP)->i_sb, \
126 RC = -EIO; \
186 #define ciToUpper(c) UniStrupr((c)->name)
201 s32 xlen; in read_index_page() local
203 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); in read_index_page()
207 return read_metapage(inode, xaddr, PSIZE, 1); in read_index_page()
220 s32 xlen; in get_index_page() local
222 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); in get_index_page()
226 return get_metapage(inode, xaddr, PSIZE, 1); in get_index_page()
250 maxWarnings--; in find_index()
255 if (index >= jfs_ip->next_index) { in find_index()
265 slot = &jfs_ip->i_dirtable[index - 2]; in find_index()
267 offset = (index - 2) * sizeof(struct dir_table_slot); in find_index()
268 page_offset = offset & (PSIZE - 1); in find_index()
269 blkno = ((offset + 1) >> L2PSIZE) << in find_index()
270 JFS_SBI(ip->i_sb)->l2nbperpage; in find_index()
286 (struct dir_table_slot *) ((char *) (*mp)->data + in find_index()
300 llck = (struct linelock *) tlck->lock; in lock_index()
302 if (llck->index >= llck->maxcnt) in lock_index()
304 lv = &llck->lv[llck->index]; in lock_index()
310 lv->offset = ((index - 2) & 511) >> 1; in lock_index()
311 lv->length = 1; in lock_index()
312 llck->index++; in lock_index()
324 struct super_block *sb = ip->i_sb; in add_index()
340 if (jfs_ip->next_index < 2) { in add_index()
342 jfs_ip->next_index); in add_index()
343 jfs_ip->next_index = 2; in add_index()
346 index = jfs_ip->next_index++; in add_index()
352 ip->i_size = (loff_t) (index - 1) << 3; in add_index()
357 dirtab_slot = &jfs_ip->i_dirtable[index-2]; in add_index()
358 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
359 dirtab_slot->slot = slot; in add_index()
366 if (index == (MAX_INLINE_DIRTABLE_ENTRY + 1)) { in add_index()
373 if (dquot_alloc_block(ip, sbi->nbperpage)) in add_index()
375 if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) { in add_index()
376 dquot_free_block(ip, sbi->nbperpage); in add_index()
384 memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table)); in add_index()
387 * Initialize empty x-tree in add_index()
394 if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) { in add_index()
397 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
399 dbFree(ip, xaddr, sbi->nbperpage); in add_index()
400 dquot_free_block(ip, sbi->nbperpage); in add_index()
403 ip->i_size = PSIZE; in add_index()
409 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
414 llck = (struct linelock *) & tlck->lock; in add_index()
415 ASSERT(llck->index == 0); in add_index()
416 lv = &llck->lv[0]; in add_index()
418 lv->offset = 0; in add_index()
419 lv->length = 6; /* tlckDATA slot size is 16 bytes */ in add_index()
420 llck->index++; in add_index()
422 memcpy(mp->data, temp_table, sizeof(temp_table)); in add_index()
433 offset = (index - 2) * sizeof(struct dir_table_slot); in add_index()
434 page_offset = offset & (PSIZE - 1); in add_index()
435 blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage; in add_index()
441 if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) { in add_index()
445 ip->i_size += PSIZE; in add_index()
448 memset(mp->data, 0, PSIZE); /* Just looks better */ in add_index()
462 (struct dir_table_slot *) ((char *) mp->data + page_offset); in add_index()
463 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
464 dirtab_slot->slot = slot; in add_index()
474 jfs_ip->next_index--; in add_index()
495 dirtab_slot->flag = DIR_INDEX_FREE; in free_index()
496 dirtab_slot->slot = dirtab_slot->addr1 = 0; in free_index()
497 dirtab_slot->addr2 = cpu_to_le32(next); in free_index()
523 dirtab_slot->slot = slot; in modify_index()
546 return -EIO; in read_index()
565 * return: 0 - search result on stack, leaf page pinned;
566 * errno - I/O error
572 int cmp = 1; /* init for empty page */ in dtSearch()
580 int psize = 288; /* initial in-line directory */ in dtSearch()
583 struct super_block *sb = ip->i_sb; in dtSearch()
585 ciKey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t), in dtSearch()
588 rc = -ENOMEM; in dtSearch()
593 /* uppercase search key for c-i directory */ in dtSearch()
594 UniStrcpy(ciKey.name, key->name); in dtSearch()
595 ciKey.namlen = key->namlen; in dtSearch()
597 /* only uppercase if case-insensitive support is on */ in dtSearch()
598 if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) { in dtSearch()
604 btstack->nsplit = 1; in dtSearch()
634 for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) { in dtSearch()
635 index = base + (lim >> 1); in dtSearch()
638 rc = -EIO; in dtSearch()
642 if (p->header.flag & BT_LEAF) { in dtSearch()
646 JFS_SBI(sb)->mntflag); in dtSearch()
658 /* search hit - leaf page: in dtSearch()
661 if (p->header.flag & BT_LEAF) { in dtSearch()
663 ((struct ldtentry *) & p->slot[stbl[index]])->inumber); in dtSearch()
679 rc = -EEXIST; in dtSearch()
689 rc = -ESTALE; in dtSearch()
698 btsp = btstack->top; in dtSearch()
699 btsp->bn = bn; in dtSearch()
700 btsp->index = index; in dtSearch()
701 btsp->mp = mp; in dtSearch()
707 /* search hit - internal page: in dtSearch()
714 base = index + 1; in dtSearch()
715 --lim; in dtSearch()
723 * search key (K) and may be zero or (maxindex + 1) index. in dtSearch()
726 * search miss - leaf page in dtSearch()
731 if (p->header.flag & BT_LEAF) { in dtSearch()
737 rc = -ENOENT; in dtSearch()
747 btsp = btstack->top; in dtSearch()
748 btsp->bn = bn; in dtSearch()
749 btsp->index = base; in dtSearch()
750 btsp->mp = mp; in dtSearch()
757 * search miss - internal page in dtSearch()
759 * if base is non-zero, decrement base by one to get the parent in dtSearch()
762 index = base ? base - 1 : base; in dtSearch()
775 rc = -EIO; in dtSearch()
778 btstack->nsplit++; in dtSearch()
784 pxd = (pxd_t *) & p->slot[stbl[index]]; in dtSearch()
786 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; in dtSearch()
812 * return: 0 - success;
813 * errno - failure;
819 struct metapage *mp; /* meta-page buffer */ in dtInsert()
820 dtpage_t *p; /* base B+-tree index page */ in dtInsert()
834 * n.b. dtSearch() may return index of (maxindex + 1) of in dtInsert()
837 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtInsert()
838 if (p->header.freelist == 0) in dtInsert()
839 return -EINVAL; in dtInsert()
845 if (JFS_IP(ip)->next_index == DIREND) { in dtInsert()
847 return -EMLINK; in dtInsert()
849 n = NDTLEAF(name->namlen); in dtInsert()
853 n = NDTLEAF_LEGACY(name->namlen); in dtInsert()
865 if (n > p->header.freecnt) { in dtInsert()
885 dtlck = (struct dt_lock *) & tlck->lock; in dtInsert()
886 ASSERT(dtlck->index == 0); in dtInsert()
887 lv = & dtlck->lv[0]; in dtInsert()
890 lv->offset = 0; in dtInsert()
891 lv->length = 1; in dtInsert()
892 dtlck->index++; in dtInsert()
896 /* linelock stbl of non-root leaf page */ in dtInsert()
897 if (!(p->header.flag & BT_ROOT)) { in dtInsert()
898 if (dtlck->index >= dtlck->maxcnt) in dtInsert()
900 lv = & dtlck->lv[dtlck->index]; in dtInsert()
902 lv->offset = p->header.stblindex + n; in dtInsert()
903 lv->length = in dtInsert()
904 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtInsert()
905 dtlck->index++; in dtInsert()
922 * return: 0 - success;
923 * errno - failure;
929 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dtSplitUp()
941 int xlen, xsize; in dtSplitUp() local
945 ddata_t *data = split->data; in dtSplitUp()
953 smp = split->mp; in dtSplitUp()
959 rc = -ENOMEM; in dtSplitUp()
972 if (sp->header.flag & BT_ROOT) { in dtSplitUp()
976 xlen = 1; in dtSplitUp()
977 n = sbi->bsize >> L2DTSLOTSIZE; in dtSplitUp()
978 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
979 n -= DTROOTMAXSLOT - sp->header.freecnt; /* header + entries */ in dtSplitUp()
980 if (n <= split->nslot) in dtSplitUp()
981 xlen++; in dtSplitUp()
982 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr))) { in dtSplitUp()
987 pxdlist.maxnpxd = 1; in dtSplitUp()
991 PXDlength(pxd, xlen); in dtSplitUp()
992 split->pxdlist = &pxdlist; in dtSplitUp()
996 dbFree(ip, xaddr, xlen); in dtSplitUp()
1003 ip->i_size = xlen << sbi->l2bsize; in dtSplitUp()
1011 * extend the 1st extent if less than buffer page size in dtSplitUp()
1014 pxd = &sp->header.self; in dtSplitUp()
1015 xlen = lengthPXD(pxd); in dtSplitUp()
1016 xsize = xlen << sbi->l2bsize; in dtSplitUp()
1020 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
1021 if ((n + sp->header.freecnt) <= split->nslot) in dtSplitUp()
1022 n = xlen + (xlen << 1); in dtSplitUp()
1024 n = xlen; in dtSplitUp()
1032 if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen, in dtSplitUp()
1036 pxdlist.maxnpxd = 1; in dtSplitUp()
1040 PXDlength(pxd, xlen + n); in dtSplitUp()
1041 split->pxdlist = &pxdlist; in dtSplitUp()
1046 xlen = lengthPXD(pxd); in dtSplitUp()
1047 dbFree(ip, nxaddr, (s64) xlen); in dtSplitUp()
1050 xlen = lengthPXD(pxd) - n; in dtSplitUp()
1051 xaddr = addressPXD(pxd) + xlen; in dtSplitUp()
1055 ip->i_size = lengthPXD(pxd) << sbi->l2bsize; in dtSplitUp()
1074 n = btstack->nsplit; in dtSplitUp()
1076 xlen = sbi->nbperpage; in dtSplitUp()
1077 for (pxd = pxdlist.pxd; n > 0; n--, pxd++) { in dtSplitUp()
1078 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr)) == 0) { in dtSplitUp()
1080 PXDlength(pxd, xlen); in dtSplitUp()
1091 split->pxdlist = &pxdlist; in dtSplitUp()
1100 ip->i_size += PSIZE; in dtSplitUp()
1134 DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); in dtSplitUp()
1145 skip = parent->index + 1; in dtSplitUp()
1168 * the entire key must be retained for the next-to-leftmost in dtSplitUp()
1172 switch (rp->header.flag & BT_TYPE) { in dtSplitUp()
1179 if ((sp->header.flag & BT_ROOT && skip > 1) || in dtSplitUp()
1180 sp->header.prev != 0 || skip > 1) { in dtSplitUp()
1183 lp->header.nextindex-1, in dtSplitUp()
1185 sbi->mntflag); in dtSplitUp()
1197 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1200 if ((sbi->mntflag & JFS_OS2) == JFS_OS2) in dtSplitUp()
1208 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1223 data->xd = rpxd; /* child page xd */ in dtSplitUp()
1226 * parent page is full - split the parent page in dtSplitUp()
1228 if (n > sp->header.freecnt) { in dtSplitUp()
1230 split->mp = smp; in dtSplitUp()
1231 split->index = skip; /* index at insert */ in dtSplitUp()
1232 split->nslot = n; in dtSplitUp()
1233 split->key = &key; in dtSplitUp()
1234 /* split->data = data; */ in dtSplitUp()
1243 rc = (sp->header.flag & BT_ROOT) ? in dtSplitUp()
1254 * parent page is not full - insert router entry in parent page in dtSplitUp()
1262 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitUp()
1263 ASSERT(dtlck->index == 0); in dtSplitUp()
1264 lv = & dtlck->lv[0]; in dtSplitUp()
1267 lv->offset = 0; in dtSplitUp()
1268 lv->length = 1; in dtSplitUp()
1269 dtlck->index++; in dtSplitUp()
1271 /* linelock stbl of non-root parent page */ in dtSplitUp()
1272 if (!(sp->header.flag & BT_ROOT)) { in dtSplitUp()
1275 lv->offset = sp->header.stblindex + n; in dtSplitUp()
1276 lv->length = in dtSplitUp()
1277 ((sp->header.nextindex - in dtSplitUp()
1278 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitUp()
1279 dtlck->index++; in dtSplitUp()
1318 * function: Split a non-root page of a btree.
1322 * return: 0 - success;
1323 * errno - failure;
1353 smp = split->mp; in dtSplitPage()
1359 pxdlist = split->pxdlist; in dtSplitPage()
1360 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitPage()
1361 pxdlist->npxd++; in dtSplitPage()
1363 rmp = get_metapage(ip, rbn, PSIZE, 1); in dtSplitPage()
1365 return -EIO; in dtSplitPage()
1381 rdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1383 rp = (dtpage_t *) rmp->data; in dtSplitPage()
1385 rp->header.self = *pxd; in dtSplitPage()
1394 sdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1397 ASSERT(sdtlck->index == 0); in dtSplitPage()
1398 slv = & sdtlck->lv[0]; in dtSplitPage()
1399 slv->offset = 0; in dtSplitPage()
1400 slv->length = 1; in dtSplitPage()
1401 sdtlck->index++; in dtSplitPage()
1406 nextbn = le64_to_cpu(sp->header.next); in dtSplitPage()
1407 rp->header.next = cpu_to_le64(nextbn); in dtSplitPage()
1408 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); in dtSplitPage()
1409 sp->header.next = cpu_to_le64(rbn); in dtSplitPage()
1414 rp->header.flag = sp->header.flag; in dtSplitPage()
1417 rp->header.nextindex = 0; in dtSplitPage()
1418 rp->header.stblindex = 1; in dtSplitPage()
1421 rp->header.maxslot = n; in dtSplitPage()
1425 fsi = rp->header.stblindex + stblsize; in dtSplitPage()
1426 rp->header.freelist = fsi; in dtSplitPage()
1427 rp->header.freecnt = rp->header.maxslot - fsi; in dtSplitPage()
1442 if (nextbn == 0 && split->index == sp->header.nextindex) { in dtSplitPage()
1444 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1445 rlv->offset = 0; in dtSplitPage()
1446 rlv->length = 2; in dtSplitPage()
1447 rdtlck->index++; in dtSplitPage()
1452 f = &rp->slot[fsi]; in dtSplitPage()
1453 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1454 f->next = fsi; in dtSplitPage()
1455 f->next = -1; in dtSplitPage()
1458 dtInsertEntry(rp, 0, split->key, split->data, &rdtlck); in dtSplitPage()
1464 * non-sequential insert (at possibly middle page) in dtSplitPage()
1484 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1487 lv = & dtlck->lv[dtlck->index]; in dtSplitPage()
1488 lv->offset = 0; in dtSplitPage()
1489 lv->length = 1; in dtSplitPage()
1490 dtlck->index++; in dtSplitPage()
1492 p->header.prev = cpu_to_le64(rbn); in dtSplitPage()
1500 skip = split->index; in dtSplitPage()
1501 half = (PSIZE >> L2DTSLOTSIZE) >> 1; /* swag */ in dtSplitPage()
1510 stbl = (u8 *) & sp->slot[sp->header.stblindex]; in dtSplitPage()
1511 nextindex = sp->header.nextindex; in dtSplitPage()
1515 n = split->nslot; in dtSplitPage()
1518 switch (sp->header.flag & BT_TYPE) { in dtSplitPage()
1520 ldtentry = (struct ldtentry *) & sp->slot[si]; in dtSplitPage()
1522 n = NDTLEAF(ldtentry->namlen); in dtSplitPage()
1524 n = NDTLEAF_LEGACY(ldtentry-> in dtSplitPage()
1529 idtentry = (struct idtentry *) & sp->slot[si]; in dtSplitPage()
1530 n = NDTINTERNAL(idtentry->namlen); in dtSplitPage()
1545 /* <nxt> poins to the 1st entry to move */ in dtSplitPage()
1556 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1557 rlv->offset = 0; in dtSplitPage()
1558 rlv->length = 5; in dtSplitPage()
1559 rdtlck->index++; in dtSplitPage()
1563 sp->header.nextindex = nxt; in dtSplitPage()
1568 fsi = rp->header.freelist; in dtSplitPage()
1569 f = &rp->slot[fsi]; in dtSplitPage()
1570 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1571 f->next = fsi; in dtSplitPage()
1572 f->next = -1; in dtSplitPage()
1577 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitPage()
1582 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitPage()
1583 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitPage()
1584 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitPage()
1596 dtInsertEntry(sp, skip, split->key, split->data, &sdtlck); in dtSplitPage()
1599 if (sdtlck->index >= sdtlck->maxcnt) in dtSplitPage()
1601 slv = & sdtlck->lv[sdtlck->index]; in dtSplitPage()
1603 slv->offset = sp->header.stblindex + n; in dtSplitPage()
1604 slv->length = in dtSplitPage()
1605 ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitPage()
1606 sdtlck->index++; in dtSplitPage()
1613 skip -= nxt; in dtSplitPage()
1616 dtInsertEntry(rp, skip, split->key, split->data, &rdtlck); in dtSplitPage()
1630 * function: extend 1st/only directory leaf page
1634 * return: 0 - success;
1635 * errno - failure;
1641 struct super_block *sb = ip->i_sb; in dtExtendPage()
1647 int xlen, xsize; in dtExtendPage() local
1664 smp = split->mp; in dtExtendPage()
1669 DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc); in dtExtendPage()
1676 pxdlist = split->pxdlist; in dtExtendPage()
1677 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtExtendPage()
1678 pxdlist->npxd++; in dtExtendPage()
1681 tpxd = &sp->header.self; in dtExtendPage()
1683 /* in-place extension */ in dtExtendPage()
1693 pxdlock = (struct pxd_lock *) & tlck->lock; in dtExtendPage()
1694 pxdlock->flag = mlckFREEPXD; in dtExtendPage()
1695 pxdlock->pxd = sp->header.self; in dtExtendPage()
1696 pxdlock->index = 1; in dtExtendPage()
1706 for (n = 0; n < sp->header.nextindex; n++) { in dtExtendPage()
1708 (struct ldtentry *) & sp->slot[stbl[n]]; in dtExtendPage()
1710 le32_to_cpu(ldtentry->index), in dtExtendPage()
1721 sp->header.self = *pxd; in dtExtendPage()
1730 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1731 lv = & dtlck->lv[0]; in dtExtendPage()
1734 xlen = lengthPXD(pxd); in dtExtendPage()
1735 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtExtendPage()
1740 oldstblindex = sp->header.stblindex; in dtExtendPage()
1741 oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE; in dtExtendPage()
1742 newstblindex = sp->header.maxslot; in dtExtendPage()
1745 memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex], in dtExtendPage()
1746 sp->header.nextindex); in dtExtendPage()
1749 * in-line extension: linelock old area of extended page in dtExtendPage()
1753 lv->offset = 0; in dtExtendPage()
1754 lv->length = 1; in dtExtendPage()
1755 dtlck->index++; in dtExtendPage()
1759 lv->offset = newstblindex; in dtExtendPage()
1760 lv->length = newstblsize; in dtExtendPage()
1766 lv->offset = 0; in dtExtendPage()
1767 lv->length = sp->header.maxslot + newstblsize; in dtExtendPage()
1770 dtlck->index++; in dtExtendPage()
1772 sp->header.maxslot = n; in dtExtendPage()
1773 sp->header.stblindex = newstblindex; in dtExtendPage()
1774 /* sp->header.nextindex remains the same */ in dtExtendPage()
1780 f = &sp->slot[fsi]; in dtExtendPage()
1781 last = sp->header.freelist; in dtExtendPage()
1783 f->next = last; in dtExtendPage()
1786 sp->header.freelist = last; in dtExtendPage()
1787 sp->header.freecnt += oldstblsize; in dtExtendPage()
1794 f = &sp->slot[fsi]; in dtExtendPage()
1795 for (fsi++; fsi < sp->header.maxslot; f++, fsi++) in dtExtendPage()
1796 f->next = fsi; in dtExtendPage()
1797 f->next = -1; in dtExtendPage()
1800 fsi = sp->header.freelist; in dtExtendPage()
1801 if (fsi == -1) in dtExtendPage()
1802 sp->header.freelist = n; in dtExtendPage()
1805 f = &sp->slot[fsi]; in dtExtendPage()
1806 fsi = f->next; in dtExtendPage()
1807 } while (fsi != -1); in dtExtendPage()
1809 f->next = n; in dtExtendPage()
1812 sp->header.freecnt += sp->header.maxslot - n; in dtExtendPage()
1817 dtInsertEntry(sp, split->index, split->key, split->data, &dtlck); in dtExtendPage()
1824 n = sp->header.maxslot >> 2; in dtExtendPage()
1825 if (sp->header.freelist < n) in dtExtendPage()
1836 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1837 lv = & dtlck->lv[dtlck->index]; in dtExtendPage()
1839 /* linelock parent entry - 1st slot */ in dtExtendPage()
1840 lv->offset = 1; in dtExtendPage()
1841 lv->length = 1; in dtExtendPage()
1842 dtlck->index++; in dtExtendPage()
1845 tpxd = (pxd_t *) & pp->slot[1]; in dtExtendPage()
1861 * since root page << non-root page, and
1867 * return: 0 - success;
1868 * errno - failure;
1874 struct super_block *sb = ip->i_sb; in dtSplitRoot()
1880 int xlen; in dtSplitRoot() local
1895 smp = split->mp; in dtSplitRoot()
1896 sp = &JFS_IP(ip)->i_dtroot; in dtSplitRoot()
1904 pxdlist = split->pxdlist; in dtSplitRoot()
1905 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitRoot()
1906 pxdlist->npxd++; in dtSplitRoot()
1908 xlen = lengthPXD(pxd); in dtSplitRoot()
1909 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtSplitRoot()
1910 rmp = get_metapage(ip, rbn, xsize, 1); in dtSplitRoot()
1912 return -EIO; in dtSplitRoot()
1914 rp = rmp->data; in dtSplitRoot()
1928 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
1930 rp->header.flag = in dtSplitRoot()
1931 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; in dtSplitRoot()
1932 rp->header.self = *pxd; in dtSplitRoot()
1935 rp->header.next = 0; in dtSplitRoot()
1936 rp->header.prev = 0; in dtSplitRoot()
1939 * move in-line root page into new right page extent in dtSplitRoot()
1941 /* linelock header + copied entries + new stbl (1st slot) in new page */ in dtSplitRoot()
1942 ASSERT(dtlck->index == 0); in dtSplitRoot()
1943 lv = & dtlck->lv[0]; in dtSplitRoot()
1944 lv->offset = 0; in dtSplitRoot()
1945 lv->length = 10; /* 1 + 8 + 1 */ in dtSplitRoot()
1946 dtlck->index++; in dtSplitRoot()
1949 rp->header.maxslot = n; in dtSplitRoot()
1953 rp->header.stblindex = DTROOTMAXSLOT; in dtSplitRoot()
1954 stbl = (s8 *) & rp->slot[DTROOTMAXSLOT]; in dtSplitRoot()
1955 memcpy(stbl, sp->header.stbl, sp->header.nextindex); in dtSplitRoot()
1956 rp->header.nextindex = sp->header.nextindex; in dtSplitRoot()
1959 memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE); in dtSplitRoot()
1966 f = &rp->slot[fsi]; in dtSplitRoot()
1967 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitRoot()
1968 f->next = fsi; in dtSplitRoot()
1969 f->next = -1; in dtSplitRoot()
1972 fsi = sp->header.freelist; in dtSplitRoot()
1973 if (fsi == -1) in dtSplitRoot()
1974 rp->header.freelist = n; in dtSplitRoot()
1976 rp->header.freelist = fsi; in dtSplitRoot()
1979 f = &rp->slot[fsi]; in dtSplitRoot()
1980 fsi = f->next; in dtSplitRoot()
1983 f->next = n; in dtSplitRoot()
1986 rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n; in dtSplitRoot()
1991 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitRoot()
1997 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitRoot()
1998 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitRoot()
1999 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitRoot()
2009 dtInsertEntry(rp, split->index, split->key, split->data, &dtlck); in dtSplitRoot()
2014 * set the 1st entry offset to 0, which force the left-most key in dtSplitRoot()
2017 * The btree comparison code guarantees that the left-most key on any in dtSplitRoot()
2022 * acquire a transaction lock on the root page (in-memory inode) in dtSplitRoot()
2025 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
2028 ASSERT(dtlck->index == 0); in dtSplitRoot()
2029 lv = & dtlck->lv[0]; in dtSplitRoot()
2030 lv->offset = 0; in dtSplitRoot()
2031 lv->length = DTROOTMAXSLOT; in dtSplitRoot()
2032 dtlck->index++; in dtSplitRoot()
2035 if (sp->header.flag & BT_LEAF) { in dtSplitRoot()
2036 sp->header.flag &= ~BT_LEAF; in dtSplitRoot()
2037 sp->header.flag |= BT_INTERNAL; in dtSplitRoot()
2041 s = (struct idtentry *) & sp->slot[DTENTRYSTART]; in dtSplitRoot()
2044 s->next = -1; in dtSplitRoot()
2045 s->namlen = 0; in dtSplitRoot()
2047 stbl = sp->header.stbl; in dtSplitRoot()
2049 sp->header.nextindex = 1; in dtSplitRoot()
2052 fsi = DTENTRYSTART + 1; in dtSplitRoot()
2053 f = &sp->slot[fsi]; in dtSplitRoot()
2057 f->next = fsi; in dtSplitRoot()
2058 f->next = -1; in dtSplitRoot()
2060 sp->header.freelist = DTENTRYSTART + 1; in dtSplitRoot()
2061 sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1); in dtSplitRoot()
2115 ldtentry = (struct ldtentry *) & p->slot[stbl[index]]; in dtDelete()
2116 table_index = le32_to_cpu(ldtentry->index); in dtDelete()
2117 if (index == (p->header.nextindex - 1)) { in dtDelete()
2121 if ((p->header.flag & BT_ROOT) in dtDelete()
2122 || (p->header.next == 0)) in dtDelete()
2123 next_index = -1; in dtDelete()
2126 DT_GETPAGE(ip, le64_to_cpu(p->header.next), in dtDelete()
2129 next_index = -1; in dtDelete()
2133 (struct ldtentry *) & np-> in dtDelete()
2136 le32_to_cpu(ldtentry->index); in dtDelete()
2142 (struct ldtentry *) & p->slot[stbl[index + 1]]; in dtDelete()
2143 next_index = le32_to_cpu(ldtentry->index); in dtDelete()
2150 if (p->header.nextindex == 1) { in dtDelete()
2165 dtlck = (struct dt_lock *) & tlck->lock; in dtDelete()
2168 * Do not assume that dtlck->index will be zero. During a in dtDelete()
2174 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2176 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2177 lv->offset = 0; in dtDelete()
2178 lv->length = 1; in dtDelete()
2179 dtlck->index++; in dtDelete()
2181 /* linelock stbl of non-root leaf page */ in dtDelete()
2182 if (!(p->header.flag & BT_ROOT)) { in dtDelete()
2183 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2185 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2187 lv->offset = p->header.stblindex + i; in dtDelete()
2188 lv->length = in dtDelete()
2189 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDelete()
2190 i + 1; in dtDelete()
2191 dtlck->index++; in dtDelete()
2200 if (DO_INDEX(ip) && index < p->header.nextindex) { in dtDelete()
2205 for (i = index; i < p->header.nextindex; i++) { in dtDelete()
2207 (struct ldtentry *) & p->slot[stbl[i]]; in dtDelete()
2209 le32_to_cpu(ldtentry->index), in dtDelete()
2240 int xlen; in dtDeleteUp() local
2265 * free the non-root leaf page in dtDeleteUp()
2275 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2276 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2277 pxdlock->pxd = fp->header.self; in dtDeleteUp()
2278 pxdlock->index = 1; in dtDeleteUp()
2286 xlen = lengthPXD(&fp->header.self); in dtDeleteUp()
2289 dquot_free_block(ip, xlen); in dtDeleteUp()
2304 DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); in dtDeleteUp()
2311 index = parent->index; in dtDeleteUp()
2316 nextindex = p->header.nextindex; in dtDeleteUp()
2323 if (nextindex == 1) { in dtDeleteUp()
2327 if (p->header.flag & BT_ROOT) { in dtDeleteUp()
2351 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2352 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2353 pxdlock->pxd = p->header.self; in dtDeleteUp()
2354 pxdlock->index = 1; in dtDeleteUp()
2362 xlen = lengthPXD(&p->header.self); in dtDeleteUp()
2365 dquot_free_block(ip, xlen); in dtDeleteUp()
2387 dtlck = (struct dt_lock *) & tlck->lock; in dtDeleteUp()
2390 if (dtlck->index >= dtlck->maxcnt) in dtDeleteUp()
2392 lv = & dtlck->lv[dtlck->index]; in dtDeleteUp()
2393 lv->offset = 0; in dtDeleteUp()
2394 lv->length = 1; in dtDeleteUp()
2395 dtlck->index++; in dtDeleteUp()
2397 /* linelock stbl of non-root leaf page */ in dtDeleteUp()
2398 if (!(p->header.flag & BT_ROOT)) { in dtDeleteUp()
2399 if (dtlck->index < dtlck->maxcnt) in dtDeleteUp()
2403 lv = & dtlck->lv[0]; in dtDeleteUp()
2406 lv->offset = p->header.stblindex + i; in dtDeleteUp()
2407 lv->length = in dtDeleteUp()
2408 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDeleteUp()
2409 i + 1; in dtDeleteUp()
2410 dtlck->index++; in dtDeleteUp()
2418 ((p->header.flag & BT_ROOT) || p->header.prev == 0)) in dtDeleteUp()
2429 ip->i_size -= PSIZE; in dtDeleteUp()
2454 nextbn = le64_to_cpu(p->header.next); in dtRelink()
2455 prevbn = le64_to_cpu(p->header.prev); in dtRelink()
2472 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2475 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2477 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2478 lv->offset = 0; in dtRelink()
2479 lv->length = 1; in dtRelink()
2480 dtlck->index++; in dtRelink()
2482 p->header.prev = cpu_to_le64(prevbn); in dtRelink()
2501 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2504 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2506 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2507 lv->offset = 0; in dtRelink()
2508 lv->length = 1; in dtRelink()
2509 dtlck->index++; in dtRelink()
2511 p->header.next = cpu_to_le64(nextbn); in dtRelink()
2536 * If this was previously an non-empty directory, we need to remove in dtInitRoot()
2548 xflag_save = tblk->xflag; in dtInitRoot()
2549 tblk->xflag = 0; in dtInitRoot()
2561 tblk->xflag = xflag_save; in dtInitRoot()
2563 ip->i_size = 1; in dtInitRoot()
2565 jfs_ip->next_index = 2; in dtInitRoot()
2567 ip->i_size = IDATASIZE; in dtInitRoot()
2574 tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag, in dtInitRoot()
2576 dtlck = (struct dt_lock *) & tlck->lock; in dtInitRoot()
2579 ASSERT(dtlck->index == 0); in dtInitRoot()
2580 lv = & dtlck->lv[0]; in dtInitRoot()
2581 lv->offset = 0; in dtInitRoot()
2582 lv->length = DTROOTMAXSLOT; in dtInitRoot()
2583 dtlck->index++; in dtInitRoot()
2585 p = &jfs_ip->i_dtroot; in dtInitRoot()
2587 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; in dtInitRoot()
2589 p->header.nextindex = 0; in dtInitRoot()
2592 fsi = 1; in dtInitRoot()
2593 f = &p->slot[fsi]; in dtInitRoot()
2597 f->next = fsi; in dtInitRoot()
2598 f->next = -1; in dtInitRoot()
2600 p->header.freelist = 1; in dtInitRoot()
2601 p->header.freecnt = 8; in dtInitRoot()
2604 p->header.idotdot = cpu_to_le32(idotdot); in dtInitRoot()
2630 tid = txBegin(inode->i_sb, 0); in add_missing_indices()
2640 ASSERT(p->header.flag & BT_LEAF); in add_missing_indices()
2644 tlck->type |= tlckBTROOT; in add_missing_indices()
2646 dtlck = (struct dt_lock *) &tlck->lock; in add_missing_indices()
2649 for (i = 0; i < p->header.nextindex; i++) { in add_missing_indices()
2652 i, stbl[i], (long)inode->i_ino, (long long)bn); in add_missing_indices()
2653 rc = -EIO; in add_missing_indices()
2660 d = (struct ldtentry *) &p->slot[stbl[i]]; in add_missing_indices()
2661 index = le32_to_cpu(d->index); in add_missing_indices()
2662 if ((index < 2) || (index >= JFS_IP(inode)->next_index)) { in add_missing_indices()
2663 d->index = cpu_to_le32(add_index(tid, inode, bn, i)); in add_missing_indices()
2664 if (dtlck->index >= dtlck->maxcnt) in add_missing_indices()
2666 lv = &dtlck->lv[dtlck->index]; in add_missing_indices()
2667 lv->offset = stbl[i]; in add_missing_indices()
2668 lv->length = 1; in add_missing_indices()
2669 dtlck->index++; in add_missing_indices()
2674 (void) txCommit(tid, 1, &inode, 0); in add_missing_indices()
2692 * function to determine next variable-sized jfs_dirent in buffer
2698 ((sizeof (struct jfs_dirent) + dirent->name_len + 1 + in next_jfs_dirent()
2699 sizeof (loff_t) - 1) & in next_jfs_dirent()
2700 ~(sizeof (loff_t) - 1))); in next_jfs_dirent()
2717 struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab; in jfs_readdir()
2745 if (ctx->pos == DIREND) in jfs_readdir()
2752 * 1 = .. in jfs_readdir()
2753 * -1 = End of directory in jfs_readdir()
2755 do_index = 1; in jfs_readdir()
2757 dir_index = (u32) ctx->pos; in jfs_readdir()
2760 * NFSv4 reserves cookies 1 and 2 for . and .. so the value in jfs_readdir()
2765 dir_index--; in jfs_readdir()
2767 if (dir_index > 1) { in jfs_readdir()
2771 (dir_index >= JFS_IP(ip)->next_index)) { in jfs_readdir()
2773 ctx->pos = DIREND; in jfs_readdir()
2779 ctx->pos = DIREND; in jfs_readdir()
2783 if (loop_count++ > JFS_IP(ip)->next_index) { in jfs_readdir()
2785 ctx->pos = DIREND; in jfs_readdir()
2789 if (dir_index == -1) { in jfs_readdir()
2790 ctx->pos = DIREND; in jfs_readdir()
2799 ctx->pos = DIREND; in jfs_readdir()
2802 if (p->header.flag & BT_INTERNAL) { in jfs_readdir()
2805 ctx->pos = DIREND; in jfs_readdir()
2813 ctx->pos = 1; in jfs_readdir()
2814 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
2820 ctx->pos = 2; in jfs_readdir()
2825 * Find first entry of left-most leaf in jfs_readdir()
2828 ctx->pos = DIREND; in jfs_readdir()
2839 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6 in jfs_readdir()
2841 * pn = 0; index = 1: First entry "." in jfs_readdir()
2843 * pn > 0: Real entries, pn=1 -> leftmost page in jfs_readdir()
2844 * pn = index = -1: No more entries in jfs_readdir()
2846 dtpos = ctx->pos; in jfs_readdir()
2849 ctx->pos = 1; in jfs_readdir()
2850 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
2852 dtoffset->index = 2; in jfs_readdir()
2853 ctx->pos = dtpos; in jfs_readdir()
2856 if (dtoffset->pn == 0) { in jfs_readdir()
2857 if (dtoffset->index == 2) { in jfs_readdir()
2864 dtoffset->pn = 1; in jfs_readdir()
2865 dtoffset->index = 0; in jfs_readdir()
2866 ctx->pos = dtpos; in jfs_readdir()
2870 ctx->pos = DIREND; in jfs_readdir()
2874 if ((rc = dtReadNext(ip, &ctx->pos, &btstack))) { in jfs_readdir()
2877 ctx->pos = DIREND; in jfs_readdir()
2885 ctx->pos = DIREND; in jfs_readdir()
2894 ctx->pos = DIREND; in jfs_readdir()
2895 return -ENOMEM; in jfs_readdir()
2898 while (1) { in jfs_readdir()
2905 for (i = index; i < p->header.nextindex; i++) { in jfs_readdir()
2908 i, stbl[i], (long)ip->i_ino, (long long)bn); in jfs_readdir()
2911 return -EIO; in jfs_readdir()
2914 d = (struct ldtentry *) & p->slot[stbl[i]]; in jfs_readdir()
2916 if (((long) jfs_dirent + d->namlen + 1) > in jfs_readdir()
2920 overflow = 1; in jfs_readdir()
2924 d_namleft = d->namlen; in jfs_readdir()
2925 name_ptr = jfs_dirent->name; in jfs_readdir()
2926 jfs_dirent->ino = le32_to_cpu(d->inumber); in jfs_readdir()
2930 jfs_dirent->position = le32_to_cpu(d->index); in jfs_readdir()
2932 * d->index should always be valid, but it in jfs_readdir()
2938 if ((jfs_dirent->position < 2) || in jfs_readdir()
2939 (jfs_dirent->position >= in jfs_readdir()
2940 JFS_IP(ip)->next_index)) { in jfs_readdir()
2942 fix_page = 1; in jfs_readdir()
2949 overflow = 1; in jfs_readdir()
2953 jfs_dirent->position = unique_pos++; in jfs_readdir()
2956 * We add 1 to the index because we may in jfs_readdir()
2960 jfs_dirent->position++; in jfs_readdir()
2962 jfs_dirent->position = dtpos; in jfs_readdir()
2967 outlen = jfs_strfromUCS_le(name_ptr, d->name, len, in jfs_readdir()
2969 jfs_dirent->name_len = outlen; in jfs_readdir()
2972 next = d->next; in jfs_readdir()
2974 t = (struct dtslot *) & p->slot[next]; in jfs_readdir()
2976 d_namleft -= len; in jfs_readdir()
2979 jfs_error(ip->i_sb, in jfs_readdir()
2981 (long)ip->i_ino, in jfs_readdir()
2987 outlen = jfs_strfromUCS_le(name_ptr, t->name, in jfs_readdir()
2989 jfs_dirent->name_len += outlen; in jfs_readdir()
2991 next = t->next; in jfs_readdir()
2998 dtoffset->index++; in jfs_readdir()
3003 if (p->header.flag & BT_ROOT) in jfs_readdir()
3006 bn = le64_to_cpu(p->header.next); in jfs_readdir()
3010 dtoffset->pn++; in jfs_readdir()
3011 dtoffset->index = 0; in jfs_readdir()
3021 while (jfs_dirents--) { in jfs_readdir()
3022 ctx->pos = jfs_dirent->position; in jfs_readdir()
3023 if (!dir_emit(ctx, jfs_dirent->name, in jfs_readdir()
3024 jfs_dirent->name_len, in jfs_readdir()
3025 jfs_dirent->ino, DT_UNKNOWN)) in jfs_readdir()
3033 page_fixed = 1; in jfs_readdir()
3037 ctx->pos = DIREND; in jfs_readdir()
3064 int psize = 288; /* initial in-line directory */ in dtReadFirst()
3086 if (p->header.flag & BT_LEAF) { in dtReadFirst()
3088 btsp = btstack->top; in dtReadFirst()
3089 btsp->bn = bn; in dtReadFirst()
3090 btsp->index = 0; in dtReadFirst()
3091 btsp->mp = mp; in dtReadFirst()
3101 jfs_error(ip->i_sb, "btstack overrun\n"); in dtReadFirst()
3103 return -EIO; in dtReadFirst()
3113 jfs_error(ip->i_sb, "stbl[0] out of bound\n"); in dtReadFirst()
3114 return -EIO; in dtReadFirst()
3117 xd = (pxd_t *) & p->slot[stbl[0]]; in dtReadFirst()
3121 psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize; in dtReadFirst()
3134 * return: if (offset > eof), bn = -1;
3137 * start with 1st entry of next leaf page;
3164 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtReadNext()
3167 pn = dtoffset->pn - 1; /* Now pn = 0 represents leftmost leaf */ in dtReadNext()
3168 index = dtoffset->index; in dtReadNext()
3173 if (index < p->header.nextindex) in dtReadNext()
3176 if (p->header.flag & BT_ROOT) { in dtReadNext()
3177 bn = -1; in dtReadNext()
3181 /* start with 1st entry of next leaf page */ in dtReadNext()
3182 dtoffset->pn++; in dtReadNext()
3183 dtoffset->index = index = 0; in dtReadNext()
3187 /* start at non-leftmost page: scan parent pages for large pn */ in dtReadNext()
3188 if (p->header.flag & BT_ROOT) { in dtReadNext()
3189 bn = -1; in dtReadNext()
3194 if (pn > 1) in dtReadNext()
3197 /* get leaf page pn = 1 */ in dtReadNext()
3199 bn = le64_to_cpu(p->header.next); in dtReadNext()
3206 bn = -1; in dtReadNext()
3220 btsp = btstack->top; in dtReadNext()
3221 parent = btsp - 1; in dtReadNext()
3222 bn = parent->bn; in dtReadNext()
3228 while (pn >= p->header.nextindex) { in dtReadNext()
3229 pn -= p->header.nextindex; in dtReadNext()
3232 bn = le64_to_cpu(p->header.next); in dtReadNext()
3239 bn = -1; in dtReadNext()
3249 parent->bn = bn; in dtReadNext()
3254 xd = (pxd_t *) & p->slot[stbl[pn]]; in dtReadNext()
3270 * start with 1st entry of next leaf page in dtReadNext()
3272 if (index >= p->header.nextindex) { in dtReadNext()
3273 bn = le64_to_cpu(p->header.next); in dtReadNext()
3280 bn = -1; in dtReadNext()
3289 /* start with 1st entry of next leaf page */ in dtReadNext()
3290 dtoffset->pn++; in dtReadNext()
3291 dtoffset->index = 0; in dtReadNext()
3296 btsp = btstack->top; in dtReadNext()
3297 btsp->bn = bn; in dtReadNext()
3298 btsp->index = dtoffset->index; in dtReadNext()
3299 btsp->mp = mp; in dtReadNext()
3326 * force the left-most key on internal pages, at any level of in dtCompare()
3332 * (? if/when dtSearch() narrows down to 1st entry (index = 0), in dtCompare()
3334 * it descends to child of the entry anyway - in dtCompare()
3337 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in dtCompare()
3338 * return (1); in dtCompare()
3341 kname = key->name; in dtCompare()
3342 klen = key->namlen; in dtCompare()
3344 ih = (struct idtentry *) & p->slot[si]; in dtCompare()
3345 si = ih->next; in dtCompare()
3346 name = ih->name; in dtCompare()
3347 namlen = ih->namlen; in dtCompare()
3355 klen -= len; in dtCompare()
3356 namlen -= len; in dtCompare()
3362 t = (struct dtslot *) & p->slot[si]; in dtCompare()
3365 name = t->name; in dtCompare()
3369 klen -= len; in dtCompare()
3370 namlen -= len; in dtCompare()
3372 si = t->next; in dtCompare()
3375 return (klen - namlen); in dtCompare()
3405 * force the left-most key on internal pages, at any level of in ciCompare()
3411 * (? if/when dtSearch() narrows down to 1st entry (index = 0), in ciCompare()
3413 * it descends to child of the entry anyway - in ciCompare()
3416 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in ciCompare()
3417 * return (1); in ciCompare()
3420 kname = key->name; in ciCompare()
3421 klen = key->namlen; in ciCompare()
3426 if (p->header.flag & BT_LEAF) { in ciCompare()
3427 lh = (struct ldtentry *) & p->slot[si]; in ciCompare()
3428 si = lh->next; in ciCompare()
3429 name = lh->name; in ciCompare()
3430 namlen = lh->namlen; in ciCompare()
3440 ih = (struct idtentry *) & p->slot[si]; in ciCompare()
3441 si = ih->next; in ciCompare()
3442 name = ih->name; in ciCompare()
3443 namlen = ih->namlen; in ciCompare()
3450 /* only uppercase if case-insensitive support is on */ in ciCompare()
3455 if ((rc = *kname - x)) in ciCompare()
3459 klen -= len; in ciCompare()
3460 namlen -= len; in ciCompare()
3465 t = (struct dtslot *) & p->slot[si]; in ciCompare()
3468 name = t->name; in ciCompare()
3470 /* only uppercase if case-insensitive support is on */ in ciCompare()
3476 if ((rc = *kname - x)) in ciCompare()
3480 klen -= len; in ciCompare()
3481 namlen -= len; in ciCompare()
3482 si = t->next; in ciCompare()
3485 return (klen - namlen); in ciCompare()
3496 * return: non-zero on error
3507 lkey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t), in ciGetLeafPrefixKey()
3510 return -ENOMEM; in ciGetLeafPrefixKey()
3512 rkey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t), in ciGetLeafPrefixKey()
3516 return -ENOMEM; in ciGetLeafPrefixKey()
3535 kname = key->name; in ciGetLeafPrefixKey()
3538 namlen; pl++, pr++, namlen--, klen++, kname++) { in ciGetLeafPrefixKey()
3541 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3546 /* l->namlen <= r->namlen since l <= r */ in ciGetLeafPrefixKey()
3549 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3550 } else /* l->namelen == r->namelen */ in ciGetLeafPrefixKey()
3551 key->namlen = klen; in ciGetLeafPrefixKey()
3581 if (p->header.flag & BT_LEAF) { in dtGetKey()
3582 lh = (struct ldtentry *) & p->slot[si]; in dtGetKey()
3583 si = lh->next; in dtGetKey()
3584 namlen = lh->namlen; in dtGetKey()
3585 name = lh->name; in dtGetKey()
3591 ih = (struct idtentry *) & p->slot[si]; in dtGetKey()
3592 si = ih->next; in dtGetKey()
3593 namlen = ih->namlen; in dtGetKey()
3594 name = ih->name; in dtGetKey()
3598 key->namlen = namlen; in dtGetKey()
3599 kname = key->name; in dtGetKey()
3611 t = &p->slot[si]; in dtGetKey()
3613 namlen -= len; in dtGetKey()
3615 UniStrncpy_from_le(kname, t->name, len); in dtGetKey()
3617 si = t->next; in dtGetKey()
3647 klen = key->namlen; in dtInsertEntry()
3648 kname = key->name; in dtInsertEntry()
3651 hsi = fsi = p->header.freelist; in dtInsertEntry()
3652 h = &p->slot[fsi]; in dtInsertEntry()
3653 p->header.freelist = h->next; in dtInsertEntry()
3654 --p->header.freecnt; in dtInsertEntry()
3657 if (dtlck->index >= dtlck->maxcnt) in dtInsertEntry()
3660 lv = & dtlck->lv[dtlck->index]; in dtInsertEntry()
3661 lv->offset = hsi; in dtInsertEntry()
3664 if (p->header.flag & BT_LEAF) { in dtInsertEntry()
3666 lh->next = h->next; in dtInsertEntry()
3667 lh->inumber = cpu_to_le32(data->leaf.ino); in dtInsertEntry()
3668 lh->namlen = klen; in dtInsertEntry()
3669 name = lh->name; in dtInsertEntry()
3670 if (data->leaf.ip) { in dtInsertEntry()
3672 if (!(p->header.flag & BT_ROOT)) in dtInsertEntry()
3673 bn = addressPXD(&p->header.self); in dtInsertEntry()
3674 lh->index = cpu_to_le32(add_index(data->leaf.tid, in dtInsertEntry()
3675 data->leaf.ip, in dtInsertEntry()
3681 ih->next = h->next; in dtInsertEntry()
3683 *xd = data->xd; in dtInsertEntry()
3684 ih->namlen = klen; in dtInsertEntry()
3685 name = ih->name; in dtInsertEntry()
3691 n = 1; in dtInsertEntry()
3696 klen -= len; in dtInsertEntry()
3699 fsi = p->header.freelist; in dtInsertEntry()
3700 t = &p->slot[fsi]; in dtInsertEntry()
3701 p->header.freelist = t->next; in dtInsertEntry()
3702 --p->header.freecnt; in dtInsertEntry()
3705 if (fsi != xsi + 1) { in dtInsertEntry()
3707 lv->length = n; in dtInsertEntry()
3708 dtlck->index++; in dtInsertEntry()
3711 if (dtlck->index < dtlck->maxcnt) in dtInsertEntry()
3715 lv = & dtlck->lv[0]; in dtInsertEntry()
3718 lv->offset = fsi; in dtInsertEntry()
3724 UniStrncpy_to_le(t->name, kname, len); in dtInsertEntry()
3728 klen -= len; in dtInsertEntry()
3732 lv->length = n; in dtInsertEntry()
3733 dtlck->index++; in dtInsertEntry()
3740 if (p->header.flag & BT_LEAF) in dtInsertEntry()
3741 lh->next = -1; in dtInsertEntry()
3743 ih->next = -1; in dtInsertEntry()
3745 /* multi-segment entry */ in dtInsertEntry()
3746 t->next = -1; in dtInsertEntry()
3750 nextindex = p->header.nextindex; in dtInsertEntry()
3752 memmove(stbl + index + 1, stbl + index, nextindex - index); in dtInsertEntry()
3754 if ((p->header.flag & BT_LEAF) && data->leaf.ip) { in dtInsertEntry()
3762 for (n = index + 1; n <= nextindex; n++) { in dtInsertEntry()
3763 lh = (struct ldtentry *) & (p->slot[stbl[n]]); in dtInsertEntry()
3764 modify_index(data->leaf.tid, data->leaf.ip, in dtInsertEntry()
3765 le32_to_cpu(lh->index), bn, n, in dtInsertEntry()
3776 ++p->header.nextindex; in dtInsertEntry()
3805 sstbl = (s8 *) & sp->slot[sp->header.stblindex]; in dtMoveEntry()
3806 dstbl = (s8 *) & dp->slot[dp->header.stblindex]; in dtMoveEntry()
3808 dsi = dp->header.freelist; /* first (whole page) free slot */ in dtMoveEntry()
3809 sfsi = sp->header.freelist; in dtMoveEntry()
3812 dlv = & ddtlck->lv[ddtlck->index]; in dtMoveEntry()
3813 dlv->offset = dsi; in dtMoveEntry()
3816 slv = & sdtlck->lv[sdtlck->index]; in dtMoveEntry()
3817 slv->offset = sstbl[si]; in dtMoveEntry()
3818 xssi = slv->offset - 1; in dtMoveEntry()
3824 for (di = 0; si < sp->header.nextindex; si++, di++) { in dtMoveEntry()
3829 if (ssi != xssi + 1) { in dtMoveEntry()
3831 slv->length = ns; in dtMoveEntry()
3832 sdtlck->index++; in dtMoveEntry()
3835 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
3839 slv = & sdtlck->lv[0]; in dtMoveEntry()
3842 slv->offset = ssi; in dtMoveEntry()
3850 h = d = &dp->slot[dsi]; in dtMoveEntry()
3853 s = &sp->slot[ssi]; in dtMoveEntry()
3854 if (sp->header.flag & BT_LEAF) { in dtMoveEntry()
3858 snamlen = slh->namlen; in dtMoveEntry()
3862 dlh->index = slh->index; /* little-endian */ in dtMoveEntry()
3868 next = slh->next; in dtMoveEntry()
3872 dlh->next = dsi; in dtMoveEntry()
3875 snamlen = sih->namlen; in dtMoveEntry()
3880 next = sih->next; in dtMoveEntry()
3883 dih->next = dsi; in dtMoveEntry()
3887 s->next = sfsi; in dtMoveEntry()
3888 s->cnt = 1; in dtMoveEntry()
3898 snamlen -= len; in dtMoveEntry()
3901 if (ssi != xssi + 1) { in dtMoveEntry()
3903 slv->length = ns; in dtMoveEntry()
3904 sdtlck->index++; in dtMoveEntry()
3907 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
3913 slv = & sdtlck->lv[0]; in dtMoveEntry()
3916 slv->offset = ssi; in dtMoveEntry()
3921 s = &sp->slot[ssi]; in dtMoveEntry()
3927 UniStrncpy_le(d->name, s->name, len); in dtMoveEntry()
3934 d->next = dsi; in dtMoveEntry()
3937 next = s->next; in dtMoveEntry()
3938 s->next = sfsi; in dtMoveEntry()
3939 s->cnt = 1; in dtMoveEntry()
3942 snamlen -= len; in dtMoveEntry()
3948 if (dp->header.flag & BT_LEAF) in dtMoveEntry()
3949 dlh->next = -1; in dtMoveEntry()
3951 dih->next = -1; in dtMoveEntry()
3953 /* multi-segment entry */ in dtMoveEntry()
3954 d->next = -1; in dtMoveEntry()
3958 slv->length = ns; in dtMoveEntry()
3959 sdtlck->index++; in dtMoveEntry()
3962 dlv->length = nd; in dtMoveEntry()
3963 ddtlck->index++; in dtMoveEntry()
3967 sp->header.freelist = sfsi; in dtMoveEntry()
3968 sp->header.freecnt += nd; in dtMoveEntry()
3971 dp->header.nextindex = di; in dtMoveEntry()
3973 dp->header.freelist = dsi; in dtMoveEntry()
3974 dp->header.freecnt -= nd; in dtMoveEntry()
4004 if (dtlck->index >= dtlck->maxcnt) in dtDeleteEntry()
4006 lv = & dtlck->lv[dtlck->index]; in dtDeleteEntry()
4008 lv->offset = fsi; in dtDeleteEntry()
4011 t = &p->slot[fsi]; in dtDeleteEntry()
4012 if (p->header.flag & BT_LEAF) in dtDeleteEntry()
4013 si = ((struct ldtentry *) t)->next; in dtDeleteEntry()
4015 si = ((struct idtentry *) t)->next; in dtDeleteEntry()
4016 t->next = si; in dtDeleteEntry()
4017 t->cnt = 1; in dtDeleteEntry()
4019 n = freecnt = 1; in dtDeleteEntry()
4025 if (si != xsi + 1) { in dtDeleteEntry()
4027 lv->length = n; in dtDeleteEntry()
4028 dtlck->index++; in dtDeleteEntry()
4031 if (dtlck->index < dtlck->maxcnt) in dtDeleteEntry()
4035 lv = & dtlck->lv[0]; in dtDeleteEntry()
4038 lv->offset = si; in dtDeleteEntry()
4046 t = &p->slot[si]; in dtDeleteEntry()
4047 t->cnt = 1; in dtDeleteEntry()
4048 si = t->next; in dtDeleteEntry()
4052 lv->length = n; in dtDeleteEntry()
4053 dtlck->index++; in dtDeleteEntry()
4058 t->next = p->header.freelist; in dtDeleteEntry()
4059 p->header.freelist = fsi; in dtDeleteEntry()
4060 p->header.freecnt += freecnt; in dtDeleteEntry()
4065 si = p->header.nextindex; in dtDeleteEntry()
4066 if (fi < si - 1) in dtDeleteEntry()
4067 memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1); in dtDeleteEntry()
4069 p->header.nextindex--; in dtDeleteEntry()
4099 if (dtlck->index >= dtlck->maxcnt) in dtTruncateEntry()
4101 lv = & dtlck->lv[dtlck->index]; in dtTruncateEntry()
4103 lv->offset = tsi; in dtTruncateEntry()
4106 t = &p->slot[tsi]; in dtTruncateEntry()
4107 ASSERT(p->header.flag & BT_INTERNAL); in dtTruncateEntry()
4108 ((struct idtentry *) t)->namlen = 0; in dtTruncateEntry()
4109 si = ((struct idtentry *) t)->next; in dtTruncateEntry()
4110 ((struct idtentry *) t)->next = -1; in dtTruncateEntry()
4112 n = 1; in dtTruncateEntry()
4120 if (si != xsi + 1) { in dtTruncateEntry()
4122 lv->length = n; in dtTruncateEntry()
4123 dtlck->index++; in dtTruncateEntry()
4126 if (dtlck->index < dtlck->maxcnt) in dtTruncateEntry()
4130 lv = & dtlck->lv[0]; in dtTruncateEntry()
4133 lv->offset = si; in dtTruncateEntry()
4141 t = &p->slot[si]; in dtTruncateEntry()
4142 t->cnt = 1; in dtTruncateEntry()
4143 si = t->next; in dtTruncateEntry()
4147 lv->length = n; in dtTruncateEntry()
4148 dtlck->index++; in dtTruncateEntry()
4155 t->next = p->header.freelist; in dtTruncateEntry()
4156 p->header.freelist = fsi; in dtTruncateEntry()
4157 p->header.freecnt += freecnt; in dtTruncateEntry()
4176 fsi = p->header.freelist; in dtLinelockFreelist()
4179 if (dtlck->index >= dtlck->maxcnt) in dtLinelockFreelist()
4181 lv = & dtlck->lv[dtlck->index]; in dtLinelockFreelist()
4183 lv->offset = fsi; in dtLinelockFreelist()
4185 n = 1; in dtLinelockFreelist()
4188 t = &p->slot[fsi]; in dtLinelockFreelist()
4189 si = t->next; in dtLinelockFreelist()
4194 if (si != xsi + 1) { in dtLinelockFreelist()
4196 lv->length = n; in dtLinelockFreelist()
4197 dtlck->index++; in dtLinelockFreelist()
4200 if (dtlck->index < dtlck->maxcnt) in dtLinelockFreelist()
4204 lv = & dtlck->lv[0]; in dtLinelockFreelist()
4207 lv->offset = si; in dtLinelockFreelist()
4214 t = &p->slot[si]; in dtLinelockFreelist()
4215 si = t->next; in dtLinelockFreelist()
4219 lv->length = n; in dtLinelockFreelist()
4220 dtlck->index++; in dtLinelockFreelist()
4232 * tid - Transaction id
4233 * ip - Inode of parent directory
4234 * key - Name of entry to be modified
4235 * orig_ino - Original inode number expected in entry
4236 * new_ino - New inode number to put into entry
4237 * flag - JFS_RENAME
4240 * -ESTALE - If entry found does not match orig_ino passed in
4241 * -ENOENT - If no entry can be found to match key
4242 * 0 - If successfully modified entry
4276 dtlck = (struct dt_lock *) & tlck->lock; in dtModify()
4283 ASSERT(dtlck->index == 0); in dtModify()
4284 lv = & dtlck->lv[0]; in dtModify()
4285 lv->offset = entry_si; in dtModify()
4286 lv->length = 1; in dtModify()
4287 dtlck->index++; in dtModify()
4290 entry = (struct ldtentry *) & p->slot[entry_si]; in dtModify()
4293 entry->inumber = cpu_to_le32(new_ino); in dtModify()