/****************************************************************************** * 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 *, int * ); 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 1000 void init_string_space() { BufEntry *walk; int i; string_space = (char *)malloc( MAX_STRING ); if( !string_space ) { bug( "[SSM] Cant allocate shared string space.", 0 ); 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; } } 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. */ 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.", 0 ); bug( (char*)&ptr->buf[0], 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.", 0 ); bug( str, 0 ); } 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, int *status ) { char buf[ MAX_STRING_LENGTH*4 ]; char *ptr = buf; char c; *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++; *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: bug( "Fread_string: EOF", 0 ); 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 ) { TempHash *ptr; int len; int ihash; if( !fBootDb || !*str ) return 0; len = strlen( str ); ihash = len % MAX_KEY_HASH; 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 ) { 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 */ }