RE: [PATCH] Avoiding mmap fragmentation - clean rev

[Wolfgang Wander <wwc@rentec.com>]

Chen, Kenneth W writes:
 > Wolfgang Wander wrote on Wednesday, May 18, 2005 10:16 AM
 > > My goal was to place small requests close to the base while leaving
 > > larger holes open as long as possible and far from the base. 2.4
 > > kernels did this inadvertently by always starting to search from the
 > > base, my patch starts searching from the base (upward or downward)
 > > if the new request is known to fit between base and current cache
 > > pointer, thus it maintains the 2.4 quality of mixing small and large
 > > requests and maintains the huge speedups Ingo introduced with the
 > > cache pointer.
 > 
 > This algorithm tends to penalize small size request and it would do a
 > linear search from the beginning. It would also penalize large size
 > request since cache pointer will be reset to a lower address and making
 > a subsequent large request to search forward.  In your case, since all
 > mappings are anonymous mmap with same page protection, you won't notice
 > performance problem because of coalescing in the mapped area.  But other
 > app like apache web server, which mmap thousands of different files will
 > degrade. The probability of linear search is lot higher with this proposal.
 > The nice thing about the current *broken* cache pointer is that it is
 > almost an O(1) order to fulfill a request since it moves in one direction.
 > The new proposal would reduce that O(1) probability.

I do certainly see that the algorithm isn't perfect in every case
however for the test case Ingo sent me (Ingo, did you verify the
timing?)  my patch performed as well as Ingo's original solution.  I
assume that Ingo's test was requesting same map sizes for every thread
so the results would be a bit biased in my favour... ;-)

That leaves us with two scenarious for a new mmap request:

  * the new request is greater or equal than the cached_hole_size ->
    no change in behaviour
  * otherwise we start the search at a position where we know the
    new request will fit in, this could eventually even be faster
    than the required wrap.

So I don't necessarily see that the probability is reduced in all
circumstances.  Clearly mixed size requests do tend to keep the
free_area_cache pointer low and thus will likely extend the search length.

Are there test cases/benchmarks which would simulate the behaviour of an 
Apache like application under the various schemes?

Clearly one has to weight the performance issues against the memory
efficiency but since we demonstratibly throw away 25% (or 1GB) of the
available address space in the various accumulated holes a long
running application can generate I hope that for the time being we can
stick with my first solution, preferably extended by your munmap fix? 

Please? ;-)

            Wolfgang
--
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:"aart@kvack.org"> aart@kvack.org </a>