Gesaan dan konteks
Satu subsistem kernel mesti mengekalkan banyak julat integer yang tidak bertindih dengan operasi carian (lookup), sisipan (insert), pemadaman (delete) dan lelaran jurang (gap iteration). Terangkan struktur Maple Tree, akses serentak, kekangan peruntukan dan cara anda mengesahkan migrasi daripada struktur lama.
Dokumentasi kernel Linux menerangkan Maple Tree sebagai B-tree yang dioptimumkan untuk julat yang tidak bertindih. Ia menyimpan indeks titik dan julat, menyokong mod peruntukan biasa dan terhad, serta boleh dibaca di bawah kuncinya atau dengan RCU. Temu duga ini menguji kitaran hayat, penguncian dan semantik peruntukan dan bukannya sekadar mendakwa bahawa ia "lebih pantas daripada red-black tree."
Perkara yang dinilai oleh penemu duga
Penemu duga mencari perbezaan antara nilai indeks, nilai julat dan jurang (gap); penjelasan tentang pemisahan nod, penggabungan dan keadaan operasi; pengendalian GFP, kunci, pengiraan rujukan dan RCU yang betul; pemeliharaan ciri tidak bertindih, susunan lelaran dan semantik pemadaman semasa migrasi; serta penanda aras yang merangkumi keserentakan dan tekanan memori.
Soalan penjelasan
Model julat
Sahkan sama ada julat adalah tertutup, sama ada titik akhir boleh menjadi integer maksimum, sama ada julat bersebelahan boleh bergabung, sama ada jurang mempunyai makna dan sama ada satu indeks memetakan kepada satu objek.
Keserentakan dan konteks
Sahkan sama ada pemanggil berjalan dalam konteks proses, gangguan (interrupt) atau tidak boleh tidur (non-sleepable); sama ada pembaca boleh menggunakan RCU; dan sama ada penulis bergantung pada kunci dalaman Maple Tree atau kunci luaran.
Sasaran migrasi
Sahkan kerumitan struktur lama, belanjawan memori, ABI yang stabil, alatan penyahpepijatan dan kod ralat yang mesti kekal serasi. Migrasi tidak boleh dinilai berdasarkan pemprosesan (throughput) bebenang tunggal semata-mata.
Jawapan 30 saat
"Maple Tree menggunakan nod B-tree berorientasikan julat untuk memadatkan indeks dan selang, yang sesuai untuk julat tidak bertindih dan pertanyaan jurang. Kemas kini biasa boleh memperuntukkan memori dengan peraturan GFP; laluan atomik atau non-sleepable memerlukan keadaan operasi yang disediakan dan peruntukan terhad. Pembaca boleh menggunakan kunci, atau di bawah RCU mereka memperoleh rujukan objek sebelum meninggalkan bahagian baca. Saya akan mewujudkan invariant dan perbandingan penulisan dwi (dual-write), menguji sempadan, jurang, pemadaman, keserentakan dan tekanan memori, kemudian membandingkan kependaman dan jejak memori beban kerja sebenar."
Penyelesaian langkah demi langkah
Langkah 1: Tentukan invariant julat
Nyatakan indeks mula dan tamat bagi setiap entri, sama ada nilai kosong dibenarkan dan sama ada julat bersebelahan bergabung. Setiap operasi sisip, ganti dan padam mesti mengekalkan sifat tidak bertindih, dengan tingkah laku yang jelas untuk limpahan titik akhir dan julat kosong.
Langkah 2: Fahami nod dan keadaan operasi
Nod Maple Tree menyimpan berbilang pangsi (pivots) dan slot, mengurangkan kedalaman penunjuk dan meningkatkan lokaliti julat. Lelaran atau kemas kini yang kompleks boleh menggunakan ma_state untuk kedudukan semasa dan konteks operasi; jangan gunakan semula keadaan merentasi sempadan keserentakan yang tidak disokong.
Langkah 3: Pilih mod peruntukan
Kemas kini biasa boleh memperuntukkan dengan GFP_KERNEL dan tidur (sleep). Laluan non-sleepable memerlukan pra-peruntukan atau bendera GFP terhad dan keadaan operasi yang disediakan. Jangan sekali-kali memanggil laluan peruntukan yang berpotensi tidur semasa memegang spinlock atau di dalam bahagian baca RCU.
Langkah 4: Reka bentuk ketekalan bacaan
Bacaan berasaskan kunci adalah mudah. Dengan RCU, dapatkan rujukan atau salin data yang diperlukan sebelum meninggalkan bahagian RCU. Pelepasan objek mesti menyelaraskan pengiraan rujukan, panggilan balik (callbacks) dan pemadaman pepohon; melindungi nod sahaja tidak melindungi jangka hayat nilai.
Langkah 5: Laksanakan carian julat dan jurang
Carian pada sesuatu indeks mengembalikan julat yang meliputi atau tiada nilai. Lelaran jurang diteruskan dari penghujung entri sebelumnya supaya sempadan pertama dan terakhir tidak dilangkau. Pelerap (iterator) merekodkan indeks seterusnya dan mengendalikan pemadaman serentak serta indeks maksimum; "tiada nilai" tidak secara automatik bermaksud akhir lelaran.
lookup(index):
lock_or_rcu_read()
entry = maple_lookup(index)
if entry != null:
refcount_inc(entry.owner)
unlock_or_rcu_read()
return entry
find_gap(start, end):
state = maple_state(start)
while state.index <= end:
range = maple_next_range(state)
if gap_before(range, state.index): return [state.index, range.start - 1]
state.index = range.end + 1
return [state.index, end]Langkah 6: Migrasikan struktur lama
Kekalkan struktur lama sebagai punca kebenaran (source of truth) semasa membina penulisan dwi atau indeks sampingan. Bandingkan sempadan rawak, sisipan bertindih, jurang selepas pemadaman dan bacaan serentak. Tukar laluan baca hanya selepas kod ralat, susunan kunci, kegagalan peruntukan dan tingkah laku pemulihan sepadan.
Langkah 7: Sahkan penambahbaikan dan buat pengunduran (rollback)
Rekod persentil kependaman untuk carian, lelaran julat, carian jurang dan kemas kini, bersama-sama dengan memori nod, kegagalan peruntukan dan masa menunggu kunci. Kekalkan suis ciri dan pembilang ketekalan; henti dan undur (rollback) jika berlaku perbezaan daripada menggantikan ujian beban kerja pengeluaran dengan satu penanda aras mikro semata-mata.
Jawapan model
Saya akan mentakrifkan invariant tidak bertindih, titik akhir dan jurang terlebih dahulu, kemudian menyimpan julat dalam B-tree berorientasikan julat Maple Tree. Laluan biasa yang boleh tidur boleh menggunakan GFP_KERNEL; laluan non-sleepable menyediakan keadaan dan mengelakkan peruntukan di dalam bahagian kunci atau RCU. Pembaca sama ada memegang kunci atau memperoleh rujukan objek di bawah RCU sebelum menggunakannya, dengan pengiraan rujukan melindungi jangka hayat nilai. Saya akan melakukan penulisan dwi semasa migrasi dan membandingkan tingkah laku carian, jurang, pemadaman dan sempadan, kemudian menukar menggunakan metrik kependaman, memori dan kegagalan peruntukan sambil mengekalkan pelaksanaan lama sebagai laluan pengunduran (rollback).
Kesilapan lazim
- Kesilapan: Menganggap Maple Tree sebagai pemetaan kunci titik (point-key map). → Sebab ia gagal: Nilainya terletak pada julat yang tidak bertindih dan operasi jurang. → Penyelesaian: Tentukan titik akhir, carian liputan dan lelaran jurang.
- Kesilapan: Memanggil kemas kini yang berpotensi tidur di bawah spinlock atau dalam bahagian baca RCU. → Sebab ia gagal: Konteks peruntukan GFP tidak boleh tidur di situ. → Penyelesaian: Pra-peruntukkan, pilih mod yang betul dan asingkan sempadan kunci.
- Kesilapan: Melindungi nod pepohon sahaja, bukan objek nilai. → Sebab ia gagal: Nilai boleh dibebaskan selepas kunci dilepaskan. → Penyelesaian: Salin atau ambil rujukan sebelum meninggalkan bahagian RCU atau kunci.
- Kesilapan: Hanya mengukur pemprosesan carian semasa migrasi. → Sebab ia gagal: Pemisahan, pemadaman, jurang dan tekanan memori boleh mendominasi. → Penyelesaian: Bandingkan julat yang realistik, keserentakan dan senario kegagalan peruntukan.
Soalan susulan dan respons
Maple Tree atau red-black tree?
Untuk kunci titik tertib yang mudah, red-black tree mungkin sudah mencukupi. Set julat tidak bertindih yang besar, pertanyaan jurang dan lokaliti lebih memihak kepada Maple Tree. Biarkan metrik beban kerja dan keserentakan menentukan.
Bilakah anda akan menggunakan RCU?
Gunakan ia untuk laluan yang banyak membaca dengan pertikaian kunci yang rendah apabila nilai boleh dituntut semula dengan selamat selepas tempoh bertenang (grace period). Jika pembaca mesti mengubah suai objek dengan serta-merta atau rujukan tidak dapat diuruskan, akses berasaskan kunci adalah lebih jelas.
Mengapakah mtree_erase() boleh memerlukan GFP_KERNEL?
Pemadaman boleh mencetuskan penstrukturan semula nod atau kerja peruntukan yang berkaitan, jadi konteks pemanggil mesti membenarkan operasi memori yang diperlukan. Laluan non-sleepable memerlukan antara muka terhad yang didokumenkan dan keadaan yang disediakan.
Bagaimanakah anda membuktikan bahawa tiada jurang yang dilangkau?
Hasilkan model yang tepat dengan sempadan lengkap, julat bersebelahan, indeks maksimum dan pemadaman rawak; bandingkan setiap titik akhir jurang, termasuk pemadaman serentak dan permulaan semula pelerap (iterator).