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