Implémentation d'une boucle d'attente précise au cycle près en C++ pour un système embarqué

Lors d'un récent travail sur le firmware de l'imprimante Marlin, j'ai trouvé une pull request en attente concernant l'attente de délais précis, idéalement de l'ordre de la nanoseconde. Alors que cela semblait facile à première vue, l'implémentation s'est avérée délicate. Ce billet explique les difficultés et les détails de l'implémentation.

Nombreuses plateformes

Marlin est un firmware qui cible de nombreuses plateformes (du CPU AVR, à l'ARM Cortex M0, Cortex M3, Cortex M4, Cortex M7, ESP32, AMD64...). Implémenter une boucle de retard commune à toutes ces plateformes est presque impossible.

Je me suis donc concentré sur la plateforme ARM uniquement.

Même dans ce cas, le nombre de plates-formes implique de nombreux comportements temporels différents, en raison de :

  1. Un nombre de cycle incohérent selon la plateforme (alors que les Cortex M0 et M0+ ont un nombre de cycle fixe par instruction, les Cortex M3/M4/M7 sont pipelinés et prédisent les branchements).
  2. Incohérence matérielle réelle (les STM32 récupèrent leurs instructions directement à partir de la Flash, avec une pénalité de 5 cycles, à moins qu'elles ne soient chargées dans le cache d'instructions).
  3. Présence d'un compteur de cycles matériel (non requis pour le Cortex M0)

Voici les liens permettant de calculer le nombre de cycles pour un processeur Cortex nu. L'implémentation réelle sera différente de ces liens (à cause de la pénalité pour la recherche d'instructions dans la Flash ou la RAM externe, etc...) :

  • Cortex M0
  • Cortex M3
  • Cortex M4
  • Cortex M7, il semble que si l'assemblage est en mode Thumb, le nombre de cycles devrait être plus ou moins le même que pour M4. Sinon, il n'est pas possible de calculer le nombre de cycles des instructions.

Description d'une solution idéale

Passons à l'univers de Wonderprinter pour une seconde. Dans cet univers, le souhait du premier Lanterne arc-en-ciel était d'avoir un délai d'exactement 182ns avant d'être activé, puis un délai d'exactement 34ns avant d'être désactivé. Dans cet univers, la physique est simple. Le Grand Maître CPU exécute exactement une instruction par cycle et peut fonctionner à une vitesse d'horloge infinie sans consommer un seul watt d'énergie.

Le méchant Entropyman rôde malheureusement dans les parages et est attiré par l'innocent CPU qui va trop vite comme les mouches à fruits sont attirées par la marmelade. À quelle vitesse le Grand Maître CPU doit-il aller pour atteindre la lanterne arc-en-ciel sans attirer l'Entropyman ?

La réponse évidente est que la période d'horloge doit être égale au PGCD des deux retards (dans ce monde, c'est 2ns). Ainsi, le Grand Maître CPU doit être cadencé à 1/2µs = 500MHz.

Il comptera alors 91 cycles avant d'activer la Lanterne arc-en-ciel, puis 17 cycles avant de désactiver la Lanterne de l'arc-en-ciel.

Malheureusement, le maléfique Entropyman est très sensible à ces hautes fréquences, et, pour des raisons de sécurité car je ne veux pas trahir les enfants qui lisent cette histoire avec de la violence et des images d'horreur, tout ce qui est au-dessus de 84 MHz attirera le méchant aussi sûrement que le sucre attire les fourmis et les caries.

Avec une fréquence aussi basse, chaque cycle du Grand Maître CPU utilisera 1/84MHz ou 11.9ns. Cela signifie que la Lanterne Arc-en-ciel devra accepter une petite déviation de ses souhaits, puisque le mieux que l'on puisse faire sera 178,5ns pour le temps fort (15 cycles), et 35,7ns (avec 3 cycles de retard).

Et pourtant. et pourtant...

Le Grand Maître CPU ne connaît pas à l'avance les souhaits de la Lanterne Arc-en-ciel. Lorsque la lanterne arc-en-ciel décide de son nouveau souhait, le Grand Maître CPU doit calculer le nombre de cycles à attendre, et il doit interrompre ce qu'il était en train de faire pour exaucer les rêves de la jolie lanterne. Cela prend également quelques cycles.

Dans cet univers, le Grand Maître CPU peut demander aux petits nains de calculer le nombre de cycles à sa place, de sorte qu'il ne passe pas son temps précieux à effectuer des calculs ennuyeux. Pourtant, ces satanées créatures administratives refusent de s'occuper d'une valeur portée par le vent, elles ne commencent à travailler que lorsque la valeur est écrite dans un livre, sinon elles se mettent en grève (elles ont moitié de sang français, moitié de sang magique).

Ils disent qu'une valeur parlée peut changer pendant que le flux est en train de s'écouler, alors qu'une valeur écrite ne change jamais.

Le Grand Maître CPU est réticent à accepter une telle condition dans son intégralité, il décide donc d'accepter la solution en partie. Si la valeur est écrite dans un livre, petit nain effectuera un précalcul. Sinon, il prendra le temps de la calculer lui-même. Comme il sait combien de temps prend un tel calcul, il demande alors à la Lanterne Arc-en-ciel de ne jamais lui dire un souhait oral inférieur à son temps de calcul.

Pourtant. pourtant...

Le Grand Maître CPU se fait vieux maintenant, et l'interruption de son travail prend plus de temps que dans son enfance. Il doit maintenant fermer le livre sur lequel il travaillait, ouvrir un autre livre pour compter les cycles, puis le refermer une fois qu'il a terminé... pour rouvrir le livre précédent. Il se demande si une peur mystique ne pourrait pas lui permettre d'éviter ce délai de commutation. Il s'avère que Mz Inline Intrinsics connaît une vieille formule magique qui fait exactement cela.

Back to our universe...

Description technique du besoin

Nous voulons une solution qui :

  1. Attende le cycle le plus proche du délai demandé
  2. N'attende pas plus que le délai demandé (par exemple, si le CPU est interrompu, il ne doit pas s'attarder)
  3. Peut attendre entre un seul cycle à quelques microsecondes (si vous avez besoin de plus, n'attirez pas Entropyman, vous feriez mieux d'utiliser une minuterie matérielle pour cela).
  4. Utilise sur un timer matériel chaque fois que cela est possible
  5. Idéalement, le code ne doit pas être modifié à la main pour chaque plate-forme.
  6. Idéalement, pas d'étalonnage manuel de chaque plate-forme et pas de base de données sur le cycle par instruction
  7. Qui peut être maintenue facilement

En termes de couche de langage, nous aimerions que le compilateur écrive ceci (pseudo-assemblage) :

main :
   [previous_code()]
   nop
   nop
   nop
   nop
   nop
   [quelque_autre_chose()]
   call cycle_wait(210)

à partir d'une telle source :

int main() {
    previous_code() ;
    DELAY_CYCLES(5) ; // Ou DELAY_NS(65)
    quelque_autre_chose() ;
    DELAY_CYCLES(210) ;
}   

Solution pour cette énigme

Comme Marlin est écrit en C++, notre petit nain dort dans le compilateur et attend de faire des calculs au moment de la compilation.

Lorsque le code appelle une fonction DELAY, il y a 2 possibilités. Soit l'argument de la fonction est connu à la compilation, soit c'est une variable runtime. Dans ce dernier cas, nous passerons à une fonction qui compte simplement les cycles. Idéalement, nous devons savoir combien de cycles sont gaspillés en sautant et en revenant à cette fonction et le soustraire au compte de la fonction.

Dans le premier cas, nous avons besoin que notre petit nain calcule le nombre de cycles à attendre et qu'il insère, en grognant, autant de cycles endormis qu'il en trouve dans notre flux d'instructions actuel. Nous ne voulons pas qu'il appelle une autre fonction, car cela ajouterait des cycles non désirés pour entrer et revenir. Cependant, nous devons toujours le surveiller, car il est parfois stupide et nous ne voulons pas qu'il insère trop de cycles de sommeil. Au lieu de cela, nous lui demanderons de remplacer tous ces cycles par un appel à une fonction de boucle lorsque le nombre de cycles endormis est supérieur au coût d'appel de la fonction de boucle.

Attendez...

Vous avez dit que chaque plateforme est différente, comment gérez-vous ces différences ?

L'étalonnage est le mot clé. Au démarrage, le système utilise une minuterie (imprécise) pour mesurer un retard important dans le comptage des cycles. Une fois que c'est fait, déterminer les bizarreries de la plate-forme est un problème mathématique qui est stocké dans une variable statique. Laissons l'imprimante faire les calculs pour nous, afin de ne pas avoir à maintenir une base de données de valeurs qui pourraient évoluer avec la version du compilateur ou le niveau d'optimisation.

Comment écrire "sleepy cycle" en C++ à partir d'une variable de compilation ?

Il y a un truc de basse qualité et un truc de haute qualité. L'astuce de basse qualité est d'avoir un tas de cas de commutation comme ceci :

switch(cycle_count) {
    case 10 : sleepy_cycle() ; // Pas de break ici
    case 9 : sleepy_cycle() ;
        ...
    case 1 : sleepy_cycle() ;
    case 0 : break ;
}

Si le compilateur n'est pas trop stupide, il générera un tableau d'instructions sleepy_cycle et sautera au milieu du tableau en fonction du cycle_count demandé. C'est le cas.

Cependant, cette solution n'est pas très amusante, parce que vous devez écrire autant de switch case que vous pensez que l'overhead de la fonction boucle va prendre (sur mon imprimante, c'est ~ 40 cycles, mais c'est différent pour n'importe quelle imprimante). Supposons que vous ayez une nouvelle imprimante avec un CPU de 4THz qui a besoin de 400 cycles pour appeler une fonction ? C'est vrai, vous devez mettre à jour votre code à la main ou il se cassera à nouveau. De plus, il ne s'agit pas d'une function, elle doit être écrite à l'intérieur d'une fonction (via une macro), vous aurez donc toujours le surcoût de l'appel à cette fonction à prendre en compte.

L'astuce de haute qualité est cependant bien meilleure et moins verbeuse :

template <int N> struct SleepCycleWriter 
{
  inline static void sleep() { sleepy_cycle(); SleepCycleWriter<N-1>::sleep(); }
};

// Terminer la récursion par une fonction vide
template <> struct SleepCycleWriter<0> { inline static void sleep() {} };

Ici, chaque fois que vous instanciez SleepCycleWriter<N>::sleep(), le compilateur émet récursivement N sleepy_cycle(). Vous avez besoin de 400 cycles ? Pas de problème.

Aucun appel de fonction n'est nécessaire, puisque toutes les fonctions sleep() sont inline.

Ok, tout semble bien se passer maintenant. Mais comment savoir si une variable est une variable de compilation ou d'exécution ? Comment agir différemment ?

En C++ (version 2014 utilisée par Marlin), il n'est pas possible de réagir différemment à la compilation ou à l'exécution... à moins d'utiliser un tas d'astuces non standard. En effet, une variable à la compilation peut être utilisée dans un paramètre de template, mais une variable à l'exécution ne le peut pas. Ceci est du C++ incorrect :

int x = 10 ; SleepCycleWrite<x>::sleep();

Donc, à moins de faire cette mocheté:

switch (cycle_count) { case 10 : SleepCycleWriter<10>::sleep(); break; ...}

Il n'existe pas de solution optimale standard (même en C++20... pour l'instant).

Pour résoudre ce problème, je m'appuie sur une extension du compilateur (appelée __builtin_constant_p). Ce symbole magique vérifie si le paramètre donné est une constante à la compilation (un constexpr en termes de gourou du C++) mais n'échoue pas si ce n'est pas le cas (contrairement à if constexpr en C++17 et plus).

Il fournit aussi un avantage appréciable, lorsqu'il est utilisé comme ceci :

constexpr int o = __builtin_constant_p(count) ? count : 0;

Dans ce cas précis, je construis une expression constante (une valeur à la compilation) à partir d'une valeur possible à l'exécution : c'est le nombre donné si le nombre est une valeur à la compilation ou la constante 0.

La magie réside dans la partie ? count ici, puisque si count n'est pas une valeur constante à la compilation, l'opérande n'est pas évalué et ne génère pas d'erreur de compilation (contrairement à l'instruction if constexpr).

Après cela, tout est assez simple, o est une valeur à la compilation qui peut être utilisée dans le paramètre du template. Nous avons juste besoin de spécialiser un template sur ce paramètre pour que s'il vaut 0 (ou -1 ou autre, il faut juste être cohérent ici), nous revenions à un appel de la fonction de boucle au moment de l'exécution.

Résultats

Eh bien, tout se résume aux résultats de toute façon. Pourquoi s'embêter avec tout ce bazar s'il ne donne pas d'excellents résultats ?

En fait, c'est le cas :

L'appel direct de la macro DELAY_CYCLES pour 1cycles a pris : 1cycles
L'appel direct de la macro DELAY_CYCLES pour 5cycles a pris : 5cycles
L'appel direct de la macro DELAY_CYCLES pour 10cycles a pris : 11cycles
L'appel direct de la macro DELAY_CYCLES pour 20cycles a pris : 20cycles
L'appel direct de la macro DELAY_CYCLES pour 50cycles a pris : 49cycles
L'appel direct de la macro DELAY_CYCLES pour 100cycles a pris : 102cycles
L'appel direct de la macro DELAY_CYCLES pour 200cycles a pris : 207cycles
L'appel direct de la macro DELAY_CYCLES pour 500cycles a pris : 497cycles

Moins d'un cycle d'erreur pour un petit délai et moins de 7 cycles d'erreur pour un grand délai.

Vous pouvez le constater par vous-même dans ce godbolt

Article précédent

Articles en relation