Date: Thu, 16 Dec 2010 12:43:43 -0600 From: Alan Cox <alan.l.cox@gmail.com> To: me@endeavour.zapto.org Cc: freebsd-hackers@freebsd.org Subject: Re: vm_map_findspace space search? Message-ID: <AANLkTi=OQS-mXGna8e8mUH%2BaNHjfOVN2FzRZ3OARpVso@mail.gmail.com> In-Reply-To: <AANLkTimCAAFqZjvCX1ebi7Epjc0i5f9kNTSkumHLEizM@mail.gmail.com> References: <AANLkTimCAAFqZjvCX1ebi7Epjc0i5f9kNTSkumHLEizM@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, Dec 15, 2010 at 7:37 PM, Venkatesh Srinivas < vsrinivas@dragonflybsd.org> wrote: > Hi, > > 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 suggest something. Alan
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTi=OQS-mXGna8e8mUH%2BaNHjfOVN2FzRZ3OARpVso>