Tom Locke wrote:
> Thanks for this - I hadn't come across it before. I would guess that these
> pools are contiguous blocks of (virtual) memory which means you have to
> commit to a maximum size in advance.
>
> I was thinking more along the lines of a graph structure where each node is
> separately allocated from the main heap, but pointers are managed so that
> they can never be used outside of their own graph. This may require a 'graph
> id' to be kept with each pointer so that they can't be used out of place,
> which is a cost I'd like to avoid.
>
> Maybe the memory pool is a better idea - let the virtual memory system do
> the work.
See http://www.apache.org/docs/misc/API.html#pools for Apache pool description.
I've attached alloc.h (from Apache 1.3.9 as it happens) for your info. Looking
at ap_palloc (below), you'll notice that it takes a pool and a size as its
arguments. It returns a pointer to memory on the heap, for which the reference
in the pool ensures that free will be called later. A pool structure is a node
in a graph that links to its peers, its parent pool and its children pools.
struct pool {
union block_hdr *first;
union block_hdr *last;
struct cleanup *cleanups;
struct process_chain *subprocesses;
struct pool *sub_pools;
struct pool *sub_next;
struct pool *sub_prev;
struct pool *parent;
char *free_first_avail;
#ifdef ALLOC_USE_MALLOC
void *allocation_list;
#endif
};
API_EXPORT(void *) ap_palloc(struct pool *a, int reqsize)
{
#ifdef ALLOC_USE_MALLOC
int size = reqsize + CLICK_SZ;
void *ptr;
ap_block_alarms();
ptr = malloc(size);
if (ptr == NULL) {
fputs("Ouch! Out of memory!\n", stderr);
exit(1);
}
debug_fill(ptr, size); /* might as well get uninitialized protection */
*(void **)ptr = a->allocation_list;
a->allocation_list = ptr;
ap_unblock_alarms();
return (char *)ptr + CLICK_SZ;
#else
... home-grown alternative to malloc
#endif
}
Because of the use of linked lists/trees in this way, the pools are not of a
fixed size. Freeing a pool is not as simple as freeing a contiguous span of
memory because each pool node must be scanned and its allocation lists freed
element by element. So that leaves quite a lot of defragmentation to contend
with.
The simpler approach of contiguous spans of memory, like mini-heaps, would cut
down greatly on heap fragmentation, provided that the problem of having
fixed-size spans could be handled cleanly.
I have to confess that I'm rather a novice when it comes to advanced memory
allocation techniques. My colleagues here sometimes launch into complex
descriptions that leave me bewildered! Certainly, there is a considerable body
of prior art in the C world. But they are usually interested in moderately
general memory systems (as per Apache request handling) rather than the
deliberately circumscribed memory model that Tom is looking into. I am eagerly
looking forward to what Tom is able to achieve with a clean sheet of ideas
approach (but don't feel under too much pressure, eh Tom! ;-)
Rick
----
PS this message only sent to one list.
Attachment:
alloc.h
Description: application/unknown-content-type-hfile
begin:vcard n:Beton;Richard tel;pager:ICQ: 56840977 tel;cell:MSN/Hotmail: richardbeton@xxxxxxxxxxx tel;fax:01794 833434 tel;work:01794 833458 x-mozilla-html:TRUE url:http://www.beton.freeserve.co.uk/ org:Roke Manor Research Limited;Internet Technology & Networks adr:;;Roke Manor: http://www.roke.co.uk/;;;SO51 0ZN;UK version:2.1 email;internet:richard.beton@xxxxxxxxxx title:Internet Consultant note;quoted-printable:The information contained in this e-mail is confidential and must =0D=0Anot be passed to any third party without permission. This =0D=0Acommunication is for information only and shall not create =0D=0Aor change any contractual relationship. =0D=0A fn:Rick Beton end:vcard