kmalloc.cpp 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216
  1. /*
  2. * Really really *really* Q&D malloc() and free() implementations
  3. * just to get going. Don't ever let anyone see this shit. :^)
  4. */
  5. #include <AK/Types.h>
  6. #include <Kernel/kmalloc.h>
  7. #include <Kernel/StdLib.h>
  8. #include <Kernel/i386.h>
  9. #include <Kernel/Process.h>
  10. #include <Kernel/Scheduler.h>
  11. #include <Kernel/KSyms.h>
  12. #include <AK/Assertions.h>
  13. #define SANITIZE_KMALLOC
  14. struct [[gnu::packed]] allocation_t {
  15. size_t start;
  16. size_t nchunk;
  17. };
  18. #define CHUNK_SIZE 32
  19. #define POOL_SIZE (1024 * 1024)
  20. #define ETERNAL_BASE_PHYSICAL 0x100000
  21. #define ETERNAL_RANGE_SIZE 0x100000
  22. #define BASE_PHYSICAL 0x200000
  23. #define RANGE_SIZE 0x100000
  24. static byte alloc_map[POOL_SIZE / CHUNK_SIZE / 8];
  25. volatile size_t sum_alloc = 0;
  26. volatile size_t sum_free = POOL_SIZE;
  27. volatile size_t kmalloc_sum_eternal = 0;
  28. dword g_kmalloc_call_count;
  29. dword g_kfree_call_count;
  30. bool g_dump_kmalloc_stacks;
  31. static byte* s_next_eternal_ptr;
  32. static byte* s_end_of_eternal_range;
  33. bool is_kmalloc_address(const void* ptr)
  34. {
  35. if (ptr >= (byte*)ETERNAL_BASE_PHYSICAL && ptr < s_next_eternal_ptr)
  36. return true;
  37. return (size_t)ptr >= BASE_PHYSICAL && (size_t)ptr <= (BASE_PHYSICAL + POOL_SIZE);
  38. }
  39. void kmalloc_init()
  40. {
  41. memset(&alloc_map, 0, sizeof(alloc_map));
  42. memset((void *)BASE_PHYSICAL, 0, POOL_SIZE);
  43. kmalloc_sum_eternal = 0;
  44. sum_alloc = 0;
  45. sum_free = POOL_SIZE;
  46. s_next_eternal_ptr = (byte*)ETERNAL_BASE_PHYSICAL;
  47. s_end_of_eternal_range = s_next_eternal_ptr + ETERNAL_RANGE_SIZE;
  48. }
  49. void* kmalloc_eternal(size_t size)
  50. {
  51. void* ptr = s_next_eternal_ptr;
  52. s_next_eternal_ptr += size;
  53. ASSERT(s_next_eternal_ptr < s_end_of_eternal_range);
  54. kmalloc_sum_eternal += size;
  55. return ptr;
  56. }
  57. void* kmalloc_aligned(size_t size, size_t alignment)
  58. {
  59. void* ptr = kmalloc(size + alignment + sizeof(void*));
  60. size_t max_addr = (size_t)ptr + alignment;
  61. void* aligned_ptr = (void*)(max_addr - (max_addr % alignment));
  62. ((void**)aligned_ptr)[-1] = ptr;
  63. return aligned_ptr;
  64. }
  65. void kfree_aligned(void* ptr)
  66. {
  67. kfree(((void**)ptr)[-1]);
  68. }
  69. void* kmalloc_page_aligned(size_t size)
  70. {
  71. void* ptr = kmalloc_aligned(size, PAGE_SIZE);
  72. size_t d = (size_t)ptr;
  73. ASSERT((d & PAGE_MASK) == d);
  74. return ptr;
  75. }
  76. void* kmalloc_impl(size_t size)
  77. {
  78. InterruptDisabler disabler;
  79. ++g_kmalloc_call_count;
  80. if (g_dump_kmalloc_stacks && ksyms_ready) {
  81. dbgprintf("kmalloc(%u)\n", size);
  82. dump_backtrace();
  83. }
  84. // We need space for the allocation_t structure at the head of the block.
  85. size_t real_size = size + sizeof(allocation_t);
  86. if (sum_free < real_size) {
  87. dump_backtrace();
  88. kprintf("%s(%u) kmalloc(): PANIC! Out of memory (sucks, dude)\nsum_free=%u, real_size=%u\n", current->process().name().characters(), current->pid(), sum_free, real_size);
  89. hang();
  90. }
  91. size_t chunks_needed = real_size / CHUNK_SIZE;
  92. if (real_size % CHUNK_SIZE)
  93. ++chunks_needed;
  94. size_t chunks_here = 0;
  95. size_t first_chunk = 0;
  96. for (size_t i = 0; i < (POOL_SIZE / CHUNK_SIZE / 8); ++i) {
  97. if (alloc_map[i] == 0xff) {
  98. // Skip over completely full bucket.
  99. chunks_here = 0;
  100. continue;
  101. }
  102. // FIXME: This scan can be optimized further with LZCNT.
  103. for (size_t j = 0; j < 8; ++j) {
  104. if (!(alloc_map[i] & (1<<j))) {
  105. if (chunks_here == 0) {
  106. // Mark where potential allocation starts.
  107. first_chunk = i * 8 + j;
  108. }
  109. ++chunks_here;
  110. if (chunks_here == chunks_needed) {
  111. auto* a = (allocation_t *)(BASE_PHYSICAL + (first_chunk * CHUNK_SIZE));
  112. byte *ptr = (byte *)a;
  113. ptr += sizeof(allocation_t);
  114. a->nchunk = chunks_needed;
  115. a->start = first_chunk;
  116. for (size_t k = first_chunk; k < (first_chunk + chunks_needed); ++k) {
  117. alloc_map[k / 8] |= 1 << (k % 8);
  118. }
  119. sum_alloc += a->nchunk * CHUNK_SIZE;
  120. sum_free -= a->nchunk * CHUNK_SIZE;
  121. #ifdef SANITIZE_KMALLOC
  122. memset(ptr, 0xbb, (a->nchunk * CHUNK_SIZE) - sizeof(allocation_t));
  123. #endif
  124. return ptr;
  125. }
  126. } else {
  127. // This is in use, so restart chunks_here counter.
  128. chunks_here = 0;
  129. }
  130. }
  131. }
  132. kprintf("%s(%u) kmalloc(): PANIC! Out of memory (no suitable block for size %u)\n", current->process().name().characters(), current->pid(), size);
  133. dump_backtrace();
  134. hang();
  135. }
  136. void kfree(void *ptr)
  137. {
  138. if (!ptr)
  139. return;
  140. InterruptDisabler disabler;
  141. ++g_kfree_call_count;
  142. auto* a = (allocation_t*)((((byte*)ptr) - sizeof(allocation_t)));
  143. for (size_t k = a->start; k < (a->start + a->nchunk); ++k)
  144. alloc_map[k / 8] &= ~(1 << (k % 8));
  145. sum_alloc -= a->nchunk * CHUNK_SIZE;
  146. sum_free += a->nchunk * CHUNK_SIZE;
  147. #ifdef SANITIZE_KMALLOC
  148. memset(a, 0xaa, a->nchunk * CHUNK_SIZE);
  149. #endif
  150. }
  151. void* operator new(size_t size)
  152. {
  153. return kmalloc(size);
  154. }
  155. void* operator new[](size_t size)
  156. {
  157. return kmalloc(size);
  158. }
  159. void operator delete(void* ptr)
  160. {
  161. return kfree(ptr);
  162. }
  163. void operator delete[](void* ptr)
  164. {
  165. return kfree(ptr);
  166. }
  167. void operator delete(void* ptr, size_t)
  168. {
  169. return kfree(ptr);
  170. }
  171. void operator delete[](void* ptr, size_t)
  172. {
  173. return kfree(ptr);
  174. }