2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
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.
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.
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
20 #include "xfs_types.h"
24 #include "xfs_trans.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_alloc.h"
40 #include "xfs_error.h"
42 STATIC void xfs_inobt_log_block(xfs_trans_t *, xfs_buf_t *, int);
43 STATIC void xfs_inobt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
44 STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
45 STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
46 STATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *);
47 STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *);
48 STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
49 xfs_inobt_key_t *, xfs_btree_cur_t **, int *);
52 * Single level of the xfs_inobt_delete record deletion routine.
53 * Delete record pointed to by cur/level.
54 * Remove the record from its block then rebalance the tree.
55 * Return 0 for error, 1 for done, 2 to go on to the next level.
57 STATIC int /* error */
59 xfs_btree_cur_t *cur, /* btree cursor */
60 int level, /* level removing record from */
61 int *stat) /* fail/done/go-on */
63 xfs_buf_t *agbp; /* buffer for a.g. inode header */
64 xfs_mount_t *mp; /* mount structure */
65 xfs_agi_t *agi; /* allocation group inode header */
66 xfs_inobt_block_t *block; /* btree block record/key lives in */
67 xfs_agblock_t bno; /* btree block number */
68 xfs_buf_t *bp; /* buffer for block */
69 int error; /* error return value */
70 int i; /* loop index */
71 xfs_inobt_key_t key; /* kp points here if block is level 0 */
72 xfs_inobt_key_t *kp = NULL; /* pointer to btree keys */
73 xfs_agblock_t lbno; /* left block's block number */
74 xfs_buf_t *lbp; /* left block's buffer pointer */
75 xfs_inobt_block_t *left; /* left btree block */
76 xfs_inobt_key_t *lkp; /* left block key pointer */
77 xfs_inobt_ptr_t *lpp; /* left block address pointer */
78 int lrecs = 0; /* number of records in left block */
79 xfs_inobt_rec_t *lrp; /* left block record pointer */
80 xfs_inobt_ptr_t *pp = NULL; /* pointer to btree addresses */
81 int ptr; /* index in btree block for this rec */
82 xfs_agblock_t rbno; /* right block's block number */
83 xfs_buf_t *rbp; /* right block's buffer pointer */
84 xfs_inobt_block_t *right; /* right btree block */
85 xfs_inobt_key_t *rkp; /* right block key pointer */
86 xfs_inobt_rec_t *rp; /* pointer to btree records */
87 xfs_inobt_ptr_t *rpp; /* right block address pointer */
88 int rrecs = 0; /* number of records in right block */
90 xfs_inobt_rec_t *rrp; /* right block record pointer */
91 xfs_btree_cur_t *tcur; /* temporary btree cursor */
96 * Get the index of the entry being deleted, check for nothing there.
98 ptr = cur->bc_ptrs[level];
105 * Get the buffer & block containing the record or key/ptr.
107 bp = cur->bc_bufs[level];
108 block = XFS_BUF_TO_INOBT_BLOCK(bp);
110 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
114 * Fail if we're off the end of the block.
117 numrecs = be16_to_cpu(block->bb_numrecs);
123 * It's a nonleaf. Excise the key and ptr being deleted, by
124 * sliding the entries past them down one.
125 * Log the changed areas of the block.
128 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
129 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
131 for (i = ptr; i < numrecs; i++) {
132 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i]), level)))
137 memmove(&kp[ptr - 1], &kp[ptr],
138 (numrecs - ptr) * sizeof(*kp));
139 memmove(&pp[ptr - 1], &pp[ptr],
140 (numrecs - ptr) * sizeof(*kp));
141 xfs_inobt_log_keys(cur, bp, ptr, numrecs - 1);
142 xfs_inobt_log_ptrs(cur, bp, ptr, numrecs - 1);
146 * It's a leaf. Excise the record being deleted, by sliding the
147 * entries past it down one. Log the changed areas of the block.
150 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
152 memmove(&rp[ptr - 1], &rp[ptr],
153 (numrecs - ptr) * sizeof(*rp));
154 xfs_inobt_log_recs(cur, bp, ptr, numrecs - 1);
157 * If it's the first record in the block, we'll need a key
158 * structure to pass up to the next level (updkey).
161 key.ir_startino = rp->ir_startino;
166 * Decrement and log the number of entries in the block.
169 block->bb_numrecs = cpu_to_be16(numrecs);
170 xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
172 * Is this the root level? If so, we're almost done.
174 if (level == cur->bc_nlevels - 1) {
176 * If this is the root level,
177 * and there's only one entry left,
178 * and it's NOT the leaf level,
179 * then we can get rid of this level.
181 if (numrecs == 1 && level > 0) {
182 agbp = cur->bc_private.a.agbp;
183 agi = XFS_BUF_TO_AGI(agbp);
185 * pp is still set to the first pointer in the block.
186 * Make it the new root of the btree.
188 bno = be32_to_cpu(agi->agi_root);
190 be32_add_cpu(&agi->agi_level, -1);
194 if ((error = xfs_free_extent(cur->bc_tp,
195 XFS_AGB_TO_FSB(mp, cur->bc_private.a.agno, bno), 1)))
197 xfs_trans_binval(cur->bc_tp, bp);
198 xfs_ialloc_log_agi(cur->bc_tp, agbp,
199 XFS_AGI_ROOT | XFS_AGI_LEVEL);
201 * Update the cursor so there's one fewer level.
203 cur->bc_bufs[level] = NULL;
205 } else if (level > 0 &&
206 (error = xfs_btree_decrement(cur, level, &i)))
212 * If we deleted the leftmost entry in the block, update the
213 * key values above us in the tree.
215 if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)kp, level + 1)))
218 * If the number of records remaining in the block is at least
219 * the minimum, we're done.
221 if (numrecs >= XFS_INOBT_BLOCK_MINRECS(level, cur)) {
223 (error = xfs_btree_decrement(cur, level, &i)))
229 * Otherwise, we have to move some records around to keep the
230 * tree balanced. Look at the left and right sibling blocks to
231 * see if we can re-balance by moving only one record.
233 rbno = be32_to_cpu(block->bb_rightsib);
234 lbno = be32_to_cpu(block->bb_leftsib);
236 ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
238 * Duplicate the cursor so our btree manipulations here won't
239 * disrupt the next level up.
241 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
244 * If there's a right sibling, see if it's ok to shift an entry
247 if (rbno != NULLAGBLOCK) {
249 * Move the temp cursor to the last entry in the next block.
250 * Actually any entry but the first would suffice.
252 i = xfs_btree_lastrec(tcur, level);
253 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
254 if ((error = xfs_btree_increment(tcur, level, &i)))
256 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
257 i = xfs_btree_lastrec(tcur, level);
258 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
260 * Grab a pointer to the block.
262 rbp = tcur->bc_bufs[level];
263 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
265 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
269 * Grab the current block number, for future use.
271 bno = be32_to_cpu(right->bb_leftsib);
273 * If right block is full enough so that removing one entry
274 * won't make it too empty, and left-shifting an entry out
275 * of right to us works, we're done.
277 if (be16_to_cpu(right->bb_numrecs) - 1 >=
278 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
279 if ((error = xfs_inobt_lshift(tcur, level, &i)))
282 ASSERT(be16_to_cpu(block->bb_numrecs) >=
283 XFS_INOBT_BLOCK_MINRECS(level, cur));
284 xfs_btree_del_cursor(tcur,
287 (error = xfs_btree_decrement(cur, level,
295 * Otherwise, grab the number of records in right for
296 * future reference, and fix up the temp cursor to point
297 * to our block again (last record).
299 rrecs = be16_to_cpu(right->bb_numrecs);
300 if (lbno != NULLAGBLOCK) {
301 xfs_btree_firstrec(tcur, level);
302 if ((error = xfs_btree_decrement(tcur, level, &i)))
307 * If there's a left sibling, see if it's ok to shift an entry
310 if (lbno != NULLAGBLOCK) {
312 * Move the temp cursor to the first entry in the
315 xfs_btree_firstrec(tcur, level);
316 if ((error = xfs_btree_decrement(tcur, level, &i)))
318 xfs_btree_firstrec(tcur, level);
320 * Grab a pointer to the block.
322 lbp = tcur->bc_bufs[level];
323 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
325 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
329 * Grab the current block number, for future use.
331 bno = be32_to_cpu(left->bb_rightsib);
333 * If left block is full enough so that removing one entry
334 * won't make it too empty, and right-shifting an entry out
335 * of left to us works, we're done.
337 if (be16_to_cpu(left->bb_numrecs) - 1 >=
338 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
339 if ((error = xfs_btree_rshift(tcur, level, &i)))
342 ASSERT(be16_to_cpu(block->bb_numrecs) >=
343 XFS_INOBT_BLOCK_MINRECS(level, cur));
344 xfs_btree_del_cursor(tcur,
353 * Otherwise, grab the number of records in right for
356 lrecs = be16_to_cpu(left->bb_numrecs);
359 * Delete the temp cursor, we're done with it.
361 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
363 * If here, we need to do a join to keep the tree balanced.
365 ASSERT(bno != NULLAGBLOCK);
367 * See if we can join with the left neighbor block.
369 if (lbno != NULLAGBLOCK &&
370 lrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
372 * Set "right" to be the starting block,
373 * "left" to be the left neighbor.
377 rrecs = be16_to_cpu(right->bb_numrecs);
379 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
380 cur->bc_private.a.agno, lbno, 0, &lbp,
383 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
384 lrecs = be16_to_cpu(left->bb_numrecs);
385 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
389 * If that won't work, see if we can join with the right neighbor block.
391 else if (rbno != NULLAGBLOCK &&
392 rrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
394 * Set "left" to be the starting block,
395 * "right" to be the right neighbor.
399 lrecs = be16_to_cpu(left->bb_numrecs);
401 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
402 cur->bc_private.a.agno, rbno, 0, &rbp,
405 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
406 rrecs = be16_to_cpu(right->bb_numrecs);
407 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
411 * Otherwise, we can't fix the imbalance.
412 * Just return. This is probably a logic error, but it's not fatal.
415 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i)))
421 * We're now going to join "left" and "right" by moving all the stuff
422 * in "right" to "left" and deleting "right".
426 * It's a non-leaf. Move keys and pointers.
428 lkp = XFS_INOBT_KEY_ADDR(left, lrecs + 1, cur);
429 lpp = XFS_INOBT_PTR_ADDR(left, lrecs + 1, cur);
430 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
431 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
433 for (i = 0; i < rrecs; i++) {
434 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
438 memcpy(lkp, rkp, rrecs * sizeof(*lkp));
439 memcpy(lpp, rpp, rrecs * sizeof(*lpp));
440 xfs_inobt_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
441 xfs_inobt_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
444 * It's a leaf. Move records.
446 lrp = XFS_INOBT_REC_ADDR(left, lrecs + 1, cur);
447 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
448 memcpy(lrp, rrp, rrecs * sizeof(*lrp));
449 xfs_inobt_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
452 * If we joined with the left neighbor, set the buffer in the
453 * cursor to the left block, and fix up the index.
456 xfs_btree_setbuf(cur, level, lbp);
457 cur->bc_ptrs[level] += lrecs;
460 * If we joined with the right neighbor and there's a level above
461 * us, increment the cursor at that level.
463 else if (level + 1 < cur->bc_nlevels &&
464 (error = xfs_btree_increment(cur, level + 1, &i)))
467 * Fix up the number of records in the surviving block.
470 left->bb_numrecs = cpu_to_be16(lrecs);
472 * Fix up the right block pointer in the surviving block, and log it.
474 left->bb_rightsib = right->bb_rightsib;
475 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
477 * If there is a right sibling now, make it point to the
480 if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
481 xfs_inobt_block_t *rrblock;
484 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
485 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
486 &rrbp, XFS_INO_BTREE_REF)))
488 rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp);
489 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
491 rrblock->bb_leftsib = cpu_to_be32(lbno);
492 xfs_inobt_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
495 * Free the deleting block.
497 if ((error = xfs_free_extent(cur->bc_tp, XFS_AGB_TO_FSB(mp,
498 cur->bc_private.a.agno, rbno), 1)))
500 xfs_trans_binval(cur->bc_tp, rbp);
502 * Readjust the ptr at this level if it's not a leaf, since it's
503 * still pointing at the deletion point, which makes the cursor
504 * inconsistent. If this makes the ptr 0, the caller fixes it up.
505 * We can't use decrement because it would change the next level up.
508 cur->bc_ptrs[level]--;
510 * Return value means the next level up has something to do.
516 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
521 * Insert one record/level. Return information to the caller
522 * allowing the next level up to proceed if necessary.
524 STATIC int /* error */
526 xfs_btree_cur_t *cur, /* btree cursor */
527 int level, /* level to insert record at */
528 xfs_agblock_t *bnop, /* i/o: block number inserted */
529 xfs_inobt_rec_t *recp, /* i/o: record data inserted */
530 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
531 int *stat) /* success/failure */
533 xfs_inobt_block_t *block; /* btree block record/key lives in */
534 xfs_buf_t *bp; /* buffer for block */
535 int error; /* error return value */
536 int i; /* loop index */
537 xfs_inobt_key_t key; /* key value being inserted */
538 xfs_inobt_key_t *kp=NULL; /* pointer to btree keys */
539 xfs_agblock_t nbno; /* block number of allocated block */
540 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
541 xfs_inobt_key_t nkey; /* new key value, from split */
542 xfs_inobt_rec_t nrec; /* new record value, for caller */
544 int optr; /* old ptr value */
545 xfs_inobt_ptr_t *pp; /* pointer to btree addresses */
546 int ptr; /* index in btree block for this rec */
547 xfs_inobt_rec_t *rp=NULL; /* pointer to btree records */
550 * GCC doesn't understand the (arguably complex) control flow in
551 * this function and complains about uninitialized structure fields
554 memset(&nrec, 0, sizeof(nrec));
557 * If we made it to the root level, allocate a new root block
560 if (level >= cur->bc_nlevels) {
561 error = xfs_inobt_newroot(cur, &i);
567 * Make a key out of the record data to be inserted, and save it.
569 key.ir_startino = recp->ir_startino;
570 optr = ptr = cur->bc_ptrs[level];
572 * If we're off the left edge, return failure.
579 * Get pointers to the btree buffer and block.
581 bp = cur->bc_bufs[level];
582 block = XFS_BUF_TO_INOBT_BLOCK(bp);
583 numrecs = be16_to_cpu(block->bb_numrecs);
585 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
588 * Check that the new entry is being inserted in the right place.
590 if (ptr <= numrecs) {
592 rp = XFS_INOBT_REC_ADDR(block, ptr, cur);
593 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
595 kp = XFS_INOBT_KEY_ADDR(block, ptr, cur);
596 xfs_btree_check_key(cur->bc_btnum, &key, kp);
603 * If the block is full, we can't insert the new entry until we
604 * make the block un-full.
606 if (numrecs == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
608 * First, try shifting an entry to the right neighbor.
610 if ((error = xfs_btree_rshift(cur, level, &i)))
616 * Next, try shifting an entry to the left neighbor.
619 if ((error = xfs_inobt_lshift(cur, level, &i)))
622 optr = ptr = cur->bc_ptrs[level];
625 * Next, try splitting the current block
626 * in half. If this works we have to
627 * re-set our variables because
628 * we could be in a different block now.
630 if ((error = xfs_inobt_split(cur, level, &nbno,
634 bp = cur->bc_bufs[level];
635 block = XFS_BUF_TO_INOBT_BLOCK(bp);
637 if ((error = xfs_btree_check_sblock(cur,
641 ptr = cur->bc_ptrs[level];
642 nrec.ir_startino = nkey.ir_startino;
645 * Otherwise the insert fails.
654 * At this point we know there's room for our new entry in the block
657 numrecs = be16_to_cpu(block->bb_numrecs);
660 * It's a non-leaf entry. Make a hole for the new data
661 * in the key and ptr regions of the block.
663 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
664 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
666 for (i = numrecs; i >= ptr; i--) {
667 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
671 memmove(&kp[ptr], &kp[ptr - 1],
672 (numrecs - ptr + 1) * sizeof(*kp));
673 memmove(&pp[ptr], &pp[ptr - 1],
674 (numrecs - ptr + 1) * sizeof(*pp));
676 * Now stuff the new data in, bump numrecs and log the new data.
679 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
683 pp[ptr - 1] = cpu_to_be32(*bnop);
685 block->bb_numrecs = cpu_to_be16(numrecs);
686 xfs_inobt_log_keys(cur, bp, ptr, numrecs);
687 xfs_inobt_log_ptrs(cur, bp, ptr, numrecs);
690 * It's a leaf entry. Make a hole for the new record.
692 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
693 memmove(&rp[ptr], &rp[ptr - 1],
694 (numrecs - ptr + 1) * sizeof(*rp));
696 * Now stuff the new record in, bump numrecs
697 * and log the new data.
701 block->bb_numrecs = cpu_to_be16(numrecs);
702 xfs_inobt_log_recs(cur, bp, ptr, numrecs);
705 * Log the new number of records in the btree header.
707 xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
710 * Check that the key/record is in the right place, now.
714 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
717 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
722 * If we inserted at the start of a block, update the parents' keys.
724 if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1)))
727 * Return the new block number, if any.
728 * If there is one, give back a record value and a cursor too.
731 if (nbno != NULLAGBLOCK) {
740 * Log header fields from a btree block.
744 xfs_trans_t *tp, /* transaction pointer */
745 xfs_buf_t *bp, /* buffer containing btree block */
746 int fields) /* mask of fields: XFS_BB_... */
748 int first; /* first byte offset logged */
749 int last; /* last byte offset logged */
750 static const short offsets[] = { /* table of offsets */
751 offsetof(xfs_inobt_block_t, bb_magic),
752 offsetof(xfs_inobt_block_t, bb_level),
753 offsetof(xfs_inobt_block_t, bb_numrecs),
754 offsetof(xfs_inobt_block_t, bb_leftsib),
755 offsetof(xfs_inobt_block_t, bb_rightsib),
756 sizeof(xfs_inobt_block_t)
759 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
760 xfs_trans_log_buf(tp, bp, first, last);
764 * Log keys from a btree block (nonleaf).
768 xfs_btree_cur_t *cur, /* btree cursor */
769 xfs_buf_t *bp, /* buffer containing btree block */
770 int kfirst, /* index of first key to log */
771 int klast) /* index of last key to log */
773 xfs_inobt_block_t *block; /* btree block to log from */
774 int first; /* first byte offset logged */
775 xfs_inobt_key_t *kp; /* key pointer in btree block */
776 int last; /* last byte offset logged */
778 block = XFS_BUF_TO_INOBT_BLOCK(bp);
779 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
780 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
781 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
782 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
786 * Log block pointer fields from a btree block (nonleaf).
790 xfs_btree_cur_t *cur, /* btree cursor */
791 xfs_buf_t *bp, /* buffer containing btree block */
792 int pfirst, /* index of first pointer to log */
793 int plast) /* index of last pointer to log */
795 xfs_inobt_block_t *block; /* btree block to log from */
796 int first; /* first byte offset logged */
797 int last; /* last byte offset logged */
798 xfs_inobt_ptr_t *pp; /* block-pointer pointer in btree blk */
800 block = XFS_BUF_TO_INOBT_BLOCK(bp);
801 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
802 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
803 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
804 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
808 * Log records from a btree block (leaf).
812 xfs_btree_cur_t *cur, /* btree cursor */
813 xfs_buf_t *bp, /* buffer containing btree block */
814 int rfirst, /* index of first record to log */
815 int rlast) /* index of last record to log */
817 xfs_inobt_block_t *block; /* btree block to log from */
818 int first; /* first byte offset logged */
819 int last; /* last byte offset logged */
820 xfs_inobt_rec_t *rp; /* record pointer for btree block */
822 block = XFS_BUF_TO_INOBT_BLOCK(bp);
823 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
824 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
825 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
826 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
830 * Move 1 record left from cur/level if possible.
831 * Update cur to reflect the new path.
833 STATIC int /* error */
835 xfs_btree_cur_t *cur, /* btree cursor */
836 int level, /* level to shift record on */
837 int *stat) /* success/failure */
839 int error; /* error return value */
841 int i; /* loop index */
843 xfs_inobt_key_t key; /* key value for leaf level upward */
844 xfs_buf_t *lbp; /* buffer for left neighbor block */
845 xfs_inobt_block_t *left; /* left neighbor btree block */
846 xfs_inobt_key_t *lkp=NULL; /* key pointer for left block */
847 xfs_inobt_ptr_t *lpp; /* address pointer for left block */
848 xfs_inobt_rec_t *lrp=NULL; /* record pointer for left block */
849 int nrec; /* new number of left block entries */
850 xfs_buf_t *rbp; /* buffer for right (current) block */
851 xfs_inobt_block_t *right; /* right (current) btree block */
852 xfs_inobt_key_t *rkp=NULL; /* key pointer for right block */
853 xfs_inobt_ptr_t *rpp=NULL; /* address pointer for right block */
854 xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */
857 * Set up variables for this block as "right".
859 rbp = cur->bc_bufs[level];
860 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
862 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
866 * If we've got no left sibling then we can't shift an entry left.
868 if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
873 * If the cursor entry is the one that would be moved, don't
874 * do it... it's too complicated.
876 if (cur->bc_ptrs[level] <= 1) {
881 * Set up the left neighbor as "left".
883 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
884 cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
885 0, &lbp, XFS_INO_BTREE_REF)))
887 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
888 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
891 * If it's full, it can't take another entry.
893 if (be16_to_cpu(left->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
897 nrec = be16_to_cpu(left->bb_numrecs) + 1;
899 * If non-leaf, copy a key and a ptr to the left block.
902 lkp = XFS_INOBT_KEY_ADDR(left, nrec, cur);
903 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
905 xfs_inobt_log_keys(cur, lbp, nrec, nrec);
906 lpp = XFS_INOBT_PTR_ADDR(left, nrec, cur);
907 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
909 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
913 xfs_inobt_log_ptrs(cur, lbp, nrec, nrec);
916 * If leaf, copy a record to the left block.
919 lrp = XFS_INOBT_REC_ADDR(left, nrec, cur);
920 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
922 xfs_inobt_log_recs(cur, lbp, nrec, nrec);
925 * Bump and log left's numrecs, decrement and log right's numrecs.
927 be16_add_cpu(&left->bb_numrecs, 1);
928 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
931 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
933 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
935 be16_add_cpu(&right->bb_numrecs, -1);
936 xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
938 * Slide the contents of right down one entry.
942 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
943 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
948 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
949 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
950 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
951 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
953 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
954 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
955 key.ir_startino = rrp->ir_startino;
959 * Update the parent key values of right.
961 if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1)))
964 * Slide the cursor value left one.
966 cur->bc_ptrs[level]--;
972 * Allocate a new root block, fill it in.
974 STATIC int /* error */
976 xfs_btree_cur_t *cur, /* btree cursor */
977 int *stat) /* success/failure */
979 xfs_agi_t *agi; /* a.g. inode header */
980 xfs_alloc_arg_t args; /* allocation argument structure */
981 xfs_inobt_block_t *block; /* one half of the old root block */
982 xfs_buf_t *bp; /* buffer containing block */
983 int error; /* error return value */
984 xfs_inobt_key_t *kp; /* btree key pointer */
985 xfs_agblock_t lbno; /* left block number */
986 xfs_buf_t *lbp; /* left buffer pointer */
987 xfs_inobt_block_t *left; /* left btree block */
988 xfs_buf_t *nbp; /* new (root) buffer */
989 xfs_inobt_block_t *new; /* new (root) btree block */
990 int nptr; /* new value for key index, 1 or 2 */
991 xfs_inobt_ptr_t *pp; /* btree address pointer */
992 xfs_agblock_t rbno; /* right block number */
993 xfs_buf_t *rbp; /* right buffer pointer */
994 xfs_inobt_block_t *right; /* right btree block */
995 xfs_inobt_rec_t *rp; /* btree record pointer */
997 ASSERT(cur->bc_nlevels < XFS_IN_MAXLEVELS(cur->bc_mp));
1000 * Get a block & a buffer.
1002 agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
1003 args.tp = cur->bc_tp;
1004 args.mp = cur->bc_mp;
1005 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno,
1006 be32_to_cpu(agi->agi_root));
1007 args.mod = args.minleft = args.alignment = args.total = args.wasdel =
1008 args.isfl = args.userdata = args.minalignslop = 0;
1009 args.minlen = args.maxlen = args.prod = 1;
1010 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1011 if ((error = xfs_alloc_vextent(&args)))
1014 * None available, we fail.
1016 if (args.fsbno == NULLFSBLOCK) {
1020 ASSERT(args.len == 1);
1021 nbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
1022 new = XFS_BUF_TO_INOBT_BLOCK(nbp);
1024 * Set the root data in the a.g. inode structure.
1026 agi->agi_root = cpu_to_be32(args.agbno);
1027 be32_add_cpu(&agi->agi_level, 1);
1028 xfs_ialloc_log_agi(args.tp, cur->bc_private.a.agbp,
1029 XFS_AGI_ROOT | XFS_AGI_LEVEL);
1031 * At the previous root level there are now two blocks: the old
1032 * root, and the new block generated when it was split.
1033 * We don't know which one the cursor is pointing at, so we
1034 * set up variables "left" and "right" for each case.
1036 bp = cur->bc_bufs[cur->bc_nlevels - 1];
1037 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1039 if ((error = xfs_btree_check_sblock(cur, block, cur->bc_nlevels - 1, bp)))
1042 if (be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
1044 * Our block is left, pick up the right block.
1047 lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
1049 rbno = be32_to_cpu(left->bb_rightsib);
1050 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
1051 rbno, 0, &rbp, XFS_INO_BTREE_REF)))
1054 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
1055 if ((error = xfs_btree_check_sblock(cur, right,
1056 cur->bc_nlevels - 1, rbp)))
1061 * Our block is right, pick up the left block.
1064 rbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(rbp));
1066 lbno = be32_to_cpu(right->bb_leftsib);
1067 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
1068 lbno, 0, &lbp, XFS_INO_BTREE_REF)))
1071 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
1072 if ((error = xfs_btree_check_sblock(cur, left,
1073 cur->bc_nlevels - 1, lbp)))
1078 * Fill in the new block's btree header and log it.
1080 new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1081 new->bb_level = cpu_to_be16(cur->bc_nlevels);
1082 new->bb_numrecs = cpu_to_be16(2);
1083 new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1084 new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
1085 xfs_inobt_log_block(args.tp, nbp, XFS_BB_ALL_BITS);
1086 ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
1088 * Fill in the key data in the new root.
1090 kp = XFS_INOBT_KEY_ADDR(new, 1, cur);
1091 if (be16_to_cpu(left->bb_level) > 0) {
1092 kp[0] = *XFS_INOBT_KEY_ADDR(left, 1, cur);
1093 kp[1] = *XFS_INOBT_KEY_ADDR(right, 1, cur);
1095 rp = XFS_INOBT_REC_ADDR(left, 1, cur);
1096 kp[0].ir_startino = rp->ir_startino;
1097 rp = XFS_INOBT_REC_ADDR(right, 1, cur);
1098 kp[1].ir_startino = rp->ir_startino;
1100 xfs_inobt_log_keys(cur, nbp, 1, 2);
1102 * Fill in the pointer data in the new root.
1104 pp = XFS_INOBT_PTR_ADDR(new, 1, cur);
1105 pp[0] = cpu_to_be32(lbno);
1106 pp[1] = cpu_to_be32(rbno);
1107 xfs_inobt_log_ptrs(cur, nbp, 1, 2);
1109 * Fix up the cursor.
1111 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
1112 cur->bc_ptrs[cur->bc_nlevels] = nptr;
1119 * Split cur/level block in half.
1120 * Return new block number and its first record (to be inserted into parent).
1122 STATIC int /* error */
1124 xfs_btree_cur_t *cur, /* btree cursor */
1125 int level, /* level to split */
1126 xfs_agblock_t *bnop, /* output: block number allocated */
1127 xfs_inobt_key_t *keyp, /* output: first key of new block */
1128 xfs_btree_cur_t **curp, /* output: new cursor */
1129 int *stat) /* success/failure */
1131 xfs_alloc_arg_t args; /* allocation argument structure */
1132 int error; /* error return value */
1133 int i; /* loop index/record number */
1134 xfs_agblock_t lbno; /* left (current) block number */
1135 xfs_buf_t *lbp; /* buffer for left block */
1136 xfs_inobt_block_t *left; /* left (current) btree block */
1137 xfs_inobt_key_t *lkp; /* left btree key pointer */
1138 xfs_inobt_ptr_t *lpp; /* left btree address pointer */
1139 xfs_inobt_rec_t *lrp; /* left btree record pointer */
1140 xfs_buf_t *rbp; /* buffer for right block */
1141 xfs_inobt_block_t *right; /* right (new) btree block */
1142 xfs_inobt_key_t *rkp; /* right btree key pointer */
1143 xfs_inobt_ptr_t *rpp; /* right btree address pointer */
1144 xfs_inobt_rec_t *rrp; /* right btree record pointer */
1147 * Set up left block (current one).
1149 lbp = cur->bc_bufs[level];
1150 args.tp = cur->bc_tp;
1151 args.mp = cur->bc_mp;
1152 lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
1154 * Allocate the new block.
1155 * If we can't do it, we're toast. Give up.
1157 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, lbno);
1158 args.mod = args.minleft = args.alignment = args.total = args.wasdel =
1159 args.isfl = args.userdata = args.minalignslop = 0;
1160 args.minlen = args.maxlen = args.prod = 1;
1161 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1162 if ((error = xfs_alloc_vextent(&args)))
1164 if (args.fsbno == NULLFSBLOCK) {
1168 ASSERT(args.len == 1);
1169 rbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
1171 * Set up the new block as "right".
1173 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
1175 * "Left" is the current (according to the cursor) block.
1177 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
1179 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1183 * Fill in the btree header for the new block.
1185 right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1186 right->bb_level = left->bb_level;
1187 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1189 * Make sure that if there's an odd number of entries now, that
1190 * each new block will have the same number of entries.
1192 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1193 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1194 be16_add_cpu(&right->bb_numrecs, 1);
1195 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1197 * For non-leaf blocks, copy keys and addresses over to the new block.
1200 lkp = XFS_INOBT_KEY_ADDR(left, i, cur);
1201 lpp = XFS_INOBT_PTR_ADDR(left, i, cur);
1202 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
1203 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
1205 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1206 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
1210 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1211 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1212 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1213 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1217 * For leaf blocks, copy records over to the new block.
1220 lrp = XFS_INOBT_REC_ADDR(left, i, cur);
1221 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
1222 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1223 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1224 keyp->ir_startino = rrp->ir_startino;
1227 * Find the left block number by looking in the buffer.
1228 * Adjust numrecs, sibling pointers.
1230 be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1231 right->bb_rightsib = left->bb_rightsib;
1232 left->bb_rightsib = cpu_to_be32(args.agbno);
1233 right->bb_leftsib = cpu_to_be32(lbno);
1234 xfs_inobt_log_block(args.tp, rbp, XFS_BB_ALL_BITS);
1235 xfs_inobt_log_block(args.tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1237 * If there's a block to the new block's right, make that block
1238 * point back to right instead of to left.
1240 if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
1241 xfs_inobt_block_t *rrblock; /* rr btree block */
1242 xfs_buf_t *rrbp; /* buffer for rrblock */
1244 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
1245 be32_to_cpu(right->bb_rightsib), 0, &rrbp,
1246 XFS_INO_BTREE_REF)))
1248 rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp);
1249 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1251 rrblock->bb_leftsib = cpu_to_be32(args.agbno);
1252 xfs_inobt_log_block(args.tp, rrbp, XFS_BB_LEFTSIB);
1255 * If the cursor is really in the right block, move it there.
1256 * If it's just pointing past the last entry in left, then we'll
1257 * insert there, so don't change anything in that case.
1259 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1260 xfs_btree_setbuf(cur, level, rbp);
1261 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1264 * If there are more levels, we'll need another cursor which refers
1265 * the right block, no matter where this cursor was.
1267 if (level + 1 < cur->bc_nlevels) {
1268 if ((error = xfs_btree_dup_cursor(cur, curp)))
1270 (*curp)->bc_ptrs[level + 1]++;
1278 * Externally visible routines.
1282 * Delete the record pointed to by cur.
1283 * The cursor refers to the place where the record was (could be inserted)
1284 * when the operation returns.
1288 xfs_btree_cur_t *cur, /* btree cursor */
1289 int *stat) /* success/failure */
1292 int i; /* result code */
1293 int level; /* btree level */
1296 * Go up the tree, starting at leaf level.
1297 * If 2 is returned then a join was done; go to the next level.
1298 * Otherwise we are done.
1300 for (level = 0, i = 2; i == 2; level++) {
1301 if ((error = xfs_inobt_delrec(cur, level, &i)))
1305 for (level = 1; level < cur->bc_nlevels; level++) {
1306 if (cur->bc_ptrs[level] == 0) {
1307 if ((error = xfs_btree_decrement(cur, level, &i)))
1319 * Get the data from the pointed-to record.
1323 xfs_btree_cur_t *cur, /* btree cursor */
1324 xfs_agino_t *ino, /* output: starting inode of chunk */
1325 __int32_t *fcnt, /* output: number of free inodes */
1326 xfs_inofree_t *free, /* output: free inode mask */
1327 int *stat) /* output: success/failure */
1329 xfs_inobt_block_t *block; /* btree block */
1330 xfs_buf_t *bp; /* buffer containing btree block */
1332 int error; /* error return value */
1334 int ptr; /* record number */
1335 xfs_inobt_rec_t *rec; /* record data */
1337 bp = cur->bc_bufs[0];
1338 ptr = cur->bc_ptrs[0];
1339 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1341 if ((error = xfs_btree_check_sblock(cur, block, 0, bp)))
1345 * Off the right end or left end, return failure.
1347 if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
1352 * Point to the record and extract its data.
1354 rec = XFS_INOBT_REC_ADDR(block, ptr, cur);
1355 *ino = be32_to_cpu(rec->ir_startino);
1356 *fcnt = be32_to_cpu(rec->ir_freecount);
1357 *free = be64_to_cpu(rec->ir_free);
1363 * Insert the current record at the point referenced by cur.
1364 * The cursor may be inconsistent on return if splits have been done.
1368 xfs_btree_cur_t *cur, /* btree cursor */
1369 int *stat) /* success/failure */
1371 int error; /* error return value */
1372 int i; /* result value, 0 for failure */
1373 int level; /* current level number in btree */
1374 xfs_agblock_t nbno; /* new block number (split result) */
1375 xfs_btree_cur_t *ncur; /* new cursor (split result) */
1376 xfs_inobt_rec_t nrec; /* record being inserted this level */
1377 xfs_btree_cur_t *pcur; /* previous level's cursor */
1381 nrec.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
1382 nrec.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
1383 nrec.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
1387 * Loop going up the tree, starting at the leaf level.
1388 * Stop when we don't get a split block, that must mean that
1389 * the insert is finished with this level.
1393 * Insert nrec/nbno into this level of the tree.
1394 * Note if we fail, nbno will be null.
1396 if ((error = xfs_inobt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1399 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1403 * See if the cursor we just used is trash.
1404 * Can't trash the caller's cursor, but otherwise we should
1405 * if ncur is a new cursor or we're about to be done.
1407 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
1408 cur->bc_nlevels = pcur->bc_nlevels;
1409 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1412 * If we got a new cursor, switch to it.
1418 } while (nbno != NULLAGBLOCK);
1423 STATIC struct xfs_btree_cur *
1424 xfs_inobt_dup_cursor(
1425 struct xfs_btree_cur *cur)
1427 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
1428 cur->bc_private.a.agbp, cur->bc_private.a.agno);
1432 xfs_inobt_get_maxrecs(
1433 struct xfs_btree_cur *cur,
1436 return cur->bc_mp->m_inobt_mxr[level != 0];
1440 xfs_inobt_init_key_from_rec(
1441 union xfs_btree_key *key,
1442 union xfs_btree_rec *rec)
1444 key->inobt.ir_startino = rec->inobt.ir_startino;
1448 * intial value of ptr for lookup
1451 xfs_inobt_init_ptr_from_cur(
1452 struct xfs_btree_cur *cur,
1453 union xfs_btree_ptr *ptr)
1455 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
1457 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
1459 ptr->s = agi->agi_root;
1464 struct xfs_btree_cur *cur,
1465 union xfs_btree_key *key)
1467 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
1468 cur->bc_rec.i.ir_startino;
1471 #ifdef XFS_BTREE_TRACE
1472 ktrace_t *xfs_inobt_trace_buf;
1475 xfs_inobt_trace_enter(
1476 struct xfs_btree_cur *cur,
1493 ktrace_enter(xfs_inobt_trace_buf, (void *)(__psint_t)type,
1494 (void *)func, (void *)s, NULL, (void *)cur,
1495 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1496 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1497 (void *)a8, (void *)a9, (void *)a10);
1501 xfs_inobt_trace_cursor(
1502 struct xfs_btree_cur *cur,
1507 *s0 = cur->bc_private.a.agno;
1508 *l0 = cur->bc_rec.i.ir_startino;
1509 *l1 = cur->bc_rec.i.ir_free;
1513 xfs_inobt_trace_key(
1514 struct xfs_btree_cur *cur,
1515 union xfs_btree_key *key,
1519 *l0 = be32_to_cpu(key->inobt.ir_startino);
1524 xfs_inobt_trace_record(
1525 struct xfs_btree_cur *cur,
1526 union xfs_btree_rec *rec,
1531 *l0 = be32_to_cpu(rec->inobt.ir_startino);
1532 *l1 = be32_to_cpu(rec->inobt.ir_freecount);
1533 *l2 = be64_to_cpu(rec->inobt.ir_free);
1535 #endif /* XFS_BTREE_TRACE */
1537 static const struct xfs_btree_ops xfs_inobt_ops = {
1538 .rec_len = sizeof(xfs_inobt_rec_t),
1539 .key_len = sizeof(xfs_inobt_key_t),
1541 .dup_cursor = xfs_inobt_dup_cursor,
1542 .get_maxrecs = xfs_inobt_get_maxrecs,
1543 .init_key_from_rec = xfs_inobt_init_key_from_rec,
1544 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
1545 .key_diff = xfs_inobt_key_diff,
1547 #ifdef XFS_BTREE_TRACE
1548 .trace_enter = xfs_inobt_trace_enter,
1549 .trace_cursor = xfs_inobt_trace_cursor,
1550 .trace_key = xfs_inobt_trace_key,
1551 .trace_record = xfs_inobt_trace_record,
1556 * Allocate a new inode btree cursor.
1558 struct xfs_btree_cur * /* new inode btree cursor */
1559 xfs_inobt_init_cursor(
1560 struct xfs_mount *mp, /* file system mount point */
1561 struct xfs_trans *tp, /* transaction pointer */
1562 struct xfs_buf *agbp, /* buffer for agi structure */
1563 xfs_agnumber_t agno) /* allocation group number */
1565 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
1566 struct xfs_btree_cur *cur;
1568 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
1572 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
1573 cur->bc_btnum = XFS_BTNUM_INO;
1574 cur->bc_blocklog = mp->m_sb.sb_blocklog;
1576 cur->bc_ops = &xfs_inobt_ops;
1578 cur->bc_private.a.agbp = agbp;
1579 cur->bc_private.a.agno = agno;