Miser – динамически загружаемый аллокатор памяти для многопоточных приложений

Создать новую статью

23.11.2009 12:00


Данный текст является продолжением статьи Параллельные механизмы выделения памяти.

При работе с одним из ранних прототипов Cilk++ довольно быстро стало понятно, что механизм выделения памяти, предоставляемый по умолчанию ран-тайм библиотекой С для Windows, становится узким местом многопоточных приложений. Аллокатор памяти для Windows имеет одну единственную блокировку, которая используется для обеспечения последовательного доступа к его внутренним структурам. Это вполне безопасно, но приводит к серьезным потерям в параллелизме.

Существует множество механизмов выделения памяти, как бесплатных, так и коммерческих. Мы исследовали некоторые из них и обнаружили, что ни один не обладает всеми качествами, которые мы искали. В итоге мы решили написать свой собственный. Поскольку конечный продукт был приложением для Windows, то мы сначала занялись реализацией для Windows.

Функции, заимствованные от Hoard

Мы решили создать новый аллокатор на основе принципов, заложенных в Hoard: A Scalable Memory Allocator for Multithreaded Applications  Эмери Бергера (Emery D. Berger), Кэтрин МакКинли (Kathryn S. McKinley), Роберта Блюмоф (Robert D. Blumofe) и Пола Вилсона (Paul R. Wilson). Hoard был разработан с целью минимизировать блокировки, соревнование, false sharing (ложное общее использование) и дрейф памяти. Детальное описание Hoard можно найти на сайте Hoard.

Мы назвали наш новый отводчик памяти «Miser», чтобы сыграть на его отношении к Hoard (игра слов, Hoard означает «запас», Miser означает «жадина», прим. пер.). Мы создали реализации Miser как для Linux, так и для Windows. В данной заметке описываются общие структуры данных в обеих версиях, некоторые особенности реализации для Windows и, в конце, несколько замечаний, относящихся к Linux.

Суперблоки

Основной единицей распределения памяти в Miser является суперблок (superblock). Суперблок содержит заголовок, массив для хранения размеров каждого затребованного блока памяти и массив равных по размеру блоков памяти, или корзин (bins), которые и используются при выделении памяти. Корзины имеют размер степени двойки, от 8 до 256 байт. Исследования показали, что такой размер удовлетворяет более чем 98% всех случаев. Выделение блоков большего размера перепоручается стандартным механизмам языка С. Массив корзин располагается в конце суперблока, поэтому блоки памяти, возвращаемые пользователю, являются естественно выровненными.

Глобальный пул памяти и пулы потоков

Miser, как и Hoard, создает собственный пул памяти для каждого потока. Поскольку пул является собственностью потока, к нему можно обращаться без блокировки. Пул состоит из суперблоков, которые грубо отсортированы по размеру оставшегося в них свободного места. Использование локальных потоковых пулов памяти является фундаментальным принципом оптимизации производительности приложений:

  • Пул памяти потока позволяет Miser выполнять бОльшую часть запросов по выделению памяти без блокировки.
  • Пул памяти потока минимизирует false sharing. Пока блоки не передаются между потоками, все обращения к памяти на одной линии кэша исходят от одного и того же потока.

Глобальный пул не принадлежит потокам. Если локальный пул потока не может удовлетворить запрос на память, то он берет еще один суперблок из глобального пула. Если глобальный пул пуст, Miser берет дополнительную память у операционной системы. По мере освобождения памяти в локальном пуле суперблоки переходят обратно в глобальный пул, чтобы предотвратить дрейф памяти.

Дополнительные функции

Хотя функциональность Hoard является хорошей базой, в Miser мы добавили следующие требования:

  • Он должен иметь возможность загружаться динамически. Это позволяет использовать компоненты Miser в виде общей (shared) библиотеки, не требуя от приложения загружать библиотеку при старте.
  • Он должен уметь узнавать блоки, выделенные не им, и передавать их системной библиотеке С.
  • Он должен быть потокобезопасным и быстрым.
  • Он должен уметь одновременно поддерживать разные версии рантайм библиотеки С, которые использует приложение.

Динамическая загрузка Miser

Формат исполняемого файла или динамической библиотеки (DLL) Windows определяется форматом исполняемых файлов Windows Portable Executable File Format. Почти все модули Windows импортируют функции из других модулей. Эти зависимости описываются парой таблиц: Import Name Table и Import Address Table. Когда модуль загружается в память, загрузчик проставляет адреса входных точек модуля в Import Address Table. Все вызовы функций из модуля косвенно осуществляются через эту таблицу.

Когда Miser загружается приложением, он пробегает все модули приложения и перенаправляет указатели в  Import Address Table для каждой функции выделения памяти из библиотеки С на свои собственные. Эта технология была впервые описана Мэттом Пьетреком (Matt Pietrek) в статье Peering Inside the PE: A Tour of the Win32 Portable Executable File Format. Поскольку изменение пункта таблицы IAT представляет собой  запись 32 бит, операция атомарна; пункт таблицы может являться адресом либо динамической библиотеки С, либо Miser.

После того, как Miser загружается в процесс, его уже нельзя выгрузить, потому что хотя Miser и может восстанавливать изначальные указатели функций библиотеки С в IAT, сама библиотека С не может управлять памятью, отведенной в Miser.

Распознавание блоков, выделенных отличными от Miser инструментами

Когда Miser загружается, некоторый объем памяти может быть уже выделен. Miser не может заменить эти блоки памяти блоками из своих ресурсов. Поскольку Miser переводит все вызовы free() and _msize() на себя, то он должен уметь опознавать блоки, распределенные библиотекой С, и перенаправить соответствующие вызовы нужной версии библиотеки С.

ОС Windows предоставляет несколько пользовательских API для управления памятью. Одним из самых фундаментальных является функция VirtualAlloc(), которая отводит память 64К блоками по границам 64К. Miser разбивает их на суперблоки по 4Кбайта, выровненных по границе 4К. Это не случайно: таков размер страницы памяти в 32-разрядной Windows. В начале суперблока содержится заголовок, включающий «магическое число» и другую контрольную информацию. Т.о. маскируя нижние 12 битов адреса памяти мы получаем заголовок суперблока, содержащего данный блок памяти. Существует два метода проверки суперблока:

  • Заголовок суперблока содержит правильное «магическое число».
  • Заголовок суперблока содержит указатель на локальный пул памяти потока, который владеет этим суперблоком, и индекс массива указателей на суперблоки, принадлежащие локальному пулу. Элемент массива должен соответствовать адресу суперблока.

Если хотя бы один из этих тестов не проходит, Miser передает вызов библиотеке Windows С.

Дополнительным плюсом «распознавания» блоков памяти, выделенных библиотекой С, является возможность Miser передавать стандартным средствам все запросы на блоки более 256 байт.

Поддержка разных версий библиотеки С

Каждый модуль, загруженный приложением, может требовать ту или иную версию библиотеки С. В дополнение к взаимной поддержке, встроенной в ОС, последние версии библиотеки С включают номер версии в имени DLL. Miser поддерживает все версии библиотеки С начиная с Visual Studio .NET 2002. Поскольку каждая версия библиотеки С имеет свою собственную кучу (heap), Miser запоминает, за какую версию библиотеки С он зацепился и перенаправляет запросы соответственно.

Скорость и потокобезопасность

Потокобезопасность и скорость работы очень тесно связаны. Чем больше блокировок использует поток, тем больше вероятность, что ему придется дожидаться своей очереди. Для большинства операций Miser не использует блокировок – как правило, для удовлетворения запроса хватает ресурсов локального пула. Блокировку приходится применять в следующих случаях:

  1. Доступ к глобальному пулу – только один поток может обращаться к глобальному пулу за раз. Любой поток, получающий доступ к глобальному пулу, сначала должен установить на него блокировку. Фактически, доступ к глобальному пулу является последовательным.
  2. Освобождение блока, распределенного из другого локального пула – в отличие от Hoard, Miser не блокирует заголовок суперблока. Блоки, освобождаемые в другом локальном пуле, размещаются в очереди на освобождение этого локального пула с помощью интерблокированных инструкций (interlocked instructions). Удаленная очередь на освобождение очищается до того, как будет отведен новый блок, в надежде, что освобожденный блок будет использован новым запросом.
  3. Поддержка _msize() для блоков, отведенных другим потоком – Функция _msize() позволяет приложениям Windows запрашивать у библиотеки С размер блока памяти. Возвращаемое значение представляет собой размер блока в байтах, на момент выделения памяти. Если блок был выделен с помощью Miser в текущем потоке, то мы можем пользоваться информацией суперблока, принадлежащего локальному пулу памяти. Однако, если суперблок принадлежит локальному пулу другого потока, то нужно заблокировать локальный пул перед попыткой проверки суперблока через массив суперблоков.
  4. Поддержка списка суперблоков – Каждый локальный пул потока содержит массив суперблоков, которые он распределил. Заголовок каждого суперблока содержит указатель на локальный пул, которому этот суперблок принадлежит, а также индекс из массива суперблоков пула. Эти данные используются для проверки того, что адрес памяти принадлежит блоку, который распределил Miser. Так как другой поток может потребовать доступ к массиву суперблоков, чтобы выполнить свой вызов _msize(), перед обновлением массив суперблоков необходимо заблокировать.

Необходимо отметить, что хотя Miser и поддерживает Cilk++, он ни коим образом не привязан к компилятору или динамическим библиотекам Cilk++. Так же хорошо он будет работать в любом многопоточном приложении, использующем любую параллельную технологию.

Ограничения Miser в Windows

  • Miser не поддерживает функции библиотеки С, которые выделяют память с выравниванием по границе адреса.
  • Miser подразумевает, что программа работает правильно. Он не оставляет никаких полей между блоками в попытке обнаружить запись вне границ отведенной памяти. Отведенные блоки располагаются вплотную друг к другу. Miser содержит размеры отведенных блоков в отдельной структуре, чтобы сохранить естественно выровненное расположение массивов корзин.
  • Из-за зависимости от таблицы Import Address Table, Miser можно использовать только с DLL модулями библиотеки С. Модули, скомпилированные статически,  не проходят через IAT, и Miser не может их подхватить.

Производительность

Ниже приведен пример выигрыша в производительности, которого можно достичь с помощью Miser. Пример взят из статьи Multicore-enabling the N-Queens Problem Using Cilk++.

Выигрыш в производительности с помощью Miser

Miser в Linux

Хотя Miser изначально писался для Windows, после того, как в некоторых тестах он показал более высокую производительность, чем Hoard, его решено было портировать на Linux. Внутренний код остался практически без изменений, за исключением некоторых системных вызовов (например, пришлось заменить VirtualAlloc() на mmap() и т.д.).

Что касается интерфейса, то механизм доступа к функциям был переписан. Библиотека Miser экспортирует malloc(), free(), calloc() и т.д., и подключение какого-либо бинарного файла заставляет загрузчик искать их. К тому же, предварительная загрузка с помощью установки LD_LIBRARY_PATH заставляет объекты находить в первую очередь аллокаторы Miser, и лишь затем библиотеки С. Miser использует системную функцию  malloc() при обработке больших запросов, и она находит их в текущей библиотеке с помощью dlsym().

Miser не подменяет собой стандартные средства выделения памяти в Linux, если он загружается после того, как модуль обнаружил функции работы с памятью. Однако, возможно использовать его функции malloc() с помощью dlsym() и получать «malloc» из библиотеки, но, как и в Windows, память, отведенная с помощью Miser, должна освобождаться также с помощью Miser. Системная функция free() не будет знать, что делать с памятью, распределенной Miser.

Дополнительные ресурсы по Cilk++

Данная статья является переводом блога Бэрри Тэнненбаума (Barry Tannenbaum).
Оригинал доступен по адресу http://www.cilk.com/multicore-blog/bid/7812/Miser-A-Dynamically-Loadable-Memory-Allocator-for-Multi-Threaded-Applications.