]> git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_ialloc_btree.c
projects / thirdparty / xfsprogs-dev.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Sort out cosmetic differences between user and kernel copies of some sources.
[thirdparty/xfsprogs-dev.git] / libxfs / xfs_ialloc_btree.c
1 /*
2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19 /*
20 * Inode allocation management for XFS.
21 */
22
23 #include <xfs.h>
24
25 /*
26 * Insert one record/level. Return information to the caller
27 * allowing the next level up to proceed if necessary.
28 */
29 STATIC int /* error */
30 xfs_inobt_insrec(
31 xfs_btree_cur_t *cur, /* btree cursor */
32 int level, /* level to insert record at */
33 xfs_agblock_t *bnop, /* i/o: block number inserted */
34 xfs_inobt_rec_t *recp, /* i/o: record data inserted */
35 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
36 int *stat) /* success/failure */
37 {
38 xfs_inobt_block_t *block; /* btree block record/key lives in */
39 xfs_buf_t *bp; /* buffer for block */
40 int error; /* error return value */
41 int i; /* loop index */
42 xfs_inobt_key_t key; /* key value being inserted */
43 xfs_inobt_key_t *kp=NULL; /* pointer to btree keys */
44 xfs_agblock_t nbno; /* block number of allocated block */
45 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
46 xfs_inobt_key_t nkey; /* new key value, from split */
47 xfs_inobt_rec_t nrec; /* new record value, for caller */
48 int numrecs;
49 int optr; /* old ptr value */
50 xfs_inobt_ptr_t *pp; /* pointer to btree addresses */
51 int ptr; /* index in btree block for this rec */
52 xfs_inobt_rec_t *rp=NULL; /* pointer to btree records */
53
54 /*
55 * GCC doesn't understand the (arguably complex) control flow in
56 * this function and complains about uninitialized structure fields
57 * without this.
58 */
59 memset(&nrec, 0, sizeof(nrec));
60
61 /*
62 * If we made it to the root level, allocate a new root block
63 * and we're done.
64 */
65 if (level >= cur->bc_nlevels) {
66 error = xfs_inobt_newroot(cur, &i);
67 *bnop = NULLAGBLOCK;
68 *stat = i;
69 return error;
70 }
71 /*
72 * Make a key out of the record data to be inserted, and save it.
73 */
74 key.ir_startino = recp->ir_startino; /* INT_: direct copy */
75 optr = ptr = cur->bc_ptrs[level];
76 /*
77 * If we're off the left edge, return failure.
78 */
79 if (ptr == 0) {
80 *stat = 0;
81 return 0;
82 }
83 /*
84 * Get pointers to the btree buffer and block.
85 */
86 bp = cur->bc_bufs[level];
87 block = XFS_BUF_TO_INOBT_BLOCK(bp);
88 numrecs = be16_to_cpu(block->bb_numrecs);
89 #ifdef DEBUG
90 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
91 return error;
92 /*
93 * Check that the new entry is being inserted in the right place.
94 */
95 if (ptr <= numrecs) {
96 if (level == 0) {
97 rp = XFS_INOBT_REC_ADDR(block, ptr, cur);
98 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
99 } else {
100 kp = XFS_INOBT_KEY_ADDR(block, ptr, cur);
101 xfs_btree_check_key(cur->bc_btnum, &key, kp);
102 }
103 }
104 #endif
105 nbno = NULLAGBLOCK;
106 ncur = (xfs_btree_cur_t *)0;
107 /*
108 * If the block is full, we can't insert the new entry until we
109 * make the block un-full.
110 */
111 if (numrecs == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
112 /*
113 * First, try shifting an entry to the right neighbor.
114 */
115 if ((error = xfs_inobt_rshift(cur, level, &i)))
116 return error;
117 if (i) {
118 /* nothing */
119 }
120 /*
121 * Next, try shifting an entry to the left neighbor.
122 */
123 else {
124 if ((error = xfs_inobt_lshift(cur, level, &i)))
125 return error;
126 if (i) {
127 optr = ptr = cur->bc_ptrs[level];
128 } else {
129 /*
130 * Next, try splitting the current block
131 * in half. If this works we have to
132 * re-set our variables because
133 * we could be in a different block now.
134 */
135 if ((error = xfs_inobt_split(cur, level, &nbno,
136 &nkey, &ncur, &i)))
137 return error;
138 if (i) {
139 bp = cur->bc_bufs[level];
140 block = XFS_BUF_TO_INOBT_BLOCK(bp);
141 #ifdef DEBUG
142 if ((error = xfs_btree_check_sblock(cur,
143 block, level, bp)))
144 return error;
145 #endif
146 ptr = cur->bc_ptrs[level];
147 nrec.ir_startino = nkey.ir_startino; /* INT_: direct copy */
148 } else {
149 /*
150 * Otherwise the insert fails.
151 */
152 *stat = 0;
153 return 0;
154 }
155 }
156 }
157 }
158 /*
159 * At this point we know there's room for our new entry in the block
160 * we're pointing at.
161 */
162 numrecs = be16_to_cpu(block->bb_numrecs);
163 if (level > 0) {
164 /*
165 * It's a non-leaf entry. Make a hole for the new data
166 * in the key and ptr regions of the block.
167 */
168 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
169 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
170 #ifdef DEBUG
171 for (i = numrecs; i >= ptr; i--) {
172 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
173 return error;
174 }
175 #endif
176 memmove(&kp[ptr], &kp[ptr - 1],
177 (numrecs - ptr + 1) * sizeof(*kp));
178 memmove(&pp[ptr], &pp[ptr - 1],
179 (numrecs - ptr + 1) * sizeof(*pp));
180 /*
181 * Now stuff the new data in, bump numrecs and log the new data.
182 */
183 #ifdef DEBUG
184 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
185 return error;
186 #endif
187 kp[ptr - 1] = key; /* INT_: struct copy */
188 pp[ptr - 1] = cpu_to_be32(*bnop);
189 numrecs++;
190 block->bb_numrecs = cpu_to_be16(numrecs);
191 xfs_inobt_log_keys(cur, bp, ptr, numrecs);
192 xfs_inobt_log_ptrs(cur, bp, ptr, numrecs);
193 } else {
194 /*
195 * It's a leaf entry. Make a hole for the new record.
196 */
197 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
198 memmove(&rp[ptr], &rp[ptr - 1],
199 (numrecs - ptr + 1) * sizeof(*rp));
200 /*
201 * Now stuff the new record in, bump numrecs
202 * and log the new data.
203 */
204 rp[ptr - 1] = *recp; /* INT_: struct copy */
205 numrecs++;
206 block->bb_numrecs = cpu_to_be16(numrecs);
207 xfs_inobt_log_recs(cur, bp, ptr, numrecs);
208 }
209 /*
210 * Log the new number of records in the btree header.
211 */
212 xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
213 #ifdef DEBUG
214 /*
215 * Check that the key/record is in the right place, now.
216 */
217 if (ptr < numrecs) {
218 if (level == 0)
219 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
220 rp + ptr);
221 else
222 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
223 kp + ptr);
224 }
225 #endif
226 /*
227 * If we inserted at the start of a block, update the parents' keys.
228 */
229 if (optr == 1 && (error = xfs_inobt_updkey(cur, &key, level + 1)))
230 return error;
231 /*
232 * Return the new block number, if any.
233 * If there is one, give back a record value and a cursor too.
234 */
235 *bnop = nbno;
236 if (nbno != NULLAGBLOCK) {
237 *recp = nrec; /* INT_: struct copy */
238 *curp = ncur;
239 }
240 *stat = 1;
241 return 0;
242 }
243
244 /*
245 * Log header fields from a btree block.
246 */
247 STATIC void
248 xfs_inobt_log_block(
249 xfs_trans_t *tp, /* transaction pointer */
250 xfs_buf_t *bp, /* buffer containing btree block */
251 int fields) /* mask of fields: XFS_BB_... */
252 {
253 int first; /* first byte offset logged */
254 int last; /* last byte offset logged */
255 static const short offsets[] = { /* table of offsets */
256 offsetof(xfs_inobt_block_t, bb_magic),
257 offsetof(xfs_inobt_block_t, bb_level),
258 offsetof(xfs_inobt_block_t, bb_numrecs),
259 offsetof(xfs_inobt_block_t, bb_leftsib),
260 offsetof(xfs_inobt_block_t, bb_rightsib),
261 sizeof(xfs_inobt_block_t)
262 };
263
264 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
265 xfs_trans_log_buf(tp, bp, first, last);
266 }
267
268 /*
269 * Log keys from a btree block (nonleaf).
270 */
271 STATIC void
272 xfs_inobt_log_keys(
273 xfs_btree_cur_t *cur, /* btree cursor */
274 xfs_buf_t *bp, /* buffer containing btree block */
275 int kfirst, /* index of first key to log */
276 int klast) /* index of last key to log */
277 {
278 xfs_inobt_block_t *block; /* btree block to log from */
279 int first; /* first byte offset logged */
280 xfs_inobt_key_t *kp; /* key pointer in btree block */
281 int last; /* last byte offset logged */
282
283 block = XFS_BUF_TO_INOBT_BLOCK(bp);
284 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
285 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
286 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
287 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
288 }
289
290 /*
291 * Log block pointer fields from a btree block (nonleaf).
292 */
293 STATIC void
294 xfs_inobt_log_ptrs(
295 xfs_btree_cur_t *cur, /* btree cursor */
296 xfs_buf_t *bp, /* buffer containing btree block */
297 int pfirst, /* index of first pointer to log */
298 int plast) /* index of last pointer to log */
299 {
300 xfs_inobt_block_t *block; /* btree block to log from */
301 int first; /* first byte offset logged */
302 int last; /* last byte offset logged */
303 xfs_inobt_ptr_t *pp; /* block-pointer pointer in btree blk */
304
305 block = XFS_BUF_TO_INOBT_BLOCK(bp);
306 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
307 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
308 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
309 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
310 }
311
312 /*
313 * Log records from a btree block (leaf).
314 */
315 STATIC void
316 xfs_inobt_log_recs(
317 xfs_btree_cur_t *cur, /* btree cursor */
318 xfs_buf_t *bp, /* buffer containing btree block */
319 int rfirst, /* index of first record to log */
320 int rlast) /* index of last record to log */
321 {
322 xfs_inobt_block_t *block; /* btree block to log from */
323 int first; /* first byte offset logged */
324 int last; /* last byte offset logged */
325 xfs_inobt_rec_t *rp; /* record pointer for btree block */
326
327 block = XFS_BUF_TO_INOBT_BLOCK(bp);
328 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
329 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
330 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
331 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
332 }
333
334 /*
335 * Lookup the record. The cursor is made to point to it, based on dir.
336 * Return 0 if can't find any such record, 1 for success.
337 */
338 STATIC int /* error */
339 xfs_inobt_lookup(
340 xfs_btree_cur_t *cur, /* btree cursor */
341 xfs_lookup_t dir, /* <=, ==, or >= */
342 int *stat) /* success/failure */
343 {
344 xfs_agblock_t agbno; /* a.g. relative btree block number */
345 xfs_agnumber_t agno; /* allocation group number */
346 xfs_inobt_block_t *block=NULL; /* current btree block */
347 __int64_t diff; /* difference for the current key */
348 int error; /* error return value */
349 int keyno=0; /* current key number */
350 int level; /* level in the btree */
351 xfs_mount_t *mp; /* file system mount point */
352
353 /*
354 * Get the allocation group header, and the root block number.
355 */
356 mp = cur->bc_mp;
357 {
358 xfs_agi_t *agi; /* a.g. inode header */
359
360 agi = XFS_BUF_TO_AGI(cur->bc_private.i.agbp);
361 agno = be32_to_cpu(agi->agi_seqno);
362 agbno = be32_to_cpu(agi->agi_root);
363 }
364 /*
365 * Iterate over each level in the btree, starting at the root.
366 * For each level above the leaves, find the key we need, based
367 * on the lookup record, then follow the corresponding block
368 * pointer down to the next level.
369 */
370 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
371 xfs_buf_t *bp; /* buffer pointer for btree block */
372 xfs_daddr_t d; /* disk address of btree block */
373
374 /*
375 * Get the disk address we're looking for.
376 */
377 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
378 /*
379 * If the old buffer at this level is for a different block,
380 * throw it away, otherwise just use it.
381 */
382 bp = cur->bc_bufs[level];
383 if (bp && XFS_BUF_ADDR(bp) != d)
384 bp = (xfs_buf_t *)0;
385 if (!bp) {
386 /*
387 * Need to get a new buffer. Read it, then
388 * set it in the cursor, releasing the old one.
389 */
390 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
391 agno, agbno, 0, &bp, XFS_INO_BTREE_REF)))
392 return error;
393 xfs_btree_setbuf(cur, level, bp);
394 /*
395 * Point to the btree block, now that we have the buffer
396 */
397 block = XFS_BUF_TO_INOBT_BLOCK(bp);
398 if ((error = xfs_btree_check_sblock(cur, block, level,
399 bp)))
400 return error;
401 } else
402 block = XFS_BUF_TO_INOBT_BLOCK(bp);
403 /*
404 * If we already had a key match at a higher level, we know
405 * we need to use the first entry in this block.
406 */
407 if (diff == 0)
408 keyno = 1;
409 /*
410 * Otherwise we need to search this block. Do a binary search.
411 */
412 else {
413 int high; /* high entry number */
414 xfs_inobt_key_t *kkbase=NULL;/* base of keys in block */
415 xfs_inobt_rec_t *krbase=NULL;/* base of records in block */
416 int low; /* low entry number */
417
418 /*
419 * Get a pointer to keys or records.
420 */
421 if (level > 0)
422 kkbase = XFS_INOBT_KEY_ADDR(block, 1, cur);
423 else
424 krbase = XFS_INOBT_REC_ADDR(block, 1, cur);
425 /*
426 * Set low and high entry numbers, 1-based.
427 */
428 low = 1;
429 if (!(high = be16_to_cpu(block->bb_numrecs))) {
430 /*
431 * If the block is empty, the tree must
432 * be an empty leaf.
433 */
434 ASSERT(level == 0 && cur->bc_nlevels == 1);
435 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
436 *stat = 0;
437 return 0;
438 }
439 /*
440 * Binary search the block.
441 */
442 while (low <= high) {
443 xfs_agino_t startino; /* key value */
444
445 /*
446 * keyno is average of low and high.
447 */
448 keyno = (low + high) >> 1;
449 /*
450 * Get startino.
451 */
452 if (level > 0) {
453 xfs_inobt_key_t *kkp;
454
455 kkp = kkbase + keyno - 1;
456 startino = INT_GET(kkp->ir_startino, ARCH_CONVERT);
457 } else {
458 xfs_inobt_rec_t *krp;
459
460 krp = krbase + keyno - 1;
461 startino = INT_GET(krp->ir_startino, ARCH_CONVERT);
462 }
463 /*
464 * Compute difference to get next direction.
465 */
466 diff = (__int64_t)
467 startino - cur->bc_rec.i.ir_startino;
468 /*
469 * Less than, move right.
470 */
471 if (diff < 0)
472 low = keyno + 1;
473 /*
474 * Greater than, move left.
475 */
476 else if (diff > 0)
477 high = keyno - 1;
478 /*
479 * Equal, we're done.
480 */
481 else
482 break;
483 }
484 }
485 /*
486 * If there are more levels, set up for the next level
487 * by getting the block number and filling in the cursor.
488 */
489 if (level > 0) {
490 /*
491 * If we moved left, need the previous key number,
492 * unless there isn't one.
493 */
494 if (diff > 0 && --keyno < 1)
495 keyno = 1;
496 agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, keyno, cur));
497 #ifdef DEBUG
498 if ((error = xfs_btree_check_sptr(cur, agbno, level)))
499 return error;
500 #endif
501 cur->bc_ptrs[level] = keyno;
502 }
503 }
504 /*
505 * Done with the search.
506 * See if we need to adjust the results.
507 */
508 if (dir != XFS_LOOKUP_LE && diff < 0) {
509 keyno++;
510 /*
511 * If ge search and we went off the end of the block, but it's
512 * not the last block, we're in the wrong block.
513 */
514 if (dir == XFS_LOOKUP_GE &&
515 keyno > be16_to_cpu(block->bb_numrecs) &&
516 be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
517 int i;
518
519 cur->bc_ptrs[0] = keyno;
520 if ((error = xfs_inobt_increment(cur, 0, &i)))
521 return error;
522 ASSERT(i == 1);
523 *stat = 1;
524 return 0;
525 }
526 }
527 else if (dir == XFS_LOOKUP_LE && diff > 0)
528 keyno--;
529 cur->bc_ptrs[0] = keyno;
530 /*
531 * Return if we succeeded or not.
532 */
533 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
534 *stat = 0;
535 else
536 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
537 return 0;
538 }
539
540 /*
541 * Move 1 record left from cur/level if possible.
542 * Update cur to reflect the new path.
543 */
544 STATIC int /* error */
545 xfs_inobt_lshift(
546 xfs_btree_cur_t *cur, /* btree cursor */
547 int level, /* level to shift record on */
548 int *stat) /* success/failure */
549 {
550 int error; /* error return value */
551 #ifdef DEBUG
552 int i; /* loop index */
553 #endif
554 xfs_inobt_key_t key; /* key value for leaf level upward */
555 xfs_buf_t *lbp; /* buffer for left neighbor block */
556 xfs_inobt_block_t *left; /* left neighbor btree block */
557 xfs_inobt_key_t *lkp=NULL; /* key pointer for left block */
558 xfs_inobt_ptr_t *lpp; /* address pointer for left block */
559 xfs_inobt_rec_t *lrp=NULL; /* record pointer for left block */
560 int nrec; /* new number of left block entries */
561 xfs_buf_t *rbp; /* buffer for right (current) block */
562 xfs_inobt_block_t *right; /* right (current) btree block */
563 xfs_inobt_key_t *rkp=NULL; /* key pointer for right block */
564 xfs_inobt_ptr_t *rpp=NULL; /* address pointer for right block */
565 xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */
566
567 /*
568 * Set up variables for this block as "right".
569 */
570 rbp = cur->bc_bufs[level];
571 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
572 #ifdef DEBUG
573 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
574 return error;
575 #endif
576 /*
577 * If we've got no left sibling then we can't shift an entry left.
578 */
579 if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
580 *stat = 0;
581 return 0;
582 }
583 /*
584 * If the cursor entry is the one that would be moved, don't
585 * do it... it's too complicated.
586 */
587 if (cur->bc_ptrs[level] <= 1) {
588 *stat = 0;
589 return 0;
590 }
591 /*
592 * Set up the left neighbor as "left".
593 */
594 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
595 cur->bc_private.i.agno, be32_to_cpu(right->bb_leftsib),
596 0, &lbp, XFS_INO_BTREE_REF)))
597 return error;
598 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
599 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
600 return error;
601 /*
602 * If it's full, it can't take another entry.
603 */
604 if (be16_to_cpu(left->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
605 *stat = 0;
606 return 0;
607 }
608 nrec = be16_to_cpu(left->bb_numrecs) + 1;
609 /*
610 * If non-leaf, copy a key and a ptr to the left block.
611 */
612 if (level > 0) {
613 lkp = XFS_INOBT_KEY_ADDR(left, nrec, cur);
614 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
615 *lkp = *rkp;
616 xfs_inobt_log_keys(cur, lbp, nrec, nrec);
617 lpp = XFS_INOBT_PTR_ADDR(left, nrec, cur);
618 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
619 #ifdef DEBUG
620 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
621 return error;
622 #endif
623 *lpp = *rpp; /* INT_: no-change copy */
624 xfs_inobt_log_ptrs(cur, lbp, nrec, nrec);
625 }
626 /*
627 * If leaf, copy a record to the left block.
628 */
629 else {
630 lrp = XFS_INOBT_REC_ADDR(left, nrec, cur);
631 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
632 *lrp = *rrp;
633 xfs_inobt_log_recs(cur, lbp, nrec, nrec);
634 }
635 /*
636 * Bump and log left's numrecs, decrement and log right's numrecs.
637 */
638 be16_add(&left->bb_numrecs, 1);
639 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
640 #ifdef DEBUG
641 if (level > 0)
642 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
643 else
644 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
645 #endif
646 be16_add(&right->bb_numrecs, -1);
647 xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
648 /*
649 * Slide the contents of right down one entry.
650 */
651 if (level > 0) {
652 #ifdef DEBUG
653 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
654 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
655 level)))
656 return error;
657 }
658 #endif
659 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
660 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
661 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
662 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
663 } else {
664 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
665 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
666 key.ir_startino = rrp->ir_startino; /* INT_: direct copy */
667 rkp = &key;
668 }
669 /*
670 * Update the parent key values of right.
671 */
672 if ((error = xfs_inobt_updkey(cur, rkp, level + 1)))
673 return error;
674 /*
675 * Slide the cursor value left one.
676 */
677 cur->bc_ptrs[level]--;
678 *stat = 1;
679 return 0;
680 }
681
682 /*
683 * Allocate a new root block, fill it in.
684 */
685 STATIC int /* error */
686 xfs_inobt_newroot(
687 xfs_btree_cur_t *cur, /* btree cursor */
688 int *stat) /* success/failure */
689 {
690 xfs_agi_t *agi; /* a.g. inode header */
691 xfs_alloc_arg_t args; /* allocation argument structure */
692 xfs_inobt_block_t *block; /* one half of the old root block */
693 xfs_buf_t *bp; /* buffer containing block */
694 int error; /* error return value */
695 xfs_inobt_key_t *kp; /* btree key pointer */
696 xfs_agblock_t lbno; /* left block number */
697 xfs_buf_t *lbp; /* left buffer pointer */
698 xfs_inobt_block_t *left; /* left btree block */
699 xfs_buf_t *nbp; /* new (root) buffer */
700 xfs_inobt_block_t *new; /* new (root) btree block */
701 int nptr; /* new value for key index, 1 or 2 */
702 xfs_inobt_ptr_t *pp; /* btree address pointer */
703 xfs_agblock_t rbno; /* right block number */
704 xfs_buf_t *rbp; /* right buffer pointer */
705 xfs_inobt_block_t *right; /* right btree block */
706 xfs_inobt_rec_t *rp; /* btree record pointer */
707
708 ASSERT(cur->bc_nlevels < XFS_IN_MAXLEVELS(cur->bc_mp));
709
710 /*
711 * Get a block & a buffer.
712 */
713 agi = XFS_BUF_TO_AGI(cur->bc_private.i.agbp);
714 args.tp = cur->bc_tp;
715 args.mp = cur->bc_mp;
716 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno,
717 be32_to_cpu(agi->agi_root));
718 args.mod = args.minleft = args.alignment = args.total = args.wasdel =
719 args.isfl = args.userdata = args.minalignslop = 0;
720 args.minlen = args.maxlen = args.prod = 1;
721 args.type = XFS_ALLOCTYPE_NEAR_BNO;
722 if ((error = xfs_alloc_vextent(&args)))
723 return error;
724 /*
725 * None available, we fail.
726 */
727 if (args.fsbno == NULLFSBLOCK) {
728 *stat = 0;
729 return 0;
730 }
731 ASSERT(args.len == 1);
732 nbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
733 new = XFS_BUF_TO_INOBT_BLOCK(nbp);
734 /*
735 * Set the root data in the a.g. inode structure.
736 */
737 agi->agi_root = cpu_to_be32(args.agbno);
738 be32_add(&agi->agi_level, 1);
739 xfs_ialloc_log_agi(args.tp, cur->bc_private.i.agbp,
740 XFS_AGI_ROOT | XFS_AGI_LEVEL);
741 /*
742 * At the previous root level there are now two blocks: the old
743 * root, and the new block generated when it was split.
744 * We don't know which one the cursor is pointing at, so we
745 * set up variables "left" and "right" for each case.
746 */
747 bp = cur->bc_bufs[cur->bc_nlevels - 1];
748 block = XFS_BUF_TO_INOBT_BLOCK(bp);
749 #ifdef DEBUG
750 if ((error = xfs_btree_check_sblock(cur, block, cur->bc_nlevels - 1, bp)))
751 return error;
752 #endif
753 if (be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
754 /*
755 * Our block is left, pick up the right block.
756 */
757 lbp = bp;
758 lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
759 left = block;
760 rbno = be32_to_cpu(left->bb_rightsib);
761 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
762 rbno, 0, &rbp, XFS_INO_BTREE_REF)))
763 return error;
764 bp = rbp;
765 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
766 if ((error = xfs_btree_check_sblock(cur, right,
767 cur->bc_nlevels - 1, rbp)))
768 return error;
769 nptr = 1;
770 } else {
771 /*
772 * Our block is right, pick up the left block.
773 */
774 rbp = bp;
775 rbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(rbp));
776 right = block;
777 lbno = be32_to_cpu(right->bb_leftsib);
778 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
779 lbno, 0, &lbp, XFS_INO_BTREE_REF)))
780 return error;
781 bp = lbp;
782 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
783 if ((error = xfs_btree_check_sblock(cur, left,
784 cur->bc_nlevels - 1, lbp)))
785 return error;
786 nptr = 2;
787 }
788 /*
789 * Fill in the new block's btree header and log it.
790 */
791 new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
792 new->bb_level = cpu_to_be16(cur->bc_nlevels);
793 new->bb_numrecs = cpu_to_be16(2);
794 new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
795 new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
796 xfs_inobt_log_block(args.tp, nbp, XFS_BB_ALL_BITS);
797 ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
798 /*
799 * Fill in the key data in the new root.
800 */
801 kp = XFS_INOBT_KEY_ADDR(new, 1, cur);
802 if (be16_to_cpu(left->bb_level) > 0) {
803 kp[0] = *XFS_INOBT_KEY_ADDR(left, 1, cur); /* INT_: struct copy */
804 kp[1] = *XFS_INOBT_KEY_ADDR(right, 1, cur); /* INT_: struct copy */
805 } else {
806 rp = XFS_INOBT_REC_ADDR(left, 1, cur);
807 INT_COPY(kp[0].ir_startino, rp->ir_startino, ARCH_CONVERT);
808 rp = XFS_INOBT_REC_ADDR(right, 1, cur);
809 INT_COPY(kp[1].ir_startino, rp->ir_startino, ARCH_CONVERT);
810 }
811 xfs_inobt_log_keys(cur, nbp, 1, 2);
812 /*
813 * Fill in the pointer data in the new root.
814 */
815 pp = XFS_INOBT_PTR_ADDR(new, 1, cur);
816 pp[0] = cpu_to_be32(lbno);
817 pp[1] = cpu_to_be32(rbno);
818 xfs_inobt_log_ptrs(cur, nbp, 1, 2);
819 /*
820 * Fix up the cursor.
821 */
822 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
823 cur->bc_ptrs[cur->bc_nlevels] = nptr;
824 cur->bc_nlevels++;
825 *stat = 1;
826 return 0;
827 }
828
829 /*
830 * Move 1 record right from cur/level if possible.
831 * Update cur to reflect the new path.
832 */
833 STATIC int /* error */
834 xfs_inobt_rshift(
835 xfs_btree_cur_t *cur, /* btree cursor */
836 int level, /* level to shift record on */
837 int *stat) /* success/failure */
838 {
839 int error; /* error return value */
840 int i; /* loop index */
841 xfs_inobt_key_t key; /* key value for leaf level upward */
842 xfs_buf_t *lbp; /* buffer for left (current) block */
843 xfs_inobt_block_t *left; /* left (current) btree block */
844 xfs_inobt_key_t *lkp; /* key pointer for left block */
845 xfs_inobt_ptr_t *lpp; /* address pointer for left block */
846 xfs_inobt_rec_t *lrp; /* record pointer for left block */
847 xfs_buf_t *rbp; /* buffer for right neighbor block */
848 xfs_inobt_block_t *right; /* right neighbor btree block */
849 xfs_inobt_key_t *rkp; /* key pointer for right block */
850 xfs_inobt_ptr_t *rpp; /* address pointer for right block */
851 xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */
852 xfs_btree_cur_t *tcur; /* temporary cursor */
853
854 /*
855 * Set up variables for this block as "left".
856 */
857 lbp = cur->bc_bufs[level];
858 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
859 #ifdef DEBUG
860 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
861 return error;
862 #endif
863 /*
864 * If we've got no right sibling then we can't shift an entry right.
865 */
866 if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
867 *stat = 0;
868 return 0;
869 }
870 /*
871 * If the cursor entry is the one that would be moved, don't
872 * do it... it's too complicated.
873 */
874 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
875 *stat = 0;
876 return 0;
877 }
878 /*
879 * Set up the right neighbor as "right".
880 */
881 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
882 cur->bc_private.i.agno, be32_to_cpu(left->bb_rightsib),
883 0, &rbp, XFS_INO_BTREE_REF)))
884 return error;
885 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
886 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
887 return error;
888 /*
889 * If it's full, it can't take another entry.
890 */
891 if (be16_to_cpu(right->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
892 *stat = 0;
893 return 0;
894 }
895 /*
896 * Make a hole at the start of the right neighbor block, then
897 * copy the last left block entry to the hole.
898 */
899 if (level > 0) {
900 lkp = XFS_INOBT_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
901 lpp = XFS_INOBT_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
902 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
903 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
904 #ifdef DEBUG
905 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
906 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
907 return error;
908 }
909 #endif
910 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
911 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
912 #ifdef DEBUG
913 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
914 return error;
915 #endif
916 *rkp = *lkp; /* INT_: no change copy */
917 *rpp = *lpp; /* INT_: no change copy */
918 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
919 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
920 } else {
921 lrp = XFS_INOBT_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
922 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
923 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
924 *rrp = *lrp;
925 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
926 key.ir_startino = rrp->ir_startino; /* INT_: direct copy */
927 rkp = &key;
928 }
929 /*
930 * Decrement and log left's numrecs, bump and log right's numrecs.
931 */
932 be16_add(&left->bb_numrecs, -1);
933 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
934 be16_add(&right->bb_numrecs, 1);
935 #ifdef DEBUG
936 if (level > 0)
937 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
938 else
939 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
940 #endif
941 xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
942 /*
943 * Using a temporary cursor, update the parent key values of the
944 * block on the right.
945 */
946 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
947 return error;
948 xfs_btree_lastrec(tcur, level);
949 if ((error = xfs_inobt_increment(tcur, level, &i)) ||
950 (error = xfs_inobt_updkey(tcur, rkp, level + 1))) {
951 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
952 return error;
953 }
954 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
955 *stat = 1;
956 return 0;
957 }
958
959 /*
960 * Split cur/level block in half.
961 * Return new block number and its first record (to be inserted into parent).
962 */
963 STATIC int /* error */
964 xfs_inobt_split(
965 xfs_btree_cur_t *cur, /* btree cursor */
966 int level, /* level to split */
967 xfs_agblock_t *bnop, /* output: block number allocated */
968 xfs_inobt_key_t *keyp, /* output: first key of new block */
969 xfs_btree_cur_t **curp, /* output: new cursor */
970 int *stat) /* success/failure */
971 {
972 xfs_alloc_arg_t args; /* allocation argument structure */
973 int error; /* error return value */
974 int i; /* loop index/record number */
975 xfs_agblock_t lbno; /* left (current) block number */
976 xfs_buf_t *lbp; /* buffer for left block */
977 xfs_inobt_block_t *left; /* left (current) btree block */
978 xfs_inobt_key_t *lkp; /* left btree key pointer */
979 xfs_inobt_ptr_t *lpp; /* left btree address pointer */
980 xfs_inobt_rec_t *lrp; /* left btree record pointer */
981 xfs_buf_t *rbp; /* buffer for right block */
982 xfs_inobt_block_t *right; /* right (new) btree block */
983 xfs_inobt_key_t *rkp; /* right btree key pointer */
984 xfs_inobt_ptr_t *rpp; /* right btree address pointer */
985 xfs_inobt_rec_t *rrp; /* right btree record pointer */
986
987 /*
988 * Set up left block (current one).
989 */
990 lbp = cur->bc_bufs[level];
991 args.tp = cur->bc_tp;
992 args.mp = cur->bc_mp;
993 lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
994 /*
995 * Allocate the new block.
996 * If we can't do it, we're toast. Give up.
997 */
998 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno, lbno);
999 args.mod = args.minleft = args.alignment = args.total = args.wasdel =
1000 args.isfl = args.userdata = args.minalignslop = 0;
1001 args.minlen = args.maxlen = args.prod = 1;
1002 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1003 if ((error = xfs_alloc_vextent(&args)))
1004 return error;
1005 if (args.fsbno == NULLFSBLOCK) {
1006 *stat = 0;
1007 return 0;
1008 }
1009 ASSERT(args.len == 1);
1010 rbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
1011 /*
1012 * Set up the new block as "right".
1013 */
1014 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
1015 /*
1016 * "Left" is the current (according to the cursor) block.
1017 */
1018 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
1019 #ifdef DEBUG
1020 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1021 return error;
1022 #endif
1023 /*
1024 * Fill in the btree header for the new block.
1025 */
1026 right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1027 right->bb_level = left->bb_level;
1028 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1029 /*
1030 * Make sure that if there's an odd number of entries now, that
1031 * each new block will have the same number of entries.
1032 */
1033 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1034 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1035 be16_add(&right->bb_numrecs, 1);
1036 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1037 /*
1038 * For non-leaf blocks, copy keys and addresses over to the new block.
1039 */
1040 if (level > 0) {
1041 lkp = XFS_INOBT_KEY_ADDR(left, i, cur);
1042 lpp = XFS_INOBT_PTR_ADDR(left, i, cur);
1043 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
1044 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
1045 #ifdef DEBUG
1046 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1047 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
1048 return error;
1049 }
1050 #endif
1051 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1052 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1053 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1054 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1055 *keyp = *rkp;
1056 }
1057 /*
1058 * For leaf blocks, copy records over to the new block.
1059 */
1060 else {
1061 lrp = XFS_INOBT_REC_ADDR(left, i, cur);
1062 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
1063 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1064 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1065 keyp->ir_startino = rrp->ir_startino; /* INT_: direct copy */
1066 }
1067 /*
1068 * Find the left block number by looking in the buffer.
1069 * Adjust numrecs, sibling pointers.
1070 */
1071 be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1072 right->bb_rightsib = left->bb_rightsib;
1073 left->bb_rightsib = cpu_to_be32(args.agbno);
1074 right->bb_leftsib = cpu_to_be32(lbno);
1075 xfs_inobt_log_block(args.tp, rbp, XFS_BB_ALL_BITS);
1076 xfs_inobt_log_block(args.tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1077 /*
1078 * If there's a block to the new block's right, make that block
1079 * point back to right instead of to left.
1080 */
1081 if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
1082 xfs_inobt_block_t *rrblock; /* rr btree block */
1083 xfs_buf_t *rrbp; /* buffer for rrblock */
1084
1085 if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
1086 be32_to_cpu(right->bb_rightsib), 0, &rrbp,
1087 XFS_INO_BTREE_REF)))
1088 return error;
1089 rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp);
1090 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1091 return error;
1092 rrblock->bb_leftsib = cpu_to_be32(args.agbno);
1093 xfs_inobt_log_block(args.tp, rrbp, XFS_BB_LEFTSIB);
1094 }
1095 /*
1096 * If the cursor is really in the right block, move it there.
1097 * If it's just pointing past the last entry in left, then we'll
1098 * insert there, so don't change anything in that case.
1099 */
1100 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1101 xfs_btree_setbuf(cur, level, rbp);
1102 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1103 }
1104 /*
1105 * If there are more levels, we'll need another cursor which refers
1106 * the right block, no matter where this cursor was.
1107 */
1108 if (level + 1 < cur->bc_nlevels) {
1109 if ((error = xfs_btree_dup_cursor(cur, curp)))
1110 return error;
1111 (*curp)->bc_ptrs[level + 1]++;
1112 }
1113 *bnop = args.agbno;
1114 *stat = 1;
1115 return 0;
1116 }
1117
1118 /*
1119 * Update keys at all levels from here to the root along the cursor's path.
1120 */
1121 STATIC int /* error */
1122 xfs_inobt_updkey(
1123 xfs_btree_cur_t *cur, /* btree cursor */
1124 xfs_inobt_key_t *keyp, /* new key value to update to */
1125 int level) /* starting level for update */
1126 {
1127 int ptr; /* index of key in block */
1128
1129 /*
1130 * Go up the tree from this level toward the root.
1131 * At each level, update the key value to the value input.
1132 * Stop when we reach a level where the cursor isn't pointing
1133 * at the first entry in the block.
1134 */
1135 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1136 xfs_buf_t *bp; /* buffer for block */
1137 xfs_inobt_block_t *block; /* btree block */
1138 #ifdef DEBUG
1139 int error; /* error return value */
1140 #endif
1141 xfs_inobt_key_t *kp; /* ptr to btree block keys */
1142
1143 bp = cur->bc_bufs[level];
1144 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1145 #ifdef DEBUG
1146 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1147 return error;
1148 #endif
1149 ptr = cur->bc_ptrs[level];
1150 kp = XFS_INOBT_KEY_ADDR(block, ptr, cur);
1151 *kp = *keyp;
1152 xfs_inobt_log_keys(cur, bp, ptr, ptr);
1153 }
1154 return 0;
1155 }
1156
1157 /*
1158 * Externally visible routines.
1159 */
1160
1161 /*
1162 * Decrement cursor by one record at the level.
1163 * For nonzero levels the leaf-ward information is untouched.
1164 */
1165 int /* error */
1166 xfs_inobt_decrement(
1167 xfs_btree_cur_t *cur, /* btree cursor */
1168 int level, /* level in btree, 0 is leaf */
1169 int *stat) /* success/failure */
1170 {
1171 xfs_inobt_block_t *block; /* btree block */
1172 int error;
1173 int lev; /* btree level */
1174
1175 ASSERT(level < cur->bc_nlevels);
1176 /*
1177 * Read-ahead to the left at this level.
1178 */
1179 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1180 /*
1181 * Decrement the ptr at this level. If we're still in the block
1182 * then we're done.
1183 */
1184 if (--cur->bc_ptrs[level] > 0) {
1185 *stat = 1;
1186 return 0;
1187 }
1188 /*
1189 * Get a pointer to the btree block.
1190 */
1191 block = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[level]);
1192 #ifdef DEBUG
1193 if ((error = xfs_btree_check_sblock(cur, block, level,
1194 cur->bc_bufs[level])))
1195 return error;
1196 #endif
1197 /*
1198 * If we just went off the left edge of the tree, return failure.
1199 */
1200 if (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK) {
1201 *stat = 0;
1202 return 0;
1203 }
1204 /*
1205 * March up the tree decrementing pointers.
1206 * Stop when we don't go off the left edge of a block.
1207 */
1208 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1209 if (--cur->bc_ptrs[lev] > 0)
1210 break;
1211 /*
1212 * Read-ahead the left block, we're going to read it
1213 * in the next loop.
1214 */
1215 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1216 }
1217 /*
1218 * If we went off the root then we are seriously confused.
1219 */
1220 ASSERT(lev < cur->bc_nlevels);
1221 /*
1222 * Now walk back down the tree, fixing up the cursor's buffer
1223 * pointers and key numbers.
1224 */
1225 for (block = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
1226 xfs_agblock_t agbno; /* block number of btree block */
1227 xfs_buf_t *bp; /* buffer containing btree block */
1228
1229 agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
1230 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1231 cur->bc_private.i.agno, agbno, 0, &bp,
1232 XFS_INO_BTREE_REF)))
1233 return error;
1234 lev--;
1235 xfs_btree_setbuf(cur, lev, bp);
1236 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1237 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1238 return error;
1239 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
1240 }
1241 *stat = 1;
1242 return 0;
1243 }
1244
1245 /*
1246 * Get the data from the pointed-to record.
1247 */
1248 int /* error */
1249 xfs_inobt_get_rec(
1250 xfs_btree_cur_t *cur, /* btree cursor */
1251 xfs_agino_t *ino, /* output: starting inode of chunk */
1252 __int32_t *fcnt, /* output: number of free inodes */
1253 xfs_inofree_t *free, /* output: free inode mask */
1254 int *stat) /* output: success/failure */
1255 {
1256 xfs_inobt_block_t *block; /* btree block */
1257 xfs_buf_t *bp; /* buffer containing btree block */
1258 #ifdef DEBUG
1259 int error; /* error return value */
1260 #endif
1261 int ptr; /* record number */
1262 xfs_inobt_rec_t *rec; /* record data */
1263
1264 bp = cur->bc_bufs[0];
1265 ptr = cur->bc_ptrs[0];
1266 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1267 #ifdef DEBUG
1268 if ((error = xfs_btree_check_sblock(cur, block, 0, bp)))
1269 return error;
1270 #endif
1271 /*
1272 * Off the right end or left end, return failure.
1273 */
1274 if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
1275 *stat = 0;
1276 return 0;
1277 }
1278 /*
1279 * Point to the record and extract its data.
1280 */
1281 rec = XFS_INOBT_REC_ADDR(block, ptr, cur);
1282 *ino = INT_GET(rec->ir_startino, ARCH_CONVERT);
1283 *fcnt = INT_GET(rec->ir_freecount, ARCH_CONVERT);
1284 *free = INT_GET(rec->ir_free, ARCH_CONVERT);
1285 *stat = 1;
1286 return 0;
1287 }
1288
1289 /*
1290 * Increment cursor by one record at the level.
1291 * For nonzero levels the leaf-ward information is untouched.
1292 */
1293 int /* error */
1294 xfs_inobt_increment(
1295 xfs_btree_cur_t *cur, /* btree cursor */
1296 int level, /* level in btree, 0 is leaf */
1297 int *stat) /* success/failure */
1298 {
1299 xfs_inobt_block_t *block; /* btree block */
1300 xfs_buf_t *bp; /* buffer containing btree block */
1301 int error; /* error return value */
1302 int lev; /* btree level */
1303
1304 ASSERT(level < cur->bc_nlevels);
1305 /*
1306 * Read-ahead to the right at this level.
1307 */
1308 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1309 /*
1310 * Get a pointer to the btree block.
1311 */
1312 bp = cur->bc_bufs[level];
1313 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1314 #ifdef DEBUG
1315 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1316 return error;
1317 #endif
1318 /*
1319 * Increment the ptr at this level. If we're still in the block
1320 * then we're done.
1321 */
1322 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1323 *stat = 1;
1324 return 0;
1325 }
1326 /*
1327 * If we just went off the right edge of the tree, return failure.
1328 */
1329 if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
1330 *stat = 0;
1331 return 0;
1332 }
1333 /*
1334 * March up the tree incrementing pointers.
1335 * Stop when we don't go off the right edge of a block.
1336 */
1337 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1338 bp = cur->bc_bufs[lev];
1339 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1340 #ifdef DEBUG
1341 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1342 return error;
1343 #endif
1344 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
1345 break;
1346 /*
1347 * Read-ahead the right block, we're going to read it
1348 * in the next loop.
1349 */
1350 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1351 }
1352 /*
1353 * If we went off the root then we are seriously confused.
1354 */
1355 ASSERT(lev < cur->bc_nlevels);
1356 /*
1357 * Now walk back down the tree, fixing up the cursor's buffer
1358 * pointers and key numbers.
1359 */
1360 for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_INOBT_BLOCK(bp);
1361 lev > level; ) {
1362 xfs_agblock_t agbno; /* block number of btree block */
1363
1364 agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
1365 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1366 cur->bc_private.i.agno, agbno, 0, &bp,
1367 XFS_INO_BTREE_REF)))
1368 return error;
1369 lev--;
1370 xfs_btree_setbuf(cur, lev, bp);
1371 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1372 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1373 return error;
1374 cur->bc_ptrs[lev] = 1;
1375 }
1376 *stat = 1;
1377 return 0;
1378 }
1379
1380 /*
1381 * Insert the current record at the point referenced by cur.
1382 * The cursor may be inconsistent on return if splits have been done.
1383 */
1384 int /* error */
1385 xfs_inobt_insert(
1386 xfs_btree_cur_t *cur, /* btree cursor */
1387 int *stat) /* success/failure */
1388 {
1389 int error; /* error return value */
1390 int i; /* result value, 0 for failure */
1391 int level; /* current level number in btree */
1392 xfs_agblock_t nbno; /* new block number (split result) */
1393 xfs_btree_cur_t *ncur; /* new cursor (split result) */
1394 xfs_inobt_rec_t nrec; /* record being inserted this level */
1395 xfs_btree_cur_t *pcur; /* previous level's cursor */
1396
1397 level = 0;
1398 nbno = NULLAGBLOCK;
1399 INT_SET(nrec.ir_startino, ARCH_CONVERT, cur->bc_rec.i.ir_startino);
1400 INT_SET(nrec.ir_freecount, ARCH_CONVERT, cur->bc_rec.i.ir_freecount);
1401 INT_SET(nrec.ir_free, ARCH_CONVERT, cur->bc_rec.i.ir_free);
1402 ncur = (xfs_btree_cur_t *)0;
1403 pcur = cur;
1404 /*
1405 * Loop going up the tree, starting at the leaf level.
1406 * Stop when we don't get a split block, that must mean that
1407 * the insert is finished with this level.
1408 */
1409 do {
1410 /*
1411 * Insert nrec/nbno into this level of the tree.
1412 * Note if we fail, nbno will be null.
1413 */
1414 if ((error = xfs_inobt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1415 &i))) {
1416 if (pcur != cur)
1417 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1418 return error;
1419 }
1420 /*
1421 * See if the cursor we just used is trash.
1422 * Can't trash the caller's cursor, but otherwise we should
1423 * if ncur is a new cursor or we're about to be done.
1424 */
1425 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
1426 cur->bc_nlevels = pcur->bc_nlevels;
1427 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1428 }
1429 /*
1430 * If we got a new cursor, switch to it.
1431 */
1432 if (ncur) {
1433 pcur = ncur;
1434 ncur = (xfs_btree_cur_t *)0;
1435 }
1436 } while (nbno != NULLAGBLOCK);
1437 *stat = i;
1438 return 0;
1439 }
1440
1441 /*
1442 * Lookup the record equal to ino in the btree given by cur.
1443 */
1444 int /* error */
1445 xfs_inobt_lookup_eq(
1446 xfs_btree_cur_t *cur, /* btree cursor */
1447 xfs_agino_t ino, /* starting inode of chunk */
1448 __int32_t fcnt, /* free inode count */
1449 xfs_inofree_t free, /* free inode mask */
1450 int *stat) /* success/failure */
1451 {
1452 cur->bc_rec.i.ir_startino = ino;
1453 cur->bc_rec.i.ir_freecount = fcnt;
1454 cur->bc_rec.i.ir_free = free;
1455 return xfs_inobt_lookup(cur, XFS_LOOKUP_EQ, stat);
1456 }
1457
1458 /*
1459 * Lookup the first record greater than or equal to ino
1460 * in the btree given by cur.
1461 */
1462 int /* error */
1463 xfs_inobt_lookup_ge(
1464 xfs_btree_cur_t *cur, /* btree cursor */
1465 xfs_agino_t ino, /* starting inode of chunk */
1466 __int32_t fcnt, /* free inode count */
1467 xfs_inofree_t free, /* free inode mask */
1468 int *stat) /* success/failure */
1469 {
1470 cur->bc_rec.i.ir_startino = ino;
1471 cur->bc_rec.i.ir_freecount = fcnt;
1472 cur->bc_rec.i.ir_free = free;
1473 return xfs_inobt_lookup(cur, XFS_LOOKUP_GE, stat);
1474 }
1475
1476 /*
1477 * Lookup the first record less than or equal to ino
1478 * in the btree given by cur.
1479 */
1480 int /* error */
1481 xfs_inobt_lookup_le(
1482 xfs_btree_cur_t *cur, /* btree cursor */
1483 xfs_agino_t ino, /* starting inode of chunk */
1484 __int32_t fcnt, /* free inode count */
1485 xfs_inofree_t free, /* free inode mask */
1486 int *stat) /* success/failure */
1487 {
1488 cur->bc_rec.i.ir_startino = ino;
1489 cur->bc_rec.i.ir_freecount = fcnt;
1490 cur->bc_rec.i.ir_free = free;
1491 return xfs_inobt_lookup(cur, XFS_LOOKUP_LE, stat);
1492 }
1493
1494 /*
1495 * Update the record referred to by cur, to the value given
1496 * by [ino, fcnt, free].
1497 * This either works (return 0) or gets an EFSCORRUPTED error.
1498 */
1499 int /* error */
1500 xfs_inobt_update(
1501 xfs_btree_cur_t *cur, /* btree cursor */
1502 xfs_agino_t ino, /* starting inode of chunk */
1503 __int32_t fcnt, /* free inode count */
1504 xfs_inofree_t free) /* free inode mask */
1505 {
1506 xfs_inobt_block_t *block; /* btree block to update */
1507 xfs_buf_t *bp; /* buffer containing btree block */
1508 int error; /* error return value */
1509 int ptr; /* current record number (updating) */
1510 xfs_inobt_rec_t *rp; /* pointer to updated record */
1511
1512 /*
1513 * Pick up the current block.
1514 */
1515 bp = cur->bc_bufs[0];
1516 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1517 #ifdef DEBUG
1518 if ((error = xfs_btree_check_sblock(cur, block, 0, bp)))
1519 return error;
1520 #endif
1521 /*
1522 * Get the address of the rec to be updated.
1523 */
1524 ptr = cur->bc_ptrs[0];
1525 rp = XFS_INOBT_REC_ADDR(block, ptr, cur);
1526 /*
1527 * Fill in the new contents and log them.
1528 */
1529 INT_SET(rp->ir_startino, ARCH_CONVERT, ino);
1530 INT_SET(rp->ir_freecount, ARCH_CONVERT, fcnt);
1531 INT_SET(rp->ir_free, ARCH_CONVERT, free);
1532 xfs_inobt_log_recs(cur, bp, ptr, ptr);
1533 /*
1534 * Updating first record in leaf. Pass new key value up to our parent.
1535 */
1536 if (ptr == 1) {
1537 xfs_inobt_key_t key; /* key containing [ino] */
1538
1539 INT_SET(key.ir_startino, ARCH_CONVERT, ino);
1540 if ((error = xfs_inobt_updkey(cur, &key, 1)))
1541 return error;
1542 }
1543 return 0;
1544 }
Unnamed repository; edit this file 'description' to name the repository.