slabmgr.h 14 KB

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