elf: move arch-specific object rela relocs to arch

Signed-off-by: Claudio Fontana <claudio.fontana@huawei.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
elf: move arch-specific object jump slot relocs to arch

Signed-off-by: Claudio Fontana <claudio.fontana@huawei.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
elf: move arch-specific initial dynamic segment relocs

move the initial arch-specific relocations done in get_init
into the arch-specific directories.

Signed-off-by: Claudio Fontana <claudio.fontana@huawei.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
drivers: Add null device

Signed-off-by: Raphael S. Carvalho <raphaelsc@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mmu: introduce memory areas

This patch introduces memory areas. They are going to be used to determine
which memory allocator is responsible for a particular object.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: use memory areas to determine the object allocator

Two new memory areas are introduced: early and mempool. Large allocations,
physically contiguous allocations and MMIO mappings happen in main memory
area.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: remove non_mempool_obj_offset

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Merge branch 'memarea'

"This series is the first step in implementing memory allocator enhancements
described by Avi in #87. Virtual memory starting from address 0xffff800000000000
is divided into memory areas. Each of the object allocators (currently: mempool,
large and early) return addresses to memory block only in its own memory area.
When memory block is freed bits [44:46] of its virtual address are used to
identify the responsible allocator.

phys_to_virt() makes things a bit tricky, since it is not possible to determine
to which memory area should the returned virtual address belong to. Current
solution is to return addresses in memory_area::main (used also by large memory
allocator) and make alloc_phys_contiguous_aligned() use memory::malloc_large()
only."

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

provide the symbol, but fail at every call.

Signed-off-by: Glauber Costa <glommer@cloudius-systems.com>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
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>