AUTHORS: Fix spelling of Anoob Soman's name.

Signed-off-by: Ben Pfaff <blp@nicira.com>
dpif: Refactor flow dumping interface to make better sense for batching.

Commit a6ce4b9d251 (ofproto-dpif-upcall: Avoid use-after-free in
revalidate() corner case.) showed that it is somewhat tricky to correctly
use the existing dpif flow dumping interface to obtain batches of flows.
One has to be careful about calling dpif_flow_dump_next_may_destroy_keys()
before going on to the next flow.

A better interface is possible, one that is naturally oriented toward
retrieving batches when that is a useful optimization.  This commit
replaces the dpif interface by such a design, and updates both the
implementations and the callers to adopt it.

This is a fairly large change, but I think that the code in
ofproto-dpif-upcall is easier to understand after the change.

Signed-off-by: Ben Pfaff <blp@nicira.com>
cmap: New module for cuckoo hash table.

This implements an "optimistic concurrent cuckoo hash", a single-writer,
multiple-reader hash table data structure.  The point of this data
structure is performance, so this commit message focuses on performance.

I tested the performance of cmap with the test-cmap utility included in
this commit.  It takes three parameters for benchmarking:

    - n, the number of elements to insert.

    - n_threads, the number of threads to use for searching and
      mutating the hash table.

    - mutations, the percentage of operations that should modify the
      hash table, from 0% to 100%.

e.g. "test-cmap 1000000 16 1" inserts one million elements, uses 16
threads, and 1% of the operations modify the hash table.

Any given run does the following for both hmap and cmap
implementations:

    - Inserts n elements into a hash table.

    - Iterates over all of the elements.

    - Spawns n_threads threads, each of which searches for each of the
      elements in the hash table, once, and removes the specified
      percentage of them.

    - Removes each of the (remaining) elements and destroys the hash
      table.

and reports the time taken by each step,

The tables below report results for various parameters with a draft version
of this library.  The tests were not formally rerun for the final version,
but the intermediate changes should only have improved performance, and
this seemed to be the case in some informal testing.

n_threads=16 was used each time, on a 16-core x86-64 machine.  The compiler
used was Clang 3.5.  (GCC yields different numbers but similar relative
results.)

The results show:

    - Insertion is generally 3x to 5x faster in an hmap.

    - Iteration is generally about 3x faster in a cmap.

    - Search and mutation is 4x faster with .1% mutations and the
      advantage grows as the fraction of mutations grows.  This is
      because a cmap does not require locking for read operations,
      even in the presence of a writer.

      With no mutations, however, no locking is required in the hmap
      case, and the hmap is somewhat faster.  This is because raw hmap
      search is somewhat simpler and faster than raw cmap search.

    - Destruction is faster, usually by less than 2x, in an hmap.

n=10,000,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:   6132  2182     6136   2178      6111   2174       6124  2180
iterate:   370  1203      378   1201       370   1200        371  1202
search:   1375  8692     2393  28197     18402  80379       1281  1097
destroy:  1382  1187     1197   1034       324    241       1405  1205

n=1,000,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:    311    25      310     60       311     59        310    60
iterate:    25    62       25     64        25     57         25    60
search:    115   637      197   2266      1803   7284        101    67
destroy:   103    64       90     59        25     13        104    66

n=100,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:     25     6       26      5        25      5         25     5
iterate:     1     3        1      3         1      3          2     3
search:     12    57       27    219       164    735         10     5
destroy:     5     3        6      3         2      1          6     4

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jarno Rajahalme <jrajahalme@nicira.com>
dpif-netdev: Use cmap for ports.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jarno Rajahalme <jrajahalme@nicira.com>