aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc.c
diff options
context:
space:
mode:
authorDave Chinner <david@fromorbit.com>2010-01-11 06:47:44 -0500
committerAlex Elder <aelder@sgi.com>2010-01-15 16:33:52 -0500
commit1c1c6ebcf5284aee4910f3b906ac90c20e510c82 (patch)
treebbcf74752bf7bc058a5c5bdd6bd03090c845b041 /fs/xfs/xfs_alloc.c
parent44b56e0a1aed522a10051645e85d300e10926fd3 (diff)
xfs: Replace per-ag array with a radix tree
The use of an array for the per-ag structures requires reallocation of the array when growing the filesystem. This requires locking access to the array to avoid use after free situations, and the locking is difficult to get right. To avoid needing to reallocate an array, change the per-ag structures to an allocated object per ag and index them using a tree structure. The AGs are always densely indexed (hence the use of an array), but the number supported is 2^32 and lookups tend to be random and hence indexing needs to scale. A simple choice is a radix tree - it works well with this sort of index. This change also removes another large contiguous allocation from the mount/growfs path in XFS. The growing process now needs to change to only initialise the new AGs required for the extra space, and as such only needs to exclusively lock the tree for inserts. The rest of the code only needs to lock the tree while doing lookups, and hence this will remove all the deadlocks that currently occur on the m_perag_lock as it is now an innermost lock. The lock is also changed to a spinlock from a read/write lock as the hold time is now extremely short. To complete the picture, the per-ag structures will need to be reference counted to ensure that we don't free/modify them while they are still in use. This will be done in subsequent patch. Signed-off-by: Dave Chinner <david@fromorbit.com> Reviewed-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Alex Elder <aelder@sgi.com>
Diffstat (limited to 'fs/xfs/xfs_alloc.c')
-rw-r--r--fs/xfs/xfs_alloc.c8
1 files changed, 0 insertions, 8 deletions
diff --git a/fs/xfs/xfs_alloc.c b/fs/xfs/xfs_alloc.c
index 84070f2e0ba4..4d66bb75579c 100644
--- a/fs/xfs/xfs_alloc.c
+++ b/fs/xfs/xfs_alloc.c
@@ -2276,7 +2276,6 @@ xfs_alloc_vextent(
2276 * These three force us into a single a.g. 2276 * These three force us into a single a.g.
2277 */ 2277 */
2278 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno); 2278 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2279 down_read(&mp->m_peraglock);
2280 args->pag = xfs_perag_get(mp, args->agno); 2279 args->pag = xfs_perag_get(mp, args->agno);
2281 args->minleft = 0; 2280 args->minleft = 0;
2282 error = xfs_alloc_fix_freelist(args, 0); 2281 error = xfs_alloc_fix_freelist(args, 0);
@@ -2286,14 +2285,12 @@ xfs_alloc_vextent(
2286 goto error0; 2285 goto error0;
2287 } 2286 }
2288 if (!args->agbp) { 2287 if (!args->agbp) {
2289 up_read(&mp->m_peraglock);
2290 trace_xfs_alloc_vextent_noagbp(args); 2288 trace_xfs_alloc_vextent_noagbp(args);
2291 break; 2289 break;
2292 } 2290 }
2293 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno); 2291 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2294 if ((error = xfs_alloc_ag_vextent(args))) 2292 if ((error = xfs_alloc_ag_vextent(args)))
2295 goto error0; 2293 goto error0;
2296 up_read(&mp->m_peraglock);
2297 break; 2294 break;
2298 case XFS_ALLOCTYPE_START_BNO: 2295 case XFS_ALLOCTYPE_START_BNO:
2299 /* 2296 /*
@@ -2345,7 +2342,6 @@ xfs_alloc_vextent(
2345 * Loop over allocation groups twice; first time with 2342 * Loop over allocation groups twice; first time with
2346 * trylock set, second time without. 2343 * trylock set, second time without.
2347 */ 2344 */
2348 down_read(&mp->m_peraglock);
2349 for (;;) { 2345 for (;;) {
2350 args->pag = xfs_perag_get(mp, args->agno); 2346 args->pag = xfs_perag_get(mp, args->agno);
2351 if (no_min) args->minleft = 0; 2347 if (no_min) args->minleft = 0;
@@ -2408,7 +2404,6 @@ xfs_alloc_vextent(
2408 } 2404 }
2409 xfs_perag_put(args->pag); 2405 xfs_perag_put(args->pag);
2410 } 2406 }
2411 up_read(&mp->m_peraglock);
2412 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) { 2407 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2413 if (args->agno == sagno) 2408 if (args->agno == sagno)
2414 mp->m_agfrotor = (mp->m_agfrotor + 1) % 2409 mp->m_agfrotor = (mp->m_agfrotor + 1) %
@@ -2438,7 +2433,6 @@ xfs_alloc_vextent(
2438 return 0; 2433 return 0;
2439error0: 2434error0:
2440 xfs_perag_put(args->pag); 2435 xfs_perag_put(args->pag);
2441 up_read(&mp->m_peraglock);
2442 return error; 2436 return error;
2443} 2437}
2444 2438
@@ -2463,7 +2457,6 @@ xfs_free_extent(
2463 args.agno = XFS_FSB_TO_AGNO(args.mp, bno); 2457 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2464 ASSERT(args.agno < args.mp->m_sb.sb_agcount); 2458 ASSERT(args.agno < args.mp->m_sb.sb_agcount);
2465 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno); 2459 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2466 down_read(&args.mp->m_peraglock);
2467 args.pag = xfs_perag_get(args.mp, args.agno); 2460 args.pag = xfs_perag_get(args.mp, args.agno);
2468 if ((error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING))) 2461 if ((error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING)))
2469 goto error0; 2462 goto error0;
@@ -2475,7 +2468,6 @@ xfs_free_extent(
2475 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0); 2468 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
2476error0: 2469error0:
2477 xfs_perag_put(args.pag); 2470 xfs_perag_put(args.pag);
2478 up_read(&args.mp->m_peraglock);
2479 return error; 2471 return error;
2480} 2472}
2481 2473