klish/lub/heap/cache.c

#include <stdio.h>
#include <string.h>
#include "cache.h"

/*--------------------------------------------------------- */
size_t lub_heap_cache__get_max_free(lub_heap_cache_t * this)
{
	size_t size = 0;
	/* get the size from the cache */
	lub_heap_cache_bucket_t **ptr;

	for (ptr = this->m_bucket_start; ptr < this->m_bucket_end; ++ptr) {
		lub_blockpool_stats_t stats;
		lub_blockpool__get_stats(&(*ptr)->m_blockpool, &stats);
		if (stats.free_blocks
		    && ((stats.block_size - sizeof(lub_heap_cache_bucket_t *)) >
			size)) {
			size =
			    stats.block_size -
			    sizeof(lub_heap_cache_bucket_t *);
		}
	}
	return size;
}

/*--------------------------------------------------------- */
static lub_heap_cache_bucket_t
    *_lub_heap_cache_find_bucket_from_size(lub_heap_cache_t * this, size_t size)
{
	lub_heap_cache_bucket_t **ptr = this->m_bucket_start;
	/* leave space to put the bucket reference into place */
	size += sizeof(lub_heap_cache_bucket_t *);
	/* place powers of two into the correct bucket */
	--size;
	/* ignore sizes of 1,2 and 4 bytes */
	size >>= 3;
	for (; (ptr < this->m_bucket_end) && size; ++ptr) {
		size >>= 1;
	}
	return (ptr == this->m_bucket_end) ? 0 : *ptr;
}

/*--------------------------------------------------------- */
static size_t lub_heap_cache_num_buckets(lub_heap_align_t max_block_size)
{
	unsigned num_buckets = 0;

	/* count the number of buckets to be created */
	max_block_size >>= 3;	/* ignore buckets of size 1,2 and 4 bytes */
	while (max_block_size) {
		++num_buckets;
		max_block_size >>= 1;
	}
	return num_buckets;
}

/*--------------------------------------------------------- */
size_t
lub_heap_cache_overhead_size(lub_heap_align_t max_block_size,
			     size_t num_max_blocks)
{
	size_t overhead = 0;
	if (num_max_blocks && max_block_size) {
		/* 
		 * account for the cache overheads
		 */
		size_t num_buckets = lub_heap_cache_num_buckets(max_block_size);

		/* cache control block */
		overhead += sizeof(lub_heap_cache_t);

		/* array of bucket pointers (-1 because one is contained in control block) */
		overhead +=
		    sizeof(lub_heap_cache_bucket_t *) * (num_buckets - 1);

		/* fast size lookup array */
		overhead += sizeof(lub_heap_cache_bucket_t *) * max_block_size;

		/* buckets themselves */
		overhead +=
		    num_buckets * offsetof(lub_heap_cache_bucket_t,
					   m_memory_start);
	}
	return overhead;
}

/*--------------------------------------------------------- */
size_t
lub_heap_overhead_size(lub_heap_align_t max_block_size, size_t num_max_blocks)
{
	/* heap control block */
	size_t overhead = sizeof(lub_heap_t);

	/* need at least one free blocks worth */
	overhead += sizeof(lub_heap_free_block_t);

	if (max_block_size && num_max_blocks) {
		size_t num_buckets = lub_heap_cache_num_buckets(max_block_size);
		size_t bucket_size = max_block_size * num_max_blocks;

		/* now add any cache overhead contribution */
		overhead +=
		    lub_heap_cache_overhead_size(max_block_size,
						 num_max_blocks);

		/* add the bucket contents */
		overhead += (num_buckets * bucket_size);
	}
	return overhead;
}

/*--------------------------------------------------------- */
lub_heap_status_t
lub_heap_cache_init(lub_heap_t * this,
		    lub_heap_align_t max_block_size, size_t num_max_blocks)
{
	lub_heap_status_t status = LUB_HEAP_FAILED;
	do {
		size_t bucket_size = (max_block_size * num_max_blocks);
		unsigned num_buckets =
		    lub_heap_cache_num_buckets(max_block_size);
		size_t block_size = 8;
		lub_heap_cache_t *cache;
		lub_heap_cache_bucket_t **ptr;
		int i;
		/* cannot call this multiple times */
		if (this->cache)
			break;

		/* allocate a cache control block */
		cache = this->cache = lub_heap_static_alloc(this,
							    sizeof
							    (lub_heap_cache_t) +
							    sizeof
							    (lub_heap_cache_bucket_t
							     *) * (num_buckets -
								   1));
		if (!cache)
			break;

		cache->m_max_block_size = max_block_size;
		cache->m_num_max_blocks = num_max_blocks;
		cache->m_num_buckets = num_buckets;
		cache->m_bucket_size = bucket_size;
		cache->m_misses = 0;
		cache->m_bucket_end = &cache->m_bucket_start[num_buckets];

		/* allocate each bucket for the cache */
		for (ptr = cache->m_bucket_start;
		     ptr < cache->m_bucket_end; ++ptr) {
			*ptr = lub_heap_static_alloc(this,
						     bucket_size +
						     offsetof
						     (lub_heap_cache_bucket_t,
						      m_memory_start));
			if (!*ptr)
				break;
			/* set up each bucket */
			lub_heap_cache_bucket_init(*ptr,
						   cache,
						   block_size, bucket_size);
			block_size <<= 1;
		}
		if (ptr != cache->m_bucket_end)
			break;

		/* now create a fast lookup for resolving size to bucket */
		cache->m_bucket_lookup =
		    lub_heap_static_alloc(this,
					  sizeof(lub_heap_cache_bucket_t *) *
					  max_block_size);
		if (!cache->m_bucket_lookup)
			break;

		for (i = 0; i < cache->m_max_block_size; ++i) {
			cache->m_bucket_lookup[i] =
			    _lub_heap_cache_find_bucket_from_size(cache, i + 1);
		}
		status = LUB_HEAP_OK;
	} while (0);

	return status;
}

/*--------------------------------------------------------- */
lub_heap_cache_bucket_t
    *lub_heap_cache_find_bucket_from_address(lub_heap_cache_t * this,
					     const void *address)
{
	lub_heap_cache_bucket_t **bucket = (void *)address;

	/* get the bucket reference */
	--bucket;

	if ((*bucket > this->m_bucket_start[0])
	    || (*bucket < this->m_bucket_end[-1])) {
		bucket = 0;
	}
	return bucket ? *bucket : 0;
}

/*--------------------------------------------------------- */
lub_heap_cache_bucket_t *lub_heap_cache_find_bucket_from_size(lub_heap_cache_t *
							      this, size_t size)
{
	lub_heap_cache_bucket_t *bucket = 0;

	/* simply get the result from the fast lookup table */
	if (size > 0) {
		if (size <= this->m_max_block_size) {
			bucket = this->m_bucket_lookup[size - 1];
		} else {
			++this->m_misses;
		}
	}
	return bucket;
}

/*--------------------------------------------------------- */
lub_heap_status_t
lub_heap_cache_realloc(lub_heap_t * this, char **ptr, size_t size)
{
	lub_heap_status_t status = LUB_HEAP_FAILED;
	lub_heap_cache_bucket_t *old_bucket = 0;
	lub_heap_cache_bucket_t *new_bucket =
	    size ? lub_heap_cache_find_bucket_from_size(this->cache, size) : 0;
	char *new_ptr = 0;

	do {
		char *old_ptr = *ptr;
		if (old_ptr) {
			old_bucket =
			    lub_heap_cache_find_bucket_from_address(this->cache,
								    old_ptr);
		} else if (size == 0) {
			/* nothing to do */
			status = LUB_HEAP_OK;
			break;
		}
		if (old_bucket) {
	    /********************************
             * old from CACHE, new from CACHE
             ******************************** */
			if (new_bucket) {
				if (old_bucket == new_bucket) {
					/* keep the existing cache block which is big enough */
					new_ptr = old_ptr;
					status = LUB_HEAP_OK;
					break;
				}
				/* try and get memory from the cache */
				new_ptr =
				    lub_heap_cache_bucket_alloc(new_bucket);
				if (new_ptr) {
					if (old_ptr) {
						/* copy the old details across */
						memcpy(new_ptr, old_ptr, size);

						/* release the old cache block */
						status =
						    lub_heap_cache_bucket_free
						    (old_bucket, old_ptr);
						if (LUB_HEAP_OK != status) {
							break;
						}
					}
					/* all done */
					status = LUB_HEAP_OK;
					break;
				}
			}
	    /********************************
             * old from CACHE, new from HEAP
             ******************************** */
			if (size) {
				/* get new memory from the dynamic heap */
				status =
				    lub_heap_raw_realloc(this, &new_ptr, size,
							 LUB_HEAP_ALIGN_NATIVE);
				if (LUB_HEAP_OK != status) {
					break;
				}
				/* copy the old details across */
				memcpy(new_ptr, old_ptr, size);
			}
			/* release the old cache block */
			status =
			    lub_heap_cache_bucket_free(old_bucket, old_ptr);
		} else {
	    /********************************
             * old from HEAP, new from CACHE
             ******************************** */
			if (size) {
				if (new_bucket) {
					/* try and get memory from the cache */
					new_ptr =
					    lub_heap_cache_bucket_alloc
					    (new_bucket);
					if (new_ptr) {
						if (old_ptr) {
							/* copy the old details across */
							memcpy(new_ptr, old_ptr,
							       size);
							size = 0;
						} else {
							/* all done */
							status = LUB_HEAP_OK;
							break;
						}
					}
				}
			} else if (!old_ptr) {
				/* nothing to do */
				status = LUB_HEAP_OK;
				break;
			}
	    /********************************
             * old from HEAP, new from HEAP
             ******************************** */
			/* release old memory and potentially get new memory */
			status =
			    lub_heap_raw_realloc(this, &old_ptr, size,
						 LUB_HEAP_ALIGN_NATIVE);
			if (LUB_HEAP_OK != status) {
				break;
			} else if (size) {
				new_ptr = old_ptr;
			}
		}
	} while (0);

	if (LUB_HEAP_OK == status) {
		/* set up the new pointer value */
		*ptr = new_ptr;
	}
	return status;
}

/*--------------------------------------------------------- */
void lub_heap_cache_show(lub_heap_cache_t * this)
{
	lub_heap_cache_bucket_t **ptr;

	printf
	    ("       size num blocks    current  high-tide cumulative     misses\n");
	printf
	    (" ---------- ---------- ---------- ---------- ---------- ----------\n");
	for (ptr = this->m_bucket_start; ptr < this->m_bucket_end; ++ptr) {
		lub_blockpool_t *blockpool = &(*ptr)->m_blockpool;
		lub_blockpool_stats_t stats;

		lub_blockpool__get_stats(blockpool, &stats);

		printf(" %10" SIZE_FMT " %10" SIZE_FMT " %10" SIZE_FMT " %10"
		       SIZE_FMT " %10" SIZE_FMT " %10" SIZE_FMT "\n",
		       stats.block_size, stats.num_blocks, stats.alloc_blocks,
		       stats.alloc_hightide_blocks, stats.alloc_total_blocks,
		       stats.alloc_failures);
	}

	printf(" %10u %10s %10s %10s %10s %10" SIZE_FMT "\n",
	       this->m_max_block_size, "-", "-", "-", "-", this->m_misses);
}

/*--------------------------------------------------------- */
void
lub_heap_cache__get_stats(lub_heap_cache_t * this, lub_heap_stats_t * stats)
{
	lub_heap_cache_bucket_t **ptr;

	memset(stats, 0, sizeof(lub_heap_stats_t));
	stats->free_overhead =
	    lub_heap_cache_overhead_size(this->m_max_block_size,
					 this->m_num_max_blocks);

	for (ptr = this->m_bucket_start; ptr < this->m_bucket_end; ++ptr) {
		lub_blockpool_t *blockpool = &(*ptr)->m_blockpool;
		lub_blockpool_stats_t bucket_stats;
		size_t block_size;
		size_t block_overhead = sizeof(lub_heap_cache_bucket_t *);	/* used for fast lookup from address */

		lub_blockpool__get_stats(blockpool, &bucket_stats);
		block_size = (bucket_stats.block_size - block_overhead);

		stats->free_blocks += bucket_stats.free_blocks;
		stats->free_bytes += block_size * bucket_stats.free_blocks;
		stats->free_overhead +=
		    block_overhead * bucket_stats.free_blocks;

		stats->alloc_blocks += bucket_stats.alloc_blocks;
		stats->alloc_bytes += block_size * bucket_stats.alloc_blocks;
		stats->alloc_overhead +=
		    block_overhead * bucket_stats.alloc_blocks;

		stats->alloc_total_blocks += bucket_stats.alloc_total_blocks;
		stats->alloc_total_bytes +=
		    block_size * bucket_stats.alloc_total_blocks;
	}

}

/*--------------------------------------------------------- */