実行時のスタックの消費量を調べる

2006年4月28日

実行時のスタックの消費量を調べる

先日の記事では checkstack.pl を用いて個々の関数がどのくらいスタックを消費するか調べる方法を紹介しました。今回は、実行時の実際のスタック消費量を調べてみます。

以下のコードでは次のような方法でスタックの消費量を調べます。x86_32 の Linux 用です。

最初に max_num_pages 分だけスタックを伸ばす
伸ばした分をすべて mprotect でアクセス不能にしてしまう
SIGSEGV を拾って 1ページずつアクセス可能に設定する
最後に、何ページ使ったかを表示する

このような処理を行う共有オブジェクトを作成して LD_PRELOAD してやれば、実行時のスタック消費量をページ単位で調べられるのではないか、という試みです。

#include <asm/page.h>
#include <assert.h>
#include <errno.h>
#include <signal.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/resource.h>

static int max_num_pages = 2048;  // default
static void *stack_start_page;
static void *stack_current_page;
static void *stack_end_page;

static void *page_lower_bound(void *addr) {
    return (void *)((uintptr_t)addr & ~(PAGE_SIZE - 1));
}

static void install_sigaltstack() {
    const int alt_stack_size = PAGE_SIZE * 100;
    stack_t new_stack;
    new_stack.ss_sp = malloc(alt_stack_size);
    assert(new_stack.ss_sp != NULL);
    new_stack.ss_size = alt_stack_size;
    new_stack.ss_flags = 0;
    int status = sigaltstack(&new_stack, NULL);
    assert(status == 0);
}

static void signal_handler(int sig, siginfo_t *sig_info, void *sig_data) {
    if (sig_info->si_addr <= stack_end_page ||
        sig_info->si_addr >= stack_current_page)  {
        fprintf(stderr, "SIGSEGV in somewhere else\n");
        abort();
    }
    stack_current_page -= PAGE_SIZE;
    if (stack_current_page == stack_end_page) {
        fprintf(stderr, "reaches the stack end\n");
        abort();
    }
    // PROT_EXEC for trampoline code.
    int status = mprotect(stack_current_page, PAGE_SIZE,
                          PROT_READ | PROT_WRITE | PROT_EXEC);
    assert(status == 0);
}

static void grow_stack_until_passing(void *addr){
    if (__builtin_frame_address(0) < addr) {
        return;
    }
    grow_stack_until_passing(addr);
}

static void install_signal_handler() {
    struct sigaction new_sa = {};
    new_sa.sa_sigaction = signal_handler;
    new_sa.sa_flags = SA_SIGINFO | SA_RESTART | SA_ONSTACK;
    sigemptyset(&new_sa.sa_mask);
    sigaddset(&new_sa.sa_mask, SIGSEGV);
    int status = sigaction(SIGSEGV, &new_sa, NULL);
    assert(status == 0);
}

static void __attribute__((constructor))
init_stack_check() {
    const char *p = getenv("MAX_NUM_PAGES");
    if (p != NULL) {
        max_num_pages = atoi(p);
    }
    struct rlimit rlim = {};
    getrlimit(RLIMIT_STACK, &rlim);
    assert(rlim.rlim_cur > max_num_pages * PAGE_SIZE);

    install_sigaltstack();
    install_signal_handler();
    void *ebp = __builtin_frame_address(0);
    stack_current_page = page_lower_bound(ebp);
    while (ebp) {
        stack_start_page = page_lower_bound(ebp);
        ebp = *(void **)ebp;
    }
    // + 1 for the last page which we don't use.
    stack_end_page = stack_current_page - PAGE_SIZE * (max_num_pages + 1);
    grow_stack_until_passing(stack_end_page + PAGE_SIZE);
    int status = mprotect(stack_end_page, PAGE_SIZE * (max_num_pages + 1),
                          PROT_NONE);
    assert(status == 0);
}

static void __attribute__((destructor))
show_diagnosis() {
    int num_pages = (stack_start_page - stack_current_page) / PAGE_SIZE + 1;
    fprintf(stderr, "stack consumed %d pages\n", num_pages);
}

長くなってしまいましたが、ようするに init_stack_check() で初期化を行い、show_diagnosis() で結果を表示しています。これらはそれぞれ main() の前後で呼ばれます。

実験

それでは実験です。以下のプログラムのスタック消費量を調べてみます。

#include <stdlib.h>
static void test_func(int n) {
    if (n == 0) return;
    test_func(n - 1);
}
int main(int argc, char **argv) {
    test_func(atoi(argv[1]));
    return 0;
}

結果は以下の通りです。

% gcc -shared -Wall -o stackcheck.so stackcheck.c
% gcc test.c
% LD_PRELOAD=./stackcheck.so ./a.out 1
stack consumed 1 pages
% LD_PRELOAD=./stackcheck.so ./a.out 10
stack consumed 1 pages
% LD_PRELOAD=./stackcheck.so ./a.out 100
stack consumed 1 pages
% LD_PRELOAD=./stackcheck.so ./a.out 1000
stack consumed 4 pages
% LD_PRELOAD=./stackcheck.so ./a.out 10000
stack consumed 30 pages
% LD_PRELOAD=./stackcheck.so ./a.out 100000
stack consumed 294 pages

再帰の回数を増やしていくと消費されるページ数は上がっていきました。100,000回で 294ページ (1,176KB) ということは 294*4096/100000 ≒ 12 で、test_func() の呼出しごとに 12バイトが消費されていることがわかります。12バイトの内訳は、引数の n、戻りアドレス、ひとつ前のスタックフレームへのポインタ、の3つの32ビットのデータです。

問題点

stackcheck.so をいくつかのプログラムで試したところ、emacs のような凝ったプログラムや libpthread.so がリンクされたプログラム (手元の環境では /bin/ls や /bin/date なども libpthread.so をリンクしている) では起動時にクラッシュすることがわかりました。どちらの場合も init_stack_check() 内の mprotect() がクラッシュの原因となっています。残念ながら、うまい対処方法は思いつきませんでした。

その他のアプローチ

憂鬱な午後のひとときの 4月26日では、スタックをマジックナンバーで塗りつぶしておいて、後からどこまで上書きされたかを調べる方法が紹介されています。

まとめ

実行時の実際のスタックの消費量を調べるプログラムを思いつきで作ってみました。今回のプログラムが実際に役立つことはなさそうですが、上のコードの中で使われている、 sigaltstack, __builtin_frame_address, mprotect といった手法は割といろいろな場面で使えるのではないかと思います。

bkブログ

2006年4月28日

実行時のスタックの消費量を調べる

実験

問題点

その他のアプローチ

まとめ