Um servidor de Minecraft feito do zero usando Bash (2022)

 (sdomi.pl)
4 pontos por GN⁺ 2024-03-04 | 1 comentários | Compartilhar no WhatsApp
  • Witchcraft é um projeto experimental que implementa um servidor de Minecraft do zero usando apenas Bash, lidando com o protocolo binário, Join Game e até envio de chunks, com o objetivo de permitir a conexão de clientes reais
  • A limitação do Bash de não preservar bytes nulos em strings foi contornada processando os dados binários dentro de pipes com dd e xxd, sem colocá-los em variáveis
  • As principais dificuldades de implementação se concentraram em formatos de dados próprios do Minecraft, como VarInt/VarLong, ponto flutuante IEEE 754, Position e NBT; em especial, a conversão de Double era lenta por causa do custo de chamar comandos externos
  • O servidor foi expandido na sequência de pacotes Server List Ping, handshake, Join Game e Chunk Data And Update Light, e o Dimension codec usa um blob binário NBT obtido de um servidor vanilla
  • Plugins baseados em hooks permitem mudar a geração do mundo e os efeitos, mas ainda restam limitações como multiplayer incompleto, comunicação entre threads baseada em /dev/shm/witchcraft, troca lenta de dados e dependência do BusyBox 1.35.0

Lidando com o protocolo binário do Minecraft no Bash

  • A tentativa inicial mirava o Classic protocol de 2009, mas logo ficou claro que havia limitações para fazer parsing correto de dados binários em Bash
  • Strings em Bash ignoram bytes nulos (0x00), e não há como detectar se eles ocorreram, então os dados podem ser corrompidos em um protocolo binário rígido
  • A solução alternativa foi manter os dados binários dentro de pipes, sem colocá-los em variáveis do Bash nem em substituição de comandos
    • dd count=$len bs=1 status=none | xxd -p lê a quantidade necessária de bytes e converte em string hexadecimal
    • Sobre essa string hexadecimal, são feitos pattern matching, substituição e extração de dados
    • Para enviar a resposta, usa-se a opção reverse do xxd para voltar ao formato binário
  • Para aceitar conexões na porta TCP padrão do Minecraft, é usado ncat, que executa o script principal mc.sh quando uma conexão chega

Implementação dos tipos de dados do protocolo

  • O primeiro alvo mais viável de implementar foi o pacote Server List Ping
    • Ele não é obrigatório, então mesmo sem uma resposta correta o jogo ainda pode se conectar ao servidor
    • Ainda assim, é uma boa forma de aprender conceitos centrais do protocolo, como os data types

  • VarInt e VarLong

    • Os VarInt/VarLong do Minecraft são uma variação de LEB128, familiar para quem já mexeu com MQTT
    • LEB128 é um formato comprimido que armazena inteiros dividindo cada byte em 1 bit de sinalização e 7 bits de dados
    • Se o primeiro bit for 0, aquele byte é o último; se for 1, há outro byte em seguida
    • Como era difícil portar a implementação de referência diretamente para Bash, foi criado um codificador próprio usando módulo e divisão
    • O decodificador foi implementado de forma semelhante à referência, usando operação AND e multiplicação
    • Mais incômodo do que o próprio LEB128 era o fato de ele aparecer por todo o protocolo misturado com int, long e signed short comuns

  • Ponto flutuante IEEE 754

    • A conversão de IEEE 754 Double foi uma das partes mais irritantes da implementação
    • A implementação básica exige um loop com potências negativas, mas o Bash não oferece suporte nativo a isso
    • Perl foi evitado, e o bc aparentemente não suportava exponenciação no ambiente usado ou naquela versão do BusyBox
    • O awk conseguia lidar com potências negativas como 2**-1, então foi usado na implementação da conversão
    • A implementação inicial era tão lenta que levava vários minutos para processar cerca de 50 a 100 pacotes enviados pelo cliente no pacote Player Move, com 3 Doubles X·Y·Z em cada um
    • A estrutura que chamava awk repetidamente dentro de um loop for do Bash foi movida para um loop interno do próprio awk, reduzindo a quantidade de chamadas externas
    • Depois disso, a conversão caiu para cerca de 10 ms em um Xeon E5-2680v2
    • O valor anterior de cerca de 350 ms não era uma medição muito confiável

  • Tipo de dado Position

    • Position é um tipo de dado criado pela Mojang com base em um Long de 64 bits
    • X fica nos 26 bits superiores, Z nos 26 bits do meio e Y nos 12 bits inferiores
    • Como o Bash tem os operadores de bitshift necessários, a implementação foi simples
    • Ainda assim, esse tipo não é muito usado, e muitos pacotes armazenam as coordenadas X·Y·Z como valores Double separados
    • Com isso, os dados de posição crescem de 64 bits para 192 bits por pacote
    • Assumindo que só seja necessário chegar até o world border padrão de 30.000.000, isso dá precisão de ponto flutuante de 9 dígitos
    • A comunicação normal do servidor usa zlib, e para representar posição dentro de blocos provavelmente não são necessários mais que 2 ou 3 dígitos decimais na prática

  • NBT

    • NBT é um formato interno da Mojang, algo parecido com JSON para dados binários
    • Assim como JSON, também é usado para armazenar dados arbitrários fora da especificação
    • A Mojang, por exemplo, armazena bitstreams de tamanho variável em arrays de Long
    • Se o array não estiver alinhado a Long ou byte, o último Long é preenchido com 0
    • O parser de NBT quase chegou a ficar pronto, mas no fim foi considerado sem valor suficiente para justificar o esforço
    • Esse código foi perdido em um crash do sistema enquanto o projeto usava bastante tmpfs como diretório de trabalho

Criando um servidor ao qual dá para se conectar

  • Depois do Server Ping, o próximo passo foi tratar o handshake e os pacotes adicionais necessários para uma conexão real ao jogo
  • Para o cliente entrar no servidor, ele precisa concluir o handshake e receber pacotes de chunk, posição do jogador, inventário e Join Game
  • O maior obstáculo estava nas estruturas de dados internas do pacote Join Game e dos pacotes de chunk

  • Join Game

    • O pacote Join Game envia os metadados iniciais
    • Entre os itens incluídos estão o entity ID do jogador, gamemode, informações do mundo e o Dimension codec, presente a partir de versões em torno do Minecraft 1.16
    • Como o Dimension codec é um NBT Compound, o custo de implementação era alto
    • O Witchcraft reutiliza esse campo NBT obtido de um servidor vanilla
    • Essa é a única parte em blob binário da implementação; seria possível reimplementar, mas não foi considerado necessário personalizá-la

  • Chunk Data And Update Light

    • O pacote Chunk Data And Update Light parece grande e complexo à primeira vista, mas fica simples se vários campos BitSet forem deixados como 0x00 e o campo Block Entity não for enviado
    • Os campos que sobram são X, Y, heightmaps e o campo Data
    • Os heightmaps são uma forma mais complexamente codificada de repetir b000000010, e na prática parece que quase qualquer valor serve

Tratamento de Chunk Section e palette

  • O campo Data é um array de Chunk Section
  • Uma Chunk Section tem blocos 16×16×16, e várias sections podem ser empilhadas para formar um Chunk
  • Para simplificar a implementação, esse array usa apenas um único elemento
  • Uma Chunk Section é composta de block count, block states container e biome container
  • Os containers de block states e de biome usam uma estrutura de palette
    • Antes dos dados reais dos blocos, o servidor precisa definir o mapeamento entre IDs locais de bloco e IDs globais de bloco
    • É uma estrutura pensada para colocar o máximo possível de dados no menor espaço possível
    • A definição de bloco pode chegar ao mínimo de 4 bits
  • O Witchcraft usa 8 bits por bloco em vez do mínimo de 4 bits, por facilidade de gerenciamento
    • Isso permite 256 entradas possíveis na palette
    • Os dados reais do chunk podem então simplesmente enviar números hexadecimais apontando para entradas da palette
    • Uma palette de 4 bits também seria fácil de manipular com strings hexadecimais, já que um byte representa dois blocos, mas limitaria o chunk a 16 blocos
  • O padrão permite de 4 bits por bloco até 9 bits por bloco; fora disso, considera-se um mapeamento direto de palette com 15 bits por bloco
  • A palette de biome é tratada de forma separada
    • Envia-se uma palette vazia e faz-se o mapeamento direto do biome ID 0x01, isto é, minecraft:plains, para todas as regiões do chunk
    • Isso foi baseado em engenharia reversa do comportamento do vanilla
    • Há suspeita de que a documentação existente dessa parte do pacote possa estar incorreta

Estrutura de plugins baseada em hooks e demos

  • Como a implementação básica só mostrava chunks comuns, era preciso uma demo que mostrasse que o servidor podia fazer mais do que apenas exibir chunks
  • Para não criar uma árvore de código separada para cada demo, funções sobreponíveis foram chamadas de hooks, permitindo que o servidor carregasse código do usuário
  • Com essa estrutura, foi possível ir de mudanças no formato do mundo até ligar pkt_effect para fazer o jogador emitir ticking noise ao mover o mouse
  • Um plugin de exemplo gera chunks escolhendo blocos aleatórios da palette padrão
    • Em hook_chunks(), chama-se chunk_header
    • Para os 4096 blocos, acrescenta-se um valor hexadecimal de RANDOM%30
    • O chunk gerado é salvo em $TEMP/world/0000000000000000
    • Em seguida, pkt_chunk é chamado várias vezes para enviar chunks nas coordenadas ao redor
  • Outra demo, digmeout, é um jogo simples baseado em pontuação
    • O jogador é lançado em um chunk com pedra e minérios distribuídos aleatoriamente
    • O objetivo é minerar os minérios mais valiosos até o fim do tempo limite

Limitações do Witchcraft

  • O Bash é muito fraco para lidar com frações decimais
    • Inteiros até podem ser tratados razoavelmente bem
    • Frações decimais precisam ser manipuladas multiplicando na entrada e inserindo o ponto na posição apropriada na saída
    • Por causa disso, a maioria ou talvez todos os números tratados pelo Witchcraft são int
  • O multiplayer não funciona direito
    • Até funciona em algum nível, mas não foi investido tempo para concluir ou polir isso
  • O Witchcraft é tecnicamente um servidor multithread
    • Como resultado, foi necessário um hack ruim para comunicação entre threads
    • A maior parte dos dados globais fica armazenada em /dev/shm/witchcraft, referenciado internamente como $TEMP
  • O desempenho continua sendo uma limitação importante
    • Principalmente porque a troca de dados entre várias threads é lenta
    • É difícil enviar grandes volumes de dados, e gerar e enviar 16 chunks sólidos pode levar até 1 segundo
  • Atualmente, ele só roda se o BusyBox 1.35.0 mais recente estiver instalado
    • Não foi testado com GNU coreutils, e a expectativa é de que não funcione

Referências

Leituras relacionadas

1 comentários

 
GN⁺ 2024-03-04
Opiniões no Hacker News

  • Como alguém que já trabalhou bastante com servidores Minecraft programáveis para Java e Bedrock, isso é bem impressionante
    Ganha pontos extras por ter usado “duckduckgoing” numa frase

  • Discussão da época: https://news.ycombinator.com/item?id=30347501 — 92 comentários

  • Expoente negativo é só 2^(-n) = 1/(2^n)
    Achei curioso o autor não ter lembrado disso, mesmo tendo dado 2^-1 = 0.5 como exemplo, e no fim ter passado para o awk

    • De todo modo, Bash não dá suporte a números de ponto flutuante, então não sei como isso ajudaria o autor

  • Ele deveria ter usado minha biblioteca idiota(?) ctypes.sh: https://github.com/taviso/ctypes.sh
    Aí dá para acessar libm, poll(), select() e coisas do tipo a partir do Bash :)

    • Não sei se precisava ir tão longe, mas só pela imprudência já é impressionante
      Dá a sensação de ressuscitar Frankenstein
    • É legal, mas se afasta um pouco da essência de escrever em Bash algo que, tecnicamente, não tem motivo nenhum para precisar ser Bash
      Se exige até código C compilado instalado à parte para o Bash, então também daria para exigir simplesmente C ou Python, e fica mais fraco chamar isso de “escrito em Bash”. Digo isso com todo respeito, e eu gosto desse tipo de projeto “inútil”
      Dito isso, esse projeto de Minecraft também depende de ferramentas externas como xxd, então neste caso usar ctypes.sh não pioraria nada; na verdade, faz sentido
      A propósito, dá para ler, armazenar, manipular, calcular e emitir binário em Bash puro, mesmo sem dd ou xxd. O único byte problemático é o nulo; não dá para armazená-lo diretamente, mas dá para detectar e registrar que ele foi lido e depois restaurá-lo na saída, ou usá-lo como valor numérico em índices de array, offsets de bytes etc.
      Um exemplo mínimo para copiar um arquivo binário é while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Mas isso é basicamente fazer cat sem cat, então a utilidade não fica muito evidente
      Há um exemplo mais geral e útil em https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705
      Combinando LANG=C, IFS= e -d'', dá para acessar todos os bytes exceto 0x00, e pelo valor de retorno de read() dá para distinguir “li 0x00”, “não li nada” e “a entrada acabou”
      Também não é preciso usar < e > no comando while() inteiro. Você pode abrir com exec 3<>file_or_fifo_or_tty e, dentro do loop, usar read -u3, printf >&3 etc.
      Um exemplo de leitura de porta serial está em https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, e o código que usei de fato está em https://github.com/bkw777/pdd.sh. Veja tpdd_read, tpdd_write, file_to_fhex, str_to_shex: eles leem e escrevem portas seriais e arquivos locais, processando os dados de várias formas
      Esses loops nem sequer são subprocessos, muito menos processos externos. Se você manipular variáveis dentro do loop, continua no mesmo contexto original. Como não há processo filho, fica até estranho chamar de shell pai
      Os exemplos leem um byte por vez com read -n 1, mas não precisa ser assim. Se você ler sem -n1, cada iteração do loop coleta o máximo de dados possível entre nulos, usando menos memória e menos iterações
      No meu uso, preciso recortar e manipular bytes individuais e intervalos de bytes por offset numérico, e os dados são pequenos para os padrões atuais, então um array de pares hexadecimais é muito conveniente. a[n] == byte n, e dá para tratar caracteres imprimíveis, não imprimíveis e nulos da mesma forma; além de salvar e recriar com printf, também dá para usar diretamente como valor numérico, como 0x$n ou 0x${a[n]}
      Por exemplo, dá para ler o segundo byte de h[] como o tamanho do payload seguinte e recortar esse payload com ${h[@]:2:0x${h[1]}}
    • Uau, o que foi que eu acabei de ler? Sensacional. Instalei na hora. Também quero fazer parte do problema
    • Ah, legal :) E oi, tavis
    • Quero ver como poll() e select() funcionam desse jeito

  • É isso que faz de um site um verdadeiro site hacker. Excelente

  • Não sou bom em programação Bash, mas me surpreende que, na prática, ela seja mais poderosa e menos horrível do que parece

  • Bash é uma das minhas ferramentas favoritas, junto com vim e Lua
    É um binário único de menos de 2 MB, está em todo lugar e faz muito mais coisas do que muita gente imagina
    Com shellcheck e boas práticas, Bash também pode ficar legível e seguro
    Se precisar de mais alguma coisa, dá para acoplar utilitários em C/C++ sem uma FFI complicada, sem precisar puxar um monte de dependências obscuras com pip/npm

    • Minha coisa favorita a fazer com shellcheck é colocá-lo no CI. Aquele golpe que os desenvolvedores odeiam!
      É comum haver scripts Bash inline dentro do CI e do Dockerfile, e também gosto de mover tudo isso para arquivos de script separados. Agora que há shellcheck no CI, esse código também é verificado
      Os desenvolvedores reclamam que “piora a legibilidade”, mas, longe de piorar, fica muito mais seguro
      O próximo problema é que o mesmo script Bash acaba duplicado no mesmo arquivo em vários repositórios. É uma estrutura de build distribuída; estou aberto a ideias de melhoria
    • Odeio Bash porque não sou bom nele. Mesmo sendo meio ruim, muitas vezes ainda é a melhor solução possível
      Me arrependo de não ter investido mais tempo nisso quando era estudante. Foi uma das poucas ferramentas que me acompanharam por toda a carreira

  • Fico me perguntando se ainda existe gente criando servidores customizados para jogos comerciais

    • No Minecraft, isso é muito ativo
      A versão Java, em especial, está numa posição relativamente peculiar: continua recebendo grandes atualizações gratuitas de conteúdo, tem suporte oficial para rodar todas as versões antigas, e a comunidade de mods é extremamente ativa
      Minecraft (Java) é tanto um jogo quanto algo mais próximo de uma engine de jogos sobre a qual outras pessoas constroem
    • Em alguns jogos, não só há servidores como também clientes: https://runelite.net/
    • Acho que sempre vai existir para pessoas que gostam de mexer com tecnologia enquanto jogam
      Elas fazem isso para corrigir bugs, aprender uma linguagem ou ver como as coisas funcionam por dentro
    • Pelo que sei, a área de engenharia reversa ainda está ativa

  • Minecraft é um dos melhores jogos lançados desde Quake

  • Meu Deus, isso realmente aconteceu
    Já li muitos textos sobre abordagens de implementação, mas este é esmagador. É tranquilamente um dos melhores textos de projetos estranhos que já li, e é realmente excelente