/* * File: gcalloc.h * Last modified on Sat Aug 28 10:17:26 1993 by eroberts * ----------------------------------------------------- * This file defines the interface for a garbage-collecting * allocator.  This interface defines only an initialization * function (InitGCAllocator) and facilities for protecting * global variables.  The actual allocation is handled by * the standard GetBlock and FreeBlock functions defined in * genlib.h.  These functions use the garbage-collecting * allocator if InitGCAllocator has been called. */#ifndef _gcalloc_h#define _gcalloc_h#include <stdlib.h>#include "genlib.h"/* * Background * ---------- * In a typical application program, memory is allocated in * three different regions.  Static data is stored in fixed * memory addresses and is declared in C using the storage * classes static or extern (extern is in fact omitted in * the defining instance).  Automatic data (the default * storage class for variables defined within a function) * is stored on the control stack, where it is allocated * when a function is called and deallocated on return * from that function.  In addition to these two classes, * however, many programs will need to allocated additional * memory from an expandable pool called the "heap."  All * memory in the heap is addressed via pointers, which are * generated as the program runs. * * Although heap allocation is extremely convenient, * particularly when used in library implementations, it * suffers from an important failing.  The problem is not * identifying what parts of the program have responsibility * for allocating memory.  That task is easy.  The thorny * issue is who has responsibility for freeing previously * allocated memory when it is no longer needed. * * The central problem is that the operations of allocating * and freeing memory are most naturally situated on opposite * sides of the interface boundary between an implementation * and its client.  The implementation knows when to allocate * memory and simply returns pointers to the client.  The * implementation, however, has no idea when the client is * finished with the allocated object, so that freeing the * storage has to remain the client's responsibility, even * though the client may not understand enough about the * object's structure to do so. * * To get around this problem, most libraries have been * designed in one of two ways.  One approach is to make * the client responsible for allocating storage and * passing a pointer to the implementation.  The alternative * is to provide procedures in each interface that free any * storage allocated by the abstraction.  Each of these * approaches is decidedly non-optimal. * * A completely different alternative is to use a strategy * called "garbage collection."  Under this strategy, * implementations are free to allocate memory and pass * their addresses back to the client.  As long as the * client holds that pointer, the memory is considered * to be in use.  When the pointer goes away (which occurs * when a different pointer is assigned to the variable or * when the variable holding the pointer is deallocated * by returning from the function declaring it), the * storage to which it referred is no longer accessible, * and can be reallocated to new purposes. * * Detecting what memory is garbage does not happen as the * memory becomes inaccessible.  Instead, the traditional * garbage-collection strategy is to wait until a memory * cannot be satisfied, and then to go through accessible * memory to see what previously allocated blocks are no * longer reachable, freeing these for reuse. *//* * Client responsibilities * ----------------------- * The garbage-collecting allocator imposes some important * responsibilities on the client who uses the package.  In * particular, the client must agree to obey the following * rules: * *   (1)  Whenever a heap object is allocated, the client *        must agree to keep at least one copy of the *        original pointer returned by GetBlock.  In C, *        it is common to use pointer arithmetic to adjust *        a pointer so that, for example, it points to the *        interior of an array.  The rule is that a block *        is protected from garbage collection only by *        a pointer to its beginning and not to its *        interior.  Note that this rule does not prohibit *        pointing to the interior of the block; the *        implication is simply that the client must *        also keep the original pointer around. * *   (2)  The garbage collector must be able to identify *        all places in which valid heap pointers might *        be maintained, so that it can ensure that *        valid data is not collected by accident.  This *        package (subject to the system assumptions *        below) is able to find pointers living in *        automatic variables on the stack, or in heap *        blocks allocated by GetBlock which themselves *        remain accessible (see condition 3 as well).  If *        static variables contain allocated data, however, *        the client must warn the allocator of this *        fact by calling * *                ProtectVariable(variable); * *        where variable is the name of the global *        variable. * *   (3)  It is the client's responsibility to free *        explicitly any storage allocated outside of the *        GetBlock/FreeBlock mechanism.  Moreover, it is *        also important to remember that the garbage *        collector is not able to find pointers which are *        stored in dynamically allocated blocks unless *        those blocks were allocated by GetBlock.  Thus, *        if an implementation makes direct calls to the *        system allocation functions in addition to *        GetBlock, that implementation may not store the *        GetBlock pointers in the system-allocated memory. *//* * Function: InitGCAllocator * Usage: InitGCAllocator(&argc); * ------------------------------ * This call enables the garbage-collecting allocator and * also establishes the base of the stack for tracing.  This * call should be made from main, and the address passed * should be the address of the argc parameter. */void InitGCAllocator(void *stackbase);/* * Macro: ProtectVariable * Usage: ProtectVariable(v); * -------------------------- * Registers a global variable with the allocation system, so * that the variable is traced when the garbage collector is * used.  This operation needs to be provided in "genlib.h" * so that code can be written to function correctly whether * or not the garbage-collecting allocator is loaded. */#define ProtectVariable(v) ProtectBlock(&v, sizeof v)/* * Function: ProtectBlock * Usage: ProtectBlock(ptr, nbytes); * --------------------------------- * This function is not usually called by clients (who will * ordinarily use ProtectVariable instead), but has the * effect of protecting the block of memory beginning at * ptr and extending for nbytes from the garbage collector. */void ProtectBlock(void *ptr, size_t nbytes);/* * Global linkage variable: _acb * ----------------------------- * This variable is used to hold the allocation control block * that provides the linkage between this package and the * dynamic allocator.  The reason for using the structure * as a linkage is so that the garbage-collecting allocator * need not even be loaded if it is not explicitly called. */typedef struct {    void *(*allocMethod)(size_t nbytes);    void (*freeMethod)(void *ptr);    void (*protectMethod)(void *ptr, size_t nbytes);} *_GCControlBlock;extern _GCControlBlock _acb;#endif