Bagaimana cara kerja malloc () dan gratis ()?

Saya ingin tahu bagaimana mallocdan freebekerja.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Saya akan sangat berterima kasih jika jawabannya mendalam pada tingkat memori, jika memungkinkan.

OK beberapa jawaban tentang malloc sudah diposting.

Bagian yang lebih menarik adalah cara kerja gratis (dan ke arah ini, malloc juga dapat dipahami dengan lebih baik).

Dalam banyak implementasi malloc / gratis, bebas biasanya tidak mengembalikan memori ke sistem operasi (atau setidaknya hanya dalam kasus yang jarang terjadi). Alasannya adalah bahwa Anda akan mendapatkan celah di tumpukan Anda dan dengan demikian itu bisa terjadi, bahwa Anda baru saja menghabiskan 2 atau 4 GB memori virtual Anda dengan kesenjangan. Ini harus dihindari, karena begitu memori virtual selesai, Anda akan berada dalam masalah besar. Alasan lainnya adalah, bahwa OS hanya dapat menangani potongan memori yang berukuran dan sejajar. Untuk lebih spesifik: Biasanya OS hanya dapat menangani blok yang dapat ditangani oleh manajer memori virtual (paling sering kelipatan 512 byte misalnya 4KB).

Jadi mengembalikan 40 Bytes ke OS tidak akan berfungsi. Jadi apa yang dilakukan gratis?

Gratis akan menempatkan blok memori dalam daftar blokir sendiri. Biasanya ia juga mencoba untuk menyatukan blok yang berdekatan di ruang alamat. Daftar blokir gratis hanyalah daftar bundar memori yang memiliki beberapa data administratif pada awalnya. Ini juga alasan mengapa mengelola elemen memori yang sangat kecil dengan standar malloc / gratis tidak efisien. Setiap potongan memori membutuhkan data tambahan dan dengan ukuran yang lebih kecil terjadi fragmentasi lebih banyak.

Daftar bebas juga merupakan tempat pertama yang dilihat malloc ketika sepotong memori baru diperlukan. Itu dipindai sebelum memanggil memori baru dari OS. Ketika potongan ditemukan yang lebih besar dari memori yang dibutuhkan, itu dibagi menjadi dua bagian. Satu dikembalikan ke penelepon, yang lain dimasukkan kembali ke daftar gratis.

Ada banyak optimasi berbeda untuk perilaku standar ini (misalnya untuk potongan memori kecil). Tetapi karena malloc dan bebas harus sangat universal, perilaku standar selalu menjadi kelemahan ketika alternatif tidak dapat digunakan. Ada juga optimisasi dalam menangani daftar-bebas - misalnya menyimpan potongan-potongan dalam daftar yang diurutkan berdasarkan ukuran. Tetapi semua optimasi juga memiliki keterbatasan mereka sendiri.

Mengapa kode Anda rusak:

Alasannya adalah bahwa dengan menulis 9 chars (jangan lupa trailing byte nol) ke dalam area berukuran untuk 4 chars, Anda mungkin akan menimpa data administrasi yang disimpan untuk sepotong memori lain yang berada "di belakang" potongan data Anda ( karena data ini paling sering disimpan "di depan" potongan memori). Ketika bebas kemudian mencoba untuk memasukkan potongan Anda ke dalam daftar gratis, ia dapat menyentuh data administrasi ini dan karena itu tersandung pada penunjuk yang ditimpa. Ini akan merusak sistem.

Ini adalah perilaku yang agak anggun. Saya juga telah melihat situasi di mana pointer pelarian di suatu tempat memiliki data yang ditimpa dalam daftar bebas memori dan sistem tidak segera crash tetapi beberapa subrutin kemudian. Bahkan dalam sistem dengan kompleksitas sedang masalah seperti itu bisa sangat, sangat sulit untuk di-debug! Dalam satu kasus saya terlibat, kami butuh (sekelompok besar pengembang) beberapa hari untuk menemukan alasan crash - karena berada di lokasi yang sama sekali berbeda dari yang ditunjukkan oleh dump memori. Itu seperti bom waktu. Anda tahu, "bebas" atau "malloc" Anda berikutnya akan macet, tetapi Anda tidak tahu mengapa!

Itulah beberapa masalah C / C ++ terburuk, dan salah satu alasan mengapa pointer bisa sangat bermasalah.

Seperti kata aluser di utas forum ini :

Proses Anda memiliki wilayah memori, dari alamat x ke alamat y, disebut heap. Semua data malloc'd Anda tinggal di area ini. malloc () menyimpan beberapa struktur data, katakanlah daftar, dari semua ruang kosong di heap. Ketika Anda memanggil malloc, ia akan mencari potongan yang cukup besar untuk Anda, mengembalikan pointer ke dalamnya, dan mencatat fakta bahwa itu tidak gratis lagi serta seberapa besar itu. Saat Anda memanggil free () dengan pointer yang sama, free () mencari seberapa besar chunk itu dan menambahkannya kembali ke daftar chunks gratis (). Jika Anda memanggil malloc () dan tidak dapat menemukan potongan yang cukup besar di heap, ia menggunakan syscall brk () untuk menumbuhkan heap, yaitu meningkatkan alamat y dan menyebabkan semua alamat antara y lama dan y baru untuk menjadi memori yang valid. brk () harus berupa syscall;

malloc () bergantung pada sistem / kompiler sehingga sulit untuk memberikan jawaban spesifik. Namun pada dasarnya ia melacak memori apa yang dialokasikan dan tergantung pada bagaimana melakukannya sehingga panggilan Anda untuk bebas bisa gagal atau berhasil.

malloc() and free() don't work the same way on every O/S.

Salah satu implementasi malloc / gratis melakukan hal berikut:

1. Dapatkan blok memori dari OS melalui sbrk () (Panggilan Unix).
2. Buat header dan footer di sekitar blok memori dengan beberapa informasi seperti ukuran, izin, dan di mana blok berikutnya dan sebelumnya berada.
3. Ketika panggilan ke malloc masuk, daftar direferensikan yang menunjuk ke blok dengan ukuran yang sesuai.
4. Blok ini kemudian dikembalikan dan header dan footer diperbarui sesuai.

Perlindungan memori memiliki granularitas halaman dan akan membutuhkan interaksi kernel

Kode contoh Anda pada dasarnya bertanya mengapa program contoh tidak menjebak, dan jawabannya adalah bahwa perlindungan memori adalah fitur kernel dan hanya berlaku untuk seluruh halaman, sedangkan pengalokasi memori adalah fitur perpustakaan dan mengelola .. tanpa penegakan .. sewenang-wenang .. sewenang-wenang blok berukuran yang seringkali jauh lebih kecil dari halaman.

Memori hanya dapat dihapus dari program Anda dalam satuan halaman, dan bahkan itu tidak mungkin diamati.

calloc (3) dan malloc (3) berinteraksi dengan kernel untuk mendapatkan memori, jika perlu. Tetapi sebagian besar implementasi bebas (3) tidak mengembalikan memori ke kernel ¹ , mereka hanya menambahkannya ke daftar bebas yang calloc () dan malloc () akan berkonsultasi nanti untuk menggunakan kembali blok yang dirilis.

Bahkan jika free () ingin mengembalikan memori ke sistem, itu akan memerlukan setidaknya satu halaman memori yang berdekatan untuk mendapatkan kernel untuk benar-benar melindungi wilayah, jadi melepaskan blok kecil hanya akan menyebabkan perubahan perlindungan jika itu adalah yang terakhir blok kecil di halaman.

Jadi blok Anda ada di sana, duduk di daftar gratis. Anda hampir selalu dapat mengaksesnya dan memori terdekat seolah-olah itu masih dialokasikan. C mengkompilasi langsung ke kode mesin dan tanpa pengaturan debug khusus tidak ada pemeriksaan kewarasan pada beban dan toko. Sekarang, jika Anda mencoba dan mengakses blok gratis, perilaku tersebut tidak ditentukan oleh standar agar tidak membuat tuntutan yang tidak masuk akal pada pelaksana perpustakaan. Jika Anda mencoba dan mengakses memori yang bebas atau meory di luar blok yang dialokasikan, ada berbagai hal yang bisa salah:

• Kadang-kadang pengalokasi mempertahankan blok memori yang terpisah, kadang-kadang mereka menggunakan header yang mereka alokasikan sebelum atau sesudah ("catatan kaki", saya kira) blok Anda, tetapi mereka mungkin hanya ingin menggunakan memori di dalam blok untuk tujuan menjaga daftar gratis terhubung bersama. Jika demikian, Anda membaca blokir itu OK, tetapi isinya dapat berubah, dan menulis ke blok tersebut akan menyebabkan pengalokasi untuk bertingkah buruk atau macet.
• Secara alami, blok Anda mungkin dialokasikan di masa depan, dan kemudian kemungkinan akan ditimpa oleh kode Anda atau rutin perpustakaan, atau dengan nol oleh calloc ().
• Jika blok dialokasikan kembali, mungkin juga ukurannya berubah, dalam hal ini lebih banyak tautan atau inisialisasi akan ditulis di berbagai tempat.
• Tentunya Anda dapat referensi sejauh ini di luar jangkauan sehingga Anda melewati batas salah satu segmen program yang dikenal dengan kernel, dan dalam hal ini Anda akan menjebak.

Teori Operasi

Jadi, bekerja mundur dari contoh Anda ke teori keseluruhan, malloc (3) mendapatkan memori dari kernel saat dibutuhkan, dan biasanya dalam satuan halaman. Halaman-halaman ini dibagi atau dikonsolidasikan sesuai kebutuhan program. Malloc dan bebas bekerja sama untuk memelihara direktori. Mereka menyatu blok bebas yang berdekatan bila mungkin untuk dapat memberikan blok besar. Direktori mungkin melibatkan atau tidak menggunakan memori dalam blok yang dibebaskan untuk membentuk daftar yang ditautkan. (Alternatifnya adalah sedikit lebih banyak shared-memory dan paging-friendly, dan itu melibatkan mengalokasikan memori khusus untuk direktori.) Malloc dan gratis memiliki sedikit jika ada kemampuan untuk menegakkan akses ke blok individu bahkan ketika kode debugging khusus dan opsional dikompilasi ke dalam program.

^{1. Fakta bahwa sangat sedikit implementasi dari upaya free () untuk mengembalikan memori ke sistem belum tentu disebabkan oleh implementor yang malas. Berinteraksi dengan kernel jauh lebih lambat daripada hanya mengeksekusi kode perpustakaan, dan manfaatnya akan kecil. Sebagian besar program memiliki kondisi mapan atau jejak memori yang meningkat, sehingga waktu yang dihabiskan untuk menganalisis tumpukan yang mencari memori yang dapat dikembalikan akan benar-benar terbuang. Alasan lain termasuk fakta bahwa fragmentasi internal membuat blok yang disejajarkan dengan halaman tidak mungkin ada, dan kemungkinan bahwa mengembalikan blok akan memecah blok di kedua sisi. Akhirnya, beberapa program yang mengembalikan memori dalam jumlah besar kemungkinan akan memotong malloc () dan tetap mengalokasikan dan membebaskan halaman.}

Secara teori, malloc mendapatkan memori dari sistem operasi untuk aplikasi ini. Namun, karena Anda mungkin hanya ingin 4 byte, dan OS perlu bekerja di halaman (sering 4k), malloc melakukan sedikit lebih dari itu. Dibutuhkan halaman, dan menempatkan informasi itu sendiri di sana sehingga dapat melacak apa yang telah Anda alokasikan dan dibebaskan dari halaman itu.

Ketika Anda mengalokasikan 4 byte, misalnya, malloc memberi Anda pointer ke 4 byte. Apa yang mungkin tidak Anda sadari adalah bahwa memori 8-12 byte sebelum 4 byte Anda digunakan oleh malloc untuk membuat rantai semua memori yang telah Anda alokasikan. Saat Anda menelpon gratis, dibutuhkan pointer Anda, mencadangkan ke tempat datanya, dan mengoperasikannya.

Saat Anda mengosongkan memori, malloc mengeluarkan memori itu dari rantai ... dan mungkin atau mungkin tidak mengembalikan memori itu ke sistem operasi. Jika ya, daripada mengakses memori itu mungkin akan gagal, karena OS akan mengambil izin Anda untuk mengakses lokasi itu. Jika malloc menyimpan memori (karena memiliki hal-hal lain yang dialokasikan di halaman itu, atau untuk beberapa optimasi), maka akses tersebut akan berfungsi. Itu masih salah, tetapi mungkin berhasil.

PENOLAKAN: Apa yang saya jelaskan adalah implementasi umum malloc, tetapi tidak berarti satu-satunya yang mungkin.

Garis strcpy Anda mencoba menyimpan 9 byte, bukan 8, karena terminator NUL. Ini memunculkan perilaku yang tidak terdefinisi.

Panggilan untuk bebas mungkin atau mungkin tidak macet. Memori "setelah" 4 byte alokasi Anda dapat digunakan untuk hal lain oleh implementasi C atau C ++ Anda. Jika ini digunakan untuk sesuatu yang lain, maka mencoret-coret seluruh itu akan menyebabkan "sesuatu yang lain" menjadi salah, tetapi jika itu tidak digunakan untuk hal lain, maka Anda bisa lolos begitu saja. "Meloloskan diri dengan itu" mungkin terdengar bagus, tetapi sebenarnya buruk, karena itu berarti kode Anda akan tampak berjalan OK, tetapi pada masa yang akan datang Anda mungkin tidak lolos begitu saja.

Dengan pengalokasi memori gaya debugging, Anda mungkin menemukan bahwa nilai penjaga khusus telah ditulis di sana, dan bebas memeriksa nilai itu dan panik jika tidak menemukannya.

Jika tidak, Anda mungkin menemukan bahwa 5 byte berikutnya termasuk bagian dari simpul tautan milik beberapa blok memori lain yang belum dialokasikan. Membebaskan blok Anda bisa melibatkan menambahkannya ke daftar blok yang tersedia, dan karena Anda telah menulis di simpul daftar, operasi itu dapat mengubah pointer dengan nilai yang tidak valid, menyebabkan crash.

Itu semua tergantung pada pengalokasi memori - implementasi yang berbeda menggunakan mekanisme yang berbeda.

Cara kerja malloc () dan free () tergantung pada pustaka runtime yang digunakan. Secara umum, malloc () mengalokasikan heap (blok memori) dari sistem operasi. Setiap permintaan ke malloc () kemudian mengalokasikan sebagian kecil dari memori ini menjadi mengembalikan pointer ke pemanggil. Rutin alokasi memori harus menyimpan beberapa informasi tambahan tentang blok memori yang dialokasikan untuk dapat melacak memori yang digunakan dan membebaskan pada heap. Informasi ini sering disimpan dalam beberapa byte sebelum pointer dikembalikan oleh malloc () dan dapat berupa daftar blok memori yang ditautkan.

Dengan menulis melewati blok memori yang dialokasikan oleh malloc () Anda kemungkinan besar akan menghancurkan beberapa informasi pembukuan blok berikutnya yang mungkin merupakan sisa blok memori yang tidak digunakan.

Satu tempat di mana program Anda mungkin macet adalah ketika menyalin terlalu banyak karakter ke buffer. Jika karakter tambahan terletak di luar tumpukan, Anda mungkin mendapatkan pelanggaran akses saat Anda mencoba menulis ke memori yang tidak ada.

Ini tidak ada hubungannya dengan malloc dan gratis. Program Anda menunjukkan perilaku yang tidak terdefinisi setelah Anda menyalin string - itu bisa macet pada titik itu atau pada titik mana pun setelahnya. Ini akan benar bahkan jika Anda tidak pernah menggunakan malloc dan gratis, dan mengalokasikan array char di stack atau secara statis.

malloc dan gratis tergantung pada implementasi. Implementasi tipikal melibatkan mempartisi memori yang tersedia ke dalam "daftar bebas" - daftar tertaut dari blok memori yang tersedia. Banyak implementasi secara artifisial membaginya menjadi objek kecil vs besar. Blok gratis dimulai dengan informasi tentang seberapa besar blok memori dan di mana yang berikutnya, dll.

Ketika Anda malloc, blok ditarik dari daftar gratis. Ketika Anda bebas, blok dimasukkan kembali ke daftar gratis. Kemungkinannya adalah, ketika Anda menimpa ujung pointer Anda, Anda menulis di header blok dalam daftar gratis. Saat Anda mengosongkan memori, free () mencoba melihat blok berikutnya dan mungkin akhirnya mengenai pointer yang menyebabkan kesalahan bus.

Yah itu tergantung pada implementasi pengalokasi memori dan OS.

Di bawah windows misalnya proses dapat meminta satu halaman atau lebih dari RAM. OS kemudian menugaskan halaman-halaman itu ke proses. Namun ini bukan memori yang dialokasikan untuk aplikasi Anda. Alokasi memori CRT akan menandai memori sebagai blok "tersedia" yang berdekatan. Alokasi memori CRT kemudian akan dijalankan melalui daftar blok gratis dan menemukan blok sekecil mungkin yang dapat digunakan. Kemudian akan mengambil sebanyak itu blok yang diperlukan dan menambahkannya ke daftar "dialokasikan". Terlampir ke kepala alokasi memori aktual akan menjadi header. Header ini akan berisi berbagai bit informasi (itu bisa, misalnya, berisi blok yang dialokasikan berikutnya dan sebelumnya untuk membentuk daftar tertaut. Kemungkinan besar akan berisi ukuran alokasi).

Gratis kemudian akan menghapus header dan menambahkannya kembali ke daftar memori bebas. Jika membentuk blok yang lebih besar dengan blok bebas di sekitarnya, ini akan ditambahkan bersama untuk memberikan blok yang lebih besar. Jika seluruh halaman sekarang bebas, pengalokasi akan, kemungkinan besar, mengembalikan halaman ke OS.

Ini bukan masalah sederhana. Bagian pengalokasi OS sepenuhnya di luar kendali Anda. Saya sarankan Anda membaca sesuatu seperti Doug Lea's Malloc (DLMalloc) untuk mendapatkan pemahaman tentang bagaimana pengalokasi yang cukup cepat akan bekerja.

Sunting: Kecelakaan Anda akan disebabkan oleh fakta bahwa dengan menulis lebih besar dari alokasi, Anda telah menimpa tajuk memori berikutnya. Dengan cara ini ketika dibebaskan itu menjadi sangat bingung untuk apa sebenarnya itu free'ing dan bagaimana untuk bergabung ke dalam blok berikut. Ini mungkin tidak selalu menyebabkan kerusakan langsung saat gratis. Ini dapat menyebabkan kerusakan nanti. Secara umum, hindari menimpa memori!

Program Anda macet karena menggunakan memori yang bukan milik Anda. Ini dapat digunakan oleh orang lain atau tidak - jika Anda beruntung Anda crash, jika tidak masalahnya mungkin tetap tersembunyi untuk waktu yang lama dan kembali dan menggigit Anda nanti.

Sejauh implementasi malloc / gratis - seluruh buku dikhususkan untuk topik ini. Pada dasarnya pengalokasi akan mendapatkan potongan memori yang lebih besar dari OS dan mengelolanya untuk Anda. Beberapa masalah yang harus ditangani oleh pengalokasi adalah:

• Cara mendapatkan memori baru
• Cara menyimpannya - (daftar atau struktur lain, beberapa daftar untuk potongan memori dengan ukuran berbeda, dan sebagainya)
• Apa yang harus dilakukan jika pengguna meminta lebih banyak memori daripada yang tersedia saat ini (meminta lebih banyak memori dari OS, bergabung dengan beberapa blok yang ada, bagaimana cara menggabungkannya dengan tepat, ...)
• Apa yang harus dilakukan ketika pengguna membebaskan memori
• Debug pengalokasi dapat memberikan Anda potongan yang lebih besar yang Anda minta dan mengisinya beberapa pola byte, ketika Anda membebaskan memori pengalokasi dapat memeriksa apakah menulis di luar blok (yang mungkin terjadi dalam kasus Anda) ...

Sulit dikatakan karena perilaku aktual berbeda antara kompiler / runtime yang berbeda. Bahkan debug / rilis build memiliki perilaku berbeda. Debug build dari VS2005 akan menyisipkan marker di antara alokasi untuk mendeteksi kerusakan memori, jadi alih-alih crash, ini akan menyatakan secara gratis ().

Penting juga untuk menyadari bahwa hanya dengan memindahkan pointer program break sekitar brkdan sbrktidak benar-benar mengalokasikan memori, itu hanya mengatur ruang alamat. Di Linux, misalnya, memori akan "didukung" oleh halaman fisik yang sebenarnya ketika rentang alamat itu diakses, yang akan mengakibatkan kesalahan halaman, dan pada akhirnya akan mengarah ke pemanggilan kernel ke pengalokasi halaman untuk mendapatkan halaman dukungan.