amxpool.c

00001 /*  Simple allocation from a memory pool, with automatic release of
00002  *  least-recently used blocks (LRU blocks).
00003  *
00004  *  These routines are as simple as possible, and they are neither re-entrant
00005  *  nor thread-safe. Their purpose is to have a standard implementation for
00006  *  systems where overlays are used and malloc() is not available.
00007  *
00008  *  The algorithm uses a first-fit strategy. It keeps all blocks in a single
00009  *  list (both used blocks and free blocks are in the same list). Every memory
00010  *  block must have a unique number that identifies the block. This unique
00011  *  number allows to search for the presence of the block in the pool and for
00012  *  "conditional allocation".
00013  *
00014  *
00015  *  Copyright (c) ITB CompuPhase, 2007-2012
00016  *
00017  *  Licensed under the Apache License, Version 2.0 (the "License"); you may not
00018  *  use this file except in compliance with the License. You may obtain a copy
00019  *  of the License at
00020  *
00021  *      http://www.apache.org/licenses/LICENSE-2.0
00022  *
00023  *  Unless required by applicable law or agreed to in writing, software
00024  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00025  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
00026  *  License for the specific language governing permissions and limitations
00027  *  under the License.
00028  *
00029  *  Version: $Id: amxpool.c 4731 2012-06-21 11:11:18Z thiadmer $
00030  */
00031 #include <assert.h>
00032 #include "amx.h"
00033 #include "amxpool.h"
00034 
00035 #if !defined NULL
00036   #define NULL  ((void*)0)
00037 #endif
00038 
00039 #define MIN_BLOCKSIZE 32
00040 #define PROTECT_LRU   0xffff
00041 
00042 typedef struct tagARENA {
00043   unsigned blocksize;
00044   short index;      /* overlay index, -1 if free */
00045   unsigned short lru;
00046 } ARENA;
00047 
00048 static void *pool_base;
00049 static unsigned pool_size;
00050 static unsigned short pool_lru;
00051 
00052 static void touchblock(ARENA *hdr);
00053 static ARENA *findblock(int index);
00054 
00055 /* amx_poolinit() initializes the memory pool for the allocated blocks.
00056  * If parameter pool is NULL, the existing pool is cleared (without changing
00057  * its position or size).
00058  */
00059 void amx_poolinit(void *pool, unsigned size)
00060 {
00061   assert(pool!=NULL || pool_base!=NULL);
00062   if (pool!=NULL) {
00063     assert(size>sizeof(ARENA));
00064     /* save parameters in global variables, then "free" the entire pool */
00065     pool_base=pool;
00066     pool_size=size;
00067   } /* if */
00068   pool_lru=0;
00069   amx_poolfree(NULL);
00070 }
00071 
00072 /* amx_poolfree() releases a block allocated earlier. The parameter must have
00073  * the same value as that returned by an earlier call to amx_poolalloc(). That
00074  * is, the "block" parameter must point directly behind the arena header of the
00075  * block.
00076  * When parameter "block" is NULL, the pool is re-initialized (meaning that
00077  * all blocks are freed).
00078  */
00079 void amx_poolfree(void *block)
00080 {
00081   ARENA *hdr,*hdr2;
00082   unsigned sz;
00083 
00084   assert(pool_base!=NULL);
00085   assert(pool_size>sizeof(ARENA));
00086 
00087   /* special case: if "block" is NULL, create a single free space */
00088   if (block==NULL) {
00089     /* store an arena header at the start of the pool */
00090     hdr=(ARENA*)pool_base;
00091     hdr->blocksize=pool_size-sizeof(ARENA);
00092     hdr->index=-1;
00093     hdr->lru=0;
00094   } else {
00095     hdr=(ARENA*)((char*)block-sizeof(ARENA));
00096     assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
00097     assert(hdr->blocksize<pool_size);
00098 
00099     /* free this block */
00100     hdr->index=-1;
00101 
00102     /* try to coalesce with the next block */
00103     hdr2=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
00104     if (hdr2->index==-1)
00105       hdr->blocksize+=hdr2->blocksize+sizeof(ARENA);
00106 
00107     /* try to coalesce with the previous block */
00108     if ((void*)hdr!=pool_base) {
00109       sz=pool_size;
00110       hdr2=(ARENA*)pool_base;
00111       while (sz>0 && (char*)hdr2+hdr2->blocksize+sizeof(ARENA)!=(char*)hdr) {
00112         assert(sz<=pool_size);
00113         sz-=hdr2->blocksize+sizeof(ARENA);
00114         hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA));
00115       } /* while */
00116       assert((char*)hdr2+hdr2->blocksize+sizeof(ARENA)==(char*)hdr);
00117       if (hdr2->index==-1)
00118         hdr2->blocksize+=hdr->blocksize+sizeof(ARENA);
00119     } /* if */
00120   } /* if */
00121 }
00122 
00123 /* amx_poolalloc() allocates the requested number of bytes from the pool and
00124  * returns a header to the start of it. Every block in the pool is prefixed
00125  * with an "arena header"; the return value of this function points just
00126  * behind this arena header.
00127  *
00128  * The block with the specified "index" should not already exist in the pool.
00129  * In other words, parameter "index" should be unique for every of memory block,
00130  * and the block should not change in size. Use amx_poolfind() to verify whether
00131  * a block is already in the pool (and optionally amx_poolfree() to remove it).
00132  *
00133  * If no block of sufficient size is available, the routine frees blocks until
00134  * the requested amount of memory can be allocated. There is no intelligent
00135  * algorithm involved: the routine just frees the least-recently used block at
00136  * every iteration (without considering the size of the block or whether that
00137  * block is adjacent to a free block).
00138  */
00139 void *amx_poolalloc(unsigned size,int index)
00140 {
00141   ARENA *hdr,*hdrlru;
00142   unsigned sz;
00143   unsigned short minlru;
00144 
00145   assert(size>0);
00146   assert(index>=0 && index<=SHRT_MAX);
00147   assert(findblock(index)==NULL);
00148 
00149   /* align the size to a cell boundary */
00150   if ((size % sizeof(cell))!=0)
00151     size+=sizeof(cell)-(size % sizeof(cell));
00152   if (size+sizeof(ARENA)>pool_size)
00153     return NULL;  /* requested block does not fit in the pool */
00154 
00155   /* find a block large enough to get the size plus an arena header; at
00156    * the same time, detect the block with the lowest LRU
00157    * if no block of sufficient size can be found, the routine then frees
00158    * the block with the lowest LRU count and tries again
00159    */
00160   do {
00161     sz=pool_size;
00162     hdr=(ARENA*)pool_base;
00163     hdrlru=hdr;
00164     minlru=USHRT_MAX;
00165     while (sz>0) {
00166       assert(sz<=pool_size);
00167       assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
00168       if (hdr->index==-1 && hdr->blocksize>=size)
00169         break;
00170       if (hdr->index!=-1 && hdr->lru<minlru) {
00171         minlru=hdr->lru;
00172         hdrlru=hdr;
00173       } /* if */
00174       sz-=hdr->blocksize+sizeof(ARENA);
00175       hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
00176     } /* while */
00177     assert(sz<=pool_size);
00178     if (sz==0) {
00179       /* free up memory and try again */
00180       assert(hdrlru->index!=-1);
00181       amx_poolfree((char*)hdrlru+sizeof(ARENA));
00182     } /* if */
00183   } while (sz==0);
00184 
00185   /* see whether to allocate the entire free block, or to cut it in two blocks */
00186   if (hdr->blocksize>size+MIN_BLOCKSIZE+sizeof(ARENA)) {
00187     /* cut the block in two */
00188     ARENA *next=(ARENA*)((char*)hdr+size+sizeof(ARENA));
00189     next->blocksize=hdr->blocksize-size-sizeof(ARENA);
00190     next->index=-1;
00191     next->lru=0;
00192   } else {
00193     size=hdr->blocksize;
00194   } /* if */
00195   hdr->blocksize=size;
00196   hdr->index=(short)index;
00197   touchblock(hdr);    /* set LRU field */
00198 
00199   return (void*)((char*)hdr+sizeof(ARENA));
00200 }
00201 
00202 /* amx_poolfind() returns the address of the memory block with the given index,
00203  * or NULL if no such block exists. Parameter "index" should not be -1, because
00204  * -1 represents a free block (actually, only positive values are valid).
00205  * When amx_poolfind() finds the block, it increments its LRU count.
00206  */
00207 void *amx_poolfind(int index)
00208 {
00209   ARENA *hdr=findblock(index);
00210   if (hdr==NULL)
00211     return NULL;
00212   touchblock(hdr);
00213   return (void*)((char*)hdr+sizeof(ARENA));
00214 }
00215 
00216 int amx_poolprotect(int index)
00217 {
00218   ARENA *hdr=findblock(index);
00219   if (hdr==NULL)
00220     return AMX_ERR_GENERAL;
00221   hdr->lru=PROTECT_LRU;
00222   return AMX_ERR_NONE;
00223 }
00224 
00225 static ARENA *findblock(int index)
00226 {
00227   ARENA *hdr;
00228   unsigned sz;
00229 
00230   assert(index>=0);
00231   sz=pool_size;
00232   hdr=(ARENA*)pool_base;
00233   while (sz>0 && hdr->index!=index) {
00234     assert(sz<=pool_size);
00235     assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
00236     sz-=hdr->blocksize+sizeof(ARENA);
00237     hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
00238   } /* while */
00239   assert(sz<=pool_size);
00240   return (sz>0 && hdr->index==index) ? hdr : NULL;
00241 }
00242 
00243 static void touchblock(ARENA *hdr)
00244 {
00245   assert(hdr!=NULL);
00246   if (++pool_lru >= PROTECT_LRU)
00247     pool_lru=0;
00248   hdr->lru=pool_lru;
00249 
00250   /* special case: if the overlay LRU count wrapped back to zero, set the
00251    * LRU count of all blocks to zero, but set the count of the block just
00252    * touched to 1 (skip blocks marked as protected, too)
00253    */
00254   if (pool_lru==0) {
00255     ARENA *hdr2;
00256     unsigned sz=pool_size;
00257     hdr2=(ARENA*)pool_base;
00258     while (sz>0) {
00259       assert(sz<=pool_size);
00260       if (hdr2->lru!=PROTECT_LRU)
00261         hdr2->lru=0;
00262       sz-=hdr2->blocksize+sizeof(ARENA);
00263       hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA));
00264     } /* while */
00265     assert(sz==0);
00266     hdr->lru=++pool_lru;
00267   } /* if */
00268 }