aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_bmap_btree.c
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:57:40 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:57:40 -0400
commit4b22a57188d87e873346b73c227607715be96399 (patch)
tree4cf2d0deede695968b7a32b098c0c64fac8610e5 /fs/xfs/xfs_bmap_btree.c
parentea77b0a66e6c910ef265d9af522d6303ea6b3055 (diff)
[XFS] implement generic xfs_btree_insert/insrec
Make the btree insert code generic. Based on a patch from David Chinner with lots of changes to follow the original btree implementations more closely. While this loses some of the generic helper routines for inserting/moving/removing records it also solves some of the one off bugs in the original code and makes it easier to verify. SGI-PV: 985583 SGI-Modid: xfs-linux-melb:xfs-kern:32202a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: Bill O'Donnell <billodo@sgi.com> Signed-off-by: David Chinner <david@fromorbit.com>
Diffstat (limited to 'fs/xfs/xfs_bmap_btree.c')
-rw-r--r--fs/xfs/xfs_bmap_btree.c308
1 files changed, 55 insertions, 253 deletions
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 204f276aeaad..2b15df32b7d2 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -456,198 +456,6 @@ error0:
456 return error; 456 return error;
457} 457}
458 458
459/*
460 * Insert one record/level. Return information to the caller
461 * allowing the next level up to proceed if necessary.
462 */
463STATIC int /* error */
464xfs_bmbt_insrec(
465 xfs_btree_cur_t *cur,
466 int level,
467 xfs_fsblock_t *bnop,
468 xfs_bmbt_rec_t *recp,
469 xfs_btree_cur_t **curp,
470 int *stat) /* no-go/done/continue */
471{
472 xfs_bmbt_block_t *block; /* bmap btree block */
473 xfs_buf_t *bp; /* buffer for block */
474 int error; /* error return value */
475 int i; /* loop index */
476 xfs_bmbt_key_t key; /* bmap btree key */
477 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
478 int logflags; /* inode logging flags */
479 xfs_fsblock_t nbno; /* new block number */
480 struct xfs_btree_cur *ncur; /* new btree cursor */
481 __uint64_t startoff; /* new btree key value */
482 xfs_bmbt_rec_t nrec; /* new record count */
483 int optr; /* old key/record index */
484 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
485 int ptr; /* key/record index */
486 xfs_bmbt_rec_t *rp=NULL; /* pointer to bmap btree rec */
487 int numrecs;
488
489 ASSERT(level < cur->bc_nlevels);
490 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
491 XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
492 ncur = NULL;
493 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
494 optr = ptr = cur->bc_ptrs[level];
495 if (ptr == 0) {
496 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
497 *stat = 0;
498 return 0;
499 }
500 XFS_STATS_INC(xs_bmbt_insrec);
501 block = xfs_bmbt_get_block(cur, level, &bp);
502 numrecs = be16_to_cpu(block->bb_numrecs);
503#ifdef DEBUG
504 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
505 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
506 return error;
507 }
508 if (ptr <= numrecs) {
509 if (level == 0) {
510 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
511 xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
512 } else {
513 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
514 xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
515 }
516 }
517#endif
518 nbno = NULLFSBLOCK;
519 if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
520 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
521 /*
522 * A root block, that can be made bigger.
523 */
524 xfs_iroot_realloc(cur->bc_private.b.ip, 1,
525 cur->bc_private.b.whichfork);
526 block = xfs_bmbt_get_block(cur, level, &bp);
527 } else if (level == cur->bc_nlevels - 1) {
528 if ((error = xfs_btree_new_iroot(cur, &logflags, stat)) ||
529 *stat == 0) {
530 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
531 return error;
532 }
533 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
534 logflags);
535 block = xfs_bmbt_get_block(cur, level, &bp);
536 } else {
537 if ((error = xfs_btree_rshift(cur, level, &i))) {
538 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
539 return error;
540 }
541 if (i) {
542 /* nothing */
543 } else {
544 if ((error = xfs_btree_lshift(cur, level, &i))) {
545 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
546 return error;
547 }
548 if (i) {
549 optr = ptr = cur->bc_ptrs[level];
550 } else {
551 union xfs_btree_ptr bno = { .l = cpu_to_be64(nbno) };
552 union xfs_btree_key skey;
553 if ((error = xfs_btree_split(cur, level,
554 &bno, &skey, &ncur,
555 &i))) {
556 XFS_BMBT_TRACE_CURSOR(cur,
557 ERROR);
558 return error;
559 }
560 nbno = be64_to_cpu(bno.l);
561 startoff = be64_to_cpu(skey.bmbt.br_startoff);
562 if (i) {
563 block = xfs_bmbt_get_block(
564 cur, level, &bp);
565#ifdef DEBUG
566 if ((error =
567 xfs_btree_check_lblock(cur,
568 block, level, bp))) {
569 XFS_BMBT_TRACE_CURSOR(
570 cur, ERROR);
571 return error;
572 }
573#endif
574 ptr = cur->bc_ptrs[level];
575 xfs_bmbt_disk_set_allf(&nrec,
576 startoff, 0, 0,
577 XFS_EXT_NORM);
578 } else {
579 XFS_BMBT_TRACE_CURSOR(cur,
580 EXIT);
581 *stat = 0;
582 return 0;
583 }
584 }
585 }
586 }
587 }
588 numrecs = be16_to_cpu(block->bb_numrecs);
589 if (level > 0) {
590 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
591 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
592#ifdef DEBUG
593 for (i = numrecs; i >= ptr; i--) {
594 if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
595 level))) {
596 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
597 return error;
598 }
599 }
600#endif
601 memmove(&kp[ptr], &kp[ptr - 1],
602 (numrecs - ptr + 1) * sizeof(*kp));
603 memmove(&pp[ptr], &pp[ptr - 1],
604 (numrecs - ptr + 1) * sizeof(*pp));
605#ifdef DEBUG
606 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
607 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
608 return error;
609 }
610#endif
611 kp[ptr - 1] = key;
612 pp[ptr - 1] = cpu_to_be64(*bnop);
613 numrecs++;
614 block->bb_numrecs = cpu_to_be16(numrecs);
615 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
616 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
617 } else {
618 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
619 memmove(&rp[ptr], &rp[ptr - 1],
620 (numrecs - ptr + 1) * sizeof(*rp));
621 rp[ptr - 1] = *recp;
622 numrecs++;
623 block->bb_numrecs = cpu_to_be16(numrecs);
624 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
625 }
626 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
627#ifdef DEBUG
628 if (ptr < numrecs) {
629 if (level == 0)
630 xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
631 rp + ptr);
632 else
633 xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
634 kp + ptr);
635 }
636#endif
637 if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1))) {
638 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
639 return error;
640 }
641 *bnop = nbno;
642 if (nbno != NULLFSBLOCK) {
643 *recp = nrec;
644 *curp = ncur;
645 }
646 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
647 *stat = 1;
648 return 0;
649}
650
651STATIC int 459STATIC int
652xfs_bmbt_killroot( 460xfs_bmbt_killroot(
653 xfs_btree_cur_t *cur) 461 xfs_btree_cur_t *cur)
@@ -1060,67 +868,6 @@ xfs_bmbt_disk_get_startoff(
1060} 868}
1061 869
1062/* 870/*
1063 * Insert the current record at the point referenced by cur.
1064 *
1065 * A multi-level split of the tree on insert will invalidate the original
1066 * cursor. All callers of this function should assume that the cursor is
1067 * no longer valid and revalidate it.
1068 */
1069int /* error */
1070xfs_bmbt_insert(
1071 xfs_btree_cur_t *cur,
1072 int *stat) /* success/failure */
1073{
1074 int error; /* error return value */
1075 int i;
1076 int level;
1077 xfs_fsblock_t nbno;
1078 xfs_btree_cur_t *ncur;
1079 xfs_bmbt_rec_t nrec;
1080 xfs_btree_cur_t *pcur;
1081
1082 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1083 level = 0;
1084 nbno = NULLFSBLOCK;
1085 xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
1086 ncur = NULL;
1087 pcur = cur;
1088 do {
1089 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1090 &i))) {
1091 if (pcur != cur)
1092 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1093 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1094 return error;
1095 }
1096 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1097 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
1098 cur->bc_nlevels = pcur->bc_nlevels;
1099 cur->bc_private.b.allocated +=
1100 pcur->bc_private.b.allocated;
1101 pcur->bc_private.b.allocated = 0;
1102 ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
1103 XFS_IS_REALTIME_INODE(cur->bc_private.b.ip));
1104 cur->bc_private.b.firstblock =
1105 pcur->bc_private.b.firstblock;
1106 ASSERT(cur->bc_private.b.flist ==
1107 pcur->bc_private.b.flist);
1108 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1109 }
1110 if (ncur) {
1111 pcur = ncur;
1112 ncur = NULL;
1113 }
1114 } while (nbno != NULLFSBLOCK);
1115 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1116 *stat = i;
1117 return 0;
1118error0:
1119 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1120 return error;
1121}
1122
1123/*
1124 * Log fields from the btree block header. 871 * Log fields from the btree block header.
1125 */ 872 */
1126void 873void
@@ -1450,6 +1197,21 @@ xfs_bmbt_dup_cursor(
1450 return new; 1197 return new;
1451} 1198}
1452 1199
1200STATIC void
1201xfs_bmbt_update_cursor(
1202 struct xfs_btree_cur *src,
1203 struct xfs_btree_cur *dst)
1204{
1205 ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
1206 (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
1207 ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
1208
1209 dst->bc_private.b.allocated += src->bc_private.b.allocated;
1210 dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
1211
1212 src->bc_private.b.allocated = 0;
1213}
1214
1453STATIC int 1215STATIC int
1454xfs_bmbt_alloc_block( 1216xfs_bmbt_alloc_block(
1455 struct xfs_btree_cur *cur, 1217 struct xfs_btree_cur *cur,
@@ -1544,6 +1306,23 @@ xfs_bmbt_get_maxrecs(
1544 return XFS_BMAP_BLOCK_IMAXRECS(level, cur); 1306 return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
1545} 1307}
1546 1308
1309/*
1310 * Get the maximum records we could store in the on-disk format.
1311 *
1312 * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
1313 * for the root node this checks the available space in the dinode fork
1314 * so that we can resize the in-memory buffer to match it. After a
1315 * resize to the maximum size this function returns the same value
1316 * as xfs_bmbt_get_maxrecs for the root node, too.
1317 */
1318STATIC int
1319xfs_bmbt_get_dmaxrecs(
1320 struct xfs_btree_cur *cur,
1321 int level)
1322{
1323 return XFS_BMAP_BLOCK_DMAXRECS(level, cur);
1324}
1325
1547STATIC void 1326STATIC void
1548xfs_bmbt_init_key_from_rec( 1327xfs_bmbt_init_key_from_rec(
1549 union xfs_btree_key *key, 1328 union xfs_btree_key *key,
@@ -1554,6 +1333,25 @@ xfs_bmbt_init_key_from_rec(
1554} 1333}
1555 1334
1556STATIC void 1335STATIC void
1336xfs_bmbt_init_rec_from_key(
1337 union xfs_btree_key *key,
1338 union xfs_btree_rec *rec)
1339{
1340 ASSERT(key->bmbt.br_startoff != 0);
1341
1342 xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
1343 0, 0, XFS_EXT_NORM);
1344}
1345
1346STATIC void
1347xfs_bmbt_init_rec_from_cur(
1348 struct xfs_btree_cur *cur,
1349 union xfs_btree_rec *rec)
1350{
1351 xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
1352}
1353
1354STATIC void
1557xfs_bmbt_init_ptr_from_cur( 1355xfs_bmbt_init_ptr_from_cur(
1558 struct xfs_btree_cur *cur, 1356 struct xfs_btree_cur *cur,
1559 union xfs_btree_ptr *ptr) 1357 union xfs_btree_ptr *ptr)
@@ -1660,9 +1458,13 @@ static const struct xfs_btree_ops xfs_bmbt_ops = {
1660 .key_len = sizeof(xfs_bmbt_key_t), 1458 .key_len = sizeof(xfs_bmbt_key_t),
1661 1459
1662 .dup_cursor = xfs_bmbt_dup_cursor, 1460 .dup_cursor = xfs_bmbt_dup_cursor,
1461 .update_cursor = xfs_bmbt_update_cursor,
1663 .alloc_block = xfs_bmbt_alloc_block, 1462 .alloc_block = xfs_bmbt_alloc_block,
1664 .get_maxrecs = xfs_bmbt_get_maxrecs, 1463 .get_maxrecs = xfs_bmbt_get_maxrecs,
1464 .get_dmaxrecs = xfs_bmbt_get_dmaxrecs,
1665 .init_key_from_rec = xfs_bmbt_init_key_from_rec, 1465 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
1466 .init_rec_from_key = xfs_bmbt_init_rec_from_key,
1467 .init_rec_from_cur = xfs_bmbt_init_rec_from_cur,
1666 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur, 1468 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur,
1667 .key_diff = xfs_bmbt_key_diff, 1469 .key_diff = xfs_bmbt_key_diff,
1668 1470
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-30 07:27:26 -0500