13.2 MEMORY MANAGEMENT (ALLOCATION/ FREE)

In addition to static checking through strict typing, DOL provides run-time protection against pointer errors, and it gives you safer data structures than you get in Java. The integrity of of your data structure is guaranteed at all times, and the ZZ_CHECK() statement in your destructor detects any attempt to destroy an object which is still connected with other objects. The idea is simple:

When a new object is allocated, all automatically managed pointers (those which hide under ZZ_EXT_statements and are transparent to the user) are initialized to NULL. An object can join a new organization or be de-allocated only when all of its pointers are NULL.

The protection against pointer errors is complete for most DOL organizations such as RING, TREE, GRAPH, or DOUBLE_LINK even if they are singly linked because they use rings instead of NULL-ending lists. However, the protection is only partial for a few uni-directional organization where the target object carries no information on whether it has been disconnected. These special cases which you have to treat with more care are: SINGLE_LINK, GENERAL_LINK, and NAME.

DOL is not protected against the allocation of an array of objects and then attempting to free each object separately. For this reason, we strongly recommend always allocating one object at a time, and applying the ARRAY organization if you want to use arrays.

The util.clear() function which automatically destroyes your entire data organization also works only if all objects were allocated individually. Unless you use the ARRAY organization, a raw array of objects is saved as individual objects, one for each element of the array. After opening such data, pointer linked data structures using these objects are correct, but you cannot index the elements of the array.

Also note that automatically allocated objects are restored as heap-allocated. For more on these functions, see Chap.13.3.

Important:

When you allocate an object or an array of objects from the heap (using operator new), DOL initializes all data organizations as empty, with all the internal data structure pointers set to NULL. For example:

class Town {
    ZZ_EXT_Town
    ...
};

void foo(...){
    Town *myTown;      // pointer, not object
    myTown = new Town; // internal pointers automatically initialized

class Town {
    ZZ_EXT_Town
    ...
};

void foo(...){
    Town myTown; // object, internal pointers not initialized

When using DOL, you can use one of the following two strategies. (a) Not to worry about this issue and, consistently, allocate all objects from the heap. (b) Insert ZZ_INIT either into constructors of all your classes that have ZZ_EXT_... (prefered strategy), or at least into those classes that have automatically allocated objects:

class Town {
    ZZ_EXT_Town
    ...
public:
    Town(){ZZ_INIT(Town); ... your code ...}
    Town(int i){ZZ_INIT(Town); ... }
    ...
};

void foo(...){
    Town myTown; // object initialized as disconnected

Since DOL implements all data structures as pointer-linked rings, it allows powerful and yet inexpensive integrity checking. For example, any time you add() an object to any data structure, DOL checks that all its internal pointer(s) are NULL. It is impossible to mess up the data structure or create stray pointers, and it all happens transparently.

One of the typical ways to crash any program is to destroy an object without disconnecting it from a linked list or other data structure. All data structures in DOL provide del() function which disconnects a given object. But what if we forget to call del() before destroying the object?

If you insert ZZ_CHECK(objType) into the destructor(s) of a class which has the ZZ_EXT statement, any time you try to destroy an object of that class, regardless whether it was allocated automatically or from the heap, all its internal pointers are checked for being NULL. If any pointer is not NULL, it means the object was not properly disconnected, and a detailed warning message is issued which tells you which data structure caused the problem. Unfortunately, the C++ language does not allow to interrupt the destruction process once it started, so after printing the message your program will likely crash or mulfunction. This will not be a blind crash though. You will know exactly where the problem is, and will be able to correct it without any debugging.

class Town {
    ZZ_EXT_Town
    ...
public:
    Town(){ZZ_INIT(Town); ... your code ...}
    ~Town(){ ... your code ...; ZZ_CHECK(Town);}
    ...
};

void foo(...){
    Town myTown, *townPtr; 
    ...
    delete townPtr; // checks whether this is safe
}   // on return from foo(), myTown is checked before destruction

For examples of the use of ZZ_INIT(), see test4d.c, test27a.c, test29d, and test31.c. In test4d.c, the use of ZZ_INIT() is essential, at least for class Apple. In test29d.c, the macro is there for historical reasons, but could be removed without any effect on the operation of the program. For examples of ZZ_CHECK(), see test4d.c, test0n.c and test31.c. Note that ZZ_CHECK_FREE(Pin,1,this) is an older equivalent of ZZ_CHECK(Pin). For another example, see the end of Chap.6.

For objects that do not have any hidden pointers (their classes are not used in any of the ZZ_HYPER_.. statements), neither ZZ_INIT() nor ZZ_CHECK() should be used.

Using the internal free lists:

Some programs have to deal with a large number of objects that are frequently allocated and freed. The standard allocation available on most systems may lead to memory fragmentation, causing performance deterioration, and possibly program failure due to insufficient memory. In particular, this is very important for memory blasting (see Chap.13.3.), which does not automatically reuse the space from discarded objects. Operator delete there is overloaded to do nothing, and if we don't do anything else, each destructed object would leave an unused hole in the memory space. Since memory blasting saves the entire memory image to disk, this would also dramatically increase the size of the disk file.

In such situations, the best strategy is to keep a list of free objects, and reuse them instead of allocating them again.

DOL has a manager of the free space, which hides under ZZ_HYPER_UTILITIES(util). This manager works with three types of objects:

1. registered classes (those that have ZZ_EXT_..);
2. other objects and text strings that do not exceed in size the largest registered object (maxSz);
3. large objects and arrays.

The manager keeps a set of free lists, one for each object size up to maxSz, with the increment of 4 bytes. Free objects are linked by a pointer which overlays the first four bytes of the object. No additional memory is needed in order to maintain the free list. There is one linked list of large objects, with each object keeping pointer to the next object plus its own size.

There are three pairs of functions to allocate/free objects in this manner. Mixing these calls can lead to serious errors.

Note how different cases are handled internally. Functions new() and delete() know the class and its size, and can reuse the the space without a header or any other overhead. Functions newStr() and delStr() rely on the \0 character to determine the size of the string; they also do not use any overhead for the memory management. Functions newArr() and delArr() keep the size of the space internally (overhead of one int). Since these operations are typeless, delArr() must know the size of the object.

Examples of correct reuse:

class Town { ... }; Town* tp=new Town; delete tp; //registered class
char* s=util.newStr("John Brown"); util.delStr(s); //fixed string reuse
int i[]; int n=12000;
i=(int*)util.newArr(n*sizeof(int)); util.delArr(i); //general block
char* s=(char*)util.newArr(80); strcpy(s,"Joe Doe"); 
util.delArr(i); // text buffer

Examples of incorrect use:

// no possibility of problems with new() and delete()
char* s=util.newStr("John Brown"); delete(s); // will crash
char* s=new char[12]; strcpy(s,"John Brown");
util.delStr(s); // will crash in open
char* s=util.newStr("John Brown"); 
strcpy(s,"Joe Doe"); util.delStr(s); // memory leak 
char* s=util.newStr("John Brown"); util.delArr(s); //will crash

Control of free storage:

Function util.freeCount(int sz) returns the present number of free objects of this size. Using sz=0 returns number of large (variable sized) objects.

You can turn on the free store by calling util.useFreeStore(1), and turn it off by util.useFreeStore(0). For memory blasting,the default is free storage on.

Instead of globally invoking free lists for all registered classes, you can invoke free lists only for selected classes. ZZ_OBJECT_NEW(type,ptr) is a macro which picks up the next object from the free list (or allocates it if the free list is empty); ZZ_OBJECT_FREE(type,ptr) places the object on the internal free list.

You can control (and mix) the regular allocation with free lists:

    class myObj {
        ZZ_EXT_myObj
    publ:
        static myObj *newObj(){ myObj *p; ZZ_OBJECT_NEW(myObj,p); return(p); }
        void delObj(){ ZZ_OBJECT_FREE(myObj,this); }
    };

    
    myObj* obj1 = new myObj; // straight allocation, not using free list
    myObj* obj2 = myObj::newObj(); // using free list
    delete obj1; // destroys object regardless of where it came from
    obj2->delObj(); // move obj2 to the free list

util.clear(void) deallocates all internal free lists.

For an example of how to use the free list allocation, see test23b.c

Handling names:

In addition to free lists of text strings (see just explained), DOL also helps with the general management of names. It has the organization ZZ_HYPER_NAME (Chap.11.5 - similar to a String class), which treats names as instances of a string object, and it provides additional functions that facilitate creating/freeing names:

char *ptr=util.strAlloc(char *name) for a given name allocates the appropriate space, copies the name into it, and returns a pointer to it.

void util.strFree(char *ptr) frees the given string.

IMPORTANT: When saving data to disk, all names must first be allocated with util.strAlloc(), and then registered as NAME, if you use automatically allocated strings like "abcd" (for more details, see page 11.6.2).

For examples of how to handle variable length names, see test0n.c, test9a.c, test16c.c, and test25b.c.

Allocating arrays:

DOL also provides a package for the management of arrays (see Chap.11.12). Note that binary heaps and hash tables, which are both based on arrays, use the same method of allocation/deallocation as arrays do.

In DOL, an array exists as a data organization attached to an object.

ZZ_HYPER_ARRAY(id,HOLDER,TYPE); declares that every object of type HOLDER can have an array of objects type TYPE.

TYPE *arr=id.form(HOLDER *obj,int size,int increment); this function allocates an array of size objects, initializes the pointers of all its members, and properly sets the internal array header. It also sets the size increment, and returns the pointer to the array (arr) for fast unprotected indexing. It is recommended not(!) to use arr directly (as in arr[i], but through the index function, id.ind(obj,i). The array may reallocate itself, and render the [..] reference invalid.

void id.reset(HOLDER *obj,int size,int increment) resets the control parameters of the array (current waterMark and increment), without re-allocating the array or changing its actual content.

void id.free(HOLDER *obj) frees (destroys) the array.

For an example of allocating/deallocating arrays, see test16c.c.

Historical note: DOL has been used on large and complex projects long before the existing (non-persistent) data structure libraries came to existence. For this reason the DOL terminology related to arrays is slightly different from that used in the STL library and in Java. For example:
size in DOL corresponds to capacity in STL, and
waterMark in DOL is the highest index currently used which corresponds to (length-1) in STL.

Private allocation schemes:

If you have a private memory management system which you prefer to use, allocate objects through your system, and then initialize them with ZZ_INIT(). It is even better to convert the entire DOL to your memory management system:

File orgc/lib/msgs.c contains functions ZZmassAlloc() and ZZmassFree(), which control allocation/deallocation throughout DOL. Replace malloc() and calloc() there by your private functions, and recompile the library.

Big block of memory

One of the methods available for fast storage to disk (persistency) is based on the idea of reserving a block of memory for allocation of runtime objects, and restoring them from disk into the same relative position in another memory block, which has the same size. The advantage of this arrangement is that mutual offsets between objects remain constant, which allows fast updating of pointers after restoring the data from disk.

The disadvantage of this arrangement is the need to estimate the size of required memory, which is often difficult to predict. Also, even though the memory is reserved as one compact block, the data is saved to disk object-by-object, and even when buffered, it cannot match the efficiency of memory blasting .

This option is still in DOL mainly for historical reasons. Some large commercial applications use this option, and do not want it to disappear from the system. Two functions control big block allocation:

void util.blkAlloc(int n,0) allocates a new block of n bytes. If called several times, the most recent block acts as the currently active block.
void util.blkFree(int i) controls the use of the existing block. i=0 deallocates the active block; i=1 keeps it but, temporarily, returns to the normal allocation algorithm; i=2 turns allocation back to the big memory block.

There are no special SAVE/OPEN commands for this option - regular util.save(...) and util.open(...) are used. If the data was saved as one big block of memory, util.open(...) makes the following attempts:

1. If there is no active memory block, it opens a block of the same size as was originally used, including the free section of the pool.
2. If there is an active memory block that can contain the new data, the block is used, and the free pool is appropriately reduced.
3. If there is an active block of memory, but its free area is not large enough, the program creates a new block, which becomes a new active block.
4. If all allocation attempts fail (block size is too big), the program issues a warning message, and returns to normal allocation mode.

When the active pool is exhausted, a warning message is issued, and the operation automatically switches to normal allocation mode. Your program can safely continue the run. You can even save your data to disk. All you lose is the speed when re-opening the data from disk.

Allocation based on internal free lists works together with the memory block.

Note that all internal data, such as stacks and tables used by util.save() and util.open() are allocated from this the same memory block. (This is not true for other memory allocation modes.)

The current memory assigning algorithm is simple. For every new object, the high water mark of the given pool is raised. Unless you use the free-list option, discarded objects are not reused.

If util.blkAlloc() is called several times, the old data remains in memory. The most recently allocated block becomes the active block.

util.blkFree(1) allows you to separate the allocation of useful objects from temporary data, as in the following example, where all the application data has been allocated through the memory block, but then before calling util.save() allocation switches to normal mode, thus avoiding the allocation of temporary data, internal only to util.save() from the same block.

ZZ_HYPER_UTILITIES(util);
myObj *p,*s,m;
util.blkAlloc(3500,0); // reserves block of 3500 bytes
...
p=m.newObj(1); // create object
s=m.newObj(1); // create object
...
util.blkFree(1);// switch to normal allocation mode
util.save(...); // normal allocation, inter. tables
util.blkFree(0); // free the memory block

Free lists:

When allocating objects from a block of pages, you can use either new() or ZZ_OBJECT_NEW() which also provides, on top of memory paging, a list of free objects by type.

Use new() and constructors as usual, but never place ZZ_OBJECT_NEW() into a constructor. Look at test23b.c for the correct way to use ZZ_OBJECT_NEW().

Error conditions:

If a block of a given size cannot be allocated, util.error() returns 01, and a warning message is printed. The situation is the same as when exhausting the available pool. You can continue to run, but util.open() will allocate memory for individual objects, not from one big block.

Examples:

DOL used to be available both for C and C++, and the test suite does not have any examples of the big block allocation in C++. For examples in C, look at test0k.c, test24c.c and test33b.c. Note that ZZ_BLOCK_ALLOC() and ZZ_BLOCK_FREE() are identical to util.blkAlloc() and util.blkFree().

Previous Section 13.1 Virtual Functions and Internal Pointers

Next Section 13.3 Saving on Disk