drivers/clock: Fix comment

Fixed error in ::clock's Doxygen comment. It referred to
osv::clock::monotonic, while in fact the correct name is osv::clock::uptime.

Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
stub setsid

Same as fork, vfork, etc. So goes in the same place.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
mempool: make mempool_cpuid() inline

In some runs callq to mempool_cpuid shows up in 'perf kvm top' profile.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
mempool: drop redundant assert

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
mempool: erase page range using an iterator rather than a reference

free_page_ranges is an intrusive set. erasing via a reference requires
iteration over reference equal_range under the hood, which means
traversing the tree to the leafs. Whereas erasing via an iterator
requires no such lookups so should be faster.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
lockfree: introduce unordered_queue_mpsc

It's like queue_mpsc with two improvements:

 * consumer and producer links are cache line aligned to avoid false
   sharing. I was tempted to apply this to queue_mpsc too but then
   discovered that this queue is embedded in a mutex, and doing so
   would greatly bloat mutex size, so I gave up on this idea.

 * The contract of pop() is relaxed to return items in no particular
   order so that we can avoid the cost of reversing the chain.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
lockfree: introduce unordered_queue_spsc

It is meant to provide both the speed of a ring buffer and
non-blocking properties of linked queues by combining the two. Unlike
for ring_spsc, push() is always guaranteed to succeed.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
tests: introduce latch.is_released()

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
tests: introduce latch.await_for()

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
tests: add test for free() throughput across CPUs

There is one allocating threads and two freeing threads. Each thread
is allocated on a different core. The test measures throughput of
objects freed by both threads.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
mempool: remove contention inside free_different_cpu()

Fixes #308.

When the per-cpu-pair ring fills up, the freeing thread is blocked and
enters a synchronous object hand-off. That synchronous hand-off is
cause of contention. Instead of having a bounded ring we can use an
unordered_queue_mpsc which links the freed objects in a chain. In this
implementation push() always succeeds and we don't need to block.

In a test which allocates 1K blocks on once CPU and having two threads
freeing them on two other CPUs, there is a ~40% improvement of free()
throughput.

I tested various implementaions, based on different queues. Statistics
of free/sec reported by misc-free-perf (one sample = one run):

current:

  avg =  8133055.09
  stdev = 118322.06
  samples = 5

ring_spsc<1M> (no blocking):

  avg = 10442665.98
  stdev = 476334.93
  samples = 5

unordered_queue_spsc:

  avg = 10258212.69
  stdev = 418194.22
  samples = 5

unordered_queue_mpsc:

  avg = 11701334.99
  stdev = 725299.97
  samples = 5

Testing showed that unordered_queue_mpsc() performs best in this case.

Dead objects are collected by per-CPU worker thread (same as
before). The thread is woken up once every 256 frees. That threshold
was chosen so that the behavior would more or less correspond to what
was before.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Merge branch 'mempool' of https://github.com/tgrabiec/osv

"The main improvement is in the last patch which removes contention
inside free_different_cpu() on sync._mtx. It improves my
micro-benchmark by ~30%."

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
tests: test more sizes for memcpy

Simple power of two is too easy.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
memcpy: aggressive unrolling

Copy < 256 bytes without any loops; 16 bytes and above use sse to reduce
instruction count.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
pthread: implement sem_destroy

Note that we don't allocate memory in sem_init: we are using placement new to
just construct the object over an already existing memory location. Therefore,
all we need to do is release our unique_ptr

Thanks Pawel for noticing we need to release memory of the internal semaphore

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
libc: implement lockf

This is mainly a wrapper around fcntl, so it should work to the extent
that fcntl works and fail gracefully where it doesn't. Code is imported
from musl with some modifications to allow it to compile as C++ code.

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

Similar to pipe, but taking flags. We will ignore exec related flags.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
libc: implement ffsl and ffsll functions

We already have the ffs function, ffsl and ffsll are easy from here.
Theoretically, a_ctz_l should do the job here as well since we're 64 all
over, but I found a_ctz_64 safer.

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

Code from musl.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
pthread: implement raise() function

The man page for raise says:

In a single-threaded program it is equivalent to

           kill(getpid(), sig);

In a multithreaded program it is equivalent to

           pthread_kill(pthread_self(), sig);

In our case we should mimic the second. It is a good question then whether this
function should be in a more generic place or in pthread.cc itself, but I will
argue for the second, since it will make it easier for people to notice that
this is what our implementation does.

Of course at this moment pthread_kill is stubbed and so is raise. But if we
ever implement the first, we gain the later for free.

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