Vous devez savoir : rand() peut appeler malloc()

Actualités de de l'Intelligence Artificielle - Machine Learning - Objets connectés

Vous devez savoir : rand() peut appeler malloc()


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.

Disposition de la mémoire

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.

Utilisation de la pile

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.