#include "db_config.h"
#include "db_int.h"
typedef struct __alloc_layout {
SH_TAILQ_HEAD(__addrq) addrq;
SH_TAILQ_HEAD(__sizeq) sizeq;
#ifdef HAVE_STATISTICS
u_int32_t success;
u_int32_t failure;
u_int32_t freed;
u_int32_t longest;
#ifdef __ALLOC_DISPLAY_ALLOCATION_SIZES
u_int32_t pow2_size[32];
#endif
#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;
void
__env_alloc_init(infop, size)
REGINFO *infop;
size_t size;
{
DB_ENV *dbenv;
ALLOC_ELEMENT *elp;
ALLOC_LAYOUT *head;
dbenv = infop->dbenv;
if (F_ISSET(dbenv, DB_ENV_PRIVATE))
return;
head = infop->addr;
SH_TAILQ_INIT(&head->addrq);
SH_TAILQ_INIT(&head->sizeq);
STAT((head->success = head->failure = head->freed = 0));
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, 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;
{
ALLOC_ELEMENT *elp, *frag, *elp_tmp;
ALLOC_LAYOUT *head;
DB_ENV *dbenv;
size_t total_len;
u_int8_t *p;
int ret;
#ifdef HAVE_STATISTICS
u_long st_search;
#endif
dbenv = infop->dbenv;
*(void **)retp = NULL;
if (F_ISSET(dbenv, DB_ENV_PRIVATE)) {
if (infop->allocated >= infop->max_alloc)
return (ENOMEM);
len += sizeof(size_t);
#ifdef DIAGNOSTIC
++len;
#endif
if ((ret = __os_malloc(dbenv, 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);
#ifdef __ALLOC_DISPLAY_ALLOCATION_SIZES
STAT((++head->pow2_size[__db_log2(len) - 1]));
#endif
#define SHALLOC_FRAGMENT (sizeof(ALLOC_ELEMENT) + 64)
elp = NULL;
STAT((st_search = 0));
SH_TAILQ_FOREACH(elp_tmp, &head->sizeq, sizeq, __alloc_element) {
STAT((++st_search));
if (elp_tmp->len < total_len)
break;
elp = elp_tmp;
if (elp->len - total_len <= SHALLOC_FRAGMENT)
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(&head->sizeq, 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);
SH_TAILQ_FOREACH(elp_tmp, &head->sizeq, sizeq, __alloc_element)
if (elp_tmp->len < frag->len)
break;
if (elp_tmp == NULL)
SH_TAILQ_INSERT_TAIL(&head->sizeq, frag, sizeq);
else
SH_TAILQ_INSERT_BEFORE(&head->sizeq,
elp_tmp, frag, sizeq, __alloc_element);
}
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;
DB_ENV *dbenv;
size_t len;
u_int8_t *p;
dbenv = infop->dbenv;
if (F_ISSET(dbenv, DB_ENV_PRIVATE)) {
p = (u_int8_t *)((size_t *)ptr - 1);
len = *(size_t *)p;
infop->allocated -= len;
#ifdef DIAGNOSTIC
DB_ASSERT(dbenv, p[len - 1] == GUARD_BYTE);
memset(p, CLEAR_BYTE, len);
#endif
__os_free(dbenv, p);
return;
}
head = infop->addr;
STAT((++head->freed));
p = ptr;
elp = (ALLOC_ELEMENT *)(p - sizeof(ALLOC_ELEMENT));
#ifdef DIAGNOSTIC
DB_ASSERT(dbenv, 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);
SH_TAILQ_REMOVE(&head->sizeq, 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);
SH_TAILQ_REMOVE(&head->sizeq, elp_tmp, sizeq, __alloc_element);
elp->len += elp_tmp->len;
}
SH_TAILQ_FOREACH(elp_tmp, &head->sizeq, sizeq, __alloc_element)
if (elp->len >= elp_tmp->len)
break;
if (elp_tmp == NULL)
SH_TAILQ_INSERT_TAIL(&head->sizeq, elp, sizeq);
else
SH_TAILQ_INSERT_BEFORE(&head->sizeq,
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;
DB_ENV *dbenv;
#ifdef __ALLOC_DISPLAY_ALLOCATION_SIZES
DB_MSGBUF mb;
int i;
#endif
dbenv = infop->dbenv;
head = infop->addr;
if (F_ISSET(dbenv, DB_ENV_PRIVATE))
return;
__db_msg(dbenv,
"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;
#ifdef __ALLOC_DISPLAY_ALLOCATION_SIZES
DB_MSGBUF_INIT(&mb);
for (i = 0; i < 32; ++i)
__db_msgadd(dbenv, &mb, "%s%2d/%lu",
i == 0 ? "Allocations by power-of-two sizes: " : ", ",
i + 1, (u_long)head->pow2_size[i]);
DB_MSGBUF_FLUSH(dbenv, &mb);
#endif
#ifdef __ALLOC_DISPLAY_ALLOCATION_LISTS
__db_msg(dbenv,
"Allocation list by address: {chunk length, user length}");
SH_TAILQ_FOREACH(elp, &head->addrq, addrq, __alloc_element)
__db_msg(dbenv, "\t%#lx {%lu, %lu}",
P_TO_ULONG(elp), (u_long)elp->len, (u_long)elp->ulen);
__db_msg(dbenv, "Allocation free list by size: {chunk length}");
SH_TAILQ_FOREACH(elp, &head->sizeq, sizeq, __alloc_element)
__db_msg(dbenv, "\t%#lx {%lu}",
P_TO_ULONG(elp), (u_long)elp->len);
#endif
return;
}
#endif