| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142 |
- /* Kernel heap allocator: power-of-two segregated free lists over mm.c. */
- #include "kmalloc.h"
- #include "mm.h"
- #define KMALLOC_MIN 16 /* smallest block (bytes) */
- #define KMALLOC_CLASSES 9 /* 16, 32, ..., 4096 (log2(4096)-log2(16)+1) */
- /* Block header: when allocated, first word = size; when free, first word =
- * the free-list link. The returned pointer is block + sizeof(header). */
- union km_block {
- struct { unsigned int size; } h;
- union km_block *next;
- };
- static union km_block *free_lists[KMALLOC_CLASSES];
- /* The free lists are shared by every process; the PIT must not switch in the
- * middle of a list update. mm_alloc_page()/mm_free_page() have their own
- * nested IRQ gates. */
- static inline unsigned int irq_save_disable(void)
- {
- unsigned int flags;
- __asm__ volatile ("pushfl; popl %0; cli" : "=r"(flags));
- return flags;
- }
- static inline void irq_restore(unsigned int flags)
- {
- __asm__ volatile ("pushl %0; popfl" : : "r"(flags));
- }
- static inline unsigned int round_up_pow2(unsigned int n)
- {
- n--;
- n |= n >> 1;
- n |= n >> 2;
- n |= n >> 4;
- n |= n >> 8;
- n |= n >> 16;
- return n + 1;
- }
- /* size is a power of two in [KMALLOC_MIN, PAGE_SIZE]. */
- static inline unsigned int size_class_of(unsigned int size)
- {
- unsigned int c = 0;
- while (size > KMALLOC_MIN) {
- size >>= 1;
- c++;
- }
- return c;
- }
- void kmalloc_init(void)
- {
- unsigned int i;
- for (i = 0; i < KMALLOC_CLASSES; i++)
- free_lists[i] = 0;
- }
- void *kmalloc(unsigned int size)
- {
- unsigned int total, cls, off, flags;
- union km_block *b;
- void *page;
- if (size == 0)
- size = 1;
- /* Round up (header + payload) to a power of two. */
- total = round_up_pow2(size + sizeof(unsigned int));
- if (total < KMALLOC_MIN)
- total = KMALLOC_MIN;
- flags = irq_save_disable();
- /* Large allocation: whole contiguous pages. */
- if (total > PAGE_SIZE) {
- unsigned int pages = (total + PAGE_SIZE - 1) / PAGE_SIZE;
- page = (void *)mm_alloc_pages(pages);
- if (!page) {
- irq_restore(flags);
- return 0;
- }
- ((union km_block *)page)->h.size = total;
- irq_restore(flags);
- return (void *)((unsigned int)page + sizeof(unsigned int));
- }
- cls = size_class_of(total);
- b = free_lists[cls];
- if (!b) {
- /* Refill this size class from a fresh page. */
- page = (void *)mm_alloc_page();
- if (!page) {
- irq_restore(flags);
- return 0;
- }
- for (off = 0; off + total <= PAGE_SIZE; off += total) {
- union km_block *blk =
- (union km_block *)((unsigned int)page + off);
- blk->next = free_lists[cls];
- free_lists[cls] = blk;
- }
- b = free_lists[cls];
- }
- free_lists[cls] = b->next;
- b->h.size = total;
- irq_restore(flags);
- return (void *)((unsigned int)b + sizeof(unsigned int));
- }
- void kfree(void *ptr)
- {
- union km_block *b;
- unsigned int size, cls, flags;
- if (!ptr)
- return;
- b = (union km_block *)((unsigned int)ptr - sizeof(unsigned int));
- size = b->h.size;
- flags = irq_save_disable();
- if (size > PAGE_SIZE) {
- unsigned int pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
- unsigned int addr = (unsigned int)b;
- unsigned int i;
- for (i = 0; i < pages; i++)
- mm_free_page(addr + i * PAGE_SIZE);
- irq_restore(flags);
- return;
- }
- cls = size_class_of(size);
- b->next = free_lists[cls];
- free_lists[cls] = b;
- irq_restore(flags);
- }
|