Returning Memory

Some languages allow requested storage to be freed or returned to the heap. This is an efficient method of storage management, but it allows two kinds of errors:

• Forgetting to return memory: a storage leak.

• Returning the same memory more than once. This can produce errors that are very difficult to find.

Released storage can be held in linked lists that are pointed to by an array of pointers, where the array is indexed by block size.

Potential problem: mismatch of block sizes. The user requests and releases many blocks of size 7, then needs blocks of size 5.

Larger blocks can be subdivided, but this leads to fragmentation (many small blocks that cannot be used). The buddy system (see Knuth) is one way of combining smaller blocks into larger ones when possible.

malloc puts the size of a block behind the block (just before the pointer value that is returned). This makes it easy to check whether adjacent blocks have been returned, so that they can be combined. However, a misbehaving program can overwrite the size and crash the system.