slabmgr.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456
  1. /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
  2. /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
  3. /* Copyright (C) 2014 Stony Brook University
  4. This file is part of Graphene Library OS.
  5. Graphene Library OS is free software: you can redistribute it and/or
  6. modify it under the terms of the GNU Lesser General Public License
  7. as published by the Free Software Foundation, either version 3 of the
  8. License, or (at your option) any later version.
  9. Graphene Library OS is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU Lesser General Public License for more details.
  13. You should have received a copy of the GNU Lesser General Public License
  14. along with this program. If not, see <http://www.gnu.org/licenses/>. */
  15. /*
  16. * slabmgr.h
  17. *
  18. * This file contains implementation of SLAB (variable-size) memory allocator.
  19. */
  20. #ifndef SLABMGR_H
  21. #define SLABMGR_H
  22. #include "list.h"
  23. #include <assert.h>
  24. #include <sys/mman.h>
  25. #ifndef system_malloc
  26. #error "macro \"void * system_malloc(int size)\" not declared"
  27. #endif
  28. #ifndef system_free
  29. #error "macro \"void * system_free(void * ptr, int size)\" not declared"
  30. #endif
  31. #ifndef system_lock
  32. #define system_lock() ({})
  33. #endif
  34. #ifndef system_unlock
  35. #define system_unlock() ({})
  36. #endif
  37. /* malloc is supposed to provide some kind of alignment guarantees, but
  38. * I can't find a specific reference to what that should be for x86_64.
  39. * The first link here is a reference to a technical report from Mozilla,
  40. * which seems to indicate that 64-bit platforms align return values to
  41. * 16-bytes. calloc and malloc provide the same alignment guarantees.
  42. * calloc additionally sets the memory to 0, which malloc is not required
  43. * to do.
  44. *
  45. * http://www.erahm.org/2016/03/24/minimum-alignment-of-allocation-across-platforms/
  46. * http://pubs.opengroup.org/onlinepubs/9699919799/functions/malloc.html
  47. */
  48. #define MIN_MALLOC_ALIGNMENT 16
  49. /* Slab objects need to be a multiple of 16 bytes to ensure proper address
  50. * alignment for malloc and calloc. */
  51. #define OBJ_PADDING 15
  52. #define LARGE_OBJ_PADDING 8
  53. /* Returns the smallest exact multiple of _y that is at least as large as _x.
  54. * In other words, returns _x if _x is a multiple of _y, otherwise rounds
  55. * _x up to be a multiple of _y.
  56. */
  57. #define ROUND_UP(_x, _y) ((((_x) + (_y) - 1) / (_y)) * (_y))
  58. DEFINE_LIST(slab_obj);
  59. typedef struct __attribute__((packed)) slab_obj {
  60. unsigned char level;
  61. unsigned char padding[OBJ_PADDING];
  62. union {
  63. LIST_TYPE(slab_obj) __list;
  64. unsigned char *raw;
  65. };
  66. } SLAB_OBJ_TYPE, * SLAB_OBJ;
  67. /* In order for slab elements to be 16-byte aligned, struct slab_area must
  68. * be a multiple of 16 bytes. TODO: Add compile time assertion that this
  69. * invariant is respected. */
  70. #define AREA_PADDING 12
  71. DEFINE_LIST(slab_area);
  72. typedef struct __attribute__((packed)) slab_area {
  73. LIST_TYPE(slab_area) __list;
  74. unsigned int size;
  75. unsigned char pad[AREA_PADDING];
  76. unsigned char raw[];
  77. } SLAB_AREA_TYPE, * SLAB_AREA;
  78. #ifdef SLAB_DEBUG
  79. struct slab_debug {
  80. struct {
  81. const char * file;
  82. int line;
  83. } alloc, free;
  84. };
  85. # define SLAB_DEBUG_SIZE sizeof(struct slab_debug)
  86. #else
  87. # define SLAB_DEBUG_SIZE 0
  88. #endif
  89. #ifdef SLAB_CANARY
  90. # define SLAB_CANARY_STRING 0xDEADBEEF
  91. # define SLAB_CANARY_SIZE sizeof(unsigned long)
  92. #else
  93. # define SLAB_CANARY_SIZE 0
  94. #endif
  95. #define SLAB_HDR_SIZE \
  96. ROUND_UP((sizeof(SLAB_OBJ_TYPE) - sizeof(LIST_TYPE(slab_obj)) + \
  97. SLAB_DEBUG_SIZE + SLAB_CANARY_SIZE), \
  98. MIN_MALLOC_ALIGNMENT)
  99. #ifndef SLAB_LEVEL
  100. #define SLAB_LEVEL 8
  101. #endif
  102. #ifndef SLAB_LEVEL_SIZES
  103. # define SLAB_LEVEL_SIZES 16, 32, 64, \
  104. 128 - SLAB_HDR_SIZE, \
  105. 256 - SLAB_HDR_SIZE, \
  106. 512 - SLAB_HDR_SIZE, \
  107. 1024 - SLAB_HDR_SIZE, \
  108. 2048 - SLAB_HDR_SIZE
  109. # define SLAB_LEVELS_SUM (4080 - SLAB_HDR_SIZE * 5)
  110. #else
  111. # ifndef SLAB_LEVELS_SUM
  112. # error "SALB_LEVELS_SUM not defined"
  113. # endif
  114. #endif
  115. static int slab_levels[SLAB_LEVEL] = { SLAB_LEVEL_SIZES };
  116. DEFINE_LISTP(slab_obj);
  117. DEFINE_LISTP(slab_area);
  118. typedef struct slab_mgr {
  119. LISTP_TYPE(slab_area) area_list[SLAB_LEVEL];
  120. LISTP_TYPE(slab_obj) free_list[SLAB_LEVEL];
  121. unsigned int size[SLAB_LEVEL];
  122. void * addr[SLAB_LEVEL], * addr_top[SLAB_LEVEL];
  123. } SLAB_MGR_TYPE, * SLAB_MGR;
  124. typedef struct __attribute__((packed)) large_mem_obj {
  125. // offset 0
  126. unsigned long size;
  127. unsigned char large_padding[LARGE_OBJ_PADDING];
  128. // offset 16
  129. unsigned char level;
  130. unsigned char padding[OBJ_PADDING];
  131. // offset 32
  132. unsigned char raw[];
  133. } LARGE_MEM_OBJ_TYPE, * LARGE_MEM_OBJ;
  134. #define OBJ_LEVEL(obj) ((obj)->level)
  135. #define OBJ_RAW(obj) (&(obj)->raw)
  136. #ifndef container_of
  137. #define container_of(ptr, type, field) ((type *)((char *)(ptr) - offsetof(type, field)))
  138. #endif
  139. #define RAW_TO_LEVEL(raw_ptr) \
  140. (*((unsigned char *) (raw_ptr) - OBJ_PADDING - 1))
  141. #define RAW_TO_OBJ(raw_ptr, type) container_of((raw_ptr), type, raw)
  142. #define __SUM_OBJ_SIZE(slab_size, size) \
  143. (((slab_size) + SLAB_HDR_SIZE) * (size))
  144. #define __MIN_MEM_SIZE() (sizeof(SLAB_AREA_TYPE))
  145. #define __MAX_MEM_SIZE(slab_size, size) \
  146. (__MIN_MEM_SIZE() + __SUM_OBJ_SIZE((slab_size), (size)))
  147. #define __INIT_SUM_OBJ_SIZE(size) \
  148. ((SLAB_LEVELS_SUM + SLAB_HDR_SIZE * SLAB_LEVEL) * (size))
  149. #define __INIT_MIN_MEM_SIZE() \
  150. (sizeof(SLAB_MGR_TYPE) + sizeof(SLAB_AREA_TYPE) * SLAB_LEVEL)
  151. #define __INIT_MAX_MEM_SIZE(size) \
  152. (__INIT_MIN_MEM_SIZE() + __INIT_SUM_OBJ_SIZE((size)))
  153. #ifdef PAGE_SIZE
  154. static inline int size_align_down(int slab_size, int size)
  155. {
  156. int s = __MAX_MEM_SIZE(slab_size, size);
  157. int p = s - (s & ~(PAGE_SIZE - 1));
  158. int o = __SUM_OBJ_SIZE(slab_size, 1);
  159. return size - p / o - (p % o ? 1 : 0);
  160. }
  161. static inline int size_align_up(int slab_size, int size)
  162. {
  163. int s = __MAX_MEM_SIZE(slab_size, size);
  164. int p = ((s + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1)) - s;
  165. int o = __SUM_OBJ_SIZE(slab_size, 1);
  166. return size + p / o;
  167. }
  168. static inline int init_align_down(int size)
  169. {
  170. int s = __INIT_MAX_MEM_SIZE(size);
  171. int p = s - (s & ~(PAGE_SIZE - 1));
  172. int o = __INIT_SUM_OBJ_SIZE(1);
  173. return size - p /o - (p % o ? 1 : 0);
  174. }
  175. static inline int init_size_align_up(int size)
  176. {
  177. int s = __INIT_MAX_MEM_SIZE(size);
  178. int p = ((s + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1)) - s;
  179. int o = __INIT_SUM_OBJ_SIZE(1);
  180. return size + p / o;
  181. }
  182. #endif /* PAGE_SIZE */
  183. #ifndef STARTUP_SIZE
  184. # define STARTUP_SIZE 16
  185. #endif
  186. static inline void __set_free_slab_area (SLAB_AREA area, SLAB_MGR mgr,
  187. int level)
  188. {
  189. int slab_size = slab_levels[level] + SLAB_HDR_SIZE;
  190. mgr->addr[level] = (void *) area->raw;
  191. mgr->addr_top[level] = (void *) area->raw + area->size * slab_size;
  192. mgr->size[level] += area->size;
  193. }
  194. static inline SLAB_MGR create_slab_mgr (void)
  195. {
  196. #ifdef PAGE_SIZE
  197. int size = init_size_align_up(STARTUP_SIZE);
  198. #else
  199. int size = STARTUP_SIZE;
  200. #endif
  201. unsigned long mem;
  202. SLAB_AREA area;
  203. SLAB_MGR mgr;
  204. mem = (unsigned long) system_malloc(__INIT_MAX_MEM_SIZE(size));
  205. if (mem <= 0)
  206. return NULL;
  207. mgr = (SLAB_MGR) mem;
  208. void * addr = (void *) mgr + sizeof(SLAB_MGR_TYPE);
  209. int i;
  210. for (i = 0 ; i < SLAB_LEVEL ; i++) {
  211. area = (SLAB_AREA) addr;
  212. area->size = STARTUP_SIZE;
  213. INIT_LIST_HEAD(area, __list);
  214. INIT_LISTP(&mgr->area_list[i]);
  215. listp_add_tail(area, &mgr->area_list[i], __list);
  216. INIT_LISTP(&mgr->free_list[i]);
  217. mgr->size[i] = 0;
  218. __set_free_slab_area(area, mgr, i);
  219. addr += __MAX_MEM_SIZE(slab_levels[i], STARTUP_SIZE);
  220. }
  221. return mgr;
  222. }
  223. static inline void destroy_slab_mgr (SLAB_MGR mgr)
  224. {
  225. void * addr = (void *) mgr + sizeof(SLAB_MGR_TYPE);
  226. SLAB_AREA area, tmp, n;
  227. int i;
  228. for (i = 0 ; i < SLAB_LEVEL; i++) {
  229. area = (SLAB_AREA) addr;
  230. listp_for_each_entry_safe(tmp, n, &mgr->area_list[i], __list) {
  231. if (tmp != area)
  232. system_free(area,
  233. __MAX_MEM_SIZE(slab_levels[i], area->size));
  234. }
  235. addr += __MAX_MEM_SIZE(slab_levels[i], STARTUP_SIZE);
  236. }
  237. system_free(mgr, addr - (void *) mgr);
  238. }
  239. static inline SLAB_MGR enlarge_slab_mgr (SLAB_MGR mgr, int level)
  240. {
  241. SLAB_AREA area;
  242. int size;
  243. if (level >= SLAB_LEVEL) {
  244. system_lock();
  245. goto out;
  246. }
  247. size = mgr->size[level];
  248. area = (SLAB_AREA) system_malloc(__MAX_MEM_SIZE(slab_levels[level], size));
  249. if (area <= 0)
  250. return NULL;
  251. system_lock();
  252. area->size = size;
  253. INIT_LIST_HEAD(area, __list);
  254. listp_add(area, &mgr->area_list[level], __list);
  255. __set_free_slab_area(area, mgr, level);
  256. system_unlock();
  257. out:
  258. return mgr;
  259. }
  260. static inline void * slab_alloc (SLAB_MGR mgr, int size)
  261. {
  262. SLAB_OBJ mobj;
  263. int i;
  264. int level = -1;
  265. for (i = 0 ; i < SLAB_LEVEL ; i++)
  266. if (size <= slab_levels[i]) {
  267. level = i;
  268. break;
  269. }
  270. if (level == -1) {
  271. LARGE_MEM_OBJ mem = (LARGE_MEM_OBJ)
  272. system_malloc(sizeof(LARGE_MEM_OBJ_TYPE) + size);
  273. if (!mem)
  274. return NULL;
  275. mem->size = size;
  276. OBJ_LEVEL(mem) = (unsigned char) -1;
  277. return OBJ_RAW(mem);
  278. }
  279. system_lock();
  280. if (mgr->addr[level] == mgr->addr_top[level] &&
  281. listp_empty(&mgr->free_list[level])) {
  282. system_unlock();
  283. enlarge_slab_mgr(mgr, level);
  284. system_lock();
  285. }
  286. if (!listp_empty(&mgr->free_list[level])) {
  287. mobj = listp_first_entry(&mgr->free_list[level], SLAB_OBJ_TYPE, __list);
  288. listp_del(mobj, &mgr->free_list[level], __list);
  289. } else {
  290. mobj = (void *) mgr->addr[level];
  291. mgr->addr[level] += slab_levels[level] + SLAB_HDR_SIZE;
  292. }
  293. OBJ_LEVEL(mobj) = level;
  294. system_unlock();
  295. #ifdef SLAB_CANARY
  296. unsigned long * m =
  297. (unsigned long *) ((void *) OBJ_RAW(mobj) + slab_levels[level]);
  298. *m = SLAB_CANARY_STRING;
  299. #endif
  300. return OBJ_RAW(mobj);
  301. }
  302. #ifdef SLAB_DEBUG
  303. static inline void * slab_alloc_debug (SLAB_MGR mgr, int size,
  304. const char * file, int line)
  305. {
  306. void * mem = slab_alloc(mgr, size);
  307. int i;
  308. int level = -1;
  309. for (i = 0 ; i < SLAB_LEVEL ; i++)
  310. if (size <= slab_levels[i]) {
  311. level = i;
  312. break;
  313. }
  314. if (level != -1) {
  315. struct slab_debug * debug =
  316. (struct slab_debug *) (mem + slab_levels[level] +
  317. SLAB_CANARY_SIZE);
  318. debug->alloc.file = file;
  319. debug->alloc.line = line;
  320. }
  321. return mem;
  322. }
  323. #endif
  324. static inline void slab_free (SLAB_MGR mgr, void * obj)
  325. {
  326. /* In a general purpose allocator, free of NULL is allowed (and is a
  327. * nop). We might want to enforce stricter rules for our allocator if
  328. * we're sure that no clients rely on being able to free NULL. */
  329. if (obj == NULL)
  330. return;
  331. unsigned char level = RAW_TO_LEVEL(obj);
  332. if (level == (unsigned char) -1) {
  333. LARGE_MEM_OBJ mem = RAW_TO_OBJ(obj, LARGE_MEM_OBJ_TYPE);
  334. system_free(mem, mem->size + sizeof(LARGE_MEM_OBJ_TYPE));
  335. return;
  336. }
  337. /* If this happens, either the heap is already corrupted, or someone's
  338. * freeing something that's wrong, which will most likely lead to heap
  339. * corruption. Either way, panic if this happens. TODO: this doesn't allow
  340. * us to detect cases where the heap headers have been zeroed, which
  341. * is a common type of heap corruption. We could make this case slightly
  342. * more likely to be detected by adding a non-zero offset to the level,
  343. * so a level of 0 in the header would no longer be a valid level. */
  344. if (level >= SLAB_LEVEL) {
  345. pal_printf("Heap corruption detected: invalid heap level %ud\n", level);
  346. assert(0); // panic
  347. }
  348. #ifdef SLAB_CANARY
  349. unsigned long * m = (unsigned long *) (obj + slab_levels[level]);
  350. assert((*m) == SLAB_CANARY_STRING);
  351. #endif
  352. SLAB_OBJ mobj = RAW_TO_OBJ(obj, SLAB_OBJ_TYPE);
  353. system_lock();
  354. INIT_LIST_HEAD(mobj, __list);
  355. listp_add_tail(mobj, &mgr->free_list[level], __list);
  356. system_unlock();
  357. }
  358. #ifdef SLAB_DEBUG
  359. static inline void slab_free_debug (SLAB_MGR mgr, void * obj,
  360. const char * file, int line)
  361. {
  362. if (obj == NULL)
  363. return;
  364. unsigned char level = RAW_TO_LEVEL(obj);
  365. if (level < SLAB_LEVEL) {
  366. struct slab_debug * debug =
  367. (struct slab_debug *) (obj + slab_levels[level] +
  368. SLAB_CANARY_SIZE);
  369. debug->free.file = file;
  370. debug->free.line = line;
  371. }
  372. slab_free(mgr, obj);
  373. }
  374. #endif
  375. #endif /* SLABMGR_H */