1 /* 2 * zsmalloc memory allocator 3 * 4 * Copyright (C) 2011 Nitin Gupta 5 * 6 * This code is released using a dual license strategy: BSD/GPL 7 * You can choose the license that better fits your requirements. 8 * 9 * Released under the terms of 3-clause BSD License 10 * Released under the terms of GNU General Public License Version 2.0 11 */ 12 13 #ifndef _ZS_MALLOC_INT_H_ 14 #define _ZS_MALLOC_INT_H_ 15 16 #include <linux/kernel.h> 17 #include <linux/spinlock.h> 18 #include <linux/types.h> 19 20 /* 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. 25 */ 26 #define ZS_ALIGN 8 27 28 /* 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. 31 */ 32 #define ZS_MAX_ZSPAGE_ORDER 2 33 #define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER) 34 35 /* 36 * Object location (<PFN>, <obj_idx>) is encoded as 37 * as single (void *) handle value. 38 * 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. 42 * 43 * This is made more complicated by various memory models and PAE. 44 */ 45 46 #ifndef MAX_PHYSMEM_BITS 47 #ifdef CONFIG_HIGHMEM64G 48 #define MAX_PHYSMEM_BITS 36 49 #else /* !CONFIG_HIGHMEM64G */ 50 /* 51 * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just 52 * be PAGE_SHIFT 53 */ 54 #define MAX_PHYSMEM_BITS BITS_PER_LONG 55 #endif 56 #endif 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) 60 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 66 67 /* 68 * On systems with 4K page size, this gives 254 size classes! There is a 69 * trader-off here: 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. 76 * 77 * ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN 78 * (reason above) 79 */ 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) 83 84 /* 85 * We do not maintain any list for completely empty or full pages 86 */ 87 enum fullness_group { 88 ZS_ALMOST_FULL, 89 ZS_ALMOST_EMPTY, 90 _ZS_NR_FULLNESS_GROUPS, 91 92 ZS_EMPTY, 93 ZS_FULL 94 }; 95 96 /* 97 * We assign a page to ZS_ALMOST_EMPTY fullness group when: 98 * n <= N / f, where 99 * n = number of allocated objects 100 * N = total number of objects zspage can store 101 * f = 1/fullness_threshold_frac 102 * 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 107 * 108 * (see: fix_fullness_group()) 109 */ 110 static const int fullness_threshold_frac = 4; 111 112 struct mapping_area { 113 struct vm_struct *vm; 114 pte_t *vm_ptes[2]; 115 char *vm_addr; 116 }; 117 118 struct size_class { 119 /* 120 * Size of objects stored in this class. Must be multiple 121 * of ZS_ALIGN. 122 */ 123 int size; 124 unsigned int index; 125 126 /* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */ 127 int zspage_order; 128 129 spinlock_t lock; 130 131 /* stats */ 132 u64 pages_allocated; 133 134 struct page *fullness_list[_ZS_NR_FULLNESS_GROUPS]; 135 }; 136 137 /* 138 * Placed within free objects to form a singly linked list. 139 * For every zspage, first_page->freelist gives head of this list. 140 * 141 * This must be power of 2 and less than or equal to ZS_ALIGN 142 */ 143 struct link_free { 144 /* Handle of next free chunk (encodes <PFN, obj_idx>) */ 145 void *next; 146 }; 147 148 struct zs_pool { 149 struct size_class size_class[ZS_SIZE_CLASSES]; 150 151 gfp_t flags; /* allocation flags used when growing pool */ 152 const char *name; 153 }; 154 155 #endif 156