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

422

Acabo de terminar una prueba como parte de una entrevista de trabajo, y una pregunta me dejó perplejo, incluso usando Google como referencia. Me gustaría ver qué puede hacer el equipo de StackOverflow con él:

La memset_16alignedfunción requiere que se le pase un puntero alineado de 16 bytes o se bloqueará.

a) ¿Cómo asignaría 1024 bytes de memoria y los alinearía a un límite de 16 bytes?
b) Libere la memoria después de que se memset_16alignedhaya ejecutado.

{    
   void *mem;
   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here    
}
JimDaniel
fuente
89
hmmm ... para la viabilidad del código a largo plazo, ¿qué tal "despedir a quien escribió memset_16 alineado y arreglarlo o reemplazarlo para que no tenga una condición límite peculiar"
Steven A. Lowe
29
Ciertamente, una pregunta válida para hacer - "por qué la alineación peculiar de la memoria". Pero puede haber buenas razones para ello: en este caso, podría ser que memset_16aligned () pueda usar enteros de 128 bits y esto es más fácil si se sabe que la memoria está alineada. Etc.
Jonathan Leffler
55
Quien escribió memset podría usar una alineación interna de 16 bytes para borrar el bucle interno y un pequeño prólogo / epílogo de datos para limpiar los extremos no alineados. Eso sería mucho más fácil que hacer que los codificadores manejen punteros de memoria adicionales.
Adisak
8
¿Por qué alguien querría datos alineados a un límite de 16 bytes? Probablemente para cargarlo en registros SSE de 128 bits. Creo que los movs (más nuevos) no alineados (por ejemplo, movupd, lddqu) son más lentos, o tal vez están apuntando a procesadores sin SSE2 / 3
11
La alineación de la dirección conduce a un uso optimizado de la memoria caché, así como a un mayor ancho de banda entre los diferentes niveles de memoria caché y RAM (para la mayoría de las cargas de trabajo comunes). Vea aquí stackoverflow.com/questions/381244/purpose-of-memory-alignment
Deepthought el

Respuestas:

587

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 a 16 bytes (lo que significa que la dirección de byte inicial debe ser un múltiplo de 16), agregar 16 bytes adicionales garantiza que tenemos 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 alineada para cualquier . Propósito Sin embargo, el significado de 'cualquier' es principalmente para cosas como tipos básicos - long, double, long double, long long., Y los 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, por lo tanto, preguntas y respuestas como esta).

El siguiente paso es convertir el puntero vacío en un puntero char; A pesar de GCC, se supone que no debe hacer aritmética de puntero en punteros nulos (y GCC tiene opciones de advertencia para informarle cuando abusa de él). Luego agregue 16 al puntero de inicio. Supongamos que le malloc()devuelve un puntero imposiblemente mal alineado: 0x800001. Agregar los 16 da 0x800011. Ahora quiero redondear al 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 eso con 0x800011 da 0x800010. Puede iterar sobre los otros desplazamientos y ver que funciona la misma aritmética.

El último paso, free()es fácil: siempre, y sólo, el retorno a free()un valor que uno de malloc(), calloc()o realloc()devuelto a usted - todo lo demás es un desastre. Usted proporcionó correctamente mempara mantener ese valor, gracias. Lo libera gratis.

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

Alguien más mencionó posix_memalign()como otra forma de obtener la memoria alineada; eso no está disponible en todas partes, pero a menudo podría implementarse utilizando esto como base. Tenga en cuenta que era conveniente que la alineación tuviera una potencia de 2; otras alineaciones son más desordenadas.

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 así. Entonces, sigue una versión enmendada del código básico, convertida en un programa principal. También me he tomado la libertad de agregar solo 15 en lugar de 16, como se ha señalado. Estoy usando uintptr_tya que C99 ha existido 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 en #include <stdint.h>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 marginalmente más generalizada, que funcionará para tamaños que tienen 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 convertir 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 publicación, como varias personas han indicado en sus respuestas.

Problemas con los entrevistadores.

Uri comentó: Tal vez tengo [un] problema de comprensión de lectura 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 un fracaso automático del entrevistador?

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

Depende, supongo. Creo que la mayoría de la gente (incluyéndome a mí) consideró 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 puede asignar 1024 bytes (solo) y alinearlo con 16 bytes, entonces las opciones son más limitadas.

  • Claramente, una posibilidad es asignar 1024 bytes y luego dar a esa dirección el 'tratamiento de alineación'; El problema con ese enfoque es que el espacio disponible real no está correctamente 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 menos útil.
  • Otra posibilidad es que se espera que escriba un asignador de memoria completa y se asegure de que el bloque de 1024 bytes que devuelve esté alineado adecuadamente. Si ese es el caso, probablemente termines haciendo una operación bastante similar a la que hizo la solución propuesta, pero la ocultas dentro del asignador.

Sin embargo, si el entrevistador esperaba cualquiera de esas respuestas, esperaría que reconocieran que esta solución responde a una pregunta estrechamente relacionada, y luego que reformule su pregunta para dirigir la conversación en la dirección correcta. (Además, si el entrevistador se pusiera realmente escaso, 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 resolver la alineación de la memoria en la pregunta de la entrevista 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 apéndice lo 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 se especifica por alignment, cuyo tamaño se especifica 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 integral 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 alignment, y devolverá un puntero a la memoria asignada en memptr. El valor de alignmentserá una potencia de dos múltiplos de sizeof(void *).

Al completar 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 debe desasignar la memoria que previamente ha sido asignada por posix_memalign().

VALOR DEVUELTO

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

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

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

Jonathan Leffler
fuente
13
Y estoy oxidado con C ++, pero realmente no confío en que ~ 0x0F se expandirá correctamente al tamaño del puntero. Si no es así, todo el infierno se desatará porque también enmascararás los bits más significativos de tu puntero. Aunque podría estar equivocado sobre eso.
Bill K
66
Por cierto, '+15' funciona tan bien como '+16' ... sin embargo, no hay impacto práctico en esta situación.
Menkboy
15
Los comentarios '+ 15' de Menkboy y Greg son correctos, pero malloc () casi seguramente redondeará eso a 16 de todos modos. Usar +16 es marginalmente más fácil de explicar. La solución generalizada es complicada, pero factible.
Jonathan Leffler
66
@Aerovistae: es una pregunta un poco engañosa, y depende principalmente de su comprensión de cómo hacer que un número arbitrario (en realidad, la dirección que devuelve el asignador de memoria) coincida con un determinado requisito (múltiplo de 16). Si le pidieran redondear 53 al múltiplo más cercano de 16, ¿cómo haría eso? El proceso no es muy diferente para las direcciones; es solo que los números con los que normalmente estás tratando son mayores. No olvide que las preguntas de la entrevista se hacen para saber cómo piensa, no para saber si sabe la respuesta.
Jonathan Leffler
3
@akristmann: el código original es correcto si tiene <inttypes.h>disponible desde C99 (al menos para la cadena de formato, posiblemente, los valores deben pasarse con un reparto :) (uintptr_t)mem, (uintptr_t)ptr. La cadena de formato se basa en la concatenación de cadenas y la macro PRIXPTR es el printf()especificador de longitud y tipo correcto para la salida hexadecimal de un uintptr_tvalor. La alternativa es usarla, %ppero la salida de eso varía según la plataforma (algunos agregan un líder 0x, la mayoría no) y generalmente se escribe con dígitos hexadecimales en minúscula, lo que no me gusta; Lo que escribí es uniforme en todas las plataformas.
Jonathan Leffler
58

Tres respuestas ligeramente diferentes dependiendo de cómo veas la pregunta:

1) Lo suficientemente bueno para la pregunta exacta es la solución de Jonathan Leffler, excepto que para redondear a 16 alineados, solo necesita 15 bytes adicionales, no 16.

UNA:

/* allocate a buffer with room to add 0-15 bytes to ensure 16-alignment */
void *mem = malloc(1024+15);
ASSERT(mem); // some kind of error-handling code
/* round up to multiple of 16: add 15 and then round down by masking */
void *ptr = ((char*)mem+15) & ~ (size_t)0x0F;

SI:

free(mem);

2) Para una función de asignación de memoria más genérica, la persona que llama no quiere tener que realizar un seguimiento de dos punteros (uno para usar y otro para liberar). Por lo tanto, almacena un puntero al búfer 'real' debajo del búfer alineado.

UNA:

void *mem = malloc(1024+15+sizeof(void*));
if (!mem) return mem;
void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;
((void**)ptr)[-1] = mem;
return ptr;

SI:

if (ptr) free(((void**)ptr)[-1]);

Tenga en cuenta que, a diferencia de (1), donde solo se agregaron 15 bytes a mem, este código podría reducir la alineación si su implementación garantiza una alineación de 32 bytes de malloc (poco probable, pero en teoría una implementación de C podría tener un byte de 32 bytes) tipo alineado). Eso no importa si todo lo que haces es llamar a memset_16aligned, pero si usas la memoria para una estructura, entonces podría importar.

No estoy seguro de qué es una buena solución para esto (aparte de advertir al usuario que el búfer devuelto no es necesariamente adecuado para estructuras arbitrarias) ya que no hay forma de determinar programáticamente cuál es la garantía de alineación específica de la implementación. Supongo que al inicio podría asignar dos o más almacenamientos intermedios de 1 byte, y asumir que la peor alineación que ve es la alineación garantizada. Si te equivocas, desperdicias memoria. Alguien con una idea mejor, por favor dígalo ...

[ Agregado : El truco 'estándar' es crear una unión de 'tipos probablemente alineados al máximo' para determinar la alineación requerida. Es probable que los tipos máximamente alineados sean (en C99) ' long long', ' long double', ' void *' o ' void (*)(void)'; si incluye <stdint.h>, presumiblemente podría usar ' intmax_t' en lugar de long long(y, en máquinas Power 6 (AIX), intmax_tle daría un tipo entero de 128 bits). Los requisitos de alineación para esa unión se pueden determinar incrustándolos en una estructura con un único carácter seguido por la unión:

struct alignment
{
    char     c;
    union
    {
        intmax_t      imax;
        long double   ldbl;
        void         *vptr;
        void        (*fptr)(void);
    }        u;
} align_data;
size_t align = (char *)&align_data.u.imax - &align_data.c;

Luego usaría la alineación solicitada más grande (en el ejemplo, 16) y el alignvalor calculado anteriormente.

En (64 bits) Solaris 10, parece que la alineación básica del resultado malloc()es un múltiplo de 32 bytes.
]

En la práctica, los asignadores alineados a menudo toman un parámetro para la alineación en lugar de estar cableados. Entonces, el usuario pasará el tamaño de la estructura que le importa (o la menor potencia de 2 mayor o igual a eso) y todo estará bien.

3) Use lo que proporciona su plataforma: posix_memalignpara POSIX, _aligned_mallocen Windows.

4) Si usa C11, la opción más limpia, portátil y concisa, es usar la función de biblioteca estándar aligned_allocque se introdujo en esta versión de la especificación del lenguaje.

Steve Jessop
fuente
1
Estoy de acuerdo, creo que la intención de la pregunta es que el código que libera el bloque de memoria solo tendría acceso al puntero alineado de 16 bytes 'cocinado'.
Michael Burr el
1
Para una solución general, tienes razón. Sin embargo, la plantilla de código en la pregunta muestra claramente ambos.
Jonathan Leffler
1
Claro, y en una buena entrevista lo que sucede es que usted da su respuesta, entonces si el entrevistador quiere ver mi respuesta, cambian la pregunta.
Steve Jessop
1
Me opongo a usar ASSERT(mem);para verificar los resultados de la asignación; assertes para detectar errores de programación y no falta de recursos en tiempo de ejecución.
hlovdal
44
El uso de binario & con a char *y a size_tgenerará un error. Tendrías que usar algo como uintptr_t.
Marko
20

Aquí hay un enfoque alternativo para la parte 'redondear'. No es la solución codificada más brillante, pero hace el trabajo, y este tipo de sintaxis es un poco más fácil de recordar (además, funcionaría para valores de alineación que no son una potencia de 2). El uintptr_telenco fue necesario para apaciguar al compilador; La aritmética de puntero no es muy aficionada a la división o multiplicación.

void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);
Andrés
fuente
2
En general, donde tiene 'unsigned long long', también tiene uintptr_t que se define explícitamente como lo suficientemente grande como para contener un puntero de datos (void *). Pero su solución tiene méritos si, por alguna razón, necesita una alineación que no era una potencia de 2. Poco probable, pero posible.
Jonathan Leffler
@Andrew: El voto a favor para este tipo de sintaxis es un poco más fácil de recordar (además, funcionaría para valores de alineación que no son una potencia de 2) .
legends2k
19

Desafortunadamente, en C99 parece bastante difícil garantizar la alineación de cualquier tipo de manera que sea portátil en cualquier implementación de C que se ajuste a C99. ¿Por qué? Porque no se garantiza que un puntero sea la "dirección de byte" que uno podría imaginar con un modelo de memoria plana. Tampoco es la representación de garantizada uintptr_t , que de todos modos es un tipo opcional.

Podríamos conocer algunas implementaciones que usan una representación para void * (y por definición, también char * ), que es una dirección de byte simple, pero para C99 es opaca para nosotros, los programadores. Una implementación podría representar un puntero por un conjunto { segmento , desplazamiento } donde el desplazamiento podría tener una alineación de quién sabe qué "en realidad". Por qué, un puntero podría incluso ser alguna forma de valor de búsqueda de tabla hash, o incluso un valor de búsqueda de lista vinculada. Podría codificar información de límites.

En un borrador reciente de C1X para un Estándar C, vemos la palabra clave _Alignas . Eso podría ayudar un poco.

La única garantía que nos brinda C99 es que las funciones de asignación de memoria devolverán un puntero adecuado para la asignación a un puntero que apunta a cualquier tipo de objeto. Como no podemos especificar la alineación de los objetos, no podemos implementar nuestras propias funciones de asignación con la responsabilidad de la alineación de una manera bien definida y portátil.

Sería bueno estar equivocado sobre este reclamo.

Shao
fuente
C11 tiene aligned_alloc(). (C ++ 11/14 / 1z todavía no lo tiene). _Alignas()y C ++ alignas()no hacen nada para la asignación dinámica, solo para almacenamiento automático y estático (o diseño de estructura).
Peter Cordes
15

En el frente de relleno de 16 contra 15 bytes, el número real que necesita agregar para obtener una alineación de N es max (0, NM) donde M es la alineación natural del asignador de memoria (y ambas son potencias de 2).

Como la alineación mínima de memoria de cualquier asignador es de 1 byte, 15 = max (0,16-1) es una respuesta conservadora. Sin embargo, si sabe que su asignador de memoria le dará direcciones int alineadas de 32 bits (lo cual es bastante común), podría haber usado 12 como pad.

Esto no es importante para este ejemplo, pero podría ser importante en un sistema embebido con 12K de RAM donde cada int guardado cuenta.

La mejor manera de implementarlo si realmente va a intentar guardar cada byte posible es como una macro para que pueda alimentar su alineación de memoria nativa. Una vez más, esto probablemente solo sea útil para sistemas integrados donde necesita guardar cada byte.

En el ejemplo a continuación, en la mayoría de los sistemas, el valor 1 está bien MEMORY_ALLOCATOR_NATIVE_ALIGNMENT, sin embargo, para nuestro sistema embebido teórico con asignaciones alineadas de 32 bits, lo siguiente podría ahorrar un poco de memoria preciosa:

#define MEMORY_ALLOCATOR_NATIVE_ALIGNMENT    4
#define ALIGN_PAD2(N,M) (((N)>(M)) ? ((N)-(M)) : 0)
#define ALIGN_PAD(N) ALIGN_PAD2((N), MEMORY_ALLOCATOR_NATIVE_ALIGNMENT)
Adisak
fuente
8

¿Quizás habrían quedado satisfechos con un conocimiento de memalign ? Y como Jonathan Leffler señala, hay dos funciones preferibles más nuevas para conocer.

Vaya, Florin me ganó. Sin embargo, si lee la página de manual a la que me vinculé, lo más probable es que comprenda el ejemplo proporcionado por un póster anterior.

Don Wakefield
fuente
1
Tenga en cuenta que el (febrero de 2016) la versión actual de la página referenciada dice "La memalignfunción es obsoleta y aligned_allocni posix_memalignse debe utilizar en su lugar". No sé lo que dijo en octubre de 2008, pero probablemente no lo mencionó, aligned_alloc()ya que se agregó a C11.
Jonathan Leffler
5

Hacemos este tipo de cosas todo el tiempo para Accelerate.framework, una biblioteca OS X / iOS muy vectorizada, donde tenemos que prestar atención a la alineación todo el tiempo. Hay bastantes opciones, una o dos de las cuales no vi mencionadas anteriormente.

El método más rápido para una matriz pequeña como esta es simplemente pegarlo en la pila. Con GCC / clang:

 void my_func( void )
 {
     uint8_t array[1024] __attribute__ ((aligned(16)));
     ...
 }

No se requiere gratis (). Esto suele ser dos instrucciones: restar 1024 del puntero de la pila, luego Y el puntero de la pila con -alineación. Presumiblemente, el solicitante necesitaba los datos en el montón porque su vida útil de la matriz excedía la pila o la recursión está en funcionamiento o el espacio de la pila es muy importante.

En OS X / iOS todas las llamadas a malloc / calloc / etc. siempre están alineados a 16 bytes. Si necesita 32 bytes alineados para AVX, por ejemplo, puede usar posix_memalign:

void *buf = NULL;
int err = posix_memalign( &buf, 32 /*alignment*/, 1024 /*size*/);
if( err )
   RunInCirclesWaivingArmsWildly();
...
free(buf);

Algunas personas han mencionado la interfaz de C ++ que funciona de manera similar.

No debe olvidarse que las páginas están alineadas a grandes potencias de dos, por lo que los búferes alineados a la página también están alineados a 16 bytes. Por lo tanto, mmap () y valloc () y otras interfaces similares también son opciones. mmap () tiene la ventaja de que el búfer se puede asignar preinicializado con algo distinto de cero, si lo desea. Dado que estos tienen un tamaño de página alineado, no obtendrá la asignación mínima de estos, y es probable que esté sujeto a un error de VM la primera vez que lo toque.

Cursi: activar guardia malloc o similar. Los búferes que tienen un tamaño de n * 16 bytes, como este, estarán alineados con n * 16 bytes, porque VM se usa para capturar desbordamientos y sus límites están en los límites de la página.

Algunas funciones de Accelerate.framework incorporan un búfer temporal provisto por el usuario para usarlo como espacio reutilizable. Aquí tenemos que suponer que el búfer que nos ha pasado está muy desalineado y el usuario está tratando de hacer nuestra vida difícil por despecho. (Nuestros casos de prueba pegan una página de protección justo antes y después del búfer temporal para subrayar el despecho). Aquí, devolvemos el tamaño mínimo que necesitamos para garantizar un segmento alineado de 16 bytes en algún lugar, y luego alineamos manualmente el búfer después. Este tamaño es deseado_size + alineación - 1. Entonces, en este caso eso es 1024 + 16 - 1 = 1039 bytes. Luego alinear así:

#include <stdint.h>
void My_func( uint8_t *tempBuf, ... )
{
    uint8_t *alignedBuf = (uint8_t*) 
                          (((uintptr_t) tempBuf + ((uintptr_t)alignment-1)) 
                                        & -((uintptr_t) alignment));
    ...
}

Agregar alineación-1 moverá el puntero más allá de la primera dirección alineada y luego AND con -alineación (por ejemplo, 0xfff ... ff0 para alineación = 16) lo regresa a la dirección alineada.

Como se describe en otras publicaciones, en otros sistemas operativos sin garantías de alineación de 16 bytes, puede llamar a malloc con el tamaño más grande, dejar de lado el puntero de forma gratuita () más tarde, luego alinear como se describe inmediatamente antes y usar el puntero alineado, tanto como descrito para nuestro caso de buffer temporal.

En cuanto a alineado_memset, esto es bastante tonto. Solo tiene que realizar un bucle de hasta 15 bytes para llegar a una dirección alineada, y luego continuar con las tiendas alineadas con un posible código de limpieza al final. Incluso puede hacer los bits de limpieza en el código vectorial, ya sea como almacenes no alineados que se superponen a la región alineada (siempre que la longitud sea al menos la longitud de un vector) o usando algo como movmaskdqu. Alguien solo está siendo vago. Sin embargo, probablemente sea una pregunta de entrevista razonable si el entrevistador quiere saber si se siente cómodo con stdint.h, operadores bit a bit y fundamentos de memoria, por lo que se puede perdonar el ejemplo artificial.

Ian Ollmann
fuente
5

Me sorprende que nadie haya votado por la respuesta de Shao de que, según tengo entendido, es imposible hacer lo que se pide en el estándar C99, ya que convertir un puntero a un tipo integral formalmente es un comportamiento indefinido. (Aparte del estándar que permite la conversión de <-> , pero el estándar no parece permitir ninguna manipulación del valor y luego volverlo a convertir).uintptr_tvoid*uintptr_t

Lutorm
fuente
No es necesario que exista un tipo uintptr_t, o que sus bits tengan alguna relación con los bits en el puntero subyacente. Si uno fuera a sobreasignar almacenamiento, almacene el puntero como unsigned char* myptr; y luego calcule `mptr + = (16- (uintptr_t) my_ptr) & 0x0F, el comportamiento se definiría en todas las implementaciones que definan my_ptr, pero si el puntero resultante estaría alineado dependería de la asignación entre uintptr_t bits y direcciones.
supercat
3

El uso de memalign, Aligned-Memory-Blocks podría ser una buena solución para el problema.

neurona
fuente
Tenga en cuenta que el (febrero de 2016) la versión actual de la página referenciada dice "La memalignfunción es obsoleta y aligned_allocni posix_memalignse debe utilizar en su lugar". No sé lo que dijo en octubre de 2010.
Jonathan Leffler
3

Lo primero que me vino a la cabeza al leer esta pregunta fue definir una estructura alineada, instanciarla y luego señalarla.

¿Hay alguna razón fundamental que me falta ya que nadie más sugirió esto?

Como nota al margen, dado que utilicé una matriz de caracteres (suponiendo que el carácter del sistema es de 8 bits (es decir, 1 byte)), no veo la necesidad de __attribute__((packed)) necesariamente (corrígeme si me equivoco), pero lo puse de cualquier manera.

Esto funciona en dos sistemas en los que lo probé, pero es posible que exista una optimización del compilador que desconozco si me da falsos positivos con respecto a la eficacia del código. Solía gcc 4.9.2en OSX y gcc 5.2.1en Ubuntu.

#include <stdio.h>
#include <stdlib.h>

int main ()
{

   void *mem;

   void *ptr;

   // answer a) here
   struct __attribute__((packed)) s_CozyMem {
       char acSpace[16];
   };

   mem = malloc(sizeof(struct s_CozyMem));
   ptr = mem;

   // memset_16aligned(ptr, 0, 1024);

   // Check if it's aligned
   if(((unsigned long)ptr & 15) == 0) printf("Aligned to 16 bytes.\n");
   else printf("Rubbish.\n");

   // answer b) here
   free(mem);

   return 1;
}
Janus
fuente
1

MacOS X específico:

  1. Todos los punteros asignados con malloc están alineados a 16 bytes.
  2. C11 es compatible, por lo que puede llamar a alineado_malloc (16, tamaño).

  3. MacOS X elige el código que está optimizado para procesadores individuales en el momento del arranque para memset, memcpy y memmove y ese código usa trucos de los que nunca has oído hablar para que sea más rápido. 99% de probabilidad de que memset se ejecute más rápido que cualquier memset escrito a mano16, lo que hace que toda la pregunta no tenga sentido.

Si desea una solución 100% portátil, antes de C11 no hay ninguna. Porque no hay una forma portátil de probar la alineación de un puntero. Si no tiene que ser 100% portátil, puede usar

char* p = malloc (size + 15);
p += (- (unsigned int) p) % 16;

Esto supone que la alineación de un puntero se almacena en los bits más bajos al convertir un puntero a int sin signo. La conversión a unsigned int pierde información y su implementación está definida, pero eso no importa porque no convertimos el resultado a un puntero.

La parte horrible es, por supuesto, que el puntero original debe guardarse en algún lugar para llamar a free () con él. Así que, en general, dudaría mucho de la sabiduría de este diseño.

Chris
fuente
1
¿Dónde te encuentras aligned_mallocen OS X? Estoy usando Xcode 6.1 y no está definido en ninguna parte del SDK de iOS, ni está declarado en ninguna parte /usr/include/*.
Todd Lehman
Lo mismo para XCode 7.2 en El Capitan (Mac OS X 10.11.3). La función C11 es, en cualquier caso aligned_alloc(), pero tampoco se declara. De GCC 5.3.0, recibo los mensajes interesantes alig.c:7:15: error: incompatible implicit declaration of built-in function ‘aligned_alloc’ [-Werror]y alig.c:7:15: note: include ‘<stdlib.h>’ or provide a declaration of ‘aligned_alloc’. El código sí incluyó <stdlib.h>, pero -std=c11ni -std=gnu11cambió los mensajes de error.
Jonathan Leffler
0

También puede agregar unos 16 bytes y luego empujar el ptr original a 16 bits alineados agregando el (16-mod) como debajo del puntero:

main(){
void *mem1 = malloc(1024+16);
void *mem = ((char*)mem1)+1; // force misalign ( my computer always aligns)
printf ( " ptr = %p \n ", mem );
void *ptr = ((long)mem+16) & ~ 0x0F;
printf ( " aligned ptr = %p \n ", ptr );

printf (" ptr after adding diff mod %p (same as above ) ", (long)mem1 + (16 -((long)mem1%16)) );


free(mem1);
}
resultados
fuente
0

Si existen restricciones, no puede desperdiciar un solo byte, entonces esta solución funciona: Nota: Hay un caso en el que esto puede ejecutarse infinitamente: D

   void *mem;  
   void *ptr;
try:
   mem =  malloc(1024);  
   if (mem % 16 != 0) {  
       free(mem);  
       goto try;
   }  
   ptr = mem;  
   memset_16aligned(ptr, 0, 1024);
Pensamiento profundo
fuente
Existe una muy buena posibilidad de que si asigna y luego libera un bloque de N bytes y luego solicita otro bloque de N bytes, el bloque original se devolverá nuevamente. Por lo tanto, es muy probable un bucle infinito si la primera asignación no cumple con el requisito de alineación. Por supuesto, eso evita desperdiciar un solo byte a costa de desperdiciar muchos ciclos de CPU.
Jonathan Leffler
¿Está seguro de que el %operador está definido de void*manera significativa?
Ajay Brahmakshatriya
0

Para la solución, utilicé un concepto de relleno que alinea la memoria y no desperdicia la memoria de un solo byte.

Si existen restricciones, no puede desperdiciar un solo byte. Todos los punteros asignados con malloc están alineados a 16 bytes.

C11 es compatible, por lo que puede llamar aligned_alloc (16, size).

void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
usuario3415603
fuente
1
En muchos sistemas de 64 bits, el puntero devuelto por sí malloc()está alineado en un límite de 16 bytes, pero nada en ningún estándar garantiza que, simplemente estará suficientemente bien alineado para cualquier uso, y en muchos sistemas de 32 bits que se alinean en un El límite de 8 bytes es suficiente, y para algunos, un límite de 4 bytes es suficiente.
Jonathan Leffler
0
size =1024;
alignment = 16;
aligned_size = size +(alignment -(size %  alignment));
mem = malloc(aligned_size);
memset_16aligned(mem, 0, 1024);
free(mem);

Espero que esta sea la implementación más simple, hágame saber sus comentarios.

stackguy
fuente
-3
long add;   
mem = (void*)malloc(1024 +15);
add = (long)mem;
add = add - (add % 16);//align to 16 byte boundary
ptr = (whatever*)(add);
Ramana
fuente
Creo que hay un problema con esto porque su complemento apuntará a una ubicación que no está mal asignada: no estoy seguro de cómo funcionó esto en la suya.
resultados el
@Sam Debería ser add += 16 - (add % 16). (2 - (2 % 16)) == 0.
SS Anne