Which allocator used by malloc

[john]

Hi,

I'm trying to put together an autoconf test that will try to detect what
allocation method is being used on the current platform by malloc()
(buddy/ fixed size pools/ etc.), and how big control blocks are etc.

The idea is that programmers might want to change allocation sizes to fit
within blocks, e.g. allocate (2^n - k) as the initial size of an array
instead of (2^n), if k is the size of the malloc control block.

So far, I've got this test program:

#include"stdio.h"
main()
{
int i;
char *p, *q, *malloc();
p = malloc(100);
q = malloc(100);
printf("difference: %d\n", (int) (q - p));
}

On gcc, this produces 112 while on tcc it's 104, so this is obviously
giving me some information about what malloc is doing in each case.

Does anyone have any suggestions for useful tests that would help
characterise the malloc() implementation? How could I distinguish buddy
from fixed pool just by looking at the outcome of a simple program
invoking malloc()?

Cheers

John

PS. I know technically some of the tests might be undefined, but
heuristics are fine for the application I have in mind.

 

[Seebs]

I'm trying to put together an autoconf test that will try to detect what
allocation method is being used on the current platform by malloc()
(buddy/ fixed size pools/ etc.), and how big control blocks are etc.
Don't.

Does anyone have any suggestions for useful tests that would help
characterise the malloc() implementation? How could I distinguish buddy
from fixed pool just by looking at the outcome of a simple program
invoking malloc()?

You couldn't.

Here's the thing. Most autoconf tests are garbage. This would actually
lower the average quality of the test pool.

Implementations may switch from one strategy to another, they may use
different strategies on different sizes of allocations, they may use
different strategies on different sizes of allocations based on environment
variables, they may change strategies if one fails and another succeeds.

In short, even if you narrow it down as far as "I only care to try to
detect this for glibc version 2.5 or 2.8", you're STILL not going to be
able to give a meaningful answer.

Secondly, if someone cares that much, the right thing for them to do is
request a single huge block and manage it in their own code.

This test, if you could write it, would be a competitor with the test on
sizeof(char) for sheer pointlessness. Don't.

-s

 

[Kaz Kylheku]

Hi,

I'm trying to put together an autoconf test that will try to detect what
allocation method is being used on the current platform by malloc()
(buddy/ fixed size pools/ etc.), and how big control blocks are etc.

That's tricky! Autoconf tests are fun, haha.

The idea is that programmers might want to change allocation sizes to fit
within blocks, e.g. allocate (2^n - k) as the initial size of an array
instead of (2^n), if k is the size of the malloc control block.

So far, I've got this test program:

#include"stdio.h"

main()

Don't use old-style definitions. Even in autoconf tests.
It's not worth supporting antedeluvial system.s

{
int i;
char *p, *q, *malloc();

malloc is declared in <stdlib.h>. It returns void *,
and takes an argument of type size_t. Your
old-style declaration not only has the wrong return
type here, but does not say anything about
the argument type.

p = malloc(100);

Here, you are calling malloc with an argument of type int, which is different
from size_t. This will probably work on platforms where size_t and int are of
the same size, which is a bad assumption.

E.g. what if size is a 64 bit unsigned long, and int is 32 bits? It might still
work as you expect (e.g. 64 bit registers are used for parameter passing and
the 100 gets zero-extended to to a 64 bit register, so all is well). But
suppose a stack is used. Pushing a 32 bit 100 onto the stack where a function
expects a 64 bit object? Not good.

q = malloc(100);
printf("difference: %d\n", (int) (q - p));

You should return something from a configuration test case, and not
leave the termination status be indeterminate!

It behooves you to have your shell script bail if the test program does not
execute successfully. This automatic bailing can obtained from the POSIX
shell via ``set -e''.

}

Subtracting pointers to different objects is not defined by ISO C, but in
practice it is highly portable and understandably necessary in this particular
test case; there is no way around doing this if you want to know what is the
addressing distance between two blocks from malloc.

On gcc, this produces 112 while on tcc it's 104, so this is obviously

Note that GCC does not come with a malloc implementation. That is supplied by a
library, and GCC is used with many different libraries (not only glibc). Even
on GNU/Linux distributions, there are alternative C libraries used, not always
glibc.

Your configure test is of a bad type which cannot be run when the program is
being cross-compiled. Be kind to those of us who cross-compile programs and
try not to write test which requires code to be run on the target system! Your
code will have to fall back on some default values, which makes the whole thing
worthless for cross-compiled systems. Or else users will have to manually take
your test code, run it on the cross-system and then tweak some configuration
values manually, which is a pain. (Think about the distro guy who has 80 other
packages to build).

If you want to know something about malloc, see if you can roll that into the
run-time behavior of the program. It's true that there are some things you
can't do that way (like make some compile-time decision based on the result of
the test), but perhaps that's a wortwhile compromise. It's at least worth
considering the question, ``what do I sacrifice, if anything, if I don't
require the build machine to be the host machine, and is it worth it?''

giving me some information about what malloc is doing in each case.

Does anyone have any suggestions for useful tests that would help
characterise the malloc() implementation?

You could allocate a whole bunch of blocks of different sizes, and
then analyze the spread of addresses.

From this you could make observations like, ``hey look, all 32 byte requests
are being allocated in a sequence together, and 128 byte requests are also
being allocated in a sequence together, elsewhere. That suggests that
allocation from size buckets is going on''.

On some implementations, there is an API for getting statistics from malloc.
There also may be an API to obtain the underlying size of the allocated block.

Since you're writing Autoconf tests, you can detect which of those API's are
available, and then conditionally generate further tests which exploit those
API's!

PS. I know technically some of the tests might be undefined, but
heuristics are fine for the application I have in mind.

Of course, but your declaration of malloc doesn't have to be wrong,
and your call to it doesn't have to be undefined.
Make only those things undefined that have to be.

 

[Nick]

Here, you are calling malloc with an argument of type int, which is different
from size_t. This will probably work on platforms where size_t and int are of
the same size, which is a bad assumption.

E.g. what if size is a 64 bit unsigned long, and int is 32 bits? It might still
work as you expect (e.g. 64 bit registers are used for parameter passing and
the 100 gets zero-extended to to a 64 bit register, so all is well). But
suppose a stack is used. Pushing a 32 bit 100 onto the stack where a function
expects a 64 bit object? Not good.

Are you saying that "malloc(100)" has to be "malloc((size_t)100)", or is
this a follow-on to not having a prototype in scope?

 

[gwowen]

Are you saying that "malloc(100)" has to be "malloc((size_t)100)", or is

this a follow-on to not having a prototype in scope?

The latter.

 

[Noob]

Welcome back, "amit" (Antoninus, is that you?)

Did you post original material this time?

Are you getting tired of trolling yet?

 

[Kenny McCormack]

Are you getting tired of trolling yet?[/QUOTE]

Are you?

Note: We are all trolls here - some wear white hats and some wear black.

 

[Eric Sosman]

Hi,

I'm trying to put together an autoconf test that will try to detect what
allocation method is being used on the current platform by malloc()
(buddy/ fixed size pools/ etc.), and how big control blocks are etc.

The idea is that programmers might want to change allocation sizes to fit
within blocks, e.g. allocate (2^n - k) as the initial size of an array
instead of (2^n), if k is the size of the malloc control block.
[...]

Note that on some platforms, the choice of which malloc()
implementation to use may be made at run-time, and may be made
differently for different runs of the same compiled program.
The malloc() you wind up using may turn out to be different
from the malloc() you tested with.

See also LD_PRELOAD, LD_LIBRARY_PATH.

 

[john]

That's tricky! Autoconf tests are fun, haha.




Don't use old-style definitions. Even in autoconf tests. It's not worth
supporting antedeluvial system.s


malloc is declared in <stdlib.h>. It returns void *, and takes an
argument of type size_t. Your old-style declaration not only has the
wrong return type here, but does not say anything about the argument
type.


Here, you are calling malloc with an argument of type int, which is
different from size_t. This will probably work on platforms where size_t
and int are of the same size, which is a bad assumption.

E.g. what if size is a 64 bit unsigned long, and int is 32 bits? It
might still work as you expect (e.g. 64 bit registers are used for
parameter passing and the 100 gets zero-extended to to a 64 bit
register, so all is well). But suppose a stack is used. Pushing a 32 bit
100 onto the stack where a function expects a 64 bit object? Not good.


You should return something from a configuration test case, and not
leave the termination status be indeterminate!

It behooves you to have your shell script bail if the test program does
not execute successfully. This automatic bailing can obtained from the
POSIX shell via ``set -e''.


Subtracting pointers to different objects is not defined by ISO C, but
in practice it is highly portable and understandably necessary in this
particular test case; there is no way around doing this if you want to
know what is the addressing distance between two blocks from malloc.


Note that GCC does not come with a malloc implementation. That is
supplied by a library, and GCC is used with many different libraries
(not only glibc). Even on GNU/Linux distributions, there are
alternative C libraries used, not always glibc.

Your configure test is of a bad type which cannot be run when the
program is being cross-compiled. Be kind to those of us who
cross-compile programs and try not to write test which requires code to
be run on the target system! Your code will have to fall back on some
default values, which makes the whole thing worthless for cross-compiled
systems. Or else users will have to manually take your test code, run it
on the cross-system and then tweak some configuration values manually,
which is a pain. (Think about the distro guy who has 80 other packages
to build).

If you want to know something about malloc, see if you can roll that
into the run-time behavior of the program. It's true that there are some
things you can't do that way (like make some compile-time decision based
on the result of the test), but perhaps that's a wortwhile compromise.
It's at least worth considering the question, ``what do I sacrifice, if
anything, if I don't require the build machine to be the host machine,
and is it worth it?''


You could allocate a whole bunch of blocks of different sizes, and then
analyze the spread of addresses.

From this you could make observations like, ``hey look, all 32 byte
requests are being allocated in a sequence together, and 128 byte
requests are also being allocated in a sequence together, elsewhere.
That suggests that allocation from size buckets is going on''.

On some implementations, there is an API for getting statistics from
malloc. There also may be an API to obtain the underlying size of the
allocated block.

Since you're writing Autoconf tests, you can detect which of those API's
are available, and then conditionally generate further tests which
exploit those API's!


Of course, but your declaration of malloc doesn't have to be wrong, and
your call to it doesn't have to be undefined. Make only those things
undefined that have to be.

Kaz,

Thanks a lot for your great answer, all very illuminating.

The only point I'd make is that autoconf tests need to run on LOTS of
platforms. There are still PLENTY of older compilers out there where
there's no void* and no size_t. Since void* and char* are guaranteed
binary compatible when void* exists, its harmless to declare malloc
returning a char*. Also if size_t exists and is wider than int, then
probably the compiler will "know secretly" what types the params of
malloc should be and will make sure the int gets zero-extended.

Cheers

John

 

[Eric Sosman]

The only point I'd make is that autoconf tests need to run on LOTS of
platforms. There are still PLENTY of older compilers out there where
there's no void* and no size_t. Since void* and char* are guaranteed
binary compatible when void* exists, its harmless to declare malloc
returning a char*. Also if size_t exists and is wider than int, then
probably the compiler will "know secretly" what types the params of
malloc should be and will make sure the int gets zero-extended.

If there really are PLENTY of pre-ANSI compilers still in
use, it's a sobering reminder of the limits of a Standard's
prescriptive power. Every so often we hear a call for the
next version of the Standard to outlaw X or require Y -- and
what you're saying is that even if it does so, the year 2030
will still see PLENTY of code relying on X and not daring to
use Y, twenty years after the event.

One also wonders about the nature of the "guarantees" that
pre-ANSI compilers observe. The reason for the ANSI Standard
was, in a sense, to bring those multiple different idiosyncratic
"guarantees" into harmony; a compiler that still sings out of
key after all this time may be tone-deaf in other ways, too.

 

[Keith Thompson]

The only point I'd make is that autoconf tests need to run on LOTS of
platforms. There are still PLENTY of older compilers out there where
there's no void* and no size_t. Since void* and char* are guaranteed
binary compatible when void* exists, its harmless to declare malloc
returning a char*. Also if size_t exists and is wider than int, then
probably the compiler will "know secretly" what types the params of
malloc should be and will make sure the int gets zero-extended.

void* and size_t were introduced by ANSI in 1989, and probably
supported by some compilers before that. I could probably find a
system with an implementation that doesn't have void* and size_t,
but I doubt that I could find such a system that doesn't also have
at least an ANSI C implementation. (I'm not saying such systems
don't exist, just that I probably couldn't find one.)

If you really have a specific need to support such ancient
implementations, then you gotta do what you gotta do. But I
personally wouldn't do the extra work needed to support pre-ANSI
implementations without a concrete requirement to do so. Even so, I'd
probably use "#if __STDC__ == 1" and isolate any pre-ANSI code as much
as possible. For example:

#if __STDC__ == 1
#include <stdlib.h>
#else
extern char *malloc();
#endif

(The whole point of standardizing the language was to avoid the need
for crud like this.)

As for implicitly zero-extending an int argument to malloc, I wouldn't
count on it. If I wrote:

char *malloc();
/* ... */
... malloc(42);

I'd expect the compiler to generate code to pass an int value to
malloc. If size_t is bigger than int, there's a very good chance
it would fail in some horrible way (one likely symptom is that the
argument is effectively multiplied by 2**32).

Since the call's behavior is undefined, the compiler *could* "fix"
it, but I've never seen a compiler actually do that. If you're
getting away with it, it's probably because int and size_t happen
to be the same size, or because the parameter passing conventions
happen to work in your favor.

 

[Phil Carmody]

The only point I'd make is that autoconf tests need to run on LOTS of
platforms. There are still PLENTY of older compilers out there where
there's no void* and no size_t.

Thanks for helping keep such systems alive.

Phil