🚀 go-pugleaf

(This is a long one, so be patient)


About 2 years ago (maybe longer), I posted the following article
to this newsgroup:



|I have been working on a Xinu port to an Omnibyte 68000 based computer
|on and off for awhile, and I have finally got it to work.
|I ported from the Version 7.1 Sun3 code which we obtained from Purdue.
|Along the way I uncovered some bugs, and I made some additions which
|may be useful to somebody.
|
|The Omnibyte is a very basic 68000 based Multibus board.  It has 512K
|ram, 2 6850 serial chips, a 6840 timer, and a couple of parallel ports.
|We use these boards at Systech for test fixtures.
|
|For my port, I stripped out all of the networking code, and all of
|the file system stuff.  I was interested in getting a bare-bones system
|up and running.  The port went pretty fast, and in the beginning
|the most difficult thing for me was getting the code compiled and running
|under our Microtec 'C' development tools.  The shell came up quickly,
|and after a few tweaks of my tty driver, Xinu was up and running.
|
|The difficult part of the port was when I attempted to get a shell 
|session going on both of the serial ports.  The Xinu code, as I got it,
|assumes that there will only be a console port and thats it.  I
|needed to make many additions in order to get 2 login sessions going
|simultaneously.  If anyone is interested in the details involved with
|this, please E-mail me.
|
|So I finally got 2 shells going at the same time, and the next logical
|step was to blast output on both channels to see how the OS performed.
|This was where I really got into the nitty-gritty debug stuff.
|
|I had a login session enabled on both the console and "ttyb".  And I
|added a very simple shell command which blasted output to "stdout".
|The program was an endless loop of 26 "writes", and each write was for
|50 characters.  So I would log on to the console then log on to ttyb,
|and start things going.
|
|I started up "ptest" (the blast output program) on the console and 
|output blasted at 19.2kbaud on the terminal.  I typed in "ptest"
|on ttyb and nothing happened--it just kind of hung there.  After
|messing around with it for awhile I discovered something very
|surpising.  If I hit the return key on ttyb where output was hung up,
|about 20 characters would pop out.  And if the return key was held
|down long enough, output would begin to flow constantly.  It was
|almost like "priming the pump": you had to hold the return key down
|for awhile to get it going.  The kicker though, was that once it got
|going the output rate was severely decreased.  Both terminals were
|configured for 19.2kbaud and the output looked like about 4800 baud.
|Something was definitely wrong!  Typing a ^S on one of the terminals
|would allow the output on the other terminal to blast at 19.2k, but
|when ^Q was hit, the output rate went to pot again.  Sometimes the
|output would not start back up, and the return key had to be used again
|to "prime the pump".
|
|It took me a good 2 days to debug this problem, and I uncovered a
|nasty little bug.  The bug is in the transmit interupt routine "ttyoin".
|Here is the section of code at fault:
|
|           if ((ct=iptr->ocnt) > 0) {
|                 zptr->zscc_data = iptr->obuff[iptr->otail++];
|                 --iptr->ocnt;
|                 if (iptr->otail >= OBUFLEN)
|                        iptr->otail = 0;
|                 if (ct > OBMINSP)
|                        signal(iptr->osem);
|                 else if ( ++(iptr->odsend) == OBMINSP) {
|                        iptr->odsend = 0;
|                        signaln(iptr->osem, OBMINSP);
|                 }
|           } else
|                 ttyostop(iptr);
|
|The statement:
|
|                 if (ct > OBMINSP)
|                        signal(iptr->osem);
|
|is the one in error.  When a process is doing heavy output, the output
|buffer will fill up quickly and the process will be taken off of the
|ready queue.  iptr->ocnt will increase very quickly (the upper-half
|code increments it for every character put into the buffer) and will approach
|the value of OBUFLEN.  It will certainly be greater than OBMINSP (the
|low water mark), so the signal statement will be executed for every
|character that is transmitted.  This will happen as long as the process
|keeps filling the output buffer, which in my test case, it will do
|endlessly.  What we end up with is a process taking itself off of the
|ready queue for every (single) character that it stuffs in the output
|buffer, then waking back up for every character that is transmitted.
|That is some pretty serious thrashing going on there DUDE!
|
|The solution is straightforward:
|
|                 if (ct < OBMINSP)
|                        signal(iptr->osem);
|
|Which was the intended behavior.  After further investigation and trial
|runs, I could find no real use for iptr->ocnt.  I got rid of the references
|to ocnt and  modified the code further to look like this:
|
|           if ((ct=semaph[iptr->osem].semcnt) < OBUFLEN) {
|                 aptr->trdr = iptr->obuff[iptr->otail++];
|                 if (iptr->otail >= OBUFLEN)
|                        iptr->otail = 0;
|                 if (ct > OBMINSP)
|                        signal(iptr->osem);
|                 else if ( ++(iptr->odsend) == OBMINSP) {
|                        iptr->odsend = 0;
|                        signaln(iptr->osem, OBMINSP);
|                 }
|           } else
|                 ttyostop(iptr);
|
|This version of the code is more in line with the code found in the
|LSI version of Comer's book.
|
|So all in all, I am pleased with the Xinu port.  It is a neat little
|system to work with.  I plan to port next to one of Systech's
|cluster controllers.  Each cluster controller has an arcnet chip set,
|a very high performance 8 channel octart, 128k of ram, and a 68000 to
|run the show.  I am especially anxious to get the networking code
|implemented and running under arcnet.  What'dya say there Vern?
|
|Please mail me if anybody out there has any questions about my work.


Here is the relevant code from Xinu 7.9:

    if ((ct=iptr->ocnt) > 0) {
        /**foob1++ = iptr->obuff[iptr->otail];*/
        zptr->zscc_data = iptr->obuff[iptr->otail++];
            --iptr->ocnt;
        if (iptr->otail >= OBUFLEN)
            iptr->otail = 0;
#ifdef NOTYET
        if (ct > OBMINSP)
#endif
            signal(iptr->osem);
#ifdef NOTYET
        else if ( ++(iptr->odsend) == OBMINSP) {
            iptr->odsend = 0;
            signaln(iptr->osem, OBMINSP);
        }
#endif
    } else
            ttyostop(iptr);
 


And here is the relevant code from Xinu 8.0:


    if ((ct=iptr->ocnt) > 0) {
        zptr->zscc_data = iptr->obuff[iptr->otail++];
            --iptr->ocnt;
        if (iptr->otail >= OBUFLEN)
            iptr->otail = 0;
#ifdef NOTYET
        if (ct > OBMINSP)
#endif
            signal(iptr->osem);
#ifdef NOTYET
        else if ( ++(iptr->odsend) == OBMINSP) {
            iptr->odsend = 0;
            signaln(iptr->osem, OBMINSP);
        }
#endif
    } else
            ttyostop(iptr);
 

Here is the text from Comer's Operating System Design (Vol I, LSI),
section 12.7.1:

    Ttyoin uses a technique called watermark processing to minimize
 overhead in the interaction between upper and lower halves of the
 driver. The technique is worthy of comment because it is both
 fundamental and popular.

    To understand the motivation for watermark processing, suppose for a
 moment that the lower-half called signal each time it removed a
 character from the buffer.  Because the processor can generate characters
 much faster than the SLU can transmit them, the output buffer usually
 remains full with a process waiting for the output semaphore.  When
 ttyoin removes a character, it signals the semaphore, causing the first
 waiting process to deposit a character and continue processing.  Because
 programs often write more than one character at a time, the process that
 was waiting has a high probability of producing another character
 quickly and ending up waiting for the semaphore again before the
 transmitter has time to transmit a single character and interrupt again.
 The problem is that rescheduling is relatively expensive; executing it
 on every character interrupt deprives other ready processes of CPU time.

    To lower the rescheduling overhead, ttyoin runs in two modes.  It
 continues processing normally until it finds the buffer filled beyond
 the high watermark at which time it switches to delayed mode and stops
 signalling the output semaphore.  While in delayed mode, it accumulates
 the count of times it should have called signal.  Finally, when the
 buffer has drained to the low watermark, ttyoin calls signal to make
 up for the signal it has skipped.  Delaying when the buffer is nearly
 full introduces hysteresis, because it does not reschedule until some
 minimum number of buffer position are available.  Thus, the process
 that was generating output can run for a while before the buffer fills and
 the upper-half forces rescheduling.

    In the code, constant OBMINSP determines the high and low watermarks.
 When less than OBMINSP space remains, ttyoin switches to delayed mode,
 and delays exactly OBMINSP times before switching back to normal mode.

-----end section-----


My speculation on why this bug endures is that the output from ex2.c,
(the 2nd example of chapter 1) looks a little strange when the
tty code is implemented correctly.  When it is implemented in-correctly
(see the examples above) the output from ex2.c is a never-ending
alternating sequence of A's and B's:

ABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABAB.......


Here is the output from ex2.c when ttyoin is implemented correctly:

(Note that I've got OBMINSP set to 40)


BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB...........

I guess to the casual observer the ABABABABA sequence should be the
correct one, but its not.

Anyway, I guess that's enough blabbering about this little bug.
Anybody care to discuss this further??


JR



-- 


   /------------------------------------------------------------------\
  |  John Reed                           {ucsd,uunet}!pacdata!johnr    |
  |  Pacific Data Products               johnr%pacdata.uucp@ucsd.edu   |
  |                    ---------------------                           |
  |  George Herbert Walker Bush, with the letters re-arranged spells:  |
  |                                                                    |
  |                 Huge Berserk Rebel Warthog                         |
  |                                     -- From Cosmic Trigger II      |
   \------------------------------------------------------------------/