Advanced data structures

[Seebs]

excuseme if the question is trivial ... suppose we are in a hosted
environment with virtual memory management by the os. is it true that
malloc *never* returns NULL?

Probably not.

That said, you could go years of active software development and use without
ever seeing it happen.

-s

 

[Rui Maciel]

Yes, but for C programming memory management is not an
irrelevant detail.

If the author would have wanted to focus on how to do
it /without manual memory management/ he could have chosen
a language with a garbage collector, like Java, or - if it
had to be C-like - a C-like language with a garbage collector,
like C with the Boehm collector. But he had chosen to use C.

This is silly. The author provided examples to illustrate concepts. In order
to better communicate concepts it is better to focus on the meaningful details
instead of wasting time with secondary, irrelevant aspects which is safe to
assume that all potential readers are already very familiar with.

Moreover, if an author opts to present concepts through pseudo-code instead of C
code then his work will not be less valuable and even the author would not be
more open to criticism. Therefore, if using purely abstract languages is not a
sin nor a sign of incompetence then why should anyone complain that an author
used a real-world programming language while leaving out irrelevant and
secondary details?

Taking the possibility of a 0 result of malloc into account
is not what I deem to be a »sanity« test ...

Is that even relevant, particularly in this discussion?

... nor irrelevant for C programing.

I believe you don't quite get it. Let's put it in this way: if a C programmer
picks up a book entitled "Advanced data structures" and he doesn't find a single
validation on calls to malloc(), do you believe that the absence of those tests
will hinder his ability to learn any topic covered in that book? And do you
believe that the problem would also be there if the book's examples were in
pseudo-code instead of C?

And then the author /does not even discuss/ this problem.

Why should he? That's terribly basic stuff. It's usually covered extensively
right at the beginning of any introductory course. Why should the author waste
time with topics which clearly should be a prerequisite to pick up the book?
Should the author also waste time discussing some intricacies of using the
english language to communicate with the reader?

It would not have been such a bad book, if he would have first
explained how to do proper memory management in C and then why
he will not use this in the rest of the book.

It's impressive how you are quick to label a book as being bad just because the
author chose to leave out such basic stuff, and therefore irrelevant and
meaningless due to the book's topic, out of it.

But he did not
mention this. Which gives the impression that he might not even be
aware of it.

If the author doesn't mention computers will that give you the impression that
he might not even be aware they exist?

I agree that the author of "Advance Data Structures" should
have read a book on basic C programming.

It appears that you are far too keen to quickly accuse someone as being
incompetent.


Rui Maciel

 

[Eric Sosman]

Stefan Ram ha scritto:

excuseme if the question is trivial ... suppose we are in a hosted
environment with virtual memory management by the os. is it true that
malloc *never* returns NULL?

A moment's thought will show that every malloc() must
eventually return NULL (or die catastrophically, failing to
conform to its specification). Consider: A non-NULL value
returned by malloc() must be distinct from all other values
it has returned, if those allocated blocks have not been
released. sizeof(void*) is finite, hence void* has only a
finite number of possible distinct values (at least one of
which is equal to NULL). If there are N possible void*
values and you call malloc(1) N times, at least one of those
calls (usually far more than one) must return NULL.

 

[Rui Maciel]

Yes, this question is exactly what the author of such
a book should discuss! In the case of the book given,
he missed to do this.

That's your opinion, which you are free to have and express. Yet, it doesn't
make it right, let alone an absolute truth.

When implementing data structures in C, the implementation
needs to have a documented policy towards run-time errors.

I believe this is exactly where you fail to understand the issue. The source
code snippets aren't supposed to be real world implementations of those data
structures. They are nothing more than small examples that are used to simply
illustrate the subjects being discussed. They aren't there to be picked up,
transcribed to a text file and slapped into a project tree. If the author had
intended to do that then he wouldn't have wasted his time writing a book. He
would've been writing libraries for his data structures.

On the other hand, if you intend to write a book covering an advanced subject
then what you will do is provide small examples in the form of code snippets in
order to better illustrate the subjects you have been discussing. Those code
snippets will be straight to the point and you will omit irrelevant, secondary
details in order to efficiently convey your ideas. And that's what has been
done.

Authors of such implementations need to be aware of the
different options.

What leads you to believe they aren't?

This is not beginner's material.

....which makes it safe to assume that the author doesn't need to waste his time
covering beginner's subjects, such as validating calls to malloc().

This is
hard. Beginner's material is implementing data structures
and ignoring this question.

....which only happens if the reader doesn't know how to code in C to begin with
and therefore should be reading an introductory C book before picking up books
targeted at a more knowledgeable readership.


Rui Maciel

 

[Keith Thompson]

Stefan Ram a écrit :

Yes it is. If malloc fails, the program crashes. So what?

That's a correct behavior for a sample program!

[...]

How do you know it crashes?

The glibc implementation of printf's "%s" format prints the string
"(null)" given a null pointer. I've seen people here advocate
"friendly" handling of null pointers for other functions as well,
such as treating a null pointer as equivalent to a pointer to an
empty string. Misusing a null pointer gives you undefined behavior.
A crash is the most common behavior, but not the only possibility.

I can understand leaving out checking in a sample program, but
there needs to be some mention of the need for it in the real world.
(I'm not even sure what book we're talking about; I'm just making
a general point.)

 

[Kaz Kylheku]

Stefan Ram ha scritto:

excuseme if the question is trivial ... suppose we are in a hosted
environment with virtual memory management by the os. is it true that
malloc *never* returns NULL?

What do you conclude from the following observations?

1. malloc returns a fixed-size pointer with a finite number of bits
in its representation, giving rise to an upper bound on the number
of unique values it can hold.

The number of bits in void * is CHAR_BIT * sizeof(void *).
Not all of these may be value-contributing,b ut that is the upper
bound on the number of value-contributing bits. (We just care
about the existence of an upper bound, not what it is).

An upper bound on the number of bits means an upper bound on the
number of distinct values, which is given by pow(2, bits).

Thus the void * pointer type can only represent so many distinct
values.

2. malloc returns either null, or a unique address: a new object
that is different from any other live object in the program.

In light of 1 and 2, can malloc keep producing objects indefinitely?

 

[Nick]

A moment's thought will show that every malloc() must
eventually return NULL (or die catastrophically, failing to
conform to its specification). Consider: A non-NULL value
returned by malloc() must be distinct from all other values
it has returned, if those allocated blocks have not been
released. sizeof(void*) is finite, hence void* has only a
finite number of possible distinct values (at least one of
which is equal to NULL). If there are N possible void*
values and you call malloc(1) N times, at least one of those
calls (usually far more than one) must return NULL.

Not if the operating system kills your process first! Which is what can
happen.

 

[Willem]

Kaz Kylheku wrote:
) What do you conclude from the following observations?
)
) 1. malloc returns a fixed-size pointer with a finite number of bits
) in its representation, giving rise to an upper bound on the number
) of unique values it can hold.
)
) The number of bits in void * is CHAR_BIT * sizeof(void *).
) Not all of these may be value-contributing,b ut that is the upper
) bound on the number of value-contributing bits. (We just care
) about the existence of an upper bound, not what it is).
)
) An upper bound on the number of bits means an upper bound on the
) number of distinct values, which is given by pow(2, bits).
)
) Thus the void * pointer type can only represent so many distinct
) values.
)
) 2. malloc returns either null, or a unique address: a new object
) that is different from any other live object in the program.
)
) In light of 1 and 2, can malloc keep producing objects indefinitely?

Yes, in the opposite vein of the hare being unable to overtake the
tortoise.

You see, assuming the computer slows down after each malloc() call,
you could conjecture that it would take an infinite time to process
a finite amount of malloc() calls, and that that finite amount is
small enough that all of them will succeed even in light of the
observations above.

Or, in tech terms: The computer will grind to a halt long before
the malloc() calls start failing.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Eric Sosman]

Stefan Ram ha scritto:
and unencumbered by those long, tedious series of sanity tests, which
are pretty

Taking the possibility of a 0 result of malloc into account
is not what I deem to be a »sanity« test ...

excuseme if the question is trivial ... suppose we are in a hosted
environment with virtual memory management by the os. is it true that
malloc *never* returns NULL?

A moment's thought will show that every malloc() must
eventually return NULL (or die catastrophically, failing to
conform to its specification). [...]

Not if the operating system kills your process first! Which is what can
happen.

That falls under "die catastrophically." If a call to
malloc() terminates the program, malloc() has not behaved as
the Standard requires.

 

[gwowen]

  Yes, this question is exactly what the author of such
  a book should discuss! In the case of the book given,
  he missed to do this.

It should be discussed. Failure to even discuss it is an oversight.
But *specific* error handling code *in the code samples* would not be
useful.

/* error handling goes here... */

would suffice. If you don't agree, please post code samples of what
generic, non-application specific error handling should look like.

 

[gwowen]

     That falls under "die catastrophically."  If a call to
malloc() terminates the program, malloc() has not behaved as
the Standard requires.

Well, under linux, a call to malloc() *in someone else's program* can
cause your program to die catastrophically, so I think looking to the
C standard for salvation here is not going to help you. One might as
well look in the C standard to see what happens when your six-year-old
pulss the power lead out.

 

[Nick Keighley]

Just curious where you think the problems of C++ are. Is it just too
big?

Dann Corbit a écrit :


Yes. The problem with C++ is in other parts of the language and
in its enormous complexity.

what are the other parts that cause problems? I always thought
templates were the really hairy part (and I've never liked their
syntax).

Templates are a good idea. You can
accomplish pretty much the same thing with a preprocessed text
file in C, that takes a template file and adapts it to the specific
data type given.

have you read "Modern C++ Design" by Alexandrescu? "Eye opening" isnt
the term, more like "eye watering".


<snip>

--

"If you think C++ is not overly complicated, just what is a protected
abstract virtual base pure virtual private destructor, and when
was the last time you needed one?"
-- Tom Cargil, C++ Journal.

 

[Nick Keighley]

  ``It is (now) widely recognized that this type-system computation language
  [of C++ templates] is simply an extraordinarily baroque functional language,
  full of /ad hoc/ coding tricks and conventions.''

Bingo!

oh. Is *that* what it is!

 

[Rui Maciel]

Well, under linux, a call to malloc() *in someone else's program* can
cause your program to die catastrophically

Is it possible to provide more info on this issue?


Rui Maciel

 

[Mark]

Well, under linux, a call to malloc() *in someone else's program* can
cause your program to die catastrophically, so I think looking to the
C standard for salvation here is not going to help you. One might as
well look in the C standard to see what happens when your six-year-old
pulss the power lead out.

Are you talking about your system getting sufficiently overloaded that,
with overcommit switched on (which it needn't be), it invokes the
oom-killer? Switching off overcommit will drastically reduce the
chances of this, of course.

But the call to malloc is not what has caused the process to die any
more than a six year old pulling the power lead is malloc's fault.

Or is it something else that you're thinking of.

 

[Ben Bacarisse]

Is it possible to provide more info on this issue?

Search for "OOM killer".

 

[gwowen]

But the call to malloc is not what has caused the process to die any
more than a six year old pulling the power lead is malloc's fault.

Well, the interaction between the libc's malloc(), sbrk(), mmap() and
any other language specific memory manipulation, and Linux's
overcommit causes the death, so memory allocation (if not malloc()) is
a contributory factor.

The point is, in some configurations, a perfect bug-free program can
be killed by the OOM killer, even if it never called malloc() in its
life. I'm not suggesting this is a terrible thing, just pointing out
to Eric that its way beyond the scope of the C standard (like the
notional six-year-old).

 

[gwowen]

Is it possible to provide more info on this issue?

I was thinking of the OOM killer. Actually, if I wanted to be
specific, its not the malloc() that triggers the OOM killer, but malloc
() followed by an attempt to use the allocated memory (and the
subsequent page fault) that might kill your program.

And this behaviour can be turned off.

As a side issue, it is easy to get malloc() to return NULL in 32-bit
Linux, simply request more memory than their is contiguous address
space available. 3GB will probably do it.

 

[Mark]

Well, the interaction between the libc's malloc(), sbrk(), mmap() and
any other language specific memory manipulation, and Linux's
overcommit causes the death, so memory allocation (if not malloc()) is
a contributory factor.

The point is, in some configurations, a perfect bug-free program can
be killed by the OOM killer, even if it never called malloc() in its
life. I'm not suggesting this is a terrible thing, just pointing out
to Eric that its way beyond the scope of the C standard (like the
notional six-year-old).

Sure. But nothing in any specification can prevent a bug-free program
from failing. Hardware faults, OS bugs, acts of god are all ways for a
bug-free program to fail, but there's nothing you can do to guarantee
things beyond a point.

I think, in the case of a hosted environment, you need to consider the
running program as running on it's own (virtual) machine*. Problems with
the host (OS, hardware, whatever) are no different to the issues listed
above and, therefore, nothing to do with the language or programs
written in that language.

Just my point of view.

* After all, that's almost the definition of a (good) modern operating
system; something that provides an environment which allows you to run
processes without having to pay attention to other processes also
running on the same system...except where you wish to, and then only
through appropriate, provided interfaces.

 

[gwowen]

Sure.

I'd love to argue with you, but I can't see anything on which we
disagree.

If you recall, I was merely commenting on Eric Sosman's comment, who
described the "calling malloc() kills my program" as a non-conformant
in malloc(). I observed that not calling malloc(), or anyone doing
anything that causes a page fault, can also kill your program, so
malloc() shouldn't be singled out as as non-conformant. An hosting OS
that kills processes (for whatever reason) is no more covered by the
standard than power-cuts. Its beyond its scope.