kmalloc.c 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
  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. /* The free lists are shared by every process; the PIT must not switch in the
  14. * middle of a list update. mm_alloc_page()/mm_free_page() have their own
  15. * nested IRQ gates. */
  16. static inline unsigned int irq_save_disable(void)
  17. {
  18. unsigned int flags;
  19. __asm__ volatile ("pushfl; popl %0; cli" : "=r"(flags));
  20. return flags;
  21. }
  22. static inline void irq_restore(unsigned int flags)
  23. {
  24. __asm__ volatile ("pushl %0; popfl" : : "r"(flags));
  25. }
  26. static inline unsigned int round_up_pow2(unsigned int n)
  27. {
  28. n--;
  29. n |= n >> 1;
  30. n |= n >> 2;
  31. n |= n >> 4;
  32. n |= n >> 8;
  33. n |= n >> 16;
  34. return n + 1;
  35. }
  36. /* size is a power of two in [KMALLOC_MIN, PAGE_SIZE]. */
  37. static inline unsigned int size_class_of(unsigned int size)
  38. {
  39. unsigned int c = 0;
  40. while (size > KMALLOC_MIN) {
  41. size >>= 1;
  42. c++;
  43. }
  44. return c;
  45. }
  46. void kmalloc_init(void)
  47. {
  48. unsigned int i;
  49. for (i = 0; i < KMALLOC_CLASSES; i++)
  50. free_lists[i] = 0;
  51. }
  52. void *kmalloc(unsigned int size)
  53. {
  54. unsigned int total, cls, off, flags;
  55. union km_block *b;
  56. void *page;
  57. if (size == 0)
  58. size = 1;
  59. /* Round up (header + payload) to a power of two. */
  60. total = round_up_pow2(size + sizeof(unsigned int));
  61. if (total < KMALLOC_MIN)
  62. total = KMALLOC_MIN;
  63. flags = irq_save_disable();
  64. /* Large allocation: whole contiguous pages. */
  65. if (total > PAGE_SIZE) {
  66. unsigned int pages = (total + PAGE_SIZE - 1) / PAGE_SIZE;
  67. page = (void *)mm_alloc_pages(pages);
  68. if (!page) {
  69. irq_restore(flags);
  70. return 0;
  71. }
  72. ((union km_block *)page)->h.size = total;
  73. irq_restore(flags);
  74. return (void *)((unsigned int)page + sizeof(unsigned int));
  75. }
  76. cls = size_class_of(total);
  77. b = free_lists[cls];
  78. if (!b) {
  79. /* Refill this size class from a fresh page. */
  80. page = (void *)mm_alloc_page();
  81. if (!page) {
  82. irq_restore(flags);
  83. return 0;
  84. }
  85. for (off = 0; off + total <= PAGE_SIZE; off += total) {
  86. union km_block *blk =
  87. (union km_block *)((unsigned int)page + off);
  88. blk->next = free_lists[cls];
  89. free_lists[cls] = blk;
  90. }
  91. b = free_lists[cls];
  92. }
  93. free_lists[cls] = b->next;
  94. b->h.size = total;
  95. irq_restore(flags);
  96. return (void *)((unsigned int)b + sizeof(unsigned int));
  97. }
  98. void kfree(void *ptr)
  99. {
  100. union km_block *b;
  101. unsigned int size, cls, flags;
  102. if (!ptr)
  103. return;
  104. b = (union km_block *)((unsigned int)ptr - sizeof(unsigned int));
  105. size = b->h.size;
  106. flags = irq_save_disable();
  107. if (size > PAGE_SIZE) {
  108. unsigned int pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
  109. unsigned int addr = (unsigned int)b;
  110. unsigned int i;
  111. for (i = 0; i < pages; i++)
  112. mm_free_page(addr + i * PAGE_SIZE);
  113. irq_restore(flags);
  114. return;
  115. }
  116. cls = size_class_of(size);
  117. b->next = free_lists[cls];
  118. free_lists[cls] = b;
  119. irq_restore(flags);
  120. }