tree def9e166df1ec091a7e1d7361a09decc596b5e50
parent 11cb5e533794bf0b6ba25c49abc527d48ddfb183
author Phillip Lougher <phillip@squashfs.org.uk> 1368237138 +0100
committer Mohamad Ayyash <mkayyash@google.com> 1424723755 -0800

caches-queues-lists: add a specialised "sequential queue" implementation

Add a specialised "sequential queue" implementation.  This rather
than outputing the data in the order pushed to the queue, outputs
it in the order specified in the "sequence" field in the pushed
entries.  Also only output data if the queue holds the next
sequential number to the previous output buffer.

This ensures that buffers pushed to the queue out of sequence
are delivered in the correct sequential order.

This queue is necessary because the queue collects data from
the deflate threads, and also (in the future and originally a couple
of releases ago) directly from the reader thread.   Depending on the
necessary time to compress the buffers, the deflate threads can
deliver buffers out of sequence, for instance deflate_thread_1 takes
buffer_1, and deflate_thread_2 takes buffer_2, if buffer_2 takes
less time to compress, this will be delivered before buffer_1 by the
deflate threads.  Previously(*) (and in the future) uncompressed fragment
buffers were sent directly to the main thread, rather than going via
the deflate threads.  Due to this a fragment block (representing block n)
could arrive before buffers n-1, n-2 etc because they have gone via the
deflate threads and taken time to compress.

(*) this was changed to queue the fragment buffers via the
deflate threads.  This was done for two reasons:

1. it was noticed queueing fragment blocks directly to the main thread
   resulted in a significant number of out of order blocks, and a lot
   of unnecessary wake-ups of the main thread.  Queuing via the
   deflate threads eliminated that source of out of order blocks, but with
   the consequence that the deflate_threads got more wake ups.  But
   queueing via the deflate threads at least enabled the next reason to
   take place.

2. Queueing via the deflate threads enabled the deflate threads to do
   sparse checking (all zero) on the fragment blocks, and to "promote"
   them to sparse blocks if they were all zero.

But for a long time a better solution was required, and this is it ...

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>