Експерименти з malloc

image

Як відомо, в сучасних архітектур x86(_64) і ARM віртуальна пам'ять процесу лінійна і неперервна, бо, на щастя, минули часи
char near*
та
int huge*
. Віртуальна пам'ять поділена на сторінки, типовий розмір яких 4 KiB, і за замовчуванням вони не відображені на фізичну пам'ять (mapping), так що працювати з ними не вийде. Щоб подивитися поточні відображені інтервали адрес у процесу, в Linux дивимося /proc/<pid>/maps, в OS X vmmap <pid>. У кожного інтервалу адрес є три види захисту: від виконання, запису та читання. Як видно, перший інтервал, який починається з load address (відповідний сегменту .text у ELF в Linux, __TEXT у Mach-O OS X), доступний на читання і виконання — дуже логічно. Ще можна побачити, що стек по суті нічим не відрізняється від інших інтервалів, і можна швидко вирахувати його розмір, віднявши з кінцевого адреси початковий. Відображення сторінок виконується за допомогою mmap/munmap, а захист змінюється за допомогою mprotect. Ще існують brk/sbrk, deprecated давні пережитки минулого, які змінюють розмір одного-єдиного інтервалу «даних» і в сучасних системах емулюються mmap'ом.

Всі POSIX-реалізації malloc так чи інакше впираються в перераховані вище функції. Порівняно з наївним виділенням і звільненням сторінок, округляючи необхідний розмір в більшу сторону, malloc має багато переваг:

  • оптимально керує вже виділеної пам'яттю;
  • значно зменшує кількість звернень до ядра (адже mmap — це syscall);
  • взагалі абстрагує програміста від віртуальної пам'яті, так що багато користуються malloc'ом, взагалі не підозрюючи про існування сторінок, таблиць трансляції і т. п.
Досить теорії! Будемо мацати malloc на практиці. Проведемо три експерименту. Робота буде можлива на POSIX-сумісних операционках, зокрема була перевірена робота на Linux і OS X.

NULL з malloc
Почнемо з банального. Якщо перевизначити функцію з libc (як і будь-який інший бібліотеки) у себе в коді, то linker не буде проти, якщо libc динамічно підключається (а за замовчуванням саме так), і не буде лаятися на подвійне визначення. Наприклад, такий код:

#include < stdio.h>
#include <stdlib.h>

void* malloc(size_t size) {
puts("malloc");
return NULL;
}

int main() {
return (int)malloc(100500);
}

Він буде друкувати «malloc» і мати нульовий код повернення (
echo $?
). Однак давайте перевіримо, що буде, якщо викликати яку-небудь функцію, в надрах якої викликається malloc, наприклад asprintf.

// 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;
}

І тут буде сильно залежати від linker'а. Якщо це ld/Linux, то надрукується

malloc
(nil)

Бо malloc викличеться наш, перевизначено, а glibc-реалізація printf не використовує malloc. Але при dyld / OS X поведінку інше:

0x7fc1eb403230

Насправді malloc на маці не переопределился! Справа має бути в багаторівневих просторах імен dyld. Ну-ка, ну-ка…

DYLD_FORCE_FLAT_NAMESPACE=1 ./program
Segmentation fault: 11

Хрясь БАБАХ бдыжь! Справа, вочевидь, навіть не дійшло до 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, const char* (* const&)(dyld_image_states, unsigned int, dyld_image_info const*)) + 343
frame #130939: 0x00007fff5fc04507 dyld'dyld::registerImageStateBatchChangeHandler(dyld_image_states, const char* (*)(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, const char**, const char**, const char**, unsigned long*) + 3793
frame #130951: 0x00007fff5fc01276 dyld'dyldbootstrap::start(macho_header const*, int, const char**, long, macho_header const*, unsigned long*) + 512
frame #130952: 0x00007fff5fc01036 dyld'_dyld_start + 54

Будь-який кадр? 130952-й? Та у нас, виявляється, Stack Overflow! А ще ми дізналися кілька цікавих речей: dyld написаний на C++, а puts навіщо-то виділяє пам'ять тим самим 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

Отже, видно, що на відміну від GNU/Linux, ld якого зроблений на статичній алокації, при запуску програми в OS X інтенсивно використовується купа. Також видно, що викид винятки про невдалий виділення пам'яті оператором new викликає calloc, який, як ми пам'ятаємо, є комбінація malloc + заповнення нулями (bzero). Реалізація calloc попалася бажная і не перевірила нульовий покажчик. З цим знанням мені тепер не дасть спокою думка, що буде, якщо в OS X по-справжньому закінчиться пам'ять, «до останнього байта». Очевидно, що правильним і логічним рішенням було б заздалегідь виділяти пам'ять для std::bad_alloc.

Ок, Гугл, як нам все-таки перевизначити malloc під OS X так, щоб нічого не падало? Доведеться зануритися в деталі реалізації. Malloc на маці виділяє пам'ять в зонах. Спочатку зона всього одна, за замовчуванням, і саме її покаже 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, але потім знайшов у собі сили обійтися без динамічної пам'яті і все одно роздрукував нульовий покажчик.

До речі, про зонах. Malloc в glibc використовує схожий похід, який назвали obstacks. З одного боку, для роботи з ними існує багато функцій, з іншого боку, відсутня можливість застосовувати в різних obstack'ах різні алгоритми виділення пам'яті.

Висновок: dyld, завантажувач OS X, написаний на C++ і робота з купою в програмах на цій системі починається задовго до int main(). C ld на Linux такого не відбувається і звернень до купі немає.

Неефективний 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. MAP_ANONYMOUS в прапорах mmap означає, що ми відображаємо в пам'ять не реальний файл, а фізичну пам'ять (зазвичай mmap'ом відображають в пам'ять саме файли, це дає прискорення в деяких операціях). MAP_PRIVATE у разі файлів створював би індивідуальну копію запису (copy-on-write), але для нас, по суті, нічого не робить, просто документація вимагає присутності або 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 згадуємо про простору імен dyld і робимо їх плоскими, як інтерфейс Windows 10.

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

Програма відпрацювала, і вже добре. Що дивно — явне невідповідність між кількістю викликів malloc і free перед int main(). Також free багато разів завершувався невдало. Зацікавлені можуть запустити test в налагоджувач, поставити на бряку free і дізнатися про темну життя dyld багато нового, а ми будемо рухатися далі.

Висновок: цілком реально написати реалізацію malloc «в лоб» в 30 рядків.

Шпигує за malloc
Спробуємо використовувати техніку DLL injection, щоб впроваджувати свій 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, а другу — звернення до clock_gettime, так що я був змушений трохи скоротити. Вся принадність у однієї рядку:

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

У ній ми подгружаем «попередній» malloc. Зазвичай dlsym використовують для витягування функцій з завантажених динамічних бібліотек, але у нас як дескриптора бібліотеки використаний магічний RTLD_NEXT. Строго кажучи, в POSIX його немає, але за фактом його підтримують багато linker'и. Отже, ми отримуємо вказівник на істинний malloc, зберігаємо його і згодом викликаємо, повертаючи його результат. Попутно логируем всі виклики.

Збираємо так само, як і hack_malloc.c, використовуємо на Linux так:

LD_PRELOAD=/path/to/libtracemalloc.so program

Шлях обов'язково повинен бути абсолютним, інакше магія не трапиться. LD_PRELOAD — спеціальна змінна оточення, насильно подгружающая зазначені бібліотеки перед основними, з якими зібрана програма. Таким чином можна змінити довільні функції або вирішувати тимчасові проблеми з запуском неправильно скомпонованих програм (те саме повідомлення lib*.so: not found).

Ls, приміром, створює близько 2 KB лода. А whoami впаде з повідомленням undefined symbol: dlsym, тому що dlsym визначений у libdl.so, який деякі подгружают, а деякі ні. І немає сенсу збирати libtracemalloc з -ldl, так як LD_PRELOAD не буде довантажувати залежності інжектіруемих бібліотек. Доведеться робити як-то так:

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

І ми побачимо кілобайт лода виділень пам'яті навіть у випадку такої елементарної утиліти.

Ок, а що там з 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

Так вже працює. На закінчення доведемо відомий теза про двох типах виділення пам'яті. Зберемо лог 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 повинен обслуговувати мінімум два окремих домену: для великих об'єктів і для всіх інших.

Зауважимо, що для того, щоб проаналізувати вашу програму, можна не возитися з самосборной бібліотекою зразок описаної вище, а взяти вже готову. Наприклад, tcmalloc дозволяє профілювати купу і робити багато іншого корисного.

Код статті доступний на гітхабі. Наступного разу ми візьмемо справжню, велику програму, зберемо лог виділення пам'яті під час її роботи і спробуємо робити передбачення на основі LSTM-рекурсивної моделі нейронної мережі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.