Dave Schmitt was a founder and president of Lattice, the well-known C compiler company, from 1983 until 1990. Prior to that, he worked at Bell Telephone Laboratories where he was involved in the design of fault-tolerant operating systems, including a nonstop version of UNIX. He is currently a free-lance author and consultant. You may contact him at Pivot, (708) 469-2235.
Early versions of UNIX offered C programmers a simple memory allocator using a linear heap and two functions named sbrk and brk. (Later systems renamed the latter rbrk.) This heap management system is fast and efficient because, unlike more sophisticated random heap systems, it requires no overhead to keep track of allocated and free blocks.
A random heap manager usually adds a pointer and an integer to each block. The integer contains the block size, and the pointer is used to chain the block into a linked list. I've seen some applications in which nearly 20 percent of the memory was lost to this overhead information. This typically occurs when you need to allocate a lot of very small blocks, such as when building a compiler symbol table.
Nonetheless, a linear heap is not as generally useful as a random heap, so the ANSI committee did not include sbrk and rbrk in the standard C library. They perpetuated only the UNIX random heap functions named malloc, free, calloc, and realloc. As a result, compiler vendors are gradually dropping sbrk and rbrk from their libraries.
Despite its omission from the ANSI standard, the linear heap has advantages in some applications. This article shows how you can implement sbrk and rbrk in an environment that offers only the ANSI random heap functions.
Linear Heap Management
A linear heap is a contiguous memory area divided into allocated and unallocated portions as shown in Figure 1. A break pointer contains the address of the unallocated portion. It initially points to the beginning (i.e., the low address) of the heap. You allocate memory by moving the pointer upwards (i.e., by increasing its address), and you free memory by moving the pointer downwards. The sbrk function handles both of these operations, as shown in Listing 1.The first two calls to sbrk allocate a 100-byte block and a 200-byte block, assigning the block addresses to pointers p and q, respectively. The third and fourth calls free both blocks by telling sbrk to move the break pointer first 200 bytes and then 100 bytes in the negative direction. You could combine these into a single call moving the break pointer down 300 bytes. Also, you can call rbrk to reset the break pointer to its initial position, thereby freeing all allocated blocks.
Linear Heap Applications
The example in Listing 1 shows the primary disadvantage of the linear heap: You must always free blocks in the reverse order that they were allocated. If you no longer need the 100-byte block, you cannot release it until you are done with all the blocks allocated after it. Indeed, the linear heap manager knows nothing about blocks; it merely moves a pointer up and down.Despite this disadvantage, the linear heap is well-suited to some applications. Suppose you're building a symbol table for a compiler. Each symbol is represented by a structure having the format shown in Listing 2.
When the compiler encounters a new symbol, it builds a SYMBOL structure on the stack and then calls a function named savesym to save this information in the heap. When the function returns, the compiler links the new SYMBOL structure into the appropriate place in an alphabetical list. These structures remain allocated throughout the compilation and are all released at the same time when the compiler is finished. This is clearly a case where the overhead of a random heap is unnecessary.
To show the difference between the two heap methods, the savesym function can be written to use either sbrk or malloc, as shown in Listing 3.
This function uses sbrk if the symbol LHEAP is defined; otherwise, it uses malloc. Note that savesym returns NULL if no space can be allocated. The strange if statement after the sbrk call is necessary because sbrk does not return NULL when it fails. Instead, it conforms to the original UNIX definition by returning the value -1 cast to a pointer.
The little test program in Listing 4 shows how many symbols we can save under various conditions. Figure 2 shows the results of running this test program with the linear and random heap, using the Lattice compiler and various symbol sizes. The left column indicates the size of the symbol. A size of 8 produces a 19-byte SYMBOL structure, while a size of 255 produces a 266-byte structure. The percentage column is computed by taking the difference between the sbrk and malloc results, divided by the malloc results.
This test indicates that, given a typical implementation, sbrk is about 25 percent more space efficient than malloc when allocating small blocks. As the block size increases, this advantage gradually disappears.
Since many programming languages use small symbols of 32 bytes or less, the linear heap method can make a noticable difference in compiler memory consumption. In general, you should consider using sbrk if your application allocates a lot of small blocks that it keeps until termination or until the beginning of another processing phase. In such an application, you can also get a performance improvement with a linear heap because it allows you to release all memory with a single call to rbrk rather than with multiple calls to free.
Implementing A Linear Heap
If your favorite C compiler doesn't support sbrk and rbrk, you can easily implement them on top of malloc and free. The code is shown in Listing 5.The operation of sbrk is straightforward. On the first call, it uses malloc to get a block whose size is the larger of the requested size and the global parameter _LHINCR. Local variables base and size are used to save the base address and size of this block, respectively. The variable xbrk is the offset of the break location within the block. It is initially set to zero. In other words, the current break address is &base[xbrk]. In keeping with the UNIX definition of sbrk, a new block is cleared — memset is called if n is greater than 0.
The rbrk function is even simpler. If a linear heap has been created, it frees the block and resets all the local variables. Otherwise, it does nothing.
Notice that _LHINCR normally causes the linear heap to contain 8 kilobytes. You can change this to a different value before the first call to sbrk or after calling rbrk. You might wonder why this approach is used rather than having sbrk call realloc to expand the linear heap when it cannot honor a request. The problem is that realloc may move the heap, thereby invalidating the pointers returned by all previous sbrk calls.
Final Thoughts
The latest compiler from Microsoft does not provide sbrk and rbrk, so you can use the functions from Listing 5 with no problems.Borland provides a verison of sbrk that performs about the same as Lattice's. However, Borland's C compilers do not have an rbrk function. This is not a big problem if you maintain a total of all the space you have allocated via sbrk. You can then simulate rbrk by calling sbrk with the negative of this total value.
Watcom and Zortech also provide sbrk but not rbrk. However, you may not want to use their linear heaps because of the implementation's overhead. When I ran the Listing 4 test program with these two compilers, I discovered that the sbrk version of savesym stored fewer symbols than the malloc version.
This discovery led me to examine the source code that Zortech supplies in their Developer's Edition. It turns out that each time you call their sbrk function, they invoke DOS to get more memory. Since DOS allocates in multiples of 16-byte paragraphs, each sbrk request is rounded up to the next multiple of 16. This is considerably more overhead than Zortech's malloc, which rounds each request up to the next multiple of four.
Zortech's implementation of sbrk also violates the spirit of the original UNIX version, where the requested size was not rounded up and each allocated block was immediately above its predecessor. To be fair, however, Zortech says this about sbrk in their manual: "Applications should avoid using it." If that's the case, I wonder why they bothered to include it in their library and documentation.
The Watcom version of sbrk behaves so much like Zortech's that I suspect it uses a similar strategy, although I did not have access to their library source. It's clear that if you can benefit from the linear heap approach, you should use the routines from Listing 5 even in the Watcom and Zortech environments, which supposedly support this feature. To be sure of linking in the correct version, you might want to put a leading underscore in front of your sbrk and rbrk routines, or give them completely different names.