2010.02.26
There are still some quirks during testing of this, like
a "device full" error from cat when I start a cat writer
before a reader and give a larger-than-buffer line.
But at least I can play with it. I probably should print
out the semaphore counter values for closer debugging.
2010.02.26
Notes from the source code. Many comments below are
debug ramblings on the wrong track.
* 2010.02.26
* The fix to buffer level blocking appears to be working fine.
* One quirk is that there is no way to tell the reader that
* the fifo is done. I don't have an end-of-file protocol
* using the blocking read.
*
* 2010.02.26
* Awk! All my speculation below about improper blocking is wrong!
* Or at least completely off track. The problem is that my
* semaphores are set up for doing character level blocking
* but the code is set up to do buffer level blocking. A simple
* fix is to just initialize the fullQ semaphore to 1 instead
* of MAX_BUF -1. Sigh.
*
2010.02.25
Is the writer blocking when the buffer fills? It
isn't clear. The device full seems to come from
cat >mydevW when it tries twice to write and
the same number of characters are discarded
two times in a row. Why wouldn't the writer
block? Hmmmm. I seem to have already answered
this question in the header notes of the
source file chardev.c in this directory. The
driver doesn't actually block on fifo buffer full!
It blocks if the buffer is *already* full. But if
it fills during the enQ, then it returns to the
caller with a count of chars written. The caller
turns around and calls the device again to finish
the write... and should block... but doesn't. Hmmm.
Ah, yes, I've already answered this also in the
source code header notes. The Kernel 2.4 is non-preemptive,
so the kernel code will keep working until the user timeslice
is over. Then it will block. The testing behavior
confirms this.
2010.02.25
Well, the only part that doesn't seem to work as
expected on command line testing is that writing
to the fifo with an overflow will cause a device
full error from cat and the overflow characters
will be thrown away. Note that the characters
in the buffer will not be printed on the other
end either because the head -n 1 mydevR will
not print a line without a newline at the end
and when we filled the buffer, there was no
newline at the end. The read_device shows
that the characters were dequeued.
2010.02.21
I don't understand this program yet! What uniform
behavior does the fifo present to the readers and
writers? How does the reader and writer behavior
differ or not when it is command line or programmed?
What is the interaction between line buffering
in the command line version and the fifo? How
about creating a named pipe (a fifo) and testing
it to see how it is supposed to work!?
2010.02.20
A good stress test of this is to write a program that
pumps characters into the queue with one process and
pulls characters out of the queue with another
at full speed to see if integrity can be maintained.
Then take out the spinlock and see if the buffer gets
corrupted. I've still got to fix the enQ dumping
of characters. Not sure how to do that yet.
2010.02.20
Well, it seems to be sort-of working. When I do
echo 12345 >./dev/mydevW
it puts things into the queue. When I subsequently do
cat ./dev/mydevR
in another terminal, I get those things back but
the reader blocks waiting for more (probably because
cat is waiting for an end of file; I shouldn't use
cat). I again did
echo 789 > ./dev/mydevW
and when I looked at the reader terminal, I saw those
character come on out and the reader blocks again.
Finally I ^C the reader and I got a 0 bytes read
back and it quit. This is a little tricky, because
I'm using interruptible semaphores and when I ^C out
of the blocked reader, I'm aborting the reader from
the semaphore queue and returning from the
down_interruptible without acquiring the lock. Yet
the way I've (improperly) coded the down, it falls
through and accesses the queue as if it had the
lock! But the queue was empty, so a 0 bytes was
returned and the read returned normally.
First, I need to fix the down_interrruptible
so I can handle interrupt signals. Then I need
to test this fifo without using a cat or
figure a way to send an EOF into the fifo from
the writer end.
One more quirk. When I put long strings into
the fifo in one long string, it still throws
away the extra characters rather than blocking
and reading the rest later. This is because I call
the enQ with the longer string and enQ just throws
the extra characters away and happily returns.
2010.02.20
Now add the reader and writer blocking. This should
be easier to test.
2010.02.20
This version behaves well with separate writer and
reader devices for the fifo, but has not been stress
tested to see if the mutual exclusion on the
circular buffer works properly. Also, the guarantee
of only one reader and one writer needs to be stress
tested, although that can be tested in the previous
experiment.
2010.02.20
Ok, this is version 2 discussed below. I will have
only one reader and one writer. I will not block
either reader or writer. Writers will have even
numbered devices (eg, 254) and readers for each
writer to device n will have the odd device
number n+1 (eg, 255). I'll enforce one writer
by an atomic lock on write open and similiarly
enforce one reader by an atomic lock on read
open. The write device only supports writes
to the circular buffer and the read device only
supports reads form the circular buffer. I'll
use a spinlock to enforce mutual exclusion on
the circular buffer between the shared reader and
writer access to the buffer. The writer can
write to the fifo device even if the read end
is not open. The reader can read from the fifo
even if the write end is not open, but a zero
byte read will be returned. Or maybe I'll return
an error to the reader if the writer end is
not open.
2010.02.20
Conclusion: I'll make three versions. This first
version is a cleaned-up command line fifo discussed
below. The next versions will use a spin lock on the
shared fifo buffer. This still leaves a pile of
unresolved design decisions. To get a taste of
the considerations, do man 2 pipe and man 2 fifo.
Do you allow multiple processes to access one or
the other end of the fifo, or both? Do you restrict
the fifo to a single reader and a single writer? Do
you use a separate device number for writing vs
reading (as Nutt suggests)? What do you do if
one end is open but the other is not?
So version 2 and 3 will only allow one process to
write to the fifo and one process to read from the
fifo. Version 2 will bounce the writer on full and
bounce the reader on empty. Version 3 will block
the reader and writer, giving a fully flow-controlled
bounded buffer producer-consumer fifo. Someday,
anyway. I don't yet see how to handle the
synchronization of opening the fifo by both the
reader and writer. The man fifo page discusses the
various options, but suggests that normally one
end blocks until the other end opens.
2010.02.20
This version creates a single device file for both writing
and reading and using
a simple atomic lock on dev_open, replacing the unsafe
locking of experiment 3. This is sufficient as long as I'm
only using the fifo from the command line where every access
to the fifo involves an open, a read or write, and a close.
Note that any command line process can write to the fifo
and any can read from the fifo, whether that makes sense
or not. Writes continue until all characters are written
or the buffer is full and then characters are dumped.
The command line reads like cat read empty the entire
buffer at once. This code isn't really set up for
C-program access to the fifos.
2010.02.16
Hmmm. It seems to me what this program really needs is locking
around the circular buffer device read and write! After all,
it is clearly a shared device acting like the bounded buffer
synchronization problem which requires three locks, one for
the buffer and one each for wp and rp buffer pointers.
2010.02.16
This is experiment 4 derived from experiment 3. I'm just going
to try using kernel atomic_t types for atomic locking of
the dev_open synchronization variable in this experiment 3
code. If that works, then I might try putting in automatic
system call to create the new device file right in the
init_module code.
2010.02.12
Fixed two problems. Here's the comments in the code.
* I fixed two bugs. First, I accidently typed an index i in qbuf[i]
* in the put_user instead of the proper index qbuf[rp].
* Second, I fixed an infinite write loop that occurred when the
* buffer to write had a length greater than the circular buffer.
* This caused the caller to persistently call back waiting to
* hear that all of the buffer length of characters had been
* written to the device. To fix this I just lied and returned
* the caller's buffer length on write instead of the actual
* number of characters put into the device circular buffer.
* That fix is consistent with just throwing the characters
* away, although I should probably have returned
* a -EOVERFLOW error or something like that.
2010.02.11
It currently succeeds on write echo hi > ./dev/mydev
followed by cat ./dev/mydev.
It fails in an infinite loop on echo 123456789abcde > ./dev/mydev
The device_write goes into an infinite loop
and the buffer conditions indicate the buffer has filled.
But it keeps trying to write. Why? Do I need to return something
to echo device write to indicate writing is done?
Also, it dumps tons of garbage to /var/log/syslog that
I just manually deleted. That means it is buffer overflowing.
2010.02.11
Generally got it performing some activities. I needed to
sort out the types ssize_t and size_t and I needed to
stop using 0 terminated string assumptions and move to
buffers with lengths. I needed to explicitly manage buffer
overflow checks.
2010.02.08
I'm just getting started with this, now that I've finished
my circular buffer prototype in experiment 2. Sigh, it took
forever.
2010.02.03
In this experiment, derived from experiment one, I want to provide
a device_write function that allows a user to put something into
the device that I'm creating. I'll allow the user to put stuff
into the device until the device is "full". I will be able
to read from the device but the read will return nothing if
the device is empty.
I'll just have a simple circular character buffer. Each
write will append a sequence of characters and each read
will return a sequence of characters, removing them from
the buffer. When buffer pointers are equal the device
is empty. When write pointer catches the read pointer
less one then the buffer is full.
I should be able to cat characters into the device up to
the size of the device (the buffer size) and I should be
able to cat from the device to empty it.
Note that this operates like a character FIFO, but is not
yet the Nutt lab 10 because the readers and writers do
not block. Also, I'm only doing one FIFO.
I also don't plan on writing test programs in C. I'll just
use cat on the command line to write and read from the
file. Note that I think the regular cat >mydev will act
like a cat >>mydev. On the other hand, cat mydev will
empty the entire device and I won't get to see a partial
read. Maybe I'll write a get.c function that lets me
read just n characters.