🌴

Linuxのメモリ割り当てアルゴリズムを追う Slab Allocation編

2023/12/24に公開

Linux

はじめに

この記事はコネヒトAdvent Calendar2023の24日目の記事です。

前回の記事では、Linuxの主要なメモリ割り当てアルゴリズムの一つであるBuddy Memory Allocationについて詳しく紹介しました。
本記事では、Linuxで使用されているもう一つの重要なメモリ割り当てアルゴリズムであるSlab Allocationに焦点を当てて、その仕組みについて解説していきたいと思います。

↓ 前編の記事です

前提

前編のおさらい

前編では、Buddy Memory Allocationの基本原理と仕組みについて紹介しました。

このアルゴリズムは、メモリブロックの割り当てと解放を2の冪乗単位で行うことにより、外部フラグメンテーションの発生を削減できると同時に、割り当てと解放のプロセスを高速化できるというものでした。

ビットマップ方式とBuddy Memory Allocationの比較

特に、ビットマップ方式などの連続的なメモリ割り当て方式と比較して、Buddy Memory Allocationは外部フラグメンテーションを大幅に削減することが可能になります。
しかし、内部フラグメンテーションが発生してしまうといった懸念点もありました。

今回のスコープ

32byteのメモリを割り当てる様子

本記事では、Linuxカーネルで使用されるSlab Allocationに焦点を当てます。このアルゴリズムの仕組み、利点と懸念点、Linuxでの実装などについて見ていきます。

また、この二部構成のシリーズを通じて、上図に示されたメモリ割り当てプロセスの全体像を理解することを目指します。

Slab Allocation

歴史

Slab Allocationは、1994年にJeff Bonwick氏によって開発され、Solaris 2.4カーネルで最初に導入されたメモリ割り当てアルゴリズムです。Linuxカーネルではバージョン2.2から採用されていて、現在に至るまで重要なメモリ割り当てアルゴリズムとして使用され続けています。
LinuxカーネルではSlab Allocationの導入によって、メモリ割り当てと解放の効率が大幅に向上しました。

ちなみに、Nintendo SwitchのマイクロカーネルであるHorizonや、インメモリデータストアの一つであるMemcachedでもSlab Allocationが使用されているので、なんだか身近に感じるアルゴリズムですね。

概要

端的に言うと、Slab Allocationは、内部フラグメンテーションの削減と、メモリの割り当て・解放のパフォーマンスを向上させるためのメモリ管理アルゴリズムです。

以下に示す図はSlab Allocation の全体の構造を表しています。

Slab Allocationの全体像

Slab AllocationはCacheやSlabなどの要素から構成されており、これらを用いて高速なメモリ割り当てと解放を実現します。それぞれの構成要素を紹介し、全体の流れを追っていきます。

Cache

Cacheは、特定の種類またはサイズのオブジェクトのSlab(メモリ)を管理するための構造体です。
カーネル内では、特定のオブジェクト(例：fileやprocess構造体など)が頻繁に利用されます。そのような特定のサイズのオブジェクトは、それ専用のCacheによって管理されます。
Slab Allocationシステムは、Cache Chainと呼ばれるCacheの循環リストから構成されており、メモリ割り当ての際には、このリストから該当のCacheが選択されます。

Slab

Slabは、特定サイズのオブジェクトを格納するための連続したメモリ領域です。
Buddy Memory Allocationによって割り当てられた割り当てられたメモリブロック（Page）を管理し、そこに何個のオブジェクトが格納可能であるかや、オブジェクトの割り当て状況を追跡します。

CacheはSlabを以下の三つのリストで管理しています。

slabs_free : どのオブジェクトも割り当てられていないSlabが格納される
slabs_partial : 一部のオブジェクトが割り当てられているSlabが格納される
slabs_full : 全てのオブジェクトが割り当てられている Slabが格納される

割り当ての際は、slabs_partialに格納されているSlabから優先的に割り当てられます。

これらの情報を踏まえて、割り当て・解放の全体的な流れを以下に示します。

割り当て

Slab Allocationでのメモリ割り当て

① 32バイトのメモリ割り当て要求が発生すると、 AllocatorはCache Chainの中から該当するサイズのCacheを探します。もし該当サイズのCacheが存在しない場合は、32バイト用の新しいCacheが作成されます。

② 適切なCacheを取得すると、AllocatorはそのCacheのslabs_partialリストをチェックします。もしslabs_partialが空であれば、slabs_freeからSlabを取り出し、slabs_partialに移動させます。

③ 選択されたSlab内で空いているオブジェクトの場所を見つけ、そのメモリアドレスを割り当て要求に返却します。

解放

Slab Allocationでのメモリ解放

① 32バイトのメモリ解放要求が発生すると、返却するメモリアドレスがどのPage範囲に含まれているアドレスかを計算します。

② そのPageに紐付いているCache,Slabを調べます。

③ Slabからそのアドレスがどのオブジェクトかを割り出して、そのオブジェクトを解放します。この解放によってSlab内のオブジェクトが全て未割り当てになれば、そのSlabをslabs_freeに移動させます。

このように、Slab AllocationはCacheとSlabを用いてメモリ管理を実現します。
この管理方法がどのような利点を生み出すのかを見ていきます。

利点

Slab Allocationは、以下のような利点があります。

内部フラグメンテーションを削減できる

Linuxにおいて、最小メモリブロックは4KiBに設定されているので、例えば32バイトのメモリ割り当て要求に対しても、実際には4KiBのメモリブロックが割り当てられます。この結果、3KiB以上のメモリ未使用のままとなり、内部フラグメンテーションが発生します。

Slab Allocationは、この内部フラグメンテーションを削減することができます。
これは、Buddy Memory Allocationによって割り当てられた4KiBのメモリブロック(Page)をSlabで効率的に分割し、小さなオブジェクトへの割り当てを行うためです。

PageとSlabの簡略図

上図のように、SlabはPageを細かく分割し、複数の小さなオブジェクトにメモリを割り当てることが可能です。
例えば、32バイトのオブジェクトを管理するSlabの場合、理論上は128個のオブジェクトを管理できるようになります（実際のSlabは、もう少し複雑な構造なのでそのようにはいきませんが）。
このようにSlabを用いることで、大きなメモリブロック内の未使用領域を減らし、内部フラグメンテーションを大幅に削減することができます。

割り当て・解放にかかるオーバーヘッドを削減できる

先ほども述べたように、カーネルでは同一のオブジェクト（構造体）が頻繁に利用されることが一般的です。これらのオブジェクトが必要になるたびに、物理メモリ領域から空き領域を探し出して、使用が終わったら解放をするというプロセスは、コストが高くパフォーマンスに影響を及ぼす可能性があります。

Slab Allocationでは、このような頻繁なメモリ割り当て・解放に伴うオーバーヘッドを削減します。具体的には、あらかじめPageが割り当てられたSlabをslabs_freeにキャッシュとして保持しておきます。メモリ割り当て要求が発生した場合、Slab Allocationシステムはすぐにslabs_freeまたはslabs_partialにあるSlabの中から空いている領域を見つけ、そのアドレスを返却します。このプロセスはO(1)のコストで済むため、迅速なメモリ割り当てが可能になります。
このように、Slab Allocationによってあらかじめオブジェクトを用意し、キャッシュ化しておくことで、メモリ割り当てと解放のプロセスが高速化され、カーネルの全体的なパフォーマンスが向上します。

ハードウェアキャッシュを有効に活用できる

Slab Allocationはキャッシュメモリを有効に活用するための工夫が施されています。

Slabの構造

Slab Allocationでは、カラーリングと呼ばれる概念が用いられています。これは、Slab内のオブジェクト間にわずかなオフセットを追加することで、キャッシュメモリの利用効率を向上させるためのものです。キャッシュメモリは、キャッシュラインと呼ばれる固定長の単位でメインメモリのデータを保持します。
しかし、隣接するオブジェクトが同じキャッシュラインに配置されると、一方のオブジェクトへのアクセスがもう一方のオブジェクトをキャッシュから追い出し、パフォーマンスの低下（キャッシュミス）を招く可能性があります。

カラーリングは、オブジェクト間にオフセットを追加することで、同一Slab内のオブジェクトが異なるキャッシュラインに配置されるように試みます。これにより、オブジェクト同士が互いのキャッシュラインからデータを追い出し合う可能性が減少し、キャッシュヒット率が向上し、結果的に全体的なシステムパフォーマンスが改善されます。

懸念点

多くの利点がある一方で、懸念点もいくつか存在します。

メモリ使用効率の問題

Slab Allocationは特定の種類のオブジェクト用にメモリを予め割り当てて保持します。そのため、使用頻度の低いオブジェクトのために確保されたメモリが十分活用されない場合があり、メモリ使用効率が低下する可能性があります。

管理の複雑さ

Slab AllocationはCache、Slab、オブジェクトといった複数のレイヤーを持っており、これらを効率的に管理するためには、複雑なロジックが必要になります。これはカーネルのメモリ管理コードを複雑にし、デバッグやメンテナンスのしにくさに直結します。

スケーラビリティの問題

一部のSlab Allocationの実装では、マルチコアプロセッサシステムにおけるスケーラビリティに課題があります。これは、複数のプロセッサが同時にスラブにアクセスする際にロック競合が発生するためです。Slab Allocationが生まれた時代にマルチコアプロセッサは普及していなかったので、この問題が発生するのは当然っちゃ当然ですね。

Linuxでの実装

Linuxカーネルでは、Slab Allocationの考え方に基づいて、以下の三つのメモリ管理方法が導入されています。

SLAB : Slab Allocationのオリジナル実装。古いアーキテクチャに基づいており、初期のLinuxカーネルで採用されていた
SLUB : SLABのよりシンプルで高性能な代替案として導入された。SLUBは、マルチコアプロセッサに適した設計で、オーバーヘッドを減らすことに重点を置いている
SLOB : 主に組込みシステム向けに設計されたSlab Allocationの軽量実装。リソースが限られた環境において有用

しかし、このLinuxカーネルのメーリスに書かれている通り、Linuxカーネル6.5でSLABは非推奨とされ、Linuxカーネル6.8のリリースに向けてコードの削除が計画されています。SLABはマルチコアプロセッサが普及する前のアーキテクチャに基づいているため、現代のオペレーティングシステムの要求に完全には適応できていません。その結果、より効率的でシンプルなSLUBが主流になる方向で進んでいるようです。
SLABの削除は、Linuxカーネルのメモリ管理コードを単純化し、現代のハードウェアとの相性を改善するための一環と見ることができます。
今回の紹介では、Slab Allocationのオリジナルの概念であるSLABについて説明したので、気が向けば年明けにSLUBの詳細を解説する記事でも出そうと思います。

おわりに

この二つの記事を通じて、Linuxの物理メモリ管理における「Buddy Memory Allocation」と「Slab Allocation」の仕組みと役割について書きました。

Linuxではこれら二つのアルゴリズムを組み合わせることで、外部フラグメンテーションと内部フラグメンテーションの両方を効果的に防ぐことができ、効率の良い高速なメモリ割り当てを実現しているのです。

SLABからSLUBへの移行のように、時代の流れや技術の進歩によってアルゴリズムは進化し続けています。しかし、その根本的な考え方は数十年にわたって変わらず、多くのシステムで広く採用されているので、学びがいのあるアルゴリズムなのではないでしょうか。