Area Memory Allocation

[brian at bradley.UUCP]

  Several weeks ago I outlined a scheme in which a code would be added to
the header that malloc maintains for every block on the heap. After calling
malloc(), A mark() function could be called to set the code. Later, other
functions could use the code number to identify blocks. You could free
all the blocks with the same code, print out the sizes of all the blocks
with the same code, etc...

  Several people suggested changes/extensions to this idea.  Here I present
a summary of the responses posted, and a proposal for how I plan to implement
this module.

  raeburn at athena.mit.edu suggested that the malloc() and mark() functions
be combined:

    /* Written  5:59 am  May 23, 1988 by raeburn at athena.mit.edu */
    > How about combining these steps?  Or letting the allocator dynamically
    > assign the code number?  I think PL/I does something like this.
    >
    > A C/UNIX variant could probably be implemented with an internal design
    > similar to what you're already doing.
    > 
    > 	typedef struct _area {
    > 		struct _area *next;
    > 		/* data relating to allocations */
    > 	} *area;
    > 
    > 	area create_area (void);
    > 	void * allocate (size_t size, area a);
    > 	void release (void * ptr);
    > 	void free_area (area a);
    > 

  henry at utzoo.uucp writes that this could be implemented on top of
malloc(), without re-writing the storage allocator:

    /* Written  4:16 pm  May 25, 1988 by henry at utzoo.uucp */
    > There is no need to mess with the insides of malloc for this.  It is
    > really pretty easy to implement a scheme in which you get an "area" by
    > calling newarea() and then get data "within" the area by calling, say,
    > areaalloc() with the area and the size you want.  The area is in fact
    > a data structure which keeps pointers to everything you allocate through
    > it.  areaalloc() just invokes malloc() and adds a pointer to the result
    > to the area.  You can then deallocate everything in the area by calling
    > a function that just goes through the area calling free() on everything.
    > Note that the "area" doesn't actually correspond to a contiguous block
    > of storage, despite its name.
    > 
    > You can add arbitrary bookkeeping to the area functions easily.  The
    > major advantage is this stuff can be fully portable, which the insides
    > of malloc (and hence, changes to the insides of malloc) are *NOT*.

  chris at mimsy.UUCP suggests adding the following functions to the
"area allocator":

    > 	void a_snapshot(FILE *outf);
    > 
    > might produce a list of all allocated blocks, their sizes, and
    > their identifiers.
    > 
    > If you decide it would be worthwhile, it would be easy enough
    > to add a `find named area' routine:
    > 
    > 	area a_find(char *identifier);
    > 
    > which would make freeing someone else's trash easier:
    > 
    > 	a_freeall(a_find("jow bloe/lawnmower data"));


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


  I plan to implement this in the following manner:


  Multiple blocks on the heap will be grouped into an area. An area
will have some information identifying it. This information can be
of any type desired. For example, if you wished to mark the areas
with a string, the following line would be used in the header file:

typedef char * a_info_t;

  All the areas will be internally maintained in a linked list. All the
blocks on the heap "belonging" to an area will be stored in a linked list.
The area structure is as follows:

#define A_AREA struct a_area
A_AREA
  {
  A_AREA *next;			/* pointer to next A_AREA		*/


  A_HEADER *first;		/* pointer to first block in the heap	*/					/* which "belongs" to this area		*/

  a_info_t  info;		/* information identifying this area	*/
  };

  The blocks on the heap which belong to an area have the following
structure attached to them:

#define A_HEADER struct a_header
A_HEADER
  {
  A_HEADER *next;		/* pointer to next block on the heap	*/
				/* that belongs to the same area	*/

  size_t size;			/* size of this block. On most		*/
				/* implementations, this will be	*/
				/* obtainable from the header that	*/
				/* malloc attaches to the block		*/
  };


  The interface will consist of the following functions:


A_AREA *a_create(a_info_t info);

  This function will create a new A_AREA structure, add it to the linked
list of areas, and copy the identifying information into it.

  
void *a_alloc(size_t sz, A_AREA *area);

  This will be used instead of malloc(). It will allocate a block of
memory on the heap, and make it a member of the area passed as the
second parameter.


void a_free(void *p);

  This will free blocks allocated with a_alloc(). One must be very careful
to call a_free(), not free(), on blocks that were allocated with a_alloc().
  

int a_destroy(A_AREA *area);

  This function will destroy an area that was created with a_create().
It will call a_free() on any blocks that belong to the area. a_destroy()
returns a count of how many blocks belonged to the area.

  If a_destroy() is passed NULL, it will destory all the areas that have
been created with a_create(). If a program uses a_alloc() exclusively,
without calling any of the standard malloc() functions, it can assure
that all allocated blocks are freed by with the following call:
	(void) a_destory((A_AREA *) NULL);



int a_freeall(A_AREA *area);

  This function will free all the blocks belonging to an area, as
a_destroy() does. However, it will leave the area itself intact.
a_freeall() returns a count of how many blocks were freed.


A_AREA *a_find(a_info_t info);

  This will return a pointer to the area whose identifying information
matches that passed in the first parameter.


int a_snapshot(A_AREA *area, FILE *outf);

  For the area passed to it, this will produce a list of all allocated
blocks, and their sizes. If NULL is passed for the area parameter,
it will produce a list of all allocated blocks belonging to any area.
a_snapshot() returns a count of how many blocks were found.


...............................................................................

  When the going gets weird, the weird turn pro.

  Brian Michael Wendt       UUCP: {cepu,ihnp4,uiucdcs,noao}!bradley!brian
  Bradley University        ARPA: cepu!bradley!brian at seas.ucla.edu
  (309) 677-2230            ICBM: 40 40' N  89 34' W