diff options
author | Nitin Gupta <ngupta@vflare.org> | 2010-06-01 04:01:24 -0400 |
---|---|---|
committer | Greg Kroah-Hartman <gregkh@suse.de> | 2010-06-18 15:46:42 -0400 |
commit | 16a4bfb9e9dfefbd28ee170fa3e259bc88d81eb5 (patch) | |
tree | fc8cdc97f97b699c7ed0e0a08eacd5a3b1f3058f /drivers/staging/zram/xvmalloc.c | |
parent | a1dd52afa94238d361d70502b219409ea115e235 (diff) |
Staging: Rename ramzswap files to zram
Related changes:
- Modify revelant Kconfig and Makefile accordingly.
- Change include filenames in code.
- Remove dependency on CONFIG_SWAP in Kconfig as zram usage
is no longer limited to swap disks.
Signed-off-by: Nitin Gupta <ngupta@vflare.org>
Acked-by: Pekka Enberg <penberg@cs.helsinki.fi>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
Diffstat (limited to 'drivers/staging/zram/xvmalloc.c')
-rw-r--r-- | drivers/staging/zram/xvmalloc.c | 507 |
1 files changed, 507 insertions, 0 deletions
diff --git a/drivers/staging/zram/xvmalloc.c b/drivers/staging/zram/xvmalloc.c new file mode 100644 index 00000000000..3fdbb8ada82 --- /dev/null +++ b/drivers/staging/zram/xvmalloc.c | |||
@@ -0,0 +1,507 @@ | |||
1 | /* | ||
2 | * xvmalloc memory allocator | ||
3 | * | ||
4 | * Copyright (C) 2008, 2009, 2010 Nitin Gupta | ||
5 | * | ||
6 | * This code is released using a dual license strategy: BSD/GPL | ||
7 | * You can choose the licence that better fits your requirements. | ||
8 | * | ||
9 | * Released under the terms of 3-clause BSD License | ||
10 | * Released under the terms of GNU General Public License Version 2.0 | ||
11 | */ | ||
12 | |||
13 | #include <linux/bitops.h> | ||
14 | #include <linux/errno.h> | ||
15 | #include <linux/highmem.h> | ||
16 | #include <linux/init.h> | ||
17 | #include <linux/string.h> | ||
18 | #include <linux/slab.h> | ||
19 | |||
20 | #include "xvmalloc.h" | ||
21 | #include "xvmalloc_int.h" | ||
22 | |||
23 | static void stat_inc(u64 *value) | ||
24 | { | ||
25 | *value = *value + 1; | ||
26 | } | ||
27 | |||
28 | static void stat_dec(u64 *value) | ||
29 | { | ||
30 | *value = *value - 1; | ||
31 | } | ||
32 | |||
33 | static int test_flag(struct block_header *block, enum blockflags flag) | ||
34 | { | ||
35 | return block->prev & BIT(flag); | ||
36 | } | ||
37 | |||
38 | static void set_flag(struct block_header *block, enum blockflags flag) | ||
39 | { | ||
40 | block->prev |= BIT(flag); | ||
41 | } | ||
42 | |||
43 | static void clear_flag(struct block_header *block, enum blockflags flag) | ||
44 | { | ||
45 | block->prev &= ~BIT(flag); | ||
46 | } | ||
47 | |||
48 | /* | ||
49 | * Given <page, offset> pair, provide a derefrencable pointer. | ||
50 | * This is called from xv_malloc/xv_free path, so it | ||
51 | * needs to be fast. | ||
52 | */ | ||
53 | static void *get_ptr_atomic(struct page *page, u16 offset, enum km_type type) | ||
54 | { | ||
55 | unsigned char *base; | ||
56 | |||
57 | base = kmap_atomic(page, type); | ||
58 | return base + offset; | ||
59 | } | ||
60 | |||
61 | static void put_ptr_atomic(void *ptr, enum km_type type) | ||
62 | { | ||
63 | kunmap_atomic(ptr, type); | ||
64 | } | ||
65 | |||
66 | static u32 get_blockprev(struct block_header *block) | ||
67 | { | ||
68 | return block->prev & PREV_MASK; | ||
69 | } | ||
70 | |||
71 | static void set_blockprev(struct block_header *block, u16 new_offset) | ||
72 | { | ||
73 | block->prev = new_offset | (block->prev & FLAGS_MASK); | ||
74 | } | ||
75 | |||
76 | static struct block_header *BLOCK_NEXT(struct block_header *block) | ||
77 | { | ||
78 | return (struct block_header *) | ||
79 | ((char *)block + block->size + XV_ALIGN); | ||
80 | } | ||
81 | |||
82 | /* | ||
83 | * Get index of free list containing blocks of maximum size | ||
84 | * which is less than or equal to given size. | ||
85 | */ | ||
86 | static u32 get_index_for_insert(u32 size) | ||
87 | { | ||
88 | if (unlikely(size > XV_MAX_ALLOC_SIZE)) | ||
89 | size = XV_MAX_ALLOC_SIZE; | ||
90 | size &= ~FL_DELTA_MASK; | ||
91 | return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT; | ||
92 | } | ||
93 | |||
94 | /* | ||
95 | * Get index of free list having blocks of size greater than | ||
96 | * or equal to requested size. | ||
97 | */ | ||
98 | static u32 get_index(u32 size) | ||
99 | { | ||
100 | if (unlikely(size < XV_MIN_ALLOC_SIZE)) | ||
101 | size = XV_MIN_ALLOC_SIZE; | ||
102 | size = ALIGN(size, FL_DELTA); | ||
103 | return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT; | ||
104 | } | ||
105 | |||
106 | /** | ||
107 | * find_block - find block of at least given size | ||
108 | * @pool: memory pool to search from | ||
109 | * @size: size of block required | ||
110 | * @page: page containing required block | ||
111 | * @offset: offset within the page where block is located. | ||
112 | * | ||
113 | * Searches two level bitmap to locate block of at least | ||
114 | * the given size. If such a block is found, it provides | ||
115 | * <page, offset> to identify this block and returns index | ||
116 | * in freelist where we found this block. | ||
117 | * Otherwise, returns 0 and <page, offset> params are not touched. | ||
118 | */ | ||
119 | static u32 find_block(struct xv_pool *pool, u32 size, | ||
120 | struct page **page, u32 *offset) | ||
121 | { | ||
122 | ulong flbitmap, slbitmap; | ||
123 | u32 flindex, slindex, slbitstart; | ||
124 | |||
125 | /* There are no free blocks in this pool */ | ||
126 | if (!pool->flbitmap) | ||
127 | return 0; | ||
128 | |||
129 | /* Get freelist index correspoding to this size */ | ||
130 | slindex = get_index(size); | ||
131 | slbitmap = pool->slbitmap[slindex / BITS_PER_LONG]; | ||
132 | slbitstart = slindex % BITS_PER_LONG; | ||
133 | |||
134 | /* | ||
135 | * If freelist is not empty at this index, we found the | ||
136 | * block - head of this list. This is approximate best-fit match. | ||
137 | */ | ||
138 | if (test_bit(slbitstart, &slbitmap)) { | ||
139 | *page = pool->freelist[slindex].page; | ||
140 | *offset = pool->freelist[slindex].offset; | ||
141 | return slindex; | ||
142 | } | ||
143 | |||
144 | /* | ||
145 | * No best-fit found. Search a bit further in bitmap for a free block. | ||
146 | * Second level bitmap consists of series of 32-bit chunks. Search | ||
147 | * further in the chunk where we expected a best-fit, starting from | ||
148 | * index location found above. | ||
149 | */ | ||
150 | slbitstart++; | ||
151 | slbitmap >>= slbitstart; | ||
152 | |||
153 | /* Skip this search if we were already at end of this bitmap chunk */ | ||
154 | if ((slbitstart != BITS_PER_LONG) && slbitmap) { | ||
155 | slindex += __ffs(slbitmap) + 1; | ||
156 | *page = pool->freelist[slindex].page; | ||
157 | *offset = pool->freelist[slindex].offset; | ||
158 | return slindex; | ||
159 | } | ||
160 | |||
161 | /* Now do a full two-level bitmap search to find next nearest fit */ | ||
162 | flindex = slindex / BITS_PER_LONG; | ||
163 | |||
164 | flbitmap = (pool->flbitmap) >> (flindex + 1); | ||
165 | if (!flbitmap) | ||
166 | return 0; | ||
167 | |||
168 | flindex += __ffs(flbitmap) + 1; | ||
169 | slbitmap = pool->slbitmap[flindex]; | ||
170 | slindex = (flindex * BITS_PER_LONG) + __ffs(slbitmap); | ||
171 | *page = pool->freelist[slindex].page; | ||
172 | *offset = pool->freelist[slindex].offset; | ||
173 | |||
174 | return slindex; | ||
175 | } | ||
176 | |||
177 | /* | ||
178 | * Insert block at <page, offset> in freelist of given pool. | ||
179 | * freelist used depends on block size. | ||
180 | */ | ||
181 | static void insert_block(struct xv_pool *pool, struct page *page, u32 offset, | ||
182 | struct block_header *block) | ||
183 | { | ||
184 | u32 flindex, slindex; | ||
185 | struct block_header *nextblock; | ||
186 | |||
187 | slindex = get_index_for_insert(block->size); | ||
188 | flindex = slindex / BITS_PER_LONG; | ||
189 | |||
190 | block->link.prev_page = 0; | ||
191 | block->link.prev_offset = 0; | ||
192 | block->link.next_page = pool->freelist[slindex].page; | ||
193 | block->link.next_offset = pool->freelist[slindex].offset; | ||
194 | pool->freelist[slindex].page = page; | ||
195 | pool->freelist[slindex].offset = offset; | ||
196 | |||
197 | if (block->link.next_page) { | ||
198 | nextblock = get_ptr_atomic(block->link.next_page, | ||
199 | block->link.next_offset, KM_USER1); | ||
200 | nextblock->link.prev_page = page; | ||
201 | nextblock->link.prev_offset = offset; | ||
202 | put_ptr_atomic(nextblock, KM_USER1); | ||
203 | } | ||
204 | |||
205 | __set_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]); | ||
206 | __set_bit(flindex, &pool->flbitmap); | ||
207 | } | ||
208 | |||
209 | /* | ||
210 | * Remove block from head of freelist. Index 'slindex' identifies the freelist. | ||
211 | */ | ||
212 | static void remove_block_head(struct xv_pool *pool, | ||
213 | struct block_header *block, u32 slindex) | ||
214 | { | ||
215 | struct block_header *tmpblock; | ||
216 | u32 flindex = slindex / BITS_PER_LONG; | ||
217 | |||
218 | pool->freelist[slindex].page = block->link.next_page; | ||
219 | pool->freelist[slindex].offset = block->link.next_offset; | ||
220 | block->link.prev_page = 0; | ||
221 | block->link.prev_offset = 0; | ||
222 | |||
223 | if (!pool->freelist[slindex].page) { | ||
224 | __clear_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]); | ||
225 | if (!pool->slbitmap[flindex]) | ||
226 | __clear_bit(flindex, &pool->flbitmap); | ||
227 | } else { | ||
228 | /* | ||
229 | * DEBUG ONLY: We need not reinitialize freelist head previous | ||
230 | * pointer to 0 - we never depend on its value. But just for | ||
231 | * sanity, lets do it. | ||
232 | */ | ||
233 | tmpblock = get_ptr_atomic(pool->freelist[slindex].page, | ||
234 | pool->freelist[slindex].offset, KM_USER1); | ||
235 | tmpblock->link.prev_page = 0; | ||
236 | tmpblock->link.prev_offset = 0; | ||
237 | put_ptr_atomic(tmpblock, KM_USER1); | ||
238 | } | ||
239 | } | ||
240 | |||
241 | /* | ||
242 | * Remove block from freelist. Index 'slindex' identifies the freelist. | ||
243 | */ | ||
244 | static void remove_block(struct xv_pool *pool, struct page *page, u32 offset, | ||
245 | struct block_header *block, u32 slindex) | ||
246 | { | ||
247 | u32 flindex; | ||
248 | struct block_header *tmpblock; | ||
249 | |||
250 | if (pool->freelist[slindex].page == page | ||
251 | && pool->freelist[slindex].offset == offset) { | ||
252 | remove_block_head(pool, block, slindex); | ||
253 | return; | ||
254 | } | ||
255 | |||
256 | flindex = slindex / BITS_PER_LONG; | ||
257 | |||
258 | if (block->link.prev_page) { | ||
259 | tmpblock = get_ptr_atomic(block->link.prev_page, | ||
260 | block->link.prev_offset, KM_USER1); | ||
261 | tmpblock->link.next_page = block->link.next_page; | ||
262 | tmpblock->link.next_offset = block->link.next_offset; | ||
263 | put_ptr_atomic(tmpblock, KM_USER1); | ||
264 | } | ||
265 | |||
266 | if (block->link.next_page) { | ||
267 | tmpblock = get_ptr_atomic(block->link.next_page, | ||
268 | block->link.next_offset, KM_USER1); | ||
269 | tmpblock->link.prev_page = block->link.prev_page; | ||
270 | tmpblock->link.prev_offset = block->link.prev_offset; | ||
271 | put_ptr_atomic(tmpblock, KM_USER1); | ||
272 | } | ||
273 | } | ||
274 | |||
275 | /* | ||
276 | * Allocate a page and add it to freelist of given pool. | ||
277 | */ | ||
278 | static int grow_pool(struct xv_pool *pool, gfp_t flags) | ||
279 | { | ||
280 | struct page *page; | ||
281 | struct block_header *block; | ||
282 | |||
283 | page = alloc_page(flags); | ||
284 | if (unlikely(!page)) | ||
285 | return -ENOMEM; | ||
286 | |||
287 | stat_inc(&pool->total_pages); | ||
288 | |||
289 | spin_lock(&pool->lock); | ||
290 | block = get_ptr_atomic(page, 0, KM_USER0); | ||
291 | |||
292 | block->size = PAGE_SIZE - XV_ALIGN; | ||
293 | set_flag(block, BLOCK_FREE); | ||
294 | clear_flag(block, PREV_FREE); | ||
295 | set_blockprev(block, 0); | ||
296 | |||
297 | insert_block(pool, page, 0, block); | ||
298 | |||
299 | put_ptr_atomic(block, KM_USER0); | ||
300 | spin_unlock(&pool->lock); | ||
301 | |||
302 | return 0; | ||
303 | } | ||
304 | |||
305 | /* | ||
306 | * Create a memory pool. Allocates freelist, bitmaps and other | ||
307 | * per-pool metadata. | ||
308 | */ | ||
309 | struct xv_pool *xv_create_pool(void) | ||
310 | { | ||
311 | u32 ovhd_size; | ||
312 | struct xv_pool *pool; | ||
313 | |||
314 | ovhd_size = roundup(sizeof(*pool), PAGE_SIZE); | ||
315 | pool = kzalloc(ovhd_size, GFP_KERNEL); | ||
316 | if (!pool) | ||
317 | return NULL; | ||
318 | |||
319 | spin_lock_init(&pool->lock); | ||
320 | |||
321 | return pool; | ||
322 | } | ||
323 | |||
324 | void xv_destroy_pool(struct xv_pool *pool) | ||
325 | { | ||
326 | kfree(pool); | ||
327 | } | ||
328 | |||
329 | /** | ||
330 | * xv_malloc - Allocate block of given size from pool. | ||
331 | * @pool: pool to allocate from | ||
332 | * @size: size of block to allocate | ||
333 | * @page: page no. that holds the object | ||
334 | * @offset: location of object within page | ||
335 | * | ||
336 | * On success, <page, offset> identifies block allocated | ||
337 | * and 0 is returned. On failure, <page, offset> is set to | ||
338 | * 0 and -ENOMEM is returned. | ||
339 | * | ||
340 | * Allocation requests with size > XV_MAX_ALLOC_SIZE will fail. | ||
341 | */ | ||
342 | int xv_malloc(struct xv_pool *pool, u32 size, struct page **page, | ||
343 | u32 *offset, gfp_t flags) | ||
344 | { | ||
345 | int error; | ||
346 | u32 index, tmpsize, origsize, tmpoffset; | ||
347 | struct block_header *block, *tmpblock; | ||
348 | |||
349 | *page = NULL; | ||
350 | *offset = 0; | ||
351 | origsize = size; | ||
352 | |||
353 | if (unlikely(!size || size > XV_MAX_ALLOC_SIZE)) | ||
354 | return -ENOMEM; | ||
355 | |||
356 | size = ALIGN(size, XV_ALIGN); | ||
357 | |||
358 | spin_lock(&pool->lock); | ||
359 | |||
360 | index = find_block(pool, size, page, offset); | ||
361 | |||
362 | if (!*page) { | ||
363 | spin_unlock(&pool->lock); | ||
364 | if (flags & GFP_NOWAIT) | ||
365 | return -ENOMEM; | ||
366 | error = grow_pool(pool, flags); | ||
367 | if (unlikely(error)) | ||
368 | return error; | ||
369 | |||
370 | spin_lock(&pool->lock); | ||
371 | index = find_block(pool, size, page, offset); | ||
372 | } | ||
373 | |||
374 | if (!*page) { | ||
375 | spin_unlock(&pool->lock); | ||
376 | return -ENOMEM; | ||
377 | } | ||
378 | |||
379 | block = get_ptr_atomic(*page, *offset, KM_USER0); | ||
380 | |||
381 | remove_block_head(pool, block, index); | ||
382 | |||
383 | /* Split the block if required */ | ||
384 | tmpoffset = *offset + size + XV_ALIGN; | ||
385 | tmpsize = block->size - size; | ||
386 | tmpblock = (struct block_header *)((char *)block + size + XV_ALIGN); | ||
387 | if (tmpsize) { | ||
388 | tmpblock->size = tmpsize - XV_ALIGN; | ||
389 | set_flag(tmpblock, BLOCK_FREE); | ||
390 | clear_flag(tmpblock, PREV_FREE); | ||
391 | |||
392 | set_blockprev(tmpblock, *offset); | ||
393 | if (tmpblock->size >= XV_MIN_ALLOC_SIZE) | ||
394 | insert_block(pool, *page, tmpoffset, tmpblock); | ||
395 | |||
396 | if (tmpoffset + XV_ALIGN + tmpblock->size != PAGE_SIZE) { | ||
397 | tmpblock = BLOCK_NEXT(tmpblock); | ||
398 | set_blockprev(tmpblock, tmpoffset); | ||
399 | } | ||
400 | } else { | ||
401 | /* This block is exact fit */ | ||
402 | if (tmpoffset != PAGE_SIZE) | ||
403 | clear_flag(tmpblock, PREV_FREE); | ||
404 | } | ||
405 | |||
406 | block->size = origsize; | ||
407 | clear_flag(block, BLOCK_FREE); | ||
408 | |||
409 | put_ptr_atomic(block, KM_USER0); | ||
410 | spin_unlock(&pool->lock); | ||
411 | |||
412 | *offset += XV_ALIGN; | ||
413 | |||
414 | return 0; | ||
415 | } | ||
416 | |||
417 | /* | ||
418 | * Free block identified with <page, offset> | ||
419 | */ | ||
420 | void xv_free(struct xv_pool *pool, struct page *page, u32 offset) | ||
421 | { | ||
422 | void *page_start; | ||
423 | struct block_header *block, *tmpblock; | ||
424 | |||
425 | offset -= XV_ALIGN; | ||
426 | |||
427 | spin_lock(&pool->lock); | ||
428 | |||
429 | page_start = get_ptr_atomic(page, 0, KM_USER0); | ||
430 | block = (struct block_header *)((char *)page_start + offset); | ||
431 | |||
432 | /* Catch double free bugs */ | ||
433 | BUG_ON(test_flag(block, BLOCK_FREE)); | ||
434 | |||
435 | block->size = ALIGN(block->size, XV_ALIGN); | ||
436 | |||
437 | tmpblock = BLOCK_NEXT(block); | ||
438 | if (offset + block->size + XV_ALIGN == PAGE_SIZE) | ||
439 | tmpblock = NULL; | ||
440 | |||
441 | /* Merge next block if its free */ | ||
442 | if (tmpblock && test_flag(tmpblock, BLOCK_FREE)) { | ||
443 | /* | ||
444 | * Blocks smaller than XV_MIN_ALLOC_SIZE | ||
445 | * are not inserted in any free list. | ||
446 | */ | ||
447 | if (tmpblock->size >= XV_MIN_ALLOC_SIZE) { | ||
448 | remove_block(pool, page, | ||
449 | offset + block->size + XV_ALIGN, tmpblock, | ||
450 | get_index_for_insert(tmpblock->size)); | ||
451 | } | ||
452 | block->size += tmpblock->size + XV_ALIGN; | ||
453 | } | ||
454 | |||
455 | /* Merge previous block if its free */ | ||
456 | if (test_flag(block, PREV_FREE)) { | ||
457 | tmpblock = (struct block_header *)((char *)(page_start) + | ||
458 | get_blockprev(block)); | ||
459 | offset = offset - tmpblock->size - XV_ALIGN; | ||
460 | |||
461 | if (tmpblock->size >= XV_MIN_ALLOC_SIZE) | ||
462 | remove_block(pool, page, offset, tmpblock, | ||
463 | get_index_for_insert(tmpblock->size)); | ||
464 | |||
465 | tmpblock->size += block->size + XV_ALIGN; | ||
466 | block = tmpblock; | ||
467 | } | ||
468 | |||
469 | /* No used objects in this page. Free it. */ | ||
470 | if (block->size == PAGE_SIZE - XV_ALIGN) { | ||
471 | put_ptr_atomic(page_start, KM_USER0); | ||
472 | spin_unlock(&pool->lock); | ||
473 | |||
474 | __free_page(page); | ||
475 | stat_dec(&pool->total_pages); | ||
476 | return; | ||
477 | } | ||
478 | |||
479 | set_flag(block, BLOCK_FREE); | ||
480 | if (block->size >= XV_MIN_ALLOC_SIZE) | ||
481 | insert_block(pool, page, offset, block); | ||
482 | |||
483 | if (offset + block->size + XV_ALIGN != PAGE_SIZE) { | ||
484 | tmpblock = BLOCK_NEXT(block); | ||
485 | set_flag(tmpblock, PREV_FREE); | ||
486 | set_blockprev(tmpblock, offset); | ||
487 | } | ||
488 | |||
489 | put_ptr_atomic(page_start, KM_USER0); | ||
490 | spin_unlock(&pool->lock); | ||
491 | } | ||
492 | |||
493 | u32 xv_get_object_size(void *obj) | ||
494 | { | ||
495 | struct block_header *blk; | ||
496 | |||
497 | blk = (struct block_header *)((char *)(obj) - XV_ALIGN); | ||
498 | return blk->size; | ||
499 | } | ||
500 | |||
501 | /* | ||
502 | * Returns total memory used by allocator (userdata + metadata) | ||
503 | */ | ||
504 | u64 xv_get_total_size_bytes(struct xv_pool *pool) | ||
505 | { | ||
506 | return pool->total_pages << PAGE_SHIFT; | ||
507 | } | ||