(C) comment un tas allocateur traiter un en-tête de bloc de 4 octets, alors que seulement les adresses de retour qui sont des multiples de 8?
https://stackoverflow.com/questions/2947085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Il ne semble pas logique, à moins que nous ne négligeons aucun espace excédentaire potentiel au début d'un segment, et ensuite le premier morceau alloué soit au premier multiple de 8 (avec son premier en-tête correspondant étant cette adresse -4). Cela laisserait toutefois d'octets avant que inutilisés. Est-ce que ce qui est généralement fait?
modifier grâce à paxdiablo pour l'explication détaillée ci-dessous. que tous les sens pour les en-têtes de 16 octets. cependant, je travaille avec un en-tête de 4 octets, qui ressemble à quelque chose comme ceci:
struct mhdr {
int size; // size of this block
} tMallocHdr;
maintenant, si mes mises en tas sur une adresse qui est un multiple de 8, et une adresse de retour par les besoins malloc pour être un multiple de 8, et je dois utiliser 4 têtes d'octets, il me semble être forcé de « déchets «les 4 premiers octets de mon tas. par exemple:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
^
(heap starts)
Si le tas commence à la carotte ci-dessus à l'adresse 8, en utilisant le schéma d'adressage dans cet exemple, la première adresse retournable i pourrait revenir à un utilisateur suite à un appel de malloc serait 16; i besoin de 4 octets d'en-tête, et la première adresse qui est un multiple de 8 octets qui permet d'en-tête 4 est de 16 (en-tête commence à 12). Cela signifie que j'ai perdu les 4 premiers octets de ma mémoire de tas interne aux choses de la ligne vers le haut (8-11).
Est-ce un sacrifice acceptable, ou suis-je penser à ce mal?
La solution
Généralement, il espace perdu dans un en-tête de bloc d'une région allouée. De nombreuses implémentations je l'ai utilisé vu un 16 octets (j'utilise la définition classique de l'octet ici, l'un des huit bits, plutôt que la définition ISO C) en-tête, immédiatement avant l'adresse de retour de malloc, et le tampon alloué région de 16 octets à la fin aussi bien.
très simplifie les algorithmes utilisés pour l'allocation et garantit également que les adresses de mémoire retournées seront alignées de façon appropriée pour l'architecture.
Mais gardez à l'esprit que ceci est un détail de mise en œuvre, et non pas une caractéristique de la norme C. S'il n'y a aucune exigence d'alignement et les allocations de mémoire sont limités à 255 octets, il est tout à fait plausible qu'un seul octet sera gaspillé (mais au détriment d'un algorithme plus compliqué).
Il est tout à fait plausible que vous pourriez avoir une application embarquée qui n'alloue toujours des morceaux de 256 octets dans ce cas, vous pourriez avoir simple allocateur base bitmap (avec le bitmap stocké ailleurs plutôt que en ligne avec les blocs de mémoire étant alloués ), perdre un seul bit par morceau (nous avons fait auparavant dans des environnements peu de mémoire).
Ou vous avez peut-être un allocateur dans un grand environnement et l'espace d'adressage mémoire qui vous donne 4G, peu importe ce que vous demandez. Ensuite, il y a pas de gaspillage pour un en-tête, mais probablement beaucoup pour le rembourrage: -)
Ou peut-être vous obtenez un morceau d'une arène spécifique de taille (1-64 octets de domaine A, 65-128 de l'arène B et ainsi de suite). Cela signifie pas de tête requis, mais en permettant la taille variable (jusqu'à un maximum) et le gaspillage sensiblement inférieure à la solution 4G ci-dessus.
En bout de ligne, cela dépend de la mise en œuvre.
Dans un (assez simple) la mise en œuvre de malloc, vous pourriez avoir une liste doublement chaînée des « morceaux » qui sont donnés par l'allocateur. Ces morceaux sont constitués d'un en-tête et une section de données et, pour assurer l'alignement de la section de données est correct, l'en-tête doit être sur une limite de 16 octets et être un multiple de 16 octets de longueur (qui est pour une exigence d'alignement de 16 octets - votre exigence réelle peut ne pas être que sévère)
En outre, le bloc lui-même est rembourré de sorte qu'il est un multiple de 16 octets de sorte que le segment suivant est convenablement aligné aussi bien.
qui garantit que la section de données d'un morceau, qui est l'adresse indiquée à l'appelant de malloc, est aligné correctement.
Alors, vous pouvez bien obtenir le gaspillage dans ce domaine. Un en-tête (avec des entiers et des pointeurs de 4 octets) peut être simplement:
struct mhdr {
int size; // size of this block.
struct mhdr *prev; // prev chunk.
struct mhdr *next; // next chunk.
int junk; // for padding.
} tMallocHdr;
ce qui signifie que quatre de ces seize octets seront gaspillés. Parfois, ce qui est nécessaire pour répondre aux autres exigences (alignement) et, en tout cas, vous pouvez utiliser cet espace de remplissage pour d'autres fins. Comme un commentateur a fait remarquer, les octets de garde peuvent être utilisés pour détecter certaines formes de corruption arène:
struct mhdr {
int guard_bytes; // set to 0xdeadbeef to detect some corruptions.
int size; // size of this block.
struct mhdr *prev; // prev chunk.
struct mhdr *next; // next chunk.
} tMallocHdr;
Et, alors que le rembourrage est techniquement espace gaspillé, il ne devient important si elle est une proportion non négligeable de l'ensemble arène. Si vous allouer des blocs de 4k de mémoire, les quatre octets de gaspillage est seulement environ un millième de la taille totale. En fait, le gaspillage pour vous en tant qu'utilisateur est probablement les 16 octets entiers de l'en-tête depuis sa mémoire, vous ne pouvez pas utiliser, il est donc environ 0,39% (16 / (4096 + 16)).
C'est pourquoi une liste chaînée malloc de caractères est une très mauvaise idée - vous avez tendance à utiliser, pour chaque caractère:
- 16 octets d'en-tête.
- 1 octet pour le caractère (en supposant que les caractères de 8 bits).
- 15 octets de remplissage.
Ceci changerait votre chiffre de 0,39% dans les pertes de 96,9% (31 / (31 + 1)).
Et, en réponse à votre autre question:
Est-ce un sacrifice acceptable, ou suis-je penser à ce mal?
Je dirais que oui, cela est acceptable. En général, vous tousocate plus gros morceaux de mémoire où quatre octets ne faire une différence dans le grand schéma des choses. Comme je l'ai dit plus tôt, ce n'est pas une bonne solution si vous allouez beaucoup de petites choses, mais ce n'est pas le cas d'utilisation générale de malloc.
Autres conseils
Certains ne pas allocateurs les en-têtes pour les blocs attribués. Certains en-têtes pour éliminer les petits blocs. Il n'y a pas besoin d'en-têtes pour les blocs attribués à tous les autres que pour la sécurité. Ceci peut être réalisé par d'autres moyens, par exemple par des données administratives séparées physiquement complètement à partir de la mémoire allouée.
Répartiteurs mémoire Même tapées peuvent éliminer les en-têtes. Voir par exemple BIBOP .
Vous trouverez probablement que si les blocs retournés sont toujours alignés sur une limite de 8 octets, la mise en œuvre utilise un bloc de 8 octets pour stocker les informations de contrôle. Je crois que la mise en œuvre K & R (les deux première et deuxième éditions) fait cela. En effet, il utilise un pointeur et une taille, il dispose de 8 octets d'informations de contrôle. Et si elle utilise des blocs alignés 8 octets, il n'y a pas de pénalité réelle pour le faire. (Avec les machines 64 bits, le plus alignement rigoureux pourrait être de 16 octets - il est sur SPARC, par exemple -. Et le bloc est donc un peu plus frais généraux, mais pour essentiellement la même raison)
