musl 1.1.24 源码分析

2022-04-24

musl libc是一种轻量级的C标准动态链接库,用来替代日益臃肿的glibc

之所以要分析它的源码,是因为它出现在了题目当中….

它诞生是为了取代日益臃肿的glibc,主要用在轻量级的系统当中

musl源码可以在官网中下载,我把我的理解都写在注释里了,便于分析

/src/malloc/malloc.c 是源代码位置

一些结构信息在 /src/internal/malloc_impl.h中

malloc源码分析

void *malloc(size_t n)
{
    struct chunk *c;
    int i, j;

    if (adjust_size(&n) < 0) return 0; //大小比较合适,就会对齐,进入下一步,不合适直接寄,

    if (n > MMAP_THRESHOLD) {//0x1c00*0x20 = 0x38000 用mmap分配内存
        size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
        char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
            MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
        if (base == (void *)-1) return 0;  //结果为-1 分配失败
        c = (void *)(base + SIZE_ALIGN - OVERHEAD);
        c->csize = len - (SIZE_ALIGN - OVERHEAD);//对于mmap分配的 csize和psize inuse位均为0
        c->psize = SIZE_ALIGN - OVERHEAD;
        return CHUNK_TO_MEM(c);//返回mem地址
    }

    i = bin_index_up(n);//告诉你这个地址的n应该位于哪个bin中
    for (;;) {
        uint64_t mask = mal.binmap & -(1ULL<<i);//看看这个bin以上的其他bin是否全为空
        if (!mask) {//若这个bin以上的其他bin是否全为空 均为空,调用 expand_heap 函数延展堆空间,生成新的 chunk
            c = expand_heap(n);
            if (!c) return 0; //拓展失败
            if (alloc_rev(c)) { //如果上一个chunk空闲,会触发unbin操作进行脱链
                struct chunk *x = c; //合并操作
                c = PREV_CHUNK(c);
                NEXT_CHUNK(x)->psize = c->csize =
                    x->csize + CHUNK_SIZE(c);
            }
            break; 
        }
        j = first_set(mask);//获取最接近n的可用bin下标j
        lock_bin(j);
        c = mal.bins[j].head;
        if (c != BIN_TO_CHUNK(j)) { //不等于才是正常的(
            if (!pretrim(c, n, i, j)) unbin(c, j); //预裁剪失败,把c从bins[j]的链中脱离
            unlock_bin(j);
            break;
        }
        unlock_bin(j);
    }

    /* Now patch up in case we over-allocated */
    trim(c, n);//把裁剪后的chunk放入bin中

    return CHUNK_TO_MEM(c);
}

free源码分析

void free(void *p)
{
    if (!p) return;//基本检查,p是0什么都不做

    struct chunk *self = MEM_TO_CHUNK(p);

    if (IS_MMAPPED(self))//如果是mmap分配出来的 值得一提的是csize的inuse位为1,表示是正在被使用,如果为0,要么被释放,要么是mmap分配来的,这时候根据psize的inuse位判断它是否正在被使用
        unmap_chunk(self);
    else
        __bin_chunk(self);
}

adjust_size

比较简单,说白了就是裁剪n使得它是关于0x20对齐的

static int adjust_size(size_t *n)
{
    /* Result of pointer difference must fit in ptrdiff_t. */
    if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
        if (*n) {
            errno = ENOMEM; //申请的数量太大了,直接寄
            return -1;
        } else {					//如果是0 0-1无符号是最大值
            *n = SIZE_ALIGN;
            return 0;
        }
    }
    *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
    return 0;
}

expand_heap分析

static struct chunk *expand_heap(size_t n)
{
    static int heap_lock[2];
    static void *end;
    void *p;
    struct chunk *w;

    /* The argument n already accounts for the caller's chunk
    * overhead needs, but if the heap can't be extended in-place,
    * we need room for an extra zero-sized sentinel chunk. */
    n += SIZE_ALIGN;

    lock(heap_lock);

    p = __expand_heap(&n);
    if (!p) {
        unlock(heap_lock);//扩展失败
        return 0;
    }

    /* If not just expanding existing space, we need to make a
    * new sentinel chunk below the allocated space. */
    if (p != end) {
        /* Valid/safe because of the prologue increment. */
        n -= SIZE_ALIGN;  //之前加了size_ALIGN 现在要减掉(
        p = (char *)p + SIZE_ALIGN; //进行一个隔离
        w = MEM_TO_CHUNK(p);
        w->psize = 0 | C_INUSE;
    }

    /* Record new heap end and fill in footer. */
    end = (char *)p + n;
    w = MEM_TO_CHUNK(end);
    w->psize = n | C_INUSE;
    w->csize = 0 | C_INUSE;

    /* Fill in header, which may be new or may be replacing a
    * zero-size sentinel header at the old end-of-heap. */
    w = MEM_TO_CHUNK(p);
    w->csize = n | C_INUSE;

    unlock(heap_lock);

    return w;
}

pretrim源码分析

pretrim主要针对的是裁剪后剩下的chunk仍然在 j当中时的情景,这样进入trim可以直接返回,不用调用__bin_chunk函数。

static int pretrim(struct chunk *self, size_t n, int i, int j)
{
    size_t n1;
    struct chunk *next, *split;

    /* We cannot pretrim if it would require re-binning. */
    if (j < 40) return 0;//一般来说要满足以下条件,对chunk进行切割的时候,能保证切割后的chunk仍然在该bin中,就比较方便
    if (j < i+3) {
        if (j != 63) return 0;
        n1 = CHUNK_SIZE(self);
        if (n1-n <= MMAP_THRESHOLD) return 0;
    } else {
        n1 = CHUNK_SIZE(self);
    }
    if (bin_index(n1-n) != j) return 0;

    next = NEXT_CHUNK(self);
    split = (void *)((char *)self + n); 

    split->prev = self->prev;
    split->next = self->next;
    split->prev->next = split;
    split->next->prev = split;
    split->psize = n | C_INUSE;
    split->csize = n1-n;
    next->psize = n1-n;
    self->csize = n | C_INUSE;
    return 1;
}

trim源码分析

正常的回收多余部分的工作

static void trim(struct chunk *self, size_t n)
{
    size_t n1 = CHUNK_SIZE(self);
    struct chunk *next, *split;

    if (n >= n1 - DONTCARE) return;

    next = NEXT_CHUNK(self);
    split = (void *)((char *)self + n);

    split->psize = n | C_INUSE;
    split->csize = n1-n | C_INUSE;
    next->psize = n1-n | C_INUSE;
    self->csize = n | C_INUSE;

    __bin_chunk(split);//回收split
}

unmap_chunk分析

static void unmap_chunk(struct chunk *self)
{
    size_t extra = self->psize;
    char *base = (char *)self - extra;
    size_t len = CHUNK_SIZE(self) + extra;
    /* Crash on double free */
    if (extra & 1) a_crash();//如果psize的inuse位为0,表明它是mmap分配的,可以释放,如果psize位是1,表示它是已经被释放的,double free
    __munmap(base, len);
}

__bin_chunk分析

void __bin_chunk(struct chunk *self)
{
    struct chunk *next = NEXT_CHUNK(self);
    size_t final_size, new_size, size;
    int reclaim=0;
    int i;

    final_size = new_size = CHUNK_SIZE(self);

    /* Crash on corrupted footer (likely from buffer overflow) */
    if (next->psize != self->csize) a_crash();

    for (;;) {
        if (self->psize & next->csize & C_INUSE) {//下一个块正在使用中(
            self->csize = final_size | C_INUSE;
            next->psize = final_size | C_INUSE;
            i = bin_index(final_size);
            lock_bin(i);
            lock(mal.free_lock);
            if (self->psize & next->csize & C_INUSE)
                break;
            unlock(mal.free_lock);
            unlock_bin(i);
        }

        if (alloc_rev(self)) {//如果上一个chunk空闲,会触发unbin操作进行脱链
            self = PREV_CHUNK(self);
            size = CHUNK_SIZE(self);
            final_size += size;
            if (new_size+size > RECLAIM && (new_size+size^size) > size)
                reclaim = 1;
        }

        if (alloc_fwd(next)) {//如果下一个chunk空闲,会触发unbin操作进行脱链
            size = CHUNK_SIZE(next);
            final_size += size;
            if (new_size+size > RECLAIM && (new_size+size^size) > size)
                reclaim = 1;
            next = NEXT_CHUNK(next);
        }
    }
    //binmap 中,将 bin i 设为非空 bin
    if (!(mal.binmap & 1ULL<<i))
        a_or_64(&mal.binmap, 1ULL<<i);

    //清空inuse 位
    self->csize = final_size;
    next->psize = final_size;
    unlock(mal.free_lock);
    //加入链的尾部
    self->next = BIN_TO_CHUNK(i);
    self->prev = mal.bins[i].tail;
    self->next->prev = self;
    self->prev->next = self;

    /* Replace middle of large chunks with fresh zero pages */
    if (reclaim) {
        uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
        uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
#if 1
        __madvise((void *)a, b-a, MADV_DONTNEED);
#else
        __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
            MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
#endif
    }

    unlock_bin(i);
}

参考

https://www.anquanke.com/post/id/202253#h3-8