]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_ialloc_btree.c
2 * Copyright (c) 2000-2001 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 * Inode allocation management for XFS.
39 * Insert one record/level. Return information to the caller
40 * allowing the next level up to proceed if necessary.
42 STATIC
int /* error */
44 xfs_btree_cur_t
*cur
, /* btree cursor */
45 int level
, /* level to insert record at */
46 xfs_agblock_t
*bnop
, /* i/o: block number inserted */
47 xfs_inobt_rec_t
*recp
, /* i/o: record data inserted */
48 xfs_btree_cur_t
**curp
, /* output: new cursor replacing cur */
49 int *stat
) /* success/failure */
51 xfs_inobt_block_t
*block
; /* btree block record/key lives in */
52 xfs_buf_t
*bp
; /* buffer for block */
53 int error
; /* error return value */
54 int i
; /* loop index */
55 xfs_inobt_key_t key
; /* key value being inserted */
56 xfs_inobt_key_t
*kp
=NULL
; /* pointer to btree keys */
57 xfs_agblock_t nbno
; /* block number of allocated block */
58 xfs_btree_cur_t
*ncur
; /* new cursor to be used at next lvl */
59 xfs_inobt_key_t nkey
; /* new key value, from split */
60 xfs_inobt_rec_t nrec
; /* new record value, for caller */
61 int optr
; /* old ptr value */
62 xfs_inobt_ptr_t
*pp
; /* pointer to btree addresses */
63 int ptr
; /* index in btree block for this rec */
64 xfs_inobt_rec_t
*rp
=NULL
; /* pointer to btree records */
67 * If we made it to the root level, allocate a new root block
70 if (level
>= cur
->bc_nlevels
) {
71 error
= xfs_inobt_newroot(cur
, &i
);
77 * Make a key out of the record data to be inserted, and save it.
79 key
.ir_startino
= recp
->ir_startino
; /* INT_: direct copy */
80 optr
= ptr
= cur
->bc_ptrs
[level
];
82 * If we're off the left edge, return failure.
89 * Get pointers to the btree buffer and block.
91 bp
= cur
->bc_bufs
[level
];
92 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
94 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
97 * Check that the new entry is being inserted in the right place.
99 if (ptr
<= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
101 rp
= XFS_INOBT_REC_ADDR(block
, ptr
, cur
);
102 xfs_btree_check_rec(cur
->bc_btnum
, recp
, rp
);
104 kp
= XFS_INOBT_KEY_ADDR(block
, ptr
, cur
);
105 xfs_btree_check_key(cur
->bc_btnum
, &key
, kp
);
110 ncur
= (xfs_btree_cur_t
*)0;
112 * If the block is full, we can't insert the new entry until we
113 * make the block un-full.
115 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) == XFS_INOBT_BLOCK_MAXRECS(level
, cur
)) {
117 * First, try shifting an entry to the right neighbor.
119 if ((error
= xfs_inobt_rshift(cur
, level
, &i
)))
125 * Next, try shifting an entry to the left neighbor.
128 if ((error
= xfs_inobt_lshift(cur
, level
, &i
)))
131 optr
= ptr
= cur
->bc_ptrs
[level
];
134 * Next, try splitting the current block
135 * in half. If this works we have to
136 * re-set our variables because
137 * we could be in a different block now.
139 if ((error
= xfs_inobt_split(cur
, level
, &nbno
,
143 bp
= cur
->bc_bufs
[level
];
144 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
146 if ((error
= xfs_btree_check_sblock(cur
,
150 ptr
= cur
->bc_ptrs
[level
];
151 nrec
.ir_startino
= nkey
.ir_startino
; /* INT_: direct copy */
154 * Otherwise the insert fails.
163 * At this point we know there's room for our new entry in the block
168 * It's a non-leaf entry. Make a hole for the new data
169 * in the key and ptr regions of the block.
171 kp
= XFS_INOBT_KEY_ADDR(block
, 1, cur
);
172 pp
= XFS_INOBT_PTR_ADDR(block
, 1, cur
);
174 for (i
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
); i
>= ptr
; i
--) {
175 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(pp
[i
- 1], ARCH_CONVERT
), level
)))
179 ovbcopy(&kp
[ptr
- 1], &kp
[ptr
],
180 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*kp
));
181 ovbcopy(&pp
[ptr
- 1], &pp
[ptr
],
182 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*pp
));
184 * Now stuff the new data in, bump numrecs and log the new data.
187 if ((error
= xfs_btree_check_sptr(cur
, *bnop
, level
)))
190 kp
[ptr
- 1] = key
; /* INT_: struct copy */
191 INT_SET(pp
[ptr
- 1], ARCH_CONVERT
, *bnop
);
192 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
193 xfs_inobt_log_keys(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
194 xfs_inobt_log_ptrs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
197 * It's a leaf entry. Make a hole for the new record.
199 rp
= XFS_INOBT_REC_ADDR(block
, 1, cur
);
200 ovbcopy(&rp
[ptr
- 1], &rp
[ptr
],
201 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*rp
));
203 * Now stuff the new record in, bump numrecs
204 * and log the new data.
206 rp
[ptr
- 1] = *recp
; /* INT_: struct copy */
207 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
208 xfs_inobt_log_recs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
211 * Log the new number of records in the btree header.
213 xfs_inobt_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
216 * Check that the key/record is in the right place, now.
218 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
220 xfs_btree_check_rec(cur
->bc_btnum
, rp
+ ptr
- 1,
223 xfs_btree_check_key(cur
->bc_btnum
, kp
+ ptr
- 1,
228 * If we inserted at the start of a block, update the parents' keys.
230 if (optr
== 1 && (error
= xfs_inobt_updkey(cur
, &key
, level
+ 1)))
233 * Return the new block number, if any.
234 * If there is one, give back a record value and a cursor too.
237 if (nbno
!= NULLAGBLOCK
) {
238 *recp
= nrec
; /* INT_: struct copy */
246 * Log header fields from a btree block.
250 xfs_trans_t
*tp
, /* transaction pointer */
251 xfs_buf_t
*bp
, /* buffer containing btree block */
252 int fields
) /* mask of fields: XFS_BB_... */
254 int first
; /* first byte offset logged */
255 int last
; /* last byte offset logged */
256 static const short offsets
[] = { /* table of offsets */
257 offsetof(xfs_inobt_block_t
, bb_magic
),
258 offsetof(xfs_inobt_block_t
, bb_level
),
259 offsetof(xfs_inobt_block_t
, bb_numrecs
),
260 offsetof(xfs_inobt_block_t
, bb_leftsib
),
261 offsetof(xfs_inobt_block_t
, bb_rightsib
),
262 sizeof(xfs_inobt_block_t
)
265 xfs_btree_offsets(fields
, offsets
, XFS_BB_NUM_BITS
, &first
, &last
);
266 xfs_trans_log_buf(tp
, bp
, first
, last
);
270 * Log keys from a btree block (nonleaf).
274 xfs_btree_cur_t
*cur
, /* btree cursor */
275 xfs_buf_t
*bp
, /* buffer containing btree block */
276 int kfirst
, /* index of first key to log */
277 int klast
) /* index of last key to log */
279 xfs_inobt_block_t
*block
; /* btree block to log from */
280 int first
; /* first byte offset logged */
281 xfs_inobt_key_t
*kp
; /* key pointer in btree block */
282 int last
; /* last byte offset logged */
284 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
285 kp
= XFS_INOBT_KEY_ADDR(block
, 1, cur
);
286 first
= (int)((xfs_caddr_t
)&kp
[kfirst
- 1] - (xfs_caddr_t
)block
);
287 last
= (int)(((xfs_caddr_t
)&kp
[klast
] - 1) - (xfs_caddr_t
)block
);
288 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
292 * Log block pointer fields from a btree block (nonleaf).
296 xfs_btree_cur_t
*cur
, /* btree cursor */
297 xfs_buf_t
*bp
, /* buffer containing btree block */
298 int pfirst
, /* index of first pointer to log */
299 int plast
) /* index of last pointer to log */
301 xfs_inobt_block_t
*block
; /* btree block to log from */
302 int first
; /* first byte offset logged */
303 int last
; /* last byte offset logged */
304 xfs_inobt_ptr_t
*pp
; /* block-pointer pointer in btree blk */
306 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
307 pp
= XFS_INOBT_PTR_ADDR(block
, 1, cur
);
308 first
= (int)((xfs_caddr_t
)&pp
[pfirst
- 1] - (xfs_caddr_t
)block
);
309 last
= (int)(((xfs_caddr_t
)&pp
[plast
] - 1) - (xfs_caddr_t
)block
);
310 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
314 * Log records from a btree block (leaf).
318 xfs_btree_cur_t
*cur
, /* btree cursor */
319 xfs_buf_t
*bp
, /* buffer containing btree block */
320 int rfirst
, /* index of first record to log */
321 int rlast
) /* index of last record to log */
323 xfs_inobt_block_t
*block
; /* btree block to log from */
324 int first
; /* first byte offset logged */
325 int last
; /* last byte offset logged */
326 xfs_inobt_rec_t
*rp
; /* record pointer for btree block */
328 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
329 rp
= XFS_INOBT_REC_ADDR(block
, 1, cur
);
330 first
= (int)((xfs_caddr_t
)&rp
[rfirst
- 1] - (xfs_caddr_t
)block
);
331 last
= (int)(((xfs_caddr_t
)&rp
[rlast
] - 1) - (xfs_caddr_t
)block
);
332 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
336 * Lookup the record. The cursor is made to point to it, based on dir.
337 * Return 0 if can't find any such record, 1 for success.
339 STATIC
int /* error */
341 xfs_btree_cur_t
*cur
, /* btree cursor */
342 xfs_lookup_t dir
, /* <=, ==, or >= */
343 int *stat
) /* success/failure */
345 xfs_agblock_t agbno
; /* a.g. relative btree block number */
346 xfs_agnumber_t agno
; /* allocation group number */
347 xfs_inobt_block_t
*block
=NULL
; /* current btree block */
348 int diff
; /* difference for the current key */
349 int error
; /* error return value */
350 int keyno
=0; /* current key number */
351 int level
; /* level in the btree */
352 xfs_mount_t
*mp
; /* file system mount point */
355 * Get the allocation group header, and the root block number.
359 xfs_agi_t
*agi
; /* a.g. inode header */
361 agi
= XFS_BUF_TO_AGI(cur
->bc_private
.i
.agbp
);
362 agno
= INT_GET(agi
->agi_seqno
, ARCH_CONVERT
);
363 agbno
= INT_GET(agi
->agi_root
, ARCH_CONVERT
);
366 * Iterate over each level in the btree, starting at the root.
367 * For each level above the leaves, find the key we need, based
368 * on the lookup record, then follow the corresponding block
369 * pointer down to the next level.
371 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
372 xfs_buf_t
*bp
; /* buffer pointer for btree block */
373 xfs_daddr_t d
; /* disk address of btree block */
376 * Get the disk address we're looking for.
378 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
380 * If the old buffer at this level is for a different block,
381 * throw it away, otherwise just use it.
383 bp
= cur
->bc_bufs
[level
];
384 if (bp
&& XFS_BUF_ADDR(bp
) != d
)
388 * Need to get a new buffer. Read it, then
389 * set it in the cursor, releasing the old one.
391 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
392 agno
, agbno
, 0, &bp
, XFS_INO_BTREE_REF
)))
394 xfs_btree_setbuf(cur
, level
, bp
);
396 * Point to the btree block, now that we have the buffer
398 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
399 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
403 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
405 * If we already had a key match at a higher level, we know
406 * we need to use the first entry in this block.
411 * Otherwise we need to search this block. Do a binary search.
414 int high
; /* high entry number */
415 xfs_inobt_key_t
*kkbase
=NULL
;/* base of keys in block */
416 xfs_inobt_rec_t
*krbase
=NULL
;/* base of records in block */
417 int low
; /* low entry number */
420 * Get a pointer to keys or records.
423 kkbase
= XFS_INOBT_KEY_ADDR(block
, 1, cur
);
425 krbase
= XFS_INOBT_REC_ADDR(block
, 1, cur
);
427 * Set low and high entry numbers, 1-based.
430 if (!(high
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))) {
432 * If the block is empty, the tree must
435 ASSERT(level
== 0 && cur
->bc_nlevels
== 1);
436 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
441 * Binary search the block.
443 while (low
<= high
) {
444 xfs_agino_t startino
; /* key value */
447 * keyno is average of low and high.
449 keyno
= (low
+ high
) >> 1;
454 xfs_inobt_key_t
*kkp
;
456 kkp
= kkbase
+ keyno
- 1;
457 startino
= INT_GET(kkp
->ir_startino
, ARCH_CONVERT
);
459 xfs_inobt_rec_t
*krp
;
461 krp
= krbase
+ keyno
- 1;
462 startino
= INT_GET(krp
->ir_startino
, ARCH_CONVERT
);
465 * Compute difference to get next direction.
467 diff
= (int)startino
- cur
->bc_rec
.i
.ir_startino
;
469 * Less than, move right.
474 * Greater than, move left.
486 * If there are more levels, set up for the next level
487 * by getting the block number and filling in the cursor.
491 * If we moved left, need the previous key number,
492 * unless there isn't one.
494 if (diff
> 0 && --keyno
< 1)
496 agbno
= INT_GET(*XFS_INOBT_PTR_ADDR(block
, keyno
, cur
), ARCH_CONVERT
);
498 if ((error
= xfs_btree_check_sptr(cur
, agbno
, level
)))
501 cur
->bc_ptrs
[level
] = keyno
;
505 * Done with the search.
506 * See if we need to adjust the results.
508 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
511 * If ge search and we went off the end of the block, but it's
512 * not the last block, we're in the wrong block.
514 if (dir
== XFS_LOOKUP_GE
&&
515 keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) &&
516 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
519 cur
->bc_ptrs
[0] = keyno
;
520 if ((error
= xfs_inobt_increment(cur
, 0, &i
)))
527 else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
529 cur
->bc_ptrs
[0] = keyno
;
531 * Return if we succeeded or not.
533 if (keyno
== 0 || keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
536 *stat
= ((dir
!= XFS_LOOKUP_EQ
) || (diff
== 0));
541 * Move 1 record left from cur/level if possible.
542 * Update cur to reflect the new path.
544 STATIC
int /* error */
546 xfs_btree_cur_t
*cur
, /* btree cursor */
547 int level
, /* level to shift record on */
548 int *stat
) /* success/failure */
550 int error
; /* error return value */
552 int i
; /* loop index */
554 xfs_inobt_key_t key
; /* key value for leaf level upward */
555 xfs_buf_t
*lbp
; /* buffer for left neighbor block */
556 xfs_inobt_block_t
*left
; /* left neighbor btree block */
557 xfs_inobt_key_t
*lkp
=NULL
; /* key pointer for left block */
558 xfs_inobt_ptr_t
*lpp
; /* address pointer for left block */
559 xfs_inobt_rec_t
*lrp
=NULL
; /* record pointer for left block */
560 int nrec
; /* new number of left block entries */
561 xfs_buf_t
*rbp
; /* buffer for right (current) block */
562 xfs_inobt_block_t
*right
; /* right (current) btree block */
563 xfs_inobt_key_t
*rkp
=NULL
; /* key pointer for right block */
564 xfs_inobt_ptr_t
*rpp
=NULL
; /* address pointer for right block */
565 xfs_inobt_rec_t
*rrp
=NULL
; /* record pointer for right block */
568 * Set up variables for this block as "right".
570 rbp
= cur
->bc_bufs
[level
];
571 right
= XFS_BUF_TO_INOBT_BLOCK(rbp
);
573 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
577 * If we've got no left sibling then we can't shift an entry left.
579 if (INT_GET(right
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
584 * If the cursor entry is the one that would be moved, don't
585 * do it... it's too complicated.
587 if (cur
->bc_ptrs
[level
] <= 1) {
592 * Set up the left neighbor as "left".
594 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
595 cur
->bc_private
.i
.agno
, INT_GET(right
->bb_leftsib
, ARCH_CONVERT
), 0, &lbp
,
598 left
= XFS_BUF_TO_INOBT_BLOCK(lbp
);
599 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
602 * If it's full, it can't take another entry.
604 if (INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) == XFS_INOBT_BLOCK_MAXRECS(level
, cur
)) {
608 nrec
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1;
610 * If non-leaf, copy a key and a ptr to the left block.
613 lkp
= XFS_INOBT_KEY_ADDR(left
, nrec
, cur
);
614 rkp
= XFS_INOBT_KEY_ADDR(right
, 1, cur
);
616 xfs_inobt_log_keys(cur
, lbp
, nrec
, nrec
);
617 lpp
= XFS_INOBT_PTR_ADDR(left
, nrec
, cur
);
618 rpp
= XFS_INOBT_PTR_ADDR(right
, 1, cur
);
620 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(*rpp
, ARCH_CONVERT
), level
)))
623 *lpp
= *rpp
; /* INT_: no-change copy */
624 xfs_inobt_log_ptrs(cur
, lbp
, nrec
, nrec
);
627 * If leaf, copy a record to the left block.
630 lrp
= XFS_INOBT_REC_ADDR(left
, nrec
, cur
);
631 rrp
= XFS_INOBT_REC_ADDR(right
, 1, cur
);
633 xfs_inobt_log_recs(cur
, lbp
, nrec
, nrec
);
636 * Bump and log left's numrecs, decrement and log right's numrecs.
638 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, +1);
639 xfs_inobt_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
642 xfs_btree_check_key(cur
->bc_btnum
, lkp
- 1, lkp
);
644 xfs_btree_check_rec(cur
->bc_btnum
, lrp
- 1, lrp
);
646 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, -1);
647 xfs_inobt_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
649 * Slide the contents of right down one entry.
653 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
654 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
+ 1], ARCH_CONVERT
),
659 ovbcopy(rkp
+ 1, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
660 ovbcopy(rpp
+ 1, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
661 xfs_inobt_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
662 xfs_inobt_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
664 ovbcopy(rrp
+ 1, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
665 xfs_inobt_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
666 key
.ir_startino
= rrp
->ir_startino
; /* INT_: direct copy */
670 * Update the parent key values of right.
672 if ((error
= xfs_inobt_updkey(cur
, rkp
, level
+ 1)))
675 * Slide the cursor value left one.
677 cur
->bc_ptrs
[level
]--;
683 * Allocate a new root block, fill it in.
685 STATIC
int /* error */
687 xfs_btree_cur_t
*cur
, /* btree cursor */
688 int *stat
) /* success/failure */
690 xfs_agi_t
*agi
; /* a.g. inode header */
691 xfs_alloc_arg_t args
; /* allocation argument structure */
692 xfs_inobt_block_t
*block
; /* one half of the old root block */
693 xfs_buf_t
*bp
; /* buffer containing block */
694 int error
; /* error return value */
695 xfs_inobt_key_t
*kp
; /* btree key pointer */
696 xfs_agblock_t lbno
; /* left block number */
697 xfs_buf_t
*lbp
; /* left buffer pointer */
698 xfs_inobt_block_t
*left
; /* left btree block */
699 xfs_buf_t
*nbp
; /* new (root) buffer */
700 xfs_inobt_block_t
*new; /* new (root) btree block */
701 int nptr
; /* new value for key index, 1 or 2 */
702 xfs_inobt_ptr_t
*pp
; /* btree address pointer */
703 xfs_agblock_t rbno
; /* right block number */
704 xfs_buf_t
*rbp
; /* right buffer pointer */
705 xfs_inobt_block_t
*right
; /* right btree block */
706 xfs_inobt_rec_t
*rp
; /* btree record pointer */
708 ASSERT(cur
->bc_nlevels
< XFS_IN_MAXLEVELS(cur
->bc_mp
));
711 * Get a block & a buffer.
713 agi
= XFS_BUF_TO_AGI(cur
->bc_private
.i
.agbp
);
714 args
.tp
= cur
->bc_tp
;
715 args
.mp
= cur
->bc_mp
;
716 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.i
.agno
,
717 INT_GET(agi
->agi_root
, ARCH_CONVERT
));
718 args
.mod
= args
.minleft
= args
.alignment
= args
.total
= args
.wasdel
=
719 args
.isfl
= args
.userdata
= args
.minalignslop
= 0;
720 args
.minlen
= args
.maxlen
= args
.prod
= 1;
721 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
722 if ((error
= xfs_alloc_vextent(&args
)))
725 * None available, we fail.
727 if (args
.fsbno
== NULLFSBLOCK
) {
731 ASSERT(args
.len
== 1);
732 nbp
= xfs_btree_get_bufs(args
.mp
, args
.tp
, args
.agno
, args
.agbno
, 0);
733 new = XFS_BUF_TO_INOBT_BLOCK(nbp
);
735 * Set the root data in the a.g. inode structure.
737 INT_SET(agi
->agi_root
, ARCH_CONVERT
, args
.agbno
);
738 INT_MOD(agi
->agi_level
, ARCH_CONVERT
, 1);
739 xfs_ialloc_log_agi(args
.tp
, cur
->bc_private
.i
.agbp
,
740 XFS_AGI_ROOT
| XFS_AGI_LEVEL
);
742 * At the previous root level there are now two blocks: the old
743 * root, and the new block generated when it was split.
744 * We don't know which one the cursor is pointing at, so we
745 * set up variables "left" and "right" for each case.
747 bp
= cur
->bc_bufs
[cur
->bc_nlevels
- 1];
748 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
750 if ((error
= xfs_btree_check_sblock(cur
, block
, cur
->bc_nlevels
- 1, bp
)))
753 if (INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
755 * Our block is left, pick up the right block.
758 lbno
= XFS_DADDR_TO_AGBNO(args
.mp
, XFS_BUF_ADDR(lbp
));
760 rbno
= INT_GET(left
->bb_rightsib
, ARCH_CONVERT
);
761 if ((error
= xfs_btree_read_bufs(args
.mp
, args
.tp
, args
.agno
,
762 rbno
, 0, &rbp
, XFS_INO_BTREE_REF
)))
765 right
= XFS_BUF_TO_INOBT_BLOCK(rbp
);
766 if ((error
= xfs_btree_check_sblock(cur
, right
,
767 cur
->bc_nlevels
- 1, rbp
)))
772 * Our block is right, pick up the left block.
775 rbno
= XFS_DADDR_TO_AGBNO(args
.mp
, XFS_BUF_ADDR(rbp
));
777 lbno
= INT_GET(right
->bb_leftsib
, ARCH_CONVERT
);
778 if ((error
= xfs_btree_read_bufs(args
.mp
, args
.tp
, args
.agno
,
779 lbno
, 0, &lbp
, XFS_INO_BTREE_REF
)))
782 left
= XFS_BUF_TO_INOBT_BLOCK(lbp
);
783 if ((error
= xfs_btree_check_sblock(cur
, left
,
784 cur
->bc_nlevels
- 1, lbp
)))
789 * Fill in the new block's btree header and log it.
791 INT_SET(new->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
792 INT_SET(new->bb_level
, ARCH_CONVERT
, (__uint16_t
)cur
->bc_nlevels
);
793 INT_SET(new->bb_numrecs
, ARCH_CONVERT
, 2);
794 INT_SET(new->bb_leftsib
, ARCH_CONVERT
, NULLAGBLOCK
);
795 INT_SET(new->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
796 xfs_inobt_log_block(args
.tp
, nbp
, XFS_BB_ALL_BITS
);
797 ASSERT(lbno
!= NULLAGBLOCK
&& rbno
!= NULLAGBLOCK
);
799 * Fill in the key data in the new root.
801 kp
= XFS_INOBT_KEY_ADDR(new, 1, cur
);
802 if (INT_GET(left
->bb_level
, ARCH_CONVERT
) > 0) {
803 kp
[0] = *XFS_INOBT_KEY_ADDR(left
, 1, cur
); /* INT_: struct copy */
804 kp
[1] = *XFS_INOBT_KEY_ADDR(right
, 1, cur
); /* INT_: struct copy */
806 rp
= XFS_INOBT_REC_ADDR(left
, 1, cur
);
807 INT_COPY(kp
[0].ir_startino
, rp
->ir_startino
, ARCH_CONVERT
);
808 rp
= XFS_INOBT_REC_ADDR(right
, 1, cur
);
809 INT_COPY(kp
[1].ir_startino
, rp
->ir_startino
, ARCH_CONVERT
);
811 xfs_inobt_log_keys(cur
, nbp
, 1, 2);
813 * Fill in the pointer data in the new root.
815 pp
= XFS_INOBT_PTR_ADDR(new, 1, cur
);
816 INT_SET(pp
[0], ARCH_CONVERT
, lbno
);
817 INT_SET(pp
[1], ARCH_CONVERT
, rbno
);
818 xfs_inobt_log_ptrs(cur
, nbp
, 1, 2);
822 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
823 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
830 * Move 1 record right 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 */
840 int i
; /* loop index */
841 xfs_inobt_key_t key
; /* key value for leaf level upward */
842 xfs_buf_t
*lbp
; /* buffer for left (current) block */
843 xfs_inobt_block_t
*left
; /* left (current) btree block */
844 xfs_inobt_key_t
*lkp
; /* key pointer for left block */
845 xfs_inobt_ptr_t
*lpp
; /* address pointer for left block */
846 xfs_inobt_rec_t
*lrp
; /* record pointer for left block */
847 xfs_buf_t
*rbp
; /* buffer for right neighbor block */
848 xfs_inobt_block_t
*right
; /* right neighbor btree block */
849 xfs_inobt_key_t
*rkp
; /* key pointer for right block */
850 xfs_inobt_ptr_t
*rpp
; /* address pointer for right block */
851 xfs_inobt_rec_t
*rrp
=NULL
; /* record pointer for right block */
852 xfs_btree_cur_t
*tcur
; /* temporary cursor */
855 * Set up variables for this block as "left".
857 lbp
= cur
->bc_bufs
[level
];
858 left
= XFS_BUF_TO_INOBT_BLOCK(lbp
);
860 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
864 * If we've got no right sibling then we can't shift an entry right.
866 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
871 * If the cursor entry is the one that would be moved, don't
872 * do it... it's too complicated.
874 if (cur
->bc_ptrs
[level
] >= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
)) {
879 * Set up the right neighbor as "right".
881 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
882 cur
->bc_private
.i
.agno
, INT_GET(left
->bb_rightsib
, ARCH_CONVERT
), 0, &rbp
,
885 right
= XFS_BUF_TO_INOBT_BLOCK(rbp
);
886 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
889 * If it's full, it can't take another entry.
891 if (INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) == XFS_INOBT_BLOCK_MAXRECS(level
, cur
)) {
896 * Make a hole at the start of the right neighbor block, then
897 * copy the last left block entry to the hole.
900 lkp
= XFS_INOBT_KEY_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
901 lpp
= XFS_INOBT_PTR_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
902 rkp
= XFS_INOBT_KEY_ADDR(right
, 1, cur
);
903 rpp
= XFS_INOBT_PTR_ADDR(right
, 1, cur
);
905 for (i
= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) - 1; i
>= 0; i
--) {
906 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
], ARCH_CONVERT
), level
)))
910 ovbcopy(rkp
, rkp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
911 ovbcopy(rpp
, rpp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
913 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(*lpp
, ARCH_CONVERT
), level
)))
916 *rkp
= *lkp
; /* INT_: no change copy */
917 *rpp
= *lpp
; /* INT_: no change copy */
918 xfs_inobt_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
919 xfs_inobt_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
921 lrp
= XFS_INOBT_REC_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
922 rrp
= XFS_INOBT_REC_ADDR(right
, 1, cur
);
923 ovbcopy(rrp
, rrp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
925 xfs_inobt_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
926 key
.ir_startino
= rrp
->ir_startino
; /* INT_: direct copy */
930 * Decrement and log left's numrecs, bump and log right's numrecs.
932 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -1);
933 xfs_inobt_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
934 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
937 xfs_btree_check_key(cur
->bc_btnum
, rkp
, rkp
+ 1);
939 xfs_btree_check_rec(cur
->bc_btnum
, rrp
, rrp
+ 1);
941 xfs_inobt_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
943 * Using a temporary cursor, update the parent key values of the
944 * block on the right.
946 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
948 xfs_btree_lastrec(tcur
, level
);
949 if ((error
= xfs_inobt_increment(tcur
, level
, &i
)) ||
950 (error
= xfs_inobt_updkey(tcur
, rkp
, level
+ 1))) {
951 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
954 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
960 * Split cur/level block in half.
961 * Return new block number and its first record (to be inserted into parent).
963 STATIC
int /* error */
965 xfs_btree_cur_t
*cur
, /* btree cursor */
966 int level
, /* level to split */
967 xfs_agblock_t
*bnop
, /* output: block number allocated */
968 xfs_inobt_key_t
*keyp
, /* output: first key of new block */
969 xfs_btree_cur_t
**curp
, /* output: new cursor */
970 int *stat
) /* success/failure */
972 xfs_alloc_arg_t args
; /* allocation argument structure */
973 int error
; /* error return value */
974 int i
; /* loop index/record number */
975 xfs_agblock_t lbno
; /* left (current) block number */
976 xfs_buf_t
*lbp
; /* buffer for left block */
977 xfs_inobt_block_t
*left
; /* left (current) btree block */
978 xfs_inobt_key_t
*lkp
; /* left btree key pointer */
979 xfs_inobt_ptr_t
*lpp
; /* left btree address pointer */
980 xfs_inobt_rec_t
*lrp
; /* left btree record pointer */
981 xfs_buf_t
*rbp
; /* buffer for right block */
982 xfs_inobt_block_t
*right
; /* right (new) btree block */
983 xfs_inobt_key_t
*rkp
; /* right btree key pointer */
984 xfs_inobt_ptr_t
*rpp
; /* right btree address pointer */
985 xfs_inobt_rec_t
*rrp
; /* right btree record pointer */
988 * Set up left block (current one).
990 lbp
= cur
->bc_bufs
[level
];
991 args
.tp
= cur
->bc_tp
;
992 args
.mp
= cur
->bc_mp
;
993 lbno
= XFS_DADDR_TO_AGBNO(args
.mp
, XFS_BUF_ADDR(lbp
));
995 * Allocate the new block.
996 * If we can't do it, we're toast. Give up.
998 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.i
.agno
, lbno
);
999 args
.mod
= args
.minleft
= args
.alignment
= args
.total
= args
.wasdel
=
1000 args
.isfl
= args
.userdata
= args
.minalignslop
= 0;
1001 args
.minlen
= args
.maxlen
= args
.prod
= 1;
1002 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
1003 if ((error
= xfs_alloc_vextent(&args
)))
1005 if (args
.fsbno
== NULLFSBLOCK
) {
1009 ASSERT(args
.len
== 1);
1010 rbp
= xfs_btree_get_bufs(args
.mp
, args
.tp
, args
.agno
, args
.agbno
, 0);
1012 * Set up the new block as "right".
1014 right
= XFS_BUF_TO_INOBT_BLOCK(rbp
);
1016 * "Left" is the current (according to the cursor) block.
1018 left
= XFS_BUF_TO_INOBT_BLOCK(lbp
);
1020 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1024 * Fill in the btree header for the new block.
1026 INT_SET(right
->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
1027 right
->bb_level
= left
->bb_level
; /* INT_: direct copy */
1028 INT_SET(right
->bb_numrecs
, ARCH_CONVERT
, (__uint16_t
)(INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) / 2));
1030 * Make sure that if there's an odd number of entries now, that
1031 * each new block will have the same number of entries.
1033 if ((INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) & 1) &&
1034 cur
->bc_ptrs
[level
] <= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1)
1035 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
1036 i
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) - INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1;
1038 * For non-leaf blocks, copy keys and addresses over to the new block.
1041 lkp
= XFS_INOBT_KEY_ADDR(left
, i
, cur
);
1042 lpp
= XFS_INOBT_PTR_ADDR(left
, i
, cur
);
1043 rkp
= XFS_INOBT_KEY_ADDR(right
, 1, cur
);
1044 rpp
= XFS_INOBT_PTR_ADDR(right
, 1, cur
);
1046 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
1047 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(lpp
[i
], ARCH_CONVERT
), level
)))
1051 bcopy(lkp
, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
1052 bcopy(lpp
, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
1053 xfs_inobt_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1054 xfs_inobt_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1058 * For leaf blocks, copy records over to the new block.
1061 lrp
= XFS_INOBT_REC_ADDR(left
, i
, cur
);
1062 rrp
= XFS_INOBT_REC_ADDR(right
, 1, cur
);
1063 bcopy(lrp
, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1064 xfs_inobt_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1065 keyp
->ir_startino
= rrp
->ir_startino
; /* INT_: direct copy */
1068 * Find the left block number by looking in the buffer.
1069 * Adjust numrecs, sibling pointers.
1071 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -(INT_GET(right
->bb_numrecs
, ARCH_CONVERT
)));
1072 right
->bb_rightsib
= left
->bb_rightsib
; /* INT_: direct copy */
1073 INT_SET(left
->bb_rightsib
, ARCH_CONVERT
, args
.agbno
);
1074 INT_SET(right
->bb_leftsib
, ARCH_CONVERT
, lbno
);
1075 xfs_inobt_log_block(args
.tp
, rbp
, XFS_BB_ALL_BITS
);
1076 xfs_inobt_log_block(args
.tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
1078 * If there's a block to the new block's right, make that block
1079 * point back to right instead of to left.
1081 if (INT_GET(right
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1082 xfs_inobt_block_t
*rrblock
; /* rr btree block */
1083 xfs_buf_t
*rrbp
; /* buffer for rrblock */
1085 if ((error
= xfs_btree_read_bufs(args
.mp
, args
.tp
, args
.agno
,
1086 INT_GET(right
->bb_rightsib
, ARCH_CONVERT
), 0, &rrbp
,
1087 XFS_INO_BTREE_REF
)))
1089 rrblock
= XFS_BUF_TO_INOBT_BLOCK(rrbp
);
1090 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
1092 INT_SET(rrblock
->bb_leftsib
, ARCH_CONVERT
, args
.agbno
);
1093 xfs_inobt_log_block(args
.tp
, rrbp
, XFS_BB_LEFTSIB
);
1096 * If the cursor is really in the right block, move it there.
1097 * If it's just pointing past the last entry in left, then we'll
1098 * insert there, so don't change anything in that case.
1100 if (cur
->bc_ptrs
[level
] > INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1) {
1101 xfs_btree_setbuf(cur
, level
, rbp
);
1102 cur
->bc_ptrs
[level
] -= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
1105 * If there are more levels, we'll need another cursor which refers
1106 * the right block, no matter where this cursor was.
1108 if (level
+ 1 < cur
->bc_nlevels
) {
1109 if ((error
= xfs_btree_dup_cursor(cur
, curp
)))
1111 (*curp
)->bc_ptrs
[level
+ 1]++;
1119 * Update keys at all levels from here to the root along the cursor's path.
1121 STATIC
int /* error */
1123 xfs_btree_cur_t
*cur
, /* btree cursor */
1124 xfs_inobt_key_t
*keyp
, /* new key value to update to */
1125 int level
) /* starting level for update */
1127 int ptr
; /* index of key in block */
1130 * Go up the tree from this level toward the root.
1131 * At each level, update the key value to the value input.
1132 * Stop when we reach a level where the cursor isn't pointing
1133 * at the first entry in the block.
1135 for (ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
1136 xfs_buf_t
*bp
; /* buffer for block */
1137 xfs_inobt_block_t
*block
; /* btree block */
1139 int error
; /* error return value */
1141 xfs_inobt_key_t
*kp
; /* ptr to btree block keys */
1143 bp
= cur
->bc_bufs
[level
];
1144 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1146 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1149 ptr
= cur
->bc_ptrs
[level
];
1150 kp
= XFS_INOBT_KEY_ADDR(block
, ptr
, cur
);
1152 xfs_inobt_log_keys(cur
, bp
, ptr
, ptr
);
1158 * Externally visible routines.
1162 * Decrement cursor by one record at the level.
1163 * For nonzero levels the leaf-ward information is untouched.
1166 xfs_inobt_decrement(
1167 xfs_btree_cur_t
*cur
, /* btree cursor */
1168 int level
, /* level in btree, 0 is leaf */
1169 int *stat
) /* success/failure */
1171 xfs_inobt_block_t
*block
; /* btree block */
1173 int lev
; /* btree level */
1175 ASSERT(level
< cur
->bc_nlevels
);
1177 * Read-ahead to the left at this level.
1179 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1181 * Decrement the ptr at this level. If we're still in the block
1184 if (--cur
->bc_ptrs
[level
] > 0) {
1189 * Get a pointer to the btree block.
1191 block
= XFS_BUF_TO_INOBT_BLOCK(cur
->bc_bufs
[level
]);
1193 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
1194 cur
->bc_bufs
[level
])))
1198 * If we just went off the left edge of the tree, return failure.
1200 if (INT_GET(block
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1205 * March up the tree decrementing pointers.
1206 * Stop when we don't go off the left edge of a block.
1208 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1209 if (--cur
->bc_ptrs
[lev
] > 0)
1212 * Read-ahead the left block, we're going to read it
1215 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1218 * If we went off the root then we are seriously confused.
1220 ASSERT(lev
< cur
->bc_nlevels
);
1222 * Now walk back down the tree, fixing up the cursor's buffer
1223 * pointers and key numbers.
1225 for (block
= XFS_BUF_TO_INOBT_BLOCK(cur
->bc_bufs
[lev
]); lev
> level
; ) {
1226 xfs_agblock_t agbno
; /* block number of btree block */
1227 xfs_buf_t
*bp
; /* buffer containing btree block */
1229 agbno
= INT_GET(*XFS_INOBT_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1230 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1231 cur
->bc_private
.i
.agno
, agbno
, 0, &bp
,
1232 XFS_INO_BTREE_REF
)))
1235 xfs_btree_setbuf(cur
, lev
, bp
);
1236 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1237 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1239 cur
->bc_ptrs
[lev
] = INT_GET(block
->bb_numrecs
, ARCH_CONVERT
);
1246 * Get the data from the pointed-to record.
1250 xfs_btree_cur_t
*cur
, /* btree cursor */
1251 xfs_agino_t
*ino
, /* output: starting inode of chunk */
1252 __int32_t
*fcnt
, /* output: number of free inodes */
1253 xfs_inofree_t
*free
, /* output: free inode mask */
1254 int *stat
, /* output: success/failure */
1255 xfs_arch_t arch
) /* input: architecture */
1257 xfs_inobt_block_t
*block
; /* btree block */
1258 xfs_buf_t
*bp
; /* buffer containing btree block */
1260 int error
; /* error return value */
1262 int ptr
; /* record number */
1263 xfs_inobt_rec_t
*rec
; /* record data */
1265 bp
= cur
->bc_bufs
[0];
1266 ptr
= cur
->bc_ptrs
[0];
1267 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1269 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, bp
)))
1273 * Off the right end or left end, return failure.
1275 if (ptr
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) || ptr
<= 0) {
1280 * Point to the record and extract its data.
1282 rec
= XFS_INOBT_REC_ADDR(block
, ptr
, cur
);
1283 ASSERT(arch
== ARCH_NOCONVERT
|| arch
== ARCH_CONVERT
);
1284 if (arch
== ARCH_NOCONVERT
) {
1285 *ino
= INT_GET(rec
->ir_startino
, ARCH_CONVERT
);
1286 *fcnt
= INT_GET(rec
->ir_freecount
, ARCH_CONVERT
);
1287 *free
= INT_GET(rec
->ir_free
, ARCH_CONVERT
);
1289 INT_COPY(*ino
, rec
->ir_startino
, ARCH_CONVERT
);
1290 INT_COPY(*fcnt
, rec
->ir_freecount
, ARCH_CONVERT
);
1291 INT_COPY(*free
, rec
->ir_free
, ARCH_CONVERT
);
1298 * Increment cursor by one record at the level.
1299 * For nonzero levels the leaf-ward information is untouched.
1302 xfs_inobt_increment(
1303 xfs_btree_cur_t
*cur
, /* btree cursor */
1304 int level
, /* level in btree, 0 is leaf */
1305 int *stat
) /* success/failure */
1307 xfs_inobt_block_t
*block
; /* btree block */
1308 xfs_buf_t
*bp
; /* buffer containing btree block */
1309 int error
; /* error return value */
1310 int lev
; /* btree level */
1312 ASSERT(level
< cur
->bc_nlevels
);
1314 * Read-ahead to the right at this level.
1316 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1318 * Get a pointer to the btree block.
1320 bp
= cur
->bc_bufs
[level
];
1321 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1323 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1327 * Increment the ptr at this level. If we're still in the block
1330 if (++cur
->bc_ptrs
[level
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
1335 * If we just went off the right edge of the tree, return failure.
1337 if (INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1342 * March up the tree incrementing pointers.
1343 * Stop when we don't go off the right edge of a block.
1345 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1346 bp
= cur
->bc_bufs
[lev
];
1347 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1349 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1352 if (++cur
->bc_ptrs
[lev
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
1355 * Read-ahead the right block, we're going to read it
1358 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1361 * If we went off the root then we are seriously confused.
1363 ASSERT(lev
< cur
->bc_nlevels
);
1365 * Now walk back down the tree, fixing up the cursor's buffer
1366 * pointers and key numbers.
1368 for (bp
= cur
->bc_bufs
[lev
], block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1370 xfs_agblock_t agbno
; /* block number of btree block */
1372 agbno
= INT_GET(*XFS_INOBT_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1373 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1374 cur
->bc_private
.i
.agno
, agbno
, 0, &bp
,
1375 XFS_INO_BTREE_REF
)))
1378 xfs_btree_setbuf(cur
, lev
, bp
);
1379 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1380 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1382 cur
->bc_ptrs
[lev
] = 1;
1389 * Insert the current record at the point referenced by cur.
1390 * The cursor may be inconsistent on return if splits have been done.
1394 xfs_btree_cur_t
*cur
, /* btree cursor */
1395 int *stat
) /* success/failure */
1397 int error
; /* error return value */
1398 int i
; /* result value, 0 for failure */
1399 int level
; /* current level number in btree */
1400 xfs_agblock_t nbno
; /* new block number (split result) */
1401 xfs_btree_cur_t
*ncur
; /* new cursor (split result) */
1402 xfs_inobt_rec_t nrec
; /* record being inserted this level */
1403 xfs_btree_cur_t
*pcur
; /* previous level's cursor */
1407 INT_SET(nrec
.ir_startino
, ARCH_CONVERT
, cur
->bc_rec
.i
.ir_startino
);
1408 INT_SET(nrec
.ir_freecount
, ARCH_CONVERT
, cur
->bc_rec
.i
.ir_freecount
);
1409 INT_SET(nrec
.ir_free
, ARCH_CONVERT
, cur
->bc_rec
.i
.ir_free
);
1410 ncur
= (xfs_btree_cur_t
*)0;
1413 * Loop going up the tree, starting at the leaf level.
1414 * Stop when we don't get a split block, that must mean that
1415 * the insert is finished with this level.
1419 * Insert nrec/nbno into this level of the tree.
1420 * Note if we fail, nbno will be null.
1422 if ((error
= xfs_inobt_insrec(pcur
, level
++, &nbno
, &nrec
, &ncur
,
1425 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
1429 * See if the cursor we just used is trash.
1430 * Can't trash the caller's cursor, but otherwise we should
1431 * if ncur is a new cursor or we're about to be done.
1433 if (pcur
!= cur
&& (ncur
|| nbno
== NULLAGBLOCK
)) {
1434 cur
->bc_nlevels
= pcur
->bc_nlevels
;
1435 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
1438 * If we got a new cursor, switch to it.
1442 ncur
= (xfs_btree_cur_t
*)0;
1444 } while (nbno
!= NULLAGBLOCK
);
1450 * Lookup the record equal to ino in the btree given by cur.
1453 xfs_inobt_lookup_eq(
1454 xfs_btree_cur_t
*cur
, /* btree cursor */
1455 xfs_agino_t ino
, /* starting inode of chunk */
1456 __int32_t fcnt
, /* free inode count */
1457 xfs_inofree_t free
, /* free inode mask */
1458 int *stat
) /* success/failure */
1460 cur
->bc_rec
.i
.ir_startino
= ino
;
1461 cur
->bc_rec
.i
.ir_freecount
= fcnt
;
1462 cur
->bc_rec
.i
.ir_free
= free
;
1463 return xfs_inobt_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
1467 * Lookup the first record greater than or equal to ino
1468 * in the btree given by cur.
1471 xfs_inobt_lookup_ge(
1472 xfs_btree_cur_t
*cur
, /* btree cursor */
1473 xfs_agino_t ino
, /* starting inode of chunk */
1474 __int32_t fcnt
, /* free inode count */
1475 xfs_inofree_t free
, /* free inode mask */
1476 int *stat
) /* success/failure */
1478 cur
->bc_rec
.i
.ir_startino
= ino
;
1479 cur
->bc_rec
.i
.ir_freecount
= fcnt
;
1480 cur
->bc_rec
.i
.ir_free
= free
;
1481 return xfs_inobt_lookup(cur
, XFS_LOOKUP_GE
, stat
);
1485 * Lookup the first record less than or equal to ino
1486 * in the btree given by cur.
1489 xfs_inobt_lookup_le(
1490 xfs_btree_cur_t
*cur
, /* btree cursor */
1491 xfs_agino_t ino
, /* starting inode of chunk */
1492 __int32_t fcnt
, /* free inode count */
1493 xfs_inofree_t free
, /* free inode mask */
1494 int *stat
) /* success/failure */
1496 cur
->bc_rec
.i
.ir_startino
= ino
;
1497 cur
->bc_rec
.i
.ir_freecount
= fcnt
;
1498 cur
->bc_rec
.i
.ir_free
= free
;
1499 return xfs_inobt_lookup(cur
, XFS_LOOKUP_LE
, stat
);
1503 * Update the record referred to by cur, to the value given
1504 * by [ino, fcnt, free].
1505 * This either works (return 0) or gets an EFSCORRUPTED error.
1509 xfs_btree_cur_t
*cur
, /* btree cursor */
1510 xfs_agino_t ino
, /* starting inode of chunk */
1511 __int32_t fcnt
, /* free inode count */
1512 xfs_inofree_t free
) /* free inode mask */
1514 xfs_inobt_block_t
*block
; /* btree block to update */
1515 xfs_buf_t
*bp
; /* buffer containing btree block */
1516 int error
; /* error return value */
1517 int ptr
; /* current record number (updating) */
1518 xfs_inobt_rec_t
*rp
; /* pointer to updated record */
1521 * Pick up the current block.
1523 bp
= cur
->bc_bufs
[0];
1524 block
= XFS_BUF_TO_INOBT_BLOCK(bp
);
1526 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, bp
)))
1530 * Get the address of the rec to be updated.
1532 ptr
= cur
->bc_ptrs
[0];
1533 rp
= XFS_INOBT_REC_ADDR(block
, ptr
, cur
);
1535 * Fill in the new contents and log them.
1537 INT_SET(rp
->ir_startino
, ARCH_CONVERT
, ino
);
1538 INT_SET(rp
->ir_freecount
, ARCH_CONVERT
, fcnt
);
1539 INT_SET(rp
->ir_free
, ARCH_CONVERT
, free
);
1540 xfs_inobt_log_recs(cur
, bp
, ptr
, ptr
);
1542 * Updating first record in leaf. Pass new key value up to our parent.
1545 xfs_inobt_key_t key
; /* key containing [ino] */
1547 INT_SET(key
.ir_startino
, ARCH_CONVERT
, ino
);
1548 if ((error
= xfs_inobt_updkey(cur
, &key
, 1)))