Un servidor de Minecraft hecho desde cero con Bash (2022)

 (sdomi.pl)
4 puntos por GN⁺ 2024-03-04 | 1 comentarios | Compartir por WhatsApp
  • Witchcraft es un proyecto experimental que implementa un servidor de Minecraft desde cero usando solo Bash, abordando el protocolo binario, Join Game y hasta el envío de chunks con el objetivo de permitir la conexión de clientes reales
  • La limitación de Bash de no poder conservar bytes nulos en cadenas se resolvió evitando guardar binarios en variables y procesándolos dentro de tuberías con dd y xxd
  • Las principales dificultades de implementación se concentraron en formatos de datos propios de Minecraft como VarInt/VarLong, punto flotante IEEE 754, Position y NBT; en especial, la conversión de Double era lenta por el costo de invocar comandos externos
  • El servidor se fue ampliando en este orden: Server List Ping, handshake, Join Game y paquetes Chunk Data And Update Light; para el dimension codec se usó un blob binario NBT tomado de un servidor vanilla
  • Puede cambiar la generación del mundo y los efectos mediante plugins basados en hooks, pero siguen pendientes el multijugador incompleto, la comunicación entre hilos basada en /dev/shm/witchcraft, el intercambio de datos lento y la dependencia de BusyBox 1.35.0

Manejo del protocolo binario de Minecraft en Bash

  • El intento inicial apuntaba al Classic protocol de 2009, pero primero quedó en evidencia la limitación de que Bash no puede parsear bien datos binarios
  • Las cadenas de Bash ignoran los bytes nulos (0x00), y tampoco hay forma de detectar si apareció uno, por lo que en un protocolo binario estricto los datos pueden corromperse
  • La solución fue mantener los datos binarios dentro de tuberías, sin meterlos en variables de Bash ni en sustituciones de comandos
    • dd count=$len bs=1 status=none | xxd -p lee la cantidad de bytes necesaria y la convierte en una cadena hex
    • Sobre esa cadena hex se hacen pattern matching, sustituciones y extracción de datos
    • Para enviar respuestas, se convierte otra vez a binario con la opción reverse de xxd
  • Para aceptar conexiones en el puerto TCP por defecto de Minecraft se usa ncat, y cuando entra una conexión se ejecuta el script principal mc.sh

Implementación de tipos de datos del protocolo

  • El primer objetivo fácil de implementar fue el paquete Server List Ping
    • No es un paquete obligatorio, así que aunque el servidor no responda bien, igual es posible conectarse al juego
    • Aun así, sirve para familiarizarse con conceptos centrales del protocolo como los data types

  • VarInt y VarLong

    • Los VarInt/VarLong de Minecraft son una variante de LEB128 que puede resultar familiar para quienes tienen experiencia con MQTT
    • LEB128 es un formato comprimido que guarda la longitud de enteros dividiendo cada byte en 1 bit de señal y 7 bits de datos
    • Si el primer bit es 0, ese byte es el último; si es 1, continúa otro byte
    • Como era difícil trasladar tal cual la reference implementation a Bash, se escribió un codificador propio usando módulo y división
    • El decodificador se implementó de forma similar a la referencia usando operaciones AND y multiplicación
    • Más que LEB128 en sí, lo molesto era que aparecía por todo el protocolo mezclado con int, long y signed short normales

  • Punto flotante IEEE 754

    • La conversión de IEEE 754 Double fue una de las partes más fastidiosas de implementar
    • La implementación básica necesitaba un bucle que aplicara potencias negativas, pero Bash no las soporta de forma nativa
    • Se evitó usar Perl, y bc aparentemente no soportaba exponenciación en ese entorno o en esa versión de BusyBox
    • awk sí puede manejar potencias negativas como 2**-1, así que se usó para implementar la conversión
    • La implementación inicial era tan lenta que procesar unos 50 a 100 paquetes enviados por el cliente en Player Move, con 3 valores Double de X·Y·Z por paquete, podía tomar varios minutos
    • La estructura que llamaba repetidamente a awk dentro de un bucle for de Bash se pasó a un bucle interno en awk para reducir la cantidad de invocaciones externas
    • Después, la conversión bajó a unos 10 ms en un Xeon E5-2680v2
    • La cifra anterior de unos 350 ms no era una medición totalmente confiable

  • Tipo de dato Position

    • Position es un tipo de dato basado en Long de 64 bits creado por Mojang
    • X se guarda en los 26 bits superiores, Z en los 26 bits intermedios y Y en los 12 bits inferiores
    • Bash sí tiene los operadores de desplazamiento de bits necesarios, así que implementarlo fue fácil
    • Aun así, este tipo no se usa mucho, y muchos paquetes guardan las coordenadas X·Y·Z como valores Double separados
    • Como resultado, los datos de posición crecen de 64 bits a 192 bits por paquete
    • Si se asume que solo hacen falta números hasta el world border por defecto de 30,000,000, se obtiene precisión de punto flotante de 9 dígitos
    • La comunicación normal del servidor usa zlib, y para representar posiciones dentro de bloques en la práctica no parece necesario más de 2 o 3 decimales

  • NBT

    • NBT es un formato interno de Mojang, parecido a JSON pero para datos binarios
    • Igual que JSON, también se usa para guardar datos arbitrarios fuera de la especificación
    • Mojang, por ejemplo, guarda bitstreams de longitud variable como arreglos de Long
    • Si el arreglo no está alineado a Long o a byte, el último Long se rellena con 0
    • El parser de NBT estuvo cerca de completarse, pero se decidió que no valía la pena terminarlo
    • Ese código se perdió en un crash del sistema cuando el directorio del proyecto usaba mucho tmpfs

Crear un servidor al que sí se pueda entrar

  • El siguiente paso después de Server Ping fue manejar el handshake real y más paquetes necesarios para entrar al juego
  • Para que el cliente pueda entrar al servidor, debe completar el handshake y recibir paquetes relacionados con chunks, player position, inventory y join game
  • El mayor obstáculo fueron las estructuras de datos internas del paquete Join Game y de los paquetes de Chunk

  • Join Game

    • El paquete Join Game envía metadatos iniciales
    • Incluye el entity ID del jugador, gamemode, información del mundo y el Dimension codec añadido alrededor de Minecraft 1.16
    • El Dimension codec es un NBT Compound, así que implicaba bastante carga de implementación
    • Witchcraft reutiliza este campo NBT tomándolo de un servidor vanilla
    • Esta es la única parte con un blob binario en toda la implementación, y aunque se podría reimplementar, se consideró que no hacía falta personalizarla

  • Chunk Data And Update Light

    • El paquete Chunk Data And Update Light al principio parecía grande y complejo, pero se simplifica si varios campos BitSet se dejan en 0x00 y no se envía el campo Block Entity
    • Los campos que quedan son X, Y, heightmaps y Data
    • Los heightmaps son una forma más compleja de codificar la repetición de b000000010, y en la práctica se consideró que podían ser casi cualquier valor

Manejo de Chunk Section y palette

  • El campo Data es un arreglo de Chunk Section
  • Una Chunk Section es un bloque de 16×16×16, y apilando varias sections se puede formar un Chunk completo
  • Para simplificar la implementación, este arreglo usa un solo elemento
  • Chunk Section se compone de block count, block states container y biome container
  • Tanto block states como biome container usan una estructura de palette
    • Antes de los datos reales de bloques, el servidor debe definir el mapeo entre local block ID y global block ID
    • Es una estructura pensada para meter la mayor cantidad posible de datos en el menor espacio
    • La definición de bloques puede reducirse hasta un mínimo de 4 bits
  • Witchcraft usa 8 bits por bloque en lugar del mínimo de 4 bits para facilitar la gestión
    • Así se obtienen 256 entradas disponibles en la palette
    • Los datos reales del chunk pueden enviarse simplemente como números hex que apuntan a entradas de la palette
    • Una palette de 4 bits también sería fácil de manejar en una cadena hex, porque un byte representa dos bloques, pero limitaría el chunk a 16 bloques
  • El estándar permite desde 4 bits por bloque hasta 9 bits por bloque; fuera de eso se considera un direct palette mapping de 15 bits por bloque
  • La biome palette se maneja de otra manera
    • Se envía una palette vacía y se mapea directamente el biome ID 0x01, es decir, minecraft:plains, a todas las regiones dentro del chunk
    • Esto se basa en ingeniería inversa del comportamiento vanilla
    • Se sospecha que la documentación existente de esa parte del paquete podría ser inexacta

Estructura de plugins basada en hooks y demos

  • Con la implementación básica solo se mostraban chunks comunes, así que hacía falta una demo para mostrar que el servidor podía hacer algo más que desplegar chunks
  • Para evitar crear un árbol de código separado para cada demo, se llamaron hooks a las funciones sobreescribibles y se permitió que el servidor cargara código de usuario
  • Con esta estructura se puede desde cambiar la forma del mundo hasta conectar pkt_effect para que el jugador haga un ticking noise al mover el mouse
  • Un plugin de ejemplo genera chunks eligiendo bloques aleatorios de la palette base
    • En hook_chunks() se llama a chunk_header
    • Para 4096 bloques se agrega en hex el valor RANDOM%30
    • El chunk generado se guarda en $TEMP/world/0000000000000000
    • Luego se llama varias veces a pkt_chunk sobre coordenadas cercanas para enviar los chunks
  • Otra demo, digmeout, es un juego simple basado en puntaje
    • Lanza al jugador a un chunk con piedra y minerales colocados al azar
    • La idea es minar el mineral más valioso antes de que se acabe el tiempo

Limitaciones de Witchcraft

  • Bash es muy malo para manejar fracciones decimales
    • Los enteros se pueden manejar más o menos bien
    • Las fracciones decimales deben tratarse multiplicando en la entrada y colocando el punto en la posición adecuada al salir
    • Por eso, la mayoría o todos los números que maneja Witchcraft son int
  • El multijugador no funciona bien
    • Hasta cierto punto sí funciona, pero no se invirtió tiempo en terminarlo ni pulirlo
  • Witchcraft es técnicamente un servidor multihilo
    • Como resultado, necesita hacks poco elegantes para la comunicación entre hilos
    • La mayor parte de los datos globales se guarda bajo /dev/shm/witchcraft y se referencia internamente como $TEMP
  • El rendimiento sigue siendo una gran limitación
    • Sobre todo, el intercambio de datos entre varios hilos es lento
    • Es difícil enviar grandes cantidades de datos, y generar y mandar 16 chunks sólidos puede tardar hasta 1 segundo
  • Actualmente solo funciona si está instalado BusyBox 1.35.0 reciente
    • No se probó con GNU coreutils y se espera que no funcione

Material de referencia

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-03-04
Opiniones en Hacker News

  • Como alguien que ha trabajado bastante en servidores de Minecraft programables para Java y Bedrock, esto es bastante impresionante.
    También suma puntos por usar “duckduckgoing” en una oración.

  • Discusión de aquel entonces: https://news.ycombinator.com/item?id=30347501 — 92 comentarios

  • Un exponente negativo no es más que 2^(-n) = 1/(2^n).
    Me sorprendió que el autor, incluso habiendo puesto como ejemplo 2^-1 = 0.5, no se diera cuenta de eso y terminara pasándoselo a awk.

    • De todos modos Bash no soporta números de punto flotante, así que no sé cómo le habría ayudado eso al autor.

  • Debería haber usado mi biblioteca tonta(?) ctypes.sh: https://github.com/taviso/ctypes.sh
    Con eso se puede acceder desde Bash a cosas como libm, poll(), select() :)

    • No sé si hacía falta llegar tan lejos, pero solo esa temeridad ya es impresionante.
      Se siente como revivir a Frankenstein.
    • Está genial, pero se aleja un poco de la esencia de escribir en Bash algo que técnicamente no tiene ninguna necesidad de ser Bash.
      Si además necesitas código C compilado instalado aparte para Bash, entonces también podrías pedir C o Python directamente, y se debilita la razón para llamarlo “escrito en Bash”. Lo digo con respeto, claro, y me encantan estos proyectos “inútiles”.
      Dicho eso, este proyecto de Minecraft también depende de herramientas externas como xxd, así que en este caso usar ctypes.sh no lo haría peor; de hecho, tiene sentido.
      Como referencia, incluso sin dd ni xxd se puede leer, almacenar, manipular, calcular e imprimir binarios en Bash puro. El único byte problemático es el nulo: aunque no se pueda almacenar directamente, se puede detectar que fue leído, registrarlo y luego restaurarlo al imprimir, o usarlo como valor numérico para índices de arreglos, offsets de bytes, etc.
      Un ejemplo mínimo para copiar un archivo binario es while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Pero eso es básicamente hacer cat sin cat, así que no muestra muy bien su utilidad.
      Hay un ejemplo más general y útil en https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705
      Combinando LANG=C, IFS= y -d'' se puede acceder a todos los bytes excepto 0x00, y con el valor de retorno de read() se puede distinguir entre “leí 0x00”, “no pude leer nada” y “se terminó la entrada”.
      Tampoco hace falta usar < y > en todo el comando while(). Se puede abrir con exec 3<>file_or_fifo_or_tty y usar read -u3, printf >&3, etc. dentro del bucle.
      Un ejemplo de lectura desde un puerto serial está en https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, y el código que usé realmente está en https://github.com/bkw777/pdd.sh. Si miras tpdd_read, tpdd_write, file_to_fhex, str_to_shex, verás cómo lee y escribe puertos seriales y archivos locales, procesando los datos de varias maneras.
      Esos bucles ni siquiera son procesos externos, ni subshells. Si manipulas variables dentro del bucle, sigues en el mismo contexto original. Como no hay hijo, incluso es raro llamarlo shell padre.
      Los ejemplos leen byte por byte con read -n 1, pero no tiene por qué ser así. Si lees sin -n1, cada iteración del bucle reúne la mayor cantidad posible de datos entre nulos, usando menos memoria y menos iteraciones.
      En mi caso de uso necesito cortar y manipular bytes individuales y rangos de bytes por offsets numéricos, y los datos además son pequeños para los estándares actuales, así que un arreglo de pares hexadecimales resulta muy cómodo. a[n] == byte n, y puedo tratar de la misma forma caracteres imprimibles, no imprimibles y nulos; además de guardarlos y regenerarlos con printf, también puedo usarlos directamente como valores numéricos con 0x$n o 0x${a[n]}.
      Por ejemplo, puedo leer el segundo byte de h[] como longitud del payload que le sigue y extraer ese payload con ${h[@]:2:0x${h[1]}}.
    • Wow, ¿qué acabo de leer? Increíble. Lo instalé de inmediato. Yo también quiero ser parte del problema.
    • Oh, qué bueno :) Y hola, tavis.
    • Me gustaría ver cómo funcionan poll() y select() de esta manera.

  • Así sí se ve un verdadero sitio de hackers. Excelente.

  • No soy muy bueno programando en Bash, pero me sorprende que en la práctica sea más potente y menos horrible de lo que uno pensaría.

  • Bash es una de mis herramientas favoritas, junto con vim y Lua.
    Es un binario único de menos de 2 MB, está en todas partes y puede hacer muchísimo más de lo que mucha gente cree.
    Con shellcheck y buenas prácticas, Bash también puede volverse legible y seguro.
    Si necesitas algo más, puedes agregar utilidades en C/C++ sin FFI complicadas, y no hace falta arrastrar un montón de dependencias misteriosas con cosas como pip/npm.

    • Lo que más me gusta hacer con shellcheck es meterlo en CI. ¡Ese movimiento que los desarrolladores odian!
      Muchas veces hay scripts Bash inline dentro de CI y Dockerfile, y también me gusta moverlos todos a archivos de script separados. Ahora que hay shellcheck en CI, también se revisa ese código.
      Los desarrolladores lo odian diciendo que “reduce la legibilidad”, pero lejos de hacerla peor, lo vuelve mucho más seguro.
      El siguiente problema es que el mismo script Bash termina duplicado en el mismo archivo de varios repositorios. Es una estructura de build distribuida; estoy abierto a ideas para mejorarla.
    • Odio Bash porque no soy bueno usándolo. Es malo, pero aun así muchas veces sigue siendo la mejor solución posible.
      Me arrepiento de no haberle dedicado más tiempo cuando era estudiante, porque ha sido una de las pocas herramientas que me acompañó durante toda mi carrera.

  • Me pregunto si todavía se hacen servidores personalizados para juegos comerciales.

    • En Minecraft está muy activo.
      En particular, la versión Java ocupa una posición relativamente particular: sigue recibiendo grandes actualizaciones gratuitas de contenido, soporta oficialmente ejecutar todas las versiones anteriores, y la comunidad de modding es enormemente activa.
      Minecraft (Java) es tanto un juego como algo cercano a un motor de juegos sobre el que otras personas construyen.
    • No solo servidores; en algunos juegos también hay clientes: https://runelite.net/
    • Creo que esto siempre existirá para quienes disfrutan jugar y al mismo tiempo trastear con la tecnología.
      Lo hacen para corregir bugs, aprender un lenguaje o ver cómo funcionan las cosas por dentro.
    • Hasta donde sé, el área de ingeniería inversa sigue activa.

  • Minecraft es uno de los mejores juegos que salieron después de Quake.

  • No puedo creer que esto haya pasado de verdad.
    He leído muchos artículos sobre implementaciones, pero esto es abrumador. Es, por mucho, uno de los mejores textos sobre proyectos extraños que he leído, y está realmente excelente.