Home > Archive > Unix Programming > February 2007 > Posix Shared memory with linked list
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Posix Shared memory with linked list
|
|
| queengambit 2007-02-25, 7:06 pm |
| Hi people, as the subject title already says I've got trouble with how
to use a linked list in a shared memory between processes. More
specific, initially my linked list would be NULL and it is a doubly
circular linked list. Here is the structure of any element in the
linked list:
typedef struct my_ringnode_st my_ringnode_t;
struct my_ringnode_st {
my_ringnode_t *next;
my_ringnode_t *prev;
};
I would like my linked list to be able to shrink/expand without
running into the coredumb/memory violation. Having looked at other
posts, i know that i have to use offset instead of pointers 'next' &
'prev' to refer to next and previous elements of the linked list; but
still i'm still  about how to do that, what size initially my
shared memory should be and if the my shared memory is a big chunk of,
say N*sizeof(struct my_ringnode_st), then how can i assign the next
block of memory for a new ringnode object?
any response would be much appreciated
Jim
| |
| Ian Collins 2007-02-25, 7:06 pm |
| queengambit wrote:
> Hi people, as the subject title already says I've got trouble with how
> to use a linked list in a shared memory between processes. More
> specific, initially my linked list would be NULL and it is a doubly
> circular linked list. Here is the structure of any element in the
> linked list:
>
> typedef struct my_ringnode_st my_ringnode_t;
>
> struct my_ringnode_st {
> my_ringnode_t *next;
> my_ringnode_t *prev;
> };
>
> I would like my linked list to be able to shrink/expand without
> running into the coredumb/memory violation. Having looked at other
> posts, i know that i have to use offset instead of pointers 'next' &
> 'prev' to refer to next and previous elements of the linked list; but
> still i'm still about how to do that, what size initially my
> shared memory should be and if the my shared memory is a big chunk of,
> say N*sizeof(struct my_ringnode_st), then how can i assign the next
> block of memory for a new ringnode object?
>
If you can use a fixed mapping address in each process, next and prev
will work. Otherwise you have to store the offset form the base of the
memory segment.
The segment has to be big enough to meet your expected maximum list
size, which will depend the size of the objects you intend to save in
the list.
You will have to provide your own allocation and deallocation routines
(malloc/free replacements) to manage the shared memory.
--
Ian Collins.
| |
| Bin Chen 2007-02-25, 7:06 pm |
| On Feb 26, 7:14 am, "queengambit" <cbp...@cs.york.ac.uk> wrote:
> Hi people, as the subject title already says I've got trouble with how
> to use a linked list in a shared memory between processes. More
> specific, initially my linked list would be NULL and it is a doubly
> circular linked list. Here is the structure of any element in the
> linked list:
>
> typedef struct my_ringnode_st my_ringnode_t;
>
> struct my_ringnode_st {
> my_ringnode_t *next;
> my_ringnode_t *prev;
>
> };
>
> I would like my linked list to be able to shrink/expand without
> running into the coredumb/memory violation. Having looked at other
> posts, i know that i have to use offset instead of pointers 'next' &
> 'prev' to refer to next and previous elements of the linked list; but
> still i'm still about how to do that, what size initially my
> shared memory should be and if the my shared memory is a big chunk of,
> say N*sizeof(struct my_ringnode_st), then how can i assign the next
> block of memory for a new ringnode object?
>
> any response would be much appreciated
>
> Jim
What you can do simply is replace the direct addressing using '->'
with a function or a macro, such as:
LINK_NEXT(b)
In this macro you manipulate the address using the prior memorized
base address.
| |
| queengambit 2007-02-26, 4:12 am |
| Good morning Ian, Bin,
I don't think mapping the shared memory to processes at exactly the
same address a good idea as in my wrapper (which is what i have to
write) users are allowed to 'exec' after 'fork'. The method sounds
good is using offset.
ok, let say i already do the following:
struct my_ringnode_st {
my_ringnode_t *next;
my_ringnode_t *prev;
int my_offset[PTHREAD_THREADS_MAX]; /* for offset to nex and prev
elements */
};
shm_unlink(shm_name);
fd = shm_open(mm_name, O_RDWR | O_CREAT | O_EXCL, S_IRWXU);
if (fd ==-1)
perror("error opening file for read and write");
/*set size of the my_shared memory object to sizeof(struct
my_ringnode_st) */
ftruncate(fd, PTHREAD_THREADS_MAX*sizeof(struct my_ringnode_st));
/*in parent */
ptr1 = mmap(NULL, PTHREAD_THREADS_MAX*sizeof(struct my_ringnode_st),
PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
if (ptr == MAP_FAILED)
{
perror("error mapping the file");
exit(EXIT_FAILURE);
}
/*in child */
ptr2 = ... /* same as parent */
With child, ptr2 = child_base_addr. Now if i want to add a new element
to the linked list in child, which is initially NULL , what do i have
to do? What i'm really is how to allocate new block of space
from the shared memory for the new element of the linked list and how
offset works
thank you
| |
| Ian Collins 2007-02-26, 4:12 am |
| queengambit wrote:
> Good morning Ian, Bin,
> I don't think mapping the shared memory to processes at exactly the
> same address a good idea as in my wrapper (which is what i have to
> write) users are allowed to 'exec' after 'fork'. The method sounds
> good is using offset.
The segment could be mapped with MAP_FIXED.
>
> With child, ptr2 = child_base_addr. Now if i want to add a new element
> to the linked list in child, which is initially NULL , what do i have
> to do? What i'm really is how to allocate new block of space
> from the shared memory for the new element of the linked list and how
> offset works
>
As I said, you have to write an allocator for items that are added to
your list, think of it as malloc and free for the list objects. If the
items in the list are all the same size, this is simple (you can
consider the shared memory as an array of objects), if not it gets a
little harder.
In the list, you could use the difference in the addresses of the list
items as net and prev so node+next = address of next node and node-prev
= address of previous node.
--
Ian Collins.
| |
| Casper H.S. Dik 2007-02-26, 8:07 am |
| Ian Collins <ian-news@hotmail.com> writes:
>queengambit wrote:
[color=darkred]
>The segment could be mapped with MAP_FIXED.
Dangerous, because you might accidentily map on top of something else.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
| |
| Bin Chen 2007-02-26, 8:07 am |
| On 2=D4=C226=C8=D5, =CF=C2=CE=E74=CA=B136=B7=D6, "queengambit" <cbp...@cs.y=
ork.ac.uk> wrote:
> Good morning Ian, Bin,
> I don't think mapping the shared memory to processes at exactly the
> same address a good idea as in my wrapper (which is what i have to
> write) users are allowed to 'exec' after 'fork'. The method sounds
> good is using offset.
> ok, let say i already do the following:
>
> struct my_ringnode_st {
> my_ringnode_t *next;
> my_ringnode_t *prev;
> int my_offset[PTHREAD_THREADS_MAX]; /* for offset to nex and prev
> elements */
> };
>
> shm_unlink(shm_name);
> fd =3D shm_open(mm_name, O_RDWR | O_CREAT | O_EXCL, S_IRWXU);
> if (fd =3D=3D-1)
> perror("error opening file for read and write");
>
> /*set size of the my_shared memory object to sizeof(struct
> my_ringnode_st) */
> ftruncate(fd, PTHREAD_THREADS_MAX*sizeof(struct my_ringnode_st));
>
> /*in parent */
> ptr1 =3D mmap(NULL, PTHREAD_THREADS_MAX*sizeof(struct my_ringnode_st),
> PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
> if (ptr =3D=3D MAP_FAILED)
> {
> perror("error mapping the file");
> exit(EXIT_FAILURE);
> }
>
> /*in child */
> ptr2 =3D ... /* same as parent */
>
> With child, ptr2 =3D child_base_addr. Now if i want to add a new element
> to the linked list in child, which is initially NULL , what do i have
> to do? What i'm really is how to allocate new block of space
> from the shared memory for the new element of the linked list and how
> offset works
>
> thank you
You need to write a simple allocator that ensures what memory you
allocated for the list are within the range of the mmap'd range.
Otherwise, you can't share the pointer between the parent and
child(multi-process).
| |
| queengambit 2007-02-26, 7:08 pm |
| I'm sorry but i can't think of even a simple way to implement my own
allocator & deallocator working on shared memory with items in the
linked list are of the same size sizeof(struct my_ringnode_st).
I thought of defining a new struct with two arrays, one for holding
offset in shared memory of each item of the linked list and the other
for the actual items. The problem with this approach is how to keep
track of free slots in the second array so that new item can be
allocated as any item can be removed from the linked list.
struct my_shm{
long ringnode_off[PTHREAD_THREADS_MAX];
my_ringnode_t ringnodes_array[PTHREAD_THREADS_MAX*size
of(struct
my_ringnode_st)]
}
Please advise me on how to implement the allocator/deallocator for my
shared memory of linked list.
Thank you
| |
| Casper H.S. Dik 2007-02-26, 7:08 pm |
| "queengambit" <cbp500@cs.york.ac.uk> writes:
>I thought of defining a new struct with two arrays, one for holding
>offset in shared memory of each item of the linked list and the other
>for the actual items. The problem with this approach is how to keep
>track of free slots in the second array so that new item can be
>allocated as any item can be removed from the linked list.
I'd suggest doing it simpler and just allocating an array of your
structures in the shared memory.
struct mystruct *myarray = <address of start of shmem>
Then, rather than using pointers to entries, use integer indices 1 .. N.
The initial allocating would put all those entries on a single
free list, e.g., of the "next" field of the initial node which
would be reserved as the free list pointer (and this allows you
to use index 0 as NULL as index 0 would be invalid)
(You'd need N+1 structures allocated)
Casper
| |
| Ian Collins 2007-02-26, 7:08 pm |
| Casper H.S. Dik wrote:
> Ian Collins <ian-news@hotmail.com> writes:
>
>
>
>
>
>
> Dangerous, because you might accidentily map on top of something else.
>
I agree, use with great care but still worth investigating.
--
Ian Collins.
| |
| Bin Chen 2007-02-27, 8:07 am |
| On 2=D4=C227=C8=D5, =C9=CF=CE=E712=CA=B103=B7=D6, "queengambit" <cbp...@cs.=
york.ac.uk> wrote:
> I'm sorry but i can't think of even a simple way to implement my own
> allocator & deallocator working on shared memory with items in the
> linked list are of the same size sizeof(struct my_ringnode_st).
Use an array to do the management, you can refer to:
https://gro.clinux.org/scm/cvsweb.p...m/memory.c?rev=
=3D1.3&contenttype=3Dtext/plain&cvsroot=3Dlingix
>
> I thought of defining a new struct with two arrays, one for holding
> offset in shared memory of each item of the linked list and the other
> for the actual items. The problem with this approach is how to keep
> track of free slots in the second array so that new item can be
> allocated as any item can be removed from the linked list.
>
> struct my_shm{
> long ringnode_off[PTHREAD_THREADS_MAX];
> my_ringnode_t ringnodes_array[PTHREAD_THREADS_MAX*size
of(struct
> my_ringnode_st)]}
>
> Please advise me on how to implement the allocator/deallocator for my
> shared memory of linked list.
>
> Thank you
| |
| Bin Chen 2007-02-27, 8:07 am |
| On 2=D4=C227=C8=D5, =CF=C2=CE=E78=CA=B109=B7=D6, "Bin Chen" <binary.c...@gm=
ail.com> wrote:
> On 2=D4=C227=C8=D5, =C9=CF=CE=E712=CA=B103=B7=D6, "queengambit" <cbp...@c=
s=2Eyork.ac.uk> wrote:
>
>
> Use an array to do the management, you can refer to:
>
> https://gro.clinux.org/scm/cvsweb.p...ix/mm/memory...
>
BTW: This is done when I was a college student and have many defects,
just for illustration purpose, don't laugh at it.[color=darkred]
>
>
>
>
>
|
|
|
|
|