stdlib.cpp 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337
  1. #include <stdlib.h>
  2. #include <sys/mman.h>
  3. #include <stdio.h>
  4. #include <unistd.h>
  5. #include <string.h>
  6. #include <alloca.h>
  7. #include <assert.h>
  8. #include <errno.h>
  9. #include <AK/Assertions.h>
  10. #include <AK/Types.h>
  11. #include <Kernel/Syscall.h>
  12. #include <AK/StdLibExtras.h>
  13. extern "C" {
  14. #define MALLOC_SCRUB_BYTE 0x85
  15. #define FREE_SCRUB_BYTE 0x82
  16. struct MallocHeader {
  17. uint16_t first_chunk_index;
  18. uint16_t chunk_count;
  19. size_t size;
  20. uint32_t compute_xorcheck() const
  21. {
  22. return 0x19820413 ^ ((first_chunk_index << 16) | chunk_count) ^ size;
  23. }
  24. };
  25. struct MallocFooter {
  26. uint32_t xorcheck;
  27. };
  28. #define CHUNK_SIZE 8
  29. #define POOL_SIZE 128 * 1024
  30. static const size_t malloc_budget = POOL_SIZE;
  31. static byte s_malloc_map[POOL_SIZE / CHUNK_SIZE / 8];
  32. static byte* s_malloc_pool;
  33. static uint32_t s_malloc_sum_alloc = 0;
  34. static uint32_t s_malloc_sum_free = POOL_SIZE;
  35. void* malloc(size_t size)
  36. {
  37. if (size == 0)
  38. return nullptr;
  39. // We need space for the MallocHeader structure at the head of the block.
  40. size_t real_size = size + sizeof(MallocHeader) + sizeof(MallocFooter);
  41. if (s_malloc_sum_free < real_size) {
  42. fprintf(stderr, "malloc(): Out of memory\ns_malloc_sum_free=%u, real_size=%u\n", s_malloc_sum_free, real_size);
  43. assert(false);
  44. }
  45. size_t chunks_needed = real_size / CHUNK_SIZE;
  46. if (real_size % CHUNK_SIZE)
  47. chunks_needed++;
  48. size_t chunks_here = 0;
  49. size_t first_chunk = 0;
  50. for (unsigned i = 0; i < (POOL_SIZE / CHUNK_SIZE / 8); ++i) {
  51. if (s_malloc_map[i] == 0xff) {
  52. // Skip over completely full bucket.
  53. chunks_here = 0;
  54. continue;
  55. }
  56. // FIXME: This scan can be optimized further with TZCNT.
  57. for (unsigned j = 0; j < 8; ++j) {
  58. if ((s_malloc_map[i] & (1<<j))) {
  59. // This is in use, so restart chunks_here counter.
  60. chunks_here = 0;
  61. continue;
  62. }
  63. if (chunks_here == 0) {
  64. // Mark where potential allocation starts.
  65. first_chunk = i * 8 + j;
  66. }
  67. ++chunks_here;
  68. if (chunks_here == chunks_needed) {
  69. auto* header = (MallocHeader*)(s_malloc_pool + (first_chunk * CHUNK_SIZE));
  70. byte* ptr = ((byte*)header) + sizeof(MallocHeader);
  71. header->chunk_count = chunks_needed;
  72. header->first_chunk_index = first_chunk;
  73. header->size = size;
  74. auto* footer = (MallocFooter*)((byte*)header + (header->chunk_count * CHUNK_SIZE) - sizeof(MallocFooter));
  75. footer->xorcheck = header->compute_xorcheck();
  76. for (size_t k = first_chunk; k < (first_chunk + chunks_needed); ++k)
  77. s_malloc_map[k / 8] |= 1 << (k % 8);
  78. s_malloc_sum_alloc += header->chunk_count * CHUNK_SIZE;
  79. s_malloc_sum_free -= header->chunk_count * CHUNK_SIZE;
  80. memset(ptr, MALLOC_SCRUB_BYTE, (header->chunk_count * CHUNK_SIZE) - (sizeof(MallocHeader) + sizeof(MallocFooter)));
  81. return ptr;
  82. }
  83. }
  84. }
  85. fprintf(stderr, "malloc(): Out of memory (no consecutive chunks found for size %u)\n", size);
  86. volatile char* crashme = (char*)0xc007d00d;
  87. *crashme = 0;
  88. return nullptr;
  89. }
  90. static void validate_mallocation(void* ptr, const char* func)
  91. {
  92. auto* header = (MallocHeader*)((((byte*)ptr) - sizeof(MallocHeader)));
  93. if (header->size == 0) {
  94. fprintf(stderr, "%s called on bad pointer %p, size=0\n", func, ptr);
  95. assert(false);
  96. }
  97. auto* footer = (MallocFooter*)((byte*)header + (header->chunk_count * CHUNK_SIZE) - sizeof(MallocFooter));
  98. uint32_t expected_xorcheck = header->compute_xorcheck();
  99. if (footer->xorcheck != expected_xorcheck) {
  100. fprintf(stderr, "%s called on bad pointer %p, xorcheck=%w (expected %w)\n", func, ptr, footer->xorcheck, expected_xorcheck);
  101. assert(false);
  102. }
  103. }
  104. void free(void* ptr)
  105. {
  106. if (!ptr)
  107. return;
  108. validate_mallocation(ptr, "free()");
  109. auto* header = (MallocHeader*)((((byte*)ptr) - sizeof(MallocHeader)));
  110. for (unsigned i = header->first_chunk_index; i < (header->first_chunk_index + header->chunk_count); ++i)
  111. s_malloc_map[i / 8] &= ~(1 << (i % 8));
  112. s_malloc_sum_alloc -= header->chunk_count * CHUNK_SIZE;
  113. s_malloc_sum_free += header->chunk_count * CHUNK_SIZE;
  114. memset(header, FREE_SCRUB_BYTE, header->chunk_count * CHUNK_SIZE);
  115. }
  116. void __malloc_init()
  117. {
  118. s_malloc_pool = (byte*)mmap(nullptr, malloc_budget, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
  119. int rc = set_mmap_name(s_malloc_pool, malloc_budget, "malloc pool");
  120. if (rc < 0)
  121. perror("set_mmap_name failed");
  122. }
  123. void* calloc(size_t count, size_t size)
  124. {
  125. size_t new_size = count * size;
  126. auto* ptr = malloc(new_size);
  127. memset(ptr, 0, new_size);
  128. return ptr;
  129. }
  130. void* realloc(void *ptr, size_t size)
  131. {
  132. validate_mallocation(ptr, "realloc()");
  133. auto* header = (MallocHeader*)((((byte*)ptr) - sizeof(MallocHeader)));
  134. size_t old_size = header->size;
  135. if (size == old_size)
  136. return ptr;
  137. auto* new_ptr = malloc(size);
  138. memcpy(new_ptr, ptr, min(old_size, size));
  139. free(ptr);
  140. return new_ptr;
  141. }
  142. void exit(int status)
  143. {
  144. _exit(status);
  145. assert(false);
  146. }
  147. void abort()
  148. {
  149. // FIXME: Implement proper abort().
  150. exit(253);
  151. }
  152. char* getenv(const char* name)
  153. {
  154. for (size_t i = 0; environ[i]; ++i) {
  155. const char* decl = environ[i];
  156. char* eq = strchr(decl, '=');
  157. if (!eq)
  158. continue;
  159. size_t varLength = eq - decl;
  160. char* var = (char*)alloca(varLength + 1);
  161. memcpy(var, decl, varLength);
  162. var[varLength] = '\0';
  163. if (!strcmp(var, name)) {
  164. char* value = eq + 1;
  165. return value;
  166. }
  167. }
  168. return nullptr;
  169. }
  170. int putenv(char*)
  171. {
  172. assert(false);
  173. }
  174. double atof(const char*)
  175. {
  176. assert(false);
  177. }
  178. int atoi(const char* str)
  179. {
  180. size_t len = strlen(str);
  181. int value = 0;
  182. bool isNegative = false;
  183. for (size_t i = 0; i < len; ++i) {
  184. if (i == 0 && str[0] == '-') {
  185. isNegative = true;
  186. continue;
  187. }
  188. if (str[i] < '0' || str[i] > '9')
  189. return value;
  190. value = value * 10;
  191. value += str[i] - '0';
  192. }
  193. return isNegative ? -value : value;
  194. }
  195. long atol(const char* str)
  196. {
  197. static_assert(sizeof(int) == sizeof(long));
  198. return atoi(str);
  199. }
  200. static char ptsname_buf[32];
  201. char* ptsname(int fd)
  202. {
  203. if (ptsname_r(fd, ptsname_buf, sizeof(ptsname_buf)) < 0)
  204. return nullptr;
  205. return ptsname_buf;
  206. }
  207. int ptsname_r(int fd, char* buffer, size_t size)
  208. {
  209. int rc = syscall(SC_ptsname_r, fd, buffer, size);
  210. __RETURN_WITH_ERRNO(rc, rc, -1);
  211. }
  212. static unsigned long s_next_rand = 1;
  213. int rand()
  214. {
  215. s_next_rand = s_next_rand * 1103515245 + 12345;
  216. return((unsigned)(s_next_rand/((RAND_MAX + 1) * 2)) % (RAND_MAX + 1));
  217. }
  218. void srand(unsigned seed)
  219. {
  220. s_next_rand = seed;
  221. }
  222. int abs(int i)
  223. {
  224. return i < 0 ? -i : i;
  225. }
  226. long int random()
  227. {
  228. return rand();
  229. }
  230. void srandom(unsigned seed)
  231. {
  232. srand(seed);
  233. }
  234. int system(const char* command)
  235. {
  236. return execl("/bin/sh", "sh", "-c", command, nullptr);
  237. }
  238. char* mktemp(char*)
  239. {
  240. ASSERT_NOT_REACHED();
  241. }
  242. void* bsearch(const void* key, const void* base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
  243. {
  244. dbgprintf("FIXME(LibC): bsearch(%p, %p, %u, %u, %p)\n", key, base, nmemb, size, compar);
  245. ASSERT_NOT_REACHED();
  246. }
  247. div_t div(int numerator, int denominator)
  248. {
  249. div_t result;
  250. result.quot = numerator / denominator;
  251. result.rem = numerator % denominator;
  252. return result;
  253. }
  254. ldiv_t ldiv(long numerator, long denominator)
  255. {
  256. ldiv_t result;
  257. result.quot = numerator / denominator;
  258. result.rem = numerator % denominator;
  259. return result;
  260. }
  261. size_t mbstowcs(wchar_t*, const char*, size_t)
  262. {
  263. assert(false);
  264. }
  265. int atexit(void (*function)())
  266. {
  267. (void)function;
  268. assert(false);
  269. }
  270. long strtol(const char*, char** endptr, int base)
  271. {
  272. (void)endptr;
  273. (void)base;
  274. assert(false);
  275. }
  276. unsigned long strtoul(const char*, char** endptr, int base)
  277. {
  278. (void)endptr;
  279. (void)base;
  280. assert(false);
  281. }
  282. }