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>
net: kill lltable_drain

It has been #if 0'd in freebsd too. It is dead code. Remove it.

Signed-off-by: Asias He <asias@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
net: kill arp_ifinit2

It is used in sys/netinet/ip_carp.c by CARP[1][2] protocol which we do not
support it now and have very little chance to support it in the future.

[1] http://www.freebsd.org/doc/en_US.ISO8859-1/books/handbook/carp.html
[2] http://www.freebsd.org/cgi/man.cgi?query=carp&sektion=4&n=1

Signed-off-by: Asias He <asias@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
net: Remove dead code in if.cc

This is backport from freebsd:

   commit 58f7b15da98d85f702ada8a45f4e1f50c97f5155
   Author: melifaro <melifaro@FreeBSD.org>
   Date:   Tue Jan 7 19:00:40 2014 +0000

       Remove dead code.

       Reported by:        Coverity
       Coverity CID:       1018057
       MFC after:  2 weeks

       Reviewed by:        bz

Signed-off-by: Asias He <asias@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
net: Remove ifa_ref()/ifa_free(), which are atomic(9), from ip_output()

This is backport from freebsd:

   commit 2c50988dca8f1c498ada4b3c8c0c275a7c324622
   Author: glebius <glebius@FreeBSD.org>
   Date:   Tue Mar 4 19:49:41 2014 +0000

       Remove ifa_ref()/ifa_free(), which are atomic(9), from ip_output().

       The ifaddr is already referenced by the rtentry, and we are holding
       reference on the rtentry throughout the function execution.

       Sponsored by:       Netflix
       Sponsored by:       Nginx, Inc.

Signed-off-by: Asias He <asias@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
net: Do not leak ifa in ip_output

This is backport from freebsd:

   commit ab0c56942296d702f3fb3e9418d3cde78711097b
   Author: glebius <glebius@FreeBSD.org>
   Date:   Wed Jul 9 07:48:05 2014 +0000

       In several cases in ip_output() we obtain reference on ifa. Do not
       leak it.

Signed-off-by: Asias He <asias@cloudius-systems.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
loader: get offset of list and set hooks in page_range

Hardcoded values are not nice and make it easy break something as
I demonstrated in 9202b75. Fixes #407.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Lua: Install modules with LuaRocks

Replace the manual building and installation of Lua modules with LuaRocks,
a management system for Lua modules.

Added the regular Lua executable to execute LuaRocks.
LuaRocks libraries and executables are excluded from the image, since it's only
needed in build time.

Signed-off-by: Or Cohen <orc@fewbytes.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>
Lua: Add lua-stdlib to available Lua modules

Contains many useful utilities to be used in the CLI.

Signed-off-by: Or Cohen <orc@fewbytes.com>
Signed-off-by: Pekka Enberg <penberg@cloudius-systems.com>