Root/
1 | /* |
2 | * zbud.c |
3 | * |
4 | * Copyright (C) 2013, Seth Jennings, IBM |
5 | * |
6 | * Concepts based on zcache internal zbud allocator by Dan Magenheimer. |
7 | * |
8 | * zbud is an special purpose allocator for storing compressed pages. Contrary |
9 | * to what its name may suggest, zbud is not a buddy allocator, but rather an |
10 | * allocator that "buddies" two compressed pages together in a single memory |
11 | * page. |
12 | * |
13 | * While this design limits storage density, it has simple and deterministic |
14 | * reclaim properties that make it preferable to a higher density approach when |
15 | * reclaim will be used. |
16 | * |
17 | * zbud works by storing compressed pages, or "zpages", together in pairs in a |
18 | * single memory page called a "zbud page". The first buddy is "left |
19 | * justified" at the beginning of the zbud page, and the last buddy is "right |
20 | * justified" at the end of the zbud page. The benefit is that if either |
21 | * buddy is freed, the freed buddy space, coalesced with whatever slack space |
22 | * that existed between the buddies, results in the largest possible free region |
23 | * within the zbud page. |
24 | * |
25 | * zbud also provides an attractive lower bound on density. The ratio of zpages |
26 | * to zbud pages can not be less than 1. This ensures that zbud can never "do |
27 | * harm" by using more pages to store zpages than the uncompressed zpages would |
28 | * have used on their own. |
29 | * |
30 | * zbud pages are divided into "chunks". The size of the chunks is fixed at |
31 | * compile time and determined by NCHUNKS_ORDER below. Dividing zbud pages |
32 | * into chunks allows organizing unbuddied zbud pages into a manageable number |
33 | * of unbuddied lists according to the number of free chunks available in the |
34 | * zbud page. |
35 | * |
36 | * The zbud API differs from that of conventional allocators in that the |
37 | * allocation function, zbud_alloc(), returns an opaque handle to the user, |
38 | * not a dereferenceable pointer. The user must map the handle using |
39 | * zbud_map() in order to get a usable pointer by which to access the |
40 | * allocation data and unmap the handle with zbud_unmap() when operations |
41 | * on the allocation data are complete. |
42 | */ |
43 | |
44 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
45 | |
46 | #include <linux/atomic.h> |
47 | #include <linux/list.h> |
48 | #include <linux/mm.h> |
49 | #include <linux/module.h> |
50 | #include <linux/preempt.h> |
51 | #include <linux/slab.h> |
52 | #include <linux/spinlock.h> |
53 | #include <linux/zbud.h> |
54 | |
55 | /***************** |
56 | * Structures |
57 | *****************/ |
58 | /* |
59 | * NCHUNKS_ORDER determines the internal allocation granularity, effectively |
60 | * adjusting internal fragmentation. It also determines the number of |
61 | * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the |
62 | * allocation granularity will be in chunks of size PAGE_SIZE/64, and there |
63 | * will be 64 freelists per pool. |
64 | */ |
65 | #define NCHUNKS_ORDER 6 |
66 | |
67 | #define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER) |
68 | #define CHUNK_SIZE (1 << CHUNK_SHIFT) |
69 | #define NCHUNKS (PAGE_SIZE >> CHUNK_SHIFT) |
70 | #define ZHDR_SIZE_ALIGNED CHUNK_SIZE |
71 | |
72 | /** |
73 | * struct zbud_pool - stores metadata for each zbud pool |
74 | * @lock: protects all pool fields and first|last_chunk fields of any |
75 | * zbud page in the pool |
76 | * @unbuddied: array of lists tracking zbud pages that only contain one buddy; |
77 | * the lists each zbud page is added to depends on the size of |
78 | * its free region. |
79 | * @buddied: list tracking the zbud pages that contain two buddies; |
80 | * these zbud pages are full |
81 | * @lru: list tracking the zbud pages in LRU order by most recently |
82 | * added buddy. |
83 | * @pages_nr: number of zbud pages in the pool. |
84 | * @ops: pointer to a structure of user defined operations specified at |
85 | * pool creation time. |
86 | * |
87 | * This structure is allocated at pool creation time and maintains metadata |
88 | * pertaining to a particular zbud pool. |
89 | */ |
90 | struct zbud_pool { |
91 | spinlock_t lock; |
92 | struct list_head unbuddied[NCHUNKS]; |
93 | struct list_head buddied; |
94 | struct list_head lru; |
95 | u64 pages_nr; |
96 | struct zbud_ops *ops; |
97 | }; |
98 | |
99 | /* |
100 | * struct zbud_header - zbud page metadata occupying the first chunk of each |
101 | * zbud page. |
102 | * @buddy: links the zbud page into the unbuddied/buddied lists in the pool |
103 | * @lru: links the zbud page into the lru list in the pool |
104 | * @first_chunks: the size of the first buddy in chunks, 0 if free |
105 | * @last_chunks: the size of the last buddy in chunks, 0 if free |
106 | */ |
107 | struct zbud_header { |
108 | struct list_head buddy; |
109 | struct list_head lru; |
110 | unsigned int first_chunks; |
111 | unsigned int last_chunks; |
112 | bool under_reclaim; |
113 | }; |
114 | |
115 | /***************** |
116 | * Helpers |
117 | *****************/ |
118 | /* Just to make the code easier to read */ |
119 | enum buddy { |
120 | FIRST, |
121 | LAST |
122 | }; |
123 | |
124 | /* Converts an allocation size in bytes to size in zbud chunks */ |
125 | static int size_to_chunks(int size) |
126 | { |
127 | return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT; |
128 | } |
129 | |
130 | #define for_each_unbuddied_list(_iter, _begin) \ |
131 | for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++) |
132 | |
133 | /* Initializes the zbud header of a newly allocated zbud page */ |
134 | static struct zbud_header *init_zbud_page(struct page *page) |
135 | { |
136 | struct zbud_header *zhdr = page_address(page); |
137 | zhdr->first_chunks = 0; |
138 | zhdr->last_chunks = 0; |
139 | INIT_LIST_HEAD(&zhdr->buddy); |
140 | INIT_LIST_HEAD(&zhdr->lru); |
141 | zhdr->under_reclaim = 0; |
142 | return zhdr; |
143 | } |
144 | |
145 | /* Resets the struct page fields and frees the page */ |
146 | static void free_zbud_page(struct zbud_header *zhdr) |
147 | { |
148 | __free_page(virt_to_page(zhdr)); |
149 | } |
150 | |
151 | /* |
152 | * Encodes the handle of a particular buddy within a zbud page |
153 | * Pool lock should be held as this function accesses first|last_chunks |
154 | */ |
155 | static unsigned long encode_handle(struct zbud_header *zhdr, enum buddy bud) |
156 | { |
157 | unsigned long handle; |
158 | |
159 | /* |
160 | * For now, the encoded handle is actually just the pointer to the data |
161 | * but this might not always be the case. A little information hiding. |
162 | * Add CHUNK_SIZE to the handle if it is the first allocation to jump |
163 | * over the zbud header in the first chunk. |
164 | */ |
165 | handle = (unsigned long)zhdr; |
166 | if (bud == FIRST) |
167 | /* skip over zbud header */ |
168 | handle += ZHDR_SIZE_ALIGNED; |
169 | else /* bud == LAST */ |
170 | handle += PAGE_SIZE - (zhdr->last_chunks << CHUNK_SHIFT); |
171 | return handle; |
172 | } |
173 | |
174 | /* Returns the zbud page where a given handle is stored */ |
175 | static struct zbud_header *handle_to_zbud_header(unsigned long handle) |
176 | { |
177 | return (struct zbud_header *)(handle & PAGE_MASK); |
178 | } |
179 | |
180 | /* Returns the number of free chunks in a zbud page */ |
181 | static int num_free_chunks(struct zbud_header *zhdr) |
182 | { |
183 | /* |
184 | * Rather than branch for different situations, just use the fact that |
185 | * free buddies have a length of zero to simplify everything. -1 at the |
186 | * end for the zbud header. |
187 | */ |
188 | return NCHUNKS - zhdr->first_chunks - zhdr->last_chunks - 1; |
189 | } |
190 | |
191 | /***************** |
192 | * API Functions |
193 | *****************/ |
194 | /** |
195 | * zbud_create_pool() - create a new zbud pool |
196 | * @gfp: gfp flags when allocating the zbud pool structure |
197 | * @ops: user-defined operations for the zbud pool |
198 | * |
199 | * Return: pointer to the new zbud pool or NULL if the metadata allocation |
200 | * failed. |
201 | */ |
202 | struct zbud_pool *zbud_create_pool(gfp_t gfp, struct zbud_ops *ops) |
203 | { |
204 | struct zbud_pool *pool; |
205 | int i; |
206 | |
207 | pool = kmalloc(sizeof(struct zbud_pool), gfp); |
208 | if (!pool) |
209 | return NULL; |
210 | spin_lock_init(&pool->lock); |
211 | for_each_unbuddied_list(i, 0) |
212 | INIT_LIST_HEAD(&pool->unbuddied[i]); |
213 | INIT_LIST_HEAD(&pool->buddied); |
214 | INIT_LIST_HEAD(&pool->lru); |
215 | pool->pages_nr = 0; |
216 | pool->ops = ops; |
217 | return pool; |
218 | } |
219 | |
220 | /** |
221 | * zbud_destroy_pool() - destroys an existing zbud pool |
222 | * @pool: the zbud pool to be destroyed |
223 | * |
224 | * The pool should be emptied before this function is called. |
225 | */ |
226 | void zbud_destroy_pool(struct zbud_pool *pool) |
227 | { |
228 | kfree(pool); |
229 | } |
230 | |
231 | /** |
232 | * zbud_alloc() - allocates a region of a given size |
233 | * @pool: zbud pool from which to allocate |
234 | * @size: size in bytes of the desired allocation |
235 | * @gfp: gfp flags used if the pool needs to grow |
236 | * @handle: handle of the new allocation |
237 | * |
238 | * This function will attempt to find a free region in the pool large enough to |
239 | * satisfy the allocation request. A search of the unbuddied lists is |
240 | * performed first. If no suitable free region is found, then a new page is |
241 | * allocated and added to the pool to satisfy the request. |
242 | * |
243 | * gfp should not set __GFP_HIGHMEM as highmem pages cannot be used |
244 | * as zbud pool pages. |
245 | * |
246 | * Return: 0 if success and handle is set, otherwise -EINVAL if the size or |
247 | * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate |
248 | * a new page. |
249 | */ |
250 | int zbud_alloc(struct zbud_pool *pool, int size, gfp_t gfp, |
251 | unsigned long *handle) |
252 | { |
253 | int chunks, i, freechunks; |
254 | struct zbud_header *zhdr = NULL; |
255 | enum buddy bud; |
256 | struct page *page; |
257 | |
258 | if (size <= 0 || gfp & __GFP_HIGHMEM) |
259 | return -EINVAL; |
260 | if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE) |
261 | return -ENOSPC; |
262 | chunks = size_to_chunks(size); |
263 | spin_lock(&pool->lock); |
264 | |
265 | /* First, try to find an unbuddied zbud page. */ |
266 | zhdr = NULL; |
267 | for_each_unbuddied_list(i, chunks) { |
268 | if (!list_empty(&pool->unbuddied[i])) { |
269 | zhdr = list_first_entry(&pool->unbuddied[i], |
270 | struct zbud_header, buddy); |
271 | list_del(&zhdr->buddy); |
272 | if (zhdr->first_chunks == 0) |
273 | bud = FIRST; |
274 | else |
275 | bud = LAST; |
276 | goto found; |
277 | } |
278 | } |
279 | |
280 | /* Couldn't find unbuddied zbud page, create new one */ |
281 | spin_unlock(&pool->lock); |
282 | page = alloc_page(gfp); |
283 | if (!page) |
284 | return -ENOMEM; |
285 | spin_lock(&pool->lock); |
286 | pool->pages_nr++; |
287 | zhdr = init_zbud_page(page); |
288 | bud = FIRST; |
289 | |
290 | found: |
291 | if (bud == FIRST) |
292 | zhdr->first_chunks = chunks; |
293 | else |
294 | zhdr->last_chunks = chunks; |
295 | |
296 | if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0) { |
297 | /* Add to unbuddied list */ |
298 | freechunks = num_free_chunks(zhdr); |
299 | list_add(&zhdr->buddy, &pool->unbuddied[freechunks]); |
300 | } else { |
301 | /* Add to buddied list */ |
302 | list_add(&zhdr->buddy, &pool->buddied); |
303 | } |
304 | |
305 | /* Add/move zbud page to beginning of LRU */ |
306 | if (!list_empty(&zhdr->lru)) |
307 | list_del(&zhdr->lru); |
308 | list_add(&zhdr->lru, &pool->lru); |
309 | |
310 | *handle = encode_handle(zhdr, bud); |
311 | spin_unlock(&pool->lock); |
312 | |
313 | return 0; |
314 | } |
315 | |
316 | /** |
317 | * zbud_free() - frees the allocation associated with the given handle |
318 | * @pool: pool in which the allocation resided |
319 | * @handle: handle associated with the allocation returned by zbud_alloc() |
320 | * |
321 | * In the case that the zbud page in which the allocation resides is under |
322 | * reclaim, as indicated by the PG_reclaim flag being set, this function |
323 | * only sets the first|last_chunks to 0. The page is actually freed |
324 | * once both buddies are evicted (see zbud_reclaim_page() below). |
325 | */ |
326 | void zbud_free(struct zbud_pool *pool, unsigned long handle) |
327 | { |
328 | struct zbud_header *zhdr; |
329 | int freechunks; |
330 | |
331 | spin_lock(&pool->lock); |
332 | zhdr = handle_to_zbud_header(handle); |
333 | |
334 | /* If first buddy, handle will be page aligned */ |
335 | if ((handle - ZHDR_SIZE_ALIGNED) & ~PAGE_MASK) |
336 | zhdr->last_chunks = 0; |
337 | else |
338 | zhdr->first_chunks = 0; |
339 | |
340 | if (zhdr->under_reclaim) { |
341 | /* zbud page is under reclaim, reclaim will free */ |
342 | spin_unlock(&pool->lock); |
343 | return; |
344 | } |
345 | |
346 | /* Remove from existing buddy list */ |
347 | list_del(&zhdr->buddy); |
348 | |
349 | if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) { |
350 | /* zbud page is empty, free */ |
351 | list_del(&zhdr->lru); |
352 | free_zbud_page(zhdr); |
353 | pool->pages_nr--; |
354 | } else { |
355 | /* Add to unbuddied list */ |
356 | freechunks = num_free_chunks(zhdr); |
357 | list_add(&zhdr->buddy, &pool->unbuddied[freechunks]); |
358 | } |
359 | |
360 | spin_unlock(&pool->lock); |
361 | } |
362 | |
363 | #define list_tail_entry(ptr, type, member) \ |
364 | list_entry((ptr)->prev, type, member) |
365 | |
366 | /** |
367 | * zbud_reclaim_page() - evicts allocations from a pool page and frees it |
368 | * @pool: pool from which a page will attempt to be evicted |
369 | * @retires: number of pages on the LRU list for which eviction will |
370 | * be attempted before failing |
371 | * |
372 | * zbud reclaim is different from normal system reclaim in that the reclaim is |
373 | * done from the bottom, up. This is because only the bottom layer, zbud, has |
374 | * information on how the allocations are organized within each zbud page. This |
375 | * has the potential to create interesting locking situations between zbud and |
376 | * the user, however. |
377 | * |
378 | * To avoid these, this is how zbud_reclaim_page() should be called: |
379 | |
380 | * The user detects a page should be reclaimed and calls zbud_reclaim_page(). |
381 | * zbud_reclaim_page() will remove a zbud page from the pool LRU list and call |
382 | * the user-defined eviction handler with the pool and handle as arguments. |
383 | * |
384 | * If the handle can not be evicted, the eviction handler should return |
385 | * non-zero. zbud_reclaim_page() will add the zbud page back to the |
386 | * appropriate list and try the next zbud page on the LRU up to |
387 | * a user defined number of retries. |
388 | * |
389 | * If the handle is successfully evicted, the eviction handler should |
390 | * return 0 _and_ should have called zbud_free() on the handle. zbud_free() |
391 | * contains logic to delay freeing the page if the page is under reclaim, |
392 | * as indicated by the setting of the PG_reclaim flag on the underlying page. |
393 | * |
394 | * If all buddies in the zbud page are successfully evicted, then the |
395 | * zbud page can be freed. |
396 | * |
397 | * Returns: 0 if page is successfully freed, otherwise -EINVAL if there are |
398 | * no pages to evict or an eviction handler is not registered, -EAGAIN if |
399 | * the retry limit was hit. |
400 | */ |
401 | int zbud_reclaim_page(struct zbud_pool *pool, unsigned int retries) |
402 | { |
403 | int i, ret, freechunks; |
404 | struct zbud_header *zhdr; |
405 | unsigned long first_handle = 0, last_handle = 0; |
406 | |
407 | spin_lock(&pool->lock); |
408 | if (!pool->ops || !pool->ops->evict || list_empty(&pool->lru) || |
409 | retries == 0) { |
410 | spin_unlock(&pool->lock); |
411 | return -EINVAL; |
412 | } |
413 | for (i = 0; i < retries; i++) { |
414 | zhdr = list_tail_entry(&pool->lru, struct zbud_header, lru); |
415 | list_del(&zhdr->lru); |
416 | list_del(&zhdr->buddy); |
417 | /* Protect zbud page against free */ |
418 | zhdr->under_reclaim = true; |
419 | /* |
420 | * We need encode the handles before unlocking, since we can |
421 | * race with free that will set (first|last)_chunks to 0 |
422 | */ |
423 | first_handle = 0; |
424 | last_handle = 0; |
425 | if (zhdr->first_chunks) |
426 | first_handle = encode_handle(zhdr, FIRST); |
427 | if (zhdr->last_chunks) |
428 | last_handle = encode_handle(zhdr, LAST); |
429 | spin_unlock(&pool->lock); |
430 | |
431 | /* Issue the eviction callback(s) */ |
432 | if (first_handle) { |
433 | ret = pool->ops->evict(pool, first_handle); |
434 | if (ret) |
435 | goto next; |
436 | } |
437 | if (last_handle) { |
438 | ret = pool->ops->evict(pool, last_handle); |
439 | if (ret) |
440 | goto next; |
441 | } |
442 | next: |
443 | spin_lock(&pool->lock); |
444 | zhdr->under_reclaim = false; |
445 | if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) { |
446 | /* |
447 | * Both buddies are now free, free the zbud page and |
448 | * return success. |
449 | */ |
450 | free_zbud_page(zhdr); |
451 | pool->pages_nr--; |
452 | spin_unlock(&pool->lock); |
453 | return 0; |
454 | } else if (zhdr->first_chunks == 0 || |
455 | zhdr->last_chunks == 0) { |
456 | /* add to unbuddied list */ |
457 | freechunks = num_free_chunks(zhdr); |
458 | list_add(&zhdr->buddy, &pool->unbuddied[freechunks]); |
459 | } else { |
460 | /* add to buddied list */ |
461 | list_add(&zhdr->buddy, &pool->buddied); |
462 | } |
463 | |
464 | /* add to beginning of LRU */ |
465 | list_add(&zhdr->lru, &pool->lru); |
466 | } |
467 | spin_unlock(&pool->lock); |
468 | return -EAGAIN; |
469 | } |
470 | |
471 | /** |
472 | * zbud_map() - maps the allocation associated with the given handle |
473 | * @pool: pool in which the allocation resides |
474 | * @handle: handle associated with the allocation to be mapped |
475 | * |
476 | * While trivial for zbud, the mapping functions for others allocators |
477 | * implementing this allocation API could have more complex information encoded |
478 | * in the handle and could create temporary mappings to make the data |
479 | * accessible to the user. |
480 | * |
481 | * Returns: a pointer to the mapped allocation |
482 | */ |
483 | void *zbud_map(struct zbud_pool *pool, unsigned long handle) |
484 | { |
485 | return (void *)(handle); |
486 | } |
487 | |
488 | /** |
489 | * zbud_unmap() - maps the allocation associated with the given handle |
490 | * @pool: pool in which the allocation resides |
491 | * @handle: handle associated with the allocation to be unmapped |
492 | */ |
493 | void zbud_unmap(struct zbud_pool *pool, unsigned long handle) |
494 | { |
495 | } |
496 | |
497 | /** |
498 | * zbud_get_pool_size() - gets the zbud pool size in pages |
499 | * @pool: pool whose size is being queried |
500 | * |
501 | * Returns: size in pages of the given pool. The pool lock need not be |
502 | * taken to access pages_nr. |
503 | */ |
504 | u64 zbud_get_pool_size(struct zbud_pool *pool) |
505 | { |
506 | return pool->pages_nr; |
507 | } |
508 | |
509 | static int __init init_zbud(void) |
510 | { |
511 | /* Make sure the zbud header will fit in one chunk */ |
512 | BUILD_BUG_ON(sizeof(struct zbud_header) > ZHDR_SIZE_ALIGNED); |
513 | pr_info("loaded\n"); |
514 | return 0; |
515 | } |
516 | |
517 | static void __exit exit_zbud(void) |
518 | { |
519 | pr_info("unloaded\n"); |
520 | } |
521 | |
522 | module_init(init_zbud); |
523 | module_exit(exit_zbud); |
524 | |
525 | MODULE_LICENSE("GPL"); |
526 | MODULE_AUTHOR("Seth Jennings <sjenning@linux.vnet.ibm.com>"); |
527 | MODULE_DESCRIPTION("Buddy Allocator for Compressed Pages"); |
528 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9