Finishing the network protocol

[Andreas Hartmetz]

(Oops, I think I sent the last message to Marty instead of the list, thanks 
for quoting it, Marty)

On Wednesday 23 February 2011 14:52:24 you wrote:
> On 02/23/2011 07:26 AM, Andreas Hartmetz wrote:
> > On Wednesday 23 February 2011 00:31:56 Marty Jack wrote:
> >> On 02/22/2011 01:16 PM, Andreas Hartmetz wrote:
> >>> Hello,
> >>> 
> >>> I've started a Wayland implementation currently called "area", written
> >>> in C++ and with the main goal to work on all hardware that currently
> >>> works on Linux in some way (Framebuffer or X11).
> >>> I've started with the network code and noticed a few things that still
> >>> look like prototype code in Wayland, probably unchanged from early
> >>> versions.
> >>> Well, Wayland is becoming a serious project, so I think we should start
> >>> finishing and fixing the protocol. Additionally I don't know if I will
> >>> finish my own project so I'm looking to contribute my findings to the
> >>> main project.
> >>> 
> >>> First some hopefully correct primer of the Wayland protocol for
> >>> interested onlookers.
> >>> - The Wayland protocol is a remote procedure call protocol of sorts.
> >>> All
> >>> 
> >>>   messages are exchanged between objects; the protocol is asynchronous
> >>>   and no methods have return values as such.
> >>>   Methods can "return values" by triggering a message back.
> >>>   Everything is asynchronous, but order of messages is preserved.
> >>> 
> >>> - Each protocol-level object exists on both client and server
> >>> - It's easiest to think of all objects being created by the server on
> >>> 
> >>>   behalf of the clients.
> >>> 
> >>> - Object constructors don't return anything, they have an object ID
> >>> 
> >>>   argument that is pre-chosen and can later be used to refer to the
> >>>   created object. If creation succeeded there is no message back.
> >>> 
> >>> - The conversation between client and server is bootstrapped by
> >>> creating
> >>> 
> >>>   the "display" object on each client, which then starts talking to the
> >>>   global display object on the server.
> >>> 
> >>> I see the following issues:
> >>> - There is no way to subscribe to events, or rather there is no way not
> >>> 
> >>>   to subscribe to all events.
> >>> 
> >>> - Range-based ID issuance for object IDs (obviously can't use pointers
> >>> 
> >>>   between processes) is not bulletproof. It is possible for ranges to
> >>>   become fragmented insofar that they can't be reclaimed because
> >>>   there's one ID in every range. There is also currently no code that
> >>>   tries to reclaim ranges.
> >>>   The practical implication is that a Wayland server can, by design,
> >>>   not run indefinitely without exhausting ID (range)s.
> >>>   Another kind-of-problem is that a client can interfere with another
> >>>   client's operation by, intentionally or not, using IDs belonging to
> >>>   the other client.
> >>> 
> >>> I've looked at the TODO and come up with a few ideas of my own for the
> >>> following suggestions to modify the protocol:
> >>> 
> >>> - Have one ID<->object map per client, except for global objects where
> >>> 
> >>>   there is a global map in the server.
> >>>   This is suggested in the TODO file; I've done it this way right away.
> >>>   Obviously each client will have its own map in the client process
> >>>   anyway.
> >>> 
> >>> - Have three ID ranges:
> >>>    a) for global objects
> >>>    b) for client-specific objects created by the server (do they
> >>>    exist?) c) for client-specific objects created by the client
> >>>   
> >>>   where "created by" really means "creation initiated (assigning an
> >>>   object ID) by".
> >>> 
> >>> - Handle subscription without an extra mechanism by creating or not
> >>> 
> >>>   creating the object that will receive the desired events. Might need
> >>>   some splitting of existing objects.
> >>>   This would IMHO be an elegant and minimal way to handle the matter.
> >>> 
> >>> - A scheme to recycle object IDs. When a new ID is needed, pick a free
> >>> 
> >>>   one at random. This introduces a problem:
> >>>   Suppose the client destroys object A with ID n, then by chance
> >>>   immediately reuses ID n for object B.
> >>>   The server will only receive this information later, the Wayland
> >>>   protocol being asynchronous and the server not having to respond to
> >>>   an object creation request, unless it goes wrong. In the meantime
> >>>   the server could send an event intended for A which would end up at
> >>>   B, causing Bad Things to happen - in my implementation most likely
> >>>   an assert failure unless the objects are of the same class.
> >>>   (This is the trickiest failure mode I could think of)
> >>>   The suggested solution is a kind of "rendezvous" for objects where
> >>>   this can happen, or for simplicity all objects:
> >>>   On both client and server, have a function that needs to be called
> >>>   twice to unregister an object ID.
> >>>   One call from the destructor of the local object when it destroys
> >>>   itself, one call from the remote counterpart object when it destroys
> >>>   itself. No matter in which order the method is called, the first call
> >>>   removes the ID<->object mapping and puts the object ID on a waiting
> >>>   list to avoid reuse. The second call removes the ID from the waiting
> >>>   list, making it free to reuse.
> >>> 
> >>> - Specify how parent-child relationships work, e.g. (bad example, the
> >>> 
> >>>   answer is probably no here) is a surface automatically destroyed when
> >>>   its screen goes away? By whom?
> >>> 
> >>> - Specify who gets do delete objects and how that looks in the protocol
> >>> 
> >>>   - this is probably more a matter of documentation; I didn't read all
> >>>   of Wayland's code carefully and implementers ideally shouldn't have
> >>>   to.
> >>> 
> >>> - Add information in the protocol description XML file about things
> >>> like
> >>> 
> >>>   an object being global or not, and basically everything mentioned
> >>>   above that can benefit from help from the code generator.
> >>> 
> >>> I'm not publishing a repository URL right now because I haven't chosen
> >>> a license yet and because I've copied over the wayland.xml protocol
> >>> description file that bears no license header. Kristian, what about
> >>> the license of that file?
> >>> If there is interest I can polish my code a bit and publish an URL.
> >>> 
> >>> Cheers,
> >>> Andreas
> >>> _______________________________________________
> >>> wayland-devel mailing list
> >>> wayland-devel at lists.freedesktop.org
> >>> http://lists.freedesktop.org/mailman/listinfo/wayland-devel
> >> 
> >> I haven't analyzed this in any detail but maybe there is a simple
> >> unique-ID encoding along the lines of partitioning the encoding space
> >> into "created by client", "created by server" and then a wraparound
> >> counter sufficiently big, say 28 bits of counter and 4 bits of who
> >> allocated the value, that a collision would require the connection to
> >> be up for an insanely long time and the risk of collision is low (but
> >> would need to be checked for).
> >> 
> >> Usually the only time you want a random value is when there is some
> >> security risk involved in being able to predict one.
> > 
> > Using sequential IDs is fine for most aspects, but it doesn't prevent
> > collisions. Without some list of "dangerous" IDs it can always happen
> > that you get one that was just freed, however. Saying that wraparound is
> > not allowed makes the protocol "mostly reliable", which should be
> > avoided IMHO. Even if it never causes problems it's always something you
> > have to think of when debugging;  you can't completetely forget about
> > lower-level details. Picking an ID that is not in use on both sides with
> > complete (not 99.9999995%) reliability unfortunately takes a little more
> > work.
> > Maybe somebody has a great idea how to do it with less effort?
> > Sequential 64-bit integers maybe? Adds quite a few nines to the
> > likeliness that no collision occurs, taking a little more space and
> > time... _______________________________________________
> > wayland-devel mailing list
> > wayland-devel at lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/wayland-devel
> 
> No, I disagree about the possibility of getting one that was just freed,
> assuming you buy into the namespace partitioning.
> 
> If you have a variable in the client that holds the last one allocated, and
> you increment it, you are guaranteed not to get the same value for
> client-allocated IDs until the counter wraps around.  If you partition the
> ID space, you are guaranteed not to get the same value as any other ID
> allocator can allocate.  Assuming you have a data structure that maps the
> ID back to your structure corresponding to the ID, which I think you would
> need anyway, and you are about to put your pointer into that structure, it
> is easy to check if the ID is used and retry the allocation.
> 
The whole point of IDs is to have data structures that maps IDs to objects 
(one each on both sides of a client connection and a single one for the global 
objects on the server), sure. You seem to forget here that the client and the 
server can get out of sync, which is why I purposefully picked such an example 
in my first e-mail.

> I would be tempted to use a multilevel page table for the aforementioned
> data structure the same way page frame data bases work.  That way you
> don't have a lot of wasted pointer space; you can clean up the second (and
> third, if you wanted) level page table when it becomes free after those
> objects are deleted and it won't be needed again until the ID wraps.
> 
There are many ways to pick an ID if you don't have to worry about the other 
side of the connection, it doesn't even need to be specified in the protocol 
how exactly to do that.

> Also, if you put the "who allocated this" in the lowest order bits, and
> increment just the upper bits, this is a very easy way to do it, most
> computers these days have add instructions that will handle the overflow
> for you.
> 
> 	static uint32_t id;	/* WhoAmI in 0:3; sequential counter in 4:31 */
> 	Initialize:  id = WhoAmI;
> 	Allocate:  id += 1 << 4;
> 
> (This idea comes long ago from a professor at CMU who wanted to put a
> protection ring ID in those low order bits)

This works just as well as determining who allocated an ID using ranges, with 
the difference that it's harder for a human to see who allocated it without 
doing bit arithmetic. One could debug-print IDs in hex, granted, but decimal 
is still easiest to handle for humans.
Both ways are good enough and I don't care that much.