背景：

前几天去面试，被问到了一个问题：“malloc的底层实现是怎样的？怎样防止内存碎片？” 当时答的不够好，现在再整理一下。

（本文档通过收集整理网上博客而来。先挖个坑，等有时间了去看一下《深入理解操作系统》的第九章虚拟内存，再重新整理一篇）

内存布局

Linux中每个进程都有自己的虚拟地址空间，通常会划分为几个区域。如下：

+--------------------------------------------------+
|           命令行参数和环境变量                      |
+--------------------------------------------------+
|           栈   局部变量，参数等。后进先出             |  (从高地址向低地址增长)
+--------------------------------------------------+
|           堆   动态内存分配 malloc calloc分配出来的  |  (从低地址向高地址增长)
+--------------------------------------------------+
|       BSS 段   未初始化的全局变量和静态变量           |
+--------------------------------------------------+
|   初始化数据段   已初始化的全局变量和静态变量           |
+--------------------------------------------------+
|       文本段    代码段，包含程序机器指令，只读         |
+--------------------------------------------------+

补充一点：

栈：速度快，不用程序员释放，空间小，容易栈溢出，有的系统只有8M。

堆：速度慢一点，空间大，要自己释放，管理起来难度大，容易内存泄漏。new 和 malloc都是操作的堆区。

malloc底层实现

小内存分配（通常小于128KB）：

通常使用内存池（通过sbrk系统调用）来管理，先从内存池中查找一个空闲的块，将其标记为已分配，并返回指针。

DEFAULT_MMAP_THRESHOLD一般为128k，可通过mallopt进行设置。

sbrk通过移动堆指针来实现分配。

大内存分配：

通常使用mmap系统调用来直接分配内存。mmap将文件或匿名内存映射到进程的地址空间，返回一个指向映射区域的指针。

Free List():

空闲列表（free list），malloc实现分配内存时会利用空闲链表来操作。

本质是一个链表，用于存储已经释放尚未分配的内存块，当需要分配时，优先从空闲链表中选择合适的内存卡。数据结构大致如下：

struct FreeBlock {
    size_t size;          // 块的大小
    bool bIsAvalib;  // 是否使用
    struct FreeBlock *next; // 指向下一个空闲块的指针
};

如下图：来源于：https://www.jianshu.com/p/2fedeacfa797

大致流程：

初始化时：空闲列表通常为空。会向操作系统申请一块初始内存，作为第一个空闲块插入空闲列表中。

分配时：查找合适的空闲块，返回指针。（这里有不同的分配策略）

释放时：将释放的内存插入空闲列表中。并合并相邻的空闲块（为了避免出现内存碎片）。

分配策略：

大致有下列几种分配策略，配合内存管理模块，实际上会比较复杂，可能是几种方式组合使用。

1）从第一个空闲块开始找，找到空间够的。

2）从上一次分配的空闲块开始找个空间够的。

3）找个大小最接近的。

4）实际上可能会维护多个不同大小的空闲列表，根据malloc要申请的大小去使用不同的空闲列表。

关于free：

1）调用free后，会自动合并相邻的空闲块，为避免出现内存碎片。

2）为什么free可以不用传大小？

因为每次malloc后，申请的内存会比实际使用的大一点，在用户使用的内存前面会存放内存块头部信息，里面会存着本内存块的大小。free时根据该大小来正确回收资源。

如下图：是用vs2017测试的。

内存碎片：

定义：

在频繁的内存分配和释放的过程中，可能会导致内存碎片。大致分两类：

内部碎片（Internal Fragmentation）：已经被分配出去，结果无法使用的内存空间。比如用户申请了45字节，内存分配必须是4字节对齐的，系统可能会分配48个字节给用户。多出来的3个字节就成为了内部碎片。

外部碎片（External Fragmentation）：由于频繁分配释放，导致内存中出现许多小的，不连续的内存区域。这些区域可能总和能满足新内存请求，但是由于不连续而无法使用。

影响：

性能下降：碎片过多，会导致再分配时需要更多的时间来查找合适的内存块。

内存利用率低：

系统稳定性问题：引发程序崩溃或系统挂起。

分配失败：用户无法分配足够的内存空间，影响用户程序运行。

解决策略：

1）内存池（Memory Pool）：预先分配一块打内存，并划分为小块。每次申请时从内存池中获取。

2）紧凑（Compaction）：移动内存中的数据块，将分散的空闲块合并。需要额外的开销。

3）使用不同的内存分配算法：

4）内存对齐和预取：确保内存分配是对齐的，减少内部碎片。

实际使用：

操作系统提供了多种内存管理机制，Linux下如：slab分配器，伙伴系统等。 win下有Heap Manager等，都可以用于优化内存的分配释放。

new和delete

1.new和delete是运算符（malloc free是函数），理论上可以被重载，实现自己的new 运算符。

2.malloc失败了返回空指针，new失败了抛异常（没有被重载的情况下）。、

3.new 和 delete配套使用。 new数组和 delete[]配套使用。

4.new不仅会分配内存，还会调用构造函数。

两个小开脑洞的问题：

问题1：malloc出来的指针，用delete释放？

问题2：new出来的指针，用free释放？

先上结论：

1）malloc出来的空间，可以通过delete回收。

2）new出来的空间，可以通过free回收。（如果new出来的是数组，无法用free回收，会引起崩溃）

3）上述理论可行，但是不建议这么做。还是要配套使用，或者使用智能指针管理变量。

上代码：

mallocTest.cpp

#include <iostream>

struct AAA
{
    AAA(){printf("AAA() ... \n");}
    ~AAA(){printf("~AAA() ... \n");}
    int index;
    float fdata;
    int arrData[1024 * 1024 * 100];
};

void mallocTest()
{
    printf("mallocTest  +++++ \n");
    int nnn = 2;
    auto pp = (AAA*)malloc(sizeof(AAA)*nnn);
    pp->index = 555;
    for(int i = 0; i < nnn; i++)
    {
        pp[i].index = i;
        int len = sizeof(pp[i].arrData) / sizeof(int);
        for(int j = 0; j < len; j++)
        {
            pp[i].arrData[j] = i * j *j;
        }
    }
    printf("mallocTest  new end. getchar free \n");
    getchar();
    delete pp;
    //free(pp);
    printf("mallocTest  free end. getchar quit \n");
    getchar();
}

void newTest()
{
    printf("newTest  +++++ \n");
    auto pp = new AAA();
    pp->index = 555;
    
        int len = sizeof(pp[0].arrData) / sizeof(int);
        for(int j = 0; j < len; j++)
        {
            pp[0].arrData[j] = 1 * j *j;
        }
    
    printf("newTest  new end. getchar free \n");
    getchar();
    free(pp);
    printf("newTest  free end. getchar quit \n");
    getchar();
}

int main()
{
    printf("main  +++++ \n");
    //newTest();
    mallocTest();
    return 0;
}

先执行mallocTest()：

同时打开htop查看系统占用情况，按下回车，再次查看系统占用情况。

malloc分配完内存情况：

delete后内存情况：

再执行newtest:

new之后（free之前）：

free之后：

标签：malloc,free,内存,new,分配,空闲,底层
From： https://www.cnblogs.com/xcywt/p/18475892

malloc底层实现以及和new的比较

背景：