Rambler's Top100 Service калинин.ru / программирование / c и c++ /  << 18.02.03 >>

Простой, но полезный аллокатор памяти

Лицензии

В этой заметке использованы составные части исходного текста почтовой системы postfix, автором которой является Wietse Venema. Postfix распространяется по лицензии "IBM PUBLIC LICENSE VERSION 1.0 - SECURE MAILER". Исходные тексты в этой заметке предоставлены исключительно в образовательных целях, если вы хотите их использовать как-то иначе, вы должны ознакомиться с этой лицензией. Вы можете ее найти в поставке Postfix'а, файл LICENSE.

Эта заметка --- продолжение "Postfix изнутри" в том смысле, что в качестве примера опять берется postfix. Но если в прошлый раз postfix рассматривался "с высоты птичьего полета", то теперь, наоборот, будет взят небольшой кусочек программного кода, не имеющего никакой специализации, и приведен в качестве примера.

Если у вас есть под рукой дистрибутив postfix'а, то понадобятся файлы src/util/mymalloc.h и src/util/mymalloc.c. Это функции сервисной библиотеки postfix'а для всех модулей, можно сказать "среды программирования" postfix'а. В заголовочном файле определены следующие прототипы:

extern char *mymalloc(int);
extern char *myrealloc(char *, int);
extern void myfree(char *);
extern char *mystrdup(const char *);
extern char *mystrndup(const char *, int len);
extern char *mymemdup(const char *, int);

Вообще, если вы сейчас смотрите внутрь настоящих файлов postfix'а, то обратите внимание на их оформление: начало файла, его окончание. Более подробно эти моменты мы попытаемся обсудить позже, пока что просто отметьте эти подробные комментарии в начале файлов, по которым можно достаточно просто понять смысл того, что находится внутри.

Назначение вышеперечисленных прототипов функций, на мой взгляд, понятно: они дублируют функциональность стандартной библиотеки языка C, конкретно такие вызовы, как malloc, realloc и strdup. Правда в стандартной библиотеке не существует функции с именем memdup, но ее назначение тоже должно быть понятным.

На мой взгляд подобный файл чуть-ли не первый, который должен быть создан (или заимствован из другого проекта) при начале непосредственного программирования на языке C. Точно так же как и реализация этих функций должна быть тоже очень простой: они все сводятся к вызову функций malloc, realloc и т.п. И больше ничего.

Непосредственное использование библиотечных функций связано с тем, что ситуация, когда способ выделения динамической памяти является критичным сразу, очень редка. Обычно важнее сначала получить что-нибудь работоспособное, а уже потом начинать модифицировать различные части программы.

Кроме того, углубившись в дебри оптимизации маленьких, но очень интересных проблем, можно попросту потерять из виду общую задачу. Очень вероятно, что хороший, умный менеджер памяти приведет попросту к бесполезной трате времени и сил программиста. То есть это то, что нужно уметь изменять по потребности, но не делать сразу же. Обычно стандартного менеджера памяти хватает. Кроме того, нестандартный аллокатор обычно требуется не для всех объектов в программе, а только для однотипных, имеющих особые свойства (например: фиксированный размер, частота поиска, частота создания или удаления объектов и т.д.) Для таких объектов можно реализовать свои методы работы с памятью поверх стандартного менеджера памяти.

Тем не менее, использовать подобные обертки очень полезно. Во-первых, если стандартного менеджера памяти все-таки не хватит, то можно перейти на другой. Причем таким менеджером может быть как просто реализация "кучи" иного вида, так и, например, менеджер памяти, выделяющий исключительно разделяемую между процессами памяти (кстати, существует неплохой, по слухам, подобный менеджер памяти основанный на shm_open и mmap).

Во-вторых, даже если стандартного менеджера памяти хватит, вполне вероятно что захочется определять динамику выделения памяти, размеры, утечки, помечать выделенные блоки памяти некоей дополнительной информацией и т.д. Все это можно сделать, в принципе, просто подменив malloc в стандартной библиотеке или воспользовавшись средствами операционной системы, но практически всегда значительно удобнее иметь все под своим контролем.

Оговорюсь сразу: все ситуации выше характерны именно при использовании C, а не C++. В C++ существует оператор new, который можно переопределять как для конкретного типа данных, так и глобально для всей программы. Это значительно удобнее, надо признать, хотя и не всегда помогает: использование STL скрывает от программиста громадное количество деталей, в том числе и используемые менеджеры памяти. Их можно менять, можно писать новые, но это уже требует совсем иного знания STL, чем то, которое обычно имеется у программистов на C++. Вообще, STL является очень характерным примером того, что сложность решения проблемы в общем виде (в данном случае решалась проблема организации структур данных и методов их обработки) достигает сложности самой проблемы. То есть, STL очень полезно при написании небольших программ, но как только требуется что-то необычное, сразу же оказывается что как именно это лучше сделать при помощи STL в общем-то, неизвестно и не всегда очевидно. Это не критика STL, не бессмысленное заявление из разряда "да все там не так" коими кишат т.н. "программистские" форумы (а дизайн STL, на самом деле, лично мне очень нравится), это просто замечание о пагубности общих решений.

В случае с postfix'ом, стандартного менеджера памяти вполне хватает. Это связано с тем, что простая приемка почты (без фильтрации, проверки на вирусы и т.д.) не требует от компьютера больших вычислительных ресурсов, но зависит от скорости жесткого диска: любое письмо, проходящее через MTA должно оказаться в очереди на отправку, то есть на жестком диске. Мало того, MTA должен по возможности гарантировать доставку почты даже в том случае, если компьютер работает нестабильно (допустим, постоянно перезагружается). То есть, MTA должен ответить посылающему релею "220 OK" тогда и только тогда, когда почтовое сообщение прочно легло на жесткий диск. А это значит, что MTA должен выполнять sync на очередь после каждого помещения туда одного сообщения. Следовательно буферизация жесткого диска (кеширование), полезная при обычной работе с компьютером, никак не сказывается на производительность почтовой системы. А вот производительность жесткого диска (конкретно --- количество транзакций в секунду, которые он может выполнить, а не скорость записи как это могло бы показаться на первый взгляд) влияет на производительность почтовой системы непосредственно.

Тем самым, менеджер памяти в postfix'е нужен исключительно для повышенного контроля за доступом к памяти, а не для увеличения производительности. Собственно говоря, так он и реализован.

Давайте теперь перейдем к файлу src/util/mymalloc.c. Основная структура, которая используется аллокатором, называется MBLOCK и выглядит следующим образом:

typedef struct MBLOCK {
    int     signature;			/* set when block is active */
    int     length;			/* user requested length */
    union {
	ALIGN_TYPE align;
	char    payload[1];		/* actually a bunch of bytes */
    } u;
} MBLOCK;

#define SIGNATURE	0xdead
#define FILLER		0xff

Назначение поля length понятно --- это размер выделенного блока. Имеется в виду именно тот размер, который был запрошен при вызове mymalloc, а не тот, который был реально выделен.

Поле signature так же достаточно простое: при выделении нового блока памяти оно заполняется значением константы SIGNATURE, а при освобождении --- каким-то другим. Это позволяет определять такие ошибки, как повторный вызов myfree на тот же указатель или вызов myfree на указатель, который был получен иным способом, чем вызов mymalloc.

Поле u.payload используется для доступа к выделенной памяти. Это общепринятая практика для ситуаций, когда структура данных не имеет фиксированного размера, а зависит от каких-то внешних факторов (обычно сохраняется в этой же структуре, как в length). То есть, структура MBLOCK имеет, конечно же, фиксированный размер (sizeof(MBLOCK)), но так как она выделяется при помощи malloc, то в качестве требуемого размера мы можем указать любой размер, превышающий sizeof(MBLOCK). После этого структура MBLOCK помещается в начале выделенного блока памяти, а доступ к оставшейся памяти может осуществляться как раз через массив u.payload, например как u.payload[100]. Это возможно потому, что, во-первых, в языке C нет встроенной проверки границ массивов и, во-вторых, компиляторы обычно физически располагают поля структур данных в том же порядке, в котором они были перечислены. Последнее замечание нужно осознать: на самом деле, стандартом языка C это не гарантируется и компилятор может перетасовать поля, но есть т.н. "общепринятая практика", которой в данном случае можно следовать.

Поле align имеет тип ALIGN_TYPE, определенный в sys_defs.h (имеется в виду заголовочный файл из библиотеки postfix) и зависящий от архитектуры конкретной ЭВМ. Этот тип используется аллокатором для выравнивания размеров своих структур исходя из особенностей конкретной архитектуры.

Кстати сказать, обратите внимание на обычный для языка C способ определения структур --- через typedef, а не напрямую через struct. Все дело в том, что typedef задает синоним имени (в данном случае MBLOCK), а конструкция вида:

struct MBLOCK {
...
};

задает именно структуру. Разница в этих понятиях заключается в том, как эти имена могут быть использованы: синоним имени используется напрямую (MBLOCK), а структура --- только как структура (т.е., struct MBLOCK). То есть в последнем случае (без typedef) следующий код будет некорректен:

MBLOCK block1, block2;
MBLOCK *pblock;

А корректным будет немного другой код:

struct MBLOCK block1, block2;
struct MBLOCK *pblock;

В C++ это поведение было изменено.

Но вернемся к аллокатору. Вопрос, который должен был бы задать себе читатель этой заметки, должен быть примерно следующего вида: "Ну хорошо, структура MBLOCK понятна. Но mymalloc возвращает void*, а не MBLOCK и myfree получает в качестве аргумента void*. Тогда, если mymalloc может вернуть адрес u.payload, то каким образом myfree по этому указателю сможет восстановить указатель на структуру MBLOCK, соответствующую u.payload?"

Ответ на этот вопрос "в первом приближении", конечно же, достаточно очевиден --- так как u.payload входит в состав структуры MBLOCK, то по смещению u.payload внутри MBLOCK, мы запросто можем вернуться к указателю на MBLOCK путем вычитания этого смещения из указателя на u.payload.

Но вот что неочевидно, так это каким образом можно получить данное смещение --- сумма sizeof всех полей структуры до payload вполне вероятно будет меньше реального смещения. Можно вычислить смещение исходя из познаний о собственном компиляторе и его выравнивании, но postfix, напомню, собирается на большом количестве архитектур, а такое смещение совершенно непереносимо.

На самом деле, я просто пытаюсь объяснить проблему. Существует еще один оператор языка C (или, точнее сказать, макрос стандартной библиотеки), который, как это ни странно, часто неизвестен даже опытным программистам. Это оператор offsetof, который как раз и позволяет получить смещение поля в структуре: именно на его основе myfree получает искомое смещение. Для демонстрации его работы процитируем следующий макрос, используемый для этой операции в myfree и myrealloc:

#define CHECK_IN_PTR(ptr, real_ptr, len, fname) { \
    if (ptr == 0) \
	msg_panic("%s: null pointer input", fname); \
    real_ptr = (MBLOCK *) (ptr - offsetof(MBLOCK, u.payload[0])); \
    if (real_ptr->signature != SIGNATURE) \
	msg_panic("%s: corrupt or unallocated memory block", fname); \
    real_ptr->signature = 0; \
    if ((len = real_ptr->length) < 1) \
	msg_panic("%s: corrupt memory block length", fname); \
}

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

if( ... ) CHECK_IN_PTR(...) ; 
else  ... ;

Это связано с тем, что после применения макроса код выше превратится в такой:

if( ... ) { } ; 
else  ... ;

А подобный код содержит в себе синтаксическую ошибку (точка с запятой после закрывающей фигурной скобки является концом оператора if, а за ним следует else). То есть, надо или убрать точку с запятой после CHECK_IN_PTR (а это значит, что макрос будет отличаться от операторов, потому что после, например, какого-нибудь i++ точка с запятой будет обязательна), или выполнить макрос немного по другому. Достаточно вместо фигурных скобках использовать следующее:

#define CHECK_IN_PTR(ptr, real_ptr, len, fname) do { \
... \
} while(0)

Тогда do { } while(0) будет как раз оператором и использование CHECK_IN_PTR не будет отличаться от обычных операторов.

Тем не менее, макрос CHECK_IN_PTR используется только в mymalloc.c (то есть, контроллируемо) и при этом нет ни одного условного оператора с его участием. Поэтому задумываться о преимуществах do { ... } while(0) перед простым { ... }, было совершенно необязательно. Я же указал на это только из желания попридираться в учебных, так сказать, целях.

Если придираться дальше, то можно обратить внимание на то, что все параметры макроса используются "как есть", без заключения в скобки. Для макроса, который находился бы в общей библиотеке, это очень плохо: неизвестно что и когда туда будет передано, а потом придется разбираться с совершенно непонятными ошибками. Но этот макрос, повторю, используется только в одном файле в известном окружении. Можно было бы вообще сделать его без параметров, опираясь на одинаковые названия переменных в функциях, где он используется и это тоже было бы совершенно нормально.

Использование offsetof, я думаю, очевидно из его употребления в макросе CHECK_IN_PTR: первый аргумент --- структура, второй --- поле, смещение которого нас интересует.

И напоследок, я хотел бы обратить внимание на константу FILLER: она используется для заполнения выделенных блоков памяти. Она не равна 0, хотя, казалось бы, 0 был бы значительно удобнее. Это связано с тем, что нулевые значения чего бы то ни было обычно имеют осмысленные значения и тогда если объект забыть инициализировать (а это, повторю, не C++, где ошибки связанные с инициализацией в большинстве своем решены наличием конструкторов), то им все равно можно будет пользоваться. А вот ненулевые значения приведут, скорее всего, к аварийному завершению программы и следовательно подобные ошибки будут найдены быстрее.

На этом рассматривать аллокатор postfix стоит закончить --- все оставшееся, по-моему, предельно понятно из самого кода.

Резюме

Описанный аллокатор postfix'а обладает следующими преимуществами:

  • Контроль за памятью (размеры, повторное удаление и т.д.)
  • Простота реализации: mymalloc.c содержит всего 200 строчек, при этом порядка 100 строк --- комментарии.
  • Переносимость.
  • Инициализация памяти.

Версия для печати


  Ссылки по теме:
http://www.postfix.org
   Официальный сайт почтовой системы Postfix, оттуда его можно скачать.
  Рядом в разделе:
C или C++? (09.07.01)
   Существуют два диаметрально противоположенных, но одинаково распространенных мнения, которые можно выразить как "C++ это C с классами" и "C++ и C...   >>>>
Религия и goto (14.04.01)
   Начнем несколько издалека. В программировании существует тенденция к алгоритмизации самого процесса программирования. То есть, выведение некоторых универсальных правил, использование которых в...   >>>>
  Рядом по дате:
Спамеры и антиспамеры: путь к компромиссу (14.08.03)
   Статья написана для электронного журнала . На данный момент в околокомпьютерной прессе опубликовано достаточно большое количество статей на тему спама. Большая...   >>>>
Postfix изнутри (08.02.03)
   Эта заметка пишется после громадного перерыва и поэтому, наверняка, будет отличаться от всего остального. Что же, год назад я закончил нравоучениями...   >>>>
  Содержание:
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
   C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Просто так
Студенческое
Туризм
  Байки
Фотографии
Комментарии
   Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Благодарности
Форум
Хронология
 
  В этом разделе:
Простой, но полезный аллокатор памяти (18.02.03)
   Эта заметка --- продолжение "Postfix изнутри" в том смысле, что в качестве примера опять берется postfix. Но если в прошлый раз...   >>>>
C или C++? (09.07.01)
   Существуют два диаметрально противоположенных, но одинаково распространенных мнения, которые можно выразить как "C++ это C с классами" и "C++ и C...   >>>>
Религия и goto (14.04.01)
   Начнем несколько издалека. В программировании существует тенденция к алгоритмизации самого процесса программирования. То есть, выведение некоторых универсальных правил, использование которых в...   >>>>
ploticus (16.10.00)
   Есть такая программа, предназначенная для создания графиков различных видов из командной строки, называется ploticus. Программа сама по себе достаточно удобная ---...   >>>>
Шаманство, или ошибки работы с памятью (25.09.00)
   Когда программа становится внушительной по своему содержанию (то есть, не по количеству строчек, а по непонятности внутренних связей), то ее поведение...   >>>>
Библиотека консорциума W3, libwww (20.09.00)
   Популярный нынче термин "веб-программирование" обычно подразумевает под собой программирование, в лучшем случае, на perl, в худшем --- на PHP, в совсем...   >>>>
Инварианты внутри программы (18.09.00)
   Вы когда-нибудь задумывались, над тем, как вы пишите программы? Если нет, то, я думаю, сегодняшняя заметка будет вам полезна. Итак, как...   >>>>
Содержание раздела полностью...
   Примерно в тоже время
Спамеры и антиспамеры: путь к компромиссу (14.08.03)
   Статья написана для электронного журнала . На данный момент в околокомпьютерной прессе опубликовано достаточно большое количество статей на тему спама. Большая...   >>>>
Postfix изнутри (08.02.03)
   Эта заметка пишется после громадного перерыва и поэтому, наверняка, будет отличаться от всего остального. Что же, год назад я закончил нравоучениями...   >>>>
Хронология полностью...
   Содержание
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
  C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Туризм
  Байки
Фотографии
Комментарии
  Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Студенческое
Просто так
Благодарности
Форум
Хронология
© 2000-2008, Andrey L. Kalinin
mailto:andrey@kalinin.ru
Rambler's Top100