<html>
<head>
<title>Memory Management Overview</title>
<link rel="stylesheet" type="text/css" href="doc.css"
title="Documentation Standard Style">
</head>
<body bgcolor="#ffffff">
<table class="main" width="600" border="0">
<tr><td>
<div align="right">
DalekenMUD 1.12 documentation.
<br>Updated 7 June 2000.
<br>Based on original Envy 2.2 documentation.
</div>
</td></tr>
<tr><th class="heading">
<h1>Memory Management Overview</h1>
</th></tr>
<tr><td>
<p>Daleken contains the following memory regions: run file memory; stack;
string space; and permanent space. The approximate sizes of these regions
are:</p>
<pre>
Runtime memory ???
String space 1279 k
Permanent space 1345 k
TOTAL 3612 k
</pre>
<p>Note that the value for string space can be modofied by changing
<code>MAX_CHUNKS</code> and the permanent space taken will depend on how many
areas you are running as well as the number of players on. The total here
may depend on the operating system, but the string and permanent space are
about this value all the time.</p>
<p>One thing to consider with permanent memnory is that memory that is
claimed is recycled by the mud, so for a short time it will spend time
grabbing memory, then the amount used will settle. The mud had been running
for an hour before taking these measurements so there shouldn't be too much
movement. See below for details on permanent memory.</p>
</td></tr>
<tr><th class="heading">
<h2>Run File Memory</h2>
</th></tr>
<tr><td>
<p>The Daleken executable file has a large amount of code, optimised and
stripped this weighs in slightly under 1Mb, with full debugging symbols, this
bloats to around 2.7Mb.</p>
<p>The following command compiles Daleken with optimised code.
<blockquote><code>
make -k optim >&! make.out
</code></blockquote>
This takes a fair while longer than the standard make.</p>
</td></tr>
<tr><th class="heading">
<h2>Stack</h2>
</th></tr>
<tr><td>
<p>We have never measured stack usage, but estimate it's somewhere between
600Kb and 1Mb. Daleken has a wide, shallow calling tree. The largest
consumers of stack memory are local buffers of size
<code>MAX_STRING_LENGTH</code> and the functions for mud programs.</p>
<p>If you port Daleken 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.</p>
</td></tr>
<tr><th class="heading">
<h2>String Space and fread_string()</h2>
</th></tr>
<tr><td>
<p>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 will be used for new string
generation.</p>
<p>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).</p>
<p>When <code>fread_string()</code> 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.</p>
<p>If <code>fread_string()</code> 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.</p>
<p>After area-file loading is over, <code>fread_string()</code> is also used
to read player files. In this case, new strings are not appended to string
space, but instead are simply handed to <code>str_dup()</code>. Thus the
amount of string space used is fixed at area-file loading time.</p>
<p>The functions <code>str_dup()</code> and <code>free_string()</code> take
advantage of string space. If a string being duplicated is in string space,
<code>str_dup()</code> simply returns the same pointer while increases its
internal counters. If a string being freed is in string space,
<code>free_string()</code> will:</p>
<ol>
<li>look for it in overflow and if it is there free the memory.</li>
<li>look for it in string space and mark it as free to be defragged and
reused.</li>
</ol>
<p>This strategy not only saves megabytes of memory through string re-use,
but also saves processor time as well.</p>
<p>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 <code>MAX_STRING</code>. (The hash chains don't require
contiguous allocation).<p>
<p>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.</p>
<p>After boot time, the unused end of string space is used for new strings
the game might generate. This amounts to about 250k in Daleken. 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.</p>
<p>If you add a lot of areas you may need to increase
<code>MAX_STRING</code>. Again, Daleken will tell you when you've run
out.</p>
<p>Envy 2.2 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.</p>
<p>Now, overflow strings are shared until not needed and then freed using
<code>free()</code>. Strings not needed in string space is cleared and the
memory chunks are defragmented for use again.</p>
<p>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 <code>MAX_CHUNKS</code> in <code>config.h</code> to about 100k over
the string space needed at boot time.</p>
</td></tr>
<tr><th class="heading">
<h2>Permanent Space - Heap</h2>
</th></tr>
<tr><td>
<p>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.</p>
<p>This space is dynamically allocated from <code>calloc()</code> in large
blocks, which are carved up and handed out as needed by
<code>alloc_perm()</code>. As distributed, Daleken uses about 1250k of
permanent space.</p>
<p>Unlike string space, permanent space grows on demand;
<code>alloc_perm()</code> calloc's and carves up as many blocks as needed as
the game runs.</p>
<p>You can adjust the block size by changing <code>MAX_PERM_BLOCK</code> in
<code>db.c</code>. Adjustment will have only a minor effect on space and
time usage. If you port Daleken to a new system with a 64k or 32k limit on
<code>calloc()</code> size, you could simply change
<code>MAX_PERM_BLOCK</code> to the largest calloc'able block on your
system.</p>
<p>Daleken never calls <code>free()</code> 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 <code>free()</code>,
and it's faster to allocate a block from a free list than to allocate one
from <code>calloc()</code> or <code>alloc_perm()</code>. Most of the
structure types have their own free lists: <code>char_free, obj_free,
affect_free, </code>et cetera.</p>
<p>Variable-sized blocks don't fit the per-structure-type free-list model.
The functions <code>alloc_mem()</code> and <code>free_mem()</code> 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.</p>
</td></tr>
</table>
</body>
</html>
