File area_alloc.c¶
File List > base > area_alloc.c
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* area_alloc.c - Area memory manager
*
* Note:
* Allocation areas provide a way to block allocate structures and maintain
* a free list. Useful for small structures that are used frequently.
* Used for allocation and freeing of many small objects of the same size.
*
* These areas are NOT allocated within the "workspace" memory so that
* they can be used for structures that need to serve as roots to the
* garbage collector.
*/
#ident "$Id$"
#include "config.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "area_alloc.h"
#include "set_object.h"
#if !defined (SERVER_MODE)
#include "work_space.h"
#endif /* !defined (SERVER_MODE) */
// XXX: SHOULD BE THE LAST INCLUDE HEADER
#include "memory_wrapper.hpp"
#if !defined (SERVER_MODE)
#define pthread_mutex_init(a, b)
#define pthread_mutex_destroy(a)
#define pthread_mutex_lock(a) 0
#define pthread_mutex_unlock(a)
#endif
#if !defined (NDEBUG)
/* The size of the prefix containing allocation status, if we're
on a machine that requires double allignment of structures, we
may have to make this sizeof(double) */
#define AREA_PREFIX_SIZE sizeof(double)
enum
{
AREA_PREFIX_INITED = 0,
AREA_PREFIX_FREED = 0x01010101
};
#endif /* !NDEBUG */
/*
* Area_list - Global list of areas
*/
static AREA *area_List = NULL;
#if defined (SERVER_MODE)
pthread_mutex_t area_List_lock = PTHREAD_MUTEX_INITIALIZER;
#endif
#if defined (SERVER_MODE)
#define LF_AREA_BITMAP_USAGE_RATIO LF_BITMAP_95PERCENTILE_USAGE_RATIO
#else
#define LF_AREA_BITMAP_USAGE_RATIO LF_BITMAP_FULL_USAGE_RATIO
#endif
/*
* Volatile access to a variable
*/
#define VOLATILE_ACCESS(v,t) (*((t volatile *) &(v)))
static void area_info (AREA * area, FILE * fp);
static AREA_BLOCK *area_alloc_block (AREA * area);
static AREA_BLOCKSET_LIST *area_alloc_blockset (AREA * area);
static int area_insert_block (AREA * area, AREA_BLOCK * new_block);
static AREA_BLOCK *area_find_block (AREA * area, const void *ptr);
/*
* area_init - Initialize the area manager
* return: none
*
* Note: Will be called during system startup
*/
void
area_init (void)
{
#define ER_AREA_ALREADY_STARTED ER_GENERIC_ERROR
if (area_List != NULL)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_AREA_ALREADY_STARTED, 0);
return;
}
area_List = NULL;
}
/*
* area_final - Shut down the area manager
* return: none
*
* Note: Will be called during system shutdown
*/
void
area_final (void)
{
AREA *area, *next;
for (area = area_List, next = NULL; area != NULL; area = next)
{
next = area->next;
area_flush (area);
free_and_init (area);
}
area_List = NULL;
set_area_reset ();
pthread_mutex_destroy (&area_List_lock);
}
/*
* area_create - Build a new area and add it to the global list
* return: created AREA or NULL if fail
* name(in):
* element_size(in):
* alloc_count(in):
*
* Note:
*/
AREA *
area_create (const char *name, size_t element_size, size_t alloc_count)
{
AREA *area;
size_t adjust;
int rv;
area = (AREA *) malloc (sizeof (AREA));
if (area == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (AREA));
return NULL;
}
area->blockset_list = NULL;
if (name == NULL)
{
area->name = NULL;
}
else
{
area->name = strdup (name);
if (area->name == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, (size_t) (strlen (name) + 1));
goto error;
}
}
#if !defined (NDEBUG)
/* Reserve space for memory checking */
element_size += AREA_PREFIX_SIZE;
#endif /* !NDEBUG */
/* always make sure element size is a double word multiple */
adjust = element_size % 8;
if (adjust)
{
element_size += 8 - adjust;
}
area->element_size = element_size;
/* adjust alloc count for lf_bitmap */
area->alloc_count = LF_BITMAP_COUNT_ALIGN (alloc_count);
area->block_size = area->element_size * area->alloc_count;
area->n_allocs = 0;
area->n_frees = 0;
#if defined (SERVER_MODE)
area->failure_function = NULL;
#else
area->failure_function = ws_abort_transaction;
#endif
area->blockset_list = area_alloc_blockset (area);
if (area->blockset_list == NULL)
{
goto error;
}
area->hint_block = area_alloc_block (area);
if (area->hint_block == NULL)
{
goto error;
}
area->blockset_list->items[0] = area->hint_block;
area->blockset_list->used_count++;
pthread_mutex_init (&area->area_mutex, NULL);
rv = pthread_mutex_lock (&area_List_lock);
area->next = area_List;
area_List = area;
pthread_mutex_unlock (&area_List_lock);
return area;
error:
if (area->name)
{
free_and_init (area->name);
}
if (area->blockset_list != NULL)
{
free_and_init (area->blockset_list);
}
free_and_init (area);
return NULL;
}
/*
* area_destroy - Removes an area
* return: none
* area(in): AREA tp destroy
*/
void
area_destroy (AREA * area)
{
AREA *a, *prev;
int rv;
assert (area != NULL);
rv = pthread_mutex_lock (&area_List_lock);
for (prev = NULL, a = area_List; a != NULL && a != area; a = a->next)
{
prev = a;
}
if (a != NULL)
{
if (prev == NULL)
{
area_List = a->next;
}
else
{
prev->next = a->next;
}
}
pthread_mutex_unlock (&area_List_lock);
area_flush (area);
free_and_init (area);
}
/*
* area_alloc_block - Allocate a new block for an area
* return: the address of area block, if error, return NULL.
* area(in): AREA
* thrd_index(in): thread index
*
* Note: this is called by area_alloc, and lock is also held by area_alloc
*/
static AREA_BLOCK *
area_alloc_block (AREA * area)
{
AREA_BLOCK *new_block;
size_t total;
assert (area != NULL);
total = area->block_size + sizeof (AREA_BLOCK);
new_block = (AREA_BLOCK *) malloc (total);
if (new_block == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, total);
if (area->failure_function != NULL)
{
(*(area->failure_function)) ();
}
return NULL;
}
new_block->bitmap.init (LF_BITMAP_LIST_OF_CHUNKS, (int) area->alloc_count, LF_AREA_BITMAP_USAGE_RATIO);
assert ((int) area->alloc_count == new_block->bitmap.entry_count);
new_block->data = ((char *) new_block) + sizeof (AREA_BLOCK);
return new_block;
}
/*
* area_alloc_blockset - Allocate a new blockset node
* return: the address of area blockset, if error, return NULL.
* area(in): AREA
*
*/
static AREA_BLOCKSET_LIST *
area_alloc_blockset (AREA * area)
{
AREA_BLOCKSET_LIST *new_blockset;
new_blockset = (AREA_BLOCKSET_LIST *) malloc (sizeof (AREA_BLOCKSET_LIST));
if (new_blockset == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (AREA_BLOCKSET_LIST));
if (area->failure_function != NULL)
{
(*(area->failure_function)) ();
}
return NULL;
}
new_blockset->next = NULL;
new_blockset->used_count = 0;
memset ((void *) new_blockset->items, 0, sizeof (sizeof (AREA_BLOCK *) * AREA_BLOCKSET_SIZE));
return new_blockset;
}
/*
* area_alloc - Allocate a new element from an area
* return: pointer to the element allocated
* area(in):
*
* Note: The element will be taken from the area's free list,
* otherwise a new block will be allocated and the element
* taken from there
*/
void *
area_alloc (AREA * area)
{
AREA_BLOCKSET_LIST *blockset;
AREA_BLOCK *block, *hint_block;
int used_count, i, entry_idx;
char *entry_ptr;
int rv;
#if !defined (NDEBUG)
int *prefix;
#endif /* !NDEBUG */
assert (area != NULL);
/* Step 1: find a free entry from the hint block */
hint_block = VOLATILE_ACCESS (area->hint_block, AREA_BLOCK *);
entry_idx = hint_block->bitmap.get_entry ();
if (entry_idx != -1)
{
block = hint_block;
goto found;
}
/* Step 2: if not found, find a free entry from the blockset lists */
for (blockset = area->blockset_list; blockset != NULL;
blockset = VOLATILE_ACCESS (blockset->next, AREA_BLOCKSET_LIST *))
{
used_count = VOLATILE_ACCESS (blockset->used_count, int);
for (i = 0; i < used_count; i++)
{
block = VOLATILE_ACCESS (blockset->items[i], AREA_BLOCK *);
entry_idx = block->bitmap.get_entry ();
if (entry_idx != -1)
{
/* change the hint block */
hint_block = VOLATILE_ACCESS (area->hint_block, AREA_BLOCK *);
if (LF_BITMAP_IS_FULL (&hint_block->bitmap) && !LF_BITMAP_IS_FULL (&block->bitmap))
{
ATOMIC_CAS_ADDR (&area->hint_block, hint_block, block);
}
goto found;
}
}
}
/* Step 3: if not found, add a new block. Then find free entry in this new block.
* Only one thread is allowed to add a new block at a moment.
*/
rv = pthread_mutex_lock (&area->area_mutex);
if (area->hint_block != hint_block)
{
/* someone may change the hint block */
block = area->hint_block;
entry_idx = block->bitmap.get_entry ();
if (entry_idx != -1)
{
pthread_mutex_unlock (&area->area_mutex);
goto found;
}
}
block = area_alloc_block (area);
if (block == NULL)
{
pthread_mutex_unlock (&area->area_mutex);
/* error has been set */
return NULL;
}
/* alloc free entry from this new block */
entry_idx = block->bitmap.get_entry ();
assert (entry_idx != -1);
if (area_insert_block (area, block) != NO_ERROR)
{
block->bitmap.destroy ();
free_and_init (block);
pthread_mutex_unlock (&area->area_mutex);
/* error has been set */
return NULL;
}
/* always set new block as hint_block */
area->hint_block = block;
pthread_mutex_unlock (&area->area_mutex);
found:
#if defined(SERVER_MODE)
/* do not count in SERVER_MODE */
/* ATOMIC_INC_32 (&area->n_allocs, 1); */
#else
area->n_allocs++;
#endif
entry_ptr = block->data + area->element_size * entry_idx;
#if !defined (NDEBUG)
prefix = (int *) entry_ptr;
*prefix = AREA_PREFIX_INITED;
entry_ptr += AREA_PREFIX_SIZE;
#endif /* !NDEBUG */
assert (entry_ptr < (block->data + area->block_size));
return ((void *) entry_ptr);
}
/*
* area_validate - validate that a pointer is within range in an area
* return: NO_ERROR if ok (address in range) or ER_AREA_ILLEGAL_POINTER
* area(in): AREA
* address(in): pointer to check
*
* Note: ER_AREA_ILLEGAL_POINTER will be set if fails.
* This does not guarentee that the pointer is alligned
* correctly to the start of an element, only that it points into one
* of the area blocks.
*/
int
area_validate (AREA * area, const void *address)
{
AREA_BLOCK *p;
int error = NO_ERROR;
assert (area != NULL);
p = area_find_block (area, address);
if (p == NULL)
{
/* need more specific error here */
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_ILLEGAL_POINTER, 0);
error = ER_AREA_ILLEGAL_POINTER;
}
return error;
}
/*
* area_free - Free an element in an area
* return: error code
* area(in): AREA
* ptr(in): pointer to the element
*
* Note: Validation is performed; the element is simply pushed on the free list
*/
int
area_free (AREA * area, void *ptr)
{
AREA_BLOCK *block, *hint_block;
char *entry_ptr;
int entry_idx;
int offset = -1;
#if !defined (NDEBUG)
int *prefix;
#endif /* !NDEBUG */
assert (area != NULL);
if (ptr == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_ILLEGAL_POINTER, 0);
assert (ptr != NULL);
return ER_AREA_ILLEGAL_POINTER;
}
#if !defined (NDEBUG)
entry_ptr = ((char *) ptr) - AREA_PREFIX_SIZE;
#else
entry_ptr = (char *) ptr;
#endif /* !NDEBUG */
block = area_find_block (area, (const void *) entry_ptr);
if (block == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_ILLEGAL_POINTER, 0);
assert (false);
return ER_AREA_ILLEGAL_POINTER;
}
offset = (int) (entry_ptr - block->data);
if (offset < 0 || offset % area->element_size != 0)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_ILLEGAL_POINTER, 0);
assert (false);
return ER_AREA_ILLEGAL_POINTER;
}
#if !defined (NDEBUG)
prefix = (int *) entry_ptr;
if ((*prefix) != AREA_PREFIX_INITED)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_FREE_TWICE, 0);
assert ((*prefix) == AREA_PREFIX_INITED);
return ER_AREA_FREE_TWICE;
}
*prefix = AREA_PREFIX_FREED;
#endif /* !NDEBUG */
entry_idx = offset / (int) area->element_size;
assert (entry_idx >= 0 && entry_idx < (int) area->alloc_count);
block->bitmap.free_entry (entry_idx);
/* change hint block if needed */
hint_block = VOLATILE_ACCESS (area->hint_block, AREA_BLOCK *);
if (LF_BITMAP_IS_FULL (&hint_block->bitmap) && !LF_BITMAP_IS_FULL (&block->bitmap))
{
ATOMIC_CAS_ADDR (&area->hint_block, hint_block, block);
}
#if defined(SERVER_MODE)
/* do not count in SERVER_MODE */
/* ATOMIC_INC_32 (&area->n_frees, 1); */
#else
area->n_frees++;
#endif
return NO_ERROR;
}
/*
* area_flush - Free all storage allocated for an area
* return: none
* area(in): AREA to free
*
* Note: Normally called as part of final
*/
void
area_flush (AREA * area)
{
AREA_BLOCKSET_LIST *blockset, *next_blockset;
AREA_BLOCK *block;
int i;
assert (area != NULL);
for (blockset = area->blockset_list; blockset != NULL; blockset = next_blockset)
{
next_blockset = blockset->next;
for (i = 0; i < blockset->used_count; i++)
{
block = blockset->items[i];
block->bitmap.destroy ();
free_and_init (block);
blockset->items[i] = NULL;
}
free_and_init (blockset);
}
area->blockset_list = NULL;
pthread_mutex_destroy (&area->area_mutex);
if (area->name != NULL)
{
free_and_init (area->name);
}
}
/*
* area_add_block --- insert block into the blockset list
* return: none
* area(in): area descriptor
* new_block(in): the new area_block pointer
*
* Note: This function is protected by area_mutex, which mean only
* 1 thread can insert block in the same time.
*/
static int
area_insert_block (AREA * area, AREA_BLOCK * new_block)
{
AREA_BLOCKSET_LIST **last_blockset_p;
AREA_BLOCKSET_LIST *blockset, *new_blockset;
int used_count;
assert (area != NULL && new_block != NULL);
last_blockset_p = &area->blockset_list;
/* find an available blockset and insert new_block into it */
for (blockset = area->blockset_list; blockset != NULL; blockset = blockset->next)
{
last_blockset_p = &blockset->next;
used_count = blockset->used_count;
if (used_count == AREA_BLOCKSET_SIZE)
{
/* no room */
continue;
}
/* each blockset owns one block at least */
assert (used_count >= 1);
/* If it fits, insert new_block to the last slot of this blockset. We don't shift/re-sort the blockset to manage
* sorted order. Our policy may require more space but greatly reduces the complexity of logic. */
if (blockset->items[used_count - 1] < new_block)
{
blockset->items[used_count] = new_block;
/* Use full barrier to ensure that above assignment done before increase used_count */
ATOMIC_INC_32 (&blockset->used_count, 1);
return NO_ERROR;
}
}
/* If there's no available blockset, we need to allocate a new blockset */
new_blockset = area_alloc_blockset (area);
if (new_blockset == NULL)
{
assert (er_errid () != NO_ERROR);
return er_errid ();
}
/* insert new_block to the first slot */
new_blockset->items[0] = new_block;
/* Use full barrier to ensure that above assignment done before increase used_count */
ATOMIC_INC_32 (&new_blockset->used_count, 1);
/* append the new blockset to the end of blockset list */
assert ((*last_blockset_p) == NULL);
*last_blockset_p = new_blockset;
return NO_ERROR;
}
/*
* area_find_block -- find related block in blockset list.
*
* return: the related block pointer, if not found, return NULL
* area(in): area descriptor
* ptr(in): the entry pointer
*
* Note: This function does not require area_mutex.
*/
static AREA_BLOCK *
area_find_block (AREA * area, const void *ptr)
{
AREA_BLOCKSET_LIST *blockset;
AREA_BLOCK *first_block, *last_block, *block;
int middle, left, right, pos;
int used_count;
/* find the related block in blockset list */
for (blockset = area->blockset_list; blockset != NULL;
blockset = VOLATILE_ACCESS (blockset->next, AREA_BLOCKSET_LIST *))
{
used_count = VOLATILE_ACCESS (blockset->used_count, int);
/* each blocskset owns one block at least */
assert (used_count >= 1);
first_block = blockset->items[0];
if ((char *) ptr < first_block->data)
{
continue; /* less than min address */
}
last_block = VOLATILE_ACCESS (blockset->items[used_count - 1], AREA_BLOCK *);
if (last_block->data + area->block_size <= (char *) ptr)
{
continue; /* large than max address */
}
assert ((first_block->data <= (char *) ptr) && ((char *) ptr < last_block->data + area->block_size));
left = 0;
right = used_count - 1;
/* binary search in this blockset */
while (left <= right)
{
middle = (left + right) / 2;
block = VOLATILE_ACCESS (blockset->items[middle], AREA_BLOCK *);
if (block->data > (char *) ptr)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
pos = right;
if (pos < 0 || pos >= AREA_BLOCKSET_SIZE)
{
/* impossible to here */
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_AREA_ILLEGAL_POINTER, 0);
assert (false);
return NULL;
}
block = VOLATILE_ACCESS (blockset->items[pos], AREA_BLOCK *);
if ((block->data <= (char *) ptr) && ((char *) ptr < block->data + area->block_size))
{
return block;
}
}
/* not found */
return NULL;
}
/*
* area_info - Display information about an area
* return: none
* area(in): area descriptor
* fp(in):
*/
static void
area_info (AREA * area, FILE * fp)
{
AREA_BLOCKSET_LIST *blockset;
AREA_BLOCK *block;
size_t nblocksets, nblocks, bytes, elements, used, unused;
size_t min_blocks_in_set, avg_blocks_in_set, max_blocks_in_set;
size_t nallocs = 0, nfrees = 0;
int i;
assert (area != NULL && fp != NULL);
nblocksets = nblocks = bytes = elements = used = unused = 0;
min_blocks_in_set = AREA_BLOCKSET_SIZE;
max_blocks_in_set = 0;
for (blockset = area->blockset_list; blockset != NULL; blockset = blockset->next)
{
nblocksets++;
for (i = 0; i < blockset->used_count; i++)
{
block = blockset->items[i];
nblocks++;
used += block->bitmap.entry_count_in_use;
bytes += area->block_size + sizeof (AREA_BLOCK);
}
if ((size_t) blockset->used_count < min_blocks_in_set)
{
min_blocks_in_set = blockset->used_count;
}
if ((size_t) blockset->used_count > max_blocks_in_set)
{
max_blocks_in_set = blockset->used_count;
}
}
avg_blocks_in_set = nblocks / nblocksets;
elements = (nblocks * area->alloc_count);
unused = elements - used;
nallocs = area->n_allocs;
nfrees = area->n_frees;
fprintf (fp, "Area: %s\n", area->name);
#if !defined (NDEBUG)
fprintf (fp, " %lld bytes/element ", (long long) area->element_size - AREA_PREFIX_SIZE);
fprintf (fp, "(plus %d bytes overhead), ", (int) AREA_PREFIX_SIZE);
#else
fprintf (fp, " %lld bytes/element, ", (long long) area->element_size);
#endif
fprintf (fp, "%lld elements/block, %lld blocks/blockset\n", (long long) area->alloc_count,
(long long) AREA_BLOCKSET_SIZE);
fprintf (fp, " %lld blocksets, usage stats:" " MIN %lld, AVG %lld, MAX %lld\n", (long long) nblocksets,
(long long) min_blocks_in_set, (long long) avg_blocks_in_set, (long long) max_blocks_in_set);
fprintf (fp, " %lld blocks, %lld bytes, %lld elements," " %lld unused, %lld in use\n", (long long) nblocks,
(long long) bytes, (long long) elements, (long long) unused, (long long) used);
fprintf (fp, " %lld total allocs, %lld total frees\n", (long long) nallocs, (long long) nfrees);
}
/*
* area_dump - Print descriptions of all areas.
* return: none
* fp(in):
*/
void
area_dump (FILE * fp)
{
AREA *area;
int rv;
if (fp == NULL)
{
fp = stdout;
}
rv = pthread_mutex_lock (&area_List_lock);
for (area = area_List; area != NULL; area = area->next)
{
area_info (area, fp);
}
pthread_mutex_unlock (&area_List_lock);
}