Como alocar memória alinhada apenas usando a biblioteca padrão?

422

Acabei de terminar um teste como parte de uma entrevista de emprego, e uma pergunta me surpreendeu, mesmo usando o Google como referência. Gostaria de ver o que a equipe do StackOverflow pode fazer com isso:

A memset_16alignedfunção requer que um ponteiro alinhado de 16 bytes seja passado para ele ou ele trava.

a) Como você alocaria 1024 bytes de memória e o alinharia a um limite de 16 bytes?
b) Libere a memória após a memset_16alignedexecução.

{    
   void *mem;
   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here    
}
JimDaniel
fonte
89
hmmm ... para a viabilidade código de longo prazo, como sobre "Fire Quem escreveu memset_16aligned e corrigi-lo ou substituí-lo para que ele não tem uma condição de contorno peculiar"
Steven A. Lowe
29
Certamente uma pergunta válida a ser feita - "por que o alinhamento peculiar da memória". Mas pode haver boas razões para isso - nesse caso, pode ser que o memset_16aligned () possa usar números inteiros de 128 bits e isso é mais fácil se a memória estiver alinhada. Etc.
Jonathan Leffler
5
Quem escreveu o memset pode usar o alinhamento interno de 16 bytes para limpar o loop interno e um pequeno prólogo / epilog de dados para limpar as extremidades não alinhadas. Isso seria muito mais fácil do que fazer os codificadores manipularem indicadores adicionais de memória.
Adisak
8
Por que alguém iria querer dados alinhados com um limite de 16 bytes? Provavelmente carregá-lo em registradores SSE de 128 bits. Acredito que as mais recentes () movs não alinhados (por exemplo, movupd, lddqu) são mais lentas, ou talvez que se dirigem processadores sem SSE2 / 3
11
O alinhamento de endereços leva ao uso otimizado do cache, bem como a uma maior largura de banda entre os diferentes níveis de cache e RAM (para as cargas de trabalho mais comuns). Veja aqui stackoverflow.com/questions/381244/purpose-of-memory-alignment
Deepthought

Respostas:

587

Resposta original

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

Resposta fixa

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

Explicação conforme solicitado

O primeiro passo é alocar espaço livre suficiente, apenas por precaução. Como a memória deve estar alinhada por 16 bytes (o que significa que o endereço de byte inicial precisa ser um múltiplo de 16), adicionar 16 bytes extras garante que temos espaço suficiente. Em algum lugar nos primeiros 16 bytes, há um ponteiro alinhado de 16 bytes. (Note que malloc()deve retornar um ponteiro que está suficientemente bem alinhado para qualquer . Propósito No entanto, o significado de 'qualquer' é principalmente para coisas como tipos básicos - long, double, long double, long long., E ponteiros para objetos e ponteiros para funções Quando você está fazendo coisas mais especializadas, como brincar com sistemas gráficos, eles podem precisar de um alinhamento mais rigoroso do que o resto do sistema - daí perguntas e respostas como essa.)

O próximo passo é converter o ponteiro nulo em um ponteiro de caracteres; Não obstante, o GCC, você não deve fazer aritmética de ponteiro em ponteiros nulos (e o GCC tem opções de aviso para informar quando você o abusar). Em seguida, adicione 16 ao ponteiro de início. Suponha que malloc()você retornou um ponteiro impossivelmente mal alinhado: 0x800001. A adição de 16 fornece 0x800011. Agora, quero arredondar para o limite de 16 bytes - então, quero redefinir os últimos 4 bits para 0. 0x0F tem os últimos 4 bits definidos como um; portanto, ~0x0Fpossui todos os bits definidos como um, exceto os quatro últimos. E isso com 0x800011 fornece 0x800010. Você pode iterar sobre os outros deslocamentos e ver que a mesma aritmética funciona.

O último passo, free()é fácil: você sempre, e só, o retorno para free()um valor que um dos malloc(), calloc()ou realloc()devolvido a você - qualquer outra coisa é um desastre. Você forneceu corretamente mempara manter esse valor - obrigado. O livre lança.

Por fim, se você souber sobre os componentes internos do mallocpacote do seu sistema , poderá adivinhar que ele pode retornar dados alinhados em 16 bytes (ou alinhados em 8 bytes). Se estivesse alinhado por 16 bytes, não seria necessário alterar os valores. No entanto, isso é desonesto e não portátil - outros mallocpacotes têm alinhamentos mínimos diferentes e, portanto, assumindo uma coisa quando faz algo diferente levaria a despejos de núcleo. Dentro de limites amplos, esta solução é portátil.

Outra pessoa mencionou posix_memalign()como outra maneira de obter a memória alinhada; que não está disponível em todos os lugares, mas pode ser implementado com base nisso. Observe que era conveniente que o alinhamento fosse uma potência de 2; outros alinhamentos são mais confusos.

Mais um comentário - esse código não verifica se a alocação foi bem-sucedida.

Alteração

O Programador do Windows apontou que você não pode fazer operações de máscara de bits em ponteiros e, de fato, o GCC (3.4.6 e 4.3.1 testado) se queixa assim. Portanto, segue uma versão alterada do código básico - convertido em um programa principal. Também tomei a liberdade de adicionar apenas 15 em vez de 16, como foi apontado. Estou usando uintptr_tdesde que o C99 existe há tempo suficiente para ser acessível na maioria das plataformas. Se não fosse pelo uso de PRIXPTRnas printf()instruções, seria suficiente em #include <stdint.h>vez de usar #include <inttypes.h>. [Esse código inclui a correção apontada pelo CR , que estava reiterando um argumento feito por Bill K há vários anos, que eu consegui ignorar até agora.]

#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);
}

E aqui está uma versão marginalmente mais generalizada, que funcionará para tamanhos com uma potência 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 converter test_mask()em uma função de alocação de uso geral, o valor de retorno único do alocador teria que codificar o endereço de liberação, como várias pessoas indicaram em suas respostas.

Problemas com os entrevistadores

Uri comentou: Talvez eu esteja tendo [um] problema de compreensão de leitura esta manhã, mas se a pergunta da entrevista disser especificamente: "Como você alocaria 1024 bytes de memória" e você claramente alocará mais do que isso. Isso não seria uma falha automática do entrevistador?

Minha resposta não se encaixa em um comentário de 300 caracteres ...

Depende, suponho. Acho que a maioria das pessoas (inclusive eu) entendeu a pergunta como "como você alocaria um espaço no qual 1024 bytes de dados podem ser armazenados e onde o endereço base é um múltiplo de 16 bytes". Se o entrevistador realmente quis dizer como você pode alocar 1024 bytes (apenas) e ter 16 bytes alinhados, as opções são mais limitadas.

  • Claramente, uma possibilidade é alocar 1024 bytes e atribuir a esse endereço o 'tratamento de alinhamento'; o problema dessa abordagem é que o espaço disponível real não é determinado adequadamente (o espaço utilizável está entre 1008 e 1024 bytes, mas não havia um mecanismo disponível para especificar qual tamanho), o que o torna menos útil.
  • Outra possibilidade é que você deve escrever um alocador de memória completo e garantir que o bloco de 1024 bytes retornado esteja alinhado adequadamente. Se for esse o caso, você provavelmente acaba executando uma operação bastante semelhante à que a solução proposta fez, mas a oculta dentro do alocador.

No entanto, se o entrevistador esperava alguma dessas respostas, eu esperaria que eles reconhecessem que esta solução responde a uma pergunta intimamente relacionada e, em seguida, reformulassem a pergunta para apontar a conversa na direção correta. (Além disso, se o entrevistador ficou realmente desleixado, então eu não gostaria do emprego; se a resposta a um requisito insuficientemente preciso é abatida em chamas sem correção, então o entrevistador não é alguém para quem é seguro trabalhar.)

O mundo segue em frente

O título da pergunta mudou recentemente. Foi resolver o alinhamento de memória na pergunta da entrevista C que me surpreendeu . O título revisado ( Como alocar memória alinhada usando apenas a biblioteca padrão? ) Exige uma resposta ligeiramente revisada - este adendo fornece.

Função adicionada C11 (ISO / IEC 9899: 2011) aligned_alloc() :

7.22.3.1 aligned_alloc função

Sinopse

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

Descrição
A aligned_allocfunção aloca espaço para um objeto cujo alinhamento é especificado por alignment, cujo tamanho é especificado por sizee cujo valor é indeterminado. O valor de alignmentdeve ser um alinhamento válido suportado pela implementação e pelo valor desize deve ser um múltiplo integral de alignment.

Retornos
A aligned_allocfunção retorna um ponteiro nulo ou um ponteiro para o espaço alocado.

E o POSIX define posix_memalign():

#include <stdlib.h>

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

DESCRIÇÃO

A posix_memalign()função deve alocar sizebytes alinhados em um limite especificado por alignmente deve retornar um ponteiro para a memória alocada em memptr. O valor de alignmentdeve ser uma potência de dois múltiplos de sizeof(void *).

Após a conclusão bem-sucedida, o valor apontado por memptrdeve ser um múltiplo de alignment.

Se o tamanho do espaço solicitado for 0, o comportamento será definido pela implementação; o valor retornado memptrdeve ser um ponteiro nulo ou um ponteiro exclusivo.

A free()função deve desalocar a memória que foi alocada anteriormente por posix_memalign().

VALOR DE RETORNO

Após a conclusão bem-sucedida, posix_memalign()retornará zero; caso contrário, um número de erro será retornado para indicar o erro.

Um ou ambos podem ser usados ​​para responder à pergunta agora, mas apenas a função POSIX era uma opção quando a pergunta foi originalmente respondida.

Nos bastidores, a nova função de memória alinhada faz o mesmo trabalho descrito na pergunta, exceto que eles têm a capacidade de forçar o alinhamento com mais facilidade e acompanhar o início da memória alinhada internamente, para que o código não funcione. tem que lidar com especialmente - apenas libera a memória retornada pela função de alocação que foi usada.

Jonathan Leffler
fonte
13
E estou enferrujado com C ++, mas realmente não confio que ~ 0x0F seja expandido corretamente para o tamanho do ponteiro. Caso contrário, o inferno se abrirá porque você mascarará os bits mais significativos do ponteiro. Eu posso estar errado sobre isso.
Bill K
66
O BTW '+15' funciona tão bem quanto o '+16' ... embora não haja impacto prático nesta situação.
Menkboy 22/10/08
15
Os comentários '+ 15' de Menkboy e Greg estão corretos, mas malloc () quase certamente aumentaria isso para 16, de qualquer maneira. Usar +16 é marginalmente mais fácil de explicar. A solução generalizada é complicada, mas factível.
Jonathan Leffler
6
@ Aerovistae: Essa é uma pergunta um pouco complicada, e depende principalmente de como você faz um número arbitrário (na verdade, o endereço retornado pelo alocador de memória) corresponde a um determinado requisito (múltiplo de 16). Se lhe dissessem para arredondar 53 para o múltiplo mais próximo de 16, como você faria isso? O processo não é muito diferente para endereços; é apenas que os números com os quais você normalmente lida são maiores. Não se esqueça, as perguntas da entrevista são solicitadas para descobrir como você pensa, não para saber se você sabe a resposta.
Jonathan Leffler
3
@akristmann: O código original está correto se você tiver o <inttypes.h>C99 disponível (pelo menos para a string de formato - sem dúvida, os valores devem ser passados ​​com um elenco :) (uintptr_t)mem, (uintptr_t)ptr. A seqüência de formato depende da concatenação de seqüência de caracteres e a macro PRIXPTR é o printf()especificador de tamanho e tipo correto para saída hexadecimal para um uintptr_tvalor. A alternativa é usar, %pmas a saída disso varia de acordo com a plataforma (algumas adicionam uma inicial 0x, a maioria não) e geralmente é escrita com dígitos hexadecimais em letras minúsculas, o que eu não gosto; o que eu escrevi é uniforme entre plataformas.
Jonathan Leffler
58

Três respostas ligeiramente diferentes, dependendo de como você olha para a pergunta:

1) Bom o suficiente para a pergunta exata feita é a solução de Jonathan Leffler, exceto que para arredondar até 16 alinhados, você precisa apenas de 15 bytes extras, e não de 16.

UMA:

/* 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;

B:

free(mem);

2) Para uma função de alocação de memória mais genérica, o chamador não deseja controlar dois ponteiros (um para usar e outro para liberar). Portanto, você armazena um ponteiro no buffer 'real' abaixo do buffer alinhado.

UMA:

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;

B:

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

Observe que, ao contrário de (1), onde apenas 15 bytes foram adicionados ao mem, esse código pode realmente reduzir o alinhamento se a sua implementação garantir alinhamento de 32 bytes do malloc (improvável, mas, em teoria, uma implementação em C pode ter 32 bytes) tipo alinhado). Isso não importa se tudo o que você faz é chamar memset_16aligned, mas se você usar a memória para uma estrutura, isso poderá importar.

Não sei ao certo qual é uma boa solução para isso (exceto avisar o usuário que o buffer retornado não é necessariamente adequado para estruturas arbitrárias), pois não há como determinar programaticamente qual é a garantia de alinhamento específica da implementação. Acho que na inicialização você pode alocar dois ou mais buffers de 1 byte e supor que o pior alinhamento que você vê é o alinhamento garantido. Se você está errado, você perde memória. Qualquer pessoa com uma ideia melhor, diga-o ...

[ Adicionado : O truque 'padrão' é criar uma união de 'tipos provavelmente alinhados ao máximo' para determinar o alinhamento necessário. É provável que os tipos alinhados ao máximo sejam (em C99) ' long long', ' long double', ' void *' ou ' void (*)(void)'; se você incluir <stdint.h>, presumivelmente poderia usar ' intmax_t' no lugar de long long(e, nas máquinas Power 6 (AIX), intmax_tforneceria um tipo inteiro de 128 bits). Os requisitos de alinhamento para essa união podem ser determinados incorporando-a em uma estrutura com um único caractere seguido pela união:

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;

Você usaria o maior alinhamento solicitado (no exemplo, 16) e o alignvalor calculado acima.

No Solaris 10 (64 bits), parece que o alinhamento básico para o resultado malloc()é um múltiplo de 32 bytes.
]

Na prática, os alocadores alinhados geralmente adotam um parâmetro para o alinhamento, em vez de serem conectados. Portanto, o usuário transmitirá o tamanho da estrutura com a qual se preocupa (ou a menor potência de 2 maior ou igual a isso) e tudo ficará bem.

3) Use o que sua plataforma fornece: posix_memalignpara POSIX, _aligned_mallocno Windows.

4) Se você usa C11, a opção mais limpa - portátil e concisa - é usar a função de biblioteca padrão aligned_allocque foi introduzida nesta versão da especificação de idioma.

Steve Jessop
fonte
1
Eu concordo - acho que o objetivo da pergunta é que o código que libera o bloco de memória tenha acesso apenas ao ponteiro alinhado de 16 bytes 'cozido'.
Michael Burr
1
Para uma solução geral - você está certo. No entanto, o modelo de código na pergunta mostra claramente os dois.
23616 Jonathan Leffler
1
Claro, e em uma boa entrevista o que acontece é que você dá sua resposta; se o entrevistador quiser ver minha resposta, eles mudam a pergunta.
Steve Jessop
1
Eu me oponho a usar ASSERT(mem);para verificar os resultados da alocação; asserté para detectar erros de programação e não falta de recursos em tempo de execução.
hlovdal
4
Usando binário e com um char *e size_tresultará em um erro. Você teria que usar algo parecido uintptr_t.
21414 Marko
20

Aqui está uma abordagem alternativa para a parte 'arredondar'. Não é a solução mais brilhantemente codificada, mas realiza o trabalho, e esse tipo de sintaxe é um pouco mais fácil de lembrar (além de funcionar com valores de alinhamento que não são 2). O uintptr_telenco era necessário para apaziguar o compilador; A aritmética dos ponteiros não gosta muito de divisão ou multiplicação.

void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);
An̲̳̳drew
fonte
2
Em geral, onde você 'não assinou por muito tempo', também possui o uintptr_t, que é explicitamente definido como grande o suficiente para armazenar um ponteiro de dados (void *). Mas sua solução realmente tem méritos se, por algum motivo, você precisar de um alinhamento que não seja uma potência de 2. Improvável, mas possível.
Jonathan Leffler
@ Andrew: Upvoted para este tipo de sintaxe é um pouco mais fácil de lembrar (além de trabalhar para valores de alinhamento que não são uma potência de 2) .
legends2k
19

Infelizmente, no C99, parece bastante difícil garantir o alinhamento de qualquer tipo que seja portátil em qualquer implementação C em conformidade com o C99. Por quê? Como não é garantido que um ponteiro seja o "endereço de bytes" que se pode imaginar com um modelo de memória plana. Tampouco é garantida a representação de uintptr_t , que de qualquer forma é um tipo opcional.

Podemos conhecer algumas implementações que usam uma representação para void * (e, por definição, também char * ), que é um endereço de bytes simples, mas, por C99, é opaco para nós, os programadores. Uma implementação pode representar um ponteiro por um conjunto { segmento , deslocamento } em que o deslocamento pode ter um alinhamento de quem sabe o que "na realidade". Por que, um ponteiro pode até ser uma forma de valor de pesquisa de tabela de hash ou mesmo um valor de pesquisa de lista vinculada. Pode codificar informações de limites.

Em um rascunho C1X recente para um padrão C, vemos a palavra-chave _Alignas . Isso pode ajudar um pouco.

A única garantia que C99 nos dá é que as funções de alocação de memória retornem um ponteiro adequado para atribuição a um ponteiro apontando para qualquer tipo de objeto. Como não podemos especificar o alinhamento dos objetos, não podemos implementar nossas próprias funções de alocação com responsabilidade pelo alinhamento de uma maneira bem definida e portátil.

Seria bom estar errado sobre essa afirmação.

Shao
fonte
C11 tem aligned_alloc() . (C ++ 11/14 / 1z ainda não o possui). _Alignas()e C ++ alignas()não fazem nada para alocação dinâmica, apenas para armazenamento automático e estático (ou layout de estrutura).
Peter Cordes
15

Na frente de preenchimento de 16 x 15 bytes, o número real que você precisa adicionar para obter um alinhamento de N é máximo (0, NM), em que M é o alinhamento natural do alocador de memória (e ambos são potências de 2).

Como o alinhamento mínimo da memória de qualquer alocador é de 1 byte, 15 = max (0,16-1) é uma resposta conservadora. No entanto, se você souber que o seu alocador de memória fornecerá endereços alinhados int de 32 bits (o que é bastante comum), você poderia ter usado 12 como bloco.

Isso não é importante para este exemplo, mas pode ser importante em um sistema incorporado com 12K de RAM, onde cada int salvo é importante.

A melhor maneira de implementá-lo se você realmente tentar salvar todos os bytes possíveis é como uma macro, para que você possa alimentar seu alinhamento de memória nativa. Novamente, isso provavelmente é útil apenas para sistemas embarcados em que você precisa salvar todos os bytes.

No exemplo abaixo, na maioria dos sistemas, o valor 1 é MEMORY_ALLOCATOR_NATIVE_ALIGNMENTadequado, no entanto, para o nosso sistema teórico incorporado com alocações alinhadas de 32 bits, o seguinte pode economizar um pouquinho de memória 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
fonte
8

Talvez eles teria sido satisfeitos com um conhecimento de memalign ? E, como Jonathan Leffler aponta, existem duas novas funções preferíveis para conhecer.

Opa, florin me venceu. No entanto, se você ler a página de manual à qual vinculei, provavelmente entenderá o exemplo fornecido por um pôster anterior.

Don Wakefield
fonte
1
Observe que a versão atual (fevereiro de 2016) da página referenciada diz "A memalignfunção está obsoleta e aligned_allocou posix_memaligndeve ser usada". Não sei o que dizia em outubro de 2008 - mas provavelmente não mencionou, aligned_alloc()pois foi adicionado ao C11.
Jonathan Leffler
5

Fazemos esse tipo de coisa o tempo todo para o Accelerate.framework, uma biblioteca OS X / iOS fortemente vetorizada, onde precisamos prestar atenção ao alinhamento o tempo todo. Existem algumas opções, uma ou duas das quais não vi mencionadas acima.

O método mais rápido para uma matriz pequena como essa é colocá-lo na pilha. Com GCC / clang:

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

Não é necessário livre (). Geralmente, são duas instruções: subtraia 1024 do ponteiro da pilha e AND o ponteiro da pilha com -alignment. Presumivelmente, o solicitante precisava dos dados no heap porque sua vida útil da matriz excedeu a pilha ou a recursão está no trabalho ou o espaço na pilha é muito importante.

No OS X / iOS, todas as chamadas para malloc / calloc / etc. estão sempre alinhados por 16 bytes. Se você precisou de 32 bytes alinhados para o AVX, por exemplo, pode usar posix_memalign:

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

Algumas pessoas mencionaram a interface C ++ que funciona da mesma forma.

Não se deve esquecer que as páginas estão alinhadas com grandes potências de dois, portanto, os buffers alinhados à página também são alinhados em 16 bytes. Assim, mmap () e valloc () e outras interfaces semelhantes também são opções. mmap () tem a vantagem de que o buffer pode ser alocado pré-inicializado com algo diferente de zero, se você desejar. Como estes têm tamanho alinhado à página, você não receberá a alocação mínima deles e provavelmente estará sujeito a uma falha de VM na primeira vez em que o tocar.

Extravagante: ative o malloc ou similar. Buffers com tamanho n * 16 bytes como este serão n * 16 bytes alinhados, porque a VM é usada para capturar excedentes e seus limites estão nos limites da página.

Algumas funções do Accelerate.framework recebem um buffer temporário fornecido pelo usuário para uso como espaço temporário. Aqui, devemos assumir que o buffer que nos foi passado está desalinhado e o usuário está tentando ativamente dificultar nossa vida. (Nossos casos de teste mantêm uma página de proteção logo antes e depois do buffer temporário para sublinhar o despeito.) Aqui, retornamos o tamanho mínimo necessário para garantir um segmento alinhado de 16 bytes em algum lugar nele e, em seguida, alinhamos manualmente o buffer posteriormente. Esse tamanho é desejado_size + alinhamento - 1. Portanto, neste caso, são 1024 + 16 - 1 = 1039 bytes. Em seguida, alinhe da seguinte forma:

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

Adicionar o alinhamento-1 moverá o ponteiro além do primeiro endereço alinhado e ANDing com -alignment (por exemplo, 0xfff ... ff0 para o alinhamento = 16) o levará de volta ao endereço alinhado.

Conforme descrito em outras postagens, em outros sistemas operacionais sem garantias de alinhamento de 16 bytes, você pode chamar malloc com o tamanho maior, deixar o ponteiro de graça () posteriormente () e depois alinhar conforme descrito imediatamente acima e usar o ponteiro alinhado, tanto quanto descrito para o nosso caso de buffer temporário.

Quanto ao align_memset, isso é bastante tolo. Você só precisa fazer um loop de até 15 bytes para alcançar um endereço alinhado e, em seguida, prosseguir com os armazenamentos alinhados depois disso, com algum código de limpeza possível no final. Você pode até fazer os bits de limpeza no código vetorial, como armazenamentos desalinhados que se sobrepõem à região alinhada (desde que o comprimento seja pelo menos o comprimento de um vetor) ou usando algo como movmaskdqu. Alguém está apenas sendo preguiçoso. No entanto, é provavelmente uma pergunta de entrevista razoável se o entrevistador quiser saber se você se sente confortável com stdint.h, operadores bit a bit e fundamentos de memória, para que o exemplo artificial possa ser perdoado.

Ian Ollmann
fonte
5

Estou há ninguém surpreendeu votou-se Shao 's resposta que, no meu entender, é impossível fazer o que é perguntado em C99 padrão, uma vez que a conversão de um ponteiro para um tipo integral formalmente é um comportamento indefinido. (Além do padrão que permite a conversão de uintptr_t<-> void*, mas o padrão não parece permitir nenhuma manipulação do uintptr_tvalor e depois convertê-lo novamente.)

Lutorm
fonte
Não é necessário que exista um tipo uintptr_t ou que seus bits tenham qualquer relação com bits no ponteiro subjacente. Se houver um excesso de alocação de armazenamento, armazene o ponteiro como um unsigned char* myptr; e, em seguida, calcule `mptr + = (16- (uintptr_t) my_ptr) & 0x0F, o comportamento seria definido em todas as implementações que definem my_ptr, mas se o ponteiro resultante seria alinhado dependeria do mapeamento entre bits e endereços uintptr_t.
Supercat 8/16
3

uso de memalign, Aligned-Memory-Blocks pode ser uma boa solução para o problema.

neurônio
fonte
Observe que a versão atual (fevereiro de 2016) da página referenciada diz "A memalignfunção está obsoleta e aligned_allocou posix_memaligndeve ser usada". Eu não sei o que ele disse em outubro de 2010.
Jonathan Leffler
3

A primeira coisa que me veio à cabeça ao ler esta pergunta foi definir uma estrutura alinhada, instanciar e apontar para ela.

Existe uma razão fundamental para a minha falta, já que ninguém mais sugeriu isso?

Como nota de rodapé, como usei uma matriz de caracteres (supondo que o sistema seja 8 bits (ou seja, 1 byte)), não vejo a necessidade do __attribute__((packed))necessariamente (corrija-me se estiver errado), mas coloquei de qualquer maneira.

Isso funciona em dois sistemas nos quais eu tentei, mas é possível que exista uma otimização do compilador que eu não tenha me dado falsos positivos em relação à eficácia do código. Eu usei gcc 4.9.2no OSX e gcc 5.2.1no 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
fonte
1

Específico para o MacOS X:

  1. Todos os ponteiros alocados com malloc são alinhados em 16 bytes.
  2. O C11 é suportado, então você pode simplesmente chamar align_malloc (16, tamanho).

  3. O MacOS X escolhe um código otimizado para processadores individuais no momento da inicialização para memset, memcpy e memmove e esse código usa truques que você nunca ouviu falar para torná-lo mais rápido. 99% de chance de o memset funcionar mais rápido do que qualquer memset escrito à mão16, o que torna toda a questão inútil.

Se você deseja uma solução 100% portátil, antes do C11 não há. Porque não há uma maneira portátil de testar o alinhamento de um ponteiro. Se não precisar ser 100% portátil, você pode usar

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

Isso pressupõe que o alinhamento de um ponteiro seja armazenado nos bits mais baixos ao converter um ponteiro em int não assinado. A conversão para int não assinado perde informações e a implementação é definida, mas isso não importa, porque não convertemos o resultado em um ponteiro.

A parte horrível é, é claro, que o ponteiro original deve ser salvo em algum lugar para ser liberado () com ele. Então, apesar de tudo, eu realmente duvidaria da sabedoria deste design.

Chris
fonte
1
Onde você encontra o aligned_mallocOS X? Estou usando o Xcode 6.1 e ele não está definido em nenhum lugar do SDK do iOS, nem é declarado em nenhum lugar /usr/include/*.
Todd Lehman
O mesmo vale para o XCode 7.2 no El Capitan (Mac OS X 10.11.3). A função C11 é, de qualquer forma aligned_alloc(), mas também não é declarada. No GCC 5.3.0, recebo as mensagens alig.c:7:15: error: incompatible implicit declaration of built-in function ‘aligned_alloc’ [-Werror]e interessantes alig.c:7:15: note: include ‘<stdlib.h>’ or provide a declaration of ‘aligned_alloc’. O código realmente incluiu <stdlib.h>, mas -std=c11nem -std=gnu11alterou as mensagens de erro.
Jonathan Leffler
0

Você também pode adicionar 16 bytes e enviar o ptr original para 16 bits alinhado adicionando o (16-mod) conforme abaixo do ponteiro:

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
fonte
0

Se houver restrições, você não poderá desperdiçar um único byte, e esta solução funcionará: Nota: Há um caso em que isso pode ser executado 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);
Pensamento profundo
fonte
Há uma chance muito boa de que, se você alocar e liberar um bloco de N bytes e solicitar outro bloco de N bytes, o bloco original seja retornado novamente. Portanto, um loop infinito é muito provável se a primeira alocação não atender ao requisito de alinhamento. Evidentemente, isso evita desperdiçar um único byte ao custo de desperdiçar muitos ciclos de CPU.
Jonathan Leffler
Você tem certeza de que o %operador está definido de void*maneira significativa?
Ajay Brahmakshatriya
0

Para a solução, usei um conceito de preenchimento que alinha a memória e não desperdiça a memória de um único byte.

Se houver restrições, você não poderá desperdiçar um único byte. Todos os ponteiros alocados com malloc são alinhados em 16 bytes.

O C11 é suportado, então você pode simplesmente ligar aligned_alloc (16, size).

void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
user3415603
fonte
1
Em muitos sistemas de 64 bits, o ponteiro retornado por malloc()é alinhado de fato em um limite de 16 bytes, mas nada em qualquer padrão garante que - ele estará simplesmente suficientemente bem alinhado para qualquer uso e em muitos sistemas de 32 bits alinhados em um O limite de 8 bytes é suficiente e, para alguns, um limite de 4 bytes é 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 seja a implementação mais simples, deixe-me saber seus comentários.

stackguy
fonte
-3
long add;   
mem = (void*)malloc(1024 +15);
add = (long)mem;
add = add - (add % 16);//align to 16 byte boundary
ptr = (whatever*)(add);
Ramana
fonte
Acho que há um problema com isso porque o seu add aponta para um local que não é comercializado - Não tenho certeza de como isso funcionou no seu.
resultado é o seguinte
@ Sam deveria ser add += 16 - (add % 16). (2 - (2 % 16)) == 0.
SS Anne