Server Minecraft yang Dibuat dari Nol dengan Bash (2022)

 (sdomi.pl)
4 poin oleh GN⁺ 2024-03-04 | 1 komentar | Bagikan ke WhatsApp
  • Witchcraft adalah proyek eksperimen yang mengimplementasikan server Minecraft dari nol hanya dengan Bash, menargetkan koneksi klien sungguhan dengan menangani protokol biner, Join Game, hingga pengiriman chunk
  • Keterbatasan Bash yang tidak bisa mempertahankan null byte di dalam string diakali dengan memproses biner di dalam pipe dd dan xxd alih-alih menyimpannya ke variabel
  • Kesulitan implementasi berfokus pada format data khas Minecraft seperti VarInt/VarLong, floating point IEEE 754, Position, dan NBT; terutama konversi Double yang lambat karena biaya pemanggilan perintah eksternal
  • Server diperluas secara bertahap melalui urutan paket Server List Ping, handshake, Join Game, dan Chunk Data And Update Light; Dimension codec memakai blob biner NBT yang diambil dari server vanilla
  • Dengan plugin berbasis hook, pembuatan world dan efek bisa diubah, tetapi masih ada keterbatasan seperti multiplayer yang belum selesai, komunikasi thread berbasis /dev/shm/witchcraft, pertukaran data yang lambat, dan ketergantungan pada BusyBox 1.35.0

Menangani protokol Minecraft biner di Bash

  • Upaya awal menargetkan Classic protocol tahun 2009, tetapi segera terlihat batasannya: Bash sulit mem-parsing data biner dengan benar
  • String Bash mengabaikan null byte (0x00), dan tidak ada cara untuk mendeteksi apakah null byte muncul, sehingga data bisa rusak pada protokol biner yang ketat
  • Solusinya adalah menjaga data biner tetap berada di dalam pipe, bukan memasukkannya ke variabel Bash atau command substitution
    • dd count=$len bs=1 status=none | xxd -p dipakai untuk membaca jumlah byte yang dibutuhkan lalu mengubahnya menjadi string hex
    • Pencocokan pola, substitusi, dan ekstraksi data dilakukan di atas string hex
    • Pengiriman respons mengubahnya kembali menjadi biner dengan opsi reverse milik xxd
  • Untuk menerima koneksi pada port TCP default Minecraft, digunakan ncat, lalu saat ada koneksi masuk dijalankan skrip shell utama mc.sh

Implementasi tipe data protokol

  • Target paling cocok untuk diimplementasikan terlebih dahulu adalah paket Server List Ping
    • Ini bukan paket wajib, jadi meski server tidak merespons dengan benar, klien tetap bisa masuk ke game
    • Namun paket ini memudahkan pemahaman konsep inti protokol seperti data types

  • VarInt dan VarLong

    • VarInt/VarLong di Minecraft adalah varian LEB128 yang mungkin terasa familier bagi pengguna MQTT
    • LEB128 adalah metode kompresi untuk menyimpan panjang integer dengan membagi byte menjadi 1 bit sinyal dan 7 bit data
    • Jika bit pertama 0, byte itu adalah yang terakhir; jika 1, byte berikutnya masih berlanjut
    • Karena sulit memindahkan reference implementation apa adanya ke Bash, dibuat encoder sendiri dengan modulo dan pembagian
    • Decoder diimplementasikan mirip cara referensi dengan operasi AND dan perkalian
    • Yang lebih merepotkan daripada LEB128 itu sendiri adalah karena tipe ini muncul di seluruh protokol bercampur dengan int, long, dan signed short biasa

  • Floating point IEEE 754

    • Konversi IEEE 754 Double adalah salah satu bagian yang paling merepotkan dalam implementasi
    • Implementasi dasarnya memerlukan loop untuk menerapkan pangkat negatif, tetapi Bash tidak mendukung pangkat negatif secara bawaan
    • Perl dihindari, dan bc tampaknya tidak mendukung perpangkatan di lingkungan yang dipakai atau pada versi BusyBox tersebut
    • awk bisa menangani pangkat negatif seperti 2**-1, sehingga dipakai untuk implementasi konversi
    • Implementasi awal sangat lambat, sampai butuh beberapa menit untuk memproses sekitar 50~100 paket yang dikirim klien pada paket Player Move, masing-masing dengan 3 nilai Double X·Y·Z
    • Struktur yang semula berulang kali memanggil awk di dalam loop for Bash dipindahkan ke loop internal awk untuk mengurangi jumlah pemanggilan perintah eksternal
    • Setelah itu, konversinya turun menjadi sekitar 10ms pada Xeon E5-2680v2
    • Angka sekitar 350ms pada versi sebelumnya bukan hasil pengukuran yang benar-benar pasti

  • Tipe data Position

    • Position adalah tipe data berbasis Long 64-bit buatan Mojang
    • X disimpan di 26 bit teratas, Z di 26 bit tengah, dan Y di 12 bit terbawah
    • Bash memiliki operator bitshift yang diperlukan, jadi implementasinya cukup mudah
    • Namun tipe ini tidak terlalu sering digunakan, dan banyak paket justru menyimpan koordinat X·Y·Z sebagai nilai Double terpisah
    • Akibatnya, data posisi membesar dari 64 bit menjadi 192 bit per paket
    • Jika diasumsikan hanya perlu angka hingga world border bawaan 30.000.000, maka didapat ketelitian floating point 9 digit
    • Komunikasi server biasa memakai zlib, dan untuk representasi posisi di dalam blok secara realistis tidak perlu lebih dari 2~3 digit desimal

  • NBT

    • NBT adalah format internal Mojang, semacam JSON untuk data biner
    • Seperti JSON, format ini juga dipakai untuk menyimpan data arbitrer di luar spesifikasi formal
    • Misalnya, Mojang menyimpan bitstream panjang variabel sebagai array Long
    • Jika array tidak sejajar dengan Long atau byte, Long terakhir akan di-padding dengan 0
    • Parser NBT sempat hampir selesai, tetapi pada akhirnya dianggap tidak layak untuk dituntaskan
    • Kode tersebut hilang karena sistem crash saat direktori proyek banyak memakai tmpfs

Membuat server yang bisa dimasuki

  • Langkah setelah Server Ping adalah menangani handshake dan paket tambahan yang diperlukan agar benar-benar bisa masuk ke game
  • Agar klien bisa masuk ke server, handshake harus selesai dan klien harus menerima paket chunk, player position, inventory, serta join game
  • Hambatan terbesar adalah struktur data di dalam paket Join Game dan paket Chunk

  • Join Game

    • Paket Join Game mengirim metadata awal
    • Isinya mencakup entity ID pemain, gamemode, informasi world, dan Dimension codec yang hadir mulai sekitar Minecraft 1.16
    • Dimension codec adalah NBT Compound sehingga beban implementasinya besar
    • Witchcraft memakai field NBT ini dengan mengambilnya dari server vanilla
    • Bagian ini adalah satu-satunya blob biner dalam implementasi, dan meski bisa diimplementasikan ulang, dianggap tidak perlu dikustomisasi

  • Chunk Data And Update Light

    • Paket Chunk Data And Update Light awalnya terlihat besar dan rumit, tetapi menjadi sederhana jika beberapa field BitSet dibiarkan 0x00 dan field Block Entity tidak dikirim
    • Field yang tersisa adalah X, Y, heightmaps, dan field Data
    • heightmaps adalah bentuk pengkodean yang lebih rumit dari pengulangan b000000010, dan pada dasarnya dianggap bisa berisi nilai apa pun

Penanganan Chunk Section dan palette

  • Field Data adalah array Chunk Section
  • Chunk Section berisi blok 16×16×16, dan beberapa section dapat ditumpuk untuk membentuk satu Chunk
  • Untuk menyederhanakan implementasi, array ini hanya memakai satu elemen
  • Chunk Section terdiri dari block count, block states container, dan biome container
  • block states dan biome container memakai struktur palette
    • Sebelum data blok sebenarnya, server harus mendefinisikan pemetaan antara local block ID dan global block ID
    • Strukturnya dibuat agar sebanyak mungkin data muat di ruang sekecil mungkin
    • Definisi blok bisa diperkecil hingga minimal 4 bit
  • Demi kemudahan pengelolaan, Witchcraft memakai 8 bits per block alih-alih minimum 4 bit
    • Ini menyediakan 256 entri palette yang bisa dipakai
    • Data chunk yang sebenarnya cukup mengirim angka hex yang menunjuk ke entri palette
    • Palette 4 bit juga mudah ditangani karena satu byte pada string hex bisa mewakili dua blok, tetapi itu membatasi chunk menjadi 16 blok per chunk
  • Standarnya mengizinkan dari 4 bits per block sampai 9 bits per block, dan selain itu dianggap sebagai direct palette mapping 15 bits per block
  • Palette biome ditangani dengan cara terpisah
    • Mengirim palette kosong lalu memetakan biome ID 0x01, yaitu minecraft:plains, secara langsung ke semua region di dalam chunk
    • Ini berdasarkan hasil reverse engineering terhadap perilaku vanilla
    • Diduga dokumentasi yang ada untuk bagian paket ini bisa jadi tidak akurat

Struktur plugin berbasis hook dan demo

  • Implementasi dasar saja hanya menampilkan chunk biasa, sehingga dibutuhkan demo untuk menunjukkan bahwa server bisa melakukan lebih dari sekadar menampilkan chunk
  • Agar tidak perlu membuat source tree terpisah untuk tiap demo, fungsi-fungsi yang bisa dioverride disebut hooks, dan server dapat memuat kode pengguna
  • Dengan struktur ini, dimungkinkan mengubah bentuk world sampai menyambungkan pkt_effect agar saat menggerakkan mouse pemain mengeluarkan ticking noise
  • Plugin contoh membuat chunk dengan memilih blok acak dari palette bawaan
    • Di hook_chunks(), dipanggil chunk_header
    • Untuk 4096 blok, ditambahkan nilai hex dari RANDOM%30
    • Chunk yang dihasilkan disimpan ke $TEMP/world/0000000000000000
    • Lalu pkt_chunk dipanggil beberapa kali untuk mengirim chunk ke koordinat sekitar
  • Demo lain, digmeout, adalah game sederhana berbasis skor
    • Pemain dilempar ke chunk berisi batu dan bijih yang ditempatkan secara acak
    • Tujuannya menambang bijih paling bernilai hingga batas waktu habis

Keterbatasan Witchcraft

  • Bash sangat lemah dalam menangani pecahan desimal
    • Integer masih bisa ditangani sampai tingkat tertentu
    • Pecahan desimal harus diperlakukan dengan mengalikannya saat input lalu menaruh titik di posisi yang sesuai saat output
    • Karena itu, sebagian besar atau bahkan semua angka yang diproses Witchcraft adalah int
  • Multiplayer tidak benar-benar berfungsi dengan baik
    • Sampai taraf tertentu bisa jalan, tetapi tidak ada waktu yang dihabiskan untuk menyelesaikan atau memolesnya
  • Secara teknis, Witchcraft adalah multi-threaded server
    • Akibatnya dibutuhkan hack yang kurang baik untuk komunikasi antar-thread
    • Sebagian besar data global disimpan di bawah /dev/shm/witchcraft, yang secara internal dirujuk sebagai $TEMP
  • Performa tetap menjadi keterbatasan besar
    • Terutama pertukaran data antar beberapa thread yang lambat
    • Sulit mengirim data dalam jumlah besar, dan membuat lalu mengirim 16 solid chunk bisa memakan waktu hingga 1 detik
  • Saat ini hanya berjalan jika BusyBox 1.35.0 terbaru terpasang
    • Belum diuji dengan GNU coreutils, dan diperkirakan tidak akan berfungsi

Referensi

Bacaan terkait

1 komentar

 
GN⁺ 2024-03-04
Komentar Hacker News

  • Sebagai orang yang sudah banyak mengerjakan server Minecraft yang bisa diskrip untuk Java dan Bedrock, ini cukup mengesankan
    Poin plus juga karena memakai “duckduckgoing” di dalam kalimat

  • Diskusi saat itu: https://news.ycombinator.com/item?id=30347501 — 92 komentar

  • Eksponen negatif hanyalah 2^(-n) = 1/(2^n)
    Agak mengejutkan penulis tidak terpikir akan hal ini meski dalam contohnya sendiri sudah memakai 2^-1 = 0.5, dan akhirnya menyerahkannya ke awk

    • Bash toh memang tidak mendukung angka floating-point, jadi aku tidak tahu bagaimana itu membantu penulis

  • Seharusnya memakai library bodoh(?) buatanku, ctypes.sh: https://github.com/taviso/ctypes.sh
    Dengan begitu, libm, poll(), select(), dan semacamnya bisa diakses dari Bash :)

    • Entah apakah memang perlu sampai sejauh itu, tapi kenekatan itu saja sudah mengesankan
      Rasanya seperti menghidupkan kembali Frankenstein
    • Memang keren, tapi agak menyimpang dari esensi menulis sesuatu dengan Bash yang secara teknis sama sekali tidak perlu Bash
      Kalau sampai butuh kode C terkompilasi yang dipasang terpisah di Bash, ya sama saja bisa meminta C atau Python, jadi alasan untuk menyebutnya “ditulis dengan Bash” jadi lemah. Tentu ini kukatakan dengan hormat, dan aku suka proyek-proyek “tidak berguna” seperti ini
      Namun proyek Minecraft ini juga bergantung pada tool eksternal seperti xxd, jadi dalam kasus ini memakai ctypes.sh tidak akan lebih buruk, malah masuk akal
      Sebagai catatan, tanpa dd atau xxd pun kita bisa membaca, menyimpan, memanipulasi, menghitung, dan mencetak biner murni dengan Bash. Byte yang bermasalah hanya null; meski tidak bisa disimpan langsung, kita bisa mendeteksi dan mencatat fakta bahwa byte itu terbaca, lalu memulihkannya saat output nanti atau memakainya sebagai nilai angka untuk indeks array, offset byte, dan sebagainya
      Contoh minimal untuk menyalin file biner adalah while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Namun ini hanya seperti melakukan cat tanpa cat, jadi kegunaannya tidak terlalu terlihat
      Contoh yang lebih umum dan berguna ada di https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705
      Dengan kombinasi LANG=C, IFS=, dan -d'', semua byte selain 0x00 bisa diakses, dan dari nilai balik read() kita bisa membedakan “apakah membaca 0x00”, “apakah tidak membaca apa pun”, dan “apakah input sudah berakhir”
      Tidak perlu juga memakai < dan > untuk seluruh perintah while(). Buka saja dengan exec 3<>file_or_fifo_or_tty, lalu di dalam loop gunakan read -u3, printf >&3, dan seterusnya
      Contoh membaca dari port serial ada di https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, dan kode yang benar-benar kupakai ada di https://github.com/bkw777/pdd.sh. Lihat tpdd_read, tpdd_write, file_to_fhex, str_to_shex; semuanya membaca dan menulis port serial serta file lokal sambil memproses data dengan berbagai cara
      Loop-loop ini bahkan bukan proses eksternal, apalagi subshell. Variabel yang dimanipulasi di dalam loop tetap berada di konteks aslinya. Karena tidak ada child, menyebutnya parent shell pun agak janggal
      Contoh-contohnya membaca satu byte demi satu byte dengan read -n 1, tetapi itu tidak wajib. Jika membaca tanpa -n1, setiap iterasi loop akan mengumpulkan sebanyak mungkin data di antara null, sehingga memakai lebih sedikit memori dan jumlah iterasi
      Untuk kebutuhanku, aku harus memotong dan memanipulasi byte individual serta rentang byte berdasarkan offset numerik, dan datanya juga kecil menurut standar sekarang, jadi array pasangan heksadesimal sangat nyaman. Jadinya a[n] == byte n, semua karakter yang bisa dicetak, yang tidak bisa dicetak, dan null dapat diperlakukan sama, dan selain bisa disimpan/dibuat ulang dengan printf, nilainya juga bisa langsung dipakai sebagai angka seperti 0x$n atau 0x${a[n]}
      Misalnya, byte kedua dari h[] bisa dibaca sebagai panjang payload yang mengikutinya, lalu payload itu dipotong dengan ${h[@]:2:0x${h[1]}}
    • Wah, barusan aku membaca apa? Hebat. Langsung kupasang. Aku juga ingin menjadi bagian dari masalah
    • Oh keren :) dan halo tavis
    • Aku ingin melihat bagaimana poll() dan select() bekerja dengan cara seperti ini

  • Nah, ini baru benar-benar situs hacker. Luar biasa

  • Aku tidak jago pemrograman Bash, tapi mengejutkan bahwa pada praktiknya Bash lebih kuat dan tidak semengerikan yang dibayangkan

  • Bash adalah salah satu tool favoritku, setara dengan vim dan Lua
    Ia berupa satu binary kurang dari 2MB, ada di mana-mana, dan bisa melakukan jauh lebih banyak hal daripada yang dipikirkan banyak orang
    Dengan shellcheck dan kebiasaan yang baik, Bash juga bisa dibuat mudah dibaca dan aman
    Kalau butuh hal lain, cukup tempelkan utility C/C++ tanpa FFI yang rumit, dan tidak perlu menarik banyak dependency entah dari mana lewat pip/npm dan semacamnya

    • Hal yang paling kusukai dengan shellcheck adalah memasukkannya ke CI. Jurus yang dibenci developer!
      Sering ada skrip Bash inline di dalam CI dan Dockerfile, dan aku juga suka memindahkan semuanya ke file skrip terpisah. Sekarang karena ada shellcheck di CI, kode-kode itu juga diperiksa
      Developer tidak suka karena katanya “mengurangi keterbacaan”, padahal bukannya kurang terbaca, justru jauh lebih aman
      Masalah berikutnya adalah skrip Bash yang sama diduplikasi ke file yang sama di beberapa repository. Ini struktur build terdistribusi, dan aku terbuka kalau ada ide perbaikan
    • Aku tidak suka Bash karena tidak begitu mahir memakainya. Meski kurang enak, Bash masih sering menjadi solusi terbaik yang tersedia
      Aku menyesal tidak lebih banyak meluangkan waktu saat masih mahasiswa. Karena Bash ternyata salah satu dari sedikit tool yang terus mengikutiku sepanjang karier

  • Aku penasaran apakah membuat server kustom untuk game komersial masih ada sampai sekarang

    • Di Minecraft, itu sangat aktif
      Khususnya versi Java berada di posisi yang cukup unik: terus mendapat update konten besar gratis, tetapi tetap secara resmi mendukung menjalankan semua versi lama, dan komunitas modding-nya juga sangat aktif
      Minecraft (Java) adalah game sekaligus nyaris seperti game engine yang di atasnya orang lain membangun sesuatu
    • Bukan hanya server; beberapa game juga punya klien: https://runelite.net/
    • Menurutku ini akan selalu ada bagi orang yang suka bermain game sambil mengutak-atik teknologi
      Mereka melakukannya untuk memperbaiki bug, belajar bahasa, atau ingin melihat cara kerja bagian dalamnya
    • Setahuku, ranah reverse engineering masih aktif

  • Minecraft adalah salah satu game terbaik yang muncul setelah Quake

  • Astaga, tidak menyangka hal seperti ini benar-benar terjadi
    Aku sudah membaca banyak tulisan tentang cara implementasi, tetapi yang ini luar biasa. Ini jelas salah satu tulisan proyek aneh terbaik yang pernah kubaca, dan benar-benar tulisan yang hebat