Re: [Lhms-devel] [PATCH 0/7] Fragmentation Avoidance V19 - Summary

[Mel Gorman]

On Wed, 2 Nov 2005, Nick Piggin wrote:

> Dave Hansen wrote:
>
> > What the fragmentation patches _can_ give us is the ability to have 100%
> > success in removing certain areas: the "user-reclaimable" areas
> > referenced in the patch.  This gives a customer at least the ability to
> > plan for how dynamically reconfigurable a system should be.
> >
>
> But the "user-reclaimable" areas can still be taken over by other
> areas which become fragmented.
>

This is true, we have worst case scenarios. With our patches though, our
assertion it takes a lot longer to degrade and in good scenarios like
where the workload is not using all of physical memory, we don't degrade
at all.  Assuming we get a page migration or active defragmentation in the
future, it will be a lot longer before they have to do any work. As we
only fragment when there is nothing else to do, page migration will also
have less work to do.

> That's like saying we can already guarantee 100% success in removing
> areas that are unfragmented and free, or freeable.
>
> > After these patches, the next logical steps are to increase the
> > knowledge that the slabs have about fragmentation, and to teach some of
> > the shrinkers about fragmentation.
> >
>
> I don't like all this work and complexity and overheads going into a
> partial solution.
>
> Look: if you have to guarantee memory can be shrunk, set aside a zone
> for it (that only fills with user reclaimable areas). This is better
> than the current frag patches because it will give you the 100%
> guarantee that you need (provided we have page migration to move mlocked
> pages).
>
> If you don't need a guarantee, then our current, simple system does the
> job perfectly.
>

Ok. To me, the rest of the thread are beating around the same points and
no one is giving ground. The points are made so lets summarise. Apologies
if anything is missing.

Problem
=======

Memory gets fragmented meaning that contiguous blocks of memory are not
free and not freeable no matter how much kswapd works

Impact
======
A number of different users are hit, in different ways
  Physical Hotplug remove: Hotplug remove needs to be able to free a large
	region of memory that is then unplugged. Different architectures have
	different ways of doing this
  Virtualization hotplug remove: The requirements are lighter here.
	Contiguous Regions from 1MiB to 64MiB (figure taken from thread)
	must be freed to move the memory between virtual machines
  High order allocations: With fragmentation, high order allocations fail.
	Depending on the workload, kswapd could work forever and not free up a
	4MiB chunk

Who cares
=========
  Physical hotplug remove: Vendors of the hardware that support this -
	Fujitsu, HP (I think), IBM etc

  Virtualization hotplug remove: Sellers of virtualization software, some
	hardware like any IBM machine that lists LPAR in it's list of
	features.  Probably software solutions like Xen are also affected
	if they want to be able to grow and shrink the virtual machines on
	demand

  High order allocations: Ultimately, hugepage users. Today, that is a
	feature only big server users like Oracle care about. In the
	future I reckon applications will be able to use them for things
	like backing the heap by huge pages. Other users like GigE,
	loopback devices with large MTUs, some filesystem like CIFS are
	all interested although they are also been told use use smaller
	pages.

Solutions
=========

Anti-defrag: This solution defines three groups of pages KernNoRclm,
	KernRclm and EasyRclm. Small sub-zone regions of size
	2^(MAX_ORDER-1) are reserved for each allocation type. If there
	are no large blocks available and no reserved pages available, it
	falls back and begins to fragment. This tries to delay
	fragmentation for as long as possible

New Zone: Add a new zone for easyrclm only allocations. This means that
	all kernel pages go in one place and all easyrclm go in another.
	This solution would allow us to reclaim contiguous blocks of
	(Note: This is basically what Solaris Kernel Cages are)

Note that I am leaving out Growing/Shrinking zone code for the moment.
While zones are currently able to get new pages with something like memory
hotadd, there is no mechanism available to move existing pages from one
zone into another. This will need planning and code. Code exists for page
migration so we can reasonable speculate about what it brings to the table
for both anti-defrag and New Zone approaches.

Pros/Cons of Solutions
======================

Anti-defrag Pros
  o Aim9 shows no significant regressions (.37% on page_test). On some
    tests, it shows performance gains (> 5% on fork_test)
  o Stress tests show that it manages to keep fragmentation down to a far
    lower level even without teaching kswapd how to linear reclaim
  o Stress tests with a linear reclaim experimental patch shows that it
    can successfully find large contiguous chunks of memory
  o It is known to help hotplug on PPC64
  o No tunables. The approach tries to manage itself as much as possible
  o It exists, heavily tested, and synced against the latest -mm1
  o Can be compiled away be redefining the RCLM_* macros and the
    __GFP_*RCLM flags

Anti-defrag Cons
  o More complexity within the page allocator
  o Adds a new layer onto the allocator that effectively creates subzones
  o Adding a new concept that maintainers have to work with
  o Depending on the workload, it fragments anyway

New Zone Pros
  o Zones are a well known and understood concept
  o For people that do not care about hotplug, they can easily get rid of it
  o Provides reliable areas of contiguous groups that can be freed for
    HugeTLB pages going to userspace
  o Uses existing zone infrastructure for balancing

New Zone Cons
  o Zones historically have introduced balancing problems
  o Been tried for hotplug and dropped because of being awkward to work with
  o It only helps hotplug and potentially HugeTLB pages for userspace
  o Tunable required. If you get it wrong, the system suffers a lot
  o Needs to be planned for and developed

Scenarios
=========

Lets outline some situations then or workloads that can occur

1. Heavy job running that consumes 75% of physical memory. Like a kernel
   build

  Anti-defrag: It will not fragment as it will never have to fallback.High
	order allocations will be possible in the remaining 25%.
  Zone-based: After been tuned to a kernel build load, it will not
	fragment. Get the tuning wrong, performance suffers or workload
	fails. High order allocations will be possible in the remaining 25%.

  Future work for scenario 1
    Anti-defrag: No problem.
    Zone-based: Tune some more if problems occur.

2. Heavy job running that needs 110% of physical memory, swap is used.
  	Example would be too many simultaneous kernel builds
  Anti-defrag: UserRclm regions are stolen to prevent too many fallbacks.
	KernNoRclm starts stealing UserRclm regions to avoid excessive
	fragmentation but some fragmentation occurs. Extent depends on the
	duration and heaviness of the load. High order allocations will
	work if kswapd runs for long enough as it will reclaim the
	UserRclm reserved areas. Your chances depend on the intensity of
	KernNoRclm allocations

  Zone-based: After been tuned to the new kernel build load, it will not
	fragment. Get it wrong and performance suffers. High order
	allocations will work if you're lucky enough to have enough
	reclaimable pages together. Your chances are not good

  Future work for scenario 2
    Anti-defrag: kswapd would need to know how to reclaim EasyRclm pages
	from the KernNoRclm, KernRclm and Fallback areas.
    Zone-based: Keep tuning

3. HighMem intensive workload with CONFIG_HIGHPTE set. Example would be a
	scientific job that was performing a very large calculation on an
	anonymous region of memory. Possible that some desktop
	workloads are like this - i.e. use large amounts of anonymous
	memory

  Anti-defrag: For ZONE_HIGHMEM, PTEs are grouped into one area,
	everything else into another, no fragmentation. HugeTLB
	allocations in ZONE_HIGHMEM will work if kswapd works long enough
  Zone-based: PTEs go to anywhere in ZONE_HIGHMEM. Easy-reclaimed goes to
	ZONE_HIGHMEM and ZONE_HOTREMOVABLE. ZONE_HIGHMEM fragments,
	ZONE_HOTREMOVABLE does not. HugeTLB pages will be available in
	ZONE_HOTREMOVABLE, but probably not in ZONE_HIGHMEM.

  Future work for scenario 3
    Anti-defrag: No problem. On-demand HugeTLB allocation for userspace is
	possible. Would work better with linear page reclaim.
    Zone-based: Depends if we care that ZONE_HIGHMEM gets fragmented. We
	would only care if trying to allocate HugeTLB pages on demand from
	ZONE_HIGHMEM. ZONE_HOTREMOVABLE depending on it's size would be
	possible. Linear reclaim will help ZONE_HOTREMOVABLE, but not
	ZONE_HIGHMEM

4. KBuild. Main concerns here are performance
  Anti-defrag: May cause problems because of the .37% drop on page_test.
	May cause improvements because of the 5% increase on fork_test. No
	figures on kbuild available
  Zone-based: No figures available. Depends heavily on being configured
	correctly

  Future work for scenario 4
    Anti-defrag: Try and optimise the paths affected. Alternatively make
	anti-defrag a configurable option by altering the values of RCLM_*
	and __GFP_*RCLM. (Note, would people be interested in a
	compile-time option for anti-defrag or would it make the complexity
	worse for people?)
    Zone-based: Tune for performance or compile away the zone

5. Physically unplug memory 25% of physical memory

  Anti-defrag: Memory in the region gets reclaimed if it's EasyRclm.
	Possibly will encounter awkward pages. Known that PPC64 has some
	success. Fujitsu's use nodes for hotplug, they would need to
	adjust the fallbacks to be fully reliable
  Zone-based: If we are unplugging the right zone, reclaim the pages.
	Possibly will encounter awkward pages (only mlock in this case)

  Future work for scenario 5
    Anti-defrag: fallback_allocs for each node for Fujitsu to be any way
	reliable. Ability to move awkward pages around. For 100% success,
	ability to move kernel pages
    Zone-based: Ability to move awkward pages around. There is no 100%
	success scenario here. You remove the ZONE_HOTREMOVEABLE area or
	you turn the machine off.

6. Fsck a large filesystem (known to be a KernNoRclm heavy workload)

  Anti-defrag: Memory fragments, but fsck is a short-lived kernel heavy
	workload. It is also known that free blocks reappear through the
	address space when it finishes. Contiguous blocks may appear in
	the middle of the zone rather than either end.
  Zone-based: If misconfigured, performance degrades. As a machine will
	not be tuned for fsck, changes of degrading are pretty high. On
	the other hand, fsck is something people can wait for

  Future work for scenario 6
    Anti-defrag: Ideally, in case of fallbacks, page migration would move
	awkward pages out of UserRclm areas
    Zone-based: Keep tuning if you run into problems

Lets say we agree on a way that ZONE_HOTREMOVABLE can be shrunk in such a
way to give pages to ZONE_NORMAL and ZONE_HIGHMEM as necessary (and we
have to be able to handle both), Situation 2 and 6 changes. Note that this
changing of zones sizes brings all the problems from the anti-defrag
approach to the zone-based approach.

2a. Heavy job running that needs 110% of physical memory, swap is used.
  Anti-defrag: UserRclm regions are stolen to prevent too many fallbacks.
	KernNoRclm starts stealing UserRclm regions to avoid excessive
	fragmentation but some fragmentation occurs. Extent depends on the
	duration and heaviness of the load.
  Zone-based: ZONE_NORMAL grows into ZONE_HOTREMOVALE. The zone cannot be
	shrunk so ZONE_NORMAL fragments as normal.

  Future work for scenario 2a
    Anti-defrag: kswapd would need to know how to clean EasyRclm pages
	from the KernNoRclm, KernRclm and Fallback reserved areas. When
	load drops off, regions will get reserved again for EasyRclm.
	Contiguous blocks will become whenever possible be it the
	beginning, middle or end of the zone. Page migration would help
	fix up single kernel pages left in EasyRclm areas.
    Zone-based: Page migration would need to move pages from the end of
	the zone so it could be shrunk.

6a. Fsck
    Anti-defrag: Memory fragments, but fsck is a short-lived kernel heavy
	workload. It is also known that free blocks reappear through the
	address space when it finishes. Once the free blocks appear, they
	get reserved for the different allocation types on demand and
	business continues as usual
    Zone-based: ZONE_NORMAL grows into ZONE_HOTREMOVABLE. No mechanism to
	shrink it so it doesn't recover

  Future work for scenario 2a

    Anti-defrag: Same as for Situation 2. kswapd would need to know how to
	clean UserRclm pages from the KernNoRclm, KernRclm and Fallback
	reserved areas.
    Zone-based: Same as for 2a. Page migration would need to move pages
	from the end of the zone so it could be shrunk

I've tried to be as objective as possible with the summary.

>From the points above though, I think that anti-defrag gets us a lot of
the way, with the complexity isolated in one place. It's downside is that
it can still break down and future work is needed to stop it degrading
(kswapd cleaning UserRclm areas and page migration when we get really
stuck). Zone-based is more reliable but only addresses a limited
situation, principally hotplug and it does not even go 100% of the way for
hotplug. It also depends on a tunable which is not cool and it is static.
If we make the zones growable+shrinkable, we run into all the same
problems that anti-defrag has today.

-- 
Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/