Skip to contentSkip to conversation

compressed in-memory swapping take4

PATCH In review Nitin Gupta 2 participants 6 messages Mar 29, 2009

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

cover compressed in-memory swapping take4

Hi,

Project home: http://compcache.googlecode.com

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.

* Changelog: take4 vs take3
xvmalloc changes:
- Fixed regression in take3 that caused ramzswap write failures. This happened due to error in find_block() where we did not do explicit cast to 'unsigned long' when checking for bits set in bitmap. Now changed it to use kernel build-in test_bit().
- Fix divide by zero error in proc read function.
ramzswap changes:
- Forward write requests to backing swap device if allocation for compressed page fails.
- Code cleanups.

(Please also see testing notes below).

* Changelog: take3 vs take2
xvmalloc changes:
- Use kernel defined macros and constants in xvmalloc and remove equivalent defines for ALIGN, roundup etc.
- Use kernel bitops (set_bit, clear_bit)
- Moved it to drivers/block since its not clear if it has any other user.
ramzswap changes:
- All instances of compcache renamed to ramzswap.
Also renamed module to ramzswap
- Renamed "backing_dev" parameter to "backing_swap"
- Documentation changes to reflect above changes.
- Remove "table index" from object header (4 bytes). This will be needed when memory defragmentation is implemented. So, avoid this (small) overhead for now.

* Changelog: take2 vs initial revision:
xvmalloc changes:
- Use Linux kernel coding style for xvmalloc
- Collapse all individual flag test/set/get to generic {test_set_get}_flag
- Added BLOCK_NEXT() macro to reach next contiguous block
- Other minor cleanups - no functional changes
compcache block device code:
- compcache core changes due to change in xvmalloc interface names

* Testing notes:
- Multiple cycles of 'scan' benchmark available at:
http://linux-mm.org/PageReplacementTesting
It does scans of anonymous mapped memory, both cyclic and use once.

Config:
Arch: x86 and x64
CPUs: 1/2, RAM: 512MB
backing swap: 768MB, ramzswap memlimit: 76MB (15% of RAM).

Continuously run 'scan' till it triggers 200K R/W operations on ramzswap. Any incompressible pages were correctly forwarded to backing swap device.
cmd: ./scan 450 20 # scan over 450MB, 20 times.

- Links to more performance numbers, use cases can be found at:
http://lkml.org/lkml/2009/3/17/116

Thanks to Ed Tomlinson for reporting bug in 'take3' patches and to reviewers of previous versions.

Thanks,
Nitin

#1 lore raw

PATCH 1/3 xvmalloc memory allocator

 drivers/block/xvmalloc.c     |  563 ++++++++++++++++++++++++++++++++++++++++++
 drivers/block/xvmalloc.h     |   27 ++
 drivers/block/xvmalloc_int.h |   86 +++++++
 3 files changed, 676 insertions(+), 0 deletions(-)

xvmalloc is a memory allocator designed specifically for ramzswap 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). Creating various kmem_caches can reduce space efficiency gap but still problem of being limited to low memory exists. Also, it depends on allocating higher order pages to reduce fragmentation - this is not acceptable for ramzswap as it is used under memory crunch (its a swap device!).

SLOB allocator could not be used do to reasons mentioned here:
http://lkml.org/lkml/2009/3/18/210

* 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

---

drivers/block/xvmalloc.c new file +563 -0
new file mode 100644
index 0000000..1d45cd8
@@ -0,0 +1,563 @@
+/*
+ * xvmalloc.c
+ *
+ * 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 GNU General Public License Version 2.0
+ * Released under the terms of GNU Lesser General Public License Version 2.1
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/bitops.h>
+#include <linux/errno.h>
+#include <linux/highmem.h>
+#include <linux/init.h>
+#include <linux/string.h>
+#include <linux/slab.h>
+
+#include "xvmalloc.h"
+#include "xvmalloc_int.h"
+
+static void stat_inc(u64 *value)
+{
+	(*value)++;
+}
+
+static void stat_dec(u64 *value)
+{
+	(*value)--;
+}
+
+static u32 test_flag(struct block_header *block, enum blockflags flag)
+{
+	return block->prev & (1 << flag);
+}
+
+static void set_flag(struct block_header *block, enum blockflags flag)
+{
+	block->prev |= (1 << flag);
+}
+
+static void clear_flag(struct block_header *block, enum blockflags flag)
+{
+	block->prev &= ~(1 << flag);
+}
+
+static u32 get_blockprev(struct block_header *block)
+{
+	return block->prev & PREV_MASK;
+}
+
+static void set_blockprev(struct block_header *block, u16 new_offset)
+{
+	block->prev = new_offset | (block->prev & FLAGS_MASK);
+}
+
+static struct block_header *BLOCK_NEXT(struct block_header *block)
+{
+	return (struct block_header *)((char *)block + block->size + XV_ALIGN);
+}
+
+/*
+ * Get index of free list containing blocks of maximum size
+ * which is less than or equal to given size.
+ */
+static u32 get_index_for_insert(u32 size)
+{
+	size = size > XV_MAX_ALLOC_SIZE ? XV_MAX_ALLOC_SIZE : size;
+	size &= ~FL_DELTA_MASK;
+	return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT;
+}
+
+/*
+ * Get index of free list having blocks of size greater than
+ * or equal to requested size.
+ */
+static u32 get_index(u32 size)
+{
+	size = (size + FL_DELTA_MASK) & ~FL_DELTA_MASK;
+	return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT;
+}
+
+/*
+ * Given <pagenum, offset> pair, provide a derefrencable pointer.
+ * This is called from xv_malloc/xv_free path, so it needs to be fast.
+ */
+static void *get_ptr_atomic(u32 pagenum, u16 offset, enum km_type type)
+{
+	unsigned char *base;
+
+	base = kmap_atomic(pfn_to_page(pagenum), type);
+	return base + offset;
+}
+
+static void put_ptr_atomic(void *ptr, enum km_type type)
+{
+	kunmap_atomic(ptr, type);
+}
+
+/*
+ * Allocate a memory page. Called when a pool needs to grow.
+ */
+static u32 xv_alloc_page(void)
+{
+	struct page *page;
+
+	page = alloc_page(GFP_NOIO | __GFP_HIGHMEM);
+	if (unlikely(!page))
+		return 0;
+
+	return page_to_pfn(page);
+}
+
+/*
+ * Called when all objects in a page are freed.
+ */
+static void xv_free_page(u32 pagenum)
+{
+	__free_page(pfn_to_page(pagenum));
+}
+
+/**
+ * find_block - find block of at least given size
+ * @pool: memory pool to search from
+ * @size: size of block required
+ * @pagenum: page no. containing required block
+ * @offset: offset within the page where block is located.
+ *
+ * Searches two level bitmap to locate block of at least
+ * the given size. If such a block is found, it provides
+ * <pagenum, offset> to identify this block and returns index
+ * in freelist where we found this block.
+ * Otherwise, returns 0 and <pagenum, offset> params are not touched.
+ */
+static u32 find_block(struct xv_pool *pool, u32 size,
+			u32 *pagenum, u32 *offset)
+{
+	ulong flbitmap, slbitmap;
+	u32 flindex, slindex, slbitstart;
+
+	/* There are no free blocks in this pool */
+	if (!pool->flbitmap)
+		return 0;
+
+	if (unlikely(size < XV_MIN_ALLOC_SIZE))
+		size = XV_MIN_ALLOC_SIZE;
+
+	/* Get freelist index correspoding to this size */
+	slindex = get_index(size);
+	slbitmap = pool->slbitmap[slindex / BITS_PER_LONG];
+	slbitstart = slindex % BITS_PER_LONG;
+
+	/*
+	 * If freelist is not empty at this index, we found the
+	 * block - head of this list. This is approximate best-fit match.
+	 */
+	if (test_bit(slbitstart, &slbitmap)) {
+		*pagenum = pool->freelist[slindex].pagenum;
+		*offset = pool->freelist[slindex].offset;
+		return slindex;
+	}
+
+	/*
+	 * No best-fit found. Search a bit further in bitmap for a free block.
+	 * Second level bitmap consists of series of 32-bit chunks. Search
+	 * further in the chunk where we expected a best-fit, starting from
+	 * index location found above.
+	 */
+	slbitstart++;
+	slbitmap >>= slbitstart;
+
+	/* Skip this search if we were already at end of this bitmap chunk */
+	if ((slbitstart != BITS_PER_LONG) && slbitmap) {
+		slindex += __ffs(slbitmap) + 1;
+		*pagenum = pool->freelist[slindex].pagenum;
+		*offset = pool->freelist[slindex].offset;
+		return slindex;
+	}
+
+	/* Now do a full two-level bitmap search to find next nearest fit */
+	flindex = slindex / BITS_PER_LONG;
+
+	flbitmap = (pool->flbitmap) >> (flindex + 1);
+	if (!flbitmap)
+		return 0;
+
+	flindex += __ffs(flbitmap) + 1;
+	slbitmap = pool->slbitmap[flindex];
+	slindex = (flindex * BITS_PER_LONG) + __ffs(slbitmap);
+	*pagenum = pool->freelist[slindex].pagenum;
+	*offset = pool->freelist[slindex].offset;
+
+	return slindex;
+}
+
+/*
+ * Insert block at <pagenum, offset> in freelist of given pool.
+ * freelist used depends on block size.
+ */
+static void insert_block(struct xv_pool *pool, u32 pagenum, u32 offset,
+			struct block_header *block)
+{
+	u32 flindex, slindex;
+	struct block_header *nextblock;
+
+	slindex = get_index_for_insert(block->size);
+	flindex = slindex / BITS_PER_LONG;
+
+	block->link.prev_pagenum = 0;
+	block->link.prev_offset = 0;
+	block->link.next_pagenum = pool->freelist[slindex].pagenum;
+	block->link.next_offset = pool->freelist[slindex].offset;
+	pool->freelist[slindex].pagenum = pagenum;
+	pool->freelist[slindex].offset = offset;
+
+	if (block->link.next_pagenum) {
+		nextblock = get_ptr_atomic(block->link.next_pagenum,
+					block->link.next_offset, KM_USER1);
+		nextblock->link.prev_pagenum = pagenum;
+		nextblock->link.prev_offset = offset;
+		put_ptr_atomic(nextblock, KM_USER1);
+	}
+
+	__set_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]);
+	__set_bit(flindex, &pool->flbitmap);
+}
+
+/*
+ * Remove block from head of freelist. Index 'slindex' identifies the freelist.
+ */
+static void remove_block_head(struct xv_pool *pool,
+			struct block_header *block, u32 slindex)
+{
+	struct block_header *tmpblock;
+	u32 flindex = slindex / BITS_PER_LONG;
+
+	pool->freelist[slindex].pagenum = block->link.next_pagenum;
+	pool->freelist[slindex].offset = block->link.next_offset;
+	block->link.prev_pagenum = 0;
+	block->link.prev_offset = 0;
+
+	if (!pool->freelist[slindex].pagenum) {
+		__clear_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]);
+		if (!pool->slbitmap[flindex])
+			__clear_bit(flindex, &pool->flbitmap);
+	} else {
+		/*
+		 * DEBUG ONLY: We need not reinitialize freelist head previous
+		 * pointer to 0 - we never depend on its value. But just for
+		 * sanity, lets do it.
+		 */
+		tmpblock = get_ptr_atomic(pool->freelist[slindex].pagenum,
+				pool->freelist[slindex].offset, KM_USER1);
+		tmpblock->link.prev_pagenum = 0;
+		tmpblock->link.prev_offset = 0;
+		put_ptr_atomic(tmpblock, KM_USER1);
+	}
+}
+
+/*
+ * Remove block from freelist. Index 'slindex' identifies the freelist.
+ */
+static void remove_block(struct xv_pool *pool, u32 pagenum, u32 offset,
+			struct block_header *block, u32 slindex)
+{
+	u32 flindex;
+	struct block_header *tmpblock;
+
+	if (pool->freelist[slindex].pagenum == pagenum
+	   && pool->freelist[slindex].offset == offset) {
+		remove_block_head(pool, block, slindex);
+		return;
+	}
+
+	flindex = slindex / BITS_PER_LONG;
+
+	if (block->link.prev_pagenum) {
+		tmpblock = get_ptr_atomic(block->link.prev_pagenum,
+				block->link.prev_offset, KM_USER1);
+		tmpblock->link.next_pagenum = block->link.next_pagenum;
+		tmpblock->link.next_offset = block->link.next_offset;
+		put_ptr_atomic(tmpblock, KM_USER1);
+	}
+
+	if (block->link.next_pagenum) {
+		tmpblock = get_ptr_atomic(block->link.next_pagenum,
+				block->link.next_offset, KM_USER1);
+		tmpblock->link.prev_pagenum = block->link.prev_pagenum;
+		tmpblock->link.prev_offset = block->link.prev_offset;
+		put_ptr_atomic(tmpblock, KM_USER1);
+	}
+
+	return;
+}
+
+/*
+ * Allocate a page and add it freelist of given pool.
+ */
+static int grow_pool(struct xv_pool *pool)
+{
+	u32 pagenum;
+	struct block_header *block;
+
+	pagenum = xv_alloc_page();
+	if (unlikely(!pagenum))
+		return -ENOMEM;
+
+	stat_inc(&pool->total_pages);
+
+	spin_lock(&pool->lock);
+	block = get_ptr_atomic(pagenum, 0, KM_USER0);
+
+	block->size = PAGE_SIZE - XV_ALIGN;
+	set_flag(block, BLOCK_FREE);
+	clear_flag(block, PREV_FREE);
+	set_blockprev(block, 0);
+
+	insert_block(pool, pagenum, 0, block);
+
+	put_ptr_atomic(block, KM_USER0);
+	spin_unlock(&pool->lock);
+
+	return 0;
+}
+
+/*
+ * Create a memory pool. Allocates freelist, bitmaps and other
+ * per-pool metadata.
+ */
+struct xv_pool *xv_create_pool(void)
+{
+	int i;
+	u32 ovhd_size;
+	struct xv_pool *pool;
+
+	ovhd_size = roundup(sizeof(*pool), PAGE_SIZE);
+	pool = kmalloc(ovhd_size, GFP_KERNEL);
+	if (!pool)
+		return NULL;
+
+	memset(pool, 0, ovhd_size);
+
+	for (i = 0; i < NUM_FREE_LISTS; i++) {
+		pool->freelist[i].pagenum = 0;
+		pool->freelist[i].offset = 0;
+	}
+
+	spin_lock_init(&pool->lock);
+
+	return pool;
+}
+EXPORT_SYMBOL_GPL(xv_create_pool);
+
+void xv_destroy_pool(struct xv_pool *pool)
+{
+	kfree(pool);
+}
+EXPORT_SYMBOL_GPL(xv_destroy_pool);
+
+/**
+ * xvMalloc - Allocate block of given size from pool.
+ * @pool: pool to allocate from
+ * @size: size of block to allocate
+ * @pagenum: page no. that holds the object
+ * @offset: location of object within pagenum
+ *
+ * On success, <pagenum, offset> identifies block allocated
+ * and 0 is returned. On failure, <pagenum, offset> is set to
+ * 0 and -ENOMEM is returned.
+ *
+ * Allocation requests with size > XV_MAX_ALLOC_SIZE will fail.
+ */
+int xv_malloc(struct xv_pool *pool, u32 size, u32 *pagenum, u32 *offset)
+{
+	int error;
+	u32 index, tmpsize, origsize, tmpoffset;
+	struct block_header *block, *tmpblock = NULL;
+
+	*pagenum = 0;
+	*offset = 0;
+	origsize = size;
+
+	if (unlikely(!size || size > XV_MAX_ALLOC_SIZE))
+		return -ENOMEM;
+
+	if (unlikely(size < XV_MIN_ALLOC_SIZE))
+		size = XV_MIN_ALLOC_SIZE;
+	else
+		size = ALIGN(size, XV_ALIGN);
+
+	spin_lock(&pool->lock);
+
+	index = find_block(pool, size, pagenum, offset);
+
+	if (!*pagenum) {
+		spin_unlock(&pool->lock);
+		error = grow_pool(pool);
+		if (unlikely(error))
+			return -ENOMEM;
+
+		spin_lock(&pool->lock);
+		index = find_block(pool, size, pagenum, offset);
+	}
+
+	if (!*pagenum) {
+		spin_unlock(&pool->lock);
+		return -ENOMEM;
+	}
+
+	block = get_ptr_atomic(*pagenum, *offset, KM_USER0);
+
+	remove_block_head(pool, block, index);
+
+	/* Split the block if required */
+	tmpoffset = *offset + size + XV_ALIGN;
+	tmpsize = block->size - size;
+	tmpblock = (struct block_header *)((char *)block + size + XV_ALIGN);
+	if (tmpsize) {
+		tmpblock->size = tmpsize - XV_ALIGN;
+		set_flag(tmpblock, BLOCK_FREE);
+		clear_flag(tmpblock, PREV_FREE);
+
+		set_blockprev(tmpblock, *offset);
+		if (tmpblock->size >= XV_MIN_ALLOC_SIZE)
+			insert_block(pool, *pagenum, tmpoffset, tmpblock);
+
+		if (tmpoffset + XV_ALIGN + tmpblock->size < PAGE_SIZE) {
+			tmpblock = BLOCK_NEXT(tmpblock);
+			set_blockprev(tmpblock, tmpoffset);
+		}
+	} else {
+		/* This block is exact fit */
+		if (tmpoffset < PAGE_SIZE)
+			clear_flag(tmpblock, PREV_FREE);
+	}
+
+	block->size = origsize;
+	clear_flag(block, BLOCK_FREE);
+
+	put_ptr_atomic(block, KM_USER0);
+	spin_unlock(&pool->lock);
+
+	*offset += XV_ALIGN;
+
+	return 0;
+}
+EXPORT_SYMBOL_GPL(xv_malloc);
+
+/*
+ * Free block identified with <pagenum, offset>
+ */
+void xv_free(struct xv_pool *pool, u32 pagenum, u32 offset)
+{
+	void *page;
+	struct block_header *block, *tmpblock;
+
+	offset -= XV_ALIGN;
+
+	spin_lock(&pool->lock);
+
+	page = get_ptr_atomic(pagenum, 0, KM_USER0);
+	block = (struct block_header *)((char *)page + offset);
+
+	if (unlikely(block->size < XV_MIN_ALLOC_SIZE))
+		block->size = XV_MIN_ALLOC_SIZE;
+	else
+		block->size = ALIGN(block->size, XV_ALIGN);
+
+	tmpblock = BLOCK_NEXT(block);
+	if (offset + block->size + XV_ALIGN == PAGE_SIZE)
+		tmpblock = NULL;
+
+	/* Merge next block if its free */
+	if (tmpblock && test_flag(tmpblock, BLOCK_FREE)) {
+		/*
+		 * Blocks smaller than XV_MIN_ALLOC_SIZE
+		 * are not inserted in any free list.
+		 */
+		if (tmpblock->size >= XV_MIN_ALLOC_SIZE) {
+			remove_block(pool, pagenum,
+				    offset + block->size + XV_ALIGN, tmpblock,
+				    get_index_for_insert(tmpblock->size));
+		}
+		block->size += tmpblock->size + XV_ALIGN;
+	}
+
+	/* Merge previous block if its free */
+	if (test_flag(block, PREV_FREE)) {
+		tmpblock = (struct block_header *)((char *)(page) +
+						get_blockprev(block));
+		offset = offset - tmpblock->size - XV_ALIGN;
+
+		if (tmpblock->size >= XV_MIN_ALLOC_SIZE)
+			remove_block(pool, pagenum, offset, tmpblock,
+				    get_index_for_insert(tmpblock->size));
+
+		tmpblock->size += block->size + XV_ALIGN;
+		block = tmpblock;
+	}
+
+	/* No used objects in this page. Free it. */
+	if (block->size == PAGE_SIZE - XV_ALIGN) {
+		put_ptr_atomic(page, KM_USER0);
+		spin_unlock(&pool->lock);
+
+		xv_free_page(pagenum);
+		stat_dec(&pool->total_pages);
+		return;
+	}
+
+	set_flag(block, BLOCK_FREE);
+	insert_block(pool, pagenum, offset, block);
+
+	if (offset + block->size < PAGE_SIZE - XV_ALIGN) {
+		tmpblock = BLOCK_NEXT(block);
+		set_flag(tmpblock, PREV_FREE);
+		set_blockprev(tmpblock, offset);
+	}
+
+	put_ptr_atomic(page, KM_USER0);
+	spin_unlock(&pool->lock);
+
+	return;
+}
+EXPORT_SYMBOL_GPL(xv_free);
+
+u32 xv_get_object_size(void *obj)
+{
+	struct block_header *blk;
+
+	blk = (struct block_header *)((char *)(obj) - XV_ALIGN);
+	return blk->size;
+}
+EXPORT_SYMBOL_GPL(xv_get_object_size);
+
+/*
+ * Returns total memory used by allocator (userdata + metadata)
+ */
+u64 xv_get_total_size_bytes(struct xv_pool *pool)
+{
+	return pool->total_pages << PAGE_SHIFT;
+}
+EXPORT_SYMBOL_GPL(xv_get_total_size_bytes);
+
+static int __init xv_malloc_init(void)
+{
+	return 0;
+}
+
+static void __exit xv_malloc_exit(void)
+{
+	return;
+}
+
+module_init(xv_malloc_init);
+module_exit(xv_malloc_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Nitin Gupta <[email protected]>");
+MODULE_DESCRIPTION("xvmalloc memory allocator");
drivers/block/xvmalloc.h new file +27 -0
new file mode 100644
index 0000000..da21872
@@ -0,0 +1,27 @@
+/*
+ * 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 GNU General Public License Version 2.0
+ * Released under the terms of GNU Lesser General Public License Version 2.1
+ */
+
+#ifndef _XVMALLOC_H_
+#define _XVMALLOC_H_
+
+struct xv_pool;
+
+struct xv_pool *xv_create_pool(void);
+void xv_destroy_pool(struct xv_pool *pool);
+
+int xv_malloc(struct xv_pool *pool, u32 size, u32 *pagenum, u32 *offset);
+void xv_free(struct xv_pool *pool, u32 pagenum, u32 offset);
+
+u32 xv_get_object_size(void *obj);
+u64 xv_get_total_size_bytes(struct xv_pool *pool);
+
+#endif
drivers/block/xvmalloc_int.h new file +86 -0

86 lines not on this page · raw message

#2 lore raw

Re: [PATCH 1/3] xvmalloc memory allocator

drivers/block/xvmalloc.c line 33

Quoted 9 lines · Nitin Gupta
drivers/block/xvmalloc.c new file +9 -0
+static void stat_inc(u64 *value)
+{
+    (*value)++;
+}
+
+static void stat_dec(u64 *value)
+{
+    (*value)--;
+}

Why not open code it?

Quoted 5 lines
drivers/block/xvmalloc.c new file +5 -0
+
+static u32 test_flag(struct block_header *block, enum blockflags flag)
+{
+    return block->prev & (1 << flag);
+}

drivers/block/xvmalloc.c line 48

Quoted 10 lines
drivers/block/xvmalloc.c new file +10 -0
+
+static void set_flag(struct block_header *block, enum blockflags flag)
+{
+    block->prev |= (1 << flag);
+}
+
+static void clear_flag(struct block_header *block, enum blockflags flag)
+{
+    block->prev &= ~(1 << flag);
+}

Why don't you use test_bit / __set_bit / __clear_bit directly?

drivers/block/xvmalloc.c line 344

Quoted 12 lines
drivers/block/xvmalloc.c new file +12 -0
+struct xv_pool *xv_create_pool(void)
+{
+    int i;
+    u32 ovhd_size;
+    struct xv_pool *pool;
+
+    ovhd_size = roundup(sizeof(*pool), PAGE_SIZE);
+    pool = kmalloc(ovhd_size, GFP_KERNEL);
+    if (!pool)
+        return NULL;
+
+    memset(pool, 0, ovhd_size);

Please use kzalloc.

drivers/block/xvmalloc.c line 349

Quoted 5 lines
drivers/block/xvmalloc.c new file +5 -0
+
+    for (i = 0; i < NUM_FREE_LISTS; i++) {
+        pool->freelist[i].pagenum = 0;
+        pool->freelist[i].offset = 0;
+    }

It was already zeroed by memset.

Quoted 7 lines
drivers/block/xvmalloc.c new file +7 -0
+
+    spin_lock_init(&pool->lock);
+
+    return pool;
+}
+EXPORT_SYMBOL_GPL(xv_create_pool);
+
#3 lore raw

Re: [PATCH 1/3] xvmalloc memory allocator

Quoted 13 lines · Marcin Slusarz

drivers/block/xvmalloc.c line 33

Quoted 9 lines · Nitin Gupta
drivers/block/xvmalloc.c new file +9 -0
+static void stat_inc(u64 *value)
+{
+    (*value)++;
+}
+
+static void stat_dec(u64 *value)
+{
+    (*value)--;
+}

Why not open code it?

This looks nicer, doesn't it?

Quoted 9 lines
Quoted 9 lines
drivers/block/xvmalloc.c new file +9 -0
+
+static u32 test_flag(struct block_header *block, enum blockflags flag)
+{
+    return block->prev & (1 << flag);
+}
+
+static void set_flag(struct block_header *block, enum blockflags flag)
+{
+    block->prev |= (1 << flag);
Quoted 9 lines

drivers/block/xvmalloc.c line 48

Quoted 6 lines
drivers/block/xvmalloc.c new file +6 -0
+}
+
+static void clear_flag(struct block_header *block, enum blockflags flag)
+{
+    block->prev &= ~(1 << flag);
+}

Why don't you use test_bit / __set_bit / __clear_bit directly?

block->prev is 16 bits. __set_bit() etc. need unsigned long pointer.

Quoted 6 lines
Quoted 6 lines
drivers/block/xvmalloc.c new file +6 -0
+struct xv_pool *xv_create_pool(void)
+{
+    int i;
+    u32 ovhd_size;
+    struct xv_pool *pool;
+
Quoted 9 lines

drivers/block/xvmalloc.c line 344

Quoted 6 lines
drivers/block/xvmalloc.c new file +6 -0
+    ovhd_size = roundup(sizeof(*pool), PAGE_SIZE);
+    pool = kmalloc(ovhd_size, GFP_KERNEL);
+    if (!pool)
+        return NULL;
+
+    memset(pool, 0, ovhd_size);

Please use kzalloc.

Ok...

Quoted 8 lines

drivers/block/xvmalloc.c line 349

Quoted 5 lines
drivers/block/xvmalloc.c new file +5 -0
+
+    for (i = 0; i < NUM_FREE_LISTS; i++) {
+        pool->freelist[i].pagenum = 0;
+        pool->freelist[i].offset = 0;
+    }

It was already zeroed by memset.

Remains from earlier code; we used to set it to 'INVALID_PGNUM'. Ok, will remove this.

Thanks for review.
Nitin

#4 lore raw

PATCH 2/3 ramzswap virtual block device

In reply to Nitin Gupta
 drivers/block/Kconfig    |   24 ++
 drivers/block/Makefile   |    1 +
 drivers/block/ramzswap.c |  991 ++++++++++++++++++++++++++++++++++++++++++++++
 drivers/block/ramzswap.h |  160 ++++++++
 4 files changed, 1176 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 ramzswap.ko. It depends on:
- xvmalloc.ko: memory allocator
- lzo_compress.ko
- lzo_decompress.ko

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

Project home: http://compcache.googlecode.com

---

drivers/block/Kconfig +24 -0
index e7b8aa0..33fee91 100644
@@ -355,6 +355,30 @@ config BLK_DEV_RAM_SIZE
 	  The default value is 4096 kilobytes. Only change this if you know
 	  what you are doing.
 
+config BLK_DEV_RAMZSWAP
+	tristate "Compressed RAM swap device"
+	select LZO_COMPRESS
+	select LZO_DECOMPRESS
+	help
+	  Saying Y here will allow you to use in-memory compressed swapping.
+	  It creates a pseudo block device (named ramzswap0) which acts as
+	  swap device. Pages swapped to this device are compressed and stored
+	  in memory itself.
+
+	  Project home: http://compcache.googlecode.com
+	  For details, read <file:Documentation/blockdev/ramzswap.txt>
+
+	  To compile this driver as a module, choose M here: the
+	  module will be called ramzswap.
+
+config BLK_DEV_RAMZSWAP_STATS
+	bool "Collect statistics"
+	depends on BLK_DEV_RAMZSWAP
+	default y
+	help
+	  If enabled, ramzswap statistics are available via /proc/ramzswap.
+	  If unsure, say Y.
+
 config BLK_DEV_XIP
 	bool "Support XIP filesystems on RAM block device"
 	depends on BLK_DEV_RAM
drivers/block/Makefile +1 -0
index 3145141..647a9e1 100644
@@ -14,6 +14,7 @@ obj-$(CONFIG_PS3_VRAM)		+= ps3vram.o
 obj-$(CONFIG_ATARI_FLOPPY)	+= ataflop.o
 obj-$(CONFIG_AMIGA_Z2RAM)	+= z2ram.o
 obj-$(CONFIG_BLK_DEV_RAM)	+= brd.o
+obj-$(CONFIG_BLK_DEV_RAMZSWAP)	+= ramzswap.o xvmalloc.o
 obj-$(CONFIG_BLK_DEV_LOOP)	+= loop.o
 obj-$(CONFIG_BLK_DEV_XD)	+= xd.o
 obj-$(CONFIG_BLK_CPQ_DA)	+= cpqarray.o
drivers/block/ramzswap.c new file +991 -0

991 lines not on this page · raw message

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

160 lines not on this page · raw message

#5 lore raw

PATCH 3/3 ramzswap documentation

In reply to Nitin Gupta
 Documentation/blockdev/ramzswap.txt |   67 +++++++++++++++++++++++++++++++++++
 Documentation/kernel-parameters.txt |    9 +++++
 2 files changed, 76 insertions(+), 0 deletions(-)

Documentation on how to use ramzswap module.

---

Documentation/blockdev/ramzswap.txt new file +67 -0
new file mode 100644
index 0000000..835afcf
@@ -0,0 +1,67 @@
+ramzswap: Compressed RAM swap device
+------------------------------------
+
+Project home: http://compcache.googlecode.com
+
+This module creates RAM based block device (named ramzswap0) which acts
+as swap disk. Pages swapped to this disk are compressed and stored in
+memory itself.
+
+It uses these components:
+ - xvMalloc: memory allocator (xvmalloc.ko)
+ - LZO1X: de/compressor: (lzo_compress.ko, lzo_decompress.ko)
+
+Usage:
+ - modprobe ramzswap [memlimit_kb=<val>|disksize_kb=<val>] [backing_swap=<dev>]
+
+   memlimit_kb: This param is applicable only when backing_swap is given.
+	It is limit on amount compressed data stored in memory. Any
+	additional data is forwarded to backing_swap. It cannot be greater
+	than backing device size. If missing or 0, default value is used:
+	15% of RAM or backing device size, whichever is smaller.
+
+   disksize_kb: This param is applicable only when backing_swap is not given.
+	It is limit on amount of *uncompressed* worth of data stored in
+	memory. For e.g. disksize_kb=1024 means it can hold 1024kb worth of
+	uncompressed data even if this data compresses to just, say, 100kb.
+	If missing or 0, default value is used: 25% of RAM.
+
+   backing_swap: This is block device to be used as backing store for ramzswap.
+	It must be a valid swap partition. We move data to this device when we
+	encounter incompressible page or memlimit is reached. TODO: we may also
+	move some pages from ramzswap to this device in case system is really
+	low on memory.
+	This device is not directly visible to kernel as a swap device
+	(/proc/swaps will only show /dev/ramzswap0 and not this device).
+	Managing this backing device is the job of ramzswap module.
+
+Examples:
+	1) modprobe ramzswap memlimit_kb=10240 backing_swap=/dev/sda2
+	sets ramzswap limit as 10MB and /dev/sda2 as backing swap device.
+	NOTE: here /dev/sda2 is a valid swap partition.
+
+	2) modprobe ramzswap backing_swap=/dev/sda2
+	same as (1) but memlimit is set to default: 15% of RAM or size of
+	backing swap device, whichever is smaller.
+
+	3) modprobe ramzswap disksize_kb=10240
+	sets ramzswap disk size as 10MB.
+
+	4) modprobe ramzswap.ko
+	same as (3) but ramzswap disk size will be set to default:
+	25% of RAM size.
+
+	Once module is loaded, activate this swap with highest priority:
+	swapon /dev/ramzswap0 -p 100
+	(-p param set swap priority)
+
+Notes:
+ - ramzswap stats are exported via /proc/ramzswap
+ - If you give non-swap partition as backing_swap, nothing bad will happen -
+   swapon will simply fail to recognize /dev/ramzswap0 as swap partition.
+   So, in this case, unload the module and reload with correct backing_swap.
+
+Please report any problems to:
+
+Nitin Gupta
[email protected]
Documentation/kernel-parameters.txt +9 -0
index fa4e123..d7bcf51 100644
@@ -415,6 +415,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.
 
+	ramzswap.memlimit_kb=
+			See Documentation/blockdev/ramzswap.txt.
+
+	ramzswap.disksize_kb=
+			See Documentation/blockdev/ramzswap.txt.
+
+	ramzswap.backing_swap=
+			See Documentation/blockdev/ramzswap.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