Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / mempool.c @ 6b3f1a54

History | View | Annotate | Download (7.12 KB)

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

    
9
/**
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 (or in stack order).
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
#include <stdlib.h>
22
#include <stdint.h>
23

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

    
28
struct lp_chunk {
29
  struct lp_chunk *next;
30
  uint size;
31
  uintptr_t data_align[0];
32
  byte data[0];
33
};
34

    
35
const int lp_chunk_size = sizeof(struct lp_chunk);
36

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

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

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

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

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

    
97
  if (e <= m->end)
98
    {
99
      m->ptr = e;
100
      return a;
101
    }
102
  else
103
    {
104
      struct lp_chunk *c;
105
      if (size >= m->threshold)
106
        {
107
          /* Too large => allocate large chunk */
108
          c = xmalloc(sizeof(struct lp_chunk) + size);
109
          m->total_large += size;
110
          c->next = m->first_large;
111
          m->first_large = c;
112
          c->size = size;
113
        }
114
      else
115
        {
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
          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
              c->next = NULL;
127
              c->size = m->chunk_size;
128

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

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

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

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

    
179
  bzero(z, size);
180
  return z;
181
}
182

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

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

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

    
208
/**
209
 * lp_save - save the state of a linear memory pool
210
 * @m: linear memory pool
211
 * @p: state buffer
212
 *
213
 * This function saves the state of a linear memory pool. Saved state can be
214
 * used later to restore the pool (to free memory allocated since).
215
 */
216
void
217
lp_save(linpool *m, lp_state *p)
218
{
219
  p->current = m->current;
220
  p->large = m->first_large;
221
  p->ptr = m->ptr;
222
}
223

    
224
/**
225
 * lp_restore - restore the state of a linear memory pool
226
 * @m: linear memory pool
227
 * @p: saved state
228
 *
229
 * This function restores the state of a linear memory pool, freeing all memory
230
 * allocated since the state was saved. Note that the function cannot un-free
231
 * the memory, therefore the function also invalidates other states that were
232
 * saved between (on the same pool).
233
 */
234
void
235
lp_restore(linpool *m, lp_state *p)
236
{
237
  struct lp_chunk *c;
238

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

    
244
  while ((c = m->first_large) && (c != p->large))
245
    {
246
      m->first_large = c->next;
247
      m->total_large -= c->size;
248
      xfree(c);
249
    }
250
}
251

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

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

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

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

    
290
static size_t
291
lp_memsize(resource *r)
292
{
293
  linpool *m = (linpool *) r;
294
  struct lp_chunk *c;
295
  int cnt = 0;
296

    
297
  for(c=m->first; c; c=c->next)
298
    cnt++;
299
  for(c=m->first_large; c; c=c->next)
300
    cnt++;
301

    
302
  return ALLOC_OVERHEAD + sizeof(struct linpool) +
303
    cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
304
    m->total + m->total_large;
305
}
306

    
307

    
308
static resource *
309
lp_lookup(resource *r, unsigned long a)
310
{
311
  linpool *m = (linpool *) r;
312
  struct lp_chunk *c;
313

    
314
  for(c=m->first; c; c=c->next)
315
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
316
      return r;
317
  for(c=m->first_large; c; c=c->next)
318
    if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
319
      return r;
320
  return NULL;
321
}