Русский
Русский
English
Статистика
Реклама

Shared memory

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

18.08.2020 08:21:44 | Автор: admin

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

Так и автор однажды задался мыслью, а что если если произойдёт вырождение адресов сегментов разделяемой памяти в разных процессах. Вообще-то именно это происходит, когда процесс с разделяемой памятью делает 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 sizexfree(_Ptr);}pointer allocate(size_type _Count){// allocate array of _Count elementsreturn (pointer)xalloc(sizeof(T) * _Count);}pointer allocate(size_type _Count, const void *){// allocate array of _Count elements, ignore hintreturn (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 fileNULL,                     // default securityPAGE_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 accessFALSE,                    // 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 objectFILE_MAP_ALL_ACCESS,      // read/write permission0,                        // 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 {// каждый знает что такое magicuint64_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 lockslock.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 156 541 753 5138 18549
THR_SPN 126 738 2530 10329 34704
PRC_SPN 124 727 2402 9234 32241
PRC_MTX 455 1301 7814 13325 35721

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

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru