Index: ossp-pkg/act/act_grid.c RCS File: /v/ossp/cvs/ossp-pkg/act/act_grid.c,v rcsdiff -q -kk '-r1.4' '-r1.5' -u '/v/ossp/cvs/ossp-pkg/act/act_grid.c,v' 2>/dev/null --- act_grid.c 2002/01/02 17:05:53 1.4 +++ act_grid.c 2002/01/18 17:31:39 1.5 @@ -26,101 +26,341 @@ ** 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" -/* the top-level structure of a grid */ +/* 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_grid_tile_t *gt_next; +}; + +/* the structure of a grid segment */ +struct act_grid_seg_st { + act_grid_seg_t *gs_next; + act_grid_tile_t *gs_tile_base; + int gs_tile_num; + act_grid_tile_t *gs_tile_free_first; + int gs_tile_free_num; +}; + +/* the structure of a grid */ struct act_grid_st { - act_ctx_t *g_ctx; - void *g_seg_block; - void *g_seg_free; - size_t g_seg_num; - size_t g_seg_size; + act_ctx_t *g_ctx; + act_grid_seg_t *g_seg_first; + int g_seg_num; + size_t g_tile_size; + int g_tile_num_first; }; -act_grid_t * -act_grid_create( +/* create a grid segment [INTERNAL] */ +static act_rc_t +act_grid_seg_create( act_ctx_t *ctx, - size_t segnum, - size_t segsize) + act_grid_seg_t **pseg, + size_t tile_size, + int tile_num) { - act_grid_t *grid = NULL; - void *block; - void *seg; + 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 */ + seg->gs_next = NULL; + seg->gs_tile_base = (act_grid_tile_t *)((char *)seg + seg_top_size); + seg->gs_tile_num = tile_num; + seg->gs_tile_free_first = seg->gs_tile_base; + seg->gs_tile_free_num = seg->gs_tile_num; + + /* initialize free tile list in first segment */ + tile = seg->gs_tile_free_first; + for (i = 0; i < seg->gs_tile_free_num-1; i++) { + tile->gt_next = (act_grid_tile_t *)((char *)tile+tile_size); + tile = tile->gt_next; + } + tile->gt_next = 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 */ - insist(ctx != NULL, NULL); - insist(segnum >= 1, NULL); - insist(segsize >= sizeof(void *), NULL); + act_argcheck(ctx != NULL); + act_argcheck(tile_size >= 1); + act_argcheck(tile_num >= 1); - /* align segment size */ - segsize = act_mem_align(segsize); + /* determine (aligned) sizes */ + tile_size = act_mem_align(tile_size); - /* allocate memory chunks */ + /* allocate top-level grid structure */ if ((grid = (act_grid_t *)act_mem_alloc_ctx(ctx, sizeof(act_grid_t))) == NULL) - return NULL; - if ((block = act_mem_alloc_ctx(ctx, segnum * segsize)) == 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 NULL; + return rc; } /* initialize top-level structure */ - grid->g_ctx = act_ctx_dup(ctx, NULL); - grid->g_seg_block = block; - grid->g_seg_free = block; - grid->g_seg_num = segnum; - grid->g_seg_size = segsize; + grid->g_ctx = act_ctx_dup(ctx, NULL); + grid->g_seg_first = seg; + grid->g_seg_num = 1; + grid->g_tile_size = tile_size; + grid->g_tile_num_first = tile_num; - /* initialize segment block */ - seg = grid->g_seg_free; - for (i = 0; i < segnum-1; i++) { - *((void **)seg) = (char *)seg+segsize; - seg = (char *)seg+segsize; - } - *((void **)seg) = NULL; + /* pass grid to caller */ + *pgrid = grid; - return grid; + return ACT_OK; } -int +/* destroy a grid */ +act_rc_t act_grid_destroy( act_grid_t *grid) { - act_ctx_t *ctx; + act_grid_seg_t *seg; + act_grid_seg_t *seg_last; + + /* consistency checks */ + act_argcheck(grid != NULL); - insist(grid != NULL, FALSE); + /* destroy grid segments */ + seg_last = grid->g_seg_first; + while (seg_last != NULL) { + seg = seg_last->gs_next; + act_mem_free_ctx(grid->g_ctx, seg_last); + } - ctx = grid->g_ctx; - act_mem_free_ctx(ctx, grid->g_seg_block); - act_mem_free_ctx(ctx, grid); + /* destroy top-level grid structure */ + act_mem_free_ctx(grid->g_ctx, grid); - return TRUE; + return ACT_OK; } -void * +/* allocate a tile from a grid */ +act_rc_t act_grid_alloc( - act_grid_t *grid) + act_grid_t *grid, + void **ptile) { - void *chunk = NULL; + 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; - insist(grid != NULL, NULL); + /* consistency checks */ + act_argcheck(grid != NULL); + act_argcheck(ptile != NULL); - /* XXX */ + /* find segment with first free tile */ + seg_l2 = NULL; + seg_l1 = NULL; + seg = grid->g_seg_first; + while (seg != NULL) { + if (seg->gs_tile_free_num > 0) + break; + seg_l2 = seg_l1; + seg_l1 = seg; + seg = seg->gs_next; + } - return chunk; + /* if no more segment with a free tile exists, add new segment */ + if (seg == NULL) { + /* 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; + if (seg_l1 == NULL) + grid->g_seg_first = seg; + else + seg_l1->gs_next = seg; + } + + /* allocate tile from segment */ + tile = seg->gs_tile_free_first; + seg->gs_tile_free_first = tile->gt_next; + seg->gs_tile_free_num--; + + /* pass tile to caller */ + *ptile = tile; + + return ACT_OK; } -int +/* 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 = grid->g_seg_first; + while (seg != NULL) { + 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 = seg->gs_next; + } + return ACT_ERR_INT; +} + +/* free a tile to a grid */ +act_rc_t act_grid_free( act_grid_t *grid, - void *segptr) + void *_tile) +{ + act_grid_seg_t *seg; + act_grid_seg_t *seg_last; + 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 */ + tile->gt_next = seg->gs_tile_free_first; + seg->gs_tile_free_first = tile; + seg->gs_tile_free_num++; + + /* free last segment if it is empty and if segment + before (this one here) is now also empty */ + if ( seg->gs_tile_num == seg->gs_tile_free_num + && (seg_last = seg->gs_next) != NULL ) { + if ( seg_last->gs_tile_num == seg_last->gs_tile_free_num + && seg_last->gs_next == NULL ) { + act_mem_free_ctx(grid->g_ctx, seg_last); + seg->gs_next = NULL; + } + } + + return ACT_OK; +} + +/* test whether a tile is inside a grid */ +act_rc_t +act_grid_inside( + act_grid_t *grid, + void *_tile) { - insist(grid != NULL, FALSE); - insist(segptr != NULL, FALSE); + act_grid_tile_t *tile; + + /* cast to internal structure */ + tile = (act_grid_tile_t *)_tile; - /* XXX */ + /* consistency checks */ + act_argcheck(grid != NULL); + act_argcheck(tile != NULL); - return TRUE; + /* just try to find a segment */ + return act_grid_seg_find(grid, NULL, tile); } Index: ossp-pkg/act/act_grid.h RCS File: /v/ossp/cvs/ossp-pkg/act/act_grid.h,v rcsdiff -q -kk '-r1.3' '-r1.4' -u '/v/ossp/cvs/ossp-pkg/act/act_grid.h,v' 2>/dev/null --- act_grid.h 2002/01/02 17:05:53 1.3 +++ act_grid.h 2002/01/18 17:31:39 1.4 @@ -26,16 +26,17 @@ ** act_grid.h: memory grid (declaration) */ -#ifndef _ACT_GRID_H_ -#define _ACT_GRID_H_ +#ifndef __ACT_GRID_H__ +#define __ACT_GRID_H__ struct act_grid_st; typedef struct act_grid_st act_grid_t; -extern act_grid_t *act_grid_create (act_ctx_t *ctx, size_t segnum, size_t segsize); -extern void *act_grid_alloc (act_grid_t *grid); -extern int act_grid_free (act_grid_t *grid, void *segptr); -extern int act_grid_destroy (act_grid_t *grid); +extern act_rc_t act_grid_create (act_grid_t **grid, act_ctx_t *ctx, size_t tile_size, int tile_num); +extern act_rc_t act_grid_alloc (act_grid_t *grid, void **tile); +extern act_rc_t act_grid_free (act_grid_t *grid, void *tile); +extern act_rc_t act_grid_inside (act_grid_t *grid, void *tile); +extern act_rc_t act_grid_destroy(act_grid_t *grid); -#endif /* _ACT_GRID_H_ */ +#endif /* __ACT_GRID_H__ */