aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc_btree.c
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:58:01 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:58:01 -0400
commit91cca5df9bc85efdabfa645f51d54259ed09f4bf (patch)
tree29032361e21d1210effb72f4018f2a202d6a9fb0 /fs/xfs/xfs_alloc_btree.c
parentd4b3a4b7dd62f2e111d4d0afa9ef3f9b6cd955c0 (diff)
[XFS] implement generic xfs_btree_delete/delrec
Make the btree delete code generic. Based on a patch from David Chinner with lots of changes to follow the original btree implementations more closely. While this loses some of the generic helper routines for inserting/moving/removing records it also solves some of the one off bugs in the original code and makes it easier to verify. SGI-PV: 985583 SGI-Modid: xfs-linux-melb:xfs-kern:32205a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: Bill O'Donnell <billodo@sgi.com> Signed-off-by: David Chinner <david@fromorbit.com>
Diffstat (limited to 'fs/xfs/xfs_alloc_btree.c')
-rw-r--r--fs/xfs/xfs_alloc_btree.c744
1 files changed, 59 insertions, 685 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index f124ddd91c08..d256b51f913d 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -40,691 +40,6 @@
40#include "xfs_alloc.h" 40#include "xfs_alloc.h"
41#include "xfs_error.h" 41#include "xfs_error.h"
42 42
43/*
44 * Prototypes for internal functions.
45 */
46
47STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
48STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
49STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
50STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
51
52/*
53 * Internal functions.
54 */
55
56/*
57 * Single level of the xfs_alloc_delete record deletion routine.
58 * Delete record pointed to by cur/level.
59 * Remove the record from its block then rebalance the tree.
60 * Return 0 for error, 1 for done, 2 to go on to the next level.
61 */
62STATIC int /* error */
63xfs_alloc_delrec(
64 xfs_btree_cur_t *cur, /* btree cursor */
65 int level, /* level removing record from */
66 int *stat) /* fail/done/go-on */
67{
68 xfs_agf_t *agf; /* allocation group freelist header */
69 xfs_alloc_block_t *block; /* btree block record/key lives in */
70 xfs_agblock_t bno; /* btree block number */
71 xfs_buf_t *bp; /* buffer for block */
72 int error; /* error return value */
73 int i; /* loop index */
74 xfs_alloc_key_t key; /* kp points here if block is level 0 */
75 xfs_agblock_t lbno; /* left block's block number */
76 xfs_buf_t *lbp; /* left block's buffer pointer */
77 xfs_alloc_block_t *left; /* left btree block */
78 xfs_alloc_key_t *lkp=NULL; /* left block key pointer */
79 xfs_alloc_ptr_t *lpp=NULL; /* left block address pointer */
80 int lrecs=0; /* number of records in left block */
81 xfs_alloc_rec_t *lrp; /* left block record pointer */
82 xfs_mount_t *mp; /* mount structure */
83 int ptr; /* index in btree block for this rec */
84 xfs_agblock_t rbno; /* right block's block number */
85 xfs_buf_t *rbp; /* right block's buffer pointer */
86 xfs_alloc_block_t *right; /* right btree block */
87 xfs_alloc_key_t *rkp; /* right block key pointer */
88 xfs_alloc_ptr_t *rpp; /* right block address pointer */
89 int rrecs=0; /* number of records in right block */
90 int numrecs;
91 xfs_alloc_rec_t *rrp; /* right block record pointer */
92 xfs_btree_cur_t *tcur; /* temporary btree cursor */
93
94 /*
95 * Get the index of the entry being deleted, check for nothing there.
96 */
97 ptr = cur->bc_ptrs[level];
98 if (ptr == 0) {
99 *stat = 0;
100 return 0;
101 }
102 /*
103 * Get the buffer & block containing the record or key/ptr.
104 */
105 bp = cur->bc_bufs[level];
106 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
107#ifdef DEBUG
108 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
109 return error;
110#endif
111 /*
112 * Fail if we're off the end of the block.
113 */
114 numrecs = be16_to_cpu(block->bb_numrecs);
115 if (ptr > numrecs) {
116 *stat = 0;
117 return 0;
118 }
119 XFS_STATS_INC(xs_abt_delrec);
120 /*
121 * It's a nonleaf. Excise the key and ptr being deleted, by
122 * sliding the entries past them down one.
123 * Log the changed areas of the block.
124 */
125 if (level > 0) {
126 lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
127 lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
128#ifdef DEBUG
129 for (i = ptr; i < numrecs; i++) {
130 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
131 return error;
132 }
133#endif
134 if (ptr < numrecs) {
135 memmove(&lkp[ptr - 1], &lkp[ptr],
136 (numrecs - ptr) * sizeof(*lkp));
137 memmove(&lpp[ptr - 1], &lpp[ptr],
138 (numrecs - ptr) * sizeof(*lpp));
139 xfs_alloc_log_ptrs(cur, bp, ptr, numrecs - 1);
140 xfs_alloc_log_keys(cur, bp, ptr, numrecs - 1);
141 }
142 }
143 /*
144 * It's a leaf. Excise the record being deleted, by sliding the
145 * entries past it down one. Log the changed areas of the block.
146 */
147 else {
148 lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
149 if (ptr < numrecs) {
150 memmove(&lrp[ptr - 1], &lrp[ptr],
151 (numrecs - ptr) * sizeof(*lrp));
152 xfs_alloc_log_recs(cur, bp, ptr, numrecs - 1);
153 }
154 /*
155 * If it's the first record in the block, we'll need a key
156 * structure to pass up to the next level (updkey).
157 */
158 if (ptr == 1) {
159 key.ar_startblock = lrp->ar_startblock;
160 key.ar_blockcount = lrp->ar_blockcount;
161 lkp = &key;
162 }
163 }
164 /*
165 * Decrement and log the number of entries in the block.
166 */
167 numrecs--;
168 block->bb_numrecs = cpu_to_be16(numrecs);
169 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
170 /*
171 * See if the longest free extent in the allocation group was
172 * changed by this operation. True if it's the by-size btree, and
173 * this is the leaf level, and there is no right sibling block,
174 * and this was the last record.
175 */
176 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
177 mp = cur->bc_mp;
178
179 if (level == 0 &&
180 cur->bc_btnum == XFS_BTNUM_CNT &&
181 be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
182 ptr > numrecs) {
183 ASSERT(ptr == numrecs + 1);
184 /*
185 * There are still records in the block. Grab the size
186 * from the last one.
187 */
188 if (numrecs) {
189 rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
190 agf->agf_longest = rrp->ar_blockcount;
191 }
192 /*
193 * No free extents left.
194 */
195 else
196 agf->agf_longest = 0;
197 mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest =
198 be32_to_cpu(agf->agf_longest);
199 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
200 XFS_AGF_LONGEST);
201 }
202 /*
203 * Is this the root level? If so, we're almost done.
204 */
205 if (level == cur->bc_nlevels - 1) {
206 /*
207 * If this is the root level,
208 * and there's only one entry left,
209 * and it's NOT the leaf level,
210 * then we can get rid of this level.
211 */
212 if (numrecs == 1 && level > 0) {
213 /*
214 * lpp is still set to the first pointer in the block.
215 * Make it the new root of the btree.
216 */
217 bno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
218 agf->agf_roots[cur->bc_btnum] = *lpp;
219 be32_add_cpu(&agf->agf_levels[cur->bc_btnum], -1);
220 mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_levels[cur->bc_btnum]--;
221 /*
222 * Put this buffer/block on the ag's freelist.
223 */
224 error = xfs_alloc_put_freelist(cur->bc_tp,
225 cur->bc_private.a.agbp, NULL, bno, 1);
226 if (error)
227 return error;
228 /*
229 * Since blocks move to the free list without the
230 * coordination used in xfs_bmap_finish, we can't allow
231 * block to be available for reallocation and
232 * non-transaction writing (user data) until we know
233 * that the transaction that moved it to the free list
234 * is permanently on disk. We track the blocks by
235 * declaring these blocks as "busy"; the busy list is
236 * maintained on a per-ag basis and each transaction
237 * records which entries should be removed when the
238 * iclog commits to disk. If a busy block is
239 * allocated, the iclog is pushed up to the LSN
240 * that freed the block.
241 */
242 xfs_alloc_mark_busy(cur->bc_tp,
243 be32_to_cpu(agf->agf_seqno), bno, 1);
244
245 xfs_trans_agbtree_delta(cur->bc_tp, -1);
246 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
247 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
248 /*
249 * Update the cursor so there's one fewer level.
250 */
251 xfs_btree_setbuf(cur, level, NULL);
252 cur->bc_nlevels--;
253 } else if (level > 0 &&
254 (error = xfs_btree_decrement(cur, level, &i)))
255 return error;
256 *stat = 1;
257 return 0;
258 }
259 /*
260 * If we deleted the leftmost entry in the block, update the
261 * key values above us in the tree.
262 */
263 if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)lkp, level + 1)))
264 return error;
265 /*
266 * If the number of records remaining in the block is at least
267 * the minimum, we're done.
268 */
269 if (numrecs >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
270 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i)))
271 return error;
272 *stat = 1;
273 return 0;
274 }
275 /*
276 * Otherwise, we have to move some records around to keep the
277 * tree balanced. Look at the left and right sibling blocks to
278 * see if we can re-balance by moving only one record.
279 */
280 rbno = be32_to_cpu(block->bb_rightsib);
281 lbno = be32_to_cpu(block->bb_leftsib);
282 bno = NULLAGBLOCK;
283 ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
284 /*
285 * Duplicate the cursor so our btree manipulations here won't
286 * disrupt the next level up.
287 */
288 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
289 return error;
290 /*
291 * If there's a right sibling, see if it's ok to shift an entry
292 * out of it.
293 */
294 if (rbno != NULLAGBLOCK) {
295 /*
296 * Move the temp cursor to the last entry in the next block.
297 * Actually any entry but the first would suffice.
298 */
299 i = xfs_btree_lastrec(tcur, level);
300 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
301 if ((error = xfs_btree_increment(tcur, level, &i)))
302 goto error0;
303 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
304 i = xfs_btree_lastrec(tcur, level);
305 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
306 /*
307 * Grab a pointer to the block.
308 */
309 rbp = tcur->bc_bufs[level];
310 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
311#ifdef DEBUG
312 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
313 goto error0;
314#endif
315 /*
316 * Grab the current block number, for future use.
317 */
318 bno = be32_to_cpu(right->bb_leftsib);
319 /*
320 * If right block is full enough so that removing one entry
321 * won't make it too empty, and left-shifting an entry out
322 * of right to us works, we're done.
323 */
324 if (be16_to_cpu(right->bb_numrecs) - 1 >=
325 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
326 if ((error = xfs_btree_lshift(tcur, level, &i)))
327 goto error0;
328 if (i) {
329 ASSERT(be16_to_cpu(block->bb_numrecs) >=
330 XFS_ALLOC_BLOCK_MINRECS(level, cur));
331 xfs_btree_del_cursor(tcur,
332 XFS_BTREE_NOERROR);
333 if (level > 0 &&
334 (error = xfs_btree_decrement(cur, level,
335 &i)))
336 return error;
337 *stat = 1;
338 return 0;
339 }
340 }
341 /*
342 * Otherwise, grab the number of records in right for
343 * future reference, and fix up the temp cursor to point
344 * to our block again (last record).
345 */
346 rrecs = be16_to_cpu(right->bb_numrecs);
347 if (lbno != NULLAGBLOCK) {
348 i = xfs_btree_firstrec(tcur, level);
349 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
350 if ((error = xfs_btree_decrement(tcur, level, &i)))
351 goto error0;
352 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
353 }
354 }
355 /*
356 * If there's a left sibling, see if it's ok to shift an entry
357 * out of it.
358 */
359 if (lbno != NULLAGBLOCK) {
360 /*
361 * Move the temp cursor to the first entry in the
362 * previous block.
363 */
364 i = xfs_btree_firstrec(tcur, level);
365 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
366 if ((error = xfs_btree_decrement(tcur, level, &i)))
367 goto error0;
368 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
369 xfs_btree_firstrec(tcur, level);
370 /*
371 * Grab a pointer to the block.
372 */
373 lbp = tcur->bc_bufs[level];
374 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
375#ifdef DEBUG
376 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
377 goto error0;
378#endif
379 /*
380 * Grab the current block number, for future use.
381 */
382 bno = be32_to_cpu(left->bb_rightsib);
383 /*
384 * If left block is full enough so that removing one entry
385 * won't make it too empty, and right-shifting an entry out
386 * of left to us works, we're done.
387 */
388 if (be16_to_cpu(left->bb_numrecs) - 1 >=
389 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
390 if ((error = xfs_btree_rshift(tcur, level, &i)))
391 goto error0;
392 if (i) {
393 ASSERT(be16_to_cpu(block->bb_numrecs) >=
394 XFS_ALLOC_BLOCK_MINRECS(level, cur));
395 xfs_btree_del_cursor(tcur,
396 XFS_BTREE_NOERROR);
397 if (level == 0)
398 cur->bc_ptrs[0]++;
399 *stat = 1;
400 return 0;
401 }
402 }
403 /*
404 * Otherwise, grab the number of records in right for
405 * future reference.
406 */
407 lrecs = be16_to_cpu(left->bb_numrecs);
408 }
409 /*
410 * Delete the temp cursor, we're done with it.
411 */
412 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
413 /*
414 * If here, we need to do a join to keep the tree balanced.
415 */
416 ASSERT(bno != NULLAGBLOCK);
417 /*
418 * See if we can join with the left neighbor block.
419 */
420 if (lbno != NULLAGBLOCK &&
421 lrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
422 /*
423 * Set "right" to be the starting block,
424 * "left" to be the left neighbor.
425 */
426 rbno = bno;
427 right = block;
428 rrecs = be16_to_cpu(right->bb_numrecs);
429 rbp = bp;
430 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
431 cur->bc_private.a.agno, lbno, 0, &lbp,
432 XFS_ALLOC_BTREE_REF)))
433 return error;
434 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
435 lrecs = be16_to_cpu(left->bb_numrecs);
436 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
437 return error;
438 }
439 /*
440 * If that won't work, see if we can join with the right neighbor block.
441 */
442 else if (rbno != NULLAGBLOCK &&
443 rrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
444 /*
445 * Set "left" to be the starting block,
446 * "right" to be the right neighbor.
447 */
448 lbno = bno;
449 left = block;
450 lrecs = be16_to_cpu(left->bb_numrecs);
451 lbp = bp;
452 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
453 cur->bc_private.a.agno, rbno, 0, &rbp,
454 XFS_ALLOC_BTREE_REF)))
455 return error;
456 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
457 rrecs = be16_to_cpu(right->bb_numrecs);
458 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
459 return error;
460 }
461 /*
462 * Otherwise, we can't fix the imbalance.
463 * Just return. This is probably a logic error, but it's not fatal.
464 */
465 else {
466 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i)))
467 return error;
468 *stat = 1;
469 return 0;
470 }
471 /*
472 * We're now going to join "left" and "right" by moving all the stuff
473 * in "right" to "left" and deleting "right".
474 */
475 if (level > 0) {
476 /*
477 * It's a non-leaf. Move keys and pointers.
478 */
479 lkp = XFS_ALLOC_KEY_ADDR(left, lrecs + 1, cur);
480 lpp = XFS_ALLOC_PTR_ADDR(left, lrecs + 1, cur);
481 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
482 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
483#ifdef DEBUG
484 for (i = 0; i < rrecs; i++) {
485 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
486 return error;
487 }
488#endif
489 memcpy(lkp, rkp, rrecs * sizeof(*lkp));
490 memcpy(lpp, rpp, rrecs * sizeof(*lpp));
491 xfs_alloc_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
492 xfs_alloc_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
493 } else {
494 /*
495 * It's a leaf. Move records.
496 */
497 lrp = XFS_ALLOC_REC_ADDR(left, lrecs + 1, cur);
498 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
499 memcpy(lrp, rrp, rrecs * sizeof(*lrp));
500 xfs_alloc_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
501 }
502 /*
503 * If we joined with the left neighbor, set the buffer in the
504 * cursor to the left block, and fix up the index.
505 */
506 if (bp != lbp) {
507 xfs_btree_setbuf(cur, level, lbp);
508 cur->bc_ptrs[level] += lrecs;
509 }
510 /*
511 * If we joined with the right neighbor and there's a level above
512 * us, increment the cursor at that level.
513 */
514 else if (level + 1 < cur->bc_nlevels &&
515 (error = xfs_btree_increment(cur, level + 1, &i)))
516 return error;
517 /*
518 * Fix up the number of records in the surviving block.
519 */
520 lrecs += rrecs;
521 left->bb_numrecs = cpu_to_be16(lrecs);
522 /*
523 * Fix up the right block pointer in the surviving block, and log it.
524 */
525 left->bb_rightsib = right->bb_rightsib;
526 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
527 /*
528 * If there is a right sibling now, make it point to the
529 * remaining block.
530 */
531 if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
532 xfs_alloc_block_t *rrblock;
533 xfs_buf_t *rrbp;
534
535 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
536 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
537 &rrbp, XFS_ALLOC_BTREE_REF)))
538 return error;
539 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
540 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
541 return error;
542 rrblock->bb_leftsib = cpu_to_be32(lbno);
543 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
544 }
545 /*
546 * Free the deleting block by putting it on the freelist.
547 */
548 error = xfs_alloc_put_freelist(cur->bc_tp,
549 cur->bc_private.a.agbp, NULL, rbno, 1);
550 if (error)
551 return error;
552 /*
553 * Since blocks move to the free list without the coordination
554 * used in xfs_bmap_finish, we can't allow block to be available
555 * for reallocation and non-transaction writing (user data)
556 * until we know that the transaction that moved it to the free
557 * list is permanently on disk. We track the blocks by declaring
558 * these blocks as "busy"; the busy list is maintained on a
559 * per-ag basis and each transaction records which entries
560 * should be removed when the iclog commits to disk. If a
561 * busy block is allocated, the iclog is pushed up to the
562 * LSN that freed the block.
563 */
564 xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
565 xfs_trans_agbtree_delta(cur->bc_tp, -1);
566
567 /*
568 * Adjust the current level's cursor so that we're left referring
569 * to the right node, after we're done.
570 * If this leaves the ptr value 0 our caller will fix it up.
571 */
572 if (level > 0)
573 cur->bc_ptrs[level]--;
574 /*
575 * Return value means the next level up has something to do.
576 */
577 *stat = 2;
578 return 0;
579
580error0:
581 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
582 return error;
583}
584
585/*
586 * Log header fields from a btree block.
587 */
588STATIC void
589xfs_alloc_log_block(
590 xfs_trans_t *tp, /* transaction pointer */
591 xfs_buf_t *bp, /* buffer containing btree block */
592 int fields) /* mask of fields: XFS_BB_... */
593{
594 int first; /* first byte offset logged */
595 int last; /* last byte offset logged */
596 static const short offsets[] = { /* table of offsets */
597 offsetof(xfs_alloc_block_t, bb_magic),
598 offsetof(xfs_alloc_block_t, bb_level),
599 offsetof(xfs_alloc_block_t, bb_numrecs),
600 offsetof(xfs_alloc_block_t, bb_leftsib),
601 offsetof(xfs_alloc_block_t, bb_rightsib),
602 sizeof(xfs_alloc_block_t)
603 };
604
605 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
606 xfs_trans_log_buf(tp, bp, first, last);
607}
608
609/*
610 * Log keys from a btree block (nonleaf).
611 */
612STATIC void
613xfs_alloc_log_keys(
614 xfs_btree_cur_t *cur, /* btree cursor */
615 xfs_buf_t *bp, /* buffer containing btree block */
616 int kfirst, /* index of first key to log */
617 int klast) /* index of last key to log */
618{
619 xfs_alloc_block_t *block; /* btree block to log from */
620 int first; /* first byte offset logged */
621 xfs_alloc_key_t *kp; /* key pointer in btree block */
622 int last; /* last byte offset logged */
623
624 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
625 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
626 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
627 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
628 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
629}
630
631/*
632 * Log block pointer fields from a btree block (nonleaf).
633 */
634STATIC void
635xfs_alloc_log_ptrs(
636 xfs_btree_cur_t *cur, /* btree cursor */
637 xfs_buf_t *bp, /* buffer containing btree block */
638 int pfirst, /* index of first pointer to log */
639 int plast) /* index of last pointer to log */
640{
641 xfs_alloc_block_t *block; /* btree block to log from */
642 int first; /* first byte offset logged */
643 int last; /* last byte offset logged */
644 xfs_alloc_ptr_t *pp; /* block-pointer pointer in btree blk */
645
646 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
647 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
648 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
649 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
650 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
651}
652
653/*
654 * Log records from a btree block (leaf).
655 */
656STATIC void
657xfs_alloc_log_recs(
658 xfs_btree_cur_t *cur, /* btree cursor */
659 xfs_buf_t *bp, /* buffer containing btree block */
660 int rfirst, /* index of first record to log */
661 int rlast) /* index of last record to log */
662{
663 xfs_alloc_block_t *block; /* btree block to log from */
664 int first; /* first byte offset logged */
665 int last; /* last byte offset logged */
666 xfs_alloc_rec_t *rp; /* record pointer for btree block */
667
668
669 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
670 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
671#ifdef DEBUG
672 {
673 xfs_agf_t *agf;
674 xfs_alloc_rec_t *p;
675
676 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
677 for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
678 ASSERT(be32_to_cpu(p->ar_startblock) +
679 be32_to_cpu(p->ar_blockcount) <=
680 be32_to_cpu(agf->agf_length));
681 }
682#endif
683 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
684 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
685 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
686}
687
688
689/*
690 * Externally visible routines.
691 */
692
693/*
694 * Delete the record pointed to by cur.
695 * The cursor refers to the place where the record was (could be inserted)
696 * when the operation returns.
697 */
698int /* error */
699xfs_alloc_delete(
700 xfs_btree_cur_t *cur, /* btree cursor */
701 int *stat) /* success/failure */
702{
703 int error; /* error return value */
704 int i; /* result code */
705 int level; /* btree level */
706
707 /*
708 * Go up the tree, starting at leaf level.
709 * If 2 is returned then a join was done; go to the next level.
710 * Otherwise we are done.
711 */
712 for (level = 0, i = 2; i == 2; level++) {
713 if ((error = xfs_alloc_delrec(cur, level, &i)))
714 return error;
715 }
716 if (i == 0) {
717 for (level = 1; level < cur->bc_nlevels; level++) {
718 if (cur->bc_ptrs[level] == 0) {
719 if ((error = xfs_btree_decrement(cur, level, &i)))
720 return error;
721 break;
722 }
723 }
724 }
725 *stat = i;
726 return 0;
727}
728 43
729/* 44/*
730 * Get the data from the pointed-to record. 45 * Get the data from the pointed-to record.
@@ -879,6 +194,7 @@ xfs_allocbt_update_lastrec(
879 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 194 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
880 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 195 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
881 __be32 len; 196 __be32 len;
197 int numrecs;
882 198
883 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); 199 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
884 200
@@ -898,6 +214,22 @@ xfs_allocbt_update_lastrec(
898 return; 214 return;
899 len = rec->alloc.ar_blockcount; 215 len = rec->alloc.ar_blockcount;
900 break; 216 break;
217 case LASTREC_DELREC:
218 numrecs = xfs_btree_get_numrecs(block);
219 if (ptr <= numrecs)
220 return;
221 ASSERT(ptr == numrecs + 1);
222
223 if (numrecs) {
224 xfs_alloc_rec_t *rrp;
225
226 rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
227 len = rrp->ar_blockcount;
228 } else {
229 len = 0;
230 }
231
232 break;
901 default: 233 default:
902 ASSERT(0); 234 ASSERT(0);
903 return; 235 return;
@@ -909,6 +241,14 @@ xfs_allocbt_update_lastrec(
909} 241}
910 242
911STATIC int 243STATIC int
244xfs_allocbt_get_minrecs(
245 struct xfs_btree_cur *cur,
246 int level)
247{
248 return cur->bc_mp->m_alloc_mnr[level != 0];
249}
250
251STATIC int
912xfs_allocbt_get_maxrecs( 252xfs_allocbt_get_maxrecs(
913 struct xfs_btree_cur *cur, 253 struct xfs_btree_cur *cur,
914 int level) 254 int level)
@@ -983,6 +323,38 @@ xfs_allocbt_key_diff(
983 return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 323 return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
984} 324}
985 325
326STATIC int
327xfs_allocbt_kill_root(
328 struct xfs_btree_cur *cur,
329 struct xfs_buf *bp,
330 int level,
331 union xfs_btree_ptr *newroot)
332{
333 int error;
334
335 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
336 XFS_BTREE_STATS_INC(cur, killroot);
337
338 /*
339 * Update the root pointer, decreasing the level by 1 and then
340 * free the old root.
341 */
342 xfs_allocbt_set_root(cur, newroot, -1);
343 error = xfs_allocbt_free_block(cur, bp);
344 if (error) {
345 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
346 return error;
347 }
348
349 XFS_BTREE_STATS_INC(cur, free);
350
351 xfs_btree_setbuf(cur, level, NULL);
352 cur->bc_nlevels--;
353
354 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
355 return 0;
356}
357
986#ifdef XFS_BTREE_TRACE 358#ifdef XFS_BTREE_TRACE
987ktrace_t *xfs_allocbt_trace_buf; 359ktrace_t *xfs_allocbt_trace_buf;
988 360
@@ -1055,9 +427,11 @@ static const struct xfs_btree_ops xfs_allocbt_ops = {
1055 427
1056 .dup_cursor = xfs_allocbt_dup_cursor, 428 .dup_cursor = xfs_allocbt_dup_cursor,
1057 .set_root = xfs_allocbt_set_root, 429 .set_root = xfs_allocbt_set_root,
430 .kill_root = xfs_allocbt_kill_root,
1058 .alloc_block = xfs_allocbt_alloc_block, 431 .alloc_block = xfs_allocbt_alloc_block,
1059 .free_block = xfs_allocbt_free_block, 432 .free_block = xfs_allocbt_free_block,
1060 .update_lastrec = xfs_allocbt_update_lastrec, 433 .update_lastrec = xfs_allocbt_update_lastrec,
434 .get_minrecs = xfs_allocbt_get_minrecs,
1061 .get_maxrecs = xfs_allocbt_get_maxrecs, 435 .get_maxrecs = xfs_allocbt_get_maxrecs,
1062 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 436 .init_key_from_rec = xfs_allocbt_init_key_from_rec,
1063 .init_rec_from_key = xfs_allocbt_init_rec_from_key, 437 .init_rec_from_key = xfs_allocbt_init_rec_from_key,
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-18 10:00:28 -0500