Re: frontswap/zcache: xvmalloc discussion

[Nitin Gupta <ngupta@vflare.org>]

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>