malloc_malloc函数 - CSDN
malloc 订阅
malloc的全称是memory allocation,中文叫动态内存分配,用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存,且分配的大小就是程序要求的大小。 展开全文
malloc的全称是memory allocation,中文叫动态内存分配,用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存,且分配的大小就是程序要求的大小。
信息
头文件
stdlib.h
简    称
malloc
特    点
由系统根据程序的需要即时分配
中文名
动态内存分配
原    型
extern void *malloc
外文名
memory allocation
malloc函数函数定义
其函数原型为void *malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的返回值是分配区域的起始地址,或者说,此函数是一个指针型函数,返回的指针指向该分配域的开头位置。如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定),否则返回空指针NULL。当内存不再使用时,应使用free()函数将内存块释放。函数返回的指针一定要适当对齐,使其可以用于任何数据对象。关于该函数的原型,在以前malloc返回的是char型指针,新的ANSIC标准规定,该函数返回为void型指针,因此必要时要进行类型转换。它能向系统申请分配一个长度为num_bytes(或size)个字节的内存块。一般它需和free函数配对使用。free函数能释放某个动态分配的地址,表明不再使用这块动态分配的内存了,实现把之前动态申请的内存返还给系统。 [1] 
收起全文
精华内容
参与话题
  • malloc函数,大大的详解

    万次阅读 多人点赞 2016-06-17 17:22:46
    1,关于malloc以及相关的几个函数  #include (Linux下)  void *malloc(size_t size);  void free(void *ptr);  void *calloc(size_t nmemb, size_t size);  void *realloc(void *ptr, size_t

    很多学过C的人对malloc都不是很了解,知道使用malloc要加头文件,知道malloc是分配一块连续的内存,知道和free函数是一起用的。但是但是:

    一部分人还是将:malloc当作系统所提供的或者是C的关键字,事实上:malloc只是C标准库中提供的一个普通函数

    而且很多很多人都对malloc的具体实现机制不是很了解。



    1,关于malloc以及相关的几个函数

          #include <stdlib.h>(Linux下)

           void *malloc(size_t size);
           void free(void *ptr);
           void *calloc(size_t nmemb, size_t size);
           void *realloc(void *ptr, size_t size);

          也可以这样认为(window下)原型:extern void *malloc(unsigned int num_bytes);

                                                          头文件:#include <malloc.h>或者#include <alloc.h>两者的内容是完全一样的。

           如果分配成功:则返回指向被分配内存空间的指针

           不然,返回空指针NULL。

           同时,当内存不再使用的时候,应使用free()函数将内存块释放掉。


           关于:void *,表示未确定类型的指针。C,C++规定,void *类型可以强转为任何其他类型的的指针。


    malloc returns a void pointer to the allocated space, or NULL if there is insufficient memory available. To return a pointer to a type other than void, use a type cast on the return value. The storage space pointed to by the return value is guaranteed to be suitably aligned for storage of any type of object. If size is 0, malloc allocates a zero-length item in the heap and returns a valid pointer to that item. Always check the return from malloc, even if the amount of memory requested is small.


             关于void *的其他说法:

             void * p1;

             int *p2;

             p1 = p2;                 就是说其他任意类型都可以直接赋值给它,无需进行强转,但是反过来不可以。


    malloc:

    malloc分配的内存大小至少为size参数所指定的字节数

    malloc的返回值是一个指针,指向一段可用内存的起始地址

    多次调用malloc所分配的地址不能有重叠部分,除非某次malloc所分配的地址被释放掉

    malloc应该尽快完成内存分配并返回(不能使用NP-hard的内存分配算法)

    实现malloc时应同时实现内存大小调整和内存释放函数(realloc和free)




    malloc和free函数是配对的,如果申请后不释放就是内存泄露;如果无故释放那就是什么都没有做,释放只能释放一次,如果释放两次及两次以上会出现错误(但是释放空指针例外,释放空指针其实也等于什么都没有做,所以,释放多少次都是可以的)






    2,malloc和new

         

         new返回指定类型的指针,并且可以自动计算所需要的大小。

        

          int *p;

          p = new int;   //返回类型为int *类型,分配的大小为sizeof(int)

          p = new int[100];    //返回类型为int *类型,分配的大小为sizeof(int) * 100

        

          而malloc则必须由我们计算字节数,并且在返回的时候强转成实际指定类型的指针。

      

          int *p;

          p = (int *)malloc(sizeof(int));


              1,malloc的返回是void *,如果我们写成了: p = malloc(sizeof(int));间接的说明了(将void *转化给了int *,这不合理)

          2,malloc的实参是sizeof(int),用于指明一个整形数据需要的大小,如果我们写成:

                p =  (int *)malloc(1),          那么可以看出:只是申请了一个字节的空间,如果向里面存放了一个整数的话,

                将会占用额外的3个字节,可能会改变原有内存空间中的数据

         3,malloc只管分配内存,并不能对其进行初始化,所以得到的一片新内存中,其值将是随机的。一般意义上:我

               们习惯性的将其初始化为NULL。            当然,也可以用memset函数的。



    简单的说:


    malloc函数其实就是在内存中:找一片指定大小的空间,然后将这个空间的首地址给一个指针变量,这里的指针变量可以是一个单独的指针,也可以是一个数组的首地址,这要看malloc函数中参数size的具体内容。我们这里malloc分配的内存空间在逻辑上是连续的,而在物理上可以不连续。我们作为程序员,关注的是逻辑上的连续,其它的,操作系统会帮着我们处理的。

     


    下面我们聊聊malloc的具体实现机制:

    Linux内存管理

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

      为了简单,现代操作系统在处理内存地址时,普遍采用虚拟内存地址技术。即在汇编程序(或机器语言)层面,当涉及内存地址时,都是使用虚拟内存地址。采用这种技术时,每个进程仿佛自己独享一片2N字节的内存,其中N是机器位数。例如在64位CPU和64位操作系统下,每个进程的虚拟地址空间为264Byte。

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

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



    页与地址构成

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

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

    内存地址构成

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

      MMU映射单位并不是字节,而是页,这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂,为了加快速度会引入一系列缓存和优化,例如TLB等机制。下面给出一个经过简化的内存地址翻译示意图,虽然经过了简化,但是基本原理与现代计算机真实的情况的一致的。

    内存地址翻译


    内存页与磁盘页

      我们知道一般将内存看做磁盘的的缓存,有时MMU在工作时,会发现页表表明某个内存页不在物理内存中,此时会触发一个缺页异常(Page Fault),此时系统会到磁盘中相应的地方将磁盘页载入到内存中,然后重新执行由于缺页而失败的机器指令。关于这部分,因为可以看做对malloc实现是透明的,所以不再详细讲述,有兴趣的可以参考《深入理解计算机系统》相关章节。

      最后附上一张在维基百科找到的更加符合真实地址翻译的流程供大家参考,这张图加入了TLB和缺页异常的流程(图片来源页)。

    较为完整的地址翻译流程


    Linux进程级内存管理

      2.2.1 内存排布

      明白了虚拟内存和物理内存的关系及相关的映射机制,下面看一下具体在一个进程内是如何排布内存的。

      以Linux 64位系统为例。理论上,64bit内存地址可用空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF,这是个相当庞大的空间,Linux实际上只用了其中一小部分(256T)。

      根据Linux内核相关文档描述,Linux64位操作系统仅使用低47位,高17位做扩展(只能是全0或全1)。所以,实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF,其中前面为用户空间(User Space),后者为内核空间(Kernel Space)。图示如下:

    Linux进程地址排布

      对用户来说,主要关注的空间是User Space。将User Space放大后,可以看到里面主要分为如下几段:

    • Code:这是整个用户空间的最低地址部分,存放的是指令(也就是程序所编译成的可执行机器码)
    • Data:这里存放的是初始化过的全局变量
    • BSS:这里存放的是未初始化的全局变量
    • Heap:堆,这是我们本文重点关注的地方,堆自低地址向高地址增长,后面要讲到的brk相关的系统调用就是从这里分配内存
    • Mapping Area:这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域,本文不讨论这种情况。这个区域自高地址向低地址增长
    • Stack:这是栈区域,自高地址向低地址增长

      下面我们主要关注Heap区域的操作。对整个Linux内存排布有兴趣的同学可以参考其它资料。


    Heap内存模型

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

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

    Linux进程堆管理

      Linux维护一个break指针,这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的,可以供进程访问;而从break往上,是未映射的地址空间,如果访问这段空间则程序会报错。


    brk与sbrk

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

    int brk(void *addr);
    void *sbrk(intptr_t increment);

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

      一个小技巧是,如果将increment设置为0,则可以获得当前break的地址。

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



    资源限制与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

      3.1 玩具实现

      在正式开始讨论malloc的实现前,我们可以利用上述知识实现一个简单但几乎没法用于真实的玩具malloc,权当对上面知识的复习:

    /* 一个玩具malloc */
    #include <sys/types.h>
    #include <unistd.h>
    void *malloc(size_t size)
    {
    void *p;
    p = sbrk(0);
    if (sbrk(size) == (void *)-1)
    return NULL;
    return p;
    }

      这个malloc每次都在当前break的基础上增加size所指定的字节数,并将之前break的地址返回。这个malloc由于对所分配的内存缺乏记录,不便于内存释放,所以无法用于真实场景。



    3.2 正式实现

      下面严肃点讨论malloc的实现方案。

      3.2.1 数据结构

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

      可以用如下结构体定义一个block:

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

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

    Block结构




    3.2.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 *last, size_t size) {
    t_block b = first_block;
    while(b && !(b->free && b->size >= size)) {
    *last = b;
    b = b->next;
    }
    return b;
    }

      find_block从frist_block开始,查找第一个符合要求的block并返回block起始地址,如果找不到这返回NULL。这里在遍历时会更新一个叫last的指针,这个指针始终指向当前遍历的block。这是为了如果找不到合适的block而开辟新block使用的,具体会在接下来的一节用到。



    3.2.3 开辟新的block

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

    #define BLOCK_SIZE 24 /* 由于存在虚拟的data字段,sizeof不能正确计算meta长度,这里手工设置 */
     
    t_block extend_heap(t_block last, size_t s) {
    t_block b;
    b = sbrk(0);
    if(sbrk(BLOCK_SIZE + s) == (void *)-1)
    return NULL;
    b->size = s;
    b->next = NULL;
    if(last)
    last->next = b;
    b->free = 0;
    return b;
    }

      3.2.4 分裂block

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

    分裂block

      实现代码:

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



    3.2.5 malloc的实现

      有了上面的代码,我们可以利用它们整合成一个简单但初步可用的malloc。注意首先我们要定义个block链表的头first_block,初始化为NULL;另外,我们需要剩余空间至少有BLOCK_SIZE + 8才执行分裂操作。

      由于我们希望malloc分配的数据区是按8字节对齐,所以在size不为8的倍数时,我们需要将size调整为大于size的最小的8的倍数:

    size_t align8(size_t s) {
    if(s & 0x7 == 0)
    return s;
    return ((s >> 3) + 1) << 3;
    }
    #define BLOCK_SIZE 24
    void *first_block=NULL;
     
    /* other functions... */
     
    void *malloc(size_t size) {
    t_block b, last;
    size_t s;
    /* 对齐地址 */
    s = align8(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;
    }


    3.2.6 calloc的实现

      有了malloc,实现calloc只要两步:

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

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

    void *calloc(size_t number, size_t size) {
    size_t *new;
    size_t s8, i;
    new = malloc(number * size);
    if(new) {
    s8 = align8(number * size) >> 3;
    for(i = 0; i < s8; i++)
    new[i] = 0;
    }
    return new;
    }


    3.2.7 free的实现

      free的实现并不像看上去那么简单,这里我们要解决两个关键问题:

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

      首先我们要保证传入free的地址是有效的,这个有效包括两方面:

    • 地址应该在之前malloc所分配的区域内,即在first_block和当前break指针范围内
    • 这个地址确实是之前通过我们自己的malloc分配的

      第一个问题比较好解决,只要进行地址比较就可以了,关键是第二个问题。这里有两种解决方案:一是在结构体内埋一个magic number字段,free之前通过相对偏移检查特定位置的值是否为我们设置的magic number,另一种方法是在结构体内增加一个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。实现如下:

    void free(void *p) {
    t_block b;
    if(valid_addr(p)) {
    b = get_block(p);
    b->free = 1;
    if(b->prev && b->prev->free)
    b = fusion(b->prev);
    if(b->next)
    fusion(b);
    else {
    if(b->prev)
    b->prev->prev = NULL;
    else
    first_block = NULL;
    brk(b);
    }
    }
    }





     3.2.8 realloc的实现

      为了实现realloc,我们首先要实现一个内存复制方法。如同calloc一样,为了效率,我们以8字节为单位进行复制:

    void copy_block(t_block src, t_block dst) {
    size_t *sdata, *ddata;
    size_t i;
    sdata = src->ptr;
    ddata = dst->ptr;
    for(i = 0; (i * 8) < src->size && (i * 8) < dst->size; i++)
    ddata[i] = sdata[i];
    }

      然后我们开始实现realloc。一个简单(但是低效)的方法是malloc一段内存,然后将数据复制过去。但是我们可以做的更高效,具体可以考虑以下几个方面:

    • 如果当前block的数据区大于等于realloc所要求的size,则不做任何操作
    • 如果新的size变小了,考虑split
    • 如果当前block的数据区不能满足size,但是其后继block是free的,并且合并后可以满足,则考虑做合并

      下面是realloc的实现:

    void *realloc(void *p, size_t size) {
    size_t s;
    t_block b, new;
    void *newp;
    if (!p)
    /* 根据标准库文档,当p传入NULL时,相当于调用malloc */
    return malloc(size);
    if(valid_addr(p)) {
    s = align8(size);
    b = get_block(p);
    if(b->size >= s) {
    if(b->size - s >= (BLOCK_SIZE + 8))
    split_block(b,s);
    } else {
    /* 看是否可进行合并 */
    if(b->next && b->next->free
    && (b->size + BLOCK_SIZE + b->next->size) >= s) {
    fusion(b);
    if(b->size - s >= (BLOCK_SIZE + 8))
    split_block(b, s);
    } else {
    /* 新malloc */
    newp = malloc (s);
    if (!newp)
    return NULL;
    new = get_block(newp);
    copy_block(b, new);
    free(p);
    return(newp);
    }
    }
    return (p);
    }
    return NULL;
    }

      3.3 遗留问题和优化

      以上是一个较为简陋,但是初步可用的malloc实现。还有很多遗留的可能优化点,例如:

    • 同时兼容32位和64位系统
    • 在分配较大快内存时,考虑使用mmap而非sbrk,这通常更高效
    • 可以考虑维护多个链表而非单个,每个链表中的block大小均为一个范围内,例如8字节链表、16字节链表、24-32字节链表等等。此时可以根据size到对应链表中做分配,可以有效减少碎片,并提高查询block的速度
    • 可以考虑链表中只存放free的block,而不存放已分配的block,可以减少查找block的次数,提高效率

      还有很多可能的优化,这里不一一赘述。下面附上一些参考文献,有兴趣的同学可以更深入研究。

      4 其它参考

    1. 这篇文章大量参考了A malloc Tutorial,其中一些图片和代码直接引用了文中的内容,这里特别指出
    2. Computer Systems: A Programmer's Perspective, 2/E一书有许多值得参考的地方
    3. 关于Linux的虚拟内存模型,Anatomy of a Program in Memory是很好的参考资料,另外作者还有一篇How the Kernel Manages Your Memory对于Linux内核中虚拟内存管理的部分有很好的讲解
    4. 对于真实世界的malloc实现,可以参考glibc的实现
    5. 本文写作过程中大量参考了维基百科,再次感谢这个伟大的网站,并且呼吁大家在手头允许的情况下可以适当捐助维基百科,帮助这个造福人类的系统运行下去



    本文转载:http://kb.cnblogs.com/page/512454/

    展开全文
  • malloc函数的用法

    2018-09-04 17:19:43
    malloc函数是动态分配内存的重要的函数,看完该文,轻松学会使用malloc函数
  • malloc 函数详解

    万次阅读 多人点赞 2018-06-29 22:09:32
    很多学过C的人对malloc都不是很了解,知道使用malloc要加头文件,知道malloc是分配一块连续的内存,知道和free函数是一起用的。但是但是:一部分人还是将:malloc当作系统所提供的或者是C的关键字,事实上:malloc...

    很多学过C的人对malloc都不是很了解,知道使用malloc要加头文件,知道malloc是分配一块连续的内存,知道和free函数是一起用的。但是但是:

    一部分人还是将:malloc当作系统所提供的或者是C的关键字,事实上:malloc只是C标准库中提供的一个普通函数

    而且很多很多人都对malloc的具体实现机制不是很了解。



    1,关于malloc以及相关的几个函数

          #include <stdlib.h>(Linux下)

           void *malloc(size_t size);
           void free(void *ptr);
           void *calloc(size_t nmemb, size_t size);
           void *realloc(void *ptr, size_t size);

          也可以这样认为(window下)原型:extern void *malloc(unsigned int num_bytes);

                                                          头文件:#include <malloc.h>或者#include <alloc.h>两者的内容是完全一样的。

           如果分配成功:则返回指向被分配内存空间的指针

           不然,返回空指针NULL。

           同时,当内存不再使用的时候,应使用free()函数将内存块释放掉。


           关于:void *,表示未确定类型的指针。C,C++规定,void *类型可以强转为任何其他类型的的指针。


    malloc returns a void pointer to the allocated space, or NULL if there is insufficient memory available. To return a pointer to a type other than void, use a type cast on the return value. The storage space pointed to by the return value is guaranteed to be suitably aligned for storage of any type of object. If size is 0, malloc allocates a zero-length item in the heap and returns a valid pointer to that item. Always check the return from malloc, even if the amount of memory requested is small.


             关于void *的其他说法:

             void * p1;

             int *p2;

             p1 = p2;                 就是说其他任意类型都可以直接赋值给它,无需进行强转,但是反过来不可以。


    malloc:

    malloc分配的内存大小至少为size参数所指定的字节数

    malloc的返回值是一个指针,指向一段可用内存的起始地址

    多次调用malloc所分配的地址不能有重叠部分,除非某次malloc所分配的地址被释放掉

    malloc应该尽快完成内存分配并返回(不能使用NP-hard的内存分配算法)

    实现malloc时应同时实现内存大小调整和内存释放函数(realloc和free)




    malloc和free函数是配对的,如果申请后不释放就是内存泄露;如果无故释放那就是什么都没有做,释放只能释放一次,如果释放两次及两次以上会出现错误(但是释放空指针例外,释放空指针其实也等于什么都没有做,所以,释放多少次都是可以的)






    2,malloc和new

         

         new返回指定类型的指针,并且可以自动计算所需要的大小。

        

          int *p;

          p = new int;   //返回类型为int *类型,分配的大小为sizeof(int)

          p = new int[100];    //返回类型为int *类型,分配的大小为sizeof(int) * 100

        

          而malloc则必须由我们计算字节数,并且在返回的时候强转成实际指定类型的指针。

      

          int *p;

          p = (int *)malloc(sizeof(int));


              1,malloc的返回是void *,如果我们写成了: p = malloc(sizeof(int));间接的说明了(将void *转化给了int *,这不合理)

          2,malloc的实参是sizeof(int),用于指明一个整形数据需要的大小,如果我们写成:

                p =  (int *)malloc(1),          那么可以看出:只是申请了一个字节的空间,如果向里面存放了一个整数的话,

                将会占用额外的3个字节,可能会改变原有内存空间中的数据

         3,malloc只管分配内存,并不能对其进行初始化,所以得到的一片新内存中,其值将是随机的。一般意义上:我

               们习惯性的将其初始化为NULL。            当然,也可以用memset函数的。



    简单的说:


    malloc 函数其实就是在内存中:找一片指定大小的空间,然后将这个空间的首地址给一个指针变量,这里的指针变量可以是一个单独的指针,也可以是一个数组的首地址, 这要看malloc函数中参数size的具体内容。我们这里malloc分配的内存空间在逻辑上是连续的,而在物理上可以不连续。我们作为程序员,关注的 是逻辑上的连续,其它的,操作系统会帮着我们处理的。

     


    下面我们聊聊malloc的具体实现机制:

    Linux内存管理

     

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

      为了简单,现代操作系统在处理内存地址时,普遍采用虚拟内存地址技术。即在汇编程序(或机器语言)层面,当涉及内存地址时, 都是使用虚拟内存地址。采用这种技术时,每个进程仿佛自己独享一片2N字节的内存,其中N是机器位数。例如在64位CPU和64位操作系统下,每个进程的 虚拟地址空间为264Byte。

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

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

     


    页与地址构成

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

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

    内存地址构成

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

      MMU映射单位并不是字节,而是页,这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂,为了加快速度会引入一系列缓存和优化,例如TLB等机制。下面给出一个经过简化的内存地址翻译示意图,虽然经过了简化,但是基本原理与现代计算机真实的情况的一致的。

    内存地址翻译


    内存页与磁盘页

      我们知道一般将内存看做磁盘的的缓存,有时MMU在工作时,会发现页表表明某个内存页不在物理内存中,此时会触发一个缺页异 常(Page Fault),此时系统会到磁盘中相应的地方将磁盘页载入到内存中,然后重新执行由于缺页而失败的机器指令。关于这部分,因为可以看做对malloc实现 是透明的,所以不再详细讲述,有兴趣的可以参考《深入理解计算机系统》相关章节。

      最后附上一张在维基百科找到的更加符合真实地址翻译的流程供大家参考,这张图加入了TLB和缺页异常的流程(图片来源页)。

    较为完整的地址翻译流程


    Linux进程级内存管理

      2.2.1 内存排布

      明白了虚拟内存和物理内存的关系及相关的映射机制,下面看一下具体在一个进程内是如何排布内存的。

      以Linux 64位系统为例。理论上,64bit内存地址可用空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF,这是个相当庞大的空间,Linux实际上只用了其中一小部分(256T)。

      根据Linux内核相关文档描述,Linux64位操作系统仅使用低47位,高17位做扩展(只能是全0或全1)。所以,实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF,其中前面为用户空间(User Space),后者为内核空间(Kernel Space)。图示如下:

    Linux进程地址排布

      对用户来说,主要关注的空间是User Space。将User Space放大后,可以看到里面主要分为如下几段:

    • Code:这是整个用户空间的最低地址部分,存放的是指令(也就是程序所编译成的可执行机器码)
    • Data:这里存放的是初始化过的全局变量
    • BSS:这里存放的是未初始化的全局变量
    • Heap:堆,这是我们本文重点关注的地方,堆自低地址向高地址增长,后面要讲到的brk相关的系统调用就是从这里分配内存
    • Mapping Area:这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域,本文不讨论这种情况。这个区域自高地址向低地址增长
    • Stack:这是栈区域,自高地址向低地址增长

      下面我们主要关注Heap区域的操作。对整个Linux内存排布有兴趣的同学可以参考其它资料。

     

    Heap内存模型

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

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

    Linux进程堆管理

      Linux维护一个break指针,这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的,可以供进程访问;而从break往上,是未映射的地址空间,如果访问这段空间则程序会报错。


    brk与sbrk

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

    int brk(void *addr);
    void *sbrk(intptr_t increment);

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

      一个小技巧是,如果将increment设置为0,则可以获得当前break的地址。

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



    资源限制与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

      3.1 玩具实现

      在正式开始讨论malloc的实现前,我们可以利用上述知识实现一个简单但几乎没法用于真实的玩具malloc,权当对上面知识的复习:

    复制代码
    /* 一个玩具malloc */
    #include <sys/types.h>
    #include <unistd.h>
    void *malloc(size_t size)
    {
    void *p;
    p = sbrk(0);
    if (sbrk(size) == (void *)-1)
    return NULL;
    return p;
    }
    复制代码

      这个malloc每次都在当前break的基础上增加size所指定的字节数,并将之前break的地址返回。这个malloc由于对所分配的内存缺乏记录,不便于内存释放,所以无法用于真实场景。



    3.2 正式实现

      下面严肃点讨论malloc的实现方案。

      3.2.1 数据结构

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

      可以用如下结构体定义一个block:

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

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

    Block结构


    关于长度为1的数组注意:http://bbs.csdn.net/topics/300077699


    3.2.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 *last, size_t size) {
    t_block b = first_block;
    while(b && !(b->free && b->size >= size)) {
    *last = b;
    b = b->next;
    }
    return b;
    }
    复制代码

      find_block从frist_block开始,查找第一个符合要求的block并返回block起始地址,如果找不到 这返回NULL。这里在遍历时会更新一个叫last的指针,这个指针始终指向当前遍历的block。这是为了如果找不到合适的block而开辟新 block使用的,具体会在接下来的一节用到。



    3.2.3 开辟新的block

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

    复制代码
    #define BLOCK_SIZE 24 /* 由于存在虚拟的data字段,sizeof不能正确计算meta长度,这里手工设置 */
     
    t_block extend_heap(t_block last, size_t s) {
    t_block b;
    b = sbrk(0);
    if(sbrk(BLOCK_SIZE + s) == (void *)-1)
    return NULL;
    b->size = s;
    b->next = NULL;
    if(last)
    last->next = b;
    b->free = 0;
    return b;
    }
    复制代码

      3.2.4 分裂block

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

    分裂block

      实现代码:

    复制代码
    void split_block(t_block b, size_t s) {
    t_block new;
    new = b->data + s;
    new->size = b->size - s - BLOCK_SIZE ;
    new->next = b->next;
    new->free = 1;
    b->size = s;
    b->next = new;
    }
    复制代码



     

    3.2.5 malloc的实现

      有了上面的代码,我们可以利用它们整合成一个简单但初步可用的malloc。注意首先我们要定义个block链表的头first_block,初始化为NULL;另外,我们需要剩余空间至少有BLOCK_SIZE + 8才执行分裂操作。

      由于我们希望malloc分配的数据区是按8字节对齐,所以在size不为8的倍数时,我们需要将size调整为大于size的最小的8的倍数:

    size_t align8(size_t s) {
    if(s & 0x7 == 0)
    return s;
    return ((s >> 3) + 1) << 3;
    }
    复制代码
    #define BLOCK_SIZE 24
    void *first_block=NULL;
     
    /* other functions... */
     
    void *malloc(size_t size) {
    t_block b, last;
    size_t s;
    /* 对齐地址 */
    s = align8(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;
    }
    复制代码

     


     

    3.2.6 calloc的实现

      有了malloc,实现calloc只要两步:

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

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

    复制代码
    void *calloc(size_t number, size_t size) {
    size_t *new;
    size_t s8, i;
    new = malloc(number * size);
    if(new) {
    s8 = align8(number * size) >> 3;
    for(i = 0; i < s8; i++)
    new[i] = 0;
    }
    return new;
    }
    复制代码

     


     

    3.2.7 free的实现

      free的实现并不像看上去那么简单,这里我们要解决两个关键问题:

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

      首先我们要保证传入free的地址是有效的,这个有效包括两方面:

    • 地址应该在之前malloc所分配的区域内,即在first_block和当前break指针范围内
    • 这个地址确实是之前通过我们自己的malloc分配的

      第一个问题比较好解决,只要进行地址比较就可以了,关键是第二个问题。这里有两种解决方案:一是在结构体内埋一个magic number字段,free之前通过相对偏移检查特定位置的值是否为我们设置的magic number,另一种方法是在结构体内增加一个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。实现如下:

    复制代码
    void free(void *p) {
    t_block b;
    if(valid_addr(p)) {
    b = get_block(p);
    b->free = 1;
    if(b->prev && b->prev->free)
    b = fusion(b->prev);
    if(b->next)
    fusion(b);
    else {
    if(b->prev)
    b->prev->prev = NULL;
    else
    first_block = NULL;
    brk(b);
    }
    }
    }
    复制代码





     3.2.8 realloc的实现

      为了实现realloc,我们首先要实现一个内存复制方法。如同calloc一样,为了效率,我们以8字节为单位进行复制:

    复制代码
    void copy_block(t_block src, t_block dst) {
    size_t *sdata, *ddata;
    size_t i;
    sdata = src->ptr;
    ddata = dst->ptr;
    for(i = 0; (i * 8) < src->size && (i * 8) < dst->size; i++)
    ddata[i] = sdata[i];
    }
    复制代码

      然后我们开始实现realloc。一个简单(但是低效)的方法是malloc一段内存,然后将数据复制过去。但是我们可以做的更高效,具体可以考虑以下几个方面:

    • 如果当前block的数据区大于等于realloc所要求的size,则不做任何操作
    • 如果新的size变小了,考虑split
    • 如果当前block的数据区不能满足size,但是其后继block是free的,并且合并后可以满足,则考虑做合并

      下面是realloc的实现:

    复制代码
    void *realloc(void *p, size_t size) {
    size_t s;
    t_block b, new;
    void *newp;
    if (!p)
    /* 根据标准库文档,当p传入NULL时,相当于调用malloc */
    return malloc(size);
    if(valid_addr(p)) {
    s = align8(size);
    b = get_block(p);
    if(b->size >= s) {
    if(b->size - s >= (BLOCK_SIZE + 8))
    split_block(b,s);
    } else {
    /* 看是否可进行合并 */
    if(b->next && b->next->free
    && (b->size + BLOCK_SIZE + b->next->size) >= s) {
    fusion(b);
    if(b->size - s >= (BLOCK_SIZE + 8))
    split_block(b, s);
    } else {
    /* 新malloc */
    newp = malloc (s);
    if (!newp)
    return NULL;
    new = get_block(newp);
    copy_block(b, new);
    free(p);
    return(newp);
    }
    }
    return (p);
    }
    return NULL;
    }
    复制代码

      3.3 遗留问题和优化

      以上是一个较为简陋,但是初步可用的malloc实现。还有很多遗留的可能优化点,例如:

    • 同时兼容32位和64位系统
    • 在分配较大快内存时,考虑使用mmap而非sbrk,这通常更高效
    • 可以考虑维护多个链表而非单个,每个链表中的block大小均为一个范围内,例如8字节链表、16字节链表、24-32字节链表等等。此时可以根据size到对应链表中做分配,可以有效减少碎片,并提高查询block的速度
    • 可以考虑链表中只存放free的block,而不存放已分配的block,可以减少查找block的次数,提高效率

      还有很多可能的优化,这里不一一赘述。下面附上一些参考文献,有兴趣的同学可以更深入研究。

    展开全文
  • 【c语言】malloc函数详解

    万次阅读 多人点赞 2018-07-29 11:35:53
    谈到malloc函数相信学过c语言的人都很熟悉,但是malloc底层到底做了什么又有多少人知道。 关于malloc相关的几个函数 关于malloc我们进入Linux man一下就会得到如下结果: 也可以这样认为(window下)原型: ...

    谈到malloc函数相信学过c语言的人都很熟悉,但是malloc底层到底做了什么又有多少人知道。
    1、关于malloc相关的几个函数
    关于malloc我们进入Linux man一下就会得到如下结果:
    这里写图片描述
    也可以这样认为(window下)原型:

    extern void *malloc(unsigned int num_bytes);

    头文件:

    #include<malloc.h>或者#include<alloc.h>两者的内容是完全一样的

    如果分配成功:则返回指向被分配内存空间的指针
    不然返回指针NULL
    同时,当内存不再使用的时候,应使用free()函数将内存块释放掉。
    关于:void*,表示未确定类型的指针,c,c++规定void*可以强转为任何其他类型的指针,关于void还有一种说法就是其他任何类型都可以直接赋值给它,无需进行强转,但是反过来不可以
    malloc:
    malloc分配的内存大小至少为参数所指定的字节数
    malloc的返回值是一个指针,指向一段可用内存的起始位置,指向一段可用内存的起始地址,多次调用malloc所分配的地址不能有重叠部分,除非某次malloc所分配的地址被释放掉malloc应该尽快完成内存分配并返回(不能使用NP-hard的内存分配算法)实现malloc时应同时实现内存大小调整和内存释放函数(realloc和free)
    malloc和free是配对的,如果申请后不释放就是内存泄露,如果无故释放那就是什么也没做,释放只能释放一次,如果一块空间释放两次或者两次以上会出现错误(但是释放空指针例外,释放空指针也等于什么也没做,所以释放多少次都是可以的。)
    2、malloc和new
    new返回指定类型的指针,并且可以自动计算所需要的大小。

    int *p;
    p = new int;//返回类型为int* ,分配的大小是sizeof(int)
    p = new int[100];//返回类型是int*类型,分配的大小为sizeof(int)*100
    

    而malloc需要我们自己计算字节数,并且返回的时候要强转成指定类型的指针。

    int *p;
    p = (int *)malloc(sizeof(int));

    (1)malloc的返回是void*,如果我们写成了:p=malloc(sizeof(int));间接的说明了(将void转化给了int*,这不合理)
    (2)malloc的实参是sizeof(int),用于指明一个整型数据需要的大小,如果我们写成p=(int*)malloc(1),那么可以看出:只是申请了一个一个字节大小的空间。
    (3)malloc只管分配内存,并不能对其进行初始化,所以得到的一片新内存中,其值将是随机的。一般意义上:我们习惯性的将其初始化为NULL,当然也可以使用memset函数。
    简单的说:
    malloc函数其实就是在内存中找一片指定大小的空间,然后将这个空间的首地址给一个指针变量,这里的指针变量可以是一个单独的指针,也可以是一个数组的首地址,这要看malloc函数中参数size的具体内容。我们这里malloc分配的内存空间在逻辑上是连续的,而在物理上可以不连续。我们作为程序员,关注的是逻辑上的连续,其他的操作系统会帮着我们处理。
    下面就来看看malloc具体是怎么实现的。
    首先要了解操作系统相关的知识:
    虚拟内存地址和物理内存地址
    为了简单,现代操作系统在处理物理内存地址时,普遍采用虚拟内存地址技术。即在汇编程序层面,当涉及内存地址时,都是使用的虚拟内存地址。采用这种技术时,每个进程仿佛自己独享一片2N字节的内存,其中N是机器位数。例如在64位CPU和64位操作系统下每个进程的虚拟地址空间为264Byte。
    这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理,真实中的进程不太可能如此大的空间,实际能用到的空间大小取决于物理内存的大小。
    由于在机器语言层面都是采用虚拟地址,当实际的机器码程序涉及到内存操作时,需要根据当前进程运行的实际上下文将虚拟地址转化为物理内存地址,才能实现对内存数据的操作。这个转换一般由一个叫MMU的硬件完成。
    页与地址构成
    在现代操作系统中,不论是虚拟内存还是物理内存,都不是以字节为单位进行管理的,而是以页为单位。一个内存页是一段固定大小的连续的连续内存地址的总称,具体到Linux中,典型的内存页大小为4096 Byte
    所以内存地址可以分为页号和页内偏移量。下面以64位机器,4G物理内存,4K页大小为例,虚拟内存地址和物理内存地址的组成如下:
    这里写图片描述
    上面是虚拟内存地址,下面是物理内存地址。由于页大小都是4k,所以页内偏移都是用低12位表示,而剩下的高地址表示页号
    MMU映射单位并不是字节,而是页,这个映射通过差一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂,为了加快速度会引入一系列缓存和优化,例如TLB等机制,下面给出一个经过简化的内存地址翻译示意图:
    这里写图片描述
    内存页与磁盘页
    我们知道一般将内存看做磁盘的缓存,有时MMU在工作时,会发现页表表名某个内存页不在物理内存页不在物理内存中,此时会触发一个缺页异常,此时系统会到磁盘中相应的地方将磁盘页载入到内存中,然后重新执行由于缺页而失败的机器指令。关于这部分,因为可以看做对malloc实现是透明的,所以不再详述
    真实地址翻译流程:
    这里写图片描述
    Linux进程级内存管理
    2.2.1内存排布
    明白了虚拟内存和物理内存的关系及相关的映射机制,下面看一下具体在一个进程内是如何排布内存的。
    以Linux 64位系统为例。理论上,64bit内存地址空间为0x0000000000000000-0xFFFFFFFFFFFFFFF,这是个相当庞大的空间,Linux实际上只用了其中一小部分
    具体分布如图所示:
    这里写图片描述
    对用户来说主要关心的是User Space。将User Space放大后,可以看到里面主要分成如下几段:
    Code:这是整个用户空间的最低地址部分,存放的是指令(也就是程序所编译成的可执行机器码)
    Data:这里存放的是初始化过的全局变量
    BSS:这里存放的是未初始化的全局变量
    Heap:堆,这是我们本文主要关注的地方,堆自底向上由低地址向高地址增长
    Mapping Area:这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存空间,本文不考虑这种情况,这个区域由高地址像低地址增长
    Stack:栈区域,自高地址像低地址增长
    Heap内存模型:
    一般来说,malloc所申请的内存主要从Heap区域分配,来看看Heap的结构是怎样的。
    这里写图片描述
    Linux维护一个break指针,这个指针执行堆空间的某个地址,从堆开始到break之间的地址空间为映射好的,可以供进程访问,而从break往上,是未映射的地址空间,如果访问这段空间则程序会报错
    brk与sbrk
    由上文知道,要增加一个进程实际上的可用堆大小,就需要将break指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下:

    int brk(void *addr);
    void *sbrk(inptr_t increment);

    brk将break指针直接设置为某个地址,而sbrk将break从当前位置移动increment所指定的增量。brk在执行成功时返回0,否则返回-1并设置为errno为ENOMEM,sbrk成功时返回break移动之前所指向的地址,否则返回(void*)-1;
    资源限制和rlimirt
    系统为每一个进程所分配的资源不是无限的,包括可映射的空间,因此每个进程有一个rlimit表示当前进程可用的资源上限,这个限制可以通过getrlimit系统调用得到,下面代码获取当前进程虚拟内存空间的rlimit
    其中rlimt是一个结构体

    struct rlimit
    {
        rlimt_t rlim_cur;
        rlim_t rlim_max;
    };

    每种资源有硬限制和软限制,并且可以通过setrlimit对rlimit进行有条件限制作为软限制的上限,非特权进程只能设置软限制,且不能超过硬限制
    实现malloc
    (1)数据结构
    首先我们要确定所采用的数据结构。一个简单可行方案是将堆内存空间以块的形式组织起来,每个块由meta区和数据区组成,meta区记录数据块的元信息(数据区大小、空闲标志位、指针等等),数据区是真实分配的内存区域,并且数据区的第一个字节地址即为malloc返回的地址
    可以使用如下结构体定义一个block

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

    (2)寻找合适的block
    现在考虑如何在block链中查找合适的block。一般来说有两种查找算法:
    First fit:从头开始,使用第一个数据区大小大于要求size的块所谓此次分配的块
    Best fit:从头开始,遍历所有块,使用数据区大小大于size且差值最小的块作为此次分配的块
    两种方式各有千秋,best fit有较高的内存使用率(payload较高),而first fit具有较高的运行效率。这里我们采用first fit算法

    t_block find_block(t_block *last,size_t size){
        t_block b = first_block;
        while(b&&b->size>=size)
        {
            *last = b;
            b = b->next;
        }
        return b;
    }

    find_block从first_block开始,查找第一个符合要求的block并返回block起始地址,如果找不到这返回NULL,这里在遍历时会更新一个叫last的指针,这个指针始终指向当前遍历的block.这是为了如果找不到合适的block而开辟新block使用的。

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

    #define BLOCK_SIZE 24
    
    t_block extend_heap{
        t_block b;
        b = sbrk(0);
            if(sbrk(BLOCK_SIZE+s)==(void*)-1)
            return NULL;
            b->size = s;
            b->next - NULL;
            if(last)
            last->next = b;
            b->free = 0;
            return b;
    };

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

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

    (5)malloc的实现
    有了上面的代码,我们就可以实现一个简单的malloc.注意首先我们要定义个block链表的头first_block,初始化为NULL;另外,我们需要剩余空间至少有BLOCK_SIZE+8才执行分裂操作
    由于我们需要malloc分配的数据区是按8字节对齐,所以size不为8的倍数时,我们需要将size调整为大于size的最小的8的倍数

    size_t align8(size_t s)
    {
        if(s&0x7 == 0)
        return s;
        return ((s>>3)+1)<<3;
    }
    #define BLOCK_SIZE 24
    void *first_block=NULL;
    void *mallloc(size_t size)
    {
        t_block b,last;
        size_t s;
        //对齐地址
        s = align8(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;
    }
    展开全文
  • malloc详细

    千次阅读 多人点赞 2017-11-03 18:47:01
    malloc个人认识: malloc是一个函数,这个函数主要用于动态分配内存。 在我们运用过程中,数组虽然与可以用于开辟空间,但是相对于malloc这个函数,malloc的开辟的空间,可以在你用完内存后,迅速让计算机清楚掉。...

    malloc个人认识:
    malloc是一个函数,这个函数主要用于动态分配内存。
    在我们运用过程中,数组虽然与可以用于开辟空间,但是相对于malloc这个函数,malloc的开辟的空间,可以在你用完内存后,迅速让计算机清楚掉。

    malloc用法:
    指针名=(数据类型)malloc(长度),(数据类型)表示指针.
    举例1:int* buffer = (int*)malloc(8 * sizeof(int));
    这行代码是说,malloc开辟了一个int类型,8个int大小的空间,并且指针buffer指向这个malloc所开辟的空间。

    举例2:int** buffer = (int**)malloc(8 * sizeof(int*));
    这行代码则是在说,malloc开辟了一个int**类型,8个int*大小的空间,并且二维指针指向这个malloc所开辟的空间。

    那么举例1与举例2有什么区别呢?这里写图片描述

    举例1
    如上图所示:
    指针buffer指向这个malloc开创的空间,而malloc的首地址便是buffer的首地址,malloc则是如图中所示,开创8个int类型的空间。
    这里写图片描述
    举例2
    如上图所示:
    二维指针buffer 所指的对象其实是一个集合,而这个集合里面装的是buffer1,buffer2,buffer3,而buffer1,buffer2,buffer3则是分别指向malloc的指针。

    举例3:
    运用malloc开辟一个8*8的int类型的空间,并对其随机赋值。

    int i = 0, k = 0, j = 0;
        int** buffer = (int**)malloc(8 * sizeof(int*));
    //定义**buffer指向malloc,而malloc开辟了8个int类型空间;
        for (i = 0; i < 8; i++)
        {
            buffer[i] = (int*)malloc(8 * sizeof(int));
    //buffer集合下的指针buffer,让malloc开辟了8个int类型空间。ps:因为只有int类型,才能对buffer赋值
            for (k = 0; k < 8; k++)
            {
    
                buffer[i][k] = rand() % 100 + 1;
            //赋值
            }
    
        }

    值得注意的是,因为** buffer是二维指针,并且指向malloc,因此我们需要一层一层的对它进行解封。

    展开全文
  • malloc的用法及其用法意义

    千次阅读 2018-07-27 22:58:33
    函数原型:void *malloc(unsigned int num_bytes); //分配长度为num_bytes字节的内存块  返回值是void指针,void* 表示未确定类型的指针,void *可以指向任何类型的数据,更明确的说是指申请内存空间时还不...
  • 思考: 在C语言中我们向操作系统请求malloc内存空间地址是连续的吗??? 测试 1 每次申请一块内存空间 void *a1 = malloc(1); void *a2 = malloc(2); printf("%p\n",a ); printf("%p\n", ...
  • malloc

    千次阅读 2018-07-13 11:05:53
    因为链表需要malloc-free它不像数组天生有内存,它需要分配。     关于STM32能否使用malloc申请动态内存的问题 考察1: 参考:https://blog.csdn.net/c12345423/article/details/53004465 首先,malloc( )...
  • malloc函数详解

    万次阅读 多人点赞 2009-12-08 11:14:00
    一、原型:extern void *malloc(unsigned int num_bytes);头文件:#include 或 #include (注意:alloc.h 与 malloc.h 的内容是完全一致的。)功能:分配长度为num_bytes字节的内存块说明:如果分配成功则返回指向被...
  • malloc函数

    千次阅读 多人点赞 2016-12-02 23:54:06
    malloc
  • malloc详解

    2019-09-17 20:26:39
    具体问题是这样的,首先malloc申请一块内存,但使用时比实际的大一个字节,比如我申请了52个字节,使用了53个或者申请50个使用了51个,然后我发现的现象是当我申请了52个字节使用了53个字节的时候,程序肯定会挂掉,...
  • new和malloc区别和malloc详解

    万次阅读 多人点赞 2018-07-05 18:32:28
    参考:https://www.cnblogs.com/huhuuu/archive/2013/11/19/3432371.htmlhttps://blog.csdn.net/chance_wang/article/details/1609081一、区别其实在使用的大...1、malloc与free是c++/c语言的标准函数,new/delete...
  • malloc 底层实现

    千次阅读 2018-03-13 01:19:48
    malloc 又称显示动态存储器分配器,动态存储器分配器维护着一个进程的虚拟存储器区域,称为堆。 我们假设堆紧接着未初始化.bss段后开始,并向上生长,对于每个进程,由内核维护着堆顶(brk —- break) 分配器将堆...
  • malloc和Free 工作原理

    千次阅读 多人点赞 2011-06-27 15:07:00
    malloc原型:extern void *malloc(unsigned int num_bytes);用法:#include 或#include功能:分配长度为num_bytes字节的内存块说明:如果分配成功则返回指向被分配内存的指针,否则返回空指针NULL。当内存不再使用时...
  • malloc函数实现原理!

    万次阅读 多人点赞 2016-12-03 12:37:54
    任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间,并且在不再使用时可以通过free释放掉。但是,许多程序员对malloc背后的事情并不熟悉,许多人甚至把malloc当做操作系统所...
  • malloc的实现源码

    2017-08-03 00:51:15
    特别是在BootLoader或者单片机开发过程中,想要实现malloc、free、realloc等函数时,只需要将压缩包里的malloc.c和malloc.h拷贝到你的工程的同一个目录下,编译链接进去即可。压缩包里的test.c提供了一个使用示例供...
  • malloc内存分配详解

    千次阅读 2015-09-21 16:57:57
    这里的存储分配程序,讲的就是标准库中malloc函数的实现原理。首先要了解针对malloc的内存存储结构。malloc不像全局变量一样,不是在编译器编译的时候就会分配内存空间,而是在调用到malloc函数时才会分配空间。有时...
  • 理解 glibc malloc:主流用户态内存分配器实现原理

    万次阅读 热门讨论 2016-07-21 23:39:14
    本篇文章主要完成了对《Understanding glibc malloc》的翻译工作。限于本人翻译水平与专业技术水平(纯粹为了了解内存分配而翻),本文章必定会有很多不足之处,请大家见谅,也欢迎大家的指正! 联系邮箱:...
1 2 3 4 5 ... 20
收藏数 425,339
精华内容 170,135
关键字:

malloc