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.

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