内存管理

内存管理功能

接下来就是重头戏了, 严格来讲这是将堆的管理功能

上节课说到一个程序运行之后, 它好像占据着一片连续内存空间, 这个空间里面放有代码正文和数据以及一些其它各种分区. 再往上的话就是放了你的堆, 自顶往下就是放了你的栈.

栈已经讲过了, 现在我们讲堆. 堆就是程序运行的时候, 你动态分配的那些空间, 就是分配到堆的上面.

什么叫动态分配, 就是 C 函数中 alloc, calloc, malloc 之类分配出来的内存, 都放在堆上面的, 这也就是程序动态分配的. C 语言中的这些函数就是操作这块区域的.

当前堆的地址上线被称为 system break, 就是堆自底往上涨, 当然总得有一个上限, 那么过了这个上限就需要再分配才能使用. 上限之下可以直接使用, 因为已经分配给你了.

system break 可以通过系统调用, 叫作 brk(0). 或者通过 libc 函数 sbrk(0) 也可以获得你这个 break 这个上限的地址.

system break 这个上限地址是可以按需调整的, 那如果是系统调用 break 的话, 它是给你一个绝对的地址. 比如说我要指明当前 break 在这, 我要让它往上走一走, 那么就需要把这个地址做一个绝对值, 指示系统去调整它.

当然这里面有一个问题就是, 你怎么知道你应该调整到哪里去. 所以你肯定一般是先通过 brk(0) 来获得当前的值, 当前值是绝对值, 绝对值加一个数或者减一个数获得另外一个值, 再调用这个 brk 去设置到一个新的 system break.

注意, 返回的 system break 这个地址本身, 包括这个地址往上都是不能直接访问的. 因为它给了你一个堆的上限, 就是返回的这个值本身又刚好是这个上限. 这个上限或者再往上, 就不能被直接访问, 因为它还没有分配给你.

系统调用 : brk

这个 brk 系统调用是 45 号, 它有一个唯一的参数, 通过 ebx 来输入. 这个输入值是想要设置的新的 brk 地址, 这是个绝对的地址, 所以说你不知道的话, 可以通过 brk(0) 来获得当前地址, 然后再加一个数或者减去一个数, 调整一下.

返回成功的话, eax 里面就是新的 system break, 否则返回当前的.

• Call No.45 (%eax)
  • Input
  • %ebx : 想要设置的新的 break
  • Output
  • %eax : 如果成功, 就返回新的 system break ; 否则就返回当前的 system break

注意 : 失败时, 与 libc 库里面同名调用的返回值不一样

---

那么堆的好处是什么呢, 它提供了一个用户进程可用的连续的内存空间, 其上限可动态调整, 但是系统调用本身无法提供灵活高效的内存分配 / 释放等管理功能.

实际上我们在 C 里面这些 malloc free 这些函数其实都是由 libc 实现的.

这种情况下我们想通过汇编来实现这种内存管理模块, 模块提供两类接口 :

• 分配 (输入 : 所需的内存大小 ; 输出 : 分配的内存地址)

  • 可用的内存块如何跟踪和定位 ?
  • 如何选择合适的内存块进行分配 ?
  • 碎片如何处理 ?

• 释放 (输入 : 想要释放的内存地址)

  • 如何知道该指针指向的内存块的大小 ?
  • 如何复用释放的内存块 ?

简单示例 1 - External Fragmentation

这个例子, 假设有这么一个连续的内存空间, 每一格是一个单位的内存大小, 一共这么多个.

然后我假设我自己设计了一套内存分配和释放算法. 首先分配了 4 块内存出去, 那从里面找 4 块, 再紧挨着又分配了 5 块出去, 再紧挨着又分配了 6 块.

然后呢我把第 2 块内存释放掉, 1 2 3 4 5, 所以 dealocate(p2) 中间这块就空出来了, 这块是 available free 的. 前后都有.

然后我要是再分配一块 6 行不行呢 ?

从整个空余的块数来说, 一共有 7 块, 但问题是你没有一个连续的 6 块, 只有 5 块加 2 块, 所以你分配不出来一个 6. 这就叫做外部碎片, 就是在你分配出去内存块之外的一些碎片, 这些碎片合起来足够大, 但是每一个又比较小, 没法满足你后续分配的需求.

简单示例 2 - Internal Fragmentation

还有叫作内部碎片, 我们可以想想看, 一个内存块的自身, 肯定带有一定结构的.

因为你不能是一个指针来指示它, 这个指针比方说它指向这个 payload, 就是说你用户数据存在这个地方, 但你前后有一定的结构, 包括你的长度是多少, 你下一块的内存地址是在什么地方, 肯定是有些内部结构的.

这个结构的本身, 相当于这个你分配出来的内存块, 内部的一些碎片化, 不能被你充分使用, 是用于管理用的, 所以它有两种碎片化的问题, 一个是外部, 一个是内部的碎片化.

所以说我们要做一个内存分配程序的话呢, 这两块问题是要好好解决的, 你程序的效率在很多情况下取决于这两个问题.

内存管理功能示例, 实现两个函数

我们要实现内存管理功能, 实际上就是堆的管理功能, 要实现两个函数, 一个是分配, 一个是释放.

• allocation 分配

  • 从堆的起始地址开始, 遍历每个内存块

  • 如果某一块标记为 "可用" 且其尺寸不小于所需求的大小, 则将其标为 "不可用", 并返回其数据块的地址, 结束

  • 否则继续遍历, 如果没有合适的块, 则通过系统调用增长 system break, 将新块标记为 "不可用", 并返回其数据块的地址, 结束.

首先我们可以想象, 我们肯定是要在堆里形成一个类似链表的结构

我们要分配的时候, 肯定是从链表头开始查, 最笨的方法, 一个一个往下查, 查到哪一块是空闲的, 同时它的长度又足够, 我们就把它分出来.

• deallocate 释放

  • 直接置相应的标志位为 "可用"

---

我们从堆当前 system break 起始地址开始, 遍历每个内存块, 如果某一个内存块标记为 "可用" 的, 同时它是 free 的, 没有被分配掉的, 而且其尺寸足够, 就将其标为 "不可用", 并返回其数据库的地址结束.

否则就去遍历, 一直到找不到为止. 如果一个都找不到, 那么就通过系统调用增长你这个堆的上限, 因为都不够用嘛, 那么就把堆的上限往上涨一涨, 你要多少就涨多少, 然后再把这一块分给你就行了.

那如果释放的话, 就把相应的标志位标记为 "可用".

---

比方说如图

一个块的长度, 一个块的单元是这个样子

你真正分配出来的数据是 payload, 真正人家能用的数据块在这.

你前面应该有两个头, 头里面有两个元数据, 是管理用的. 一个是标识它当前是不是已经被分配出去了; 另一个标识你的块长度是多少.

你在块长度之后呢, 相当于一个指针式了, 你可以找到下一块的地址了.

代码

section .data
                  # This points to the beginning of the memory
heap_begin:
.long 0
                  # This points to one location past the memory we are managing current_break:
.long 0

                  # size of space for memory region header
.equ  HEADER_SIZE, 8
                  # Location of the "available" flag in the header
.equ  HDR_AVAIL_OFFSET, 0
                  # Location of the size field in the header
.equ  HDR_SIZE_OFFSET, 4

.equ  UNAVAILABLE, 0
.equ  AVAILABLE, 1
.equ  SYS_BRK, 45 # System call number for brk
.equ  LINUX_SYSCALL, 0x80

这个是开头的一些定义我们就不去说它了.

---

# alloc.s
.section  .text

.globl  allocate_init
.type allocate_init,@function
allocate_init:
  pushl %ebp
  movl  %esp, %ebp

  # If the brk system call is called with 0 in %ebx, it returns the last valid usable address
  movl  $SYS_BRK, %eax  # 获得当前堆的上限地址
  movl  $0, %ebx
  int $LINUX_SYSCALL
  decl  %eax  # %eax now has the last vali address
  # 当前堆的上限地址放在 eax 里面, eax 首先要做一个减一, 因为我们说过当前这个上限实际上是不可用的, 我们减去一才可用.
  movl  %eax, current_break # store the curren break, 把当前堆的起始地址搁到这里面
  movl  %eax, heap_begin

  movl  %ebp, %esp  # exit the function
  popl  %ebp

然后就是我们最终要做的这个 allocate 这个函数了

.globl  allocate
.type allocate,@function
.equ  ST_MEM_SIZE, 8  # stack position of the memory size to allocate
# 它里面有一个参数, 参数是你要分配的内存的大小是多少
allocate:
  pushl %ebp
  movl  %esp, %ebp
  movl  ST_MEM_SIZE(%ebp), %ecx # %ecx will hold the size
# 通过传参传进来, 把它放到 ecx 里面去
# 然后我们开始查找, 一个个遍历
# we are looking for (which is the first and only parameter)
  movl  heap_begin, %eax  # %eax will hold the search location
  movl  current_break, %ebx # %ebx will hold the current break
# eax, ebx 分别赋值成当前堆的起始地址和当前 break 这个地址减去 1

loop_begin: # we iterate through memory regions
  cmpl  %ebx, %eax  # need more memory if these are equal, 这两个相等就说明我们遍历到了你这个 break 的上限了, 就是你所有空间去找都没有找到, 只能去移动这个上限了
  je  move_break

  # grab the size of this memory
  movl  HDR_SIZE_OFFSET(%eax), %edx # 如果你 break 不用涨的话, 我们还是把当前这个地址, eax 就是这个当前地址嘛, 就是 eax + HDR_SIZE_OFFSET, 把当前的我们所在遍历的内存块, 先把这个内存块里面的标志位给它取出来

  cmpl  $UNAVAILABLE, HDR_AVAIL_OFFSET(%eax)
  je  next_location # If unavailable, go to the next, 这个标志位如果发现是 unavailable 的 不可用的, 就是已经分配出去了, 那我们就继续往下走
  cmpl  %edx, %ecx  # If available, check the size
  jle allocate_here # big enough, go to allocate_here
  # 如果可用, 就比较一下, edx ecx 如果是小于等于的话, 也就是你找到的这个内存块是足够用的, 你就在这分配就完了, 如果不是小于等于的话, 我们就去查找下一个内存块.

next_location:
  addl  $HEADER_SIZE, %eax
  addl  %edx, %eax  # The total size of the memory
  jmp loop_begin  # go look at the next location

allocate_here:
  # If we've made it here, that means that the region header header of the region to allocate is in %eax, mark space as unavailable
  movl  $UNAVAILABLE, HDR_AVAIL_OFFSET(%eax)
  addl  $HEADER_SIZE, %eax  # move %eax to the usable memory, 因为内存块分为块头和 payload, payload 的起始地址, 才是我们要返回的那个可用的数据地址

  morl  %ebp, %esp
  popl  %ebp
  ret

# 再往下就是, 如果当前堆已经遍历完了, 还不够用, 就把上限调整一下 :
move_break:
  addl  $HEADER_SIZE, %ebx  # add space for the headers structure
  addl  %ecx, %ebx  # add space to the break for the data requested

  pushl %eaz
  movl  $SYS_BRK, %eax  # reset the break
  int $LINUX_SYSCALL
  popl  %eax  # no error check ? 因为这里是示例程序所有没有错误检查

# set this memory as unavailable, since we're about to give it away
  movl  $UNAVAILABLE, HDR_AVAIL_OFFSET(%eax)  # set the size of the memory
  addl  $HEADER_SIZE, %eax  # move %eax to the actual start of usable memory.
  movl  %ebx, current_break # save the new break

  movl  %ebp, %esp
  popl  %ebp
  ret

刚才是分配, 现在是释放, 释放比较简单 :

.globl  deallocate
.type deallocate,@function
.equ  ST_MEMORY_SEG, 4

deallocate:
  movl  ST_MEMORY_SEG(%esp), %eax
  # get the pointer to the real beginning of the memory
  subl  $HEADER_SIZE, %eax
  # mark it as available
  movl  $AVAILABLE, HDR_AVAIL_OFFSET(%eax)

  ret

释放函数有一个参数, 就是给个指针, 指针指向内存块

该内存管理效率低

这个内存管理实际上效率非常低

• 分配时遍历所有的内存块, 复杂度为 O(n)

• 每次调用 brk 只是分配所需的内存大小, 会导致系统调用次数过多

实际上每次 brk 的时候, 如果有一次发现不够用, 可以一次性多分配一点, 留到以后用

• Internal Fragmentation
  释放时应将相邻的 available 块合并

但是我们释放的时候没有进行合并

• 如何改进 ?

留作作业

如何使用

那么这作业里面怎么去做

假设就是给大家提个要求, 我们在上节课讲到, 读写记录文件的时候, 以前我们通过在这个 bss 里面, 声明了几个 (实际上是静态声明), 静态保留了几个空间, 这个空间比方说是 RECORD_SIZE, 大概 300 多字节用于进行数据的读写.

现在假设说如果我们自己去实现一个内存分配, 也就是堆管理的这个函数, 这个函数之外, 我需要把原来程序改改, 就是不要在文件这里给写死了, 多大就保留下来.

就是我们要在运行时动态分配有效内存, 内存大小可变了, 然后拿它这块内存地址, 由它来指向, 由record_buffer_ptr point 来指向

就是说你 buffer 原来一种写法, 现在另一种写法, 把它变成一个指针, 动态给它分配一个大小出来

这边我们想想看, 当时上节课在 read-record.s 里面, read-record buffer, 我们给它作为一个常量 push 这么去用. 那么我们如果采用这种方式的话, 相对应的这些指令所完成的功能, 如果我们把 record_buffer 替换成 record_buffer_ptr 变成动态分配一个指针的话, 那么这个代码该怎么写, 大家去想想看