Go 语言设计与实现-Part2

2020-09-15  本文已影响0人  shuff1e

20.栈内存管理

栈是由高地址向低地址增长。
堆是由低地址向高地址增长。

栈: 栈用于维护函数调用的上下文,离开了栈,函数调用就无法实现,栈通常在用户空间的最高地址处分配,通常有数兆字节的大小。

堆: 堆是用来容纳应用程序动态分配的内存区域,当程序使用 malloc 或者 new 分配内存的时候,得到的内存会来自堆里。堆通常存在栈的下方(低地址方向),在某些时候,堆也可能没有固定统一的存储区域。堆一般比栈大很多,可以有几十至数百兆字节的容量。

可执行文件映像: 存储着可执行文件在内存里的映像,由装载器在装载时将可执行文件的内存读取或映射到这里。

保留区: 保留区并不是一个单一的内存区域,而是对内存中受到保护而禁止访问的内存区域的总称:例如大多数操作系统中,极小的地址通常都是不允许访问的,如 NULL,C 语言将无效指针赋值为 0 也是这个考虑。

动态链接库映射区: 这个区域用于映射装载的动态链接库。在 Linux 下,如果可执行文件依赖其它共享库,那么系统就会为它在从 0x40000000 开始的地址分配相应的空间,并将共享库载入该空间。
剩下的还有以下几部份组成:
(1)代码段
(2)初始化数据段(数据段)
(3)未初始化数据段(BSS 段)

1、空闲链表法(即调用 malloc 分配):
就是把堆中各个空闲的块按照链表的方式连接起来,当用户请求一块空间的时候,可以遍历整个列表,直到找到合适大小的块并且将它拆分;当用户释放空间的时候将它合并到空闲链表中。
空闲链表是这样一种结构,在堆里的每一个空闲空间的开头(或结尾)有一个头 (header),头结构里记录了上一个 (prev) 和下一个 (next) 空闲块的地址,也就是说,所有的空闲块形成了一个链表。如图所示。

image

具体实现方案:

1)malloc 函数的实质是它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。

2)调用 malloc()函数时,它沿着连接表寻找一个大到足以满足用户请求所需要的内存块。然后,将该内存块一分为二(一块的大小与用户申请的大小相等,另一块的大小就是剩下来的字节)。接下来,将分配给用户的那块内存存储区域传给用户,并将剩下的那块(如果有的话)返回到连接表上。

3)调用 free 函数时,它将用户释放的内存块连接到空闲链表上。

4)到最后,空闲链会被切成很多的小内存片段,如果这时用户申请一个大的内存片段, 那么空闲链表上可能没有可以满足用户要求的片段了。于是,malloc() 函数请求延时,并开始在空闲链表上检查各内存片段,对它们进行内存整理,将相邻的小空闲块合并成较大的内存块。

2、位图法

针对空闲链表的弊端,另一种分配方式显得更加稳健。这种方式称为位围(Bitmap),其核心思想是将整个堆划分为大量的块(block),每个块的大小相同。

当用户请求内存的时候,总是分配整数个块的空间给用户,第一个块我们称为已分配区域的头(Head),其余的称为己分配区域的主体(Body),而我们可以使用一个整数数组来记录块的使用情况,由于每个块只有头/主体/空闲三种状态,因此仅仅需要两位即可表示一个块,因此称为位图。

3、对象池

还有一种方法是对象池,也是把堆空间分成了大小相等的一些块,它是认为某些场合每次分配的空间都相等,所以每次就直接返回一个块的大小,它的管理方法可以是链表也可以是位图。因为不用每次查找合适的大小的内存返回,所以效率很高。

实际上很多现实应用中,堆的分配算法往往是采取多种算法复合而成的。

比如对于 glibc 来说,它对于小于 64 字节的空间申请是采用类似于对象池的方法;

而对于大于 512 字节的空间申请采用的是最佳适配算法;对于大于 64 字节而小于 512 字节的,它会根据情况采取上述方法中的最佳折中策略;对于大于 128KB 的申请,它会使用mmap 机制直接向操作系统申请空间。

有没有办法既不影响所有thread又不会给开发者增加太多的负担呢? 答案当然是有的,比如: 我们可以在函数调用处插桩, 每次调用的时候检查当前栈的空间是否能够满足新函数的执行,满足的话直接执行,否则创建新的栈空间并将老的栈拷贝到新的栈然后再执行。 这个想法听起来很fancy & simple, 但当前的Linux thread模型却不能满足,实现的话只能够在用户空间实现,并且有不小的难度。

go作为一门21世纪的现代语言,定位于简单高效,充分利用多核优势,解放工程师,自然不能够少了这个特性。它使用内置的运行时runtime优雅地解决了这个问题, 每个routine(g0除外)在初始化时stack大小都为2KB, 运行过程中会根据不同的场景做动态的调整。

栈收缩不是在函数调用时发生的,是由垃圾回收器在垃圾回收时主动触发的。基本过程是计算当前使用的空间,小于栈空间的1/4的话, 执行栈的收缩,将栈收缩为现在的1/2,否则直接返回

一旦 Goroutine 使用的内存越过了分段栈的扩缩容阈值,运行时就会触发栈的扩容和缩容,带来额外的工作量;

在内存空间中分配更大的栈内存空间;
将旧栈中的所有内容复制到新的栈中;
将指向旧栈对应变量的指针重新指向新栈;
销毁并回收旧栈的内存空间;

在 GC 期间如果 Goroutine 使用了栈内存的四分之一,那就将其内存减少一半,这样在栈内存几乎充满时也只会扩容一次,不会因为函数调用频繁扩缩容。

type stack struct {
    lo uintptr
    hi uintptr
}

编译器会在编译阶段会通过 cmd/internal/obj/x86.stacksplit 在调用函数前插入 runtime.morestack 或者 runtime.morestack_noctxt 函数;

运行时在创建新的 Goroutine 时会在 runtime.malg 函数中调用 runtime.stackalloc 申请新的栈内存,并在编译器插入的 runtime.morestack 中检查栈空间是否充足;

var stackpool [_NumStackOrders]struct {
    item stackpoolItem
    _    [cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize]byte
}

type stackpoolItem struct {
    mu   mutex
    span mSpanList
}

var stackLarge struct {
    lock mutex
    free [heapAddrBits - pageShift]mSpanList
}

运行时使用全局的 runtime.stackpool 和线程缓存中的空闲链表分配 32KB 以下的栈内存,使用全局的 runtime.stackLarge 和堆内存分配 32KB 以上的栈内存,提高本地分配栈内存的性能。

  1. 如果栈空间较小,使用全局栈缓存或者线程缓存上固定大小的空闲链表分配内存;
  2. 如果栈空间较大,从全局的大栈缓存 runtime.stackLarge 中获取内存空间;
  3. 如果栈空间较大并且 runtime.stackLarge 空间不足,在堆上申请一片大小足够内存空间;
上一篇 下一篇

猜你喜欢

热点阅读