On Wed, Dec 15, 2010 at 7:37 PM, Venkatesh Srinivas < vsrini...@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 _______________________________________________ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
