[ad_1]
Nous avons récemment découvert un bogue étrange au plus profond de la dernière version de la plateforme IoT Thingsquare qui nous a pris par surprise.
La cause profonde s’est avérée être que le rand() fonction appelée la malloc() une fonction. Nous avons été surpris par cela.
Et maintenant, nous voulons passer le mot, pour que tout le monde sache : rand() peut – sous certaines conditions – appeler malloc().
Qu’est-ce que cela signifie pour la personne moyenne?
Pour la plupart des gens, pas grand-chose.
En fait, même la plupart des développeurs de logiciels ne seront pas affectés par cela.
Mais cela nous a touchés.
Ce dont nous parlons ici est de très bas niveau. Très nu-métal. Bien plus bare-metal que la plupart des développeurs de logiciels ne le seront jamais.
Mais plongeons-y.
La plate-forme IoT Thingsquare fonctionne sur des appareils dotés d’une quantité de mémoire ridiculement petite.
L’allocation de mémoire est un défi
La plate-forme IoT Thingsquare s’exécute sur des appareils dotés de petites quantités de mémoire.
Très petit.
Parfois aussi petit que 10 kilo-octets. Et parfois, nous pouvons faire des folies avec jusqu’à 32 kilo-octets.
Pour la plupart des usages modernes, c’est ridiculement petit.
Il faut donc être très malin dans la gestion de cette mémoire.
Dans le système Thingsquare, nous avons trois types différents de mécanismes d’allocation de mémoire :
- membre: l’allocateur de bloc mémoire. Blocs de taille fixe à partir de pools statiques de blocs.
- mmem: l’allocateur de mémoire managé. Blocs de taille dynamique, qui peuvent être réorganisés pour éviter la fragmentation, à partir d’un bloc de mémoire statique.
- bmem: l’allocateur de tas de mémoire de bloc. Blocs de taille dynamique à partir d’un bloc de mémoire statique.
Et, comme le système est écrit en langage de programmation C, nous utilisons également la mémoire de la pile.
Tout ce qui précède est basé sur un principe :
Toujours pré-allouer tout au moment de la compilation.
Cela signifie que nous savons, à l’avance, combien de mémoire est utilisée. Si nous en utilisons trop, nous ne pourrons même pas compiler le code. Encore moins le courir.
Nous nous retrouvons avec une structure de mémoire qui ressemble à ceci :
La pile commence au sommet de la mémoire et grandit vers le bas. Mais nous devons être prudents – plus à ce sujet ci-dessous.
La pile est suivie d’un ensemble de blocs memb, mmem et bmem. Ainsi que d’autres données que le code utilise.
Parce que la mémoire est si serrée, il n’y a pas beaucoup d’air dans cette disposition de la mémoire. Dans la plupart des cas, il est presque utilisé à 100 %.
malloc() pourrait vous tuer
Notez qu’il existe un mécanisme d’allocation de mémoire qui est ne pas dans la liste ci-dessus : le standard du langage C malloc()/free() mécanisme.
Pourquoi?
Parce qu’avec malloc()/free()nous ne savons pas à l’avance combien de mémoire sera utilisée.
Nous pouvons finir par en utiliser plus que prévu, lors de l’exécution. Et puis, il sera peut-être trop tard. L’appareil est peut-être déjà mort.
Nos appareils sont déployés dans des endroits difficiles d’accès. Ils doivent être toujours disponibles. Nous ne pouvons pas nous permettre de manquer de mémoire au moment où nous nous y attendons le moins.
En fait, nous nous efforçons d’éviter toute surprise.
Nous avons une configuration de test approfondie, que nous exécutons à chaque changement de code. Cela implique d’exécuter le système dans un ensemble de simulateurs de réseau, afin que nous puissions savoir avec certitude que le système fonctionne comme prévu. Et pendant la fabrication, nous effectuons des tests de production pour nous assurer que le matériel fonctionne.
Nous ne pouvons donc pas utiliser malloc()/free(). Et nous ne le faisons pas.
La pile ne joue pas bien
Dans la disposition de la mémoire, la pile est un gros morceau. Comment savons-nous combien allouer à la pile ?
La mémoire de la pile est quelque peu délicate à allouer, car sa taille maximale est déterminée au moment de l’exécution.
Il n’y a pas de solution miracle : nous ne pouvons pas le prévoir. Il faut donc le mesurer.
La façon dont nous procédons est simple : au démarrage, nous remplissons la mémoire de la pile avec un modèle d’octet connu. Nous exécutons ensuite le système. Le système utilisera la pile. Cela écrasera ce modèle d’octets.
Après avoir fait fonctionner le système pendant un certain temps, nous vérifions la quantité de ce modèle d’octets qui reste. Cela nous donne une idée de la quantité de pile utilisée par le système.
Nous allouons alors un peu plus de mémoire de pile que ce dont nous pensons avoir besoin. Être en sécurité.
Mais il nous reste une astuce : nous pouvons continuer à mesurer ce modèle d’octets, même lorsque des appareils sont déployés.
Ce bogue
Donc, tout cela mène à ce bogue surprenant sur lequel nous sommes tombés.
Nous avons constaté que certains appareils, sur le terrain, utilisaient plus de pile que nous ne l’avions supposé. Et c’était étrange. Parce que nous nous étions vraiment assurés que la taille de la pile était bonne.
Cela a fait que l’appareil s’est comporté étrangement. Imprévisible.
Alors que se passait-il ?
Nous avons examiné de plus près l’un des appareils, en laboratoire.
Nous avons ajouté plus d’endroits dans le code où nous avons mesuré l’utilisation de la pile. Pour essayer de cibler la partie du code qui a provoqué le débordement.
Et nous l’avons trouvé :
rand();Hein?
Oui, la fonction standard de la bibliothèque C qui produit des nombres pseudo-aléatoires.
Cela a provoqué un débordement de la pile.
Nous utilisons rand() à quelques endroits dans le code, où nous avons besoin d’un nombre pseudo-aléatoire rapide qui n’a pas besoin d’être cryptographiquement sûr.
C’est une fonction simple qui ne devrait pas utiliser beaucoup de pile.
Alors pourquoi débordait-il de la pile ?
Le coupable : rand()
Le système Thingsquare utilise la bibliothèque C standard newlib. C’est open source, nous pouvons donc regarder le code.
C’est le code du rand() fonction, qui semble familière:
int
rand_r (unsigned int *seed)
{
long k;
long s = (long)(*seed);
if (s == 0)
s = 0x12345987;
k = s / 127773;
s = 16807 * (s - k * 127773) - 2836 * k;
if (s < 0)
s += 2147483647;
(*seed) = (unsigned int)s;
return (int)(s & RAND_MAX);
}Pourquoi ce code utiliserait-il tellement de pile qu’il dépasserait ses limites ?
Il n’y a pas de grands tableaux ou structures alloués sur la pile.
Il n’y a pas de récursivité.
Mais attendez! C’est rand_r()ne pas rand(). Nous regardons le mauvais code. Parce que nous cherchions quelque chose qui nous semblait familier.
Le problème n’est donc pas dans ce code. Creusons plus profondément.
La bibliothèque newlib a une couche de réentrance qui permet d’appeler des fonctions plusieurs fois, simultanément.
Et ce code de réentrance est implémenté avec des macros C. C’est difficile à comprendre d’un premier coup d’œil. C’est ainsi que le réel rand() la fonction ressemble:
int
rand (void)
{
struct _reent *reent = _REENT;
/* This multiplier was obtained from Knuth, D.E., "The Art of
Computer Programming," Vol 2, Seminumerical Algorithms, Third
Edition, Addison-Wesley, 1998, p. 106 (line 26) & p. 108 */
_REENT_CHECK_RAND48(reent);
_REENT_RAND_NEXT(reent) =
_REENT_RAND_NEXT(reent) * __extension__ 6364136223846793005LL + 1;
return (int)((_REENT_RAND_NEXT(reent) >> 32) & RAND_MAX);
}Peut-être que ces appels sont le problème?
Et, oui, il s’avère qu’ils le sont.
Au fond de ça _REENT_CHECK_RAND48() macro, on trouve :
/* Generic _REENT check macro. */
#define _REENT_CHECK(var, what, type, size, init) do { \
struct _reent *_r = (var); \
if (_r->what == NULL) { \
_r->what = (type)malloc(size); \
__reent_assert(_r->what); \
init; \
} \
} while (0)Oups – un malloc()! Cette fonction tueuse que nous voulions éviter.
Mais est-ce vraiment utilisé ?
Oui, en regardant le code compilé, on voit que malloc() être appelé:
0001ff80 <rand>:
1ff80: 4b16 ldr r3, [pc, #88] ; (1ffdc <rand+0x5c>)
1ff82: b510 push {r4, lr}
1ff84: 681c ldr r4, [r3, #0]
1ff86: 6ba3 ldr r3, [r4, #56] ; 0x38
1ff88: b9b3 cbnz r3, 1ffb8 <rand+0x38>
1ff8a: 2018 movs r0, #24
1ff8c: f7ff fee4 bl 1fd58 <malloc>
1ff90: 4602 mov r2, r0
1ff92: 63a0 str r0, [r4, #56] ; 0x38
1ff94: b920 cbnz r0, 1ffa0 <rand+0x20>
1ff96: 4b12 ldr r3, [pc, #72] ; (1ffe0 <rand+0x60>)
1ff98: 4812 ldr r0, [pc, #72] ; (1ffe4 <rand+0x64>)
1ff9a: 214e movs r1, #78 ; 0x4e
1ff9c: f000 f952 bl 20244 <__assert_func>
1ffa0: 4911 ldr r1, [pc, #68] ; (1ffe8 <rand+0x68>)
1ffa2: 4b12 ldr r3, [pc, #72] ; (1ffec <rand+0x6c>)
1ffa4: e9c0 1300 strd r1, r3, [r0]
1ffa8: 4b11 ldr r3, [pc, #68] ; (1fff0 <rand+0x70>)
1ffaa: 6083 str r3, [r0, #8]
1ffac: 230b movs r3, #11
1ffae: 8183 strh r3, [r0, #12]
1ffb0: 2100 movs r1, #0
1ffb2: 2001 movs r0, #1
1ffb4: e9c2 0104 strd r0, r1, [r2, #16]
1ffb8: 6ba4 ldr r4, [r4, #56] ; 0x38
1ffba: 4a0e ldr r2, [pc, #56] ; (1fff4 <rand+0x74>)
1ffbc: 6920 ldr r0, [r4, #16]
1ffbe: 6963 ldr r3, [r4, #20]
1ffc0: 490d ldr r1, [pc, #52] ; (1fff8 <rand+0x78>)
1ffc2: 4342 muls r2, r0
1ffc4: fb01 2203 mla r2, r1, r3, r2
1ffc8: fba0 0101 umull r0, r1, r0, r1
1ffcc: 1c43 adds r3, r0, #1
1ffce: eb42 0001 adc.w r0, r2, r1
1ffd2: e9c4 3004 strd r3, r0, [r4, #16]
1ffd6: f020 4000 bic.w r0, r0, #2147483648 ; 0x80000000
1ffda: bd10 pop {r4, pc}
1ffdc: 20000770 .word 0x20000770
1ffe0: 00027bfc .word 0x00027bfc
1ffe4: 00027c13 .word 0x00027c13
1ffe8: abcd330e .word 0xabcd330e
1ffec: e66d1234 .word 0xe66d1234
1fff0: 0005deec .word 0x0005deec
1fff4: 5851f42d .word 0x5851f42d
1fff8: 4c957f2d .word 0x4c957f2d
Pour réaliser la réentrance, le code newlib utilise malloc() pour allouer l’état pour son caractère aléatoire, de sorte qu’il puisse être appelé plusieurs fois.
Juste ce que nous voulions éviter.
Mais pourquoi malloc() entraîner l’explosion de la pile ?
Parce que malloc(), dans son implémentation par défaut, utilise de la mémoire entre l’octet alloué le plus élevé et la pile. Dans la plupart des cas, pour les grands systèmes, cela convient. Parce qu’il y a beaucoup de mémoire libre entre l’octet alloué le plus élevé et la pile.
Mais pas dans notre cas.
Nous n’avons pas beaucoup de mémoire libre. Alors cet appel à malloc() va interférer avec la pile, immédiatement.
Et heureusement, nous avons pu le trouver en surveillant la pile.
Mais pourquoi est-ce arrivé maintenant ? Nous utilisons ce code depuis des années sans aucun problème. Il s’avère que la raison en est que nous avons récemment mis à jour la version arm-gcc. Et cette version a sa newlib construite avec le support de la réentrance, ce que les versions précédentes n’avaient pas.
La solution?
Heureusement, la solution est simple.
Nous arrêtons simplement d’utiliser rand().
Au lieu de cela, nous fournissons notre propre fonction pseudo-aléatoire. Par exemple, le PCG générateur de nombres aléatoires.
De plus, nous avons ajouté un autre test de régression qui vérifie explicitement les occurrences du malloc() code dans les binaires générés.