ossp-pkg/act/act_grid.c
/*
** OSSP act - Abstract Container Types
** Copyright (c) 1999-2003 Ralf S. Engelschall <rse@engelschall.com>
** Copyright (c) 1999-2003 The OSSP Project <http://www.ossp.org/>
**
** This file is part of OSSP act, an abstract container type library
** which can be found at http://www.ossp.org/pkg/lib/act/.
**
** Permission to use, copy, modify, and distribute this software for
** any purpose with or without fee is hereby granted, provided that
** the above copyright notice and this permission notice appear in all
** copies.
**
** THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
** IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
** USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
** ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
** OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
** SUCH DAMAGE.
**
** act_grid.c: memory grid (implementation)
*/
/*
* This is a special-case memory management library dedicated to the
* speed- and memory-optimized allocation and deallocation of fixed
* size objects. Inside OSSP act we have lots of those objects and
* if we would manage them directly through malloc(3) it would be to
* run-time expensive and waste too much total memory.
*
* It works by collecting together larger segments (act_grid_seg_t) of
* those fixed size objects (act_grid_tile_t) and linking them into
* a top-level grid structure (act_grid_t). The number of tiles in a
* segment grows with the Fibonacci numbers f(n) = f(n-1)+f(n-2) in
* order to dynamically scale better to the allocation requests without
* having to waste too much memory (in contrast to the usual "double to
* twice of size" approach). Inside a grid segment, the tiles are just
* arranged as a linar array after a linkage structure. The free tiles
* are remembered in a single linked list. So the grid in memory looks
* like this:
*
* -----BEGIN EMBEDDED OBJECT-----
* Content-type: application/fig
* Description: grid memory allocator memory architecture
* Version: eo/1.0
* H4sIAFxTSDwCA61aTW/cNhA9R79CQM82+DUUdS7QIkBuvfYSJAvXQLIoYv9/VOKI
* b0itg/i5RhD6rcX5nqFm6P3tj49/zvE+TJ8+X78+ffn872X6/XJ9vvyYPl6//HN5
* mj5dnrdP8zx55+6dm/56vD58u0x3YfLBuTlMefbiZu+2ZdlB2TaFOcwb3P6HdZb6
* 0807+bZu/5a6yvRBSXc+ywA2HvoIIIxcyyzuF1yhEEDomGHPxtUfXBdleuc7pvuH
* XdDGNbqDtAI185WkqUlNwpLmJjXTUquJsVkfhSWVFg6hpeYmNQsRt+rYXeEkPZDm
* c4DIcM3uZAs000cA4lhdc1MRoHT5gT1k5t7am8WZX9ue6S5vxbe6I8Xrbq76VmfF
* MKBd+XUAVP2ddDIUOnbYRaSWQ/U6upCUzhaOOEJypCWvIBPHFuKKmIhjK3HtUodO
* RNdKsLPaEuQUXKoeO1eclgyZhqiiVG0ydDVU+qSxfWROv2T7LgOebru0NlX+viuE
* fUmULSNxh06mZfpNpj6AXw69Xku8QvIqLHHwTXJFpGRkhfqBe6OhEJRYeMkZkrlS
* KiigVQaEs7ZDVCmpOwejTMPjqSGhOjMkmCUdsvjgmvpEZB0iN6fTsRQ3oDcEqkDr
* whOviPJK55cmdTgQSxz6hXUndO9QcbcLl7orPOJdj04fsY/U+iU2CFyPvGOrYvRm
* l7o4eGyfntYRY0PcG8St8XLtt3W7/fbVRXQiHtnoU0PcYRhjM6OiQ6/XEidok4Qm
* zpCcecnVUmlO3hFLvMCdCy+5QHKhJpPq7ap2kgEtLQIdEop1dmejTMPjqaHF0VoX
* 6AqkSdfyxvYRrP3PjK9CzNdt315jHHcrxQ6FVi0d4qZ4G+Mj3YFEDPKoILJulDjz
* kjHMR36ajzZW8vN8xOAZ3zDRY6SPmOmjDfU25fJjfcRcD6NMw+OpIaGPbY3UMiA9
* 9fyAuN6nM9mCYh7GtI99bKAKtC488Yoor/y57OElz5/LAedy4PMrI6sMFWSVIS51
* EzySXY/U0CQ94nofPXleYKNuiG5AVO+jGg7e7FN3fHVb76P9UMILgepyTsQjm/MD
* cl4UtG1CNyr1paTEC92o1LeXEhde8qAx2eWMGpNdzqgx+VJXb0t7s3fo9FGE7XLU
* nYNRpuHNQnU5qg34nyUNUWAdkn5m/Jgd2Ed1OTo/u6Zfh0JL3A5RXU5VUomFv6RZ
* IHnhK7ZAcuElJ7QLjr4qVWJpgedennaXocSZrhu9mFrcgKRFoEORrpvRKNPweGpI
* 6GO7/UGrR3ae28J1OZ3JCEp3byQyoDcEqkDrwhOviPLKn8seXvL8uRxwFgU+vzKy
* ylBBVhniUnfBvUuRHunlyOJ6xHU5evK8wEbvYkQGxN3wFDl7s0/d0+Ec6PnQpuIU
* 6PlQiXdEEmdIzrxk34ZtvV/ydP+uhi8HYokTJCe6E+44GIrudvH0fDgaZRoeTw1F
* eojrVD8ZEd3ZCNabGbpmnnjpF5Z4heSVlpxwTZMcnwRJbhcLoaFED3HwZI9WyDS0
* 8Fq/wEbdUA8PoMObTOqO3jxQ6E8H20debeghswwo4T7N0Gno2eJ9mwRLfZSmD34D
* /r5+UeVeG4b960LHd1/c8f2IEkQ/AJz62rfJ6L4TsKPKvPTgfaSszZSKdub13QXw
* LlL0TevaK35nXlMI4F2kRIQltrikFpd0+PD/mxI3bvWiYQdHvuGnHxM3ul//USd2
* A50CXMjkrjmbkpLti8+bIOW46Tof19Hb1kVqRj78ePz6t3P+RJONZKl+V5X9ZsfT
* 5eH75fr8KiLNFpqqvEWWpiBLFTm7crVpzruWcQPPj98uleI/a7orF0koAAA=
* -----END EMBEDDED OBJECT-----
*/
#include "act_p.h"
#include "act_grid.h"
/* forward declarations */
struct act_grid_tile_st;
struct act_grid_seg_st;
/* corresponding types */
typedef struct act_grid_tile_st act_grid_tile_t;
typedef struct act_grid_seg_st act_grid_seg_t;
/* the structure of a grid tile */
struct act_grid_tile_st {
ACT_LIST_ELEM(act_grid_tile_t) gt_link; /* linkage to next tile */
};
/* the structure of a grid segment */
struct act_grid_seg_st {
ACT_RING_ELEM(act_grid_seg_t) gs_link; /* linkage to next+prev segments */
act_grid_tile_t *gs_tile_base; /* pointer to tile base */
int gs_tile_num; /* number of tiles */
ACT_LIST_HEAD(act_grid_tile_t) gs_tile_free_list; /* list of free tiles */
int gs_tile_free_num; /* number of free tiles */
};
/* the structure of a grid */
struct act_grid_st {
act_ctx_t *g_ctx; /* context structure */
ACT_RING_HEAD(act_grid_seg_t) g_seg; /* ring of segments */
int g_seg_num; /* number of segments */
size_t g_tile_size; /* size of a tile */
int g_tile_num_first; /* number of tiles in first segment */
};
/* create a grid segment [INTERNAL] */
static act_rc_t
act_grid_seg_create(
act_ctx_t *ctx,
act_grid_seg_t **pseg,
size_t tile_size,
int tile_num)
{
size_t seg_top_size;
size_t seg_size;
act_grid_seg_t *seg;
act_grid_tile_t *tile;
int i;
/* determine (aligned) sizes */
seg_top_size = act_mem_align(sizeof(act_grid_seg_t));
seg_size = seg_top_size + (tile_size * tile_num);
/* allocate first segment */
if ((seg = act_mem_alloc_ctx(ctx, seg_size)) == NULL)
return ACT_ERR_SYS;
/* initialize first segment */
ACT_RING_ELEM_INIT(seg, gs_link);
seg->gs_tile_base = (act_grid_tile_t *)((char *)seg + seg_top_size);
seg->gs_tile_num = tile_num;
ACT_LIST_ELEM_INIT(seg->gs_tile_base, gt_link);
ACT_LIST_INIT(&seg->gs_tile_free_list);
ACT_LIST_INSERT_HEAD(&seg->gs_tile_free_list, seg->gs_tile_base, gt_link);
seg->gs_tile_free_num = seg->gs_tile_num;
/* initialize free tile list in first segment */
tile = ACT_LIST_FIRST(&seg->gs_tile_free_list);
for (i = 0; i < seg->gs_tile_free_num-1; i++) {
ACT_LIST_NEXT(tile, gt_link) = (act_grid_tile_t *)((char *)tile+tile_size);
tile = ACT_LIST_NEXT(tile, gt_link);
}
ACT_LIST_NEXT(tile, gt_link) = NULL;
/* pass segment to caller */
*pseg = seg;
return ACT_OK;
}
/* create a grid */
act_rc_t
act_grid_create(
act_grid_t **pgrid,
act_ctx_t *ctx,
size_t tile_size,
int tile_num)
{
act_grid_t *grid;
act_grid_seg_t *seg;
act_rc_t rc;
/* consistency checks */
act_argcheck(ctx != NULL);
act_argcheck(tile_size >= 1);
act_argcheck(tile_num >= 1);
/* determine (aligned) sizes */
tile_size = act_mem_align(tile_size);
/* allocate top-level grid structure */
if ((grid = (act_grid_t *)act_mem_alloc_ctx(ctx, sizeof(act_grid_t))) == NULL)
return ACT_ERR_SYS;
/* allocate first segment */
if ((rc = act_grid_seg_create(ctx, &seg, tile_size, tile_num)) != ACT_OK) {
act_mem_free_ctx(ctx, grid);
return rc;
}
/* initialize top-level structure */
grid->g_ctx = act_ctx_dup(ctx, NULL);
ACT_RING_INIT(&grid->g_seg, act_grid_seg_t, gs_link);
ACT_RING_INSERT_HEAD(&grid->g_seg, seg, act_grid_seg_t, gs_link);
grid->g_seg_num = 1;
grid->g_tile_size = tile_size;
grid->g_tile_num_first = tile_num;
/* pass grid to caller */
*pgrid = grid;
return ACT_OK;
}
/* destroy a grid */
act_rc_t
act_grid_destroy(
act_grid_t *grid)
{
act_grid_seg_t *seg;
act_grid_seg_t *seg_last;
/* consistency checks */
act_argcheck(grid != NULL);
/* destroy grid segments */
seg_last = ACT_RING_FIRST(&grid->g_seg);
while (seg_last != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) {
seg = ACT_RING_NEXT(seg_last, gs_link);
act_mem_free_ctx(grid->g_ctx, seg_last);
}
/* destroy top-level grid structure */
act_mem_free_ctx(grid->g_ctx, grid);
return ACT_OK;
}
/* allocate a tile from a grid */
act_rc_t
act_grid_alloc(
act_grid_t *grid,
void **ptile)
{
act_grid_seg_t *seg;
act_grid_seg_t *seg_l1;
act_grid_seg_t *seg_l2;
act_grid_tile_t *tile;
act_rc_t rc;
int tile_num;
/* consistency checks */
act_argcheck(grid != NULL);
act_argcheck(ptile != NULL);
/* find segment with first free tile */
seg_l2 = NULL;
seg_l1 = NULL;
seg = ACT_RING_FIRST(&grid->g_seg);
while (seg != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) {
if (seg->gs_tile_free_num > 0)
break;
seg_l2 = seg_l1;
seg_l1 = seg;
seg = ACT_RING_NEXT(seg, gs_link);
}
/* if no more segment with a free tile exists, add new segment */
if (seg == ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) {
/* tile_num increases with Fibonacci behaviour, i.e,
tile_num(seg) = tile_num(seg_l1) + tile_num(seg_l2). This way
the segments grow in size exponentially but not as fast as
twith he usual "double the size" approach. */
if (seg_l2 == NULL)
tile_num = grid->g_tile_num_first;
else
tile_num = seg_l1->gs_tile_num + seg_l2->gs_tile_num;
if ((rc = act_grid_seg_create(grid->g_ctx, &seg, grid->g_tile_size, tile_num)) != ACT_OK)
return rc;
ACT_RING_INSERT_TAIL(&grid->g_seg, seg, act_grid_seg_t, gs_link);
grid->g_seg_num++;
}
/* allocate tile from segment */
tile = ACT_LIST_FIRST(&seg->gs_tile_free_list);
ACT_LIST_REMOVE_HEAD(&seg->gs_tile_free_list, gt_link);
seg->gs_tile_free_num--;
/* pass tile to caller */
*ptile = tile;
return ACT_OK;
}
/* find grid segment where tile is stored [INTERNAL] */
static act_rc_t
act_grid_seg_find(
act_grid_t *grid,
act_grid_seg_t **pseg,
act_grid_tile_t *tile)
{
act_grid_seg_t *seg;
seg = ACT_RING_FIRST(&grid->g_seg);
while (seg != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) {
if ( seg->gs_tile_base <= tile
&& tile < (seg->gs_tile_base+(grid->g_tile_size*seg->gs_tile_num))) {
if (pseg != NULL)
*pseg = seg;
return ACT_OK;
}
seg = ACT_RING_NEXT(seg, gs_link);
}
return ACT_ERR_INT;
}
/* free a tile to a grid */
act_rc_t
act_grid_free(
act_grid_t *grid,
void *_tile)
{
act_grid_seg_t *seg;
act_grid_tile_t *tile;
act_rc_t rc;
/* cast to internal structure */
tile = (act_grid_tile_t *)_tile;
/* consistency checks */
act_argcheck(grid != NULL);
act_argcheck(tile != NULL);
/* find segment of tile */
if ((rc = act_grid_seg_find(grid, &seg, tile)) != ACT_OK)
return rc;
/* move into list of free tiles */
ACT_LIST_INSERT_HEAD(&seg->gs_tile_free_list, tile, gt_link);
seg->gs_tile_free_num++;
/* free segment if it is now empty */
if ( grid->g_seg_num > 1
&& seg->gs_tile_num == seg->gs_tile_free_num) {
ACT_RING_REMOVE(seg, gs_link);
grid->g_seg_num--;
act_mem_free_ctx(grid->g_ctx, seg);
}
return ACT_OK;
}
/* test whether a tile is inside a grid */
act_rc_t
act_grid_inside(
act_grid_t *grid,
void *_tile)
{
act_grid_tile_t *tile;
/* cast to internal structure */
tile = (act_grid_tile_t *)_tile;
/* consistency checks */
act_argcheck(grid != NULL);
act_argcheck(tile != NULL);
/* just try to find a segment */
return act_grid_seg_find(grid, NULL, tile);
}
/* determine grid statistics */
act_rc_t
act_grid_stat(
act_grid_t *grid,
int *pchunks,
int *pbytes_mgmt, int *pbytes_used, int *pbytes_free,
int *ptiles_used, int *ptiles_free)
{
act_grid_seg_t *seg;
int chunks = 0;
int bytes_mgmt = 0;
int bytes_used = 0;
int bytes_free = 0;
int tiles_used = 0;
int tiles_free = 0;
/* consistency checks */
act_argcheck(grid != NULL);
/* determine statistic information */
bytes_mgmt += sizeof(act_grid_t);
chunks += 1;
ACT_RING_FOREACH(seg, &grid->g_seg, act_grid_seg_t, gs_link) {
chunks++;
bytes_mgmt += sizeof(act_grid_seg_t);
bytes_used += ((seg->gs_tile_num - seg->gs_tile_free_num) * grid->g_tile_size);
bytes_free += (seg->gs_tile_free_num * grid->g_tile_size);
tiles_used += (seg->gs_tile_num - seg->gs_tile_free_num);
tiles_free += seg->gs_tile_free_num;
}
/* pass statistic information to caller */
if (pchunks != NULL)
*pchunks = chunks;
if (pbytes_mgmt != NULL)
*pbytes_mgmt = bytes_mgmt;
if (pbytes_used != NULL)
*pbytes_used = bytes_used;
if (pbytes_free != NULL)
*pbytes_free = bytes_free;
if (ptiles_used != NULL)
*ptiles_used = tiles_used;
if (ptiles_free != NULL)
*ptiles_free = tiles_free;
return ACT_OK;
}
