Re: A solution for the allocation failures problem

Paul Hsieh wrote, On 31/01/08 18:47:
On Jan 30, 9:28 am, jacob navia <ja...@xxxxxxxxxx> wrote:
Paul Hsieh wrote:
On Jan 29, 3:47 am, jacob navia <ja...@xxxxxxxxxx> wrote:
1:
It is not possible to check EVERY malloc result within complex software.
I'm not sure what you mean by this. Are you saying that large complex
projects will inevitably have bugs of not checking? Or are you saying
that this is a literal impossibility?
There are many situations when you can't add at each level a complex
unwinding code to take care of an allocation failure in the middle of
the construction of a complex data structure. It is much more sensible
to set an a priori strategy and not check at each call.

Ah! I see what you mean now. I have actually run across this, and
found that as long as you allocate in a consistent nested order that
there is always a way to clean up properly; though in the worst cases
it requires a bunch of gotos that *could* actually be seen as
spaghetti code.

I have a different but possibly related method...

I suppose if this nested consistency could not be guaranteed, then
these clean up fragments could be very complicated.

Or just as simple...

But then I just
use the other method of getting this done which is to free everything
no matter what -- the point being that there would be some boolean
method for determining if a resource/object/whatever has not even yet
been initialized, in which case freeing is a NOOP on it. In the case
of bstrings, for example, if the bstring pointer is NULL, freeing it
becomes a NOOP.

For me the boolean method for determining whether a resource has been created yet is set the pointers to NULL at the point where they are created. For example...

struct difficult {
struct nested *ptr1;
struct more *ptr2;
...
};

static const difficult_null = {0};

struct difficult ptr = malloc(sizeof *ptr);
*ptr = difficult_null;

Now I can create the rest in an order and if I write all my "destroy" functions so that like free they are a noop for a null pointer all is simple.

But in both cases I am relying on conventions (that I am defining) to
make sure I can do it. I am pretty sure that my conventions don't
impact the ultimate scope of programming that I am capable of, so I
could make a claim that I think that its always possible to clean up
in a well defined way, but I can't say this with certainty.

I suspect your convention is probably similar to what I've just shown and I can't think of how destroying a partially created object can be difficult if you stick to it.

Clean-up
from failures along the way is certainly the least structured and
therefore least maintainable code I have ever written. So it would
similarly not surprise me if there were some cases where it was
actually *really hard* to write proper clean up code.

Apply appropriate methods at all levels of constructing the object and I find it hard to see how you can reach a really hard to destroy situation. Do a bad job of constructing, on the other hand, and you can make it damn near impossible.

I have code, not written by me, that can manage to tidy up a heck of a lot through some horrendous structures. At most levels the destroy code is simple linear code or simple loops, the only places it is tricky is where IMHO the constructor is truly horrible.

One could, for example, change the API for malloc to be something
like:
void * safemalloc(label,size_t sz);
which would jump to label if the allocation failed. Of course there
isn't a way to do this in standard C either with the pre-processor or
by function declarations. But some other sort of pre-processor, or
LINT check could do the equivalent of this.
I think a case could be made for extending the language standard to
include the above.
In any event, the *standard* approach of forcing your programmers to
painstakingly do the equivalent of this is still possible, and
essentially mandatory in C.
No. lcc-win implements try/catch, but of course the regulars here will
start crying "heresy heresy" so I did not mention that.

I happen to like try/catch, but it is not part of the C language.

Hmmm ... right. Personally, I try to separate each of my "extensions"
from the standard.

I agree with your implication that your libraries are not really extensions, just third party libraries. I also agree with keeping them independent *unless* there is a real dependency. For example, libxslt depending on libxml makes perfect sense to me. With real extensions there is a much bigger argument for keeping them separate, and to be fair to Jacob I believe his try/catch extension is independent from his other extensions.

>snip>

Solution:
1) At program start, allocate a big buffer that is not used
elsewhere in the program. This big buffer will be freed when
a memory exhaustion situation arises, to give enough memory
to the error reporting routines to close files, or otherwise
do housekeeping chores.
Ok, I see what you are doing here, but this is a desperate strategy
that I don't think fully works as well as you are hoping.
It is one way of trying to cope with this. The same strategy is
implemented for the stack under windows. You get a stack overflow
exception with one LAST page still free to be allocated for
the stack. You can then still call some functions and you have
a stack of 4096 bytes reserved for this purpose. This is the
same strategy.

With the stack I don't think it "frees the stack to make it available for use during recovery". Rather it uses the already allocated reserve stack. Linux can have a separate stack for signal handling for probably similar reasons. So in the malloc instance I would say you make use of the pre-allocated reserve rather than freeing it so you can do further mallocs whilst recovering.

Yes I see. But in the case of the depleted stack there is a platform
specific design problem with your program that cannot be resolved at
runtime; so some instant desperate strategy *must* be employed. With

There is another strategy. You analyse your code and *prove* the maximum stack usage. This is easiest if you completely avoid recursion. It was also a requirement for the embedded work I used to do in which recursion was actually banned.

the heap, things are different. There many well known algorithm
alternatives which trade of memory footprint for speed -- if you fail
with the memory allocation method, you can often just retry your
algorithm with a slower memory conservative solution.

The same can apply to stack usage. Switch to an algorithm that does not use recursion for example (maybe implementing a "stack" using malloc ;-)).

This is
fundamentally why I cannot endorse the xmalloc() design -- it removes
a legitimate programming path in which you literally write recovery
code in your software (if you could no longer use malloc() I mean).

Yup.

<snip>

This is just a model OBVIOUSLY. No multi-threading considerations are
in this code. It is just an outline of how this could be solved.

Right. I am just sensitive to this sort of thing, so I feel the need
to bring it up when I see it. Its clear the entire C language
committee seems to care less about these things as they continue to
endorse errno(), strtok(), asctime() and so on.

<snip>

errno is not a function ;-) Actually, errno can be implemented in a thread-safe manner and I believe the it is on current Linux systems. This actually broke some ancient code I inherited which provided its own external declaration of errno rather than including error.h

strtok, asctime and other functions which use static data are a pain though and should be avoided when doing threading. However removing them from the language would break perfectly good single-threaded code that uses them correctly, so I don't think they will be removed.
--
Flash Gordon
.

Relevant Pages

  • Re: Stack vs. Heap Question, Please Help
    ... public class Circle ... Could you please say where this would fall off the stack in your ... Circle is a class, not a struct, so creation of the circle goes on the heap. ... is not made at the point of allocation, but at the point of object (class ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: using malloc and calloc - help
    ... > in understanding malloc and calloc use in C. ... with dynamic memory allocation. ... instances of 'struct employee' to be automatic or static, ...
    (alt.comp.lang.learn.c-cpp)
  • Re: ten thousand small processes
    ... them roughly in the middle you take space away from heap and stack ... identical across two processes as is the case with large shared memory ... There is no special allocation for virtual address space that is ... the standard libc or at least not the standard malloc implementation. ...
    (freebsd-performance)
  • Re: C garbage collection -crazy idea
    ... node allocation function in my binary tree builder grabbed. ... then call those functions lmalloc... ... You can assign locally allocated memory to local ... similar (but only on the stack). ...
    (comp.lang.c)
  • Re: Why are variables stored on the stack?
    ... And that stack must be allocated previously and be contiguous. ... Where did you got this linked list allocation story? ... a dynamic storage area for its own use, ... Think about the supposed call to "malloc" to allocate a stack ...
    (comp.lang.c)