(void *) blog

Posted on by fortytwo_de


La asignación dinámica de memoria es un tema complicado. Aunque lo realmente complicado es liberar la memoria después de haber sido asignada. En este post voy a asumir un sistema de 16 bits, porque es en lo que he hecho mi implementación de malloc/free.

Watermark allocator

La forma más simple de asignar memoria es mantener un puntero de la última dirección de memoria asignada. Este sistema de asignación se llama Watermark allocator.

El mapa de memoria original sería:

0000: [0001] 0000 0000 0000 0000 0000 0000 0000
0008:  0000  0000 0000 0000 0000 0000 0000 0000

Al solicitar un bloque de 8 words, se incrementa el puntero de memoria. Muy simple.

0000: [0009] 0000 0000 0000 0000 0000 0000 0000
0008:  0000  0000 0000 0000 0000 0000 0000 0000

Luego, el programa podría llenar su región asignada de la memoria con los valores que necesite:

0000: [0009] AAAA AAAA AAAA AAAA AAAA AAAA AAAA
0008:  AAAA  0000 0000 0000 0000 0000 0000 0000

Ventajas

  • Muy simple de implementar.

Desventajas

  • No se puede implementar free. (muy importante)

Fixed size allocation

Otra forma de asignar memoria dinámicamente es con una lista de páginas de tamaño fijo (blocks). Cada vez que se pide un bloque de n words, se redondea al menor número de bloques del tamaño predefinido cuyo tamaño total es mayor o igual que lo solicitado. Con este tipo de asignación de memoria es necesario mantener una lista de los bloques que están siendo utilizados.

En este ejemplo, las 4 primeras words de la memoria se usarán para mantener la tabla.

0000: [0000 0000 0000 0000] 0000 0000 0000 0000
0008:  0000 0000 0000 0000  0000 0000 0000 0000

Usaré bloques de 4 palabras, pero podrían ser de más. Si un proceso solicita 9 palabras de memoria, se redondea y se le asignan 3 bloques (3 * 4 >= 9).

0000: [0001 0001 0001 0000] AAAA AAAA AAAA AAAA
0008:  AAAA AAAA AAAA AAAA  AAAA BBBB BBBB BBBB

Aquí, he llenado de 0xAAAA las posiciones de memoria que corresponden a las 9 primeras palabras solicitadas, y he llenado de 0xBBBB las que corresponden a posiciones que se han asignado a ese proceso pero que no habían sido solicitadas originalmente.

En la tabla de asignación se pueden usar el resto de bits para otros flags, pero en este ejemplo simple he utilizado simplemente el bit menos significante para marcar "usado" o "libre".

Ventajas

  • Se pueden liberar bloques de memoria.
  • Sobran 15 bits en cada word de la tabla de asignación que se pueden usar para almacenar metadatos sobre la página de memoria.

Desventajas

  • La tabla de asignación ocupa espacio en memoria, lo cual es muy importante en sistemas con recursos reducidos.
  • En ocasiones (como el ejemplo anterior), algunos bytes pueden desperdiciarse. También importante en sistemas reducidos.

0x42c/KnightOS allocator

El algoritmo es un poco más complejo, pero las ventajas merecen la pena. El concepto es relativamente simple: los bloques de memoria tienen una cabecera y un pie. La cabecera son dos words.

typedef struct {
    uint16_t owner;
    uint16_t size;
} header_t;

Y el pie es básicamente un puntero a la cabecera. La ventaja de este sistema de asignación de memoria es que se puede asignar un número arbitrario de bloques con un tamaño arbitrario.

Un dato importante es que el owner de la memoria libre es 0xffff. Por lo tanto, el estado inicial de la memoria sería el siguiente:

0000: ffff 000d [0000 0000 0000 0000 0000  0000
0008: 0000 0000  0000 0000 0000 0000 0000] 0000

La última word es 0x0000 pero porque es el puntero a la cabecera, que se encuentra en la posición 0xffff. El espacio útil de memoria está marcado por los corchetes. El tamaño del bloque son 12 words, 0x000d en hexadecimal.

Si un programa con ID 0x042c quisiese asignarse 5 palabras de memoria:

0000: 042c 0005 [0000 0000 0000 0000 0000] 0000
0008: ffff 0000  0000 0000 0000 0000 0000  0008

El algoritmo para asignar memoria es muy sencillo.

  • La variable mempointer es igual a memory_start (una variable que contiene la primera word de memoria)
  • Se comprueba si el valor de la celda de memoria en la posición [mempointer] es 0xffff.
    • Si lo es, se comprueba el tamaño. Si es igual o mayor que el solicitado, se cambia el campo [owner] de la cabecera
      • Se intenta subdividir el bloque de memoria libre en uno con [owner] 0xffff.
        • Si no se puede porque el espacio restante en el bloque es inferior al necesario para establecer un bloque de memoria, se añade el espacio restante al tamño de bloque a asignar.
    • Si no lo es, se sigue escaneando la memoria.
  • Si no lo es, se añade 1 a mempointer, y se añade el valor de la memoria en esa celda a mempointer. Dicho de otra forma, se añade la longitud de ese bloque de memoria para "saltárselo".

Implementación de malloc siguiendo este concepto (DCPU-16 ASM):

:mem_start dat 0x0
:mem_end dat 0x10000

:malloc
    set push, i ; se guarda el valor del registro I
    set i, [mem_start]

    :malloc_loop
        ife [i], 0xffff ; si la celda de memoria en i es 0xffff...
            set pc, malloc_found_free

        ; si no...
        add i, 1 
        add i, [i]
        add i, 2 ; se salta un bloque de memoria no vacía

        set pc, malloc_loop
    :malloc_found_free
        ife i, [mem_start] ; si es el principio de la memoria no necesitamos comprobar el tamaño
            set pc, malloc_allocate

        add i, 1 ; [i] es ahora el tamaño del bloque

        ife [i], a ; si exactamente igual... 
            set pc, malloc_prepare ; ... se asigna la memoria.
        ifg [i], a ; si es mayor que el tamaño pedido...
            set pc, malloc_check_overhead ; se intanta subdividir la memoria en un bloque vacío

        add i, 1
        add i, [i] ; size of block

        set pc, malloc_loop    

    :malloc_check_overhead
        set push, b ; se guarda el registro b en el stack
        set b, [i]
        sub b, a
        ifg b, 3 ; si hay más de tres bloques libres... 
            set pc, malloc_check_end ; se salta al final

        ; si no... 
        sub i, 1
        set b, pop ; se devuelve b a su estado original
        set [i], b ; no merece la pena dividir el espacio restante
        set push, i
        set pc, malloc_end

        :malloc_check_end
            set b, pop
            set pc, malloc_prepare    

    :malloc_prepare
        sub i, 1
        set pc, malloc_allocate

    :malloc_allocate ; entender esta función es un ejercicio para el lector.
        set push, i
        set push, i
        set [i], b
        add i, 1
        set [i], a
        add i, 1
        add i, a
        set b, pop
        set [i], b ; header pointer

        add i, 1
        set a, i
        set b, [mem_end]
        jsr set_initial_blocks
        set pc, malloc_end

    :malloc_end
        set a, pop
        add a, 2 ; se devuelve el principio de la memoria usable.
        set i, pop
        set pc, pop ; hecho!

(puedes ver el código aquí.)

Y en el siguiente capítulo, free!

Posted on by fortytwo_de | Posted in Algoritmos, osdev, Programación


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>