Finishing the network protocol

[Bill Spitzak]

I think the objection to partitioning the id numbers into a client 
number and object number is that it requires much larger id numbers. 
Wayland will likely run out of memory before it uses up 2^32 ids, but it 
is quite possible for there to either be more than 2^16 clients or more 
than 2^16 ids in one client, so the ids now have to be 64 bits.

It seems to me that the following scheme will work to avoid race 
conditions and to allow all the ids to be packed into a small space:

1. Id's are assigned to clients in "blocks" (similar to the current 
Wayland design). A message is sent to the client to indicate that it 
owns a given block. I think the blocks are small, like 256 or fewer ids. 
The size is a compile-time constant.

2. On initial contact, one of the global things sent from Wayland will 
be one block of ids. This avoids an extra round trip in order to get the 
first ids that a program needs. A server may send more than one if it wants.

3. When the program uses "enough" ids, the server will spontaneously 
send at least one more block. The exact rules can be determined by the 
implementation and may vary between servers. One possibility is that it 
will send another block when it allocates an ID more than 1/2 way 
through all the existing blocks.

4. A client can request N blocks (not N *more* blocks which is what 
Wayland does now). If the current allocation is less than N the server 
will respond with at least 1 more block (it can send more if it wants).

5. When a client creates an object, it sends the id it wants to use. 
This will produce an error if the id is not in a block belonging to the 
client, or if the id is already in use by another object.

6. When an object is destroyed, the very last thing it does is send an 
event saying it was destroyed to the owner of the id. Only after 
receiving this event is it safe for a client to reuse that id.

7. Clients can free entire blocks. This will destroy all the objects in 
that block without sending any messages. I'm not sure how useful this is 
but Wayland needs it anyway to handle clients crashing.

8. If a client crashes or otherwise the connection goes down, all the 
blocks allocated to that client are freed, destroying all the objects it 
created.

A client will typically record all the block-allocated messages it 
receives in a vector, and keep track of the first block and index into 
the block that it has not used as an id. It will also keep a free list 
of ids, destruction messages will add ids to this list. When it needs an 
id it will take the first thing from the free list. If that is empty it 
will take the next index from the current block. If it is full then it 
starts on the next block.

If there are no more blocks it will request N+1 blocks (where N is how 
many it has now) and wait for a new block to come from the server. This 
is synchronous but should only happen in rare occasions.