memmgr.h 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276
  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. * memmgr.h
  17. *
  18. * This file contains implementation of fixed-size memory allocator.
  19. */
  20. #ifndef MEMMGR_H
  21. #define MEMMGR_H
  22. #include "list.h"
  23. #include <sys/mman.h>
  24. #ifndef OBJ_TYPE
  25. #error "OBJ_TYPE not defined"
  26. #endif
  27. #ifndef system_malloc
  28. #error "macro \"void * system_malloc (size_t size)\" not declared"
  29. #endif
  30. #ifndef system_free
  31. #error "macro \"void * system_free (void * ptr, size_t size)\" not declared"
  32. #endif
  33. #ifndef system_lock
  34. #define system_lock() ({})
  35. #endif
  36. #ifndef system_unlock
  37. #define system_unlock() ({})
  38. #endif
  39. DEFINE_LIST(mem_obj);
  40. typedef struct mem_obj {
  41. union {
  42. LIST_TYPE(mem_obj) __list;
  43. OBJ_TYPE obj;
  44. };
  45. } MEM_OBJ_TYPE, * MEM_OBJ;
  46. DEFINE_LIST(mem_area);
  47. typedef struct mem_area {
  48. LIST_TYPE(mem_area) __list;
  49. unsigned int size;
  50. MEM_OBJ_TYPE objs[];
  51. } MEM_AREA_TYPE, * MEM_AREA;
  52. DEFINE_LISTP(mem_area);
  53. DEFINE_LISTP(mem_obj);
  54. typedef struct mem_mgr {
  55. LISTP_TYPE(mem_area) area_list;
  56. LISTP_TYPE(mem_obj) free_list;
  57. size_t size;
  58. MEM_OBJ_TYPE * obj, * obj_top;
  59. MEM_AREA active_area;
  60. } MEM_MGR_TYPE, * MEM_MGR;
  61. #define __SUM_OBJ_SIZE(size) (sizeof(MEM_OBJ_TYPE) * (size))
  62. #define __MIN_MEM_SIZE() (sizeof(MEM_MGR_TYPE) + sizeof(MEM_AREA_TYPE))
  63. #define __MAX_MEM_SIZE(size) (__MIN_MEM_SIZE() + __SUM_OBJ_SIZE(size))
  64. #ifdef PAGE_SIZE
  65. static inline int size_align_down (int size)
  66. {
  67. int s = __MAX_MEM_SIZE(size) - sizeof(MEM_MGR_TYPE);
  68. int p = s - (s & ~(PAGE_SIZE - 1));
  69. int o = __SUM_OBJ_SIZE(1);
  70. return size - p / o - (p % o ? 1 : 0);
  71. }
  72. static inline int size_align_up (int size)
  73. {
  74. int s = __MAX_MEM_SIZE(size) - sizeof(MEM_MGR_TYPE);
  75. int p = ((s + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1)) - s;
  76. int o = __SUM_OBJ_SIZE(1);
  77. return size + p / o;
  78. }
  79. static inline int init_align_down (int size)
  80. {
  81. int s = __MAX_MEM_SIZE(size);
  82. int p = s - (s & ~(PAGE_SIZE - 1));
  83. int o = __SUM_OBJ_SIZE(1);
  84. return size - p / o - (p % o ? 1 : 0);
  85. }
  86. static inline int init_align_up (int size)
  87. {
  88. int s = __MAX_MEM_SIZE(size);
  89. int p = ((s + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1)) - s;
  90. int o = __SUM_OBJ_SIZE(1);
  91. return size + p / o;
  92. }
  93. #endif
  94. static inline void __set_free_mem_area (MEM_AREA area, MEM_MGR mgr)
  95. {
  96. mgr->size += area->size;
  97. mgr->obj = area->objs;
  98. mgr->obj_top = area->objs + area->size;
  99. mgr->active_area = area;
  100. }
  101. static inline MEM_MGR create_mem_mgr (unsigned int size)
  102. {
  103. void * mem = system_malloc(__MAX_MEM_SIZE(size));
  104. MEM_AREA area;
  105. MEM_MGR mgr;
  106. if (!mem)
  107. return NULL;
  108. mgr = (MEM_MGR) mem;
  109. mgr->size = 0;
  110. area = (MEM_AREA) (mem + sizeof(MEM_MGR_TYPE));
  111. area->size = size;
  112. INIT_LIST_HEAD(area, __list);
  113. INIT_LISTP(&mgr->area_list);
  114. listp_add(area, &mgr->area_list, __list);
  115. INIT_LISTP(&mgr->free_list);
  116. __set_free_mem_area(area, mgr);
  117. return mgr;
  118. }
  119. static inline MEM_MGR enlarge_mem_mgr (MEM_MGR mgr, unsigned int size)
  120. {
  121. MEM_AREA area;
  122. area = (MEM_AREA) system_malloc(sizeof(MEM_AREA_TYPE) +
  123. __SUM_OBJ_SIZE(size));
  124. if (!area)
  125. return NULL;
  126. system_lock();
  127. area->size = size;
  128. INIT_LIST_HEAD(area, __list);
  129. listp_add(area, &mgr->area_list, __list);
  130. __set_free_mem_area(area, mgr);
  131. system_unlock();
  132. return mgr;
  133. }
  134. static inline void destroy_mem_mgr (MEM_MGR mgr)
  135. {
  136. MEM_AREA tmp, n, first = NULL;
  137. first = tmp = listp_first_entry(&mgr->area_list, MEM_AREA_TYPE, __list);
  138. if (!first)
  139. goto free_mgr;
  140. listp_for_each_entry_safe_continue(tmp, n, &mgr->area_list, __list) {
  141. listp_del(tmp, &mgr->area_list, __list);
  142. system_free(tmp, sizeof(MEM_AREA_TYPE) + __SUM_OBJ_SIZE(tmp->size));
  143. }
  144. free_mgr:
  145. system_free(mgr, __MAX_MEM_SIZE(first->size));
  146. }
  147. static inline OBJ_TYPE * get_mem_obj_from_mgr (MEM_MGR mgr)
  148. {
  149. MEM_OBJ mobj;
  150. system_lock();
  151. if (mgr->obj == mgr->obj_top && listp_empty(&mgr->free_list)) {
  152. system_unlock();
  153. return NULL;
  154. }
  155. if (!listp_empty(&mgr->free_list)) {
  156. mobj = listp_first_entry(&mgr->free_list, MEM_OBJ_TYPE, __list);
  157. listp_del_init(mobj, &mgr->free_list, __list);
  158. check_list_head(MEM_OBJ, &mgr->free_list, __list);
  159. } else {
  160. mobj = mgr->obj++;
  161. }
  162. system_unlock();
  163. return &mobj->obj;
  164. }
  165. static inline OBJ_TYPE * get_mem_obj_from_mgr_enlarge (MEM_MGR mgr,
  166. unsigned int size)
  167. {
  168. MEM_OBJ mobj;
  169. system_lock();
  170. if (mgr->obj == mgr->obj_top && listp_empty(&mgr->free_list)) {
  171. size_t mgr_size = mgr->size;
  172. MEM_AREA area;
  173. /* If there is a previously allocated area, just activate it. */
  174. area = listp_prev_entry(mgr->active_area, &mgr->area_list, __list);
  175. if (area) {
  176. __set_free_mem_area(area, mgr);
  177. goto alloc;
  178. }
  179. system_unlock();
  180. if (!size)
  181. return NULL;
  182. /* There can be concurrent attempt to try to enlarge the
  183. allocator, but we prevent deadlocks or crashes. */
  184. area = (MEM_AREA) system_malloc(sizeof(MEM_AREA_TYPE) +
  185. __SUM_OBJ_SIZE(size));
  186. if (!area)
  187. return NULL;
  188. system_lock();
  189. area->size = size;
  190. INIT_LIST_HEAD(area, __list);
  191. /* There can be concurrent operations to extend the manager. In case
  192. * someone has already enlarged the space, we just add the new area to
  193. * the list for later use. */
  194. listp_add(area, &mgr->area_list, __list);
  195. if (mgr_size == mgr->size) /* check if the size has changed */
  196. __set_free_mem_area(area, mgr);
  197. }
  198. alloc:
  199. if (!listp_empty(&mgr->free_list)) {
  200. mobj = listp_first_entry(&mgr->free_list, MEM_OBJ_TYPE, __list);
  201. listp_del_init(mobj, &mgr->free_list, __list);
  202. check_list_head(MEM_OBJ, &mgr->free_list, __list);
  203. } else {
  204. mobj = mgr->obj++;
  205. }
  206. assert(mgr->obj <= mgr->obj_top);
  207. system_unlock();
  208. return &mobj->obj;
  209. }
  210. static inline void free_mem_obj_to_mgr (MEM_MGR mgr, OBJ_TYPE * obj)
  211. {
  212. MEM_OBJ mobj = container_of(obj, MEM_OBJ_TYPE, obj);
  213. system_lock();
  214. MEM_AREA area, found = NULL;
  215. listp_for_each_entry(area, &mgr->area_list, __list)
  216. if (mobj >= area->objs && mobj < area->objs + area->size) {
  217. found = area;
  218. break;
  219. }
  220. if (found) {
  221. INIT_LIST_HEAD(mobj, __list);
  222. listp_add_tail(mobj, &mgr->free_list, __list);
  223. check_list_head(MEM_OBJ, &mgr->free_list, __list);
  224. }
  225. system_unlock();
  226. }
  227. #endif /* MEMMGR_H */