aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_ialloc.c
diff options
context:
space:
mode:
authorDave Chinner <dgc@sgi.com>2009-08-31 19:58:28 -0400
committerFelix Blyakher <felixb@sgi.com>2009-09-01 13:45:48 -0400
commitbd169565993b39b9b4b102cdac8b13e0a259ce2f (patch)
tree4cc6dc56cf7a2b9af71156299e091062dbe30594 /fs/xfs/xfs_ialloc.c
parent2187550525d7bcb8c87689e4eca41b1955bf9ac3 (diff)
xfs: speed up free inode search
Don't search too far - abort if it is outside a certain radius and simply do a linear search for the first free inode. In AGs with a million inodes this can speed up allocation speed by 3-4x. [hch: ported to the new xfs_ialloc.c world order] Signed-off-by: Dave Chinner <dgc@sgi.com> Signed-off-by: Christoph Hellwig <hch@lst.de> Reviewed-by: Alex Elder <aelder@sgi.com> Signed-off-by: Felix Blyakher <felixb@sgi.com>
Diffstat (limited to 'fs/xfs/xfs_ialloc.c')
-rw-r--r--fs/xfs/xfs_ialloc.c133
1 files changed, 106 insertions, 27 deletions
diff --git a/fs/xfs/xfs_ialloc.c b/fs/xfs/xfs_ialloc.c
index 748637cd70ff..d12d805f20a5 100644
--- a/fs/xfs/xfs_ialloc.c
+++ b/fs/xfs/xfs_ialloc.c
@@ -587,6 +587,30 @@ xfs_ialloc_next_rec(
587 return 0; 587 return 0;
588} 588}
589 589
590STATIC int
591xfs_ialloc_get_rec(
592 struct xfs_btree_cur *cur,
593 xfs_agino_t agino,
594 xfs_inobt_rec_incore_t *rec,
595 int *done,
596 int left)
597{
598 int error;
599 int i;
600
601 error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_EQ, &i);
602 if (error)
603 return error;
604 *done = !i;
605 if (i) {
606 error = xfs_inobt_get_rec(cur, rec, &i);
607 if (error)
608 return error;
609 XFS_WANT_CORRUPTED_RETURN(i == 1);
610 }
611
612 return 0;
613}
590 614
591/* 615/*
592 * Visible inode allocation functions. 616 * Visible inode allocation functions.
@@ -766,6 +790,8 @@ nextag:
766 */ 790 */
767 agno = tagno; 791 agno = tagno;
768 *IO_agbp = NULL; 792 *IO_agbp = NULL;
793
794 restart_pagno:
769 cur = xfs_inobt_init_cursor(mp, tp, agbp, be32_to_cpu(agi->agi_seqno)); 795 cur = xfs_inobt_init_cursor(mp, tp, agbp, be32_to_cpu(agi->agi_seqno));
770 /* 796 /*
771 * If pagino is 0 (this is the root inode allocation) use newino. 797 * If pagino is 0 (this is the root inode allocation) use newino.
@@ -782,8 +808,10 @@ nextag:
782 * If in the same AG as the parent, try to get near the parent. 808 * If in the same AG as the parent, try to get near the parent.
783 */ 809 */
784 if (pagno == agno) { 810 if (pagno == agno) {
811 xfs_perag_t *pag = &mp->m_perag[agno];
785 int doneleft; /* done, to the left */ 812 int doneleft; /* done, to the left */
786 int doneright; /* done, to the right */ 813 int doneright; /* done, to the right */
814 int searchdistance = 10;
787 815
788 error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i); 816 error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
789 if (error) 817 if (error)
@@ -813,15 +841,33 @@ nextag:
813 if (error) 841 if (error)
814 goto error0; 842 goto error0;
815 843
816 /* search left with tcur, back up 1 record */ 844 /*
817 error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1); 845 * Skip to last blocks looked up if same parent inode.
818 if (error) 846 */
819 goto error1; 847 if (pagino != NULLAGINO &&
848 pag->pagl_pagino == pagino &&
849 pag->pagl_leftrec != NULLAGINO &&
850 pag->pagl_rightrec != NULLAGINO) {
851 error = xfs_ialloc_get_rec(tcur, pag->pagl_leftrec,
852 &trec, &doneleft, 1);
853 if (error)
854 goto error1;
820 855
821 /* search right with cur, go forward 1 record. */ 856 error = xfs_ialloc_get_rec(cur, pag->pagl_rightrec,
822 error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0); 857 &rec, &doneright, 0);
823 if (error) 858 if (error)
824 goto error1; 859 goto error1;
860 } else {
861 /* search left with tcur, back up 1 record */
862 error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1);
863 if (error)
864 goto error1;
865
866 /* search right with cur, go forward 1 record. */
867 error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0);
868 if (error)
869 goto error1;
870 }
825 871
826 /* 872 /*
827 * Loop until we find an inode chunk with a free inode. 873 * Loop until we find an inode chunk with a free inode.
@@ -829,6 +875,17 @@ nextag:
829 while (!doneleft || !doneright) { 875 while (!doneleft || !doneright) {
830 int useleft; /* using left inode chunk this time */ 876 int useleft; /* using left inode chunk this time */
831 877
878 if (!--searchdistance) {
879 /*
880 * Not in range - save last search
881 * location and allocate a new inode
882 */
883 pag->pagl_leftrec = trec.ir_startino;
884 pag->pagl_rightrec = rec.ir_startino;
885 pag->pagl_pagino = pagino;
886 goto newino;
887 }
888
832 /* figure out the closer block if both are valid. */ 889 /* figure out the closer block if both are valid. */
833 if (!doneleft && !doneright) { 890 if (!doneleft && !doneright) {
834 useleft = pagino - 891 useleft = pagino -
@@ -843,12 +900,20 @@ nextag:
843 rec = trec; 900 rec = trec;
844 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 901 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
845 cur = tcur; 902 cur = tcur;
903
904 pag->pagl_leftrec = trec.ir_startino;
905 pag->pagl_rightrec = rec.ir_startino;
906 pag->pagl_pagino = pagino;
846 goto alloc_inode; 907 goto alloc_inode;
847 } 908 }
848 909
849 /* free inodes to the right? */ 910 /* free inodes to the right? */
850 if (!useleft && rec.ir_freecount) { 911 if (!useleft && rec.ir_freecount) {
851 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 912 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
913
914 pag->pagl_leftrec = trec.ir_startino;
915 pag->pagl_rightrec = rec.ir_startino;
916 pag->pagl_pagino = pagino;
852 goto alloc_inode; 917 goto alloc_inode;
853 } 918 }
854 919
@@ -863,14 +928,28 @@ nextag:
863 if (error) 928 if (error)
864 goto error1; 929 goto error1;
865 } 930 }
866 ASSERT(!doneleft || !doneright); 931
932 /*
933 * We've reached the end of the btree. because
934 * we are only searching a small chunk of the
935 * btree each search, there is obviously free
936 * inodes closer to the parent inode than we
937 * are now. restart the search again.
938 */
939 pag->pagl_pagino = NULLAGINO;
940 pag->pagl_leftrec = NULLAGINO;
941 pag->pagl_rightrec = NULLAGINO;
942 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
943 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
944 goto restart_pagno;
867 } 945 }
868 946
869 /* 947 /*
870 * In a different AG from the parent. 948 * In a different AG from the parent.
871 * See if the most recently allocated block has any free. 949 * See if the most recently allocated block has any free.
872 */ 950 */
873 else if (be32_to_cpu(agi->agi_newino) != NULLAGINO) { 951newino:
952 if (be32_to_cpu(agi->agi_newino) != NULLAGINO) {
874 error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino), 953 error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
875 XFS_LOOKUP_EQ, &i); 954 XFS_LOOKUP_EQ, &i);
876 if (error) 955 if (error)
@@ -889,27 +968,27 @@ nextag:
889 goto alloc_inode; 968 goto alloc_inode;
890 } 969 }
891 } 970 }
971 }
892 972
893 /* 973 /*
894 * None left in the last group, search the whole AG 974 * None left in the last group, search the whole AG
895 */ 975 */
896 error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i); 976 error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
977 if (error)
978 goto error0;
979 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
980
981 for (;;) {
982 error = xfs_inobt_get_rec(cur, &rec, &i);
983 if (error)
984 goto error0;
985 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
986 if (rec.ir_freecount > 0)
987 break;
988 error = xfs_btree_increment(cur, 0, &i);
897 if (error) 989 if (error)
898 goto error0; 990 goto error0;
899 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 991 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
900
901 for (;;) {
902 error = xfs_inobt_get_rec(cur, &rec, &i);
903 if (error)
904 goto error0;
905 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
906 if (rec.ir_freecount > 0)
907 break;
908 error = xfs_btree_increment(cur, 0, &i);
909 if (error)
910 goto error0;
911 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
912 }
913 } 992 }
914 993
915alloc_inode: 994alloc_inode: