Lines Matching +full:smp +full:- +full:offset
2 * Copyright (C) International Business Machines Corp., 2000-2004
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 * jfs_dtree.c: directory B+-tree manager
22 * B+-tree with variable length key directory:
24 * each directory page is structured as an array of 32-byte
41 * directory starts as a root/leaf page in on-disk inode
54 * case-insensitive directory file system
56 * names are stored in case-sensitive way in leaf entry.
57 * but stored, searched and compared in case-insensitive (uppercase) order
59 * (note that case-sensitive order is BROKEN in storage, e.g.,
60 * sensitive: Ad, aB, aC, aD -> insensitive: aB, aC, aD, Ad
68 * either for, in case-insensitive search, duplicate
69 * or for, in case-sensitive search, for exact match
71 * router entry must be created/stored in case-insensitive way
79 * case-insensitive search:
83 * case-insensitive search of B-tree:
87 * if (leaf entry case-insensitive match found)
88 * if (next entry satisfies case-insensitive match)
90 * if (prev entry satisfies case-insensitive match)
131 if (((P)->header.nextindex > \
132 (((BN) == 0) ? DTROOTMAXSLOT : (P)->header.maxslot)) || \
133 ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT))) { \
135 jfs_error((IP)->i_sb, \
138 RC = -EIO; \
172 loff_t * offset, struct btstack * btstack);
198 #define ciToUpper(c) UniStrupr((c)->name)
254 s64 offset; in find_index() local
262 maxWarnings--; in find_index()
267 if (index >= jfs_ip->next_index) { in find_index()
277 slot = &jfs_ip->i_dirtable[index - 2]; in find_index()
279 offset = (index - 2) * sizeof(struct dir_table_slot); in find_index()
280 page_offset = offset & (PSIZE - 1); in find_index()
281 blkno = ((offset + 1) >> L2PSIZE) << in find_index()
282 JFS_SBI(ip->i_sb)->l2nbperpage; in find_index()
298 (struct dir_table_slot *) ((char *) (*mp)->data + in find_index()
312 llck = (struct linelock *) tlck->lock; in lock_index()
314 if (llck->index >= llck->maxcnt) in lock_index()
316 lv = &llck->lv[llck->index]; in lock_index()
322 lv->offset = ((index - 2) & 511) >> 1; in lock_index()
323 lv->length = 1; in lock_index()
324 llck->index++; in lock_index()
336 struct super_block *sb = ip->i_sb; in add_index()
345 s64 offset; in add_index() local
352 if (jfs_ip->next_index < 2) { in add_index()
354 jfs_ip->next_index); in add_index()
355 jfs_ip->next_index = 2; in add_index()
358 index = jfs_ip->next_index++; in add_index()
364 ip->i_size = (loff_t) (index - 1) << 3; in add_index()
369 dirtab_slot = &jfs_ip->i_dirtable[index-2]; in add_index()
370 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
371 dirtab_slot->slot = slot; in add_index()
385 if (dquot_alloc_block(ip, sbi->nbperpage)) in add_index()
387 if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) { in add_index()
388 dquot_free_block(ip, sbi->nbperpage); in add_index()
396 memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table)); in add_index()
399 * Initialize empty x-tree in add_index()
406 if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) { in add_index()
409 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
411 dbFree(ip, xaddr, sbi->nbperpage); in add_index()
412 dquot_free_block(ip, sbi->nbperpage); in add_index()
415 ip->i_size = PSIZE; in add_index()
421 memcpy(&jfs_ip->i_dirtable, temp_table, in add_index()
426 llck = (struct linelock *) & tlck->lock; in add_index()
427 ASSERT(llck->index == 0); in add_index()
428 lv = &llck->lv[0]; in add_index()
430 lv->offset = 0; in add_index()
431 lv->length = 6; /* tlckDATA slot size is 16 bytes */ in add_index()
432 llck->index++; in add_index()
434 memcpy(mp->data, temp_table, sizeof(temp_table)); in add_index()
445 offset = (index - 2) * sizeof(struct dir_table_slot); in add_index()
446 page_offset = offset & (PSIZE - 1); in add_index()
447 blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage; in add_index()
453 if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) { in add_index()
457 ip->i_size += PSIZE; in add_index()
460 memset(mp->data, 0, PSIZE); /* Just looks better */ in add_index()
462 xtTruncate(tid, ip, offset, COMMIT_PWMAP); in add_index()
474 (struct dir_table_slot *) ((char *) mp->data + page_offset); in add_index()
475 dirtab_slot->flag = DIR_INDEX_VALID; in add_index()
476 dirtab_slot->slot = slot; in add_index()
486 jfs_ip->next_index--; in add_index()
507 dirtab_slot->flag = DIR_INDEX_FREE; in free_index()
508 dirtab_slot->slot = dirtab_slot->addr1 = 0; in free_index()
509 dirtab_slot->addr2 = cpu_to_le32(next); in free_index()
535 dirtab_slot->slot = slot; in modify_index()
558 return -EIO; in read_index()
577 * return: 0 - search result on stack, leaf page pinned;
578 * errno - I/O error
592 int psize = 288; /* initial in-line directory */ in dtSearch()
595 struct super_block *sb = ip->i_sb; in dtSearch()
600 rc = -ENOMEM; in dtSearch()
605 /* uppercase search key for c-i directory */ in dtSearch()
606 UniStrcpy(ciKey.name, key->name); in dtSearch()
607 ciKey.namlen = key->namlen; in dtSearch()
609 /* only uppercase if case-insensitive support is on */ in dtSearch()
610 if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) { in dtSearch()
616 btstack->nsplit = 1; in dtSearch()
646 for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) { in dtSearch()
649 if (p->header.flag & BT_LEAF) { in dtSearch()
653 JFS_SBI(sb)->mntflag); in dtSearch()
665 /* search hit - leaf page: in dtSearch()
668 if (p->header.flag & BT_LEAF) { in dtSearch()
670 ((struct ldtentry *) & p->slot[stbl[index]])->inumber); in dtSearch()
686 rc = -EEXIST; in dtSearch()
696 rc = -ESTALE; in dtSearch()
705 btsp = btstack->top; in dtSearch()
706 btsp->bn = bn; in dtSearch()
707 btsp->index = index; in dtSearch()
708 btsp->mp = mp; in dtSearch()
714 /* search hit - internal page: in dtSearch()
722 --lim; in dtSearch()
733 * search miss - leaf page in dtSearch()
738 if (p->header.flag & BT_LEAF) { in dtSearch()
744 rc = -ENOENT; in dtSearch()
754 btsp = btstack->top; in dtSearch()
755 btsp->bn = bn; in dtSearch()
756 btsp->index = base; in dtSearch()
757 btsp->mp = mp; in dtSearch()
764 * search miss - internal page in dtSearch()
766 * if base is non-zero, decrement base by one to get the parent in dtSearch()
769 index = base ? base - 1 : base; in dtSearch()
782 rc = -EIO; in dtSearch()
785 btstack->nsplit++; in dtSearch()
791 pxd = (pxd_t *) & p->slot[stbl[index]]; in dtSearch()
793 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; in dtSearch()
819 * return: 0 - success;
820 * errno - failure;
826 struct metapage *mp; /* meta-page buffer */ in dtInsert()
827 dtpage_t *p; /* base B+-tree index page */ in dtInsert()
844 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtInsert()
850 if (JFS_IP(ip)->next_index == DIREND) { in dtInsert()
852 return -EMLINK; in dtInsert()
854 n = NDTLEAF(name->namlen); in dtInsert()
858 n = NDTLEAF_LEGACY(name->namlen); in dtInsert()
870 if (n > p->header.freecnt) { in dtInsert()
890 dtlck = (struct dt_lock *) & tlck->lock; in dtInsert()
891 ASSERT(dtlck->index == 0); in dtInsert()
892 lv = & dtlck->lv[0]; in dtInsert()
895 lv->offset = 0; in dtInsert()
896 lv->length = 1; in dtInsert()
897 dtlck->index++; in dtInsert()
901 /* linelock stbl of non-root leaf page */ in dtInsert()
902 if (!(p->header.flag & BT_ROOT)) { in dtInsert()
903 if (dtlck->index >= dtlck->maxcnt) in dtInsert()
905 lv = & dtlck->lv[dtlck->index]; in dtInsert()
907 lv->offset = p->header.stblindex + n; in dtInsert()
908 lv->length = in dtInsert()
909 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtInsert()
910 dtlck->index++; in dtInsert()
927 * return: 0 - success;
928 * errno - failure;
934 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dtSplitUp()
936 struct metapage *smp; in dtSplitUp() local
950 ddata_t *data = split->data; in dtSplitUp()
958 smp = split->mp; in dtSplitUp()
959 sp = DT_PAGE(ip, smp); in dtSplitUp()
963 DT_PUTPAGE(smp); in dtSplitUp()
964 rc = -ENOMEM; in dtSplitUp()
977 if (sp->header.flag & BT_ROOT) { in dtSplitUp()
982 n = sbi->bsize >> L2DTSLOTSIZE; in dtSplitUp()
983 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
984 n -= DTROOTMAXSLOT - sp->header.freecnt; /* header + entries */ in dtSplitUp()
985 if (n <= split->nslot) in dtSplitUp()
988 DT_PUTPAGE(smp); in dtSplitUp()
997 split->pxdlist = &pxdlist; in dtSplitUp()
1005 DT_PUTPAGE(smp); in dtSplitUp()
1008 ip->i_size = xlen << sbi->l2bsize; in dtSplitUp()
1019 pxd = &sp->header.self; in dtSplitUp()
1021 xsize = xlen << sbi->l2bsize; in dtSplitUp()
1025 n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */ in dtSplitUp()
1026 if ((n + sp->header.freecnt) <= split->nslot) in dtSplitUp()
1037 if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen, in dtSplitUp()
1046 split->pxdlist = &pxdlist; in dtSplitUp()
1055 xlen = lengthPXD(pxd) - n; in dtSplitUp()
1060 ip->i_size = lengthPXD(pxd) << sbi->l2bsize; in dtSplitUp()
1064 DT_PUTPAGE(smp); in dtSplitUp()
1079 n = btstack->nsplit; in dtSplitUp()
1081 xlen = sbi->nbperpage; in dtSplitUp()
1082 for (pxd = pxdlist.pxd; n > 0; n--, pxd++) { in dtSplitUp()
1090 DT_PUTPAGE(smp); in dtSplitUp()
1096 split->pxdlist = &pxdlist; in dtSplitUp()
1098 DT_PUTPAGE(smp); in dtSplitUp()
1105 ip->i_size += PSIZE; in dtSplitUp()
1132 lmp = smp; in dtSplitUp()
1139 DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); in dtSplitUp()
1150 skip = parent->index + 1; in dtSplitUp()
1173 * the entire key must be retained for the next-to-leftmost in dtSplitUp()
1177 switch (rp->header.flag & BT_TYPE) { in dtSplitUp()
1184 if ((sp->header.flag & BT_ROOT && skip > 1) || in dtSplitUp()
1185 sp->header.prev != 0 || skip > 1) { in dtSplitUp()
1188 lp->header.nextindex-1, in dtSplitUp()
1190 sbi->mntflag); in dtSplitUp()
1194 DT_PUTPAGE(smp); in dtSplitUp()
1202 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1205 if ((sbi->mntflag & JFS_OS2) == JFS_OS2) in dtSplitUp()
1213 dtGetKey(rp, 0, &key, sbi->mntflag); in dtSplitUp()
1228 data->xd = rpxd; /* child page xd */ in dtSplitUp()
1231 * parent page is full - split the parent page in dtSplitUp()
1233 if (n > sp->header.freecnt) { in dtSplitUp()
1235 split->mp = smp; in dtSplitUp()
1236 split->index = skip; /* index at insert */ in dtSplitUp()
1237 split->nslot = n; in dtSplitUp()
1238 split->key = &key; in dtSplitUp()
1239 /* split->data = data; */ in dtSplitUp()
1248 rc = (sp->header.flag & BT_ROOT) ? in dtSplitUp()
1252 DT_PUTPAGE(smp); in dtSplitUp()
1256 /* smp and rmp are pinned */ in dtSplitUp()
1259 * parent page is not full - insert router entry in parent page in dtSplitUp()
1262 BT_MARK_DIRTY(smp, ip); in dtSplitUp()
1266 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); in dtSplitUp()
1267 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitUp()
1268 ASSERT(dtlck->index == 0); in dtSplitUp()
1269 lv = & dtlck->lv[0]; in dtSplitUp()
1272 lv->offset = 0; in dtSplitUp()
1273 lv->length = 1; in dtSplitUp()
1274 dtlck->index++; in dtSplitUp()
1276 /* linelock stbl of non-root parent page */ in dtSplitUp()
1277 if (!(sp->header.flag & BT_ROOT)) { in dtSplitUp()
1280 lv->offset = sp->header.stblindex + n; in dtSplitUp()
1281 lv->length = in dtSplitUp()
1282 ((sp->header.nextindex - in dtSplitUp()
1283 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitUp()
1284 dtlck->index++; in dtSplitUp()
1295 DT_PUTPAGE(smp); in dtSplitUp()
1323 * function: Split a non-root page of a btree.
1327 * return: 0 - success;
1328 * errno - failure;
1335 struct metapage *smp; in dtSplitPage() local
1358 smp = split->mp; in dtSplitPage()
1359 sp = DT_PAGE(ip, smp); in dtSplitPage()
1364 pxdlist = split->pxdlist; in dtSplitPage()
1365 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitPage()
1366 pxdlist->npxd++; in dtSplitPage()
1370 return -EIO; in dtSplitPage()
1379 jfs_info("dtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp); in dtSplitPage()
1386 rdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1388 rp = (dtpage_t *) rmp->data; in dtSplitPage()
1390 rp->header.self = *pxd; in dtSplitPage()
1392 BT_MARK_DIRTY(smp, ip); in dtSplitPage()
1398 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY); in dtSplitPage()
1399 sdtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1402 ASSERT(sdtlck->index == 0); in dtSplitPage()
1403 slv = & sdtlck->lv[0]; in dtSplitPage()
1404 slv->offset = 0; in dtSplitPage()
1405 slv->length = 1; in dtSplitPage()
1406 sdtlck->index++; in dtSplitPage()
1411 nextbn = le64_to_cpu(sp->header.next); in dtSplitPage()
1412 rp->header.next = cpu_to_le64(nextbn); in dtSplitPage()
1413 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); in dtSplitPage()
1414 sp->header.next = cpu_to_le64(rbn); in dtSplitPage()
1419 rp->header.flag = sp->header.flag; in dtSplitPage()
1422 rp->header.nextindex = 0; in dtSplitPage()
1423 rp->header.stblindex = 1; in dtSplitPage()
1426 rp->header.maxslot = n; in dtSplitPage()
1430 fsi = rp->header.stblindex + stblsize; in dtSplitPage()
1431 rp->header.freelist = fsi; in dtSplitPage()
1432 rp->header.freecnt = rp->header.maxslot - fsi; in dtSplitPage()
1447 if (nextbn == 0 && split->index == sp->header.nextindex) { in dtSplitPage()
1449 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1450 rlv->offset = 0; in dtSplitPage()
1451 rlv->length = 2; in dtSplitPage()
1452 rdtlck->index++; in dtSplitPage()
1457 f = &rp->slot[fsi]; in dtSplitPage()
1458 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1459 f->next = fsi; in dtSplitPage()
1460 f->next = -1; in dtSplitPage()
1463 dtInsertEntry(rp, 0, split->key, split->data, &rdtlck); in dtSplitPage()
1469 * non-sequential insert (at possibly middle page) in dtSplitPage()
1489 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitPage()
1492 lv = & dtlck->lv[dtlck->index]; in dtSplitPage()
1493 lv->offset = 0; in dtSplitPage()
1494 lv->length = 1; in dtSplitPage()
1495 dtlck->index++; in dtSplitPage()
1497 p->header.prev = cpu_to_le64(rbn); in dtSplitPage()
1505 skip = split->index; in dtSplitPage()
1515 stbl = (u8 *) & sp->slot[sp->header.stblindex]; in dtSplitPage()
1516 nextindex = sp->header.nextindex; in dtSplitPage()
1520 n = split->nslot; in dtSplitPage()
1523 switch (sp->header.flag & BT_TYPE) { in dtSplitPage()
1525 ldtentry = (struct ldtentry *) & sp->slot[si]; in dtSplitPage()
1527 n = NDTLEAF(ldtentry->namlen); in dtSplitPage()
1529 n = NDTLEAF_LEGACY(ldtentry-> in dtSplitPage()
1534 idtentry = (struct idtentry *) & sp->slot[si]; in dtSplitPage()
1535 n = NDTINTERNAL(idtentry->namlen); in dtSplitPage()
1561 rlv = & rdtlck->lv[rdtlck->index]; in dtSplitPage()
1562 rlv->offset = 0; in dtSplitPage()
1563 rlv->length = 5; in dtSplitPage()
1564 rdtlck->index++; in dtSplitPage()
1568 sp->header.nextindex = nxt; in dtSplitPage()
1573 fsi = rp->header.freelist; in dtSplitPage()
1574 f = &rp->slot[fsi]; in dtSplitPage()
1575 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitPage()
1576 f->next = fsi; in dtSplitPage()
1577 f->next = -1; in dtSplitPage()
1582 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitPage()
1587 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitPage()
1588 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitPage()
1589 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitPage()
1601 dtInsertEntry(sp, skip, split->key, split->data, &sdtlck); in dtSplitPage()
1604 if (sdtlck->index >= sdtlck->maxcnt) in dtSplitPage()
1606 slv = & sdtlck->lv[sdtlck->index]; in dtSplitPage()
1608 slv->offset = sp->header.stblindex + n; in dtSplitPage()
1609 slv->length = in dtSplitPage()
1610 ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1; in dtSplitPage()
1611 sdtlck->index++; in dtSplitPage()
1618 skip -= nxt; in dtSplitPage()
1621 dtInsertEntry(rp, skip, split->key, split->data, &rdtlck); in dtSplitPage()
1639 * return: 0 - success;
1640 * errno - failure;
1646 struct super_block *sb = ip->i_sb; in dtExtendPage()
1648 struct metapage *smp, *pmp, *mp; in dtExtendPage() local
1669 smp = split->mp; in dtExtendPage()
1670 sp = DT_PAGE(ip, smp); in dtExtendPage()
1674 DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc); in dtExtendPage()
1681 pxdlist = split->pxdlist; in dtExtendPage()
1682 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtExtendPage()
1683 pxdlist->npxd++; in dtExtendPage()
1686 tpxd = &sp->header.self; in dtExtendPage()
1688 /* in-place extension */ in dtExtendPage()
1698 pxdlock = (struct pxd_lock *) & tlck->lock; in dtExtendPage()
1699 pxdlock->flag = mlckFREEPXD; in dtExtendPage()
1700 pxdlock->pxd = sp->header.self; in dtExtendPage()
1701 pxdlock->index = 1; in dtExtendPage()
1711 for (n = 0; n < sp->header.nextindex; n++) { in dtExtendPage()
1713 (struct ldtentry *) & sp->slot[stbl[n]]; in dtExtendPage()
1715 le32_to_cpu(ldtentry->index), in dtExtendPage()
1726 sp->header.self = *pxd; in dtExtendPage()
1728 jfs_info("dtExtendPage: ip:0x%p smp:0x%p sp:0x%p", ip, smp, sp); in dtExtendPage()
1730 BT_MARK_DIRTY(smp, ip); in dtExtendPage()
1734 tlck = txLock(tid, ip, smp, tlckDTREE | type); in dtExtendPage()
1735 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1736 lv = & dtlck->lv[0]; in dtExtendPage()
1740 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtExtendPage()
1745 oldstblindex = sp->header.stblindex; in dtExtendPage()
1746 oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE; in dtExtendPage()
1747 newstblindex = sp->header.maxslot; in dtExtendPage()
1750 memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex], in dtExtendPage()
1751 sp->header.nextindex); in dtExtendPage()
1754 * in-line extension: linelock old area of extended page in dtExtendPage()
1758 lv->offset = 0; in dtExtendPage()
1759 lv->length = 1; in dtExtendPage()
1760 dtlck->index++; in dtExtendPage()
1764 lv->offset = newstblindex; in dtExtendPage()
1765 lv->length = newstblsize; in dtExtendPage()
1771 lv->offset = 0; in dtExtendPage()
1772 lv->length = sp->header.maxslot + newstblsize; in dtExtendPage()
1775 dtlck->index++; in dtExtendPage()
1777 sp->header.maxslot = n; in dtExtendPage()
1778 sp->header.stblindex = newstblindex; in dtExtendPage()
1779 /* sp->header.nextindex remains the same */ in dtExtendPage()
1785 f = &sp->slot[fsi]; in dtExtendPage()
1786 last = sp->header.freelist; in dtExtendPage()
1788 f->next = last; in dtExtendPage()
1791 sp->header.freelist = last; in dtExtendPage()
1792 sp->header.freecnt += oldstblsize; in dtExtendPage()
1799 f = &sp->slot[fsi]; in dtExtendPage()
1800 for (fsi++; fsi < sp->header.maxslot; f++, fsi++) in dtExtendPage()
1801 f->next = fsi; in dtExtendPage()
1802 f->next = -1; in dtExtendPage()
1805 fsi = sp->header.freelist; in dtExtendPage()
1806 if (fsi == -1) in dtExtendPage()
1807 sp->header.freelist = n; in dtExtendPage()
1810 f = &sp->slot[fsi]; in dtExtendPage()
1811 fsi = f->next; in dtExtendPage()
1812 } while (fsi != -1); in dtExtendPage()
1814 f->next = n; in dtExtendPage()
1817 sp->header.freecnt += sp->header.maxslot - n; in dtExtendPage()
1822 dtInsertEntry(sp, split->index, split->key, split->data, &dtlck); in dtExtendPage()
1829 n = sp->header.maxslot >> 2; in dtExtendPage()
1830 if (sp->header.freelist < n) in dtExtendPage()
1841 dtlck = (struct dt_lock *) & tlck->lock; in dtExtendPage()
1842 lv = & dtlck->lv[dtlck->index]; in dtExtendPage()
1844 /* linelock parent entry - 1st slot */ in dtExtendPage()
1845 lv->offset = 1; in dtExtendPage()
1846 lv->length = 1; in dtExtendPage()
1847 dtlck->index++; in dtExtendPage()
1850 tpxd = (pxd_t *) & pp->slot[1]; in dtExtendPage()
1866 * since root page << non-root page, and
1872 * return: 0 - success;
1873 * errno - failure;
1879 struct super_block *sb = ip->i_sb; in dtSplitRoot()
1880 struct metapage *smp; in dtSplitRoot() local
1900 smp = split->mp; in dtSplitRoot()
1901 sp = &JFS_IP(ip)->i_dtroot; in dtSplitRoot()
1909 pxdlist = split->pxdlist; in dtSplitRoot()
1910 pxd = &pxdlist->pxd[pxdlist->npxd]; in dtSplitRoot()
1911 pxdlist->npxd++; in dtSplitRoot()
1914 xsize = xlen << JFS_SBI(sb)->l2bsize; in dtSplitRoot()
1917 return -EIO; in dtSplitRoot()
1919 rp = rmp->data; in dtSplitRoot()
1933 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
1935 rp->header.flag = in dtSplitRoot()
1936 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; in dtSplitRoot()
1937 rp->header.self = *pxd; in dtSplitRoot()
1940 rp->header.next = 0; in dtSplitRoot()
1941 rp->header.prev = 0; in dtSplitRoot()
1944 * move in-line root page into new right page extent in dtSplitRoot()
1947 ASSERT(dtlck->index == 0); in dtSplitRoot()
1948 lv = & dtlck->lv[0]; in dtSplitRoot()
1949 lv->offset = 0; in dtSplitRoot()
1950 lv->length = 10; /* 1 + 8 + 1 */ in dtSplitRoot()
1951 dtlck->index++; in dtSplitRoot()
1954 rp->header.maxslot = n; in dtSplitRoot()
1958 rp->header.stblindex = DTROOTMAXSLOT; in dtSplitRoot()
1959 stbl = (s8 *) & rp->slot[DTROOTMAXSLOT]; in dtSplitRoot()
1960 memcpy(stbl, sp->header.stbl, sp->header.nextindex); in dtSplitRoot()
1961 rp->header.nextindex = sp->header.nextindex; in dtSplitRoot()
1964 memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE); in dtSplitRoot()
1971 f = &rp->slot[fsi]; in dtSplitRoot()
1972 for (fsi++; fsi < rp->header.maxslot; f++, fsi++) in dtSplitRoot()
1973 f->next = fsi; in dtSplitRoot()
1974 f->next = -1; in dtSplitRoot()
1977 fsi = sp->header.freelist; in dtSplitRoot()
1978 if (fsi == -1) in dtSplitRoot()
1979 rp->header.freelist = n; in dtSplitRoot()
1981 rp->header.freelist = fsi; in dtSplitRoot()
1984 f = &rp->slot[fsi]; in dtSplitRoot()
1985 fsi = f->next; in dtSplitRoot()
1986 } while (fsi != -1); in dtSplitRoot()
1988 f->next = n; in dtSplitRoot()
1991 rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n; in dtSplitRoot()
1996 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) { in dtSplitRoot()
2002 for (n = 0; n < rp->header.nextindex; n++) { in dtSplitRoot()
2003 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]]; in dtSplitRoot()
2004 modify_index(tid, ip, le32_to_cpu(ldtentry->index), in dtSplitRoot()
2014 dtInsertEntry(rp, split->index, split->key, split->data, &dtlck); in dtSplitRoot()
2019 * set the 1st entry offset to 0, which force the left-most key in dtSplitRoot()
2022 * The btree comparison code guarantees that the left-most key on any in dtSplitRoot()
2025 BT_MARK_DIRTY(smp, ip); in dtSplitRoot()
2027 * acquire a transaction lock on the root page (in-memory inode) in dtSplitRoot()
2029 tlck = txLock(tid, ip, smp, tlckDTREE | tlckNEW | tlckBTROOT); in dtSplitRoot()
2030 dtlck = (struct dt_lock *) & tlck->lock; in dtSplitRoot()
2033 ASSERT(dtlck->index == 0); in dtSplitRoot()
2034 lv = & dtlck->lv[0]; in dtSplitRoot()
2035 lv->offset = 0; in dtSplitRoot()
2036 lv->length = DTROOTMAXSLOT; in dtSplitRoot()
2037 dtlck->index++; in dtSplitRoot()
2040 if (sp->header.flag & BT_LEAF) { in dtSplitRoot()
2041 sp->header.flag &= ~BT_LEAF; in dtSplitRoot()
2042 sp->header.flag |= BT_INTERNAL; in dtSplitRoot()
2046 s = (struct idtentry *) & sp->slot[DTENTRYSTART]; in dtSplitRoot()
2049 s->next = -1; in dtSplitRoot()
2050 s->namlen = 0; in dtSplitRoot()
2052 stbl = sp->header.stbl; in dtSplitRoot()
2054 sp->header.nextindex = 1; in dtSplitRoot()
2058 f = &sp->slot[fsi]; in dtSplitRoot()
2062 f->next = fsi; in dtSplitRoot()
2063 f->next = -1; in dtSplitRoot()
2065 sp->header.freelist = DTENTRYSTART + 1; in dtSplitRoot()
2066 sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1); in dtSplitRoot()
2120 ldtentry = (struct ldtentry *) & p->slot[stbl[index]]; in dtDelete()
2121 table_index = le32_to_cpu(ldtentry->index); in dtDelete()
2122 if (index == (p->header.nextindex - 1)) { in dtDelete()
2126 if ((p->header.flag & BT_ROOT) in dtDelete()
2127 || (p->header.next == 0)) in dtDelete()
2128 next_index = -1; in dtDelete()
2131 DT_GETPAGE(ip, le64_to_cpu(p->header.next), in dtDelete()
2134 next_index = -1; in dtDelete()
2138 (struct ldtentry *) & np-> in dtDelete()
2141 le32_to_cpu(ldtentry->index); in dtDelete()
2147 (struct ldtentry *) & p->slot[stbl[index + 1]]; in dtDelete()
2148 next_index = le32_to_cpu(ldtentry->index); in dtDelete()
2155 if (p->header.nextindex == 1) { in dtDelete()
2170 dtlck = (struct dt_lock *) & tlck->lock; in dtDelete()
2173 * Do not assume that dtlck->index will be zero. During a in dtDelete()
2179 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2181 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2182 lv->offset = 0; in dtDelete()
2183 lv->length = 1; in dtDelete()
2184 dtlck->index++; in dtDelete()
2186 /* linelock stbl of non-root leaf page */ in dtDelete()
2187 if (!(p->header.flag & BT_ROOT)) { in dtDelete()
2188 if (dtlck->index >= dtlck->maxcnt) in dtDelete()
2190 lv = & dtlck->lv[dtlck->index]; in dtDelete()
2192 lv->offset = p->header.stblindex + i; in dtDelete()
2193 lv->length = in dtDelete()
2194 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDelete()
2196 dtlck->index++; in dtDelete()
2205 if (DO_INDEX(ip) && index < p->header.nextindex) { in dtDelete()
2210 for (i = index; i < p->header.nextindex; i++) { in dtDelete()
2212 (struct ldtentry *) & p->slot[stbl[i]]; in dtDelete()
2214 le32_to_cpu(ldtentry->index), in dtDelete()
2270 * free the non-root leaf page in dtDeleteUp()
2280 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2281 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2282 pxdlock->pxd = fp->header.self; in dtDeleteUp()
2283 pxdlock->index = 1; in dtDeleteUp()
2291 xlen = lengthPXD(&fp->header.self); in dtDeleteUp()
2309 DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); in dtDeleteUp()
2316 index = parent->index; in dtDeleteUp()
2321 nextindex = p->header.nextindex; in dtDeleteUp()
2332 if (p->header.flag & BT_ROOT) { in dtDeleteUp()
2356 pxdlock = (struct pxd_lock *) & tlck->lock; in dtDeleteUp()
2357 pxdlock->flag = mlckFREEPXD; in dtDeleteUp()
2358 pxdlock->pxd = p->header.self; in dtDeleteUp()
2359 pxdlock->index = 1; in dtDeleteUp()
2367 xlen = lengthPXD(&p->header.self); in dtDeleteUp()
2392 dtlck = (struct dt_lock *) & tlck->lock; in dtDeleteUp()
2395 if (dtlck->index >= dtlck->maxcnt) in dtDeleteUp()
2397 lv = & dtlck->lv[dtlck->index]; in dtDeleteUp()
2398 lv->offset = 0; in dtDeleteUp()
2399 lv->length = 1; in dtDeleteUp()
2400 dtlck->index++; in dtDeleteUp()
2402 /* linelock stbl of non-root leaf page */ in dtDeleteUp()
2403 if (!(p->header.flag & BT_ROOT)) { in dtDeleteUp()
2404 if (dtlck->index < dtlck->maxcnt) in dtDeleteUp()
2408 lv = & dtlck->lv[0]; in dtDeleteUp()
2411 lv->offset = p->header.stblindex + i; in dtDeleteUp()
2412 lv->length = in dtDeleteUp()
2413 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - in dtDeleteUp()
2415 dtlck->index++; in dtDeleteUp()
2423 ((p->header.flag & BT_ROOT) || p->header.prev == 0)) in dtDeleteUp()
2434 ip->i_size -= PSIZE; in dtDeleteUp()
2498 if (p->header.next) { in dtRelocate()
2499 nextbn = le64_to_cpu(p->header.next); in dtRelocate()
2509 if (p->header.prev) { in dtRelocate()
2510 prevbn = le64_to_cpu(p->header.prev); in dtRelocate()
2528 dtlck = (struct dt_lock *) & tlck->lock; in dtRelocate()
2530 ASSERT(dtlck->index == 0); in dtRelocate()
2531 lv = & dtlck->lv[0]; in dtRelocate()
2532 lv->offset = 0; in dtRelocate()
2533 lv->length = 1; in dtRelocate()
2534 dtlck->index++; in dtRelocate()
2536 lp->header.next = cpu_to_le64(nxaddr); in dtRelocate()
2542 dtlck = (struct dt_lock *) & tlck->lock; in dtRelocate()
2544 ASSERT(dtlck->index == 0); in dtRelocate()
2545 lv = & dtlck->lv[0]; in dtRelocate()
2546 lv->offset = 0; in dtRelocate()
2547 lv->length = 1; in dtRelocate()
2548 dtlck->index++; in dtRelocate()
2550 rp->header.prev = cpu_to_le64(nxaddr); in dtRelocate()
2564 dtlck = (struct dt_lock *) & tlck->lock; in dtRelocate()
2566 ASSERT(dtlck->index == 0); in dtRelocate()
2567 lv = & dtlck->lv[0]; in dtRelocate()
2570 pxd = &p->header.self; in dtRelocate()
2576 lv->offset = 0; in dtRelocate()
2577 lv->length = p->header.maxslot; in dtRelocate()
2578 dtlck->index++; in dtRelocate()
2581 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize; in dtRelocate()
2601 pxdlock = (struct pxd_lock *) & tlck->lock; in dtRelocate()
2602 pxdlock->flag = mlckFREEPXD; in dtRelocate()
2603 PXDaddress(&pxdlock->pxd, oxaddr); in dtRelocate()
2604 PXDlength(&pxdlock->pxd, xlen); in dtRelocate()
2605 pxdlock->index = 1; in dtRelocate()
2615 dtlck = (struct dt_lock *) & tlck->lock; in dtRelocate()
2616 lv = & dtlck->lv[dtlck->index]; in dtRelocate()
2620 pxd = (pxd_t *) & pp->slot[stbl[index]]; in dtRelocate()
2622 lv->offset = stbl[index]; in dtRelocate()
2623 lv->length = 1; in dtRelocate()
2624 dtlck->index++; in dtRelocate()
2650 int psize = 288; /* initial in-line directory */ in dtSearchNode()
2672 if (p->header.flag & BT_ROOT) { in dtSearchNode()
2675 } else if (addressPXD(&p->header.self) == lmxaddr) in dtSearchNode()
2681 if (p->header.flag & BT_LEAF) { in dtSearchNode()
2683 return -ESTALE; in dtSearchNode()
2688 pxd = (pxd_t *) & p->slot[stbl[0]]; in dtSearchNode()
2692 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize; in dtSearchNode()
2702 for (i = 0; i < p->header.nextindex; i++) { in dtSearchNode()
2703 pxd = (pxd_t *) & p->slot[stbl[i]]; in dtSearchNode()
2708 btsp = btstack->top; in dtSearchNode()
2709 btsp->bn = bn; in dtSearchNode()
2710 btsp->index = i; in dtSearchNode()
2711 btsp->mp = mp; in dtSearchNode()
2718 if (p->header.next) in dtSearchNode()
2719 bn = le64_to_cpu(p->header.next); in dtSearchNode()
2722 return -ESTALE; in dtSearchNode()
2757 nextbn = le64_to_cpu(p->header.next); in dtRelink()
2758 prevbn = le64_to_cpu(p->header.prev); in dtRelink()
2775 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2778 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2780 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2781 lv->offset = 0; in dtRelink()
2782 lv->length = 1; in dtRelink()
2783 dtlck->index++; in dtRelink()
2785 p->header.prev = cpu_to_le64(prevbn); in dtRelink()
2804 dtlck = (struct dt_lock *) & tlck->lock; in dtRelink()
2807 if (dtlck->index >= dtlck->maxcnt) in dtRelink()
2809 lv = & dtlck->lv[dtlck->index]; in dtRelink()
2810 lv->offset = 0; in dtRelink()
2811 lv->length = 1; in dtRelink()
2812 dtlck->index++; in dtRelink()
2814 p->header.next = cpu_to_le64(nextbn); in dtRelink()
2839 * If this was previously an non-empty directory, we need to remove in dtInitRoot()
2851 xflag_save = tblk->xflag; in dtInitRoot()
2852 tblk->xflag = 0; in dtInitRoot()
2864 tblk->xflag = xflag_save; in dtInitRoot()
2866 ip->i_size = 1; in dtInitRoot()
2868 jfs_ip->next_index = 2; in dtInitRoot()
2870 ip->i_size = IDATASIZE; in dtInitRoot()
2877 tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag, in dtInitRoot()
2879 dtlck = (struct dt_lock *) & tlck->lock; in dtInitRoot()
2882 ASSERT(dtlck->index == 0); in dtInitRoot()
2883 lv = & dtlck->lv[0]; in dtInitRoot()
2884 lv->offset = 0; in dtInitRoot()
2885 lv->length = DTROOTMAXSLOT; in dtInitRoot()
2886 dtlck->index++; in dtInitRoot()
2888 p = &jfs_ip->i_dtroot; in dtInitRoot()
2890 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; in dtInitRoot()
2892 p->header.nextindex = 0; in dtInitRoot()
2896 f = &p->slot[fsi]; in dtInitRoot()
2900 f->next = fsi; in dtInitRoot()
2901 f->next = -1; in dtInitRoot()
2903 p->header.freelist = 1; in dtInitRoot()
2904 p->header.freecnt = 8; in dtInitRoot()
2907 p->header.idotdot = cpu_to_le32(idotdot); in dtInitRoot()
2933 tid = txBegin(inode->i_sb, 0); in add_missing_indices()
2943 ASSERT(p->header.flag & BT_LEAF); in add_missing_indices()
2947 tlck->type |= tlckBTROOT; in add_missing_indices()
2949 dtlck = (struct dt_lock *) &tlck->lock; in add_missing_indices()
2952 for (i = 0; i < p->header.nextindex; i++) { in add_missing_indices()
2953 d = (struct ldtentry *) &p->slot[stbl[i]]; in add_missing_indices()
2954 index = le32_to_cpu(d->index); in add_missing_indices()
2955 if ((index < 2) || (index >= JFS_IP(inode)->next_index)) { in add_missing_indices()
2956 d->index = cpu_to_le32(add_index(tid, inode, bn, i)); in add_missing_indices()
2957 if (dtlck->index >= dtlck->maxcnt) in add_missing_indices()
2959 lv = &dtlck->lv[dtlck->index]; in add_missing_indices()
2960 lv->offset = stbl[i]; in add_missing_indices()
2961 lv->length = 1; in add_missing_indices()
2962 dtlck->index++; in add_missing_indices()
2984 * function to determine next variable-sized jfs_dirent in buffer
2990 ((sizeof (struct jfs_dirent) + dirent->name_len + 1 + in next_jfs_dirent()
2991 sizeof (loff_t) - 1) & in next_jfs_dirent()
2992 ~(sizeof (loff_t) - 1))); in next_jfs_dirent()
2999 * from the specified entry offset
3003 * return: offset = (pn, index) of start entry
3009 struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab; in jfs_readdir()
3037 if (ctx->pos == DIREND) in jfs_readdir()
3045 * -1 = End of directory in jfs_readdir()
3049 dir_index = (u32) ctx->pos; in jfs_readdir()
3057 dir_index--; in jfs_readdir()
3063 (dir_index >= JFS_IP(ip)->next_index)) { in jfs_readdir()
3065 ctx->pos = DIREND; in jfs_readdir()
3071 ctx->pos = DIREND; in jfs_readdir()
3075 if (loop_count++ > JFS_IP(ip)->next_index) { in jfs_readdir()
3077 ctx->pos = DIREND; in jfs_readdir()
3081 if (dir_index == -1) { in jfs_readdir()
3082 ctx->pos = DIREND; in jfs_readdir()
3091 ctx->pos = DIREND; in jfs_readdir()
3094 if (p->header.flag & BT_INTERNAL) { in jfs_readdir()
3097 ctx->pos = DIREND; in jfs_readdir()
3105 ctx->pos = 1; in jfs_readdir()
3106 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
3112 ctx->pos = 2; in jfs_readdir()
3117 * Find first entry of left-most leaf in jfs_readdir()
3120 ctx->pos = DIREND; in jfs_readdir()
3131 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6 in jfs_readdir()
3135 * pn > 0: Real entries, pn=1 -> leftmost page in jfs_readdir()
3136 * pn = index = -1: No more entries in jfs_readdir()
3138 dtpos = ctx->pos; in jfs_readdir()
3141 ctx->pos = 1; in jfs_readdir()
3142 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR)) in jfs_readdir()
3144 dtoffset->index = 2; in jfs_readdir()
3145 ctx->pos = dtpos; in jfs_readdir()
3148 if (dtoffset->pn == 0) { in jfs_readdir()
3149 if (dtoffset->index == 2) { in jfs_readdir()
3154 jfs_err("jfs_readdir called with invalid offset!"); in jfs_readdir()
3156 dtoffset->pn = 1; in jfs_readdir()
3157 dtoffset->index = 0; in jfs_readdir()
3158 ctx->pos = dtpos; in jfs_readdir()
3162 ctx->pos = DIREND; in jfs_readdir()
3166 if ((rc = dtReadNext(ip, &ctx->pos, &btstack))) { in jfs_readdir()
3169 ctx->pos = DIREND; in jfs_readdir()
3175 /* offset beyond directory eof ? */ in jfs_readdir()
3177 ctx->pos = DIREND; in jfs_readdir()
3186 ctx->pos = DIREND; in jfs_readdir()
3187 return -ENOMEM; in jfs_readdir()
3197 for (i = index; i < p->header.nextindex; i++) { in jfs_readdir()
3198 d = (struct ldtentry *) & p->slot[stbl[i]]; in jfs_readdir()
3200 if (((long) jfs_dirent + d->namlen + 1) > in jfs_readdir()
3208 d_namleft = d->namlen; in jfs_readdir()
3209 name_ptr = jfs_dirent->name; in jfs_readdir()
3210 jfs_dirent->ino = le32_to_cpu(d->inumber); in jfs_readdir()
3214 jfs_dirent->position = le32_to_cpu(d->index); in jfs_readdir()
3216 * d->index should always be valid, but it in jfs_readdir()
3222 if ((jfs_dirent->position < 2) || in jfs_readdir()
3223 (jfs_dirent->position >= in jfs_readdir()
3224 JFS_IP(ip)->next_index)) { in jfs_readdir()
3237 jfs_dirent->position = unique_pos++; in jfs_readdir()
3244 jfs_dirent->position++; in jfs_readdir()
3246 jfs_dirent->position = dtpos; in jfs_readdir()
3251 outlen = jfs_strfromUCS_le(name_ptr, d->name, len, in jfs_readdir()
3253 jfs_dirent->name_len = outlen; in jfs_readdir()
3256 next = d->next; in jfs_readdir()
3258 t = (struct dtslot *) & p->slot[next]; in jfs_readdir()
3260 d_namleft -= len; in jfs_readdir()
3263 jfs_error(ip->i_sb, in jfs_readdir()
3265 (long)ip->i_ino, in jfs_readdir()
3271 outlen = jfs_strfromUCS_le(name_ptr, t->name, in jfs_readdir()
3273 jfs_dirent->name_len += outlen; in jfs_readdir()
3275 next = t->next; in jfs_readdir()
3282 dtoffset->index++; in jfs_readdir()
3287 if (p->header.flag & BT_ROOT) in jfs_readdir()
3290 bn = le64_to_cpu(p->header.next); in jfs_readdir()
3292 /* update offset (pn:index) for new page */ in jfs_readdir()
3294 dtoffset->pn++; in jfs_readdir()
3295 dtoffset->index = 0; in jfs_readdir()
3305 while (jfs_dirents--) { in jfs_readdir()
3306 ctx->pos = jfs_dirent->position; in jfs_readdir()
3307 if (!dir_emit(ctx, jfs_dirent->name, in jfs_readdir()
3308 jfs_dirent->name_len, in jfs_readdir()
3309 jfs_dirent->ino, DT_UNKNOWN)) in jfs_readdir()
3320 ctx->pos = DIREND; in jfs_readdir()
3347 int psize = 288; /* initial in-line directory */ in dtReadFirst()
3369 if (p->header.flag & BT_LEAF) { in dtReadFirst()
3371 btsp = btstack->top; in dtReadFirst()
3372 btsp->bn = bn; in dtReadFirst()
3373 btsp->index = 0; in dtReadFirst()
3374 btsp->mp = mp; in dtReadFirst()
3384 jfs_error(ip->i_sb, "btstack overrun\n"); in dtReadFirst()
3386 return -EIO; in dtReadFirst()
3393 xd = (pxd_t *) & p->slot[stbl[0]]; in dtReadFirst()
3397 psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize; in dtReadFirst()
3408 * function: get the page of the specified offset (pn:index)
3410 * return: if (offset > eof), bn = -1;
3415 static int dtReadNext(struct inode *ip, loff_t * offset, in dtReadNext() argument
3423 } *dtoffset = (struct dtoffset *) offset; in dtReadNext()
3440 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index); in dtReadNext()
3442 /* get the start offset (pn:index) */ in dtReadNext()
3443 pn = dtoffset->pn - 1; /* Now pn = 0 represents leftmost leaf */ in dtReadNext()
3444 index = dtoffset->index; in dtReadNext()
3448 /* offset beyond eof ? */ in dtReadNext()
3449 if (index < p->header.nextindex) in dtReadNext()
3452 if (p->header.flag & BT_ROOT) { in dtReadNext()
3453 bn = -1; in dtReadNext()
3458 dtoffset->pn++; in dtReadNext()
3459 dtoffset->index = index = 0; in dtReadNext()
3463 /* start at non-leftmost page: scan parent pages for large pn */ in dtReadNext()
3464 if (p->header.flag & BT_ROOT) { in dtReadNext()
3465 bn = -1; in dtReadNext()
3475 bn = le64_to_cpu(p->header.next); in dtReadNext()
3480 /* offset beyond eof ? */ in dtReadNext()
3482 bn = -1; in dtReadNext()
3496 btsp = btstack->top; in dtReadNext()
3497 parent = btsp - 1; in dtReadNext()
3498 bn = parent->bn; in dtReadNext()
3504 while (pn >= p->header.nextindex) { in dtReadNext()
3505 pn -= p->header.nextindex; in dtReadNext()
3508 bn = le64_to_cpu(p->header.next); in dtReadNext()
3513 /* offset beyond eof ? */ in dtReadNext()
3515 bn = -1; in dtReadNext()
3525 parent->bn = bn; in dtReadNext()
3530 xd = (pxd_t *) & p->slot[stbl[pn]]; in dtReadNext()
3548 if (index >= p->header.nextindex) { in dtReadNext()
3549 bn = le64_to_cpu(p->header.next); in dtReadNext()
3554 /* offset beyond eof ? */ in dtReadNext()
3556 bn = -1; in dtReadNext()
3566 dtoffset->pn++; in dtReadNext()
3567 dtoffset->index = 0; in dtReadNext()
3572 btsp = btstack->top; in dtReadNext()
3573 btsp->bn = bn; in dtReadNext()
3574 btsp->index = dtoffset->index; in dtReadNext()
3575 btsp->mp = mp; in dtReadNext()
3602 * force the left-most key on internal pages, at any level of in dtCompare()
3610 * it descends to child of the entry anyway - in dtCompare()
3613 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in dtCompare()
3617 kname = key->name; in dtCompare()
3618 klen = key->namlen; in dtCompare()
3620 ih = (struct idtentry *) & p->slot[si]; in dtCompare()
3621 si = ih->next; in dtCompare()
3622 name = ih->name; in dtCompare()
3623 namlen = ih->namlen; in dtCompare()
3631 klen -= len; in dtCompare()
3632 namlen -= len; in dtCompare()
3638 t = (struct dtslot *) & p->slot[si]; in dtCompare()
3641 name = t->name; in dtCompare()
3645 klen -= len; in dtCompare()
3646 namlen -= len; in dtCompare()
3648 si = t->next; in dtCompare()
3651 return (klen - namlen); in dtCompare()
3681 * force the left-most key on internal pages, at any level of in ciCompare()
3689 * it descends to child of the entry anyway - in ciCompare()
3692 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF)) in ciCompare()
3696 kname = key->name; in ciCompare()
3697 klen = key->namlen; in ciCompare()
3702 if (p->header.flag & BT_LEAF) { in ciCompare()
3703 lh = (struct ldtentry *) & p->slot[si]; in ciCompare()
3704 si = lh->next; in ciCompare()
3705 name = lh->name; in ciCompare()
3706 namlen = lh->namlen; in ciCompare()
3716 ih = (struct idtentry *) & p->slot[si]; in ciCompare()
3717 si = ih->next; in ciCompare()
3718 name = ih->name; in ciCompare()
3719 namlen = ih->namlen; in ciCompare()
3726 /* only uppercase if case-insensitive support is on */ in ciCompare()
3731 if ((rc = *kname - x)) in ciCompare()
3735 klen -= len; in ciCompare()
3736 namlen -= len; in ciCompare()
3741 t = (struct dtslot *) & p->slot[si]; in ciCompare()
3744 name = t->name; in ciCompare()
3746 /* only uppercase if case-insensitive support is on */ in ciCompare()
3752 if ((rc = *kname - x)) in ciCompare()
3756 klen -= len; in ciCompare()
3757 namlen -= len; in ciCompare()
3758 si = t->next; in ciCompare()
3761 return (klen - namlen); in ciCompare()
3772 * return: non-zero on error
3786 return -ENOMEM; in ciGetLeafPrefixKey()
3792 return -ENOMEM; in ciGetLeafPrefixKey()
3811 kname = key->name; in ciGetLeafPrefixKey()
3814 namlen; pl++, pr++, namlen--, klen++, kname++) { in ciGetLeafPrefixKey()
3817 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3822 /* l->namlen <= r->namlen since l <= r */ in ciGetLeafPrefixKey()
3825 key->namlen = klen + 1; in ciGetLeafPrefixKey()
3826 } else /* l->namelen == r->namelen */ in ciGetLeafPrefixKey()
3827 key->namlen = klen; in ciGetLeafPrefixKey()
3857 if (p->header.flag & BT_LEAF) { in dtGetKey()
3858 lh = (struct ldtentry *) & p->slot[si]; in dtGetKey()
3859 si = lh->next; in dtGetKey()
3860 namlen = lh->namlen; in dtGetKey()
3861 name = lh->name; in dtGetKey()
3867 ih = (struct idtentry *) & p->slot[si]; in dtGetKey()
3868 si = ih->next; in dtGetKey()
3869 namlen = ih->namlen; in dtGetKey()
3870 name = ih->name; in dtGetKey()
3874 key->namlen = namlen; in dtGetKey()
3875 kname = key->name; in dtGetKey()
3887 t = &p->slot[si]; in dtGetKey()
3889 namlen -= len; in dtGetKey()
3891 UniStrncpy_from_le(kname, t->name, len); in dtGetKey()
3893 si = t->next; in dtGetKey()
3923 klen = key->namlen; in dtInsertEntry()
3924 kname = key->name; in dtInsertEntry()
3927 hsi = fsi = p->header.freelist; in dtInsertEntry()
3928 h = &p->slot[fsi]; in dtInsertEntry()
3929 p->header.freelist = h->next; in dtInsertEntry()
3930 --p->header.freecnt; in dtInsertEntry()
3933 if (dtlck->index >= dtlck->maxcnt) in dtInsertEntry()
3936 lv = & dtlck->lv[dtlck->index]; in dtInsertEntry()
3937 lv->offset = hsi; in dtInsertEntry()
3940 if (p->header.flag & BT_LEAF) { in dtInsertEntry()
3942 lh->next = h->next; in dtInsertEntry()
3943 lh->inumber = cpu_to_le32(data->leaf.ino); in dtInsertEntry()
3944 lh->namlen = klen; in dtInsertEntry()
3945 name = lh->name; in dtInsertEntry()
3946 if (data->leaf.ip) { in dtInsertEntry()
3948 if (!(p->header.flag & BT_ROOT)) in dtInsertEntry()
3949 bn = addressPXD(&p->header.self); in dtInsertEntry()
3950 lh->index = cpu_to_le32(add_index(data->leaf.tid, in dtInsertEntry()
3951 data->leaf.ip, in dtInsertEntry()
3957 ih->next = h->next; in dtInsertEntry()
3959 *xd = data->xd; in dtInsertEntry()
3960 ih->namlen = klen; in dtInsertEntry()
3961 name = ih->name; in dtInsertEntry()
3972 klen -= len; in dtInsertEntry()
3975 fsi = p->header.freelist; in dtInsertEntry()
3976 t = &p->slot[fsi]; in dtInsertEntry()
3977 p->header.freelist = t->next; in dtInsertEntry()
3978 --p->header.freecnt; in dtInsertEntry()
3983 lv->length = n; in dtInsertEntry()
3984 dtlck->index++; in dtInsertEntry()
3987 if (dtlck->index < dtlck->maxcnt) in dtInsertEntry()
3991 lv = & dtlck->lv[0]; in dtInsertEntry()
3994 lv->offset = fsi; in dtInsertEntry()
4000 UniStrncpy_to_le(t->name, kname, len); in dtInsertEntry()
4004 klen -= len; in dtInsertEntry()
4008 lv->length = n; in dtInsertEntry()
4009 dtlck->index++; in dtInsertEntry()
4016 if (p->header.flag & BT_LEAF) in dtInsertEntry()
4017 lh->next = -1; in dtInsertEntry()
4019 ih->next = -1; in dtInsertEntry()
4021 /* multi-segment entry */ in dtInsertEntry()
4022 t->next = -1; in dtInsertEntry()
4026 nextindex = p->header.nextindex; in dtInsertEntry()
4028 memmove(stbl + index + 1, stbl + index, nextindex - index); in dtInsertEntry()
4030 if ((p->header.flag & BT_LEAF) && data->leaf.ip) { in dtInsertEntry()
4039 lh = (struct ldtentry *) & (p->slot[stbl[n]]); in dtInsertEntry()
4040 modify_index(data->leaf.tid, data->leaf.ip, in dtInsertEntry()
4041 le32_to_cpu(lh->index), bn, n, in dtInsertEntry()
4052 ++p->header.nextindex; in dtInsertEntry()
4081 sstbl = (s8 *) & sp->slot[sp->header.stblindex]; in dtMoveEntry()
4082 dstbl = (s8 *) & dp->slot[dp->header.stblindex]; in dtMoveEntry()
4084 dsi = dp->header.freelist; /* first (whole page) free slot */ in dtMoveEntry()
4085 sfsi = sp->header.freelist; in dtMoveEntry()
4088 dlv = & ddtlck->lv[ddtlck->index]; in dtMoveEntry()
4089 dlv->offset = dsi; in dtMoveEntry()
4092 slv = & sdtlck->lv[sdtlck->index]; in dtMoveEntry()
4093 slv->offset = sstbl[si]; in dtMoveEntry()
4094 xssi = slv->offset - 1; in dtMoveEntry()
4100 for (di = 0; si < sp->header.nextindex; si++, di++) { in dtMoveEntry()
4107 slv->length = ns; in dtMoveEntry()
4108 sdtlck->index++; in dtMoveEntry()
4111 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
4115 slv = & sdtlck->lv[0]; in dtMoveEntry()
4118 slv->offset = ssi; in dtMoveEntry()
4126 h = d = &dp->slot[dsi]; in dtMoveEntry()
4129 s = &sp->slot[ssi]; in dtMoveEntry()
4130 if (sp->header.flag & BT_LEAF) { in dtMoveEntry()
4134 snamlen = slh->namlen; in dtMoveEntry()
4138 dlh->index = slh->index; /* little-endian */ in dtMoveEntry()
4144 next = slh->next; in dtMoveEntry()
4148 dlh->next = dsi; in dtMoveEntry()
4151 snamlen = sih->namlen; in dtMoveEntry()
4156 next = sih->next; in dtMoveEntry()
4159 dih->next = dsi; in dtMoveEntry()
4163 s->next = sfsi; in dtMoveEntry()
4164 s->cnt = 1; in dtMoveEntry()
4174 snamlen -= len; in dtMoveEntry()
4179 slv->length = ns; in dtMoveEntry()
4180 sdtlck->index++; in dtMoveEntry()
4183 if (sdtlck->index < sdtlck->maxcnt) in dtMoveEntry()
4189 slv = & sdtlck->lv[0]; in dtMoveEntry()
4192 slv->offset = ssi; in dtMoveEntry()
4197 s = &sp->slot[ssi]; in dtMoveEntry()
4203 UniStrncpy_le(d->name, s->name, len); in dtMoveEntry()
4210 d->next = dsi; in dtMoveEntry()
4213 next = s->next; in dtMoveEntry()
4214 s->next = sfsi; in dtMoveEntry()
4215 s->cnt = 1; in dtMoveEntry()
4218 snamlen -= len; in dtMoveEntry()
4224 if (dp->header.flag & BT_LEAF) in dtMoveEntry()
4225 dlh->next = -1; in dtMoveEntry()
4227 dih->next = -1; in dtMoveEntry()
4229 /* multi-segment entry */ in dtMoveEntry()
4230 d->next = -1; in dtMoveEntry()
4234 slv->length = ns; in dtMoveEntry()
4235 sdtlck->index++; in dtMoveEntry()
4238 dlv->length = nd; in dtMoveEntry()
4239 ddtlck->index++; in dtMoveEntry()
4243 sp->header.freelist = sfsi; in dtMoveEntry()
4244 sp->header.freecnt += nd; in dtMoveEntry()
4247 dp->header.nextindex = di; in dtMoveEntry()
4249 dp->header.freelist = dsi; in dtMoveEntry()
4250 dp->header.freecnt -= nd; in dtMoveEntry()
4280 if (dtlck->index >= dtlck->maxcnt) in dtDeleteEntry()
4282 lv = & dtlck->lv[dtlck->index]; in dtDeleteEntry()
4284 lv->offset = fsi; in dtDeleteEntry()
4287 t = &p->slot[fsi]; in dtDeleteEntry()
4288 if (p->header.flag & BT_LEAF) in dtDeleteEntry()
4289 si = ((struct ldtentry *) t)->next; in dtDeleteEntry()
4291 si = ((struct idtentry *) t)->next; in dtDeleteEntry()
4292 t->next = si; in dtDeleteEntry()
4293 t->cnt = 1; in dtDeleteEntry()
4303 lv->length = n; in dtDeleteEntry()
4304 dtlck->index++; in dtDeleteEntry()
4307 if (dtlck->index < dtlck->maxcnt) in dtDeleteEntry()
4311 lv = & dtlck->lv[0]; in dtDeleteEntry()
4314 lv->offset = si; in dtDeleteEntry()
4322 t = &p->slot[si]; in dtDeleteEntry()
4323 t->cnt = 1; in dtDeleteEntry()
4324 si = t->next; in dtDeleteEntry()
4328 lv->length = n; in dtDeleteEntry()
4329 dtlck->index++; in dtDeleteEntry()
4334 t->next = p->header.freelist; in dtDeleteEntry()
4335 p->header.freelist = fsi; in dtDeleteEntry()
4336 p->header.freecnt += freecnt; in dtDeleteEntry()
4341 si = p->header.nextindex; in dtDeleteEntry()
4342 if (fi < si - 1) in dtDeleteEntry()
4343 memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1); in dtDeleteEntry()
4345 p->header.nextindex--; in dtDeleteEntry()
4375 if (dtlck->index >= dtlck->maxcnt) in dtTruncateEntry()
4377 lv = & dtlck->lv[dtlck->index]; in dtTruncateEntry()
4379 lv->offset = tsi; in dtTruncateEntry()
4382 t = &p->slot[tsi]; in dtTruncateEntry()
4383 ASSERT(p->header.flag & BT_INTERNAL); in dtTruncateEntry()
4384 ((struct idtentry *) t)->namlen = 0; in dtTruncateEntry()
4385 si = ((struct idtentry *) t)->next; in dtTruncateEntry()
4386 ((struct idtentry *) t)->next = -1; in dtTruncateEntry()
4398 lv->length = n; in dtTruncateEntry()
4399 dtlck->index++; in dtTruncateEntry()
4402 if (dtlck->index < dtlck->maxcnt) in dtTruncateEntry()
4406 lv = & dtlck->lv[0]; in dtTruncateEntry()
4409 lv->offset = si; in dtTruncateEntry()
4417 t = &p->slot[si]; in dtTruncateEntry()
4418 t->cnt = 1; in dtTruncateEntry()
4419 si = t->next; in dtTruncateEntry()
4423 lv->length = n; in dtTruncateEntry()
4424 dtlck->index++; in dtTruncateEntry()
4431 t->next = p->header.freelist; in dtTruncateEntry()
4432 p->header.freelist = fsi; in dtTruncateEntry()
4433 p->header.freecnt += freecnt; in dtTruncateEntry()
4452 fsi = p->header.freelist; in dtLinelockFreelist()
4455 if (dtlck->index >= dtlck->maxcnt) in dtLinelockFreelist()
4457 lv = & dtlck->lv[dtlck->index]; in dtLinelockFreelist()
4459 lv->offset = fsi; in dtLinelockFreelist()
4464 t = &p->slot[fsi]; in dtLinelockFreelist()
4465 si = t->next; in dtLinelockFreelist()
4472 lv->length = n; in dtLinelockFreelist()
4473 dtlck->index++; in dtLinelockFreelist()
4476 if (dtlck->index < dtlck->maxcnt) in dtLinelockFreelist()
4480 lv = & dtlck->lv[0]; in dtLinelockFreelist()
4483 lv->offset = si; in dtLinelockFreelist()
4490 t = &p->slot[si]; in dtLinelockFreelist()
4491 si = t->next; in dtLinelockFreelist()
4495 lv->length = n; in dtLinelockFreelist()
4496 dtlck->index++; in dtLinelockFreelist()
4508 * tid - Transaction id
4509 * ip - Inode of parent directory
4510 * key - Name of entry to be modified
4511 * orig_ino - Original inode number expected in entry
4512 * new_ino - New inode number to put into entry
4513 * flag - JFS_RENAME
4516 * -ESTALE - If entry found does not match orig_ino passed in
4517 * -ENOENT - If no entry can be found to match key
4518 * 0 - If successfully modified entry
4552 dtlck = (struct dt_lock *) & tlck->lock; in dtModify()
4559 ASSERT(dtlck->index == 0); in dtModify()
4560 lv = & dtlck->lv[0]; in dtModify()
4561 lv->offset = entry_si; in dtModify()
4562 lv->length = 1; in dtModify()
4563 dtlck->index++; in dtModify()
4566 entry = (struct ldtentry *) & p->slot[entry_si]; in dtModify()
4569 entry->inumber = cpu_to_le32(new_ino); in dtModify()