xref: /openbmc/linux/fs/jfs/jfs_xtree.c (revision d5cb9783536a41df9f9cba5b0a1d78047ed787f7)
1 /*
2  *   Copyright (C) International Business Machines Corp., 2000-2005
3  *
4  *   This program is free software;  you can redistribute it and/or modify
5  *   it under the terms of the GNU General Public License as published by
6  *   the Free Software Foundation; either version 2 of the License, or
7  *   (at your option) any later version.
8  *
9  *   This program is distributed in the hope that it will be useful,
10  *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
12  *   the GNU General Public License for more details.
13  *
14  *   You should have received a copy of the GNU General Public License
15  *   along with this program;  if not, write to the Free Software
16  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  */
18 /*
19  *      jfs_xtree.c: extent allocation descriptor B+-tree manager
20  */
21 
22 #include <linux/fs.h>
23 #include <linux/quotaops.h>
24 #include "jfs_incore.h"
25 #include "jfs_filsys.h"
26 #include "jfs_metapage.h"
27 #include "jfs_dmap.h"
28 #include "jfs_dinode.h"
29 #include "jfs_superblock.h"
30 #include "jfs_debug.h"
31 
32 /*
33  * xtree local flag
34  */
35 #define XT_INSERT       0x00000001
36 
37 /*
38  *       xtree key/entry comparison: extent offset
39  *
40  * return:
41  *      -1: k < start of extent
42  *       0: start_of_extent <= k <= end_of_extent
43  *       1: k > end_of_extent
44  */
45 #define XT_CMP(CMP, K, X, OFFSET64)\
46 {\
47         OFFSET64 = offsetXAD(X);\
48         (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
49               ((K) < OFFSET64) ? -1 : 0;\
50 }
51 
52 /* write a xad entry */
53 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
54 {\
55         (XAD)->flag = (FLAG);\
56         XADoffset((XAD), (OFF));\
57         XADlength((XAD), (LEN));\
58         XADaddress((XAD), (ADDR));\
59 }
60 
61 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
62 
63 /* get page buffer for specified block address */
64 /* ToDo: Replace this ugly macro with a function */
65 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
66 {\
67 	BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
68 	if (!(RC))\
69 	{\
70 		if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
71 		    (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
72 		    (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
73 		{\
74 			jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
75 			BT_PUTPAGE(MP);\
76 			MP = NULL;\
77 			RC = -EIO;\
78 		}\
79         }\
80 }
81 
82 /* for consistency */
83 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
84 
85 #define XT_GETSEARCH(IP, LEAF, BN, MP,  P, INDEX) \
86 	BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
87 /* xtree entry parameter descriptor */
88 struct xtsplit {
89 	struct metapage *mp;
90 	s16 index;
91 	u8 flag;
92 	s64 off;
93 	s64 addr;
94 	int len;
95 	struct pxdlist *pxdlist;
96 };
97 
98 
99 /*
100  *      statistics
101  */
102 #ifdef CONFIG_JFS_STATISTICS
103 static struct {
104 	uint search;
105 	uint fastSearch;
106 	uint split;
107 } xtStat;
108 #endif
109 
110 
111 /*
112  * forward references
113  */
114 static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
115 		    struct btstack * btstack, int flag);
116 
117 static int xtSplitUp(tid_t tid,
118 		     struct inode *ip,
119 		     struct xtsplit * split, struct btstack * btstack);
120 
121 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
122 		       struct metapage ** rmpp, s64 * rbnp);
123 
124 static int xtSplitRoot(tid_t tid, struct inode *ip,
125 		       struct xtsplit * split, struct metapage ** rmpp);
126 
127 #ifdef _STILL_TO_PORT
128 static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
129 		      xtpage_t * fp, struct btstack * btstack);
130 
131 static int xtSearchNode(struct inode *ip,
132 			xad_t * xad,
133 			int *cmpp, struct btstack * btstack, int flag);
134 
135 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
136 #endif				/*  _STILL_TO_PORT */
137 
138 /*
139  *      xtLookup()
140  *
141  * function: map a single page into a physical extent;
142  */
143 int xtLookup(struct inode *ip, s64 lstart,
144 	     s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
145 {
146 	int rc = 0;
147 	struct btstack btstack;
148 	int cmp;
149 	s64 bn;
150 	struct metapage *mp;
151 	xtpage_t *p;
152 	int index;
153 	xad_t *xad;
154 	s64 next, size, xoff, xend;
155 	int xlen;
156 	s64 xaddr;
157 
158 	*paddr = 0;
159 	*plen = llen;
160 
161 	if (!no_check) {
162 		/* is lookup offset beyond eof ? */
163 		size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
164 		    JFS_SBI(ip->i_sb)->l2bsize;
165 		if (lstart >= size) {
166 			jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
167 				(ulong) lstart, (ulong) size);
168 			return 0;
169 		}
170 	}
171 
172 	/*
173 	 * search for the xad entry covering the logical extent
174 	 */
175 //search:
176 	if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
177 		jfs_err("xtLookup: xtSearch returned %d", rc);
178 		return rc;
179 	}
180 
181 	/*
182 	 *      compute the physical extent covering logical extent
183 	 *
184 	 * N.B. search may have failed (e.g., hole in sparse file),
185 	 * and returned the index of the next entry.
186 	 */
187 	/* retrieve search result */
188 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
189 
190 	/* is xad found covering start of logical extent ?
191 	 * lstart is a page start address,
192 	 * i.e., lstart cannot start in a hole;
193 	 */
194 	if (cmp) {
195 		if (next)
196 			*plen = min(next - lstart, llen);
197 		goto out;
198 	}
199 
200 	/*
201 	 * lxd covered by xad
202 	 */
203 	xad = &p->xad[index];
204 	xoff = offsetXAD(xad);
205 	xlen = lengthXAD(xad);
206 	xend = xoff + xlen;
207 	xaddr = addressXAD(xad);
208 
209 	/* initialize new pxd */
210 	*pflag = xad->flag;
211 	*paddr = xaddr + (lstart - xoff);
212 	/* a page must be fully covered by an xad */
213 	*plen = min(xend - lstart, llen);
214 
215       out:
216 	XT_PUTPAGE(mp);
217 
218 	return rc;
219 }
220 
221 
222 /*
223  *      xtLookupList()
224  *
225  * function: map a single logical extent into a list of physical extent;
226  *
227  * parameter:
228  *      struct inode    *ip,
229  *      struct lxdlist  *lxdlist,       lxd list (in)
230  *      struct xadlist  *xadlist,       xad list (in/out)
231  *      int		flag)
232  *
233  * coverage of lxd by xad under assumption of
234  * . lxd's are ordered and disjoint.
235  * . xad's are ordered and disjoint.
236  *
237  * return:
238  *      0:      success
239  *
240  * note: a page being written (even a single byte) is backed fully,
241  *      except the last page which is only backed with blocks
242  *      required to cover the last byte;
243  *      the extent backing a page is fully contained within an xad;
244  */
245 int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
246 		 struct xadlist * xadlist, int flag)
247 {
248 	int rc = 0;
249 	struct btstack btstack;
250 	int cmp;
251 	s64 bn;
252 	struct metapage *mp;
253 	xtpage_t *p;
254 	int index;
255 	lxd_t *lxd;
256 	xad_t *xad, *pxd;
257 	s64 size, lstart, lend, xstart, xend, pstart;
258 	s64 llen, xlen, plen;
259 	s64 xaddr, paddr;
260 	int nlxd, npxd, maxnpxd;
261 
262 	npxd = xadlist->nxad = 0;
263 	maxnpxd = xadlist->maxnxad;
264 	pxd = xadlist->xad;
265 
266 	nlxd = lxdlist->nlxd;
267 	lxd = lxdlist->lxd;
268 
269 	lstart = offsetLXD(lxd);
270 	llen = lengthLXD(lxd);
271 	lend = lstart + llen;
272 
273 	size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
274 	    JFS_SBI(ip->i_sb)->l2bsize;
275 
276 	/*
277 	 * search for the xad entry covering the logical extent
278 	 */
279       search:
280 	if (lstart >= size)
281 		return 0;
282 
283 	if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
284 		return rc;
285 
286 	/*
287 	 *      compute the physical extent covering logical extent
288 	 *
289 	 * N.B. search may have failed (e.g., hole in sparse file),
290 	 * and returned the index of the next entry.
291 	 */
292 //map:
293 	/* retrieve search result */
294 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
295 
296 	/* is xad on the next sibling page ? */
297 	if (index == le16_to_cpu(p->header.nextindex)) {
298 		if (p->header.flag & BT_ROOT)
299 			goto mapend;
300 
301 		if ((bn = le64_to_cpu(p->header.next)) == 0)
302 			goto mapend;
303 
304 		XT_PUTPAGE(mp);
305 
306 		/* get next sibling page */
307 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
308 		if (rc)
309 			return rc;
310 
311 		index = XTENTRYSTART;
312 	}
313 
314 	xad = &p->xad[index];
315 
316 	/*
317 	 * is lxd covered by xad ?
318 	 */
319       compare:
320 	xstart = offsetXAD(xad);
321 	xlen = lengthXAD(xad);
322 	xend = xstart + xlen;
323 	xaddr = addressXAD(xad);
324 
325       compare1:
326 	if (xstart < lstart)
327 		goto compare2;
328 
329 	/* (lstart <= xstart) */
330 
331 	/* lxd is NOT covered by xad */
332 	if (lend <= xstart) {
333 		/*
334 		 * get next lxd
335 		 */
336 		if (--nlxd == 0)
337 			goto mapend;
338 		lxd++;
339 
340 		lstart = offsetLXD(lxd);
341 		llen = lengthLXD(lxd);
342 		lend = lstart + llen;
343 		if (lstart >= size)
344 			goto mapend;
345 
346 		/* compare with the current xad  */
347 		goto compare1;
348 	}
349 	/* lxd is covered by xad */
350 	else {			/* (xstart < lend) */
351 
352 		/* initialize new pxd */
353 		pstart = xstart;
354 		plen = min(lend - xstart, xlen);
355 		paddr = xaddr;
356 
357 		goto cover;
358 	}
359 
360 	/* (xstart < lstart) */
361       compare2:
362 	/* lxd is covered by xad */
363 	if (lstart < xend) {
364 		/* initialize new pxd */
365 		pstart = lstart;
366 		plen = min(xend - lstart, llen);
367 		paddr = xaddr + (lstart - xstart);
368 
369 		goto cover;
370 	}
371 	/* lxd is NOT covered by xad */
372 	else {			/* (xend <= lstart) */
373 
374 		/*
375 		 * get next xad
376 		 *
377 		 * linear search next xad covering lxd on
378 		 * the current xad page, and then tree search
379 		 */
380 		if (index == le16_to_cpu(p->header.nextindex) - 1) {
381 			if (p->header.flag & BT_ROOT)
382 				goto mapend;
383 
384 			XT_PUTPAGE(mp);
385 			goto search;
386 		} else {
387 			index++;
388 			xad++;
389 
390 			/* compare with new xad */
391 			goto compare;
392 		}
393 	}
394 
395 	/*
396 	 * lxd is covered by xad and a new pxd has been initialized
397 	 * (lstart <= xstart < lend) or (xstart < lstart < xend)
398 	 */
399       cover:
400 	/* finalize pxd corresponding to current xad */
401 	XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
402 
403 	if (++npxd >= maxnpxd)
404 		goto mapend;
405 	pxd++;
406 
407 	/*
408 	 * lxd is fully covered by xad
409 	 */
410 	if (lend <= xend) {
411 		/*
412 		 * get next lxd
413 		 */
414 		if (--nlxd == 0)
415 			goto mapend;
416 		lxd++;
417 
418 		lstart = offsetLXD(lxd);
419 		llen = lengthLXD(lxd);
420 		lend = lstart + llen;
421 		if (lstart >= size)
422 			goto mapend;
423 
424 		/*
425 		 * test for old xad covering new lxd
426 		 * (old xstart < new lstart)
427 		 */
428 		goto compare2;
429 	}
430 	/*
431 	 * lxd is partially covered by xad
432 	 */
433 	else {			/* (xend < lend)  */
434 
435 		/*
436 		 * get next xad
437 		 *
438 		 * linear search next xad covering lxd on
439 		 * the current xad page, and then next xad page search
440 		 */
441 		if (index == le16_to_cpu(p->header.nextindex) - 1) {
442 			if (p->header.flag & BT_ROOT)
443 				goto mapend;
444 
445 			if ((bn = le64_to_cpu(p->header.next)) == 0)
446 				goto mapend;
447 
448 			XT_PUTPAGE(mp);
449 
450 			/* get next sibling page */
451 			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
452 			if (rc)
453 				return rc;
454 
455 			index = XTENTRYSTART;
456 			xad = &p->xad[index];
457 		} else {
458 			index++;
459 			xad++;
460 		}
461 
462 		/*
463 		 * test for new xad covering old lxd
464 		 * (old lstart < new xstart)
465 		 */
466 		goto compare;
467 	}
468 
469       mapend:
470 	xadlist->nxad = npxd;
471 
472 //out:
473 	XT_PUTPAGE(mp);
474 
475 	return rc;
476 }
477 
478 
479 /*
480  *      xtSearch()
481  *
482  * function:    search for the xad entry covering specified offset.
483  *
484  * parameters:
485  *      ip      - file object;
486  *      xoff    - extent offset;
487  *      nextp	- address of next extent (if any) for search miss
488  *      cmpp    - comparison result:
489  *      btstack - traverse stack;
490  *      flag    - search process flag (XT_INSERT);
491  *
492  * returns:
493  *      btstack contains (bn, index) of search path traversed to the entry.
494  *      *cmpp is set to result of comparison with the entry returned.
495  *      the page containing the entry is pinned at exit.
496  */
497 static int xtSearch(struct inode *ip, s64 xoff,	s64 *nextp,
498 		    int *cmpp, struct btstack * btstack, int flag)
499 {
500 	struct jfs_inode_info *jfs_ip = JFS_IP(ip);
501 	int rc = 0;
502 	int cmp = 1;		/* init for empty page */
503 	s64 bn;			/* block number */
504 	struct metapage *mp;	/* page buffer */
505 	xtpage_t *p;		/* page */
506 	xad_t *xad;
507 	int base, index, lim, btindex;
508 	struct btframe *btsp;
509 	int nsplit = 0;		/* number of pages to split */
510 	s64 t64;
511 	s64 next = 0;
512 
513 	INCREMENT(xtStat.search);
514 
515 	BT_CLR(btstack);
516 
517 	btstack->nsplit = 0;
518 
519 	/*
520 	 *      search down tree from root:
521 	 *
522 	 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
523 	 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
524 	 *
525 	 * if entry with search key K is not found
526 	 * internal page search find the entry with largest key Ki
527 	 * less than K which point to the child page to search;
528 	 * leaf page search find the entry with smallest key Kj
529 	 * greater than K so that the returned index is the position of
530 	 * the entry to be shifted right for insertion of new entry.
531 	 * for empty tree, search key is greater than any key of the tree.
532 	 *
533 	 * by convention, root bn = 0.
534 	 */
535 	for (bn = 0;;) {
536 		/* get/pin the page to search */
537 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
538 		if (rc)
539 			return rc;
540 
541 		/* try sequential access heuristics with the previous
542 		 * access entry in target leaf page:
543 		 * once search narrowed down into the target leaf,
544 		 * key must either match an entry in the leaf or
545 		 * key entry does not exist in the tree;
546 		 */
547 //fastSearch:
548 		if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
549 		    (p->header.flag & BT_LEAF) &&
550 		    (index = jfs_ip->btindex) <
551 		    le16_to_cpu(p->header.nextindex)) {
552 			xad = &p->xad[index];
553 			t64 = offsetXAD(xad);
554 			if (xoff < t64 + lengthXAD(xad)) {
555 				if (xoff >= t64) {
556 					*cmpp = 0;
557 					goto out;
558 				}
559 
560 				/* stop sequential access heuristics */
561 				goto binarySearch;
562 			} else {	/* (t64 + lengthXAD(xad)) <= xoff */
563 
564 				/* try next sequential entry */
565 				index++;
566 				if (index <
567 				    le16_to_cpu(p->header.nextindex)) {
568 					xad++;
569 					t64 = offsetXAD(xad);
570 					if (xoff < t64 + lengthXAD(xad)) {
571 						if (xoff >= t64) {
572 							*cmpp = 0;
573 							goto out;
574 						}
575 
576 						/* miss: key falls between
577 						 * previous and this entry
578 						 */
579 						*cmpp = 1;
580 						next = t64;
581 						goto out;
582 					}
583 
584 					/* (xoff >= t64 + lengthXAD(xad));
585 					 * matching entry may be further out:
586 					 * stop heuristic search
587 					 */
588 					/* stop sequential access heuristics */
589 					goto binarySearch;
590 				}
591 
592 				/* (index == p->header.nextindex);
593 				 * miss: key entry does not exist in
594 				 * the target leaf/tree
595 				 */
596 				*cmpp = 1;
597 				goto out;
598 			}
599 
600 			/*
601 			 * if hit, return index of the entry found, and
602 			 * if miss, where new entry with search key is
603 			 * to be inserted;
604 			 */
605 		      out:
606 			/* compute number of pages to split */
607 			if (flag & XT_INSERT) {
608 				if (p->header.nextindex ==	/* little-endian */
609 				    p->header.maxentry)
610 					nsplit++;
611 				else
612 					nsplit = 0;
613 				btstack->nsplit = nsplit;
614 			}
615 
616 			/* save search result */
617 			btsp = btstack->top;
618 			btsp->bn = bn;
619 			btsp->index = index;
620 			btsp->mp = mp;
621 
622 			/* update sequential access heuristics */
623 			jfs_ip->btindex = index;
624 
625 			if (nextp)
626 				*nextp = next;
627 
628 			INCREMENT(xtStat.fastSearch);
629 			return 0;
630 		}
631 
632 		/* well, ... full search now */
633 	      binarySearch:
634 		lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
635 
636 		/*
637 		 * binary search with search key K on the current page
638 		 */
639 		for (base = XTENTRYSTART; lim; lim >>= 1) {
640 			index = base + (lim >> 1);
641 
642 			XT_CMP(cmp, xoff, &p->xad[index], t64);
643 			if (cmp == 0) {
644 				/*
645 				 *      search hit
646 				 */
647 				/* search hit - leaf page:
648 				 * return the entry found
649 				 */
650 				if (p->header.flag & BT_LEAF) {
651 					*cmpp = cmp;
652 
653 					/* compute number of pages to split */
654 					if (flag & XT_INSERT) {
655 						if (p->header.nextindex ==
656 						    p->header.maxentry)
657 							nsplit++;
658 						else
659 							nsplit = 0;
660 						btstack->nsplit = nsplit;
661 					}
662 
663 					/* save search result */
664 					btsp = btstack->top;
665 					btsp->bn = bn;
666 					btsp->index = index;
667 					btsp->mp = mp;
668 
669 					/* init sequential access heuristics */
670 					btindex = jfs_ip->btindex;
671 					if (index == btindex ||
672 					    index == btindex + 1)
673 						jfs_ip->btorder = BT_SEQUENTIAL;
674 					else
675 						jfs_ip->btorder = BT_RANDOM;
676 					jfs_ip->btindex = index;
677 
678 					return 0;
679 				}
680 				/* search hit - internal page:
681 				 * descend/search its child page
682 				 */
683 				if (index < le16_to_cpu(p->header.nextindex)-1)
684 					next = offsetXAD(&p->xad[index + 1]);
685 				goto next;
686 			}
687 
688 			if (cmp > 0) {
689 				base = index + 1;
690 				--lim;
691 			}
692 		}
693 
694 		/*
695 		 *      search miss
696 		 *
697 		 * base is the smallest index with key (Kj) greater than
698 		 * search key (K) and may be zero or maxentry index.
699 		 */
700 		if (base < le16_to_cpu(p->header.nextindex))
701 			next = offsetXAD(&p->xad[base]);
702 		/*
703 		 * search miss - leaf page:
704 		 *
705 		 * return location of entry (base) where new entry with
706 		 * search key K is to be inserted.
707 		 */
708 		if (p->header.flag & BT_LEAF) {
709 			*cmpp = cmp;
710 
711 			/* compute number of pages to split */
712 			if (flag & XT_INSERT) {
713 				if (p->header.nextindex ==
714 				    p->header.maxentry)
715 					nsplit++;
716 				else
717 					nsplit = 0;
718 				btstack->nsplit = nsplit;
719 			}
720 
721 			/* save search result */
722 			btsp = btstack->top;
723 			btsp->bn = bn;
724 			btsp->index = base;
725 			btsp->mp = mp;
726 
727 			/* init sequential access heuristics */
728 			btindex = jfs_ip->btindex;
729 			if (base == btindex || base == btindex + 1)
730 				jfs_ip->btorder = BT_SEQUENTIAL;
731 			else
732 				jfs_ip->btorder = BT_RANDOM;
733 			jfs_ip->btindex = base;
734 
735 			if (nextp)
736 				*nextp = next;
737 
738 			return 0;
739 		}
740 
741 		/*
742 		 * search miss - non-leaf page:
743 		 *
744 		 * if base is non-zero, decrement base by one to get the parent
745 		 * entry of the child page to search.
746 		 */
747 		index = base ? base - 1 : base;
748 
749 		/*
750 		 * go down to child page
751 		 */
752 	      next:
753 		/* update number of pages to split */
754 		if (p->header.nextindex == p->header.maxentry)
755 			nsplit++;
756 		else
757 			nsplit = 0;
758 
759 		/* push (bn, index) of the parent page/entry */
760 		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  */
790 int 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;
804 	s64 next;
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 	 */
818 	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
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: */
826 	if ((cmp == 0) || (next && (xlen > next - xoff))) {
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  */
941 static int
942 xtSplitUp(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  */
1214 static int
1215 xtSplitPage(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  */
1483 static int
1484 xtSplitRoot(tid_t tid,
1485 	    struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1486 {
1487 	xtpage_t *sp;
1488 	struct metapage *rmp;
1489 	xtpage_t *rp;
1490 	s64 rbn;
1491 	int skip, nextindex;
1492 	xad_t *xad;
1493 	pxd_t *pxd;
1494 	struct pxdlist *pxdlist;
1495 	struct tlock *tlck;
1496 	struct xtlock *xtlck;
1497 
1498 	sp = &JFS_IP(ip)->i_xtroot;
1499 
1500 	INCREMENT(xtStat.split);
1501 
1502 	/*
1503 	 *      allocate a single (right) child page
1504 	 */
1505 	pxdlist = split->pxdlist;
1506 	pxd = &pxdlist->pxd[pxdlist->npxd];
1507 	pxdlist->npxd++;
1508 	rbn = addressPXD(pxd);
1509 	rmp = get_metapage(ip, rbn, PSIZE, 1);
1510 	if (rmp == NULL)
1511 		return -EIO;
1512 
1513 	/* Allocate blocks to quota. */
1514 	if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1515 		release_metapage(rmp);
1516 		return -EDQUOT;
1517 	}
1518 
1519 	jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1520 
1521 	/*
1522 	 * acquire a transaction lock on the new right page;
1523 	 *
1524 	 * action: new page;
1525 	 */
1526 	BT_MARK_DIRTY(rmp, ip);
1527 
1528 	rp = (xtpage_t *) rmp->data;
1529 	rp->header.flag =
1530 	    (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1531 	rp->header.self = *pxd;
1532 	rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1533 	rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1534 
1535 	/* initialize sibling pointers */
1536 	rp->header.next = 0;
1537 	rp->header.prev = 0;
1538 
1539 	/*
1540 	 * copy the in-line root page into new right page extent
1541 	 */
1542 	nextindex = le16_to_cpu(sp->header.maxentry);
1543 	memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1544 		(nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1545 
1546 	/*
1547 	 * insert the new entry into the new right/child page
1548 	 * (skip index in the new right page will not change)
1549 	 */
1550 	skip = split->index;
1551 	/* if insert into middle, shift right remaining entries */
1552 	if (skip != nextindex)
1553 		memmove(&rp->xad[skip + 1], &rp->xad[skip],
1554 			(nextindex - skip) * sizeof(xad_t));
1555 
1556 	xad = &rp->xad[skip];
1557 	XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1558 
1559 	/* update page header */
1560 	rp->header.nextindex = cpu_to_le16(nextindex + 1);
1561 
1562 	if (!test_cflag(COMMIT_Nolink, ip)) {
1563 		tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1564 		xtlck = (struct xtlock *) & tlck->lock;
1565 		xtlck->lwm.offset = XTENTRYSTART;
1566 		xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1567 		    XTENTRYSTART;
1568 	}
1569 
1570 	/*
1571 	 *      reset the root
1572 	 *
1573 	 * init root with the single entry for the new right page
1574 	 * set the 1st entry offset to 0, which force the left-most key
1575 	 * at any level of the tree to be less than any search key.
1576 	 */
1577 	/*
1578 	 * acquire a transaction lock on the root page (in-memory inode);
1579 	 *
1580 	 * action: root split;
1581 	 */
1582 	BT_MARK_DIRTY(split->mp, ip);
1583 
1584 	xad = &sp->xad[XTENTRYSTART];
1585 	XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1586 
1587 	/* update page header of root */
1588 	sp->header.flag &= ~BT_LEAF;
1589 	sp->header.flag |= BT_INTERNAL;
1590 
1591 	sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1592 
1593 	if (!test_cflag(COMMIT_Nolink, ip)) {
1594 		tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1595 		xtlck = (struct xtlock *) & tlck->lock;
1596 		xtlck->lwm.offset = XTENTRYSTART;
1597 		xtlck->lwm.length = 1;
1598 	}
1599 
1600 	*rmpp = rmp;
1601 
1602 	jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1603 	return 0;
1604 }
1605 
1606 
1607 /*
1608  *      xtExtend()
1609  *
1610  * function: extend in-place;
1611  *
1612  * note: existing extent may or may not have been committed.
1613  * caller is responsible for pager buffer cache update, and
1614  * working block allocation map update;
1615  * update pmap: alloc whole extended extent;
1616  */
1617 int xtExtend(tid_t tid,		/* transaction id */
1618 	     struct inode *ip, s64 xoff,	/* delta extent offset */
1619 	     s32 xlen,		/* delta extent length */
1620 	     int flag)
1621 {
1622 	int rc = 0;
1623 	int cmp;
1624 	struct metapage *mp;	/* meta-page buffer */
1625 	xtpage_t *p;		/* base B+-tree index page */
1626 	s64 bn;
1627 	int index, nextindex, len;
1628 	struct btstack btstack;	/* traverse stack */
1629 	struct xtsplit split;	/* split information */
1630 	xad_t *xad;
1631 	s64 xaddr;
1632 	struct tlock *tlck;
1633 	struct xtlock *xtlck = NULL;
1634 
1635 	jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1636 
1637 	/* there must exist extent to be extended */
1638 	if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1639 		return rc;
1640 
1641 	/* retrieve search result */
1642 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1643 
1644 	if (cmp != 0) {
1645 		XT_PUTPAGE(mp);
1646 		jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1647 		return -EIO;
1648 	}
1649 
1650 	/* extension must be contiguous */
1651 	xad = &p->xad[index];
1652 	if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1653 		XT_PUTPAGE(mp);
1654 		jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1655 		return -EIO;
1656 	}
1657 
1658 	/*
1659 	 * acquire a transaction lock on the leaf page;
1660 	 *
1661 	 * action: xad insertion/extension;
1662 	 */
1663 	BT_MARK_DIRTY(mp, ip);
1664 	if (!test_cflag(COMMIT_Nolink, ip)) {
1665 		tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1666 		xtlck = (struct xtlock *) & tlck->lock;
1667 	}
1668 
1669 	/* extend will overflow extent ? */
1670 	xlen = lengthXAD(xad) + xlen;
1671 	if ((len = xlen - MAXXLEN) <= 0)
1672 		goto extendOld;
1673 
1674 	/*
1675 	 *      extent overflow: insert entry for new extent
1676 	 */
1677 //insertNew:
1678 	xoff = offsetXAD(xad) + MAXXLEN;
1679 	xaddr = addressXAD(xad) + MAXXLEN;
1680 	nextindex = le16_to_cpu(p->header.nextindex);
1681 
1682 	/*
1683 	 *      if the leaf page is full, insert the new entry and
1684 	 *      propagate up the router entry for the new page from split
1685 	 *
1686 	 * The xtSplitUp() will insert the entry and unpin the leaf page.
1687 	 */
1688 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
1689 		/* xtSpliUp() unpins leaf pages */
1690 		split.mp = mp;
1691 		split.index = index + 1;
1692 		split.flag = XAD_NEW;
1693 		split.off = xoff;	/* split offset */
1694 		split.len = len;
1695 		split.addr = xaddr;
1696 		split.pxdlist = NULL;
1697 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1698 			return rc;
1699 
1700 		/* get back old page */
1701 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1702 		if (rc)
1703 			return rc;
1704 		/*
1705 		 * if leaf root has been split, original root has been
1706 		 * copied to new child page, i.e., original entry now
1707 		 * resides on the new child page;
1708 		 */
1709 		if (p->header.flag & BT_INTERNAL) {
1710 			ASSERT(p->header.nextindex ==
1711 			       cpu_to_le16(XTENTRYSTART + 1));
1712 			xad = &p->xad[XTENTRYSTART];
1713 			bn = addressXAD(xad);
1714 			XT_PUTPAGE(mp);
1715 
1716 			/* get new child page */
1717 			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1718 			if (rc)
1719 				return rc;
1720 
1721 			BT_MARK_DIRTY(mp, ip);
1722 			if (!test_cflag(COMMIT_Nolink, ip)) {
1723 				tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1724 				xtlck = (struct xtlock *) & tlck->lock;
1725 			}
1726 		}
1727 	}
1728 	/*
1729 	 *      insert the new entry into the leaf page
1730 	 */
1731 	else {
1732 		/* insert the new entry: mark the entry NEW */
1733 		xad = &p->xad[index + 1];
1734 		XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1735 
1736 		/* advance next available entry index */
1737 		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  */
1780 int 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 /*
1801 printf("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 */
1806 	if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
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 /*
1839 printf("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  */
1965 int 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 
1989 	if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
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 
2303 		if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
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 /*
2342 printf("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  */
2430 int xtAppend(tid_t tid,		/* transaction id */
2431 	     struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
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;
2450 	s64 next;
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 	 */
2465 	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
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 	}
2475 
2476 	if (next)
2477 		xlen = min(xlen, (int)(next - xoff));
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;
2502 	for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
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 
2517 	xlen = min(xlen, maxblocks);
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  */
2601 int 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 	 */
2616 	if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
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  */
2672 static int
2673 xtDeleteUp(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  */
2823 int
2824 xtRelocate(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 */
2868 		rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
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 */
2967 			cmPut(cp, TRUE);
2968 
2969 			dxaddr += nblks;
2970 			sxaddr += nblks;
2971 		}
2972 
2973 		/* get back parent page */
2974 		if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
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  */
3158 static 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  */
3278 static 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  */
3340 void 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  */
3429 s64 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 
3519 
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.
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 
3536 	if (p->header.flag & BT_INTERNAL)
3537 		goto getChild;
3538 
3539 	/*
3540 	 *      leaf page
3541 	 */
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  */
3980 s64 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;
4007 		rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
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 
4135 #ifdef CONFIG_JFS_STATISTICS
4136 int 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
4167