Круче кучи! Разбираем в подробностях проблемы heap allocation

Прак­тиковать­ся мы будем на реали­зации кучи ptmalloc2, которая сей­час исполь­зует­ся по умол­чанию в glibc, поэто­му нам понадо­бят­ся машина с Linux и необ­ходимый софт. Уста­новим отладчик GDB, GCC (мож­но сра­зу пос­тавить весь пакет build-essential) и отла­доч­ную вер­сию биб­лиоте­ки libc, поз­воля­ющую видеть под­робную информа­цию о куче. Так­же пос­тавим pwngdb и его зависи­мость — peda, что­бы получить удоб­ные коман­ды vmmap, hexdump, heapinfo.

Основы GDB

Для изу­чения работы наших тес­товых прог­рамм понадо­бит­ся зна­ние базовых команд GDB:

• r[un] — запус­тить файл;
• b[reak] *0x1234 — пос­тавить точ­ку оста­нова на адре­се 0x1234;
• b[reak] 123 — пос­тавить точ­ку оста­нова на стро­ке 123 текуще­го исходно­го фай­ла;
• b[reak] basic.c:123 — пос­тавить точ­ку оста­нова на стро­ке 123 исходно­го фай­ла basic.c;
• c[ontinue] — про­дол­жить выпол­нение;
• s[tep] — выпол­нить одну ассем­блер­ную инс­трук­цию;
• n[ext] — выпол­нить одну строч­ку исходно­го фай­ла;
• x/10xg 0x1234 — рас­печатать десять 8-бай­тных слов по адре­су 0x1234;
• p[rint] a — рас­печатать зна­чение перемен­ной a;
• p[rint] *((mchunkptr)0x555555756680) — взять содер­жимое памяти по адре­су 0x555555756680 как тип mchunkptr, задере­ферен­сить его и рас­печатать;
• where — показать, на какой строч­ке исходно­го кода находит­ся выпол­нение прог­раммы.

Ко­ман­ды peda и pwngdb:

• vmmap — вывес­ти кар­ту памяти;
• hexdump — показать содер­жимое памяти по адре­су в виде hexdump;
• heapinfo — пос­мотреть информа­цию о куче.

Структура чанков

Ког­да прог­рамма зап­рашива­ет буфер для дан­ных (нап­ример, раз­мером в 10 байт) с помощью malloc, на самом деле выделя­ется боль­ше памяти, так как для хра­нения метадан­ных необ­ходимо допол­нитель­ное прос­транс­тво. Такой кусок памяти, содер­жащий метадан­ные, называ­ют чан­ком (chunk).

Струк­тура чан­ка, исполь­зуемая в ptmalloc2, при­веде­на ниже. Из нее мож­но понять, что перед ука­зате­лем на выделен­ный буфер памяти, который воз­вра­щает­ся поль­зовате­лю (mem), рас­полага­ются еще два поля: раз­мер чан­ка и раз­мер пре­дыду­щего чан­ка.

Сам чанк име­ет такую струк­туру:

Что­бы получить из ука­зате­ля на чанк (слу­жеб­ную струк­туру) ука­затель на буфер памяти, который мож­но исполь­зовать, к пер­вому при­бав­ляют зна­чение 2*SIZE_SZ. SIZE_SZ. Для архи­тек­туры x64 оно рав­но 8, а для x86 — 4. То есть на x64 user_mem = chunk + 16. И наобо­рот, что­бы из ука­зате­ля, который вер­нул malloc, получить ука­затель на чанк, необ­ходимо вычесть 2*SIZE_SZ из него. За это отве­чают сле­дующие мак­росы:

Важ­ный момент: поле mchunk_prev_size в сле­дующем чан­ке исполь­зует­ся для хра­нения поль­зователь­ских дан­ных пре­дыду­щего чан­ка.

Арена

Ста­рые менед­жеры кучи исполь­зовали одну кучу на весь про­цесс и син­хро­низи­рова­ли дос­туп к ней раз­ных потоков с помощью мьютек­сов. Как нес­ложно догадать­ся, положи­тель­но на про­изво­дитель­нос­ти это не ска­зыва­лось. Ptmalloc2 исполь­зует аре­ны — области памяти для того, что­бы каж­дый поток мог там хра­нить свою кучу.

Но пос­коль­ку на прак­тике потоков в при­ложе­нии может быть слиш­ком мно­го, мак­сималь­ное количес­тво соз­дава­емых арен вычис­ляет­ся по сле­дующей фор­муле (n — количес­тво про­цес­соров):

По­ка количес­тво арен мень­ше мак­сималь­ного, менед­жер кучи соз­дает новую аре­ну на каж­дый новый поток. Пос­ле это­го, увы, нес­коль­ким потокам при­дет­ся делить меж­ду собой одну аре­ну.

Пер­вая соз­данная менед­жером кучи аре­на называ­ется основной (main). Одно­поточ­ное при­ложе­ние исполь­зует толь­ко основную аре­ну.

Флаги

Ос­тановим­ся под­робнее на фла­гах чан­ка. Поле раз­мера пре­дыду­щего чан­ка (mchunk_size), кро­ме собс­твен­но раз­мера, хра­нит три фла­га: A, M, P. Это воз­можно за счет вырав­нивания раз­мера чан­ка. Так как раз­мер чан­ка всег­да кра­тен либо 8, либо 16 бай­там, пос­ледние 3 бита раз­мера не несут смыс­ловой наг­рузки, и их мож­но исполь­зовать для хра­нения фла­гов.

• A (NON_MAIN_ARENA): 0 — чанк был выделен из основной аре­ны и основной кучи; 1 — чанк при­над­лежит одной из вто­рос­тепен­ных арен. Ког­да при­ложе­ние соз­дает допол­нитель­ные потоки, каж­дый из них получа­ет свою аре­ну (гру­бо говоря, свою кучу). В чан­ках, выделя­емых на этих аре­нах, уста­нов­лен бит A;
• M (IS_MMAPPED): 1 — чанк получен с помощью вызова mmap. Осталь­ные фла­ги игно­риру­ются, потому что дан­ные чан­ки не рас­полага­ются в аре­не и к ним не при­мыка­ют дру­гие чан­ки;
• P (PREV_INUSE): 0 — пре­дыду­щий чанк не исполь­зует­ся. Перед полем mchunk_size рас­полага­ется зна­чение раз­мера пре­дыду­щего чан­ка; 1 — пре­дыду­щий чанк исполь­зует­ся. Перед полем mchunk_size рас­полага­ются поль­зователь­ские дан­ные.

Bins

Для повыше­ния быс­тро­дей­ствия чан­ки исполь­зуют пов­торно (и имен­но эту осо­бен­ность учи­тыва­ют при экс­плу­ата­ции кучи). Ранее исполь­зован­ные и осво­бож­денные чан­ки скла­дыва­ют в бины (bins). В нашей реали­зации кучи сущес­тву­ет пять типов бинов:

• small (62 шту­ки);
• large (63 шту­ки);
• unsorted (1 шту­ка);
• fast (10 штук);
• tcache (64 на поток).

Small bins

• Чан­ки в каж­дом из small bin хра­нят­ся в двус­вязном спис­ке.
• Встав­ка осво­бож­денных чан­ков в этот спи­сок про­изво­дит­ся с начала (head), уда­ление — с кон­ца (tail, FIFO). Для ведения это­го спис­ка исполь­зуют­ся ука­зате­ли fd и bk (см. струк­туру чан­ка).
• Та­ких бинов 62 шту­ки. Каж­дый из small bins хра­нит чан­ки толь­ко одно­го раз­мера: 16, 24, ..., 504 байт для x86 и 1008 байт для x64.
• Ес­ли в small bin попада­ют два сосед­них чан­ка, то они объ­еди­няют­ся и отправ­ляют­ся в unsorted bin.

Large bins

• Чан­ки в каж­дом из large bin так­же хра­нят­ся в двус­вязном спис­ке.
• Чан­ки в каж­дом из бинов име­ют диапа­зон раз­меров.
• Чан­ки сор­тиру­ются сле­дующим обра­зом: самый боль­шой чанк находит­ся в head спис­ка, а самый малень­кий — в tail. Для это­го исполь­зуют­ся ука­зате­ли fd_nextsize и bk_nextsize.
• Встав­ки и уда­ления про­исхо­дят на любой позиции.
• Та­ких бинов 63 шту­ки, в них хра­нят­ся чан­ки раз­мером от 512 байт для x86 и от 1024 байт для x64.