blob: b72403927aa4b06610cb08e9506d677c98a1a5cd [file] [log] [blame]
Nitin Gupta61989a82012-01-09 16:51:56 -06001/*
2 * zsmalloc memory allocator
3 *
4 * Copyright (C) 2011 Nitin Gupta
Minchan Kim31fc00b2014-01-30 15:45:55 -08005 * Copyright (C) 2012, 2013 Minchan Kim
Nitin Gupta61989a82012-01-09 16:51:56 -06006 *
7 * This code is released using a dual license strategy: BSD/GPL
8 * You can choose the license that better fits your requirements.
9 *
10 * Released under the terms of 3-clause BSD License
11 * Released under the terms of GNU General Public License Version 2.0
12 */
13
Nitin Gupta2db51da2012-06-09 17:41:14 -070014/*
Nitin Cuptac3e3e882013-12-11 11:04:37 +090015 * This allocator is designed for use with zram. Thus, the allocator is
16 * supposed to work well under low memory conditions. In particular, it
17 * never attempts higher order page allocation which is very likely to
18 * fail under memory pressure. On the other hand, if we just use single
19 * (0-order) pages, it would suffer from very high fragmentation --
20 * any object of size PAGE_SIZE/2 or larger would occupy an entire page.
21 * This was one of the major issues with its predecessor (xvmalloc).
Nitin Gupta2db51da2012-06-09 17:41:14 -070022 *
23 * To overcome these issues, zsmalloc allocates a bunch of 0-order pages
24 * and links them together using various 'struct page' fields. These linked
25 * pages act as a single higher-order page i.e. an object can span 0-order
26 * page boundaries. The code refers to these linked pages as a single entity
27 * called zspage.
28 *
Nitin Cuptac3e3e882013-12-11 11:04:37 +090029 * For simplicity, zsmalloc can only allocate objects of size up to PAGE_SIZE
30 * since this satisfies the requirements of all its current users (in the
31 * worst case, page is incompressible and is thus stored "as-is" i.e. in
32 * uncompressed form). For allocation requests larger than this size, failure
33 * is returned (see zs_malloc).
34 *
35 * Additionally, zs_malloc() does not return a dereferenceable pointer.
36 * Instead, it returns an opaque handle (unsigned long) which encodes actual
37 * location of the allocated object. The reason for this indirection is that
38 * zsmalloc does not keep zspages permanently mapped since that would cause
39 * issues on 32-bit systems where the VA region for kernel space mappings
40 * is very small. So, before using the allocating memory, the object has to
41 * be mapped using zs_map_object() to get a usable pointer and subsequently
42 * unmapped using zs_unmap_object().
43 *
Nitin Gupta2db51da2012-06-09 17:41:14 -070044 * Following is how we use various fields and flags of underlying
45 * struct page(s) to form a zspage.
46 *
47 * Usage of struct page fields:
48 * page->first_page: points to the first component (0-order) page
49 * page->index (union with page->freelist): offset of the first object
50 * starting in this page. For the first page, this is
51 * always 0, so we use this field (aka freelist) to point
52 * to the first free object in zspage.
53 * page->lru: links together all component pages (except the first page)
54 * of a zspage
55 *
56 * For _first_ page only:
57 *
58 * page->private (union with page->first_page): refers to the
59 * component page after the first page
60 * page->freelist: points to the first free object in zspage.
61 * Free objects are linked together using in-place
62 * metadata.
63 * page->objects: maximum number of objects we can store in this
64 * zspage (class->zspage_order * PAGE_SIZE / class->size)
65 * page->lru: links together first pages of various zspages.
66 * Basically forming list of zspages in a fullness group.
67 * page->mapping: class index and fullness group of the zspage
68 *
69 * Usage of struct page flags:
70 * PG_private: identifies the first component page
71 * PG_private2: identifies the last component page
72 *
73 */
74
Nitin Gupta61989a82012-01-09 16:51:56 -060075#ifdef CONFIG_ZSMALLOC_DEBUG
76#define DEBUG
77#endif
78
79#include <linux/module.h>
80#include <linux/kernel.h>
81#include <linux/bitops.h>
82#include <linux/errno.h>
83#include <linux/highmem.h>
Nitin Gupta61989a82012-01-09 16:51:56 -060084#include <linux/string.h>
85#include <linux/slab.h>
86#include <asm/tlbflush.h>
87#include <asm/pgtable.h>
88#include <linux/cpumask.h>
89#include <linux/cpu.h>
Seth Jennings0cbb6132012-02-13 08:47:49 -060090#include <linux/vmalloc.h>
Seth Jenningsc60369f2012-07-18 11:55:55 -050091#include <linux/hardirq.h>
Seth Jennings0959c632012-08-08 15:12:17 +090092#include <linux/spinlock.h>
93#include <linux/types.h>
Minchan Kimbcf16472014-01-30 15:45:50 -080094#include <linux/zsmalloc.h>
Dan Streetmanc7957792014-08-06 16:08:38 -070095#include <linux/zpool.h>
Seth Jennings0959c632012-08-08 15:12:17 +090096
97/*
98 * This must be power of 2 and greater than of equal to sizeof(link_free).
99 * These two conditions ensure that any 'struct link_free' itself doesn't
100 * span more than 1 page which avoids complex case of mapping 2 pages simply
101 * to restore link_free pointer values.
102 */
103#define ZS_ALIGN 8
104
105/*
106 * A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
107 * pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
108 */
109#define ZS_MAX_ZSPAGE_ORDER 2
110#define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
111
112/*
113 * Object location (<PFN>, <obj_idx>) is encoded as
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900114 * as single (unsigned long) handle value.
Seth Jennings0959c632012-08-08 15:12:17 +0900115 *
116 * Note that object index <obj_idx> is relative to system
117 * page <PFN> it is stored in, so for each sub-page belonging
118 * to a zspage, obj_idx starts with 0.
119 *
120 * This is made more complicated by various memory models and PAE.
121 */
122
123#ifndef MAX_PHYSMEM_BITS
124#ifdef CONFIG_HIGHMEM64G
125#define MAX_PHYSMEM_BITS 36
126#else /* !CONFIG_HIGHMEM64G */
127/*
128 * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
129 * be PAGE_SHIFT
130 */
131#define MAX_PHYSMEM_BITS BITS_PER_LONG
132#endif
133#endif
134#define _PFN_BITS (MAX_PHYSMEM_BITS - PAGE_SHIFT)
135#define OBJ_INDEX_BITS (BITS_PER_LONG - _PFN_BITS)
136#define OBJ_INDEX_MASK ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
137
138#define MAX(a, b) ((a) >= (b) ? (a) : (b))
139/* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
140#define ZS_MIN_ALLOC_SIZE \
141 MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
142#define ZS_MAX_ALLOC_SIZE PAGE_SIZE
143
144/*
Weijie Yang7eb52512014-06-04 16:11:08 -0700145 * On systems with 4K page size, this gives 255 size classes! There is a
Seth Jennings0959c632012-08-08 15:12:17 +0900146 * trader-off here:
147 * - Large number of size classes is potentially wasteful as free page are
148 * spread across these classes
149 * - Small number of size classes causes large internal fragmentation
150 * - Probably its better to use specific size classes (empirically
151 * determined). NOTE: all those class sizes must be set as multiple of
152 * ZS_ALIGN to make sure link_free itself never has to span 2 pages.
153 *
154 * ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
155 * (reason above)
156 */
Seth Jenningsd662b8e2013-01-25 11:46:18 -0600157#define ZS_SIZE_CLASS_DELTA (PAGE_SIZE >> 8)
Seth Jennings0959c632012-08-08 15:12:17 +0900158
159/*
160 * We do not maintain any list for completely empty or full pages
161 */
162enum fullness_group {
163 ZS_ALMOST_FULL,
164 ZS_ALMOST_EMPTY,
165 _ZS_NR_FULLNESS_GROUPS,
166
167 ZS_EMPTY,
168 ZS_FULL
169};
170
171/*
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -0800172 * number of size_classes
173 */
174static int zs_size_classes;
175
176/*
Seth Jennings0959c632012-08-08 15:12:17 +0900177 * We assign a page to ZS_ALMOST_EMPTY fullness group when:
178 * n <= N / f, where
179 * n = number of allocated objects
180 * N = total number of objects zspage can store
Wang Sheng-Hui6dd97372014-10-09 15:29:59 -0700181 * f = fullness_threshold_frac
Seth Jennings0959c632012-08-08 15:12:17 +0900182 *
183 * Similarly, we assign zspage to:
184 * ZS_ALMOST_FULL when n > N / f
185 * ZS_EMPTY when n == 0
186 * ZS_FULL when n == N
187 *
188 * (see: fix_fullness_group())
189 */
190static const int fullness_threshold_frac = 4;
191
192struct size_class {
193 /*
194 * Size of objects stored in this class. Must be multiple
195 * of ZS_ALIGN.
196 */
197 int size;
198 unsigned int index;
199
200 /* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
201 int pages_per_zspage;
202
203 spinlock_t lock;
204
Seth Jennings0959c632012-08-08 15:12:17 +0900205 struct page *fullness_list[_ZS_NR_FULLNESS_GROUPS];
206};
207
208/*
209 * Placed within free objects to form a singly linked list.
210 * For every zspage, first_page->freelist gives head of this list.
211 *
212 * This must be power of 2 and less than or equal to ZS_ALIGN
213 */
214struct link_free {
215 /* Handle of next free chunk (encodes <PFN, obj_idx>) */
216 void *next;
217};
218
219struct zs_pool {
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -0800220 struct size_class **size_class;
Seth Jennings0959c632012-08-08 15:12:17 +0900221
222 gfp_t flags; /* allocation flags used when growing pool */
Minchan Kim13de8932014-10-09 15:29:48 -0700223 atomic_long_t pages_allocated;
Seth Jennings0959c632012-08-08 15:12:17 +0900224};
Nitin Gupta61989a82012-01-09 16:51:56 -0600225
226/*
227 * A zspage's class index and fullness group
228 * are encoded in its (first)page->mapping
229 */
230#define CLASS_IDX_BITS 28
231#define FULLNESS_BITS 4
232#define CLASS_IDX_MASK ((1 << CLASS_IDX_BITS) - 1)
233#define FULLNESS_MASK ((1 << FULLNESS_BITS) - 1)
234
Seth Jenningsf5536462012-07-18 11:55:56 -0500235struct mapping_area {
Minchan Kim1b945ae2013-12-11 11:04:36 +0900236#ifdef CONFIG_PGTABLE_MAPPING
Seth Jenningsf5536462012-07-18 11:55:56 -0500237 struct vm_struct *vm; /* vm area for mapping object that span pages */
238#else
239 char *vm_buf; /* copy buffer for objects that span pages */
240#endif
241 char *vm_addr; /* address of kmap_atomic()'ed pages */
242 enum zs_mapmode vm_mm; /* mapping mode */
243};
244
Dan Streetmanc7957792014-08-06 16:08:38 -0700245/* zpool driver */
246
247#ifdef CONFIG_ZPOOL
248
249static void *zs_zpool_create(gfp_t gfp, struct zpool_ops *zpool_ops)
250{
251 return zs_create_pool(gfp);
252}
253
254static void zs_zpool_destroy(void *pool)
255{
256 zs_destroy_pool(pool);
257}
258
259static int zs_zpool_malloc(void *pool, size_t size, gfp_t gfp,
260 unsigned long *handle)
261{
262 *handle = zs_malloc(pool, size);
263 return *handle ? 0 : -1;
264}
265static void zs_zpool_free(void *pool, unsigned long handle)
266{
267 zs_free(pool, handle);
268}
269
270static int zs_zpool_shrink(void *pool, unsigned int pages,
271 unsigned int *reclaimed)
272{
273 return -EINVAL;
274}
275
276static void *zs_zpool_map(void *pool, unsigned long handle,
277 enum zpool_mapmode mm)
278{
279 enum zs_mapmode zs_mm;
280
281 switch (mm) {
282 case ZPOOL_MM_RO:
283 zs_mm = ZS_MM_RO;
284 break;
285 case ZPOOL_MM_WO:
286 zs_mm = ZS_MM_WO;
287 break;
288 case ZPOOL_MM_RW: /* fallthru */
289 default:
290 zs_mm = ZS_MM_RW;
291 break;
292 }
293
294 return zs_map_object(pool, handle, zs_mm);
295}
296static void zs_zpool_unmap(void *pool, unsigned long handle)
297{
298 zs_unmap_object(pool, handle);
299}
300
301static u64 zs_zpool_total_size(void *pool)
302{
Minchan Kim722cdc12014-10-09 15:29:50 -0700303 return zs_get_total_pages(pool) << PAGE_SHIFT;
Dan Streetmanc7957792014-08-06 16:08:38 -0700304}
305
306static struct zpool_driver zs_zpool_driver = {
307 .type = "zsmalloc",
308 .owner = THIS_MODULE,
309 .create = zs_zpool_create,
310 .destroy = zs_zpool_destroy,
311 .malloc = zs_zpool_malloc,
312 .free = zs_zpool_free,
313 .shrink = zs_zpool_shrink,
314 .map = zs_zpool_map,
315 .unmap = zs_zpool_unmap,
316 .total_size = zs_zpool_total_size,
317};
318
Kees Cook137f8cf2014-08-29 15:18:40 -0700319MODULE_ALIAS("zpool-zsmalloc");
Dan Streetmanc7957792014-08-06 16:08:38 -0700320#endif /* CONFIG_ZPOOL */
321
Nitin Gupta61989a82012-01-09 16:51:56 -0600322/* per-cpu VM mapping areas for zspage accesses that cross page boundaries */
323static DEFINE_PER_CPU(struct mapping_area, zs_map_area);
324
325static int is_first_page(struct page *page)
326{
Minchan Kima27545bf2012-04-25 15:23:09 +0900327 return PagePrivate(page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600328}
329
330static int is_last_page(struct page *page)
331{
Minchan Kima27545bf2012-04-25 15:23:09 +0900332 return PagePrivate2(page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600333}
334
335static void get_zspage_mapping(struct page *page, unsigned int *class_idx,
336 enum fullness_group *fullness)
337{
338 unsigned long m;
339 BUG_ON(!is_first_page(page));
340
341 m = (unsigned long)page->mapping;
342 *fullness = m & FULLNESS_MASK;
343 *class_idx = (m >> FULLNESS_BITS) & CLASS_IDX_MASK;
344}
345
346static void set_zspage_mapping(struct page *page, unsigned int class_idx,
347 enum fullness_group fullness)
348{
349 unsigned long m;
350 BUG_ON(!is_first_page(page));
351
352 m = ((class_idx & CLASS_IDX_MASK) << FULLNESS_BITS) |
353 (fullness & FULLNESS_MASK);
354 page->mapping = (struct address_space *)m;
355}
356
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900357/*
358 * zsmalloc divides the pool into various size classes where each
359 * class maintains a list of zspages where each zspage is divided
360 * into equal sized chunks. Each allocation falls into one of these
361 * classes depending on its size. This function returns index of the
362 * size class which has chunk size big enough to hold the give size.
363 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600364static int get_size_class_index(int size)
365{
366 int idx = 0;
367
368 if (likely(size > ZS_MIN_ALLOC_SIZE))
369 idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE,
370 ZS_SIZE_CLASS_DELTA);
371
372 return idx;
373}
374
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900375/*
376 * For each size class, zspages are divided into different groups
377 * depending on how "full" they are. This was done so that we could
378 * easily find empty or nearly empty zspages when we try to shrink
379 * the pool (not yet implemented). This function returns fullness
380 * status of the given page.
381 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600382static enum fullness_group get_fullness_group(struct page *page)
383{
384 int inuse, max_objects;
385 enum fullness_group fg;
386 BUG_ON(!is_first_page(page));
387
388 inuse = page->inuse;
389 max_objects = page->objects;
390
391 if (inuse == 0)
392 fg = ZS_EMPTY;
393 else if (inuse == max_objects)
394 fg = ZS_FULL;
395 else if (inuse <= max_objects / fullness_threshold_frac)
396 fg = ZS_ALMOST_EMPTY;
397 else
398 fg = ZS_ALMOST_FULL;
399
400 return fg;
401}
402
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900403/*
404 * Each size class maintains various freelists and zspages are assigned
405 * to one of these freelists based on the number of live objects they
406 * have. This functions inserts the given zspage into the freelist
407 * identified by <class, fullness_group>.
408 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600409static void insert_zspage(struct page *page, struct size_class *class,
410 enum fullness_group fullness)
411{
412 struct page **head;
413
414 BUG_ON(!is_first_page(page));
415
416 if (fullness >= _ZS_NR_FULLNESS_GROUPS)
417 return;
418
419 head = &class->fullness_list[fullness];
420 if (*head)
421 list_add_tail(&page->lru, &(*head)->lru);
422
423 *head = page;
424}
425
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900426/*
427 * This function removes the given zspage from the freelist identified
428 * by <class, fullness_group>.
429 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600430static void remove_zspage(struct page *page, struct size_class *class,
431 enum fullness_group fullness)
432{
433 struct page **head;
434
435 BUG_ON(!is_first_page(page));
436
437 if (fullness >= _ZS_NR_FULLNESS_GROUPS)
438 return;
439
440 head = &class->fullness_list[fullness];
441 BUG_ON(!*head);
442 if (list_empty(&(*head)->lru))
443 *head = NULL;
444 else if (*head == page)
445 *head = (struct page *)list_entry((*head)->lru.next,
446 struct page, lru);
447
448 list_del_init(&page->lru);
449}
450
Nitin Cuptac3e3e882013-12-11 11:04:37 +0900451/*
452 * Each size class maintains zspages in different fullness groups depending
453 * on the number of live objects they contain. When allocating or freeing
454 * objects, the fullness status of the page can change, say, from ALMOST_FULL
455 * to ALMOST_EMPTY when freeing an object. This function checks if such
456 * a status change has occurred for the given page and accordingly moves the
457 * page from the freelist of the old fullness group to that of the new
458 * fullness group.
459 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600460static enum fullness_group fix_fullness_group(struct zs_pool *pool,
461 struct page *page)
462{
463 int class_idx;
464 struct size_class *class;
465 enum fullness_group currfg, newfg;
466
467 BUG_ON(!is_first_page(page));
468
469 get_zspage_mapping(page, &class_idx, &currfg);
470 newfg = get_fullness_group(page);
471 if (newfg == currfg)
472 goto out;
473
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -0800474 class = pool->size_class[class_idx];
Nitin Gupta61989a82012-01-09 16:51:56 -0600475 remove_zspage(page, class, currfg);
476 insert_zspage(page, class, newfg);
477 set_zspage_mapping(page, class_idx, newfg);
478
479out:
480 return newfg;
481}
482
483/*
484 * We have to decide on how many pages to link together
485 * to form a zspage for each size class. This is important
486 * to reduce wastage due to unusable space left at end of
487 * each zspage which is given as:
488 * wastage = Zp - Zp % size_class
489 * where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ...
490 *
491 * For example, for size class of 3/8 * PAGE_SIZE, we should
492 * link together 3 PAGE_SIZE sized pages to form a zspage
493 * since then we can perfectly fit in 8 such objects.
494 */
Minchan Kim2e3b6152012-05-03 15:40:39 +0900495static int get_pages_per_zspage(int class_size)
Nitin Gupta61989a82012-01-09 16:51:56 -0600496{
497 int i, max_usedpc = 0;
498 /* zspage order which gives maximum used size per KB */
499 int max_usedpc_order = 1;
500
Seth Jennings84d4faa2012-03-05 11:33:21 -0600501 for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) {
Nitin Gupta61989a82012-01-09 16:51:56 -0600502 int zspage_size;
503 int waste, usedpc;
504
505 zspage_size = i * PAGE_SIZE;
506 waste = zspage_size % class_size;
507 usedpc = (zspage_size - waste) * 100 / zspage_size;
508
509 if (usedpc > max_usedpc) {
510 max_usedpc = usedpc;
511 max_usedpc_order = i;
512 }
513 }
514
515 return max_usedpc_order;
516}
517
518/*
519 * A single 'zspage' is composed of many system pages which are
520 * linked together using fields in struct page. This function finds
521 * the first/head page, given any component page of a zspage.
522 */
523static struct page *get_first_page(struct page *page)
524{
525 if (is_first_page(page))
526 return page;
527 else
528 return page->first_page;
529}
530
531static struct page *get_next_page(struct page *page)
532{
533 struct page *next;
534
535 if (is_last_page(page))
536 next = NULL;
537 else if (is_first_page(page))
Sunghan Suhe842b972013-07-12 16:08:13 +0900538 next = (struct page *)page_private(page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600539 else
540 next = list_entry(page->lru.next, struct page, lru);
541
542 return next;
543}
544
Olav Haugan67296872013-11-22 09:30:41 -0800545/*
546 * Encode <page, obj_idx> as a single handle value.
547 * On hardware platforms with physical memory starting at 0x0 the pfn
548 * could be 0 so we ensure that the handle will never be 0 by adjusting the
549 * encoded obj_idx value before encoding.
550 */
Nitin Gupta61989a82012-01-09 16:51:56 -0600551static void *obj_location_to_handle(struct page *page, unsigned long obj_idx)
552{
553 unsigned long handle;
554
555 if (!page) {
556 BUG_ON(obj_idx);
557 return NULL;
558 }
559
560 handle = page_to_pfn(page) << OBJ_INDEX_BITS;
Olav Haugan67296872013-11-22 09:30:41 -0800561 handle |= ((obj_idx + 1) & OBJ_INDEX_MASK);
Nitin Gupta61989a82012-01-09 16:51:56 -0600562
563 return (void *)handle;
564}
565
Olav Haugan67296872013-11-22 09:30:41 -0800566/*
567 * Decode <page, obj_idx> pair from the given object handle. We adjust the
568 * decoded obj_idx back to its original value since it was adjusted in
569 * obj_location_to_handle().
570 */
Minchan Kimc2344342012-06-08 15:39:25 +0900571static void obj_handle_to_location(unsigned long handle, struct page **page,
Nitin Gupta61989a82012-01-09 16:51:56 -0600572 unsigned long *obj_idx)
573{
Minchan Kimc2344342012-06-08 15:39:25 +0900574 *page = pfn_to_page(handle >> OBJ_INDEX_BITS);
Olav Haugan67296872013-11-22 09:30:41 -0800575 *obj_idx = (handle & OBJ_INDEX_MASK) - 1;
Nitin Gupta61989a82012-01-09 16:51:56 -0600576}
577
578static unsigned long obj_idx_to_offset(struct page *page,
579 unsigned long obj_idx, int class_size)
580{
581 unsigned long off = 0;
582
583 if (!is_first_page(page))
584 off = page->index;
585
586 return off + obj_idx * class_size;
587}
588
Nitin Guptaf4477e92012-04-02 09:13:56 -0500589static void reset_page(struct page *page)
590{
591 clear_bit(PG_private, &page->flags);
592 clear_bit(PG_private_2, &page->flags);
593 set_page_private(page, 0);
594 page->mapping = NULL;
595 page->freelist = NULL;
Mel Gorman22b751c2013-02-22 16:34:59 -0800596 page_mapcount_reset(page);
Nitin Guptaf4477e92012-04-02 09:13:56 -0500597}
598
Nitin Gupta61989a82012-01-09 16:51:56 -0600599static void free_zspage(struct page *first_page)
600{
Nitin Guptaf4477e92012-04-02 09:13:56 -0500601 struct page *nextp, *tmp, *head_extra;
Nitin Gupta61989a82012-01-09 16:51:56 -0600602
603 BUG_ON(!is_first_page(first_page));
604 BUG_ON(first_page->inuse);
605
Nitin Guptaf4477e92012-04-02 09:13:56 -0500606 head_extra = (struct page *)page_private(first_page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600607
Nitin Guptaf4477e92012-04-02 09:13:56 -0500608 reset_page(first_page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600609 __free_page(first_page);
610
611 /* zspage with only 1 system page */
Nitin Guptaf4477e92012-04-02 09:13:56 -0500612 if (!head_extra)
Nitin Gupta61989a82012-01-09 16:51:56 -0600613 return;
614
Nitin Guptaf4477e92012-04-02 09:13:56 -0500615 list_for_each_entry_safe(nextp, tmp, &head_extra->lru, lru) {
Nitin Gupta61989a82012-01-09 16:51:56 -0600616 list_del(&nextp->lru);
Nitin Guptaf4477e92012-04-02 09:13:56 -0500617 reset_page(nextp);
Nitin Gupta61989a82012-01-09 16:51:56 -0600618 __free_page(nextp);
619 }
Nitin Guptaf4477e92012-04-02 09:13:56 -0500620 reset_page(head_extra);
621 __free_page(head_extra);
Nitin Gupta61989a82012-01-09 16:51:56 -0600622}
623
624/* Initialize a newly allocated zspage */
625static void init_zspage(struct page *first_page, struct size_class *class)
626{
627 unsigned long off = 0;
628 struct page *page = first_page;
629
630 BUG_ON(!is_first_page(first_page));
631 while (page) {
632 struct page *next_page;
633 struct link_free *link;
Dan Streetman5538c562014-10-09 15:30:01 -0700634 unsigned int i = 1;
Minchan Kimaf4ee5e2014-12-12 16:56:58 -0800635 void *vaddr;
Nitin Gupta61989a82012-01-09 16:51:56 -0600636
637 /*
638 * page->index stores offset of first object starting
639 * in the page. For the first page, this is always 0,
640 * so we use first_page->index (aka ->freelist) to store
641 * head of corresponding zspage's freelist.
642 */
643 if (page != first_page)
644 page->index = off;
645
Minchan Kimaf4ee5e2014-12-12 16:56:58 -0800646 vaddr = kmap_atomic(page);
647 link = (struct link_free *)vaddr + off / sizeof(*link);
Nitin Gupta61989a82012-01-09 16:51:56 -0600648
Dan Streetman5538c562014-10-09 15:30:01 -0700649 while ((off += class->size) < PAGE_SIZE) {
650 link->next = obj_location_to_handle(page, i++);
651 link += class->size / sizeof(*link);
Nitin Gupta61989a82012-01-09 16:51:56 -0600652 }
653
654 /*
655 * We now come to the last (full or partial) object on this
656 * page, which must point to the first object on the next
657 * page (if present)
658 */
659 next_page = get_next_page(page);
660 link->next = obj_location_to_handle(next_page, 0);
Minchan Kimaf4ee5e2014-12-12 16:56:58 -0800661 kunmap_atomic(vaddr);
Nitin Gupta61989a82012-01-09 16:51:56 -0600662 page = next_page;
Dan Streetman5538c562014-10-09 15:30:01 -0700663 off %= PAGE_SIZE;
Nitin Gupta61989a82012-01-09 16:51:56 -0600664 }
665}
666
667/*
668 * Allocate a zspage for the given size class
669 */
670static struct page *alloc_zspage(struct size_class *class, gfp_t flags)
671{
672 int i, error;
Seth Jenningsb4b700c2012-06-13 16:03:42 -0500673 struct page *first_page = NULL, *uninitialized_var(prev_page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600674
675 /*
676 * Allocate individual pages and link them together as:
677 * 1. first page->private = first sub-page
678 * 2. all sub-pages are linked together using page->lru
679 * 3. each sub-page is linked to the first page using page->first_page
680 *
681 * For each size class, First/Head pages are linked together using
682 * page->lru. Also, we set PG_private to identify the first page
683 * (i.e. no other sub-page has this flag set) and PG_private_2 to
684 * identify the last page.
685 */
686 error = -ENOMEM;
Minchan Kim2e3b6152012-05-03 15:40:39 +0900687 for (i = 0; i < class->pages_per_zspage; i++) {
Seth Jenningsb4b700c2012-06-13 16:03:42 -0500688 struct page *page;
Nitin Gupta61989a82012-01-09 16:51:56 -0600689
690 page = alloc_page(flags);
691 if (!page)
692 goto cleanup;
693
694 INIT_LIST_HEAD(&page->lru);
695 if (i == 0) { /* first page */
Minchan Kima27545bf2012-04-25 15:23:09 +0900696 SetPagePrivate(page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600697 set_page_private(page, 0);
698 first_page = page;
699 first_page->inuse = 0;
700 }
701 if (i == 1)
Sunghan Suhe842b972013-07-12 16:08:13 +0900702 set_page_private(first_page, (unsigned long)page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600703 if (i >= 1)
704 page->first_page = first_page;
705 if (i >= 2)
706 list_add(&page->lru, &prev_page->lru);
Minchan Kim2e3b6152012-05-03 15:40:39 +0900707 if (i == class->pages_per_zspage - 1) /* last page */
Minchan Kima27545bf2012-04-25 15:23:09 +0900708 SetPagePrivate2(page);
Nitin Gupta61989a82012-01-09 16:51:56 -0600709 prev_page = page;
710 }
711
712 init_zspage(first_page, class);
713
714 first_page->freelist = obj_location_to_handle(first_page, 0);
715 /* Maximum number of objects we can store in this zspage */
Minchan Kim2e3b6152012-05-03 15:40:39 +0900716 first_page->objects = class->pages_per_zspage * PAGE_SIZE / class->size;
Nitin Gupta61989a82012-01-09 16:51:56 -0600717
718 error = 0; /* Success */
719
720cleanup:
721 if (unlikely(error) && first_page) {
722 free_zspage(first_page);
723 first_page = NULL;
724 }
725
726 return first_page;
727}
728
729static struct page *find_get_zspage(struct size_class *class)
730{
731 int i;
732 struct page *page;
733
734 for (i = 0; i < _ZS_NR_FULLNESS_GROUPS; i++) {
735 page = class->fullness_list[i];
736 if (page)
737 break;
738 }
739
740 return page;
741}
742
Minchan Kim1b945ae2013-12-11 11:04:36 +0900743#ifdef CONFIG_PGTABLE_MAPPING
Seth Jenningsf5536462012-07-18 11:55:56 -0500744static inline int __zs_cpu_up(struct mapping_area *area)
Seth Jennings5f601902012-07-02 16:15:49 -0500745{
Seth Jenningsf5536462012-07-18 11:55:56 -0500746 /*
747 * Make sure we don't leak memory if a cpu UP notification
748 * and zs_init() race and both call zs_cpu_up() on the same cpu
749 */
750 if (area->vm)
751 return 0;
752 area->vm = alloc_vm_area(PAGE_SIZE * 2, NULL);
753 if (!area->vm)
754 return -ENOMEM;
755 return 0;
756}
757
758static inline void __zs_cpu_down(struct mapping_area *area)
759{
760 if (area->vm)
761 free_vm_area(area->vm);
762 area->vm = NULL;
763}
764
765static inline void *__zs_map_object(struct mapping_area *area,
766 struct page *pages[2], int off, int size)
767{
WANG Chaof6f8ed42014-08-06 16:06:58 -0700768 BUG_ON(map_vm_area(area->vm, PAGE_KERNEL, pages));
Seth Jenningsf5536462012-07-18 11:55:56 -0500769 area->vm_addr = area->vm->addr;
770 return area->vm_addr + off;
771}
772
773static inline void __zs_unmap_object(struct mapping_area *area,
774 struct page *pages[2], int off, int size)
775{
776 unsigned long addr = (unsigned long)area->vm_addr;
Seth Jenningsf5536462012-07-18 11:55:56 -0500777
Joerg Roedeld95abbb2013-03-27 01:43:14 +0100778 unmap_kernel_range(addr, PAGE_SIZE * 2);
Seth Jenningsf5536462012-07-18 11:55:56 -0500779}
780
Minchan Kim1b945ae2013-12-11 11:04:36 +0900781#else /* CONFIG_PGTABLE_MAPPING */
Seth Jenningsf5536462012-07-18 11:55:56 -0500782
783static inline int __zs_cpu_up(struct mapping_area *area)
784{
785 /*
786 * Make sure we don't leak memory if a cpu UP notification
787 * and zs_init() race and both call zs_cpu_up() on the same cpu
788 */
789 if (area->vm_buf)
790 return 0;
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -0800791 area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
Seth Jenningsf5536462012-07-18 11:55:56 -0500792 if (!area->vm_buf)
793 return -ENOMEM;
794 return 0;
795}
796
797static inline void __zs_cpu_down(struct mapping_area *area)
798{
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -0800799 kfree(area->vm_buf);
Seth Jenningsf5536462012-07-18 11:55:56 -0500800 area->vm_buf = NULL;
801}
802
803static void *__zs_map_object(struct mapping_area *area,
804 struct page *pages[2], int off, int size)
805{
Seth Jennings5f601902012-07-02 16:15:49 -0500806 int sizes[2];
807 void *addr;
Seth Jenningsf5536462012-07-18 11:55:56 -0500808 char *buf = area->vm_buf;
Seth Jennings5f601902012-07-02 16:15:49 -0500809
Seth Jenningsf5536462012-07-18 11:55:56 -0500810 /* disable page faults to match kmap_atomic() return conditions */
811 pagefault_disable();
812
813 /* no read fastpath */
814 if (area->vm_mm == ZS_MM_WO)
815 goto out;
Seth Jennings5f601902012-07-02 16:15:49 -0500816
817 sizes[0] = PAGE_SIZE - off;
818 sizes[1] = size - sizes[0];
819
Seth Jennings5f601902012-07-02 16:15:49 -0500820 /* copy object to per-cpu buffer */
821 addr = kmap_atomic(pages[0]);
822 memcpy(buf, addr + off, sizes[0]);
823 kunmap_atomic(addr);
824 addr = kmap_atomic(pages[1]);
825 memcpy(buf + sizes[0], addr, sizes[1]);
826 kunmap_atomic(addr);
Seth Jenningsf5536462012-07-18 11:55:56 -0500827out:
828 return area->vm_buf;
Seth Jennings5f601902012-07-02 16:15:49 -0500829}
830
Seth Jenningsf5536462012-07-18 11:55:56 -0500831static void __zs_unmap_object(struct mapping_area *area,
832 struct page *pages[2], int off, int size)
Seth Jennings5f601902012-07-02 16:15:49 -0500833{
Seth Jennings5f601902012-07-02 16:15:49 -0500834 int sizes[2];
835 void *addr;
Seth Jenningsf5536462012-07-18 11:55:56 -0500836 char *buf = area->vm_buf;
Seth Jennings5f601902012-07-02 16:15:49 -0500837
Seth Jenningsf5536462012-07-18 11:55:56 -0500838 /* no write fastpath */
839 if (area->vm_mm == ZS_MM_RO)
840 goto out;
Seth Jennings5f601902012-07-02 16:15:49 -0500841
842 sizes[0] = PAGE_SIZE - off;
843 sizes[1] = size - sizes[0];
844
845 /* copy per-cpu buffer to object */
846 addr = kmap_atomic(pages[0]);
847 memcpy(addr + off, buf, sizes[0]);
848 kunmap_atomic(addr);
849 addr = kmap_atomic(pages[1]);
850 memcpy(addr, buf + sizes[0], sizes[1]);
851 kunmap_atomic(addr);
Seth Jenningsf5536462012-07-18 11:55:56 -0500852
853out:
854 /* enable page faults to match kunmap_atomic() return conditions */
855 pagefault_enable();
Seth Jennings5f601902012-07-02 16:15:49 -0500856}
Nitin Gupta61989a82012-01-09 16:51:56 -0600857
Minchan Kim1b945ae2013-12-11 11:04:36 +0900858#endif /* CONFIG_PGTABLE_MAPPING */
Seth Jenningsf5536462012-07-18 11:55:56 -0500859
Nitin Gupta61989a82012-01-09 16:51:56 -0600860static int zs_cpu_notifier(struct notifier_block *nb, unsigned long action,
861 void *pcpu)
862{
Seth Jenningsf5536462012-07-18 11:55:56 -0500863 int ret, cpu = (long)pcpu;
Nitin Gupta61989a82012-01-09 16:51:56 -0600864 struct mapping_area *area;
865
866 switch (action) {
867 case CPU_UP_PREPARE:
868 area = &per_cpu(zs_map_area, cpu);
Seth Jenningsf5536462012-07-18 11:55:56 -0500869 ret = __zs_cpu_up(area);
870 if (ret)
871 return notifier_from_errno(ret);
Nitin Gupta61989a82012-01-09 16:51:56 -0600872 break;
873 case CPU_DEAD:
874 case CPU_UP_CANCELED:
875 area = &per_cpu(zs_map_area, cpu);
Seth Jenningsf5536462012-07-18 11:55:56 -0500876 __zs_cpu_down(area);
Nitin Gupta61989a82012-01-09 16:51:56 -0600877 break;
878 }
879
880 return NOTIFY_OK;
881}
882
883static struct notifier_block zs_cpu_nb = {
884 .notifier_call = zs_cpu_notifier
885};
886
Sergey Senozhatskyb1b00a52014-12-12 16:56:56 -0800887static int zs_register_cpu_notifier(void)
Nitin Gupta61989a82012-01-09 16:51:56 -0600888{
Sergey Senozhatskyb1b00a52014-12-12 16:56:56 -0800889 int cpu, uninitialized_var(ret);
Nitin Gupta61989a82012-01-09 16:51:56 -0600890
Srivatsa S. Bhatf0e71fc2014-03-11 02:09:59 +0530891 cpu_notifier_register_begin();
892
893 __register_cpu_notifier(&zs_cpu_nb);
Nitin Gupta61989a82012-01-09 16:51:56 -0600894 for_each_online_cpu(cpu) {
895 ret = zs_cpu_notifier(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
Sergey Senozhatskyb1b00a52014-12-12 16:56:56 -0800896 if (notifier_to_errno(ret))
897 break;
Nitin Gupta61989a82012-01-09 16:51:56 -0600898 }
Srivatsa S. Bhatf0e71fc2014-03-11 02:09:59 +0530899
900 cpu_notifier_register_done();
Sergey Senozhatskyb1b00a52014-12-12 16:56:56 -0800901 return notifier_to_errno(ret);
902}
903
Ganesh Mahendran66cdef62014-12-18 16:17:40 -0800904static void zs_unregister_cpu_notifier(void)
905{
906 int cpu;
907
908 cpu_notifier_register_begin();
909
910 for_each_online_cpu(cpu)
911 zs_cpu_notifier(NULL, CPU_DEAD, (void *)(long)cpu);
912 __unregister_cpu_notifier(&zs_cpu_nb);
913
914 cpu_notifier_register_done();
915}
916
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -0800917static void init_zs_size_classes(void)
918{
919 int nr;
920
921 nr = (ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) / ZS_SIZE_CLASS_DELTA + 1;
922 if ((ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) % ZS_SIZE_CLASS_DELTA)
923 nr += 1;
924
925 zs_size_classes = nr;
926}
927
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -0800928static unsigned int get_maxobj_per_zspage(int size, int pages_per_zspage)
929{
930 return pages_per_zspage * PAGE_SIZE / size;
931}
932
933static bool can_merge(struct size_class *prev, int size, int pages_per_zspage)
934{
935 if (prev->pages_per_zspage != pages_per_zspage)
936 return false;
937
938 if (get_maxobj_per_zspage(prev->size, prev->pages_per_zspage)
939 != get_maxobj_per_zspage(size, pages_per_zspage))
940 return false;
941
942 return true;
943}
944
Ganesh Mahendran66cdef62014-12-18 16:17:40 -0800945unsigned long zs_get_total_pages(struct zs_pool *pool)
946{
947 return atomic_long_read(&pool->pages_allocated);
948}
949EXPORT_SYMBOL_GPL(zs_get_total_pages);
950
951/**
952 * zs_map_object - get address of allocated object from handle.
953 * @pool: pool from which the object was allocated
954 * @handle: handle returned from zs_malloc
955 *
956 * Before using an object allocated from zs_malloc, it must be mapped using
957 * this function. When done with the object, it must be unmapped using
958 * zs_unmap_object.
959 *
960 * Only one object can be mapped per cpu at a time. There is no protection
961 * against nested mappings.
962 *
963 * This function returns with preemption and page faults disabled.
964 */
965void *zs_map_object(struct zs_pool *pool, unsigned long handle,
966 enum zs_mapmode mm)
967{
968 struct page *page;
969 unsigned long obj_idx, off;
970
971 unsigned int class_idx;
972 enum fullness_group fg;
973 struct size_class *class;
974 struct mapping_area *area;
975 struct page *pages[2];
976
977 BUG_ON(!handle);
978
979 /*
980 * Because we use per-cpu mapping areas shared among the
981 * pools/users, we can't allow mapping in interrupt context
982 * because it can corrupt another users mappings.
983 */
984 BUG_ON(in_interrupt());
985
986 obj_handle_to_location(handle, &page, &obj_idx);
987 get_zspage_mapping(get_first_page(page), &class_idx, &fg);
988 class = pool->size_class[class_idx];
989 off = obj_idx_to_offset(page, obj_idx, class->size);
990
991 area = &get_cpu_var(zs_map_area);
992 area->vm_mm = mm;
993 if (off + class->size <= PAGE_SIZE) {
994 /* this object is contained entirely within a page */
995 area->vm_addr = kmap_atomic(page);
996 return area->vm_addr + off;
997 }
998
999 /* this object spans two pages */
1000 pages[0] = page;
1001 pages[1] = get_next_page(page);
1002 BUG_ON(!pages[1]);
1003
1004 return __zs_map_object(area, pages, off, class->size);
1005}
1006EXPORT_SYMBOL_GPL(zs_map_object);
1007
1008void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
1009{
1010 struct page *page;
1011 unsigned long obj_idx, off;
1012
1013 unsigned int class_idx;
1014 enum fullness_group fg;
1015 struct size_class *class;
1016 struct mapping_area *area;
1017
1018 BUG_ON(!handle);
1019
1020 obj_handle_to_location(handle, &page, &obj_idx);
1021 get_zspage_mapping(get_first_page(page), &class_idx, &fg);
1022 class = pool->size_class[class_idx];
1023 off = obj_idx_to_offset(page, obj_idx, class->size);
1024
1025 area = this_cpu_ptr(&zs_map_area);
1026 if (off + class->size <= PAGE_SIZE)
1027 kunmap_atomic(area->vm_addr);
1028 else {
1029 struct page *pages[2];
1030
1031 pages[0] = page;
1032 pages[1] = get_next_page(page);
1033 BUG_ON(!pages[1]);
1034
1035 __zs_unmap_object(area, pages, off, class->size);
1036 }
1037 put_cpu_var(zs_map_area);
1038}
1039EXPORT_SYMBOL_GPL(zs_unmap_object);
1040
1041/**
1042 * zs_malloc - Allocate block of given size from pool.
1043 * @pool: pool to allocate from
1044 * @size: size of block to allocate
1045 *
1046 * On success, handle to the allocated object is returned,
1047 * otherwise 0.
1048 * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
1049 */
1050unsigned long zs_malloc(struct zs_pool *pool, size_t size)
1051{
1052 unsigned long obj;
1053 struct link_free *link;
1054 struct size_class *class;
1055 void *vaddr;
1056
1057 struct page *first_page, *m_page;
1058 unsigned long m_objidx, m_offset;
1059
1060 if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
1061 return 0;
1062
1063 class = pool->size_class[get_size_class_index(size)];
1064
1065 spin_lock(&class->lock);
1066 first_page = find_get_zspage(class);
1067
1068 if (!first_page) {
1069 spin_unlock(&class->lock);
1070 first_page = alloc_zspage(class, pool->flags);
1071 if (unlikely(!first_page))
1072 return 0;
1073
1074 set_zspage_mapping(first_page, class->index, ZS_EMPTY);
1075 atomic_long_add(class->pages_per_zspage,
1076 &pool->pages_allocated);
1077 spin_lock(&class->lock);
1078 }
1079
1080 obj = (unsigned long)first_page->freelist;
1081 obj_handle_to_location(obj, &m_page, &m_objidx);
1082 m_offset = obj_idx_to_offset(m_page, m_objidx, class->size);
1083
1084 vaddr = kmap_atomic(m_page);
1085 link = (struct link_free *)vaddr + m_offset / sizeof(*link);
1086 first_page->freelist = link->next;
1087 memset(link, POISON_INUSE, sizeof(*link));
1088 kunmap_atomic(vaddr);
1089
1090 first_page->inuse++;
1091 /* Now move the zspage to another fullness group, if required */
1092 fix_fullness_group(pool, first_page);
1093 spin_unlock(&class->lock);
1094
1095 return obj;
1096}
1097EXPORT_SYMBOL_GPL(zs_malloc);
1098
1099void zs_free(struct zs_pool *pool, unsigned long obj)
1100{
1101 struct link_free *link;
1102 struct page *first_page, *f_page;
1103 unsigned long f_objidx, f_offset;
1104 void *vaddr;
1105
1106 int class_idx;
1107 struct size_class *class;
1108 enum fullness_group fullness;
1109
1110 if (unlikely(!obj))
1111 return;
1112
1113 obj_handle_to_location(obj, &f_page, &f_objidx);
1114 first_page = get_first_page(f_page);
1115
1116 get_zspage_mapping(first_page, &class_idx, &fullness);
1117 class = pool->size_class[class_idx];
1118 f_offset = obj_idx_to_offset(f_page, f_objidx, class->size);
1119
1120 spin_lock(&class->lock);
1121
1122 /* Insert this object in containing zspage's freelist */
1123 vaddr = kmap_atomic(f_page);
1124 link = (struct link_free *)(vaddr + f_offset);
1125 link->next = first_page->freelist;
1126 kunmap_atomic(vaddr);
1127 first_page->freelist = (void *)obj;
1128
1129 first_page->inuse--;
1130 fullness = fix_fullness_group(pool, first_page);
1131 spin_unlock(&class->lock);
1132
1133 if (fullness == ZS_EMPTY) {
1134 atomic_long_sub(class->pages_per_zspage,
1135 &pool->pages_allocated);
1136 free_zspage(first_page);
1137 }
1138}
1139EXPORT_SYMBOL_GPL(zs_free);
1140
Davidlohr Bueso4bbc0bc2013-01-04 12:14:00 -08001141/**
1142 * zs_create_pool - Creates an allocation pool to work from.
Seth Jennings0d145a52013-01-30 09:36:52 -06001143 * @flags: allocation flags used to allocate pool metadata
Davidlohr Bueso4bbc0bc2013-01-04 12:14:00 -08001144 *
1145 * This function must be called before anything when using
1146 * the zsmalloc allocator.
1147 *
1148 * On success, a pointer to the newly created pool is returned,
1149 * otherwise NULL.
1150 */
Seth Jennings0d145a52013-01-30 09:36:52 -06001151struct zs_pool *zs_create_pool(gfp_t flags)
Nitin Gupta61989a82012-01-09 16:51:56 -06001152{
Ganesh Mahendran18136652014-12-12 16:57:10 -08001153 int i;
Nitin Gupta61989a82012-01-09 16:51:56 -06001154 struct zs_pool *pool;
Ganesh Mahendrandf8b5bb2014-12-12 16:57:07 -08001155 struct size_class *prev_class = NULL;
Nitin Gupta61989a82012-01-09 16:51:56 -06001156
Ganesh Mahendran18136652014-12-12 16:57:10 -08001157 pool = kzalloc(sizeof(*pool), GFP_KERNEL);
Nitin Gupta61989a82012-01-09 16:51:56 -06001158 if (!pool)
1159 return NULL;
1160
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -08001161 pool->size_class = kcalloc(zs_size_classes, sizeof(struct size_class *),
1162 GFP_KERNEL);
1163 if (!pool->size_class) {
1164 kfree(pool);
1165 return NULL;
1166 }
1167
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001168 /*
1169 * Iterate reversly, because, size of size_class that we want to use
1170 * for merging should be larger or equal to current size.
1171 */
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -08001172 for (i = zs_size_classes - 1; i >= 0; i--) {
Nitin Gupta61989a82012-01-09 16:51:56 -06001173 int size;
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001174 int pages_per_zspage;
Nitin Gupta61989a82012-01-09 16:51:56 -06001175 struct size_class *class;
1176
1177 size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
1178 if (size > ZS_MAX_ALLOC_SIZE)
1179 size = ZS_MAX_ALLOC_SIZE;
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001180 pages_per_zspage = get_pages_per_zspage(size);
Nitin Gupta61989a82012-01-09 16:51:56 -06001181
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001182 /*
1183 * size_class is used for normal zsmalloc operation such
1184 * as alloc/free for that size. Although it is natural that we
1185 * have one size_class for each size, there is a chance that we
1186 * can get more memory utilization if we use one size_class for
1187 * many different sizes whose size_class have same
1188 * characteristics. So, we makes size_class point to
1189 * previous size_class if possible.
1190 */
Ganesh Mahendrandf8b5bb2014-12-12 16:57:07 -08001191 if (prev_class) {
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001192 if (can_merge(prev_class, size, pages_per_zspage)) {
1193 pool->size_class[i] = prev_class;
1194 continue;
1195 }
1196 }
1197
1198 class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
1199 if (!class)
1200 goto err;
1201
Nitin Gupta61989a82012-01-09 16:51:56 -06001202 class->size = size;
1203 class->index = i;
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001204 class->pages_per_zspage = pages_per_zspage;
Nitin Gupta61989a82012-01-09 16:51:56 -06001205 spin_lock_init(&class->lock);
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001206 pool->size_class[i] = class;
Ganesh Mahendrandf8b5bb2014-12-12 16:57:07 -08001207
1208 prev_class = class;
Nitin Gupta61989a82012-01-09 16:51:56 -06001209 }
1210
Nitin Gupta61989a82012-01-09 16:51:56 -06001211 pool->flags = flags;
Nitin Gupta61989a82012-01-09 16:51:56 -06001212
Nitin Gupta61989a82012-01-09 16:51:56 -06001213 return pool;
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001214
1215err:
1216 zs_destroy_pool(pool);
1217 return NULL;
Nitin Gupta61989a82012-01-09 16:51:56 -06001218}
1219EXPORT_SYMBOL_GPL(zs_create_pool);
1220
1221void zs_destroy_pool(struct zs_pool *pool)
1222{
1223 int i;
1224
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -08001225 for (i = 0; i < zs_size_classes; i++) {
Nitin Gupta61989a82012-01-09 16:51:56 -06001226 int fg;
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001227 struct size_class *class = pool->size_class[i];
1228
1229 if (!class)
1230 continue;
1231
1232 if (class->index != i)
1233 continue;
Nitin Gupta61989a82012-01-09 16:51:56 -06001234
1235 for (fg = 0; fg < _ZS_NR_FULLNESS_GROUPS; fg++) {
1236 if (class->fullness_list[fg]) {
Marlies Ruck93ad5ab2013-05-15 16:56:49 -04001237 pr_info("Freeing non-empty class with size %db, fullness group %d\n",
Nitin Gupta61989a82012-01-09 16:51:56 -06001238 class->size, fg);
1239 }
1240 }
Joonsoo Kim9eec4cd2014-12-12 16:56:44 -08001241 kfree(class);
Nitin Gupta61989a82012-01-09 16:51:56 -06001242 }
Mahendran Ganesh40f9fb82014-12-12 16:57:01 -08001243
1244 kfree(pool->size_class);
Nitin Gupta61989a82012-01-09 16:51:56 -06001245 kfree(pool);
1246}
1247EXPORT_SYMBOL_GPL(zs_destroy_pool);
1248
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001249static int __init zs_init(void)
Nitin Gupta61989a82012-01-09 16:51:56 -06001250{
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001251 int ret = zs_register_cpu_notifier();
Nitin Gupta61989a82012-01-09 16:51:56 -06001252
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001253 if (ret) {
1254 zs_unregister_cpu_notifier();
1255 return ret;
Nitin Gupta61989a82012-01-09 16:51:56 -06001256 }
1257
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001258 init_zs_size_classes();
Nitin Gupta61989a82012-01-09 16:51:56 -06001259
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001260#ifdef CONFIG_ZPOOL
1261 zpool_register_driver(&zs_zpool_driver);
1262#endif
1263 return 0;
Nitin Gupta61989a82012-01-09 16:51:56 -06001264}
Nitin Gupta61989a82012-01-09 16:51:56 -06001265
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001266static void __exit zs_exit(void)
Nitin Gupta61989a82012-01-09 16:51:56 -06001267{
Ganesh Mahendran66cdef62014-12-18 16:17:40 -08001268#ifdef CONFIG_ZPOOL
1269 zpool_unregister_driver(&zs_zpool_driver);
1270#endif
1271 zs_unregister_cpu_notifier();
Nitin Gupta61989a82012-01-09 16:51:56 -06001272}
Ben Hutchings069f1012012-06-20 02:31:11 +01001273
1274module_init(zs_init);
1275module_exit(zs_exit);
1276
1277MODULE_LICENSE("Dual BSD/GPL");
1278MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");