关闭
Hit
enter
to search or
ESC
to close
May I Suggest ?
#leanote #leanote blog #code #hello world
Mutepig's Blog
Home
Archives
Tags
Search
About Me
Linux堆基础知识(1)
无
1455
1
1
mut3p1g
对于堆溢出，最重要的就是了解内存空间是如何申请和释放的，而最简单的方式就是阅读源码。源码可以直接查看`ptmalloc`的[源代码](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html)，同时根据华庭的[pdf](http://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf)辅助理解。首先这里先将一些基本名词及函数、定义罗列一下，方便后续的分析。 <!--more--> # 0x01 Linux内存分布 Linux下`.bss段`到栈之间的空间是空闲的，而这空闲的空间被划分为了`heap`和`mmap`两个部分，如下图所示(小小的盗下图XD)。这两个区域都可以供用户自由使用，一般可以使用`malloc()`和`free()`两个函数来动态申请和释放内存。  这两个部分的内存由下面两个函数分别申请： ## 1.brk() `brk()`用于`heap`空间的申请，主要是设定堆访存的上限，也就是堆顶`top`，当申请的空间太大使得`bins`无法分配的时候就会调用`brk()`来将堆顶向上推移。 ## 2.mmap() `mmap()`用于申请空间过大而堆无法满足时(小于mmap的分配阈值`mmap_threshold`)，向`mmap`映射区域来申请内存；`munmap()`是用来将这些申请的空间销毁的。 ``` 865 #ifndef DEFAULT_MMAP_THRESHOLD_MIN 866 #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024) //128k 867 #endif ``` # 0x02 内存管理数据结构 ## 1. main_arena&none_main_arena 每个进程都有一个主分配区(`main_arena`)，但在SMP多线程环境下可能存在多个非主分配区(`none_main_arena`)，并且分配区的数量一旦增加就不会减少了。主分配区可以访问进程的`heap`和`mmap`，但非主分配区只能访问`mmap`，每个分配区之间是独立的。 ### 1) main_arena 主分配区的申明如下： ``` 1723 static struct malloc_state main_arena = 1724 { 1725 .mutex = _LIBC_LOCK_INITIALIZER, 1726 .next = &main_arena, 1727 .attached_threads = 1 1728 }; ``` ### 2) none_main_area 非主分配区主要作用是分担主分配区分配的压力，在多线程时加速小内存块的分配。大致流程如下: 1. 创建新的非主分配区 2. 通过`mmap`分配一个大内存块作为模拟堆 3. 通过模拟堆分配小内存块 4. 当模拟堆分配完了，再通过`mmap`分配一个模拟堆，加入模拟堆的单向链表中 下面对源码的分析主要是在[sysmalloc](http://www.mutepig.club/index.php/archives/47/#3.sysmalloc)才会用到，如果还不想分析的话可以直接跳到后面一小节。 #### a. 模拟堆 * heap_info ``` 53 typedef struct _heap_info 54 { 55 mstate ar_ptr; /* Arena for this heap. */ //heap所在的分配区 56 struct _heap_info *prev; /* Previous heap. */ // 上一个heap 57 size_t size; /* Current size in bytes. */ // heap的大小 58 size_t mprotect_size; /* Size in bytes that has been mprotected 59 PROT_READ|PROT_WRITE. */ // heap中受读写保护的空间大小 60 /* Make sure the following data is properly aligned, particularly 61 that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of 62 MALLOC_ALIGNMENT. */ 63 char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK]; // 填充，为了保证堆的实例是对齐的。 64 } heap_info; ``` * 创建模拟堆 创建模拟堆的主要都是映射`HEAP_MAX_SIZE`的空间，但是只会申请`size`的可读写空间，其步骤如下： 1. 调整size合法 2. 尝试从`aligned_heap_area`开始映射空间 3. 如果2.失败，则直接映射`2*HEAP_MAX_SIZE`的空间 4. 如果3.失败，则直接映射`HEAP_MAX_SIZE`的空间 5. 2.3.4有一个映射成功了，则申请`size`的可读写空间，作为申请的模拟堆返回 ``` 465 static heap_info * 466 internal_function 467 new_heap (size_t size, size_t top_pad) 468 { 469 size_t pagesize = GLRO (dl_pagesize); // 页大小，64位下是0x1000 470 char *p1, *p2; 471 unsigned long ul; 472 heap_info *h; 473 474 if (size + top_pad < HEAP_MIN_SIZE) // 模拟堆最小大小=32KB 475 size = HEAP_MIN_SIZE; 476 else if (size + top_pad <= HEAP_MAX_SIZE) // 小于模拟堆最大大小=（32位：1M；64位：64M） 477 size += top_pad; 478 else if (size > HEAP_MAX_SIZE) // 超过了则退出 479 return 0; 480 else 481 size = HEAP_MAX_SIZE; 482 size = ALIGN_UP (size, pagesize); // 页对齐 483 484 /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed. 485 No swap space needs to be reserved for the following large 486 mapping (on Linux, this is the case for all non-writable mappings 487 anyway). */ 488 p2 = MAP_FAILED; 489 if (aligned_heap_area) // 全局变量aligned_heap_area表示上次调用mmap分配内存的结束地址 490 { 491 p2 = (char *) MMAP (aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE, 492 MAP_NORESERVE); // 尝试从aligned_heap_area结束地址映射空间 493 aligned_heap_area = NULL; 494 if (p2 != MAP_FAILED && ((unsigned long) p2 & (HEAP_MAX_SIZE - 1))) // 如果成功了但是没有与HEAP_MAX_SIZE对齐 495 { 496 __munmap (p2, HEAP_MAX_SIZE); // 取消该映射 497 p2 = MAP_FAILED; // 记为映射失败 498 } 499 } 500 if (p2 == MAP_FAILED) // 如果映射失败 501 { 502 p1 = (char *) MMAP (0, HEAP_MAX_SIZE << 1, PROT_NONE, MAP_NORESERVE); // 用mmap映射2*HEAP_MAX_SIZE的空间，因为最坏的情况下需要2倍才能按HEAP_MAX_SIZE对齐 503 if (p1 != MAP_FAILED) // 映射成功了 504 { 505 p2 = (char *) (((unsigned long) p1 + (HEAP_MAX_SIZE - 1)) 506 & ~(HEAP_MAX_SIZE - 1)); // 与HEAP_MAX_SIZE对齐，记作模拟堆的起始地址 507 ul = p2 - p1; // 多余的空间 508 if (ul) 509 __munmap (p1, ul); // 将多余的空间返回给系统 510 else 511 aligned_heap_area = p2 + HEAP_MAX_SIZE; // 将模拟堆的结束地址赋值给aligned_heap_area 512 __munmap (p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul); // 将多余的空间返回给系统 513 } 514 else // 如果映射2倍HEAP_MAX_SIZE失败了，则只映射HEAP_MAX_SIZE的空间 515 { 516 /* Try to take the chance that an allocation of only HEAP_MAX_SIZE 517 is already aligned. */ 518 p2 = (char *) MMAP (0, HEAP_MAX_SIZE, PROT_NONE, MAP_NORESERVE); 519 if (p2 == MAP_FAILED) 520 return 0; 521 522 if ((unsigned long) p2 & (HEAP_MAX_SIZE - 1)) // 如果没有对齐，则释放 523 { 524 __munmap (p2, HEAP_MAX_SIZE); 525 return 0; 526 } 527 } 528 } 529 if (__mprotect (p2, size, PROT_READ | PROT_WRITE) != 0) // 如果设置刚映射的空间可读可写失败，也释放 530 { 531 __munmap (p2, HEAP_MAX_SIZE); 532 return 0; 533 } 534 h = (heap_info *) p2; // 映射成功了，将其作为模拟堆返回 535 h->size = size; 536 h->mprotect_size = size; 537 LIBC_PROBE (memory_heap_new, 2, h, h->size); 538 return h; 539 } ``` * 增长模拟堆 由于每个非主分配区都已经映射了`HEAP_MAX_SIZE`的空间，所以这个函数主要是将模拟堆`h`向上增长`diff`的可读写空间。 ``` 541 /* Grow a heap. size is automatically rounded up to a 542 multiple of the page size. */ 543 544 static int 545 grow_heap (heap_info *h, long diff) // h是堆，diff为增长的大小 546 { 547 size_t pagesize = GLRO (dl_pagesize); 548 long new_size; 549 550 diff = ALIGN_UP (diff, pagesize); // diff需要按页对齐 551 new_size = (long) h->size + diff; // 获得新的size，加上diff就行 552 if ((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE) // 如果超出堆大小限制则增长失败 553 return -1; 554 555 if ((unsigned long) new_size > h->mprotect_size) // 如果大小符合要求 556 { 557 if (__mprotect ((char *) h + h->mprotect_size, 558 (unsigned long) new_size - h->mprotect_size, 559 PROT_READ | PROT_WRITE) != 0) // 拓展可读写空间失败 560 return -2; 561 562 h->mprotect_size = new_size; 563 } 564 565 h->size = new_size; // 更新大小 566 LIBC_PROBE (memory_heap_more, 2, h, h->size); 567 return 0; 568 } ``` * 收缩模拟堆 和增长模拟堆类似，这个函数主要是将模拟堆`h`收缩`diff`的可读写空间。 ``` 572 static int 573 shrink_heap (heap_info *h, long diff) 574 { 575 long new_size; 576 577 new_size = (long) h->size - diff; // 收缩后的空间 578 if (new_size < (long) sizeof (*h)) // 收缩后空间不能比模拟堆的结构还小 579 return -1; 580 581 /* Try to re-map the extra heap space freshly to save memory, and make it 582 inaccessible. See malloc-sysdep.h to know when this is true. */ 583 if (__glibc_unlikely (check_may_shrink_heap ())) // 如果能收缩堆 584 { 585 if ((char *) MMAP ((char *) h + new_size, diff, PROT_NONE, 586 MAP_FIXED) == (char *) MAP_FAILED) // 收缩失败 587 return -2; 588 589 h->mprotect_size = new_size; // 更新模拟堆的可读写的大小 590 } 591 else 592 __madvise ((char *) h + new_size, diff, MADV_DONTNEED); 593 /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/ 594 595 h->size = new_size; 596 LIBC_PROBE (memory_heap_less, 2, h, h->size); 597 return 0; ``` * 删除模拟堆 ``` 602 #define delete_heap(heap) \ 603 do { \ 604 if ((char *) (heap) + HEAP_MAX_SIZE == aligned_heap_area) \ // 如果当前模拟堆结束地址和一样aligned_heap_area，那么如果删掉了后就能从当前模拟堆或者更小的地方开始申请了，这样就能优先从低地址映射空间 605 aligned_heap_area = NULL; \ 606 __munmap ((char *) (heap), HEAP_MAX_SIZE); \ 607 } while (0) ``` * 释放模拟堆 首先这里需要了解一下什么是`fencepost`，它是专门用来分隔两个模拟堆的。其初始化过程在第三节中可以看到，具体形式如下图所示： ``` 主分配区 +====================+ 高地址 chunk +====================+ heap_info +====================+ next_heap 0 | 2*SIZE_SZ+1 +====================+ fencepost_chunk2 prev_size | 2*SIZE_SZ +====================+ fencepost_chunk1 topchunk +====================+ chunk +====================+ heap_info +====================+ heap 非主分配区 +====================+ 高地址 chunk +====================+ heap_info +====================+ next_heap 2*SIZE_SZ| 0+1 +====================+ fencepost_chunk2 prev_size | 2*SIZE_SZ +====================+ fencepost_chunk1 topchunk +====================+ chunk +====================+ heap_info +====================+ heap ``` 可以看到`fencepost`有两个`chunk`，第一个`chunk`记录了其前一个`topchunk`的大小，以及自己的大小；第二个`chunk`标记第一个`chunk`在使用中，在主分配区中会设置自己的大小，但在非主分配区中不会。这样处理的原因是不能有两个连续的`chunk`是空闲的，所以为了区分`fencepost`和`topchunk`才设置成如此奇葩的样子。当`topchunk`很小的话，还会将`topchunk`和第一个`chunk`合并，不过这种情况比较少见。 然后接下来就是如何释放模拟堆了。首先是判断能否释放：如果topchunk起始地址和heap_info的结束地址相同，那么就意味着这个heap是完全空闲的，所以就能释放了。 ``` 609 static int 610 internal_function 611 heap_trim (heap_info *heap, size_t pad) 612 { 613 mstate ar_ptr = heap->ar_ptr; 614 unsigned long pagesz = GLRO (dl_pagesize); 615 mchunkptr top_chunk = top (ar_ptr), p, bck, fwd; 616 heap_info *prev_heap; 617 long new_size, top_size, top_area, extra, prev_size, misalign; 618 619 /* Can this heap go away completely? */ 620 while (top_chunk == chunk_at_offset (heap, sizeof (*heap))) // 判断topchunk起始地址和heap_info结束地址是否相同 621 { 622 prev_heap = heap->prev; 623 prev_size = prev_heap->size - (MINSIZE - 2 * SIZE_SZ); 624 p = chunk_at_offset (prev_heap, prev_size);// p指向了fencepost的第二个chunk 625 /* fencepost must be properly aligned. */ 626 misalign = ((long) p) & MALLOC_ALIGN_MASK; 627 p = chunk_at_offset (prev_heap, prev_size - misalign); // 对齐调整 628 assert (chunksize_nomask (p) == (0 | PREV_INUSE)); /* must be fencepost */ 629 p = prev_chunk (p); // p指向fencepost第一个chunk 630 new_size = chunksize (p) + (MINSIZE - 2 * SIZE_SZ) + misalign; // 将fencepost两个chunk大小加一起 631 assert (new_size > 0 && new_size < (long) (2 * MINSIZE)); 632 if (!prev_inuse (p)) // 如果fencepost前一个chunk也是空闲，大小也加一起 633 new_size += prev_size (p); 634 assert (new_size > 0 && new_size < HEAP_MAX_SIZE); 635 if (new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz) // 如果前一个模拟堆的空闲空间太小，则不能释放当前堆（避免再次新建模拟堆） 636 break; 637 ar_ptr->system_mem -= heap->size; // 释放当前heap，从系统分配的内存中减掉 638 LIBC_PROBE (memory_heap_free, 2, heap, heap->size); 639 delete_heap (heap); 640 heap = prev_heap; // heap指向上一个heap 641 if (!prev_inuse (p)) /* consolidate backward */ // 如果fencepost的前一个chunk不在使用中，则合并 642 { 643 p = prev_chunk (p); 644 unlink (ar_ptr, p, bck, fwd); 645 } 646 assert (((unsigned long) ((char *) p + new_size) & (pagesz - 1)) == 0); 647 assert (((char *) p + new_size) == ((char *) heap + heap->size)); 648 top (ar_ptr) = top_chunk = p; // topchunk设置为上一个模拟堆的topchunk 649 set_head (top_chunk, new_size | PREV_INUSE); 650 /*check_chunk(ar_ptr, top_chunk);*/ 651 } 652 653 /* Uses similar logic for per-thread arenas as the main arena with systrim 654 and _int_free by preserving the top pad and rounding down to the nearest 655 page. */ 656 top_size = chunksize (top_chunk); 657 if ((unsigned long)(top_size) < 658 (unsigned long)(mp_.trim_threshold)) // 如果topchunk没达到收缩堆的大小则退出 659 return 0; 660 661 top_area = top_size - MINSIZE - 1; 662 if (top_area < 0 || (size_t) top_area <= pad) // topchunk太小也退出 663 return 0; 664 665 /* Release in pagesize units and round down to the nearest page. */ 666 extra = ALIGN_DOWN(top_area - pad, pagesz); // 需要收缩的空间 667 if (extra == 0) 668 return 0; 669 670 /* Try to shrink. */ 671 if (shrink_heap (heap, extra) != 0) // 收缩堆 672 return 0; 673 674 ar_ptr->system_mem -= extra; 675 676 /* Success. Adjust top accordingly. */ 677 set_head (top_chunk, (top_size - extra) | PREV_INUSE); 678 /*check_chunk(ar_ptr, top_chunk);*/ 679 return 1; 680 } ``` #### b. 创建非主分配区 当已有的分配区的锁都被占用的时候，就需要再创建一个非主分配区。主要是创建一个模拟堆，其构成为:`heap_info`实例+`malloc_state`实例+可供分配的空间。创建好后，将其加入全局分配区链表中，最后返回该分配区。 ``` 700 static mstate 701 _int_new_arena (size_t size) 702 { 703 mstate a; 704 heap_info *h; 705 char *ptr; 706 unsigned long misalign; 707 708 h = new_heap (size + (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT), 709 mp_.top_pad); // 申请的空间需要满足size，以及一个heap_info实例和malloc_state实例，最后还需对齐 710 if (!h) // 如果申请失败，则不需要size了，可以申请一个正常的模拟堆之后再加空间 711 { 712 /* Maybe size is too large to fit in a single heap. So, just try 713 to create a minimally-sized arena and let _int_malloc() attempt 714 to deal with the large request via mmap_chunk(). */ 715 h = new_heap (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT, mp_.top_pad); 716 if (!h) 717 return 0; 718 } 719 a = h->ar_ptr = (mstate) (h + 1); // h对应的空间为heap_info的实例，以及在new_heap中初始化了；h+1对应的就是malloc_state的实例 720 malloc_init_state (a); // 初始化分配区 721 a->attached_threads = 1; 722 /*a->next = NULL;*/ 723 a->system_mem = a->max_system_mem = h->size; 724 725 /* Set up the top chunk, with proper alignment. */ 726 ptr = (char *) (a + 1); // 剩下的空间用来分配 727 misalign = (unsigned long) chunk2mem (ptr) & MALLOC_ALIGN_MASK; // 对齐 728 if (misalign > 0) 729 ptr += MALLOC_ALIGNMENT - misalign; 730 top (a) = (mchunkptr) ptr; // 由于是刚创建分配区，所以整个可分配的区域都属于topchunk 731 set_head (top (a), (((char *) h + h->size) - ptr) | PREV_INUSE); // 设置topchunk的头部 732 733 LIBC_PROBE (memory_arena_new, 2, a, size); 734 mstate replaced_arena = thread_arena; 735 thread_arena = a; 736 __libc_lock_init (a->mutex); 737 738 __libc_lock_lock (list_lock); 739 740 /* Add the new arena to the global list. */ 741 a->next = main_arena.next; // 将刚创建的非主分配区加入分配区的全局链表中 742 /* FIXME: The barrier is an attempt to synchronize with read access 743 in reused_arena, which does not acquire list_lock while 744 traversing the list. */ 745 atomic_write_barrier (); 746 main_arena.next = a; 747 748 __libc_lock_unlock (list_lock); 749 750 __libc_lock_lock (free_list_lock); 751 detach_arena (replaced_arena); 752 __libc_lock_unlock (free_list_lock); 753 754 /* Lock this arena. NB: Another thread may have been attached to 755 this arena because the arena is now accessible from the 756 main_arena.next list and could have been picked by reused_arena. 757 This can only happen for the last arena created (before the arena 758 limit is reached). At this point, some arena has to be attached 759 to two threads. We could acquire the arena lock before list_lock 760 to make it less likely that reused_arena picks this new arena, 761 but this could result in a deadlock with 762 __malloc_fork_lock_parent. */ 763 764 __libc_lock_lock (a->mutex); 765 766 return a; 767 } ``` 所以对于非主分配区，每个分配区都是由多个模拟堆组合而成的。其中只有第一个模拟堆构造是`heap_info`实例+`malloc_state`实例+分配空间，后续的模拟堆都是`heap_info`实例+分配空间，同时每个模拟堆之间都存在一个`fencepost`用来分隔。 ## 2.内存基本单元——chunk ### 1) malloc_chunk `malloc_chunk`用来描述内存分布后划分的块，从而对内存进行分配和回收，其结构如图所示(继续盗图XD)  可以看到每个`chunk`都存在头部，用以存储相关信息，之后才是用户申请的内存空间用来存储数据。对比下面的源码进行分析： ``` 1009 /* Forward declarations. */ 1010 struct malloc_chunk; 1011 typedef struct malloc_chunk* mchunkptr; // chunk链表 1389 typedef struct malloc_chunk *mbinptr; //实际上也是chunk链表 1067 struct malloc_chunk { 1068 1069 INTERNAL_SIZE_T mchunk_prev_size; // 如果前一个chunk是空闲的则表示前一个chunk的大小，否则无意义 1070 INTERNAL_SIZE_T mchunk_size; // 当前chunk的大小，而由于补齐的原因所以低3位作为flag，代表意义如下： /* A: 倒数第三位表示当前chunk属于主分配区(0)还是非主分配区(1) M: 倒数第二位表示当前chunk是从mmap(1)分配的，还是从heap(0)分配的 P: 最低位表示前一块是否在使用中 */ 1071 1072 struct malloc_chunk* fd; // 当该chunk为空闲时才有意义，记录后一个空闲chunk的地址 1073 struct malloc_chunk* bk; // 同上，记录前一个空闲chunk的地址 1074 1075 /* Only used for large blocks: pointer to next larger size. */ 1076 struct malloc_chunk* fd_nextsize; // 当前chunk为largebin时才有意义，指向比当前chunk大的第一个空闲chunk 1077 struct malloc_chunk* bk_nextsize; // 同上，指向比当前chunk小的第一个空闲chunk 1078 }; ``` 而在申请内存时，实际申请的空间和声明要申请的空间并不相同，其原因有以下几点： ``` 1. 每个chunk都存在head，来存储prev_size、size等相关信息 2. 用户申请的空间需要对齐到size_t，这样方便处理 3. 上一个chunk在使用中时，当前chunk是的prev_size是没有意义的，所以上一个chunk可以使用当前chunk的prev_size ``` 针对上面的第三点给个demo，运行后可以发现`p1`只申请了0x20的空间，而赋值后占用了p2的`prev_size`。 ``` #include <stdio.h> #include <stdlib.h> void main(){ char *p1,*p2; p1 = (char *) malloc(sizeof(char)*18); p2 = (char *) malloc(sizeof(char)*1); memcpy(p1,"111111111111111111",18); } ``` ### 2) 边界标记法 `ptmalloc`通过边界标记法实现其对chunk的管理。 #### a. 对齐值 首先需要明确的是，每个chunk都是根据`size_t`来进行对齐的，而具体值可以看下面的代码： ``` 54 #ifndef INTERNAL_SIZE_T 55 # define INTERNAL_SIZE_T size_t 56 #endif 57 58 /* The corresponding word size. */ 59 #define SIZE_SZ (sizeof (INTERNAL_SIZE_T)) 60 61 /* The corresponding bit mask value. */ 62 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) 27 #define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \ 28 ? __alignof__ (long double) : 2 * SIZE_SZ) ``` 其中`MALLOC_ALIGNMENT`是chunk大小对齐的最小值，而`MALLOC_ALIGN_MASK`就是其掩码，后面可以看到他们的作用。 #### b. 关于chunk的一些定义及操作 首先是chunk和mem互相转换，由于chunk包含了head，所以会比mem多出`2*SIZE_SZ`。所以转换就是加减这个值： ``` 1192 /* conversion from malloc headers to user pointers, and back */ 1193 1194 #define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ)) 1195 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ)) ``` 下面两个定义主要是用来判断分配的内存是否对齐了 ``` 1205 /* Check if m has acceptable alignment */ 1206 1207 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0) 1208 1209 #define misaligned_chunk(p) \ 1210 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \ 1211 & MALLOC_ALIGN_MASK) ``` #### c. 用户申请处理 由于用户申请的内存大小是不确定的，所以需要定义一系列函数来对请求进行处理。 首先是判断请求有无超过限制： ``` 1220 #define REQUEST_OUT_OF_RANGE(req) \ 1221 ((unsigned long) (req) >= \ 1222 (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))u) ``` 然后就是将请求的大小对齐一下，这里需要注意的是表达式中的`SIZE_SZ`，实际上这就是之前说到的借用的下面一个chunk的`prev_size`。而若是直接用`mmap`申请的空间，不存在空间可以借用，所以需要`2*SIZE_SZ`： ``` 1224 /* pad request bytes into a usable size -- internal version */ 1225 1226 #define request2size(req) \ 1227 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \ 1228 MINSIZE : /*请求小于最小大小则直接返回最小MINSIZE*/ \ 1229 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) //请求大了就对齐 ``` 最后就是带上检测 ``` 1233 #define checked_request2size(req, sz) \ 1234 if (REQUEST_OUT_OF_RANGE (req)) { \ 1235 __set_errno (ENOMEM); \ 1236 return 0; \ 1237 } \ 1238 (sz) = request2size (req); ``` #### d. chunk标志位处理 前面提过，由于对齐所以将chunk的后3位视作标志位，分别是`A|M|P`，下面以P为例子看下源码，其他两个也是一样的。 ``` 1245 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ 1246 #define PREV_INUSE 0x1 1247 1248 /* extract inuse bit of previous chunk */ 1249 #define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE) ``` 接着就是对chunk的一些处理 ``` 1278 // 这里是将标志位三个值或操作->1|2|4=7 1279 #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) 1280 1281 /* Get size, ignoring use bits 获取chunk p的size去掉标志位*/ 1282 #define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS)) 1283 1284 /* Like chunksize, but do not mask SIZE_BITS.获取chunk p的size，不去掉标志位 */ 1285 #define chunksize_nomask(p) ((p)->mchunk_size) 1286 1287 /* Ptr to next physical malloc_chunk. 获取chunk p的下一个chunk，加上自己的size就可以了 */ 1288 #define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p))) 1289 1290 /* Size of the chunk below P. Only valid if prev_inuse (P). 获得chunk p前一个chunk的大小，只有在前一个chunk是空闲的才有意义*/ 1291 #define prev_size(p) ((p)->mchunk_prev_size) 1292 1293 /* Set the size of the chunk below P. Only valid if prev_inuse (P). 设置chunk p->prev_size */ 1294 #define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz)) 1295 1296 /* Ptr to previous physical malloc_chunk. Only valid if prev_inuse (P). 获取chunk p的上一个chunk，减上一个chunk的size就可以了 */ 1297 #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p))) 1298 1299 /* Treat space at ptr + offset as a chunk 强行将p+s视作一个chunk*/ 1300 #define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s))) 1301 ``` #### e. 设置chunk是否在使用 下面三个操作分别是判断p是否在使用、设置p在使用、设置p空闲。而其确定的标准就是下一个chunk的size的`PREV_INUSE`标志位，所以对这个标志位进行操作就可以了。 ``` 1302 /* extract p's inuse bit */ 1303 #define inuse(p) \ 1304 ((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE) 1305 1306 /* set/clear chunk as being inuse without otherwise disturbing */ 1307 #define set_inuse(p) \ 1308 ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE 1309 1310 #define clear_inuse(p) \ 1311 ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE) ``` ## 3. 空闲内存管理 ### 1) bins `bins`就是由空闲chunk组成的数组, 每一个`bin` 都是双向链表. `bin`存放是整理过的chunks, 并且`bin` 中合并过的空闲chunk是不存在相邻的, 所以`bin` 中的每一个 chunk 都是可以被使用, 并且都是紧挨着正在使用的chunk内存末尾。`bins` 中的 chunk是按照大小排序的,采用FIFO, `从头部插入节点, 尾部取节点`。这样有个特点就是更容易内存的合并。 整个数组大概如下图所示(又小小的盗了下图XD)：  其中虽然定义了`NBINS=128`，但是`bins[0]`和`bins[127]`其实是不存在的，`bins[1]`为`unsorted bin`，然后有62个`smallbin`和63个`largebin`。 #### a.small bins `smallbins`是用来管理较小空间的`bins`，其中每个`bins`里面的chunk大小都是相同的，一共包含62个`bin`，具体大小依据系统是32位还是64位： 32位：16B,24B,32B...,504B => 62bins 64位：32B,48B,64B...,1008B => 62bins 这样当应用需要多大的空间，直接从`smallbins`里面申请就可以了。 相关定义及函数如下： * 定义`smallbins`的相关参数 ``` 1435 #define NBINS 128 // bins数组大小 1436 #define NSMALLBINS 64 // smallbins数组大小 1437 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT // 1438 #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ) 1439 #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH) // largebin的最小大小 ``` * 判断`sz`大小是否为`smallbin` ``` 1441 #define in_smallbin_range(sz) \ 1442 ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE) // fastbin也属于smallbin ``` * 获得`sz`大小在`smallbins`中的`index` ``` 1444 #define smallbin_index(sz) \ 1445 ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\ 1446 + SMALLBIN_CORRECTION) ``` #### b.fast bins `fastbins`可以看作`smallbins`的一小部分缓存，当申请的空间小于`max_fast`，会先从`fastbins`里面寻找空间，如果没有再从bins里面寻找。`fastbins`一共有7个chunk空闲单向链表，分别为32B，48B，64B，80B，96B，112B，128B。 相关定义及函数如下： * 根据`index`获得`fastbin`的对应地址 ``` 1562 typedef struct malloc_chunk *mfastbinptr; 1563 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx]) ``` * 获得`sz`大小在`fastbins`中的`index` ``` 1565 /* offset 2 to use otherwise unindexable first 2 bins 减2是由于0和1没有对应的chunk*/ 1566 #define fastbin_index(sz) \ 1567 ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2) ``` * 定义`fastbins`的相关参数 ``` 1571 #define MAX_FAST_SIZE (80 * SIZE_SZ / 4)// 定义MAX_FAST_SIZE 1573 #define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1) // fasbins数组大小 1586 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL) // fastbin合并的阈值 #ifndef DEFAULT_MXFAST #define DEFAULT_MXFAST (64 * SIZE_SZ / 4) // 定义max_fast的值 ``` * 分配区关于`fastbin`的一些操作 ``` 1603 #define FASTCHUNKS_BIT (1U) //判断有无fastbin的标志位是哪一位 1605 #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0) // M为分配区，若flags最低位为0则表示M中存在fastbin 1606 #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT) //清空M中的fastbin，即直接将flags置为1 1607 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT) // 设置fastbin，直接将flags置为0 ``` #### c.large bins `largebins`是用来管理较大空间的`bins`，一共包含63个`bin`，具体大小也是根据32位和64位而不同，具体数值很复杂，可以参考[pdf](http://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf)的P36。 相关定义及函数如下，顺便把`bins`的也一起列举了： * 获得`sz`大小在`bins`中的`index` ``` 1480 #define bin_index(sz) \ 1481 ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz)) ``` * 获得`sz`大小在`largebins`中的`index` ``` 1475 #define largebin_index(sz) \ 1476 (SIZE_SZ == 8 ? largebin_index_64 (sz) \ 1477 : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \ 1478 : largebin_index_32 (sz)) ``` * 获取分配区第`i`个`bin`的链表头 ``` 1365 #define bin_at(m, i) \ 1366 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \ 1367 - offsetof (struct malloc_chunk, fd)) ``` * 获取某个`bin`的下一个`bin` ``` #define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1))) ``` * 获取某个`bin`的第一个和最后个可用的chunk ``` 1373 #define first(b) ((b)->fd) 1374 #define last(b) ((b)->bk) ``` #### d.unsorted bin `unsorted bin`相当于整个`bins`的缓存。如果刚刚释放的空间大于`max_fast`，那么会首先放到`unsorted bin`中(只有一个，且为`bins[1]`)，在下一次内存分配时,如果无法从`fastbins`和`smallbins`中分配空间，那么会首先在这里寻找空间。如果无法从中寻找到空间则会将其中的chunk直接整理到`bins`。 相关定义及函数如下: * 获得`unsorted bin`的地址 ``` 1499 #define unsorted_chunks(M) (bin_at (M, 1)) ``` * `top chunk`初始化为`unsorted bin` ``` 1520 #define initial_top(M) (unsorted_chunks (M)) ``` ### 2) other chunk 下面介绍的三中chunk是特殊的chunk，无法在bins里面寻找到，用来解决bins所无法解决的内存分配的情况。 #### a.top chunk 系统会一开始就创建一个很大的缓冲区用来作为缓存空间，这样申请的时候直接在这个空间里面申请就可以了。`top chunk`实际上是系统最开始申请内存分配给`bins`后剩下的一块内存空间，所以处在最高处。当申请的空间太大使得`bins`无法分配的时候，就需要向`top chunk`进行申请。如果`top chunk`的空间不够的话，就会将堆的上界向上推移。 #### b.mmaped chunk 当申请的空间太大使得`bins`乃至`top chunk`都无法找到对应空间的时候，系统会用`mmap`来直接接使用内存映射来将页映射到进程空间。这样的chunk被释放的时候会返回给系统，并且无法再被调用。 #### c.last remainder 当且仅当申请`smallbin`的时候，如果`smallbins`无法找到满足的空间来分配，如果`last remainder`的空间大于申请的空间，就将从`last remainder`里面获得空间，而其剩下的空间变成新的`last remainder`。 # 0x03 内存管理核心结构体 这里的内容大多也与[sysmalloc](http://www.mutepig.club/index.php/archives/47/#3.sysmalloc)有关，可以简略的过一下。 ## 1.mm_struct Linux下每个进程都有一个内存描述符结构体`mm_struct`，描述和管理进程地址空间的所有信息。这里挑选几个比较关键的属性，完整的可以查看源码：https://code.woboq.org/linux/linux/include/linux/mm_types.h.html#mm_struct ``` 359 struct mm_struct { 368 unsigned long mmap_base; //memory mapping段的起始地址 419 unsigned long start_code, end_code, start_data, end_data; //代码和数据起始、结束地址 420 unsigned long start_brk, brk, start_stack;//heap段的起始地址和当前地址，以及stack段的起始地址 498 }; ``` ## 2.malloc_state 每个分配区都是`malloc_state`的一个分配实例，`ptmalloc`正是使用这个结构体来管理所有分配区，更为详细的解析可以参照[pdf](http://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf)的P44。 ``` 1651 struct malloc_state 1652 { 1653 /* Serialize access. */ 1654 __libc_lock_define (, mutex); 1655 //mutex翻译过来就是互斥锁，用来保证当多个线程同时访问一个分配区的时候，第一个获得mutex的线程将拥有其分配权。 1656 /* Flags (formerly in max_fast). */ 1657 int flags; 1658 // 记录了一些标志，bit0=0时表示分配区中有fastbin 1659 /* Fastbins */ 1660 mfastbinptr fastbinsY[NFASTBINS]; 1661 // NFASTBINS个fastbin链表指针头 1662 /* Base of the topmost chunk -- not otherwise kept in a bin */ 1663 mchunkptr top; 1664 // 指向topchunk的chunk指针 1665 /* The remainder from the most recent split of a small request */ 1666 mchunkptr last_remainder; 1667 // 指向last_remainder的chunk指针 1668 /* Normal bins packed as described above */ 1669 mchunkptr bins[NBINS * 2 - 2]; 1670 // 用来存储包括unstored bin，small bins，large bins的链表指针头，其中bins[1]为unstored bin。 1671 /* Bitmap of bins */ 1672 unsigned int binmap[BINMAPSIZE]; 1673 // binmap用来标识对应的bin中是否包含空闲chunk。 1674 /* Linked list */ 1675 struct malloc_state *next; 1676 // 将分配区以单向链表链接起来。 1677 /* Linked list for free arenas. Access to this field is serialized 1678 by free_list_lock in arena.c. */ 1679 struct malloc_state *next_free; 1680 // 将空闲的分配区以单向链表链接起来。 1681 /* Number of threads attached to this arena. 0 if the arena is on 1682 the free list. Access to this field is serialized by 1683 free_list_lock in arena.c. */ 1684 INTERNAL_SIZE_T attached_threads; 1685 1686 /* Memory allocated from the system in this arena. */ 1687 INTERNAL_SIZE_T system_mem; // 记录当前分配区已经分配的内存大小。 1688 INTERNAL_SIZE_T max_system_mem; // 记录当前分配区最大能分配的内存大小。 1689 }; ``` ### bitmap `bitmap`是一个`BINMAPSIZE(4)`大小的数组，每一个元素都叫一个`block`。而每一个元素都是一个`unsigned int`，所以正好是2^32，这样对应的数字的每一`bit`代表着对应的`bin`是否包含空闲`chunk`。这样就只用几个数字就能表示每个`bin`是否为空的情况了。 相关定义如下： * binmap大小 ``` 1561 #define BINMAPSHIFT 5 1562 #define BITSPERMAP (1U << BINMAPSHIFT) // 32 1563 #define BINMAPSIZE (NBINS / BITSPERMAP) // 4 ``` * idx转换到bitmap ``` 1565 #define idx2block(i) ((i) >> BINMAPSHIFT) // 获得idx对应的block 1566 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1)))) // 获得idx对应的bit ``` * bitmap操作 ``` 1568 #define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i)) // 标记分配区m的idx号bin存在空闲chunk 1569 #define unmark_bin(m, i) ((m)->binmap[idx2block (i)] &= ~(idx2bit (i))) // 标记分配区m的idx号bin不存在空闲chunk 1570 #define get_binmap(m, i) ((m)->binmap[idx2block (i)] & idx2bit (i)) // 获得分配区m的idx号bin是否存在chunk ``` ## 3.malloc_par `malloc_par`是全局唯一的结构体，用来定义分配时的各项参数，更为详细的解析可以参照[pdf](http://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf)的P47。 ``` 1691 struct malloc_par 1692 { 1693 /* Tunable parameters */ 1694 unsigned long trim_threshold; // 表示收缩阈值。默认为128*1024 1695 INTERNAL_SIZE_T top_pad; 1696 INTERNAL_SIZE_T mmap_threshold; // 表示mmap的分配阈值，该字段会动态修改，但不会超过最大值。默认为128*1024 1697 INTERNAL_SIZE_T arena_test; // 当每个进程的分配区数量小于等于 arena_test时，不会重用已有的分配区。32位下为2，64位下为8. 1698 INTERNAL_SIZE_T arena_max; // 保存分配区的最大数量 1699 1700 /* Memory map support */ 1701 int n_mmaps; // 表示当前进程使用 mmap()函数分配的内存块的个数。 1702 int n_mmaps_max; // 表示进程使用 mmap()函数分配的内存块的最大数量。默认为65536 1703 int max_n_mmaps; // 表示当前进程使用 mmap()函数分配的内存块的最大数量。 1704 /* the mmap_threshold is dynamic, until the user sets 1705 it manually, at which point we need to disable any 1706 dynamic behavior. */ 1707 int no_dyn_threshold; 1708 1709 /* Statistics */ 1710 INTERNAL_SIZE_T mmapped_mem; // 用于统计 mmap 分配的内存大小 1711 INTERNAL_SIZE_T max_mmapped_mem; 1712 1713 /* First address handed out by MORECORE/sbrk. */ 1714 char *sbrk_base; // 表示堆的起始地址 1715 }; ```
觉得不错，点个赞？
提交评论
Sign in
to leave a comment.
No Leanote account ?
Sign up now
.
1
条评论
More...
文章目录
mut3p1g
No Leanote account ? Sign up now.