Memory allocation
*****************

The ability to allocate memory of on at compile-time unknown amount is an important feature for most programs.

On modern operating systems, processes do not have direct access to the memory. Only the operating system kernel does. Instead, the process have virtual memory-addresses, that the kernel maps to either, real RAM, swap space (disc backed), file segments, or zeroes.

Memory for a process is either allocated programmatically, or when the process forks (is created) or exec:s (changes process image.) The operating system kernel is typically configured to share a much memory between processes as possible. For example, and a process forks, they will share their memory rather than duplicate the memory, and the kernel will only remap the memory when the processs' memory content diverges. It is also possible to allocate memory in such a way that processes can share it. so that updates from one process influences the other processes.

A process' virtual address space is divided into segments. There are three important segments.

text segment
     When a process exec:s this segment is allocated. It contains instructions, static constants, and literals.

BSS segment
     When a process exec:s this segment is allocated. It contains all global and static variables that are initialised to zero or lacks explicit initialisation. On some systems this segment is merged into the data segment. BSS is an acronym: `Block Started by Symbol'.

data segment
     When a process exec:s this segment is allocated. It is filled all global and static variables that are not covered by the BSS segment. This segment's lower end is fixed, and its upper end is unfixed; it can be resized. Any part of the segment that is a result of it being resized, is referred to as the heap.

stack segment
     This segment contains a (Program stack's can created programmtically, hence `a' rather than `the'.) program stack. A program stack contains information required to return after a function call, and automatic variables. Depending on the platform and the function it may also contain arguments passed in function calls and return values. It grows as the stack grows, but it does not shrink as the stack shrinks.

The layout of the segments is machine dependent and operating system. However, a common (Keeping in mind this cannot be assumed practice, and that it is in fact different between systems.) layout is have the text segment (as other fixed segments) start at 0, and end at some positive address. The text segment is then followed by the BSS segment, and the data segment. The stack segment however, grows from the highest address (-1 on two's complement-machines) downwards. The process cannot allocate any more memory when the allocation would require the data segment to be grown to such an extent that it would overlap with the stack segment.

In C there are multiple ways to allocate memory.

  * Variables that are declared outside functions are called global variables (Even if that are declared with static. In this context, static is only use to hide object from other translation units.). These are stored either in the BSS segment or in the data segment, depending on their initialisation. Pointer are stored as numerical values, and the content is stored in the text segment. Arrays however are not stored, but their content is. In the data segment (or in the BSS segment if the elements are zeroes.) These allocations are known as static allocations.

  * Variables that are declared inside functions, with static, are stored just like global variables. These are called static variables, and remain unchanged between function calls, and only change in statements other than the declaration statement. These allocations are known as static allocations.

  * Variables that are declared inside functions (these are known as local variables), without static, but with auto, are called automatic variables. These are stored in the stack segment, and are deallocated when the function returns. Local variables that are declared with neither static, auto, or register are often though of as automatic; however, the compiler may choose to add register. These allocations are known as automatic allocations (Known in some other programming languages as stack-allocations.).

  * Variables that are declared with register are not stored in any segment. They lack addresses and stored as CPU registers.

  * Using system calls, a heap can be created, where new allocations are stored. These are often allocated with the function malloc, and are known as dynamic allocations (Known in some other programming languages as heap-allocations.).

Some compilers, including GCC, provide two additional ways to allocate memory.

Variable-length arrays
     A simple example of variable-length arrays, available with some compilers, is

          void function(size_t n)
          {
            int array[n];
            /* ... */
          }

     Variable-length arrays have a special property: they may be deallocated before the function returns. In fact, they are returned once the variable becomes invisible, this causes the follow example to work without every exhausting the memory.

          void function(size_t n)
          {
            for (;;)
              {
                int array[n];
                /* ... */
              }
          }

alloca
     alloca is a special function that is implement by the compiler. It increases the stack and returns a pointer to the beginning of the new part of the stack. It is similar to variable-length arrays, however the allocation is not deallocated before the function returns. This causes the follow example to eventually exhaust the memory.

          void function(size_t n)
          {
            for (;;)
              {
                int pointer* = alloca(n);
                /* ... */
              }
          }

Both of these allocation-methods are both automatic and dynamic.

Memory allocation functions return NULL if the process cannot allocate more memory. However, under typical configurations of the operating system kernel, memory allocation functions can return succesfully, even if the system's memory is exhausted. The process's virtual address space is not exhausted, so it thinks it can allocate the memory, but the machines memory is exhausted, so once the process tries to write to the memory, the kernel cannot map the virtual address to a real address. When this happens the process is killed by a SIGSEGV (Segmentation violation, also known as segmentation fault.) signal.

The alloca function
===================

The function void* alloca(size_t n) appears on multiple systems: 32V, PWB, PWB.2, 3BSD, 4BSD, and GNU. It has been added to slibc, without require on feature-test macros, despite not being standardised (for instance, it does not appear in POSIX). This function is however not portable, and will not be made available if _PORTABLE_SOURCE or _LIBRARY_HEADER is defined. alloca is defined in the header file <alloca.h>.

void* alloca(size_t n) is similar to the function malloc. It allocates a contiguous space of usable memory of n bytes, and returns a pointer, which points to the beginning of the allocated memory. However, the allocate appears on the stack rather than the heap, and it automatically deallocated when the function whence the call to alloca was made. Be cause if this, alloca is implemented as a macro --- using an intrinsic function provided by the compiler --- rather than as a function.

You must not try to free the memory explicitly, with a function like free, or resize it with a function like realloc. Just like arrays and pointers to automatic variables, memory management functions cannot operate memory allocated with alloca.

Unlike malloc, alloca does not detect memory exhaustion, thus it will never return NULL. However, it is likely that the process will receive SIGSEGV (Segmentation violation, also known as segmentation fault.) if it tries to access memory that could not be allocated, or, depending on the kernel's configuration, before it returns.

On typical kernels and kernel configurations, alloca and malloc will handle memory exhaustion identically.

Undefined behaviour may be invoked if alloca is called within a function call. The behaviour depends on the machine, the compiler, and optimisations. You should avoid code similar to

     #define strdupa(string)  \
       strcpy(alloca((strlen(string) + 1) * sizeof(char)), string)

alloca has its restrictions --- limited lifetime, cannot be explicitly deallocated, not growable, and not shrinkable ---  but it can also be advantageous because:

  * Results in cleaner code because it is deallocated automatically.

  * It does not waste any space on metainformation required for bookkeeping.

  * Uses a faster memory allocation mechanism.

Basic memory allocation
=======================

malloc is the most general, and most commonly used memory allocation facility. It is also the most portable, and is available on all environments. There are three important function that were introduced in ANSI C. These are defined in <malloc.h>, however, they should be included via <stdlib.h> whihc includes <malloc.h>.

void* malloc(size_t size)
     Allocates a contiguous memory block of size bytes of usuable memory, and returns a pointer to the beginning of the usable part of the allocation. The function allocates some extra memory for internal bookkeeping, this part of the allocation is located before the address the returned pointer points. Allocated memory is uninitialised.

     If the memory cannot be allocated (due to memory exhaustion,) NULL is returned and errno is set to ENOMEM.

     It is implementation defined whether this function returns NULL or a unique pointer if size is zero. In slibc, NULL is returned.

     The allocation be grown or shrinked at any time. See Resizing memory allocations.

     In ISO C, void* can be implicitly casted to any other pointer type. Therefore it is sufficient (and preferable) to write

          int* ten_integers = malloc(10 * sizeof(int));

     You do not need to write

          int* ten_integers = (int*)malloc(10 * sizeof(int));

void* calloc(size_t count, size_t size)
     This function is similar to malloc, but it initialises the memory to zeroes. The only other difference is that it as two parameters rather than one.

     If count * size would overflow, NULL is returned and errno is set to ENOMEM. Otherwise, p = calloc(a, b) is identical to

          p = malloc(a * b);
          memset(p, 0, a * b);

void free(void* ptr)
     Memory that is dynamically allocated (without automatic deallocation) can be deallocated with this function. It is required that ptr is the pointer returned by the function that allocated it. It must not have been incremented. Undefined behaviour is invoked otherwise. One exception is NULL, if ptr is NULL nothing happens.

     Do not try to free a pointer twice, undefined behaviour. Neither should you try to pass pointers to variables to this function, nor pointers to functions, arrays, main's parameters, memory-mapped I/O, or memory allocate with alloca. Function-like macros that allocate memory with alloca (There functions that will return pointers allocate with alloca, because the memory would be deallocated at the return. Thus, such facilities are implemented as function-like macros.) specifies so, and their name typically end with an `a', which is not too common for other functions.

     Be also cautious of whether functions return statically allocated arrays, which must not be deallocated, or dynamically allocated memory, which should be deallocated to avoid memory leaks.

<malloc.h> also includes three unportable functions.

void* zalloc(size_t size)
     This function is similar to calloc, but it only has one parameter. Assuming a and b are two size_t:s, and a * b does not overflow, calloc(a, b) is identical to zalloc(a * b). zalloc is a klibc extension.

void cfree(void* ptr, ...)
     This function is an obsolete function provided by a number of C standard library implementations. It has been replaced by free. cfree is identical to free.

     Different implementions libc, defined cfree with different numbers of parameters, therefore slibc declares cfree as a variadic function, and ignores all but the first argument.

size_t malloc_usable_size(void* ptr)
     This function returns the number of usable bytes for a pointer. If ptr is NULL, zero is returned. It has the same restrictions as the function free.

     malloc_usable_size(malloc(n)) returns n (and allocates memory in the process.)

     This function is a GNU extension and requires _GNU_SOURCE.

Aligned memory allocation
=========================

TODO

Resizing memory allocations
===========================

TODO

Efficient stack-based allocations
=================================

TODO obstack.h

Resizing the data segment
=========================

TODO brk, sbrk

Memory locking
==============

TODO mlock, munlock, mlockall, munlockall