la fonction malloc de la mise en œuvre?

Je suis en train de mettre en œuvre malloc et free pour le C, et je ne suis pas sûr de la façon de réutiliser la mémoire. J'ai actuellement un struct qui ressemble à ceci:

typedef struct _mem_dictionary {
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;

Mon malloc ressemble à ceci:

void *malloc(size_t size) {
    void *return_ptr = sbrk(size);
    if (dictionary == NULL) 
        dictionary = sbrk(1024 * sizeof(mem_dictionary));

    dictionary[dictionary_ct].addr = return_ptr;
    dictionary[dictionary_ct].size = size;
    dictionary[dictionary_ct].freed = 1;
    dictionary_ct++;

    return return_ptr;
}

Quand j'ai de la mémoire libre, je voudrais juste marquer l'adresse 0 (qui indique que c'est gratuit). Dans mon malloc, je puis utiliser une boucle for pour rechercher une valeur dans le tableau de l'égalité des 0, et ensuite d'allouer de la mémoire à cette adresse. Je suis un peu confus comment le mettre en œuvre.

Il y a un bel article sur dlmalloc ici: g.oswego.edu/dl/html/malloc.html

InformationsquelleAutor user675257 | 2011-03-24

c free malloc memory-management

22

La façon la plus simple de le faire est de garder une liste chaînée de blocs. Dans malloc, si la liste n'est pas vide, vous recherchez un bloc assez grand pour satisfaire la demande et le retourner. Si la liste est vide ou si un tel bloc peut être trouvé, vous appelez sbrk d'allouer de la mémoire à partir du système d'exploitation. dans free, il vous suffit d'ajouter de la mémoire de morceau à la liste de bloc libre. En bonus, vous pouvez essayer de fusionner contiguë bloc libéré, et vous pouvez modifier la stratégie pour le choix du bloc de retour (premier ajustement, ajustement optimal, ...). Vous pouvez également choisir de partager la bloquer si elle est plus grande que la demande.

Quelques exemples de mise en œuvre (il n'est pas testé et il est évidemment pas thread-safe, utilisez à vos risques et périls):
```
typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };
static const size_t overhead = sizeof(size_t);
static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(size_t);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(size_t);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}
```
Remarque: (n + align_to - 1) & ~ (align_to - 1) est une astuce pour arrondir n au plus proche multiple de align_to qui est plus grande que n. Cela ne fonctionne que lorsque align_to est une puissance de deux et dépend de la représentation binaire des nombres.

Quand align_to est une puissance de deux, il n'a qu'un ensemble de bits, et donc align_to - 1 a tous le bit de poids faible de jeux (ie. align_to est de la forme 010 000......0, et align_to - 1 est de la forme 000...001...1). Cela signifie que ~ (align_to - 1) a l'ensemble de la haute ensemble de bits, et de la faible peu unset (ie. il est de la forme 111...110...0). Donc x & ~ (align_to - 1) sera mis à zéro tous les les bits de poids faible de x et autour d'elle jusqu'à la plus proche multiple de align_to.

Enfin, l'ajout de align_to - 1 à size de nous assurer de round-up au plus proche multiple de align_to (sauf size est déjà un multiple de align_to dans ce cas, nous voulons obtenir size).
- ce qui fait la magie de la première ligne de la fonction de malloc faire?
- Il arrondit (size + sizeof(size_t)) au plus proche multiple de align_to qui est plus grande que (size + sizeof(size_t)). Cela ne fonctionne que si align_to est une puissance de deux.
- Une technique similaire de l'aide d'une liste liée cache pour conserver la mémoire allouée (au lieu d'affectation de tout recommencer) pour accélérer un programme graphique (qui est de passer trop de temps sur malloc) est utilisé comme exemple dans la première partie de la Colonne 9: Code de Réglage dans le livre de Programmation Perles par Jon Bentley. Le livre, malheureusement, ne contient pas de code dans son exemple, afin de voir le code comme ceci a été particulièrement utile pour moi.
InformationsquelleAutor Sylvain Defresne
8

Vous ne souhaitez pas définir la size champ de l'entrée du dictionnaire de zéro, vous aurez besoin de cette information pour les ré-utiliser. Au lieu de cela, définir freed=1 uniquement lorsque le bloc est libéré.

Vous ne pouvez pas fusionner deux blocs adjacents, car il peut y avoir intervenant appels à sbrk(), de sorte que rend cela plus facile. Vous avez juste besoin d'un for boucle qui recherche un assez grand bloc libéré:
```
typedef struct _mem_dictionary
{
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;


void *malloc(size_t size)
{
     void *return_ptr = NULL;
     int i;

     if (dictionary == NULL) {
         dictionary = sbrk(1024 * sizeof(mem_dictionary));
         memset(dictionary, 0, 1024 * sizeof(mem_dictionary));
     }

     for (i = 0; i < dictionary_ct; i++)
         if (dictionary[i].size >= size
          && dictionary[i].freed)
     {
         dictionary[i].freed = 0;
         return dictionary[i].addr;
     }

     return_ptr = sbrk(size);

     dictionary[dictionary_ct].addr = return_ptr;
     dictionary[dictionary_ct].size = size;
     dictionary[dictionary_ct].freed = 0;
     dictionary_ct++;

     return return_ptr;
}

void free(void *ptr)
{
    int i;

    if (!dictionary)
        return;

    for (i = 0; i < dictionary_ct; i++ )
    {
        if (dictionary[i].addr == ptr)
        {
            dictionary[i].freed = 1;
            return;
        }
    }
}
```
Ce n'est pas un grand malloc() mise en œuvre. En fait, la plupart des malloc/free implémentations d'allouer un petit en-tête de chaque bloc retourné par malloc. L'en-tête peut débuter à l'adresse de huit (8) octets moins que le pointeur retourné, par exemple. Dans ces octets que vous pouvez stocker un pointeur vers le mem_dictionary entrée de posséder le bloc. Cela évite de O(N) opérations en free. Vous pouvez éviter le O(N) dans malloc() par la mise en œuvre d'une file d'attente de priorité de blocs libérés. Envisager l'utilisation d'un binôme tas, avec une taille de bloc que l'index.
- Désolé, je suis relativement nouveau à C, mais qu'est-ce que le dictionnaire de la variable dans la fonction malloc()?
- Je doit avoir nommé que le "journal" au lieu de "le dictionnaire." Rappelez-vous, c'est mon exemple et trivial de mise en œuvre de malloc. Il a au moins un défaut évident: il ne peut jamais être supérieure à 1024 blocs attribués à un moment donné. Le seul but de donner cet exemple est de donner au lecteur un point de départ pour la mise en œuvre de leurs propres malloc. C'est juste une base conceptuelle pour la mise en œuvre d'un malloc/free de la bibliothèque. Il ne prend même pas la mettre en œuvre realloc une insuffisance éclatante. Il pourrait même ne pas être le meilleur exemple. 🙂
InformationsquelleAutor Heath Hunnicutt
5

Je suis d'emprunt code de Sylvain réponse. Il semble avoir manqué le calcul de la taille de la free_block* ini calcul de la surcharge.

Dans l'ensemble du code en ajoutant cette free_block comme en-tête de la mémoire allouée.
1. Lorsque l'utilisateur appelle la fonction malloc, malloc renvoie l'adresse de la charge utile, juste après cet en-tête.
2. quand free est appelé, l'adresse de départ de l'en-tête du bloc est calculée (en soustrayant la taille d'en-tête à partir du bloc d'adresse, et qui est ajouté au bloc libre de la piscine.
```
typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };

//static const size_t overhead = sizeof(size_t);

static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(free_block);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block ));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}
```
- Merci, je pense que cette réponse est un peu plus correct que celui de Sylvain réponse, car je me demandais juste à ce sujet. La surcharge variable est une très bonne idée, tout simplement pas calculés correctement ou même utilisé.
- Quelqu'un peut me dire l'utilisation de la tête en fonction de malloc? (free_block** head = &(free_block_list_head.next);) Je ne le vois pas être utilisé n'importe où. En outre, pourquoi le faisons-nous ajouter sizeof(free_block) avant de revenir?
- head est un pointeur vers une adresse contenant un pointeur. Il est utilisé dans la boucle permettant de dissocier le bloc de mémoire est retourné à l'utilisateur. L'addition et la soustraction sizeof(free_block) est une commune et astuce pour "masquer" les métadonnées de l'appelant.
- Il y a aussi une petite erreur dans le free() la mise en œuvre free(NULL) sera erreur de segmentation.
- Sylvain utilise sizeof(size_t) au lieu de sizeof(free_block), parce que le "prochain" pointeur est utilisé uniquement dans les blocs libérés, sinon, il peut être remplacé par l'utilisateur.
- Bonjour, pouvez-vous ajouter adapté realloc fonction de cette mise en œuvre?
InformationsquelleAutor Kingkong Jnr

Vous devez vous connecter pour publier un commentaire.