]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_alloc_btree.c
2 * Copyright (c) 2000 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 * Free space allocation for XFS.
40 * Single level of the xfs_alloc_delete record deletion routine.
41 * Delete record pointed to by cur/level.
42 * Remove the record from its block then rebalance the tree.
43 * Return 0 for error, 1 for done, 2 to go on to the next level.
45 STATIC
int /* error */
47 xfs_btree_cur_t
*cur
, /* btree cursor */
48 int level
, /* level removing record from */
49 int *stat
) /* fail/done/go-on */
51 xfs_agf_t
*agf
; /* allocation group freelist header */
52 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
53 xfs_agblock_t bno
; /* btree block number */
54 xfs_buf_t
*bp
; /* buffer for block */
55 int error
; /* error return value */
56 int i
; /* loop index */
57 xfs_alloc_key_t key
; /* kp points here if block is level 0 */
58 xfs_agblock_t lbno
; /* left block's block number */
59 xfs_buf_t
*lbp
; /* left block's buffer pointer */
60 xfs_alloc_block_t
*left
; /* left btree block */
61 xfs_alloc_key_t
*lkp
; /* left block key pointer */
62 xfs_alloc_ptr_t
*lpp
; /* left block address pointer */
63 int lrecs
; /* number of records in left block */
64 xfs_alloc_rec_t
*lrp
; /* left block record pointer */
65 xfs_mount_t
*mp
; /* mount structure */
66 int ptr
; /* index in btree block for this rec */
67 xfs_agblock_t rbno
; /* right block's block number */
68 xfs_buf_t
*rbp
; /* right block's buffer pointer */
69 xfs_alloc_block_t
*right
; /* right btree block */
70 xfs_alloc_key_t
*rkp
; /* right block key pointer */
71 xfs_alloc_ptr_t
*rpp
; /* right block address pointer */
72 int rrecs
; /* number of records in right block */
73 xfs_alloc_rec_t
*rrp
; /* right block record pointer */
74 xfs_btree_cur_t
*tcur
; /* temporary btree cursor */
77 * Get the index of the entry being deleted, check for nothing there.
79 ptr
= cur
->bc_ptrs
[level
];
85 * Get the buffer & block containing the record or key/ptr.
87 bp
= cur
->bc_bufs
[level
];
88 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
90 if (error
= xfs_btree_check_sblock(cur
, block
, level
, bp
))
94 * Fail if we're off the end of the block.
96 if (ptr
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
100 XFS_STATS_INC(xs_abt_delrec
);
102 * It's a nonleaf. Excise the key and ptr being deleted, by
103 * sliding the entries past them down one.
104 * Log the changed areas of the block.
107 lkp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
108 lpp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
110 for (i
= ptr
; i
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
); i
++) {
111 if (error
= xfs_btree_check_sptr(cur
, INT_GET(lpp
[i
], ARCH_CONVERT
), level
))
115 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
116 ovbcopy(&lkp
[ptr
], &lkp
[ptr
- 1],
117 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
) * sizeof(*lkp
)); /* INT_: mem copy */
118 ovbcopy(&lpp
[ptr
], &lpp
[ptr
- 1],
119 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
) * sizeof(*lpp
)); /* INT_: mem copy */
120 xfs_alloc_log_ptrs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - 1);
121 xfs_alloc_log_keys(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - 1);
125 * It's a leaf. Excise the record being deleted, by sliding the
126 * entries past it down one. Log the changed areas of the block.
129 lrp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
130 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
131 ovbcopy(&lrp
[ptr
], &lrp
[ptr
- 1],
132 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
) * sizeof(*lrp
));
133 xfs_alloc_log_recs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - 1);
136 * If it's the first record in the block, we'll need a key
137 * structure to pass up to the next level (updkey).
140 key
.ar_startblock
= lrp
->ar_startblock
; /* INT_: direct copy */
141 key
.ar_blockcount
= lrp
->ar_blockcount
; /* INT_: direct copy */
146 * Decrement and log the number of entries in the block.
148 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, -1);
149 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
151 * See if the longest free extent in the allocation group was
152 * changed by this operation. True if it's the by-size btree, and
153 * this is the leaf level, and there is no right sibling block,
154 * and this was the last record.
156 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
160 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
161 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
&&
162 ptr
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
163 ASSERT(ptr
== INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) + 1);
165 * There are still records in the block. Grab the size
168 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
169 rrp
= XFS_ALLOC_REC_ADDR(block
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
), cur
);
170 INT_COPY(agf
->agf_longest
, rrp
->ar_blockcount
, ARCH_CONVERT
);
173 * No free extents left.
176 INT_ZERO(agf
->agf_longest
, ARCH_CONVERT
);
177 mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)].pagf_longest
=
178 INT_GET(agf
->agf_longest
, ARCH_CONVERT
);
179 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
183 * Is this the root level? If so, we're almost done.
185 if (level
== cur
->bc_nlevels
- 1) {
187 * If this is the root level,
188 * and there's only one entry left,
189 * and it's NOT the leaf level,
190 * then we can get rid of this level.
192 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) == 1 && level
> 0) {
194 * lpp is still set to the first pointer in the block.
195 * Make it the new root of the btree.
197 bno
= INT_GET(agf
->agf_roots
[cur
->bc_btnum
], ARCH_CONVERT
);
198 INT_COPY(agf
->agf_roots
[cur
->bc_btnum
], *lpp
, ARCH_CONVERT
);
199 INT_MOD(agf
->agf_levels
[cur
->bc_btnum
], ARCH_CONVERT
, -1);
200 mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)].pagf_levels
[cur
->bc_btnum
]--;
202 * Put this buffer/block on the ag's freelist.
204 if (error
= xfs_alloc_put_freelist(cur
->bc_tp
,
205 cur
->bc_private
.a
.agbp
, NULL
, bno
))
207 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
208 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
209 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
211 * Update the cursor so there's one fewer level.
213 xfs_btree_setbuf(cur
, level
, 0);
215 } else if (level
> 0 &&
216 (error
= xfs_alloc_decrement(cur
, level
, &i
)))
222 * If we deleted the leftmost entry in the block, update the
223 * key values above us in the tree.
225 if (ptr
== 1 && (error
= xfs_alloc_updkey(cur
, lkp
, level
+ 1)))
228 * If the number of records remaining in the block is at least
229 * the minimum, we're done.
231 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >= XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
232 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
238 * Otherwise, we have to move some records around to keep the
239 * tree balanced. Look at the left and right sibling blocks to
240 * see if we can re-balance by moving only one record.
242 rbno
= INT_GET(block
->bb_rightsib
, ARCH_CONVERT
);
243 lbno
= INT_GET(block
->bb_leftsib
, ARCH_CONVERT
);
245 ASSERT(rbno
!= NULLAGBLOCK
|| lbno
!= NULLAGBLOCK
);
247 * Duplicate the cursor so our btree manipulations here won't
248 * disrupt the next level up.
250 if (error
= xfs_btree_dup_cursor(cur
, &tcur
))
253 * If there's a right sibling, see if it's ok to shift an entry
256 if (rbno
!= NULLAGBLOCK
) {
258 * Move the temp cursor to the last entry in the next block.
259 * Actually any entry but the first would suffice.
261 i
= xfs_btree_lastrec(tcur
, level
);
262 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
263 if (error
= xfs_alloc_increment(tcur
, level
, &i
))
265 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
266 i
= xfs_btree_lastrec(tcur
, level
);
267 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
269 * Grab a pointer to the block.
271 rbp
= tcur
->bc_bufs
[level
];
272 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
274 if (error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
))
278 * Grab the current block number, for future use.
280 bno
= INT_GET(right
->bb_leftsib
, ARCH_CONVERT
);
282 * If right block is full enough so that removing one entry
283 * won't make it too empty, and left-shifting an entry out
284 * of right to us works, we're done.
286 if (INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) - 1 >=
287 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
288 if (error
= xfs_alloc_lshift(tcur
, level
, &i
))
291 ASSERT(INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >=
292 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
293 xfs_btree_del_cursor(tcur
,
296 (error
= xfs_alloc_decrement(cur
, level
,
304 * Otherwise, grab the number of records in right for
305 * future reference, and fix up the temp cursor to point
306 * to our block again (last record).
308 rrecs
= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
);
309 if (lbno
!= NULLAGBLOCK
) {
310 i
= xfs_btree_firstrec(tcur
, level
);
311 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
312 if (error
= xfs_alloc_decrement(tcur
, level
, &i
))
314 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
318 * If there's a left sibling, see if it's ok to shift an entry
321 if (lbno
!= NULLAGBLOCK
) {
323 * Move the temp cursor to the first entry in the
326 i
= xfs_btree_firstrec(tcur
, level
);
327 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
328 if (error
= xfs_alloc_decrement(tcur
, level
, &i
))
330 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
331 xfs_btree_firstrec(tcur
, level
);
333 * Grab a pointer to the block.
335 lbp
= tcur
->bc_bufs
[level
];
336 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
338 if (error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
))
342 * Grab the current block number, for future use.
344 bno
= INT_GET(left
->bb_rightsib
, ARCH_CONVERT
);
346 * If left block is full enough so that removing one entry
347 * won't make it too empty, and right-shifting an entry out
348 * of left to us works, we're done.
350 if (INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) - 1 >=
351 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
352 if (error
= xfs_alloc_rshift(tcur
, level
, &i
))
355 ASSERT(INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >=
356 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
357 xfs_btree_del_cursor(tcur
,
366 * Otherwise, grab the number of records in right for
369 lrecs
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
372 * Delete the temp cursor, we're done with it.
374 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
376 * If here, we need to do a join to keep the tree balanced.
378 ASSERT(bno
!= NULLAGBLOCK
);
380 * See if we can join with the left neighbor block.
382 if (lbno
!= NULLAGBLOCK
&&
383 lrecs
+ INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) <= XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
385 * Set "right" to be the starting block,
386 * "left" to be the left neighbor.
391 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
392 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
393 XFS_ALLOC_BTREE_REF
))
395 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
396 if (error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
))
400 * If that won't work, see if we can join with the right neighbor block.
402 else if (rbno
!= NULLAGBLOCK
&&
403 rrecs
+ INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) <=
404 XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
406 * Set "left" to be the starting block,
407 * "right" to be the right neighbor.
412 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
413 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
414 XFS_ALLOC_BTREE_REF
))
416 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
417 if (error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
))
421 * Otherwise, we can't fix the imbalance.
422 * Just return. This is probably a logic error, but it's not fatal.
425 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
431 * We're now going to join "left" and "right" by moving all the stuff
432 * in "right" to "left" and deleting "right".
436 * It's a non-leaf. Move keys and pointers.
438 lkp
= XFS_ALLOC_KEY_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
439 lpp
= XFS_ALLOC_PTR_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
440 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
441 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
443 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
444 if (error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
], ARCH_CONVERT
), level
))
448 bcopy(rkp
, lkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lkp
)); /* INT_: structure copy */
449 bcopy(rpp
, lpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lpp
)); /* INT_: structure copy */
450 xfs_alloc_log_keys(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
451 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
452 xfs_alloc_log_ptrs(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
453 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
456 * It's a leaf. Move records.
458 lrp
= XFS_ALLOC_REC_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
459 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
460 bcopy(rrp
, lrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lrp
));
461 xfs_alloc_log_recs(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
462 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
465 * If we joined with the left neighbor, set the buffer in the
466 * cursor to the left block, and fix up the index.
469 xfs_btree_setbuf(cur
, level
, lbp
);
470 cur
->bc_ptrs
[level
] += INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
473 * If we joined with the right neighbor and there's a level above
474 * us, increment the cursor at that level.
476 else if (level
+ 1 < cur
->bc_nlevels
&&
477 (error
= xfs_alloc_increment(cur
, level
+ 1, &i
)))
480 * Fix up the number of records in the surviving block.
482 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
484 * Fix up the right block pointer in the surviving block, and log it.
486 left
->bb_rightsib
= right
->bb_rightsib
; /* INT_: direct copy */
487 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
489 * If there is a right sibling now, make it point to the
492 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
493 xfs_alloc_block_t
*rrblock
;
496 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
497 cur
->bc_private
.a
.agno
, INT_GET(left
->bb_rightsib
, ARCH_CONVERT
), 0,
498 &rrbp
, XFS_ALLOC_BTREE_REF
))
500 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
501 if (error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
))
503 INT_SET(rrblock
->bb_leftsib
, ARCH_CONVERT
, lbno
);
504 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
507 * Free the deleting block by putting it on the freelist.
509 if (error
= xfs_alloc_put_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
512 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
514 * Adjust the current level's cursor so that we're left referring
515 * to the right node, after we're done.
516 * If this leaves the ptr value 0 our caller will fix it up.
519 cur
->bc_ptrs
[level
]--;
521 * Return value means the next level up has something to do.
527 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
532 * Insert one record/level. Return information to the caller
533 * allowing the next level up to proceed if necessary.
535 STATIC
int /* error */
537 xfs_btree_cur_t
*cur
, /* btree cursor */
538 int level
, /* level to insert record at */
539 xfs_agblock_t
*bnop
, /* i/o: block number inserted */
540 xfs_alloc_rec_t
*recp
, /* i/o: record data inserted */
541 xfs_btree_cur_t
**curp
, /* output: new cursor replacing cur */
542 int *stat
) /* output: success/failure */
544 xfs_agf_t
*agf
; /* allocation group freelist header */
545 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
546 xfs_buf_t
*bp
; /* buffer for block */
547 int error
; /* error return value */
548 int i
; /* loop index */
549 xfs_alloc_key_t key
; /* key value being inserted */
550 xfs_alloc_key_t
*kp
; /* pointer to btree keys */
551 xfs_agblock_t nbno
; /* block number of allocated block */
552 xfs_btree_cur_t
*ncur
; /* new cursor to be used at next lvl */
553 xfs_alloc_key_t nkey
; /* new key value, from split */
554 xfs_alloc_rec_t nrec
; /* new record value, for caller */
555 int optr
; /* old ptr value */
556 xfs_alloc_ptr_t
*pp
; /* pointer to btree addresses */
557 int ptr
; /* index in btree block for this rec */
558 xfs_alloc_rec_t
*rp
; /* pointer to btree records */
560 ASSERT(INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
) > 0);
562 * If we made it to the root level, allocate a new root block
565 if (level
>= cur
->bc_nlevels
) {
566 XFS_STATS_INC(xs_abt_insrec
);
567 if (error
= xfs_alloc_newroot(cur
, &i
))
574 * Make a key out of the record data to be inserted, and save it.
576 key
.ar_startblock
= recp
->ar_startblock
; /* INT_: direct copy */
577 key
.ar_blockcount
= recp
->ar_blockcount
; /* INT_: direct copy */
578 optr
= ptr
= cur
->bc_ptrs
[level
];
580 * If we're off the left edge, return failure.
586 XFS_STATS_INC(xs_abt_insrec
);
588 * Get pointers to the btree buffer and block.
590 bp
= cur
->bc_bufs
[level
];
591 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
593 if (error
= xfs_btree_check_sblock(cur
, block
, level
, bp
))
596 * Check that the new entry is being inserted in the right place.
598 if (ptr
<= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
600 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
601 xfs_btree_check_rec(cur
->bc_btnum
, recp
, rp
);
603 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
604 xfs_btree_check_key(cur
->bc_btnum
, &key
, kp
);
609 ncur
= (xfs_btree_cur_t
*)0;
611 * If the block is full, we can't insert the new entry until we
612 * make the block un-full.
614 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
616 * First, try shifting an entry to the right neighbor.
618 if (error
= xfs_alloc_rshift(cur
, level
, &i
))
624 * Next, try shifting an entry to the left neighbor.
627 if (error
= xfs_alloc_lshift(cur
, level
, &i
))
630 optr
= ptr
= cur
->bc_ptrs
[level
];
633 * Next, try splitting the current block in
634 * half. If this works we have to re-set our
635 * variables because we could be in a
636 * different block now.
638 if (error
= xfs_alloc_split(cur
, level
, &nbno
,
642 bp
= cur
->bc_bufs
[level
];
643 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
646 xfs_btree_check_sblock(cur
,
650 ptr
= cur
->bc_ptrs
[level
];
651 nrec
.ar_startblock
= nkey
.ar_startblock
; /* INT_: direct copy */
652 nrec
.ar_blockcount
= nkey
.ar_blockcount
; /* INT_: direct copy */
655 * Otherwise the insert fails.
665 * At this point we know there's room for our new entry in the block
670 * It's a non-leaf entry. Make a hole for the new data
671 * in the key and ptr regions of the block.
673 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
674 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
676 for (i
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
); i
>= ptr
; i
--) {
677 if (error
= xfs_btree_check_sptr(cur
, INT_GET(pp
[i
- 1], ARCH_CONVERT
), level
))
681 ovbcopy(&kp
[ptr
- 1], &kp
[ptr
],
682 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*kp
)); /* INT_: copy */
683 ovbcopy(&pp
[ptr
- 1], &pp
[ptr
],
684 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*pp
)); /* INT_: copy */
686 if (error
= xfs_btree_check_sptr(cur
, *bnop
, level
))
690 * Now stuff the new data in, bump numrecs and log the new data.
693 INT_SET(pp
[ptr
- 1], ARCH_CONVERT
, *bnop
);
694 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
695 xfs_alloc_log_keys(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
696 xfs_alloc_log_ptrs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
698 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
699 xfs_btree_check_key(cur
->bc_btnum
, kp
+ ptr
- 1,
704 * It's a leaf entry. Make a hole for the new record.
706 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
707 ovbcopy(&rp
[ptr
- 1], &rp
[ptr
],
708 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*rp
));
710 * Now stuff the new record in, bump numrecs
711 * and log the new data.
713 rp
[ptr
- 1] = *recp
; /* INT_: struct copy */
714 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
715 xfs_alloc_log_recs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
717 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
718 xfs_btree_check_rec(cur
->bc_btnum
, rp
+ ptr
- 1,
723 * Log the new number of records in the btree header.
725 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
727 * If we inserted at the start of a block, update the parents' keys.
729 if (optr
== 1 && (error
= xfs_alloc_updkey(cur
, &key
, level
+ 1)))
732 * Look to see if the longest extent in the allocation group
733 * needs to be updated.
736 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
738 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
739 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
&&
740 INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
) > INT_GET(agf
->agf_longest
, ARCH_CONVERT
)) {
742 * If this is a leaf in the by-size btree and there
743 * is no right sibling block and this block is bigger
744 * than the previous longest block, update it.
746 INT_COPY(agf
->agf_longest
, recp
->ar_blockcount
, ARCH_CONVERT
);
747 cur
->bc_mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)].pagf_longest
748 = INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
);
749 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
753 * Return the new block number, if any.
754 * If there is one, give back a record value and a cursor too.
757 if (nbno
!= NULLAGBLOCK
) {
758 *recp
= nrec
; /* INT_: struct copy */
759 *curp
= ncur
; /* INT_: struct copy */
766 * Log header fields from a btree block.
770 xfs_trans_t
*tp
, /* transaction pointer */
771 xfs_buf_t
*bp
, /* buffer containing btree block */
772 int fields
) /* mask of fields: XFS_BB_... */
774 int first
; /* first byte offset logged */
775 int last
; /* last byte offset logged */
776 static const short offsets
[] = { /* table of offsets */
777 offsetof(xfs_alloc_block_t
, bb_magic
),
778 offsetof(xfs_alloc_block_t
, bb_level
),
779 offsetof(xfs_alloc_block_t
, bb_numrecs
),
780 offsetof(xfs_alloc_block_t
, bb_leftsib
),
781 offsetof(xfs_alloc_block_t
, bb_rightsib
),
782 sizeof(xfs_alloc_block_t
)
785 xfs_btree_offsets(fields
, offsets
, XFS_BB_NUM_BITS
, &first
, &last
);
786 xfs_trans_log_buf(tp
, bp
, first
, last
);
790 * Log keys from a btree block (nonleaf).
794 xfs_btree_cur_t
*cur
, /* btree cursor */
795 xfs_buf_t
*bp
, /* buffer containing btree block */
796 int kfirst
, /* index of first key to log */
797 int klast
) /* index of last key to log */
799 xfs_alloc_block_t
*block
; /* btree block to log from */
800 int first
; /* first byte offset logged */
801 xfs_alloc_key_t
*kp
; /* key pointer in btree block */
802 int last
; /* last byte offset logged */
804 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
805 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
806 first
= (int)((xfs_caddr_t
)&kp
[kfirst
- 1] - (xfs_caddr_t
)block
);
807 last
= (int)(((xfs_caddr_t
)&kp
[klast
] - 1) - (xfs_caddr_t
)block
);
808 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
812 * Log block pointer fields from a btree block (nonleaf).
816 xfs_btree_cur_t
*cur
, /* btree cursor */
817 xfs_buf_t
*bp
, /* buffer containing btree block */
818 int pfirst
, /* index of first pointer to log */
819 int plast
) /* index of last pointer to log */
821 xfs_alloc_block_t
*block
; /* btree block to log from */
822 int first
; /* first byte offset logged */
823 int last
; /* last byte offset logged */
824 xfs_alloc_ptr_t
*pp
; /* block-pointer pointer in btree blk */
826 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
827 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
828 first
= (int)((xfs_caddr_t
)&pp
[pfirst
- 1] - (xfs_caddr_t
)block
);
829 last
= (int)(((xfs_caddr_t
)&pp
[plast
] - 1) - (xfs_caddr_t
)block
);
830 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
834 * Log records from a btree block (leaf).
838 xfs_btree_cur_t
*cur
, /* btree cursor */
839 xfs_buf_t
*bp
, /* buffer containing btree block */
840 int rfirst
, /* index of first record to log */
841 int rlast
) /* index of last record to log */
843 xfs_alloc_block_t
*block
; /* btree block to log from */
844 int first
; /* first byte offset logged */
845 int last
; /* last byte offset logged */
846 xfs_alloc_rec_t
*rp
; /* record pointer for btree block */
849 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
850 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
856 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
857 for (p
= &rp
[rfirst
- 1]; p
<= &rp
[rlast
- 1]; p
++)
858 ASSERT(INT_GET(p
->ar_startblock
, ARCH_CONVERT
) + INT_GET(p
->ar_blockcount
, ARCH_CONVERT
) <=
859 INT_GET(agf
->agf_length
, ARCH_CONVERT
));
862 first
= (int)((xfs_caddr_t
)&rp
[rfirst
- 1] - (xfs_caddr_t
)block
);
863 last
= (int)(((xfs_caddr_t
)&rp
[rlast
] - 1) - (xfs_caddr_t
)block
);
864 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
868 * Lookup the record. The cursor is made to point to it, based on dir.
869 * Return 0 if can't find any such record, 1 for success.
871 STATIC
int /* error */
873 xfs_btree_cur_t
*cur
, /* btree cursor */
874 xfs_lookup_t dir
, /* <=, ==, or >= */
875 int *stat
) /* success/failure */
877 xfs_agblock_t agbno
; /* a.g. relative btree block number */
878 xfs_agnumber_t agno
; /* allocation group number */
879 xfs_alloc_block_t
*block
; /* current btree block */
880 int diff
; /* difference for the current key */
881 int error
; /* error return value */
882 int keyno
; /* current key number */
883 int level
; /* level in the btree */
884 xfs_mount_t
*mp
; /* file system mount point */
886 XFS_STATS_INC(xs_abt_lookup
);
888 * Get the allocation group header, and the root block number.
893 xfs_agf_t
*agf
; /* a.g. freespace header */
895 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
896 agno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
897 agbno
= INT_GET(agf
->agf_roots
[cur
->bc_btnum
], ARCH_CONVERT
);
900 * Iterate over each level in the btree, starting at the root.
901 * For each level above the leaves, find the key we need, based
902 * on the lookup record, then follow the corresponding block
903 * pointer down to the next level.
905 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
906 xfs_buf_t
*bp
; /* buffer pointer for btree block */
907 xfs_daddr_t d
; /* disk address of btree block */
910 * Get the disk address we're looking for.
912 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
914 * If the old buffer at this level is for a different block,
915 * throw it away, otherwise just use it.
917 bp
= cur
->bc_bufs
[level
];
918 if (bp
&& XFS_BUF_ADDR(bp
) != d
)
922 * Need to get a new buffer. Read it, then
923 * set it in the cursor, releasing the old one.
925 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
, agno
,
926 agbno
, 0, &bp
, XFS_ALLOC_BTREE_REF
))
928 xfs_btree_setbuf(cur
, level
, bp
);
930 * Point to the btree block, now that we have the buffer
932 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
933 if (error
= xfs_btree_check_sblock(cur
, block
, level
,
937 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
939 * If we already had a key match at a higher level, we know
940 * we need to use the first entry in this block.
945 * Otherwise we need to search this block. Do a binary search.
948 int high
; /* high entry number */
949 xfs_alloc_key_t
*kkbase
;/* base of keys in block */
950 xfs_alloc_rec_t
*krbase
;/* base of records in block */
951 int low
; /* low entry number */
954 * Get a pointer to keys or records.
957 kkbase
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
959 krbase
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
961 * Set low and high entry numbers, 1-based.
964 if (!(high
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))) {
966 * If the block is empty, the tree must
969 ASSERT(level
== 0 && cur
->bc_nlevels
== 1);
970 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
975 * Binary search the block.
977 while (low
<= high
) {
978 xfs_extlen_t blockcount
; /* key value */
979 xfs_agblock_t startblock
; /* key value */
981 XFS_STATS_INC(xs_abt_compare
);
983 * keyno is average of low and high.
985 keyno
= (low
+ high
) >> 1;
987 * Get startblock & blockcount.
990 xfs_alloc_key_t
*kkp
;
992 kkp
= kkbase
+ keyno
- 1;
993 startblock
= INT_GET(kkp
->ar_startblock
, ARCH_CONVERT
);
994 blockcount
= INT_GET(kkp
->ar_blockcount
, ARCH_CONVERT
);
996 xfs_alloc_rec_t
*krp
;
998 krp
= krbase
+ keyno
- 1;
999 startblock
= INT_GET(krp
->ar_startblock
, ARCH_CONVERT
);
1000 blockcount
= INT_GET(krp
->ar_blockcount
, ARCH_CONVERT
);
1003 * Compute difference to get next direction.
1005 if (cur
->bc_btnum
== XFS_BTNUM_BNO
)
1006 diff
= (int)startblock
-
1007 (int)cur
->bc_rec
.a
.ar_startblock
;
1008 else if (!(diff
= (int)blockcount
-
1009 (int)cur
->bc_rec
.a
.ar_blockcount
))
1010 diff
= (int)startblock
-
1011 (int)cur
->bc_rec
.a
.ar_startblock
;
1013 * Less than, move right.
1018 * Greater than, move left.
1023 * Equal, we're done.
1030 * If there are more levels, set up for the next level
1031 * by getting the block number and filling in the cursor.
1035 * If we moved left, need the previous key number,
1036 * unless there isn't one.
1038 if (diff
> 0 && --keyno
< 1)
1040 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, keyno
, cur
), ARCH_CONVERT
);
1042 if (error
= xfs_btree_check_sptr(cur
, agbno
, level
))
1045 cur
->bc_ptrs
[level
] = keyno
;
1049 * Done with the search.
1050 * See if we need to adjust the results.
1052 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1055 * If ge search and we went off the end of the block, but it's
1056 * not the last block, we're in the wrong block.
1058 if (dir
== XFS_LOOKUP_GE
&&
1059 keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) &&
1060 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1063 cur
->bc_ptrs
[0] = keyno
;
1064 if (error
= xfs_alloc_increment(cur
, 0, &i
))
1066 XFS_WANT_CORRUPTED_RETURN(i
== 1);
1071 else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
1073 cur
->bc_ptrs
[0] = keyno
;
1075 * Return if we succeeded or not.
1077 if (keyno
== 0 || keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
1080 *stat
= ((dir
!= XFS_LOOKUP_EQ
) || (diff
== 0));
1085 * Move 1 record left from cur/level if possible.
1086 * Update cur to reflect the new path.
1088 STATIC
int /* error */
1090 xfs_btree_cur_t
*cur
, /* btree cursor */
1091 int level
, /* level to shift record on */
1092 int *stat
) /* success/failure */
1094 int error
; /* error return value */
1096 int i
; /* loop index */
1098 xfs_alloc_key_t key
; /* key value for leaf level upward */
1099 xfs_buf_t
*lbp
; /* buffer for left neighbor block */
1100 xfs_alloc_block_t
*left
; /* left neighbor btree block */
1101 int nrec
; /* new number of left block entries */
1102 xfs_buf_t
*rbp
; /* buffer for right (current) block */
1103 xfs_alloc_block_t
*right
; /* right (current) btree block */
1104 xfs_alloc_key_t
*rkp
; /* key pointer for right block */
1105 xfs_alloc_ptr_t
*rpp
; /* address pointer for right block */
1106 xfs_alloc_rec_t
*rrp
; /* record pointer for right block */
1109 * Set up variables for this block as "right".
1111 rbp
= cur
->bc_bufs
[level
];
1112 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1114 if (error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
))
1118 * If we've got no left sibling then we can't shift an entry left.
1120 if (INT_GET(right
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1125 * If the cursor entry is the one that would be moved, don't
1126 * do it... it's too complicated.
1128 if (cur
->bc_ptrs
[level
] <= 1) {
1133 * Set up the left neighbor as "left".
1135 if (error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1136 cur
->bc_private
.a
.agno
, INT_GET(right
->bb_leftsib
, ARCH_CONVERT
), 0, &lbp
,
1137 XFS_ALLOC_BTREE_REF
))
1139 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1140 if (error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
))
1143 * If it's full, it can't take another entry.
1145 if (INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1149 nrec
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1;
1151 * If non-leaf, copy a key and a ptr to the left block.
1154 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1155 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1157 lkp
= XFS_ALLOC_KEY_ADDR(left
, nrec
, cur
);
1158 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1160 xfs_alloc_log_keys(cur
, lbp
, nrec
, nrec
);
1161 lpp
= XFS_ALLOC_PTR_ADDR(left
, nrec
, cur
);
1162 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1164 if (error
= xfs_btree_check_sptr(cur
, INT_GET(*rpp
, ARCH_CONVERT
), level
))
1167 *lpp
= *rpp
; /* INT_: copy */
1168 xfs_alloc_log_ptrs(cur
, lbp
, nrec
, nrec
);
1169 xfs_btree_check_key(cur
->bc_btnum
, lkp
- 1, lkp
);
1172 * If leaf, copy a record to the left block.
1175 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1177 lrp
= XFS_ALLOC_REC_ADDR(left
, nrec
, cur
);
1178 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1180 xfs_alloc_log_recs(cur
, lbp
, nrec
, nrec
);
1181 xfs_btree_check_rec(cur
->bc_btnum
, lrp
- 1, lrp
);
1184 * Bump and log left's numrecs, decrement and log right's numrecs.
1186 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, +1);
1187 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1188 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, -1);
1189 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1191 * Slide the contents of right down one entry.
1195 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
1196 if (error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
+ 1], ARCH_CONVERT
),
1201 ovbcopy(rkp
+ 1, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
1202 ovbcopy(rpp
+ 1, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
1203 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1204 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1206 ovbcopy(rrp
+ 1, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1207 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1208 key
.ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1209 key
.ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1213 * Update the parent key values of right.
1215 if (error
= xfs_alloc_updkey(cur
, rkp
, level
+ 1))
1218 * Slide the cursor value left one.
1220 cur
->bc_ptrs
[level
]--;
1226 * Allocate a new root block, fill it in.
1228 STATIC
int /* error */
1230 xfs_btree_cur_t
*cur
, /* btree cursor */
1231 int *stat
) /* success/failure */
1233 int error
; /* error return value */
1234 xfs_agblock_t lbno
; /* left block number */
1235 xfs_buf_t
*lbp
; /* left btree buffer */
1236 xfs_alloc_block_t
*left
; /* left btree block */
1237 xfs_mount_t
*mp
; /* mount structure */
1238 xfs_agblock_t nbno
; /* new block number */
1239 xfs_buf_t
*nbp
; /* new (root) buffer */
1240 xfs_alloc_block_t
*new; /* new (root) btree block */
1241 int nptr
; /* new value for key index, 1 or 2 */
1242 xfs_agblock_t rbno
; /* right block number */
1243 xfs_buf_t
*rbp
; /* right btree buffer */
1244 xfs_alloc_block_t
*right
; /* right btree block */
1248 ASSERT(cur
->bc_nlevels
< XFS_AG_MAXLEVELS(mp
));
1250 * Get a buffer from the freelist blocks, for the new root.
1252 if (error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1256 * None available, we fail.
1258 if (nbno
== NULLAGBLOCK
) {
1262 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1263 nbp
= xfs_btree_get_bufs(mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
, nbno
,
1265 new = XFS_BUF_TO_ALLOC_BLOCK(nbp
);
1267 * Set the root data in the a.g. freespace structure.
1270 xfs_agf_t
*agf
; /* a.g. freespace header */
1271 xfs_agnumber_t seqno
;
1273 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
1274 INT_SET(agf
->agf_roots
[cur
->bc_btnum
], ARCH_CONVERT
, nbno
);
1275 INT_MOD(agf
->agf_levels
[cur
->bc_btnum
], ARCH_CONVERT
, 1);
1276 seqno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
1277 mp
->m_perag
[seqno
].pagf_levels
[cur
->bc_btnum
]++;
1278 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1279 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
1282 * At the previous root level there are now two blocks: the old
1283 * root, and the new block generated when it was split.
1284 * We don't know which one the cursor is pointing at, so we
1285 * set up variables "left" and "right" for each case.
1287 lbp
= cur
->bc_bufs
[cur
->bc_nlevels
- 1];
1288 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1290 if (error
= xfs_btree_check_sblock(cur
, left
, cur
->bc_nlevels
- 1, lbp
))
1293 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1295 * Our block is left, pick up the right block.
1297 lbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(lbp
));
1298 rbno
= INT_GET(left
->bb_rightsib
, ARCH_CONVERT
);
1299 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1300 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
1301 XFS_ALLOC_BTREE_REF
))
1303 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1304 if (error
= xfs_btree_check_sblock(cur
, right
,
1305 cur
->bc_nlevels
- 1, rbp
))
1310 * Our block is right, pick up the left block.
1314 rbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(rbp
));
1315 lbno
= INT_GET(right
->bb_leftsib
, ARCH_CONVERT
);
1316 if (error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1317 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
1318 XFS_ALLOC_BTREE_REF
))
1320 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1321 if (error
= xfs_btree_check_sblock(cur
, left
,
1322 cur
->bc_nlevels
- 1, lbp
))
1327 * Fill in the new block's btree header and log it.
1329 INT_SET(new->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
1330 INT_SET(new->bb_level
, ARCH_CONVERT
, (__uint16_t
)cur
->bc_nlevels
);
1331 INT_SET(new->bb_numrecs
, ARCH_CONVERT
, 2);
1332 INT_SET(new->bb_leftsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1333 INT_SET(new->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1334 xfs_alloc_log_block(cur
->bc_tp
, nbp
, XFS_BB_ALL_BITS
);
1335 ASSERT(lbno
!= NULLAGBLOCK
&& rbno
!= NULLAGBLOCK
);
1337 * Fill in the key data in the new root.
1340 xfs_alloc_key_t
*kp
; /* btree key pointer */
1342 kp
= XFS_ALLOC_KEY_ADDR(new, 1, cur
);
1343 if (INT_GET(left
->bb_level
, ARCH_CONVERT
) > 0) {
1344 kp
[0] = *XFS_ALLOC_KEY_ADDR(left
, 1, cur
); /* INT_: structure copy */
1345 kp
[1] = *XFS_ALLOC_KEY_ADDR(right
, 1, cur
);/* INT_: structure copy */
1347 xfs_alloc_rec_t
*rp
; /* btree record pointer */
1349 rp
= XFS_ALLOC_REC_ADDR(left
, 1, cur
);
1350 kp
[0].ar_startblock
= rp
->ar_startblock
; /* INT_: direct copy */
1351 kp
[0].ar_blockcount
= rp
->ar_blockcount
; /* INT_: direct copy */
1352 rp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1353 kp
[1].ar_startblock
= rp
->ar_startblock
; /* INT_: direct copy */
1354 kp
[1].ar_blockcount
= rp
->ar_blockcount
; /* INT_: direct copy */
1357 xfs_alloc_log_keys(cur
, nbp
, 1, 2);
1359 * Fill in the pointer data in the new root.
1362 xfs_alloc_ptr_t
*pp
; /* btree address pointer */
1364 pp
= XFS_ALLOC_PTR_ADDR(new, 1, cur
);
1365 INT_SET(pp
[0], ARCH_CONVERT
, lbno
);
1366 INT_SET(pp
[1], ARCH_CONVERT
, rbno
);
1368 xfs_alloc_log_ptrs(cur
, nbp
, 1, 2);
1370 * Fix up the cursor.
1372 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
1373 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
1380 * Move 1 record right from cur/level if possible.
1381 * Update cur to reflect the new path.
1383 STATIC
int /* error */
1385 xfs_btree_cur_t
*cur
, /* btree cursor */
1386 int level
, /* level to shift record on */
1387 int *stat
) /* success/failure */
1389 int error
; /* error return value */
1390 int i
; /* loop index */
1391 xfs_alloc_key_t key
; /* key value for leaf level upward */
1392 xfs_buf_t
*lbp
; /* buffer for left (current) block */
1393 xfs_alloc_block_t
*left
; /* left (current) btree block */
1394 xfs_buf_t
*rbp
; /* buffer for right neighbor block */
1395 xfs_alloc_block_t
*right
; /* right neighbor btree block */
1396 xfs_alloc_key_t
*rkp
; /* key pointer for right block */
1397 xfs_btree_cur_t
*tcur
; /* temporary cursor */
1400 * Set up variables for this block as "left".
1402 lbp
= cur
->bc_bufs
[level
];
1403 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1405 if (error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
))
1409 * If we've got no right sibling then we can't shift an entry right.
1411 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1416 * If the cursor entry is the one that would be moved, don't
1417 * do it... it's too complicated.
1419 if (cur
->bc_ptrs
[level
] >= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
)) {
1424 * Set up the right neighbor as "right".
1426 if (error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1427 cur
->bc_private
.a
.agno
, INT_GET(left
->bb_rightsib
, ARCH_CONVERT
), 0, &rbp
,
1428 XFS_ALLOC_BTREE_REF
))
1430 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1431 if (error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
))
1434 * If it's full, it can't take another entry.
1436 if (INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1441 * Make a hole at the start of the right neighbor block, then
1442 * copy the last left block entry to the hole.
1445 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1446 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1447 xfs_alloc_ptr_t
*rpp
; /* address pointer for right block */
1449 lkp
= XFS_ALLOC_KEY_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1450 lpp
= XFS_ALLOC_PTR_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1451 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1452 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1454 for (i
= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) - 1; i
>= 0; i
--) {
1455 if (error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
], ARCH_CONVERT
), level
))
1459 ovbcopy(rkp
, rkp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
1460 ovbcopy(rpp
, rpp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
1462 if (error
= xfs_btree_check_sptr(cur
, INT_GET(*lpp
, ARCH_CONVERT
), level
))
1465 *rkp
= *lkp
; /* INT_: copy */
1466 *rpp
= *lpp
; /* INT_: copy */
1467 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1468 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1469 xfs_btree_check_key(cur
->bc_btnum
, rkp
, rkp
+ 1);
1471 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1472 xfs_alloc_rec_t
*rrp
; /* record pointer for right block */
1474 lrp
= XFS_ALLOC_REC_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1475 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1476 ovbcopy(rrp
, rrp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1478 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1479 key
.ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1480 key
.ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1482 xfs_btree_check_rec(cur
->bc_btnum
, rrp
, rrp
+ 1);
1485 * Decrement and log left's numrecs, bump and log right's numrecs.
1487 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -1);
1488 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1489 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
1490 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1492 * Using a temporary cursor, update the parent key values of the
1493 * block on the right.
1495 if (error
= xfs_btree_dup_cursor(cur
, &tcur
))
1497 i
= xfs_btree_lastrec(tcur
, level
);
1498 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1499 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)) ||
1500 (error
= xfs_alloc_updkey(tcur
, rkp
, level
+ 1)))
1502 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1506 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
1511 * Split cur/level block in half.
1512 * Return new block number and its first record (to be inserted into parent).
1514 STATIC
int /* error */
1516 xfs_btree_cur_t
*cur
, /* btree cursor */
1517 int level
, /* level to split */
1518 xfs_agblock_t
*bnop
, /* output: block number allocated */
1519 xfs_alloc_key_t
*keyp
, /* output: first key of new block */
1520 xfs_btree_cur_t
**curp
, /* output: new cursor */
1521 int *stat
) /* success/failure */
1523 int error
; /* error return value */
1524 int i
; /* loop index/record number */
1525 xfs_agblock_t lbno
; /* left (current) block number */
1526 xfs_buf_t
*lbp
; /* buffer for left block */
1527 xfs_alloc_block_t
*left
; /* left (current) btree block */
1528 xfs_agblock_t rbno
; /* right (new) block number */
1529 xfs_buf_t
*rbp
; /* buffer for right block */
1530 xfs_alloc_block_t
*right
; /* right (new) btree block */
1533 * Allocate the new block from the freelist.
1534 * If we can't do it, we're toast. Give up.
1536 if (error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1539 if (rbno
== NULLAGBLOCK
) {
1543 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1544 rbp
= xfs_btree_get_bufs(cur
->bc_mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
,
1547 * Set up the new block as "right".
1549 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1551 * "Left" is the current (according to the cursor) block.
1553 lbp
= cur
->bc_bufs
[level
];
1554 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1556 if (error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
))
1560 * Fill in the btree header for the new block.
1562 INT_SET(right
->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
1563 right
->bb_level
= left
->bb_level
; /* INT_: direct copy */
1564 INT_SET(right
->bb_numrecs
, ARCH_CONVERT
, (__uint16_t
)(INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) / 2));
1566 * Make sure that if there's an odd number of entries now, that
1567 * each new block will have the same number of entries.
1569 if ((INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) & 1) &&
1570 cur
->bc_ptrs
[level
] <= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1)
1571 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
1572 i
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) - INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1;
1574 * For non-leaf blocks, copy keys and addresses over to the new block.
1577 xfs_alloc_key_t
*lkp
; /* left btree key pointer */
1578 xfs_alloc_ptr_t
*lpp
; /* left btree address pointer */
1579 xfs_alloc_key_t
*rkp
; /* right btree key pointer */
1580 xfs_alloc_ptr_t
*rpp
; /* right btree address pointer */
1582 lkp
= XFS_ALLOC_KEY_ADDR(left
, i
, cur
);
1583 lpp
= XFS_ALLOC_PTR_ADDR(left
, i
, cur
);
1584 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1585 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1587 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
1588 if (error
= xfs_btree_check_sptr(cur
, INT_GET(lpp
[i
], ARCH_CONVERT
), level
))
1592 bcopy(lkp
, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
)); /* INT_: copy */
1593 bcopy(lpp
, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));/* INT_: copy */
1594 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1595 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1599 * For leaf blocks, copy records over to the new block.
1602 xfs_alloc_rec_t
*lrp
; /* left btree record pointer */
1603 xfs_alloc_rec_t
*rrp
; /* right btree record pointer */
1605 lrp
= XFS_ALLOC_REC_ADDR(left
, i
, cur
);
1606 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1607 bcopy(lrp
, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1608 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1609 keyp
->ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1610 keyp
->ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1613 * Find the left block number by looking in the buffer.
1614 * Adjust numrecs, sibling pointers.
1616 lbno
= XFS_DADDR_TO_AGBNO(cur
->bc_mp
, XFS_BUF_ADDR(lbp
));
1617 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -(INT_GET(right
->bb_numrecs
, ARCH_CONVERT
)));
1618 right
->bb_rightsib
= left
->bb_rightsib
; /* INT_: direct copy */
1619 INT_SET(left
->bb_rightsib
, ARCH_CONVERT
, rbno
);
1620 INT_SET(right
->bb_leftsib
, ARCH_CONVERT
, lbno
);
1621 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_ALL_BITS
);
1622 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
1624 * If there's a block to the new block's right, make that block
1625 * point back to right instead of to left.
1627 if (INT_GET(right
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1628 xfs_alloc_block_t
*rrblock
; /* rr btree block */
1629 xfs_buf_t
*rrbp
; /* buffer for rrblock */
1631 if (error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1632 cur
->bc_private
.a
.agno
, INT_GET(right
->bb_rightsib
, ARCH_CONVERT
), 0,
1633 &rrbp
, XFS_ALLOC_BTREE_REF
))
1635 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
1636 if (error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
))
1638 INT_SET(rrblock
->bb_leftsib
, ARCH_CONVERT
, rbno
);
1639 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
1642 * If the cursor is really in the right block, move it there.
1643 * If it's just pointing past the last entry in left, then we'll
1644 * insert there, so don't change anything in that case.
1646 if (cur
->bc_ptrs
[level
] > INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1) {
1647 xfs_btree_setbuf(cur
, level
, rbp
);
1648 cur
->bc_ptrs
[level
] -= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
1651 * If there are more levels, we'll need another cursor which refers to
1652 * the right block, no matter where this cursor was.
1654 if (level
+ 1 < cur
->bc_nlevels
) {
1655 if (error
= xfs_btree_dup_cursor(cur
, curp
))
1657 (*curp
)->bc_ptrs
[level
+ 1]++;
1665 * Update keys at all levels from here to the root along the cursor's path.
1667 STATIC
int /* error */
1669 xfs_btree_cur_t
*cur
, /* btree cursor */
1670 xfs_alloc_key_t
*keyp
, /* new key value to update to */
1671 int level
) /* starting level for update */
1673 int ptr
; /* index of key in block */
1676 * Go up the tree from this level toward the root.
1677 * At each level, update the key value to the value input.
1678 * Stop when we reach a level where the cursor isn't pointing
1679 * at the first entry in the block.
1681 for (ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
1682 xfs_alloc_block_t
*block
; /* btree block */
1683 xfs_buf_t
*bp
; /* buffer for block */
1685 int error
; /* error return value */
1687 xfs_alloc_key_t
*kp
; /* ptr to btree block keys */
1689 bp
= cur
->bc_bufs
[level
];
1690 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1692 if (error
= xfs_btree_check_sblock(cur
, block
, level
, bp
))
1695 ptr
= cur
->bc_ptrs
[level
];
1696 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
1698 xfs_alloc_log_keys(cur
, bp
, ptr
, ptr
);
1704 * Externally visible routines.
1708 * Decrement cursor by one record at the level.
1709 * For nonzero levels the leaf-ward information is untouched.
1712 xfs_alloc_decrement(
1713 xfs_btree_cur_t
*cur
, /* btree cursor */
1714 int level
, /* level in btree, 0 is leaf */
1715 int *stat
) /* success/failure */
1717 xfs_alloc_block_t
*block
; /* btree block */
1718 int error
; /* error return value */
1719 int lev
; /* btree level */
1721 ASSERT(level
< cur
->bc_nlevels
);
1723 * Read-ahead to the left at this level.
1725 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1727 * Decrement the ptr at this level. If we're still in the block
1730 if (--cur
->bc_ptrs
[level
] > 0) {
1735 * Get a pointer to the btree block.
1737 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[level
]);
1739 if (error
= xfs_btree_check_sblock(cur
, block
, level
,
1740 cur
->bc_bufs
[level
]))
1744 * If we just went off the left edge of the tree, return failure.
1746 if (INT_GET(block
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1751 * March up the tree decrementing pointers.
1752 * Stop when we don't go off the left edge of a block.
1754 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1755 if (--cur
->bc_ptrs
[lev
] > 0)
1758 * Read-ahead the left block, we're going to read it
1761 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1764 * If we went off the root then we are seriously confused.
1766 ASSERT(lev
< cur
->bc_nlevels
);
1768 * Now walk back down the tree, fixing up the cursor's buffer
1769 * pointers and key numbers.
1771 for (block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[lev
]); lev
> level
; ) {
1772 xfs_agblock_t agbno
; /* block number of btree block */
1773 xfs_buf_t
*bp
; /* buffer pointer for block */
1775 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1776 if (error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1777 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1778 XFS_ALLOC_BTREE_REF
))
1781 xfs_btree_setbuf(cur
, lev
, bp
);
1782 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1783 if (error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
))
1785 cur
->bc_ptrs
[lev
] = INT_GET(block
->bb_numrecs
, ARCH_CONVERT
);
1792 * Delete the record pointed to by cur.
1793 * The cursor refers to the place where the record was (could be inserted)
1794 * when the operation returns.
1798 xfs_btree_cur_t
*cur
, /* btree cursor */
1799 int *stat
) /* success/failure */
1801 int error
; /* error return value */
1802 int i
; /* result code */
1803 int level
; /* btree level */
1806 * Go up the tree, starting at leaf level.
1807 * If 2 is returned then a join was done; go to the next level.
1808 * Otherwise we are done.
1810 for (level
= 0, i
= 2; i
== 2; level
++) {
1811 if (error
= xfs_alloc_delrec(cur
, level
, &i
))
1815 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
1816 if (cur
->bc_ptrs
[level
] == 0) {
1817 if (error
= xfs_alloc_decrement(cur
, level
, &i
))
1828 * Get the data from the pointed-to record.
1832 xfs_btree_cur_t
*cur
, /* btree cursor */
1833 xfs_agblock_t
*bno
, /* output: starting block of extent */
1834 xfs_extlen_t
*len
, /* output: length of extent */
1835 int *stat
) /* output: success/failure */
1837 xfs_alloc_block_t
*block
; /* btree block */
1839 int error
; /* error return value */
1841 int ptr
; /* record number */
1843 ptr
= cur
->bc_ptrs
[0];
1844 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
1846 if (error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0]))
1850 * Off the right end or left end, return failure.
1852 if (ptr
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) || ptr
<= 0) {
1857 * Point to the record and extract its data.
1860 xfs_alloc_rec_t
*rec
; /* record data */
1862 rec
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
1863 *bno
= INT_GET(rec
->ar_startblock
, ARCH_CONVERT
);
1864 *len
= INT_GET(rec
->ar_blockcount
, ARCH_CONVERT
);
1871 * Increment cursor by one record at the level.
1872 * For nonzero levels the leaf-ward information is untouched.
1875 xfs_alloc_increment(
1876 xfs_btree_cur_t
*cur
, /* btree cursor */
1877 int level
, /* level in btree, 0 is leaf */
1878 int *stat
) /* success/failure */
1880 xfs_alloc_block_t
*block
; /* btree block */
1881 xfs_buf_t
*bp
; /* tree block buffer */
1882 int error
; /* error return value */
1883 int lev
; /* btree level */
1885 ASSERT(level
< cur
->bc_nlevels
);
1887 * Read-ahead to the right at this level.
1889 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1891 * Get a pointer to the btree block.
1893 bp
= cur
->bc_bufs
[level
];
1894 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1896 if (error
= xfs_btree_check_sblock(cur
, block
, level
, bp
))
1900 * Increment the ptr at this level. If we're still in the block
1903 if (++cur
->bc_ptrs
[level
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
1908 * If we just went off the right edge of the tree, return failure.
1910 if (INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1915 * March up the tree incrementing pointers.
1916 * Stop when we don't go off the right edge of a block.
1918 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1919 bp
= cur
->bc_bufs
[lev
];
1920 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1922 if (error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
))
1925 if (++cur
->bc_ptrs
[lev
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
1928 * Read-ahead the right block, we're going to read it
1931 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1934 * If we went off the root then we are seriously confused.
1936 ASSERT(lev
< cur
->bc_nlevels
);
1938 * Now walk back down the tree, fixing up the cursor's buffer
1939 * pointers and key numbers.
1941 for (bp
= cur
->bc_bufs
[lev
], block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1943 xfs_agblock_t agbno
; /* block number of btree block */
1945 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1946 if (error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1947 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1948 XFS_ALLOC_BTREE_REF
))
1951 xfs_btree_setbuf(cur
, lev
, bp
);
1952 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1953 if (error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
))
1955 cur
->bc_ptrs
[lev
] = 1;
1962 * Insert the current record at the point referenced by cur.
1963 * The cursor may be inconsistent on return if splits have been done.
1967 xfs_btree_cur_t
*cur
, /* btree cursor */
1968 int *stat
) /* success/failure */
1970 int error
; /* error return value */
1971 int i
; /* result value, 0 for failure */
1972 int level
; /* current level number in btree */
1973 xfs_agblock_t nbno
; /* new block number (split result) */
1974 xfs_btree_cur_t
*ncur
; /* new cursor (split result) */
1975 xfs_alloc_rec_t nrec
; /* record being inserted this level */
1976 xfs_btree_cur_t
*pcur
; /* previous level's cursor */
1980 INT_SET(nrec
.ar_startblock
, ARCH_CONVERT
, cur
->bc_rec
.a
.ar_startblock
);
1981 INT_SET(nrec
.ar_blockcount
, ARCH_CONVERT
, cur
->bc_rec
.a
.ar_blockcount
);
1982 ncur
= (xfs_btree_cur_t
*)0;
1985 * Loop going up the tree, starting at the leaf level.
1986 * Stop when we don't get a split block, that must mean that
1987 * the insert is finished with this level.
1991 * Insert nrec/nbno into this level of the tree.
1992 * Note if we fail, nbno will be null.
1994 if (error
= xfs_alloc_insrec(pcur
, level
++, &nbno
, &nrec
, &ncur
,
1997 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
2001 * See if the cursor we just used is trash.
2002 * Can't trash the caller's cursor, but otherwise we should
2003 * if ncur is a new cursor or we're about to be done.
2005 if (pcur
!= cur
&& (ncur
|| nbno
== NULLAGBLOCK
)) {
2006 cur
->bc_nlevels
= pcur
->bc_nlevels
;
2007 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
2010 * If we got a new cursor, switch to it.
2014 ncur
= (xfs_btree_cur_t
*)0;
2016 } while (nbno
!= NULLAGBLOCK
);
2022 * Lookup the record equal to [bno, len] in the btree given by cur.
2025 xfs_alloc_lookup_eq(
2026 xfs_btree_cur_t
*cur
, /* btree cursor */
2027 xfs_agblock_t bno
, /* starting block of extent */
2028 xfs_extlen_t len
, /* length of extent */
2029 int *stat
) /* success/failure */
2031 cur
->bc_rec
.a
.ar_startblock
= bno
;
2032 cur
->bc_rec
.a
.ar_blockcount
= len
;
2033 return xfs_alloc_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
2037 * Lookup the first record greater than or equal to [bno, len]
2038 * in the btree given by cur.
2041 xfs_alloc_lookup_ge(
2042 xfs_btree_cur_t
*cur
, /* btree cursor */
2043 xfs_agblock_t bno
, /* starting block of extent */
2044 xfs_extlen_t len
, /* length of extent */
2045 int *stat
) /* success/failure */
2047 cur
->bc_rec
.a
.ar_startblock
= bno
;
2048 cur
->bc_rec
.a
.ar_blockcount
= len
;
2049 return xfs_alloc_lookup(cur
, XFS_LOOKUP_GE
, stat
);
2053 * Lookup the first record less than or equal to [bno, len]
2054 * in the btree given by cur.
2057 xfs_alloc_lookup_le(
2058 xfs_btree_cur_t
*cur
, /* btree cursor */
2059 xfs_agblock_t bno
, /* starting block of extent */
2060 xfs_extlen_t len
, /* length of extent */
2061 int *stat
) /* success/failure */
2063 cur
->bc_rec
.a
.ar_startblock
= bno
;
2064 cur
->bc_rec
.a
.ar_blockcount
= len
;
2065 return xfs_alloc_lookup(cur
, XFS_LOOKUP_LE
, stat
);
2069 * Update the record referred to by cur, to the value given by [bno, len].
2070 * This either works (return 0) or gets an EFSCORRUPTED error.
2074 xfs_btree_cur_t
*cur
, /* btree cursor */
2075 xfs_agblock_t bno
, /* starting block of extent */
2076 xfs_extlen_t len
) /* length of extent */
2078 xfs_alloc_block_t
*block
; /* btree block to update */
2079 int error
; /* error return value */
2080 int ptr
; /* current record number (updating) */
2084 * Pick up the a.g. freelist struct and the current block.
2086 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
2088 if (error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0]))
2092 * Get the address of the rec to be updated.
2094 ptr
= cur
->bc_ptrs
[0];
2096 xfs_alloc_rec_t
*rp
; /* pointer to updated record */
2098 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
2100 * Fill in the new contents and log them.
2102 INT_SET(rp
->ar_startblock
, ARCH_CONVERT
, bno
);
2103 INT_SET(rp
->ar_blockcount
, ARCH_CONVERT
, len
);
2104 xfs_alloc_log_recs(cur
, cur
->bc_bufs
[0], ptr
, ptr
);
2107 * If it's the by-size btree and it's the last leaf block and
2108 * it's the last record... then update the size of the longest
2109 * extent in the a.g., which we cache in the a.g. freelist header.
2111 if (cur
->bc_btnum
== XFS_BTNUM_CNT
&&
2112 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
&&
2113 ptr
== INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
2114 xfs_agf_t
*agf
; /* a.g. freespace header */
2115 xfs_agnumber_t seqno
;
2117 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
2118 seqno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
2119 cur
->bc_mp
->m_perag
[seqno
].pagf_longest
= len
;
2120 INT_SET(agf
->agf_longest
, ARCH_CONVERT
, len
);
2121 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
2125 * Updating first record in leaf. Pass new key value up to our parent.
2128 xfs_alloc_key_t key
; /* key containing [bno, len] */
2130 INT_SET(key
.ar_startblock
, ARCH_CONVERT
, bno
);
2131 INT_SET(key
.ar_blockcount
, ARCH_CONVERT
, len
);
2132 if (error
= xfs_alloc_updkey(cur
, &key
, 1))