ESP-IDF v4.3でESP32のヒープ残量が10KB減る問題の調査

ファームウェアエンジニアの中林 (id:tomo-wait-for-it-yuki) です。ESP32愛好家の皆様、ESP-IDF v4.3で次の変更が入ったことにお気づきでしょうか？

  • Heap: Switched heap algorithm to one based on TLSF, improves performance especially when using a high number of allocations in PSRAM

リリースノート1にさらっと1行だけ書かれていますが、「え？ヒープアロケータ変わったの？インパクト大きくない？」というのが最初の印象でした。本エントリではこのさらっと入った変更の、意外と大きな影響について解説して参りたいと思います。

本エントリの要点は次の通りです。

  • ESP-IDF v4.3からヒープアロケータがフリーリストアロケータからTLSFアロケータに変わった
  • TLSFアロケータはメモリ確保 / 解放の最悪実行時間を大幅に改善できる (おそらく平均実行時間も改善する
  • ESP32では使えるヒープ容量が問答無用で10KBほど減る
  • v4.3以降、ヒープ残量の計算が間違っており、ヒープ残量取得APIで取得できる残量より実際に使えるヒープは少ない

本エントリでは、まず第一にヒープアロケータ変更に伴う一番の問題点について動作確認します。その後、ESP-IDFメモリアロケータの実装を紐解きながら、本問題が発生する原因について解説し、最後にESP-IDF v4.2とv4.3.2とでヒープアロケータの性能比較を行います。

ヒープ残量の減少

では、早速ヒープ残量が減少する問題から見ていきましょう。次のヒープ残量を表示するだけのプログラムを、ESP-IDF v4.2とv4.3.2とでそれぞれ実行します。ESP32-DevKitC (ESP-WROOM-32) を使用し、PSRAMは非搭載です。sdkconfigはそれぞれ各バージョンのデフォルトとします。

#include <esp_log.h>
#include <esp_heap_caps.h>

void app_main(void)
{
    ESP_LOGI("app_main", "start free heap size test");
    ESP_LOGI("app_main", "free heap: %d bytes", heap_caps_get_free_size(MALLOC_CAP_INTERNAL));
}

するとなんということでしょう！ESP-IDFをバージョンアップしただけで匠の技によって、ヒープ残量が12KBも減っています！

ESP-IDF ログ出力
v4.2 I (319) app_main: free heap: 388804 bytes
v4.3.2 I (323) app_main: free heap: 376160 bytes

このヒープ残量減少のうち、約10KBはヒープアロケータを変更したことに起因しています。ではなぜこのような問題が発生するのか、ESP-IDFメモリアロケータの実装を解析しながら見ていきましょう。

ESP-IDFのメモリアロケータ概要

まず、ESP32でヒープとして使えるメモリ領域についてです。ESP32では5つの非連続RAM領域をヒープとして使用することが出来ます。これはハードウェアアーキテクチャ上の仕様です。ESP-IDFでビルドしたファームウェアで次のようなログを目にした方も多くいらっしゃるでしょう。こちらは5つのRAM領域それぞれで、ヒープとして使える残量を示しています。

I (243) heap_init: Initializing. RAM available for dynamic allocation:
I (250) heap_init: At 3FFAE6E0 len 00001920 (6 KiB): DRAM
I (256) heap_init: At 3FFB31F8 len 0002CE08 (179 KiB): DRAM
I (262) heap_init: At 3FFE0440 len 00003AE0 (14 KiB): D/IRAM
I (268) heap_init: At 3FFE4350 len 0001BCB0 (111 KiB): D/IRAM
I (275) heap_init: At 4008B2AC len 00014D54 (83 KiB): IRAM

ESP-IDFでファームウェアを書く時、一般的なCプログラムと同様にmalloc / freeでメモリの確保 / 解放を行います。この裏でESP-IDFでは5つのRAM領域を束ねてmalloc / freeでメモリ管理できるようにしています。これを大雑把に図示すると次の通りです。今回、「ヒープアロケータが変わった」と言っているのは、図中のheap allocatorの部分にあたります。本エントリは、下図全体をメモリアロケータ、RAM領域のアロケータをヒープアロケータと記述しています (これは特に一般的な分類ではなく、本エントリでの説明の便宜上そう呼んでいます) 。

f:id:tomo-wait-for-it-yuki:20220125073233p:plain
ESP-IDFメモリアロケータアーキテクチャ

上図を簡単に説明すると、ヒープアロケータ (heap allocator) がベースのアロケータとなっており、その上に、スレッド安全性を担保する薄いラッパーのmulti_heap (components/heap/multi_heap.c) *1、複数のRAM領域を統合するheap_cap (components/heap/heap_caps.c) があります。newlib (libc) のmalloc / freeはheap_capに処理をdelegateしているだけです*2。

通常、malloc()はheap_caps_malloc_default()を呼び出すだけです。

esp-idf/components/newlib/heap.c
void* malloc(size_t size)
{
    return heap_caps_malloc_default(size);
}

heap_caps_malloc_default()はPSRAMがあるかどうかで少し処理が変わるのですが、いずれにしてもheap_caps_malloc()を呼び出します。heap_caps_malloc()は5つのRAM領域を順番にたどりながら、どこかでメモリが確保できるかどうか試します。

esp-idf/components/heap/heap_caps.c
        SLIST_FOREACH(heap, &registered_heaps, next) {
            if (heap->heap == NULL) {
                continue;
            }
            // ...
                        ret = multi_heap_malloc(heap->heap, size + 4);

multi_heap_malloc()ではスレッド安全性を確保するためにロックを取得し、heap allocator (v4.2までではフリーリストアロケータ、v4.3以降はTLSFアロケータ) のmallocを呼び出し、ヒープ残量の計算をします。下はv4.3.2の実装で、tlsf_malloc()がTLSFアロケータのmallocです。

esp-idf/components/heap/multi_heap.c
void *multi_heap_malloc_impl(multi_heap_handle_t heap, size_t size)
{
    if (size == 0 || heap == NULL) {
        return NULL;
    }

    multi_heap_internal_lock(heap);
    void *result = tlsf_malloc(heap->heap_data, size);
    if(result) {
        heap->free_bytes -= tlsf_block_size(result);
        if (heap->free_bytes < heap->minimum_free_bytes) {
            heap->minimum_free_bytes = heap->free_bytes;
        }
    }
    multi_heap_internal_unlock(heap);

    return result;
}

ESP-IDFメモリアロケータの概要は以上です。続いてTLSFアロケータについて見ていきましょう。

TLSFアロケータ

TLSF (Two-Level Segregate Fit) アロケータ2は2003年に提案されたヒープアロケータで、特にリアルタイム性への要求を満たすヒープアロケータとして設計されています。端的にTLSFアロケータの特徴を挙げると以下の通りです。

  • リアルタイム性への要求を満たすアロケータとして設計されている
  • 割り当て可能なメモリの検索が非常に高速 O(1) に行える
  • メモリフラグメンテーションが発生しにくい

そのため、RTOS (Real-Time Operating System) のヒープアロケータとしてや、ゲームに適しているアロケータと言えます。実際にHypervisorのXen3やIoT向けの組込みOSであるRIOT4で使われているようです。ゲームつくろー！5でTLSFについてめちゃくちゃ詳しく、しかもわかりやすく解説されています。もし TLSFアロケータの詳細に興味がある場合は、ぜひこちらをご参照ください。

重要な点だけかいつまんで説明すると、TLSFアロケータは割り当て可能なメモリの検索を高速化するために、割り当てるメモリブロック容量ごとのフリーリストを、テーブルをひいて検索します。まず、RAM全体をN分割した第1カテゴリーがあり、さらに第1カテゴリーをM分割した第2カテゴリーにフリーリストへのポインタが格納されています。まず第1カテゴリーでおおよそのメモリサイズに当たりをつけて、第2カテゴリーでさらに細かく分類します。テーブルサイズはN × M × sizeof(intptr_t)で計算できます((最後の4はポインタのバイト数です))。例えば、32ビットプロセッサでRAM全体を10分割して第1カテゴリーを作り、第1カテゴリーを32分割して第2カテゴリーを作る場合、10 × 32 × 4 = 1,280[byte]となります。

このテーブルは、TLSFアロケータの重要なパラメータで、どの程度細かくテーブルを持つか (すなわち、テーブルのサイズをどのくらいにするか) 、が設定できるようになっています。ESP-IDFではcomponents/heap/heap_tlsf_config.hにそのパラメータがあります。このパラメータを順番に計算していくと、テーブルサイズは約1.6KBになります。ただし、ESP32では5つのRAM領域があり、それぞれにTLSFアロケータのテーブルを持つようになっているため、1.6KB x 5で合計8KBのRAMがこのテーブルで消費されることになり、本エントリを書くに至った問題につながります。

ESP-IDFではheap_tlsf_config.hで、利用可能なRAMサイズに応じて、確保するテーブルサイズを決めています。テーブルが占めるバイト数の計算式は、第1カテゴリーの分割数 × 32 × 4となっています*3。第1カテゴリーの分割数は次のコードで求めています。PSRAM (SPIRAM) を有効化している場合、PSRAMの容量をベースにテーブルが作られてしまうことに注意が必要です。現在は全てのRAM領域で同じテーブルサイズを使うため、PSRAMを搭載するとインターナルRAMを管理するためのテーブルサイズも大きくなります。PSRAMが8MBだとRAM領域ごとに約2KBのテーブルが確保されます。

#ifdef ESP_PLATFORM

#include "soc/soc.h"

#if !CONFIG_SPIRAM
#define TLSF_MAX_POOL_SIZE (SOC_DIRAM_DRAM_HIGH - SOC_DIRAM_DRAM_LOW)
#else
#define TLSF_MAX_POOL_SIZE SOC_EXTRAM_DATA_SIZE
#endif

 #if (TLSF_MAX_POOL_SIZE <= (256 * 1024))
    FL_INDEX_MAX = 18, //Each pool can have up 256KB
    #elif (TLSF_MAX_POOL_SIZE <= (512 * 1024))
    FL_INDEX_MAX = 19, //Each pool can have up 512KB
    #elif (TLSF_MAX_POOL_SIZE <= (1 * 1024 * 1024))
    FL_INDEX_MAX = 20, //Each pool can have up 1MB
    #elif (TLSF_MAX_POOL_SIZE <= (2 * 1024 * 1024))
    FL_INDEX_MAX = 21, //Each pool can have up 2MB
    #elif (TLSF_MAX_POOL_SIZE <= (4 * 1024 * 1024))
    FL_INDEX_MAX = 22, //Each pool can have up 4MB
    #elif (TLSF_MAX_POOL_SIZE <= (8 * 1024 * 1024))
    FL_INDEX_MAX = 23, //Each pool can have up 8MB
    #elif (TLSF_MAX_POOL_SIZE <= (16 * 1024 * 1024))
    FL_INDEX_MAX = 24, //Each pool can have up 16MB
    #else

加えて、TLSFアロケータのassertion文がRAMに乗ってしまっている、という問題もあるようです。こちらは約1.5KBほどRAMを圧迫するようです。本問題の簡潔なまとめは下記issueに書かれています。

github.com

TLSFアロケータを採用することで、テーブルにRAM容量が消費されることをは避けられません。しかし、今のテーブルサイズの計算は、各RAM領域のサイズが異なるにも関わらず、一律同じテーブルサイズを確保している、という問題があります。そこで、各RAM領域のサイズごとにテーブルサイズを変更するPRが出されています。こちらがマージされれば、ある程度ヒープ残量の減少がおさえられそうです。

github.com

v4.3以降のヒープ残量計算について

ヒープアロケータをフリーリストアロケータからTLSFアロケータに変更したことで、フリーブロックを分割 / マージした際のブロックヘッダの計算が漏れているようです。そのため、ESP-IDFのAPIで取得できるメモリ残量より、実際に使える残量が少なく計算されています。こちらも一応注意が必要です。

github.com

ESP-IDF v4.3でESP32のヒープ残量が10KB減る問題については以上となります。以下は、v4.2までのヒープアロケータ実装を改めて解析し、v4.3のヒープアロケータと比較を行った結果を掲載しています。

v4.2までのフリーリストアロケータ

ここで、TLSFアロケータとの対比のために、ESP-IDF v4.2まで使われていたヒープアロケータを紹介します。ヒントはこちらの構造体を割り当て可能なフリーブロックの管理に使っていることです。

typedef struct heap_block {
    intptr_t header;                  /* Encodes next block in heap (used or unused) and also free/used flag */
    union {
        uint8_t data[1];              /* First byte of data, valid if block is used. Actual size of data is 'block_data_size(block)' */
        struct heap_block *next_free; /* Pointer to next free block, valid if block is free */
    };
} heap_block_t;

これは、割り当て可能なフリーブロックをLinked Listで管理するタイプの、いわゆるフリーリストアロケータと呼ばれるアロケータです。自作OSのメモリアロケータとして実装したことがある方も多いのではないでしょうか？実装としても600行程度の簡素なものです。フリーリストアロケータにもいくつか作り方があるのですが、実装のバリエーションとしては、次のとおりです。

  • 単方向リスト
  • ベストフィット
  • リストはメモリアドレス順にソート

ベストフィットするフリーブロックを割り当てるために、単方向リストを全探索しており、メモリ割り当ての効率は高くなさそうです。また、メモリブロックのヘッダの使い方として、割り当てたサイズを保持するのではなく、次のメモリブロック (フリーブロックではない) を指すために使っているのが特徴です。

フリーリストアロケータ (v4.2) vs TLSFアロケータ (v4.3.2)

ESP-IDFのesp-idf/components/heap/test_multi_heap_hostにホストPCでヒープアロケータをユニットテストフレームワークCatch6でお試しできる環境が整っています (しかしずいぶんバージョンが古い…) 。ここで色々試してみましょう。

ヒープ残量比較

次のテストケースを使って、250KiBのメモリがあるときに、何個メモリブロックが確保できるか確認します。確保するメモリブロックのサイズは、適当に4バイト / 32バイト / 128バイト / 512バイトとしました。また、ヒープを作成した直後、何バイト空き容量があるかを出力してTLSFアロケータのテーブルが占める容量を明らかにします。

TEST_CASE("count memory block allocation", "[multi_heap")
{
    uint8_t big_heap[250000];
    multi_heap_handle_t heap = multi_heap_register(big_heap, sizeof(big_heap));
    printf("free heap: %u\n", multi_heap_free_size(heap));

    const size_t alloc_size = GENERATE(4, 32, 128, 256);
    size_t count = 0;
    for (; (int32_t*)multi_heap_malloc(heap, alloc_size) != nullptr; count++) {}
    printf("%u %d-byte memory block allocated\n", count, alloc_size);
}

まず、ヒープ作成直後の空き容量です。フリーリストアロケータが249,964バイトなのに対して、TLSFアロケータでは246,780バイトでした。つまり、フリーリストアロケータではヒープの管理領域として36バイトしか使っていないのに対して、TLSFアロケータでは3KB近く管理領域として使われていることがわかります。

次に、メモリブロックサイズごとに確保できるメモリブロック量の結果としては、確保するメモリブロックが少ない場合、TLSFアロケータで確保できるメモリブロック数が極端に少ないことがわかりました。どうも挙動を見る限り、最小割り当て単位が16バイトになっている気がします。

確保メモリブロックサイズ フリーリストアロケータ [ブロック数] TLSFアロケータ [ブロック数]
4バイト 31246 12339
32バイト 6943 5141
128バイト 1893 1713
512バイト 484 467

詳細は調査していないのですが、ブロックヘッダの定義がこうなっているので、ブロックを分割するごとに16バイト持っていかれている気がします。

typedef struct block_header_t
{
    /* Points to the previous physical block. */
    struct block_header_t* prev_phys_block;

    /* The size of this block, excluding the block header. */
    size_t size;

    /* Next and previous free blocks. */
    struct block_header_t* next_free;
    struct block_header_t* prev_free;
} block_header_t;

実行時間比較

せっかくなので両方のアロケータをいじめてみましょう。

TLSFアロケータは割り当てるフリーブロックの探索を定数時間で行えるため、あまり苦手なシチュエーションはないのですが、あえて言うなら毎回メモリブロックを分割しないといけない状況だと不利になります。メモリブロックの分割が進んでいない状態で、小さいメモリブロックをひたすら確保し続けるケースが苦手です。

フリーリストアロケータはメモリフラグメンテーションが進むと性能が悪化します。その理由はベストフィットなフリーブロックを探すためにフリーリスト全探索するためです。そこで、4バイトのメモリを10000回確保して、奇数番目に確保したメモリを解放します。これで4バイトのフリーブロックがヒープのアドレス前半に大量にできて、アドレス後半に大きなフリーブロックが残っている状態になります。ここでおもむろに8バイトのメモリを確保しようとすると、フリーリストを全探索しないとベストフィットブロックが見つかりません。

次のコードでこのことを簡易的に確かめてみます。メモリアロケータの性能評価を真面目にやると色々と大変なので、おおよその傾向に対する参考としていただけると幸いです。

TEST_CASE("benchmark malloc", "[multi_heap]")
{
    // 250[KiB]のヒープ領域を作成します
    uint8_t big_heap[250000];
    multi_heap_handle_t heap = multi_heap_register(big_heap, sizeof(big_heap));

    // ラムダ式 `operation` で計測対象のヒープ処理を与え、実行にかかった時間を返す便利ラムダ式
    auto measure = [](auto&& operation) {
        const auto& begin = std::chrono::high_resolution_clock::now();
        operation();
        const auto& end = std::chrono::high_resolution_clock::now();
        return end - begin;
    };

    // ヒープ初期状態から8バイトのメモリを1回確保する
    {
        int32_t* ptr = nullptr;
        auto elapsed = measure([&]{
            ptr = (int32_t*)multi_heap_malloc(heap, 8);
        });
        CHECK(ptr != nullptr);
        printf("first alloc elapsed: %llu\n", elapsed.count()); // ★1
    }

    {
        // 1万回、4バイトのメモリを確保する
        const size_t alloc_num = 10000;
        int32_t* ptrs[alloc_num];
        {
            auto elapsed = measure([&]{
                for (size_t i = 0; i < alloc_num; i++) {
                    auto alloc = (int32_t*)multi_heap_malloc(heap, 4);
                    ptrs[i] = alloc;
                }
            });
            for (size_t i = 0; i < alloc_num; i++) {
                CHECK(ptrs[i] != nullptr);
            }
            printf("10000 times alloc elapsed: %llu\n", elapsed.count()); // ★2
        }

        // 奇数番目に確保したメモリだけ解放する
        {
            auto elapsed = measure([&]{
                for (size_t i = 1; i < alloc_num; i += 2) {
                    multi_heap_free(heap, ptrs[i]);
                }
            });
            printf("5000 times free elapsed: %llu\n", elapsed.count()); // ★3
        }
    }

    // 4バイトのフリーブロックが大量にある状態で、8バイトのメモリを確保する
    {
        int32_t* ptr = nullptr;
        auto elapsed = measure([&]{
            ptr = (int32_t*)multi_heap_malloc(heap, 8);
        });
        CHECK(ptr != nullptr);
        printf("fragmented block alloc elapsed: %llu\n", elapsed.count()); // ★4
    }
}

結果は次の通りです。

計測場所 フリーリストアロケータ (ns) TLSFアロケータ (ns)
★1 452 960
★2 1,293,934 2,399,086
★3 92,965,578 627,055
★4 78,167 1,098

★1と★2はTLSFアロケータの実行時間が悪くなるメモリブロック分割が発生するメモリアロケーションで、フリーリストアロケータの約2倍ほど遅い結果となりました。この場合、フリーリストアロケータは毎回先頭のフリーブロックに確保可能なメモリが見つかるため、フリーリストは探索が最短で終わります。ですので、フリーリストアロケータの (ほぼ) ベストケース vs TLSFアロケータのワーストケースで、このくらいは実行速度に差があることになります。

一方、★3と★4はフリーリストアロケータが苦手なパターンです (正直★3は結果を見てから、そう言えばそうか、と考えが至りました) 。★3は5000回、奇数番目に確保したメモリを解放する処理です。ここではなんと4桁の差がついています。フリーリストアロケータでは、メモリを解放したあと、フリーリストはメモリアドレス順にノードを挿入しなければならないため、フリーリストの探索が必要になります。特に後から確保したメモリほど、メモリアドレスとしては後ろの方になるため、探索により時間がかかります。ただ、それだけで説明できないほどの差がある印象なので、もう少し調査が必要かもしれません。最後に★4です。こちらも3桁近い差が出ています。フリーリストアロケータはフリーリストを全探索しなければならないのに対して、TLSFアロケータは★1のときと同じ処理をすれば良いだけです。

このようにメモリの確保 / 解放を繰り返しても性能が悪化しないのがTSLFアロケータの特徴です。そのためリリースノートにimproves performance especially when using a high number of allocations in PSRAMと書いてあったとおり大容量のPSRAMでメモリ確保 / 解放を繰り返した場合、大きく性能の改善が期待できます。

おわりに

本エントリではESP-IDF v4.3から変更されたヒープアロケータの挙動に着目して、問題点、実装の概要、v4.2までのアロケータとの比較、を説明しました。OS自作経験があるとこのような問題が発生したときに、カジュアルに「じゃあメモリアロケータの実装調べるか！」という気持ちになれます。やっててよかったOS自作！

special thanks

本エントリの執筆にあたり、Kenta IDA (@ciniml) | Twitter さんにアドバイスをいただきました。

NatureではIoTと電気を組み合わせた新しい電力サービスを作りたいと思っており、エンジニアを積極採用中です。

herp.careers

カジュアル面談も実施していますので、興味がある方はお気軽にご応募ください！

herp.careers

  1. https://github.com/espressif/esp-idf/releases/tag/v4.3↩

  2. http://www.gii.upv.es/tlsf/↩

  3. http://xenbits.xensource.com/↩

  4. https://www.riot-os.org/↩

  5. http://marupeke296.com/ALG_No2_TLSFMemoryAllocator.html↩

  6. https://github.com/catchorg/Catch2↩

*1:v4.2ではheap allocatorはmulti_heap.cの中に実装されており、その境界は曖昧です。v4.3でTLSFアロケータが導入され、multi_heapとheap allocatorの役割が明示的に階層化されています。

*2:PSRAMをmalloc / freeで使うためには次の設定が必要です https://docs.espressif.com/projects/esp-idf/en/latest/esp32/api-guides/external-ram.html#provide-external-ram-via-mallochttps://docs.espressif.com/projects/esp-idf/en/v4.3.2/esp32/api-guides/external-ram.html

*3:第2カテゴリーの分割数は32で固定、ESP32は32ビットプロセッサなのでsizeof(intptr_t)は4です