Back to index

tor  0.2.3.18-rc
Classes | Defines | Typedefs | Functions | Variables
memarea.c File Reference

Implementation for memarea_t, an allocator for allocating lots of small objects that will be freed all at once. More...

#include "orconfig.h"
#include <stdlib.h>
#include "memarea.h"
#include "util.h"
#include "compat.h"
#include "torlog.h"

Go to the source code of this file.

Classes

struct  memarea_chunk_t
 Implements part of a memarea. More...
struct  memarea_t
 A memarea_t is an allocation region for a set of small memory requests that will all be freed at once. More...
union  memarea_chunk_t.u

Defines

#define USE_SENTINELS
 If true, we try to detect any attempts to write beyond the length of a memarea.
#define MEMAREA_ALIGN   SIZEOF_VOID_P
 All returned pointers should be aligned to the nearest multiple of this value.
#define SENTINEL_VAL   0x90806622u
 Magic value that we stick at the end of a memarea so we can make sure there are no run-off-the-end bugs.
#define SENTINEL_LEN   sizeof(uint32_t)
 How many bytes per area do we devote to the sentinel?
#define SET_SENTINEL(chunk)
 Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the end, set those bytes.
#define CHECK_SENTINEL(chunk)
 Assert that the sentinel on a memarea is set correctly.
#define CHUNK_HEADER_SIZE   STRUCT_OFFSET(memarea_chunk_t, u)
 How many bytes are needed for overhead before we get to the memory part of a chunk?
#define CHUNK_SIZE   4096
 What's the smallest that we'll allocate a chunk?
#define MAX_FREELIST_LEN   4
 How many chunks will we put into the freelist before freeing them?

Typedefs

typedef struct memarea_chunk_t memarea_chunk_t
 Implements part of a memarea.

Functions

static INLINE void * realign_pointer (void *ptr)
 Increment ptr until it is aligned to MEMAREA_ALIGN.
static memarea_chunk_talloc_chunk (size_t sz, int freelist_ok)
 Helper: allocate a new memarea chunk of around chunk_size bytes.
static void chunk_free_unchecked (memarea_chunk_t *chunk)
 Release chunk from a memarea, either by adding it to the freelist or by freeing it if the freelist is already too big.
memarea_tmemarea_new (void)
 Allocate and return new memarea.
void memarea_drop_all (memarea_t *area)
 Free area, invalidating all pointers returned from memarea_alloc() and friends for this area.
void memarea_clear (memarea_t *area)
 Forget about having allocated anything in area, and free some of the backing storage associated with it, as appropriate.
void memarea_clear_freelist (void)
 Remove all unused memarea chunks from the internal freelist.
int memarea_owns_ptr (const memarea_t *area, const void *p)
 Return true iff p is in a range that has been returned by an allocation from area.
void * memarea_alloc (memarea_t *area, size_t sz)
 Return a pointer to a chunk of memory in area of at least sz bytes.
void * memarea_alloc_zero (memarea_t *area, size_t sz)
 As memarea_alloc(), but clears the memory it returns.
void * memarea_memdup (memarea_t *area, const void *s, size_t n)
 As memdup, but returns the memory from area.
char * memarea_strdup (memarea_t *area, const char *s)
 As strdup, but returns the memory from area.
char * memarea_strndup (memarea_t *area, const char *s, size_t n)
 As strndup, but returns the memory from area.
void memarea_get_stats (memarea_t *area, size_t *allocated_out, size_t *used_out)
 Set allocated_out to the number of bytes allocated in area, and used_out to the number of bytes currently used.
void memarea_assert_ok (memarea_t *area)
 Assert that area is okay.

Variables

static int freelist_len = 0
 The number of memarea chunks currently in our freelist.
static memarea_chunk_tfreelist = NULL
 A linked list of unused memory area chunks.

Detailed Description

Implementation for memarea_t, an allocator for allocating lots of small objects that will be freed all at once.

Definition in file memarea.c.


Class Documentation

struct memarea_chunk_t

Implements part of a memarea.

New memory is carved off from chunk->mem in increasing order until a request is too big, at which point a new chunk is allocated.

Definition at line 71 of file memarea.c.

Collaboration diagram for memarea_chunk_t:
Class Members
size_t mem_size How much RAM is available in u.mem, total?
struct memarea_chunk_t * next_chunk Next chunk in this area. Only kept around so we can free it.
char * next_mem Next position in u.mem to allocate data at. If it's greater than or equal to mem+mem_size, this chunk is full.
union memarea_chunk_t u
struct memarea_t

A memarea_t is an allocation region for a set of small memory requests that will all be freed at once.

Definition at line 93 of file memarea.c.

Collaboration diagram for memarea_t:
Class Members
memarea_chunk_t * first Top of the chunk stack: never NULL.
union memarea_chunk_t.u

Definition at line 78 of file memarea.c.

Class Members
void * _void_for_alignment Dummy; used to make sure mem is aligned.
char mem Memory space in this chunk.

Define Documentation

#define CHECK_SENTINEL (   chunk)
Value:
STMT_BEGIN                                                            \
  uint32_t sent_val = get_uint32(&(chunk)->u.mem[chunk->mem_size]);     \
  tor_assert(sent_val == SENTINEL_VAL);                                 \
  STMT_END

Assert that the sentinel on a memarea is set correctly.

Definition at line 45 of file memarea.c.

How many bytes are needed for overhead before we get to the memory part of a chunk?

Definition at line 86 of file memarea.c.

#define CHUNK_SIZE   4096

What's the smallest that we'll allocate a chunk?

Definition at line 89 of file memarea.c.

#define MAX_FREELIST_LEN   4

How many chunks will we put into the freelist before freeing them?

Definition at line 98 of file memarea.c.

All returned pointers should be aligned to the nearest multiple of this value.

Definition at line 22 of file memarea.c.

#define SENTINEL_LEN   sizeof(uint32_t)

How many bytes per area do we devote to the sentinel?

Definition at line 37 of file memarea.c.

#define SENTINEL_VAL   0x90806622u

Magic value that we stick at the end of a memarea so we can make sure there are no run-off-the-end bugs.

Definition at line 35 of file memarea.c.

#define SET_SENTINEL (   chunk)
Value:
STMT_BEGIN                                                    \
  set_uint32( &(chunk)->u.mem[chunk->mem_size], SENTINEL_VAL ); \
  STMT_END

Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the end, set those bytes.

Definition at line 40 of file memarea.c.

#define USE_SENTINELS

If true, we try to detect any attempts to write beyond the length of a memarea.

Definition at line 18 of file memarea.c.


Typedef Documentation

Implements part of a memarea.

New memory is carved off from chunk->mem in increasing order until a request is too big, at which point a new chunk is allocated.


Function Documentation

static memarea_chunk_t* alloc_chunk ( size_t  sz,
int  freelist_ok 
) [static]

Helper: allocate a new memarea chunk of around chunk_size bytes.

Definition at line 107 of file memarea.c.

{
  tor_assert(sz < SIZE_T_CEILING);
  if (freelist && freelist_ok) {
    memarea_chunk_t *res = freelist;
    freelist = res->next_chunk;
    res->next_chunk = NULL;
    --freelist_len;
    CHECK_SENTINEL(res);
    return res;
  } else {
    size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
    memarea_chunk_t *res;
    chunk_size += SENTINEL_LEN;
    res = tor_malloc_roundup(&chunk_size);
    res->next_chunk = NULL;
    res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
    res->next_mem = res->u.mem;
    tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
               ((char*)res)+chunk_size);
    tor_assert(realign_pointer(res->next_mem) == res->next_mem);
    SET_SENTINEL(res);
    return res;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void chunk_free_unchecked ( memarea_chunk_t chunk) [static]

Release chunk from a memarea, either by adding it to the freelist or by freeing it if the freelist is already too big.

Definition at line 136 of file memarea.c.

{
  CHECK_SENTINEL(chunk);
  if (freelist_len < MAX_FREELIST_LEN) {
    ++freelist_len;
    chunk->next_chunk = freelist;
    freelist = chunk;
    chunk->next_mem = chunk->u.mem;
  } else {
    tor_free(chunk);
  }
}

Here is the caller graph for this function:

void* memarea_alloc ( memarea_t area,
size_t  sz 
)

Return a pointer to a chunk of memory in area of at least sz bytes.

sz should be significantly smaller than the area's chunk size, though we can deal if it isn't.

Definition at line 220 of file memarea.c.

{
  memarea_chunk_t *chunk = area->first;
  char *result;
  tor_assert(chunk);
  CHECK_SENTINEL(chunk);
  tor_assert(sz < SIZE_T_CEILING);
  if (sz == 0)
    sz = 1;
  if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
    if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
      /* This allocation is too big.  Stick it in a special chunk, and put
       * that chunk second in the list. */
      memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
      new_chunk->next_chunk = chunk->next_chunk;
      chunk->next_chunk = new_chunk;
      chunk = new_chunk;
    } else {
      memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
      new_chunk->next_chunk = chunk;
      area->first = chunk = new_chunk;
    }
    tor_assert(chunk->mem_size >= sz);
  }
  result = chunk->next_mem;
  chunk->next_mem = chunk->next_mem + sz;
  /* Reinstate these if bug 930 ever comes back
  tor_assert(chunk->next_mem >= chunk->u.mem);
  tor_assert(chunk->next_mem <= chunk->u.mem+chunk->mem_size);
  */
  chunk->next_mem = realign_pointer(chunk->next_mem);
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* memarea_alloc_zero ( memarea_t area,
size_t  sz 
)

As memarea_alloc(), but clears the memory it returns.

Definition at line 256 of file memarea.c.

{
  void *result = memarea_alloc(area, sz);
  memset(result, 0, sz);
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memarea_assert_ok ( memarea_t area)

Assert that area is okay.

Definition at line 316 of file memarea.c.

{
  memarea_chunk_t *chunk;
  tor_assert(area->first);

  for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
    CHECK_SENTINEL(chunk);
    tor_assert(chunk->next_mem >= chunk->u.mem);
    tor_assert(chunk->next_mem <=
          (char*) realign_pointer(chunk->u.mem+chunk->mem_size));
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memarea_clear ( memarea_t area)

Forget about having allocated anything in area, and free some of the backing storage associated with it, as appropriate.

Invalidates all pointers returned from memarea_alloc() for this area.

Definition at line 176 of file memarea.c.

{
  memarea_chunk_t *chunk, *next;
  if (area->first->next_chunk) {
    for (chunk = area->first->next_chunk; chunk; chunk = next) {
      next = chunk->next_chunk;
      chunk_free_unchecked(chunk);
    }
    area->first->next_chunk = NULL;
  }
  area->first->next_mem = area->first->u.mem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memarea_clear_freelist ( void  )

Remove all unused memarea chunks from the internal freelist.

Definition at line 191 of file memarea.c.

{
  memarea_chunk_t *chunk, *next;
  freelist_len = 0;
  for (chunk = freelist; chunk; chunk = next) {
    next = chunk->next_chunk;
    tor_free(chunk);
  }
  freelist = NULL;
}

Here is the caller graph for this function:

void memarea_drop_all ( memarea_t area)

Free area, invalidating all pointers returned from memarea_alloc() and friends for this area.

Definition at line 161 of file memarea.c.

{
  memarea_chunk_t *chunk, *next;
  for (chunk = area->first; chunk; chunk = next) {
    next = chunk->next_chunk;
    chunk_free_unchecked(chunk);
  }
  area->first = NULL; /*fail fast on */
  tor_free(area);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memarea_get_stats ( memarea_t area,
size_t *  allocated_out,
size_t *  used_out 
)

Set allocated_out to the number of bytes allocated in area, and used_out to the number of bytes currently used.

Definition at line 300 of file memarea.c.

{
  size_t a = 0, u = 0;
  memarea_chunk_t *chunk;
  for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
    CHECK_SENTINEL(chunk);
    a += CHUNK_HEADER_SIZE + chunk->mem_size;
    tor_assert(chunk->next_mem >= chunk->u.mem);
    u += CHUNK_HEADER_SIZE + (chunk->next_mem - chunk->u.mem);
  }
  *allocated_out = a;
  *used_out = u;
}
void* memarea_memdup ( memarea_t area,
const void *  s,
size_t  n 
)

As memdup, but returns the memory from area.

Definition at line 265 of file memarea.c.

{
  char *result = memarea_alloc(area, n);
  memcpy(result, s, n);
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

memarea_t* memarea_new ( void  )

Allocate and return new memarea.

Definition at line 151 of file memarea.c.

{
  memarea_t *head = tor_malloc(sizeof(memarea_t));
  head->first = alloc_chunk(CHUNK_SIZE, 1);
  return head;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int memarea_owns_ptr ( const memarea_t area,
const void *  p 
)

Return true iff p is in a range that has been returned by an allocation from area.

Definition at line 205 of file memarea.c.

{
  memarea_chunk_t *chunk;
  const char *ptr = p;
  for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
    if (ptr >= chunk->u.mem && ptr < chunk->next_mem)
      return 1;
  }
  return 0;
}

Here is the caller graph for this function:

char* memarea_strdup ( memarea_t area,
const char *  s 
)

As strdup, but returns the memory from area.

Definition at line 274 of file memarea.c.

{
  return memarea_memdup(area, s, strlen(s)+1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

char* memarea_strndup ( memarea_t area,
const char *  s,
size_t  n 
)

As strndup, but returns the memory from area.

Definition at line 281 of file memarea.c.

{
  size_t ln;
  char *result;
  const char *cp, *end = s+n;
  tor_assert(n < SIZE_T_CEILING);
  for (cp = s; cp < end && *cp; ++cp)
    ;
  /* cp now points to s+n, or to the 0 in the string. */
  ln = cp-s;
  result = memarea_alloc(area, ln+1);
  memcpy(result, s, ln);
  result[ln]='\0';
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE void* realign_pointer ( void *  ptr) [static]

Increment ptr until it is aligned to MEMAREA_ALIGN.

Definition at line 58 of file memarea.c.

{
  uintptr_t x = (uintptr_t)ptr;
  x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
  /* Reinstate this if bug 930 ever reappears
  tor_assert(((void*)x) >= ptr);
  */
  return (void*)x;
}

Here is the caller graph for this function:


Variable Documentation

memarea_chunk_t* freelist = NULL [static]

A linked list of unused memory area chunks.

Used to prevent us from spinning in malloc/free loops.

Definition at line 103 of file memarea.c.

int freelist_len = 0 [static]

The number of memarea chunks currently in our freelist.

Definition at line 100 of file memarea.c.