]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_alloc_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 * 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
=NULL
; /* left block key pointer */
62 xfs_alloc_ptr_t
*lpp
=NULL
; /* left block address pointer */
63 int lrecs
=0; /* 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
=0; /* 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 memmove(&lkp
[ptr
- 1], &lkp
[ptr
],
117 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
) * sizeof(*lkp
)); /* INT_: mem copy */
118 memmove(&lpp
[ptr
- 1], &lpp
[ptr
],
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 memmove(&lrp
[ptr
- 1], &lrp
[ptr
],
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
)))
208 * Since blocks move to the free list without the
209 * coordination used in xfs_bmap_finish, we can't allow
210 * block to be available for reallocation and
211 * non-transaction writing (user data) until we know
212 * that the transaction that moved it to the free list
213 * is permanently on disk. We track the blocks by
214 * declaring these blocks as "busy"; the busy list is
215 * maintained on a per-ag basis and each transaction
216 * records which entries should be removed when the
217 * iclog commits to disk. If a busy block is
218 * allocated, the iclog is pushed up to the LSN
219 * that freed the block.
221 xfs_alloc_mark_busy(cur
->bc_tp
,
222 INT_GET(agf
->agf_seqno
, ARCH_CONVERT
), bno
, 1);
224 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
225 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
226 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
228 * Update the cursor so there's one fewer level.
230 xfs_btree_setbuf(cur
, level
, 0);
232 } else if (level
> 0 &&
233 (error
= xfs_alloc_decrement(cur
, level
, &i
)))
239 * If we deleted the leftmost entry in the block, update the
240 * key values above us in the tree.
242 if (ptr
== 1 && (error
= xfs_alloc_updkey(cur
, lkp
, level
+ 1)))
245 * If the number of records remaining in the block is at least
246 * the minimum, we're done.
248 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >= XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
249 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
255 * Otherwise, we have to move some records around to keep the
256 * tree balanced. Look at the left and right sibling blocks to
257 * see if we can re-balance by moving only one record.
259 rbno
= INT_GET(block
->bb_rightsib
, ARCH_CONVERT
);
260 lbno
= INT_GET(block
->bb_leftsib
, ARCH_CONVERT
);
262 ASSERT(rbno
!= NULLAGBLOCK
|| lbno
!= NULLAGBLOCK
);
264 * Duplicate the cursor so our btree manipulations here won't
265 * disrupt the next level up.
267 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
270 * If there's a right sibling, see if it's ok to shift an entry
273 if (rbno
!= NULLAGBLOCK
) {
275 * Move the temp cursor to the last entry in the next block.
276 * Actually any entry but the first would suffice.
278 i
= xfs_btree_lastrec(tcur
, level
);
279 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
280 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)))
282 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
283 i
= xfs_btree_lastrec(tcur
, level
);
284 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
286 * Grab a pointer to the block.
288 rbp
= tcur
->bc_bufs
[level
];
289 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
291 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
295 * Grab the current block number, for future use.
297 bno
= INT_GET(right
->bb_leftsib
, ARCH_CONVERT
);
299 * If right block is full enough so that removing one entry
300 * won't make it too empty, and left-shifting an entry out
301 * of right to us works, we're done.
303 if (INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) - 1 >=
304 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
305 if ((error
= xfs_alloc_lshift(tcur
, level
, &i
)))
308 ASSERT(INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >=
309 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
310 xfs_btree_del_cursor(tcur
,
313 (error
= xfs_alloc_decrement(cur
, level
,
321 * Otherwise, grab the number of records in right for
322 * future reference, and fix up the temp cursor to point
323 * to our block again (last record).
325 rrecs
= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
);
326 if (lbno
!= NULLAGBLOCK
) {
327 i
= xfs_btree_firstrec(tcur
, level
);
328 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
329 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
331 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
335 * If there's a left sibling, see if it's ok to shift an entry
338 if (lbno
!= NULLAGBLOCK
) {
340 * Move the temp cursor to the first entry in the
343 i
= xfs_btree_firstrec(tcur
, level
);
344 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
345 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
347 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
348 xfs_btree_firstrec(tcur
, level
);
350 * Grab a pointer to the block.
352 lbp
= tcur
->bc_bufs
[level
];
353 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
355 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
359 * Grab the current block number, for future use.
361 bno
= INT_GET(left
->bb_rightsib
, ARCH_CONVERT
);
363 * If left block is full enough so that removing one entry
364 * won't make it too empty, and right-shifting an entry out
365 * of left to us works, we're done.
367 if (INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) - 1 >=
368 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
369 if ((error
= xfs_alloc_rshift(tcur
, level
, &i
)))
372 ASSERT(INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) >=
373 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
374 xfs_btree_del_cursor(tcur
,
383 * Otherwise, grab the number of records in right for
386 lrecs
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
389 * Delete the temp cursor, we're done with it.
391 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
393 * If here, we need to do a join to keep the tree balanced.
395 ASSERT(bno
!= NULLAGBLOCK
);
397 * See if we can join with the left neighbor block.
399 if (lbno
!= NULLAGBLOCK
&&
400 lrecs
+ INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) <= XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
402 * Set "right" to be the starting block,
403 * "left" to be the left neighbor.
408 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
409 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
410 XFS_ALLOC_BTREE_REF
)))
412 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
413 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
417 * If that won't work, see if we can join with the right neighbor block.
419 else if (rbno
!= NULLAGBLOCK
&&
420 rrecs
+ INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) <=
421 XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
423 * Set "left" to be the starting block,
424 * "right" to be the right neighbor.
429 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
430 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
431 XFS_ALLOC_BTREE_REF
)))
433 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
434 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
438 * Otherwise, we can't fix the imbalance.
439 * Just return. This is probably a logic error, but it's not fatal.
442 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
448 * We're now going to join "left" and "right" by moving all the stuff
449 * in "right" to "left" and deleting "right".
453 * It's a non-leaf. Move keys and pointers.
455 lkp
= XFS_ALLOC_KEY_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
456 lpp
= XFS_ALLOC_PTR_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
457 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
458 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
460 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
461 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
], ARCH_CONVERT
), level
)))
465 memcpy(lkp
, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lkp
)); /* INT_: structure copy */
466 memcpy(lpp
, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lpp
)); /* INT_: structure copy */
467 xfs_alloc_log_keys(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
468 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
469 xfs_alloc_log_ptrs(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
470 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
473 * It's a leaf. Move records.
475 lrp
= XFS_ALLOC_REC_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1, cur
);
476 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
477 memcpy(lrp
, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*lrp
));
478 xfs_alloc_log_recs(cur
, lbp
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1,
479 INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
482 * If we joined with the left neighbor, set the buffer in the
483 * cursor to the left block, and fix up the index.
486 xfs_btree_setbuf(cur
, level
, lbp
);
487 cur
->bc_ptrs
[level
] += INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
490 * If we joined with the right neighbor and there's a level above
491 * us, increment the cursor at that level.
493 else if (level
+ 1 < cur
->bc_nlevels
&&
494 (error
= xfs_alloc_increment(cur
, level
+ 1, &i
)))
497 * Fix up the number of records in the surviving block.
499 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
501 * Fix up the right block pointer in the surviving block, and log it.
503 left
->bb_rightsib
= right
->bb_rightsib
; /* INT_: direct copy */
504 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
506 * If there is a right sibling now, make it point to the
509 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
510 xfs_alloc_block_t
*rrblock
;
513 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
514 cur
->bc_private
.a
.agno
, INT_GET(left
->bb_rightsib
, ARCH_CONVERT
), 0,
515 &rrbp
, XFS_ALLOC_BTREE_REF
)))
517 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
518 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
520 INT_SET(rrblock
->bb_leftsib
, ARCH_CONVERT
, lbno
);
521 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
524 * Free the deleting block by putting it on the freelist.
526 if ((error
= xfs_alloc_put_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
530 * Since blocks move to the free list without the coordination
531 * used in xfs_bmap_finish, we can't allow block to be available
532 * for reallocation and non-transaction writing (user data)
533 * until we know that the transaction that moved it to the free
534 * list is permanently on disk. We track the blocks by declaring
535 * these blocks as "busy"; the busy list is maintained on a
536 * per-ag basis and each transaction records which entries
537 * should be removed when the iclog commits to disk. If a
538 * busy block is allocated, the iclog is pushed up to the
539 * LSN that freed the block.
541 xfs_alloc_mark_busy(cur
->bc_tp
,
542 INT_GET(agf
->agf_seqno
, ARCH_CONVERT
), bno
, 1);
544 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
546 * Adjust the current level's cursor so that we're left referring
547 * to the right node, after we're done.
548 * If this leaves the ptr value 0 our caller will fix it up.
551 cur
->bc_ptrs
[level
]--;
553 * Return value means the next level up has something to do.
559 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
564 * Insert one record/level. Return information to the caller
565 * allowing the next level up to proceed if necessary.
567 STATIC
int /* error */
569 xfs_btree_cur_t
*cur
, /* btree cursor */
570 int level
, /* level to insert record at */
571 xfs_agblock_t
*bnop
, /* i/o: block number inserted */
572 xfs_alloc_rec_t
*recp
, /* i/o: record data inserted */
573 xfs_btree_cur_t
**curp
, /* output: new cursor replacing cur */
574 int *stat
) /* output: success/failure */
576 xfs_agf_t
*agf
; /* allocation group freelist header */
577 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
578 xfs_buf_t
*bp
; /* buffer for block */
579 int error
; /* error return value */
580 int i
; /* loop index */
581 xfs_alloc_key_t key
; /* key value being inserted */
582 xfs_alloc_key_t
*kp
; /* pointer to btree keys */
583 xfs_agblock_t nbno
; /* block number of allocated block */
584 xfs_btree_cur_t
*ncur
; /* new cursor to be used at next lvl */
585 xfs_alloc_key_t nkey
; /* new key value, from split */
586 xfs_alloc_rec_t nrec
; /* new record value, for caller */
587 int optr
; /* old ptr value */
588 xfs_alloc_ptr_t
*pp
; /* pointer to btree addresses */
589 int ptr
; /* index in btree block for this rec */
590 xfs_alloc_rec_t
*rp
; /* pointer to btree records */
592 ASSERT(INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
) > 0);
594 * If we made it to the root level, allocate a new root block
597 if (level
>= cur
->bc_nlevels
) {
598 XFS_STATS_INC(xs_abt_insrec
);
599 if ((error
= xfs_alloc_newroot(cur
, &i
)))
606 * Make a key out of the record data to be inserted, and save it.
608 key
.ar_startblock
= recp
->ar_startblock
; /* INT_: direct copy */
609 key
.ar_blockcount
= recp
->ar_blockcount
; /* INT_: direct copy */
610 optr
= ptr
= cur
->bc_ptrs
[level
];
612 * If we're off the left edge, return failure.
618 XFS_STATS_INC(xs_abt_insrec
);
620 * Get pointers to the btree buffer and block.
622 bp
= cur
->bc_bufs
[level
];
623 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
625 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
628 * Check that the new entry is being inserted in the right place.
630 if (ptr
<= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
632 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
633 xfs_btree_check_rec(cur
->bc_btnum
, recp
, rp
);
635 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
636 xfs_btree_check_key(cur
->bc_btnum
, &key
, kp
);
641 ncur
= (xfs_btree_cur_t
*)0;
643 * If the block is full, we can't insert the new entry until we
644 * make the block un-full.
646 if (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
648 * First, try shifting an entry to the right neighbor.
650 if ((error
= xfs_alloc_rshift(cur
, level
, &i
)))
656 * Next, try shifting an entry to the left neighbor.
659 if ((error
= xfs_alloc_lshift(cur
, level
, &i
)))
662 optr
= ptr
= cur
->bc_ptrs
[level
];
665 * Next, try splitting the current block in
666 * half. If this works we have to re-set our
667 * variables because we could be in a
668 * different block now.
670 if ((error
= xfs_alloc_split(cur
, level
, &nbno
,
674 bp
= cur
->bc_bufs
[level
];
675 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
678 xfs_btree_check_sblock(cur
,
682 ptr
= cur
->bc_ptrs
[level
];
683 nrec
.ar_startblock
= nkey
.ar_startblock
; /* INT_: direct copy */
684 nrec
.ar_blockcount
= nkey
.ar_blockcount
; /* INT_: direct copy */
687 * Otherwise the insert fails.
697 * At this point we know there's room for our new entry in the block
702 * It's a non-leaf entry. Make a hole for the new data
703 * in the key and ptr regions of the block.
705 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
706 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
708 for (i
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
); i
>= ptr
; i
--) {
709 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(pp
[i
- 1], ARCH_CONVERT
), level
)))
713 memmove(&kp
[ptr
], &kp
[ptr
- 1],
714 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*kp
)); /* INT_: copy */
715 memmove(&pp
[ptr
], &pp
[ptr
- 1],
716 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*pp
)); /* INT_: copy */
718 if ((error
= xfs_btree_check_sptr(cur
, *bnop
, level
)))
722 * Now stuff the new data in, bump numrecs and log the new data.
725 INT_SET(pp
[ptr
- 1], ARCH_CONVERT
, *bnop
);
726 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
727 xfs_alloc_log_keys(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
728 xfs_alloc_log_ptrs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
730 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
731 xfs_btree_check_key(cur
->bc_btnum
, kp
+ ptr
- 1,
736 * It's a leaf entry. Make a hole for the new record.
738 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
739 memmove(&rp
[ptr
], &rp
[ptr
- 1],
740 (INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) - ptr
+ 1) * sizeof(*rp
));
742 * Now stuff the new record in, bump numrecs
743 * and log the new data.
745 rp
[ptr
- 1] = *recp
; /* INT_: struct copy */
746 INT_MOD(block
->bb_numrecs
, ARCH_CONVERT
, +1);
747 xfs_alloc_log_recs(cur
, bp
, ptr
, INT_GET(block
->bb_numrecs
, ARCH_CONVERT
));
749 if (ptr
< INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
750 xfs_btree_check_rec(cur
->bc_btnum
, rp
+ ptr
- 1,
755 * Log the new number of records in the btree header.
757 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
759 * If we inserted at the start of a block, update the parents' keys.
761 if (optr
== 1 && (error
= xfs_alloc_updkey(cur
, &key
, level
+ 1)))
764 * Look to see if the longest extent in the allocation group
765 * needs to be updated.
768 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
770 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
771 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
&&
772 INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
) > INT_GET(agf
->agf_longest
, ARCH_CONVERT
)) {
774 * If this is a leaf in the by-size btree and there
775 * is no right sibling block and this block is bigger
776 * than the previous longest block, update it.
778 INT_COPY(agf
->agf_longest
, recp
->ar_blockcount
, ARCH_CONVERT
);
779 cur
->bc_mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)].pagf_longest
780 = INT_GET(recp
->ar_blockcount
, ARCH_CONVERT
);
781 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
785 * Return the new block number, if any.
786 * If there is one, give back a record value and a cursor too.
789 if (nbno
!= NULLAGBLOCK
) {
790 *recp
= nrec
; /* INT_: struct copy */
791 *curp
= ncur
; /* INT_: struct copy */
798 * Log header fields from a btree block.
802 xfs_trans_t
*tp
, /* transaction pointer */
803 xfs_buf_t
*bp
, /* buffer containing btree block */
804 int fields
) /* mask of fields: XFS_BB_... */
806 int first
; /* first byte offset logged */
807 int last
; /* last byte offset logged */
808 static const short offsets
[] = { /* table of offsets */
809 offsetof(xfs_alloc_block_t
, bb_magic
),
810 offsetof(xfs_alloc_block_t
, bb_level
),
811 offsetof(xfs_alloc_block_t
, bb_numrecs
),
812 offsetof(xfs_alloc_block_t
, bb_leftsib
),
813 offsetof(xfs_alloc_block_t
, bb_rightsib
),
814 sizeof(xfs_alloc_block_t
)
817 xfs_btree_offsets(fields
, offsets
, XFS_BB_NUM_BITS
, &first
, &last
);
818 xfs_trans_log_buf(tp
, bp
, first
, last
);
822 * Log keys from a btree block (nonleaf).
826 xfs_btree_cur_t
*cur
, /* btree cursor */
827 xfs_buf_t
*bp
, /* buffer containing btree block */
828 int kfirst
, /* index of first key to log */
829 int klast
) /* index of last key to log */
831 xfs_alloc_block_t
*block
; /* btree block to log from */
832 int first
; /* first byte offset logged */
833 xfs_alloc_key_t
*kp
; /* key pointer in btree block */
834 int last
; /* last byte offset logged */
836 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
837 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
838 first
= (int)((xfs_caddr_t
)&kp
[kfirst
- 1] - (xfs_caddr_t
)block
);
839 last
= (int)(((xfs_caddr_t
)&kp
[klast
] - 1) - (xfs_caddr_t
)block
);
840 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
844 * Log block pointer fields from a btree block (nonleaf).
848 xfs_btree_cur_t
*cur
, /* btree cursor */
849 xfs_buf_t
*bp
, /* buffer containing btree block */
850 int pfirst
, /* index of first pointer to log */
851 int plast
) /* index of last pointer to log */
853 xfs_alloc_block_t
*block
; /* btree block to log from */
854 int first
; /* first byte offset logged */
855 int last
; /* last byte offset logged */
856 xfs_alloc_ptr_t
*pp
; /* block-pointer pointer in btree blk */
858 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
859 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
860 first
= (int)((xfs_caddr_t
)&pp
[pfirst
- 1] - (xfs_caddr_t
)block
);
861 last
= (int)(((xfs_caddr_t
)&pp
[plast
] - 1) - (xfs_caddr_t
)block
);
862 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
866 * Log records from a btree block (leaf).
870 xfs_btree_cur_t
*cur
, /* btree cursor */
871 xfs_buf_t
*bp
, /* buffer containing btree block */
872 int rfirst
, /* index of first record to log */
873 int rlast
) /* index of last record to log */
875 xfs_alloc_block_t
*block
; /* btree block to log from */
876 int first
; /* first byte offset logged */
877 int last
; /* last byte offset logged */
878 xfs_alloc_rec_t
*rp
; /* record pointer for btree block */
881 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
882 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
888 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
889 for (p
= &rp
[rfirst
- 1]; p
<= &rp
[rlast
- 1]; p
++)
890 ASSERT(INT_GET(p
->ar_startblock
, ARCH_CONVERT
) + INT_GET(p
->ar_blockcount
, ARCH_CONVERT
) <=
891 INT_GET(agf
->agf_length
, ARCH_CONVERT
));
894 first
= (int)((xfs_caddr_t
)&rp
[rfirst
- 1] - (xfs_caddr_t
)block
);
895 last
= (int)(((xfs_caddr_t
)&rp
[rlast
] - 1) - (xfs_caddr_t
)block
);
896 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
900 * Lookup the record. The cursor is made to point to it, based on dir.
901 * Return 0 if can't find any such record, 1 for success.
903 STATIC
int /* error */
905 xfs_btree_cur_t
*cur
, /* btree cursor */
906 xfs_lookup_t dir
, /* <=, ==, or >= */
907 int *stat
) /* success/failure */
909 xfs_agblock_t agbno
; /* a.g. relative btree block number */
910 xfs_agnumber_t agno
; /* allocation group number */
911 xfs_alloc_block_t
*block
=NULL
; /* current btree block */
912 int diff
; /* difference for the current key */
913 int error
; /* error return value */
914 int keyno
=0; /* current key number */
915 int level
; /* level in the btree */
916 xfs_mount_t
*mp
; /* file system mount point */
918 XFS_STATS_INC(xs_abt_lookup
);
920 * Get the allocation group header, and the root block number.
925 xfs_agf_t
*agf
; /* a.g. freespace header */
927 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
928 agno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
929 agbno
= INT_GET(agf
->agf_roots
[cur
->bc_btnum
], ARCH_CONVERT
);
932 * Iterate over each level in the btree, starting at the root.
933 * For each level above the leaves, find the key we need, based
934 * on the lookup record, then follow the corresponding block
935 * pointer down to the next level.
937 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
938 xfs_buf_t
*bp
; /* buffer pointer for btree block */
939 xfs_daddr_t d
; /* disk address of btree block */
942 * Get the disk address we're looking for.
944 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
946 * If the old buffer at this level is for a different block,
947 * throw it away, otherwise just use it.
949 bp
= cur
->bc_bufs
[level
];
950 if (bp
&& XFS_BUF_ADDR(bp
) != d
)
954 * Need to get a new buffer. Read it, then
955 * set it in the cursor, releasing the old one.
957 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
, agno
,
958 agbno
, 0, &bp
, XFS_ALLOC_BTREE_REF
)))
960 xfs_btree_setbuf(cur
, level
, bp
);
962 * Point to the btree block, now that we have the buffer
964 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
965 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
969 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
971 * If we already had a key match at a higher level, we know
972 * we need to use the first entry in this block.
977 * Otherwise we need to search this block. Do a binary search.
980 int high
; /* high entry number */
981 xfs_alloc_key_t
*kkbase
=NULL
;/* base of keys in block */
982 xfs_alloc_rec_t
*krbase
=NULL
;/* base of records in block */
983 int low
; /* low entry number */
986 * Get a pointer to keys or records.
989 kkbase
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
991 krbase
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
993 * Set low and high entry numbers, 1-based.
996 if (!(high
= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))) {
998 * If the block is empty, the tree must
1001 ASSERT(level
== 0 && cur
->bc_nlevels
== 1);
1002 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
1007 * Binary search the block.
1009 while (low
<= high
) {
1010 xfs_extlen_t blockcount
; /* key value */
1011 xfs_agblock_t startblock
; /* key value */
1013 XFS_STATS_INC(xs_abt_compare
);
1015 * keyno is average of low and high.
1017 keyno
= (low
+ high
) >> 1;
1019 * Get startblock & blockcount.
1022 xfs_alloc_key_t
*kkp
;
1024 kkp
= kkbase
+ keyno
- 1;
1025 startblock
= INT_GET(kkp
->ar_startblock
, ARCH_CONVERT
);
1026 blockcount
= INT_GET(kkp
->ar_blockcount
, ARCH_CONVERT
);
1028 xfs_alloc_rec_t
*krp
;
1030 krp
= krbase
+ keyno
- 1;
1031 startblock
= INT_GET(krp
->ar_startblock
, ARCH_CONVERT
);
1032 blockcount
= INT_GET(krp
->ar_blockcount
, ARCH_CONVERT
);
1035 * Compute difference to get next direction.
1037 if (cur
->bc_btnum
== XFS_BTNUM_BNO
)
1038 diff
= (int)startblock
-
1039 (int)cur
->bc_rec
.a
.ar_startblock
;
1040 else if (!(diff
= (int)blockcount
-
1041 (int)cur
->bc_rec
.a
.ar_blockcount
))
1042 diff
= (int)startblock
-
1043 (int)cur
->bc_rec
.a
.ar_startblock
;
1045 * Less than, move right.
1050 * Greater than, move left.
1055 * Equal, we're done.
1062 * If there are more levels, set up for the next level
1063 * by getting the block number and filling in the cursor.
1067 * If we moved left, need the previous key number,
1068 * unless there isn't one.
1070 if (diff
> 0 && --keyno
< 1)
1072 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, keyno
, cur
), ARCH_CONVERT
);
1074 if ((error
= xfs_btree_check_sptr(cur
, agbno
, level
)))
1077 cur
->bc_ptrs
[level
] = keyno
;
1081 * Done with the search.
1082 * See if we need to adjust the results.
1084 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1087 * If ge search and we went off the end of the block, but it's
1088 * not the last block, we're in the wrong block.
1090 if (dir
== XFS_LOOKUP_GE
&&
1091 keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) &&
1092 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1095 cur
->bc_ptrs
[0] = keyno
;
1096 if ((error
= xfs_alloc_increment(cur
, 0, &i
)))
1098 XFS_WANT_CORRUPTED_RETURN(i
== 1);
1103 else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
1105 cur
->bc_ptrs
[0] = keyno
;
1107 * Return if we succeeded or not.
1109 if (keyno
== 0 || keyno
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
1112 *stat
= ((dir
!= XFS_LOOKUP_EQ
) || (diff
== 0));
1117 * Move 1 record left from cur/level if possible.
1118 * Update cur to reflect the new path.
1120 STATIC
int /* error */
1122 xfs_btree_cur_t
*cur
, /* btree cursor */
1123 int level
, /* level to shift record on */
1124 int *stat
) /* success/failure */
1126 int error
; /* error return value */
1128 int i
; /* loop index */
1130 xfs_alloc_key_t key
; /* key value for leaf level upward */
1131 xfs_buf_t
*lbp
; /* buffer for left neighbor block */
1132 xfs_alloc_block_t
*left
; /* left neighbor btree block */
1133 int nrec
; /* new number of left block entries */
1134 xfs_buf_t
*rbp
; /* buffer for right (current) block */
1135 xfs_alloc_block_t
*right
; /* right (current) btree block */
1136 xfs_alloc_key_t
*rkp
=NULL
; /* key pointer for right block */
1137 xfs_alloc_ptr_t
*rpp
=NULL
; /* address pointer for right block */
1138 xfs_alloc_rec_t
*rrp
=NULL
; /* record pointer for right block */
1141 * Set up variables for this block as "right".
1143 rbp
= cur
->bc_bufs
[level
];
1144 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1146 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1150 * If we've got no left sibling then we can't shift an entry left.
1152 if (INT_GET(right
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1157 * If the cursor entry is the one that would be moved, don't
1158 * do it... it's too complicated.
1160 if (cur
->bc_ptrs
[level
] <= 1) {
1165 * Set up the left neighbor as "left".
1167 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1168 cur
->bc_private
.a
.agno
, INT_GET(right
->bb_leftsib
, ARCH_CONVERT
), 0, &lbp
,
1169 XFS_ALLOC_BTREE_REF
)))
1171 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1172 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1175 * If it's full, it can't take another entry.
1177 if (INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1181 nrec
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1;
1183 * If non-leaf, copy a key and a ptr to the left block.
1186 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1187 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1189 lkp
= XFS_ALLOC_KEY_ADDR(left
, nrec
, cur
);
1190 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1192 xfs_alloc_log_keys(cur
, lbp
, nrec
, nrec
);
1193 lpp
= XFS_ALLOC_PTR_ADDR(left
, nrec
, cur
);
1194 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1196 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(*rpp
, ARCH_CONVERT
), level
)))
1199 *lpp
= *rpp
; /* INT_: copy */
1200 xfs_alloc_log_ptrs(cur
, lbp
, nrec
, nrec
);
1201 xfs_btree_check_key(cur
->bc_btnum
, lkp
- 1, lkp
);
1204 * If leaf, copy a record to the left block.
1207 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1209 lrp
= XFS_ALLOC_REC_ADDR(left
, nrec
, cur
);
1210 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1212 xfs_alloc_log_recs(cur
, lbp
, nrec
, nrec
);
1213 xfs_btree_check_rec(cur
->bc_btnum
, lrp
- 1, lrp
);
1216 * Bump and log left's numrecs, decrement and log right's numrecs.
1218 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, +1);
1219 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1220 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, -1);
1221 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1223 * Slide the contents of right down one entry.
1227 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
1228 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
+ 1], ARCH_CONVERT
),
1233 memmove(rkp
, rkp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
1234 memmove(rpp
, rpp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
1235 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1236 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1238 memmove(rrp
, rrp
+ 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1239 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1240 key
.ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1241 key
.ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1245 * Update the parent key values of right.
1247 if ((error
= xfs_alloc_updkey(cur
, rkp
, level
+ 1)))
1250 * Slide the cursor value left one.
1252 cur
->bc_ptrs
[level
]--;
1258 * Allocate a new root block, fill it in.
1260 STATIC
int /* error */
1262 xfs_btree_cur_t
*cur
, /* btree cursor */
1263 int *stat
) /* success/failure */
1265 int error
; /* error return value */
1266 xfs_agblock_t lbno
; /* left block number */
1267 xfs_buf_t
*lbp
; /* left btree buffer */
1268 xfs_alloc_block_t
*left
; /* left btree block */
1269 xfs_mount_t
*mp
; /* mount structure */
1270 xfs_agblock_t nbno
; /* new block number */
1271 xfs_buf_t
*nbp
; /* new (root) buffer */
1272 xfs_alloc_block_t
*new; /* new (root) btree block */
1273 int nptr
; /* new value for key index, 1 or 2 */
1274 xfs_agblock_t rbno
; /* right block number */
1275 xfs_buf_t
*rbp
; /* right btree buffer */
1276 xfs_alloc_block_t
*right
; /* right btree block */
1280 ASSERT(cur
->bc_nlevels
< XFS_AG_MAXLEVELS(mp
));
1282 * Get a buffer from the freelist blocks, for the new root.
1284 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1288 * None available, we fail.
1290 if (nbno
== NULLAGBLOCK
) {
1294 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1295 nbp
= xfs_btree_get_bufs(mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
, nbno
,
1297 new = XFS_BUF_TO_ALLOC_BLOCK(nbp
);
1299 * Set the root data in the a.g. freespace structure.
1302 xfs_agf_t
*agf
; /* a.g. freespace header */
1303 xfs_agnumber_t seqno
;
1305 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
1306 INT_SET(agf
->agf_roots
[cur
->bc_btnum
], ARCH_CONVERT
, nbno
);
1307 INT_MOD(agf
->agf_levels
[cur
->bc_btnum
], ARCH_CONVERT
, 1);
1308 seqno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
1309 mp
->m_perag
[seqno
].pagf_levels
[cur
->bc_btnum
]++;
1310 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1311 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
1314 * At the previous root level there are now two blocks: the old
1315 * root, and the new block generated when it was split.
1316 * We don't know which one the cursor is pointing at, so we
1317 * set up variables "left" and "right" for each case.
1319 lbp
= cur
->bc_bufs
[cur
->bc_nlevels
- 1];
1320 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1322 if ((error
= xfs_btree_check_sblock(cur
, left
, cur
->bc_nlevels
- 1, lbp
)))
1325 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1327 * Our block is left, pick up the right block.
1329 lbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(lbp
));
1330 rbno
= INT_GET(left
->bb_rightsib
, ARCH_CONVERT
);
1331 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1332 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
1333 XFS_ALLOC_BTREE_REF
)))
1335 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1336 if ((error
= xfs_btree_check_sblock(cur
, right
,
1337 cur
->bc_nlevels
- 1, rbp
)))
1342 * Our block is right, pick up the left block.
1346 rbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(rbp
));
1347 lbno
= INT_GET(right
->bb_leftsib
, ARCH_CONVERT
);
1348 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1349 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
1350 XFS_ALLOC_BTREE_REF
)))
1352 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1353 if ((error
= xfs_btree_check_sblock(cur
, left
,
1354 cur
->bc_nlevels
- 1, lbp
)))
1359 * Fill in the new block's btree header and log it.
1361 INT_SET(new->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
1362 INT_SET(new->bb_level
, ARCH_CONVERT
, (__uint16_t
)cur
->bc_nlevels
);
1363 INT_SET(new->bb_numrecs
, ARCH_CONVERT
, 2);
1364 INT_SET(new->bb_leftsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1365 INT_SET(new->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1366 xfs_alloc_log_block(cur
->bc_tp
, nbp
, XFS_BB_ALL_BITS
);
1367 ASSERT(lbno
!= NULLAGBLOCK
&& rbno
!= NULLAGBLOCK
);
1369 * Fill in the key data in the new root.
1372 xfs_alloc_key_t
*kp
; /* btree key pointer */
1374 kp
= XFS_ALLOC_KEY_ADDR(new, 1, cur
);
1375 if (INT_GET(left
->bb_level
, ARCH_CONVERT
) > 0) {
1376 kp
[0] = *XFS_ALLOC_KEY_ADDR(left
, 1, cur
); /* INT_: structure copy */
1377 kp
[1] = *XFS_ALLOC_KEY_ADDR(right
, 1, cur
);/* INT_: structure copy */
1379 xfs_alloc_rec_t
*rp
; /* btree record pointer */
1381 rp
= XFS_ALLOC_REC_ADDR(left
, 1, cur
);
1382 kp
[0].ar_startblock
= rp
->ar_startblock
; /* INT_: direct copy */
1383 kp
[0].ar_blockcount
= rp
->ar_blockcount
; /* INT_: direct copy */
1384 rp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1385 kp
[1].ar_startblock
= rp
->ar_startblock
; /* INT_: direct copy */
1386 kp
[1].ar_blockcount
= rp
->ar_blockcount
; /* INT_: direct copy */
1389 xfs_alloc_log_keys(cur
, nbp
, 1, 2);
1391 * Fill in the pointer data in the new root.
1394 xfs_alloc_ptr_t
*pp
; /* btree address pointer */
1396 pp
= XFS_ALLOC_PTR_ADDR(new, 1, cur
);
1397 INT_SET(pp
[0], ARCH_CONVERT
, lbno
);
1398 INT_SET(pp
[1], ARCH_CONVERT
, rbno
);
1400 xfs_alloc_log_ptrs(cur
, nbp
, 1, 2);
1402 * Fix up the cursor.
1404 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
1405 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
1412 * Move 1 record right from cur/level if possible.
1413 * Update cur to reflect the new path.
1415 STATIC
int /* error */
1417 xfs_btree_cur_t
*cur
, /* btree cursor */
1418 int level
, /* level to shift record on */
1419 int *stat
) /* success/failure */
1421 int error
; /* error return value */
1422 int i
; /* loop index */
1423 xfs_alloc_key_t key
; /* key value for leaf level upward */
1424 xfs_buf_t
*lbp
; /* buffer for left (current) block */
1425 xfs_alloc_block_t
*left
; /* left (current) btree block */
1426 xfs_buf_t
*rbp
; /* buffer for right neighbor block */
1427 xfs_alloc_block_t
*right
; /* right neighbor btree block */
1428 xfs_alloc_key_t
*rkp
; /* key pointer for right block */
1429 xfs_btree_cur_t
*tcur
; /* temporary cursor */
1432 * Set up variables for this block as "left".
1434 lbp
= cur
->bc_bufs
[level
];
1435 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1437 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1441 * If we've got no right sibling then we can't shift an entry right.
1443 if (INT_GET(left
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1448 * If the cursor entry is the one that would be moved, don't
1449 * do it... it's too complicated.
1451 if (cur
->bc_ptrs
[level
] >= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
)) {
1456 * Set up the right neighbor as "right".
1458 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1459 cur
->bc_private
.a
.agno
, INT_GET(left
->bb_rightsib
, ARCH_CONVERT
), 0, &rbp
,
1460 XFS_ALLOC_BTREE_REF
)))
1462 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1463 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1466 * If it's full, it can't take another entry.
1468 if (INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1473 * Make a hole at the start of the right neighbor block, then
1474 * copy the last left block entry to the hole.
1477 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1478 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1479 xfs_alloc_ptr_t
*rpp
; /* address pointer for right block */
1481 lkp
= XFS_ALLOC_KEY_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1482 lpp
= XFS_ALLOC_PTR_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1483 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1484 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1486 for (i
= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) - 1; i
>= 0; i
--) {
1487 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(rpp
[i
], ARCH_CONVERT
), level
)))
1491 memmove(rkp
+ 1, rkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
));
1492 memmove(rpp
+ 1, rpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
));
1494 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(*lpp
, ARCH_CONVERT
), level
)))
1497 *rkp
= *lkp
; /* INT_: copy */
1498 *rpp
= *lpp
; /* INT_: copy */
1499 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1500 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1501 xfs_btree_check_key(cur
->bc_btnum
, rkp
, rkp
+ 1);
1503 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1504 xfs_alloc_rec_t
*rrp
; /* record pointer for right block */
1506 lrp
= XFS_ALLOC_REC_ADDR(left
, INT_GET(left
->bb_numrecs
, ARCH_CONVERT
), cur
);
1507 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1508 memmove(rrp
+ 1, rrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1510 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1);
1511 key
.ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1512 key
.ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1514 xfs_btree_check_rec(cur
->bc_btnum
, rrp
, rrp
+ 1);
1517 * Decrement and log left's numrecs, bump and log right's numrecs.
1519 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -1);
1520 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1521 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
1522 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1524 * Using a temporary cursor, update the parent key values of the
1525 * block on the right.
1527 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
1529 i
= xfs_btree_lastrec(tcur
, level
);
1530 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1531 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)) ||
1532 (error
= xfs_alloc_updkey(tcur
, rkp
, level
+ 1)))
1534 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1538 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
1543 * Split cur/level block in half.
1544 * Return new block number and its first record (to be inserted into parent).
1546 STATIC
int /* error */
1548 xfs_btree_cur_t
*cur
, /* btree cursor */
1549 int level
, /* level to split */
1550 xfs_agblock_t
*bnop
, /* output: block number allocated */
1551 xfs_alloc_key_t
*keyp
, /* output: first key of new block */
1552 xfs_btree_cur_t
**curp
, /* output: new cursor */
1553 int *stat
) /* success/failure */
1555 int error
; /* error return value */
1556 int i
; /* loop index/record number */
1557 xfs_agblock_t lbno
; /* left (current) block number */
1558 xfs_buf_t
*lbp
; /* buffer for left block */
1559 xfs_alloc_block_t
*left
; /* left (current) btree block */
1560 xfs_agblock_t rbno
; /* right (new) block number */
1561 xfs_buf_t
*rbp
; /* buffer for right block */
1562 xfs_alloc_block_t
*right
; /* right (new) btree block */
1565 * Allocate the new block from the freelist.
1566 * If we can't do it, we're toast. Give up.
1568 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1571 if (rbno
== NULLAGBLOCK
) {
1575 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1576 rbp
= xfs_btree_get_bufs(cur
->bc_mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
,
1579 * Set up the new block as "right".
1581 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1583 * "Left" is the current (according to the cursor) block.
1585 lbp
= cur
->bc_bufs
[level
];
1586 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1588 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1592 * Fill in the btree header for the new block.
1594 INT_SET(right
->bb_magic
, ARCH_CONVERT
, xfs_magics
[cur
->bc_btnum
]);
1595 right
->bb_level
= left
->bb_level
; /* INT_: direct copy */
1596 INT_SET(right
->bb_numrecs
, ARCH_CONVERT
, (__uint16_t
)(INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) / 2));
1598 * Make sure that if there's an odd number of entries now, that
1599 * each new block will have the same number of entries.
1601 if ((INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) & 1) &&
1602 cur
->bc_ptrs
[level
] <= INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1)
1603 INT_MOD(right
->bb_numrecs
, ARCH_CONVERT
, +1);
1604 i
= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) - INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) + 1;
1606 * For non-leaf blocks, copy keys and addresses over to the new block.
1609 xfs_alloc_key_t
*lkp
; /* left btree key pointer */
1610 xfs_alloc_ptr_t
*lpp
; /* left btree address pointer */
1611 xfs_alloc_key_t
*rkp
; /* right btree key pointer */
1612 xfs_alloc_ptr_t
*rpp
; /* right btree address pointer */
1614 lkp
= XFS_ALLOC_KEY_ADDR(left
, i
, cur
);
1615 lpp
= XFS_ALLOC_PTR_ADDR(left
, i
, cur
);
1616 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1617 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1619 for (i
= 0; i
< INT_GET(right
->bb_numrecs
, ARCH_CONVERT
); i
++) {
1620 if ((error
= xfs_btree_check_sptr(cur
, INT_GET(lpp
[i
], ARCH_CONVERT
), level
)))
1624 memcpy(rkp
, lkp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rkp
)); /* INT_: copy */
1625 memcpy(rpp
, lpp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rpp
)); /* INT_: copy */
1626 xfs_alloc_log_keys(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1627 xfs_alloc_log_ptrs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1631 * For leaf blocks, copy records over to the new block.
1634 xfs_alloc_rec_t
*lrp
; /* left btree record pointer */
1635 xfs_alloc_rec_t
*rrp
; /* right btree record pointer */
1637 lrp
= XFS_ALLOC_REC_ADDR(left
, i
, cur
);
1638 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1639 memcpy(rrp
, lrp
, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
) * sizeof(*rrp
));
1640 xfs_alloc_log_recs(cur
, rbp
, 1, INT_GET(right
->bb_numrecs
, ARCH_CONVERT
));
1641 keyp
->ar_startblock
= rrp
->ar_startblock
; /* INT_: direct copy */
1642 keyp
->ar_blockcount
= rrp
->ar_blockcount
; /* INT_: direct copy */
1645 * Find the left block number by looking in the buffer.
1646 * Adjust numrecs, sibling pointers.
1648 lbno
= XFS_DADDR_TO_AGBNO(cur
->bc_mp
, XFS_BUF_ADDR(lbp
));
1649 INT_MOD(left
->bb_numrecs
, ARCH_CONVERT
, -(INT_GET(right
->bb_numrecs
, ARCH_CONVERT
)));
1650 right
->bb_rightsib
= left
->bb_rightsib
; /* INT_: direct copy */
1651 INT_SET(left
->bb_rightsib
, ARCH_CONVERT
, rbno
);
1652 INT_SET(right
->bb_leftsib
, ARCH_CONVERT
, lbno
);
1653 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_ALL_BITS
);
1654 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
1656 * If there's a block to the new block's right, make that block
1657 * point back to right instead of to left.
1659 if (INT_GET(right
->bb_rightsib
, ARCH_CONVERT
) != NULLAGBLOCK
) {
1660 xfs_alloc_block_t
*rrblock
; /* rr btree block */
1661 xfs_buf_t
*rrbp
; /* buffer for rrblock */
1663 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1664 cur
->bc_private
.a
.agno
, INT_GET(right
->bb_rightsib
, ARCH_CONVERT
), 0,
1665 &rrbp
, XFS_ALLOC_BTREE_REF
)))
1667 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
1668 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
1670 INT_SET(rrblock
->bb_leftsib
, ARCH_CONVERT
, rbno
);
1671 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
1674 * If the cursor is really in the right block, move it there.
1675 * If it's just pointing past the last entry in left, then we'll
1676 * insert there, so don't change anything in that case.
1678 if (cur
->bc_ptrs
[level
] > INT_GET(left
->bb_numrecs
, ARCH_CONVERT
) + 1) {
1679 xfs_btree_setbuf(cur
, level
, rbp
);
1680 cur
->bc_ptrs
[level
] -= INT_GET(left
->bb_numrecs
, ARCH_CONVERT
);
1683 * If there are more levels, we'll need another cursor which refers to
1684 * the right block, no matter where this cursor was.
1686 if (level
+ 1 < cur
->bc_nlevels
) {
1687 if ((error
= xfs_btree_dup_cursor(cur
, curp
)))
1689 (*curp
)->bc_ptrs
[level
+ 1]++;
1697 * Update keys at all levels from here to the root along the cursor's path.
1699 STATIC
int /* error */
1701 xfs_btree_cur_t
*cur
, /* btree cursor */
1702 xfs_alloc_key_t
*keyp
, /* new key value to update to */
1703 int level
) /* starting level for update */
1705 int ptr
; /* index of key in block */
1708 * Go up the tree from this level toward the root.
1709 * At each level, update the key value to the value input.
1710 * Stop when we reach a level where the cursor isn't pointing
1711 * at the first entry in the block.
1713 for (ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
1714 xfs_alloc_block_t
*block
; /* btree block */
1715 xfs_buf_t
*bp
; /* buffer for block */
1717 int error
; /* error return value */
1719 xfs_alloc_key_t
*kp
; /* ptr to btree block keys */
1721 bp
= cur
->bc_bufs
[level
];
1722 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1724 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1727 ptr
= cur
->bc_ptrs
[level
];
1728 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
1730 xfs_alloc_log_keys(cur
, bp
, ptr
, ptr
);
1736 * Externally visible routines.
1740 * Decrement cursor by one record at the level.
1741 * For nonzero levels the leaf-ward information is untouched.
1744 xfs_alloc_decrement(
1745 xfs_btree_cur_t
*cur
, /* btree cursor */
1746 int level
, /* level in btree, 0 is leaf */
1747 int *stat
) /* success/failure */
1749 xfs_alloc_block_t
*block
; /* btree block */
1750 int error
; /* error return value */
1751 int lev
; /* btree level */
1753 ASSERT(level
< cur
->bc_nlevels
);
1755 * Read-ahead to the left at this level.
1757 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1759 * Decrement the ptr at this level. If we're still in the block
1762 if (--cur
->bc_ptrs
[level
] > 0) {
1767 * Get a pointer to the btree block.
1769 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[level
]);
1771 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
1772 cur
->bc_bufs
[level
])))
1776 * If we just went off the left edge of the tree, return failure.
1778 if (INT_GET(block
->bb_leftsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1783 * March up the tree decrementing pointers.
1784 * Stop when we don't go off the left edge of a block.
1786 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1787 if (--cur
->bc_ptrs
[lev
] > 0)
1790 * Read-ahead the left block, we're going to read it
1793 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1796 * If we went off the root then we are seriously confused.
1798 ASSERT(lev
< cur
->bc_nlevels
);
1800 * Now walk back down the tree, fixing up the cursor's buffer
1801 * pointers and key numbers.
1803 for (block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[lev
]); lev
> level
; ) {
1804 xfs_agblock_t agbno
; /* block number of btree block */
1805 xfs_buf_t
*bp
; /* buffer pointer for block */
1807 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1808 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1809 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1810 XFS_ALLOC_BTREE_REF
)))
1813 xfs_btree_setbuf(cur
, lev
, bp
);
1814 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1815 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1817 cur
->bc_ptrs
[lev
] = INT_GET(block
->bb_numrecs
, ARCH_CONVERT
);
1824 * Delete the record pointed to by cur.
1825 * The cursor refers to the place where the record was (could be inserted)
1826 * when the operation returns.
1830 xfs_btree_cur_t
*cur
, /* btree cursor */
1831 int *stat
) /* success/failure */
1833 int error
; /* error return value */
1834 int i
; /* result code */
1835 int level
; /* btree level */
1838 * Go up the tree, starting at leaf level.
1839 * If 2 is returned then a join was done; go to the next level.
1840 * Otherwise we are done.
1842 for (level
= 0, i
= 2; i
== 2; level
++) {
1843 if ((error
= xfs_alloc_delrec(cur
, level
, &i
)))
1847 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
1848 if (cur
->bc_ptrs
[level
] == 0) {
1849 if ((error
= xfs_alloc_decrement(cur
, level
, &i
)))
1860 * Get the data from the pointed-to record.
1864 xfs_btree_cur_t
*cur
, /* btree cursor */
1865 xfs_agblock_t
*bno
, /* output: starting block of extent */
1866 xfs_extlen_t
*len
, /* output: length of extent */
1867 int *stat
) /* output: success/failure */
1869 xfs_alloc_block_t
*block
; /* btree block */
1871 int error
; /* error return value */
1873 int ptr
; /* record number */
1875 ptr
= cur
->bc_ptrs
[0];
1876 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
1878 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
1882 * Off the right end or left end, return failure.
1884 if (ptr
> INT_GET(block
->bb_numrecs
, ARCH_CONVERT
) || ptr
<= 0) {
1889 * Point to the record and extract its data.
1892 xfs_alloc_rec_t
*rec
; /* record data */
1894 rec
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
1895 *bno
= INT_GET(rec
->ar_startblock
, ARCH_CONVERT
);
1896 *len
= INT_GET(rec
->ar_blockcount
, ARCH_CONVERT
);
1903 * Increment cursor by one record at the level.
1904 * For nonzero levels the leaf-ward information is untouched.
1907 xfs_alloc_increment(
1908 xfs_btree_cur_t
*cur
, /* btree cursor */
1909 int level
, /* level in btree, 0 is leaf */
1910 int *stat
) /* success/failure */
1912 xfs_alloc_block_t
*block
; /* btree block */
1913 xfs_buf_t
*bp
; /* tree block buffer */
1914 int error
; /* error return value */
1915 int lev
; /* btree level */
1917 ASSERT(level
< cur
->bc_nlevels
);
1919 * Read-ahead to the right at this level.
1921 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1923 * Get a pointer to the btree block.
1925 bp
= cur
->bc_bufs
[level
];
1926 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1928 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1932 * Increment the ptr at this level. If we're still in the block
1935 if (++cur
->bc_ptrs
[level
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
1940 * If we just went off the right edge of the tree, return failure.
1942 if (INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
) {
1947 * March up the tree incrementing pointers.
1948 * Stop when we don't go off the right edge of a block.
1950 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1951 bp
= cur
->bc_bufs
[lev
];
1952 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1954 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1957 if (++cur
->bc_ptrs
[lev
] <= INT_GET(block
->bb_numrecs
, ARCH_CONVERT
))
1960 * Read-ahead the right block, we're going to read it
1963 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1966 * If we went off the root then we are seriously confused.
1968 ASSERT(lev
< cur
->bc_nlevels
);
1970 * Now walk back down the tree, fixing up the cursor's buffer
1971 * pointers and key numbers.
1973 for (bp
= cur
->bc_bufs
[lev
], block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1975 xfs_agblock_t agbno
; /* block number of btree block */
1977 agbno
= INT_GET(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
), ARCH_CONVERT
);
1978 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1979 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1980 XFS_ALLOC_BTREE_REF
)))
1983 xfs_btree_setbuf(cur
, lev
, bp
);
1984 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1985 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1987 cur
->bc_ptrs
[lev
] = 1;
1994 * Insert the current record at the point referenced by cur.
1995 * The cursor may be inconsistent on return if splits have been done.
1999 xfs_btree_cur_t
*cur
, /* btree cursor */
2000 int *stat
) /* success/failure */
2002 int error
; /* error return value */
2003 int i
; /* result value, 0 for failure */
2004 int level
; /* current level number in btree */
2005 xfs_agblock_t nbno
; /* new block number (split result) */
2006 xfs_btree_cur_t
*ncur
; /* new cursor (split result) */
2007 xfs_alloc_rec_t nrec
; /* record being inserted this level */
2008 xfs_btree_cur_t
*pcur
; /* previous level's cursor */
2012 INT_SET(nrec
.ar_startblock
, ARCH_CONVERT
, cur
->bc_rec
.a
.ar_startblock
);
2013 INT_SET(nrec
.ar_blockcount
, ARCH_CONVERT
, cur
->bc_rec
.a
.ar_blockcount
);
2014 ncur
= (xfs_btree_cur_t
*)0;
2017 * Loop going up the tree, starting at the leaf level.
2018 * Stop when we don't get a split block, that must mean that
2019 * the insert is finished with this level.
2023 * Insert nrec/nbno into this level of the tree.
2024 * Note if we fail, nbno will be null.
2026 if ((error
= xfs_alloc_insrec(pcur
, level
++, &nbno
, &nrec
, &ncur
,
2029 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
2033 * See if the cursor we just used is trash.
2034 * Can't trash the caller's cursor, but otherwise we should
2035 * if ncur is a new cursor or we're about to be done.
2037 if (pcur
!= cur
&& (ncur
|| nbno
== NULLAGBLOCK
)) {
2038 cur
->bc_nlevels
= pcur
->bc_nlevels
;
2039 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
2042 * If we got a new cursor, switch to it.
2046 ncur
= (xfs_btree_cur_t
*)0;
2048 } while (nbno
!= NULLAGBLOCK
);
2054 * Lookup the record equal to [bno, len] in the btree given by cur.
2057 xfs_alloc_lookup_eq(
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_EQ
, stat
);
2069 * Lookup the first record greater than or equal to [bno, len]
2070 * in the btree given by cur.
2073 xfs_alloc_lookup_ge(
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 */
2077 int *stat
) /* success/failure */
2079 cur
->bc_rec
.a
.ar_startblock
= bno
;
2080 cur
->bc_rec
.a
.ar_blockcount
= len
;
2081 return xfs_alloc_lookup(cur
, XFS_LOOKUP_GE
, stat
);
2085 * Lookup the first record less than or equal to [bno, len]
2086 * in the btree given by cur.
2089 xfs_alloc_lookup_le(
2090 xfs_btree_cur_t
*cur
, /* btree cursor */
2091 xfs_agblock_t bno
, /* starting block of extent */
2092 xfs_extlen_t len
, /* length of extent */
2093 int *stat
) /* success/failure */
2095 cur
->bc_rec
.a
.ar_startblock
= bno
;
2096 cur
->bc_rec
.a
.ar_blockcount
= len
;
2097 return xfs_alloc_lookup(cur
, XFS_LOOKUP_LE
, stat
);
2101 * Update the record referred to by cur, to the value given by [bno, len].
2102 * This either works (return 0) or gets an EFSCORRUPTED error.
2106 xfs_btree_cur_t
*cur
, /* btree cursor */
2107 xfs_agblock_t bno
, /* starting block of extent */
2108 xfs_extlen_t len
) /* length of extent */
2110 xfs_alloc_block_t
*block
; /* btree block to update */
2111 int error
; /* error return value */
2112 int ptr
; /* current record number (updating) */
2116 * Pick up the a.g. freelist struct and the current block.
2118 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
2120 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
2124 * Get the address of the rec to be updated.
2126 ptr
= cur
->bc_ptrs
[0];
2128 xfs_alloc_rec_t
*rp
; /* pointer to updated record */
2130 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
2132 * Fill in the new contents and log them.
2134 INT_SET(rp
->ar_startblock
, ARCH_CONVERT
, bno
);
2135 INT_SET(rp
->ar_blockcount
, ARCH_CONVERT
, len
);
2136 xfs_alloc_log_recs(cur
, cur
->bc_bufs
[0], ptr
, ptr
);
2139 * If it's the by-size btree and it's the last leaf block and
2140 * it's the last record... then update the size of the longest
2141 * extent in the a.g., which we cache in the a.g. freelist header.
2143 if (cur
->bc_btnum
== XFS_BTNUM_CNT
&&
2144 INT_GET(block
->bb_rightsib
, ARCH_CONVERT
) == NULLAGBLOCK
&&
2145 ptr
== INT_GET(block
->bb_numrecs
, ARCH_CONVERT
)) {
2146 xfs_agf_t
*agf
; /* a.g. freespace header */
2147 xfs_agnumber_t seqno
;
2149 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
2150 seqno
= INT_GET(agf
->agf_seqno
, ARCH_CONVERT
);
2151 cur
->bc_mp
->m_perag
[seqno
].pagf_longest
= len
;
2152 INT_SET(agf
->agf_longest
, ARCH_CONVERT
, len
);
2153 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
2157 * Updating first record in leaf. Pass new key value up to our parent.
2160 xfs_alloc_key_t key
; /* key containing [bno, len] */
2162 INT_SET(key
.ar_startblock
, ARCH_CONVERT
, bno
);
2163 INT_SET(key
.ar_blockcount
, ARCH_CONVERT
, len
);
2164 if ((error
= xfs_alloc_updkey(cur
, &key
, 1)))