EnvyMud Release 2.2
Friday, 14th February 1997

Kahn		envy@envy.com



=== Memory Management Overview

Envy contains the following memory regions:  run file memory; stack;
string space; and permanent space.  The approximate sizes of these
regions are:

    Run file memory	 606 k
    Stack		 584 k
    String space	1664 k
    Permanent space	1944 k
    TOTAL		4798 k



=== Run File Memory

The envy executable file has about 606k of code.

This size is small compared to the total size, and there is little you
can do to change it.



=== Stack

We have never measured stack usage, but estimate it's somewhere
between 580k and 600k.  Envy has a wide, shallow calling tree.  The
largest consumers of stack memory are local buffers of size
MAX_STRING_LENGTH.

If you port Envy to a machine with 1024k or less of stack, you should
instrument your object code with stack-usage measurements.  Most
compilers for machines in this range have an option to do this.



=== String Space and fread_string()

At boot time, the function fread_string() is used to read in
~-delimited strings from area files.  These strings are stored into
string space.  After all of the area files are read in, that string
space area is read-only for the duration of the program.  The excess
is might be used for new string generation.

Duplicate strings are stored only once into string space; hashing is
used to achieve this.  The hash code for a string is simply its
length.  Each string in string space is prefaced with a backpointer to
the previous string with the same hash code.  (Aliasing through a
union is needed to read and write these pointers, because they can
start at any byte boundary, and thus are misaligned).

When fread_string() reads a new string, it creates the string at the
end of string space.  It then finds the first hash pointer for that
length and follows the thread of hash pointers, looking for an already
existing string with the same contents.  Strings in the hash chain are
checked newest-first, which benefits from the usual construction of
area files, where duplicates are usually duplicates of something seen
recently.

If fread_string() finds that the new string is a duplicate, it simply
discards the new string and returns a pointer to the existing string
while increases its internal counters.  If the string is new, it
leaves it at the end of string space, fills in the new hash pointers,
and returns the new string.  If we overflow the string space, it makes
room and marks it as overflow.

After area-file loading is over, fread_string is also used to read
player files.  In this case, new strings are not appended to string
space, but instead are simply handed to str_dup().  Thus the amount of
string space used is fixed at area-file loading time.

The functions str_dup() and free_string() take advantage of string
space.  If a string being duplicated is in string space, str_dup()
simply returns the same pointer while increases its internal counters.
If a string being freed is in string space, free_string() will:

1)  look for it in overflow and if it is there free the memory.
2)  look for it in string space and mark it as free to be defragged
    and reused.

This strategy not only saves megabytes of memory through string
re-use, but also saves processor time as well.

Thus a cheap method is needed for deciding whether a given string is
in string space.  This is one reason why strings are stored in one
contiguous region of size MAX_STRING.  (The hash chains don't require
contiguous allocation).

Collecting all strings into one region has another advantage: locality
of reference.  Most strings are unused most of the time.  Because they
are not interspersed with other dynamically allocated memory, a
virtual memory operating system can page out almost all of the string
space without affecting performance.

After boot time, the unused end of string space is used for new strings
the game might generate.  This amounts to about 100k in Envy 2.2.  On
a VM system, unused space is paged out quickly, so it doesn't hurt to
leave it alone.  If the new strings generated by the game overflow
string space, you will be notified and the game will make do.

If you add a lot of areas you may need to increase MAX_STRING.  Again,
Envy will tell you when you've run out.

Envy 2.2 has changed its string memory management from Envy 2.0
through Fusion's Shared String Manager v2.2.  Previously new strings
generated by the game which overflow string space are lost and cannot
be shared.

Now, overflow strings are shared until not needed and then freed using
free().  Strings not needed in string space is cleared and the memory
chunks are defragmented for use again.

There is some gain in performance with the improved string management.
Though we lose it all once we start managing overflow.  It is
suggested setting MAX_CHUNKS in 'merc.h' to about 100k over the string
space needed at boot time.



=== Permanent space

This space holds everything else: all of the area file non-string
data; all of the created mobiles and objects; descriptor and player
character structures; you name it.

This space is dynamically allocated from calloc() in large blocks,
which are carved up and handed out as needed by alloc_perm().  As
distributed, Envy 2.2 uses about 1944k of permanent space.

Unlike string space, permanent space grows on demand; alloc_perm()
calloc's and carves up as many blocks as needed as the game runs.

You can adjust the block size by changing MAX_PERM_BLOCK in 'db.c'.
Adjustment will have only a minor effect on space and time usage.  If
you port Envy to a new system with a 64k or 32k limit on calloc()
size, you could simply change MAX_PERM_BLOCK to the largest
calloc'able block on your system.

Envy never calls free() to return memory when handling permanent
memory.  Instead, memory is recycled for future use.  This has two
advantages: it's faster to recycle a block than to call free(), and
it's faster to allocate a block from a free list than to allocate one
from calloc() or alloc_perm().  Most of the structure types have their
own free lists: char_free, obj_free, affect_free, et cetera.

Variable-sized blocks don't fit the per-structure-type free-list
model.  The functions alloc_mem() and free_mem() manage blocks of
arbitrary size.  They actually work by maintaining fixed-size lists
for just a few supported sizes and rounding requests up to a supported
size.  This is extremely fast; because there are so few variable-sized
blocks, the space penalty is inconsequential.