ossp-pkg/cfg/cfg_grid.c
/*
** OSSP cfg - Configuration Parsing
** Copyright (c) 2002-2006 Ralf S. Engelschall <rse@engelschall.com>
** Copyright (c) 2002-2006 The OSSP Project (http://www.ossp.org/)
**
** This file is part of OSSP cfg, a configuration parsing
** library which can be found at http://www.ossp.org/pkg/lib/cfg/.
**
** 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.
**
** cfg_grid.c: grid memory allocator (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 cfg 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 (cfg_grid_seg_t) of
* those fixed size objects (cfg_grid_tile_t) and linking them into
* a top-level grid structure (cfg_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 linear array after a heading 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
* H4sIAOT/mDwCA61aTW/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 "cfg_grid.h"
/* macro set for implementing single-linked lists */
#define CFG_LIST_HEAD(type)\
struct { type *first; }
#define CFG_LIST_ELEM(type) \
struct { type *next; }
#define CFG_LIST_INIT(hp) \
CFG_LIST_FIRST((hp)) = NULL
#define CFG_LIST_ELEM_INIT(ep, field) \
CFG_LIST_NEXT((ep), field) = NULL
#define CFG_LIST_FIRST(hp) \
((hp)->first)
#define CFG_LIST_NEXT(ep, field) \
((ep)->field.next)
#define CFG_LIST_INSERT_HEAD(hp, ep, field) \
do { CFG_LIST_NEXT((ep), field) = CFG_LIST_FIRST((hp)); \
CFG_LIST_FIRST((hp)) = (ep); } while (0)
#define CFG_LIST_REMOVE_HEAD(hp, field) \
CFG_LIST_FIRST((hp)) = \
CFG_LIST_NEXT(CFG_LIST_FIRST((hp)), field)
/* macro set for implementing double-linked rings */
#define CFG_RING_HEAD(type) \
struct { type *next; type *prev; }
#define CFG_RING_ELEM(type) \
struct { type *next; type *prev; }
#define CFG_RING_SENTINEL(hp, type, field) \
(type *)(void *)((char *)(hp) - ((size_t)(&((type *)0)->field)))
#define CFG_RING_INIT(hp, type, field) \
do { CFG_RING_FIRST((hp)) = CFG_RING_SENTINEL((hp), type, field); \
CFG_RING_LAST((hp)) = CFG_RING_SENTINEL((hp), type, field); } while (0)
#define CFG_RING_ELEM_INIT(ep, field) \
do { CFG_RING_NEXT((ep), field) = (ep); \
CFG_RING_PREV((ep), field) = (ep); } while (0)
#define CFG_RING_FIRST(hp) \
((hp)->next)
#define CFG_RING_LAST(hp) \
((hp)->prev)
#define CFG_RING_NEXT(ep, field) \
((ep)->field.next)
#define CFG_RING_PREV(ep, field) \
((ep)->field.prev)
#define CFG_RING_SPLICE_BEFORE(lep, ep1, epN, field) \
do { \
CFG_RING_NEXT((epN), field) = (lep); \
CFG_RING_PREV((ep1), field) = CFG_RING_PREV((lep), field); \
CFG_RING_NEXT(CFG_RING_PREV((lep), field), field) = (ep1); \
CFG_RING_PREV((lep), field) = (epN); \
} while (0)
#define CFG_RING_SPLICE_AFTER(lep, ep1, epN, field) \
do { \
CFG_RING_PREV((ep1), field) = (lep); \
CFG_RING_NEXT((epN), field) = CFG_RING_NEXT((lep), field); \
CFG_RING_PREV(CFG_RING_NEXT((lep), field), field) = (epN); \
CFG_RING_NEXT((lep), field) = (ep1); \
} while (0)
#define CFG_RING_SPLICE_HEAD(hp, ep1, epN, type, field) \
CFG_RING_SPLICE_AFTER(CFG_RING_SENTINEL((hp), type, field), (ep1), (epN), field)
#define CFG_RING_SPLICE_TAIL(hp, ep1, epN, type, field) \
CFG_RING_SPLICE_BEFORE(CFG_RING_SENTINEL((hp), type, field), (ep1), (epN), field)
#define CFG_RING_INSERT_BEFORE(lep, nep, field) \
CFG_RING_SPLICE_BEFORE((lep), (nep), (nep), field)
#define CFG_RING_INSERT_AFTER(lep, nep, field) \
CFG_RING_SPLICE_AFTER((lep), (nep), (nep), field)
#define CFG_RING_INSERT_HEAD(hp, nep, type, field) \
CFG_RING_SPLICE_HEAD((hp), (nep), (nep), type, field)
#define CFG_RING_INSERT_TAIL(hp, nep, type, field) \
CFG_RING_SPLICE_TAIL((hp), (nep), (nep), type, field)
#define CFG_RING_UNSPLICE(ep1, epN, field) \
do { \
CFG_RING_NEXT(CFG_RING_PREV((ep1), field), field) = \
CFG_RING_NEXT((epN), field); \
CFG_RING_PREV(CFG_RING_NEXT((epN), field), field) = \
CFG_RING_PREV((ep1), field); \
} while (0)
#define CFG_RING_REMOVE(ep, field) \
CFG_RING_UNSPLICE((ep), (ep), field)
#define CFG_RING_FOREACH(ep, hp, type, field) \
for ((ep) = CFG_RING_FIRST((hp)); \
(ep) != CFG_RING_SENTINEL((hp), type, field); \
(ep) = CFG_RING_NEXT((ep), field))
#define CFG_RING_FOREACH_REVERSE(ep, hp, type, field) \
for ((ep) = CFG_RING_LAST((hp)); \
(ep) != CFG_RING_SENTINEL((hp), type, field); \
(ep) = CFG_RING_PREV((ep), field))
/* forward declarations */
struct cfg_grid_tile_st;
struct cfg_grid_seg_st;
/* corresponding types */
typedef struct cfg_grid_tile_st cfg_grid_tile_t;
typedef struct cfg_grid_seg_st cfg_grid_seg_t;
/* the structure of a grid tile */
struct cfg_grid_tile_st {
CFG_LIST_ELEM(cfg_grid_tile_t) gt_link; /* linkage to next tile */
};
/* the structure of a grid segment */
struct cfg_grid_seg_st {
CFG_RING_ELEM(cfg_grid_seg_t) gs_link; /* linkage to next+prev segments */
cfg_grid_tile_t *gs_tile_base; /* pointer to tile base */
int gs_tile_num; /* number of tiles */
CFG_LIST_HEAD(cfg_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 cfg_grid_st {
CFG_RING_HEAD(cfg_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 */
};
/*
* Align a size to the next larger or equal size which is likely to have the
* longest *relevant* CPU-specific memory word alignment restrictions.
*/
static size_t cfg_mem_align(size_t size)
{
union mem_word {
void *mw_vp;
void (*mw_fp)(void);
char *mw_cp;
long mw_l;
double mw_d;
};
return ((1+((size-1) / sizeof(union mem_word))) * sizeof(union mem_word));
}
/* create a grid segment [INTERNAL] */
static cfg_rc_t
cfg_grid_seg_create(
cfg_grid_seg_t **pseg,
size_t tile_size,
int tile_num)
{
size_t seg_top_size;
size_t seg_size;
cfg_grid_seg_t *seg;
cfg_grid_tile_t *tile;
int i;
/* determine (aligned) sizes */
seg_top_size = cfg_mem_align(sizeof(cfg_grid_seg_t));
seg_size = seg_top_size + (tile_size * tile_num);
/* allocate first segment */
if ((seg = (cfg_grid_seg_t *)malloc(seg_size)) == NULL)
return CFG_ERR_SYS;
/* initialize first segment */
CFG_RING_ELEM_INIT(seg, gs_link);
seg->gs_tile_base = (cfg_grid_tile_t *)(void *)((char *)seg + seg_top_size);
seg->gs_tile_num = tile_num;
CFG_LIST_ELEM_INIT(seg->gs_tile_base, gt_link);
CFG_LIST_INIT(&seg->gs_tile_free_list);
CFG_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 = CFG_LIST_FIRST(&seg->gs_tile_free_list);
for (i = 0; i < seg->gs_tile_free_num-1; i++) {
CFG_LIST_NEXT(tile, gt_link) = (cfg_grid_tile_t *)(void *)((char *)tile+tile_size);
tile = CFG_LIST_NEXT(tile, gt_link);
}
CFG_LIST_NEXT(tile, gt_link) = NULL;
/* pass segment to caller */
*pseg = seg;
return CFG_OK;
}
/* create a grid */
cfg_rc_t
cfg_grid_create(
cfg_grid_t **pgrid,
size_t tile_size,
int tile_num)
{
cfg_grid_t *grid;
cfg_grid_seg_t *seg;
cfg_rc_t rc;
/* consistency checks */
if (tile_size < 1)
return CFG_ERR_ARG;
if (tile_num < 1)
return CFG_ERR_ARG;
/* determine (aligned) sizes */
tile_size = cfg_mem_align(tile_size);
/* allocate top-level grid structure */
if ((grid = (cfg_grid_t *)malloc(sizeof(cfg_grid_t))) == NULL)
return CFG_ERR_SYS;
/* allocate first segment */
if ((rc = cfg_grid_seg_create(&seg, tile_size, tile_num)) != CFG_OK) {
free(grid);
return rc;
}
/* initialize top-level structure */
CFG_RING_INIT(&grid->g_seg, cfg_grid_seg_t, gs_link);
CFG_RING_INSERT_HEAD(&grid->g_seg, seg, cfg_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 CFG_OK;
}
/* destroy a grid */
cfg_rc_t
cfg_grid_destroy(
cfg_grid_t *grid)
{
cfg_grid_seg_t *seg;
cfg_grid_seg_t *seg_last;
/* consistency checks */
if (grid == NULL)
return CFG_ERR_ARG;
/* destroy grid segments */
seg_last = CFG_RING_FIRST(&grid->g_seg);
while (seg_last != CFG_RING_SENTINEL(&grid->g_seg, cfg_grid_seg_t, gs_link)) {
seg = CFG_RING_NEXT(seg_last, gs_link);
free(seg_last);
seg_last = seg;
}
/* destroy top-level grid structure */
free(grid);
return CFG_OK;
}
/* allocate a tile from a grid */
cfg_rc_t
cfg_grid_alloc(
cfg_grid_t *grid,
void **ptile)
{
cfg_grid_seg_t *seg;
cfg_grid_seg_t *seg_l1;
cfg_grid_seg_t *seg_l2;
cfg_grid_tile_t *tile;
cfg_rc_t rc;
int tile_num;
/* consistency checks */
if (grid == NULL || ptile == NULL)
return CFG_ERR_ARG;
/* find segment with first free tile */
seg_l2 = NULL;
seg_l1 = NULL;
seg = CFG_RING_FIRST(&grid->g_seg);
while (seg != CFG_RING_SENTINEL(&grid->g_seg, cfg_grid_seg_t, gs_link)) {
if (seg->gs_tile_free_num > 0)
break;
seg_l2 = seg_l1;
seg_l1 = seg;
seg = CFG_RING_NEXT(seg, gs_link);
}
/* if no more segment with a free tile exists, add new segment */
if (seg == CFG_RING_SENTINEL(&grid->g_seg, cfg_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 = cfg_grid_seg_create(&seg, grid->g_tile_size, tile_num)) != CFG_OK)
return rc;
CFG_RING_INSERT_TAIL(&grid->g_seg, seg, cfg_grid_seg_t, gs_link);
grid->g_seg_num++;
}
/* allocate tile from segment */
tile = CFG_LIST_FIRST(&seg->gs_tile_free_list);
CFG_LIST_REMOVE_HEAD(&seg->gs_tile_free_list, gt_link);
seg->gs_tile_free_num--;
/* pass tile to caller */
*ptile = tile;
return CFG_OK;
}
/* find grid segment where tile is stored [INTERNAL] */
static cfg_rc_t
cfg_grid_seg_find(
cfg_grid_t *grid,
cfg_grid_seg_t **pseg,
cfg_grid_tile_t *tile)
{
cfg_grid_seg_t *seg;
seg = CFG_RING_FIRST(&grid->g_seg);
while (seg != CFG_RING_SENTINEL(&grid->g_seg, cfg_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 CFG_OK;
}
seg = CFG_RING_NEXT(seg, gs_link);
}
return CFG_ERR_INT;
}
/* free a tile to a grid */
cfg_rc_t
cfg_grid_free(
cfg_grid_t *grid,
void *_tile)
{
cfg_grid_seg_t *seg;
cfg_grid_tile_t *tile;
cfg_rc_t rc;
/* cast to internal structure */
tile = (cfg_grid_tile_t *)_tile;
/* consistency checks */
if (grid == NULL || tile == NULL)
return CFG_ERR_ARG;
/* find segment of tile */
if ((rc = cfg_grid_seg_find(grid, &seg, tile)) != CFG_OK)
return rc;
/* move into list of free tiles */
CFG_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) {
CFG_RING_REMOVE(seg, gs_link);
grid->g_seg_num--;
free(seg);
}
return CFG_OK;
}
/* test whether a tile is inside a grid */
cfg_rc_t
cfg_grid_inside(
cfg_grid_t *grid,
void *_tile)
{
cfg_grid_tile_t *tile;
/* cast to internal structure */
tile = (cfg_grid_tile_t *)_tile;
/* consistency checks */
if (grid == NULL || tile == NULL)
return CFG_ERR_ARG;
/* just try to find a segment */
return cfg_grid_seg_find(grid, NULL, tile);
}
/* determine grid statistics */
cfg_rc_t
cfg_grid_stat(
cfg_grid_t *grid,
int *pchunks,
int *pbytes_mgmt, int *pbytes_used, int *pbytes_free,
int *ptiles_used, int *ptiles_free)
{
cfg_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 */
if (grid == NULL)
return CFG_ERR_ARG;
/* determine statistic information */
bytes_mgmt += sizeof(cfg_grid_t);
chunks += 1;
CFG_RING_FOREACH(seg, &grid->g_seg, cfg_grid_seg_t, gs_link) {
chunks++;
bytes_mgmt += sizeof(cfg_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 CFG_OK;
}