2 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
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.
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.
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
20 #include "xfs_types.h"
24 #include "xfs_trans.h"
28 #include "xfs_dmapi.h"
29 #include "xfs_mount.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_ialloc_btree.h"
33 #include "xfs_dir2_sf.h"
34 #include "xfs_attr_sf.h"
35 #include "xfs_dinode.h"
36 #include "xfs_inode.h"
37 #include "xfs_inode_item.h"
38 #include "xfs_alloc.h"
39 #include "xfs_btree.h"
40 #include "xfs_ialloc.h"
41 #include "xfs_itable.h"
43 #include "xfs_error.h"
44 #include "xfs_quota.h"
46 #if defined(XFS_BMBT_TRACE)
47 ktrace_t *xfs_bmbt_trace_buf;
51 * Prototypes for internal btree functions.
55 STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
56 STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
57 STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
58 STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
59 STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
60 STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
61 __uint64_t *, xfs_btree_cur_t **, int *);
62 STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);
65 #if defined(XFS_BMBT_TRACE)
67 static char ARGS[] = "args";
68 static char ENTRY[] = "entry";
69 static char ERROR[] = "error";
71 static char EXIT[] = "exit";
74 * Add a trace buffer entry for the arguments given to the routine,
99 ip = cur->bc_private.b.ip;
100 whichfork = cur->bc_private.b.whichfork;
101 ktrace_enter(xfs_bmbt_trace_buf,
102 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
103 (void *)func, (void *)s, (void *)ip, (void *)cur,
104 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
105 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
106 (void *)a8, (void *)a9, (void *)a10);
107 ASSERT(ip->i_btrace);
108 ktrace_enter(ip->i_btrace,
109 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
110 (void *)func, (void *)s, (void *)ip, (void *)cur,
111 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
112 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
113 (void *)a8, (void *)a9, (void *)a10);
116 * Add a trace buffer entry for arguments, for a buffer & 1 integer arg.
119 xfs_bmbt_trace_argbi(
121 xfs_btree_cur_t *cur,
126 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBI, line,
127 (__psunsigned_t)b, i, 0, 0,
133 * Add a trace buffer entry for arguments, for a buffer & 2 integer args.
136 xfs_bmbt_trace_argbii(
138 xfs_btree_cur_t *cur,
144 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBII, line,
145 (__psunsigned_t)b, i0, i1, 0,
151 * Add a trace buffer entry for arguments, for 3 block-length args
152 * and an integer arg.
155 xfs_bmbt_trace_argfffi(
157 xfs_btree_cur_t *cur,
164 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGFFFI, line,
165 o >> 32, (int)o, b >> 32, (int)b,
166 i >> 32, (int)i, (int)j, 0,
171 * Add a trace buffer entry for arguments, for one integer arg.
176 xfs_btree_cur_t *cur,
180 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGI, line,
187 * Add a trace buffer entry for arguments, for int, fsblock, key.
190 xfs_bmbt_trace_argifk(
192 xfs_btree_cur_t *cur,
198 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
199 i, (xfs_dfsbno_t)f >> 32, (int)f, o >> 32,
205 * Add a trace buffer entry for arguments, for int, fsblock, rec.
208 xfs_bmbt_trace_argifr(
210 xfs_btree_cur_t *cur,
223 xfs_bmbt_disk_get_all(r, &s);
224 o = (xfs_dfiloff_t)s.br_startoff;
225 b = (xfs_dfsbno_t)s.br_startblock;
227 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFR, line,
228 i, d >> 32, (int)d, o >> 32,
229 (int)o, b >> 32, (int)b, c >> 32,
234 * Add a trace buffer entry for arguments, for int, key.
237 xfs_bmbt_trace_argik(
239 xfs_btree_cur_t *cur,
246 o = be64_to_cpu(k->br_startoff);
247 xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
248 i, o >> 32, (int)o, 0,
254 * Add a trace buffer entry for the cursor/operation.
257 xfs_bmbt_trace_cursor(
259 xfs_btree_cur_t *cur,
263 xfs_bmbt_rec_host_t r;
265 xfs_bmbt_set_all(&r, &cur->bc_rec.b);
266 xfs_bmbt_trace_enter(func, cur, s, XFS_BMBT_KTRACE_CUR, line,
267 (cur->bc_nlevels << 24) | (cur->bc_private.b.flags << 16) |
268 cur->bc_private.b.allocated,
269 r.l0 >> 32, (int)r.l0,
270 r.l1 >> 32, (int)r.l1,
271 (unsigned long)cur->bc_bufs[0], (unsigned long)cur->bc_bufs[1],
272 (unsigned long)cur->bc_bufs[2], (unsigned long)cur->bc_bufs[3],
273 (cur->bc_ptrs[0] << 16) | cur->bc_ptrs[1],
274 (cur->bc_ptrs[2] << 16) | cur->bc_ptrs[3]);
277 #define XFS_BMBT_TRACE_ARGBI(c,b,i) \
278 xfs_bmbt_trace_argbi(__func__, c, b, i, __LINE__)
279 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
280 xfs_bmbt_trace_argbii(__func__, c, b, i, j, __LINE__)
281 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
282 xfs_bmbt_trace_argfffi(__func__, c, o, b, i, j, __LINE__)
283 #define XFS_BMBT_TRACE_ARGI(c,i) \
284 xfs_bmbt_trace_argi(__func__, c, i, __LINE__)
285 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
286 xfs_bmbt_trace_argifk(__func__, c, i, f, s, __LINE__)
287 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
288 xfs_bmbt_trace_argifr(__func__, c, i, f, r, __LINE__)
289 #define XFS_BMBT_TRACE_ARGIK(c,i,k) \
290 xfs_bmbt_trace_argik(__func__, c, i, k, __LINE__)
291 #define XFS_BMBT_TRACE_CURSOR(c,s) \
292 xfs_bmbt_trace_cursor(__func__, c, s, __LINE__)
294 #define XFS_BMBT_TRACE_ARGBI(c,b,i)
295 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j)
296 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j)
297 #define XFS_BMBT_TRACE_ARGI(c,i)
298 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,s)
299 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r)
300 #define XFS_BMBT_TRACE_ARGIK(c,i,k)
301 #define XFS_BMBT_TRACE_CURSOR(c,s)
302 #endif /* XFS_BMBT_TRACE */
306 * Internal functions.
310 * Delete record pointed to by cur/level.
312 STATIC int /* error */
314 xfs_btree_cur_t *cur,
316 int *stat) /* success/failure */
318 xfs_bmbt_block_t *block; /* bmap btree block */
319 xfs_fsblock_t bno; /* fs-relative block number */
320 xfs_buf_t *bp; /* buffer for block */
321 int error; /* error return value */
322 int i; /* loop counter */
323 int j; /* temp state */
324 xfs_bmbt_key_t key; /* bmap btree key */
325 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
326 xfs_fsblock_t lbno; /* left sibling block number */
327 xfs_buf_t *lbp; /* left buffer pointer */
328 xfs_bmbt_block_t *left; /* left btree block */
329 xfs_bmbt_key_t *lkp; /* left btree key */
330 xfs_bmbt_ptr_t *lpp; /* left address pointer */
331 int lrecs=0; /* left record count */
332 xfs_bmbt_rec_t *lrp; /* left record pointer */
333 xfs_mount_t *mp; /* file system mount point */
334 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
335 int ptr; /* key/record index */
336 xfs_fsblock_t rbno; /* right sibling block number */
337 xfs_buf_t *rbp; /* right buffer pointer */
338 xfs_bmbt_block_t *right; /* right btree block */
339 xfs_bmbt_key_t *rkp; /* right btree key */
340 xfs_bmbt_rec_t *rp; /* pointer to bmap btree rec */
341 xfs_bmbt_ptr_t *rpp; /* right address pointer */
342 xfs_bmbt_block_t *rrblock; /* right-right btree block */
343 xfs_buf_t *rrbp; /* right-right buffer pointer */
344 int rrecs=0; /* right record count */
345 xfs_bmbt_rec_t *rrp; /* right record pointer */
346 xfs_btree_cur_t *tcur; /* temporary btree cursor */
347 int numrecs; /* temporary numrec count */
348 int numlrecs, numrrecs;
350 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
351 XFS_BMBT_TRACE_ARGI(cur, level);
352 ptr = cur->bc_ptrs[level];
355 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
359 block = xfs_bmbt_get_block(cur, level, &bp);
360 numrecs = be16_to_cpu(block->bb_numrecs);
362 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
363 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
368 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
372 XFS_STATS_INC(xs_bmbt_delrec);
374 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
375 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
377 for (i = ptr; i < numrecs; i++) {
378 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
379 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
385 memmove(&kp[ptr - 1], &kp[ptr],
386 (numrecs - ptr) * sizeof(*kp));
387 memmove(&pp[ptr - 1], &pp[ptr],
388 (numrecs - ptr) * sizeof(*pp));
389 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
390 xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
393 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
395 memmove(&rp[ptr - 1], &rp[ptr],
396 (numrecs - ptr) * sizeof(*rp));
397 xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
401 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
406 block->bb_numrecs = cpu_to_be16(numrecs);
407 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
409 * We're at the root level.
410 * First, shrink the root block in-memory.
411 * Try to get rid of the next level down.
412 * If we can't then there's nothing left to do.
414 if (level == cur->bc_nlevels - 1) {
415 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
416 cur->bc_private.b.whichfork);
417 if ((error = xfs_bmbt_killroot(cur))) {
418 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
421 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
422 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
425 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
429 if (ptr == 1 && (error = xfs_bmbt_updkey(cur, kp, level + 1))) {
430 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
433 if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
434 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
435 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
438 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
442 rbno = be64_to_cpu(block->bb_rightsib);
443 lbno = be64_to_cpu(block->bb_leftsib);
445 * One child of root, need to get a chance to copy its contents
446 * into the root and delete it. Can't go up to next level,
447 * there's nothing to delete there.
449 if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
450 level == cur->bc_nlevels - 2) {
451 if ((error = xfs_bmbt_killroot(cur))) {
452 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
455 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
456 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
459 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
463 ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
464 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
465 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
469 if (rbno != NULLFSBLOCK) {
470 i = xfs_btree_lastrec(tcur, level);
471 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
472 if ((error = xfs_bmbt_increment(tcur, level, &i))) {
473 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
476 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
477 i = xfs_btree_lastrec(tcur, level);
478 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
479 rbp = tcur->bc_bufs[level];
480 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
482 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
483 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
487 bno = be64_to_cpu(right->bb_leftsib);
488 if (be16_to_cpu(right->bb_numrecs) - 1 >=
489 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
490 if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
491 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
495 ASSERT(be16_to_cpu(block->bb_numrecs) >=
496 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
497 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
500 if ((error = xfs_bmbt_decrement(cur,
502 XFS_BMBT_TRACE_CURSOR(cur,
507 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
512 rrecs = be16_to_cpu(right->bb_numrecs);
513 if (lbno != NULLFSBLOCK) {
514 i = xfs_btree_firstrec(tcur, level);
515 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
516 if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
517 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
520 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
523 if (lbno != NULLFSBLOCK) {
524 i = xfs_btree_firstrec(tcur, level);
525 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
527 * decrement to last in block
529 if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
530 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
533 i = xfs_btree_firstrec(tcur, level);
534 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
535 lbp = tcur->bc_bufs[level];
536 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
538 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
539 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
543 bno = be64_to_cpu(left->bb_rightsib);
544 if (be16_to_cpu(left->bb_numrecs) - 1 >=
545 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
546 if ((error = xfs_bmbt_rshift(tcur, level, &i))) {
547 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
551 ASSERT(be16_to_cpu(block->bb_numrecs) >=
552 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
553 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
557 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
562 lrecs = be16_to_cpu(left->bb_numrecs);
564 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
567 ASSERT(bno != NULLFSBLOCK);
568 if (lbno != NULLFSBLOCK &&
569 lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
573 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
574 XFS_BMAP_BTREE_REF))) {
575 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
578 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
579 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
580 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
583 } else if (rbno != NULLFSBLOCK &&
584 rrecs + be16_to_cpu(block->bb_numrecs) <=
585 XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
589 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
590 XFS_BMAP_BTREE_REF))) {
591 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
594 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
595 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
596 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
599 lrecs = be16_to_cpu(left->bb_numrecs);
601 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
602 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
605 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
609 numlrecs = be16_to_cpu(left->bb_numrecs);
610 numrrecs = be16_to_cpu(right->bb_numrecs);
612 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
613 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
614 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
615 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
617 for (i = 0; i < numrrecs; i++) {
618 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
619 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
624 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
625 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
626 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
627 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
629 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
630 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
631 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
632 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
634 be16_add_cpu(&left->bb_numrecs, numrrecs);
635 left->bb_rightsib = right->bb_rightsib;
636 xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
637 if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
638 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
639 be64_to_cpu(left->bb_rightsib),
640 0, &rrbp, XFS_BMAP_BTREE_REF))) {
641 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
644 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
645 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
646 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
649 rrblock->bb_leftsib = cpu_to_be64(lbno);
650 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
652 xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
653 cur->bc_private.b.flist, mp);
654 cur->bc_private.b.ip->i_d.di_nblocks--;
655 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
656 XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
657 XFS_TRANS_DQ_BCOUNT, -1L);
658 xfs_trans_binval(cur->bc_tp, rbp);
660 cur->bc_bufs[level] = lbp;
661 cur->bc_ptrs[level] += lrecs;
662 cur->bc_ra[level] = 0;
663 } else if ((error = xfs_bmbt_increment(cur, level + 1, &i))) {
664 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
668 cur->bc_ptrs[level]--;
669 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
675 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
680 * Insert one record/level. Return information to the caller
681 * allowing the next level up to proceed if necessary.
683 STATIC int /* error */
685 xfs_btree_cur_t *cur,
688 xfs_bmbt_rec_t *recp,
689 xfs_btree_cur_t **curp,
690 int *stat) /* no-go/done/continue */
692 xfs_bmbt_block_t *block; /* bmap btree block */
693 xfs_buf_t *bp; /* buffer for block */
694 int error; /* error return value */
695 int i; /* loop index */
696 xfs_bmbt_key_t key; /* bmap btree key */
697 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
698 int logflags; /* inode logging flags */
699 xfs_fsblock_t nbno; /* new block number */
700 struct xfs_btree_cur *ncur; /* new btree cursor */
701 __uint64_t startoff; /* new btree key value */
702 xfs_bmbt_rec_t nrec; /* new record count */
703 int optr; /* old key/record index */
704 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
705 int ptr; /* key/record index */
706 xfs_bmbt_rec_t *rp=NULL; /* pointer to bmap btree rec */
709 ASSERT(level < cur->bc_nlevels);
710 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
711 XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
713 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
714 optr = ptr = cur->bc_ptrs[level];
716 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
720 XFS_STATS_INC(xs_bmbt_insrec);
721 block = xfs_bmbt_get_block(cur, level, &bp);
722 numrecs = be16_to_cpu(block->bb_numrecs);
724 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
725 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
728 if (ptr <= numrecs) {
730 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
731 xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
733 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
734 xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
739 if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
740 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
742 * A root block, that can be made bigger.
744 xfs_iroot_realloc(cur->bc_private.b.ip, 1,
745 cur->bc_private.b.whichfork);
746 block = xfs_bmbt_get_block(cur, level, &bp);
747 } else if (level == cur->bc_nlevels - 1) {
748 if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
750 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
753 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
755 block = xfs_bmbt_get_block(cur, level, &bp);
757 if ((error = xfs_bmbt_rshift(cur, level, &i))) {
758 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
764 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
765 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
769 optr = ptr = cur->bc_ptrs[level];
771 if ((error = xfs_bmbt_split(cur, level,
772 &nbno, &startoff, &ncur,
774 XFS_BMBT_TRACE_CURSOR(cur,
779 block = xfs_bmbt_get_block(
783 xfs_btree_check_lblock(cur,
784 block, level, bp))) {
785 XFS_BMBT_TRACE_CURSOR(
790 ptr = cur->bc_ptrs[level];
791 xfs_bmbt_disk_set_allf(&nrec,
795 XFS_BMBT_TRACE_CURSOR(cur,
804 numrecs = be16_to_cpu(block->bb_numrecs);
806 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
807 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
809 for (i = numrecs; i >= ptr; i--) {
810 if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
812 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
817 memmove(&kp[ptr], &kp[ptr - 1],
818 (numrecs - ptr + 1) * sizeof(*kp));
819 memmove(&pp[ptr], &pp[ptr - 1],
820 (numrecs - ptr + 1) * sizeof(*pp));
822 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
823 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
828 pp[ptr - 1] = cpu_to_be64(*bnop);
830 block->bb_numrecs = cpu_to_be16(numrecs);
831 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
832 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
834 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
835 memmove(&rp[ptr], &rp[ptr - 1],
836 (numrecs - ptr + 1) * sizeof(*rp));
839 block->bb_numrecs = cpu_to_be16(numrecs);
840 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
842 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
846 xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
849 xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
853 if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
854 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
858 if (nbno != NULLFSBLOCK) {
862 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
869 xfs_btree_cur_t *cur)
871 xfs_bmbt_block_t *block;
872 xfs_bmbt_block_t *cblock;
886 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
887 level = cur->bc_nlevels - 1;
890 * Don't deal with the root block needs to be a leaf case.
891 * We're just going to turn the thing back into extents anyway.
894 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
897 block = xfs_bmbt_get_block(cur, level, &cbp);
899 * Give up if the root has multiple children.
901 if (be16_to_cpu(block->bb_numrecs) != 1) {
902 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
906 * Only do this if the next level will fit.
907 * Then the data must be copied up to the inode,
908 * instead of freeing the root you free the next level.
910 cbp = cur->bc_bufs[level - 1];
911 cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
912 if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
913 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
916 ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
917 ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
918 ip = cur->bc_private.b.ip;
919 ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
920 ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
921 XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
922 i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
924 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
925 block = ifp->if_broot;
927 be16_add_cpu(&block->bb_numrecs, i);
928 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
929 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
930 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
931 memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
932 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
933 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
935 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
936 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
937 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
942 memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
943 xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
944 cur->bc_private.b.flist, cur->bc_mp);
945 ip->i_d.di_nblocks--;
946 XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
947 XFS_TRANS_DQ_BCOUNT, -1L);
948 xfs_trans_binval(cur->bc_tp, cbp);
949 cur->bc_bufs[level - 1] = NULL;
950 be16_add_cpu(&block->bb_level, -1);
951 xfs_trans_log_inode(cur->bc_tp, ip,
952 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
954 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
959 * Log key values from the btree block.
963 xfs_btree_cur_t *cur,
970 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
971 XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
974 xfs_bmbt_block_t *block;
979 block = XFS_BUF_TO_BMBT_BLOCK(bp);
980 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
981 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
982 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
983 xfs_trans_log_buf(tp, bp, first, last);
987 ip = cur->bc_private.b.ip;
988 xfs_trans_log_inode(tp, ip,
989 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
991 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
995 * Log pointer values from the btree block.
999 xfs_btree_cur_t *cur,
1006 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1007 XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
1010 xfs_bmbt_block_t *block;
1015 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1016 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
1017 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
1018 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
1019 xfs_trans_log_buf(tp, bp, first, last);
1023 ip = cur->bc_private.b.ip;
1024 xfs_trans_log_inode(tp, ip,
1025 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1027 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1031 * Lookup the record. The cursor is made to point to it, based on dir.
1033 STATIC int /* error */
1035 xfs_btree_cur_t *cur,
1037 int *stat) /* success/failure */
1039 xfs_bmbt_block_t *block=NULL;
1043 int error; /* error return value */
1044 xfs_fsblock_t fsbno=0;
1048 xfs_bmbt_key_t *kkbase=NULL;
1049 xfs_bmbt_key_t *kkp;
1050 xfs_bmbt_rec_t *krbase=NULL;
1051 xfs_bmbt_rec_t *krp;
1056 xfs_bmbt_irec_t *rp;
1057 xfs_fileoff_t startoff;
1060 XFS_STATS_INC(xs_bmbt_lookup);
1061 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1062 XFS_BMBT_TRACE_ARGI(cur, (int)dir);
1065 rp = &cur->bc_rec.b;
1066 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1067 if (level < cur->bc_nlevels - 1) {
1068 d = XFS_FSB_TO_DADDR(mp, fsbno);
1069 bp = cur->bc_bufs[level];
1070 if (bp && XFS_BUF_ADDR(bp) != d)
1073 if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
1074 0, &bp, XFS_BMAP_BTREE_REF))) {
1075 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1078 xfs_btree_setbuf(cur, level, bp);
1079 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1080 if ((error = xfs_btree_check_lblock(cur, block,
1082 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1086 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1088 block = xfs_bmbt_get_block(cur, level, &bp);
1093 kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
1095 krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
1097 if (!(high = be16_to_cpu(block->bb_numrecs))) {
1099 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1100 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1104 while (low <= high) {
1105 XFS_STATS_INC(xs_bmbt_compare);
1106 keyno = (low + high) >> 1;
1108 kkp = kkbase + keyno - 1;
1109 startoff = be64_to_cpu(kkp->br_startoff);
1111 krp = krbase + keyno - 1;
1112 startoff = xfs_bmbt_disk_get_startoff(krp);
1114 diff = (xfs_sfiloff_t)
1115 (startoff - rp->br_startoff);
1125 if (diff > 0 && --keyno < 1)
1127 pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
1128 fsbno = be64_to_cpu(*pp);
1130 if ((error = xfs_btree_check_lptr(cur, fsbno, level))) {
1131 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1135 cur->bc_ptrs[level] = keyno;
1138 if (dir != XFS_LOOKUP_LE && diff < 0) {
1141 * If ge search and we went off the end of the block, but it's
1142 * not the last block, we're in the wrong block.
1144 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
1145 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
1146 cur->bc_ptrs[0] = keyno;
1147 if ((error = xfs_bmbt_increment(cur, 0, &i))) {
1148 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1151 XFS_WANT_CORRUPTED_RETURN(i == 1);
1152 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1157 else if (dir == XFS_LOOKUP_LE && diff > 0)
1159 cur->bc_ptrs[0] = keyno;
1160 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
1161 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1164 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1165 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1171 * Move 1 record left from cur/level if possible.
1172 * Update cur to reflect the new path.
1174 STATIC int /* error */
1176 xfs_btree_cur_t *cur,
1178 int *stat) /* success/failure */
1180 int error; /* error return value */
1182 int i; /* loop counter */
1184 xfs_bmbt_key_t key; /* bmap btree key */
1185 xfs_buf_t *lbp; /* left buffer pointer */
1186 xfs_bmbt_block_t *left; /* left btree block */
1187 xfs_bmbt_key_t *lkp=NULL; /* left btree key */
1188 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1189 int lrecs; /* left record count */
1190 xfs_bmbt_rec_t *lrp=NULL; /* left record pointer */
1191 xfs_mount_t *mp; /* file system mount point */
1192 xfs_buf_t *rbp; /* right buffer pointer */
1193 xfs_bmbt_block_t *right; /* right btree block */
1194 xfs_bmbt_key_t *rkp=NULL; /* right btree key */
1195 xfs_bmbt_ptr_t *rpp=NULL; /* right address pointer */
1196 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
1197 int rrecs; /* right record count */
1199 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1200 XFS_BMBT_TRACE_ARGI(cur, level);
1201 if (level == cur->bc_nlevels - 1) {
1202 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1206 rbp = cur->bc_bufs[level];
1207 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1209 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1210 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1214 if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
1215 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1219 if (cur->bc_ptrs[level] <= 1) {
1220 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1225 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
1226 &lbp, XFS_BMAP_BTREE_REF))) {
1227 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1230 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1231 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1232 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1235 if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1236 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1240 lrecs = be16_to_cpu(left->bb_numrecs) + 1;
1242 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
1243 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1245 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
1246 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
1247 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1249 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
1250 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1255 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
1257 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
1258 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1260 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
1262 left->bb_numrecs = cpu_to_be16(lrecs);
1263 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1266 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
1268 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
1270 rrecs = be16_to_cpu(right->bb_numrecs) - 1;
1271 right->bb_numrecs = cpu_to_be16(rrecs);
1272 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1275 for (i = 0; i < rrecs; i++) {
1276 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
1278 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1283 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
1284 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
1285 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
1286 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
1288 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
1289 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
1290 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1293 if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
1294 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1297 cur->bc_ptrs[level]--;
1298 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1304 * Move 1 record right from cur/level if possible.
1305 * Update cur to reflect the new path.
1307 STATIC int /* error */
1309 xfs_btree_cur_t *cur,
1311 int *stat) /* success/failure */
1313 int error; /* error return value */
1314 int i; /* loop counter */
1315 xfs_bmbt_key_t key; /* bmap btree key */
1316 xfs_buf_t *lbp; /* left buffer pointer */
1317 xfs_bmbt_block_t *left; /* left btree block */
1318 xfs_bmbt_key_t *lkp; /* left btree key */
1319 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1320 xfs_bmbt_rec_t *lrp; /* left record pointer */
1321 xfs_mount_t *mp; /* file system mount point */
1322 xfs_buf_t *rbp; /* right buffer pointer */
1323 xfs_bmbt_block_t *right; /* right btree block */
1324 xfs_bmbt_key_t *rkp; /* right btree key */
1325 xfs_bmbt_ptr_t *rpp; /* right address pointer */
1326 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
1327 struct xfs_btree_cur *tcur; /* temporary btree cursor */
1329 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1330 XFS_BMBT_TRACE_ARGI(cur, level);
1331 if (level == cur->bc_nlevels - 1) {
1332 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1336 lbp = cur->bc_bufs[level];
1337 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1339 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1340 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1344 if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
1345 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1349 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1350 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1355 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
1356 &rbp, XFS_BMAP_BTREE_REF))) {
1357 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1360 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1361 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1362 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1365 if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1366 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1371 lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1372 lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1373 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1374 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1376 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1377 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1378 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1383 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1384 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1386 if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
1387 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1393 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1394 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1396 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1397 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1398 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1400 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1401 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1404 be16_add_cpu(&left->bb_numrecs, -1);
1405 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1406 be16_add_cpu(&right->bb_numrecs, 1);
1409 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1411 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1413 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1414 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1415 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1418 i = xfs_btree_lastrec(tcur, level);
1419 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1420 if ((error = xfs_bmbt_increment(tcur, level, &i))) {
1421 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1424 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1425 if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {
1426 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1429 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1430 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1434 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1436 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1441 * Determine the extent state.
1450 ASSERT(blks != 0); /* saved for DMIG */
1451 return XFS_EXT_UNWRITTEN;
1453 return XFS_EXT_NORM;
1458 * Split cur/level block in half.
1459 * Return new block number and its first record (to be inserted into parent).
1461 STATIC int /* error */
1463 xfs_btree_cur_t *cur,
1465 xfs_fsblock_t *bnop,
1466 __uint64_t *startoff,
1467 xfs_btree_cur_t **curp,
1468 int *stat) /* success/failure */
1470 xfs_alloc_arg_t args; /* block allocation args */
1471 int error; /* error return value */
1472 int i; /* loop counter */
1473 xfs_fsblock_t lbno; /* left sibling block number */
1474 xfs_buf_t *lbp; /* left buffer pointer */
1475 xfs_bmbt_block_t *left; /* left btree block */
1476 xfs_bmbt_key_t *lkp; /* left btree key */
1477 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1478 xfs_bmbt_rec_t *lrp; /* left record pointer */
1479 xfs_buf_t *rbp; /* right buffer pointer */
1480 xfs_bmbt_block_t *right; /* right btree block */
1481 xfs_bmbt_key_t *rkp; /* right btree key */
1482 xfs_bmbt_ptr_t *rpp; /* right address pointer */
1483 xfs_bmbt_block_t *rrblock; /* right-right btree block */
1484 xfs_buf_t *rrbp; /* right-right buffer pointer */
1485 xfs_bmbt_rec_t *rrp; /* right record pointer */
1487 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1488 XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
1489 args.tp = cur->bc_tp;
1490 args.mp = cur->bc_mp;
1491 lbp = cur->bc_bufs[level];
1492 lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1493 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1494 args.fsbno = cur->bc_private.b.firstblock;
1495 args.firstblock = args.fsbno;
1497 if (args.fsbno == NULLFSBLOCK) {
1499 args.type = XFS_ALLOCTYPE_START_BNO;
1501 * Make sure there is sufficient room left in the AG to
1502 * complete a full tree split for an extent insert. If
1503 * we are converting the middle part of an extent then
1504 * we may need space for two tree splits.
1506 * We are relying on the caller to make the correct block
1507 * reservation for this operation to succeed. If the
1508 * reservation amount is insufficient then we may fail a
1509 * block allocation here and corrupt the filesystem.
1511 args.minleft = xfs_trans_get_block_res(args.tp);
1512 } else if (cur->bc_private.b.flist->xbf_low)
1513 args.type = XFS_ALLOCTYPE_START_BNO;
1515 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1516 args.mod = args.alignment = args.total = args.isfl =
1517 args.userdata = args.minalignslop = 0;
1518 args.minlen = args.maxlen = args.prod = 1;
1519 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1520 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1521 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1522 return XFS_ERROR(ENOSPC);
1524 if ((error = xfs_alloc_vextent(&args))) {
1525 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1528 if (args.fsbno == NULLFSBLOCK) {
1529 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1533 ASSERT(args.len == 1);
1534 cur->bc_private.b.firstblock = args.fsbno;
1535 cur->bc_private.b.allocated++;
1536 cur->bc_private.b.ip->i_d.di_nblocks++;
1537 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1538 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1539 XFS_TRANS_DQ_BCOUNT, 1L);
1540 rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1541 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1543 if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1544 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1548 right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1549 right->bb_level = left->bb_level;
1550 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1551 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1552 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1553 be16_add_cpu(&right->bb_numrecs, 1);
1554 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1556 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1557 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1558 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1559 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1561 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1562 if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
1563 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1568 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1569 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1570 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1571 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1572 *startoff = be64_to_cpu(rkp->br_startoff);
1574 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1575 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1576 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1577 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1578 *startoff = xfs_bmbt_disk_get_startoff(rrp);
1580 be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1581 right->bb_rightsib = left->bb_rightsib;
1582 left->bb_rightsib = cpu_to_be64(args.fsbno);
1583 right->bb_leftsib = cpu_to_be64(lbno);
1584 xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1585 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1586 if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
1587 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
1588 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
1589 XFS_BMAP_BTREE_REF))) {
1590 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1593 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1594 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1595 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1598 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
1599 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1601 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1602 xfs_btree_setbuf(cur, level, rbp);
1603 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1605 if (level + 1 < cur->bc_nlevels) {
1606 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1607 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1610 (*curp)->bc_ptrs[level + 1]++;
1613 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1620 * Update keys for the record.
1624 xfs_btree_cur_t *cur,
1625 xfs_bmbt_key_t *keyp, /* on-disk format */
1628 xfs_bmbt_block_t *block;
1637 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1638 XFS_BMBT_TRACE_ARGIK(cur, level, keyp);
1639 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1640 block = xfs_bmbt_get_block(cur, level, &bp);
1642 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1643 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1647 ptr = cur->bc_ptrs[level];
1648 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
1650 xfs_bmbt_log_keys(cur, bp, ptr, ptr);
1652 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1657 * Convert on-disk form of btree root to in-memory form.
1661 xfs_bmdr_block_t *dblock,
1663 xfs_bmbt_block_t *rblock,
1667 xfs_bmbt_key_t *fkp;
1669 xfs_bmbt_key_t *tkp;
1672 rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1673 rblock->bb_level = dblock->bb_level;
1674 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1675 rblock->bb_numrecs = dblock->bb_numrecs;
1676 rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
1677 rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
1678 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1679 fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1680 tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1681 fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1682 tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1683 dmxr = be16_to_cpu(dblock->bb_numrecs);
1684 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1685 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1689 * Decrement cursor by one record at the level.
1690 * For nonzero levels the leaf-ward information is untouched.
1694 xfs_btree_cur_t *cur,
1696 int *stat) /* success/failure */
1698 xfs_bmbt_block_t *block;
1700 int error; /* error return value */
1701 xfs_fsblock_t fsbno;
1706 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1707 XFS_BMBT_TRACE_ARGI(cur, level);
1708 ASSERT(level < cur->bc_nlevels);
1709 if (level < cur->bc_nlevels - 1)
1710 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1711 if (--cur->bc_ptrs[level] > 0) {
1712 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1716 block = xfs_bmbt_get_block(cur, level, &bp);
1718 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1719 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1723 if (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO) {
1724 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1728 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1729 if (--cur->bc_ptrs[lev] > 0)
1731 if (lev < cur->bc_nlevels - 1)
1732 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1734 if (lev == cur->bc_nlevels) {
1735 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1741 for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
1742 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
1743 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1744 XFS_BMAP_BTREE_REF))) {
1745 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1749 xfs_btree_setbuf(cur, lev, bp);
1750 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1751 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1752 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1755 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
1757 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1763 * Delete the record pointed to by cur.
1767 xfs_btree_cur_t *cur,
1768 int *stat) /* success/failure */
1770 int error; /* error return value */
1774 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1775 for (level = 0, i = 2; i == 2; level++) {
1776 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1777 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1782 for (level = 1; level < cur->bc_nlevels; level++) {
1783 if (cur->bc_ptrs[level] == 0) {
1784 if ((error = xfs_bmbt_decrement(cur, level,
1786 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1793 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1799 * Convert a compressed bmap extent record to an uncompressed form.
1800 * This code must be in sync with the routines xfs_bmbt_get_startoff,
1801 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1813 ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1814 s->br_startoff = ((xfs_fileoff_t)l0 &
1815 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1817 s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1818 (((xfs_fsblock_t)l1) >> 21);
1824 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1825 (((xfs_dfsbno_t)l1) >> 21);
1826 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1827 s->br_startblock = (xfs_fsblock_t)b;
1830 s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1832 #endif /* XFS_BIG_BLKNOS */
1833 s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1834 /* This is xfs_extent_state() in-line */
1836 ASSERT(s->br_blockcount != 0); /* saved for DMIG */
1837 st = XFS_EXT_UNWRITTEN;
1845 xfs_bmbt_rec_host_t *r,
1848 __xfs_bmbt_get_all(r->l0, r->l1, s);
1852 * Get the block pointer for the given level of the cursor.
1853 * Fill in the buffer pointer, if applicable.
1857 xfs_btree_cur_t *cur,
1862 xfs_bmbt_block_t *rval;
1864 if (level < cur->bc_nlevels - 1) {
1865 *bpp = cur->bc_bufs[level];
1866 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1869 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1870 cur->bc_private.b.whichfork);
1871 rval = ifp->if_broot;
1877 * Extract the blockcount field from an in memory bmap extent record.
1880 xfs_bmbt_get_blockcount(
1881 xfs_bmbt_rec_host_t *r)
1883 return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1887 * Extract the startblock field from an in memory bmap extent record.
1890 xfs_bmbt_get_startblock(
1891 xfs_bmbt_rec_host_t *r)
1894 return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1895 (((xfs_fsblock_t)r->l1) >> 21);
1900 b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1901 (((xfs_dfsbno_t)r->l1) >> 21);
1902 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1903 return (xfs_fsblock_t)b;
1905 return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1907 #endif /* XFS_BIG_BLKNOS */
1911 * Extract the startoff field from an in memory bmap extent record.
1914 xfs_bmbt_get_startoff(
1915 xfs_bmbt_rec_host_t *r)
1917 return ((xfs_fileoff_t)r->l0 &
1918 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1923 xfs_bmbt_rec_host_t *r)
1927 ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
1928 return xfs_extent_state(xfs_bmbt_get_blockcount(r),
1932 /* Endian flipping versions of the bmbt extraction functions */
1934 xfs_bmbt_disk_get_all(
1938 __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
1942 * Extract the blockcount field from an on disk bmap extent record.
1945 xfs_bmbt_disk_get_blockcount(
1948 return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
1952 * Extract the startoff field from a disk format bmap extent record.
1955 xfs_bmbt_disk_get_startoff(
1958 return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
1959 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1963 * Increment cursor by one record at the level.
1964 * For nonzero levels the leaf-ward information is untouched.
1968 xfs_btree_cur_t *cur,
1970 int *stat) /* success/failure */
1972 xfs_bmbt_block_t *block;
1974 int error; /* error return value */
1975 xfs_fsblock_t fsbno;
1980 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1981 XFS_BMBT_TRACE_ARGI(cur, level);
1982 ASSERT(level < cur->bc_nlevels);
1983 if (level < cur->bc_nlevels - 1)
1984 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1985 block = xfs_bmbt_get_block(cur, level, &bp);
1987 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1988 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1992 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1993 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1997 if (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO) {
1998 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2002 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
2003 block = xfs_bmbt_get_block(cur, lev, &bp);
2005 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2006 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2010 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
2012 if (lev < cur->bc_nlevels - 1)
2013 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2015 if (lev == cur->bc_nlevels) {
2016 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2022 for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
2023 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
2024 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
2025 XFS_BMAP_BTREE_REF))) {
2026 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2030 xfs_btree_setbuf(cur, lev, bp);
2031 block = XFS_BUF_TO_BMBT_BLOCK(bp);
2032 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2033 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2036 cur->bc_ptrs[lev] = 1;
2038 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2044 * Insert the current record at the point referenced by cur.
2046 * A multi-level split of the tree on insert will invalidate the original
2047 * cursor. All callers of this function should assume that the cursor is
2048 * no longer valid and revalidate it.
2052 xfs_btree_cur_t *cur,
2053 int *stat) /* success/failure */
2055 int error; /* error return value */
2059 xfs_btree_cur_t *ncur;
2060 xfs_bmbt_rec_t nrec;
2061 xfs_btree_cur_t *pcur;
2063 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2066 xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
2070 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
2073 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2074 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2077 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2078 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
2079 cur->bc_nlevels = pcur->bc_nlevels;
2080 cur->bc_private.b.allocated +=
2081 pcur->bc_private.b.allocated;
2082 pcur->bc_private.b.allocated = 0;
2083 ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
2084 XFS_IS_REALTIME_INODE(cur->bc_private.b.ip));
2085 cur->bc_private.b.firstblock =
2086 pcur->bc_private.b.firstblock;
2087 ASSERT(cur->bc_private.b.flist ==
2088 pcur->bc_private.b.flist);
2089 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2095 } while (nbno != NULLFSBLOCK);
2096 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2100 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2105 * Log fields from the btree block header.
2109 xfs_btree_cur_t *cur,
2116 static const short offsets[] = {
2117 offsetof(xfs_bmbt_block_t, bb_magic),
2118 offsetof(xfs_bmbt_block_t, bb_level),
2119 offsetof(xfs_bmbt_block_t, bb_numrecs),
2120 offsetof(xfs_bmbt_block_t, bb_leftsib),
2121 offsetof(xfs_bmbt_block_t, bb_rightsib),
2122 sizeof(xfs_bmbt_block_t)
2125 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2126 XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
2129 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
2131 xfs_trans_log_buf(tp, bp, first, last);
2133 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
2134 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
2135 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2139 * Log record values from the btree block.
2143 xfs_btree_cur_t *cur,
2148 xfs_bmbt_block_t *block;
2154 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2155 XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
2158 block = XFS_BUF_TO_BMBT_BLOCK(bp);
2159 rp = XFS_BMAP_REC_DADDR(block, 1, cur);
2160 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
2161 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
2162 xfs_trans_log_buf(tp, bp, first, last);
2163 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2168 xfs_btree_cur_t *cur,
2172 int *stat) /* success/failure */
2174 cur->bc_rec.b.br_startoff = off;
2175 cur->bc_rec.b.br_startblock = bno;
2176 cur->bc_rec.b.br_blockcount = len;
2177 return xfs_bmbt_lookup(cur, XFS_LOOKUP_EQ, stat);
2182 xfs_btree_cur_t *cur,
2186 int *stat) /* success/failure */
2188 cur->bc_rec.b.br_startoff = off;
2189 cur->bc_rec.b.br_startblock = bno;
2190 cur->bc_rec.b.br_blockcount = len;
2191 return xfs_bmbt_lookup(cur, XFS_LOOKUP_GE, stat);
2195 * Give the bmap btree a new root block. Copy the old broot contents
2196 * down into a real block and make the broot point to it.
2200 xfs_btree_cur_t *cur, /* btree cursor */
2201 int *logflags, /* logging flags for inode */
2202 int *stat) /* return status - 0 fail */
2204 xfs_alloc_arg_t args; /* allocation arguments */
2205 xfs_bmbt_block_t *block; /* bmap btree block */
2206 xfs_buf_t *bp; /* buffer for block */
2207 xfs_bmbt_block_t *cblock; /* child btree block */
2208 xfs_bmbt_key_t *ckp; /* child key pointer */
2209 xfs_bmbt_ptr_t *cpp; /* child ptr pointer */
2210 int error; /* error return code */
2212 int i; /* loop counter */
2214 xfs_bmbt_key_t *kp; /* pointer to bmap btree key */
2215 int level; /* btree level */
2216 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
2218 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2219 level = cur->bc_nlevels - 1;
2220 block = xfs_bmbt_get_block(cur, level, &bp);
2222 * Copy the root into a real block.
2224 args.mp = cur->bc_mp;
2225 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
2226 args.tp = cur->bc_tp;
2227 args.fsbno = cur->bc_private.b.firstblock;
2228 args.mod = args.minleft = args.alignment = args.total = args.isfl =
2229 args.userdata = args.minalignslop = 0;
2230 args.minlen = args.maxlen = args.prod = 1;
2231 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
2232 args.firstblock = args.fsbno;
2233 if (args.fsbno == NULLFSBLOCK) {
2235 if ((error = xfs_btree_check_lptr_disk(cur, *pp, level))) {
2236 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2240 args.fsbno = be64_to_cpu(*pp);
2241 args.type = XFS_ALLOCTYPE_START_BNO;
2242 } else if (cur->bc_private.b.flist->xbf_low)
2243 args.type = XFS_ALLOCTYPE_START_BNO;
2245 args.type = XFS_ALLOCTYPE_NEAR_BNO;
2246 if ((error = xfs_alloc_vextent(&args))) {
2247 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2250 if (args.fsbno == NULLFSBLOCK) {
2251 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2255 ASSERT(args.len == 1);
2256 cur->bc_private.b.firstblock = args.fsbno;
2257 cur->bc_private.b.allocated++;
2258 cur->bc_private.b.ip->i_d.di_nblocks++;
2259 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
2260 XFS_TRANS_DQ_BCOUNT, 1L);
2261 bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
2262 cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
2264 be16_add_cpu(&block->bb_level, 1);
2265 block->bb_numrecs = cpu_to_be16(1);
2267 cur->bc_ptrs[level + 1] = 1;
2268 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
2269 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
2270 memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
2271 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
2273 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2274 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
2275 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2280 memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
2282 if ((error = xfs_btree_check_lptr(cur, args.fsbno, level))) {
2283 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2287 *pp = cpu_to_be64(args.fsbno);
2288 xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
2289 cur->bc_private.b.whichfork);
2290 xfs_btree_setbuf(cur, level, bp);
2292 * Do all this logging at the end so that
2293 * the root is at the right level.
2295 xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
2296 xfs_bmbt_log_keys(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
2297 xfs_bmbt_log_ptrs(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
2298 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2300 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
2306 * Set all the fields in a bmap extent record from the arguments.
2310 xfs_bmbt_rec_host_t *r,
2311 xfs_fileoff_t startoff,
2312 xfs_fsblock_t startblock,
2313 xfs_filblks_t blockcount,
2316 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
2318 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
2319 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2320 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2323 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2325 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2326 ((xfs_bmbt_rec_base_t)startoff << 9) |
2327 ((xfs_bmbt_rec_base_t)startblock >> 43);
2328 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
2329 ((xfs_bmbt_rec_base_t)blockcount &
2330 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2331 #else /* !XFS_BIG_BLKNOS */
2332 if (ISNULLSTARTBLOCK(startblock)) {
2333 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2334 ((xfs_bmbt_rec_base_t)startoff << 9) |
2335 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2336 r->l1 = XFS_MASK64HI(11) |
2337 ((xfs_bmbt_rec_base_t)startblock << 21) |
2338 ((xfs_bmbt_rec_base_t)blockcount &
2339 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2341 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2342 ((xfs_bmbt_rec_base_t)startoff << 9);
2343 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
2344 ((xfs_bmbt_rec_base_t)blockcount &
2345 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2347 #endif /* XFS_BIG_BLKNOS */
2351 * Set all the fields in a bmap extent record from the uncompressed form.
2355 xfs_bmbt_rec_host_t *r,
2358 xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
2359 s->br_blockcount, s->br_state);
2364 * Set all the fields in a disk format bmap extent record from the arguments.
2367 xfs_bmbt_disk_set_allf(
2369 xfs_fileoff_t startoff,
2370 xfs_fsblock_t startblock,
2371 xfs_filblks_t blockcount,
2374 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
2376 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
2377 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2378 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2381 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2383 r->l0 = cpu_to_be64(
2384 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2385 ((xfs_bmbt_rec_base_t)startoff << 9) |
2386 ((xfs_bmbt_rec_base_t)startblock >> 43));
2387 r->l1 = cpu_to_be64(
2388 ((xfs_bmbt_rec_base_t)startblock << 21) |
2389 ((xfs_bmbt_rec_base_t)blockcount &
2390 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2391 #else /* !XFS_BIG_BLKNOS */
2392 if (ISNULLSTARTBLOCK(startblock)) {
2393 r->l0 = cpu_to_be64(
2394 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2395 ((xfs_bmbt_rec_base_t)startoff << 9) |
2396 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2397 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
2398 ((xfs_bmbt_rec_base_t)startblock << 21) |
2399 ((xfs_bmbt_rec_base_t)blockcount &
2400 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2402 r->l0 = cpu_to_be64(
2403 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2404 ((xfs_bmbt_rec_base_t)startoff << 9));
2405 r->l1 = cpu_to_be64(
2406 ((xfs_bmbt_rec_base_t)startblock << 21) |
2407 ((xfs_bmbt_rec_base_t)blockcount &
2408 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2410 #endif /* XFS_BIG_BLKNOS */
2414 * Set all the fields in a bmap extent record from the uncompressed form.
2417 xfs_bmbt_disk_set_all(
2421 xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
2422 s->br_blockcount, s->br_state);
2426 * Set the blockcount field in a bmap extent record.
2429 xfs_bmbt_set_blockcount(
2430 xfs_bmbt_rec_host_t *r,
2433 ASSERT((v & XFS_MASK64HI(43)) == 0);
2434 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
2435 (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
2439 * Set the startblock field in a bmap extent record.
2442 xfs_bmbt_set_startblock(
2443 xfs_bmbt_rec_host_t *r,
2447 ASSERT((v & XFS_MASK64HI(12)) == 0);
2448 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
2449 (xfs_bmbt_rec_base_t)(v >> 43);
2450 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
2451 (xfs_bmbt_rec_base_t)(v << 21);
2452 #else /* !XFS_BIG_BLKNOS */
2453 if (ISNULLSTARTBLOCK(v)) {
2454 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2455 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
2456 ((xfs_bmbt_rec_base_t)v << 21) |
2457 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2459 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2460 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
2461 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2463 #endif /* XFS_BIG_BLKNOS */
2467 * Set the startoff field in a bmap extent record.
2470 xfs_bmbt_set_startoff(
2471 xfs_bmbt_rec_host_t *r,
2474 ASSERT((v & XFS_MASK64HI(9)) == 0);
2475 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
2476 ((xfs_bmbt_rec_base_t)v << 9) |
2477 (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2481 * Set the extent state field in a bmap extent record.
2485 xfs_bmbt_rec_host_t *r,
2488 ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
2489 if (v == XFS_EXT_NORM)
2490 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
2492 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
2496 * Convert in-memory form of btree root to on-disk form.
2500 xfs_bmbt_block_t *rblock,
2502 xfs_bmdr_block_t *dblock,
2506 xfs_bmbt_key_t *fkp;
2508 xfs_bmbt_key_t *tkp;
2511 ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
2512 ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
2513 ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
2514 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
2515 dblock->bb_level = rblock->bb_level;
2516 dblock->bb_numrecs = rblock->bb_numrecs;
2517 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2518 fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2519 tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
2520 fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
2521 tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
2522 dmxr = be16_to_cpu(dblock->bb_numrecs);
2523 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
2524 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
2528 * Update the record to the passed values.
2532 xfs_btree_cur_t *cur,
2538 xfs_bmbt_block_t *block;
2545 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2546 XFS_BMBT_TRACE_ARGFFFI(cur, (xfs_dfiloff_t)off, (xfs_dfsbno_t)bno,
2547 (xfs_dfilblks_t)len, (int)state);
2548 block = xfs_bmbt_get_block(cur, 0, &bp);
2550 if ((error = xfs_btree_check_lblock(cur, block, 0, bp))) {
2551 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2555 ptr = cur->bc_ptrs[0];
2556 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
2557 xfs_bmbt_disk_set_allf(rp, off, bno, len, state);
2558 xfs_bmbt_log_recs(cur, bp, ptr, ptr);
2560 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2563 key.br_startoff = cpu_to_be64(off);
2564 if ((error = xfs_bmbt_updkey(cur, &key, 1))) {
2565 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2568 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2573 * Check extent records, which have just been read, for
2574 * any bit in the extent flag field. ASSERT on debug
2575 * kernels, as this condition should not occur.
2576 * Return an error condition (1) if any flags found,
2577 * otherwise return 0.
2581 xfs_check_nostate_extents(
2586 for (; num > 0; num--, idx++) {
2587 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
2589 (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {