General method for dynamically allocating memory for a string

[Keith Thompson]

Richard Heathfield wrote:
[ snip all ]
Some time ago now I attacked the GC problem, as I saw it, with what
I called GE or Garbage Elimination.
It has to do with wrapping malloc, calloc, realloc and free such
that they all come to GE first. GE is basically a manager of a
linked list of allocation data, including addresses and sizes.
GE.h adds 'size_t size(void *p);' to the vocabulary, size of the
allocation.
User calls to *alloc are simply recorded in the list and then passed
to their libc namesakes. Calls to free() are looked up in the list
and if found result in a call to libc free() and deletion from the
list. If the user calls free(x) and x is not in the list, we simply
return, a NOP.
What do you think of it?

I am afraid you are actually repeating the code of malloc.
The system function malloc has been probably coded with great care to
do exactly that:

Find a free block in the list of free blocks!

You are just adding a layer that does the same.

But that layer in the system malloc() is not exposed to the user. The
only *portable* way to do this kind of thing is to add a wrapper
around *alloc() and free(). Such a wrapper can detect errors that
malloc() can't (such as free()ing the same pointer twice).

It could significantly hurt performance if you keep track of
allocations with a simple linear linked list.

 

[Gordon Burditt]

Some time ago now I attacked the GC problem, as I saw it, with what I

called GE or Garbage Elimination.

It has to do with wrapping malloc, calloc, realloc and free such that
they all come to GE first. GE is basically a manager of a linked list of
allocation data, including addresses and sizes.

GE.h adds 'size_t size(void *p);' to the vocabulary, size of the allocation.

User calls to *alloc are simply recorded in the list and then passed to
their libc namesakes. Calls to free() are looked up in the list and if
found result in a call to libc free() and deletion from the list. If the
user calls free(x) and x is not in the list, we simply return, a NOP.

What do you think of it?

I'd like to see it have a debugging mode with these characteristics:

(1) Attempting to free something not in the list results in a call to abort().
Or perhaps just logs it.

(2) Allocated memory is initialized to a machine-specific bit pattern
that matches neither all bits 0 nor the bit pattern of a null
pointer, and which is likely to cause program aborts when used as
a pointer accidentally. It should be pessimally aligned. This
pattern should be known to users of the platform so it can easily
be spotted in memory dumps by a debugger. Example: on 32-bit
machines where a null pointer does not use this pattern (no,
0xdeadbeef is *NOT* always used as the bit pattern for a null
pointer, even on machines with 32-bit pointers): 0xdeadbeef.

(3) Deallocated memory is scribbled on with a machine-specific bit
pattern different from the one used in (2) above. The objective
here is to find errors like:

free(foo);
free(foo->next);
where freed memory is used. Example: on 32-bit machines where a
null pointer does not use this pattern: 0xf3eebee1.

Another useful mode is to have (2) and (3) use random bit patterns.
Also, code like this could easily have a memory-leak-detection feature.

 

[Joe Wright]

Richard Heathfield wrote:
[ snip all ]
Some time ago now I attacked the GC problem, as I saw it, with what
I called GE or Garbage Elimination.
It has to do with wrapping malloc, calloc, realloc and free such
that they all come to GE first. GE is basically a manager of a
linked list of allocation data, including addresses and sizes.
GE.h adds 'size_t size(void *p);' to the vocabulary, size of the
allocation.
User calls to *alloc are simply recorded in the list and then passed
to their libc namesakes. Calls to free() are looked up in the list
and if found result in a call to libc free() and deletion from the
list. If the user calls free(x) and x is not in the list, we simply
return, a NOP.
What do you think of it?

I am afraid you are actually repeating the code of malloc.
The system function malloc has been probably coded with great care to
do exactly that:

Find a free block in the list of free blocks!

You are just adding a layer that does the same.

But that layer in the system malloc() is not exposed to the user. The
only *portable* way to do this kind of thing is to add a wrapper
around *alloc() and free(). Such a wrapper can detect errors that
malloc() can't (such as free()ing the same pointer twice).

It could significantly hurt performance if you keep track of
allocations with a simple linear linked list.

I could use some sort of hash I guess but according to the second rule
(for experts only) I haven't optimized it yet.

 

[av]

Richard Heathfield wrote:
[ snip all ]
Some time ago now I attacked the GC problem, as I saw it, with what
I called GE or Garbage Elimination.
It has to do with wrapping malloc, calloc, realloc and free such
that they all come to GE first. GE is basically a manager of a
linked list of allocation data, including addresses and sizes.
GE.h adds 'size_t size(void *p);' to the vocabulary, size of the
allocation.
User calls to *alloc are simply recorded in the list and then passed
to their libc namesakes. Calls to free() are looked up in the list
and if found result in a call to libc free() and deletion from the
list. If the user calls free(x) and x is not in the list, we simply
return, a NOP.
What do you think of it?

I am afraid you are actually repeating the code of malloc.
The system function malloc has been probably coded with great care to
do exactly that:

Find a free block in the list of free blocks!

You are just adding a layer that does the same.

But that layer in the system malloc() is not exposed to the user. The
only *portable* way to do this kind of thing is to add a wrapper
around *alloc() and free(). Such a wrapper can detect errors that
malloc() can't (such as free()ing the same pointer twice).

It could significantly hurt performance if you keep track of
allocations with a simple linear linked list.

wrong, in the 90% of case (how malloc and free have to use) e.g.
something like

{ p1=malloc(n1);
p2=malloc(n2);
p3=malloc(n3);
p4=malloc(n4);
...NO MALLOC HERE
free(p4);
free(p3);
free(p2);
free(p1);
}

the search of p1, p2, p3, p4 is O(1) if there is a search like

free(void* k)
{int i;
...
for(i=last; i>=0; --i)
if(vettore==k) break;
if(i<0) \\ error;

}

 

[av]

Richard Heathfield wrote:

[ snip all ]

Some time ago now I attacked the GC problem, as I saw it, with what I
called GE or Garbage Elimination.

It has to do with wrapping malloc, calloc, realloc and free such that
they all come to GE first. GE is basically a manager of a linked list
of allocation data, including addresses and sizes.

GE.h adds 'size_t size(void *p);' to the vocabulary, size of the
allocation.

User calls to *alloc are simply recorded in the list and then passed
to their libc namesakes. Calls to free() are looked up in the list and
if found result in a call to libc free() and deletion from the list.
If the user calls free(x) and x is not in the list, we simply return,
a NOP.

for me, free a pointer that is not realised from malloc is an error
that has to be segnaled

I think that if an invalid pointer is passed it should abort the program
since something serious has gone wrong and you don't know how much else
has been messed up.



No, his layer does *not* do the same as the C library. Most
implementations will crash at some point after you have called free with
an invalid pointer. Joe Wright's wrapper will prevent that.

for me a crash that show an error is better than the "silent running
wrong"

 

[Michael Wojcik]

My inclination would be to have an optional callback for this and
other error conditions; that would let the library user log the
error, or abort, or whatever seems appropriate for the application.

But the general idea is a good one, and many of the projects I've
worked on had similar allocation wrappers. (They also often support
things like generating allocation reports at program termination, to
help detect leaks.)

It could significantly hurt performance if you keep track of
allocations with a simple linear linked list.

It *could*, particularly due to caching effects (linked lists generally
have poor cache behavior), but there's ample room for optimization if
that becomes an issue, and I suspect that for most C programs it
won't. If a performance-critical program is doing dynamic memory
allocation in the inner loop, that suggests the program might stand a
bit of optimization.

IME, C programs tend to do significantly less dynamic allocation than
programs written in languages with more dynamic-allocation sugar,
presumably for the obvious reason - the programmer has to write all
the allocation code explicitly.

And the tradeoff advantages are sufficient to justify a significant
performance cost in many cases anyway; for example, just duplicating
the malloc housekeeping data somewhere not adjacent to the allocated
storage itself, and using it as a preliminary check, prevents dup-free
heap-smashing attacks, which have been very successful against a wide
range of programs. It's a cheap security measure.

--
Michael Wojcik (e-mail address removed)

Poe said that poetry was exact.
But pleasures are mechanical
and know beforehand what they want
and know exactly what they want. -- Elizabeth Bishop

 

[Keith Thompson]

wrong, in the 90% of case (how malloc and free have to use) e.g.
something like

{ p1=malloc(n1);
p2=malloc(n2);
p3=malloc(n3);
p4=malloc(n4);
...NO MALLOC HERE
free(p4);
free(p3);
free(p2);
free(p1);
}

the search of p1, p2, p3, p4 is O(1) if there is a search like

[snip]

Yes, that can happen in *some* cases -- which is why I wrote that it
*could* significantly hurt performance.

 

[websnarf]

Richard Heathfield wrote:
Some time ago now I attacked the GC problem, as I saw it, with what I
called GE or Garbage Elimination.

It has to do with wrapping malloc, calloc, realloc and free such that
they all come to GE first. GE is basically a manager of a linked list of
allocation data, including addresses and sizes.

GE.h adds 'size_t size(void *p);' to the vocabulary, size of the allocation.

User calls to *alloc are simply recorded in the list and then passed to
their libc namesakes. Calls to free() are looked up in the list and if
found result in a call to libc free() and deletion from the list. If the
user calls free(x) and x is not in the list, we simply return, a NOP.

What do you think of it?

This does not solve the general problem of garbage collection. GC
typically eliminates the need for free() by automatically recycling
memory any time that memory stops being referenced by any pointer that
is ultimately reachable from within the program's current run state.

From what I can tell, what you've done is simply enhanced the memory

model by adding a size(void *p) function, and have a method for
detecting bogus calls to free() (including double frees.) There is no
end of ways to enhance C's memory model, and this is certainly one of
them, but this is not GC. True GCs are somewhat difficult to implement
in C and ultimately rely on platform specific behavior (to access all
live run-time autos, and all writable data areas, for example). Though
they certainly exist (the Boehm GC mechanism, for example.)

That all being said, I fully endorse the idea of enhancing C's memory
model. A big reason why people have run away from C and gone to other
langauges is because the whole malloc/free, programming model is very
hard to sustain especially given the bear-bones support that the
language gives you. But in doing such enhancements, you should not
target an attempt to duplicate GC, since that truly changes programming
paradigms -- C has way too much cruft in it to support a true paradigm
shift without substantial change to the language (comparable to what
C++ or Objective C did.)

What you want to do is to go ahead and embrace C's basic way of doing
things (after all that's the environment) we are in, but attack all its
main weaknesses. I.e., when a GC advocate says "C's memory model is
bad because of reason/example x" you want to be able to respond, "No,
that's easily detectable and correctable with an enhanced C memory
manager that does y". With this in mind, let us return to your "GE"
enhancement.

In your case, rather than *IGNORING* attempts to free garbage, you
should generate some sort of diagnostic to provide the programmer with
information telling them that they did something wrong. In fact you
can do this:

/* In some include file somewhere, say "estdlib.h" */
#define free(x) free_enhanced ((x), __FILE__, __LINE__)
void free_enhanced (void *, const char *, int);

/* In some module, say estdlib.c */
void free_enhanced (void * ptr, const char * file, int line) {
if (wasLegallyAllocated (ptr))
specialfree (ptr); /* find the real header, then free */
else
diagnostic_badfree (file, line, ptr);
}

So that in your error log, or message or whatever you decide to do, you
know exactly which call to free is failing. Its very important for the
programmer to know that this bad thing is going in in his/her program
as this may be symptomatic of more serious problems in the program, and
simply avoiding this one anomily is likely to be a bandage that just
doesn't do the surgeon's job.

Another really easy to implement feature is to simply keep track of the
total amount of memory currently allocated, as well as the lifetime
maximum allocated by the program. You could then provide two simple
functions that just returned these values. These are usually
sufficient hints for most programmers to know if they are leaking
memory or not.

As long as you are tracking all allocations in a linked list, you also
might as well provide a memory traversal mechanism. I.e., an ability
to walk through all allocated memory locations. Why would you do this?
Well you would do it in conjunction with an enhancement that tracked
*where* each allocation came from:

/* In some include file somewhere, say "estdlib.h" */
#define malloc(x) malloc_enhanced ((x), __FILE__, __LINE__)
void * malloc_enhanced (size_t, const char *, int);

/* In some module, say estdlib.c */
struct enhancedMemHdr {
struct enhancedMemHdr * linkNext;
size_t sz;
const char * moduleOrg;
int lineNumberOrg;
char mem[1]; /* struct hack */
};

void * malloc_enhanced (size_t sz, const char * file, int line) {
struct enhancedMemHdr * ptr;
if (!sz) {
diagnostic_badmalloc (file, line, sz);
return NULL;
}
/* store sz, file & line as well: */
ptr = specialmalloc (sz, file, line);
if (!ptr) {
diagnostic_outofmemory (file, line, sz); /* don't abort */
}
return ptr.mem;
}

So the point is not to look into the memory itself while you walk the
allocations (you wouldn't have type information, so that would be kind
of useless) but rather you would be interested in *where* the memory
got allocated. So you could do some simple statistics to figure out
where your memory was mostly being allocated for.

 

[Philip Potter]

No. It is quite more easy to write errorfree programs using
malloc()/free() than having a defective GC. A GC that can't handle
perfectly each and any dynamic memory is perfectly unuseable per
design.


GC as it should be designed araises this claim.

I'm not sure what this sentence means. Assuming "araises" is a typo for
"raises", you're changing the definition of a GC to be something which is
impossible to implement, and then rebutting it. It's a straw man argument.

The fact of the matter is that GCs are not inherently broken. Java and LISP
programs do actually work without crashing, provided the programmer
understands what they are doing. (And if the programmer doesn't know what
they are doing, well, all is lost.)

In C it will fail
always miserably, so it is useless.

I'm prepared to talk about whether or not GCs are suited to C, but blind
assertions do little to convince me that they are not.

I personally feel that GCs are suited to some forms of programming but not
others. A programmer using a GC still has to take care - but less care IMHO
than one using malloc()/free(); GCs reduce development time and maintainence
costs, at the cost of less efficient memory management and bigger runtime
footprint - lower performance, in short.

If this isn't what the Standards committee think what C is about, then I'm
not going to argue. But I'm also not going to argue with anybody who plugs a
GC into C for their own personal use.

Philip

 

[Joe Wright]

(e-mail address removed) wrote:

[ snipped ]

Thanks Paul for a very thoughtful and helpful critique of GE. Some of
your suggested enhancements are provided for. GE.h has a new prototype
allowing 'void * Free(void *);' and provides a typedef of the node
structure for the list. Free returns a pointer to the beginning of the
list. Also besides 'size_t size(void *)' there is 'size_t sizeall(void)'
which sums all the sizes.

Also 'void freeall(void)' which trips through the list freeing each
allocation and removing its node in turn. I think I have to revisit this
function to ensure allocations get freed in reverse order so that I
don't free **a before I free all the *a pointers.

Thanks again.

 

[Herbert Rosenau]

/* In some module, say estdlib.c */
struct enhancedMemHdr {
struct enhancedMemHdr * linkNext;
size_t sz;
const char * moduleOrg;
int lineNumberOrg;
char mem[1]; /* struct hack */
};

It's faulty. It does not help against the most bad pointer handling
one can do. It will not even catch such things as

1. dosn't help against overwriting memory but will destroy the
bookkeeping the memory manager knows nothing of AND may or may not the
memory bookkeeping of malloc too.

p = malloc(1000)
p2 = p - 3;
memcpy(p2, "I'm destroying memory management now");

or

long p = malloc(400);
p2 = p + 100;
strcpy(p2, "I'm writing behind the size of the allocated memory block
now");

In both cases the crash will occure 345 calls of some other functions
from here.

2. When you have to made 1.000.000 calls to get all memory you needs
20.000.000 bytes of memory extra. In an program I maintain that will
cost exactly the amout of memory that let it get at lest the amount of
memory it needs to get for it highly need of short structs to fill the
nested lists of nested lists of nested list of nested lists of structs
beside a number of dynamically allocated buffers in size of some bytes
up to some megabytes in size each. to do its primitive work: get
enough members to store all data needed. That meenas 20 MB memory is
not dispensable.

I've written my own c/m/realloc() to win 8 - 12 from 16 bytes my
standard memory manager uses for its internal storage on each request
of a memory block to give me a higher number of requestable blocks as
the mayority of memory blocks is less than 20, 40 or 120 bytes in size
spending 16 for each only for mangement is too high.

3. The risk that your struct will end up in returning a pointer to
unaligned address is high.
Even on 32 bit mashines alignment on an address divisible through 4
may not enough. What is when an long double address needs alignment of
8 instead of 4?

It's not even portable. Because nothing ssays that an alignment of 6
or 7 is not an requirement for some data or pointer size? The
c/m/realloc() is committed to return a pointer aligned for each
possible data type

void * malloc_enhanced (size_t sz, const char * file, int line) {
struct enhancedMemHdr * ptr;
if (!sz) {
diagnostic_badmalloc (file, line, sz);
return NULL;
}
/* store sz, file & line as well: */
ptr = specialmalloc (sz, file, line);
if (!ptr) {
diagnostic_outofmemory (file, line, sz); /* don't abort */
}
return ptr.mem;
}

Too time expensive for practical use where memory allocation is mor
than the half needed runtime for creating the structures needed to
store the data in an ordered manner.

So the point is not to look into the memory itself while you walk the
allocations (you wouldn't have type information, so that would be kind
of useless) but rather you would be interested in *where* the memory
got allocated. So you could do some simple statistics to figure out
where your memory was mostly being allocated for.

To fix the possibility to dedect memory overrides you have to change
your struct:
1. don't use the struct hack. Use a separate memory are for your
memory management that is truly separate from the area you gives to
your users. That means you have to build up an array of n structs to
get space for the management, you have to build a list of that arrays
to be extensible when that array gets full and more memory is
requested.

You have to spend more and more and more runtime to
- find an free element in your management structure for reuse
- find the management struct again to free it after you free()d
the memory the user will free.


An advansed C programmer needs no nanny to get memory management
right. A beginner will learn that quickly or should use C++ and new
instead.

And a nanny that does not really help in catching faoulty memory
writes is no help either. Faulty means here overwriting the limimts of
allocated block either before its start or after its end.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

 

[av]

p = malloc(1000)
p2 = p - 3;
memcpy(p2, "I'm destroying memory management now");

in this case here when free p my prog know there is something wrong
and i go for the default exit

or

long p = malloc(400);
p2 = p + 100;
strcpy(p2, "I'm writing behind the size of the allocated memory block
now");

the same here

In both cases the crash will occure 345 calls of some other functions
from here.

at last when it free p. if the information for the pointer is stored
in the same array for vectors only when free p and this can not
"destroying memory management"

 

[jacob navia]

I'm prepared to talk about whether or not GCs are suited to C, but blind
assertions do little to convince me that they are not.

I personally feel that GCs are suited to some forms of programming but not
others. A programmer using a GC still has to take care - but less care IMHO
than one using malloc()/free(); GCs reduce development time and maintainence
costs, at the cost of less efficient memory management and bigger runtime
footprint - lower performance, in short.

If this isn't what the Standards committee think what C is about, then I'm
not going to argue. But I'm also not going to argue with anybody who plugs a
GC into C for their own personal use.

Philip

Just one example:

I wrote the debugger of the lcc-win32 compiler system using the GC.

Without it, I would have never finished it.

There are 3 threads in the debugger: the edtior, (UI), the
debugger itself, and the debuggee, the program that is to be debugged.

The debugger and the editor that displays the results of the
debugger share a lot of buffers, and state. Messages are sent
to the UI for display, and input is retrieved from the user
and sent to the debugger. At the same time, complicated
data structures are built on the fly to support the displays
for the current line, structures that must be thrown away
immediately and rebuilt when the debugger reaches another,
completely unrelated point...

Using malloc/free this was HELL!!!

Tracking each and every buffer, each and every data structure,
is so complex that it would have taken months and months
to develop and debug. Specially, debugging a debugger
is not really an easy to do thing... specially if the debugger
is not able to debug itself.

Freeing complicated hierarchical data structures is very difficult.
And it takes time and effort. Each pointer that you have stored
somewhere must be proofed... is it still valid???

The GC allowed me to develop the debugger without ALL those
questions.

I concentrated in the debugger, and memory management is now automatic.

jacob

 

[ena8t8si]

I'm not sure what this sentence means. Assuming "araises" is a typo for
"raises", you're changing the definition of a GC to be something which is
impossible to implement, and then rebutting it. It's a straw man argument.

The fact of the matter is that GCs are not inherently broken. Java and LISP
programs do actually work without crashing, provided the programmer
understands what they are doing. (And if the programmer doesn't know what
they are doing, well, all is lost.)


I'm prepared to talk about whether or not GCs are suited to C, but blind
assertions do little to convince me that they are not.

I personally feel that GCs are suited to some forms of programming but not
others. A programmer using a GC still has to take care - but less care IMHO
than one using malloc()/free(); GCs reduce development time and maintainence
costs, at the cost of less efficient memory management and bigger runtime
footprint - lower performance, in short.

GC isn't always inherently less efficient or lower performance
than using malloc()/free(). For some applications, using GC
produces a faster application than using malloc().

If this isn't what the Standards committee think what C is about, then I'm
not going to argue. But I'm also not going to argue with anybody who plugs a
GC into C for their own personal use.

How do you expect to fit in on comp.lang.c with
a reasonable attitude like that?

 

[Herbert Rosenau]

Just one example:

I wrote the debugger of the lcc-win32 compiler system using the GC.

Without it, I would have never finished it.

Umm, it seems you have to learn programming, not hacking.

There are 3 threads in the debugger: the edtior, (UI), the
debugger itself, and the debuggee, the program that is to be debugged.

Ugh, on an real OS a debugger would not been a thread of the debuggee
and the debugee will never benn a thread of the debugger. You'll have
2 independant processes, where the OS allows the debugger to control
the debugee. You would have to learn how process and thread control
works on the system the debuger and debugee runs on. You'll have to
learn how the debug control interface of the OS works. It's not really
easy but doable. Hacking around is no choice.

The debugger and the editor that displays the results of the
debugger share a lot of buffers, and state. Messages are sent
to the UI for display, and input is retrieved from the user
and sent to the debugger. At the same time, complicated
data structures are built on the fly to support the displays
for the current line, structures that must be thrown away
immediately and rebuilt when the debugger reaches another,
completely unrelated point...

Gee, you have to learn how the memory manager of the OS works beside
the memory manager of the CRT. When you're a real compiler developer
you would be able to write a CRT supporting the debugger.

Using malloc/free this was HELL!!!

Only if you're not able to understund how the memory managers of both,
the OS and the CRT works. You needs to be a real programmer and not
only hacking around.

Tracking each and every buffer, each and every data structure,
is so complex that it would have taken months and months
to develop and debug. Specially, debugging a debugger
is not really an easy to do thing... specially if the debugger
is not able to debug itself.

Where is the problem? I'm not a compiler developer. I had no need to
develop a debuger, but I learned enough from both, the OSes memory
manager and the CRTs ones of my compiler to read and understund and
interpret theyr memory management structures. I can't find something
horrible on them. There is nothing horrible to management 2 linear
double linked lists like the malloc familiy does. The only you have to
do is to learn programming right instead of hacking around.

Freeing complicated hierarchical data structures is very difficult.

Really? It seams you're only a bloody hacker but knows nothing about
programming. You should start from begin and learn how to program.

And it takes time and effort. Each pointer that you have stored
somewhere must be proofed... is it still valid???

That is really simple. As developer you will simple set each invalid
pointer to NULL. As developer of a debugger you will catch the event
you get from the OS when the debugee fails on illegal memory access.
What is horrible on that?

What is the problem of multiple nested data stuctures? When you've
learned how to use them in assember you'll laugh about them in C.

The GC allowed me to develop the debugger without ALL those
questions.

GC was, is and will never a possible solution for the unabilities of a
programmer in C but will bring more problems in as it can resolve.
When you're unable to handle the malloc family right then C is not the
right language for you. Go to java instead.

I concentrated in the debugger, and memory management is now automatic.

And will produce memory leaks.

jacob

who has proven again that he knows nothing about programming but seems
to be gread in hacking around blindly.

Jacob, you should really learn how real programming works before you
tries to write such complicate things like a compiler or debugger.
They are both too big for your current knowledge.
Having extensive knowledge of assembly of a specific platform makes
you not a good C programmer.
You have to learn what C is, how C is designed, the standard, what it
means and how and why it is designed (for).

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!