Lines Matching +full:smp +full:- +full:offset
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
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))) { \
122 jfs_error((IP)->i_sb, \
125 RC = -EIO; \
159 loff_t * offset, struct btstack * btstack);
185 #define ciToUpper(c) UniStrupr((c)->name)
241 s64 offset; in find_index() local
249 maxWarnings--; in find_index()
254 if (index >= jfs_ip->next_index) { in find_index()
264 slot = &jfs_ip->i_dirtable[index - 2]; in find_index()
266 offset = (index - 2) * sizeof(struct dir_table_slot); in find_index()
267 page_offset = offset & (PSIZE - 1); in find_index()
268 blkno = ((offset + 1) >> L2PSIZE) << in find_index()
269 JFS_SBI(ip->i_sb)->l2nbperpage; in find_index()
285 (struct dir_table_slot *) ((char *) (*mp)->data + in find_index()
299 llck = (struct linelock *) tlck->lock; in lock_index()
301 if (llck->index >= llck->maxcnt) in lock_index()
303 lv = &llck->lv[llck->index]; in lock_index()
309 lv->offset = ((index - 2) & 511) >> 1; in lock_index()
310 lv->length = 1; in lock_index()
311 llck->index++; in lock_index()
323 struct super_block *sb = ip->i_sb; in add_index()
332 s64 offset; in add_index() local
339 if (jfs_ip->next_index < 2) { in add_index()
341 jfs_ip->next_index); in add_index()
342 jfs_ip->next_index = 2; in add_index()
345 index = jfs_ip->next_index++; in add_index()
351 ip->i_size = (loff_t) (index - 1) << 3; in add_index()
356 dirtab_slot = &jfs_ip->i_dirtable[index-2]; in add_index()
357 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
358 dirtab_slot->slot = slot; in add_index()
372 if (dquot_alloc_block(ip, sbi->nbperpage)) in add_index()
374 if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) { in add_index()
375 dquot_free_block(ip, sbi->nbperpage); in add_index()
383 memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table)); in add_index()
386 * Initialize empty x-tree in add_index()
393 if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) { in add_index()
396 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
398 dbFree(ip, xaddr, sbi->nbperpage); in add_index()
399 dquot_free_block(ip, sbi->nbperpage); in add_index()
402 ip->i_size = PSIZE; in add_index()
408 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
413 llck = (struct linelock *) & tlck->lock; in add_index()
414 ASSERT(llck->index == 0); in add_index()
415 lv = &llck->lv[0]; in add_index()
417 lv->offset = 0; in add_index()
418 lv->length = 6; /* tlckDATA slot size is 16 bytes */ in add_index()
419 llck->index++; in add_index()
421 memcpy(mp->data, temp_table, sizeof(temp_table)); in add_index()
432 offset = (index - 2) * sizeof(struct dir_table_slot); in add_index()
433 page_offset = offset & (PSIZE - 1); in add_index()
434 blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage; in add_index()
440 if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) { in add_index()
444 ip->i_size += PSIZE; in add_index()
447 memset(mp->data, 0, PSIZE); /* Just looks better */ in add_index()
449 xtTruncate(tid, ip, offset, COMMIT_PWMAP); in add_index()
461 (struct dir_table_slot *) ((char *) mp->data + page_offset); in add_index()
462 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
463 dirtab_slot->slot = slot; in add_index()
473 jfs_ip->next_index--; in add_index()
494 dirtab_slot->flag = DIR_INDEX_FREE; in free_index()
495 dirtab_slot->slot = dirtab_slot->addr1 = 0; in free_index()
496 dirtab_slot->addr2 = cpu_to_le32(next); in free_index()
522 dirtab_slot->slot = slot; in modify_index()
545 return -EIO; in read_index()
564 * return: 0 - search result on stack, leaf page pinned;
565 * errno - I/O error
579 int psize = 288; /* initial in-line directory */ in dtSearch()
582 struct super_block *sb = ip->i_sb; in dtSearch()
587 rc = -ENOMEM; in dtSearch()
592 /* uppercase search key for c-i directory */ in dtSearch()
593 UniStrcpy(ciKey.name, key->name); in dtSearch()
594 ciKey.namlen = key->namlen; in dtSearch()
596 /* only uppercase if case-insensitive support is on */ in dtSearch()
597 if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) { in dtSearch()
603 btstack->nsplit = 1; in dtSearch()
633 for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) { in dtSearch()
637 rc = -EIO; in dtSearch()
641 if (p->header.flag & BT_LEAF) { in dtSearch()
645 JFS_SBI(sb)->mntflag); in dtSearch()
657 /* search hit - leaf page: in dtSearch()
660 if (p->header.flag & BT_LEAF) { in dtSearch()
662 ((struct ldtentry *) & p->slot[stbl[index]])->inumber); in dtSearch()
678 rc = -EEXIST; in dtSearch()
688 rc = -ESTALE; in dtSearch()
697 btsp = btstack->top; in dtSearch()
698 btsp->bn = bn; in dtSearch()
699 btsp->index = index; in dtSearch()
700 btsp->mp = mp; in dtSearch()
706 /* search hit - internal page: in dtSearch()
714 --lim; in dtSearch()
725 * search miss - leaf page in dtSearch()
730 if (p->header.flag & BT_LEAF) { in dtSearch()
736 rc = -ENOENT; in dtSearch()
746 btsp = btstack->top; in dtSearch()
747 btsp->bn = bn; in dtSearch()
748 btsp->index = base; in dtSearch()
749 btsp->mp = mp; in dtSearch()
756 * search miss - internal page in dtSearch()
758 * if base is non-zero, decrement base by one to get the parent in dtSearch()
761 index = base ? base - 1 : base; in dtSearch()
774 rc = -EIO; in dtSearch()
777 btstack->nsplit++; in dtSearch()
783 pxd = (pxd_t *) & p->slot[stbl[index]]; in dtSearch()
785 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; in dtSearch()
811 * return: 0 - success;
812 * errno - failure;
818 struct metapage *mp; /* meta-page buffer */ in dtInsert()
819 dtpage_t *p; /* base B+-tree index page */ in dtInsert()
836 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtInsert()
837 if (p->header.freelist == 0) in dtInsert()
838 return -EINVAL; in dtInsert()
844 if (JFS_IP(ip)->next_index == DIREND) { in dtInsert()
846 return -EMLINK; in dtInsert()
848 n = NDTLEAF(name->namlen); in dtInsert()
852 n = NDTLEAF_LEGACY(name->namlen); in dtInsert()
864 if (n > p->header.freecnt) { in dtInsert()
884 dtlck = (struct dt_lock *) & tlck->lock; in dtInsert()
885 ASSERT(dtlck->index == 0); in dtInsert()
886 lv = & dtlck->lv[0]; in dtInsert()
889 lv->offset = 0; in dtInsert()
890 lv->length = 1; in dtInsert()
891 dtlck->index++; in dtInsert()
895 /* linelock stbl of non-root leaf page */ in dtInsert()
896 if (!(p->header.flag & BT_ROOT)) { in dtInsert()
897 if (dtlck->index >= dtlck->maxcnt) in dtInsert()
899 lv = & dtlck->lv[dtlck->index]; in dtInsert()
901 lv->offset = p->header.stblindex + n; in dtInsert()
902 lv->length = in dtInsert()
903 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtInsert()
904 dtlck->index++; in dtInsert()
921 * return: 0 - success;
922 * errno - failure;
928 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dtSplitUp()
930 struct metapage *smp; in dtSplitUp() local
944 ddata_t *data = split->data; in dtSplitUp()
952 smp = split->mp; in dtSplitUp()
953 sp = DT_PAGE(ip, smp); in dtSplitUp()
957 DT_PUTPAGE(smp); in dtSplitUp()
958 rc = -ENOMEM; in dtSplitUp()
971 if (sp->header.flag & BT_ROOT) { in dtSplitUp()
976 n = sbi->bsize >> L2DTSLOTSIZE; in dtSplitUp()
977 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
978 n -= DTROOTMAXSLOT - sp->header.freecnt; /* header + entries */ in dtSplitUp()
979 if (n <= split->nslot) in dtSplitUp()
982 DT_PUTPAGE(smp); in dtSplitUp()
991 split->pxdlist = &pxdlist; in dtSplitUp()
999 DT_PUTPAGE(smp); in dtSplitUp()
1002 ip->i_size = xlen << sbi->l2bsize; in dtSplitUp()
1013 pxd = &sp->header.self; in dtSplitUp()
1015 xsize = xlen << sbi->l2bsize; in dtSplitUp()
1019 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
1020 if ((n + sp->header.freecnt) <= split->nslot) in dtSplitUp()
1031 if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen, in dtSplitUp()
1040 split->pxdlist = &pxdlist; in dtSplitUp()
1049 xlen = lengthPXD(pxd) - n; in dtSplitUp()
1054 ip->i_size = lengthPXD(pxd) << sbi->l2bsize; in dtSplitUp()
1058 DT_PUTPAGE(smp); in dtSplitUp()
1073 n = btstack->nsplit; in dtSplitUp()
1075 xlen = sbi->nbperpage; in dtSplitUp()
1076 for (pxd = pxdlist.pxd; n > 0; n--, pxd++) { in dtSplitUp()
1084 DT_PUTPAGE(smp); in dtSplitUp()
1090 split->pxdlist = &pxdlist; in dtSplitUp()
1092 DT_PUTPAGE(smp); in dtSplitUp()
1099 ip->i_size += PSIZE; in dtSplitUp()
1126 lmp = smp; in dtSplitUp()
1133 DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); in dtSplitUp()
1144 skip = parent->index + 1; in dtSplitUp()
1167 * the entire key must be retained for the next-to-leftmost in dtSplitUp()
1171 switch (rp->header.flag & BT_TYPE) { in dtSplitUp()
1178 if ((sp->header.flag & BT_ROOT && skip > 1) || in dtSplitUp()
1179 sp->header.prev != 0 || skip > 1) { in dtSplitUp()
1182 lp->header.nextindex-1, in dtSplitUp()
1184 sbi->mntflag); in dtSplitUp()
1188 DT_PUTPAGE(smp); in dtSplitUp()
1196 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1199 if ((sbi->mntflag & JFS_OS2) == JFS_OS2) in dtSplitUp()
1207 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1222 data->xd = rpxd; /* child page xd */ in dtSplitUp()
1225 * parent page is full - split the parent page in dtSplitUp()
1227 if (n > sp->header.freecnt) { in dtSplitUp()
1229 split->mp = smp; in dtSplitUp()
1230 split->index = skip; /* index at insert */ in dtSplitUp()
1231 split->nslot = n; in dtSplitUp()
1232 split->key = &key; in dtSplitUp()
1233 /* split->data = data; */ in dtSplitUp()
1242 rc = (sp->header.flag & BT_ROOT) ? in dtSplitUp()
1246 DT_PUTPAGE(smp); in dtSplitUp()
1250 /* smp and rmp are pinned */ in dtSplitUp()
1253 * parent page is not full - insert router entry in parent page in dtSplitUp()
1256 BT_MARK_DIRTY(smp, ip); in dtSplitUp()
1260 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); in dtSplitUp()
1261 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitUp()
1262 ASSERT(dtlck->index == 0); in dtSplitUp()
1263 lv = & dtlck->lv[0]; in dtSplitUp()
1266 lv->offset = 0; in dtSplitUp()
1267 lv->length = 1; in dtSplitUp()
1268 dtlck->index++; in dtSplitUp()
1270 /* linelock stbl of non-root parent page */ in dtSplitUp()
1271 if (!(sp->header.flag & BT_ROOT)) { in dtSplitUp()
1274 lv->offset = sp->header.stblindex + n; in dtSplitUp()
1275 lv->length = in dtSplitUp()
1276 ((sp->header.nextindex - in dtSplitUp()
1277 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitUp()
1278 dtlck->index++; in dtSplitUp()
1289 DT_PUTPAGE(smp); in dtSplitUp()
1317 * function: Split a non-root page of a btree.
1321 * return: 0 - success;
1322 * errno - failure;
1329 struct metapage *smp; in dtSplitPage() local
1352 smp = split->mp; in dtSplitPage()
1353 sp = DT_PAGE(ip, smp); in dtSplitPage()
1358 pxdlist = split->pxdlist; in dtSplitPage()
1359 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitPage()
1360 pxdlist->npxd++; in dtSplitPage()
1364 return -EIO; in dtSplitPage()
1373 jfs_info("dtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp); in dtSplitPage()
1380 rdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1382 rp = (dtpage_t *) rmp->data; in dtSplitPage()
1384 rp->header.self = *pxd; in dtSplitPage()
1386 BT_MARK_DIRTY(smp, ip); in dtSplitPage()
1392 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); in dtSplitPage()
1393 sdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1396 ASSERT(sdtlck->index == 0); in dtSplitPage()
1397 slv = & sdtlck->lv[0]; in dtSplitPage()
1398 slv->offset = 0; in dtSplitPage()
1399 slv->length = 1; in dtSplitPage()
1400 sdtlck->index++; in dtSplitPage()
1405 nextbn = le64_to_cpu(sp->header.next); in dtSplitPage()
1406 rp->header.next = cpu_to_le64(nextbn); in dtSplitPage()
1407 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); in dtSplitPage()
1408 sp->header.next = cpu_to_le64(rbn); in dtSplitPage()
1413 rp->header.flag = sp->header.flag; in dtSplitPage()
1416 rp->header.nextindex = 0; in dtSplitPage()
1417 rp->header.stblindex = 1; in dtSplitPage()
1420 rp->header.maxslot = n; in dtSplitPage()
1424 fsi = rp->header.stblindex + stblsize; in dtSplitPage()
1425 rp->header.freelist = fsi; in dtSplitPage()
1426 rp->header.freecnt = rp->header.maxslot - fsi; in dtSplitPage()
1441 if (nextbn == 0 && split->index == sp->header.nextindex) { in dtSplitPage()
1443 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1444 rlv->offset = 0; in dtSplitPage()
1445 rlv->length = 2; in dtSplitPage()
1446 rdtlck->index++; in dtSplitPage()
1451 f = &rp->slot[fsi]; in dtSplitPage()
1452 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1453 f->next = fsi; in dtSplitPage()
1454 f->next = -1; in dtSplitPage()
1457 dtInsertEntry(rp, 0, split->key, split->data, &rdtlck); in dtSplitPage()
1463 * non-sequential insert (at possibly middle page) in dtSplitPage()
1483 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1486 lv = & dtlck->lv[dtlck->index]; in dtSplitPage()
1487 lv->offset = 0; in dtSplitPage()
1488 lv->length = 1; in dtSplitPage()
1489 dtlck->index++; in dtSplitPage()
1491 p->header.prev = cpu_to_le64(rbn); in dtSplitPage()
1499 skip = split->index; in dtSplitPage()
1509 stbl = (u8 *) & sp->slot[sp->header.stblindex]; in dtSplitPage()
1510 nextindex = sp->header.nextindex; in dtSplitPage()
1514 n = split->nslot; in dtSplitPage()
1517 switch (sp->header.flag & BT_TYPE) { in dtSplitPage()
1519 ldtentry = (struct ldtentry *) & sp->slot[si]; in dtSplitPage()
1521 n = NDTLEAF(ldtentry->namlen); in dtSplitPage()
1523 n = NDTLEAF_LEGACY(ldtentry-> in dtSplitPage()
1528 idtentry = (struct idtentry *) & sp->slot[si]; in dtSplitPage()
1529 n = NDTINTERNAL(idtentry->namlen); in dtSplitPage()
1555 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1556 rlv->offset = 0; in dtSplitPage()
1557 rlv->length = 5; in dtSplitPage()
1558 rdtlck->index++; in dtSplitPage()
1562 sp->header.nextindex = nxt; in dtSplitPage()
1567 fsi = rp->header.freelist; in dtSplitPage()
1568 f = &rp->slot[fsi]; in dtSplitPage()
1569 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1570 f->next = fsi; in dtSplitPage()
1571 f->next = -1; in dtSplitPage()
1576 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitPage()
1581 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitPage()
1582 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitPage()
1583 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitPage()
1595 dtInsertEntry(sp, skip, split->key, split->data, &sdtlck); in dtSplitPage()
1598 if (sdtlck->index >= sdtlck->maxcnt) in dtSplitPage()
1600 slv = & sdtlck->lv[sdtlck->index]; in dtSplitPage()
1602 slv->offset = sp->header.stblindex + n; in dtSplitPage()
1603 slv->length = in dtSplitPage()
1604 ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitPage()
1605 sdtlck->index++; in dtSplitPage()
1612 skip -= nxt; in dtSplitPage()
1615 dtInsertEntry(rp, skip, split->key, split->data, &rdtlck); in dtSplitPage()
1633 * return: 0 - success;
1634 * errno - failure;
1640 struct super_block *sb = ip->i_sb; in dtExtendPage()
1642 struct metapage *smp, *pmp, *mp; in dtExtendPage() local
1663 smp = split->mp; in dtExtendPage()
1664 sp = DT_PAGE(ip, smp); in dtExtendPage()
1668 DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc); in dtExtendPage()
1675 pxdlist = split->pxdlist; in dtExtendPage()
1676 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtExtendPage()
1677 pxdlist->npxd++; in dtExtendPage()
1680 tpxd = &sp->header.self; in dtExtendPage()
1682 /* in-place extension */ in dtExtendPage()
1692 pxdlock = (struct pxd_lock *) & tlck->lock; in dtExtendPage()
1693 pxdlock->flag = mlckFREEPXD; in dtExtendPage()
1694 pxdlock->pxd = sp->header.self; in dtExtendPage()
1695 pxdlock->index = 1; in dtExtendPage()
1705 for (n = 0; n < sp->header.nextindex; n++) { in dtExtendPage()
1707 (struct ldtentry *) & sp->slot[stbl[n]]; in dtExtendPage()
1709 le32_to_cpu(ldtentry->index), in dtExtendPage()
1720 sp->header.self = *pxd; in dtExtendPage()
1722 jfs_info("dtExtendPage: ip:0x%p smp:0x%p sp:0x%p", ip, smp, sp); in dtExtendPage()
1724 BT_MARK_DIRTY(smp, ip); in dtExtendPage()
1728 tlck = txLock(tid, ip, smp, tlckDTREE | type); in dtExtendPage()
1729 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1730 lv = & dtlck->lv[0]; in dtExtendPage()
1734 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtExtendPage()
1739 oldstblindex = sp->header.stblindex; in dtExtendPage()
1740 oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE; in dtExtendPage()
1741 newstblindex = sp->header.maxslot; in dtExtendPage()
1744 memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex], in dtExtendPage()
1745 sp->header.nextindex); in dtExtendPage()
1748 * in-line extension: linelock old area of extended page in dtExtendPage()
1752 lv->offset = 0; in dtExtendPage()
1753 lv->length = 1; in dtExtendPage()
1754 dtlck->index++; in dtExtendPage()
1758 lv->offset = newstblindex; in dtExtendPage()
1759 lv->length = newstblsize; in dtExtendPage()
1765 lv->offset = 0; in dtExtendPage()
1766 lv->length = sp->header.maxslot + newstblsize; in dtExtendPage()
1769 dtlck->index++; in dtExtendPage()
1771 sp->header.maxslot = n; in dtExtendPage()
1772 sp->header.stblindex = newstblindex; in dtExtendPage()
1773 /* sp->header.nextindex remains the same */ in dtExtendPage()
1779 f = &sp->slot[fsi]; in dtExtendPage()
1780 last = sp->header.freelist; in dtExtendPage()
1782 f->next = last; in dtExtendPage()
1785 sp->header.freelist = last; in dtExtendPage()
1786 sp->header.freecnt += oldstblsize; in dtExtendPage()
1793 f = &sp->slot[fsi]; in dtExtendPage()
1794 for (fsi++; fsi < sp->header.maxslot; f++, fsi++) in dtExtendPage()
1795 f->next = fsi; in dtExtendPage()
1796 f->next = -1; in dtExtendPage()
1799 fsi = sp->header.freelist; in dtExtendPage()
1800 if (fsi == -1) in dtExtendPage()
1801 sp->header.freelist = n; in dtExtendPage()
1804 f = &sp->slot[fsi]; in dtExtendPage()
1805 fsi = f->next; in dtExtendPage()
1806 } while (fsi != -1); in dtExtendPage()
1808 f->next = n; in dtExtendPage()
1811 sp->header.freecnt += sp->header.maxslot - n; in dtExtendPage()
1816 dtInsertEntry(sp, split->index, split->key, split->data, &dtlck); in dtExtendPage()
1823 n = sp->header.maxslot >> 2; in dtExtendPage()
1824 if (sp->header.freelist < n) in dtExtendPage()
1835 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1836 lv = & dtlck->lv[dtlck->index]; in dtExtendPage()
1838 /* linelock parent entry - 1st slot */ in dtExtendPage()
1839 lv->offset = 1; in dtExtendPage()
1840 lv->length = 1; in dtExtendPage()
1841 dtlck->index++; in dtExtendPage()
1844 tpxd = (pxd_t *) & pp->slot[1]; in dtExtendPage()
1860 * since root page << non-root page, and
1866 * return: 0 - success;
1867 * errno - failure;
1873 struct super_block *sb = ip->i_sb; in dtSplitRoot()
1874 struct metapage *smp; in dtSplitRoot() local
1894 smp = split->mp; in dtSplitRoot()
1895 sp = &JFS_IP(ip)->i_dtroot; in dtSplitRoot()
1903 pxdlist = split->pxdlist; in dtSplitRoot()
1904 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitRoot()
1905 pxdlist->npxd++; in dtSplitRoot()
1908 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtSplitRoot()
1911 return -EIO; in dtSplitRoot()
1913 rp = rmp->data; in dtSplitRoot()
1927 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
1929 rp->header.flag = in dtSplitRoot()
1930 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; in dtSplitRoot()
1931 rp->header.self = *pxd; in dtSplitRoot()
1934 rp->header.next = 0; in dtSplitRoot()
1935 rp->header.prev = 0; in dtSplitRoot()
1938 * move in-line root page into new right page extent in dtSplitRoot()
1941 ASSERT(dtlck->index == 0); in dtSplitRoot()
1942 lv = & dtlck->lv[0]; in dtSplitRoot()
1943 lv->offset = 0; in dtSplitRoot()
1944 lv->length = 10; /* 1 + 8 + 1 */ in dtSplitRoot()
1945 dtlck->index++; in dtSplitRoot()
1948 rp->header.maxslot = n; in dtSplitRoot()
1952 rp->header.stblindex = DTROOTMAXSLOT; in dtSplitRoot()
1953 stbl = (s8 *) & rp->slot[DTROOTMAXSLOT]; in dtSplitRoot()
1954 memcpy(stbl, sp->header.stbl, sp->header.nextindex); in dtSplitRoot()
1955 rp->header.nextindex = sp->header.nextindex; in dtSplitRoot()
1958 memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE); in dtSplitRoot()
1965 f = &rp->slot[fsi]; in dtSplitRoot()
1966 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitRoot()
1967 f->next = fsi; in dtSplitRoot()
1968 f->next = -1; in dtSplitRoot()
1971 fsi = sp->header.freelist; in dtSplitRoot()
1972 if (fsi == -1) in dtSplitRoot()
1973 rp->header.freelist = n; in dtSplitRoot()
1975 rp->header.freelist = fsi; in dtSplitRoot()
1978 f = &rp->slot[fsi]; in dtSplitRoot()
1979 fsi = f->next; in dtSplitRoot()
1982 f->next = n; in dtSplitRoot()
1985 rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n; in dtSplitRoot()
1990 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitRoot()
1996 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitRoot()
1997 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitRoot()
1998 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitRoot()
2008 dtInsertEntry(rp, split->index, split->key, split->data, &dtlck); in dtSplitRoot()
2013 * set the 1st entry offset to 0, which force the left-most key in dtSplitRoot()
2016 * The btree comparison code guarantees that the left-most key on any in dtSplitRoot()
2019 BT_MARK_DIRTY(smp, ip); in dtSplitRoot()
2021 * acquire a transaction lock on the root page (in-memory inode) in dtSplitRoot()
2023 tlck = txLock(tid, ip, smp, tlckDTREE | tlckNEW | tlckBTROOT); in dtSplitRoot()
2024 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
2027 ASSERT(dtlck->index == 0); in dtSplitRoot()
2028 lv = & dtlck->lv[0]; in dtSplitRoot()
2029 lv->offset = 0; in dtSplitRoot()
2030 lv->length = DTROOTMAXSLOT; in dtSplitRoot()
2031 dtlck->index++; in dtSplitRoot()
2034 if (sp->header.flag & BT_LEAF) { in dtSplitRoot()
2035 sp->header.flag &= ~BT_LEAF; in dtSplitRoot()
2036 sp->header.flag |= BT_INTERNAL; in dtSplitRoot()
2040 s = (struct idtentry *) & sp->slot[DTENTRYSTART]; in dtSplitRoot()
2043 s->next = -1; in dtSplitRoot()
2044 s->namlen = 0; in dtSplitRoot()
2046 stbl = sp->header.stbl; in dtSplitRoot()
2048 sp->header.nextindex = 1; in dtSplitRoot()
2052 f = &sp->slot[fsi]; in dtSplitRoot()
2056 f->next = fsi; in dtSplitRoot()
2057 f->next = -1; in dtSplitRoot()
2059 sp->header.freelist = DTENTRYSTART + 1; in dtSplitRoot()
2060 sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1); in dtSplitRoot()
2114 ldtentry = (struct ldtentry *) & p->slot[stbl[index]]; in dtDelete()
2115 table_index = le32_to_cpu(ldtentry->index); in dtDelete()
2116 if (index == (p->header.nextindex - 1)) { in dtDelete()
2120 if ((p->header.flag & BT_ROOT) in dtDelete()
2121 || (p->header.next == 0)) in dtDelete()
2122 next_index = -1; in dtDelete()
2125 DT_GETPAGE(ip, le64_to_cpu(p->header.next), in dtDelete()
2128 next_index = -1; in dtDelete()
2132 (struct ldtentry *) & np-> in dtDelete()
2135 le32_to_cpu(ldtentry->index); in dtDelete()
2141 (struct ldtentry *) & p->slot[stbl[index + 1]]; in dtDelete()
2142 next_index = le32_to_cpu(ldtentry->index); in dtDelete()
2149 if (p->header.nextindex == 1) { in dtDelete()
2164 dtlck = (struct dt_lock *) & tlck->lock; in dtDelete()
2167 * Do not assume that dtlck->index will be zero. During a in dtDelete()
2173 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2175 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2176 lv->offset = 0; in dtDelete()
2177 lv->length = 1; in dtDelete()
2178 dtlck->index++; in dtDelete()
2180 /* linelock stbl of non-root leaf page */ in dtDelete()
2181 if (!(p->header.flag & BT_ROOT)) { in dtDelete()
2182 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2184 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2186 lv->offset = p->header.stblindex + i; in dtDelete()
2187 lv->length = in dtDelete()
2188 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDelete()
2190 dtlck->index++; in dtDelete()
2199 if (DO_INDEX(ip) && index < p->header.nextindex) { in dtDelete()
2204 for (i = index; i < p->header.nextindex; i++) { in dtDelete()
2206 (struct ldtentry *) & p->slot[stbl[i]]; in dtDelete()
2208 le32_to_cpu(ldtentry->index), in dtDelete()
2264 * free the non-root leaf page in dtDeleteUp()
2274 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2275 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2276 pxdlock->pxd = fp->header.self; in dtDeleteUp()
2277 pxdlock->index = 1; in dtDeleteUp()
2285 xlen = lengthPXD(&fp->header.self); in dtDeleteUp()
2303 DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); in dtDeleteUp()
2310 index = parent->index; in dtDeleteUp()
2315 nextindex = p->header.nextindex; in dtDeleteUp()
2326 if (p->header.flag & BT_ROOT) { in dtDeleteUp()
2350 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2351 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2352 pxdlock->pxd = p->header.self; in dtDeleteUp()
2353 pxdlock->index = 1; in dtDeleteUp()
2361 xlen = lengthPXD(&p->header.self); in dtDeleteUp()
2386 dtlck = (struct dt_lock *) & tlck->lock; in dtDeleteUp()
2389 if (dtlck->index >= dtlck->maxcnt) in dtDeleteUp()
2391 lv = & dtlck->lv[dtlck->index]; in dtDeleteUp()
2392 lv->offset = 0; in dtDeleteUp()
2393 lv->length = 1; in dtDeleteUp()
2394 dtlck->index++; in dtDeleteUp()
2396 /* linelock stbl of non-root leaf page */ in dtDeleteUp()
2397 if (!(p->header.flag & BT_ROOT)) { in dtDeleteUp()
2398 if (dtlck->index < dtlck->maxcnt) in dtDeleteUp()
2402 lv = & dtlck->lv[0]; in dtDeleteUp()
2405 lv->offset = p->header.stblindex + i; in dtDeleteUp()
2406 lv->length = in dtDeleteUp()
2407 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDeleteUp()
2409 dtlck->index++; in dtDeleteUp()
2417 ((p->header.flag & BT_ROOT) || p->header.prev == 0)) in dtDeleteUp()
2428 ip->i_size -= PSIZE; in dtDeleteUp()
2453 nextbn = le64_to_cpu(p->header.next); in dtRelink()
2454 prevbn = le64_to_cpu(p->header.prev); in dtRelink()
2471 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2474 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2476 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2477 lv->offset = 0; in dtRelink()
2478 lv->length = 1; in dtRelink()
2479 dtlck->index++; in dtRelink()
2481 p->header.prev = cpu_to_le64(prevbn); in dtRelink()
2500 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2503 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2505 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2506 lv->offset = 0; in dtRelink()
2507 lv->length = 1; in dtRelink()
2508 dtlck->index++; in dtRelink()
2510 p->header.next = cpu_to_le64(nextbn); in dtRelink()
2535 * If this was previously an non-empty directory, we need to remove in dtInitRoot()
2547 xflag_save = tblk->xflag; in dtInitRoot()
2548 tblk->xflag = 0; in dtInitRoot()
2560 tblk->xflag = xflag_save; in dtInitRoot()
2562 ip->i_size = 1; in dtInitRoot()
2564 jfs_ip->next_index = 2; in dtInitRoot()
2566 ip->i_size = IDATASIZE; in dtInitRoot()
2573 tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag, in dtInitRoot()
2575 dtlck = (struct dt_lock *) & tlck->lock; in dtInitRoot()
2578 ASSERT(dtlck->index == 0); in dtInitRoot()
2579 lv = & dtlck->lv[0]; in dtInitRoot()
2580 lv->offset = 0; in dtInitRoot()
2581 lv->length = DTROOTMAXSLOT; in dtInitRoot()
2582 dtlck->index++; in dtInitRoot()
2584 p = &jfs_ip->i_dtroot; in dtInitRoot()
2586 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; in dtInitRoot()
2588 p->header.nextindex = 0; in dtInitRoot()
2592 f = &p->slot[fsi]; in dtInitRoot()
2596 f->next = fsi; in dtInitRoot()
2597 f->next = -1; in dtInitRoot()
2599 p->header.freelist = 1; in dtInitRoot()
2600 p->header.freecnt = 8; in dtInitRoot()
2603 p->header.idotdot = cpu_to_le32(idotdot); in dtInitRoot()
2629 tid = txBegin(inode->i_sb, 0); in add_missing_indices()
2639 ASSERT(p->header.flag & BT_LEAF); in add_missing_indices()
2643 tlck->type |= tlckBTROOT; in add_missing_indices()
2645 dtlck = (struct dt_lock *) &tlck->lock; in add_missing_indices()
2648 for (i = 0; i < p->header.nextindex; i++) { in add_missing_indices()
2649 d = (struct ldtentry *) &p->slot[stbl[i]]; in add_missing_indices()
2650 index = le32_to_cpu(d->index); in add_missing_indices()
2651 if ((index < 2) || (index >= JFS_IP(inode)->next_index)) { in add_missing_indices()
2652 d->index = cpu_to_le32(add_index(tid, inode, bn, i)); in add_missing_indices()
2653 if (dtlck->index >= dtlck->maxcnt) in add_missing_indices()
2655 lv = &dtlck->lv[dtlck->index]; in add_missing_indices()
2656 lv->offset = stbl[i]; in add_missing_indices()
2657 lv->length = 1; in add_missing_indices()
2658 dtlck->index++; in add_missing_indices()
2680 * function to determine next variable-sized jfs_dirent in buffer
2686 ((sizeof (struct jfs_dirent) + dirent->name_len + 1 + in next_jfs_dirent()
2687 sizeof (loff_t) - 1) & in next_jfs_dirent()
2688 ~(sizeof (loff_t) - 1))); in next_jfs_dirent()
2695 * from the specified entry offset
2699 * return: offset = (pn, index) of start entry
2705 struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab; in jfs_readdir()
2733 if (ctx->pos == DIREND) in jfs_readdir()
2741 * -1 = End of directory in jfs_readdir()
2745 dir_index = (u32) ctx->pos; in jfs_readdir()
2753 dir_index--; in jfs_readdir()
2759 (dir_index >= JFS_IP(ip)->next_index)) { in jfs_readdir()
2761 ctx->pos = DIREND; in jfs_readdir()
2767 ctx->pos = DIREND; in jfs_readdir()
2771 if (loop_count++ > JFS_IP(ip)->next_index) { in jfs_readdir()
2773 ctx->pos = DIREND; in jfs_readdir()
2777 if (dir_index == -1) { in jfs_readdir()
2778 ctx->pos = DIREND; in jfs_readdir()
2787 ctx->pos = DIREND; in jfs_readdir()
2790 if (p->header.flag & BT_INTERNAL) { in jfs_readdir()
2793 ctx->pos = DIREND; in jfs_readdir()
2801 ctx->pos = 1; in jfs_readdir()
2802 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
2808 ctx->pos = 2; in jfs_readdir()
2813 * Find first entry of left-most leaf in jfs_readdir()
2816 ctx->pos = DIREND; in jfs_readdir()
2827 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6 in jfs_readdir()
2831 * pn > 0: Real entries, pn=1 -> leftmost page in jfs_readdir()
2832 * pn = index = -1: No more entries in jfs_readdir()
2834 dtpos = ctx->pos; in jfs_readdir()
2837 ctx->pos = 1; in jfs_readdir()
2838 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
2840 dtoffset->index = 2; in jfs_readdir()
2841 ctx->pos = dtpos; in jfs_readdir()
2844 if (dtoffset->pn == 0) { in jfs_readdir()
2845 if (dtoffset->index == 2) { in jfs_readdir()
2850 jfs_err("jfs_readdir called with invalid offset!"); in jfs_readdir()
2852 dtoffset->pn = 1; in jfs_readdir()
2853 dtoffset->index = 0; in jfs_readdir()
2854 ctx->pos = dtpos; in jfs_readdir()
2858 ctx->pos = DIREND; in jfs_readdir()
2862 if ((rc = dtReadNext(ip, &ctx->pos, &btstack))) { in jfs_readdir()
2865 ctx->pos = DIREND; in jfs_readdir()
2871 /* offset beyond directory eof ? */ in jfs_readdir()
2873 ctx->pos = DIREND; in jfs_readdir()
2882 ctx->pos = DIREND; in jfs_readdir()
2883 return -ENOMEM; in jfs_readdir()
2893 for (i = index; i < p->header.nextindex; i++) { in jfs_readdir()
2894 d = (struct ldtentry *) & p->slot[stbl[i]]; in jfs_readdir()
2896 if (((long) jfs_dirent + d->namlen + 1) > in jfs_readdir()
2904 d_namleft = d->namlen; in jfs_readdir()
2905 name_ptr = jfs_dirent->name; in jfs_readdir()
2906 jfs_dirent->ino = le32_to_cpu(d->inumber); in jfs_readdir()
2910 jfs_dirent->position = le32_to_cpu(d->index); in jfs_readdir()
2912 * d->index should always be valid, but it in jfs_readdir()
2918 if ((jfs_dirent->position < 2) || in jfs_readdir()
2919 (jfs_dirent->position >= in jfs_readdir()
2920 JFS_IP(ip)->next_index)) { in jfs_readdir()
2933 jfs_dirent->position = unique_pos++; in jfs_readdir()
2940 jfs_dirent->position++; in jfs_readdir()
2942 jfs_dirent->position = dtpos; in jfs_readdir()
2947 outlen = jfs_strfromUCS_le(name_ptr, d->name, len, in jfs_readdir()
2949 jfs_dirent->name_len = outlen; in jfs_readdir()
2952 next = d->next; in jfs_readdir()
2954 t = (struct dtslot *) & p->slot[next]; in jfs_readdir()
2956 d_namleft -= len; in jfs_readdir()
2959 jfs_error(ip->i_sb, in jfs_readdir()
2961 (long)ip->i_ino, in jfs_readdir()
2967 outlen = jfs_strfromUCS_le(name_ptr, t->name, in jfs_readdir()
2969 jfs_dirent->name_len += outlen; in jfs_readdir()
2971 next = t->next; in jfs_readdir()
2978 dtoffset->index++; in jfs_readdir()
2983 if (p->header.flag & BT_ROOT) in jfs_readdir()
2986 bn = le64_to_cpu(p->header.next); in jfs_readdir()
2988 /* update offset (pn:index) for new page */ in jfs_readdir()
2990 dtoffset->pn++; in jfs_readdir()
2991 dtoffset->index = 0; in jfs_readdir()
3001 while (jfs_dirents--) { in jfs_readdir()
3002 ctx->pos = jfs_dirent->position; in jfs_readdir()
3003 if (!dir_emit(ctx, jfs_dirent->name, in jfs_readdir()
3004 jfs_dirent->name_len, in jfs_readdir()
3005 jfs_dirent->ino, DT_UNKNOWN)) in jfs_readdir()
3016 ctx->pos = DIREND; in jfs_readdir()
3043 int psize = 288; /* initial in-line directory */ in dtReadFirst()
3065 if (p->header.flag & BT_LEAF) { in dtReadFirst()
3067 btsp = btstack->top; in dtReadFirst()
3068 btsp->bn = bn; in dtReadFirst()
3069 btsp->index = 0; in dtReadFirst()
3070 btsp->mp = mp; in dtReadFirst()
3080 jfs_error(ip->i_sb, "btstack overrun\n"); in dtReadFirst()
3082 return -EIO; in dtReadFirst()
3089 xd = (pxd_t *) & p->slot[stbl[0]]; in dtReadFirst()
3093 psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize; in dtReadFirst()
3104 * function: get the page of the specified offset (pn:index)
3106 * return: if (offset > eof), bn = -1;
3111 static int dtReadNext(struct inode *ip, loff_t * offset, in dtReadNext() argument
3119 } *dtoffset = (struct dtoffset *) offset; in dtReadNext()
3136 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtReadNext()
3138 /* get the start offset (pn:index) */ in dtReadNext()
3139 pn = dtoffset->pn - 1; /* Now pn = 0 represents leftmost leaf */ in dtReadNext()
3140 index = dtoffset->index; in dtReadNext()
3144 /* offset beyond eof ? */ in dtReadNext()
3145 if (index < p->header.nextindex) in dtReadNext()
3148 if (p->header.flag & BT_ROOT) { in dtReadNext()
3149 bn = -1; in dtReadNext()
3154 dtoffset->pn++; in dtReadNext()
3155 dtoffset->index = index = 0; in dtReadNext()
3159 /* start at non-leftmost page: scan parent pages for large pn */ in dtReadNext()
3160 if (p->header.flag & BT_ROOT) { in dtReadNext()
3161 bn = -1; in dtReadNext()
3171 bn = le64_to_cpu(p->header.next); in dtReadNext()
3176 /* offset beyond eof ? */ in dtReadNext()
3178 bn = -1; in dtReadNext()
3192 btsp = btstack->top; in dtReadNext()
3193 parent = btsp - 1; in dtReadNext()
3194 bn = parent->bn; in dtReadNext()
3200 while (pn >= p->header.nextindex) { in dtReadNext()
3201 pn -= p->header.nextindex; in dtReadNext()
3204 bn = le64_to_cpu(p->header.next); in dtReadNext()
3209 /* offset beyond eof ? */ in dtReadNext()
3211 bn = -1; in dtReadNext()
3221 parent->bn = bn; in dtReadNext()
3226 xd = (pxd_t *) & p->slot[stbl[pn]]; in dtReadNext()
3244 if (index >= p->header.nextindex) { in dtReadNext()
3245 bn = le64_to_cpu(p->header.next); in dtReadNext()
3250 /* offset beyond eof ? */ in dtReadNext()
3252 bn = -1; in dtReadNext()
3262 dtoffset->pn++; in dtReadNext()
3263 dtoffset->index = 0; in dtReadNext()
3268 btsp = btstack->top; in dtReadNext()
3269 btsp->bn = bn; in dtReadNext()
3270 btsp->index = dtoffset->index; in dtReadNext()
3271 btsp->mp = mp; in dtReadNext()
3298 * force the left-most key on internal pages, at any level of in dtCompare()
3306 * it descends to child of the entry anyway - in dtCompare()
3309 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in dtCompare()
3313 kname = key->name; in dtCompare()
3314 klen = key->namlen; in dtCompare()
3316 ih = (struct idtentry *) & p->slot[si]; in dtCompare()
3317 si = ih->next; in dtCompare()
3318 name = ih->name; in dtCompare()
3319 namlen = ih->namlen; in dtCompare()
3327 klen -= len; in dtCompare()
3328 namlen -= len; in dtCompare()
3334 t = (struct dtslot *) & p->slot[si]; in dtCompare()
3337 name = t->name; in dtCompare()
3341 klen -= len; in dtCompare()
3342 namlen -= len; in dtCompare()
3344 si = t->next; in dtCompare()
3347 return (klen - namlen); in dtCompare()
3377 * force the left-most key on internal pages, at any level of in ciCompare()
3385 * it descends to child of the entry anyway - in ciCompare()
3388 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in ciCompare()
3392 kname = key->name; in ciCompare()
3393 klen = key->namlen; in ciCompare()
3398 if (p->header.flag & BT_LEAF) { in ciCompare()
3399 lh = (struct ldtentry *) & p->slot[si]; in ciCompare()
3400 si = lh->next; in ciCompare()
3401 name = lh->name; in ciCompare()
3402 namlen = lh->namlen; in ciCompare()
3412 ih = (struct idtentry *) & p->slot[si]; in ciCompare()
3413 si = ih->next; in ciCompare()
3414 name = ih->name; in ciCompare()
3415 namlen = ih->namlen; in ciCompare()
3422 /* only uppercase if case-insensitive support is on */ in ciCompare()
3427 if ((rc = *kname - x)) in ciCompare()
3431 klen -= len; in ciCompare()
3432 namlen -= len; in ciCompare()
3437 t = (struct dtslot *) & p->slot[si]; in ciCompare()
3440 name = t->name; in ciCompare()
3442 /* only uppercase if case-insensitive support is on */ in ciCompare()
3448 if ((rc = *kname - x)) in ciCompare()
3452 klen -= len; in ciCompare()
3453 namlen -= len; in ciCompare()
3454 si = t->next; in ciCompare()
3457 return (klen - namlen); in ciCompare()
3468 * return: non-zero on error
3482 return -ENOMEM; in ciGetLeafPrefixKey()
3488 return -ENOMEM; in ciGetLeafPrefixKey()
3507 kname = key->name; in ciGetLeafPrefixKey()
3510 namlen; pl++, pr++, namlen--, klen++, kname++) { in ciGetLeafPrefixKey()
3513 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3518 /* l->namlen <= r->namlen since l <= r */ in ciGetLeafPrefixKey()
3521 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3522 } else /* l->namelen == r->namelen */ in ciGetLeafPrefixKey()
3523 key->namlen = klen; in ciGetLeafPrefixKey()
3553 if (p->header.flag & BT_LEAF) { in dtGetKey()
3554 lh = (struct ldtentry *) & p->slot[si]; in dtGetKey()
3555 si = lh->next; in dtGetKey()
3556 namlen = lh->namlen; in dtGetKey()
3557 name = lh->name; in dtGetKey()
3563 ih = (struct idtentry *) & p->slot[si]; in dtGetKey()
3564 si = ih->next; in dtGetKey()
3565 namlen = ih->namlen; in dtGetKey()
3566 name = ih->name; in dtGetKey()
3570 key->namlen = namlen; in dtGetKey()
3571 kname = key->name; in dtGetKey()
3583 t = &p->slot[si]; in dtGetKey()
3585 namlen -= len; in dtGetKey()
3587 UniStrncpy_from_le(kname, t->name, len); in dtGetKey()
3589 si = t->next; in dtGetKey()
3619 klen = key->namlen; in dtInsertEntry()
3620 kname = key->name; in dtInsertEntry()
3623 hsi = fsi = p->header.freelist; in dtInsertEntry()
3624 h = &p->slot[fsi]; in dtInsertEntry()
3625 p->header.freelist = h->next; in dtInsertEntry()
3626 --p->header.freecnt; in dtInsertEntry()
3629 if (dtlck->index >= dtlck->maxcnt) in dtInsertEntry()
3632 lv = & dtlck->lv[dtlck->index]; in dtInsertEntry()
3633 lv->offset = hsi; in dtInsertEntry()
3636 if (p->header.flag & BT_LEAF) { in dtInsertEntry()
3638 lh->next = h->next; in dtInsertEntry()
3639 lh->inumber = cpu_to_le32(data->leaf.ino); in dtInsertEntry()
3640 lh->namlen = klen; in dtInsertEntry()
3641 name = lh->name; in dtInsertEntry()
3642 if (data->leaf.ip) { in dtInsertEntry()
3644 if (!(p->header.flag & BT_ROOT)) in dtInsertEntry()
3645 bn = addressPXD(&p->header.self); in dtInsertEntry()
3646 lh->index = cpu_to_le32(add_index(data->leaf.tid, in dtInsertEntry()
3647 data->leaf.ip, in dtInsertEntry()
3653 ih->next = h->next; in dtInsertEntry()
3655 *xd = data->xd; in dtInsertEntry()
3656 ih->namlen = klen; in dtInsertEntry()
3657 name = ih->name; in dtInsertEntry()
3668 klen -= len; in dtInsertEntry()
3671 fsi = p->header.freelist; in dtInsertEntry()
3672 t = &p->slot[fsi]; in dtInsertEntry()
3673 p->header.freelist = t->next; in dtInsertEntry()
3674 --p->header.freecnt; in dtInsertEntry()
3679 lv->length = n; in dtInsertEntry()
3680 dtlck->index++; in dtInsertEntry()
3683 if (dtlck->index < dtlck->maxcnt) in dtInsertEntry()
3687 lv = & dtlck->lv[0]; in dtInsertEntry()
3690 lv->offset = fsi; in dtInsertEntry()
3696 UniStrncpy_to_le(t->name, kname, len); in dtInsertEntry()
3700 klen -= len; in dtInsertEntry()
3704 lv->length = n; in dtInsertEntry()
3705 dtlck->index++; in dtInsertEntry()
3712 if (p->header.flag & BT_LEAF) in dtInsertEntry()
3713 lh->next = -1; in dtInsertEntry()
3715 ih->next = -1; in dtInsertEntry()
3717 /* multi-segment entry */ in dtInsertEntry()
3718 t->next = -1; in dtInsertEntry()
3722 nextindex = p->header.nextindex; in dtInsertEntry()
3724 memmove(stbl + index + 1, stbl + index, nextindex - index); in dtInsertEntry()
3726 if ((p->header.flag & BT_LEAF) && data->leaf.ip) { in dtInsertEntry()
3735 lh = (struct ldtentry *) & (p->slot[stbl[n]]); in dtInsertEntry()
3736 modify_index(data->leaf.tid, data->leaf.ip, in dtInsertEntry()
3737 le32_to_cpu(lh->index), bn, n, in dtInsertEntry()
3748 ++p->header.nextindex; in dtInsertEntry()
3777 sstbl = (s8 *) & sp->slot[sp->header.stblindex]; in dtMoveEntry()
3778 dstbl = (s8 *) & dp->slot[dp->header.stblindex]; in dtMoveEntry()
3780 dsi = dp->header.freelist; /* first (whole page) free slot */ in dtMoveEntry()
3781 sfsi = sp->header.freelist; in dtMoveEntry()
3784 dlv = & ddtlck->lv[ddtlck->index]; in dtMoveEntry()
3785 dlv->offset = dsi; in dtMoveEntry()
3788 slv = & sdtlck->lv[sdtlck->index]; in dtMoveEntry()
3789 slv->offset = sstbl[si]; in dtMoveEntry()
3790 xssi = slv->offset - 1; in dtMoveEntry()
3796 for (di = 0; si < sp->header.nextindex; si++, di++) { in dtMoveEntry()
3803 slv->length = ns; in dtMoveEntry()
3804 sdtlck->index++; in dtMoveEntry()
3807 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
3811 slv = & sdtlck->lv[0]; in dtMoveEntry()
3814 slv->offset = ssi; in dtMoveEntry()
3822 h = d = &dp->slot[dsi]; in dtMoveEntry()
3825 s = &sp->slot[ssi]; in dtMoveEntry()
3826 if (sp->header.flag & BT_LEAF) { in dtMoveEntry()
3830 snamlen = slh->namlen; in dtMoveEntry()
3834 dlh->index = slh->index; /* little-endian */ in dtMoveEntry()
3840 next = slh->next; in dtMoveEntry()
3844 dlh->next = dsi; in dtMoveEntry()
3847 snamlen = sih->namlen; in dtMoveEntry()
3852 next = sih->next; in dtMoveEntry()
3855 dih->next = dsi; in dtMoveEntry()
3859 s->next = sfsi; in dtMoveEntry()
3860 s->cnt = 1; in dtMoveEntry()
3870 snamlen -= len; in dtMoveEntry()
3875 slv->length = ns; in dtMoveEntry()
3876 sdtlck->index++; in dtMoveEntry()
3879 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
3885 slv = & sdtlck->lv[0]; in dtMoveEntry()
3888 slv->offset = ssi; in dtMoveEntry()
3893 s = &sp->slot[ssi]; in dtMoveEntry()
3899 UniStrncpy_le(d->name, s->name, len); in dtMoveEntry()
3906 d->next = dsi; in dtMoveEntry()
3909 next = s->next; in dtMoveEntry()
3910 s->next = sfsi; in dtMoveEntry()
3911 s->cnt = 1; in dtMoveEntry()
3914 snamlen -= len; in dtMoveEntry()
3920 if (dp->header.flag & BT_LEAF) in dtMoveEntry()
3921 dlh->next = -1; in dtMoveEntry()
3923 dih->next = -1; in dtMoveEntry()
3925 /* multi-segment entry */ in dtMoveEntry()
3926 d->next = -1; in dtMoveEntry()
3930 slv->length = ns; in dtMoveEntry()
3931 sdtlck->index++; in dtMoveEntry()
3934 dlv->length = nd; in dtMoveEntry()
3935 ddtlck->index++; in dtMoveEntry()
3939 sp->header.freelist = sfsi; in dtMoveEntry()
3940 sp->header.freecnt += nd; in dtMoveEntry()
3943 dp->header.nextindex = di; in dtMoveEntry()
3945 dp->header.freelist = dsi; in dtMoveEntry()
3946 dp->header.freecnt -= nd; in dtMoveEntry()
3976 if (dtlck->index >= dtlck->maxcnt) in dtDeleteEntry()
3978 lv = & dtlck->lv[dtlck->index]; in dtDeleteEntry()
3980 lv->offset = fsi; in dtDeleteEntry()
3983 t = &p->slot[fsi]; in dtDeleteEntry()
3984 if (p->header.flag & BT_LEAF) in dtDeleteEntry()
3985 si = ((struct ldtentry *) t)->next; in dtDeleteEntry()
3987 si = ((struct idtentry *) t)->next; in dtDeleteEntry()
3988 t->next = si; in dtDeleteEntry()
3989 t->cnt = 1; in dtDeleteEntry()
3999 lv->length = n; in dtDeleteEntry()
4000 dtlck->index++; in dtDeleteEntry()
4003 if (dtlck->index < dtlck->maxcnt) in dtDeleteEntry()
4007 lv = & dtlck->lv[0]; in dtDeleteEntry()
4010 lv->offset = si; in dtDeleteEntry()
4018 t = &p->slot[si]; in dtDeleteEntry()
4019 t->cnt = 1; in dtDeleteEntry()
4020 si = t->next; in dtDeleteEntry()
4024 lv->length = n; in dtDeleteEntry()
4025 dtlck->index++; in dtDeleteEntry()
4030 t->next = p->header.freelist; in dtDeleteEntry()
4031 p->header.freelist = fsi; in dtDeleteEntry()
4032 p->header.freecnt += freecnt; in dtDeleteEntry()
4037 si = p->header.nextindex; in dtDeleteEntry()
4038 if (fi < si - 1) in dtDeleteEntry()
4039 memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1); in dtDeleteEntry()
4041 p->header.nextindex--; in dtDeleteEntry()
4071 if (dtlck->index >= dtlck->maxcnt) in dtTruncateEntry()
4073 lv = & dtlck->lv[dtlck->index]; in dtTruncateEntry()
4075 lv->offset = tsi; in dtTruncateEntry()
4078 t = &p->slot[tsi]; in dtTruncateEntry()
4079 ASSERT(p->header.flag & BT_INTERNAL); in dtTruncateEntry()
4080 ((struct idtentry *) t)->namlen = 0; in dtTruncateEntry()
4081 si = ((struct idtentry *) t)->next; in dtTruncateEntry()
4082 ((struct idtentry *) t)->next = -1; in dtTruncateEntry()
4094 lv->length = n; in dtTruncateEntry()
4095 dtlck->index++; in dtTruncateEntry()
4098 if (dtlck->index < dtlck->maxcnt) in dtTruncateEntry()
4102 lv = & dtlck->lv[0]; in dtTruncateEntry()
4105 lv->offset = si; in dtTruncateEntry()
4113 t = &p->slot[si]; in dtTruncateEntry()
4114 t->cnt = 1; in dtTruncateEntry()
4115 si = t->next; in dtTruncateEntry()
4119 lv->length = n; in dtTruncateEntry()
4120 dtlck->index++; in dtTruncateEntry()
4127 t->next = p->header.freelist; in dtTruncateEntry()
4128 p->header.freelist = fsi; in dtTruncateEntry()
4129 p->header.freecnt += freecnt; in dtTruncateEntry()
4148 fsi = p->header.freelist; in dtLinelockFreelist()
4151 if (dtlck->index >= dtlck->maxcnt) in dtLinelockFreelist()
4153 lv = & dtlck->lv[dtlck->index]; in dtLinelockFreelist()
4155 lv->offset = fsi; in dtLinelockFreelist()
4160 t = &p->slot[fsi]; in dtLinelockFreelist()
4161 si = t->next; in dtLinelockFreelist()
4168 lv->length = n; in dtLinelockFreelist()
4169 dtlck->index++; in dtLinelockFreelist()
4172 if (dtlck->index < dtlck->maxcnt) in dtLinelockFreelist()
4176 lv = & dtlck->lv[0]; in dtLinelockFreelist()
4179 lv->offset = si; in dtLinelockFreelist()
4186 t = &p->slot[si]; in dtLinelockFreelist()
4187 si = t->next; in dtLinelockFreelist()
4191 lv->length = n; in dtLinelockFreelist()
4192 dtlck->index++; in dtLinelockFreelist()
4204 * tid - Transaction id
4205 * ip - Inode of parent directory
4206 * key - Name of entry to be modified
4207 * orig_ino - Original inode number expected in entry
4208 * new_ino - New inode number to put into entry
4209 * flag - JFS_RENAME
4212 * -ESTALE - If entry found does not match orig_ino passed in
4213 * -ENOENT - If no entry can be found to match key
4214 * 0 - If successfully modified entry
4248 dtlck = (struct dt_lock *) & tlck->lock; in dtModify()
4255 ASSERT(dtlck->index == 0); in dtModify()
4256 lv = & dtlck->lv[0]; in dtModify()
4257 lv->offset = entry_si; in dtModify()
4258 lv->length = 1; in dtModify()
4259 dtlck->index++; in dtModify()
4262 entry = (struct ldtentry *) & p->slot[entry_si]; in dtModify()
4265 entry->inumber = cpu_to_le32(new_ino); in dtModify()