/* 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); }