精华内容
下载资源
问答
  • slab分配

    2020-02-06 20:20:22
    Linux内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求,它所分配的内存区是以页框为基本单位的。...为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分...

    Linux内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求,它所分配的内存区是以页框为基本单位的。对于内核中小块连续内存的请求,比 如说几个字节或者几百个字节,如果依然分配一个页框来来满足该请求,那么这很明显就是一种浪费,即产生内部碎片(internal fragmentation)
    为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分配器。除此之外,slab分配器另一个主要功能是作为一个高速缓存,它用来存储内核中那些经常分配并释放的对象。

    Slab分配器的原理

    slab分配器中用到了对象这个概念,所谓对象就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。它的基本思想是将内核中经常使用的对象 放到高速缓存中,并且由系统保持为初始的可利用状态。比如进程描述符,内核中会频繁对此数据进行申请和释放。当一个新进程创建时,内核会直接从slab分 配器的高速缓存中获取一个已经初始化了的对象;当进程结束时,该结构所占的页框并不被释放,而是重新返回slab分配器中。如果没有基于对象的slab分 配器,内核将花费更多的时间去分配、初始化以及释放一个对象。

    slab分配器有以下三个基本目标:
    1.减少伙伴算法在分配小块连续内存时所产生的内部碎片;
    2.将频繁使用的对象缓存起来,减少分配、初始化和释放对象的时间开销。
    3.通过着色技术调整对象以更好的使用硬件高速缓存;

    Slab相关数据结构

    在这里插入图片描述

    Kmem_cache_t是高速缓存描述符,每一类对象都有一个kmem_cache_t,当申请类的对象所需要的内存时,就向对应的kmem_cache_t中取申请,每个kmem_cache_t包含了slabs_full、slabs_prtial、slabs_empty三个链表,分别代表已使用完、部分空闲、完全空闲三个slab块,不过需要注意的是,当刚刚申请一类对象的高速缓存描述符kmem_cache_t时,kmem_cache_t是没有空闲的slab的,当第一次分配slab空间时才会向伙伴系统申请内存页空间。
    Kmem_cache_t也是一类slab对象,这类slab是通过cache_chain来申请的,cache_chain的类型也是kmem_cache_t,只不过cache_chain是静态定义的,这就避免了鸡生蛋蛋生鸡的问题。
    当该类kmem_cache_t中没有空闲的slab对象时,就会向伙伴系统申请一组连续空闲页空间,这段页空间包含slab偏移、slab描述符、对象描述符和对象空间,关系如下:

    其中对象描述符标识了对应对象有没有被分配。

    slab分配器初始化

    Linux将高速缓存分为普通高速缓存和专用高速缓存
    高速缓存又分成两种类型:普通的和专用的。普通高速缓存是slab用于自己目的的缓存,比方kmem_cache就是slab用来分配其余高速缓存描述符的,再比如上面讲到的kmalloc对应的缓存。而专用缓存是内核其它地方用到的缓存。普通缓存调用kmem_cache_init接口来初始化,其中cache_cache保存着第一个缓存描述符。专用缓存调用的是kmem_cache_create接口来创建。

    kmem_cache_init
    list_add(&cache_cache.next, &cache_chain);
        cache_cache.colour_off = cache_line_size(); //256
        cache_cache.array[smp_processor_id()] = &initarray_cache.cache; //首先是静态定义的array_cache
        cache_cache.objsize = ALIGN(cache_cache.objsize, cache_line_size()); //往上对齐
        //计算一页可以保存多少slab的对象,并且还剩多少空间
        cache_estimate(0, cache_cache.objsize, cache_line_size(), 0, &left_over, &cache_cache.num);
            size_t wastage = PAGE_SIZE<<gfporder;
            if (!(flags & CFLGS_OFF_SLAB)) //slab管理结构在slab内部
                base = sizeof(struct slab);
                extra = sizeof(kmem_bufctl_t);  //typedef unsigned short kmem_bufctl_t;
            while (i*size + ALIGN(base+i*extra, align) <= wastage) 
                i++;
            if(i > 0) i--;
            *num = i;
            wastage -= i*size;
            wastage -= ALIGN(base+i*extra, align);
            *left_over = wastage;
        cache_cache.colour = left_over/cache_cache.colour_off;
        cache_cache.colour_next = 0;
        //一个slab元数据对齐后的大小
        cache_cache.slab_size = ALIGN(cache_cache.num*sizeof(kmem_bufctl_t) + sizeof(struct slab), cache_line_size());
    	sizes = malloc_sizes;
    	names = cache_names;    
        
        //初始化mem_size,用于kmalloc
        while(sizes->cs_size)
        {
            sizes->cs_cachep = kmem_cache_create(names->name, sizes->cs_size, ARCH_KMALLOC_MINALIGN, (ARCH_KMALLOC_FLAGS | SLAB_PANIC), NULL, NULL);
            sizes->cs_dmacachep = kmem_cache_create(names->name_dma, sizes->cs_size, ARCH_KMALLOC_MINALIGN, (ARCH_KMALLOC_FLAGS | SLAB_CACHE_DMA | SLAB_PANIC), NULL, NULL);
            sizes++;
            names++;
        }
        
        ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
            if (__builtin_constant_p(size))
                return kmem_cache_alloc((flags & GFP_DMA) ? malloc_sizes[i].cs_dmacachep :malloc_sizes[i].cs_cachep, flags);
                    
            else
                __kmalloc(size, flags);
            
        memcpy(ptr, ac_data(&cache_cache), sizeof(struct arraycache_init)); //arraycache_init和araycache结构体大小相同
        //ac_data为return cachep->array[smp_processor_id()];
        cache_cache.array[smp_processor_id()] = ptr;  //更换高速缓存指针的内容
        
        ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
        memcpy(ptr, ac_data(malloc_sizes[0].cs_cachep), sizeof(struct arraycache_init));
        malloc_sizes[0].cs_cachep->array[smp_processor_id()] = ptr;
        
        g_cpucache_up = FULL;
    

    从上面可以看到kmem_cache_init的作用有以下几点
    (1)初始化kmalloc里各大小的高速缓存描述符
    (2)初始化cache_cache里的各项数据,比如对象大小、slab大小。

    创建高速缓存

    一个新创建的高速缓存没有包含任何slab,因此也没有空闲的对象。只有当以下两个条件都为真时,才给高速缓存分配slab:
    (1)已发出一个分配新对象的请求
    (2)高速缓存不包含任何空闲对象
    实际上,cache_cache就是一个高速缓存,kmem_cache_create就是从cache_cache高速缓存中分配一个kmem_cache_t对象,最初cache_cache中是没有任何slab的,所以先需要像伙伴算法系统申请内存页面。

    kmem_cache_create
        cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL); //从cache_cache里申请的slab就是为了存放kmem_cache_t
            return __cache_alloc(cachep, flags);  //cachep就是 cache_cache
                ac = ac_data(cachep); //返回struct array_cache	*array[NR_CPUS];中的某项
                    return cachep->array[smp_processor_id()];
                //静态初始化array_cache时,avail为0
                if (likely(ac->avail))  //缓存中仍然有之前申请的内存
                    ac->touched = 1;    
                    objp = ac_entry(ac)[--ac->avail];
                else
                    objp = cache_alloc_refill(cachep, flags){ //第一次扩充的是cache_cache中的slab,返回的是最后插入到cache_array中的最后一个object的指针
                        ac = ac_data(cachep); //访问cache_cache的array,被初始化为&initarray_cache.cache;
                        retry:
                            batchcount = ac->batchcount; //一开始为1
                            
                            /*
                            #define list3_data(cachep) (&(cachep)->lists)
                            */
                            l3 = list3_data(cachep);
                            
                            while (batchcount > 0)  //batchcount 初始化为1
                                entry = l3->slabs_partial.next;
                                if (entry == &l3->slabs_partial)//先从部分链表找
                                    l3->free_touched = 1;
                                    entry = l3->slabs_free.next;  //再从空闲链表找
                                    if (entry == &l3->slabs_free) //两个链表都没有,需要扩充slab
                                        goto must_grow;
                            slabp = list_entry(entry, struct slab, list); 
                            while (slabp->inuse < cachep->num && batchcount--)
                                ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize; //return (void**)(ac+1);
                                    return (void**)(ac+1);
                                slabp->inuse++;
    							//更新slabp->free,该值指向下一个空闲的对象
                                next = slab_bufctl(slabp)[slabp->free]; //return (kmem_bufctl_t *)(slabp+1);
                                slabp->free = next;
                            list_del(&slabp->list);
                            if (slabp->free == BUFCTL_END)
                                list_add(&slabp->list, &l3->slabs_full);
                            else
                                list_add(&slabp->list, &l3->slabs_partial);
                                
                        must_grow:
                            l3->free_objects -= ac->avail;  //一开始avail为0
                        alloc_done:
                            if (unlikely(!ac->avail))
                                x = cache_grow(cachep, flags, -1){   //cachep最开始为cache_cache
                                    offset = cachep->colour_next;
                                    cachep->colour_next++;
                                    if (cachep->colour_next >= cachep->colour)
                                        cachep->colour_next = 0
                                    offset *= cachep->colour_off;//横跨一个cache line ?
                                    objp = kmem_getpages(cachep, flags, nodeid)//返回页对应的虚拟地址
                                        if (likely(nodeid == -1))
                                            page = alloc_pages(flags, cachep->gfporder);
                                                alloc_pages_node(numa_node_id(), gfp_mask, order)
                                                    return __alloc_pages(gfp_mask, order, NODE_DATA(nid)->node_zonelists + (gfp_mask & GFP_ZONEMASK));
                                        else
                                            page = alloc_pages_node(nodeid, flags, cachep->gfporder);
                                        addr = page_address(page); //virtual
                                        while (i--)
                                            SetPageSlab(page);
                                                set_bit(PG_slab, &(page)->flags) //设置flags的第PG_slab位
                                            page++;
                                        return addr;
                                    slabp = alloc_slabmgmt(cachep, objp, offset, local_flags)
                                        slabp = objp+colour_off; //省略部分内存
                                        colour_off += cachep->slab_size; //跨过元数据
                                    	slabp->inuse = 0;
                                        slabp->colouroff = colour_off; //该slab内的偏移,也是真实对象的偏移
                                        slabp->s_mem = objp+colour_off; //真实数据开始的位置
                                        return slabp;
                                    set_slab_attr(cachep, slabp, objp);    
                                        i = 1 << cachep->gfporder;
                                        page = virt_to_page(objp);
                                            pfn_to_page(__pa(kaddr) >> PAGE_SHIFT) 
                                            //#define pfn_to_page(pfn)	(mem_map + (pfn)) 
                                            //#define __pa(x)			((unsigned long)(x)-PAGE_OFFSET)
                                        do {
                                            //#define	SET_PAGE_CACHE(pg,x)  ((pg)->lru.next = (struct list_head *)(x))
                                            SET_PAGE_CACHE(page, cachep);
                                                ((pg)->lru.next = (struct list_head *)(x))
                                            //#define	SET_PAGE_SLAB(pg,x)   ((pg)->lru.prev = (struct list_head *)(x))
                                            SET_PAGE_SLAB(page, slabp);
                                                ((pg)->lru.prev = (struct list_head *)(x))
                                            page++;
                                        }while(--i)
                                    cache_init_objs(cachep, slabp, ctor_flags);  
                                        for (i = 0; i < cachep->num; i++)
                                            void* objp = slabp->s_mem+cachep->objsize*i;//获取第i个对象
                                            if (cachep->ctor)
                                                cachep->ctor(objp, cachep, ctor_flags);
                                            slab_bufctl(slabp)[i] = i+1;  //return (kmem_bufctl_t *)(slabp+1);,取slabp下一个字节的位置
                                                return (kmem_bufctl_t *)(slabp+1); //跨过slab元数据,直达描述符
                                        slab_bufctl(slabp)[i-1] = BUFCTL_END;
                                        slabp->free = 0;
                                    list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_free));  //刚开始加入到free链表中
                                    list3_data(cachep)->free_objects += cachep->num;    
                                ac = ac_data(cachep); 
                                if(!ac->avail)
                                    goto retry;
                            }  
                            ac->touched = 1;
                            return ac_entry(ac)[--ac->avail];
                    }
                objp = cache_alloc_debugcheck_after(cachep, flags, objp, __builtin_return_address(0));
                return objp;   
    
        cache_estimate(cachep->gfporder, size, align, flags, &left_over, &cachep->num); 
        cachep->gfporder++;
        slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t) + sizeof(struct slab), align);
        memset(cachep, 0, sizeof(kmem_cache_t)); 
        slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t)+ sizeof(struct slab), align);
        cachep->colour_off = cache_line_size();
        cachep->colour = left_over/cachep->colour_off;
    	//slab描述符和对象描述符的大小
        cachep->slab_size = slab_size;
        cachep->flags = flags;
        cachep->gfpflags = 0;
        cachep->objsize = size;
    	INIT_LIST_HEAD(&cachep->lists.slabs_full);
    	INIT_LIST_HEAD(&cachep->lists.slabs_partial);
    	INIT_LIST_HEAD(&cachep->lists.slabs_free);
    	cachep->ctor = ctor;
    	cachep->dtor = dtor;
    	cachep->name = name;
        
        if (g_cpucache_up == FULL)
            enable_cpucache(cachep);
        else
            if (g_cpucache_up == NONE)
                cachep->array[smp_processor_id()] = &initarray_generic.cache;
                g_cpucache_up = PARTIAL;
            else
                //等到第二次运行到这里的适合已经有对应size大小的malloc_sizes[i].cs_cachep了
                cachep->array[smp_processor_id()] = kmalloc(sizeof(struct arraycache_init),GFP_KERNEL);//从已经建立的malloc_sizes中获取合适大小的slab对象
                    if (__builtin_constant_p(size))
                        return kmem_cache_alloc((flags & GFP_DMA) ? malloc_sizes[i].cs_dmacachep :malloc_sizes[i].cs_cachep, flags);
                            return __cache_alloc(cachep, flags);
                                ac = ac_data(cachep);
                                if (likely(ac->avail)) 
                                    ac->touched = 1;
                                    objp = ac_entry(ac)[--ac->avail];
                                else
                                    objp = cache_alloc_refill(cachep, flags);
                    else
                        __kmalloc(size, flags);                
            ac_data(cachep)->avail = 0;
            ac_data(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
            ac_data(cachep)->batchcount = 1;
            ac_data(cachep)->touched = 0;
            
        list_add(&cachep->next, &cache_chain);
    return cachep;
    
    kmem_cache_alloc就是从slab中分配指定的对象,但是最初kmem_cache_t中是没有任何slab空间的,所以需要先像伙伴算法系统中申请页空间,我们建立专用高速缓存时,就要先用kmem_cache_create建立高速缓存,然后再调用kmem_cahce_alloc从我们建立的高速缓存中分配对象空间。
    

    释放slab对象

    kmem_cache_free
    	//将对象空间回收到指定的高速缓存中
        __cache_free(cachep, objp);
            struct array_cache *ac = ac_data(cachep);
                return cachep->array[smp_processor_id()];
            if (likely(ac->avail < ac->limit))
                ac_entry(ac)[ac->avail++] = objp;
            else
                cache_flusharray(cachep, ac);
                    batchcount = ac->batchcount;
    				//释放batchcount个对象空间
                    free_block(cachep, &ac_entry(ac)[0], batchcount);
                        cachep->lists.free_objects += nr_objects;
                        for (i = 0; i < nr_objects; i++)
                            void *objp = objpp[i];
    						//((struct slab *)(pg)->lru.prev)指向相应的slab描述符
    						//如果一个页是分配给slab,则页描述符的lru.prev指向相应的slab描述符
                            slabp = GET_PAGE_SLAB(virt_to_page(objp));
                            list_del(&slabp->list);
    						//计算slab内对象的下标
    						objnr = (objp - slabp->s_mem) / cachep->objsize;
    						
    						//将该对象插入到slab空闲“链表”中,并将空闲对象游标指向该对象
    						slab_bufctl(slabp)[objnr] = slabp->free;
    						slabp->free = objnr;
    						
    						slabp->inuse--;
    						//如果inuse等于0,即slab中所有对象空闲
    						if (slabp->inuse == 0)
    							//并且整个slab高速缓存中空闲对象的个数(cachep->lists.free_objects)大于cachep->free_limit
    							if (cachep->lists.free_objects > cachep->free_limit)
    								cachep->lists.free_objects -= cachep->num;
    								//将slab的页框释放到分区页框分配器
    								slab_destroy(cachep, slabp);
    							else
    								//否则函数将slab描述符插入到slabs_free链表中
    								list_add(&slabp->list, &list3_data_ptr(cachep, objp)->slabs_free);
    						else
    							//inuse > 0,slab被部分填充,则将slab描述符插入到slabs_partial中
    							list_add_tail(&slabp->list,&list3_data_ptr(cachep, objp)->slabs_partial);
    				ac->avail -= batchcount;
    				//移动本地高速缓存数组起始处的那个本地高速缓存中的所有指针。
    				//因为已经把第一个对象指针从本地高速缓存上删除,因此剩余的指针必须上移。
    				memmove(&ac_entry(ac)[0], &ac_entry(ac)[batchcount],sizeof(void*)*ac->avail);
    			//更新空闲对象的指针
                ac_entry(ac)[ac->avail++] = objp;
    

    通用对象

    在kmem_cache_init中,我们还创建了固定大小的高速缓存存放在malloc_sizes中,范围是32~131072字节,当我们调用kmalloc来申请内存时,会从malloc_sizes中第一个大于要分配大小的高速缓存中分配对象空间

    kmalloc(size_t size, int flags)
    	if (__builtin_constant_p(size))
    		#define CACHE(x) \
    				if (size <= x) \
    					goto found; \
    				else \
    					i++;
    		#include "kmalloc_sizes.h"
    				/**
    				 * 运行到此,说明要分配的对象太大,不能分配这么大的对象。
    				 */
    		#undef CACHE	
    		//请求分配的size对应的高速缓存描述符索引号为i,从malloc_sizes[i]中分配对象空间
    		return kmem_cache_alloc((flags & GFP_DMA) ? malloc_sizes[i].cs_dmacachep : malloc_sizes[i].cs_cachep, flags);
    	return __kmalloc(size, flags);
    		for (; csizep->cs_size; csizep++) 
    			if (size > csizep->cs_size)
    				continue;
    			//从对应的高速缓存中申请对象空间
    			return __cache_alloc(flags & GFP_DMA ?csizep->cs_dmacachep : csizep->cs_cachep, flags);
    
    展开全文
  • Linux系统中SLAB分配器内存回收算法分析和优化,陈卉,张振华,SLAB分配器在linux系统中的使用大大提高了内核中分配内存对象的效率,并且解决了小对象分配内存时产生的内存碎片问题。而该分配器的
  • Linux内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求,它所分配的内存区是以页框为基本单位的。...为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分配...

    Linux内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求,它所分配的内存区是以页框为基本单位的。对于内核中小块连续内存的请求,比如说几个字节或者几百个字节,如果依然分配一个页框来来满足该请求,那么这很明显就是一种浪费,即产生内部碎片(internal fragmentation)

    为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分配器。除此之外,slab分配器另一个主要功能是作为一个高速缓存,它用来存储内核中那些经常分配并释放的对象。

    1.slab分配器的基本原理

    slab分配器中用到了对象这个概念,所谓对象就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。它的基本思想是将内核中经常使用的对象放到高速缓存中,并且由系统保持为初始的可利用状态。比如进程描述符,内核中会频繁对此数据进行申请和释放。当一个新进程创建时,内核会直接从slab分配器的高速缓存中获取一个已经初始化了的对象;当进程结束时,该结构所占的页框并不被释放,而是重新返回slab分配器中。如果没有基于对象的slab分配器,内核将花费更多的时间去分配、初始化以及释放一个对象。

    slab分配器有以下三个基本目标:

    1. 减少伙伴算法在分配小块连续内存时所产生的内部碎片;

    2. 将频繁使用的对象缓存起来,减少分配、初始化和释放对象的时间开销。

    3. 通过着色技术调整对象以更好的使用硬件高速缓存;

    2.slab分配器的结构

    slab分配器为每种对象分配一个高速缓存,这个缓存可以看做是同类型对象的一种储备。每个高速缓存所占的内存区又被划分多个slab,每个slab是由一个或多个连续的页框组成。每个页框中包含若干个对象,既有已经分配的对象,也包含空闲的对象。slab分配器的大致组成图如下:

    在这里插入图片描述
    每个高速缓存通过kmem_cache结构来描述,这个结构中包含了对当前高速缓存各种属性信息的描述。所有的高速缓存通过双链表组织在一起,形成高速缓存链表cache_chain。每个kmem_cache结构中并不包含对具体slab的描述,而是通过kmem_list3结构组织各个slab。该结构的定义如下:

    struct kmem_list3 {
            struct list_head slabs_partial;
            struct list_head slabs_full;
            struct list_head slabs_free;
            unsigned long free_objects;
            unsigned int free_limit;
            unsigned int colour_next;
            spinlock_t list_lock;
            struct array_cache *shared;
            struct array_cache **alien;
            unsigned long next_reap;
            int free_touched;
    };
    

    可以看到,该结构将当前缓存中的所有slab分为三个集合:空闲对象的slab链表slabs_free,非空闲对象的slab链表slabs_full以及部分空闲对象的slab链表slabs_partial。每个slab有相应的slab描述符,即slab结构,它的定义如下:

    struct slab {
            struct list_head list;
            unsigned long colouroff;
            void *s_mem;
            unsigned int inuse;
            kmem_bufctl_t free;
            unsigned short nodeid;
    };
    

    slab描述符中的list字段标明了当前slab处于三个slab链表的其中一个。我们将上述的slab分配器进行细化,可以得到下面的结构图:
    在这里插入图片描述

    3.高速缓存的分类

    slab高速缓存分为两大类,普通高速缓存和专用高速缓存。普通高速缓存并不针对内核中特定的对象,它首先会为kmem_cache结构本身提供高速缓存,这类缓存保存在cache_cache变量中,该变量即代表的是cache_chain链表中的第一个元素;另一方面,它为内核提供了一种通用高速缓存。专用高速缓存是根据内核所需,通过指定具体的对象而创建。

    3.1 普通高速缓存

    slab分配器中kmem_cache是用来描述高速缓存的结构,因此它本身也需要slab分配器对其进行高速缓存。cache_cache变量保存着对高速缓存描述符的高速缓存。

    static struct kmem_cache cache_cache = {
            .batchcount = 1,
            .limit = BOOT_CPUCACHE_ENTRIES,
            .shared = 1,
            .buffer_size = sizeof(struct kmem_cache),
            .name = "kmem_cache",
    };
    

    slab分配器所提供的小块连续内存的分配是通过通用高速缓存实现的。通用高速缓存所提供的对象具有几何分布的大小,范围为32到131072字节。内核中提供了kmalloc()和kfree()两个接口分别进行内存的申请和释放。

    3.2 专用高速缓存

    内核为专用高速缓存的申请和释放提供了一套完整的接口,根据所传入的参数为具体的对象分配slab缓存。
    高速缓存的申请和释放
    kmem_cache_create()用于对一个指定的对象创建高速缓存。它从cache_cache普通高速缓存中为新的专有缓存分配一个高速缓存描述符,并把这个描述符插入到高速缓存描述符形成的cache_chain链表中。kmem_cache_destory()用于撤销一个高速缓存,并将它从cache_chain链表上删除。
    slab的申请和释放
    kmem_cache_alloc()在其参数所指定的高速缓存中分配一个slab。相反,kmem_cache_free()在其参数所指定的高速缓存中释放一个slab。

    展开全文
  • slab算法

    千次阅读 2018-05-06 21:23:36
    slab算法提出原因:Buddy 系统解决了物理内存分配的外部碎片问题,但由于粒度太大(内存块的单位较大),以页为单位,采用伙伴算法分配内存时,每次至少分配一个页面(4K),显然用起来有些浪费,当如果要申请一些小的...

    slab算法提出原因:

    Buddy 系统解决了物理内存分配的外部碎片问题,但由于粒度太大(内存块的单位较大),以页为单位,采用伙伴算法分配内存时,每次至少分配一个页面(4K),显然用起来有些浪费,当如果要申请一些小的内存(请求分配的内存大小为几十个字节或几百个字节时,对于小块内存的分配和回收),并且会频繁的申请相同数据结构的内存来存储一些内核中的数据时,这时 Slab 便应运而生了。

    在内核中,经常会使用一些链表,链表中会申请许多相同结构的结构体,比如文件对象,进程对象等等,如果申请比较频繁,那么为它们建立一个内存池,内存池中都是相同结构的结构体,当想申请这种结构体时,直接从这种内存池中取一个结构体出来,是有用且速度极快的。一个物理页就可以作用这种内存池的载体,进而进行充分利用,减少了内部碎片的产生。

    所以,Slab 相当于内存池思想,且是为了解决内碎片而产生的,slab的核心思想是以对象的观点管理内存。

    实际上内核中slab分配器对不同长度内存是分档的,这是slab分配器的一个基本原则,按申请的内存的大小分配相应长度的内存。同时也说明一个事实,内核中一定应该有这样的按不同长度slab内存单元,也就是说已经创建过这样的内存块,否则申请时怎能根据大小识别应该分配给怎样大小的内存。(这可以先参考kmalloc的实现,kmalloc申请的物理内存长度为参数size,它需要先根据这个长度找到相应的长度的缓存)。slab分配器并非一开始就能智能的根据内存分档值分配相应长度的内存。每种cache对应一种长度的slab分配slab分配接口,一个是函数kmalloc一个是函数kmem_cache_allockmalloc的参数比较轻松,直接输入自己想要的内存长度即可,由slab分配器去找应该是属于哪个长度分档的,然后由那个分档的kmem_cache结构指针去分配相应长度内存,而kmem_cache_alloc就显得比较“专业”,它不是输入我要多少长度内存,而是直接以kmem_cache结构指针作为参数,直接指定我要这样长度分档的内存。内核slab分配器能够默认的提供32-4194304共20种内存长度分档,肯定是需要创建这样20个“规则”的,这是在初始化时创建的。

    比如需要一个100字节的连续物理内存,那么内核slab分配器会给我提供一个相应大小的连续物理内存单元(2的次幂),为128字节大小(不会是整好100字节,而是这个档的一个对齐值,如100字节对应128字节,30字节对应32字节,60字节对应64字节),这个物理内存实际上是从伙伴系统获取的物理页;当不再需要这个内存时应该释放它,释放它并非把它归还给伙伴系统,而是归还给slab分配器,这样等再需要获取时无需再从伙伴系统申请,这也就是为什么slab分配器往往会把最近释放的内存(即所谓“热”)分配给申请者,这样效率是比较高的。

    对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此不应该将内存释放回一个全局的内存池,而是将内存保持为针对特定目的而初始化的状态。

    slab分配器是基于对象进行管理的,所谓的对象就是存放一组数据结构的内存区,为便于理解可把对象看作内核中的数据结构(例如:task_struct,file_struct 等),其方法就是构造或析构函数,构造函数用于初始化数据结构所在的内存区,而析构函数收回相应的内存区。相同类型的对象归为一类,每当要申请这样一个对象时,slab分配器就从一个slab列表中分配一个这样大小的单元出去,而当要释放时,将其重新保存在该列表中,而不是直接返回给伙伴系统,从而避免内部碎片。slab分配器并不丢弃已经分配的对象,而是释放并把它们保存在内存中。slab分配对象时,会使用最近释放的对象的内存块,因此其驻留在cpu高速缓存中的概率会大大提高。为了避免重复初始化对象,Slab分配模式并不丢弃已分配的对象,而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时,就可以从内存获取而不用进行初始化,这是在Solaris 中引入Slab的基本思想。实际上,Linux中对Slab分配模式有所改进,它对内存区的处理并不需要进行初始化或回收。出于效率的考虑,Linux并不调用对象的构造或析构函数,而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。

    实际上,内核经常反复使用某一内存区。例如,只要内核创建一个新的进程,就要为该进程相关的数据结构(task_struct、打开文件对象等)分配内存区。当进程结束时,收回这些内存区。因为进程的创建和撤销非常频繁,因此,Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始,把那些频繁使用的页面保存在高速缓存中并重新使用。

    Slab分配模式把对象分组放进缓冲区(尽管英文中使用了Cache这个词,但实际上指的是内存中的区域,而不是指硬件高速缓存)。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关,因此,Slab缓冲区并非由各个对象直接构成,而是由一连串的“大块(Slab)”构成,而每个slab中则包含了若干个同种类型的对象,这些对象或已被分配,或空闲。一般而言,对象分两种,一种是大对象,一种是小对象。所谓小对象,是指在一个页面中可以容纳下好几个对象的那种。例如,一个inode结构大约占300多个字节,因此,一个页面中可以容纳8个以上的inode结构,因此,inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。

    实际上,缓冲区就是主存中的一片区域,把这片区域划分为多个块,每块就是一个Slab,每个Slab由一个或多个页面组成,每个Slab中存放的就是对象。

     下图是slab 结构的高层组织结构。在最高层是 cache_chain,这是一个 slab 缓存的链接列表。这对于 best-fit 算法非常有用,可以用来查找最适合所需要的分配大小的缓存(遍历列表)。cache_chain 的每个元素都是一个 kmem_cache 结构的引用(称为一个 cache)。它定义了一个要管理的给定大小的对象池。

    每个缓存都包含了一个 slabs 列表,这是一段连续的内存块(通常都是页面)。存在 3 种 slab:
    slabs_full:完全分配的 slab
    slabs_partial:部分分配的 slab
    slabs_free:空 slab,或者没有对象被分配
    注意 slabs_free 列表中的 slab 是进行回收(reaping)的主要备选对象。正是通过此过程,slab 所使用的内存被返回给操作系统供其他用户使用。
    slab 列表中的每个 slab 都是一个连续的内存块(一个或多个连续页,通常为一页),它们被划分成一个个对象。这些对象是从特定缓存中进行分配和释放的基本元素。注意 slab 是 slab 分配器进行操作的最小分配单位,因此如果需要对 slab 进行扩展,这也就是所扩展的最小值。通常来说,每个 slab 被分配为多个对象。

    由于对象是从 slab 中进行分配和释放的,因此单个 slab 可以在 slab 列表之间进行移动。例如,当一个 slab 中的所有对象都被使用完时,就从 slabs_partial 列表中移动到 slabs_full 列表中。当一个 slab 完全被分配并且有对象被释放后,就从 slabs_full 列表中移动到 slabs_partial 列表中。当所有对象都被释放之后,就从 slabs_partial 列表移动到 slabs_free 列表中。

    slab 分配器首先从部分空闲的slab 进行分配。如没有,则从空的slab 进行分配。如没有,则从物理连续页上分配新的slab,并把它赋给一个cache ,然后再重新slab 分配空间。

    举例说明:如果有一个名叫inode_cachep的struct kmem_cache节点,它存放了一些inode对象。当内核请求分配一个新的inode对象时,slab分配器就开始工作了:

    • 首先要查看inode_cachep的slabs_partial链表,如果slabs_partial非空,就从中选中一个slab,返回一个指向已分配但未使用的inode结构的指针。完事之后,如果这个slab满了,就把它从slabs_partial中删除,插入到slabs_full中去,结束;
    • 如果slabs_partial为空,也就是没有半满的slab,就会到slabs_empty中寻找。如果slabs_empty非空,就选中一个slab,返回一个指向已分配但未使用的inode结构的指针,然后将这个slab从slabs_empty中删除,插入到slabs_partial(或者slab_full)中去,结束;
    • 如果slabs_empty也为空,那么没办法,cache内存已经不足,只能新创建一个slab了。


    其实slab机制的简介表示如下图所示:


    slab内的结构如下图所示:

     每个Slab的首部都有一个小小的区域是不用的,称为“着色区(coloring area)”。着色区的大小使Slab中的每个对象的起始地址都按高速缓存中的缓存行(cache line)”大小进行对齐(80386的一级高速缓存行大小为16字节,Pentium为32字节)。因为Slab是由1个页面或多个页面(最多为32)组成,因此,每个Slab都是从一个页面边界开始的,它自然按高速缓存的缓冲行对齐。但是,Slab中的对象大小不确定设置着色区的目的就是将Slab中第一个对象的起始地址往后推到与缓冲行对齐的位置。因为一个缓冲区中有多个Slab,因此,应该把每个缓冲区中的各个Slab着色区的大小尽量安排成不同的大小,这样可以使得在不同的Slab中,处于同一相对位置的对象,让它们在高速缓存中的起始地址相互错开,这样就可以改善高速缓存的存取效率

     每个Slab上最后一个对象以后也有个小小的废料区是不用的,这是对着色区大小的补偿,其大小取决于着色区的大小,以及Slab与其每个对象的相对大小。但该区域与着色区的总和对于同一种对象的各个Slab是个常数

     每个对象的大小基本上是所需数据结构的大小。只有当数据结构的大小不与高速缓存中的缓冲行对齐时,才增加若干字节使其对齐。所以,一个Slab上的所有对象的起始地址都必然是按高速缓存中的缓冲行对齐的。

     Slab 算法的结构图:

    一个高速缓存即 kmem_cache ,就代表一个结构体的内存池,它有一个每 CPU 数据 array, 进一步加快了申请速度,解决了多 CPU 加锁,且小数据缓存的目的,因为保留少量的频繁申请和释放得来的空间,等下次申请时直接从这里取得,由于结构简单,所以速度极快。所以每一个 CPU 都会对应一个 array_cache 结构体,在内存布局上,该结构体后面,紧接着有一个数组,数组项就是一些结构体内存的指针,vail  即可计算空闲项的下标,这样,当出现一个申请请求时,直接从这里取一个结构体块的指针,(这里的结构体我们称之为对象)然后返回,效率极高。释放时,原理相同,细节很简单,这里不讨论。
            那对象的具体内存是在哪里呢?
            这里称之为对象,Slab 采用了面向对象的概念,每一个结构体看作是一个对象,它们有共用的构造和析构的方法,其实就是为一些结构体赋值和释放。它们存放的位置才是 slab 的关键所在,在每一种对象内存池中,即 kmem_cache 中,有三个链表,slabs_partial, slabs_full, slabs_free, 链表元素都是 slab 结构体,而 slab 结构体所描述的就是对象的内存空间,顾名思义,这三个链表分别代表,slab 里对象部分被装满,全满,全空三种链表,重点就在这 slab 结构里。
            每一个 Slab 描述了这种类型对象内存池中的一小部分内存,它会描述一段对象数组的使用情况,通过 slab 描述符可以得到一些未使用的对象的地址。从这句话里,可以知道,一个 slab 描述的对象的内存都相当于数组般连续排列的。这个数组的起始地址非常重要,因为考虑到了 Cache line,所以起始地址都会以 cache line 对齐,这样理想情况下,对象会被装入一整条 cache line 中,也容易再次命中。但如果两个 slab 中的对象对齐到同一 cache line ,事必会造成 cache line 不命中而重新读取 RAM,所以尽量使每个 slab 的对象的开始地址分配到不同 cache line 中,就有了每个 slab 都会有一个 colouroff 作为随机种子,来使对象起始地址分散到不同 cache line 中。但我认为这种效果意义不大,但有了这个随机种子,总是会起到一点效果的。
            对象所占用的空间也会进行取整,规则如下:
            1. 如果 对象的大小大于 cache line 的一半,那么就以 L1_CACHE_BYTES 的倍数对齐对象
            2. 否则,对象大小就是 L1_CACHE_BYTES 的因子取整 ,这样一个小对象,就不会跨越两个 cache line。即 cache line 一直除以 2 ,找到一个刚好大于对象大小的值,作为对象的大小来处理。
            这们,当对象的起始地址,以及大小决定以后,然后再从物理页中安排这些对象数组就变得简单了。此时有个情况,因为当从伙伴系统中申请物理页来作为对象缓冲池时,既可以把 slab 的描述符与它描述的对象池放在一起,也可以分开放,放在一起,即 slab 描述符后面,就是对象池,反之,就是分开存储,两者皆可,取决于 slab 中存放的对象的个数。
            讲到这里,某一对象的缓冲池差不多建好了,那么一个 slab 描述符如何描述自己的对象池呢,如上图,每一个 slab 描述符后面,紧接着是它所描述对象的 对象描述符 ,对象描述符是一个无符号整型数, 只有在它所描述的对象空闲时才有意义 当某一对象空闲时,它的描述符包含下一个空闲对象在该 slab 中的下标,最后一个空闲对象的对象描述符的值为 BUFCTL_END. 这样便形成了一个空闲链表
            总结一下,slab 算法中申请某一对象的情景,当为某一结构体创建一个高速缓存时,会调用,kmem_cache_create 来创建一个上图中的结构,此时就可以从该高速缓冲申请该结构体的内存了,申请是通过 kmem_cache_alloc, 来分配,它首先检查每 CPU 高速缓存中是否可以得到一个空闲对象,如果没有,那么它从 slab 链表中选取一个,得到空闲对象,去填充每 CPU 高速缓存,然后再从每 CPU 高速缓存中返回一个空闲对象的地址,释放过程与之相反。

    有关slab的着色问题

    着色与硬件cache有关,这就牵扯到cache和主存的工作结构:

    1. 全相连 
      • 任一主存块能映射到任意缓存行(主存块的大小等于缓存行的大小)。
      • 优点:灵活,不易产生冲突
      • 缺点:比较难于实现,且效率低,速度慢
    2. 直接映射 
      • 某一主存块只能映射到特定的缓存行
      • 优点:硬件简单,成本低
      • 缺点:容易产生冲突,易产生缓存“颠簸”,不能有效利用cache空间
    3. 组相联 
      • 组间直接映射,组内全相联映射
      • 优点:结合上面两种的优点 
        • 因为组内行数较少,比较器容易实现
        • 组内又有灵活性,冲突大大减小

    由上可知,slab着色对于直接映射和组相联映射的工作结构效率帮助较大,而全项联结构本身冲突就比较小,那么着色的帮助是很小的。在全相连工作结构中,使用着色无疑是一个巨大的内存浪费。 

    slab算法的缺点

    随着大规模多处理器系统和NUMA系统的广泛应用,slab分配器逐渐暴露出自身严重的不足:

    1. 较多复杂的队列管理。在slab分配器中存在众多的队列,例如针对处理器的本地缓存队列,slab中空闲队列,每个slab处于一个特定状态的队列之中。所以,管理太费劲了。
    2. slab管理数据和队列的存储开销比较大。每个slab需要一个struct slab数据结构和一个管理者kmem_bufctl_t型的数组。当对象体积较小时,该数组将造成较大的开销(比如对象大小为32字节时,将浪费1/8空间)。为了使得对象在硬件告诉缓存中对齐和使用着色策略,还必须浪费额外的内存。同时,缓冲区针对节点和处理器的队列也会浪费不少内存。测试表明在一个1000节点/处理器的大规模NUMA系统中,数GB内存被用来维护队列和对象引用。
    3. 缓冲区回收比较复杂。
    4. 对NUMA的支持非常复杂。slab对NUMA的支持基于物理页框分配器,无法细粒度的使用对象,因此不能保证处理器级的缓存来自同一节点(这个我暂时不太懂)。
    5. 冗余的partial队列。slab分配器针对每个节点都有一个partial队列,随着时间流逝,将有大量的partial slab产生,不利于内存的合理使用。
    6. 性能调优比较困难。针对每个slab可以调整的参数比较复杂,而且分配处理器本地缓存时,不得不使用自旋锁。
    7. 调试功能比较难于使用。

    为了解决以上slab分配器的不足,引入新的解决方案,slub分配器。slub分配器的特点是简化设计理念,同时保留slab分配器的基本思想:每个缓冲区有多个slab组成,每个slab包含固定数目的对象。slub分配器简化了kmem_cache,slab等相关的管理结构,摈弃了slab分配器中的众多队列概念,并针对多处理器、NUMA系统进行优化,从而提高了性能和可扩展性并降低了内存的浪费。并且,为了保证内核其他模块能无缝迁移到slub分配器,API接口函数与slab保持一致。

    缺点简单说就是:

    1. 缓存队列管理复杂;
    2. 管理数据存储开销大;
    3. 对NUMA支持复杂;
    4. 调试调优困难;
    5. 摒弃了效果不太明显的slab着色机制;

    优点

    编辑
    与传统的内存管理模式相比, slab 缓存分配器提供了很多优点。
    1、内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。
    2、slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能,从而避免了常见的碎片问题。
    3、slab 分配器还支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化。
    4、slab 分配器还可以支持硬件缓存对齐和着色,这允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能。
    与传统的内存管理模式相比, slab 缓存分配器提供了很多优点。 首先,内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能,从而避免了常见的碎片问题。slab 分配器还支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化。最后,slab 分配器还可以支持硬件缓存对齐和着色,这允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能。


    展开全文
  • Linux所使用的slab分配器的基础是JeffBonwick 为SunOS操作系统首次引入的一种算法。Jeff的分配器是围绕对象缓存进行的。在内核中,会为有限的对象集(例如文件描述符和其他常见结构)分配大量内存。Jeff 发现对内核...
  • linux slab算法

    2011-08-17 15:18:13
    linux slab 算法详细介绍 Slab分配机制 Slab的基本思想 Slab的数据结构
  • Buddy算法slab分配

    2018-04-18 16:32:53
    具体buddy管理基于位图,其分配回收页面的算法描述如下,buddy算法举例描述:假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面)...

    伙伴Buddy算法解决了外部碎片问题.内核在每个zone区管理着可用的页面,按2的幂级(order)大小排成链表队列,存放在free_area数组。

    具体buddy管理基于位图,其分配回收页面的算法描述如下,

    buddy算法举例描述:

    假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面),如下图所示。

     

     

    order(0)bimap有8个bit位(页面最多16个页面,所以16/2

    order(1)bimap有4个bit位(order0bimap8bit,所以8/2);

    也就是order(1)第一块由两个页框page1 page2组成与order(1)第2块由两个页框page3 page4组成,这两个块之间有一个bit

    order(2)bimap有2个bit位(order1bimap4bit,所以4/2)

    order(3)bimap有1个bit位(order2bimap4bit,所以2/2)

    在order(0),第一个bit表示开始2个页面,第二个bit表示接下来的2个页面,以此类推。因为页面4已分配,而页面5空闲,故第三个bit为1。

    同样在order(1)中,bit3是1的原因是一个伙伴完全空闲(页面8和9),和它对应的伙伴(页面10和11)却并非如此,故以后回收页面时,可以合并。

    分配过程

    当我们需要order1)的空闲页面块时,则执行以下步骤:

    1、初始空闲链表为:

    order(0): 5, 10

    order(1): 8 [8,9]

    order(2): 12 [12,13,14,15]

    order(3):

    2、从上面空闲链表中,我们可以看出,order(1)链表上,有一个空闲的页面块,把它分配给用户,并从该链表中删除。

    3、当我们再需要一个order(1)的块时,同样我们从order(1)空闲链表上开始扫描。

    4、若在order1)上没有空闲页面块,那么我们就到更高的级别(order)上找,order(2)。

    5、此时(order1)上没有空闲页面块)有一个空闲页面块,该块是从页面12开始。该页面块被分割成两个稍微小一些order(1)的页面块,[12,13]和[14,15]。[14,15]页面块加到order1)空闲链表中,同时[1213]页面块返回给用户。

    6、最终空闲链表为:

    order(0): 5, 10

    order(1): 14 [14,15]

    order(2):

    order(3):

    回收过程

    当我们回收页面11order 0)时,则执行以下步骤:

    1找到在order0)伙伴位图中代表页面11的位,计算使用下面公示:

    index = page_idx >> (order + 1)

    = 11 >> (0 + 1)

    = 5

    2、检查上面一步计算位图中相应bit的值。若该bit值为1,则和我们临近的,有一个空闲伙伴。Bit5的值为1(注意是从bit0开始的,Bit5即为第6bit),因为它的伙伴页面10是空闲的。

    3、现在我们重新设置该bit的值为0,因为此时两个伙伴(页面10和页面11)完全空闲。

    4、我们将页面10,从order(0)空闲链表中摘除。

    5、此时,我们对2个空闲页面(页面10和11,order(1))进行进一步操作。

    6、新的空闲页面是从页面10开始的,于是我们在order(1)的伙伴位图中找到它的索引,看是否有空闲的伙伴,以进一步进行合并操作。使用第一步中的计算公司,我们得到bit 2(第3位)。

    7、Bit 2(order(1)位图)同样也是1,因为它的伙伴页面块(页面8和9)是空闲的。

    8、重新设置bit2(order(1)位图)的值,然后在order(1)链表中删除该空闲页面块。

    9、现在我们合并成了4页面大小(从页面8开始)的空闲块,从而进入另外的级别。在order(2)中找到伙伴位图对应的bit值,是bit1,且值为1,需进一步合并(原因同上)。

    10、从oder(2)链表中摘除空闲页面块(从页面12开始),进而将该页面块和前面合并得到的页面块进一步合并。现在我们得到从页面8开始,大小为8个页面的空闲页面块。

    11、我们进入另外一个级别,order(3)。它的位索引为0,它的值同样为0。这意味着对应的伙伴不是全部空闲的,所以没有再进一步合并的可能。我们仅设置该bit为1,然后将合并得到的空闲页面块放入order(3)空闲链表中。

    12、最终我们得到大小为8个页面的空闲块,

     

    buddy避免内部碎片的努力

    物理内存的碎片化一直是Linux操作系统的弱点之一,尽管已经有人提出了很多解决方法,但是没有哪个方法能够彻底的解决,memory buddy分配就是解决方法之一。 我们知道磁盘文件也有碎片化问题,但是磁盘文件的碎片化只会减慢系统的读写速度,并不会导致功能性错误,而且我们还可以在不影响磁盘功能的前提的下,进行磁盘碎片整理。而物理内存碎片则截然不同,物理内存和操作系统结合的太过于紧密,以至于我们很难在运行时,进行物理内存的搬移(这一点上,磁盘碎片要容易的多;实际上mel gorman已经提交了内存紧缩的patch,只是还没有被主线内核接收)。 因此解决的方向主要放在预防碎片上。在2.6.24内核开发期间,防止碎片的内核功能加入了主线内核。在了解反碎片的基本原理前,先对内存页面做个归类:

    1. 不可移动页面 unmoveable:在内存中位置必须固定,无法移动到其他地方,核心内核分配的大部分页面都属于这一类。

    2.  可回收页面 reclaimable:不能直接移动,但是可以回收,因为还可以从某些源重建页面,比如映射文件的数据属于这种类别,kswapd会按照一定的规则,周期性的回收这类页面。

    3. 可移动页面 movable:可以随意的移动。属于用户空间应用程序的页属于此类页面,它们是通过页表映射的,因此我们只需要更新页表项,并把数据复制到新位置就可以了,当然要注意,一个页面可能被多个进程共享,对应着多个页表项。

    防止碎片的方法就是把这三类page放在不同的链表上,避免不同类型页面相互干扰。考虑这样的情形,一个不可移动的页面位于可移动页面中间,那么我们移动或者回收这些页面后,这个不可移动的页面阻碍着我们获得更大的连续物理空闲空间。

     

    另外,每个zone区都有一个自己的失活净页面队列,与此对应的是两个跨zone的全局队列,失活脏页队列 和 活跃队列。这些队列都是通过page结构的lru指针链入的。

    思考:失活队列的意义是什么(见<linux内核源代码情景分析>)?

    slab分配器:解决内部碎片问题

    内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。slab  缓存分配器通过对类似大小(远小于1page)的对象进行缓存而提供这种功能,从而避免了常见的内部碎片问题。此处暂贴一图,关于其原理,常见参考文献3。很显然,slab机制是基于buddy算法的,前者是对后者的细化。


    展开全文
  • 引进SLAB内存管理算法,BUDDY算法来说,如果要存放很少字节内容而分配一个页,会照成很大的浪费。内存管理引进了SLAB内存管理。
  • 本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。 伙伴系统 使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。 原理:系统中...
  • 文章目录1 slab分配器原理2 slab分配器重要数据结构以及组织关系2.1 slab cache描述符struct kmem_cache2.2 slab描述符struct page3.slab分配器中各个重要结构体间的关系总结 linux中的伙伴系统内存分配器是以页(4k...
  • Slab 算法

    千次阅读 2015-01-06 14:33:37
    Slab 作为一个历史悠久的算法,在 Linux 内核中是如何实现的呢,本文将简要说明它的原理。
  • Memcached slab 分配策略

    2015-11-20 17:42:44
    这篇文章,来看看 Memcached slab 内存分配算法是怎么做的。 一个内存分配算法要考虑算法的效率,管理内存所占的空间和内存碎片的问题。这个是三个衡量点往往不能个个都得到满足,每个实现都会各有所长。slab 能较...
  • Linux slab 分配器剖析

    2019-06-21 13:33:23
    Linux slab 分配器剖析 了解 Linux 内存管理的方式 动态内存管理 内存管理的目标是提供一种方法,为实现各种目的而在各个用户之间实现内存共享。内存管理方法应该实现以下两个功能: 最小化管理内存所需的时间 ...
  • Slab分配机制

    2013-05-15 20:22:48
    Slab分配机制  采用伙伴算法分配内存时,每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理?如何在一个页面中分配小的内存区,小内存区的分配所产生的内碎片又如何解决?  ...
  • Linux slab分配

    2015-05-26 21:37:00
    Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为 SunOS 操作系统首次引入的一种算法。Jeff 的分配器是围绕对象缓存进行的。在内核中,会为有限的对象集(例如文件描述符和其他常见结构)分配大量内存。Jeff ...
  • slab分配器最终还是由伙伴系统来分配出实际的物理页面,只不过slab分配器在这些连续的物理页面上实现了自己的算法,以此来对小内存块进行管理。关于slab分配器,我们需要思考如下几个问题。 slab分配器是如何分配...
  • 内存管理简介之Buddy算法slab分配

    千次阅读 2013-04-13 13:45:05
    1.Buddy算法 linux对空闲内存空间管理采取buddy算法,  Buddy算法: 把内存中所有页面按照2^n划分,其中n=0~5,每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成...
  • 详解slab机制(3) slab分配机制

    千次阅读 2013-08-21 09:34:29
    2.3、slab分配机制: 不论kmalloc还是kmem_cache_alloc,最终都是调用函数__cache_alloc,这是给调用者分配slab的总接口: static __always_inline void * __cache_alloc(struct kmem_cache *cachep, gfp_t flags...
  • 内存管理问题: 内存碎片大小和管理内存碎片的效率问题(即空间和时间效率的问题): 内存碎片是指当回收一块内存时,一般将内存直接放入free链表中,由于内存越分配越小,内存块就会特别多而且特别小,当...3.slab算法. ...
  • http://baike.baidu.com/link?url=oNua6Uugasd9L0IZ1fWiUIABErsN59uGoAIwtSXzBbCgJ6IGddtz9HFR5dekbga6z4ot1F7sBe_1psjb5Q3G5q
  • Linux内存管理之SLAB分配

    千次阅读 多人点赞 2018-08-06 15:07:49
    1、SLAB分配器的由来 在讲SLAB分配器之前先说两个概念: 内部碎片和外部碎片。 外部碎片指的是还没有被分配出去(不属于任何进程)但由于太小而无法分配给申请内存空间的新进程的内存空闲区域。外部碎片是除了任何...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,499
精华内容 3,799
关键字:

slab分配算法