bsd: add missing include to random.h

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
ring_spsc: introduce emplace() method

The method accepts a template functor which can be used to construct
the element in-place. Useful when storing large objects to avoid
copying cost.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
core: introduce unordered_ring_mpsc

It's supposed to be an efficient multiple-producer single-consumer
non-blocking container based on per-CPU rings.

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
tests: add test for unordered_ring_mpsc

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
bsd: C++'ify random_harvestq.c

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
random: make random_harvest() non-blocking

We need to make it non-blocking to use it in interrupt context.

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
random: collect entropy from interrupts

This is based on the FreeBSD implementation with slight
modifications. FreeBSD collects 2 bits of entropy from each interrupt,
based on:

 - interrupt vector number
 - current thread id
 - cycles counter

We collect 1 bit from the following information:

 - interrupt vector number
 - instruction pointer
 - cycles counter

For the reference I will describe what Linux is doing. Linux is using
the following information for entropy:

 - interrupt vector number
 - instruction pointer
 - cycles counter
 - jiffies counter

This information is hashed on Linux using a cryptographically unsecure
(but fast) hash into a per-CPU pool on every interrupt. Once every 64
interrupts or if a second has passed they feed the accumulated hash to
the common entropy pool and credit it for 1 bit of entropy.

 === Performance tests ===

I have performed tests on my laptop with netperf and iperf. The
results are below. I didn't see significant impact on performance.

$ netperf -H osv

=== Before ===

Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

 65536  16384  16384    10.00    1998.67
 65536  16384  16384    10.00    1958.58
 65536  16384  16384    10.00    1976.67
 65536  16384  16384    10.00    2050.17
 65536  16384  16384    10.00    2069.08

avg = 2010.63
stdev = 42.39

=== After ===

Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

 65536  16384  16384    10.00    1938.42
 65536  16384  16384    10.00    2003.05
 65536  16384  16384    10.00    2055.37
 65536  16384  16384    10.00    2016.63
 65536  16384  16384    10.00    1982.83

avg = 1999.26
stdev = 38.56

$ iperf -c osv -P 10 | grep SUM

=== Before ===

[SUM]  0.0-10.0 sec  1.85 GBytes  1.58 Gbits/sec
[SUM]  0.0-10.0 sec  1.78 GBytes  1.52 Gbits/sec
[SUM]  0.0-10.1 sec  1.84 GBytes  1.57 Gbits/sec
[SUM]  0.0-10.0 sec  1.77 GBytes  1.51 Gbits/sec
[SUM]  0.0-10.0 sec  1.92 GBytes  1.64 Gbits/sec
[SUM]  0.0-10.0 sec  1.87 GBytes  1.60 Gbits/sec
[SUM]  0.0-10.1 sec  1.78 GBytes  1.52 Gbits/sec
[SUM]  0.0-10.0 sec  1.83 GBytes  1.57 Gbits/sec
[SUM]  0.0-10.0 sec  1.78 GBytes  1.52 Gbits/sec

avg   = 1.82 [GBytes]
stdev = 0.05 [GBytes]

=== After ===

[SUM]  0.0-10.0 sec  1.85 GBytes  1.59 Gbits/sec
[SUM]  0.0-10.0 sec  1.82 GBytes  1.56 Gbits/sec
[SUM]  0.0-10.0 sec  1.83 GBytes  1.57 Gbits/sec
[SUM]  0.0-10.0 sec  1.82 GBytes  1.56 Gbits/sec
[SUM]  0.0-10.0 sec  2.02 GBytes  1.73 Gbits/sec
[SUM]  0.0-10.0 sec  1.81 GBytes  1.55 Gbits/sec
[SUM]  0.0-10.1 sec  1.80 GBytes  1.53 Gbits/sec
[SUM]  0.0-10.0 sec  1.50 GBytes  1.28 Gbits/sec
[SUM]  0.0-10.0 sec  1.83 GBytes  1.57 Gbits/sec
[SUM]  0.0-10.0 sec  1.89 GBytes  1.61 Gbits/sec

avg   = 1.82 [GBytes]
stdev = 0.12 [GBytes]

Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
random: Print warning when no hw source of entropy is available

live_entropy_source_empty() is introduced for the purpose of checking
whether or not any live entropy source was registered.

Reviewed-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Raphael S. Carvalho <raphaelsc@cloudius-systems.com>
Signed-off-by: Tomasz Grabiec <tgrabiec@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>