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 $