Chinaunix首页 | 论坛 | 博客
  • 博客访问: 5693465
  • 博文数量: 409
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 8273
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-23 19:15
个人简介

qq:78080458 学习交流群:150633458

文章分类

全部博文(409)

文章存档

2019年(127)

2018年(130)

2016年(20)

2015年(60)

2014年(41)

2013年(31)

分类: LINUX

2015-04-23 17:02:10

原文地址:linux内存管理之malloc 作者:linuxDOS

       对于内核的内存管理,像kmalloc,vmalloc,kmap,ioremap等比较熟悉。而对用户层的管理机制不是很熟悉,下面就从malloc的实现入手.( 这里不探讨linux系统调用的实现机制. ) ,参考了《深入理解计算机系统》和一些网上的资料.
首先从http://ftp.gnu.org/gnu/glibc下载glibc库2.21,
通常我们用的bsp或者sdk里面的工具链都是编译好的,而这个是源码,需要自己编译(常用的有定制交叉编译工具链).有时候我们需要添加自定义库.     

Linuxmalloc的早期版本是由Doug Lea实现的,它有一个重要问题就是在并行处理时多个线程共享进程的内存空间,各线程可能并发请求内存,在这种情况下应该如何保证分配和回收的正确和有效。Wolfram GlogerDoug Lea的基础上改进使得glibcmalloc可以支持多线程——,在glibc-2.3.x.中已经集成了ptmalloc2,这就是我们平时使用的malloc.

其做法是,为了支持多线程并行处理时对于内存的并发请求操作,malloc的实现中把全局用户堆(heap)划分成很多子堆(sub-heap)。这些子堆是按照循环单链表的形式组织起来的。每一个子堆利用互斥锁(mutex)使线程对于该子堆的访问互斥。当某一线程需要调用malloc分配内存空间时,该线程搜索循环链表试图获得一个没有加锁的子堆。如果所有的子堆都已经加锁,那么malloc会开辟一块新的子堆,对于新开辟的子堆默认情况下是不加锁的,因此线程不需要阻塞就可以获得一个新的子堆并进行分配操作。在回收free操作中,线程同样试图获得待回收块所在子堆的锁,如果该子堆正在被别的线程使用,则需要等待直到其他线程释放该子堆的互斥锁之后才可以进行回收操作。

         申请小块内存时会产生很多内存碎片,ptmalloc在整理时需要对子堆做加锁操作,每个加锁操作大概需要510cpu指令,而且程序线程数很高的情况下,锁等待的时间就会延长,导致malloc性能下降。

因此很多大型的服务端应用会自己实现内存池,以降低向系统malloc的开销。是在glibc和应用程序之间实现的内存管理。Hoard的作者是美国麻省的Amherst College的一名老师,理论角度对hoard的研究和优化比较多,相关的文献可以hoard主页下载到到。从我自己项目中的系统使用来看,Hoard确实能够很大程度的提高程序的性能和稳定性。TCMallocThread-Caching Malloc)是google开发的开源工具──“google-perftools”中的成员。这里有它的和安装方法。这个只是对它历史发展的一个简单介绍,具体改动还需去官网查看.
  下面我们就看看malloc:

malloc的全称是memory allocation,中文叫分配,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存。 

原型为: extern void *malloc(unsigned int num_bytes)。
  具体声明在malloc.h中:

点击(此处)折叠或打开

  1. /* Allocate SIZE bytes of memory. */
  2. extern void *malloc (size_t __size) __THROW __attribute_malloc__ __wur;

返回值:

如果分配成功则返回指向被分配内存的(此存储区中的初始值不确定),否则返回空指针。当内存不再使用时,应使用()函数将内存块释放。函数返回的一定要适当对齐,使其可以用于任何 

注意:

malloc(0) 返回不为空。  Free(p) p不为空。

那么malloc到底是从哪里获取的内存呢? 
   答案是从堆里面获得空间;malloc的应用必然是某一个进程调用,而每一个进程在启动的时候,系统默认给它分配了heap。下面我们就看看进程的内存空间布局:
Anyway, here is the standard segment layout in a Linux process:(这个是x86 虚拟地址空间的默认布局)

在glibc库中找到malloc.c文件:

点击(此处)折叠或打开

  1. strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
即malloc别名为__libc_malloc,__malloc.并且在malloc.c中我们不能找到malloc的直接实现,而是有__libc_malloc:

点击(此处)折叠或打开

  1. /*------------------------ Public wrappers. --------------------------------*/

  2. void *
  3. __libc_malloc (size_t bytes)
  4. {
  5.   mstate ar_ptr;
  6.   void *victim;

  7.   void *(*hook) (size_t, const void *)
  8.     = atomic_forced_read (__malloc_hook);
  9.   if (__builtin_expect (hook != NULL, 0))
  10.     return (*hook)(bytes, RETURN_ADDRESS (0));

  11.   arena_lookup (ar_ptr);

  12.   arena_lock (ar_ptr, bytes);
  13.   if (!ar_ptr)
  14.     return 0;

  15.   victim = _int_malloc (ar_ptr, bytes);
  16.   if (!victim)
  17.     {
  18.       LIBC_PROBE (memory_malloc_retry, 1, bytes);
  19.       ar_ptr = arena_get_retry (ar_ptr, bytes);
  20.       if (__builtin_expect (ar_ptr != NULL, 1))
  21.         {
  22.           victim = _int_malloc (ar_ptr, bytes);
  23.           (void) mutex_unlock (&ar_ptr->mutex);
  24.         }
  25.     }
  26.   else
  27.     (void) mutex_unlock (&ar_ptr->mutex);
  28.   assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
  29.           ar_ptr == arena_for_chunk (mem2chunk (victim)));
  30.   return victim;
  31. }
在这个函数的第一行是关于hook的,我们先看一个定义:

点击(此处)折叠或打开

  1. void *weak_variable (*__malloc_hook)
  2.   (size_t __size, const void *) = malloc_hook_ini;
它是gcc  attribute weak的特性,可以查资料进一步了解.这里说明一下由于是弱属性,所以当有具体的实现的时候,就以外部实现为准.

点击(此处)折叠或打开

  1. static void *
  2. malloc_hook_ini (size_t sz, const void *caller)
  3. {
  4.   __malloc_hook = NULL;
  5.   ptmalloc_init ();
  6.   return __libc_malloc (sz);
  7. }
__libc_malloc中首先判断hook函数指针是否为空,不为空则调用它,并返回。glibc2.21里默认malloc_hook是初始化为malloc_hook_ini的
但是我们发现在malloc_hook_ini中把__malloc_hook赋值为NULl,这样就避免了递归调用.
同理在最后部分也有一个__malloc_initialize_hook的:默认为空.

点击(此处)折叠或打开

  1. void weak_variable (*__malloc_initialize_hook) (void) = NULL;
那么ptmalloc_init到底又做了什么工作呢?

点击(此处)折叠或打开

  1. static void
  2. ptmalloc_init (void)
  3. {
  4.   if (__malloc_initialized >= 0)
  5.     return;

  6.   __malloc_initialized = 0;

  7. #ifdef SHARED
  8.   /* In case this libc copy is in a non-default namespace, never use brk.
  9.      Likewise if dlopened from statically linked program. */
  10.   Dl_info di;
  11.   struct link_map *l;

  12.   if (_dl_open_hook != NULL
  13.       || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
  14.           && l->l_ns != LM_ID_BASE))
  15.     __morecore = __failing_morecore;
  16. #endif

  17.   tsd_key_create (&arena_key, NULL);
  18.   tsd_setspecific (arena_key, (void *) &main_arena);
  19.   thread_atfork (ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
  20.   const char *s = NULL;
  21.   if (__glibc_likely (_environ != NULL))
  22.     {
  23.       char **runp = _environ;
  24.       char *envline;

  25.       while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
  26.                                0))
  27.         {
  28.           size_t len = strcspn (envline, "=");

  29.           if (envline[len] != '=')
  30.             /* This is a "MALLOC_" variable at the end of the string
  31.                without a '=' character. Ignore it since otherwise we
  32.                will access invalid memory below. */
  33.             continue;

  34.           switch (len)
  35.             {
  36.             case 6:
  37.               if (memcmp (envline, "CHECK_", 6) == 0)
  38.                 s = &envline[7];
  39.               break;
  40.             case 8:
  41.               if (!__builtin_expect (__libc_enable_secure, 0))
  42.                 {
  43.                   if (memcmp (envline, "TOP_PAD_", 8) == 0)
  44.                     __libc_mallopt (M_TOP_PAD, atoi (&envline[9]));
  45.                   else if (memcmp (envline, "PERTURB_", 8) == 0)
  46.                     __libc_mallopt (M_PERTURB, atoi (&envline[9]));
  47.                 }
  48.               break;
  49.             case 9:
  50.               if (!__builtin_expect (__libc_enable_secure, 0))
  51.                 {
  52.                   if (memcmp (envline, "MMAP_MAX_", 9) == 0)
  53.                     __libc_mallopt (M_MMAP_MAX, atoi (&envline[10]));
  54.                   else if (memcmp (envline, "ARENA_MAX", 9) == 0)
  55.                     __libc_mallopt (M_ARENA_MAX, atoi (&envline[10]));
  56.                 }
  57.               break;
  58.             case 10:
  59.               if (!__builtin_expect (__libc_enable_secure, 0))
  60.                 {
  61.                   if (memcmp (envline, "ARENA_TEST", 10) == 0)
  62.                     __libc_mallopt (M_ARENA_TEST, atoi (&envline[11]));
  63.                 }
  64.               break;
  65.             case 15:
  66.               if (!__builtin_expect (__libc_enable_secure, 0))
  67.                 {
  68.                   if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
  69.                     __libc_mallopt (M_TRIM_THRESHOLD, atoi (&envline[16]));
  70.                   else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
  71.                     __libc_mallopt (M_MMAP_THRESHOLD, atoi (&envline[16]));
  72.                 }
  73.               break;
  74.             default:
  75.               break;
  76.             }
  77.         }
  78.     }
  79.   if (s && s[0])
  80.     {
  81.       __libc_mallopt (M_CHECK_ACTION, (int) (s[0] - '0'));
  82.       if (check_action != 0)
  83.         __malloc_check_init ();
  84.     }
  85.   void (*hook) (void) = atomic_forced_read (__malloc_initialize_hook);
  86.   if (hook != NULL)
  87.     (*hook)();
  88.   __malloc_initialized = 1;
  89. }
而__malloc_initialized在arena.c中默认初始化为:即开始的时候小于0.

点击(此处)折叠或打开

  1. /* Already initialized? */
  2. int __malloc_initialized = -1;
函数开始把它赋值为0,最后初始化完成赋值为1. 所以这个函数完成了malloc的初始化工作.只有第一次调用的时候会用到.
接着是处理_environ即传递过来的环境变量,进行内存分配策略控制你可以定制内存管理函数的行为,通过调整由mallopt()函数的参数。(
默认环境变量为空

内存分配调整甚至可以不在你的程序中引入mallopt()调用和重新编译它。在你想快速测试一些值或者你没有源代码时,这非常有用。你仅需要做的是在运行程序前,设置合适的环境变量。表1展示mallopt()参数和环境变量的映射关系以及一些额外的信息。例如,如果你希望设置内存消减阈值为64k,你可以运行这个程序:

#MALLOC_TRIM_THRESHOLD=65536 my_prog

内存调试:连续性检查 ,可以设置变量
MALLOC_CHECK_=1
#MALLOC_CHECK_=1 my_prog
还有一个mtrace使用的例子:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>


  4. void main(void)
  5. {

  6.  char *p;
  7.  mtrace();
  8.  p=(char *)malloc(100);
  9.  if(p ==NULL)
  10.      return 0;
  11.   memcpy(p,"helllllllllll",20);
  12.  printf("....1 %s.....\n",p);
  13.  //free(p);

  14. }
运行: #MALLOC_TRACE="1.txt" ./a.out 
然后用mtrace查看结果:

点击(此处)折叠或打开

  1. mtrace 1.txt

  2. Memory not freed:
  3. -----------------
  4.    Address Size Caller
  5. 0x09849378 0x64 at 0x804849e
  一些GNU C库提供的标准调试工具可能并不适合你程序的特殊需求。在这种情况下,你可以借助一个外部的内存调试工具(见 Resource)或者在你的库内部作修改。做这件事中只是简单的写三个函数以及将它们与预先定义的变量相关联:
  • __malloc_hook points to a function to be called when the user calls malloc(). You can do your own checks and accounting here, and then call the real malloc() to get the memory that was requested.

    __malloc_hook 指向一个函数,当用户调用malloc()时,这个函数将被调用。你可以在这里做你自己的检查和计数,然后调用真实的malloc来得到被请求的内存。

  • __free_hook points to a function called instead of the standard free().

    __free_hook 指向一个函数,用来替换标准的free()

  • __malloc_initialize_hook points to a function called when the memory management system is initialized. This allows you to perform some operations, say, setting the values of the previous hooks, before any memory-related operation takes place.

    __malloc_initialize__hook 指向一个函数,当内存管理系统被初始化的时候,这个函数被调用。这允许你来实施一些操作,例如,在任何内存相关的操作生效前,设置前面的勾子值。

在其它的内存相关的调用中,Hooks()也有效,包括realloc(),calloc()等等。确保在调用malloc()或free()之前,保存先前的勾子的值,把它们存储起来。如果你不这么做,你的程序将陷入无尽的递归。看看libc info page给的一个内存调试的例子来看看相关细节,最后一点,勾子也被mcheck和mtrace系统使用。在使用所有它们的组合的时候,小心是没错的。

而下面的是关于多线程的:

创建线程私有实例 arena_key,该私有实例保存的是分配区( arena )的 malloc_state 实例指针。 arena_key 指向的可能是主分配区的指针,也可能是非主分配区的指针,这里将调用 ptmalloc_init() 的线程的 arena_key 绑定到主分配区上。意味着本线程首选从主分配区分配内存。

然后调用 thread_atfork() 设置当前进程在 fork 子线程( linux 下线程是轻量级进程,使用类似 fork 进程的机制创建)时处理 mutex 的回调函数,在本进程 fork 子线程时,调用 ptmalloc_lock_all() 获得所有分配区的锁,禁止所有分配区分配内存,当子线程创建完毕,父进程调用 ptmalloc_unlock_all() 重新 unlock 每个分配区的锁 mutex ,子线程调用 ptmalloc_unlock_all2() 重新初始化每个分配区的锁 mutex

点击(此处)折叠或打开

  1. tsd_key_create (&arena_key, NULL);
  2.   tsd_setspecific (arena_key, (void *) &main_arena);
  3.   thread_atfork (ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
当有多个线程同时申请访问内存的时候,arena_key的main_arena处于保持互斥锁状态,那么为了提高效率即上面的代码,保证了在获取不到主分区的时候,调用arena_get2自动创建次分区state。见代码:

点击(此处)折叠或打开

  1. #define arena_lookup(ptr) do { \
  2.       void *vptr = NULL;                         \
  3.       ptr = (mstate) tsd_getspecific (arena_key, vptr);             \
  4.   } while (0)

点击(此处)折叠或打开

  1. #define arena_lock(ptr, size) do {                     \
  2.       if (ptr)                                 \
  3.         (void) mutex_lock (&ptr->mutex);                 \
  4.       else                                 \
  5.         ptr = arena_get2 (ptr, (size), NULL);                 \
  6.   } while (0)
在继续之前我们补一下关键的数据结构:

点击(此处)折叠或打开

  1. struct malloc_state
  2. {
  3.   /* Serialize access. */
  4.   mutex_t mutex;

  5.   /* Flags (formerly in max_fast). */
  6.   int flags;

  7.   /* Fastbins */
  8.   mfastbinptr fastbinsY[NFASTBINS];

  9.   /* Base of the topmost chunk -- not otherwise kept in a bin */
  10.   mchunkptr top;

  11.   /* The remainder from the most recent split of a small request */
  12.   mchunkptr last_remainder;

  13.   /* Normal bins packed as described above */
  14.   mchunkptr bins[NBINS * 2 - 2];

  15.   /* Bitmap of bins */
  16.   unsigned int binmap[BINMAPSIZE];

  17.   /* Linked list */
  18.   struct malloc_state *next;

  19.   /* Linked list for free arenas. */
  20.   struct malloc_state *next_free;

  21.   /* Memory allocated from the system in this arena. */
  22.   INTERNAL_SIZE_T system_mem;
  23.   INTERNAL_SIZE_T max_system_mem;
  24. }
还有具体分配的chunk:关于它的注释部分这么就不翻译了,但需要好好看看。

点击(此处)折叠或打开

  1. /*
  2.   ----------------------- Chunk representations -----------------------
  3. */


  4. /*
  5.   This struct declaration is misleading (but accurate and necessary).
  6.   It declares a "view" into memory allowing access to necessary
  7.   fields at known offsets from a given base. See explanation below.
  8. */

  9. struct malloc_chunk {

  10.   INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
  11.   INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */

  12.   struct malloc_chunk* fd; /* double links -- used only if free. */
  13.   struct malloc_chunk* bk;

  14.   /* Only used for large blocks: pointer to next larger size. */
  15.   struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  16.   struct malloc_chunk* bk_nextsize;
  17. };


  18. /*
  19.    malloc_chunk details:

  20.     (The following includes lightly edited explanations by Colin Plumb.)

  21.     Chunks of memory are maintained using a `boundary tag' method as
  22.     described in e.g., Knuth or Standish. (See the paper by Paul
  23.     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
  24.     survey of such techniques.) Sizes of free chunks are stored both
  25.     in the front of each chunk and at the end. This makes
  26.     consolidating fragmented chunks into bigger chunks very fast. The
  27.     size fields also hold bits representing whether chunks are free or
  28.     in use.

  29.     An allocated chunk looks like this:


  30.     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  31.      | Size of previous chunk, if allocated | |
  32.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  33.      | Size of chunk, in bytes |M|P|
  34.       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  35.      | User data starts here... .
  36.      . .
  37.      . (malloc_usable_size() bytes) .
  38.      . |
  39. nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  40.      | Size of chunk |
  41.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


  42.     Where "chunk" is the front of the chunk for the purpose of most of
  43.     the malloc code, but "mem" is the pointer that is returned to the
  44.     user. "Nextchunk" is the beginning of the next contiguous chunk.

  45.     Chunks always begin on even word boundaries, so the mem portion
  46.     (which is returned to the user) is also on an even word boundary, and
  47.     thus at least double-word aligned.

  48.     Free chunks are stored in circular doubly-linked lists, and look like this:

  49.     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  50.      | Size of previous chunk |
  51.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  52.     `head:' | Size of chunk, in bytes |P|
  53.       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  54.      | Forward pointer to next chunk in list |
  55.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  56.      | Back pointer to previous chunk in list |
  57.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  58.      | Unused space (may be 0 bytes long) .
  59.      . .
  60.      . |
  61. nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  62.     `foot:' | Size of chunk, in bytes |
  63.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  64.     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
  65.     chunk size (which is always a multiple of two words), is an in-use
  66.     bit for the *previous* chunk. If that bit is *clear*, then the
  67.     word before the current chunk size contains the previous chunk
  68.     size, and can be used to find the front of the previous chunk.
  69.     The very first chunk allocated always has this bit set,
  70.     preventing access to non-existent (or non-owned) memory. If
  71.     prev_inuse is set for any given chunk, then you CANNOT determine
  72.     the size of the previous chunk, and might even get a memory
  73.     addressing fault when trying to do so.

  74.     Note that the `foot' of the current chunk is actually represented
  75.     as the prev_size of the NEXT chunk. This makes it easier to
  76.     deal with alignments etc but can be very confusing when trying
  77.     to extend or adapt this code.

  78.     The two exceptions to all this are

  79.      1. The special chunk `top' doesn't bother using the
  80.     trailing size field since there is no next contiguous chunk
  81.     that would have to index off it. After initialization, `top'
  82.     is forced to always exist. If it would become less than
  83.     MINSIZE bytes long, it is replenished.

  84.      2. Chunks allocated via mmap, which have the second-lowest-order
  85.     bit M (IS_MMAPPED) set in their size fields. Because they are
  86.     allocated one-by-one, each must contain its own trailing size field.

  87. */
实际分配的chunk图,空间里如何布局的:

而空的chunk结构如下图:

因为后边代码就是按照这个结构来操作的.
继续回到__libc_malloc函数,hook处理完之后,
Arena_lookup查询arena_key,当然不为空,前面第一次调用hook时已经赋值。(如果多线程下,获取不到main_arena,则分配次分区,这个前面也讨论过)

那么获得互斥锁。

进入内存分配的核心函数_int_malloc,它是malloc分配的核心代码和实现.代码挺多,自行分析.

   1.       判断申请的空间是否在fastbin,如果在则申请返回,否则继续(<64B,一般小字节chunk释放后放在这里)

   2.       判断申请的空间是否在smallbin(小于512B),如果是申请返回否则在largebin

   3.       前两个都不在,那么肯定在largebin,计算索引,继续

   4.       进入for(;;)后续处理.主要是垃圾回收工作。如果垃圾回收也不行,则进入use_top chunk
5.       use_top  chunk申请,如果没有,则调用sysmalloc扩展heap,如下:

点击(此处)折叠或打开

  1. /*
  2.          Otherwise, relay to handle system-dependent cases
  3.        */
  4.       else
  5.         {
  6.           void *p = sysmalloc (nb, av);
  7.           if (p != NULL)
  8.             alloc_perturb (p, bytes);
  9.           return p;
  10.         }
对于第一次调用malloc它直接到sysmalloc来扩展heap,自测的例子是先申请200字节的空间.由于程序一开始fast_max为0,所以肯定在smallbins分类中,但是由于初始化,所以
会调用malloc_consolidate来初始化bins,见malloc_init_state(av);:

点击(此处)折叠或打开

  1. /*
  2.    Initialize a malloc_state struct.

  3.    This is called only from within malloc_consolidate, which needs
  4.    be called in the same contexts anyway. It is never called directly
  5.    outside of malloc_consolidate because some optimizing compilers try
  6.    to inline it at all call points, which turns out not to be an
  7.    optimization at all. (Inlining it in malloc_consolidate is fine though.)
  8.  */

  9. static void
  10. malloc_init_state (mstate av)
  11. {
  12.   int i;
  13.   mbinptr bin;

  14.   /* Establish circular links for normal bins */
  15.   for (i = 1; i < NBINS; ++i)
  16.     {
  17.       bin = bin_at (av, i);
  18.       bin->fd = bin->bk = bin;   //  链表初始化指向自己
  19.     }

  20. #if MORECORE_CONTIGUOUS
  21.   if (av != &main_arena)
  22. #endif
  23.   set_noncontiguous (av);
  24.   if (av == &main_arena)
  25.     set_max_fast (DEFAULT_MXFAST);            //  设置fastbin max 为 64B
  26.   av->flags |= FASTCHUNKS_BIT;

  27.   av->top = initial_top (av);
  28. }
我们进入sysmalloc,一开始判断申请的nb是否大于需要map的阀值,如果大于则进入mmap。一般大于128K,它可以动态调整

点击(此处)折叠或打开

  1. /*
  2.   MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
  3.   adjusted MMAP_THRESHOLD.
  4. */

  5. #ifndef DEFAULT_MMAP_THRESHOLD_MIN
  6. #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
  7. #endif

  8. #ifndef DEFAULT_MMAP_THRESHOLD_MAX
  9.   /* For 32-bit platforms we cannot increase the maximum mmap
  10.      threshold much because it is also the minimum value for the
  11.      maximum heap size and its alignment. Going above 512k (i.e., 1M
  12.      for new heaps) wastes too much address space. */
  13. # if __WORDSIZE == 32
  14. # define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
  15. # else
  16. # define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
  17. # endif
  18. #endi
然后是判断是主分配区或非主分配区,分别不同处理。
这里进入主分配,我们看下部分核心分配代码:

点击(此处)折叠或打开

  1. else /* av == main_arena */


  2.     { /* Request enough space for nb + pad + overhead */
  3.       size = nb + mp_.top_pad + MINSIZE;

  4.       /*
  5.          If contiguous, we can subtract out existing space that we hope to
  6.          combine with new space. We add it back later only if
  7.          we don't actually get contiguous space.
  8.        */

  9.       if (contiguous (av))
  10.         size -= old_size;

  11.       /*
  12.          Round to a multiple of page size.
  13.          If MORECORE is not contiguous, this ensures that we only call it
  14.          with whole-page arguments. And if MORECORE is contiguous and
  15.          this is not first time through, this preserves page-alignment of
  16.          previous calls. Otherwise, we correct to page-align below.
  17.        */

  18.       size = (size + pagemask) & ~pagemask;

  19.       /*
  20.          Don't try to call MORECORE if argument is so big as to appear
  21.          negative. Note that since mmap takes size_t arg, it may succeed
  22.          below even if we cannot call MORECORE.
  23.        */

  24.       if (size > 0)
  25.         {
  26.           brk = (char *) (MORECORE (size));
  27.           LIBC_PROBE (memory_sbrk_more, 2, brk, size);
  28.         }

  29.       if (brk != (char *) (MORECORE_FAILURE))
  30.         {
  31.           /* Call the `morecore' hook if necessary. */
  32.           void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
  33.           if (__builtin_expect (hook != NULL, 0))
  34.             (*hook)();
  35.         }
  36.       else
  37.         {
由于申请的是200B,8字节对齐为208B,而mp_.top_pad用的默认值为7个pages(0x20000),MINSIZE为16B.后边还需要page对齐,所以需要申请8个page。
下面我们看关键的代码:

点击(此处)折叠或打开

  1. brk = (char *) (MORECORE (size));
这个是什么?

点击(此处)折叠或打开

  1. /* Definition for getting more memory from the OS. */
  2. #define MORECORE (*__morecore)
  3. #define MORECORE_FAILURE 0
  4. void * __default_morecore (ptrdiff_t);
  5. void *(*__morecore)(ptrdiff_t) = __default_morecore;


  6. #include <string.h>

  7. /*
  8.   MORECORE-related declarations. By default, rely on sbrk
  9. */


  10. /*
  11.   MORECORE is the name of the routine to call to obtain more memory
  12.   from the system. See below for general guidance on writing
  13.   alternative MORECORE functions, as well as a version for WIN32 and a
  14.   sample version for pre-OSX macos.
  15. */

  16. #ifndef MORECORE
  17. #define MORECORE sbrk
  18. #endif
__default_morecore是:

点击(此处)折叠或打开

  1. /* Allocate INCREMENT more bytes of data space,
  2.    and return the start of data space, or NULL on errors.
  3.    If INCREMENT is negative, shrink data space. */
  4. void *
  5. __default_morecore (ptrdiff_t increment)
  6. {
  7.   void *result = (void *) __sbrk (increment);
  8.   if (result == (void *) -1)
  9.     return NULL;

  10.   return result;
  11. }
  12. libc_hidden_def (__default_morecore)
这里解释下sbrk:

    sbrk不是系统调用,是C库函数。系统调用通常提供一种最小功能,而库函数通常提供比较复杂的功能。sbrk/brk是从堆中分配空间,本质是移动一个位置,向后移就是分配空间,向前移就是释放空间,sbrk用相对的整数值确定位置,如果这个整数是正数,会从当前位置向后移若干字节,如果为负数就向前若干字节。在任何情况下,返回值永远是移动之前的位置。sbrk是brk的封装。
默认mp_.sbrk_base为空。所以需要:

点击(此处)折叠或打开

  1. if (mp_.sbrk_base == 0)
  2.             mp_.sbrk_base = brk;
 av->system_mem默认也为0 

点击(此处)折叠或打开

  1. av->system_mem += size;
然后需要做一些调整:

点击(此处)折叠或打开

  1. /*
  2.              Otherwise, make adjustments:

  3.            * If the first time through or noncontiguous, we need to call sbrk
  4.               just to find out where the end of memory lies.

  5.            * We need to ensure that all returned chunks from malloc will meet
  6.               MALLOC_ALIGNMENT

  7.            * If there was an intervening foreign sbrk, we need to adjust sbrk
  8.               request size to account for fact that we will not be able to
  9.               combine new space with existing space in old_top.

  10.            * Almost all systems internally allocate whole pages at a time, in
  11.               which case we might as well use the whole last page of request.
  12.               So we allocate enough more memory to hit a page boundary now,
  13.               which in turn causes future contiguous calls to page-align.
  14.            */

  15.           else
  16.             {
  17.               front_misalign = 0;
  18.               end_misalign = 0;
  19.               correction = 0;
  20.               aligned_brk = brk;

  21.               /* handle contiguous cases */
  22.               if (contiguous (av))
  23.                 {
  24.                   /* Count foreign sbrk as system_mem. */
后面有这么一句:由于correction为0,所以返回当前的值.

点击(此处)折叠或打开

  1. snd_brk = (char *) (MORECORE (correction));
最后来分配空间:

点击(此处)折叠或打开

  1. /* finally, do the allocation */
  2.   p = av->top;    
  3.   size = chunksize (p);

  4.   /* check that one of the above allocation paths succeeded */
  5.   if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))    // size 为top->size  ,为刚申请空间的大小. 我们的例子是0x21000 (8pages)而nb为208B
  6.     {
  7.       remainder_size = size - nb;// 0x2100 - 208(0xd0)
  8.       remainder = chunk_at_offset (p, nb);
  9.       av->top = remainder;                                 // 改变top的指针                                              
  10.       set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
  11.       set_head (remainder, remainder_size | PREV_INUSE);
  12.       check_malloced_chunk (av, p, nb);
  13.       return chunk2mem (p);
  14.     }
av->top是什么值呢?

点击(此处)折叠或打开

  1. /* Adjust top based on results of second sbrk */
  2.               if (snd_brk != (char *) (MORECORE_FAILURE))
  3.                 {
  4.                   av->top = (mchunkptr) aligned_brk;    //      aligned_brk = brk;  当然如果需要对齐,aligned_brk会偏移一些字节
也就是top就是一个指向heap开始的指针.并转换为struct malloc_chunk 指针.和我们上面的 图就对应起来了。

然后重新设置top指针,和size的标志位,偏移过pre_size和size,就是实际数据地址即return chunk2mem (p);

如果我们紧接着申请了200B后,马上申请16B,由于fastbins虽然设置了max 为64B但是它里面的chunk是free的时候放置进来的,目前为空。
所以继续进入smallbin。同理由于没有free的small chunk 。所以进入top chunk 分配成功:

点击(此处)折叠或打开

  1. use_top:
  2.       /*
  3.          If large enough, split off the chunk bordering the end of memory
  4.          (held in av->top). Note that this is in accord with the best-fit
  5.          search rule. In effect, av->top is treated as larger (and thus
  6.          less well fitting) than any other available chunk since it can
  7.          be extended to be as large as necessary (up to system
  8.          limitations).

  9.          We require that av->top always exists (i.e., has size >=
  10.          MINSIZE) after initialization, so if it would otherwise be
  11.          exhausted by current request, it is replenished. (The main
  12.          reason for ensuring it exists is that we may need MINSIZE space
  13.          to put in fenceposts in sysmalloc.)
  14.        */

  15.       victim = av->top;
  16.       size = chunksize (victim);

  17.       if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
  18.         {
  19.           remainder_size = size - nb;
  20.           remainder = chunk_at_offset (victim, nb);
  21.           av->top = remainder;
  22.           set_head (victim, nb | PREV_INUSE |
  23.                     (av != &main_arena ? NON_MAIN_ARENA : 0));
  24.           set_head (remainder, remainder_size | PREV_INUSE);

  25.           check_malloced_chunk (av, victim, nb);
  26.           void *p = chunk2mem (victim);
  27.           alloc_perturb (p, bytes);
  28.           return p;
  29.         }
当然如果我们释放了16B后,有马上申请16B,那么它会直接进入fastbin并申请返回成功。,这里我们知道当第一次使用的时候不论什么bin都是空的,只有当多次使用多次释放的时候才会体会出来它的优势和效率来.
这里附上自己测试的小程序:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. int main(void)
  5. {

  6.   char *p,*q;
  7.   void * brk;
  8.  brk=sbrk(0);
  9. printf("brk is ....%p...\n",brk);
  10.   p = (char *)malloc(200);
  11.  if(p==NULL)
  12.   return 1;

  13.  strcpy(p,"hello");

  14.   brk=sbrk(100);
  15. printf("111....brk is ....%p...\n",brk);
  16.  printf("200,p is %s...\n",p);

  17.   q= (char *)malloc(16);
  18.   if(q==NULL)
  19.    return 1;

  20.  strcpy(q,"nihao");

  21.  printf("16,q is %s...\n",q);

  22.  free(q);
  23.  free(p);

  24.   p= (char *)malloc(16);

  25.  return 0;

  26. }
关于不论fastbin还是smallbin的机制,或许我们记得在《深入理解计算机系统》中,讲到垃圾回收的时候,脚注法。书和代码一起看效果会不错.
内存的延迟分配,只有
在真正访问一个地址的时候才建立这个地址的物理映射,这是Linux内存管理的基本思想之一
还有就是:
内核默认配置下,进程的栈和mmap映射区域并不是从一个固定地址开始,并且每次启动时的值都不一样,这是程序在启动时随机改变这些值的设置,使得使用缓冲区溢出进行攻击更加困难。当然也可以让进程的栈和mmap映射区域从一个固定位置开始,只需要设置全局变量randomize_va_space值为0,这个变量默认值为1。用户可以通过设置/proc/sys/kernel/randomize_va_space来停用该特性,也可以用如下命令:  sudo sysctl -w kernel.randomize_va_space=0











 



















阅读(3783) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~