1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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/zpool.h>
55
56
57
58
59
60
61
62
63
64
65
66
67
68#define NCHUNKS_ORDER 6
69
70#define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER)
71#define CHUNK_SIZE (1 << CHUNK_SHIFT)
72#define ZHDR_SIZE_ALIGNED CHUNK_SIZE
73#define NCHUNKS ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT)
74
75struct zbud_pool;
76
77struct zbud_ops {
78 int (*evict)(struct zbud_pool *pool, unsigned long handle);
79};
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101struct zbud_pool {
102 spinlock_t lock;
103 union {
104
105
106
107
108 struct list_head buddied;
109 struct list_head unbuddied[NCHUNKS];
110 };
111 struct list_head lru;
112 u64 pages_nr;
113 const struct zbud_ops *ops;
114 struct zpool *zpool;
115 const struct zpool_ops *zpool_ops;
116};
117
118
119
120
121
122
123
124
125
126struct zbud_header {
127 struct list_head buddy;
128 struct list_head lru;
129 unsigned int first_chunks;
130 unsigned int last_chunks;
131 bool under_reclaim;
132};
133
134
135
136
137
138enum buddy {
139 FIRST,
140 LAST
141};
142
143
144static int size_to_chunks(size_t size)
145{
146 return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT;
147}
148
149#define for_each_unbuddied_list(_iter, _begin) \
150 for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
151
152
153static struct zbud_header *init_zbud_page(struct page *page)
154{
155 struct zbud_header *zhdr = page_address(page);
156 zhdr->first_chunks = 0;
157 zhdr->last_chunks = 0;
158 INIT_LIST_HEAD(&zhdr->buddy);
159 INIT_LIST_HEAD(&zhdr->lru);
160 zhdr->under_reclaim = false;
161 return zhdr;
162}
163
164
165static void free_zbud_page(struct zbud_header *zhdr)
166{
167 __free_page(virt_to_page(zhdr));
168}
169
170
171
172
173
174static unsigned long encode_handle(struct zbud_header *zhdr, enum buddy bud)
175{
176 unsigned long handle;
177
178
179
180
181
182
183
184 handle = (unsigned long)zhdr;
185 if (bud == FIRST)
186
187 handle += ZHDR_SIZE_ALIGNED;
188 else
189 handle += PAGE_SIZE - (zhdr->last_chunks << CHUNK_SHIFT);
190 return handle;
191}
192
193
194static struct zbud_header *handle_to_zbud_header(unsigned long handle)
195{
196 return (struct zbud_header *)(handle & PAGE_MASK);
197}
198
199
200static int num_free_chunks(struct zbud_header *zhdr)
201{
202
203
204
205
206 return NCHUNKS - zhdr->first_chunks - zhdr->last_chunks;
207}
208
209
210
211
212
213
214
215
216
217
218
219
220static struct zbud_pool *zbud_create_pool(gfp_t gfp, const struct zbud_ops *ops)
221{
222 struct zbud_pool *pool;
223 int i;
224
225 pool = kzalloc(sizeof(struct zbud_pool), gfp);
226 if (!pool)
227 return NULL;
228 spin_lock_init(&pool->lock);
229 for_each_unbuddied_list(i, 0)
230 INIT_LIST_HEAD(&pool->unbuddied[i]);
231 INIT_LIST_HEAD(&pool->buddied);
232 INIT_LIST_HEAD(&pool->lru);
233 pool->pages_nr = 0;
234 pool->ops = ops;
235 return pool;
236}
237
238
239
240
241
242
243
244static void zbud_destroy_pool(struct zbud_pool *pool)
245{
246 kfree(pool);
247}
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268static int zbud_alloc(struct zbud_pool *pool, size_t size, gfp_t gfp,
269 unsigned long *handle)
270{
271 int chunks, i, freechunks;
272 struct zbud_header *zhdr = NULL;
273 enum buddy bud;
274 struct page *page;
275
276 if (!size || (gfp & __GFP_HIGHMEM))
277 return -EINVAL;
278 if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE)
279 return -ENOSPC;
280 chunks = size_to_chunks(size);
281 spin_lock(&pool->lock);
282
283
284 for_each_unbuddied_list(i, chunks) {
285 if (!list_empty(&pool->unbuddied[i])) {
286 zhdr = list_first_entry(&pool->unbuddied[i],
287 struct zbud_header, buddy);
288 list_del(&zhdr->buddy);
289 if (zhdr->first_chunks == 0)
290 bud = FIRST;
291 else
292 bud = LAST;
293 goto found;
294 }
295 }
296
297
298 spin_unlock(&pool->lock);
299 page = alloc_page(gfp);
300 if (!page)
301 return -ENOMEM;
302 spin_lock(&pool->lock);
303 pool->pages_nr++;
304 zhdr = init_zbud_page(page);
305 bud = FIRST;
306
307found:
308 if (bud == FIRST)
309 zhdr->first_chunks = chunks;
310 else
311 zhdr->last_chunks = chunks;
312
313 if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0) {
314
315 freechunks = num_free_chunks(zhdr);
316 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
317 } else {
318
319 list_add(&zhdr->buddy, &pool->buddied);
320 }
321
322
323 if (!list_empty(&zhdr->lru))
324 list_del(&zhdr->lru);
325 list_add(&zhdr->lru, &pool->lru);
326
327 *handle = encode_handle(zhdr, bud);
328 spin_unlock(&pool->lock);
329
330 return 0;
331}
332
333
334
335
336
337
338
339
340
341
342
343static void zbud_free(struct zbud_pool *pool, unsigned long handle)
344{
345 struct zbud_header *zhdr;
346 int freechunks;
347
348 spin_lock(&pool->lock);
349 zhdr = handle_to_zbud_header(handle);
350
351
352 if ((handle - ZHDR_SIZE_ALIGNED) & ~PAGE_MASK)
353 zhdr->last_chunks = 0;
354 else
355 zhdr->first_chunks = 0;
356
357 if (zhdr->under_reclaim) {
358
359 spin_unlock(&pool->lock);
360 return;
361 }
362
363
364 list_del(&zhdr->buddy);
365
366 if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
367
368 list_del(&zhdr->lru);
369 free_zbud_page(zhdr);
370 pool->pages_nr--;
371 } else {
372
373 freechunks = num_free_chunks(zhdr);
374 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
375 }
376
377 spin_unlock(&pool->lock);
378}
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415static int zbud_reclaim_page(struct zbud_pool *pool, unsigned int retries)
416{
417 int i, ret, freechunks;
418 struct zbud_header *zhdr;
419 unsigned long first_handle = 0, last_handle = 0;
420
421 spin_lock(&pool->lock);
422 if (!pool->ops || !pool->ops->evict || list_empty(&pool->lru) ||
423 retries == 0) {
424 spin_unlock(&pool->lock);
425 return -EINVAL;
426 }
427 for (i = 0; i < retries; i++) {
428 zhdr = list_last_entry(&pool->lru, struct zbud_header, lru);
429 list_del(&zhdr->lru);
430 list_del(&zhdr->buddy);
431
432 zhdr->under_reclaim = true;
433
434
435
436
437 first_handle = 0;
438 last_handle = 0;
439 if (zhdr->first_chunks)
440 first_handle = encode_handle(zhdr, FIRST);
441 if (zhdr->last_chunks)
442 last_handle = encode_handle(zhdr, LAST);
443 spin_unlock(&pool->lock);
444
445
446 if (first_handle) {
447 ret = pool->ops->evict(pool, first_handle);
448 if (ret)
449 goto next;
450 }
451 if (last_handle) {
452 ret = pool->ops->evict(pool, last_handle);
453 if (ret)
454 goto next;
455 }
456next:
457 spin_lock(&pool->lock);
458 zhdr->under_reclaim = false;
459 if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
460
461
462
463
464 free_zbud_page(zhdr);
465 pool->pages_nr--;
466 spin_unlock(&pool->lock);
467 return 0;
468 } else if (zhdr->first_chunks == 0 ||
469 zhdr->last_chunks == 0) {
470
471 freechunks = num_free_chunks(zhdr);
472 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
473 } else {
474
475 list_add(&zhdr->buddy, &pool->buddied);
476 }
477
478
479 list_add(&zhdr->lru, &pool->lru);
480 }
481 spin_unlock(&pool->lock);
482 return -EAGAIN;
483}
484
485
486
487
488
489
490
491
492
493
494
495
496
497static void *zbud_map(struct zbud_pool *pool, unsigned long handle)
498{
499 return (void *)(handle);
500}
501
502
503
504
505
506
507static void zbud_unmap(struct zbud_pool *pool, unsigned long handle)
508{
509}
510
511
512
513
514
515
516
517
518static u64 zbud_get_pool_size(struct zbud_pool *pool)
519{
520 return pool->pages_nr;
521}
522
523
524
525
526
527static int zbud_zpool_evict(struct zbud_pool *pool, unsigned long handle)
528{
529 if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict)
530 return pool->zpool_ops->evict(pool->zpool, handle);
531 else
532 return -ENOENT;
533}
534
535static const struct zbud_ops zbud_zpool_ops = {
536 .evict = zbud_zpool_evict
537};
538
539static void *zbud_zpool_create(const char *name, gfp_t gfp,
540 const struct zpool_ops *zpool_ops,
541 struct zpool *zpool)
542{
543 struct zbud_pool *pool;
544
545 pool = zbud_create_pool(gfp, zpool_ops ? &zbud_zpool_ops : NULL);
546 if (pool) {
547 pool->zpool = zpool;
548 pool->zpool_ops = zpool_ops;
549 }
550 return pool;
551}
552
553static void zbud_zpool_destroy(void *pool)
554{
555 zbud_destroy_pool(pool);
556}
557
558static int zbud_zpool_malloc(void *pool, size_t size, gfp_t gfp,
559 unsigned long *handle)
560{
561 return zbud_alloc(pool, size, gfp, handle);
562}
563static void zbud_zpool_free(void *pool, unsigned long handle)
564{
565 zbud_free(pool, handle);
566}
567
568static int zbud_zpool_shrink(void *pool, unsigned int pages,
569 unsigned int *reclaimed)
570{
571 unsigned int total = 0;
572 int ret = -EINVAL;
573
574 while (total < pages) {
575 ret = zbud_reclaim_page(pool, 8);
576 if (ret < 0)
577 break;
578 total++;
579 }
580
581 if (reclaimed)
582 *reclaimed = total;
583
584 return ret;
585}
586
587static void *zbud_zpool_map(void *pool, unsigned long handle,
588 enum zpool_mapmode mm)
589{
590 return zbud_map(pool, handle);
591}
592static void zbud_zpool_unmap(void *pool, unsigned long handle)
593{
594 zbud_unmap(pool, handle);
595}
596
597static u64 zbud_zpool_total_size(void *pool)
598{
599 return zbud_get_pool_size(pool) * PAGE_SIZE;
600}
601
602static struct zpool_driver zbud_zpool_driver = {
603 .type = "zbud",
604 .sleep_mapped = true,
605 .owner = THIS_MODULE,
606 .create = zbud_zpool_create,
607 .destroy = zbud_zpool_destroy,
608 .malloc = zbud_zpool_malloc,
609 .free = zbud_zpool_free,
610 .shrink = zbud_zpool_shrink,
611 .map = zbud_zpool_map,
612 .unmap = zbud_zpool_unmap,
613 .total_size = zbud_zpool_total_size,
614};
615
616MODULE_ALIAS("zpool-zbud");
617
618static int __init init_zbud(void)
619{
620
621 BUILD_BUG_ON(sizeof(struct zbud_header) > ZHDR_SIZE_ALIGNED);
622 pr_info("loaded\n");
623
624 zpool_register_driver(&zbud_zpool_driver);
625
626 return 0;
627}
628
629static void __exit exit_zbud(void)
630{
631 zpool_unregister_driver(&zbud_zpool_driver);
632 pr_info("unloaded\n");
633}
634
635module_init(init_zbud);
636module_exit(exit_zbud);
637
638MODULE_LICENSE("GPL");
639MODULE_AUTHOR("Seth Jennings <sjennings@variantweb.net>");
640MODULE_DESCRIPTION("Buddy Allocator for Compressed Pages");
641