aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs
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
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')
-rw-r--r--fs/xfs/xfs_alloc.c14
-rw-r--r--fs/xfs/xfs_alloc_btree.c744
-rw-r--r--fs/xfs/xfs_alloc_btree.h7
-rw-r--r--fs/xfs/xfs_bmap.c14
-rw-r--r--fs/xfs/xfs_bmap_btree.c525
-rw-r--r--fs/xfs/xfs_bmap_btree.h3
-rw-r--r--fs/xfs/xfs_btree.c593
-rw-r--r--fs/xfs/xfs_btree.h5
-rw-r--r--fs/xfs/xfs_ialloc.c4
-rw-r--r--fs/xfs/xfs_ialloc_btree.c646
-rw-r--r--fs/xfs/xfs_ialloc_btree.h7
11 files changed, 723 insertions, 1839 deletions
diff --git a/fs/xfs/xfs_alloc.c b/fs/xfs/xfs_alloc.c
index a983824c12be..e9c70249d2c5 100644
--- a/fs/xfs/xfs_alloc.c
+++ b/fs/xfs/xfs_alloc.c
@@ -398,7 +398,7 @@ xfs_alloc_fixup_trees(
398 /* 398 /*
399 * Delete the entry from the by-size btree. 399 * Delete the entry from the by-size btree.
400 */ 400 */
401 if ((error = xfs_alloc_delete(cnt_cur, &i))) 401 if ((error = xfs_btree_delete(cnt_cur, &i)))
402 return error; 402 return error;
403 XFS_WANT_CORRUPTED_RETURN(i == 1); 403 XFS_WANT_CORRUPTED_RETURN(i == 1);
404 /* 404 /*
@@ -427,7 +427,7 @@ xfs_alloc_fixup_trees(
427 /* 427 /*
428 * No remaining freespace, just delete the by-block tree entry. 428 * No remaining freespace, just delete the by-block tree entry.
429 */ 429 */
430 if ((error = xfs_alloc_delete(bno_cur, &i))) 430 if ((error = xfs_btree_delete(bno_cur, &i)))
431 return error; 431 return error;
432 XFS_WANT_CORRUPTED_RETURN(i == 1); 432 XFS_WANT_CORRUPTED_RETURN(i == 1);
433 } else { 433 } else {
@@ -1651,7 +1651,7 @@ xfs_free_ag_extent(
1651 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i))) 1651 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1652 goto error0; 1652 goto error0;
1653 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1653 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1654 if ((error = xfs_alloc_delete(cnt_cur, &i))) 1654 if ((error = xfs_btree_delete(cnt_cur, &i)))
1655 goto error0; 1655 goto error0;
1656 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1656 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1657 /* 1657 /*
@@ -1660,13 +1660,13 @@ xfs_free_ag_extent(
1660 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i))) 1660 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1661 goto error0; 1661 goto error0;
1662 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1662 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1663 if ((error = xfs_alloc_delete(cnt_cur, &i))) 1663 if ((error = xfs_btree_delete(cnt_cur, &i)))
1664 goto error0; 1664 goto error0;
1665 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1665 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1666 /* 1666 /*
1667 * Delete the old by-block entry for the right block. 1667 * Delete the old by-block entry for the right block.
1668 */ 1668 */
1669 if ((error = xfs_alloc_delete(bno_cur, &i))) 1669 if ((error = xfs_btree_delete(bno_cur, &i)))
1670 goto error0; 1670 goto error0;
1671 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1671 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1672 /* 1672 /*
@@ -1711,7 +1711,7 @@ xfs_free_ag_extent(
1711 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i))) 1711 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1712 goto error0; 1712 goto error0;
1713 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1713 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1714 if ((error = xfs_alloc_delete(cnt_cur, &i))) 1714 if ((error = xfs_btree_delete(cnt_cur, &i)))
1715 goto error0; 1715 goto error0;
1716 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1716 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1717 /* 1717 /*
@@ -1737,7 +1737,7 @@ xfs_free_ag_extent(
1737 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i))) 1737 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1738 goto error0; 1738 goto error0;
1739 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1739 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1740 if ((error = xfs_alloc_delete(cnt_cur, &i))) 1740 if ((error = xfs_btree_delete(cnt_cur, &i)))
1741 goto error0; 1741 goto error0;
1742 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1742 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1743 /* 1743 /*
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,
diff --git a/fs/xfs/xfs_alloc_btree.h b/fs/xfs/xfs_alloc_btree.h
index 2e340ef8025a..8d2e3ec21fd0 100644
--- a/fs/xfs/xfs_alloc_btree.h
+++ b/fs/xfs/xfs_alloc_btree.h
@@ -95,13 +95,6 @@ typedef struct xfs_btree_sblock xfs_alloc_block_t;
95 XFS_BTREE_PTR_ADDR(xfs_alloc, bb, i, XFS_ALLOC_BLOCK_MAXRECS(1, cur)) 95 XFS_BTREE_PTR_ADDR(xfs_alloc, bb, i, XFS_ALLOC_BLOCK_MAXRECS(1, cur))
96 96
97/* 97/*
98 * Delete the record pointed to by cur.
99 * The cursor refers to the place where the record was (could be inserted)
100 * when the operation returns.
101 */
102extern int xfs_alloc_delete(struct xfs_btree_cur *cur, int *stat);
103
104/*
105 * Get the data from the pointed-to record. 98 * Get the data from the pointed-to record.
106 */ 99 */
107extern int xfs_alloc_get_rec(struct xfs_btree_cur *cur, xfs_agblock_t *bno, 100extern int xfs_alloc_get_rec(struct xfs_btree_cur *cur, xfs_agblock_t *bno,
diff --git a/fs/xfs/xfs_bmap.c b/fs/xfs/xfs_bmap.c
index 85e2e8b9cf41..74761ca2c63d 100644
--- a/fs/xfs/xfs_bmap.c
+++ b/fs/xfs/xfs_bmap.c
@@ -864,7 +864,7 @@ xfs_bmap_add_extent_delay_real(
864 RIGHT.br_blockcount, &i))) 864 RIGHT.br_blockcount, &i)))
865 goto done; 865 goto done;
866 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 866 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
867 if ((error = xfs_bmbt_delete(cur, &i))) 867 if ((error = xfs_btree_delete(cur, &i)))
868 goto done; 868 goto done;
869 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 869 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
870 if ((error = xfs_btree_decrement(cur, 0, &i))) 870 if ((error = xfs_btree_decrement(cur, 0, &i)))
@@ -1425,13 +1425,13 @@ xfs_bmap_add_extent_unwritten_real(
1425 RIGHT.br_blockcount, &i))) 1425 RIGHT.br_blockcount, &i)))
1426 goto done; 1426 goto done;
1427 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1427 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1428 if ((error = xfs_bmbt_delete(cur, &i))) 1428 if ((error = xfs_btree_delete(cur, &i)))
1429 goto done; 1429 goto done;
1430 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1430 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1431 if ((error = xfs_btree_decrement(cur, 0, &i))) 1431 if ((error = xfs_btree_decrement(cur, 0, &i)))
1432 goto done; 1432 goto done;
1433 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1433 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1434 if ((error = xfs_bmbt_delete(cur, &i))) 1434 if ((error = xfs_btree_delete(cur, &i)))
1435 goto done; 1435 goto done;
1436 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1436 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1437 if ((error = xfs_btree_decrement(cur, 0, &i))) 1437 if ((error = xfs_btree_decrement(cur, 0, &i)))
@@ -1474,7 +1474,7 @@ xfs_bmap_add_extent_unwritten_real(
1474 &i))) 1474 &i)))
1475 goto done; 1475 goto done;
1476 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1476 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1477 if ((error = xfs_bmbt_delete(cur, &i))) 1477 if ((error = xfs_btree_delete(cur, &i)))
1478 goto done; 1478 goto done;
1479 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1479 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1480 if ((error = xfs_btree_decrement(cur, 0, &i))) 1480 if ((error = xfs_btree_decrement(cur, 0, &i)))
@@ -1517,7 +1517,7 @@ xfs_bmap_add_extent_unwritten_real(
1517 RIGHT.br_blockcount, &i))) 1517 RIGHT.br_blockcount, &i)))
1518 goto done; 1518 goto done;
1519 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1519 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1520 if ((error = xfs_bmbt_delete(cur, &i))) 1520 if ((error = xfs_btree_delete(cur, &i)))
1521 goto done; 1521 goto done;
1522 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 1522 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
1523 if ((error = xfs_btree_decrement(cur, 0, &i))) 1523 if ((error = xfs_btree_decrement(cur, 0, &i)))
@@ -2152,7 +2152,7 @@ xfs_bmap_add_extent_hole_real(
2152 right.br_blockcount, &i))) 2152 right.br_blockcount, &i)))
2153 goto done; 2153 goto done;
2154 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 2154 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
2155 if ((error = xfs_bmbt_delete(cur, &i))) 2155 if ((error = xfs_btree_delete(cur, &i)))
2156 goto done; 2156 goto done;
2157 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 2157 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
2158 if ((error = xfs_btree_decrement(cur, 0, &i))) 2158 if ((error = xfs_btree_decrement(cur, 0, &i)))
@@ -3216,7 +3216,7 @@ xfs_bmap_del_extent(
3216 flags |= XFS_ILOG_FEXT(whichfork); 3216 flags |= XFS_ILOG_FEXT(whichfork);
3217 break; 3217 break;
3218 } 3218 }
3219 if ((error = xfs_bmbt_delete(cur, &i))) 3219 if ((error = xfs_btree_delete(cur, &i)))
3220 goto done; 3220 goto done;
3221 XFS_WANT_CORRUPTED_GOTO(i == 1, done); 3221 XFS_WANT_CORRUPTED_GOTO(i == 1, done);
3222 break; 3222 break;
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 6b7774ebc26a..5b8030561d78 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -44,14 +44,6 @@
44#include "xfs_error.h" 44#include "xfs_error.h"
45#include "xfs_quota.h" 45#include "xfs_quota.h"
46 46
47/*
48 * Prototypes for internal btree functions.
49 */
50
51
52STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
53STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
54
55#undef EXIT 47#undef EXIT
56 48
57#define ENTRY XBT_ENTRY 49#define ENTRY XBT_ENTRY
@@ -80,453 +72,6 @@ STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
80#define XFS_BMBT_TRACE_CURSOR(c,s) \ 72#define XFS_BMBT_TRACE_CURSOR(c,s) \
81 XFS_BTREE_TRACE_CURSOR(c,s) 73 XFS_BTREE_TRACE_CURSOR(c,s)
82 74
83
84/*
85 * Internal functions.
86 */
87
88/*
89 * Delete record pointed to by cur/level.
90 */
91STATIC int /* error */
92xfs_bmbt_delrec(
93 xfs_btree_cur_t *cur,
94 int level,
95 int *stat) /* success/failure */
96{
97 xfs_bmbt_block_t *block; /* bmap btree block */
98 xfs_fsblock_t bno; /* fs-relative block number */
99 xfs_buf_t *bp; /* buffer for block */
100 int error; /* error return value */
101 int i; /* loop counter */
102 int j; /* temp state */
103 xfs_bmbt_key_t key; /* bmap btree key */
104 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
105 xfs_fsblock_t lbno; /* left sibling block number */
106 xfs_buf_t *lbp; /* left buffer pointer */
107 xfs_bmbt_block_t *left; /* left btree block */
108 xfs_bmbt_key_t *lkp; /* left btree key */
109 xfs_bmbt_ptr_t *lpp; /* left address pointer */
110 int lrecs=0; /* left record count */
111 xfs_bmbt_rec_t *lrp; /* left record pointer */
112 xfs_mount_t *mp; /* file system mount point */
113 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
114 int ptr; /* key/record index */
115 xfs_fsblock_t rbno; /* right sibling block number */
116 xfs_buf_t *rbp; /* right buffer pointer */
117 xfs_bmbt_block_t *right; /* right btree block */
118 xfs_bmbt_key_t *rkp; /* right btree key */
119 xfs_bmbt_rec_t *rp; /* pointer to bmap btree rec */
120 xfs_bmbt_ptr_t *rpp; /* right address pointer */
121 xfs_bmbt_block_t *rrblock; /* right-right btree block */
122 xfs_buf_t *rrbp; /* right-right buffer pointer */
123 int rrecs=0; /* right record count */
124 xfs_bmbt_rec_t *rrp; /* right record pointer */
125 xfs_btree_cur_t *tcur; /* temporary btree cursor */
126 int numrecs; /* temporary numrec count */
127 int numlrecs, numrrecs;
128
129 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
130 XFS_BMBT_TRACE_ARGI(cur, level);
131 ptr = cur->bc_ptrs[level];
132 tcur = NULL;
133 if (ptr == 0) {
134 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
135 *stat = 0;
136 return 0;
137 }
138 block = xfs_bmbt_get_block(cur, level, &bp);
139 numrecs = be16_to_cpu(block->bb_numrecs);
140#ifdef DEBUG
141 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
142 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
143 goto error0;
144 }
145#endif
146 if (ptr > numrecs) {
147 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
148 *stat = 0;
149 return 0;
150 }
151 XFS_STATS_INC(xs_bmbt_delrec);
152 if (level > 0) {
153 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
154 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
155#ifdef DEBUG
156 for (i = ptr; i < numrecs; i++) {
157 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
158 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
159 goto error0;
160 }
161 }
162#endif
163 if (ptr < numrecs) {
164 memmove(&kp[ptr - 1], &kp[ptr],
165 (numrecs - ptr) * sizeof(*kp));
166 memmove(&pp[ptr - 1], &pp[ptr],
167 (numrecs - ptr) * sizeof(*pp));
168 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
169 xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
170 }
171 } else {
172 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
173 if (ptr < numrecs) {
174 memmove(&rp[ptr - 1], &rp[ptr],
175 (numrecs - ptr) * sizeof(*rp));
176 xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
177 }
178 if (ptr == 1) {
179 key.br_startoff =
180 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
181 kp = &key;
182 }
183 }
184 numrecs--;
185 block->bb_numrecs = cpu_to_be16(numrecs);
186 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
187 /*
188 * We're at the root level.
189 * First, shrink the root block in-memory.
190 * Try to get rid of the next level down.
191 * If we can't then there's nothing left to do.
192 */
193 if (level == cur->bc_nlevels - 1) {
194 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
195 cur->bc_private.b.whichfork);
196 if ((error = xfs_btree_kill_iroot(cur))) {
197 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
198 goto error0;
199 }
200 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
201 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
202 goto error0;
203 }
204 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
205 *stat = 1;
206 return 0;
207 }
208 if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)kp, level + 1))) {
209 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
210 goto error0;
211 }
212 if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
213 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
214 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
215 goto error0;
216 }
217 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
218 *stat = 1;
219 return 0;
220 }
221 rbno = be64_to_cpu(block->bb_rightsib);
222 lbno = be64_to_cpu(block->bb_leftsib);
223 /*
224 * One child of root, need to get a chance to copy its contents
225 * into the root and delete it. Can't go up to next level,
226 * there's nothing to delete there.
227 */
228 if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
229 level == cur->bc_nlevels - 2) {
230 if ((error = xfs_btree_kill_iroot(cur))) {
231 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
232 goto error0;
233 }
234 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
235 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
236 goto error0;
237 }
238 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
239 *stat = 1;
240 return 0;
241 }
242 ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
243 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
244 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
245 goto error0;
246 }
247 bno = NULLFSBLOCK;
248 if (rbno != NULLFSBLOCK) {
249 i = xfs_btree_lastrec(tcur, level);
250 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
251 if ((error = xfs_btree_increment(tcur, level, &i))) {
252 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
253 goto error0;
254 }
255 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
256 i = xfs_btree_lastrec(tcur, level);
257 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
258 rbp = tcur->bc_bufs[level];
259 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
260#ifdef DEBUG
261 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
262 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
263 goto error0;
264 }
265#endif
266 bno = be64_to_cpu(right->bb_leftsib);
267 if (be16_to_cpu(right->bb_numrecs) - 1 >=
268 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
269 if ((error = xfs_btree_lshift(tcur, level, &i))) {
270 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
271 goto error0;
272 }
273 if (i) {
274 ASSERT(be16_to_cpu(block->bb_numrecs) >=
275 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
276 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
277 tcur = NULL;
278 if (level > 0) {
279 if ((error = xfs_btree_decrement(cur,
280 level, &i))) {
281 XFS_BMBT_TRACE_CURSOR(cur,
282 ERROR);
283 goto error0;
284 }
285 }
286 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
287 *stat = 1;
288 return 0;
289 }
290 }
291 rrecs = be16_to_cpu(right->bb_numrecs);
292 if (lbno != NULLFSBLOCK) {
293 i = xfs_btree_firstrec(tcur, level);
294 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
295 if ((error = xfs_btree_decrement(tcur, level, &i))) {
296 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
297 goto error0;
298 }
299 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
300 }
301 }
302 if (lbno != NULLFSBLOCK) {
303 i = xfs_btree_firstrec(tcur, level);
304 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
305 /*
306 * decrement to last in block
307 */
308 if ((error = xfs_btree_decrement(tcur, level, &i))) {
309 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
310 goto error0;
311 }
312 i = xfs_btree_firstrec(tcur, level);
313 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
314 lbp = tcur->bc_bufs[level];
315 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
316#ifdef DEBUG
317 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
318 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
319 goto error0;
320 }
321#endif
322 bno = be64_to_cpu(left->bb_rightsib);
323 if (be16_to_cpu(left->bb_numrecs) - 1 >=
324 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
325 if ((error = xfs_btree_rshift(tcur, level, &i))) {
326 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
327 goto error0;
328 }
329 if (i) {
330 ASSERT(be16_to_cpu(block->bb_numrecs) >=
331 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
332 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
333 tcur = NULL;
334 if (level == 0)
335 cur->bc_ptrs[0]++;
336 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
337 *stat = 1;
338 return 0;
339 }
340 }
341 lrecs = be16_to_cpu(left->bb_numrecs);
342 }
343 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
344 tcur = NULL;
345 mp = cur->bc_mp;
346 ASSERT(bno != NULLFSBLOCK);
347 if (lbno != NULLFSBLOCK &&
348 lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
349 rbno = bno;
350 right = block;
351 rbp = bp;
352 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
353 XFS_BMAP_BTREE_REF))) {
354 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
355 goto error0;
356 }
357 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
358 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
359 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
360 goto error0;
361 }
362 } else if (rbno != NULLFSBLOCK &&
363 rrecs + be16_to_cpu(block->bb_numrecs) <=
364 XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
365 lbno = bno;
366 left = block;
367 lbp = bp;
368 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
369 XFS_BMAP_BTREE_REF))) {
370 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
371 goto error0;
372 }
373 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
374 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
375 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
376 goto error0;
377 }
378 lrecs = be16_to_cpu(left->bb_numrecs);
379 } else {
380 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
381 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
382 goto error0;
383 }
384 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
385 *stat = 1;
386 return 0;
387 }
388 numlrecs = be16_to_cpu(left->bb_numrecs);
389 numrrecs = be16_to_cpu(right->bb_numrecs);
390 if (level > 0) {
391 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
392 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
393 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
394 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
395#ifdef DEBUG
396 for (i = 0; i < numrrecs; i++) {
397 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
398 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
399 goto error0;
400 }
401 }
402#endif
403 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
404 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
405 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
406 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
407 } else {
408 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
409 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
410 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
411 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
412 }
413 be16_add_cpu(&left->bb_numrecs, numrrecs);
414 left->bb_rightsib = right->bb_rightsib;
415 xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
416 if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
417 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
418 be64_to_cpu(left->bb_rightsib),
419 0, &rrbp, XFS_BMAP_BTREE_REF))) {
420 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
421 goto error0;
422 }
423 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
424 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
425 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
426 goto error0;
427 }
428 rrblock->bb_leftsib = cpu_to_be64(lbno);
429 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
430 }
431 xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
432 cur->bc_private.b.flist, mp);
433 cur->bc_private.b.ip->i_d.di_nblocks--;
434 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
435 XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
436 XFS_TRANS_DQ_BCOUNT, -1L);
437 xfs_trans_binval(cur->bc_tp, rbp);
438 if (bp != lbp) {
439 cur->bc_bufs[level] = lbp;
440 cur->bc_ptrs[level] += lrecs;
441 cur->bc_ra[level] = 0;
442 } else if ((error = xfs_btree_increment(cur, level + 1, &i))) {
443 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
444 goto error0;
445 }
446 if (level > 0)
447 cur->bc_ptrs[level]--;
448 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
449 *stat = 2;
450 return 0;
451
452error0:
453 if (tcur)
454 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
455 return error;
456}
457
458/*
459 * Log key values from the btree block.
460 */
461STATIC void
462xfs_bmbt_log_keys(
463 xfs_btree_cur_t *cur,
464 xfs_buf_t *bp,
465 int kfirst,
466 int klast)
467{
468 xfs_trans_t *tp;
469
470 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
471 XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
472 tp = cur->bc_tp;
473 if (bp) {
474 xfs_bmbt_block_t *block;
475 int first;
476 xfs_bmbt_key_t *kp;
477 int last;
478
479 block = XFS_BUF_TO_BMBT_BLOCK(bp);
480 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
481 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
482 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
483 xfs_trans_log_buf(tp, bp, first, last);
484 } else {
485 xfs_inode_t *ip;
486
487 ip = cur->bc_private.b.ip;
488 xfs_trans_log_inode(tp, ip,
489 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
490 }
491 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
492}
493
494/*
495 * Log pointer values from the btree block.
496 */
497STATIC void
498xfs_bmbt_log_ptrs(
499 xfs_btree_cur_t *cur,
500 xfs_buf_t *bp,
501 int pfirst,
502 int plast)
503{
504 xfs_trans_t *tp;
505
506 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
507 XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
508 tp = cur->bc_tp;
509 if (bp) {
510 xfs_bmbt_block_t *block;
511 int first;
512 int last;
513 xfs_bmbt_ptr_t *pp;
514
515 block = XFS_BUF_TO_BMBT_BLOCK(bp);
516 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
517 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
518 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
519 xfs_trans_log_buf(tp, bp, first, last);
520 } else {
521 xfs_inode_t *ip;
522
523 ip = cur->bc_private.b.ip;
524 xfs_trans_log_inode(tp, ip,
525 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
526 }
527 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
528}
529
530/* 75/*
531 * Determine the extent state. 76 * Determine the extent state.
532 */ 77 */
@@ -576,42 +121,6 @@ xfs_bmdr_to_bmbt(
576} 121}
577 122
578/* 123/*
579 * Delete the record pointed to by cur.
580 */
581int /* error */
582xfs_bmbt_delete(
583 xfs_btree_cur_t *cur,
584 int *stat) /* success/failure */
585{
586 int error; /* error return value */
587 int i;
588 int level;
589
590 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
591 for (level = 0, i = 2; i == 2; level++) {
592 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
593 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
594 return error;
595 }
596 }
597 if (i == 0) {
598 for (level = 1; level < cur->bc_nlevels; level++) {
599 if (cur->bc_ptrs[level] == 0) {
600 if ((error = xfs_btree_decrement(cur, level,
601 &i))) {
602 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
603 return error;
604 }
605 break;
606 }
607 }
608 }
609 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
610 *stat = i;
611 return 0;
612}
613
614/*
615 * Convert a compressed bmap extent record to an uncompressed form. 124 * Convert a compressed bmap extent record to an uncompressed form.
616 * This code must be in sync with the routines xfs_bmbt_get_startoff, 125 * This code must be in sync with the routines xfs_bmbt_get_startoff,
617 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state. 126 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
@@ -665,31 +174,6 @@ xfs_bmbt_get_all(
665} 174}
666 175
667/* 176/*
668 * Get the block pointer for the given level of the cursor.
669 * Fill in the buffer pointer, if applicable.
670 */
671xfs_bmbt_block_t *
672xfs_bmbt_get_block(
673 xfs_btree_cur_t *cur,
674 int level,
675 xfs_buf_t **bpp)
676{
677 xfs_ifork_t *ifp;
678 xfs_bmbt_block_t *rval;
679
680 if (level < cur->bc_nlevels - 1) {
681 *bpp = cur->bc_bufs[level];
682 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
683 } else {
684 *bpp = NULL;
685 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
686 cur->bc_private.b.whichfork);
687 rval = ifp->if_broot;
688 }
689 return rval;
690}
691
692/*
693 * Extract the blockcount field from an in memory bmap extent record. 177 * Extract the blockcount field from an in memory bmap extent record.
694 */ 178 */
695xfs_filblks_t 179xfs_filblks_t
@@ -1226,6 +710,14 @@ xfs_bmbt_free_block(
1226} 710}
1227 711
1228STATIC int 712STATIC int
713xfs_bmbt_get_minrecs(
714 struct xfs_btree_cur *cur,
715 int level)
716{
717 return XFS_BMAP_BLOCK_IMINRECS(level, cur);
718}
719
720STATIC int
1229xfs_bmbt_get_maxrecs( 721xfs_bmbt_get_maxrecs(
1230 struct xfs_btree_cur *cur, 722 struct xfs_btree_cur *cur,
1231 int level) 723 int level)
@@ -1389,6 +881,7 @@ static const struct xfs_btree_ops xfs_bmbt_ops = {
1389 .alloc_block = xfs_bmbt_alloc_block, 881 .alloc_block = xfs_bmbt_alloc_block,
1390 .free_block = xfs_bmbt_free_block, 882 .free_block = xfs_bmbt_free_block,
1391 .get_maxrecs = xfs_bmbt_get_maxrecs, 883 .get_maxrecs = xfs_bmbt_get_maxrecs,
884 .get_minrecs = xfs_bmbt_get_minrecs,
1392 .get_dmaxrecs = xfs_bmbt_get_dmaxrecs, 885 .get_dmaxrecs = xfs_bmbt_get_dmaxrecs,
1393 .init_key_from_rec = xfs_bmbt_init_key_from_rec, 886 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
1394 .init_rec_from_key = xfs_bmbt_init_rec_from_key, 887 .init_rec_from_key = xfs_bmbt_init_rec_from_key,
diff --git a/fs/xfs/xfs_bmap_btree.h b/fs/xfs/xfs_bmap_btree.h
index 703fe2e34347..952ab395f79c 100644
--- a/fs/xfs/xfs_bmap_btree.h
+++ b/fs/xfs/xfs_bmap_btree.h
@@ -237,10 +237,7 @@ typedef struct xfs_btree_lblock xfs_bmbt_block_t;
237 * Prototypes for xfs_bmap.c to call. 237 * Prototypes for xfs_bmap.c to call.
238 */ 238 */
239extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t *, int, xfs_bmbt_block_t *, int); 239extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t *, int, xfs_bmbt_block_t *, int);
240extern int xfs_bmbt_delete(struct xfs_btree_cur *, int *);
241extern void xfs_bmbt_get_all(xfs_bmbt_rec_host_t *r, xfs_bmbt_irec_t *s); 240extern void xfs_bmbt_get_all(xfs_bmbt_rec_host_t *r, xfs_bmbt_irec_t *s);
242extern xfs_bmbt_block_t *xfs_bmbt_get_block(struct xfs_btree_cur *cur,
243 int, struct xfs_buf **bpp);
244extern xfs_filblks_t xfs_bmbt_get_blockcount(xfs_bmbt_rec_host_t *r); 241extern xfs_filblks_t xfs_bmbt_get_blockcount(xfs_bmbt_rec_host_t *r);
245extern xfs_fsblock_t xfs_bmbt_get_startblock(xfs_bmbt_rec_host_t *r); 242extern xfs_fsblock_t xfs_bmbt_get_startblock(xfs_bmbt_rec_host_t *r);
246extern xfs_fileoff_t xfs_bmbt_get_startoff(xfs_bmbt_rec_host_t *r); 243extern xfs_fileoff_t xfs_bmbt_get_startoff(xfs_bmbt_rec_host_t *r);
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 75a8a7b00dfb..28cc76818343 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -3171,3 +3171,596 @@ out0:
3171 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 3171 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3172 return 0; 3172 return 0;
3173} 3173}
3174
3175STATIC int
3176xfs_btree_dec_cursor(
3177 struct xfs_btree_cur *cur,
3178 int level,
3179 int *stat)
3180{
3181 int error;
3182 int i;
3183
3184 if (level > 0) {
3185 error = xfs_btree_decrement(cur, level, &i);
3186 if (error)
3187 return error;
3188 }
3189
3190 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3191 *stat = 1;
3192 return 0;
3193}
3194
3195/*
3196 * Single level of the btree record deletion routine.
3197 * Delete record pointed to by cur/level.
3198 * Remove the record from its block then rebalance the tree.
3199 * Return 0 for error, 1 for done, 2 to go on to the next level.
3200 */
3201STATIC int /* error */
3202xfs_btree_delrec(
3203 struct xfs_btree_cur *cur, /* btree cursor */
3204 int level, /* level removing record from */
3205 int *stat) /* fail/done/go-on */
3206{
3207 struct xfs_btree_block *block; /* btree block */
3208 union xfs_btree_ptr cptr; /* current block ptr */
3209 struct xfs_buf *bp; /* buffer for block */
3210 int error; /* error return value */
3211 int i; /* loop counter */
3212 union xfs_btree_key key; /* storage for keyp */
3213 union xfs_btree_key *keyp = &key; /* passed to the next level */
3214 union xfs_btree_ptr lptr; /* left sibling block ptr */
3215 struct xfs_buf *lbp; /* left buffer pointer */
3216 struct xfs_btree_block *left; /* left btree block */
3217 int lrecs = 0; /* left record count */
3218 int ptr; /* key/record index */
3219 union xfs_btree_ptr rptr; /* right sibling block ptr */
3220 struct xfs_buf *rbp; /* right buffer pointer */
3221 struct xfs_btree_block *right; /* right btree block */
3222 struct xfs_btree_block *rrblock; /* right-right btree block */
3223 struct xfs_buf *rrbp; /* right-right buffer pointer */
3224 int rrecs = 0; /* right record count */
3225 struct xfs_btree_cur *tcur; /* temporary btree cursor */
3226 int numrecs; /* temporary numrec count */
3227
3228 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3229 XFS_BTREE_TRACE_ARGI(cur, level);
3230
3231 tcur = NULL;
3232
3233 /* Get the index of the entry being deleted, check for nothing there. */
3234 ptr = cur->bc_ptrs[level];
3235 if (ptr == 0) {
3236 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3237 *stat = 0;
3238 return 0;
3239 }
3240
3241 /* Get the buffer & block containing the record or key/ptr. */
3242 block = xfs_btree_get_block(cur, level, &bp);
3243 numrecs = xfs_btree_get_numrecs(block);
3244
3245#ifdef DEBUG
3246 error = xfs_btree_check_block(cur, block, level, bp);
3247 if (error)
3248 goto error0;
3249#endif
3250
3251 /* Fail if we're off the end of the block. */
3252 if (ptr > numrecs) {
3253 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3254 *stat = 0;
3255 return 0;
3256 }
3257
3258 XFS_BTREE_STATS_INC(cur, delrec);
3259 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3260
3261 /* Excise the entries being deleted. */
3262 if (level > 0) {
3263 /* It's a nonleaf. operate on keys and ptrs */
3264 union xfs_btree_key *lkp;
3265 union xfs_btree_ptr *lpp;
3266
3267 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3268 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3269
3270#ifdef DEBUG
3271 for (i = 0; i < numrecs - ptr; i++) {
3272 error = xfs_btree_check_ptr(cur, lpp, i, level);
3273 if (error)
3274 goto error0;
3275 }
3276#endif
3277
3278 if (ptr < numrecs) {
3279 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3280 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3281 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3282 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3283 }
3284
3285 /*
3286 * If it's the first record in the block, we'll need to pass a
3287 * key up to the next level (updkey).
3288 */
3289 if (ptr == 1)
3290 keyp = xfs_btree_key_addr(cur, 1, block);
3291 } else {
3292 /* It's a leaf. operate on records */
3293 if (ptr < numrecs) {
3294 xfs_btree_shift_recs(cur,
3295 xfs_btree_rec_addr(cur, ptr + 1, block),
3296 -1, numrecs - ptr);
3297 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3298 }
3299
3300 /*
3301 * If it's the first record in the block, we'll need a key
3302 * structure to pass up to the next level (updkey).
3303 */
3304 if (ptr == 1) {
3305 cur->bc_ops->init_key_from_rec(&key,
3306 xfs_btree_rec_addr(cur, 1, block));
3307 keyp = &key;
3308 }
3309 }
3310
3311 /*
3312 * Decrement and log the number of entries in the block.
3313 */
3314 xfs_btree_set_numrecs(block, --numrecs);
3315 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3316
3317 /*
3318 * If we are tracking the last record in the tree and
3319 * we are at the far right edge of the tree, update it.
3320 */
3321 if (xfs_btree_is_lastrec(cur, block, level)) {
3322 cur->bc_ops->update_lastrec(cur, block, NULL,
3323 ptr, LASTREC_DELREC);
3324 }
3325
3326 /*
3327 * We're at the root level. First, shrink the root block in-memory.
3328 * Try to get rid of the next level down. If we can't then there's
3329 * nothing left to do.
3330 */
3331 if (level == cur->bc_nlevels - 1) {
3332 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3333 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
3334 cur->bc_private.b.whichfork);
3335
3336 error = xfs_btree_kill_iroot(cur);
3337 if (error)
3338 goto error0;
3339
3340 error = xfs_btree_dec_cursor(cur, level, stat);
3341 if (error)
3342 goto error0;
3343 *stat = 1;
3344 return 0;
3345 }
3346
3347 /*
3348 * If this is the root level, and there's only one entry left,
3349 * and it's NOT the leaf level, then we can get rid of this
3350 * level.
3351 */
3352 if (numrecs == 1 && level > 0) {
3353 union xfs_btree_ptr *pp;
3354 /*
3355 * pp is still set to the first pointer in the block.
3356 * Make it the new root of the btree.
3357 */
3358 pp = xfs_btree_ptr_addr(cur, 1, block);
3359 error = cur->bc_ops->kill_root(cur, bp, level, pp);
3360 if (error)
3361 goto error0;
3362 } else if (level > 0) {
3363 error = xfs_btree_dec_cursor(cur, level, stat);
3364 if (error)
3365 goto error0;
3366 }
3367 *stat = 1;
3368 return 0;
3369 }
3370
3371 /*
3372 * If we deleted the leftmost entry in the block, update the
3373 * key values above us in the tree.
3374 */
3375 if (ptr == 1) {
3376 error = xfs_btree_updkey(cur, keyp, level + 1);
3377 if (error)
3378 goto error0;
3379 }
3380
3381 /*
3382 * If the number of records remaining in the block is at least
3383 * the minimum, we're done.
3384 */
3385 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3386 error = xfs_btree_dec_cursor(cur, level, stat);
3387 if (error)
3388 goto error0;
3389 return 0;
3390 }
3391
3392 /*
3393 * Otherwise, we have to move some records around to keep the
3394 * tree balanced. Look at the left and right sibling blocks to
3395 * see if we can re-balance by moving only one record.
3396 */
3397 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3398 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3399
3400 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3401 /*
3402 * One child of root, need to get a chance to copy its contents
3403 * into the root and delete it. Can't go up to next level,
3404 * there's nothing to delete there.
3405 */
3406 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3407 xfs_btree_ptr_is_null(cur, &lptr) &&
3408 level == cur->bc_nlevels - 2) {
3409 error = xfs_btree_kill_iroot(cur);
3410 if (!error)
3411 error = xfs_btree_dec_cursor(cur, level, stat);
3412 if (error)
3413 goto error0;
3414 return 0;
3415 }
3416 }
3417
3418 ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3419 !xfs_btree_ptr_is_null(cur, &lptr));
3420
3421 /*
3422 * Duplicate the cursor so our btree manipulations here won't
3423 * disrupt the next level up.
3424 */
3425 error = xfs_btree_dup_cursor(cur, &tcur);
3426 if (error)
3427 goto error0;
3428
3429 /*
3430 * If there's a right sibling, see if it's ok to shift an entry
3431 * out of it.
3432 */
3433 if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3434 /*
3435 * Move the temp cursor to the last entry in the next block.
3436 * Actually any entry but the first would suffice.
3437 */
3438 i = xfs_btree_lastrec(tcur, level);
3439 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3440
3441 error = xfs_btree_increment(tcur, level, &i);
3442 if (error)
3443 goto error0;
3444 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3445
3446 i = xfs_btree_lastrec(tcur, level);
3447 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3448
3449 /* Grab a pointer to the block. */
3450 right = xfs_btree_get_block(tcur, level, &rbp);
3451#ifdef DEBUG
3452 error = xfs_btree_check_block(tcur, right, level, rbp);
3453 if (error)
3454 goto error0;
3455#endif
3456 /* Grab the current block number, for future use. */
3457 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3458
3459 /*
3460 * If right block is full enough so that removing one entry
3461 * won't make it too empty, and left-shifting an entry out
3462 * of right to us works, we're done.
3463 */
3464 if (xfs_btree_get_numrecs(right) - 1 >=
3465 cur->bc_ops->get_minrecs(tcur, level)) {
3466 error = xfs_btree_lshift(tcur, level, &i);
3467 if (error)
3468 goto error0;
3469 if (i) {
3470 ASSERT(xfs_btree_get_numrecs(block) >=
3471 cur->bc_ops->get_minrecs(tcur, level));
3472
3473 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3474 tcur = NULL;
3475
3476 error = xfs_btree_dec_cursor(cur, level, stat);
3477 if (error)
3478 goto error0;
3479 return 0;
3480 }
3481 }
3482
3483 /*
3484 * Otherwise, grab the number of records in right for
3485 * future reference, and fix up the temp cursor to point
3486 * to our block again (last record).
3487 */
3488 rrecs = xfs_btree_get_numrecs(right);
3489 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3490 i = xfs_btree_firstrec(tcur, level);
3491 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3492
3493 error = xfs_btree_decrement(tcur, level, &i);
3494 if (error)
3495 goto error0;
3496 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3497 }
3498 }
3499
3500 /*
3501 * If there's a left sibling, see if it's ok to shift an entry
3502 * out of it.
3503 */
3504 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3505 /*
3506 * Move the temp cursor to the first entry in the
3507 * previous block.
3508 */
3509 i = xfs_btree_firstrec(tcur, level);
3510 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3511
3512 error = xfs_btree_decrement(tcur, level, &i);
3513 if (error)
3514 goto error0;
3515 i = xfs_btree_firstrec(tcur, level);
3516 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3517
3518 /* Grab a pointer to the block. */
3519 left = xfs_btree_get_block(tcur, level, &lbp);
3520#ifdef DEBUG
3521 error = xfs_btree_check_block(cur, left, level, lbp);
3522 if (error)
3523 goto error0;
3524#endif
3525 /* Grab the current block number, for future use. */
3526 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
3527
3528 /*
3529 * If left block is full enough so that removing one entry
3530 * won't make it too empty, and right-shifting an entry out
3531 * of left to us works, we're done.
3532 */
3533 if (xfs_btree_get_numrecs(left) - 1 >=
3534 cur->bc_ops->get_minrecs(tcur, level)) {
3535 error = xfs_btree_rshift(tcur, level, &i);
3536 if (error)
3537 goto error0;
3538 if (i) {
3539 ASSERT(xfs_btree_get_numrecs(block) >=
3540 cur->bc_ops->get_minrecs(tcur, level));
3541 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3542 tcur = NULL;
3543 if (level == 0)
3544 cur->bc_ptrs[0]++;
3545 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3546 *stat = 1;
3547 return 0;
3548 }
3549 }
3550
3551 /*
3552 * Otherwise, grab the number of records in right for
3553 * future reference.
3554 */
3555 lrecs = xfs_btree_get_numrecs(left);
3556 }
3557
3558 /* Delete the temp cursor, we're done with it. */
3559 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3560 tcur = NULL;
3561
3562 /* If here, we need to do a join to keep the tree balanced. */
3563 ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
3564
3565 if (!xfs_btree_ptr_is_null(cur, &lptr) &&
3566 lrecs + xfs_btree_get_numrecs(block) <=
3567 cur->bc_ops->get_maxrecs(cur, level)) {
3568 /*
3569 * Set "right" to be the starting block,
3570 * "left" to be the left neighbor.
3571 */
3572 rptr = cptr;
3573 right = block;
3574 rbp = bp;
3575 error = xfs_btree_read_buf_block(cur, &lptr, level,
3576 0, &left, &lbp);
3577 if (error)
3578 goto error0;
3579
3580 /*
3581 * If that won't work, see if we can join with the right neighbor block.
3582 */
3583 } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
3584 rrecs + xfs_btree_get_numrecs(block) <=
3585 cur->bc_ops->get_maxrecs(cur, level)) {
3586 /*
3587 * Set "left" to be the starting block,
3588 * "right" to be the right neighbor.
3589 */
3590 lptr = cptr;
3591 left = block;
3592 lbp = bp;
3593 error = xfs_btree_read_buf_block(cur, &rptr, level,
3594 0, &right, &rbp);
3595 if (error)
3596 goto error0;
3597
3598 /*
3599 * Otherwise, we can't fix the imbalance.
3600 * Just return. This is probably a logic error, but it's not fatal.
3601 */
3602 } else {
3603 error = xfs_btree_dec_cursor(cur, level, stat);
3604 if (error)
3605 goto error0;
3606 return 0;
3607 }
3608
3609 rrecs = xfs_btree_get_numrecs(right);
3610 lrecs = xfs_btree_get_numrecs(left);
3611
3612 /*
3613 * We're now going to join "left" and "right" by moving all the stuff
3614 * in "right" to "left" and deleting "right".
3615 */
3616 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
3617 if (level > 0) {
3618 /* It's a non-leaf. Move keys and pointers. */
3619 union xfs_btree_key *lkp; /* left btree key */
3620 union xfs_btree_ptr *lpp; /* left address pointer */
3621 union xfs_btree_key *rkp; /* right btree key */
3622 union xfs_btree_ptr *rpp; /* right address pointer */
3623
3624 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
3625 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
3626 rkp = xfs_btree_key_addr(cur, 1, right);
3627 rpp = xfs_btree_ptr_addr(cur, 1, right);
3628#ifdef DEBUG
3629 for (i = 1; i < rrecs; i++) {
3630 error = xfs_btree_check_ptr(cur, rpp, i, level);
3631 if (error)
3632 goto error0;
3633 }
3634#endif
3635 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
3636 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
3637
3638 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
3639 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
3640 } else {
3641 /* It's a leaf. Move records. */
3642 union xfs_btree_rec *lrp; /* left record pointer */
3643 union xfs_btree_rec *rrp; /* right record pointer */
3644
3645 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
3646 rrp = xfs_btree_rec_addr(cur, 1, right);
3647
3648 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
3649 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
3650 }
3651
3652 XFS_BTREE_STATS_INC(cur, join);
3653
3654 /*
3655 * Fix up the the number of records and right block pointer in the
3656 * surviving block, and log it.
3657 */
3658 xfs_btree_set_numrecs(left, lrecs + rrecs);
3659 xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB),
3660 xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3661 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
3662
3663 /* If there is a right sibling, point it to the remaining block. */
3664 xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3665 if (!xfs_btree_ptr_is_null(cur, &cptr)) {
3666 error = xfs_btree_read_buf_block(cur, &cptr, level,
3667 0, &rrblock, &rrbp);
3668 if (error)
3669 goto error0;
3670 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
3671 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
3672 }
3673
3674 /* Free the deleted block. */
3675 error = cur->bc_ops->free_block(cur, rbp);
3676 if (error)
3677 goto error0;
3678 XFS_BTREE_STATS_INC(cur, free);
3679
3680 /*
3681 * If we joined with the left neighbor, set the buffer in the
3682 * cursor to the left block, and fix up the index.
3683 */
3684 if (bp != lbp) {
3685 cur->bc_bufs[level] = lbp;
3686 cur->bc_ptrs[level] += lrecs;
3687 cur->bc_ra[level] = 0;
3688 }
3689 /*
3690 * If we joined with the right neighbor and there's a level above
3691 * us, increment the cursor at that level.
3692 */
3693 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
3694 (level + 1 < cur->bc_nlevels)) {
3695 error = xfs_btree_increment(cur, level + 1, &i);
3696 if (error)
3697 goto error0;
3698 }
3699
3700 /*
3701 * Readjust the ptr at this level if it's not a leaf, since it's
3702 * still pointing at the deletion point, which makes the cursor
3703 * inconsistent. If this makes the ptr 0, the caller fixes it up.
3704 * We can't use decrement because it would change the next level up.
3705 */
3706 if (level > 0)
3707 cur->bc_ptrs[level]--;
3708
3709 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3710 /* Return value means the next level up has something to do. */
3711 *stat = 2;
3712 return 0;
3713
3714error0:
3715 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3716 if (tcur)
3717 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
3718 return error;
3719}
3720
3721/*
3722 * Delete the record pointed to by cur.
3723 * The cursor refers to the place where the record was (could be inserted)
3724 * when the operation returns.
3725 */
3726int /* error */
3727xfs_btree_delete(
3728 struct xfs_btree_cur *cur,
3729 int *stat) /* success/failure */
3730{
3731 int error; /* error return value */
3732 int level;
3733 int i;
3734
3735 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3736
3737 /*
3738 * Go up the tree, starting at leaf level.
3739 *
3740 * If 2 is returned then a join was done; go to the next level.
3741 * Otherwise we are done.
3742 */
3743 for (level = 0, i = 2; i == 2; level++) {
3744 error = xfs_btree_delrec(cur, level, &i);
3745 if (error)
3746 goto error0;
3747 }
3748
3749 if (i == 0) {
3750 for (level = 1; level < cur->bc_nlevels; level++) {
3751 if (cur->bc_ptrs[level] == 0) {
3752 error = xfs_btree_decrement(cur, level, &i);
3753 if (error)
3754 goto error0;
3755 break;
3756 }
3757 }
3758 }
3759
3760 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3761 *stat = i;
3762 return 0;
3763error0:
3764 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3765 return error;
3766}
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index ff2552febba7..06ef792e0aac 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -192,6 +192,8 @@ struct xfs_btree_ops {
192 /* update btree root pointer */ 192 /* update btree root pointer */
193 void (*set_root)(struct xfs_btree_cur *cur, 193 void (*set_root)(struct xfs_btree_cur *cur,
194 union xfs_btree_ptr *nptr, int level_change); 194 union xfs_btree_ptr *nptr, int level_change);
195 int (*kill_root)(struct xfs_btree_cur *cur, struct xfs_buf *bp,
196 int level, union xfs_btree_ptr *newroot);
195 197
196 /* block allocation / freeing */ 198 /* block allocation / freeing */
197 int (*alloc_block)(struct xfs_btree_cur *cur, 199 int (*alloc_block)(struct xfs_btree_cur *cur,
@@ -207,6 +209,7 @@ struct xfs_btree_ops {
207 int ptr, int reason); 209 int ptr, int reason);
208 210
209 /* records in block/level */ 211 /* records in block/level */
212 int (*get_minrecs)(struct xfs_btree_cur *cur, int level);
210 int (*get_maxrecs)(struct xfs_btree_cur *cur, int level); 213 int (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
211 214
212 /* records on disk. Matter for the root in inode case. */ 215 /* records on disk. Matter for the root in inode case. */
@@ -251,6 +254,7 @@ struct xfs_btree_ops {
251 */ 254 */
252#define LASTREC_UPDATE 0 255#define LASTREC_UPDATE 0
253#define LASTREC_INSREC 1 256#define LASTREC_INSREC 1
257#define LASTREC_DELREC 2
254 258
255 259
256/* 260/*
@@ -562,6 +566,7 @@ int xfs_btree_new_root(struct xfs_btree_cur *, int *);
562int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *); 566int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
563int xfs_btree_kill_iroot(struct xfs_btree_cur *); 567int xfs_btree_kill_iroot(struct xfs_btree_cur *);
564int xfs_btree_insert(struct xfs_btree_cur *, int *); 568int xfs_btree_insert(struct xfs_btree_cur *, int *);
569int xfs_btree_delete(struct xfs_btree_cur *, int *);
565 570
566/* 571/*
567 * Helpers. 572 * Helpers.
diff --git a/fs/xfs/xfs_ialloc.c b/fs/xfs/xfs_ialloc.c
index b68e73bb17cd..f13f59b13cc8 100644
--- a/fs/xfs/xfs_ialloc.c
+++ b/fs/xfs/xfs_ialloc.c
@@ -1168,8 +1168,8 @@ xfs_difree(
1168 xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen); 1168 xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
1169 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1)); 1169 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
1170 1170
1171 if ((error = xfs_inobt_delete(cur, &i))) { 1171 if ((error = xfs_btree_delete(cur, &i))) {
1172 cmn_err(CE_WARN, "xfs_difree: xfs_inobt_delete returned an error %d on %s.\n", 1172 cmn_err(CE_WARN, "xfs_difree: xfs_btree_delete returned an error %d on %s.\n",
1173 error, mp->m_fsname); 1173 error, mp->m_fsname);
1174 goto error0; 1174 goto error0;
1175 } 1175 }
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index 90f1d4ee7720..6c0a07d1fed3 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -40,611 +40,6 @@
40#include "xfs_alloc.h" 40#include "xfs_alloc.h"
41#include "xfs_error.h" 41#include "xfs_error.h"
42 42
43STATIC void xfs_inobt_log_block(xfs_trans_t *, xfs_buf_t *, int);
44STATIC void xfs_inobt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
45STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
46STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
47
48/*
49 * Single level of the xfs_inobt_delete record deletion routine.
50 * Delete record pointed to by cur/level.
51 * Remove the record from its block then rebalance the tree.
52 * Return 0 for error, 1 for done, 2 to go on to the next level.
53 */
54STATIC int /* error */
55xfs_inobt_delrec(
56 xfs_btree_cur_t *cur, /* btree cursor */
57 int level, /* level removing record from */
58 int *stat) /* fail/done/go-on */
59{
60 xfs_buf_t *agbp; /* buffer for a.g. inode header */
61 xfs_mount_t *mp; /* mount structure */
62 xfs_agi_t *agi; /* allocation group inode header */
63 xfs_inobt_block_t *block; /* btree block record/key lives in */
64 xfs_agblock_t bno; /* btree block number */
65 xfs_buf_t *bp; /* buffer for block */
66 int error; /* error return value */
67 int i; /* loop index */
68 xfs_inobt_key_t key; /* kp points here if block is level 0 */
69 xfs_inobt_key_t *kp = NULL; /* pointer to btree keys */
70 xfs_agblock_t lbno; /* left block's block number */
71 xfs_buf_t *lbp; /* left block's buffer pointer */
72 xfs_inobt_block_t *left; /* left btree block */
73 xfs_inobt_key_t *lkp; /* left block key pointer */
74 xfs_inobt_ptr_t *lpp; /* left block address pointer */
75 int lrecs = 0; /* number of records in left block */
76 xfs_inobt_rec_t *lrp; /* left block record pointer */
77 xfs_inobt_ptr_t *pp = NULL; /* pointer to btree addresses */
78 int ptr; /* index in btree block for this rec */
79 xfs_agblock_t rbno; /* right block's block number */
80 xfs_buf_t *rbp; /* right block's buffer pointer */
81 xfs_inobt_block_t *right; /* right btree block */
82 xfs_inobt_key_t *rkp; /* right block key pointer */
83 xfs_inobt_rec_t *rp; /* pointer to btree records */
84 xfs_inobt_ptr_t *rpp; /* right block address pointer */
85 int rrecs = 0; /* number of records in right block */
86 int numrecs;
87 xfs_inobt_rec_t *rrp; /* right block record pointer */
88 xfs_btree_cur_t *tcur; /* temporary btree cursor */
89
90 mp = cur->bc_mp;
91
92 /*
93 * Get the index of the entry being deleted, check for nothing there.
94 */
95 ptr = cur->bc_ptrs[level];
96 if (ptr == 0) {
97 *stat = 0;
98 return 0;
99 }
100
101 /*
102 * Get the buffer & block containing the record or key/ptr.
103 */
104 bp = cur->bc_bufs[level];
105 block = XFS_BUF_TO_INOBT_BLOCK(bp);
106#ifdef DEBUG
107 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
108 return error;
109#endif
110 /*
111 * Fail if we're off the end of the block.
112 */
113
114 numrecs = be16_to_cpu(block->bb_numrecs);
115 if (ptr > numrecs) {
116 *stat = 0;
117 return 0;
118 }
119 /*
120 * It's a nonleaf. Excise the key and ptr being deleted, by
121 * sliding the entries past them down one.
122 * Log the changed areas of the block.
123 */
124 if (level > 0) {
125 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
126 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
127#ifdef DEBUG
128 for (i = ptr; i < numrecs; i++) {
129 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i]), level)))
130 return error;
131 }
132#endif
133 if (ptr < numrecs) {
134 memmove(&kp[ptr - 1], &kp[ptr],
135 (numrecs - ptr) * sizeof(*kp));
136 memmove(&pp[ptr - 1], &pp[ptr],
137 (numrecs - ptr) * sizeof(*kp));
138 xfs_inobt_log_keys(cur, bp, ptr, numrecs - 1);
139 xfs_inobt_log_ptrs(cur, bp, ptr, numrecs - 1);
140 }
141 }
142 /*
143 * It's a leaf. Excise the record being deleted, by sliding the
144 * entries past it down one. Log the changed areas of the block.
145 */
146 else {
147 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
148 if (ptr < numrecs) {
149 memmove(&rp[ptr - 1], &rp[ptr],
150 (numrecs - ptr) * sizeof(*rp));
151 xfs_inobt_log_recs(cur, bp, ptr, numrecs - 1);
152 }
153 /*
154 * If it's the first record in the block, we'll need a key
155 * structure to pass up to the next level (updkey).
156 */
157 if (ptr == 1) {
158 key.ir_startino = rp->ir_startino;
159 kp = &key;
160 }
161 }
162 /*
163 * Decrement and log the number of entries in the block.
164 */
165 numrecs--;
166 block->bb_numrecs = cpu_to_be16(numrecs);
167 xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
168 /*
169 * Is this the root level? If so, we're almost done.
170 */
171 if (level == cur->bc_nlevels - 1) {
172 /*
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.
177 */
178 if (numrecs == 1 && level > 0) {
179 agbp = cur->bc_private.a.agbp;
180 agi = XFS_BUF_TO_AGI(agbp);
181 /*
182 * pp is still set to the first pointer in the block.
183 * Make it the new root of the btree.
184 */
185 bno = be32_to_cpu(agi->agi_root);
186 agi->agi_root = *pp;
187 be32_add_cpu(&agi->agi_level, -1);
188 /*
189 * Free the block.
190 */
191 if ((error = xfs_free_extent(cur->bc_tp,
192 XFS_AGB_TO_FSB(mp, cur->bc_private.a.agno, bno), 1)))
193 return error;
194 xfs_trans_binval(cur->bc_tp, bp);
195 xfs_ialloc_log_agi(cur->bc_tp, agbp,
196 XFS_AGI_ROOT | XFS_AGI_LEVEL);
197 /*
198 * Update the cursor so there's one fewer level.
199 */
200 cur->bc_bufs[level] = NULL;
201 cur->bc_nlevels--;
202 } else if (level > 0 &&
203 (error = xfs_btree_decrement(cur, level, &i)))
204 return error;
205 *stat = 1;
206 return 0;
207 }
208 /*
209 * If we deleted the leftmost entry in the block, update the
210 * key values above us in the tree.
211 */
212 if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)kp, level + 1)))
213 return error;
214 /*
215 * If the number of records remaining in the block is at least
216 * the minimum, we're done.
217 */
218 if (numrecs >= XFS_INOBT_BLOCK_MINRECS(level, cur)) {
219 if (level > 0 &&
220 (error = xfs_btree_decrement(cur, level, &i)))
221 return error;
222 *stat = 1;
223 return 0;
224 }
225 /*
226 * Otherwise, we have to move some records around to keep the
227 * tree balanced. Look at the left and right sibling blocks to
228 * see if we can re-balance by moving only one record.
229 */
230 rbno = be32_to_cpu(block->bb_rightsib);
231 lbno = be32_to_cpu(block->bb_leftsib);
232 bno = NULLAGBLOCK;
233 ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
234 /*
235 * Duplicate the cursor so our btree manipulations here won't
236 * disrupt the next level up.
237 */
238 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
239 return error;
240 /*
241 * If there's a right sibling, see if it's ok to shift an entry
242 * out of it.
243 */
244 if (rbno != NULLAGBLOCK) {
245 /*
246 * Move the temp cursor to the last entry in the next block.
247 * Actually any entry but the first would suffice.
248 */
249 i = xfs_btree_lastrec(tcur, level);
250 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
251 if ((error = xfs_btree_increment(tcur, level, &i)))
252 goto error0;
253 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
254 i = xfs_btree_lastrec(tcur, level);
255 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
256 /*
257 * Grab a pointer to the block.
258 */
259 rbp = tcur->bc_bufs[level];
260 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
261#ifdef DEBUG
262 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
263 goto error0;
264#endif
265 /*
266 * Grab the current block number, for future use.
267 */
268 bno = be32_to_cpu(right->bb_leftsib);
269 /*
270 * If right block is full enough so that removing one entry
271 * won't make it too empty, and left-shifting an entry out
272 * of right to us works, we're done.
273 */
274 if (be16_to_cpu(right->bb_numrecs) - 1 >=
275 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
276 if ((error = xfs_btree_lshift(tcur, level, &i)))
277 goto error0;
278 if (i) {
279 ASSERT(be16_to_cpu(block->bb_numrecs) >=
280 XFS_INOBT_BLOCK_MINRECS(level, cur));
281 xfs_btree_del_cursor(tcur,
282 XFS_BTREE_NOERROR);
283 if (level > 0 &&
284 (error = xfs_btree_decrement(cur, level,
285 &i)))
286 return error;
287 *stat = 1;
288 return 0;
289 }
290 }
291 /*
292 * Otherwise, grab the number of records in right for
293 * future reference, and fix up the temp cursor to point
294 * to our block again (last record).
295 */
296 rrecs = be16_to_cpu(right->bb_numrecs);
297 if (lbno != NULLAGBLOCK) {
298 xfs_btree_firstrec(tcur, level);
299 if ((error = xfs_btree_decrement(tcur, level, &i)))
300 goto error0;
301 }
302 }
303 /*
304 * If there's a left sibling, see if it's ok to shift an entry
305 * out of it.
306 */
307 if (lbno != NULLAGBLOCK) {
308 /*
309 * Move the temp cursor to the first entry in the
310 * previous block.
311 */
312 xfs_btree_firstrec(tcur, level);
313 if ((error = xfs_btree_decrement(tcur, level, &i)))
314 goto error0;
315 xfs_btree_firstrec(tcur, level);
316 /*
317 * Grab a pointer to the block.
318 */
319 lbp = tcur->bc_bufs[level];
320 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
321#ifdef DEBUG
322 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
323 goto error0;
324#endif
325 /*
326 * Grab the current block number, for future use.
327 */
328 bno = be32_to_cpu(left->bb_rightsib);
329 /*
330 * If left block is full enough so that removing one entry
331 * won't make it too empty, and right-shifting an entry out
332 * of left to us works, we're done.
333 */
334 if (be16_to_cpu(left->bb_numrecs) - 1 >=
335 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
336 if ((error = xfs_btree_rshift(tcur, level, &i)))
337 goto error0;
338 if (i) {
339 ASSERT(be16_to_cpu(block->bb_numrecs) >=
340 XFS_INOBT_BLOCK_MINRECS(level, cur));
341 xfs_btree_del_cursor(tcur,
342 XFS_BTREE_NOERROR);
343 if (level == 0)
344 cur->bc_ptrs[0]++;
345 *stat = 1;
346 return 0;
347 }
348 }
349 /*
350 * Otherwise, grab the number of records in right for
351 * future reference.
352 */
353 lrecs = be16_to_cpu(left->bb_numrecs);
354 }
355 /*
356 * Delete the temp cursor, we're done with it.
357 */
358 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
359 /*
360 * If here, we need to do a join to keep the tree balanced.
361 */
362 ASSERT(bno != NULLAGBLOCK);
363 /*
364 * See if we can join with the left neighbor block.
365 */
366 if (lbno != NULLAGBLOCK &&
367 lrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
368 /*
369 * Set "right" to be the starting block,
370 * "left" to be the left neighbor.
371 */
372 rbno = bno;
373 right = block;
374 rrecs = be16_to_cpu(right->bb_numrecs);
375 rbp = bp;
376 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
377 cur->bc_private.a.agno, lbno, 0, &lbp,
378 XFS_INO_BTREE_REF)))
379 return error;
380 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
381 lrecs = be16_to_cpu(left->bb_numrecs);
382 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
383 return error;
384 }
385 /*
386 * If that won't work, see if we can join with the right neighbor block.
387 */
388 else if (rbno != NULLAGBLOCK &&
389 rrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
390 /*
391 * Set "left" to be the starting block,
392 * "right" to be the right neighbor.
393 */
394 lbno = bno;
395 left = block;
396 lrecs = be16_to_cpu(left->bb_numrecs);
397 lbp = bp;
398 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
399 cur->bc_private.a.agno, rbno, 0, &rbp,
400 XFS_INO_BTREE_REF)))
401 return error;
402 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
403 rrecs = be16_to_cpu(right->bb_numrecs);
404 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
405 return error;
406 }
407 /*
408 * Otherwise, we can't fix the imbalance.
409 * Just return. This is probably a logic error, but it's not fatal.
410 */
411 else {
412 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i)))
413 return error;
414 *stat = 1;
415 return 0;
416 }
417 /*
418 * We're now going to join "left" and "right" by moving all the stuff
419 * in "right" to "left" and deleting "right".
420 */
421 if (level > 0) {
422 /*
423 * It's a non-leaf. Move keys and pointers.
424 */
425 lkp = XFS_INOBT_KEY_ADDR(left, lrecs + 1, cur);
426 lpp = XFS_INOBT_PTR_ADDR(left, lrecs + 1, cur);
427 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
428 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
429#ifdef DEBUG
430 for (i = 0; i < rrecs; i++) {
431 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
432 return error;
433 }
434#endif
435 memcpy(lkp, rkp, rrecs * sizeof(*lkp));
436 memcpy(lpp, rpp, rrecs * sizeof(*lpp));
437 xfs_inobt_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
438 xfs_inobt_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
439 } else {
440 /*
441 * It's a leaf. Move records.
442 */
443 lrp = XFS_INOBT_REC_ADDR(left, lrecs + 1, cur);
444 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
445 memcpy(lrp, rrp, rrecs * sizeof(*lrp));
446 xfs_inobt_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
447 }
448 /*
449 * If we joined with the left neighbor, set the buffer in the
450 * cursor to the left block, and fix up the index.
451 */
452 if (bp != lbp) {
453 xfs_btree_setbuf(cur, level, lbp);
454 cur->bc_ptrs[level] += lrecs;
455 }
456 /*
457 * If we joined with the right neighbor and there's a level above
458 * us, increment the cursor at that level.
459 */
460 else if (level + 1 < cur->bc_nlevels &&
461 (error = xfs_btree_increment(cur, level + 1, &i)))
462 return error;
463 /*
464 * Fix up the number of records in the surviving block.
465 */
466 lrecs += rrecs;
467 left->bb_numrecs = cpu_to_be16(lrecs);
468 /*
469 * Fix up the right block pointer in the surviving block, and log it.
470 */
471 left->bb_rightsib = right->bb_rightsib;
472 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
473 /*
474 * If there is a right sibling now, make it point to the
475 * remaining block.
476 */
477 if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
478 xfs_inobt_block_t *rrblock;
479 xfs_buf_t *rrbp;
480
481 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
482 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
483 &rrbp, XFS_INO_BTREE_REF)))
484 return error;
485 rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp);
486 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
487 return error;
488 rrblock->bb_leftsib = cpu_to_be32(lbno);
489 xfs_inobt_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
490 }
491 /*
492 * Free the deleting block.
493 */
494 if ((error = xfs_free_extent(cur->bc_tp, XFS_AGB_TO_FSB(mp,
495 cur->bc_private.a.agno, rbno), 1)))
496 return error;
497 xfs_trans_binval(cur->bc_tp, rbp);
498 /*
499 * Readjust the ptr at this level if it's not a leaf, since it's
500 * still pointing at the deletion point, which makes the cursor
501 * inconsistent. If this makes the ptr 0, the caller fixes it up.
502 * We can't use decrement because it would change the next level up.
503 */
504 if (level > 0)
505 cur->bc_ptrs[level]--;
506 /*
507 * Return value means the next level up has something to do.
508 */
509 *stat = 2;
510 return 0;
511
512error0:
513 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
514 return error;
515}
516
517/*
518 * Log header fields from a btree block.
519 */
520STATIC void
521xfs_inobt_log_block(
522 xfs_trans_t *tp, /* transaction pointer */
523 xfs_buf_t *bp, /* buffer containing btree block */
524 int fields) /* mask of fields: XFS_BB_... */
525{
526 int first; /* first byte offset logged */
527 int last; /* last byte offset logged */
528 static const short offsets[] = { /* table of offsets */
529 offsetof(xfs_inobt_block_t, bb_magic),
530 offsetof(xfs_inobt_block_t, bb_level),
531 offsetof(xfs_inobt_block_t, bb_numrecs),
532 offsetof(xfs_inobt_block_t, bb_leftsib),
533 offsetof(xfs_inobt_block_t, bb_rightsib),
534 sizeof(xfs_inobt_block_t)
535 };
536
537 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
538 xfs_trans_log_buf(tp, bp, first, last);
539}
540
541/*
542 * Log keys from a btree block (nonleaf).
543 */
544STATIC void
545xfs_inobt_log_keys(
546 xfs_btree_cur_t *cur, /* btree cursor */
547 xfs_buf_t *bp, /* buffer containing btree block */
548 int kfirst, /* index of first key to log */
549 int klast) /* index of last key to log */
550{
551 xfs_inobt_block_t *block; /* btree block to log from */
552 int first; /* first byte offset logged */
553 xfs_inobt_key_t *kp; /* key pointer in btree block */
554 int last; /* last byte offset logged */
555
556 block = XFS_BUF_TO_INOBT_BLOCK(bp);
557 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
558 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
559 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
560 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
561}
562
563/*
564 * Log block pointer fields from a btree block (nonleaf).
565 */
566STATIC void
567xfs_inobt_log_ptrs(
568 xfs_btree_cur_t *cur, /* btree cursor */
569 xfs_buf_t *bp, /* buffer containing btree block */
570 int pfirst, /* index of first pointer to log */
571 int plast) /* index of last pointer to log */
572{
573 xfs_inobt_block_t *block; /* btree block to log from */
574 int first; /* first byte offset logged */
575 int last; /* last byte offset logged */
576 xfs_inobt_ptr_t *pp; /* block-pointer pointer in btree blk */
577
578 block = XFS_BUF_TO_INOBT_BLOCK(bp);
579 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
580 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
581 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
582 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
583}
584
585/*
586 * Log records from a btree block (leaf).
587 */
588STATIC void
589xfs_inobt_log_recs(
590 xfs_btree_cur_t *cur, /* btree cursor */
591 xfs_buf_t *bp, /* buffer containing btree block */
592 int rfirst, /* index of first record to log */
593 int rlast) /* index of last record to log */
594{
595 xfs_inobt_block_t *block; /* btree block to log from */
596 int first; /* first byte offset logged */
597 int last; /* last byte offset logged */
598 xfs_inobt_rec_t *rp; /* record pointer for btree block */
599
600 block = XFS_BUF_TO_INOBT_BLOCK(bp);
601 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
602 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
603 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
604 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
605}
606
607
608/*
609 * Externally visible routines.
610 */
611
612/*
613 * Delete the record pointed to by cur.
614 * The cursor refers to the place where the record was (could be inserted)
615 * when the operation returns.
616 */
617int /* error */
618xfs_inobt_delete(
619 xfs_btree_cur_t *cur, /* btree cursor */
620 int *stat) /* success/failure */
621{
622 int error;
623 int i; /* result code */
624 int level; /* btree level */
625
626 /*
627 * Go up the tree, starting at leaf level.
628 * If 2 is returned then a join was done; go to the next level.
629 * Otherwise we are done.
630 */
631 for (level = 0, i = 2; i == 2; level++) {
632 if ((error = xfs_inobt_delrec(cur, level, &i)))
633 return error;
634 }
635 if (i == 0) {
636 for (level = 1; level < cur->bc_nlevels; level++) {
637 if (cur->bc_ptrs[level] == 0) {
638 if ((error = xfs_btree_decrement(cur, level, &i)))
639 return error;
640 break;
641 }
642 }
643 }
644 *stat = i;
645 return 0;
646}
647
648 43
649/* 44/*
650 * Get the data from the pointed-to record. 45 * Get the data from the pointed-to record.
@@ -690,6 +85,13 @@ xfs_inobt_get_rec(
690 return 0; 85 return 0;
691} 86}
692 87
88STATIC int
89xfs_inobt_get_minrecs(
90 struct xfs_btree_cur *cur,
91 int level)
92{
93 return cur->bc_mp->m_inobt_mnr[level != 0];
94}
693 95
694STATIC struct xfs_btree_cur * 96STATIC struct xfs_btree_cur *
695xfs_inobt_dup_cursor( 97xfs_inobt_dup_cursor(
@@ -829,6 +231,38 @@ xfs_inobt_key_diff(
829 cur->bc_rec.i.ir_startino; 231 cur->bc_rec.i.ir_startino;
830} 232}
831 233
234STATIC int
235xfs_inobt_kill_root(
236 struct xfs_btree_cur *cur,
237 struct xfs_buf *bp,
238 int level,
239 union xfs_btree_ptr *newroot)
240{
241 int error;
242
243 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
244 XFS_BTREE_STATS_INC(cur, killroot);
245
246 /*
247 * Update the root pointer, decreasing the level by 1 and then
248 * free the old root.
249 */
250 xfs_inobt_set_root(cur, newroot, -1);
251 error = xfs_inobt_free_block(cur, bp);
252 if (error) {
253 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
254 return error;
255 }
256
257 XFS_BTREE_STATS_INC(cur, free);
258
259 cur->bc_bufs[level] = NULL;
260 cur->bc_nlevels--;
261
262 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
263 return 0;
264}
265
832#ifdef XFS_BTREE_TRACE 266#ifdef XFS_BTREE_TRACE
833ktrace_t *xfs_inobt_trace_buf; 267ktrace_t *xfs_inobt_trace_buf;
834 268
@@ -901,8 +335,10 @@ static const struct xfs_btree_ops xfs_inobt_ops = {
901 335
902 .dup_cursor = xfs_inobt_dup_cursor, 336 .dup_cursor = xfs_inobt_dup_cursor,
903 .set_root = xfs_inobt_set_root, 337 .set_root = xfs_inobt_set_root,
338 .kill_root = xfs_inobt_kill_root,
904 .alloc_block = xfs_inobt_alloc_block, 339 .alloc_block = xfs_inobt_alloc_block,
905 .free_block = xfs_inobt_free_block, 340 .free_block = xfs_inobt_free_block,
341 .get_minrecs = xfs_inobt_get_minrecs,
906 .get_maxrecs = xfs_inobt_get_maxrecs, 342 .get_maxrecs = xfs_inobt_get_maxrecs,
907 .init_key_from_rec = xfs_inobt_init_key_from_rec, 343 .init_key_from_rec = xfs_inobt_init_key_from_rec,
908 .init_rec_from_key = xfs_inobt_init_rec_from_key, 344 .init_rec_from_key = xfs_inobt_init_rec_from_key,
diff --git a/fs/xfs/xfs_ialloc_btree.h b/fs/xfs/xfs_ialloc_btree.h
index c9cbc4f2168d..3eff3b6e5fa4 100644
--- a/fs/xfs/xfs_ialloc_btree.h
+++ b/fs/xfs/xfs_ialloc_btree.h
@@ -117,13 +117,6 @@ typedef struct xfs_btree_sblock xfs_inobt_block_t;
117 i, XFS_INOBT_BLOCK_MAXRECS(1, cur))) 117 i, XFS_INOBT_BLOCK_MAXRECS(1, cur)))
118 118
119/* 119/*
120 * Delete the record pointed to by cur.
121 * The cursor refers to the place where the record was (could be inserted)
122 * when the operation returns.
123 */
124extern int xfs_inobt_delete(struct xfs_btree_cur *cur, int *stat);
125
126/*
127 * Get the data from the pointed-to record. 120 * Get the data from the pointed-to record.
128 */ 121 */
129extern int xfs_inobt_get_rec(struct xfs_btree_cur *cur, xfs_agino_t *ino, 122extern int xfs_inobt_get_rec(struct xfs_btree_cur *cur, xfs_agino_t *ino,
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-30 12:28:22 -0500