2 * zsmalloc memory allocator
4 * Copyright (C) 2011 Nitin Gupta
6 * This code is released using a dual license strategy: BSD/GPL
7 * You can choose the license that better fits your requirements.
9 * Released under the terms of 3-clause BSD License
10 * Released under the terms of GNU General Public License Version 2.0
13 #ifndef _ZS_MALLOC_INT_H_
14 #define _ZS_MALLOC_INT_H_
16 #include <linux/kernel.h>
17 #include <linux/spinlock.h>
18 #include <linux/types.h>
21 * This must be power of 2 and greater than of equal to sizeof(link_free).
22 * These two conditions ensure that any 'struct link_free' itself doesn't
23 * span more than 1 page which avoids complex case of mapping 2 pages simply
24 * to restore link_free pointer values.
29 * A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
30 * pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
32 #define ZS_MAX_ZSPAGE_ORDER 2
33 #define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
36 * Object location (<PFN>, <obj_idx>) is encoded as
37 * as single (void *) handle value.
39 * Note that object index <obj_idx> is relative to system
40 * page <PFN> it is stored in, so for each sub-page belonging
41 * to a zspage, obj_idx starts with 0.
43 * This is made more complicated by various memory models and PAE.
46 #ifndef MAX_PHYSMEM_BITS
47 #ifdef CONFIG_HIGHMEM64G
48 #define MAX_PHYSMEM_BITS 36
49 #else /* !CONFIG_HIGHMEM64G */
51 * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
54 #define MAX_PHYSMEM_BITS BITS_PER_LONG
57 #define _PFN_BITS (MAX_PHYSMEM_BITS - PAGE_SHIFT)
58 #define OBJ_INDEX_BITS (BITS_PER_LONG - _PFN_BITS)
59 #define OBJ_INDEX_MASK ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
61 #define MAX(a, b) ((a) >= (b) ? (a) : (b))
62 /* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
63 #define ZS_MIN_ALLOC_SIZE \
64 MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
65 #define ZS_MAX_ALLOC_SIZE PAGE_SIZE
68 * On systems with 4K page size, this gives 254 size classes! There is a
70 * - Large number of size classes is potentially wasteful as free page are
71 * spread across these classes
72 * - Small number of size classes causes large internal fragmentation
73 * - Probably its better to use specific size classes (empirically
74 * determined). NOTE: all those class sizes must be set as multiple of
75 * ZS_ALIGN to make sure link_free itself never has to span 2 pages.
77 * ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
80 #define ZS_SIZE_CLASS_DELTA 16
81 #define ZS_SIZE_CLASSES ((ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) / \
82 ZS_SIZE_CLASS_DELTA + 1)
85 * We do not maintain any list for completely empty or full pages
90 _ZS_NR_FULLNESS_GROUPS,
97 * We assign a page to ZS_ALMOST_EMPTY fullness group when:
99 * n = number of allocated objects
100 * N = total number of objects zspage can store
101 * f = 1/fullness_threshold_frac
103 * Similarly, we assign zspage to:
104 * ZS_ALMOST_FULL when n > N / f
105 * ZS_EMPTY when n == 0
106 * ZS_FULL when n == N
108 * (see: fix_fullness_group())
110 static const int fullness_threshold_frac = 4;
112 struct mapping_area {
113 struct vm_struct *vm;
120 * Size of objects stored in this class. Must be multiple
126 /* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
127 int pages_per_zspage;
134 struct page *fullness_list[_ZS_NR_FULLNESS_GROUPS];
138 * Placed within free objects to form a singly linked list.
139 * For every zspage, first_page->freelist gives head of this list.
141 * This must be power of 2 and less than or equal to ZS_ALIGN
144 /* Handle of next free chunk (encodes <PFN, obj_idx>) */
149 struct size_class size_class[ZS_SIZE_CLASSES];
151 gfp_t flags; /* allocation flags used when growing pool */