Memory allocation

serdarkose edited this page Aug 19, 2015 · 7 revisions

Contiki provides three ways to allocate and deallocate memory: the memb memory block allocator, the mmem managed memory allocator, and the standard C library malloc heap memory allocator. The memb memory block allocator is the most frequently used. The mmem managed memory allocator is used very infrequently and use of the malloc heap memory allocator is discouraged.

Table of Contents

The memb Memory Block Allocator

The memb library provides a set of memory block management functions. Memory blocks are allocated as an array of objects of constant size and are placed in static memory.

The memb API

MEMB(name, structure, num); // Declare a memory block. 
void memb_init(struct memb *m); // Initialize a memory block. 
void *memb_alloc(struct memb *m); // Allocate a memory block. 
int memb_free(struct memb *m, void *ptr); // Free a memory block. 
int memb_inmemb(struct memb *m, void *ptr); // Check if an address is in a memory block. 

The MEMB() macro declares a memory block, which has the type struct memb. The definition of this data type is shown below. Since the block is put into static memory, it is typically placed at the top of a C source file that uses memory blocks. name identifies the memory block, and is later used as an argument to the other memory block functions. The structure parameter specifies the C type of the memory block, num represent the amount objects that the block accommodates.

The expansion of the MEMB() macro yields three statements that define static memory. One statement stores the amount of object that the memory block can hold. Since the amount is stored in a variable of type char, the memory block can hold at most 127 objects. The second statement allocates an array of num structures of the type referenced to by the structure parameter.

Once the memory block has been declared by using MEMB(), it has to be initialized by calling memb_init(). This function takes a parameter of struct memb, identifying the memory block.

After initializing a struct memb, we are ready to start allocating objects from it by using memb_alloc(). All objects allocated through the same struct memb have the same size, which is determined by the size of the structure argument to MEMB(). memb_alloc() returns a pointer to the allocated object if the operation was successful, or NULL if the memory block has no free object.

memb_free() deallocates an object that has previously been allocated by using memb_alloc(). Two arguments are needed to free the object: m points to the memory block, whereas ptr points to the object within the memory block.

Any pointer can be checked to determine whether it is within the data area of a memory block. memb_inmemb() returns 1 if ptr is inside the memory block m, and 0 if it points to unknown memory.

The memb memory block structure.

 struct memb {
   unsigned short size;
   unsigned short num;
   char *count;
   void *mem;
 };

The open_connection() function allocates a new struct connection variable for each new connection identified by socket. When a connection is closed, we free the memory block for the struct connection variable.

 #include "contiki.h"
 #include "lib/memb.h"
 
 struct connection {
   int socket;
 };
 MEMB(connections, struct connection, 16);
 
 struct connection *
 open_connection(int socket)
 {
   struct connection *conn;
 
   conn = memb_alloc(&connections);
   if(conn == NULL) {
     return NULL;
   }
   conn->socket = socket;
   return conn;
 }
 
 void
 close_connection(struct connection *conn)
 {
   memb_free(&connections, conn);
 }

The mmem Managed Memory Allocator

The managed memory allocator (mmem) provides a dynamic memory allocation service similar to malloc. Its main distinction, however, is that it uses a level of indirection to enable automatic deframentation of the managed memory area.

It must be noted that the memory allocated with mmem_alloc() is 1-byte aligned. This is different from what malloc() does. The memory allocated with malloc() is suitably aligned for every data type and the returned void pointer can be safely casted to any other pointer type.

Instead, the pointer to the memory allocated by mmem_alloc() cannot be safely converted to any pointer type other than char*, signed char* or unsigned char*.

This means that if the allocated memory chunk is used to store the contents of a struct type, either the struct must be declared packed or memcpy() must be used. With GCC a packed struct can be specified using the following syntax:

 struct __attribute__ ((__packed__)) my_packed_struct {
   ...
 }

Many other compilers allow to specify a packed struct, often through an implementation-specific #pragma directive.

Every managed memory block is represented by an object of type struct mmem, as shown below. The mmem library organizes the struct mmem objects in a list named mmemlist. In the struct mmem object, ptr refers to the size of the allocated chunk in the contiguous memory pool reserved for the mmem library. size denotes the amount of bytes that the memory block can store.

The managed memory structure:

 struct mmem {
   struct mmem *next;
   unsigned int size;
   void *ptr;
 };

Programming Interface

The mmem programming interface is declared in core/lib/mmem.h. The available functions and macros are shown below.

mmem_init() initializes the managed memory library. MMEM_SIZE determines the size of the managed memory pool. The default size is 4~kB, but can be modified by defining MMEM_CONF_SIZE to another value in the configuration file used by the platform. Note that several platforms do not initialize the mmem library, which makes it necessary to include ensure that mmem_init() is called when using those platforms. The call to mmem_init() can be placed either in the module using mmem or in the platform startup code, which is typically found in platforms/name/contiki-name-main.c().

mmem_alloc() allocates a block of memory. The first argument, m, is the reference to the struct mmem that will be initializes in mmem_alloc() and later used to refer to the memory block. The size argument specifies how large the block should be. The function returns a non-zero value if the memory block was allocated, and zero if there was not enough memory available. Allocated memory must be deallocated by using mmem_free() when it is no longer needed. MMEM_PTR() is a macro that returns a pointer to the memory block pointed to by m.

mmem_free() deallocates a managed memory block pointed to by the m argument. The mmem library will try to defragmentate the managed memory poll inside this function. All memory following the deallocated block is moved downwards to start at the newly freed position. The struct mmem object of each moved block gets it MMEM_PTR() pointer updated to reflect the new position of the memory block.

The mmem API

MMEM_PTR(m); // Provide a pointer to managed memory. 
int mmem_alloc(struct mmem *m, unsigned int size); // Allocated managed memory. 
void mmem_free(struct mmem *); // Free managed memory. 
void mmem_init(void); // Initialize the managed memory library. 

test_mmem() allocates a managed memory object, copies a data structure into it, and retrieves the value of an element in the structure. The managed memory is deallocated when we have finished using it.

 #include "contiki.h"
 #include "lib/mmem.h"
 
 static struct mmem mmem;
 
 static void
 test_mmem(void)
 {
   struct my_struct {
     int a;
   } my_data, *my_data_ptr;
 
   if(mmem_alloc(&mmem, sizeof(my_data)) == 0) {
     printf("memory allocation failed\n");
   } else {
     printf("memory allocation succeeded\n");
     my_data.a = 0xaa;
     memcpy(MMEM_PTR(&mmem), &my_data, sizeof(my_data));
     /* The cast below is safe only if the struct is packed */
     my_data_ptr = (struct my_struct *)MMEM_PTR(&mmem);
     printf("Value a equals 0x%x\n", my_data_ptr->a);
     mmem_free(&mmem);
   }
 }

The example above shows a basic example of how the managed memory library can be used. On line 4, we allocate a variable, mmem, that identifies the managed memory object that we are about to allocate. On line 13, we use the mmem variable as an argument for mmem_alloc() to allocate space for a structure of sizeof(my_data) bytes. If the allocation succeeded, we copy the values from an existing structure into the allocated structure, pointed to by MMEM_PTR(&mmem). Individual members of allocated structure can then be accessed by a type cast of MMEM_PTR(&mmem) to struct my_struct *, as shown on line 20. Note that the cast is only safe if the struct is packed. The managed memory is finally deallocated on line 21 by calling mmem_free().

Thread Safety

The mmem library is unsafe to use in preemptible code if it is also used in interrupt handlers or in MT threads. A module that uses a memory block could find its memory block relocated if the preemptive code called free.

In the ordinary case, the mmem library is used only within Contiki processes. Although such processes are cooperatively scheduled, it is necessary to ensure that each pointer to an address within in the memory block is updated when the process resumes control after waiting for an event. Any pointer to the block should then be reassigned using MMEM_PTR().

The malloc Heap Memory Allocator

The standard C library provides a set of functions for allocating and freeing memory in the heap memory space. Contiki platforms may specify a small area of their memory spaces for the heap.

Static allocations are typically preferable in memory-constrained systems because dynamic allocations may incur fragmentation. Allocation and deallocation patterns on objects of varying sizes may be problematic in some malloc implementations.

The Malloc API

void *malloc(size_t size); // Allocate uninitialized memory. 
void *calloc(size_t number, size_t size); // Allocate zero-initialized memory. 
void *realloc(void *ptr, size_t size); // Change the size of an allocated object. 
void free(void *ptr); // Free memory. 

All functions listed in this section are declared in the standard C header stdlib.h. The malloc() function allocates size bytes of memory on the heap. If the memory was successfully allocated, malloc() returns a pointer to it. If there was not enough contiguous free memory, malloc() returns NULL. Interested readers should get a book on the C programming language for a thorough description of the C malloc API.

calloc() works like malloc, but also ensures that allocated memory is zero-initialized. For unknown reasons, calloc() takes two arguments instead of one. The argument number denotes the amount of objects of a particular, specified by the size argument, that calloc() should allocate. Hence, the product of these two arguments is the size of the block of memory requested to be allocated.

The realloc() function reallocates a previously allocated block, ptr, with a new size. If the new block is smaller, size bytes of the data in the old block is copied into the new block. If the new block is larger, the complete old block is copied, and the rest of the new block contains unspecified data. Once the new block has been allocated, and its contents has been filled in, the old block is deallocated. realloc() returns NULL if the block could not be allocated. If the reallocation succeeded, realloc() returns a pointer to the new block.

free() deallocates a block that was previously allocated through malloc(), calloc(), or realloc(). The argument ptr must point to the start of an allocated block.

Conclusions

The memb library is a block allocator that use a statically declared memory area to store objects of a fixed size. The mmem library enables dynamic allocations with automatic defragmentation by using pointer indirection. Contiki also supports the malloc family of functions available in the standard C library. Although static memory is the most common type in Contiki, the methods presented here give programmers good options to dynamically adjusting the size the memory in use based on changing requirements during runtime.