summaryrefslogtreecommitdiff
path: root/drivers/staging/zram
diff options
context:
space:
mode:
authorNitin Gupta <ngupta@vflare.org>2012-01-09 16:52:00 -0600
committerGreg Kroah-Hartman <gregkh@linuxfoundation.org>2012-02-08 17:13:01 -0800
commitb154ff05e1b0d749231a71896c90e38657f8e675 (patch)
treec22f6c908685d5e2cb7c2bdbda05b0b77b3b6746 /drivers/staging/zram
parentfd1a30dea194002c061503af8425688dcc6f3970 (diff)
staging: zram: remove xvmalloc
Removes the xvmalloc allocator code from the zram driver Signed-off-by: Nitin Gupta <ngupta@vflare.org> Acked-by: Seth Jennings <sjenning@linux.vnet.ibm.com> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Diffstat (limited to 'drivers/staging/zram')
-rw-r--r--drivers/staging/zram/xvmalloc.c510
-rw-r--r--drivers/staging/zram/xvmalloc.h30
-rw-r--r--drivers/staging/zram/xvmalloc_int.h95
3 files changed, 0 insertions, 635 deletions
diff --git a/drivers/staging/zram/xvmalloc.c b/drivers/staging/zram/xvmalloc.c
deleted file mode 100644
index 1f9c5082b6d5..000000000000
--- a/drivers/staging/zram/xvmalloc.c
+++ /dev/null
@@ -1,510 +0,0 @@
-/*
- * xvmalloc memory allocator
- *
- * Copyright (C) 2008, 2009, 2010 Nitin Gupta
- *
- * This code is released using a dual license strategy: BSD/GPL
- * You can choose the licence that better fits your requirements.
- *
- * Released under the terms of 3-clause BSD License
- * Released under the terms of GNU General Public License Version 2.0
- */
-
-#ifdef CONFIG_ZRAM_DEBUG
-#define DEBUG
-#endif
-
-#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 = *value + 1;
-}
-
-static void stat_dec(u64 *value)
-{
- *value = *value - 1;
-}
-
-static int test_flag(struct block_header *block, enum blockflags flag)
-{
- return block->prev & BIT(flag);
-}
-
-static void set_flag(struct block_header *block, enum blockflags flag)
-{
- block->prev |= BIT(flag);
-}
-
-static void clear_flag(struct block_header *block, enum blockflags flag)
-{
- block->prev &= ~BIT(flag);
-}
-
-/*
- * Given <page, offset> pair, provide a dereferencable pointer.
- * This is called from xv_malloc/xv_free path, so it
- * needs to be fast.
- */
-static void *get_ptr_atomic(struct page *page, u16 offset, enum km_type type)
-{
- unsigned char *base;
-
- base = kmap_atomic(page, type);
- return base + offset;
-}
-
-static void put_ptr_atomic(void *ptr, enum km_type type)
-{
- kunmap_atomic(ptr, type);
-}
-
-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)
-{
- if (unlikely(size > XV_MAX_ALLOC_SIZE))
- size = XV_MAX_ALLOC_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)
-{
- if (unlikely(size < XV_MIN_ALLOC_SIZE))
- size = XV_MIN_ALLOC_SIZE;
- size = ALIGN(size, FL_DELTA);
- return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT;
-}
-
-/**
- * find_block - find block of at least given size
- * @pool: memory pool to search from
- * @size: size of block required
- * @page: page 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
- * <page, offset> to identify this block and returns index
- * in freelist where we found this block.
- * Otherwise, returns 0 and <page, offset> params are not touched.
- */
-static u32 find_block(struct xv_pool *pool, u32 size,
- struct page **page, u32 *offset)
-{
- ulong flbitmap, slbitmap;
- u32 flindex, slindex, slbitstart;
-
- /* There are no free blocks in this pool */
- if (!pool->flbitmap)
- return 0;
-
- /* 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)) {
- *page = pool->freelist[slindex].page;
- *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;
- *page = pool->freelist[slindex].page;
- *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);
- *page = pool->freelist[slindex].page;
- *offset = pool->freelist[slindex].offset;
-
- return slindex;
-}
-
-/*
- * Insert block at <page, offset> in freelist of given pool.
- * freelist used depends on block size.
- */
-static void insert_block(struct xv_pool *pool, struct page *page, 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_page = NULL;
- block->link.prev_offset = 0;
- block->link.next_page = pool->freelist[slindex].page;
- block->link.next_offset = pool->freelist[slindex].offset;
- pool->freelist[slindex].page = page;
- pool->freelist[slindex].offset = offset;
-
- if (block->link.next_page) {
- nextblock = get_ptr_atomic(block->link.next_page,
- block->link.next_offset, KM_USER1);
- nextblock->link.prev_page = page;
- nextblock->link.prev_offset = offset;
- put_ptr_atomic(nextblock, KM_USER1);
- /* If there was a next page then the free bits are set. */
- return;
- }
-
- __set_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]);
- __set_bit(flindex, &pool->flbitmap);
-}
-
-/*
- * Remove block from freelist. Index 'slindex' identifies the freelist.
- */
-static void remove_block(struct xv_pool *pool, struct page *page, u32 offset,
- struct block_header *block, u32 slindex)
-{
- u32 flindex = slindex / BITS_PER_LONG;
- struct block_header *tmpblock;
-
- if (block->link.prev_page) {
- tmpblock = get_ptr_atomic(block->link.prev_page,
- block->link.prev_offset, KM_USER1);
- tmpblock->link.next_page = block->link.next_page;
- tmpblock->link.next_offset = block->link.next_offset;
- put_ptr_atomic(tmpblock, KM_USER1);
- }
-
- if (block->link.next_page) {
- tmpblock = get_ptr_atomic(block->link.next_page,
- block->link.next_offset, KM_USER1);
- tmpblock->link.prev_page = block->link.prev_page;
- tmpblock->link.prev_offset = block->link.prev_offset;
- put_ptr_atomic(tmpblock, KM_USER1);
- }
-
- /* Is this block is at the head of the freelist? */
- if (pool->freelist[slindex].page == page
- && pool->freelist[slindex].offset == offset) {
-
- pool->freelist[slindex].page = block->link.next_page;
- pool->freelist[slindex].offset = block->link.next_offset;
-
- if (pool->freelist[slindex].page) {
- struct block_header *tmpblock;
- tmpblock = get_ptr_atomic(pool->freelist[slindex].page,
- pool->freelist[slindex].offset,
- KM_USER1);
- tmpblock->link.prev_page = NULL;
- tmpblock->link.prev_offset = 0;
- put_ptr_atomic(tmpblock, KM_USER1);
- } else {
- /* This freelist bucket is empty */
- __clear_bit(slindex % BITS_PER_LONG,
- &pool->slbitmap[flindex]);
- if (!pool->slbitmap[flindex])
- __clear_bit(flindex, &pool->flbitmap);
- }
- }
-
- block->link.prev_page = NULL;
- block->link.prev_offset = 0;
- block->link.next_page = NULL;
- block->link.next_offset = 0;
-}
-
-/*
- * Allocate a page and add it to freelist of given pool.
- */
-static int grow_pool(struct xv_pool *pool, gfp_t flags)
-{
- struct page *page;
- struct block_header *block;
-
- page = alloc_page(flags);
- if (unlikely(!page))
- return -ENOMEM;
-
- stat_inc(&pool->total_pages);
-
- spin_lock(&pool->lock);
- block = get_ptr_atomic(page, 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, page, 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)
-{
- u32 ovhd_size;
- struct xv_pool *pool;
-
- ovhd_size = roundup(sizeof(*pool), PAGE_SIZE);
- pool = kzalloc(ovhd_size, GFP_KERNEL);
- if (!pool)
- return NULL;
-
- 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);
-
-/**
- * xv_malloc - Allocate block of given size from pool.
- * @pool: pool to allocate from
- * @size: size of block to allocate
- * @page: page no. that holds the object
- * @offset: location of object within page
- *
- * On success, <page, offset> identifies block allocated
- * and 0 is returned. On failure, <page, 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, struct page **page,
- u32 *offset, gfp_t flags)
-{
- int error;
- u32 index, tmpsize, origsize, tmpoffset;
- struct block_header *block, *tmpblock;
-
- *page = NULL;
- *offset = 0;
- origsize = size;
-
- if (unlikely(!size || size > XV_MAX_ALLOC_SIZE))
- return -ENOMEM;
-
- size = ALIGN(size, XV_ALIGN);
-
- spin_lock(&pool->lock);
-
- index = find_block(pool, size, page, offset);
-
- if (!*page) {
- spin_unlock(&pool->lock);
- if (flags & GFP_NOWAIT)
- return -ENOMEM;
- error = grow_pool(pool, flags);
- if (unlikely(error))
- return error;
-
- spin_lock(&pool->lock);
- index = find_block(pool, size, page, offset);
- }
-
- if (!*page) {
- spin_unlock(&pool->lock);
- return -ENOMEM;
- }
-
- block = get_ptr_atomic(*page, *offset, KM_USER0);
-
- remove_block(pool, *page, *offset, 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, *page, 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 <page, offset>
- */
-void xv_free(struct xv_pool *pool, struct page *page, u32 offset)
-{
- void *page_start;
- struct block_header *block, *tmpblock;
-
- offset -= XV_ALIGN;
-
- spin_lock(&pool->lock);
-
- page_start = get_ptr_atomic(page, 0, KM_USER0);
- block = (struct block_header *)((char *)page_start + offset);
-
- /* Catch double free bugs */
- BUG_ON(test_flag(block, BLOCK_FREE));
-
- 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, page,
- 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_start) +
- get_blockprev(block));
- offset = offset - tmpblock->size - XV_ALIGN;
-
- if (tmpblock->size >= XV_MIN_ALLOC_SIZE)
- remove_block(pool, page, 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_start, KM_USER0);
- spin_unlock(&pool->lock);
-
- __free_page(page);
- stat_dec(&pool->total_pages);
- return;
- }
-
- set_flag(block, BLOCK_FREE);
- if (block->size >= XV_MIN_ALLOC_SIZE)
- insert_block(pool, page, offset, block);
-
- if (offset + block->size + XV_ALIGN != PAGE_SIZE) {
- tmpblock = BLOCK_NEXT(block);
- set_flag(tmpblock, PREV_FREE);
- set_blockprev(tmpblock, offset);
- }
-
- put_ptr_atomic(page_start, KM_USER0);
- spin_unlock(&pool->lock);
-}
-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);
diff --git a/drivers/staging/zram/xvmalloc.h b/drivers/staging/zram/xvmalloc.h
deleted file mode 100644
index 5b1a81aa5faf..000000000000
--- a/drivers/staging/zram/xvmalloc.h
+++ /dev/null
@@ -1,30 +0,0 @@
-/*
- * xvmalloc memory allocator
- *
- * Copyright (C) 2008, 2009, 2010 Nitin Gupta
- *
- * This code is released using a dual license strategy: BSD/GPL
- * You can choose the licence that better fits your requirements.
- *
- * Released under the terms of 3-clause BSD License
- * Released under the terms of GNU General Public License Version 2.0
- */
-
-#ifndef _XV_MALLOC_H_
-#define _XV_MALLOC_H_
-
-#include <linux/types.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, struct page **page,
- u32 *offset, gfp_t flags);
-void xv_free(struct xv_pool *pool, struct page *page, u32 offset);
-
-u32 xv_get_object_size(void *obj);
-u64 xv_get_total_size_bytes(struct xv_pool *pool);
-
-#endif
diff --git a/drivers/staging/zram/xvmalloc_int.h b/drivers/staging/zram/xvmalloc_int.h
deleted file mode 100644
index b5f1f7febcf6..000000000000
--- a/drivers/staging/zram/xvmalloc_int.h
+++ /dev/null
@@ -1,95 +0,0 @@
-/*
- * xvmalloc memory allocator
- *
- * Copyright (C) 2008, 2009, 2010 Nitin Gupta
- *
- * This code is released using a dual license strategy: BSD/GPL
- * You can choose the licence that better fits your requirements.
- *
- * Released under the terms of 3-clause BSD License
- * Released under the terms of GNU General Public License Version 2.0
- */
-
-#ifndef _XV_MALLOC_INT_H_
-#define _XV_MALLOC_INT_H_
-
-#include <linux/kernel.h>
-#include <linux/types.h>
-
-/* User configurable params */
-
-/* Must be power of two */
-#ifdef CONFIG_64BIT
-#define XV_ALIGN_SHIFT 3
-#else
-#define XV_ALIGN_SHIFT 2
-#endif
-#define XV_ALIGN (1 << XV_ALIGN_SHIFT)
-#define XV_ALIGN_MASK (XV_ALIGN - 1)
-
-/* This must be greater than sizeof(link_free) */
-#define XV_MIN_ALLOC_SIZE 32
-#define XV_MAX_ALLOC_SIZE (PAGE_SIZE - XV_ALIGN)
-
-/*
- * Free lists are separated by FL_DELTA bytes
- * This value is 3 for 4k pages and 4 for 64k pages, for any
- * other page size, a conservative (PAGE_SHIFT - 9) is used.
- */
-#if PAGE_SHIFT == 16
-#define FL_DELTA_SHIFT 4
-#else
-#define FL_DELTA_SHIFT (PAGE_SHIFT - 9)
-#endif
-#define FL_DELTA (1 << FL_DELTA_SHIFT)
-#define FL_DELTA_MASK (FL_DELTA - 1)
-#define NUM_FREE_LISTS ((XV_MAX_ALLOC_SIZE - XV_MIN_ALLOC_SIZE) \
- / FL_DELTA + 1)
-
-#define MAX_FLI DIV_ROUND_UP(NUM_FREE_LISTS, BITS_PER_LONG)
-
-/* End of user params */
-
-enum blockflags {
- BLOCK_FREE,
- PREV_FREE,
- __NR_BLOCKFLAGS,
-};
-
-#define FLAGS_MASK XV_ALIGN_MASK
-#define PREV_MASK (~FLAGS_MASK)
-
-struct freelist_entry {
- struct page *page;
- u16 offset;
- u16 pad;
-};
-
-struct link_free {
- struct page *prev_page;
- struct page *next_page;
- u16 prev_offset;
- u16 next_offset;
-};
-
-struct block_header {
- union {
- /* This common header must be XV_ALIGN bytes */
- u8 common[XV_ALIGN];
- struct {
- u16 size;
- u16 prev;
- };
- };
- struct link_free link;
-};
-
-struct xv_pool {
- ulong flbitmap;
- ulong slbitmap[MAX_FLI];
- u64 total_pages; /* stats */
- struct freelist_entry freelist[NUM_FREE_LISTS];
- spinlock_t lock;
-};
-
-#endif