QemuMutex does not guarantee fairness and cannot be acquired
recursively:

Fairness means each locker gets a turn and the scheduler cannot cause
starvation.

Recursive locking is useful for composition, it allows a sequence of
locking operations to be invoked atomically by acquiring the lock around
them.

This patch adds RFifoLock, a recursive lock that guarantees FIFO order.
Its first user is added in the next patch.

RFifoLock has one additional feature: it can be initialized with an
optional contention callback.  The callback is invoked whenever a thread
must wait for the lock.  For example, it can be used to poke the current
owner so that they release the lock soon.
Signed-off-by: NStefan Hajnoczi <stefanha@redhat.com>

Now that the monitor and readline are decoupled, readline.h no longer
belongs in include/monitor/.  Put the header into include/qemu/.

Move the source file into util/ so it can be linked as part of
libqemuutil.a.
Signed-off-by: NStefan Hajnoczi <stefanha@redhat.com>
Signed-off-by: NKevin Wolf <kwolf@redhat.com>

Abstract away dependence on a system implementation of getauxval.
Signed-off-by: NRichard Henderson <rth@twiddle.net>

Implement the continuous leaky bucket algorithm devised on IRC as a separate
module.
Signed-off-by: NBenoit Canet <benoit@irqsave.net>
Signed-off-by: NStefan Hajnoczi <stefanha@redhat.com>

In two places qemu uses openpty() which is very system-dependent,
and in both places the pty is switched to raw mode as well.
Make a wrapper function which does both steps, and move all the
system-dependent complexity into a separate file, together
with static/local implementations of openpty() and cfmakeraw()
from qemu-char.c.

It is in a separate file, not part of oslib-posix.c, because
openpty() often resides in -lutil which is not linked to
every program qemu builds.

This change removes #including of <pty.h>, <termios.h>
and other rather specific system headers out of qemu-common.h,
which isn't a place for such specific headers really.

This version has been verified to build correctly on Linux,
OpenBSD, FreeBSD and OpenIndiana.  On the latter it lets qemu
to be built with gtk gui which were not possible there due to
missing openpty() and cfmakeraw().
Signed-off-by: NMichael Tokarev <mjt@tls.msk.ru>
Tested-by: NAndreas Färber <andreas.faerber@web.de>

This adds the Castagnoli CRC32C algorithm, using the 0x11EDC6F41
polynomial.

This is extracted from the linux kernel cryptographic crc32.c module.

The algorithm is based on:

Castagnoli93: Guy Castagnoli and Stefan Braeuer and Martin Herrman
             "Optimization of Cyclic Redundancy-Check Codes with 24
              and 32 Parity Bits", IEEE Transactions on Communication,
              Volume 41, Number 6, June 1993
Signed-off-by: NJeff Cody <jcody@redhat.com>
Signed-off-by: NStefan Hajnoczi <stefanha@redhat.com>

Signed-off-by: NMarkus Armbruster <armbru@redhat.com>
Reviewed-by: NLaszlo Ersek <lersek@redhat.com>
Signed-off-by: NBlue Swirl <blauwirbel@gmail.com>

Factor out the hexdumper functionality from iov for all to use. Useful for
creating verbose debug printfery that dumps packet data.
Signed-off-by: NPeter Crosthwaite <peter.crosthwaite@xilinx.com>
Message-id: faaac219c55ea586d3f748befaf5a2788fd271b8.1361853677.git.peter.crosthwaite@xilinx.com
Signed-off-by: NPeter Maydell <peter.maydell@linaro.org>

fifo.c is generic code that can be easily unit tested.  So it
belongs in libqemuutil.
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

HBitmaps provides an array of bits.  The bits are stored as usual in an
array of unsigned longs, but HBitmap is also optimized to provide fast
iteration over set bits; going from one bit to the next is O(logB n)
worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
that the number of levels is in fact fixed.

In order to do this, it stacks multiple bitmaps with progressively coarser
granularity; in all levels except the last, bit N is set iff the N-th
unsigned long is nonzero in the immediately next level.  When iteration
completes on the last level it can examine the 2nd-last level to quickly
skip entire words, and even do so recursively to skip blocks of 64 words or
powers thereof (32 on 32-bit machines).

Given an index in the bitmap, it can be split in group of bits like
this (for the 64-bit case):

     bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
     bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
     bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word

So it is easy to move up simply by shifting the index right by
log2(BITS_PER_LONG) bits.  To move down, you shift the index left
similarly, and add the word index within the group.  Iteration uses
ffs (find first set bit) to find the next word to examine; this
operation can be done in constant time in most current architectures.

Setting or clearing a range of m bits on all levels, the work to perform
is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.

When iterating on a bitmap, each bit (on any level) is only visited
once.  Hence, The total cost of visiting a bitmap with m bits in it is
the number of bits that are set in all bitmaps.  Unless the bitmap is
extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
cost of advancing from one bit to the next is usually constant.
Reviewed-by: NLaszlo Ersek <lersek@redhat.com>
Reviewed-by: NEric Blake <eblake@redhat.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>
Signed-off-by: NKevin Wolf <kwolf@redhat.com>

Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>