[ovs-dev] [thread 15/15] ofproto-dpif: Implement multi-threaded miss handling.

[Ben Pfaff]

On Thu, Aug 08, 2013 at 12:58:34PM -0700, Ethan Jackson wrote:
> This patch factors flow miss handling into its own module,
> ofproto-dpif-upcall which can utilize multiple threads to process
> misses.  For some important benchmarks, this change improves Open
> vSwitch flow setup performance by roughly 50x (that's 50 times not
> 50%) in my testing.
> 
> Signed-off-by: Ethan Jackson <ethan at nicira.com>

I've taken a look at this code to get an idea of the structure and
organization.  I'm happy with both, and especially with the simplicity.
There just isn't that much here, which is awesome.

I have not scrutinized this code to look for small bugs or even really
for some big ones.  But I think we should throw it into master and sort
out bugs as we find them.

Acked-by: Ben Pfaff <blp at nicira.com>

I noticed a couple typos in the struct udpif declaration.  s/thrad/thread/:
> +    pthread_t dispatcher;              /* Dispatcher thrad ID. */
and usually we put the * just before the name:
> +    struct seq* wait_seq;

Thanks for adding an overview comment to ofproto-dpif.h.  My only
suggestion there is that a few more blank lines would make it easier to
read, e.g.:

+/* Ofproto-dpif -- DPIF based ofproto implementation.
+ *
+ * Ofproto-dpif provides an ofproto implementation for those platforms which
+ * implement the netdev and dpif interface defined in netdev.h and dpif.h.  The
+ * most important of which is the Linux Kernel Module (dpif-linux), but
+ * alternatives are supported such as a userspace only implementation
+ * (dpif-netdev), and a dummy implementation used for unit testing.
+ *
+ * Ofproto-dpif is divided into three major chunks.
+ *
+ * - ofproto-dpif.c
+ *   The main ofproto-dpif module is responsible for implementing the
+ *   provider interface, installing and removing datapath flows, maintaining
+ *   packet statistics, running protocols (BFD, LACP, STP, etc), and
+ *   configuring relevant submodules.
+ *
+ * - ofproto-dpif-upcall.c
+ *   Ofproto-dpif-upcall is responsible for retrieving upcalls from the kernel,
+ *   processing miss upcalls, and handing more complex ones up to the main
+ *   ofproto-dpif module.  Miss upcall processing boils down to figuring out
+ *   what each packet's actions are, executing them (i.e. asking the kernel to
+ *   forward it), and handing it up to ofproto-dpif to decided whether or not
+ *   to install a kernel flow.
+ *
+ * - ofproto-dpif-xlate.c
+ *   Ofproto-dpif-xlate is responsible for translating translating OpenFlow
+ *   actions into datapath actions. */

I think that ofproto-dpif-upcall.h could use a top-level comment too.
If there's nothing more to say than what's above then just a reference
to ofproto-dpif.h would be helpful.

Actually I think ofproto-dpif-upcall might be easier to understand with
a little reorganization.  I took the liberty of doing this myself.  I'm
appending the result to the end of this email.  Feel free to use it or
change it or ignore it.

I have a suggested comment for struct handler:
/* A thread that processes each upcall handed to it by the dispatcher thread,
 * forwards the upcall's packet, and then queues it to the main ofproto_dpif to
 * possibly set up a kernel flow as a cache. */
and for struct udpif:
/* An upcall handler for ofproto_dpif.
 *
 * udpif is implemented as a "dispatcher" thread that reads upcalls from the
 * kernel.  It processes each upcall just enough to figure out its next
 * destination.  For a "miss" upcall (MISS_UPCALL), this is one of several
 * "handler" threads (see struct handler).  Other upcalls are queued to the
 * main ofproto_dpif. */

udpif_dispatcher() might use "while (!latch_is_set(&udpif->exit_latch))"
instead of for (;;).  udpif_miss_handler() too (I don't think that
handler->mutex is needed to check the latch).

I see that recv_upcalls() wakes up a handler after queuing a single
upcall to it.  I guess that this makes it fairly unlikely that
udpif_miss_handler() is able to get much of a batch.  Maybe we will need
some tuning there, hard to say.

I'm a little surprised that struct flow_miss_batch doesn't carry a
reval_seq or similar, so that when ofproto_dpif unqueues the fmb it can
compare the seq against whatever's current and throw it away if it
isn't.  But, I dunno, maybe the logic is that the fmb's actions are
likely to correct anyway and we'll fix them up if they aren't later in
revalidation?

--8<--------------------------cut here-------------------------->8--

/* Copyright (c) 2013 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License. */

#ifndef OFPROTO_DPIF_UPCALL_H
#define OFPROTO_DPIF_UPCALL_H

#define FLOW_MISS_MAX_BATCH 50

#include "dpif.h"
#include "flow.h"
#include "hmap.h"
#include "list.h"
#include "odp-util.h"
#include "ofpbuf.h"
#include "ofproto-dpif-xlate.h"

struct dpif;
struct dpif_backer;

/* udif is responsible for retrieving upcalls from the kernel, processing miss
 * upcalls, and handing more complex ones up to the main ofproto-dpif
 * module. */

struct udpif *udpif_create(struct dpif_backer *, struct dpif *);
void udpif_recv_set(struct udpif *, size_t n_workers, bool enable);
void udpif_destroy(struct udpif *);

void udpif_run(struct udpif *);
void udpif_wait(struct udpif *);

void udpif_revalidate(struct udpif *);

/* udpif can handle some upcalls on its own.  Others need the main ofproto_dpif
 * code to handle them.  This interface passes upcalls not handled by udpif up
 * to the ofproto_dpif main thread. */

/* Type of an upcall. */
enum upcall_type {
    /* Handled internally by udpif code.  Not returned by upcall_next().*/
    BAD_UPCALL,                 /* Some kind of bug somewhere. */
    MISS_UPCALL,                /*  */

    /* Require main thread's involvement.  May be returned by upcall_next(). */
    SFLOW_UPCALL,               /* sFlow sample. */
    FLOW_SAMPLE_UPCALL,         /* Per-flow sampling. */
    IPFIX_UPCALL                /* Per-bridge sampling. */
};

/* An upcall. */
struct upcall {
    struct list list_node;          /* For queuing upcalls. */

    enum upcall_type type;          /* Classification. */

    /* Raw upcall plus data for keeping track of the memory backing it. */
    struct dpif_upcall dpif_upcall; /* As returned by dpif_recv() */
    struct ofpbuf upcall_buf;       /* Owns some data in 'dpif_upcall'. */
    uint64_t upcall_stub[256 / 8];  /* Buffer to reduce need for malloc(). */
};

struct upcall *upcall_next(struct udpif *);
void upcall_destroy(struct upcall *);

/* udpif figures out how to forward packets, and does forward them, but it
 * can't set up datapath flows on its own.  This interface passes packet
 * forwarding data from udpif to the higher level ofproto_dpif to allow the
 * latter to set up datapath flows. */

/* Flow miss batching.
 *
 * Some dpifs implement operations faster when you hand them off in a batch.
 * To allow batching, "struct flow_miss" queues the dpif-related work needed
 * for a given flow.  Each "struct flow_miss" corresponds to sending one or
 * more packets, plus possibly installing the flow in the dpif. */
struct flow_miss {
    struct hmap_node hmap_node;
    struct ofproto_dpif *ofproto;

    struct flow flow;
    enum odp_key_fitness key_fitness;
    const struct nlattr *key;
    size_t key_len;
    struct list packets;
    enum dpif_upcall_type upcall_type;
    struct dpif_flow_stats stats;

    struct xlate_out xout;

    struct list upcalls;
};

struct flow_miss_batch {
    struct list list_node;

    struct flow_miss miss_buf[FLOW_MISS_MAX_BATCH];
    struct hmap misses;
};

struct flow_miss_batch *flow_miss_batch_next(struct udpif *);
void flow_miss_batch_destroy(struct flow_miss_batch *);

/* Drop keys are odp flow keys which have drop flows installed in the kernel.
 * These are datapath flows which have no associated ofproto, if they did we
 * would use facets.
 *
 * udpif can't install drop flows by itself.  This interfaces allows udpif to
 * pass the drop flows up to ofproto_dpif to get it to install them. */
struct drop_key {
    struct hmap_node hmap_node;
    struct list list_node;
    struct nlattr *key;
    size_t key_len;
};

struct drop_key *drop_key_next(struct udpif *);
void drop_key_destroy(struct drop_key *);
void udpif_drop_key_clear(struct udpif *);

#endif /* ofproto-dpif-upcall.h */