This is a white paper on BBS programming. It describes how the next generation of bbs100 will work.
The standard implementation of Unix BBSes today is pretty straight-forward; you simply fork() a process per online user. Doing this you run into standard issues like, how do you send a message to the other process (user), and how to access files when we are racing with others. These problems can be overcome, nothing new there. However, running such a BBS will put a certain strain on the system, especially when you have lots (30, 50, 100? 1000? even more?) of users online. There will be people logging on and off continuously, and the system will start to suffer under the tremendous load. This is bad, especially if you do not want to dedicate a machine to just serving a BBS.
The problem described above has been solved. As proven by earlier projects (BrintaBBS, bbs100), it is possible to serve all connections in just one process that serves all users. Because it is just one process, no forking is done, all memory appears to be shared automatically, and there no race conditions. This one process serves the input and ouput of all users, and sleeps when doing nothing. This causes it to consume very little (< 1%) of cpu time. It uses much less memory than the forking equivalent because all memory is shared, typically a few megs, compared to half a meg per process.
Of course, there is a drawback to this wonderful system. The server sits
waiting in an input loop, and then serves the connection that has any input.
The connection then 'continues where it left off' the last time it needed
input. This is implemented as a state machine -- which is exactly the drawback
of this kind of implementation; you need a function per state, and each state
is an input routine. I was very proud of the sophisticated solution I came up
with, but as you may be able to imagine, it can be a great pain to add new
code to this kind of program -- leading to bugs and memory leaks.
Bugs are fatal in this concept because when the server screws up, everybody
is affected because everyone is contained in the single process server.
When the server crashes, everyone goes down, as opposed to the classic system
where just one user would drop out.
Memory leaks are just way bad because it keeps on consuming until you restart
the BBS, and you don't really want any downtime at all.
These pains are in the design of the BBS. The only way to get rid of them,
is to redesign it and change something drastically.
What you really want is to be able to write normal looking code, instead of
having to write a state function that processes a character at a time.
You also want a mechanism for garbage collection. The system should keep track
of what memory is allocated to what user, and free up that memory when the
user process has 'forgotten' to do so.
So, let's do it.
Easy things first. The garbage collector isn't all that hard to implement, it's hard however to implement it in the existing bbs100 code because it is often not clear if the memory should be assigned to the system or the user. Therefore user and system should be abstracted even more, the system should run the user and not the other way around. The user should request memory instead of take it, and the system should serve memory rather than providing it. The same goes for access to files (which is, in fact, already abstracted in bbs100, which has a file cache).
Now for the problem concerning the code. You want to be able to write normal
linear, sequential code without having to worry about states and all.
But still, the code should be able to switch from current user to another
user on input.
I was wrestling with this problem until I attended a class to freshen up my
knowledge of Unix. And then it struck me, this system should be a Unix-like
scheduler. But how to schedule anything from within a Unix process? How to
contain multiple threads of execution within a single thread of execution?
The only way of doing this would be to jump back and forth through the program,
in a similar way the state machine implementation did. However, with jumps
all over the code it would be hard to maintain, just like the state machine
implementation is. Jumping would solve the problem though, but expirements
showed it became impossible to use local variables and it even became
impossible to return from a subroutine. In order to solve this, we would have
to save the execution stack of the current thread somewhere, load the saved
stack of another thread, and jump to run the thread.
I came up with the following solution: The way to actually run multiple threads
in a single Unix process is to do the scheduling of the threads yourself.
This is possible by accessing the processor registers and modifying them
correctly (which is probably the hardest part) and to reset them to your needs.
This is implemented as a (tiny) piece of machine-dependent code. Note that I
do not resort to using assembly, it can all be done in C, but the exact
implementation of the jmpbuf structure is machine-dependent. To clarify things,
it works a little like this:
void context_switch(void) {
if (!setjmp(curr_task->env)) {
memcpy(curr_task->stack, curr_task->env[SP], stack_end - curr_task->env[SP]);
curr_task = curr_task->next;
memcpy(curr_task->env[SP], curr_task->stack, stack_end - curr_task->env[SP]);
longjmp(curr_task->env, 1);
}
}
context_switch() is called from input routines, such as Getch(). The actual implementation is much more complex than this, because the next task may not have input ready yet. The actual implementation will have a real scheduler which closely resembles the design of a Unix scheduler. It will even count the cpu time spent by each thread and use that to do earnings based scheduling. The only thing missing will be preemption, but that won't be a problem and who knows, I may find a solution to do even that.
Now that we're back to running threads per user, we're also having race
conditions again. This is not as big as a problem as previously, because our
parallellism is not concurrent and it is not very fine grained.
We still have automatic shared memory, we do have to be careful however to
obey the rules and go through this kernel-like system instead of messing
around all by ourselves. This won't be much of a problem, because this system
should come with an API to provide functionality for the system.
In the end, the system will have many more features like tons of tuneable
parameters, a command console, loadable modules, and system threads monitoring
resources and collecting statistics. Adding client<->server functionality
won't be as much of a problem as it is with a truly monolithic server.
There aren't enough hours in a day however, so please mind that it may take
a while before I come up with something workable from the user's point of view.
The technique described above has actually been implemented in a prototype.
The code is extremely complex, because it comes down to writing an operating system
that controls all executing, sleeping, and suspended threads in the program context.
Gordon McMillan has had the same ideas about handling connections this way. His approach,
however, involves using Stackless Python, in
which he uses generators and continuation objects to jump forth and
back between micro-threads. He even implemented an FTP server this way. Read all
about it at his website.
See also: CBBX, a clustered version of BBX