[Xcb] xcb recursive write not protected in all cases?

[Uli Schlachter]

On 26.12.2013 22:56, Josh Triplett wrote:
> On Thu, Dec 26, 2013 at 01:25:50PM -0800, Keith Packard wrote:
>> Uli Schlachter <psychon at znc.in> writes:
>>> After having figured all of this out today, who wants to write this down? And
>>> where? Some Wiki page called "ThreadSafetyInternals"?
>>
>> Sounds like we've got a good start here...
> 
> I'd actually suggest putting it in the XCB source code, under the doc/
> directory.  Easier to keep it in sync with the code that way, and easier
> to find it when trying to figure out how the code works.  (Not least of
> which because, through naming some of the functions and variables and
> locks in question, it'll show up in the obvious greps.)

The attached file has been laying around for a while now. I don't feel like the
resulting text is easily understandable, but it helped me reason about some of
the logic.

I do think that there are more threading issues lurking in xcb. However, I
haven't had much time to look into this and write convincing arguments for the
needed patches. So this mail just exists so that the mailing list archive has a
backup of this file and perhaps it even helps someone...

Uli
-- 
"Why make things difficult, when it is possible to make them cryptic
and totally illogical, with just a little bit more effort?" -- A. P. J.
-------------- next part --------------
Thoughts about XCB's thread safety
==================================

Table of context
----------------

TODO


Introduction
------------

The X-protocol C Binding is supposed to be fully thread-safe. This means that
multiple threads can freely call into the library without needing to synchronize
with other threads, as long as no thread calls xcb_disconnect() and some rules
that also apply in single-threaded use are honored, like not calling
xcb_wait_for_reply() twice on the same cookie.

At the same time, threads should not unnecessarily block and wait for other
threads, if possible.

This document looks into how this is implemented and provides some reasons for
the implementation's correctness. A first observation is that much work is done
locally without taking any locks (e.g. xcb_send_request() calculates the
request's total length and gets the extension's major opcode before acquiring
the iolock).

Some of the required guarantees are:

- Access to shared data structures is protected via mutual exclusion
- There is always at most one thread attempting to write or read from the socket
- Requests are written atomically (without other writers interfering)


Access to shared data structures is protected via mutual exclusion
------------------------------------------------------------------

To protected shared data, obviously mutexes are used. Currently, there are some
global mutexes, per-connection mutexe and some data that is only ever read:


next_nonce():

In xcb_auth.c, function next_nonce(), a static variable is used to generate
nonces (number used once). This static variable is protected with a mutex. Since
this is the only function using these, this code is obviously correct. Also, it
is not possibly to (portably) shorten the critical sections that this mutex
protects, thus threads really are blocked as shortly as possible.


next_global_id():

Extensions are represented by an xcb_extension_t structure. These can be used
without being registered, as long as the global_id field is initialized to 0.
When an extension is first used, get_lazyreply() in xcb_ext.c will assign an
unique, process-local identifier to the extension. This id later gets used as an
index into an array. The code for this is similar to the code in next_nonce()
that was described above.


c->xid.lock:
Fields in xcb_connection_t protected:
- All entries in c->xid.

This lock is only used by xcb_generate_id() which is the only function that
touches fields in c->xid. Thus, this protects the generation of XIDs. The lock
is held across the full function body and thus no other thread can interfere.


c->ext.lock:
Fields in xcb_connection_t protected:
- All entries in c->ext.

This lock is used by xcb_get_extension_data() and xcb_prefetch_extension_data().
Both functions hold this lock for their full function body and these are the
only functions touching fields in c->ext.


c->out.reqlenlock:
Fields in xcb_connection_t protected:
- c->out.maximum_request_length
- c->out.maximum_request_length_tag

Traditionally, the maximum request length is a 16 bit field in the connection
setup information which the server sends directly after a successful connection.
However, 16 bit was later deemed to be too small and the BIG-REQUESTS extension
was introduced. Now, the client library has to query this extension and the
maximum request length separately.

For this, a simple state machine is implemented in
xcb_prefetch_maximum_request_length() and xcb_get_maximum_request_length().
Both of these functions use the reqlenlock to exclude other threads while they
are running. This code is as simple as the code protected by c->ext.lock from
above.


c->iolock:
Fields in xcb_connection_t protected:
- All entries in c->in
- All entries in c->out except for c->out.maximum_request_length{,_tag}

This is the most important and complicated lock in XCB. It is used in
xcb_conn.c, xcb_in.c and xcb_out.c. The only interesting function using this
lock in xcb_conn.c is _xcb_conn_wait() which waits for the underlying file
descriptor to become read- or writable. However, while waiting, this function
releases the lock! All other functions hold this lock around accesses to shared
data. This lock will be looked at in more detail in a later section.


'Unprotected' data:
Fields in xcb_connection_t:
- c->has_error
- c->setup
- c->fd

The last two fields are only written to while xcb_connect_to_fd() is executed
which means that the connection is being established. Since this function did
not return yet, no other thread has access to the xcb_connection_t and no races
can occur.

For c->has_error, atomic writes to integers are assumed. This field is
initialized to 0. If it ever gets set to some other value, the connection is in
an error state and all function calls fail immediately. This means that this
field can be read without holding any locks.


There is always at most one thread attempting to write or read from the socket
------------------------------------------------------------------------------

If more than one thread were to write to the socket at the same time, no order
between the writes could be guaranteed. If multiple threads were to read from
the socket at the same time, only one of them would actually read some data.
This data could e.g. be a reply that the other thread is waiting for, but this
thread is now stuck in the system call. Thus, there must never be multiple
threads reading or writing at the same call.

===============================================================================
TODO: What if the cond_wait() in the writing case in _xcb_conn_wait() really is
redundant?
===============================================================================

This is implemented in _xcb_conn_wait(). This function maintains c->out.writing
and c->in.reading which are the number of threads currently writing or reading.
When this function is called while another thread already does the requested
action, the function will wait on a condition variable instead. The other thread
will then wake us up when it is done. Thus, reading threads exclude other
reading threads and writing threads exclude other writing threads.

However, as explained in the "X Meets Z" paper in the 'See also' section, a
writing thread must also be prepared to read from the connection, because the
X11 server could stop reading new data until its writer buffer is drained. Thus,
writing and readings threads cannot exclude each other, as the following
scenario shows:

- Thread 1 calls xcb_wait_for_reply()
- The requested reply wasn't read yet
- Thus, thread 1 calls _xcb_conn_wait(), wanting to read new data
- The thread is blocked in poll() (and the iolock is released, so that other
  threads can continue)
- Thread 2 calls xcb_send_request()
- The write queue (c->out.queue) is full and needs to be flushed
- Thus, thread 2 calls _xcb_conn_wait(), wanting to write data

If thread 2 would now only poll() for the socket to become writable, there is a
race where no thread wants to read, because thread 1 could have returned from
poll() and is now waiting for the iolock to become available. As soon as thread
2 releases the iolock, thread 1 would read once and then we are in a situation
where a thread is trying to write to the socket without reading.

Thus, thread 2 must also poll() for readability. As soon as the socket becomes
readable, one of these threads is woken up for sure. If thread 1 awakes and
reads its data, everything is fine. However, if thread 2 wakes up, it must not
read any data that could possibly be interesting to thread 1. This makes sure
that thread 1 wakes up from poll() to read from the socket.

To implement this, a thread trying to write from the socket may only read from
the socket if no thread is waiting for readability. See the corresponding
comment in _xcb_conn_wait().


Requests are written atomically (without other writers interfering)
-------------------------------------------------------------------

There are two functions in XCB which require the caller to hold the iolock, but
possibly release this lock. This can introduce unexpected races since the
calling function's critical section gets split. These functions are
get_socket_back() in xcb_out.c and _xcb_conn_wait() from xcb_conn.c.

====================================================
TODO: Rewrite after Keith's patch changes things (?)
====================================================

All functions calling get_socket_back() do so right after acquiring the socket.
Thus, there is nothing before this function call that could cause problems. In
other words, if another thread acquires the iolock while get_socket_back()
released it, there is an equivalent situation where the other thread acquired
the lock before the current thread acquired the iolock in the first place.

===========================================
TODO: Not the case for _xcb_out_send_sync()
===========================================

For _xcb_conn_wait(), the situation is more complicated. The callers from
xcb_in.c and _xcb_out_send() will be looked at separately. The later function's
callers have to be looked at, too.

All callers from xcb_in.c use this to wait for new data to be read from the
socket (this means that this is logically equivalent to waiting on a condition
variable). These functions are public entry points and thus there is nothing in
the call chain which does not expect to be interrupted.

In xcb_out.c, _xcb_out_send() calls _xcb_conn_wait(). The possible call chains
for this function are the following:

  _xcb_out_send()
  -> _xcb_out_flush_to()
     -> wait_for_reply
        -> xcb_wait_for_reply()
        -> xcb_request_check()
     -> xcb_flush()
     -> xcb_request_check()
     -> xcb_send_fd()
     -> xcb_take_socket()
  -> send_request()
     -> send_sync()
        -> _xcb_out_send_sync()
           -> xcb_request_check()
        -> xcb_send_request()
     -> xcb_send_request()
  -> write_setup()
     -> xcb_connect_to_fd()
  -> xcb_writev()

Because these functions are all writing requests, c->out.writing will be
non-zero while _xcb_conn_wait() releases the iolock. This is important because
==================
TODO: Only most!!!
==================
callers wait for c->out.writing to become zero before doing anything critical.
This means that while one thread is writing to the connection, other threads
will be blocked. Only after the writing thread has finished and released the
iolock without increasing c->out.writing, these other threads can continue.

The call through write_setup() and xcb_connect_to_fd() can be ignored, because
this is setting up the connection. At this time, no other thread can access the
xcb_connection_t yet and thus no races are possible.

TODO: More explanations

TODO: _xcb_out_send(c, whatever, 0) possible? Is that bad?

TODO: xcb_writev() called from more than one thread at once?


See also
--------

- Bart Massey and Robert T. Bauer. 2002. X Meets Z: Verifying Correctness in the
  Presence of POSIX Threads. In Proceedings of the FREENIX Track: 2002 USENIX
  Annual Technical Conference, Chris G. Demetriou (Ed.). USENIX Association,
  Berkeley, CA, USA, 221-234.
  http://www.freedesktop.org/software/xcb/usenix-zxcb.pdf