Allocation de mémoire pour le noyau

Les Slabs

Pour expliquer le mécanisme d'allocation mémoire, on va directement partir ici du plus haut niveau, c'est à dire un niveau encore au dessus de la couche des slabs. On va considérer qu'un utilisateur/développeur a fait la demande d'allocation d'un objet de taille 10 octets et montrer le cheminement.

Ajout d'un objet

C'est assez simple :

  1. On a une liste de caches de slabs initialisée à différentes tailles croissantes. C'est important pour garantir qu'en itérant à partir du premier cache, on va trouver celui qui nous fasse perdre le moins de place possible (sos/kmalloc.c:16).

    static struct {
  const char             *name;
  sos_size_t             object_size;
  sos_count_t            pages_per_slab;
  struct sos_kslab_cache *cache;
} kmalloc_cache[] =
  {
    { "kmalloc 8B objects",     8,     1  },
    { "kmalloc 16B objects",    16,    1  },
    { "kmalloc 32B objects",    32,    1  },
    { "kmalloc 64B objects",    64,    1  },
    { "kmalloc 128B objects",   128,   1  },
    { "kmalloc 256B objects",   256,   2  },
    { "kmalloc 1024B objects",  1024,  2  },
    { "kmalloc 2048B objects",  2048,  3  },
    { "kmalloc 4096B objects",  4096,  4  },
    { "kmalloc 8192B objects",  8192,  8  },
    { "kmalloc 16384B objects", 16384, 12 },
    { NULL, 0, 0, NULL }
  };

sos_ret_t sos_kmalloc_setup()
{
  int i;
  for (i = 0 ; kmalloc_cache[i].object_size != 0 ; i ++)
    {
      struct sos_kslab_cache *new_cache;
      new_cache = sos_kmem_cache_create(kmalloc_cache[i].name,
					kmalloc_cache[i].object_size,
					kmalloc_cache[i].pages_per_slab,
					0,
					SOS_KSLAB_CREATE_MAP
					);
      SOS_ASSERT_FATAL(new_cache != NULL);
      kmalloc_cache[i].cache = new_cache;
    }
  return SOS_OK;
}

  2. Chacun de ces caches contient une liste de slabs capables de contenir une seule taille d'objets. Lorsqu'on cherche à ajouter un objet, il suffit alors de trouver le cache des slabs de la bonne taille (sos/kmalloc.c:76) :

    for (i = 0 ; kmalloc_cache[i].object_size != 0 ; i ++)
    {
      /* Comme ils sont triés par taille à la création, on 
       * est sûr de perdre le moins de place possible
       */
      if (kmalloc_cache[i].object_size >= size)
	return sos_kmem_cache_alloc(kmalloc_cache[i].cache,
				    (flags
				     & SOS_KMALLOC_ATOMIC)?
				    SOS_KSLAB_ALLOC_ATOMIC:0);
    }
  3. Chaque cache de slabs suit un principe simple : on s'arrange pour trouver le plus rapidement possible le slab qui contient encore de la place. Pour ce faire, on travaille toujours avec le début de la liste chaînée pour ajouter un objet. Si le slab est plein, il est transféré en fin de liste. Si le slab de début de liste n'a aucun objet libre, c'est alors que plus aucun slab n'en a, on en ajoute donc un nouveau (sos/kmem_slab.c:628) :

    Si le slab en tête est plein, on n'a plus rien de libre, on doit agrandir (cache_grow) le cache des slabs.

    if ((! kslab_cache->slab_list)
      || (! list_get_head(kslab_cache->slab_list)->free))
    {
      if (cache_grow(kslab_cache, alloc_flags) != SOS_OK)
	/* Not enough memory or blocking alloc */
	ALLOC_RET( (sos_vaddr_t)NULL);
    }

    Ici, on est certain qu'on a de la place en tête. On peut donc allouer l'objet sans crainte.

    slab_head = list_get_head(kslab_cache->slab_list);
  SOS_ASSERT_FATAL(slab_head != NULL);

  /* Allocate the object at the head of the slab at the head of the
     slabs' list */
  obj_vaddr = (sos_vaddr_t)list_pop_head(slab_head->free);
  slab_head->nb_free --;
  kslab_cache->nb_free_objects --;

  /* If needed, reset object's contents */
  if (kslab_cache->flags & SOS_KSLAB_CREATE_ZERO)
    memset((void*)obj_vaddr, 0x0, kslab_cache->alloc_obj_size);

    Si l'objet qu'on vient d'ajouter était la dernière place disponible, on rajoute un nouveau slab au cache et on déplace le slab plein en fin de liste comme expliqué plus haut.

    if (slab_head->free == NULL)
    {
      /* Transfer it at the tail of the slabs' list */
      struct sos_kslab *slab;
      slab = list_pop_head(kslab_cache->slab_list);
      list_add_tail(kslab_cache->slab_list, slab);
    }

Suppression d'un objet

  1. Depuis l'appel de kfree, on arrive dans free_object (sos/kmem_slab.c:710). On commence par rechercher dans quel slab l'objet est stocké :

    struct sos_kslab *slab = sos_kmem_vmm_resolve_slab(vaddr);

  2. À l'inverse de tout à l'heure, si l'objet à libérer appartient à un slab plein, il faut le déplacer en tête pour continuer à respecter le contrat : les slabs avec de la place se trouvent toujours en tête de liste, alors que ceux en queue sont pleins (ou alors aucun ne l'est).

    if (! slab->free)
    {
      list_delete(kslab_cache->slab_list, slab);
      list_add_head(kslab_cache->slab_list, slab);
    }

  3. On peut supprimer l'objet. On ajoute l'adresse de l'objet à la liste des objets libres du slab et on remet à jour les compteurs (nombre d'objets libres dans le slab, nombre total d'objets libres dans le cache de slabs contenant ce slab).

    Si on est passé en dessous de la limite du nombre d'objets libre dans le slab, on le libère.

    kslab_cache = slab->cache;
[...]
list_add_head(slab->free, (struct sos_kslab_free_object*)vaddr);
  slab->nb_free++;
  kslab_cache->nb_free_objects++;
  SOS_ASSERT_FATAL(slab->nb_free <= slab->cache->nb_objects_per_slab);

  /* Causes the slab to be released if it becomes empty, and if we are
     allowed to do it */
  if ((slab->nb_free >= kslab_cache->nb_objects_per_slab)
      && (kslab_cache->nb_free_objects - slab->nb_free
	  >= kslab_cache->min_free_objects))
    {
      *empty_slab = slab;
    }

  return SOS_OK;