Malloc problems

[brian at bucc2.UUCP]

> /* Written  7:32 am  May 16, 1988 by kazoo.cis.ohio-state.edu!spencer */
> It is true that when malloc() runs out of memory, the call to malloc()
> will return NULL. 

	[ example of if (!(p = malloc(n))) die(); deleted ]

> Good (in my estimation) code would test any and all dynamically allocated
> memory for successful completion of the malloc() call.  
> 
> I suppose that 'garbage collection' would be too machine-dependent.
> It'd sure be a nice feature.

  See _A Memory Allocator with Garbage Collection for C_, Michael
Caplinger (Bell Communications Research.) in the Winter 1988 USENIX
conference proceedings...

  This paper gave me the inspiration for an extension to malloc() we
are considering implementing. A short description follows:

  For the reasons outlined in Caplinger's paper, it is often difficult
to free() everything that has gotten *alloc()'d in a large project.
We do not want to implement garbage collection, however, due to
the code overhead and lack of sources. The environment we are running
is Microsoft C 5.0 on IBM AT's and PS/2's under MS-DOSN'T.

  We are considering a solution which is easier to implement, but
is not as clean.

  An additional field will be added to the header at the beginning of
every block on the heap. After a call to malloc is made, a mark() function
can be called to set a code in this field. Later, a function called
free_group() frees all the blocks with a specific code. The functions
would look like this:

/* mark a pointer to a block allocated from the heap. returns ptr on	*/
/* success, or NULL if ptr didn't point into the heap.			*/
char *mark(ptr, code)
  char *ptr;			/* block to mark			*/
  long code;			/* code number to mark with		*/

/* free all blocks on the heap with a specified mark code. Returns a	*/
/* count of the number of blocks free'd.				*/
int free_group(code)
  long code;			/* code number of blocks to free	*/


  An example is a function to read ten lines from a file, allocating
a new buffer for each line. If less than ten lines were found, we wish
to deallocate any lines that were read.

#define MY_MEM_GROUP	17L

char *lines[10];
char buf[512];

int readtenlines(fp)
  FILE *fp;
  {
  register int i;
  char *p;

  for (i = 0; i < 10; i++)
    {
    if (!fgets(buf, 512, fp))
      {
      free_group(MY_MEM_GROUP);
      return(0);
      }

    if (!(p = malloc(strlen(buf)+1)))
      {
      fatal_error("read_ten_lines", "malloc()", "ran out of memory");
      /*NOTREACHED*/
      }

    mark(p, MY_MEM_GROUP);
    strcpy(p, buf);
    lines[i] = p;
    }
  }

  MY_MEM_GROUP is just the arbitrary code number assigned for this
function. After the calling function is done with lines[], it can
call free_group(MY_MEM_GROUP) to get rid of the buffers.

  Another function, for debugging, will report how many objects with
a certain code are on the heap. This can be called at the end of a
module to find out if anything has been left "lying around" on the
heap.


  The code numbers will be 31 bits. The "missing" bit in that number is
used to indicate whether the block is allocated or free. Since we have
many programmers working on each project, the code will probably be
broken down as follows:

struct myheapinfo
  {
  size_t	 size;

  unsigned      inuse :  1;
  unsigned programmer :  6;
  unsigned    project :  8;
  unsigned     gensym :  1;
  unsigned       code : 16;
  }
 
   Each programmer will have a unique code similar to a UID, which will be
stored in the programmer field. This will help in finding a scapegoat when
problems arise... errrr rather in locating the code that isn't freeing
its allocated memory. Since we only have about 15 programmers doing this
type of work, 64 programmer codes per project should be sufficient.

  The project field will be a code indicating which project or library
allocated the block.

  Sixteen bits are reserved for the code itself, allowing for 2^16 
"memory" groups per programmer per project. Additionaly, to help with
coding reentrant functions, a gensym() function will return a unique
code number. To make gensym() codes seperate from codes defined by
the programmer, the gensym flag is provided in the structure.

  Blocks that haven't been mark()'d will have zeroes in all these
fields. Code zero will be reserved for this reason. Thus, it will
support 255 projects/libraries, with 63 programmers per project.
Each programmer will have 65535 codes he can define per project,
and can call gensym() for an additional 65535 codes.


  Any thoughts, comments, suggestions, flames, etc, would be
appreciated.

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

  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