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>
vfs: add dentry_ref, a smart pointer for dentrys

Makes managing references easier.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
vfs: convert file::f_dentry to dentry_ref

Fixes possible leak in sys_open() and vfs_file::close() error cases.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
vfs: make error class build in C code

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
vfs: add C++ namei()

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
vfs: covert sys_stat, sys_statfs to C++ namei

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.