]> git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_btree.c
projects / thirdparty / xfsprogs-dev.git / blob
? search:


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