vmem Resource Allocator

[Alboin]

Has anyone here read this paper? I was wondering if I understand it 100%...(Note: I'm only interested in the vmem idea, atm. I'm not doing much with MP's yet, so magazines aren't of my concern.)

I understand the idea relatively well, so I won't bother rewriting that here. The implementation, on the other hand...

vmem seems simple. Each 'arena', or allocator, keeps its 'segments', or allocated regions, in two ways, depending on their status. Moreover, all of the segments' boundary tags are linked together in order as well.

If a segment is free, it is stored in a list determined by its size. So, if the segment's size falls between n and n+1, it is located in freelist[n]. When alloc is called, the appropriate list is determined from the size requested, and a segment is found. Then, if it is too large, it is split, and the remaining half is then put into its correct list. The requested half is taken out of its list, and put into the arena's hash table. (below) The segment is then returned.

If a segment is allocated, however, it is stored in a hash table. When free is called on it, free finds the segment's boundary tag in the hash table, and moves it to the appropriate free list.

As for quantum caching, that simply means that should an alloc come in for objects up to qcache_max that are in the form (n*quantum), we just return an object from a local cache. (local cache as in slab allocation.) That is, we do not return a segment of the arena, but of a separate, independent, cache that feeds off of the arena.

All of this, then, can be used to create, for example, a physical and virtual memory manager, and, with a slab allocator, a malloc interface.

I'm at least semi-on-track, aren't I? Any hits would be lovely.
Thanks,
Alboin

[xyzzy]

Hi,

I'm using the VMem resource allocator in my kernel, currently only to manage the kernel heap, but I plan to use it for PID allocation sometime. My implementation is somewhat more simple than what you describe, and I don't currently implement several features described in the paper, such as quantum caching and ability to sleep while waiting for allocations.

Basically, I have just a single list that all boundary tags (both allocated and free, and both segments and spans) are stored on, in order. When a segment is freed, it is marked as free, and then vmem_free checks if there are any adjacent free segments. If there are, the segment that was just freed is coalesced with the adjacent free segments. This makes it easy to do allocations: just iterate through the list to find a free segment tag large enough to satisfy the allocation.

One thing that should be noted is that you have to be careful with how you allocate boundary tags. How you do this depends on what you use it for. I'm using it for the kernel heap, which means that I can't use malloc to allocate tags as that will end up recursively allocating. So instead, I pull a page out of the physical memory manager, split it up into tag structures and put them on a list. Then to get a boundary tag I just take off this list.

You can see my implementation of VMem here: http://svn.exclaim-project.org/websvn/f ... m%2Fvmem.c

Hope that helps!

[Alboin]

Yeah, thanks. That seems to agree with what I was thinking.

-Alboin