0cc63d657a14ed2937df63826b3445aac41ef600
[linux-2.6.git] / fs / xfs / xfs_btree.c
1 /*
2  * Copyright (c) 2000-2002 Silicon Graphics, Inc.  All Rights Reserved.
3  *
4  * This program is free software; you can redistribute it and/or modify it
5  * under the terms of version 2 of the GNU General Public License as
6  * published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it would be useful, but
9  * WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
11  *
12  * Further, this software is distributed without any warranty that it is
13  * free of the rightful claim of any third person regarding infringement
14  * or the like.  Any license provided herein, whether implied or
15  * otherwise, applies only to this software file.  Patent licenses, if
16  * any, provided herein do not apply to combinations of this program with
17  * other software, or any other product whatsoever.
18  *
19  * You should have received a copy of the GNU General Public License along
20  * with this program; if not, write the Free Software Foundation, Inc., 59
21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
22  *
23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24  * Mountain View, CA  94043, or:
25  *
26  * http://www.sgi.com
27  *
28  * For further information regarding this notice, see:
29  *
30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
31  */
32
33 /*
34  * This file contains common code for the space manager's btree implementations.
35  */
36
37 #include "xfs.h"
38
39 #include "xfs_macros.h"
40 #include "xfs_types.h"
41 #include "xfs_inum.h"
42 #include "xfs_log.h"
43 #include "xfs_trans.h"
44 #include "xfs_sb.h"
45 #include "xfs_ag.h"
46 #include "xfs_dir.h"
47 #include "xfs_dir2.h"
48 #include "xfs_dmapi.h"
49 #include "xfs_mount.h"
50 #include "xfs_alloc_btree.h"
51 #include "xfs_bmap_btree.h"
52 #include "xfs_ialloc_btree.h"
53 #include "xfs_btree.h"
54 #include "xfs_ialloc.h"
55 #include "xfs_attr_sf.h"
56 #include "xfs_dir_sf.h"
57 #include "xfs_dir2_sf.h"
58 #include "xfs_dinode.h"
59 #include "xfs_inode.h"
60 #include "xfs_bit.h"
61 #include "xfs_error.h"
62
63 /*
64  * Cursor allocation zone.
65  */
66 kmem_zone_t     *xfs_btree_cur_zone;
67
68 /*
69  * Btree magic numbers.
70  */
71 const __uint32_t xfs_magics[XFS_BTNUM_MAX] =
72 {
73         XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC
74 };
75
76 /*
77  * Prototypes for internal routines.
78  */
79
80 /*
81  * Checking routine: return maxrecs for the block.
82  */
83 STATIC int                              /* number of records fitting in block */
84 xfs_btree_maxrecs(
85         xfs_btree_cur_t         *cur,   /* btree cursor */
86         xfs_btree_block_t       *block);/* generic btree block pointer */
87
88 /*
89  * Internal routines.
90  */
91
92 /*
93  * Retrieve the block pointer from the cursor at the given level.
94  * This may be a bmap btree root or from a buffer.
95  */
96 STATIC xfs_btree_block_t *                      /* generic btree block pointer */
97 xfs_btree_get_block(
98         xfs_btree_cur_t         *cur,   /* btree cursor */
99         int                     level,  /* level in btree */
100         struct xfs_buf          **bpp); /* buffer containing the block */
101
102 /*
103  * Checking routine: return maxrecs for the block.
104  */
105 STATIC int                              /* number of records fitting in block */
106 xfs_btree_maxrecs(
107         xfs_btree_cur_t         *cur,   /* btree cursor */
108         xfs_btree_block_t       *block) /* generic btree block pointer */
109 {
110         switch (cur->bc_btnum) {
111         case XFS_BTNUM_BNO:
112         case XFS_BTNUM_CNT:
113                 return (int)XFS_ALLOC_BLOCK_MAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
114         case XFS_BTNUM_BMAP:
115                 return (int)XFS_BMAP_BLOCK_IMAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
116         case XFS_BTNUM_INO:
117                 return (int)XFS_INOBT_BLOCK_MAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
118         default:
119                 ASSERT(0);
120                 return 0;
121         }
122 }
123
124 /*
125  * External routines.
126  */
127
128 #ifdef DEBUG
129 /*
130  * Debug routine: check that block header is ok.
131  */
132 void
133 xfs_btree_check_block(
134         xfs_btree_cur_t         *cur,   /* btree cursor */
135         xfs_btree_block_t       *block, /* generic btree block pointer */
136         int                     level,  /* level of the btree block */
137         xfs_buf_t               *bp)    /* buffer containing block, if any */
138 {
139         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
140                 xfs_btree_check_lblock(cur, (xfs_btree_lblock_t *)block, level,
141                         bp);
142         else
143                 xfs_btree_check_sblock(cur, (xfs_btree_sblock_t *)block, level,
144                         bp);
145 }
146
147 /*
148  * Debug routine: check that keys are in the right order.
149  */
150 void
151 xfs_btree_check_key(
152         xfs_btnum_t     btnum,          /* btree identifier */
153         void            *ak1,           /* pointer to left (lower) key */
154         void            *ak2)           /* pointer to right (higher) key */
155 {
156         switch (btnum) {
157         case XFS_BTNUM_BNO: {
158                 xfs_alloc_key_t *k1;
159                 xfs_alloc_key_t *k2;
160
161                 k1 = ak1;
162                 k2 = ak2;
163                 ASSERT(INT_GET(k1->ar_startblock, ARCH_CONVERT) < INT_GET(k2->ar_startblock, ARCH_CONVERT));
164                 break;
165             }
166         case XFS_BTNUM_CNT: {
167                 xfs_alloc_key_t *k1;
168                 xfs_alloc_key_t *k2;
169
170                 k1 = ak1;
171                 k2 = ak2;
172                 ASSERT(INT_GET(k1->ar_blockcount, ARCH_CONVERT) < INT_GET(k2->ar_blockcount, ARCH_CONVERT) ||
173                        (INT_GET(k1->ar_blockcount, ARCH_CONVERT) == INT_GET(k2->ar_blockcount, ARCH_CONVERT) &&
174                         INT_GET(k1->ar_startblock, ARCH_CONVERT) < INT_GET(k2->ar_startblock, ARCH_CONVERT)));
175                 break;
176             }
177         case XFS_BTNUM_BMAP: {
178                 xfs_bmbt_key_t  *k1;
179                 xfs_bmbt_key_t  *k2;
180
181                 k1 = ak1;
182                 k2 = ak2;
183                 ASSERT(INT_GET(k1->br_startoff, ARCH_CONVERT) < INT_GET(k2->br_startoff, ARCH_CONVERT));
184                 break;
185             }
186         case XFS_BTNUM_INO: {
187                 xfs_inobt_key_t *k1;
188                 xfs_inobt_key_t *k2;
189
190                 k1 = ak1;
191                 k2 = ak2;
192                 ASSERT(INT_GET(k1->ir_startino, ARCH_CONVERT) < INT_GET(k2->ir_startino, ARCH_CONVERT));
193                 break;
194             }
195         default:
196                 ASSERT(0);
197         }
198 }
199 #endif  /* DEBUG */
200
201 /*
202  * Checking routine: check that long form block header is ok.
203  */
204 /* ARGSUSED */
205 int                                     /* error (0 or EFSCORRUPTED) */
206 xfs_btree_check_lblock(
207         xfs_btree_cur_t         *cur,   /* btree cursor */
208         xfs_btree_lblock_t      *block, /* btree long form block pointer */
209         int                     level,  /* level of the btree block */
210         xfs_buf_t               *bp)    /* buffer for block, if any */
211 {
212         int                     lblock_ok; /* block passes checks */
213         xfs_mount_t             *mp;    /* file system mount point */
214
215         mp = cur->bc_mp;
216         lblock_ok =
217                 INT_GET(block->bb_magic, ARCH_CONVERT) == xfs_magics[cur->bc_btnum] &&
218                 INT_GET(block->bb_level, ARCH_CONVERT) == level &&
219                 INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
220                         xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
221                 block->bb_leftsib &&
222                 (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO ||
223                  XFS_FSB_SANITY_CHECK(mp, INT_GET(block->bb_leftsib, ARCH_CONVERT))) &&
224                 block->bb_rightsib &&
225                 (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO ||
226                  XFS_FSB_SANITY_CHECK(mp, INT_GET(block->bb_rightsib, ARCH_CONVERT)));
227         if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK,
228                         XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
229                 if (bp)
230                         xfs_buftrace("LBTREE ERROR", bp);
231                 XFS_ERROR_REPORT("xfs_btree_check_lblock", XFS_ERRLEVEL_LOW,
232                                  mp);
233                 return XFS_ERROR(EFSCORRUPTED);
234         }
235         return 0;
236 }
237
238 /*
239  * Checking routine: check that (long) pointer is ok.
240  */
241 int                                     /* error (0 or EFSCORRUPTED) */
242 xfs_btree_check_lptr(
243         xfs_btree_cur_t *cur,           /* btree cursor */
244         xfs_dfsbno_t    ptr,            /* btree block disk address */
245         int             level)          /* btree block level */
246 {
247         xfs_mount_t     *mp;            /* file system mount point */
248
249         mp = cur->bc_mp;
250         XFS_WANT_CORRUPTED_RETURN(
251                 level > 0 &&
252                 ptr != NULLDFSBNO &&
253                 XFS_FSB_SANITY_CHECK(mp, ptr));
254         return 0;
255 }
256
257 #ifdef DEBUG
258 /*
259  * Debug routine: check that records are in the right order.
260  */
261 void
262 xfs_btree_check_rec(
263         xfs_btnum_t     btnum,          /* btree identifier */
264         void            *ar1,           /* pointer to left (lower) record */
265         void            *ar2)           /* pointer to right (higher) record */
266 {
267         switch (btnum) {
268         case XFS_BTNUM_BNO: {
269                 xfs_alloc_rec_t *r1;
270                 xfs_alloc_rec_t *r2;
271
272                 r1 = ar1;
273                 r2 = ar2;
274                 ASSERT(INT_GET(r1->ar_startblock, ARCH_CONVERT) + INT_GET(r1->ar_blockcount, ARCH_CONVERT) <=
275                        INT_GET(r2->ar_startblock, ARCH_CONVERT));
276                 break;
277             }
278         case XFS_BTNUM_CNT: {
279                 xfs_alloc_rec_t *r1;
280                 xfs_alloc_rec_t *r2;
281
282                 r1 = ar1;
283                 r2 = ar2;
284                 ASSERT(INT_GET(r1->ar_blockcount, ARCH_CONVERT) < INT_GET(r2->ar_blockcount, ARCH_CONVERT) ||
285                        (INT_GET(r1->ar_blockcount, ARCH_CONVERT) == INT_GET(r2->ar_blockcount, ARCH_CONVERT) &&
286                         INT_GET(r1->ar_startblock, ARCH_CONVERT) < INT_GET(r2->ar_startblock, ARCH_CONVERT)));
287                 break;
288             }
289         case XFS_BTNUM_BMAP: {
290                 xfs_bmbt_rec_t  *r1;
291                 xfs_bmbt_rec_t  *r2;
292
293                 r1 = ar1;
294                 r2 = ar2;
295                 ASSERT(xfs_bmbt_disk_get_startoff(r1) +
296                        xfs_bmbt_disk_get_blockcount(r1) <=
297                        xfs_bmbt_disk_get_startoff(r2));
298                 break;
299             }
300         case XFS_BTNUM_INO: {
301                 xfs_inobt_rec_t *r1;
302                 xfs_inobt_rec_t *r2;
303
304                 r1 = ar1;
305                 r2 = ar2;
306                 ASSERT(INT_GET(r1->ir_startino, ARCH_CONVERT) + XFS_INODES_PER_CHUNK <=
307                        INT_GET(r2->ir_startino, ARCH_CONVERT));
308                 break;
309             }
310         default:
311                 ASSERT(0);
312         }
313 }
314 #endif  /* DEBUG */
315
316 /*
317  * Checking routine: check that block header is ok.
318  */
319 /* ARGSUSED */
320 int                                     /* error (0 or EFSCORRUPTED) */
321 xfs_btree_check_sblock(
322         xfs_btree_cur_t         *cur,   /* btree cursor */
323         xfs_btree_sblock_t      *block, /* btree short form block pointer */
324         int                     level,  /* level of the btree block */
325         xfs_buf_t               *bp)    /* buffer containing block */
326 {
327         xfs_buf_t               *agbp;  /* buffer for ag. freespace struct */
328         xfs_agf_t               *agf;   /* ag. freespace structure */
329         xfs_agblock_t           agflen; /* native ag. freespace length */
330         int                     sblock_ok; /* block passes checks */
331
332         agbp = cur->bc_private.a.agbp;
333         agf = XFS_BUF_TO_AGF(agbp);
334         agflen = INT_GET(agf->agf_length, ARCH_CONVERT);
335         sblock_ok =
336                 INT_GET(block->bb_magic, ARCH_CONVERT) == xfs_magics[cur->bc_btnum] &&
337                 INT_GET(block->bb_level, ARCH_CONVERT) == level &&
338                 INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
339                         xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
340                 (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK ||
341                  INT_GET(block->bb_leftsib, ARCH_CONVERT) < agflen) &&
342                 block->bb_leftsib &&
343                 (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK ||
344                  INT_GET(block->bb_rightsib, ARCH_CONVERT) < agflen) &&
345                 block->bb_rightsib;
346         if (unlikely(XFS_TEST_ERROR(!sblock_ok, cur->bc_mp,
347                         XFS_ERRTAG_BTREE_CHECK_SBLOCK,
348                         XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
349                 if (bp)
350                         xfs_buftrace("SBTREE ERROR", bp);
351                 XFS_ERROR_REPORT("xfs_btree_check_sblock", XFS_ERRLEVEL_LOW,
352                                  cur->bc_mp);
353                 return XFS_ERROR(EFSCORRUPTED);
354         }
355         return 0;
356 }
357
358 /*
359  * Checking routine: check that (short) pointer is ok.
360  */
361 int                                     /* error (0 or EFSCORRUPTED) */
362 xfs_btree_check_sptr(
363         xfs_btree_cur_t *cur,           /* btree cursor */
364         xfs_agblock_t   ptr,            /* btree block disk address */
365         int             level)          /* btree block level */
366 {
367         xfs_buf_t       *agbp;          /* buffer for ag. freespace struct */
368         xfs_agf_t       *agf;           /* ag. freespace structure */
369
370         agbp = cur->bc_private.a.agbp;
371         agf = XFS_BUF_TO_AGF(agbp);
372         XFS_WANT_CORRUPTED_RETURN(
373                 level > 0 &&
374                 ptr != NULLAGBLOCK && ptr != 0 &&
375                 ptr < INT_GET(agf->agf_length, ARCH_CONVERT));
376         return 0;
377 }
378
379 /*
380  * Delete the btree cursor.
381  */
382 void
383 xfs_btree_del_cursor(
384         xfs_btree_cur_t *cur,           /* btree cursor */
385         int             error)          /* del because of error */
386 {
387         int             i;              /* btree level */
388
389         /*
390          * Clear the buffer pointers, and release the buffers.
391          * If we're doing this in the face of an error, we
392          * need to make sure to inspect all of the entries
393          * in the bc_bufs array for buffers to be unlocked.
394          * This is because some of the btree code works from
395          * level n down to 0, and if we get an error along
396          * the way we won't have initialized all the entries
397          * down to 0.
398          */
399         for (i = 0; i < cur->bc_nlevels; i++) {
400                 if (cur->bc_bufs[i])
401                         xfs_btree_setbuf(cur, i, NULL);
402                 else if (!error)
403                         break;
404         }
405         /*
406          * Can't free a bmap cursor without having dealt with the
407          * allocated indirect blocks' accounting.
408          */
409         ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
410                cur->bc_private.b.allocated == 0);
411         /*
412          * Free the cursor.
413          */
414         kmem_zone_free(xfs_btree_cur_zone, cur);
415 }
416
417 /*
418  * Duplicate the btree cursor.
419  * Allocate a new one, copy the record, re-get the buffers.
420  */
421 int                                     /* error */
422 xfs_btree_dup_cursor(
423         xfs_btree_cur_t *cur,           /* input cursor */
424         xfs_btree_cur_t **ncur)         /* output cursor */
425 {
426         xfs_buf_t       *bp;            /* btree block's buffer pointer */
427         int             error;          /* error return value */
428         int             i;              /* level number of btree block */
429         xfs_mount_t     *mp;            /* mount structure for filesystem */
430         xfs_btree_cur_t *new;           /* new cursor value */
431         xfs_trans_t     *tp;            /* transaction pointer, can be NULL */
432
433         tp = cur->bc_tp;
434         mp = cur->bc_mp;
435         /*
436          * Allocate a new cursor like the old one.
437          */
438         new = xfs_btree_init_cursor(mp, tp, cur->bc_private.a.agbp,
439                 cur->bc_private.a.agno, cur->bc_btnum, cur->bc_private.b.ip,
440                 cur->bc_private.b.whichfork);
441         /*
442          * Copy the record currently in the cursor.
443          */
444         new->bc_rec = cur->bc_rec;
445         /*
446          * For each level current, re-get the buffer and copy the ptr value.
447          */
448         for (i = 0; i < new->bc_nlevels; i++) {
449                 new->bc_ptrs[i] = cur->bc_ptrs[i];
450                 new->bc_ra[i] = cur->bc_ra[i];
451                 if ((bp = cur->bc_bufs[i])) {
452                         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
453                                 XFS_BUF_ADDR(bp), mp->m_bsize, 0, &bp))) {
454                                 xfs_btree_del_cursor(new, error);
455                                 *ncur = NULL;
456                                 return error;
457                         }
458                         new->bc_bufs[i] = bp;
459                         ASSERT(bp);
460                         ASSERT(!XFS_BUF_GETERROR(bp));
461                 } else
462                         new->bc_bufs[i] = NULL;
463         }
464         /*
465          * For bmap btrees, copy the firstblock, flist, and flags values,
466          * since init cursor doesn't get them.
467          */
468         if (new->bc_btnum == XFS_BTNUM_BMAP) {
469                 new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
470                 new->bc_private.b.flist = cur->bc_private.b.flist;
471                 new->bc_private.b.flags = cur->bc_private.b.flags;
472         }
473         *ncur = new;
474         return 0;
475 }
476
477 /*
478  * Change the cursor to point to the first record at the given level.
479  * Other levels are unaffected.
480  */
481 int                                     /* success=1, failure=0 */
482 xfs_btree_firstrec(
483         xfs_btree_cur_t         *cur,   /* btree cursor */
484         int                     level)  /* level to change */
485 {
486         xfs_btree_block_t       *block; /* generic btree block pointer */
487         xfs_buf_t               *bp;    /* buffer containing block */
488
489         /*
490          * Get the block pointer for this level.
491          */
492         block = xfs_btree_get_block(cur, level, &bp);
493         xfs_btree_check_block(cur, block, level, bp);
494         /*
495          * It's empty, there is no such record.
496          */
497         if (!block->bb_h.bb_numrecs)
498                 return 0;
499         /*
500          * Set the ptr value to 1, that's the first record/key.
501          */
502         cur->bc_ptrs[level] = 1;
503         return 1;
504 }
505
506 /*
507  * Retrieve the block pointer from the cursor at the given level.
508  * This may be a bmap btree root or from a buffer.
509  */
510 STATIC xfs_btree_block_t *              /* generic btree block pointer */
511 xfs_btree_get_block(
512         xfs_btree_cur_t         *cur,   /* btree cursor */
513         int                     level,  /* level in btree */
514         xfs_buf_t               **bpp)  /* buffer containing the block */
515 {
516         xfs_btree_block_t       *block; /* return value */
517         xfs_buf_t               *bp;    /* return buffer */
518         xfs_ifork_t             *ifp;   /* inode fork pointer */
519         int                     whichfork; /* data or attr fork */
520
521         if (cur->bc_btnum == XFS_BTNUM_BMAP && level == cur->bc_nlevels - 1) {
522                 whichfork = cur->bc_private.b.whichfork;
523                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, whichfork);
524                 block = (xfs_btree_block_t *)ifp->if_broot;
525                 bp = NULL;
526         } else {
527                 bp = cur->bc_bufs[level];
528                 block = XFS_BUF_TO_BLOCK(bp);
529         }
530         ASSERT(block != NULL);
531         *bpp = bp;
532         return block;
533 }
534
535 /*
536  * Get a buffer for the block, return it with no data read.
537  * Long-form addressing.
538  */
539 xfs_buf_t *                             /* buffer for fsbno */
540 xfs_btree_get_bufl(
541         xfs_mount_t     *mp,            /* file system mount point */
542         xfs_trans_t     *tp,            /* transaction pointer */
543         xfs_fsblock_t   fsbno,          /* file system block number */
544         uint            lock)           /* lock flags for get_buf */
545 {
546         xfs_buf_t       *bp;            /* buffer pointer (return value) */
547         xfs_daddr_t             d;              /* real disk block address */
548
549         ASSERT(fsbno != NULLFSBLOCK);
550         d = XFS_FSB_TO_DADDR(mp, fsbno);
551         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
552         ASSERT(bp);
553         ASSERT(!XFS_BUF_GETERROR(bp));
554         return bp;
555 }
556
557 /*
558  * Get a buffer for the block, return it with no data read.
559  * Short-form addressing.
560  */
561 xfs_buf_t *                             /* buffer for agno/agbno */
562 xfs_btree_get_bufs(
563         xfs_mount_t     *mp,            /* file system mount point */
564         xfs_trans_t     *tp,            /* transaction pointer */
565         xfs_agnumber_t  agno,           /* allocation group number */
566         xfs_agblock_t   agbno,          /* allocation group block number */
567         uint            lock)           /* lock flags for get_buf */
568 {
569         xfs_buf_t       *bp;            /* buffer pointer (return value) */
570         xfs_daddr_t             d;              /* real disk block address */
571
572         ASSERT(agno != NULLAGNUMBER);
573         ASSERT(agbno != NULLAGBLOCK);
574         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
575         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
576         ASSERT(bp);
577         ASSERT(!XFS_BUF_GETERROR(bp));
578         return bp;
579 }
580
581 /*
582  * Allocate a new btree cursor.
583  * The cursor is either for allocation (A) or bmap (B) or inodes (I).
584  */
585 xfs_btree_cur_t *                       /* new btree cursor */
586 xfs_btree_init_cursor(
587         xfs_mount_t     *mp,            /* file system mount point */
588         xfs_trans_t     *tp,            /* transaction pointer */
589         xfs_buf_t       *agbp,          /* (A only) buffer for agf structure */
590                                         /* (I only) buffer for agi structure */
591         xfs_agnumber_t  agno,           /* (AI only) allocation group number */
592         xfs_btnum_t     btnum,          /* btree identifier */
593         xfs_inode_t     *ip,            /* (B only) inode owning the btree */
594         int             whichfork)      /* (B only) data or attr fork */
595 {
596         xfs_agf_t       *agf;           /* (A) allocation group freespace */
597         xfs_agi_t       *agi;           /* (I) allocation group inodespace */
598         xfs_btree_cur_t *cur;           /* return value */
599         xfs_ifork_t     *ifp;           /* (I) inode fork pointer */
600         int             nlevels=0;      /* number of levels in the btree */
601
602         ASSERT(xfs_btree_cur_zone != NULL);
603         /*
604          * Allocate a new cursor.
605          */
606         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
607         /*
608          * Deduce the number of btree levels from the arguments.
609          */
610         switch (btnum) {
611         case XFS_BTNUM_BNO:
612         case XFS_BTNUM_CNT:
613                 agf = XFS_BUF_TO_AGF(agbp);
614                 nlevels = INT_GET(agf->agf_levels[btnum], ARCH_CONVERT);
615                 break;
616         case XFS_BTNUM_BMAP:
617                 ifp = XFS_IFORK_PTR(ip, whichfork);
618                 nlevels = INT_GET(ifp->if_broot->bb_level, ARCH_CONVERT) + 1;
619                 break;
620         case XFS_BTNUM_INO:
621                 agi = XFS_BUF_TO_AGI(agbp);
622                 nlevels = INT_GET(agi->agi_level, ARCH_CONVERT);
623                 break;
624         default:
625                 ASSERT(0);
626         }
627         /*
628          * Fill in the common fields.
629          */
630         cur->bc_tp = tp;
631         cur->bc_mp = mp;
632         cur->bc_nlevels = nlevels;
633         cur->bc_btnum = btnum;
634         cur->bc_blocklog = mp->m_sb.sb_blocklog;
635         /*
636          * Fill in private fields.
637          */
638         switch (btnum) {
639         case XFS_BTNUM_BNO:
640         case XFS_BTNUM_CNT:
641                 /*
642                  * Allocation btree fields.
643                  */
644                 cur->bc_private.a.agbp = agbp;
645                 cur->bc_private.a.agno = agno;
646                 break;
647         case XFS_BTNUM_BMAP:
648                 /*
649                  * Bmap btree fields.
650                  */
651                 cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
652                 cur->bc_private.b.ip = ip;
653                 cur->bc_private.b.firstblock = NULLFSBLOCK;
654                 cur->bc_private.b.flist = NULL;
655                 cur->bc_private.b.allocated = 0;
656                 cur->bc_private.b.flags = 0;
657                 cur->bc_private.b.whichfork = whichfork;
658                 break;
659         case XFS_BTNUM_INO:
660                 /*
661                  * Inode allocation btree fields.
662                  */
663                 cur->bc_private.i.agbp = agbp;
664                 cur->bc_private.i.agno = agno;
665                 break;
666         default:
667                 ASSERT(0);
668         }
669         return cur;
670 }
671
672 /*
673  * Check for the cursor referring to the last block at the given level.
674  */
675 int                                     /* 1=is last block, 0=not last block */
676 xfs_btree_islastblock(
677         xfs_btree_cur_t         *cur,   /* btree cursor */
678         int                     level)  /* level to check */
679 {
680         xfs_btree_block_t       *block; /* generic btree block pointer */
681         xfs_buf_t               *bp;    /* buffer containing block */
682
683         block = xfs_btree_get_block(cur, level, &bp);
684         xfs_btree_check_block(cur, block, level, bp);
685         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
686                 return INT_GET(block->bb_u.l.bb_rightsib, ARCH_CONVERT) == NULLDFSBNO;
687         else
688                 return INT_GET(block->bb_u.s.bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK;
689 }
690
691 /*
692  * Change the cursor to point to the last record in the current block
693  * at the given level.  Other levels are unaffected.
694  */
695 int                                     /* success=1, failure=0 */
696 xfs_btree_lastrec(
697         xfs_btree_cur_t         *cur,   /* btree cursor */
698         int                     level)  /* level to change */
699 {
700         xfs_btree_block_t       *block; /* generic btree block pointer */
701         xfs_buf_t               *bp;    /* buffer containing block */
702
703         /*
704          * Get the block pointer for this level.
705          */
706         block = xfs_btree_get_block(cur, level, &bp);
707         xfs_btree_check_block(cur, block, level, bp);
708         /*
709          * It's empty, there is no such record.
710          */
711         if (!block->bb_h.bb_numrecs)
712                 return 0;
713         /*
714          * Set the ptr value to numrecs, that's the last record/key.
715          */
716         cur->bc_ptrs[level] = INT_GET(block->bb_h.bb_numrecs, ARCH_CONVERT);
717         return 1;
718 }
719
720 /*
721  * Compute first and last byte offsets for the fields given.
722  * Interprets the offsets table, which contains struct field offsets.
723  */
724 void
725 xfs_btree_offsets(
726         __int64_t       fields,         /* bitmask of fields */
727         const short     *offsets,       /* table of field offsets */
728         int             nbits,          /* number of bits to inspect */
729         int             *first,         /* output: first byte offset */
730         int             *last)          /* output: last byte offset */
731 {
732         int             i;              /* current bit number */
733         __int64_t       imask;          /* mask for current bit number */
734
735         ASSERT(fields != 0);
736         /*
737          * Find the lowest bit, so the first byte offset.
738          */
739         for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
740                 if (imask & fields) {
741                         *first = offsets[i];
742                         break;
743                 }
744         }
745         /*
746          * Find the highest bit, so the last byte offset.
747          */
748         for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
749                 if (imask & fields) {
750                         *last = offsets[i + 1] - 1;
751                         break;
752                 }
753         }
754 }
755
756 /*
757  * Get a buffer for the block, return it read in.
758  * Long-form addressing.
759  */
760 int                                     /* error */
761 xfs_btree_read_bufl(
762         xfs_mount_t     *mp,            /* file system mount point */
763         xfs_trans_t     *tp,            /* transaction pointer */
764         xfs_fsblock_t   fsbno,          /* file system block number */
765         uint            lock,           /* lock flags for read_buf */
766         xfs_buf_t       **bpp,          /* buffer for fsbno */
767         int             refval)         /* ref count value for buffer */
768 {
769         xfs_buf_t       *bp;            /* return value */
770         xfs_daddr_t             d;              /* real disk block address */
771         int             error;
772
773         ASSERT(fsbno != NULLFSBLOCK);
774         d = XFS_FSB_TO_DADDR(mp, fsbno);
775         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
776                         mp->m_bsize, lock, &bp))) {
777                 return error;
778         }
779         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
780         if (bp != NULL) {
781                 XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
782         }
783         *bpp = bp;
784         return 0;
785 }
786
787 /*
788  * Get a buffer for the block, return it read in.
789  * Short-form addressing.
790  */
791 int                                     /* error */
792 xfs_btree_read_bufs(
793         xfs_mount_t     *mp,            /* file system mount point */
794         xfs_trans_t     *tp,            /* transaction pointer */
795         xfs_agnumber_t  agno,           /* allocation group number */
796         xfs_agblock_t   agbno,          /* allocation group block number */
797         uint            lock,           /* lock flags for read_buf */
798         xfs_buf_t       **bpp,          /* buffer for agno/agbno */
799         int             refval)         /* ref count value for buffer */
800 {
801         xfs_buf_t       *bp;            /* return value */
802         xfs_daddr_t     d;              /* real disk block address */
803         int             error;
804
805         ASSERT(agno != NULLAGNUMBER);
806         ASSERT(agbno != NULLAGBLOCK);
807         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
808         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
809                                         mp->m_bsize, lock, &bp))) {
810                 return error;
811         }
812         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
813         if (bp != NULL) {
814                 switch (refval) {
815                 case XFS_ALLOC_BTREE_REF:
816                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
817                         break;
818                 case XFS_INO_BTREE_REF:
819                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_INOMAP, refval);
820                         break;
821                 }
822         }
823         *bpp = bp;
824         return 0;
825 }
826
827 /*
828  * Read-ahead the block, don't wait for it, don't return a buffer.
829  * Long-form addressing.
830  */
831 /* ARGSUSED */
832 void
833 xfs_btree_reada_bufl(
834         xfs_mount_t     *mp,            /* file system mount point */
835         xfs_fsblock_t   fsbno,          /* file system block number */
836         xfs_extlen_t    count)          /* count of filesystem blocks */
837 {
838         xfs_daddr_t             d;
839
840         ASSERT(fsbno != NULLFSBLOCK);
841         d = XFS_FSB_TO_DADDR(mp, fsbno);
842         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
843 }
844
845 /*
846  * Read-ahead the block, don't wait for it, don't return a buffer.
847  * Short-form addressing.
848  */
849 /* ARGSUSED */
850 void
851 xfs_btree_reada_bufs(
852         xfs_mount_t     *mp,            /* file system mount point */
853         xfs_agnumber_t  agno,           /* allocation group number */
854         xfs_agblock_t   agbno,          /* allocation group block number */
855         xfs_extlen_t    count)          /* count of filesystem blocks */
856 {
857         xfs_daddr_t             d;
858
859         ASSERT(agno != NULLAGNUMBER);
860         ASSERT(agbno != NULLAGBLOCK);
861         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
862         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
863 }
864
865 /*
866  * Read-ahead btree blocks, at the given level.
867  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
868  */
869 int
870 xfs_btree_readahead_core(
871         xfs_btree_cur_t         *cur,           /* btree cursor */
872         int                     lev,            /* level in btree */
873         int                     lr)             /* left/right bits */
874 {
875         xfs_alloc_block_t       *a;
876         xfs_bmbt_block_t        *b;
877         xfs_inobt_block_t       *i;
878         int                     rval = 0;
879
880         ASSERT(cur->bc_bufs[lev] != NULL);
881         cur->bc_ra[lev] |= lr;
882         switch (cur->bc_btnum) {
883         case XFS_BTNUM_BNO:
884         case XFS_BTNUM_CNT:
885                 a = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]);
886                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(a->bb_leftsib, ARCH_CONVERT) != NULLAGBLOCK) {
887                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
888                                 INT_GET(a->bb_leftsib, ARCH_CONVERT), 1);
889                         rval++;
890                 }
891                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(a->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
892                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
893                                 INT_GET(a->bb_rightsib, ARCH_CONVERT), 1);
894                         rval++;
895                 }
896                 break;
897         case XFS_BTNUM_BMAP:
898                 b = XFS_BUF_TO_BMBT_BLOCK(cur->bc_bufs[lev]);
899                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(b->bb_leftsib, ARCH_CONVERT) != NULLDFSBNO) {
900                         xfs_btree_reada_bufl(cur->bc_mp, INT_GET(b->bb_leftsib, ARCH_CONVERT), 1);
901                         rval++;
902                 }
903                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(b->bb_rightsib, ARCH_CONVERT) != NULLDFSBNO) {
904                         xfs_btree_reada_bufl(cur->bc_mp, INT_GET(b->bb_rightsib, ARCH_CONVERT), 1);
905                         rval++;
906                 }
907                 break;
908         case XFS_BTNUM_INO:
909                 i = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[lev]);
910                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(i->bb_leftsib, ARCH_CONVERT) != NULLAGBLOCK) {
911                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
912                                 INT_GET(i->bb_leftsib, ARCH_CONVERT), 1);
913                         rval++;
914                 }
915                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(i->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
916                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
917                                 INT_GET(i->bb_rightsib, ARCH_CONVERT), 1);
918                         rval++;
919                 }
920                 break;
921         default:
922                 ASSERT(0);
923         }
924         return rval;
925 }
926
927 /*
928  * Set the buffer for level "lev" in the cursor to bp, releasing
929  * any previous buffer.
930  */
931 void
932 xfs_btree_setbuf(
933         xfs_btree_cur_t         *cur,   /* btree cursor */
934         int                     lev,    /* level in btree */
935         xfs_buf_t               *bp)    /* new buffer to set */
936 {
937         xfs_btree_block_t       *b;     /* btree block */
938         xfs_buf_t               *obp;   /* old buffer pointer */
939
940         obp = cur->bc_bufs[lev];
941         if (obp)
942                 xfs_trans_brelse(cur->bc_tp, obp);
943         cur->bc_bufs[lev] = bp;
944         cur->bc_ra[lev] = 0;
945         if (!bp)
946                 return;
947         b = XFS_BUF_TO_BLOCK(bp);
948         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum)) {
949                 if (INT_GET(b->bb_u.l.bb_leftsib, ARCH_CONVERT) == NULLDFSBNO)
950                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
951                 if (INT_GET(b->bb_u.l.bb_rightsib, ARCH_CONVERT) == NULLDFSBNO)
952                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
953         } else {
954                 if (INT_GET(b->bb_u.s.bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK)
955                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
956                 if (INT_GET(b->bb_u.s.bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK)
957                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
958         }
959 }