¿Cómo asignar memoria alineada solo usando la biblioteca estándar?

Respuesta original

{
    void *mem = malloc(1024+16);
    void *ptr = ((char *)mem+16) & ~ 0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

Respuesta fija

{
    void *mem = malloc(1024+15);
    void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

Explicación según lo solicitado

El primer paso es asignar suficiente espacio libre, por si acaso. Dado que la memoria debe estar alineada en 16 bytes (lo que significa que la dirección del byte inicial debe ser múltiplo de 16), agregar 16 bytes adicionales garantiza que tengamos suficiente espacio. En algún lugar de los primeros 16 bytes, hay un puntero alineado de 16 bytes. (Tenga en cuenta que malloc()se supone que devuelve un puntero que está suficientemente bien alineado para cualquier propósito. Sin embargo, el significado de 'cualquiera' es principalmente para cosas como tipos básicos: long, double, long double, long longy punteros a objetos y punteros a funciones. Cuando está Al hacer cosas más especializadas, como jugar con sistemas gráficos, pueden necesitar una alineación más estricta que el resto del sistema; de ahí preguntas y respuestas como esta).

El siguiente paso es convertir el puntero void en un puntero char; A pesar de GCC, se supone que no debes hacer aritmética de punteros en punteros vacíos (y GCC tiene opciones de advertencia para avisarte cuando abusas de ella). Luego agregue 16 al puntero de inicio. Supongamos que malloc()le devolvió un puntero increíblemente mal alineado: 0x800001. Sumar los 16 da 0x800011. Ahora quiero redondear hacia abajo hasta el límite de 16 bytes, por lo que quiero restablecer los últimos 4 bits a 0. 0x0F tiene los últimos 4 bits establecidos en uno; por lo tanto, ~0x0Ftiene todos los bits establecidos en uno excepto los últimos cuatro. Y agregar eso con 0x800011 da 0x800010. Puede iterar sobre las otras compensaciones y ver que funciona la misma aritmética.

El último paso, free(), es fácil: siempre, y sólo, regresas a free()un valor que uno de malloc(), calloc()o realloc()te devolvió; cualquier otra cosa es un desastre. Proporcionó correctamente memmantener ese valor, gracias. Lo libera gratis.

Finalmente, si conoce los aspectos internos del mallocpaquete de su sistema, puede suponer que bien podría devolver datos alineados de 16 bytes (o podría estar alineado con 8 bytes). Si estuviera alineado con 16 bytes, entonces no necesitaría preocuparse por los valores. Sin embargo, esto es dudoso y no portátil: otros mallocpaquetes tienen alineaciones mínimas diferentes y, por lo tanto, asumir una cosa cuando hace algo diferente conduciría a volcados de núcleo. Dentro de amplios límites, esta solución es portátil.

Alguien más mencionó posix_memalign()como otra forma de alinear la memoria; eso no está disponible en todas partes, pero a menudo podría implementarse usando esto como base. Nótese que era conveniente que el alineamiento fuera una potencia de 2; otras alineaciones son más complicadas.

Un comentario más: este código no verifica que la asignación se haya realizado correctamente.

Enmienda

El programador de Windows señaló que no se pueden realizar operaciones de máscara de bits en punteros y, de hecho, GCC (3.4.6 y 4.3.1 probado) se queja de eso. A continuación se presenta una versión modificada del código básico, convertido en un programa principal. También me he tomado la libertad de añadir sólo 15 en lugar de 16, como ya se ha señalado. Lo estoy usando uintptr_tdesde que C99 existe el tiempo suficiente para ser accesible en la mayoría de las plataformas. Si no fuera por el uso de PRIXPTRen las printf()declaraciones, sería suficiente #include <stdint.h>en lugar de usar #include <inttypes.h>. [Este código incluye la solución señalada por CR , que reiteraba un punto planteado por primera vez por Bill K hace varios años, que logré pasar por alto hasta ahora.]

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

int main(void)
{
    void *mem = malloc(1024+15);
    void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
    return(0);
}

Y aquí hay una versión ligeramente más generalizada, que funcionará para tamaños que son una potencia de 2:

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

static void test_mask(size_t align)
{
    uintptr_t mask = ~(uintptr_t)(align - 1);
    void *mem = malloc(1024+align-1);
    void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
    assert((align & (align - 1)) == 0);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

int main(void)
{
    test_mask(16);
    test_mask(32);
    test_mask(64);
    test_mask(128);
    return(0);
}

Para convertirla test_mask()en una función de asignación de propósito general, el valor de retorno único del asignador tendría que codificar la dirección de liberación, como lo han indicado varias personas en sus respuestas.

Problemas con los entrevistadores.

Uri comentó: Tal vez esté teniendo [un] problema de comprensión lectora esta mañana, pero si la pregunta de la entrevista dice específicamente: "¿Cómo asignarías 1024 bytes de memoria?" y claramente asignas más que eso. ¿No sería eso un fracaso automático por parte del entrevistador?

Mi respuesta no cabe en un comentario de 300 caracteres...

Depende, supongo. Creo que la mayoría de las personas (incluyéndome a mí) entendieron que la pregunta significaba "¿Cómo asignaría un espacio en el que se pueden almacenar 1024 bytes de datos y donde la dirección base es un múltiplo de 16 bytes?". Si el entrevistador realmente quiso decir cómo se pueden asignar 1024 bytes (solo) y alinearlos con 16 bytes, entonces las opciones son más limitadas.

• Claramente, una posibilidad es asignar 1024 bytes y luego darle a esa dirección el 'tratamiento de alineación'; El problema con ese enfoque es que el espacio disponible real no está adecuadamente determinado (el espacio utilizable está entre 1008 y 1024 bytes, pero no había un mecanismo disponible para especificar qué tamaño), lo que lo hace poco útil.
• Otra posibilidad es que se espere que escriba un asignador de memoria completo y se asegure de que el bloque de 1024 bytes que devuelve esté alineado adecuadamente. Si ese es el caso, probablemente terminará realizando una operación bastante similar a la que hizo la solución propuesta, pero la ocultará dentro del asignador.

Sin embargo, si el entrevistador esperaba cualquiera de esas respuestas, esperaría que reconociera que esta solución responde a una pregunta estrechamente relacionada y luego reformulara su pregunta para orientar la conversación en la dirección correcta. (Además, si el entrevistador se volviera muy irritable, entonces no querría el trabajo; si la respuesta a un requisito insuficientemente preciso es derribada sin corrección, entonces el entrevistador no es alguien para quien sea seguro trabajar).

El mundo sigue adelante

El título de la pregunta ha cambiado recientemente. Fue la pregunta de la entrevista Resolver la alineación de la memoria en C lo que me dejó perplejo . El título revisado (¿ Cómo asignar memoria alineada solo usando la biblioteca estándar? ) exige una respuesta ligeramente revisada: este anexo la proporciona.

Función agregada C11 (ISO/IEC 9899:2011) aligned_alloc():

7.22.3.1 La aligned_allocfunción

Sinopsis

#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);

Descripción
La aligned_allocfunción asigna espacio para un objeto cuya alineación está especificada por alignment, cuyo tamaño está especificado por sizey cuyo valor es indeterminado. El valor de alignmentserá una alineación válida respaldada por la implementación y el valor de sizeserá un múltiplo entero de alignment.

Devuelve
La aligned_allocfunción devuelve un puntero nulo o un puntero al espacio asignado.

Y POSIX define posix_memalign():

#include <stdlib.h>

int posix_memalign(void **memptr, size_t alignment, size_t size);

DESCRIPCIÓN

La posix_memalign()función asignará sizebytes alineados en un límite especificado por alignmenty devolverá un puntero a la memoria asignada en memptr. El valor de alignmentserá una potencia de dos múltiplo de sizeof(void *).

Una vez completado con éxito, el valor señalado por memptrserá un múltiplo de alignment.

Si el tamaño del espacio solicitado es 0, el comportamiento está definido por la implementación; el valor devuelto memptrserá un puntero nulo o un puntero único.

La free()función desasignará la memoria que ha sido previamente asignada por posix_memalign().

VALOR DEVUELTO

Una vez completado con éxito, posix_memalign()devolverá cero; de lo contrario, se devolverá un número de error para indicar el error.

Cualquiera o ambos podrían usarse para responder la pregunta ahora, pero solo la función POSIX era una opción cuando se respondió la pregunta originalmente.

Detrás de escena, la nueva función de memoria alineada hace prácticamente el mismo trabajo que se describe en la pregunta, excepto que tiene la capacidad de forzar la alineación más fácilmente y realizar un seguimiento del inicio de la memoria alineada internamente para que el código no tiene que tratar especialmente: simplemente libera la memoria devuelta por la función de asignación que se utilizó.

Oct 22 '2008 23:10 Jonathan Leffler