3.5.3.3 Memory Management

Most of the data structures used in the Input Deck database are implemented using dynamic memory. Since for typical applications the database stores several thousands of database entries (variables and sections) and thousands of expressions are evaluated at runtime (see Section 3.5.2.1) memory allocation has to be fast. The standard functions malloc and free have been found to be much too slow.

Therefore, in the Input Deck database a similar memory management has been implemented as suggested by Stroustrup [119] who shows an implementation of an allocator using a pool class for the programming language C++. Since the Input Deck database has been written in C a modified approach had to be developed.

When a piece of memory is requested, e.g. $78$ Bytes, the size is rounded up to a multiple of $8$ like many operating systems do, in this case $80$ Bytes. Since the size of a requested piece of memory is a multiple of $8$ an index can be calculated by $index = size / 8 - 1$, which in this case equals $9$.

This index is used to determine a certain pointer from an array of pointers. Each pointer contains the address to a list of so called memory chunks or may be 0 to indicate that no list exists. A chunk is a memory block of a fixed size. Each chunk contains a list of elements. The elements hold the requested memory blocks. For instance, the pointer with index $9$ points to a list of chunks containing elements of size $80$ Bytes. An example of such an array is shown in Fig. 3.12.

Figure 3.12: Array of pointers to lists of chunks.

During initialization all pointers are set to zero and no memory blocks are stored. During runtime, when a piece of memory is requested the index is calculated and a chunk is allocated if no list of chunks exists for the given index. The list inside the chunk is initialized, where each element stores a pointer to the next element, the length of the requested piece of memory, and the requested memory space.

To allocate a piece of memory, the first element of the list is removed and the address of the memory space inside the list element is returned. Thus, memory allocation is quite fast, since only the head of a list has to be removed.

If no memory is left inside the chunk, another chunk is allocated and initialized. Therefore, the memory management can be interpreted as a list of pieces of memory inside a list of large memory chunks.

Since the free command does not provide an argument for the memory size the size of the memory to be freed has to be stored inside the list elements as mentioned before. Therefore, the address of the memory to be freed is decremented by a certain constant and the structure of the list element is obtained which stores the size of the memory space. The memory is freed by inserting the list element at the beginning of the corresponding list.

Figure 3.13: Allocating elements in chunks.

(a)  Initialized chunk.

(b) Allocate an element.

(c) Allocate another element.

(d) Free first element.

(e) Free second element.

Fig. 3.13(a) to Fig. 3.13(e) show the process of allocating and freeing memory in a chunk. For reasons of clearness the size of the memory block which is also stored in each element is not shown. When a piece of memory of a given size is requested for the first time a chunk is created and a list of elements inside the chunk is initialized (Fig. 3.13(a)). To allocate a piece of memory the first element (index 0) is removed from the list (Fig. 3.13(b)). To allocate another memory block of the same size again the first element of the list (now index $1$) is removed (Fig. 3.13(c)). To free a so allocated memory block it is simply inserted again at the beginning of the list. Therefore, to free the block which has been allocated first (index 0) the situation in Fig. 3.13(d) appears. To free the second element (index $1$) it is inserted at the beginning of the list, too, as shown in Fig. 3.13(e).

The memory management implemented in the Input Deck database is much faster than the functions for allocating and freeing memory provided by common operating systems. Another advantage of this approach is that the memory management can be used for debugging. Memory leaks can be identified if the list inside the chunks are not empty after all structures have been freed. Moreover errors caused by algorithms which write beyond the boundaries of allocated arrays can be found for some cases.