/* ** OSSP cfg - Configuration Parsing ** Copyright (c) 2002-2006 Ralf S. Engelschall ** 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; }