]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_alloc_btree.c
2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * Free space allocation for XFS.
26 * Single level of the xfs_alloc_delete record deletion routine.
27 * Delete record pointed to by cur/level.
28 * Remove the record from its block then rebalance the tree.
29 * Return 0 for error, 1 for done, 2 to go on to the next level.
31 STATIC
int /* error */
33 xfs_btree_cur_t
*cur
, /* btree cursor */
34 int level
, /* level removing record from */
35 int *stat
) /* fail/done/go-on */
37 xfs_agf_t
*agf
; /* allocation group freelist header */
38 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
39 xfs_agblock_t bno
; /* btree block number */
40 xfs_buf_t
*bp
; /* buffer for block */
41 int error
; /* error return value */
42 int i
; /* loop index */
43 xfs_alloc_key_t key
; /* kp points here if block is level 0 */
44 xfs_agblock_t lbno
; /* left block's block number */
45 xfs_buf_t
*lbp
; /* left block's buffer pointer */
46 xfs_alloc_block_t
*left
; /* left btree block */
47 xfs_alloc_key_t
*lkp
=NULL
; /* left block key pointer */
48 xfs_alloc_ptr_t
*lpp
=NULL
; /* left block address pointer */
49 int lrecs
=0; /* number of records in left block */
50 xfs_alloc_rec_t
*lrp
; /* left block record pointer */
51 xfs_mount_t
*mp
; /* mount structure */
52 int ptr
; /* index in btree block for this rec */
53 xfs_agblock_t rbno
; /* right block's block number */
54 xfs_buf_t
*rbp
; /* right block's buffer pointer */
55 xfs_alloc_block_t
*right
; /* right btree block */
56 xfs_alloc_key_t
*rkp
; /* right block key pointer */
57 xfs_alloc_ptr_t
*rpp
; /* right block address pointer */
58 int rrecs
=0; /* number of records in right block */
59 xfs_alloc_rec_t
*rrp
; /* right block record pointer */
60 xfs_btree_cur_t
*tcur
; /* temporary btree cursor */
63 * Get the index of the entry being deleted, check for nothing there.
65 ptr
= cur
->bc_ptrs
[level
];
71 * Get the buffer & block containing the record or key/ptr.
73 bp
= cur
->bc_bufs
[level
];
74 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
76 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
80 * Fail if we're off the end of the block.
82 if (ptr
> be16_to_cpu(block
->bb_numrecs
)) {
86 XFS_STATS_INC(xs_abt_delrec
);
88 * It's a nonleaf. Excise the key and ptr being deleted, by
89 * sliding the entries past them down one.
90 * Log the changed areas of the block.
93 lkp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
94 lpp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
96 for (i
= ptr
; i
< be16_to_cpu(block
->bb_numrecs
); i
++) {
97 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(lpp
[i
]), level
)))
101 if (ptr
< be16_to_cpu(block
->bb_numrecs
)) {
102 memmove(&lkp
[ptr
- 1], &lkp
[ptr
],
103 (be16_to_cpu(block
->bb_numrecs
) - ptr
) * sizeof(*lkp
));
104 memmove(&lpp
[ptr
- 1], &lpp
[ptr
],
105 (be16_to_cpu(block
->bb_numrecs
) - ptr
) * sizeof(*lpp
));
106 xfs_alloc_log_ptrs(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
) - 1);
107 xfs_alloc_log_keys(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
) - 1);
111 * It's a leaf. Excise the record being deleted, by sliding the
112 * entries past it down one. Log the changed areas of the block.
115 lrp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
116 if (ptr
< be16_to_cpu(block
->bb_numrecs
)) {
117 memmove(&lrp
[ptr
- 1], &lrp
[ptr
],
118 (be16_to_cpu(block
->bb_numrecs
) - ptr
) * sizeof(*lrp
));
119 xfs_alloc_log_recs(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
) - 1);
122 * If it's the first record in the block, we'll need a key
123 * structure to pass up to the next level (updkey).
126 key
.ar_startblock
= lrp
->ar_startblock
;
127 key
.ar_blockcount
= lrp
->ar_blockcount
;
132 * Decrement and log the number of entries in the block.
134 be16_add(&block
->bb_numrecs
, -1);
135 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
137 * See if the longest free extent in the allocation group was
138 * changed by this operation. True if it's the by-size btree, and
139 * this is the leaf level, and there is no right sibling block,
140 * and this was the last record.
142 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
146 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
147 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
148 ptr
> be16_to_cpu(block
->bb_numrecs
)) {
149 ASSERT(ptr
== be16_to_cpu(block
->bb_numrecs
) + 1);
151 * There are still records in the block. Grab the size
154 if (be16_to_cpu(block
->bb_numrecs
)) {
155 rrp
= XFS_ALLOC_REC_ADDR(block
, be16_to_cpu(block
->bb_numrecs
), cur
);
156 agf
->agf_longest
= rrp
->ar_blockcount
;
159 * No free extents left.
162 agf
->agf_longest
= 0;
163 mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_longest
=
164 be32_to_cpu(agf
->agf_longest
);
165 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
169 * Is this the root level? If so, we're almost done.
171 if (level
== cur
->bc_nlevels
- 1) {
173 * If this is the root level,
174 * and there's only one entry left,
175 * and it's NOT the leaf level,
176 * then we can get rid of this level.
178 if (be16_to_cpu(block
->bb_numrecs
) == 1 && level
> 0) {
180 * lpp is still set to the first pointer in the block.
181 * Make it the new root of the btree.
183 bno
= be32_to_cpu(agf
->agf_roots
[cur
->bc_btnum
]);
184 agf
->agf_roots
[cur
->bc_btnum
] = *lpp
;
185 be32_add(&agf
->agf_levels
[cur
->bc_btnum
], -1);
186 mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_levels
[cur
->bc_btnum
]--;
188 * Put this buffer/block on the ag's freelist.
190 if ((error
= xfs_alloc_put_freelist(cur
->bc_tp
,
191 cur
->bc_private
.a
.agbp
, NULL
, bno
, 1)))
194 * Since blocks move to the free list without the
195 * coordination used in xfs_bmap_finish, we can't allow
196 * block to be available for reallocation and
197 * non-transaction writing (user data) until we know
198 * that the transaction that moved it to the free list
199 * is permanently on disk. We track the blocks by
200 * declaring these blocks as "busy"; the busy list is
201 * maintained on a per-ag basis and each transaction
202 * records which entries should be removed when the
203 * iclog commits to disk. If a busy block is
204 * allocated, the iclog is pushed up to the LSN
205 * that freed the block.
207 xfs_alloc_mark_busy(cur
->bc_tp
,
208 be32_to_cpu(agf
->agf_seqno
), bno
, 1);
210 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
211 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
212 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
214 * Update the cursor so there's one fewer level.
216 xfs_btree_setbuf(cur
, level
, NULL
);
218 } else if (level
> 0 &&
219 (error
= xfs_alloc_decrement(cur
, level
, &i
)))
225 * If we deleted the leftmost entry in the block, update the
226 * key values above us in the tree.
228 if (ptr
== 1 && (error
= xfs_alloc_updkey(cur
, lkp
, level
+ 1)))
231 * If the number of records remaining in the block is at least
232 * the minimum, we're done.
234 if (be16_to_cpu(block
->bb_numrecs
) >= XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
235 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
241 * Otherwise, we have to move some records around to keep the
242 * tree balanced. Look at the left and right sibling blocks to
243 * see if we can re-balance by moving only one record.
245 rbno
= be32_to_cpu(block
->bb_rightsib
);
246 lbno
= be32_to_cpu(block
->bb_leftsib
);
248 ASSERT(rbno
!= NULLAGBLOCK
|| lbno
!= NULLAGBLOCK
);
250 * Duplicate the cursor so our btree manipulations here won't
251 * disrupt the next level up.
253 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
256 * If there's a right sibling, see if it's ok to shift an entry
259 if (rbno
!= NULLAGBLOCK
) {
261 * Move the temp cursor to the last entry in the next block.
262 * Actually any entry but the first would suffice.
264 i
= xfs_btree_lastrec(tcur
, level
);
265 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
266 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)))
268 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
269 i
= xfs_btree_lastrec(tcur
, level
);
270 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
272 * Grab a pointer to the block.
274 rbp
= tcur
->bc_bufs
[level
];
275 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
277 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
281 * Grab the current block number, for future use.
283 bno
= be32_to_cpu(right
->bb_leftsib
);
285 * If right block is full enough so that removing one entry
286 * won't make it too empty, and left-shifting an entry out
287 * of right to us works, we're done.
289 if (be16_to_cpu(right
->bb_numrecs
) - 1 >=
290 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
291 if ((error
= xfs_alloc_lshift(tcur
, level
, &i
)))
294 ASSERT(be16_to_cpu(block
->bb_numrecs
) >=
295 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
296 xfs_btree_del_cursor(tcur
,
299 (error
= xfs_alloc_decrement(cur
, level
,
307 * Otherwise, grab the number of records in right for
308 * future reference, and fix up the temp cursor to point
309 * to our block again (last record).
311 rrecs
= be16_to_cpu(right
->bb_numrecs
);
312 if (lbno
!= NULLAGBLOCK
) {
313 i
= xfs_btree_firstrec(tcur
, level
);
314 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
315 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
317 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
321 * If there's a left sibling, see if it's ok to shift an entry
324 if (lbno
!= NULLAGBLOCK
) {
326 * Move the temp cursor to the first entry in the
329 i
= xfs_btree_firstrec(tcur
, level
);
330 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
331 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
333 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
334 xfs_btree_firstrec(tcur
, level
);
336 * Grab a pointer to the block.
338 lbp
= tcur
->bc_bufs
[level
];
339 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
341 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
345 * Grab the current block number, for future use.
347 bno
= be32_to_cpu(left
->bb_rightsib
);
349 * If left block is full enough so that removing one entry
350 * won't make it too empty, and right-shifting an entry out
351 * of left to us works, we're done.
353 if (be16_to_cpu(left
->bb_numrecs
) - 1 >=
354 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
355 if ((error
= xfs_alloc_rshift(tcur
, level
, &i
)))
358 ASSERT(be16_to_cpu(block
->bb_numrecs
) >=
359 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
360 xfs_btree_del_cursor(tcur
,
369 * Otherwise, grab the number of records in right for
372 lrecs
= be16_to_cpu(left
->bb_numrecs
);
375 * Delete the temp cursor, we're done with it.
377 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
379 * If here, we need to do a join to keep the tree balanced.
381 ASSERT(bno
!= NULLAGBLOCK
);
383 * See if we can join with the left neighbor block.
385 if (lbno
!= NULLAGBLOCK
&&
386 lrecs
+ be16_to_cpu(block
->bb_numrecs
) <= XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
388 * Set "right" to be the starting block,
389 * "left" to be the left neighbor.
394 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
395 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
396 XFS_ALLOC_BTREE_REF
)))
398 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
399 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
403 * If that won't work, see if we can join with the right neighbor block.
405 else if (rbno
!= NULLAGBLOCK
&&
406 rrecs
+ be16_to_cpu(block
->bb_numrecs
) <=
407 XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
409 * Set "left" to be the starting block,
410 * "right" to be the right neighbor.
415 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
416 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
417 XFS_ALLOC_BTREE_REF
)))
419 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
420 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
424 * Otherwise, we can't fix the imbalance.
425 * Just return. This is probably a logic error, but it's not fatal.
428 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
434 * We're now going to join "left" and "right" by moving all the stuff
435 * in "right" to "left" and deleting "right".
439 * It's a non-leaf. Move keys and pointers.
441 lkp
= XFS_ALLOC_KEY_ADDR(left
, be16_to_cpu(left
->bb_numrecs
) + 1, cur
);
442 lpp
= XFS_ALLOC_PTR_ADDR(left
, be16_to_cpu(left
->bb_numrecs
) + 1, cur
);
443 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
444 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
446 for (i
= 0; i
< be16_to_cpu(right
->bb_numrecs
); i
++) {
447 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
]), level
)))
451 memcpy(lkp
, rkp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*lkp
));
452 memcpy(lpp
, rpp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*lpp
));
453 xfs_alloc_log_keys(cur
, lbp
, be16_to_cpu(left
->bb_numrecs
) + 1,
454 be16_to_cpu(left
->bb_numrecs
) +
455 be16_to_cpu(right
->bb_numrecs
));
456 xfs_alloc_log_ptrs(cur
, lbp
, be16_to_cpu(left
->bb_numrecs
) + 1,
457 be16_to_cpu(left
->bb_numrecs
) +
458 be16_to_cpu(right
->bb_numrecs
));
461 * It's a leaf. Move records.
463 lrp
= XFS_ALLOC_REC_ADDR(left
, be16_to_cpu(left
->bb_numrecs
) + 1, cur
);
464 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
465 memcpy(lrp
, rrp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*lrp
));
466 xfs_alloc_log_recs(cur
, lbp
, be16_to_cpu(left
->bb_numrecs
) + 1,
467 be16_to_cpu(left
->bb_numrecs
) +
468 be16_to_cpu(right
->bb_numrecs
));
471 * If we joined with the left neighbor, set the buffer in the
472 * cursor to the left block, and fix up the index.
475 xfs_btree_setbuf(cur
, level
, lbp
);
476 cur
->bc_ptrs
[level
] += be16_to_cpu(left
->bb_numrecs
);
479 * If we joined with the right neighbor and there's a level above
480 * us, increment the cursor at that level.
482 else if (level
+ 1 < cur
->bc_nlevels
&&
483 (error
= xfs_alloc_increment(cur
, level
+ 1, &i
)))
486 * Fix up the number of records in the surviving block.
488 be16_add(&left
->bb_numrecs
, be16_to_cpu(right
->bb_numrecs
));
490 * Fix up the right block pointer in the surviving block, and log it.
492 left
->bb_rightsib
= right
->bb_rightsib
;
493 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
495 * If there is a right sibling now, make it point to the
498 if (be32_to_cpu(left
->bb_rightsib
) != NULLAGBLOCK
) {
499 xfs_alloc_block_t
*rrblock
;
502 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
503 cur
->bc_private
.a
.agno
, be32_to_cpu(left
->bb_rightsib
), 0,
504 &rrbp
, XFS_ALLOC_BTREE_REF
)))
506 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
507 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
509 rrblock
->bb_leftsib
= cpu_to_be32(lbno
);
510 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
513 * Free the deleting block by putting it on the freelist.
515 if ((error
= xfs_alloc_put_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
519 * Since blocks move to the free list without the coordination
520 * used in xfs_bmap_finish, we can't allow block to be available
521 * for reallocation and non-transaction writing (user data)
522 * until we know that the transaction that moved it to the free
523 * list is permanently on disk. We track the blocks by declaring
524 * these blocks as "busy"; the busy list is maintained on a
525 * per-ag basis and each transaction records which entries
526 * should be removed when the iclog commits to disk. If a
527 * busy block is allocated, the iclog is pushed up to the
528 * LSN that freed the block.
530 xfs_alloc_mark_busy(cur
->bc_tp
, be32_to_cpu(agf
->agf_seqno
), bno
, 1);
531 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
534 * Adjust the current level's cursor so that we're left referring
535 * to the right node, after we're done.
536 * If this leaves the ptr value 0 our caller will fix it up.
539 cur
->bc_ptrs
[level
]--;
541 * Return value means the next level up has something to do.
547 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
552 * Insert one record/level. Return information to the caller
553 * allowing the next level up to proceed if necessary.
555 STATIC
int /* error */
557 xfs_btree_cur_t
*cur
, /* btree cursor */
558 int level
, /* level to insert record at */
559 xfs_agblock_t
*bnop
, /* i/o: block number inserted */
560 xfs_alloc_rec_t
*recp
, /* i/o: record data inserted */
561 xfs_btree_cur_t
**curp
, /* output: new cursor replacing cur */
562 int *stat
) /* output: success/failure */
564 xfs_agf_t
*agf
; /* allocation group freelist header */
565 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
566 xfs_buf_t
*bp
; /* buffer for block */
567 int error
; /* error return value */
568 int i
; /* loop index */
569 xfs_alloc_key_t key
; /* key value being inserted */
570 xfs_alloc_key_t
*kp
; /* pointer to btree keys */
571 xfs_agblock_t nbno
; /* block number of allocated block */
572 xfs_btree_cur_t
*ncur
; /* new cursor to be used at next lvl */
573 xfs_alloc_key_t nkey
; /* new key value, from split */
574 xfs_alloc_rec_t nrec
; /* new record value, for caller */
575 int optr
; /* old ptr value */
576 xfs_alloc_ptr_t
*pp
; /* pointer to btree addresses */
577 int ptr
; /* index in btree block for this rec */
578 xfs_alloc_rec_t
*rp
; /* pointer to btree records */
580 ASSERT(be32_to_cpu(recp
->ar_blockcount
) > 0);
583 * GCC doesn't understand the (arguably complex) control flow in
584 * this function and complains about uninitialized structure fields
587 memset(&nrec
, 0, sizeof(nrec
));
590 * If we made it to the root level, allocate a new root block
593 if (level
>= cur
->bc_nlevels
) {
594 XFS_STATS_INC(xs_abt_insrec
);
595 if ((error
= xfs_alloc_newroot(cur
, &i
)))
602 * Make a key out of the record data to be inserted, and save it.
604 key
.ar_startblock
= recp
->ar_startblock
;
605 key
.ar_blockcount
= recp
->ar_blockcount
;
606 optr
= ptr
= cur
->bc_ptrs
[level
];
608 * If we're off the left edge, return failure.
614 XFS_STATS_INC(xs_abt_insrec
);
616 * Get pointers to the btree buffer and block.
618 bp
= cur
->bc_bufs
[level
];
619 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
621 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
624 * Check that the new entry is being inserted in the right place.
626 if (ptr
<= be16_to_cpu(block
->bb_numrecs
)) {
628 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
629 xfs_btree_check_rec(cur
->bc_btnum
, recp
, rp
);
631 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
632 xfs_btree_check_key(cur
->bc_btnum
, &key
, kp
);
637 ncur
= (xfs_btree_cur_t
*)0;
639 * If the block is full, we can't insert the new entry until we
640 * make the block un-full.
642 if (be16_to_cpu(block
->bb_numrecs
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
644 * First, try shifting an entry to the right neighbor.
646 if ((error
= xfs_alloc_rshift(cur
, level
, &i
)))
652 * Next, try shifting an entry to the left neighbor.
655 if ((error
= xfs_alloc_lshift(cur
, level
, &i
)))
658 optr
= ptr
= cur
->bc_ptrs
[level
];
661 * Next, try splitting the current block in
662 * half. If this works we have to re-set our
663 * variables because we could be in a
664 * different block now.
666 if ((error
= xfs_alloc_split(cur
, level
, &nbno
,
670 bp
= cur
->bc_bufs
[level
];
671 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
674 xfs_btree_check_sblock(cur
,
678 ptr
= cur
->bc_ptrs
[level
];
679 nrec
.ar_startblock
= nkey
.ar_startblock
;
680 nrec
.ar_blockcount
= nkey
.ar_blockcount
;
683 * Otherwise the insert fails.
693 * At this point we know there's room for our new entry in the block
698 * It's a non-leaf entry. Make a hole for the new data
699 * in the key and ptr regions of the block.
701 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
702 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
704 for (i
= be16_to_cpu(block
->bb_numrecs
); i
>= ptr
; i
--) {
705 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(pp
[i
- 1]), level
)))
709 memmove(&kp
[ptr
], &kp
[ptr
- 1],
710 (be16_to_cpu(block
->bb_numrecs
) - ptr
+ 1) * sizeof(*kp
));
711 memmove(&pp
[ptr
], &pp
[ptr
- 1],
712 (be16_to_cpu(block
->bb_numrecs
) - ptr
+ 1) * sizeof(*pp
));
714 if ((error
= xfs_btree_check_sptr(cur
, *bnop
, level
)))
718 * Now stuff the new data in, bump numrecs and log the new data.
721 pp
[ptr
- 1] = cpu_to_be32(*bnop
);
722 be16_add(&block
->bb_numrecs
, 1);
723 xfs_alloc_log_keys(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
));
724 xfs_alloc_log_ptrs(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
));
726 if (ptr
< be16_to_cpu(block
->bb_numrecs
))
727 xfs_btree_check_key(cur
->bc_btnum
, kp
+ ptr
- 1,
732 * It's a leaf entry. Make a hole for the new record.
734 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
735 memmove(&rp
[ptr
], &rp
[ptr
- 1],
736 (be16_to_cpu(block
->bb_numrecs
) - ptr
+ 1) * sizeof(*rp
));
738 * Now stuff the new record in, bump numrecs
739 * and log the new data.
741 rp
[ptr
- 1] = *recp
; /* INT_: struct copy */
742 be16_add(&block
->bb_numrecs
, 1);
743 xfs_alloc_log_recs(cur
, bp
, ptr
, be16_to_cpu(block
->bb_numrecs
));
745 if (ptr
< be16_to_cpu(block
->bb_numrecs
))
746 xfs_btree_check_rec(cur
->bc_btnum
, rp
+ ptr
- 1,
751 * Log the new number of records in the btree header.
753 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
755 * If we inserted at the start of a block, update the parents' keys.
757 if (optr
== 1 && (error
= xfs_alloc_updkey(cur
, &key
, level
+ 1)))
760 * Look to see if the longest extent in the allocation group
761 * needs to be updated.
764 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
766 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
767 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
768 be32_to_cpu(recp
->ar_blockcount
) > be32_to_cpu(agf
->agf_longest
)) {
770 * If this is a leaf in the by-size btree and there
771 * is no right sibling block and this block is bigger
772 * than the previous longest block, update it.
774 agf
->agf_longest
= recp
->ar_blockcount
;
775 cur
->bc_mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_longest
776 = be32_to_cpu(recp
->ar_blockcount
);
777 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
781 * Return the new block number, if any.
782 * If there is one, give back a record value and a cursor too.
785 if (nbno
!= NULLAGBLOCK
) {
786 *recp
= nrec
; /* INT_: struct copy */
787 *curp
= ncur
; /* INT_: struct copy */
794 * Log header fields from a btree block.
798 xfs_trans_t
*tp
, /* transaction pointer */
799 xfs_buf_t
*bp
, /* buffer containing btree block */
800 int fields
) /* mask of fields: XFS_BB_... */
802 int first
; /* first byte offset logged */
803 int last
; /* last byte offset logged */
804 static const short offsets
[] = { /* table of offsets */
805 offsetof(xfs_alloc_block_t
, bb_magic
),
806 offsetof(xfs_alloc_block_t
, bb_level
),
807 offsetof(xfs_alloc_block_t
, bb_numrecs
),
808 offsetof(xfs_alloc_block_t
, bb_leftsib
),
809 offsetof(xfs_alloc_block_t
, bb_rightsib
),
810 sizeof(xfs_alloc_block_t
)
813 xfs_btree_offsets(fields
, offsets
, XFS_BB_NUM_BITS
, &first
, &last
);
814 xfs_trans_log_buf(tp
, bp
, first
, last
);
818 * Log keys from a btree block (nonleaf).
822 xfs_btree_cur_t
*cur
, /* btree cursor */
823 xfs_buf_t
*bp
, /* buffer containing btree block */
824 int kfirst
, /* index of first key to log */
825 int klast
) /* index of last key to log */
827 xfs_alloc_block_t
*block
; /* btree block to log from */
828 int first
; /* first byte offset logged */
829 xfs_alloc_key_t
*kp
; /* key pointer in btree block */
830 int last
; /* last byte offset logged */
832 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
833 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
834 first
= (int)((xfs_caddr_t
)&kp
[kfirst
- 1] - (xfs_caddr_t
)block
);
835 last
= (int)(((xfs_caddr_t
)&kp
[klast
] - 1) - (xfs_caddr_t
)block
);
836 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
840 * Log block pointer fields from a btree block (nonleaf).
844 xfs_btree_cur_t
*cur
, /* btree cursor */
845 xfs_buf_t
*bp
, /* buffer containing btree block */
846 int pfirst
, /* index of first pointer to log */
847 int plast
) /* index of last pointer to log */
849 xfs_alloc_block_t
*block
; /* btree block to log from */
850 int first
; /* first byte offset logged */
851 int last
; /* last byte offset logged */
852 xfs_alloc_ptr_t
*pp
; /* block-pointer pointer in btree blk */
854 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
855 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
856 first
= (int)((xfs_caddr_t
)&pp
[pfirst
- 1] - (xfs_caddr_t
)block
);
857 last
= (int)(((xfs_caddr_t
)&pp
[plast
] - 1) - (xfs_caddr_t
)block
);
858 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
862 * Log records from a btree block (leaf).
866 xfs_btree_cur_t
*cur
, /* btree cursor */
867 xfs_buf_t
*bp
, /* buffer containing btree block */
868 int rfirst
, /* index of first record to log */
869 int rlast
) /* index of last record to log */
871 xfs_alloc_block_t
*block
; /* btree block to log from */
872 int first
; /* first byte offset logged */
873 int last
; /* last byte offset logged */
874 xfs_alloc_rec_t
*rp
; /* record pointer for btree block */
877 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
878 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
884 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
885 for (p
= &rp
[rfirst
- 1]; p
<= &rp
[rlast
- 1]; p
++)
886 ASSERT(be32_to_cpu(p
->ar_startblock
) +
887 be32_to_cpu(p
->ar_blockcount
) <=
888 be32_to_cpu(agf
->agf_length
));
891 first
= (int)((xfs_caddr_t
)&rp
[rfirst
- 1] - (xfs_caddr_t
)block
);
892 last
= (int)(((xfs_caddr_t
)&rp
[rlast
] - 1) - (xfs_caddr_t
)block
);
893 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
897 * Lookup the record. The cursor is made to point to it, based on dir.
898 * Return 0 if can't find any such record, 1 for success.
900 STATIC
int /* error */
902 xfs_btree_cur_t
*cur
, /* btree cursor */
903 xfs_lookup_t dir
, /* <=, ==, or >= */
904 int *stat
) /* success/failure */
906 xfs_agblock_t agbno
; /* a.g. relative btree block number */
907 xfs_agnumber_t agno
; /* allocation group number */
908 xfs_alloc_block_t
*block
=NULL
; /* current btree block */
909 int diff
; /* difference for the current key */
910 int error
; /* error return value */
911 int keyno
=0; /* current key number */
912 int level
; /* level in the btree */
913 xfs_mount_t
*mp
; /* file system mount point */
915 XFS_STATS_INC(xs_abt_lookup
);
917 * Get the allocation group header, and the root block number.
922 xfs_agf_t
*agf
; /* a.g. freespace header */
924 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
925 agno
= be32_to_cpu(agf
->agf_seqno
);
926 agbno
= be32_to_cpu(agf
->agf_roots
[cur
->bc_btnum
]);
929 * Iterate over each level in the btree, starting at the root.
930 * For each level above the leaves, find the key we need, based
931 * on the lookup record, then follow the corresponding block
932 * pointer down to the next level.
934 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
935 xfs_buf_t
*bp
; /* buffer pointer for btree block */
936 xfs_daddr_t d
; /* disk address of btree block */
939 * Get the disk address we're looking for.
941 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
943 * If the old buffer at this level is for a different block,
944 * throw it away, otherwise just use it.
946 bp
= cur
->bc_bufs
[level
];
947 if (bp
&& XFS_BUF_ADDR(bp
) != d
)
951 * Need to get a new buffer. Read it, then
952 * set it in the cursor, releasing the old one.
954 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
, agno
,
955 agbno
, 0, &bp
, XFS_ALLOC_BTREE_REF
)))
957 xfs_btree_setbuf(cur
, level
, bp
);
959 * Point to the btree block, now that we have the buffer
961 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
962 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
966 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
968 * If we already had a key match at a higher level, we know
969 * we need to use the first entry in this block.
974 * Otherwise we need to search this block. Do a binary search.
977 int high
; /* high entry number */
978 xfs_alloc_key_t
*kkbase
=NULL
;/* base of keys in block */
979 xfs_alloc_rec_t
*krbase
=NULL
;/* base of records in block */
980 int low
; /* low entry number */
983 * Get a pointer to keys or records.
986 kkbase
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
988 krbase
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
990 * Set low and high entry numbers, 1-based.
993 if (!(high
= be16_to_cpu(block
->bb_numrecs
))) {
995 * If the block is empty, the tree must
998 ASSERT(level
== 0 && cur
->bc_nlevels
== 1);
999 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
1004 * Binary search the block.
1006 while (low
<= high
) {
1007 xfs_extlen_t blockcount
; /* key value */
1008 xfs_agblock_t startblock
; /* key value */
1010 XFS_STATS_INC(xs_abt_compare
);
1012 * keyno is average of low and high.
1014 keyno
= (low
+ high
) >> 1;
1016 * Get startblock & blockcount.
1019 xfs_alloc_key_t
*kkp
;
1021 kkp
= kkbase
+ keyno
- 1;
1022 startblock
= be32_to_cpu(kkp
->ar_startblock
);
1023 blockcount
= be32_to_cpu(kkp
->ar_blockcount
);
1025 xfs_alloc_rec_t
*krp
;
1027 krp
= krbase
+ keyno
- 1;
1028 startblock
= be32_to_cpu(krp
->ar_startblock
);
1029 blockcount
= be32_to_cpu(krp
->ar_blockcount
);
1032 * Compute difference to get next direction.
1034 if (cur
->bc_btnum
== XFS_BTNUM_BNO
)
1035 diff
= (int)startblock
-
1036 (int)cur
->bc_rec
.a
.ar_startblock
;
1037 else if (!(diff
= (int)blockcount
-
1038 (int)cur
->bc_rec
.a
.ar_blockcount
))
1039 diff
= (int)startblock
-
1040 (int)cur
->bc_rec
.a
.ar_startblock
;
1042 * Less than, move right.
1047 * Greater than, move left.
1052 * Equal, we're done.
1059 * If there are more levels, set up for the next level
1060 * by getting the block number and filling in the cursor.
1064 * If we moved left, need the previous key number,
1065 * unless there isn't one.
1067 if (diff
> 0 && --keyno
< 1)
1069 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, keyno
, cur
));
1071 if ((error
= xfs_btree_check_sptr(cur
, agbno
, level
)))
1074 cur
->bc_ptrs
[level
] = keyno
;
1078 * Done with the search.
1079 * See if we need to adjust the results.
1081 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1084 * If ge search and we went off the end of the block, but it's
1085 * not the last block, we're in the wrong block.
1087 if (dir
== XFS_LOOKUP_GE
&&
1088 keyno
> be16_to_cpu(block
->bb_numrecs
) &&
1089 be32_to_cpu(block
->bb_rightsib
) != NULLAGBLOCK
) {
1092 cur
->bc_ptrs
[0] = keyno
;
1093 if ((error
= xfs_alloc_increment(cur
, 0, &i
)))
1095 XFS_WANT_CORRUPTED_RETURN(i
== 1);
1100 else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
1102 cur
->bc_ptrs
[0] = keyno
;
1104 * Return if we succeeded or not.
1106 if (keyno
== 0 || keyno
> be16_to_cpu(block
->bb_numrecs
))
1109 *stat
= ((dir
!= XFS_LOOKUP_EQ
) || (diff
== 0));
1114 * Move 1 record left from cur/level if possible.
1115 * Update cur to reflect the new path.
1117 STATIC
int /* error */
1119 xfs_btree_cur_t
*cur
, /* btree cursor */
1120 int level
, /* level to shift record on */
1121 int *stat
) /* success/failure */
1123 int error
; /* error return value */
1125 int i
; /* loop index */
1127 xfs_alloc_key_t key
; /* key value for leaf level upward */
1128 xfs_buf_t
*lbp
; /* buffer for left neighbor block */
1129 xfs_alloc_block_t
*left
; /* left neighbor btree block */
1130 int nrec
; /* new number of left block entries */
1131 xfs_buf_t
*rbp
; /* buffer for right (current) block */
1132 xfs_alloc_block_t
*right
; /* right (current) btree block */
1133 xfs_alloc_key_t
*rkp
=NULL
; /* key pointer for right block */
1134 xfs_alloc_ptr_t
*rpp
=NULL
; /* address pointer for right block */
1135 xfs_alloc_rec_t
*rrp
=NULL
; /* record pointer for right block */
1138 * Set up variables for this block as "right".
1140 rbp
= cur
->bc_bufs
[level
];
1141 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1143 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1147 * If we've got no left sibling then we can't shift an entry left.
1149 if (be32_to_cpu(right
->bb_leftsib
) == NULLAGBLOCK
) {
1154 * If the cursor entry is the one that would be moved, don't
1155 * do it... it's too complicated.
1157 if (cur
->bc_ptrs
[level
] <= 1) {
1162 * Set up the left neighbor as "left".
1164 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1165 cur
->bc_private
.a
.agno
, be32_to_cpu(right
->bb_leftsib
),
1166 0, &lbp
, XFS_ALLOC_BTREE_REF
)))
1168 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1169 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1172 * If it's full, it can't take another entry.
1174 if (be16_to_cpu(left
->bb_numrecs
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1178 nrec
= be16_to_cpu(left
->bb_numrecs
) + 1;
1180 * If non-leaf, copy a key and a ptr to the left block.
1183 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1184 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1186 lkp
= XFS_ALLOC_KEY_ADDR(left
, nrec
, cur
);
1187 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1189 xfs_alloc_log_keys(cur
, lbp
, nrec
, nrec
);
1190 lpp
= XFS_ALLOC_PTR_ADDR(left
, nrec
, cur
);
1191 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1193 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(*rpp
), level
)))
1196 *lpp
= *rpp
; /* INT_: copy */
1197 xfs_alloc_log_ptrs(cur
, lbp
, nrec
, nrec
);
1198 xfs_btree_check_key(cur
->bc_btnum
, lkp
- 1, lkp
);
1201 * If leaf, copy a record to the left block.
1204 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1206 lrp
= XFS_ALLOC_REC_ADDR(left
, nrec
, cur
);
1207 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1209 xfs_alloc_log_recs(cur
, lbp
, nrec
, nrec
);
1210 xfs_btree_check_rec(cur
->bc_btnum
, lrp
- 1, lrp
);
1213 * Bump and log left's numrecs, decrement and log right's numrecs.
1215 be16_add(&left
->bb_numrecs
, 1);
1216 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1217 be16_add(&right
->bb_numrecs
, -1);
1218 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1220 * Slide the contents of right down one entry.
1224 for (i
= 0; i
< be16_to_cpu(right
->bb_numrecs
); i
++) {
1225 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
+ 1]),
1230 memmove(rkp
, rkp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1231 memmove(rpp
, rpp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1232 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1233 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1235 memmove(rrp
, rrp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1236 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1237 key
.ar_startblock
= rrp
->ar_startblock
;
1238 key
.ar_blockcount
= rrp
->ar_blockcount
;
1242 * Update the parent key values of right.
1244 if ((error
= xfs_alloc_updkey(cur
, rkp
, level
+ 1)))
1247 * Slide the cursor value left one.
1249 cur
->bc_ptrs
[level
]--;
1255 * Allocate a new root block, fill it in.
1257 STATIC
int /* error */
1259 xfs_btree_cur_t
*cur
, /* btree cursor */
1260 int *stat
) /* success/failure */
1262 int error
; /* error return value */
1263 xfs_agblock_t lbno
; /* left block number */
1264 xfs_buf_t
*lbp
; /* left btree buffer */
1265 xfs_alloc_block_t
*left
; /* left btree block */
1266 xfs_mount_t
*mp
; /* mount structure */
1267 xfs_agblock_t nbno
; /* new block number */
1268 xfs_buf_t
*nbp
; /* new (root) buffer */
1269 xfs_alloc_block_t
*new; /* new (root) btree block */
1270 int nptr
; /* new value for key index, 1 or 2 */
1271 xfs_agblock_t rbno
; /* right block number */
1272 xfs_buf_t
*rbp
; /* right btree buffer */
1273 xfs_alloc_block_t
*right
; /* right btree block */
1277 ASSERT(cur
->bc_nlevels
< XFS_AG_MAXLEVELS(mp
));
1279 * Get a buffer from the freelist blocks, for the new root.
1281 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1285 * None available, we fail.
1287 if (nbno
== NULLAGBLOCK
) {
1291 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1292 nbp
= xfs_btree_get_bufs(mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
, nbno
,
1294 new = XFS_BUF_TO_ALLOC_BLOCK(nbp
);
1296 * Set the root data in the a.g. freespace structure.
1299 xfs_agf_t
*agf
; /* a.g. freespace header */
1300 xfs_agnumber_t seqno
;
1302 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
1303 agf
->agf_roots
[cur
->bc_btnum
] = cpu_to_be32(nbno
);
1304 be32_add(&agf
->agf_levels
[cur
->bc_btnum
], 1);
1305 seqno
= be32_to_cpu(agf
->agf_seqno
);
1306 mp
->m_perag
[seqno
].pagf_levels
[cur
->bc_btnum
]++;
1307 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1308 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
1311 * At the previous root level there are now two blocks: the old
1312 * root, and the new block generated when it was split.
1313 * We don't know which one the cursor is pointing at, so we
1314 * set up variables "left" and "right" for each case.
1316 lbp
= cur
->bc_bufs
[cur
->bc_nlevels
- 1];
1317 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1319 if ((error
= xfs_btree_check_sblock(cur
, left
, cur
->bc_nlevels
- 1, lbp
)))
1322 if (be32_to_cpu(left
->bb_rightsib
) != NULLAGBLOCK
) {
1324 * Our block is left, pick up the right block.
1326 lbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(lbp
));
1327 rbno
= be32_to_cpu(left
->bb_rightsib
);
1328 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1329 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
1330 XFS_ALLOC_BTREE_REF
)))
1332 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1333 if ((error
= xfs_btree_check_sblock(cur
, right
,
1334 cur
->bc_nlevels
- 1, rbp
)))
1339 * Our block is right, pick up the left block.
1343 rbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(rbp
));
1344 lbno
= be32_to_cpu(right
->bb_leftsib
);
1345 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1346 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
1347 XFS_ALLOC_BTREE_REF
)))
1349 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1350 if ((error
= xfs_btree_check_sblock(cur
, left
,
1351 cur
->bc_nlevels
- 1, lbp
)))
1356 * Fill in the new block's btree header and log it.
1358 new->bb_magic
= cpu_to_be32(xfs_magics
[cur
->bc_btnum
]);
1359 new->bb_level
= cpu_to_be16(cur
->bc_nlevels
);
1360 new->bb_numrecs
= cpu_to_be16(2);
1361 new->bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
1362 new->bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1363 xfs_alloc_log_block(cur
->bc_tp
, nbp
, XFS_BB_ALL_BITS
);
1364 ASSERT(lbno
!= NULLAGBLOCK
&& rbno
!= NULLAGBLOCK
);
1366 * Fill in the key data in the new root.
1369 xfs_alloc_key_t
*kp
; /* btree key pointer */
1371 kp
= XFS_ALLOC_KEY_ADDR(new, 1, cur
);
1372 if (be16_to_cpu(left
->bb_level
) > 0) {
1373 kp
[0] = *XFS_ALLOC_KEY_ADDR(left
, 1, cur
); /* INT_: structure copy */
1374 kp
[1] = *XFS_ALLOC_KEY_ADDR(right
, 1, cur
);/* INT_: structure copy */
1376 xfs_alloc_rec_t
*rp
; /* btree record pointer */
1378 rp
= XFS_ALLOC_REC_ADDR(left
, 1, cur
);
1379 kp
[0].ar_startblock
= rp
->ar_startblock
;
1380 kp
[0].ar_blockcount
= rp
->ar_blockcount
;
1381 rp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1382 kp
[1].ar_startblock
= rp
->ar_startblock
;
1383 kp
[1].ar_blockcount
= rp
->ar_blockcount
;
1386 xfs_alloc_log_keys(cur
, nbp
, 1, 2);
1388 * Fill in the pointer data in the new root.
1391 xfs_alloc_ptr_t
*pp
; /* btree address pointer */
1393 pp
= XFS_ALLOC_PTR_ADDR(new, 1, cur
);
1394 pp
[0] = cpu_to_be32(lbno
);
1395 pp
[1] = cpu_to_be32(rbno
);
1397 xfs_alloc_log_ptrs(cur
, nbp
, 1, 2);
1399 * Fix up the cursor.
1401 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
1402 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
1409 * Move 1 record right from cur/level if possible.
1410 * Update cur to reflect the new path.
1412 STATIC
int /* error */
1414 xfs_btree_cur_t
*cur
, /* btree cursor */
1415 int level
, /* level to shift record on */
1416 int *stat
) /* success/failure */
1418 int error
; /* error return value */
1419 int i
; /* loop index */
1420 xfs_alloc_key_t key
; /* key value for leaf level upward */
1421 xfs_buf_t
*lbp
; /* buffer for left (current) block */
1422 xfs_alloc_block_t
*left
; /* left (current) btree block */
1423 xfs_buf_t
*rbp
; /* buffer for right neighbor block */
1424 xfs_alloc_block_t
*right
; /* right neighbor btree block */
1425 xfs_alloc_key_t
*rkp
; /* key pointer for right block */
1426 xfs_btree_cur_t
*tcur
; /* temporary cursor */
1429 * Set up variables for this block as "left".
1431 lbp
= cur
->bc_bufs
[level
];
1432 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1434 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1438 * If we've got no right sibling then we can't shift an entry right.
1440 if (be32_to_cpu(left
->bb_rightsib
) == NULLAGBLOCK
) {
1445 * If the cursor entry is the one that would be moved, don't
1446 * do it... it's too complicated.
1448 if (cur
->bc_ptrs
[level
] >= be16_to_cpu(left
->bb_numrecs
)) {
1453 * Set up the right neighbor as "right".
1455 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1456 cur
->bc_private
.a
.agno
, be32_to_cpu(left
->bb_rightsib
),
1457 0, &rbp
, XFS_ALLOC_BTREE_REF
)))
1459 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1460 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1463 * If it's full, it can't take another entry.
1465 if (be16_to_cpu(right
->bb_numrecs
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1470 * Make a hole at the start of the right neighbor block, then
1471 * copy the last left block entry to the hole.
1474 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1475 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1476 xfs_alloc_ptr_t
*rpp
; /* address pointer for right block */
1478 lkp
= XFS_ALLOC_KEY_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1479 lpp
= XFS_ALLOC_PTR_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1480 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1481 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1483 for (i
= be16_to_cpu(right
->bb_numrecs
) - 1; i
>= 0; i
--) {
1484 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
]), level
)))
1488 memmove(rkp
+ 1, rkp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1489 memmove(rpp
+ 1, rpp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1491 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(*lpp
), level
)))
1494 *rkp
= *lkp
; /* INT_: copy */
1495 *rpp
= *lpp
; /* INT_: copy */
1496 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1497 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1498 xfs_btree_check_key(cur
->bc_btnum
, rkp
, rkp
+ 1);
1500 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1501 xfs_alloc_rec_t
*rrp
; /* record pointer for right block */
1503 lrp
= XFS_ALLOC_REC_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1504 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1505 memmove(rrp
+ 1, rrp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1507 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1508 key
.ar_startblock
= rrp
->ar_startblock
;
1509 key
.ar_blockcount
= rrp
->ar_blockcount
;
1511 xfs_btree_check_rec(cur
->bc_btnum
, rrp
, rrp
+ 1);
1514 * Decrement and log left's numrecs, bump and log right's numrecs.
1516 be16_add(&left
->bb_numrecs
, -1);
1517 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1518 be16_add(&right
->bb_numrecs
, 1);
1519 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1521 * Using a temporary cursor, update the parent key values of the
1522 * block on the right.
1524 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
1526 i
= xfs_btree_lastrec(tcur
, level
);
1527 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1528 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)) ||
1529 (error
= xfs_alloc_updkey(tcur
, rkp
, level
+ 1)))
1531 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1535 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
1540 * Split cur/level block in half.
1541 * Return new block number and its first record (to be inserted into parent).
1543 STATIC
int /* error */
1545 xfs_btree_cur_t
*cur
, /* btree cursor */
1546 int level
, /* level to split */
1547 xfs_agblock_t
*bnop
, /* output: block number allocated */
1548 xfs_alloc_key_t
*keyp
, /* output: first key of new block */
1549 xfs_btree_cur_t
**curp
, /* output: new cursor */
1550 int *stat
) /* success/failure */
1552 int error
; /* error return value */
1553 int i
; /* loop index/record number */
1554 xfs_agblock_t lbno
; /* left (current) block number */
1555 xfs_buf_t
*lbp
; /* buffer for left block */
1556 xfs_alloc_block_t
*left
; /* left (current) btree block */
1557 xfs_agblock_t rbno
; /* right (new) block number */
1558 xfs_buf_t
*rbp
; /* buffer for right block */
1559 xfs_alloc_block_t
*right
; /* right (new) btree block */
1562 * Allocate the new block from the freelist.
1563 * If we can't do it, we're toast. Give up.
1565 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1568 if (rbno
== NULLAGBLOCK
) {
1572 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1573 rbp
= xfs_btree_get_bufs(cur
->bc_mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
,
1576 * Set up the new block as "right".
1578 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1580 * "Left" is the current (according to the cursor) block.
1582 lbp
= cur
->bc_bufs
[level
];
1583 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1585 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1589 * Fill in the btree header for the new block.
1591 right
->bb_magic
= cpu_to_be32(xfs_magics
[cur
->bc_btnum
]);
1592 right
->bb_level
= left
->bb_level
;
1593 right
->bb_numrecs
= cpu_to_be16(be16_to_cpu(left
->bb_numrecs
) / 2);
1595 * Make sure that if there's an odd number of entries now, that
1596 * each new block will have the same number of entries.
1598 if ((be16_to_cpu(left
->bb_numrecs
) & 1) &&
1599 cur
->bc_ptrs
[level
] <= be16_to_cpu(right
->bb_numrecs
) + 1)
1600 be16_add(&right
->bb_numrecs
, 1);
1601 i
= be16_to_cpu(left
->bb_numrecs
) - be16_to_cpu(right
->bb_numrecs
) + 1;
1603 * For non-leaf blocks, copy keys and addresses over to the new block.
1606 xfs_alloc_key_t
*lkp
; /* left btree key pointer */
1607 xfs_alloc_ptr_t
*lpp
; /* left btree address pointer */
1608 xfs_alloc_key_t
*rkp
; /* right btree key pointer */
1609 xfs_alloc_ptr_t
*rpp
; /* right btree address pointer */
1611 lkp
= XFS_ALLOC_KEY_ADDR(left
, i
, cur
);
1612 lpp
= XFS_ALLOC_PTR_ADDR(left
, i
, cur
);
1613 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1614 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1616 for (i
= 0; i
< be16_to_cpu(right
->bb_numrecs
); i
++) {
1617 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(lpp
[i
]), level
)))
1621 memcpy(rkp
, lkp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1622 memcpy(rpp
, lpp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1623 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1624 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1628 * For leaf blocks, copy records over to the new block.
1631 xfs_alloc_rec_t
*lrp
; /* left btree record pointer */
1632 xfs_alloc_rec_t
*rrp
; /* right btree record pointer */
1634 lrp
= XFS_ALLOC_REC_ADDR(left
, i
, cur
);
1635 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1636 memcpy(rrp
, lrp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1637 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1638 keyp
->ar_startblock
= rrp
->ar_startblock
;
1639 keyp
->ar_blockcount
= rrp
->ar_blockcount
;
1642 * Find the left block number by looking in the buffer.
1643 * Adjust numrecs, sibling pointers.
1645 lbno
= XFS_DADDR_TO_AGBNO(cur
->bc_mp
, XFS_BUF_ADDR(lbp
));
1646 be16_add(&left
->bb_numrecs
, -(be16_to_cpu(right
->bb_numrecs
)));
1647 right
->bb_rightsib
= left
->bb_rightsib
;
1648 left
->bb_rightsib
= cpu_to_be32(rbno
);
1649 right
->bb_leftsib
= cpu_to_be32(lbno
);
1650 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_ALL_BITS
);
1651 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
1653 * If there's a block to the new block's right, make that block
1654 * point back to right instead of to left.
1656 if (be32_to_cpu(right
->bb_rightsib
) != NULLAGBLOCK
) {
1657 xfs_alloc_block_t
*rrblock
; /* rr btree block */
1658 xfs_buf_t
*rrbp
; /* buffer for rrblock */
1660 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1661 cur
->bc_private
.a
.agno
, be32_to_cpu(right
->bb_rightsib
), 0,
1662 &rrbp
, XFS_ALLOC_BTREE_REF
)))
1664 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
1665 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
1667 rrblock
->bb_leftsib
= cpu_to_be32(rbno
);
1668 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
1671 * If the cursor is really in the right block, move it there.
1672 * If it's just pointing past the last entry in left, then we'll
1673 * insert there, so don't change anything in that case.
1675 if (cur
->bc_ptrs
[level
] > be16_to_cpu(left
->bb_numrecs
) + 1) {
1676 xfs_btree_setbuf(cur
, level
, rbp
);
1677 cur
->bc_ptrs
[level
] -= be16_to_cpu(left
->bb_numrecs
);
1680 * If there are more levels, we'll need another cursor which refers to
1681 * the right block, no matter where this cursor was.
1683 if (level
+ 1 < cur
->bc_nlevels
) {
1684 if ((error
= xfs_btree_dup_cursor(cur
, curp
)))
1686 (*curp
)->bc_ptrs
[level
+ 1]++;
1694 * Update keys at all levels from here to the root along the cursor's path.
1696 STATIC
int /* error */
1698 xfs_btree_cur_t
*cur
, /* btree cursor */
1699 xfs_alloc_key_t
*keyp
, /* new key value to update to */
1700 int level
) /* starting level for update */
1702 int ptr
; /* index of key in block */
1705 * Go up the tree from this level toward the root.
1706 * At each level, update the key value to the value input.
1707 * Stop when we reach a level where the cursor isn't pointing
1708 * at the first entry in the block.
1710 for (ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
1711 xfs_alloc_block_t
*block
; /* btree block */
1712 xfs_buf_t
*bp
; /* buffer for block */
1714 int error
; /* error return value */
1716 xfs_alloc_key_t
*kp
; /* ptr to btree block keys */
1718 bp
= cur
->bc_bufs
[level
];
1719 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1721 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1724 ptr
= cur
->bc_ptrs
[level
];
1725 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
1727 xfs_alloc_log_keys(cur
, bp
, ptr
, ptr
);
1733 * Externally visible routines.
1737 * Decrement cursor by one record at the level.
1738 * For nonzero levels the leaf-ward information is untouched.
1741 xfs_alloc_decrement(
1742 xfs_btree_cur_t
*cur
, /* btree cursor */
1743 int level
, /* level in btree, 0 is leaf */
1744 int *stat
) /* success/failure */
1746 xfs_alloc_block_t
*block
; /* btree block */
1747 int error
; /* error return value */
1748 int lev
; /* btree level */
1750 ASSERT(level
< cur
->bc_nlevels
);
1752 * Read-ahead to the left at this level.
1754 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1756 * Decrement the ptr at this level. If we're still in the block
1759 if (--cur
->bc_ptrs
[level
] > 0) {
1764 * Get a pointer to the btree block.
1766 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[level
]);
1768 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
1769 cur
->bc_bufs
[level
])))
1773 * If we just went off the left edge of the tree, return failure.
1775 if (be32_to_cpu(block
->bb_leftsib
) == NULLAGBLOCK
) {
1780 * March up the tree decrementing pointers.
1781 * Stop when we don't go off the left edge of a block.
1783 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1784 if (--cur
->bc_ptrs
[lev
] > 0)
1787 * Read-ahead the left block, we're going to read it
1790 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1793 * If we went off the root then we are seriously confused.
1795 ASSERT(lev
< cur
->bc_nlevels
);
1797 * Now walk back down the tree, fixing up the cursor's buffer
1798 * pointers and key numbers.
1800 for (block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[lev
]); lev
> level
; ) {
1801 xfs_agblock_t agbno
; /* block number of btree block */
1802 xfs_buf_t
*bp
; /* buffer pointer for block */
1804 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
));
1805 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1806 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1807 XFS_ALLOC_BTREE_REF
)))
1810 xfs_btree_setbuf(cur
, lev
, bp
);
1811 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1812 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1814 cur
->bc_ptrs
[lev
] = be16_to_cpu(block
->bb_numrecs
);
1821 * Delete the record pointed to by cur.
1822 * The cursor refers to the place where the record was (could be inserted)
1823 * when the operation returns.
1827 xfs_btree_cur_t
*cur
, /* btree cursor */
1828 int *stat
) /* success/failure */
1830 int error
; /* error return value */
1831 int i
; /* result code */
1832 int level
; /* btree level */
1835 * Go up the tree, starting at leaf level.
1836 * If 2 is returned then a join was done; go to the next level.
1837 * Otherwise we are done.
1839 for (level
= 0, i
= 2; i
== 2; level
++) {
1840 if ((error
= xfs_alloc_delrec(cur
, level
, &i
)))
1844 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
1845 if (cur
->bc_ptrs
[level
] == 0) {
1846 if ((error
= xfs_alloc_decrement(cur
, level
, &i
)))
1857 * Get the data from the pointed-to record.
1861 xfs_btree_cur_t
*cur
, /* btree cursor */
1862 xfs_agblock_t
*bno
, /* output: starting block of extent */
1863 xfs_extlen_t
*len
, /* output: length of extent */
1864 int *stat
) /* output: success/failure */
1866 xfs_alloc_block_t
*block
; /* btree block */
1868 int error
; /* error return value */
1870 int ptr
; /* record number */
1872 ptr
= cur
->bc_ptrs
[0];
1873 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
1875 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
1879 * Off the right end or left end, return failure.
1881 if (ptr
> be16_to_cpu(block
->bb_numrecs
) || ptr
<= 0) {
1886 * Point to the record and extract its data.
1889 xfs_alloc_rec_t
*rec
; /* record data */
1891 rec
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
1892 *bno
= be32_to_cpu(rec
->ar_startblock
);
1893 *len
= be32_to_cpu(rec
->ar_blockcount
);
1900 * Increment cursor by one record at the level.
1901 * For nonzero levels the leaf-ward information is untouched.
1904 xfs_alloc_increment(
1905 xfs_btree_cur_t
*cur
, /* btree cursor */
1906 int level
, /* level in btree, 0 is leaf */
1907 int *stat
) /* success/failure */
1909 xfs_alloc_block_t
*block
; /* btree block */
1910 xfs_buf_t
*bp
; /* tree block buffer */
1911 int error
; /* error return value */
1912 int lev
; /* btree level */
1914 ASSERT(level
< cur
->bc_nlevels
);
1916 * Read-ahead to the right at this level.
1918 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1920 * Get a pointer to the btree block.
1922 bp
= cur
->bc_bufs
[level
];
1923 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1925 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1929 * Increment the ptr at this level. If we're still in the block
1932 if (++cur
->bc_ptrs
[level
] <= be16_to_cpu(block
->bb_numrecs
)) {
1937 * If we just went off the right edge of the tree, return failure.
1939 if (be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
) {
1944 * March up the tree incrementing pointers.
1945 * Stop when we don't go off the right edge of a block.
1947 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1948 bp
= cur
->bc_bufs
[lev
];
1949 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1951 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1954 if (++cur
->bc_ptrs
[lev
] <= be16_to_cpu(block
->bb_numrecs
))
1957 * Read-ahead the right block, we're going to read it
1960 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1963 * If we went off the root then we are seriously confused.
1965 ASSERT(lev
< cur
->bc_nlevels
);
1967 * Now walk back down the tree, fixing up the cursor's buffer
1968 * pointers and key numbers.
1970 for (bp
= cur
->bc_bufs
[lev
], block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1972 xfs_agblock_t agbno
; /* block number of btree block */
1974 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
));
1975 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1976 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1977 XFS_ALLOC_BTREE_REF
)))
1980 xfs_btree_setbuf(cur
, lev
, bp
);
1981 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1982 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1984 cur
->bc_ptrs
[lev
] = 1;
1991 * Insert the current record at the point referenced by cur.
1992 * The cursor may be inconsistent on return if splits have been done.
1996 xfs_btree_cur_t
*cur
, /* btree cursor */
1997 int *stat
) /* success/failure */
1999 int error
; /* error return value */
2000 int i
; /* result value, 0 for failure */
2001 int level
; /* current level number in btree */
2002 xfs_agblock_t nbno
; /* new block number (split result) */
2003 xfs_btree_cur_t
*ncur
; /* new cursor (split result) */
2004 xfs_alloc_rec_t nrec
; /* record being inserted this level */
2005 xfs_btree_cur_t
*pcur
; /* previous level's cursor */
2009 nrec
.ar_startblock
= cpu_to_be32(cur
->bc_rec
.a
.ar_startblock
);
2010 nrec
.ar_blockcount
= cpu_to_be32(cur
->bc_rec
.a
.ar_blockcount
);
2011 ncur
= (xfs_btree_cur_t
*)0;
2014 * Loop going up the tree, starting at the leaf level.
2015 * Stop when we don't get a split block, that must mean that
2016 * the insert is finished with this level.
2020 * Insert nrec/nbno into this level of the tree.
2021 * Note if we fail, nbno will be null.
2023 if ((error
= xfs_alloc_insrec(pcur
, level
++, &nbno
, &nrec
, &ncur
,
2026 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
2030 * See if the cursor we just used is trash.
2031 * Can't trash the caller's cursor, but otherwise we should
2032 * if ncur is a new cursor or we're about to be done.
2034 if (pcur
!= cur
&& (ncur
|| nbno
== NULLAGBLOCK
)) {
2035 cur
->bc_nlevels
= pcur
->bc_nlevels
;
2036 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
2039 * If we got a new cursor, switch to it.
2043 ncur
= (xfs_btree_cur_t
*)0;
2045 } while (nbno
!= NULLAGBLOCK
);
2051 * Lookup the record equal to [bno, len] in the btree given by cur.
2054 xfs_alloc_lookup_eq(
2055 xfs_btree_cur_t
*cur
, /* btree cursor */
2056 xfs_agblock_t bno
, /* starting block of extent */
2057 xfs_extlen_t len
, /* length of extent */
2058 int *stat
) /* success/failure */
2060 cur
->bc_rec
.a
.ar_startblock
= bno
;
2061 cur
->bc_rec
.a
.ar_blockcount
= len
;
2062 return xfs_alloc_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
2066 * Lookup the first record greater than or equal to [bno, len]
2067 * in the btree given by cur.
2070 xfs_alloc_lookup_ge(
2071 xfs_btree_cur_t
*cur
, /* btree cursor */
2072 xfs_agblock_t bno
, /* starting block of extent */
2073 xfs_extlen_t len
, /* length of extent */
2074 int *stat
) /* success/failure */
2076 cur
->bc_rec
.a
.ar_startblock
= bno
;
2077 cur
->bc_rec
.a
.ar_blockcount
= len
;
2078 return xfs_alloc_lookup(cur
, XFS_LOOKUP_GE
, stat
);
2082 * Lookup the first record less than or equal to [bno, len]
2083 * in the btree given by cur.
2086 xfs_alloc_lookup_le(
2087 xfs_btree_cur_t
*cur
, /* btree cursor */
2088 xfs_agblock_t bno
, /* starting block of extent */
2089 xfs_extlen_t len
, /* length of extent */
2090 int *stat
) /* success/failure */
2092 cur
->bc_rec
.a
.ar_startblock
= bno
;
2093 cur
->bc_rec
.a
.ar_blockcount
= len
;
2094 return xfs_alloc_lookup(cur
, XFS_LOOKUP_LE
, stat
);
2098 * Update the record referred to by cur, to the value given by [bno, len].
2099 * This either works (return 0) or gets an EFSCORRUPTED error.
2103 xfs_btree_cur_t
*cur
, /* btree cursor */
2104 xfs_agblock_t bno
, /* starting block of extent */
2105 xfs_extlen_t len
) /* length of extent */
2107 xfs_alloc_block_t
*block
; /* btree block to update */
2108 int error
; /* error return value */
2109 int ptr
; /* current record number (updating) */
2113 * Pick up the a.g. freelist struct and the current block.
2115 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
2117 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
2121 * Get the address of the rec to be updated.
2123 ptr
= cur
->bc_ptrs
[0];
2125 xfs_alloc_rec_t
*rp
; /* pointer to updated record */
2127 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
2129 * Fill in the new contents and log them.
2131 rp
->ar_startblock
= cpu_to_be32(bno
);
2132 rp
->ar_blockcount
= cpu_to_be32(len
);
2133 xfs_alloc_log_recs(cur
, cur
->bc_bufs
[0], ptr
, ptr
);
2136 * If it's the by-size btree and it's the last leaf block and
2137 * it's the last record... then update the size of the longest
2138 * extent in the a.g., which we cache in the a.g. freelist header.
2140 if (cur
->bc_btnum
== XFS_BTNUM_CNT
&&
2141 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
2142 ptr
== be16_to_cpu(block
->bb_numrecs
)) {
2143 xfs_agf_t
*agf
; /* a.g. freespace header */
2144 xfs_agnumber_t seqno
;
2146 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
2147 seqno
= be32_to_cpu(agf
->agf_seqno
);
2148 cur
->bc_mp
->m_perag
[seqno
].pagf_longest
= len
;
2149 agf
->agf_longest
= cpu_to_be32(len
);
2150 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
2154 * Updating first record in leaf. Pass new key value up to our parent.
2157 xfs_alloc_key_t key
; /* key containing [bno, len] */
2159 key
.ar_startblock
= cpu_to_be32(bno
);
2160 key
.ar_blockcount
= cpu_to_be32(len
);
2161 if ((error
= xfs_alloc_updkey(cur
, &key
, 1)))