Linux: Implementing linked list in shared memory

Question

I'm wondering is it possible to create linked list in shared memory (C, Linux).

Suppose I have library which creates a shared memory and returns a pointer to this memory. Example:

// 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;
}

So in the lib I have allocated shared memory enough for 20 structs SHM_STR_t.

What is the best way to add a new member each time I call lib_ret_shmem()?

Should I work with the offset of the base address of the memory (or with arrays)? Like for member [3] I'll return something like

*shm_pt = shm_map + 3;

OR it's possible to create linked list in this memory? I have the feeling that *next wont point to the correct memory.

Sorry for the terrible explanation :/

Your struct has no "next" pointer (or offset), so you're just creating an array, not a linked list. — Carey Gregory
– Carey Gregory, Commented Jan 29, 2013 at 21:14
yes, it hasn't :) suppose I add "struct list_head list;" in the struct . — Meh
– Meh, Commented Jan 29, 2013 at 21:25

phonetagger · Accepted Answer · 2013-01-29 21:24:12Z

1

If you're intending for the linked list to be shared across processes, then you can never use malloc() to create new nodes in the list; you'll need some other allocation mechanism. If all of the allocations will be of the same size, you can do that easily be creating a special shared_malloc() function that pulls the next allocation off of a free node list, and a shared_free() function that returns a node back to the free nodes list. That's not terribly difficult. When you create the shared memory pool, simply carve up the big mmap'ed allocation into individual blocks of memory of the size you need (or if you need more than one size, then make them all the largest size), and initialize them all with a 'next' pointer that points to the next guy in the memory range, and assign the "free list" head pointer to the first one in the list. Any time you need another allocation, grab the one at the head of the free list, and reassign the free list head pointer to the next one down the list.

If you're doing this in a multithread/multiprocess environment (indeed, why would you care about shared memory if it weren't?), then you'll need to consider concurrency in your shared_malloc() & shared_free() functions... perhaps use a semaphore or mutex. (Consider what would happen if process A had just grabbed the next free node, but hadn't adjusted the head pointer yet, and process B interrupts & grabs the top of the free list... now two processes both have the same node....)

answered Jan 29, 2013 at 21:24

phonetagger

7,9033 gold badges35 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Meh Over a year ago

yeah, that's why I'm thinking to do it with "array" (return the offset of the beginning). The MAX member count is known value so maybe it'll be easier...

phonetagger Over a year ago

@Meh - If your shared memory block isn't at the same address in all processes, you can use "offsets from the beginning of the shared memory space" as the next "pointers" in your linked list. That way the "pointers" would be meaningful in any of the processes where the linked list is seen (though it would require accessing them via pointer arithmetic, e.g. by using array index notation).

Collectives™ on Stack Overflow

Linux: Implementing linked list in shared memory

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related