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