Quelles précautions dois-je prendre pour créer un pool de mémoire qui n'invoque pas un comportement indéfini?

Question

Mon premier problème est que j'ai, sur un projet, plusieurs objets qui ont une durée de vie (c'est à dire, une fois que j'ai de libre-l'un d'eux, je vais les libérer tous), puis j'ai voulu allouer un bloc de mémoire. J'ai des tableaux de trois différents types d'objets, struct foo, void *, et char. Au début, je voulais malloc() d'un bloc comme ceci:

// +---------------+---------+-----------+---------+---------+
// | struct foo[n] | padding | void *[m] | padding | char[o] |
// +---------------+---------+-----------+---------+---------+

Mais alors... comment ai-je pu accomplir cela sans faire appel à un comportement indéfini? I. e., le respect de type aliasing règles, aligment... Comment calculer correctement la taille du bloc de mémoire, de déclarer le bloc de mémoire (avec son effectif type), et comment obtenir des pointeurs vers tous les trois sections de façon portable?

(Je ne comprends que je ne pouvais malloc() 3 blocs, ce qui aurait pour résultat de trois free(), mais j'aimerais savoir comment le faire avec un seul bloc, tandis que toujours bien comportés.)

Je voudrais étendre mon problème à une question plus générale: quelles précautions doit-on prendre pour mettre en œuvre un pool de mémoire pour les objets de dimensions arbitraires et l'alignement tout en gardant le programme comporte bien? (En supposant qu'il est possible de la mettre en œuvre sans avoir recours à un comportement indéfini.)

Answer 1

Cependant dur vous essayez, il n'est pas possible de mettre en oeuvre malloc pure C.

Vous vous retrouvez toujours violer stricte de l'aliasing à un certain point. Pour éviter tout doute, à l'aide d'un char tampon qui n'ont pas la dynamique de stockage durée de violer stricte aliasing règles. Vous devez également avoir à faire en sorte que tout pointeur retourné à un alignement.

Si vous êtes heureux de vous contenter d'une plate-forme particulière, alors vous pouvez aussi bien tourner à la mise en œuvre de l' malloc pour l'inspiration.

Mais pourquoi ne pas envisager la rédaction d'un talon de fonction qui demande malloc et également construit une table des autres objets alloués? Vous pourriez même mettre en place une sorte d'observateur / avertir le cadre. Un autre point de départ pourrait être bien connu ramasseurs d'ordures qui ont été écrits en C.

Answer 2

Comme dit dans une autre réponse, vous ne pouvez pas reproduire malloc au sein de la C lui-même. La raison en est que vous ne pouvez pas générer des objets qui n'ont pas un moyen efficace de type sans malloc.

Mais pour votre application, vous n'en avez pas besoin, vous pouvez utiliser malloc ou similaire, voir ci-dessous, un grand bloc de mémoire sans problèmes.

Si vous en avez un gros bloc, vous devez savoir comment placer les objets à l'intérieur de ce bloc. Le problème majeur ici est de l'alignement, vous devez placer tous vos objets sur les limites qui correspondent à leur minimum les exigences alignement.

Depuis C11, l'alignement des types peuvent être obtenus avec l' _Alignof de l'opérateur, et overaligned mémoire peut être demandé à l' aligned_alloc.

Mettez tout cela ensemble, on peut lire:

• calculer le ppcm de tous les alignements de vos types de
• avec aligned_alloc demande de suffisamment de mémoire qui est aligné sur cette valeur
• placez tous vos objets sur des multiples de l'alignement

Aliasing alors n'est-ce pas un problème si vous êtes débutant avec un sans type d'objet que vous recevez par l'intermédiaire d'un void* pointeur. Chaque partie de ce grand objet a la efficace avec lequel vous avez écrit dans, voir mon récent billet de blog.

La partie pertinente de la norme C est de 6,5 p6:

L'effectif type d'un objet pour un accès à sa valeur stockée est le type déclaré de l'objet, le cas échéant.87) Si une valeur est stockée dans l' un objet ayant pas de déclaration de type à travers une lvalue avoir un type qui n'est pas un type de caractère, alors le type de la lvalue devient le efficace type de l'objet pour que l'accès et pour la suite les accès qui ne modifiez pas la valeur stockée. Si une valeur est copiée dans un objet ayant pas de déclaration de type à l'aide de memcpy ou memmove, ou est copié comme un tableau de caractères, puis l'effet du type de la objet modifié pour que l'accès et pour les demandes d'accès qui ne ne pas modifier la valeur est le type de l'objet à partir duquel la valeur est copiée, si elle en a un. Pour tous les autres accès à un objet ayant pas de déclaration de type, le type de l'objet est tout simplement le type de la lvalue utilisé pour l'accès.

Ici, l'objet "avec pas de déclaration de type" est un objet (ou un sous-objet) alloués par malloc ou similaire. Il est clairement dit que de tels objets peuvent être écrites dans n'importe quel type, à tout moment, et que ce que les changements de la efficace désirée.

Answer 3

Par la connaissance de la taille de l' union des 3 types une répartition plus efficace peut se produire.

union common {
  struct foo f;
  void * ptr;
  char ch;
};

void *allocate3(struct foo **f, size_t m, void **ptr, size_t n, char **ch,
    size_t o) {
  size_t u_sz = sizeof (union common);
  size_t f_sz = sizeof *f * m;
  size_t f_cnt = (f_sz + u_sz - 1)/u_sz;
  size_t p_sz = sizeof *ptr * n;
  size_t p_cnt = (p_sz + u_sz - 1)/u_sz;
  size_t c_sz = sizeof *ch * o;
  size_t c_cnt = (c_sz + u_sz - 1)/u_sz;
  size_t sum = f_cnt + p_cnt + c_cnt;
  union common *u = malloc(sum * u_sz);
  if (u) {
    *f = &u[0].f;
    *ptr = &u[f_cnt].ptr;
    *ch = &u[f_cnt + c_cnt].ch;
  }
  return u;
}

De cette façon, chacun des 3 tableau de commencer sur un union limite , si problèmes d'alignement sont remplies. En ajustant l'espace de chaque tableau doit être un multiple de la taille de l' union, moins de perte d'espace que la première réponse encore satisfait OP posté objectifs.

Un peu de gaspillage est - struct foo est grand, encore o est faible. Pourrait utiliser à la suite de tant d'autres améliorations. Il n'est pas nécessaire pour le remplissage après la dernière tableau.

malloc((f_cnt + p_cnt) * u_sz + c_cz);

---

La poursuite de la réflexion sur la serrant la répartition. Chaque "comte de la union éléments" peuvent utiliser une autre union qui omet les premiers types, et ainsi de suite. En arrivant à la fin qui est l'essentiel de l'idée, juste au-dessus, le dernier tableau ne doit dépendre du dernier type. Cela rend le code plus compliqué (sujettes à l'erreur), mais ne le gain de augmentation de l'efficacité de l'espace sans aliments, etc. Certains de codage des idées à suivre

union common_last2 {
  // struct foo f;
  void * ptr;
  char ch;
};

size_t u2_sz = sizeof (union common_last2);
size_t p_cnt = (p_sz + u2_sz - 1)/u2_sz;

... malloc(f_cnt*usz + p_cnt*u2_sz + c_cz);

*ch = tbd;

Answer 4

Tout d'abord, assurez-vous d'utiliser -fno-strict-aliasing ou quelque soit l'équivalent est sur votre compilateur. Sinon, même si tous les alignements sont satisfaits d'un compilateur peut utiliser des alias règles de chevauchement des différents usages d'un même bloc de mémoire.

Je doute que cela soit cohérent avec l'intention de la Norme auteurs, mais étant donné les optimiseurs peut être si agressif que la seule façon de mettre en œuvre type agnostique pools de mémoire en toute sécurité est de désactiver en fonction de leur type de repliement de l'analyse. Les auteurs de la Norme voulu éviter l'image de marque de non-conformité de certains compilateurs qui ont utilisé le type à base d'aliasing. De plus, ils ont pensé qu'ils pourraient reporter à compilateur des écrivains de jugement sur la façon de reconnaître et de gérer les cas où l'aliasing était probable. Ils ont identifié des cas où les rédacteurs de compilateur ne puisse penser qu'il était nécessaire de reconnaître aliasing (par exemple entre les entiers signés et non signés) mais sinon attend les rédacteurs du compilateur de jugement raisonnable. Je ne vois aucune preuve qu'ils ont préparé leur liste des admissibles cas être considérée comme exhaustive, même sur les plates-formes où d'autres formes d'aliasing serait utile.

De plus, peu importe avec quel soin on se conforme à la Norme, il n'y a aucune garantie que les compilateurs appliquer la rupture "optimisations" de toute façon. À moins que de gcc 6.2 il y a de l'aliasing des bugs qui vont casser le code qui utilise un stockage de type X, écrit sous la forme Y lit il Y, estime que la même valeur de X, et on lit le stockage X--comportement qui est 100% défini dans la Norme.

Si l'aliasing est pris en charge (par exemple, à l'aide de l'indication du drapeau), et vous savez le pire des cas, l'alignement requis pour votre système, la définition de stockage pour la piscine est facile:

union
{
   char [POOL_BLOCK_SIZE] dat;
   TYPE_WITH_WORST_ALIGNMENT align;
} memory_pool[POOL_BLOCK_COUNT];

Malheureusement, la Norme ne fournit aucun moyen pour éviter le type de la base de l'aliasing des problèmes, même si tout dépend de la plateforme problèmes d'alignement sont pris en charge.

Answer 5

Pour répondre à l'une des questions d'OP

comment pourrais-je accomplir cela (je voulais malloc () un bloc comme celui-ci) sans invoquer un comportement indéfini?

Une approche spatiale inefficace . Attribuez un union des types. Raisonnable si la taille nécessaire des petits types n'est pas trop grande.

 union common {
  struct foo f;
  void * ptr;
  char ch;
};

void *allocate3(struct foo **f, size_t m, void **ptr, size_t n, char **ch,
    size_t o) {
  size_t sum = m + n + o;
  union common *u = malloc(sizeof *u * sum);
  if (u) {
    *f = &u[0].f;
    *ptr = &u[m].ptr;
    *ch = &u[m + n].ch;
  }
  return u;
}

void sample() {
  struct foo *f;
  void *ptr;
  char *ch;
  size_t m, n, o;
  void *base = allocate3(&f, m, &ptr, n, &ch, o);
  if (base) {
    // use data
  }
  free(base);
}