Linux: реализация связанного списка в разделяемой памяти

Мне интересно, можно ли создать связанный список в общей памяти (C, Linux).

Предположим, у меня есть библиотека, которая создает разделяемую память и возвращает указатель на эту память. Пример:

// in lib header
typedef struct _SHM_STR_ {
    int i;
    char c;
} SHM_STR_t;

// in libomg.so
void lib_ret_shmem(SHM_STR_t** shm_pt)
{
    int shm_fd;
    SHM_STR_t *shm_map;

    if ((shm_fd = shm_open(SHM_FILE, (O_CREAT | O_EXCL | O_RDWR), (S_IREAD | S_IWRITE))) > 0) {
        //first time created; init
        ...
    } else if ((shm_fd = shm_open(SHM_FILE, (O_CREAT | O_RDWR), (S_IREAD | S_IWRITE))) < 0) {
        return 1;
    }

    ftruncate(shm_fd, 20*sizeof(SHM_STR_t));

    shm_map = (SHM_STR_t *)mmap(0, 20*sizeof(SHM_STR_t), (PROT_READ | PROT_WRITE), MAP_SHARED, shm_fd, 0)
    ...
    // add new member
    // linked list or work with the offset in the shared mem?
    // increment pointer with offset and return in:
    *shm_pt = shm_map;
}

// in proc1.c something like this
int main(int argc, char *argv[])
{
    SHM_STR_t *ppp = NULL;

    lib_ret_shmem(&ppp);
    printf("%d %c\n", ppp->a, ppp->b);

    return 0;
}

Итак, в библиотеке я выделил общей памяти достаточно для 20 структур SHM_STR_t.

Как лучше всего добавлять нового члена каждый раз, когда я вызываю lib_ret_shmem()?

Должен ли я работать со смещением базового адреса памяти (или с массивами)? Лайк для участника [3] Я верну что-то вроде

*shm_pt = shm_map + 3;

ИЛИ в этой памяти можно создать связанный список? У меня такое ощущение, что *next не будет указывать на правильную память.

Извините за ужасное объяснение :/


c linux shared-memory linked-list
person Meh    schedule 29.01.2013    source источник
comment
В вашей структуре нет следующего указателя (или смещения), поэтому вы просто создаете массив, а не связанный список.   -  person Carey Gregory    schedule 30.01.2013
comment
да, нет :) предположим, я добавляю struct list_head list; в структуре.   -  person Meh    schedule 30.01.2013

Ответы (1)


arrow_upward
1
arrow_downward

Если вы хотите, чтобы связанный список был общим для процессов, вы никогда не сможете использовать malloc() для создания новых узлов в списке; вам понадобится другой механизм распределения. Если все распределения будут одинакового размера, вы можете легко сделать это, создав специальную функцию shared_malloc(), которая извлекает следующее выделение из списка свободных узлов, и функцию shared_free(), которая возвращает узел обратно в список. список свободных узлов. Это не очень сложно. Когда вы создаете общий пул памяти, просто разделите большое выделение mmap на отдельные блоки памяти нужного вам размера (или, если вам нужно более одного размера, сделайте их все самого большого размера) и инициализируйте их все с указателем «следующий», который указывает на следующего парня в диапазоне памяти, и назначьте указатель заголовка «свободный список» первому в списке. В любое время, когда вам нужно другое выделение, возьмите тот, который находится во главе списка свободных мест, и переназначьте указатель заголовка списка свободных мест следующему в списке.

Если вы делаете это в многопоточной/многопроцессорной среде (действительно, зачем вам заботиться об общей памяти, если это не так?), то вам нужно будет учитывать параллелизм в ваших функциях shared_malloc() и shared_free(). т. е. возможно используйте семафор или мьютекс. (Подумайте, что произойдет, если процесс A только что захватил следующий свободный узел, но еще не скорректировал указатель начала, а процесс B прерывает и захватывает вершину списка свободных... теперь два процесса имеют один и тот же узел. ...)

person phonetagger    schedule 29.01.2013
comment
да, именно поэтому я думаю сделать это с помощью массива (вернуть смещение начала). Количество членов MAX известно, поэтому, возможно, будет проще... - person Meh; 30.01.2013
comment
@Meh - Если ваш блок общей памяти не находится по одному и тому же адресу во всех процессах, вы можете использовать смещения от начала пространства общей памяти в качестве указателей next в вашем связанном списке. Таким образом, указатели будут иметь смысл в любом из процессов, где виден связанный список (хотя для этого потребуется доступ к ним с помощью арифметики указателей, например, с использованием нотации индекса массива). - person phonetagger; 30.01.2013