aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/xfs/xfs_alloc_btree.c')
-rw-r--r--fs/xfs/xfs_alloc_btree.c2204
1 files changed, 2204 insertions, 0 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
new file mode 100644
index 000000000000..e0355a12d946
--- /dev/null
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -0,0 +1,2204 @@
1/*
2 * Copyright (c) 2000-2001 Silicon Graphics, Inc. All Rights Reserved.
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
11 *
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
22 *
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
25 *
26 * http://www.sgi.com
27 *
28 * For further information regarding this notice, see:
29 *
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
31 */
32
33/*
34 * Free space allocation for XFS.
35 */
36
37#include "xfs.h"
38#include "xfs_macros.h"
39#include "xfs_types.h"
40#include "xfs_inum.h"
41#include "xfs_log.h"
42#include "xfs_trans.h"
43#include "xfs_sb.h"
44#include "xfs_ag.h"
45#include "xfs_dir.h"
46#include "xfs_dmapi.h"
47#include "xfs_mount.h"
48#include "xfs_alloc_btree.h"
49#include "xfs_ialloc_btree.h"
50#include "xfs_bmap_btree.h"
51#include "xfs_btree.h"
52#include "xfs_ialloc.h"
53#include "xfs_alloc.h"
54#include "xfs_error.h"
55
56/*
57 * Prototypes for internal functions.
58 */
59
60STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
61STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
62STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
63STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
64STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
65STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
66STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
67STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
68 xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
69STATIC int xfs_alloc_updkey(xfs_btree_cur_t *, xfs_alloc_key_t *, int);
70
71/*
72 * Internal functions.
73 */
74
75/*
76 * Single level of the xfs_alloc_delete record deletion routine.
77 * Delete record pointed to by cur/level.
78 * Remove the record from its block then rebalance the tree.
79 * Return 0 for error, 1 for done, 2 to go on to the next level.
80 */
81STATIC int /* error */
82xfs_alloc_delrec(
83 xfs_btree_cur_t *cur, /* btree cursor */
84 int level, /* level removing record from */
85 int *stat) /* fail/done/go-on */
86{
87 xfs_agf_t *agf; /* allocation group freelist header */
88 xfs_alloc_block_t *block; /* btree block record/key lives in */
89 xfs_agblock_t bno; /* btree block number */
90 xfs_buf_t *bp; /* buffer for block */
91 int error; /* error return value */
92 int i; /* loop index */
93 xfs_alloc_key_t key; /* kp points here if block is level 0 */
94 xfs_agblock_t lbno; /* left block's block number */
95 xfs_buf_t *lbp; /* left block's buffer pointer */
96 xfs_alloc_block_t *left; /* left btree block */
97 xfs_alloc_key_t *lkp=NULL; /* left block key pointer */
98 xfs_alloc_ptr_t *lpp=NULL; /* left block address pointer */
99 int lrecs=0; /* number of records in left block */
100 xfs_alloc_rec_t *lrp; /* left block record pointer */
101 xfs_mount_t *mp; /* mount structure */
102 int ptr; /* index in btree block for this rec */
103 xfs_agblock_t rbno; /* right block's block number */
104 xfs_buf_t *rbp; /* right block's buffer pointer */
105 xfs_alloc_block_t *right; /* right btree block */
106 xfs_alloc_key_t *rkp; /* right block key pointer */
107 xfs_alloc_ptr_t *rpp; /* right block address pointer */
108 int rrecs=0; /* number of records in right block */
109 xfs_alloc_rec_t *rrp; /* right block record pointer */
110 xfs_btree_cur_t *tcur; /* temporary btree cursor */
111
112 /*
113 * Get the index of the entry being deleted, check for nothing there.
114 */
115 ptr = cur->bc_ptrs[level];
116 if (ptr == 0) {
117 *stat = 0;
118 return 0;
119 }
120 /*
121 * Get the buffer & block containing the record or key/ptr.
122 */
123 bp = cur->bc_bufs[level];
124 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
125#ifdef DEBUG
126 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
127 return error;
128#endif
129 /*
130 * Fail if we're off the end of the block.
131 */
132 if (ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
133 *stat = 0;
134 return 0;
135 }
136 XFS_STATS_INC(xs_abt_delrec);
137 /*
138 * It's a nonleaf. Excise the key and ptr being deleted, by
139 * sliding the entries past them down one.
140 * Log the changed areas of the block.
141 */
142 if (level > 0) {
143 lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
144 lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
145#ifdef DEBUG
146 for (i = ptr; i < INT_GET(block->bb_numrecs, ARCH_CONVERT); i++) {
147 if ((error = xfs_btree_check_sptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level)))
148 return error;
149 }
150#endif
151 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
152 memmove(&lkp[ptr - 1], &lkp[ptr],
153 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lkp)); /* INT_: mem copy */
154 memmove(&lpp[ptr - 1], &lpp[ptr],
155 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lpp)); /* INT_: mem copy */
156 xfs_alloc_log_ptrs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
157 xfs_alloc_log_keys(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
158 }
159 }
160 /*
161 * It's a leaf. Excise the record being deleted, by sliding the
162 * entries past it down one. Log the changed areas of the block.
163 */
164 else {
165 lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
166 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
167 memmove(&lrp[ptr - 1], &lrp[ptr],
168 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lrp));
169 xfs_alloc_log_recs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
170 }
171 /*
172 * If it's the first record in the block, we'll need a key
173 * structure to pass up to the next level (updkey).
174 */
175 if (ptr == 1) {
176 key.ar_startblock = lrp->ar_startblock; /* INT_: direct copy */
177 key.ar_blockcount = lrp->ar_blockcount; /* INT_: direct copy */
178 lkp = &key;
179 }
180 }
181 /*
182 * Decrement and log the number of entries in the block.
183 */
184 INT_MOD(block->bb_numrecs, ARCH_CONVERT, -1);
185 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
186 /*
187 * See if the longest free extent in the allocation group was
188 * changed by this operation. True if it's the by-size btree, and
189 * this is the leaf level, and there is no right sibling block,
190 * and this was the last record.
191 */
192 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
193 mp = cur->bc_mp;
194
195 if (level == 0 &&
196 cur->bc_btnum == XFS_BTNUM_CNT &&
197 INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
198 ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
199 ASSERT(ptr == INT_GET(block->bb_numrecs, ARCH_CONVERT) + 1);
200 /*
201 * There are still records in the block. Grab the size
202 * from the last one.
203 */
204 if (INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
205 rrp = XFS_ALLOC_REC_ADDR(block, INT_GET(block->bb_numrecs, ARCH_CONVERT), cur);
206 INT_COPY(agf->agf_longest, rrp->ar_blockcount, ARCH_CONVERT);
207 }
208 /*
209 * No free extents left.
210 */
211 else
212 agf->agf_longest = 0;
213 mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_longest =
214 INT_GET(agf->agf_longest, ARCH_CONVERT);
215 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
216 XFS_AGF_LONGEST);
217 }
218 /*
219 * Is this the root level? If so, we're almost done.
220 */
221 if (level == cur->bc_nlevels - 1) {
222 /*
223 * If this is the root level,
224 * and there's only one entry left,
225 * and it's NOT the leaf level,
226 * then we can get rid of this level.
227 */
228 if (INT_GET(block->bb_numrecs, ARCH_CONVERT) == 1 && level > 0) {
229 /*
230 * lpp is still set to the first pointer in the block.
231 * Make it the new root of the btree.
232 */
233 bno = INT_GET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT);
234 INT_COPY(agf->agf_roots[cur->bc_btnum], *lpp, ARCH_CONVERT);
235 INT_MOD(agf->agf_levels[cur->bc_btnum], ARCH_CONVERT, -1);
236 mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_levels[cur->bc_btnum]--;
237 /*
238 * Put this buffer/block on the ag's freelist.
239 */
240 if ((error = xfs_alloc_put_freelist(cur->bc_tp,
241 cur->bc_private.a.agbp, NULL, bno)))
242 return error;
243 /*
244 * Since blocks move to the free list without the
245 * coordination used in xfs_bmap_finish, we can't allow
246 * block to be available for reallocation and
247 * non-transaction writing (user data) until we know
248 * that the transaction that moved it to the free list
249 * is permanently on disk. We track the blocks by
250 * declaring these blocks as "busy"; the busy list is
251 * maintained on a per-ag basis and each transaction
252 * records which entries should be removed when the
253 * iclog commits to disk. If a busy block is
254 * allocated, the iclog is pushed up to the LSN
255 * that freed the block.
256 */
257 xfs_alloc_mark_busy(cur->bc_tp,
258 INT_GET(agf->agf_seqno, ARCH_CONVERT), bno, 1);
259
260 xfs_trans_agbtree_delta(cur->bc_tp, -1);
261 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
262 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
263 /*
264 * Update the cursor so there's one fewer level.
265 */
266 xfs_btree_setbuf(cur, level, NULL);
267 cur->bc_nlevels--;
268 } else if (level > 0 &&
269 (error = xfs_alloc_decrement(cur, level, &i)))
270 return error;
271 *stat = 1;
272 return 0;
273 }
274 /*
275 * If we deleted the leftmost entry in the block, update the
276 * key values above us in the tree.
277 */
278 if (ptr == 1 && (error = xfs_alloc_updkey(cur, lkp, level + 1)))
279 return error;
280 /*
281 * If the number of records remaining in the block is at least
282 * the minimum, we're done.
283 */
284 if (INT_GET(block->bb_numrecs, ARCH_CONVERT) >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
285 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
286 return error;
287 *stat = 1;
288 return 0;
289 }
290 /*
291 * Otherwise, we have to move some records around to keep the
292 * tree balanced. Look at the left and right sibling blocks to
293 * see if we can re-balance by moving only one record.
294 */
295 rbno = INT_GET(block->bb_rightsib, ARCH_CONVERT);
296 lbno = INT_GET(block->bb_leftsib, ARCH_CONVERT);
297 bno = NULLAGBLOCK;
298 ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
299 /*
300 * Duplicate the cursor so our btree manipulations here won't
301 * disrupt the next level up.
302 */
303 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
304 return error;
305 /*
306 * If there's a right sibling, see if it's ok to shift an entry
307 * out of it.
308 */
309 if (rbno != NULLAGBLOCK) {
310 /*
311 * Move the temp cursor to the last entry in the next block.
312 * Actually any entry but the first would suffice.
313 */
314 i = xfs_btree_lastrec(tcur, level);
315 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
316 if ((error = xfs_alloc_increment(tcur, level, &i)))
317 goto error0;
318 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
319 i = xfs_btree_lastrec(tcur, level);
320 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
321 /*
322 * Grab a pointer to the block.
323 */
324 rbp = tcur->bc_bufs[level];
325 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
326#ifdef DEBUG
327 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
328 goto error0;
329#endif
330 /*
331 * Grab the current block number, for future use.
332 */
333 bno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
334 /*
335 * If right block is full enough so that removing one entry
336 * won't make it too empty, and left-shifting an entry out
337 * of right to us works, we're done.
338 */
339 if (INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1 >=
340 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
341 if ((error = xfs_alloc_lshift(tcur, level, &i)))
342 goto error0;
343 if (i) {
344 ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
345 XFS_ALLOC_BLOCK_MINRECS(level, cur));
346 xfs_btree_del_cursor(tcur,
347 XFS_BTREE_NOERROR);
348 if (level > 0 &&
349 (error = xfs_alloc_decrement(cur, level,
350 &i)))
351 return error;
352 *stat = 1;
353 return 0;
354 }
355 }
356 /*
357 * Otherwise, grab the number of records in right for
358 * future reference, and fix up the temp cursor to point
359 * to our block again (last record).
360 */
361 rrecs = INT_GET(right->bb_numrecs, ARCH_CONVERT);
362 if (lbno != NULLAGBLOCK) {
363 i = xfs_btree_firstrec(tcur, level);
364 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
365 if ((error = xfs_alloc_decrement(tcur, level, &i)))
366 goto error0;
367 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
368 }
369 }
370 /*
371 * If there's a left sibling, see if it's ok to shift an entry
372 * out of it.
373 */
374 if (lbno != NULLAGBLOCK) {
375 /*
376 * Move the temp cursor to the first entry in the
377 * previous block.
378 */
379 i = xfs_btree_firstrec(tcur, level);
380 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
381 if ((error = xfs_alloc_decrement(tcur, level, &i)))
382 goto error0;
383 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
384 xfs_btree_firstrec(tcur, level);
385 /*
386 * Grab a pointer to the block.
387 */
388 lbp = tcur->bc_bufs[level];
389 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
390#ifdef DEBUG
391 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
392 goto error0;
393#endif
394 /*
395 * Grab the current block number, for future use.
396 */
397 bno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
398 /*
399 * If left block is full enough so that removing one entry
400 * won't make it too empty, and right-shifting an entry out
401 * of left to us works, we're done.
402 */
403 if (INT_GET(left->bb_numrecs, ARCH_CONVERT) - 1 >=
404 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
405 if ((error = xfs_alloc_rshift(tcur, level, &i)))
406 goto error0;
407 if (i) {
408 ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
409 XFS_ALLOC_BLOCK_MINRECS(level, cur));
410 xfs_btree_del_cursor(tcur,
411 XFS_BTREE_NOERROR);
412 if (level == 0)
413 cur->bc_ptrs[0]++;
414 *stat = 1;
415 return 0;
416 }
417 }
418 /*
419 * Otherwise, grab the number of records in right for
420 * future reference.
421 */
422 lrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT);
423 }
424 /*
425 * Delete the temp cursor, we're done with it.
426 */
427 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
428 /*
429 * If here, we need to do a join to keep the tree balanced.
430 */
431 ASSERT(bno != NULLAGBLOCK);
432 /*
433 * See if we can join with the left neighbor block.
434 */
435 if (lbno != NULLAGBLOCK &&
436 lrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
437 /*
438 * Set "right" to be the starting block,
439 * "left" to be the left neighbor.
440 */
441 rbno = bno;
442 right = block;
443 rbp = bp;
444 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
445 cur->bc_private.a.agno, lbno, 0, &lbp,
446 XFS_ALLOC_BTREE_REF)))
447 return error;
448 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
449 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
450 return error;
451 }
452 /*
453 * If that won't work, see if we can join with the right neighbor block.
454 */
455 else if (rbno != NULLAGBLOCK &&
456 rrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
457 XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
458 /*
459 * Set "left" to be the starting block,
460 * "right" to be the right neighbor.
461 */
462 lbno = bno;
463 left = block;
464 lbp = bp;
465 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
466 cur->bc_private.a.agno, rbno, 0, &rbp,
467 XFS_ALLOC_BTREE_REF)))
468 return error;
469 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
470 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
471 return error;
472 }
473 /*
474 * Otherwise, we can't fix the imbalance.
475 * Just return. This is probably a logic error, but it's not fatal.
476 */
477 else {
478 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
479 return error;
480 *stat = 1;
481 return 0;
482 }
483 /*
484 * We're now going to join "left" and "right" by moving all the stuff
485 * in "right" to "left" and deleting "right".
486 */
487 if (level > 0) {
488 /*
489 * It's a non-leaf. Move keys and pointers.
490 */
491 lkp = XFS_ALLOC_KEY_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
492 lpp = XFS_ALLOC_PTR_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
493 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
494 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
495#ifdef DEBUG
496 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
497 if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level)))
498 return error;
499 }
500#endif
501 memcpy(lkp, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lkp)); /* INT_: structure copy */
502 memcpy(lpp, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lpp)); /* INT_: structure copy */
503 xfs_alloc_log_keys(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
504 INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
505 xfs_alloc_log_ptrs(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
506 INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
507 } else {
508 /*
509 * It's a leaf. Move records.
510 */
511 lrp = XFS_ALLOC_REC_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
512 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
513 memcpy(lrp, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lrp));
514 xfs_alloc_log_recs(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
515 INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
516 }
517 /*
518 * If we joined with the left neighbor, set the buffer in the
519 * cursor to the left block, and fix up the index.
520 */
521 if (bp != lbp) {
522 xfs_btree_setbuf(cur, level, lbp);
523 cur->bc_ptrs[level] += INT_GET(left->bb_numrecs, ARCH_CONVERT);
524 }
525 /*
526 * If we joined with the right neighbor and there's a level above
527 * us, increment the cursor at that level.
528 */
529 else if (level + 1 < cur->bc_nlevels &&
530 (error = xfs_alloc_increment(cur, level + 1, &i)))
531 return error;
532 /*
533 * Fix up the number of records in the surviving block.
534 */
535 INT_MOD(left->bb_numrecs, ARCH_CONVERT, INT_GET(right->bb_numrecs, ARCH_CONVERT));
536 /*
537 * Fix up the right block pointer in the surviving block, and log it.
538 */
539 left->bb_rightsib = right->bb_rightsib; /* INT_: direct copy */
540 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
541 /*
542 * If there is a right sibling now, make it point to the
543 * remaining block.
544 */
545 if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
546 xfs_alloc_block_t *rrblock;
547 xfs_buf_t *rrbp;
548
549 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
550 cur->bc_private.a.agno, INT_GET(left->bb_rightsib, ARCH_CONVERT), 0,
551 &rrbp, XFS_ALLOC_BTREE_REF)))
552 return error;
553 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
554 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
555 return error;
556 INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, lbno);
557 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
558 }
559 /*
560 * Free the deleting block by putting it on the freelist.
561 */
562 if ((error = xfs_alloc_put_freelist(cur->bc_tp, cur->bc_private.a.agbp,
563 NULL, rbno)))
564 return error;
565 /*
566 * Since blocks move to the free list without the coordination
567 * used in xfs_bmap_finish, we can't allow block to be available
568 * for reallocation and non-transaction writing (user data)
569 * until we know that the transaction that moved it to the free
570 * list is permanently on disk. We track the blocks by declaring
571 * these blocks as "busy"; the busy list is maintained on a
572 * per-ag basis and each transaction records which entries
573 * should be removed when the iclog commits to disk. If a
574 * busy block is allocated, the iclog is pushed up to the
575 * LSN that freed the block.
576 */
577 xfs_alloc_mark_busy(cur->bc_tp,
578 INT_GET(agf->agf_seqno, ARCH_CONVERT), bno, 1);
579
580 xfs_trans_agbtree_delta(cur->bc_tp, -1);
581 /*
582 * Adjust the current level's cursor so that we're left referring
583 * to the right node, after we're done.
584 * If this leaves the ptr value 0 our caller will fix it up.
585 */
586 if (level > 0)
587 cur->bc_ptrs[level]--;
588 /*
589 * Return value means the next level up has something to do.
590 */
591 *stat = 2;
592 return 0;
593
594error0:
595 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
596 return error;
597}
598
599/*
600 * Insert one record/level. Return information to the caller
601 * allowing the next level up to proceed if necessary.
602 */
603STATIC int /* error */
604xfs_alloc_insrec(
605 xfs_btree_cur_t *cur, /* btree cursor */
606 int level, /* level to insert record at */
607 xfs_agblock_t *bnop, /* i/o: block number inserted */
608 xfs_alloc_rec_t *recp, /* i/o: record data inserted */
609 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
610 int *stat) /* output: success/failure */
611{
612 xfs_agf_t *agf; /* allocation group freelist header */
613 xfs_alloc_block_t *block; /* btree block record/key lives in */
614 xfs_buf_t *bp; /* buffer for block */
615 int error; /* error return value */
616 int i; /* loop index */
617 xfs_alloc_key_t key; /* key value being inserted */
618 xfs_alloc_key_t *kp; /* pointer to btree keys */
619 xfs_agblock_t nbno; /* block number of allocated block */
620 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
621 xfs_alloc_key_t nkey; /* new key value, from split */
622 xfs_alloc_rec_t nrec; /* new record value, for caller */
623 int optr; /* old ptr value */
624 xfs_alloc_ptr_t *pp; /* pointer to btree addresses */
625 int ptr; /* index in btree block for this rec */
626 xfs_alloc_rec_t *rp; /* pointer to btree records */
627
628 ASSERT(INT_GET(recp->ar_blockcount, ARCH_CONVERT) > 0);
629 /*
630 * If we made it to the root level, allocate a new root block
631 * and we're done.
632 */
633 if (level >= cur->bc_nlevels) {
634 XFS_STATS_INC(xs_abt_insrec);
635 if ((error = xfs_alloc_newroot(cur, &i)))
636 return error;
637 *bnop = NULLAGBLOCK;
638 *stat = i;
639 return 0;
640 }
641 /*
642 * Make a key out of the record data to be inserted, and save it.
643 */
644 key.ar_startblock = recp->ar_startblock; /* INT_: direct copy */
645 key.ar_blockcount = recp->ar_blockcount; /* INT_: direct copy */
646 optr = ptr = cur->bc_ptrs[level];
647 /*
648 * If we're off the left edge, return failure.
649 */
650 if (ptr == 0) {
651 *stat = 0;
652 return 0;
653 }
654 XFS_STATS_INC(xs_abt_insrec);
655 /*
656 * Get pointers to the btree buffer and block.
657 */
658 bp = cur->bc_bufs[level];
659 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
660#ifdef DEBUG
661 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
662 return error;
663 /*
664 * Check that the new entry is being inserted in the right place.
665 */
666 if (ptr <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
667 if (level == 0) {
668 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
669 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
670 } else {
671 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
672 xfs_btree_check_key(cur->bc_btnum, &key, kp);
673 }
674 }
675#endif
676 nbno = NULLAGBLOCK;
677 ncur = (xfs_btree_cur_t *)0;
678 /*
679 * If the block is full, we can't insert the new entry until we
680 * make the block un-full.
681 */
682 if (INT_GET(block->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
683 /*
684 * First, try shifting an entry to the right neighbor.
685 */
686 if ((error = xfs_alloc_rshift(cur, level, &i)))
687 return error;
688 if (i) {
689 /* nothing */
690 }
691 /*
692 * Next, try shifting an entry to the left neighbor.
693 */
694 else {
695 if ((error = xfs_alloc_lshift(cur, level, &i)))
696 return error;
697 if (i)
698 optr = ptr = cur->bc_ptrs[level];
699 else {
700 /*
701 * Next, try splitting the current block in
702 * half. If this works we have to re-set our
703 * variables because we could be in a
704 * different block now.
705 */
706 if ((error = xfs_alloc_split(cur, level, &nbno,
707 &nkey, &ncur, &i)))
708 return error;
709 if (i) {
710 bp = cur->bc_bufs[level];
711 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
712#ifdef DEBUG
713 if ((error =
714 xfs_btree_check_sblock(cur,
715 block, level, bp)))
716 return error;
717#endif
718 ptr = cur->bc_ptrs[level];
719 nrec.ar_startblock = nkey.ar_startblock; /* INT_: direct copy */
720 nrec.ar_blockcount = nkey.ar_blockcount; /* INT_: direct copy */
721 }
722 /*
723 * Otherwise the insert fails.
724 */
725 else {
726 *stat = 0;
727 return 0;
728 }
729 }
730 }
731 }
732 /*
733 * At this point we know there's room for our new entry in the block
734 * we're pointing at.
735 */
736 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
744 for (i = INT_GET(block->bb_numrecs, ARCH_CONVERT); i >= ptr; i--) {
745 if ((error = xfs_btree_check_sptr(cur, INT_GET(pp[i - 1], ARCH_CONVERT), level)))
746 return error;
747 }
748#endif
749 memmove(&kp[ptr], &kp[ptr - 1],
750 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*kp)); /* INT_: copy */
751 memmove(&pp[ptr], &pp[ptr - 1],
752 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*pp)); /* INT_: copy */
753#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;
761 INT_SET(pp[ptr - 1], ARCH_CONVERT, *bnop);
762 INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
763 xfs_alloc_log_keys(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
764 xfs_alloc_log_ptrs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
765#ifdef DEBUG
766 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
767 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
768 kp + ptr);
769#endif
770 } else {
771 /*
772 * It's a leaf entry. Make a hole for the new record.
773 */
774 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
775 memmove(&rp[ptr], &rp[ptr - 1],
776 (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*rp));
777 /*
778 * Now stuff the new record in, bump numrecs
779 * and log the new data.
780 */
781 rp[ptr - 1] = *recp; /* INT_: struct copy */
782 INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
783 xfs_alloc_log_recs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
784#ifdef DEBUG
785 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
786 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
787 rp + ptr);
788#endif
789 }
790 /*
791 * Log the new number of records in the btree header.
792 */
793 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
794 /*
795 * If we inserted at the start of a block, update the parents' keys.
796 */
797 if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
798 return error;
799 /*
800 * Look to see if the longest extent in the allocation group
801 * needs to be updated.
802 */
803
804 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
805 if (level == 0 &&
806 cur->bc_btnum == XFS_BTNUM_CNT &&
807 INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
808 INT_GET(recp->ar_blockcount, ARCH_CONVERT) > INT_GET(agf->agf_longest, ARCH_CONVERT)) {
809 /*
810 * If this is a leaf in the by-size btree and there
811 * is no right sibling block and this block is bigger
812 * than the previous longest block, update it.
813 */
814 INT_COPY(agf->agf_longest, recp->ar_blockcount, ARCH_CONVERT);
815 cur->bc_mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_longest
816 = INT_GET(recp->ar_blockcount, ARCH_CONVERT);
817 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
818 XFS_AGF_LONGEST);
819 }
820 /*
821 * Return the new block number, if any.
822 * If there is one, give back a record value and a cursor too.
823 */
824 *bnop = nbno;
825 if (nbno != NULLAGBLOCK) {
826 *recp = nrec; /* INT_: struct copy */
827 *curp = ncur; /* INT_: struct copy */
828 }
829 *stat = 1;
830 return 0;
831}
832
833/*
834 * Log header fields from a btree block.
835 */
836STATIC void
837xfs_alloc_log_block(
838 xfs_trans_t *tp, /* transaction pointer */
839 xfs_buf_t *bp, /* buffer containing btree block */
840 int fields) /* mask of fields: XFS_BB_... */
841{
842 int first; /* first byte offset logged */
843 int last; /* last byte offset logged */
844 static const short offsets[] = { /* table of offsets */
845 offsetof(xfs_alloc_block_t, bb_magic),
846 offsetof(xfs_alloc_block_t, bb_level),
847 offsetof(xfs_alloc_block_t, bb_numrecs),
848 offsetof(xfs_alloc_block_t, bb_leftsib),
849 offsetof(xfs_alloc_block_t, bb_rightsib),
850 sizeof(xfs_alloc_block_t)
851 };
852
853 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
854 xfs_trans_log_buf(tp, bp, first, last);
855}
856
857/*
858 * Log keys from a btree block (nonleaf).
859 */
860STATIC void
861xfs_alloc_log_keys(
862 xfs_btree_cur_t *cur, /* btree cursor */
863 xfs_buf_t *bp, /* buffer containing btree block */
864 int kfirst, /* index of first key to log */
865 int klast) /* index of last key to log */
866{
867 xfs_alloc_block_t *block; /* btree block to log from */
868 int first; /* first byte offset logged */
869 xfs_alloc_key_t *kp; /* key pointer in btree block */
870 int last; /* last byte offset logged */
871
872 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
873 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
874 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
875 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
876 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
877}
878
879/*
880 * Log block pointer fields from a btree block (nonleaf).
881 */
882STATIC void
883xfs_alloc_log_ptrs(
884 xfs_btree_cur_t *cur, /* btree cursor */
885 xfs_buf_t *bp, /* buffer containing btree block */
886 int pfirst, /* index of first pointer to log */
887 int plast) /* index of last pointer to log */
888{
889 xfs_alloc_block_t *block; /* btree block to log from */
890 int first; /* first byte offset logged */
891 int last; /* last byte offset logged */
892 xfs_alloc_ptr_t *pp; /* block-pointer pointer in btree blk */
893
894 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
895 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
896 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
897 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
898 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
899}
900
901/*
902 * Log records from a btree block (leaf).
903 */
904STATIC void
905xfs_alloc_log_recs(
906 xfs_btree_cur_t *cur, /* btree cursor */
907 xfs_buf_t *bp, /* buffer containing btree block */
908 int rfirst, /* index of first record to log */
909 int rlast) /* index of last record to log */
910{
911 xfs_alloc_block_t *block; /* btree block to log from */
912 int first; /* first byte offset logged */
913 int last; /* last byte offset logged */
914 xfs_alloc_rec_t *rp; /* record pointer for btree block */
915
916
917 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
918 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
919#ifdef DEBUG
920 {
921 xfs_agf_t *agf;
922 xfs_alloc_rec_t *p;
923
924 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
925 for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
926 ASSERT(INT_GET(p->ar_startblock, ARCH_CONVERT) + INT_GET(p->ar_blockcount, ARCH_CONVERT) <=
927 INT_GET(agf->agf_length, ARCH_CONVERT));
928 }
929#endif
930 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
931 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
932 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
933}
934
935/*
936 * Lookup the record. The cursor is made to point to it, based on dir.
937 * Return 0 if can't find any such record, 1 for success.
938 */
939STATIC int /* error */
940xfs_alloc_lookup(
941 xfs_btree_cur_t *cur, /* btree cursor */
942 xfs_lookup_t dir, /* <=, ==, or >= */
943 int *stat) /* success/failure */
944{
945 xfs_agblock_t agbno; /* a.g. relative btree block number */
946 xfs_agnumber_t agno; /* allocation group number */
947 xfs_alloc_block_t *block=NULL; /* current btree block */
948 int diff; /* difference for the current key */
949 int error; /* error return value */
950 int keyno=0; /* current key number */
951 int level; /* level in the btree */
952 xfs_mount_t *mp; /* file system mount point */
953
954 XFS_STATS_INC(xs_abt_lookup);
955 /*
956 * Get the allocation group header, and the root block number.
957 */
958 mp = cur->bc_mp;
959
960 {
961 xfs_agf_t *agf; /* a.g. freespace header */
962
963 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
964 agno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
965 agbno = INT_GET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT);
966 }
967 /*
968 * Iterate over each level in the btree, starting at the root.
969 * For each level above the leaves, find the key we need, based
970 * on the lookup record, then follow the corresponding block
971 * pointer down to the next level.
972 */
973 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
974 xfs_buf_t *bp; /* buffer pointer for btree block */
975 xfs_daddr_t d; /* disk address of btree block */
976
977 /*
978 * Get the disk address we're looking for.
979 */
980 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
981 /*
982 * If the old buffer at this level is for a different block,
983 * throw it away, otherwise just use it.
984 */
985 bp = cur->bc_bufs[level];
986 if (bp && XFS_BUF_ADDR(bp) != d)
987 bp = (xfs_buf_t *)0;
988 if (!bp) {
989 /*
990 * Need to get a new buffer. Read it, then
991 * set it in the cursor, releasing the old one.
992 */
993 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
994 agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
995 return error;
996 xfs_btree_setbuf(cur, level, bp);
997 /*
998 * Point to the btree block, now that we have the buffer
999 */
1000 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1001 if ((error = xfs_btree_check_sblock(cur, block, level,
1002 bp)))
1003 return error;
1004 } else
1005 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1006 /*
1007 * If we already had a key match at a higher level, we know
1008 * we need to use the first entry in this block.
1009 */
1010 if (diff == 0)
1011 keyno = 1;
1012 /*
1013 * Otherwise we need to search this block. Do a binary search.
1014 */
1015 else {
1016 int high; /* high entry number */
1017 xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
1018 xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
1019 int low; /* low entry number */
1020
1021 /*
1022 * Get a pointer to keys or records.
1023 */
1024 if (level > 0)
1025 kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
1026 else
1027 krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
1028 /*
1029 * Set low and high entry numbers, 1-based.
1030 */
1031 low = 1;
1032 if (!(high = INT_GET(block->bb_numrecs, ARCH_CONVERT))) {
1033 /*
1034 * If the block is empty, the tree must
1035 * be an empty leaf.
1036 */
1037 ASSERT(level == 0 && cur->bc_nlevels == 1);
1038 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1039 *stat = 0;
1040 return 0;
1041 }
1042 /*
1043 * Binary search the block.
1044 */
1045 while (low <= high) {
1046 xfs_extlen_t blockcount; /* key value */
1047 xfs_agblock_t startblock; /* key value */
1048
1049 XFS_STATS_INC(xs_abt_compare);
1050 /*
1051 * keyno is average of low and high.
1052 */
1053 keyno = (low + high) >> 1;
1054 /*
1055 * Get startblock & blockcount.
1056 */
1057 if (level > 0) {
1058 xfs_alloc_key_t *kkp;
1059
1060 kkp = kkbase + keyno - 1;
1061 startblock = INT_GET(kkp->ar_startblock, ARCH_CONVERT);
1062 blockcount = INT_GET(kkp->ar_blockcount, ARCH_CONVERT);
1063 } else {
1064 xfs_alloc_rec_t *krp;
1065
1066 krp = krbase + keyno - 1;
1067 startblock = INT_GET(krp->ar_startblock, ARCH_CONVERT);
1068 blockcount = INT_GET(krp->ar_blockcount, ARCH_CONVERT);
1069 }
1070 /*
1071 * Compute difference to get next direction.
1072 */
1073 if (cur->bc_btnum == XFS_BTNUM_BNO)
1074 diff = (int)startblock -
1075 (int)cur->bc_rec.a.ar_startblock;
1076 else if (!(diff = (int)blockcount -
1077 (int)cur->bc_rec.a.ar_blockcount))
1078 diff = (int)startblock -
1079 (int)cur->bc_rec.a.ar_startblock;
1080 /*
1081 * Less than, move right.
1082 */
1083 if (diff < 0)
1084 low = keyno + 1;
1085 /*
1086 * Greater than, move left.
1087 */
1088 else if (diff > 0)
1089 high = keyno - 1;
1090 /*
1091 * Equal, we're done.
1092 */
1093 else
1094 break;
1095 }
1096 }
1097 /*
1098 * If there are more levels, set up for the next level
1099 * by getting the block number and filling in the cursor.
1100 */
1101 if (level > 0) {
1102 /*
1103 * If we moved left, need the previous key number,
1104 * unless there isn't one.
1105 */
1106 if (diff > 0 && --keyno < 1)
1107 keyno = 1;
1108 agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, keyno, cur), ARCH_CONVERT);
1109#ifdef DEBUG
1110 if ((error = xfs_btree_check_sptr(cur, agbno, level)))
1111 return error;
1112#endif
1113 cur->bc_ptrs[level] = keyno;
1114 }
1115 }
1116 /*
1117 * Done with the search.
1118 * See if we need to adjust the results.
1119 */
1120 if (dir != XFS_LOOKUP_LE && diff < 0) {
1121 keyno++;
1122 /*
1123 * If ge search and we went off the end of the block, but it's
1124 * not the last block, we're in the wrong block.
1125 */
1126 if (dir == XFS_LOOKUP_GE &&
1127 keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT) &&
1128 INT_GET(block->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1129 int i;
1130
1131 cur->bc_ptrs[0] = keyno;
1132 if ((error = xfs_alloc_increment(cur, 0, &i)))
1133 return error;
1134 XFS_WANT_CORRUPTED_RETURN(i == 1);
1135 *stat = 1;
1136 return 0;
1137 }
1138 }
1139 else if (dir == XFS_LOOKUP_LE && diff > 0)
1140 keyno--;
1141 cur->bc_ptrs[0] = keyno;
1142 /*
1143 * Return if we succeeded or not.
1144 */
1145 if (keyno == 0 || keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT))
1146 *stat = 0;
1147 else
1148 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1149 return 0;
1150}
1151
1152/*
1153 * Move 1 record left from cur/level if possible.
1154 * Update cur to reflect the new path.
1155 */
1156STATIC int /* error */
1157xfs_alloc_lshift(
1158 xfs_btree_cur_t *cur, /* btree cursor */
1159 int level, /* level to shift record on */
1160 int *stat) /* success/failure */
1161{
1162 int error; /* error return value */
1163#ifdef DEBUG
1164 int i; /* loop index */
1165#endif
1166 xfs_alloc_key_t key; /* key value for leaf level upward */
1167 xfs_buf_t *lbp; /* buffer for left neighbor block */
1168 xfs_alloc_block_t *left; /* left neighbor btree block */
1169 int nrec; /* new number of left block entries */
1170 xfs_buf_t *rbp; /* buffer for right (current) block */
1171 xfs_alloc_block_t *right; /* right (current) btree block */
1172 xfs_alloc_key_t *rkp=NULL; /* key pointer for right block */
1173 xfs_alloc_ptr_t *rpp=NULL; /* address pointer for right block */
1174 xfs_alloc_rec_t *rrp=NULL; /* record pointer for right block */
1175
1176 /*
1177 * Set up variables for this block as "right".
1178 */
1179 rbp = cur->bc_bufs[level];
1180 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1181#ifdef DEBUG
1182 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1183 return error;
1184#endif
1185 /*
1186 * If we've got no left sibling then we can't shift an entry left.
1187 */
1188 if (INT_GET(right->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK) {
1189 *stat = 0;
1190 return 0;
1191 }
1192 /*
1193 * If the cursor entry is the one that would be moved, don't
1194 * do it... it's too complicated.
1195 */
1196 if (cur->bc_ptrs[level] <= 1) {
1197 *stat = 0;
1198 return 0;
1199 }
1200 /*
1201 * Set up the left neighbor as "left".
1202 */
1203 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1204 cur->bc_private.a.agno, INT_GET(right->bb_leftsib, ARCH_CONVERT), 0, &lbp,
1205 XFS_ALLOC_BTREE_REF)))
1206 return error;
1207 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1208 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1209 return error;
1210 /*
1211 * If it's full, it can't take another entry.
1212 */
1213 if (INT_GET(left->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1214 *stat = 0;
1215 return 0;
1216 }
1217 nrec = INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1;
1218 /*
1219 * If non-leaf, copy a key and a ptr to the left block.
1220 */
1221 if (level > 0) {
1222 xfs_alloc_key_t *lkp; /* key pointer for left block */
1223 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1224
1225 lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
1226 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1227 *lkp = *rkp;
1228 xfs_alloc_log_keys(cur, lbp, nrec, nrec);
1229 lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
1230 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1231#ifdef DEBUG
1232 if ((error = xfs_btree_check_sptr(cur, INT_GET(*rpp, ARCH_CONVERT), level)))
1233 return error;
1234#endif
1235 *lpp = *rpp; /* INT_: copy */
1236 xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
1237 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
1238 }
1239 /*
1240 * If leaf, copy a record to the left block.
1241 */
1242 else {
1243 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1244
1245 lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
1246 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1247 *lrp = *rrp;
1248 xfs_alloc_log_recs(cur, lbp, nrec, nrec);
1249 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
1250 }
1251 /*
1252 * Bump and log left's numrecs, decrement and log right's numrecs.
1253 */
1254 INT_MOD(left->bb_numrecs, ARCH_CONVERT, +1);
1255 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1256 INT_MOD(right->bb_numrecs, ARCH_CONVERT, -1);
1257 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1258 /*
1259 * Slide the contents of right down one entry.
1260 */
1261 if (level > 0) {
1262#ifdef DEBUG
1263 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
1264 if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i + 1], ARCH_CONVERT),
1265 level)))
1266 return error;
1267 }
1268#endif
1269 memmove(rkp, rkp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1270 memmove(rpp, rpp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1271 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1272 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1273 } else {
1274 memmove(rrp, rrp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1275 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1276 key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1277 key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1278 rkp = &key;
1279 }
1280 /*
1281 * Update the parent key values of right.
1282 */
1283 if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
1284 return error;
1285 /*
1286 * Slide the cursor value left one.
1287 */
1288 cur->bc_ptrs[level]--;
1289 *stat = 1;
1290 return 0;
1291}
1292
1293/*
1294 * Allocate a new root block, fill it in.
1295 */
1296STATIC int /* error */
1297xfs_alloc_newroot(
1298 xfs_btree_cur_t *cur, /* btree cursor */
1299 int *stat) /* success/failure */
1300{
1301 int error; /* error return value */
1302 xfs_agblock_t lbno; /* left block number */
1303 xfs_buf_t *lbp; /* left btree buffer */
1304 xfs_alloc_block_t *left; /* left btree block */
1305 xfs_mount_t *mp; /* mount structure */
1306 xfs_agblock_t nbno; /* new block number */
1307 xfs_buf_t *nbp; /* new (root) buffer */
1308 xfs_alloc_block_t *new; /* new (root) btree block */
1309 int nptr; /* new value for key index, 1 or 2 */
1310 xfs_agblock_t rbno; /* right block number */
1311 xfs_buf_t *rbp; /* right btree buffer */
1312 xfs_alloc_block_t *right; /* right btree block */
1313
1314 mp = cur->bc_mp;
1315
1316 ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
1317 /*
1318 * Get a buffer from the freelist blocks, for the new root.
1319 */
1320 if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1321 &nbno)))
1322 return error;
1323 /*
1324 * None available, we fail.
1325 */
1326 if (nbno == NULLAGBLOCK) {
1327 *stat = 0;
1328 return 0;
1329 }
1330 xfs_trans_agbtree_delta(cur->bc_tp, 1);
1331 nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
1332 0);
1333 new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
1334 /*
1335 * Set the root data in the a.g. freespace structure.
1336 */
1337 {
1338 xfs_agf_t *agf; /* a.g. freespace header */
1339 xfs_agnumber_t seqno;
1340
1341 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
1342 INT_SET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT, nbno);
1343 INT_MOD(agf->agf_levels[cur->bc_btnum], ARCH_CONVERT, 1);
1344 seqno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
1345 mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
1346 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
1347 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
1348 }
1349 /*
1350 * At the previous root level there are now two blocks: the old
1351 * root, and the new block generated when it was split.
1352 * We don't know which one the cursor is pointing at, so we
1353 * set up variables "left" and "right" for each case.
1354 */
1355 lbp = cur->bc_bufs[cur->bc_nlevels - 1];
1356 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1357#ifdef DEBUG
1358 if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
1359 return error;
1360#endif
1361 if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1362 /*
1363 * Our block is left, pick up the right block.
1364 */
1365 lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
1366 rbno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
1367 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1368 cur->bc_private.a.agno, rbno, 0, &rbp,
1369 XFS_ALLOC_BTREE_REF)))
1370 return error;
1371 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1372 if ((error = xfs_btree_check_sblock(cur, right,
1373 cur->bc_nlevels - 1, rbp)))
1374 return error;
1375 nptr = 1;
1376 } else {
1377 /*
1378 * Our block is right, pick up the left block.
1379 */
1380 rbp = lbp;
1381 right = left;
1382 rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
1383 lbno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
1384 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1385 cur->bc_private.a.agno, lbno, 0, &lbp,
1386 XFS_ALLOC_BTREE_REF)))
1387 return error;
1388 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1389 if ((error = xfs_btree_check_sblock(cur, left,
1390 cur->bc_nlevels - 1, lbp)))
1391 return error;
1392 nptr = 2;
1393 }
1394 /*
1395 * Fill in the new block's btree header and log it.
1396 */
1397 INT_SET(new->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
1398 INT_SET(new->bb_level, ARCH_CONVERT, (__uint16_t)cur->bc_nlevels);
1399 INT_SET(new->bb_numrecs, ARCH_CONVERT, 2);
1400 INT_SET(new->bb_leftsib, ARCH_CONVERT, NULLAGBLOCK);
1401 INT_SET(new->bb_rightsib, ARCH_CONVERT, NULLAGBLOCK);
1402 xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
1403 ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
1404 /*
1405 * Fill in the key data in the new root.
1406 */
1407 {
1408 xfs_alloc_key_t *kp; /* btree key pointer */
1409
1410 kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
1411 if (INT_GET(left->bb_level, ARCH_CONVERT) > 0) {
1412 kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur); /* INT_: structure copy */
1413 kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);/* INT_: structure copy */
1414 } else {
1415 xfs_alloc_rec_t *rp; /* btree record pointer */
1416
1417 rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
1418 kp[0].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
1419 kp[0].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
1420 rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1421 kp[1].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
1422 kp[1].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
1423 }
1424 }
1425 xfs_alloc_log_keys(cur, nbp, 1, 2);
1426 /*
1427 * Fill in the pointer data in the new root.
1428 */
1429 {
1430 xfs_alloc_ptr_t *pp; /* btree address pointer */
1431
1432 pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
1433 INT_SET(pp[0], ARCH_CONVERT, lbno);
1434 INT_SET(pp[1], ARCH_CONVERT, rbno);
1435 }
1436 xfs_alloc_log_ptrs(cur, nbp, 1, 2);
1437 /*
1438 * Fix up the cursor.
1439 */
1440 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
1441 cur->bc_ptrs[cur->bc_nlevels] = nptr;
1442 cur->bc_nlevels++;
1443 *stat = 1;
1444 return 0;
1445}
1446
1447/*
1448 * Move 1 record right from cur/level if possible.
1449 * Update cur to reflect the new path.
1450 */
1451STATIC int /* error */
1452xfs_alloc_rshift(
1453 xfs_btree_cur_t *cur, /* btree cursor */
1454 int level, /* level to shift record on */
1455 int *stat) /* success/failure */
1456{
1457 int error; /* error return value */
1458 int i; /* loop index */
1459 xfs_alloc_key_t key; /* key value for leaf level upward */
1460 xfs_buf_t *lbp; /* buffer for left (current) block */
1461 xfs_alloc_block_t *left; /* left (current) btree block */
1462 xfs_buf_t *rbp; /* buffer for right neighbor block */
1463 xfs_alloc_block_t *right; /* right neighbor btree block */
1464 xfs_alloc_key_t *rkp; /* key pointer for right block */
1465 xfs_btree_cur_t *tcur; /* temporary cursor */
1466
1467 /*
1468 * Set up variables for this block as "left".
1469 */
1470 lbp = cur->bc_bufs[level];
1471 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1472#ifdef DEBUG
1473 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1474 return error;
1475#endif
1476 /*
1477 * If we've got no right sibling then we can't shift an entry right.
1478 */
1479 if (INT_GET(left->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK) {
1480 *stat = 0;
1481 return 0;
1482 }
1483 /*
1484 * If the cursor entry is the one that would be moved, don't
1485 * do it... it's too complicated.
1486 */
1487 if (cur->bc_ptrs[level] >= INT_GET(left->bb_numrecs, ARCH_CONVERT)) {
1488 *stat = 0;
1489 return 0;
1490 }
1491 /*
1492 * Set up the right neighbor as "right".
1493 */
1494 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1495 cur->bc_private.a.agno, INT_GET(left->bb_rightsib, ARCH_CONVERT), 0, &rbp,
1496 XFS_ALLOC_BTREE_REF)))
1497 return error;
1498 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1499 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1500 return error;
1501 /*
1502 * If it's full, it can't take another entry.
1503 */
1504 if (INT_GET(right->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1505 *stat = 0;
1506 return 0;
1507 }
1508 /*
1509 * Make a hole at the start of the right neighbor block, then
1510 * copy the last left block entry to the hole.
1511 */
1512 if (level > 0) {
1513 xfs_alloc_key_t *lkp; /* key pointer for left block */
1514 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1515 xfs_alloc_ptr_t *rpp; /* address pointer for right block */
1516
1517 lkp = XFS_ALLOC_KEY_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1518 lpp = XFS_ALLOC_PTR_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1519 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1520 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1521#ifdef DEBUG
1522 for (i = INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1; i >= 0; i--) {
1523 if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level)))
1524 return error;
1525 }
1526#endif
1527 memmove(rkp + 1, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1528 memmove(rpp + 1, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1529#ifdef DEBUG
1530 if ((error = xfs_btree_check_sptr(cur, INT_GET(*lpp, ARCH_CONVERT), level)))
1531 return error;
1532#endif
1533 *rkp = *lkp; /* INT_: copy */
1534 *rpp = *lpp; /* INT_: copy */
1535 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1536 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1537 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1538 } else {
1539 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1540 xfs_alloc_rec_t *rrp; /* record pointer for right block */
1541
1542 lrp = XFS_ALLOC_REC_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1543 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1544 memmove(rrp + 1, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1545 *rrp = *lrp;
1546 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1547 key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1548 key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1549 rkp = &key;
1550 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1551 }
1552 /*
1553 * Decrement and log left's numrecs, bump and log right's numrecs.
1554 */
1555 INT_MOD(left->bb_numrecs, ARCH_CONVERT, -1);
1556 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1557 INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1558 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1559 /*
1560 * Using a temporary cursor, update the parent key values of the
1561 * block on the right.
1562 */
1563 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1564 return error;
1565 i = xfs_btree_lastrec(tcur, level);
1566 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1567 if ((error = xfs_alloc_increment(tcur, level, &i)) ||
1568 (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
1569 goto error0;
1570 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1571 *stat = 1;
1572 return 0;
1573error0:
1574 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1575 return error;
1576}
1577
1578/*
1579 * Split cur/level block in half.
1580 * Return new block number and its first record (to be inserted into parent).
1581 */
1582STATIC int /* error */
1583xfs_alloc_split(
1584 xfs_btree_cur_t *cur, /* btree cursor */
1585 int level, /* level to split */
1586 xfs_agblock_t *bnop, /* output: block number allocated */
1587 xfs_alloc_key_t *keyp, /* output: first key of new block */
1588 xfs_btree_cur_t **curp, /* output: new cursor */
1589 int *stat) /* success/failure */
1590{
1591 int error; /* error return value */
1592 int i; /* loop index/record number */
1593 xfs_agblock_t lbno; /* left (current) block number */
1594 xfs_buf_t *lbp; /* buffer for left block */
1595 xfs_alloc_block_t *left; /* left (current) btree block */
1596 xfs_agblock_t rbno; /* right (new) block number */
1597 xfs_buf_t *rbp; /* buffer for right block */
1598 xfs_alloc_block_t *right; /* right (new) btree block */
1599
1600 /*
1601 * Allocate the new block from the freelist.
1602 * If we can't do it, we're toast. Give up.
1603 */
1604 if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1605 &rbno)))
1606 return error;
1607 if (rbno == NULLAGBLOCK) {
1608 *stat = 0;
1609 return 0;
1610 }
1611 xfs_trans_agbtree_delta(cur->bc_tp, 1);
1612 rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
1613 rbno, 0);
1614 /*
1615 * Set up the new block as "right".
1616 */
1617 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1618 /*
1619 * "Left" is the current (according to the cursor) block.
1620 */
1621 lbp = cur->bc_bufs[level];
1622 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1623#ifdef DEBUG
1624 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1625 return error;
1626#endif
1627 /*
1628 * Fill in the btree header for the new block.
1629 */
1630 INT_SET(right->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
1631 right->bb_level = left->bb_level; /* INT_: direct copy */
1632 INT_SET(right->bb_numrecs, ARCH_CONVERT, (__uint16_t)(INT_GET(left->bb_numrecs, ARCH_CONVERT) / 2));
1633 /*
1634 * Make sure that if there's an odd number of entries now, that
1635 * each new block will have the same number of entries.
1636 */
1637 if ((INT_GET(left->bb_numrecs, ARCH_CONVERT) & 1) &&
1638 cur->bc_ptrs[level] <= INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1)
1639 INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1640 i = INT_GET(left->bb_numrecs, ARCH_CONVERT) - INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1;
1641 /*
1642 * For non-leaf blocks, copy keys and addresses over to the new block.
1643 */
1644 if (level > 0) {
1645 xfs_alloc_key_t *lkp; /* left btree key pointer */
1646 xfs_alloc_ptr_t *lpp; /* left btree address pointer */
1647 xfs_alloc_key_t *rkp; /* right btree key pointer */
1648 xfs_alloc_ptr_t *rpp; /* right btree address pointer */
1649
1650 lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
1651 lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
1652 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1653 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1654#ifdef DEBUG
1655 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
1656 if ((error = xfs_btree_check_sptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level)))
1657 return error;
1658 }
1659#endif
1660 memcpy(rkp, lkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp)); /* INT_: copy */
1661 memcpy(rpp, lpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp)); /* INT_: copy */
1662 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1663 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1664 *keyp = *rkp;
1665 }
1666 /*
1667 * For leaf blocks, copy records over to the new block.
1668 */
1669 else {
1670 xfs_alloc_rec_t *lrp; /* left btree record pointer */
1671 xfs_alloc_rec_t *rrp; /* right btree record pointer */
1672
1673 lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
1674 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1675 memcpy(rrp, lrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1676 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1677 keyp->ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1678 keyp->ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1679 }
1680 /*
1681 * Find the left block number by looking in the buffer.
1682 * Adjust numrecs, sibling pointers.
1683 */
1684 lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
1685 INT_MOD(left->bb_numrecs, ARCH_CONVERT, -(INT_GET(right->bb_numrecs, ARCH_CONVERT)));
1686 right->bb_rightsib = left->bb_rightsib; /* INT_: direct copy */
1687 INT_SET(left->bb_rightsib, ARCH_CONVERT, rbno);
1688 INT_SET(right->bb_leftsib, ARCH_CONVERT, lbno);
1689 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
1690 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1691 /*
1692 * If there's a block to the new block's right, make that block
1693 * point back to right instead of to left.
1694 */
1695 if (INT_GET(right->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1696 xfs_alloc_block_t *rrblock; /* rr btree block */
1697 xfs_buf_t *rrbp; /* buffer for rrblock */
1698
1699 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1700 cur->bc_private.a.agno, INT_GET(right->bb_rightsib, ARCH_CONVERT), 0,
1701 &rrbp, XFS_ALLOC_BTREE_REF)))
1702 return error;
1703 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
1704 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1705 return error;
1706 INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, rbno);
1707 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
1708 }
1709 /*
1710 * If the cursor is really in the right block, move it there.
1711 * If it's just pointing past the last entry in left, then we'll
1712 * insert there, so don't change anything in that case.
1713 */
1714 if (cur->bc_ptrs[level] > INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1) {
1715 xfs_btree_setbuf(cur, level, rbp);
1716 cur->bc_ptrs[level] -= INT_GET(left->bb_numrecs, ARCH_CONVERT);
1717 }
1718 /*
1719 * If there are more levels, we'll need another cursor which refers to
1720 * the right block, no matter where this cursor was.
1721 */
1722 if (level + 1 < cur->bc_nlevels) {
1723 if ((error = xfs_btree_dup_cursor(cur, curp)))
1724 return error;
1725 (*curp)->bc_ptrs[level + 1]++;
1726 }
1727 *bnop = rbno;
1728 *stat = 1;
1729 return 0;
1730}
1731
1732/*
1733 * Update keys at all levels from here to the root along the cursor's path.
1734 */
1735STATIC int /* error */
1736xfs_alloc_updkey(
1737 xfs_btree_cur_t *cur, /* btree cursor */
1738 xfs_alloc_key_t *keyp, /* new key value to update to */
1739 int level) /* starting level for update */
1740{
1741 int ptr; /* index of key in block */
1742
1743 /*
1744 * Go up the tree from this level toward the root.
1745 * At each level, update the key value to the value input.
1746 * Stop when we reach a level where the cursor isn't pointing
1747 * at the first entry in the block.
1748 */
1749 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1750 xfs_alloc_block_t *block; /* btree block */
1751 xfs_buf_t *bp; /* buffer for block */
1752#ifdef DEBUG
1753 int error; /* error return value */
1754#endif
1755 xfs_alloc_key_t *kp; /* ptr to btree block keys */
1756
1757 bp = cur->bc_bufs[level];
1758 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1759#ifdef DEBUG
1760 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1761 return error;
1762#endif
1763 ptr = cur->bc_ptrs[level];
1764 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
1765 *kp = *keyp;
1766 xfs_alloc_log_keys(cur, bp, ptr, ptr);
1767 }
1768 return 0;
1769}
1770
1771/*
1772 * Externally visible routines.
1773 */
1774
1775/*
1776 * Decrement cursor by one record at the level.
1777 * For nonzero levels the leaf-ward information is untouched.
1778 */
1779int /* error */
1780xfs_alloc_decrement(
1781 xfs_btree_cur_t *cur, /* btree cursor */
1782 int level, /* level in btree, 0 is leaf */
1783 int *stat) /* success/failure */
1784{
1785 xfs_alloc_block_t *block; /* btree block */
1786 int error; /* error return value */
1787 int lev; /* btree level */
1788
1789 ASSERT(level < cur->bc_nlevels);
1790 /*
1791 * Read-ahead to the left at this level.
1792 */
1793 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1794 /*
1795 * Decrement the ptr at this level. If we're still in the block
1796 * then we're done.
1797 */
1798 if (--cur->bc_ptrs[level] > 0) {
1799 *stat = 1;
1800 return 0;
1801 }
1802 /*
1803 * Get a pointer to the btree block.
1804 */
1805 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[level]);
1806#ifdef DEBUG
1807 if ((error = xfs_btree_check_sblock(cur, block, level,
1808 cur->bc_bufs[level])))
1809 return error;
1810#endif
1811 /*
1812 * If we just went off the left edge of the tree, return failure.
1813 */
1814 if (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK) {
1815 *stat = 0;
1816 return 0;
1817 }
1818 /*
1819 * March up the tree decrementing pointers.
1820 * Stop when we don't go off the left edge of a block.
1821 */
1822 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1823 if (--cur->bc_ptrs[lev] > 0)
1824 break;
1825 /*
1826 * Read-ahead the left block, we're going to read it
1827 * in the next loop.
1828 */
1829 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1830 }
1831 /*
1832 * If we went off the root then we are seriously confused.
1833 */
1834 ASSERT(lev < cur->bc_nlevels);
1835 /*
1836 * Now walk back down the tree, fixing up the cursor's buffer
1837 * pointers and key numbers.
1838 */
1839 for (block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
1840 xfs_agblock_t agbno; /* block number of btree block */
1841 xfs_buf_t *bp; /* buffer pointer for block */
1842
1843 agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
1844 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1845 cur->bc_private.a.agno, agbno, 0, &bp,
1846 XFS_ALLOC_BTREE_REF)))
1847 return error;
1848 lev--;
1849 xfs_btree_setbuf(cur, lev, bp);
1850 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1851 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1852 return error;
1853 cur->bc_ptrs[lev] = INT_GET(block->bb_numrecs, ARCH_CONVERT);
1854 }
1855 *stat = 1;
1856 return 0;
1857}
1858
1859/*
1860 * Delete the record pointed to by cur.
1861 * The cursor refers to the place where the record was (could be inserted)
1862 * when the operation returns.
1863 */
1864int /* error */
1865xfs_alloc_delete(
1866 xfs_btree_cur_t *cur, /* btree cursor */
1867 int *stat) /* success/failure */
1868{
1869 int error; /* error return value */
1870 int i; /* result code */
1871 int level; /* btree level */
1872
1873 /*
1874 * Go up the tree, starting at leaf level.
1875 * If 2 is returned then a join was done; go to the next level.
1876 * Otherwise we are done.
1877 */
1878 for (level = 0, i = 2; i == 2; level++) {
1879 if ((error = xfs_alloc_delrec(cur, level, &i)))
1880 return error;
1881 }
1882 if (i == 0) {
1883 for (level = 1; level < cur->bc_nlevels; level++) {
1884 if (cur->bc_ptrs[level] == 0) {
1885 if ((error = xfs_alloc_decrement(cur, level, &i)))
1886 return error;
1887 break;
1888 }
1889 }
1890 }
1891 *stat = i;
1892 return 0;
1893}
1894
1895/*
1896 * Get the data from the pointed-to record.
1897 */
1898int /* error */
1899xfs_alloc_get_rec(
1900 xfs_btree_cur_t *cur, /* btree cursor */
1901 xfs_agblock_t *bno, /* output: starting block of extent */
1902 xfs_extlen_t *len, /* output: length of extent */
1903 int *stat) /* output: success/failure */
1904{
1905 xfs_alloc_block_t *block; /* btree block */
1906#ifdef DEBUG
1907 int error; /* error return value */
1908#endif
1909 int ptr; /* record number */
1910
1911 ptr = cur->bc_ptrs[0];
1912 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
1913#ifdef DEBUG
1914 if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
1915 return error;
1916#endif
1917 /*
1918 * Off the right end or left end, return failure.
1919 */
1920 if (ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT) || ptr <= 0) {
1921 *stat = 0;
1922 return 0;
1923 }
1924 /*
1925 * Point to the record and extract its data.
1926 */
1927 {
1928 xfs_alloc_rec_t *rec; /* record data */
1929
1930 rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
1931 *bno = INT_GET(rec->ar_startblock, ARCH_CONVERT);
1932 *len = INT_GET(rec->ar_blockcount, ARCH_CONVERT);
1933 }
1934 *stat = 1;
1935 return 0;
1936}
1937
1938/*
1939 * Increment cursor by one record at the level.
1940 * For nonzero levels the leaf-ward information is untouched.
1941 */
1942int /* error */
1943xfs_alloc_increment(
1944 xfs_btree_cur_t *cur, /* btree cursor */
1945 int level, /* level in btree, 0 is leaf */
1946 int *stat) /* success/failure */
1947{
1948 xfs_alloc_block_t *block; /* btree block */
1949 xfs_buf_t *bp; /* tree block buffer */
1950 int error; /* error return value */
1951 int lev; /* btree level */
1952
1953 ASSERT(level < cur->bc_nlevels);
1954 /*
1955 * Read-ahead to the right at this level.
1956 */
1957 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1958 /*
1959 * Get a pointer to the btree block.
1960 */
1961 bp = cur->bc_bufs[level];
1962 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1963#ifdef DEBUG
1964 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1965 return error;
1966#endif
1967 /*
1968 * Increment the ptr at this level. If we're still in the block
1969 * then we're done.
1970 */
1971 if (++cur->bc_ptrs[level] <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
1972 *stat = 1;
1973 return 0;
1974 }
1975 /*
1976 * If we just went off the right edge of the tree, return failure.
1977 */
1978 if (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK) {
1979 *stat = 0;
1980 return 0;
1981 }
1982 /*
1983 * March up the tree incrementing pointers.
1984 * Stop when we don't go off the right edge of a block.
1985 */
1986 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1987 bp = cur->bc_bufs[lev];
1988 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1989#ifdef DEBUG
1990 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1991 return error;
1992#endif
1993 if (++cur->bc_ptrs[lev] <= INT_GET(block->bb_numrecs, ARCH_CONVERT))
1994 break;
1995 /*
1996 * Read-ahead the right block, we're going to read it
1997 * in the next loop.
1998 */
1999 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2000 }
2001 /*
2002 * If we went off the root then we are seriously confused.
2003 */
2004 ASSERT(lev < cur->bc_nlevels);
2005 /*
2006 * Now walk back down the tree, fixing up the cursor's buffer
2007 * pointers and key numbers.
2008 */
2009 for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2010 lev > level; ) {
2011 xfs_agblock_t agbno; /* block number of btree block */
2012
2013 agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
2014 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
2015 cur->bc_private.a.agno, agbno, 0, &bp,
2016 XFS_ALLOC_BTREE_REF)))
2017 return error;
2018 lev--;
2019 xfs_btree_setbuf(cur, lev, bp);
2020 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2021 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
2022 return error;
2023 cur->bc_ptrs[lev] = 1;
2024 }
2025 *stat = 1;
2026 return 0;
2027}
2028
2029/*
2030 * Insert the current record at the point referenced by cur.
2031 * The cursor may be inconsistent on return if splits have been done.
2032 */
2033int /* error */
2034xfs_alloc_insert(
2035 xfs_btree_cur_t *cur, /* btree cursor */
2036 int *stat) /* success/failure */
2037{
2038 int error; /* error return value */
2039 int i; /* result value, 0 for failure */
2040 int level; /* current level number in btree */
2041 xfs_agblock_t nbno; /* new block number (split result) */
2042 xfs_btree_cur_t *ncur; /* new cursor (split result) */
2043 xfs_alloc_rec_t nrec; /* record being inserted this level */
2044 xfs_btree_cur_t *pcur; /* previous level's cursor */
2045
2046 level = 0;
2047 nbno = NULLAGBLOCK;
2048 INT_SET(nrec.ar_startblock, ARCH_CONVERT, cur->bc_rec.a.ar_startblock);
2049 INT_SET(nrec.ar_blockcount, ARCH_CONVERT, cur->bc_rec.a.ar_blockcount);
2050 ncur = (xfs_btree_cur_t *)0;
2051 pcur = cur;
2052 /*
2053 * Loop going up the tree, starting at the leaf level.
2054 * Stop when we don't get a split block, that must mean that
2055 * the insert is finished with this level.
2056 */
2057 do {
2058 /*
2059 * Insert nrec/nbno into this level of the tree.
2060 * Note if we fail, nbno will be null.
2061 */
2062 if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
2063 &i))) {
2064 if (pcur != cur)
2065 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2066 return error;
2067 }
2068 /*
2069 * See if the cursor we just used is trash.
2070 * Can't trash the caller's cursor, but otherwise we should
2071 * if ncur is a new cursor or we're about to be done.
2072 */
2073 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
2074 cur->bc_nlevels = pcur->bc_nlevels;
2075 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2076 }
2077 /*
2078 * If we got a new cursor, switch to it.
2079 */
2080 if (ncur) {
2081 pcur = ncur;
2082 ncur = (xfs_btree_cur_t *)0;
2083 }
2084 } while (nbno != NULLAGBLOCK);
2085 *stat = i;
2086 return 0;
2087}
2088
2089/*
2090 * Lookup the record equal to [bno, len] in the btree given by cur.
2091 */
2092int /* error */
2093xfs_alloc_lookup_eq(
2094 xfs_btree_cur_t *cur, /* btree cursor */
2095 xfs_agblock_t bno, /* starting block of extent */
2096 xfs_extlen_t len, /* length of extent */
2097 int *stat) /* success/failure */
2098{
2099 cur->bc_rec.a.ar_startblock = bno;
2100 cur->bc_rec.a.ar_blockcount = len;
2101 return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
2102}
2103
2104/*
2105 * Lookup the first record greater than or equal to [bno, len]
2106 * in the btree given by cur.
2107 */
2108int /* error */
2109xfs_alloc_lookup_ge(
2110 xfs_btree_cur_t *cur, /* btree cursor */
2111 xfs_agblock_t bno, /* starting block of extent */
2112 xfs_extlen_t len, /* length of extent */
2113 int *stat) /* success/failure */
2114{
2115 cur->bc_rec.a.ar_startblock = bno;
2116 cur->bc_rec.a.ar_blockcount = len;
2117 return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
2118}
2119
2120/*
2121 * Lookup the first record less than or equal to [bno, len]
2122 * in the btree given by cur.
2123 */
2124int /* error */
2125xfs_alloc_lookup_le(
2126 xfs_btree_cur_t *cur, /* btree cursor */
2127 xfs_agblock_t bno, /* starting block of extent */
2128 xfs_extlen_t len, /* length of extent */
2129 int *stat) /* success/failure */
2130{
2131 cur->bc_rec.a.ar_startblock = bno;
2132 cur->bc_rec.a.ar_blockcount = len;
2133 return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
2134}
2135
2136/*
2137 * Update the record referred to by cur, to the value given by [bno, len].
2138 * This either works (return 0) or gets an EFSCORRUPTED error.
2139 */
2140int /* error */
2141xfs_alloc_update(
2142 xfs_btree_cur_t *cur, /* btree cursor */
2143 xfs_agblock_t bno, /* starting block of extent */
2144 xfs_extlen_t len) /* length of extent */
2145{
2146 xfs_alloc_block_t *block; /* btree block to update */
2147 int error; /* error return value */
2148 int ptr; /* current record number (updating) */
2149
2150 ASSERT(len > 0);
2151 /*
2152 * Pick up the a.g. freelist struct and the current block.
2153 */
2154 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
2155#ifdef DEBUG
2156 if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
2157 return error;
2158#endif
2159 /*
2160 * Get the address of the rec to be updated.
2161 */
2162 ptr = cur->bc_ptrs[0];
2163 {
2164 xfs_alloc_rec_t *rp; /* pointer to updated record */
2165
2166 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
2167 /*
2168 * Fill in the new contents and log them.
2169 */
2170 INT_SET(rp->ar_startblock, ARCH_CONVERT, bno);
2171 INT_SET(rp->ar_blockcount, ARCH_CONVERT, len);
2172 xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
2173 }
2174 /*
2175 * If it's the by-size btree and it's the last leaf block and
2176 * it's the last record... then update the size of the longest
2177 * extent in the a.g., which we cache in the a.g. freelist header.
2178 */
2179 if (cur->bc_btnum == XFS_BTNUM_CNT &&
2180 INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
2181 ptr == INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
2182 xfs_agf_t *agf; /* a.g. freespace header */
2183 xfs_agnumber_t seqno;
2184
2185 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
2186 seqno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
2187 cur->bc_mp->m_perag[seqno].pagf_longest = len;
2188 INT_SET(agf->agf_longest, ARCH_CONVERT, len);
2189 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
2190 XFS_AGF_LONGEST);
2191 }
2192 /*
2193 * Updating first record in leaf. Pass new key value up to our parent.
2194 */
2195 if (ptr == 1) {
2196 xfs_alloc_key_t key; /* key containing [bno, len] */
2197
2198 INT_SET(key.ar_startblock, ARCH_CONVERT, bno);
2199 INT_SET(key.ar_blockcount, ARCH_CONVERT, len);
2200 if ((error = xfs_alloc_updkey(cur, &key, 1)))
2201 return error;
2202 }
2203 return 0;
2204}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-29 03:09:22 -0500