#include "db_config.h"
#include "db_int.h"
typedef SH_TAILQ_HEAD(__sizeq) SIZEQ_HEAD;
typedef struct __alloc_layout {
SH_TAILQ_HEAD(__addrq) addrq;
#define DB_SIZE_Q_COUNT 11
SIZEQ_HEAD sizeq[DB_SIZE_Q_COUNT];
#ifdef HAVE_STATISTICS
u_int32_t pow2_size[DB_SIZE_Q_COUNT];
#endif
#ifdef HAVE_STATISTICS
u_int32_t success;
u_int32_t failure;
u_int32_t freed;
u_int32_t longest;
#endif
uintmax_t unused;
} ALLOC_LAYOUT;
typedef struct __alloc_element {
SH_TAILQ_ENTRY addrq;
SH_TAILQ_ENTRY sizeq;
size_t len;
uintmax_t ulen;
} ALLOC_ELEMENT;
#define SHALLOC_FRAGMENT (sizeof(ALLOC_ELEMENT) + 64)
#undef SET_QUEUE_FOR_SIZE
#define SET_QUEUE_FOR_SIZE(head, q, i, len) do { \
for (i = 0; i < DB_SIZE_Q_COUNT; ++i) { \
q = &(head)->sizeq[i]; \
if ((len) <= (size_t)1024 << i) \
break; \
} \
} while (0)
static void __env_size_insert __P((ALLOC_LAYOUT *, ALLOC_ELEMENT *));
void
__env_alloc_init(infop, size)
REGINFO *infop;
size_t size;
{
ALLOC_ELEMENT *elp;
ALLOC_LAYOUT *head;
ENV *env;
u_int i;
env = infop->env;
if (F_ISSET(env, ENV_PRIVATE))
return;
head = infop->addr;
memset(head, 0, sizeof(*head));
SH_TAILQ_INIT(&head->addrq);
for (i = 0; i < DB_SIZE_Q_COUNT; ++i)
SH_TAILQ_INIT(&head->sizeq[i]);
COMPQUIET(head->unused, 0);
elp = (ALLOC_ELEMENT *)((u_int8_t *)head + sizeof(ALLOC_LAYOUT));
elp->len = size - sizeof(ALLOC_LAYOUT);
elp->ulen = 0;
SH_TAILQ_INSERT_HEAD(&head->addrq, elp, addrq, __alloc_element);
SH_TAILQ_INSERT_HEAD(
&head->sizeq[DB_SIZE_Q_COUNT - 1], elp, sizeq, __alloc_element);
}
#ifdef DIAGNOSTIC
#define DB_ALLOC_SIZE(len) \
(size_t)DB_ALIGN((len) + sizeof(ALLOC_ELEMENT) + 1, sizeof(uintmax_t))
#else
#define DB_ALLOC_SIZE(len) \
(size_t)DB_ALIGN((len) + sizeof(ALLOC_ELEMENT), sizeof(uintmax_t))
#endif
size_t
__env_alloc_overhead()
{
return (sizeof(ALLOC_ELEMENT));
}
size_t
__env_alloc_size(len)
size_t len;
{
return (DB_ALLOC_SIZE(len));
}
int
__env_alloc(infop, len, retp)
REGINFO *infop;
size_t len;
void *retp;
{
SIZEQ_HEAD *q;
ALLOC_ELEMENT *elp, *frag, *elp_tmp;
ALLOC_LAYOUT *head;
ENV *env;
size_t total_len;
u_int8_t *p;
u_int i;
int ret;
#ifdef HAVE_STATISTICS
u_int32_t st_search;
#endif
env = infop->env;
*(void **)retp = NULL;
if (F_ISSET(env, ENV_PRIVATE)) {
if (infop->allocated >= infop->max_alloc)
return (ENOMEM);
len += sizeof(size_t);
#ifdef DIAGNOSTIC
++len;
#endif
if ((ret = __os_malloc(env, len, &p)) != 0)
return (ret);
infop->allocated += len;
*(size_t *)p = len;
#ifdef DIAGNOSTIC
p[len - 1] = GUARD_BYTE;
#endif
*(void **)retp = p + sizeof(size_t);
return (0);
}
head = infop->addr;
total_len = DB_ALLOC_SIZE(len);
SET_QUEUE_FOR_SIZE(head, q, i, total_len);
#ifdef HAVE_STATISTICS
++head->pow2_size[i];
#endif
STAT((st_search = 0));
for (elp = NULL;; ++q) {
SH_TAILQ_FOREACH(elp_tmp, q, sizeq, __alloc_element) {
STAT((++st_search));
if (elp_tmp->len < total_len)
break;
elp = elp_tmp;
if (elp_tmp->len - total_len <= SHALLOC_FRAGMENT)
break;
}
if (elp != NULL || ++i >= DB_SIZE_Q_COUNT)
break;
}
#ifdef HAVE_STATISTICS
if (head->longest < st_search)
head->longest = st_search;
#endif
if (elp == NULL) {
STAT((++head->failure));
return (ENOMEM);
}
STAT((++head->success));
SH_TAILQ_REMOVE(q, elp, sizeq, __alloc_element);
if (elp->len - total_len > SHALLOC_FRAGMENT) {
frag = (ALLOC_ELEMENT *)((u_int8_t *)elp + total_len);
frag->len = elp->len - total_len;
frag->ulen = 0;
elp->len = total_len;
SH_TAILQ_INSERT_AFTER(
&head->addrq, elp, frag, addrq, __alloc_element);
__env_size_insert(head, frag);
}
p = (u_int8_t *)elp + sizeof(ALLOC_ELEMENT);
elp->ulen = len;
#ifdef DIAGNOSTIC
p[len] = GUARD_BYTE;
#endif
*(void **)retp = p;
return (0);
}
void
__env_alloc_free(infop, ptr)
REGINFO *infop;
void *ptr;
{
ALLOC_ELEMENT *elp, *elp_tmp;
ALLOC_LAYOUT *head;
ENV *env;
SIZEQ_HEAD *q;
size_t len;
u_int8_t i, *p;
env = infop->env;
if (F_ISSET(env, ENV_PRIVATE)) {
p = (u_int8_t *)((size_t *)ptr - 1);
len = *(size_t *)p;
infop->allocated -= len;
#ifdef DIAGNOSTIC
DB_ASSERT(env, p[len - 1] == GUARD_BYTE);
memset(p, CLEAR_BYTE, len);
#endif
__os_free(env, p);
return;
}
head = infop->addr;
STAT((++head->freed));
p = ptr;
elp = (ALLOC_ELEMENT *)(p - sizeof(ALLOC_ELEMENT));
#ifdef DIAGNOSTIC
DB_ASSERT(env, p[elp->ulen] == GUARD_BYTE);
memset(p, CLEAR_BYTE, elp->len - sizeof(ALLOC_ELEMENT));
#endif
elp->ulen = 0;
if ((elp_tmp =
SH_TAILQ_PREV(&head->addrq, elp, addrq, __alloc_element)) != NULL &&
elp_tmp->ulen == 0 &&
(u_int8_t *)elp_tmp + elp_tmp->len == (u_int8_t *)elp) {
SH_TAILQ_REMOVE(&head->addrq, elp, addrq, __alloc_element);
SET_QUEUE_FOR_SIZE(head, q, i, elp_tmp->len);
SH_TAILQ_REMOVE(q, elp_tmp, sizeq, __alloc_element);
elp_tmp->len += elp->len;
elp = elp_tmp;
}
if ((elp_tmp = SH_TAILQ_NEXT(elp, addrq, __alloc_element)) != NULL &&
elp_tmp->ulen == 0 &&
(u_int8_t *)elp + elp->len == (u_int8_t *)elp_tmp) {
SH_TAILQ_REMOVE(&head->addrq, elp_tmp, addrq, __alloc_element);
SET_QUEUE_FOR_SIZE(head, q, i, elp_tmp->len);
SH_TAILQ_REMOVE(q, elp_tmp, sizeq, __alloc_element);
elp->len += elp_tmp->len;
}
__env_size_insert(head, elp);
}
static void
__env_size_insert(head, elp)
ALLOC_LAYOUT *head;
ALLOC_ELEMENT *elp;
{
SIZEQ_HEAD *q;
ALLOC_ELEMENT *elp_tmp;
u_int i;
SET_QUEUE_FOR_SIZE(head, q, i, elp->len);
SH_TAILQ_FOREACH(elp_tmp, q, sizeq, __alloc_element)
if (elp->len <= elp_tmp->len)
break;
if (elp_tmp == NULL)
SH_TAILQ_INSERT_TAIL(q, elp, sizeq);
else
SH_TAILQ_INSERT_BEFORE(q, elp_tmp, elp, sizeq, __alloc_element);
}
#ifdef HAVE_STATISTICS
void
__env_alloc_print(infop, flags)
REGINFO *infop;
u_int32_t flags;
{
#ifdef __ALLOC_DISPLAY_ALLOCATION_LISTS
ALLOC_ELEMENT *elp;
#endif
ALLOC_LAYOUT *head;
ENV *env;
u_int i;
env = infop->env;
head = infop->addr;
if (F_ISSET(env, ENV_PRIVATE))
return;
__db_msg(env,
"Region allocations: %lu allocations, %lu failures, %lu frees, %lu longest",
(u_long)head->success, (u_long)head->failure, (u_long)head->freed,
(u_long)head->longest);
if (!LF_ISSET(DB_STAT_ALL))
return;
__db_msg(env, "%s", "Allocations by power-of-two sizes:");
for (i = 0; i < DB_SIZE_Q_COUNT; ++i)
__db_msg(env, "%3dKB\t%lu",
(1024 << i) / 1024, (u_long)head->pow2_size[i]);
#ifdef __ALLOC_DISPLAY_ALLOCATION_LISTS
__db_msg(env,
"Allocation list by address: {chunk length, user length}");
SH_TAILQ_FOREACH(elp, &head->addrq, addrq, __alloc_element)
__db_msg(env, "\t%#lx {%lu, %lu}",
P_TO_ULONG(elp), (u_long)elp->len, (u_long)elp->ulen);
__db_msg(env, "Allocation free list by size: KB {chunk length}");
for (i = 0; i < DB_SIZE_Q_COUNT; ++i) {
__db_msg(env, "%3dKB", (1024 << i) / 1024);
SH_TAILQ_FOREACH(elp, &head->sizeq[i], sizeq, __alloc_element)
__db_msg(env,
"\t%#lx {%lu}", P_TO_ULONG(elp), (u_long)elp->len);
}
#endif
}
#endif