Heap management

[Victor Nazarov]

So seems to be slightly wrong group, but...

The question is: Is there any extentions for C or well known libraries
to implement heap managment, for example if I want to allocate a randome
data in the static array of chars? For example:

Heap *heap_new (void *ptr, size_t size/*, may be some other
arguments*/);
void heap_delete (Heap *heapp);
void *heap_alloc (Heap *heapp, size_t object_size);
void *heap_realloc (Heap *heapp, void *alloced_object, size_t new_size);
void heap_free (Heap *heapp, void *alloced_object);

K&R book has a sample implementation of this, but is there a more
effective implementations and what do you think about including such
mecanism to a standard library (as a backend for malloc and co.)?

 

[Chris Torek]

So seems to be slightly wrong group, but...

The question is: Is there any extentions for C or well known libraries
to implement heap managment, for example if I want to allocate a randome
data in the static array of chars? For example:

Heap *heap_new (void *ptr, size_t size/*, may be some other
arguments*/);
void heap_delete (Heap *heapp);
void *heap_alloc (Heap *heapp, size_t object_size);
void *heap_realloc (Heap *heapp, void *alloced_object, size_t new_size);
void heap_free (Heap *heapp, void *alloced_object);

Your examples suggest to me that you want to write a set of functions
that work a lot like malloc/realloc/free, but on specific arenas
-- so that, for instance, you can create one area of size "3000
bytes" and make sure that whatever is allocated in that area, the
entire area never consumes more than 3000 bytes.

It *is* possible to write malloc()-like functions in C, and there are
existing libraries of such functions (to find them, try google or
perhaps comp.sources.wanted), except for one problem: ANSI/ISO C
lacks the ability to tell you what "maximal alignment" *is*. The
malloc() family always returns a "maximally aligned" pointer, so
that you can do things like:

char *p;
float *q;
long complex double *r;

p = malloc(NP * sizeof *p);
q = malloc(NQ * sizeof *q);
r = malloc(NR * sizeof *r);

and if p, q, or r are not NULL afterward, they are all valid pointers
pointing to the first of NP, NQ, or NR objects, so that (for
instance) r is valid for all integer values of i in [0..NR).

If you try to write your own malloc()-like function, however,
there is no *portable* way to find out what alignment to use.
In the example above, you can make a union:

union align { char c; float f; long complex double lcd; };

and use "sizeof(union align)" as a clue to the alignment required
to handle all of p, q, and r; but what if for some reason "short"
requires more alignment than "long complex double"? You can add
"short" to the union, but then what if the maximal alignment type
is actually "int *(*)(long)" or some such? No matter what types
you add to "union align", you *could* miss the underlying system's
"strictest" type, whatever that is.

If ANSI/ISO C had merely provided some sort of "alignment testing
and adjusting" macros or functions, then -- and only then -- would
there be some portable method for you to get the implementation
to tell you how to align pointers you would return from your own
malloc()-like functions, so that they would always work for every
valid piece of C code. But alas, none of the C standards (past or
present) do this.

Ultimately, what this really means is that while you *can* write
your own malloc()-like functions, you must resort to some non-Standard
trick to discover the alignment value. If you put this trick in
file(s) that you simply port or write anew every time you change
compilation environments, you can solve the problem relatively
cleanly.

... and what do you think about including such
mecanism to a standard library (as a backend for malloc and co.)?

If you study the CS literature, you will find dozens of memory
allocation strategies. There is no single best method for all
problems. (This is another reason I find the lack of a Standard
method for discovering alignment restrictions somewhat annoying.
On the other hand, when writing specialized, tuned allocators for
particular problems, you may already know all the data-types
involved, in which case the "union align" method generally suffices.)

 

[Victor Nazarov]

Chris Torek wrote:

I've knew most of your answers before. Thank you anyway. I have proposed
to involve heap_alloc and similar function to generalize standart
allocator. The idia was to make such functions that malloc could be
defined and implemented using these more general functions, not
nessesaraly the most effective for particular purpose.

If you study the CS literature, you will find dozens of memory
allocation strategies. There is no single best method for all
problems. (This is another reason I find the lack of a Standard
method for discovering alignment restrictions somewhat annoying.
On the other hand, when writing specialized, tuned allocators for
particular problems, you may already know all the data-types
involved, in which case the "union align" method generally suffices.)

I understand that if I'll nedd an effective allocator I'll need to write
an allocator suited for the particular application myself.

And I have two questions:
!) If I wrote an allocator using the union of all allocatable objects fo
alignment, would it be the most effictive in space usage, could it be
optimized to use less space with the help of system specific alignment
information?

2) What do think might be included in the standard lib to provide
alignment information?

 

[Chris Torek]

... And I have two [more] questions:
!) If I wrote an allocator using the union of all allocatable objects fo
alignment, would it be the most effictive in space usage, could it be
optimized to use less space with the help of system specific alignment
information?

Quite possibly. Note, one way to get what the *compiler* considers the
"minimal" alignment is to do something like this:

struct align {
char offset_zero;
/* padding goes here */
union {
/* this list will probably work in most cases */
int i;
long l;
long long ll; /* C99 only */
double d;
long double ld;
long double complex lcx; /* C99 only */
char *cp;
int *ip;
void (*fp)(void);
} u;
};
/* now use offsetof(struct align, u) to get alignment in bytes */

2) What do think might be included in the standard lib to provide
alignment information?

For 4.4BSD, I convinced the appropriate people to add two macros
to <machine/param.h>: ALIGNBYTES, whish is an integral constant
that is the largest number of "extra bytes" required to align
some pointer "p", and ALIGN(p), which is an expression that produces
an aligned value that is no less than "p" but perhaps as many as
ALIGNBYTES bytes "beyond" the initial value in p.

The type of the ALIGN(p) macro was "unsigned int", but in C99,
would be better expressed as intptr_t, or perhaps just "char *".

One problem with the ALIGN() macro is that it takes an arbitrary
pointer (of any type); 4.xBSD "gets away" with this by assuming
that these Unix-like systems are never going to run correctly on
any machine that is not inherently byte-addressed.

I think, however, that if one were to constrain the ALIGN macro
(or function, should it be made into a function in a future C
standard) to take a value of type "char *", these two -- ALIGNBYTES
and ALIGN -- would suffice. Note that:

ALIGN(p) - p /* p must have type "char *" */

would then have type "ptrdiff_t" and be a value between 0 and
ALIGNBYTES inclusive, e.g., 0 to 3, or 0 to 7, or 0 to 31, or
whatever the underlying system requires.

The actual implementation of ALIGN(p), on many real systems, is
then just:

#define ALIGN(p) \
((char *)(((intptr_t)(p) + ALIGNBYTES) & ~ALIGNBYTES))

On systems where this does *not* work, for whatever reason (such
as Cray systems with word addressing and "byte offsets" stashed
in high-order bits), some alternative macro invariably seems to
work.

 

[Malcolm]

I've knew most of your answers before. Thank you anyway. I have proposed
to involve heap_alloc and similar function to generalize standart
allocator. The idia was to make such functions that malloc could be
defined and implemented using these more general functions, not
nessesaraly the most effective for particular purpose.

You can write mymalloc() and myfree() and then implement them as you want.
The problem is that you make all your code dependent on this library.
Or you can call the functions malloc() and free(), effectively implementing
the standard library, but then the linker tends to complain on hosted
platforms.

And I have two questions:
!) If I wrote an allocator using the union of all allocatable objects fo
alignment, would it be the most effictive in space usage, could it be
optimized to use less space with the help of system specific alignment
information?

If you are bothered about a few bytes wasted at the beginning of an
allocation for alignment, then rethink the memory management of the whole
program. Probably you are allocating many very small chunks, so write a
"fixedalloc()" to allocate them efficiently.
But no, there is no easy way to determine alignment requirements in ANSI C.

2) What do think might be included in the standard lib to provide
alignment information?

The practical answer is to align to "double", and this will be portable
enough for most systems. It is a weakness in the standard that malloc cannot
be written portably, and I would solve it by creating a special type,
"strictest". On most compilers this would simply be implemented as a header
typedefing "strictest", though on an oddball it could be a keyword.

 

[Keith Thompson]

... And I have two [more] questions:
!) If I wrote an allocator using the union of all allocatable objects fo
alignment, would it be the most effictive in space usage, could it be
optimized to use less space with the help of system specific alignment
information?

Quite possibly. Note, one way to get what the *compiler* considers the
"minimal" alignment is to do something like this:

struct align {
char offset_zero;
/* padding goes here */
union {
/* this list will probably work in most cases */
int i;
long l;
long long ll; /* C99 only */
double d;
long double ld;
long double complex lcx; /* C99 only */
char *cp;
int *ip;
void (*fp)(void);
} u;
};
/* now use offsetof(struct align, u) to get alignment in bytes */

And you can probably get away with dropping the int and double members
(and the long, and perhaps long double, members for C99). It's
unlikely that double will have stricter alignment requirements than
long double. A system that's exotic enough to break this assumption
may have other problems as well, like requiring stricter alignment for
large structures.

 

[Malcolm]

And you can probably get away with dropping the int and double members
(and the long, and perhaps long double, members for C99). It's
unlikely that double will have stricter alignment requirements than
long double. A system that's exotic enough to break this assumption
may have other problems as well, like requiring stricter alignment for
large structures.

If I had a processor with 32 and 64 bit fpus, I'd make the smaller float and
the larger double. long double would then be supported in software to cater
for the person who needs precison but doesn't care about speed. It would be
quite likely that double would have a stricter alignment than long double.