core: introduce deferred work framework

The design behind timer_task

timer_task was design for making cancel() and reschedule() scale well
with the number of threads and CPUs in the system. These methods may
be called frequently and from different CPUs. A task scheduled on one
CPU may be rescheduled later from another CPU. To avoid expensive
coordination between CPUs a lockfree per-CPU worker was implemented.

Every CPU has a worker (async_worker) which has task registry and a
thread to execute them. Most of the worker's state may only be changed
from the CPU on which it runs.

When timer_task is rescheduled it registers its percpu part in current
CPU's worker. When it is then rescheduled from another CPU, the
previous registration is marked as not valid and new percpu part is
registered. When percpu task fires it checks if it is the last
registration - only then it can fire.

Because timer_task's state is scattered across CPUs some extra
housekeeping needs to be done before it can be destroyed.  We need to
make sure that no percpu task will try to access timer_task object
after it is destroyed. To ensure that we walk the list of
registrations of given timer_task and atomically flip their state from
ACTIVE to RELEASED. If that succeeds it means the task is now revoked
and worker will not try to execute it. If that fails it means the task
is in the middle of firing and we need to wait for it to finish. When
the per-CPU task is moved to RELEASED state it is appended to worker's
queue of released percpu tasks using lockfree mpsc queue. These
objects may be later reused for registrations.
net: add tracepoints for inpcb life cycle
net: comment-out dead code
net: replace callouts with the new async framework

The callout subsystem is using a shared global lock for most of its
operations. This became a bottleneck after merging net channels.
Explanation for this phenomena is that before net channels
were merged packet processing on the receive side was done form one
(virtio) thread and there was no contention on that lock. After the
merge the packets started to be processed from many CPUs which made
taking the lock expensive.

The new framework uses only per-timer locks, the worker is lock-free.

Below are measurements of the improvement. The measurements (both
before and after) were taken with Nadav's per-CPU rcu_defer()
improvement applied, because it was also a bottleneck.

The value measured was HTTP request-response throughput of tomcat
server as reported by the wrk tool. Server and client on different
machines, 4 vCPUs, 3g of guest memory.

=== 16 connections ===

Before:

  avg = 39272.61
  stdev = 3611.84

After:

  avg = 52701.82
  stdev = 3953.76

Improvement: 34%

=== 256 connections ===

Before:

 avg = 35225.19
 stdev = 2504.27

After:

 avg = 50576.67
 stdev = 3533.39

Improvement: 43%

One challenge in integrating the new framework with TCP stack was a
proper teardown of timers. Current code assumed that after calling
callout_cancel() it is safe to free the timer's memory. This was not
correct because the timer may have already fired and will try to
access memory which has been freed. This is even less correct with the
new framework in which timers have state distributed over many CPUs
and an explicit shutdown() or timer_task destructor need to be
run. The TCP stack had a workaround for this race, each timer checked
the inp field of the tcpcb block for NULL, which was supposed to
indicate that the block has been freed. It still was not perfect
though because the timer may have performed the check before the field
was nulled-out in the tcp_discardcb and then block on a mutex which
will be promptly freed. The solution I went for is to delegate the
release of memory into an async deferred task, which will be executed
as soon as possible but in a safe context, in which we can wait until
all timers are shut down and then free the memory.
RCU: Per-CPU rcu_defer(), v2

v2: this is a complete redesign of the patch. Should more correct (the
previous version wasn't), doesn't rely on yield(), and does fewer copies
and memory allocations.

The existing rcu_defer() used a global list of deferred work, protected by
a global mutex. It also woke up the cleanup thread on every call. These
decisions made rcu_dispose() noticably slower than a regular delete, to the
point that when commit 70502950c097d082565952bfc9915278c7aedbce introduced
an rcu_dispose() to every poll() call, we saw performance of UDP memcached,
which calls poll() on every request, drop by as much as 40%.

The slowness of rcu_defer() was even more apparent in an artificial benchmark
which repeatedly calls new and rcu_dispose from one or several concurrent
threads. While on my machine a new/delete pair takes 24 ns, a new/rcu_dispose
from a single thread (on a 4 cpus VM) takes a whopping 330 ns, and worse -
when we have 4 threads on 4 cpus in a tight new/rcu_dispose loop, the mutex
contention, the fact we free the memory on the "wrong" cpu, and the excessive
context switches all bring the measurement to as much as 12,000 ns.

With this patch the new/rcu_dispose numbers are down to 60 ns on a single
thread (on 4 cpus) and 111 ns on 4 concurrent threads (on 4 cpus). This is
a x5.5 - x120 speedup :-)

This patch replaces the single list of functions with a per-cpu list.
rcu_defer() can add more callbacks to this per-cpu list without a mutex,
and instead of a single "garbage collection" thread running these callbacks,
the per-cpu RCU thread, which we already had, is the one that runs the work
deferred on this cpu's list. This per-cpu work is particularly effective
for free() work (i.e., rcu_dispose()) because it is faster to free memory
on the same CPU where it was allocated. This patch eliminates the single
"garbage collection" thread which the previous code needed.

The per-CPU work queue has a fixed size, currently set to 2000 functions.
It is actually a double-buffer, so we can continue to accumulate more work
while cleaning up; If rcu_defer() is used so quickly that it outpaces the
cleanup  rcu_defer() will wait while the buffer is full.
The choice of buffer size is a tradeoff between speed and memory: a larger
buffer means fewer context switches (between the thread doing rcu_defer()
and the RCU thread doing the cleanup), but also more memory temporarily
being used by unfreed objects.

Unlike the previous code, we do not wake up the cleanup threads after
every rcu_defer(). When the RCU cleanup work is frequent but still small
relative to the main work of the application (e.g., memcached server),
the RCU cleanup thread would always have low runtime which meant we suffered
a context switch on almost every wakeup of this thread by rcu_defer().
In this patch, we only wake up the cleanup thread when the buffer becomes
full, so we have far fewer context switches. This means that currently
rcu_defer() may delay the cleanup an unbounded amount of time. This is
normally not a problem, and when it it, namely in rcu_synchronize(),
we wake up the thread immediately.

Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
asapt RCU
run.py: allow multiple arguments to --trace

Currently --trace may only be used with one tracepoint, this
change allows to pass multiple like this:

 scripts/run.py --trace trace_point1* trace_point2*
sched: change timer state inside atomic context

timer_base is a thread-agnostic interface for per-CPU timers.  The
current code is prone to a race condition involving set() and
cancel(). The latter may attempt to remove the timer before it was
inserted into timer tree.

Found during code inspection.
trace: fix use of undefined symbol