route-table: Use classifier to store routing table.

Rather than using hmap for storing routing entries we can directly use
classifier which has support for priority and wildcard entries.
This makes route lookup lockless. This help when we use route lookup
for native tunneling.

Signed-off-by: Pravin B Shelar <pshelar@nicira.com>
Acked-by: Thomas Graf <tgraf@noironetworks.com>
Acked-by: Jarno Rajahalme <jrajahalme@nicira.com>

1 files changed, 275 insertions, 0 deletions

diff --git a/lib/ovs-router.c b/lib/ovs-router.c
new file mode 100644
index 000000000..c119c9422
--- /dev/null
+++ b/lib/ovs-router.c
@@ -0,0 +1,275 @@
+/*
+ * Copyright (c) 2014 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.
+ */
+
+#include <config.h>
+#include <arpa/inet.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <sys/socket.h>
+#include <net/if.h>
+#include <netinet/in.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "classifier.h"
+#include "command-line.h"
+#include "compiler.h"
+#include "dpif.h"
+#include "dynamic-string.h"
+#include "netdev.h"
+#include "packets.h"
+#include "ovs-router.h"
+#include "unixctl.h"
+#include "util.h"
+
+static struct classifier cls;
+
+struct ovs_router_entry {
+    struct cls_rule cr;
+    char output_bridge[IFNAMSIZ];
+    ovs_be32 gw;
+    ovs_be32 nw_addr;
+    uint8_t plen;
+    uint8_t priority;
+};
+
+static struct ovs_router_entry *
+ovs_router_entry_cast(const struct cls_rule *cr)
+{
+    if (offsetof(struct ovs_router_entry, cr) == 0) {
+        return CONTAINER_OF(cr, struct ovs_router_entry, cr);
+    } else {
+        return cr ? CONTAINER_OF(cr, struct ovs_router_entry, cr) : NULL;
+    }
+}
+
+bool
+ovs_router_lookup(ovs_be32 ip_dst, char output_bridge[], ovs_be32 *gw)
+{
+    const struct cls_rule *cr;
+    struct flow flow = {.nw_dst = ip_dst};
+
+    cr = classifier_lookup(&cls, &flow, NULL);
+    if (cr) {
+        struct ovs_router_entry *p = ovs_router_entry_cast(cr);
+
+        strncpy(output_bridge, p->output_bridge, IFNAMSIZ);
+        *gw = p->gw;
+        return true;
+    }
+    return false;
+}
+
+static void
+rt_entry_free(struct ovs_router_entry *p)
+{
+    cls_rule_destroy(&p->cr);
+    free(p);
+}
+
+static void rt_init_match(struct match *match, ovs_be32 ip_dst, uint8_t plen)
+{
+    ovs_be32 mask;
+
+    mask = htonl(UINT32_MAX << (32 - plen));
+
+    ip_dst &= mask; /* Clear out insignificant bits. */
+    memset(match, 0, sizeof *match);
+    match->flow.nw_dst = ip_dst;
+    match->wc.masks.nw_dst = mask;
+}
+
+static void
+ovs_router_insert__(uint8_t priority, ovs_be32 ip_dst, uint8_t plen,
+                    const char output_bridge[],
+                    ovs_be32 gw)
+{
+    const struct cls_rule *cr;
+    struct ovs_router_entry *p;
+    struct match match;
+
+    rt_init_match(&match, ip_dst, plen);
+
+    p = xzalloc(sizeof *p);
+    strncpy(p->output_bridge, output_bridge, IFNAMSIZ);
+    p->gw = gw;
+    p->nw_addr = match.flow.nw_dst;
+    p->plen = plen;
+    p->priority = priority;
+    cls_rule_init(&p->cr, &match, priority); /* Longest prefix matches first. */
+
+    cr = classifier_replace(&cls, &p->cr);
+    if (cr) {
+        /* An old rule with the same match was displaced. */
+        ovsrcu_postpone(rt_entry_free, ovs_router_entry_cast(cr));
+    }
+}
+
+void
+ovs_router_insert(ovs_be32 ip_dst, uint8_t plen, const char output_bridge[],
+                  ovs_be32 gw)
+{
+    ovs_router_insert__(plen, ip_dst, plen, output_bridge, gw);
+}
+
+static bool
+rt_entry_delete(uint8_t priority, ovs_be32 ip_dst, uint8_t plen)
+{
+    struct cls_rule *cr;
+    struct cls_rule rule;
+    struct match match;
+
+    rt_init_match(&match, ip_dst, plen);
+
+    cls_rule_init(&rule, &match, priority);
+
+    /* Find the exact rule. */
+    cr = classifier_find_rule_exactly(&cls, &rule);
+    if (cr) {
+        /* Remove it. */
+        cr = classifier_remove(&cls, cr);
+        if (cr) {
+
+            ovsrcu_postpone(rt_entry_free, ovs_router_entry_cast(cr));
+            return true;
+        }
+    }
+    return false;
+}
+
+static bool
+scan_ipv4_route(const char *s, ovs_be32 *addr, unsigned int *plen)
+{
+    int len, max_plen, n;
+    int slen = strlen(s);
+    uint8_t *ip = (uint8_t *)addr;
+
+    *addr = htons(0);
+    if (!ovs_scan(s, "%"SCNu8"%n", &ip[0], &n)) {
+        return false;
+    }
+    len = n;
+    max_plen = 8;
+    for (int i = 1; i < 4; i++) {
+        if (ovs_scan(s + len, ".%"SCNu8"%n", &ip[i], &n)) {
+            len += n;
+            max_plen += 8;
+        } else {
+            break;
+        }
+    }
+    if (len == slen && max_plen == 32) {
+        *plen = 32;
+        return true;
+    }
+    if (ovs_scan(s + len, "/%u%n", plen, &n)
+        && len + n == slen && *plen <= max_plen) {
+        return true;
+    }
+    return false;
+}
+
+static void
+ovs_router_add(struct unixctl_conn *conn, int argc,
+              const char *argv[], void *aux OVS_UNUSED)
+{
+    ovs_be32 ip, gw;
+    unsigned int plen;
+
+    if (scan_ipv4_route(argv[1], &ip, &plen)) {
+        if (argc > 3) {
+            inet_pton(AF_INET, argv[3], (struct in_addr *)&gw);
+        } else {
+            gw = 0;
+        }
+        ovs_router_insert__(plen + 32, ip, plen, argv[2], gw);
+        unixctl_command_reply(conn, "OK");
+    } else {
+        unixctl_command_reply(conn, "Invalid parameters");
+    }
+}
+
+static void
+ovs_router_del(struct unixctl_conn *conn, int argc OVS_UNUSED,
+              const char *argv[], void *aux OVS_UNUSED)
+{
+    ovs_be32 ip;
+    unsigned int plen;
+
+    if (scan_ipv4_route(argv[1], &ip, &plen)) {
+
+        if (rt_entry_delete(plen + 32, ip, plen)) {
+            unixctl_command_reply(conn, "OK");
+        } else {
+            unixctl_command_reply(conn, "Not found");
+        }
+    } else {
+        unixctl_command_reply(conn, "Invalid parameters");
+    }
+}
+
+static void
+ovs_router_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
+               const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
+{
+    struct ovs_router_entry *rt;
+    struct ds ds = DS_EMPTY_INITIALIZER;
+
+    ds_put_format(&ds, "Route Table:\n");
+    CLS_FOR_EACH(rt, cr, &cls) {
+        if (rt->priority == rt->plen) {
+            ds_put_format(&ds, "Cached: ");
+        } else {
+            ds_put_format(&ds, "User: ");
+        }
+        ds_put_format(&ds, IP_FMT"/%"PRIu16" dev %s",
+                      IP_ARGS(rt->nw_addr), rt->plen,
+                      rt->output_bridge);
+        if (rt->gw) {
+            ds_put_format(&ds, " GW "IP_FMT, IP_ARGS(rt->gw));
+        }
+        ds_put_format(&ds, "\n");
+    }
+    unixctl_command_reply(conn, ds_cstr(&ds));
+    ds_destroy(&ds);
+}
+
+void
+ovs_router_flush(void)
+{
+    struct ovs_router_entry *rt;
+
+    CLS_FOR_EACH_SAFE(rt, cr, &cls) {
+        if (rt->priority == rt->plen) {
+            classifier_remove(&cls, &rt->cr);
+        }
+    }
+}
+
+/* May not be called more than once. */
+void
+ovs_router_unixctl_register(void)
+{
+    classifier_init(&cls, NULL);
+    /* XXX: Add documentation for these commands. */
+    unixctl_command_register("ovs/route/add", "ip mask dev gw", 2, 3,
+                             ovs_router_add, NULL);
+    unixctl_command_register("ovs/route/show", "", 0, 0, ovs_router_show, NULL);
+    unixctl_command_register("ovs/route/del", "ip mask", 1, 1, ovs_router_del,
+                             NULL);
+}