include: add ilog2()

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
include: add count_trailing_zeros() functions

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: remove unused function debug_memory_pool()

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: introduce new page range allocator

The main goal of the new page range allocator is to improve computational
complexity. To achieve that N (currently N = 16) doubly linked lists are
used, list i contains areas which size is in range [2^i, 2^(i+1)). Huge
areas (i.e. too large for any list) are kept in a multiset sorted by their
sizes.

When a memroy block of size M is requested the allocator gets an area
from a not empty list that contains smallest objects greater or equal
2^ceil(log2(M)). If there is no such list an area is taken from a tree
of huge areas. If still allocator cannot find appropriate area the
temporary solution is to search list floor(log2(M)). That, obviously
ruins worst case computational complexity of the algorithm but can be
replaced by the fallback to non-contiguous once it is implemented.

When a memory block is freed allocator checks if it can be merged with
an neighbouring areas (at most 2) and then puts a resulting area in
an appropriate container. To quickly (O(1)) find whether there
neighbouring unallocated areas a bitmap is maintained where each bit
represents one page. If the bit is set the page is not allocated.
Moreover, each unallocated page range contains a valid header at the
beginning and at its very end (&pr + pr.size - sizeof(page_range**))
a pointer to its header.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: use new page range allocator

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Improve complexity of the large allocator

From: Paweł Dziepak <pdziepak@quarnos.org>

This patch series improves complexity of the large allocator to O(1) for large
objects that are small and O(log n) for large objects that are not small. There
is still one fallback that makes the worst case complexity O(n), but that can
be easily improved once falling back to non-contiguous allocations is
implemented.

The details of the allocator are described in the fourth patch of this series
(i.e. "mempool: introduce new page range allocator"), hopefully. this time not
stopped by the spam filter.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
build: don't regenerate makefiles constantly

The phoney prepare-dir target means we keep regenerating makefiles.  Avoid
it by folding it into the regular target.

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
build: ask before nuking old build/release/

Suggested by Nadav.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Revert "mempool: use new page range allocator"

This reverts commit 9202b754911e59f1c958d1be5d322edad4a4a9ee; causes assert
failures with iperf:

Backtrace:
    at /home/vladz/work/osv/external/x64/gcc.bin/usr/include/c++/4.8.2/bits/vector.tcc:519
    at /home/vladz/work/osv/external/x64/gcc.bin/usr/include/c++/4.8.2/bits/stl_vector.h:1024

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Revert "build: ask before nuking old build/release/"

This reverts commit 15aebf20b2c17b0e30d34ce0b001aa264ec7577e.

Causes problems with non-interactive builds.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
rcu_hashtable: fix bad erase()

erase() first shrinks the hash table if needed, then erases the element
given by the iterator.  However, as elements are copied during shrinking
(to satisfy rcu), we erase the element in the *old* table, rather than
the new (shrunk) one.  The effect is that the element is not removed.

Found using wrk vs. tomcat, with the net channel rcu hashtable patch
applied.

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Revert "Revert "net: use rcu_hashtable in net channel classifier""

This reverts commit 181d26253d5e, which itself reverted 181d26253d.

With the rcu hashtable fixed (16ab9520eb), we can use rcu_hashtable in the
net channel classifier again.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
bsd: avoid #define malloc() when possible

bsd uses a 3-argument variant of malloc() instead of the standard single-
argument malloc().  This causes problems when including standard headers
along with bsd headers.

Fix by using a function overload instead.  A #define is only used in C code.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
memory: allow using debug allocator in parallel with standard allocator

Minor changes, allowing dbg::malloc() to be used in parallel with ::malloc().
This allows use-after-free debugging when the misbehaving type is known or
suspected.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: fix page_range_allocator::_bitmap resize

When resizing a dynamic_bitset some memory may be freed. In such case it is
not safe to attempt to merge unallocated block since the bitmap is in
undefined state. Instead, the memory free is deferred to a moment when the
resize is done and bitmap is reinitialized with up to date values.

page_range_allocator::_bitmap uses now custom allocator to get rid of
numerous checks agains _nobitmap in allocation and deallocation code.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Revert "Revert "mempool: use new page range allocator""

This reverts commit 0ff46442658062554221fc22f7bf2225b2f9b4b0.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
memory: debug allocator helper

Add a helper template that defines the appropriate new/delete operators for
the debug allocator.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Merge branch dbg-alloc

Small debug allocator improvements.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
build: remove .SECONDARY

Somehow this confuses make, causing it to ignore the explicit dependency
between libstatic-thread-variable.so and tst-static-thread-variable.so,
breaking a parallel build.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Fix 'sign-compare' error in unordered_ring_mpsc.hh

Fixes the following error when compiling osv on my Archlinux machine
with gcc 4.9:

  In file included from tst-unordered-ring-mpsc.cc:12:0:
  unordered_ring_mpsc.hh:40:22: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare]
               if (_idx >= _ring.rings.size()) {
                      ^
  unordered_ring_mpsc.hh:48:33: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare]
               do {} while (++_idx < _ring.rings.size() && !_ring.rings[_idx].pop(_element));

Reviewed-by: Tomasz Grabiec <tgrabiec@gmail.com>
Signed-off-by: Zifei Tong <zifeitong@gmail.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>