kmalloc.c 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
  1. /* Kernel heap allocator: power-of-two segregated free lists over mm.c. */
  2. #include "kmalloc.h"
  3. #include "mm.h"
  4. #define KMALLOC_MIN 16 /* smallest block (bytes) */
  5. #define KMALLOC_CLASSES 9 /* 16, 32, ..., 4096 (log2(4096)-log2(16)+1) */
  6. /* Block header: when allocated, first word = size; when free, first word =
  7. * the free-list link. The returned pointer is block + sizeof(header). */
  8. union km_block {
  9. struct { unsigned int size; } h;
  10. union km_block *next;
  11. };
  12. static union km_block *free_lists[KMALLOC_CLASSES];
  13. static inline unsigned int round_up_pow2(unsigned int n)
  14. {
  15. n--;
  16. n |= n >> 1;
  17. n |= n >> 2;
  18. n |= n >> 4;
  19. n |= n >> 8;
  20. n |= n >> 16;
  21. return n + 1;
  22. }
  23. /* size is a power of two in [KMALLOC_MIN, PAGE_SIZE]. */
  24. static inline unsigned int size_class_of(unsigned int size)
  25. {
  26. unsigned int c = 0;
  27. while (size > KMALLOC_MIN) {
  28. size >>= 1;
  29. c++;
  30. }
  31. return c;
  32. }
  33. void kmalloc_init(void)
  34. {
  35. unsigned int i;
  36. for (i = 0; i < KMALLOC_CLASSES; i++)
  37. free_lists[i] = 0;
  38. }
  39. void *kmalloc(unsigned int size)
  40. {
  41. unsigned int total, cls, off;
  42. union km_block *b;
  43. void *page;
  44. if (size == 0)
  45. size = 1;
  46. /* Round up (header + payload) to a power of two. */
  47. total = round_up_pow2(size + sizeof(unsigned int));
  48. if (total < KMALLOC_MIN)
  49. total = KMALLOC_MIN;
  50. /* Large allocation: whole contiguous pages. */
  51. if (total > PAGE_SIZE) {
  52. unsigned int pages = (total + PAGE_SIZE - 1) / PAGE_SIZE;
  53. page = (void *)mm_alloc_pages(pages);
  54. if (!page)
  55. return 0;
  56. ((union km_block *)page)->h.size = total;
  57. return (void *)((unsigned int)page + sizeof(unsigned int));
  58. }
  59. cls = size_class_of(total);
  60. b = free_lists[cls];
  61. if (!b) {
  62. /* Refill this size class from a fresh page. */
  63. page = (void *)mm_alloc_page();
  64. if (!page)
  65. return 0;
  66. for (off = 0; off + total <= PAGE_SIZE; off += total) {
  67. union km_block *blk =
  68. (union km_block *)((unsigned int)page + off);
  69. blk->next = free_lists[cls];
  70. free_lists[cls] = blk;
  71. }
  72. b = free_lists[cls];
  73. }
  74. free_lists[cls] = b->next;
  75. b->h.size = total;
  76. return (void *)((unsigned int)b + sizeof(unsigned int));
  77. }
  78. void kfree(void *ptr)
  79. {
  80. union km_block *b;
  81. unsigned int size, cls;
  82. if (!ptr)
  83. return;
  84. b = (union km_block *)((unsigned int)ptr - sizeof(unsigned int));
  85. size = b->h.size;
  86. if (size > PAGE_SIZE) {
  87. unsigned int pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
  88. unsigned int addr = (unsigned int)b;
  89. unsigned int i;
  90. for (i = 0; i < pages; i++)
  91. mm_free_page(addr + i * PAGE_SIZE);
  92. return;
  93. }
  94. cls = size_class_of(size);
  95. b->next = free_lists[cls];
  96. free_lists[cls] = b;
  97. }