bsd: Change again recently-changed rwlock API

This patch removes the readers() method of rwlock, as we don't have any
use for the actual number of readers - just for the question of whether
there are any. So we replace unsigned readers() by bool has_readers().
I don't want us to unnecessarily have a readers-count method that we
don't need, because some scalable rwlock implementations don't actually
keep a coherent count of readers across all CPUs, just knowledge of
whether there are any (see for example, C-SNZI).

The patch also renames rw_rowned() to rw_has_readers(), calling the
above has_readers(). We add a comment explaining that this function
is very different from rw_owned(), in that rw_owned() checks if *this*
thread owns the write lock, while rw_has_readers() checks if *any*
thread has the read lock.

Reviewed-by: Gleb Natapov <gleb@cloudius-systems.com>
Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
path lookup: allow null pointer for name argument

The name argument only contains a pointer to the place in the string where the
basename is. In many sitations, we are not interested in such information.
Declaring a variable just for that is just clutter. Allow it to take a null
parameter.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
fs: implement lutimes

Most of the code is common to utimes. This patch then factors out utimes (now
do_utimes) and sys_utimes to accept a flags paramater, and then implements both
utimes and lutimes based on it.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
tests: return a failure code if tst-utimes fails

tst-utimes.so is currently always returning 0, and relying on strings only to
mark success/failure. It's better to reflect that in the return code.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
tst: increment tst-utimes with lutimes functionality

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
libc: implement glibc's glob_pattern_p

Currently, glob is implemented but glob_pattern_p is not. This function
can trivially be implemented with existing glob machinery, since all it
does is to tell whether or not the string contains special symbols. This
is basically the same logic as is_literal, but with inverted return value.

The value of the "quote" parameter should also be inverted, since the man
page states that when the quote parameter is *non*-zero, then backslashes
are ignored. is_literal ignores them when useesc is *zero*.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
time functions: implement utime

utime is almost the same as time, but has second resolution, a different
signature, and uses current time automatically when the time argument is NULL

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
httpserver: Support POST requests with application/x-www-form-urlencoded

Add handling of POST requests with application/x-www-form-urlencoded
content type (which is actually the "normal" way to send parameters for
POSTs). Also propagate content data (if any) to request handler (needed
to handle json structured requests - i.e. prereq for jolokia).
 
Somewhat naive implementation that assumes non-multipart content will be
smallish, so its propagated in-memory. No stream management, through
this would be more proper.

Signed-off-by: Calle Wilund <calle@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Re-add ".SECONDARY" to build.mk

Over a year ago, commit e6e2f4f51be571b27c37d6d4f7c87af71e9aee6c removed
the ".SECONDARY:" statement from build.mk. Unfortunately it turns out that
this removal caused issue #161.

Issue #161 describes the weird phenomenon where the first "make" after a
"make clean" removes all test/*.o, leaving behind only *.so (which in
itself, is fine), but then the second "make" compiles the same tests
again, this time leaving behind the .o. A third "make" will finally not
recompile the tests.

Turns out that this is a known bug^H^H^Hfeature of how "chained rules"
work in make (see https://www.gnu.org/software/make/manual/html_node/
Chained-Rules.html#Chained-Rules). To create a test.so, we follow two
implict rules: One for .c->.o, and a second for .o->.so. In this "chain"
of rules, the ".o" file is considered an "intermediate" file - it is
deleted as superflous when make completes (this is the deletion we're
seeing in the first make), and next time "make" is run, make considers
whether the .so is newer than the .c - without building the .o at all.

BUT, another thing that happens during the first build is that the
dependency files *.d are generated, and they are used in the second
make. These suddenly explicitly mention the test.o as targets in rules
(e.g., test.o: something.h), and at that point, make suddenly thinks
that test.o is not an "intermediate" file but a normal file we care
about - so it needs it to exist (hence the recompilation on the second
make), and doesn't delete it at the end (hence finally everything is
quite on the third make).

Adding an empty target ".SECONDARY:" tells make that intermediate files
should not be deleted when we're done, which makes behave on the second
run like it would on the second, solves the weird recompilation issue.

I don't understand why .SECONDARY was dropped in the first place in
commit e6e2f4f51be571b27c37d6d4f7c87af71e9aee6c. If we do need to always
remove or remake a specific file on every run, we can definitely do
this (with rm or .PHONY) and don't need to drop the .SECONDARY.

Fixes #161.

Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
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>