Comment allouer de la mémoire alignée uniquement à l'aide de la bibliothèque standard?

422

Je viens de terminer un test dans le cadre d'un entretien d'embauche, et une question m'a dérouté, même en utilisant Google comme référence. J'aimerais voir ce que l'équipe StackOverflow peut en faire:

La memset_16alignedfonction nécessite un pointeur aligné de 16 octets qui lui est transmis, sinon elle se bloque.

a) Comment alloueriez-vous 1024 octets de mémoire et l'alignez-vous sur une limite de 16 octets?
b) Libérez la mémoire après l' memset_16alignedexécution de.

{    
   void *mem;
   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here    
}
JimDaniel
la source
89
hmmm ... pour la viabilité à long terme du code, que diriez-vous de "Incendiez quiconque a écrit memset_16aligned et corrigez-le ou remplacez-le afin qu'il n'ait pas de condition aux limites particulière"
Steven A. Lowe
29
Certainement une question valable à poser - "pourquoi l'alignement particulier de la mémoire". Mais il peut y avoir de bonnes raisons à cela - dans ce cas, il se pourrait que le memset_16aligned () puisse utiliser des entiers de 128 bits et c'est plus facile si la mémoire est connue pour être alignée. Etc.
Jonathan Leffler
5
Celui qui a écrit memset pourrait utiliser un alignement interne de 16 octets pour effacer la boucle intérieure et un petit prologue / épilogue de données pour nettoyer les extrémités non alignées. Ce serait beaucoup plus facile que de faire en sorte que les codeurs gèrent des pointeurs de mémoire supplémentaires.
Adisak
8
Pourquoi voudrait-on que les données soient alignées sur une limite de 16 octets? Probablement pour le charger dans des registres SSE 128 bits. Je pense que les (plus récents) movs non alignés (par exemple, movupd, lddqu) sont plus lents, ou peut-être qu'ils ciblent les processeurs sans SSE2 / 3
11
L'alignement des adresses permet une utilisation optimisée du cache ainsi qu'une bande passante plus élevée entre les différents niveaux de cache et de RAM (pour les charges de travail les plus courantes). Voir ici stackoverflow.com/questions/381244/purpose-of-memory-alignment
Deepthought

Réponses:

587

Réponse originale

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

Réponse fixe

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

Explication comme demandé

La première étape consiste à allouer suffisamment d'espace libre, au cas où. Étant donné que la mémoire doit être alignée sur 16 octets (ce qui signifie que l'adresse d'octet de tête doit être un multiple de 16), l'ajout de 16 octets supplémentaires garantit que nous avons suffisamment d'espace. Quelque part dans les 16 premiers octets, il y a un pointeur aligné de 16 octets. (Notez que malloc()est censé renvoyer un pointeur qui est suffisamment bien aligné pour tout . But Cependant, le sens de « tout » est principalement pour des choses comme les types de base - long, double, long double, long long., Et des pointeurs vers des objets et des pointeurs vers des fonctions Lorsque vous êtes faire des choses plus spécialisées, comme jouer avec des systèmes graphiques, ils peuvent avoir besoin d'un alignement plus strict que le reste du système - d'où des questions et réponses comme celle-ci.)

L'étape suivante consiste à convertir le pointeur void en un pointeur char; Malgré GCC, vous n'êtes pas censé faire de l'arithmétique des pointeurs sur les pointeurs vides (et GCC a des options d'avertissement pour vous dire quand vous en abusez). Ajoutez ensuite 16 au pointeur de départ. Supposons que malloc()vous ayez renvoyé un pointeur incroyablement mal aligné: 0x800001. L'ajout du 16 donne 0x800011. Maintenant, je veux arrondir à la limite de 16 octets - je veux donc réinitialiser les 4 derniers bits à 0. 0x0F a les 4 derniers bits mis à un; par conséquent, ~0x0Ftous les bits sont définis sur un, à l'exception des quatre derniers. Et cela avec 0x800011 donne 0x800010. Vous pouvez parcourir les autres décalages et voir que la même arithmétique fonctionne.

La dernière étape, free()est facile: vous toujours, et seulement, le retour à free()une valeur que l' un des malloc(), calloc()ou realloc()retourné à vous - tout est bien une catastrophe. Vous avez correctement fourni memde conserver cette valeur - merci. Le libre le libère.

Enfin, si vous connaissez les éléments internes du mallocpackage de votre système , vous pourriez deviner qu'il pourrait bien renvoyer des données alignées sur 16 octets (ou qu'il pourrait être aligné sur 8 octets). S'il était aligné sur 16 octets, vous n'auriez pas besoin de vous arrêter aux valeurs. Cependant, c'est douteux et non portable - d'autres mallocpackages ont des alignements minimaux différents, et donc supposer une chose quand il fait quelque chose de différent conduirait à des vidages de mémoire. Dans de larges limites, cette solution est portable.

Quelqu'un d'autre a mentionné posix_memalign()une autre façon d'obtenir la mémoire alignée; qui n'est pas disponible partout, mais pourrait souvent être implémenté en utilisant cela comme base. Notez qu'il était pratique que l'alignement soit une puissance de 2; d'autres alignements sont plus compliqués.

Encore un commentaire - ce code ne vérifie pas que l'allocation a réussi.

Amendement

Le programmeur Windows a souligné que vous ne pouvez pas effectuer d'opérations de masquage de bits sur des pointeurs, et, en effet, GCC (testé 3.4.6 et 4.3.1) se plaint comme ça. Ainsi, une version modifiée du code de base - converti en un programme principal, suit. J'ai également pris la liberté d'ajouter seulement 15 au lieu de 16, comme cela a été souligné. J'utilise uintptr_tdepuis que C99 existe depuis assez longtemps pour être accessible sur la plupart des plateformes. Si ce n'était pas pour l'utilisation de PRIXPTRdans les printf()instructions, ce serait suffisant pour #include <stdint.h>au lieu d'utiliser #include <inttypes.h>. [Ce code inclut le correctif signalé par CR , qui réitère un point soulevé par Bill K il y a plusieurs années, que j'ai réussi à ignorer jusqu'à présent.]

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

Et voici une version légèrement plus généralisée, qui fonctionnera pour les tailles qui sont une puissance 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);
}

Pour convertir test_mask()en une fonction d'allocation à usage général, la valeur de retour unique de l'allocateur devrait coder l'adresse de libération, comme plusieurs personnes l'ont indiqué dans leurs réponses.

Problèmes avec les enquêteurs

Uri a commenté: Peut-être que j'ai un problème de compréhension de la lecture ce matin, mais si la question d'entrevue dit spécifiquement: "Comment alloueriez-vous 1024 octets de mémoire" et vous allouez clairement plus que cela. Ne serait-ce pas un échec automatique de l'intervieweur?

Ma réponse ne rentre pas dans un commentaire de 300 caractères ...

Cela dépend, je suppose. Je pense que la plupart des gens (y compris moi) ont pris la question pour signifier "Comment alloueriez-vous un espace dans lequel 1024 octets de données peuvent être stockés, et où l'adresse de base est un multiple de 16 octets". Si l'intervieweur voulait vraiment savoir comment allouer 1024 octets (uniquement) et l'aligner sur 16 octets, alors les options sont plus limitées.

  • De toute évidence, une possibilité consiste à allouer 1 024 octets, puis à donner à cette adresse le «traitement d'alignement»; le problème avec cette approche est que l'espace disponible réel n'est pas correctement déterminé (l'espace utilisable est compris entre 1008 et 1024 octets, mais il n'y avait pas de mécanisme disponible pour spécifier quelle taille), ce qui le rend moins qu'utile.
  • Une autre possibilité est que vous êtes censé écrire un allocateur de mémoire plein et vous assurer que le bloc de 1024 octets que vous renvoyez est correctement aligné. Si tel est le cas, vous finissez probablement par faire une opération assez similaire à celle de la solution proposée, mais vous la cachez dans l'allocateur.

Cependant, si l'intervieweur s'attendait à l'une de ces réponses, je m'attendrais à ce qu'il reconnaisse que cette solution répond à une question étroitement liée, puis à recadrer sa question pour orienter la conversation dans la bonne direction. (De plus, si l'intervieweur est devenu très bâclé, alors je ne voudrais pas le travail; si la réponse à une exigence insuffisamment précise est abattue dans les flammes sans correction, alors l'intervieweur n'est pas quelqu'un pour qui il est sûr de travailler.)

Le monde continue

Le titre de la question a changé récemment. C'est Résoudre l'alignement de la mémoire dans la question d'entrevue C qui m'a déconcerté . Le titre révisé ( Comment allouer la mémoire alignée uniquement en utilisant la bibliothèque standard? ) Exige une réponse légèrement révisée - cet addendum le fournit.

C11 (ISO / IEC 9899: 2011) fonction ajoutée aligned_alloc():

7.22.3.1 La aligned_allocfonction

Synopsis

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

Description
La aligned_allocfonction alloue de l'espace à un objet dont l'alignement est spécifié par alignment, dont la taille est spécifiée par sizeet dont la valeur est indéterminée. La valeur de alignmentdoit être un alignement valide pris en charge par la mise en œuvre et la valeur de sizedoit être un multiple entier de alignment.

Renvoie
La aligned_allocfonction renvoie soit un pointeur nul, soit un pointeur sur l'espace alloué.

Et POSIX définit posix_memalign():

#include <stdlib.h>

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

LA DESCRIPTION

La posix_memalign()fonction doit allouer des sizeoctets alignés sur une frontière spécifiée par alignmentet retourner un pointeur vers la mémoire allouée dans memptr. La valeur de alignmentdoit être une puissance de deux multiples de sizeof(void *).

En cas de réussite, la valeur indiquée par memptrdoit être un multiple de alignment.

Si la taille de l'espace demandé est 0, le comportement est défini par l'implémentation; la valeur renvoyée memptrdoit être soit un pointeur nul, soit un pointeur unique.

La free()fonction doit désallouer la mémoire qui a été précédemment allouée par posix_memalign().

VALEUR DE RETOUR

En cas de réussite, posix_memalign()doit retourner zéro; sinon, un numéro d'erreur doit être renvoyé pour indiquer l'erreur.

L'un ou l'autre ou les deux peuvent être utilisés pour répondre à la question maintenant, mais seule la fonction POSIX était une option lorsque la question a été répondue à l'origine.

Dans les coulisses, la nouvelle fonction de mémoire alignée fait à peu près le même travail que celui décrit dans la question, sauf qu'elle a la possibilité de forcer l'alignement plus facilement et de garder une trace du début de la mémoire alignée en interne afin que le code ne avoir à traiter spécialement - il libère juste la mémoire retournée par la fonction d'allocation qui a été utilisée.

Jonathan Leffler
la source
13
Et je suis rouillé avec C ++, mais je ne crois pas vraiment que ~ 0x0F se développera correctement à la taille du pointeur. Si ce n'est pas le cas, tout l'enfer se déchaînera car vous masquerez également les parties les plus importantes de votre pointeur. Je peux me tromper cependant.
Bill K
66
BTW '+15' fonctionne aussi bien que '+16' ... pas d'impact pratique dans cette situation.
Menkboy
15
Les commentaires '+ 15' de Menkboy et Greg sont corrects, mais malloc () arrondirait presque certainement cela à 16 de toute façon. L'utilisation de +16 est légèrement plus facile à expliquer. La solution généralisée est fastidieuse, mais réalisable.
Jonathan Leffler
6
@Aerovistae: C'est un peu une question piège, et dépend principalement de votre compréhension de la façon de faire correspondre un nombre arbitraire (en fait l'adresse renvoyée par l'allocateur de mémoire) à une certaine exigence (multiple de 16). Si on vous disait d'arrondir 53 au multiple de 16 le plus proche, comment feriez-vous cela? Le processus n'est pas très différent pour les adresses; c'est simplement que les chiffres avec lesquels vous avez généralement affaire sont plus importants. N'oubliez pas, des questions d'entrevue sont posées pour savoir comment vous pensez, pas pour savoir si vous connaissez la réponse.
Jonathan Leffler
3
@akristmann: Le code d'origine est correct si vous disposez <inttypes.h>de C99 disponible (au moins pour la chaîne de format - sans doute, les valeurs devraient être passées avec un cast :) (uintptr_t)mem, (uintptr_t)ptr. La chaîne de format repose sur la concaténation de chaînes et la macro PRIXPTR est le printf()spécificateur de longueur et de type correct pour la sortie hexadécimale d'une uintptr_tvaleur. L'alternative est d'utiliser, %pmais la sortie de celui-ci varie selon la plate-forme (certains ajoutent un interligne 0x, la plupart n'en ont pas) et est généralement écrite avec des chiffres hexadécimaux en minuscule, ce que je n'aime pas; ce que j'ai écrit est uniforme sur toutes les plateformes.
Jonathan Leffler
58

Trois réponses légèrement différentes selon la façon dont vous regardez la question:

1) La solution de Jonathan Leffler est assez bonne pour la question exacte, sauf que pour arrondir à 16 alignés, vous n'avez besoin que de 15 octets supplémentaires, pas de 16.

UNE:

/* 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) Pour une fonction d'allocation de mémoire plus générique, l'appelant ne veut pas avoir à suivre deux pointeurs (un à utiliser et un à libérer). Vous stockez donc un pointeur vers le "vrai" tampon sous le tampon aligné.

UNE:

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]);

Notez que contrairement à (1), où seulement 15 octets ont été ajoutés à mem, ce code pourrait en fait réduire l'alignement si votre implémentation arrive à garantir un alignement de 32 octets à partir de malloc (peu probable, mais en théorie une implémentation C pourrait avoir un 32 octets type aligné). Cela n'a pas d'importance si tout ce que vous faites est d'appeler memset_16aligned, mais si vous utilisez la mémoire pour une structure, cela peut être important.

Je ne suis pas sûr de savoir ce qu'est un bon correctif pour cela (autre que d'avertir l'utilisateur que le tampon renvoyé n'est pas nécessairement adapté aux structures arbitraires) car il n'y a aucun moyen de déterminer par programme ce qu'est la garantie d'alignement spécifique à l'implémentation. Je suppose qu'au démarrage, vous pouvez allouer deux ou plusieurs tampons de 1 octet et supposer que le pire alignement que vous voyez est l'alignement garanti. Si vous vous trompez, vous perdez de la mémoire. Quiconque a une meilleure idée, dites-le s'il vous plaît ...

[ Ajouté : L'astuce «standard» consiste à créer une union de «types susceptibles d'être alignés au maximum» pour déterminer l'alignement requis. Les types alignés au maximum sont susceptibles d'être (en C99) ' long long', ' long double', ' void *' ou ' void (*)(void)'; si vous incluez <stdint.h>, vous pourriez probablement utiliser ' intmax_t' à la place de long long(et, sur les machines Power 6 (AIX), vous intmax_tobtiendriez un type entier 128 bits). Les exigences d'alignement pour cette union peuvent être déterminées en l'incorporant dans une structure avec un seul caractère suivi de l'union:

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;

Vous utiliseriez alors le plus grand de l'alignement demandé (dans l'exemple, 16) et la alignvaleur calculée ci-dessus.

Sur Solaris 10 (64 bits), il semble que l'alignement de base du résultat malloc()est un multiple de 32 octets.
]

En pratique, les allocateurs alignés prennent souvent un paramètre pour l'alignement plutôt que d'être câblé. Ainsi, l'utilisateur transmettra la taille de la structure dont il se soucie (ou la moindre puissance de 2 supérieure ou égale à cela) et tout ira bien.

3) Utilisez ce que fournit votre plateforme: posix_memalignpour POSIX, _aligned_mallocsous Windows.

4) Si vous utilisez C11, l'option la plus propre - portable et concise - consiste à utiliser la fonction de bibliothèque standard aligned_allocintroduite dans cette version de la spécification de langage.

Steve Jessop
la source
1
Je suis d'accord - je pense que l'intention de la question est que le code qui libère le bloc de mémoire n'aurait accès qu'au pointeur aligné de 16 octets "cuit".
Michael Burr
1
Pour une solution générale - vous avez raison. Cependant, le modèle de code dans la question montre clairement les deux.
Jonathan Leffler
1
Bien sûr, et dans une bonne interview, ce qui se passe, c'est que vous donnez votre réponse, puis si l'enquêteur veut voir ma réponse, il change la question.
Steve Jessop
1
Je m'oppose à l'utilisation ASSERT(mem);pour vérifier les résultats d'allocation; assertsert à détecter les erreurs de programmation et non à manquer de ressources d'exécution.
hlovdal
4
L'utilisation de binaire & avec a char *et a size_tentraînera une erreur. Il faudrait utiliser quelque chose comme uintptr_t.
Marko
20

Voici une approche alternative à la partie «arrondir». Ce n'est pas la solution la plus brillamment codée, mais elle fait le travail, et ce type de syntaxe est un peu plus facile à retenir (plus fonctionnerait pour les valeurs d'alignement qui ne sont pas une puissance de 2). Le uintptr_tcasting était nécessaire pour apaiser le compilateur; l'arithmétique des pointeurs n'aime pas beaucoup la division ou la multiplication.

void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);
An̲̳̳drew
la source
2
En général, lorsque vous avez 'unsigned long long', vous avez également uintptr_t qui est explicitement défini pour être suffisamment grand pour contenir un pointeur de données (void *). Mais votre solution a bien des avantages si, pour une raison quelconque, vous aviez besoin d'un alignement qui n'était pas une puissance de 2. Peu probable, mais possible.
Jonathan Leffler
@Andrew: Le vote positif pour ce type de syntaxe est un peu plus facile à retenir (plus fonctionnerait pour les valeurs d'alignement qui ne sont pas une puissance de 2) .
legends2k
19

Malheureusement, en C99, il semble assez difficile de garantir l'alignement de toute sorte d'une manière qui serait portable sur toute implémentation C conforme à C99. Pourquoi? Parce qu'un pointeur n'est pas garanti d'être "l'adresse d'octet" que l'on pourrait imaginer avec un modèle de mémoire plate. La représentation de uintptr_t n'est pas non plus garantie, qui est de toute façon un type facultatif.

Nous connaissons peut-être certaines implémentations qui utilisent une représentation pour void * (et par définition, aussi char * ) qui est une simple adresse d'octet, mais en C99, elle est opaque pour nous, les programmeurs. Une implémentation peut représenter un pointeur par un ensemble { segment , offset } où l' offset pourrait avoir un alignement qui sait quoi "en réalité". Pourquoi, un pointeur pourrait même être une certaine forme de valeur de recherche de table de hachage, ou même une valeur de recherche de liste liée. Il pourrait encoder des informations sur les limites.

Dans un récent projet C1X pour une norme C, nous voyons le mot clé _Alignas . Cela pourrait aider un peu.

La seule garantie que C99 nous donne est que les fonctions d'allocation de mémoire renverront un pointeur approprié pour une affectation à un pointeur pointant sur n'importe quel type d'objet. Comme nous ne pouvons pas spécifier l'alignement des objets, nous ne pouvons pas implémenter nos propres fonctions d'allocation avec la responsabilité de l'alignement d'une manière portable bien définie.

Il serait bon de se tromper sur cette affirmation.

Shao
la source
C11 a aligned_alloc(). (C ++ 11/14 / 1z ne l'a toujours pas). _Alignas()et C ++ alignas()ne font rien pour l'allocation dynamique, seulement pour le stockage automatique et statique (ou la structure).
Peter Cordes
15

Sur le front de remplissage de 16 vs 15 octets, le nombre réel que vous devez ajouter pour obtenir un alignement de N est max (0, NM) où M est l'alignement naturel de l'allocateur de mémoire (et les deux sont des puissances de 2).

Étant donné que l'alignement minimal de la mémoire de tout allocateur est de 1 octet, 15 = max (0,16-1) est une réponse prudente. Cependant, si vous savez que votre allocateur de mémoire va vous donner des adresses alignées int 32 bits (ce qui est assez courant), vous auriez pu utiliser 12 comme pad.

Ce n'est pas important pour cet exemple, mais cela pourrait être important sur un système embarqué avec 12 Ko de RAM où chaque int enregistré seul compte.

La meilleure façon de l'implémenter si vous essayez réellement d'enregistrer chaque octet possible est en tant que macro afin de pouvoir l'alimenter en alignement de votre mémoire native. Encore une fois, cela n'est probablement utile que pour les systèmes embarqués où vous devez enregistrer chaque octet.

Dans l'exemple ci-dessous, sur la plupart des systèmes, la valeur 1 est très bien car MEMORY_ALLOCATOR_NATIVE_ALIGNMENT, pour notre système embarqué théorique avec des allocations alignées sur 32 bits, les éléments suivants pourraient économiser un tout petit peu de mémoire précieuse:

#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
la source
8

Peut-être auraient-ils été satisfaits d'une connaissance de memalign ? Et comme le souligne Jonathan Leffler, il y a deux nouvelles fonctions préférables à connaître.

Oups, Florin m'a battu. Cependant, si vous lisez la page de manuel à laquelle j'ai lié, vous comprendrez très probablement l'exemple fourni par une affiche précédente.

Don Wakefield
la source
1
Notez que la version actuelle (février 2016) de la page référencée indique "La memalignfonction est obsolète et aligned_allocou posix_memaligndoit être utilisée à la place". Je ne sais pas ce qu'il a dit en octobre 2008 - mais il ne l'a probablement pas mentionné aligned_alloc()car cela a été ajouté au C11.
Jonathan Leffler
5

Nous faisons ce genre de choses tout le temps pour Accelerate.framework, une bibliothèque OS X / iOS fortement vectorisée, où nous devons faire attention à l'alignement tout le temps. Il existe plusieurs options, dont une ou deux que je n'ai pas vues mentionnées ci-dessus.

La méthode la plus rapide pour un petit tableau comme celui-ci est simplement de le coller sur la pile. Avec GCC / clang:

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

Pas de gratuit () requis. Il s'agit généralement de deux instructions: soustraire 1024 du pointeur de pile, puis ET le pointeur de pile avec -alignment. Vraisemblablement, le demandeur avait besoin des données sur le tas car la durée de vie de la baie dépassait la pile ou la récursivité est à l'œuvre ou l'espace de pile est très important.

Sous OS X / iOS, tous les appels vers malloc / calloc / etc. sont toujours alignés sur 16 octets. Si vous aviez besoin de 32 octets alignés pour AVX, par exemple, vous pouvez utiliser posix_memalign:

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

Certaines personnes ont mentionné l'interface C ++ qui fonctionne de manière similaire.

Il ne faut pas oublier que les pages sont alignées sur de grandes puissances de deux, donc les tampons alignés sur les pages sont également alignés sur 16 octets. Ainsi, mmap () et valloc () et d'autres interfaces similaires sont également des options. mmap () a l'avantage que le tampon peut être alloué préinitialisé avec quelque chose de non nul, si vous le souhaitez. Étant donné que ceux-ci ont une taille alignée sur la page, vous n'obtiendrez pas l'allocation minimale de ceux-ci, et il sera probablement soumis à un défaut de machine virtuelle la première fois que vous le toucherez.

Cheesy: Allumez guard malloc ou similaire. Les tampons de taille n * 16 octets tels que celui-ci seront alignés n * 16 octets, car la machine virtuelle est utilisée pour intercepter les dépassements et ses limites se trouvent aux limites de la page.

Certaines fonctions Accelerate.framework intègrent un tampon temporaire fourni par l'utilisateur à utiliser comme espace de travail. Ici, nous devons supposer que le tampon qui nous est transmis est très mal aligné et que l'utilisateur essaie activement de rendre notre vie difficile par dépit. (Nos cas de test collent une page de garde juste avant et après le tampon temporaire pour souligner la dépit.) Ici, nous retournons la taille minimale dont nous avons besoin pour garantir un segment aligné de 16 octets quelque part, puis alignons manuellement le tampon par la suite. Cette taille est souhaitée_taille + alignement - 1. Donc, dans ce cas, c'est 1024 + 16 - 1 = 1039 octets. Alignez ensuite comme suit:

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

L'ajout d'alignement-1 déplacera le pointeur au-delà de la première adresse alignée, puis AND avec -alignment (par exemple 0xfff ... ff0 pour alignement = 16) le ramènera à l'adresse alignée.

Comme décrit par d'autres articles, sur d'autres systèmes d'exploitation sans garanties d'alignement de 16 octets, vous pouvez appeler malloc avec la plus grande taille, mettre de côté le pointeur gratuitement () plus tard, puis aligner comme décrit immédiatement ci-dessus et utiliser le pointeur aligné, autant que décrit pour notre cas de tampon temporaire.

Quant à align_memset, c'est plutôt idiot. Vous n'avez qu'à boucler jusqu'à 15 octets pour atteindre une adresse alignée, puis procédez à des magasins alignés après cela avec un code de nettoyage possible à la fin. Vous pouvez même faire les bits de nettoyage en code vectoriel, soit en tant que magasins non alignés qui chevauchent la région alignée (à condition que la longueur soit au moins la longueur d'un vecteur) ou en utilisant quelque chose comme movmaskdqu. Quelqu'un est juste paresseux. Cependant, c'est probablement une question d'entrevue raisonnable si l'intervieweur veut savoir si vous êtes à l'aise avec stdint.h, les opérateurs au niveau du bit et les fondamentaux de la mémoire, de sorte que l'exemple artificiel peut être pardonné.

Ian Ollmann
la source
5

Je suis surpris que personne n'ait voté la réponse de Shao selon laquelle, si je comprends bien, il est impossible de faire ce qui est demandé dans la norme C99, car la conversion formelle d'un pointeur en un type intégral est un comportement indéfini. (En dehors de la norme autorisant la conversion de <-> , mais la norme ne semble pas autoriser de manipulation de la valeur, puis la reconvertir.)uintptr_tvoid*uintptr_t

Lutorm
la source
Il n'est pas nécessaire qu'un type uintptr_t existe, ou que ses bits aient une relation avec les bits du pointeur sous-jacent. Si vous deviez surallouer du stockage, stockez le pointeur en tant que unsigned char* myptr; puis calculez `mptr + = (16- (uintptr_t) my_ptr) & 0x0F, le comportement serait défini sur toutes les implémentations qui définissent my_ptr, mais si le pointeur résultant serait aligné dépendrait du mappage entre les bits uintptr_t et les adresses.
supercat
3

l'utilisation de memalign, Aligned-Memory-Blocks peut être une bonne solution au problème.

neurone
la source
Notez que la version actuelle (février 2016) de la page référencée indique "La memalignfonction est obsolète et aligned_allocou posix_memaligndoit être utilisée à la place". Je ne sais pas ce qu'il a dit en octobre 2010.
Jonathan Leffler
3

La première chose qui m'est venue à l'esprit lors de la lecture de cette question a été de définir une structure alignée, de l'instancier, puis de la désigner.

Y a-t-il une raison fondamentale pour laquelle je manque car personne d'autre ne l'a suggéré?

En tant que sidenote, puisque j'ai utilisé un tableau de caractères (en supposant que le caractère du système est de 8 bits (soit 1 octet)), je ne vois pas la nécessité du __attribute__((packed))nécessairement (corrigez-moi si je me trompe), mais je le mets de quelque manière que.

Cela fonctionne sur deux systèmes sur lesquels j'ai essayé, mais il est possible qu'il existe une optimisation du compilateur que je ne suis pas au courant de me donner de faux positifs vis-à-vis de l'efficacité du code. J'ai utilisé gcc 4.9.2sur OSX et gcc 5.2.1sur 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
la source
1

Spécifique à MacOS X:

  1. Tous les pointeurs alloués avec malloc sont alignés sur 16 octets.
  2. C11 est pris en charge, vous pouvez donc simplement appeler align_malloc (16, taille).

  3. MacOS X sélectionne du code optimisé pour les processeurs individuels au démarrage pour memset, memcpy et memmove et ce code utilise des astuces dont vous n'avez jamais entendu parler pour le rendre rapide. 99% de chances que le memset fonctionne plus rapidement que tout memset écrit à la main16, ce qui rend toute la question inutile.

Si vous voulez une solution 100% portable, avant C11 il n'y en a pas. Parce qu'il n'y a aucun moyen portable de tester l'alignement d'un pointeur. S'il ne doit pas être 100% portable, vous pouvez utiliser

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

Cela suppose que l'alignement d'un pointeur est stocké dans les bits les plus bas lors de la conversion d'un pointeur en entier non signé. La conversion en entier non signé perd des informations et est définie par l'implémentation, mais cela n'a pas d'importance car nous ne convertissons pas le résultat en un pointeur.

La partie horrible est bien sûr que le pointeur d'origine doit être enregistré quelque part pour appeler free () avec lui. Donc, dans l'ensemble, je doute vraiment de la sagesse de cette conception.

Chris
la source
1
Où trouvez-vous aligned_mallocdans OS X? J'utilise Xcode 6.1 et il n'est défini nulle part dans le SDK iOS, ni déclaré nulle part dans /usr/include/*.
Todd Lehman
Idem pour XCode 7.2 sur El Capitan (Mac OS X 10.11.3). La fonction C11 l'est en tout cas aligned_alloc(), mais elle n'est pas non plus déclarée. De GCC 5.3.0, je reçois les messages intéressants alig.c:7:15: error: incompatible implicit declaration of built-in function ‘aligned_alloc’ [-Werror]et alig.c:7:15: note: include ‘<stdlib.h>’ or provide a declaration of ‘aligned_alloc’. Le code comprenait en effet <stdlib.h>, mais ni -std=c11ni -std=gnu11modifié les messages d'erreur.
Jonathan Leffler
0

Vous pouvez également ajouter quelques 16 octets, puis pousser le ptr d'origine à 16 bits aligné en ajoutant le (16-mod) comme sous le pointeur:

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);
}
résultats
la source
0

S'il y a des contraintes, vous ne pouvez pas gaspiller un seul octet, alors cette solution fonctionne: Remarque: Il y a un cas où cela peut être exécuté à l'infini: D

   void *mem;  
   void *ptr;
try:
   mem =  malloc(1024);  
   if (mem % 16 != 0) {  
       free(mem);  
       goto try;
   }  
   ptr = mem;  
   memset_16aligned(ptr, 0, 1024);
Pensée profonde
la source
Il y a de très bonnes chances que si vous allouez puis libérez un bloc de N octets puis demandez un autre bloc de N octets, le bloc d'origine sera renvoyé à nouveau. Une boucle infinie est donc très probable si la première allocation ne répond pas aux exigences d'alignement. Bien sûr, cela évite de gaspiller un seul octet au prix de perdre beaucoup de cycles CPU.
Jonathan Leffler
Êtes-vous sûr que l' %opérateur est défini de void*manière significative?
Ajay Brahmakshatriya
0

Pour la solution, j'ai utilisé un concept de remplissage qui aligne la mémoire et ne gaspille pas la mémoire d'un seul octet.

S'il y a des contraintes, vous ne pouvez pas perdre un seul octet. Tous les pointeurs alloués avec malloc sont alignés sur 16 octets.

C11 est pris en charge, vous pouvez donc simplement appeler aligned_alloc (16, size).

void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
user3415603
la source
1
Sur de nombreux systèmes 64 bits, le pointeur renvoyé par malloc()est en effet aligné sur une limite de 16 octets, mais rien dans aucune norme ne garantit que - il sera simplement suffisamment bien aligné pour toute utilisation, et sur de nombreux systèmes 32 bits alignés sur un Une limite de 8 octets est suffisante, et pour certains, une limite de 4 octets est suffisante.
Jonathan Leffler
0
size =1024;
alignment = 16;
aligned_size = size +(alignment -(size %  alignment));
mem = malloc(aligned_size);
memset_16aligned(mem, 0, 1024);
free(mem);

J'espère que celui-ci est la mise en œuvre la plus simple, faites-moi part de vos commentaires.

stackguy
la source
-3
long add;   
mem = (void*)malloc(1024 +15);
add = (long)mem;
add = add - (add % 16);//align to 16 byte boundary
ptr = (whatever*)(add);
Ramana
la source
Je pense qu'il y a un problème avec cela car votre annonce pointera vers un emplacement qui n'est pas malloc'd - Je ne sais pas comment cela a fonctionné sur le vôtre.
resultsway
@Sam Ça devrait être add += 16 - (add % 16). (2 - (2 % 16)) == 0.
SS Anne