Introduction
------------
My intention in this document is to roughly sketch the internals of
TeenyMUD, particularly the database management code. If you don't plan to hack
at the server at all, or if you don't know C, don't bother reading this.
This document has been updated to reflect changes relevant to the 1.2
release of TeenyMUD by jason downs, who just happens to be the one who coded
most of the changes relevant to this document.
Database Implementation
-----------------------
The database is implemented as an index, a cache and a chunks file
providing backing store for the cache. The index is implemented as a large
array (main_index) of pointers to 'descriptor' structs (things of type struct
dsc). An object number is used as an index into this array to locate the unique
descriptor associated with the object. A NULL pointer in the array indicates a
non-existant object (typically one that has been recycled). The descriptor
contains the following:
* a flags element, which contains both the internal (database
relevant), and external (mud relevant) flags
* a pointer to the name of the object
* a `next' element (used in contents/exits lists)
* a `home/dropto/destination' element
* an `owner' element (contains an object number)
As well as a pointer to where the remainder of the object data can be found.
If the object is in cache, this is a memory pointer to an 'obj_data' struct,
otherwise this is an offset into the chunks file. The flags field contains a
flag (the IN_MEMORY flag) which allows the system to differentiate between
these cases. Quite incidentally, the same descriptor structs are used to
describe free chunks in the chunkfile, and a list of these is used to maintain
data about the free chunks.
Descriptors are permanently resident in memory, thus the name, flags,
etc., fields of any object are rapidly accessible. Because database elements
such as the owner and home/destination/dropto are in memory, features like
database searches and room recycling are possible in this release. All the
rest of the data associated with an object is subject to being cached and
paged in and out. When an object is read in from disk, the information about
where it is on disk (the disk chunk it lives in) is copied into the obj_data
struct, and the descriptor no longer contains this data. When the object is
flushed from cache, if it is unchanged nothing happens, otherwise this disk
chunk is freed, and then a new chunk is requested (since the object may have
changed size while in memory) into which to write the updated object data.
The descriptor is then filled back in with data about where in the chunks
file the object data can be found. At any given moment, the descriptor
contains the actual size the object takes (or will take when written back)
on disk. It is this number that is used for cache usage estimates (thus,
cache usage is really only approximate, since in memory size is somewhat
different). This size data is also used by disk_freeze() when requesting a
disk chunk.
The code responsible for reading and writing objects to the chunks file
is in db/disk.c, and consists primarily of two routines, disk_thaw() and
disk_freeze(), each of which accepts a pointer to a descriptor. The former
reads the object data off disk into an obj_data struct, and returns a pointer
to this, the latter writes an obj_data struct to disk, and frees all the
associated memory.
The code responsible for managing the cache -- inserting things into
it, deleting things from it, trimming it back to the current cache size, and
purging it for dumps, lives in (surprise!) db/cache.c. Since it seemed like a
good idea at the time, the code which keeps track of where free chunks
('holes') reside in the chunks file also lives in here. Routines for making a
disk chunk free, and for acquiring a disk chunk to write data in to exist, and
are used by disk.c. These routines implement a worst fit algorithm, and do
amalgamate adjacent free chunks, so fragmentation should remain fairly well
controlled. See my remarks in doc/teeny.doc for how to de-frag a database.
For performance reasons, and since I didn't want to constantly maintain
the index on disk, the cache is NOT write-through. Thus, in the event of a
server crash, the chunks file is out of date, and the information about where
things are in it is completely lost. The option is to write objects back to
disk immediately when they are changed, and to update the disk copy of the
index at the same time. I deemed this an unacceptable performance hit.
Finally, the code for actually implementing the TeenyMUD database lives
in db/db.c. It includes a suite of routines for accessing elements of an object
completely transparently: set_str_elt(), set_int_elt(), set_lock_elt(),
get_str_elt(), get_int_elt(), get_lock_elt(). These accept an element code, and
return or set the appropriate element. They take care of allocating and freeing
memory for everything, with the exception of set_lock_elt(), which expects to
be supplied with a lock written into memory it can use (this is an anachronism,
for which I apologise). Note that get_str_elt() and get_lock_elt() return
pointers to the literal in-memory data. If subsequent database accesses cause
this data to be purged and written back to disk, these pointers will be
garbage. For this reason, the command handler calls cache_lock() to prevent
*any* data from being purged from the cache at the beginning of each command,
and calls cache_unlock() at the end. (and calls cache_trim() at that time to
trim the cache back if required). Several utility routines are also provided,
create_obj(), destroy_obj(), exists_object() and so on.
The main index is read in at server startup time by read_descriptors(),
and is written back during dumps by write_descriptors(). These functions read
and write all the descriptors and descriptor data in to the index file,
followed by a list of data about the free chunks in the chunk file. To bring
the db into synch, one needs merely to flush the cache, and then call
write_descriptors(). Note that doing this in the wrong order would be
disasterous, since many of the descriptors written will contain data on where
*in memory* the object data can be found, with no mention of the location in
the chunk file.
Game Database Layout
--------------------
Each thing in the database has a number of elements associated with it.
The usual strings (name/suc/osuc/fail/ofail/desc) and the usual integers
(pennies/owner/location/home/flags) are present, and do the usual things. Here,
usual means 'usual in the sense of TinyMUD.' Each object also has a contents
element, and an exits element. These both point to the first thing in the exits
or contents list of the thing, lists are constructed by chaining items together
with the 'next' element. This closely resembles the TinyMUD database, with the
difference that everything has an exits list. In particular, when a player
picks up an exit, it goes into the player's *exits* list, not into their
contents list. It is fundamentally this that makes the TinyMUD dump format
incompatible with the TeenyMUD text dump. See doc/convert.doc for instructions
on converting a TinyMUD database dump to a TeenyMUD database.
Besides this, there is nothing terribly exciting about the database
layout. The astute reader will notice, however, the distinct lack of a password
field on things. This is because most things don't have passwords, so I chose
to code the passwords as the second word of the player name, and then be
careful about things. This is responsible for much ookey code in the server,
and I sometimes regret this decision. Such is life.
Network interface
-----------------
The network interface is implemented in mud/tcpio.c and mud/misc.c (the
latter is so named because I couldn't think of anything better). These
implement a fairly simple server interface with minimal protection for the
server. tcpio.c is a hacked version of the UberMud network interface, by the
way. Many thanks are due Marcus Ranum for writing this beautiful code, which is
much less beautiful since I've gotten ahold of it. The code in mud/misc.c
implements command quotas on a per time slice basis, and is responsible for
slicing input from the network up into commands and dispatching them
appropriately. It is in mud/misc.c that WHO and QUIT are handled, as well as
connect and create (create player). The function match_who(), for matching
against the WHO list also lives in mud/misc.c, since it needs to fiddle around
with data structures private to this module.
Other stuff
-----------
mud/match.c contains the bulk of the routines for resolving strings into
database references. The code herein is somewhat ookey. Feel free to re-write
it. See the comments for how to use it, it's fairly straighforward with a few
icky bits that may or may not be well described in the code.
The TeenyMUD command set is implemented in mud/cmds.c, mud/buildcmds.c,
mud/speech.c, mud/wiz.c and mud/dbutils.c. Utilities used by these commands
for doing all sorts of things are contained in mud/cmdutils.c, mud/dbutils.c,
and mud/money.c. The command parser is in mud/command.c.
The command parser for TeenyMUD has been radically rewritten since 1.1
was released, and is now based upon two arrays of pointers to the command
function matching the appropriate command name (i.e., "dr", "dro", and "drop"
all call the function do_drop()). A player's input is compared, case
insensitively, to the names of commands stored in the arrays, and the function
matching the name is called, with the specified number of arguments passed to
it. Adding a command is rather simple. Just find the appropriate position
in the array (commands that begin with an '@' go in the *second* array, with
the leading '@' left out of the name), and following the format of surrounding
entries, put in the name(s) of the command, the function it should call, and
the number of arguments it requires. Note that the argument number is relative,
i.e., a function of zero arguments is passed only the executing player's object
number, a function with one argument is passed the player's i.d. and a
single command line argument, and a function with two arguments is passed
the player i.d. and two command arguments. (Argument one is everything after
the command name and before the first '=' encountered, and argument two is
everything after the first '=' in the command line).
mud/boolexp.c contains, basically, three routines: one for parsing
Boolean expressions into my nifty internal format, one for writing an infix
(text) version of an internal-format Boolean expression into a buffer, and one
for evaluating a internal-format Boolean expression. The internal format
consists of an array of integers, the first of which is how many integers
follow. The remaining integers constitute a simple RPN 'program' for the
evaluator. Positive numbers are interpreted as db references, and evaluate to
TRUE if the player is, or is carrying the numbered object. Negative numbers are
operations, AND, OR, NOT and STOP. A small stack machine in islocked() executes
the program, and returns the negation of the result. An artifact of this design
(and of my laziness) is that when an object is recycled, any lock it appears in
retains the reference to that object number. If and when the object number is
re-used, the lock will now reference that new object. The alternative is to
scan the entire db (sucking most of it off disk) and fiddle wildly with locks
on everything. Ick.
mud/main.c is the mainline, and also contains a few other high-level
take-this-goo-and-make-it-a-MUD type routines, like dump_db(), the console
handler and so on.
mud/notify.c contains some routines for telling players and groups of
players things.
mud/dbutils.c contains various db intensive commands and server
utilities. Most of the code within this file has been written with speed
in mind, and thus usually references the database using methods that
may not work so well in the future.
Hacking the Server
------------------
Most of the improvements in the 1.2 release were created out of
various hacks, so feel free to do so. I came up with the idea that made
such commands as @find, @stats, @owned, and @recycle out of the blue one
day, and had it implemented with twenty-four hours. I contacted Sean and
Andrew right after that, saying that I'd just revolutionized TeenyMUD.
That's when the 1.2 revision began.
Prior to my editing this document, Andrew had included some tips
for expanding the server, along the lines of pronoun substitutions and
strings like drop and odrop. I've not included those tips. If you wish
to learn how to hack the server, it's best to just start reading the code.
If you come up with really good ideas, contact
xibo@fido.econ.arizona.edu or send mail to the teeny-list.