memory allocation wrapper

[goose]

Hello all

I've written a wrapper for malloc and friends. Its
available from

http://www.lelanthran.com/downloads/os_mem/index.php

The reason for doing writing this so that newbies
can finally get answers to the following
newbie questions:
1. How do I know how much memory a pointer points to?
2. How can I tell if a pointer is valid?

I know most of the regs don't need this, but be
a good samaritan and point out the bugs

Comments and criticisms(sp?) welcome; note that it aims
for c99 compliance only.

goose,

 

[Malcolm]

Hello all

I've written a wrapper for malloc and friends. Its
available from

http://www.lelanthran.com/downloads/os_mem/index.php

The reason for doing writing this so that newbies
can finally get answers to the following
newbie questions:
1. How do I know how much memory a pointer points to?
2. How can I tell if a pointer is valid?

I know most of the regs don't need this, but be
a good samaritan and point out the bugs

Comments and criticisms(sp?) welcome; note that it aims
for c99 compliance only.

goose,

There's a much easier way of achieveing what you want to do.
Simply put a structure at the start of the allocated memory, add your
control information, and return the pointer immediately after.
Then when the user calls the free, subtract the size of the control
structure, and free. Similarly for the access functions.

There is a niggly snag. malloc() must return memory aligned for any purpose.
In practise you can get "good enough" portability by padding your structure
out to an even number of doubles. In standards land, you risk the horrors of
UB, and there is no way of achieving a fully compliant program in ANSI C.

 

[Ancient_Hacker]

Hello all

Good start. You might consider adding:

(1)A sentinel field, say a char[4] == 'HEAP' before and after each
block, so you can detect block write overruns.

(2) Have your free() zero out the block data, to ensure the program
won't continue running okay even if it accesses the data after the
pointer is freed.

(3) make your free() a macro, so you can append a "ptr = NULL"
statement sot he user can't use a dangling pointer.

 

[websnarf]

I've written a wrapper for malloc and friends. Its
available from

http://www.lelanthran.com/downloads/os_mem/index.php

The reason for doing writing this so that newbies
can finally get answers to the following
newbie questions:
1. How do I know how much memory a pointer points to?
2. How can I tell if a pointer is valid?

I know most of the regs don't need this, but be
a good samaritan and point out the bugs

It look fairly sound, but I did not look that deeply at it. I just
can't get out of my head the serious performance problems! find_ptr is
O(#allocations), which is just brutal!

Comments and criticisms(sp?) welcome; note that it aims
for c99 compliance only.

Ok, since you are going for "C99" then why don't you use stdint.h? (In
fact, why don't you use pstdint.h, which you can find here:
http://www.pobox.com/~qed/pstdint.h ?)

With (p)stdint.h you can cast pointers to uintptr_t. This means you
can put a metric on pointers and thus sort and hash them. Without
this, I think this would just be too costly to be used by anyone.

 

[goose]

There's a much easier way of achieveing what you want to do.
Simply put a structure at the start of the allocated memory, add your
control information, and return the pointer immediately after.
Then when the user calls the free, subtract the size of the control
structure, and free. Similarly for the access functions.

I did initially have it this way but I wasn't able to
figure out how determine if a pointer is valid. The other
things I wanted was to be able to tell at any given time
how much total memory the program is using and to allow
the program to free all allocated memory.

The last (and most important) reason I did it this way
is because I'm designing my own language[1] and implementing
it in C and would like to have my language automatically GC.

Within My Own Toy Language if I only use os_mem_* functions
I can implement the gc much easier.


[1] Every programmer goes through the phase of thinking
"surely there must be a better way" and then goes off
designing their own language with all the nifty features
they'd like to have. It's probably a rite of passage, or
something

goose,

 

[Ben Pfaff]

(2) Have your free() zero out the block data, to ensure the program
won't continue running okay even if it accesses the data after the
pointer is freed.

Clearing data to some value other than zero is probably better.
Zero is often a valid value for data and so it doesn't cause as
many problems as might be wanted.

(3) make your free() a macro, so you can append a "ptr = NULL"
statement sot he user can't use a dangling pointer.

The argument to free() is not necessarily an lvalue.

 

[Clark S. Cox III]

Hello all

Good start. You might consider adding:

(1)A sentinel field, say a char[4] == 'HEAP' before and after each
block, so you can detect block write overruns.

(2) Have your free() zero out the block data, to ensure the program
won't continue running okay even if it accesses the data after the
pointer is freed.

Some other value is probably better than zero; something more
recognizable like 0xDEADBEEF

(3) make your free() a macro, so you can append a "ptr = NULL"
statement sot he user can't use a dangling pointer.

Not a good idea; this will just hide errors.

 

[Malcolm]

I did initially have it this way but I wasn't able to
figure out how determine if a pointer is valid. The other
things I wanted was to be able to tell at any given time
how much total memory the program is using and to allow
the program to free all allocated memory.

Have a member called void *me which points to the structure itself. Then on
free check that this member is intact.
On a 4GB system you have only a 1 in 4 billion chance of being wrong. Shred
the pointer on free to avoid being freed twice.

 

[Flash Gordon]

Hello all

Good start. You might consider adding:

(1)A sentinel field, say a char[4] == 'HEAP' before and after each
block, so you can detect block write overruns.

(2) Have your free() zero out the block data, to ensure the program
won't continue running okay even if it accesses the data after the
pointer is freed.

Some other value is probably better than zero; something more
recognizable like 0xDEADBEEF

(3) make your free() a macro, so you can append a "ptr = NULL"
statement sot he user can't use a dangling pointer.

Not a good idea; this will just hide errors.

On which topic, on attempting to reallocate something not allocated
through your code you should at least print an error to stderr or even
abort the program. The same applies to freeing of course.

Your (goose) check for sorted pointers is not valid. You can only use
the relational operators (e.g. <) on pointers to the same object or one
past the object, not on pointers to different objects. Personally I
would just scrap the bit about unsorted pointers since I can't see the
value of it.

Other than that and the points others have made it looks like a good start.

 

[goose]

Hello all

<snipped original announcement>

Hello all

I've summarised the replies here so that I could
reply to all without scattering the replies through
the thread.


---------------------------------------------------------------

Malcolm replied:
>Have a member called void *me which points to the structure itself. Then on
>free check that this member is intact.
>On a 4GB system you have only a 1 in 4 billion chance of being wrong. Shred
>the pointer on free to avoid being freed twice.
>

Certainly the odds are low, but I feel a little
uncomfortable knowing that every 4 billion pointers[1]
the valid() function is certain to succeed even
when the pointer is invalid.

[1]I'm not all that sure that that really is the
probability anyway. A more practical probability
is sure to be less than that due to me using
up addresses in os_mem itself.

---------------------------------------------------------------

>Good start. You might consider adding:
>
>(1)A sentinel field, say a char[4] == 'HEAP' before and after each
>block, so you can detect block write overruns.
>

A sentinel is a good idea; I might add that in
(although its bound to never be 100% reliable).

The other two points sufficiently covered by
Ben Pfaff downthread.

---------------------------------------------------------------

>> Ancient_Hacker wrote:
>>

>>> goose wrote:
>>>
>>>> Hello all
>>>
>>> Good start. You might consider adding:
>>>
>>> (1)A sentinel field, say a char[4] == 'HEAP' before and after each
>>> block, so you can detect block write overruns.
>>>
>>> (2) Have your free() zero out the block data, to ensure the program
>>> won't continue running okay even if it accesses the data after the
>>> pointer is freed.

>>
>>
>> Some other value is probably better than zero; something more
>> recognizable like 0xDEADBEEF
>>

>>> (3) make your free() a macro, so you can append a "ptr = NULL"
>>> statement sot he user can't use a dangling pointer.

>>
>>
>> Not a good idea; this will just hide errors.

>

[I've reformatted this to shorter line lengths]

>
>On which topic, on attempting to reallocate something not
>allocated through your code you should at least print an
>error to stderr or even abort the program. The same applies
>to freeing of course.

I agree, an attempt to realloc invalid pointer should be
handled more seriously (as it means the caller seriously
mixed up his pointers and there is probably more wrong
than simply reallocing a buffer not allocated by os_mem).

I think perhaps a callback in the init() function, or
raising a signal should be sufficient. Not really a good
idea to abort the program without letting the caller
clean up (close files, notify user, etc). Printing to
stderr might confuse the user without helping the
caller too much.

Obviously I need to put more thought into this.

>
>Your (goose) check for sorted pointers is not valid. You can
>only use the relational operators (e.g. <) on pointers to the
>same object >or one past the object, not on pointers to
>different objects. Personally I would just scrap the bit
>about unsorted pointers since I can't see the value of it.

Well, neither could I, which is why it is in (I wanted the
list of pointers to be sorted so that find_ptr has reasonable
running time) but unused. I suppose I really should remove it,
but I'll need to make changes so that find_ptr has better
running time.

>
>Other than that and the points others have made it looks like a good
>start.

Thanks


---------------------------------------------------------------

>
>
>It look fairly sound, but I did not look that deeply at it. I just
>can't get out of my head the serious performance problems! find_ptr is
>O(#allocations), which is just brutal!
>

Yes, I knew that when I wrote it :-(. I was banking on
the caller not using memory routines in any time-critical
part of the program as malloc and friends generally are
quite time-intensive anyway. The reason it got written that
way was because I figured I'd profile and optimise
later when I used this in any real project.

>
>
>
>Ok, since you are going for "C99" then why don't you use stdint.h? (In
> fact, why don't you use pstdint.h, which you can find here:
> http://www.pobox.com/~qed/pstdint.h ?)
>

I'm not familiar with pstdint.h.

>With (p)stdint.h you can cast pointers to uintptr_t. This means you
>can put a metric on pointers and thus sort and hash them.

I'll give it a quick look this coming week. Thanks for the
response though.

>Without
>this, I think this would just be too costly to be used by anyone.
>

Well, a quick way to speed up the implementation of find_ptr
would be to search from the beginning and the end of the array
at the same time (in the same loop); this will effectively
halve the running time of find_ptr. Makes it O(n/2) instead
of O(n). I'll profile before and after making this change
(and add a file detailing the profiling in with the rest
of the project). If it is still unacceptable, then I'll
investigate the hash solution.

---------------------------------------------------------------
Thanks to all for your comments; I'll do the best I can
to follow them and where I don't I've explained above.
If i've not replied to your post in this post, that means
I agree with you .

I'll update os_mem, repost to my website and let you
all know when it's ready for criticisms again (probably
only next weekend).

Later
goose,
ps. I've also decided to change the licence from
GPL to BSD; this allows the user to freely incorporate
os_mem into closed code while keeping their code
closed.

 

[CBFalconer]

I've summarised the replies here so that I could
reply to all without scattering the replies through
the thread.

.... large snip ...

Why don't you take a look at the methods I use in malldbg to detect
invalid structure in nmalloc. This is all contained in my
nmalloc.zip package, available for DJGPP at:

<http://cbfalconer.home.att.net/download/>

Basically validation is a dynamic thing, walking the known heap
structure and looking for disagreements between lengths and
next/prev pointers. There is also provision for maintaining
markers, of the 0xdeadbeef variety.

Conceded, this is not the same thing as validating a pointer
candidate in user space, but it does yield a comprehensive list of
valid pointers. Also, the methods used are not portable, but are
suited to systems with similar memory organization to DJGPP, which
is most OSs today.