分类： LINUX
2016-04-01 17:43:11
引言：应用级别的内存分配器的作用主要在于减少malloc函数的调用，降低系统的内存碎片。作为高性能的服务器，一般都会有自己的内存分配方案。slab作为一款Linux内核的经典内存分配方式，应用在很多的应用级别的软件上，比如说Memcached 等。
今天的主题就分享一下最近写的slab的一个简单的Demo，在于分享，代码有些粗糙，比如缺少对于内存字节的比例因子，缺少关于内存不足的情况下重分配等。不过各种应用各有各自的用途，在实现某些cached操作的软件中，由于带有LRU 算法等，在内存快使用完后就采取淘汰策略，所以不一定在内存不足的情况下重新给操作系统分配。
Slab内存分配器原理：
此图片来自自己的另一篇博文，如若不能显示，请google slab 内存分配器
slab内存分配器的原理大致如图所示，由index 确定一个由slot 组成的链表，这里也可以设置为一个固定长度大小的结构，然后划分为不同大小的slot
两种方式都有自己的好处，采用链表的方式可以动态增长，采用固定长度大小的块结构结构清晰，可以采用链式的数组构造slot，然后由empty_index 来确定空闲的slot，本篇博文就是讲解采用了这种方式的管理的。稍后会有详解，这里只是作为简单介绍。
我们只需要了解可以通过对齐后的内存大小找到index，然后通过index 找到slot数组，通过empty_index找到空闲的slot，改变empty_index 使其指向下一个空闲的slot。
对齐宏：
#define ALIGN(a,size) ((a+size-1)&(~(size-1)))
a为申请的内存大小，size为内存对齐大小
比如说 a = 127 size = 128 ， 那么小于128 的将a转化为128，总的来说，就是128的整数倍。
很多人说这样的方式会导致内存浪费，但是至今几乎都是采用这种方式。在没有找到一个更好的方式以前，这个也许就是最好的方式吧。
通过对齐后的内存大小，找到对应的index 是很容易的。比如说，我们的内存对齐是64，我们只需要将申请的 a>>6 .
#define MC_SLOT_ALIGN_SIZE (64)
我们定义了默认的内存字节就是64Byte.可以通过自己的喜好做修改
解释一下这里的命名方式，CHUNK_ARRAY 就是由index 作为下标的数组。
我们定义
#define MC_CHUNK_ARRAY_SIZE (16)
就是说，index最大为15 0 不做为index。
每一个slot 的结构是这样定义的：
1 typedef struct _slot_s 2 { 3 struct _slot_s *data ; /* The next empty slot */ 4 mc_address *star ; 5 mc_address *end ; 6 mc_length slot_length ; 7 int slot_index ; 8 mc_chunk_t *which_chunk_p ; 9 }mc_slot_t;
data 指针作为连接slot 数组的每一个槽的指针存在着，另一种方式是设置为 void *data ,这样可以复用 data指针，在申请出来后可以作为指向数据的指针。
1 #define mc_address unsigned char 2 3 #define mc_length unsigned int
mc_address *start 用于指向slot申请的真正的内存地址，一般由malloc来申请。
mc_address *end 指向内存的末尾。 end - start == slot_length
slot_index 用于表示此slot是位于slot数组的下标
mc_chunkt_t *which_chunk_p 是用来表示属于哪一个chunk 的，这个指针可以在释放的时候降低接口复杂度。
下面看看chunk的结构表示：
1 struct _chunk_s 2 { 3 mc_length chunk_length ; 4 mc_slot_t *slots ; 5 int slots_size ; /*(int)(MC_CHUNK_SIZE/ALIGN(i,MC_SLOT_ALIGN_SIZE))*/ 6 int empty_slot_index ; 7 int last_slot_num ; 8 int slots_array_num ; /*slot array size */ 9 };
chunk_length 为宏定义的MC_CHUNK_ARRAY_SIZE
slots 是一个指针，指向不同的slot数组，这里的slot数组也是通过动态分配的。后面会贴出相应代码。
slots_size是这个chunk下的slot数组中slot的内存大小。即end-statr
empty_slot_index是空闲的slot的index，这中数据结构可以查看类似的nginx的connection数组。
last_slot_num作为标示剩余的slot数量
slots_array_num是slot的数组的大小
下面看看头文件中的函数声明：
1 mc_slab_t * mc_slab_create(void); 2 /* 3 * This function create a handle of slab and 4 * you can use this handle to alloc slot 5 * besieds,when you free the slab , you must take this 6 * handle as a argument of mc_slab_free function 7 */ 8 9 mc_slot_t * mc_slot_alloc( mc_slab_t * par_slab , size_t par_size ); 10 /* 11 * mc_slot_alloc first arg is handle created by mc_slab_create 12 * the second arg is memory size you want 13 * NOTICE:because of handle is a global value , so this function is 14 * not thread safty 15 */ 16 17 int mc_slot_free( mc_slot_t * par_slot_p ); 18 /* 19 * mc_slot_free take a slot structure as argument 20 * return 1 indicate successed 21 * 22 * this function find the lowest index of slot array 23 * It's simple but useful 24 */ 25 26 void mc_slab_free( mc_slab_t * par_slab ); 27 /* 28 * free the whole slab 29 * argument is handle of create by mc_slab_create 30 * 31 * well done ,this function is test by valgrind and not memory leak
大致就是这几个函数，功能有说明。
1 3 4 mc_slab_t * mc_slab_create(void) 5 { 6 mc_chunk_t *p_chunk ; 7 mc_slot_t *p_slot ; 8 int i; 9 int j; 10 11 int chunk_array_size = MC_CHUNK_ARRAY_SIZE ; 12 /* MALLOC */ 13 mc_slab_t * ret_big_array_p = (mc_slab_t *)malloc( sizeof(mc_slab_t) ); 14 15 /* alloc memory for chunk_array */ 16 /* MALLOC */ 17 ret_big_array_p->chunk_array = (mc_chunk_t *)malloc( sizeof(mc_chunk_t)*MC_CHUNK_ARRAY_SIZE ); 18 19 ret_big_array_p->total_alloced = MC_CHUNK_SIZE * MC_CHUNK_ARRAY_SIZE ; 20 21 ret_big_array_p->chunk_array_size = MC_CHUNK_ARRAY_SIZE ; 22 23 p_chunk = ret_big_array_p->chunk_array ; 24 25 /* 26 p_chunk[0] = NULL ; 27 */ 28 for( i = 1 ; i < chunk_array_size ; i++ ) 29 { 30 p_chunk[i].chunk_length = MC_CHUNK_SIZE ; 31 32 /* every slot has a stable size of MC_CHUNK_SIZE */ 33 p_chunk[i].slots_size = (int)(MC_CHUNK_SIZE/ALIGN(i,MC_SLOT_ALIGN_SIZE)); 34 35 /* alloc memory for slots every chunk */ 36 /* MALLOC */ 37 p_chunk[i].slots = (mc_slot_t *)malloc( sizeof(mc_slot_t)*p_chunk[i].slots_size ); 38 39 p_chunk[i].empty_slot_index = 0 ; 40 41 p_chunk[i].last_slot_num = p_chunk[i].slots_size ; 42 43 p_chunk[i].slots_array_num = p_chunk[i].slots_size ; 44 45 46 47 /*initialize the slots*/ 48 j = p_chunk[i].slots_size - 1 ; 49 /*slot_size = */ 50 51 int slot_alloc_size = i<<6 ; 52 53 /* ini the last slot of slot array */ 54 p_chunk[i].slots[j].data = NULL ; 55 56 /* MALLOC */ 57 p_chunk[i].slots[j].star = (void *)malloc( slot_alloc_size ); 58 ret_big_array_p->total_lasted += slot_alloc_size ; 59 p_chunk[i].slots[j].end = p_chunk[i].slots[j].star + slot_alloc_size ; 60 p_chunk[i].slots[j].slot_length = slot_alloc_size ; 61 p_chunk[i].slots[j].slot_index = j ; 62 p_chunk[i].slots[j].which_chunk_p = &(p_chunk[i]); 63 64 /* for other slots initialize */ 65 for( j = p_chunk[i].slots_size -2 ; j >= 0 ; j-- ) 66 { 67 p_chunk[i].slots[j].data = &(p_chunk[i].slots[j+1]) ; 68 69 /* MALLOC */ 70 p_chunk[i].slots[j].star = (void *)malloc( slot_alloc_size ); 71 ret_big_array_p->total_lasted += slot_alloc_size ; 72 73 p_chunk[i].slots[j].end = p_chunk[i].slots[j].star + slot_alloc_size ; 74 75 p_chunk[i].slots[j].slot_length = slot_alloc_size ; 76 77 p_chunk[i].slots[j].slot_index = j ; 78 79 p_chunk[i].slots[j].which_chunk_p = &(p_chunk[i]); 80 } 81 } 82 ret_big_array_p->total_alloced = 0 ; 83 84 85 /* flag of wether this block is initialized */ 86 ret_big_array_p->is_initialized = 1 ; 87 return ret_big_array_p ; 88 } 89 90 mc_slot_t * mc_slot_alloc( mc_slab_t * par_slab , size_t par_size ) 91 { 92 if( par_slab == NULL || par_slab->is_initialized != 1 ) 93 { 94 /*There may be some debug information*/ 95 return NULL ; 96 } 97 98 /* args checked right */ 99 100 mc_slot_t * ret_slot_p ; 101 size_t allocsize = ALIGN( par_size,MC_SLOT_ALIGN_SIZE ) ; 102 int chunk_index = allocsize >> 6 ; 103 104 if( chunk_index >= MC_CHUNK_ARRAY_SIZE ) 105 { 106 /* to protected out of chunk[] bound */ 107 /*We should do someting At least we should let users know there was no slot for him */ 108 return NULL ; 109 110 } 111 112 if( par_slab->chunk_array[ chunk_index ].last_slot_num == 0 ) 113 { 114 /*we should do something eh ??*/ 115 /*At least we should let user know there was no slot for him */ 116 return NULL ; 117 } 118 119 mc_chunk_t * p_chunk = &(par_slab->chunk_array[ chunk_index ]); 120 int empty_index = p_chunk->empty_slot_index ; 121 122 /* find a empty slot for ret_slot_p point */ 123 ret_slot_p = &(p_chunk->slots[empty_index]) ; 124 125 /* we should change the chunk's empty index */ 126 127 p_chunk->empty_slot_index = ret_slot_p->data->slot_index ; 128 129 (p_chunk->last_slot_num)-- ; 130 return ret_slot_p ; 131 132 } 133 134 135 136 /* Notice ! free slot but not slab */ 137 int mc_slot_free( mc_slot_t * par_slot_p ) 138 { 139 mc_chunk_t * chunk_p = par_slot_p->which_chunk_p ; 140 chunk_p->slots[chunk_p->empty_slot_index].data = par_slot_p ; 141 chunk_p->empty_slot_index = par_slot_p->slot_index; 142 (chunk_p->last_slot_num)++ ; 143 return 1 ; 144 } 145 146 void mc_slab_free( mc_slab_t * par_slab ) 147 { 148 mc_chunk_t * chunk_p ; 149 mc_chunk_t * free_chunk_p ; 150 mc_slot_t * slot_p ; 151 mc_slot_t * free_slot_p ; 152 153 154 /* free each slot first */ 155 int i = 0 ; 156 int j = 0 ; 157 158 for( i = 1 ; i < MC_CHUNK_ARRAY_SIZE ; i++ ) 159 { 160 161 chunk_p = &(par_slab->chunk_array[i]); 162 163 slot_p = chunk_p->slots; 164 165 for( j = 0 ; j < chunk_p->slots_array_num ; j++ ) 166 { 167 free(slot_p[j].star); 168 } 169 free( slot_p ); 170 } 171 free( par_slab->chunk_array ); 172 free( par_slab ); 173 } 174 175 176 /* 177 int main() 178 { 179 mc_slab_t *my_slab = mc_slab_create(); 180 fprintf(stderr,"%d\n",my_slab->total_lasted); 181 mc_slot_t * my_slot = mc_slot_alloc( my_slab, 127 ) ; 182 fprintf(stderr,"%p\n",my_slot->star); 183 fprintf(stderr,"%p\n",my_slot->end); 184 fprintf(stderr,"%d\n",my_slot->slot_index); 185 fprintf(stderr,"%d\n",my_slot->slot_length); 186 187 my_slot = mc_slot_alloc( my_slab, 127 ) ; 188 fprintf(stderr,"%p\n",my_slot->star); 189 fprintf(stderr,"%p\n",my_slot->end); 190 fprintf(stderr,"%d\n",my_slot->slot_index); 191 fprintf(stderr,"%d\n",my_slot->slot_length); 192 193 my_slot = mc_slot_alloc( my_slab, 127 ) ; 194 fprintf(stderr,"%p\n",my_slot->star); 195 fprintf(stderr,"%p\n",my_slot->end); 196 fprintf(stderr,"%d\n",my_slot->slot_index); 197 fprintf(stderr,"%d\n",my_slot->slot_length); 198 199 my_slot = mc_slot_alloc( my_slab, 127 ) ; 200 fprintf(stderr,"%p\n",my_slot->star); 201 fprintf(stderr,"%p\n",my_slot->end); 202 fprintf(stderr,"%d\n",my_slot->slot_index); 203 fprintf(stderr,"%d\n",my_slot->slot_length); 204 205 mc_slot_free(my_slot); 206 my_slot = mc_slot_alloc( my_slab, 127 ) ; 207 fprintf(stderr,"%p\n",my_slot->star); 208 fprintf(stderr,"%p\n",my_slot->end); 209 fprintf(stderr,"%d\n",my_slot->slot_index); 210 fprintf(stderr,"%d\n",my_slot->slot_length); 211 212 my_slot = mc_slot_alloc( my_slab, 127 ) ; 213 fprintf(stderr,"%p\n",my_slot->star); 214 fprintf(stderr,"%p\n",my_slot->end); 215 fprintf(stderr,"%d\n",my_slot->slot_index); 216 fprintf(stderr,"%d\n",my_slot->slot_length); 217 218 my_slot = mc_slot_alloc( my_slab, 62 ) ; 219 fprintf(stderr,"%p\n",my_slot->star); 220 fprintf(stderr,"%p\n",my_slot->end); 221 fprintf(stderr,"%d\n",my_slot->slot_index); 222 fprintf(stderr,"%d\n",my_slot->slot_length); 223 224 mc_slab_free(my_slab); 225 226 return 0; 227 } 228 229 */
