diff options
Diffstat (limited to 'drivers/staging/zram/xvmalloc.c')
-rw-r--r-- | drivers/staging/zram/xvmalloc.c | 510 |
1 files changed, 510 insertions, 0 deletions
diff --git a/drivers/staging/zram/xvmalloc.c b/drivers/staging/zram/xvmalloc.c new file mode 100644 index 00000000000..1f9c5082b6d --- /dev/null +++ b/drivers/staging/zram/xvmalloc.c | |||
@@ -0,0 +1,510 @@ | |||
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 | #ifdef CONFIG_ZRAM_DEBUG | ||
14 | #define DEBUG | ||
15 | #endif | ||
16 | |||
17 | #include <linux/module.h> | ||
18 | #include <linux/kernel.h> | ||
19 | #include <linux/bitops.h> | ||
20 | #include <linux/errno.h> | ||
21 | #include <linux/highmem.h> | ||
22 | #include <linux/init.h> | ||
23 | #include <linux/string.h> | ||
24 | #include <linux/slab.h> | ||
25 | |||
26 | #include "xvmalloc.h" | ||
27 | #include "xvmalloc_int.h" | ||
28 | |||
29 | static void stat_inc(u64 *value) | ||
30 | { | ||
31 | *value = *value + 1; | ||
32 | } | ||
33 | |||
34 | static void stat_dec(u64 *value) | ||
35 | { | ||
36 | *value = *value - 1; | ||
37 | } | ||
38 | |||
39 | static int test_flag(struct block_header *block, enum blockflags flag) | ||
40 | { | ||
41 | return block->prev & BIT(flag); | ||
42 | } | ||
43 | |||
44 | static void set_flag(struct block_header *block, enum blockflags flag) | ||
45 | { | ||
46 | block->prev |= BIT(flag); | ||
47 | } | ||
48 | |||
49 | static void clear_flag(struct block_header *block, enum blockflags flag) | ||
50 | { | ||
51 | block->prev &= ~BIT(flag); | ||
52 | } | ||
53 | |||
54 | /* | ||
55 | * Given <page, offset> pair, provide a dereferencable pointer. | ||
56 | * This is called from xv_malloc/xv_free path, so it | ||
57 | * needs to be fast. | ||
58 | */ | ||
59 | static void *get_ptr_atomic(struct page *page, u16 offset, enum km_type type) | ||
60 | { | ||
61 | unsigned char *base; | ||
62 | |||
63 | base = kmap_atomic(page, type); | ||
64 | return base + offset; | ||
65 | } | ||
66 | |||
67 | static void put_ptr_atomic(void *ptr, enum km_type type) | ||
68 | { | ||
69 | kunmap_atomic(ptr, type); | ||
70 | } | ||
71 | |||
72 | static u32 get_blockprev(struct block_header *block) | ||
73 | { | ||
74 | return block->prev & PREV_MASK; | ||
75 | } | ||
76 | |||
77 | static void set_blockprev(struct block_header *block, u16 new_offset) | ||
78 | { | ||
79 | block->prev = new_offset | (block->prev & FLAGS_MASK); | ||
80 | } | ||
81 | |||
82 | static struct block_header *BLOCK_NEXT(struct block_header *block) | ||
83 | { | ||
84 | return (struct block_header *) | ||
85 | ((char *)block + block->size + XV_ALIGN); | ||
86 | } | ||
87 | |||
88 | /* | ||
89 | * Get index of free list containing blocks of maximum size | ||
90 | * which is less than or equal to given size. | ||
91 | */ | ||
92 | static u32 get_index_for_insert(u32 size) | ||
93 | { | ||
94 | if (unlikely(size > XV_MAX_ALLOC_SIZE)) | ||
95 | size = XV_MAX_ALLOC_SIZE; | ||
96 | size &= ~FL_DELTA_MASK; | ||
97 | return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT; | ||
98 | } | ||
99 | |||
100 | /* | ||
101 | * Get index of free list having blocks of size greater than | ||
102 | * or equal to requested size. | ||
103 | */ | ||
104 | static u32 get_index(u32 size) | ||
105 | { | ||
106 | if (unlikely(size < XV_MIN_ALLOC_SIZE)) | ||
107 | size = XV_MIN_ALLOC_SIZE; | ||
108 | size = ALIGN(size, FL_DELTA); | ||
109 | return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT; | ||
110 | } | ||
111 | |||
112 | /** | ||
113 | * find_block - find block of at least given size | ||
114 | * @pool: memory pool to search from | ||
115 | * @size: size of block required | ||
116 | * @page: page containing required block | ||
117 | * @offset: offset within the page where block is located. | ||
118 | * | ||
119 | * Searches two level bitmap to locate block of at least | ||
120 | * the given size. If such a block is found, it provides | ||
121 | * <page, offset> to identify this block and returns index | ||
122 | * in freelist where we found this block. | ||
123 | * Otherwise, returns 0 and <page, offset> params are not touched. | ||
124 | */ | ||
125 | static u32 find_block(struct xv_pool *pool, u32 size, | ||
126 | struct page **page, u32 *offset) | ||
127 | { | ||
128 | ulong flbitmap, slbitmap; | ||
129 | u32 flindex, slindex, slbitstart; | ||
130 | |||
131 | /* There are no free blocks in this pool */ | ||
132 | if (!pool->flbitmap) | ||
133 | return 0; | ||
134 | |||
135 | /* Get freelist index correspoding to this size */ | ||
136 | slindex = get_index(size); | ||
137 | slbitmap = pool->slbitmap[slindex / BITS_PER_LONG]; | ||
138 | slbitstart = slindex % BITS_PER_LONG; | ||
139 | |||
140 | /* | ||
141 | * If freelist is not empty at this index, we found the | ||
142 | * block - head of this list. This is approximate best-fit match. | ||
143 | */ | ||
144 | if (test_bit(slbitstart, &slbitmap)) { | ||
145 | *page = pool->freelist[slindex].page; | ||
146 | *offset = pool->freelist[slindex].offset; | ||
147 | return slindex; | ||
148 | } | ||
149 | |||
150 | /* | ||
151 | * No best-fit found. Search a bit further in bitmap for a free block. | ||
152 | * Second level bitmap consists of series of 32-bit chunks. Search | ||
153 | * further in the chunk where we expected a best-fit, starting from | ||
154 | * index location found above. | ||
155 | */ | ||
156 | slbitstart++; | ||
157 | slbitmap >>= slbitstart; | ||
158 | |||
159 | /* Skip this search if we were already at end of this bitmap chunk */ | ||
160 | if ((slbitstart != BITS_PER_LONG) && slbitmap) { | ||
161 | slindex += __ffs(slbitmap) + 1; | ||
162 | *page = pool->freelist[slindex].page; | ||
163 | *offset = pool->freelist[slindex].offset; | ||
164 | return slindex; | ||
165 | } | ||
166 | |||
167 | /* Now do a full two-level bitmap search to find next nearest fit */ | ||
168 | flindex = slindex / BITS_PER_LONG; | ||
169 | |||
170 | flbitmap = (pool->flbitmap) >> (flindex + 1); | ||
171 | if (!flbitmap) | ||
172 | return 0; | ||
173 | |||
174 | flindex += __ffs(flbitmap) + 1; | ||
175 | slbitmap = pool->slbitmap[flindex]; | ||
176 | slindex = (flindex * BITS_PER_LONG) + __ffs(slbitmap); | ||
177 | *page = pool->freelist[slindex].page; | ||
178 | *offset = pool->freelist[slindex].offset; | ||
179 | |||
180 | return slindex; | ||
181 | } | ||
182 | |||
183 | /* | ||
184 | * Insert block at <page, offset> in freelist of given pool. | ||
185 | * freelist used depends on block size. | ||
186 | */ | ||
187 | static void insert_block(struct xv_pool *pool, struct page *page, u32 offset, | ||
188 | struct block_header *block) | ||
189 | { | ||
190 | u32 flindex, slindex; | ||
191 | struct block_header *nextblock; | ||
192 | |||
193 | slindex = get_index_for_insert(block->size); | ||
194 | flindex = slindex / BITS_PER_LONG; | ||
195 | |||
196 | block->link.prev_page = NULL; | ||
197 | block->link.prev_offset = 0; | ||
198 | block->link.next_page = pool->freelist[slindex].page; | ||
199 | block->link.next_offset = pool->freelist[slindex].offset; | ||
200 | pool->freelist[slindex].page = page; | ||
201 | pool->freelist[slindex].offset = offset; | ||
202 | |||
203 | if (block->link.next_page) { | ||
204 | nextblock = get_ptr_atomic(block->link.next_page, | ||
205 | block->link.next_offset, KM_USER1); | ||
206 | nextblock->link.prev_page = page; | ||
207 | nextblock->link.prev_offset = offset; | ||
208 | put_ptr_atomic(nextblock, KM_USER1); | ||
209 | /* If there was a next page then the free bits are set. */ | ||
210 | return; | ||
211 | } | ||
212 | |||
213 | __set_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]); | ||
214 | __set_bit(flindex, &pool->flbitmap); | ||
215 | } | ||
216 | |||
217 | /* | ||
218 | * Remove block from freelist. Index 'slindex' identifies the freelist. | ||
219 | */ | ||
220 | static void remove_block(struct xv_pool *pool, struct page *page, u32 offset, | ||
221 | struct block_header *block, u32 slindex) | ||
222 | { | ||
223 | u32 flindex = slindex / BITS_PER_LONG; | ||
224 | struct block_header *tmpblock; | ||
225 | |||
226 | if (block->link.prev_page) { | ||
227 | tmpblock = get_ptr_atomic(block->link.prev_page, | ||
228 | block->link.prev_offset, KM_USER1); | ||
229 | tmpblock->link.next_page = block->link.next_page; | ||
230 | tmpblock->link.next_offset = block->link.next_offset; | ||
231 | put_ptr_atomic(tmpblock, KM_USER1); | ||
232 | } | ||
233 | |||
234 | if (block->link.next_page) { | ||
235 | tmpblock = get_ptr_atomic(block->link.next_page, | ||
236 | block->link.next_offset, KM_USER1); | ||
237 | tmpblock->link.prev_page = block->link.prev_page; | ||
238 | tmpblock->link.prev_offset = block->link.prev_offset; | ||
239 | put_ptr_atomic(tmpblock, KM_USER1); | ||
240 | } | ||
241 | |||
242 | /* Is this block is at the head of the freelist? */ | ||
243 | if (pool->freelist[slindex].page == page | ||
244 | && pool->freelist[slindex].offset == offset) { | ||
245 | |||
246 | pool->freelist[slindex].page = block->link.next_page; | ||
247 | pool->freelist[slindex].offset = block->link.next_offset; | ||
248 | |||
249 | if (pool->freelist[slindex].page) { | ||
250 | struct block_header *tmpblock; | ||
251 | tmpblock = get_ptr_atomic(pool->freelist[slindex].page, | ||
252 | pool->freelist[slindex].offset, | ||
253 | KM_USER1); | ||
254 | tmpblock->link.prev_page = NULL; | ||
255 | tmpblock->link.prev_offset = 0; | ||
256 | put_ptr_atomic(tmpblock, KM_USER1); | ||
257 | } else { | ||
258 | /* This freelist bucket is empty */ | ||
259 | __clear_bit(slindex % BITS_PER_LONG, | ||
260 | &pool->slbitmap[flindex]); | ||
261 | if (!pool->slbitmap[flindex]) | ||
262 | __clear_bit(flindex, &pool->flbitmap); | ||
263 | } | ||
264 | } | ||
265 | |||
266 | block->link.prev_page = NULL; | ||
267 | block->link.prev_offset = 0; | ||
268 | block->link.next_page = NULL; | ||
269 | block->link.next_offset = 0; | ||
270 | } | ||
271 | |||
272 | /* | ||
273 | * Allocate a page and add it to freelist of given pool. | ||
274 | */ | ||
275 | static int grow_pool(struct xv_pool *pool, gfp_t flags) | ||
276 | { | ||
277 | struct page *page; | ||
278 | struct block_header *block; | ||
279 | |||
280 | page = alloc_page(flags); | ||
281 | if (unlikely(!page)) | ||
282 | return -ENOMEM; | ||
283 | |||
284 | stat_inc(&pool->total_pages); | ||
285 | |||
286 | spin_lock(&pool->lock); | ||
287 | block = get_ptr_atomic(page, 0, KM_USER0); | ||
288 | |||
289 | block->size = PAGE_SIZE - XV_ALIGN; | ||
290 | set_flag(block, BLOCK_FREE); | ||
291 | clear_flag(block, PREV_FREE); | ||
292 | set_blockprev(block, 0); | ||
293 | |||
294 | insert_block(pool, page, 0, block); | ||
295 | |||
296 | put_ptr_atomic(block, KM_USER0); | ||
297 | spin_unlock(&pool->lock); | ||
298 | |||
299 | return 0; | ||
300 | } | ||
301 | |||
302 | /* | ||
303 | * Create a memory pool. Allocates freelist, bitmaps and other | ||
304 | * per-pool metadata. | ||
305 | */ | ||
306 | struct xv_pool *xv_create_pool(void) | ||
307 | { | ||
308 | u32 ovhd_size; | ||
309 | struct xv_pool *pool; | ||
310 | |||
311 | ovhd_size = roundup(sizeof(*pool), PAGE_SIZE); | ||
312 | pool = kzalloc(ovhd_size, GFP_KERNEL); | ||
313 | if (!pool) | ||
314 | return NULL; | ||
315 | |||
316 | spin_lock_init(&pool->lock); | ||
317 | |||
318 | return pool; | ||
319 | } | ||
320 | EXPORT_SYMBOL_GPL(xv_create_pool); | ||
321 | |||
322 | void xv_destroy_pool(struct xv_pool *pool) | ||
323 | { | ||
324 | kfree(pool); | ||
325 | } | ||
326 | EXPORT_SYMBOL_GPL(xv_destroy_pool); | ||
327 | |||
328 | /** | ||
329 | * xv_malloc - Allocate block of given size from pool. | ||
330 | * @pool: pool to allocate from | ||
331 | * @size: size of block to allocate | ||
332 | * @page: page no. that holds the object | ||
333 | * @offset: location of object within page | ||
334 | * | ||
335 | * On success, <page, offset> identifies block allocated | ||
336 | * and 0 is returned. On failure, <page, offset> is set to | ||
337 | * 0 and -ENOMEM is returned. | ||
338 | * | ||
339 | * Allocation requests with size > XV_MAX_ALLOC_SIZE will fail. | ||
340 | */ | ||
341 | int xv_malloc(struct xv_pool *pool, u32 size, struct page **page, | ||
342 | u32 *offset, gfp_t flags) | ||
343 | { | ||
344 | int error; | ||
345 | u32 index, tmpsize, origsize, tmpoffset; | ||
346 | struct block_header *block, *tmpblock; | ||
347 | |||
348 | *page = NULL; | ||
349 | *offset = 0; | ||
350 | origsize = size; | ||
351 | |||
352 | if (unlikely(!size || size > XV_MAX_ALLOC_SIZE)) | ||
353 | return -ENOMEM; | ||
354 | |||
355 | size = ALIGN(size, XV_ALIGN); | ||
356 | |||
357 | spin_lock(&pool->lock); | ||
358 | |||
359 | index = find_block(pool, size, page, offset); | ||
360 | |||
361 | if (!*page) { | ||
362 | spin_unlock(&pool->lock); | ||
363 | if (flags & GFP_NOWAIT) | ||
364 | return -ENOMEM; | ||
365 | error = grow_pool(pool, flags); | ||
366 | if (unlikely(error)) | ||
367 | return error; | ||
368 | |||
369 | spin_lock(&pool->lock); | ||
370 | index = find_block(pool, size, page, offset); | ||
371 | } | ||
372 | |||
373 | if (!*page) { | ||
374 | spin_unlock(&pool->lock); | ||
375 | return -ENOMEM; | ||
376 | } | ||
377 | |||
378 | block = get_ptr_atomic(*page, *offset, KM_USER0); | ||
379 | |||
380 | remove_block(pool, *page, *offset, block, index); | ||
381 | |||
382 | /* Split the block if required */ | ||
383 | tmpoffset = *offset + size + XV_ALIGN; | ||
384 | tmpsize = block->size - size; | ||
385 | tmpblock = (struct block_header *)((char *)block + size + XV_ALIGN); | ||
386 | if (tmpsize) { | ||
387 | tmpblock->size = tmpsize - XV_ALIGN; | ||
388 | set_flag(tmpblock, BLOCK_FREE); | ||
389 | clear_flag(tmpblock, PREV_FREE); | ||
390 | |||
391 | set_blockprev(tmpblock, *offset); | ||
392 | if (tmpblock->size >= XV_MIN_ALLOC_SIZE) | ||
393 | insert_block(pool, *page, tmpoffset, tmpblock); | ||
394 | |||
395 | if (tmpoffset + XV_ALIGN + tmpblock->size != PAGE_SIZE) { | ||
396 | tmpblock = BLOCK_NEXT(tmpblock); | ||
397 | set_blockprev(tmpblock, tmpoffset); | ||
398 | } | ||
399 | } else { | ||
400 | /* This block is exact fit */ | ||
401 | if (tmpoffset != PAGE_SIZE) | ||
402 | clear_flag(tmpblock, PREV_FREE); | ||
403 | } | ||
404 | |||
405 | block->size = origsize; | ||
406 | clear_flag(block, BLOCK_FREE); | ||
407 | |||
408 | put_ptr_atomic(block, KM_USER0); | ||
409 | spin_unlock(&pool->lock); | ||
410 | |||
411 | *offset += XV_ALIGN; | ||
412 | |||
413 | return 0; | ||
414 | } | ||
415 | EXPORT_SYMBOL_GPL(xv_malloc); | ||
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 | EXPORT_SYMBOL_GPL(xv_free); | ||
493 | |||
494 | u32 xv_get_object_size(void *obj) | ||
495 | { | ||
496 | struct block_header *blk; | ||
497 | |||
498 | blk = (struct block_header *)((char *)(obj) - XV_ALIGN); | ||
499 | return blk->size; | ||
500 | } | ||
501 | EXPORT_SYMBOL_GPL(xv_get_object_size); | ||
502 | |||
503 | /* | ||
504 | * Returns total memory used by allocator (userdata + metadata) | ||
505 | */ | ||
506 | u64 xv_get_total_size_bytes(struct xv_pool *pool) | ||
507 | { | ||
508 | return pool->total_pages << PAGE_SHIFT; | ||
509 | } | ||
510 | EXPORT_SYMBOL_GPL(xv_get_total_size_bytes); | ||