La función alloca simplemente reserva espacio en la pila, o en otras palabras, modifica el puntero de pila. Esa es la razón por la que es tan eficiente, y es la misma razón por la que depende de la plataforma. La otra gran ventaja de alloca es que, puesto que solo modifica el puntero de pila, la memoria se libera automáticamente al salir de la función.

Que significa reservar memoria?

A no ser que ya sepas de que va esto de alloca, y en ese caso seguro que ya no estás leyendo esto, quizás no tengas muy claro como funciona el proceso de reservar memoria. Aquí tienes un curso intensivo :)

Cuando se lanza un proceso, el sistema operativo reserva varios bloques de memoria para su ejecución. Por una parte un bloque de memoria contendrá el código, otro los datos de solo lectura, otro las variables globales y otro la pila. Los dos primeros bloques son, en principio fijos, mientras que el tamaño de los dos últimos pueden variar durante la ejecución del programa.

El bloque de datos se puede modificar con las llamadas al sistema brk, mientras que la pila la modifica el programa a voluntad, básicamente modificando el puntero de pila.

En general, la pila crece hacia las direcciones bajas (hay algunos procesadores en los que va al revés) y el segmento de datos crece hacia las direcciones altas. Por esa razón, la pila se inicia en la zona alta de la memoria, y el segmento de datos en la zona baja. De esta forma tenemos el mayor hueco posible entre ambas, para reservar memoria, ya sea en la pila o en el segmento de datos.

NOTA:En realidad las librerías dinámicas se mapean en medio y medio de esa zona libre, pero eso no tiene relevancia para el tema que nos ocupa.

El mapa de memoria genérico de un proceso sería algo como esto:

  +--------------------+
  | Pila               | | Crece hacia abajo
  +--------------------+ v
  |                    |
  ~ Memoria Libre      |
  |                    |
  +--------------------+ ^
  | Segmento de Datos  | | Crece hacia arriba
  +--------------------+
  | Codigo + rodata    | rodata -> Datos solo-lectura
  +--------------------+

El Stack Frame

Si eres uno de nuestros asiduos lectores seguro que ya sabes de que va esto del Stack Frame, pero para los que recién os incorporáis, aquí tenéis una rápida introducción.

Cada vez que ejecutamos una función, el compilador crea para nosotros lo que se conoce como un marco de pila (stack frame en inglés). Este stack frame (voy a usar el término inglés, por que el español la verdad que da miedito), comienza con la dirección de retorno, que no es otra que la dirección de la siguiente instrucción a la que contiene el salto a la función. Dependiendo del procesador esto sucede de distintas formas, por ejemplo, los x86 utilizan la instrucción call que automáticamente añade la dirección de retorno a la pila. Otros procesadores almacenan la dirección en un registro especial y depende del programador hacer lo correcto con él.

El compilar añade a todas las funciones (a no ser que le digamos lo contrario), lo que se conoce como el prólogo de la función, que no es más que un par de líneas de código para crear el stack frame (si, yo considero la dirección de retorno parte del stack frame, pero eso es discutible). Este prólogo, normalmente almacena el valor del registro de pila (que apunta a la siguiente posición disponible en la pila) en un registro auxiliar que se suele conocer como registro base y que para los procesadores intel ha sido tradicionalmente el BP (Base Pointer ). A continuación modifica el registro de pila para reservar espacio para las variables locales.

El registro base RBP marca el comienzo de la zona de la pila asociada a esta función. Por esa razón debemos almacenarlo en algún sitio antes de modificarlo... bueno, la razón es que si nuestra función ha sido llamada por otra función, al entrar en ella, RBP apunta al stack frame de la función que llama, y cuando terminemos de ejecutar nuestra función queremos restaurarlo, para que al retornar la función llamante pueda continuar su ejecución... es decir, encuentre sus variables locales y su dirección de retorno.

El código del prólogo es normalmente algo como esto:

push RBP
mov  RBP, RSP
sub  RSP, ESPACIO_VARIABLES_LOCALES

Lo que nos deja la pila de esta forma

 | RET  | 
 | RBP  |
 |      | <--- RBP
 ~ ...  ~
 |      | <--- RSP = RBP - ESPACIO_VARIABLES

Como podéis ver, las variables locales se reservan en la pila, simplemente haciendo hueco (cambiando el valor del puntero de pila). De esta forma, podemos acceder a las variables locales de la función, con simples deplazamientos en el registro base (en realidad utilizando direccionamiento indexado sobre él).

Este código va acompañado de un epilogo, al final del la función, que simplemente hace lo siguiente:

mov RSP, EBP
pop RBP
ret

En otras palabras, restauramos nuestro puntero de pila al valor que tenía justo al entrar en la función, y restauramos el registro base con el stack frame anterior que habíamos almacenado en la pila... Tras eso, el valor al que apunta RSP es la dirección de retorno, con lo que ret retornará al lugar adecuado.

Los procesadores intel incorporan instrucciones para hacer estas dos cosas de forma automática. Las instrucciones enter y leave respectivamente ejecutan el prólogo y epilogo de la función. En general, enter no se utiliza ya que es menos eficiente que el código que os mostramos más arriba, así que raramente lo veréis en código real.

Esta sencilla estructura nos permite anidar fácilmente funciones y es la base sobre la que se pueden construir funciones recursivas.

alloca again

Pues, después de todo este rollo, ya os podéis imaginar que es lo que hace alloca... simplemente, modifica el puntero de pila, para hacer más hueco. Si tomamos como ejemplo el diagrama de pila anterior y suponemos que ejecutamos la función alloca (128), se nos quedaría tal que así:

 | RET  | 
 | RBP  |
 |      | <--- RBP
 ~ ...  ~
 |      | <--- Termina ESPACIO_VARIABLES
 ~ 128  ~
 | bytes|
 |      | <-- RSP

Como podéis ver, cuando se ejecuta el epílogo de la función, el puntero de pila, simplemente se resetea (se sobre escribe con el valor de RBP) y como resultado, toda la memoria está ahora disponible de nuevo para utilizarla con otro alloca u otra Stack Frame.

Esta es la razón por la que alloca es tan eficiente, básicamente hace una suma o una resta.... Para asegurarnos, veamos que genera gcc para la siguiente sencilla función:

void* func () {
  char *ptr;
  ptr = alloca (1024);
  memset (ptr, 0, 1024);
  return ptr;
}
int main () { func (); return 0;}

Nota: El memset es necesario para que al optimizar el código el compilador se de cuenta que hacemos algo con ptr y no lo elimine.

Si compilamos nuestro programa con la optimización '-O1':

gcc -O1 -o alloca-test alloca-test.c

La función func se quedaría más o menos así:

<func>:
    push   rbp
    xor    eax,eax
    mov    ecx,0x80
    mov    rbp,rsp
    sub    rsp,0x410
    lea    rdx,[rsp+0xf]
    and    rdx,0xfffffffffffffff0
    mov    rdi,rdx
    rep stos QWORD PTR es:[rdi],rax
    mov    rax,rdx
    leave
    ret

Analizando el código generado

Si reordenamos un poco el código...

    push   rbp
    mov    rbp,rsp
    sub    rsp,0x410
    
    lea    rdx,[rsp+0xf]
    and    rdx,0xfffffffffffffff0
        
    xor    eax,eax
    mov    ecx,0x80     
    mov    rdi,rdx
    rep stos QWORD PTR es:[rdi],rax
    mov    rax,rdx
    
    leave
    ret

Ahora podemos ver claramente el prólogo de la función y como reservamos espacio para los 1024 bytes reservados con alloca y 16 bytes más para almacenar el puntero... que para una arquitectura de 64 bits debe estar alineado a 16 bytes... aunque solo usemos 8.

Las dos instrucciones siguientes se encargan de alinear el puntero en la zona de la pila reservada. Veamos como está la pila justo después del prólogo, para entender que está pasando:

  | RET     |
  | RBP     | <- RBP
  |         |
  ~ ....    ~ <= 0x400 bytes de alloca
  |         | <= 0x10 bytes para el puntero
  |         | <- RSP = RBP - 0x410

Lo que el compilador ha hecho es reservar 0x10 bytes para almacenar nuestro puntero que realmente solo necesita 8 bytes en lugar de 16, para a continuación calcular la dirección de entre esas 16 que esté alineada a 16 bytes. Para ello lo que hace es lo siguiente: sumar 15 y luego borrar los últimos 4 bytes (o dividirlo por 16 si preferís).... que efectivamente significa alinear a 16 bytes (4 bits -> 16 valores).

Imaginad que el valor de RSP después de reservar la memoria es por ejemplo 0x01412, lo que significa que nuestro buffer está en 0x01432... por lo que tenemos que elegir una dirección entre esas dos que esté alineada a 16 bytes... o lo que es lo mismo que los últimos 4 bits sean cero.

Podríamos pensar en simplemente borrarlos... eso nos daría como resultado0x01410 que está fuera de nuestro rango (fuera de la pila), así que lo que hacemos es sumar 15... de forma que nos aseguramos que vamos a quedarnos en el rango disponible... pero sin tocar el buffer:

  0x001412 + 0xf = 0x001421

Si ahora borramos los últimos 4 bits, obtenemos la dirección 0x001420, que se encuentra en el rango adecuado de nuestra pila, nos da espacio suficiente para almacenar nuestro puntero de 8 bytes y además está alineado con la pila a 16 bytes.

El resto del programa no es más que la versión inline de memset... El único comentario es que stos en el código generado, usa registros de 64 bytes, por lo que el contador en rcx es solo 0x80 (0x80 * 8 = 0x400 = 1024)... vamos que copia de 8 en 8 bytes.

Stack vs Heap.... FIGHT!

Probablemente siempre has escuchado que la forma de reservar memoria en C es utilizando las funciones malloc y free. Si bien eso es lo normal, como hemos visto el proceso de reservar memoria es un poco más complicado que eso. Así que vamos a describir rápidamente como funcionan esas dos funciones.

Ya hemos hablado brevemente del segmento de datos y como modificarlo. Esa es la forma más sencilla de implementar un sistema de gestión de memoria dinámico. De hecho es un buen ejercicio. Si lo hacéis, veréis que hay muchos problemas que tener en cuenta y que no es nada fácil hacer uno de estos sistemas que funcione decentemente en cualquier situación.

Esa es la razón por la que la librería C de GNU no implementa una única estrategia para reservar memoria aunque nosotros, como programadores, no lo vemos. Esto lo podemos dejar para otro artículo en el futuro, ya que el funcionamiento interno del sistema de gestión de memoria es fundamental para entender ciertos ataques como los heap overflows, out by one,... relacionados con el heap.

Para terminar, deciros que existe otra forma más de reservar memoria (de hecho la implementación de malloc de la librería estándar también la utiliza), y no es otra que la llamada al systema mmap. mmap nos permite reservar bloques de memoria, con permisos específicos e incluso, mapearlos en direcciones específicas... todo esto con algunas limitaciones.... Parece una auténtica pasada no? Os preguntaréis porque no usamos mmap y ya está... bueno, hay distintas razones, pero lo fundamental es que mmap trabaja sobre páginas de memoria, no sobre direcciones. Lo que significa que si necesitamos 8 bytes, tendremos que reservar 4K (o el tamaño de página que sea que utilice el OS).

Como podéis ver, no existen las panaceas. Cada técnica tiene sus pros y sus contras y por ello debemos conocerlas todas para poder elegir la más adecuada.

Problemas con alloca

Para terminar este artículo, vamos a discutir brevemente los problemas que os podéis encontrar con alloca. La función no tiene ningún problema, y usada con cuidado puede hacer que nuestro programa sea mucho más eficiente, pero si nos despistamos, puede hacer que el programa falle de formas poco obvias.

Lo primero que tenemos que entender es que, en contra de lo que podría parecer, alloca no es una versión optimizada de malloc, aunque se use con ese objetivo. La principal consecuencia de esto es que objetos creados con alloca no pueden ser utilizados fuera de la función como ocurre con la memoria reservada con malloc.

Lo segundo es que la memoria reservada con alloca no hay que liberarla como ocurre con la memoria reservada con malloc. De hecho, ejecutar free sobre un bloque de memoria reservado por alloca puede ser fatal. La memoria reservada con alloca se libera de forma automática al dejar la función (como hemos visto antes).

alloca puede producir desbordamientos de pila, ya que la implementación muchas veces no hace ningún tipo de comprobación sobre los parámetros. De esta forma, si pasamos un valor negativo, por ejemplo, podríamos sobre escribir el stack frame de la función y hacer que el programa se estrelle... Probad a escribir alloca(-1024); en nuestro programa de ejemplo y observad que código se genera.

De la misma forma, utilizar valores muy grandes nos puede llevar fuera del bloque de memoria asociado a la pila y provocar un fallo de segmentación.... Sí, la pila no puede crecer indeterminadamente en el hueco libre en medio del espacio de direccionamiento del proceso, especialmente en un sistema multi-proceso. El segmento de pila tiene un tamaño y si nos pasamos de él se producirá una violación de segmento. Para ver donde se encuentra la pila para un determinado proceso podéis mirar el mapa de memoria del proceso en /proc/PID/maps donde PID es el identificador del proceso.

Otra cosa a tener en cuenta es que utilizar alloca solo tiene sentido cuando no conocemos el tamaño del bloque a reservar, ya que de lo contrario simplemente deberíamos declarar una variable local del tamaño adecuado. La principal ventaja de declarar la variable es que el compilador podrá hacer un mejor trabajo detectando posible bugs.

Conclusiones

Bueno, hasta aquí esta pequeña introducción a la función alloca y una no tan pequeña digresión sobre la gestión de memoria en procesos. Conocer los detalles de como funciona la gestión de memoria nos hace más fácil entender lo que hacemos en cada momento y reducir los bugs en nuestros programas.

alloca, si bien , no debería ser tu primera opción para manejar la memoria de tu programa, puede ser una optimización muy interesante en algunos casos cuando es usada con cuidado.