技能系统中的循环控制

动作循环控制

• 动作类技能, 普攻等依赖战斗单位身体动作的技能, 其受影响的身体部位不能同时做出两个动作
• 根据技能的价值级别以及特色设计, 在可能导致冲突的两个动作之间需要明确打断关系

设计策略

无论是时间线的设计还是多段设计亦或是朴素的单段多子技能设计, 我们需要标记出每段动作的影响部位, 其意义是在于我们对所有技能通过打标记的形式来获得’技能与技能之间是否存在动作冲突’的信息.

其次, 我们需要对冲突的技能之间的 重叠释放问题, 这里本质上是一个压制规则问题.

1. 冲突的动作类技能一旦释放成功, 一定打断掉所有相关旧的技能
2. 如果不做上下半身分离, 普通移动视为动作, 否则为下半身动作
3. 不希望被某些类型打断的时候 要禁止这些类型的技能释放 即压制类标签

举例来说

• 跳击技能:

  • 技能类型: 上半身动作, 下半身动作
  • 前摇时间压制: 禁止普通移动 禁止下半身动作 禁止上半身动作

• 出拳技能

  • 技能类型: 上半身动作
  • 前摇时间压制: 禁止上半身动作

• 闪避技能

  • 技能类型: 上半身动作 下半身动作
  • 前摇时间压制: 禁止普通移动 禁止上半身移动 禁止下半身移动

注意: 有些闪避是特色玩法 则需要额外的标签和流程来完成
闪避技能进行条件判定时先使用脚本进行预判, 如果当前存在会因动作压制闪避的技能 则先进行打断, 防止被压制
所有动作类技能额外添加是否可被闪避技能打断的标签, 单独完成闪避相关的压制处理.

设计小结: 本质上动作类循环的控制, 在流程上首先是模拟动作状态机, 其次通过压制策略对状态机的切换策略进行控制

脚本设计

前言和需求情景

每种语言都有自己的惯用思维, 面对领域需求时, 也应该在不同的语言思维环境下寻找解决方案, 而不是生搬硬套另外一种语言的特性, 但是从可计算性的角度上来看, 相同需求的良好解决方案往往具备很强的相似性.

那么更具体的领域中, 我们说说技能系统的场景:

技能系统的复杂度偏向问题域, 如果不去约束问题域的规模, 最好的解决方案一定是通过脚本化方式让技能的设计者直接去写设计者期望的战斗逻辑. 但是作为一门通用的语言, 是需要转化为一个简洁的, 低门槛的领域语言.

这里不讨论如何拆解该系统所面对的问题域, 如何抽象出解决域的模型等, 这部分在之前的技能系统相关的PPT中已经描述过, 这里主要关注的是, 在使用脚本的情况下, 我们如何对脚本这部分进行更具体的设计.

• 作为开发者, 更关注的是开发测试成本, 即用最简洁的代码, 一劳永逸的提供最丰富的上层接口.
• 作为设计者, 更关注的是是否提供了足够的封装, 隐藏掉不需要关心的功能实现细节以及流程细节, 并且能够总是通过简单的if else call来完成所有决策, 或者用简单的枚举或者画图 打钩完成所有决策而不需要操刀脚本编写.

• 更进一步的, 从设计者角度, 按照配置的出场频度和复杂度应该有如下的方案选型排序:
  • 几乎总是需要配置的: 默认配置方案, 什么都不需要做就是应该有的功能或者流程
  • 次高频: 通过开关来切换功能或者流程
  • 高频: 通过枚举来完成多功能或者多流程case
  • 高频低中度复杂: 通过枚举+固定的跟随参数来完成
  • 高频低中度复杂: 开发人员编写特定的功能模块, 条件模块, 并提炼出参数以特定枚举方式提供
  • 中低频复杂条件: 嵌入简短的脚本, 通过数据接口+脚本提供的布尔表达式来完成
  • 中低频复杂逻辑: 开发人员协助设计者编写脚本
  • 中低频中低复杂: 策划自行写脚本 自行验证
  • 低频其他: 脚本兜底实现

• 对于中小型硬核技能玩法项目 或者设计者本身有一定的编程功底, 那么我们可以实现一个简洁的脚本驱动的内核, 然后任由设计者天马行空的设计和铺展战斗系统.

• 但对于另外一些情况, 比如存在大规模的低复杂度技能设计, 或者策划人员对脚本的接受能力参差不齐, 我们需要对脚本的适用范围进行收敛, 但是仍然想要灵活的机制来实现丰富的技能体系. 这就需要对涉及到脚本编写部分的更具体的优化设计.

  • 直接提高数据驱动部分的配置在整个技能系统下所包含的范围

    通过堆开发人力来提高. 但是这部分会随着需求的细化和新需求的提出导致不断的重构, 开发人员需要持续跟进
    持续变更的核心代码会降低整个系统的稳定性, 因此这部分的工作需要克制,谨慎的拆解,分析,以及交付测试.

  • 把可以简单替换成脚本的逻辑, 给设计者提供数据驱动的配置接口, 在配表完成阶段或者读取配置阶段翻译成脚本

    相比上面的方案, 该方案不需要修改核心逻辑, 性能略有下降.

  • 提供脚本片段/脚本模版, 配置时候快速复用已有脚本逻辑

    相比上面一条, 该方案设计者可见脚本代码, 但是不需要手写.
    不容易出错, 可以用来熏陶设计者对脚本的接受能力, 降低脚本门槛.

  • 提供脚本级别的封装机制, 对脚本复杂度进行降级

    把复杂的脚本实现拆解成独立的多段脚本函数, 一次测试多次复用
    把多行脚本能完成事情 封装成一行脚本 或者一个函数+参数的形式
    把简单的脚本映射成数据驱动的枚举+参数形式 (直接映射为封装好的函数+参数)
    封装的位置单独存放在脚本文件中, 并且支持热更新方便快速试错和验证

内存分配器核心思想和算法

内存管理策略

Sequential Fit (连续适配)

是基于一个单向或双向链表管理各个blocks的基础算法，因为和blocks的个数有关，性能比较差。这一类算法包括Fast-Fit, First-Fit, Next-Fit, and Worst-Fit。

Segregated List (分离列表)

将所有的空闲块，放入到一组链表中，每一个链表中只包含某一个大小范围的空闲块

• Buddy System (Sequential Fit变种)
  • 内部碎片化问题比较严重
  • Binary Buddies
  • Fibonacci Buddies
  • Weighted Buddies

Indexed Fit

通过一些高阶的数据结构来索引（Index）空闲的内存块。例如基于平衡树的“Best Fit”算法。

• 使用Balanced Tree的Best Fit allocator
• 使用Cartesian tree 的Stephenson Fast-Fit allocator
• Bitmap Fit (Indexed Fit 变种)
  Indexed Fit算法的变种，通过一小段内存的位图来标记对应的内存是空闲的还是使用中。

路径匹配策略

对于操作系统而言, 除了管理进程之外, 还需要有效的管理计算机的主内存, 管理主内存的共享使用和最小化内存访问时间是内存管理器的基本目标. 虽然使用了各种不同的策略来为争夺内存的进程分配空间，但最流行的三种策略是最佳匹配、最不适合匹配和首次匹配.

• Best fit:
  The allocator places a process in the smallest block of unallocated memory in which it will fit. For example, suppose a process requests 12KB of memory and the memory manager currently has a list of unallocated blocks of 6KB, 14KB, 19KB, 11KB, and 13KB blocks. The best-fit strategy will allocate 12KB of the 13KB block to the process.
  最佳匹配:
  这种匹配策略中, 分配器会从满足匹配要求的未分配内存中选择最小的块.
  例如程序请求一个12kb的内存, 而当前的内存管理器有一个未分配的内存块列表, 分别为14k, 19k, 11k, 13k, 那么best-fit讲从13k的内存块中分配内存给程序.

• Worst fit:
  The memory manager places a process in the largest block of unallocated memory available. The idea is that this placement will create the largest hold after the allocations, thus increasing the possibility that, compared to best fit, another process can use the remaining space. Using the same example as above, worst fit will allocate 12KB of the 19KB block to the process, leaving a 7KB block for future use.
  最不适合匹配
  内存管理器总是选择获得的最大的那个未分配内存块.
  这种策略在每次分配后总是持有最大的内存块, 从而增加匹配的可能性. 与最佳匹配相比, 其他的请求可以使用剩余的空间.(最佳匹配的剩余内存往往无法利用)
  同上例, 最坏匹配会从19k的那个内存块中分配, 并留下7k的内存留给将来使用.

• First fit:
  There may be many holes in the memory, so the operating system, to reduce the amount of time it spends analyzing the available spaces, begins at the start of primary memory and allocates memory from the first hole it encounters large enough to satisfy the request. Using the same example as above, first fit will allocate 12KB of the 14KB block to the process.
  通常内存中会存在很多空洞, 所以操作系统为了减少分析可用空间的性能(时间)消耗, 会从主要内存或者 第一个足够大并且满足求要的可分配内存的起始位置相应请求.
  同上例中, 首先匹配会从14k的block中分配12k的请求.
  First Fit的一个改良版本叫做Next Fit, 即在下次请求时会从上次中断的地方的开始搜索, 从而避免总是从起始的空闲内存开始查找. (Designated victim), First Fit的策略会倾向于总是把大块切的更零碎也因此带来更多的外部碎片问题, 也因为总是从空闲内存的头部开始切造成更多的内部碎片, 而Next Fit的做法会避免(改良)这些问题, 并且速度比Firt 以及 Best更快.

TLSF: a New Dynamic Memory Allocator for Real-Time Systems

通过一组链表来管理不同大小内存块的内存分配算法。
适用环境和要求:
内存分配/释放的执行时间可预期，可接受的。由于RTOS对指令的执行时间有严格要求，所以常常采用静态内存分配的方法，以获得一个可以预期的执行时间。
内存分配算法的碎片化程度要低，这是由于RTOS往往长时间执行，碎片化程度高会导致内存分配失败。
实时系统动态内存算法
可信的执行环境，Trusted Environment，应用不会故意破坏数据或者窃取数据。
有限的物理内存。
没有物理MMU来支持虚拟内存。

核心概念: Two Level
基本的Segregated Fit算法是使用一组链表，每个链表只包含特定长度范围来的空闲块的方式来管理空闲块的，这样链表数组的长度可能会很大。如下图，TLSF为了简化查找定位过程，使用了两层链表。第一层，将空闲内存块的大小根据2的幂进行分类，如（16、32、64…）。第二层链表在第一层的基础上，按照一定的间隔，线性分段。比如2的6次方这一段，分为4个小区间【64,80），【80,96），【96,112），【112，128）.每一级的链表都有一个bitmap用于标记对应的链表中是否有内存块。比如第一级别bitmap的后4bit位0100，即2的6次方这个区间有空闲块。对应的第二级链表的bitmap位0010及【80,96）这个区间有空闲块，即下面的89 Byte。

策略:
Immediate coalescing，立即合并，当内存块被释放后，立即与相邻的空闲内存块合并，以获得一个更大的空闲块，插入到链表的相应位置。这样可以减少碎片化。
Splitting threshold，分割阈值，最小可分配的内存块大小为16字节，应用一般不会分配一些基本的数据结构，如int、char等。限定最小可分配大小为16字节，这样可以在空闲的内存块中存储一些管理信息。
Good-fit strategy，TLSF会尽可能的返回一个最小的、能够满足需求的内存块。
Same strategy for all block sizes，对于不同大小的内存请求，TLSF只有一个分配策略，实现相对简单，执行时间可以预期。相应的dlmalloc根据所请求的内存大小不同，有多达4种内存分配策略。
Memory is not cleaned-up，分配个应用的内存没有被请0.

特点:
可以预期的分配执行时间，无论对于多达的内存分配请求，TLSF可以在限定的时间内完成分配。
碎片化程度低。

mimalloc:

多线程

• 局部化, 本地缓存/链表
• 注意false shared
• 跨线程队列 最大本地缓存

内存安全

管理数据和被管理内存分离
buddy system
pages 管理

可信的执行环境Trusted Environment，应用不会故意破坏数据或者窃取数据
有限的物理内存
有限的物理地址
没有物理MMU来支持虚拟内存

开源内存分配器

• dlmalloc
• tcmalloc
• jemalloc
• Hoard
• minimalloc
• TLSF: https://github.com/OlegHahm/tlsf

援引

jemalloc深入分析 PDF
jemalloc 2015演讲视频 tick tock, malloc needs a clock 背景和初始设计思想介绍
jemalloc facebook工程贴
BSDcan paper 2006
On the Impact of Memory Allocationon High-Performance Query Processing
How tcmalloc Works
Chromimum Project: Out of memory handling
Scalable Memory Allocation TBB
ptmalloc,tcmalloc和jemalloc内存分配策略研究

shadowsocks服务器配置

• 安装shadowsocks

  1	apt-get install shadowsocks

• 配置shadowsocks
  配置路径

  1	/etc/shadowsocks/config.json

• 配置内容(参考):

  1 2 3 4 5 6 7

  { "server":["::1", "0.0.0.0"], "mode":"tcp_and_udp", "server_port":8080, "password":"****", "method":"aes-256-cfb" }

  Read more »

..1. 目录

通用的对象池方案

该方案本质上一个简单分离存储的内存分配方案:
分配器维护多个空闲链表, 每个空闲链表包含大小相等的空闲块 每个块的大小为这个大小类中最大元素的大小, 不分割不合并.

数据结构定义

1
2
3
4
5

对象池管理器
  [对象A条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象B条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象C条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数   
  [对象D条目IDX]: 对象是否包含虚函数(是否需要重建虚函数表):  对象类型(对应条目IDX): 对象大小: 对象个数: 该条目总长: 条目对应内存地址:  条目对应对象起始地址: 空闲对象下标ID : 已分配计数

单个条目指向的起始地址结构:

1

flag|flag|flag : ...  FENCE SIZE: NODE SIZE :   FENCE SIZE: NODE SIZE :   ...

条目指向的地址会首先保存flag标志标明该对象是否在使用中, 用于请求和释放时候的判定标志
NODE SIZE会进行8字节对齐, FENCE SIZE也选择8字节 这样整个对象池的地址都是保证8字节对齐的
FENCE写入特殊固定的魔法数值 用于溢出检测
分配出去的对象 NODE SIZE的起始地址即为对象的地址
空闲的对象, 其NODE SIZE的第一个U32保存的是下一个空闲内存

1
2

: NODE SIZE: 对应下面结构
: FREE IDX, NODE SIZE- FENCE SIZE:

..1. 目录

linux系统的内存管理设计

Linux内核内存管理的一项重要工作就是如何在长期频繁申请释放内存的情况下, 避免碎片的产生.
Linux采用伙伴系统在极高的分配和回收性能(LGN)上, 最大化的减少了外部碎片(总是合并伙伴内存)的产生.
伙伴算法非常简洁并且容易实现, 其一般实现的核心思路为维护一个整块内存, 通过不断的2分把最适配的内存分配给用户, 并且总是优先选择最零碎的空闲内存进行适配, 在回收时候则总是会合并空闲的伙伴内存(左右两个子节点的关系称之为伙伴关系), 以此来尽可能的保证大块的连续内存.
但是伙伴算法要求分配的内存必须是2的幂次大小, 因此直接使用会带来大量的内部碎片, 也因此伙伴算法一般都是作为底层内存管理算法不直接提供给用户, 而是通过dlmalloc等slab算法或者衍生算法提供给最终用户.

linux采用slab算法来进行更细粒度的内存分配管理, 通过分箱算法, 对于小内存(256字节及以下, 分离存储)可以达到常数的性能, 对于 >256 && <1m的内存可以做到不大于LGN的分配性能, 并且通过对大块内存的精细切分和分箱算法可以做到几乎没有内部碎片, 通过对空闲内存的合并(没有伙伴关系约束也不存在假碎片问题, 但是因为大小chunk混合切分带来了更多的合并次数) 也有效的控制了外部碎片的产生.

linux面对的环境在通用性上要求更高, 考虑到brk/mmap作为系统调用在一些环境下的性能差异表现, 以及小内存的在初始化数据(查找 切分等), slab相关的算法中更倾向于缓存足够多的block来保证小内存在分配上的性能表现, 而操作系统heap苛刻的收缩条件也会导致在项目中的实际表现往往是整个heap的内存总是接近保持在峰值水平上, 换句话说slab算法在实际的实现中其分配策略更接近’内存池’的概念.

其分箱算法采用64位的bitmap 也就是64个箱位, 支持单个内存分配请求的大小范围在dlmalloc的实现中为8字节-1M, 又因为内存池的分配策略, 以及外部碎片的有限控制, 所以slab只是一个针对小内存分配优化方案, 对于一个通用分配器来说仍然需要大内存的分配方案.

因此包括linux内核, 整体的通用内存分配方案中, 使用buddy算法或者衍生算法来做大块线性地址空间的管理, 保证性能的情况下最小化外部碎片的产生, 通过slab算法或者衍生算法维护一个小内存请求的内存池, 以增加一小部分外部碎片的代价换取更少的内部碎片产生, 并保证向buddy system索要的内存都是满足2的幂次大小, 从而得到一个综合性能最优的方案, 这个方案比喻成[buddy算法负责批发 slab算法负责零售]具有比较形象的参考价值.

伙伴算法

因为最终的目的是希望把伙伴算法的管理结构保存在共享内存中, 因此我们在数组结构上以完美二叉树(perfect binary tree)的方式构建了整个伙伴算法, 由于对cpu cache友好的特征, 并且全局几乎只有简单的加减位移操作, 所以整个实现可以在非常简洁的基础上得到了一个比较出色的性能表现.

数据结构和概述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/*  perfect binary tree
*                   0        -----------   : reserve
*	                  1        -----------   :  root 
*
*          2                 3
*
*     4        5         6        7
*
*   8   9   10   11   12   13  14   15
*
* ----------------------------------------
*
*   0   1   2    3    4    5   6     7     : memory buff
*
*/

伙伴算法是一个特殊的分离适配的内存管理器

• 能被有效管理的内存大小必须是2的幂次方

• 分配的内存大小一定是2的幂次大小对齐, 通过逐层向下2分找到最适配请求的大小

• 回收的内存会逐层向上合并 并且总是幂次大小合并 并且只能对伙伴内存(左右子节点)进行合并

• 显而易见的内部碎片
  因为2的幂次对齐分配, 比如我们需要power(2, 12)+1 的内存 实际上就会分配power(2,13)的内存, 内部碎片比例为 (power(2, 12)+1)/power(2,13), 有效负荷只有0.5左右.
  伙伴系统的分配粒度如果为页框机制, 例如采取页框大小为4k(方便匹配操作系统的页大小), 那么即使请求1个字节也需要一个完整的页框内存, 有效负荷只有1/(4k-1)即4k分之一.

• 显而易见的假碎片
  两块相邻的空闲内存因为不属于伙伴关系则无法合并, 换句话说存在一块连续的空闲地址满足需求但是却因为无法在内存管理器中完成合并操作而不能提供服务.
  比如上面结构中 IDX 9 和 IDX 10皆为空闲, IDX 9 和 IDX 5皆为空闲等

• 存在但被有效控制的外部碎片
  对于动态内存分配策略中, 只要满足通用性目标中”处理任意请求序列” 那么就一定会有外部碎片的产生, 因为其产生不仅仅在于分配器管理结构的设计, 更在于将来时, 外部的请求和释放时机.
  如图所示中, 我们并不能保证不会出现索引11和12被分配出去其他内存全部空闲这样的情况, 导致总空闲内存大小为6但是只能最大分配3个连续页框 .
  但相比其他的分配方案, 合并成一个2倍大小的大块内存, 总是只需要两个空闲小块, 而在分配策略中又总是会分配大小相同且相邻的块, 可以说是所有分配策略在保证LGN性能下控制外部碎片最好的方案.

• 较为恒定的分配复杂度
  分配时会从根节点向下查找直到适配, 回收时从叶子节点向上查找, 并且都会从对应节点向根节点方向进行分配能力的修改.
  因此一对分配和释放请求总是恒定为LGN

数据结构的定义:

同linux系统的方式类似, 我们按照页框为单位来管理内存, 页框的大小大于等于系统的页框大小, 可结合slab分配器进行调整.
根据要管理的内存大小和页框大小, 我们可以算出总得叶子数量, 而在这棵树上, 节点总数为2N(2倍叶子节点)

因此数据结构的定义为如下方式:

1

共享内存管理头部: 所有叶子节点 : 被管理的内存

每个节点用1个字节来记录, 内容为该节点的所对应的空间大小, (这里记录的不是大小, 而是大小的幂, 所以可以用一个字节来存储)
该节点对应的空间起始地址这位该节点在该层中的offset* power(2, order)

初始化

所有节点的初始化为为该节点的空间大小.
例如index1 对应的则是被管理的所有空间
然后每层递减1
到叶子节点则为2^0次幂大小, 即一个页框单位.

分配

如果分配参数是字节数, 则需要先按照页框向上取整
如果分配的参数是页框数量, 则需要按照2的幂次取整, 可以用bit search指令获取2的幂数(这个取法是向下取整 所以取完后要进行一次向上取整)
如果分配的是order
则检查root节点保存的order是否满足需求, 不满足这代表没有足够大的空间
如果满足需求则逐层查找, 直到到达对应的order层级, 然后修改该节点的可分配空间为0, 然后逐层向上修改分配能力

tips:
这里定义0为已分配, 而不是power(2,0)个空间大小, 因此在这里节点对应空间大小计算是power(2, (order ability)-1) -1后才是power(2, order) .
这样可以保证这棵树中从叶子节点向上查找时候的可以简单的while循环时候少一次边界判定, 计算方便

分配时候永远选择刚好满足需求的路径, 可以减少切分大块, 其次优先左子树, 减少外部碎片的产生以及提高cache命中.

释放

通过地址计算页框编号, 然后加上N (树的大小是2N, N为所有非叶子节点的节点总数) 得到叶子节点的索引.
从叶子节点用IDX /2 不断的向上查找, 直到找到节点被标记为0的层级, 修改该节点为该层级对应的空间大小, 然后逐层向上修改每层的新的空间分配能力, 如果左右节点的空间大小为该层级的大小(都空闲)则合并,(每个上层节点的能力均是节点对应的空间大小)

SLAB内存分配器

有了buddy system之后, 移植所有可以基于mmap或者brk批量分配的内存分配器都会变得容易, 常见的现在linux系统使用的ptmalloc属于dlmalloc的分支版本, 而常用的TCMALLOC或者jemalloc都是基于dlmalloc的思想进行了更优更细粒度的实现, 体现在cpu cache更友好的分配策略以及多线程下更少的竞争等来获取更好的分配性能.

dlmalloc有着更简洁干净的实现 大约只有5000行代码, 其设计也非常的出色, 可以说是最容易移植的优秀的内存分配器.

基础术语和概念如下:

Payload: 有效负载.指的是实际交给应用程序使用的内存大小.

Overhead: 负载,开销.本意是为了满足分配需求所消耗的内存量,实际在代码注释中多指除了payload之外的额外开销(有些书中也称之为cookie).

Chunk: 区块.是内存分配的基本单位,类似物质世界中的原子不可再分. dlmalloc对内存的管理基本上都是以chunk为单位.一个典型的chunk是由用户程序使用的部分(payload)以及额外的标记信息(overhead)组成.

Bin: 分箱.用来管理相同或同一区间大小的chunk.在dlmalloc中分为sbin和tbin两种.

Mspace: 分配空间.说白了就是dlmalloc中内存池的叫法.在dlmalloc中可以管理多个mspace.如果不显式声明,将会使用一个全局的匿名空间,或者用户可以自行划分空间交给dlmalloc管理.

Segment: 区段.一般情况下,内存分配都是在一片连续区间内开采(exploit).但也会遇到不连续的情况,这就需要分成若干个区段记录.多个区段可以同属一个mspace.

Fenceposts: 栅栏.大多数分配器中, fencepost起到非连续内存间的隔离作用.一般这种隔离被用做安全检查.分配器会在fenceposts所在位置写上特殊标记,一旦非连续内存间发生写入溢出(overwrite)就可以通过异常的fenceposts值发出警告.

Bookkeeping: 记录信息.不同于每个chunk中的overhead,这里指的是整个mspace控制块的记录信息.往往这部分信息都固定在mspace开始的一段空间,或者干脆就放在地址空间的静态区中.

Granularity: 粒度.这个粒度指的是从system heap上获取内存的最小单位.一般来说该值至少为一个page size, 且必须以2为底.

Mmap: 本意是类unix系统的文件映射调用.但在dlmalloc中表示的更宽泛,这里指代可以在进程地址空间中开辟非连续内存空间的系统调用.

Morecore: 指可以在进程地址空间中开辟连续内存空间的系统调用.在类unix系统下morecore指的是sbrk调用.

Program break: 前面提到的sbrk()实际也是一个库函数,真正起作用的是brk()系统调用.这个函数其实就是break的缩写.所谓的break是一个代表进程heap区top-most位置的指针.当我们通过sbrk/brk向系统请求内存时,系统做的仅仅是移动break指针,内存就这样被划拨到heap中了.而当释放内存时,就反方向移动该指针,内存就返回给系统.

Footprint: 从系统获得的内存量.指的是当前dlmalloc从system heap获取的内存总和.设立footprint一方面是为了方便统计,另一方面也可以限制dlmalloc从系统获取的最大内存量.

Trimming: 裁剪.被dlmalloc管理的内存被free后,并不直接返还给系统,而是当积累到一定程度会通过一些算法判断system heap是否收缩(shrink),这个过程在dlmalloc中称作auto-trimming.

分箱机制

分箱指的是在内存分配器内部划定一些chunk集合, 每个集合中记录的都是固定大小或区间的free chunk, 当分配时可以直接从中找到最贴近用户要求的那一个.
越是想要高效的分配,就越要将分箱划分的更细致,相应的也就浪费更多的内存, 因此, 分箱机制既不能太粗放而影响效率, 也不能太细致而降低利用率.
分箱算法通过位移的计算技巧, 可以简单且快速的找到满足请求大小的最小非空箱位索引

小内存分配

dlmalloc定义了最小的分配粒度为8字节, 这样在保存chunk大小的字段中可以多出来3个位作为bit标记
然后每8个字节递增, 直到248字节, 总共32个箱子 如下:

1
2
3
4
5

[bin idx] 8 8 8 8 8 8 8 8 8 
[bin idx] 16 16 16 16 16 16   
[bin idx] 24 24 24 24 24 24   
...
[bin idx] 248 248 248 248 248 248

在64位下需要保证分配给用户的地址是两倍(void*)大小且包含一个8字节的prev_foot 一个8字节的head, 因此实际上使用的箱位不会用满32个.
dlmalloc的prev_foot是一个边界标记法的使用技巧, 逻辑上其实是上一个chunk的foot部分, 如果不是空闲状态则会标记”下个chunk的P”为非空闲, 如果是空闲则会填充该字段为空闲chunk的大小.
这样就可以完成一个块从分配状态到空闲状态时候 总是能直接向前合并或者向后合并.
在非空闲状态没有合并需求, 因此为了充分利用内存, 分配状态的chunk其foot部分总是被’踩’的, 也就是说这里的的箱位使用在实际情况下(64位)
是32byte开始, 后面以24字节递增(踩prev_foot) 48byte 64byte 直到240byte 对于调用dlmalloc接口请求的大小在超过232字节后就会走big bin分配[256~384)范围的内存.

分配:

首先检查对应bin idx是否有空闲chunk 有这分配并返回
其次检查更高bin idx中是否有空闲的chunk, 有则切割, 并把剩余大小组合成一个新chunk记录为切割剩余chunk(如果过小则直接丢给用户)
其次检查大内存的bin里面是否有内存 有则切割 同上
其次检查上次剩余切割的chunk是否满足需要 如果满足则进一步切割 同上
其次检查最新从上级分配器(buddy system, 或者对应系统函数mmap brk)得到的大块chunk的剩余是否满足 满足就切割 (brk表现为扩展top)
其次则申请一个新的大块chunk进行切割

大内存分配

大内存的bin idx递增则为2的幂次的半高为区分 总共32个箱子, 箱内是一个特殊实现的bitwise trie tree 如:

1
2
3
4
5
6
7

[bin idx] [256~384)  
[bin idx] [384~512)  
[bin idx] [512~768)  
[bin idx] ...  
[bin idx] [4096~6144)  
[bin idx] ...   
[bin idx] [768k~1m)

分配:
首先查找对应的bin idx是否存在空闲, 如果空闲则从该bitwise trie tree中查找最佳的chunk节点

如果当前bin无空闲内存或者没找到合适空闲内存, 则检查更高bin idx中是否存在空闲, 如果有则拿最小的一个chunk

如果找到则切分保存剩余内存为剩余chunk并返回合适大小的内存给用户

其次检查剩余chunk的大小是否满足, 满足则进一步切割

其次检查最近一次向上层管理器申请的内存chunk是否满足需求, 满足则切分

其次选择向底层(操作系统)申请满足需求的大块内存

bitwise trie tree

大内存的箱内管理是一个特殊的前缀树, 节点均为0或者1, 和buddy system的结构稍微有点相似 都是做地址空间管理.
这个树的的节点是按照chunk的大小(chunk大小在二进制上的0,1顺序作为排序依据)进行构建的
并且其节点本身就是chunk, 因此查找时候时候不但要检测叶子节点的大小是否最佳 也要检测其节点路径的chunk大小是否是最佳.
添加节点时候会自顶向下查找最佳位置, 如果已经存在大小相同的节点或者叶子节点 则以链表形式附加到该节点的空闲链表中, 如果不存在则直接以叶子节点添加
删除(最佳)节点时, 如果该节点有相同大小的其他chunk 则直接替换为相同大小的即可, 如果是叶子节点直接摘除, 否则会从右侧叶子节点提升到该节点位置.

这棵树的优点是动态树高, 查找的最坏性能是地址空间的LGN复杂度, 在树不满的情况则是相对树高的LGN复杂度, 在插入和删除时只是简单的查找+一次替换/添加操作, 不会对树进行调整, 因此性能非常好.

内存回收和内存收缩

回收内存时会根据标志检查是否存在前一个空闲块 如果存在则合并.
如果是直接mmap的内存 则直接返还给底层分配器
检查是否满足收缩条件, 满足收缩条件则向系统/底层分配器返还内存 这里分heap的堆顶收缩检测和非连续mmap segment回收检测
未被返还给底层分配器则插入到对应的bin空闲块中.

默认内存分配阈值

分配对齐至少8字节 默认为两倍sizeof(void*)
向系统的索要内存的最小粒度默认为64k, windows下通过api获取到的分配粒度默认也是64k (最小单位)
当dlmalloc的请求内存超过阈值256k时 直接向系统索要内存
系统的内存分配方式是brk时至少在堆顶缓存一个分配粒度的空闲内存而不是收缩堆顶所有空闲内存
系统的内存分配方式是mmap时会通过满足条件一定次数后扫描线性扫描所有segment列表, 对未使用并且完全空闲的segment进行清除(保留堆顶 剩余切分被占用的segment).

..1. 目录

• 目录
  • 动态链接过程
    • 基础宏定义
    • 重定位定义
    • 符号表定义
    • 动态段定义
    • rscopeelem 定义
    • linkmap
    • dlfixup 函数定义和分析
    • 符号版本
    • 强弱符号
    • 强弱引用
    • 符号的作用域
• 动态库装载过程
  • ELF的辅助向量 AUXV
  • ELF的装载有三种方法