Как видно, по сравнению с привычными malloc()/free() в прикладных приложениях, здесь указывается еще один аргумент: тип malloc, определяемый где-нибудь в начале макросом MALLOC_DEFINE(); а для самого malloc() еще и флаги. Что это за тип? Он предназначен для ведения статистики. Аллокатор отслеживает, сколько для каждого типа сейчас выделено объектов, байт, и каких размеров блоков. Системный администратор может запустить команду vmstat -m и увидеть такую информацию:

Например:

Здесь нужно отметить, что округления блоков идут до 2^n только размера страницы, дальше идет округление до целого числа страниц. То есть на запрос в 10 Кб будет выделено 12 Кб, а не 16.

Остается рассмотреть только флаги вызова malloc(). M_ZERO понятен из названия — выделяемая память будет сразу заполнена нулями. Более важны два других взаимоисключающих флага, один из которых обязательно должен быть указан:

Следует обратить внимание, что эта паника, как правило, возникает не в той подсистеме, которая всю память сожрала. Типичный пример из жизни: небольшой роутер падает в такую панику в UFS с запросом в 16384 байта — это какой-то процесс хочет прочитать что-то с диска, и для блока с диска вызывается malloc(16384, ..., M_WAITOK) — памяти в kmem больше нет, всё, сохраняется корка. После ребута делаем vmstat -m -M /var/crash/vmcore.1 и видим, что всю память сожрал NAT на базе libalias — просто он с M_NOWAIT обламывался в получении еще памяти, а система пока жила.

Еще в конце 80-х начались исследования специальных аллокаторов, предназначенных для отдельных подсистем. Они показывали результаты лучше общего аллокатора, но страдали от указанных в начале этого раздела недостатков — плохое взаимодействие с другими подсистемами. Самый важный полученный в ислледованиях вывод: «...a customized segregated-storage allocator — one that has a priori knowledge of the most common allocation sizes — is usually optimal in both space and time».

И вот в 1994 году, опираясь на этот вывод, Jeff Bonwick из Sun Microsystems придумал (и реализовал в Solaris) так называемый Slab Allocator (название отсылает к плитке шоколада, которая делится на дольки). Суть идеи: каждая подсистема, которая использует много объектов одинакового типа (а значит, одинакового размера), вместо заведения своих собственных кэшей регистрируется в slab-аллокаторе. А тот сам управляет размером кэшей, исходя из общего количества свободной памяти. Почему кэшей? Потому что аллокатор при регистрации принимает функции конструктора и деструктора объекта, и возвращает при аллокации уже инициализированный объект. Он может инициализировать некоторое их количество заранее, да и при free() объект может быть лишь частично деинициализирован, просто возвращаясь в кэш и будучи немедленно готовым к следующей аллокации.

"Плитка", которая обычно составляет страницу виртуальной памяти, разбивается на объекты, которые плотно упакованы. Например, если размер объекта 72 байта, их помещается 58 штук на одной странице, и неиспользованным остается лишь "хвост" в 64 байта — впустую тратится всего лишь 1.5% объема. Обычно в этом хвосте находится заголовок slab с битовой картой, какие из объектов свободны, какие выделены:

Реализация slab во FreeBSD называется UMA (Universal Memory Allocator) и документирован в zone(9). Потребитель вызывает uma_zcreate() для создания зоны — коллекции объектов одинакового типа/размера, из которой и будут происходить выделения (она и является кэшом). С точки зрения системного администратора наиболее важным является то, что для зоны может быть установлен лимит с помощью uma_zone_set_max(). Зона не вырастет больше лимита, и если аллокация выполнялась с помощью M_WAITOK в syscall для пользовательского процесса, то он повиснет в top в состоянии keglim (в предыдущих версиях оно называлось zoneli) — до тех пор, пока не появится свободных элементов.

Текущее состояние UMA системный администратор может посмотреть в vmstat -z:

Значение полей:•ITEM — указывает название зоны

Как заметили об универсальности разработчики Facebook: «If it isn't general purpose, it isn't good enough». Мы во FreeBSD любим разрабатывать универсальные вещи — GEOM, netgraph и много чего еще... И именно новый универсальный аллокатор для пользовательских приложений jemalloc и был взят разработчиками Facebook и Firefox 3. Подробнее о том, как сейчас обстоят дела на фронте масштабируемых аллокаторов, можно прочитать в их заметке http://www.facebook.com/note.php?note_id=480222803919 

В примере можно заметить, почему UMA называется universal — потому что использует свои зоны даже для своих же собственных структур, а кроме того, malloc() сейчас реализован поверх того же UMA — имена зон от "16" до "4096". Дотошный читатель, однако, обратит внимание, что здесь размеры блоков только по 4096 включительно, а выделять-то можно и больше — и будет прав. Объекты большего размера выделяются внутренней функцией uma_large_malloc() — и, к сожалению, в общей статистике зон они не учитываются. Можно обнаружить, что результат vmstat -m | sed -E 's/.* ([0-9]+)K.*/\1/g' | awk '{s+=$1}END{print s}' не совпадает с vmstat -z | awk -F'[:,]' '/^[0-9]+:/ {s += $2*($4+$5)} END {print s}' именно по этой причине. Впрочем, даже если просуммировать vmstat -m и всех остальных зон, всё равно это будет неточное значение размера kmem из-за выравниваний на кратное число страниц, потерь в UMA на хвосты страниц, и т.д. Поэтому на живой системе удобнее пользоваться sysctl vm.kmem_map_size vm.kmem_map_free, оставив упражнения с awk для посмертного анализа корок.

Кстати, возвращаясь к примеру с паниковавшим маленьким роутером: если бы в ядерном libalias вызывался не malloc(), а uma_zalloc() (принимает 2 аргумента — зону и те же флаги M_NOWAIT/M_WAITOK), то, во-первых, размер элемента не округлялся бы до 128 байт, и в ту же память влезало бы большее количество трансляций. Во-вторых, можно было бы выставить лимит этой зоне и избежать бесконтрольного захвата памяти libalias'ом вообще.

Подробнее о slab-аллокаторах можно прочитать в публикации "The Slab Allocator: An Object-Caching Kernel Memory Allocator", Jeff Bonwick, Sun Microsystems (в сети доступна в PDF), и в man uma (он же man zone).

Рис. 1. Структура mbuf (размер посчитан для 32-битных архитектур)

Итак, было описано, что фрагментация памяти плохо влияет на производительность аллокатора, что с этим можно бороться либо ценой потерь памяти из-за округления размера вверх, либо с использованием slab-аллокаторов, когда имеется множество объектов одного типа/размера. А теперь посмотрим, что же происходит в сетевой подсистеме? Мало того, что прибывающие пакеты очень сильно варьируются в размерах, есть куда более серьезная проблема: в течение жизни пакета его размер изменяется — добавляются и удаляются заголовки, бывает необходимо разбиение пользовательских данных на сегменты, сбор их обратно при чтении в большой буфер пользовательского процесса, и т.п.

Для решения всех этих имеющихся тогда, в 80-е годы, проблем разом, в BSD было введен концепт mbuf (memory buffer) — структуры данных небольшого фиксированного размера. Эти буферы объединялись в связные списки, и данные пакета, таким образом, оказывались размазаны по цепочке из нескольких mbuf. Поскольку размер фиксирован, нет проблем с аллокатором, являвшимся надстройкой над стандартным (в наше время, понятное дело, их выделяет UMA). Поскольку это связный список, добавить ему в голову еще один mbuf с заголовком более низкого уровня (IP или L2) не составляет проблем.

Физически mbuf, как видно из рисунка 1, представляет из себя буфер определенного размера, в начале которого имеется фиксированный заголовок. Поля (не менялись уже многие годы) служат для связи нескольких mbuf в списках, указывают тип содержимого, флаги, фактическую длину содержащихся данных и указатель на их начало. Понятное дело, что, например, для "отрезания" IP-заголовка можно просто увеличить указатель начала данных на 20 байт, а длину содержимого уменьшить на 20 байт — тогда данные в начале буфера станут как бы свободными, без всякого перемещения байтов пакета в памяти (это сравнительно затратная операция). А для удаления данных из конца вообще достаточно только уменьшить длину, не трогая указатель.

Исторически, размер одного mbuf составлял 128 байт, включая этот фиксированный заголовок. Применялся он в сетевой подсистеме практически для всего — адреса, пути, записи таблицы маршрутизации... Потому и название универсальное, а не только про пакеты. Потом все эти усложнения кода "всё-в-одном" повычистили, и из имеющихся типов осталось только относящееся к сокетам (помимо собственно данных пакетов это, например, OOB data или ancillary data в struct cmsghdr). Кроме того, за годы постепенно добавляются новые поля в переменной части mbuf, и поэтому с FreeBSD 4 размер mbuf (константа MSIZE в param.h) составляет уже 256 байт.

Рис. 2. Очередь из двух mbuf chain по 2 mbuf каждая, в первой состояние после m_prepend()/MH_ALIGN

Как показано на рисунке 2, mbuf связываются в цепочки (mbuf chain) с использованием поля m_next. Все связанные таким образом mbuf обрабатываются как единый объект — то есть единый пакет данных. Многие функции обработки mbuf оперируют именно всей цепочкой. Далее, несколько независимых пакетов связываются между собой с помощью поля m_nextpkt (имеет смысл, понятное дело, только в головном mbuf пакета). В документации нередко один пакет (цепочку по m_next) называют chain, а связь нескольких mbuf chain по m_nextpkt называют queue, очередь — потому что таким образом они помещаются в исходящую очередь интерфейса, во входную очередь обработки, входящий или исходящий буфер сокета тоже есть очередь, и т.д.

Пакет обычно размещается в mbuf chain так, что первый mbuf имеет установленный флаг M_PKTHDR, отмечающий наличие в нем дополнительной структуры m_pkthdr. Она не является частью самого пакета, но описывает его для системы. Вот её основные поля:

Кроме них, время от времени в pkthdr разрешается включать и другие поля, если они малы по размеру, и при этом важны для быстродействия, например, номер VLAN-тега в ether_vtag, или информацию для TCP segmentation offloading, и т.д. Ведь, как можно видеть из рисунка, включение pkthdr в головном mbuf цепочки — уменьшает в нём доступное для данных место.

Внимательный читатель на этом месте уже подсчитал, что для хранения полноразмерного Ethernet-пакета потребуется целых 7 mbuf, а при старых размерах в первоначальной реализации — и вообще 15. Жить с этим можно, но не слишком ли это неудобно и медленно, когда основная часть пакета всё-таки распиливания не требует? Это поняли еще в 80-е годы, и первоначальная реализация mbuf была изменена для поддержки хранения больших объемов данных вне mbuf (и, например, поле смещения, говорившее, где начинаются данные, было изменено на указатель m_data, который может показывать в нужное место). Была предусмотрена возможность использования различных типов внешних хранилищ, поэтому флаг M_EXT стал не просто говорить о наличии внешнего хранилища, а обозначать наличие в mbuf еще одного заголовка — struct m_ext. При этом теряется возможность использовать для хранения данных внутреннее пространство (m_dat) в самом mbuf, однако приобретается возможность использования одной и той же копии данных внешнего буфера во многих mbuf — при этом просто увеличивается счетчик ссылок (на него указывает поле ref_cnt) этого внешнего буфера. Другие поля struct m_ext указывают размер, тип внешнего хранилища, и данные для той подсистемы, которая этот тип обрабатывает.

Рис. 3. Поля mbuf (для FreeBSD 7.4/i386) при установленных флагах M_PKTHDR (слева) и M_EXT (справа)

Для ряда типов внешних буферов администратору доступны настройки, задающие их количество:

Хотя расширяемость (поддержка более одного типа) была сделана сразу, долгое время единственным типом внешних данных был так называемый mbuf cluster — область данных размером MCLBYTES (см. param.h), обычно это ровно половина страницы, 2048 байт. Система предпочитает помещать данные в кластер, если запрашиваемый размер превышает половину доступного размера в головном mbuf (т.е. 100 байт для версии 7.4/i386, показанной на рисунках).

Максимальное число этих кластеров в системе и задается широко известным sysctl kern.ipc.nmbclusters. При этом при общих расчетах памяти следует помнить, что на каждый кластер всегда приходится еще и как минимум один ссылающийся на него просто mbuf. Здесь же объяснение, почему на машину, где исчерпались mbuf clusters, невозможно даже зайти по ssh — ведь они используются для любых операций с сетью (хотя можно, конечно, попробовать отправлять очень мелкие пакеты).

Стандартный mbuf cluster остается типом по умолчанию и сейчас, но появились и другие. Прежде всего, конечно, это буфера sendfile(2), регулируемые sysctl kern.ipc.nsfbufs (если это число равно нулю, для этой архитектуры настройка не требуется). Их тюнинг актуален для тех, кто держит нагруженные сервера с раздачей статики, например с nginx или каким-нибудь ftpd, умеющим sendfile() (например, штатным ftpd из базовой системы FreeBSD).

Кроме того, начиная с FreeBSD 6.3 доступны другие типы кластеров, предназначенные для поддержки jumbo frames размером 9 Кб и 16 Кб, а также специальный тип кластера размером с одну страницу (4 Кб). Последний нужен для экономии памяти (не выделять слишком большие буфера, если не нужно) в локальном IPC (127.0.0.1) и не очень больших пакетах при больших MTU (линки с jumbo frames).

Наиболее часто встречающиеся очереди mbuf, с которыми приходится иметь дело администратору — это буфера сокетов приложений. Буфер сокета — это просто небольшая структура, имеющая несколько управляющих переменных, типа своего размера, и собственно указатель на очередь mbuf. Буферов у каждого сокета два штуки, на прием (recv) и передачу (send). Операции в ядре по выставлению размера буферов выполняются функцией sbreserve() (программисты, в норме следует использовать не её, а soreserve(), ставящую watermark'и для обоих сразу). Создавалась и используется она в предположении, что под сокет реально резервируется какое-то место, никому больше недоступное, но на самом деле она только лишь проверяет лимиты — то есть неиспользованное до лимита в сокете место доступно другим приложениям. В противном случае, ядерной памяти бы просто не хватило при большом числе сокетов в системе.

Проверяемых лимитов на размер буфера сокета всего два. Это глобальный sysctl kern.ipc.maxsockbuf (не может быть уменьшен ниже размера одного mbuf + кластера, т.е. MSIZE + MCLBYTES = 2304 байт) и соответствующий лимит ресурсов пользователя (см. ulimit). Применяются они, однако, не так просто, как может показаться на первый взгляд. Дело в том, что цифру лимита можно трактовать двояко — как реальное число помещающихся в буфер байт (это интересует автора приложения) и как размер выделенных системой ресурсов (это интересует администратора). Какой вариант используется? Оба. Прежде всего, будет отказано в выделении размера, превышающего kern.ipc.maxsockbuf * MCLBYTES / (MSIZE + MCLBYTES) — как видно, здесь учтены неиспользуемые mbuf, когда данные лежат в кластерах. Затем, если пройдена проверка на лимит ресурсов пользователя, в переменную sb_hiwat заносится запрошенное количество байт, но в sb_mbmax пишется значение, вычисляемое по такой формуле:

Таким образом, поскольку с sb_mbmax сравнивается полный размер всех mbuf и кластеров, включая накладные расходы на внутренние заголовки и теряемые области, то реальных ресурсов не будет выделено больше лимита. [На самом деле, всё несколько сложнее, бывают readonly mbuf (когда одна физическая копия данных принадлежит нескольким буферам), и, например, sbspace()может вернуть отрицательное значение. Но эти темы выходят за объем поста.]

Состояние sk_buff в Linux после:

1) skb_reserve()

2) skb_put()

3) skb_push()

По теме буферов осталось заметить только разницу между несколькими переменными, кочующими по хаутушкам о тюнинге. Есть kern.ipc.maxsockbuf, задающий глобальный лимит, а есть переменные recvspace и sendspace у каждого протокола (например, net.inet.tcp.sendspace). Эти переменные — всего лишь значение по умолчанию, используемое при создании сокета. Приложение с помощью вызова setsockopt() легко может перекрыть эти значения своими, в пределах лимитов (впрочем, программистам следует помнить, что нет смысла ставить буфер меньше, чем MSIZE + MCLBYTES).

Прежде, чем переходить к теме интерфейсов программиста к mbuf, окинем еще раз взглядом их архитектуру, рассмотрим достоинства и недостатки. Здесь полезно сравнить их с аналогом в Linux, структурой sk_buff, которая представляет собой один непрерывный кусок памяти заранее выделенного максимального размера. Некий размер в начале sk_buff резервируется под заголовки пакета, которые постепенно туда добавляются (см. рисунок справа). Поскольку пакет непрерывен, то огромным плюсом sk_buff является простота. Каждый, кто писал модули к iptables, знает, что пакет есть просто массив байт, просто берешь по нужному смещению и всё. Соответственно, минусом mbuf является сложность работы — необходимо постоянно помнить, что пакет может быть "размазан" по цепочке буферов, вызывать m_pullup(), дабы удостовериться, что заголовки пакета непрерывны (в худшем случае это может повлечь за собой выделение памяти и копирование части байт), и т.д. В некоторых случаях иметь не-непрерывный буфер вообще невозможно либо слишком трудоемко, тогда данные приходится копировать в отдельный непрерывный буфер (так делается, например, в портированном из юзерленда libalias, что несколько снижает его производительность), если они не находятся целиком в mbuf или кластере.

Однако, простота sk_buff в определенных случаях оборачивается минусом — поскольку размеры задаются один раз, обычно в месте выделения, при необходимости вместить больше заголовков, чем было рассчитано автором кода, приходится перетряхивать все такие места при любом серьезном изменении (на самом деле, не только поэтому, а еще и потому что там все возможные варианты протоколов сделаны в union, и т.д., в общем, обычный линуксовый стиль "о долговременном не думаем"). В mbuf такой проблемы (как и проблемы с размерами/экономией выделенной памяти) просто не существует. В результате неожиданно завернуть пакет в еще один туннель, или соорудить что-то еще более нетривиальное типа netgraph — в линуксе стоит гораздо более тяжелых усилий. При этом, наличие mbuf cluster'ов всё же до некоторой степени упрощает жизнь, хотя со всем историческим наследием дизайн mbuf'ов и нельзя назвать полностью удачным. Но перейдем к использованию того, что уже есть.

Поскольку интерфейсы для работы с mbuf описаны в системной документации, нет смысла повторять маны и приводить полные определения функций и макросов. Рассмотрим наиболее важные из них.

Макросы не всегда эквивалентны соответствующим функциями, иногда они могут включать незначительные отличия (например, MCLGET() может вернуть просто mbuf без установленного M_EXT, если не удалось выделить кластер, а m_getcl() вернет NULL и в этом случае).

Далее обратимся снова к рисунку 2. На нем в первой цепочке видно два mbuf, в первом заголовки, во втором — пользовательские данные. Здесь следует обратить внимание, что заголовки находятся в конце области данных mbuf. Как добиться этого эффекта? В зависимости от того, что было в начале, можно использовать разные функции/макросы. В типичном случае приписывания заголовков следует использовать оптимизированный макрос M_PREPEND(), который проверит наличие запрошенной длины (в которую потом пользователь поместит заголовки) в свободном месте в начале mbuf. Если его там нет, будет вызвана m_prepend() для прицепления нового пустого mbuf в голову цепочки. Последняя учтет, заголовок ли это пакета, при необходимости сделает M_MOVE_PKTHDR() для перемещения его в новый головной mbuf, и вызовет MH_ALIGN() или M_ALIGN() для собственно выравнивания указателя на данные в конец.

Для доступа к данным используется макрос mtod(). Если это нужно для доступа к заголовкам, предварительно следует вызвать m_pullup(), которая удостоверится, что данные запрошенной длины от начала цепочки — непрерывны и лежат в одном mbuf, при необходимости выделив его (и если ей не удастся, ipfw, например, напишет на консоль загадочное "pullup failed"). Обратите внимание, что только в одном mbuf (т.е. не более 200 байт по рисункам выше) — встречается ошибка, когда ею пытаются сделать непрерывным весь пакет. Для такой цели существует m_copydata(), которую надобно снабдить буфером, куда она скопирует пакет (или его часть по запрошенному смещению/длине). Чтобы положить данные из такого буфера обратно в цепочку (расширяя её при необходимости), предусмотрен m_copyback().

Если же непрерывность не требуется, можно воспользоваться m_getptr() для получения указателя/смещения mbuf, в котором лежит N-ный байт пакета в цепочке. О длине цепочки расскажет m_length(), а о свободном месте в одном mbuf — макросы M_LEADINGSPACE() и M_TRAILINGSPACE(). Добавить места, обрезав данные, можно с помощью m_adj(). Интересной функцией является также m_apply(), обходящая всю цепочку и вызывающая callback-функцию пользователя для каждого участка данных. Подобным образом, например, вызывается MD5_Update() и считается сигнатура TCP-пакета.

Есть и оперирующие цепочками функции: m_cat() для объединения, m_split() для разрезания, m_copym() для получения read-only копии цепочки увеличением счетчиков ссылок на кластерах (m_unshare() из разделяемой read-only копии скопирует в свою, приватную). Если данные кажутся слишком размазанными — m_defrag() сожмет цепочку в минимальное количество mbuf'ов и кластеров.

Подробнее обо всех этих (и других) интерфейсах можно прочитать в mbuf(9) и в книге "The Design and Implementation of the FreeBSD Operating System", by Marshall Kirk McKusick, George V. Neville-Neil (которая настоятельно рекомендуется к прочтению вообще всем, кому нужно писать в ядре).