STL的第二级空间配置器代码分析[2]

2013年4月26日 由 Creater 留言 »

上面描诉了allocate函数,这个函数是标准配置器的接口函数。在该函数中,首先判断区块大小是否大于128字节,如果大于则调用第一级配置器,小于则检查对应的自由链表,如果对应的自由链表有可用的块则直接使用,否则将区块大小上升到8的倍数,调用refill重新填充空间。再来看看allocate的对立面deallocate,具体的意思看代码里的注释。

   /* p may not be 0 */
  static void deallocate(void *p, size_t n)
  {
    obj *q = (obj *)p;
		//用于指向16个自由链表中最合适哪一个
    obj * __VOLATILE * my_free_list;
		//大于128字节则交给第一级配置器处理
    if (n > (size_t) __MAX_BYTES) {
        malloc_alloc::deallocate(p, n);
        return;
    }
		//确定自由链表
    my_free_list = free_list + FREELIST_INDEX(n);
    // acquire lock
#       ifndef _NOTHREADS
        /*REFERENCED*/
        lock lock_instance;
#       endif /* _NOTHREADS */
	//将p指向的内存块添加到自由链表里
    q -> free_list_link = *my_free_list;
		//修改自由链表的指向
    *my_free_list = q;
    // lock is released here
  }


前面说过,如果特定的自由链表中已经没有可用的块,则需要在堆中分配一大块内存注入内存池,这一大块内存一部分加入到自由链表中,剩下的则空闲在内存池中。这些都是由chunk_alloc来实现。

template <bool threads, int inst>
char*
__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
		//用于最终返回结果
    char * result;
		//预想分配的内存大小
    size_t total_bytes = size * nobjs;
		//内存池中的空闲内存大小
    size_t bytes_left = end_free - start_free;
		//如果内存池中剩余的内存大于请求的内存(nobjs*size),则直接返回这段内存,无需在堆中分配
    if (bytes_left >= total_bytes) {
			//更新内存池区间
        result = start_free;
        start_free += total_bytes;
        return(result);
				//如果剩余的内存小于size*nobjs, 大于size,则表明可以申请至少一个size大小的内存块。
    } else if (bytes_left >= size) {
				//计算剩余可以容纳size大小的个数
        nobjs = bytes_left/size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return(result);
				//这样处理后,可能剩余有<size大小的零头
    } else {
			//没办法,内存池已经不能满足,只能在堆着申请。下面的大小为2倍加上一个指数
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // Try to make use of the left-over piece.
				// 先前内存池中还有零头
        if (bytes_left > 0) {
            obj * __VOLATILE * my_free_list =
                        free_list + FREELIST_INDEX(bytes_left);
				//将这个零头加入到合适的自由链表
            ((obj *)start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
				//从堆中分配内存
        start_free = (char *)malloc(bytes_to_get);
				//堆中不能分配bytes_to_get大小的块,怎么办呢?
				//那就从自由链表中将未使用的都划出来
        if (0 == start_free) {
            int i;
            obj * __VOLATILE * my_free_list, *p;
            // Try to make do with what we have.  That can't
            // hurt.  We do not try smaller requests, since that tends
            // to result in disaster on multi-process machines.
						// 因为至少需要size大小,所以从size大小开始扫描自由链表
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
								//发现有空闲的自由链表
                if (0 != p) {
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
										//继续修正nobjs,企图在刚才划出来的内存中再申请nobjs个size块
                    return(chunk_alloc(size, nobjs));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
						//自由链表中已经没有内存,堆中又不能分配内存
	    			end_free = 0;	// In case of exception.
						//交给第一级分配器来分配
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
				//记录内存池的大小
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return(chunk_alloc(size, nobjs));
    }
}

原理是:start_free end_free确定了内存池中没有被分配为自由链表的块。
1.如果内存每次申请任意大小都成功,则start_free永远等于end_free,每次申请的内存都通过refill添加到自由链表。
2.如果在堆中申请的块小于预期(nobjs*size)申请,则会将申请的内存的size整数个返回并通过refill添加到自由链表,这时可能会出现零头。比如预期申请40 = 10*4字节内存,但是结果在堆中分配了30字节,则7个size返回通过refill添加到自由链表,剩下的2个字节则空闲在内存池中,由start_free与end_free限定。在下一次有申请时,可以将这些零头添加到其他的自由链表。
3如果堆中未能分配,则会扫描自由链表中未使用的内存,这时会将该自由链表的第一个块从自由链表中剥离,注入内存池,由start_free与end_free限定。则可以在这个区间中找到可用内存。如果连自由链表中都没有的话,则交给第一级配置器。如果我想分配44字节,但是堆中又不能申请,则会扫描自由链表到索引5(索引5中链接的是大小48的块)。如果索引5中有可用块则将第一个块剥离开来注入内存池,然后再分配出去。如果索引5中没有可用块则继续扫描其他索引….

另外就是注意递归调用的巧妙…

广告位

发表评论

你必须 登陆 方可发表评论.