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