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