Route Cache patch #1

The first patch replaces the calls to the BSD functions in three places
by calls to a new function route_cache::lookup(). lookup() is a new
function which still does the slow lock-full lookup, but the point of
this patch is twofold: 1. To verify that indeed, these three places are
all the lookups done in the fast-path of the UDP memcached and tomcat
benchmarks (other benchmarks may involve more code paths, can be fixed
later).
2. Now lookup() takes care of the locking, and there is no need to
unlock a route after calling it - and the first patch verifies this
movement of the unlock code indeed works as a expected.

Note that this patch defines an invalidate() function but nothing
ever defines it, nor uses it. Once we're confident about the direction
of these two patches, I think it should be pretty straighforward to
implement and call invalidate() on route changes.

Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Route Cache patch #2

The second patch is starting to rewrite lookup() to have an RCU cache
so the route is first looked up in the cache, and only if it's not there,
look it up in the old slow way (as in the first patch) and add it to the
cache. Instead of using sophisticated radix tree (possibly even BSD's
super-convoluted implementation) for this cache, this patch uses a linear
search of netmasks. If we have a handful of routes (usually we'll just
have two or three), the linear search is fast enough.

Signed-off-by: Nadav Har'El <nyh@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Merge branch 'route-cache'

Nadav writes in the cover letter:

  This is a series of two patches aimed to remove the routing table
  locking (rwlock and mutex) which currently happens in the BSD code
  every time a packet is set, often resulting in a million locks per
  second, and in multi-threaded scenarios, can also cause contention
  because of our unscalable rwlock implementation (where readers must
  syncrhonize among themselves, despite only being readers).

  The first patch replaces the calls to the BSD functions in three places
  by calls to a new function route_cache::lookup(). lookup() is a new
  function which still does the slow lock-full lookup, but the point of
  this patch is twofold: 1. To verify that indeed, these three places are
  all the lookups done in the fast-path of the UDP memcached benchmark
  (other benchmarks may involve more code paths, can be fixed later).
  2. Now lookup() takes care of the locking, and there is no need to
  unlock a route after calling it - and the first patch verifies this
  movement of the unlock code indeed works as a expected.

  The second patch is starting rewrites lookup() to have an RCU cache
  so the route is first looked up in the cache, and only if it's not there,
  look it up in the old slow way (as in the first patch) and add it to the
  cache.

  In my experiments on Memcached (UDP) and Tomcat (TCP) these patches
  indeed eliminated all the locks (rwlock and mutex) coming from the
  route lookup on every output packet.

Tomek confirms that this improves Tomcat performance:

  I've performed a series of experiments using
  https://github.com/tgrabiec/tomcat-bench and this config:

  load_driver = {
      'ssh': 'huginn',
  }
  tomcat = {
      'ssh': 'muninn',
      'src_base': '/home/tgrabiec/src',
      'image_run_dir': '/data/tgrabiec/',
  }
  bridge = 'bridge2'

  I tested 3 images:
  master is dbdd63a94df244b7d62f9c40db9c876df609f6bb
  nadav is master + this series
  nadav-hacks is nadav + 1ff14cae01bf79f91552aaa90f5bf71639c372c3 + d0ca3509a78367213d3331b87ff10557db1ce941 + 754f6cc9092ed7bd7af58c5726d13a56aa8cbaf8

  Results (throughput):
           name        avg          stdev             min        max count
         master   63892.49          2349.59      59199.80   67261.25     9
          nadav   70142.33    +9.8% 1975.55      65920.22   73026.45    10
    nadav-hacks   79104.87   +23.8% 1246.69      77063.41   80862.42    10

  We can see that this series alone brings 10% improvement in throughput.

  It also looks like the remainder of the hacks branch also brings some
  improvements, probably due to ARP lock removal.

Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>