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. число процессов\потоков):

Эксперимент проводился на двухпроцессорном (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 лицензией.