blob: 74cadf95d4e84de19879cbcfea33e6d41433f9fb [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110019#include "xfs_fs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include "xfs_types.h"
Nathan Scotta844f452005-11-02 14:38:42 +110021#include "xfs_bit.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#include "xfs_log.h"
Nathan Scotta844f452005-11-02 14:38:42 +110023#include "xfs_inum.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include "xfs_trans.h"
25#include "xfs_sb.h"
26#include "xfs_ag.h"
Nathan Scotta844f452005-11-02 14:38:42 +110027#include "xfs_dir2.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070028#include "xfs_dmapi.h"
29#include "xfs_mount.h"
Nathan Scotta844f452005-11-02 14:38:42 +110030#include "xfs_bmap_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include "xfs_alloc_btree.h"
32#include "xfs_ialloc_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110033#include "xfs_dir2_sf.h"
34#include "xfs_attr_sf.h"
35#include "xfs_dinode.h"
36#include "xfs_inode.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include "xfs_btree.h"
38#include "xfs_ialloc.h"
39#include "xfs_alloc.h"
40#include "xfs_error.h"
41
42/*
43 * Prototypes for internal functions.
44 */
45
46STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
47STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
48STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
49STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
50STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
51STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
52STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
53STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
54 xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
55STATIC int xfs_alloc_updkey(xfs_btree_cur_t *, xfs_alloc_key_t *, int);
56
57/*
58 * Internal functions.
59 */
60
61/*
62 * Single level of the xfs_alloc_delete record deletion routine.
63 * Delete record pointed to by cur/level.
64 * Remove the record from its block then rebalance the tree.
65 * Return 0 for error, 1 for done, 2 to go on to the next level.
66 */
67STATIC int /* error */
68xfs_alloc_delrec(
69 xfs_btree_cur_t *cur, /* btree cursor */
70 int level, /* level removing record from */
71 int *stat) /* fail/done/go-on */
72{
73 xfs_agf_t *agf; /* allocation group freelist header */
74 xfs_alloc_block_t *block; /* btree block record/key lives in */
75 xfs_agblock_t bno; /* btree block number */
76 xfs_buf_t *bp; /* buffer for block */
77 int error; /* error return value */
78 int i; /* loop index */
79 xfs_alloc_key_t key; /* kp points here if block is level 0 */
80 xfs_agblock_t lbno; /* left block's block number */
81 xfs_buf_t *lbp; /* left block's buffer pointer */
82 xfs_alloc_block_t *left; /* left btree block */
83 xfs_alloc_key_t *lkp=NULL; /* left block key pointer */
84 xfs_alloc_ptr_t *lpp=NULL; /* left block address pointer */
85 int lrecs=0; /* number of records in left block */
86 xfs_alloc_rec_t *lrp; /* left block record pointer */
87 xfs_mount_t *mp; /* mount structure */
88 int ptr; /* index in btree block for this rec */
89 xfs_agblock_t rbno; /* right block's block number */
90 xfs_buf_t *rbp; /* right block's buffer pointer */
91 xfs_alloc_block_t *right; /* right btree block */
92 xfs_alloc_key_t *rkp; /* right block key pointer */
93 xfs_alloc_ptr_t *rpp; /* right block address pointer */
94 int rrecs=0; /* number of records in right block */
Eric Sandeen91d87232006-09-28 11:05:40 +100095 int numrecs;
Linus Torvalds1da177e2005-04-16 15:20:36 -070096 xfs_alloc_rec_t *rrp; /* right block record pointer */
97 xfs_btree_cur_t *tcur; /* temporary btree cursor */
98
99 /*
100 * Get the index of the entry being deleted, check for nothing there.
101 */
102 ptr = cur->bc_ptrs[level];
103 if (ptr == 0) {
104 *stat = 0;
105 return 0;
106 }
107 /*
108 * Get the buffer & block containing the record or key/ptr.
109 */
110 bp = cur->bc_bufs[level];
111 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
112#ifdef DEBUG
113 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
114 return error;
115#endif
116 /*
117 * Fail if we're off the end of the block.
118 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000119 numrecs = be16_to_cpu(block->bb_numrecs);
120 if (ptr > numrecs) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 *stat = 0;
122 return 0;
123 }
124 XFS_STATS_INC(xs_abt_delrec);
125 /*
126 * It's a nonleaf. Excise the key and ptr being deleted, by
127 * sliding the entries past them down one.
128 * Log the changed areas of the block.
129 */
130 if (level > 0) {
131 lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
132 lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
133#ifdef DEBUG
Eric Sandeen91d87232006-09-28 11:05:40 +1000134 for (i = ptr; i < numrecs; i++) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100135 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 return error;
137 }
138#endif
Eric Sandeen91d87232006-09-28 11:05:40 +1000139 if (ptr < numrecs) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140 memmove(&lkp[ptr - 1], &lkp[ptr],
Eric Sandeen91d87232006-09-28 11:05:40 +1000141 (numrecs - ptr) * sizeof(*lkp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142 memmove(&lpp[ptr - 1], &lpp[ptr],
Eric Sandeen91d87232006-09-28 11:05:40 +1000143 (numrecs - ptr) * sizeof(*lpp));
144 xfs_alloc_log_ptrs(cur, bp, ptr, numrecs - 1);
145 xfs_alloc_log_keys(cur, bp, ptr, numrecs - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146 }
147 }
148 /*
149 * It's a leaf. Excise the record being deleted, by sliding the
150 * entries past it down one. Log the changed areas of the block.
151 */
152 else {
153 lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
Eric Sandeen91d87232006-09-28 11:05:40 +1000154 if (ptr < numrecs) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155 memmove(&lrp[ptr - 1], &lrp[ptr],
Eric Sandeen91d87232006-09-28 11:05:40 +1000156 (numrecs - ptr) * sizeof(*lrp));
157 xfs_alloc_log_recs(cur, bp, ptr, numrecs - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700158 }
159 /*
160 * If it's the first record in the block, we'll need a key
161 * structure to pass up to the next level (updkey).
162 */
163 if (ptr == 1) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100164 key.ar_startblock = lrp->ar_startblock;
165 key.ar_blockcount = lrp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166 lkp = &key;
167 }
168 }
169 /*
170 * Decrement and log the number of entries in the block.
171 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000172 numrecs--;
173 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
175 /*
176 * See if the longest free extent in the allocation group was
177 * changed by this operation. True if it's the by-size btree, and
178 * this is the leaf level, and there is no right sibling block,
179 * and this was the last record.
180 */
181 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
182 mp = cur->bc_mp;
183
184 if (level == 0 &&
185 cur->bc_btnum == XFS_BTNUM_CNT &&
Christoph Hellwig16259e72005-11-02 15:11:25 +1100186 be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
Eric Sandeen91d87232006-09-28 11:05:40 +1000187 ptr > numrecs) {
188 ASSERT(ptr == numrecs + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189 /*
190 * There are still records in the block. Grab the size
191 * from the last one.
192 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000193 if (numrecs) {
194 rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100195 agf->agf_longest = rrp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196 }
197 /*
198 * No free extents left.
199 */
200 else
201 agf->agf_longest = 0;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100202 mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest =
203 be32_to_cpu(agf->agf_longest);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
205 XFS_AGF_LONGEST);
206 }
207 /*
208 * Is this the root level? If so, we're almost done.
209 */
210 if (level == cur->bc_nlevels - 1) {
211 /*
212 * If this is the root level,
213 * and there's only one entry left,
214 * and it's NOT the leaf level,
215 * then we can get rid of this level.
216 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000217 if (numrecs == 1 && level > 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218 /*
219 * lpp is still set to the first pointer in the block.
220 * Make it the new root of the btree.
221 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100222 bno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
223 agf->agf_roots[cur->bc_btnum] = *lpp;
224 be32_add(&agf->agf_levels[cur->bc_btnum], -1);
225 mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_levels[cur->bc_btnum]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226 /*
227 * Put this buffer/block on the ag's freelist.
228 */
229 if ((error = xfs_alloc_put_freelist(cur->bc_tp,
230 cur->bc_private.a.agbp, NULL, bno)))
231 return error;
232 /*
233 * Since blocks move to the free list without the
234 * coordination used in xfs_bmap_finish, we can't allow
235 * block to be available for reallocation and
236 * non-transaction writing (user data) until we know
237 * that the transaction that moved it to the free list
238 * is permanently on disk. We track the blocks by
239 * declaring these blocks as "busy"; the busy list is
240 * maintained on a per-ag basis and each transaction
241 * records which entries should be removed when the
242 * iclog commits to disk. If a busy block is
243 * allocated, the iclog is pushed up to the LSN
244 * that freed the block.
245 */
246 xfs_alloc_mark_busy(cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +1100247 be32_to_cpu(agf->agf_seqno), bno, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248
249 xfs_trans_agbtree_delta(cur->bc_tp, -1);
250 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
251 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
252 /*
253 * Update the cursor so there's one fewer level.
254 */
255 xfs_btree_setbuf(cur, level, NULL);
256 cur->bc_nlevels--;
257 } else if (level > 0 &&
258 (error = xfs_alloc_decrement(cur, level, &i)))
259 return error;
260 *stat = 1;
261 return 0;
262 }
263 /*
264 * If we deleted the leftmost entry in the block, update the
265 * key values above us in the tree.
266 */
267 if (ptr == 1 && (error = xfs_alloc_updkey(cur, lkp, level + 1)))
268 return error;
269 /*
270 * If the number of records remaining in the block is at least
271 * the minimum, we're done.
272 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000273 if (numrecs >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
275 return error;
276 *stat = 1;
277 return 0;
278 }
279 /*
280 * Otherwise, we have to move some records around to keep the
281 * tree balanced. Look at the left and right sibling blocks to
282 * see if we can re-balance by moving only one record.
283 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100284 rbno = be32_to_cpu(block->bb_rightsib);
285 lbno = be32_to_cpu(block->bb_leftsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286 bno = NULLAGBLOCK;
287 ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
288 /*
289 * Duplicate the cursor so our btree manipulations here won't
290 * disrupt the next level up.
291 */
292 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
293 return error;
294 /*
295 * If there's a right sibling, see if it's ok to shift an entry
296 * out of it.
297 */
298 if (rbno != NULLAGBLOCK) {
299 /*
300 * Move the temp cursor to the last entry in the next block.
301 * Actually any entry but the first would suffice.
302 */
303 i = xfs_btree_lastrec(tcur, level);
304 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
305 if ((error = xfs_alloc_increment(tcur, level, &i)))
306 goto error0;
307 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
308 i = xfs_btree_lastrec(tcur, level);
309 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
310 /*
311 * Grab a pointer to the block.
312 */
313 rbp = tcur->bc_bufs[level];
314 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
315#ifdef DEBUG
316 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
317 goto error0;
318#endif
319 /*
320 * Grab the current block number, for future use.
321 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100322 bno = be32_to_cpu(right->bb_leftsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323 /*
324 * If right block is full enough so that removing one entry
325 * won't make it too empty, and left-shifting an entry out
326 * of right to us works, we're done.
327 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100328 if (be16_to_cpu(right->bb_numrecs) - 1 >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700329 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
330 if ((error = xfs_alloc_lshift(tcur, level, &i)))
331 goto error0;
332 if (i) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100333 ASSERT(be16_to_cpu(block->bb_numrecs) >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 XFS_ALLOC_BLOCK_MINRECS(level, cur));
335 xfs_btree_del_cursor(tcur,
336 XFS_BTREE_NOERROR);
337 if (level > 0 &&
338 (error = xfs_alloc_decrement(cur, level,
339 &i)))
340 return error;
341 *stat = 1;
342 return 0;
343 }
344 }
345 /*
346 * Otherwise, grab the number of records in right for
347 * future reference, and fix up the temp cursor to point
348 * to our block again (last record).
349 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100350 rrecs = be16_to_cpu(right->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700351 if (lbno != NULLAGBLOCK) {
352 i = xfs_btree_firstrec(tcur, level);
353 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
354 if ((error = xfs_alloc_decrement(tcur, level, &i)))
355 goto error0;
356 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
357 }
358 }
359 /*
360 * If there's a left sibling, see if it's ok to shift an entry
361 * out of it.
362 */
363 if (lbno != NULLAGBLOCK) {
364 /*
365 * Move the temp cursor to the first entry in the
366 * previous block.
367 */
368 i = xfs_btree_firstrec(tcur, level);
369 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
370 if ((error = xfs_alloc_decrement(tcur, level, &i)))
371 goto error0;
372 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
373 xfs_btree_firstrec(tcur, level);
374 /*
375 * Grab a pointer to the block.
376 */
377 lbp = tcur->bc_bufs[level];
378 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
379#ifdef DEBUG
380 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
381 goto error0;
382#endif
383 /*
384 * Grab the current block number, for future use.
385 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100386 bno = be32_to_cpu(left->bb_rightsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387 /*
388 * If left block is full enough so that removing one entry
389 * won't make it too empty, and right-shifting an entry out
390 * of left to us works, we're done.
391 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100392 if (be16_to_cpu(left->bb_numrecs) - 1 >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
394 if ((error = xfs_alloc_rshift(tcur, level, &i)))
395 goto error0;
396 if (i) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100397 ASSERT(be16_to_cpu(block->bb_numrecs) >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398 XFS_ALLOC_BLOCK_MINRECS(level, cur));
399 xfs_btree_del_cursor(tcur,
400 XFS_BTREE_NOERROR);
401 if (level == 0)
402 cur->bc_ptrs[0]++;
403 *stat = 1;
404 return 0;
405 }
406 }
407 /*
408 * Otherwise, grab the number of records in right for
409 * future reference.
410 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100411 lrecs = be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700412 }
413 /*
414 * Delete the temp cursor, we're done with it.
415 */
416 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
417 /*
418 * If here, we need to do a join to keep the tree balanced.
419 */
420 ASSERT(bno != NULLAGBLOCK);
421 /*
422 * See if we can join with the left neighbor block.
423 */
424 if (lbno != NULLAGBLOCK &&
Eric Sandeen91d87232006-09-28 11:05:40 +1000425 lrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 /*
427 * Set "right" to be the starting block,
428 * "left" to be the left neighbor.
429 */
430 rbno = bno;
431 right = block;
Eric Sandeen91d87232006-09-28 11:05:40 +1000432 rrecs = be16_to_cpu(right->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 rbp = bp;
434 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
435 cur->bc_private.a.agno, lbno, 0, &lbp,
436 XFS_ALLOC_BTREE_REF)))
437 return error;
438 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
Eric Sandeen91d87232006-09-28 11:05:40 +1000439 lrecs = be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700440 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
441 return error;
442 }
443 /*
444 * If that won't work, see if we can join with the right neighbor block.
445 */
446 else if (rbno != NULLAGBLOCK &&
Eric Sandeen91d87232006-09-28 11:05:40 +1000447 rrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448 /*
449 * Set "left" to be the starting block,
450 * "right" to be the right neighbor.
451 */
452 lbno = bno;
453 left = block;
Eric Sandeen91d87232006-09-28 11:05:40 +1000454 lrecs = be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455 lbp = bp;
456 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
457 cur->bc_private.a.agno, rbno, 0, &rbp,
458 XFS_ALLOC_BTREE_REF)))
459 return error;
460 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
Eric Sandeen91d87232006-09-28 11:05:40 +1000461 rrecs = be16_to_cpu(right->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
463 return error;
464 }
465 /*
466 * Otherwise, we can't fix the imbalance.
467 * Just return. This is probably a logic error, but it's not fatal.
468 */
469 else {
470 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
471 return error;
472 *stat = 1;
473 return 0;
474 }
475 /*
476 * We're now going to join "left" and "right" by moving all the stuff
477 * in "right" to "left" and deleting "right".
478 */
479 if (level > 0) {
480 /*
481 * It's a non-leaf. Move keys and pointers.
482 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000483 lkp = XFS_ALLOC_KEY_ADDR(left, lrecs + 1, cur);
484 lpp = XFS_ALLOC_PTR_ADDR(left, lrecs + 1, cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
486 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
487#ifdef DEBUG
Eric Sandeen91d87232006-09-28 11:05:40 +1000488 for (i = 0; i < rrecs; i++) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100489 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490 return error;
491 }
492#endif
Eric Sandeen91d87232006-09-28 11:05:40 +1000493 memcpy(lkp, rkp, rrecs * sizeof(*lkp));
494 memcpy(lpp, rpp, rrecs * sizeof(*lpp));
495 xfs_alloc_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
496 xfs_alloc_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497 } else {
498 /*
499 * It's a leaf. Move records.
500 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000501 lrp = XFS_ALLOC_REC_ADDR(left, lrecs + 1, cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
Eric Sandeen91d87232006-09-28 11:05:40 +1000503 memcpy(lrp, rrp, rrecs * sizeof(*lrp));
504 xfs_alloc_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 }
506 /*
507 * If we joined with the left neighbor, set the buffer in the
508 * cursor to the left block, and fix up the index.
509 */
510 if (bp != lbp) {
511 xfs_btree_setbuf(cur, level, lbp);
Eric Sandeen91d87232006-09-28 11:05:40 +1000512 cur->bc_ptrs[level] += lrecs;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 }
514 /*
515 * If we joined with the right neighbor and there's a level above
516 * us, increment the cursor at that level.
517 */
518 else if (level + 1 < cur->bc_nlevels &&
519 (error = xfs_alloc_increment(cur, level + 1, &i)))
520 return error;
521 /*
522 * Fix up the number of records in the surviving block.
523 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000524 lrecs += rrecs;
525 left->bb_numrecs = cpu_to_be16(lrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 /*
527 * Fix up the right block pointer in the surviving block, and log it.
528 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100529 left->bb_rightsib = right->bb_rightsib;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
531 /*
532 * If there is a right sibling now, make it point to the
533 * remaining block.
534 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100535 if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700536 xfs_alloc_block_t *rrblock;
537 xfs_buf_t *rrbp;
538
539 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +1100540 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541 &rrbp, XFS_ALLOC_BTREE_REF)))
542 return error;
543 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
544 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
545 return error;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100546 rrblock->bb_leftsib = cpu_to_be32(lbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
548 }
549 /*
550 * Free the deleting block by putting it on the freelist.
551 */
552 if ((error = xfs_alloc_put_freelist(cur->bc_tp, cur->bc_private.a.agbp,
553 NULL, rbno)))
554 return error;
555 /*
556 * Since blocks move to the free list without the coordination
557 * used in xfs_bmap_finish, we can't allow block to be available
558 * for reallocation and non-transaction writing (user data)
559 * until we know that the transaction that moved it to the free
560 * list is permanently on disk. We track the blocks by declaring
561 * these blocks as "busy"; the busy list is maintained on a
562 * per-ag basis and each transaction records which entries
563 * should be removed when the iclog commits to disk. If a
564 * busy block is allocated, the iclog is pushed up to the
565 * LSN that freed the block.
566 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100567 xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568 xfs_trans_agbtree_delta(cur->bc_tp, -1);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100569
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570 /*
571 * Adjust the current level's cursor so that we're left referring
572 * to the right node, after we're done.
573 * If this leaves the ptr value 0 our caller will fix it up.
574 */
575 if (level > 0)
576 cur->bc_ptrs[level]--;
577 /*
578 * Return value means the next level up has something to do.
579 */
580 *stat = 2;
581 return 0;
582
583error0:
584 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
585 return error;
586}
587
588/*
589 * Insert one record/level. Return information to the caller
590 * allowing the next level up to proceed if necessary.
591 */
592STATIC int /* error */
593xfs_alloc_insrec(
594 xfs_btree_cur_t *cur, /* btree cursor */
595 int level, /* level to insert record at */
596 xfs_agblock_t *bnop, /* i/o: block number inserted */
597 xfs_alloc_rec_t *recp, /* i/o: record data inserted */
598 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
599 int *stat) /* output: success/failure */
600{
601 xfs_agf_t *agf; /* allocation group freelist header */
602 xfs_alloc_block_t *block; /* btree block record/key lives in */
603 xfs_buf_t *bp; /* buffer for block */
604 int error; /* error return value */
605 int i; /* loop index */
606 xfs_alloc_key_t key; /* key value being inserted */
607 xfs_alloc_key_t *kp; /* pointer to btree keys */
608 xfs_agblock_t nbno; /* block number of allocated block */
609 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
610 xfs_alloc_key_t nkey; /* new key value, from split */
611 xfs_alloc_rec_t nrec; /* new record value, for caller */
Eric Sandeen91d87232006-09-28 11:05:40 +1000612 int numrecs;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700613 int optr; /* old ptr value */
614 xfs_alloc_ptr_t *pp; /* pointer to btree addresses */
615 int ptr; /* index in btree block for this rec */
616 xfs_alloc_rec_t *rp; /* pointer to btree records */
617
Christoph Hellwig16259e72005-11-02 15:11:25 +1100618 ASSERT(be32_to_cpu(recp->ar_blockcount) > 0);
Christoph Hellwig5bde1ba92005-11-02 15:06:18 +1100619
620 /*
621 * GCC doesn't understand the (arguably complex) control flow in
622 * this function and complains about uninitialized structure fields
623 * without this.
624 */
625 memset(&nrec, 0, sizeof(nrec));
626
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627 /*
628 * If we made it to the root level, allocate a new root block
629 * and we're done.
630 */
631 if (level >= cur->bc_nlevels) {
632 XFS_STATS_INC(xs_abt_insrec);
633 if ((error = xfs_alloc_newroot(cur, &i)))
634 return error;
635 *bnop = NULLAGBLOCK;
636 *stat = i;
637 return 0;
638 }
639 /*
640 * Make a key out of the record data to be inserted, and save it.
641 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100642 key.ar_startblock = recp->ar_startblock;
643 key.ar_blockcount = recp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 optr = ptr = cur->bc_ptrs[level];
645 /*
646 * If we're off the left edge, return failure.
647 */
648 if (ptr == 0) {
649 *stat = 0;
650 return 0;
651 }
652 XFS_STATS_INC(xs_abt_insrec);
653 /*
654 * Get pointers to the btree buffer and block.
655 */
656 bp = cur->bc_bufs[level];
657 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
Eric Sandeen91d87232006-09-28 11:05:40 +1000658 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659#ifdef DEBUG
660 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
661 return error;
662 /*
663 * Check that the new entry is being inserted in the right place.
664 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000665 if (ptr <= numrecs) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666 if (level == 0) {
667 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
668 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
669 } else {
670 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
671 xfs_btree_check_key(cur->bc_btnum, &key, kp);
672 }
673 }
674#endif
675 nbno = NULLAGBLOCK;
Nathan Scott1121b212006-09-28 10:58:40 +1000676 ncur = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677 /*
678 * If the block is full, we can't insert the new entry until we
679 * make the block un-full.
680 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000681 if (numrecs == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682 /*
683 * First, try shifting an entry to the right neighbor.
684 */
685 if ((error = xfs_alloc_rshift(cur, level, &i)))
686 return error;
687 if (i) {
688 /* nothing */
689 }
690 /*
691 * Next, try shifting an entry to the left neighbor.
692 */
693 else {
694 if ((error = xfs_alloc_lshift(cur, level, &i)))
695 return error;
696 if (i)
697 optr = ptr = cur->bc_ptrs[level];
698 else {
699 /*
700 * Next, try splitting the current block in
701 * half. If this works we have to re-set our
702 * variables because we could be in a
703 * different block now.
704 */
705 if ((error = xfs_alloc_split(cur, level, &nbno,
706 &nkey, &ncur, &i)))
707 return error;
708 if (i) {
709 bp = cur->bc_bufs[level];
710 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
711#ifdef DEBUG
712 if ((error =
713 xfs_btree_check_sblock(cur,
714 block, level, bp)))
715 return error;
716#endif
717 ptr = cur->bc_ptrs[level];
Christoph Hellwig16259e72005-11-02 15:11:25 +1100718 nrec.ar_startblock = nkey.ar_startblock;
719 nrec.ar_blockcount = nkey.ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720 }
721 /*
722 * Otherwise the insert fails.
723 */
724 else {
725 *stat = 0;
726 return 0;
727 }
728 }
729 }
730 }
731 /*
732 * At this point we know there's room for our new entry in the block
733 * we're pointing at.
734 */
Eric Sandeen91d87232006-09-28 11:05:40 +1000735 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 if (level > 0) {
737 /*
738 * It's a non-leaf entry. Make a hole for the new data
739 * in the key and ptr regions of the block.
740 */
741 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
742 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
743#ifdef DEBUG
Eric Sandeen91d87232006-09-28 11:05:40 +1000744 for (i = numrecs; i >= ptr; i--) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100745 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700746 return error;
747 }
748#endif
749 memmove(&kp[ptr], &kp[ptr - 1],
Eric Sandeen91d87232006-09-28 11:05:40 +1000750 (numrecs - ptr + 1) * sizeof(*kp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751 memmove(&pp[ptr], &pp[ptr - 1],
Eric Sandeen91d87232006-09-28 11:05:40 +1000752 (numrecs - ptr + 1) * sizeof(*pp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700753#ifdef DEBUG
754 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
755 return error;
756#endif
757 /*
758 * Now stuff the new data in, bump numrecs and log the new data.
759 */
760 kp[ptr - 1] = key;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100761 pp[ptr - 1] = cpu_to_be32(*bnop);
Eric Sandeen91d87232006-09-28 11:05:40 +1000762 numrecs++;
763 block->bb_numrecs = cpu_to_be16(numrecs);
764 xfs_alloc_log_keys(cur, bp, ptr, numrecs);
765 xfs_alloc_log_ptrs(cur, bp, ptr, numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700766#ifdef DEBUG
Eric Sandeen91d87232006-09-28 11:05:40 +1000767 if (ptr < numrecs)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700768 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
769 kp + ptr);
770#endif
771 } else {
772 /*
773 * It's a leaf entry. Make a hole for the new record.
774 */
775 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
776 memmove(&rp[ptr], &rp[ptr - 1],
Eric Sandeen91d87232006-09-28 11:05:40 +1000777 (numrecs - ptr + 1) * sizeof(*rp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700778 /*
779 * Now stuff the new record in, bump numrecs
780 * and log the new data.
781 */
Christoph Hellwigc38e5e82006-09-28 10:57:17 +1000782 rp[ptr - 1] = *recp;
Eric Sandeen91d87232006-09-28 11:05:40 +1000783 numrecs++;
784 block->bb_numrecs = cpu_to_be16(numrecs);
785 xfs_alloc_log_recs(cur, bp, ptr, numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700786#ifdef DEBUG
Eric Sandeen91d87232006-09-28 11:05:40 +1000787 if (ptr < numrecs)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
789 rp + ptr);
790#endif
791 }
792 /*
793 * Log the new number of records in the btree header.
794 */
795 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
796 /*
797 * If we inserted at the start of a block, update the parents' keys.
798 */
799 if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
800 return error;
801 /*
802 * Look to see if the longest extent in the allocation group
803 * needs to be updated.
804 */
805
806 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
807 if (level == 0 &&
808 cur->bc_btnum == XFS_BTNUM_CNT &&
Christoph Hellwig16259e72005-11-02 15:11:25 +1100809 be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
810 be32_to_cpu(recp->ar_blockcount) > be32_to_cpu(agf->agf_longest)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700811 /*
812 * If this is a leaf in the by-size btree and there
813 * is no right sibling block and this block is bigger
814 * than the previous longest block, update it.
815 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100816 agf->agf_longest = recp->ar_blockcount;
817 cur->bc_mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest
818 = be32_to_cpu(recp->ar_blockcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
820 XFS_AGF_LONGEST);
821 }
822 /*
823 * Return the new block number, if any.
824 * If there is one, give back a record value and a cursor too.
825 */
826 *bnop = nbno;
827 if (nbno != NULLAGBLOCK) {
Christoph Hellwigc38e5e82006-09-28 10:57:17 +1000828 *recp = nrec;
829 *curp = ncur;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700830 }
831 *stat = 1;
832 return 0;
833}
834
835/*
836 * Log header fields from a btree block.
837 */
838STATIC void
839xfs_alloc_log_block(
840 xfs_trans_t *tp, /* transaction pointer */
841 xfs_buf_t *bp, /* buffer containing btree block */
842 int fields) /* mask of fields: XFS_BB_... */
843{
844 int first; /* first byte offset logged */
845 int last; /* last byte offset logged */
846 static const short offsets[] = { /* table of offsets */
847 offsetof(xfs_alloc_block_t, bb_magic),
848 offsetof(xfs_alloc_block_t, bb_level),
849 offsetof(xfs_alloc_block_t, bb_numrecs),
850 offsetof(xfs_alloc_block_t, bb_leftsib),
851 offsetof(xfs_alloc_block_t, bb_rightsib),
852 sizeof(xfs_alloc_block_t)
853 };
854
855 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
856 xfs_trans_log_buf(tp, bp, first, last);
857}
858
859/*
860 * Log keys from a btree block (nonleaf).
861 */
862STATIC void
863xfs_alloc_log_keys(
864 xfs_btree_cur_t *cur, /* btree cursor */
865 xfs_buf_t *bp, /* buffer containing btree block */
866 int kfirst, /* index of first key to log */
867 int klast) /* index of last key to log */
868{
869 xfs_alloc_block_t *block; /* btree block to log from */
870 int first; /* first byte offset logged */
871 xfs_alloc_key_t *kp; /* key pointer in btree block */
872 int last; /* last byte offset logged */
873
874 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
875 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
876 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
877 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
878 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
879}
880
881/*
882 * Log block pointer fields from a btree block (nonleaf).
883 */
884STATIC void
885xfs_alloc_log_ptrs(
886 xfs_btree_cur_t *cur, /* btree cursor */
887 xfs_buf_t *bp, /* buffer containing btree block */
888 int pfirst, /* index of first pointer to log */
889 int plast) /* index of last pointer to log */
890{
891 xfs_alloc_block_t *block; /* btree block to log from */
892 int first; /* first byte offset logged */
893 int last; /* last byte offset logged */
894 xfs_alloc_ptr_t *pp; /* block-pointer pointer in btree blk */
895
896 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
897 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
898 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
899 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
900 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
901}
902
903/*
904 * Log records from a btree block (leaf).
905 */
906STATIC void
907xfs_alloc_log_recs(
908 xfs_btree_cur_t *cur, /* btree cursor */
909 xfs_buf_t *bp, /* buffer containing btree block */
910 int rfirst, /* index of first record to log */
911 int rlast) /* index of last record to log */
912{
913 xfs_alloc_block_t *block; /* btree block to log from */
914 int first; /* first byte offset logged */
915 int last; /* last byte offset logged */
916 xfs_alloc_rec_t *rp; /* record pointer for btree block */
917
918
919 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
920 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
921#ifdef DEBUG
922 {
923 xfs_agf_t *agf;
924 xfs_alloc_rec_t *p;
925
926 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
927 for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
Christoph Hellwig16259e72005-11-02 15:11:25 +1100928 ASSERT(be32_to_cpu(p->ar_startblock) +
929 be32_to_cpu(p->ar_blockcount) <=
930 be32_to_cpu(agf->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931 }
932#endif
933 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
934 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
935 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
936}
937
938/*
939 * Lookup the record. The cursor is made to point to it, based on dir.
940 * Return 0 if can't find any such record, 1 for success.
941 */
942STATIC int /* error */
943xfs_alloc_lookup(
944 xfs_btree_cur_t *cur, /* btree cursor */
945 xfs_lookup_t dir, /* <=, ==, or >= */
946 int *stat) /* success/failure */
947{
948 xfs_agblock_t agbno; /* a.g. relative btree block number */
949 xfs_agnumber_t agno; /* allocation group number */
950 xfs_alloc_block_t *block=NULL; /* current btree block */
951 int diff; /* difference for the current key */
952 int error; /* error return value */
953 int keyno=0; /* current key number */
954 int level; /* level in the btree */
955 xfs_mount_t *mp; /* file system mount point */
956
957 XFS_STATS_INC(xs_abt_lookup);
958 /*
959 * Get the allocation group header, and the root block number.
960 */
961 mp = cur->bc_mp;
962
963 {
964 xfs_agf_t *agf; /* a.g. freespace header */
965
966 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100967 agno = be32_to_cpu(agf->agf_seqno);
968 agbno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969 }
970 /*
971 * Iterate over each level in the btree, starting at the root.
972 * For each level above the leaves, find the key we need, based
973 * on the lookup record, then follow the corresponding block
974 * pointer down to the next level.
975 */
976 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
977 xfs_buf_t *bp; /* buffer pointer for btree block */
978 xfs_daddr_t d; /* disk address of btree block */
979
980 /*
981 * Get the disk address we're looking for.
982 */
983 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
984 /*
985 * If the old buffer at this level is for a different block,
986 * throw it away, otherwise just use it.
987 */
988 bp = cur->bc_bufs[level];
989 if (bp && XFS_BUF_ADDR(bp) != d)
Nathan Scott1121b212006-09-28 10:58:40 +1000990 bp = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700991 if (!bp) {
992 /*
993 * Need to get a new buffer. Read it, then
994 * set it in the cursor, releasing the old one.
995 */
996 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
997 agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
998 return error;
999 xfs_btree_setbuf(cur, level, bp);
1000 /*
1001 * Point to the btree block, now that we have the buffer
1002 */
1003 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1004 if ((error = xfs_btree_check_sblock(cur, block, level,
1005 bp)))
1006 return error;
1007 } else
1008 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1009 /*
1010 * If we already had a key match at a higher level, we know
1011 * we need to use the first entry in this block.
1012 */
1013 if (diff == 0)
1014 keyno = 1;
1015 /*
1016 * Otherwise we need to search this block. Do a binary search.
1017 */
1018 else {
1019 int high; /* high entry number */
1020 xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
1021 xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
1022 int low; /* low entry number */
1023
1024 /*
1025 * Get a pointer to keys or records.
1026 */
1027 if (level > 0)
1028 kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
1029 else
1030 krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
1031 /*
1032 * Set low and high entry numbers, 1-based.
1033 */
1034 low = 1;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001035 if (!(high = be16_to_cpu(block->bb_numrecs))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036 /*
1037 * If the block is empty, the tree must
1038 * be an empty leaf.
1039 */
1040 ASSERT(level == 0 && cur->bc_nlevels == 1);
1041 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1042 *stat = 0;
1043 return 0;
1044 }
1045 /*
1046 * Binary search the block.
1047 */
1048 while (low <= high) {
1049 xfs_extlen_t blockcount; /* key value */
1050 xfs_agblock_t startblock; /* key value */
1051
1052 XFS_STATS_INC(xs_abt_compare);
1053 /*
1054 * keyno is average of low and high.
1055 */
1056 keyno = (low + high) >> 1;
1057 /*
1058 * Get startblock & blockcount.
1059 */
1060 if (level > 0) {
1061 xfs_alloc_key_t *kkp;
1062
1063 kkp = kkbase + keyno - 1;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001064 startblock = be32_to_cpu(kkp->ar_startblock);
1065 blockcount = be32_to_cpu(kkp->ar_blockcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066 } else {
1067 xfs_alloc_rec_t *krp;
1068
1069 krp = krbase + keyno - 1;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001070 startblock = be32_to_cpu(krp->ar_startblock);
1071 blockcount = be32_to_cpu(krp->ar_blockcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001072 }
1073 /*
1074 * Compute difference to get next direction.
1075 */
1076 if (cur->bc_btnum == XFS_BTNUM_BNO)
1077 diff = (int)startblock -
1078 (int)cur->bc_rec.a.ar_startblock;
1079 else if (!(diff = (int)blockcount -
1080 (int)cur->bc_rec.a.ar_blockcount))
1081 diff = (int)startblock -
1082 (int)cur->bc_rec.a.ar_startblock;
1083 /*
1084 * Less than, move right.
1085 */
1086 if (diff < 0)
1087 low = keyno + 1;
1088 /*
1089 * Greater than, move left.
1090 */
1091 else if (diff > 0)
1092 high = keyno - 1;
1093 /*
1094 * Equal, we're done.
1095 */
1096 else
1097 break;
1098 }
1099 }
1100 /*
1101 * If there are more levels, set up for the next level
1102 * by getting the block number and filling in the cursor.
1103 */
1104 if (level > 0) {
1105 /*
1106 * If we moved left, need the previous key number,
1107 * unless there isn't one.
1108 */
1109 if (diff > 0 && --keyno < 1)
1110 keyno = 1;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001111 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, keyno, cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001112#ifdef DEBUG
1113 if ((error = xfs_btree_check_sptr(cur, agbno, level)))
1114 return error;
1115#endif
1116 cur->bc_ptrs[level] = keyno;
1117 }
1118 }
1119 /*
1120 * Done with the search.
1121 * See if we need to adjust the results.
1122 */
1123 if (dir != XFS_LOOKUP_LE && diff < 0) {
1124 keyno++;
1125 /*
1126 * If ge search and we went off the end of the block, but it's
1127 * not the last block, we're in the wrong block.
1128 */
1129 if (dir == XFS_LOOKUP_GE &&
Christoph Hellwig16259e72005-11-02 15:11:25 +11001130 keyno > be16_to_cpu(block->bb_numrecs) &&
1131 be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001132 int i;
1133
1134 cur->bc_ptrs[0] = keyno;
1135 if ((error = xfs_alloc_increment(cur, 0, &i)))
1136 return error;
1137 XFS_WANT_CORRUPTED_RETURN(i == 1);
1138 *stat = 1;
1139 return 0;
1140 }
1141 }
1142 else if (dir == XFS_LOOKUP_LE && diff > 0)
1143 keyno--;
1144 cur->bc_ptrs[0] = keyno;
1145 /*
1146 * Return if we succeeded or not.
1147 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001148 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001149 *stat = 0;
1150 else
1151 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1152 return 0;
1153}
1154
1155/*
1156 * Move 1 record left from cur/level if possible.
1157 * Update cur to reflect the new path.
1158 */
1159STATIC int /* error */
1160xfs_alloc_lshift(
1161 xfs_btree_cur_t *cur, /* btree cursor */
1162 int level, /* level to shift record on */
1163 int *stat) /* success/failure */
1164{
1165 int error; /* error return value */
1166#ifdef DEBUG
1167 int i; /* loop index */
1168#endif
1169 xfs_alloc_key_t key; /* key value for leaf level upward */
1170 xfs_buf_t *lbp; /* buffer for left neighbor block */
1171 xfs_alloc_block_t *left; /* left neighbor btree block */
1172 int nrec; /* new number of left block entries */
1173 xfs_buf_t *rbp; /* buffer for right (current) block */
1174 xfs_alloc_block_t *right; /* right (current) btree block */
1175 xfs_alloc_key_t *rkp=NULL; /* key pointer for right block */
1176 xfs_alloc_ptr_t *rpp=NULL; /* address pointer for right block */
1177 xfs_alloc_rec_t *rrp=NULL; /* record pointer for right block */
1178
1179 /*
1180 * Set up variables for this block as "right".
1181 */
1182 rbp = cur->bc_bufs[level];
1183 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1184#ifdef DEBUG
1185 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1186 return error;
1187#endif
1188 /*
1189 * If we've got no left sibling then we can't shift an entry left.
1190 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001191 if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 *stat = 0;
1193 return 0;
1194 }
1195 /*
1196 * If the cursor entry is the one that would be moved, don't
1197 * do it... it's too complicated.
1198 */
1199 if (cur->bc_ptrs[level] <= 1) {
1200 *stat = 0;
1201 return 0;
1202 }
1203 /*
1204 * Set up the left neighbor as "left".
1205 */
1206 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001207 cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
1208 0, &lbp, XFS_ALLOC_BTREE_REF)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001209 return error;
1210 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1211 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1212 return error;
1213 /*
1214 * If it's full, it can't take another entry.
1215 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001216 if (be16_to_cpu(left->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217 *stat = 0;
1218 return 0;
1219 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001220 nrec = be16_to_cpu(left->bb_numrecs) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001221 /*
1222 * If non-leaf, copy a key and a ptr to the left block.
1223 */
1224 if (level > 0) {
1225 xfs_alloc_key_t *lkp; /* key pointer for left block */
1226 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1227
1228 lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
1229 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1230 *lkp = *rkp;
1231 xfs_alloc_log_keys(cur, lbp, nrec, nrec);
1232 lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
1233 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1234#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001235 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001236 return error;
1237#endif
Christoph Hellwigc38e5e82006-09-28 10:57:17 +10001238 *lpp = *rpp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001239 xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
1240 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
1241 }
1242 /*
1243 * If leaf, copy a record to the left block.
1244 */
1245 else {
1246 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1247
1248 lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
1249 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1250 *lrp = *rrp;
1251 xfs_alloc_log_recs(cur, lbp, nrec, nrec);
1252 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
1253 }
1254 /*
1255 * Bump and log left's numrecs, decrement and log right's numrecs.
1256 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001257 be16_add(&left->bb_numrecs, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001258 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001259 be16_add(&right->bb_numrecs, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1261 /*
1262 * Slide the contents of right down one entry.
1263 */
1264 if (level > 0) {
1265#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001266 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1267 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268 level)))
1269 return error;
1270 }
1271#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001272 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1273 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1274 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1275 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001276 } else {
Christoph Hellwig16259e72005-11-02 15:11:25 +11001277 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1278 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1279 key.ar_startblock = rrp->ar_startblock;
1280 key.ar_blockcount = rrp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281 rkp = &key;
1282 }
1283 /*
1284 * Update the parent key values of right.
1285 */
1286 if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
1287 return error;
1288 /*
1289 * Slide the cursor value left one.
1290 */
1291 cur->bc_ptrs[level]--;
1292 *stat = 1;
1293 return 0;
1294}
1295
1296/*
1297 * Allocate a new root block, fill it in.
1298 */
1299STATIC int /* error */
1300xfs_alloc_newroot(
1301 xfs_btree_cur_t *cur, /* btree cursor */
1302 int *stat) /* success/failure */
1303{
1304 int error; /* error return value */
1305 xfs_agblock_t lbno; /* left block number */
1306 xfs_buf_t *lbp; /* left btree buffer */
1307 xfs_alloc_block_t *left; /* left btree block */
1308 xfs_mount_t *mp; /* mount structure */
1309 xfs_agblock_t nbno; /* new block number */
1310 xfs_buf_t *nbp; /* new (root) buffer */
1311 xfs_alloc_block_t *new; /* new (root) btree block */
1312 int nptr; /* new value for key index, 1 or 2 */
1313 xfs_agblock_t rbno; /* right block number */
1314 xfs_buf_t *rbp; /* right btree buffer */
1315 xfs_alloc_block_t *right; /* right btree block */
1316
1317 mp = cur->bc_mp;
1318
1319 ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
1320 /*
1321 * Get a buffer from the freelist blocks, for the new root.
1322 */
1323 if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1324 &nbno)))
1325 return error;
1326 /*
1327 * None available, we fail.
1328 */
1329 if (nbno == NULLAGBLOCK) {
1330 *stat = 0;
1331 return 0;
1332 }
1333 xfs_trans_agbtree_delta(cur->bc_tp, 1);
1334 nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
1335 0);
1336 new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
1337 /*
1338 * Set the root data in the a.g. freespace structure.
1339 */
1340 {
1341 xfs_agf_t *agf; /* a.g. freespace header */
1342 xfs_agnumber_t seqno;
1343
1344 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001345 agf->agf_roots[cur->bc_btnum] = cpu_to_be32(nbno);
1346 be32_add(&agf->agf_levels[cur->bc_btnum], 1);
1347 seqno = be32_to_cpu(agf->agf_seqno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001348 mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
1349 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
1350 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
1351 }
1352 /*
1353 * At the previous root level there are now two blocks: the old
1354 * root, and the new block generated when it was split.
1355 * We don't know which one the cursor is pointing at, so we
1356 * set up variables "left" and "right" for each case.
1357 */
1358 lbp = cur->bc_bufs[cur->bc_nlevels - 1];
1359 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1360#ifdef DEBUG
1361 if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
1362 return error;
1363#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001364 if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001365 /*
1366 * Our block is left, pick up the right block.
1367 */
1368 lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
Christoph Hellwig16259e72005-11-02 15:11:25 +11001369 rbno = be32_to_cpu(left->bb_rightsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001370 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1371 cur->bc_private.a.agno, rbno, 0, &rbp,
1372 XFS_ALLOC_BTREE_REF)))
1373 return error;
1374 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1375 if ((error = xfs_btree_check_sblock(cur, right,
1376 cur->bc_nlevels - 1, rbp)))
1377 return error;
1378 nptr = 1;
1379 } else {
1380 /*
1381 * Our block is right, pick up the left block.
1382 */
1383 rbp = lbp;
1384 right = left;
1385 rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
Christoph Hellwig16259e72005-11-02 15:11:25 +11001386 lbno = be32_to_cpu(right->bb_leftsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001387 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1388 cur->bc_private.a.agno, lbno, 0, &lbp,
1389 XFS_ALLOC_BTREE_REF)))
1390 return error;
1391 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1392 if ((error = xfs_btree_check_sblock(cur, left,
1393 cur->bc_nlevels - 1, lbp)))
1394 return error;
1395 nptr = 2;
1396 }
1397 /*
1398 * Fill in the new block's btree header and log it.
1399 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001400 new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1401 new->bb_level = cpu_to_be16(cur->bc_nlevels);
1402 new->bb_numrecs = cpu_to_be16(2);
1403 new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1404 new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001405 xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
1406 ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
1407 /*
1408 * Fill in the key data in the new root.
1409 */
1410 {
1411 xfs_alloc_key_t *kp; /* btree key pointer */
1412
1413 kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001414 if (be16_to_cpu(left->bb_level) > 0) {
Christoph Hellwigc38e5e82006-09-28 10:57:17 +10001415 kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur);
1416 kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001417 } else {
1418 xfs_alloc_rec_t *rp; /* btree record pointer */
1419
1420 rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001421 kp[0].ar_startblock = rp->ar_startblock;
1422 kp[0].ar_blockcount = rp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001423 rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001424 kp[1].ar_startblock = rp->ar_startblock;
1425 kp[1].ar_blockcount = rp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426 }
1427 }
1428 xfs_alloc_log_keys(cur, nbp, 1, 2);
1429 /*
1430 * Fill in the pointer data in the new root.
1431 */
1432 {
1433 xfs_alloc_ptr_t *pp; /* btree address pointer */
1434
1435 pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001436 pp[0] = cpu_to_be32(lbno);
1437 pp[1] = cpu_to_be32(rbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001438 }
1439 xfs_alloc_log_ptrs(cur, nbp, 1, 2);
1440 /*
1441 * Fix up the cursor.
1442 */
1443 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
1444 cur->bc_ptrs[cur->bc_nlevels] = nptr;
1445 cur->bc_nlevels++;
1446 *stat = 1;
1447 return 0;
1448}
1449
1450/*
1451 * Move 1 record right from cur/level if possible.
1452 * Update cur to reflect the new path.
1453 */
1454STATIC int /* error */
1455xfs_alloc_rshift(
1456 xfs_btree_cur_t *cur, /* btree cursor */
1457 int level, /* level to shift record on */
1458 int *stat) /* success/failure */
1459{
1460 int error; /* error return value */
1461 int i; /* loop index */
1462 xfs_alloc_key_t key; /* key value for leaf level upward */
1463 xfs_buf_t *lbp; /* buffer for left (current) block */
1464 xfs_alloc_block_t *left; /* left (current) btree block */
1465 xfs_buf_t *rbp; /* buffer for right neighbor block */
1466 xfs_alloc_block_t *right; /* right neighbor btree block */
1467 xfs_alloc_key_t *rkp; /* key pointer for right block */
1468 xfs_btree_cur_t *tcur; /* temporary cursor */
1469
1470 /*
1471 * Set up variables for this block as "left".
1472 */
1473 lbp = cur->bc_bufs[level];
1474 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1475#ifdef DEBUG
1476 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1477 return error;
1478#endif
1479 /*
1480 * If we've got no right sibling then we can't shift an entry right.
1481 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001482 if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483 *stat = 0;
1484 return 0;
1485 }
1486 /*
1487 * If the cursor entry is the one that would be moved, don't
1488 * do it... it's too complicated.
1489 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001490 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 *stat = 0;
1492 return 0;
1493 }
1494 /*
1495 * Set up the right neighbor as "right".
1496 */
1497 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001498 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
1499 0, &rbp, XFS_ALLOC_BTREE_REF)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001500 return error;
1501 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1502 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1503 return error;
1504 /*
1505 * If it's full, it can't take another entry.
1506 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001507 if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001508 *stat = 0;
1509 return 0;
1510 }
1511 /*
1512 * Make a hole at the start of the right neighbor block, then
1513 * copy the last left block entry to the hole.
1514 */
1515 if (level > 0) {
1516 xfs_alloc_key_t *lkp; /* key pointer for left block */
1517 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1518 xfs_alloc_ptr_t *rpp; /* address pointer for right block */
1519
Christoph Hellwig16259e72005-11-02 15:11:25 +11001520 lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1521 lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001522 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1523 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1524#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001525 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1526 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001527 return error;
1528 }
1529#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001530 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1531 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001532#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001533 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001534 return error;
1535#endif
Christoph Hellwigc38e5e82006-09-28 10:57:17 +10001536 *rkp = *lkp;
1537 *rpp = *lpp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001538 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1539 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001540 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1541 } else {
1542 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1543 xfs_alloc_rec_t *rrp; /* record pointer for right block */
1544
Christoph Hellwig16259e72005-11-02 15:11:25 +11001545 lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001546 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001547 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001548 *rrp = *lrp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001549 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1550 key.ar_startblock = rrp->ar_startblock;
1551 key.ar_blockcount = rrp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001552 rkp = &key;
1553 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1554 }
1555 /*
1556 * Decrement and log left's numrecs, bump and log right's numrecs.
1557 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001558 be16_add(&left->bb_numrecs, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001559 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001560 be16_add(&right->bb_numrecs, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001561 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1562 /*
1563 * Using a temporary cursor, update the parent key values of the
1564 * block on the right.
1565 */
1566 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1567 return error;
1568 i = xfs_btree_lastrec(tcur, level);
1569 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1570 if ((error = xfs_alloc_increment(tcur, level, &i)) ||
1571 (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
1572 goto error0;
1573 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1574 *stat = 1;
1575 return 0;
1576error0:
1577 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1578 return error;
1579}
1580
1581/*
1582 * Split cur/level block in half.
1583 * Return new block number and its first record (to be inserted into parent).
1584 */
1585STATIC int /* error */
1586xfs_alloc_split(
1587 xfs_btree_cur_t *cur, /* btree cursor */
1588 int level, /* level to split */
1589 xfs_agblock_t *bnop, /* output: block number allocated */
1590 xfs_alloc_key_t *keyp, /* output: first key of new block */
1591 xfs_btree_cur_t **curp, /* output: new cursor */
1592 int *stat) /* success/failure */
1593{
1594 int error; /* error return value */
1595 int i; /* loop index/record number */
1596 xfs_agblock_t lbno; /* left (current) block number */
1597 xfs_buf_t *lbp; /* buffer for left block */
1598 xfs_alloc_block_t *left; /* left (current) btree block */
1599 xfs_agblock_t rbno; /* right (new) block number */
1600 xfs_buf_t *rbp; /* buffer for right block */
1601 xfs_alloc_block_t *right; /* right (new) btree block */
1602
1603 /*
1604 * Allocate the new block from the freelist.
1605 * If we can't do it, we're toast. Give up.
1606 */
1607 if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1608 &rbno)))
1609 return error;
1610 if (rbno == NULLAGBLOCK) {
1611 *stat = 0;
1612 return 0;
1613 }
1614 xfs_trans_agbtree_delta(cur->bc_tp, 1);
1615 rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
1616 rbno, 0);
1617 /*
1618 * Set up the new block as "right".
1619 */
1620 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1621 /*
1622 * "Left" is the current (according to the cursor) block.
1623 */
1624 lbp = cur->bc_bufs[level];
1625 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1626#ifdef DEBUG
1627 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1628 return error;
1629#endif
1630 /*
1631 * Fill in the btree header for the new block.
1632 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001633 right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1634 right->bb_level = left->bb_level;
1635 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001636 /*
1637 * Make sure that if there's an odd number of entries now, that
1638 * each new block will have the same number of entries.
1639 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001640 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1641 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1642 be16_add(&right->bb_numrecs, 1);
1643 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001644 /*
1645 * For non-leaf blocks, copy keys and addresses over to the new block.
1646 */
1647 if (level > 0) {
1648 xfs_alloc_key_t *lkp; /* left btree key pointer */
1649 xfs_alloc_ptr_t *lpp; /* left btree address pointer */
1650 xfs_alloc_key_t *rkp; /* right btree key pointer */
1651 xfs_alloc_ptr_t *rpp; /* right btree address pointer */
1652
1653 lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
1654 lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
1655 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1656 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1657#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001658 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1659 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001660 return error;
1661 }
1662#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001663 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1664 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1665 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1666 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001667 *keyp = *rkp;
1668 }
1669 /*
1670 * For leaf blocks, copy records over to the new block.
1671 */
1672 else {
1673 xfs_alloc_rec_t *lrp; /* left btree record pointer */
1674 xfs_alloc_rec_t *rrp; /* right btree record pointer */
1675
1676 lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
1677 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001678 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1679 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1680 keyp->ar_startblock = rrp->ar_startblock;
1681 keyp->ar_blockcount = rrp->ar_blockcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001682 }
1683 /*
1684 * Find the left block number by looking in the buffer.
1685 * Adjust numrecs, sibling pointers.
1686 */
1687 lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
Christoph Hellwig16259e72005-11-02 15:11:25 +11001688 be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1689 right->bb_rightsib = left->bb_rightsib;
1690 left->bb_rightsib = cpu_to_be32(rbno);
1691 right->bb_leftsib = cpu_to_be32(lbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001692 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
1693 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1694 /*
1695 * If there's a block to the new block's right, make that block
1696 * point back to right instead of to left.
1697 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001698 if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001699 xfs_alloc_block_t *rrblock; /* rr btree block */
1700 xfs_buf_t *rrbp; /* buffer for rrblock */
1701
1702 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001703 cur->bc_private.a.agno, be32_to_cpu(right->bb_rightsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001704 &rrbp, XFS_ALLOC_BTREE_REF)))
1705 return error;
1706 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
1707 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1708 return error;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001709 rrblock->bb_leftsib = cpu_to_be32(rbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001710 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
1711 }
1712 /*
1713 * If the cursor is really in the right block, move it there.
1714 * If it's just pointing past the last entry in left, then we'll
1715 * insert there, so don't change anything in that case.
1716 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001717 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001718 xfs_btree_setbuf(cur, level, rbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001719 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001720 }
1721 /*
1722 * If there are more levels, we'll need another cursor which refers to
1723 * the right block, no matter where this cursor was.
1724 */
1725 if (level + 1 < cur->bc_nlevels) {
1726 if ((error = xfs_btree_dup_cursor(cur, curp)))
1727 return error;
1728 (*curp)->bc_ptrs[level + 1]++;
1729 }
1730 *bnop = rbno;
1731 *stat = 1;
1732 return 0;
1733}
1734
1735/*
1736 * Update keys at all levels from here to the root along the cursor's path.
1737 */
1738STATIC int /* error */
1739xfs_alloc_updkey(
1740 xfs_btree_cur_t *cur, /* btree cursor */
1741 xfs_alloc_key_t *keyp, /* new key value to update to */
1742 int level) /* starting level for update */
1743{
1744 int ptr; /* index of key in block */
1745
1746 /*
1747 * Go up the tree from this level toward the root.
1748 * At each level, update the key value to the value input.
1749 * Stop when we reach a level where the cursor isn't pointing
1750 * at the first entry in the block.
1751 */
1752 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1753 xfs_alloc_block_t *block; /* btree block */
1754 xfs_buf_t *bp; /* buffer for block */
1755#ifdef DEBUG
1756 int error; /* error return value */
1757#endif
1758 xfs_alloc_key_t *kp; /* ptr to btree block keys */
1759
1760 bp = cur->bc_bufs[level];
1761 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1762#ifdef DEBUG
1763 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1764 return error;
1765#endif
1766 ptr = cur->bc_ptrs[level];
1767 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
1768 *kp = *keyp;
1769 xfs_alloc_log_keys(cur, bp, ptr, ptr);
1770 }
1771 return 0;
1772}
1773
1774/*
1775 * Externally visible routines.
1776 */
1777
1778/*
1779 * Decrement cursor by one record at the level.
1780 * For nonzero levels the leaf-ward information is untouched.
1781 */
1782int /* error */
1783xfs_alloc_decrement(
1784 xfs_btree_cur_t *cur, /* btree cursor */
1785 int level, /* level in btree, 0 is leaf */
1786 int *stat) /* success/failure */
1787{
1788 xfs_alloc_block_t *block; /* btree block */
1789 int error; /* error return value */
1790 int lev; /* btree level */
1791
1792 ASSERT(level < cur->bc_nlevels);
1793 /*
1794 * Read-ahead to the left at this level.
1795 */
1796 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1797 /*
1798 * Decrement the ptr at this level. If we're still in the block
1799 * then we're done.
1800 */
1801 if (--cur->bc_ptrs[level] > 0) {
1802 *stat = 1;
1803 return 0;
1804 }
1805 /*
1806 * Get a pointer to the btree block.
1807 */
1808 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[level]);
1809#ifdef DEBUG
1810 if ((error = xfs_btree_check_sblock(cur, block, level,
1811 cur->bc_bufs[level])))
1812 return error;
1813#endif
1814 /*
1815 * If we just went off the left edge of the tree, return failure.
1816 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001817 if (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001818 *stat = 0;
1819 return 0;
1820 }
1821 /*
1822 * March up the tree decrementing pointers.
1823 * Stop when we don't go off the left edge of a block.
1824 */
1825 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1826 if (--cur->bc_ptrs[lev] > 0)
1827 break;
1828 /*
1829 * Read-ahead the left block, we're going to read it
1830 * in the next loop.
1831 */
1832 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1833 }
1834 /*
1835 * If we went off the root then we are seriously confused.
1836 */
1837 ASSERT(lev < cur->bc_nlevels);
1838 /*
1839 * Now walk back down the tree, fixing up the cursor's buffer
1840 * pointers and key numbers.
1841 */
1842 for (block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
1843 xfs_agblock_t agbno; /* block number of btree block */
1844 xfs_buf_t *bp; /* buffer pointer for block */
1845
Christoph Hellwig16259e72005-11-02 15:11:25 +11001846 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001847 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1848 cur->bc_private.a.agno, agbno, 0, &bp,
1849 XFS_ALLOC_BTREE_REF)))
1850 return error;
1851 lev--;
1852 xfs_btree_setbuf(cur, lev, bp);
1853 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1854 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1855 return error;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001856 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001857 }
1858 *stat = 1;
1859 return 0;
1860}
1861
1862/*
1863 * Delete the record pointed to by cur.
1864 * The cursor refers to the place where the record was (could be inserted)
1865 * when the operation returns.
1866 */
1867int /* error */
1868xfs_alloc_delete(
1869 xfs_btree_cur_t *cur, /* btree cursor */
1870 int *stat) /* success/failure */
1871{
1872 int error; /* error return value */
1873 int i; /* result code */
1874 int level; /* btree level */
1875
1876 /*
1877 * Go up the tree, starting at leaf level.
1878 * If 2 is returned then a join was done; go to the next level.
1879 * Otherwise we are done.
1880 */
1881 for (level = 0, i = 2; i == 2; level++) {
1882 if ((error = xfs_alloc_delrec(cur, level, &i)))
1883 return error;
1884 }
1885 if (i == 0) {
1886 for (level = 1; level < cur->bc_nlevels; level++) {
1887 if (cur->bc_ptrs[level] == 0) {
1888 if ((error = xfs_alloc_decrement(cur, level, &i)))
1889 return error;
1890 break;
1891 }
1892 }
1893 }
1894 *stat = i;
1895 return 0;
1896}
1897
1898/*
1899 * Get the data from the pointed-to record.
1900 */
1901int /* error */
1902xfs_alloc_get_rec(
1903 xfs_btree_cur_t *cur, /* btree cursor */
1904 xfs_agblock_t *bno, /* output: starting block of extent */
1905 xfs_extlen_t *len, /* output: length of extent */
1906 int *stat) /* output: success/failure */
1907{
1908 xfs_alloc_block_t *block; /* btree block */
1909#ifdef DEBUG
1910 int error; /* error return value */
1911#endif
1912 int ptr; /* record number */
1913
1914 ptr = cur->bc_ptrs[0];
1915 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
1916#ifdef DEBUG
1917 if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
1918 return error;
1919#endif
1920 /*
1921 * Off the right end or left end, return failure.
1922 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001923 if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001924 *stat = 0;
1925 return 0;
1926 }
1927 /*
1928 * Point to the record and extract its data.
1929 */
1930 {
1931 xfs_alloc_rec_t *rec; /* record data */
1932
1933 rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001934 *bno = be32_to_cpu(rec->ar_startblock);
1935 *len = be32_to_cpu(rec->ar_blockcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001936 }
1937 *stat = 1;
1938 return 0;
1939}
1940
1941/*
1942 * Increment cursor by one record at the level.
1943 * For nonzero levels the leaf-ward information is untouched.
1944 */
1945int /* error */
1946xfs_alloc_increment(
1947 xfs_btree_cur_t *cur, /* btree cursor */
1948 int level, /* level in btree, 0 is leaf */
1949 int *stat) /* success/failure */
1950{
1951 xfs_alloc_block_t *block; /* btree block */
1952 xfs_buf_t *bp; /* tree block buffer */
1953 int error; /* error return value */
1954 int lev; /* btree level */
1955
1956 ASSERT(level < cur->bc_nlevels);
1957 /*
1958 * Read-ahead to the right at this level.
1959 */
1960 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1961 /*
1962 * Get a pointer to the btree block.
1963 */
1964 bp = cur->bc_bufs[level];
1965 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1966#ifdef DEBUG
1967 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1968 return error;
1969#endif
1970 /*
1971 * Increment the ptr at this level. If we're still in the block
1972 * then we're done.
1973 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001974 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001975 *stat = 1;
1976 return 0;
1977 }
1978 /*
1979 * If we just went off the right edge of the tree, return failure.
1980 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001981 if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001982 *stat = 0;
1983 return 0;
1984 }
1985 /*
1986 * March up the tree incrementing pointers.
1987 * Stop when we don't go off the right edge of a block.
1988 */
1989 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1990 bp = cur->bc_bufs[lev];
1991 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1992#ifdef DEBUG
1993 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1994 return error;
1995#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001996 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001997 break;
1998 /*
1999 * Read-ahead the right block, we're going to read it
2000 * in the next loop.
2001 */
2002 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2003 }
2004 /*
2005 * If we went off the root then we are seriously confused.
2006 */
2007 ASSERT(lev < cur->bc_nlevels);
2008 /*
2009 * Now walk back down the tree, fixing up the cursor's buffer
2010 * pointers and key numbers.
2011 */
2012 for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2013 lev > level; ) {
2014 xfs_agblock_t agbno; /* block number of btree block */
2015
Christoph Hellwig16259e72005-11-02 15:11:25 +11002016 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002017 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
2018 cur->bc_private.a.agno, agbno, 0, &bp,
2019 XFS_ALLOC_BTREE_REF)))
2020 return error;
2021 lev--;
2022 xfs_btree_setbuf(cur, lev, bp);
2023 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2024 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
2025 return error;
2026 cur->bc_ptrs[lev] = 1;
2027 }
2028 *stat = 1;
2029 return 0;
2030}
2031
2032/*
2033 * Insert the current record at the point referenced by cur.
2034 * The cursor may be inconsistent on return if splits have been done.
2035 */
2036int /* error */
2037xfs_alloc_insert(
2038 xfs_btree_cur_t *cur, /* btree cursor */
2039 int *stat) /* success/failure */
2040{
2041 int error; /* error return value */
2042 int i; /* result value, 0 for failure */
2043 int level; /* current level number in btree */
2044 xfs_agblock_t nbno; /* new block number (split result) */
2045 xfs_btree_cur_t *ncur; /* new cursor (split result) */
2046 xfs_alloc_rec_t nrec; /* record being inserted this level */
2047 xfs_btree_cur_t *pcur; /* previous level's cursor */
2048
2049 level = 0;
2050 nbno = NULLAGBLOCK;
Christoph Hellwig16259e72005-11-02 15:11:25 +11002051 nrec.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
2052 nrec.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
Nathan Scott1121b212006-09-28 10:58:40 +10002053 ncur = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002054 pcur = cur;
2055 /*
2056 * Loop going up the tree, starting at the leaf level.
2057 * Stop when we don't get a split block, that must mean that
2058 * the insert is finished with this level.
2059 */
2060 do {
2061 /*
2062 * Insert nrec/nbno into this level of the tree.
2063 * Note if we fail, nbno will be null.
2064 */
2065 if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
2066 &i))) {
2067 if (pcur != cur)
2068 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2069 return error;
2070 }
2071 /*
2072 * See if the cursor we just used is trash.
2073 * Can't trash the caller's cursor, but otherwise we should
2074 * if ncur is a new cursor or we're about to be done.
2075 */
2076 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
2077 cur->bc_nlevels = pcur->bc_nlevels;
2078 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2079 }
2080 /*
2081 * If we got a new cursor, switch to it.
2082 */
2083 if (ncur) {
2084 pcur = ncur;
Nathan Scott1121b212006-09-28 10:58:40 +10002085 ncur = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002086 }
2087 } while (nbno != NULLAGBLOCK);
2088 *stat = i;
2089 return 0;
2090}
2091
2092/*
2093 * Lookup the record equal to [bno, len] in the btree given by cur.
2094 */
2095int /* error */
2096xfs_alloc_lookup_eq(
2097 xfs_btree_cur_t *cur, /* btree cursor */
2098 xfs_agblock_t bno, /* starting block of extent */
2099 xfs_extlen_t len, /* length of extent */
2100 int *stat) /* success/failure */
2101{
2102 cur->bc_rec.a.ar_startblock = bno;
2103 cur->bc_rec.a.ar_blockcount = len;
2104 return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
2105}
2106
2107/*
2108 * Lookup the first record greater than or equal to [bno, len]
2109 * in the btree given by cur.
2110 */
2111int /* error */
2112xfs_alloc_lookup_ge(
2113 xfs_btree_cur_t *cur, /* btree cursor */
2114 xfs_agblock_t bno, /* starting block of extent */
2115 xfs_extlen_t len, /* length of extent */
2116 int *stat) /* success/failure */
2117{
2118 cur->bc_rec.a.ar_startblock = bno;
2119 cur->bc_rec.a.ar_blockcount = len;
2120 return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
2121}
2122
2123/*
2124 * Lookup the first record less than or equal to [bno, len]
2125 * in the btree given by cur.
2126 */
2127int /* error */
2128xfs_alloc_lookup_le(
2129 xfs_btree_cur_t *cur, /* btree cursor */
2130 xfs_agblock_t bno, /* starting block of extent */
2131 xfs_extlen_t len, /* length of extent */
2132 int *stat) /* success/failure */
2133{
2134 cur->bc_rec.a.ar_startblock = bno;
2135 cur->bc_rec.a.ar_blockcount = len;
2136 return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
2137}
2138
2139/*
2140 * Update the record referred to by cur, to the value given by [bno, len].
2141 * This either works (return 0) or gets an EFSCORRUPTED error.
2142 */
2143int /* error */
2144xfs_alloc_update(
2145 xfs_btree_cur_t *cur, /* btree cursor */
2146 xfs_agblock_t bno, /* starting block of extent */
2147 xfs_extlen_t len) /* length of extent */
2148{
2149 xfs_alloc_block_t *block; /* btree block to update */
2150 int error; /* error return value */
2151 int ptr; /* current record number (updating) */
2152
2153 ASSERT(len > 0);
2154 /*
2155 * Pick up the a.g. freelist struct and the current block.
2156 */
2157 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
2158#ifdef DEBUG
2159 if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
2160 return error;
2161#endif
2162 /*
2163 * Get the address of the rec to be updated.
2164 */
2165 ptr = cur->bc_ptrs[0];
2166 {
2167 xfs_alloc_rec_t *rp; /* pointer to updated record */
2168
2169 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
2170 /*
2171 * Fill in the new contents and log them.
2172 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11002173 rp->ar_startblock = cpu_to_be32(bno);
2174 rp->ar_blockcount = cpu_to_be32(len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002175 xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
2176 }
2177 /*
2178 * If it's the by-size btree and it's the last leaf block and
2179 * it's the last record... then update the size of the longest
2180 * extent in the a.g., which we cache in the a.g. freelist header.
2181 */
2182 if (cur->bc_btnum == XFS_BTNUM_CNT &&
Christoph Hellwig16259e72005-11-02 15:11:25 +11002183 be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
2184 ptr == be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002185 xfs_agf_t *agf; /* a.g. freespace header */
2186 xfs_agnumber_t seqno;
2187
2188 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002189 seqno = be32_to_cpu(agf->agf_seqno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002190 cur->bc_mp->m_perag[seqno].pagf_longest = len;
Christoph Hellwig16259e72005-11-02 15:11:25 +11002191 agf->agf_longest = cpu_to_be32(len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002192 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
2193 XFS_AGF_LONGEST);
2194 }
2195 /*
2196 * Updating first record in leaf. Pass new key value up to our parent.
2197 */
2198 if (ptr == 1) {
2199 xfs_alloc_key_t key; /* key containing [bno, len] */
2200
Christoph Hellwig16259e72005-11-02 15:11:25 +11002201 key.ar_startblock = cpu_to_be32(bno);
2202 key.ar_blockcount = cpu_to_be32(len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002203 if ((error = xfs_alloc_updkey(cur, &key, 1)))
2204 return error;
2205 }
2206 return 0;
2207}