[MUD-Dev] Orthogonality and invariants

[Miroslav Silovic]

Okay, I've been prompted by the previous programming language
discussion to write a quick essay. Feel free to dissect/flame. :)

First, in my experience, the main time-sink in writing MUDs is not
coding per se, it's debugging. In most 1,000,000 line applications,
you won't even notice a crash every 12 hours, or a memory leak that
fills the swap after a couple of days - this is because most
applications don't run for hours, let alone days. A MUD that crashes
daily is (in my experience) unplayable. This goes especially for
persistent MUDs that don't even see regular reboots more often than
twice per year.

So, MUD servers (and more generally, application servers) have
EXTREMELY severe stability constraint: they have to be able to run
stably for months, without visible bloat, fd leak, heap corruption,
thread forking, thread blocking, and all other types of weirdness that
plague applications.

Several MUD codebases already reached this plateaou (MOO, various
types of MUSH, Cold are those I know about for sure). I don't think
that a less stable codebase can compete at all (because crashes and
losses are just too annoying to bother with - especially with all
those stable MUDs laying around).

Now... the topic is achieving this stability. The main issue, IMHO, is
the lack of orthogonality, and orthogonality is lost each time you
have to spread functionality that logically belongs to the same unit
throughout the code (I'll use the word orthogonality to mean
funcionality separation along logical, rather than pragmatic
boundaries).

Let's start with a canonic example: memory management in C. Each time
you need a chunk of memory, you request it from the system, and each
time you don't need it any more, you free it. The problem, as anybody
who tried to debug memory leaks can tell, is that you have to code
memory management each time you want to deal with memory -
i.e. throughout the program. Wouldn't it be nicer if you could just
point at a big chunk of code and just say, "That thing manages my
memory. Touch only if memory management is broken, and then that's the
place responsible." -- this is exactly what garbage collectors do.

This example illustrates one related issue: dynamic invariants
(namely, the statements that must hold true, and can not always be
checked just by reading the program source). The C malloc/free
paradigm sets one such invariant: 'each path of control that allocates
a memory block must contain a free with that same block' (it posts
some more dynamic invariants, for example, 'a block passed to the free
call must have been allocated with malloc call and it must not have
been already freed', but let's keep the focus). Now, since C compiler
can not check this (and it'd require really hellishly powerful lint,
as well as limits on the use of malloc/free, to check this
statically), the programmer has to worry about this each time.  Since
programmers *always* make mistakes, this invariant will *not* hold
true in a freshly written code.

The lack of orthogonality, in this case, manifests itself in the fact
that in practice it's highly nontrivial to check for dynamic invariant
breakage.

So, let's state two principles of orthogonality: 

1. Whenever it's possible to reorganise the code so that distributed
functionality can be sequestrated into a module, it should be done so,
even when the cost is a (reasonably small) loss of performance.

2. The code should not have dynamic invariants.

There are also some classical orthogonality principles (I assume
they're well-known to the more technically oriented people here):

3. Functions shouldn't have side-effects (and more generally, broader
language constructs, such as objects, classes, or defmacro constructs
in LISP, shouldn't have side-effects)

Okay, to conclude, here are some common sources of orthogonality
breaks:

   Resource management
   -------------------

The C example above can be extended to cover broad range of idioms:
malloc/free, mutex lock/unlock, file open/close, socket accept/close,
and socket connect/disconnect. In each of these cases, there are two
functions (let's call them mumble and unmumble), with the following
dynamic invariant:

	each path of control that contains mumble(object) must
	contain unmumble(object) such that it executes after the
	object has been mumbled, and such that there is no other
	mumble or unmumble between it and the opening mumble.

Now, there are two ways of removing this invariant: First, for
malloc/free pair, you can use garbage collector. It works by taking
the snapshot of your system and finding all the allocated resources at
that moment, and then finds the resources that the code can't use
(because it doesn't have references to them). Those resources get
released.

The other way is with construct in LISP:

(with-mumbled-object (object)
    code...)

This construct does mumble(object), executed the code, and then
unmumbles the object. If this is the only way for the object to ever
get mumbled, this code will never break the invariant.

This is also how constructor/destructor pairs work in C++.

Now, if your system supports nonlocal exits (throws, exceptions,
conditions - whatever name you're used to), with will have to catch
the throw, unmumble the object, and pass the throw onward (this is why
exceptions in C++ cause the codesize to increase by 30-50% - every
block that has constructor/destructor pair will also have to trap the
exception and handle the cleanup before passing it on). In my
experience, this is the main reason to use garbage collection - you
can have exceptions without unwinding (more or less) each block that
has variables in it.

Note that reference counting does NOT solve the memory management
issue - it simply moves the issue from malloc/free (pointer) to
grab/ungrab (reference). Also, circular references HEAVILY complicate
the issues - but certain MUD languages are designed to make circular
references impossible.

   Object persistence
   ------------------

All MUDs have to handle persistence in some way - if nothing, they
have to save the snapshot of all the players before each reboot. Now,
the raw LPMUD handles this by providing save function (I'm not sure if
it's in the LPMUD driver or mudlib). So, if you want the object saved,
you do something like save(object), whenever the object has changed.

So, here's the dynamic invariant:

	each persistent object that has been changed has to be saved.

Breaking this invariant causes the well-known

	Bubba shouts 'wheres my gear?!?!?!'

Again you can implement persistence library, one that places each
loaded object on a list that is guaranteed to get saved before the
process terminates.

However, there is another, related issue: how to automate object
loads? If your objects are indirected (i.e. implemented via some
abstract reference type), you can just check for the load status each
time you transform the reference to the actual object pointer (Cold
and MOO do this). You can also use object pointers that point to
write-protected pages and then load the objects from segfault handler
(this is done by Texas Persistent Store, and despite the technical
coolness, it's unfortunately quite slow).


   Database integrity
   ------------------

Each working MUD has a large number of invariants that are rarely, if
ever, checked (remember, in C, ASSERT macro is your friend). For
example,

	for each container, the location of each object within the
	container must be the container itself

It's quite interesting that some languages (Eiffel) actually support
class invariants - statements that are true for each instance of the
class and get checked on a regular basis. Languages with a MOP (Common
LISP and the new, yet-to-be-released Python) can implement this on top
of their existing object systems. While class invariants don't
eliminate dynamic invariants, they at least cause the program to
complain now rather than later.

   Transactional integrity
   -----------------------

While forgetting to unlock the mutexes falls under resource
management, forgetting to lock them in the first place is a beast in
its own right. There have been some articles on this list (including
those by me and JCL) that cover this. The invariant here is

	non-reentrant code should be protected by a mutex

My solution to this is to put mutexes on each object and handle the
deadlocks automatically - recent post on dgd mailing list suggests
that they took the same approach; JC instead makes all the code
reentrant by copying and timestamping objects). I'd be really
interested in a solution to this that is generic (i.e. would work for
any application server, not just a MUD server), and that doesn't have
performance penalty of the solutions above.

--
How to eff the ineffable?



_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev