Lines Matching +full:xlen +full:- +full:1
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) International Business Machines Corp., 2000-2005
6 * jfs_xtree.c: extent allocation descriptor B+-tree manager
30 * -1: k < start of extent
32 * 1: k > end_of_extent
37 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
38 ((K) < OFFSET64) ? -1 : 0;\
44 (XAD)->flag = (FLAG);\
58 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) || \
59 (le16_to_cpu((P)->header.nextindex) > \
60 le16_to_cpu((P)->header.maxentry)) || \
61 (le16_to_cpu((P)->header.maxentry) > \
63 jfs_error((IP)->i_sb, \
67 RC = -EIO; \
134 int xlen; in xtLookup() local
142 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >> in xtLookup()
143 JFS_SBI(ip->i_sb)->l2bsize; in xtLookup()
172 *plen = min(next - lstart, llen); in xtLookup()
179 xad = &p->xad[index]; in xtLookup()
181 xlen = lengthXAD(xad); in xtLookup()
182 xend = xoff + xlen; in xtLookup()
186 *pflag = xad->flag; in xtLookup()
187 *paddr = xaddr + (lstart - xoff); in xtLookup()
189 *plen = min(xend - lstart, llen); in xtLookup()
203 * ip - file object;
204 * xoff - extent offset;
205 * nextp - address of next extent (if any) for search miss
206 * cmpp - comparison result:
207 * btstack - traverse stack;
208 * flag - search process flag (XT_INSERT);
220 int cmp = 1; /* init for empty page */ in xtSearch()
235 btstack->nsplit = 0; in xtSearch()
266 if ((jfs_ip->btorder & BT_SEQUENTIAL) && in xtSearch()
267 (p->header.flag & BT_LEAF) && in xtSearch()
268 (index = jfs_ip->btindex) < in xtSearch()
269 le16_to_cpu(p->header.nextindex)) { in xtSearch()
270 xad = &p->xad[index]; in xtSearch()
285 le16_to_cpu(p->header.nextindex)) { in xtSearch()
297 *cmpp = 1; in xtSearch()
310 /* (index == p->header.nextindex); in xtSearch()
314 *cmpp = 1; in xtSearch()
326 if (p->header.nextindex == /* little-endian */ in xtSearch()
327 p->header.maxentry) in xtSearch()
331 btstack->nsplit = nsplit; in xtSearch()
335 btsp = btstack->top; in xtSearch()
336 btsp->bn = bn; in xtSearch()
337 btsp->index = index; in xtSearch()
338 btsp->mp = mp; in xtSearch()
341 jfs_ip->btindex = index; in xtSearch()
352 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART; in xtSearch()
357 for (base = XTENTRYSTART; lim; lim >>= 1) { in xtSearch()
358 index = base + (lim >> 1); in xtSearch()
360 XT_CMP(cmp, xoff, &p->xad[index], t64); in xtSearch()
365 /* search hit - leaf page: in xtSearch()
368 if (p->header.flag & BT_LEAF) { in xtSearch()
373 if (p->header.nextindex == in xtSearch()
374 p->header.maxentry) in xtSearch()
378 btstack->nsplit = nsplit; in xtSearch()
382 btsp = btstack->top; in xtSearch()
383 btsp->bn = bn; in xtSearch()
384 btsp->index = index; in xtSearch()
385 btsp->mp = mp; in xtSearch()
388 btindex = jfs_ip->btindex; in xtSearch()
390 index == btindex + 1) in xtSearch()
391 jfs_ip->btorder = BT_SEQUENTIAL; in xtSearch()
393 jfs_ip->btorder = BT_RANDOM; in xtSearch()
394 jfs_ip->btindex = index; in xtSearch()
398 /* search hit - internal page: in xtSearch()
401 if (index < le16_to_cpu(p->header.nextindex)-1) in xtSearch()
402 next = offsetXAD(&p->xad[index + 1]); in xtSearch()
407 base = index + 1; in xtSearch()
408 --lim; in xtSearch()
418 if (base < le16_to_cpu(p->header.nextindex)) in xtSearch()
419 next = offsetXAD(&p->xad[base]); in xtSearch()
421 * search miss - leaf page: in xtSearch()
426 if (p->header.flag & BT_LEAF) { in xtSearch()
431 if (p->header.nextindex == in xtSearch()
432 p->header.maxentry) in xtSearch()
436 btstack->nsplit = nsplit; in xtSearch()
440 btsp = btstack->top; in xtSearch()
441 btsp->bn = bn; in xtSearch()
442 btsp->index = base; in xtSearch()
443 btsp->mp = mp; in xtSearch()
446 btindex = jfs_ip->btindex; in xtSearch()
447 if (base == btindex || base == btindex + 1) in xtSearch()
448 jfs_ip->btorder = BT_SEQUENTIAL; in xtSearch()
450 jfs_ip->btorder = BT_RANDOM; in xtSearch()
451 jfs_ip->btindex = base; in xtSearch()
460 * search miss - non-leaf page: in xtSearch()
462 * if base is non-zero, decrement base by one to get the parent in xtSearch()
465 index = base ? base - 1 : base; in xtSearch()
472 if (p->header.nextindex == p->header.maxentry) in xtSearch()
479 jfs_error(ip->i_sb, "stack overrun!\n"); in xtSearch()
481 return -EIO; in xtSearch()
486 bn = addressXAD(&p->xad[index]); in xtSearch()
499 * tid - transaction id;
500 * ip - file object;
501 * xflag - extent flag (XAD_NOTRECORDED):
502 * xoff - extent offset;
503 * xlen - extent length;
504 * xaddrp - extent address pointer (in/out):
509 * flag -
514 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp, in xtInsert() argument
519 struct metapage *mp; /* meta-page buffer */ in xtInsert()
520 xtpage_t *p; /* base B+-tree index page */ in xtInsert()
531 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen); in xtInsert()
549 if ((cmp == 0) || (next && (xlen > next - xoff))) { in xtInsert()
550 rc = -EEXIST; in xtInsert()
561 xad = &p->xad[index - 1]; in xtInsert()
562 hint = addressXAD(xad) + lengthXAD(xad) - 1; in xtInsert()
565 if ((rc = dquot_alloc_block(ip, xlen))) in xtInsert()
567 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) { in xtInsert()
568 dquot_free_block(ip, xlen); in xtInsert()
584 nextindex = le16_to_cpu(p->header.nextindex); in xtInsert()
585 if (nextindex == le16_to_cpu(p->header.maxentry)) { in xtInsert()
590 split.len = xlen; in xtInsert()
596 dbFree(ip, xaddr, (s64) xlen); in xtInsert()
597 dquot_free_block(ip, xlen); in xtInsert()
618 memmove(&p->xad[index + 1], &p->xad[index], in xtInsert()
619 (nextindex - index) * sizeof(xad_t)); in xtInsert()
622 xad = &p->xad[index]; in xtInsert()
623 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); in xtInsert()
626 le16_add_cpu(&p->header.nextindex, 1); in xtInsert()
631 xtlck = (struct xtlock *) & tlck->lock; in xtInsert()
632 xtlck->lwm.offset = in xtInsert()
633 (xtlck->lwm.offset) ? min(index, in xtInsert()
634 (int)xtlck->lwm.offset) : index; in xtInsert()
635 xtlck->lwm.length = in xtInsert()
636 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; in xtInsert()
656 * tid - transaction id;
657 * ip - file object;
658 * split - entry parameter descriptor;
659 * btstack - traverse stack from xtSearch()
680 int xlen; in xtSplitUp() local
687 smp = split->mp; in xtSplitUp()
691 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) && in xtSplitUp()
692 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) && in xtSplitUp()
693 (JFS_IP(ip)->mode2 & INLINEEA)) { in xtSplitUp()
694 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT); in xtSplitUp()
695 JFS_IP(ip)->mode2 &= ~INLINEEA; in xtSplitUp()
705 skip = split->index; in xtSplitUp()
706 nextindex = le16_to_cpu(sp->header.nextindex); in xtSplitUp()
708 memmove(&sp->xad[skip + 1], &sp->xad[skip], in xtSplitUp()
709 (nextindex - skip) * sizeof(xad_t)); in xtSplitUp()
712 xad = &sp->xad[skip]; in xtSplitUp()
713 XT_PUTENTRY(xad, split->flag, split->off, split->len, in xtSplitUp()
714 split->addr); in xtSplitUp()
717 le16_add_cpu(&sp->header.nextindex, 1); in xtSplitUp()
722 xtlck = (struct xtlock *) & tlck->lock; in xtSplitUp()
723 xtlck->lwm.offset = (xtlck->lwm.offset) ? in xtSplitUp()
724 min(skip, (int)xtlck->lwm.offset) : skip; in xtSplitUp()
725 xtlck->lwm.length = in xtSplitUp()
726 le16_to_cpu(sp->header.nextindex) - in xtSplitUp()
727 xtlck->lwm.offset; in xtSplitUp()
738 if (split->pxdlist == NULL) { in xtSplitUp()
739 nsplit = btstack->nsplit; in xtSplitUp()
740 split->pxdlist = &pxdlist; in xtSplitUp()
743 xlen = JFS_SBI(ip->i_sb)->nbperpage; in xtSplitUp()
744 for (; nsplit > 0; nsplit--, pxd++) { in xtSplitUp()
745 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr)) in xtSplitUp()
748 PXDlength(pxd, xlen); in xtSplitUp()
769 rc = (sp->header.flag & BT_ROOT) ? in xtSplitUp()
776 return -EIO; in xtSplitUp()
810 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc); in xtSplitUp()
820 skip = parent->index + 1; in xtSplitUp()
825 nextindex = le16_to_cpu(sp->header.nextindex); in xtSplitUp()
827 * parent page is full - split the parent page in xtSplitUp()
829 if (nextindex == le16_to_cpu(sp->header.maxentry)) { in xtSplitUp()
831 split->mp = smp; in xtSplitUp()
832 split->index = skip; /* index at insert */ in xtSplitUp()
833 split->flag = XAD_NEW; in xtSplitUp()
834 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]); in xtSplitUp()
835 split->len = JFS_SBI(ip->i_sb)->nbperpage; in xtSplitUp()
836 split->addr = rcbn; in xtSplitUp()
845 rc = (sp->header.flag & BT_ROOT) ? in xtSplitUp()
857 * parent page is not full - insert in parent page in xtSplitUp()
875 memmove(&sp->xad[skip + 1], &sp->xad[skip], in xtSplitUp()
876 (nextindex - in xtSplitUp()
880 xad = &sp->xad[skip]; in xtSplitUp()
882 offsetXAD(&rcp->xad[XTENTRYSTART]), in xtSplitUp()
883 JFS_SBI(ip->i_sb)->nbperpage, rcbn); in xtSplitUp()
886 le16_add_cpu(&sp->header.nextindex, 1); in xtSplitUp()
892 xtlck = (struct xtlock *) & tlck->lock; in xtSplitUp()
893 xtlck->lwm.offset = (xtlck->lwm.offset) ? in xtSplitUp()
894 min(skip, (int)xtlck->lwm.offset) : skip; in xtSplitUp()
895 xtlck->lwm.length = in xtSplitUp()
896 le16_to_cpu(sp->header.nextindex) - in xtSplitUp()
897 xtlck->lwm.offset; in xtSplitUp()
919 * split a full non-root page into
954 smp = split->mp; in xtSplitPage()
959 pxdlist = split->pxdlist; in xtSplitPage()
960 pxd = &pxdlist->pxd[pxdlist->npxd]; in xtSplitPage()
961 pxdlist->npxd++; in xtSplitPage()
974 rmp = get_metapage(ip, rbn, PSIZE, 1); in xtSplitPage()
976 rc = -EIO; in xtSplitPage()
987 rp = (xtpage_t *) rmp->data; in xtSplitPage()
988 rp->header.self = *pxd; in xtSplitPage()
989 rp->header.flag = sp->header.flag & BT_TYPE; in xtSplitPage()
990 rp->header.maxentry = sp->header.maxentry; /* little-endian */ in xtSplitPage()
991 rp->header.nextindex = cpu_to_le16(XTENTRYSTART); in xtSplitPage()
1000 rxtlck = (struct xtlock *) & tlck->lock; in xtSplitPage()
1001 rxtlck->lwm.offset = XTENTRYSTART; in xtSplitPage()
1006 sxtlck = (struct xtlock *) & tlck->lock; in xtSplitPage()
1012 nextbn = le64_to_cpu(sp->header.next); in xtSplitPage()
1013 rp->header.next = cpu_to_le64(nextbn); in xtSplitPage()
1014 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self)); in xtSplitPage()
1015 sp->header.next = cpu_to_le64(rbn); in xtSplitPage()
1017 skip = split->index; in xtSplitPage()
1026 * if we're wrong it's no big deal - we will do the split the right in xtSplitPage()
1032 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) { in xtSplitPage()
1039 xad = &rp->xad[XTENTRYSTART]; in xtSplitPage()
1040 XT_PUTENTRY(xad, split->flag, split->off, split->len, in xtSplitPage()
1041 split->addr); in xtSplitPage()
1043 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1); in xtSplitPage()
1046 /* rxtlck->lwm.offset = XTENTRYSTART; */ in xtSplitPage()
1047 rxtlck->lwm.length = 1; in xtSplitPage()
1058 * non-sequential insert (at possibly middle page) in xtSplitPage()
1080 p->header.prev = cpu_to_le64(rbn); in xtSplitPage()
1092 maxentry = le16_to_cpu(sp->header.maxentry); in xtSplitPage()
1093 middle = maxentry >> 1; in xtSplitPage()
1094 righthalf = maxentry - middle; in xtSplitPage()
1097 * skip index in old split/left page - insert into left page: in xtSplitPage()
1101 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle], in xtSplitPage()
1106 memmove(&sp->xad[skip + 1], &sp->xad[skip], in xtSplitPage()
1107 (middle - skip) << L2XTSLOTSIZE); in xtSplitPage()
1110 xad = &sp->xad[skip]; in xtSplitPage()
1111 XT_PUTENTRY(xad, split->flag, split->off, split->len, in xtSplitPage()
1112 split->addr); in xtSplitPage()
1115 sp->header.nextindex = cpu_to_le16(middle + 1); in xtSplitPage()
1117 sxtlck->lwm.offset = (sxtlck->lwm.offset) ? in xtSplitPage()
1118 min(skip, (int)sxtlck->lwm.offset) : skip; in xtSplitPage()
1121 rp->header.nextindex = in xtSplitPage()
1125 * skip index in new right page - insert into right page: in xtSplitPage()
1129 n = skip - middle; in xtSplitPage()
1130 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle], in xtSplitPage()
1135 xad = &rp->xad[n]; in xtSplitPage()
1136 XT_PUTENTRY(xad, split->flag, split->off, split->len, in xtSplitPage()
1137 split->addr); in xtSplitPage()
1141 memmove(&rp->xad[n + 1], &sp->xad[skip], in xtSplitPage()
1142 (maxentry - skip) << L2XTSLOTSIZE); in xtSplitPage()
1145 sp->header.nextindex = cpu_to_le16(middle); in xtSplitPage()
1147 sxtlck->lwm.offset = (sxtlck->lwm.offset) ? in xtSplitPage()
1148 min(middle, (int)sxtlck->lwm.offset) : middle; in xtSplitPage()
1151 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + in xtSplitPage()
1152 righthalf + 1); in xtSplitPage()
1156 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) - in xtSplitPage()
1157 sxtlck->lwm.offset; in xtSplitPage()
1159 /* rxtlck->lwm.offset = XTENTRYSTART; */ in xtSplitPage()
1160 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) - in xtSplitPage()
1188 * non-root page, and the split root page contains a single entry
1216 sp = (xtpage_t *) &JFS_IP(ip)->i_xtroot; in xtSplitRoot()
1223 pxdlist = split->pxdlist; in xtSplitRoot()
1224 pxd = &pxdlist->pxd[pxdlist->npxd]; in xtSplitRoot()
1225 pxdlist->npxd++; in xtSplitRoot()
1227 rmp = get_metapage(ip, rbn, PSIZE, 1); in xtSplitRoot()
1229 return -EIO; in xtSplitRoot()
1247 rp = (xtpage_t *) rmp->data; in xtSplitRoot()
1248 rp->header.flag = in xtSplitRoot()
1249 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL; in xtSplitRoot()
1250 rp->header.self = *pxd; in xtSplitRoot()
1251 rp->header.nextindex = cpu_to_le16(XTENTRYSTART); in xtSplitRoot()
1252 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE); in xtSplitRoot()
1255 rp->header.next = 0; in xtSplitRoot()
1256 rp->header.prev = 0; in xtSplitRoot()
1259 * copy the in-line root page into new right page extent in xtSplitRoot()
1261 nextindex = le16_to_cpu(sp->header.maxentry); in xtSplitRoot()
1262 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART], in xtSplitRoot()
1263 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE); in xtSplitRoot()
1269 skip = split->index; in xtSplitRoot()
1272 memmove(&rp->xad[skip + 1], &rp->xad[skip], in xtSplitRoot()
1273 (nextindex - skip) * sizeof(xad_t)); in xtSplitRoot()
1275 xad = &rp->xad[skip]; in xtSplitRoot()
1276 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr); in xtSplitRoot()
1279 rp->header.nextindex = cpu_to_le16(nextindex + 1); in xtSplitRoot()
1283 xtlck = (struct xtlock *) & tlck->lock; in xtSplitRoot()
1284 xtlck->lwm.offset = XTENTRYSTART; in xtSplitRoot()
1285 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) - in xtSplitRoot()
1293 * set the 1st entry offset to 0, which force the left-most key in xtSplitRoot()
1297 * acquire a transaction lock on the root page (in-memory inode); in xtSplitRoot()
1301 BT_MARK_DIRTY(split->mp, ip); in xtSplitRoot()
1303 xad = &sp->xad[XTENTRYSTART]; in xtSplitRoot()
1304 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn); in xtSplitRoot()
1307 sp->header.flag &= ~BT_LEAF; in xtSplitRoot()
1308 sp->header.flag |= BT_INTERNAL; in xtSplitRoot()
1310 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1); in xtSplitRoot()
1313 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW); in xtSplitRoot()
1314 xtlck = (struct xtlock *) & tlck->lock; in xtSplitRoot()
1315 xtlck->lwm.offset = XTENTRYSTART; in xtSplitRoot()
1316 xtlck->lwm.length = 1; in xtSplitRoot()
1329 * function: extend in-place;
1338 s32 xlen, /* delta extent length */ in xtExtend() argument
1343 struct metapage *mp; /* meta-page buffer */ in xtExtend()
1344 xtpage_t *p; /* base B+-tree index page */ in xtExtend()
1354 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen); in xtExtend()
1357 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT))) in xtExtend()
1365 jfs_error(ip->i_sb, "xtSearch did not find extent\n"); in xtExtend()
1366 return -EIO; in xtExtend()
1370 xad = &p->xad[index]; in xtExtend()
1373 jfs_error(ip->i_sb, "extension is not contiguous\n"); in xtExtend()
1374 return -EIO; in xtExtend()
1385 xtlck = (struct xtlock *) & tlck->lock; in xtExtend()
1389 xlen = lengthXAD(xad) + xlen; in xtExtend()
1390 if ((len = xlen - MAXXLEN) <= 0) in xtExtend()
1399 nextindex = le16_to_cpu(p->header.nextindex); in xtExtend()
1407 if (nextindex == le16_to_cpu(p->header.maxentry)) { in xtExtend()
1410 split.index = index + 1; in xtExtend()
1428 if (p->header.flag & BT_INTERNAL) { in xtExtend()
1429 ASSERT(p->header.nextindex == in xtExtend()
1430 cpu_to_le16(XTENTRYSTART + 1)); in xtExtend()
1431 xad = &p->xad[XTENTRYSTART]; in xtExtend()
1443 xtlck = (struct xtlock *) & tlck->lock; in xtExtend()
1452 xad = &p->xad[index + 1]; in xtExtend()
1456 le16_add_cpu(&p->header.nextindex, 1); in xtExtend()
1460 xad = &p->xad[index]; in xtExtend()
1461 xlen = MAXXLEN; in xtExtend()
1467 XADlength(xad, xlen); in xtExtend()
1468 if (!(xad->flag & XAD_NEW)) in xtExtend()
1469 xad->flag |= XAD_EXTENDED; in xtExtend()
1472 xtlck->lwm.offset = in xtExtend()
1473 (xtlck->lwm.offset) ? min(index, in xtExtend()
1474 (int)xtlck->lwm.offset) : index; in xtExtend()
1475 xtlck->lwm.length = in xtExtend()
1476 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; in xtExtend()
1494 * nxad - new XAD;
1502 struct metapage *mp; /* meta-page buffer */ in xtUpdate()
1503 xtpage_t *p; /* base B+-tree index page */ in xtUpdate()
1511 int nxlen, xlen, lxlen, rxlen; in xtUpdate() local
1530 jfs_error(ip->i_sb, "Could not find extent\n"); in xtUpdate()
1531 return -EIO; in xtUpdate()
1540 xtlck = (struct xtlock *) & tlck->lock; in xtUpdate()
1543 xad = &p->xad[index0]; in xtUpdate()
1544 xflag = xad->flag; in xtUpdate()
1546 xlen = lengthXAD(xad); in xtUpdate()
1551 (nxoff + nxlen > xoff + xlen)) { in xtUpdate()
1553 jfs_error(ip->i_sb, in xtUpdate()
1555 return -EIO; in xtUpdate()
1559 newindex = index + 1; in xtUpdate()
1560 nextindex = le16_to_cpu(p->header.nextindex); in xtUpdate()
1573 lxad = &p->xad[index - 1]; in xtUpdate()
1575 if (!(lxad->flag & XAD_NOTRECORDED) && in xtUpdate()
1580 index0 = index - 1; in xtUpdate()
1588 if (!(lxad->flag & XAD_NEW)) in xtUpdate()
1589 lxad->flag |= XAD_EXTENDED; in xtUpdate()
1591 if (xlen > nxlen) { in xtUpdate()
1594 XADlength(xad, xlen - nxlen); in xtUpdate()
1597 } else { /* (xlen == nxlen) */ in xtUpdate()
1600 if (index < nextindex - 1) in xtUpdate()
1601 memmove(&p->xad[index], &p->xad[index + 1], in xtUpdate()
1602 (nextindex - index - in xtUpdate()
1603 1) << L2XTSLOTSIZE); in xtUpdate()
1605 p->header.nextindex = in xtUpdate()
1606 cpu_to_le16(le16_to_cpu(p->header.nextindex) - in xtUpdate()
1607 1); in xtUpdate()
1610 newindex = index + 1; in xtUpdate()
1611 nextindex = le16_to_cpu(p->header.nextindex); in xtUpdate()
1613 xlen = nxlen = lxlen + nxlen; in xtUpdate()
1623 if (nxlen == xlen) { in xtUpdate()
1626 xad->flag = xflag & ~XAD_NOTRECORDED; in xtUpdate()
1629 } else /* (nxlen < xlen) */ in xtUpdate()
1644 rxad = &p->xad[index + 1]; in xtUpdate()
1646 if (!(rxad->flag & XAD_NOTRECORDED) && in xtUpdate()
1660 if (!(rxad->flag & XAD_NEW)) in xtUpdate()
1661 rxad->flag |= XAD_EXTENDED; in xtUpdate()
1663 if (xlen > nxlen) in xtUpdate()
1665 XADlength(xad, xlen - nxlen); in xtUpdate()
1666 else { /* (xlen == nxlen) */ in xtUpdate()
1669 memmove(&p->xad[index], &p->xad[index + 1], in xtUpdate()
1670 (nextindex - index - 1) << L2XTSLOTSIZE); in xtUpdate()
1672 p->header.nextindex = in xtUpdate()
1673 cpu_to_le16(le16_to_cpu(p->header.nextindex) - in xtUpdate()
1674 1); in xtUpdate()
1683 jfs_error(ip->i_sb, "xoff >= nxoff\n"); in xtUpdate()
1684 return -EIO; in xtUpdate()
1690 * |---nXAD---> in xtUpdate()
1691 * --|----------XAD----------|-- in xtUpdate()
1692 * |-lXAD-| in xtUpdate()
1696 xad = &p->xad[index]; in xtUpdate()
1697 XADlength(xad, nxoff - xoff); in xtUpdate()
1700 if (nextindex == le16_to_cpu(p->header.maxentry)) { in xtUpdate()
1722 if (p->header.flag & BT_INTERNAL) { in xtUpdate()
1723 ASSERT(p->header.nextindex == in xtUpdate()
1724 cpu_to_le16(XTENTRYSTART + 1)); in xtUpdate()
1725 xad = &p->xad[XTENTRYSTART]; in xtUpdate()
1737 xtlck = (struct xtlock *) & tlck->lock; in xtUpdate()
1742 (le16_to_cpu(p->header.maxentry) >> 1)) { in xtUpdate()
1744 newindex - in xtUpdate()
1745 le16_to_cpu(p->header.nextindex) + in xtUpdate()
1747 newpage = 1; in xtUpdate()
1753 memmove(&p->xad[newindex + 1], &p->xad[newindex], in xtUpdate()
1754 (nextindex - newindex) << L2XTSLOTSIZE); in xtUpdate()
1757 xad = &p->xad[newindex]; in xtUpdate()
1759 xad->flag = xflag & ~XAD_NOTRECORDED; in xtUpdate()
1762 p->header.nextindex = in xtUpdate()
1763 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1); in xtUpdate()
1767 * does nXAD force 3-way split ? in xtUpdate()
1769 * |---nXAD--->| in xtUpdate()
1770 * --|----------XAD-------------|-- in xtUpdate()
1771 * |-lXAD-| |-rXAD -| in xtUpdate()
1773 if (nxoff + nxlen == xoff + xlen) in xtUpdate()
1780 xtlck->lwm.offset = (xtlck->lwm.offset) ? in xtUpdate()
1781 min(index0, (int)xtlck->lwm.offset) : index0; in xtUpdate()
1782 xtlck->lwm.length = in xtUpdate()
1783 le16_to_cpu(p->header.nextindex) - in xtUpdate()
1784 xtlck->lwm.offset; in xtUpdate()
1787 bn = le64_to_cpu(p->header.next); in xtUpdate()
1798 xtlck = (struct xtlock *) & tlck->lock; in xtUpdate()
1805 newindex = index + 1; in xtUpdate()
1806 nextindex = le16_to_cpu(p->header.nextindex); in xtUpdate()
1807 xlen = xlen - (nxoff - xoff); in xtUpdate()
1812 if (nextindex == le16_to_cpu(p->header.maxentry)) { in xtUpdate()
1823 jfs_error(ip->i_sb, "xtSearch failed\n"); in xtUpdate()
1824 return -EIO; in xtUpdate()
1829 jfs_error(ip->i_sb, "unexpected value of index\n"); in xtUpdate()
1830 return -EIO; in xtUpdate()
1837 * ---nXAD---| in xtUpdate()
1838 * --|----------XAD----------|-- in xtUpdate()
1839 * |-rXAD-| in xtUpdate()
1841 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */ in xtUpdate()
1843 xad = &p->xad[index]; in xtUpdate()
1845 xad->flag = xflag & ~XAD_NOTRECORDED; in xtUpdate()
1849 xlen = xlen - nxlen; in xtUpdate()
1851 if (nextindex == le16_to_cpu(p->header.maxentry)) { in xtUpdate()
1860 split.len = xlen; in xtUpdate()
1876 if (p->header.flag & BT_INTERNAL) { in xtUpdate()
1877 ASSERT(p->header.nextindex == in xtUpdate()
1878 cpu_to_le16(XTENTRYSTART + 1)); in xtUpdate()
1879 xad = &p->xad[XTENTRYSTART]; in xtUpdate()
1891 xtlck = (struct xtlock *) & tlck->lock; in xtUpdate()
1897 memmove(&p->xad[newindex + 1], &p->xad[newindex], in xtUpdate()
1898 (nextindex - newindex) << L2XTSLOTSIZE); in xtUpdate()
1901 xad = &p->xad[newindex]; in xtUpdate()
1902 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); in xtUpdate()
1905 p->header.nextindex = in xtUpdate()
1906 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1); in xtUpdate()
1911 xtlck->lwm.offset = (xtlck->lwm.offset) ? in xtUpdate()
1912 min(index0, (int)xtlck->lwm.offset) : index0; in xtUpdate()
1913 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - in xtUpdate()
1914 xtlck->lwm.offset; in xtUpdate()
1930 * tid - transaction id;
1931 * ip - file object;
1932 * xflag - extent flag:
1933 * xoff - extent offset;
1934 * maxblocks - max extent length;
1935 * xlen - extent length (in/out);
1936 * xaddrp - extent address pointer (in/out):
1937 * flag -
1948 struct metapage *mp; /* meta-page buffer */ in xtAppend()
1949 xtpage_t *p; /* base B+-tree index page */ in xtAppend()
1958 int nsplit, nblocks, xlen; in xtAppend() local
1964 xlen = *xlenp; in xtAppend()
1965 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx", in xtAppend()
1966 (ulong) xoff, maxblocks, xlen, (ulong) xaddr); in xtAppend()
1983 rc = -EEXIST; in xtAppend()
1988 xlen = min(xlen, (int)(next - xoff)); in xtAppend()
2001 nextindex = le16_to_cpu(p->header.nextindex); in xtAppend()
2002 if (nextindex < le16_to_cpu(p->header.maxentry)) in xtAppend()
2012 nblocks = JFS_SBI(ip->i_sb)->nbperpage; in xtAppend()
2013 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) { in xtAppend()
2028 xlen = min(xlen, maxblocks); in xtAppend()
2033 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen))) in xtAppend()
2040 split.len = xlen; in xtAppend()
2050 *xlenp = xlen; in xtAppend()
2060 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen))) in xtAppend()
2070 xtlck = (struct xtlock *) & tlck->lock; in xtAppend()
2073 xad = &p->xad[index]; in xtAppend()
2074 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr); in xtAppend()
2077 le16_add_cpu(&p->header.nextindex, 1); in xtAppend()
2079 xtlck->lwm.offset = in xtAppend()
2080 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index; in xtAppend()
2081 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - in xtAppend()
2082 xtlck->lwm.offset; in xtAppend()
2085 *xlenp = xlen; in xtAppend()
2108 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag, in xtInitRoot()
2110 p = &JFS_IP(ip)->i_xtroot; in xtInitRoot()
2112 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF; in xtInitRoot()
2113 p->header.nextindex = cpu_to_le16(XTENTRYSTART); in xtInitRoot()
2115 if (S_ISDIR(ip->i_mode)) in xtInitRoot()
2116 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR); in xtInitRoot()
2118 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT); in xtInitRoot()
2119 ip->i_size = 0; in xtInitRoot()
2160 * 1. truncate (non-COMMIT_NOLINK file)
2168 * 1. remove (free zero link count) on last reference release
2198 int xlen, len, freexlen; in xtTruncate() local
2213 tblk->xflag |= flag; in xtTruncate()
2222 log = 1; in xtTruncate()
2226 xadlock.index = 1; in xtTruncate()
2252 * temporary file (zerolink count file truncated to zero-length)). in xtTruncate()
2254 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >> in xtTruncate()
2255 JFS_SBI(ip->i_sb)->l2bsize; in xtTruncate()
2276 index = le16_to_cpu(p->header.nextindex) - 1; in xtTruncate()
2283 if (p->header.next) { in xtTruncate()
2292 p->header.next = 0; in xtTruncate()
2295 if (p->header.flag & BT_INTERNAL) in xtTruncate()
2304 xad = &p->xad[index]; in xtTruncate()
2306 xlen = lengthXAD(xad); in xtTruncate()
2307 if (teof >= xoff + xlen) { in xtTruncate()
2320 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize; in xtTruncate()
2324 tlck->type = tlckXTREE | tlckTRUNCATE; in xtTruncate()
2325 xtlck = (struct xtlock *) & tlck->lock; in xtTruncate()
2326 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1; in xtTruncate()
2333 for (; index >= XTENTRYSTART; index--) { in xtTruncate()
2334 xad = &p->xad[index]; in xtTruncate()
2336 xlen = lengthXAD(xad); in xtTruncate()
2344 if (S_ISDIR(ip->i_mode) && (teof == 0)) in xtTruncate()
2349 * ---|---=======-------> in xtTruncate()
2353 nfreed += xlen; in xtTruncate()
2365 * -------|=======-------> in xtTruncate()
2370 nfreed += xlen; in xtTruncate()
2380 * -------===|===-------> in xtTruncate()
2383 else if (teof < xoff + xlen) { in xtTruncate()
2385 len = teof - xoff; in xtTruncate()
2386 freexlen = xlen - len; in xtTruncate()
2392 xtlck->lwm.offset = (xtlck->lwm.offset) ? in xtTruncate()
2393 min(index, (int)xtlck->lwm.offset) : index; in xtTruncate()
2394 xtlck->lwm.length = index + 1 - in xtTruncate()
2395 xtlck->lwm.offset; in xtTruncate()
2396 xtlck->twm.offset = index; in xtTruncate()
2397 pxdlock = (struct pxd_lock *) & xtlck->pxdlock; in xtTruncate()
2398 pxdlock->flag = mlckFREEPXD; in xtTruncate()
2399 PXDaddress(&pxdlock->pxd, xaddr); in xtTruncate()
2400 PXDlength(&pxdlock->pxd, freexlen); in xtTruncate()
2406 pxdlock->flag = mlckFREEPXD; in xtTruncate()
2407 PXDaddress(&pxdlock->pxd, xaddr); in xtTruncate()
2408 PXDlength(&pxdlock->pxd, freexlen); in xtTruncate()
2416 nextindex = index + 1; in xtTruncate()
2423 * -------=======---|---> in xtTruncate()
2426 else { /* (xoff + xlen < teof) */ in xtTruncate()
2428 nextindex = index + 1; in xtTruncate()
2431 if (nextindex < le16_to_cpu(p->header.nextindex)) { in xtTruncate()
2433 xadlock.xdlist = &p->xad[nextindex]; in xtTruncate()
2435 le16_to_cpu(p->header.nextindex) - in xtTruncate()
2440 p->header.nextindex = cpu_to_le16(nextindex); in xtTruncate()
2449 freed = 1; in xtTruncate()
2460 tlck->type = tlckXTREE | tlckFREE; in xtTruncate()
2464 xadlock.xdlist = &p->xad[XTENTRYSTART]; in xtTruncate()
2466 le16_to_cpu(p->header.nextindex) - XTENTRYSTART; in xtTruncate()
2470 if (p->header.flag & BT_ROOT) { in xtTruncate()
2471 p->header.flag &= ~BT_INTERNAL; in xtTruncate()
2472 p->header.flag |= BT_LEAF; in xtTruncate()
2473 p->header.nextindex = cpu_to_le16(XTENTRYSTART); in xtTruncate()
2484 if (mp->lid) in xtTruncate()
2485 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK; in xtTruncate()
2508 bn = parent->bn; in xtTruncate()
2513 index = parent->index; in xtTruncate()
2520 if (index < le16_to_cpu(p->header.nextindex) - 1) { in xtTruncate()
2527 xtlck = (struct xtlock *) & tlck->lock; in xtTruncate()
2528 if (!(tlck->type & tlckTRUNCATE)) { in xtTruncate()
2529 xtlck->hwm.offset = in xtTruncate()
2530 le16_to_cpu(p->header. in xtTruncate()
2531 nextindex) - 1; in xtTruncate()
2532 tlck->type = in xtTruncate()
2538 xadlock.xdlist = &p->xad[index + 1]; in xtTruncate()
2540 le16_to_cpu(p->header.nextindex) - in xtTruncate()
2541 index - 1; in xtTruncate()
2547 p->header.nextindex = cpu_to_le16(index + 1); in xtTruncate()
2556 nfreed += lengthXAD(&p->xad[index]); in xtTruncate()
2564 * ToDo: tlocks should be on doubly-linked list, so we can in xtTruncate()
2571 if (log && mp->lid && (tblk->last != mp->lid) && in xtTruncate()
2572 lid_to_tlock(mp->lid)->tid) { in xtTruncate()
2573 lid_t lid = mp->lid; in xtTruncate()
2578 if (tblk->next == lid) in xtTruncate()
2579 tblk->next = tlck->next; in xtTruncate()
2581 for (prev = lid_to_tlock(tblk->next); in xtTruncate()
2582 prev->next != lid; in xtTruncate()
2583 prev = lid_to_tlock(prev->next)) { in xtTruncate()
2584 assert(prev->next); in xtTruncate()
2586 prev->next = tlck->next; in xtTruncate()
2588 lid_to_tlock(tblk->last)->next = lid; in xtTruncate()
2589 tlck->next = 0; in xtTruncate()
2590 tblk->last = lid; in xtTruncate()
2603 xtlck = (struct xtlock *) & tlck->lock; in xtTruncate()
2604 xtlck->hwm.offset = in xtTruncate()
2605 le16_to_cpu(p->header.nextindex) - 1; in xtTruncate()
2606 tlck->type = tlckXTREE | tlckFREE; in xtTruncate()
2610 xadlock.xdlist = &p->xad[XTENTRYSTART]; in xtTruncate()
2612 le16_to_cpu(p->header.nextindex) - in xtTruncate()
2619 if (p->header.flag & BT_ROOT) { in xtTruncate()
2620 p->header.flag &= ~BT_INTERNAL; in xtTruncate()
2621 p->header.flag |= BT_LEAF; in xtTruncate()
2622 p->header.nextindex = cpu_to_le16(XTENTRYSTART); in xtTruncate()
2623 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) { in xtTruncate()
2628 p->header.maxentry = in xtTruncate()
2630 JFS_IP(ip)->mode2 |= INLINEEA; in xtTruncate()
2642 if (mp->lid) in xtTruncate()
2643 lid_to_tlock(mp->lid)->flag |= in xtTruncate()
2653 /* freed = 1; */ in xtTruncate()
2664 index--; in xtTruncate()
2678 jfs_error(ip->i_sb, "stack overrun!\n"); in xtTruncate()
2680 return -EIO; in xtTruncate()
2685 xad = &p->xad[index]; in xtTruncate()
2703 if (S_ISDIR(ip->i_mode) && !newsize) in xtTruncate()
2704 ip->i_size = 1; /* fsck hates zero-length directories */ in xtTruncate()
2706 ip->i_size = newsize; in xtTruncate()
2758 int xlen; in xtTruncate_pmap() local
2764 tblk->xflag |= COMMIT_PMAP; in xtTruncate_pmap()
2770 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1; in xtTruncate_pmap()
2779 jfs_error(ip->i_sb, "did not find extent\n"); in xtTruncate_pmap()
2780 return -EIO; in xtTruncate_pmap()
2799 index = le16_to_cpu(p->header.nextindex) - 1; in xtTruncate_pmap()
2801 if (p->header.flag & BT_INTERNAL) in xtTruncate_pmap()
2814 xad = &p->xad[index]; in xtTruncate_pmap()
2816 xlen = lengthXAD(xad); in xtTruncate_pmap()
2818 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize; in xtTruncate_pmap()
2821 tlck->type = tlckXTREE | tlckFREE; in xtTruncate_pmap()
2822 xtlck = (struct xtlock *) & tlck->lock; in xtTruncate_pmap()
2823 xtlck->hwm.offset = index; in xtTruncate_pmap()
2838 bn = parent->bn; in xtTruncate_pmap()
2843 index = parent->index; in xtTruncate_pmap()
2854 xtlck = (struct xtlock *) & tlck->lock; in xtTruncate_pmap()
2855 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1; in xtTruncate_pmap()
2856 tlck->type = tlckXTREE | tlckFREE; in xtTruncate_pmap()
2860 if (p->header.flag & BT_ROOT) { in xtTruncate_pmap()
2871 index--; in xtTruncate_pmap()
2878 jfs_error(ip->i_sb, "stack overrun!\n"); in xtTruncate_pmap()
2880 return -EIO; in xtTruncate_pmap()
2885 xad = &p->xad[index]; in xtTruncate_pmap()