精华内容
下载资源
问答
  • LwIP 之五 详解动态内存管理 内存堆(mem.c/h)

    千次阅读 多人点赞 2018-05-13 11:24:56
    LwIP为了能够灵活的使用内存,为使用者提供两种简单却又高效的动态内存管理机制:动态内存堆管理(heap)、动态内存池管理(pool)。这两中内存管理策略的实现分别对应着源码文件mem.c/h和memp.c/h。   其中,...

    写在前面

      目前网上有很多介绍LwIP内存的文章,但是绝大多数都不够详细,甚至很多介绍都是错误的!无论是代码的说明还是给出的图例,都欠佳!下面就从源代码,到图例详细进行说明。
      目前,网络上多数文章所使用的LwIP版本为1.4.1。最新版本为2.0.3。从1.4.1到2.0.3(貌似从2.0.0开始),LwIP的源码有了一定的变化,甚至于源码的文件结构也不一样,内部的一些实现源文件也被更新和替换了。

    简介

      对于嵌入式开发来说,内存管理及使用是至关重要的,内存的使用多少、内存泄漏等时刻需要注意!合理的内存管理策略将从根本上决定内存分配和回收效率,最终决定系统的整体性能。LwIP为了能够灵活的使用内存,为使用者提供两种简单却又高效的动态内存管理机制:***动态内存堆管理(heap)、动态内存池管理(pool)***。这两中内存管理策略的实现分别对应着源码文件mem.c/hmemp.c/h
      其中,***动态内存池管理(heap)***又可以分为两种: C 运行时库自带的内存分配策略、LwIP自己实现的内存堆分配策略。这两者的选择需要通过宏值MEM_LIBC_MALLOC来选择,且二者只能选择其一。
      其次,LwIP在自己的内存堆和内存池具体实现上也比较灵活。内存池可有由内存堆实现,反之,内存堆也可以有内存池实现。通过宏值MEM_USE_POOLS和MEMP_MEM_MALLOC来选择,且二者只能选择其一。

    内存堆和内存池

      动态内存堆分配策略原理就是在一个事先定义好大小的内存块中进行管理,其内存分配的策略是采用最快合适( First Fit)方式,只要找到一个比所请求的内存大的空闲块,就从中切割出合适的块,并把剩余的部分返回到动态内存堆中。内存的释放时,重新将申请到的内存返回堆中。
      其优点就是内存浪费小,比较简单,适合用于小内存的管理,其缺点就是如果频繁的动态分配和释放,可能会造成严重的内存碎片,如果在碎片情况严重的话,可能会导致内存分配不成功。

    这其中也有个问题,就是内存合并问题。因为内存堆的管理通常为链表的形式进行管理。可选择将小的链表节点(较小的内存)进行合并。

      内存池的特点是预先开辟多组固定大小的内存块组织成链表,实现简单,分配和回收速度快,不会产生内存碎片,但是大小固定,并且需要预估算准确。

    内存对齐

      一般来说,每一种处理器都会有自己的内存对齐要求,这样做的目的很大程度上是为了处理器读取内存数据的效率,且与对应硬件上的设计也有很大的关系。LwIP中,对于内存的操作函数都用到了内存对齐。

      在LwIP中,用户需要处理一个重要的部分sys_arch。具体可以参见另一片博文。整个arch框架中,就包含了内存对其这一块的配置:

    /** Allocates a memory buffer of specified size that is of sufficient size to align
     * its start address using LWIP_MEM_ALIGN.
     * You can declare your own version here e.g. to enforce alignment without adding
     * trailing padding bytes (see LWIP_MEM_ALIGN_BUFFER) or your own section placement
     * requirements.\n
     * e.g. if you use gcc and need 32 bit alignment:\n
     * \#define LWIP_DECLARE_MEMORY_ALIGNED(variable_name, size) u8_t variable_name[size] \_\_attribute\_\_((aligned(4)))\n
     * or more portable:\n
     * \#define LWIP_DECLARE_MEMORY_ALIGNED(variable_name, size) u32_t variable_name[(size + sizeof(u32_t) - 1) / sizeof(u32_t)]
     */
     /* 定义全局数组作为内存堆的内存,LwIP就是实现的如何管理这块内存的。这块内存时经过对其操作的 */
    #ifndef LWIP_DECLARE_MEMORY_ALIGNED
    #define LWIP_DECLARE_MEMORY_ALIGNED(variable_name, size) u8_t variable_name[LWIP_MEM_ALIGN_BUFFER(size)]
    #endif
    
    /** Calculate memory size for an aligned buffer - returns the next highest
     * multiple of MEM_ALIGNMENT (e.g. LWIP_MEM_ALIGN_SIZE(3) and
     * LWIP_MEM_ALIGN_SIZE(4) will both yield 4 for MEM_ALIGNMENT == 4).
     */
     /* 数据占用空间大小对齐计算 */
    #ifndef LWIP_MEM_ALIGN_SIZE
    #define LWIP_MEM_ALIGN_SIZE(size) (((size) + MEM_ALIGNMENT - 1U) & ~(MEM_ALIGNMENT-1U))
    #endif
    
    /** Calculate safe memory size for an aligned buffer when using an unaligned
     * type as storage. This includes a safety-margin on (MEM_ALIGNMENT - 1) at the
     * start (e.g. if buffer is u8_t[] and actual data will be u32_t*)
     */
    #ifndef LWIP_MEM_ALIGN_BUFFER
    #define LWIP_MEM_ALIGN_BUFFER(size) (((size) + MEM_ALIGNMENT - 1U))
    #endif
    
    /** Align a memory pointer to the alignment defined by MEM_ALIGNMENT
     * so that ADDR % MEM_ALIGNMENT == 0
     */
     /* 数据起始地址对齐 */
    #ifndef LWIP_MEM_ALIGN
    #define LWIP_MEM_ALIGN(addr) ((void *)(((mem_ptr_t)(addr) + MEM_ALIGNMENT - 1) & ~(mem_ptr_t)(MEM_ALIGNMENT-1)))
    #endif
    

    为什么要对齐

      这个其实和各种处理器的硬件设计息息相关,具体可以参见该博文《为什么要内存对齐》。

    对齐的本质

      首先,这里所说的对其是指 2k2^k 字节的对其(其中k取0,1,2,3…正整数)。如果你纠结于什么3字节的对齐等。这里不适用! 在计算机中,所有的数据都是二进制!所谓对齐,就是将一串二进制的最后N位抹成 0。具体几位呢?这就是根据自己要对齐的字节数来定了。1字节对齐时N == 0;2 字节对齐时N == 1,4 字节对齐时N == 2;以此类推。对齐字节数是根据硬件平台来的,一般不会随便来。
      再一点就是,对齐的抹 0,是需要向上取整的。为什么要向上取整呢?如果网下取整,那么,实际返回的大小就比用户实际需要的要小了。这可就麻烦了,甚至由于不满足自己需要的大小,申请的这块内存都没法使用!

    关于任意自己对齐,可以参考一下文章:
      1. 实现任意字节对齐的内存分配和释放
      2. 任意字节对齐的内存分配和释放

    LWIP_MEM_ALIGN_SIZE(size)

      这个宏的作用就是将指定的大小处理成对其后大小,对其的大小由用户提供宏值MEM_ALIGNMENT来决定。其中size为想要分配的大小。下面来看看这个宏:

    • ~(MEM_ALIGNMENT-1U): 这一步就是按照对应的对齐字节数据,将二进制的最后最后几位置为 0。例如,MEM_ALIGNMENT为4 ,则该步就将后2位置为了 0。自己可以转为二进制计算一下!
    • ((size) + MEM_ALIGNMENT - 1U): 这里其实就是为了在处理时,能够向上取整。

      下面是针对其中不同值得计算结果(MEM_ALIGNMENT表示要对其的字节,size 为想要的大小,ALIG表示对齐后实际的大小)

     MEM_ALIGNMENT = 1       MEM_ALIGNMENT = 2       MEM_ALIGNMENT = 4       MEM_ALIGNMENT = 8
    size = 1   ALIG = 1     size = 1   ALIG = 2     size = 1   ALIG = 4     size = 1   ALIG = 8
    size = 2   ALIG = 2     size = 2   ALIG = 2     size = 2   ALIG = 4     size = 2   ALIG = 8
    size = 3   ALIG = 3     size = 3   ALIG = 4     size = 3   ALIG = 4     size = 3   ALIG = 8
    size = 4   ALIG = 4     size = 4   ALIG = 4     size = 4   ALIG = 4     size = 4   ALIG = 8
    size = 5   ALIG = 5     size = 5   ALIG = 6     size = 5   ALIG = 8     size = 5   ALIG = 8
    size = 6   ALIG = 6     size = 6   ALIG = 6     size = 6   ALIG = 8     size = 6   ALIG = 8
    size = 7   ALIG = 7     size = 7   ALIG = 8     size = 7   ALIG = 8     size = 7   ALIG = 8
    size = 8   ALIG = 8     size = 8   ALIG = 8     size = 8   ALIG = 8     size = 8   ALIG = 8
    size = 9   ALIG = 9     size = 9   ALIG = 10    size = 9   ALIG = 12    size = 9   ALIG = 16
    size = 10  ALIG = 10    size = 10  ALIG = 10    size = 10  ALIG = 12    size = 10  ALIG = 16
    size = 11  ALIG = 11    size = 11  ALIG = 12    size = 11  ALIG = 12    size = 11  ALIG = 16
    size = 12  ALIG = 12    size = 12  ALIG = 12    size = 12  ALIG = 12    size = 12  ALIG = 16
    size = 13  ALIG = 13    size = 13  ALIG = 14    size = 13  ALIG = 16    size = 13  ALIG = 16
    size = 14  ALIG = 14    size = 14  ALIG = 14    size = 14  ALIG = 16    size = 14  ALIG = 16
    size = 15  ALIG = 15    size = 15  ALIG = 16    size = 15  ALIG = 16    size = 15  ALIG = 16
    size = 16  ALIG = 16    size = 16  ALIG = 16    size = 16  ALIG = 16    size = 16  ALIG = 16
    size = 17  ALIG = 17    size = 17  ALIG = 18    size = 17  ALIG = 20    size = 17  ALIG = 24
    size = 18  ALIG = 18    size = 18  ALIG = 18    size = 18  ALIG = 20    size = 18  ALIG = 24
    size = 19  ALIG = 19    size = 19  ALIG = 20    size = 19  ALIG = 20    size = 19  ALIG = 24
    size = 20  ALIG = 20    size = 20  ALIG = 20    size = 20  ALIG = 20    size = 20  ALIG = 24
    

    LWIP_MEM_ALIGN(addr)

      这个宏用来处理数据起始地址对齐。其处理方式与上面的数据大小的处理没有任何区别。关于数据类型在arch.h的开头部分有定义,这里有个文件stdint.h需要注意一下!在某写平台,可能没有该文件,需要用户自己来添加。

    #if !LWIP_NO_STDINT_H
    #include <stdint.h>
    typedef uint8_t   u8_t;
    typedef int8_t    s8_t;
    typedef uint16_t  u16_t;
    typedef int16_t   s16_t;
    typedef uint32_t  u32_t;
    typedef int32_t   s32_t;
    typedef uintptr_t mem_ptr_t;   /* 这个通常为一个 unsigned int 类型 */
    #endif
    

    LwIP中宏配置及使用

      LwIP中,内存的选择是通过以下这几个宏值来决定的,根据用户对宏值的定义值来判断使用那种内存管理策略,具体如下:

    • MEM_LIBC_MALLOC: 该宏值定义是否使用C 运行时库自带的内存分配策略。该值默认情况下为0,表示不使用C 运行时库自带的内存分配策略。即默认使用LwIP提供的内存堆分配策略。
        如果要使用C运行时库自带的分配策略,则需要把该值定义为 1。此时,宏值MEM_USE_POOLS必然不能为 1。
    • MEMP_MEM_MALLOC: 该宏值定义是否使用lwip内存堆分配策略实现内存池分配(即:要从内存池中获取内存时,实际是从内存堆中分配)。默认情况下为 0,表示不从内存堆中分配,内存池为独立一块内存实现。MEM_USE_POOLS只能选择其一
    • MEM_USE_POOLS:该宏值定时是否使用lwip内存池分配策略实现内存堆的分配(即:要从内存堆中获取内存时,实际是从内存池中分配)。默认情况下为 0,表示不使用。MEMP_MEM_MALLOC只能选择其一
        要使用内存池的方式,则需要将该宏值定义为 1,且MEMP_MEM_MALLOC必须为 0,除此之外还需要做一下处理:
    1. MEMP_USE_CUSTOM_POOLS == 1
    2. 新建文件lwippools.h,并且在该文件中定义如下内存池(想多定义几个时,必须在宏LWIP_MALLOC_MEMPOOL_START和LWIP_MALLOC_MEMPOOL_END之间添加):
    LWIP_MALLOC_MEMPOOL(20, 256)
    LWIP_MALLOC_MEMPOOL(10, 512)
    LWIP_MALLOC_MEMPOOL(5, 1512)
    LWIP_MALLOC_MEMPOOL_END
    

      根据宏值的不同,mem.c/h会部分有效,下面简单看看mem.c文件的结构:

    #if MEM_LIBC_MALLOC
    /* 这里表示使用C库时的部分 */
    #elif MEM_USE_POOLS
    /* 这里表示使用内存池方式实现的内存堆函数 */
    #else
    /* 使用内存堆实现分配函数 */
    #endif
    

    而对于memp.c/h来说,就没这么复杂了。因为该文件就是独立实现内存池的管理策略的,无论宏值怎么配置,里面的函数就是那些。唯一有影响的宏值是MEMP_MEM_MALLOC后面会说明。
      总结来说,无论宏值怎么配置,LwIP都有两种内存管理策略:内存堆内存池

    • 内存堆: 可以来自C库,也可以使用LwIP自己实现的。
    • 内存池: 可以单独实现,也可以从内存堆中分配实现。

      上面说了如何进行配置,那么在LwIP内部是如何做到兼容以上的灵活配置的呢?其实很简单,LwIP内部全部使用统一的内存分配函数,只是在不同模式下,对相应的函数进行了重新定义,具体函数如下:

    • void mem_init(void):内存堆初始化函数,主要设置内存堆的起始地址,以及初始化空闲列表,lwip初始化时调用,内部接口。配置不同时,其实现也不同(可能为空)
    • void *mem_trim(void *mem, mem_size_t size): 减小mem_malloc所分配的内存。mem为申请到的内存的地址,size为新的大小。

    与标准C函数realloc不同,该函数只能缩减分配内存

    • void *mem_malloc(mem_size_t size):申请分配内存,size为需要申请的内存字节数,返回值为最新分配的内存块的数据地址。
    • void *mem_calloc(mem_size_t count, mem_size_t size):是对mem_malloc()函数的简单包装,两个入口参数,count为元素的总个数,size为每个元素大小,两个参数的乘积就是实际要分配的内存空间的大小。mem_malloc()不同的是它会把动态分配的内存清零
    • void mem_free(void *mem):内存释放函数,mem前面申请到的内存时分配得地址。

    这样,无论用户选择了什么配置方式,对于LwIP内部来说,函数全都是一个样的!下面,详细说明每种方式下,以上函数是怎么实现的。

    C库分配方式

      上面已经说了要使用该方式如何进行配置,下面结合源码看看,如果用户选择了该方式,LwIP内部是如何处理的。该部分对应的源码文件为mem.c
      首先,如果用户选择了该方式,那么内存处理函数void mem_init(void)和void* mem_trim(void *mem, mem_size_t size)将没有实际的实现内容,既然选择了C库策略,此时也必然没法实现。
      接下来我们将看到如下代码:

    /* in case C library malloc() needs extra protection,
     * allow these defines to be overridden.
     */
    #ifndef mem_clib_free
    #define mem_clib_free free
    #endif
    #ifndef mem_clib_malloc
    #define mem_clib_malloc malloc
    #endif
    #ifndef mem_clib_calloc
    #define mem_clib_calloc calloc
    #endif
    
    #if LWIP_STATS && MEM_STATS
    #define MEM_LIBC_STATSHELPER_SIZE LWIP_MEM_ALIGN_SIZE(sizeof(mem_size_t))
    #else
    #define MEM_LIBC_STATSHELPER_SIZE 0
    #endif
    

    这里将C库的标准内存处理函数进行了重定义,没啥太大作用,就是为了后面使用的方便。下面以void * mem_malloc(mem_size_t size)为例看看以上宏值的用法(其他函数类似,注意:有几个函数在文件的最末尾统一处理了):

    void *
    mem_malloc(mem_size_t size)
    {
      /* 这里就是调用的malloc有木有! */
      void* ret = mem_clib_malloc(size + MEM_LIBC_STATSHELPER_SIZE);
      if (ret == NULL) {  /* 分配失败 */
        MEM_STATS_INC(err);
      } else { /* 需要重点注意的就是,内存的对其问题,下面就是处理对其的。然后直接返回申请到的内存地址。 */
        LWIP_ASSERT("malloc() must return aligned memory", LWIP_MEM_ALIGN(ret) == ret);
    #if LWIP_STATS && MEM_STATS
        *(mem_size_t*)ret = size;
        ret = (u8_t*)ret + MEM_LIBC_STATSHELPER_SIZE;
        MEM_STATS_INC_USED(used, size);
    #endif
      }
      return ret;
    }
    

      最后,使用C库内存处理策略时,LwIP的处理就是这么简单,也没啥需要特殊注意的地方!如果说非得注意点啥,就是一旦选择了该种模式,内存池的配置问题。

    LwIP内存堆

      上面已经说了要使用该方式如何进行配置,下面结合源码看看,如果用户选择了该方式,LwIP内部是如何处理的。该部分对应的源码文件为mem.c

    用内存池实现

      首先,LwIP会判断用户是否定义了宏值MEM_USE_POOLS,如果定义了该宏值,表示内存堆的内存来自于内存池,需要调用内存池的相关函数来处理内存。
      既然是调用内存堆中的各函数,那么这边的实现也相对简单。这与上面的调用C库的各函数没啥太大区别,至少在处理逻辑上是一致的,当然,由于内存池的实现上的原因,该部分看着还是挺复杂的!下面仍旧以函数void *mem_malloc(mem_size_t size)来看看LwIP是如何处理的。

    void *
    mem_malloc(mem_size_t size)
    {
      void *ret;
      struct memp_malloc_helper *element = NULL;
      memp_t poolnr;
      mem_size_t required_size = size + LWIP_MEM_ALIGN_SIZE(sizeof(struct memp_malloc_helper));
    
      for (poolnr = MEMP_POOL_FIRST; poolnr <= MEMP_POOL_LAST; poolnr = (memp_t)(poolnr + 1)) {
        /* is this pool big enough to hold an element of the required size
           plus a struct memp_malloc_helper that saves the pool this element came from? */
        if (required_size <= memp_pools[poolnr]->size) {
          element = (struct memp_malloc_helper*)memp_malloc(poolnr);
          if (element == NULL) {
            /* No need to DEBUGF or ASSERT: This error is already taken care of in memp.c */
    #if MEM_USE_POOLS_TRY_BIGGER_POOL
            /** Try a bigger pool if this one is empty! */
            if (poolnr < MEMP_POOL_LAST) {
              continue;
            }
    #endif /* MEM_USE_POOLS_TRY_BIGGER_POOL */
            MEM_STATS_INC(err);
            return NULL;
          }
          break;
        }
      }
      if (poolnr > MEMP_POOL_LAST) {
        LWIP_ASSERT("mem_malloc(): no pool is that big!", 0);
        MEM_STATS_INC(err);
        return NULL;
      }
    
      /* save the pool number this element came from */
      element->poolnr = poolnr;
      /* and return a pointer to the memory directly after the struct memp_malloc_helper */
      ret = (u8_t*)element + LWIP_MEM_ALIGN_SIZE(sizeof(struct memp_malloc_helper));
    
    #if MEMP_OVERFLOW_CHECK || (LWIP_STATS && MEM_STATS)
      /* truncating to u16_t is safe because struct memp_desc::size is u16_t */
      element->size = (u16_t)size;
      MEM_STATS_INC_USED(used, element->size);
    #endif /* MEMP_OVERFLOW_CHECK || (LWIP_STATS && MEM_STATS) */
    #if MEMP_OVERFLOW_CHECK
      /* initialize unused memory (diff between requested size and selected pool's size) */
      memset((u8_t*)ret + size, 0xcd, memp_pools[poolnr]->size - size);
    #endif /* MEMP_OVERFLOW_CHECK */
      return ret;
    }
    

      该部分许多地方需要看看后面的内存池。再次不做过多深入说明。

    独立实现内存堆

      如果没有定义宏值MEM_USE_POOLS,那么LwIP提供了一套独立实现的内存堆处理接口。
      内存堆的本质是对一个事先定义好的内存块进行合理有效的组织和管理。主要用于任意大小的内存分配,实现较复杂,分配需要查找,回收需要合并,容易产生内存碎片,需要合理估算内存堆的总大小。LwIP使用类似于链表的结构来组织管理堆内存。节点的结构如下(在该部分的源码实现中,第一部分的代码便是以下结构体):

    struct mem {
      /** index (-> ram[next]) of the next struct */
      mem_size_t next;    /* 下一个内存块的索引,不是指针,而是个索引号 */
      /** index (-> ram[prev]) of the previous struct */
      mem_size_t prev;    /* 前一个内存块的索引,不是指针,而是个索引号 */
      /** 1: this area is used; 0: this area is unused */
      u8_t used;          /* 此内存快是否被用。1使用、0 未使用 */
    };
    

      LwIP的内存堆实现中,分配的内存块有个最小大小的限制,要求请求的分配大小不能小于 MIN_SIZE,默认 MIN_SIZE为 12 字节。所以在该部分实现中,我看到的第二部分便是如下结构(第一部分是链表结构体):

    /** All allocated blocks will be MIN_SIZE bytes big, at least!
     * MIN_SIZE can be overridden to suit your needs. Smaller values save space,
     * larger values could prevent too small blocks to fragment the RAM too much. */
    #ifndef MIN_SIZE
    #define MIN_SIZE             12
    #endif /* MIN_SIZE */
    /* some alignment macros: we define them here for better source code layout */
    #define MIN_SIZE_ALIGNED     LWIP_MEM_ALIGN_SIZE(MIN_SIZE)				/* 最小大小做对齐处理,后面均用对齐后的该宏值 */
    #define SIZEOF_STRUCT_MEM    LWIP_MEM_ALIGN_SIZE(sizeof(struct mem))	/* 内存块头大小做对齐处理,后面均用对齐后的该宏值 */
    #define MEM_SIZE_ALIGNED     LWIP_MEM_ALIGN_SIZE(MEM_SIZE)				/* 用户定义的堆大小做对齐处理,后面均用对齐后的该宏值 */
    

    这就有一个问题,为什么默认值是12呢?因为这正好是2个sizeof(struct mem)的长度。为什么是2个sizeof(struct mem)。后面再说内存堆的定义及初始化时,我们会详细说明。
      接下来就是使用宏值LWIP_DECLARE_MEMORY_ALIGNED定义内存堆所使用的内存空间的了,这个宏值在上面一节由介绍,具体如下。从下面的定义中,我们可以看到***内存堆空间就是定义的一个名为ram_heap,大小为MEM_SIZE_ALIGNED + (2U*SIZEOF_STRUCT_MEM)的数组***。内存堆管理的具体实现,就是实现如何管理使用这个数组!

    /** If you want to relocate the heap to external memory, simply define
     * LWIP_RAM_HEAP_POINTER as a void-pointer to that location.
     * If so, make sure the memory at that location is big enough (see below on
     * how that space is calculated). */
    #ifndef LWIP_RAM_HEAP_POINTER
    /** the heap. we need one struct mem at the end and some room for alignment */
    /* 下面用全局变量的形式(名字为ram_heap),定义堆内存空间。并且由于对齐问题,不能直接使用数组名。因此,后面再用时全部处理为指针 */
    LWIP_DECLARE_MEMORY_ALIGNED(ram_heap, MEM_SIZE_ALIGNED + (2U*SIZEOF_STRUCT_MEM));
    #define LWIP_RAM_HEAP_POINTER ram_heap
    #endif /* LWIP_RAM_HEAP_POINTER */
    

    注意:这里的大小多加了两个SIZEOF_STRUCT_MEM

      在定义完内存空间后,接下来就是一些为了管理内存堆,而定义的结构性的全局变量的定义。再后面是一些内存保护相关的宏,这里不具体说明。下面看看,为了管理内存堆,LwIP都定义了那些变量。

    /** pointer to the heap (ram_heap): for alignment, ram is now a pointer instead of an array */
    static u8_t *ram;		/* 指向对齐后的内存堆的地址。由于对齐问题,不能直接使用数组名上面的数组名。*/
    /** the last entry, always unused! */
    static struct mem *ram_end;		/* 指向对齐后的内存堆的最后一个内存块。*/
    /** pointer to the lowest free block, this is used for faster search */
    static struct mem *lfree;		/* 指向已被释放的索引号最小的内存块(内存堆最前面的已被释放的)。*/
    

    下面,就结合各接口函数来说说LwIP对内存堆的管理是如何实现的。先说第一个函数void mem_init(void)。先好看看源码,具体说明见其中的注释部分:

    void
    mem_init(void)
    {
      struct mem *mem;
    
      LWIP_ASSERT("Sanity check alignment",
        (SIZEOF_STRUCT_MEM & (MEM_ALIGNMENT-1)) == 0);
    
      /* align the heap 对内存堆的地址(全局变量的名)进行对齐。*/
      ram = (u8_t *)LWIP_MEM_ALIGN(LWIP_RAM_HEAP_POINTER);
      /* initialize the start of the heap 建立第一个内存块,内存块由内存块头+空间组成。 */
      mem = (struct mem *)(void *)ram;
      mem->next = MEM_SIZE_ALIGNED;		/* 下一个内存块不存在,因此指向内存堆的结束 */
      mem->prev = 0;					/* 前一个内存块就是它自己,因为这是第一个内存块 */
      mem->used = 0;					/* 第一个内存块没有被使用 */
      /* initialize the end of the heap 建立最后一个内存块 */
      ram_end = (struct mem *)(void *)&ram[MEM_SIZE_ALIGNED];
      ram_end->used = 1;				/* 最后一个内存块被使用。因为其后面没有可用空间,必须标记为已被使用 */
      ram_end->next = MEM_SIZE_ALIGNED;/* 下一个不存在,因此指向内存堆的结束 */
      ram_end->prev = MEM_SIZE_ALIGNED;/* 前一个不存在,因此指向内存堆的结束 */
    
      /* initialize the lowest-free pointer to the start of the heap */
      lfree = (struct mem *)(void *)ram;	/* 已释放的索引最小的内存块就是上面建立的第一个内存块。 */
    
      MEM_STATS_AVAIL(avail, MEM_SIZE_ALIGNED);
      /* 这里建立一个互斥信号量,主要是用来进行内存的申请、释放的保护 */
      if (sys_mutex_new(&mem_mutex) != ERR_OK) {
        LWIP_ASSERT("failed to create mem_mutex", 0);
      }
    }
    

      经过初始化,LwIP将内存堆划分为了如下格式:
    MemInit
    上图中已经非常详细的给出了从定义到初始化后,详细的内存堆的结构!在整个内存堆的开头和结尾,各有一个内存块头。开头的内存块头用来定义第一个内存块(也就是整个内存堆只有一个内存块),最后一个内存块头用来标识内存块的结尾。 看图的时候,结合源码和上一节的内存对齐部分。因为在上图中,到处都是对齐!
      接下来,在看看函数void *mem_malloc(mem_size_t size)。仍旧是先看源代码,具体语句在源码中都有注释,对于源码中,保护部分暂不作说明!

    void *
    mem_malloc(mem_size_t size)
    {
      mem_size_t ptr, ptr2;
      struct mem *mem, *mem2;
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
      u8_t local_mem_free_count = 0;
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
      LWIP_MEM_ALLOC_DECL_PROTECT();
      /* 第一步:参数检查 */
      if (size == 0) {
        return NULL;
      }
    
      /* Expand the size of the allocated memory region so that we can
         adjust for alignment. */
      size = LWIP_MEM_ALIGN_SIZE(size);
    
      if (size < MIN_SIZE_ALIGNED) {  /* 这里处理 最小内存块的限制问题 不能小于前面定义的宏值 */
        /* every data block must be at least MIN_SIZE_ALIGNED long */
        size = MIN_SIZE_ALIGNED;
      }
    
      if (size > MEM_SIZE_ALIGNED) {
        return NULL;
      }
      /* 第二步:从内存堆中划分需要的内存块 */
      /* protect the heap from concurrent access */
      sys_mutex_lock(&mem_mutex);
      LWIP_MEM_ALLOC_PROTECT();
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
      /* run as long as a mem_free disturbed mem_malloc or mem_trim */
      do {
        local_mem_free_count = 0;
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
    
        /* Scan through the heap searching for a free block that is big enough,
         * beginning with the lowest free block.
         */
        for (ptr = (mem_size_t)((u8_t *)lfree - ram); ptr < MEM_SIZE_ALIGNED - size;
             ptr = ((struct mem *)(void *)&ram[ptr])->next) {/* 遍历内存堆,注意遍历时的开始地址:永远从最前面开始找。因为lfree指向已释放的最靠前的内存块 */
          mem = (struct mem *)(void *)&ram[ptr];	/* 内存块的头 */
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
          mem_free_count = 0;
          LWIP_MEM_ALLOC_UNPROTECT();
          /* allow mem_free or mem_trim to run */
          LWIP_MEM_ALLOC_PROTECT();
          if (mem_free_count != 0) {
            /* If mem_free or mem_trim have run, we have to restart since they
               could have altered our current struct mem. */
            local_mem_free_count = 1;
            break;
          }
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
    
          if ((!mem->used) &&
              (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size) { /* 空间大小必须排除内存块头大小 */
            /* mem is not used and at least perfect fit is possible:
             * mem->next - (ptr + SIZEOF_STRUCT_MEM) gives us the 'user data size' of mem */
    
            if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >= (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED)) { /* 这个地方需要判断 最后一个内存块头和最小大小 */
              /* (in addition to the above, we test if another struct mem (SIZEOF_STRUCT_MEM) containing
               * at least MIN_SIZE_ALIGNED of data also fits in the 'user data space' of 'mem')
               * -> split large block, create empty remainder,
               * remainder must be large enough to contain MIN_SIZE_ALIGNED data: if
               * mem->next - (ptr + (2*SIZEOF_STRUCT_MEM)) == size,
               * struct mem would fit in but no data between mem2 and mem2->next
               * @todo we could leave out MIN_SIZE_ALIGNED. We would create an empty
               *       region that couldn't hold data, but when mem->next gets freed,
               *       the 2 regions would be combined, resulting in more free memory
               */
               /* 上面注释一大堆,主要就是说,剩余内存可能连一个内存块的头都放不下了,这个时候就没法新建空内存块。其索引也就不能移动 */
              ptr2 = ptr + SIZEOF_STRUCT_MEM + size;   /* 指向申请后的位置,即:建立下一个未使用的内存块的头部。即:插入一个新空内存块 */
              /* create mem2 struct */
              mem2 = (struct mem *)(void *)&ram[ptr2];
              mem2->used = 0;
              mem2->next = mem->next;	/* */
              mem2->prev = ptr;			/* 空闲内存块的前一个指向上面分配的内存块 */
              /* and insert it between mem and mem->next 前一个内存块指向上面建立的空闲内存块 */
              mem->next = ptr2;
              mem->used = 1;		/* 将当前分配的内存块标记为 已使用 */
    
              if (mem2->next != MEM_SIZE_ALIGNED) {/* 中间节点 建立后,原来的下一个节点的前一个要指向 新建的空节点 */
                ((struct mem *)(void *)&ram[mem2->next])->prev = ptr2;
              }
              MEM_STATS_INC_USED(used, (size + SIZEOF_STRUCT_MEM));
            } else {/* 进入了这一步,则表示内存块太小了,即:生产的碎片 */
              /* (a mem2 struct does no fit into the user data space of mem and mem->next will always
               * be used at this point: if not we have 2 unused structs in a row, plug_holes should have
               * take care of this).
               * -> near fit or exact fit: do not split, no mem2 creation
               * also can't move mem->next directly behind mem, since mem->next
               * will always be used at this point!
               */
              mem->used = 1;
              MEM_STATS_INC_USED(used, mem->next - (mem_size_t)((u8_t *)mem - ram));
            }
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
    mem_malloc_adjust_lfree:
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
            if (mem == lfree) {		/* 这里处理:当分配出去的内存正好是lfree时,因为该内存块已经被分配出去了,必须修改lfree的指向下一个最其前面的已释放的内存块*/
              struct mem *cur = lfree;
              /* Find next free block after mem and update lowest free pointer */
              while (cur->used && cur != ram_end) { /* 只要内存块已使用且没到结尾,则继续往后找 */
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
                mem_free_count = 0;
                LWIP_MEM_ALLOC_UNPROTECT();
                /* prevent high interrupt latency... */
                LWIP_MEM_ALLOC_PROTECT();
                if (mem_free_count != 0) {
                  /* If mem_free or mem_trim have run, we have to restart since they
                     could have altered our current struct mem or lfree. */
                  goto mem_malloc_adjust_lfree;
                }
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
                cur = (struct mem *)(void *)&ram[cur->next];		/* 下一个内存块 */
              }
              lfree = cur; /* 指向找到的 第一个已释放的内存块。如果上面没有找到,则lfree =    lfree不变 */
              LWIP_ASSERT("mem_malloc: !lfree->used", ((lfree == ram_end) || (!lfree->used)));
            }
            LWIP_MEM_ALLOC_UNPROTECT();
            sys_mutex_unlock(&mem_mutex);
            LWIP_ASSERT("mem_malloc: allocated memory not above ram_end.",
             (mem_ptr_t)mem + SIZEOF_STRUCT_MEM + size <= (mem_ptr_t)ram_end);
            LWIP_ASSERT("mem_malloc: allocated memory properly aligned.",
             ((mem_ptr_t)mem + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT == 0);
            LWIP_ASSERT("mem_malloc: sanity check alignment",
              (((mem_ptr_t)mem) & (MEM_ALIGNMENT-1)) == 0);
    
            return (u8_t *)mem + SIZEOF_STRUCT_MEM;		/* 这里返回 内存块的空间的地址,排除内存块的头 */
          }
        }
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
        /* if we got interrupted by a mem_free, try again */
      } while (local_mem_free_count != 0);
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
      LWIP_DEBUGF(MEM_DEBUG | LWIP_DBG_LEVEL_SERIOUS, ("mem_malloc: could not allocate %"S16_F" bytes\n", (s16_t)size));
      MEM_STATS_INC(err);
      LWIP_MEM_ALLOC_UNPROTECT();
      sys_mutex_unlock(&mem_mutex);
      return NULL;
    }
    

      分配内存的过程,就是从初始化后的内存块中,划分新内存块的过程。新内存块划分完成后,将其标记为已使用,并且新建的空内存块。在划分过程中,需要处理已经被释放的内存块的问题。划分后如下图所示:
    MemMalloc
      首先需要重点注意的就是遍历查找新内存块时的起始位置:ptr = (mem_size_t)((u8_t *)lfree - ram)。前面说过,变量lfree永远指向内存堆中最靠前的那个已经释放的内存块。这也就是意味值,每次总是从整个内存堆的开始的第一个空闲内存块开始找合适的内存块的,即便后面可能有更大的空间!
      这其中有个需要注意的地方:if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >= (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))。这个地方具体是干嘛的呢?看下图(图例不考虑对齐问题):
    MemMalloc2
      接下来一个注意的地方就是if (mem2->next != MEM_SIZE_ALIGNED) { 省略...。这个地方又是干什么用的呢?具体看下图(图例不考虑对齐问题)
    MemMalloc3
      其实上面两个问题,就是针对中间已经释放过的内存块由重新划分时的处理。一旦从释放过的内存块中划分出新的内存后,则可能会导致剩余的内存块有可能充足,也可能不充足,这就是针对以上两个情况!
      最后再看看内存的释放函数,和上面相同,仍旧从源代码说起,具体见注释。

    void
    mem_free(void *rmem)
    {
      struct mem *mem;
      LWIP_MEM_FREE_DECL_PROTECT();
      /* 第一步:检查参数 */
      if (rmem == NULL) {	/* 指针空检查 */
        LWIP_DEBUGF(MEM_DEBUG | LWIP_DBG_TRACE | LWIP_DBG_LEVEL_SERIOUS, ("mem_free(p == NULL) was called.\n"));
        return;
      }
      LWIP_ASSERT("mem_free: sanity check alignment", (((mem_ptr_t)rmem) & (MEM_ALIGNMENT-1)) == 0);
    
      LWIP_ASSERT("mem_free: legal memory", (u8_t *)rmem >= (u8_t *)ram &&
        (u8_t *)rmem < (u8_t *)ram_end);
    
      if ((u8_t *)rmem < (u8_t *)ram || (u8_t *)rmem >= (u8_t *)ram_end) {		/* 检查是否在内存堆范围内 */
        SYS_ARCH_DECL_PROTECT(lev);
        LWIP_DEBUGF(MEM_DEBUG | LWIP_DBG_LEVEL_SEVERE, ("mem_free: illegal memory\n"));
        /* protect mem stats from concurrent access */
        SYS_ARCH_PROTECT(lev);
        MEM_STATS_INC(illegal);
        SYS_ARCH_UNPROTECT(lev);
        return;
      }
      /* 第二步:查找指定的内存块,标记为未使用 */
      /* protect the heap from concurrent access */
      LWIP_MEM_FREE_PROTECT();
      /* Get the corresponding struct mem ... */
      /* cast through void* to get rid of alignment warnings */
      mem = (struct mem *)(void *)((u8_t *)rmem - SIZEOF_STRUCT_MEM);		/* 通过mem_malloc的到的地址是不含 struct mem 的 */
      /* ... which has to be in a used state ... */
      LWIP_ASSERT("mem_free: mem->used", mem->used);
      /* ... and is now unused. */
      mem->used = 0;
      /* 第三步:需要移动全局的释放指针,因为lfree始终指向内存堆中最小索引的那个已经释放的内存块 */
      if (mem < lfree) {
        /* the newly freed struct is now the lowest */
        lfree = mem;
      }
    
      MEM_STATS_DEC_USED(used, mem->next - (mem_size_t)(((u8_t *)mem - ram)));
    
      /* finally, see if prev or next are free also */
      plug_holes(mem);
    #if LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT
      mem_free_count = 1;
    #endif /* LWIP_ALLOW_MEM_FREE_FROM_OTHER_CONTEXT */
      LWIP_MEM_FREE_UNPROTECT();
    }
    

    释放过程非常简单,就是将指定的内存块标记为未使用,其他不做任何处理。唯一处理的一个地方就就是全局变量lfree,必须检查是否为最前面的内存块,释放后如下图:
    MemFree
    内存块释放后,其原先建立的连接关系是不会改变的。
      这部分中还有一个函数:static void plug_holes(struct mem *mem),用来对相邻且未用的内存块进行合并。该函数暂时未使用,这里就不过多说明了!

    LwIP内存池

    见后文 LwIP 之 详解动态内存管理 内存池(memp.c/h)

    展开全文
  • 堆的特性: 必须是完全二叉树 用数组实现 任一结点的值是其子树所有结点的最大值或最小值 ...数据结构中堆与内存堆区的区别 一、数据结构中的堆和栈 堆和栈在数据结构中是两种不同的数据结构。 两者都是数据...

    堆的特性:

    必须是完全二叉树
    用数组实现
    任一结点的值是其子树所有结点的最大值或最小值
    最大值时,称为“最大堆”,也称大根堆;

    在完全二叉树中,任何一个子树的最大值都在这个子树的根结点。
    

    最小值时,称为“最小堆”,也称小根堆。

    在完全二叉树中,任何一个子树的最小值都在这个子树的根结点。
    

    大根堆
    在这里插入图片描述
    小根堆
    在这里插入图片描述
    可以看到,对于**堆(Heap)**这种数据结构,从根节点到任意结点路径上所有的结点都是有序的。

    整理:
    二叉堆

    逻辑上:完全二叉树
    存储上:数组(顺序存储)
    作用:找最值		(优先级队列)
    

    操作:

    1向下调整	*	(建队,删除)
    2建堆
    3向上调整  (插入)
    

    数据结构中堆与内存堆区的区别

    一、数据结构中的堆和栈

       堆和栈在数据结构中是两种不同的数据结构。 两者都是数据项按序排列的数据结构。
    
       栈:像是装数据的桶或者箱子
    
        栈是大家比较熟悉的一种数据结构,它是一种具有后进先出的数据结构,也就是说后存放的先取,
        先存放的后取,这就类似于我们要在取放在箱子底部的东西(放进去比较早的物体),
        我们首先要移开压在它上面的物体(放入比较晚的物体)。
    
       堆:像是一颗倒立的大树
    
       堆是一种经过排序的树形数据结构,每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。
       堆的特点是根节点的值最小(或最大),且根节点的两个树也是一个堆。
       由于堆的这个特性,常用来实现优先队列,堆的存取是随意的,这就如同我们在图书馆的书架上取书,虽然书的摆放是有顺序的,
       但是我们想取任意一本时不必像栈一样,先取出前面所有的书,书架这种机制不同于箱子,我们可以直接取出我们想要的书。
    

    二、内存分配中的堆和栈

       我们现在经常用的并不是数据结构中的堆和栈,之所以说了数据结构中的堆和栈是为了和后面将要说的堆区和栈区区别开来,请大家一定要注意。
       内存中的栈区处于相对较高的地址,以地址的增长方向为上的话,栈地址是向下增长的。
    
       栈中分配局部变量空间,堆区是向上增长的用于分配程序员申请的内存空间。
       另外还有静态区是分配静态变量,全局变量空间的。
       只读区是分配常量和程序代码空间的;以及其他一些分区。
    

    来看一个很经典的例子:

    main.cpp
    
       int a = 0;  全局初始化区
    
       char *p1;  全局未初始化区
    
       main ()
    
       {
    
       int b; 栈
    
       char  s[] = “abc”;栈
    
       char *p2; 栈
    
       char *p3 = “123456”; 123456\0 在常量区,p3 在栈区
    
       static  int c = 0; 全局(静态)初始化区
    
       p1 = (char *)malloc(10);堆
    
       p2 = (char *)malloc (20);堆
    
       }
    

    三 、 内存分配中栈区和堆区的区别

    0、申请方式和回收方式不同

      不知道你是否有点明白了,堆和栈的第一个区别就是申请方式的不同:栈(英文名字;stack)是系统自动分配空间的
    

    ,例如我们定义了一个 char a ;系统会自动的在栈上为其开辟空间。而堆(英文名字:heap)则是程序员根据需要自己申请的空间,例如malloc(10); 开辟是个字节的空间。由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。

    1、 申请后系统的响应

        栈 : 只要栈的剩余空间大于所申请的空间,系统将为程序提供内存,否则将报异常提示栈溢出。
    
    
     堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统受到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆。
    
     结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,
     另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。
     另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
     也就是说堆会在申请后还要做一些后续的工作这就会引出申请效率的问题
    

    2、申请效率的比较

    栈:  由系统自动分配,速度较快。但程序员是无法控制的。
    
    堆:  是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。
    

    3、 申请大小的限制

    栈: 在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。
    这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,
    在Windows下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),
    如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
    
      堆:堆是向高地址扩展的数据结构,是不连续的内存区域。
      这是由于系统是用链表来存储空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。
      堆的大小受限于计算机系统中有效的虚拟内存。
      由此可见,堆获得的空间比较灵活,也比较大。
    

    4、堆和栈中的内存内容

     由于栈的大小限制,所以用子函数还是有物理意义的,而不仅仅是逻辑意义。
    
    栈:在函数调用时,第一个进栈的是主函数中函数调用后的下一条指令(函数调用语句的吓一跳可执行语句)的地址,
    然后是函数的各个参数,在大多数的C编译器中,参数是有右往左入栈的,然后是函数中的局部变量。
    注意静态变量是不入栈的。
    当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,
    也就是主函数中的下一条指令,程序由该点继续运行。
    

    堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

    5、 关于堆和栈一个比较形象的比喻

    栈:使用栈就像我们去饭馆里吃饭,只管点菜(发出申请)、付钱、吃(使用),吃饱了就走,
    不必理会切菜,洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处就是快捷,但是自由度小。
    
       堆:使用堆就像是自己动手做喜欢的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大
    

    此处参考了博客:http://blog.csdn.net/wolenski/article/details/7951961#comments

    堆的基本操作

    堆就是完全二叉树
    而完全二叉树其实就是数组,你可以把它想象成一个完全二叉树。在数组中定义一个规则,
    在这里插入图片描述
    规则
    左 2i+1
    右 2
    i+2
    父 (i-1)/2

    大根堆的向下调整

    1,每回数组中进来一个树,把它与父结点进行比较,如果比他大,就交换
    2,找父结点,进来的数在数组中的下标(i-1)/2,就是父结点的位置
    

    堆的操作

    堆的向下调整

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    建堆

    小堆的建立

    在这里插入图片描述
    从最后一个非叶子节点开始,不断的向下调整。
    在这里插入图片描述

    向上调整

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 内存堆和数据结构堆区别

    千次阅读 2019-01-28 11:36:56
    内存空间有堆内存,栈内存。数据结构中也存在结构,栈结构。两者本质没有什么联系。内存和栈是存储数据的,而数据结构中的和栈是用来组织数据的一种工具。...

    在内存空间有堆内存,栈内存。数据结构中也存在堆结构,栈结构。两者本质没有什么联系。内存中堆和栈是存储数据的,而数据结构中的堆和栈是用来组织数据的一种工具。

    展开全文
  • 1、内存堆相关的几个重要数据结构 MIN_SIZE 是12个字节:这谁能给我说说这个最新内存字节为什么是12,想破脑袋了也布吉岛啊。 内存池的链表头:LWIP中内存堆的管理的链表头中使用的 next 和 prev 是地址偏移量而...

    1、内存堆相关的几个重要数据结构

    MIN_SIZE 是12个字节:这谁能给我说说这个最新内存字节为什么是12,想破脑袋了也布吉岛啊

    内存池的链表头:LWIP中内存堆的管理的链表头中使用的 next 和 prev 是地址偏移量而不是指针,这么做的原因是在堆大小满足条件 MEM_SIZE <= 64000L 时可以起到节省内存的效果,不要问为什么,因为指针啊。。。。

    内存堆大小:内存堆的大小是由下面的一个宏函数定义的,是由:对齐后的堆大小 + 2倍的链表头大小 + 对齐字节

    LWIP_DECLARE_MEMORY_ALIGNED(ram_heap, MEM_SIZE_ALIGNED + (2U * SIZEOF_STRUCT_MEM));

    需要注意的是用户定义的HEAP大小 MEM_SIZE_ALIGNED ,在其实能被使用的空间是 MEM_SIZE_ALIGNED - SIZEOF_STRUCT_MEM,因为要在 ram_heap[] 数组头部放一个链表头结构体,具体内存分布会在后面介绍。

    其他全局变量:

    static u8_t *ram;//指向堆对齐的后的起始地址,地址不会改变

    static struct mem *ram_end;//指向内存块的最后,地址不会改变

    static struct mem * LWIP_MEM_LFREE_VOLATILE lfree;//指向最靠前的空闲内存块,LWIP_MEM_LFREE_VOLATILE 是volatile,在使用操作系统的时候会被定义,至于为什么,请自行百度。

     

    2、内存堆管理的相关函数

    以下函数介绍只介绍重要的几个,内存的溢出检查不在范围以内,且不涉 MEM_LIBC_MALLOC= 1和 MEM_USE_POOLS = 1的情况。

    内存堆初始化函数 mem_init(void):

    步骤1:获取对齐后的堆数组地址,然后把堆数组的前几个字节转换成 mem 结构体类型;

    步骤2:把链表头的next 地址偏移到堆数组的第MEM_SIZE_ALIGNED 字节位置,把 prev 地址偏移到堆数组首个元素的位置,并标记内存块没有使用。

    步骤3:把 MEM_SIZE_ALIGNED 字节之后的几个字节转换成 mem 结构体类型存放尾链表,再把链表尾的 next和prev 地址偏移到堆数组的第 MEM_SIZE_ALIGNED 个字节位置,然后标记数组已经被使用;

    步骤4:最后在把空闲块指针指向堆数组的开始位置;

    相关困惑:1、在步骤2中为什么不把next 地址偏移位置加上一个链表空间的大小?2、为什么不把步骤3中的尾链表位置向后移动一个链表空间大小?这样就不会浪费了一个结构体大小的空间了,可用堆空间会变成 (ram_end - ram),这个问题几乎没人解释,但是我查看了1.4.1\2.0.0\2.0.3这几个版本都是这样的,可能是有我理解不了的原因。

    初始化后的内存空间如下图:

    内存堆申请函数 mem_malloc(mem_size_t size_in):

    本函数主要是申请 size 个字节的内存空间,申请成功则返回申请的内存块的起始地址,这个地址是 used 之后的地址,否则则返回 NULL。注意申请的内存空间 size_in 是我们要求的可用内存大小,不包括链表大小,可能比我们想要的要大点,因为要进行内存大小对齐,其次还可能剩余的内存空间不足以被分割为新的内存块;申请的最小内存大小至少是12字节;

    步骤1:判断 size_in 的大小是否符合要求,否则直接返回NULL;

    步骤2:从首个空闲内存块开始寻找一个没有被占用且大小符合 size+SIZEOF_STRUCT_MEM 的空闲结构体,注意这里的内存块遍历也是要遍历已经使用的内存块的,具体原因后面介绍;

    步骤3:通过以上步骤找到了这样一个符合要求的内存块,之后还要判断这个空闲内存块能不能被分割出一个新的内存块,也就是判断剩余的空间是否大于等于 SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED 。如果不能被分割了,那么就直接把当前内存块的 used=1 即可;如果可以被分割,则在内存中会多出一个分割后的空闲内存块,然后调整相应内存块的前后项偏移,再把已被申请的内存块 used=1,这里要注意非空闲内存块依然是在内存链表上的,并不是像FreeRTOS的内存管理那样,使用一个链表把所有空闲内存块串在一起。

    步骤4:如果申请走的是首个空闲内存块,那还需要把空闲内存块指针向后移动,找到下一个空闲内存块,在这之间或许要跨过多个已经被申请的内存块。

    步骤5:然后返回申请的地址,注意这个地址使用跨过了链表头内存的,不是跨过鸭绿江的。

    注意这里的内存块申请后是没有进行内存空间初始化的。

    内存堆释放函数 mem_free(void *rmem):

    此函数传入的参数是要释放的内存块的地址,这个地址是由 mem_malloc() 函数申请来的地址。整个过程非常简单就是在满足条件的情况下把这个要释放的内存块的 used=0 即可,其次就是进行内存合并;

    步骤1:更具以下条件判断内存是否能够释放:① 地址是否为空;② 地址是否是对齐地址;③ 释放的地址是否在ram_heap[]空间内;④ 地址是内存是否被占用;⑤ 整个链表是否有问题;如果以上有一条没有满足则释放不成功。

    步骤2:传入的地址满足释放条件后,直接把当前内存块的 used = 0,内存释放到此就结束了,这就是在申请的时候不把占用内存块从链表移除的好处,不需要进行插入操作啦,不过这也导致在申请的时候遍历链表的开销变大;

    步骤3:然后把进入 plug_holes() 函数去进行内存合并,先获取当前内存块前一个内存块和后一个内存块是否被占用,如果没有被占用就直接进行内存块的合并,这也是非空闲内存块不提出带来的好处,而对于FreeRTOS的内存管理进行合并时还需要进行前后内存地址计算和检查,这也是要花费开销的。

    内存堆裁剪函数mem_trim(void *rmem, mem_size_t new_size):

    这个函数是对已经申请的内存块进行裁剪的函数,第一个参数是要裁剪的内存块的地址,必须是由 mem_malloc() 函数申请来的地址,第二个参数是新内存块的大小,也就是从第一个参数向后申请多大空间,这个空间不能大于原先内存块的空间,否则裁剪失败。

    mem_calloc(mem_size_t count, mem_size_t size):

    此函数是 mem_malloc() 的重新封装,申请的内存大小就是两个参数的乘积,与 mem_malloc() 的主要区别就是他会在内存申请后对内存进行初始化,这是非常有用的。

    以下用图例说明内存堆的申请和释放过程,注意这里忽略内存对齐和内存碎片等情况,只是便于理解而已,这里是内存堆中某一时刻的内存分布,可以看出不论内存块是否使用,都是在链表上的:

    从内存堆中申请一个40 Bytes大小的内存,之后的内存分布情况如下图从这里可以看出,内存被分割且Ifree指针发送了移动:


    从内存堆中释放一个60 Bytes的内存块,释放之后的内存分布如下图,从这里可以看出内存释放后,与前后的空闲内存进行了合并,形成了一个大的内存块:

     

    展开全文
  • 内存堆管理器GenCollectedHeap的初始化

    千次阅读 2014-11-16 17:17:31
    前文在介绍Java对象内存分配的上层接口CollectedHeap时就提过, GenCollectedHeap是一种基于内存分代管理的内存堆管理器实现. 它一方面负责java对象的内存分配, 另一方面还得负责垃圾对象的回收, 而GC策略...
  • 前言:我们经常听见一个概念,(heap)和栈(stack),其实在数据结构中也有同样的这两个概念,但是这和内存的堆栈是不一样的东西哦,本文也会说明他们之间的区别的,另外,本文的只是是以C/C++为背景来说明,不同...
  • Android手机 内存堆大小

    千次阅读 2017-08-23 09:32:46
    ActivityManager manager = (ActivityManager)getSystemService(Context.ACTIVITY_SERVICE); int heapSize = manager.... 这个就是每个程序可使用的内存上限, 开发应用程序时所使用的内存不能超出这个限制,否则就
  • windows内存堆的数据结构

    千次阅读 2012-10-16 19:52:21
    还是紧接着昨天的问题,很想明白到底在内存的数据结构到底是怎么样的?究竟是不是别人回答的红黑树的结构? 在网上搜索了一番好像也鲜有答案。后来在《0day 安全 软件漏洞分析技术》一书里面找到了这个问题的...
  • 前面在介绍内存堆管理器的抽象层CollectedHeap时着重提到过, Java对象的内存分配主要涉及到其三个核心方法,这三个方法分别表示: 一.从线程的本地分配缓冲区中分配临时内存; 二.从内存堆中分配临时内存; 三.从内存堆...
  • 栈:存放基本类型的变量数据和对象的引用,但对象本身不存放在栈中,而是存放在(new 出来的对象)或者常量池中(字符串常量对象存放在常量池中。)  3. :存放所有new出来的对象。  4. 静态域:存放静态...
  • 直接内存堆内存 堆内存 直接内存内存) 零拷贝 NIO原生直接内存 直接内存的GC Netty的直接内存 在介绍Netty的内存管理前,先简单了解一下直接内存堆内存 直接内存堆内存 jvm中使用的内存可分为...
  • 内存内存详解

    万次阅读 多人点赞 2018-05-07 17:14:42
    一、什么是内存1、内存(on-heap memory)回顾内存内存是相对的二个概念,其中内存是我们平常工作中接触比较多的,我们在jvm参数中只要使用-Xms,-Xmx等参数就可以设置的大小和最大值,理解...
  • 关于堆内存和栈内存释放

    千次阅读 2019-06-28 20:47:18
    js 中的内存分为堆内存和 栈内存 堆内存:存储引用类型值 (对象:键值对 函数:代码字符串) 栈内存: 提供JS代码执行的环境和存储基本类型值 堆内存释放 让所有引用堆内存空间地址的变量赋值给Null 即可 (没有...
  • java堆内存和栈内存的区别

    万次阅读 多人点赞 2017-06-05 14:48:57
    一段时间之前,我写了两篇文章文章分别是Java的垃圾回收和Java的值传递,从那之后我收到了很多要求解释Java堆内存和栈内存的邮件,并且要求解释他们的异同点。 在Java中你会看到很多和栈内存的引用,JavaEE书和...
  • JAVA内存内存

    千次阅读 2018-07-15 21:08:07
    定义堆内存完全由JVM负责分配和释放,如果代码有程序缺陷,可能是触发OOM内存为了能直接分配和释放内存,提高效率。使用方式:使用未公开的Unsafe和NIO下的ByteBuffer内存的回收机制Direct Memory是受GC控制...
  • 直接内存堆内存谁快

    千次阅读 2018-05-30 08:25:35
    直接内存大多时候也被称为内存,自从 JDK 引入 NIO 后,直接内存的使用也越来越普遍。通过 native 方法可以分配内存,通过 DirectByteBuffer 对象来操作。 直接内存不属于 Java ,所以它不受大小限制,...
  • 堆内存完全由JVM负责分配和释放,如果程序没有缺陷代码导致内存泄露,那么就不会遇到java.lang.OutOfMemoryError这个错误。 使用内存,就是为了能直接分配和释放内存,提高效率。JDK5.0之后,代码中能直接操作...
  • jvm堆内存和非堆内存

    千次阅读 2014-03-06 12:50:45
    (Heap)和非(Non-heap)内存   按照官方的说法:“Java 虚拟机具有一个是运行时数据区域,所有类实例和数组的内存均从此处分配。是在 Java 虚拟机启动时创建的。”“在JVM中之外的内存称为非堆内存...
  • jvm堆内存和非堆内存(转载)

    千次阅读 2019-03-27 15:46:17
    和非堆内存 按照官方的说法:“Java 虚拟机具有一个(Heap),是运行时数据区域,所有类实例和数组的内存均从此处分配。是在 Java 虚拟机启动时创建的。”“在JVM中之外的内存称为非堆内存(Non-heap ...
  • 其实外是两个相对的关系,内存是我们常用到的。Java分配的非空对象都是由java虚拟机的垃圾收集器管理的,这一部分称为内存,虚拟机会定期对垃圾内存进行回收,在某些特定的时间点,它会进行一次彻底的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,217
精华内容 39,686
关键字:

内存堆