STL, allocator, его разделяемая память и её особенности

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

Так и автор однажды задался мыслью, а что если … если произойдёт вырождение адресов сегментов разделяемой памяти в разных процессах. Вообще-то именно это происходит, когда процесс с разделяемой памятью делает fork, а как насчет разных процессов? Кроме того, не во всех системах есть fork.

Казалось бы, совпали адреса и что с того? Как минимум, можно пользоваться абсолютными указателями и это избавляет от кучи головной боли. Станет возможно работать со строками и контейнерами С++, сконструированными из разделяемой памяти.

Отличный, кстати, пример. Не то, чтобы автор сильно любил STL, но это возможность продемонстрировать компактный и всем понятный тест на работоспособность предлагаемой методики. Методики, позволяющей (как видится) существенно упростить и ускорить межпроцессное взаимодействие. Вот работает ли она и чем придётся заплатить, будем разбираться далее.

Введение

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

А с распространением 64-разрядных операционных систем и повсеместным использованием когерентного кэша, идея разделяемой памяти получила второе дыхание. Теперь это не просто циклический буфер — реализация “трубы” своими руками, а настоящий “трансфункционер континуума” — крайне загадочный и мощный прибор, причем, лишь его загадочность равна его мощи.

Рассмотрим несколько примеров использования.

• Протокол “shared memory” при обмене данными с MS SQL. Демонстрирует некоторое улучшение производительности (~10...15%)
• Mysql также имеет под Windows протокол “shared memory”, который улучшает производительность передачи данных на десятки процентов.
• Sqlite размещает в разделяемой памяти индекс навигации по WAL-файлу. Причем берётся существующий файл, который отображается в память. Это позволяет использовать его процессам с разными корневыми директориями (chroot).
• PostgreSQL использует как раз fork для порождения процессов-обработчиков запросов. Причем эти процессы наследуют разделяемую память, структура которой показана ниже.
  
  
  
  
  Фиг.1 структура разделяемой памяти PostgreSQL (отсюда)

Из общих соображений, а какой бы мы хотели видеть идеальную разделяемую память? На это легко ответить — желаем, чтобы объекты в ней можно было использовать, как если бы это были объекты, разделяемые между потоками одного процесса. Да, нужна синхронизация (а она в любом случае нужна), но в остальном — просто берёшь и используешь! Пожалуй, … это можно устроить.

Для проверки концепции требуется минимально-осмысленная задача:

• есть аналог std::map<std::string, std::string>, расположенный в разделяемой памяти
• имеем N процессов, которые асинхронно вносят/меняют значения с префиксом, соответствующим номеру процесса (ex: key_1_… для процесса номер 1)
• в результате, конечный результат мы можем проконтролировать

Начнём с самого простого — раз у нас есть std::string и std::map, потребуется и специальный аллокатор STL.

Аллокатор STL

Допустим, для работы с разделяемой памятью существуют функции xalloc/xfree как аналоги malloc/free. В этом случае аллокатор выглядит так:

template <typename T>
class stl_buddy_alloc
{
public:
	typedef T                 value_type;
	typedef value_type*       pointer;
	typedef value_type&       reference;
	typedef const value_type* const_pointer;
	typedef const value_type& const_reference;
	typedef ptrdiff_t         difference_type;
	typedef size_t            size_type;
public:
	stl_buddy_alloc() throw()
	{	// construct default allocator (do nothing)
	}
	stl_buddy_alloc(const stl_buddy_alloc<T> &) throw()
	{	// construct by copying (do nothing)
	}
	template<class _Other>
	stl_buddy_alloc(const stl_buddy_alloc<_Other> &) throw()
	{	// construct from a related allocator (do nothing)
	}

	void deallocate(pointer _Ptr, size_type)
	{	// deallocate object at _Ptr, ignore size
		xfree(_Ptr);
	}
	pointer allocate(size_type _Count)
	{	// allocate array of _Count elements
		return (pointer)xalloc(sizeof(T) * _Count);
	}
	pointer allocate(size_type _Count, const void *)
	{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
	}
};

Этого достаточно, чтобы подсадить на него std::map & std::string

template <typename _Kty, typename _Ty>
class q_map : 
    public std::map<
        _Kty, 
        _Ty, 
        std::less<_Kty>, 
        stl_buddy_alloc<std::pair<const _Kty, _Ty> > 
    >
{ };

typedef std::basic_string<
        char, 
        std::char_traits<char>, 
        stl_buddy_alloc<char> > q_string

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

Разделяемая память

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

Windows

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

  HANDLE hMapFile = CreateFileMapping(
  	INVALID_HANDLE_VALUE,     // use paging file
  	NULL,                     // default security
  	PAGE_READWRITE,           // read/write access
  	(alloc_size >> 32)        // maximum object size (high-order DWORD)
  	(alloc_size & 0xffffffff),// maximum object size (low-order DWORD)
  	"Local\\SomeData");       // name of mapping object
  

  
  Префикс имени файла “Local\\” означает, что объект будет создан в локальном пространстве имён сессии.
• Чтобы присоединиться к уже созданному другим процессом отображению, используем
  
  

  HANDLE hMapFile = OpenFileMapping(
  	FILE_MAP_ALL_ACCESS,      // read/write access
  	FALSE,                    // do not inherit the name
  	"Local\\SomeData");       // name of mapping object
  

• Теперь необходимо создать сегмент, указывающий на готовое отображение
  
  

  void *hint = (void *)0x200000000000ll;
  unsigned char *shared_ptr = (unsigned char*)MapViewOfFileEx(
  	hMapFile,                 // handle to map object
  	FILE_MAP_ALL_ACCESS,      // read/write permission
  	0,                        // offset in map object (high-order DWORD)
  	0,                        // offset in map object (low-order DWORD)
  	0,                        // segment size,
  	hint);                    // подсказка
  

  
  segment size 0 означает, что будет использован размер, с которым создано отображение с учетом сдвига.
  
  Самое важно здесь — hint. Если он не задан (NULL), система подберет адрес на своё усмотрение. Но если значение ненулевое, будет сделана попытка создать сегмент нужного размера с нужным адресом. Именно определяя его значение одинаковым в разных процессах мы и добиваемся вырождения адресов разделяемой памяти. В 32-разрядном режиме найти большой незанятый непрерывный кусок адресного пространства непросто, в 64-разрядном же такой проблемы нет, всегда можно подобрать что-нибудь подходящее.

Linux

Здесь принципиально всё то же самое.

• Создаём объект разделяемой памяти
  
  

    int fd = shm_open(
                   “/SomeData”,               // имя объекта, начинается с /
                   O_CREAT | O_EXCL | O_RDWR, // flags, аналогично open
                   S_IRUSR | S_IWUSR);        // mode, аналогично open
  
    ftruncate(fd, alloc_size);
  

  
  ftruncate в данном случае используется чтобы задать размер разделяемой памяти. Использование shm_open аналогично созданию файла в /dev/shm/. Есть еще устаревший вариант через shmget\shmat от SysV, где в качестве идентификатора объекта используется ftok (inode от реально существующего файла).
• Чтобы присоединиться к созданной разделяемой памяти
  
  

  int fd = shm_open(“/SomeData”, O_RDWR, 0);
  

• для создания сегмента
  
  

    void *hint = (void *)0x200000000000ll;
    unsigned char *shared_ptr = (unsigned char*) = mmap(
                     hint,                      // подсказка
                     alloc_size,                // segment size,
                     PROT_READ | PROT_WRITE,    // protection flags
                     MAP_SHARED,                // sharing flags
                     fd,                        // handle to map object
                     0);                        // offset
  

  
  Здесь также важен hint.

Ограничения на подсказку

Что касается подсказки (hint), каковы ограничения на её значение? Вообще-то, есть разные виды ограничений.

Во-первых, архитектурные/аппаратные. Здесь следует сказать несколько слов о том, как виртуальный адрес превращается в физический. При промахе в кэше TLB, приходится обращаться в древовидную структуру под названием “таблица страниц” (page table). Например, в IA-32 это выглядит так:

Фиг.2 случай 4K страниц, взято здесь

Входом в дерево является содержимое регистра CR3, индексы в страницах разных уровней — фрагменты виртуального адреса. В данном случае 32 разряда превращаются в 32 разряда, всё честно.

В AMD64 картина выглядит немного по-другому.

Фиг.3 AMD64, 4K страницы, взято отсюда

В CR3 теперь 40 значимых разрядов вместо 20 ранее, в дереве 4 уровня страниц, физический адрес ограничен 52 разрядами при том, что виртуальный адрес ограничен 48 разрядами.

И лишь в(начиная с) микроархитектуре Ice Lake(Intel) дозволено использовать 57 разрядов виртуального адреса (и по-прежнему 52 физического) при работе с 5-уровневой таблицей страниц.

До сих пор мы говорили лишь об Intel/AMD. Просто для разнообразия, в архитектуре Aarch64 таблица страниц может быть 3 или 4 уровневой, разрешая использование 39 или 48 разрядов в виртуальном адресе соответственно (1).

Во вторых, программные ограничения. Microsoft, в частности, налагает (44 разряда до 8.1/Server12, 48 начиная с) таковые на разные варианты ОС исходя из, в том числе, маркетинговых соображений.

Между прочим, 48 разрядов, это 65 тысяч раз по 4Гб, пожалуй, на таких просторах всегда найдётся уголок, куда можно приткнуться со своим hint-ом.

Аллокатор разделяемой памяти

Во первых. Аллокатор должен жить на выделенной разделяемой памяти, размещая все свои внутренние данные там же.

Во вторых. Мы говорим о средстве межпроцессного общения, любые оптимизации, связанные с использованием TLS неуместны.

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

В четвертых. Обращения к ОС за дополнительной памятью недопустимы. Так, dlmalloc, например, выделяет фрагменты относительно большого размера непосредственно через mmap. Да, его можно отучить, завысив порог, но тем не менее.

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

Итого, учитывая всё вышесказанное а так же потому, что под рук��й оказался живой аллокатор методом близнецов (любезно предоставленный Александром Артюшиным, слегка переработанный), выбор оказался несложным.

Описание деталей реализации оставим до лучших времён, сейчас интересен публичный интерфейс:

class BuddyAllocator {
public:
	BuddyAllocator(uint64_t maxCapacity, u_char * buf, uint64_t bufsize);
	~BuddyAllocator(){};

	void *allocBlock(uint64_t nbytes);
	void freeBlock(void *ptr);
...
};

Деструктор тривиальный т.к. никаких посторонних ресурсов BuddyAllocator не захватывает.

Последние приготовления

Раз всё размещено в разделяемой памяти, у этой памяти должен быть заголовок. Для нашего теста этот заголовок выглядит так:

struct glob_header_t {
	// каждый знает что такое magic
	uint64_t magic_;
	// hint для присоединения к разделяемой памяти
	const void *own_addr_;
	// собственно аллокатор
	BuddyAllocator alloc_;
	// спинлок
	std::atomic_flag lock_;
	// контейнер для тестирования
	q_map<q_string, q_string> q_map_;

	static const size_t alloc_shift = 0x01000000;
	static const size_t balloc_size = 0x10000000;
	static const size_t alloc_size = balloc_size + alloc_shift;
	static glob_header_t *pglob_;
};
static_assert (
    sizeof(glob_header_t) < glob_header_t::alloc_shift, 
    "glob_header_t size mismatch");

glob_header_t *glob_header_t::pglob_ = NULL;

• own_addr_ прописывается при создании разделяемой памяти для того, чтобы все, кто присоединяются к ней по имени могли узнать фактический адрес (hint) и пере-подключиться при необходимости
• вот так хардкодить размеры нехорошо, но для тестов приемлемо
• вызывать конструктор(ы) должен процесс, создающий разделяемую память, выглядит это так:
  
  

  glob_header_t::pglob_ = (glob_header_t *)shared_ptr;
  
  new (&glob_header_t::pglob_->alloc_)
          qz::BuddyAllocator(
                  // максимальный размер
                  glob_header_t::balloc_size,
                  // стартовый указатель
                  shared_ptr + glob_header_t::alloc_shift,
                  // размер доступной памяти
                  glob_header_t::alloc_size - glob_header_t::alloc_shift;
  
  new (&glob_header_t::pglob_->q_map_) 
                  q_map<q_string, q_string>();
  
  glob_header_t::pglob_->lock_.clear();
  

• подключающийся к разделяемой памяти процесс получает всё в готовом виде
• теперь у нас есть всё что нужно для тестов кроме функций xalloc/xfree
  
  

  void *xalloc(size_t size)
  {
  	return glob_header_t::pglob_->alloc_.allocBlock(size);
  }
  void xfree(void* ptr)
  {
  	glob_header_t::pglob_->alloc_.freeBlock(ptr);
  }
  

Похоже, можно начинать.

Эксперимент

Сам тест очень прост:

for (int i = 0; i < 100000000; i++)
{
        char buf1[64];
        sprintf(buf1, "key_%d_%d", curid, (i % 100) + 1);
        char buf2[64];
        sprintf(buf2, "val_%d", i + 1);

        LOCK();

        qmap.erase(buf1); // пусть аллокатор трудится
        qmap[buf1] = buf2;

        UNLOCK();
}

Curid — это номер процесса/потока, процесс, создавший разделяемую память имеет нулевой curid, но для теста это неважно.
Qmap, LOCK/UNLOCK для разных тестов разные.

Проведем несколько тестов

1. THR_MTX — многопоточное приложение, синхронизация идёт через std::recursive_mutex,
   qmap — глобальная std::map<std::string, std::string>
2. THR_SPN — многопоточное приложение, синхронизация идёт через спинлок:
   
   

   std::atomic_flag slock;
   ..
   while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
   …
   slock.clear(std::memory_order_release);                 // release lock
   

   
   qmap — глобальная std::map<std::string, std::string>
3. PRC_SPN — несколько работающих процессов, синхронизация идёт через спинлок:
   
   

   while (glob_header_t::pglob_->lock_.test_and_set(              // acquire lock
           std::memory_order_acquire));                          
   …
   glob_header_t::pglob_->lock_.clear(std::memory_order_release); // release lock
   

   qmap — glob_header_t::pglob_->q_map_
4. PRC_MTX — несколько работающих процессов, синхронизация идёт через именованный мутекс.
   
   qmap — glob_header_t::pglob_->q_map_

Результаты (тип теста vs. число процессов\потоков):

	1	2	4	8	16
THR_MTX	1’56’’	5’41’’	7’53’’	51’38’’	185’49
THR_SPN	1’26’’	7’38’’	25’30’’	103’29’’	347’04’’
PRC_SPN	1’24’’	7’27’’	24’02’’	92’34’’	322’41’’
PRC_MTX	4’55’’	13’01’’	78’14’’	133’25’’	357’21’’

Эксперимент проводился на двухпроцессорном (48 ядер) компьютере с Xeon® Gold 5118 2.3GHz, Windows Server 2016.

Итого

• Да, использовать объекты/контейнеры STL (размещенные в разделяемой памяти) из разных процессов можно при условии, что они сконструированы надлежащим образом.
• По производительности явного проигрыша нет, скорее наоборот, PRC_SPN даже чуть быстрее THR_SPN. Поскольку разница здесь только в аллокаторе, значит BuddyAllocator чуть быстрее malloc\free от MS (при невысокой конкуренции).
• Проблемой является высокая конкуренция. Даже самый быстрый вариант — многопоточность + std::mutex в этих условиях работает безобразно медленно. Здесь были бы полезны lock-free контейнеры, но это уже тема для отдельного разговора.

Вдогонку

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

Объяснение дороговизны простое, если std::(recursive_)mutex (критическая секция под windows) умеет работать как спинлок, то именованный мутекс — это системный вызов, вход в режим ядра с соответствующими издержками. Кроме того, потеря потоком/процессом контекста исполнения это всегда очень дорого.

Но раз синхронизация процессов неизбежна, как же нам уменьшить издержки? Ответ давно придуман — буферизация. Синхронизируется не каждый отдельный пакет, а некоторый объем данных — буфер, в который эти данные сериализуются. Если буфер заметно больше размера пакета, то и синхронизироваться приходится заметно реже.

Удобно смешивать две техники — данные в разделяемой памяти, а через межпроцессный канал данных (ex: петля через localhost) отправляют только относительные указатели (от начала разделяемой памяти). Т.к. указатель обычно меньше пакета данных, удаётся сэкономить на синхронизации.

А в случае, когда разным процессам доступна разделяемая память по одному виртуальному адресу, можно еще немного добавить производительности.

• не сериализуем данные для отправки, не десериализуем при получении
• отправляем через поток честные указатели на объекты, созданные в разделяемой памяти
• при получении готового (указателя) объекта, пользуемся им, затем удаляем через обычный delete, вся память автоматически освобождается. Это избавляет нас от возни с кольцевым буфером
• можно даже посылать не указатель, а (минимально возможное — байт со значением “you have mail”) уведомление о факте наличия чего-нибудь в очереди

Напоследок

Чего нельзя делать с объектами, сконструированными в разделяемой памяти.

1. Использовать RTTI. По понятным причинам. Std::type_info объекта существует вне разделяемой памяти и недоступен в разных процессах.
2. Использовать виртуальные методы. По той же причине. Таблицы виртуальных функций и сами функции недоступны в разных процессах.
3. Если говорить об STL, все исполняемые файлы процессов, разделяющих память, должны быть скомпилированы одним компилятором с одними настройками да и сама STL должна быть одинаковой.

PS: спасибо Александру Артюшину и Дмитрию Иптышеву (Dmitria) за помощь в подготовке данной статьи.

UPD: исходники BuddyAllocator выложены здесь под BSD лицензией.