Ein von Grund auf mit Bash gebauter Minecraft-Server (2022)

 (sdomi.pl)
4 Punkte von GN⁺ 2024-03-04 | 1 Kommentare | Auf WhatsApp teilen
  • Witchcraft ist ein experimentelles Projekt, das einen Minecraft-Server ausschließlich in Bash von Grund auf implementiert hat und dabei sogar Binärprotokoll, Join Game und Chunk-Übertragung behandelt, mit dem Ziel, echte Client-Verbindungen zu ermöglichen
  • Die Einschränkung von Bash, Null-Bytes nicht in Strings erhalten zu können, wird umgangen, indem Binärdaten nicht in Variablen gespeichert, sondern innerhalb von dd- und xxd-Pipelines verarbeitet werden
  • Die größten Implementierungsprobleme konzentrierten sich auf Minecraft-spezifische Datentypen wie VarInt/VarLong, IEEE-754-Gleitkommazahlen, Position und NBT; insbesondere die Double-Konvertierung war wegen der Kosten externer Befehlsaufrufe langsam
  • Der Server wurde schrittweise um Server List Ping, Handshake, Join Game und Chunk Data And Update Light erweitert; für den Dimension codec wird ein NBT-Binärblob aus einem Vanilla-Server verwendet
  • Über Hook-basierte Plugins lassen sich Weltgenerierung und Effekte verändern, aber unvollständiger Multiplayer, Thread-Kommunikation über /dev/shm/witchcraft, langsamer Datenaustausch und die Abhängigkeit von BusyBox 1.35.0 bleiben bestehen

Binäres Minecraft-Protokoll in Bash behandeln

  • Ein erster Versuch zielte auf das Classic protocol von 2009, doch dabei zeigte sich schnell die Grenze, dass sich Binärdaten in Bash nur schwer korrekt parsen lassen
  • Bash-Strings ignorieren Null-Bytes (0x00), und es gibt keine Möglichkeit zu erkennen, ob ein Null-Byte aufgetreten ist, wodurch Daten in einem strikt binären Protokoll beschädigt werden können
  • Die Umgehung besteht darin, Binärdaten weder in Bash-Variablen noch in Command Substitution zu speichern, sondern in der Pipe zu halten
    • Mit dd count=$len bs=1 status=none | xxd -p wird die benötigte Byte-Anzahl gelesen und in einen Hex-String umgewandelt
    • Auf dem Hex-String werden danach Pattern Matching, Ersetzungen und Datenextraktion ausgeführt
    • Zum Senden einer Antwort wird mit der Reverse-Option von xxd wieder in Binärdaten zurückgewandelt
  • Um Verbindungen auf dem Standard-TCP-Port von Minecraft anzunehmen, wird ncat verwendet; bei einer eingehenden Verbindung startet es das Haupt-Shell-Skript mc.sh

Implementierung der Protokoll-Datentypen

  • Das am einfachsten zuerst umzusetzende Ziel war das Paket Server List Ping
    • Es ist kein Pflichtpaket, daher ist der Spielbeitritt auch dann möglich, wenn der Server darauf nicht korrekt antwortet
    • Es eignet sich aber gut, um zentrale Protokollkonzepte wie data types kennenzulernen

  • VarInt und VarLong

    • Die VarInt/VarLong-Typen von Minecraft sind eine LEB128-Variante, die MQTT-Erfahrenen bekannt vorkommen dürfte
    • LEB128 ist ein Komprimierungsverfahren, das die Länge eines Integers speichert, indem jedes Byte in 1 Signalbit und 7 Datenbits aufgeteilt wird
    • Ist das erste Bit 0, ist dieses Byte das letzte; ist es 1, folgt ein weiteres Byte
    • Da sich die Referenzimplementierung nicht leicht direkt nach Bash übertragen ließ, wurde ein eigener Encoder mit Modulo und Division geschrieben
    • Der Decoder wurde ähnlich wie die Referenz mit AND-Operationen und Multiplikation implementiert
    • Umständlicher als LEB128 selbst war, dass es im Protokoll überall zusammen mit normalen int-, long- und signed-short-Werten auftaucht

  • IEEE-754-Gleitkommazahlen

    • Die Konvertierung von IEEE-754-Double war einer der lästigsten Teile der Implementierung
    • Die Grundimplementierung benötigt eine Schleife mit negativen Potenzen, aber Bash unterstützt negative Potenzen nicht nativ
    • Auf Perl wurde verzichtet, und bc schien in der Zielumgebung bzw. in der BusyBox-Version keine Potenzen zu unterstützen
    • awk kann negative Potenzen wie 2**-1 verarbeiten und wurde deshalb für die Konvertierung genutzt
    • Eine frühe Implementierung war so langsam, dass die Verarbeitung von etwa 50–100 Paketen, die der Client im Player-Move-Paket sendet, mit jeweils 3 Double-Werten für X, Y und Z mehrere Minuten dauern konnte
    • Die wiederholten awk-Aufrufe innerhalb einer Bash-for-Schleife wurden in eine interne awk-Schleife verlagert, um die Zahl externer Befehlsaufrufe zu senken
    • Danach sank die Konvertierungszeit auf einem Xeon E5-2680v2 auf etwa 10 ms
    • Der frühere Wert von etwa 350 ms war kein sicher gemessener Benchmark

  • Position-Datentyp

    • Position ist ein von Mojang definierter Datentyp auf Basis eines 64-Bit-Longs
    • X belegt die oberen 26 Bit, Z die mittleren 26 Bit und Y die unteren 12 Bit
    • Da Bash die nötigen Bitshift-Operatoren bietet, war die Implementierung einfach
    • Der Typ wird allerdings nicht häufig verwendet; viele Pakete speichern X-, Y- und Z-Koordinaten stattdessen als separate Double-Werte
    • Dadurch wächst die Positionsinformation pro Paket von 64 Bit auf 192 Bit
    • Wenn man annimmt, dass nur Zahlen bis zur Standard-World-Border von 30.000.000 benötigt werden, ergibt sich eine Gleitkommagenauigkeit von 9 Stellen
    • Da normale Serverkommunikation zlib nutzt und für Positionen innerhalb eines Blocks realistisch nicht mehr als 2–3 Nachkommastellen nötig sind, ist das vertretbar

  • NBT

    • NBT ist ein internes Mojang-Format, das für Binärdaten in etwa eine JSON-ähnliche Rolle einnimmt
    • Wie JSON wird es auch zur Speicherung beliebiger Daten außerhalb der eigentlichen Spezifikation verwendet
    • Mojang speichert darin zum Beispiel Bitstreams variabler Länge als Long-Arrays
    • Wenn ein Array nicht auf Long- oder Byte-Grenzen endet, wird das letzte Long mit 0 aufgefüllt
    • Ein NBT-Parser war beinahe fertig, wurde aber letztlich als nicht lohnend eingeschätzt
    • Der entsprechende Code ging bei einem Systemabsturz verloren, während im Projektverzeichnis viel tmpfs genutzt wurde

Einen beitretbaren Server bauen

  • Nach Server Ping war der nächste Schritt das Handshake und weitere Pakete, die für einen echten Spielbeitritt nötig sind
  • Damit ein Client dem Server beitreten kann, muss er das Handshake abschließen und Pakete für Chunks, Spielerposition, Inventar und Join Game erhalten
  • Die größten Hürden waren die Datenstrukturen innerhalb des Join Game-Pakets und der Chunk-Pakete

  • Join Game

    • Das Paket Join Game überträgt anfängliche Metadaten
    • Dazu gehören die Entity-ID des Spielers, der Gamemode, weltbezogene Informationen und der seit etwa Minecraft 1.16 enthaltene Dimension codec
    • Der Dimension codec ist ein NBT-Compound und dadurch aufwendig zu implementieren
    • Witchcraft übernimmt dieses NBT-Feld aus einem Vanilla-Server
    • Das ist der einzige Binärblob in der Implementierung; eine Neuumsetzung wäre möglich, wurde aber als unnötig für Anpassungen angesehen

  • Chunk Data And Update Light

    • Das Paket Chunk Data And Update Light wirkt anfangs groß und komplex, wird aber einfach, wenn mehrere BitSet-Felder auf 0x00 gesetzt und keine Block-Entity-Felder gesendet werden
    • Dann bleiben nur die Felder X, Y, heightmaps und Data übrig
    • heightmaps ist eine aufwendiger kodierte Form von wiederholtem b000000010 und kann im Grunde wohl nahezu jeden Wert haben

Chunk-Section- und Palette-Verarbeitung

  • Das Data-Feld ist ein Array von Chunk Sections
  • Eine Chunk Section umfasst 16×16×16 Blöcke; mehrere Sections können gestapelt werden, um einen ganzen Chunk zu bilden
  • Zur Vereinfachung wird in dieser Implementierung nur ein einziges Array-Element verwendet
  • Eine Chunk Section besteht aus Block Count, Block States Container und Biome Container
  • Sowohl Block States als auch der Biome Container verwenden eine Palette-Struktur
    • Vor den eigentlichen Blockdaten muss der Server eine Zuordnung zwischen lokaler Block-ID und globaler Block-ID definieren
    • Die Struktur dient dazu, möglichst viele Daten auf möglichst kleinem Raum unterzubringen
    • Blockdefinitionen können bis auf mindestens 4 Bit schrumpfen
  • Witchcraft verwendet aus Gründen der Handhabbarkeit 8 bits per block statt der minimalen 4 Bit
    • Dadurch gibt es 256 nutzbare Palette-Einträge
    • Für die eigentlichen Chunk-Daten reicht es dann, Hex-Zahlen zu senden, die auf einen Palette-Eintrag verweisen
    • Auch eine 4-Bit-Palette wäre auf Hex-String-Ebene einfach, da ein Byte zwei Blöcke darstellen kann, würde pro Chunk aber auf 16 Blöcke begrenzen
  • Der Standard erlaubt 4 bis 9 bits per block; alles andere wird als direktes Palette-Mapping mit 15 bits per block behandelt
  • Die Biome-Palette wird gesondert behandelt
    • Es wird eine leere Palette gesendet und die Biome-ID 0x01, also minecraft:plains, direkt auf alle Regionen im Chunk gemappt
    • Das basiert auf Reverse Engineering des Vanilla-Verhaltens
    • Es besteht der Verdacht, dass die vorhandene Dokumentation zu diesem Teil des Pakets ungenau ist

Hook-basierte Plugin-Struktur und Demos

  • Mit nur der Grundimplementierung wurden bloß gewöhnliche Chunks angezeigt; deshalb war eine Demo nötig, um zu zeigen, dass der Server mehr kann als nur Chunks auszugeben
  • Um nicht für jede Demo einen separaten Quellbaum anzulegen, wurden überschreibbare Funktionen als hooks bezeichnet und der Server so aufgebaut, dass er Benutzercode laden kann
  • Mit dieser Struktur lassen sich sowohl die Form der Welt verändern als auch Effekte wie das Verbinden von pkt_effect, damit der Spieler beim Bewegen der Maus Tickgeräusche erzeugt
  • Ein Beispiel-Plugin erzeugt Chunks, indem es zufällige Blöcke aus der Standard-Palette auswählt
    • In hook_chunks() wird chunk_header aufgerufen
    • Für 4096 Blöcke wird der Wert RANDOM%30 als Hex angehängt
    • Der erzeugte Chunk wird unter $TEMP/world/0000000000000000 gespeichert
    • Für umliegende Koordinaten wird mehrfach pkt_chunk aufgerufen, um Chunks zu senden
  • Eine weitere Demo namens digmeout ist ein einfaches punktbasiertes Spiel
    • Der Spieler wird in einen Chunk mit zufällig platzierten Steinen und Erzen geworfen
    • Ziel ist es, bis zum Ablauf der Zeit die wertvollsten Erze abzubauen

Einschränkungen von Witchcraft

  • Bash ist bei der Verarbeitung von dezimalen Bruchzahlen sehr schwach
    • Integer lassen sich einigermaßen verarbeiten
    • Dezimalwerte müssen behandelt werden, indem beim Einlesen multipliziert und beim Ausgeben an der passenden Stelle ein Punkt eingefügt wird
    • Deshalb sind die meisten oder alle Zahlen, die Witchcraft verarbeitet, int-Werte
  • Multiplayer funktioniert nicht wirklich ordentlich
    • Teilweise läuft er, aber es wurde keine Zeit investiert, ihn fertigzustellen oder zu polieren
  • Witchcraft ist technisch gesehen ein multi-threaded server
    • Dadurch waren unschöne Hacks für die Kommunikation zwischen Threads nötig
    • Die meisten globalen Daten liegen unter /dev/shm/witchcraft und werden intern über $TEMP referenziert
  • Performance bleibt eine große Einschränkung
    • Vor allem der Datenaustausch zwischen mehreren Threads ist langsam
    • Große Datenmengen zu senden ist schwierig; das Erzeugen und Versenden von 16 massiven Chunks kann bis zu 1 Sekunde dauern
  • Derzeit läuft das Projekt nur, wenn BusyBox 1.35.0 in aktueller Version installiert ist
    • Mit GNU coreutils wurde es nicht getestet, und es wird erwartet, dass es dort nicht funktioniert

Referenzen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-03-04
Hacker-News-Kommentare

  • Als jemand, der viel an skriptbaren Minecraft-Servern für Java und Bedrock gearbeitet hat: Das ist ziemlich beeindruckend.
    Bonuspunkte auch dafür, „duckduckgoing“ in einem Satz zu verwenden.

  • Diskussion von damals: https://news.ycombinator.com/item?id=30347501 — 92 Kommentare

  • Negative Exponenten sind einfach 2^(-n) = 1/(2^n).
    Ich fand es überraschend, dass der Autor das nicht erkannt hat, obwohl er in seinem eigenen Beispiel sogar 2^-1 = 0,5 anführt, und es am Ende an awk ausgelagert hat.

    • Bash unterstützt ohnehin keine Fließkommazahlen, daher weiß ich nicht, wie ihm das geholfen hätte.

  • Er hätte meine alberne(?) Bibliothek ctypes.sh verwenden sollen: https://github.com/taviso/ctypes.sh
    Damit kann man aus Bash auch auf libm, poll(), select() und Ähnliches zugreifen :)

    • Ich weiß nicht, ob man wirklich so weit hätte gehen müssen, aber allein diese Tollkühnheit ist beeindruckend.
      Fühlt sich an, als würde man Frankenstein wiederbeleben.
    • Cool ist es schon, aber es weicht etwas vom eigentlichen Punkt ab, nämlich etwas in Bash zu schreiben, das technisch überhaupt nicht Bash sein müsste.
      Wenn Bash zusätzlich installierten, kompilierten C-Code braucht, könnte man genauso gut C oder Python verlangen; dann gibt es weniger Grund, es „in Bash geschrieben“ zu nennen. Das ist natürlich respektvoll gemeint, und ich mag solche „nutzlosen“ Projekte an sich.
      Allerdings hängt auch dieses Minecraft-Projekt von externen Tools wie xxd ab; in diesem Fall wäre ctypes.sh also nicht schlimmer, sondern eigentlich ein fairer Punkt.
      Nebenbei: Auch ohne dd oder xxd kann man rein in Bash Binärdaten lesen, speichern, manipulieren, berechnen und ausgeben. Das problematische Byte ist nur Null; man kann es zwar nicht direkt speichern, aber erkennen und vermerken, dass es gelesen wurde, es später bei der Ausgabe wiederherstellen oder seinen Zahlenwert als Array-Index, Byte-Offset usw. verwenden.
      Ein Minimalbeispiel zum Kopieren einer Binärdatei ist while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Allerdings ist das im Grunde cat ohne cat, daher wird der Nutzen nicht besonders sichtbar.
      Ein allgemeineres und nützlicheres Beispiel steht unter https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705.
      Mit der Kombination aus LANG=C, IFS= und -d'' kann man auf alle Bytes außer 0x00 zugreifen, und über den Rückgabewert von read() kann man unterscheiden, ob „0x00 gelesen wurde“, „gar nichts gelesen werden konnte“ oder „das Eingabeende erreicht wurde“.
      Man muss auch nicht den gesamten while()-Befehl mit < und > versehen. Man kann mit exec 3<>file_or_fifo_or_tty öffnen und in der Schleife read -u3, printf >&3 usw. verwenden.
      Ein Beispiel zum Lesen von einem seriellen Port steht unter https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, und der tatsächlich verwendete Code ist unter https://github.com/bkw777/pdd.sh zu finden. Wenn man sich tpdd_read, tpdd_write, file_to_fhex, str_to_shex ansieht, sieht man, wie serielle Ports und lokale Dateien gelesen und geschrieben werden und die Daten auf verschiedene Arten verarbeitet werden.
      Diese Schleifen sind nicht einmal Subshells, geschweige denn externe Prozesse. Wenn man innerhalb der Schleife Variablen verändert, bleibt man im ursprünglichen Kontext. Da es kein Kind gibt, ist es auch etwas schwer, von einer Parent-Shell zu sprechen.
      Die Beispiele lesen mit read -n 1 jeweils ein Byte, aber das muss nicht zwingend so sein. Liest man ohne -n1, sammelt die Schleife pro Durchlauf möglichst viele Daten zwischen Null-Bytes, wodurch weniger Speicher und weniger Iterationen nötig sind.
      Für meine Zwecke muss ich einzelne Bytes und Bytebereiche anhand numerischer Offsets ausschneiden und manipulieren, und die Daten sind nach heutigen Maßstäben klein, daher ist ein Array aus Hex-Paaren sehr praktisch. Dann gilt a[n] == byte n; druckbare Zeichen, nicht druckbare Zeichen und Null-Bytes lassen sich einheitlich behandeln, und man kann sie nicht nur mit printf speichern und neu erzeugen, sondern auch direkt als Zahlenwerte wie 0x$n oder 0x${a[n]} verwenden.
      Zum Beispiel kann man das zweite Byte von h[] als Länge des folgenden Payloads lesen und diesen Payload mit ${h[@]:2:0x${h[1]}} herausschneiden.
    • Wow, was habe ich da gerade gelesen? Großartig. Direkt installiert. Ich will auch Teil des Problems sein.
    • Oh, cool :) Und hallo, tavis.
    • Ich würde gern sehen, wie poll() und select() auf diese Weise funktionieren.

  • Genau so muss eine echte Hacker-Site sein. Großartig.

  • Ich bin nicht besonders gut in Bash-Programmierung, aber es überrascht mich, dass Bash in der Praxis mächtiger und weniger schrecklich ist, als man denkt.

  • Bash ist eines meiner Lieblingstools, zusammen mit vim und Lua.
    Es ist ein einzelnes Binary von unter 2 MB, überall verfügbar, und man kann damit viel mehr machen, als viele glauben.
    Mit shellcheck und guten Gewohnheiten kann Bash ebenfalls lesbar und sicher werden.
    Wenn man mehr braucht, kann man ohne kompliziertes FFI Utilities in C/C++ anbinden, statt über pip/npm einen Haufen undurchsichtiger Abhängigkeiten hereinzuziehen.

    • Was ich mit shellcheck am liebsten mache, ist, es in die CI zu packen. Dieser eine Trick, den Entwickler hassen!
      In CI und Dockerfiles stecken oft Inline-Bash-Skripte, und ich verschiebe sie gern alle in separate Skriptdateien. Jetzt gibt es shellcheck in der CI, also werden auch diese Codeabschnitte geprüft.
      Entwickler mögen das nicht und sagen, es sei „weniger lesbar“, aber statt weniger lesbar zu sein, ist es viel sicherer.
      Das nächste Problem ist, dass dasselbe Bash-Skript in derselben Datei über mehrere Repositories hinweg dupliziert wird. Es ist eine verteilte Build-Struktur; für Verbesserungsideen bin ich offen.
    • Ich mag Bash nicht, weil ich nicht gut darin bin. Es ist zwar nicht toll, aber trotzdem oft die bestmögliche Lösung.
      Ich bereue, als Student nicht mehr Zeit darin investiert zu haben. Es ist eines der wenigen Tools, die mich meine ganze Karriere lang begleitet haben.

  • Ich frage mich, ob es noch Leute gibt, die Custom-Server für kommerzielle Spiele bauen.

    • Bei Minecraft ist das sehr aktiv.
      Besonders die Java-Version nimmt eine relativ ungewöhnliche Position ein: Sie bekommt weiterhin große kostenlose Content-Updates, unterstützt offiziell das Ausführen aller früheren Versionen, und die Modding-Community ist enorm aktiv.
      Minecraft (Java) ist gleichzeitig ein Spiel und fast schon eine Game Engine, auf der andere Leute aufbauen.
    • Nicht nur Server; für manche Spiele gibt es auch Clients: https://runelite.net/
    • Für Leute, die beim Spielen gern an Technik herumbasteln, wird es so etwas wohl immer geben.
      Man macht es, um Bugs zu beheben, eine Sprache zu lernen oder zu sehen, wie die Interna funktionieren.
    • Soweit ich weiß, ist die Reverse-Engineering-Szene noch aktiv.

  • Minecraft ist eines der besten Spiele seit Quake.

  • Dass so etwas tatsächlich passiert ist — meine Güte.
    Ich habe viele Artikel über Implementierungsdetails gelesen, aber dieser hier ist überragend. Das ist mit Abstand einer der besten Beiträge über ein kurioses Projekt, die ich je gelesen habe, und wirklich hervorragend geschrieben.