/****************************************************************************** * 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 * * * *****************************************************************************/ #include <sys/types.h> #include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include "merc.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 *, const int ); char *temp_hash_find ( const char * ); static unsigned long get_string_hash( register const char *key ); /* * ssm_buf_head points to start of shared space, * ssm_buf_free points to next free block */ BufEntry *ssm_buf_head = NULL, *ssm_buf_free = NULL; /* 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; string_space = (char *)calloc( 1, MAX_STRING ); if( !string_space ) { #if defined(cbuilder) logf_string( "[SSM] Cant allocate shared string space." ); return -1; #else bug( "[SSM] Cant allocate shared string space.", 0 ); exit( 1 ); #endif } 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 = NULL; 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 = NULL, *last_free = NULL, *next = NULL; 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; } } if( merges ) bug( "[SSM] defrag_heap : made %d block merges.", merges ); else bug( "[SSM] defrag_heap : resulted in 0 merges.", 0 ); /* 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", 0 ); bug( str, 0 ); } 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.", 0 ); 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!", 0 ); 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. * * You must now pass a pointer to the string pointer you're wanting to free. This * way free_string can set that pointer to NULL and not rely on the caller to * set the pointer to null after call free_string. This method makes it so * no-one can free the same string twice (which was causing major string-space * corruption). -Zane * */ void free_string( char **strptr ) { char *str; BufEntry *ptr; str = *strptr; if( !str ) return; if( str == &str_empty[0] ) { *strptr = NULL; return; } if( str > string_space && str < top_string ) { ptr = (BufEntry *)( str - HEADER_SIZE ); if( --ptr->usage > 0 ) { *strptr = NULL; return; } else if( ptr->usage < 0 ) { /* Undo the change we made above, avoid memory corruption if possible. */ ptr->usage++; bug( "SSM:free_string: multiple free or invalid string.", 0 ); bug( str, 0 ); *strptr = NULL; return; } numFree++; sAllocString -= ( ptr->size + HEADER_SIZE ); nAllocString--; if( ssm_buf_free > ptr ) ssm_buf_free = ptr; if( fBootDb ) { TempHash *ptr; TempHash *walk; unsigned long ihash = get_string_hash(str); 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; } } *strptr = NULL; return; } sOverFlowString -= strlen( str ) + 1; nOverFlowString--; if ( sOverFlowString < 0 || nOverFlowString < 0 ) bug( "SSM:free_string: string free from outside SS space.", 0 ); free( str ); *strptr = NULL; return; } /* * 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*4 ]; register char *ptr = buf; register char c; int len; /* *status = 0;*/ do c = getc( fp ); while( isspace( c ) ); if( ( *ptr++ = c ) == '~' ) return &str_empty[0]; for ( ;; ) { switch ( *ptr = getc( fp ) ) { default: ptr++; break; case EOF: bug( "Fread_string: EOF", 0 ); /* *status = 1; */ return NULL; break; case '\n': *ptr++ = '\r'; *ptr++ = '\n'; break; case '\r': break; case '~': *ptr = '\0'; if( fBootDb ) { len = ptr - buf; ptr = temp_hash_find( buf ); if( ptr ) return str_dup( ptr ); ptr = str_dup( buf ); temp_hash_add( ptr, len ); return ptr; } return str_dup( buf ); } } } char *fread_string_eol( FILE *fp ) { signed char buf[ MAX_STRING_LENGTH*4 ]; register signed char *ptr = buf; register signed char c; int len; /* * Skip blanks. * Read first char. */ do c = getc( fp ); while ( c == ' ' || c == '\t' ); *ptr = c; while ( *ptr != '\n' && *ptr != '\r' && *ptr != EOF ) *++ptr = getc( fp ); if ( ptr == buf ) return &str_empty[0]; *ptr = '\0'; if( fBootDb ) { len = ptr-buf; ptr = temp_hash_find( buf ); 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 fread_string_eol */ int temp_fread_string_eol( FILE *fp, char *outbuf ) { register signed char *ptr = outbuf; register signed char c; bool bEOF = FALSE; /* * Skip blanks. * Read first char. */ do c = getc( fp ); while ( c == ' ' || c == '\t' ); *ptr = c; while ( *ptr != '\n' && *ptr != '\r' && *ptr != EOF ) *++ptr = getc( fp ); if ( *ptr == EOF ) bEOF = TRUE; *ptr = '\0'; return bEOF; } /* * Read string into user supplied buffer. * Modified version of Furey's fread_string */ void temp_fread_string( FILE *fp, char *outbuf ) { char *ptr = outbuf; char c; do { c = getc( fp ); } while ( isspace( c ) ); if ( ( *ptr++ = c ) == '~' ) { *outbuf = '\0'; return; } for ( ;; ) { switch ( *ptr = getc( fp ) ) { default: ptr++; break; case EOF: #if defined(cbuilder) logf_string("Fread_string: EOF"); return -1; #else bug( "Fread_string: EOF", 0 ); exit( 1 ); #endif break; case '\n': ptr++; *ptr++ = '\r'; break; case '\r': break; case '~': *ptr = '\0'; return; } } } /*--- ElfHash --------------------------------------------------- * The published hash algorithm used in the UNIX ELF format * for object files. Accepts a pointer to a string to be hashed * and returns an unsigned long. *-------------------------------------------------------------*/ static unsigned long get_string_hash( register const char *key) { register unsigned long hash = 0, g; while(*key) { hash = (hash << 4) + *key++; if ( (g = hash & 0xF0000000) ) hash ^= g >> 24; hash &= ~g; } return hash % MAX_KEY_HASH; } /* Lookup the string in the boot-time hash table. */ char *temp_hash_find( const char *str ) { TempHash *ptr; unsigned long ihash; if( !fBootDb || !*str ) return 0; ihash = get_string_hash( str ) ; 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, const int len ) { TempHash *add; unsigned long ihash; if( !fBootDb || !*str || ( str <= string_space && str >= top_string ) ) return; ihash = get_string_hash( str ); 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 */ }