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