Statistics
| Branch: | Revision:

iof-bird-daemon / lib / mempool.c @ 5cc1e1f8

History | View | Annotate | Download (5.6 KB)

1 18c8241a Martin Mares
/*
2
 *        BIRD Resource Manager -- Memory Pools
3
 *
4 5cc1e1f8 Martin Mares
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5 18c8241a Martin Mares
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8
9 5cc1e1f8 Martin Mares
/**
10
 * DOC: Linear memory pools
11
 *
12
 * Linear memory pools are collections of memory blocks which
13
 * support very fast allocation of new blocks, but are able to free only
14
 * the whole collection at once.
15
 *
16
 * Example: Each configuration is described by a complex system of structures,
17
 * linked lists and function trees which are all allocated from a single linear
18
 * pool, thus they can be freed at once when the configuration is no longer used.
19
 */
20
21 18c8241a Martin Mares
#include <stdlib.h>
22
23
#include "nest/bird.h"
24
#include "lib/resource.h"
25 221135d6 Martin Mares
#include "lib/string.h"
26 18c8241a Martin Mares
27 b35d72ac Martin Mares
struct lp_chunk {
28
  struct lp_chunk *next;
29 c9763428 Martin Mares
  unsigned int size;
30 18c8241a Martin Mares
  byte data[0];
31
};
32
33 b35d72ac Martin Mares
struct linpool {
34 18c8241a Martin Mares
  resource r;
35
  byte *ptr, *end;
36 f5c687f7 Martin Mares
  struct lp_chunk *first, *current, **plast;        /* Normal (reusable) chunks */
37
  struct lp_chunk *first_large;                        /* Large chunks */
38
  unsigned chunk_size, threshold, total, total_large;
39 18c8241a Martin Mares
};
40
41 c9763428 Martin Mares
static void lp_free(resource *);
42
static void lp_dump(resource *);
43
static resource *lp_lookup(resource *, unsigned long);
44 18c8241a Martin Mares
45 b35d72ac Martin Mares
static struct resclass lp_class = {
46
  "LinPool",
47
  sizeof(struct linpool),
48
  lp_free,
49 c9763428 Martin Mares
  lp_dump,
50
  lp_lookup
51 18c8241a Martin Mares
};
52
53 5cc1e1f8 Martin Mares
/**
54
 * lp_new - create a new linear memory pool
55
 * @p: pool
56
 * @blk: block size
57
 *
58
 * lp_new() creates a new linear memory pool resource inside the pool @p.
59
 * The linear pool consists of a list of memory chunks of size at least
60
 * @blk.
61
 */
62 b35d72ac Martin Mares
linpool
63
*lp_new(pool *p, unsigned blk)
64 18c8241a Martin Mares
{
65 b35d72ac Martin Mares
  linpool *m = ralloc(p, &lp_class);
66 18c8241a Martin Mares
  m->ptr = m->end = NULL;
67 f5c687f7 Martin Mares
  m->first = m->current = NULL;
68 18c8241a Martin Mares
  m->plast = &m->first;
69 f5c687f7 Martin Mares
  m->first_large = NULL;
70 18c8241a Martin Mares
  m->chunk_size = blk;
71
  m->threshold = 3*blk/4;
72 f5c687f7 Martin Mares
  m->total = m->total_large = 0;
73 18c8241a Martin Mares
  return m;
74
}
75
76 5cc1e1f8 Martin Mares
/**
77
 * lp_alloc - allocate memory from a &linpool
78
 * @m: linear memory pool
79
 * @size: amount of memory
80
 *
81
 * lp_alloc() allocates @size bytes of memory from a &linpool @m
82
 * and it returns a pointer to the allocated memory.
83
 *
84
 * It works by trying to find free space in the last memory chunk
85
 * associated with the &linpool and creating a new chunk of the standard
86
 * size (as specified during lp_new()) if the free space is too small
87
 * to satisfy the allocation. If @size is too large to fit in a standard
88
 * size chunk, an "overflow" chunk is created for it instead.
89
 */
90 18c8241a Martin Mares
void *
91 b35d72ac Martin Mares
lp_alloc(linpool *m, unsigned size)
92 18c8241a Martin Mares
{
93
  byte *a = (byte *) ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
94
  byte *e = a + size;
95
96
  if (e <= m->end)
97
    {
98
      m->ptr = e;
99
      return a;
100
    }
101
  else
102
    {
103 b35d72ac Martin Mares
      struct lp_chunk *c;
104 18c8241a Martin Mares
      if (size >= m->threshold)
105
        {
106 f5c687f7 Martin Mares
          /* Too large => allocate large chunk */
107 b35d72ac Martin Mares
          c = xmalloc(sizeof(struct lp_chunk) + size);
108 f5c687f7 Martin Mares
          m->total_large += size;
109
          c->next = m->first_large;
110
          m->first_large = c->next;
111 c9763428 Martin Mares
          c->size = size;
112 18c8241a Martin Mares
        }
113
      else
114
        {
115 92af6f30 Martin Mares
          if (m->current)
116
            {
117
              /* Still have free chunks from previous incarnation (before lp_flush()) */
118
              c = m->current;
119
              m->current = c->next;
120
            }
121 f5c687f7 Martin Mares
          else
122
            {
123
              /* Need to allocate a new chunk */
124
              c = xmalloc(sizeof(struct lp_chunk) + m->chunk_size);
125
              m->total += m->chunk_size;
126
              *m->plast = c;
127
              m->plast = &c->next;
128
              c->next = NULL;
129 c9763428 Martin Mares
              c->size = m->chunk_size;
130 f5c687f7 Martin Mares
            }
131 18c8241a Martin Mares
          m->ptr = c->data + size;
132
          m->end = c->data + m->chunk_size;
133
        }
134
      return c->data;
135
    }
136
}
137
138 5cc1e1f8 Martin Mares
/**
139
 * lp_allocu - allocate unaligned memory from a &linpool
140
 * @m: linear memory pool
141
 * @size: amount of memory
142
 *
143
 * lp_allocu() allocates @size bytes of memory from a &linpool @m
144
 * and it returns a pointer to the allocated memory. It doesn't
145
 * attempt to align the memory block, giving a very efficient way
146
 * how to allocate strings without any space overhead.
147
 */
148 18c8241a Martin Mares
void *
149 b35d72ac Martin Mares
lp_allocu(linpool *m, unsigned size)
150 18c8241a Martin Mares
{
151
  byte *a = m->ptr;
152
  byte *e = a + size;
153
154
  if (e <= m->end)
155
    {
156
      m->ptr = e;
157
      return a;
158
    }
159 b35d72ac Martin Mares
  return lp_alloc(m, size);
160 18c8241a Martin Mares
}
161
162 5cc1e1f8 Martin Mares
/**
163
 * lp_allocz - allocate cleared memory from a &linpool
164
 * @m: linear memory pool
165
 * @size: amount of memory
166
 *
167
 * This function is identical to lp_alloc() except that it
168
 * clears the allocated memory block.
169
 */
170 18c8241a Martin Mares
void *
171 b35d72ac Martin Mares
lp_allocz(linpool *m, unsigned size)
172 18c8241a Martin Mares
{
173 b35d72ac Martin Mares
  void *z = lp_alloc(m, size);
174 18c8241a Martin Mares
175
  bzero(z, size);
176
  return z;
177
}
178
179 5cc1e1f8 Martin Mares
/**
180
 * lp_flush - flush a linear memory pool
181
 * @m: linear memory pool
182
 *
183
 * This function frees the whole contents of the given &linpool @m,
184
 * but leaves the pool itself.
185
 */
186 18c8241a Martin Mares
void
187 f5c687f7 Martin Mares
lp_flush(linpool *m)
188
{
189
  struct lp_chunk *c;
190
191
  /* Relink all normal chunks to free list and free all large chunks */
192
  m->ptr = m->end = NULL;
193
  m->current = m->first;
194
  while (c = m->first_large)
195
    {
196
      m->first_large = c->next;
197
      xfree(c);
198
    }
199
  m->total_large = 0;
200
}
201
202 c9763428 Martin Mares
static void
203 b35d72ac Martin Mares
lp_free(resource *r)
204 18c8241a Martin Mares
{
205 b35d72ac Martin Mares
  linpool *m = (linpool *) r;
206
  struct lp_chunk *c, *d;
207 18c8241a Martin Mares
208
  for(d=m->first; d; d = c)
209
    {
210
      c = d->next;
211
      xfree(d);
212
    }
213 507cb9e5 Martin Mares
  for(d=m->first_large; d; d = c)
214
    {
215
      c = d->next;
216
      xfree(d);
217
    }
218 18c8241a Martin Mares
}
219
220 c9763428 Martin Mares
static void
221 b35d72ac Martin Mares
lp_dump(resource *r)
222 18c8241a Martin Mares
{
223 b35d72ac Martin Mares
  linpool *m = (linpool *) r;
224
  struct lp_chunk *c;
225 5bc512aa Martin Mares
  int cnt, cntl;
226 18c8241a Martin Mares
227
  for(cnt=0, c=m->first; c; c=c->next, cnt++)
228
    ;
229 5bc512aa Martin Mares
  for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
230
    ;
231
  debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
232 18c8241a Martin Mares
        m->chunk_size,
233
        m->threshold,
234
        cnt,
235 5bc512aa Martin Mares
        cntl,
236
        m->total,
237
        m->total_large);
238 18c8241a Martin Mares
}
239 c9763428 Martin Mares
240
static resource *
241
lp_lookup(resource *r, unsigned long a)
242
{
243
  linpool *m = (linpool *) r;
244
  struct lp_chunk *c;
245
246
  for(c=m->first; c; c=c->next)
247
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
248
      return r;
249
  for(c=m->first_large; c; c=c->next)
250
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
251
      return r;
252
  return NULL;
253
}