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 #define _PFN_BITS               (MAX_PHYSMEM_BITS - PAGE_SHIFT)
  44 #define OBJ_INDEX_BITS  (BITS_PER_LONG - _PFN_BITS)
  45 #define OBJ_INDEX_MASK  ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
  46
  47 /* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
  48 #define ZS_MIN_ALLOC_SIZE       32
  49 #define ZS_MAX_ALLOC_SIZE       PAGE_SIZE
  50
  51 /*
  52  * On systems with 4K page size, this gives 254 size classes! There is a
  53  * trader-off here:
  54  *  - Large number of size classes is potentially wasteful as free page are
  55  *    spread across these classes
  56  *  - Small number of size classes causes large internal fragmentation
  57  *  - Probably its better to use specific size classes (empirically
  58  *    determined). NOTE: all those class sizes must be set as multiple of
  59  *    ZS_ALIGN to make sure link_free itself never has to span 2 pages.
  60  *
  61  *  ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
  62  *  (reason above)
  63  */
  64 #define ZS_SIZE_CLASS_DELTA     16
  65 #define ZS_SIZE_CLASSES         ((ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) / \
  66                                         ZS_SIZE_CLASS_DELTA + 1)
  67
  68 /*
  69  * We do not maintain any list for completely empty or full pages
  70  */
  71 enum fullness_group {
  72         ZS_ALMOST_FULL,
  73         ZS_ALMOST_EMPTY,
  74         _ZS_NR_FULLNESS_GROUPS,
  75
  76         ZS_EMPTY,
  77         ZS_FULL
  78 };
  79
  80 /*
  81  * We assign a page to ZS_ALMOST_EMPTY fullness group when:
  82  *      n <= N / f, where
  83  * n = number of allocated objects
  84  * N = total number of objects zspage can store
  85  * f = 1/fullness_threshold_frac
  86  *
  87  * Similarly, we assign zspage to:
  88  *      ZS_ALMOST_FULL  when n > N / f
  89  *      ZS_EMPTY        when n == 0
  90  *      ZS_FULL         when n == N
  91  *
  92  * (see: fix_fullness_group())
  93  */
  94 static const int fullness_threshold_frac = 4;
  95
  96 struct mapping_area {
  97         struct vm_struct *vm;
  98         pte_t *vm_ptes[2];
  99         char *vm_addr;
 100 };
 101
 102 struct size_class {
 103         /*
 104          * Size of objects stored in this class. Must be multiple
 105          * of ZS_ALIGN.
 106          */
 107         int size;
 108         unsigned int index;
 109
 110         /* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
 111         int zspage_order;
 112
 113         spinlock_t lock;
 114
 115         /* stats */
 116         u64 pages_allocated;
 117
 118         struct page *fullness_list[_ZS_NR_FULLNESS_GROUPS];
 119 };
 120
 121 /*
 122  * Placed within free objects to form a singly linked list.
 123  * For every zspage, first_page->freelist gives head of this list.
 124  *
 125  * This must be power of 2 and less than or equal to ZS_ALIGN
 126  */
 127 struct link_free {
 128         /* Handle of next free chunk (encodes <PFN, obj_idx>) */
 129         void *next;
 130 };
 131
 132 struct zs_pool {
 133         struct size_class size_class[ZS_SIZE_CLASSES];
 134
 135         gfp_t flags;    /* allocation flags used when growing pool */
 136         const char *name;
 137 };
 138
 139 #endif