5.3.15. Allocate more Heap, sbrk

5.3.15. Allocate more Heap, `sbrk`

For a namespace clean function, implement _sbrk, otherwise implement sbrk. This is one function for which there is no default minimal implementation. It is important that it is implemented wherever possible, since malloc depends on it, and in turn many other functions depend on malloc. In this application note, the OpenRISC 1000 implementation is used as an example.

As noted earlier (Section 5.2.2), the heap on the OpenRISC 1000 grows up from the end of loaded program space, and the stack grows down from the top of memory. The linker defines the symbol _end, which will be the start of the heap, whilst the C runtime initialization places the address of the last work in memory in the global variable _stack.

	Caution
	`_end` is a symbol defined by the linker, not a variable, so it is its address that must be used, not its value.

Within a C program these two variables are referred to without their leading underscore—the C compiler prepends all variable names with underscore.

#include <errno.h>

#undef errno
extern int  errno;

#define STACK_BUFFER  65536     /* Reserved stack space in bytes. */

void *
_sbrk (int nbytes)
{
  /* Symbol defined by linker map */
  extern int  end;              /* start of free memory (as symbol) */

  /* Value set by crt0.S */
  extern void *stack;           /* end of free memory */

  /* The statically held previous end of the heap, with its initialization. */
  static void *heap_ptr = (void *)&end;         /* Previous end */

  if ((stack - (heap_ptr + nbytes)) > STACK_BUFFER )
    {
      void *base  = heap_ptr;
      heap_ptr   += nbytes;
                
      return  base;
    }
  else
    {
      errno = ENOMEM;
      return  (void *) -1;
    }
}       /* _sbrk () */

The program always tries to keep a minimum of 65,536 (2¹⁶) bytes spare for the stack.

	Note
	This implementation defines `_sbrk` as returning type void . The standard newlib documentation uses return type caddr_t, which is defined in `unistd.h`. The author believes that void is now the recommended return type for this function.

Important

	Important
`sbrk` has to return the previous end of the heap, whose value is held in the static variable, `heap_ptr`. The problem is that this now makes the function non-reentrant. If the function were interrupted after the assignment to `base`, but before the following assignment to `heap_ptr`, and the interrupt routine itself also called `sbrk`, then the heap would become corrupted. For simple systems, it would be sufficient to avoid using this function in interrupt service routines. However the problem then knowing which functions might call `malloc` and hence `sbrk`, so effectively all library functions must be avoided. The problem cannot even be completely avoided by using reentrant functions (see Section 5.4), since just providing a per thread data structure does not help. The end of heap is a single global value. The only full solution is to surround the update of the global variable by a semaphore, and failing the allocation if the region is blocked (we cannot wait, or deadlock would result).

sbrk has to return the previous end of the heap, whose value is held in the static variable, heap_ptr.

The problem is that this now makes the function non-reentrant. If the function were interrupted after the assignment to base, but before the following assignment to heap_ptr, and the interrupt routine itself also called sbrk, then the heap would become corrupted.

For simple systems, it would be sufficient to avoid using this function in interrupt service routines. However the problem then knowing which functions might call malloc and hence sbrk, so effectively all library functions must be avoided.

The problem cannot even be completely avoided by using reentrant functions (see Section 5.4), since just providing a per thread data structure does not help. The end of heap is a single global value. The only full solution is to surround the update of the global variable by a semaphore, and failing the allocation if the region is blocked (we cannot wait, or deadlock would result).