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