Root/fs/jfs/jfs_xtree.c

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

Archive Download this file



interactive