malloc読んでみた3 mallocの中のデータ型

mallocで使われるデータ型はまずarenaがあります。
arenaはarena_bin_tの配列を持っています。

struct arena_s {
        ...
        arena_bin_t        bins[1]; /* Dynamically sized. */
    };

arena_binはarena_runの赤黒木を持っています。

struct arena_bin_s {
        arena_run_t    *runcur;

        /*
         * Tree of non-full runs. This tree is used when looking for an
         * existing run when runcur is no longer usable. We choose the
         * non-full run that is lowest in memory; this policy tends to keep
         * objects packed well, and it can also help reduce the number of
         * almost-empty chunks.
         */
        arena_run_tree_t runs;

       ...
    };

arena_newの中でarena->binsが準備されていきます。

i = 0;

        /* (2^n)-spaced tiny bins. */
        for (; i < ntbins; i++) {
            bin = &arena->bins[i];
            bin->runcur = NULL;
            arena_run_tree_new(&bin->runs);
            bin->reg_size = (1U << (TINY_MIN_2POW + i));
            prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
            ....
        }

それぞれのbinの中にtreeを作り

bin->reg_sizeを設定します。

arena_bin_run_size_calc内ではなるべく大きなrun_sizeを探し

    bin->run_size

    bin->nregs

    bin->regs_mask_nelms

    bin->reg0_offset

を設定します。

arena_bin_nonfull_run_getでbin->runsから使用可能なrunをもってきます。ない場合はarena_run_allocでrunを作ります。

bin->runsizeはarena_run_allocのsizeに使われます。

arena_run_allocではarena->runs_availから探し返します。無い場合はarena_chunk_allocをしてその先頭をrunとして返します。

chunk = arena_chunk_alloc(arena);
        if (chunk == NULL)
            return (NULL);
        run = (arena_run_t *) ( (uintptr_t)chunk + (arena_chunk_header_npages < <
            PAGE_SHIFT));
        /* Update page map. */
        arena_run_split(arena, run, size, large, zero);
        return (run);　(2720)

mallocが呼ばれた時のsizeに応じてbinを探し出します。例えば

arena_malloc_small(arena_t *arena, size_t size, bool zero)
    {
        ...
        binind = size2bin[size];
        ...
        bin = &arena->bins[binind];
        size = bin->reg_size;

        ...

のようになります。そしてarena_bin_nonfull_run_getを呼びそのbinからrunを取ります。そのrunからメモリーをarena_run_reg_allocで取り出します。

arenaとbinとrunの関係がわかりました。次はchunkについて見てみましょう。