dynamic allocation

[meital]

I need to implement these functions:

void *malloc(int size);
void free(void* p);

using the functions below:

void* malloc_os(int size);
void free_os(int size, void* p);

the problem is that free_os can free only
the exact size of memory which was allocated
to p by malloc_os.

my idea was to define a struct, and for
each allocation, the number of bytes allocated
to the pointer, will be saved in the struct.

struct ptr
{
void* pointer;
int size;
}

the implementation should be as follows:

void* malloc(int size)
{
return malloc_os(size);
}

void free (void* p)
{
free_os( ((ptr*)p).size, ((ptr*)p).pointer);
}

main
{
struct ptr m;
int n_bytes = 9;

m.p = (void*)malloc(size);
m.size = n_bytes;
free(&m);
}

any other suggestions?

 

[meital]

main
{
struct ptr m;
int n_bytes = 9;

m.pointer = (void*)malloc(size); //correction m.pointer
m.size = n_bytes;
free(&m);
}

 

[Martin Ambuhl]

main
{
struct ptr m;
int n_bytes = 9;

m.pointer = (void*)malloc(size); //correction m.pointer

We have seen silly casts of the return value of (the real) malloc, but
this is the first time I've ever seen someone cast a (void *) to
(void *).

Not only does (the real) malloc return a (void *), but so does yours:
void* malloc(int size)
{
return malloc_os(size);
}


Is there a prize for most pointless cast?

 

[Nick Austin]

I need to implement these functions:

void *malloc(int size);
void free(void* p);

using the functions below:

void* malloc_os(int size);
void free_os(int size, void* p);

You can do all the pointer maths within the wrapper
functions so that the callee is unaware of the
trickery involved:

typedef struct
{
unsigned long size;
char userdata[ 1 ];
} MALLOC;

void* wrapper_malloc( int size )
{
MALLOC *p;

p = malloc_os( size + sizeof p->size );
if ( !p )
return NULL;

p -> size = size + sizeof p->size;
return &(p -> userdata);
}

void wrapper_free( void* p )
{
MALLOC *s;

s = (void *)( (char *)p - sizeof s->size );
free_os( s -> size, s );
}

Nick.

 

[meital]

I know that there is a problem with the casting.
Let's suppose the pointer in the struct is of
type int*, and then the casting will be:

m.pointer = (int*)malloc(size);

the type of pointer in the struct will also
change to int*.

will it work?

I can't think of another way it can be done.
the struct is essential.

 

[Martin Ambuhl]

I know that there is a problem with the casting.
Let's suppose the pointer in the struct is of
type int*, and then the casting will be:

m.pointer = (int*)malloc(size);

And is still pointless, but it doesn't look as silly as casting a
(void *) to a (void *).

the type of pointer in the struct will also
change to int*.

will it work?

Yes, and so will omitting the cast.

 

[Chris Torek]

I need to implement [the Standard C malloc() and free() functions]
using [OS-specific functions that manage underlying memory, but

require sizes].

In other words, you have to be an implementor.

As the implementor, you know what the alignment constraints for
your system are. (Since I do not know what your system is, *I*
do *not* know what those constraints are.)

You also know which integer type(s), if any, can hold the value
of a "void *" pointer, and whether the OS functions need to deal
only with whole words, whole pages, whole segments, or whatever.
Again, I do not know about this; only you do.

Using all that information, and a copy of Knuth's "The Art of
Computer Programming", you can write your own allocator that manages
the underlying storage pool efficiently, and also conforms to the
C Standard. Because I do not have that information, I cannot
write it for you. (Besides, I would want to charge consulting
fees. )

You might also look at existing malloc() implementations for existing
systems, such as the various free BSDs and Linux.

my idea was to define a struct, and for
each allocation, the number of bytes allocated
to the pointer, will be saved in the struct.

This is fine so far...

struct ptr
{
void* pointer;
int size;
}

(The type "int" may [or may not] be too small. The one argument
to malloc() has type "size_t", not "int". size_t is some unsigned
type. Since you are the implementor, *you* get to pick which
unsigned type to use.)

the implementation should be as follows:

void* malloc(int size)
{
return malloc_os(size);
}

But this is not. You will need to call the OS function (which
really should not be named "malloc_os", as that name is in the
"user use-able" part of the ANSI/ISO C name space -- you should
use a name that users are NOT allowed to use, such as __os_malloc,
or _OS_malloc, or _Malloc_os, etc.), which will give you some
space in which to save your own data structures, but then you
may (or may not, depending on your system) have to fiddle with
alignment issues.

For instance, on machines that require 16-byte alignment (Intel
x86, with some of the newer extended instructions) but in which
you might store just a 4-byte "size_t", you may have to "waste" as
many as 12 bytes just to get things aligned.

 

[meital]

I think that the following solution is a clean and simple one that will
work in all cases.

Instead of allocating size bytes, allocate size+1 bytes starting at p.
The address which will be returned is p+1, whereas the number of bytes
used for this allocation will be stored in p.

void *malloc(int size)
{
char *p;

p = (char*)malloc_os(size+1);
*p = size+1;

return p++;
}

Later on when it's time to free the memory starting at p,
we will actually free the memory starting at p-1,when the
number of bytes to free is saved in p-1.

void free(void *p)
{
free_os(*(p-1),p-1);
}

How does it sound?

 

[Richard Harter]

I think that the following solution is a clean and simple one that will
work in all cases.

Instead of allocating size bytes, allocate size+1 bytes starting at p.
The address which will be returned is p+1, whereas the number of bytes
used for this allocation will be stored in p.

void *malloc(int size)
{
char *p;

p = (char*)malloc_os(size+1);
*p = size+1;

return p++;
}

Later on when it's time to free the memory starting at p,
we will actually free the memory starting at p-1,when the
number of bytes to free is saved in p-1.

void free(void *p)
{
free_os(*(p-1),p-1);
}

How does it sound?

I suppose all of this is off topic; everything is in clc. That said,
your idea is one that is often used, but, IMHO, is not a good one,
because it makes for a fragile allocator. All it takes is one memory
overwrite and your allocator goes off into la-la land.

 

[Chris Torek]

I think that the following solution is a clean and simple one that will
work in all cases.

Define "all cases"...

Instead of allocating size bytes, allocate size+1 bytes starting at p.
The address which will be returned is p+1, whereas the number of bytes
used for this allocation will be stored in p.

How big are your bytes, and how big is your size_t? If CHAR_BIT
is 8 on your implementation, UCHAR_MAX will be 255. Will size_t
also be "unsigned char", so that (size_t)-1 is 255?

void *malloc(int size)
{

This continues to be wrong, because the argument to malloc() is
a "size_t" -- often an alias for unsigned int, but certainly never
a plain (signed) int.

char *p;

p = (char*)malloc_os(size+1);

The name "malloc_os" is still in the user's namespace.

If this returns "void *" (and is properly prototyped), the cast is
not needed (not that it will hurt). If this returns "void *" but
is not properly prototyped, the cast will shut up a C89 compiler
without fixing the problem ("the problem" being the missing
prototype).

*p = size+1;

This is OK if and only if "size+1" fits in *p. That depends on
the value of CHAR_MAX. If plain char is signed, you may find that
CHAR_MAX is a mere 127. This seems unlikely to be big enough.

return p++;
}

This is definitely wrong. "p++" means "find the value of p, and
compute one more than that value. Store the new, incremented value
some time before the next sequence point, but as the value of the
expression, use the old, non-incremented value". Since you return
the value of the expression, this returns the non-incremented value,
and the incremented "p" is then destroyed by the action of returning.

Just "return p + 1" if you mean to return p + 1. Note, however,
that p+1 is only one byte higher than p, and if your machine requires
(say) 16-byte alignment, it is *your* job to provide that alignment.
(Whether malloc_os() does or not, even!)

Later on when it's time to free the memory starting at p,
we will actually free the memory starting at p-1,when the
number of bytes to free is saved in p-1.

void free(void *p)
{
free_os(*(p-1),p-1);
}

Since "p" has type "void *", pointer arithmetic is not allowed.
The fundamental idea here is not far off though.

How does it sound?

Assuming CHAR_BIT is (say) 32, and all this code is for some DSP
chip, this is likely to work (after correcting malloc() to return
p+1). (Even if plain char is signed, a 32-bit char should be able
to store sizes up to 2147483647.) If not, this is not likely to
work.

We might assume instead that your machine has no alignment constraints
at all, or is such that the OS allocator (which I will call __os_alloc
to keep it out of the user's namespace) returns a "well-aligned"
pointer that remains well-aligned when moving it by sizeof(size_t)
bytes. In this case, your example code is still close to workable.
The rewritten version might look like this:

#include <limits.h>
#include <some non-Standard header that declares __os_alloc etc>

void *malloc(size_t size) {
size_t *p;
size_t os_size;

/*
* Compute the size we want from the OS. Check for
* overflow; return NULL in that case. Also, __os_alloc
* apparently takes only an "int", not a size_t, so
* make sure the request will also fit in a plain int.
*/
os_size = size + sizeof *p;
if (os_size < size || os_size > INT_MAX)
return NULL;

p = __os_alloc(os_size);
/* what does __os_alloc return on failure? */

*p = os_size;

return p + 1;
}

void free(void *p0) {
size_t *p = p0;

__os_free(p[-1], p - 1);
}

Note that if __os_alloc() does not return "well-aligned" pointers,
or if they do not remain well-aligned when moving forward by one
"size_t" object, this will *still* not work. You will need to add
code to align the pointers, and you may need to align both on the
"in" and "out" sides: you may need to align both the value returned
from __os_alloc (which may not be suitably aligned to store the
data structure(s) you want to use to track OS-allocated regions),
and the value you will return to the user.

Many modern CPUs have 8-bit-bytes and 4-byte "size_t"s, but require
8-byte alignment for "double"s. As I noted earlier, x86 CPUs even
require 16-byte (128-bit) alignment for some of the new instructions
(SSE). Thus, there is a good chance the above is *not* sufficient.
It all depends on the underlying system.

 

[meital]

Thanks a lot. It seems to be that you referred to
every possible case. Cases ,which I admit, didn't even
cross my mind. I read carefully your notes, and they were
all somehow relevant and helpful.