Problem with offset based linked list

[kalyan]

Hi,

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory. I run fedora 9 and gcc 4.2. I am able to insert values in to
the list, remove values from the list, but the problem is in
traversing the list. Atlease one or 2 list nodes disappear when
traversing from the base of the list or the shared memory.

PS: Don't get carried away because of PROC1 macro. It's just used to
compile the same code to two different processes one that creates,
inserts & destroys the list & creates & destroys shared memory & the
other one simply attaches to the shared memory and traverses the
linked list created by the process that is compiled using PROC1 macro
defined. So to compile:
gcc -g -O -D PROC1 proc1 shlist.c
gcc -g -O -o proc2 shlist.c

now proc1 creates shared memory & destroys it and also creates &
destroys linked list. Where as proc2 just attaches (and detaches
finally) to shared memory and just traverses the list and prints the
value in each list element.

Thanks.

Kalyan

Below is the complete code (shlist.c) :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/stat.h>

int open_shared_memory(key_t shm_key,size_t shm_sz);
void* attach_shared_memory(int shm_id);
void detach_shared_memory(const void *mem);
void destroy_shared_memory(int shm_id);

#define SHMEM_CREAT (IPC_CREAT|IPC_EXCL|0644)
#define SHMEM_OPEN (IPC_CREAT|0644)

int open_shared_memory(key_t shm_key,size_t shm_sz)
{
size_t shm_size = 1024;
int shm_id = -2; /*some invalid id number*/

if (shm_key == IPC_PRIVATE) abort();
if (shm_sz < 1024) {
fprintf(stderr,"Warning: Shared memory size is defaulted to 1024
bytes\n");
} else {
shm_size = shm_sz;
}

shm_id = shmget(shm_key,shm_size,SHMEM_CREAT);
if (shm_id == -1) {
shm_id = shmget(shm_key,shm_size,SHMEM_OPEN);
if (shm_id == -1) {
fprintf(stderr,"Unable to create/open shared memory with key value:
%lu\n",(unsigned long) shm_key);
fprintf(stderr,"Error occured is \"%s\"\n",strerror(errno));
return -1;
}
}
return shm_id;
}

void* attach_shared_memory(int shm_id)
{
void *mem = shmat(shm_id,NULL,0);
if (mem == (void *) -1) return NULL;
return mem;
}

void detach_shared_memory(const void *mem)
{
shmdt(mem);
}

void destroy_shared_memory(int shm_id)
{
shmctl(shm_id,IPC_RMID,(struct shmid_ds *) 0);
}
typedef long OffsetPtr;

extern unsigned char* base;

#define OFFSET_BASE(ptr) \
if (ptr != NULL) base = (unsigned char*) ptr;

#define GET_OFFSET(ptr) \
((long) ((unsigned char*) ptr - base))

#define GET_POINTER(off) \
((void*) (base + off))

#define IS_VALID_POINTER(ptr) \
(base < (unsigned char*) (ptr))
unsigned char* base = 0;

static int count = 0;

typedef struct {
int value;
OffsetPtr next;
} IntList;

void InitList(IntList *list);
void InsertHead(IntList *list,int value);
void RemoveHead(IntList *list,int *removedValue);
void DestroyList(IntList *list);

void InitList(IntList *list)
{
if (list == NULL || !list) return;
OFFSET_BASE(list);
list->next = -1;
list->value = 0;
}

void InsertHead(IntList *list,int value)
{
IntList *newList,*nnode;

if (list == NULL || !list) abort();

newList = (IntList *) (base + (count *sizeof(IntList)));

if (!newList || newList == NULL)
abort();

newList->value = value;
if (list->next == -1) newList->next = -1;
else newList->next = list->next;
list->next = GET_OFFSET(newList);
++count;
}

void RemoveHead(IntList *list,int *removedValue)
{
IntList *node,*nnode;
OffsetPtr next;

if (list == NULL || !list) return;

node = (IntList *) GET_POINTER(list->next);
nnode = (IntList *) GET_POINTER(node->next);
list->next = GET_OFFSET(nnode);
*removedValue = node->value;
node->next = -1;
--count;
}

void DestroyList(IntList *list)
{
int val;
while (list->next != -1)
{
RemoveHead(list,&val);
printf("Removed: %d\n",val);
}
list->next = -1;
}

int main(void)
{
IntList *myList;
IntList *node;
int i,val,shm_id;

shm_id = open_shared_memory(1511,4096);
if (shm_id == -1) return -errno;
base = attach_shared_memory(shm_id);
myList = (IntList *) base;
#ifdef PROC1
InitList(myList);
for (i = 0 ; i < 20; i++) {
printf("Inserting :%d\n",(i + 1));
InsertHead(myList,(i + 1));
}
#endif
node = (IntList *) base;
while (node->next)
{
printf("%d ",node->value);
node = (IntList *) GET_POINTER(node->next);
}
printf("\n");
#ifndef PROC1
detach_shared_memory((const void *) base);
#endif
#ifdef PROC1
printf("Press enter key to quit ...");
getchar();
DestroyList(myList);
myList->next = -1;
detach_shared_memory((const void *) base);
destroy_shared_memory(shm_id);
#endif
return 0;
}

[Ben Bacarisse]

kalyan <rk**********@gmail.comwrites:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.

I run fedora 9 and gcc 4.2. I am able to insert values in to
the list, remove values from the list, but the problem is in
traversing the list. Atlease one or 2 list nodes disappear when
traversing from the base of the list or the shared memory.

I think the problem is that you have tied yourself up using these
indexes. For example, in the first InsertHead operation, list and
newlist refer to the same place.

If you need to use indexes (not obvious yet) it is much simpler to
make base a pointer to an array of nodes and just index into it -- not
messy pointer arithmetic. Remove for a moment the shared memory stuff
and just write the code to add an remove elements from linked list
using a declared array of nodes. A debugger might help you see the
confusion you have over the first node.

Then, put the shared memory back in and you will be up and running.

<snip>

Below is the complete code (shlist.c) :

A few comments...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

<snip>

typedef long OffsetPtr;

extern unsigned char* base;

#define OFFSET_BASE(ptr) \
if (ptr != NULL) base = (unsigned char*) ptr;

#define GET_OFFSET(ptr) \
((long) ((unsigned char*) ptr - base))

#define GET_POINTER(off) \
((void*) (base + off))

Always fully parenthesise macro arguments: (ptr). I think all is well
but I have to check all the uses one by one to be sure. In fact,
while you are debugging, I'd write all these as functions.

#define IS_VALID_POINTER(ptr) \
(base < (unsigned char*) (ptr))
unsigned char* base = 0;

static int count = 0;

typedef struct {
int value;
OffsetPtr next;
} IntList;

Life would be easier if base were declared:

IntList *base;

so base[0], base[1] are the nodes.

void InitList(IntList *list);
void InsertHead(IntList *list,int value);
void RemoveHead(IntList *list,int *removedValue);
void DestroyList(IntList *list);

void InitList(IntList *list)
{
if (list == NULL || !list) return;

Either half of the || is enough. This confused me for a while!

OFFSET_BASE(list);
list->next = -1;
list->value = 0;
}

void InsertHead(IntList *list,int value)
{
IntList *newList,*nnode;

if (list == NULL || !list) abort();

newList = (IntList *) (base + (count *sizeof(IntList)));

if (!newList || newList == NULL)
abort();

newList->value = value;
if (list->next == -1) newList->next = -1;
else newList->next = list->next;

This if is just the same as: newList->next = list->next;

list->next = GET_OFFSET(newList);
++count;
}

<snip>

--
Ben.

[Jean-Marc Bourguet]

Ben Bacarisse <be********@bsb.me.ukwrites:

kalyan <rk**********@gmail.comwrites:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

Yours,

--
Jean-Marc

[kalyan]

On Aug 25, 6:19*pm, Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <[e-mail]:

kalyan <[e-mail]:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. *One you have a pointer it is a pointer.
No need for indexes. *If there some plan to cope with moving lists
from one place to another? *That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

Yours,

--
Jean-Marc

Hi Jean-Marc,

That's the reason why one needs to use offsets in place of pointers
when having linked lists in the shared memory?

Did you find any thing wrong in the code that I've posted? Especially
in the code that traverses the list.

Regards
kalyan

[Jean-Marc Bourguet]

kalyan <rk**********@gmail.comwrites:

Did you find any thing wrong in the code that I've posted? Especially
in the code that traverses the list.

I've marked the message so that I can come back later but I've some other
buggy code to look at for the moment :-(

Yours,

--
Jean-Marc

[Ben Bacarisse]

Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <be********@bsb.me.ukwrites:

>kalyan <rk**********@gmail.comwrites:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

You still don't need offsets. You need offsets (or something else) to
describe positions if the processes communicate about the memory. The
OP is free to use them if they are needed but nothing in the code
presented or the problem described did (unless I missed it).

--
Ben.

[Ben Bacarisse]

kalyan <rk**********@gmail.comwrites:

On Aug 25, 6:19Â*pm, Jean-Marc Bourguet <[e-mail]:

>Ben Bacarisse <[e-mail]:

kalyan <[e-mail]:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. Â*One you have a pointer it is a pointer.
No need for indexes. Â*If there some plan to cope with moving lists
from one place to another? Â*That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

Yours,

--
Jean-Marc

Best not to quote sigs.

Hi Jean-Marc,

That's the reason why one needs to use offsets in place of pointers
when having linked lists in the shared memory?

Did you find any thing wrong in the code that I've posted? Especially
in the code that traverses the list.

It is wrong too, but I think the main problem is in the building. If
you correct:

while (node->next)
{
printf("%d ",node->value);
node = (IntList *) GET_POINTER(node->next);
}

to:

node = (IntList *) base;
while (node)
{
printf("%d ",node->value);
if (node->next != -1)
node = (IntList *) GET_POINTER(node->next);
else node = NULL;
}

you will see that the list is circular which I don't think you intended.

--
Ben.

[Jean-Marc Bourguet]

Ben Bacarisse <be********@bsb.me.ukwrites:

Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <be********@bsb.me.ukwrites:

kalyan <rk**********@gmail.comwrites:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

You still don't need offsets. You need offsets (or something else) to
describe positions if the processes communicate about the memory. The
OP is free to use them if they are needed but nothing in the code
presented or the problem described did (unless I missed it).

I didn't even read the code :-) I assumed that he built the list in one
process and read it in the other, in which case if the shared memory is not
mapped in the same adress using pointers would be problematic.

Yours,

--
Jean-Marc

[Ben Bacarisse]

Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <be********@bsb.me.ukwrites:

>Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <be********@bsb.me.ukwrites:

kalyan <rk**********@gmail.comwrites:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

You still don't need offsets. You need offsets (or something else) to
describe positions if the processes communicate about the memory. The
OP is free to use them if they are needed but nothing in the code
presented or the problem described did (unless I missed it).

I didn't even read the code :-) I assumed that he built the list in one
process and read it in the other, in which case if the shared memory is not
mapped in the same adress using pointers would be problematic.

You are right. Because the errors are not related to the shared
memory I factored it out from the view of the code, but offsets are
needed. The reported errors show up (and can be fixed) in just one
process and are just C/logic errors (which I why I answered here rather
than redirecting to a *nix group).

--
Ben.

[Barry Schwarz]

On Mon, 25 Aug 2008 03:16:22 -0700 (PDT), kalyan
<rk**********@gmail.comwrote:

>Hi,

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory. I run fedora 9 and gcc 4.2. I am able to insert values in to
the list, remove values from the list, but the problem is in
traversing the list. Atlease one or 2 list nodes disappear when

It should be only one. See comment in print loop.

>traversing from the base of the list or the shared memory.

PS: Don't get carried away because of PROC1 macro. It's just used to
compile the same code to two different processes one that creates,
inserts & destroys the list & creates & destroys shared memory & the
other one simply attaches to the shared memory and traverses the
linked list created by the process that is compiled using PROC1 macro
defined. So to compile:
gcc -g -O -D PROC1 proc1 shlist.c
gcc -g -O -o proc2 shlist.c

now proc1 creates shared memory & destroys it and also creates &
destroys linked list. Where as proc2 just attaches (and detaches
finally) to shared memory and just traverses the list and prints the
value in each list element.

Which one fails?

>
Thanks.

Kalyan

Below is the complete code (shlist.c) :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/stat.h>

int open_shared_memory(key_t shm_key,size_t shm_sz);
void* attach_shared_memory(int shm_id);
void detach_shared_memory(const void *mem);
void destroy_shared_memory(int shm_id);

#define SHMEM_CREAT (IPC_CREAT|IPC_EXCL|0644)
#define SHMEM_OPEN (IPC_CREAT|0644)

int open_shared_memory(key_t shm_key,size_t shm_sz)
{
size_t shm_size = 1024;
int shm_id = -2; /*some invalid id number*/

if (shm_key == IPC_PRIVATE) abort();
if (shm_sz < 1024) {
fprintf(stderr,"Warning: Shared memory size is defaulted to 1024
bytes\n");

Magic numbers are the bane of maintenance. Life could be a lot
simpler in six months if you change these two statements to
if (shm_sz < shm_size) {
fprintf(stderr, "Warning: ... defaulted to %d bytes\n",
(int)shm_size);

snip

>
void destroy_shared_memory(int shm_id)
{
shmctl(shm_id,IPC_RMID,(struct shmid_ds *) 0);

If there is a prototype in scope for this function, the third argument
would be better as NULL. 0 cast to a type other than void* is not
guaranteed to be NULL.

>}
typedef long OffsetPtr;

extern unsigned char* base;

#define OFFSET_BASE(ptr) \
if (ptr != NULL) base = (unsigned char*) ptr;

#define GET_OFFSET(ptr) \
((long) ((unsigned char*) ptr - base))

#define GET_POINTER(off) \
((void*) (base + off))

#define IS_VALID_POINTER(ptr) \
(base < (unsigned char*) (ptr))
unsigned char* base = 0;

static int count = 0;

typedef struct {
int value;
OffsetPtr next;

Since OffsetPtr is not a pointer type, this is a confusing name.

>} IntList;

void InitList(IntList *list);
void InsertHead(IntList *list,int value);
void RemoveHead(IntList *list,int *removedValue);
void DestroyList(IntList *list);

void InitList(IntList *list)
{
if (list == NULL || !list) return;

Is there some reason you think the two boolean expressions can ever
evaluate to different values?

> OFFSET_BASE(list);
list->next = -1;
list->value = 0;
}

void InsertHead(IntList *list,int value)
{
IntList *newList,*nnode;

if (list == NULL || !list) abort();

newList = (IntList *) (base + (count *sizeof(IntList)));

if (!newList || newList == NULL)

Can this if ever evaluate to true?

> abort();

newList->value = value;
if (list->next == -1) newList->next = -1;
else newList->next = list->next;
list->next = GET_OFFSET(newList);
++count;
}

void RemoveHead(IntList *list,int *removedValue)
{
IntList *node,*nnode;
OffsetPtr next;

if (list == NULL || !list) return;

node = (IntList *) GET_POINTER(list->next);

The cast serves no purpose.

> nnode = (IntList *) GET_POINTER(node->next);
list->next = GET_OFFSET(nnode);
*removedValue = node->value;
node->next = -1;
--count;
}

void DestroyList(IntList *list)
{
int val;
while (list->next != -1)
{
RemoveHead(list,&val);
printf("Removed: %d\n",val);
}
list->next = -1;
}

int main(void)
{
IntList *myList;
IntList *node;
int i,val,shm_id;

shm_id = open_shared_memory(1511,4096);
if (shm_id == -1) return -errno;
base = attach_shared_memory(shm_id);
myList = (IntList *) base;
#ifdef PROC1
InitList(myList);
for (i = 0 ; i < 20; i++) {
printf("Inserting :%d\n",(i + 1));
InsertHead(myList,(i + 1));
}
#endif
node = (IntList *) base;
while (node->next)

You probably want the test to read (node->next != -1). As it stands,
the loop stops when node->next is 0 but before it prints the value.
And an offset of 0 is valid. You may even need to change it to a
do{}while().

> {
printf("%d ",node->value);
node = (IntList *) GET_POINTER(node->next);
}
printf("\n");
#ifndef PROC1
detach_shared_memory((const void *) base);
#endif
#ifdef PROC1
printf("Press enter key to quit ...");
getchar();
DestroyList(myList);
myList->next = -1;
detach_shared_memory((const void *) base);
destroy_shared_memory(shm_id);
#endif
return 0;
}

--
Remove del for email

[kalyan]

On Aug 25, 7:58*pm, Ben Bacarisse <[e-mail]:

Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <[e-mail]:

Jean-Marc Bourguet <[e-mail]:

Ben Bacarisse <[e-mail]:

kalyan <[e-mail]:

I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset's instead on pointers to store the linked list in the shared
memory.

You don't need to do that. *One you have a pointer it is a pointer.
No need for indexes. *If there some plan to cope with moving lists
from one place to another? *That might need offsets.

Shared memory is not guaranteed to be at the same address in all process
mapping them; it's not moving but the effect is the same.

You still don't need offsets. *You need offsets (or something else) to
describe positions if the processes communicate about the memory. *The
OP is free to use them if they are needed but nothing in the code
presented or the problem described did (unless I missed it).

I didn't even read the code :-) I assumed that he built the list in one
process and read it in the other, in which case if the shared memory isnot
mapped in the same adress using pointers would be problematic.

You are right. *Because the errors are not related to the shared
memory I factored it out from the view of the code, but offsets are
needed. *The reported errors show up (and can be fixed) in just one
process and are just C/logic errors (which I why I answered here rather
than redirecting to a *nix group).

--
Ben.

Ben,

What errors got reported? Did you use any compiler switches to get
compiler warnings?
I didn't want my list to be circular, but want to stop when the offset
is -1. As I said in my first posting above, I used PROC1 macro to
compile the process in to two separate processes. The process that
compiled with macro PROC1 will create, destroy the linked lists and
the shared memory. The process that is created without defining PROC1
macro will simply attach to the shared memory and prints the values by
traversing. I hope in this case using offset is the right solution
instead of using pointers right?

Thanks for responding and I appreciate your time spent on this. Please
clarify the above.

Thanks & Regards
Kalyan

[jameskuyper]

Barry Schwarz wrote:

On Mon, 25 Aug 2008 03:16:22 -0700 (PDT), kalyan
<rk**********@gmail.comwrote:

....

void destroy_shared_memory(int shm_id)
{
shmctl(shm_id,IPC_RMID,(struct shmid_ds *) 0);

If there is a prototype in scope for this function, the third argument
would be better as NULL. 0 cast to a type other than void* is not
guaranteed to be NULL.

Being "An integer constant express with the value 0" is one of the two
different ways listed in the standard in which something can qualify
as a null pointer constant (NPC); the integer literal "0" certainly
qualifies. Any NPC converted to a pointer type results in a null
pointer, so (struct shmid_ds*)0 certainly qualifies . See section
6.3.2.2.p3.

On the other hand, you're technically correct - the null pointer
(struct shmid_ds*)0 is certainly not NULL. NULL is a macro whose
expansion is required to be an NPC. However, the third argument of
shmctl() is only required to be a null pointer, it's not required to
be an NPC. In this context, you should have been referring to "null",
which is an adjective, rather than "NULL", which is the name of a
macro.

[Ben Bacarisse]

kalyan <rk**********@gmail.comwrites:

<snip>

>--
Ben.

It is best not to quote sig blocks.

What errors got reported? Did you use any compiler switches to get
compiler warnings?

No, by error I just mean something wrong with the logic of the
program.

I didn't want my list to be circular, but want to stop when the offset
is -1.

I thought not, but I think you make it circular.

As I said in my first posting above, I used PROC1 macro to
compile the process in to two separate processes. The process that
compiled with macro PROC1 will create, destroy the linked lists and
the shared memory. The process that is created without defining PROC1
macro will simply attach to the shared memory and prints the values by
traversing.

Forget all that -- it is probably OK and is off-topic here anyway.
Just look at the code that builds the list. Follow through what your
code does with the first node (it that that causes it to be circular
by accident).

You then need to correct the loop that runs thought it -- I posted the
code to correct that.

I hope in this case using offset is the right solution
instead of using pointers right?

Yes, I think so, though if a linked list is the right thing to build
in shared memory is another matter.

Since you need offsets of some sort I really think you should make the
base point a pointer to a node and treat it like an array. The
offsets are then just indexes into an array of nodes. That way you
won't need all the messy code in the macros.

--
Ben.