堆栈的存储机制学习

这两天继续学习了皓子之前的文章，伙伴分配器的一个简单实现很有意思 http://coolshell.cn/articles/10427.html ，加上之前看了一些关于堆存储的知识，赶紧总结一下加固一下记忆。

首先说一下堆的内存申请和释放，在c中大多在系统的应用程序中会使用malloc和free来申请和释放内存，由于malloc和free讲究快速实现申请和释放，因此这两个操作不会去进行多余的检测。在一个应用程序启动后，系统会给它分配一块内存，分别存储着代码段、栈内存、堆内存、静态存储区等。我们假想堆内存是一条线性的很长的内存条，当执行malloc(size)时，malloc会在这条线性区域中寻找满足size大小的连续内存区域然后返回首地址给对应的指针变量。free则会寻找指针变量所指的地址区域，将指定的内存区域设置为空闲状态。
这里就有一个问题，如何在malloc中设置申请的内存大小，如何在free时确定需要将地址之后多大的内存区域还给空闲的内存。这里先需要说明，内存的空闲段有一种情况下是存储在一个链表中，即将还没分配出去的内存信息存储在一个链表中，每次malloc时在这个链表中寻找最佳的可以的内存区域分配，而free时则将一块内存还给这个链表。
终于要讲malloc和free终究在怎么做了，malloc时根据编译器的不同会在申请时多申请4个Byte或者更多的Byte来存储这段申请的内存信息。
例如，int * array = (int*) malloc(40 * sizeof(int));
从代码上看32位Linux系统中编译器分配了40*4=160（Byte）的内存空间，并将首地址返回给array指针变量。实际上在array地址之前，仍然有4个Byte的空间去记录160+4=164（Byte）的信息，表示这次分配总共占用了164个Byte，当然可能还会多余存储其他信息，这个我也没有去验证过。而在free时，这个信息就能够有效地帮助编译器去获取这次free需要去释放多少个字节的资源。
free(array);
free会对在array之前的的4个Byte去分析，知道这个指针对应的内存对应了164个Byte，然后将这么多内存释放，还给之前讲的空闲链表。所以如果我们调用了array[-1]来修改了array之前的信息可能造成在free时的信息错误。
另外，在malloc之后，每个指针会记录自己对应的内存地址。而这时可能有一个问题，在不断地申请和释放之后内存中会有很多的碎片，生成不连续的内存，使本身富余的内存资源在申请时找不到合适的连续内存获取。这时候就需要进行内存压缩，将这些变量对应的内存移位压缩到一起。但变量却记录着原本对应的地址。在这里就有一种方法，二级指针，通过在变量和内存之间添加多一层一级指针，变量对应的只是一级指针的地址，而这个是不变的，一级指针会根据压缩后的地址来变化其值，这些都是编译器内部的变化，不会对用户态造成什么影响。只是在用户态使用时可能需要使用Lock和Unlock来锁定变量，在操作时不允许进行优化压缩。（在移动内存内容时，如果两块内存可能出现重叠部分则需要使用memmove而不是memcopy）
面对这种内存碎片有很多的解决方法，在malloc申请时也有各种优化算法（最小最优、最大最优、最先的最优）。现在有一种比较合理的方法是伙伴分配器。
伙伴分配器是在内存分配时只分配2的指数大小，避免出现太多碎片，当内存被释放时检查是否可以将两块内存合并为更大的空闲内存块。整个内存可以用一个完全二叉树来管理。以下为一个简单的伙伴管理系统的实现

偷图一张：

在这里通过完全二叉树管理了16个单位的内存，通过完全二叉树来记录内存使用情况。深度每加1，节点对应的内存大小就减半。每个节点保存着对应的内存段中最大的可连续存储空间大小。每次申请内存时都会从根节点开始遍历，如果左孩子的对应值满足申请内存的大小则继续从左孩子向下寻找，否则从右孩子向下寻找。依次循环直到找到一个节点的对应值等于所需申请的内存大小（这个值是需要提前归一化为2的幂次方的）。当对应的某一个节点下的内存被申请出去后，节点的对应值变为0，然后依次对它的父节点作计算，更新他们对应的可用节点内存大小。当对应的内存被释放后，节点的对应值重修修改回来，父节点也被再次更新。

整个伙伴分配器的管理结构体为：

struct buddy {
    unsigned size;
    unsigned longest[1];
}

这里面的longest变量同之前学习的零长度数组一个道理，可以在申请内存时根据size大小扩容。size是指整个系统管理的内存大小，longest[i]是对应的每一个节点的最长可分配内存大小。

再放上作者两个辅助函数，对于我这种菜鸟还是很受用的,分别时判断x是否为2的幂和将size向上取2的幂

#define IS_POWER_OF_2(x) (!( x & (x-1)))

static unsigned fixsize(unsigned size) {
    size |= size >>1;
    size |= size >>2;
    size |= size >>4;
    size |= size >>8;
    size |= size >>16;
    return size+1;
}

伙伴管理系统的初始化：

struct buddy* buddy_new(int size) {
    unsigned node_size;
    struct buddy * self;
    int i;

    if(size < 1 || !IS_POWER_OF_2(size)) {
        return NULL;
    }
    self = (struct buddy*)malloc(size * sizeof(unsigned));
    self->size = size;
    node_size = size * 2;
    for(i = 0; i < size * 2 - 1; i++) {
        if(IS_POWER_OF_2(i+1)) {
            node_size /= 2;
        }
        longest[i] = node_size;
    }
    return self;
}

初始化size大小的系统，且对每一个节点进行赋值，给出对应的最长内存长度。

系统的注销：

void buddy_destroy(struct * buddy self) {
    free(self);
}

系统分配内存：

int buddy_alloc(struct buddy * self, int size) {
    unsigned index = 0;
    unsigned node_size;
    unsigned offset = 0;
    if(self == NULL || size < 1) {
        return -1;
    }
    if(!IS_POWER_OF_2(size)) {
        size = fixsize(size);
    }
    if(size > self->longest[index]) {
        return -1;
    }
    node_size = self->size;
    while(size != self->longest[index]) {
        if(self->longest[LEFT_LEAF(index)] > size) {
            index = LEFT_LEAF(index);
        }
        else {
            index = RIGHT_LEAF(index);
        }
        node_size /= 2;
    }
    self->longest[index] = 0;
    offset = (index + 1)* node_size - self->size;

    while(index) {
        index = PARENT(index);
        self->longest[index] = 
            MAX(self->longest[LEFT_LEAF(index)], self->longest[RIGHT_LEAF(index)]);
    }
    return offset;
}

找到最小的内存快进行分配后，然后循环更新父节点的值

系统回收内存：

void buddy_free(struct buddy * self, int offset) {
    unsigned node_size, index = 0;
    unsigned left_longest, right_longest;
    assert(self && offset >= 0 && offset < self->size);

    node_size = 1;
    index = offset + self->size -1;

    while(self->longest[index]) {
        node_size  = node_size<<1;
        if(index == 0) {
            return;
        }
        index = PARENT(index);
    }
    self->longest[index] = node_size;

    while(index) {
        index = PARENT(index);
        node_size = node_size<<1;
        left_longest = self->longest[LEFT_LEAF(index)];
        right_longest = self->longest[RIGHT_LEAF(index)];
        if(left_longest + right_longest == node_size) {
            self->longest[index] = node_size;
        }
        else {
            self->longest[index] = MAX(left_longest, right_longest);
        }
    }
}

通过位移计算出对应节点和内存大小值，恢复，循环更新父节点

看完这个之后对我的帮助，本身对伙伴内存管理没什么概念，看完这个也大致的得到了解。目前还在看栈空间内的内存分配，还没看完，看完之后也更新到这篇文章里，继续加油！