/* ** Act - Abstract Container Type Library ** Copyright (c) 1999-2002 Ralf S. Engelschall ** ** This file is part of Act, a library for dealing with Abstract ** Container Types which can be found at http://www.ossp.org/pkg/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; }