Geekly articles weekly

Mengembangkan OS seperti Unix yang monolitik - Heap (4)

Pada artikel sebelumnya, kami menerapkan log sistem kernel. Sekarang saatnya menerapkan manajer memori dinamis.

Daftar isi


  1. Membangun sistem (make, gcc, gas). Boot awal (multiboot). Luncurkan (qemu). Pustaka C (strcpy, memcpy, strext).
  2. Pustaka C (sprintf, strcpy, strcmp, strtok, va_list ...). Membangun perpustakaan dalam mode kernel dan mode aplikasi pengguna.
  3. Log sistem kernel. Memori video Output ke terminal (kprintf, kpanic, kassert).
  4. Memori dinamis, tumpukan (kmalloc, kfree).
  5. Organisasi memori dan penanganan interupsi (GDT, IDT, PIC, syscall). Pengecualian
  6. Memori virtual (direktori halaman dan tabel halaman).
  7. Proses Perencana Multitasking. Panggilan sistem (bunuh, keluar, ps).
  8. Sistem file kernel (initrd), elf, dan internalnya. Panggilan sistem (exec).
  9. Driver perangkat karakter. Panggilan sistem (ioctl, fopen, fread, fwrite). Pustaka C (fopen, fclose, fprintf, fscanf).
  10. Shell sebagai program lengkap untuk kernel.
  11. Mode perlindungan pengguna (ring3). Segmen Status Tugas (tss).

Memori kernel dinamis. Banyak


Antarmuka heap kernel akan terlihat seperti ini:

void *kmalloc(size_t size); void kfree(void *addr);

Karena belum ada tumpukan, catatan wilayah memori yang ditempati dan bebas harus disimpan.
dalam array ukuran terbatas. Semakin kecil dimensi, semakin rendah kapasitas tumpukan
fragmen kecil. Di Linux, misalnya, banyak struktur kernel disimpan dalam dapat digunakan kembali
memori yang tidak berubah ukuran saat dirilis (lempengan). Tapi kami masih jauh dari ini,
karena pembangunan adalah proses berulang.

Elemen apa pun yang berniat menjadi elemen daftar yang disusun melalui array
diperlukan untuk mengimplementasikan antarmuka.

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed);

Tidak ada antarmuka dalam C, tetapi mereka tidak diperlukan. Kami cukup melemparkan pointer dari objek apa pun ke tipe struct slist_head_t * jika objek ini secara fisik terlihat seperti ini:

 struct my_list_entry_t { struct slist_head_t list_head; ... }

Tetapi agar algoritma yang digeneralisasi mengetahui dimensi dari array di mana daftar akan disimpan
dan ukuran elemennya, elemen pertama dan terakhir dari daftar dan alamat array di mana
daftar disimpan, setiap fungsi dari daftar operasi akan membutuhkan pointer lain
ke struktur definisi daftar:

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; };

Fungsi untuk mengoperasikan daftar akan terlihat seperti ini:

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry);

Sisipkan Algoritma Fungsi:
Temukan slot gratis di array.
Isi dengan elemen baru.
Perbaiki pointer dari item daftar yang berdekatan secara logis (bukan fisik).
Tandai slot sebagai sibuk.
Sesuaikan awal dan akhir daftar.

Algoritma fungsi yang dihapus dari daftar:
Perbaiki pointer dari item daftar yang berdekatan secara logis (bukan fisik).
Sesuaikan awal dan akhir daftar.
Tandai slot sebagai gratis.

Memori dinamis dijelaskan oleh daftar dengan item berikut:

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed);

Array yang menggambarkan memori dinamis dari catatan tersebut terlihat seperti ini:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES];

Menentukan daftar wilayah memori terlihat seperti ini:

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks};

Jadi, kami telah menggambarkan memori dinamis. Semua memori dalam rentang tertentu
dibagi menjadi blok ukuran sewenang-wenang, yang masing-masing dapat kosong,
baik sibuk. Selain itu, setiap blok dijelaskan oleh elemen array dengan flag is_valid = true,
yang merupakan item daftar.

Sekarang pertimbangkan algoritma pengalokasi tumpukan paling sederhana (kmalloc):
Jika tidak ada blok gratis, pilih blok baru dari ukuran yang diperlukan (tetapi tidak lebih dari ukuran heap maksimum).

Kalau tidak, kami melihat melalui semua blok gratis. Jika kami menemukan blok gratis, lihat ukurannya. Jika sudah cukup, ambillah. Jika ada surplus maka buat blok kosong baru dengan ukuran kelebihan. Jika tidak, jika tidak mencukupi dan yang terakhir, kami memperluas batas tumpukan (tetapi tidak lebih dari maksimum).

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; }

Algoritma bebas memori akan serupa (kfree):
Temukan blok yang alamatnya dimulai dengan alamat yang akan dibebaskan. Pastikan dia sibuk. Tandai sebagai gratis.

Jika ada tetangga bebas di sebelah kanan atau kiri untuk bersatu dengannya dalam satu blok.

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); }

Itu saja. Sampai waktu berikutnya!

Referensi


Sekarang, buka tutorial video
Dan perhatikan repositori git secara paralel (Anda membutuhkan cabang lesson4)

Referensi


1. James Molloy. Gulung mainan Anda sendiri UNIX-clone OS.
2. Gigi. Assembler untuk DOS, Windows, Unix
3. Kalashnikov. Assembler mudah!
4. Tanenbaum. Sistem operasi. Implementasi dan pengembangan.
5. Robert Love. Kernel Linux Deskripsi proses pengembangan.

Source: https://habr.com/ru/post/id466831/

More articles:


All Articles