/*___________________________________________________________________________*
)()( DalekenMUD 1.12 (C) 2000 )()(
`][' by Martin Thomson, Lee Brooks, `]['
|| Ken Herbert and David Jacques ||
|| ----------------------------------------------------------------- ||
|| Envy Diku Mud improvements copyright (C) 1994 by Michael Quan, ||
|| David Love, Guilherme 'Willie' Arnold, and Mitchell Tse. ||
|| Merc Diku Mud improvments copyright (C) 1992, 1993 by Michael ||
|| Chastain, Michael Quan, and Mitchell Tse. ||
|| Original Diku Mud copyright (C) 1990, 1991 ||
|| by Sebastian Hammer, Michael Seifert, Hans Henrik St{rfeldt, ||
|| Tom Madsen, and Katja Nyboe. ||
|| ----------------------------------------------------------------- ||
|| Any use of this software must follow the licenses of the ||
|| creators. Much time and thought has gone into this software and ||
|| you are benefitting. We hope that you share your changes too. ||
|| What goes around, comes around. ||
|| ----------------------------------------------------------------- ||
|| ssm.c ||
|| Shared string manager, contains string hashing/memory management. ||
*_/<>\_________________________________________________________________/<>\_*/
/******************************************************************************
* SSM v2.2 (shared string manager) *
* *
* Copyright (C) 1996 Melvin Smith (Fusion) for EnvyMUD 2.2 *
* *
* Due to alignment differences on 32 bit and 64 bit machines, memory *
* usage is now virtually identical to standard Merc on 32-bit *
* architecture, but slightly larger on 64-bit. Memory usage is still *
* smaller than SSM 2.0 or earlier. The manager now uses short ints for *
* the count and size of chunks, so to increase MAX_STRING you must *
* increase MAX_CHUNKS instead. String have a max reference count of *
* +32766 and max size of CHUNK_SIZE (0xfff0). Fragmentation is also *
* handled more efficiently by marking failed chunks with -1 to temporarily *
* disable them until a defrag_heap() recycles them. This helps when a *
* 4 byte chunk is freed low in the heap, so string_dup() doesn't walk *
* the whole heap every time. *
* *
* <msmith@falcon.mercer.peachnet.edu> *
*****************************************************************************/
#include "mud.h"
#if !defined( ultrix )
#include <memory.h>
#endif
#define intType short int
#define uintType unsigned intType
#define intTypeSize ( sizeof( intType ) )
#define addrType void *
#define addrTypeSize ( sizeof( addrType ) )
#define addrSizeMask ( sizeof( addrType ) - 1 )
#if !defined( macintosh )
extern int _filbuf args( ( FILE * ) );
#endif
typedef struct BE BufEntry;
struct BE
{
BufEntry *next;
uintType size; /* size of the chunk (regardless of NULL CHAR) */
intType usage; /* how many pointers to the string */
char buf[1]; /* chunk starts here */
};
/*
* This is for the temporary hashing of strings at bootup to speedup
* comparison/crunching of the string space. The temp_string_hash will
* be freed after boot_done( ) is called.
*/
typedef struct TH TempHash;
struct TH
{
TempHash *next;
char *str;
};
TempHash **temp_string_hash;
/* These are the original Merc vars in db.c */
char str_empty[1];
char *string_space;
char *top_string;
long nAllocString;
long sAllocString;
long nOverFlowString;
long sOverFlowString;
int numFree;
bool Full;
void temp_hash_add args( ( char *, int ) );
char *temp_hash_find args( ( const char *, int ) );
static unsigned get_string_hash args( ( register const char *, int ) );
int defrag_heap args( ( void ) );
/*
* ssm_buf_head points to start of shared space,
* ssm_buf_free points to next free block
*/
BufEntry *ssm_buf_head, *ssm_buf_free;
/* To allocate more memory increase MAX_CHUNKS in merc.h. */
#define CHUNK_SIZE 0xfff0 /* DO NOT mess with this! */
long MAX_STRING = MAX_CHUNKS * CHUNK_SIZE;
int HEADER_SIZE;
/*
* Not sure what is a good value for MAX_FREE
* If a dup fails str_dup will not defrag unless the number
* of numFree >= MAX_FREE. numFree is NOT the current number of free blocks,
* it is just a counter so defrag doesnt start dragging the game in the
* case of a lot of failed dups.
*/
#define MAX_FREE 1000
void init_string_space( )
{
BufEntry *walk;
int i;
log_string( "SSM: allocating shared string space of %ld bytes.",
MAX_STRING );
string_space = (char *)malloc( MAX_STRING );
if( !string_space )
{
bug( "[SSM] Cant allocate shared string space." );
exit( 1 );
}
top_string = string_space + MAX_STRING - 1;
ssm_buf_head = (BufEntry *)string_space;
HEADER_SIZE = (int)( (char *)&ssm_buf_head->buf[0] - (char *)ssm_buf_head );
walk = ssm_buf_head;
for( i = 0;; i++ )
{
walk->usage = 0;
walk->size = CHUNK_SIZE - HEADER_SIZE;
if( i < MAX_CHUNKS - 1 )
{
walk->next = (BufEntry *)( (char *)walk + CHUNK_SIZE );
walk = walk->next;
continue;
}
walk->next = 0;
break;
}
ssm_buf_free = ssm_buf_head;
temp_string_hash = (TempHash **)calloc( sizeof( TempHash * ),
MAX_KEY_HASH );
}
int defrag_heap( )
{
/*
* Walk through the shared heap and merge adjacent free blocks.
* Free blocks are merged in str_free if free->next is free but
* if the block preceding free is free, it stays unmerged. I would
* rather not have the heap as a DOUBLE linked list for 2 reasons...
* (1) Extra 4 bytes per struct uses more mem
* (2) Speed - don't want to bog down str_ functions with heap management
* The "orphaned" blocks will eventually be either merged or reused.
* The str_dup function will call defrag if it cant allocate a buf.
*/
BufEntry *walk, *last_free, *next;
int merges = 0;
ssm_buf_free = 0;
for( walk = ssm_buf_head, last_free = 0; walk; walk = next )
{
next = walk->next;
if( walk->usage > 0 )
{
/* this block is in use so set last_free to NULL */
last_free = 0;
}
else if( !last_free )
{
/* OK found a NEW free block, set last_free and move to next */
last_free = walk;
if( !ssm_buf_free )
ssm_buf_free = walk;
}
else
{
/* previous block free so merge walk into last_free and move on */
if( (long)last_free->size + (long)walk->size <= CHUNK_SIZE )
{
merges++;
last_free->size += walk->size + HEADER_SIZE;
last_free->next = walk->next;
last_free->usage = 0;
}
else
last_free = walk;
}
}
if( merges )
bug( "[SSM] defrag_heap : made %d block merges.", merges );
else
bug( "[SSM] defrag_heap : resulted in 0 merges." );
/* Start count over again */
numFree = 0;
return merges;
}
/*
* Dup a string into shared space. If string exists, the usage count
* gets incremented and the reference is returned. If the string does
* not exist in heap, space is allocated and usage is 1.
* This is a linked list first fit algorithm, so strings can be
* freed. Upon bootup, there is a seperate hash table constructed in order
* to do crunching, then the table is destroyed.
*/
char *str_dup( const char *str )
{
BufEntry *ptr;
char *str_new;
int len;
int rlen;
if( !str || !*str )
return &str_empty[0];
if( str > string_space && str < top_string )
{
ptr = (BufEntry *)( str - HEADER_SIZE );
if( ptr->usage <= 0 )
{
bug( "str_dup : invalid str" );
bug( str );
}
ptr->usage++;
return (char *)str;
}
rlen = len = (int)strlen( str ) + 1;
/*
* Round up to machine dependant address size.
* Don't remove this, because when the BufEntry struct is overlaid
* the struct must be aligned correctly.
*/
if( ( len + HEADER_SIZE ) & addrSizeMask )
len += addrTypeSize - ( ( len + HEADER_SIZE ) & addrSizeMask );
if( ssm_buf_free )
{
RETRY:
for( ptr = ssm_buf_free; ptr; ptr = ptr->next )
if( ptr->usage == 0 && ptr->size >= len )
break;
if( !ptr )
{
if( numFree >= MAX_FREE )
{
int merges;
bug( "[SSM] Attempting to optimize shared string heap." );
merges = defrag_heap( );
/* goto is fine because defrag will return 0 next time */
if( merges )
goto RETRY;
}
str_new = (char *)malloc( rlen );
strcpy( str_new, str );
sOverFlowString += rlen;
nOverFlowString++;
return str_new;
}
/* If there is at least header size excess break it up */
else if( ptr->size - len >= HEADER_SIZE )
{
BufEntry *temp;
/* WARNING! - DONT REMOVE THE CASTS BELOW! - Fusion */
temp = (BufEntry *)( (char *)ptr + HEADER_SIZE + len );
temp->size = ptr->size - ( len + HEADER_SIZE );
temp->next = ptr->next;
temp->usage = 0;
ptr->size = len;
ptr->next = temp;
ptr->usage = 1;
ssm_buf_free = temp;
}
else
{
ptr->usage = 1;
if( ptr != ssm_buf_free )
ssm_buf_free->usage--; /* buf_free was skipped */
for( ssm_buf_free = ssm_buf_head; ssm_buf_free;
ssm_buf_free = ssm_buf_free->next )
if( ssm_buf_free->usage == 0 )
break;
}
str_new = (char *)&ptr->buf[0];
strcpy( str_new, str );
nAllocString++;
sAllocString += ptr->size + HEADER_SIZE;
}
else
{
/* A one time toggle just for bugging purposes */
if( !Full )
{
bug( "[SSM] The shared string heap is full!" );
Full = 1;
}
str_new = (char *)malloc( rlen );
strcpy( str_new, str );
sOverFlowString += rlen;
nOverFlowString++;
}
return str_new;
}
/*
* If string is in shared space, decrement usage, if usage then is 0,
* free the chunk and attempt to merge with next node. Other
* strings are freed with standard free.
* Never call free/delete externally on a shared string.
*/
void free_string( char *str )
{
BufEntry *ptr;
if( !str || str == &str_empty[0] )
return;
if( str > string_space && str < top_string )
{
ptr = (BufEntry *)( str - HEADER_SIZE );
if( --ptr->usage > 0 )
return;
else if( ptr->usage < 0 )
{
bug( "SSM:free_string: multiple free or invalid string." );
bug( (char *)&ptr->buf[0] );
return;
}
numFree++;
sAllocString -= ( ptr->size + HEADER_SIZE );
nAllocString--;
if( ssm_buf_free > ptr )
ssm_buf_free = ptr;
if( fBootDb )
{
TempHash *ptr;
TempHash *walk;
int ihash = strlen( str ) % MAX_KEY_HASH;
for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
{
if( ptr->str != str )
continue;
else if( ptr == temp_string_hash[ ihash ] )
temp_string_hash[ ihash ] = ptr->next;
else
for( walk = temp_string_hash[ ihash ]; walk;
walk = walk->next )
{
if( walk->next == ptr )
{
walk->next = ptr->next;
break;
}
}
free( ptr );
break;
}
}
return;
}
sOverFlowString -= strlen( str ) + 1;
nOverFlowString--;
if( sOverFlowString < 0 || nOverFlowString < 0 )
{
bug( "SSM:free_string: string free from outside SS space." );
bug( str );
}
free( str );
}
/*
* A function much along the same lines as fread_string, except
* it is supposed to understand the most simple C style strings.
*/
char *fread_string( FILE *fp, int *status )
{
char buf[MAX_STRING_LENGTH * 4];
char *ptr = &buf[0];
int c;
*status = 0;
do
{
if( feof( fp ) )
{
*status = 1;
bug( "fread_string: EOF encountered on read.\n\r" );
if( fBootDb )
exit( 1 );
return &str_empty[0];
}
c = getc( fp );
}
while( isspace( c ) );
if( c != '"' )
{
*status = 1;
bug( "Expecting a string, got %c instead.", c );
if( fBootDb )
exit( 1 );
return &str_empty[0];
}
for( ;; )
{
c = getc( fp );
*ptr = c;
switch( c )
{
default:
ptr++;
break;
case EOF:
bug( "fread_string: EOF" );
*status = 1;
return &str_empty[0];
case '\\':
c = getc( fp );
switch( c )
{
default:
*ptr++ = c;
break;
case EOF:
bug( "fread_string: EOF" );
*status = 1;
return &str_empty[0];
case '\n':
case 'n': case 'N': /* eol */
while( ptr > buf && *( ptr - 1 ) == ' ' )
--ptr;
*ptr++ = '\n';
*ptr++ = '\r';
break;
case 'r': case 'R':
break;
case 't': case 'T': /* tab */
*ptr++ = '\t';
break;
case 'a': case 'A': /* beep */
*ptr++ = '&';
*ptr++ = '*';
break;
case '\r':
break;
}
break;
case '\n':
case '\r':
break;
case '"':
if( ptr == &buf[0] )
return &str_empty[0];
*ptr = '\0';
if( fBootDb )
{
int len = ptr - buf;
ptr = temp_hash_find( buf, len );
if( ptr )
return str_dup( ptr );
ptr = str_dup( buf );
temp_hash_add( ptr, len );
return ptr;
}
return str_dup( buf );
}
}
}
/*
* Read string into user supplied buffer.
* Modified version of Furey's fread_string
*/
void temp_fread_string( FILE *fp, char *buf )
{
char *ptr = buf;
int c;
*ptr = '\0';
do
{
if( feof( fp ) )
{
bug( "temp_fread_string: EOF encountered on read.\n\r" );
return;
}
c = getc( fp );
}
while( isspace( c ) );
if( c != '"' )
{
bug( "Expecting a string, got %c instead.", c );
return;
}
c = getc( fp );
if( ( *ptr++ = c ) == '"' )
return;
for( ;; )
{
c = getc( fp );
*ptr = c;
switch( c )
{
default:
ptr++;
break;
case EOF:
bug( "fread_string: EOF" );
return;
case '\\':
c = getc( fp );
switch( c )
{
case 'n': case 'N': /* eol */
*ptr++ = '\n';
*ptr++ = '\r';
break;
case 'r': case 'R':
break;
case 't': case 'T': /* tab */
*ptr++ = '\t';
break;
case 'a': case 'A': /* beep */
*ptr++ = '&';
*ptr++ = '*';
break;
case '\n':
break;
default:
*ptr++ = c;
break;
}
break;
case '\n':
case '\r':
break;
case '"':
*ptr = '\0';
return;
}
}
}
/* Hashing function from erwin@pip.dknet.dk */
static unsigned get_string_hash( register const char *key, int len )
{
register int i = UMIN( len, 32 );
register unsigned hash = 0;
while( i-- )
hash = hash * 33U + *key++;
return hash % MAX_KEY_HASH;
}
/* Lookup the string in the boot-time hash table. */
char *temp_hash_find( const char *str, int len )
{
TempHash *ptr;
int ihash;
if( !fBootDb || !*str )
return 0;
ihash = get_string_hash( str, len );
for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
{
if( *ptr->str != *str )
continue;
else if( strcmp( ptr->str, str ) )
continue;
else
return ptr->str;
}
return 0;
}
/*
* Add a reference in the temporary hash table.
* String is still in the linked list structure but
* reference is kept here for quick lookup at boot time;
*/
void temp_hash_add( char *str, int len )
{
TempHash *add;
int ihash;
if( !fBootDb || !*str || ( str <= string_space && str >= top_string ) )
return;
ihash = get_string_hash( str, len );
add = (TempHash *) malloc( sizeof( TempHash ) );
add->next = temp_string_hash[ ihash ];
temp_string_hash[ ihash ] = add;
add->str = str;
}
/* Free the temp boot string hash table */
void boot_done( void )
{
TempHash *ptr, *next;
int ihash;
for( ihash = 0; ihash < MAX_KEY_HASH; ihash++ )
{
for( ptr = temp_string_hash[ ihash ]; ptr; ptr = next )
{
next = ptr->next;
free( ptr );
}
}
free( temp_string_hash );
temp_string_hash = 0; /* Bug check in case someone accesses later */
}
