How does free() knows?

[Gordon Burditt]

Another method is to supply the size of the target in

You'd need an offset along with the base address and size. For

Why? Not for just carrying the block size in the pointer.

example, the following is valid:

char *p = malloc(100);
char *q = p + 10;
free(q - 10);

If the information needed by free() is going to be stored in the
pointer, then q has to retain enough information to get back to the
base address of the allocated object.

If incrementing p modifies only the address, and leaves alone the
block size, and decrementing q modifies only the address, and leaves
alone the block size, then the above will still work, without needing
an offset.

Passing q (not q - 10) directly to free() invokes undefined behavior,
and the fact that q contains a block size that is not accurate for
the address in q doesn't make the problem any worse. It's already
as bad as it gets.

Either the "address" field of q
points to the base of the allocated object, with an offset of 10, or
the "address" field points directly to p[10] and the offset is -10;
the latter scheme might make for more efficient code.

You don't need an offset field.

This also gives you the possibility of run-time bounds checking.

Run-time bounds checking does require the offset field, but it
isn't a requirement for passing the block size in the pointer.

Gordon L. Burditt

 

[Matthew Fisher]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

Most standard allocators do not keep track of the size! They just
keep an ordered alloc/free list. The point is to make the allocator
fast.

The downside of this strategy is that free is totally error prone.
Free'ing the same block twice will corrupt the heap, free'ing a stack
value or global value will corrupt the heap, free'ing a misaligned ptr
will corrupt the heap, etc, etc.

My company, Dynamic Memory Solutions, markets Dynamic Leak Check that
checks for these sorts of errors, www.dynamic-memory.com. Dynamic Leak
Check has a custom allocator that catches error but is significantly
than the standard allocator.

Matthew
Dynamic Memory Solutions
www.dynamic-memory.com

 

[Keith Thompson]

Why? Not for just carrying the block size in the pointer.


If incrementing p modifies only the address, and leaves alone the
block size, and decrementing q modifies only the address, and leaves
alone the block size, then the above will still work, without needing
an offset.

Passing q (not q - 10) directly to free() invokes undefined behavior,
and the fact that q contains a block size that is not accurate for
the address in q doesn't make the problem any worse. It's already
as bad as it gets.

You're right. I was thinking in terms of an error-checking free(),
which of course is not required.

The suggested approach would mean that a lot of pointers would be
carrying a meaningless block size. An implementer adding this kind of
information to pointers probably might as well add an offset as well,
so it's useful for error checking, but it's not required.

 

[CBFalconer]

I wish to know how the free()function knows
how much memory to be freed
as we only give pointer to allocated memory as an argument to free().
Does system use an internal variable to store allocated memory
when we use malloc().

It depends upon the implementation.
Try this:

cat main.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
if (1 < argc) {
const
size_t n = atoi(argv[1]);
int* p = (int*)malloc(n*sizeof(int));
fprintf(stdout, "%d = p[-1]\n", p[-1]);
}
return 0;
}

gcc -Wall -std=c99 -pedantic -o main main.c
./main 1

17 = p[-1]

.... snip ...

Don't try this. It invokes undefined behavior and other poor
programming practices and is meaningless in portable C. In
addition Trollsdale seems to have deliberately attempted to
maximize annoyance by cross-posting to c.l.c++ where it is even
further OT.

Maybe we should save this as a horrible example to show to his
alleged superiors at JPL. We probably don't have to, google will
archive it. How many NASA shots has he destroyed so far?

 

[CBFalconer]

.... snip ...

Most standard allocators do not keep track of the size! They just
keep an ordered alloc/free list. The point is to make the allocator
fast.

Nonsense. There is no such thing as a standard allocator.

The downside of this strategy is that free is totally error prone.
Free'ing the same block twice will corrupt the heap, free'ing a stack
value or global value will corrupt the heap, free'ing a misaligned ptr
will corrupt the heap, etc, etc.

Which is why any implementor worth a grain of salt will make a
better system.

My company, Dynamic Memory Solutions, markets Dynamic Leak Check that
checks for these sorts of errors, www.dynamic-memory.com. Dynamic Leak
Check has a custom allocator that catches error but is significantly
than the standard allocator.

Matthew
Dynamic Memory Solutions
www.dynamic-memory.com

I suggest you improve your knowledge before selling your software.

 

[Percival]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

A simple implementation, one of many solutions.

char memory[0x2000]; //in real code, this would
// point to all the availiable memory in the area.
// this char array will represent the memory availiable

int mem_size = 0x2000;

struct Header{
struct Header *next;
int size;
};

struct Header start;
start.next = NULL;
start.size = mem_size;

void *malloc(int size){
struct Header *i;
//find first availiable block
// Dont use this
// just an example code that i typed up without testing
for(i = &start; size > i->size && i!=NULL ; i = i->next);

//change the header values to reflect what we have
i->size -= (size + sizeof(Header));

//create a new header at the end
struct Header *toreturn = (struct Header *)((int)i + i->size);
toreturn->size = size;
toreturn->next = NULL; //Null means block is used

//return a pointer to the end of the header, allocate from
// back to the front
return toreturn + sizeof(Header);
}

void free(void * tofree){
struct Header h = (int) tofree - sizeof(Header);
struct Header i;

//find the end of the linked list
for(i=start; i.next!=NULL; i = i->next);


//add this block to the linked list
i->next = h;
h->next = NULL;
}

Note, the method i posted is a truely horrible code, but it is like that
for simplicity because it is easier for me to type, and second, you
probably understand it more without all the checks. There are a number
of things that will definitly go wrong if the code is used, so don't
bother trying.

 

[Ben Noordhuis]

Please use the conventional "> " prefix for quoted text.
Please keep your lines down to about 72 columns.
Please use the standard "-- " signature delimiter.

I don't believe that an implementation of free() that does nothing
would be acceptable. The "terabytes of VM" you're talking about are
typically stored on disk; if you allocate more than the amount of
physical memory, your program is going to slow down as it swaps data
between disk and memory. For that matter, you're likely to slow down
the entire system, and you'll still run out eventually.

I work on some pretty big systems; they typically have no more than a
few gigabytes of virtual memory.

Even assuming terabytes of fast, cheap virtual memory and a full
64-bit address space, consider a program that does something like
this:

while (1) {
/* allocate a few megabytes of memory */
/* do some work */
/* free the allocated memory */
}

(Think of a server or a system daemon that runs continuously for
months at a time.) If free() does nothing, this is a serious memory
leak which will crash the program and/or bog down the system.

Fortunately, I don't believe that anyone has actually implemented such
a system.

Even if there ever comes an architecture into existence with such
mind-boggling amounts of memory that it really wouldn't matter if
/free()/ actually does what it's name suggests or just merely returns,
I don't think the psychology of real system programmers would allow
them to implement it like that: the thought of such a leak would come
back to haunt their dreams, making them grow old before their time. I
know it would for me ;-)

 

[Nick Landsberg]

Please use the conventional "> " prefix for quoted text.
Please keep your lines down to about 72 columns.
Please use the standard "-- " signature delimiter.

I don't believe that an implementation of free() that does nothing
would be acceptable. The "terabytes of VM" you're talking about are
typically stored on disk; if you allocate more than the amount of
physical memory, your program is going to slow down as it swaps data
between disk and memory. For that matter, you're likely to slow down
the entire system, and you'll still run out eventually.

I work on some pretty big systems; they typically have no more than a
few gigabytes of virtual memory.

Even assuming terabytes of fast, cheap virtual memory and a full
64-bit address space, consider a program that does something like
this:

while (1) {
/* allocate a few megabytes of memory */
/* do some work */
/* free the allocated memory */
}

(Think of a server or a system daemon that runs continuously for
months at a time.) If free() does nothing, this is a serious memory
leak which will crash the program and/or bog down the system.

Fortunately, I don't believe that anyone has actually implemented such
a system.

Keith,

I work in a shop which specializes in implementing just such
systems.

Planned reboots at 3 month intervals for some customers,
6 month intervals for others. If free() did nothing,
we would be dead in the water. Stress testing (at full
load) is used to verify zero net memory growth over a period of
at least 72 hours (and, in some cases, 14 days).

This is probably "not your average system" but about a
dozen applications have been built to this tolerance
over the last 5 years or so.

It ain't easy

NPL

 

[CBFalconer]

.... snip ...

I don't believe that an implementation of free() that does nothing
would be acceptable. The "terabytes of VM" you're talking about
are typically stored on disk; if you allocate more than the amount
of physical memory, your program is going to slow down as it swaps
data between disk and memory. For that matter, you're likely to
slow down the entire system, and you'll still run out eventually.

I think I've got a TV remote that is programmed like that.
Periodically it hangs with an activity led on, and the only cure
is to remove the batteries and reinsert them. The other choice is
to let the led run the batteries down to nothing It didn't
come with rebooting instructions!

 

[Richard Tobin]

Even assuming terabytes of fast, cheap virtual memory and a full
64-bit address space, consider a program that does something like
this:

while (1) {
/* allocate a few megabytes of memory */
/* do some work */
/* free the allocated memory */
}

In fact, *this* program will work well with no-op-free() in a virtual
memory system with effectively infinite swap space. The unused memory
will be paged out and have no effect on the running of the program.

The trouble is that real programs are rarely as neat as the one above.
They often free most, but not all, of the recently allocated memory,
and continue to access the other bits of it. So the active memory
becomes fragmented, and pages (VM systems work in page units)
containing only small pieces of active data will be copied in and out.
That is, the program needs good locality of reference for the technque
to work.

Fortunately, I don't believe that anyone has actually implemented such
a system.

There was a time when people talked about "DDI garbage collection" for
Lisp machines: DDI stood for "don't do it". The theory assumed that
you had to reboot those machines every few days anyway. I don't
recall whether it was ever used in practice.

-- Richard

 

[Keith Thompson]

In fact, *this* program will work well with no-op-free() in a virtual
memory system with effectively infinite swap space. The unused memory
will be paged out and have no effect on the running of the program.

Sure, it will work if the system has effectively infinite swap space.
Unfortunately, no such system exists. Note that I was assuming mere
terabytes of VM; that's no more effectively infinite than 640
kilobytes is.

I suppose all you really need is more virtual memory than all the
programs running on the system will be able to consume before the
hardware is expected to fail. A few exabytes might be sufficient.
That much storage could be useful for other reasons, but I think it's
easier and cheaper to write a working free() function.

(It's even easier to design a system that's expected to fail before it
can consume much virtual memory, but that's probably not the best
solution.)

 

[Peter Koch Larsen]

Sure, it will work if the system has effectively infinite swap space.
Unfortunately, no such system exists. Note that I was assuming mere
terabytes of VM; that's no more effectively infinite than 640
kilobytes is.

I suppose all you really need is more virtual memory than all the
programs running on the system will be able to consume before the
hardware is expected to fail. A few exabytes might be sufficient.
That much storage could be useful for other reasons, but I think it's
easier and cheaper to write a working free() function.

(It's even easier to design a system that's expected to fail before it
can consume much virtual memory, but that's probably not the best
solution.)

Well... that used to be the option of one company providing us with a quite
popular OS.

 

[tom_usenet]

Really? That sounds like it could be terribly inefficient -- a
program that allocates only chunks of a certain size could run out of
memory when there's still plenty left in another region.

That's not going to be a problem with a 64-bit address space - far
more memory can be addressed than is available, even if you give up
two bytes of your pointer to tell you the block size.

Tom

 

[Benjamin Ketcham]

That's not going to be a problem with a 64-bit address space - far
more memory can be addressed than is available, even if you give up
two bytes of your pointer to tell you the block size.

Oh, *dear*. Here we go with MacOS again!

If you have a 64-bit address space, is it *really* going to be
that expensive to keep the block info somewhere else? Do you
*really* need to munge-up the pointers? Especially given that
many 64-bit-address-space machines will really have 128-bit
(or wider) paths to memory, so with some care, you will still
be able to grab the full "fat pointer" in one cycle?

And where are you planning to pay for the extra expense of
packing and unpacking these munged pointers? In hardware?
Or in software? Lose, lose.

And are you sure that two bytes is enough for the block size?
If you're so full of need for a huge address space, mightn't you
also need a wide range of block sizes? Two bytes would
(naively speaking) limit you to 64K objects. Gee, do you
work for Bill?

And while 64 bits seems like an unimaginable amount of address
space, once you start pecking away at it like this, it doesn't
take long to whittle down to something rather closer to the
imaginable: you are proposing reducing it to a 48-bit space
(are you *sure* you don't work for Bill?). I.e., only 64K times
larger than what has already proven to be too small, as of
several years ago. OS architectures tend to outlast hardware
architectures, if they're any good (or even not!). The designers
of the original Mac may have been correct that nobody would ever
max out the 32-bit address space on a 68000 Mac I, but later Macs
of course approached and then crossed the 4G barrier.
Fortunately, Apple (or *somebody* at Apple) was smart enough to
aggressively redesign the underlying software, rather than start
hanging bags off the side like (here he is again) Mr. Bill.

Those who cannot remember the past...

My prediction is that the freedom of 64-bit address spaces
(without stupid constraints imposed by short-sighted bit-twiddlers)
will lead to new and different schemes of memory management.
An individual program may not need 4G^2 of memory space any time
soon, but I bet OS kernels will find ways to use the space, especially
given massively parallel systems where many CPUs and thousands or millions
of concurrent processes are accessing the same address space.

--Benjamin

 

[Gordon Burditt]

Those who cannot remember the past...

My prediction is that the freedom of 64-bit address spaces
(without stupid constraints imposed by short-sighted bit-twiddlers)
will lead to new and different schemes of memory management.
An individual program may not need 4G^2 of memory space any time
soon, but I bet OS kernels will find ways to use the space, especially
given massively parallel systems where many CPUs and thousands or millions
of concurrent processes are accessing the same address space.

It wouldn't surprise me if at some point there is one memory space addressed
by a rather large pointer (but, there will be a lot of access restrictons, and
access to some memory can be rather slow, especially the memory on space probes
near Neptune):

128 bits: IPv6 address of host
64 bits: drive number (RAM gets its own "drive")
64 bits: cylinder number
32 bits: head number
32 bits: sector number
16 bits: byte (or bit) number within a sector
64 bits: Planetary Area Network number [ 1 = SOL ]
112 bits: reserved for expansion (alternate universe number?)
___________
512 bits total

Think of the opportunity for virus writing!

Gordon L. Burditt

 

[kal]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

Another question is:
"How does malloc() know about memory that can be safely allocated?"

 

[Gordon Burditt]

I wish to know how the free()function knows how much memory to be

Another question is:
"How does malloc() know about memory that can be safely allocated?"

It likely has a (undocumented and system-specific) call to the OS to
ask for memory from the OS. Either that or the implementation
just knows (anything from the end of the so-called data-section to
the end of physical memory is fair game. The CP/M convention was that
anything from the end of loaded data to the beginning of the OS (findable
by a pointer down in low memory) was free when a program started).

Gordon L. Burditt

 

[Keith Thompson]

(e-mail address removed) (Suyog_Linux) wrote in message


Another question is:
"How does malloc() know about memory that can be safely allocated?"

And the answer is exactly the same: it depends on the system.
Different systems will do this in different ways. If you're
interested in the details for some particular system, you'll need to
ask in a newsgroup dedicated to that system.

 

[CBFalconer]

It likely has a (undocumented and system-specific) call to the OS
to ask for memory from the OS. Either that or the implementation
just knows (anything from the end of the so-called data-section
to the end of physical memory is fair game. The CP/M convention
was that anything from the end of loaded data to the beginning of
the OS (findable by a pointer down in low memory) was free when a
program started).

My CP/M systems used that to set the stack, and the heap grew up
until it met the stack (with a safety margin). That way
everything adapted. Stack allocation that ran into the heap also
aborted.

 

[Dave Thompson]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

A simple implementation, one of many solutions.

char memory[0x2000]; //in real code, this would
// point to all the availiable memory in the area.
// this char array will represent the memory availiable

int mem_size = 0x2000;

struct Header{
struct Header *next;
int size;

size_t, or at least unsigned long, is better for memory sizes.

};

struct Header start;
start.next = NULL;
start.size = mem_size;

A declared variable like that cannot be located in the same place as
memory, nor occupy all "available memory". You probably want a start
_pointer_ which is somehow (unportably) set to point to "memory".

And that initializing has to be in executable code; you can't write
statements at file scope (C++ namespace scope). Although in C++ if it
were (could be) a declared object you could write an initialization
using/matching any (accessible) constructor.

And the rest of your code treats Header.size as not including itself,
so that should be mem_size - sizeof(struct Header).

void *malloc(int size){

Same about size_t.

struct Header *i;
//find first availiable block
// Dont use this
// just an example code that i typed up without testing
for(i = &start; size > i->size && i!=NULL ; i = i->next);

Need to test i!=NULL _before_ testing i->size.

An empty statement as a loop body is legal but often flagged as
suspicious by tools or readers/reviewers because it is commonly done
by mistake. Suggest /*noop*/; or { } or {/*noop*/} .

If exit loop with (because) i == NULL return NULL or take other
failure action, don't continue.

//change the header values to reflect what we have
i->size -= (size + sizeof(Header));

In C a struct tag is not automatically a typename; have to write
'struct Header' (and elsewhere) unless you also typedef it.

Can't leave a remainder block if i->size - size is > 0 but <
sizeof(struct Header). In that case one solution is to overallocate,
but to do that you must remember the _previous_ list entry so you can
splice out. Alternatively, can select only a breakable free block with
i->size >= size /* rounded up, see below */ + sizeof(struct Header)

//create a new header at the end
struct Header *toreturn = (struct Header *)((int)i + i->size);

Better (char*)i + i->size. int is not guaranteed large enough to
represent all pointers, even all data pointers. long or unsigned long
is more likely, and C99 [unsigned] long long even more, but still not
guaranteed. In C99 intptr_t is guaranteed if it exists, but is not
required to exist.

On machines that require alignment, the result is not guaranteed to be
correctly aligned for a struct Header, nor for that matter to be used
as a data block. Easiest is to just round 'size' up to a multiple of
the maximal alignment on entry, also increase sizeof(struct Header) to
a multiple if necessary, and for your shave-off-end approach start
with a pool that is a multiple initially.

toreturn->size = size;
toreturn->next = NULL; //Null means block is used

//return a pointer to the end of the header, allocate from
// back to the front
return toreturn + sizeof(Header);

toreturn + 1 or (char*)toreturn + sizeof(struct Header).

}

void free(void * tofree){
struct Header h = (int) tofree - sizeof(Header);

Should be a pointer *h, and again (char*) and sizeof(struct Header).

struct Header i;

Pointer *i.

//find the end of the linked list
for(i=start; i.next!=NULL; i = i->next);
i->next, and again empty body.

//add this block to the linked list
i->next = h;
h->next = NULL;

Redundant, you already did this in malloc().

}

Note, the method i posted is a truely horrible code, but it is like that
for simplicity because it is easier for me to type, and second, you
probably understand it more without all the checks. There are a number
of things that will definitly go wrong if the code is used, so don't
bother trying.

Like the fact that without coalescing, and especially since you keep
the (only) big block at the head of the list, you will quickly get
fragmentation into tiny blocks that are less and less likely to be
(re)usable for anything.

- David.Thompson1 at worldnet.att.net