ご存知のように、現代のx86（_64）およびARMアーキテクチャでは、幸いなことにchar near*



とint huge*



char near*



時間が経過したため、プロセスの仮想メモリは線形で連続的です。 仮想メモリはページに分割されます。通常のサイズは4 KiBであり、デフォルトでは物理メモリにマッピングされないため（マッピング）、それらの操作は機能しません。 プロセスの現在表示されているアドレス範囲を確認するには、Linux look / proc / <pid> / maps、OS X vmmap <pid>で。 各アドレス間隔には、実行、書​​き込み、読み取りの3種類の保護があります。 ご覧のとおり、ロードアドレス（LinuxのELFの.textセグメント、OS XのMach-Oの __TEXTに対応）で始まる最初の間隔は読み取り可能で実行可能です-非常に論理的です。 また、スタックは他の間隔と本質的に変わらないことがわかります。また、最終アドレスから開始アドレスを減算することで、サイズをすばやく計算できます。 ページはmmap / munmapを使用して表示され 、セキュリティはmprotectを使用して変更されます。 「データ」の単一の間隔のサイズを変更し、現代のシステムでmmapによってエミュレートされる過去の非推奨の古代の名残であるbrk / sbrkがまだあります。



mallocのすべてのPOSIX実装は、上記の関数に何らかの形で依存しています。 単純にページを強調表示および解放し、必要なサイズを切り上げることに比べて、mallocには多くの利点があります。

• すでに割り当てられているメモリを最適に管理します。
• カーネルの呼び出し回数を大幅に削減します（結局、mmap / sbrkはsyscallです ）。
• 通常、プログラマは仮想メモリから抽象化されるため、多くの人はページや変換テーブルなどの存在を知らずにmallocを使用します。

十分な理論！ 実際にmallocを感じます。 3つの実験を実行します。 作業はPOSIX互換OSで可能になります。特に、作業はLinuxおよびOS Xでテストされています。

mallocからNULL

ありきたりから始めましょう。 コード内でlibc（および他のライブラリ）から関数を再定義すると、リンカーはlibcが動的に接続するかどうかを気にしません（デフォルトではそうです）、二重定義を誓うことはありません。 たとえば、次のようなコード：

 #include <stdio.h> #include <stdlib.h> void* malloc(size_t size) { puts("malloc"); return NULL; } int main() { return (int)malloc(100500); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「malloc」を出力し、戻りコードがnull（ echo $?



）になります。 ただし、asprintfなど、mallocが呼び出される腸で関数を呼び出すとどうなるかを確認しましょう。

 // program.c #include <stdio.h> #include <stddef.h> void* malloc(size_t size) { puts("malloc"); return NULL; } int main() { char *s = NULL; asprintf(&s, "%d", 0); printf("%p\n", s); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、ここではリンカに大きく依存します。 ld / Linuxの場合、印刷されます

 malloc (nil)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

mallocが呼び出され、再定義され、printfのglibc実装ではmallocが使用されないため。 glibcのmallocが弱い文字 （__attribute __（（weak）））として宣言され、デフォルトの定義が強い（ELFに固有）ため、再定義が行われました。 ただし、dyld / OS Xでは、動作が異なります。

 0x7fc1eb403230
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際、ケシのmallocは再定義されていません！ それは、マルチレベルdyld名前空間に関するものでなければなりません。 さあ、さあ...

 DYLD_FORCE_FLAT_NAMESPACE=1 ./program Segmentation fault: 11
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

不機嫌なBABAG BIG！ このケースは、明らかにint main（）にさえ達しませんでした。 その理由は何ですか？

 lldb lldb ./program (lldb) target create "./program" Current executable set to './program' (x86_64). (lldb) env DYLD_FORCE_FLAT_NAMESPACE=1 (lldb) r Process 11956 launched: './program' (x86_64) Process 11956 stopped * thread #1: tid = 0x12e214, 0x00007fff9ebb9dcb libsystem_kernel.dylib`ioctl + 67, stop reason = EXC_BAD_ACCESS (code=2, address=0x7fff5f3ffff8) frame #0: 0x00007fff9ebb9dcb libsystem_kernel.dylib`ioctl + 67 libsystem_kernel.dylib`ioctl: -> 0x7fff9ebb9dcb <+67>: movq %rcx, -0xb8(%rbp) 0x7fff9ebb9dd2 <+74>: movq %rdx, -0xc0(%rbp) 0x7fff9ebb9dd9 <+81>: leaq -0xd0(%rbp), %rax 0x7fff9ebb9de0 <+88>: movq %rax, -0x10(%rbp) (lldb) bt * thread #1: tid = 0x12e214, 0x00007fff9ebb9dcb libsystem_kernel.dylib`ioctl + 67, stop reason = EXC_BAD_ACCESS (code=2, address=0x7fff5f3ffff8) * frame #0: 0x00007fff9ebb9dcb libsystem_kernel.dylib`ioctl + 67 frame #1: 0x00007fff9a20f2c8 libsystem_c.dylib`isatty + 43 frame #2: 0x00007fff9a222ac6 libsystem_c.dylib`__smakebuf + 60 frame #3: 0x00007fff9a237b4a libsystem_c.dylib`__swsetup + 155 frame #4: 0x00007fff9a221d52 libsystem_c.dylib`__sfvwrite + 73 frame #5: 0x00007fff9a2264c9 libsystem_c.dylib`puts + 144 frame #6: 0x0000000100000f0b program`malloc(size=4096) + 27 at program.c:6 frame #7: 0x00007fff9a222af6 libsystem_c.dylib`__smakebuf + 108 frame #8: 0x00007fff9a237b4a libsystem_c.dylib`__swsetup + 155 ... frame #130931: 0x0000000100000f0b program`malloc(size=4096) + 27 at program.c:6 frame #130932: 0x00007fff9a222af6 libsystem_c.dylib`__smakebuf + 108 frame #130933: 0x00007fff9a237b4a libsystem_c.dylib`__swsetup + 155 frame #130934: 0x00007fff9a221d52 libsystem_c.dylib`__sfvwrite + 73 frame #130935: 0x00007fff9a2264c9 libsystem_c.dylib`puts + 144 frame #130936: 0x0000000100000f0b program`malloc(size=8) + 27 at program.c:6 frame #130937: 0x00007fff5fc1d22e dyld`operator new(unsigned long) + 30 frame #130938: 0x00007fff5fc095a5 dyld`std::__1::vector >::insert(std::__1::__wrap_iter, char const* (* const&)(dyld_image_states, unsigned int, dyld_image_info const*)) + 343 frame #130939: 0x00007fff5fc04507 dyld`dyld::registerImageStateBatchChangeHandler(dyld_image_states, char const* (*)(dyld_image_states, unsigned int, dyld_image_info const*)) + 147 frame #130940: 0x00007fff8bb8089e libdyld.dylib`dyld_register_image_state_change_handler + 76 frame #130941: 0x00007fff8bb8065f libdyld.dylib`_dyld_initializer + 47 frame #130942: 0x00007fff982829fd libSystem.B.dylib`libSystem_initializer + 116 frame #130943: 0x00007fff5fc12feb dyld`ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&) + 265 frame #130944: 0x00007fff5fc13164 dyld`ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&) + 40 frame #130945: 0x00007fff5fc0f79d dyld`ImageLoader::recursiveInitialization(ImageLoader::LinkContext const&, unsigned int, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&) + 305 frame #130946: 0x00007fff5fc0f732 dyld`ImageLoader::recursiveInitialization(ImageLoader::LinkContext const&, unsigned int, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&) + 198 frame #130947: 0x00007fff5fc0f623 dyld`ImageLoader::processInitializers(ImageLoader::LinkContext const&, unsigned int, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&) + 127 frame #130948: 0x00007fff5fc0f893 dyld`ImageLoader::runInitializers(ImageLoader::LinkContext const&, ImageLoader::InitializerTimingList&) + 75 frame #130949: 0x00007fff5fc020f1 dyld`dyld::initializeMainExecutable() + 208 frame #130950: 0x00007fff5fc05e5d dyld`dyld::_main(macho_header const*, unsigned long, int, char const**, char const**, char const**, unsigned long*) + 3793 frame #130951: 0x00007fff5fc01276 dyld`dyldbootstrap::start(macho_header const*, int, char const**, long, macho_header const*, unsigned long*) + 512 frame #130952: 0x00007fff5fc01036 dyld`_dyld_start + 54
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どんなフレーム？ 130952nd？ はい、判明しました、Stack Overflow！ また、いくつかの興味深いことも学びました。dyldはC ++で記述されており、何らかの理由で同じmallocでメモリを割り当て、再帰を作成します。 stdoutバッファーの初期化中に彼がこれを行うのは一度だけだと信じたい。 まあ、私たちはそれを置き換えることを余儀なくされています

 #include <stdio.h> #include <stddef.h> #include <unistd.h> void* malloc(size_t size) { write(STDOUT_FILENO, "malloc\n", 7); return NULL; } int main() { char *s = NULL; asprintf(&s, "%d", 0); printf("%p\n", s); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

開始して確認します。

 malloc malloc malloc Segmentation fault: 11
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スタックフラグメント：

 * thread #1: tid = 0x1309af, 0x00007fff5fc249ce dyld`_platform_bzero + 94, stop reason = EXC_BAD_ACCESS (code=1, address=0x8) * frame #0: 0x00007fff5fc249ce dyld`_platform_bzero + 94 frame #1: 0x00007fff5fc14045 dyld`calloc + 52 frame #2: 0x00007fff5fc0ce14 dyld`__cxa_get_globals + 100 frame #3: 0x00007fff5fc1ce7f dyld`__cxa_throw + 25 frame #4: 0x00007fff5fc1d267 dyld`operator new(unsigned long) + 87
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのため、ldが静的割り当てで作成されているGNU / Linuxとは異なり、OS Xでアプリケーションを実行するときに大量のヒープが集中的に使用されます。 また、new演算子によるメモリの割り当ての失敗に関する例外をスローすると、callocが発生することもわかります。これは、mallocとゼロ（bzero）の埋め込みの組み合わせです。 calloc実装が追いつき、nullポインターをチェックしませんでした。 この知識があれば、OS Xが実際に「最後のバイトまで」メモリを使い果たした場合に起こる考えは、もはや私に休息を与えません。 明らかに、正しい論理的な解決策は、事前にstd :: bad_allocにメモリを割り当てることです。



OK Google、OS Xでmallocを再定義してクラッシュしないようにするにはどうすればよいですか？ 実装の詳細に飛び込む必要があります。 ポピーのMallocは、ゾーンにメモリを割り当てます。 最初は、デフォルトで1つのゾーンのみがあり、vmmapは出力の最後にそれを表示します。 各ゾーンには、malloc、free、およびreallocへのポインターが格納されます。これにより、メモリ管理を柔軟に構成できます。 デフォルトゾーンを使用して、その中のmallocポインターを置き換えることができます。

 #include <stdio.h> #include <stddef.h> #include <unistd.h> #include <malloc/malloc.h> #include <sys/mman.h> void* zone_malloc(struct _malloc_zone_t *zone, size_t size) { write(STDOUT_FILENO, "malloc\n", 7); return NULL; } int main() { malloc_zone_t* zone = malloc_default_zone(); mprotect(zone, sizeof(*zone), PROT_READ | PROT_WRITE); zone->malloc = zone_malloc; mprotect(zone, sizeof(*zone), PROT_READ); char *s = NULL; asprintf(&s, "%d", 0); printf("%p\n", s); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

mprotectに注意してください。 最初に、malloc_default_zoneは、書き込み保護されているメモリ領域へのポインタを返します。 これは、mprotectを使用せずにプログラムを実行し、デバッガーとvmmapでクラッシュを調べることで簡単に確認できます。 このような保護は遊び心のある手から得られます... PROT_READに戻ると、厳密に言えば、保護は変更できませんでした。それは順序のために追加されました。 印刷されるもの：

 malloc malloc 0x0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

printfがmallocを使用したことがわかりますが、動的メモリなしで実行できる強度が見つかり、それでもヌルポインターが出力されました。



ところで、ゾーンについて。 glibcのMallocは、obstacksと呼ばれる同様のトレッキングを使用します。 一方では、それらを操作するための多くの関数がありますが、他方では、異なるobstackで異なるメモリ割り当てアルゴリズムを使用することはできません。



結論： OS XブートローダーであるdyldはC ++で記述されており、int main（）のかなり前にこのシステム上のプログラムの束を処理します。 Linuxのldでは、これは発生せず、ヒープへの呼び出しはありません。

無効なmalloc

次に、新しい目標を設定しましょう。mallocのバージョンを実装する動的ライブラリを作成します。

 // hack_malloc.c #define _GNU_SOURCE #include <stdio.h> #include <stddef.h> #include <unistd.h> #include <sys/mman.h> void* malloc(size_t size) { write(STDOUT_FILENO, "malloc... ", 10); size += sizeof(size_t); int page_size = getpagesize(); int rem = size % page_size; if (rem > 0) { size += page_size - rem; } void* addr = mmap(0, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); if (addr == MAP_FAILED) { write(STDOUT_FILENO, "fail\n", 5); return NULL; } write(STDOUT_FILENO, "ok\n", 3); *(size_t*)addr = size; return (size_t*)addr + 1; } void free (void *ptr) { write(STDOUT_FILENO, "free... ", 8); size_t* real_ptr = (size_t*)ptr - 1; if (!munmap(real_ptr, *real_ptr)) { write(STDOUT_FILENO, "ok\n", 3); } else { write(STDOUT_FILENO, "fail\n", 5); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、ページでメモリを割り当てるときに最も簡単なアプローチが実装されます。 unmapに渡すものがあるように、ページの上部にサイズを保存する必要があります。 mmapフラグのMAP_ANONYMOUSは、実際のファイルをメモリにマップするのではなく、物理メモリをマップすることを意味します（通常、ファイルはmmapによってメモリにマップします。これにより、一部の操作が加速されます）。 ファイルの場合、MAP_PRIVATEは個別のコピーオンライトコピーを作成しますが、実際には何もしません。ドキュメントだけでMAP_PRIVATEまたはMAP_SHAREDが必要です。 ちなみに、MAP_SHAREDを使用すると、このコードもうまく機能します。



例で確認します。

 // test.c #include <stdio.h> #include <stdlib.h> int main() { printf("start\n"); void* mem = malloc(100); printf("malloc() -> %p\n", mem); *(int*)mem = 0; free(mem); printf("end\n"); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このように組み立てます：

 #Linux gcc -shared -o libhackmalloc.so -fPIC -std=c99 -O2 hack_malloc.c gcc test.c -std=c99 -L. -Wl,-rpath,. -lhackmalloc -O2 -o test # Mac OS X clang -dynamiclib -undefined suppress -flat_namespace -std=c99 -fPIC -O2 hack_malloc.c -o libhackmalloc.dylib clang test.c -std=c99 -L. -lhackmalloc -O2 -o test
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

起動時に、以下が表示されます。

 ./test start malloc... ok malloc() -> 0x10935b008 free... ok end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

OS XとLinuxの出力は同じです。 OS Xの場合、Windows 10インターフェイスのように、dyld名前空間を考えてフラットにします。

 DYLD_FORCE_FLAT_NAMESPACE=1 ./test malloc... ok malloc... ok free... ok malloc... ok malloc... ok free... fail free... fail free... fail malloc... ok malloc... ok free... fail malloc... ok 70  free... fail 17  malloc... ok free... ok malloc... ok malloc... ok malloc... ok free... fail malloc... ok start malloc... ok malloc() -> 0x1035d9008 free... ok end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラムは機能し、すでに良好でした。 驚くべきことは、int main（）の前にmallocとfreeを呼び出す回数の明らかな矛盾です。 無料も何度も失敗しました。 興味のある方は、デバッガでテストを実行し、ブレーカーを無料で使用して、dyldのダークライフについて多くを学ぶことができます。



結論： mallocの実装を30行で「直接」書くことはかなり可能です。

mallocのスパイ

DLLインジェクション手法を使用して、mallocを他の人のプログラムにインジェクトしてみましょう。 Buddyなど、興味深いアルゴリズムは数多くありますが、ヒープの効果的な実装を独自に記述したくありません。 既製の実装を使用することも可能ですが、RTLD_NEXTトリックを適用してシステムmallocを参照します。 次のコードを検討してください。

 // trace_malloc.c #define _GNU_SOURCE #include <dlfcn.h> #include <fcntl.h> #include <stdio.h> #include <unistd.h> int fd = 0; void* (*__malloc)(size_t) = NULL; void* malloc(size_t size) { if (!__malloc) { __malloc = (void*(*)(size_t)) dlsym(RTLD_NEXT, "malloc"); } if (!fd) { fd = open("malloc.log", O_WRONLY | O_CREAT | O_TRUNC, 0666); } /* ... */ write(fd, record, sprintf(record, "%ld.%06ld\t%zu\n", sec, mcsec, size)); return __malloc(size); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードの完全版へのリンクは、記事の最後に記載されます。 半分はclock_gettimeのクロスプラットフォーム実装によって消費され、2番目はclock_gettimeにアクセスするため、少し削減しなければなりませんでした。 すべての魅力を1行で：

 __malloc = (void*(*)(size_t)) dlsym(RTLD_NEXT, "malloc");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その中で「前の」mallocをロードします。 通常、dlsymはロードされた動的ライブラリから関数をプルするために使用されますが、マジックRTLD_NEXTをライブラリ記述子として使用しました。 厳密に言えば、POSIXにはありませんが、実際には多くのリンカーでサポートされています。 したがって、真のmallocへのポインターを取得し、保存してから呼び出して、結果を返します。 途中で、すべての呼び出しを記録します。



hack_malloc.cと同じ方法でビルドし、Linuxで次のように使用します。

 LD_PRELOAD=/path/to/libtracemalloc.so program
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パスは絶対パスでなければなりません。そうしないと、魔法は発生しません。 LD_PRELOADは、プログラムがビルドされるメインライブラリの前に指定されたライブラリを強制的にロードする特別な環境変数です。 この方法で、任意の関数を再定義したり、誤ってリンクされたプログラム（同じlib * .so：not foundメッセージ）の起動に関する一時的な問題を解決できます。



たとえば、Lsは約2 KBのログを作成します。 また、whoamiは、未定義のシンボルメッセージdlsymを伴います。これは、dlsymがlibdl.soで定義されているためです。 また、LD_PRELOADは挿入されたライブラリの依存関係をロードしないため、-ldlを指定してlibtracemallocをビルドすることは意味がありません。 このようなことをしなければなりません：

 LD_PRELOAD=/usr/lib/.../libdl.so:/path/to/libtracemalloc.so whoami
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、このような基本ユーティリティの場合でも、1 KBのメモリ割り当てログが表示されます。



OK、OS Xはどうですか？ Dyldは、同様のことを行うDYLD_INSERT_LIBRARIES環境変数をサポートしています。 私達は試みます：

 DYLD_INSERT_LIBRARIES=/path/to/libtracemalloc.dylib ls
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...機能しません、名前空間について覚えておいてください：

 DYLD_INSERT_LIBRARIES=/path/to/libtracemalloc.dylib DYLD_FORCE_FLAT_NAMESPACE=1 ls
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...そしてまた残念。 すでに面白い！ 重要なのは、 System Integrity Protectionシステムプログラムを保護することです。 拡張ファイル属性を使用したこのメカニズムでは、ファイルの変更、コードの挿入、/ System、/ usrなどのパスのディベースは許可されません。幸いなことに、/ usr / localは許されました。

 lldb /bin/ls (lldb) target create "/bin/ls" Current executable set to '/bin/ls' (x86_64). (lldb) r error: process exited with status -1 (cannot attach to process due to System Integrity Protection)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SIPは無効にできますが、簡単にできます-興味のあるプログラムをディレクトリにコピーします。

 cp $(which ls) . DYLD_INSERT_LIBRARIES=/path/to/libtracemalloc.dylib DYLD_FORCE_FLAT_NAMESPACE=1 ./ls
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すでに機能しています。 結論として、2種類のメモリ割り当てに関する有名な論文を証明します。 mallocログを収集し、IPythonの基本コードを使用してサイズ分布のヒストグラムを作成しましょう。

 %pylab import pandas, seaborn log = pandas.DataFrame.from_csv("malloc.log", sep='\t') log[log < 100].hist() log[log < 100].count() / len(log)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

典型的な画像は、サイズヒストグラムに表示されます（Y-呼び出し回数、X-サイズ、プログラム-clang）：







私は故意にテールを100バイトにカットしました。これは、より大きな割り当てが非常にまれであり、ヒストグラムに表示されないためです。 したがって、 ヒープ内のすべてのメモリ割り当ての98％は100バイト未満です。つまり、優れたmallocは、少なくとも2つの別個のドメイン（大きなオブジェクト用とそれ以外のユーザー用）に対応する必要があります。



プログラムを分析するために、上記のような自己アセンブルされたライブラリを使用することはできませんが、既製のものを使用することができます。 たとえば、 tcmallocを使用すると、束のプロファイルを作成したり、他の多くの便利なことを実行したりできます 。



この記事のコードはgithubで入手できます。 次回、実際の大規模なプログラムを使用して、その動作中にメモリ割り当てのログを収集し、再帰的ニューラルネットワークのLSTMモデルに基づいて予測を試みます。