BluejayNotes.tioga
Copyright © 1986 by Xerox Corporation. All rights reserved.
Doug Terry, December 3, 1986 3:20:22 pm PST
A collection of notes on the implementation of Bluejay, the voice file server.
General Information
All files comprising Bluejay are in Bluejay.df.
Bluejay has two major components:
Jukebox handles to storage of voice files (or "tunes").
VoiceStream handles the transmission of voice between a Jukebox and the network.
Jukebox
See Jukebox.mesa for the basic operations on jukeboxes. The implementation modules are JukeboxImpl.mesa and JukeboxIntervalImpl.mesa. TuneAccess.mesa and TuneArchive.mesa provide additional operations on tunes. There are also several CommandTool commands available for dealing with jukeboxes and tunes.
In Jukebox.mesa the structure of a jukebox file is described as follows:
1) The first page contains the jukebox header, including chirp allocation and other miscellaneous information.
2) The second and following pages contain a bitmap indicating the availability of tune headers. (This is simply a hint; the truth lies in the tune headers themselves.)
3) After the tune header bit map come many pages of tune headers, two pages for each possible tune. The first page of each tune header is for Bluejay use only, and the second page is for client use only (Bluejay provides ops to read it and write it). Tune headers are allocated statically, and are similar in format to Unix i-nodes (three levels of block directory).
4) All pages after the tune header are used for storage of the tunes, and for indirect tune chirp lists, and for free list blocks. The pages of a tune are grouped into "chirps". Each chirp contains several pages, in order to reduce disk access time. Each chirp contains one second of conversation in 16 pages. Chirps are page aligned, with the 192 bytes per chirp following the speech samples used as a run list for interpreting the sequence of the samples.
VoiceStream
See VoiceStream.mesa for the basic operations on voice streams. The implementation modules are VoiceStreamBasicImpl.mesa, VoiceStreamServerImpl.mesa, and VoiceStreamSocketImpl.mesa.
There are three processes involved with a voice stream: Server, ReceiveProc, and SendProc. The Server process manages the transfer of information between a Jukebox and all currently active voice streams. The "client" side of each voice stream is managed by a ReceiveProc, which transfers voice from the network to a voice stream, and the SendProc, which transfers voice onto the network. The Voice Transmission Protocol is documented elsewhere.
Basics
Pieces... A "piece" indicates an area of the jukebox to be read or written. Pieces are queued and serviced in FIFO order for each voice stream. A flush operation throws away all of the pieces pending for the stream.
Buffering... Buffers are used to keep track of one chirp and the space it occupies in virtual memory; each buffer has an indication of whether it is destined to or from the jukebox. A voice stream has three queues of buffers: the server buffers are those that are waiting to be processed by the server, the client buffers are those waiting to be processed by the client (ReceiveProc and SendProc), and the idle buffers are those that aren't currently in use. The Open operation allocates a number of buffers and places them on the idle queue; Close frees all of the buffers.
Synchronization... A single monitor lock is used to control access to voice stream handles. Several condition variables are used to control the synchronization among the processes. The server waits on "serverCondition" whenever it is completely out of work; this condition is notified whenever a new stream is opened, a new piece is added to a stream, a buffer is handed to the server, or a stream is being closed (to prod the server to broadcast "closeCondition"). The server broadcasts the "client" condition when it adds a buffer to the client queue, an error occurs, (or it wants work?); this condition is also broadcast when a stream is closed or flushed; a client waits on this condition when it needs a buffer or when it is waiting for the server to write a buffer to disk(?). The "waitCondition" is broadcast whenever a stream becomes empty, flushed, or closed; the WaitEmpty operation waits on this condition. The "closeCondition" is broadcast whenever the server has no work to do (for any stream!); the Close operation waits on this condition.
Error handling... Each voice stream handle contains an errorRope; if this isn't NIL, then an error has occurred for the voice stream, as described by errorRope and errorCode. The server simply sets these fields of the stream handle when it discovers an error. The client processes check for errors and quietly go away if any are discovered. The AddPiece, Check, and Close operations report an error if necessary; errors are also reported whenever a client attempts to get/put data from/to a stream.
Event reporting... A NotifyProc is called when a voice stream begins ($started) or ends ($finished) the playback/recording of a piece, or when it is flushed ($flushed).
Server
The server is responsible for processing pieces by generating chirp-sized buffers to be read or written by the client processes. Thus, the server processes each piece a chirp at a time; the start and length of the piece's interval are adjusted along the way so that they always refer to the portion left to be processed. An important invariant maintained by the server: any buffers waiting to be processed. i.e. that are not on the idle queue, belong to a single piece; the server does not start buffering the next piece until the buffers for the previous piece are completely read or written.
The server operates in an infinite loop that takes the first buffer off the server queue and temporarily places it at the head of the idle queue (GetServerBuffer); if the server queue is empty then the buffer already at the head of the idle queue will be used. The server then jumps out of the monitor and safely processes the buffer while is sits on the idle queue.
The server first writes out the chirp in the buffer if it needs to be written. The server then tries to continue working on the current piece. If the current piece has been completely processed, then the server continues writing any buffers associated with it (by short-circuiting the rest of its loop); when the piece and all of its buffers have been processed, the server moves on to the next piece.
Next, the next chirp of the piece is read into the buffer if the piece is for playback or a partial chirp is being recorded (note that recorded intervals can start in the middle of a chirp but cannot end in the middle of a chirp!). If the piece's interval does not include the first part of the chirp just read, then the server uses the run data to determine where in the buffer the desired interval actually starts (recall that silence is not explicitly stored in a chirp so computing intervals is tricky). The server does not spend time analyzing the run data to find the end of an interval (so the buffer's block may be longer than needed but who cares).
When done, the server transfers the buffer from the idle queue to the client queue (GiveClientBuffer). The server then starts the loop again, i.e. it tries to get another buffer from the server queue.
ReceiveProc
In VoiceStreamSocketImpl.mesa: This process sets up a connection with an Etherphone, then receives incoming packets from the Etherphone. It reads packets continuously until either the voice stream is closed or the official socket for the stream changes. Note that the stream never times out. Data is added to the voice stream by calling VoiceStream.Put.
Put in VoiceStreamBasicImpl.mesa: This procedure adds the bytes from a block to the end of the voice stream.
The procedure is a loop that executes as long as there is silence or data that needs to be written in a buffer. It waits for a buffer on the client buffer queue (unless there is no piece being processed). If the stream is currently going the wrong way, i.e. is being used for playback rather than recording, then the procedure returns immediately. If the first client buffer is full or the piece is being flushed, then it gives the buffer back to the server (GiveServerBuffer) and goes back to get another buffer.
First, the given amount of silence is added to a buffer (or two) by updating the buffer's run data. Then, the actual block data is written into the buffer. However, if the block's energy level is too low and the number of packets since the last non-silent packet is too large, then instead of being written, the block is added to the buffer's run data as silence.
SendProc
In VoiceStreamSocketImpl.mesa: This procedure runs the second process for each connection between Bluejay and an Etherphone. It is responsible for sending voice to the Etherphone via the network. VoiceStream.Get is called to see if there is any data in the voice stream to be sent.
Get in VoiceStreamBasicImpl.mesa: This procedure adds the bytes from the end of the voice stream to a given block.
The procedure is a loop. It grabs the first buffer on the client queue; if there isn't one then it simply returns unless told to wait (the client should play silence and try again later). If the stream is currently going the wrong way, i.e. is being used for recording rather than playback, then the procedure returns immediately. If the piece is being flushed or the first client buffer has been completely used, then it gives the buffer back to the server (GiveServerBuffer) and goes back to get another buffer.
While processing the buffer, this procedure keeps track of how much silence is encountered; it returns if the accrued silence exceeds a caller-specified amount (maxSilentBytes). When data is encountered whose energy exceeds the ambient level, or the number of packets since the last non-silent packet is not too large, the data is copied into the provided block. The procedure returns when the block has been completely filled, silence is encountered after data has been transferred, or the client buffer queue runs out.
Scenarios
A Typical Playback
Suppose that a client wants to playback an interval of an existing tune, and that the voice stream is currently idle.
The client calls
VoiceStream.AddPiece[handle: myVoiceStream, intervalSpec: [tuneID: 29, start: 800, length: 16000, keyIndex: 1], direction: play];
Note that the encryption key for this tune must have been previously registered and an associated keyIndex assigned (see ThParty.RegisterKey). Note also that since a chirp contains 8000 voice samples the specified interval in this example overlaps three chirps.
AddPiece allocates a VoiceStream.PieceObject and adds it to the end of the piece queue (in this case it's the only thing on the queue since the voice stream was initially idle). It thens notifies the server.
The server wakes up, finds the server and client queues empty, and starts to work on the new piece. It calls the notify procedure to indicate that the piece has been $started.
The server discovers that the specified interval starts in the middle of the tune's first chirp and that the whole tail of this chirp is needed. The server reads the chirp from the Jukebox into the first buffer on the idle queue. It then uses the chirp's run data to find where the 800th sample starts in the chirp's storage block. This information is recorded in the buffer and the buffer is moved to the client queue. The piece.intervalSpec is updated to be [tuneID: 29, start: 8000, length: 8800, keyIndex: 1].
The server then loops around and discovers that the interval left to be processed starts on a chirp boundary and contains the complete chirp. It reads the chirp from the Jukebox into the first buffer on the idle queue and then moves the buffer to the client queue. The piece.intervalSpec is updated to be [tuneID: 29, start: 16000, length: 800, keyIndex: 1].
The server then loops around once again. This time it discovers that only the first part of a chirp is desired. Nevertheless, it reads the whole chirp from the Jukebox into the first buffer on the idle queue and gives the buffer to the client queue. The piece.intervalSpec is updated to be [tuneID: 29, start: 16800, length: 0, keyIndex: 1].
The next time around, the server notices that the piece has been completely buffered and waits.
Meanwhile, the SendProc's call to VoiceStream.Get succeeds in finding a buffer on the client queue. The non-silent data in the buffer is copied into packets and sent on the network. When the buffer is used up, it is passed back to the server by placing it on the server queue. This procedure is identical for all three buffers.
When the server finds buffers on the server queue, it simply moves them to the idle queue.
When all of the buffers have been replaced on the idle queue, that is the server and client queues are empty, the server concludes that the piece has been completely processed. It thens calls the notify procedure to indicate that the piece has been $finished and removes the piece from the piece queue.
A Typical Recording
Suppose that a client wants to record a new tune, and that the voice stream is currently idle.
The client calls
VoiceStream.AddPiece[handle: myVoiceStream, intervalSpec: [tuneID: 54, start: 0, length: VoiceStream.wholeTune], direction: record];
Note that the tune must exist and must be closed before calling AddPiece (however the size of the existing tune is unimportant). A new tune can be created by calling Jukebox.CreateTune.
AddPiece allocates a VoiceStream.PieceObject and adds it to the end of the piece queue (in this case it's the only thing on the queue since the voice stream was initially idle). It thens notifies the server.
The server wakes up, finds the server and client queues empty, and starts to work on the new piece. It calls the notify procedure to indicate that the piece has been $started.
The server discovers that the specified interval starts on a chirp boundary and uses the whole chirp. It simply passes an empty buffer, which indicates that it should be filled with a chirp's worth of data destined for the Jukebox, from the idle queue to the client queue. The piece.intervalSpec is updated to be [tuneID: 54, start: 8000, length: VoiceStream.wholeTune].
The server continues this until it runs out of idle buffers or a buffer is returned to the server queue.
Meanwhile, the ReceiveProc's call to VoiceStream.Put succeeds in finding a buffer on the client queue that is destined for the Jukebox. Data from packets received over the network is copied into the buffer. When the buffer is full, it is passed back to the server by placing it on the server queue. The ReceiveProc then attempts to fill another buffer.
When the server discovers a buffer on the server queue that is destined for the Jukebox, it writes the buffer's data block into the appropriate chirp in the Jukebox. It then moves the buffer to the idle queue. Since the piece has not been completely processed, this buffer is immediately set up to receive the next chirp and passed back to the client queue.
This procedure of passing buffers back and forth between the server and the receiving process continues indefinitely until the client calls
VoiceStream.FlushPieces[handle: myVoiceStream];
FlushPieces simply marks the piece as being flushed. It also calls the notify procedure to indicate that the piece has been $flushed.
When the server notices that the piece is being flushed, it sets piece.intervalSpec.length to zero so that the piece looks like it has been completed. When the ReceiveProc notices the flush, it immediately gives its buffers back to the server. The server then continues to write out buffers that contain data for the Jukebox (these are buffers that were filled before the call to FlushPieces).
When all of the buffers have been replaced on the idle queue, that is the server and client queues are empty, the server concludes that the piece has been completely processed. It thens calls the notify procedure to indicate that the piece has been $finished and removes the piece from the piece queue.
Unanswered questions
Why does Jukebox.FindClientSpace take a tuneID rather than a Tune? (All the other operations take Tunes.)
What exactly is the number of chirps that can be stored in a first-level tune, etc? That is, where do all of the constants in Jukebox.mesa come from and what do they mean?
Why does VoiceStreamServerImpl.GetPiece broadcast VoiceStream.client? Why broadcast this condition when a stream is closed or flushed? It seems that the client condition is used for two different purposes.
Why does VoiceStreamBasicImpl.Put wait for a client buffer? If there isn't one why doesn't Put return immediately?
What is the purpose of handle.action? It doesn't seem to be used for anything.