core: introduce bitset iteration utilities

The main utility allows to iterate over indexes of set bits like this:

  for (int index : for_each_set(my_bitset)) {
      ...
  }
core: introduce timer_set data structure

The data structure optimizes for timer non-delivery by deferring
sorting cost until expiry time. The optimization is based on the
observation that in many workloads timers are canceled or rescheduled
before they expire. That's especially the case for TCP timers.

The implementation is based on hierarchical timer-wheel scheme, which
was described in "Hashed and Hierarchical Timing Wheels: Efﬁcient Data
Structures for Implementing a Timer Facility" by George Varghese and
Anthony Lauck. A description of timer wheel implementation in the
Linux kernel can be found here: http://lwn.net/Articles/156329/.

Our implementation is tick-less and has precision limited only by the
precision of the underlying clock.

The idea behind the implementation from this patch was originally
proposed by Avi. Each timers is assigned a list based on the length of
the common bit-prefix between timer's expiry time point (aka timeout)
and the last expiry time point (_last). The timer whose timeout is >=
_last and has no more than N leading bits the same as _last lands in
bucket N. When we expire at time point "_now" we calculate the prefix
index between _now and _last which we will call "e_index". We don't
need to consider buckets in indexes lower than e_index, they don't
fire yet and their index won't change when base is switched to
_now. Timers in buckets with indexes higher than e_index are all known
to have just expired. Finally, we need to walk through all timers
inside bucket e_index and check if they have expired or not. If timer
from bucket e_index is not expired we need to re-hash it using the new
base time point.

 == Computational complexity ==

The cost of insert() and remove() is always O(1). Expiring a timer
involves checking all timers placed in the same bucket so the cost of
single expire() varies. Let's see how an amortized cost of expiring N
timers looks like. Imagine a set of timeouts spread evenly over a
period between T0 and Tn:

 0000 = _last

 0001 = T0
 0010
 0011
 0100
 0101
 0110
 0111
 1000
 1001
 1010
 1011
 1100
 1101
 1110
 1111 = Tn

Timers need to be expired one-by-one starting from the soonest. Let's
notice that when timers expire, other timers from their bucket are
promoted to higher buckets based on the common prefix with the
expiring timer's timeout. Each such promotion extends the common
prefix until the next '1' in timeout's binary representation, so the
number of promotions a timer will have is equal to the number of ones
in its binary representation. The total number of promotions will
therefore be O(N*log(Tn)), so the amortized cost of expiry per timer
is O(log(Tn)).
tests: add test for timer_set
core: switch async timers to use timer_set
core: switch sched::timer_list to use timer_set
core: avoid unnecessary clock reschedules

sched::timer_list is tracking last time point the clock was set in the
_last field. It seems to be an optimization which would prevent clock
sets when timers are repeatedly cancelled and set. This field is
updated by rearm() method. timer_list::resume() was not using that
method, which could leave _last with a stale value.

Spotted during code inspection.
core: use unordered_queue_mpsc for released_timer_tasks

The unordered_queue_mpsc burns a bit less cycles than queue_mpsc and
will suffice in this case.
tests: Add test to check access to static __thread variable

This is a regression test to check that access to
static __thread variable does not generates page fault.

Signed-off-by: Zika L'Etrange <zika.letrange@gmail.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
sem: implement sem_timedwait

Exactly the same as sem_wait but with a timer. Luckily, our semaphore
API already have an option to do that. Just use it.

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
mmu: fix RCU page table walking

hw_ptep holds a pointer to a pt_element in rcu_ptr object, but this
is not the pointer that is protected by RCU, hw_ptep object are always
live on a stack and never accessed from more than one thread. The one
that is protected by RCU and can be changed concurrently resides in page
table itself. Fix that by making a pointer to point to atomic type and
use correct memory order during various accesses.

Signed-off-by: Gleb Natapov <gleb@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mmu: make hw_ptep class to be a template parametrized on pte level

Utilize c++ type system to make it harder to pass wrong level ptes to
functions that expect certain pte level. Also, since now each hw_pte
level is different type, we can implement accessors differently for
each level. That allows us to use RCU accessors only for levels which
point to pages that can bee rcu freed, namely, level 1 and 2.

Signed-off-by: Gleb Natapov <gleb@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mmu: remove size parameter from page ops class and file map/unmap functions

Now, when page level is encoded into hw_ptep, size parameter is no
longer needed since size can be deduced from pte itself.

Signed-off-by: Gleb Natapov <gleb@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mmu: consolidate (small|huge)_page mapper operations

Now, when page level is encoded into hw_ptep, no need to have separate
handlers for small and large leaf pages. Most of them are nearly
identical anyways.

Signed-off-by: Gleb Natapov <gleb@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
tests: Rename tst-fsx.c to misc-fsx.c

It's a manual test case, so rename it to misc-fsx.c and remove it from
the blacklist.

Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Merge branch 'timerwheel' of https://github.com/tgrabiec/osv

"The series introduces a data structure implementing an optimized algorithm
for managing timers which is optimized for not-expiring timers.

Both async timers (global) and core (per-CPU) timers are switched
to use the new implementation.

After applying this timer_task::reschedule is no longer at the top of CPU
profile, its footprint is reduced from 2-3% to below 1%. The overhead is
coming now from the across-CPU garbage collection routine:
async_worker::borrow_task().

It doesn't seem to have any significant impact on the tomcat benchmark."

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