in , , ,

0x04 – L’Allocation Dynamique

Cet article fait parti de la série Créer un système d'exploitation pour Raspberry Pi ( 5 / 5 )

Afin d’allouer plus de mémoire que 4Kb, nous avons besoin d’allouer de la memoire en premier lieu! Puisque nous sommes le noyau, nous sommes le patron. Nous pouvons réserver la mémoire directement après les métadonnées de la page et la réserver pour notre pile de données . La taille à réserver est quelque peu arbitraire, donc nous choisissons 1 Mo parce que c’est assez spatieux pour être suffisant pour les besoins de la mémoire dynamique du noyau, et assez petit pour qu’il n’utilise pas une partie significatif de la mémoire que le code utilisateur pourrait utiliser.

Maintenant que nous avons une partie de la mémoire, tout ce dont nous avons besoin est une fonction pour la diviser! Nous allons exposer l’interface familière void * malloc (uint32_t octets)  dans les fichiers src/kernel/mem.c  et include/kernel/mem.h . Nous allons associer chaque allocation à un en-tête. Les en-têtes formeront une liste chaînée, afin que nous puissions facilement parcourir à partir du début d’une allocation à l’autre. Il comprendra également une taille, et si l’allocation est actuellement en cours d’utilisation. Voici la définition de la structure d’en-tête:

typedef struct heap_segment{
    struct heap_segment * next;
    struct heap_segment * prev;
    uint32_t is_allocated;
    uint32_t segment_size;  // Includes this header
} heap_segment_t;

Pour attribuer la mémoire, tout ce que nous devons faire est de trouver l’allocation qui correspond le mieux au nombre d’octets demandés et qui n’est pas utilisé. Si cette allocation est très importante, nous pouvons diviser cette allocation en deux plus petites, et n’utiliser que l’une d’entre elles. Le critère que nous avons utilisé pour déterminer si une allocation doit être fractionnée est si l’allocation est au moins deux fois la taille d’un en-tête. Une fois que nous avons une allocation, nous retournons un pointeur vers la mémoire directement après l’en-tête. Voici le code:

void * kmalloc(uint32_t bytes) {
    heap_segment_t * curr, *best = NULL;
    int diff, best_diff = 0x7fffffff; // Max signed int

    // Add the header to the number of bytes we need and make the size 16 byte aligned
    bytes += sizeof(heap_segment_t);
    bytes += bytes % 16 ? 16 - (bytes % 16) : 0;

    // Find the allocation that is closest in size to this request
    for (curr = heap_segment_list_head; curr != NULL; curr = curr->next) {
        diff = curr->segment_size - bytes;
        if (!curr->is_allocated && diff < best_diff && diff >= 0) {
            best = curr;
            best_diff = diff;
        }
    }

    // There must be no free memory right now :(
    if (best == NULL)
        return NULL;

    // If the best difference we could come up with was large, split up this segment into two.
    // Since our segment headers are rather large, the criterion for splitting the segment is that
    // when split, the segment not being requested should be twice a header size
    if (best_diff > (int)(2 * sizeof(heap_segment_t))) {
        bzero(((void*)(best)) + bytes, sizeof(heap_segment_t));
        curr = best->next;
        best->next = ((void*)(best)) + bytes;
        best->next->next = curr;
        best->next->prev = best;
        best->next->segment_size = best->segment_size - bytes;
        best->segment_size = bytes;
    }

    best->is_allocated = 1;

    return best + 1;
}

Libérer la mémoire

Maintenant que nous avons malloc , naturellement nous avons besoin de free  afin que nous ne remplissions pas notre 1 Mo avec des données qui ne seront plus utilisées. De toute évidence, nous devons marquer les allocations inutilisées, de sorte qu’un autre appel à malloc  pourra réattribuer. En outre, nous devons fusionner les allocations libres adjacentes en une seule. Voici le code:

void kfree(void *ptr) {
    heap_segment_t * seg = ptr - sizeof(heap_segment_t);
    seg->is_allocated = 0;

    // try to coalesce segements to the left
    while(seg->prev != NULL && !seg->prev->is_allocated) {
        seg->prev->next = seg->next;
        seg->prev->segment_size += seg->segment_size;
        seg = seg->prev;
    }
    // try to coalesce segments to the right
    while(seg->next != NULL && !seg->next->is_allocated) {
        seg->segment_size += seg->next->segment_size;
        seg->next = seg->next->next;
    }
}

Initialiser le stack

Maintenant que nous avons les algorithmes pour attribuer et libérer, nous devons initialiser le stack. Pour cela, nous devons réserver les pages que nous allons utiliser, mettre un en-tête au début de notre allocation de 1 Mo qui indique qu’il y a une allocation inutilisée de 1 Mo, et assigner heap_segment_list_head  à cet en-tête. Enfin, nous devons appeler cette fonction d’initialisation dans kernel_main . Voici le code:

static heap_segment_t * heap_segment_list_head;

void mem_init(void) {
    ...
    kernel_pages = ((uint32_t)&__end) / PAGE_SIZE;
    for (i = 0; i < kernel_pages; i++) {
        all_pages_array[i].vaddr_mapped = i * PAGE_SIZE;    // Identity map the kernel pages
        all_pages_array[i].flags.allocated = 1;
        all_pages_array[i].flags.kernel_page = 1;
    }
    // Reserve 1 MB for the kernel heap
    for(; i < kernel_pages + (KERNEL_HEAP_SIZE / PAGE_SIZE); i++){
        all_pages_array[i].vaddr_mapped = i * PAGE_SIZE;    // Identity map the kernel pages
        all_pages_array[i].flags.allocated = 1;
        all_pages_array[i].flags.kernel_heap_page = 1;
    }
    // Map the rest of the pages as unallocated, and add them to the free list
    for(; i < num_pages; i++){
        all_pages_array[i].flags.allocated = 0;
        append_page_list(&free_pages, &all_pages_array[i]);
    }


    // Initialize the heap
    page_array_end = (uint32_t)&__end + page_array_len;
    heap_init(page_array_end)    
}

static void heap_init(uint32_t heap_start) {
    heap_segment_list_head = (heap_segment_t *) heap_start;
    bzero(heap_segment_list_head, sizeof(heap_segment_t));
    heap_segment_list_head->segment_size = KERNEL_HEAP_SIZE;
}

Le code est publiquement disponible sur GitHub.

Navigation<< 0x03 – La mémoire

What do you think?

23 points
Upvote Downvote

commentaires

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Chargement & hellip;

Orange : l’opérateur de l’année

Google supprime «Kodi» des suggestions de recherche