malloc/free的原理与实现 Chunk C标准库在管理分配出去的heap时的基本单位是chunk,chunk只是一个逻辑概念,它的数据结构如下: struct malloc_chunk { size_t prev_size; /* Size of previous chunk (if free). */ size_t size; /* Size in bytes, including overhead. */ struct malloc_chunk* fd; /* double links — used only if free. */ struct malloc_chunk* bk; /* Only used for large blocks: pointer to next larger size. */ struct malloc_chunk* fd_nextsize; /* double links — used only if free. */ struct malloc_chunk* bk_nextsize; }; 如果一个chunk是free的状态,那么它的fd和bk就构成一个双链表,记录着那些已经被用户free了内存,这样以后就可以从这里直接分配或者合并成为大的空闲块以后再分配。如果一个chunk已经被alloc了,那么此时从size之后就是用户的数据,也就是说fd、bk等没有意义,这个从注释中不难看出。 当一个chunk被分配出去时,size记录了这个chunk中实际分配给用户程序的内存大小,也就是我们调用malloc时的那个参数值,而prev_size记录的是与当前chunk相邻的上一个chunk的大小。这样设计的原因是可以快速地定位/合并相邻的chunk。例如,如果当前chunk地址为char *p,那么上/下一个chunk的地址分别就是p-p->prev_size和p+p->size。简单分析下下面这两个宏就一目了然了: (1)从chunk得到用户指针(这里SIZE_SZ即sizeof(size_t)) #define chunk2mem(p) ((void_t*)((char*)(p) + 2*SIZE_SZ)) (2)从用户指针得到chunk地址 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) – 2*SIZE_SZ)) 在分配内存时,chunk的对其单位是8Byte,这样size的低3位就都是0,那么就可以作为其他用途。在glibc中有两个定义: #define PREV_INUSE 0x1 #define IS_MMAPPED 0x2 这里PREV_INUSE记录了上一个chunk是否被使用(如果被分配则为1),而IS_MMAPPED标识当前chunk是否是通过mmap分配得到。下面这些宏可以加深我们对chunk的理解: //当前chunk(p)的下一个chunk #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) )) //当前chunk(p)的上一个chunk #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) – ((p)->prev_size) )) //判断当前chunk(p)是否被使用,注意:p的inuse位信息保存在下一个相邻chunk的size中 #define inuse(p) ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE) //将当前chunk(p)设置为被使用,也即设置下一个相邻chunk中size的最低位为1 #define set_inuse(p) ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE malloc数据结构 这个数据结构记录了系统当前分配内存的状态,默认情况下,当分配内存小于64B时通过fastbin分配,它是一个caching allocator,也就是说一种memory pool。当分配内存大于512B时,系统按照best-fit算法分配,也就是可以满足需求的最小size的chunk。介于二者之间的情况比较复杂。 struct malloc_state { /* Serialize access. */ mutex_t mutex; /* Flags (formerly in max_fast). */ int flags; /* Fastbins */ mchunkptr fastbins[NFASTBINS]; /* Base of the topmost chunk — not otherwise kept in a bin */ mchunkptr top; /* The remainder from the most recent split of a small request */ mchunkptr last_remainder; /* Normal bins packed as described above */ mchunkptr bins[NBINS * 2 – 2]; /* Bitmap of bins */ unsigned int binmap[BINMAPSIZE]; /* Linked list */ struct malloc_state *next; /* Memory allocated from the system in this arena. */ INTERNAL_SIZE_T system_mem; INTERNAL_SIZE_T max_system_mem; }; malloc实现(void *malloc(size_t size)) 该调用在内部实现为_int_malloc(mstate av, size_t bytes)。主要步骤如下: 1、确定内部分配内存大小,它是用宏request2size计算得到。: #define request2size(req) (((req) + SIZE_SZ + MALLOC_ALIGN_MASK fastbins[idx]); if ( (victim = *fb) != 0) { if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0)) malloc_printerr (check_action, “malloc(): memory corruption (fast)”, chunk2mem (victim)); *fb = victim->fd; check_remalloced_chunk(av, victim, nb); void *p = chunk2mem(victim); if (__builtin_expect (perturb_byte, 0)) alloc_perturb (p, bytes); return p; } } fastbin_index(nb): 这是一个宏,定义为#define fastbin_index(sz) ((((unsigned int)(sz)) >> 3) – 2)。观察malloc_state数据结构,它有一个fastbin的指针数组,每个数组成员分配是一个单链表的表头,可见fastbin[i]专门用于分配大小为16+8i的内存块。 *fb = victim->fd: 当执行到这一行时,fastbin[idx]肯定不为空,也就是说当前内存分配可以直接从fastbin中满足,那么下面自然是从单链表中取下victim这个chunk,而这行赋值语句正是完成这个任务。这里相当于fastbin[idx]这个指针指向了victim这个chunk的后继(victim->fd),也就是说将victim从链表中移除。 void *p = chunk2mem(victim) 前文中已经分析过这个宏了,它返回的是chunk内用户内存的首地址。 3、如果分配内存大于64B,但是小于512B,那么仍属于小块内存请求,从smallbin中分配 if (in_smallbin_range(nb)) { idx = smallbin_index(nb); bin = bin_at(av,idx); if ( (victim = last(bin)) != bin) { if (victim == 0) /* initialization check */ malloc_consolidate(av); else { bck = victim->bk; set_inuse_bit_at_offset(victim, nb); bin->bk = bck; bck->fd = bin; if (av != &main_arena) victim->size |= NON_MAIN_ARENA; check_malloced_chunk(av, victim, nb); void *p = chunk2mem(victim); if (__builtin_expect (perturb_byte, 0)) alloc_perturb (p, bytes); return p; } } } smallbin_index(nb): 它也是一个宏,它定义等价于 #define smallbin_index(sz) (((unsigned)(sz)) >> 3))。这里因为系统将512B大小以下的闲置内存块都组织为双链表
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/82603.html