Loading...
1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * Copyright (C) International Business Machines Corp., 2000-2005
4 */
5/*
6 * jfs_xtree.c: extent allocation descriptor B+-tree manager
7 */
8
9#include <linux/fs.h>
10#include <linux/module.h>
11#include <linux/quotaops.h>
12#include <linux/seq_file.h>
13#include "jfs_incore.h"
14#include "jfs_filsys.h"
15#include "jfs_metapage.h"
16#include "jfs_dmap.h"
17#include "jfs_dinode.h"
18#include "jfs_superblock.h"
19#include "jfs_debug.h"
20
21/*
22 * xtree local flag
23 */
24#define XT_INSERT 0x00000001
25
26/*
27 * xtree key/entry comparison: extent offset
28 *
29 * return:
30 * -1: k < start of extent
31 * 0: start_of_extent <= k <= end_of_extent
32 * 1: k > end_of_extent
33 */
34#define XT_CMP(CMP, K, X, OFFSET64)\
35{\
36 OFFSET64 = offsetXAD(X);\
37 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
38 ((K) < OFFSET64) ? -1 : 0;\
39}
40
41/* write a xad entry */
42#define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
43{\
44 (XAD)->flag = (FLAG);\
45 XADoffset((XAD), (OFF));\
46 XADlength((XAD), (LEN));\
47 XADaddress((XAD), (ADDR));\
48}
49
50#define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
51
52/* get page buffer for specified block address */
53/* ToDo: Replace this ugly macro with a function */
54#define XT_GETPAGE(IP, BN, MP, SIZE, P, RC) \
55do { \
56 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot); \
57 if (!(RC)) { \
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) > \
62 (((BN) == 0) ? XTROOTMAXSLOT : PSIZE >> L2XTSLOTSIZE))) { \
63 jfs_error((IP)->i_sb, \
64 "XT_GETPAGE: xtree page corrupt\n"); \
65 BT_PUTPAGE(MP); \
66 MP = NULL; \
67 RC = -EIO; \
68 } \
69 } \
70} while (0)
71
72/* for consistency */
73#define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
74
75#define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
76 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
77/* xtree entry parameter descriptor */
78struct xtsplit {
79 struct metapage *mp;
80 s16 index;
81 u8 flag;
82 s64 off;
83 s64 addr;
84 int len;
85 struct pxdlist *pxdlist;
86};
87
88
89/*
90 * statistics
91 */
92#ifdef CONFIG_JFS_STATISTICS
93static struct {
94 uint search;
95 uint fastSearch;
96 uint split;
97} xtStat;
98#endif
99
100
101/*
102 * forward references
103 */
104static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
105 struct btstack * btstack, int flag);
106
107static int xtSplitUp(tid_t tid,
108 struct inode *ip,
109 struct xtsplit * split, struct btstack * btstack);
110
111static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
112 struct metapage ** rmpp, s64 * rbnp);
113
114static int xtSplitRoot(tid_t tid, struct inode *ip,
115 struct xtsplit * split, struct metapage ** rmpp);
116
117#ifdef _STILL_TO_PORT
118static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
119 xtpage_t * fp, struct btstack * btstack);
120
121static int xtSearchNode(struct inode *ip,
122 xad_t * xad,
123 int *cmpp, struct btstack * btstack, int flag);
124
125static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
126#endif /* _STILL_TO_PORT */
127
128/*
129 * xtLookup()
130 *
131 * function: map a single page into a physical extent;
132 */
133int xtLookup(struct inode *ip, s64 lstart,
134 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
135{
136 int rc = 0;
137 struct btstack btstack;
138 int cmp;
139 s64 bn;
140 struct metapage *mp;
141 xtpage_t *p;
142 int index;
143 xad_t *xad;
144 s64 next, size, xoff, xend;
145 int xlen;
146 s64 xaddr;
147
148 *paddr = 0;
149 *plen = llen;
150
151 if (!no_check) {
152 /* is lookup offset beyond eof ? */
153 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
154 JFS_SBI(ip->i_sb)->l2bsize;
155 if (lstart >= size)
156 return 0;
157 }
158
159 /*
160 * search for the xad entry covering the logical extent
161 */
162//search:
163 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
164 jfs_err("xtLookup: xtSearch returned %d", rc);
165 return rc;
166 }
167
168 /*
169 * compute the physical extent covering logical extent
170 *
171 * N.B. search may have failed (e.g., hole in sparse file),
172 * and returned the index of the next entry.
173 */
174 /* retrieve search result */
175 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
176
177 /* is xad found covering start of logical extent ?
178 * lstart is a page start address,
179 * i.e., lstart cannot start in a hole;
180 */
181 if (cmp) {
182 if (next)
183 *plen = min(next - lstart, llen);
184 goto out;
185 }
186
187 /*
188 * lxd covered by xad
189 */
190 xad = &p->xad[index];
191 xoff = offsetXAD(xad);
192 xlen = lengthXAD(xad);
193 xend = xoff + xlen;
194 xaddr = addressXAD(xad);
195
196 /* initialize new pxd */
197 *pflag = xad->flag;
198 *paddr = xaddr + (lstart - xoff);
199 /* a page must be fully covered by an xad */
200 *plen = min(xend - lstart, llen);
201
202 out:
203 XT_PUTPAGE(mp);
204
205 return rc;
206}
207
208/*
209 * xtSearch()
210 *
211 * function: search for the xad entry covering specified offset.
212 *
213 * parameters:
214 * ip - file object;
215 * xoff - extent offset;
216 * nextp - address of next extent (if any) for search miss
217 * cmpp - comparison result:
218 * btstack - traverse stack;
219 * flag - search process flag (XT_INSERT);
220 *
221 * returns:
222 * btstack contains (bn, index) of search path traversed to the entry.
223 * *cmpp is set to result of comparison with the entry returned.
224 * the page containing the entry is pinned at exit.
225 */
226static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
227 int *cmpp, struct btstack * btstack, int flag)
228{
229 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
230 int rc = 0;
231 int cmp = 1; /* init for empty page */
232 s64 bn; /* block number */
233 struct metapage *mp; /* page buffer */
234 xtpage_t *p; /* page */
235 xad_t *xad;
236 int base, index, lim, btindex;
237 struct btframe *btsp;
238 int nsplit = 0; /* number of pages to split */
239 s64 t64;
240 s64 next = 0;
241
242 INCREMENT(xtStat.search);
243
244 BT_CLR(btstack);
245
246 btstack->nsplit = 0;
247
248 /*
249 * search down tree from root:
250 *
251 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
252 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
253 *
254 * if entry with search key K is not found
255 * internal page search find the entry with largest key Ki
256 * less than K which point to the child page to search;
257 * leaf page search find the entry with smallest key Kj
258 * greater than K so that the returned index is the position of
259 * the entry to be shifted right for insertion of new entry.
260 * for empty tree, search key is greater than any key of the tree.
261 *
262 * by convention, root bn = 0.
263 */
264 for (bn = 0;;) {
265 /* get/pin the page to search */
266 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
267 if (rc)
268 return rc;
269
270 /* try sequential access heuristics with the previous
271 * access entry in target leaf page:
272 * once search narrowed down into the target leaf,
273 * key must either match an entry in the leaf or
274 * key entry does not exist in the tree;
275 */
276//fastSearch:
277 if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
278 (p->header.flag & BT_LEAF) &&
279 (index = jfs_ip->btindex) <
280 le16_to_cpu(p->header.nextindex)) {
281 xad = &p->xad[index];
282 t64 = offsetXAD(xad);
283 if (xoff < t64 + lengthXAD(xad)) {
284 if (xoff >= t64) {
285 *cmpp = 0;
286 goto out;
287 }
288
289 /* stop sequential access heuristics */
290 goto binarySearch;
291 } else { /* (t64 + lengthXAD(xad)) <= xoff */
292
293 /* try next sequential entry */
294 index++;
295 if (index <
296 le16_to_cpu(p->header.nextindex)) {
297 xad++;
298 t64 = offsetXAD(xad);
299 if (xoff < t64 + lengthXAD(xad)) {
300 if (xoff >= t64) {
301 *cmpp = 0;
302 goto out;
303 }
304
305 /* miss: key falls between
306 * previous and this entry
307 */
308 *cmpp = 1;
309 next = t64;
310 goto out;
311 }
312
313 /* (xoff >= t64 + lengthXAD(xad));
314 * matching entry may be further out:
315 * stop heuristic search
316 */
317 /* stop sequential access heuristics */
318 goto binarySearch;
319 }
320
321 /* (index == p->header.nextindex);
322 * miss: key entry does not exist in
323 * the target leaf/tree
324 */
325 *cmpp = 1;
326 goto out;
327 }
328
329 /*
330 * if hit, return index of the entry found, and
331 * if miss, where new entry with search key is
332 * to be inserted;
333 */
334 out:
335 /* compute number of pages to split */
336 if (flag & XT_INSERT) {
337 if (p->header.nextindex == /* little-endian */
338 p->header.maxentry)
339 nsplit++;
340 else
341 nsplit = 0;
342 btstack->nsplit = nsplit;
343 }
344
345 /* save search result */
346 btsp = btstack->top;
347 btsp->bn = bn;
348 btsp->index = index;
349 btsp->mp = mp;
350
351 /* update sequential access heuristics */
352 jfs_ip->btindex = index;
353
354 if (nextp)
355 *nextp = next;
356
357 INCREMENT(xtStat.fastSearch);
358 return 0;
359 }
360
361 /* well, ... full search now */
362 binarySearch:
363 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
364
365 /*
366 * binary search with search key K on the current page
367 */
368 for (base = XTENTRYSTART; lim; lim >>= 1) {
369 index = base + (lim >> 1);
370
371 XT_CMP(cmp, xoff, &p->xad[index], t64);
372 if (cmp == 0) {
373 /*
374 * search hit
375 */
376 /* search hit - leaf page:
377 * return the entry found
378 */
379 if (p->header.flag & BT_LEAF) {
380 *cmpp = cmp;
381
382 /* compute number of pages to split */
383 if (flag & XT_INSERT) {
384 if (p->header.nextindex ==
385 p->header.maxentry)
386 nsplit++;
387 else
388 nsplit = 0;
389 btstack->nsplit = nsplit;
390 }
391
392 /* save search result */
393 btsp = btstack->top;
394 btsp->bn = bn;
395 btsp->index = index;
396 btsp->mp = mp;
397
398 /* init sequential access heuristics */
399 btindex = jfs_ip->btindex;
400 if (index == btindex ||
401 index == btindex + 1)
402 jfs_ip->btorder = BT_SEQUENTIAL;
403 else
404 jfs_ip->btorder = BT_RANDOM;
405 jfs_ip->btindex = index;
406
407 return 0;
408 }
409 /* search hit - internal page:
410 * descend/search its child page
411 */
412 if (index < le16_to_cpu(p->header.nextindex)-1)
413 next = offsetXAD(&p->xad[index + 1]);
414 goto next;
415 }
416
417 if (cmp > 0) {
418 base = index + 1;
419 --lim;
420 }
421 }
422
423 /*
424 * search miss
425 *
426 * base is the smallest index with key (Kj) greater than
427 * search key (K) and may be zero or maxentry index.
428 */
429 if (base < le16_to_cpu(p->header.nextindex))
430 next = offsetXAD(&p->xad[base]);
431 /*
432 * search miss - leaf page:
433 *
434 * return location of entry (base) where new entry with
435 * search key K is to be inserted.
436 */
437 if (p->header.flag & BT_LEAF) {
438 *cmpp = cmp;
439
440 /* compute number of pages to split */
441 if (flag & XT_INSERT) {
442 if (p->header.nextindex ==
443 p->header.maxentry)
444 nsplit++;
445 else
446 nsplit = 0;
447 btstack->nsplit = nsplit;
448 }
449
450 /* save search result */
451 btsp = btstack->top;
452 btsp->bn = bn;
453 btsp->index = base;
454 btsp->mp = mp;
455
456 /* init sequential access heuristics */
457 btindex = jfs_ip->btindex;
458 if (base == btindex || base == btindex + 1)
459 jfs_ip->btorder = BT_SEQUENTIAL;
460 else
461 jfs_ip->btorder = BT_RANDOM;
462 jfs_ip->btindex = base;
463
464 if (nextp)
465 *nextp = next;
466
467 return 0;
468 }
469
470 /*
471 * search miss - non-leaf page:
472 *
473 * if base is non-zero, decrement base by one to get the parent
474 * entry of the child page to search.
475 */
476 index = base ? base - 1 : base;
477
478 /*
479 * go down to child page
480 */
481 next:
482 /* update number of pages to split */
483 if (p->header.nextindex == p->header.maxentry)
484 nsplit++;
485 else
486 nsplit = 0;
487
488 /* push (bn, index) of the parent page/entry */
489 if (BT_STACK_FULL(btstack)) {
490 jfs_error(ip->i_sb, "stack overrun!\n");
491 XT_PUTPAGE(mp);
492 return -EIO;
493 }
494 BT_PUSH(btstack, bn, index);
495
496 /* get the child page block number */
497 bn = addressXAD(&p->xad[index]);
498
499 /* unpin the parent page */
500 XT_PUTPAGE(mp);
501 }
502}
503
504/*
505 * xtInsert()
506 *
507 * function:
508 *
509 * parameter:
510 * tid - transaction id;
511 * ip - file object;
512 * xflag - extent flag (XAD_NOTRECORDED):
513 * xoff - extent offset;
514 * xlen - extent length;
515 * xaddrp - extent address pointer (in/out):
516 * if (*xaddrp)
517 * caller allocated data extent at *xaddrp;
518 * else
519 * allocate data extent and return its xaddr;
520 * flag -
521 *
522 * return:
523 */
524int xtInsert(tid_t tid, /* transaction id */
525 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
526 int flag)
527{
528 int rc = 0;
529 s64 xaddr, hint;
530 struct metapage *mp; /* meta-page buffer */
531 xtpage_t *p; /* base B+-tree index page */
532 s64 bn;
533 int index, nextindex;
534 struct btstack btstack; /* traverse stack */
535 struct xtsplit split; /* split information */
536 xad_t *xad;
537 int cmp;
538 s64 next;
539 struct tlock *tlck;
540 struct xtlock *xtlck;
541
542 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
543
544 /*
545 * search for the entry location at which to insert:
546 *
547 * xtFastSearch() and xtSearch() both returns (leaf page
548 * pinned, index at which to insert).
549 * n.b. xtSearch() may return index of maxentry of
550 * the full page.
551 */
552 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
553 return rc;
554
555 /* retrieve search result */
556 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
557
558 /* This test must follow XT_GETSEARCH since mp must be valid if
559 * we branch to out: */
560 if ((cmp == 0) || (next && (xlen > next - xoff))) {
561 rc = -EEXIST;
562 goto out;
563 }
564
565 /*
566 * allocate data extent requested
567 *
568 * allocation hint: last xad
569 */
570 if ((xaddr = *xaddrp) == 0) {
571 if (index > XTENTRYSTART) {
572 xad = &p->xad[index - 1];
573 hint = addressXAD(xad) + lengthXAD(xad) - 1;
574 } else
575 hint = 0;
576 if ((rc = dquot_alloc_block(ip, xlen)))
577 goto out;
578 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
579 dquot_free_block(ip, xlen);
580 goto out;
581 }
582 }
583
584 /*
585 * insert entry for new extent
586 */
587 xflag |= XAD_NEW;
588
589 /*
590 * if the leaf page is full, split the page and
591 * propagate up the router entry for the new page from split
592 *
593 * The xtSplitUp() will insert the entry and unpin the leaf page.
594 */
595 nextindex = le16_to_cpu(p->header.nextindex);
596 if (nextindex == le16_to_cpu(p->header.maxentry)) {
597 split.mp = mp;
598 split.index = index;
599 split.flag = xflag;
600 split.off = xoff;
601 split.len = xlen;
602 split.addr = xaddr;
603 split.pxdlist = NULL;
604 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
605 /* undo data extent allocation */
606 if (*xaddrp == 0) {
607 dbFree(ip, xaddr, (s64) xlen);
608 dquot_free_block(ip, xlen);
609 }
610 return rc;
611 }
612
613 *xaddrp = xaddr;
614 return 0;
615 }
616
617 /*
618 * insert the new entry into the leaf page
619 */
620 /*
621 * acquire a transaction lock on the leaf page;
622 *
623 * action: xad insertion/extension;
624 */
625 BT_MARK_DIRTY(mp, ip);
626
627 /* if insert into middle, shift right remaining entries. */
628 if (index < nextindex)
629 memmove(&p->xad[index + 1], &p->xad[index],
630 (nextindex - index) * sizeof(xad_t));
631
632 /* insert the new entry: mark the entry NEW */
633 xad = &p->xad[index];
634 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
635
636 /* advance next available entry index */
637 le16_add_cpu(&p->header.nextindex, 1);
638
639 /* Don't log it if there are no links to the file */
640 if (!test_cflag(COMMIT_Nolink, ip)) {
641 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
642 xtlck = (struct xtlock *) & tlck->lock;
643 xtlck->lwm.offset =
644 (xtlck->lwm.offset) ? min(index,
645 (int)xtlck->lwm.offset) : index;
646 xtlck->lwm.length =
647 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
648 }
649
650 *xaddrp = xaddr;
651
652 out:
653 /* unpin the leaf page */
654 XT_PUTPAGE(mp);
655
656 return rc;
657}
658
659
660/*
661 * xtSplitUp()
662 *
663 * function:
664 * split full pages as propagating insertion up the tree
665 *
666 * parameter:
667 * tid - transaction id;
668 * ip - file object;
669 * split - entry parameter descriptor;
670 * btstack - traverse stack from xtSearch()
671 *
672 * return:
673 */
674static int
675xtSplitUp(tid_t tid,
676 struct inode *ip, struct xtsplit * split, struct btstack * btstack)
677{
678 int rc = 0;
679 struct metapage *smp;
680 xtpage_t *sp; /* split page */
681 struct metapage *rmp;
682 s64 rbn; /* new right page block number */
683 struct metapage *rcmp;
684 xtpage_t *rcp; /* right child page */
685 s64 rcbn; /* right child page block number */
686 int skip; /* index of entry of insertion */
687 int nextindex; /* next available entry index of p */
688 struct btframe *parent; /* parent page entry on traverse stack */
689 xad_t *xad;
690 s64 xaddr;
691 int xlen;
692 int nsplit; /* number of pages split */
693 struct pxdlist pxdlist;
694 pxd_t *pxd;
695 struct tlock *tlck;
696 struct xtlock *xtlck;
697
698 smp = split->mp;
699 sp = XT_PAGE(ip, smp);
700
701 /* is inode xtree root extension/inline EA area free ? */
702 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
703 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
704 (JFS_IP(ip)->mode2 & INLINEEA)) {
705 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
706 JFS_IP(ip)->mode2 &= ~INLINEEA;
707
708 BT_MARK_DIRTY(smp, ip);
709 /*
710 * acquire a transaction lock on the leaf page;
711 *
712 * action: xad insertion/extension;
713 */
714
715 /* if insert into middle, shift right remaining entries. */
716 skip = split->index;
717 nextindex = le16_to_cpu(sp->header.nextindex);
718 if (skip < nextindex)
719 memmove(&sp->xad[skip + 1], &sp->xad[skip],
720 (nextindex - skip) * sizeof(xad_t));
721
722 /* insert the new entry: mark the entry NEW */
723 xad = &sp->xad[skip];
724 XT_PUTENTRY(xad, split->flag, split->off, split->len,
725 split->addr);
726
727 /* advance next available entry index */
728 le16_add_cpu(&sp->header.nextindex, 1);
729
730 /* Don't log it if there are no links to the file */
731 if (!test_cflag(COMMIT_Nolink, ip)) {
732 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
733 xtlck = (struct xtlock *) & tlck->lock;
734 xtlck->lwm.offset = (xtlck->lwm.offset) ?
735 min(skip, (int)xtlck->lwm.offset) : skip;
736 xtlck->lwm.length =
737 le16_to_cpu(sp->header.nextindex) -
738 xtlck->lwm.offset;
739 }
740
741 return 0;
742 }
743
744 /*
745 * allocate new index blocks to cover index page split(s)
746 *
747 * allocation hint: ?
748 */
749 if (split->pxdlist == NULL) {
750 nsplit = btstack->nsplit;
751 split->pxdlist = &pxdlist;
752 pxdlist.maxnpxd = pxdlist.npxd = 0;
753 pxd = &pxdlist.pxd[0];
754 xlen = JFS_SBI(ip->i_sb)->nbperpage;
755 for (; nsplit > 0; nsplit--, pxd++) {
756 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
757 == 0) {
758 PXDaddress(pxd, xaddr);
759 PXDlength(pxd, xlen);
760
761 pxdlist.maxnpxd++;
762
763 continue;
764 }
765
766 /* undo allocation */
767
768 XT_PUTPAGE(smp);
769 return rc;
770 }
771 }
772
773 /*
774 * Split leaf page <sp> into <sp> and a new right page <rp>.
775 *
776 * The split routines insert the new entry into the leaf page,
777 * and acquire txLock as appropriate.
778 * return <rp> pinned and its block number <rpbn>.
779 */
780 rc = (sp->header.flag & BT_ROOT) ?
781 xtSplitRoot(tid, ip, split, &rmp) :
782 xtSplitPage(tid, ip, split, &rmp, &rbn);
783
784 XT_PUTPAGE(smp);
785
786 if (rc)
787 return -EIO;
788 /*
789 * propagate up the router entry for the leaf page just split
790 *
791 * insert a router entry for the new page into the parent page,
792 * propagate the insert/split up the tree by walking back the stack
793 * of (bn of parent page, index of child page entry in parent page)
794 * that were traversed during the search for the page that split.
795 *
796 * the propagation of insert/split up the tree stops if the root
797 * splits or the page inserted into doesn't have to split to hold
798 * the new entry.
799 *
800 * the parent entry for the split page remains the same, and
801 * a new entry is inserted at its right with the first key and
802 * block number of the new right page.
803 *
804 * There are a maximum of 3 pages pinned at any time:
805 * right child, left parent and right parent (when the parent splits)
806 * to keep the child page pinned while working on the parent.
807 * make sure that all pins are released at exit.
808 */
809 while ((parent = BT_POP(btstack)) != NULL) {
810 /* parent page specified by stack frame <parent> */
811
812 /* keep current child pages <rcp> pinned */
813 rcmp = rmp;
814 rcbn = rbn;
815 rcp = XT_PAGE(ip, rcmp);
816
817 /*
818 * insert router entry in parent for new right child page <rp>
819 */
820 /* get/pin the parent page <sp> */
821 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
822 if (rc) {
823 XT_PUTPAGE(rcmp);
824 return rc;
825 }
826
827 /*
828 * The new key entry goes ONE AFTER the index of parent entry,
829 * because the split was to the right.
830 */
831 skip = parent->index + 1;
832
833 /*
834 * split or shift right remaining entries of the parent page
835 */
836 nextindex = le16_to_cpu(sp->header.nextindex);
837 /*
838 * parent page is full - split the parent page
839 */
840 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
841 /* init for parent page split */
842 split->mp = smp;
843 split->index = skip; /* index at insert */
844 split->flag = XAD_NEW;
845 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
846 split->len = JFS_SBI(ip->i_sb)->nbperpage;
847 split->addr = rcbn;
848
849 /* unpin previous right child page */
850 XT_PUTPAGE(rcmp);
851
852 /* The split routines insert the new entry,
853 * and acquire txLock as appropriate.
854 * return <rp> pinned and its block number <rpbn>.
855 */
856 rc = (sp->header.flag & BT_ROOT) ?
857 xtSplitRoot(tid, ip, split, &rmp) :
858 xtSplitPage(tid, ip, split, &rmp, &rbn);
859 if (rc) {
860 XT_PUTPAGE(smp);
861 return rc;
862 }
863
864 XT_PUTPAGE(smp);
865 /* keep new child page <rp> pinned */
866 }
867 /*
868 * parent page is not full - insert in parent page
869 */
870 else {
871 /*
872 * insert router entry in parent for the right child
873 * page from the first entry of the right child page:
874 */
875 /*
876 * acquire a transaction lock on the parent page;
877 *
878 * action: router xad insertion;
879 */
880 BT_MARK_DIRTY(smp, ip);
881
882 /*
883 * if insert into middle, shift right remaining entries
884 */
885 if (skip < nextindex)
886 memmove(&sp->xad[skip + 1], &sp->xad[skip],
887 (nextindex -
888 skip) << L2XTSLOTSIZE);
889
890 /* insert the router entry */
891 xad = &sp->xad[skip];
892 XT_PUTENTRY(xad, XAD_NEW,
893 offsetXAD(&rcp->xad[XTENTRYSTART]),
894 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
895
896 /* advance next available entry index. */
897 le16_add_cpu(&sp->header.nextindex, 1);
898
899 /* Don't log it if there are no links to the file */
900 if (!test_cflag(COMMIT_Nolink, ip)) {
901 tlck = txLock(tid, ip, smp,
902 tlckXTREE | tlckGROW);
903 xtlck = (struct xtlock *) & tlck->lock;
904 xtlck->lwm.offset = (xtlck->lwm.offset) ?
905 min(skip, (int)xtlck->lwm.offset) : skip;
906 xtlck->lwm.length =
907 le16_to_cpu(sp->header.nextindex) -
908 xtlck->lwm.offset;
909 }
910
911 /* unpin parent page */
912 XT_PUTPAGE(smp);
913
914 /* exit propagate up */
915 break;
916 }
917 }
918
919 /* unpin current right page */
920 XT_PUTPAGE(rmp);
921
922 return 0;
923}
924
925
926/*
927 * xtSplitPage()
928 *
929 * function:
930 * split a full non-root page into
931 * original/split/left page and new right page
932 * i.e., the original/split page remains as left page.
933 *
934 * parameter:
935 * int tid,
936 * struct inode *ip,
937 * struct xtsplit *split,
938 * struct metapage **rmpp,
939 * u64 *rbnp,
940 *
941 * return:
942 * Pointer to page in which to insert or NULL on error.
943 */
944static int
945xtSplitPage(tid_t tid, struct inode *ip,
946 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
947{
948 int rc = 0;
949 struct metapage *smp;
950 xtpage_t *sp;
951 struct metapage *rmp;
952 xtpage_t *rp; /* new right page allocated */
953 s64 rbn; /* new right page block number */
954 struct metapage *mp;
955 xtpage_t *p;
956 s64 nextbn;
957 int skip, maxentry, middle, righthalf, n;
958 xad_t *xad;
959 struct pxdlist *pxdlist;
960 pxd_t *pxd;
961 struct tlock *tlck;
962 struct xtlock *sxtlck = NULL, *rxtlck = NULL;
963 int quota_allocation = 0;
964
965 smp = split->mp;
966 sp = XT_PAGE(ip, smp);
967
968 INCREMENT(xtStat.split);
969
970 pxdlist = split->pxdlist;
971 pxd = &pxdlist->pxd[pxdlist->npxd];
972 pxdlist->npxd++;
973 rbn = addressPXD(pxd);
974
975 /* Allocate blocks to quota. */
976 rc = dquot_alloc_block(ip, lengthPXD(pxd));
977 if (rc)
978 goto clean_up;
979
980 quota_allocation += lengthPXD(pxd);
981
982 /*
983 * allocate the new right page for the split
984 */
985 rmp = get_metapage(ip, rbn, PSIZE, 1);
986 if (rmp == NULL) {
987 rc = -EIO;
988 goto clean_up;
989 }
990
991 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
992
993 BT_MARK_DIRTY(rmp, ip);
994 /*
995 * action: new page;
996 */
997
998 rp = (xtpage_t *) rmp->data;
999 rp->header.self = *pxd;
1000 rp->header.flag = sp->header.flag & BT_TYPE;
1001 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1002 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1003
1004 BT_MARK_DIRTY(smp, ip);
1005 /* Don't log it if there are no links to the file */
1006 if (!test_cflag(COMMIT_Nolink, ip)) {
1007 /*
1008 * acquire a transaction lock on the new right page;
1009 */
1010 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1011 rxtlck = (struct xtlock *) & tlck->lock;
1012 rxtlck->lwm.offset = XTENTRYSTART;
1013 /*
1014 * acquire a transaction lock on the split page
1015 */
1016 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1017 sxtlck = (struct xtlock *) & tlck->lock;
1018 }
1019
1020 /*
1021 * initialize/update sibling pointers of <sp> and <rp>
1022 */
1023 nextbn = le64_to_cpu(sp->header.next);
1024 rp->header.next = cpu_to_le64(nextbn);
1025 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1026 sp->header.next = cpu_to_le64(rbn);
1027
1028 skip = split->index;
1029
1030 /*
1031 * sequential append at tail (after last entry of last page)
1032 *
1033 * if splitting the last page on a level because of appending
1034 * a entry to it (skip is maxentry), it's likely that the access is
1035 * sequential. adding an empty page on the side of the level is less
1036 * work and can push the fill factor much higher than normal.
1037 * if we're wrong it's no big deal - we will do the split the right
1038 * way next time.
1039 * (it may look like it's equally easy to do a similar hack for
1040 * reverse sorted data, that is, split the tree left, but it's not.
1041 * Be my guest.)
1042 */
1043 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1044 /*
1045 * acquire a transaction lock on the new/right page;
1046 *
1047 * action: xad insertion;
1048 */
1049 /* insert entry at the first entry of the new right page */
1050 xad = &rp->xad[XTENTRYSTART];
1051 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1052 split->addr);
1053
1054 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1055
1056 if (!test_cflag(COMMIT_Nolink, ip)) {
1057 /* rxtlck->lwm.offset = XTENTRYSTART; */
1058 rxtlck->lwm.length = 1;
1059 }
1060
1061 *rmpp = rmp;
1062 *rbnp = rbn;
1063
1064 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1065 return 0;
1066 }
1067
1068 /*
1069 * non-sequential insert (at possibly middle page)
1070 */
1071
1072 /*
1073 * update previous pointer of old next/right page of <sp>
1074 */
1075 if (nextbn != 0) {
1076 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1077 if (rc) {
1078 XT_PUTPAGE(rmp);
1079 goto clean_up;
1080 }
1081
1082 BT_MARK_DIRTY(mp, ip);
1083 /*
1084 * acquire a transaction lock on the next page;
1085 *
1086 * action:sibling pointer update;
1087 */
1088 if (!test_cflag(COMMIT_Nolink, ip))
1089 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1090
1091 p->header.prev = cpu_to_le64(rbn);
1092
1093 /* sibling page may have been updated previously, or
1094 * it may be updated later;
1095 */
1096
1097 XT_PUTPAGE(mp);
1098 }
1099
1100 /*
1101 * split the data between the split and new/right pages
1102 */
1103 maxentry = le16_to_cpu(sp->header.maxentry);
1104 middle = maxentry >> 1;
1105 righthalf = maxentry - middle;
1106
1107 /*
1108 * skip index in old split/left page - insert into left page:
1109 */
1110 if (skip <= middle) {
1111 /* move right half of split page to the new right page */
1112 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1113 righthalf << L2XTSLOTSIZE);
1114
1115 /* shift right tail of left half to make room for new entry */
1116 if (skip < middle)
1117 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1118 (middle - skip) << L2XTSLOTSIZE);
1119
1120 /* insert new entry */
1121 xad = &sp->xad[skip];
1122 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1123 split->addr);
1124
1125 /* update page header */
1126 sp->header.nextindex = cpu_to_le16(middle + 1);
1127 if (!test_cflag(COMMIT_Nolink, ip)) {
1128 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1129 min(skip, (int)sxtlck->lwm.offset) : skip;
1130 }
1131
1132 rp->header.nextindex =
1133 cpu_to_le16(XTENTRYSTART + righthalf);
1134 }
1135 /*
1136 * skip index in new right page - insert into right page:
1137 */
1138 else {
1139 /* move left head of right half to right page */
1140 n = skip - middle;
1141 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1142 n << L2XTSLOTSIZE);
1143
1144 /* insert new entry */
1145 n += XTENTRYSTART;
1146 xad = &rp->xad[n];
1147 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1148 split->addr);
1149
1150 /* move right tail of right half to right page */
1151 if (skip < maxentry)
1152 memmove(&rp->xad[n + 1], &sp->xad[skip],
1153 (maxentry - skip) << L2XTSLOTSIZE);
1154
1155 /* update page header */
1156 sp->header.nextindex = cpu_to_le16(middle);
1157 if (!test_cflag(COMMIT_Nolink, ip)) {
1158 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1159 min(middle, (int)sxtlck->lwm.offset) : middle;
1160 }
1161
1162 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1163 righthalf + 1);
1164 }
1165
1166 if (!test_cflag(COMMIT_Nolink, ip)) {
1167 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1168 sxtlck->lwm.offset;
1169
1170 /* rxtlck->lwm.offset = XTENTRYSTART; */
1171 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1172 XTENTRYSTART;
1173 }
1174
1175 *rmpp = rmp;
1176 *rbnp = rbn;
1177
1178 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1179 return rc;
1180
1181 clean_up:
1182
1183 /* Rollback quota allocation. */
1184 if (quota_allocation)
1185 dquot_free_block(ip, quota_allocation);
1186
1187 return (rc);
1188}
1189
1190
1191/*
1192 * xtSplitRoot()
1193 *
1194 * function:
1195 * split the full root page into original/root/split page and new
1196 * right page
1197 * i.e., root remains fixed in tree anchor (inode) and the root is
1198 * copied to a single new right child page since root page <<
1199 * non-root page, and the split root page contains a single entry
1200 * for the new right child page.
1201 *
1202 * parameter:
1203 * int tid,
1204 * struct inode *ip,
1205 * struct xtsplit *split,
1206 * struct metapage **rmpp)
1207 *
1208 * return:
1209 * Pointer to page in which to insert or NULL on error.
1210 */
1211static int
1212xtSplitRoot(tid_t tid,
1213 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1214{
1215 xtpage_t *sp;
1216 struct metapage *rmp;
1217 xtpage_t *rp;
1218 s64 rbn;
1219 int skip, nextindex;
1220 xad_t *xad;
1221 pxd_t *pxd;
1222 struct pxdlist *pxdlist;
1223 struct tlock *tlck;
1224 struct xtlock *xtlck;
1225 int rc;
1226
1227 sp = &JFS_IP(ip)->i_xtroot;
1228
1229 INCREMENT(xtStat.split);
1230
1231 /*
1232 * allocate a single (right) child page
1233 */
1234 pxdlist = split->pxdlist;
1235 pxd = &pxdlist->pxd[pxdlist->npxd];
1236 pxdlist->npxd++;
1237 rbn = addressPXD(pxd);
1238 rmp = get_metapage(ip, rbn, PSIZE, 1);
1239 if (rmp == NULL)
1240 return -EIO;
1241
1242 /* Allocate blocks to quota. */
1243 rc = dquot_alloc_block(ip, lengthPXD(pxd));
1244 if (rc) {
1245 release_metapage(rmp);
1246 return rc;
1247 }
1248
1249 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1250
1251 /*
1252 * acquire a transaction lock on the new right page;
1253 *
1254 * action: new page;
1255 */
1256 BT_MARK_DIRTY(rmp, ip);
1257
1258 rp = (xtpage_t *) rmp->data;
1259 rp->header.flag =
1260 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1261 rp->header.self = *pxd;
1262 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1263 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1264
1265 /* initialize sibling pointers */
1266 rp->header.next = 0;
1267 rp->header.prev = 0;
1268
1269 /*
1270 * copy the in-line root page into new right page extent
1271 */
1272 nextindex = le16_to_cpu(sp->header.maxentry);
1273 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1274 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1275
1276 /*
1277 * insert the new entry into the new right/child page
1278 * (skip index in the new right page will not change)
1279 */
1280 skip = split->index;
1281 /* if insert into middle, shift right remaining entries */
1282 if (skip != nextindex)
1283 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1284 (nextindex - skip) * sizeof(xad_t));
1285
1286 xad = &rp->xad[skip];
1287 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1288
1289 /* update page header */
1290 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1291
1292 if (!test_cflag(COMMIT_Nolink, ip)) {
1293 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1294 xtlck = (struct xtlock *) & tlck->lock;
1295 xtlck->lwm.offset = XTENTRYSTART;
1296 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1297 XTENTRYSTART;
1298 }
1299
1300 /*
1301 * reset the root
1302 *
1303 * init root with the single entry for the new right page
1304 * set the 1st entry offset to 0, which force the left-most key
1305 * at any level of the tree to be less than any search key.
1306 */
1307 /*
1308 * acquire a transaction lock on the root page (in-memory inode);
1309 *
1310 * action: root split;
1311 */
1312 BT_MARK_DIRTY(split->mp, ip);
1313
1314 xad = &sp->xad[XTENTRYSTART];
1315 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1316
1317 /* update page header of root */
1318 sp->header.flag &= ~BT_LEAF;
1319 sp->header.flag |= BT_INTERNAL;
1320
1321 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1322
1323 if (!test_cflag(COMMIT_Nolink, ip)) {
1324 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1325 xtlck = (struct xtlock *) & tlck->lock;
1326 xtlck->lwm.offset = XTENTRYSTART;
1327 xtlck->lwm.length = 1;
1328 }
1329
1330 *rmpp = rmp;
1331
1332 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1333 return 0;
1334}
1335
1336
1337/*
1338 * xtExtend()
1339 *
1340 * function: extend in-place;
1341 *
1342 * note: existing extent may or may not have been committed.
1343 * caller is responsible for pager buffer cache update, and
1344 * working block allocation map update;
1345 * update pmap: alloc whole extended extent;
1346 */
1347int xtExtend(tid_t tid, /* transaction id */
1348 struct inode *ip, s64 xoff, /* delta extent offset */
1349 s32 xlen, /* delta extent length */
1350 int flag)
1351{
1352 int rc = 0;
1353 int cmp;
1354 struct metapage *mp; /* meta-page buffer */
1355 xtpage_t *p; /* base B+-tree index page */
1356 s64 bn;
1357 int index, nextindex, len;
1358 struct btstack btstack; /* traverse stack */
1359 struct xtsplit split; /* split information */
1360 xad_t *xad;
1361 s64 xaddr;
1362 struct tlock *tlck;
1363 struct xtlock *xtlck = NULL;
1364
1365 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1366
1367 /* there must exist extent to be extended */
1368 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1369 return rc;
1370
1371 /* retrieve search result */
1372 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1373
1374 if (cmp != 0) {
1375 XT_PUTPAGE(mp);
1376 jfs_error(ip->i_sb, "xtSearch did not find extent\n");
1377 return -EIO;
1378 }
1379
1380 /* extension must be contiguous */
1381 xad = &p->xad[index];
1382 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1383 XT_PUTPAGE(mp);
1384 jfs_error(ip->i_sb, "extension is not contiguous\n");
1385 return -EIO;
1386 }
1387
1388 /*
1389 * acquire a transaction lock on the leaf page;
1390 *
1391 * action: xad insertion/extension;
1392 */
1393 BT_MARK_DIRTY(mp, ip);
1394 if (!test_cflag(COMMIT_Nolink, ip)) {
1395 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1396 xtlck = (struct xtlock *) & tlck->lock;
1397 }
1398
1399 /* extend will overflow extent ? */
1400 xlen = lengthXAD(xad) + xlen;
1401 if ((len = xlen - MAXXLEN) <= 0)
1402 goto extendOld;
1403
1404 /*
1405 * extent overflow: insert entry for new extent
1406 */
1407//insertNew:
1408 xoff = offsetXAD(xad) + MAXXLEN;
1409 xaddr = addressXAD(xad) + MAXXLEN;
1410 nextindex = le16_to_cpu(p->header.nextindex);
1411
1412 /*
1413 * if the leaf page is full, insert the new entry and
1414 * propagate up the router entry for the new page from split
1415 *
1416 * The xtSplitUp() will insert the entry and unpin the leaf page.
1417 */
1418 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1419 /* xtSpliUp() unpins leaf pages */
1420 split.mp = mp;
1421 split.index = index + 1;
1422 split.flag = XAD_NEW;
1423 split.off = xoff; /* split offset */
1424 split.len = len;
1425 split.addr = xaddr;
1426 split.pxdlist = NULL;
1427 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1428 return rc;
1429
1430 /* get back old page */
1431 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1432 if (rc)
1433 return rc;
1434 /*
1435 * if leaf root has been split, original root has been
1436 * copied to new child page, i.e., original entry now
1437 * resides on the new child page;
1438 */
1439 if (p->header.flag & BT_INTERNAL) {
1440 ASSERT(p->header.nextindex ==
1441 cpu_to_le16(XTENTRYSTART + 1));
1442 xad = &p->xad[XTENTRYSTART];
1443 bn = addressXAD(xad);
1444 XT_PUTPAGE(mp);
1445
1446 /* get new child page */
1447 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1448 if (rc)
1449 return rc;
1450
1451 BT_MARK_DIRTY(mp, ip);
1452 if (!test_cflag(COMMIT_Nolink, ip)) {
1453 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1454 xtlck = (struct xtlock *) & tlck->lock;
1455 }
1456 }
1457 }
1458 /*
1459 * insert the new entry into the leaf page
1460 */
1461 else {
1462 /* insert the new entry: mark the entry NEW */
1463 xad = &p->xad[index + 1];
1464 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1465
1466 /* advance next available entry index */
1467 le16_add_cpu(&p->header.nextindex, 1);
1468 }
1469
1470 /* get back old entry */
1471 xad = &p->xad[index];
1472 xlen = MAXXLEN;
1473
1474 /*
1475 * extend old extent
1476 */
1477 extendOld:
1478 XADlength(xad, xlen);
1479 if (!(xad->flag & XAD_NEW))
1480 xad->flag |= XAD_EXTENDED;
1481
1482 if (!test_cflag(COMMIT_Nolink, ip)) {
1483 xtlck->lwm.offset =
1484 (xtlck->lwm.offset) ? min(index,
1485 (int)xtlck->lwm.offset) : index;
1486 xtlck->lwm.length =
1487 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1488 }
1489
1490 /* unpin the leaf page */
1491 XT_PUTPAGE(mp);
1492
1493 return rc;
1494}
1495
1496#ifdef _NOTYET
1497/*
1498 * xtTailgate()
1499 *
1500 * function: split existing 'tail' extent
1501 * (split offset >= start offset of tail extent), and
1502 * relocate and extend the split tail half;
1503 *
1504 * note: existing extent may or may not have been committed.
1505 * caller is responsible for pager buffer cache update, and
1506 * working block allocation map update;
1507 * update pmap: free old split tail extent, alloc new extent;
1508 */
1509int xtTailgate(tid_t tid, /* transaction id */
1510 struct inode *ip, s64 xoff, /* split/new extent offset */
1511 s32 xlen, /* new extent length */
1512 s64 xaddr, /* new extent address */
1513 int flag)
1514{
1515 int rc = 0;
1516 int cmp;
1517 struct metapage *mp; /* meta-page buffer */
1518 xtpage_t *p; /* base B+-tree index page */
1519 s64 bn;
1520 int index, nextindex, llen, rlen;
1521 struct btstack btstack; /* traverse stack */
1522 struct xtsplit split; /* split information */
1523 xad_t *xad;
1524 struct tlock *tlck;
1525 struct xtlock *xtlck = 0;
1526 struct tlock *mtlck;
1527 struct maplock *pxdlock;
1528
1529/*
1530printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1531 (ulong)xoff, xlen, (ulong)xaddr);
1532*/
1533
1534 /* there must exist extent to be tailgated */
1535 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1536 return rc;
1537
1538 /* retrieve search result */
1539 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1540
1541 if (cmp != 0) {
1542 XT_PUTPAGE(mp);
1543 jfs_error(ip->i_sb, "couldn't find extent\n");
1544 return -EIO;
1545 }
1546
1547 /* entry found must be last entry */
1548 nextindex = le16_to_cpu(p->header.nextindex);
1549 if (index != nextindex - 1) {
1550 XT_PUTPAGE(mp);
1551 jfs_error(ip->i_sb, "the entry found is not the last entry\n");
1552 return -EIO;
1553 }
1554
1555 BT_MARK_DIRTY(mp, ip);
1556 /*
1557 * acquire tlock of the leaf page containing original entry
1558 */
1559 if (!test_cflag(COMMIT_Nolink, ip)) {
1560 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1561 xtlck = (struct xtlock *) & tlck->lock;
1562 }
1563
1564 /* completely replace extent ? */
1565 xad = &p->xad[index];
1566/*
1567printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1568 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1569*/
1570 if ((llen = xoff - offsetXAD(xad)) == 0)
1571 goto updateOld;
1572
1573 /*
1574 * partially replace extent: insert entry for new extent
1575 */
1576//insertNew:
1577 /*
1578 * if the leaf page is full, insert the new entry and
1579 * propagate up the router entry for the new page from split
1580 *
1581 * The xtSplitUp() will insert the entry and unpin the leaf page.
1582 */
1583 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1584 /* xtSpliUp() unpins leaf pages */
1585 split.mp = mp;
1586 split.index = index + 1;
1587 split.flag = XAD_NEW;
1588 split.off = xoff; /* split offset */
1589 split.len = xlen;
1590 split.addr = xaddr;
1591 split.pxdlist = NULL;
1592 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1593 return rc;
1594
1595 /* get back old page */
1596 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1597 if (rc)
1598 return rc;
1599 /*
1600 * if leaf root has been split, original root has been
1601 * copied to new child page, i.e., original entry now
1602 * resides on the new child page;
1603 */
1604 if (p->header.flag & BT_INTERNAL) {
1605 ASSERT(p->header.nextindex ==
1606 cpu_to_le16(XTENTRYSTART + 1));
1607 xad = &p->xad[XTENTRYSTART];
1608 bn = addressXAD(xad);
1609 XT_PUTPAGE(mp);
1610
1611 /* get new child page */
1612 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1613 if (rc)
1614 return rc;
1615
1616 BT_MARK_DIRTY(mp, ip);
1617 if (!test_cflag(COMMIT_Nolink, ip)) {
1618 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1619 xtlck = (struct xtlock *) & tlck->lock;
1620 }
1621 }
1622 }
1623 /*
1624 * insert the new entry into the leaf page
1625 */
1626 else {
1627 /* insert the new entry: mark the entry NEW */
1628 xad = &p->xad[index + 1];
1629 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1630
1631 /* advance next available entry index */
1632 le16_add_cpu(&p->header.nextindex, 1);
1633 }
1634
1635 /* get back old XAD */
1636 xad = &p->xad[index];
1637
1638 /*
1639 * truncate/relocate old extent at split offset
1640 */
1641 updateOld:
1642 /* update dmap for old/committed/truncated extent */
1643 rlen = lengthXAD(xad) - llen;
1644 if (!(xad->flag & XAD_NEW)) {
1645 /* free from PWMAP at commit */
1646 if (!test_cflag(COMMIT_Nolink, ip)) {
1647 mtlck = txMaplock(tid, ip, tlckMAP);
1648 pxdlock = (struct maplock *) & mtlck->lock;
1649 pxdlock->flag = mlckFREEPXD;
1650 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1651 PXDlength(&pxdlock->pxd, rlen);
1652 pxdlock->index = 1;
1653 }
1654 } else
1655 /* free from WMAP */
1656 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1657
1658 if (llen)
1659 /* truncate */
1660 XADlength(xad, llen);
1661 else
1662 /* replace */
1663 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1664
1665 if (!test_cflag(COMMIT_Nolink, ip)) {
1666 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1667 min(index, (int)xtlck->lwm.offset) : index;
1668 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1669 xtlck->lwm.offset;
1670 }
1671
1672 /* unpin the leaf page */
1673 XT_PUTPAGE(mp);
1674
1675 return rc;
1676}
1677#endif /* _NOTYET */
1678
1679/*
1680 * xtUpdate()
1681 *
1682 * function: update XAD;
1683 *
1684 * update extent for allocated_but_not_recorded or
1685 * compressed extent;
1686 *
1687 * parameter:
1688 * nxad - new XAD;
1689 * logical extent of the specified XAD must be completely
1690 * contained by an existing XAD;
1691 */
1692int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1693{ /* new XAD */
1694 int rc = 0;
1695 int cmp;
1696 struct metapage *mp; /* meta-page buffer */
1697 xtpage_t *p; /* base B+-tree index page */
1698 s64 bn;
1699 int index0, index, newindex, nextindex;
1700 struct btstack btstack; /* traverse stack */
1701 struct xtsplit split; /* split information */
1702 xad_t *xad, *lxad, *rxad;
1703 int xflag;
1704 s64 nxoff, xoff;
1705 int nxlen, xlen, lxlen, rxlen;
1706 s64 nxaddr, xaddr;
1707 struct tlock *tlck;
1708 struct xtlock *xtlck = NULL;
1709 int newpage = 0;
1710
1711 /* there must exist extent to be tailgated */
1712 nxoff = offsetXAD(nxad);
1713 nxlen = lengthXAD(nxad);
1714 nxaddr = addressXAD(nxad);
1715
1716 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1717 return rc;
1718
1719 /* retrieve search result */
1720 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1721
1722 if (cmp != 0) {
1723 XT_PUTPAGE(mp);
1724 jfs_error(ip->i_sb, "Could not find extent\n");
1725 return -EIO;
1726 }
1727
1728 BT_MARK_DIRTY(mp, ip);
1729 /*
1730 * acquire tlock of the leaf page containing original entry
1731 */
1732 if (!test_cflag(COMMIT_Nolink, ip)) {
1733 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1734 xtlck = (struct xtlock *) & tlck->lock;
1735 }
1736
1737 xad = &p->xad[index0];
1738 xflag = xad->flag;
1739 xoff = offsetXAD(xad);
1740 xlen = lengthXAD(xad);
1741 xaddr = addressXAD(xad);
1742
1743 /* nXAD must be completely contained within XAD */
1744 if ((xoff > nxoff) ||
1745 (nxoff + nxlen > xoff + xlen)) {
1746 XT_PUTPAGE(mp);
1747 jfs_error(ip->i_sb,
1748 "nXAD in not completely contained within XAD\n");
1749 return -EIO;
1750 }
1751
1752 index = index0;
1753 newindex = index + 1;
1754 nextindex = le16_to_cpu(p->header.nextindex);
1755
1756#ifdef _JFS_WIP_NOCOALESCE
1757 if (xoff < nxoff)
1758 goto updateRight;
1759
1760 /*
1761 * replace XAD with nXAD
1762 */
1763 replace: /* (nxoff == xoff) */
1764 if (nxlen == xlen) {
1765 /* replace XAD with nXAD:recorded */
1766 *xad = *nxad;
1767 xad->flag = xflag & ~XAD_NOTRECORDED;
1768
1769 goto out;
1770 } else /* (nxlen < xlen) */
1771 goto updateLeft;
1772#endif /* _JFS_WIP_NOCOALESCE */
1773
1774/* #ifdef _JFS_WIP_COALESCE */
1775 if (xoff < nxoff)
1776 goto coalesceRight;
1777
1778 /*
1779 * coalesce with left XAD
1780 */
1781//coalesceLeft: /* (xoff == nxoff) */
1782 /* is XAD first entry of page ? */
1783 if (index == XTENTRYSTART)
1784 goto replace;
1785
1786 /* is nXAD logically and physically contiguous with lXAD ? */
1787 lxad = &p->xad[index - 1];
1788 lxlen = lengthXAD(lxad);
1789 if (!(lxad->flag & XAD_NOTRECORDED) &&
1790 (nxoff == offsetXAD(lxad) + lxlen) &&
1791 (nxaddr == addressXAD(lxad) + lxlen) &&
1792 (lxlen + nxlen < MAXXLEN)) {
1793 /* extend right lXAD */
1794 index0 = index - 1;
1795 XADlength(lxad, lxlen + nxlen);
1796
1797 /* If we just merged two extents together, need to make sure the
1798 * right extent gets logged. If the left one is marked XAD_NEW,
1799 * then we know it will be logged. Otherwise, mark as
1800 * XAD_EXTENDED
1801 */
1802 if (!(lxad->flag & XAD_NEW))
1803 lxad->flag |= XAD_EXTENDED;
1804
1805 if (xlen > nxlen) {
1806 /* truncate XAD */
1807 XADoffset(xad, xoff + nxlen);
1808 XADlength(xad, xlen - nxlen);
1809 XADaddress(xad, xaddr + nxlen);
1810 goto out;
1811 } else { /* (xlen == nxlen) */
1812
1813 /* remove XAD */
1814 if (index < nextindex - 1)
1815 memmove(&p->xad[index], &p->xad[index + 1],
1816 (nextindex - index -
1817 1) << L2XTSLOTSIZE);
1818
1819 p->header.nextindex =
1820 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1821 1);
1822
1823 index = index0;
1824 newindex = index + 1;
1825 nextindex = le16_to_cpu(p->header.nextindex);
1826 xoff = nxoff = offsetXAD(lxad);
1827 xlen = nxlen = lxlen + nxlen;
1828 xaddr = nxaddr = addressXAD(lxad);
1829 goto coalesceRight;
1830 }
1831 }
1832
1833 /*
1834 * replace XAD with nXAD
1835 */
1836 replace: /* (nxoff == xoff) */
1837 if (nxlen == xlen) {
1838 /* replace XAD with nXAD:recorded */
1839 *xad = *nxad;
1840 xad->flag = xflag & ~XAD_NOTRECORDED;
1841
1842 goto coalesceRight;
1843 } else /* (nxlen < xlen) */
1844 goto updateLeft;
1845
1846 /*
1847 * coalesce with right XAD
1848 */
1849 coalesceRight: /* (xoff <= nxoff) */
1850 /* is XAD last entry of page ? */
1851 if (newindex == nextindex) {
1852 if (xoff == nxoff)
1853 goto out;
1854 goto updateRight;
1855 }
1856
1857 /* is nXAD logically and physically contiguous with rXAD ? */
1858 rxad = &p->xad[index + 1];
1859 rxlen = lengthXAD(rxad);
1860 if (!(rxad->flag & XAD_NOTRECORDED) &&
1861 (nxoff + nxlen == offsetXAD(rxad)) &&
1862 (nxaddr + nxlen == addressXAD(rxad)) &&
1863 (rxlen + nxlen < MAXXLEN)) {
1864 /* extend left rXAD */
1865 XADoffset(rxad, nxoff);
1866 XADlength(rxad, rxlen + nxlen);
1867 XADaddress(rxad, nxaddr);
1868
1869 /* If we just merged two extents together, need to make sure
1870 * the left extent gets logged. If the right one is marked
1871 * XAD_NEW, then we know it will be logged. Otherwise, mark as
1872 * XAD_EXTENDED
1873 */
1874 if (!(rxad->flag & XAD_NEW))
1875 rxad->flag |= XAD_EXTENDED;
1876
1877 if (xlen > nxlen)
1878 /* truncate XAD */
1879 XADlength(xad, xlen - nxlen);
1880 else { /* (xlen == nxlen) */
1881
1882 /* remove XAD */
1883 memmove(&p->xad[index], &p->xad[index + 1],
1884 (nextindex - index - 1) << L2XTSLOTSIZE);
1885
1886 p->header.nextindex =
1887 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1888 1);
1889 }
1890
1891 goto out;
1892 } else if (xoff == nxoff)
1893 goto out;
1894
1895 if (xoff >= nxoff) {
1896 XT_PUTPAGE(mp);
1897 jfs_error(ip->i_sb, "xoff >= nxoff\n");
1898 return -EIO;
1899 }
1900/* #endif _JFS_WIP_COALESCE */
1901
1902 /*
1903 * split XAD into (lXAD, nXAD):
1904 *
1905 * |---nXAD--->
1906 * --|----------XAD----------|--
1907 * |-lXAD-|
1908 */
1909 updateRight: /* (xoff < nxoff) */
1910 /* truncate old XAD as lXAD:not_recorded */
1911 xad = &p->xad[index];
1912 XADlength(xad, nxoff - xoff);
1913
1914 /* insert nXAD:recorded */
1915 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1916
1917 /* xtSpliUp() unpins leaf pages */
1918 split.mp = mp;
1919 split.index = newindex;
1920 split.flag = xflag & ~XAD_NOTRECORDED;
1921 split.off = nxoff;
1922 split.len = nxlen;
1923 split.addr = nxaddr;
1924 split.pxdlist = NULL;
1925 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1926 return rc;
1927
1928 /* get back old page */
1929 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1930 if (rc)
1931 return rc;
1932 /*
1933 * if leaf root has been split, original root has been
1934 * copied to new child page, i.e., original entry now
1935 * resides on the new child page;
1936 */
1937 if (p->header.flag & BT_INTERNAL) {
1938 ASSERT(p->header.nextindex ==
1939 cpu_to_le16(XTENTRYSTART + 1));
1940 xad = &p->xad[XTENTRYSTART];
1941 bn = addressXAD(xad);
1942 XT_PUTPAGE(mp);
1943
1944 /* get new child page */
1945 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1946 if (rc)
1947 return rc;
1948
1949 BT_MARK_DIRTY(mp, ip);
1950 if (!test_cflag(COMMIT_Nolink, ip)) {
1951 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1952 xtlck = (struct xtlock *) & tlck->lock;
1953 }
1954 } else {
1955 /* is nXAD on new page ? */
1956 if (newindex >
1957 (le16_to_cpu(p->header.maxentry) >> 1)) {
1958 newindex =
1959 newindex -
1960 le16_to_cpu(p->header.nextindex) +
1961 XTENTRYSTART;
1962 newpage = 1;
1963 }
1964 }
1965 } else {
1966 /* if insert into middle, shift right remaining entries */
1967 if (newindex < nextindex)
1968 memmove(&p->xad[newindex + 1], &p->xad[newindex],
1969 (nextindex - newindex) << L2XTSLOTSIZE);
1970
1971 /* insert the entry */
1972 xad = &p->xad[newindex];
1973 *xad = *nxad;
1974 xad->flag = xflag & ~XAD_NOTRECORDED;
1975
1976 /* advance next available entry index. */
1977 p->header.nextindex =
1978 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1979 }
1980
1981 /*
1982 * does nXAD force 3-way split ?
1983 *
1984 * |---nXAD--->|
1985 * --|----------XAD-------------|--
1986 * |-lXAD-| |-rXAD -|
1987 */
1988 if (nxoff + nxlen == xoff + xlen)
1989 goto out;
1990
1991 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
1992 if (newpage) {
1993 /* close out old page */
1994 if (!test_cflag(COMMIT_Nolink, ip)) {
1995 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1996 min(index0, (int)xtlck->lwm.offset) : index0;
1997 xtlck->lwm.length =
1998 le16_to_cpu(p->header.nextindex) -
1999 xtlck->lwm.offset;
2000 }
2001
2002 bn = le64_to_cpu(p->header.next);
2003 XT_PUTPAGE(mp);
2004
2005 /* get new right page */
2006 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2007 if (rc)
2008 return rc;
2009
2010 BT_MARK_DIRTY(mp, ip);
2011 if (!test_cflag(COMMIT_Nolink, ip)) {
2012 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2013 xtlck = (struct xtlock *) & tlck->lock;
2014 }
2015
2016 index0 = index = newindex;
2017 } else
2018 index++;
2019
2020 newindex = index + 1;
2021 nextindex = le16_to_cpu(p->header.nextindex);
2022 xlen = xlen - (nxoff - xoff);
2023 xoff = nxoff;
2024 xaddr = nxaddr;
2025
2026 /* recompute split pages */
2027 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2028 XT_PUTPAGE(mp);
2029
2030 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2031 return rc;
2032
2033 /* retrieve search result */
2034 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2035
2036 if (cmp != 0) {
2037 XT_PUTPAGE(mp);
2038 jfs_error(ip->i_sb, "xtSearch failed\n");
2039 return -EIO;
2040 }
2041
2042 if (index0 != index) {
2043 XT_PUTPAGE(mp);
2044 jfs_error(ip->i_sb, "unexpected value of index\n");
2045 return -EIO;
2046 }
2047 }
2048
2049 /*
2050 * split XAD into (nXAD, rXAD)
2051 *
2052 * ---nXAD---|
2053 * --|----------XAD----------|--
2054 * |-rXAD-|
2055 */
2056 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2057 /* update old XAD with nXAD:recorded */
2058 xad = &p->xad[index];
2059 *xad = *nxad;
2060 xad->flag = xflag & ~XAD_NOTRECORDED;
2061
2062 /* insert rXAD:not_recorded */
2063 xoff = xoff + nxlen;
2064 xlen = xlen - nxlen;
2065 xaddr = xaddr + nxlen;
2066 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2067/*
2068printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2069*/
2070 /* xtSpliUp() unpins leaf pages */
2071 split.mp = mp;
2072 split.index = newindex;
2073 split.flag = xflag;
2074 split.off = xoff;
2075 split.len = xlen;
2076 split.addr = xaddr;
2077 split.pxdlist = NULL;
2078 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2079 return rc;
2080
2081 /* get back old page */
2082 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2083 if (rc)
2084 return rc;
2085
2086 /*
2087 * if leaf root has been split, original root has been
2088 * copied to new child page, i.e., original entry now
2089 * resides on the new child page;
2090 */
2091 if (p->header.flag & BT_INTERNAL) {
2092 ASSERT(p->header.nextindex ==
2093 cpu_to_le16(XTENTRYSTART + 1));
2094 xad = &p->xad[XTENTRYSTART];
2095 bn = addressXAD(xad);
2096 XT_PUTPAGE(mp);
2097
2098 /* get new child page */
2099 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2100 if (rc)
2101 return rc;
2102
2103 BT_MARK_DIRTY(mp, ip);
2104 if (!test_cflag(COMMIT_Nolink, ip)) {
2105 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2106 xtlck = (struct xtlock *) & tlck->lock;
2107 }
2108 }
2109 } else {
2110 /* if insert into middle, shift right remaining entries */
2111 if (newindex < nextindex)
2112 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2113 (nextindex - newindex) << L2XTSLOTSIZE);
2114
2115 /* insert the entry */
2116 xad = &p->xad[newindex];
2117 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2118
2119 /* advance next available entry index. */
2120 p->header.nextindex =
2121 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2122 }
2123
2124 out:
2125 if (!test_cflag(COMMIT_Nolink, ip)) {
2126 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2127 min(index0, (int)xtlck->lwm.offset) : index0;
2128 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2129 xtlck->lwm.offset;
2130 }
2131
2132 /* unpin the leaf page */
2133 XT_PUTPAGE(mp);
2134
2135 return rc;
2136}
2137
2138
2139/*
2140 * xtAppend()
2141 *
2142 * function: grow in append mode from contiguous region specified ;
2143 *
2144 * parameter:
2145 * tid - transaction id;
2146 * ip - file object;
2147 * xflag - extent flag:
2148 * xoff - extent offset;
2149 * maxblocks - max extent length;
2150 * xlen - extent length (in/out);
2151 * xaddrp - extent address pointer (in/out):
2152 * flag -
2153 *
2154 * return:
2155 */
2156int xtAppend(tid_t tid, /* transaction id */
2157 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2158 s32 * xlenp, /* (in/out) */
2159 s64 * xaddrp, /* (in/out) */
2160 int flag)
2161{
2162 int rc = 0;
2163 struct metapage *mp; /* meta-page buffer */
2164 xtpage_t *p; /* base B+-tree index page */
2165 s64 bn, xaddr;
2166 int index, nextindex;
2167 struct btstack btstack; /* traverse stack */
2168 struct xtsplit split; /* split information */
2169 xad_t *xad;
2170 int cmp;
2171 struct tlock *tlck;
2172 struct xtlock *xtlck;
2173 int nsplit, nblocks, xlen;
2174 struct pxdlist pxdlist;
2175 pxd_t *pxd;
2176 s64 next;
2177
2178 xaddr = *xaddrp;
2179 xlen = *xlenp;
2180 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2181 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2182
2183 /*
2184 * search for the entry location at which to insert:
2185 *
2186 * xtFastSearch() and xtSearch() both returns (leaf page
2187 * pinned, index at which to insert).
2188 * n.b. xtSearch() may return index of maxentry of
2189 * the full page.
2190 */
2191 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2192 return rc;
2193
2194 /* retrieve search result */
2195 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2196
2197 if (cmp == 0) {
2198 rc = -EEXIST;
2199 goto out;
2200 }
2201
2202 if (next)
2203 xlen = min(xlen, (int)(next - xoff));
2204//insert:
2205 /*
2206 * insert entry for new extent
2207 */
2208 xflag |= XAD_NEW;
2209
2210 /*
2211 * if the leaf page is full, split the page and
2212 * propagate up the router entry for the new page from split
2213 *
2214 * The xtSplitUp() will insert the entry and unpin the leaf page.
2215 */
2216 nextindex = le16_to_cpu(p->header.nextindex);
2217 if (nextindex < le16_to_cpu(p->header.maxentry))
2218 goto insertLeaf;
2219
2220 /*
2221 * allocate new index blocks to cover index page split(s)
2222 */
2223 nsplit = btstack.nsplit;
2224 split.pxdlist = &pxdlist;
2225 pxdlist.maxnpxd = pxdlist.npxd = 0;
2226 pxd = &pxdlist.pxd[0];
2227 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2228 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2229 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2230 PXDaddress(pxd, xaddr);
2231 PXDlength(pxd, nblocks);
2232
2233 pxdlist.maxnpxd++;
2234
2235 continue;
2236 }
2237
2238 /* undo allocation */
2239
2240 goto out;
2241 }
2242
2243 xlen = min(xlen, maxblocks);
2244
2245 /*
2246 * allocate data extent requested
2247 */
2248 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2249 goto out;
2250
2251 split.mp = mp;
2252 split.index = index;
2253 split.flag = xflag;
2254 split.off = xoff;
2255 split.len = xlen;
2256 split.addr = xaddr;
2257 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2258 /* undo data extent allocation */
2259 dbFree(ip, *xaddrp, (s64) * xlenp);
2260
2261 return rc;
2262 }
2263
2264 *xaddrp = xaddr;
2265 *xlenp = xlen;
2266 return 0;
2267
2268 /*
2269 * insert the new entry into the leaf page
2270 */
2271 insertLeaf:
2272 /*
2273 * allocate data extent requested
2274 */
2275 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2276 goto out;
2277
2278 BT_MARK_DIRTY(mp, ip);
2279 /*
2280 * acquire a transaction lock on the leaf page;
2281 *
2282 * action: xad insertion/extension;
2283 */
2284 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2285 xtlck = (struct xtlock *) & tlck->lock;
2286
2287 /* insert the new entry: mark the entry NEW */
2288 xad = &p->xad[index];
2289 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2290
2291 /* advance next available entry index */
2292 le16_add_cpu(&p->header.nextindex, 1);
2293
2294 xtlck->lwm.offset =
2295 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2296 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2297 xtlck->lwm.offset;
2298
2299 *xaddrp = xaddr;
2300 *xlenp = xlen;
2301
2302 out:
2303 /* unpin the leaf page */
2304 XT_PUTPAGE(mp);
2305
2306 return rc;
2307}
2308#ifdef _STILL_TO_PORT
2309
2310/* - TBD for defragmentaion/reorganization -
2311 *
2312 * xtDelete()
2313 *
2314 * function:
2315 * delete the entry with the specified key.
2316 *
2317 * N.B.: whole extent of the entry is assumed to be deleted.
2318 *
2319 * parameter:
2320 *
2321 * return:
2322 * ENOENT: if the entry is not found.
2323 *
2324 * exception:
2325 */
2326int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2327{
2328 int rc = 0;
2329 struct btstack btstack;
2330 int cmp;
2331 s64 bn;
2332 struct metapage *mp;
2333 xtpage_t *p;
2334 int index, nextindex;
2335 struct tlock *tlck;
2336 struct xtlock *xtlck;
2337
2338 /*
2339 * find the matching entry; xtSearch() pins the page
2340 */
2341 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2342 return rc;
2343
2344 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2345 if (cmp) {
2346 /* unpin the leaf page */
2347 XT_PUTPAGE(mp);
2348 return -ENOENT;
2349 }
2350
2351 /*
2352 * delete the entry from the leaf page
2353 */
2354 nextindex = le16_to_cpu(p->header.nextindex);
2355 le16_add_cpu(&p->header.nextindex, -1);
2356
2357 /*
2358 * if the leaf page bocome empty, free the page
2359 */
2360 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2361 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2362
2363 BT_MARK_DIRTY(mp, ip);
2364 /*
2365 * acquire a transaction lock on the leaf page;
2366 *
2367 * action:xad deletion;
2368 */
2369 tlck = txLock(tid, ip, mp, tlckXTREE);
2370 xtlck = (struct xtlock *) & tlck->lock;
2371 xtlck->lwm.offset =
2372 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2373
2374 /* if delete from middle, shift left/compact the remaining entries */
2375 if (index < nextindex - 1)
2376 memmove(&p->xad[index], &p->xad[index + 1],
2377 (nextindex - index - 1) * sizeof(xad_t));
2378
2379 XT_PUTPAGE(mp);
2380
2381 return 0;
2382}
2383
2384
2385/* - TBD for defragmentaion/reorganization -
2386 *
2387 * xtDeleteUp()
2388 *
2389 * function:
2390 * free empty pages as propagating deletion up the tree
2391 *
2392 * parameter:
2393 *
2394 * return:
2395 */
2396static int
2397xtDeleteUp(tid_t tid, struct inode *ip,
2398 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2399{
2400 int rc = 0;
2401 struct metapage *mp;
2402 xtpage_t *p;
2403 int index, nextindex;
2404 s64 xaddr;
2405 int xlen;
2406 struct btframe *parent;
2407 struct tlock *tlck;
2408 struct xtlock *xtlck;
2409
2410 /*
2411 * keep root leaf page which has become empty
2412 */
2413 if (fp->header.flag & BT_ROOT) {
2414 /* keep the root page */
2415 fp->header.flag &= ~BT_INTERNAL;
2416 fp->header.flag |= BT_LEAF;
2417 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2418
2419 /* XT_PUTPAGE(fmp); */
2420
2421 return 0;
2422 }
2423
2424 /*
2425 * free non-root leaf page
2426 */
2427 if ((rc = xtRelink(tid, ip, fp))) {
2428 XT_PUTPAGE(fmp);
2429 return rc;
2430 }
2431
2432 xaddr = addressPXD(&fp->header.self);
2433 xlen = lengthPXD(&fp->header.self);
2434 /* free the page extent */
2435 dbFree(ip, xaddr, (s64) xlen);
2436
2437 /* free the buffer page */
2438 discard_metapage(fmp);
2439
2440 /*
2441 * propagate page deletion up the index tree
2442 *
2443 * If the delete from the parent page makes it empty,
2444 * continue all the way up the tree.
2445 * stop if the root page is reached (which is never deleted) or
2446 * if the entry deletion does not empty the page.
2447 */
2448 while ((parent = BT_POP(btstack)) != NULL) {
2449 /* get/pin the parent page <sp> */
2450 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2451 if (rc)
2452 return rc;
2453
2454 index = parent->index;
2455
2456 /* delete the entry for the freed child page from parent.
2457 */
2458 nextindex = le16_to_cpu(p->header.nextindex);
2459
2460 /*
2461 * the parent has the single entry being deleted:
2462 * free the parent page which has become empty.
2463 */
2464 if (nextindex == 1) {
2465 if (p->header.flag & BT_ROOT) {
2466 /* keep the root page */
2467 p->header.flag &= ~BT_INTERNAL;
2468 p->header.flag |= BT_LEAF;
2469 p->header.nextindex =
2470 cpu_to_le16(XTENTRYSTART);
2471
2472 /* XT_PUTPAGE(mp); */
2473
2474 break;
2475 } else {
2476 /* free the parent page */
2477 if ((rc = xtRelink(tid, ip, p)))
2478 return rc;
2479
2480 xaddr = addressPXD(&p->header.self);
2481 /* free the page extent */
2482 dbFree(ip, xaddr,
2483 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2484
2485 /* unpin/free the buffer page */
2486 discard_metapage(mp);
2487
2488 /* propagate up */
2489 continue;
2490 }
2491 }
2492 /*
2493 * the parent has other entries remaining:
2494 * delete the router entry from the parent page.
2495 */
2496 else {
2497 BT_MARK_DIRTY(mp, ip);
2498 /*
2499 * acquire a transaction lock on the leaf page;
2500 *
2501 * action:xad deletion;
2502 */
2503 tlck = txLock(tid, ip, mp, tlckXTREE);
2504 xtlck = (struct xtlock *) & tlck->lock;
2505 xtlck->lwm.offset =
2506 (xtlck->lwm.offset) ? min(index,
2507 xtlck->lwm.
2508 offset) : index;
2509
2510 /* if delete from middle,
2511 * shift left/compact the remaining entries in the page
2512 */
2513 if (index < nextindex - 1)
2514 memmove(&p->xad[index], &p->xad[index + 1],
2515 (nextindex - index -
2516 1) << L2XTSLOTSIZE);
2517
2518 le16_add_cpu(&p->header.nextindex, -1);
2519 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2520 (ulong) parent->bn, index);
2521 }
2522
2523 /* unpin the parent page */
2524 XT_PUTPAGE(mp);
2525
2526 /* exit propagation up */
2527 break;
2528 }
2529
2530 return 0;
2531}
2532
2533
2534/*
2535 * NAME: xtRelocate()
2536 *
2537 * FUNCTION: relocate xtpage or data extent of regular file;
2538 * This function is mainly used by defragfs utility.
2539 *
2540 * NOTE: This routine does not have the logic to handle
2541 * uncommitted allocated extent. The caller should call
2542 * txCommit() to commit all the allocation before call
2543 * this routine.
2544 */
2545int
2546xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2547 s64 nxaddr, /* new xaddr */
2548 int xtype)
2549{ /* extent type: XTPAGE or DATAEXT */
2550 int rc = 0;
2551 struct tblock *tblk;
2552 struct tlock *tlck;
2553 struct xtlock *xtlck;
2554 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2555 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2556 xad_t *xad;
2557 pxd_t *pxd;
2558 s64 xoff, xsize;
2559 int xlen;
2560 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2561 cbuf_t *cp;
2562 s64 offset, nbytes, nbrd, pno;
2563 int nb, npages, nblks;
2564 s64 bn;
2565 int cmp;
2566 int index;
2567 struct pxd_lock *pxdlock;
2568 struct btstack btstack; /* traverse stack */
2569
2570 xtype = xtype & EXTENT_TYPE;
2571
2572 xoff = offsetXAD(oxad);
2573 oxaddr = addressXAD(oxad);
2574 xlen = lengthXAD(oxad);
2575
2576 /* validate extent offset */
2577 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2578 if (offset >= ip->i_size)
2579 return -ESTALE; /* stale extent */
2580
2581 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2582 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2583
2584 /*
2585 * 1. get and validate the parent xtpage/xad entry
2586 * covering the source extent to be relocated;
2587 */
2588 if (xtype == DATAEXT) {
2589 /* search in leaf entry */
2590 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2591 if (rc)
2592 return rc;
2593
2594 /* retrieve search result */
2595 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2596
2597 if (cmp) {
2598 XT_PUTPAGE(pmp);
2599 return -ESTALE;
2600 }
2601
2602 /* validate for exact match with a single entry */
2603 xad = &pp->xad[index];
2604 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2605 XT_PUTPAGE(pmp);
2606 return -ESTALE;
2607 }
2608 } else { /* (xtype == XTPAGE) */
2609
2610 /* search in internal entry */
2611 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2612 if (rc)
2613 return rc;
2614
2615 /* retrieve search result */
2616 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2617
2618 if (cmp) {
2619 XT_PUTPAGE(pmp);
2620 return -ESTALE;
2621 }
2622
2623 /* xtSearchNode() validated for exact match with a single entry
2624 */
2625 xad = &pp->xad[index];
2626 }
2627 jfs_info("xtRelocate: parent xad entry validated.");
2628
2629 /*
2630 * 2. relocate the extent
2631 */
2632 if (xtype == DATAEXT) {
2633 /* if the extent is allocated-but-not-recorded
2634 * there is no real data to be moved in this extent,
2635 */
2636 if (xad->flag & XAD_NOTRECORDED)
2637 goto out;
2638 else
2639 /* release xtpage for cmRead()/xtLookup() */
2640 XT_PUTPAGE(pmp);
2641
2642 /*
2643 * cmRelocate()
2644 *
2645 * copy target data pages to be relocated;
2646 *
2647 * data extent must start at page boundary and
2648 * multiple of page size (except the last data extent);
2649 * read in each page of the source data extent into cbuf,
2650 * update the cbuf extent descriptor of the page to be
2651 * homeward bound to new dst data extent
2652 * copy the data from the old extent to new extent.
2653 * copy is essential for compressed files to avoid problems
2654 * that can arise if there was a change in compression
2655 * algorithms.
2656 * it is a good strategy because it may disrupt cache
2657 * policy to keep the pages in memory afterwards.
2658 */
2659 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2660 assert((offset & CM_OFFSET) == 0);
2661 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2662 pno = offset >> CM_L2BSIZE;
2663 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2664/*
2665 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2666 (offset >> CM_L2BSIZE) + 1;
2667*/
2668 sxaddr = oxaddr;
2669 dxaddr = nxaddr;
2670
2671 /* process the request one cache buffer at a time */
2672 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2673 offset += nb, pno++, npages--) {
2674 /* compute page size */
2675 nb = min(nbytes - nbrd, CM_BSIZE);
2676
2677 /* get the cache buffer of the page */
2678 if (rc = cmRead(ip, offset, npages, &cp))
2679 break;
2680
2681 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2682 assert(!cp->cm_modified);
2683
2684 /* bind buffer with the new extent address */
2685 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2686 cmSetXD(ip, cp, pno, dxaddr, nblks);
2687
2688 /* release the cbuf, mark it as modified */
2689 cmPut(cp, true);
2690
2691 dxaddr += nblks;
2692 sxaddr += nblks;
2693 }
2694
2695 /* get back parent page */
2696 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2697 return rc;
2698
2699 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2700 jfs_info("xtRelocate: target data extent relocated.");
2701 } else { /* (xtype == XTPAGE) */
2702
2703 /*
2704 * read in the target xtpage from the source extent;
2705 */
2706 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2707 if (rc) {
2708 XT_PUTPAGE(pmp);
2709 return rc;
2710 }
2711
2712 /*
2713 * read in sibling pages if any to update sibling pointers;
2714 */
2715 rmp = NULL;
2716 if (p->header.next) {
2717 nextbn = le64_to_cpu(p->header.next);
2718 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2719 if (rc) {
2720 XT_PUTPAGE(pmp);
2721 XT_PUTPAGE(mp);
2722 return (rc);
2723 }
2724 }
2725
2726 lmp = NULL;
2727 if (p->header.prev) {
2728 prevbn = le64_to_cpu(p->header.prev);
2729 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2730 if (rc) {
2731 XT_PUTPAGE(pmp);
2732 XT_PUTPAGE(mp);
2733 if (rmp)
2734 XT_PUTPAGE(rmp);
2735 return (rc);
2736 }
2737 }
2738
2739 /* at this point, all xtpages to be updated are in memory */
2740
2741 /*
2742 * update sibling pointers of sibling xtpages if any;
2743 */
2744 if (lmp) {
2745 BT_MARK_DIRTY(lmp, ip);
2746 tlck = txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
2747 lp->header.next = cpu_to_le64(nxaddr);
2748 XT_PUTPAGE(lmp);
2749 }
2750
2751 if (rmp) {
2752 BT_MARK_DIRTY(rmp, ip);
2753 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
2754 rp->header.prev = cpu_to_le64(nxaddr);
2755 XT_PUTPAGE(rmp);
2756 }
2757
2758 /*
2759 * update the target xtpage to be relocated
2760 *
2761 * update the self address of the target page
2762 * and write to destination extent;
2763 * redo image covers the whole xtpage since it is new page
2764 * to the destination extent;
2765 * update of bmap for the free of source extent
2766 * of the target xtpage itself:
2767 * update of bmap for the allocation of destination extent
2768 * of the target xtpage itself:
2769 * update of bmap for the extents covered by xad entries in
2770 * the target xtpage is not necessary since they are not
2771 * updated;
2772 * if not committed before this relocation,
2773 * target page may contain XAD_NEW entries which must
2774 * be scanned for bmap update (logredo() always
2775 * scan xtpage REDOPAGE image for bmap update);
2776 * if committed before this relocation (tlckRELOCATE),
2777 * scan may be skipped by commit() and logredo();
2778 */
2779 BT_MARK_DIRTY(mp, ip);
2780 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
2781 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
2782 xtlck = (struct xtlock *) & tlck->lock;
2783
2784 /* update the self address in the xtpage header */
2785 pxd = &p->header.self;
2786 PXDaddress(pxd, nxaddr);
2787
2788 /* linelock for the after image of the whole page */
2789 xtlck->lwm.length =
2790 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
2791
2792 /* update the buffer extent descriptor of target xtpage */
2793 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2794 bmSetXD(mp, nxaddr, xsize);
2795
2796 /* unpin the target page to new homeward bound */
2797 XT_PUTPAGE(mp);
2798 jfs_info("xtRelocate: target xtpage relocated.");
2799 }
2800
2801 /*
2802 * 3. acquire maplock for the source extent to be freed;
2803 *
2804 * acquire a maplock saving the src relocated extent address;
2805 * to free of the extent at commit time;
2806 */
2807 out:
2808 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
2809 * free PXD of the source data extent (logredo() will update
2810 * bmap for free of source data extent), and update bmap for
2811 * free of the source data extent;
2812 */
2813 if (xtype == DATAEXT)
2814 tlck = txMaplock(tid, ip, tlckMAP);
2815 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
2816 * for the source xtpage (logredo() will init NoRedoPage
2817 * filter and will also update bmap for free of the source
2818 * xtpage), and update bmap for free of the source xtpage;
2819 * N.B. We use tlckMAP instead of tlkcXTREE because there
2820 * is no buffer associated with this lock since the buffer
2821 * has been redirected to the target location.
2822 */
2823 else /* (xtype == XTPAGE) */
2824 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
2825
2826 pxdlock = (struct pxd_lock *) & tlck->lock;
2827 pxdlock->flag = mlckFREEPXD;
2828 PXDaddress(&pxdlock->pxd, oxaddr);
2829 PXDlength(&pxdlock->pxd, xlen);
2830 pxdlock->index = 1;
2831
2832 /*
2833 * 4. update the parent xad entry for relocation;
2834 *
2835 * acquire tlck for the parent entry with XAD_NEW as entry
2836 * update which will write LOG_REDOPAGE and update bmap for
2837 * allocation of XAD_NEW destination extent;
2838 */
2839 jfs_info("xtRelocate: update parent xad entry.");
2840 BT_MARK_DIRTY(pmp, ip);
2841 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
2842 xtlck = (struct xtlock *) & tlck->lock;
2843
2844 /* update the XAD with the new destination extent; */
2845 xad = &pp->xad[index];
2846 xad->flag |= XAD_NEW;
2847 XADaddress(xad, nxaddr);
2848
2849 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
2850 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
2851 xtlck->lwm.offset;
2852
2853 /* unpin the parent xtpage */
2854 XT_PUTPAGE(pmp);
2855
2856 return rc;
2857}
2858
2859
2860/*
2861 * xtSearchNode()
2862 *
2863 * function: search for the internal xad entry covering specified extent.
2864 * This function is mainly used by defragfs utility.
2865 *
2866 * parameters:
2867 * ip - file object;
2868 * xad - extent to find;
2869 * cmpp - comparison result:
2870 * btstack - traverse stack;
2871 * flag - search process flag;
2872 *
2873 * returns:
2874 * btstack contains (bn, index) of search path traversed to the entry.
2875 * *cmpp is set to result of comparison with the entry returned.
2876 * the page containing the entry is pinned at exit.
2877 */
2878static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
2879 int *cmpp, struct btstack * btstack, int flag)
2880{
2881 int rc = 0;
2882 s64 xoff, xaddr;
2883 int xlen;
2884 int cmp = 1; /* init for empty page */
2885 s64 bn; /* block number */
2886 struct metapage *mp; /* meta-page buffer */
2887 xtpage_t *p; /* page */
2888 int base, index, lim;
2889 struct btframe *btsp;
2890 s64 t64;
2891
2892 BT_CLR(btstack);
2893
2894 xoff = offsetXAD(xad);
2895 xlen = lengthXAD(xad);
2896 xaddr = addressXAD(xad);
2897
2898 /*
2899 * search down tree from root:
2900 *
2901 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
2902 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
2903 *
2904 * if entry with search key K is not found
2905 * internal page search find the entry with largest key Ki
2906 * less than K which point to the child page to search;
2907 * leaf page search find the entry with smallest key Kj
2908 * greater than K so that the returned index is the position of
2909 * the entry to be shifted right for insertion of new entry.
2910 * for empty tree, search key is greater than any key of the tree.
2911 *
2912 * by convention, root bn = 0.
2913 */
2914 for (bn = 0;;) {
2915 /* get/pin the page to search */
2916 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2917 if (rc)
2918 return rc;
2919 if (p->header.flag & BT_LEAF) {
2920 XT_PUTPAGE(mp);
2921 return -ESTALE;
2922 }
2923
2924 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
2925
2926 /*
2927 * binary search with search key K on the current page
2928 */
2929 for (base = XTENTRYSTART; lim; lim >>= 1) {
2930 index = base + (lim >> 1);
2931
2932 XT_CMP(cmp, xoff, &p->xad[index], t64);
2933 if (cmp == 0) {
2934 /*
2935 * search hit
2936 *
2937 * verify for exact match;
2938 */
2939 if (xaddr == addressXAD(&p->xad[index]) &&
2940 xoff == offsetXAD(&p->xad[index])) {
2941 *cmpp = cmp;
2942
2943 /* save search result */
2944 btsp = btstack->top;
2945 btsp->bn = bn;
2946 btsp->index = index;
2947 btsp->mp = mp;
2948
2949 return 0;
2950 }
2951
2952 /* descend/search its child page */
2953 goto next;
2954 }
2955
2956 if (cmp > 0) {
2957 base = index + 1;
2958 --lim;
2959 }
2960 }
2961
2962 /*
2963 * search miss - non-leaf page:
2964 *
2965 * base is the smallest index with key (Kj) greater than
2966 * search key (K) and may be zero or maxentry index.
2967 * if base is non-zero, decrement base by one to get the parent
2968 * entry of the child page to search.
2969 */
2970 index = base ? base - 1 : base;
2971
2972 /*
2973 * go down to child page
2974 */
2975 next:
2976 /* get the child page block number */
2977 bn = addressXAD(&p->xad[index]);
2978
2979 /* unpin the parent page */
2980 XT_PUTPAGE(mp);
2981 }
2982}
2983
2984
2985/*
2986 * xtRelink()
2987 *
2988 * function:
2989 * link around a freed page.
2990 *
2991 * Parameter:
2992 * int tid,
2993 * struct inode *ip,
2994 * xtpage_t *p)
2995 *
2996 * returns:
2997 */
2998static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
2999{
3000 int rc = 0;
3001 struct metapage *mp;
3002 s64 nextbn, prevbn;
3003 struct tlock *tlck;
3004
3005 nextbn = le64_to_cpu(p->header.next);
3006 prevbn = le64_to_cpu(p->header.prev);
3007
3008 /* update prev pointer of the next page */
3009 if (nextbn != 0) {
3010 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3011 if (rc)
3012 return rc;
3013
3014 /*
3015 * acquire a transaction lock on the page;
3016 *
3017 * action: update prev pointer;
3018 */
3019 BT_MARK_DIRTY(mp, ip);
3020 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3021
3022 /* the page may already have been tlock'd */
3023
3024 p->header.prev = cpu_to_le64(prevbn);
3025
3026 XT_PUTPAGE(mp);
3027 }
3028
3029 /* update next pointer of the previous page */
3030 if (prevbn != 0) {
3031 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3032 if (rc)
3033 return rc;
3034
3035 /*
3036 * acquire a transaction lock on the page;
3037 *
3038 * action: update next pointer;
3039 */
3040 BT_MARK_DIRTY(mp, ip);
3041 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3042
3043 /* the page may already have been tlock'd */
3044
3045 p->header.next = le64_to_cpu(nextbn);
3046
3047 XT_PUTPAGE(mp);
3048 }
3049
3050 return 0;
3051}
3052#endif /* _STILL_TO_PORT */
3053
3054
3055/*
3056 * xtInitRoot()
3057 *
3058 * initialize file root (inline in inode)
3059 */
3060void xtInitRoot(tid_t tid, struct inode *ip)
3061{
3062 xtpage_t *p;
3063
3064 /*
3065 * acquire a transaction lock on the root
3066 *
3067 * action:
3068 */
3069 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3070 tlckXTREE | tlckNEW);
3071 p = &JFS_IP(ip)->i_xtroot;
3072
3073 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3074 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3075
3076 if (S_ISDIR(ip->i_mode))
3077 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3078 else {
3079 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3080 ip->i_size = 0;
3081 }
3082
3083
3084 return;
3085}
3086
3087
3088/*
3089 * We can run into a deadlock truncating a file with a large number of
3090 * xtree pages (large fragmented file). A robust fix would entail a
3091 * reservation system where we would reserve a number of metadata pages
3092 * and tlocks which we would be guaranteed without a deadlock. Without
3093 * this, a partial fix is to limit number of metadata pages we will lock
3094 * in a single transaction. Currently we will truncate the file so that
3095 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3096 * will be responsible for ensuring that the current transaction gets
3097 * committed, and that subsequent transactions are created to truncate
3098 * the file further if needed.
3099 */
3100#define MAX_TRUNCATE_LEAVES 50
3101
3102/*
3103 * xtTruncate()
3104 *
3105 * function:
3106 * traverse for truncation logging backward bottom up;
3107 * terminate at the last extent entry at the current subtree
3108 * root page covering new down size.
3109 * truncation may occur within the last extent entry.
3110 *
3111 * parameter:
3112 * int tid,
3113 * struct inode *ip,
3114 * s64 newsize,
3115 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3116 *
3117 * return:
3118 *
3119 * note:
3120 * PWMAP:
3121 * 1. truncate (non-COMMIT_NOLINK file)
3122 * by jfs_truncate() or jfs_open(O_TRUNC):
3123 * xtree is updated;
3124 * 2. truncate index table of directory when last entry removed
3125 * map update via tlock at commit time;
3126 * PMAP:
3127 * Call xtTruncate_pmap instead
3128 * WMAP:
3129 * 1. remove (free zero link count) on last reference release
3130 * (pmap has been freed at commit zero link count);
3131 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3132 * xtree is updated;
3133 * map update directly at truncation time;
3134 *
3135 * if (DELETE)
3136 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3137 * else if (TRUNCATE)
3138 * must write LOG_NOREDOPAGE for deleted index page;
3139 *
3140 * pages may already have been tlocked by anonymous transactions
3141 * during file growth (i.e., write) before truncation;
3142 *
3143 * except last truncated entry, deleted entries remains as is
3144 * in the page (nextindex is updated) for other use
3145 * (e.g., log/update allocation map): this avoid copying the page
3146 * info but delay free of pages;
3147 *
3148 */
3149s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3150{
3151 int rc = 0;
3152 s64 teof;
3153 struct metapage *mp;
3154 xtpage_t *p;
3155 s64 bn;
3156 int index, nextindex;
3157 xad_t *xad;
3158 s64 xoff, xaddr;
3159 int xlen, len, freexlen;
3160 struct btstack btstack;
3161 struct btframe *parent;
3162 struct tblock *tblk = NULL;
3163 struct tlock *tlck = NULL;
3164 struct xtlock *xtlck = NULL;
3165 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3166 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3167 s64 nfreed;
3168 int freed, log;
3169 int locked_leaves = 0;
3170
3171 /* save object truncation type */
3172 if (tid) {
3173 tblk = tid_to_tblock(tid);
3174 tblk->xflag |= flag;
3175 }
3176
3177 nfreed = 0;
3178
3179 flag &= COMMIT_MAP;
3180 assert(flag != COMMIT_PMAP);
3181
3182 if (flag == COMMIT_PWMAP)
3183 log = 1;
3184 else {
3185 log = 0;
3186 xadlock.flag = mlckFREEXADLIST;
3187 xadlock.index = 1;
3188 }
3189
3190 /*
3191 * if the newsize is not an integral number of pages,
3192 * the file between newsize and next page boundary will
3193 * be cleared.
3194 * if truncating into a file hole, it will cause
3195 * a full block to be allocated for the logical block.
3196 */
3197
3198 /*
3199 * release page blocks of truncated region <teof, eof>
3200 *
3201 * free the data blocks from the leaf index blocks.
3202 * delete the parent index entries corresponding to
3203 * the freed child data/index blocks.
3204 * free the index blocks themselves which aren't needed
3205 * in new sized file.
3206 *
3207 * index blocks are updated only if the blocks are to be
3208 * retained in the new sized file.
3209 * if type is PMAP, the data and index pages are NOT
3210 * freed, and the data and index blocks are NOT freed
3211 * from working map.
3212 * (this will allow continued access of data/index of
3213 * temporary file (zerolink count file truncated to zero-length)).
3214 */
3215 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3216 JFS_SBI(ip->i_sb)->l2bsize;
3217
3218 /* clear stack */
3219 BT_CLR(&btstack);
3220
3221 /*
3222 * start with root
3223 *
3224 * root resides in the inode
3225 */
3226 bn = 0;
3227
3228 /*
3229 * first access of each page:
3230 */
3231 getPage:
3232 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3233 if (rc)
3234 return rc;
3235
3236 /* process entries backward from last index */
3237 index = le16_to_cpu(p->header.nextindex) - 1;
3238
3239
3240 /* Since this is the rightmost page at this level, and we may have
3241 * already freed a page that was formerly to the right, let's make
3242 * sure that the next pointer is zero.
3243 */
3244 if (p->header.next) {
3245 if (log)
3246 /*
3247 * Make sure this change to the header is logged.
3248 * If we really truncate this leaf, the flag
3249 * will be changed to tlckTRUNCATE
3250 */
3251 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3252 BT_MARK_DIRTY(mp, ip);
3253 p->header.next = 0;
3254 }
3255
3256 if (p->header.flag & BT_INTERNAL)
3257 goto getChild;
3258
3259 /*
3260 * leaf page
3261 */
3262 freed = 0;
3263
3264 /* does region covered by leaf page precede Teof ? */
3265 xad = &p->xad[index];
3266 xoff = offsetXAD(xad);
3267 xlen = lengthXAD(xad);
3268 if (teof >= xoff + xlen) {
3269 XT_PUTPAGE(mp);
3270 goto getParent;
3271 }
3272
3273 /* (re)acquire tlock of the leaf page */
3274 if (log) {
3275 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3276 /*
3277 * We need to limit the size of the transaction
3278 * to avoid exhausting pagecache & tlocks
3279 */
3280 XT_PUTPAGE(mp);
3281 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3282 goto getParent;
3283 }
3284 tlck = txLock(tid, ip, mp, tlckXTREE);
3285 tlck->type = tlckXTREE | tlckTRUNCATE;
3286 xtlck = (struct xtlock *) & tlck->lock;
3287 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3288 }
3289 BT_MARK_DIRTY(mp, ip);
3290
3291 /*
3292 * scan backward leaf page entries
3293 */
3294 for (; index >= XTENTRYSTART; index--) {
3295 xad = &p->xad[index];
3296 xoff = offsetXAD(xad);
3297 xlen = lengthXAD(xad);
3298 xaddr = addressXAD(xad);
3299
3300 /*
3301 * The "data" for a directory is indexed by the block
3302 * device's address space. This metadata must be invalidated
3303 * here
3304 */
3305 if (S_ISDIR(ip->i_mode) && (teof == 0))
3306 invalidate_xad_metapages(ip, *xad);
3307 /*
3308 * entry beyond eof: continue scan of current page
3309 * xad
3310 * ---|---=======------->
3311 * eof
3312 */
3313 if (teof < xoff) {
3314 nfreed += xlen;
3315 continue;
3316 }
3317
3318 /*
3319 * (xoff <= teof): last entry to be deleted from page;
3320 * If other entries remain in page: keep and update the page.
3321 */
3322
3323 /*
3324 * eof == entry_start: delete the entry
3325 * xad
3326 * -------|=======------->
3327 * eof
3328 *
3329 */
3330 if (teof == xoff) {
3331 nfreed += xlen;
3332
3333 if (index == XTENTRYSTART)
3334 break;
3335
3336 nextindex = index;
3337 }
3338 /*
3339 * eof within the entry: truncate the entry.
3340 * xad
3341 * -------===|===------->
3342 * eof
3343 */
3344 else if (teof < xoff + xlen) {
3345 /* update truncated entry */
3346 len = teof - xoff;
3347 freexlen = xlen - len;
3348 XADlength(xad, len);
3349
3350 /* save pxd of truncated extent in tlck */
3351 xaddr += len;
3352 if (log) { /* COMMIT_PWMAP */
3353 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3354 min(index, (int)xtlck->lwm.offset) : index;
3355 xtlck->lwm.length = index + 1 -
3356 xtlck->lwm.offset;
3357 xtlck->twm.offset = index;
3358 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3359 pxdlock->flag = mlckFREEPXD;
3360 PXDaddress(&pxdlock->pxd, xaddr);
3361 PXDlength(&pxdlock->pxd, freexlen);
3362 }
3363 /* free truncated extent */
3364 else { /* COMMIT_WMAP */
3365
3366 pxdlock = (struct pxd_lock *) & xadlock;
3367 pxdlock->flag = mlckFREEPXD;
3368 PXDaddress(&pxdlock->pxd, xaddr);
3369 PXDlength(&pxdlock->pxd, freexlen);
3370 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3371
3372 /* reset map lock */
3373 xadlock.flag = mlckFREEXADLIST;
3374 }
3375
3376 /* current entry is new last entry; */
3377 nextindex = index + 1;
3378
3379 nfreed += freexlen;
3380 }
3381 /*
3382 * eof beyond the entry:
3383 * xad
3384 * -------=======---|--->
3385 * eof
3386 */
3387 else { /* (xoff + xlen < teof) */
3388
3389 nextindex = index + 1;
3390 }
3391
3392 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3393 if (!log) { /* COMMIT_WAMP */
3394 xadlock.xdlist = &p->xad[nextindex];
3395 xadlock.count =
3396 le16_to_cpu(p->header.nextindex) -
3397 nextindex;
3398 txFreeMap(ip, (struct maplock *) & xadlock,
3399 NULL, COMMIT_WMAP);
3400 }
3401 p->header.nextindex = cpu_to_le16(nextindex);
3402 }
3403
3404 XT_PUTPAGE(mp);
3405
3406 /* assert(freed == 0); */
3407 goto getParent;
3408 } /* end scan of leaf page entries */
3409
3410 freed = 1;
3411
3412 /*
3413 * leaf page become empty: free the page if type != PMAP
3414 */
3415 if (log) { /* COMMIT_PWMAP */
3416 /* txCommit() with tlckFREE:
3417 * free data extents covered by leaf [XTENTRYSTART:hwm);
3418 * invalidate leaf if COMMIT_PWMAP;
3419 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3420 */
3421 tlck->type = tlckXTREE | tlckFREE;
3422 } else { /* COMMIT_WAMP */
3423
3424 /* free data extents covered by leaf */
3425 xadlock.xdlist = &p->xad[XTENTRYSTART];
3426 xadlock.count =
3427 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3428 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3429 }
3430
3431 if (p->header.flag & BT_ROOT) {
3432 p->header.flag &= ~BT_INTERNAL;
3433 p->header.flag |= BT_LEAF;
3434 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3435
3436 XT_PUTPAGE(mp); /* debug */
3437 goto out;
3438 } else {
3439 if (log) { /* COMMIT_PWMAP */
3440 /* page will be invalidated at tx completion
3441 */
3442 XT_PUTPAGE(mp);
3443 } else { /* COMMIT_WMAP */
3444
3445 if (mp->lid)
3446 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3447
3448 /* invalidate empty leaf page */
3449 discard_metapage(mp);
3450 }
3451 }
3452
3453 /*
3454 * the leaf page become empty: delete the parent entry
3455 * for the leaf page if the parent page is to be kept
3456 * in the new sized file.
3457 */
3458
3459 /*
3460 * go back up to the parent page
3461 */
3462 getParent:
3463 /* pop/restore parent entry for the current child page */
3464 if ((parent = BT_POP(&btstack)) == NULL)
3465 /* current page must have been root */
3466 goto out;
3467
3468 /* get back the parent page */
3469 bn = parent->bn;
3470 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3471 if (rc)
3472 return rc;
3473
3474 index = parent->index;
3475
3476 /*
3477 * child page was not empty:
3478 */
3479 if (freed == 0) {
3480 /* has any entry deleted from parent ? */
3481 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3482 /* (re)acquire tlock on the parent page */
3483 if (log) { /* COMMIT_PWMAP */
3484 /* txCommit() with tlckTRUNCATE:
3485 * free child extents covered by parent [);
3486 */
3487 tlck = txLock(tid, ip, mp, tlckXTREE);
3488 xtlck = (struct xtlock *) & tlck->lock;
3489 if (!(tlck->type & tlckTRUNCATE)) {
3490 xtlck->hwm.offset =
3491 le16_to_cpu(p->header.
3492 nextindex) - 1;
3493 tlck->type =
3494 tlckXTREE | tlckTRUNCATE;
3495 }
3496 } else { /* COMMIT_WMAP */
3497
3498 /* free child extents covered by parent */
3499 xadlock.xdlist = &p->xad[index + 1];
3500 xadlock.count =
3501 le16_to_cpu(p->header.nextindex) -
3502 index - 1;
3503 txFreeMap(ip, (struct maplock *) & xadlock,
3504 NULL, COMMIT_WMAP);
3505 }
3506 BT_MARK_DIRTY(mp, ip);
3507
3508 p->header.nextindex = cpu_to_le16(index + 1);
3509 }
3510 XT_PUTPAGE(mp);
3511 goto getParent;
3512 }
3513
3514 /*
3515 * child page was empty:
3516 */
3517 nfreed += lengthXAD(&p->xad[index]);
3518
3519 /*
3520 * During working map update, child page's tlock must be handled
3521 * before parent's. This is because the parent's tlock will cause
3522 * the child's disk space to be marked available in the wmap, so
3523 * it's important that the child page be released by that time.
3524 *
3525 * ToDo: tlocks should be on doubly-linked list, so we can
3526 * quickly remove it and add it to the end.
3527 */
3528
3529 /*
3530 * Move parent page's tlock to the end of the tid's tlock list
3531 */
3532 if (log && mp->lid && (tblk->last != mp->lid) &&
3533 lid_to_tlock(mp->lid)->tid) {
3534 lid_t lid = mp->lid;
3535 struct tlock *prev;
3536
3537 tlck = lid_to_tlock(lid);
3538
3539 if (tblk->next == lid)
3540 tblk->next = tlck->next;
3541 else {
3542 for (prev = lid_to_tlock(tblk->next);
3543 prev->next != lid;
3544 prev = lid_to_tlock(prev->next)) {
3545 assert(prev->next);
3546 }
3547 prev->next = tlck->next;
3548 }
3549 lid_to_tlock(tblk->last)->next = lid;
3550 tlck->next = 0;
3551 tblk->last = lid;
3552 }
3553
3554 /*
3555 * parent page become empty: free the page
3556 */
3557 if (index == XTENTRYSTART) {
3558 if (log) { /* COMMIT_PWMAP */
3559 /* txCommit() with tlckFREE:
3560 * free child extents covered by parent;
3561 * invalidate parent if COMMIT_PWMAP;
3562 */
3563 tlck = txLock(tid, ip, mp, tlckXTREE);
3564 xtlck = (struct xtlock *) & tlck->lock;
3565 xtlck->hwm.offset =
3566 le16_to_cpu(p->header.nextindex) - 1;
3567 tlck->type = tlckXTREE | tlckFREE;
3568 } else { /* COMMIT_WMAP */
3569
3570 /* free child extents covered by parent */
3571 xadlock.xdlist = &p->xad[XTENTRYSTART];
3572 xadlock.count =
3573 le16_to_cpu(p->header.nextindex) -
3574 XTENTRYSTART;
3575 txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3576 COMMIT_WMAP);
3577 }
3578 BT_MARK_DIRTY(mp, ip);
3579
3580 if (p->header.flag & BT_ROOT) {
3581 p->header.flag &= ~BT_INTERNAL;
3582 p->header.flag |= BT_LEAF;
3583 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3584 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3585 /*
3586 * Shrink root down to allow inline
3587 * EA (otherwise fsck complains)
3588 */
3589 p->header.maxentry =
3590 cpu_to_le16(XTROOTINITSLOT);
3591 JFS_IP(ip)->mode2 |= INLINEEA;
3592 }
3593
3594 XT_PUTPAGE(mp); /* debug */
3595 goto out;
3596 } else {
3597 if (log) { /* COMMIT_PWMAP */
3598 /* page will be invalidated at tx completion
3599 */
3600 XT_PUTPAGE(mp);
3601 } else { /* COMMIT_WMAP */
3602
3603 if (mp->lid)
3604 lid_to_tlock(mp->lid)->flag |=
3605 tlckFREELOCK;
3606
3607 /* invalidate parent page */
3608 discard_metapage(mp);
3609 }
3610
3611 /* parent has become empty and freed:
3612 * go back up to its parent page
3613 */
3614 /* freed = 1; */
3615 goto getParent;
3616 }
3617 }
3618 /*
3619 * parent page still has entries for front region;
3620 */
3621 else {
3622 /* try truncate region covered by preceding entry
3623 * (process backward)
3624 */
3625 index--;
3626
3627 /* go back down to the child page corresponding
3628 * to the entry
3629 */
3630 goto getChild;
3631 }
3632
3633 /*
3634 * internal page: go down to child page of current entry
3635 */
3636 getChild:
3637 /* save current parent entry for the child page */
3638 if (BT_STACK_FULL(&btstack)) {
3639 jfs_error(ip->i_sb, "stack overrun!\n");
3640 XT_PUTPAGE(mp);
3641 return -EIO;
3642 }
3643 BT_PUSH(&btstack, bn, index);
3644
3645 /* get child page */
3646 xad = &p->xad[index];
3647 bn = addressXAD(xad);
3648
3649 /*
3650 * first access of each internal entry:
3651 */
3652 /* release parent page */
3653 XT_PUTPAGE(mp);
3654
3655 /* process the child page */
3656 goto getPage;
3657
3658 out:
3659 /*
3660 * update file resource stat
3661 */
3662 /* set size
3663 */
3664 if (S_ISDIR(ip->i_mode) && !newsize)
3665 ip->i_size = 1; /* fsck hates zero-length directories */
3666 else
3667 ip->i_size = newsize;
3668
3669 /* update quota allocation to reflect freed blocks */
3670 dquot_free_block(ip, nfreed);
3671
3672 /*
3673 * free tlock of invalidated pages
3674 */
3675 if (flag == COMMIT_WMAP)
3676 txFreelock(ip);
3677
3678 return newsize;
3679}
3680
3681
3682/*
3683 * xtTruncate_pmap()
3684 *
3685 * function:
3686 * Perform truncate to zero length for deleted file, leaving the
3687 * the xtree and working map untouched. This allows the file to
3688 * be accessed via open file handles, while the delete of the file
3689 * is committed to disk.
3690 *
3691 * parameter:
3692 * tid_t tid,
3693 * struct inode *ip,
3694 * s64 committed_size)
3695 *
3696 * return: new committed size
3697 *
3698 * note:
3699 *
3700 * To avoid deadlock by holding too many transaction locks, the
3701 * truncation may be broken up into multiple transactions.
3702 * The committed_size keeps track of part of the file has been
3703 * freed from the pmaps.
3704 */
3705s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3706{
3707 s64 bn;
3708 struct btstack btstack;
3709 int cmp;
3710 int index;
3711 int locked_leaves = 0;
3712 struct metapage *mp;
3713 xtpage_t *p;
3714 struct btframe *parent;
3715 int rc;
3716 struct tblock *tblk;
3717 struct tlock *tlck = NULL;
3718 xad_t *xad;
3719 int xlen;
3720 s64 xoff;
3721 struct xtlock *xtlck = NULL;
3722
3723 /* save object truncation type */
3724 tblk = tid_to_tblock(tid);
3725 tblk->xflag |= COMMIT_PMAP;
3726
3727 /* clear stack */
3728 BT_CLR(&btstack);
3729
3730 if (committed_size) {
3731 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3732 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
3733 if (rc)
3734 return rc;
3735
3736 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3737
3738 if (cmp != 0) {
3739 XT_PUTPAGE(mp);
3740 jfs_error(ip->i_sb, "did not find extent\n");
3741 return -EIO;
3742 }
3743 } else {
3744 /*
3745 * start with root
3746 *
3747 * root resides in the inode
3748 */
3749 bn = 0;
3750
3751 /*
3752 * first access of each page:
3753 */
3754 getPage:
3755 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3756 if (rc)
3757 return rc;
3758
3759 /* process entries backward from last index */
3760 index = le16_to_cpu(p->header.nextindex) - 1;
3761
3762 if (p->header.flag & BT_INTERNAL)
3763 goto getChild;
3764 }
3765
3766 /*
3767 * leaf page
3768 */
3769
3770 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3771 /*
3772 * We need to limit the size of the transaction
3773 * to avoid exhausting pagecache & tlocks
3774 */
3775 xad = &p->xad[index];
3776 xoff = offsetXAD(xad);
3777 xlen = lengthXAD(xad);
3778 XT_PUTPAGE(mp);
3779 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3780 }
3781 tlck = txLock(tid, ip, mp, tlckXTREE);
3782 tlck->type = tlckXTREE | tlckFREE;
3783 xtlck = (struct xtlock *) & tlck->lock;
3784 xtlck->hwm.offset = index;
3785
3786
3787 XT_PUTPAGE(mp);
3788
3789 /*
3790 * go back up to the parent page
3791 */
3792 getParent:
3793 /* pop/restore parent entry for the current child page */
3794 if ((parent = BT_POP(&btstack)) == NULL)
3795 /* current page must have been root */
3796 goto out;
3797
3798 /* get back the parent page */
3799 bn = parent->bn;
3800 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3801 if (rc)
3802 return rc;
3803
3804 index = parent->index;
3805
3806 /*
3807 * parent page become empty: free the page
3808 */
3809 if (index == XTENTRYSTART) {
3810 /* txCommit() with tlckFREE:
3811 * free child extents covered by parent;
3812 * invalidate parent if COMMIT_PWMAP;
3813 */
3814 tlck = txLock(tid, ip, mp, tlckXTREE);
3815 xtlck = (struct xtlock *) & tlck->lock;
3816 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3817 tlck->type = tlckXTREE | tlckFREE;
3818
3819 XT_PUTPAGE(mp);
3820
3821 if (p->header.flag & BT_ROOT) {
3822
3823 goto out;
3824 } else {
3825 goto getParent;
3826 }
3827 }
3828 /*
3829 * parent page still has entries for front region;
3830 */
3831 else
3832 index--;
3833 /*
3834 * internal page: go down to child page of current entry
3835 */
3836 getChild:
3837 /* save current parent entry for the child page */
3838 if (BT_STACK_FULL(&btstack)) {
3839 jfs_error(ip->i_sb, "stack overrun!\n");
3840 XT_PUTPAGE(mp);
3841 return -EIO;
3842 }
3843 BT_PUSH(&btstack, bn, index);
3844
3845 /* get child page */
3846 xad = &p->xad[index];
3847 bn = addressXAD(xad);
3848
3849 /*
3850 * first access of each internal entry:
3851 */
3852 /* release parent page */
3853 XT_PUTPAGE(mp);
3854
3855 /* process the child page */
3856 goto getPage;
3857
3858 out:
3859
3860 return 0;
3861}
3862
3863#ifdef CONFIG_JFS_STATISTICS
3864int jfs_xtstat_proc_show(struct seq_file *m, void *v)
3865{
3866 seq_printf(m,
3867 "JFS Xtree statistics\n"
3868 "====================\n"
3869 "searches = %d\n"
3870 "fast searches = %d\n"
3871 "splits = %d\n",
3872 xtStat.search,
3873 xtStat.fastSearch,
3874 xtStat.split);
3875 return 0;
3876}
3877#endif
1/*
2 * Copyright (C) International Business Machines Corp., 2000-2005
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18/*
19 * jfs_xtree.c: extent allocation descriptor B+-tree manager
20 */
21
22#include <linux/fs.h>
23#include <linux/module.h>
24#include <linux/quotaops.h>
25#include <linux/seq_file.h>
26#include "jfs_incore.h"
27#include "jfs_filsys.h"
28#include "jfs_metapage.h"
29#include "jfs_dmap.h"
30#include "jfs_dinode.h"
31#include "jfs_superblock.h"
32#include "jfs_debug.h"
33
34/*
35 * xtree local flag
36 */
37#define XT_INSERT 0x00000001
38
39/*
40 * xtree key/entry comparison: extent offset
41 *
42 * return:
43 * -1: k < start of extent
44 * 0: start_of_extent <= k <= end_of_extent
45 * 1: k > end_of_extent
46 */
47#define XT_CMP(CMP, K, X, OFFSET64)\
48{\
49 OFFSET64 = offsetXAD(X);\
50 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
51 ((K) < OFFSET64) ? -1 : 0;\
52}
53
54/* write a xad entry */
55#define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
56{\
57 (XAD)->flag = (FLAG);\
58 XADoffset((XAD), (OFF));\
59 XADlength((XAD), (LEN));\
60 XADaddress((XAD), (ADDR));\
61}
62
63#define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
64
65/* get page buffer for specified block address */
66/* ToDo: Replace this ugly macro with a function */
67#define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
68{\
69 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
70 if (!(RC))\
71 {\
72 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
73 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
74 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
75 {\
76 jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
77 BT_PUTPAGE(MP);\
78 MP = NULL;\
79 RC = -EIO;\
80 }\
81 }\
82}
83
84/* for consistency */
85#define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
86
87#define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
88 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
89/* xtree entry parameter descriptor */
90struct xtsplit {
91 struct metapage *mp;
92 s16 index;
93 u8 flag;
94 s64 off;
95 s64 addr;
96 int len;
97 struct pxdlist *pxdlist;
98};
99
100
101/*
102 * statistics
103 */
104#ifdef CONFIG_JFS_STATISTICS
105static struct {
106 uint search;
107 uint fastSearch;
108 uint split;
109} xtStat;
110#endif
111
112
113/*
114 * forward references
115 */
116static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
117 struct btstack * btstack, int flag);
118
119static int xtSplitUp(tid_t tid,
120 struct inode *ip,
121 struct xtsplit * split, struct btstack * btstack);
122
123static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
124 struct metapage ** rmpp, s64 * rbnp);
125
126static int xtSplitRoot(tid_t tid, struct inode *ip,
127 struct xtsplit * split, struct metapage ** rmpp);
128
129#ifdef _STILL_TO_PORT
130static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
131 xtpage_t * fp, struct btstack * btstack);
132
133static int xtSearchNode(struct inode *ip,
134 xad_t * xad,
135 int *cmpp, struct btstack * btstack, int flag);
136
137static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
138#endif /* _STILL_TO_PORT */
139
140/*
141 * xtLookup()
142 *
143 * function: map a single page into a physical extent;
144 */
145int xtLookup(struct inode *ip, s64 lstart,
146 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
147{
148 int rc = 0;
149 struct btstack btstack;
150 int cmp;
151 s64 bn;
152 struct metapage *mp;
153 xtpage_t *p;
154 int index;
155 xad_t *xad;
156 s64 next, size, xoff, xend;
157 int xlen;
158 s64 xaddr;
159
160 *paddr = 0;
161 *plen = llen;
162
163 if (!no_check) {
164 /* is lookup offset beyond eof ? */
165 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
166 JFS_SBI(ip->i_sb)->l2bsize;
167 if (lstart >= size)
168 return 0;
169 }
170
171 /*
172 * search for the xad entry covering the logical extent
173 */
174//search:
175 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
176 jfs_err("xtLookup: xtSearch returned %d", rc);
177 return rc;
178 }
179
180 /*
181 * compute the physical extent covering logical extent
182 *
183 * N.B. search may have failed (e.g., hole in sparse file),
184 * and returned the index of the next entry.
185 */
186 /* retrieve search result */
187 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
188
189 /* is xad found covering start of logical extent ?
190 * lstart is a page start address,
191 * i.e., lstart cannot start in a hole;
192 */
193 if (cmp) {
194 if (next)
195 *plen = min(next - lstart, llen);
196 goto out;
197 }
198
199 /*
200 * lxd covered by xad
201 */
202 xad = &p->xad[index];
203 xoff = offsetXAD(xad);
204 xlen = lengthXAD(xad);
205 xend = xoff + xlen;
206 xaddr = addressXAD(xad);
207
208 /* initialize new pxd */
209 *pflag = xad->flag;
210 *paddr = xaddr + (lstart - xoff);
211 /* a page must be fully covered by an xad */
212 *plen = min(xend - lstart, llen);
213
214 out:
215 XT_PUTPAGE(mp);
216
217 return rc;
218}
219
220/*
221 * xtSearch()
222 *
223 * function: search for the xad entry covering specified offset.
224 *
225 * parameters:
226 * ip - file object;
227 * xoff - extent offset;
228 * nextp - address of next extent (if any) for search miss
229 * cmpp - comparison result:
230 * btstack - traverse stack;
231 * flag - search process flag (XT_INSERT);
232 *
233 * returns:
234 * btstack contains (bn, index) of search path traversed to the entry.
235 * *cmpp is set to result of comparison with the entry returned.
236 * the page containing the entry is pinned at exit.
237 */
238static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
239 int *cmpp, struct btstack * btstack, int flag)
240{
241 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
242 int rc = 0;
243 int cmp = 1; /* init for empty page */
244 s64 bn; /* block number */
245 struct metapage *mp; /* page buffer */
246 xtpage_t *p; /* page */
247 xad_t *xad;
248 int base, index, lim, btindex;
249 struct btframe *btsp;
250 int nsplit = 0; /* number of pages to split */
251 s64 t64;
252 s64 next = 0;
253
254 INCREMENT(xtStat.search);
255
256 BT_CLR(btstack);
257
258 btstack->nsplit = 0;
259
260 /*
261 * search down tree from root:
262 *
263 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
264 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
265 *
266 * if entry with search key K is not found
267 * internal page search find the entry with largest key Ki
268 * less than K which point to the child page to search;
269 * leaf page search find the entry with smallest key Kj
270 * greater than K so that the returned index is the position of
271 * the entry to be shifted right for insertion of new entry.
272 * for empty tree, search key is greater than any key of the tree.
273 *
274 * by convention, root bn = 0.
275 */
276 for (bn = 0;;) {
277 /* get/pin the page to search */
278 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
279 if (rc)
280 return rc;
281
282 /* try sequential access heuristics with the previous
283 * access entry in target leaf page:
284 * once search narrowed down into the target leaf,
285 * key must either match an entry in the leaf or
286 * key entry does not exist in the tree;
287 */
288//fastSearch:
289 if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
290 (p->header.flag & BT_LEAF) &&
291 (index = jfs_ip->btindex) <
292 le16_to_cpu(p->header.nextindex)) {
293 xad = &p->xad[index];
294 t64 = offsetXAD(xad);
295 if (xoff < t64 + lengthXAD(xad)) {
296 if (xoff >= t64) {
297 *cmpp = 0;
298 goto out;
299 }
300
301 /* stop sequential access heuristics */
302 goto binarySearch;
303 } else { /* (t64 + lengthXAD(xad)) <= xoff */
304
305 /* try next sequential entry */
306 index++;
307 if (index <
308 le16_to_cpu(p->header.nextindex)) {
309 xad++;
310 t64 = offsetXAD(xad);
311 if (xoff < t64 + lengthXAD(xad)) {
312 if (xoff >= t64) {
313 *cmpp = 0;
314 goto out;
315 }
316
317 /* miss: key falls between
318 * previous and this entry
319 */
320 *cmpp = 1;
321 next = t64;
322 goto out;
323 }
324
325 /* (xoff >= t64 + lengthXAD(xad));
326 * matching entry may be further out:
327 * stop heuristic search
328 */
329 /* stop sequential access heuristics */
330 goto binarySearch;
331 }
332
333 /* (index == p->header.nextindex);
334 * miss: key entry does not exist in
335 * the target leaf/tree
336 */
337 *cmpp = 1;
338 goto out;
339 }
340
341 /*
342 * if hit, return index of the entry found, and
343 * if miss, where new entry with search key is
344 * to be inserted;
345 */
346 out:
347 /* compute number of pages to split */
348 if (flag & XT_INSERT) {
349 if (p->header.nextindex == /* little-endian */
350 p->header.maxentry)
351 nsplit++;
352 else
353 nsplit = 0;
354 btstack->nsplit = nsplit;
355 }
356
357 /* save search result */
358 btsp = btstack->top;
359 btsp->bn = bn;
360 btsp->index = index;
361 btsp->mp = mp;
362
363 /* update sequential access heuristics */
364 jfs_ip->btindex = index;
365
366 if (nextp)
367 *nextp = next;
368
369 INCREMENT(xtStat.fastSearch);
370 return 0;
371 }
372
373 /* well, ... full search now */
374 binarySearch:
375 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
376
377 /*
378 * binary search with search key K on the current page
379 */
380 for (base = XTENTRYSTART; lim; lim >>= 1) {
381 index = base + (lim >> 1);
382
383 XT_CMP(cmp, xoff, &p->xad[index], t64);
384 if (cmp == 0) {
385 /*
386 * search hit
387 */
388 /* search hit - leaf page:
389 * return the entry found
390 */
391 if (p->header.flag & BT_LEAF) {
392 *cmpp = cmp;
393
394 /* compute number of pages to split */
395 if (flag & XT_INSERT) {
396 if (p->header.nextindex ==
397 p->header.maxentry)
398 nsplit++;
399 else
400 nsplit = 0;
401 btstack->nsplit = nsplit;
402 }
403
404 /* save search result */
405 btsp = btstack->top;
406 btsp->bn = bn;
407 btsp->index = index;
408 btsp->mp = mp;
409
410 /* init sequential access heuristics */
411 btindex = jfs_ip->btindex;
412 if (index == btindex ||
413 index == btindex + 1)
414 jfs_ip->btorder = BT_SEQUENTIAL;
415 else
416 jfs_ip->btorder = BT_RANDOM;
417 jfs_ip->btindex = index;
418
419 return 0;
420 }
421 /* search hit - internal page:
422 * descend/search its child page
423 */
424 if (index < le16_to_cpu(p->header.nextindex)-1)
425 next = offsetXAD(&p->xad[index + 1]);
426 goto next;
427 }
428
429 if (cmp > 0) {
430 base = index + 1;
431 --lim;
432 }
433 }
434
435 /*
436 * search miss
437 *
438 * base is the smallest index with key (Kj) greater than
439 * search key (K) and may be zero or maxentry index.
440 */
441 if (base < le16_to_cpu(p->header.nextindex))
442 next = offsetXAD(&p->xad[base]);
443 /*
444 * search miss - leaf page:
445 *
446 * return location of entry (base) where new entry with
447 * search key K is to be inserted.
448 */
449 if (p->header.flag & BT_LEAF) {
450 *cmpp = cmp;
451
452 /* compute number of pages to split */
453 if (flag & XT_INSERT) {
454 if (p->header.nextindex ==
455 p->header.maxentry)
456 nsplit++;
457 else
458 nsplit = 0;
459 btstack->nsplit = nsplit;
460 }
461
462 /* save search result */
463 btsp = btstack->top;
464 btsp->bn = bn;
465 btsp->index = base;
466 btsp->mp = mp;
467
468 /* init sequential access heuristics */
469 btindex = jfs_ip->btindex;
470 if (base == btindex || base == btindex + 1)
471 jfs_ip->btorder = BT_SEQUENTIAL;
472 else
473 jfs_ip->btorder = BT_RANDOM;
474 jfs_ip->btindex = base;
475
476 if (nextp)
477 *nextp = next;
478
479 return 0;
480 }
481
482 /*
483 * search miss - non-leaf page:
484 *
485 * if base is non-zero, decrement base by one to get the parent
486 * entry of the child page to search.
487 */
488 index = base ? base - 1 : base;
489
490 /*
491 * go down to child page
492 */
493 next:
494 /* update number of pages to split */
495 if (p->header.nextindex == p->header.maxentry)
496 nsplit++;
497 else
498 nsplit = 0;
499
500 /* push (bn, index) of the parent page/entry */
501 if (BT_STACK_FULL(btstack)) {
502 jfs_error(ip->i_sb, "stack overrun in xtSearch!");
503 XT_PUTPAGE(mp);
504 return -EIO;
505 }
506 BT_PUSH(btstack, bn, index);
507
508 /* get the child page block number */
509 bn = addressXAD(&p->xad[index]);
510
511 /* unpin the parent page */
512 XT_PUTPAGE(mp);
513 }
514}
515
516/*
517 * xtInsert()
518 *
519 * function:
520 *
521 * parameter:
522 * tid - transaction id;
523 * ip - file object;
524 * xflag - extent flag (XAD_NOTRECORDED):
525 * xoff - extent offset;
526 * xlen - extent length;
527 * xaddrp - extent address pointer (in/out):
528 * if (*xaddrp)
529 * caller allocated data extent at *xaddrp;
530 * else
531 * allocate data extent and return its xaddr;
532 * flag -
533 *
534 * return:
535 */
536int xtInsert(tid_t tid, /* transaction id */
537 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
538 int flag)
539{
540 int rc = 0;
541 s64 xaddr, hint;
542 struct metapage *mp; /* meta-page buffer */
543 xtpage_t *p; /* base B+-tree index page */
544 s64 bn;
545 int index, nextindex;
546 struct btstack btstack; /* traverse stack */
547 struct xtsplit split; /* split information */
548 xad_t *xad;
549 int cmp;
550 s64 next;
551 struct tlock *tlck;
552 struct xtlock *xtlck;
553
554 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
555
556 /*
557 * search for the entry location at which to insert:
558 *
559 * xtFastSearch() and xtSearch() both returns (leaf page
560 * pinned, index at which to insert).
561 * n.b. xtSearch() may return index of maxentry of
562 * the full page.
563 */
564 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
565 return rc;
566
567 /* retrieve search result */
568 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
569
570 /* This test must follow XT_GETSEARCH since mp must be valid if
571 * we branch to out: */
572 if ((cmp == 0) || (next && (xlen > next - xoff))) {
573 rc = -EEXIST;
574 goto out;
575 }
576
577 /*
578 * allocate data extent requested
579 *
580 * allocation hint: last xad
581 */
582 if ((xaddr = *xaddrp) == 0) {
583 if (index > XTENTRYSTART) {
584 xad = &p->xad[index - 1];
585 hint = addressXAD(xad) + lengthXAD(xad) - 1;
586 } else
587 hint = 0;
588 if ((rc = dquot_alloc_block(ip, xlen)))
589 goto out;
590 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
591 dquot_free_block(ip, xlen);
592 goto out;
593 }
594 }
595
596 /*
597 * insert entry for new extent
598 */
599 xflag |= XAD_NEW;
600
601 /*
602 * if the leaf page is full, split the page and
603 * propagate up the router entry for the new page from split
604 *
605 * The xtSplitUp() will insert the entry and unpin the leaf page.
606 */
607 nextindex = le16_to_cpu(p->header.nextindex);
608 if (nextindex == le16_to_cpu(p->header.maxentry)) {
609 split.mp = mp;
610 split.index = index;
611 split.flag = xflag;
612 split.off = xoff;
613 split.len = xlen;
614 split.addr = xaddr;
615 split.pxdlist = NULL;
616 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
617 /* undo data extent allocation */
618 if (*xaddrp == 0) {
619 dbFree(ip, xaddr, (s64) xlen);
620 dquot_free_block(ip, xlen);
621 }
622 return rc;
623 }
624
625 *xaddrp = xaddr;
626 return 0;
627 }
628
629 /*
630 * insert the new entry into the leaf page
631 */
632 /*
633 * acquire a transaction lock on the leaf page;
634 *
635 * action: xad insertion/extension;
636 */
637 BT_MARK_DIRTY(mp, ip);
638
639 /* if insert into middle, shift right remaining entries. */
640 if (index < nextindex)
641 memmove(&p->xad[index + 1], &p->xad[index],
642 (nextindex - index) * sizeof(xad_t));
643
644 /* insert the new entry: mark the entry NEW */
645 xad = &p->xad[index];
646 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
647
648 /* advance next available entry index */
649 le16_add_cpu(&p->header.nextindex, 1);
650
651 /* Don't log it if there are no links to the file */
652 if (!test_cflag(COMMIT_Nolink, ip)) {
653 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
654 xtlck = (struct xtlock *) & tlck->lock;
655 xtlck->lwm.offset =
656 (xtlck->lwm.offset) ? min(index,
657 (int)xtlck->lwm.offset) : index;
658 xtlck->lwm.length =
659 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
660 }
661
662 *xaddrp = xaddr;
663
664 out:
665 /* unpin the leaf page */
666 XT_PUTPAGE(mp);
667
668 return rc;
669}
670
671
672/*
673 * xtSplitUp()
674 *
675 * function:
676 * split full pages as propagating insertion up the tree
677 *
678 * parameter:
679 * tid - transaction id;
680 * ip - file object;
681 * split - entry parameter descriptor;
682 * btstack - traverse stack from xtSearch()
683 *
684 * return:
685 */
686static int
687xtSplitUp(tid_t tid,
688 struct inode *ip, struct xtsplit * split, struct btstack * btstack)
689{
690 int rc = 0;
691 struct metapage *smp;
692 xtpage_t *sp; /* split page */
693 struct metapage *rmp;
694 s64 rbn; /* new right page block number */
695 struct metapage *rcmp;
696 xtpage_t *rcp; /* right child page */
697 s64 rcbn; /* right child page block number */
698 int skip; /* index of entry of insertion */
699 int nextindex; /* next available entry index of p */
700 struct btframe *parent; /* parent page entry on traverse stack */
701 xad_t *xad;
702 s64 xaddr;
703 int xlen;
704 int nsplit; /* number of pages split */
705 struct pxdlist pxdlist;
706 pxd_t *pxd;
707 struct tlock *tlck;
708 struct xtlock *xtlck;
709
710 smp = split->mp;
711 sp = XT_PAGE(ip, smp);
712
713 /* is inode xtree root extension/inline EA area free ? */
714 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
715 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
716 (JFS_IP(ip)->mode2 & INLINEEA)) {
717 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
718 JFS_IP(ip)->mode2 &= ~INLINEEA;
719
720 BT_MARK_DIRTY(smp, ip);
721 /*
722 * acquire a transaction lock on the leaf page;
723 *
724 * action: xad insertion/extension;
725 */
726
727 /* if insert into middle, shift right remaining entries. */
728 skip = split->index;
729 nextindex = le16_to_cpu(sp->header.nextindex);
730 if (skip < nextindex)
731 memmove(&sp->xad[skip + 1], &sp->xad[skip],
732 (nextindex - skip) * sizeof(xad_t));
733
734 /* insert the new entry: mark the entry NEW */
735 xad = &sp->xad[skip];
736 XT_PUTENTRY(xad, split->flag, split->off, split->len,
737 split->addr);
738
739 /* advance next available entry index */
740 le16_add_cpu(&sp->header.nextindex, 1);
741
742 /* Don't log it if there are no links to the file */
743 if (!test_cflag(COMMIT_Nolink, ip)) {
744 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
745 xtlck = (struct xtlock *) & tlck->lock;
746 xtlck->lwm.offset = (xtlck->lwm.offset) ?
747 min(skip, (int)xtlck->lwm.offset) : skip;
748 xtlck->lwm.length =
749 le16_to_cpu(sp->header.nextindex) -
750 xtlck->lwm.offset;
751 }
752
753 return 0;
754 }
755
756 /*
757 * allocate new index blocks to cover index page split(s)
758 *
759 * allocation hint: ?
760 */
761 if (split->pxdlist == NULL) {
762 nsplit = btstack->nsplit;
763 split->pxdlist = &pxdlist;
764 pxdlist.maxnpxd = pxdlist.npxd = 0;
765 pxd = &pxdlist.pxd[0];
766 xlen = JFS_SBI(ip->i_sb)->nbperpage;
767 for (; nsplit > 0; nsplit--, pxd++) {
768 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
769 == 0) {
770 PXDaddress(pxd, xaddr);
771 PXDlength(pxd, xlen);
772
773 pxdlist.maxnpxd++;
774
775 continue;
776 }
777
778 /* undo allocation */
779
780 XT_PUTPAGE(smp);
781 return rc;
782 }
783 }
784
785 /*
786 * Split leaf page <sp> into <sp> and a new right page <rp>.
787 *
788 * The split routines insert the new entry into the leaf page,
789 * and acquire txLock as appropriate.
790 * return <rp> pinned and its block number <rpbn>.
791 */
792 rc = (sp->header.flag & BT_ROOT) ?
793 xtSplitRoot(tid, ip, split, &rmp) :
794 xtSplitPage(tid, ip, split, &rmp, &rbn);
795
796 XT_PUTPAGE(smp);
797
798 if (rc)
799 return -EIO;
800 /*
801 * propagate up the router entry for the leaf page just split
802 *
803 * insert a router entry for the new page into the parent page,
804 * propagate the insert/split up the tree by walking back the stack
805 * of (bn of parent page, index of child page entry in parent page)
806 * that were traversed during the search for the page that split.
807 *
808 * the propagation of insert/split up the tree stops if the root
809 * splits or the page inserted into doesn't have to split to hold
810 * the new entry.
811 *
812 * the parent entry for the split page remains the same, and
813 * a new entry is inserted at its right with the first key and
814 * block number of the new right page.
815 *
816 * There are a maximum of 3 pages pinned at any time:
817 * right child, left parent and right parent (when the parent splits)
818 * to keep the child page pinned while working on the parent.
819 * make sure that all pins are released at exit.
820 */
821 while ((parent = BT_POP(btstack)) != NULL) {
822 /* parent page specified by stack frame <parent> */
823
824 /* keep current child pages <rcp> pinned */
825 rcmp = rmp;
826 rcbn = rbn;
827 rcp = XT_PAGE(ip, rcmp);
828
829 /*
830 * insert router entry in parent for new right child page <rp>
831 */
832 /* get/pin the parent page <sp> */
833 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
834 if (rc) {
835 XT_PUTPAGE(rcmp);
836 return rc;
837 }
838
839 /*
840 * The new key entry goes ONE AFTER the index of parent entry,
841 * because the split was to the right.
842 */
843 skip = parent->index + 1;
844
845 /*
846 * split or shift right remaining entries of the parent page
847 */
848 nextindex = le16_to_cpu(sp->header.nextindex);
849 /*
850 * parent page is full - split the parent page
851 */
852 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
853 /* init for parent page split */
854 split->mp = smp;
855 split->index = skip; /* index at insert */
856 split->flag = XAD_NEW;
857 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
858 split->len = JFS_SBI(ip->i_sb)->nbperpage;
859 split->addr = rcbn;
860
861 /* unpin previous right child page */
862 XT_PUTPAGE(rcmp);
863
864 /* The split routines insert the new entry,
865 * and acquire txLock as appropriate.
866 * return <rp> pinned and its block number <rpbn>.
867 */
868 rc = (sp->header.flag & BT_ROOT) ?
869 xtSplitRoot(tid, ip, split, &rmp) :
870 xtSplitPage(tid, ip, split, &rmp, &rbn);
871 if (rc) {
872 XT_PUTPAGE(smp);
873 return rc;
874 }
875
876 XT_PUTPAGE(smp);
877 /* keep new child page <rp> pinned */
878 }
879 /*
880 * parent page is not full - insert in parent page
881 */
882 else {
883 /*
884 * insert router entry in parent for the right child
885 * page from the first entry of the right child page:
886 */
887 /*
888 * acquire a transaction lock on the parent page;
889 *
890 * action: router xad insertion;
891 */
892 BT_MARK_DIRTY(smp, ip);
893
894 /*
895 * if insert into middle, shift right remaining entries
896 */
897 if (skip < nextindex)
898 memmove(&sp->xad[skip + 1], &sp->xad[skip],
899 (nextindex -
900 skip) << L2XTSLOTSIZE);
901
902 /* insert the router entry */
903 xad = &sp->xad[skip];
904 XT_PUTENTRY(xad, XAD_NEW,
905 offsetXAD(&rcp->xad[XTENTRYSTART]),
906 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
907
908 /* advance next available entry index. */
909 le16_add_cpu(&sp->header.nextindex, 1);
910
911 /* Don't log it if there are no links to the file */
912 if (!test_cflag(COMMIT_Nolink, ip)) {
913 tlck = txLock(tid, ip, smp,
914 tlckXTREE | tlckGROW);
915 xtlck = (struct xtlock *) & tlck->lock;
916 xtlck->lwm.offset = (xtlck->lwm.offset) ?
917 min(skip, (int)xtlck->lwm.offset) : skip;
918 xtlck->lwm.length =
919 le16_to_cpu(sp->header.nextindex) -
920 xtlck->lwm.offset;
921 }
922
923 /* unpin parent page */
924 XT_PUTPAGE(smp);
925
926 /* exit propagate up */
927 break;
928 }
929 }
930
931 /* unpin current right page */
932 XT_PUTPAGE(rmp);
933
934 return 0;
935}
936
937
938/*
939 * xtSplitPage()
940 *
941 * function:
942 * split a full non-root page into
943 * original/split/left page and new right page
944 * i.e., the original/split page remains as left page.
945 *
946 * parameter:
947 * int tid,
948 * struct inode *ip,
949 * struct xtsplit *split,
950 * struct metapage **rmpp,
951 * u64 *rbnp,
952 *
953 * return:
954 * Pointer to page in which to insert or NULL on error.
955 */
956static int
957xtSplitPage(tid_t tid, struct inode *ip,
958 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
959{
960 int rc = 0;
961 struct metapage *smp;
962 xtpage_t *sp;
963 struct metapage *rmp;
964 xtpage_t *rp; /* new right page allocated */
965 s64 rbn; /* new right page block number */
966 struct metapage *mp;
967 xtpage_t *p;
968 s64 nextbn;
969 int skip, maxentry, middle, righthalf, n;
970 xad_t *xad;
971 struct pxdlist *pxdlist;
972 pxd_t *pxd;
973 struct tlock *tlck;
974 struct xtlock *sxtlck = NULL, *rxtlck = NULL;
975 int quota_allocation = 0;
976
977 smp = split->mp;
978 sp = XT_PAGE(ip, smp);
979
980 INCREMENT(xtStat.split);
981
982 pxdlist = split->pxdlist;
983 pxd = &pxdlist->pxd[pxdlist->npxd];
984 pxdlist->npxd++;
985 rbn = addressPXD(pxd);
986
987 /* Allocate blocks to quota. */
988 rc = dquot_alloc_block(ip, lengthPXD(pxd));
989 if (rc)
990 goto clean_up;
991
992 quota_allocation += lengthPXD(pxd);
993
994 /*
995 * allocate the new right page for the split
996 */
997 rmp = get_metapage(ip, rbn, PSIZE, 1);
998 if (rmp == NULL) {
999 rc = -EIO;
1000 goto clean_up;
1001 }
1002
1003 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1004
1005 BT_MARK_DIRTY(rmp, ip);
1006 /*
1007 * action: new page;
1008 */
1009
1010 rp = (xtpage_t *) rmp->data;
1011 rp->header.self = *pxd;
1012 rp->header.flag = sp->header.flag & BT_TYPE;
1013 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1014 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1015
1016 BT_MARK_DIRTY(smp, ip);
1017 /* Don't log it if there are no links to the file */
1018 if (!test_cflag(COMMIT_Nolink, ip)) {
1019 /*
1020 * acquire a transaction lock on the new right page;
1021 */
1022 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1023 rxtlck = (struct xtlock *) & tlck->lock;
1024 rxtlck->lwm.offset = XTENTRYSTART;
1025 /*
1026 * acquire a transaction lock on the split page
1027 */
1028 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1029 sxtlck = (struct xtlock *) & tlck->lock;
1030 }
1031
1032 /*
1033 * initialize/update sibling pointers of <sp> and <rp>
1034 */
1035 nextbn = le64_to_cpu(sp->header.next);
1036 rp->header.next = cpu_to_le64(nextbn);
1037 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1038 sp->header.next = cpu_to_le64(rbn);
1039
1040 skip = split->index;
1041
1042 /*
1043 * sequential append at tail (after last entry of last page)
1044 *
1045 * if splitting the last page on a level because of appending
1046 * a entry to it (skip is maxentry), it's likely that the access is
1047 * sequential. adding an empty page on the side of the level is less
1048 * work and can push the fill factor much higher than normal.
1049 * if we're wrong it's no big deal - we will do the split the right
1050 * way next time.
1051 * (it may look like it's equally easy to do a similar hack for
1052 * reverse sorted data, that is, split the tree left, but it's not.
1053 * Be my guest.)
1054 */
1055 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1056 /*
1057 * acquire a transaction lock on the new/right page;
1058 *
1059 * action: xad insertion;
1060 */
1061 /* insert entry at the first entry of the new right page */
1062 xad = &rp->xad[XTENTRYSTART];
1063 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1064 split->addr);
1065
1066 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1067
1068 if (!test_cflag(COMMIT_Nolink, ip)) {
1069 /* rxtlck->lwm.offset = XTENTRYSTART; */
1070 rxtlck->lwm.length = 1;
1071 }
1072
1073 *rmpp = rmp;
1074 *rbnp = rbn;
1075
1076 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1077 return 0;
1078 }
1079
1080 /*
1081 * non-sequential insert (at possibly middle page)
1082 */
1083
1084 /*
1085 * update previous pointer of old next/right page of <sp>
1086 */
1087 if (nextbn != 0) {
1088 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1089 if (rc) {
1090 XT_PUTPAGE(rmp);
1091 goto clean_up;
1092 }
1093
1094 BT_MARK_DIRTY(mp, ip);
1095 /*
1096 * acquire a transaction lock on the next page;
1097 *
1098 * action:sibling pointer update;
1099 */
1100 if (!test_cflag(COMMIT_Nolink, ip))
1101 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1102
1103 p->header.prev = cpu_to_le64(rbn);
1104
1105 /* sibling page may have been updated previously, or
1106 * it may be updated later;
1107 */
1108
1109 XT_PUTPAGE(mp);
1110 }
1111
1112 /*
1113 * split the data between the split and new/right pages
1114 */
1115 maxentry = le16_to_cpu(sp->header.maxentry);
1116 middle = maxentry >> 1;
1117 righthalf = maxentry - middle;
1118
1119 /*
1120 * skip index in old split/left page - insert into left page:
1121 */
1122 if (skip <= middle) {
1123 /* move right half of split page to the new right page */
1124 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1125 righthalf << L2XTSLOTSIZE);
1126
1127 /* shift right tail of left half to make room for new entry */
1128 if (skip < middle)
1129 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1130 (middle - skip) << L2XTSLOTSIZE);
1131
1132 /* insert new entry */
1133 xad = &sp->xad[skip];
1134 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1135 split->addr);
1136
1137 /* update page header */
1138 sp->header.nextindex = cpu_to_le16(middle + 1);
1139 if (!test_cflag(COMMIT_Nolink, ip)) {
1140 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1141 min(skip, (int)sxtlck->lwm.offset) : skip;
1142 }
1143
1144 rp->header.nextindex =
1145 cpu_to_le16(XTENTRYSTART + righthalf);
1146 }
1147 /*
1148 * skip index in new right page - insert into right page:
1149 */
1150 else {
1151 /* move left head of right half to right page */
1152 n = skip - middle;
1153 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1154 n << L2XTSLOTSIZE);
1155
1156 /* insert new entry */
1157 n += XTENTRYSTART;
1158 xad = &rp->xad[n];
1159 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1160 split->addr);
1161
1162 /* move right tail of right half to right page */
1163 if (skip < maxentry)
1164 memmove(&rp->xad[n + 1], &sp->xad[skip],
1165 (maxentry - skip) << L2XTSLOTSIZE);
1166
1167 /* update page header */
1168 sp->header.nextindex = cpu_to_le16(middle);
1169 if (!test_cflag(COMMIT_Nolink, ip)) {
1170 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1171 min(middle, (int)sxtlck->lwm.offset) : middle;
1172 }
1173
1174 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1175 righthalf + 1);
1176 }
1177
1178 if (!test_cflag(COMMIT_Nolink, ip)) {
1179 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1180 sxtlck->lwm.offset;
1181
1182 /* rxtlck->lwm.offset = XTENTRYSTART; */
1183 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1184 XTENTRYSTART;
1185 }
1186
1187 *rmpp = rmp;
1188 *rbnp = rbn;
1189
1190 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1191 return rc;
1192
1193 clean_up:
1194
1195 /* Rollback quota allocation. */
1196 if (quota_allocation)
1197 dquot_free_block(ip, quota_allocation);
1198
1199 return (rc);
1200}
1201
1202
1203/*
1204 * xtSplitRoot()
1205 *
1206 * function:
1207 * split the full root page into original/root/split page and new
1208 * right page
1209 * i.e., root remains fixed in tree anchor (inode) and the root is
1210 * copied to a single new right child page since root page <<
1211 * non-root page, and the split root page contains a single entry
1212 * for the new right child page.
1213 *
1214 * parameter:
1215 * int tid,
1216 * struct inode *ip,
1217 * struct xtsplit *split,
1218 * struct metapage **rmpp)
1219 *
1220 * return:
1221 * Pointer to page in which to insert or NULL on error.
1222 */
1223static int
1224xtSplitRoot(tid_t tid,
1225 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1226{
1227 xtpage_t *sp;
1228 struct metapage *rmp;
1229 xtpage_t *rp;
1230 s64 rbn;
1231 int skip, nextindex;
1232 xad_t *xad;
1233 pxd_t *pxd;
1234 struct pxdlist *pxdlist;
1235 struct tlock *tlck;
1236 struct xtlock *xtlck;
1237 int rc;
1238
1239 sp = &JFS_IP(ip)->i_xtroot;
1240
1241 INCREMENT(xtStat.split);
1242
1243 /*
1244 * allocate a single (right) child page
1245 */
1246 pxdlist = split->pxdlist;
1247 pxd = &pxdlist->pxd[pxdlist->npxd];
1248 pxdlist->npxd++;
1249 rbn = addressPXD(pxd);
1250 rmp = get_metapage(ip, rbn, PSIZE, 1);
1251 if (rmp == NULL)
1252 return -EIO;
1253
1254 /* Allocate blocks to quota. */
1255 rc = dquot_alloc_block(ip, lengthPXD(pxd));
1256 if (rc) {
1257 release_metapage(rmp);
1258 return rc;
1259 }
1260
1261 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1262
1263 /*
1264 * acquire a transaction lock on the new right page;
1265 *
1266 * action: new page;
1267 */
1268 BT_MARK_DIRTY(rmp, ip);
1269
1270 rp = (xtpage_t *) rmp->data;
1271 rp->header.flag =
1272 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1273 rp->header.self = *pxd;
1274 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1275 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1276
1277 /* initialize sibling pointers */
1278 rp->header.next = 0;
1279 rp->header.prev = 0;
1280
1281 /*
1282 * copy the in-line root page into new right page extent
1283 */
1284 nextindex = le16_to_cpu(sp->header.maxentry);
1285 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1286 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1287
1288 /*
1289 * insert the new entry into the new right/child page
1290 * (skip index in the new right page will not change)
1291 */
1292 skip = split->index;
1293 /* if insert into middle, shift right remaining entries */
1294 if (skip != nextindex)
1295 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1296 (nextindex - skip) * sizeof(xad_t));
1297
1298 xad = &rp->xad[skip];
1299 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1300
1301 /* update page header */
1302 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1303
1304 if (!test_cflag(COMMIT_Nolink, ip)) {
1305 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1306 xtlck = (struct xtlock *) & tlck->lock;
1307 xtlck->lwm.offset = XTENTRYSTART;
1308 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1309 XTENTRYSTART;
1310 }
1311
1312 /*
1313 * reset the root
1314 *
1315 * init root with the single entry for the new right page
1316 * set the 1st entry offset to 0, which force the left-most key
1317 * at any level of the tree to be less than any search key.
1318 */
1319 /*
1320 * acquire a transaction lock on the root page (in-memory inode);
1321 *
1322 * action: root split;
1323 */
1324 BT_MARK_DIRTY(split->mp, ip);
1325
1326 xad = &sp->xad[XTENTRYSTART];
1327 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1328
1329 /* update page header of root */
1330 sp->header.flag &= ~BT_LEAF;
1331 sp->header.flag |= BT_INTERNAL;
1332
1333 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1334
1335 if (!test_cflag(COMMIT_Nolink, ip)) {
1336 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1337 xtlck = (struct xtlock *) & tlck->lock;
1338 xtlck->lwm.offset = XTENTRYSTART;
1339 xtlck->lwm.length = 1;
1340 }
1341
1342 *rmpp = rmp;
1343
1344 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1345 return 0;
1346}
1347
1348
1349/*
1350 * xtExtend()
1351 *
1352 * function: extend in-place;
1353 *
1354 * note: existing extent may or may not have been committed.
1355 * caller is responsible for pager buffer cache update, and
1356 * working block allocation map update;
1357 * update pmap: alloc whole extended extent;
1358 */
1359int xtExtend(tid_t tid, /* transaction id */
1360 struct inode *ip, s64 xoff, /* delta extent offset */
1361 s32 xlen, /* delta extent length */
1362 int flag)
1363{
1364 int rc = 0;
1365 int cmp;
1366 struct metapage *mp; /* meta-page buffer */
1367 xtpage_t *p; /* base B+-tree index page */
1368 s64 bn;
1369 int index, nextindex, len;
1370 struct btstack btstack; /* traverse stack */
1371 struct xtsplit split; /* split information */
1372 xad_t *xad;
1373 s64 xaddr;
1374 struct tlock *tlck;
1375 struct xtlock *xtlck = NULL;
1376
1377 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1378
1379 /* there must exist extent to be extended */
1380 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1381 return rc;
1382
1383 /* retrieve search result */
1384 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1385
1386 if (cmp != 0) {
1387 XT_PUTPAGE(mp);
1388 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1389 return -EIO;
1390 }
1391
1392 /* extension must be contiguous */
1393 xad = &p->xad[index];
1394 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1395 XT_PUTPAGE(mp);
1396 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1397 return -EIO;
1398 }
1399
1400 /*
1401 * acquire a transaction lock on the leaf page;
1402 *
1403 * action: xad insertion/extension;
1404 */
1405 BT_MARK_DIRTY(mp, ip);
1406 if (!test_cflag(COMMIT_Nolink, ip)) {
1407 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1408 xtlck = (struct xtlock *) & tlck->lock;
1409 }
1410
1411 /* extend will overflow extent ? */
1412 xlen = lengthXAD(xad) + xlen;
1413 if ((len = xlen - MAXXLEN) <= 0)
1414 goto extendOld;
1415
1416 /*
1417 * extent overflow: insert entry for new extent
1418 */
1419//insertNew:
1420 xoff = offsetXAD(xad) + MAXXLEN;
1421 xaddr = addressXAD(xad) + MAXXLEN;
1422 nextindex = le16_to_cpu(p->header.nextindex);
1423
1424 /*
1425 * if the leaf page is full, insert the new entry and
1426 * propagate up the router entry for the new page from split
1427 *
1428 * The xtSplitUp() will insert the entry and unpin the leaf page.
1429 */
1430 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1431 /* xtSpliUp() unpins leaf pages */
1432 split.mp = mp;
1433 split.index = index + 1;
1434 split.flag = XAD_NEW;
1435 split.off = xoff; /* split offset */
1436 split.len = len;
1437 split.addr = xaddr;
1438 split.pxdlist = NULL;
1439 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1440 return rc;
1441
1442 /* get back old page */
1443 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1444 if (rc)
1445 return rc;
1446 /*
1447 * if leaf root has been split, original root has been
1448 * copied to new child page, i.e., original entry now
1449 * resides on the new child page;
1450 */
1451 if (p->header.flag & BT_INTERNAL) {
1452 ASSERT(p->header.nextindex ==
1453 cpu_to_le16(XTENTRYSTART + 1));
1454 xad = &p->xad[XTENTRYSTART];
1455 bn = addressXAD(xad);
1456 XT_PUTPAGE(mp);
1457
1458 /* get new child page */
1459 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1460 if (rc)
1461 return rc;
1462
1463 BT_MARK_DIRTY(mp, ip);
1464 if (!test_cflag(COMMIT_Nolink, ip)) {
1465 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1466 xtlck = (struct xtlock *) & tlck->lock;
1467 }
1468 }
1469 }
1470 /*
1471 * insert the new entry into the leaf page
1472 */
1473 else {
1474 /* insert the new entry: mark the entry NEW */
1475 xad = &p->xad[index + 1];
1476 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1477
1478 /* advance next available entry index */
1479 le16_add_cpu(&p->header.nextindex, 1);
1480 }
1481
1482 /* get back old entry */
1483 xad = &p->xad[index];
1484 xlen = MAXXLEN;
1485
1486 /*
1487 * extend old extent
1488 */
1489 extendOld:
1490 XADlength(xad, xlen);
1491 if (!(xad->flag & XAD_NEW))
1492 xad->flag |= XAD_EXTENDED;
1493
1494 if (!test_cflag(COMMIT_Nolink, ip)) {
1495 xtlck->lwm.offset =
1496 (xtlck->lwm.offset) ? min(index,
1497 (int)xtlck->lwm.offset) : index;
1498 xtlck->lwm.length =
1499 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1500 }
1501
1502 /* unpin the leaf page */
1503 XT_PUTPAGE(mp);
1504
1505 return rc;
1506}
1507
1508#ifdef _NOTYET
1509/*
1510 * xtTailgate()
1511 *
1512 * function: split existing 'tail' extent
1513 * (split offset >= start offset of tail extent), and
1514 * relocate and extend the split tail half;
1515 *
1516 * note: existing extent may or may not have been committed.
1517 * caller is responsible for pager buffer cache update, and
1518 * working block allocation map update;
1519 * update pmap: free old split tail extent, alloc new extent;
1520 */
1521int xtTailgate(tid_t tid, /* transaction id */
1522 struct inode *ip, s64 xoff, /* split/new extent offset */
1523 s32 xlen, /* new extent length */
1524 s64 xaddr, /* new extent address */
1525 int flag)
1526{
1527 int rc = 0;
1528 int cmp;
1529 struct metapage *mp; /* meta-page buffer */
1530 xtpage_t *p; /* base B+-tree index page */
1531 s64 bn;
1532 int index, nextindex, llen, rlen;
1533 struct btstack btstack; /* traverse stack */
1534 struct xtsplit split; /* split information */
1535 xad_t *xad;
1536 struct tlock *tlck;
1537 struct xtlock *xtlck = 0;
1538 struct tlock *mtlck;
1539 struct maplock *pxdlock;
1540
1541/*
1542printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1543 (ulong)xoff, xlen, (ulong)xaddr);
1544*/
1545
1546 /* there must exist extent to be tailgated */
1547 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1548 return rc;
1549
1550 /* retrieve search result */
1551 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1552
1553 if (cmp != 0) {
1554 XT_PUTPAGE(mp);
1555 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
1556 return -EIO;
1557 }
1558
1559 /* entry found must be last entry */
1560 nextindex = le16_to_cpu(p->header.nextindex);
1561 if (index != nextindex - 1) {
1562 XT_PUTPAGE(mp);
1563 jfs_error(ip->i_sb,
1564 "xtTailgate: the entry found is not the last entry");
1565 return -EIO;
1566 }
1567
1568 BT_MARK_DIRTY(mp, ip);
1569 /*
1570 * acquire tlock of the leaf page containing original entry
1571 */
1572 if (!test_cflag(COMMIT_Nolink, ip)) {
1573 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1574 xtlck = (struct xtlock *) & tlck->lock;
1575 }
1576
1577 /* completely replace extent ? */
1578 xad = &p->xad[index];
1579/*
1580printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1581 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1582*/
1583 if ((llen = xoff - offsetXAD(xad)) == 0)
1584 goto updateOld;
1585
1586 /*
1587 * partially replace extent: insert entry for new extent
1588 */
1589//insertNew:
1590 /*
1591 * if the leaf page is full, insert the new entry and
1592 * propagate up the router entry for the new page from split
1593 *
1594 * The xtSplitUp() will insert the entry and unpin the leaf page.
1595 */
1596 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1597 /* xtSpliUp() unpins leaf pages */
1598 split.mp = mp;
1599 split.index = index + 1;
1600 split.flag = XAD_NEW;
1601 split.off = xoff; /* split offset */
1602 split.len = xlen;
1603 split.addr = xaddr;
1604 split.pxdlist = NULL;
1605 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1606 return rc;
1607
1608 /* get back old page */
1609 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1610 if (rc)
1611 return rc;
1612 /*
1613 * if leaf root has been split, original root has been
1614 * copied to new child page, i.e., original entry now
1615 * resides on the new child page;
1616 */
1617 if (p->header.flag & BT_INTERNAL) {
1618 ASSERT(p->header.nextindex ==
1619 cpu_to_le16(XTENTRYSTART + 1));
1620 xad = &p->xad[XTENTRYSTART];
1621 bn = addressXAD(xad);
1622 XT_PUTPAGE(mp);
1623
1624 /* get new child page */
1625 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1626 if (rc)
1627 return rc;
1628
1629 BT_MARK_DIRTY(mp, ip);
1630 if (!test_cflag(COMMIT_Nolink, ip)) {
1631 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1632 xtlck = (struct xtlock *) & tlck->lock;
1633 }
1634 }
1635 }
1636 /*
1637 * insert the new entry into the leaf page
1638 */
1639 else {
1640 /* insert the new entry: mark the entry NEW */
1641 xad = &p->xad[index + 1];
1642 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1643
1644 /* advance next available entry index */
1645 le16_add_cpu(&p->header.nextindex, 1);
1646 }
1647
1648 /* get back old XAD */
1649 xad = &p->xad[index];
1650
1651 /*
1652 * truncate/relocate old extent at split offset
1653 */
1654 updateOld:
1655 /* update dmap for old/committed/truncated extent */
1656 rlen = lengthXAD(xad) - llen;
1657 if (!(xad->flag & XAD_NEW)) {
1658 /* free from PWMAP at commit */
1659 if (!test_cflag(COMMIT_Nolink, ip)) {
1660 mtlck = txMaplock(tid, ip, tlckMAP);
1661 pxdlock = (struct maplock *) & mtlck->lock;
1662 pxdlock->flag = mlckFREEPXD;
1663 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1664 PXDlength(&pxdlock->pxd, rlen);
1665 pxdlock->index = 1;
1666 }
1667 } else
1668 /* free from WMAP */
1669 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1670
1671 if (llen)
1672 /* truncate */
1673 XADlength(xad, llen);
1674 else
1675 /* replace */
1676 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1677
1678 if (!test_cflag(COMMIT_Nolink, ip)) {
1679 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1680 min(index, (int)xtlck->lwm.offset) : index;
1681 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1682 xtlck->lwm.offset;
1683 }
1684
1685 /* unpin the leaf page */
1686 XT_PUTPAGE(mp);
1687
1688 return rc;
1689}
1690#endif /* _NOTYET */
1691
1692/*
1693 * xtUpdate()
1694 *
1695 * function: update XAD;
1696 *
1697 * update extent for allocated_but_not_recorded or
1698 * compressed extent;
1699 *
1700 * parameter:
1701 * nxad - new XAD;
1702 * logical extent of the specified XAD must be completely
1703 * contained by an existing XAD;
1704 */
1705int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1706{ /* new XAD */
1707 int rc = 0;
1708 int cmp;
1709 struct metapage *mp; /* meta-page buffer */
1710 xtpage_t *p; /* base B+-tree index page */
1711 s64 bn;
1712 int index0, index, newindex, nextindex;
1713 struct btstack btstack; /* traverse stack */
1714 struct xtsplit split; /* split information */
1715 xad_t *xad, *lxad, *rxad;
1716 int xflag;
1717 s64 nxoff, xoff;
1718 int nxlen, xlen, lxlen, rxlen;
1719 s64 nxaddr, xaddr;
1720 struct tlock *tlck;
1721 struct xtlock *xtlck = NULL;
1722 int newpage = 0;
1723
1724 /* there must exist extent to be tailgated */
1725 nxoff = offsetXAD(nxad);
1726 nxlen = lengthXAD(nxad);
1727 nxaddr = addressXAD(nxad);
1728
1729 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1730 return rc;
1731
1732 /* retrieve search result */
1733 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1734
1735 if (cmp != 0) {
1736 XT_PUTPAGE(mp);
1737 jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
1738 return -EIO;
1739 }
1740
1741 BT_MARK_DIRTY(mp, ip);
1742 /*
1743 * acquire tlock of the leaf page containing original entry
1744 */
1745 if (!test_cflag(COMMIT_Nolink, ip)) {
1746 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1747 xtlck = (struct xtlock *) & tlck->lock;
1748 }
1749
1750 xad = &p->xad[index0];
1751 xflag = xad->flag;
1752 xoff = offsetXAD(xad);
1753 xlen = lengthXAD(xad);
1754 xaddr = addressXAD(xad);
1755
1756 /* nXAD must be completely contained within XAD */
1757 if ((xoff > nxoff) ||
1758 (nxoff + nxlen > xoff + xlen)) {
1759 XT_PUTPAGE(mp);
1760 jfs_error(ip->i_sb,
1761 "xtUpdate: nXAD in not completely contained within XAD");
1762 return -EIO;
1763 }
1764
1765 index = index0;
1766 newindex = index + 1;
1767 nextindex = le16_to_cpu(p->header.nextindex);
1768
1769#ifdef _JFS_WIP_NOCOALESCE
1770 if (xoff < nxoff)
1771 goto updateRight;
1772
1773 /*
1774 * replace XAD with nXAD
1775 */
1776 replace: /* (nxoff == xoff) */
1777 if (nxlen == xlen) {
1778 /* replace XAD with nXAD:recorded */
1779 *xad = *nxad;
1780 xad->flag = xflag & ~XAD_NOTRECORDED;
1781
1782 goto out;
1783 } else /* (nxlen < xlen) */
1784 goto updateLeft;
1785#endif /* _JFS_WIP_NOCOALESCE */
1786
1787/* #ifdef _JFS_WIP_COALESCE */
1788 if (xoff < nxoff)
1789 goto coalesceRight;
1790
1791 /*
1792 * coalesce with left XAD
1793 */
1794//coalesceLeft: /* (xoff == nxoff) */
1795 /* is XAD first entry of page ? */
1796 if (index == XTENTRYSTART)
1797 goto replace;
1798
1799 /* is nXAD logically and physically contiguous with lXAD ? */
1800 lxad = &p->xad[index - 1];
1801 lxlen = lengthXAD(lxad);
1802 if (!(lxad->flag & XAD_NOTRECORDED) &&
1803 (nxoff == offsetXAD(lxad) + lxlen) &&
1804 (nxaddr == addressXAD(lxad) + lxlen) &&
1805 (lxlen + nxlen < MAXXLEN)) {
1806 /* extend right lXAD */
1807 index0 = index - 1;
1808 XADlength(lxad, lxlen + nxlen);
1809
1810 /* If we just merged two extents together, need to make sure the
1811 * right extent gets logged. If the left one is marked XAD_NEW,
1812 * then we know it will be logged. Otherwise, mark as
1813 * XAD_EXTENDED
1814 */
1815 if (!(lxad->flag & XAD_NEW))
1816 lxad->flag |= XAD_EXTENDED;
1817
1818 if (xlen > nxlen) {
1819 /* truncate XAD */
1820 XADoffset(xad, xoff + nxlen);
1821 XADlength(xad, xlen - nxlen);
1822 XADaddress(xad, xaddr + nxlen);
1823 goto out;
1824 } else { /* (xlen == nxlen) */
1825
1826 /* remove XAD */
1827 if (index < nextindex - 1)
1828 memmove(&p->xad[index], &p->xad[index + 1],
1829 (nextindex - index -
1830 1) << L2XTSLOTSIZE);
1831
1832 p->header.nextindex =
1833 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1834 1);
1835
1836 index = index0;
1837 newindex = index + 1;
1838 nextindex = le16_to_cpu(p->header.nextindex);
1839 xoff = nxoff = offsetXAD(lxad);
1840 xlen = nxlen = lxlen + nxlen;
1841 xaddr = nxaddr = addressXAD(lxad);
1842 goto coalesceRight;
1843 }
1844 }
1845
1846 /*
1847 * replace XAD with nXAD
1848 */
1849 replace: /* (nxoff == xoff) */
1850 if (nxlen == xlen) {
1851 /* replace XAD with nXAD:recorded */
1852 *xad = *nxad;
1853 xad->flag = xflag & ~XAD_NOTRECORDED;
1854
1855 goto coalesceRight;
1856 } else /* (nxlen < xlen) */
1857 goto updateLeft;
1858
1859 /*
1860 * coalesce with right XAD
1861 */
1862 coalesceRight: /* (xoff <= nxoff) */
1863 /* is XAD last entry of page ? */
1864 if (newindex == nextindex) {
1865 if (xoff == nxoff)
1866 goto out;
1867 goto updateRight;
1868 }
1869
1870 /* is nXAD logically and physically contiguous with rXAD ? */
1871 rxad = &p->xad[index + 1];
1872 rxlen = lengthXAD(rxad);
1873 if (!(rxad->flag & XAD_NOTRECORDED) &&
1874 (nxoff + nxlen == offsetXAD(rxad)) &&
1875 (nxaddr + nxlen == addressXAD(rxad)) &&
1876 (rxlen + nxlen < MAXXLEN)) {
1877 /* extend left rXAD */
1878 XADoffset(rxad, nxoff);
1879 XADlength(rxad, rxlen + nxlen);
1880 XADaddress(rxad, nxaddr);
1881
1882 /* If we just merged two extents together, need to make sure
1883 * the left extent gets logged. If the right one is marked
1884 * XAD_NEW, then we know it will be logged. Otherwise, mark as
1885 * XAD_EXTENDED
1886 */
1887 if (!(rxad->flag & XAD_NEW))
1888 rxad->flag |= XAD_EXTENDED;
1889
1890 if (xlen > nxlen)
1891 /* truncate XAD */
1892 XADlength(xad, xlen - nxlen);
1893 else { /* (xlen == nxlen) */
1894
1895 /* remove XAD */
1896 memmove(&p->xad[index], &p->xad[index + 1],
1897 (nextindex - index - 1) << L2XTSLOTSIZE);
1898
1899 p->header.nextindex =
1900 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1901 1);
1902 }
1903
1904 goto out;
1905 } else if (xoff == nxoff)
1906 goto out;
1907
1908 if (xoff >= nxoff) {
1909 XT_PUTPAGE(mp);
1910 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
1911 return -EIO;
1912 }
1913/* #endif _JFS_WIP_COALESCE */
1914
1915 /*
1916 * split XAD into (lXAD, nXAD):
1917 *
1918 * |---nXAD--->
1919 * --|----------XAD----------|--
1920 * |-lXAD-|
1921 */
1922 updateRight: /* (xoff < nxoff) */
1923 /* truncate old XAD as lXAD:not_recorded */
1924 xad = &p->xad[index];
1925 XADlength(xad, nxoff - xoff);
1926
1927 /* insert nXAD:recorded */
1928 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1929
1930 /* xtSpliUp() unpins leaf pages */
1931 split.mp = mp;
1932 split.index = newindex;
1933 split.flag = xflag & ~XAD_NOTRECORDED;
1934 split.off = nxoff;
1935 split.len = nxlen;
1936 split.addr = nxaddr;
1937 split.pxdlist = NULL;
1938 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1939 return rc;
1940
1941 /* get back old page */
1942 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1943 if (rc)
1944 return rc;
1945 /*
1946 * if leaf root has been split, original root has been
1947 * copied to new child page, i.e., original entry now
1948 * resides on the new child page;
1949 */
1950 if (p->header.flag & BT_INTERNAL) {
1951 ASSERT(p->header.nextindex ==
1952 cpu_to_le16(XTENTRYSTART + 1));
1953 xad = &p->xad[XTENTRYSTART];
1954 bn = addressXAD(xad);
1955 XT_PUTPAGE(mp);
1956
1957 /* get new child page */
1958 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1959 if (rc)
1960 return rc;
1961
1962 BT_MARK_DIRTY(mp, ip);
1963 if (!test_cflag(COMMIT_Nolink, ip)) {
1964 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1965 xtlck = (struct xtlock *) & tlck->lock;
1966 }
1967 } else {
1968 /* is nXAD on new page ? */
1969 if (newindex >
1970 (le16_to_cpu(p->header.maxentry) >> 1)) {
1971 newindex =
1972 newindex -
1973 le16_to_cpu(p->header.nextindex) +
1974 XTENTRYSTART;
1975 newpage = 1;
1976 }
1977 }
1978 } else {
1979 /* if insert into middle, shift right remaining entries */
1980 if (newindex < nextindex)
1981 memmove(&p->xad[newindex + 1], &p->xad[newindex],
1982 (nextindex - newindex) << L2XTSLOTSIZE);
1983
1984 /* insert the entry */
1985 xad = &p->xad[newindex];
1986 *xad = *nxad;
1987 xad->flag = xflag & ~XAD_NOTRECORDED;
1988
1989 /* advance next available entry index. */
1990 p->header.nextindex =
1991 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1992 }
1993
1994 /*
1995 * does nXAD force 3-way split ?
1996 *
1997 * |---nXAD--->|
1998 * --|----------XAD-------------|--
1999 * |-lXAD-| |-rXAD -|
2000 */
2001 if (nxoff + nxlen == xoff + xlen)
2002 goto out;
2003
2004 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2005 if (newpage) {
2006 /* close out old page */
2007 if (!test_cflag(COMMIT_Nolink, ip)) {
2008 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2009 min(index0, (int)xtlck->lwm.offset) : index0;
2010 xtlck->lwm.length =
2011 le16_to_cpu(p->header.nextindex) -
2012 xtlck->lwm.offset;
2013 }
2014
2015 bn = le64_to_cpu(p->header.next);
2016 XT_PUTPAGE(mp);
2017
2018 /* get new right page */
2019 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2020 if (rc)
2021 return rc;
2022
2023 BT_MARK_DIRTY(mp, ip);
2024 if (!test_cflag(COMMIT_Nolink, ip)) {
2025 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2026 xtlck = (struct xtlock *) & tlck->lock;
2027 }
2028
2029 index0 = index = newindex;
2030 } else
2031 index++;
2032
2033 newindex = index + 1;
2034 nextindex = le16_to_cpu(p->header.nextindex);
2035 xlen = xlen - (nxoff - xoff);
2036 xoff = nxoff;
2037 xaddr = nxaddr;
2038
2039 /* recompute split pages */
2040 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2041 XT_PUTPAGE(mp);
2042
2043 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2044 return rc;
2045
2046 /* retrieve search result */
2047 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2048
2049 if (cmp != 0) {
2050 XT_PUTPAGE(mp);
2051 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
2052 return -EIO;
2053 }
2054
2055 if (index0 != index) {
2056 XT_PUTPAGE(mp);
2057 jfs_error(ip->i_sb,
2058 "xtUpdate: unexpected value of index");
2059 return -EIO;
2060 }
2061 }
2062
2063 /*
2064 * split XAD into (nXAD, rXAD)
2065 *
2066 * ---nXAD---|
2067 * --|----------XAD----------|--
2068 * |-rXAD-|
2069 */
2070 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2071 /* update old XAD with nXAD:recorded */
2072 xad = &p->xad[index];
2073 *xad = *nxad;
2074 xad->flag = xflag & ~XAD_NOTRECORDED;
2075
2076 /* insert rXAD:not_recorded */
2077 xoff = xoff + nxlen;
2078 xlen = xlen - nxlen;
2079 xaddr = xaddr + nxlen;
2080 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2081/*
2082printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2083*/
2084 /* xtSpliUp() unpins leaf pages */
2085 split.mp = mp;
2086 split.index = newindex;
2087 split.flag = xflag;
2088 split.off = xoff;
2089 split.len = xlen;
2090 split.addr = xaddr;
2091 split.pxdlist = NULL;
2092 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2093 return rc;
2094
2095 /* get back old page */
2096 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2097 if (rc)
2098 return rc;
2099
2100 /*
2101 * if leaf root has been split, original root has been
2102 * copied to new child page, i.e., original entry now
2103 * resides on the new child page;
2104 */
2105 if (p->header.flag & BT_INTERNAL) {
2106 ASSERT(p->header.nextindex ==
2107 cpu_to_le16(XTENTRYSTART + 1));
2108 xad = &p->xad[XTENTRYSTART];
2109 bn = addressXAD(xad);
2110 XT_PUTPAGE(mp);
2111
2112 /* get new child page */
2113 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2114 if (rc)
2115 return rc;
2116
2117 BT_MARK_DIRTY(mp, ip);
2118 if (!test_cflag(COMMIT_Nolink, ip)) {
2119 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2120 xtlck = (struct xtlock *) & tlck->lock;
2121 }
2122 }
2123 } else {
2124 /* if insert into middle, shift right remaining entries */
2125 if (newindex < nextindex)
2126 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2127 (nextindex - newindex) << L2XTSLOTSIZE);
2128
2129 /* insert the entry */
2130 xad = &p->xad[newindex];
2131 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2132
2133 /* advance next available entry index. */
2134 p->header.nextindex =
2135 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2136 }
2137
2138 out:
2139 if (!test_cflag(COMMIT_Nolink, ip)) {
2140 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2141 min(index0, (int)xtlck->lwm.offset) : index0;
2142 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2143 xtlck->lwm.offset;
2144 }
2145
2146 /* unpin the leaf page */
2147 XT_PUTPAGE(mp);
2148
2149 return rc;
2150}
2151
2152
2153/*
2154 * xtAppend()
2155 *
2156 * function: grow in append mode from contiguous region specified ;
2157 *
2158 * parameter:
2159 * tid - transaction id;
2160 * ip - file object;
2161 * xflag - extent flag:
2162 * xoff - extent offset;
2163 * maxblocks - max extent length;
2164 * xlen - extent length (in/out);
2165 * xaddrp - extent address pointer (in/out):
2166 * flag -
2167 *
2168 * return:
2169 */
2170int xtAppend(tid_t tid, /* transaction id */
2171 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2172 s32 * xlenp, /* (in/out) */
2173 s64 * xaddrp, /* (in/out) */
2174 int flag)
2175{
2176 int rc = 0;
2177 struct metapage *mp; /* meta-page buffer */
2178 xtpage_t *p; /* base B+-tree index page */
2179 s64 bn, xaddr;
2180 int index, nextindex;
2181 struct btstack btstack; /* traverse stack */
2182 struct xtsplit split; /* split information */
2183 xad_t *xad;
2184 int cmp;
2185 struct tlock *tlck;
2186 struct xtlock *xtlck;
2187 int nsplit, nblocks, xlen;
2188 struct pxdlist pxdlist;
2189 pxd_t *pxd;
2190 s64 next;
2191
2192 xaddr = *xaddrp;
2193 xlen = *xlenp;
2194 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2195 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2196
2197 /*
2198 * search for the entry location at which to insert:
2199 *
2200 * xtFastSearch() and xtSearch() both returns (leaf page
2201 * pinned, index at which to insert).
2202 * n.b. xtSearch() may return index of maxentry of
2203 * the full page.
2204 */
2205 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2206 return rc;
2207
2208 /* retrieve search result */
2209 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2210
2211 if (cmp == 0) {
2212 rc = -EEXIST;
2213 goto out;
2214 }
2215
2216 if (next)
2217 xlen = min(xlen, (int)(next - xoff));
2218//insert:
2219 /*
2220 * insert entry for new extent
2221 */
2222 xflag |= XAD_NEW;
2223
2224 /*
2225 * if the leaf page is full, split the page and
2226 * propagate up the router entry for the new page from split
2227 *
2228 * The xtSplitUp() will insert the entry and unpin the leaf page.
2229 */
2230 nextindex = le16_to_cpu(p->header.nextindex);
2231 if (nextindex < le16_to_cpu(p->header.maxentry))
2232 goto insertLeaf;
2233
2234 /*
2235 * allocate new index blocks to cover index page split(s)
2236 */
2237 nsplit = btstack.nsplit;
2238 split.pxdlist = &pxdlist;
2239 pxdlist.maxnpxd = pxdlist.npxd = 0;
2240 pxd = &pxdlist.pxd[0];
2241 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2242 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2243 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2244 PXDaddress(pxd, xaddr);
2245 PXDlength(pxd, nblocks);
2246
2247 pxdlist.maxnpxd++;
2248
2249 continue;
2250 }
2251
2252 /* undo allocation */
2253
2254 goto out;
2255 }
2256
2257 xlen = min(xlen, maxblocks);
2258
2259 /*
2260 * allocate data extent requested
2261 */
2262 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2263 goto out;
2264
2265 split.mp = mp;
2266 split.index = index;
2267 split.flag = xflag;
2268 split.off = xoff;
2269 split.len = xlen;
2270 split.addr = xaddr;
2271 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2272 /* undo data extent allocation */
2273 dbFree(ip, *xaddrp, (s64) * xlenp);
2274
2275 return rc;
2276 }
2277
2278 *xaddrp = xaddr;
2279 *xlenp = xlen;
2280 return 0;
2281
2282 /*
2283 * insert the new entry into the leaf page
2284 */
2285 insertLeaf:
2286 /*
2287 * allocate data extent requested
2288 */
2289 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2290 goto out;
2291
2292 BT_MARK_DIRTY(mp, ip);
2293 /*
2294 * acquire a transaction lock on the leaf page;
2295 *
2296 * action: xad insertion/extension;
2297 */
2298 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2299 xtlck = (struct xtlock *) & tlck->lock;
2300
2301 /* insert the new entry: mark the entry NEW */
2302 xad = &p->xad[index];
2303 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2304
2305 /* advance next available entry index */
2306 le16_add_cpu(&p->header.nextindex, 1);
2307
2308 xtlck->lwm.offset =
2309 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2310 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2311 xtlck->lwm.offset;
2312
2313 *xaddrp = xaddr;
2314 *xlenp = xlen;
2315
2316 out:
2317 /* unpin the leaf page */
2318 XT_PUTPAGE(mp);
2319
2320 return rc;
2321}
2322#ifdef _STILL_TO_PORT
2323
2324/* - TBD for defragmentaion/reorganization -
2325 *
2326 * xtDelete()
2327 *
2328 * function:
2329 * delete the entry with the specified key.
2330 *
2331 * N.B.: whole extent of the entry is assumed to be deleted.
2332 *
2333 * parameter:
2334 *
2335 * return:
2336 * ENOENT: if the entry is not found.
2337 *
2338 * exception:
2339 */
2340int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2341{
2342 int rc = 0;
2343 struct btstack btstack;
2344 int cmp;
2345 s64 bn;
2346 struct metapage *mp;
2347 xtpage_t *p;
2348 int index, nextindex;
2349 struct tlock *tlck;
2350 struct xtlock *xtlck;
2351
2352 /*
2353 * find the matching entry; xtSearch() pins the page
2354 */
2355 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2356 return rc;
2357
2358 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2359 if (cmp) {
2360 /* unpin the leaf page */
2361 XT_PUTPAGE(mp);
2362 return -ENOENT;
2363 }
2364
2365 /*
2366 * delete the entry from the leaf page
2367 */
2368 nextindex = le16_to_cpu(p->header.nextindex);
2369 le16_add_cpu(&p->header.nextindex, -1);
2370
2371 /*
2372 * if the leaf page bocome empty, free the page
2373 */
2374 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2375 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2376
2377 BT_MARK_DIRTY(mp, ip);
2378 /*
2379 * acquire a transaction lock on the leaf page;
2380 *
2381 * action:xad deletion;
2382 */
2383 tlck = txLock(tid, ip, mp, tlckXTREE);
2384 xtlck = (struct xtlock *) & tlck->lock;
2385 xtlck->lwm.offset =
2386 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2387
2388 /* if delete from middle, shift left/compact the remaining entries */
2389 if (index < nextindex - 1)
2390 memmove(&p->xad[index], &p->xad[index + 1],
2391 (nextindex - index - 1) * sizeof(xad_t));
2392
2393 XT_PUTPAGE(mp);
2394
2395 return 0;
2396}
2397
2398
2399/* - TBD for defragmentaion/reorganization -
2400 *
2401 * xtDeleteUp()
2402 *
2403 * function:
2404 * free empty pages as propagating deletion up the tree
2405 *
2406 * parameter:
2407 *
2408 * return:
2409 */
2410static int
2411xtDeleteUp(tid_t tid, struct inode *ip,
2412 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2413{
2414 int rc = 0;
2415 struct metapage *mp;
2416 xtpage_t *p;
2417 int index, nextindex;
2418 s64 xaddr;
2419 int xlen;
2420 struct btframe *parent;
2421 struct tlock *tlck;
2422 struct xtlock *xtlck;
2423
2424 /*
2425 * keep root leaf page which has become empty
2426 */
2427 if (fp->header.flag & BT_ROOT) {
2428 /* keep the root page */
2429 fp->header.flag &= ~BT_INTERNAL;
2430 fp->header.flag |= BT_LEAF;
2431 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2432
2433 /* XT_PUTPAGE(fmp); */
2434
2435 return 0;
2436 }
2437
2438 /*
2439 * free non-root leaf page
2440 */
2441 if ((rc = xtRelink(tid, ip, fp))) {
2442 XT_PUTPAGE(fmp);
2443 return rc;
2444 }
2445
2446 xaddr = addressPXD(&fp->header.self);
2447 xlen = lengthPXD(&fp->header.self);
2448 /* free the page extent */
2449 dbFree(ip, xaddr, (s64) xlen);
2450
2451 /* free the buffer page */
2452 discard_metapage(fmp);
2453
2454 /*
2455 * propagate page deletion up the index tree
2456 *
2457 * If the delete from the parent page makes it empty,
2458 * continue all the way up the tree.
2459 * stop if the root page is reached (which is never deleted) or
2460 * if the entry deletion does not empty the page.
2461 */
2462 while ((parent = BT_POP(btstack)) != NULL) {
2463 /* get/pin the parent page <sp> */
2464 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2465 if (rc)
2466 return rc;
2467
2468 index = parent->index;
2469
2470 /* delete the entry for the freed child page from parent.
2471 */
2472 nextindex = le16_to_cpu(p->header.nextindex);
2473
2474 /*
2475 * the parent has the single entry being deleted:
2476 * free the parent page which has become empty.
2477 */
2478 if (nextindex == 1) {
2479 if (p->header.flag & BT_ROOT) {
2480 /* keep the root page */
2481 p->header.flag &= ~BT_INTERNAL;
2482 p->header.flag |= BT_LEAF;
2483 p->header.nextindex =
2484 cpu_to_le16(XTENTRYSTART);
2485
2486 /* XT_PUTPAGE(mp); */
2487
2488 break;
2489 } else {
2490 /* free the parent page */
2491 if ((rc = xtRelink(tid, ip, p)))
2492 return rc;
2493
2494 xaddr = addressPXD(&p->header.self);
2495 /* free the page extent */
2496 dbFree(ip, xaddr,
2497 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2498
2499 /* unpin/free the buffer page */
2500 discard_metapage(mp);
2501
2502 /* propagate up */
2503 continue;
2504 }
2505 }
2506 /*
2507 * the parent has other entries remaining:
2508 * delete the router entry from the parent page.
2509 */
2510 else {
2511 BT_MARK_DIRTY(mp, ip);
2512 /*
2513 * acquire a transaction lock on the leaf page;
2514 *
2515 * action:xad deletion;
2516 */
2517 tlck = txLock(tid, ip, mp, tlckXTREE);
2518 xtlck = (struct xtlock *) & tlck->lock;
2519 xtlck->lwm.offset =
2520 (xtlck->lwm.offset) ? min(index,
2521 xtlck->lwm.
2522 offset) : index;
2523
2524 /* if delete from middle,
2525 * shift left/compact the remaining entries in the page
2526 */
2527 if (index < nextindex - 1)
2528 memmove(&p->xad[index], &p->xad[index + 1],
2529 (nextindex - index -
2530 1) << L2XTSLOTSIZE);
2531
2532 le16_add_cpu(&p->header.nextindex, -1);
2533 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2534 (ulong) parent->bn, index);
2535 }
2536
2537 /* unpin the parent page */
2538 XT_PUTPAGE(mp);
2539
2540 /* exit propagation up */
2541 break;
2542 }
2543
2544 return 0;
2545}
2546
2547
2548/*
2549 * NAME: xtRelocate()
2550 *
2551 * FUNCTION: relocate xtpage or data extent of regular file;
2552 * This function is mainly used by defragfs utility.
2553 *
2554 * NOTE: This routine does not have the logic to handle
2555 * uncommitted allocated extent. The caller should call
2556 * txCommit() to commit all the allocation before call
2557 * this routine.
2558 */
2559int
2560xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2561 s64 nxaddr, /* new xaddr */
2562 int xtype)
2563{ /* extent type: XTPAGE or DATAEXT */
2564 int rc = 0;
2565 struct tblock *tblk;
2566 struct tlock *tlck;
2567 struct xtlock *xtlck;
2568 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2569 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2570 xad_t *xad;
2571 pxd_t *pxd;
2572 s64 xoff, xsize;
2573 int xlen;
2574 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2575 cbuf_t *cp;
2576 s64 offset, nbytes, nbrd, pno;
2577 int nb, npages, nblks;
2578 s64 bn;
2579 int cmp;
2580 int index;
2581 struct pxd_lock *pxdlock;
2582 struct btstack btstack; /* traverse stack */
2583
2584 xtype = xtype & EXTENT_TYPE;
2585
2586 xoff = offsetXAD(oxad);
2587 oxaddr = addressXAD(oxad);
2588 xlen = lengthXAD(oxad);
2589
2590 /* validate extent offset */
2591 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2592 if (offset >= ip->i_size)
2593 return -ESTALE; /* stale extent */
2594
2595 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2596 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2597
2598 /*
2599 * 1. get and validate the parent xtpage/xad entry
2600 * covering the source extent to be relocated;
2601 */
2602 if (xtype == DATAEXT) {
2603 /* search in leaf entry */
2604 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2605 if (rc)
2606 return rc;
2607
2608 /* retrieve search result */
2609 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2610
2611 if (cmp) {
2612 XT_PUTPAGE(pmp);
2613 return -ESTALE;
2614 }
2615
2616 /* validate for exact match with a single entry */
2617 xad = &pp->xad[index];
2618 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2619 XT_PUTPAGE(pmp);
2620 return -ESTALE;
2621 }
2622 } else { /* (xtype == XTPAGE) */
2623
2624 /* search in internal entry */
2625 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2626 if (rc)
2627 return rc;
2628
2629 /* retrieve search result */
2630 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2631
2632 if (cmp) {
2633 XT_PUTPAGE(pmp);
2634 return -ESTALE;
2635 }
2636
2637 /* xtSearchNode() validated for exact match with a single entry
2638 */
2639 xad = &pp->xad[index];
2640 }
2641 jfs_info("xtRelocate: parent xad entry validated.");
2642
2643 /*
2644 * 2. relocate the extent
2645 */
2646 if (xtype == DATAEXT) {
2647 /* if the extent is allocated-but-not-recorded
2648 * there is no real data to be moved in this extent,
2649 */
2650 if (xad->flag & XAD_NOTRECORDED)
2651 goto out;
2652 else
2653 /* release xtpage for cmRead()/xtLookup() */
2654 XT_PUTPAGE(pmp);
2655
2656 /*
2657 * cmRelocate()
2658 *
2659 * copy target data pages to be relocated;
2660 *
2661 * data extent must start at page boundary and
2662 * multiple of page size (except the last data extent);
2663 * read in each page of the source data extent into cbuf,
2664 * update the cbuf extent descriptor of the page to be
2665 * homeward bound to new dst data extent
2666 * copy the data from the old extent to new extent.
2667 * copy is essential for compressed files to avoid problems
2668 * that can arise if there was a change in compression
2669 * algorithms.
2670 * it is a good strategy because it may disrupt cache
2671 * policy to keep the pages in memory afterwards.
2672 */
2673 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2674 assert((offset & CM_OFFSET) == 0);
2675 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2676 pno = offset >> CM_L2BSIZE;
2677 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2678/*
2679 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2680 (offset >> CM_L2BSIZE) + 1;
2681*/
2682 sxaddr = oxaddr;
2683 dxaddr = nxaddr;
2684
2685 /* process the request one cache buffer at a time */
2686 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2687 offset += nb, pno++, npages--) {
2688 /* compute page size */
2689 nb = min(nbytes - nbrd, CM_BSIZE);
2690
2691 /* get the cache buffer of the page */
2692 if (rc = cmRead(ip, offset, npages, &cp))
2693 break;
2694
2695 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2696 assert(!cp->cm_modified);
2697
2698 /* bind buffer with the new extent address */
2699 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2700 cmSetXD(ip, cp, pno, dxaddr, nblks);
2701
2702 /* release the cbuf, mark it as modified */
2703 cmPut(cp, true);
2704
2705 dxaddr += nblks;
2706 sxaddr += nblks;
2707 }
2708
2709 /* get back parent page */
2710 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2711 return rc;
2712
2713 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2714 jfs_info("xtRelocate: target data extent relocated.");
2715 } else { /* (xtype == XTPAGE) */
2716
2717 /*
2718 * read in the target xtpage from the source extent;
2719 */
2720 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2721 if (rc) {
2722 XT_PUTPAGE(pmp);
2723 return rc;
2724 }
2725
2726 /*
2727 * read in sibling pages if any to update sibling pointers;
2728 */
2729 rmp = NULL;
2730 if (p->header.next) {
2731 nextbn = le64_to_cpu(p->header.next);
2732 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2733 if (rc) {
2734 XT_PUTPAGE(pmp);
2735 XT_PUTPAGE(mp);
2736 return (rc);
2737 }
2738 }
2739
2740 lmp = NULL;
2741 if (p->header.prev) {
2742 prevbn = le64_to_cpu(p->header.prev);
2743 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2744 if (rc) {
2745 XT_PUTPAGE(pmp);
2746 XT_PUTPAGE(mp);
2747 if (rmp)
2748 XT_PUTPAGE(rmp);
2749 return (rc);
2750 }
2751 }
2752
2753 /* at this point, all xtpages to be updated are in memory */
2754
2755 /*
2756 * update sibling pointers of sibling xtpages if any;
2757 */
2758 if (lmp) {
2759 BT_MARK_DIRTY(lmp, ip);
2760 tlck = txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
2761 lp->header.next = cpu_to_le64(nxaddr);
2762 XT_PUTPAGE(lmp);
2763 }
2764
2765 if (rmp) {
2766 BT_MARK_DIRTY(rmp, ip);
2767 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
2768 rp->header.prev = cpu_to_le64(nxaddr);
2769 XT_PUTPAGE(rmp);
2770 }
2771
2772 /*
2773 * update the target xtpage to be relocated
2774 *
2775 * update the self address of the target page
2776 * and write to destination extent;
2777 * redo image covers the whole xtpage since it is new page
2778 * to the destination extent;
2779 * update of bmap for the free of source extent
2780 * of the target xtpage itself:
2781 * update of bmap for the allocation of destination extent
2782 * of the target xtpage itself:
2783 * update of bmap for the extents covered by xad entries in
2784 * the target xtpage is not necessary since they are not
2785 * updated;
2786 * if not committed before this relocation,
2787 * target page may contain XAD_NEW entries which must
2788 * be scanned for bmap update (logredo() always
2789 * scan xtpage REDOPAGE image for bmap update);
2790 * if committed before this relocation (tlckRELOCATE),
2791 * scan may be skipped by commit() and logredo();
2792 */
2793 BT_MARK_DIRTY(mp, ip);
2794 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
2795 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
2796 xtlck = (struct xtlock *) & tlck->lock;
2797
2798 /* update the self address in the xtpage header */
2799 pxd = &p->header.self;
2800 PXDaddress(pxd, nxaddr);
2801
2802 /* linelock for the after image of the whole page */
2803 xtlck->lwm.length =
2804 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
2805
2806 /* update the buffer extent descriptor of target xtpage */
2807 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2808 bmSetXD(mp, nxaddr, xsize);
2809
2810 /* unpin the target page to new homeward bound */
2811 XT_PUTPAGE(mp);
2812 jfs_info("xtRelocate: target xtpage relocated.");
2813 }
2814
2815 /*
2816 * 3. acquire maplock for the source extent to be freed;
2817 *
2818 * acquire a maplock saving the src relocated extent address;
2819 * to free of the extent at commit time;
2820 */
2821 out:
2822 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
2823 * free PXD of the source data extent (logredo() will update
2824 * bmap for free of source data extent), and update bmap for
2825 * free of the source data extent;
2826 */
2827 if (xtype == DATAEXT)
2828 tlck = txMaplock(tid, ip, tlckMAP);
2829 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
2830 * for the source xtpage (logredo() will init NoRedoPage
2831 * filter and will also update bmap for free of the source
2832 * xtpage), and update bmap for free of the source xtpage;
2833 * N.B. We use tlckMAP instead of tlkcXTREE because there
2834 * is no buffer associated with this lock since the buffer
2835 * has been redirected to the target location.
2836 */
2837 else /* (xtype == XTPAGE) */
2838 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
2839
2840 pxdlock = (struct pxd_lock *) & tlck->lock;
2841 pxdlock->flag = mlckFREEPXD;
2842 PXDaddress(&pxdlock->pxd, oxaddr);
2843 PXDlength(&pxdlock->pxd, xlen);
2844 pxdlock->index = 1;
2845
2846 /*
2847 * 4. update the parent xad entry for relocation;
2848 *
2849 * acquire tlck for the parent entry with XAD_NEW as entry
2850 * update which will write LOG_REDOPAGE and update bmap for
2851 * allocation of XAD_NEW destination extent;
2852 */
2853 jfs_info("xtRelocate: update parent xad entry.");
2854 BT_MARK_DIRTY(pmp, ip);
2855 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
2856 xtlck = (struct xtlock *) & tlck->lock;
2857
2858 /* update the XAD with the new destination extent; */
2859 xad = &pp->xad[index];
2860 xad->flag |= XAD_NEW;
2861 XADaddress(xad, nxaddr);
2862
2863 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
2864 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
2865 xtlck->lwm.offset;
2866
2867 /* unpin the parent xtpage */
2868 XT_PUTPAGE(pmp);
2869
2870 return rc;
2871}
2872
2873
2874/*
2875 * xtSearchNode()
2876 *
2877 * function: search for the internal xad entry covering specified extent.
2878 * This function is mainly used by defragfs utility.
2879 *
2880 * parameters:
2881 * ip - file object;
2882 * xad - extent to find;
2883 * cmpp - comparison result:
2884 * btstack - traverse stack;
2885 * flag - search process flag;
2886 *
2887 * returns:
2888 * btstack contains (bn, index) of search path traversed to the entry.
2889 * *cmpp is set to result of comparison with the entry returned.
2890 * the page containing the entry is pinned at exit.
2891 */
2892static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
2893 int *cmpp, struct btstack * btstack, int flag)
2894{
2895 int rc = 0;
2896 s64 xoff, xaddr;
2897 int xlen;
2898 int cmp = 1; /* init for empty page */
2899 s64 bn; /* block number */
2900 struct metapage *mp; /* meta-page buffer */
2901 xtpage_t *p; /* page */
2902 int base, index, lim;
2903 struct btframe *btsp;
2904 s64 t64;
2905
2906 BT_CLR(btstack);
2907
2908 xoff = offsetXAD(xad);
2909 xlen = lengthXAD(xad);
2910 xaddr = addressXAD(xad);
2911
2912 /*
2913 * search down tree from root:
2914 *
2915 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
2916 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
2917 *
2918 * if entry with search key K is not found
2919 * internal page search find the entry with largest key Ki
2920 * less than K which point to the child page to search;
2921 * leaf page search find the entry with smallest key Kj
2922 * greater than K so that the returned index is the position of
2923 * the entry to be shifted right for insertion of new entry.
2924 * for empty tree, search key is greater than any key of the tree.
2925 *
2926 * by convention, root bn = 0.
2927 */
2928 for (bn = 0;;) {
2929 /* get/pin the page to search */
2930 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2931 if (rc)
2932 return rc;
2933 if (p->header.flag & BT_LEAF) {
2934 XT_PUTPAGE(mp);
2935 return -ESTALE;
2936 }
2937
2938 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
2939
2940 /*
2941 * binary search with search key K on the current page
2942 */
2943 for (base = XTENTRYSTART; lim; lim >>= 1) {
2944 index = base + (lim >> 1);
2945
2946 XT_CMP(cmp, xoff, &p->xad[index], t64);
2947 if (cmp == 0) {
2948 /*
2949 * search hit
2950 *
2951 * verify for exact match;
2952 */
2953 if (xaddr == addressXAD(&p->xad[index]) &&
2954 xoff == offsetXAD(&p->xad[index])) {
2955 *cmpp = cmp;
2956
2957 /* save search result */
2958 btsp = btstack->top;
2959 btsp->bn = bn;
2960 btsp->index = index;
2961 btsp->mp = mp;
2962
2963 return 0;
2964 }
2965
2966 /* descend/search its child page */
2967 goto next;
2968 }
2969
2970 if (cmp > 0) {
2971 base = index + 1;
2972 --lim;
2973 }
2974 }
2975
2976 /*
2977 * search miss - non-leaf page:
2978 *
2979 * base is the smallest index with key (Kj) greater than
2980 * search key (K) and may be zero or maxentry index.
2981 * if base is non-zero, decrement base by one to get the parent
2982 * entry of the child page to search.
2983 */
2984 index = base ? base - 1 : base;
2985
2986 /*
2987 * go down to child page
2988 */
2989 next:
2990 /* get the child page block number */
2991 bn = addressXAD(&p->xad[index]);
2992
2993 /* unpin the parent page */
2994 XT_PUTPAGE(mp);
2995 }
2996}
2997
2998
2999/*
3000 * xtRelink()
3001 *
3002 * function:
3003 * link around a freed page.
3004 *
3005 * Parameter:
3006 * int tid,
3007 * struct inode *ip,
3008 * xtpage_t *p)
3009 *
3010 * returns:
3011 */
3012static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3013{
3014 int rc = 0;
3015 struct metapage *mp;
3016 s64 nextbn, prevbn;
3017 struct tlock *tlck;
3018
3019 nextbn = le64_to_cpu(p->header.next);
3020 prevbn = le64_to_cpu(p->header.prev);
3021
3022 /* update prev pointer of the next page */
3023 if (nextbn != 0) {
3024 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3025 if (rc)
3026 return rc;
3027
3028 /*
3029 * acquire a transaction lock on the page;
3030 *
3031 * action: update prev pointer;
3032 */
3033 BT_MARK_DIRTY(mp, ip);
3034 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3035
3036 /* the page may already have been tlock'd */
3037
3038 p->header.prev = cpu_to_le64(prevbn);
3039
3040 XT_PUTPAGE(mp);
3041 }
3042
3043 /* update next pointer of the previous page */
3044 if (prevbn != 0) {
3045 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3046 if (rc)
3047 return rc;
3048
3049 /*
3050 * acquire a transaction lock on the page;
3051 *
3052 * action: update next pointer;
3053 */
3054 BT_MARK_DIRTY(mp, ip);
3055 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3056
3057 /* the page may already have been tlock'd */
3058
3059 p->header.next = le64_to_cpu(nextbn);
3060
3061 XT_PUTPAGE(mp);
3062 }
3063
3064 return 0;
3065}
3066#endif /* _STILL_TO_PORT */
3067
3068
3069/*
3070 * xtInitRoot()
3071 *
3072 * initialize file root (inline in inode)
3073 */
3074void xtInitRoot(tid_t tid, struct inode *ip)
3075{
3076 xtpage_t *p;
3077
3078 /*
3079 * acquire a transaction lock on the root
3080 *
3081 * action:
3082 */
3083 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3084 tlckXTREE | tlckNEW);
3085 p = &JFS_IP(ip)->i_xtroot;
3086
3087 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3088 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3089
3090 if (S_ISDIR(ip->i_mode))
3091 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3092 else {
3093 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3094 ip->i_size = 0;
3095 }
3096
3097
3098 return;
3099}
3100
3101
3102/*
3103 * We can run into a deadlock truncating a file with a large number of
3104 * xtree pages (large fragmented file). A robust fix would entail a
3105 * reservation system where we would reserve a number of metadata pages
3106 * and tlocks which we would be guaranteed without a deadlock. Without
3107 * this, a partial fix is to limit number of metadata pages we will lock
3108 * in a single transaction. Currently we will truncate the file so that
3109 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3110 * will be responsible for ensuring that the current transaction gets
3111 * committed, and that subsequent transactions are created to truncate
3112 * the file further if needed.
3113 */
3114#define MAX_TRUNCATE_LEAVES 50
3115
3116/*
3117 * xtTruncate()
3118 *
3119 * function:
3120 * traverse for truncation logging backward bottom up;
3121 * terminate at the last extent entry at the current subtree
3122 * root page covering new down size.
3123 * truncation may occur within the last extent entry.
3124 *
3125 * parameter:
3126 * int tid,
3127 * struct inode *ip,
3128 * s64 newsize,
3129 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3130 *
3131 * return:
3132 *
3133 * note:
3134 * PWMAP:
3135 * 1. truncate (non-COMMIT_NOLINK file)
3136 * by jfs_truncate() or jfs_open(O_TRUNC):
3137 * xtree is updated;
3138 * 2. truncate index table of directory when last entry removed
3139 * map update via tlock at commit time;
3140 * PMAP:
3141 * Call xtTruncate_pmap instead
3142 * WMAP:
3143 * 1. remove (free zero link count) on last reference release
3144 * (pmap has been freed at commit zero link count);
3145 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3146 * xtree is updated;
3147 * map update directly at truncation time;
3148 *
3149 * if (DELETE)
3150 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3151 * else if (TRUNCATE)
3152 * must write LOG_NOREDOPAGE for deleted index page;
3153 *
3154 * pages may already have been tlocked by anonymous transactions
3155 * during file growth (i.e., write) before truncation;
3156 *
3157 * except last truncated entry, deleted entries remains as is
3158 * in the page (nextindex is updated) for other use
3159 * (e.g., log/update allocation map): this avoid copying the page
3160 * info but delay free of pages;
3161 *
3162 */
3163s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3164{
3165 int rc = 0;
3166 s64 teof;
3167 struct metapage *mp;
3168 xtpage_t *p;
3169 s64 bn;
3170 int index, nextindex;
3171 xad_t *xad;
3172 s64 xoff, xaddr;
3173 int xlen, len, freexlen;
3174 struct btstack btstack;
3175 struct btframe *parent;
3176 struct tblock *tblk = NULL;
3177 struct tlock *tlck = NULL;
3178 struct xtlock *xtlck = NULL;
3179 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3180 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3181 s64 nfreed;
3182 int freed, log;
3183 int locked_leaves = 0;
3184
3185 /* save object truncation type */
3186 if (tid) {
3187 tblk = tid_to_tblock(tid);
3188 tblk->xflag |= flag;
3189 }
3190
3191 nfreed = 0;
3192
3193 flag &= COMMIT_MAP;
3194 assert(flag != COMMIT_PMAP);
3195
3196 if (flag == COMMIT_PWMAP)
3197 log = 1;
3198 else {
3199 log = 0;
3200 xadlock.flag = mlckFREEXADLIST;
3201 xadlock.index = 1;
3202 }
3203
3204 /*
3205 * if the newsize is not an integral number of pages,
3206 * the file between newsize and next page boundary will
3207 * be cleared.
3208 * if truncating into a file hole, it will cause
3209 * a full block to be allocated for the logical block.
3210 */
3211
3212 /*
3213 * release page blocks of truncated region <teof, eof>
3214 *
3215 * free the data blocks from the leaf index blocks.
3216 * delete the parent index entries corresponding to
3217 * the freed child data/index blocks.
3218 * free the index blocks themselves which aren't needed
3219 * in new sized file.
3220 *
3221 * index blocks are updated only if the blocks are to be
3222 * retained in the new sized file.
3223 * if type is PMAP, the data and index pages are NOT
3224 * freed, and the data and index blocks are NOT freed
3225 * from working map.
3226 * (this will allow continued access of data/index of
3227 * temporary file (zerolink count file truncated to zero-length)).
3228 */
3229 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3230 JFS_SBI(ip->i_sb)->l2bsize;
3231
3232 /* clear stack */
3233 BT_CLR(&btstack);
3234
3235 /*
3236 * start with root
3237 *
3238 * root resides in the inode
3239 */
3240 bn = 0;
3241
3242 /*
3243 * first access of each page:
3244 */
3245 getPage:
3246 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3247 if (rc)
3248 return rc;
3249
3250 /* process entries backward from last index */
3251 index = le16_to_cpu(p->header.nextindex) - 1;
3252
3253
3254 /* Since this is the rightmost page at this level, and we may have
3255 * already freed a page that was formerly to the right, let's make
3256 * sure that the next pointer is zero.
3257 */
3258 if (p->header.next) {
3259 if (log)
3260 /*
3261 * Make sure this change to the header is logged.
3262 * If we really truncate this leaf, the flag
3263 * will be changed to tlckTRUNCATE
3264 */
3265 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3266 BT_MARK_DIRTY(mp, ip);
3267 p->header.next = 0;
3268 }
3269
3270 if (p->header.flag & BT_INTERNAL)
3271 goto getChild;
3272
3273 /*
3274 * leaf page
3275 */
3276 freed = 0;
3277
3278 /* does region covered by leaf page precede Teof ? */
3279 xad = &p->xad[index];
3280 xoff = offsetXAD(xad);
3281 xlen = lengthXAD(xad);
3282 if (teof >= xoff + xlen) {
3283 XT_PUTPAGE(mp);
3284 goto getParent;
3285 }
3286
3287 /* (re)acquire tlock of the leaf page */
3288 if (log) {
3289 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3290 /*
3291 * We need to limit the size of the transaction
3292 * to avoid exhausting pagecache & tlocks
3293 */
3294 XT_PUTPAGE(mp);
3295 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3296 goto getParent;
3297 }
3298 tlck = txLock(tid, ip, mp, tlckXTREE);
3299 tlck->type = tlckXTREE | tlckTRUNCATE;
3300 xtlck = (struct xtlock *) & tlck->lock;
3301 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3302 }
3303 BT_MARK_DIRTY(mp, ip);
3304
3305 /*
3306 * scan backward leaf page entries
3307 */
3308 for (; index >= XTENTRYSTART; index--) {
3309 xad = &p->xad[index];
3310 xoff = offsetXAD(xad);
3311 xlen = lengthXAD(xad);
3312 xaddr = addressXAD(xad);
3313
3314 /*
3315 * The "data" for a directory is indexed by the block
3316 * device's address space. This metadata must be invalidated
3317 * here
3318 */
3319 if (S_ISDIR(ip->i_mode) && (teof == 0))
3320 invalidate_xad_metapages(ip, *xad);
3321 /*
3322 * entry beyond eof: continue scan of current page
3323 * xad
3324 * ---|---=======------->
3325 * eof
3326 */
3327 if (teof < xoff) {
3328 nfreed += xlen;
3329 continue;
3330 }
3331
3332 /*
3333 * (xoff <= teof): last entry to be deleted from page;
3334 * If other entries remain in page: keep and update the page.
3335 */
3336
3337 /*
3338 * eof == entry_start: delete the entry
3339 * xad
3340 * -------|=======------->
3341 * eof
3342 *
3343 */
3344 if (teof == xoff) {
3345 nfreed += xlen;
3346
3347 if (index == XTENTRYSTART)
3348 break;
3349
3350 nextindex = index;
3351 }
3352 /*
3353 * eof within the entry: truncate the entry.
3354 * xad
3355 * -------===|===------->
3356 * eof
3357 */
3358 else if (teof < xoff + xlen) {
3359 /* update truncated entry */
3360 len = teof - xoff;
3361 freexlen = xlen - len;
3362 XADlength(xad, len);
3363
3364 /* save pxd of truncated extent in tlck */
3365 xaddr += len;
3366 if (log) { /* COMMIT_PWMAP */
3367 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3368 min(index, (int)xtlck->lwm.offset) : index;
3369 xtlck->lwm.length = index + 1 -
3370 xtlck->lwm.offset;
3371 xtlck->twm.offset = index;
3372 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3373 pxdlock->flag = mlckFREEPXD;
3374 PXDaddress(&pxdlock->pxd, xaddr);
3375 PXDlength(&pxdlock->pxd, freexlen);
3376 }
3377 /* free truncated extent */
3378 else { /* COMMIT_WMAP */
3379
3380 pxdlock = (struct pxd_lock *) & xadlock;
3381 pxdlock->flag = mlckFREEPXD;
3382 PXDaddress(&pxdlock->pxd, xaddr);
3383 PXDlength(&pxdlock->pxd, freexlen);
3384 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3385
3386 /* reset map lock */
3387 xadlock.flag = mlckFREEXADLIST;
3388 }
3389
3390 /* current entry is new last entry; */
3391 nextindex = index + 1;
3392
3393 nfreed += freexlen;
3394 }
3395 /*
3396 * eof beyond the entry:
3397 * xad
3398 * -------=======---|--->
3399 * eof
3400 */
3401 else { /* (xoff + xlen < teof) */
3402
3403 nextindex = index + 1;
3404 }
3405
3406 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3407 if (!log) { /* COMMIT_WAMP */
3408 xadlock.xdlist = &p->xad[nextindex];
3409 xadlock.count =
3410 le16_to_cpu(p->header.nextindex) -
3411 nextindex;
3412 txFreeMap(ip, (struct maplock *) & xadlock,
3413 NULL, COMMIT_WMAP);
3414 }
3415 p->header.nextindex = cpu_to_le16(nextindex);
3416 }
3417
3418 XT_PUTPAGE(mp);
3419
3420 /* assert(freed == 0); */
3421 goto getParent;
3422 } /* end scan of leaf page entries */
3423
3424 freed = 1;
3425
3426 /*
3427 * leaf page become empty: free the page if type != PMAP
3428 */
3429 if (log) { /* COMMIT_PWMAP */
3430 /* txCommit() with tlckFREE:
3431 * free data extents covered by leaf [XTENTRYSTART:hwm);
3432 * invalidate leaf if COMMIT_PWMAP;
3433 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3434 */
3435 tlck->type = tlckXTREE | tlckFREE;
3436 } else { /* COMMIT_WAMP */
3437
3438 /* free data extents covered by leaf */
3439 xadlock.xdlist = &p->xad[XTENTRYSTART];
3440 xadlock.count =
3441 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3442 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3443 }
3444
3445 if (p->header.flag & BT_ROOT) {
3446 p->header.flag &= ~BT_INTERNAL;
3447 p->header.flag |= BT_LEAF;
3448 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3449
3450 XT_PUTPAGE(mp); /* debug */
3451 goto out;
3452 } else {
3453 if (log) { /* COMMIT_PWMAP */
3454 /* page will be invalidated at tx completion
3455 */
3456 XT_PUTPAGE(mp);
3457 } else { /* COMMIT_WMAP */
3458
3459 if (mp->lid)
3460 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3461
3462 /* invalidate empty leaf page */
3463 discard_metapage(mp);
3464 }
3465 }
3466
3467 /*
3468 * the leaf page become empty: delete the parent entry
3469 * for the leaf page if the parent page is to be kept
3470 * in the new sized file.
3471 */
3472
3473 /*
3474 * go back up to the parent page
3475 */
3476 getParent:
3477 /* pop/restore parent entry for the current child page */
3478 if ((parent = BT_POP(&btstack)) == NULL)
3479 /* current page must have been root */
3480 goto out;
3481
3482 /* get back the parent page */
3483 bn = parent->bn;
3484 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3485 if (rc)
3486 return rc;
3487
3488 index = parent->index;
3489
3490 /*
3491 * child page was not empty:
3492 */
3493 if (freed == 0) {
3494 /* has any entry deleted from parent ? */
3495 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3496 /* (re)acquire tlock on the parent page */
3497 if (log) { /* COMMIT_PWMAP */
3498 /* txCommit() with tlckTRUNCATE:
3499 * free child extents covered by parent [);
3500 */
3501 tlck = txLock(tid, ip, mp, tlckXTREE);
3502 xtlck = (struct xtlock *) & tlck->lock;
3503 if (!(tlck->type & tlckTRUNCATE)) {
3504 xtlck->hwm.offset =
3505 le16_to_cpu(p->header.
3506 nextindex) - 1;
3507 tlck->type =
3508 tlckXTREE | tlckTRUNCATE;
3509 }
3510 } else { /* COMMIT_WMAP */
3511
3512 /* free child extents covered by parent */
3513 xadlock.xdlist = &p->xad[index + 1];
3514 xadlock.count =
3515 le16_to_cpu(p->header.nextindex) -
3516 index - 1;
3517 txFreeMap(ip, (struct maplock *) & xadlock,
3518 NULL, COMMIT_WMAP);
3519 }
3520 BT_MARK_DIRTY(mp, ip);
3521
3522 p->header.nextindex = cpu_to_le16(index + 1);
3523 }
3524 XT_PUTPAGE(mp);
3525 goto getParent;
3526 }
3527
3528 /*
3529 * child page was empty:
3530 */
3531 nfreed += lengthXAD(&p->xad[index]);
3532
3533 /*
3534 * During working map update, child page's tlock must be handled
3535 * before parent's. This is because the parent's tlock will cause
3536 * the child's disk space to be marked available in the wmap, so
3537 * it's important that the child page be released by that time.
3538 *
3539 * ToDo: tlocks should be on doubly-linked list, so we can
3540 * quickly remove it and add it to the end.
3541 */
3542
3543 /*
3544 * Move parent page's tlock to the end of the tid's tlock list
3545 */
3546 if (log && mp->lid && (tblk->last != mp->lid) &&
3547 lid_to_tlock(mp->lid)->tid) {
3548 lid_t lid = mp->lid;
3549 struct tlock *prev;
3550
3551 tlck = lid_to_tlock(lid);
3552
3553 if (tblk->next == lid)
3554 tblk->next = tlck->next;
3555 else {
3556 for (prev = lid_to_tlock(tblk->next);
3557 prev->next != lid;
3558 prev = lid_to_tlock(prev->next)) {
3559 assert(prev->next);
3560 }
3561 prev->next = tlck->next;
3562 }
3563 lid_to_tlock(tblk->last)->next = lid;
3564 tlck->next = 0;
3565 tblk->last = lid;
3566 }
3567
3568 /*
3569 * parent page become empty: free the page
3570 */
3571 if (index == XTENTRYSTART) {
3572 if (log) { /* COMMIT_PWMAP */
3573 /* txCommit() with tlckFREE:
3574 * free child extents covered by parent;
3575 * invalidate parent if COMMIT_PWMAP;
3576 */
3577 tlck = txLock(tid, ip, mp, tlckXTREE);
3578 xtlck = (struct xtlock *) & tlck->lock;
3579 xtlck->hwm.offset =
3580 le16_to_cpu(p->header.nextindex) - 1;
3581 tlck->type = tlckXTREE | tlckFREE;
3582 } else { /* COMMIT_WMAP */
3583
3584 /* free child extents covered by parent */
3585 xadlock.xdlist = &p->xad[XTENTRYSTART];
3586 xadlock.count =
3587 le16_to_cpu(p->header.nextindex) -
3588 XTENTRYSTART;
3589 txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3590 COMMIT_WMAP);
3591 }
3592 BT_MARK_DIRTY(mp, ip);
3593
3594 if (p->header.flag & BT_ROOT) {
3595 p->header.flag &= ~BT_INTERNAL;
3596 p->header.flag |= BT_LEAF;
3597 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3598 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3599 /*
3600 * Shrink root down to allow inline
3601 * EA (otherwise fsck complains)
3602 */
3603 p->header.maxentry =
3604 cpu_to_le16(XTROOTINITSLOT);
3605 JFS_IP(ip)->mode2 |= INLINEEA;
3606 }
3607
3608 XT_PUTPAGE(mp); /* debug */
3609 goto out;
3610 } else {
3611 if (log) { /* COMMIT_PWMAP */
3612 /* page will be invalidated at tx completion
3613 */
3614 XT_PUTPAGE(mp);
3615 } else { /* COMMIT_WMAP */
3616
3617 if (mp->lid)
3618 lid_to_tlock(mp->lid)->flag |=
3619 tlckFREELOCK;
3620
3621 /* invalidate parent page */
3622 discard_metapage(mp);
3623 }
3624
3625 /* parent has become empty and freed:
3626 * go back up to its parent page
3627 */
3628 /* freed = 1; */
3629 goto getParent;
3630 }
3631 }
3632 /*
3633 * parent page still has entries for front region;
3634 */
3635 else {
3636 /* try truncate region covered by preceding entry
3637 * (process backward)
3638 */
3639 index--;
3640
3641 /* go back down to the child page corresponding
3642 * to the entry
3643 */
3644 goto getChild;
3645 }
3646
3647 /*
3648 * internal page: go down to child page of current entry
3649 */
3650 getChild:
3651 /* save current parent entry for the child page */
3652 if (BT_STACK_FULL(&btstack)) {
3653 jfs_error(ip->i_sb, "stack overrun in xtTruncate!");
3654 XT_PUTPAGE(mp);
3655 return -EIO;
3656 }
3657 BT_PUSH(&btstack, bn, index);
3658
3659 /* get child page */
3660 xad = &p->xad[index];
3661 bn = addressXAD(xad);
3662
3663 /*
3664 * first access of each internal entry:
3665 */
3666 /* release parent page */
3667 XT_PUTPAGE(mp);
3668
3669 /* process the child page */
3670 goto getPage;
3671
3672 out:
3673 /*
3674 * update file resource stat
3675 */
3676 /* set size
3677 */
3678 if (S_ISDIR(ip->i_mode) && !newsize)
3679 ip->i_size = 1; /* fsck hates zero-length directories */
3680 else
3681 ip->i_size = newsize;
3682
3683 /* update quota allocation to reflect freed blocks */
3684 dquot_free_block(ip, nfreed);
3685
3686 /*
3687 * free tlock of invalidated pages
3688 */
3689 if (flag == COMMIT_WMAP)
3690 txFreelock(ip);
3691
3692 return newsize;
3693}
3694
3695
3696/*
3697 * xtTruncate_pmap()
3698 *
3699 * function:
3700 * Perform truncate to zero length for deleted file, leaving the
3701 * the xtree and working map untouched. This allows the file to
3702 * be accessed via open file handles, while the delete of the file
3703 * is committed to disk.
3704 *
3705 * parameter:
3706 * tid_t tid,
3707 * struct inode *ip,
3708 * s64 committed_size)
3709 *
3710 * return: new committed size
3711 *
3712 * note:
3713 *
3714 * To avoid deadlock by holding too many transaction locks, the
3715 * truncation may be broken up into multiple transactions.
3716 * The committed_size keeps track of part of the file has been
3717 * freed from the pmaps.
3718 */
3719s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3720{
3721 s64 bn;
3722 struct btstack btstack;
3723 int cmp;
3724 int index;
3725 int locked_leaves = 0;
3726 struct metapage *mp;
3727 xtpage_t *p;
3728 struct btframe *parent;
3729 int rc;
3730 struct tblock *tblk;
3731 struct tlock *tlck = NULL;
3732 xad_t *xad;
3733 int xlen;
3734 s64 xoff;
3735 struct xtlock *xtlck = NULL;
3736
3737 /* save object truncation type */
3738 tblk = tid_to_tblock(tid);
3739 tblk->xflag |= COMMIT_PMAP;
3740
3741 /* clear stack */
3742 BT_CLR(&btstack);
3743
3744 if (committed_size) {
3745 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3746 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
3747 if (rc)
3748 return rc;
3749
3750 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3751
3752 if (cmp != 0) {
3753 XT_PUTPAGE(mp);
3754 jfs_error(ip->i_sb,
3755 "xtTruncate_pmap: did not find extent");
3756 return -EIO;
3757 }
3758 } else {
3759 /*
3760 * start with root
3761 *
3762 * root resides in the inode
3763 */
3764 bn = 0;
3765
3766 /*
3767 * first access of each page:
3768 */
3769 getPage:
3770 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3771 if (rc)
3772 return rc;
3773
3774 /* process entries backward from last index */
3775 index = le16_to_cpu(p->header.nextindex) - 1;
3776
3777 if (p->header.flag & BT_INTERNAL)
3778 goto getChild;
3779 }
3780
3781 /*
3782 * leaf page
3783 */
3784
3785 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3786 /*
3787 * We need to limit the size of the transaction
3788 * to avoid exhausting pagecache & tlocks
3789 */
3790 xad = &p->xad[index];
3791 xoff = offsetXAD(xad);
3792 xlen = lengthXAD(xad);
3793 XT_PUTPAGE(mp);
3794 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3795 }
3796 tlck = txLock(tid, ip, mp, tlckXTREE);
3797 tlck->type = tlckXTREE | tlckFREE;
3798 xtlck = (struct xtlock *) & tlck->lock;
3799 xtlck->hwm.offset = index;
3800
3801
3802 XT_PUTPAGE(mp);
3803
3804 /*
3805 * go back up to the parent page
3806 */
3807 getParent:
3808 /* pop/restore parent entry for the current child page */
3809 if ((parent = BT_POP(&btstack)) == NULL)
3810 /* current page must have been root */
3811 goto out;
3812
3813 /* get back the parent page */
3814 bn = parent->bn;
3815 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3816 if (rc)
3817 return rc;
3818
3819 index = parent->index;
3820
3821 /*
3822 * parent page become empty: free the page
3823 */
3824 if (index == XTENTRYSTART) {
3825 /* txCommit() with tlckFREE:
3826 * free child extents covered by parent;
3827 * invalidate parent if COMMIT_PWMAP;
3828 */
3829 tlck = txLock(tid, ip, mp, tlckXTREE);
3830 xtlck = (struct xtlock *) & tlck->lock;
3831 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3832 tlck->type = tlckXTREE | tlckFREE;
3833
3834 XT_PUTPAGE(mp);
3835
3836 if (p->header.flag & BT_ROOT) {
3837
3838 goto out;
3839 } else {
3840 goto getParent;
3841 }
3842 }
3843 /*
3844 * parent page still has entries for front region;
3845 */
3846 else
3847 index--;
3848 /*
3849 * internal page: go down to child page of current entry
3850 */
3851 getChild:
3852 /* save current parent entry for the child page */
3853 if (BT_STACK_FULL(&btstack)) {
3854 jfs_error(ip->i_sb, "stack overrun in xtTruncate_pmap!");
3855 XT_PUTPAGE(mp);
3856 return -EIO;
3857 }
3858 BT_PUSH(&btstack, bn, index);
3859
3860 /* get child page */
3861 xad = &p->xad[index];
3862 bn = addressXAD(xad);
3863
3864 /*
3865 * first access of each internal entry:
3866 */
3867 /* release parent page */
3868 XT_PUTPAGE(mp);
3869
3870 /* process the child page */
3871 goto getPage;
3872
3873 out:
3874
3875 return 0;
3876}
3877
3878#ifdef CONFIG_JFS_STATISTICS
3879static int jfs_xtstat_proc_show(struct seq_file *m, void *v)
3880{
3881 seq_printf(m,
3882 "JFS Xtree statistics\n"
3883 "====================\n"
3884 "searches = %d\n"
3885 "fast searches = %d\n"
3886 "splits = %d\n",
3887 xtStat.search,
3888 xtStat.fastSearch,
3889 xtStat.split);
3890 return 0;
3891}
3892
3893static int jfs_xtstat_proc_open(struct inode *inode, struct file *file)
3894{
3895 return single_open(file, jfs_xtstat_proc_show, NULL);
3896}
3897
3898const struct file_operations jfs_xtstat_proc_fops = {
3899 .owner = THIS_MODULE,
3900 .open = jfs_xtstat_proc_open,
3901 .read = seq_read,
3902 .llseek = seq_lseek,
3903 .release = single_release,
3904};
3905#endif