OK, I'm stumped, couldn't free string pointer list...

[Bill Reid]

Now I can, because I just figured out my error, but now I'm
more confused than usual, because I just don't get why my
code was working at all but I couldn't free the list...here's
the story, maybe somebody can explain this behavior...

In my never-ending quest to mess up my code in an attempt to
speed it up by 0.00005%, I recently tried a different way to sort
some fairly big lists of strings (up to 100,000 strings or even more).

I wanted to sort a buffer full of these null-terminated strings
by alpha order of "substrings" at certain locations in the strings.
So I generated a list of pointers to the strings in the buffer and
a function to sort the substrings and reorder the list using
qsort().

Everything worked great, it was measureably a quicker way to
sort through these strings than I was using before, but there's
just one tiny little problem: I got an exception when I tried to free
the list of string pointers!

I'm declaring my list of string pointers as "char **", allocating
the list based on the count of newlines running through a text
file buffer finding each newline and replacing it with a NUL
terminator while I add a pointer to the start of the string to
each incremented position in the list. Then I sort the list of
pointers based on substrings and can then perform various
search and other operations on the reordered list. Again,
all of this stuff worked FINE, but when I went to free the
list, BLAMMO!!!

The list pointer was fine before, during, and after all the
operations, but the problem was the fact that I forgot to
multiply the number of strings by "sizeof(char *)" when I
allocated the list originally. So I guess I was not getting a
list the size of "pointers to char" but the size of "char", right?

So my question would be: how the hell did my code work
fine with that type of error? Isn't a "pointer to char" a much
bigger size than "char", so how did the list successfully
hold and increment and sort through the pointers? And
then why the hell would it only fail to FREE the list?

ANSWER ME, DAMMIT!!!

 

[vippstar]

So my question would be: how the hell did my code work
fine with that type of error? Isn't a "pointer to char" a much
bigger size than "char", so how did the list successfully
hold and increment and sort through the pointers? And
then why the hell would it only fail to FREE the list?

ANSWER ME, DAMMIT!!!

Undefined behavior most likely.
Post your code if you want to be sure.

 

[Jens Thoms Toerring]

I wanted to sort a buffer full of these null-terminated strings
by alpha order of "substrings" at certain locations in the strings.
So I generated a list of pointers to the strings in the buffer and
a function to sort the substrings and reorder the list using
qsort().

Everything worked great, it was measureably a quicker way to
sort through these strings than I was using before, but there's
just one tiny little problem: I got an exception when I tried to free
the list of string pointers!

I'm declaring my list of string pointers as "char **",

Sounds ok.

allocating
the list based on the count of newlines running through a text
file buffer

What exactly is a "text file buffer"?

finding each newline and replacing it with a NUL
terminator

So you had read the file before into a buffer?

while I add a pointer to the start of the string to
each incremented position in the list. Then I sort the list of
pointers based on substrings and can then perform various
search and other operations on the reordered list. Again,
all of this stuff worked FINE, but when I went to free the
list, BLAMMO!!!

The list pointer was fine before, during, and after all the
operations, but the problem was the fact that I forgot to
multiply the number of strings by "sizeof(char *)" when I
allocated the list originally. So I guess I was not getting a
list the size of "pointers to char" but the size of "char", right?

Sounds very much like that, assuming that your analysis is
correct. Since you show no code that's all here to go by.

So my question would be: how the hell did my code work
fine with that type of error? Isn't a "pointer to char" a much
bigger size than "char", so how did the list successfully
hold and increment and sort through the pointers? And
then why the hell would it only fail to FREE the list?

ANSWER ME, DAMMIT!!!

Watch your language, there might be ladies;-)

Ok, welcome to the wonderful world of undefined behaviour.
If you write outside the area of a memory you allocated
literately everything can happen. You write over memory
you don't own but which may be in use by something else you
don't know about. It's like closing your eyes and driving
your car across the next crossing at full speed. Depending
on a lot of factors you could end up dead, badly hurt, with
a write-off but only minor injuries, a dead pedestrian or
arriving healthy and with no bruises to anybody or your car
on the other side of the crossing (or some other combination
of these scenarios). In the case of your program you probably
didn't write over any data that were of immediate importance
to its primary purpose but destroyed some data that were in
use by the functions for allocating and keeping track of
allocated memory - malloc() and friends also need some memory
to keep track of things and it isn't protected from your pro-
gram because those functions (including the memory they use)
are part of your program. So everything seemed to work until
you tried to free the memory - you put a booby-trap into your
program and then triggered it yourself.

Regards, Jens

 

[Bill Reid]

Undefined behavior most likely.
Post your code if you want to be sure.

Maybe, maybe not...you realize that's a hassle to pull it all together
out of several library and "unit test" files, and I already described the
situation pretty clearly.

In any event, at least part of the puzzle I guess I can answer
pretty easily. I guess I'm "allowed" to write way the hell outside
the bounds of my "block", and if I get "lucky" I won't step on
myself or anybody else so everything will work fine, even though
I'm using like 400,000 bytes instead of the 100,000 bytes I
accidentally malloced (based on my assumption that
"pointer to char" is four bytes rather than a single byte).

Since all of my accesses to the block are pointer increments
or qsort() memory shuffles of the correct size, all the assigning
and sorting and searching works OK.

That just leaves the question of why a "block" allocated for
100,000 bytes could not be freed after writing 400,000 bytes
to the block. The only requirement I see in the documentation
is that I pass free() a pointer previously allocated, and that's
what I did in all cases, so my thinking is that it would "free"
the 100,000 bytes no matter how much data I actually wrote.
It might be some system-specific memory protection scheme
that frankly doesn't make a lot of sense to me right now...but
I'm just glad the thing works because it REALLY speeds
things up and thus allow me to dramatically simplify some stuff
in my overall codebase...

 

[Keith Thompson]

Now I can, because I just figured out my error, but now I'm
more confused than usual, because I just don't get why my
code was working at all but I couldn't free the list...here's
the story, maybe somebody can explain this behavior... [...]
ANSWER ME, DAMMIT!!!

Ask politely, and I might.

 

[Bill Reid]

In the case of your program you probably
didn't write over any data that were of immediate importance
to its primary purpose but destroyed some data that were in
use by the functions for allocating and keeping track of
allocated memory - malloc() and friends also need some memory
to keep track of things and it isn't protected from your pro-
gram because those functions (including the memory they use)
are part of your program. So everything seemed to work until
you tried to free the memory - you put a booby-trap into your
program and then triggered it yourself.

Ah, yes <light bulb on>, that makes sense...I seem to remember
that malloc does put a little data somewhere near the block so it
knows how much to free, and in my case I guess that was at the
end of the block...thanks for the clarification...I can now proceed
to write more code with stupid undefined behavior...

 

[Jens Thoms Toerring]

I seem to remember that malloc does put a little data somewhere
near the block so it knows how much to free, and in my case I
guess that was at the end of the block...

And even that's not something you can rely on. A different imple-
mentation of malloc() and free() might handle things completely
different and your program might write over something else when
you write outside the area you own. In that case your program
could come crashing down e.g. if you call printf() (and in the
good old days, when programs could write everywhere in physical
memory, you could even have written over data used by the driver
for your harddisk and the next access to it my have re-formatted
it).
Regards, Jens

 

[Nick Keighley]

ANSWER ME, DAMMIT!!!

try asking in a civil fashion. Your problem is the Undefined Behaviour
on line 42.

 

[Antoninus Twink]

... snip ...

You have been PLONKED by most users here for your insufferable
attitudes. To all practical purposes, nobody heard you.

A claim that would be more credible if Bill hadn't received several
useful answers in this thread by the time you came along to wag your
finger.

 

[Kenny McCormack]

A claim that would be more credible if Bill hadn't received several
useful answers in this thread by the time you came along to wag your
finger.

CBF really is a loser, isn't he. He seems intent on establishing new
levels of loser-hood - every time he posts.

 

[Richard]

A claim that would be more credible if Bill hadn't received several
useful answers in this thread by the time you came along to wag your
finger.

LOL. Falconer really is a pretentious waste of space.

 

[Bill Reid]

CBF really is a loser, isn't he. He seems intent on establishing new
levels of loser-hood - every time he posts.

I don't know, I think you have to give this round of "The Biggest Loser"
to "troll zero", also known as "Heathfield".

Reason: he is now implying that I am in his "kill-file", although like
most Usenuts' "kill-files" it is probably imaginary. The thing is, I
did not attain this great honor until a few weeks ago when he made
a complete fool of himself claiming there was an imaginary "bug"
in some code I posted, even fighting with several other people who
pointed out that the code was perfectly legal syntax SPECIFICALLY
ALLOWED BY THE HALLOWED C "STANDARD" HE CLAIMS
TO BE SUCH A FRIGGIN' EXPERT ON.

After that, with no contribution from me other than asking him
in vain what the "bug" was, he apparently decided to start CLAIMING
I'm in his "kill-file" (of course, it is the dreaded "talking kill-file",
where
he continues to "flame" me for posts he CLAIMS he hasn't read). So
his criteria for a "kill-file" is apparently somebody who posts correct,
legal, STANDARD "C" code on the newsgroup!

Now THAT'S a TROLL, and THAT'S definitely a LOSER with a
capital "L"!!!