Un serveur Minecraft créé à partir de zéro avec Bash (2022)

 (sdomi.pl)
4 points par GN⁺ 2024-03-04 | 1 commentaires | Partager sur WhatsApp
  • Witchcraft est un projet expérimental qui implémente un serveur Minecraft à partir de zéro uniquement avec Bash. Il couvre le protocole binaire, Join Game et même l’envoi de chunks, avec pour objectif de permettre la connexion d’un vrai client.
  • La limite de Bash, qui ne peut pas conserver les octets nuls dans les chaînes, est contournée en ne stockant pas le binaire dans des variables, mais en le traitant dans des pipelines dd et xxd.
  • Les difficultés d’implémentation se sont concentrées sur les formats de données propres à Minecraft, comme VarInt/VarLong, les flottants IEEE 754, Position et NBT. La conversion des Double était particulièrement lente à cause du coût des appels à des commandes externes.
  • Le serveur a été étendu dans l’ordre suivant : Server List Ping, handshake, Join Game, puis paquets Chunk Data And Update Light. Le Dimension codec utilise un blob binaire NBT récupéré depuis un serveur vanilla.
  • Des plugins à base de hooks permettent de modifier la génération du monde et les effets, mais il reste des limites : multijoueur inachevé, communication entre threads basée sur /dev/shm/witchcraft, échanges de données lents et dépendance à BusyBox 1.35.0.

Gérer le protocole Minecraft binaire avec Bash

  • Les premières tentatives visaient le Classic protocol de 2009, mais la difficulté de parser correctement des données binaires avec Bash est apparue avant tout.
  • Les chaînes Bash ignorent les octets nuls (0x00) et il n’existe aucun moyen de détecter leur présence, ce qui peut corrompre les données dans un protocole binaire strict.
  • Le contournement consiste à garder les données binaires dans le pipeline, sans les placer dans des variables Bash ni dans des substitutions de commande.
    • dd count=$len bs=1 status=none | xxd -p lit le nombre d’octets nécessaire et les convertit en chaîne hexadécimale.
    • La correspondance de motifs, les substitutions et l’extraction de données sont effectuées sur la chaîne hexadécimale.
    • Pour envoyer une réponse, l’option reverse de xxd reconvertit le tout en binaire.
  • Pour accepter les connexions sur le port TCP par défaut de Minecraft, ncat est utilisé ; lorsqu’une connexion arrive, le script shell principal mc.sh est exécuté.

Implémentation des types de données du protocole

  • Le premier paquet le plus simple à implémenter est Server List Ping.
    • Ce n’est pas un paquet obligatoire : même si le serveur ne répond pas correctement, la connexion au jeu reste possible.
    • Il permet toutefois de se familiariser facilement avec des concepts essentiels du protocole, comme les types de données.

  • VarInt et VarLong

    • Les VarInt/VarLong de Minecraft sont une variante de LEB128, qui peut être familière aux personnes ayant déjà travaillé avec MQTT.
    • LEB128 est une méthode de compression qui stocke la longueur d’un entier en divisant les octets en 1 bit de signal et 7 bits de données.
    • Si le premier bit vaut 0, l’octet courant est le dernier ; s’il vaut 1, un autre octet suit.
    • Comme il était difficile de transposer telle quelle l’implémentation de référence en Bash, un encodeur maison a été écrit avec modulo et division.
    • Le décodeur est implémenté de façon proche de la référence, avec des opérations AND et des multiplications.
    • Plus que LEB128 lui-même, ce qui s’est révélé pénible est sa présence un peu partout dans le protocole, mêlé à des int, long et signed short classiques.

  • Flottants IEEE 754

    • La conversion des Double IEEE 754 a été l’une des parties les plus agaçantes de l’implémentation.
    • Une implémentation de base nécessite une boucle appliquant des puissances négatives, mais Bash ne prend pas en charge nativement les puissances négatives.
    • Perl a été évité, et bc semblait ne pas prendre en charge les puissances dans l’environnement d’utilisation ou avec la version de BusyBox concernée.
    • awk pouvant traiter des puissances négatives comme 2**-1, il a été utilisé pour implémenter la conversion.
    • L’implémentation initiale était si lente qu’il fallait plusieurs minutes pour traiter environ 50 à 100 paquets envoyés par le client dans les paquets Player Move, chacun contenant trois Double X, Y et Z.
    • La structure appelait awk à répétition dans une boucle Bash for ; la boucle a été déplacée à l’intérieur de awk afin de réduire le nombre d’appels à des commandes externes.
    • La conversion est ensuite descendue à environ 10 ms sur un Xeon E5-2680v2.
    • Le chiffre d’environ 350 ms pour la version précédente n’est pas une mesure certaine.

  • Type de données Position

    • Position est un type de données basé sur un Long 64 bits créé par Mojang.
    • X est stocké dans les 26 bits de poids fort, Z dans les 26 bits du milieu et Y dans les 12 bits de poids faible.
    • Bash dispose des opérateurs de bitshift nécessaires, ce qui a rendu l’implémentation simple.
    • Ce type est toutefois peu utilisé, et beaucoup de paquets stockent les coordonnées X, Y et Z comme valeurs Double séparées.
    • Résultat : les données de position passent de 64 bits à 192 bits par paquet.
    • En supposant que seules les valeurs jusqu’à la world border par défaut de 30 000 000 soient nécessaires, on obtient une précision de flottant à 9 chiffres.
    • Les communications serveur classiques utilisent zlib, et il est considéré qu’une précision supérieure à 2 ou 3 décimales n’est pas vraiment nécessaire pour représenter une position à l’intérieur d’un bloc.

  • NBT

    • NBT est un format interne de Mojang, comparable à JSON pour les données binaires.
    • Comme JSON, il est aussi utilisé pour stocker des données arbitraires hors spécification.
    • Mojang stocke par exemple des bitstreams de longueur variable sous forme de tableaux de Long.
    • Si le tableau n’est pas aligné sur des Long ou des octets, le dernier Long est complété par des zéros.
    • Un parseur NBT avait été presque achevé, mais il a été jugé inutile d’aller jusqu’au bout.
    • Ce code a été perdu lors d’un crash système, à une période où le projet utilisait beaucoup tmpfs comme répertoire de travail.

Créer un serveur auquel on peut se connecter

  • Après Server Ping, l’étape suivante consistait à gérer le handshake et les paquets supplémentaires nécessaires à une vraie connexion au jeu.
  • Pour qu’un client entre sur le serveur, il doit terminer le handshake et recevoir les paquets liés aux chunks, à la position du joueur, à l’inventaire et à Join Game.
  • Les plus gros obstacles étaient le paquet Join Game et les structures de données internes des paquets Chunk.

  • Join Game

    • Le paquet Join Game transmet les métadonnées initiales.
    • Il contient l’entity ID du joueur, le gamemode, les informations liées au monde et le Dimension codec, apparu autour de Minecraft 1.16.
    • Le Dimension codec étant un NBT Compound, il représentait une charge d’implémentation importante.
    • Witchcraft utilise ce champ NBT récupéré depuis un serveur vanilla.
    • C’est le seul blob binaire de l’implémentation ; il serait possible de le réimplémenter, mais il a été jugé inutile de le personnaliser.

  • Chunk Data And Update Light

    • Le paquet Chunk Data And Update Light paraît d’abord gros et complexe, mais il devient simple si l’on met plusieurs champs BitSet à 0x00 et que l’on n’envoie pas le champ Block Entity.
    • Les champs restants sont X, Y, heightmaps et Data.
    • Les heightmaps sont une forme plus complexe d’encodage d’une répétition de b000000010, et il est considéré qu’en pratique elles peuvent valoir à peu près n’importe quoi.

Gestion des Chunk Sections et des palettes

  • Le champ Data est un tableau de Chunk Sections.
  • Une Chunk Section correspond à 16×16×16 blocs, et plusieurs sections peuvent être empilées pour former un Chunk.
  • Pour simplifier l’implémentation, ce tableau n’utilise qu’un seul élément.
  • Une Chunk Section se compose d’un block count, d’un block states container et d’un biome container.
  • Les block states et le biome container utilisent une structure de palette.
    • Avant les données de blocs proprement dites, le serveur doit définir la correspondance entre local block ID et global block ID.
    • Cette structure sert à faire tenir un maximum de données dans un minimum d’espace.
    • Les définitions de blocs peuvent descendre jusqu’à 4 bits.
  • Pour faciliter la gestion, Witchcraft utilise 8 bits per block au lieu du minimum de 4 bits.
    • Cela donne 256 entrées de palette disponibles.
    • Les données réelles du chunk peuvent alors être envoyées sous forme de nombres hexadécimaux pointant vers des entrées de palette.
    • Une palette 4 bits est elle aussi facile à manipuler dans une chaîne hexadécimale, puisqu’un octet peut représenter deux blocs, mais elle limite à 16 blocs par chunk.
  • Le standard autorise de 4 bits per block à 9 bits per block ; toute autre valeur est considérée comme un direct palette mapping en 15 bits per block.
  • La palette des biomes est traitée séparément.
    • Une palette vide est envoyée, et le biome ID 0x01, c’est-à-dire minecraft:plains, est directement mappé à toutes les régions du chunk.
    • Cela repose sur le résultat d’une rétro-ingénierie du comportement vanilla.
    • La documentation existante de cette partie du paquet est soupçonnée d’être inexacte.

Structure de plugins à base de hooks et démos

  • Comme l’implémentation de base n’affiche que des chunks ordinaires, il fallait une démo montrant que le serveur pouvait faire plus qu’afficher des chunks.
  • Pour éviter de créer une arborescence de sources séparée pour chaque démo, des fonctions surchargeables ont été appelées hooks, et le serveur peut charger du code utilisateur.
  • Cette structure permet d’aller de la modification de la forme du monde à la connexion de pkt_effect, afin que le joueur émette un ticking noise lorsqu’il bouge la souris.
  • Un plugin d’exemple génère un chunk en choisissant des blocs aléatoires dans la palette par défaut.
    • hook_chunks() appelle chunk_header.
    • Pour les 4096 blocs, il ajoute en hexadécimal la valeur RANDOM%30.
    • Le chunk généré est enregistré dans $TEMP/world/0000000000000000.
    • Plusieurs appels à pkt_chunk sur les coordonnées alentour envoient les chunks.
  • Une autre démo, digmeout, est un petit jeu basé sur le score.
    • Le joueur est placé dans un chunk contenant des pierres et minerais disposés aléatoirement.
    • Le but est de miner les minerais les plus précieux avant la fin du temps imparti.

Limites de Witchcraft

  • Bash gère très mal les nombres décimaux.
    • Les entiers sont assez bien pris en charge.
    • Les décimaux doivent être traités en multipliant à l’entrée, puis en plaçant le point au bon endroit à la sortie.
    • De ce fait, la plupart, voire la totalité, des nombres traités par Witchcraft sont des int.
  • Le multijoueur ne fonctionne pas correctement.
    • Il fonctionne dans une certaine mesure, mais aucun temps n’a été consacré à le terminer ou à le peaufiner.
  • Witchcraft est techniquement un serveur multi-threaded.
    • Cela impose un hack peu élégant pour la communication entre threads.
    • La plupart des données globales sont stockées sous /dev/shm/witchcraft et référencées en interne via $TEMP.
  • Les performances restent une forte contrainte.
    • Les échanges de données entre plusieurs threads sont particulièrement lents.
    • Il est difficile d’envoyer de grandes quantités de données, et générer puis envoyer 16 chunks solides peut prendre jusqu’à 1 seconde.
  • À l’heure actuelle, il ne s’exécute que si la version récente BusyBox 1.35.0 est installée.
    • Il n’a pas été testé avec GNU coreutils et il est supposé ne pas fonctionner avec.

Références

À lire aussi

1 commentaires

 
GN⁺ 2024-03-04
Avis sur Hacker News

  • Pour avoir beaucoup travaillé sur des serveurs Minecraft scriptables pour Java et Bedrock, c’est plutôt impressionnant.
    Point bonus pour avoir utilisé « duckduckgoing » dans une phrase.

  • Discussion de l’époque : https://news.ycombinator.com/item?id=30347501 — 92 commentaires

  • Les exposants négatifs, c’est simplement 2^(-n) = 1/(2^n).
    J’ai été surpris que l’auteur, après avoir même donné 2^-1 = 0,5 comme exemple, n’y ait pas pensé et ait fini par déléguer ça à awk.

    • De toute façon, Bash ne prend pas en charge les nombres à virgule flottante, donc je ne vois pas bien en quoi ça l’aurait aidé.

  • Il aurait dû utiliser ma bibliothèque idiote (?) ctypes.sh : https://github.com/taviso/ctypes.sh
    Ça donne accès depuis Bash à libm, poll(), select(), etc. :)

    • Je ne sais pas s’il fallait vraiment aller jusque-là, mais rien que cette témérité est impressionnante.
      On dirait qu’on ressuscite Frankenstein.
    • C’est cool, mais ça s’éloigne un peu du principe consistant à écrire en Bash quelque chose qui, techniquement, n’a absolument pas besoin d’être en Bash.
      Si Bash nécessite en plus du code C compilé installé séparément, alors autant exiger directement du C ou du Python, et la justification pour dire que c’est « écrit en Bash » devient moins forte. Je dis ça avec respect, bien sûr, et j’aime ce genre de projets « inutiles ».
      Cela dit, ce projet Minecraft dépend aussi d’outils externes comme xxd, donc dans ce cas utiliser ctypes.sh ne serait pas pire, et l’argument se tient même plutôt bien.
      À noter qu’on peut lire, stocker, manipuler, calculer et afficher du binaire en pur Bash sans dd ni xxd. Le seul octet problématique est le nul : on ne peut pas le stocker directement, mais on peut détecter qu’il a été lu, l’enregistrer, puis le restaurer à la sortie, ou l’utiliser comme valeur numérique pour des indices de tableau, des offsets d’octets, etc.
      Un exemple minimal de copie de fichier binaire est while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Cela dit, c’est juste faire cat sans cat, donc l’utilité n’apparaît pas vraiment.
      Un exemple plus général et utile se trouve ici : https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705
      En combinant LANG=C, IFS= et -d'', on peut accéder à tous les octets sauf 0x00, et distinguer, via la valeur de retour de read(), « a lu 0x00 », « n’a rien lu » et « fin de l’entrée ».
      Il n’est pas non plus nécessaire d’utiliser < et > sur toute la commande while(). On peut ouvrir avec exec 3<>file_or_fifo_or_tty, puis utiliser read -u3, printf >&3, etc. dans la boucle.
      Un exemple de lecture depuis un port série est ici : https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, et le code que j’ai réellement utilisé est ici : https://github.com/bkw777/pdd.sh. Regardez tpdd_read, tpdd_write, file_to_fhex, str_to_shex : ils lisent et écrivent sur un port série et des fichiers locaux, tout en traitant les données de plusieurs façons.
      Ces boucles ne sont même pas des sous-shells, encore moins des processus externes. Si l’on manipule des variables dans la boucle, on reste dans le contexte d’origine. Comme il n’y a pas d’enfant, il est même difficile de parler de shell parent.
      Les exemples lisent un octet à la fois avec read -n 1, mais ce n’est pas obligatoire. Si l’on lit sans -n1, chaque itération de boucle récupère autant de données que possible entre deux nuls, ce qui réduit la mémoire et le nombre d’itérations nécessaires.
      Dans mon cas, je dois découper et manipuler des octets individuels et des plages d’octets à partir d’offsets numériques, et les données sont petites selon les standards actuels, donc un tableau de paires hexadécimales est très pratique. a[n] == byte n, on peut traiter de la même façon les caractères affichables, non affichables et nuls, et on peut non seulement les enregistrer/recréer avec printf, mais aussi les utiliser directement comme valeurs numériques, par exemple 0x$n ou 0x${a[n]}.
      Par exemple, on peut lire le deuxième octet de h[] comme longueur de la charge utile qui suit, puis extraire cette charge utile avec ${h[@]:2:0x${h[1]}}.
    • Waouh, qu’est-ce que je viens de lire ? Impressionnant. Installé direct. Moi aussi, je veux faire partie du problème.
    • Oh, sympa :) Et salut tavis.
    • J’aimerais voir comment poll() et select() fonctionnent de cette manière.

  • Voilà ce qu’on attend d’un vrai site de hackers. Excellent.

  • Je ne suis pas très bon en programmation Bash, mais je suis surpris de voir à quel point c’est en réalité puissant et moins horrible qu’on ne le pense.

  • Bash fait partie de mes outils préférés, au même titre que vim et Lua.
    C’est un binaire unique de moins de 2 Mo, il est partout, et il peut faire beaucoup plus de choses que beaucoup ne l’imaginent.
    Avec shellcheck et de bonnes pratiques, Bash peut devenir lisible et sûr.
    Si l’on a besoin de plus, on peut greffer des utilitaires en C/C++ sans FFI compliquée, et sans devoir tirer tout un tas de dépendances obscures via pip/npm.

    • Ce que je préfère faire avec shellcheck, c’est le mettre dans la CI. Le coup que les développeurs détestent !
      Il y a souvent des scripts Bash inline dans la CI et les Dockerfile, et j’aime aussi tout déplacer dans des fichiers de scripts séparés. Maintenant que shellcheck est dans la CI, ce code est lui aussi vérifié.
      Les développeurs n’aiment pas ça en disant que « ça nuit à la lisibilité », alors qu’en plus de ne pas la dégrader, c’est beaucoup plus sûr.
      Le problème suivant, c’est que les mêmes scripts Bash se retrouvent dupliqués dans les mêmes fichiers de plusieurs dépôts. C’est une architecture de build distribuée ; je suis ouvert aux idées d’amélioration.
    • Je n’aime pas Bash parce que je ne le maîtrise pas bien. Ce n’est pas génial, mais cela reste souvent la meilleure solution possible.
      Je regrette de ne pas y avoir consacré plus de temps quand j’étais étudiant. C’est l’un des rares outils qui m’a suivi pendant toute ma carrière.

  • Je me demande s’il se fait encore des serveurs custom pour des jeux commerciaux.

    • Dans Minecraft, c’est très actif.
      La version Java, en particulier, occupe une position assez singulière : elle continue de recevoir de grosses mises à jour de contenu gratuites, tout en prenant officiellement en charge l’exécution de toutes les anciennes versions, et la communauté de modding est extrêmement active.
      Minecraft (Java) est à la fois un jeu et presque un moteur de jeu sur lequel d’autres construisent.
    • Pour certains jeux, il n’y a pas seulement des serveurs, mais aussi des clients : https://runelite.net/
    • Je pense que ça existera toujours chez les gens qui aiment jouer tout en bricolant la technique.
      On s’y met pour corriger des bugs, apprendre un langage ou voir comment ça fonctionne sous le capot.
    • À ma connaissance, côté rétro-ingénierie, c’est encore actif.

  • Minecraft est l’un des meilleurs jeux sortis depuis Quake.

  • Que ce genre de chose se soit réellement produit, bon sang.
    J’ai lu beaucoup d’articles sur des implémentations, mais celui-ci est écrasant. C’est de très loin l’un des meilleurs récits de projets bizarres que j’aie lus, et c’est vraiment un excellent article.