linux-mm.kvack.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 0/11] Avoiding fragmentation with subzone groupings v26
@ 2006-11-01 11:16 Mel Gorman
  2006-11-01 11:16 ` [PATCH 1/11] Add __GFP_EASYRCLM flag and update callers Mel Gorman
                   ` (11 more replies)
  0 siblings, 12 replies; 14+ messages in thread
From: Mel Gorman @ 2006-11-01 11:16 UTC (permalink / raw)
  To: linux-mm; +Cc: Mel Gorman, linux-kernel

This is the latest version of anti-fragmentation based on sub-zones (previously
called list-based anti-fragmentation) based on top of 2.6.19-rc4-mm1. In
it's last release, it was decided that the scheme should be implemented with
zones to avoid affecting the page allocator hot paths. However, at VM Summit,
it was made clear that zones may not be the right answer either because zones
have their own issues. Hence, this is a reintroduction of the first approach.

Changelog Since V25
o Fix loop order of for_each_rclmtype_order so that order of loop matches args
o gfpflags_to_rclmtype uses gfp_t instead of unsigned long
o Rename get_pageblock_type() to get_page_rclmtype()
o Fix alignment problem in move_freepages()
o Add mechanism for assigning flags to blocks of pages instead of page->flags
o On fallback, do not examine the preferred list of free pages a second time

The purpose of these patches is to reduce external fragmentation by grouping
pages of related types together. The objective is that when page reclaim
occurs, there is a greater chance that large contiguous pages will be
free. Note that this is not a defragmentation which would get contiguous
pages by moving pages around.

This patch works by categorising allocations by their reclaimability;

EasyReclaimable - These are userspace pages that are easily reclaimable. This
	flag is set when it is known that the pages will be trivially reclaimed
	by writing the page out to swap or syncing with backing storage

KernelReclaimable - These are allocations for some kernel caches that are
	reclaimable or allocations that are known to be very short-lived.

KernelNonReclaimable - These are pages that are allocated by the kernel that
	are not trivially reclaimed. For example, the memory allocated for a
	loaded module would be in this category. By default, allocations are
	considered to be of this type

Instead of having one MAX_ORDER-sized array of free lists in struct free_area,
there is one for each type of reclaimability. Once a 2^MAX_ORDER block of
pages is split for a type of allocation, it is added to the free-lists for
that type, in effect reserving it. Hence, over time, pages of the different
types can be clustered together. When a page is allocated, the page-flags
are updated with a value indicating it's type of reclaimability so that it
is placed on the correct list on free.

When the preferred freelists are expired, the largest possible block is taken
from an alternative list. Buddies that are split from that large block are
placed on the preferred allocation-type freelists to mitigate fragmentation.

This implementation gives best-effort for low fragmentation in all zones. To
be effective, min_free_kbytes needs to be set to a value about 10% of physical
memory (10% was found by experimentation, it may be workload dependant). To
get that value lower, anti-fragmentation needs to be more invasive so it's
best to find out what sorts of workloads still cause fragmentation before
taking further steps.

Our tests show that about 60-70% of physical memory can be allocated on
a desktop after a few days uptime. In benchmarks and stress tests, we are
finding that 80% of memory is available as contiguous blocks at the end of
the test. To compare, a standard kernel was getting < 1% of memory as large
pages on a desktop and about 8-12% of memory as large pages at the end of
stress tests.

Performance tests are within 0.1% for kbuild on a number of test machines. aim9
is usually within 1% except on x86_64 where aim9 results are unreliable.
I have never been able to show it but it is possible the main allocator
path is adversely affected by anti-fragmentation (cache footprint might be a
problem) and it may be exposed by using differnet compilers or benchmarks. If
any regressions are detected due to anti-fragmentation, it may be simply
disabled via the kernel configuration and I'd appreciate a report detailing
the regression and how to trigger it.

Following this email are 8 patches that implement antifragmentation with an
additional 3 patches that provide an alternative to using page->flags. The
early patches introduce the split between user and kernel allocations.
Later we introduce a further split for kernel allocations, into KernRclm
and KernNoRclm.  Note that although in early patches an additional page
flag is consumed, later patches reuse the suspend bits, releasing this bit
again. The last three patches remove the restriction on suspend by introducing
an alternative solution for tracking page blocks which remove the need for
any page bits.

Comments?
-- 
-- 
Mel Gorman
Part-time Phd Student                          Linux Technology Center
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

^ permalink raw reply	[flat|nested] 14+ messages in thread
* [PATCH 0/11] Avoiding fragmentation with page clustering v27
@ 2006-11-21 22:50 Mel Gorman
  2006-11-21 22:53 ` [PATCH 8/11] [DEBUG] Add statistics Mel Gorman
  0 siblings, 1 reply; 14+ messages in thread
From: Mel Gorman @ 2006-11-21 22:50 UTC (permalink / raw)
  To: linux-mm; +Cc: Mel Gorman, linux-kernel, clameter

This is another post of the patches aimed at reducing external
fragmentation. Based on feedback from Christoph Lameter, it has been
reworked in two important respects. One, allocations should be grouped by
ability to migrate, not just reclaim. This lays the foundation for using
page migration as a defragmentation solution later.  Second, the per-cpu
structures were larger in earlier versions which is a problem on machines
with large CPUs. They remain the same in this version.

Tests show that the kernel is far better at servicing high-order allocations
with these patches applied. kernbench figures show performance differences
of between -0.1% and +0.5% on three test machines (two ppc64 and one x86_64).

Changelog Since V27

o Renamed anti-fragmentation to Page Clustering. Anti-fragmentation was giving
  the mistaken impression that it was the 100% solution for high order
  allocations. Instead, it greatly increases the chances high-order
  allocations will succeed and lays the foundation for defragmentation and
  memory hot-remove to work properly
o Redefine page groupings based on ability to migrate or reclaim instead of
  basing on reclaimability alone
o Get rid of spurious inits
o Per-cpu lists are no longer split up per-type. Instead the per-cpu list is
  searched for a page of the appropriate type
o Added more explanation commentary
o Fix up bug in pageblock code where bitmap was used before being initalised

Changelog Since V26
o Fix double init of lists in setup_pageset

Changelog Since V25
o Fix loop order of for_each_rclmtype_order so that order of loop matches args
o gfpflags_to_rclmtype uses gfp_t instead of unsigned long
o Rename get_pageblock_type() to get_page_rclmtype()
o Fix alignment problem in move_freepages()
o Add mechanism for assigning flags to blocks of pages instead of page->flags
o On fallback, do not examine the preferred list of free pages a second time

The purpose of these patches is to reduce external fragmentation by grouping
pages of related types together. When pages are migrated (or reclaimed under
memory pressure), large contiguous pages will be freed. 

This patch works by categorising allocations by their ability to migrate;

Movable - The pages may be moved with the page migration mechanism. These are
	generally userspace pages. 

Reclaimable - These are allocations for some kernel caches that are
	reclaimable or allocations that are known to be very short-lived.

Unmovable - These are pages that are allocated by the kernel that
	are not trivially reclaimed. For example, the memory allocated for a
	loaded module would be in this category. By default, allocations are
	considered to be of this type

Instead of having one MAX_ORDER-sized array of free lists in struct free_area,
there is one for each type of reclaimability. Once a 2^MAX_ORDER block of
pages is split for a type of allocation, it is added to the free-lists for
that type, in effect reserving it. Hence, over time, pages of the different
types can be clustered together.

When the preferred freelists are expired, the largest possible block is taken
from an alternative list. Buddies that are split from that large block are
placed on the preferred allocation-type freelists to mitigate fragmentation.

This implementation gives best-effort for low fragmentation in all zones. To
be effective, min_free_kbytes needs to be set to a value about 10% of physical
memory (10% was found by experimentation, it may be workload dependant). To
get that value lower, more invasive is required.

Our tests show that about 60-70% of physical memory can be allocated on
a desktop after a few days uptime. In benchmarks and stress tests, we are
finding that 80% of memory is available as contiguous blocks at the end of
the test. To compare, a standard kernel was getting < 1% of memory as large
pages on a desktop and about 8-12% of memory as large pages at the end of
stress tests.

Following this email are 8 patches that implement page clustering with an
additional 3 patches that provide an alternative to using page->flags. The
early patches introduce the split between movable and all other allocations.
Later we introduce a further split for reclaimable allocations.  Note that
although in early patches an additional page flag is consumed, later patches
reuse the suspend bits, releasing this bit again. The last three patches
remove the restriction on suspend by introducing an alternative solution
for tracking page blocks which remove the need for any page bits.

-- 
Mel Gorman
Part-time Phd Student                          Linux Technology Center
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

^ permalink raw reply	[flat|nested] 14+ messages in thread
end of thread, other threads:[~2006-11-21 22:53 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-11-01 11:16 [PATCH 0/11] Avoiding fragmentation with subzone groupings v26 Mel Gorman
2006-11-01 11:16 ` [PATCH 1/11] Add __GFP_EASYRCLM flag and update callers Mel Gorman
2006-11-01 11:17 ` [PATCH 2/11] Split the free lists into kernel and user parts Mel Gorman
2006-11-01 11:17 ` [PATCH 3/11] Split the per-cpu lists into RCLM_TYPES lists Mel Gorman
2006-11-01 11:17 ` [PATCH 4/11] Add a configure option for anti-fragmentation Mel Gorman
2006-11-01 11:18 ` [PATCH 5/11] Drain per-cpu lists when high-order allocations fail Mel Gorman
2006-11-01 11:18 ` [PATCH 6/11] Move free pages between lists on steal Mel Gorman
2006-11-01 11:18 ` [PATCH 7/11] Introduce the RCLM_KERN allocation type Mel Gorman
2006-11-01 11:19 ` [PATCH 8/11] [DEBUG] Add statistics Mel Gorman
2006-11-01 11:19 ` [PATCH 9/11] Add a bitmap that is used to track flags affecting a block of pages Mel Gorman
2006-11-01 11:19 ` [PATCH 10/11] Remove dependency on page->flag bits Mel Gorman
2006-11-01 11:20 ` [PATCH 11/11] Use pageblock flags for anti-fragmentation Mel Gorman
     [not found] ` <p734ptilcie.fsf@verdi.suse.de>
2006-11-02 11:21   ` [PATCH 0/11] Avoiding fragmentation with subzone groupings v26 Mel Gorman
2006-11-21 22:50 [PATCH 0/11] Avoiding fragmentation with page clustering v27 Mel Gorman
2006-11-21 22:53 ` [PATCH 8/11] [DEBUG] Add statistics Mel Gorman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox