aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_ialloc_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_ialloc_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_ialloc_btree.c')
-rw-r--r--fs/xfs/xfs_ialloc_btree.c302
1 files changed, 20 insertions, 282 deletions
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index 7ba3c7bb3984..8f66e2720566 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -515,228 +515,6 @@ error0:
515} 515}
516 516
517/* 517/*
518 * Insert one record/level. Return information to the caller
519 * allowing the next level up to proceed if necessary.
520 */
521STATIC int /* error */
522xfs_inobt_insrec(
523 xfs_btree_cur_t *cur, /* btree cursor */
524 int level, /* level to insert record at */
525 xfs_agblock_t *bnop, /* i/o: block number inserted */
526 xfs_inobt_rec_t *recp, /* i/o: record data inserted */
527 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
528 int *stat) /* success/failure */
529{
530 xfs_inobt_block_t *block; /* btree block record/key lives in */
531 xfs_buf_t *bp; /* buffer for block */
532 int error; /* error return value */
533 int i; /* loop index */
534 xfs_inobt_key_t key; /* key value being inserted */
535 xfs_inobt_key_t *kp=NULL; /* pointer to btree keys */
536 xfs_agblock_t nbno; /* block number of allocated block */
537 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
538 xfs_inobt_key_t nkey; /* new key value, from split */
539 xfs_inobt_rec_t nrec; /* new record value, for caller */
540 int numrecs;
541 int optr; /* old ptr value */
542 xfs_inobt_ptr_t *pp; /* pointer to btree addresses */
543 int ptr; /* index in btree block for this rec */
544 xfs_inobt_rec_t *rp=NULL; /* pointer to btree records */
545
546 /*
547 * GCC doesn't understand the (arguably complex) control flow in
548 * this function and complains about uninitialized structure fields
549 * without this.
550 */
551 memset(&nrec, 0, sizeof(nrec));
552
553 /*
554 * If we made it to the root level, allocate a new root block
555 * and we're done.
556 */
557 if (level >= cur->bc_nlevels) {
558 error = xfs_btree_new_root(cur, &i);
559 *bnop = NULLAGBLOCK;
560 *stat = i;
561 return error;
562 }
563 /*
564 * Make a key out of the record data to be inserted, and save it.
565 */
566 key.ir_startino = recp->ir_startino;
567 optr = ptr = cur->bc_ptrs[level];
568 /*
569 * If we're off the left edge, return failure.
570 */
571 if (ptr == 0) {
572 *stat = 0;
573 return 0;
574 }
575 /*
576 * Get pointers to the btree buffer and block.
577 */
578 bp = cur->bc_bufs[level];
579 block = XFS_BUF_TO_INOBT_BLOCK(bp);
580 numrecs = be16_to_cpu(block->bb_numrecs);
581#ifdef DEBUG
582 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
583 return error;
584 /*
585 * Check that the new entry is being inserted in the right place.
586 */
587 if (ptr <= numrecs) {
588 if (level == 0) {
589 rp = XFS_INOBT_REC_ADDR(block, ptr, cur);
590 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
591 } else {
592 kp = XFS_INOBT_KEY_ADDR(block, ptr, cur);
593 xfs_btree_check_key(cur->bc_btnum, &key, kp);
594 }
595 }
596#endif
597 nbno = NULLAGBLOCK;
598 ncur = NULL;
599 /*
600 * If the block is full, we can't insert the new entry until we
601 * make the block un-full.
602 */
603 if (numrecs == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
604 /*
605 * First, try shifting an entry to the right neighbor.
606 */
607 if ((error = xfs_btree_rshift(cur, level, &i)))
608 return error;
609 if (i) {
610 /* nothing */
611 }
612 /*
613 * Next, try shifting an entry to the left neighbor.
614 */
615 else {
616 if ((error = xfs_btree_lshift(cur, level, &i)))
617 return error;
618 if (i) {
619 optr = ptr = cur->bc_ptrs[level];
620 } else {
621 union xfs_btree_ptr bno = { .s = cpu_to_be32(nbno) };
622 /*
623 * Next, try splitting the current block
624 * in half. If this works we have to
625 * re-set our variables because
626 * we could be in a different block now.
627 */
628 if ((error = xfs_btree_split(cur, level, &bno,
629 (union xfs_btree_key *)&nkey,
630 &ncur, &i)))
631 return error;
632 nbno = be32_to_cpu(bno.s);
633 if (i) {
634 bp = cur->bc_bufs[level];
635 block = XFS_BUF_TO_INOBT_BLOCK(bp);
636#ifdef DEBUG
637 if ((error = xfs_btree_check_sblock(cur,
638 block, level, bp)))
639 return error;
640#endif
641 ptr = cur->bc_ptrs[level];
642 nrec.ir_startino = nkey.ir_startino;
643 } else {
644 /*
645 * Otherwise the insert fails.
646 */
647 *stat = 0;
648 return 0;
649 }
650 }
651 }
652 }
653 /*
654 * At this point we know there's room for our new entry in the block
655 * we're pointing at.
656 */
657 numrecs = be16_to_cpu(block->bb_numrecs);
658 if (level > 0) {
659 /*
660 * It's a non-leaf entry. Make a hole for the new data
661 * in the key and ptr regions of the block.
662 */
663 kp = XFS_INOBT_KEY_ADDR(block, 1, cur);
664 pp = XFS_INOBT_PTR_ADDR(block, 1, cur);
665#ifdef DEBUG
666 for (i = numrecs; i >= ptr; i--) {
667 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
668 return error;
669 }
670#endif
671 memmove(&kp[ptr], &kp[ptr - 1],
672 (numrecs - ptr + 1) * sizeof(*kp));
673 memmove(&pp[ptr], &pp[ptr - 1],
674 (numrecs - ptr + 1) * sizeof(*pp));
675 /*
676 * Now stuff the new data in, bump numrecs and log the new data.
677 */
678#ifdef DEBUG
679 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
680 return error;
681#endif
682 kp[ptr - 1] = key;
683 pp[ptr - 1] = cpu_to_be32(*bnop);
684 numrecs++;
685 block->bb_numrecs = cpu_to_be16(numrecs);
686 xfs_inobt_log_keys(cur, bp, ptr, numrecs);
687 xfs_inobt_log_ptrs(cur, bp, ptr, numrecs);
688 } else {
689 /*
690 * It's a leaf entry. Make a hole for the new record.
691 */
692 rp = XFS_INOBT_REC_ADDR(block, 1, cur);
693 memmove(&rp[ptr], &rp[ptr - 1],
694 (numrecs - ptr + 1) * sizeof(*rp));
695 /*
696 * Now stuff the new record in, bump numrecs
697 * and log the new data.
698 */
699 rp[ptr - 1] = *recp;
700 numrecs++;
701 block->bb_numrecs = cpu_to_be16(numrecs);
702 xfs_inobt_log_recs(cur, bp, ptr, numrecs);
703 }
704 /*
705 * Log the new number of records in the btree header.
706 */
707 xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
708#ifdef DEBUG
709 /*
710 * Check that the key/record is in the right place, now.
711 */
712 if (ptr < numrecs) {
713 if (level == 0)
714 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
715 rp + ptr);
716 else
717 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
718 kp + ptr);
719 }
720#endif
721 /*
722 * If we inserted at the start of a block, update the parents' keys.
723 */
724 if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1)))
725 return error;
726 /*
727 * Return the new block number, if any.
728 * If there is one, give back a record value and a cursor too.
729 */
730 *bnop = nbno;
731 if (nbno != NULLAGBLOCK) {
732 *recp = nrec;
733 *curp = ncur;
734 }
735 *stat = 1;
736 return 0;
737}
738
739/*
740 * Log header fields from a btree block. 518 * Log header fields from a btree block.
741 */ 519 */
742STATIC void 520STATIC void
@@ -912,66 +690,6 @@ xfs_inobt_get_rec(
912 return 0; 690 return 0;
913} 691}
914 692
915/*
916 * Insert the current record at the point referenced by cur.
917 * The cursor may be inconsistent on return if splits have been done.
918 */
919int /* error */
920xfs_inobt_insert(
921 xfs_btree_cur_t *cur, /* btree cursor */
922 int *stat) /* success/failure */
923{
924 int error; /* error return value */
925 int i; /* result value, 0 for failure */
926 int level; /* current level number in btree */
927 xfs_agblock_t nbno; /* new block number (split result) */
928 xfs_btree_cur_t *ncur; /* new cursor (split result) */
929 xfs_inobt_rec_t nrec; /* record being inserted this level */
930 xfs_btree_cur_t *pcur; /* previous level's cursor */
931
932 level = 0;
933 nbno = NULLAGBLOCK;
934 nrec.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
935 nrec.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
936 nrec.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
937 ncur = NULL;
938 pcur = cur;
939 /*
940 * Loop going up the tree, starting at the leaf level.
941 * Stop when we don't get a split block, that must mean that
942 * the insert is finished with this level.
943 */
944 do {
945 /*
946 * Insert nrec/nbno into this level of the tree.
947 * Note if we fail, nbno will be null.
948 */
949 if ((error = xfs_inobt_insrec(pcur, level++, &nbno, &nrec, &ncur,
950 &i))) {
951 if (pcur != cur)
952 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
953 return error;
954 }
955 /*
956 * See if the cursor we just used is trash.
957 * Can't trash the caller's cursor, but otherwise we should
958 * if ncur is a new cursor or we're about to be done.
959 */
960 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
961 cur->bc_nlevels = pcur->bc_nlevels;
962 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
963 }
964 /*
965 * If we got a new cursor, switch to it.
966 */
967 if (ncur) {
968 pcur = ncur;
969 ncur = NULL;
970 }
971 } while (nbno != NULLAGBLOCK);
972 *stat = i;
973 return 0;
974}
975 693
976STATIC struct xfs_btree_cur * 694STATIC struct xfs_btree_cur *
977xfs_inobt_dup_cursor( 695xfs_inobt_dup_cursor(
@@ -1053,6 +771,24 @@ xfs_inobt_init_key_from_rec(
1053 key->inobt.ir_startino = rec->inobt.ir_startino; 771 key->inobt.ir_startino = rec->inobt.ir_startino;
1054} 772}
1055 773
774STATIC void
775xfs_inobt_init_rec_from_key(
776 union xfs_btree_key *key,
777 union xfs_btree_rec *rec)
778{
779 rec->inobt.ir_startino = key->inobt.ir_startino;
780}
781
782STATIC void
783xfs_inobt_init_rec_from_cur(
784 struct xfs_btree_cur *cur,
785 union xfs_btree_rec *rec)
786{
787 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
788 rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
789 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
790}
791
1056/* 792/*
1057 * intial value of ptr for lookup 793 * intial value of ptr for lookup
1058 */ 794 */
@@ -1152,6 +888,8 @@ static const struct xfs_btree_ops xfs_inobt_ops = {
1152 .alloc_block = xfs_inobt_alloc_block, 888 .alloc_block = xfs_inobt_alloc_block,
1153 .get_maxrecs = xfs_inobt_get_maxrecs, 889 .get_maxrecs = xfs_inobt_get_maxrecs,
1154 .init_key_from_rec = xfs_inobt_init_key_from_rec, 890 .init_key_from_rec = xfs_inobt_init_key_from_rec,
891 .init_rec_from_key = xfs_inobt_init_rec_from_key,
892 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
1155 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 893 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
1156 .key_diff = xfs_inobt_key_diff, 894 .key_diff = xfs_inobt_key_diff,
1157 895
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-27 10:33:09 -0500