RE: [PATCH] Avoiding mmap fragmentation - clean rev

Chen, Kenneth W
2005-05-18T17:57:00Z

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.