test_malloc.c 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  1. /* Host stress test for libc/malloc.c.
  2. *
  3. * The allocator is compiled with the malloc/free/... names renamed to
  4. * libc_*, so the host libc stays untouched and the test can use rand/write
  5. * without recursion.
  6. */
  7. #include <stddef.h>
  8. #include <stdint.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <unistd.h>
  12. void *libc_malloc(size_t size);
  13. void libc_free(void *ptr);
  14. void *libc_calloc(size_t nmemb, size_t size);
  15. void *libc_realloc(void *ptr, size_t size);
  16. void libc_heap_reset(void);
  17. unsigned int host_mem_mapped(void);
  18. #define SLOTS 96
  19. #define LIVE_CAP (24u * 1024u * 1024u)
  20. struct slot {
  21. unsigned char *p;
  22. size_t n;
  23. unsigned char pat;
  24. };
  25. static struct slot slots[SLOTS];
  26. static unsigned int live_bytes;
  27. static unsigned int pattern_seed;
  28. static int failures;
  29. static void out(const char *s)
  30. {
  31. (void)!write(1, s, strlen(s));
  32. }
  33. static void out_num(unsigned long n)
  34. {
  35. char buf[24];
  36. char *p = buf + sizeof(buf);
  37. *--p = '\0';
  38. if (n == 0)
  39. *--p = '0';
  40. while (n) {
  41. *--p = (char)('0' + (n % 10));
  42. n /= 10;
  43. }
  44. out(p);
  45. }
  46. static void fail(const char *msg)
  47. {
  48. out("FAIL: ");
  49. out(msg);
  50. out("\n");
  51. failures++;
  52. }
  53. static int ranges_overlap(const void *a, size_t an, const void *b, size_t bn)
  54. {
  55. uintptr_t pa = (uintptr_t)a;
  56. uintptr_t pb = (uintptr_t)b;
  57. return pa < pb + bn && pb < pa + an;
  58. }
  59. static int overlaps_live(const void *p, size_t n, int skip)
  60. {
  61. int i;
  62. for (i = 0; i < SLOTS; i++) {
  63. if (i == skip || !slots[i].p)
  64. continue;
  65. if (ranges_overlap(p, n, slots[i].p, slots[i].n))
  66. return 1;
  67. }
  68. return 0;
  69. }
  70. static void fill(unsigned char *p, size_t n, unsigned char pat)
  71. {
  72. size_t i;
  73. for (i = 0; i < n; i++)
  74. p[i] = pat;
  75. }
  76. static int check_fill(const unsigned char *p, size_t n, unsigned char pat)
  77. {
  78. size_t i;
  79. for (i = 0; i < n; i++) {
  80. if (p[i] != pat)
  81. return 0;
  82. }
  83. return 1;
  84. }
  85. static size_t pick_size(void)
  86. {
  87. unsigned int r = (unsigned int)rand();
  88. if ((r & 63u) == 0)
  89. return 1 + (size_t)(rand() % (4 * 1024 * 1024));
  90. if ((r & 7u) == 0)
  91. return 1 + (size_t)(rand() % (256 * 1024));
  92. return 1 + (size_t)(rand() % 8192);
  93. }
  94. static int find_free_slot(void)
  95. {
  96. int i;
  97. for (i = 0; i < SLOTS; i++) {
  98. if (!slots[i].p)
  99. return i;
  100. }
  101. return -1;
  102. }
  103. static int find_live_slot(void)
  104. {
  105. int i;
  106. for (i = 0; i < SLOTS; i++) {
  107. if (slots[i].p)
  108. return i;
  109. }
  110. return -1;
  111. }
  112. static void free_slot(int i)
  113. {
  114. if (i < 0 || !slots[i].p)
  115. return;
  116. if (!check_fill(slots[i].p, slots[i].n, slots[i].pat))
  117. fail("pattern changed before free");
  118. libc_free(slots[i].p);
  119. live_bytes -= (unsigned int)slots[i].n;
  120. slots[i].p = 0;
  121. slots[i].n = 0;
  122. }
  123. static void test_basics(void)
  124. {
  125. unsigned char *p;
  126. unsigned char *q;
  127. unsigned char *r;
  128. size_t i;
  129. if (libc_malloc(0) != 0)
  130. fail("malloc(0) is not NULL");
  131. libc_free(0);
  132. p = (unsigned char *)libc_malloc(100);
  133. if (!p) {
  134. fail("malloc(100) failed");
  135. return;
  136. }
  137. if ((uintptr_t)p & 15u)
  138. fail("malloc is not 16-byte aligned");
  139. fill(p, 100, 0x5A);
  140. if (!check_fill(p, 100, 0x5A))
  141. fail("malloc contents changed");
  142. libc_free(p);
  143. p = (unsigned char *)libc_calloc(1024, 4);
  144. if (!p) {
  145. fail("calloc failed");
  146. } else {
  147. for (i = 0; i < 4096; i++) {
  148. if (p[i] != 0) {
  149. fail("calloc returned non-zero memory");
  150. break;
  151. }
  152. }
  153. libc_free(p);
  154. }
  155. p = (unsigned char *)libc_realloc(0, 100);
  156. if (!p) {
  157. fail("realloc(NULL, 100) failed");
  158. } else {
  159. fill(p, 100, 0x33);
  160. if (libc_realloc(p, 0) != 0)
  161. fail("realloc(ptr, 0) did not return NULL");
  162. }
  163. p = (unsigned char *)libc_malloc(1024);
  164. q = (unsigned char *)libc_malloc(2048);
  165. if (!p || !q) {
  166. fail("two small allocations failed");
  167. libc_free(p);
  168. libc_free(q);
  169. } else {
  170. fill(p, 1024, 0x11);
  171. fill(q, 2048, 0x22);
  172. if (overlaps_live(p, 1024, -1) ||
  173. overlaps_live(q, 2048, -1))
  174. fail("small allocations overlap");
  175. if (!check_fill(p, 1024, 0x11) ||
  176. !check_fill(q, 2048, 0x22))
  177. fail("small allocation contents changed");
  178. r = (unsigned char *)libc_realloc(p, 8192);
  179. if (!r) {
  180. fail("realloc grow failed");
  181. libc_free(p);
  182. } else {
  183. if (!check_fill(r, 1024, 0x11))
  184. fail("realloc lost the prefix");
  185. fill(r, 8192, 0x44);
  186. libc_free(r);
  187. }
  188. libc_free(q);
  189. }
  190. if (libc_calloc((size_t)-1, 2) != 0)
  191. fail("calloc overflow did not fail");
  192. }
  193. static void test_random(void)
  194. {
  195. unsigned int op;
  196. int i;
  197. for (op = 0; op < 4000; op++) {
  198. int fslot = find_free_slot();
  199. int live = find_live_slot();
  200. unsigned int r = (unsigned int)rand();
  201. if (live < 0 || (fslot >= 0 && (r & 3u) != 0)) {
  202. size_t n = pick_size();
  203. unsigned char *p;
  204. unsigned char pat;
  205. if (live_bytes + (unsigned int)n > LIVE_CAP &&
  206. live >= 0) {
  207. free_slot(live);
  208. fslot = find_free_slot();
  209. }
  210. if (fslot < 0)
  211. continue;
  212. p = (unsigned char *)libc_malloc(n);
  213. if (!p) {
  214. fail("random malloc failed");
  215. continue;
  216. }
  217. if ((uintptr_t)p & 15u)
  218. fail("random malloc is not 16-byte aligned");
  219. if (overlaps_live(p, n, -1))
  220. fail("random allocations overlap");
  221. pat = (unsigned char)(0x30 + (pattern_seed++ & 0x3F));
  222. fill(p, n, pat);
  223. slots[fslot].p = p;
  224. slots[fslot].n = n;
  225. slots[fslot].pat = pat;
  226. live_bytes += (unsigned int)n;
  227. } else {
  228. free_slot(live);
  229. }
  230. }
  231. /* A realloc pass over the surviving blocks. */
  232. for (i = 0; i < SLOTS; i++) {
  233. size_t n;
  234. size_t old;
  235. unsigned char *p;
  236. unsigned char *q;
  237. unsigned char pat;
  238. if (!slots[i].p)
  239. continue;
  240. old = slots[i].n;
  241. n = pick_size();
  242. if (n > old && live_bytes + (unsigned int)(n - old) > LIVE_CAP)
  243. n = old;
  244. p = slots[i].p;
  245. q = (unsigned char *)libc_realloc(p, n);
  246. if (!q) {
  247. fail("random realloc failed");
  248. continue;
  249. }
  250. if (overlaps_live(q, n, i))
  251. fail("realloc overlaps another block");
  252. if (!check_fill(q, old < n ? old : n, slots[i].pat))
  253. fail("realloc lost the prefix");
  254. pat = (unsigned char)(0x80 + (pattern_seed++ & 0x3F));
  255. fill(q, n, pat);
  256. live_bytes = live_bytes - (unsigned int)old + (unsigned int)n;
  257. slots[i].p = q;
  258. slots[i].n = n;
  259. slots[i].pat = pat;
  260. }
  261. }
  262. static void free_all(void)
  263. {
  264. int i;
  265. for (i = 0; i < SLOTS; i++)
  266. free_slot(i);
  267. if (live_bytes != 0)
  268. fail("live byte count is not zero");
  269. }
  270. static void test_large(void)
  271. {
  272. unsigned char *p;
  273. unsigned char *q;
  274. size_t n = 8u * 1024u * 1024u;
  275. p = (unsigned char *)libc_malloc(n);
  276. if (!p) {
  277. fail("8 MB allocation failed");
  278. } else {
  279. fill(p, n, 0x6C);
  280. if (!check_fill(p, n, 0x6C))
  281. fail("8 MB pattern changed");
  282. libc_free(p);
  283. }
  284. p = (unsigned char *)libc_malloc(1024u * 1024u);
  285. if (!p) {
  286. fail("1 MB allocation failed");
  287. return;
  288. }
  289. fill(p, 1024u * 1024u, 0x21);
  290. q = (unsigned char *)libc_realloc(p, 4u * 1024u * 1024u);
  291. if (!q) {
  292. fail("1 MB -> 4 MB realloc failed");
  293. libc_free(p);
  294. return;
  295. }
  296. if (!check_fill(q, 1024u * 1024u, 0x21))
  297. fail("large realloc lost the prefix");
  298. fill(q, 4u * 1024u * 1024u, 0x42);
  299. libc_free(q);
  300. }
  301. int main(void)
  302. {
  303. unsigned int seed;
  304. for (seed = 1; seed <= 8; seed++) {
  305. srand(seed);
  306. pattern_seed = 0;
  307. test_basics();
  308. test_random();
  309. free_all();
  310. libc_heap_reset();
  311. if (host_mem_mapped() != 0)
  312. fail("heap_reset did not unmap the arena");
  313. }
  314. test_large();
  315. libc_heap_reset();
  316. if (host_mem_mapped() != 0)
  317. fail("second heap_reset did not unmap the arena");
  318. if (failures) {
  319. out("malloc test: ");
  320. out_num((unsigned long)failures);
  321. out(" failure(s)\n");
  322. return 1;
  323. }
  324. out("malloc test: OK\n");
  325. return 0;
  326. }