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

Question

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

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

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

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

Answer 1

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

1. x = считывание p
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
//

Answer 2

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

shgmet, шмат, shmctl, shmdt

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

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

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

Просто укажите здесь свой собственный адрес;например , 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));
}

Answer 3

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

Answer 4

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

С помощью mmap:

void *mmap(void * addr, size_t длина, int prot, int флаги, int fd, off_t смещение);

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

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

MAP_SHARED КАРТА ОБЩЕГО ДОСТУПА Поделитесь этим отображением.Обновления сопоставления видны другим процессам, которые отображают этот файл, и передаются в базовый файл.Файл может не быть фактически обновлен до тех пор, пока не будет вызван msync(2) или munmap().

ОШИБКИ

ЭЙНВАЛ Нам не нравятся addr, длина или смещение (например, они слишком большие или не выровнены по границе страницы).

Answer 5

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