Linux点点滴滴

Author Avatar
Magicmanoooo 3月 09, 2019
  • 在其它设备中阅读本文章

Linux内存管理

1. 虚拟内存地址与物理内存地址

为了简单，现代操作系统在处理内存地址时，普遍采用虚拟内存地址技术。即在汇编程序（或机器语言）层面，当涉及内存地址时，都是使用虚拟内存地址。采用这种技术时，每个进程仿佛自己独享一片2^N字节的内存，其中N是机器位数。

这种虚拟地址空间的作用主要是：简化程序的编写及方便操作系统对进程间内存的隔离管理，真实中的进程不太可能需要（也用不到）如此大的内存空间，实际能用到的内存取决于物理内存大小。

由于在机器语言层面都是采用虚拟地址，当实际的机器码程序涉及到内存操作时，需要根据当前进程运行的实际上下文将虚拟地址转换为物理内存地址，才能实现对真实内存数据的操作。这个转换一般由一个叫MMU（Memory Management Unit）的硬件完成。

2. 页与地址构成

在现代操作系统中，不论是虚拟内存还是物理内存，都不是以字节为单位进行管理的，而是以页（Page）为单位。一个内存页是一段固定大小的连续内存地址的总称，具体到Linux中，典型的内存页大小为4096 Byte（4K）。

所以内存地址可以分为页号和页内偏移量。下面以64位机器，4G物理内存，4K页大小为例，虚拟内存地址和物理内存地址的组成如下：


上面是虚拟内存地址，下面是物理内存地址。由于页大小都是4K，所以页内便宜都是用低12位表示，而剩下的高地址表示页号。

MMU映射单位并不是字节，而是页，这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂，为了加快速度会引入一系列缓存和优化，例如TLB等机制。例如，经过简化的内存地址翻译示意图：

内存页与磁盘页

一般将内存看做磁盘的的缓存，有时MMU在工作时，会发现页表表明某个内存页不在物理内存中，此时会触发一个缺页异常（Page Fault），此时系统会到磁盘中相应的地方将磁盘页载入到内存中，然后重新执行由于缺页而失败的机器指令。

Linux进程级内存管理

1. 内存排布

Linux 64位操作系统仅使用低47位，高17位做扩展（只能是全0或全1）。所以，实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF，其中前面为用户空间（User Space），后者为内核空间（Kernel Space）。图示如下：

【注】：Linux virtual memory map
对用户来说，主要关注的空间是User Space，其主要分为如下几段：

  • Code：这是整个用户空间的最低地址部分，存放的是指令（也就是程序所编译成的可执行机器码）
  • Data：存放初始化过的全局变量
  • BSS：存放未初始化的全局变量
  • Heap：堆从低地址向高地址增长，brk相关的系统调用就是从这里分配内存
  • Mapping Area：与mmap系统调用相关的区域（大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域。此区域自高地址向低地址增长）
  • Stack：栈区域，从高地址向低地址增长

2. Heap内存模型

一般来说，malloc所申请的内存主要从Heap区域分配（本文不考虑通过mmap申请大块内存的情况）。

进程所面对的虚拟内存地址空间，只有按页映射到物理内存地址，才能真正使用。受物理存储容量限制，整个堆虚拟内存空间不可能全部映射到实际的物理内存。Linux对堆的管理示意如下：

Linux维护一个break指针，这个指针指向堆空间的某个地址

  • 从堆起始地址到break之间的地址空间为映射好的，可以供进程访问。
  • 而从break往上，是未映射的地址空间，如果访问这段空间则程序会报错。

brk与sbrk

要增加一个进程实际的可用堆大小，就需要将break指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下：

int brk(void *addr);
void *sbrk(intptr_t increment);
  • brk将break指针直接设置为某个地址。brk在执行成功时返回0，否则返回-1并设置errno为ENOMEM。
  • sbrk将break从当前位置移动increment所指定的增量。sbrk成功时，返回break移动之前所指向的地址，否则返回(void *)-1。

【注】：如果将increment设置为0，则可以获得当前break的地址。

此外，由于Linux是按页进行内存映射的，所以如果break被设置为没有按页大小对齐，则系统实际上会在最后映射一个完整的页，从而实际已映射的内存空间比break指向的地方要大一些。但是使用break之后的地址是很危险的（尽管也许break之后确实有一小块可用内存地址）。

4. 资源限制与rlimit

系统对每一个进程所分配的资源不是无限的，包括可映射的内存空间，因此每个进程有一个rlimit表示当前进程可用的资源上限。这个限制可以通过getrlimit系统调用得到。

获取当前进程虚拟内存空间的rlimit：

int main() {
    struct rlimit *limit = (struct rlimit *)malloc(sizeof(struct rlimit));
    getrlimit(RLIMIT_AS, limit);
    printf("soft limit: %ld, hard limit: %ld\n", limit->rlim_cur, limit->rlim_max);
}

其中，rlimit是一个结构体：

struct rlimit {
    rlim_t rlim_cur;  /* Soft limit */
    rlim_t rlim_max;  /* Hard limit (ceiling for rlim_cur) */
};

每种资源有软限制和硬限制，并且可以通过setrlimit对rlimit进行有条件设置。其中，硬限制作为软限制的上限，非特权进程只能设置软限制，且不能超过硬限制。

实现malloc

1. 采用的数据结构

首先需要确定所采用的数据结构。一个简单可行的方案是：将堆内空间以块（block）的形式组织起来，每个块由meta区和数据区组成。其中，meta区记录数据块的meta information（元信息，数据区的大小、空闲标志位、指针等），数据区是真实分配的内存区域，并且数据区的第一个字节地址即为malloc返回的地址。

定义一个结构体block：

typedef struct s_block *t_block;
struct s_block {
    size_t size;  /* 数据区大小 */
    t_block next; /* 指向下个块的指针 */
    bool is_free;     /* 是否是空闲块 */
    int padding;  /* 填充4字节，保证meta块长度为8的倍数 */
    char data[1]  /* 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};

由于我们只考虑64位机器，为了方便，我们在结构体最后填充一个int，使得结构体本身的长度为8的倍数，以便内存对齐。示意图如下：

2. 寻找合适的block

在block链中查找合适的block，一般有两种查找算法：

  • first fit：从头开始，查找第一个数据区大小大于或者等于要求size的块，作为此次分配的块。
  • best fit：从头开始，遍历所有块，查找数据区大小大于size且差值最小的块，作为此次分配的块。

best fit具有较高的内存使用率（payload较高），而first fit具有更好的运行效率。此处，采用first fit算法：

/* First fit */
t_block find_block(t_block *cur, size_t size) {
    t_block b = first_block;
    while(b && !(b->is_free && b->size >= size)) {
        *cur = b;
        b = b->next;
    }
    return b;
}

find_block()从frist_block开始，查找第一个符合要求的block，并返回block起始地址。如果找不到，便返回NULL。在遍历时会更新一个叫cur的指针，这个指针始终指向当前遍历的block。cur的作用是：如果找不到合适的block，便需要重新开辟新的block，这时便会用到它。

3. 开辟新的block

如果现有的block都不能满足size的要求，则需要在链表的最后开辟一个新的block。关键是：如何只使用sbrk创建一个struct：

#define BLOCK_SIZE 24 /* 由于存在虚拟的data字段，sizeof不能正确计算meta长度，这里手工设置 */

t_block extend_heap(t_block cur, size_t s) {
    t_block b;
    b = sbrk(0);
    if(sbrk(BLOCK_SIZE + s) == (void *)-1)    // 如果从heap上分配内存失败，则直接返回NULL
        return NULL;
    b->size = s;
    b->next = NULL;
    if(cur)      // 在当前指定的block后插入刚分配的block
        cur->next = b;
    b->free = 0;
    return b;
}

分裂block

First fit有一个比较致命的缺点：可能会让很小的size占据很大的一块block。此时，为了提高payload，应该在剩余数据区足够大的情况下，将其分裂为一个新的block。

示意图如下：

实现为：

void split_block(t_block b, size_t s) {
    t_block new_block;
    new_block = b->data + s;
    new_block->size = b->size - s - BLOCK_SIZE ;
    new_block->next = b->next;
    new_block->free = 1;
    b->size = s;
    b->next = new_block;
}

malloc的实现

由于希望malloc分配的数据区是按8字节进行对齐，所以当size不为8的倍数时，需要将size调整为大于size的最小的8的倍数。

size_t align(size_t s) {
    if(s & 0x7 == 0)
        return s;
    return ((s >> 3) + 1) << 3;
    // return ((s + 7) & -8);    ((size_t)s + n-1) & -n);
}

malloc 的具体实现：

#define BLOCK_SIZE 24
void *first_block=NULL;

/* other functions... */

void *malloc(size_t size) {
    t_block b, last;
    size_t s;
    /* 对齐地址 */
    s = align(size);
    if(first_block) {
        /* 查找合适的block */
        last = first_block;
        b = find_block(&last, s);
        if(b) {
            /* 如果可以，则分裂 */
            if ((b->size - s) >= ( BLOCK_SIZE + 8))
                split_block(b, s);
            b->free = 0;
        } else {
            /* 没有合适的block，开辟一个新的 */
            b = extend_heap(last, s);
            if(!b)
                return NULL;
        }
    } else {
        b = extend_heap(NULL, s);
        if(!b)
            return NULL;
        first_block = b;
    }
    return b->data;
}

calloc的实现

在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULL。

实现calloc的步骤：

  1. malloc一段内存
  2. 将数据区内容设置为0

由于数据区是按8字节对齐的，所以为了提高效率，可以每8字节一组置0，而不是一个一个字节设置。可以通过新建一个size_t指针，将内存区域强制看做size_t类型来实现。

void *calloc(size_t n, size_t size) {
    size_t *new_block;
    size_t s, i;
    new_block = malloc(n * size);
    if(new_block) {
        s = align(n * size) >> 3;
        for(i = 0; i < s; i++)
            new_block[i] = 0;
    }
    return new_block;
}

free的实现

free的实现需要解决两个关键问题：

  1. 如何验证所传入的地址是有效地址，即确实是通过malloc方式分配的数据区首地址
  2. 如何解决碎片问题

首先要保证传入free的地址是有效的，这个有效包括两方面：

  1. 地址应该在malloc所分配的区域内，即在first_block和当前break指针范围内
  2. 这个地址是由之前自己实现的malloc分配

第一个问题比较好解决，只需要进行地址比较便可，关键是第二个问题。有两种解决方案：

  1. 在结构体内设置一个magic number字段，free之前通过相对偏移，检查特定位置的值是否为设置的magic number
  2. 在结构体内增加一个magic pointer，此指针指向数据区的第一个字节（也就是在合法时free时传入的地址），在free前检查magic pointer是否指向参数所指地址。

此处采用第二种方案。首先，在结构体中增加magic pointer（同时需要修改BLOCK_SIZE）：

typedef struct s_block *t_block;
struct s_block {
    size_t size;  /* 数据区大小 */
    t_block next; /* 指向下个块的指针 */
    int free;     /* 是否是空闲块 */
    int padding;  /* 填充4字节，保证meta块长度为8的倍数 */
    void *ptr;    /* Magic pointer，指向data */
    char data[1]  /* 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};

然后，定义检查地址合法性的函数：

t_block get_block(void *p) {
    char *tmp;  
    tmp = p;
    return (p = tmp -= BLOCK_SIZE);
}

int valid_addr(void *p) {
    if(first_block) {
        if(p > first_block && p < sbrk(0)) {
            return p == (get_block(p))->ptr;
        }
    }
    return 0;
}

当多次malloc和free后，整个内存池可能会产生很多碎片block，这些block很小，经常无法使用，甚至出现许多碎片连在一起，虽然总体能满足某些malloc要求，但是由于分割成了多个小block而无法fit，这就是碎片问题。

一个简单的解决方式是：当free某个block时，如果发现它相邻的block也是free的，则将此block和相邻block进行合并。为了满足这个实现，则需要将s_block改为双向链表。修改后的block结构如下：

typedef struct s_block *t_block;
struct s_block {
    size_t size;  /* 数据区大小 */
    t_block prev; /* 指向上个块的指针 */
    t_block next; /* 指向下个块的指针 */
    int free;     /* 是否是空闲块 */
    int padding;  /* 填充4字节，保证meta块长度为8的倍数 */
    void *ptr;    /* Magic pointer，指向data */
    char data[1]  /* 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};

合并方法为：

t_block fusion(t_block b) {
    if (b->next && b->next->free) {
        b->size += BLOCK_SIZE + b->next->size;
        b->next = b->next->next;
        if(b->next)
            b->next->prev = b;
    }
    return b;
}

有了上述方法，free的实现思路就比较清晰了：首先检查参数地址的合法性，如果不合法，则不做任何事；否则，将此block的free设置为1，并且在可以的情况下与后面的block进行合并。如果当前是最后一个block，则回退break指针释放进程内存，如果当前block是最后一个block，则回退break指针并设置first_block为NULL。实现如下：

Powered by Hexo
Theme - Material