Хакер - Сборка мусора. Разбираем мифы об автоматическом управлении памятью

https://t.me/hacker_frei

Даниил Батурин

Содержание статьи

• Ошибки управления памятью
• Что делает сборщик мусора?
• Сборщик мусора — часть языка?
• Используем Boehm GC
• Сборщик мусора — неуправляемый черный ящик?
• Все реализации сборки мусора одинаковы?
• Подсчет ссылок и его проблемы
• Tracing garbage collectors
• Заключение

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

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

ОШИБКИ УПРАВЛЕНИЯ ПАМЯТЬЮ

Для начала вспом­ним, от чего нас спа­сает авто­мати­чес­кое управле­ние памятью.

Пер­вая и самая извес­тная, но при этом не самая опас­ная — утеч­ка памяти (memory leak). Утеч­ка про­исхо­дит, если зап­росить у ядра ОС память и забыть ее вер­нуть. В тер­минах язы­ка С — выз­вать malloc() и забыть free(). Прог­рамма с этой проб­лемой будет занимать все боль­ше и боль­ше памяти, пока ее не оста­новит поль­зователь или сама ОС. Поведе­ние прог­раммы при этом оста­ется кор­рек­тным, и проб­лем с безопас­ностью утеч­ки не вызыва­ют.

Вто­рая проб­лема — висячие ука­зате­ли (dangling pointers). Суть проб­лемы в том, что в прог­рамме оста­ется ука­затель на учас­ток памяти, который уже был осво­бож­ден. Для пов­торно­го обра­щения к такой памяти есть отдель­ный тер­мин — use after free. Такие ошиб­ки гораз­до опас­нее, и пос­ледс­твия могут быть самыми раз­ными: от слож­ных в отладке глю­ков до воз­можнос­ти выпол­нить про­изволь­ный код — база CVE не даст сов­рать.

Бо­лее ред­кий вари­ант проб­лемы с висячим ука­зате­лем — пов­торное осво­бож­дение (double free), которое унич­тожа­ет полез­ные дан­ные.

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

ЧТО ДЕЛАЕТ СБОРЩИК МУСОРА?

Уп­рощен­но мож­но ска­зать, что при запус­ке у прог­раммы есть неп­рерыв­ный диапа­зон адре­сов, куда она может помес­тить свои дан­ные. Прог­рамма с авто­мати­чес­ким управле­нием памятью сра­зу при запус­ке зап­рашива­ет у ОС область памяти под «кучу» (heap). Началь­ный раз­мер кучи час­то (но не всег­да) мож­но нас­тро­ить во вре­мя ком­пиляции или выпол­нения. При выпол­нении прог­раммы раз­мер кучи может рас­ти.

Пос­ле это­го сбор­щик мусора пери­оди­чес­ки сле­дит за тем, какие учас­тки памяти еще содер­жат нуж­ные дан­ные, а какие мож­но осво­бодить и запол­нить новыми дан­ными. Как имен­но он это дела­ет — зависит от реали­зации, но об этом даль­ше. Для начала раз­веем более прос­тые мифы.

СБОРЩИК МУСОРА — ЧАСТЬ ЯЗЫКА?

Час­то мож­но услы­шать утвер­жде­ния вро­де «Ruby — язык со сбор­кой мусора» или «С — язык с руч­ным управле­нием памятью». Пер­вое утвер­жде­ние вер­но в том смыс­ле, что ни одна реали­зация Ruby не пре­дос­тавля­ет воз­можность управлять памятью вруч­ную.

Со вто­рым утвер­жде­нием слож­нее. Сбор­ка мусора не вхо­дит в спе­цифи­кацию язы­ка С. Тем не менее спе­цифи­кация ее и не зап­реща­ет. Спе­цифи­кация язы­ка ада так­же не навязы­вает авто­рам ком­пилято­ров какую‑то кон­крет­ную модель управле­ния памятью, но некото­рые ком­пилято­ры при этом пре­дос­тавля­ют опци­аль­ный сбор­щик мусора.

Та­кие ком­пилято­ры С мне неиз­вес­тны, но на прак­тике авто­мати­чес­ки управлять памятью в прог­раммах на С впол­не воз­можно с помощью сто­рон­них биб­лиотек.

Для при­мера мы возь­мем Boehm GC. Это весь­ма зре­лый и фун­кци­ональ­ный про­дукт, который исполь­зовали или поныне исполь­зуют мно­жес­тво про­ектов: как при­ложе­ний (нап­ример, век­торный гра­фичес­кий редак­тор Inkscape), так и реали­заций язы­ков прог­рамми­рова­ния.

Используем Boehm GC

Мно­гие дис­три­бути­вы Linux пре­дос­тавля­ют пакет с Boehm GC в репози­тори­ях, чаще все­го под име­нем libgc. В Fedora его мож­но пос­тавить коман­дой sudo dnf install libgc-devel, в Debian — sudo apt-get install libgc-dev.

Для демонс­тра­ции мы напишем прог­рамму, которая неп­рерыв­но зап­рашива­ет память под мас­сив из тысячи целых чисел, но никог­да ее не осво­бож­дает. Если бы мы исполь­зовали для выделе­ния памяти клас­сичес­кий malloc(), это была бы хрес­томатий­ная утеч­ка памяти. Но мы обра­тим­ся не нап­рямую к ОС, а к менед­жеру памяти Boehm GC с помощью фун­кции GC_MALLOC() и пос­мотрим, что будет.

Сох­раним сле­дующий код в файл gctest.c.

#include "gc.h"

#include <stdio.h>

int main() {

GC_INIT();

while(1) {

printf("Allocating memoryn");

int *p = (int*)GC_MALLOC(sizeof(int) * 1000);

printf("There are %d free bytes in the heap nown", GC_get_free_bytes());

printf("Making the object unreachablen");

p = NULL;

printf("There are %d free bytes in the heap nown", GC_get_free_bytes());

}

}

Вы­зовом int *p = (int*)GC_MALLOC(sizeof(int) * 1000) мы зап­рашива­ем память на мас­сив из тысячи 32-бит­ных целых чисел (4069 байт) и сох­раня­ем ука­затель на этот учас­ток памяти в перемен­ной p. Далее мы дела­ем эту память недос­тупной, заменив зна­чение p нулевым ука­зате­лем.

Те­перь ском­пилиру­ем его коман­дой gcc -lgc ./gctest.c -o gctest.

В выводе прог­раммы мы будем пери­оди­чес­ки наб­людать сле­дующую кар­тину: объ­ем дос­тупной памяти будет падать спер­ва до 8192 байт, затем до 4096 и, наконец, до нуля. Ког­да он дос­тигнет нуля, сле­дующая попыт­ка выделе­ния памяти скач­ком уве­личит дос­тупный объ­ем.

$ ./gctest

...

There are 4096 free bytes in the heap now

Making the object unreachable

There are 4096 free bytes in the heap now

Allocating memory

There are 0 free bytes in the heap now

Making the object unreachable

There are 0 free bytes in the heap now

Allocating memory

There are 258048 free bytes in the heap now

По умол­чанию Boehm GC выпол­няет сбор­ку мусора толь­ко при острой необ­ходимос­ти — ког­да новую память взять уже нег­де. Если добавить в начало фун­кции main() вызов GC_enable_incremental(), сбор­ка мусора будет про­изво­дить­ся чаще и объ­ем сво­бод­ной памяти не ста­нет падать до нуля.

Во­обще, у Boehm GC мно­жес­тво опций, которые мож­но менять как изнутри прог­раммы, так и извне с помощью перемен­ных окру­жения.

СБОРЩИК МУСОРА — НЕУПРАВЛЯЕМЫЙ ЧЕРНЫЙ ЯЩИК?

Дру­гое рас­простра­нен­ное мне­ние: сбор­ка мусора — это всег­да «магичес­кий», скры­тый от поль­зовате­ля и неуп­равля­емый про­цесс.

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

Ав­торы Boehm GC откры­то приз­нают, что GC_enable_incremental() может ухуд­шить общее вре­мя выпол­нения прог­раммы, но повысить ее отзывчи­вость. Что луч­ше для каж­дой кон­крет­ной прог­раммы, могут решить толь­ко ее автор и поль­зовате­ли.

JVM пре­дос­тавля­ет огромное количес­тво оп­ций для выбора стра­тегии сбор­ки мусора и ее парамет­ров. Glasgow Haskell Compiler тоже содер­жит ряд опций, нес­мотря на репута­цию ака­деми­чес­кого язы­ка.

Не­кото­рые реали­зации язы­ков так­же поз­воля­ют управлять сбор­кой мусора и получать дан­ные об исполь­зовании памяти изнутри прог­раммы: нап­ример, Python, Ruby, OCaml. Авто­ры прог­рамм иног­да пред­почита­ют запус­кать сбор­ку мусора вруч­ную, ког­да свя­зан­ная с этим крат­ковре­мен­ная потеря про­изво­дитель­нос­ти мень­ше все­го замет­на для поль­зовате­ля.

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

ВСЕ РЕАЛИЗАЦИИ СБОРКИ МУСОРА ОДИНАКОВЫ?

Пер­вые реали­зации сбор­ки мусора появи­лись еще в шес­тидеся­тых годах прош­лого века, в интер­пре­тато­рах язы­ка лисп. С тех пор методы поис­ка «мер­твой» памяти и ее осво­бож­дения неп­рерыв­но совер­шенс­тво­вались. Увы, появ­ление новых, более эффектив­ных методов не озна­чает, что их сра­зу нач­нут исполь­зовать во всех язы­ках.

Иног­да реали­зации язы­ков про­дол­жают при­дер­живать­ся ста­рых методов по исто­ричес­ким или прак­тичес­ким при­чинам. К при­меру, Perl исполь­зует самую прос­тую стра­тегию из воз­можных — под­счет ссы­лок.

Подсчет ссылок и его проблемы

Ког­да прог­раммист на Perl пишет $msg = "hello world", интер­пре­татор помеща­ет зна­чение "hello world" в память и сох­раня­ет в $msg ука­затель на него. Если прис­воить его дру­гой перемен­ной ($hello = $msg) или помес­тить в мас­сив (@msgs = ($msg)), счет­чик ссы­лок уве­личи­вает­ся на еди­ницу. Как толь­ко перемен­ные $hello или @msgs вый­дут из области видимос­ти, счет­чик умень­шает­ся. Ког­да счет­чик дос­тигнет нуля, память со стро­кой "hello world" счи­тает­ся недос­тижимой и осво­бож­дает­ся.

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

Ав­торы Perl от­кры­то приз­нают эту проб­лему и совету­ют вруч­ную исполь­зовать сла­бые ссыл­ки (weak references). Почему они не переш­ли на более совер­шенные методы? Perl чаще все­го исполь­зуют для неболь­ших скрип­тов или во вся­ком слу­чае не для прог­рамм со слож­ными алго­рит­мами и струк­турами дан­ных, поэто­му для типич­ного исполь­зования это не соз­дает проб­лем. Одна­ко об этом нуж­но пом­нить, что­бы слу­чай­но не пос­читать Perl хорошо при­год­ным для работы с такими струк­турами дан­ных.

Python так­же исполь­зует под­счет ссы­лок как основной механизм, но, в отли­чие от Perl, содер­жит ал­горитм поис­ка цик­личес­ких ссы­лок. Поиск цик­личес­ких ссы­лок — это более зат­ратная опе­рация, поэто­му он не про­водит­ся на каж­дом цик­ле сбор­ки мусора, но, по край­ней мере, струк­туры дан­ных вро­де двус­вязных спис­ков и цик­личес­ких гра­фов не оста­нут­ся в памяти нав­сегда.

Tracing garbage collectors

Не­кото­рые дума­ют, что все сбор­щики мусора исполь­зуют под­счет ссы­лок, и совер­шенно зря. Мно­гие язы­ки и их ком­пилято­ры исполь­зуют схе­му с отсле­жива­нием (tracing garbage collector). Такие алго­рит­мы начина­ют работу от «заведо­мо дос­тупных» объ­ектов (нап­ример, гло­баль­ных перемен­ных) и отме­чают все объ­екты, на которые те ссы­лают­ся, — для отметки дос­тупнос­ти слу­жат зарезер­вирован­ные биты. Затем объ­екты, которые не помече­ны как исполь­зуемые, осво­бож­дают­ся.

Ал­горит­мы это­го семей­ства объ­еди­няют­ся тер­мином mark-and-sweep. Сре­ди их поль­зовате­лей — JVM, .Net, Go, OCaml и мно­гие дру­гие язы­ки и их биб­лиоте­ки вре­мени выпол­нения.

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

ЗАКЛЮЧЕНИЕ

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

Воз­можно ли авто­мати­чес­кое управле­ние памятью без сбор­ки мусора и свя­зан­ных с ней потерь про­изво­дитель­нос­ти? Да, но об этом — в сле­дующий раз.

Читайте ещё больше платных статей бесплатно: https://t.me/hacker_frei