Advanced data structures

[Eric Sosman]

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.

... and having looked, you'll find that the Standard has
an answer: The implementation ceases to conform.

Whether that counts as "salvation" or not is a question
I'll leave to the scum who use loaded words gratuitously.

 

[Stefan Ram]

As a meta comment, many otherwise valuable contributors to this

I would like to bring the attention of readers to the point
that "malloc" to me merely was an /example/ for a resource
allocation attempt.

I can assume for a moment that malloc will never return 0.

Still, there are other similar cases:

For example, file access:

FILE * const f = fopen( "alpha", "r" );

For example, using a third-party library function, like:

list_init( list );

It will return a nonzero-value in the case of an error and
one might/should dispose the list eventually using »list_destroy«.

Thus, we have attempt operations:

malloc
fopen
list_init
...

And release operations:

free
fclose
list_destroy
...

Even, if we could remove the pair malloc/free from this list,
all the other entries would still remain.

I do not know the book »Advance Data Structures«, but when
it teaches programming, it should certainly teach hiding
implementations of data structures behind an interface:

In the moment one has an interface for data structures,
one often has functions that will return run-time error codes.

For example, see

http://mij.oltrelinux.com/devel/simclist/simclist.h

. Thus, one need to teach how to handle such error codes anyways,
even assuming that malloc will never return 0.

 

[Mark]

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.

Sure - I think we are in complete agreement.

 

[Keith Thompson]

salvation: n
1. the act of preserving or the state of being preserved from harm
2. a person or thing that is the means of preserving from harm

There are also some religious meanings, but they're not listed first in
any dictionary I own. Still, if that's what you consider a loaded word.

Still, apparently I'm scum because you have a poor vocabulary.

Am I the only one who got Eric's joke? He was gratuitously using
the loaded word "scum" while complaining about "the scum who use
loaded words gratuitously". If certain other posters had said the
same thing, I would just think they're being hypocrites, but I'm
sure Eric did it intentionally and with humorous intent.

(Or maybe you're just going along with the joke and I'm demonstrating
my own lack of humor.)

 

[Eric Sosman]

Am I the only one who got Eric's joke? He was gratuitously using
the loaded word "scum" while complaining about "the scum who use
loaded words gratuitously". If certain other posters had said the
same thing, I would just think they're being hypocrites, but I'm
sure Eric did it intentionally and with humorous intent.

(Or maybe you're just going along with the joke and I'm demonstrating
my own lack of humor.)

I've never read all of Pope's "An Essay on Criticism,"
but I recall some excerpts in which he pointed out assorted
faults using language that demonstrated them. The example
that came to mind concerned two tactics Pope frowned on:
Trying to juice a boring passage by inserting shocking but
essentially meaningless language, and stuffing a line with
single-syllable words just to fit the poem's meter[*]:

While Expletives their feeble Aid do join,
And ten low Words oft creep in one dull Line,

It appears Pope was better at this technique than I am.

[*] ObTopicality: This is like inserting padding bytes
to preserve alignment, see?

 

[Nick]

Am I the only one who got Eric's joke? He was gratuitously using
the loaded word "scum" while complaining about "the scum who use
loaded words gratuitously". If certain other posters had said the
same thing, I would just think they're being hypocrites, but I'm
sure Eric did it intentionally and with humorous intent.

(Or maybe you're just going along with the joke and I'm demonstrating
my own lack of humor.)

I have to admit it completely wooshed me. Mainly I think because people
are so (gratuitously) rude here that it didn't make me pause to think
"that's unusual".

 

[Antoninus Twink]

I think quite a few less experienced users of C might find another
newsgroup more congenial with help less fogged by abusive reactions
from a handful of bullies.

Very well said.

 

[Tim Rentsch]

... and having looked, you'll find that the Standard has
an answer: The implementation ceases to conform.

No, because what Linux does isn't part of "the implementation". The
Standard identifies the distinction in section 1 paragraph 2, talking
about "a data-processing system that is capable of supporting a
conforming implementation." Linux is part of the data-processing
system, not part of the implementation.

 

[Keith Thompson]

No, because what Linux does isn't part of "the implementation". The
Standard identifies the distinction in section 1 paragraph 2, talking
about "a data-processing system that is capable of supporting a
conforming implementation." Linux is part of the data-processing
system, not part of the implementation.

Then I would argue that, if the malloc behavior commonly seen on
Linux-based systems is non-conforming, then Linux is a data-processing
system that is not capable of supporting a conforming implementation.
(Or rather, a conforming implementation could be created, but it would
require substantial extra work and/or some perhaps unreasonable
restrictions.)

I'm not, for now, saying anything about whether the malloc behavior in
question (returning a non-null pointer but killing some process, not
necessarily the offending one, on an attempt to use the memory) is
conforming or not.

 

[Eric Sosman]

No, because what Linux does isn't part of "the implementation". The
Standard identifies the distinction in section 1 paragraph 2, talking
about "a data-processing system that is capable of supporting a
conforming implementation." Linux is part of the data-processing
system, not part of the implementation.

(Take note of the start of paragraph 2: "This International
Standard does *not* [emphasis mine] specify" ...

The root cause of non-conforming behavior is of interest
only for diagnosis and finger-pointing. Whatever the cause,
the fact remains: If a call to malloc() causes a conforming
program to terminate, the implementation has not followed the
specification in the Standard, and has failed to conform. Or,
the data-processing system capable of supporting a conforming
implementation has chosen not to do so or has turned out to be
incapable.

 

[Ian Collins]

What if the OS terminates the process without a call to malloc (due to
some other memory hungry process)?

Then it's a naff OS.

What if the OS terminates the process without a call to malloc due to
some other external event (power-off)?

That's irrelevant. The point was malloc shouldn't terminate the
program, it should return NULL.

If a conforming process must be kept alive regardless of external
events, can an implementation ever be conforming?

That's irrelevant.

 

[Willem]

Ian Collins wrote:
) That's irrelevant. The point was malloc shouldn't terminate the
) program, it should return NULL.

malloc doesn't terminate the process. At some *later* point in time, when
the malloc()ed memory is actually used, some *other* random process gets
killed.

)> If a conforming process must be kept alive regardless of external
)> events, can an implementation ever be conforming?
)
) That's irrelevant.

False, as shown above.


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

 

[Ian Collins]

Ian Collins wrote:
) That's irrelevant. The point was malloc shouldn't terminate the
) program, it should return NULL.

malloc doesn't terminate the process. At some *later* point in time, when
the malloc()ed memory is actually used, some *other* random process gets
killed.

That's awful, but nothing to do with C.

)> If a conforming process must be kept alive regardless of external
)> events, can an implementation ever be conforming?
)
) That's irrelevant.

False, as shown above.

How?

 

[gwowen]

That's irrelevant.  The point was malloc shouldn't terminate the
program, it should return NULL.

The point is that conforming process should never terminate, unless
the programer calls exit(), abort(), returns from main() or the
like.

int main()
{
while(1) {}
}

Using your description any implementation that kills that process for
any reason is non-conforming. The standard says that program runs for
ever. Therefore, it must run for ever on any conforming
implementation. It's the kind of reductive argument that leads one to
conclude that no implementation is conforming. Possibly logically
true, but completely without merit.

 

[Tim Rentsch]

No, because what Linux does isn't part of "the implementation". The
Standard identifies the distinction in section 1 paragraph 2, talking
about "a data-processing system that is capable of supporting a
conforming implementation." Linux is part of the data-processing
system, not part of the implementation.

(Take note of the start of paragraph 2: "This International
Standard does *not* [emphasis mine] specify" ...

Yes, that's precisely the point.

The root cause of non-conforming behavior is of interest
only for diagnosis and finger-pointing. Whatever the cause,
the fact remains: If a call to malloc() causes a conforming
program to terminate, the implementation has not followed the
specification in the Standard, and has failed to conform. Or,
the data-processing system capable of supporting a conforming
implementation has chosen not to do so or has turned out to be
incapable.

It's relevant because in one case the item in question is
something covered by the Standard and in another case it isn't.
An implemenation might be conforming but work only on some
versions of Linux, just as an implementation might be conforming
but work only some processor configurations (thsoe with at least
64K of RAM, for example). A conforming C compiler won't run on
my toaster; that doesn't mean my toaster isn't conforming, only
that it can't support a C compiler, and the Standard explicitly
doesn't concern itself with such things.

I have no argument with the essential point you're making,
I just think it's important to say it in a way that's
faithful to the view taken and the language used in
the Standard, because otherwise the meaning gets confused.
If I turn my computer off that doesn't mean my C compiler
suddenly becomes non-conforming; it just means my computer
is off and can't run the (conforming) C compiler.

 

[Ian Collins]

The point is that conforming process should never terminate, unless
the programer calls exit(), abort(), returns from main() or the
like.

Who or what made that claim?

int main()
{
while(1) {}
}

Using your description any implementation that kills that process for
any reason is non-conforming.

Can you cite my description? I don't recall writing one.

The standard says that program runs for
ever. Therefore, it must run for ever on any conforming
implementation.

C&V please.

 

[Eric Sosman]

What if the OS terminates the process without a call to malloc (due to
some other memory hungry process)?

What if the OS terminates the process without a call to malloc due to
some other external event (power-off)?

If a conforming process must be kept alive regardless of external
events, can an implementation ever be conforming?

The Standard describes various things that can cause program
termination: returning from the original invocation of main(),
calling exit() or _Exit() or abort(), or receiving a signal that
causes termination (there are implementation-defined aspects
here). Plus, of course, undefined behavior may include program
termination -- or even programmer termination, as illustrated
at <http://dialspace.dial.pipex.com/town/green/gfd34/art/>.

The Standard also describes how a program executes (5.1.2.3,
also 6.8p2), and in these descriptions I see no leeway that
allows `x = y' or any such innocuous construct to terminate the
program (barring U.B., which is the program's fault and not the
implementation's worry).

The only "out" a conforming implementation can use to force
termination is to send a signal, presumably an uncatchable one
or a member of the implementation-defined set for which the
behavior is undefined if a handler attempts to return. But as
far as I can see the signal must actually be raised, even if the
root cause of termination is a bobby pin in the backplane. An
implementation that terminates a conforming program by any means
other than those documented is non-conforming; in language used
elsethread, the data-processing system "capable" of supporting
a conforming implementation has become "incapable."

In the specific case of Linux' Out-Of-Memory killer, I do
not happen to know whether it uses a signal as its murder weapon.
I also don't happen to know whether there's a "losing power"
interrupt that sends SIGPWR to every running program in the last
few milliseconds before the voltage falls too low. I sincerely
doubt the existence of SIGBOBBYPIN ...

 

[gwowen]

     In the specific case of Linux' Out-Of-Memory killer, I do
not happen to know whether it uses a signal as its murder weapon.

It does. SIGKILL, which POSIX tells us cannot be caught or handled.

 

[Nobody]

In the specific case of Linux' Out-Of-Memory killer, I do
not happen to know whether it uses a signal as its murder weapon.

It uses SIGKILL.

I also don't happen to know whether there's a "losing power"
interrupt that sends SIGPWR to every running program in the last
few milliseconds before the voltage falls too low.

Linux and Solaris have SIGPWR. On Linux, the default (uncaught) behaviour
is to terminate the process, while Solaris ignores it. In both cases, it
can be caught or explicitly ignored.

I sincerely doubt the existence of SIGBOBBYPIN ...

System failure arguably doesn't result in any processes "terminating".
E.g. a parent process wait()ing on its child will not perceive termination.

If we're competing for the most ridiculous definition of conformance,
it's more interesting to consider the case of partial failure (e.g. cosmic
rays), where (unlike total failure) the rest of the system is still around
to witness the non-conforming behaviour.

 

[Richard Herring]

›it's‹ should be ›its‹ instead.

Since you're posting in English, ›its‹ should be "its".

HTH.