drivers/staging/zsmalloc/zsmalloc_int.h

   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 pages_per_zspage;
 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