1
0

cache.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "cache.h"
  4. /*--------------------------------------------------------- */
  5. size_t
  6. lub_heap_cache__get_max_free(lub_heap_cache_t *this)
  7. {
  8. size_t size = 0;
  9. /* get the size from the cache */
  10. lub_heap_cache_bucket_t **ptr;
  11. for(ptr = this->m_bucket_start;
  12. ptr < this->m_bucket_end;
  13. ++ptr)
  14. {
  15. lub_blockpool_stats_t stats;
  16. lub_blockpool__get_stats(&(*ptr)->m_blockpool,&stats);
  17. if(stats.free_blocks && ((stats.block_size - sizeof(lub_heap_cache_bucket_t*)) > size))
  18. {
  19. size = stats.block_size - sizeof(lub_heap_cache_bucket_t*);
  20. }
  21. }
  22. return size;
  23. }
  24. /*--------------------------------------------------------- */
  25. static lub_heap_cache_bucket_t *
  26. _lub_heap_cache_find_bucket_from_size(lub_heap_cache_t *this,
  27. size_t size)
  28. {
  29. lub_heap_cache_bucket_t **ptr = this->m_bucket_start;
  30. /* leave space to put the bucket reference into place */
  31. size += sizeof(lub_heap_cache_bucket_t*);
  32. /* place powers of two into the correct bucket */
  33. --size;
  34. /* ignore sizes of 1,2 and 4 bytes */
  35. size >>= 3;
  36. for(;
  37. (ptr < this->m_bucket_end) && size;
  38. ++ptr)
  39. {
  40. size >>= 1;
  41. }
  42. return (ptr == this->m_bucket_end) ? 0 : *ptr;
  43. }
  44. /*--------------------------------------------------------- */
  45. static size_t
  46. lub_heap_cache_num_buckets(lub_heap_align_t max_block_size)
  47. {
  48. unsigned num_buckets = 0;
  49. /* count the number of buckets to be created */
  50. max_block_size >>= 3; /* ignore buckets of size 1,2 and 4 bytes */
  51. while(max_block_size)
  52. {
  53. ++num_buckets;
  54. max_block_size >>= 1;
  55. }
  56. return num_buckets;
  57. }
  58. /*--------------------------------------------------------- */
  59. size_t
  60. lub_heap_cache_overhead_size(lub_heap_align_t max_block_size,
  61. size_t num_max_blocks)
  62. {
  63. size_t overhead = 0;
  64. if(num_max_blocks && max_block_size)
  65. {
  66. /*
  67. * account for the cache overheads
  68. */
  69. size_t num_buckets = lub_heap_cache_num_buckets(max_block_size);
  70. /* cache control block */
  71. overhead += sizeof(lub_heap_cache_t);
  72. /* array of bucket pointers (-1 because one is contained in control block) */
  73. overhead += sizeof(lub_heap_cache_bucket_t*) * (num_buckets-1);
  74. /* fast size lookup array */
  75. overhead += sizeof(lub_heap_cache_bucket_t*) * max_block_size;
  76. /* buckets themselves */
  77. overhead += num_buckets * offsetof(lub_heap_cache_bucket_t,m_memory_start);
  78. }
  79. return overhead;
  80. }
  81. /*--------------------------------------------------------- */
  82. size_t
  83. lub_heap_overhead_size(lub_heap_align_t max_block_size,
  84. size_t num_max_blocks)
  85. {
  86. /* heap control block */
  87. size_t overhead = sizeof(lub_heap_t);
  88. /* need at least one free blocks worth */
  89. overhead += sizeof(lub_heap_free_block_t);
  90. if(max_block_size && num_max_blocks)
  91. {
  92. size_t num_buckets = lub_heap_cache_num_buckets(max_block_size);
  93. size_t bucket_size = max_block_size * num_max_blocks;
  94. /* now add any cache overhead contribution */
  95. overhead += lub_heap_cache_overhead_size(max_block_size,num_max_blocks);
  96. /* add the bucket contents */
  97. overhead += (num_buckets * bucket_size);
  98. }
  99. return overhead;
  100. }
  101. /*--------------------------------------------------------- */
  102. lub_heap_status_t
  103. lub_heap_cache_init(lub_heap_t *this,
  104. lub_heap_align_t max_block_size,
  105. size_t num_max_blocks)
  106. {
  107. lub_heap_status_t status = LUB_HEAP_FAILED;
  108. do
  109. {
  110. size_t bucket_size = (max_block_size * num_max_blocks);
  111. unsigned num_buckets = lub_heap_cache_num_buckets(max_block_size);
  112. size_t block_size = 8;
  113. lub_heap_cache_t *cache;
  114. lub_heap_cache_bucket_t **ptr;
  115. int i;
  116. /* cannot call this multiple times */
  117. if(this->cache) break;
  118. /* allocate a cache control block */
  119. cache = this->cache = lub_heap_static_alloc(this,
  120. sizeof(lub_heap_cache_t) + sizeof(lub_heap_cache_bucket_t*)*(num_buckets-1));
  121. if(!cache) break;
  122. cache->m_max_block_size = max_block_size;
  123. cache->m_num_max_blocks = num_max_blocks;
  124. cache->m_num_buckets = num_buckets;
  125. cache->m_bucket_size = bucket_size;
  126. cache->m_misses = 0;
  127. cache->m_bucket_end = &cache->m_bucket_start[num_buckets];
  128. /* allocate each bucket for the cache */
  129. for(ptr = cache->m_bucket_start;
  130. ptr < cache->m_bucket_end;
  131. ++ptr)
  132. {
  133. *ptr = lub_heap_static_alloc(this,
  134. bucket_size + offsetof(lub_heap_cache_bucket_t,m_memory_start));
  135. if(!*ptr) break;
  136. /* set up each bucket */
  137. lub_heap_cache_bucket_init(*ptr,
  138. cache,
  139. block_size,
  140. bucket_size);
  141. block_size <<= 1;
  142. }
  143. if(ptr != cache->m_bucket_end) break;
  144. /* now create a fast lookup for resolving size to bucket */
  145. cache->m_bucket_lookup = lub_heap_static_alloc(this,sizeof(lub_heap_cache_bucket_t*)*max_block_size);
  146. if(!cache->m_bucket_lookup) break;
  147. for(i = 0;
  148. i < cache->m_max_block_size;
  149. ++i)
  150. {
  151. cache->m_bucket_lookup[i] = _lub_heap_cache_find_bucket_from_size(cache,i+1);
  152. }
  153. status = LUB_HEAP_OK;
  154. } while(0);
  155. return status;
  156. }
  157. /*--------------------------------------------------------- */
  158. lub_heap_cache_bucket_t *
  159. lub_heap_cache_find_bucket_from_address(lub_heap_cache_t *this,
  160. const void *address)
  161. {
  162. lub_heap_cache_bucket_t **bucket = (void*)address;
  163. /* get the bucket reference */
  164. --bucket;
  165. if( (*bucket > this->m_bucket_start[0])
  166. || (*bucket < this->m_bucket_end[-1]) )
  167. {
  168. bucket = 0;
  169. }
  170. return bucket ? *bucket : 0;
  171. }
  172. /*--------------------------------------------------------- */
  173. lub_heap_cache_bucket_t *
  174. lub_heap_cache_find_bucket_from_size(lub_heap_cache_t *this,
  175. size_t size)
  176. {
  177. lub_heap_cache_bucket_t *bucket = 0;
  178. /* simply get the result from the fast lookup table */
  179. if(size > 0)
  180. {
  181. if(size <= this->m_max_block_size)
  182. {
  183. bucket = this->m_bucket_lookup[size-1];
  184. }
  185. else
  186. {
  187. ++this->m_misses;
  188. }
  189. }
  190. return bucket;
  191. }
  192. /*--------------------------------------------------------- */
  193. lub_heap_status_t
  194. lub_heap_cache_realloc(lub_heap_t *this,
  195. char **ptr,
  196. size_t size)
  197. {
  198. lub_heap_status_t status = LUB_HEAP_FAILED;
  199. lub_heap_cache_bucket_t *old_bucket = 0;
  200. lub_heap_cache_bucket_t *new_bucket = size ? lub_heap_cache_find_bucket_from_size(this->cache,size) : 0;
  201. char *new_ptr = 0;
  202. do
  203. {
  204. char *old_ptr = *ptr;
  205. if(old_ptr)
  206. {
  207. old_bucket = lub_heap_cache_find_bucket_from_address(this->cache,old_ptr);
  208. }
  209. else if (size == 0)
  210. {
  211. /* nothing to do */
  212. status = LUB_HEAP_OK;
  213. break;
  214. }
  215. if(old_bucket)
  216. {
  217. /********************************
  218. * old from CACHE, new from CACHE
  219. ******************************** */
  220. if(new_bucket)
  221. {
  222. if(old_bucket == new_bucket)
  223. {
  224. /* keep the existing cache block which is big enough */
  225. new_ptr = old_ptr;
  226. status = LUB_HEAP_OK;
  227. break;
  228. }
  229. /* try and get memory from the cache */
  230. new_ptr = lub_heap_cache_bucket_alloc(new_bucket);
  231. if(new_ptr)
  232. {
  233. if(old_ptr)
  234. {
  235. /* copy the old details across */
  236. memcpy(new_ptr,old_ptr,size);
  237. /* release the old cache block */
  238. status = lub_heap_cache_bucket_free(old_bucket,old_ptr);
  239. if(LUB_HEAP_OK != status)
  240. {
  241. break;
  242. }
  243. }
  244. /* all done */
  245. status = LUB_HEAP_OK;
  246. break;
  247. }
  248. }
  249. /********************************
  250. * old from CACHE, new from HEAP
  251. ******************************** */
  252. if(size)
  253. {
  254. /* get new memory from the dynamic heap */
  255. status = lub_heap_raw_realloc(this,&new_ptr,size,LUB_HEAP_ALIGN_NATIVE);
  256. if(LUB_HEAP_OK != status)
  257. {
  258. break;
  259. }
  260. /* copy the old details across */
  261. memcpy(new_ptr,old_ptr,size);
  262. }
  263. /* release the old cache block */
  264. status = lub_heap_cache_bucket_free(old_bucket,old_ptr);
  265. }
  266. else
  267. {
  268. /********************************
  269. * old from HEAP, new from CACHE
  270. ******************************** */
  271. if(size)
  272. {
  273. if(new_bucket)
  274. {
  275. /* try and get memory from the cache */
  276. new_ptr = lub_heap_cache_bucket_alloc(new_bucket);
  277. if(new_ptr)
  278. {
  279. if(old_ptr)
  280. {
  281. /* copy the old details across */
  282. memcpy(new_ptr,old_ptr,size);
  283. size = 0;
  284. }
  285. else
  286. {
  287. /* all done */
  288. status = LUB_HEAP_OK;
  289. break;
  290. }
  291. }
  292. }
  293. }
  294. else if(!old_ptr)
  295. {
  296. /* nothing to do */
  297. status = LUB_HEAP_OK;
  298. break;
  299. }
  300. /********************************
  301. * old from HEAP, new from HEAP
  302. ******************************** */
  303. /* release old memory and potentially get new memory */
  304. status = lub_heap_raw_realloc(this,&old_ptr,size,LUB_HEAP_ALIGN_NATIVE);
  305. if(LUB_HEAP_OK != status)
  306. {
  307. break;
  308. }
  309. else if(size)
  310. {
  311. new_ptr = old_ptr;
  312. }
  313. }
  314. } while(0);
  315. if(LUB_HEAP_OK == status)
  316. {
  317. /* set up the new pointer value */
  318. *ptr = new_ptr;
  319. }
  320. return status;
  321. }
  322. /*--------------------------------------------------------- */
  323. void
  324. lub_heap_cache_show(lub_heap_cache_t *this)
  325. {
  326. lub_heap_cache_bucket_t **ptr;
  327. printf(" size num blocks current high-tide cumulative misses\n");
  328. printf(" ---------- ---------- ---------- ---------- ---------- ----------\n");
  329. for(ptr = this->m_bucket_start;
  330. ptr < this->m_bucket_end;
  331. ++ptr)
  332. {
  333. lub_blockpool_t *blockpool = &(*ptr)->m_blockpool;
  334. lub_blockpool_stats_t stats;
  335. lub_blockpool__get_stats(blockpool,&stats);
  336. printf(" %10"SIZE_FMT" %10"SIZE_FMT" %10"SIZE_FMT" %10"SIZE_FMT" %10"SIZE_FMT" %10"SIZE_FMT"\n",
  337. stats.block_size,
  338. stats.num_blocks,
  339. stats.alloc_blocks,
  340. stats.alloc_hightide_blocks,
  341. stats.alloc_total_blocks,
  342. stats.alloc_failures);
  343. }
  344. printf(" %10u %10s %10s %10s %10s %10"SIZE_FMT"\n",
  345. this->m_max_block_size,
  346. "-",
  347. "-",
  348. "-",
  349. "-",
  350. this->m_misses);
  351. }
  352. /*--------------------------------------------------------- */
  353. void
  354. lub_heap_cache__get_stats(lub_heap_cache_t *this,
  355. lub_heap_stats_t *stats)
  356. {
  357. lub_heap_cache_bucket_t **ptr;
  358. memset(stats,0,sizeof(lub_heap_stats_t));
  359. stats->free_overhead = lub_heap_cache_overhead_size(this->m_max_block_size,this->m_num_max_blocks);
  360. for(ptr = this->m_bucket_start;
  361. ptr < this->m_bucket_end;
  362. ++ptr)
  363. {
  364. lub_blockpool_t *blockpool = &(*ptr)->m_blockpool;
  365. lub_blockpool_stats_t bucket_stats;
  366. size_t block_size;
  367. size_t block_overhead = sizeof(lub_heap_cache_bucket_t*); /* used for fast lookup from address */
  368. lub_blockpool__get_stats(blockpool,&bucket_stats);
  369. block_size = (bucket_stats.block_size - block_overhead);
  370. stats->free_blocks += bucket_stats.free_blocks;
  371. stats->free_bytes += block_size * bucket_stats.free_blocks;
  372. stats->free_overhead += block_overhead * bucket_stats.free_blocks;
  373. stats->alloc_blocks += bucket_stats.alloc_blocks;
  374. stats->alloc_bytes += block_size * bucket_stats.alloc_blocks;
  375. stats->alloc_overhead += block_overhead * bucket_stats.alloc_blocks;
  376. stats->alloc_total_blocks += bucket_stats.alloc_total_blocks;
  377. stats->alloc_total_bytes += block_size * bucket_stats.alloc_total_blocks;
  378. }
  379. }
  380. /*--------------------------------------------------------- */