Diff: amxpool.c

Revision:

0:3ab1d2d14eb3

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/amxpool.c	Thu Nov 15 17:41:21 2012 +0000
@@ -0,0 +1,268 @@
+/*  Simple allocation from a memory pool, with automatic release of
+ *  least-recently used blocks (LRU blocks).
+ *
+ *  These routines are as simple as possible, and they are neither re-entrant
+ *  nor thread-safe. Their purpose is to have a standard implementation for
+ *  systems where overlays are used and malloc() is not available.
+ *
+ *  The algorithm uses a first-fit strategy. It keeps all blocks in a single
+ *  list (both used blocks and free blocks are in the same list). Every memory
+ *  block must have a unique number that identifies the block. This unique
+ *  number allows to search for the presence of the block in the pool and for
+ *  "conditional allocation".
+ *
+ *
+ *  Copyright (c) ITB CompuPhase, 2007-2012
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ *  use this file except in compliance with the License. You may obtain a copy
+ *  of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ *  License for the specific language governing permissions and limitations
+ *  under the License.
+ *
+ *  Version: $Id: amxpool.c 4731 2012-06-21 11:11:18Z thiadmer $
+ */
+#include <assert.h>
+#include "amx.h"
+#include "amxpool.h"
+
+#if !defined NULL
+  #define NULL  ((void*)0)
+#endif
+
+#define MIN_BLOCKSIZE 32
+#define PROTECT_LRU   0xffff
+
+typedef struct tagARENA {
+  unsigned blocksize;
+  short index;      /* overlay index, -1 if free */
+  unsigned short lru;
+} ARENA;
+
+static void *pool_base;
+static unsigned pool_size;
+static unsigned short pool_lru;
+
+static void touchblock(ARENA *hdr);
+static ARENA *findblock(int index);
+
+/* amx_poolinit() initializes the memory pool for the allocated blocks.
+ * If parameter pool is NULL, the existing pool is cleared (without changing
+ * its position or size).
+ */
+void amx_poolinit(void *pool, unsigned size)
+{
+  assert(pool!=NULL || pool_base!=NULL);
+  if (pool!=NULL) {
+    assert(size>sizeof(ARENA));
+    /* save parameters in global variables, then "free" the entire pool */
+    pool_base=pool;
+    pool_size=size;
+  } /* if */
+  pool_lru=0;
+  amx_poolfree(NULL);
+}
+
+/* amx_poolfree() releases a block allocated earlier. The parameter must have
+ * the same value as that returned by an earlier call to amx_poolalloc(). That
+ * is, the "block" parameter must point directly behind the arena header of the
+ * block.
+ * When parameter "block" is NULL, the pool is re-initialized (meaning that
+ * all blocks are freed).
+ */
+void amx_poolfree(void *block)
+{
+  ARENA *hdr,*hdr2;
+  unsigned sz;
+
+  assert(pool_base!=NULL);
+  assert(pool_size>sizeof(ARENA));
+
+  /* special case: if "block" is NULL, create a single free space */
+  if (block==NULL) {
+    /* store an arena header at the start of the pool */
+    hdr=(ARENA*)pool_base;
+    hdr->blocksize=pool_size-sizeof(ARENA);
+    hdr->index=-1;
+    hdr->lru=0;
+  } else {
+    hdr=(ARENA*)((char*)block-sizeof(ARENA));
+    assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
+    assert(hdr->blocksize<pool_size);
+
+    /* free this block */
+    hdr->index=-1;
+
+    /* try to coalesce with the next block */
+    hdr2=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
+    if (hdr2->index==-1)
+      hdr->blocksize+=hdr2->blocksize+sizeof(ARENA);
+
+    /* try to coalesce with the previous block */
+    if ((void*)hdr!=pool_base) {
+      sz=pool_size;
+      hdr2=(ARENA*)pool_base;
+      while (sz>0 && (char*)hdr2+hdr2->blocksize+sizeof(ARENA)!=(char*)hdr) {
+        assert(sz<=pool_size);
+        sz-=hdr2->blocksize+sizeof(ARENA);
+        hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA));
+      } /* while */
+      assert((char*)hdr2+hdr2->blocksize+sizeof(ARENA)==(char*)hdr);
+      if (hdr2->index==-1)
+        hdr2->blocksize+=hdr->blocksize+sizeof(ARENA);
+    } /* if */
+  } /* if */
+}
+
+/* amx_poolalloc() allocates the requested number of bytes from the pool and
+ * returns a header to the start of it. Every block in the pool is prefixed
+ * with an "arena header"; the return value of this function points just
+ * behind this arena header.
+ *
+ * The block with the specified "index" should not already exist in the pool.
+ * In other words, parameter "index" should be unique for every of memory block,
+ * and the block should not change in size. Use amx_poolfind() to verify whether
+ * a block is already in the pool (and optionally amx_poolfree() to remove it).
+ *
+ * If no block of sufficient size is available, the routine frees blocks until
+ * the requested amount of memory can be allocated. There is no intelligent
+ * algorithm involved: the routine just frees the least-recently used block at
+ * every iteration (without considering the size of the block or whether that
+ * block is adjacent to a free block).
+ */
+void *amx_poolalloc(unsigned size,int index)
+{
+  ARENA *hdr,*hdrlru;
+  unsigned sz;
+  unsigned short minlru;
+
+  assert(size>0);
+  assert(index>=0 && index<=SHRT_MAX);
+  assert(findblock(index)==NULL);
+
+  /* align the size to a cell boundary */
+  if ((size % sizeof(cell))!=0)
+    size+=sizeof(cell)-(size % sizeof(cell));
+  if (size+sizeof(ARENA)>pool_size)
+    return NULL;  /* requested block does not fit in the pool */
+
+  /* find a block large enough to get the size plus an arena header; at
+   * the same time, detect the block with the lowest LRU
+   * if no block of sufficient size can be found, the routine then frees
+   * the block with the lowest LRU count and tries again
+   */
+  do {
+    sz=pool_size;
+    hdr=(ARENA*)pool_base;
+    hdrlru=hdr;
+    minlru=USHRT_MAX;
+    while (sz>0) {
+      assert(sz<=pool_size);
+      assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
+      if (hdr->index==-1 && hdr->blocksize>=size)
+        break;
+      if (hdr->index!=-1 && hdr->lru<minlru) {
+        minlru=hdr->lru;
+        hdrlru=hdr;
+      } /* if */
+      sz-=hdr->blocksize+sizeof(ARENA);
+      hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
+    } /* while */
+    assert(sz<=pool_size);
+    if (sz==0) {
+      /* free up memory and try again */
+      assert(hdrlru->index!=-1);
+      amx_poolfree((char*)hdrlru+sizeof(ARENA));
+    } /* if */
+  } while (sz==0);
+
+  /* see whether to allocate the entire free block, or to cut it in two blocks */
+  if (hdr->blocksize>size+MIN_BLOCKSIZE+sizeof(ARENA)) {
+    /* cut the block in two */
+    ARENA *next=(ARENA*)((char*)hdr+size+sizeof(ARENA));
+    next->blocksize=hdr->blocksize-size-sizeof(ARENA);
+    next->index=-1;
+    next->lru=0;
+  } else {
+    size=hdr->blocksize;
+  } /* if */
+  hdr->blocksize=size;
+  hdr->index=(short)index;
+  touchblock(hdr);    /* set LRU field */
+
+  return (void*)((char*)hdr+sizeof(ARENA));
+}
+
+/* amx_poolfind() returns the address of the memory block with the given index,
+ * or NULL if no such block exists. Parameter "index" should not be -1, because
+ * -1 represents a free block (actually, only positive values are valid).
+ * When amx_poolfind() finds the block, it increments its LRU count.
+ */
+void *amx_poolfind(int index)
+{
+  ARENA *hdr=findblock(index);
+  if (hdr==NULL)
+    return NULL;
+  touchblock(hdr);
+  return (void*)((char*)hdr+sizeof(ARENA));
+}
+
+int amx_poolprotect(int index)
+{
+  ARENA *hdr=findblock(index);
+  if (hdr==NULL)
+    return AMX_ERR_GENERAL;
+  hdr->lru=PROTECT_LRU;
+  return AMX_ERR_NONE;
+}
+
+static ARENA *findblock(int index)
+{
+  ARENA *hdr;
+  unsigned sz;
+
+  assert(index>=0);
+  sz=pool_size;
+  hdr=(ARENA*)pool_base;
+  while (sz>0 && hdr->index!=index) {
+    assert(sz<=pool_size);
+    assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size);
+    sz-=hdr->blocksize+sizeof(ARENA);
+    hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA));
+  } /* while */
+  assert(sz<=pool_size);
+  return (sz>0 && hdr->index==index) ? hdr : NULL;
+}
+
+static void touchblock(ARENA *hdr)
+{
+  assert(hdr!=NULL);
+  if (++pool_lru >= PROTECT_LRU)
+    pool_lru=0;
+  hdr->lru=pool_lru;
+
+  /* special case: if the overlay LRU count wrapped back to zero, set the
+   * LRU count of all blocks to zero, but set the count of the block just
+   * touched to 1 (skip blocks marked as protected, too)
+   */
+  if (pool_lru==0) {
+    ARENA *hdr2;
+    unsigned sz=pool_size;
+    hdr2=(ARENA*)pool_base;
+    while (sz>0) {
+      assert(sz<=pool_size);
+      if (hdr2->lru!=PROTECT_LRU)
+        hdr2->lru=0;
+      sz-=hdr2->blocksize+sizeof(ARENA);
+      hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA));
+    } /* while */
+    assert(sz==0);
+    hdr->lru=++pool_lru;
+  } /* if */
+}