Le copy-on-write

S’il est une chose souvent louée concernant Docker c’est bien sa légèreté. L’utilisateur peut en effet s’étonner du peu de mémoire que consomme un container et de la rapidité du lancement de celui-ci. Ces performances sont dues à un procédé très astucieux: le copy-on-write (que nous appellerons CoW).

L’idée théorique est telle: partant du principe qu’une ressource partagée en lecture n’a pas besoin d’exister en plusieurs exemplaires, il est plus intéressant de la copier seulement si elle venait à être modifiée.

Nous nous intéresserons dans cet article à l’utilisation du CoW au sein de la gestion de la mémoire de fork() via le kernel Linux. A noter que c’est un procédé qui trouve sa place parmi de multiples applications, par exemple en base données pour les transactions ou bien au sein du système de fichier Btrfs (qui parviendra peut-être un jour à remplacer ext4…).

Petit rappel sur la mémoire virtuelle (Linux)

Un programme a la sensation d’être seul possesseur de l’espace mémoire disponible. Les adresses mémoires utilisées par ce programme sont dites virtuelles, de taille dépendantes de l’architecture (32 ou 64 bits en général), elles correspondent à une entrée dans une table qui les lie à une adresse physique (par exemple dans la RAM mais aussi sur disque). Ces tables sont gérées par le MMU (pour Memory Management Unit, un composant du CPU qui stocke ses tables en cache avec l’aide du Translation Lookaside Buffer ou TLB), qui fait donc de la translation d’adresses virtuelles à physiques.

Deux zones de mémoire virtuelles contiguës peuvent tout à fait correspondre à deux zones de mémoires physique espacées. De ce fait, deux programmes ne partagent pas les mêmes zones de mémoire, puisque l’adresse x dans la mémoire virtuelle de ces programmes ne correspond pas à l’adresse x dans la mémoire physique.

Je parle de zone de mémoire puisque la mémoire physique est en réalité représentée par bloc que l’on appelle des pages (en général de 4096 octets, tout dépend de l’architecture du processeur).

Si une demande de translation est faite pour une adresse virtuelle qui ne correspond à aucune entrée dans la table du MMU, il y a alors un page-fault et celui-ci avertit le kernel qui doit gérer plusieurs cas possibles:

  • Le programme n’a pas accès à la zone mémoire souhaitée et un SIGSEGV est envoyé au processus (segmentation fault)
  • L’adresse correspond à une zone de la RAM compressée nommée le zswap, le kernel s’occupe alors de récupérer la page dans cette zone, de la décompresser, de la mettre dans la mémoire physique et enfin de mettre à jour le MMU ou bien l’adresse correspond à une zone du disque, le procédé est le même sans la decompression
  • L’adresse est valide mais le programme n’a pas la permission nécessaire pour écrire, le kernel s’occupe de créer un duplicata de la page et met à jour le MMU

Le cas de fork()

L’appel à fork() créé un processus enfant et ce de manière instantanée, indépendamment de la taille que peut prendre en mémoire le processus père. L’explication est simple, les pages de la section data, heap et stack de ce dernier ne sont pas dupliquées mais partagées en lecture avec une protection en écriture. Ainsi, les entrées de ces pages dans la table du processus fils correspondent aux entrées des adresses de mémoire physique des pages dans la table du processus père. Un compteur de référence des entrées de page est associé à la page. Si l’un des processus vient à écrire sur ces pages, il y a un minor page fault (voir plus haut), le kernel est prévenu par le MMU (qui suspend alors le processus) et alloue une nouvelle page physique, copie le contenu de la page partagée dans cette nouvelle page, attache la nouvelle page à la table de page, marque cette page comme possédant un droit d’écriture et décrémente le compteur de référence de la page.

Chacun des processus peut donc modifier sa propre copie privée de la page et ce sans risquer d’altérer une zone mémoire qui ne lui est pas destinée.

Le CoW est notamment utile dans le cas où un processus fils fait directement appel à execve (ce qui est très souvent le cas, par exemple lorsque l’utilisateur utilise la commande ls). Cet appel remplace les sections data, heap et stack du processus fils, il est donc inutile de les avoir copiées au préalable.

La commande strace permet de visualiser les appels systèmes réalisés lors de l’exécution de la commande donnée en argument, ici ls.

L’implémentation de fork() au sein du kernel v5.5.9

Le fork() est géré par le fichier /kernel/fork.c

Son observation nous informe d’entrée de jeu que la gestion de la mémoire lors d’un fork() se fait (non sans mal) au sein de /mm/memory.c

/*
 *  'fork.c' contains the help-routines for the 'fork' system call
 * (see also entry.S and others).
 * Fork is rather simple, once you get the hang of it, but the memory
 * management can be a bitch. See 'mm/memory.c': 'copy_page_range()'
 */

Nous n’allons pas nous rendre dans ce fichier directement, mais plutôt suivre des pistes en commençant par fork.c

L’appel système fork est défini dans /kernel/fork.c

#ifdef __ARCH_WANT_SYS_FORK
SYSCALL_DEFINE0(fork)
{
#ifdef CONFIG_MMU
        struct kernel_clone_args args = {
                .exit_signal = SIGCHLD,
        };

        return _do_fork(&args);
#else
        /* can not support in nommu mode */
        return -EINVAL;
#endif
}
#endif

La fonction _do_fork() est la routine principale du fork évoquée dans le commentaire plus haut.

long _do_fork(struct kernel_clone_args *args)
{
	…
	p = copy_process(NULL, trace, NUMA_NO_NODE, args);
	…
}

Elle fait appel à une fonction copy_process() qui va initialiser le partage du processus.

C’est une très longue fonction de 529 lignes. Heureusement, nous n’avons qu’à nous intéresser à copy_mm()

static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
{
	struct mm_struct *mm, *oldmm;
      int retval;
	…
	mm = dup_mm(tsk, current->mm);
}

mm_struct (mm pour main memory) est une structure représentant un descripteur de mémoire et donc un espace d’adresses pour un processus donné. Elle contient (entre autres):

  • Une sous-structure mmap (memory map) contenant une liste de zone de mémoire virtuelle, ou vma (voir plus bas)
  • struct rb_root mm_rb: un arbre rouge-noir contenant aussi les vma, pour un accès rapide
  • pgd_t * pgd : un pointeur sur le Page Global Directory (spécifique à l’architecture du processeur)
  • int map_count : un compteur de vma
  • struct mm_rss_stat rss_stat: la taille résidente (RSS)

L’idée est ici de copier (ou du moins initialiser la procédure de copie) un mm_struct. On remarque qu’en argument doit être passé une task_struct et pas une mm_struct comme l’on pourrait s’y attendre, c’est tout simplement que chaque task_struct (une sorte de descripteur de processus) possède un pointeur vers un mm_struct.

copy_mm() fait appel à dup_mm(), qui permet donc de dupliquer une mm_struct en appelant dup_mmap().

static struct mm_struct *dup_mm(struct task_struct *tsk,
                                struct mm_struct *oldmm)
{
	...
	err = dup_mmap(mm, oldmm);
	...
}

dup_mmap() itère sur les structures de données du kernel Linux représentant les régions de mémoires du processus parent: mmaps, stack et heap donc.

static __latent_entropy int dup_mmap(struct mm_struct *mm,
                                        struct mm_struct *oldmm)
{
	…
	for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
		...
		tmp = vm_area_dup(mpnt) ;
		…
		*pprev = tmp;
		pprev = &tmp->vm_next;
            tmp->vm_prev = prev;
            
		prev = tmp;
		...
		mm->map_count++;
		if (!(tmp->vm_flags & VM_WIPEONFORK))
      		retval = copy_page_range(mm, oldmm, mpnt);
		…
	}
   ...
}

Enfin, dup_mmap() appelle copy_page_range() qui se trouve donc dans /mm/memory.c

int copy_page_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
                struct vm_area_struct *vma)
{ ... }

On observe la familière mm_struct, pour la destination et pour la source.

En revanche, vm_area_struct est nouvelle. C’est une structure représentant une zone de mémoire virtuelle. Elle contient notamment:

  • unsigned long vm_start et vm_end : des pointeurs pour le début et la fin de la zone
  • Des structures de données pour la manipuler efficacement
  • pgprot_t vm_page_prot : le bit de protection de la page
  • vm_file : de quel fichier elle provient (si aucun, elle est anonyme)
  • const struct vm_operations_struct *vm_ops : un pointeur vers les fonctions de gestions de cette page (comme le page-fault!)
  • unsigned long vm_flags : son flag (lié au bitmask)
if (is_cow) {
	mmu_notifier_range_init(&range, MMU_NOTIFY_PROTECTION_PAGE,
                                0, vma, src_mm, addr, end);
	mmu_notifier_invalidate_range_start(&range);
}
…
if (is_cow)
	mmu_notifier_invalidate_range_end(&range);

On constate qu’une notification relative au CoW est faite au MMU, ce n’est pas réellement ce qui nous intéresse, mais plus d’informations peuvent être trouvées ici.

Il existe de multiples notifications, MMU_NOTIFY_PROTECTION_PAGE concerne les pages sur lesquelles une protection en lecture/ecriture existe.

Plus intéressant, on trouve au sein de cette fonction une variable bool is_cow; utilisée pour différencier les pages CoW (il me semble que selon l’OS, ce procédé peut prendre une forme différente).

/*
 * We need to invalidate the secondary MMU mappings only when
 * there could be a permission downgrade on the ptes of the
 * parent mm. And a permission downgrade will only happen if
 * is_cow_mapping() returns true.
 */
is_cow = is_cow_mapping(vma->vm_flags);

Pour se faire, une fonction de test du flag de la zone de mémoire virtuelle est utilisée, présente dans /mm/internal.h

static inline bool is_cow_mapping(vm_flags_t flags)
{
        return (flags & (VM_SHARED | VM_MAYWRITE)) == VM_MAYWRITE;
}
#define VM_SHARED       0x00000008
#define VM_MAYWRITE     0x00000020

Il existe une multitude de flag basé sur des bitmasks, mais celui qui nous intéresse doit donc être de type «partagé et une potentielle écriture peut avoir lieu». L’ensemble des bitmasks se trouve dans /include/linux/mm.h

Plusieurs fonctions de copie s’appellent ensuite l’une après l’autre. Elles permettent d’itérer sur les différents niveaux de directory d’une page table. Nous avons précédemment rencontré le PGD, pointé par la mm_struct. Ces directory différent en fonction des architectures, pouvant aller jusqu’à 5.

On a donc :

Au bout du chemin, c’est copy_one_pte() qui est appelée (pte pour Page Table Entry). C’est cette fonction qui va s’occuper de copier une vma dans une autre et de mettre à jour le compteur de références.

static inline unsigned long
copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,
		pte_t *dst_pte, pte_t *src_pte, struct vm_area_struct *vma,
		unsigned long addr, int *rss)
{
   ...
	/*
	 * If it's a COW mapping, write protect it both
	 * in the parent and the child
	 */
	if (is_cow_mapping(vm_flags) && pte_write(pte)) {
		ptep_set_wrprotect(src_mm, addr, src_pte);
		pte = pte_wrprotect(pte);
	}
   ...
}

On retrouve une opération propre à la gestion d’un CoW, comme le fait que le père et le fils ont une protection en écriture.

Fiou ! Nous avons donc pu observer comment été géré la mémoire aprés un fork(). Il nous reste à chercher comment est géré le page-fault lors d’une écriture forcée. Nous n’aurons pas à aller bien loin, c’est encore une fois dans /mm/memory.c

Le point d’entrée est la fonction handle_pte_fault() qui determine quel type de faute cause le page-fault (et est invoquée peu importe l’architecture sur laquelle tourne le kernel).

static vm_fault_t handle_pte_fault(struct vm_fault *vmf)
{
...
if (vmf->flags & FAULT_FLAG_WRITE) {
                if (!pte_write(entry))
                        return do_wp_page(vmf);
                entry = pte_mkdirty(entry);
        }
...
}

Après avoir vérifie que l’erreur a été faite sur une page bien présente en mémoire, il appelle la fonction do_wp_page()

static vm_fault_t do_wp_page(struct vm_fault *vmf)
        __releases(vmf->ptl)
{
     struct vm_area_struct *vma = vmf->vma;

     vmf->page = vm_normal_page(vma, vmf->address, vmf->orig_pte);
     if (!vmf->page) {
          /*
           * VM_MIXEDMAP !pfn_valid() case, or VM_SOFTDIRTY clear on a
           * VM_PFNMAP VMA.
           *
           * We should not cow pages in a shared writeable mapping.
           * Just mark the pages writable and/or call ops->pfn_mkwrite.
           */
          if ((vma->vm_flags & (VM_WRITE|VM_SHARED)) ==
                                     (VM_WRITE|VM_SHARED))
                  return wp_pfn_shared(vmf);

          pte_unmap_unlock(vmf->pte, vmf->ptl);
          return wp_page_copy(vmf);
        }
	...
}

Celle-ci détermine si la page doit vraiment être dupliquée en suivant le CoW. Pour se faire elle fait appel à vm_normal_page() qui renvoie une structure de page associée à une pte : si celle-ci est spéciale (comme une CoW), elle renvoie NULL.

Une fois qu’elle a vérifié que la page NULL correspond bien au CoW et pas à un autre type de page spéciale, elle appelle la fonction wp_page_copy(). Celle-ci s’occupe du plus gros du travail, à savoir d’allouer une page, de copier l’ancienne page sur celle-ci, de notifier le MMU, de modifier les pte… En somme tout ce qui a été expliqué en amont et qui est très bien documenté au sein de la fonction !

Nous en avons fait le tour, ce fut long et fastidieux et d’autant plus impressionnant de se dire que tout ceci se passe en une fraction de temps lorsqu’on utilise son ordinateur. Le kernel est décidément une formidable machinerie.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

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