HimeraSearchDB
Carding_EbayThief
triada
CrackerTuch
d-shop
HimeraSearchDB

НОВОСТИ STL, allocator, его разделяемая память и её особенности

NewsBot
Оффлайн

NewsBot

.
.
Регистрация
21.07.20
Сообщения
40.408
Реакции
1
Репутация
0
h1l-v_ou7wyccqrwkr1qvbvqpfs.png


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

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

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

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

Введение


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

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

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

    Фиг.1 структура разделяемой памяти PostgreSQL (
    You must be registered for see links
    )

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

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

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

Аллокатор STL


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

template
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 &) throw()
{ // construct by copying (do nothing)
}
template
stl_buddy_alloc(const stl_buddy_alloc &) 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
class q_map :
public std::map<
_Kty,
_Ty,
std::less,
stl_buddy_alloc >
>
{ };

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

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

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


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

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\\”
    You must be registered for see links
    , что объект будет создан в локальном пространстве имён сессии.
  • Чтобы присоединиться к уже созданному другим процессом отображению, используем

    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), каковы ограничения на её значение?
Вообще-то, есть разные виды ограничений.
Во-первых, архитектурные/аппаратные. Здесь следует сказать несколько слов о том, как виртуальный адрес превращается в физический. При промахе в кэше
You must be registered for see links
, приходится обращаться в древовидную структуру под названием “таблица страниц” (
You must be registered for see links
). Например, в IA-32 это выглядит так:
d7gmy1t43aryybkcljmfozvuwqq.png

Фиг.2 случай 4K страниц, взято
You must be registered for see links


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

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

Фиг.3 AMD64, 4K страницы, взято
You must be registered for see links


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

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

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

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

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

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


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

Во вторых. Мы говорим о средстве межпроцессного общения, любые оптимизации, связанные с использованием
You must be registered for see links
неуместны.

В третьих. Раз задействовано несколько процессов, сам аллокатор может жить очень долго, особую важность принимает уменьшение
You must be registered for see links
памяти.

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

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

Итого, учитывая всё вышесказанное а так же потому, что под рукой оказался живой аллокатор
You must be registered for see links
(любезно предоставленный Александром Артюшиным, слегка переработанный), выбор оказался несложным.

Описание деталей реализации оставим до лучших времён, сейчас интересен публичный интерфейс:
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_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();

    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
    • 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
    • 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_
    • PRC_MTX — несколько работающих процессов,
      синхронизация идёт через
      You must be registered for see links
      .
      qmap — glob_header_t::pglob_->q_map_

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

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)
You must be registered for see links
работать как спинлок, то именованный мутекс — это системный вызов, вход в режим ядра с соответствующими издержками. Кроме того, потеря потоком/процессом контекста исполнения это всегда очень дорого.

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

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

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


Напоследок


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


PS: спасибо Александру Артюшину и Дмитрию Иптышеву(
You must be registered for see links
) за помощь в подготовке данной статьи.
 
Войдите или зарегистрируйтесь для ответа.
Сверху Снизу