]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - fs/xfs/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 #include "xfs_types.h"
24 #include "xfs_trans.h"
28 #include "xfs_dmapi.h"
29 #include "xfs_mount.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_ialloc_btree.h"
33 #include "xfs_dir2_sf.h"
34 #include "xfs_attr_sf.h"
35 #include "xfs_dinode.h"
36 #include "xfs_inode.h"
37 #include "xfs_btree.h"
38 #include "xfs_ialloc.h"
39 #include "xfs_alloc.h"
40 #include "xfs_error.h"
43 * Prototypes for internal functions.
46 STATIC
void xfs_alloc_log_block(xfs_trans_t
*, xfs_buf_t
*, int);
47 STATIC
void xfs_alloc_log_keys(xfs_btree_cur_t
*, xfs_buf_t
*, int, int);
48 STATIC
void xfs_alloc_log_ptrs(xfs_btree_cur_t
*, xfs_buf_t
*, int, int);
49 STATIC
void xfs_alloc_log_recs(xfs_btree_cur_t
*, xfs_buf_t
*, int, int);
50 STATIC
int xfs_alloc_lshift(xfs_btree_cur_t
*, int, int *);
51 STATIC
int xfs_alloc_newroot(xfs_btree_cur_t
*, int *);
52 STATIC
int xfs_alloc_rshift(xfs_btree_cur_t
*, int, int *);
53 STATIC
int xfs_alloc_split(xfs_btree_cur_t
*, int, xfs_agblock_t
*,
54 xfs_alloc_key_t
*, xfs_btree_cur_t
**, int *);
55 STATIC
int xfs_alloc_updkey(xfs_btree_cur_t
*, xfs_alloc_key_t
*, int);
62 * Single level of the xfs_alloc_delete record deletion routine.
63 * Delete record pointed to by cur/level.
64 * Remove the record from its block then rebalance the tree.
65 * Return 0 for error, 1 for done, 2 to go on to the next level.
67 STATIC
int /* error */
69 xfs_btree_cur_t
*cur
, /* btree cursor */
70 int level
, /* level removing record from */
71 int *stat
) /* fail/done/go-on */
73 xfs_agf_t
*agf
; /* allocation group freelist header */
74 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
75 xfs_agblock_t bno
; /* btree block number */
76 xfs_buf_t
*bp
; /* buffer for block */
77 int error
; /* error return value */
78 int i
; /* loop index */
79 xfs_alloc_key_t key
; /* kp points here if block is level 0 */
80 xfs_agblock_t lbno
; /* left block's block number */
81 xfs_buf_t
*lbp
; /* left block's buffer pointer */
82 xfs_alloc_block_t
*left
; /* left btree block */
83 xfs_alloc_key_t
*lkp
=NULL
; /* left block key pointer */
84 xfs_alloc_ptr_t
*lpp
=NULL
; /* left block address pointer */
85 int lrecs
=0; /* number of records in left block */
86 xfs_alloc_rec_t
*lrp
; /* left block record pointer */
87 xfs_mount_t
*mp
; /* mount structure */
88 int ptr
; /* index in btree block for this rec */
89 xfs_agblock_t rbno
; /* right block's block number */
90 xfs_buf_t
*rbp
; /* right block's buffer pointer */
91 xfs_alloc_block_t
*right
; /* right btree block */
92 xfs_alloc_key_t
*rkp
; /* right block key pointer */
93 xfs_alloc_ptr_t
*rpp
; /* right block address pointer */
94 int rrecs
=0; /* number of records in right block */
96 xfs_alloc_rec_t
*rrp
; /* right block record pointer */
97 xfs_btree_cur_t
*tcur
; /* temporary btree cursor */
100 * Get the index of the entry being deleted, check for nothing there.
102 ptr
= cur
->bc_ptrs
[level
];
108 * Get the buffer & block containing the record or key/ptr.
110 bp
= cur
->bc_bufs
[level
];
111 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
113 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
117 * Fail if we're off the end of the block.
119 numrecs
= be16_to_cpu(block
->bb_numrecs
);
124 XFS_STATS_INC(xs_abt_delrec
);
126 * It's a nonleaf. Excise the key and ptr being deleted, by
127 * sliding the entries past them down one.
128 * Log the changed areas of the block.
131 lkp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
132 lpp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
134 for (i
= ptr
; i
< numrecs
; i
++) {
135 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(lpp
[i
]), level
)))
140 memmove(&lkp
[ptr
- 1], &lkp
[ptr
],
141 (numrecs
- ptr
) * sizeof(*lkp
));
142 memmove(&lpp
[ptr
- 1], &lpp
[ptr
],
143 (numrecs
- ptr
) * sizeof(*lpp
));
144 xfs_alloc_log_ptrs(cur
, bp
, ptr
, numrecs
- 1);
145 xfs_alloc_log_keys(cur
, bp
, ptr
, numrecs
- 1);
149 * It's a leaf. Excise the record being deleted, by sliding the
150 * entries past it down one. Log the changed areas of the block.
153 lrp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
155 memmove(&lrp
[ptr
- 1], &lrp
[ptr
],
156 (numrecs
- ptr
) * sizeof(*lrp
));
157 xfs_alloc_log_recs(cur
, bp
, ptr
, numrecs
- 1);
160 * If it's the first record in the block, we'll need a key
161 * structure to pass up to the next level (updkey).
164 key
.ar_startblock
= lrp
->ar_startblock
;
165 key
.ar_blockcount
= lrp
->ar_blockcount
;
170 * Decrement and log the number of entries in the block.
173 block
->bb_numrecs
= cpu_to_be16(numrecs
);
174 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
176 * See if the longest free extent in the allocation group was
177 * changed by this operation. True if it's the by-size btree, and
178 * this is the leaf level, and there is no right sibling block,
179 * and this was the last record.
181 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
185 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
186 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
188 ASSERT(ptr
== numrecs
+ 1);
190 * There are still records in the block. Grab the size
194 rrp
= XFS_ALLOC_REC_ADDR(block
, numrecs
, cur
);
195 agf
->agf_longest
= rrp
->ar_blockcount
;
198 * No free extents left.
201 agf
->agf_longest
= 0;
202 mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_longest
=
203 be32_to_cpu(agf
->agf_longest
);
204 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
208 * Is this the root level? If so, we're almost done.
210 if (level
== cur
->bc_nlevels
- 1) {
212 * If this is the root level,
213 * and there's only one entry left,
214 * and it's NOT the leaf level,
215 * then we can get rid of this level.
217 if (numrecs
== 1 && level
> 0) {
219 * lpp is still set to the first pointer in the block.
220 * Make it the new root of the btree.
222 bno
= be32_to_cpu(agf
->agf_roots
[cur
->bc_btnum
]);
223 agf
->agf_roots
[cur
->bc_btnum
] = *lpp
;
224 be32_add(&agf
->agf_levels
[cur
->bc_btnum
], -1);
225 mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_levels
[cur
->bc_btnum
]--;
227 * Put this buffer/block on the ag's freelist.
229 if ((error
= xfs_alloc_put_freelist(cur
->bc_tp
,
230 cur
->bc_private
.a
.agbp
, NULL
, bno
)))
233 * Since blocks move to the free list without the
234 * coordination used in xfs_bmap_finish, we can't allow
235 * block to be available for reallocation and
236 * non-transaction writing (user data) until we know
237 * that the transaction that moved it to the free list
238 * is permanently on disk. We track the blocks by
239 * declaring these blocks as "busy"; the busy list is
240 * maintained on a per-ag basis and each transaction
241 * records which entries should be removed when the
242 * iclog commits to disk. If a busy block is
243 * allocated, the iclog is pushed up to the LSN
244 * that freed the block.
246 xfs_alloc_mark_busy(cur
->bc_tp
,
247 be32_to_cpu(agf
->agf_seqno
), bno
, 1);
249 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
250 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
251 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
253 * Update the cursor so there's one fewer level.
255 xfs_btree_setbuf(cur
, level
, NULL
);
257 } else if (level
> 0 &&
258 (error
= xfs_alloc_decrement(cur
, level
, &i
)))
264 * If we deleted the leftmost entry in the block, update the
265 * key values above us in the tree.
267 if (ptr
== 1 && (error
= xfs_alloc_updkey(cur
, lkp
, level
+ 1)))
270 * If the number of records remaining in the block is at least
271 * the minimum, we're done.
273 if (numrecs
>= XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
274 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
280 * Otherwise, we have to move some records around to keep the
281 * tree balanced. Look at the left and right sibling blocks to
282 * see if we can re-balance by moving only one record.
284 rbno
= be32_to_cpu(block
->bb_rightsib
);
285 lbno
= be32_to_cpu(block
->bb_leftsib
);
287 ASSERT(rbno
!= NULLAGBLOCK
|| lbno
!= NULLAGBLOCK
);
289 * Duplicate the cursor so our btree manipulations here won't
290 * disrupt the next level up.
292 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
295 * If there's a right sibling, see if it's ok to shift an entry
298 if (rbno
!= NULLAGBLOCK
) {
300 * Move the temp cursor to the last entry in the next block.
301 * Actually any entry but the first would suffice.
303 i
= xfs_btree_lastrec(tcur
, level
);
304 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
305 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)))
307 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
308 i
= xfs_btree_lastrec(tcur
, level
);
309 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
311 * Grab a pointer to the block.
313 rbp
= tcur
->bc_bufs
[level
];
314 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
316 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
320 * Grab the current block number, for future use.
322 bno
= be32_to_cpu(right
->bb_leftsib
);
324 * If right block is full enough so that removing one entry
325 * won't make it too empty, and left-shifting an entry out
326 * of right to us works, we're done.
328 if (be16_to_cpu(right
->bb_numrecs
) - 1 >=
329 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
330 if ((error
= xfs_alloc_lshift(tcur
, level
, &i
)))
333 ASSERT(be16_to_cpu(block
->bb_numrecs
) >=
334 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
335 xfs_btree_del_cursor(tcur
,
338 (error
= xfs_alloc_decrement(cur
, level
,
346 * Otherwise, grab the number of records in right for
347 * future reference, and fix up the temp cursor to point
348 * to our block again (last record).
350 rrecs
= be16_to_cpu(right
->bb_numrecs
);
351 if (lbno
!= NULLAGBLOCK
) {
352 i
= xfs_btree_firstrec(tcur
, level
);
353 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
354 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
356 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
360 * If there's a left sibling, see if it's ok to shift an entry
363 if (lbno
!= NULLAGBLOCK
) {
365 * Move the temp cursor to the first entry in the
368 i
= xfs_btree_firstrec(tcur
, level
);
369 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
370 if ((error
= xfs_alloc_decrement(tcur
, level
, &i
)))
372 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
373 xfs_btree_firstrec(tcur
, level
);
375 * Grab a pointer to the block.
377 lbp
= tcur
->bc_bufs
[level
];
378 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
380 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
384 * Grab the current block number, for future use.
386 bno
= be32_to_cpu(left
->bb_rightsib
);
388 * If left block is full enough so that removing one entry
389 * won't make it too empty, and right-shifting an entry out
390 * of left to us works, we're done.
392 if (be16_to_cpu(left
->bb_numrecs
) - 1 >=
393 XFS_ALLOC_BLOCK_MINRECS(level
, cur
)) {
394 if ((error
= xfs_alloc_rshift(tcur
, level
, &i
)))
397 ASSERT(be16_to_cpu(block
->bb_numrecs
) >=
398 XFS_ALLOC_BLOCK_MINRECS(level
, cur
));
399 xfs_btree_del_cursor(tcur
,
408 * Otherwise, grab the number of records in right for
411 lrecs
= be16_to_cpu(left
->bb_numrecs
);
414 * Delete the temp cursor, we're done with it.
416 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
418 * If here, we need to do a join to keep the tree balanced.
420 ASSERT(bno
!= NULLAGBLOCK
);
422 * See if we can join with the left neighbor block.
424 if (lbno
!= NULLAGBLOCK
&&
425 lrecs
+ numrecs
<= XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
427 * Set "right" to be the starting block,
428 * "left" to be the left neighbor.
432 rrecs
= be16_to_cpu(right
->bb_numrecs
);
434 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
435 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
436 XFS_ALLOC_BTREE_REF
)))
438 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
439 lrecs
= be16_to_cpu(left
->bb_numrecs
);
440 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
444 * If that won't work, see if we can join with the right neighbor block.
446 else if (rbno
!= NULLAGBLOCK
&&
447 rrecs
+ numrecs
<= XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
449 * Set "left" to be the starting block,
450 * "right" to be the right neighbor.
454 lrecs
= be16_to_cpu(left
->bb_numrecs
);
456 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
457 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
458 XFS_ALLOC_BTREE_REF
)))
460 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
461 rrecs
= be16_to_cpu(right
->bb_numrecs
);
462 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
466 * Otherwise, we can't fix the imbalance.
467 * Just return. This is probably a logic error, but it's not fatal.
470 if (level
> 0 && (error
= xfs_alloc_decrement(cur
, level
, &i
)))
476 * We're now going to join "left" and "right" by moving all the stuff
477 * in "right" to "left" and deleting "right".
481 * It's a non-leaf. Move keys and pointers.
483 lkp
= XFS_ALLOC_KEY_ADDR(left
, lrecs
+ 1, cur
);
484 lpp
= XFS_ALLOC_PTR_ADDR(left
, lrecs
+ 1, cur
);
485 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
486 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
488 for (i
= 0; i
< rrecs
; i
++) {
489 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
]), level
)))
493 memcpy(lkp
, rkp
, rrecs
* sizeof(*lkp
));
494 memcpy(lpp
, rpp
, rrecs
* sizeof(*lpp
));
495 xfs_alloc_log_keys(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
496 xfs_alloc_log_ptrs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
499 * It's a leaf. Move records.
501 lrp
= XFS_ALLOC_REC_ADDR(left
, lrecs
+ 1, cur
);
502 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
503 memcpy(lrp
, rrp
, rrecs
* sizeof(*lrp
));
504 xfs_alloc_log_recs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
507 * If we joined with the left neighbor, set the buffer in the
508 * cursor to the left block, and fix up the index.
511 xfs_btree_setbuf(cur
, level
, lbp
);
512 cur
->bc_ptrs
[level
] += lrecs
;
515 * If we joined with the right neighbor and there's a level above
516 * us, increment the cursor at that level.
518 else if (level
+ 1 < cur
->bc_nlevels
&&
519 (error
= xfs_alloc_increment(cur
, level
+ 1, &i
)))
522 * Fix up the number of records in the surviving block.
525 left
->bb_numrecs
= cpu_to_be16(lrecs
);
527 * Fix up the right block pointer in the surviving block, and log it.
529 left
->bb_rightsib
= right
->bb_rightsib
;
530 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
532 * If there is a right sibling now, make it point to the
535 if (be32_to_cpu(left
->bb_rightsib
) != NULLAGBLOCK
) {
536 xfs_alloc_block_t
*rrblock
;
539 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
540 cur
->bc_private
.a
.agno
, be32_to_cpu(left
->bb_rightsib
), 0,
541 &rrbp
, XFS_ALLOC_BTREE_REF
)))
543 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
544 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
546 rrblock
->bb_leftsib
= cpu_to_be32(lbno
);
547 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
550 * Free the deleting block by putting it on the freelist.
552 if ((error
= xfs_alloc_put_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
556 * Since blocks move to the free list without the coordination
557 * used in xfs_bmap_finish, we can't allow block to be available
558 * for reallocation and non-transaction writing (user data)
559 * until we know that the transaction that moved it to the free
560 * list is permanently on disk. We track the blocks by declaring
561 * these blocks as "busy"; the busy list is maintained on a
562 * per-ag basis and each transaction records which entries
563 * should be removed when the iclog commits to disk. If a
564 * busy block is allocated, the iclog is pushed up to the
565 * LSN that freed the block.
567 xfs_alloc_mark_busy(cur
->bc_tp
, be32_to_cpu(agf
->agf_seqno
), bno
, 1);
568 xfs_trans_agbtree_delta(cur
->bc_tp
, -1);
571 * Adjust the current level's cursor so that we're left referring
572 * to the right node, after we're done.
573 * If this leaves the ptr value 0 our caller will fix it up.
576 cur
->bc_ptrs
[level
]--;
578 * Return value means the next level up has something to do.
584 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
589 * Insert one record/level. Return information to the caller
590 * allowing the next level up to proceed if necessary.
592 STATIC
int /* error */
594 xfs_btree_cur_t
*cur
, /* btree cursor */
595 int level
, /* level to insert record at */
596 xfs_agblock_t
*bnop
, /* i/o: block number inserted */
597 xfs_alloc_rec_t
*recp
, /* i/o: record data inserted */
598 xfs_btree_cur_t
**curp
, /* output: new cursor replacing cur */
599 int *stat
) /* output: success/failure */
601 xfs_agf_t
*agf
; /* allocation group freelist header */
602 xfs_alloc_block_t
*block
; /* btree block record/key lives in */
603 xfs_buf_t
*bp
; /* buffer for block */
604 int error
; /* error return value */
605 int i
; /* loop index */
606 xfs_alloc_key_t key
; /* key value being inserted */
607 xfs_alloc_key_t
*kp
; /* pointer to btree keys */
608 xfs_agblock_t nbno
; /* block number of allocated block */
609 xfs_btree_cur_t
*ncur
; /* new cursor to be used at next lvl */
610 xfs_alloc_key_t nkey
; /* new key value, from split */
611 xfs_alloc_rec_t nrec
; /* new record value, for caller */
613 int optr
; /* old ptr value */
614 xfs_alloc_ptr_t
*pp
; /* pointer to btree addresses */
615 int ptr
; /* index in btree block for this rec */
616 xfs_alloc_rec_t
*rp
; /* pointer to btree records */
618 ASSERT(be32_to_cpu(recp
->ar_blockcount
) > 0);
621 * GCC doesn't understand the (arguably complex) control flow in
622 * this function and complains about uninitialized structure fields
625 memset(&nrec
, 0, sizeof(nrec
));
628 * If we made it to the root level, allocate a new root block
631 if (level
>= cur
->bc_nlevels
) {
632 XFS_STATS_INC(xs_abt_insrec
);
633 if ((error
= xfs_alloc_newroot(cur
, &i
)))
640 * Make a key out of the record data to be inserted, and save it.
642 key
.ar_startblock
= recp
->ar_startblock
;
643 key
.ar_blockcount
= recp
->ar_blockcount
;
644 optr
= ptr
= cur
->bc_ptrs
[level
];
646 * If we're off the left edge, return failure.
652 XFS_STATS_INC(xs_abt_insrec
);
654 * Get pointers to the btree buffer and block.
656 bp
= cur
->bc_bufs
[level
];
657 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
658 numrecs
= be16_to_cpu(block
->bb_numrecs
);
660 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
663 * Check that the new entry is being inserted in the right place.
665 if (ptr
<= numrecs
) {
667 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
668 xfs_btree_check_rec(cur
->bc_btnum
, recp
, rp
);
670 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
671 xfs_btree_check_key(cur
->bc_btnum
, &key
, kp
);
678 * If the block is full, we can't insert the new entry until we
679 * make the block un-full.
681 if (numrecs
== XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
683 * First, try shifting an entry to the right neighbor.
685 if ((error
= xfs_alloc_rshift(cur
, level
, &i
)))
691 * Next, try shifting an entry to the left neighbor.
694 if ((error
= xfs_alloc_lshift(cur
, level
, &i
)))
697 optr
= ptr
= cur
->bc_ptrs
[level
];
700 * Next, try splitting the current block in
701 * half. If this works we have to re-set our
702 * variables because we could be in a
703 * different block now.
705 if ((error
= xfs_alloc_split(cur
, level
, &nbno
,
709 bp
= cur
->bc_bufs
[level
];
710 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
713 xfs_btree_check_sblock(cur
,
717 ptr
= cur
->bc_ptrs
[level
];
718 nrec
.ar_startblock
= nkey
.ar_startblock
;
719 nrec
.ar_blockcount
= nkey
.ar_blockcount
;
722 * Otherwise the insert fails.
732 * At this point we know there's room for our new entry in the block
735 numrecs
= be16_to_cpu(block
->bb_numrecs
);
738 * It's a non-leaf entry. Make a hole for the new data
739 * in the key and ptr regions of the block.
741 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
742 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
744 for (i
= numrecs
; i
>= ptr
; i
--) {
745 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(pp
[i
- 1]), level
)))
749 memmove(&kp
[ptr
], &kp
[ptr
- 1],
750 (numrecs
- ptr
+ 1) * sizeof(*kp
));
751 memmove(&pp
[ptr
], &pp
[ptr
- 1],
752 (numrecs
- ptr
+ 1) * sizeof(*pp
));
754 if ((error
= xfs_btree_check_sptr(cur
, *bnop
, level
)))
758 * Now stuff the new data in, bump numrecs and log the new data.
761 pp
[ptr
- 1] = cpu_to_be32(*bnop
);
763 block
->bb_numrecs
= cpu_to_be16(numrecs
);
764 xfs_alloc_log_keys(cur
, bp
, ptr
, numrecs
);
765 xfs_alloc_log_ptrs(cur
, bp
, ptr
, numrecs
);
768 xfs_btree_check_key(cur
->bc_btnum
, kp
+ ptr
- 1,
773 * It's a leaf entry. Make a hole for the new record.
775 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
776 memmove(&rp
[ptr
], &rp
[ptr
- 1],
777 (numrecs
- ptr
+ 1) * sizeof(*rp
));
779 * Now stuff the new record in, bump numrecs
780 * and log the new data.
784 block
->bb_numrecs
= cpu_to_be16(numrecs
);
785 xfs_alloc_log_recs(cur
, bp
, ptr
, numrecs
);
788 xfs_btree_check_rec(cur
->bc_btnum
, rp
+ ptr
- 1,
793 * Log the new number of records in the btree header.
795 xfs_alloc_log_block(cur
->bc_tp
, bp
, XFS_BB_NUMRECS
);
797 * If we inserted at the start of a block, update the parents' keys.
799 if (optr
== 1 && (error
= xfs_alloc_updkey(cur
, &key
, level
+ 1)))
802 * Look to see if the longest extent in the allocation group
803 * needs to be updated.
806 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
808 cur
->bc_btnum
== XFS_BTNUM_CNT
&&
809 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
810 be32_to_cpu(recp
->ar_blockcount
) > be32_to_cpu(agf
->agf_longest
)) {
812 * If this is a leaf in the by-size btree and there
813 * is no right sibling block and this block is bigger
814 * than the previous longest block, update it.
816 agf
->agf_longest
= recp
->ar_blockcount
;
817 cur
->bc_mp
->m_perag
[be32_to_cpu(agf
->agf_seqno
)].pagf_longest
818 = be32_to_cpu(recp
->ar_blockcount
);
819 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
823 * Return the new block number, if any.
824 * If there is one, give back a record value and a cursor too.
827 if (nbno
!= NULLAGBLOCK
) {
836 * Log header fields from a btree block.
840 xfs_trans_t
*tp
, /* transaction pointer */
841 xfs_buf_t
*bp
, /* buffer containing btree block */
842 int fields
) /* mask of fields: XFS_BB_... */
844 int first
; /* first byte offset logged */
845 int last
; /* last byte offset logged */
846 static const short offsets
[] = { /* table of offsets */
847 offsetof(xfs_alloc_block_t
, bb_magic
),
848 offsetof(xfs_alloc_block_t
, bb_level
),
849 offsetof(xfs_alloc_block_t
, bb_numrecs
),
850 offsetof(xfs_alloc_block_t
, bb_leftsib
),
851 offsetof(xfs_alloc_block_t
, bb_rightsib
),
852 sizeof(xfs_alloc_block_t
)
855 xfs_btree_offsets(fields
, offsets
, XFS_BB_NUM_BITS
, &first
, &last
);
856 xfs_trans_log_buf(tp
, bp
, first
, last
);
860 * Log keys from a btree block (nonleaf).
864 xfs_btree_cur_t
*cur
, /* btree cursor */
865 xfs_buf_t
*bp
, /* buffer containing btree block */
866 int kfirst
, /* index of first key to log */
867 int klast
) /* index of last key to log */
869 xfs_alloc_block_t
*block
; /* btree block to log from */
870 int first
; /* first byte offset logged */
871 xfs_alloc_key_t
*kp
; /* key pointer in btree block */
872 int last
; /* last byte offset logged */
874 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
875 kp
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
876 first
= (int)((xfs_caddr_t
)&kp
[kfirst
- 1] - (xfs_caddr_t
)block
);
877 last
= (int)(((xfs_caddr_t
)&kp
[klast
] - 1) - (xfs_caddr_t
)block
);
878 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
882 * Log block pointer fields from a btree block (nonleaf).
886 xfs_btree_cur_t
*cur
, /* btree cursor */
887 xfs_buf_t
*bp
, /* buffer containing btree block */
888 int pfirst
, /* index of first pointer to log */
889 int plast
) /* index of last pointer to log */
891 xfs_alloc_block_t
*block
; /* btree block to log from */
892 int first
; /* first byte offset logged */
893 int last
; /* last byte offset logged */
894 xfs_alloc_ptr_t
*pp
; /* block-pointer pointer in btree blk */
896 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
897 pp
= XFS_ALLOC_PTR_ADDR(block
, 1, cur
);
898 first
= (int)((xfs_caddr_t
)&pp
[pfirst
- 1] - (xfs_caddr_t
)block
);
899 last
= (int)(((xfs_caddr_t
)&pp
[plast
] - 1) - (xfs_caddr_t
)block
);
900 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
904 * Log records from a btree block (leaf).
908 xfs_btree_cur_t
*cur
, /* btree cursor */
909 xfs_buf_t
*bp
, /* buffer containing btree block */
910 int rfirst
, /* index of first record to log */
911 int rlast
) /* index of last record to log */
913 xfs_alloc_block_t
*block
; /* btree block to log from */
914 int first
; /* first byte offset logged */
915 int last
; /* last byte offset logged */
916 xfs_alloc_rec_t
*rp
; /* record pointer for btree block */
919 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
920 rp
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
926 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
927 for (p
= &rp
[rfirst
- 1]; p
<= &rp
[rlast
- 1]; p
++)
928 ASSERT(be32_to_cpu(p
->ar_startblock
) +
929 be32_to_cpu(p
->ar_blockcount
) <=
930 be32_to_cpu(agf
->agf_length
));
933 first
= (int)((xfs_caddr_t
)&rp
[rfirst
- 1] - (xfs_caddr_t
)block
);
934 last
= (int)(((xfs_caddr_t
)&rp
[rlast
] - 1) - (xfs_caddr_t
)block
);
935 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
939 * Lookup the record. The cursor is made to point to it, based on dir.
940 * Return 0 if can't find any such record, 1 for success.
942 STATIC
int /* error */
944 xfs_btree_cur_t
*cur
, /* btree cursor */
945 xfs_lookup_t dir
, /* <=, ==, or >= */
946 int *stat
) /* success/failure */
948 xfs_agblock_t agbno
; /* a.g. relative btree block number */
949 xfs_agnumber_t agno
; /* allocation group number */
950 xfs_alloc_block_t
*block
=NULL
; /* current btree block */
951 int diff
; /* difference for the current key */
952 int error
; /* error return value */
953 int keyno
=0; /* current key number */
954 int level
; /* level in the btree */
955 xfs_mount_t
*mp
; /* file system mount point */
957 XFS_STATS_INC(xs_abt_lookup
);
959 * Get the allocation group header, and the root block number.
964 xfs_agf_t
*agf
; /* a.g. freespace header */
966 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
967 agno
= be32_to_cpu(agf
->agf_seqno
);
968 agbno
= be32_to_cpu(agf
->agf_roots
[cur
->bc_btnum
]);
971 * Iterate over each level in the btree, starting at the root.
972 * For each level above the leaves, find the key we need, based
973 * on the lookup record, then follow the corresponding block
974 * pointer down to the next level.
976 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
977 xfs_buf_t
*bp
; /* buffer pointer for btree block */
978 xfs_daddr_t d
; /* disk address of btree block */
981 * Get the disk address we're looking for.
983 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
985 * If the old buffer at this level is for a different block,
986 * throw it away, otherwise just use it.
988 bp
= cur
->bc_bufs
[level
];
989 if (bp
&& XFS_BUF_ADDR(bp
) != d
)
993 * Need to get a new buffer. Read it, then
994 * set it in the cursor, releasing the old one.
996 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
, agno
,
997 agbno
, 0, &bp
, XFS_ALLOC_BTREE_REF
)))
999 xfs_btree_setbuf(cur
, level
, bp
);
1001 * Point to the btree block, now that we have the buffer
1003 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1004 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
1008 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1010 * If we already had a key match at a higher level, we know
1011 * we need to use the first entry in this block.
1016 * Otherwise we need to search this block. Do a binary search.
1019 int high
; /* high entry number */
1020 xfs_alloc_key_t
*kkbase
=NULL
;/* base of keys in block */
1021 xfs_alloc_rec_t
*krbase
=NULL
;/* base of records in block */
1022 int low
; /* low entry number */
1025 * Get a pointer to keys or records.
1028 kkbase
= XFS_ALLOC_KEY_ADDR(block
, 1, cur
);
1030 krbase
= XFS_ALLOC_REC_ADDR(block
, 1, cur
);
1032 * Set low and high entry numbers, 1-based.
1035 if (!(high
= be16_to_cpu(block
->bb_numrecs
))) {
1037 * If the block is empty, the tree must
1040 ASSERT(level
== 0 && cur
->bc_nlevels
== 1);
1041 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
1046 * Binary search the block.
1048 while (low
<= high
) {
1049 xfs_extlen_t blockcount
; /* key value */
1050 xfs_agblock_t startblock
; /* key value */
1052 XFS_STATS_INC(xs_abt_compare
);
1054 * keyno is average of low and high.
1056 keyno
= (low
+ high
) >> 1;
1058 * Get startblock & blockcount.
1061 xfs_alloc_key_t
*kkp
;
1063 kkp
= kkbase
+ keyno
- 1;
1064 startblock
= be32_to_cpu(kkp
->ar_startblock
);
1065 blockcount
= be32_to_cpu(kkp
->ar_blockcount
);
1067 xfs_alloc_rec_t
*krp
;
1069 krp
= krbase
+ keyno
- 1;
1070 startblock
= be32_to_cpu(krp
->ar_startblock
);
1071 blockcount
= be32_to_cpu(krp
->ar_blockcount
);
1074 * Compute difference to get next direction.
1076 if (cur
->bc_btnum
== XFS_BTNUM_BNO
)
1077 diff
= (int)startblock
-
1078 (int)cur
->bc_rec
.a
.ar_startblock
;
1079 else if (!(diff
= (int)blockcount
-
1080 (int)cur
->bc_rec
.a
.ar_blockcount
))
1081 diff
= (int)startblock
-
1082 (int)cur
->bc_rec
.a
.ar_startblock
;
1084 * Less than, move right.
1089 * Greater than, move left.
1094 * Equal, we're done.
1101 * If there are more levels, set up for the next level
1102 * by getting the block number and filling in the cursor.
1106 * If we moved left, need the previous key number,
1107 * unless there isn't one.
1109 if (diff
> 0 && --keyno
< 1)
1111 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, keyno
, cur
));
1113 if ((error
= xfs_btree_check_sptr(cur
, agbno
, level
)))
1116 cur
->bc_ptrs
[level
] = keyno
;
1120 * Done with the search.
1121 * See if we need to adjust the results.
1123 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1126 * If ge search and we went off the end of the block, but it's
1127 * not the last block, we're in the wrong block.
1129 if (dir
== XFS_LOOKUP_GE
&&
1130 keyno
> be16_to_cpu(block
->bb_numrecs
) &&
1131 be32_to_cpu(block
->bb_rightsib
) != NULLAGBLOCK
) {
1134 cur
->bc_ptrs
[0] = keyno
;
1135 if ((error
= xfs_alloc_increment(cur
, 0, &i
)))
1137 XFS_WANT_CORRUPTED_RETURN(i
== 1);
1142 else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
1144 cur
->bc_ptrs
[0] = keyno
;
1146 * Return if we succeeded or not.
1148 if (keyno
== 0 || keyno
> be16_to_cpu(block
->bb_numrecs
))
1151 *stat
= ((dir
!= XFS_LOOKUP_EQ
) || (diff
== 0));
1156 * Move 1 record left from cur/level if possible.
1157 * Update cur to reflect the new path.
1159 STATIC
int /* error */
1161 xfs_btree_cur_t
*cur
, /* btree cursor */
1162 int level
, /* level to shift record on */
1163 int *stat
) /* success/failure */
1165 int error
; /* error return value */
1167 int i
; /* loop index */
1169 xfs_alloc_key_t key
; /* key value for leaf level upward */
1170 xfs_buf_t
*lbp
; /* buffer for left neighbor block */
1171 xfs_alloc_block_t
*left
; /* left neighbor btree block */
1172 int nrec
; /* new number of left block entries */
1173 xfs_buf_t
*rbp
; /* buffer for right (current) block */
1174 xfs_alloc_block_t
*right
; /* right (current) btree block */
1175 xfs_alloc_key_t
*rkp
=NULL
; /* key pointer for right block */
1176 xfs_alloc_ptr_t
*rpp
=NULL
; /* address pointer for right block */
1177 xfs_alloc_rec_t
*rrp
=NULL
; /* record pointer for right block */
1180 * Set up variables for this block as "right".
1182 rbp
= cur
->bc_bufs
[level
];
1183 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1185 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1189 * If we've got no left sibling then we can't shift an entry left.
1191 if (be32_to_cpu(right
->bb_leftsib
) == NULLAGBLOCK
) {
1196 * If the cursor entry is the one that would be moved, don't
1197 * do it... it's too complicated.
1199 if (cur
->bc_ptrs
[level
] <= 1) {
1204 * Set up the left neighbor as "left".
1206 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1207 cur
->bc_private
.a
.agno
, be32_to_cpu(right
->bb_leftsib
),
1208 0, &lbp
, XFS_ALLOC_BTREE_REF
)))
1210 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1211 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1214 * If it's full, it can't take another entry.
1216 if (be16_to_cpu(left
->bb_numrecs
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1220 nrec
= be16_to_cpu(left
->bb_numrecs
) + 1;
1222 * If non-leaf, copy a key and a ptr to the left block.
1225 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1226 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1228 lkp
= XFS_ALLOC_KEY_ADDR(left
, nrec
, cur
);
1229 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1231 xfs_alloc_log_keys(cur
, lbp
, nrec
, nrec
);
1232 lpp
= XFS_ALLOC_PTR_ADDR(left
, nrec
, cur
);
1233 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1235 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(*rpp
), level
)))
1239 xfs_alloc_log_ptrs(cur
, lbp
, nrec
, nrec
);
1240 xfs_btree_check_key(cur
->bc_btnum
, lkp
- 1, lkp
);
1243 * If leaf, copy a record to the left block.
1246 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1248 lrp
= XFS_ALLOC_REC_ADDR(left
, nrec
, cur
);
1249 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1251 xfs_alloc_log_recs(cur
, lbp
, nrec
, nrec
);
1252 xfs_btree_check_rec(cur
->bc_btnum
, lrp
- 1, lrp
);
1255 * Bump and log left's numrecs, decrement and log right's numrecs.
1257 be16_add(&left
->bb_numrecs
, 1);
1258 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1259 be16_add(&right
->bb_numrecs
, -1);
1260 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1262 * Slide the contents of right down one entry.
1266 for (i
= 0; i
< be16_to_cpu(right
->bb_numrecs
); i
++) {
1267 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
+ 1]),
1272 memmove(rkp
, rkp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1273 memmove(rpp
, rpp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1274 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1275 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1277 memmove(rrp
, rrp
+ 1, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1278 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1279 key
.ar_startblock
= rrp
->ar_startblock
;
1280 key
.ar_blockcount
= rrp
->ar_blockcount
;
1284 * Update the parent key values of right.
1286 if ((error
= xfs_alloc_updkey(cur
, rkp
, level
+ 1)))
1289 * Slide the cursor value left one.
1291 cur
->bc_ptrs
[level
]--;
1297 * Allocate a new root block, fill it in.
1299 STATIC
int /* error */
1301 xfs_btree_cur_t
*cur
, /* btree cursor */
1302 int *stat
) /* success/failure */
1304 int error
; /* error return value */
1305 xfs_agblock_t lbno
; /* left block number */
1306 xfs_buf_t
*lbp
; /* left btree buffer */
1307 xfs_alloc_block_t
*left
; /* left btree block */
1308 xfs_mount_t
*mp
; /* mount structure */
1309 xfs_agblock_t nbno
; /* new block number */
1310 xfs_buf_t
*nbp
; /* new (root) buffer */
1311 xfs_alloc_block_t
*new; /* new (root) btree block */
1312 int nptr
; /* new value for key index, 1 or 2 */
1313 xfs_agblock_t rbno
; /* right block number */
1314 xfs_buf_t
*rbp
; /* right btree buffer */
1315 xfs_alloc_block_t
*right
; /* right btree block */
1319 ASSERT(cur
->bc_nlevels
< XFS_AG_MAXLEVELS(mp
));
1321 * Get a buffer from the freelist blocks, for the new root.
1323 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1327 * None available, we fail.
1329 if (nbno
== NULLAGBLOCK
) {
1333 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1334 nbp
= xfs_btree_get_bufs(mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
, nbno
,
1336 new = XFS_BUF_TO_ALLOC_BLOCK(nbp
);
1338 * Set the root data in the a.g. freespace structure.
1341 xfs_agf_t
*agf
; /* a.g. freespace header */
1342 xfs_agnumber_t seqno
;
1344 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
1345 agf
->agf_roots
[cur
->bc_btnum
] = cpu_to_be32(nbno
);
1346 be32_add(&agf
->agf_levels
[cur
->bc_btnum
], 1);
1347 seqno
= be32_to_cpu(agf
->agf_seqno
);
1348 mp
->m_perag
[seqno
].pagf_levels
[cur
->bc_btnum
]++;
1349 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1350 XFS_AGF_ROOTS
| XFS_AGF_LEVELS
);
1353 * At the previous root level there are now two blocks: the old
1354 * root, and the new block generated when it was split.
1355 * We don't know which one the cursor is pointing at, so we
1356 * set up variables "left" and "right" for each case.
1358 lbp
= cur
->bc_bufs
[cur
->bc_nlevels
- 1];
1359 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1361 if ((error
= xfs_btree_check_sblock(cur
, left
, cur
->bc_nlevels
- 1, lbp
)))
1364 if (be32_to_cpu(left
->bb_rightsib
) != NULLAGBLOCK
) {
1366 * Our block is left, pick up the right block.
1368 lbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(lbp
));
1369 rbno
= be32_to_cpu(left
->bb_rightsib
);
1370 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1371 cur
->bc_private
.a
.agno
, rbno
, 0, &rbp
,
1372 XFS_ALLOC_BTREE_REF
)))
1374 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1375 if ((error
= xfs_btree_check_sblock(cur
, right
,
1376 cur
->bc_nlevels
- 1, rbp
)))
1381 * Our block is right, pick up the left block.
1385 rbno
= XFS_DADDR_TO_AGBNO(mp
, XFS_BUF_ADDR(rbp
));
1386 lbno
= be32_to_cpu(right
->bb_leftsib
);
1387 if ((error
= xfs_btree_read_bufs(mp
, cur
->bc_tp
,
1388 cur
->bc_private
.a
.agno
, lbno
, 0, &lbp
,
1389 XFS_ALLOC_BTREE_REF
)))
1391 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1392 if ((error
= xfs_btree_check_sblock(cur
, left
,
1393 cur
->bc_nlevels
- 1, lbp
)))
1398 * Fill in the new block's btree header and log it.
1400 new->bb_magic
= cpu_to_be32(xfs_magics
[cur
->bc_btnum
]);
1401 new->bb_level
= cpu_to_be16(cur
->bc_nlevels
);
1402 new->bb_numrecs
= cpu_to_be16(2);
1403 new->bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
1404 new->bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1405 xfs_alloc_log_block(cur
->bc_tp
, nbp
, XFS_BB_ALL_BITS
);
1406 ASSERT(lbno
!= NULLAGBLOCK
&& rbno
!= NULLAGBLOCK
);
1408 * Fill in the key data in the new root.
1411 xfs_alloc_key_t
*kp
; /* btree key pointer */
1413 kp
= XFS_ALLOC_KEY_ADDR(new, 1, cur
);
1414 if (be16_to_cpu(left
->bb_level
) > 0) {
1415 kp
[0] = *XFS_ALLOC_KEY_ADDR(left
, 1, cur
);
1416 kp
[1] = *XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1418 xfs_alloc_rec_t
*rp
; /* btree record pointer */
1420 rp
= XFS_ALLOC_REC_ADDR(left
, 1, cur
);
1421 kp
[0].ar_startblock
= rp
->ar_startblock
;
1422 kp
[0].ar_blockcount
= rp
->ar_blockcount
;
1423 rp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1424 kp
[1].ar_startblock
= rp
->ar_startblock
;
1425 kp
[1].ar_blockcount
= rp
->ar_blockcount
;
1428 xfs_alloc_log_keys(cur
, nbp
, 1, 2);
1430 * Fill in the pointer data in the new root.
1433 xfs_alloc_ptr_t
*pp
; /* btree address pointer */
1435 pp
= XFS_ALLOC_PTR_ADDR(new, 1, cur
);
1436 pp
[0] = cpu_to_be32(lbno
);
1437 pp
[1] = cpu_to_be32(rbno
);
1439 xfs_alloc_log_ptrs(cur
, nbp
, 1, 2);
1441 * Fix up the cursor.
1443 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
1444 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
1451 * Move 1 record right from cur/level if possible.
1452 * Update cur to reflect the new path.
1454 STATIC
int /* error */
1456 xfs_btree_cur_t
*cur
, /* btree cursor */
1457 int level
, /* level to shift record on */
1458 int *stat
) /* success/failure */
1460 int error
; /* error return value */
1461 int i
; /* loop index */
1462 xfs_alloc_key_t key
; /* key value for leaf level upward */
1463 xfs_buf_t
*lbp
; /* buffer for left (current) block */
1464 xfs_alloc_block_t
*left
; /* left (current) btree block */
1465 xfs_buf_t
*rbp
; /* buffer for right neighbor block */
1466 xfs_alloc_block_t
*right
; /* right neighbor btree block */
1467 xfs_alloc_key_t
*rkp
; /* key pointer for right block */
1468 xfs_btree_cur_t
*tcur
; /* temporary cursor */
1471 * Set up variables for this block as "left".
1473 lbp
= cur
->bc_bufs
[level
];
1474 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1476 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1480 * If we've got no right sibling then we can't shift an entry right.
1482 if (be32_to_cpu(left
->bb_rightsib
) == NULLAGBLOCK
) {
1487 * If the cursor entry is the one that would be moved, don't
1488 * do it... it's too complicated.
1490 if (cur
->bc_ptrs
[level
] >= be16_to_cpu(left
->bb_numrecs
)) {
1495 * Set up the right neighbor as "right".
1497 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1498 cur
->bc_private
.a
.agno
, be32_to_cpu(left
->bb_rightsib
),
1499 0, &rbp
, XFS_ALLOC_BTREE_REF
)))
1501 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1502 if ((error
= xfs_btree_check_sblock(cur
, right
, level
, rbp
)))
1505 * If it's full, it can't take another entry.
1507 if (be16_to_cpu(right
->bb_numrecs
) == XFS_ALLOC_BLOCK_MAXRECS(level
, cur
)) {
1512 * Make a hole at the start of the right neighbor block, then
1513 * copy the last left block entry to the hole.
1516 xfs_alloc_key_t
*lkp
; /* key pointer for left block */
1517 xfs_alloc_ptr_t
*lpp
; /* address pointer for left block */
1518 xfs_alloc_ptr_t
*rpp
; /* address pointer for right block */
1520 lkp
= XFS_ALLOC_KEY_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1521 lpp
= XFS_ALLOC_PTR_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1522 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1523 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1525 for (i
= be16_to_cpu(right
->bb_numrecs
) - 1; i
>= 0; i
--) {
1526 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(rpp
[i
]), level
)))
1530 memmove(rkp
+ 1, rkp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1531 memmove(rpp
+ 1, rpp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1533 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(*lpp
), level
)))
1538 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1539 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1540 xfs_btree_check_key(cur
->bc_btnum
, rkp
, rkp
+ 1);
1542 xfs_alloc_rec_t
*lrp
; /* record pointer for left block */
1543 xfs_alloc_rec_t
*rrp
; /* record pointer for right block */
1545 lrp
= XFS_ALLOC_REC_ADDR(left
, be16_to_cpu(left
->bb_numrecs
), cur
);
1546 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1547 memmove(rrp
+ 1, rrp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1549 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
) + 1);
1550 key
.ar_startblock
= rrp
->ar_startblock
;
1551 key
.ar_blockcount
= rrp
->ar_blockcount
;
1553 xfs_btree_check_rec(cur
->bc_btnum
, rrp
, rrp
+ 1);
1556 * Decrement and log left's numrecs, bump and log right's numrecs.
1558 be16_add(&left
->bb_numrecs
, -1);
1559 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
);
1560 be16_add(&right
->bb_numrecs
, 1);
1561 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_NUMRECS
);
1563 * Using a temporary cursor, update the parent key values of the
1564 * block on the right.
1566 if ((error
= xfs_btree_dup_cursor(cur
, &tcur
)))
1568 i
= xfs_btree_lastrec(tcur
, level
);
1569 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1570 if ((error
= xfs_alloc_increment(tcur
, level
, &i
)) ||
1571 (error
= xfs_alloc_updkey(tcur
, rkp
, level
+ 1)))
1573 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1577 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
1582 * Split cur/level block in half.
1583 * Return new block number and its first record (to be inserted into parent).
1585 STATIC
int /* error */
1587 xfs_btree_cur_t
*cur
, /* btree cursor */
1588 int level
, /* level to split */
1589 xfs_agblock_t
*bnop
, /* output: block number allocated */
1590 xfs_alloc_key_t
*keyp
, /* output: first key of new block */
1591 xfs_btree_cur_t
**curp
, /* output: new cursor */
1592 int *stat
) /* success/failure */
1594 int error
; /* error return value */
1595 int i
; /* loop index/record number */
1596 xfs_agblock_t lbno
; /* left (current) block number */
1597 xfs_buf_t
*lbp
; /* buffer for left block */
1598 xfs_alloc_block_t
*left
; /* left (current) btree block */
1599 xfs_agblock_t rbno
; /* right (new) block number */
1600 xfs_buf_t
*rbp
; /* buffer for right block */
1601 xfs_alloc_block_t
*right
; /* right (new) btree block */
1604 * Allocate the new block from the freelist.
1605 * If we can't do it, we're toast. Give up.
1607 if ((error
= xfs_alloc_get_freelist(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
1610 if (rbno
== NULLAGBLOCK
) {
1614 xfs_trans_agbtree_delta(cur
->bc_tp
, 1);
1615 rbp
= xfs_btree_get_bufs(cur
->bc_mp
, cur
->bc_tp
, cur
->bc_private
.a
.agno
,
1618 * Set up the new block as "right".
1620 right
= XFS_BUF_TO_ALLOC_BLOCK(rbp
);
1622 * "Left" is the current (according to the cursor) block.
1624 lbp
= cur
->bc_bufs
[level
];
1625 left
= XFS_BUF_TO_ALLOC_BLOCK(lbp
);
1627 if ((error
= xfs_btree_check_sblock(cur
, left
, level
, lbp
)))
1631 * Fill in the btree header for the new block.
1633 right
->bb_magic
= cpu_to_be32(xfs_magics
[cur
->bc_btnum
]);
1634 right
->bb_level
= left
->bb_level
;
1635 right
->bb_numrecs
= cpu_to_be16(be16_to_cpu(left
->bb_numrecs
) / 2);
1637 * Make sure that if there's an odd number of entries now, that
1638 * each new block will have the same number of entries.
1640 if ((be16_to_cpu(left
->bb_numrecs
) & 1) &&
1641 cur
->bc_ptrs
[level
] <= be16_to_cpu(right
->bb_numrecs
) + 1)
1642 be16_add(&right
->bb_numrecs
, 1);
1643 i
= be16_to_cpu(left
->bb_numrecs
) - be16_to_cpu(right
->bb_numrecs
) + 1;
1645 * For non-leaf blocks, copy keys and addresses over to the new block.
1648 xfs_alloc_key_t
*lkp
; /* left btree key pointer */
1649 xfs_alloc_ptr_t
*lpp
; /* left btree address pointer */
1650 xfs_alloc_key_t
*rkp
; /* right btree key pointer */
1651 xfs_alloc_ptr_t
*rpp
; /* right btree address pointer */
1653 lkp
= XFS_ALLOC_KEY_ADDR(left
, i
, cur
);
1654 lpp
= XFS_ALLOC_PTR_ADDR(left
, i
, cur
);
1655 rkp
= XFS_ALLOC_KEY_ADDR(right
, 1, cur
);
1656 rpp
= XFS_ALLOC_PTR_ADDR(right
, 1, cur
);
1658 for (i
= 0; i
< be16_to_cpu(right
->bb_numrecs
); i
++) {
1659 if ((error
= xfs_btree_check_sptr(cur
, be32_to_cpu(lpp
[i
]), level
)))
1663 memcpy(rkp
, lkp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rkp
));
1664 memcpy(rpp
, lpp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rpp
));
1665 xfs_alloc_log_keys(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1666 xfs_alloc_log_ptrs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1670 * For leaf blocks, copy records over to the new block.
1673 xfs_alloc_rec_t
*lrp
; /* left btree record pointer */
1674 xfs_alloc_rec_t
*rrp
; /* right btree record pointer */
1676 lrp
= XFS_ALLOC_REC_ADDR(left
, i
, cur
);
1677 rrp
= XFS_ALLOC_REC_ADDR(right
, 1, cur
);
1678 memcpy(rrp
, lrp
, be16_to_cpu(right
->bb_numrecs
) * sizeof(*rrp
));
1679 xfs_alloc_log_recs(cur
, rbp
, 1, be16_to_cpu(right
->bb_numrecs
));
1680 keyp
->ar_startblock
= rrp
->ar_startblock
;
1681 keyp
->ar_blockcount
= rrp
->ar_blockcount
;
1684 * Find the left block number by looking in the buffer.
1685 * Adjust numrecs, sibling pointers.
1687 lbno
= XFS_DADDR_TO_AGBNO(cur
->bc_mp
, XFS_BUF_ADDR(lbp
));
1688 be16_add(&left
->bb_numrecs
, -(be16_to_cpu(right
->bb_numrecs
)));
1689 right
->bb_rightsib
= left
->bb_rightsib
;
1690 left
->bb_rightsib
= cpu_to_be32(rbno
);
1691 right
->bb_leftsib
= cpu_to_be32(lbno
);
1692 xfs_alloc_log_block(cur
->bc_tp
, rbp
, XFS_BB_ALL_BITS
);
1693 xfs_alloc_log_block(cur
->bc_tp
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
1695 * If there's a block to the new block's right, make that block
1696 * point back to right instead of to left.
1698 if (be32_to_cpu(right
->bb_rightsib
) != NULLAGBLOCK
) {
1699 xfs_alloc_block_t
*rrblock
; /* rr btree block */
1700 xfs_buf_t
*rrbp
; /* buffer for rrblock */
1702 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1703 cur
->bc_private
.a
.agno
, be32_to_cpu(right
->bb_rightsib
), 0,
1704 &rrbp
, XFS_ALLOC_BTREE_REF
)))
1706 rrblock
= XFS_BUF_TO_ALLOC_BLOCK(rrbp
);
1707 if ((error
= xfs_btree_check_sblock(cur
, rrblock
, level
, rrbp
)))
1709 rrblock
->bb_leftsib
= cpu_to_be32(rbno
);
1710 xfs_alloc_log_block(cur
->bc_tp
, rrbp
, XFS_BB_LEFTSIB
);
1713 * If the cursor is really in the right block, move it there.
1714 * If it's just pointing past the last entry in left, then we'll
1715 * insert there, so don't change anything in that case.
1717 if (cur
->bc_ptrs
[level
] > be16_to_cpu(left
->bb_numrecs
) + 1) {
1718 xfs_btree_setbuf(cur
, level
, rbp
);
1719 cur
->bc_ptrs
[level
] -= be16_to_cpu(left
->bb_numrecs
);
1722 * If there are more levels, we'll need another cursor which refers to
1723 * the right block, no matter where this cursor was.
1725 if (level
+ 1 < cur
->bc_nlevels
) {
1726 if ((error
= xfs_btree_dup_cursor(cur
, curp
)))
1728 (*curp
)->bc_ptrs
[level
+ 1]++;
1736 * Update keys at all levels from here to the root along the cursor's path.
1738 STATIC
int /* error */
1740 xfs_btree_cur_t
*cur
, /* btree cursor */
1741 xfs_alloc_key_t
*keyp
, /* new key value to update to */
1742 int level
) /* starting level for update */
1744 int ptr
; /* index of key in block */
1747 * Go up the tree from this level toward the root.
1748 * At each level, update the key value to the value input.
1749 * Stop when we reach a level where the cursor isn't pointing
1750 * at the first entry in the block.
1752 for (ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
1753 xfs_alloc_block_t
*block
; /* btree block */
1754 xfs_buf_t
*bp
; /* buffer for block */
1756 int error
; /* error return value */
1758 xfs_alloc_key_t
*kp
; /* ptr to btree block keys */
1760 bp
= cur
->bc_bufs
[level
];
1761 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1763 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1766 ptr
= cur
->bc_ptrs
[level
];
1767 kp
= XFS_ALLOC_KEY_ADDR(block
, ptr
, cur
);
1769 xfs_alloc_log_keys(cur
, bp
, ptr
, ptr
);
1775 * Externally visible routines.
1779 * Decrement cursor by one record at the level.
1780 * For nonzero levels the leaf-ward information is untouched.
1783 xfs_alloc_decrement(
1784 xfs_btree_cur_t
*cur
, /* btree cursor */
1785 int level
, /* level in btree, 0 is leaf */
1786 int *stat
) /* success/failure */
1788 xfs_alloc_block_t
*block
; /* btree block */
1789 int error
; /* error return value */
1790 int lev
; /* btree level */
1792 ASSERT(level
< cur
->bc_nlevels
);
1794 * Read-ahead to the left at this level.
1796 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1798 * Decrement the ptr at this level. If we're still in the block
1801 if (--cur
->bc_ptrs
[level
] > 0) {
1806 * Get a pointer to the btree block.
1808 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[level
]);
1810 if ((error
= xfs_btree_check_sblock(cur
, block
, level
,
1811 cur
->bc_bufs
[level
])))
1815 * If we just went off the left edge of the tree, return failure.
1817 if (be32_to_cpu(block
->bb_leftsib
) == NULLAGBLOCK
) {
1822 * March up the tree decrementing pointers.
1823 * Stop when we don't go off the left edge of a block.
1825 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1826 if (--cur
->bc_ptrs
[lev
] > 0)
1829 * Read-ahead the left block, we're going to read it
1832 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1835 * If we went off the root then we are seriously confused.
1837 ASSERT(lev
< cur
->bc_nlevels
);
1839 * Now walk back down the tree, fixing up the cursor's buffer
1840 * pointers and key numbers.
1842 for (block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[lev
]); lev
> level
; ) {
1843 xfs_agblock_t agbno
; /* block number of btree block */
1844 xfs_buf_t
*bp
; /* buffer pointer for block */
1846 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
));
1847 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
1848 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
1849 XFS_ALLOC_BTREE_REF
)))
1852 xfs_btree_setbuf(cur
, lev
, bp
);
1853 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1854 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1856 cur
->bc_ptrs
[lev
] = be16_to_cpu(block
->bb_numrecs
);
1863 * Delete the record pointed to by cur.
1864 * The cursor refers to the place where the record was (could be inserted)
1865 * when the operation returns.
1869 xfs_btree_cur_t
*cur
, /* btree cursor */
1870 int *stat
) /* success/failure */
1872 int error
; /* error return value */
1873 int i
; /* result code */
1874 int level
; /* btree level */
1877 * Go up the tree, starting at leaf level.
1878 * If 2 is returned then a join was done; go to the next level.
1879 * Otherwise we are done.
1881 for (level
= 0, i
= 2; i
== 2; level
++) {
1882 if ((error
= xfs_alloc_delrec(cur
, level
, &i
)))
1886 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
1887 if (cur
->bc_ptrs
[level
] == 0) {
1888 if ((error
= xfs_alloc_decrement(cur
, level
, &i
)))
1899 * Get the data from the pointed-to record.
1903 xfs_btree_cur_t
*cur
, /* btree cursor */
1904 xfs_agblock_t
*bno
, /* output: starting block of extent */
1905 xfs_extlen_t
*len
, /* output: length of extent */
1906 int *stat
) /* output: success/failure */
1908 xfs_alloc_block_t
*block
; /* btree block */
1910 int error
; /* error return value */
1912 int ptr
; /* record number */
1914 ptr
= cur
->bc_ptrs
[0];
1915 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
1917 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
1921 * Off the right end or left end, return failure.
1923 if (ptr
> be16_to_cpu(block
->bb_numrecs
) || ptr
<= 0) {
1928 * Point to the record and extract its data.
1931 xfs_alloc_rec_t
*rec
; /* record data */
1933 rec
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
1934 *bno
= be32_to_cpu(rec
->ar_startblock
);
1935 *len
= be32_to_cpu(rec
->ar_blockcount
);
1942 * Increment cursor by one record at the level.
1943 * For nonzero levels the leaf-ward information is untouched.
1946 xfs_alloc_increment(
1947 xfs_btree_cur_t
*cur
, /* btree cursor */
1948 int level
, /* level in btree, 0 is leaf */
1949 int *stat
) /* success/failure */
1951 xfs_alloc_block_t
*block
; /* btree block */
1952 xfs_buf_t
*bp
; /* tree block buffer */
1953 int error
; /* error return value */
1954 int lev
; /* btree level */
1956 ASSERT(level
< cur
->bc_nlevels
);
1958 * Read-ahead to the right at this level.
1960 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1962 * Get a pointer to the btree block.
1964 bp
= cur
->bc_bufs
[level
];
1965 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1967 if ((error
= xfs_btree_check_sblock(cur
, block
, level
, bp
)))
1971 * Increment the ptr at this level. If we're still in the block
1974 if (++cur
->bc_ptrs
[level
] <= be16_to_cpu(block
->bb_numrecs
)) {
1979 * If we just went off the right edge of the tree, return failure.
1981 if (be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
) {
1986 * March up the tree incrementing pointers.
1987 * Stop when we don't go off the right edge of a block.
1989 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1990 bp
= cur
->bc_bufs
[lev
];
1991 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
1993 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
1996 if (++cur
->bc_ptrs
[lev
] <= be16_to_cpu(block
->bb_numrecs
))
1999 * Read-ahead the right block, we're going to read it
2002 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
2005 * If we went off the root then we are seriously confused.
2007 ASSERT(lev
< cur
->bc_nlevels
);
2009 * Now walk back down the tree, fixing up the cursor's buffer
2010 * pointers and key numbers.
2012 for (bp
= cur
->bc_bufs
[lev
], block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
2014 xfs_agblock_t agbno
; /* block number of btree block */
2016 agbno
= be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block
, cur
->bc_ptrs
[lev
], cur
));
2017 if ((error
= xfs_btree_read_bufs(cur
->bc_mp
, cur
->bc_tp
,
2018 cur
->bc_private
.a
.agno
, agbno
, 0, &bp
,
2019 XFS_ALLOC_BTREE_REF
)))
2022 xfs_btree_setbuf(cur
, lev
, bp
);
2023 block
= XFS_BUF_TO_ALLOC_BLOCK(bp
);
2024 if ((error
= xfs_btree_check_sblock(cur
, block
, lev
, bp
)))
2026 cur
->bc_ptrs
[lev
] = 1;
2033 * Insert the current record at the point referenced by cur.
2034 * The cursor may be inconsistent on return if splits have been done.
2038 xfs_btree_cur_t
*cur
, /* btree cursor */
2039 int *stat
) /* success/failure */
2041 int error
; /* error return value */
2042 int i
; /* result value, 0 for failure */
2043 int level
; /* current level number in btree */
2044 xfs_agblock_t nbno
; /* new block number (split result) */
2045 xfs_btree_cur_t
*ncur
; /* new cursor (split result) */
2046 xfs_alloc_rec_t nrec
; /* record being inserted this level */
2047 xfs_btree_cur_t
*pcur
; /* previous level's cursor */
2051 nrec
.ar_startblock
= cpu_to_be32(cur
->bc_rec
.a
.ar_startblock
);
2052 nrec
.ar_blockcount
= cpu_to_be32(cur
->bc_rec
.a
.ar_blockcount
);
2056 * Loop going up the tree, starting at the leaf level.
2057 * Stop when we don't get a split block, that must mean that
2058 * the insert is finished with this level.
2062 * Insert nrec/nbno into this level of the tree.
2063 * Note if we fail, nbno will be null.
2065 if ((error
= xfs_alloc_insrec(pcur
, level
++, &nbno
, &nrec
, &ncur
,
2068 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
2072 * See if the cursor we just used is trash.
2073 * Can't trash the caller's cursor, but otherwise we should
2074 * if ncur is a new cursor or we're about to be done.
2076 if (pcur
!= cur
&& (ncur
|| nbno
== NULLAGBLOCK
)) {
2077 cur
->bc_nlevels
= pcur
->bc_nlevels
;
2078 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
2081 * If we got a new cursor, switch to it.
2087 } while (nbno
!= NULLAGBLOCK
);
2093 * Lookup the record equal to [bno, len] in the btree given by cur.
2096 xfs_alloc_lookup_eq(
2097 xfs_btree_cur_t
*cur
, /* btree cursor */
2098 xfs_agblock_t bno
, /* starting block of extent */
2099 xfs_extlen_t len
, /* length of extent */
2100 int *stat
) /* success/failure */
2102 cur
->bc_rec
.a
.ar_startblock
= bno
;
2103 cur
->bc_rec
.a
.ar_blockcount
= len
;
2104 return xfs_alloc_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
2108 * Lookup the first record greater than or equal to [bno, len]
2109 * in the btree given by cur.
2112 xfs_alloc_lookup_ge(
2113 xfs_btree_cur_t
*cur
, /* btree cursor */
2114 xfs_agblock_t bno
, /* starting block of extent */
2115 xfs_extlen_t len
, /* length of extent */
2116 int *stat
) /* success/failure */
2118 cur
->bc_rec
.a
.ar_startblock
= bno
;
2119 cur
->bc_rec
.a
.ar_blockcount
= len
;
2120 return xfs_alloc_lookup(cur
, XFS_LOOKUP_GE
, stat
);
2124 * Lookup the first record less than or equal to [bno, len]
2125 * in the btree given by cur.
2128 xfs_alloc_lookup_le(
2129 xfs_btree_cur_t
*cur
, /* btree cursor */
2130 xfs_agblock_t bno
, /* starting block of extent */
2131 xfs_extlen_t len
, /* length of extent */
2132 int *stat
) /* success/failure */
2134 cur
->bc_rec
.a
.ar_startblock
= bno
;
2135 cur
->bc_rec
.a
.ar_blockcount
= len
;
2136 return xfs_alloc_lookup(cur
, XFS_LOOKUP_LE
, stat
);
2140 * Update the record referred to by cur, to the value given by [bno, len].
2141 * This either works (return 0) or gets an EFSCORRUPTED error.
2145 xfs_btree_cur_t
*cur
, /* btree cursor */
2146 xfs_agblock_t bno
, /* starting block of extent */
2147 xfs_extlen_t len
) /* length of extent */
2149 xfs_alloc_block_t
*block
; /* btree block to update */
2150 int error
; /* error return value */
2151 int ptr
; /* current record number (updating) */
2155 * Pick up the a.g. freelist struct and the current block.
2157 block
= XFS_BUF_TO_ALLOC_BLOCK(cur
->bc_bufs
[0]);
2159 if ((error
= xfs_btree_check_sblock(cur
, block
, 0, cur
->bc_bufs
[0])))
2163 * Get the address of the rec to be updated.
2165 ptr
= cur
->bc_ptrs
[0];
2167 xfs_alloc_rec_t
*rp
; /* pointer to updated record */
2169 rp
= XFS_ALLOC_REC_ADDR(block
, ptr
, cur
);
2171 * Fill in the new contents and log them.
2173 rp
->ar_startblock
= cpu_to_be32(bno
);
2174 rp
->ar_blockcount
= cpu_to_be32(len
);
2175 xfs_alloc_log_recs(cur
, cur
->bc_bufs
[0], ptr
, ptr
);
2178 * If it's the by-size btree and it's the last leaf block and
2179 * it's the last record... then update the size of the longest
2180 * extent in the a.g., which we cache in the a.g. freelist header.
2182 if (cur
->bc_btnum
== XFS_BTNUM_CNT
&&
2183 be32_to_cpu(block
->bb_rightsib
) == NULLAGBLOCK
&&
2184 ptr
== be16_to_cpu(block
->bb_numrecs
)) {
2185 xfs_agf_t
*agf
; /* a.g. freespace header */
2186 xfs_agnumber_t seqno
;
2188 agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
2189 seqno
= be32_to_cpu(agf
->agf_seqno
);
2190 cur
->bc_mp
->m_perag
[seqno
].pagf_longest
= len
;
2191 agf
->agf_longest
= cpu_to_be32(len
);
2192 xfs_alloc_log_agf(cur
->bc_tp
, cur
->bc_private
.a
.agbp
,
2196 * Updating first record in leaf. Pass new key value up to our parent.
2199 xfs_alloc_key_t key
; /* key containing [bno, len] */
2201 key
.ar_startblock
= cpu_to_be32(bno
);
2202 key
.ar_blockcount
= cpu_to_be32(len
);
2203 if ((error
= xfs_alloc_updkey(cur
, &key
, 1)))