mempool.c 7.12 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
/**
 * 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
14
 * the whole collection at once (or in stack order).
15 16 17 18 19 20
 *
 * 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 36
const int lp_chunk_size = sizeof(struct lp_chunk);

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

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

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

59 60 61 62 63 64 65 66 67
/**
 * 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.
 */
68
linpool
Pavel Tvrdík's avatar
Pavel Tvrdík committed
69
*lp_new(pool *p, uint blk)
70
{
71
  linpool *m = ralloc(p, &lp_class);
72 73 74 75 76
  m->chunk_size = blk;
  m->threshold = 3*blk/4;
  return m;
}

77 78 79 80 81 82 83 84 85 86 87 88 89 90
/**
 * 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.
 */
91
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
92
lp_alloc(linpool *m, uint size)
93
{
Ondřej Filip's avatar
Ondřej Filip committed
94
  byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
95 96 97 98 99 100 101 102 103
  byte *e = a + size;

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

	      if (m->current)
		m->current->next = c;
	      else
		m->first = c;
133
	    }
134
	  m->current = c;
135 136 137 138 139 140 141
	  m->ptr = c->data + size;
	  m->end = c->data + m->chunk_size;
	}
      return c->data;
    }
}

142 143 144 145 146 147 148 149 150 151
/**
 * 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.
 */
152
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
153
lp_allocu(linpool *m, uint size)
154 155 156 157 158 159 160 161 162
{
  byte *a = m->ptr;
  byte *e = a + size;

  if (e <= m->end)
    {
      m->ptr = e;
      return a;
    }
163
  return lp_alloc(m, size);
164 165
}

166 167 168 169 170 171 172 173
/**
 * 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.
 */
174
void *
Pavel Tvrdík's avatar
Pavel Tvrdík committed
175
lp_allocz(linpool *m, uint size)
176
{
177
  void *z = lp_alloc(m, size);
178 179 180 181 182

  bzero(z, size);
  return z;
}

183 184 185 186 187 188 189
/**
 * 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.
 */
190 191 192 193 194
void
lp_flush(linpool *m)
{
  struct lp_chunk *c;

195 196 197 198 199
  /* Move ptr to the first chunk and free all large chunks */
  m->current = c = m->first;
  m->ptr = c ? c->data : NULL;
  m->end = c ? c->data + m->chunk_size : NULL;

200 201 202 203 204 205 206 207
  while (c = m->first_large)
    {
      m->first_large = c->next;
      xfree(c);
    }
  m->total_large = 0;
}

208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
/**
 * lp_save - save the state of a linear memory pool
 * @m: linear memory pool
 * @p: state buffer
 *
 * This function saves the state of a linear memory pool. Saved state can be
 * used later to restore the pool (to free memory allocated since).
 */
void
lp_save(linpool *m, lp_state *p)
{
  p->current = m->current;
  p->large = m->first_large;
  p->ptr = m->ptr;
}

/**
 * lp_restore - restore the state of a linear memory pool
 * @m: linear memory pool
 * @p: saved state
 *
 * This function restores the state of a linear memory pool, freeing all memory
 * allocated since the state was saved. Note that the function cannot un-free
 * the memory, therefore the function also invalidates other states that were
 * saved between (on the same pool).
 */
void
lp_restore(linpool *m, lp_state *p)
{
  struct lp_chunk *c;

  /* Move ptr to the saved pos and free all newer large chunks */
  m->current = c = p->current;
  m->ptr = p->ptr;
  m->end = c ? c->data + m->chunk_size : NULL;

  while ((c = m->first_large) && (c != p->large))
    {
      m->first_large = c->next;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
247
      m->total_large -= c->size;
248 249 250 251
      xfree(c);
    }
}

252
static void
253
lp_free(resource *r)
254
{
255 256
  linpool *m = (linpool *) r;
  struct lp_chunk *c, *d;
257 258 259 260 261 262

  for(d=m->first; d; d = c)
    {
      c = d->next;
      xfree(d);
    }
263 264 265 266 267
  for(d=m->first_large; d; d = c)
    {
      c = d->next;
      xfree(d);
    }
268 269
}

270
static void
271
lp_dump(resource *r)
272
{
273 274
  linpool *m = (linpool *) r;
  struct lp_chunk *c;
275
  int cnt, cntl;
276 277 278

  for(cnt=0, c=m->first; c; c=c->next, cnt++)
    ;
279 280 281
  for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
    ;
  debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
282 283 284
	m->chunk_size,
	m->threshold,
	cnt,
285 286 287
	cntl,
	m->total,
	m->total_large);
288
}
289

290 291 292 293 294 295 296 297 298 299 300 301 302
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) +
303
    cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
304 305 306 307
    m->total + m->total_large;
}


308 309 310 311 312 313 314 315 316 317 318 319 320 321
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;
}