Skip to contentSkip to conversation

: compressed in-memory swapping

PATCH In review Nitin Gupta 7 participants 22 messages Mar 17, 2009 – Mar 20, 2009 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover : compressed in-memory swapping

Hi,

Project home: http://code.google.com/p/compcache/

It allows creating a RAM based block device which acts as swap disk. Pages swapped to this device are compressed and stored in memory itself. This is a big win over swapping to slow hard-disk which are typically used as swap disk. For flash, these suffer from wear-leveling issues when used as swap disk - so again its helpful. For swapless systems, it allows more apps to run.

Its now part of Ubuntu, ALT Linux and some other distros.

Some use cases:
- Embedded Devices: Memory is scarce and adding more memory increases device cost. Also, flash storage suffers from wear-levelling issues.
- Virtualization: For host/hypervisor, VM/guest memory is all anonymous memory. So, compcache can compress any part of guest. So we can host more VMs on same amount of memory.
- Thinclients.

Testing/Performance:
- Testing for use on Thinclients (contrib: Nai Xia):
Details: http://code.google.com/p/compcache/wiki/LTSPPerf
Summary: http://code.google.com/p/compcache/wiki/LTSPPerfSummary

Summary: after the compcache was loaded:
- The time of paging down one pdf page was reduced to 1/4~1/100
- The time of switching from one firefox tab to another was reduced to 1/6
- The capacity of kpdf was be increased from 2 pdf files to 11 pdf files.
- The capacity of firefox was increased from 6 web pages to 15 web pages.

- Testing on x86 and x64 VMs (256/512MB RAM, 1 VCPU, 512MB Swap):
Started Fedora 10 and some "generic desktop" apps (KDE4, Firefox, filemanager, editors) - without compcache, system swapped heavily and very unresponsive. With compcache, very noticeable improvement in responsiveness.

- Some reported running on PS3 systems though no performance stats available here.

Limitations:
- Being a "swap disk" it can compress only anonymous memory. But as mentioned above, at hypervisor/host level, all guest memory is anonymous so any part of guest memory can be compressed.
- Memory allocator used is not scalable at all (work in progress).
- No run-time defragmentation, swapping of allocated memory - however, incompressible pages are forwarded to physical swap and can set limit on amount of memory used by compcache.

I do not claim performance gain for any arbitrary workload but as testing shows, it certainly helps in some cases :)

Also note that this is a low risk change - it does not modify any part of kernel. Its just an additional module. In case you find it hurting performance, just unload this module and maybe use normal disk swap.

Any reviews/comments/suggestions are welcome.

Thanks,
Nitin

#1 lore raw

PATCH 1/3 : compressed RAM block device

 drivers/block/Kconfig     |   22 +
 drivers/block/Makefile    |    1 +
 drivers/block/compcache.c |  995 +++++++++++++++++++++++++++++++++++++++++++++
 drivers/block/compcache.h |  160 ++++++++
 4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

See Documentation/blockdev/compcache.txt for usage details.

Project home: http://code.google.com/p/compcache/

---

drivers/block/Kconfig +22 -0
index 0344a8a..cccf76c 100644
@@ -348,6 +348,28 @@ config BLK_DEV_RAM_SIZE
 	  The default value is 4096 kilobytes. Only change this if you know
 	  what you are doing.
 
+config BLK_DEV_COMPCACHE
+	tristate "Compressed RAM swap device"
+	depends on XVMALLOC
+	depends on LZO_COMPRESS
+	depends on LZO_DECOMPRESS
+	help
+	  Saying Y here will allow you to use in-memory compressed swapping.
+	  It creates a pseudo block device (named ramzswap) which acts as
+	  swap device. Pages swapped to this device are compressed and stored
+	  in memory itself.
+
+	  Project home: http://code.google.com/p/compcache/
+	  For details, read <file:Documentation/blockdev/compcache.txt>
+
+	  To compile this driver as a module, choose M here: the
+	  module will be called compcache.
+
+config BLK_DEV_COMPCACHE_STATS
+	bool "Collect statistics"
+	depends on BLK_DEV_COMPCACHE
+	default y
+
 config BLK_DEV_XIP
 	bool "Support XIP filesystems on RAM block device"
 	depends on BLK_DEV_RAM
drivers/block/Makefile +1 -0
index 204332b..6b2ee9e 100644
@@ -12,6 +12,7 @@ obj-$(CONFIG_PS3_DISK)		+= ps3disk.o
 obj-$(CONFIG_ATARI_FLOPPY)	+= ataflop.o
 obj-$(CONFIG_AMIGA_Z2RAM)	+= z2ram.o
 obj-$(CONFIG_BLK_DEV_RAM)	+= brd.o
+obj-$(CONFIG_BLK_DEV_COMPCACHE)	+= compcache.o
 obj-$(CONFIG_BLK_DEV_LOOP)	+= loop.o
 obj-$(CONFIG_BLK_DEV_XD)	+= xd.o
 obj-$(CONFIG_BLK_CPQ_DA)	+= cpqarray.o
drivers/block/compcache.c new file +995 -0

995 lines not on this page · raw message

drivers/block/compcache.h new file +160 -0

160 lines not on this page · raw message

#2 lore raw

Re: [PATCH 1/3]: compressed RAM block device

Quoted 10 lines · On Tuesday 17 March 2009 22:36:46 Nitin Gupta wrote:
  drivers/block/Kconfig     |   22 +
  drivers/block/Makefile    |    1 +
  drivers/block/compcache.c |  995
+++++++++++++++++++++++++++++++++++++++++++++ drivers/block/compcache.h | 
160 ++++++++
  4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

Quoted 8 lines

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

See Documentation/blockdev/compcache.txt for usage details.

Project home: http://code.google.com/p/compcache/

I wonder how hard it would be to make the compression code use an arbitrary file or device for the storage backend rather than make a new block device? Then you could make a new ram block device that can swap its pages out (or even extend brd.c with that functionality, or use loop on tmpfs etc).

#3 lore raw

Re: [PATCH 1/3]: compressed RAM block device

Quoted 18 lines · Nick Piggin
Quoted 17 lines · On Tuesday 17 March 2009 22:36:46 Nitin Gupta wrote:
  drivers/block/Kconfig     |   22 +
  drivers/block/Makefile    |    1 +
  drivers/block/compcache.c |  995
+++++++++++++++++++++++++++++++++++++++++++++ drivers/block/compcache.h | 
160 ++++++++
  4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

See Documentation/blockdev/compcache.txt for usage details.

Quoted 9 lines
Quoted 1 line

Project home: http://code.google.com/p/compcache/

I wonder how hard it would be to make the compression code use an arbitrary file or device for the storage backend rather than make a new block device? Then you could make a new ram block device that can swap its pages out (or even extend brd.c with that functionality, or use loop on tmpfs etc).

Its already done as mentioned in Documentation/blockdev/compcache.txt (patch 3/3) but I should have added it here also: compcache accepts "backing_dev" parameter for backing swap partition - this allows us to forward any R/W request to backing swap device. Currently only poorly compressible pages (compress length > PAGE_SIZE/2) are forwarded to backing_dev.

Thanks,
Nitin

#4 lore raw

Re: [PATCH 1/3]: compressed RAM block device

Quoted 28 lines · On Wednesday 18 March 2009 23:38:30 Nitin Gupta wrote:
Quoted 19 lines · Nick Piggin
Quoted 18 lines · On Tuesday 17 March 2009 22:36:46 Nitin Gupta wrote:
  drivers/block/Kconfig     |   22 +
  drivers/block/Makefile    |    1 +
  drivers/block/compcache.c |  995
+++++++++++++++++++++++++++++++++++++++++++++ drivers/block/compcache.h
| 160 ++++++++
  4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

See Documentation/blockdev/compcache.txt for usage details.

Quoted 7 lines
Quoted 1 line

Project home: http://code.google.com/p/compcache/

I wonder how hard it would be to make the compression code use an arbitrary file or device for the storage backend rather than make a new block device? Then you could make a new ram block device that can swap its pages out (or even extend brd.c with that functionality, or use loop on tmpfs etc).

Quoted 3 lines

Its already done as mentioned in Documentation/blockdev/compcache.txt (patch 3/3) but I should have added it here also: compcache accepts "backing_dev" parameter for backing swap partition - this allows us to

I meant more like compressing the data then passing it down to another device. I guess you still need to make a block device to operate on the requests, however, so it would get more complicated because you'd need to pass your own down.... yeah it would probably end up being just as complex and less efficient. Ignore me then :)

Quoted 3 lines

forward any R/W request to backing swap device. Currently only poorly compressible pages (compress length > PAGE_SIZE/2) are forwarded to backing_dev.

#5 lore raw

Re: [PATCH 1/3]: compressed RAM block device

In reply to Nitin Gupta
Quoted 9 lines · Nitin Gupta
 drivers/block/Kconfig     |   22 +
 drivers/block/Makefile    |    1 +
 drivers/block/compcache.c |  995 +++++++++++++++++++++++++++++++++++++++++++++
 drivers/block/compcache.h |  160 ++++++++
 4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

Quoted 8 lines

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

See Documentation/blockdev/compcache.txt for usage details.

Project home: http://code.google.com/p/compcache/

Compcache is really bad name for this. zramdisk? gzrd?

Is the block device useful for general filesystem storage?

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
#6 lore raw

Re: [PATCH 1/3]: compressed RAM block device

Quoted 15 lines · Pavel Machek
Quoted 14 lines · Nitin Gupta
 drivers/block/Kconfig     |   22 +
 drivers/block/Makefile    |    1 +
 drivers/block/compcache.c |  995 +++++++++++++++++++++++++++++++++++++++++++++
 drivers/block/compcache.h |  160 ++++++++
 4 files changed, 1178 insertions(+), 0 deletions(-)

Creates RAM based block device (ramzswap0) which can be used as swap device. Pages swapped to this are compressed and stored in memory itself.

The module is called compcache.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

Quoted 7 lines
Quoted 3 lines

See Documentation/blockdev/compcache.txt for usage details.

Project home: http://code.google.com/p/compcache/

Compcache is really bad name for this. zramdisk? gzrd?

It was named compcache according to its original goal:
compressed caching for anonymous _and_ filesystem caches. This ram block device is for handling anonymous memory only. Anyway, actual block device is called ramzswap which you might like more :)

Quoted 2 lines

Is the block device useful for general filesystem storage?

No. It can only handle page aligned I/O. But it shouldn't be too hard to make it generic compressed ram disk with physical backing device support. But unfortunately I do not have bandwidth to do this myself.

Thanks,
Nitin

#7 lore raw

PATCH 2/3 : xvmalloc memory allocator

In reply to Nitin Gupta
 include/linux/xvmalloc.h |   30 +++
 init/Kconfig             |   14 +
 mm/Makefile              |    1 +
 mm/xvmalloc.c            |  605 ++++++++++++++++++++++++++++++++++++++++++++++
 mm/xvmalloc_int.h        |   91 +++++++
 5 files changed, 741 insertions(+), 0 deletions(-)

xvMalloc is a memory allocator designed specifically for compcache project.

* Features:
- Low metadata overhead (just 4 bytes per object)
- O(1) Alloc/Free - except when we have to call system page allocator to get additional memory.
- Very low fragmentation: In all tests, xvMalloc memory usage is within 12%

	of "Ideal".

One of the main highlights is that it maps pages only when required. So, it does not hog vmalloc area which is very small on 32-bit systems.

Slub allocator could not be used due to fragmentation issues:
http://code.google.com/p/compcache/wiki/AllocatorsComparison
Data here shows kmalloc using ~43% more memory than TLSF and xvMalloc is showed ~2% more space efficiency than TLSF (due to smaller metadata).

* Implementation:
It uses two-level bitmap search to find free list containing block of correct size. This idea is taken from TLSF (Two-Level Segregate Fit) allocator and is well explained in its paper (see [Links] below). Highlights:
- Pool based allocator: each pool can grow/shrink.
- Immediate coalescing of free blocks.
- Maps/Unmaps memory pages only when required.

* Limitations:
- Poor scalability: No per-cpu data structures (work in progress).

[Links]
1. Details and Performance data:
http://code.google.com/p/compcache/wiki/xvMalloc
http://code.google.com/p/compcache/wiki/xvMallocPerformance

2. TLSF memory allocator:
home: http://rtportal.upv.es/rtmalloc/
paper: http://rtportal.upv.es/rtmalloc/files/MRBC_2008.pdf

---

include/linux/xvmalloc.h new file +30 -0
new file mode 100755
index 0000000..92366bd
@@ -0,0 +1,30 @@
+/*
+ * xvmalloc.h
+ *
+ * Copyright (C) 2008, 2009  Nitin Gupta
+ *
+ * This code is released using a dual license strategy: GPL/LGPL
+ * You can choose the licence that better fits your requirements.
+ *
+ * Released under the terms of the GNU General Public License Version 2.0
+ * Released under the terms of the GNU Lesser General Public License Version 2.1
+ */
+
+#ifndef _XVMALLOC_H_
+#define _XVMALLOC_H_
+
+#define INVALID_POOL_ID	NULL
+#define INVALID_PGNUM	((u32)(-1))
+
+struct Pool;
+
+struct Pool *xvCreateMemPool(void);
+void xvDestroyMemPool(struct Pool *pool);
+
+int xvMalloc(struct Pool *pool, u32 size, u32 *pageNum, u32 *offset);
+void xvFree(struct Pool *pool, u32 pageNum, u32 offset);
+
+u32 xvGetObjectSize(void *obj);
+u64 xvGetTotalSizeBytes(struct Pool *pool);
+
+#endif
init/Kconfig +14 -0
index 6a5c5fe..5e722cc 100644
@@ -930,6 +930,20 @@ config SLOB
 
 endchoice
 
+config XVMALLOC
+	tristate "xvMalloc memory allocator"
+	help
+	   This is a simple, low fragmentation, O(1) allocator.
+	   Details: http://code.google.com/p/compcache/wiki/xvMalloc
+
+config XVMALLOC_STATS
+	depends on XVMALLOC
+	bool "Collect statistics"
+	default y
+	help
+	  Collect basic allocator statistics with minimal overhead.
+	  In unsure, say Y.
+
 config PROFILING
 	bool "Profiling support (EXPERIMENTAL)"
 	help
mm/Makefile +1 -0
index 72255be..b6b705f 100644
@@ -26,6 +26,7 @@ obj-$(CONFIG_SLOB) += slob.o
 obj-$(CONFIG_MMU_NOTIFIER) += mmu_notifier.o
 obj-$(CONFIG_SLAB) += slab.o
 obj-$(CONFIG_SLUB) += slub.o
+obj-$(CONFIG_XVMALLOC) += xvmalloc.o
 obj-$(CONFIG_FAILSLAB) += failslab.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
mm/xvmalloc.c new file +605 -0

605 lines not on this page · raw message

mm/xvmalloc_int.h new file +91 -0

91 lines not on this page · raw message

#8 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 4 lines · Nitin Gupta

Slub allocator could not be used due to fragmentation issues:
http://code.google.com/p/compcache/wiki/AllocatorsComparison
Data here shows kmalloc using ~43% more memory than TLSF and xvMalloc is showed ~2% more space efficiency than TLSF (due to smaller metadata).

Well this looks like the use of 2^n sizes of the kmalloc arrayse cause a lot of wastage here. Creating slab caches that fit your needs may help? Have you had a look at the SLOB approach?

#9 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

(sending again since it was blocked by lkml last time. Sorry Christoph for duplicate email).

Quoted 9 lines · Christoph Lameter
Quoted 4 lines · Nitin Gupta

Slub allocator could not be used due to fragmentation issues:
http://code.google.com/p/compcache/wiki/AllocatorsComparison
Data here shows kmalloc using ~43% more memory than TLSF and xvMalloc is showed ~2% more space efficiency than TLSF (due to smaller metadata).

Well this looks like the use of 2^n sizes of the kmalloc arrayse cause a lot of wastage here. Creating slab caches that fit your needs may help?

Creating slabs for sizes in range, say, [32, 3/4*PAGE_SIZE] separated by 64bytes will require 48 slabs! Then for slab of each size class will have wastage due to unused slab objects in each class.
Larger difference in slab sizes (and thus small no. of them), will surely cause too much wastage due to internal fragmentation.

Another (more important) point to consider is that, use of slabs will eat-up vmalloc area to keep slab memory backed by VA space. On 32-bit systems, vmalloc area is small and limits amount of memory that can be allocated for compressed pages. With xvmalloc we map/unmap pages on demand thus removing dependence on vmalloc VA area.

Quoted 2 lines

Have you had a look at the SLOB approach?

Nope. I will see how this may help.

Thanks,
Nitin

A message that is not in the archive (sent off-list or not yet received): [email protected]

#11 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 8 lines · Nitin Gupta

Creating slabs for sizes in range, say, [32, 3/4*PAGE_SIZE] separated by 64bytes
will require 48 slabs! Then for slab of each size class will have wastage due to
unused slab objects in each class.
Larger difference in slab sizes (and thus small no. of them), will surely cause too much
wastage due to internal fragmentation.

The slabs that match existing other slabs of similar sizes will be aliased and not created. Create the 48 slabs and you likely will only use 10 real additional ones. The rest will just be pointing to existing ones.

Quoted 5 lines

Another (more important) point to consider is that, use of slabs will eat-up vmalloc area to keep slab memory backed by VA space. On 32-bit systems, vmalloc area is small and limits amount of memory that can be allocated for compressed pages. With xvmalloc we map/unmap pages on demand thus removing dependence on vmalloc VA area.

Slab memory is not backed by vmalloc space.

Quoted 2 lines
Quoted 1 line

Have you had a look at the SLOB approach?

Nope. I will see how this may help.

Slob is another attempt to reduce wastage due to the rounding up of object sizes to 2^N in SLAB/SLUB.

#12 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 8 lines · Nitin Gupta
Quoted 8 lines

Creating slabs for sizes in range, say, [32, 3/4*PAGE_SIZE] separated by 64bytes
will require 48 slabs! Then for slab of each size class will have wastage due to
unused slab objects in each class.
Larger difference in slab sizes (and thus small no. of them), will surely cause too much
wastage due to internal fragmentation.

Quoted 3 lines · Christoph Lameter

The slabs that match existing other slabs of similar sizes will be aliased and not created. Create the 48 slabs and you likely will only use 10 real additional ones. The rest will just be pointing to existing ones.

Yup. One thing I don't quite understand is why you need all the 48 caches in the first place. Allocation sizes tend to be clustered and I would have imagined you'd see that when compressing page sized chunks as well. Using kmemtrace to analyze the exact reason for the bad fragmentation would probably be helpful.

#13 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 12 lines · Pekka Enberg
Quoted 8 lines · Nitin Gupta
Quoted 8 lines

Creating slabs for sizes in range, say, [32, 3/4*PAGE_SIZE] separated by 64bytes
will require 48 slabs! Then for slab of each size class will have wastage due to
unused slab objects in each class.
Larger difference in slab sizes (and thus small no. of them), will surely cause too much
wastage due to internal fragmentation.

On Tue, Mar 17, 2009 at 10:58 AM, Christoph Lameter <[email protected]> wrote:

Quoted 8 lines
Quoted 3 lines

The slabs that match existing other slabs of similar sizes will be aliased and not created. Create the 48 slabs and you likely will only use 10 real additional ones. The rest will just be pointing to existing ones.

Yup. One thing I don't quite understand is why you need all the 48 caches in the first place. Allocation sizes tend to be clustered and I would have imagined you'd see that when compressing page sized chunks as well.

Compressed page lengths sometimes do tend to cluster within somewhat small range. However, the range of where majority of pages will lie depends highly of workload - sometimes range is not clear and sometime there is no preferred range at all. Please refer this data:
http://code.google.com/p/compcache/wiki/CompressedLengthDistribution

It shows compressed page size distribution for various workloads.

Quoted 3 lines

Using kmemtrace to analyze the exact reason for the bad fragmentation would probably be helpful.

That was purely internal fragmentation.
Wastage per obj = ksize(obj) - actual_size.

Code used for testing:
http://code.google.com/p/compcache/source/browse/trunk/sub-projects/testing/kmalloc_test/kmalloc_test.c
This is a "SwapReplay client". Please see:
http://code.google.com/p/compcache/wiki/SwapReplayDesign

Thanks,
Nitin

#14 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

In reply to Christoph Lameter
Quoted 15 lines · Christoph Lameter
Quoted 8 lines · Nitin Gupta

Creating slabs for sizes in range, say, [32, 3/4*PAGE_SIZE] separated by 64bytes
will require 48 slabs! Then for slab of each size class will have wastage due to
unused slab objects in each class.
Larger difference in slab sizes (and thus small no. of them), will surely cause too much
wastage due to internal fragmentation.

The slabs that match existing other slabs of similar sizes will be aliased and not created. Create the 48 slabs and you likely will only use 10 real additional ones. The rest will just be pointing to existing ones.

Quoted 8 lines
Quoted 5 lines

Another (more important) point to consider is that, use of slabs will eat-up vmalloc area to keep slab memory backed by VA space. On 32-bit systems, vmalloc area is small and limits amount of memory that can be allocated for compressed pages. With xvmalloc we map/unmap pages on demand thus removing dependence on vmalloc VA area.

Slab memory is not backed by vmalloc space.

Oh, it uses "low memory". Still not good for compcache :)

Quoted 7 lines
Quoted 2 lines
Quoted 1 line

Have you had a look at the SLOB approach?

Nope. I will see how this may help.

Slob is another attempt to reduce wastage due to the rounding up of object sizes to 2^N in SLAB/SLUB.

I had detailed look at SLOB allocator and found it unacceptable to be used for compcache.

To begin with, SLOB maintains just 3 freelists:

 - for size < 256     - free_slob_small
 - [256, 1024)        - free_slob_medium
 - [1024, PAGE_SIZE)  - free_slob_large

and allocates from one of these lists depending on size requested. No need to create 50+ caches, we only get to use these 3 lists.

Why SLOB is bad:

1) O(n) allocation:
To find block of given size, it _linearaly_ scans corresponding free list to find a page with _total_ free space >= requested size. This free space might not be contiguous. So it runs through free blocks within each such candidate page until it finally finds some page with free contiguous area >= requested size.

2) When growing SLOB cache, page is added to one of 3 freelists (depending on what size we are currently allocating). After this, this page can never move to any other list - even if its free space drops down to fall in next range below or vice versa. This has two problems:
- Potentially large wastage due to "page internal fragmentation": e.g.:
alloc(3096) is satisfied from a page in 'large free list'. Now it has 1000b free (assuming 4k page) which will now never be used.
- It can trigger unnecessary cache grows: e.g.: even though we have such
unfilled pages in 'large' list, allocation in 'small' range can still cause cache grow if 'small free list' is empty.

3) It only allocates from "low memory". This is clearly not acceptable for compcache.

In contrast xvmalloc is O(1): do a simple search in two-level bitmap to find freelist containing block of required size. Obviously not O(1) in case it has to go to system page allocator to grow pool.

Also, xvmalloc doesn't dedicate a page to any single size class - so it doesn't suffer from above problems. Note that this might not be good in general - say, in cases where majority of alloc requests are for some select sizes only. But for compcache, this is not true. Also, in our case, there is no correlation between object sizes and object lifetime - so no benefit keeping similar sized objects together. Considering these, there's no point dedicating pages to size classes. Instead, better go for freely mixing these objects to get maximum packing.

...and xvmalloc is not restricted to "low memory".

Thanks,
Nitin

#15 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 2 lines · Nitin Gupta
Quoted 1 line

Slab memory is not backed by vmalloc space.

Oh, it uses "low memory". Still not good for compcache :)

Only if you use 32 bit.

#16 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 7 lines · Christoph Lameter
Quoted 2 lines · Nitin Gupta
Quoted 1 line

Slab memory is not backed by vmalloc space.

Oh, it uses "low memory". Still not good for compcache :)

Only if you use 32 bit.

Yes, this point is for 32-bit only - many users were unhappy with compcache size limit due to small vmalloc area on x86-32.

Nitin

#17 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 2 lines · Nitin Gupta
Quoted 2 lines
Quoted 2 lines
Quoted 1 line

Slab memory is not backed by vmalloc space.

Oh, it uses "low memory". Still not good for compcache :)

Quoted 1 line · Christoph Lameter
Quoted 1 line

Only if you use 32 bit.

Quoted 2 lines · Nitin Gupta

Yes, this point is for 32-bit only - many users were unhappy with compcache size limit due to small vmalloc area on x86-32.

Yeah, I can see the point in having a custom allocator for this. But quite frankly the xvmalloc code is just too ugly to live with. You might want to make it look like kernel code as per CodingStyle and change the name to something less generic.

#18 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 5 lines · Pekka Enberg

Yeah, I can see the point in having a custom allocator for this. But quite frankly the xvmalloc code is just too ugly to live with. You might want to make it look like kernel code as per CodingStyle and change the name to something less generic.

In beginning I also thought CamelCase coding would be a problem. But quite frankly, this is best I could do to beautify xvmalloc code.

I will change it to kernel_style. Maybe that helps.

Thanks,
Nitin

#19 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

In reply to Pekka Enberg
Quoted 8 lines · Pekka Enberg
Quoted 2 lines · Nitin Gupta
Quoted 2 lines
Quoted 2 lines
Quoted 1 line

Slab memory is not backed by vmalloc space.

Oh, it uses "low memory". Still not good for compcache :)

Quoted 1 line · Christoph Lameter
Quoted 1 line

Only if you use 32 bit.

Quoted 9 lines
Quoted 2 lines · Nitin Gupta

Yes, this point is for 32-bit only - many users were unhappy with compcache size limit due to small vmalloc area on x86-32.

Yeah, I can see the point in having a custom allocator for this. But quite frankly the xvmalloc code is just too ugly to live with. You might want to make it look like kernel code as per CodingStyle and change the name to something less generic.

I can see quite some places for cleanups (like macros for reaching next free block etc). Do you think CamelCase will be acceptable for now? and also keeping xvmalloc name? Other than these, I will check for potential cleanups and send updated diffs.

Thanks,
Nitin

#20 lore raw

Re: [PATCH 2/3]: xvmalloc memory allocator

Quoted 4 lines · Nitin Gupta

I can see quite some places for cleanups (like macros for reaching next free block etc). Do you think CamelCase will be acceptable for now? and also keeping xvmalloc name? Other than these, I will check for potential cleanups and send updated diffs.

No, I do not think it is acceptable for core kernel code.

#21 lore raw

PATCH 3/3 : documentation

In reply to Nitin Gupta
 Documentation/blockdev/00-INDEX      |    2 +
 Documentation/blockdev/compcache.txt |   67 ++++++++++++++++++++++++++++++++++
 Documentation/kernel-parameters.txt  |    9 +++++
 3 files changed, 78 insertions(+), 0 deletions(-)

Documentation on how to use compcache module.

---

Documentation/blockdev/00-INDEX +2 -0
index 86f054c..d53dec0 100644
@@ -4,6 +4,8 @@ README.DAC960
 	- info on Mylex DAC960/DAC1100 PCI RAID Controller Driver for Linux.
 cciss.txt
 	- info, major/minor #'s for Compaq's SMART Array Controllers.
+compcache.txt
+	- short guide on how to setup compressed RAM swap device.
 cpqarray.txt
 	- info on using Compaq's SMART2 Intelligent Disk Array Controllers.
 floppy.txt
Documentation/blockdev/compcache.txt new file +67 -0

67 lines not on this page · raw message

Documentation/kernel-parameters.txt +9 -0
index 54f21a5..a23f0ae 100644
@@ -414,6 +414,15 @@ and is between 256 and 4096 characters. It is defined in the file
 			possible to determine what the correct size should be.
 			This option provides an override for these situations.
 
+	compcache.memlimit_kb=
+			See Documentation/blockdev/compcache.txt.
+
+	compcache.disksize_kb=
+			See Documentation/blockdev/compcache.txt.
+
+	compcache.backing_dev=
+			See Documentation/blockdev/compcache.txt.
+
 	security=	[SECURITY] Choose a security module to enable at boot.
 			If this boot parameter is not specified, only the first
 			security module asking for security registration will be
#22 lore raw
In reply to Nitin Gupta
Quoted 12 lines · Nitin Gupta <ngupta <at> vflare.org> writes:

Hi,

Project home: http://code.google.com/p/compcache/

It allows creating a RAM based block device which acts as swap disk. Pages swapped to this device are compressed and stored in memory itself. This is a big win over swapping to slow hard-disk which are typically used as swap disk. For flash, these suffer from wear-leveling issues when used as swap disk - so again its helpful. For swapless systems, it allows more apps to run.

I would recommend making xvmalloc the 1/3 instead of 2/3 so that the commit is bisectable.

I really like this project and I'm especially impressed with how the SSD ATAPI discard command fell in nicely with the discard requirement for compcache.