Librería alloc -- asignación dinámica de memoria en Arduino

¿Qué es la asignación dinámica de memoria?

Es la solicitud de un programa para reservar un bloque de memoria en tiempo de ejecución. Se consigue a través de las funciones malloc() y free() en C/C++. No obstante, en sistemas embebidos como los microcontroladores, este recurso de la programación puede derivar en problemas graves.

* Limitación de recursos: los MCUs no comparten las mismas característicias en el hardware que los ordenadores de uso personal, son menos potentes.

* Fragmentación de la memoria: la asignación y liberación repetida de bloques de memoria conduce a problemas de fragmentación, lo que dificulta la asignación de bloques contiguos.

* Predictibilidad: la gestión dinámica de la memoria puede hacer que el programa sea menos predecible, lo cual es especialmente crítico en sistemas embebidos; ya que afecta directamente al tiempo de respuesta de los recursos compartidos.

¿Cómo se divide la memoria en un programa?

Durante el proceso de compilación, se traduce el código fuente a código máquina y se genera los archivos objeto que contienen información sobre el código y los datos. Posteriormente, los archivos objeto se combinan (gracias al enlazador) para formar un programa ejecutable. En esta fase, se asignan direcciones de memoria a las diferentes secciones de memoria que resuelven las referencias a símbolos entre los distintos ficheros objeto.

Las secciones de memoria son:

* .TEXT: contiene el código máquina de las instrucciones del programa. Esta sección es de sólo lectura y ejecución.

* .DATA: almacena datos inicializados, como variables globales o estáticas, constantes, etc.

* .BSS: almacena datos no inicializados, es decir, durante el enlazado se reserva un espacio determinado para estas variables.

Ahora bien, existen otras dos áreas de memoria utilizadas durante la ejecución de un programa.

* Heap: es una región destinada a la asignación dinámica de memoria, por lo general, de estructuras de datos grandes, como instancias o matrices.

* Stack: es la región de memoria empleada para almacenar las variables locales y registros de activación de funciones. Funciona como una FIFO (First In First Out).

¿Y qué tiene que ver todo ésto?

El stack y el heap comparten los mismos recursos de memoria física, de manera que pueden ser limitantes y muy problemáticos si el programador no tiene cuidado. Habitualmente el S.O. ya se encarga de arbitrar el uso entre estas dos regiones, de modo que lo que no suele ser un problema en el diseño de software para computadoras, se vuelve toda una odisea en microcontroladores.

Yo he desarrollado una pequeña librería para facilitar la asignación dinámica de memoria en sistemas embebidos, como el microcontrolador Atmega328 (comúnmente conocido como "Arduino"); aunque también ha sido testada en un microcontrolador de Renesas R6T1, con unos cambios mínimos y evidentes en la directivas a los encabezados de las bibliotecas. Mi librería alloc se basa en la reserva estática de memoria en el segmento .BSS, haciendo uso de un memory pool personalizado.

¡A continuación os comparto el código! Espero que os guste.

Encabezado

Código:

/**
 * Author:     profinet
 * Date:       November 14, 2023
 * Version:    v0.1
 * 
 * @file alloc.h
 * @brief Memory allocation library for Arduino.
 *
 * This library provides a memory allocation manager for Arduino projects,
 * allowing efficient allocation and deallocation of memory from a predefined
 * memory pool. The memory pool is divided into fixed-size blocks, and the
 * library supports allocation of contiguous blocks for larger memory needs.
 *
 * Usage:
 * 1. Include the library in your Arduino sketch: #include "alloc.h"
 * 2. Create an instance of the alloclib class: alloclib myMemoryAllocator;
 * 3. Use the alloc and dealloc methods to manage memory dynamically.
 *
 * Note: This library is designed for projects where dynamic memory
 * allocation is required, and it may not be suitable for all applications.
 */

#ifndef ALLOC_H
#define ALLOC_H

#include <Arduino.h>

/* Define the size of the memory pool and the block size */
#define MEMORY_POOL_SIZE 1024
#define BLOCK_SIZE 32

// Define a structure to represent a block of memory
struct MemoryBlock {
	int size;
	uint8_t *data;
};

class alloclib {
public:

	alloclib() {
		init();
	}
	~alloclib() {
	}

	void* alloc(uint16_t size);
	void dealloc(void *ptr, uint16_t size);

	template<typename T>
	T* alloc(int count = 1);

	template<typename T>
	void dealloc(T *ptr, int count = 1);

private:

	void init();
	void* allocFromPool(int16_t size);
	void deallocFromPool(void *ptr, uint16_t size);

	MemoryBlock blocks[MEMORY_POOL_SIZE / BLOCK_SIZE];
	uint8_t memoryPool[MEMORY_POOL_SIZE];
};

/**
 * @brief Allocates an array of elements of type T from the memory pool.
 *
 * This templated function allocates memory for an array of elements of type T
 * from the memory pool.
 *
 * It calculates the required size based on the count of
 * elements and checks for potential overflow. If the allocation is successful,
 * it returns a pointer to the allocated memory; otherwise, it returns nullptr.
 *
 * @tparam T The type of elements in the array.
 * @param count The number of elements to allocate.
 * @return A pointer to the allocated array, or nullptr if allocation fails.
 */
template<typename T>
T* alloclib::alloc(int count) {
	size_t sizeRequired = static_cast<size_t>(count) * sizeof(T);

	// Check for potential overflow
	if (sizeRequired > MEMORY_POOL_SIZE) {
		/* TODO: Handle the error or report it in a way that makes sense for your application */
		// Return nullptr to indicate allocation failure
		return nullptr;
	} else {
		// Perform the allocation
		return static_cast<T*>(allocFromPool(
				static_cast<uint16_t>(sizeRequired)));
	}
}

/**
 * @brief Deallocates an array of elements of type T back to the memory pool.
 *
 * This templated function deallocates memory for an array of elements of type T
 * previously allocated from the memory pool.
 *
 * It calculates the required size
 * based on the count of elements and checks for potential overflow. If the
 * deallocation is successful, it updates the memory pool; otherwise, it may
 * handle the error or report it in a way that makes sense for your application.
 *
 * @tparam T The type of elements in the array.
 * @param ptr A pointer to the array to deallocate.
 * @param count The number of elements in the array.
 */
template<typename T>
void alloclib::dealloc(T *ptr, int count) {
	size_t sizeRequired = static_cast<size_t>(count) * sizeof(T);

	// Check for potential overflow
	if (sizeRequired > MEMORY_POOL_SIZE) {
		/* TODO: Handle the error or report it in a way that makes sense for your application */
	} else {
		// Perform the deallocation
		deallocFromPool(ptr, static_cast<uint16_t>(sizeRequired));
	}
}

#endif  // ALLOC_H

Archivo de implementación

Código:

/**
 * Author:     profinet
 * Date:       November 14, 2023
 * Version:    v0.1
 * 
 * @file alloc.h
 * @brief Memory allocation library for Arduino.
 *
 * This library provides a memory allocation manager for Arduino projects,
 * allowing efficient allocation and deallocation of memory from a predefined
 * memory pool. The memory pool is divided into fixed-size blocks, and the
 * library supports allocation of contiguous blocks for larger memory needs.
 *
 * Usage:
 * 1. Include the library in your Arduino sketch: #include "alloc.h"
 * 2. Create an instance of the alloclib class: alloclib myMemoryAllocator;
 * 3. Use the alloc and dealloc methods to manage memory dynamically.
 *
 * Note: This library is designed for projects where dynamic memory
 * allocation is required, and it may not be suitable for all applications.
 */

#include <Arduino.h>
#include "alloc.h"

/**
 * @brief Initializes the memory pool with contiguous blocks of memory.
 *
 * This function initializes the memory pool by dividing it into contiguous
 * blocks of fixed size. It sets up the initial state of each block, including
 * its size and data pointer, based on the predefined block size and the size
 * of the memory pool.
 */
void alloclib::init() {
	for (int i = 0; i < MEMORY_POOL_SIZE / BLOCK_SIZE; ++i) {
		blocks[i].size = BLOCK_SIZE;
		blocks[i].data = &memoryPool[i * BLOCK_SIZE];
	}
}

/**
 * @brief Allocates a block of memory from the memory pool.
 *
 * This function attempts to allocate a block of memory of the specified size
 * from the memory pool. It first checks for contiguous blocks to satisfy the
 * request efficiently.
 *
 * If the requested size is greater than one block, it
 * searches for a sequence of contiguous blocks. If found, it allocates the
 * memory and returns a pointer to the allocated block.
 *
 * If the requested size is within a single block, it looks for a block with sufficient free space.
 * If found, it allocates the memory and returns a pointer to the allocated
 * block. If no suitable block is found, it returns nullptr.
 *
 * @param size The size of the memory block to allocate.
 * @return A pointer to the allocated memory block, or nullptr if allocation fails.
 */
void* alloclib::allocFromPool(int16_t size) {
	if (size > 0) {
		int blocksNeeded = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
		if (blocksNeeded > 1) {
			// Iterate through the memory pool to find a sequence of contiguous blocks
			for (int i = 0; i < MEMORY_POOL_SIZE / BLOCK_SIZE; ++i) {
				int contiguousBlocks = 0;

				// Check for contiguous blocks with sizes >= BLOCK_SIZE
				while (i + contiguousBlocks < MEMORY_POOL_SIZE / BLOCK_SIZE
						&& blocks[i + contiguousBlocks].size >= BLOCK_SIZE) {
					contiguousBlocks++;
					if (contiguousBlocks == blocksNeeded) {
						break;
					}
				}

				if (contiguousBlocks == blocksNeeded) {
					void *ptr = blocks[i].data;

					// Mark the blocks as allocated (size = 0)
					for (int j = 0; j < contiguousBlocks; ++j) {
						blocks[i + j].size = 0;

						// Update data pointers for subsequent blocks
						if (j < contiguousBlocks - 1) {
							blocks[i + j + 1].data = blocks[i + j].data +
							BLOCK_SIZE;
						}
					}

					// Return the pointer to the allocated memory
					return ptr;
				}
			}
			return nullptr;
		}

		// If the requested size is within one block
		for (int i = 0; i < MEMORY_POOL_SIZE / BLOCK_SIZE; ++i) {
			if (blocks[i].size >= size) {
				void *ptr = blocks[i].data;

				// Update the size and data pointer for the allocated block
				blocks[i].size -= size;
				blocks[i].data += size;
				return ptr;
			}
		}
	}
	return nullptr; // Not enough free space
}

/**
 * @brief Deallocates a block of memory back to the memory pool.
 *
 * This function deallocates a block of memory previously allocated from the
 * memory pool. It takes a pointer to the memory block and its size as
 * parameters.
 *
 * The function searches for the corresponding block in the memory
 * pool based on the provided pointer. It updates the size of the block and
 * coalesces adjacent free blocks if applicable.
 *
 * @param ptr A pointer to the memory block to deallocate.
 * @param size The size of the memory block to deallocate.
 */
void alloclib::deallocFromPool(void *ptr, uint16_t size) {
	if (ptr != nullptr && size > 0) {
		for (int i = 0; i < MEMORY_POOL_SIZE / BLOCK_SIZE; ++i) {

			// Check if the pointer is within the range of the current block
			if (ptr >= blocks[i].data && ptr < blocks[i].data + BLOCK_SIZE) {
				// Increase the size of the block by the deallocated size
				blocks[i].size += size;

				// Check if there is a next block and it is also free
				if (i < MEMORY_POOL_SIZE / BLOCK_SIZE - 1
						&& blocks[i + 1].size > 0) {
					if (blocks[i].data + BLOCK_SIZE == blocks[i + 1].data) {
						// Merge the current block with the next block
						blocks[i].size += blocks[i + 1].size;
						blocks[i + 1].size = 0;
					}
				}
				return;
			}
		}
	}
}

Ejemplo de uso en Arduino

Código:

#include "alloc.h"

alloclib allc;

void setup() {
  Serial.begin(9600);
}

void loop() {
  int size = 10;

  // Allocate and print intArray
  int* intArray = allc.alloc<int>(size);
  if (intArray != nullptr) {
    for (size_t i = 0; i < size; i++) {
      intArray[i] = i * 2;
      Serial.print(intArray[i]);
      Serial.print(" ");
    }
    Serial.println();  // Move to the next line
  }
  allc.dealloc(intArray, size);
  delay(1000);

  // Allocate and print doubleArray
  double* doubleArray = allc.alloc<double>(size);
  if (doubleArray != nullptr) {
    for (size_t i = 0; i < size; i++) {
      doubleArray[i] = i * 1.5;
      Serial.print(doubleArray[i]);
      Serial.print(" ");
    }
    Serial.println();  // Move to the next line
  }
  allc.dealloc(doubleArray, size);
  delay(1000);

  // Allocate and print charArray
  char* charArray = allc.alloc<char>(size);
  if (charArray != nullptr) {
    charArray[0] = 'h';
    charArray[1] = 'e';
    charArray[2] = 'l';
    charArray[3] = 'l';
    charArray[4] = 'o';
    charArray[5] = '\0';  // Null terminator to make it a valid C-string

    Serial.print(charArray);
    Serial.println();  // Move to the next line
  }
  allc.dealloc(charArray, size);
  delay(1000);
}