[nos-bbs] Nodes command - figured out the crashes - replacing qsort

[maiko at pcs.mb.ca]

Greetings all,

I think I have solved the problem with JNOS crashing when users are issuing
the 'Nodes' command. My JNOS development system is currently showing 525
nodes and it's perfectly fine. I can list them over and over without it
crashing - both from the BBS prompt, and from the console, and sysop mode.

Of course, one may question why one needs 525 nodes, but I did that more
for testing purposes, ie: 'netrom minquality 100'.

Getting a bit technical, this comes down to a stack overflow problem, which
appears to be caused by the qsort() function call. In linux anyways, qsort()
is a recursive function, so the more nodes to sort, the more stack it can
possibly use (it doesn't always).

The problem then becomes how much stack should a process be given when it
is created, knowing that a call to a function like qsort can make the
stack suddenly use up ALOT of space.

Barry also gave a few thoughts on this in earlier emails, and thanks to
you Barry for getting me to focus on the qsort call.

To solve the problem originally, I bumped up the starting stack size of
the process that calls the 'Nodes' command, but that is more a bandage
than anything, and it doesn't help any with regard to memory usage in
the DOS implementations.

Instead, I found an ANSI-C version of qsort that does NOT use recursion,
but rather uses explicit stack operations. The results are amazing. The
stack size of the process calling the 'Nodes' command hardly wavers, and
it's quicker supposedly than the qsort() distributed by linux.

The next release of JNOS will NOT use the system qsort() call, but rather
a new function - j2qsort () - based on this ANSI-C version. A new source
file, qsort.c, will be added to the JNOS source, and to the makefile.

So far the results are very encouraging. This is a problem that I believe
has plagued *us* for a long time. I think it has now been solved, and I
encourage the other NOS developers to try the ANSI-C version out.

Here's the link to the page :

  http://oopweb.com/Algorithms/Documents/Sman/Volume/Quicksort.html

Take a look under the section, 'Implementation in C'.

Maiko Langelaar / VE4KLM