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