BerandaComputers and TechnologyWhen Seekdir () Won't Seek to the Right Position (2008)

When Seekdir () Won't Seek to the Right Position (2008)

Suatu hari, saya mendapat email dari Edd, pengguna OpenBSD, mengklaim bahwa Samba akan macet saat menyajikan file dari sistem file MS-DOS. Ini adalah Samba yang dibangun dari sumber dan bukan dari port. Karena saya sering menggunakan Samba sendiri dan untuk basis pengguna yang cukup besar, saya tertarik dengan masalah ini dan mulai menyelidikinya. Apa yang saya temukan pada akhirnya adalah kejutan dan tidak diharapkan: Bug yang telah ada di semua BSD hampir sepanjang waktu, sejak masa 4.2BSD atau sekitar 25 tahun …

Cache Direktori Samba

Masalah dengan seekdir () Dalam kode pengganti Samba saya menemukan komentar berikut, menyatakan masalah dari sudut pandang Samba:

 “Ini diperlukan karena penanganan direktori sudah ada di FreeBSD  dan OpenBSD (dan mungkin NetBSD) tidak menangani unlink () dengan benar  pada file di direktori tempat telldir () telah digunakan. Di blok  boundary terkadang akan kehilangan file saat seekdir () digunakan  kembali ke posisi yang sebelumnya direkam dengan telldir ().   Ini juga memperbaiki masalah kinerja dan penggunaan memori yang parah  telldir () di sistem BSD. Setiap panggilan ke telldir () di BSD menambahkan  masuk ke daftar tertaut, dan entri itu dibersihkan  closedir (). Ini berarti dengan direktori besar closedir () dapat mengambil file  jumlah waktu yang sewenang-wenang, menyebabkan waktu tunggu jaringan jutaan  entri telldir () dibebaskan " 

Ternyata ada dua masalah: seekdir () tidak kembali ke posisi semula diambil menggunakan telldir () dan masalah kinerja. Sebelum menggali lebih jauh ke dalam kode sumber, saya memutuskan untuk memeriksa dokumentasi fungsi tersebut, hanya untuk memastikan, mereka digunakan seperti seharusnya digunakan. Halaman manual OpenBSD jelas: Fungsi seekdir () mengatur posisi berikutnya readdir () operasi pada direktori aliran dirp bernama. Posisi baru akan kembali ke posisi yang terkait dengan aliran direktori ketika operasi telldir () dilakukan. Nilai yang dikembalikan oleh telldir () hanya baik selama masa pakai pointer DIR, dirp, dari mana nilai tersebut diturunkan. Jika direktori ditutup dan kemudian dibuka kembali, nilai telldir () mungkin tidak valid karena pemadatan direktori yang tidak terdeteksi. Jika Anda tidak menutup aliran direktori, seekdir () akan membawa Anda kembali ke posisi previsouly yang diperoleh menggunakan telldir (). Jika sistem berperilaku berbeda, mungkin itu bug atau dokumentasinya salah. Jika sistem memang tidak membawa Anda kembali ke posisi yang benar, mengapa kita memiliki fungsi-fungsi ini sejak awal? Melihat fungsi closedir () di OpenBSD mengungkapkan bahwa pernyataan yang dibuat oleh orang-orang Samba tentang kinerja di closedir () salah: Di OpenBSD tidak ada daftar tertaut, tetapi skema penanganan memori yang lebih cerdas diimplementasikan oleh Otto Moerbeek (otto @) . FreeBSD, bagaimanapun, memang menggunakan daftar tertaut, tetapi mereka dapat beralih ke kode kami kapan saja. Jadi masalah kinerja benar-benar bukan masalah.

Berburu seekdir () Bug

Sebagai pembuat asli pustaka dir (), Anda mungkin memperbaiki salah satu bug saya 🙂 Sebelum perintah dir (), program hanya membuka, membaca, dan menafsirkan direktori secara langsung. Saya harus memperbarui 22 program yang mengejutkan (sebagian besar program yang tersedia di UNIX pada saat itu) untuk mengganti interpretasi langsung direktori mereka dengan panggilan perpustakaan dir (). (Kirk McKusick; komunikasi pribadi)

Yang saya butuhkan adalah program uji coba untuk menjalankan fungsi-fungsi ini dan pada akhirnya memicu perilaku yang mencegah orang Samba mengaktifkan cache direktori pada sistem BSD. Saya menulis program C yang kira-kira melakukan langkah-langkah berikut:

  1. Buat direktori dan isi dengan sejumlah file
  2. Iterasi di atas direktori menggunakan readdir (), merekam posisi entri menggunakan telldir () sebelum readdir (), dan menyimpan nilai yang diperoleh dalam array
  3. Hapus sejumlah file secara acak dan juga tandai sebagai dihapus dalam array dalam memori
  4. Iterasi di atas larik dalam memori, lewati entri yang ditandai sebagai dihapus, dan seekdir () ke yang lain, lakukan readdir () dan bandingkan nilai yang dikembalikan dengan salinan dalam memori
  5. Keluarkan pesan ketika salinan dalam memori dan nilai yang dikembalikan oleh readdir () berbeda

Jeremy memberi tahu saya bahwa masalah terjadi pada direktori besar, jadi saya memulai pengujian dengan direktori yang sangat besar (hingga 250’000 entri ) dan cukup cepat saya menemukan masalah tersebut. seekdir () tidak akan mengembalikan saya ke posisi yang direkam. Hal seperti ini menegaskan masalah yang dialami orang Samba selama lebih dari tiga tahun. Saya mengubah nilai program pengujian saya, untuk melihat apakah saya dapat menemukan pola. Tetapi melihat ribuan posisi direktori, nama file, nomor inode di mana lebih mungkin membuat saya gila daripada menemukan masalah … Saya mulai menurunkan angka dan yang mengejutkan saya, saya dapat memicu masalah hanya dengan 10 atau 20 file dan menghapus salah satunya. Tiba-tiba, saya mendapat kasus yang menunjukkan masalah pada setiap proses, tidak ada lagi keacakan: Buat 28 file, hapus file 25 dan seekdir ke file 26: Anda berakhir di file 27! Menatap output dari program saya, saya tiba-tiba melihat pola sejelas mungkin: Membuat direktori dengan 28 file telah membuat direktori yang mencakup lebih dari satu blok pada disk (2 dalam kasus ini). File 25 adalah entri pertama dari blok kedua. Jelas masalah terjadi saat Anda menghapus entri pertama di blok direktori dan kemudian kembali ke posisi rekaman entri kedua di blok yang sama. Ini benar-benar akan memberi Anda satu entri jauh. Saat itu saya telah melibatkan Otto untuk membantu saya dan untuk mengkonfirmasi temuan saya. Reaksi pertamanya: Masalah yang menarik …;) Kami menyelidiki lebih lanjut dan saya mulai melihat kode kernel yang menghapus entri direktori serta kode perpustakaan di libc yang mengimplementasikan seekdir () dan teman-teman.

Bagaimana Entri Direktori yang Dihapus Kernel

Fungsi kernel untuk menghapus entri direktori, ufs_dirremove (), memang memperlakukan entri yang terletak di awal blok secara berbeda dari yang lain:

         jika (dp-> i_count==0) {                 / Entri pertama di blok: set d_ino ke nol.                  /                 ep-> d_ino=0;         } lain {                 / Ciutkan ruang kosong baru ke entri sebelumnya.                  /                 ep-> d_reclen +=dp-> i_reclen;         } 

Jika ini adalah entri pertama dalam sebuah blok, nomor inode disetel ke nol, sehingga entri tersebut tidak valid. Untuk semua entri lainnya, panjang rekaman dari rekaman yang akan dihapus ditambahkan ke panjang rekaman entri sebelumnya. Karena pustaka menggunakan field record length dari sebuah entri untuk melanjutkan ke entri berikutnya dalam readdir (), ini secara efektif berarti bahwa entri yang dihapus, ketika masih dalam blok pada disk, tidak akan digunakan lagi.

Bagaimana Perpustakaan C Mengakses Entri Direktori

Pustaka C mengimplementasikan fungsi opendir (), telldir (), readdir (), seekdir (), dan closedir (). Fungsi ini ditulis dalam waktu 4.2BSD sehingga program UNIX tidak perlu menangani direktori sendiri.

 / dapatkan entri berikutnya dalam direktori.  / int _readdir_unlocked (hasil DIR dirp, struct dirent  {         struct dirent dp;          hasil=NULL;         untuk (;;) {                 jika (dirp-> dd_loc>=dirp-> dd_size)                         dirp-> dd_loc=0;                 jika (dirp-> dd_loc==0) {                         dirp-> dd_size=getdirentries (dirp-> dd_fd,                             dirp-> dd_buf, dirp-> dd_len, & dirp-> dd_seek);                         jika (dirp-> dd_size==0)                                 kembali (0);                         jika (dirp-> dd_size  dd_buf + dirp-> dd_loc);                 if ((long) dp & 03) / cek pointer palsu /                         kembali (-1);                 jika (dp-> d_reclen  d_reclen> dirp-> dd_len + 1 - dirp-> dd_loc)                         kembali (-1);                 dirp-> dd_loc +=dp-> d_reclen;                  jika (dp-> d_ino==0)                         terus;                 hasil=dp;                 kembali (0);         } } 

Pada pandangan pertama, kode ini terlihat benar. Ini akan melewati entri yang dihapus dengan nomor inode yang disetel ke nol dan sebaliknya akan menggunakan panjang rekaman. Dan karena direktori traversal menggunakan readdir () berfungsi dengan baik, ini adalah kode yang bekerja secara efektif. Melihat lebih dekat implementasi library seekdir () akhirnya mengungkap masalah:

 / mencari entri dalam direktori.  Hanya nilai yang dikembalikan oleh "telldir" yang harus diteruskan ke seekdir.  / kosong __seekdir (DIR dirp, lokasi panjang) {         struct ddloc lp;         struct dirent dp;          jika (loc =dirp-> dd_td-> td_loccnt)                 kembali;         lp=& dirp-> dd_td-> td_locs [loc];         dirp-> dd_td-> td_last=loc;         jika (lp-> loc_loc==dirp-> dd_loc && lp-> loc_seek==dirp-> dd_seek)                 kembali;         (batal) lseek (dirp-> dd_fd, (off_t) lp-> loc_seek, SEEK_SET);         dirp-> dd_seek=lp-> loc_seek;         dirp-> dd_loc=0;         while (dirp-> dd_loc  loc_loc) {                 _readdir_unlocked (dirp, & dp);                 jika (dp==NULL)                         istirahat;         } } 

Kode ini tidak akan berfungsi seperti yang diharapkan ketika mencari entri kedua dari blok di mana yang pertama telah dihapus: seekdir () memanggil readdir () yang dengan senang hati melewatkan yang pertama entri (inode telah disetel ke nol), dan maju ke entri kedua. Saat pengguna sekarang memanggil readdir () untuk membaca entri direktori yang baru saja dia cari () ed, dia tidak mendapatkan entri kedua tetapi yang ketiga. Saya sangat terkejut karena saya tidak hanya menemukan masalah ini di semua BSD atau sistem turunan BSD seperti Mac OS X, tetapi juga di versi BSD yang sangat lama. Saya pertama kali memeriksa 4.4BSD Lite 2, dan Otto mengonfirmasi bahwa itu juga ada di 4.2BSD. Bug ini telah ada selama sekitar 25 tahun atau lebih.

Solusinya

Cara mengatasinya sangat sederhana, bukan berarti sepele: _readdir_unlocked () tidak boleh melewatkan entri direktori dengan inode yang disetel ke nol saat dipanggil dari __seekdir (). q.e.d. (dan maaf kami butuh hampir dua puluh lima tahun untuk memperbaikinya)

Terima kasih banyak kepada Jeremy Allison, Edd Barrett, Volker Lendecke, dan terutama kepada Otto Moerbeek atas bantuan dan saran mereka.

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments