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@xxxxxxxxx. 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@xxxxxxxxx";> email@xxxxxxxxx </a>
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. 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@xxxxxxxxx";> email@xxxxxxxxx </a>