/******************************************************************************
* 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> *
* *
* ROM2.4 modifications by Tom Adriaenssen (Jan 1996) -- Wreck *
* *
* <tadriaen@zorro.ruca.ua.ac.be> *
* *
* Removed ROM 2.4 modifications as Envy doesnt need *fread_string_eol -Kahn *
* *
*****************************************************************************/
/**********************************************************
*************** S U N D E R M U D *** 2 . 0 **************
**********************************************************
* The unique portions of the SunderMud code as well as *
* the integration efforts for code from other sources is *
* based primarily on the efforts of: *
* *
* Lotherius <aelfwyne@operamail.com> (Alvin W. Brinson) *
* and many others, see "help sundermud" in the mud. *
**********************************************************/
// strcpy is used here instead of the SLCPY macro due to breakage of the macro
#include "everything.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;
uintType len;
char *str;
};
TempHash **temp_string_hash;
/* These are the original Merc vars in db.c */
extern bool fBootDb;
char str_empty[1];
char *string_space;
char *top_string;
long nAllocString;
long sAllocString;
long nOverFlowString;
long sOverFlowString;
int numFree;
bool Full;
char *str_dup ( const char * );
void free_string ( char * );
char *fread_string ( FILE * );
void temp_hash_add ( char * );
char *temp_hash_find ( const char * );
/*
* 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 500
void init_string_space()
{
BufEntry *walk;
int i;
string_space = (char *)malloc( MAX_STRING );
if( !string_space )
{
bugf ( "[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;
continue;
}
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;
continue;
}
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;
}
}
/* This should be info, not a bug. There will always be merges. */
if( merges )
log_string ( "[SSM] defrag_heap : made %d block merges.", merges );
else
log_string ( "[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.
* ---
* Using a local "register const char *lstr" shaved ms/call from 0.06 to 0.02,
* which I consider significant - Lotherius
*/
char *str_dup( const char *str )
{
register const char *lstr = (const char *)str;
BufEntry *ptr;
char *str_new;
int len;
int rlen;
if( !lstr || !*lstr )
return &str_empty[0];
if( lstr > string_space && lstr < top_string )
{
ptr = (BufEntry *)( lstr - HEADER_SIZE );
if( ptr->usage <= 0 )
{
bugf( "str_dup : invalid str: %s", lstr );
}
ptr->usage++;
return (char *)lstr;
}
rlen = len = (int)strlen( lstr ) + 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;
log_string ( "[SSM] Attempting to optimize shared string heap." );
merges = defrag_heap();
if( merges )
log_string ( "[SSM] defrag_heap : made %d block merges.", merges );
else
log_string ( "[SSM] defrag_heap : resulted in 0 merges." );
/* goto is fine because defrag will return 0 next time */
if( merges )
goto RETRY;
}
str_new = (char *)malloc( rlen );
strcpy( str_new, lstr );
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, lstr );
nAllocString++;
sAllocString += ptr->size + HEADER_SIZE;
}
else
{
/* A one time toggle just for bugging purposes */
if( !Full )
{
bugf ( "[SSM] The shared string heap is full!" );
Full = 1;
}
str_new = (char *)malloc( rlen );
strcpy( str_new, lstr );
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 )
{
bugf ( "SSM:free_string: multiple free or invalid string.");
bugf ( (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 )
{
bugf ( "SSM:free_string: string free from outside SS space.: %s", str );
}
free( str );
}
/*
* Read and allocate space for a string from a file.
* This replaces db.c fread_string
* This is modified version of Furey's fread_string from Merc
*/
char *fread_string( FILE *fp )
{
char buf[ MAX_STRING_LENGTH*5 ]; // Had to increase this due to some large helpfiles.
char *ptr = buf;
char c;
do { c = getc( fp ); }
while( isspace( c ) );
if( ( *ptr++ = c ) == '~' )
return &str_empty[0];
for ( ;; )
{
switch ( *ptr = getc( fp ) )
{
default:
ptr++;
break;
case EOF:
bugf ( "Fread_string: EOF" );
return NULL;
break;
case '\n':
ptr++;
*ptr++ = '\r';
break;
case '\r':
break;
case '~':
*ptr = '\0';
if( fBootDb )
{
ptr = temp_hash_find( buf );
if( ptr )
return str_dup( ptr );
ptr = str_dup( buf );
temp_hash_add( ptr );
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;
char c;
do { c = getc( fp ); }
while ( isspace( c ) );
if ( ( *ptr++ = c ) == '~' )
{
*buf = '\0';
return;
}
for ( ;; )
{
switch ( *ptr = getc( fp ) )
{
default:
ptr++;
break;
case EOF:
bugf ( "Fread_string: EOF" );
exit( 1 );
break;
case '\n':
ptr++;
*ptr++ = '\r';
break;
case '\r':
break;
case '~':
*ptr = '\0';
return;
}
}
}
/* Lookup the string in the boot-time hash table. */
char *temp_hash_find( const char *str )
{
register const unsigned char *astr = (const unsigned char *)str;
TempHash *ptr;
int len;
int ihash;
if( !fBootDb || !*str )
return 0;
len = strlen( astr );
ihash = len % MAX_KEY_HASH;
for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
{
if( *ptr->str != *astr )
continue;
else if( strcmp( ptr->str, astr ) )
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 )
{
TempHash *add;
int len;
int ihash;
if( !fBootDb || !*str || ( str <= string_space && str >= top_string ) )
return;
len = strlen( str );
ihash = len % MAX_KEY_HASH;
add = (TempHash *)malloc( sizeof( TempHash ) );
add->next = temp_string_hash[ ihash ];
temp_string_hash[ ihash ] = add;
add->len = len;
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 */
}