mempool.c 5.89 KB
Newer Older
1 2 3
/*
 *	BIRD Resource Manager -- Memory Pools
 *
4
 *	(c) 1998--2000 Martin Mares <mj@ucw.cz>
5 6 7 8
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

9 10 11 12 13 14 15 16 17 18 19 20
/**
 * DOC: Linear memory pools
 *
 * Linear memory pools are collections of memory blocks which
 * support very fast allocation of new blocks, but are able to free only
 * the whole collection at once.
 *
 * Example: Each configuration is described by a complex system of structures,
 * linked lists and function trees which are all allocated from a single linear
 * pool, thus they can be freed at once when the configuration is no longer used.
 */

21
#include <stdlib.h>
22
#include <stdint.h>
23 24 25

#include "nest/bird.h"
#include "lib/resource.h"
26
#include "lib/string.h"
27

28 29
struct lp_chunk {
  struct lp_chunk *next;
Pavel Tvrdík's avatar
Pavel Tvrdík committed
30
  uint size;
31
  uintptr_t data_align[0];
32 33 34
  byte data[0];
};

35
struct linpool {
36 37
  resource r;
  byte *ptr, *end;
38 39
  struct lp_chunk *first, *current, **plast;	/* Normal (reusable) chunks */
  struct lp_chunk *first_large;			/* Large chunks */
Pavel Tvrdík's avatar
Pavel Tvrdík committed
40
  uint chunk_size, threshold, total, total_large;
41 42
};

43 44 45
static void lp_free(resource *);
static void lp_dump(resource *);
static resource *lp_lookup(resource *, unsigned long);
46
static size_t lp_memsize(resource *r);
47

48 49 50 51
static struct resclass lp_class = {
  "LinPool",
  sizeof(struct linpool),
  lp_free,
52
  lp_dump,
53 54
  lp_lookup,
  lp_memsize
55 56
};

57 58 59 60 61 62 63 64 65
/**
 * lp_new - create a new linear memory pool
 * @p: pool
 * @blk: block size
 *
 * lp_new() creates a new linear memory pool resource inside the pool @p.
 * The linear pool consists of a list of memory chunks of size at least
 * @blk.
 */
66
linpool
Pavel Tvrdík's avatar
Pavel Tvrdík committed
67
*lp_new(pool *p, uint blk)
68
{
69
  linpool *m = ralloc(p, &lp_class);
70 71 72 73 74 75
  m->plast = &m->first;
  m->chunk_size = blk;
  m->threshold = 3*blk/4;
  return m;
}

76 77 78 79 80 81 82 83 84 85 86 87 88 89
/**
 * lp_alloc - allocate memory from a &linpool
 * @m: linear memory pool
 * @size: amount of memory
 *
 * lp_alloc() allocates @size bytes of memory from a &linpool @m
 * and it returns a pointer to the allocated memory.
 *
 * It works by trying to find free space in the last memory chunk
 * associated with the &linpool and creating a new chunk of the standard
 * size (as specified during lp_new()) if the free space is too small
 * to satisfy the allocation. If @size is too large to fit in a standard
 * size chunk, an "overflow" chunk is created for it instead.
 */
90
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
91
lp_alloc(linpool *m, uint size)
92
{
Ondřej Filip's avatar
Ondřej Filip committed
93
  byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
94 95 96 97 98 99 100 101 102
  byte *e = a + size;

  if (e <= m->end)
    {
      m->ptr = e;
      return a;
    }
  else
    {
103
      struct lp_chunk *c;
104 105
      if (size >= m->threshold)
	{
106
	  /* Too large => allocate large chunk */
107
	  c = xmalloc(sizeof(struct lp_chunk) + size);
108 109
	  m->total_large += size;
	  c->next = m->first_large;
110
	  m->first_large = c;
111
	  c->size = size;
112 113 114
	}
      else
	{
115 116 117 118 119 120
	  if (m->current)
	    {
	      /* Still have free chunks from previous incarnation (before lp_flush()) */
	      c = m->current;
	      m->current = c->next;
	    }
121 122 123 124 125 126 127 128
	  else
	    {
	      /* Need to allocate a new chunk */
	      c = xmalloc(sizeof(struct lp_chunk) + m->chunk_size);
	      m->total += m->chunk_size;
	      *m->plast = c;
	      m->plast = &c->next;
	      c->next = NULL;
129
	      c->size = m->chunk_size;
130
	    }
131 132 133 134 135 136 137
	  m->ptr = c->data + size;
	  m->end = c->data + m->chunk_size;
	}
      return c->data;
    }
}

138 139 140 141 142 143 144 145 146 147
/**
 * lp_allocu - allocate unaligned memory from a &linpool
 * @m: linear memory pool
 * @size: amount of memory
 *
 * lp_allocu() allocates @size bytes of memory from a &linpool @m
 * and it returns a pointer to the allocated memory. It doesn't
 * attempt to align the memory block, giving a very efficient way
 * how to allocate strings without any space overhead.
 */
148
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
149
lp_allocu(linpool *m, uint size)
150 151 152 153 154 155 156 157 158
{
  byte *a = m->ptr;
  byte *e = a + size;

  if (e <= m->end)
    {
      m->ptr = e;
      return a;
    }
159
  return lp_alloc(m, size);
160 161
}

162 163 164 165 166 167 168 169
/**
 * lp_allocz - allocate cleared memory from a &linpool
 * @m: linear memory pool
 * @size: amount of memory
 *
 * This function is identical to lp_alloc() except that it
 * clears the allocated memory block.
 */
170
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
171
lp_allocz(linpool *m, uint size)
172
{
173
  void *z = lp_alloc(m, size);
174 175 176 177 178

  bzero(z, size);
  return z;
}

179 180 181 182 183 184 185
/**
 * lp_flush - flush a linear memory pool
 * @m: linear memory pool
 *
 * This function frees the whole contents of the given &linpool @m,
 * but leaves the pool itself.
 */
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
void
lp_flush(linpool *m)
{
  struct lp_chunk *c;

  /* Relink all normal chunks to free list and free all large chunks */
  m->ptr = m->end = NULL;
  m->current = m->first;
  while (c = m->first_large)
    {
      m->first_large = c->next;
      xfree(c);
    }
  m->total_large = 0;
}

202
static void
203
lp_free(resource *r)
204
{
205 206
  linpool *m = (linpool *) r;
  struct lp_chunk *c, *d;
207 208 209 210 211 212

  for(d=m->first; d; d = c)
    {
      c = d->next;
      xfree(d);
    }
213 214 215 216 217
  for(d=m->first_large; d; d = c)
    {
      c = d->next;
      xfree(d);
    }
218 219
}

220
static void
221
lp_dump(resource *r)
222
{
223 224
  linpool *m = (linpool *) r;
  struct lp_chunk *c;
225
  int cnt, cntl;
226 227 228

  for(cnt=0, c=m->first; c; c=c->next, cnt++)
    ;
229 230 231
  for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
    ;
  debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
232 233 234
	m->chunk_size,
	m->threshold,
	cnt,
235 236 237
	cntl,
	m->total,
	m->total_large);
238
}
239

240 241 242 243 244 245 246 247 248 249 250 251 252
static size_t
lp_memsize(resource *r)
{
  linpool *m = (linpool *) r;
  struct lp_chunk *c;
  int cnt = 0;

  for(c=m->first; c; c=c->next)
    cnt++;
  for(c=m->first_large; c; c=c->next)
    cnt++;

  return ALLOC_OVERHEAD + sizeof(struct linpool) +
253
    cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
254 255 256 257
    m->total + m->total_large;
}


258 259 260 261 262 263 264 265 266 267 268 269 270 271
static resource *
lp_lookup(resource *r, unsigned long a)
{
  linpool *m = (linpool *) r;
  struct lp_chunk *c;

  for(c=m->first; c; c=c->next)
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
      return r;
  for(c=m->first_large; c; c=c->next)
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
      return r;
  return NULL;
}