Comments 31
Добавлю еще, что современные аллокаторы пришлось научить в дополнению ко всему остальному еще и предотвращению эксплуатации типичных для небезопасных ЯП проблем вроде double free, use-after-free и т.п., вот прекрасная статья Саара Амара о нынешнем состоянии memory safety.
Не нужно никого там учить. Необходимость возникает на уровне системного аллокатора памяти и не из-за "небезопасных" языков, а потому что если ты хранишь данные в выделенном юзеру, то юзер может что-то поменять, а система не имеет права надеятся на "хорошего" юзера и должна иметь защиту от вредоносных действий
Одно другому не мешает, если система защищает с помощью сегфолта, то предварительная защита в аллокаторе уровня приложения вернет ошибку без обращения к системному аллокатору и работа приложения не прервется.
и что же вы будете делать с ошибкой double free? Как собираетесь её обрабатывать? И кто так и где делает?
Потому, что им может пользоваться человек, который вообще ни сном ни духом об этом. Вот, представьте, что вы — секретарша, работающая в MS Word, который внутри себя сделал double free...
Ну я ниже привёл вариант, когда ничего не произойдёт. В общем, тут надо как-то очень аккуратно соображать, я бы предпочёл, чтобы программе был выслан сигнал аля SIGSEGV, после которого она постаралась бы сохранить всё, что можно, а потом перезапустилась бы и восстановила состояние.
Короче, убивание по любому чиху в некоторых случаях — "да, да, да" (особенно при отладке), а в некоторых и "нет, не надо". Вот представьте себе вариант какого-нибудь прохождения глючной игры: там уж лучше бы, чтобы она хоть иногда пропустила на след. уровень, чем 146% вылетала. Ситуации бывают разные.
То есть, у меня есть доводы и за, и против продолжения. С одной стороны, программа в некорректном состоянии. С другой стороны, может это состояние и не настолько уж некорректное, чтобы не дать пользователю сохранить данные. В конце-концов, если в коде действительно написано free(p) подряд 144 раза, то эта ошибка легко чинится без последствий, и смысла вырубать всё, выбрасывая на помойку пользовательские данные, нет.
Это приложение может оказаться прошивкой, управляющей, например, самолётом. Вы уверены, что предпочли бы в этом случае именно завершение приложения? Да, конечно, в таких случаях требования к коду обычно жёстче, а динамическую память часто и вовсе использовать запрещено. Но по факту она используется, пусть даже и не в самом прикладном коде, но в библиотеках, которые им используются, и в операционной системе. А ошибки в них тоже есть.
Из моей практики. Watchdog, конечно, есть. И вычислители дублируются физически. Но время перезагрузки программы по нормативу - 30 сек. Мы укладываемся, но запас остаётся не большой. Если вычислитель не будет функционировать даже 20 секунд, это, вообще говоря, очень плохо, слишком много всего может случиться. Поэтому, если можно не падать, предпочитаем не падать. Естественно, все ошибки и потенциальные неисправности при этом логгируются, куда нужно отправляются, и ведётся сбор статистики. При достижении определённых условий может приниматься решение, что данному вычислителю доверять нельзя, и управление перейдёт резервному. Но это будет именно процедура, а не просто перезагрузка вычислителя в рандомный момент времени.
программа, в которой что-то дважды очистилось будет выдавать плохие данные
Как раз тогда, когда двойное освобождение/закрытие ресурса реализовано так, что ничего не портит (повторная операция игнорируется), плохих данных скорее всего не будет. Я это имел в виду.
Если у вас такие жесткие требования, то на кой черт вы вообще используете кучу?
Мы не используем кучу в своём прикладном коде.
Если у вас неизвестен размер данных и позарез нужна куча - то делается свой аллокатор
Да, у нас есть свой аллокатор (блоков фиксированных размеров), для аллокации из своих же статичных пулов.
Если у вас образовался потенциальный намек на то, что у вас double free, use after free или банальное деление на ноль - это сигнал, что программой дальше пользоваться нельзя.
Всё так. Такое отлавливается при тестировании, если косяк именно в нашем коде. Но он не всегда именно там.
Как я уже говорил, кучу использует ось, используют либы. И если либы мы можем переписать, избавившись от использования динамической памяти (делаем по мере сил, но это не единомоментно, на это нужно время), с осью всё сильно сложнее (и ей же обычно больше доверяешь, сертификаты, все дела).
Могу привести пару конкретных примеров из жизни, почему внезапно падала программа, и как мы это исправляли.
Комплекс исправно работал на самолёте, но в какой-то момент появилась информация, что вычислители стали перезагружаться в процессе работы. Логи показали, что в какой-то момент ОСь не может выделить ресурс (создать семафор).
Оказалось, перед этим пилоты обновили полётную базу (xml- файл). И в этот раз база стала сильно больше размером. Соответственно, парсер XML (это был MiniXML) выделил в этот раз сильно больше памяти чем ранее. ПО кучу не использует, но остатка свободного места не хватило оси под свои объекты, в реалтайме.
Решение - сначала доработали MiniXML, чтобы аллоцировал из отдельного пула, не трогая системный. А потом написали свой парсер, который динамическую память не использует вовсе (а код оказался на порядок проще и быстрее, что очень кстати, т.к. MiniXML был крайне тормозной и сильно увеличивал время загрузки).
Аналогично, стала кончаться куча. Поймать утечку долго не удавалось. Оказалось, косяк был в самой ОС (в её штатной библиотеке поддержки SPE для PowerPC). Потокам, которые работают с floating-point, вешаются хуки на события переключения потоков, которые должны записывать и восстанавливать состояние FP-регистров. Для этого, при создании потока, система выделяет структуру. А вот на завершение потока хук просто не вешался, и, в итоге, структура оставалась не освобождённой. Оказалось, что временные сервисные потоки (создаваемые самой осью) забирали себе весь системный пул.
До сих пор не понимаю, как производители ОС такой косяк могли пропустить. Могу только предполагать, что аппаратную плавающую точку на SPE прочие заказчики не использовали, довольствуясь soft-fp, и мы просто оказались первыми.
Для расширения доступного пространства данных в C были введены (ныне изрядно устаревшие) системные функции brk & sbrk,
Не понятно, в каком смысле вы их считаете их устаревшими. В GNU libc это всё ещё самый распространенный способ выделения памяти.
sbrk and brk were considered legacy even by 1997 standards (Single UNIX Specification v2 or POSIX.1-1998).They were removed in POSIX.1-2001 (отсюда)
Спасибо, очень познавательная штука. У меня как-то не доходили руки до того, чтобы наконец-то разобраться и понять, где же в malloc'е эта самая куча. То есть, было примерно понятно, как его его в простейшем случае реализовать, но хотелось проверить свои мысли.
По-моему по аллокаторам можно написать цикл книг, и ещё останется. Всякие jemalloc, tcmalloc, slab allocator, потом bohem, потом дело доходит до джавы и начинается второй том...
Получается, что алгоритм близнецов не обладает никакими недостатками кроме большего потребления памяти (почему-то мне кажется, что где-то в sqrt(2) больше)? И вся возня с другими - это попытки убрать этот оверхед?
Но ведь проще потратить немного денег на увеличение памяти на сервере, чем полжизни на борьбу с аллокаторами?
У меня специфичные сетевые приложения, и я несколько лет назад написал аллокатор по степеням двойки, подсовываю его под внешние библиотеки, которые хотят выделять память постоянно - работает быстро и без фрагментации. Делаю это щедро - независимым для каждого потока, там размер аллоцированного всё равно небольшой.
В остальных местах (в своём коде) использую принцип избегания аллокаций - в каждом узле программы аллоцирована и не отпускается память, которая соответствует максимально потребовавшейся в этом узле исторически (можно и с запасом 1.5-2x). При таком подходе можно использовать любой аллокатор - системный, например, и не экспериментировать с альтернативами (промежуток времени между аллокациями затухает экспоненциально, очень быстро), а можно даже и стековый аллокатор использовать (который всегда отдаёт новую память, а при освобождении ничего не делает).
Близнецы и работают помедленней (в сравнении с граничными дескрипторами) плюс дополнительную память просят под маски занятости. Поэтому близнецами выделяют до какого-то предела (пусть килобайт), а всё что меньше, агрегируют в килобайтных блоках.
С точки зрения многопоточности дескрипторам опять же попроще жить.
Не очень понятно почему помедленней. У дескрипторов - всегда нужно смотреть/менять дескрипторы двух соседних блоков и сходу непонятен алгоритм поиска нужного куска при аллокации. Да и внешняя фрагментация как бы напрашивается всё равно. В близнецах делается всё константно, нет никаких масок занятости: свободные блоки одинакового размера в однонаправленном интрузивном списке (lifo для использования кешей). Однонаправленный список не позволяет сливать соседей, но это, имхо, и не обязательно (опять же оверхед в некоторых сценариях, но мне ок).
а как насчет защиты от недобросовестного пользователя?
double free того же ?
Вот, кстати, поэтому недо-buddy аллокатор в BSD 4.2 и работал так быстро, что не пытался слить соседей во время free. В самом деле, как узнать без дополнительной памяти, что твой сосед тоже свободен? Пробежать по списку?
Я в начало блока записываю степень двойки, обозначающую его размер (когда он выделен). Когда свободен - можно 0 писать, например. А уже дальше интрузивный указатель для списка. Вобщем, можно как-то выкрутиться, тем более 1 бит нужен всего для обозначения свободности - его и в указатель можно вставить, в младший бит.
Т.е. дополнительная память в виде заголовка блока.
То же самое но чуть компактнее можно сделать масками.
Плюс бонус - защита от double free/невыделенная память.
Я примерно понял что такое маски - это массивы битов про каждый блок. Но в моей имплементации только блок знает свой размер (либо в заголовке, если выделен, либо косвенно - через список свободных, в котором находится), он же может побиться в любой момент на два.
У меня требования к аллокатору такие:
Скорость (достигается за счёт: универсальности - нет лишних сравнений, константной сложности операций, lifo, локальности - служебная информация в начале блока, там же где пользователь данные размещает)
Универсальность - один аллокатор для любого размера блока (у меня до 2^28, выше - выделяется уже внешним аллокатором)
Память: оверхед до 2x не страшен, очень важно чтобы не было постоянной внешней фрагментации (которая выглядит как утечка и требует рестарта сервера периодически).
Защита от дурака не нужна
Я сейчас осознал, что счастливый человек, что могу позволить такие требования себе. Аллокаторы (и сборщики мусора) - это неисчерпаемая головная боль. Особенно, когда не можешь позволить себе просто удвоить требования к памяти или отадаёшь аллокатор любителям, которые могут двойным free всё сломать.
На всякий случай, я уже как-то выкладывал
исходники BuddyAllocator под BSD лицензией
В старой FreeBSD был любопытный аллокатор, где в мане malloc(3) было написано:
The present allocation implementation started out as a file system for a drum attached to a 20bit binary challenged computer which was built with discrete germanium transistors. It has since graduated to handle primary storage rather than secondary. It first appeared in its new shape and ability in FreeBSD 2.2.
Здорово! в принципе, до всех основных принципов построения аллокаторов, я догадался самостоятельно, сключая распределение фибонначи, показательный ряд с основанием два и метод близнецов. Особенность в том, что они были разработаны на древнейшем оборудовании, и никак не отражают современное состояние аппаратного обеспечения. А вот термин heap, по-моему связан с реализацией в виде кучи и табицы.
а вот посмотреть на то, как работает аллокатор С в одной из реализаций простых списков, можно тут
Древнее оборудование? Метод близнецов - это же, по моему, buddy-allocator, который используется во всех операционных системах для выделения памяти. За счет скорости, простоты и неподверженности фрагментации, он идеально подходил для ядра ОС, где все страницы по замеру равны степени двойки. Он используется в ядре Linux, Windows, RTOS. Да и во многих современных Си-шных быстрых аллокатарах он используется как нижележащий слой, под аренами и прочими структурами. Так что, списывать его со счетов я бы не стал.
Происхождение и эволюция аллокатора памяти в С