aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/xfs/xfs_alloc_btree.c')
-rw-r--r--fs/xfs/xfs_alloc_btree.c339
1 files changed, 30 insertions, 309 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index f21a3e9cc3db..818adca77fc6 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -583,256 +583,6 @@ error0:
583} 583}
584 584
585/* 585/*
586 * Insert one record/level. Return information to the caller
587 * allowing the next level up to proceed if necessary.
588 */
589STATIC int /* error */
590xfs_alloc_insrec(
591 xfs_btree_cur_t *cur, /* btree cursor */
592 int level, /* level to insert record at */
593 xfs_agblock_t *bnop, /* i/o: block number inserted */
594 xfs_alloc_rec_t *recp, /* i/o: record data inserted */
595 xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
596 int *stat) /* output: success/failure */
597{
598 xfs_agf_t *agf; /* allocation group freelist header */
599 xfs_alloc_block_t *block; /* btree block record/key lives in */
600 xfs_buf_t *bp; /* buffer for block */
601 int error; /* error return value */
602 int i; /* loop index */
603 xfs_alloc_key_t key; /* key value being inserted */
604 xfs_alloc_key_t *kp; /* pointer to btree keys */
605 xfs_agblock_t nbno; /* block number of allocated block */
606 xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
607 xfs_alloc_key_t nkey; /* new key value, from split */
608 xfs_alloc_rec_t nrec; /* new record value, for caller */
609 int numrecs;
610 int optr; /* old ptr value */
611 xfs_alloc_ptr_t *pp; /* pointer to btree addresses */
612 int ptr; /* index in btree block for this rec */
613 xfs_alloc_rec_t *rp; /* pointer to btree records */
614
615 ASSERT(be32_to_cpu(recp->ar_blockcount) > 0);
616
617 /*
618 * GCC doesn't understand the (arguably complex) control flow in
619 * this function and complains about uninitialized structure fields
620 * without this.
621 */
622 memset(&nrec, 0, sizeof(nrec));
623
624 /*
625 * If we made it to the root level, allocate a new root block
626 * and we're done.
627 */
628 if (level >= cur->bc_nlevels) {
629 XFS_STATS_INC(xs_abt_insrec);
630 if ((error = xfs_btree_new_root(cur, &i)))
631 return error;
632 *bnop = NULLAGBLOCK;
633 *stat = i;
634 return 0;
635 }
636 /*
637 * Make a key out of the record data to be inserted, and save it.
638 */
639 key.ar_startblock = recp->ar_startblock;
640 key.ar_blockcount = recp->ar_blockcount;
641 optr = ptr = cur->bc_ptrs[level];
642 /*
643 * If we're off the left edge, return failure.
644 */
645 if (ptr == 0) {
646 *stat = 0;
647 return 0;
648 }
649 XFS_STATS_INC(xs_abt_insrec);
650 /*
651 * Get pointers to the btree buffer and block.
652 */
653 bp = cur->bc_bufs[level];
654 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
655 numrecs = be16_to_cpu(block->bb_numrecs);
656#ifdef DEBUG
657 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
658 return error;
659 /*
660 * Check that the new entry is being inserted in the right place.
661 */
662 if (ptr <= numrecs) {
663 if (level == 0) {
664 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
665 xfs_btree_check_rec(cur->bc_btnum, recp, rp);
666 } else {
667 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
668 xfs_btree_check_key(cur->bc_btnum, &key, kp);
669 }
670 }
671#endif
672 nbno = NULLAGBLOCK;
673 ncur = NULL;
674 /*
675 * If the block is full, we can't insert the new entry until we
676 * make the block un-full.
677 */
678 if (numrecs == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
679 /*
680 * First, try shifting an entry to the right neighbor.
681 */
682 if ((error = xfs_btree_rshift(cur, level, &i)))
683 return error;
684 if (i) {
685 /* nothing */
686 }
687 /*
688 * Next, try shifting an entry to the left neighbor.
689 */
690 else {
691 if ((error = xfs_btree_lshift(cur, level, &i)))
692 return error;
693 if (i)
694 optr = ptr = cur->bc_ptrs[level];
695 else {
696 union xfs_btree_ptr bno = { .s = cpu_to_be32(nbno) };
697 /*
698 * Next, try splitting the current block in
699 * half. If this works we have to re-set our
700 * variables because we could be in a
701 * different block now.
702 */
703 if ((error = xfs_btree_split(cur, level, &bno,
704 (union xfs_btree_key *)&nkey,
705 &ncur, &i)))
706 return error;
707 nbno = be32_to_cpu(bno.s);
708 if (i) {
709 bp = cur->bc_bufs[level];
710 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
711#ifdef DEBUG
712 if ((error =
713 xfs_btree_check_sblock(cur,
714 block, level, bp)))
715 return error;
716#endif
717 ptr = cur->bc_ptrs[level];
718 nrec.ar_startblock = nkey.ar_startblock;
719 nrec.ar_blockcount = nkey.ar_blockcount;
720 }
721 /*
722 * Otherwise the insert fails.
723 */
724 else {
725 *stat = 0;
726 return 0;
727 }
728 }
729 }
730 }
731 /*
732 * At this point we know there's room for our new entry in the block
733 * we're pointing at.
734 */
735 numrecs = be16_to_cpu(block->bb_numrecs);
736 if (level > 0) {
737 /*
738 * It's a non-leaf entry. Make a hole for the new data
739 * in the key and ptr regions of the block.
740 */
741 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
742 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
743#ifdef DEBUG
744 for (i = numrecs; i >= ptr; i--) {
745 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
746 return error;
747 }
748#endif
749 memmove(&kp[ptr], &kp[ptr - 1],
750 (numrecs - ptr + 1) * sizeof(*kp));
751 memmove(&pp[ptr], &pp[ptr - 1],
752 (numrecs - ptr + 1) * sizeof(*pp));
753#ifdef DEBUG
754 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
755 return error;
756#endif
757 /*
758 * Now stuff the new data in, bump numrecs and log the new data.
759 */
760 kp[ptr - 1] = key;
761 pp[ptr - 1] = cpu_to_be32(*bnop);
762 numrecs++;
763 block->bb_numrecs = cpu_to_be16(numrecs);
764 xfs_alloc_log_keys(cur, bp, ptr, numrecs);
765 xfs_alloc_log_ptrs(cur, bp, ptr, numrecs);
766#ifdef DEBUG
767 if (ptr < numrecs)
768 xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
769 kp + ptr);
770#endif
771 } else {
772 /*
773 * It's a leaf entry. Make a hole for the new record.
774 */
775 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
776 memmove(&rp[ptr], &rp[ptr - 1],
777 (numrecs - ptr + 1) * sizeof(*rp));
778 /*
779 * Now stuff the new record in, bump numrecs
780 * and log the new data.
781 */
782 rp[ptr - 1] = *recp;
783 numrecs++;
784 block->bb_numrecs = cpu_to_be16(numrecs);
785 xfs_alloc_log_recs(cur, bp, ptr, numrecs);
786#ifdef DEBUG
787 if (ptr < numrecs)
788 xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
789 rp + ptr);
790#endif
791 }
792 /*
793 * Log the new number of records in the btree header.
794 */
795 xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
796 /*
797 * If we inserted at the start of a block, update the parents' keys.
798 */
799 if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1)))
800 return error;
801 /*
802 * Look to see if the longest extent in the allocation group
803 * needs to be updated.
804 */
805
806 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
807 if (level == 0 &&
808 cur->bc_btnum == XFS_BTNUM_CNT &&
809 be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
810 be32_to_cpu(recp->ar_blockcount) > be32_to_cpu(agf->agf_longest)) {
811 /*
812 * If this is a leaf in the by-size btree and there
813 * is no right sibling block and this block is bigger
814 * than the previous longest block, update it.
815 */
816 agf->agf_longest = recp->ar_blockcount;
817 cur->bc_mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest
818 = be32_to_cpu(recp->ar_blockcount);
819 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
820 XFS_AGF_LONGEST);
821 }
822 /*
823 * Return the new block number, if any.
824 * If there is one, give back a record value and a cursor too.
825 */
826 *bnop = nbno;
827 if (nbno != NULLAGBLOCK) {
828 *recp = nrec;
829 *curp = ncur;
830 }
831 *stat = 1;
832 return 0;
833}
834
835/*
836 * Log header fields from a btree block. 586 * Log header fields from a btree block.
837 */ 587 */
838STATIC void 588STATIC void
@@ -1019,65 +769,6 @@ xfs_alloc_get_rec(
1019 return 0; 769 return 0;
1020} 770}
1021 771
1022/*
1023 * Insert the current record at the point referenced by cur.
1024 * The cursor may be inconsistent on return if splits have been done.
1025 */
1026int /* error */
1027xfs_alloc_insert(
1028 xfs_btree_cur_t *cur, /* btree cursor */
1029 int *stat) /* success/failure */
1030{
1031 int error; /* error return value */
1032 int i; /* result value, 0 for failure */
1033 int level; /* current level number in btree */
1034 xfs_agblock_t nbno; /* new block number (split result) */
1035 xfs_btree_cur_t *ncur; /* new cursor (split result) */
1036 xfs_alloc_rec_t nrec; /* record being inserted this level */
1037 xfs_btree_cur_t *pcur; /* previous level's cursor */
1038
1039 level = 0;
1040 nbno = NULLAGBLOCK;
1041 nrec.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
1042 nrec.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
1043 ncur = NULL;
1044 pcur = cur;
1045 /*
1046 * Loop going up the tree, starting at the leaf level.
1047 * Stop when we don't get a split block, that must mean that
1048 * the insert is finished with this level.
1049 */
1050 do {
1051 /*
1052 * Insert nrec/nbno into this level of the tree.
1053 * Note if we fail, nbno will be null.
1054 */
1055 if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
1056 &i))) {
1057 if (pcur != cur)
1058 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1059 return error;
1060 }
1061 /*
1062 * See if the cursor we just used is trash.
1063 * Can't trash the caller's cursor, but otherwise we should
1064 * if ncur is a new cursor or we're about to be done.
1065 */
1066 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
1067 cur->bc_nlevels = pcur->bc_nlevels;
1068 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1069 }
1070 /*
1071 * If we got a new cursor, switch to it.
1072 */
1073 if (ncur) {
1074 pcur = ncur;
1075 ncur = NULL;
1076 }
1077 } while (nbno != NULLAGBLOCK);
1078 *stat = i;
1079 return 0;
1080}
1081 772
1082STATIC struct xfs_btree_cur * 773STATIC struct xfs_btree_cur *
1083xfs_allocbt_dup_cursor( 774xfs_allocbt_dup_cursor(
@@ -1170,6 +861,12 @@ xfs_allocbt_update_lastrec(
1170 return; 861 return;
1171 len = rec->alloc.ar_blockcount; 862 len = rec->alloc.ar_blockcount;
1172 break; 863 break;
864 case LASTREC_INSREC:
865 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
866 be32_to_cpu(agf->agf_longest))
867 return;
868 len = rec->alloc.ar_blockcount;
869 break;
1173 default: 870 default:
1174 ASSERT(0); 871 ASSERT(0);
1175 return; 872 return;
@@ -1200,6 +897,28 @@ xfs_allocbt_init_key_from_rec(
1200} 897}
1201 898
1202STATIC void 899STATIC void
900xfs_allocbt_init_rec_from_key(
901 union xfs_btree_key *key,
902 union xfs_btree_rec *rec)
903{
904 ASSERT(key->alloc.ar_startblock != 0);
905
906 rec->alloc.ar_startblock = key->alloc.ar_startblock;
907 rec->alloc.ar_blockcount = key->alloc.ar_blockcount;
908}
909
910STATIC void
911xfs_allocbt_init_rec_from_cur(
912 struct xfs_btree_cur *cur,
913 union xfs_btree_rec *rec)
914{
915 ASSERT(cur->bc_rec.a.ar_startblock != 0);
916
917 rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
918 rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
919}
920
921STATIC void
1203xfs_allocbt_init_ptr_from_cur( 922xfs_allocbt_init_ptr_from_cur(
1204 struct xfs_btree_cur *cur, 923 struct xfs_btree_cur *cur,
1205 union xfs_btree_ptr *ptr) 924 union xfs_btree_ptr *ptr)
@@ -1309,6 +1028,8 @@ static const struct xfs_btree_ops xfs_allocbt_ops = {
1309 .update_lastrec = xfs_allocbt_update_lastrec, 1028 .update_lastrec = xfs_allocbt_update_lastrec,
1310 .get_maxrecs = xfs_allocbt_get_maxrecs, 1029 .get_maxrecs = xfs_allocbt_get_maxrecs,
1311 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 1030 .init_key_from_rec = xfs_allocbt_init_key_from_rec,
1031 .init_rec_from_key = xfs_allocbt_init_rec_from_key,
1032 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur,
1312 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 1033 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur,
1313 .key_diff = xfs_allocbt_key_diff, 1034 .key_diff = xfs_allocbt_key_diff,
1314 1035
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-29 22:28:59 -0500