Можно ли хранить указатели в общей памяти без использования смещений?

При использовании общей памяти каждый процесс может отображать общую область в другую область своего соответствующего адресного пространства. Это означает, что при хранении указателей в общей области вам необходимо сохранить их как смещения начала общего региона. К сожалению, это усложняет использование атомарных инструкций (например, если вы пытаетесь написать алгоритм блокировки без блокировки). ). Например, предположим, что у вас есть куча узлов с подсчетом ссылок в общей памяти, созданных одним писателем. Модуль записи периодически атомарно обновляет указатель «p», чтобы он указывал на действительный узел с положительным счетчиком ссылок. Читатели хотят атомарно записывать 'p', потому что он указывает на начало узла (структуры), первый элемент которого является счетчиком ссылок. Поскольку p всегда указывает на действительный узел, увеличение счетчика ссылок является безопасным и делает безопасным разыменование 'p' и доступ к другим членам. Однако все это работает только тогда, когда все находится в одном адресном пространстве. Если узлы и указатель 'p' хранятся в разделяемой памяти, клиенты страдают от состояния гонки:

  1. х = читать р
  2. у = х + смещение
  3. Увеличение счетчика ссылок в y

Во время шага 2 p может измениться, и x может больше не указывать на действительный узел. Единственный обходной путь, который я могу придумать, - это каким-то образом заставить все процессы договориться о том, где отображать общую память, чтобы в области mmap'd могли храниться настоящие указатели, а не смещения. Есть ли способ сделать это? Я вижу MAP_FIXED в документации mmap, но не знаю, как выбрать безопасный адрес.

Изменить: используя встроенную сборку и префикс «блокировка» на x86, возможно, можно создать «приращение ptr X со смещением Y по значению Z»? Эквивалентные варианты на других архитектурах? Не написал много сборки, не знаю, существуют ли необходимые инструкции.


multithreading shared-memory race-condition atomic mmap
person Joseph Garvin    schedule 22.03.2010    source источник

Ответы (5)


arrow_upward
3
arrow_downward

На низком уровне атомарная инструкция x86 может выполнять все шаги этого дерева одновременно:

  1. х = читать р
  2. y = x + приращение смещения
  3. счетчик ссылок в y
//
      mov  edi, Destination
      mov  edx, DataOffset
      mov  ecx, NewData
 @Repeat:
      mov  eax, [edi + edx]    //load OldData
//Here you can also increment eax and save to [edi + edx]          
      lock cmpxchg dword ptr [edi + edx], ecx
      jnz  @Repeat
//
person GJ.    schedule 22.03.2010
comment
Если cmpxchg уже выполняет атомарное чтение и атомарную запись, необходима ли «блокировка»? Или это гарантирует, что edi + edx выполняется атомарно? Я действительно использовал только сборку MIPS. - person Joseph Garvin; 22.03.2010
comment
Блокировка гарантирует атомарный доступ к шине памяти, поэтому инструкция блокировки необходима. Вероятно, вы также можете использовать API InterlockedCompareExchange (проверьте MSDN для объяснения). Сначала загрузите 32-битный указатель памяти как OldValue, а затем увеличьте его, чтобы получить NewValue, после этого попробуйте выполнить InterlockedCompareExchange. InterlockedCompareExchange(Destination + Offset, NewValue, OldValue) вернет сравниваемое значение, если оно не совпадает со значением OldValue, которое обменивает какой-либо другой поток, поэтому обмен не производился, и вы должны повторить процедуру. - person GJ.; 22.03.2010

arrow_upward
3
arrow_downward

Это тривиально в системе UNIX; просто используйте функции общей памяти:

шгмет, шмат, шмктл, шмдт

void *shmat(int shmid, const void *shmaddr, int shmflg);

shmat() присоединяет сегмент разделяемой памяти, идентифицированный shmid, к адресному пространству вызывающего процесса. Адрес присоединения указывается shmaddr с одним из следующих критериев:

Если shmaddr имеет значение NULL, система выбирает подходящий (неиспользуемый) адрес для присоединения сегмента.

Просто укажите свой собственный адрес здесь; например 0x20000000000

Если вы shmget() используете один и тот же ключ и размер в каждом процессе, вы получите один и тот же сегмент разделяемой памяти. Если вы shmat() по одному и тому же адресу, виртуальные адреса будут одинаковыми во всех процессах. Ядру все равно, какой диапазон адресов вы используете, пока он не конфликтует с тем, где оно обычно назначает вещи. (Если вы пропустите адрес, вы увидите общую область, в которую он любит помещать вещи; также проверьте адреса в стеке и возвращенные из malloc() / new[] .)

В Linux убедитесь, что root устанавливает SHMMAX в /proc/sys/kernel/shmmax на достаточно большое число, чтобы вместить ваши сегменты общей памяти (по умолчанию 32 МБ).

Что касается атомарных операций, вы можете получить их все из исходного кода ядра Linux, например.

включить/asm-x86/atomic_64.h

/*
 * Make sure gcc doesn't try to be clever and move things around
 * on us. We need to use _exactly_ the address the user gave us,
 * not some alias that contains the same information.
 */
typedef struct {
        int counter;
} atomic_t;

/**
 * atomic_read - read atomic variable
 * @v: pointer of type atomic_t
 *
 * Atomically reads the value of @v.
 */
#define atomic_read(v)          ((v)->counter)

/**
 * atomic_set - set atomic variable
 * @v: pointer of type atomic_t
 * @i: required value
 *
 * Atomically sets the value of @v to @i.
 */
#define atomic_set(v, i)                (((v)->counter) = (i))


/**
 * atomic_add - add integer to atomic variable
 * @i: integer value to add
 * @v: pointer of type atomic_t
 *
 * Atomically adds @i to @v.
 */
static inline void atomic_add(int i, atomic_t *v)
{
        asm volatile(LOCK_PREFIX "addl %1,%0"
                     : "=m" (v->counter)
                     : "ir" (i), "m" (v->counter));
}

64-битная версия:

typedef struct {
        long counter;
} atomic64_t;

/**
 * atomic64_add - add integer to atomic64 variable
 * @i: integer value to add
 * @v: pointer to type atomic64_t
 *
 * Atomically adds @i to @v.
 */
static inline void atomic64_add(long i, atomic64_t *v)
{
        asm volatile(LOCK_PREFIX "addq %1,%0"
                     : "=m" (v->counter)
                     : "er" (i), "m" (v->counter));
}
person shm skywalker    schedule 20.04.2010

arrow_upward
2
arrow_downward

У нас есть код, похожий на ваше описание проблемы. Мы используем отображаемый в память файл, смещения и блокировку файлов. Мы не нашли альтернативы.

person Steve Emmerson    schedule 22.03.2010

arrow_upward
2
arrow_downward

Вы не должны бояться придумывать адрес наугад, потому что ядро ​​​​просто отклонит адреса, которые ему не нравятся (те, которые конфликтуют). См. мой shmat() ответ выше, используя 0x20000000000

С ммап:

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

Если адрес не равен NULL, то ядро ​​воспринимает это как подсказку о том, куда поместить отображение; в Linux сопоставление будет создано на следующей более высокой границе страницы. Адрес нового сопоставления возвращается в результате вызова.

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

MAP_SHARED Поделиться этим сопоставлением. Обновления отображения видны другим процессам, которые отображают этот файл, и переносятся в базовый файл. Файл может не обновляться до тех пор, пока не будет вызвана msync(2) или munmap().

ОШИБКИ

EINVAL Нам не нравятся адрес, длина или смещение (например, они слишком велики или не выровнены по границе страницы).

person shm skywalker    schedule 20.04.2010
comment
Интересно, я предполагал, что вы можете использовать его только при написании драйверов устройств или других хакерских атаках более низкого уровня. Это потенциально привлекательное решение, но для этого потребуется, чтобы все процессы попытались сопоставить различные регионы, пока не найдут тот, с которым они все согласны, и если будет запущен новый процесс, которому не понравится существующее сопоставление, все старые возможно, придется скопировать свои данные в новое место. Тем не менее классная идея, проголосовал. - person Joseph Garvin; 21.04.2010
comment
@shm skywalker, я знаю, что это старая тема, но это очень круто. Спасибо, что поделились :) Сейчас пытаюсь понять, почему ядро ​​вообще отклоняет? Есть ли способ предотвратить это отклонение - может быть, настроив компоновщик для создания неиспользуемого фиктивного раздела? - person user1827356; 07.05.2013

arrow_upward
1
arrow_downward

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

person Timothy Baldwin    schedule 18.08.2016