[CNT]关于自己的一个小小的slab内存分配器

引言：应用级别的内存分配器的作用主要在于减少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 */

总结：slab内存分配器的核心在于理解通过对齐后的内存大小得到index

文章属原创，转载请注明出处联系作者： Email:zhangbolinux@sina.com QQ:513364476