XCache is a fast, stable PHP opcode cacher that has been proven and is now running on production servers under high load. https://xcache.lighttpd.net/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

382 lines
7.8 KiB

  1. #ifdef TEST
  2. #include <limits.h>
  3. #include <stdio.h>
  4. #else
  5. #include <php.h>
  6. #endif
  7. #include <assert.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include "mem.h"
  11. #include "align.h"
  12. #ifdef TEST
  13. # define ALLOC_DEBUG
  14. #endif
  15. #ifdef ALLOC_DEBUG
  16. # define ALLOC_DEBUG_BLOCK_CHECK
  17. #endif
  18. #if 0
  19. #undef ALLOC_DEBUG_BLOCK_CHECK
  20. #endif
  21. #define CHAR_PTR(p) ((char *) (p))
  22. #define PADD(p, a) (CHAR_PTR(p) + a)
  23. #define PSUB(p1, p2) (CHAR_PTR(p1) - CHAR_PTR(p2))
  24. // {{{ mem
  25. struct _xc_block_t {
  26. #ifdef ALLOC_DEBUG_BLOCK_CHECK
  27. unsigned int magic;
  28. #endif
  29. xc_memsize_t size; /* reserved even after alloc */
  30. xc_block_t *next; /* not used after alloc */
  31. };
  32. struct _xc_mem_t {
  33. xc_memsize_t size;
  34. xc_memsize_t avail; /* total free */
  35. xc_block_t headblock[1]; /* just as a pointer to first block*/
  36. };
  37. #ifndef XtOffsetOf
  38. # include <linux/stddef.h>
  39. # define XtOffsetOf(s_type, field) offsetof(s_type, field)
  40. #endif
  41. #define SizeOf(type, field) sizeof( ((type *) 0)->field )
  42. #define BLOCK_HEADER_SIZE() (ALIGN( XtOffsetOf(xc_block_t, size) + SizeOf(xc_block_t, size) ))
  43. #define BLOCK_MAGIC ((unsigned int) 0x87655678)
  44. /* }}} */
  45. static inline void xc_block_setup(xc_block_t *b, xc_memsize_t size, xc_block_t *next) /* {{{ */
  46. {
  47. #ifdef ALLOC_DEBUG_BLOCK_CHECK
  48. b->magic = BLOCK_MAGIC;
  49. #endif
  50. b->size = size;
  51. b->next = next;
  52. }
  53. /* }}} */
  54. #ifdef ALLOC_DEBUG_BLOCK_CHECK
  55. static void xc_block_check(xc_block_t *b) /* {{{ */
  56. {
  57. if (b->magic != BLOCK_MAGIC) {
  58. fprintf(stderr, "0x%X != 0x%X magic wrong \n", b->magic, BLOCK_MAGIC);
  59. }
  60. }
  61. /* }}} */
  62. #else
  63. # define xc_block_check(b) do { } while(0)
  64. #endif
  65. void *xc_mem_malloc(xc_mem_t *mem, xc_memsize_t size) /* {{{ */
  66. {
  67. xc_block_t *prev, *cur;
  68. xc_block_t *newb, *b;
  69. xc_memsize_t realsize;
  70. xc_memsize_t minsize;
  71. void *p;
  72. /* [xc_block_t:size|size] */
  73. realsize = BLOCK_HEADER_SIZE() + size;
  74. /* realsize is ALIGNed so next block start at ALIGNed address */
  75. realsize = ALIGN(realsize);
  76. #ifdef ALLOC_DEBUG
  77. fprintf(stderr, "avail: %d (%dKB). Allocate size: %d realsize: %d (%dKB)"
  78. , mem->avail, mem->avail / 1024
  79. , size
  80. , realsize, realsize / 1024
  81. );
  82. #endif
  83. do {
  84. p = NULL;
  85. if (mem->avail < realsize) {
  86. #ifdef ALLOC_DEBUG
  87. fprintf(stderr, " oom\n");
  88. #endif
  89. break;
  90. }
  91. b = NULL;
  92. minsize = INT_MAX;
  93. /* prev|cur */
  94. for (prev = mem->headblock; prev->next; prev = cur) {
  95. /* while (prev->next != 0) { */
  96. cur = prev->next;
  97. xc_block_check(cur);
  98. if (cur->size == realsize) {
  99. /* found a perfect fit, stop searching */
  100. b = prev;
  101. break;
  102. }
  103. /* make sure we can split on the block */
  104. else if (cur->size > (sizeof(xc_block_t) + realsize) &&
  105. cur->size < minsize) {
  106. /* cur is acceptable and memller */
  107. b = prev;
  108. minsize = cur->size;
  109. }
  110. prev = cur;
  111. }
  112. if (b == NULL) {
  113. #ifdef ALLOC_DEBUG
  114. fprintf(stderr, " no fit chunk\n");
  115. #endif
  116. break;
  117. }
  118. prev = b;
  119. cur = prev->next;
  120. p = PADD(cur, BLOCK_HEADER_SIZE());
  121. /* update the block header */
  122. mem->avail -= realsize;
  123. /* perfect fit, just unlink */
  124. if (cur->size == realsize) {
  125. prev->next = cur->next;
  126. #ifdef ALLOC_DEBUG
  127. fprintf(stderr, " perfect fit. Got: %p\n", p);
  128. #endif
  129. break;
  130. }
  131. /* make new free block after alloced space */
  132. /* save, as it might be overwrited by newb (cur->size is ok) */
  133. b = cur->next;
  134. /* prev|cur |next=b */
  135. newb = (xc_block_t *)PADD(cur, realsize);
  136. xc_block_setup(newb, cur->size - realsize, b);
  137. cur->size = realsize;
  138. /* prev|cur|newb|next
  139. * `--^
  140. */
  141. #ifdef ALLOC_DEBUG
  142. fprintf(stderr, " -> avail: %d (%dKB). new next: %p offset: %d %dKB. Got: %p\n"
  143. , mem->avail, mem->avail / 1024
  144. , newb
  145. , PSUB(newb, mem), PSUB(newb, mem) / 1024
  146. , p
  147. );
  148. #endif
  149. prev->next = newb;
  150. /* prev|cur|newb|next
  151. * `-----^
  152. */
  153. } while (0);
  154. return p;
  155. }
  156. /* }}} */
  157. int xc_mem_free(xc_mem_t *mem, const void *p) /* {{{ return block size freed */
  158. {
  159. xc_block_t *cur, *b;
  160. int size;
  161. cur = (xc_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
  162. #ifdef ALLOC_DEBUG
  163. fprintf(stderr, "freeing: %p", p);
  164. fprintf(stderr, ", size=%d", cur->size);
  165. #endif
  166. xc_block_check(cur);
  167. assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
  168. /* find free block right before the p */
  169. b = mem->headblock;
  170. while (b->next != 0 && b->next < cur) {
  171. b = b->next;
  172. }
  173. /* restore block */
  174. cur->next = b->next;
  175. b->next = cur;
  176. size = cur->size;
  177. #ifdef ALLOC_DEBUG
  178. fprintf(stderr, ", avail %d (%dKB)", mem->avail, mem->avail / 1024);
  179. #endif
  180. mem->avail += size;
  181. /* combine prev|cur */
  182. if (PADD(b, b->size) == (char *)cur) {
  183. b->size += cur->size;
  184. b->next = cur->next;
  185. cur = b;
  186. #ifdef ALLOC_DEBUG
  187. fprintf(stderr, ", combine prev");
  188. #endif
  189. }
  190. /* combine cur|next */
  191. b = cur->next;
  192. if (PADD(cur, cur->size) == (char *)b) {
  193. cur->size += b->size;
  194. cur->next = b->next;
  195. #ifdef ALLOC_DEBUG
  196. fprintf(stderr, ", combine next");
  197. #endif
  198. }
  199. #ifdef ALLOC_DEBUG
  200. fprintf(stderr, " -> avail %d (%dKB)\n", mem->avail, mem->avail / 1024);
  201. #endif
  202. return size;
  203. }
  204. /* }}} */
  205. void *xc_mem_calloc(xc_mem_t *mem, xc_memsize_t memb, xc_memsize_t size) /* {{{ */
  206. {
  207. xc_memsize_t realsize = memb * size;
  208. void *p = xc_mem_malloc(mem, realsize);
  209. if (p) {
  210. memset(p, 0, realsize);
  211. }
  212. return p;
  213. }
  214. /* }}} */
  215. void *xc_mem_realloc(xc_mem_t *mem, const void *p, xc_memsize_t size) /* {{{ */
  216. {
  217. void *newp = xc_mem_malloc(mem, size);
  218. if (p && newp) {
  219. memcpy(newp, p, size);
  220. xc_mem_free(mem, p);
  221. }
  222. return newp;
  223. }
  224. /* }}} */
  225. char *xc_mem_strndup(xc_mem_t *mem, const char *str, xc_memsize_t len) /* {{{ */
  226. {
  227. void *p = xc_mem_malloc(mem, len + 1);
  228. if (p) {
  229. memcpy(p, str, len + 1);
  230. }
  231. return p;
  232. }
  233. /* }}} */
  234. char *xc_mem_strdup(xc_mem_t *mem, const char *str) /* {{{ */
  235. {
  236. return xc_mem_strndup(mem, str, strlen(str));
  237. }
  238. /* }}} */
  239. xc_memsize_t xc_mem_avail(xc_mem_t *mem) /* {{{ */
  240. {
  241. return mem->avail;
  242. }
  243. /* }}} */
  244. xc_memsize_t xc_mem_size(xc_mem_t *mem) /* {{{ */
  245. {
  246. return mem->size;
  247. }
  248. /* }}} */
  249. const xc_block_t *xc_mem_freeblock_first(xc_mem_t *mem) /* {{{ */
  250. {
  251. return mem->headblock->next;
  252. }
  253. /* }}} */
  254. const xc_block_t *xc_mem_freeblock_next(const xc_block_t *block) /* {{{ */
  255. {
  256. return block->next;
  257. }
  258. /* }}} */
  259. xc_memsize_t xc_mem_block_size(const xc_block_t *block) /* {{{ */
  260. {
  261. return block->size;
  262. }
  263. /* }}} */
  264. xc_memsize_t xc_mem_block_offset(const xc_mem_t *mem, const xc_block_t *block) /* {{{ */
  265. {
  266. return ((char *) block) - ((char *) mem);
  267. }
  268. /* }}} */
  269. xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
  270. {
  271. xc_mem_t *mem;
  272. xc_block_t *b;
  273. #define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
  274. /* requires at least the header and 1 tail block */
  275. if (size < MINSIZE) {
  276. fprintf(stderr, "xc_mem_init requires %d bytes at least\n", MINSIZE);
  277. return NULL;
  278. }
  279. mem = (xc_mem_t *) ptr;
  280. mem->size = size;
  281. mem->avail = size - MINSIZE;
  282. /* pointer to first block, right after ALIGNed header */
  283. b = mem->headblock;
  284. xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
  285. /* first block*/
  286. b = b->next;
  287. xc_block_setup(b, mem->avail, 0);
  288. #undef MINSIZE
  289. return mem;
  290. }
  291. /* }}} */
  292. void xc_mem_destroy(xc_mem_t *mem) /* {{{ */
  293. {
  294. }
  295. /* }}} */
  296. #ifdef TEST
  297. /* {{{ */
  298. #undef CHECK
  299. #define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
  300. #include <time.h>
  301. int main()
  302. {
  303. int count = 0;
  304. void *p;
  305. void *memory;
  306. xc_mem_t *mem;
  307. void **ptrs;
  308. int size, i;
  309. #if 0
  310. fprintf(stderr, "%s", "Input test size: ");
  311. scanf("%d", &size);
  312. #else
  313. size = 100;
  314. #endif
  315. CHECK(memory = malloc(size), "OOM");
  316. CHECK(ptrs = malloc(size * sizeof(void*)), "OOM");
  317. CHECK(mem = xc_mem_init(memory, size), "Failed init memory allocator");
  318. while ((p = xc_mem_malloc(mem, 1))) {
  319. ptrs[count ++] = p;
  320. }
  321. fprintf(stderr, "count=%d, random freeing\n", count);
  322. srandom(time(NULL));
  323. while (count) {
  324. i = (random() % count);
  325. fprintf(stderr, "freeing %d: ", i);
  326. xc_mem_free(mem, ptrs[i]);
  327. ptrs[i] = ptrs[count - 1];
  328. count --;
  329. }
  330. free(ptrs);
  331. free(memory);
  332. return 0;
  333. }
  334. /* }}} */
  335. #endif