伙伴分配器:靠"伙伴"关系自动合并

上一篇咱们把内存碎片化讲透了,留下一个悬念:一个好分配器得在释放的时候主动把相邻的空闲块拼回去,别让碎片攒着。可"拼回去"说起来容易——释放一块,我怎么知道它旁边谁空着?难道每次释放都要满池子去搜邻居?这一篇讲的伙伴分配器(buddy allocator)就有一个特别巧的招:它让每一块都有一个固定的、靠地址算术就能定位的"伙伴",释放时只消看一眼伙伴在不在,在就拼回去——合并几乎是自动的、结构性的,根本不用搜。这套设计是 Linux 物理页分配器的底子,也是下一篇要讲的 Cinux 实现的算法原型。

先把两个词说定:2 的幂 与 order

讲伙伴算法之前,得先把它的两个基本词汇说清楚,不然后面每句话都会卡。

第一个是 2 的幂。伙伴分配器手里的块,大小只能是 1、2、4、8、16……页,也就是 2 的幂次方页。为什么非得是 2 的幂,等讲到合并的时候就知道了,这是这套设计的命根子,先记着。

第二个是 order(阶)。一块有多大,用 order 来记:order 0 是 1 页(2⁰),order 1 是 2 页(2¹),order 2 是 4 页(2²),以此类推——order 就是"这块有几页"以 2 为底的对数。用 order 而不直接说"几页",是因为后面到处要做翻倍、减半的操作,用 order 算(加减 1)比拿页数算(乘除 2)利索。

伙伴:同 order 的、能拼回一整块的那一半

重头戏来了。一块 order N 的内存,在地址空间里总落在某个固定位置上;把它从正中间切开,得到两块 order N-1——这两块互为伙伴(buddy)。

关键性质是:一块的伙伴,不用查表、不用搜,靠地址算术就能算出来。具体说,把这块的起始页号,异或上它这一档的大小(2 的 order 次方个页),就得到伙伴的起始页号。异或这个操作的特点是"就翻第 order 那一位、别的不动",刚好对应"伙伴是同一个大块里的另一半"——这个"靠算术定位伙伴"是整个设计最妙的一笔,它让"我的邻居是谁"这件事变得几乎免费。

还要补一句:一对伙伴,合并回去就是它们共同所属的那块 order N;而那块 order N 自己,又有它在 order N+1 里的伙伴。所以伙伴关系是一条链——小拼中、中拼大,一层层上去。

分配:要小块就拆大块,拆下来多的一半挂回

有了 order 和伙伴,分配规则就很简单。

分配器给每个 order 都备了一条空闲链(或位图):order 0 的空闲块串一条、order 1 的串一条……你要 order N 块,它先去 order N 那条链上拿一个现成的;如果 order N 这条空了,就去 order N+1 拿一个,然后把它拆成两半——一半给你,另一半(它的伙伴)挂回 order N 的空闲链。如果 order N+1 也空了,就去 order N+2 拆,一路往上找,直到找到有货的 order,再一路拆下来。

这么一来,池子里永远只会有"刚好的"或"被拆出来的"块,不会因为你要个小块就耗尽所有大块——大块可以现拆现用。

释放:跟伙伴试着拼回去,能拼就一路拼到顶

释放才是伙伴分配器的精华,也是它治碎片的本事所在。

你释放一块 order N,分配器不去满池子找邻居——它直接算出这块的伙伴(地址异或,一下就算出来),然后看伙伴现在是不是也空闲着。如果伙伴正被用着,那没办法,这块只能标成空闲、挂回 order N 的链;但如果伙伴也空闲,两块就合并成一块 order N+1——而且合并出来的这块,会继续去试它在 order N+1 的伙伴,能拼就再拼成 order N+2,如此递归,直到伙伴不空闲、或者到了池子能管理的最大 order。

这就是它治外部碎片的机制:每一次释放,都是一个"能拼就拼回去"的机会,而且拼的过程是顺着伙伴链一路自动往上的,不用搜、不用记账。用得越久,空闲块不会越散,反而会被持续地、趁每次释放的机会拼回大块——碎片一边产生一边被回收,池子始终保持一个相当干净的状态。

为什么非得是 2 的幂

现在能回答开头那个"为什么"了:块大小为什么必须是 2 的幂?

因为伙伴关系的成立,仰仗"一块从正中间切开得到两个等大的半块",而"从正中间切、两半等大"只有在大小是 2 的幂时,才能一层层递归地成立下去——1 拼成 2、2 拼成 4、4 拼成 8,每一层都是两个等大的凑成 2 倍。同时也只有 2 的幂,地址异或才能干净利落地定位伙伴(伙伴的地址,刚好是当前地址翻转一个位)。换成别的尺寸,比如允许 3 页、5 页的块,这套"靠算术定位伙伴、靠伙伴链自动合并"的机制立刻就垮了,得回到"满池子搜邻居"的老路。

所以 2 的幂不是伙伴分配器一个随便的限制,而是这套精巧机制能成立的前提。

代价:内部碎片

伙伴分配器治外部碎片治得好,但天下没有白吃的午餐,它的代价落在内部碎片上。

块大小只能是 2 的幂,你要 5 页,它给不了你正好 5 页,只能给 8 页(向上凑到最近的 2 的幂),多出来的 3 页你用不上,浪费在这块内部。要的页数越是"不是 2 的幂"、越卡在两档中间,这种浪费就越明显。这正是为什么后面还要再叠一层 slab 分配器——小对象(几十、几百字节那种)要是也走 buddy 按 2 的幂给页,内部碎片会大到离谱,所以 slab 在 buddy 之上把一页切成同规格的小格子,专门伺候小对象。

这一篇留下了什么

到这里,伙伴分配器的精髓就齐了:块按 2 的幂、用 order 记大小;每块有个靠地址算术定位的伙伴;分配时大块现拆;释放时顺着伙伴链自动合并。它把外部碎片的治理,从"释放后满池子搜邻居"变成"释放时顺着结构自动拼回去",这是它在治碎片这件事上又快又准的根本原因。

下一篇咱们就看 Cinux 具体怎么把这套算法实现出来——它的空闲链怎么组织、释放合并怎么写、又在真机上踩了什么坑。