?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 2.6.14.1
[linux/fpc-iii.git] / fs / xfs / xfs_btree.c
blob0cc63d657a14ed2937df63826b3445aac41ef600
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 }
Linux with added FPC-III support