LBX design notes
----------------
Much of LBX is implemented as an extension. Some modifications have
been made to the Xserver OS layer to support its requirements, but
the only other impact LBX has on the core server are some hooks for
supporting tags.
Flow control
LBX multiplexes the data streams of all its clients into one, and then
splits them apart again when they are received. The X_LbxSwitch message
is used to tell each end which client is using the wire at the time.
Swapping
Swapping is handled as with any X extension, with one caveat.
Since a proxy can be supporting clients with different byte orders,
and they all share the same wire, all length fields are converted
to be sent in the proxy byte order. This prevents any problems with
length computation that may occur when clients are switched.
Tags
Tags are used to support large data items that are expected to be
queried multiple times. Such things as the keyboard map and font
metrics are often requested by multiple clients. Rather than send the
data each time, the first time the data is sent it includes a tag.
The proxy saves this data, so that subsequent requests can send
only the tag. The proxy then pulls up its local copy of the data
and sends it on to its clients.
To support this, the Xserver keeps track of what tags are known to
the proxy. The proxy can send InvalidateTag messages if it doesn't
store the tagged data. The server also sends InvalidateTag messages
when the data changes, to allow the proxy to clean out obsolete data.
If the server & proxy get out of sync, and the proxy receives a
tag which is cannot resolve, it can send a QueryTag message and the
server will respond with the requested data.
Property data makes special use of tags. A common use of properties
is for inter-client communication. If both clients use the proxy,
its wasteful to send the data to the server and then back, when
the server may never need it. X_LbxChangeProperty does the
same work as X_ChangeProperty, but it does not send the data.
X_LbxChangeProperty replies with a tag which points to the data.
If the property information is used locally, the server responds to
X_LbxGetProperty with a tag, and the property data need never be
sent to the server. If the server does require the data, it can
issue a QueryTag message. The proxy can also send the data on at
any time if it thinks its appropriate (ie, wire goes idle).
The heuristics of property handling can be complex. Because
X_LbxChangeProperty is a round-trip, it can take longer to use it
than X_ChangeProperty for some wires, especially if the amount of
property data is small. Using X_LbxChangeProperty can also be
a mistake for ICCCM properties, if the window manager is not a
proxy client.
Tag caching
The proxy contains a tag caching system that allows it to store a
controlled amount of tag data. Limited proxy hosts may wish to use
small caches or none at all. When the cache becomes full, it will
throw out the oldest data (and send the appropriate InvalidateTag
message to the Xserver).
Currently two tag caches are used, one for properties and another
for other data types. This may want to be modified to separate
out font metrics.
All tagged data is stored in the proxy byte order.
Short-circuiting
Short-circuiting is used to handle 'constant' data. This includes
atoms, colorname/RGB mappings, and AllocColor calls. Atoms and
colorname/RGB mappings stay constant for the life of the server.
AllocColor replies are constant for each colormap. Short-circuiting
replaces round-trip requests with one-way requests, and can sometimes
use one in place of many.
Atoms are used heavily for ICCCM communication. Once the proxy knows
the string<->atom mapping, it has no need to send the request on to
the server.
Colorname/RGB mappings are constant, so once the proxy sees the
response from X_LookupColor, it need not forward any subsequent
requests.
Clients often use the same color cells, so once a read-only color
allocation has occurred, the proxy knows what RGB values should
be returned to the client. The proxy doesn't need to forward any
AllocColor requests it can resolve, but it must tell the server to
modify the color cell's reference count. X_LbxIncrementPixel is
used to support this.
For all three classes of short-circuiting, the server must still
tell the server a request has occured, so that the request sequence
numbers stay in sync. This is done with X_LbxModifySequence.
Sequence numbers cause the major complication with short-circuiting.
X guarantees that any replies, events or errors generated by a
previous request will be sent before those of a later request.
This means that any requests that can be handled by the proxy must
have their reply sent after any previous events or errors.
There are 3 possible ways to support short-circuiting:
- fully correct protocol, which ensures that nothing can be out
of order
- mostly correct protocol, where only errors can be out of order
- poor protocol, where events & errors can be out of order.
A smart client or test suite could send a request it knows will
generate an event or error, followed by an InternAtom request,
and get the InternAtom reply before it gets the event.
Xlib hides this problem from most applications, so the 'poor'
protocol can be sufficient. For a fully safe environment, the proxy
can be compiled to use any of the three forms (or no short-circuiting
at all). In no case do we allow replies to come back out of order.
The proxy knows what can come back from all the core requests --
for any extensions it assumes the worst case and expects a reply.
Reply matching
LBX needs to store information about certain requests to support both
tags and short-circuiting. To do this, it creates a Reply record for
each request that can return a reply. Most of these are only used
as place holders, but for special requests data is stashed in them
(eg, InternAtom needs to save the atom name, so it can store it with
the returned Atom.)
Using the core protocol and Xlib, there is usually only one
pending Reply record per client. One common exception is caused by
XGetWIndowAttributes(), which sends two roundtrip requests and then
collects the results from both.
Test suites and interfaces other than Xlib may not follow this
convention, and could result in a number of pending Reply records.
The worst case are extensions. If the proxy doesn't know about
them, it must assume the worst case, and create a Reply record for
each extension request. These cannot be cleaned out until data
comes back from the server (event, error or reply), which allows
the proxy to flush any Reply records with older sequence numbers.
This has the potential to eat a huge amount of proxy memory, if an
extension issues a huge number of one-way requests.
Motion events
To prevent clogging the wire with MotionNotify events, the server and
proxy work together to minimize the number of events on the wire.
This is done with X_LbxAllowMotion. The proxy determines how many
events 'fill' the wire (currently hardcoded -- should be computed) and
'allows' that many events. When the server generates a MotionEvent
for a proxy client, it decrements the allowed number, throwing away
any after the wire is full. When the proxy receives a MotionNotify,
it sends an X_LbxAllowMotion to the server.
Delta cache
LBX takes advantage of the fact that an X message may be very similar
to one that has been previously sent. For example, a KeyPress event
may differ from a previous KeyPress event in just a few bytes. By
sending just the bytes that differ (or "deltas"), the number of bytes
sent over the wire can be substantially reduced. Delta compaction is
used on requests being sent by the proxy as well as on replies and
events being sent by the server.
Both the server and the proxy keep a cache of the N (currently
defaulted to 16) X messages sent and received. Only messages
smaller than a fixed maximum (currently defaulted to 64) are
saved in the delta cache.
Whenever the server has a message to send, and the message is of
appropriate length, the message is compared to any same-length messages
in its send cache. The message with the fewest number of differing
bytes is selected. If the number of differences is small enough and
the resulting X_LbxDelta message would not be longer than the original
message, the X_LbxDelta message is sent in place of the original.
The original message must also be place in the send cache. The proxy
uses the same algorithm when it has a message to send to the server.
Compression
Before being passed down to the transport layer, all messages are
passed through a general purpose data compressor (currently only LZW is
supported). The LZW compressor is presented with a simple byte stream -
the X and LBX message boundaries are not apparent. The data is
broken up into fixed sized blocks. Each block is compressed, then a two
byte header is prepended, and then the entire packet is transmitted.
(NOTE: LBX is designed to allow other compression algorithms to be used
instead of LZW. However, there is no requirement that the packet format
used for LZW be used for implementations involving other compression
algorithms.) The LZW compressor also provides for the ability to transmit
data uncompressed. This is useful when the data has already been
compressed by some other means (eg. a bitmap may be compressed using a
FAX G4 encoding) and further compression would not be effective.
The LZW compressor attempts to buffer up enough raw data to fill out a
complete block before actually compressing the data. This improves
compression efficiency. However, the LZW buffers are always flushed
before the server/proxy goes to sleep to await more data.
Master Client
When the initial X connection between the proxy and the server is
converted to LBX mode, the proxy itself becomes the "master" client.
New client requests and some tags related messages are sent in the
context of the master client.
Server Grabs
The master client must be grab-proof because the server may need to
retrieve tagged data from the proxy at any time. Since the master client
is multiplexed onto the same connection as other clients, the other
clients effectively become grab-proof as well. While the server is
grabbed, messages for non-master clients can be buffered. However, it's
possible for some client to eat up a large amount of buffer space before
the server is ungrabbed. In order to counteract this, when the server
is grabbed, an X_LbxListenToOne message will be sent to the proxy. If
the client grabbing the server belongs to the proxy, then only master
client and grabbing client messages will be transmitted to the server.
If the grabbing client does not belong to the proxy, then only master
client messages will be transmitted. The server will transmit an
X_LbxListenToAll to the proxy when the server is ungrabbed.
Graphics Re-encoding
The LBX proxy attempts to reencode X_PolyPoint, X_PolyLine, X_PolySegment,
X_PolyRectangle, X_PolyArc, X_FillPoly, X_PolyFillRectangle, and
X_PolyFillArc requests. If the request can be reencoded, it is
replaced by an equivalent LBX form of the request. The requests
are reencoded by attempting to reduce all 2-byte coordinate, length,
width and angle fields to 1 byte. Where applicable, the coordinate mode
is also converted to "previous" to improve the compressibility of the
resulting data.
Data Flow
The LBX data stream goes through a number of layers, all of which
should be negotiable:
0. client requests
1. read by LBX proxy
2. potential byte-swapping
3. requests-specific processing and reencoding
4. potential byte swapping
5. delta replacement
6. stream (LZW) compression
transport
5. stream decompression
4. delta substitution
3. potential byte swapping
2. re-encoding
1. request processing
The reverse process occurs with X server replies/events/errors.
--------
$NCDXorg: @(#)design,v 1.4 1994/04/11 18:17:03 lemke Exp $
$Xorg: design,v 1.3 2000/08/17 19:53:53 cpqbld Exp $