vm_map_findspace space search?
alan.l.cox at gmail.com
Thu Dec 16 18:43:45 UTC 2010
On Wed, Dec 15, 2010 at 7:37 PM, Venkatesh Srinivas <
vsrinivas at dragonflybsd.org> wrote:
> In svn r133636, there was a commit to convert the linear search in
> vm_map_findspace() to use the vm_map splay tree. Just curious, were
> there any discussions about that particular change? Any measurements
> other than the ones noted in the commit log? Any notes on why that
> design was used rather than any other?
> I've seen the 'Some mmap observations...' thread from about a year
> earlier and was wondering about some of the possible designs discussed
> there. In particular the Bonwick/Adams vmem allocator was brought up;
> I think that something inspired by it (and strangely close to the
> QuickFit malloc) would be appropriate:
> Here's how I see it working:
> * Add a series of power-of-two or logarithmic sized freelists to the
> vm_map structure; they would point to vm_map_entries immediately to the
> left of free space holes of a given size.
> * finding free space would just pop an entry off of the free space list
> and split in the usual way; deletion could coalesce in constant time.
> * Unlike the vmem allocator, we would not need to allocate external
> boundary tags; the vm_map_entries themselves would be the tags.
> At least from looking at the pattern of vm_map_findspace()s on DFly,
> the most common requests were for 1 page, 4 page, and 16 page-sized
> holes (iirc these combined for 75% of requests there; I imagine the
> pattern in FreeBSD would be very similar). The fragmentation concerns
> from this would be pretty minor with that pattern...
I'm afraid that the pattern is is not always so simple. Sometimes external
fragmentation is, in fact, a problem. For example, search for "ZFS ARC
kmem_map fragmentation". I recall there being at least one particularly
detailed e-mail that quantified the fragmentation being caused by the ZFS
ARC. There are also microbenchmarks that simulate an mmap() based web
server, which will show a different pattern than you describe.
If you're interested in working on something in this general area, I can
More information about the freebsd-hackers