Re: frontswap/zcache: xvmalloc discussion

[Seth Jennings <sjenning@linux.vnet.ibm.com>]

Nitin,

I have been working on this xcfmalloc allocator using most of the design 
points you described (cross-page allocations, compaction).  I should 
have a patch soon.

On 06/24/2011 01:11 AM, Nitin Gupta wrote:
> Hi Seth,
> 
> On 06/22/2011 12:15 PM, Seth Jennings wrote:
> 
>>
>> The real problem here is compressing pages of size x and storing them in
>> a pool that has "chunks", if you will, also of size x, where allocations
>> can't span multiple chunks. Ideally, I'd like to address this issue by
>> expanding the size of the xvmalloc pool chunks from one page to four
>> pages (I can explain why four is a good number, just didn't want to make
>> this note too long).
>>
>> After a little playing around, I've found this isn't entirely trivial to
>> do because of the memory mapping implications; more specifically the use
>> of kmap/kunamp in the xvmalloc and zcache layers. I've looked into using
>> vmap to map multiple pages into a linear address space, but it seems
>> like there is a lot of memory overhead in doing that.
>>
>> Do you have any feedback on this issue or suggestion solution?
>>
> 
> xvmalloc fragmentation issue has been reported by several zram users and 
> quite some time back I started working on a new allocator (xcfmalloc) 
> which potentially solves many of these issues. However, all of the 
> details are currently on paper and I'm sure actual implementation will 
> bring a lot of surprises.
> 
> Currently, xvmalloc wastes memory due to:
>   - No compaction support: Each page can store chunks of any size which 
> makes compaction really hard to implement.
>   - Use of 0-order pages only: This was enforced to avoid memory 
> allocation failures. As Dan pointed out, any higher order allocation is 
> almost guaranteed to fail under memory pressure.
> 
> To solve these issues, xcfmalloc:
>   - Supports compaction: Its size class based (like SLAB) which, among 
> other things, simplifies compaction.
>   - Supports higher order pages using little trickery:
> 
> For 64-bit systems, we can simply use vmalloc(16k or 64k) pages and 
> never bother unmapping them. This is expensive (how much?) in terms of 
> both CPU and memory but easy to implement.
> 
> But on 32-bit (almost all "embedded" devices), this ofcourse cannot be 
> done. For this case, the plan is to create a "vpage" abstraction which 
> can be treated as usual higher-order page.
> 
> vpage abstraction:
>   - Allocate 0-order pages and maintain them in an array
>   - Allow a chunk to cross at most one 4K (or whatever is the native 
> PAGE_SIZE) page boundary. This limits maximum allocation size to 4K but 
> simplifies mapping logic.
>   - A vpage is assigned a specific size class just like usual SLAB. This 
> will simplify compaction.
>   - xcfmalloc() will return a object handle instead of a direct pointer.
>   - Provide xcfmalloc_{map,unmap}() which will handle the case where a 
> chunk spans two pages. It will map the pages using kmap_atomic() and 
> thus user will be expected to unmap them soon.
>   - Allow vpage to be "partially freed" i.e. empty 4K pages can be freed 
> individually if completely empty.
> 
> Much of this vpage functionality seems to be already present in mainline 
> as "flexible arrays"[1]
> 
> For scalability, we can simply go for per-cpu lists and use Hoard[2] 
> like design to bound fragmentation associated with such per-cpu slabs.
> 
> Unfortunately, I'm currently too loaded to work on this, atleast for 
> next 2 months (internship) but would be glad to contribute if someone is 
> willing to work on this.
> 
> [1] http://lxr.linux.no/linux+v2.6.39/Documentation/flexible-arrays.txt
> [2] Hoard allocator: 
> http://www.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf
> 
> Thanks,
> Nitin
> 
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>