元論文の式

  • \(fl = \lfloor\log_2(size)\rfloor\)

  • \(sl = (size - 2^{fl})\frac{2^\text{SLLEN}}{2^{fl}}\)

rlsfの実装

  • map_ceil / map_floor のどちらも以下の二行に依存している

  • この二行は要求されたサイズのブロックが属する空きリストのインデックスを計算する

    • sl は下位 SLI ビットが結果となる

let fl = usize::BITS - GRANULARITY_LOG2 - 1 - size.leading_zeros();
let sl = size.rotate_right((fl + GRANULARITY_LOG2).wrapping_sub(Self::SLI));

  • fl は単純であり、 log2(size) から最小ブロック分を引いて空きリストのインデックスとする

  • sl は \(size\frac{2^\text{SLLEN}}{2^{fl}}\)を計算するが、いくつかのコーナケースを循環シフトでカバーしている

    1. fl + GRANULARITY_LOG2 - Self::SLI が負になるケース

    2. 要求サイズを各second-level blockの開始サイズで割ったとき余りが出る場合

  • 1. のケースは要求サイズが GRANULARITY と等しい場合しか起こり得ない

    • 一般にSLI ⇐ log2(sizeof(usize)*8) = log2(sizeof(usize)) + 3 かつ GRANULARITY_LOG2 = log2(sizeof(usize)*4) = log2(sizeof(usize)) + 2、 よってSLI > fl + GRANULARITY_LOG2が成り立つのはfl=0のときに限る

  • 2. のケースはあまりに相当する桁が循環シフトによって上位に移動するため、 map_ceil では上位の桁を見て切り上げ、 map_floor では無視している

  • 最小ブロックサイズは MBS = GRANULARITY = size_of(usize) * 4 であり、 map_ceil/map_floor ともにGRANULARITY倍の要求しか受け付けない

    • 従って、 size の下位GRANULARITY_LOG2ビット size[0..GRANULARITY_LOG2] は常にゼロとなる

    • 空きリストの添字が小さいものは、この制約から最初の数スロットしか使われない

      • 例えばfl=0とすると 2^(GRANULARITY_LOG2) ⇐ size < 2^(GRANULARITY_LOG2+1) の範囲のサイズを管理できるはずだが、 GRANULARITY 倍の要求しか受け付けないため first_free[0][0] しか使われない

mapping functionの定義と実装

  • 空きリストの定義

    • TLSFではメモリプールを2段階の空きリストで管理する

      • first-level list: リスト各添字\$n\$ に対して\$2^n \leq size < 2^{n+1}\$に該当するサイズ\$size\$のブロックを管理している

      • second-level list: 各first-level listの添字\$n\$に対して一つのsecond-level listが存在し、 添字\$n\$に対応する領域を予め与えられたパラメータSLLENで等分した領域を管理する。

与えられたfirst-level listの添字flとsecond-level listの添字slについて、 second-level listの各添字の管理するサイズ範囲は\$slb = \frac{2^{fl}}{\text{SLLEN}}\$であり、 \$2^{fl} + sl\cdot slb \leq size < 2^{fl} + (sl+1)\cdot slb\$なるサイズ \$size\$のブロックが格納されている。 以下はブロックサイズと添字の対応を示す。

Diagram

slの計算

[tlsf]における計算式は以下のようになっている

\[\begin{align} fl &= \lfloor\log_2(size)\rfloor\\ sl &= (size - 2^{fl})\frac{2^{SLI}}{2^{fl}} \end{align}\]

\$fl\$は各空きリストのサイズ範囲の定義から直接従う。 \$sl\$について、first-level blockのサイズ範囲(\$2^{fl}\$)を要求サイズから引き、second-level listのサイズ範囲(\$\frac{2^{fl}}{\text{SLLEN}}\$)で割ると

\[\begin{align} \frac{size - 2^{fl}}{\frac{2^{fl}}{\text{SLLEN}}} &= \frac{size - 2^{fl}}{\frac{2^{fl}}{2^{SLI}}} \\ &= (size - 2^{fl}) \frac{2^{SLI}}{2^{fl}} \end{align}\]

ここで\$SLI = \log_2 \text{SLLEN}\$

*

以下はrlsf内の要求サイズに対してsecond-level listの添字を計算する実装である。 この実装は変数 sl の下位SLIビットに結果を計算する。

let sl = size.rotate_right((fl + GRANULARITY_LOG2).wrapping_sub(Self::SLI));

これがいかに論文の式と対応するかをみる。 論文との仮定の差分は以下である

  • 最小のブロックサイズとして GRANULARITY = size_of(usize) * 4 を設定

  • 要求サイズとして GRANULARITY 倍のものだけを許す

分岐命令を減らすため、循環シフトによってコーナケースをカバーしている。 flが計算済みなため、\$size = 2^{fl+\text{GRANULARITY_LOG2}} + X < 2^{fl+\text{GRANULARITY_LOG2} + 1}\$が仮定できる

上で通り得るパスは

  1. シフト量が正で1を含むビットが循環しない

  2. シフト量が正で1を含むビットが循環する

  3. シフト量が負である(左シフトになる)

    • fl + GRANULARITY_LOG2 - SLI >= 0 の場合

      • fl + GRANULARITY_LOG2 - SLI >= GRANULARITY_LOG2 の場合

        • 下位SLIビットを見れば右シフトと変わらない\$\frac{size-2^{fl}}{2^{fl + \text{GRANULARITY_LOG2} - SLI}}\$

        • sl[GRANULARITY_LOG2..] のビットが循環する可能性がある もしも循環したら、それは計算結果の示すブロックサイズより元のsizeが大きいことを意味するため、 map_ceilでは切り上げるための処理が入る

          • sl[0..SLI] には切り捨てverのsecond-level listの添字が入る

      • fl + GRANULARITY_LOG2 - SLI < GRANULARITY_LOG2 → 1が該当

        • 循環する桁が下位 GRANULARITY_LOG2 のみなので影響はなく、通常の右シフトと同様

        • \$\frac{size}{2^{fl + \text{GRANULARITY_LOG2} - SLI}}\$

    • fl + GRANULARITY_LOG2 < SLI の場合 → 3が該当

      • size == GRANULARITY の場合のみ起こり、1ビット左シフト

ここで常に sl[SLI] = 1

  • 1と2ではシフト量は常に fl+GRANULARITY_LOG2 以下なため、 sl[SLI] = 1

  • 3のケースでは、SLI=6,fl=0,GRANULARITY_LOG2=5なので 0b100000 << 1 == 0b1000000 を見ると成り立っている。

fl + GRANULARITY_LOG2 >= SLI かつ fl - SLI > 0 の場合 (SLIの幅はGRANULARITY_LOG2にかかりうる)

Diagram

fl + GRANULARITY_LOG2 >= SLI かつ fl - SLI =< 0 の場合 (SLIの幅はGRANULARITY_LOG2にかかりうる)

Diagram 
sl = (sl & (SLLEN - 1)) + (sl >= (1 << (Self::SLI + 1))) as usize;

  • map_ceilの場合、循環して上位に来た桁があれば(fl,sl)を次の添字に進める必要がある

    • sl[SLI]=size[fl]なので、1の循環がなければ sl < 1<<SLI+1 、これが義であれば1を下位SLIビットに加算してsecond-level listの添字は繰り上げることができる

    • 繰り上げ後のslがSLLENを超えていれば i.e. sl[SLI]が立っていれば、1をflに加算

      • このとき繰り上げ後のslの下位SLIビットは0なので、(fl+1,0)として適切に添字の繰り上げができている

/// Find the free block list to store a free block of the specified size.
#[inline]
fn map_floor(size: usize) -> Option<(usize, usize)> {
    debug_assert!(size >= GRANULARITY);
    debug_assert!(size % GRANULARITY == 0);
    let fl = usize::BITS - GRANULARITY_LOG2 - 1 - size.leading_zeros();

    let sl = size.rotate_right((fl + GRANULARITY_LOG2).wrapping_sub(Self::SLI));

    debug_assert!(((sl >> Self::SLI) & 1) == 1);

    if fl as usize >= FLLEN {
        return None;
    }

    Some((fl as usize, sl & (SLLEN - 1)))
}
/// Find the first free block list whose every item is at least as large
/// as the specified size.
#[inline]
fn map_ceil(size: usize) -> Option<(usize, usize)> {
    debug_assert!(size >= GRANULARITY);
    debug_assert!(size % GRANULARITY == 0);
    let mut fl = usize::BITS - GRANULARITY_LOG2 - 1 - size.leading_zeros();

    let mut sl = size.rotate_right((fl + GRANULARITY_LOG2).wrapping_sub(Self::SLI));

    debug_assert!(((sl >> Self::SLI) & 1) == 1);

    sl = (sl & (SLLEN - 1)) + (sl >= (1 << (Self::SLI + 1))) as usize;

    // if sl[SLI] { fl += 1; sl = 0; }
    fl += (sl >> Self::SLI) as u32;

    if fl as usize >= FLLEN {
        return None;
    }

    Some((fl as usize, sl & (SLLEN - 1)))
}

循環シフトの形式化

  • 通常のビット演算と条件分岐で組み立て、循環シフトとなっていることを確認するための諸補題を証明する。

  • 諸補題 e.g.

    • ビット幅倍のシフトは元に戻る

    • 等量のシフト幅で逆方向にシフトすれば元に戻る

  • 実装

  • 右方向

Diagram

  • 左方向

Diagram

bibliography

  • [tlsf] MASMANO, Miguel, et al. TLSF: A new dynamic memory allocator for real-time systems. In: Proceedings. 16th Euromicro Conference on Real-Time Systems, 2004. ECRTS 2004. IEEE, 2004. p. 79-88.