1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#define NALLOC 1024    /* minimum #units to request */


typedef long Align;    /* for alignment to long boundarg. 假定 long 类型为最受限的类型。*/


/* 空闲块包含的内容：
 *    一个指向链表中下一个块的指针 
 *    一个块大小的记录 
 *    一个指向空闲空间本身的指针
 */

/* 该联合中, Align 字段永远也不会被使用，仅仅用于强制每个头部在最坏的情况下满足对其要求 */
union header {    /* block header: 位于块开始处的控制信息，成为「头部」.
                     所有块的大小必须是头部大小的整数倍，且头部已正确地对齐。*/
    struct {
        union header *ptr;    /* next block if on free list */
        unsigned size;    /* size of this block 记录实际分配的块大小*/
    } s;
    Align x;    /* force alignment of blocks */
};

typedef union header Header;


static Header base;    /* empty list to get started */
static Header *freep = NULL;    /* start of free list */


/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *moreroce(unsigned);
    unsigned nunits;

    nunits = (nbytes+sizeof(header)-1)/sizeof(header) + 1;
    if ((prevp = freep) == NULL) {    /* no free list yet */
        base.s.ptr = freeptr = prevptr = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size == nunits) {    /* big enough */
            if (p->s.size >= nunits)    /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {    /* allocate tail end */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)    /* wrapped around free list */
            if ((p = morecore(nunits)) == NULL )    /* morecore 用于向操作系统请求存储空间。
                                                     * 我们不希望每次调用 malloc 函数时执行该操作，
                                                     * 所有 morecore 函数请求至少 NALLOC 个单元， 
                                                     * 这个较大的块将根据需求分解成较小的块。 */
                return NULL;    /* none left */
    }
}



/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;
    
    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)    /* no space at all */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    free((void *)(up+1));
    return freep;
}


/* free: put block ap in free list */
void free(void *ap)
{
    Header *bp, *p;

    bp = (Header *)ap - 1;    /* point to block header */
    for (p = freep; !(bp > && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;    /* fread block at start or end of arena */

    if (bp + bp->size == p->s.ptr) {    /* join to upper nbr */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p + p->size == bp) {    /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}