*
* 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.
+ * the whole collection at once (or in stack order).
*
* Example: Each configuration is described by a complex system of structures,
* linked lists and function trees which are all allocated from a single linear
*/
#include <stdlib.h>
+#include <stdint.h>
#include "nest/bird.h"
#include "lib/resource.h"
struct lp_chunk {
struct lp_chunk *next;
- unsigned int size;
+ uintptr_t data_align[0];
byte data[0];
};
+#define LP_DATA_SIZE (page_size - OFFSETOF(struct lp_chunk, data))
+
struct linpool {
resource r;
byte *ptr, *end;
- struct lp_chunk *first, *current, **plast; /* Normal (reusable) chunks */
+ struct lp_chunk *first, *current; /* Normal (reusable) chunks */
struct lp_chunk *first_large; /* Large chunks */
- unsigned chunk_size, threshold, total, total_large;
+ uint total, total_large;
};
+_Thread_local linpool *tmp_linpool;
+
static void lp_free(resource *);
static void lp_dump(resource *);
static resource *lp_lookup(resource *, unsigned long);
+static struct resmem lp_memsize(resource *r);
static struct resclass lp_class = {
"LinPool",
sizeof(struct linpool),
lp_free,
lp_dump,
- lp_lookup
+ lp_lookup,
+ lp_memsize
};
/**
* 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.
+ * The linear pool consists of a list of memory chunks of page size.
*/
linpool
-*lp_new(pool *p, unsigned blk)
+*lp_new(pool *p)
{
- linpool *m = ralloc(p, &lp_class);
- m->ptr = m->end = NULL;
- m->first = m->current = NULL;
- m->plast = &m->first;
- m->first_large = NULL;
- m->chunk_size = blk;
- m->threshold = 3*blk/4;
- m->total = m->total_large = 0;
- return m;
+ return ralloc(p, &lp_class);
}
/**
* size chunk, an "overflow" chunk is created for it instead.
*/
void *
-lp_alloc(linpool *m, unsigned size)
+lp_alloc(linpool *m, uint size)
{
- byte *a = (byte *) ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
+ byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
byte *e = a + size;
if (e <= m->end)
else
{
struct lp_chunk *c;
- if (size >= m->threshold)
+ if (size > LP_DATA_SIZE)
{
/* Too large => allocate large chunk */
c = xmalloc(sizeof(struct lp_chunk) + size);
m->total_large += size;
c->next = m->first_large;
- m->first_large = c->next;
- c->size = size;
+ m->first_large = c;
}
else
{
- if (m->current)
+ if (m->current && m->current->next)
{
/* Still have free chunks from previous incarnation (before lp_flush()) */
- c = m->current;
- m->current = c->next;
+ c = m->current->next;
}
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 = alloc_page();
+
+ m->total += LP_DATA_SIZE;
c->next = NULL;
- c->size = m->chunk_size;
+
+ if (m->current)
+ m->current->next = c;
+ else
+ m->first = c;
}
+ m->current = c;
m->ptr = c->data + size;
- m->end = c->data + m->chunk_size;
+ m->end = c->data + LP_DATA_SIZE;
}
return c->data;
}
* how to allocate strings without any space overhead.
*/
void *
-lp_allocu(linpool *m, unsigned size)
+lp_allocu(linpool *m, uint size)
{
byte *a = m->ptr;
byte *e = a + size;
* clears the allocated memory block.
*/
void *
-lp_allocz(linpool *m, unsigned size)
+lp_allocz(linpool *m, uint size)
{
void *z = lp_alloc(m, size);
{
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;
+ /* Move ptr to the first chunk and free all other chunks */
+ m->current = c = m->first;
+ m->ptr = c ? c->data : NULL;
+ m->end = c ? c->data + LP_DATA_SIZE : NULL;
+
+ while (c && c->next)
+ {
+ struct lp_chunk *d = c->next;
+ c->next = d->next;
+ free_page(d);
+ }
+
while (c = m->first_large)
{
m->first_large = c->next;
m->total_large = 0;
}
+/**
+ * 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->total_large = m->total_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->first;
+ m->ptr = p->ptr ?: (c ? c->data : NULL);
+ m->end = c ? (c->data + LP_DATA_SIZE) : NULL;
+ m->total_large = p->total_large;
+
+ while ((c = m->first_large) && (c != p->large))
+ {
+ m->first_large = c->next;
+ xfree(c);
+ }
+}
+
static void
lp_free(resource *r)
{
for(d=m->first; d; d = c)
{
c = d->next;
- xfree(d);
+ free_page(d);
}
for(d=m->first_large; d; d = c)
{
;
for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
;
- debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
- m->chunk_size,
- m->threshold,
+ debug("(count=%d+%d total=%d+%d)\n",
cnt,
cntl,
m->total,
m->total_large);
}
+static struct resmem
+lp_memsize(resource *r)
+{
+ linpool *m = (linpool *) r;
+ struct resmem sz = {
+ .overhead = sizeof(struct linpool) + ALLOC_OVERHEAD,
+ .effective = m->total_large,
+ };
+
+ for (struct lp_chunk *c = m->first_large; c; c = c->next)
+ sz.overhead += sizeof(struct lp_chunk) + ALLOC_OVERHEAD;
+
+ uint regular = 0;
+ for (struct lp_chunk *c = m->first; c; c = c->next)
+ regular++;
+
+ sz.effective += LP_DATA_SIZE * regular;
+ sz.overhead += (sizeof(struct lp_chunk) + ALLOC_OVERHEAD) * regular;
+
+ return sz;
+}
+
+
static resource *
lp_lookup(resource *r, unsigned long a)
{
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)
+ if ((unsigned long) c->data <= a && (unsigned long) c->data + LP_DATA_SIZE > a)
return r;
return NULL;
}
projects / thirdparty / bird.git / blobdiff