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