/* objalloc.c -- routines to allocate memory for objects
|
/* objalloc.c -- routines to allocate memory for objects
|
Copyright 1997 Free Software Foundation, Inc.
|
Copyright 1997 Free Software Foundation, Inc.
|
Written by Ian Lance Taylor, Cygnus Solutions.
|
Written by Ian Lance Taylor, Cygnus Solutions.
|
|
|
This program is free software; you can redistribute it and/or modify it
|
This program is free software; you can redistribute it and/or modify it
|
under the terms of the GNU General Public License as published by the
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 2, or (at your option) any
|
Free Software Foundation; either version 2, or (at your option) any
|
later version.
|
later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with this program; if not, write to the Free Software
|
along with this program; if not, write to the Free Software
|
Foundation, 51 Franklin Street - Fifth Floor,
|
Foundation, 51 Franklin Street - Fifth Floor,
|
Boston, MA 02110-1301, USA. */
|
Boston, MA 02110-1301, USA. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "ansidecl.h"
|
#include "ansidecl.h"
|
|
|
#include "objalloc.h"
|
#include "objalloc.h"
|
|
|
/* Get a definition for NULL. */
|
/* Get a definition for NULL. */
|
#include <stdio.h>
|
#include <stdio.h>
|
|
|
#if VMS
|
#if VMS
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#include <unixlib.h>
|
#include <unixlib.h>
|
#else
|
#else
|
|
|
/* Get a definition for size_t. */
|
/* Get a definition for size_t. */
|
#include <stddef.h>
|
#include <stddef.h>
|
|
|
#ifdef HAVE_STDLIB_H
|
#ifdef HAVE_STDLIB_H
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#else
|
#else
|
/* For systems with larger pointers than ints, this must be declared. */
|
/* For systems with larger pointers than ints, this must be declared. */
|
extern PTR malloc (size_t);
|
extern PTR malloc (size_t);
|
extern void free (PTR);
|
extern void free (PTR);
|
#endif
|
#endif
|
|
|
#endif
|
#endif
|
|
|
/* These routines allocate space for an object. Freeing allocated
|
/* These routines allocate space for an object. Freeing allocated
|
space may or may not free all more recently allocated space.
|
space may or may not free all more recently allocated space.
|
|
|
We handle large and small allocation requests differently. If we
|
We handle large and small allocation requests differently. If we
|
don't have enough space in the current block, and the allocation
|
don't have enough space in the current block, and the allocation
|
request is for more than 512 bytes, we simply pass it through to
|
request is for more than 512 bytes, we simply pass it through to
|
malloc. */
|
malloc. */
|
|
|
/* The objalloc structure is defined in objalloc.h. */
|
/* The objalloc structure is defined in objalloc.h. */
|
|
|
/* This structure appears at the start of each chunk. */
|
/* This structure appears at the start of each chunk. */
|
|
|
struct objalloc_chunk
|
struct objalloc_chunk
|
{
|
{
|
/* Next chunk. */
|
/* Next chunk. */
|
struct objalloc_chunk *next;
|
struct objalloc_chunk *next;
|
/* If this chunk contains large objects, this is the value of
|
/* If this chunk contains large objects, this is the value of
|
current_ptr when this chunk was allocated. If this chunk
|
current_ptr when this chunk was allocated. If this chunk
|
contains small objects, this is NULL. */
|
contains small objects, this is NULL. */
|
char *current_ptr;
|
char *current_ptr;
|
};
|
};
|
|
|
/* The aligned size of objalloc_chunk. */
|
/* The aligned size of objalloc_chunk. */
|
|
|
#define CHUNK_HEADER_SIZE \
|
#define CHUNK_HEADER_SIZE \
|
((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \
|
((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \
|
&~ (OBJALLOC_ALIGN - 1))
|
&~ (OBJALLOC_ALIGN - 1))
|
|
|
/* We ask for this much memory each time we create a chunk which is to
|
/* We ask for this much memory each time we create a chunk which is to
|
hold small objects. */
|
hold small objects. */
|
|
|
#define CHUNK_SIZE (4096 - 32)
|
#define CHUNK_SIZE (4096 - 32)
|
|
|
/* A request for this amount or more is just passed through to malloc. */
|
/* A request for this amount or more is just passed through to malloc. */
|
|
|
#define BIG_REQUEST (512)
|
#define BIG_REQUEST (512)
|
|
|
/* Create an objalloc structure. */
|
/* Create an objalloc structure. */
|
|
|
struct objalloc *
|
struct objalloc *
|
objalloc_create (void)
|
objalloc_create (void)
|
{
|
{
|
struct objalloc *ret;
|
struct objalloc *ret;
|
struct objalloc_chunk *chunk;
|
struct objalloc_chunk *chunk;
|
|
|
ret = (struct objalloc *) malloc (sizeof *ret);
|
ret = (struct objalloc *) malloc (sizeof *ret);
|
if (ret == NULL)
|
if (ret == NULL)
|
return NULL;
|
return NULL;
|
|
|
ret->chunks = (PTR) malloc (CHUNK_SIZE);
|
ret->chunks = (PTR) malloc (CHUNK_SIZE);
|
if (ret->chunks == NULL)
|
if (ret->chunks == NULL)
|
{
|
{
|
free (ret);
|
free (ret);
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
chunk = (struct objalloc_chunk *) ret->chunks;
|
chunk = (struct objalloc_chunk *) ret->chunks;
|
chunk->next = NULL;
|
chunk->next = NULL;
|
chunk->current_ptr = NULL;
|
chunk->current_ptr = NULL;
|
|
|
ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Allocate space from an objalloc structure. */
|
/* Allocate space from an objalloc structure. */
|
|
|
PTR
|
PTR
|
_objalloc_alloc (struct objalloc *o, unsigned long len)
|
_objalloc_alloc (struct objalloc *o, unsigned long len)
|
{
|
{
|
/* We avoid confusion from zero sized objects by always allocating
|
/* We avoid confusion from zero sized objects by always allocating
|
at least 1 byte. */
|
at least 1 byte. */
|
if (len == 0)
|
if (len == 0)
|
len = 1;
|
len = 1;
|
|
|
len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
|
len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
|
|
|
if (len <= o->current_space)
|
if (len <= o->current_space)
|
{
|
{
|
o->current_ptr += len;
|
o->current_ptr += len;
|
o->current_space -= len;
|
o->current_space -= len;
|
return (PTR) (o->current_ptr - len);
|
return (PTR) (o->current_ptr - len);
|
}
|
}
|
|
|
if (len >= BIG_REQUEST)
|
if (len >= BIG_REQUEST)
|
{
|
{
|
char *ret;
|
char *ret;
|
struct objalloc_chunk *chunk;
|
struct objalloc_chunk *chunk;
|
|
|
ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
|
ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
|
if (ret == NULL)
|
if (ret == NULL)
|
return NULL;
|
return NULL;
|
|
|
chunk = (struct objalloc_chunk *) ret;
|
chunk = (struct objalloc_chunk *) ret;
|
chunk->next = (struct objalloc_chunk *) o->chunks;
|
chunk->next = (struct objalloc_chunk *) o->chunks;
|
chunk->current_ptr = o->current_ptr;
|
chunk->current_ptr = o->current_ptr;
|
|
|
o->chunks = (PTR) chunk;
|
o->chunks = (PTR) chunk;
|
|
|
return (PTR) (ret + CHUNK_HEADER_SIZE);
|
return (PTR) (ret + CHUNK_HEADER_SIZE);
|
}
|
}
|
else
|
else
|
{
|
{
|
struct objalloc_chunk *chunk;
|
struct objalloc_chunk *chunk;
|
|
|
chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
|
chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
|
if (chunk == NULL)
|
if (chunk == NULL)
|
return NULL;
|
return NULL;
|
chunk->next = (struct objalloc_chunk *) o->chunks;
|
chunk->next = (struct objalloc_chunk *) o->chunks;
|
chunk->current_ptr = NULL;
|
chunk->current_ptr = NULL;
|
|
|
o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
|
|
o->chunks = (PTR) chunk;
|
o->chunks = (PTR) chunk;
|
|
|
return objalloc_alloc (o, len);
|
return objalloc_alloc (o, len);
|
}
|
}
|
}
|
}
|
|
|
/* Free an entire objalloc structure. */
|
/* Free an entire objalloc structure. */
|
|
|
void
|
void
|
objalloc_free (struct objalloc *o)
|
objalloc_free (struct objalloc *o)
|
{
|
{
|
struct objalloc_chunk *l;
|
struct objalloc_chunk *l;
|
|
|
l = (struct objalloc_chunk *) o->chunks;
|
l = (struct objalloc_chunk *) o->chunks;
|
while (l != NULL)
|
while (l != NULL)
|
{
|
{
|
struct objalloc_chunk *next;
|
struct objalloc_chunk *next;
|
|
|
next = l->next;
|
next = l->next;
|
free (l);
|
free (l);
|
l = next;
|
l = next;
|
}
|
}
|
|
|
free (o);
|
free (o);
|
}
|
}
|
|
|
/* Free a block from an objalloc structure. This also frees all more
|
/* Free a block from an objalloc structure. This also frees all more
|
recently allocated blocks. */
|
recently allocated blocks. */
|
|
|
void
|
void
|
objalloc_free_block (struct objalloc *o, PTR block)
|
objalloc_free_block (struct objalloc *o, PTR block)
|
{
|
{
|
struct objalloc_chunk *p, *small;
|
struct objalloc_chunk *p, *small;
|
char *b = (char *) block;
|
char *b = (char *) block;
|
|
|
/* First set P to the chunk which contains the block we are freeing,
|
/* First set P to the chunk which contains the block we are freeing,
|
and set Q to the last small object chunk we see before P. */
|
and set Q to the last small object chunk we see before P. */
|
small = NULL;
|
small = NULL;
|
for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
|
for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
|
{
|
{
|
if (p->current_ptr == NULL)
|
if (p->current_ptr == NULL)
|
{
|
{
|
if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
|
if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
|
break;
|
break;
|
small = p;
|
small = p;
|
}
|
}
|
else
|
else
|
{
|
{
|
if (b == (char *) p + CHUNK_HEADER_SIZE)
|
if (b == (char *) p + CHUNK_HEADER_SIZE)
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
/* If we can't find the chunk, the caller has made a mistake. */
|
/* If we can't find the chunk, the caller has made a mistake. */
|
if (p == NULL)
|
if (p == NULL)
|
abort ();
|
abort ();
|
|
|
if (p->current_ptr == NULL)
|
if (p->current_ptr == NULL)
|
{
|
{
|
struct objalloc_chunk *q;
|
struct objalloc_chunk *q;
|
struct objalloc_chunk *first;
|
struct objalloc_chunk *first;
|
|
|
/* The block is in a chunk containing small objects. We can
|
/* The block is in a chunk containing small objects. We can
|
free every chunk through SMALL, because they have certainly
|
free every chunk through SMALL, because they have certainly
|
been allocated more recently. After SMALL, we will not see
|
been allocated more recently. After SMALL, we will not see
|
any chunks containing small objects; we can free any big
|
any chunks containing small objects; we can free any big
|
chunk if the current_ptr is greater than or equal to B. We
|
chunk if the current_ptr is greater than or equal to B. We
|
can then reset the new current_ptr to B. */
|
can then reset the new current_ptr to B. */
|
|
|
first = NULL;
|
first = NULL;
|
q = (struct objalloc_chunk *) o->chunks;
|
q = (struct objalloc_chunk *) o->chunks;
|
while (q != p)
|
while (q != p)
|
{
|
{
|
struct objalloc_chunk *next;
|
struct objalloc_chunk *next;
|
|
|
next = q->next;
|
next = q->next;
|
if (small != NULL)
|
if (small != NULL)
|
{
|
{
|
if (small == q)
|
if (small == q)
|
small = NULL;
|
small = NULL;
|
free (q);
|
free (q);
|
}
|
}
|
else if (q->current_ptr > b)
|
else if (q->current_ptr > b)
|
free (q);
|
free (q);
|
else if (first == NULL)
|
else if (first == NULL)
|
first = q;
|
first = q;
|
|
|
q = next;
|
q = next;
|
}
|
}
|
|
|
if (first == NULL)
|
if (first == NULL)
|
first = p;
|
first = p;
|
o->chunks = (PTR) first;
|
o->chunks = (PTR) first;
|
|
|
/* Now start allocating from this small block again. */
|
/* Now start allocating from this small block again. */
|
o->current_ptr = b;
|
o->current_ptr = b;
|
o->current_space = ((char *) p + CHUNK_SIZE) - b;
|
o->current_space = ((char *) p + CHUNK_SIZE) - b;
|
}
|
}
|
else
|
else
|
{
|
{
|
struct objalloc_chunk *q;
|
struct objalloc_chunk *q;
|
char *current_ptr;
|
char *current_ptr;
|
|
|
/* This block is in a large chunk by itself. We can free
|
/* This block is in a large chunk by itself. We can free
|
everything on the list up to and including this block. We
|
everything on the list up to and including this block. We
|
then start allocating from the next chunk containing small
|
then start allocating from the next chunk containing small
|
objects, setting current_ptr from the value stored with the
|
objects, setting current_ptr from the value stored with the
|
large chunk we are freeing. */
|
large chunk we are freeing. */
|
|
|
current_ptr = p->current_ptr;
|
current_ptr = p->current_ptr;
|
p = p->next;
|
p = p->next;
|
|
|
q = (struct objalloc_chunk *) o->chunks;
|
q = (struct objalloc_chunk *) o->chunks;
|
while (q != p)
|
while (q != p)
|
{
|
{
|
struct objalloc_chunk *next;
|
struct objalloc_chunk *next;
|
|
|
next = q->next;
|
next = q->next;
|
free (q);
|
free (q);
|
q = next;
|
q = next;
|
}
|
}
|
|
|
o->chunks = (PTR) p;
|
o->chunks = (PTR) p;
|
|
|
while (p->current_ptr != NULL)
|
while (p->current_ptr != NULL)
|
p = p->next;
|
p = p->next;
|
|
|
o->current_ptr = current_ptr;
|
o->current_ptr = current_ptr;
|
o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
|
o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
|
}
|
}
|
}
|
}
|
|
|
