Why does my "linked list" apparently step on other memory?

[Bill Reid]

I was stupidly fooling around over the weekend converting some
code I wrote a long time ago for a database schema into something
more like a "linked list" or actually a linked "tree". Everything seemed
to work OK, such as traversing the tree from any branch and
from any node, EXCEPT for some reason the "tree" memory,
which is currently a contiguously allocated ordered block during
database initialization, is apparently over-writing another
contiguously allocated block in the same schema structure,
which is messing up a few descriptive strings in weird and
varying ways.

Here's how I declared the offending database "linked" node:

struct DB_Node {
struct DB_Node *parent;
struct DB_Node *child;
struct DB_Node *previous;
struct DB_Node *next;
struct DB_Category *category;
unsigned order;
};

I mean, this is perfectly legal, right? The strange thing is that if
I rearrange the structure elements I get different results, but always
in some way some strings in the *category block, which is allocated
completely separately and written with strings at an earlier point, get
screwed up at some point as I assign each node values for *previous,
etc., either NULL or the address of the "linked" node, based on an
initialization file. The *category strings are either missing, or contain
garbage, depending on the number of nodes initialized AND the order
of the DB_Node structure elements.

Does this ring any immediate bells for anybody, something
fundamental I'm missing? Like I say, the "linked tree" itself
apparently works fine for traversing, etc., but when I display
the schema some of the descriptive strings are messed up
or just plain missing, and I've localized the problem to
an area in the node initialization loop...

 

[Julienne Walker]

Here's how I declared the offending database "linked" node:

struct DB_Node {
struct DB_Node *parent;
struct DB_Node *child;
struct DB_Node *previous;
struct DB_Node *next;
struct DB_Category *category;
unsigned order;
};

I mean, this is perfectly legal, right? The strange thing is that if
I rearrange the structure elements I get different results, but always
in some way some strings in the *category block, which is allocated
completely separately and written with strings at an earlier point, get
screwed up at some point as I assign each node values for *previous,
etc., either NULL or the address of the "linked" node, based on an
initialization file. The *category strings are either missing, or contain
garbage, depending on the number of nodes initialized AND the order
of the DB_Node structure elements.

Your problem suggests overflow. Somewhere you're writing to a place
that shouldn't be written to (or writing more than the memory can
hold) and you overflow into category, corrupting the data already
there. Check your boundaries, check your addresses, and verify that
you're writing to the expected places.

 

[Mark Bluemel]

I was stupidly fooling around over the weekend converting some
code I wrote a long time ago for a database schema into something
more like a "linked list" or actually a linked "tree". Everything seemed
to work OK, such as traversing the tree from any branch and
from any node, EXCEPT for some reason the "tree" memory,
which is currently a contiguously allocated ordered block during
database initialization, is apparently over-writing another
contiguously allocated block in the same schema structure,
which is messing up a few descriptive strings in weird and
varying ways.

Here's how I declared the offending database "linked" node:

struct DB_Node {
struct DB_Node *parent;
struct DB_Node *child;
struct DB_Node *previous;
struct DB_Node *next;
struct DB_Category *category;
unsigned order;
};

[snip]
You haven't given us _anything like_ enough to really go on.

Could you reduce the problem to something self-contained that you can post?

 

[Tor Rustad]

I was stupidly fooling around over the weekend converting some
code I wrote a long time ago for a database schema into something
more like a "linked list" or actually a linked "tree". Everything seemed
to work OK, such as traversing the tree from any branch and
from any node, EXCEPT for some reason the "tree" memory,
which is currently a contiguously allocated ordered block during
database initialization, is apparently over-writing another
contiguously allocated block in the same schema structure,
which is messing up a few descriptive strings in weird and
varying ways.

Here's how I declared the offending database "linked" node:

struct DB_Node {
struct DB_Node *parent;
struct DB_Node *child;
struct DB_Node *previous;
struct DB_Node *next;
struct DB_Category *category;
unsigned order;
};

I mean, this is perfectly legal, right?

Yes. You most likely have corrupted the malloc arena. I just gave some
practical advice in another thread on this. Here, I can add another trick:

struct DB_Node
{
unsigned magic; /* = 0xDEAD or 0xBEAF */
struct DB_Node *parent;
struct DB_Node *child;
struct DB_Node *previous;
struct DB_Node *next;
struct DB_Category *category;
unsigned order;
};

so valid nodes, get magic set to 0xBEAF, while deallocated nodes has
magic equal to 0xDEAD. By using NDEBUG, all magic work can be removed on
release builds.

Now, on entry & on exit for each node relevant function, you can add this:

void foo (struct DB_Node *node)
{
assert(node->magic == 0xBEAF);
....
assert(node->magic == 0xBEAF);
}


I bet you will locate your problem afterwards.

 

[Ben Pfaff]

I was stupidly fooling around over the weekend converting some
code I wrote a long time ago for a database schema into something
more like a "linked list" or actually a linked "tree". Everything seemed
to work OK, such as traversing the tree from any branch and
from any node, EXCEPT for some reason the "tree" memory,
which is currently a contiguously allocated ordered block during
database initialization, is apparently over-writing another
contiguously allocated block in the same schema structure,
which is messing up a few descriptive strings in weird and
varying ways.

Your declaration looks fine. Probably you're writing to freed
memory, or writing through a wild pointer, or some other kind of
problem in that category. I'd suggest using a memory debugger:
Valgrind, Electric Fence, Bounds Checker, etc.

 

[Bill Reid]

Your problem suggests overflow. Somewhere you're writing to a place
that shouldn't be written to (or writing more than the memory can
hold) and you overflow into category, corrupting the data already
there. Check your boundaries, check your addresses, and verify that
you're writing to the expected places.

Well, of course this is the correct answer, as we all know. And
after taking a break from my marathon Sunday night coding session,
I quickly noticed that I was allocating the memory for the nodes
block BEFORE I read the initialization file value for the number of
nodes, so was using the default of one (single-node database).
I had moved a bunch of stuff around the initialization loop because
much of it is irrelevant unless there is more than one node,
and orphaned the nodes block malloc where it shouldn't have
been. Then as the loop initialized the several nodes that were
actually in the database, incrementing the node pointer each loop,
the node values were written all over the previously-initialized
categories memory as luck would have it (for a larger database,
I might have managed an exception!).

I put the nodes malloc back where it belonged, and everything is
working fine...sorry for the stupid question, I just thought there might
be some hidden gotcha behind linked-list coding that I didn't know
about...