⟦b375516e9⟧

TextFile

/* Copyright (C) 1989 Aladdin Enterprises.  All rights reserved.
   Distributed by Free Software Foundation, Inc.

This file is part of Ghostscript.

Ghostscript is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
to anyone for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.  Refer
to the Ghostscript General Public License for full details.

Everyone is granted permission to copy, modify and redistribute
Ghostscript, but only under the conditions described in the Ghostscript
General Public License.  A copy of this license is supposed to have been
given to you along with Ghostscript so you can know your rights and
responsibilities.  It should be in a file named COPYING.  Among other
things, the copyright notice and this notice must be preserved on all
copies.  */

/* ialloc.c */
/* Memory allocator for GhostScript interpreter */
#include <stdio.h>		/* for NULL */
#include "std.h"
#include "malloc_.h"
#include "memory_.h"
#include "alloc.h"

extern char gs_debug[128];

/* Forward references */
private int alloc_add_chunk();

/* Round up all sizes so objects are aligned. */
#define log2_alloc_mod 3		/* log2(sizeof(double)) */
#define alloc_mod (1<<log2_alloc_mod)
#define alloc_mask (alloc_mod-1)
#define alloc_round(siz) (uint)(((siz) + alloc_mask) & -alloc_mod)

/* Max object size for separate free list */
#define max_chain_size 255

/* Structure for allocator state.  If we multi-thread some day, */
/* this might be instantiated more than once. */
typedef struct alloc_state_s alloc_state;
struct alloc_state_s {
	/* Note that allocation takes place both from the bottom up */
	/* (dynamic objects) and from the top down. */
	byte *base;
	byte *bot;			/* bottom of free area */
	byte *top;			/* top of free area */
	byte *limit;
	uint chunk_size;		/* unit for wholesale malloc */
	uint big_size;			/* min size for separate malloc */
	/* Cumulative statistics */
	long used, total;
	char *free[(max_chain_size >> log2_alloc_mod) + 1];
	/* Chain together any malloc'ed objects */
	char *malloc_chain;
};
/* The only instance for now */
private alloc_state as;

/* Debugging printout */
#ifdef DEBUG
#  define alloc_print(tag, blk, sz)\
	if ( gs_debug['a'] )\
	  printf("[a:%c%s]%lx(%u)\n", tag, client_name, (ulong)blk, sz)
#else
#  define alloc_print(tag, blk, sz)
#endif

/* ------ Initialize/status ------ */

/* Initialize the allocator */
void
alloc_init(uint chunk_size)
{	memset(&as, 0, sizeof(alloc_state));	/* do it all at once */
	as.chunk_size = chunk_size;
	as.big_size = chunk_size / 3;
}

/* Return the status of the allocator: space used, total space. */
void
alloc_status(long *pused, long *ptotal)
{	*pused = (as.bot - as.base) + (as.limit - as.top) + as.used;
	*ptotal = as.limit - as.base + as.total;
}

/* ------ Ordinary allocation ------ */

/* Allocate an object.  Return 0 if not enough room. */
char *
alloc(uint size, char *client_name)
{	uint left;
	uint block_size;
	if ( size <= max_chain_size )
	   {	/* See if we can use an orphan block */
		char **fptr = &as.free[alloc_round(size) >> log2_alloc_mod];
		char *block = *fptr;
		if ( block != 0 )
		   {	*fptr = *(char **)block;
			alloc_print('#', block, size);
			return block;
		   }
	   }
	left = as.top - as.bot;
	if ( size >= as.big_size )
	   {	/* Large object, do a separate malloc. */
		char *mblock = malloc(size + sizeof(char *));
		if ( mblock != NULL )
		   {	char *block = mblock + sizeof(char *);
		   	alloc_print('*', block, size);
			*(char **)mblock = as.malloc_chain;
			as.malloc_chain = mblock;
			return block;
		   }
	   }
	block_size = alloc_round(size);
	if ( block_size > left )
	   {	if ( !alloc_add_chunk() )
		   {	alloc_print('~', (ulong)0, size);
#ifdef DEBUG
			gs_dump_C_stack();
#endif
			return 0;
		   }
	   }
	as.top -= block_size;
	alloc_print(' ', as.top, size);
	return (char *)as.top;
}

/* Free an object, if possible. */
void
alloc_free(char *cobj, uint size, char *client_name)
{	uint block_size = alloc_round(size);
#define obj ((byte *)cobj)
	if ( obj == as.top )
		as.top += block_size;
	else if ( obj + block_size == as.bot )
		as.bot = (byte *)obj;
	else if ( (ptr_ord_t)obj < (ptr_ord_t)as.base ||
		  (ptr_ord_t)obj >= (ptr_ord_t)as.limit )
	   {	/* Might be in another segment, or allocated with */
		/* malloc.  Check the malloc chain. */
		char **prev;
		char *mblock;
		for ( prev = &as.malloc_chain; *prev != 0; prev = (char **)mblock )
		   {	mblock = *prev;
			if ( mblock + sizeof(char *) == cobj )
			   {	*prev = *(char **)mblock;
				free(mblock);
				alloc_print('^', obj, size);
				return;
			   }
		   }
		alloc_print('?', obj, size);
		return;
	   }
	else
	   {	alloc_print('=', obj, size);
		if ( size <= max_chain_size && size > 0 )
		   {	char **fptr = &as.free[alloc_round(size) >> log2_alloc_mod];
			*(char **)cobj = *fptr;
			*fptr = cobj;
		   }
#ifdef DEBUG
		if ( gs_debug['a'] ) gs_dump_C_stack();
#endif
		return;
	   }
	alloc_print('-', obj, size);
#undef obj
}

/* ------ Dynamic allocation ------ */

/* Allocate a dynamic object.  Return 0 if not enough room. */
byte *
alloc_dynamic(uint size, char *client_name)
{	/* We take the easy way out here.... */
	byte *obj = (byte *)alloc(size, client_name);
	uint block_size = alloc_round(size);
	if ( obj != as.top ) return obj;	/* 0, or separate malloc */
	/* "Move" the object from the top to the bottom. */
	as.top += block_size;
	obj = as.bot;
	as.bot += block_size;
	alloc_print('<', obj, size);
	return obj;
}

/* Grow a dynamic object.  This may require moving it to a new chunk. */
/* Return 0 if not enough room. */
byte *
alloc_grow(byte *obj, uint old_size, uint new_size, char *client_name)
{	byte *nobj;
	uint old_block_size = alloc_round(old_size);
	uint new_block_size = alloc_round(new_size);
	if ( obj + old_block_size == as.bot )
	   {	/* Might be able to grow in place */
		if ( new_block_size <= as.top - obj )
		   {	as.bot = obj + new_block_size;
			alloc_print('+', obj, new_size);
			return obj;
		   }
	   }
	/* Can't grow in place.  Allocate a new object and copy. */
	nobj = alloc_dynamic(new_size, client_name);
	if ( nobj == 0 ) return 0;
	memcpy(nobj, obj, old_size);
	alloc_free((char *)obj, old_size, client_name);
	alloc_print('&', obj, new_size);
	return nobj;
}

/* Shrink a dynamic object. */
byte *
alloc_shrink(byte *obj, uint old_size, uint new_size, char *client_name)
{	uint old_block_size = alloc_round(old_size);
	uint new_block_size = alloc_round(new_size);
	if ( obj + old_block_size == as.bot )
		as.bot = obj + new_block_size;
	alloc_print('.', obj, new_size);
	return obj;
}

/* Shrink a dynamic object and make it permanent. */
byte *
alloc_shrink_copy(byte *obj, uint old_size, uint new_size, char *client_name)
{	uint old_block_size = alloc_round(old_size);
	byte *perm;
	if ( obj + old_block_size == as.bot )
	   {	/* Object is at end of current segment, */
		/* so there is definitely room. */
		uint new_block_size = alloc_round(new_size);
		perm = as.top -= new_block_size;
		memcpy(perm, obj, new_size);
		as.bot = obj;
	   }
	else
	   {	/* Object is somewhere else. */
		/* Just leave it where it is. */
		perm = obj;
	   }
	alloc_print('>', obj, new_size);
	return perm;
}

/* ------ Private routines ------ */

/* Allocate a new chunk.  Return true if successful. */
private int
alloc_add_chunk()
{	char *chunk = malloc(as.chunk_size);
#ifdef DEBUG
if ( gs_debug['a'] )
	printf("[a]%lx@%u ", (ulong)chunk, as.chunk_size);
#endif
	if ( chunk == NULL ) return 0;
	/* Update statistics for the old chunk */
	alloc_status(&as.used, &as.total);
	as.base = as.bot = (byte *)chunk;
	as.limit = as.top = (byte *)(chunk + as.chunk_size);
	return 1;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦b375516e9⟧ TextFile

Derivation

TextFile
