1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  *   Copyright (C) International Business Machines Corp., 2000-2005
4  */
5 /*
6  *	jfs_xtree.c: extent allocation descriptor B+-tree manager
7  */
8 
9 #include <linux/fs.h>
10 #include <linux/module.h>
11 #include <linux/quotaops.h>
12 #include <linux/seq_file.h>
13 #include "jfs_incore.h"
14 #include "jfs_filsys.h"
15 #include "jfs_metapage.h"
16 #include "jfs_dmap.h"
17 #include "jfs_dinode.h"
18 #include "jfs_superblock.h"
19 #include "jfs_debug.h"
20 
21 /*
22  * xtree local flag
23  */
24 #define XT_INSERT	0x00000001
25 
26 /*
27  *	xtree key/entry comparison: extent offset
28  *
29  * return:
30  *	-1: k < start of extent
31  *	 0: start_of_extent <= k <= end_of_extent
32  *	 1: k > end_of_extent
33  */
34 #define XT_CMP(CMP, K, X, OFFSET64)\
35 {\
36 	OFFSET64 = offsetXAD(X);\
37 	(CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
38 		((K) < OFFSET64) ? -1 : 0;\
39 }
40 
41 /* write a xad entry */
42 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
43 {\
44 	(XAD)->flag = (FLAG);\
45 	XADoffset((XAD), (OFF));\
46 	XADlength((XAD), (LEN));\
47 	XADaddress((XAD), (ADDR));\
48 }
49 
50 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
51 
52 /* get page buffer for specified block address */
53 /* ToDo: Replace this ugly macro with a function */
54 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)				\
55 do {									\
56 	BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot);	\
57 	if (!(RC)) {							\
58 		if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) || \
59 		    (le16_to_cpu((P)->header.nextindex) >		\
60 		     le16_to_cpu((P)->header.maxentry)) ||		\
61 		    (le16_to_cpu((P)->header.maxentry) >		\
62 		     (((BN) == 0) ? XTROOTMAXSLOT : PSIZE >> L2XTSLOTSIZE))) { \
63 			jfs_error((IP)->i_sb,				\
64 				  "XT_GETPAGE: xtree page corrupt\n");	\
65 			BT_PUTPAGE(MP);					\
66 			MP = NULL;					\
67 			RC = -EIO;					\
68 		}							\
69 	}								\
70 } while (0)
71 
72 /* for consistency */
73 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
74 
75 #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
76 	BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
77 /* xtree entry parameter descriptor */
78 struct xtsplit {
79 	struct metapage *mp;
80 	s16 index;
81 	u8 flag;
82 	s64 off;
83 	s64 addr;
84 	int len;
85 	struct pxdlist *pxdlist;
86 };
87 
88 
89 /*
90  *	statistics
91  */
92 #ifdef CONFIG_JFS_STATISTICS
93 static struct {
94 	uint search;
95 	uint fastSearch;
96 	uint split;
97 } xtStat;
98 #endif
99 
100 
101 /*
102  * forward references
103  */
104 static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
105 		    struct btstack * btstack, int flag);
106 
107 static int xtSplitUp(tid_t tid,
108 		     struct inode *ip,
109 		     struct xtsplit * split, struct btstack * btstack);
110 
111 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
112 		       struct metapage ** rmpp, s64 * rbnp);
113 
114 static int xtSplitRoot(tid_t tid, struct inode *ip,
115 		       struct xtsplit * split, struct metapage ** rmpp);
116 
117 /*
118  *	xtLookup()
119  *
120  * function: map a single page into a physical extent;
121  */
xtLookup(struct inode * ip,s64 lstart,s64 llen,int * pflag,s64 * paddr,s32 * plen,int no_check)122 int xtLookup(struct inode *ip, s64 lstart,
123 	     s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
124 {
125 	int rc = 0;
126 	struct btstack btstack;
127 	int cmp;
128 	s64 bn;
129 	struct metapage *mp;
130 	xtpage_t *p;
131 	int index;
132 	xad_t *xad;
133 	s64 next, size, xoff, xend;
134 	int xlen;
135 	s64 xaddr;
136 
137 	*paddr = 0;
138 	*plen = llen;
139 
140 	if (!no_check) {
141 		/* is lookup offset beyond eof ? */
142 		size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
143 		    JFS_SBI(ip->i_sb)->l2bsize;
144 		if (lstart >= size)
145 			return 0;
146 	}
147 
148 	/*
149 	 * search for the xad entry covering the logical extent
150 	 */
151 //search:
152 	if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
153 		jfs_err("xtLookup: xtSearch returned %d", rc);
154 		return rc;
155 	}
156 
157 	/*
158 	 *	compute the physical extent covering logical extent
159 	 *
160 	 * N.B. search may have failed (e.g., hole in sparse file),
161 	 * and returned the index of the next entry.
162 	 */
163 	/* retrieve search result */
164 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
165 
166 	/* is xad found covering start of logical extent ?
167 	 * lstart is a page start address,
168 	 * i.e., lstart cannot start in a hole;
169 	 */
170 	if (cmp) {
171 		if (next)
172 			*plen = min(next - lstart, llen);
173 		goto out;
174 	}
175 
176 	/*
177 	 * lxd covered by xad
178 	 */
179 	xad = &p->xad[index];
180 	xoff = offsetXAD(xad);
181 	xlen = lengthXAD(xad);
182 	xend = xoff + xlen;
183 	xaddr = addressXAD(xad);
184 
185 	/* initialize new pxd */
186 	*pflag = xad->flag;
187 	*paddr = xaddr + (lstart - xoff);
188 	/* a page must be fully covered by an xad */
189 	*plen = min(xend - lstart, llen);
190 
191       out:
192 	XT_PUTPAGE(mp);
193 
194 	return rc;
195 }
196 
197 /*
198  *	xtSearch()
199  *
200  * function:	search for the xad entry covering specified offset.
201  *
202  * parameters:
203  *	ip	- file object;
204  *	xoff	- extent offset;
205  *	nextp	- address of next extent (if any) for search miss
206  *	cmpp	- comparison result:
207  *	btstack - traverse stack;
208  *	flag	- search process flag (XT_INSERT);
209  *
210  * returns:
211  *	btstack contains (bn, index) of search path traversed to the entry.
212  *	*cmpp is set to result of comparison with the entry returned.
213  *	the page containing the entry is pinned at exit.
214  */
xtSearch(struct inode * ip,s64 xoff,s64 * nextp,int * cmpp,struct btstack * btstack,int flag)215 static int xtSearch(struct inode *ip, s64 xoff,	s64 *nextp,
216 		    int *cmpp, struct btstack * btstack, int flag)
217 {
218 	struct jfs_inode_info *jfs_ip = JFS_IP(ip);
219 	int rc = 0;
220 	int cmp = 1;		/* init for empty page */
221 	s64 bn;			/* block number */
222 	struct metapage *mp;	/* page buffer */
223 	xtpage_t *p;		/* page */
224 	xad_t *xad;
225 	int base, index, lim, btindex;
226 	struct btframe *btsp;
227 	int nsplit = 0;		/* number of pages to split */
228 	s64 t64;
229 	s64 next = 0;
230 
231 	INCREMENT(xtStat.search);
232 
233 	BT_CLR(btstack);
234 
235 	btstack->nsplit = 0;
236 
237 	/*
238 	 *	search down tree from root:
239 	 *
240 	 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
241 	 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
242 	 *
243 	 * if entry with search key K is not found
244 	 * internal page search find the entry with largest key Ki
245 	 * less than K which point to the child page to search;
246 	 * leaf page search find the entry with smallest key Kj
247 	 * greater than K so that the returned index is the position of
248 	 * the entry to be shifted right for insertion of new entry.
249 	 * for empty tree, search key is greater than any key of the tree.
250 	 *
251 	 * by convention, root bn = 0.
252 	 */
253 	for (bn = 0;;) {
254 		/* get/pin the page to search */
255 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
256 		if (rc)
257 			return rc;
258 
259 		/* try sequential access heuristics with the previous
260 		 * access entry in target leaf page:
261 		 * once search narrowed down into the target leaf,
262 		 * key must either match an entry in the leaf or
263 		 * key entry does not exist in the tree;
264 		 */
265 //fastSearch:
266 		if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
267 		    (p->header.flag & BT_LEAF) &&
268 		    (index = jfs_ip->btindex) <
269 		    le16_to_cpu(p->header.nextindex)) {
270 			xad = &p->xad[index];
271 			t64 = offsetXAD(xad);
272 			if (xoff < t64 + lengthXAD(xad)) {
273 				if (xoff >= t64) {
274 					*cmpp = 0;
275 					goto out;
276 				}
277 
278 				/* stop sequential access heuristics */
279 				goto binarySearch;
280 			} else {	/* (t64 + lengthXAD(xad)) <= xoff */
281 
282 				/* try next sequential entry */
283 				index++;
284 				if (index <
285 				    le16_to_cpu(p->header.nextindex)) {
286 					xad++;
287 					t64 = offsetXAD(xad);
288 					if (xoff < t64 + lengthXAD(xad)) {
289 						if (xoff >= t64) {
290 							*cmpp = 0;
291 							goto out;
292 						}
293 
294 						/* miss: key falls between
295 						 * previous and this entry
296 						 */
297 						*cmpp = 1;
298 						next = t64;
299 						goto out;
300 					}
301 
302 					/* (xoff >= t64 + lengthXAD(xad));
303 					 * matching entry may be further out:
304 					 * stop heuristic search
305 					 */
306 					/* stop sequential access heuristics */
307 					goto binarySearch;
308 				}
309 
310 				/* (index == p->header.nextindex);
311 				 * miss: key entry does not exist in
312 				 * the target leaf/tree
313 				 */
314 				*cmpp = 1;
315 				goto out;
316 			}
317 
318 			/*
319 			 * if hit, return index of the entry found, and
320 			 * if miss, where new entry with search key is
321 			 * to be inserted;
322 			 */
323 		      out:
324 			/* compute number of pages to split */
325 			if (flag & XT_INSERT) {
326 				if (p->header.nextindex ==	/* little-endian */
327 				    p->header.maxentry)
328 					nsplit++;
329 				else
330 					nsplit = 0;
331 				btstack->nsplit = nsplit;
332 			}
333 
334 			/* save search result */
335 			btsp = btstack->top;
336 			btsp->bn = bn;
337 			btsp->index = index;
338 			btsp->mp = mp;
339 
340 			/* update sequential access heuristics */
341 			jfs_ip->btindex = index;
342 
343 			if (nextp)
344 				*nextp = next;
345 
346 			INCREMENT(xtStat.fastSearch);
347 			return 0;
348 		}
349 
350 		/* well, ... full search now */
351 	      binarySearch:
352 		lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
353 
354 		/*
355 		 * binary search with search key K on the current page
356 		 */
357 		for (base = XTENTRYSTART; lim; lim >>= 1) {
358 			index = base + (lim >> 1);
359 
360 			XT_CMP(cmp, xoff, &p->xad[index], t64);
361 			if (cmp == 0) {
362 				/*
363 				 *	search hit
364 				 */
365 				/* search hit - leaf page:
366 				 * return the entry found
367 				 */
368 				if (p->header.flag & BT_LEAF) {
369 					*cmpp = cmp;
370 
371 					/* compute number of pages to split */
372 					if (flag & XT_INSERT) {
373 						if (p->header.nextindex ==
374 						    p->header.maxentry)
375 							nsplit++;
376 						else
377 							nsplit = 0;
378 						btstack->nsplit = nsplit;
379 					}
380 
381 					/* save search result */
382 					btsp = btstack->top;
383 					btsp->bn = bn;
384 					btsp->index = index;
385 					btsp->mp = mp;
386 
387 					/* init sequential access heuristics */
388 					btindex = jfs_ip->btindex;
389 					if (index == btindex ||
390 					    index == btindex + 1)
391 						jfs_ip->btorder = BT_SEQUENTIAL;
392 					else
393 						jfs_ip->btorder = BT_RANDOM;
394 					jfs_ip->btindex = index;
395 
396 					return 0;
397 				}
398 				/* search hit - internal page:
399 				 * descend/search its child page
400 				 */
401 				if (index < le16_to_cpu(p->header.nextindex)-1)
402 					next = offsetXAD(&p->xad[index + 1]);
403 				goto next;
404 			}
405 
406 			if (cmp > 0) {
407 				base = index + 1;
408 				--lim;
409 			}
410 		}
411 
412 		/*
413 		 *	search miss
414 		 *
415 		 * base is the smallest index with key (Kj) greater than
416 		 * search key (K) and may be zero or maxentry index.
417 		 */
418 		if (base < le16_to_cpu(p->header.nextindex))
419 			next = offsetXAD(&p->xad[base]);
420 		/*
421 		 * search miss - leaf page:
422 		 *
423 		 * return location of entry (base) where new entry with
424 		 * search key K is to be inserted.
425 		 */
426 		if (p->header.flag & BT_LEAF) {
427 			*cmpp = cmp;
428 
429 			/* compute number of pages to split */
430 			if (flag & XT_INSERT) {
431 				if (p->header.nextindex ==
432 				    p->header.maxentry)
433 					nsplit++;
434 				else
435 					nsplit = 0;
436 				btstack->nsplit = nsplit;
437 			}
438 
439 			/* save search result */
440 			btsp = btstack->top;
441 			btsp->bn = bn;
442 			btsp->index = base;
443 			btsp->mp = mp;
444 
445 			/* init sequential access heuristics */
446 			btindex = jfs_ip->btindex;
447 			if (base == btindex || base == btindex + 1)
448 				jfs_ip->btorder = BT_SEQUENTIAL;
449 			else
450 				jfs_ip->btorder = BT_RANDOM;
451 			jfs_ip->btindex = base;
452 
453 			if (nextp)
454 				*nextp = next;
455 
456 			return 0;
457 		}
458 
459 		/*
460 		 * search miss - non-leaf page:
461 		 *
462 		 * if base is non-zero, decrement base by one to get the parent
463 		 * entry of the child page to search.
464 		 */
465 		index = base ? base - 1 : base;
466 
467 		/*
468 		 * go down to child page
469 		 */
470 	      next:
471 		/* update number of pages to split */
472 		if (p->header.nextindex == p->header.maxentry)
473 			nsplit++;
474 		else
475 			nsplit = 0;
476 
477 		/* push (bn, index) of the parent page/entry */
478 		if (BT_STACK_FULL(btstack)) {
479 			jfs_error(ip->i_sb, "stack overrun!\n");
480 			XT_PUTPAGE(mp);
481 			return -EIO;
482 		}
483 		BT_PUSH(btstack, bn, index);
484 
485 		/* get the child page block number */
486 		bn = addressXAD(&p->xad[index]);
487 
488 		/* unpin the parent page */
489 		XT_PUTPAGE(mp);
490 	}
491 }
492 
493 /*
494  *	xtInsert()
495  *
496  * function:
497  *
498  * parameter:
499  *	tid	- transaction id;
500  *	ip	- file object;
501  *	xflag	- extent flag (XAD_NOTRECORDED):
502  *	xoff	- extent offset;
503  *	xlen	- extent length;
504  *	xaddrp	- extent address pointer (in/out):
505  *		if (*xaddrp)
506  *			caller allocated data extent at *xaddrp;
507  *		else
508  *			allocate data extent and return its xaddr;
509  *	flag	-
510  *
511  * return:
512  */
xtInsert(tid_t tid,struct inode * ip,int xflag,s64 xoff,s32 xlen,s64 * xaddrp,int flag)513 int xtInsert(tid_t tid,		/* transaction id */
514 	     struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
515 	     int flag)
516 {
517 	int rc = 0;
518 	s64 xaddr, hint;
519 	struct metapage *mp;	/* meta-page buffer */
520 	xtpage_t *p;		/* base B+-tree index page */
521 	s64 bn;
522 	int index, nextindex;
523 	struct btstack btstack;	/* traverse stack */
524 	struct xtsplit split;	/* split information */
525 	xad_t *xad;
526 	int cmp;
527 	s64 next;
528 	struct tlock *tlck;
529 	struct xtlock *xtlck;
530 
531 	jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
532 
533 	/*
534 	 *	search for the entry location at which to insert:
535 	 *
536 	 * xtFastSearch() and xtSearch() both returns (leaf page
537 	 * pinned, index at which to insert).
538 	 * n.b. xtSearch() may return index of maxentry of
539 	 * the full page.
540 	 */
541 	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
542 		return rc;
543 
544 	/* retrieve search result */
545 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
546 
547 	/* This test must follow XT_GETSEARCH since mp must be valid if
548 	 * we branch to out: */
549 	if ((cmp == 0) || (next && (xlen > next - xoff))) {
550 		rc = -EEXIST;
551 		goto out;
552 	}
553 
554 	/*
555 	 * allocate data extent requested
556 	 *
557 	 * allocation hint: last xad
558 	 */
559 	if ((xaddr = *xaddrp) == 0) {
560 		if (index > XTENTRYSTART) {
561 			xad = &p->xad[index - 1];
562 			hint = addressXAD(xad) + lengthXAD(xad) - 1;
563 		} else
564 			hint = 0;
565 		if ((rc = dquot_alloc_block(ip, xlen)))
566 			goto out;
567 		if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
568 			dquot_free_block(ip, xlen);
569 			goto out;
570 		}
571 	}
572 
573 	/*
574 	 *	insert entry for new extent
575 	 */
576 	xflag |= XAD_NEW;
577 
578 	/*
579 	 *	if the leaf page is full, split the page and
580 	 *	propagate up the router entry for the new page from split
581 	 *
582 	 * The xtSplitUp() will insert the entry and unpin the leaf page.
583 	 */
584 	nextindex = le16_to_cpu(p->header.nextindex);
585 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
586 		split.mp = mp;
587 		split.index = index;
588 		split.flag = xflag;
589 		split.off = xoff;
590 		split.len = xlen;
591 		split.addr = xaddr;
592 		split.pxdlist = NULL;
593 		if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
594 			/* undo data extent allocation */
595 			if (*xaddrp == 0) {
596 				dbFree(ip, xaddr, (s64) xlen);
597 				dquot_free_block(ip, xlen);
598 			}
599 			return rc;
600 		}
601 
602 		*xaddrp = xaddr;
603 		return 0;
604 	}
605 
606 	/*
607 	 *	insert the new entry into the leaf page
608 	 */
609 	/*
610 	 * acquire a transaction lock on the leaf page;
611 	 *
612 	 * action: xad insertion/extension;
613 	 */
614 	BT_MARK_DIRTY(mp, ip);
615 
616 	/* if insert into middle, shift right remaining entries. */
617 	if (index < nextindex)
618 		memmove(&p->xad[index + 1], &p->xad[index],
619 			(nextindex - index) * sizeof(xad_t));
620 
621 	/* insert the new entry: mark the entry NEW */
622 	xad = &p->xad[index];
623 	XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
624 
625 	/* advance next available entry index */
626 	le16_add_cpu(&p->header.nextindex, 1);
627 
628 	/* Don't log it if there are no links to the file */
629 	if (!test_cflag(COMMIT_Nolink, ip)) {
630 		tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
631 		xtlck = (struct xtlock *) & tlck->lock;
632 		xtlck->lwm.offset =
633 		    (xtlck->lwm.offset) ? min(index,
634 					      (int)xtlck->lwm.offset) : index;
635 		xtlck->lwm.length =
636 		    le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
637 	}
638 
639 	*xaddrp = xaddr;
640 
641       out:
642 	/* unpin the leaf page */
643 	XT_PUTPAGE(mp);
644 
645 	return rc;
646 }
647 
648 
649 /*
650  *	xtSplitUp()
651  *
652  * function:
653  *	split full pages as propagating insertion up the tree
654  *
655  * parameter:
656  *	tid	- transaction id;
657  *	ip	- file object;
658  *	split	- entry parameter descriptor;
659  *	btstack - traverse stack from xtSearch()
660  *
661  * return:
662  */
663 static int
xtSplitUp(tid_t tid,struct inode * ip,struct xtsplit * split,struct btstack * btstack)664 xtSplitUp(tid_t tid,
665 	  struct inode *ip, struct xtsplit * split, struct btstack * btstack)
666 {
667 	int rc = 0;
668 	struct metapage *smp;
669 	xtpage_t *sp;		/* split page */
670 	struct metapage *rmp;
671 	s64 rbn;		/* new right page block number */
672 	struct metapage *rcmp;
673 	xtpage_t *rcp;		/* right child page */
674 	s64 rcbn;		/* right child page block number */
675 	int skip;		/* index of entry of insertion */
676 	int nextindex;		/* next available entry index of p */
677 	struct btframe *parent;	/* parent page entry on traverse stack */
678 	xad_t *xad;
679 	s64 xaddr;
680 	int xlen;
681 	int nsplit;		/* number of pages split */
682 	struct pxdlist pxdlist;
683 	pxd_t *pxd;
684 	struct tlock *tlck;
685 	struct xtlock *xtlck;
686 
687 	smp = split->mp;
688 	sp = XT_PAGE(ip, smp);
689 
690 	/* is inode xtree root extension/inline EA area free ? */
691 	if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
692 	    (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
693 	    (JFS_IP(ip)->mode2 & INLINEEA)) {
694 		sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
695 		JFS_IP(ip)->mode2 &= ~INLINEEA;
696 
697 		BT_MARK_DIRTY(smp, ip);
698 		/*
699 		 * acquire a transaction lock on the leaf page;
700 		 *
701 		 * action: xad insertion/extension;
702 		 */
703 
704 		/* if insert into middle, shift right remaining entries. */
705 		skip = split->index;
706 		nextindex = le16_to_cpu(sp->header.nextindex);
707 		if (skip < nextindex)
708 			memmove(&sp->xad[skip + 1], &sp->xad[skip],
709 				(nextindex - skip) * sizeof(xad_t));
710 
711 		/* insert the new entry: mark the entry NEW */
712 		xad = &sp->xad[skip];
713 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
714 			    split->addr);
715 
716 		/* advance next available entry index */
717 		le16_add_cpu(&sp->header.nextindex, 1);
718 
719 		/* Don't log it if there are no links to the file */
720 		if (!test_cflag(COMMIT_Nolink, ip)) {
721 			tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
722 			xtlck = (struct xtlock *) & tlck->lock;
723 			xtlck->lwm.offset = (xtlck->lwm.offset) ?
724 			    min(skip, (int)xtlck->lwm.offset) : skip;
725 			xtlck->lwm.length =
726 			    le16_to_cpu(sp->header.nextindex) -
727 			    xtlck->lwm.offset;
728 		}
729 
730 		return 0;
731 	}
732 
733 	/*
734 	 * allocate new index blocks to cover index page split(s)
735 	 *
736 	 * allocation hint: ?
737 	 */
738 	if (split->pxdlist == NULL) {
739 		nsplit = btstack->nsplit;
740 		split->pxdlist = &pxdlist;
741 		pxdlist.maxnpxd = pxdlist.npxd = 0;
742 		pxd = &pxdlist.pxd[0];
743 		xlen = JFS_SBI(ip->i_sb)->nbperpage;
744 		for (; nsplit > 0; nsplit--, pxd++) {
745 			if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
746 			    == 0) {
747 				PXDaddress(pxd, xaddr);
748 				PXDlength(pxd, xlen);
749 
750 				pxdlist.maxnpxd++;
751 
752 				continue;
753 			}
754 
755 			/* undo allocation */
756 
757 			XT_PUTPAGE(smp);
758 			return rc;
759 		}
760 	}
761 
762 	/*
763 	 * Split leaf page <sp> into <sp> and a new right page <rp>.
764 	 *
765 	 * The split routines insert the new entry into the leaf page,
766 	 * and acquire txLock as appropriate.
767 	 * return <rp> pinned and its block number <rpbn>.
768 	 */
769 	rc = (sp->header.flag & BT_ROOT) ?
770 	    xtSplitRoot(tid, ip, split, &rmp) :
771 	    xtSplitPage(tid, ip, split, &rmp, &rbn);
772 
773 	XT_PUTPAGE(smp);
774 
775 	if (rc)
776 		return -EIO;
777 	/*
778 	 * propagate up the router entry for the leaf page just split
779 	 *
780 	 * insert a router entry for the new page into the parent page,
781 	 * propagate the insert/split up the tree by walking back the stack
782 	 * of (bn of parent page, index of child page entry in parent page)
783 	 * that were traversed during the search for the page that split.
784 	 *
785 	 * the propagation of insert/split up the tree stops if the root
786 	 * splits or the page inserted into doesn't have to split to hold
787 	 * the new entry.
788 	 *
789 	 * the parent entry for the split page remains the same, and
790 	 * a new entry is inserted at its right with the first key and
791 	 * block number of the new right page.
792 	 *
793 	 * There are a maximum of 3 pages pinned at any time:
794 	 * right child, left parent and right parent (when the parent splits)
795 	 * to keep the child page pinned while working on the parent.
796 	 * make sure that all pins are released at exit.
797 	 */
798 	while ((parent = BT_POP(btstack)) != NULL) {
799 		/* parent page specified by stack frame <parent> */
800 
801 		/* keep current child pages <rcp> pinned */
802 		rcmp = rmp;
803 		rcbn = rbn;
804 		rcp = XT_PAGE(ip, rcmp);
805 
806 		/*
807 		 * insert router entry in parent for new right child page <rp>
808 		 */
809 		/* get/pin the parent page <sp> */
810 		XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
811 		if (rc) {
812 			XT_PUTPAGE(rcmp);
813 			return rc;
814 		}
815 
816 		/*
817 		 * The new key entry goes ONE AFTER the index of parent entry,
818 		 * because the split was to the right.
819 		 */
820 		skip = parent->index + 1;
821 
822 		/*
823 		 * split or shift right remaining entries of the parent page
824 		 */
825 		nextindex = le16_to_cpu(sp->header.nextindex);
826 		/*
827 		 * parent page is full - split the parent page
828 		 */
829 		if (nextindex == le16_to_cpu(sp->header.maxentry)) {
830 			/* init for parent page split */
831 			split->mp = smp;
832 			split->index = skip;	/* index at insert */
833 			split->flag = XAD_NEW;
834 			split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
835 			split->len = JFS_SBI(ip->i_sb)->nbperpage;
836 			split->addr = rcbn;
837 
838 			/* unpin previous right child page */
839 			XT_PUTPAGE(rcmp);
840 
841 			/* The split routines insert the new entry,
842 			 * and acquire txLock as appropriate.
843 			 * return <rp> pinned and its block number <rpbn>.
844 			 */
845 			rc = (sp->header.flag & BT_ROOT) ?
846 			    xtSplitRoot(tid, ip, split, &rmp) :
847 			    xtSplitPage(tid, ip, split, &rmp, &rbn);
848 			if (rc) {
849 				XT_PUTPAGE(smp);
850 				return rc;
851 			}
852 
853 			XT_PUTPAGE(smp);
854 			/* keep new child page <rp> pinned */
855 		}
856 		/*
857 		 * parent page is not full - insert in parent page
858 		 */
859 		else {
860 			/*
861 			 * insert router entry in parent for the right child
862 			 * page from the first entry of the right child page:
863 			 */
864 			/*
865 			 * acquire a transaction lock on the parent page;
866 			 *
867 			 * action: router xad insertion;
868 			 */
869 			BT_MARK_DIRTY(smp, ip);
870 
871 			/*
872 			 * if insert into middle, shift right remaining entries
873 			 */
874 			if (skip < nextindex)
875 				memmove(&sp->xad[skip + 1], &sp->xad[skip],
876 					(nextindex -
877 					 skip) << L2XTSLOTSIZE);
878 
879 			/* insert the router entry */
880 			xad = &sp->xad[skip];
881 			XT_PUTENTRY(xad, XAD_NEW,
882 				    offsetXAD(&rcp->xad[XTENTRYSTART]),
883 				    JFS_SBI(ip->i_sb)->nbperpage, rcbn);
884 
885 			/* advance next available entry index. */
886 			le16_add_cpu(&sp->header.nextindex, 1);
887 
888 			/* Don't log it if there are no links to the file */
889 			if (!test_cflag(COMMIT_Nolink, ip)) {
890 				tlck = txLock(tid, ip, smp,
891 					      tlckXTREE | tlckGROW);
892 				xtlck = (struct xtlock *) & tlck->lock;
893 				xtlck->lwm.offset = (xtlck->lwm.offset) ?
894 				    min(skip, (int)xtlck->lwm.offset) : skip;
895 				xtlck->lwm.length =
896 				    le16_to_cpu(sp->header.nextindex) -
897 				    xtlck->lwm.offset;
898 			}
899 
900 			/* unpin parent page */
901 			XT_PUTPAGE(smp);
902 
903 			/* exit propagate up */
904 			break;
905 		}
906 	}
907 
908 	/* unpin current right page */
909 	XT_PUTPAGE(rmp);
910 
911 	return 0;
912 }
913 
914 
915 /*
916  *	xtSplitPage()
917  *
918  * function:
919  *	split a full non-root page into
920  *	original/split/left page and new right page
921  *	i.e., the original/split page remains as left page.
922  *
923  * parameter:
924  *	int		tid,
925  *	struct inode	*ip,
926  *	struct xtsplit	*split,
927  *	struct metapage	**rmpp,
928  *	u64		*rbnp,
929  *
930  * return:
931  *	Pointer to page in which to insert or NULL on error.
932  */
933 static int
xtSplitPage(tid_t tid,struct inode * ip,struct xtsplit * split,struct metapage ** rmpp,s64 * rbnp)934 xtSplitPage(tid_t tid, struct inode *ip,
935 	    struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
936 {
937 	int rc = 0;
938 	struct metapage *smp;
939 	xtpage_t *sp;
940 	struct metapage *rmp;
941 	xtpage_t *rp;		/* new right page allocated */
942 	s64 rbn;		/* new right page block number */
943 	struct metapage *mp;
944 	xtpage_t *p;
945 	s64 nextbn;
946 	int skip, maxentry, middle, righthalf, n;
947 	xad_t *xad;
948 	struct pxdlist *pxdlist;
949 	pxd_t *pxd;
950 	struct tlock *tlck;
951 	struct xtlock *sxtlck = NULL, *rxtlck = NULL;
952 	int quota_allocation = 0;
953 
954 	smp = split->mp;
955 	sp = XT_PAGE(ip, smp);
956 
957 	INCREMENT(xtStat.split);
958 
959 	pxdlist = split->pxdlist;
960 	pxd = &pxdlist->pxd[pxdlist->npxd];
961 	pxdlist->npxd++;
962 	rbn = addressPXD(pxd);
963 
964 	/* Allocate blocks to quota. */
965 	rc = dquot_alloc_block(ip, lengthPXD(pxd));
966 	if (rc)
967 		goto clean_up;
968 
969 	quota_allocation += lengthPXD(pxd);
970 
971 	/*
972 	 * allocate the new right page for the split
973 	 */
974 	rmp = get_metapage(ip, rbn, PSIZE, 1);
975 	if (rmp == NULL) {
976 		rc = -EIO;
977 		goto clean_up;
978 	}
979 
980 	jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
981 
982 	BT_MARK_DIRTY(rmp, ip);
983 	/*
984 	 * action: new page;
985 	 */
986 
987 	rp = (xtpage_t *) rmp->data;
988 	rp->header.self = *pxd;
989 	rp->header.flag = sp->header.flag & BT_TYPE;
990 	rp->header.maxentry = sp->header.maxentry;	/* little-endian */
991 	rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
992 
993 	BT_MARK_DIRTY(smp, ip);
994 	/* Don't log it if there are no links to the file */
995 	if (!test_cflag(COMMIT_Nolink, ip)) {
996 		/*
997 		 * acquire a transaction lock on the new right page;
998 		 */
999 		tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1000 		rxtlck = (struct xtlock *) & tlck->lock;
1001 		rxtlck->lwm.offset = XTENTRYSTART;
1002 		/*
1003 		 * acquire a transaction lock on the split page
1004 		 */
1005 		tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1006 		sxtlck = (struct xtlock *) & tlck->lock;
1007 	}
1008 
1009 	/*
1010 	 * initialize/update sibling pointers of <sp> and <rp>
1011 	 */
1012 	nextbn = le64_to_cpu(sp->header.next);
1013 	rp->header.next = cpu_to_le64(nextbn);
1014 	rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1015 	sp->header.next = cpu_to_le64(rbn);
1016 
1017 	skip = split->index;
1018 
1019 	/*
1020 	 *	sequential append at tail (after last entry of last page)
1021 	 *
1022 	 * if splitting the last page on a level because of appending
1023 	 * a entry to it (skip is maxentry), it's likely that the access is
1024 	 * sequential. adding an empty page on the side of the level is less
1025 	 * work and can push the fill factor much higher than normal.
1026 	 * if we're wrong it's no big deal -  we will do the split the right
1027 	 * way next time.
1028 	 * (it may look like it's equally easy to do a similar hack for
1029 	 * reverse sorted data, that is, split the tree left, but it's not.
1030 	 * Be my guest.)
1031 	 */
1032 	if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1033 		/*
1034 		 * acquire a transaction lock on the new/right page;
1035 		 *
1036 		 * action: xad insertion;
1037 		 */
1038 		/* insert entry at the first entry of the new right page */
1039 		xad = &rp->xad[XTENTRYSTART];
1040 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1041 			    split->addr);
1042 
1043 		rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1044 
1045 		if (!test_cflag(COMMIT_Nolink, ip)) {
1046 			/* rxtlck->lwm.offset = XTENTRYSTART; */
1047 			rxtlck->lwm.length = 1;
1048 		}
1049 
1050 		*rmpp = rmp;
1051 		*rbnp = rbn;
1052 
1053 		jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1054 		return 0;
1055 	}
1056 
1057 	/*
1058 	 *	non-sequential insert (at possibly middle page)
1059 	 */
1060 
1061 	/*
1062 	 * update previous pointer of old next/right page of <sp>
1063 	 */
1064 	if (nextbn != 0) {
1065 		XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1066 		if (rc) {
1067 			XT_PUTPAGE(rmp);
1068 			goto clean_up;
1069 		}
1070 
1071 		BT_MARK_DIRTY(mp, ip);
1072 		/*
1073 		 * acquire a transaction lock on the next page;
1074 		 *
1075 		 * action:sibling pointer update;
1076 		 */
1077 		if (!test_cflag(COMMIT_Nolink, ip))
1078 			tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1079 
1080 		p->header.prev = cpu_to_le64(rbn);
1081 
1082 		/* sibling page may have been updated previously, or
1083 		 * it may be updated later;
1084 		 */
1085 
1086 		XT_PUTPAGE(mp);
1087 	}
1088 
1089 	/*
1090 	 * split the data between the split and new/right pages
1091 	 */
1092 	maxentry = le16_to_cpu(sp->header.maxentry);
1093 	middle = maxentry >> 1;
1094 	righthalf = maxentry - middle;
1095 
1096 	/*
1097 	 * skip index in old split/left page - insert into left page:
1098 	 */
1099 	if (skip <= middle) {
1100 		/* move right half of split page to the new right page */
1101 		memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1102 			righthalf << L2XTSLOTSIZE);
1103 
1104 		/* shift right tail of left half to make room for new entry */
1105 		if (skip < middle)
1106 			memmove(&sp->xad[skip + 1], &sp->xad[skip],
1107 				(middle - skip) << L2XTSLOTSIZE);
1108 
1109 		/* insert new entry */
1110 		xad = &sp->xad[skip];
1111 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1112 			    split->addr);
1113 
1114 		/* update page header */
1115 		sp->header.nextindex = cpu_to_le16(middle + 1);
1116 		if (!test_cflag(COMMIT_Nolink, ip)) {
1117 			sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1118 			    min(skip, (int)sxtlck->lwm.offset) : skip;
1119 		}
1120 
1121 		rp->header.nextindex =
1122 		    cpu_to_le16(XTENTRYSTART + righthalf);
1123 	}
1124 	/*
1125 	 * skip index in new right page - insert into right page:
1126 	 */
1127 	else {
1128 		/* move left head of right half to right page */
1129 		n = skip - middle;
1130 		memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1131 			n << L2XTSLOTSIZE);
1132 
1133 		/* insert new entry */
1134 		n += XTENTRYSTART;
1135 		xad = &rp->xad[n];
1136 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1137 			    split->addr);
1138 
1139 		/* move right tail of right half to right page */
1140 		if (skip < maxentry)
1141 			memmove(&rp->xad[n + 1], &sp->xad[skip],
1142 				(maxentry - skip) << L2XTSLOTSIZE);
1143 
1144 		/* update page header */
1145 		sp->header.nextindex = cpu_to_le16(middle);
1146 		if (!test_cflag(COMMIT_Nolink, ip)) {
1147 			sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1148 			    min(middle, (int)sxtlck->lwm.offset) : middle;
1149 		}
1150 
1151 		rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1152 						   righthalf + 1);
1153 	}
1154 
1155 	if (!test_cflag(COMMIT_Nolink, ip)) {
1156 		sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1157 		    sxtlck->lwm.offset;
1158 
1159 		/* rxtlck->lwm.offset = XTENTRYSTART; */
1160 		rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1161 		    XTENTRYSTART;
1162 	}
1163 
1164 	*rmpp = rmp;
1165 	*rbnp = rbn;
1166 
1167 	jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1168 	return rc;
1169 
1170       clean_up:
1171 
1172 	/* Rollback quota allocation. */
1173 	if (quota_allocation)
1174 		dquot_free_block(ip, quota_allocation);
1175 
1176 	return (rc);
1177 }
1178 
1179 
1180 /*
1181  *	xtSplitRoot()
1182  *
1183  * function:
1184  *	split the full root page into original/root/split page and new
1185  *	right page
1186  *	i.e., root remains fixed in tree anchor (inode) and the root is
1187  *	copied to a single new right child page since root page <<
1188  *	non-root page, and the split root page contains a single entry
1189  *	for the new right child page.
1190  *
1191  * parameter:
1192  *	int		tid,
1193  *	struct inode	*ip,
1194  *	struct xtsplit	*split,
1195  *	struct metapage	**rmpp)
1196  *
1197  * return:
1198  *	Pointer to page in which to insert or NULL on error.
1199  */
1200 static int
xtSplitRoot(tid_t tid,struct inode * ip,struct xtsplit * split,struct metapage ** rmpp)1201 xtSplitRoot(tid_t tid,
1202 	    struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1203 {
1204 	xtpage_t *sp;
1205 	struct metapage *rmp;
1206 	xtpage_t *rp;
1207 	s64 rbn;
1208 	int skip, nextindex;
1209 	xad_t *xad;
1210 	pxd_t *pxd;
1211 	struct pxdlist *pxdlist;
1212 	struct tlock *tlck;
1213 	struct xtlock *xtlck;
1214 	int rc;
1215 
1216 	sp = &JFS_IP(ip)->i_xtroot;
1217 
1218 	INCREMENT(xtStat.split);
1219 
1220 	/*
1221 	 *	allocate a single (right) child page
1222 	 */
1223 	pxdlist = split->pxdlist;
1224 	pxd = &pxdlist->pxd[pxdlist->npxd];
1225 	pxdlist->npxd++;
1226 	rbn = addressPXD(pxd);
1227 	rmp = get_metapage(ip, rbn, PSIZE, 1);
1228 	if (rmp == NULL)
1229 		return -EIO;
1230 
1231 	/* Allocate blocks to quota. */
1232 	rc = dquot_alloc_block(ip, lengthPXD(pxd));
1233 	if (rc) {
1234 		release_metapage(rmp);
1235 		return rc;
1236 	}
1237 
1238 	jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1239 
1240 	/*
1241 	 * acquire a transaction lock on the new right page;
1242 	 *
1243 	 * action: new page;
1244 	 */
1245 	BT_MARK_DIRTY(rmp, ip);
1246 
1247 	rp = (xtpage_t *) rmp->data;
1248 	rp->header.flag =
1249 	    (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1250 	rp->header.self = *pxd;
1251 	rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1252 	rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1253 
1254 	/* initialize sibling pointers */
1255 	rp->header.next = 0;
1256 	rp->header.prev = 0;
1257 
1258 	/*
1259 	 * copy the in-line root page into new right page extent
1260 	 */
1261 	nextindex = le16_to_cpu(sp->header.maxentry);
1262 	memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1263 		(nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1264 
1265 	/*
1266 	 * insert the new entry into the new right/child page
1267 	 * (skip index in the new right page will not change)
1268 	 */
1269 	skip = split->index;
1270 	/* if insert into middle, shift right remaining entries */
1271 	if (skip != nextindex)
1272 		memmove(&rp->xad[skip + 1], &rp->xad[skip],
1273 			(nextindex - skip) * sizeof(xad_t));
1274 
1275 	xad = &rp->xad[skip];
1276 	XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1277 
1278 	/* update page header */
1279 	rp->header.nextindex = cpu_to_le16(nextindex + 1);
1280 
1281 	if (!test_cflag(COMMIT_Nolink, ip)) {
1282 		tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1283 		xtlck = (struct xtlock *) & tlck->lock;
1284 		xtlck->lwm.offset = XTENTRYSTART;
1285 		xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1286 		    XTENTRYSTART;
1287 	}
1288 
1289 	/*
1290 	 *	reset the root
1291 	 *
1292 	 * init root with the single entry for the new right page
1293 	 * set the 1st entry offset to 0, which force the left-most key
1294 	 * at any level of the tree to be less than any search key.
1295 	 */
1296 	/*
1297 	 * acquire a transaction lock on the root page (in-memory inode);
1298 	 *
1299 	 * action: root split;
1300 	 */
1301 	BT_MARK_DIRTY(split->mp, ip);
1302 
1303 	xad = &sp->xad[XTENTRYSTART];
1304 	XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1305 
1306 	/* update page header of root */
1307 	sp->header.flag &= ~BT_LEAF;
1308 	sp->header.flag |= BT_INTERNAL;
1309 
1310 	sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1311 
1312 	if (!test_cflag(COMMIT_Nolink, ip)) {
1313 		tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1314 		xtlck = (struct xtlock *) & tlck->lock;
1315 		xtlck->lwm.offset = XTENTRYSTART;
1316 		xtlck->lwm.length = 1;
1317 	}
1318 
1319 	*rmpp = rmp;
1320 
1321 	jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1322 	return 0;
1323 }
1324 
1325 
1326 /*
1327  *	xtExtend()
1328  *
1329  * function: extend in-place;
1330  *
1331  * note: existing extent may or may not have been committed.
1332  * caller is responsible for pager buffer cache update, and
1333  * working block allocation map update;
1334  * update pmap: alloc whole extended extent;
1335  */
xtExtend(tid_t tid,struct inode * ip,s64 xoff,s32 xlen,int flag)1336 int xtExtend(tid_t tid,		/* transaction id */
1337 	     struct inode *ip, s64 xoff,	/* delta extent offset */
1338 	     s32 xlen,		/* delta extent length */
1339 	     int flag)
1340 {
1341 	int rc = 0;
1342 	int cmp;
1343 	struct metapage *mp;	/* meta-page buffer */
1344 	xtpage_t *p;		/* base B+-tree index page */
1345 	s64 bn;
1346 	int index, nextindex, len;
1347 	struct btstack btstack;	/* traverse stack */
1348 	struct xtsplit split;	/* split information */
1349 	xad_t *xad;
1350 	s64 xaddr;
1351 	struct tlock *tlck;
1352 	struct xtlock *xtlck = NULL;
1353 
1354 	jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1355 
1356 	/* there must exist extent to be extended */
1357 	if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1358 		return rc;
1359 
1360 	/* retrieve search result */
1361 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1362 
1363 	if (cmp != 0) {
1364 		XT_PUTPAGE(mp);
1365 		jfs_error(ip->i_sb, "xtSearch did not find extent\n");
1366 		return -EIO;
1367 	}
1368 
1369 	/* extension must be contiguous */
1370 	xad = &p->xad[index];
1371 	if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1372 		XT_PUTPAGE(mp);
1373 		jfs_error(ip->i_sb, "extension is not contiguous\n");
1374 		return -EIO;
1375 	}
1376 
1377 	/*
1378 	 * acquire a transaction lock on the leaf page;
1379 	 *
1380 	 * action: xad insertion/extension;
1381 	 */
1382 	BT_MARK_DIRTY(mp, ip);
1383 	if (!test_cflag(COMMIT_Nolink, ip)) {
1384 		tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1385 		xtlck = (struct xtlock *) & tlck->lock;
1386 	}
1387 
1388 	/* extend will overflow extent ? */
1389 	xlen = lengthXAD(xad) + xlen;
1390 	if ((len = xlen - MAXXLEN) <= 0)
1391 		goto extendOld;
1392 
1393 	/*
1394 	 *	extent overflow: insert entry for new extent
1395 	 */
1396 //insertNew:
1397 	xoff = offsetXAD(xad) + MAXXLEN;
1398 	xaddr = addressXAD(xad) + MAXXLEN;
1399 	nextindex = le16_to_cpu(p->header.nextindex);
1400 
1401 	/*
1402 	 *	if the leaf page is full, insert the new entry and
1403 	 *	propagate up the router entry for the new page from split
1404 	 *
1405 	 * The xtSplitUp() will insert the entry and unpin the leaf page.
1406 	 */
1407 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
1408 		/* xtSpliUp() unpins leaf pages */
1409 		split.mp = mp;
1410 		split.index = index + 1;
1411 		split.flag = XAD_NEW;
1412 		split.off = xoff;	/* split offset */
1413 		split.len = len;
1414 		split.addr = xaddr;
1415 		split.pxdlist = NULL;
1416 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1417 			return rc;
1418 
1419 		/* get back old page */
1420 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1421 		if (rc)
1422 			return rc;
1423 		/*
1424 		 * if leaf root has been split, original root has been
1425 		 * copied to new child page, i.e., original entry now
1426 		 * resides on the new child page;
1427 		 */
1428 		if (p->header.flag & BT_INTERNAL) {
1429 			ASSERT(p->header.nextindex ==
1430 			       cpu_to_le16(XTENTRYSTART + 1));
1431 			xad = &p->xad[XTENTRYSTART];
1432 			bn = addressXAD(xad);
1433 			XT_PUTPAGE(mp);
1434 
1435 			/* get new child page */
1436 			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1437 			if (rc)
1438 				return rc;
1439 
1440 			BT_MARK_DIRTY(mp, ip);
1441 			if (!test_cflag(COMMIT_Nolink, ip)) {
1442 				tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1443 				xtlck = (struct xtlock *) & tlck->lock;
1444 			}
1445 		}
1446 	}
1447 	/*
1448 	 *	insert the new entry into the leaf page
1449 	 */
1450 	else {
1451 		/* insert the new entry: mark the entry NEW */
1452 		xad = &p->xad[index + 1];
1453 		XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1454 
1455 		/* advance next available entry index */
1456 		le16_add_cpu(&p->header.nextindex, 1);
1457 	}
1458 
1459 	/* get back old entry */
1460 	xad = &p->xad[index];
1461 	xlen = MAXXLEN;
1462 
1463 	/*
1464 	 * extend old extent
1465 	 */
1466       extendOld:
1467 	XADlength(xad, xlen);
1468 	if (!(xad->flag & XAD_NEW))
1469 		xad->flag |= XAD_EXTENDED;
1470 
1471 	if (!test_cflag(COMMIT_Nolink, ip)) {
1472 		xtlck->lwm.offset =
1473 		    (xtlck->lwm.offset) ? min(index,
1474 					      (int)xtlck->lwm.offset) : index;
1475 		xtlck->lwm.length =
1476 		    le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1477 	}
1478 
1479 	/* unpin the leaf page */
1480 	XT_PUTPAGE(mp);
1481 
1482 	return rc;
1483 }
1484 
1485 /*
1486  *	xtUpdate()
1487  *
1488  * function: update XAD;
1489  *
1490  *	update extent for allocated_but_not_recorded or
1491  *	compressed extent;
1492  *
1493  * parameter:
1494  *	nxad	- new XAD;
1495  *		logical extent of the specified XAD must be completely
1496  *		contained by an existing XAD;
1497  */
xtUpdate(tid_t tid,struct inode * ip,xad_t * nxad)1498 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1499 {				/* new XAD */
1500 	int rc = 0;
1501 	int cmp;
1502 	struct metapage *mp;	/* meta-page buffer */
1503 	xtpage_t *p;		/* base B+-tree index page */
1504 	s64 bn;
1505 	int index0, index, newindex, nextindex;
1506 	struct btstack btstack;	/* traverse stack */
1507 	struct xtsplit split;	/* split information */
1508 	xad_t *xad, *lxad, *rxad;
1509 	int xflag;
1510 	s64 nxoff, xoff;
1511 	int nxlen, xlen, lxlen, rxlen;
1512 	s64 nxaddr, xaddr;
1513 	struct tlock *tlck;
1514 	struct xtlock *xtlck = NULL;
1515 	int newpage = 0;
1516 
1517 	/* there must exist extent to be tailgated */
1518 	nxoff = offsetXAD(nxad);
1519 	nxlen = lengthXAD(nxad);
1520 	nxaddr = addressXAD(nxad);
1521 
1522 	if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1523 		return rc;
1524 
1525 	/* retrieve search result */
1526 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1527 
1528 	if (cmp != 0) {
1529 		XT_PUTPAGE(mp);
1530 		jfs_error(ip->i_sb, "Could not find extent\n");
1531 		return -EIO;
1532 	}
1533 
1534 	BT_MARK_DIRTY(mp, ip);
1535 	/*
1536 	 * acquire tlock of the leaf page containing original entry
1537 	 */
1538 	if (!test_cflag(COMMIT_Nolink, ip)) {
1539 		tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1540 		xtlck = (struct xtlock *) & tlck->lock;
1541 	}
1542 
1543 	xad = &p->xad[index0];
1544 	xflag = xad->flag;
1545 	xoff = offsetXAD(xad);
1546 	xlen = lengthXAD(xad);
1547 	xaddr = addressXAD(xad);
1548 
1549 	/* nXAD must be completely contained within XAD */
1550 	if ((xoff > nxoff) ||
1551 	    (nxoff + nxlen > xoff + xlen)) {
1552 		XT_PUTPAGE(mp);
1553 		jfs_error(ip->i_sb,
1554 			  "nXAD in not completely contained within XAD\n");
1555 		return -EIO;
1556 	}
1557 
1558 	index = index0;
1559 	newindex = index + 1;
1560 	nextindex = le16_to_cpu(p->header.nextindex);
1561 
1562 	if (xoff < nxoff)
1563 		goto coalesceRight;
1564 
1565 	/*
1566 	 * coalesce with left XAD
1567 	 */
1568 	/* is XAD first entry of page ? */
1569 	if (index == XTENTRYSTART)
1570 		goto replace;
1571 
1572 	/* is nXAD logically and physically contiguous with lXAD ? */
1573 	lxad = &p->xad[index - 1];
1574 	lxlen = lengthXAD(lxad);
1575 	if (!(lxad->flag & XAD_NOTRECORDED) &&
1576 	    (nxoff == offsetXAD(lxad) + lxlen) &&
1577 	    (nxaddr == addressXAD(lxad) + lxlen) &&
1578 	    (lxlen + nxlen < MAXXLEN)) {
1579 		/* extend right lXAD */
1580 		index0 = index - 1;
1581 		XADlength(lxad, lxlen + nxlen);
1582 
1583 		/* If we just merged two extents together, need to make sure the
1584 		 * right extent gets logged.  If the left one is marked XAD_NEW,
1585 		 * then we know it will be logged.  Otherwise, mark as
1586 		 * XAD_EXTENDED
1587 		 */
1588 		if (!(lxad->flag & XAD_NEW))
1589 			lxad->flag |= XAD_EXTENDED;
1590 
1591 		if (xlen > nxlen) {
1592 			/* truncate XAD */
1593 			XADoffset(xad, xoff + nxlen);
1594 			XADlength(xad, xlen - nxlen);
1595 			XADaddress(xad, xaddr + nxlen);
1596 			goto out;
1597 		} else {	/* (xlen == nxlen) */
1598 
1599 			/* remove XAD */
1600 			if (index < nextindex - 1)
1601 				memmove(&p->xad[index], &p->xad[index + 1],
1602 					(nextindex - index -
1603 					 1) << L2XTSLOTSIZE);
1604 
1605 			p->header.nextindex =
1606 			    cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1607 					1);
1608 
1609 			index = index0;
1610 			newindex = index + 1;
1611 			nextindex = le16_to_cpu(p->header.nextindex);
1612 			xoff = nxoff = offsetXAD(lxad);
1613 			xlen = nxlen = lxlen + nxlen;
1614 			xaddr = nxaddr = addressXAD(lxad);
1615 			goto coalesceRight;
1616 		}
1617 	}
1618 
1619 	/*
1620 	 * replace XAD with nXAD
1621 	 */
1622       replace:			/* (nxoff == xoff) */
1623 	if (nxlen == xlen) {
1624 		/* replace XAD with nXAD:recorded */
1625 		*xad = *nxad;
1626 		xad->flag = xflag & ~XAD_NOTRECORDED;
1627 
1628 		goto coalesceRight;
1629 	} else			/* (nxlen < xlen) */
1630 		goto updateLeft;
1631 
1632 	/*
1633 	 * coalesce with right XAD
1634 	 */
1635       coalesceRight:		/* (xoff <= nxoff) */
1636 	/* is XAD last entry of page ? */
1637 	if (newindex == nextindex) {
1638 		if (xoff == nxoff)
1639 			goto out;
1640 		goto updateRight;
1641 	}
1642 
1643 	/* is nXAD logically and physically contiguous with rXAD ? */
1644 	rxad = &p->xad[index + 1];
1645 	rxlen = lengthXAD(rxad);
1646 	if (!(rxad->flag & XAD_NOTRECORDED) &&
1647 	    (nxoff + nxlen == offsetXAD(rxad)) &&
1648 	    (nxaddr + nxlen == addressXAD(rxad)) &&
1649 	    (rxlen + nxlen < MAXXLEN)) {
1650 		/* extend left rXAD */
1651 		XADoffset(rxad, nxoff);
1652 		XADlength(rxad, rxlen + nxlen);
1653 		XADaddress(rxad, nxaddr);
1654 
1655 		/* If we just merged two extents together, need to make sure
1656 		 * the left extent gets logged.  If the right one is marked
1657 		 * XAD_NEW, then we know it will be logged.  Otherwise, mark as
1658 		 * XAD_EXTENDED
1659 		 */
1660 		if (!(rxad->flag & XAD_NEW))
1661 			rxad->flag |= XAD_EXTENDED;
1662 
1663 		if (xlen > nxlen)
1664 			/* truncate XAD */
1665 			XADlength(xad, xlen - nxlen);
1666 		else {		/* (xlen == nxlen) */
1667 
1668 			/* remove XAD */
1669 			memmove(&p->xad[index], &p->xad[index + 1],
1670 				(nextindex - index - 1) << L2XTSLOTSIZE);
1671 
1672 			p->header.nextindex =
1673 			    cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1674 					1);
1675 		}
1676 
1677 		goto out;
1678 	} else if (xoff == nxoff)
1679 		goto out;
1680 
1681 	if (xoff >= nxoff) {
1682 		XT_PUTPAGE(mp);
1683 		jfs_error(ip->i_sb, "xoff >= nxoff\n");
1684 		return -EIO;
1685 	}
1686 
1687 	/*
1688 	 * split XAD into (lXAD, nXAD):
1689 	 *
1690 	 *          |---nXAD--->
1691 	 * --|----------XAD----------|--
1692 	 *   |-lXAD-|
1693 	 */
1694       updateRight:		/* (xoff < nxoff) */
1695 	/* truncate old XAD as lXAD:not_recorded */
1696 	xad = &p->xad[index];
1697 	XADlength(xad, nxoff - xoff);
1698 
1699 	/* insert nXAD:recorded */
1700 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
1701 
1702 		/* xtSpliUp() unpins leaf pages */
1703 		split.mp = mp;
1704 		split.index = newindex;
1705 		split.flag = xflag & ~XAD_NOTRECORDED;
1706 		split.off = nxoff;
1707 		split.len = nxlen;
1708 		split.addr = nxaddr;
1709 		split.pxdlist = NULL;
1710 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1711 			return rc;
1712 
1713 		/* get back old page */
1714 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1715 		if (rc)
1716 			return rc;
1717 		/*
1718 		 * if leaf root has been split, original root has been
1719 		 * copied to new child page, i.e., original entry now
1720 		 * resides on the new child page;
1721 		 */
1722 		if (p->header.flag & BT_INTERNAL) {
1723 			ASSERT(p->header.nextindex ==
1724 			       cpu_to_le16(XTENTRYSTART + 1));
1725 			xad = &p->xad[XTENTRYSTART];
1726 			bn = addressXAD(xad);
1727 			XT_PUTPAGE(mp);
1728 
1729 			/* get new child page */
1730 			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1731 			if (rc)
1732 				return rc;
1733 
1734 			BT_MARK_DIRTY(mp, ip);
1735 			if (!test_cflag(COMMIT_Nolink, ip)) {
1736 				tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1737 				xtlck = (struct xtlock *) & tlck->lock;
1738 			}
1739 		} else {
1740 			/* is nXAD on new page ? */
1741 			if (newindex >
1742 			    (le16_to_cpu(p->header.maxentry) >> 1)) {
1743 				newindex =
1744 				    newindex -
1745 				    le16_to_cpu(p->header.nextindex) +
1746 				    XTENTRYSTART;
1747 				newpage = 1;
1748 			}
1749 		}
1750 	} else {
1751 		/* if insert into middle, shift right remaining entries */
1752 		if (newindex < nextindex)
1753 			memmove(&p->xad[newindex + 1], &p->xad[newindex],
1754 				(nextindex - newindex) << L2XTSLOTSIZE);
1755 
1756 		/* insert the entry */
1757 		xad = &p->xad[newindex];
1758 		*xad = *nxad;
1759 		xad->flag = xflag & ~XAD_NOTRECORDED;
1760 
1761 		/* advance next available entry index. */
1762 		p->header.nextindex =
1763 		    cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1764 	}
1765 
1766 	/*
1767 	 * does nXAD force 3-way split ?
1768 	 *
1769 	 *          |---nXAD--->|
1770 	 * --|----------XAD-------------|--
1771 	 *   |-lXAD-|           |-rXAD -|
1772 	 */
1773 	if (nxoff + nxlen == xoff + xlen)
1774 		goto out;
1775 
1776 	/* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
1777 	if (newpage) {
1778 		/* close out old page */
1779 		if (!test_cflag(COMMIT_Nolink, ip)) {
1780 			xtlck->lwm.offset = (xtlck->lwm.offset) ?
1781 			    min(index0, (int)xtlck->lwm.offset) : index0;
1782 			xtlck->lwm.length =
1783 			    le16_to_cpu(p->header.nextindex) -
1784 			    xtlck->lwm.offset;
1785 		}
1786 
1787 		bn = le64_to_cpu(p->header.next);
1788 		XT_PUTPAGE(mp);
1789 
1790 		/* get new right page */
1791 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1792 		if (rc)
1793 			return rc;
1794 
1795 		BT_MARK_DIRTY(mp, ip);
1796 		if (!test_cflag(COMMIT_Nolink, ip)) {
1797 			tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1798 			xtlck = (struct xtlock *) & tlck->lock;
1799 		}
1800 
1801 		index0 = index = newindex;
1802 	} else
1803 		index++;
1804 
1805 	newindex = index + 1;
1806 	nextindex = le16_to_cpu(p->header.nextindex);
1807 	xlen = xlen - (nxoff - xoff);
1808 	xoff = nxoff;
1809 	xaddr = nxaddr;
1810 
1811 	/* recompute split pages */
1812 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
1813 		XT_PUTPAGE(mp);
1814 
1815 		if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1816 			return rc;
1817 
1818 		/* retrieve search result */
1819 		XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1820 
1821 		if (cmp != 0) {
1822 			XT_PUTPAGE(mp);
1823 			jfs_error(ip->i_sb, "xtSearch failed\n");
1824 			return -EIO;
1825 		}
1826 
1827 		if (index0 != index) {
1828 			XT_PUTPAGE(mp);
1829 			jfs_error(ip->i_sb, "unexpected value of index\n");
1830 			return -EIO;
1831 		}
1832 	}
1833 
1834 	/*
1835 	 * split XAD into (nXAD, rXAD)
1836 	 *
1837 	 *          ---nXAD---|
1838 	 * --|----------XAD----------|--
1839 	 *                    |-rXAD-|
1840 	 */
1841       updateLeft:		/* (nxoff == xoff) && (nxlen < xlen) */
1842 	/* update old XAD with nXAD:recorded */
1843 	xad = &p->xad[index];
1844 	*xad = *nxad;
1845 	xad->flag = xflag & ~XAD_NOTRECORDED;
1846 
1847 	/* insert rXAD:not_recorded */
1848 	xoff = xoff + nxlen;
1849 	xlen = xlen - nxlen;
1850 	xaddr = xaddr + nxlen;
1851 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
1852 /*
1853 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
1854 */
1855 		/* xtSpliUp() unpins leaf pages */
1856 		split.mp = mp;
1857 		split.index = newindex;
1858 		split.flag = xflag;
1859 		split.off = xoff;
1860 		split.len = xlen;
1861 		split.addr = xaddr;
1862 		split.pxdlist = NULL;
1863 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1864 			return rc;
1865 
1866 		/* get back old page */
1867 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1868 		if (rc)
1869 			return rc;
1870 
1871 		/*
1872 		 * if leaf root has been split, original root has been
1873 		 * copied to new child page, i.e., original entry now
1874 		 * resides on the new child page;
1875 		 */
1876 		if (p->header.flag & BT_INTERNAL) {
1877 			ASSERT(p->header.nextindex ==
1878 			       cpu_to_le16(XTENTRYSTART + 1));
1879 			xad = &p->xad[XTENTRYSTART];
1880 			bn = addressXAD(xad);
1881 			XT_PUTPAGE(mp);
1882 
1883 			/* get new child page */
1884 			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1885 			if (rc)
1886 				return rc;
1887 
1888 			BT_MARK_DIRTY(mp, ip);
1889 			if (!test_cflag(COMMIT_Nolink, ip)) {
1890 				tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1891 				xtlck = (struct xtlock *) & tlck->lock;
1892 			}
1893 		}
1894 	} else {
1895 		/* if insert into middle, shift right remaining entries */
1896 		if (newindex < nextindex)
1897 			memmove(&p->xad[newindex + 1], &p->xad[newindex],
1898 				(nextindex - newindex) << L2XTSLOTSIZE);
1899 
1900 		/* insert the entry */
1901 		xad = &p->xad[newindex];
1902 		XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
1903 
1904 		/* advance next available entry index. */
1905 		p->header.nextindex =
1906 		    cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1907 	}
1908 
1909       out:
1910 	if (!test_cflag(COMMIT_Nolink, ip)) {
1911 		xtlck->lwm.offset = (xtlck->lwm.offset) ?
1912 		    min(index0, (int)xtlck->lwm.offset) : index0;
1913 		xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1914 		    xtlck->lwm.offset;
1915 	}
1916 
1917 	/* unpin the leaf page */
1918 	XT_PUTPAGE(mp);
1919 
1920 	return rc;
1921 }
1922 
1923 
1924 /*
1925  *	xtAppend()
1926  *
1927  * function: grow in append mode from contiguous region specified ;
1928  *
1929  * parameter:
1930  *	tid		- transaction id;
1931  *	ip		- file object;
1932  *	xflag		- extent flag:
1933  *	xoff		- extent offset;
1934  *	maxblocks	- max extent length;
1935  *	xlen		- extent length (in/out);
1936  *	xaddrp		- extent address pointer (in/out):
1937  *	flag		-
1938  *
1939  * return:
1940  */
xtAppend(tid_t tid,struct inode * ip,int xflag,s64 xoff,s32 maxblocks,s32 * xlenp,s64 * xaddrp,int flag)1941 int xtAppend(tid_t tid,		/* transaction id */
1942 	     struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
1943 	     s32 * xlenp,	/* (in/out) */
1944 	     s64 * xaddrp,	/* (in/out) */
1945 	     int flag)
1946 {
1947 	int rc = 0;
1948 	struct metapage *mp;	/* meta-page buffer */
1949 	xtpage_t *p;		/* base B+-tree index page */
1950 	s64 bn, xaddr;
1951 	int index, nextindex;
1952 	struct btstack btstack;	/* traverse stack */
1953 	struct xtsplit split;	/* split information */
1954 	xad_t *xad;
1955 	int cmp;
1956 	struct tlock *tlck;
1957 	struct xtlock *xtlck;
1958 	int nsplit, nblocks, xlen;
1959 	struct pxdlist pxdlist;
1960 	pxd_t *pxd;
1961 	s64 next;
1962 
1963 	xaddr = *xaddrp;
1964 	xlen = *xlenp;
1965 	jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
1966 		 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
1967 
1968 	/*
1969 	 *	search for the entry location at which to insert:
1970 	 *
1971 	 * xtFastSearch() and xtSearch() both returns (leaf page
1972 	 * pinned, index at which to insert).
1973 	 * n.b. xtSearch() may return index of maxentry of
1974 	 * the full page.
1975 	 */
1976 	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
1977 		return rc;
1978 
1979 	/* retrieve search result */
1980 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1981 
1982 	if (cmp == 0) {
1983 		rc = -EEXIST;
1984 		goto out;
1985 	}
1986 
1987 	if (next)
1988 		xlen = min(xlen, (int)(next - xoff));
1989 //insert:
1990 	/*
1991 	 *	insert entry for new extent
1992 	 */
1993 	xflag |= XAD_NEW;
1994 
1995 	/*
1996 	 *	if the leaf page is full, split the page and
1997 	 *	propagate up the router entry for the new page from split
1998 	 *
1999 	 * The xtSplitUp() will insert the entry and unpin the leaf page.
2000 	 */
2001 	nextindex = le16_to_cpu(p->header.nextindex);
2002 	if (nextindex < le16_to_cpu(p->header.maxentry))
2003 		goto insertLeaf;
2004 
2005 	/*
2006 	 * allocate new index blocks to cover index page split(s)
2007 	 */
2008 	nsplit = btstack.nsplit;
2009 	split.pxdlist = &pxdlist;
2010 	pxdlist.maxnpxd = pxdlist.npxd = 0;
2011 	pxd = &pxdlist.pxd[0];
2012 	nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2013 	for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2014 		if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2015 			PXDaddress(pxd, xaddr);
2016 			PXDlength(pxd, nblocks);
2017 
2018 			pxdlist.maxnpxd++;
2019 
2020 			continue;
2021 		}
2022 
2023 		/* undo allocation */
2024 
2025 		goto out;
2026 	}
2027 
2028 	xlen = min(xlen, maxblocks);
2029 
2030 	/*
2031 	 * allocate data extent requested
2032 	 */
2033 	if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2034 		goto out;
2035 
2036 	split.mp = mp;
2037 	split.index = index;
2038 	split.flag = xflag;
2039 	split.off = xoff;
2040 	split.len = xlen;
2041 	split.addr = xaddr;
2042 	if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2043 		/* undo data extent allocation */
2044 		dbFree(ip, *xaddrp, (s64) * xlenp);
2045 
2046 		return rc;
2047 	}
2048 
2049 	*xaddrp = xaddr;
2050 	*xlenp = xlen;
2051 	return 0;
2052 
2053 	/*
2054 	 *	insert the new entry into the leaf page
2055 	 */
2056       insertLeaf:
2057 	/*
2058 	 * allocate data extent requested
2059 	 */
2060 	if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2061 		goto out;
2062 
2063 	BT_MARK_DIRTY(mp, ip);
2064 	/*
2065 	 * acquire a transaction lock on the leaf page;
2066 	 *
2067 	 * action: xad insertion/extension;
2068 	 */
2069 	tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2070 	xtlck = (struct xtlock *) & tlck->lock;
2071 
2072 	/* insert the new entry: mark the entry NEW */
2073 	xad = &p->xad[index];
2074 	XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2075 
2076 	/* advance next available entry index */
2077 	le16_add_cpu(&p->header.nextindex, 1);
2078 
2079 	xtlck->lwm.offset =
2080 	    (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2081 	xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2082 	    xtlck->lwm.offset;
2083 
2084 	*xaddrp = xaddr;
2085 	*xlenp = xlen;
2086 
2087       out:
2088 	/* unpin the leaf page */
2089 	XT_PUTPAGE(mp);
2090 
2091 	return rc;
2092 }
2093 
2094 /*
2095  *	xtInitRoot()
2096  *
2097  * initialize file root (inline in inode)
2098  */
xtInitRoot(tid_t tid,struct inode * ip)2099 void xtInitRoot(tid_t tid, struct inode *ip)
2100 {
2101 	xtpage_t *p;
2102 
2103 	/*
2104 	 * acquire a transaction lock on the root
2105 	 *
2106 	 * action:
2107 	 */
2108 	txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
2109 		      tlckXTREE | tlckNEW);
2110 	p = &JFS_IP(ip)->i_xtroot;
2111 
2112 	p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
2113 	p->header.nextindex = cpu_to_le16(XTENTRYSTART);
2114 
2115 	if (S_ISDIR(ip->i_mode))
2116 		p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
2117 	else {
2118 		p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
2119 		ip->i_size = 0;
2120 	}
2121 
2122 
2123 	return;
2124 }
2125 
2126 
2127 /*
2128  * We can run into a deadlock truncating a file with a large number of
2129  * xtree pages (large fragmented file).  A robust fix would entail a
2130  * reservation system where we would reserve a number of metadata pages
2131  * and tlocks which we would be guaranteed without a deadlock.  Without
2132  * this, a partial fix is to limit number of metadata pages we will lock
2133  * in a single transaction.  Currently we will truncate the file so that
2134  * no more than 50 leaf pages will be locked.  The caller of xtTruncate
2135  * will be responsible for ensuring that the current transaction gets
2136  * committed, and that subsequent transactions are created to truncate
2137  * the file further if needed.
2138  */
2139 #define MAX_TRUNCATE_LEAVES 50
2140 
2141 /*
2142  *	xtTruncate()
2143  *
2144  * function:
2145  *	traverse for truncation logging backward bottom up;
2146  *	terminate at the last extent entry at the current subtree
2147  *	root page covering new down size.
2148  *	truncation may occur within the last extent entry.
2149  *
2150  * parameter:
2151  *	int		tid,
2152  *	struct inode	*ip,
2153  *	s64		newsize,
2154  *	int		type)	{PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
2155  *
2156  * return:
2157  *
2158  * note:
2159  *	PWMAP:
2160  *	 1. truncate (non-COMMIT_NOLINK file)
2161  *	    by jfs_truncate() or jfs_open(O_TRUNC):
2162  *	    xtree is updated;
2163  *	 2. truncate index table of directory when last entry removed
2164  *	map update via tlock at commit time;
2165  *	PMAP:
2166  *	 Call xtTruncate_pmap instead
2167  *	WMAP:
2168  *	 1. remove (free zero link count) on last reference release
2169  *	    (pmap has been freed at commit zero link count);
2170  *	 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
2171  *	    xtree is updated;
2172  *	 map update directly at truncation time;
2173  *
2174  *	if (DELETE)
2175  *		no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
2176  *	else if (TRUNCATE)
2177  *		must write LOG_NOREDOPAGE for deleted index page;
2178  *
2179  * pages may already have been tlocked by anonymous transactions
2180  * during file growth (i.e., write) before truncation;
2181  *
2182  * except last truncated entry, deleted entries remains as is
2183  * in the page (nextindex is updated) for other use
2184  * (e.g., log/update allocation map): this avoid copying the page
2185  * info but delay free of pages;
2186  *
2187  */
xtTruncate(tid_t tid,struct inode * ip,s64 newsize,int flag)2188 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
2189 {
2190 	int rc = 0;
2191 	s64 teof;
2192 	struct metapage *mp;
2193 	xtpage_t *p;
2194 	s64 bn;
2195 	int index, nextindex;
2196 	xad_t *xad;
2197 	s64 xoff, xaddr;
2198 	int xlen, len, freexlen;
2199 	struct btstack btstack;
2200 	struct btframe *parent;
2201 	struct tblock *tblk = NULL;
2202 	struct tlock *tlck = NULL;
2203 	struct xtlock *xtlck = NULL;
2204 	struct xdlistlock xadlock;	/* maplock for COMMIT_WMAP */
2205 	struct pxd_lock *pxdlock;		/* maplock for COMMIT_WMAP */
2206 	s64 nfreed;
2207 	int freed, log;
2208 	int locked_leaves = 0;
2209 
2210 	/* save object truncation type */
2211 	if (tid) {
2212 		tblk = tid_to_tblock(tid);
2213 		tblk->xflag |= flag;
2214 	}
2215 
2216 	nfreed = 0;
2217 
2218 	flag &= COMMIT_MAP;
2219 	assert(flag != COMMIT_PMAP);
2220 
2221 	if (flag == COMMIT_PWMAP)
2222 		log = 1;
2223 	else {
2224 		log = 0;
2225 		xadlock.flag = mlckFREEXADLIST;
2226 		xadlock.index = 1;
2227 	}
2228 
2229 	/*
2230 	 * if the newsize is not an integral number of pages,
2231 	 * the file between newsize and next page boundary will
2232 	 * be cleared.
2233 	 * if truncating into a file hole, it will cause
2234 	 * a full block to be allocated for the logical block.
2235 	 */
2236 
2237 	/*
2238 	 * release page blocks of truncated region <teof, eof>
2239 	 *
2240 	 * free the data blocks from the leaf index blocks.
2241 	 * delete the parent index entries corresponding to
2242 	 * the freed child data/index blocks.
2243 	 * free the index blocks themselves which aren't needed
2244 	 * in new sized file.
2245 	 *
2246 	 * index blocks are updated only if the blocks are to be
2247 	 * retained in the new sized file.
2248 	 * if type is PMAP, the data and index pages are NOT
2249 	 * freed, and the data and index blocks are NOT freed
2250 	 * from working map.
2251 	 * (this will allow continued access of data/index of
2252 	 * temporary file (zerolink count file truncated to zero-length)).
2253 	 */
2254 	teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
2255 	    JFS_SBI(ip->i_sb)->l2bsize;
2256 
2257 	/* clear stack */
2258 	BT_CLR(&btstack);
2259 
2260 	/*
2261 	 * start with root
2262 	 *
2263 	 * root resides in the inode
2264 	 */
2265 	bn = 0;
2266 
2267 	/*
2268 	 * first access of each page:
2269 	 */
2270       getPage:
2271 	XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2272 	if (rc)
2273 		return rc;
2274 
2275 	/* process entries backward from last index */
2276 	index = le16_to_cpu(p->header.nextindex) - 1;
2277 
2278 
2279 	/* Since this is the rightmost page at this level, and we may have
2280 	 * already freed a page that was formerly to the right, let's make
2281 	 * sure that the next pointer is zero.
2282 	 */
2283 	if (p->header.next) {
2284 		if (log)
2285 			/*
2286 			 * Make sure this change to the header is logged.
2287 			 * If we really truncate this leaf, the flag
2288 			 * will be changed to tlckTRUNCATE
2289 			 */
2290 			tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2291 		BT_MARK_DIRTY(mp, ip);
2292 		p->header.next = 0;
2293 	}
2294 
2295 	if (p->header.flag & BT_INTERNAL)
2296 		goto getChild;
2297 
2298 	/*
2299 	 *	leaf page
2300 	 */
2301 	freed = 0;
2302 
2303 	/* does region covered by leaf page precede Teof ? */
2304 	xad = &p->xad[index];
2305 	xoff = offsetXAD(xad);
2306 	xlen = lengthXAD(xad);
2307 	if (teof >= xoff + xlen) {
2308 		XT_PUTPAGE(mp);
2309 		goto getParent;
2310 	}
2311 
2312 	/* (re)acquire tlock of the leaf page */
2313 	if (log) {
2314 		if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
2315 			/*
2316 			 * We need to limit the size of the transaction
2317 			 * to avoid exhausting pagecache & tlocks
2318 			 */
2319 			XT_PUTPAGE(mp);
2320 			newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
2321 			goto getParent;
2322 		}
2323 		tlck = txLock(tid, ip, mp, tlckXTREE);
2324 		tlck->type = tlckXTREE | tlckTRUNCATE;
2325 		xtlck = (struct xtlock *) & tlck->lock;
2326 		xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
2327 	}
2328 	BT_MARK_DIRTY(mp, ip);
2329 
2330 	/*
2331 	 * scan backward leaf page entries
2332 	 */
2333 	for (; index >= XTENTRYSTART; index--) {
2334 		xad = &p->xad[index];
2335 		xoff = offsetXAD(xad);
2336 		xlen = lengthXAD(xad);
2337 		xaddr = addressXAD(xad);
2338 
2339 		/*
2340 		 * The "data" for a directory is indexed by the block
2341 		 * device's address space.  This metadata must be invalidated
2342 		 * here
2343 		 */
2344 		if (S_ISDIR(ip->i_mode) && (teof == 0))
2345 			invalidate_xad_metapages(ip, *xad);
2346 		/*
2347 		 * entry beyond eof: continue scan of current page
2348 		 *          xad
2349 		 * ---|---=======------->
2350 		 *   eof
2351 		 */
2352 		if (teof < xoff) {
2353 			nfreed += xlen;
2354 			continue;
2355 		}
2356 
2357 		/*
2358 		 * (xoff <= teof): last entry to be deleted from page;
2359 		 * If other entries remain in page: keep and update the page.
2360 		 */
2361 
2362 		/*
2363 		 * eof == entry_start: delete the entry
2364 		 *           xad
2365 		 * -------|=======------->
2366 		 *       eof
2367 		 *
2368 		 */
2369 		if (teof == xoff) {
2370 			nfreed += xlen;
2371 
2372 			if (index == XTENTRYSTART)
2373 				break;
2374 
2375 			nextindex = index;
2376 		}
2377 		/*
2378 		 * eof within the entry: truncate the entry.
2379 		 *          xad
2380 		 * -------===|===------->
2381 		 *          eof
2382 		 */
2383 		else if (teof < xoff + xlen) {
2384 			/* update truncated entry */
2385 			len = teof - xoff;
2386 			freexlen = xlen - len;
2387 			XADlength(xad, len);
2388 
2389 			/* save pxd of truncated extent in tlck */
2390 			xaddr += len;
2391 			if (log) {	/* COMMIT_PWMAP */
2392 				xtlck->lwm.offset = (xtlck->lwm.offset) ?
2393 				    min(index, (int)xtlck->lwm.offset) : index;
2394 				xtlck->lwm.length = index + 1 -
2395 				    xtlck->lwm.offset;
2396 				xtlck->twm.offset = index;
2397 				pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
2398 				pxdlock->flag = mlckFREEPXD;
2399 				PXDaddress(&pxdlock->pxd, xaddr);
2400 				PXDlength(&pxdlock->pxd, freexlen);
2401 			}
2402 			/* free truncated extent */
2403 			else {	/* COMMIT_WMAP */
2404 
2405 				pxdlock = (struct pxd_lock *) & xadlock;
2406 				pxdlock->flag = mlckFREEPXD;
2407 				PXDaddress(&pxdlock->pxd, xaddr);
2408 				PXDlength(&pxdlock->pxd, freexlen);
2409 				txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
2410 
2411 				/* reset map lock */
2412 				xadlock.flag = mlckFREEXADLIST;
2413 			}
2414 
2415 			/* current entry is new last entry; */
2416 			nextindex = index + 1;
2417 
2418 			nfreed += freexlen;
2419 		}
2420 		/*
2421 		 * eof beyond the entry:
2422 		 *          xad
2423 		 * -------=======---|--->
2424 		 *                 eof
2425 		 */
2426 		else {		/* (xoff + xlen < teof) */
2427 
2428 			nextindex = index + 1;
2429 		}
2430 
2431 		if (nextindex < le16_to_cpu(p->header.nextindex)) {
2432 			if (!log) {	/* COMMIT_WAMP */
2433 				xadlock.xdlist = &p->xad[nextindex];
2434 				xadlock.count =
2435 				    le16_to_cpu(p->header.nextindex) -
2436 				    nextindex;
2437 				txFreeMap(ip, (struct maplock *) & xadlock,
2438 					  NULL, COMMIT_WMAP);
2439 			}
2440 			p->header.nextindex = cpu_to_le16(nextindex);
2441 		}
2442 
2443 		XT_PUTPAGE(mp);
2444 
2445 		/* assert(freed == 0); */
2446 		goto getParent;
2447 	}			/* end scan of leaf page entries */
2448 
2449 	freed = 1;
2450 
2451 	/*
2452 	 * leaf page become empty: free the page if type != PMAP
2453 	 */
2454 	if (log) {		/* COMMIT_PWMAP */
2455 		/* txCommit() with tlckFREE:
2456 		 * free data extents covered by leaf [XTENTRYSTART:hwm);
2457 		 * invalidate leaf if COMMIT_PWMAP;
2458 		 * if (TRUNCATE), will write LOG_NOREDOPAGE;
2459 		 */
2460 		tlck->type = tlckXTREE | tlckFREE;
2461 	} else {		/* COMMIT_WAMP */
2462 
2463 		/* free data extents covered by leaf */
2464 		xadlock.xdlist = &p->xad[XTENTRYSTART];
2465 		xadlock.count =
2466 		    le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
2467 		txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
2468 	}
2469 
2470 	if (p->header.flag & BT_ROOT) {
2471 		p->header.flag &= ~BT_INTERNAL;
2472 		p->header.flag |= BT_LEAF;
2473 		p->header.nextindex = cpu_to_le16(XTENTRYSTART);
2474 
2475 		XT_PUTPAGE(mp);	/* debug */
2476 		goto out;
2477 	} else {
2478 		if (log) {	/* COMMIT_PWMAP */
2479 			/* page will be invalidated at tx completion
2480 			 */
2481 			XT_PUTPAGE(mp);
2482 		} else {	/* COMMIT_WMAP */
2483 
2484 			if (mp->lid)
2485 				lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
2486 
2487 			/* invalidate empty leaf page */
2488 			discard_metapage(mp);
2489 		}
2490 	}
2491 
2492 	/*
2493 	 * the leaf page become empty: delete the parent entry
2494 	 * for the leaf page if the parent page is to be kept
2495 	 * in the new sized file.
2496 	 */
2497 
2498 	/*
2499 	 * go back up to the parent page
2500 	 */
2501       getParent:
2502 	/* pop/restore parent entry for the current child page */
2503 	if ((parent = BT_POP(&btstack)) == NULL)
2504 		/* current page must have been root */
2505 		goto out;
2506 
2507 	/* get back the parent page */
2508 	bn = parent->bn;
2509 	XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2510 	if (rc)
2511 		return rc;
2512 
2513 	index = parent->index;
2514 
2515 	/*
2516 	 * child page was not empty:
2517 	 */
2518 	if (freed == 0) {
2519 		/* has any entry deleted from parent ? */
2520 		if (index < le16_to_cpu(p->header.nextindex) - 1) {
2521 			/* (re)acquire tlock on the parent page */
2522 			if (log) {	/* COMMIT_PWMAP */
2523 				/* txCommit() with tlckTRUNCATE:
2524 				 * free child extents covered by parent [);
2525 				 */
2526 				tlck = txLock(tid, ip, mp, tlckXTREE);
2527 				xtlck = (struct xtlock *) & tlck->lock;
2528 				if (!(tlck->type & tlckTRUNCATE)) {
2529 					xtlck->hwm.offset =
2530 					    le16_to_cpu(p->header.
2531 							nextindex) - 1;
2532 					tlck->type =
2533 					    tlckXTREE | tlckTRUNCATE;
2534 				}
2535 			} else {	/* COMMIT_WMAP */
2536 
2537 				/* free child extents covered by parent */
2538 				xadlock.xdlist = &p->xad[index + 1];
2539 				xadlock.count =
2540 				    le16_to_cpu(p->header.nextindex) -
2541 				    index - 1;
2542 				txFreeMap(ip, (struct maplock *) & xadlock,
2543 					  NULL, COMMIT_WMAP);
2544 			}
2545 			BT_MARK_DIRTY(mp, ip);
2546 
2547 			p->header.nextindex = cpu_to_le16(index + 1);
2548 		}
2549 		XT_PUTPAGE(mp);
2550 		goto getParent;
2551 	}
2552 
2553 	/*
2554 	 * child page was empty:
2555 	 */
2556 	nfreed += lengthXAD(&p->xad[index]);
2557 
2558 	/*
2559 	 * During working map update, child page's tlock must be handled
2560 	 * before parent's.  This is because the parent's tlock will cause
2561 	 * the child's disk space to be marked available in the wmap, so
2562 	 * it's important that the child page be released by that time.
2563 	 *
2564 	 * ToDo:  tlocks should be on doubly-linked list, so we can
2565 	 * quickly remove it and add it to the end.
2566 	 */
2567 
2568 	/*
2569 	 * Move parent page's tlock to the end of the tid's tlock list
2570 	 */
2571 	if (log && mp->lid && (tblk->last != mp->lid) &&
2572 	    lid_to_tlock(mp->lid)->tid) {
2573 		lid_t lid = mp->lid;
2574 		struct tlock *prev;
2575 
2576 		tlck = lid_to_tlock(lid);
2577 
2578 		if (tblk->next == lid)
2579 			tblk->next = tlck->next;
2580 		else {
2581 			for (prev = lid_to_tlock(tblk->next);
2582 			     prev->next != lid;
2583 			     prev = lid_to_tlock(prev->next)) {
2584 				assert(prev->next);
2585 			}
2586 			prev->next = tlck->next;
2587 		}
2588 		lid_to_tlock(tblk->last)->next = lid;
2589 		tlck->next = 0;
2590 		tblk->last = lid;
2591 	}
2592 
2593 	/*
2594 	 * parent page become empty: free the page
2595 	 */
2596 	if (index == XTENTRYSTART) {
2597 		if (log) {	/* COMMIT_PWMAP */
2598 			/* txCommit() with tlckFREE:
2599 			 * free child extents covered by parent;
2600 			 * invalidate parent if COMMIT_PWMAP;
2601 			 */
2602 			tlck = txLock(tid, ip, mp, tlckXTREE);
2603 			xtlck = (struct xtlock *) & tlck->lock;
2604 			xtlck->hwm.offset =
2605 			    le16_to_cpu(p->header.nextindex) - 1;
2606 			tlck->type = tlckXTREE | tlckFREE;
2607 		} else {	/* COMMIT_WMAP */
2608 
2609 			/* free child extents covered by parent */
2610 			xadlock.xdlist = &p->xad[XTENTRYSTART];
2611 			xadlock.count =
2612 			    le16_to_cpu(p->header.nextindex) -
2613 			    XTENTRYSTART;
2614 			txFreeMap(ip, (struct maplock *) & xadlock, NULL,
2615 				  COMMIT_WMAP);
2616 		}
2617 		BT_MARK_DIRTY(mp, ip);
2618 
2619 		if (p->header.flag & BT_ROOT) {
2620 			p->header.flag &= ~BT_INTERNAL;
2621 			p->header.flag |= BT_LEAF;
2622 			p->header.nextindex = cpu_to_le16(XTENTRYSTART);
2623 			if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
2624 				/*
2625 				 * Shrink root down to allow inline
2626 				 * EA (otherwise fsck complains)
2627 				 */
2628 				p->header.maxentry =
2629 				    cpu_to_le16(XTROOTINITSLOT);
2630 				JFS_IP(ip)->mode2 |= INLINEEA;
2631 			}
2632 
2633 			XT_PUTPAGE(mp);	/* debug */
2634 			goto out;
2635 		} else {
2636 			if (log) {	/* COMMIT_PWMAP */
2637 				/* page will be invalidated at tx completion
2638 				 */
2639 				XT_PUTPAGE(mp);
2640 			} else {	/* COMMIT_WMAP */
2641 
2642 				if (mp->lid)
2643 					lid_to_tlock(mp->lid)->flag |=
2644 						tlckFREELOCK;
2645 
2646 				/* invalidate parent page */
2647 				discard_metapage(mp);
2648 			}
2649 
2650 			/* parent has become empty and freed:
2651 			 * go back up to its parent page
2652 			 */
2653 			/* freed = 1; */
2654 			goto getParent;
2655 		}
2656 	}
2657 	/*
2658 	 * parent page still has entries for front region;
2659 	 */
2660 	else {
2661 		/* try truncate region covered by preceding entry
2662 		 * (process backward)
2663 		 */
2664 		index--;
2665 
2666 		/* go back down to the child page corresponding
2667 		 * to the entry
2668 		 */
2669 		goto getChild;
2670 	}
2671 
2672 	/*
2673 	 *	internal page: go down to child page of current entry
2674 	 */
2675       getChild:
2676 	/* save current parent entry for the child page */
2677 	if (BT_STACK_FULL(&btstack)) {
2678 		jfs_error(ip->i_sb, "stack overrun!\n");
2679 		XT_PUTPAGE(mp);
2680 		return -EIO;
2681 	}
2682 	BT_PUSH(&btstack, bn, index);
2683 
2684 	/* get child page */
2685 	xad = &p->xad[index];
2686 	bn = addressXAD(xad);
2687 
2688 	/*
2689 	 * first access of each internal entry:
2690 	 */
2691 	/* release parent page */
2692 	XT_PUTPAGE(mp);
2693 
2694 	/* process the child page */
2695 	goto getPage;
2696 
2697       out:
2698 	/*
2699 	 * update file resource stat
2700 	 */
2701 	/* set size
2702 	 */
2703 	if (S_ISDIR(ip->i_mode) && !newsize)
2704 		ip->i_size = 1;	/* fsck hates zero-length directories */
2705 	else
2706 		ip->i_size = newsize;
2707 
2708 	/* update quota allocation to reflect freed blocks */
2709 	dquot_free_block(ip, nfreed);
2710 
2711 	/*
2712 	 * free tlock of invalidated pages
2713 	 */
2714 	if (flag == COMMIT_WMAP)
2715 		txFreelock(ip);
2716 
2717 	return newsize;
2718 }
2719 
2720 
2721 /*
2722  *	xtTruncate_pmap()
2723  *
2724  * function:
2725  *	Perform truncate to zero length for deleted file, leaving the
2726  *	xtree and working map untouched.  This allows the file to
2727  *	be accessed via open file handles, while the delete of the file
2728  *	is committed to disk.
2729  *
2730  * parameter:
2731  *	tid_t		tid,
2732  *	struct inode	*ip,
2733  *	s64		committed_size)
2734  *
2735  * return: new committed size
2736  *
2737  * note:
2738  *
2739  *	To avoid deadlock by holding too many transaction locks, the
2740  *	truncation may be broken up into multiple transactions.
2741  *	The committed_size keeps track of part of the file has been
2742  *	freed from the pmaps.
2743  */
xtTruncate_pmap(tid_t tid,struct inode * ip,s64 committed_size)2744 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
2745 {
2746 	s64 bn;
2747 	struct btstack btstack;
2748 	int cmp;
2749 	int index;
2750 	int locked_leaves = 0;
2751 	struct metapage *mp;
2752 	xtpage_t *p;
2753 	struct btframe *parent;
2754 	int rc;
2755 	struct tblock *tblk;
2756 	struct tlock *tlck = NULL;
2757 	xad_t *xad;
2758 	int xlen;
2759 	s64 xoff;
2760 	struct xtlock *xtlck = NULL;
2761 
2762 	/* save object truncation type */
2763 	tblk = tid_to_tblock(tid);
2764 	tblk->xflag |= COMMIT_PMAP;
2765 
2766 	/* clear stack */
2767 	BT_CLR(&btstack);
2768 
2769 	if (committed_size) {
2770 		xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
2771 		rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2772 		if (rc)
2773 			return rc;
2774 
2775 		XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2776 
2777 		if (cmp != 0) {
2778 			XT_PUTPAGE(mp);
2779 			jfs_error(ip->i_sb, "did not find extent\n");
2780 			return -EIO;
2781 		}
2782 	} else {
2783 		/*
2784 		 * start with root
2785 		 *
2786 		 * root resides in the inode
2787 		 */
2788 		bn = 0;
2789 
2790 		/*
2791 		 * first access of each page:
2792 		 */
2793       getPage:
2794 		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2795 		if (rc)
2796 			return rc;
2797 
2798 		/* process entries backward from last index */
2799 		index = le16_to_cpu(p->header.nextindex) - 1;
2800 
2801 		if (p->header.flag & BT_INTERNAL)
2802 			goto getChild;
2803 	}
2804 
2805 	/*
2806 	 *	leaf page
2807 	 */
2808 
2809 	if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
2810 		/*
2811 		 * We need to limit the size of the transaction
2812 		 * to avoid exhausting pagecache & tlocks
2813 		 */
2814 		xad = &p->xad[index];
2815 		xoff = offsetXAD(xad);
2816 		xlen = lengthXAD(xad);
2817 		XT_PUTPAGE(mp);
2818 		return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
2819 	}
2820 	tlck = txLock(tid, ip, mp, tlckXTREE);
2821 	tlck->type = tlckXTREE | tlckFREE;
2822 	xtlck = (struct xtlock *) & tlck->lock;
2823 	xtlck->hwm.offset = index;
2824 
2825 
2826 	XT_PUTPAGE(mp);
2827 
2828 	/*
2829 	 * go back up to the parent page
2830 	 */
2831       getParent:
2832 	/* pop/restore parent entry for the current child page */
2833 	if ((parent = BT_POP(&btstack)) == NULL)
2834 		/* current page must have been root */
2835 		goto out;
2836 
2837 	/* get back the parent page */
2838 	bn = parent->bn;
2839 	XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2840 	if (rc)
2841 		return rc;
2842 
2843 	index = parent->index;
2844 
2845 	/*
2846 	 * parent page become empty: free the page
2847 	 */
2848 	if (index == XTENTRYSTART) {
2849 		/* txCommit() with tlckFREE:
2850 		 * free child extents covered by parent;
2851 		 * invalidate parent if COMMIT_PWMAP;
2852 		 */
2853 		tlck = txLock(tid, ip, mp, tlckXTREE);
2854 		xtlck = (struct xtlock *) & tlck->lock;
2855 		xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
2856 		tlck->type = tlckXTREE | tlckFREE;
2857 
2858 		XT_PUTPAGE(mp);
2859 
2860 		if (p->header.flag & BT_ROOT) {
2861 
2862 			goto out;
2863 		} else {
2864 			goto getParent;
2865 		}
2866 	}
2867 	/*
2868 	 * parent page still has entries for front region;
2869 	 */
2870 	else
2871 		index--;
2872 	/*
2873 	 *	internal page: go down to child page of current entry
2874 	 */
2875       getChild:
2876 	/* save current parent entry for the child page */
2877 	if (BT_STACK_FULL(&btstack)) {
2878 		jfs_error(ip->i_sb, "stack overrun!\n");
2879 		XT_PUTPAGE(mp);
2880 		return -EIO;
2881 	}
2882 	BT_PUSH(&btstack, bn, index);
2883 
2884 	/* get child page */
2885 	xad = &p->xad[index];
2886 	bn = addressXAD(xad);
2887 
2888 	/*
2889 	 * first access of each internal entry:
2890 	 */
2891 	/* release parent page */
2892 	XT_PUTPAGE(mp);
2893 
2894 	/* process the child page */
2895 	goto getPage;
2896 
2897       out:
2898 
2899 	return 0;
2900 }
2901 
2902 #ifdef CONFIG_JFS_STATISTICS
jfs_xtstat_proc_show(struct seq_file * m,void * v)2903 int jfs_xtstat_proc_show(struct seq_file *m, void *v)
2904 {
2905 	seq_printf(m,
2906 		       "JFS Xtree statistics\n"
2907 		       "====================\n"
2908 		       "searches = %d\n"
2909 		       "fast searches = %d\n"
2910 		       "splits = %d\n",
2911 		       xtStat.search,
2912 		       xtStat.fastSearch,
2913 		       xtStat.split);
2914 	return 0;
2915 }
2916 #endif
2917