Re: [PATCH] Avoiding fragmentation through different allocator

Marcelo Tosatti
2005-01-23T17:05:25Z

On Sat, Jan 22, 2005 at 07:59:49PM -0200, Marcelo Tosatti wrote:
> On Sat, Jan 22, 2005 at 09:48:20PM +0000, Mel Gorman wrote:
> > On Fri, 21 Jan 2005, Marcelo Tosatti wrote:
> >
> > > On Thu, Jan 20, 2005 at 10:13:00AM +0000, Mel Gorman wrote:
> > > > <Changelog snipped>
> > >
> > > Hi Mel,
> > >
> > > I was thinking that it would be nice to have a set of high-order
> > > intensive workloads, and I wonder what are the most common high-order
> > > allocation paths which fail.
> > >
> >
> > Agreed. As I am not fully sure what workloads require high-order
> > allocations, I updated VMRegress to keep track of the count of
> > allocations and released 0.11
> > (http://www.csn.ul.ie/~mel/projects/vmregress/vmregress-0.11.tar.gz). To
> > use it to track allocations, do the following
> >
> > 1. Download and unpack vmregress
> > 2. Patch a kernel with kernel_patches/v2.6/trace_pagealloc-count.diff .
> > The patch currently requires the modified allocator but I can fix that up
> > if people want it. Build and deploy the kernel
> > 3. Build vmregress by
> > ./configure --with-linux=/usr/src/linux-2.6.11-rc1-mbuddy
> > (or whatever path is appropriate)
> > make
> > 4. Load the modules with;
> > insmod src/code/vmregress_core.ko
> > insmod src/sense/trace_alloccount.ko
> >
> > This will create a proc entry /proc/vmregress/trace_alloccount that looks
> > something like;
> >
> > Allocations (V1)
> > -----------
> > KernNoRclm 997453 370 50 0 0 0 0 0 0 0 0
> > KernRclm 35279 0 0 0 0 0 0 0 0 0 0
> > UserRclm 9870808 0 0 0 0 0 0 0 0 0 0
> > Total 10903540 370 50 0 0 0 0 0 0 0 0
> >
> > Frees
> > -----
> > KernNoRclm 590965 244 28 0 0 0 0 0 0 0 0
> > KernRclm 227100 60 5 0 0 0 0 0 0 0 0
> > UserRclm 7974200 73 17 0 0 0 0 0 0 0 0
> > Total 19695805 747 100 0 0 0 0 0 0 0 0
> >
> > To blank the counters, use
> >
> > echo 0 > /proc/vmregress/trace_alloccount
> >
> > Whatever workload we come up with, this proc entry will tell us if it is
> > exercising high-order allocations right now.
>
> Great, excellent! Thanks.
>
> I plan to spend some time testing and trying to understand the vmregress package
> this week.
>
> > > It mostly depends on hardware because most high-order allocations happen
> > > inside device drivers? What are the kernel codepaths which try to do
> > > high-order allocations and fallback if failed?
> > >
> >
> > I'm not sure. I think that the paths we exercise right now will be largely
> > artifical. For example, you can force order-2 allocations by scping a
> > large file through localhost (because of the large MTU in that interface).
> > I have not come up with another meaningful workload that guarentees
> > high-order allocations yet.
>
> Thoughts and criticism of the following ideas are very much appreciated:
>
> In private conversation with wli (who helped me providing this information) we can
> conjecture the following:
>
> Modern IO devices are capable of doing scatter/gather IO.
>
> There is overhead associated with setting up and managing the scatter/gather tables.
>
> The benefit of large physically contiguous blocks is the ability to avoid the SG
> management overhead.
>
> Now the question is: The added overhead of allocating high order blocks through migration
> offsets the overhead of SG IO ? Quantifying that is interesting.

What is the overhead of the SG IO management and how is the improvement without them?

Are block IO drivers trying to allocate big physical segments? I bet they are not, because the
"pool of huge pages" (as you say) is limited.

>
> This depends on the driver implementation (how efficiently its able to manage the SG IO tables) and
> device/IO subsystem characteristics.
>
> Also filesystems benefit from big physically contiguous blocks. Quoting wli
> "they want bigger blocks and contiguous memory to match bigger blocks..."
>
> I completly agree that your simplified allocator decreases fragmentation which in turn
> benefits the system overall.
>
> This is an area which can be further improved - ie efficiency in reducing fragmentation
> is excellent.
> I sincerely appreciate the work you are doing!
>
> > > To measure whether the cost of page migration offsets the ability to be
> > > able to deliver high-order allocations we want a set of meaningful
> > > performance tests?
> > >
> >
> > Bear in mind, there are more considerations. The allocator potentially
> > makes hotplug problems easier and could be easily tied into any
> > page-zeroing system. Some of your own benchmarks also implied that the
> > modified allocator helped some types of workloads which is beneficial in
> > itself.The last consideration is HugeTLB pages, which I am hoping William
> > will weigh in.
> >
> > Right now, I believe that the pool of huge pages is of a fixed size
> > because of fragmentation difficulties. If we knew we could allocate huge
> > pages, this pool would not have to be fixed. Some applications will
> > heavily benefit from this. While databases are the obvious one,
> > applications with large heaps will also benefit like Java Virtual
> > Machines. I can dig up papers that measured this on Solaris although I
> > don't have them at hand right now.
>
> Please.
>
> > We know right now that the overhead of this allocator is fairly low
> > (anyone got benchmarks to disagree) but I understand that page migration
> > is relatively expensive. The allocator also does not have adverse
> CPU+cache affects like migration and the concept is fairly simple.
>
> Agreed.
>
> > > Its quite possible that not all unsatisfiable high-order allocations
> > > want to force page migration (which is quite expensive in terms of
> > > CPU/cache). Only migrate on __GFP_NOFAIL ?
> > >
> >
> > I still believe with the allocator, we will only have to migrate in
> > exceptional circumstances.
>
> Agreed - best scenario is the guaranteed availability of high-order blocks, where
> migration is not necessary.