lib/route-table.c

   1 /*
   2  * Copyright (c) 2011 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "route-table.h"
  20
  21 #include <assert.h>
  22 #include <arpa/inet.h>
  23 #include <sys/socket.h>
  24 #include <linux/rtnetlink.h>
  25 #include <net/if.h>
  26
  27 #include "hash.h"
  28 #include "hmap.h"
  29 #include "netlink.h"
  30 #include "netlink-socket.h"
  31 #include "ofpbuf.h"
  32 #include "rtnetlink.h"
  33 #include "vlog.h"
  34
  35 VLOG_DEFINE_THIS_MODULE(route_table);
  36
  37 struct route_data {
  38     /* Copied from struct rtmsg. */
  39     unsigned char rtm_dst_len;
  40
  41     /* Extracted from Netlink attributes. */
  42     uint32_t rta_dst; /* Destination in host byte order. 0 if missing. */
  43     int rta_oif;      /* Output interface index. */
  44 };
  45
  46 /* A digested version of a route message sent down by the kernel to indicate
  47  * that a route has changed. */
  48 struct route_table_msg {
  49     bool relevant;        /* Should this message be processed? */
  50     int nlmsg_type;       /* e.g. RTM_NEWROUTE, RTM_DELROUTE. */
  51     struct route_data rd; /* Data parsed from this message. */
  52 };
  53
  54 struct route_node {
  55     struct hmap_node node; /* Node in route_map. */
  56     struct route_data rd;  /* Data associated with this node. */
  57 };
  58
  59 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
  60
  61 static unsigned int register_count = 0;
  62 static struct rtnetlink *rtn = NULL;
  63 static struct route_table_msg rtmsg;
  64 static struct rtnetlink_notifier notifier;
  65 static struct hmap route_map;
  66
  67 static int route_table_reset(void);
  68 static bool route_table_parse(struct ofpbuf *, struct route_table_msg *);
  69 static void route_table_change(const struct route_table_msg *, void *);
  70 static struct route_node *route_node_lookup(const struct route_data *);
  71 static struct route_node *route_node_lookup_by_ip(uint32_t ip);
  72 static void route_map_clear(void);
  73 static uint32_t hash_route_data(const struct route_data *);
  74
  75 /* Populates 'ifindex' with the interface index traffic destined for 'ip' is
  76  * likely to egress.  There is no hard guarantee that traffic destined for 'ip'
  77  * will egress out the specified interface.  'ifindex' may refer to an
  78  * interface which is not physical (such as a bridge port).
  79  *
  80  * Returns true if successful, otherwise false. */
  81 bool
  82 route_table_get_ifindex(ovs_be32 ip_, int *ifindex)
  83 {
  84     struct route_node *rn;
  85     uint32_t ip = ntohl(ip_);
  86
  87     *ifindex = 0;
  88
  89     rn = route_node_lookup_by_ip(ip);
  90
  91     if (rn) {
  92         *ifindex = rn->rd.rta_oif;
  93         return true;
  94     }
  95
  96     /* Choose a default route. */
  97     HMAP_FOR_EACH(rn, node, &route_map) {
  98         if (rn->rd.rta_dst == 0 && rn->rd.rtm_dst_len == 0) {
  99             *ifindex = rn->rd.rta_oif;
 100             return true;
 101         }
 102     }
 103
 104     return false;
 105 }
 106
 107 /* Users of the route_table module should register themselves with this
 108  * function before making any other route_table function calls. */
 109 void
 110 route_table_register(void)
 111 {
 112     if (!register_count) {
 113         rtnetlink_parse_func *pf;
 114         rtnetlink_notify_func *nf;
 115
 116         assert(!rtn);
 117
 118         pf = (rtnetlink_parse_func *)  route_table_parse;
 119         nf = (rtnetlink_notify_func *) route_table_change;
 120
 121         rtn = rtnetlink_create(RTNLGRP_IPV4_ROUTE, pf, &rtmsg);
 122         rtnetlink_notifier_register(rtn, &notifier, nf, NULL);
 123
 124         hmap_init(&route_map);
 125         route_table_reset();
 126     }
 127
 128     register_count++;
 129 }
 130
 131 /* Users of the route_table module should unregister themselves with this
 132  * function when they will no longer be making any more route_table fuction
 133  * calls. */
 134 void
 135 route_table_unregister(void)
 136 {
 137     register_count--;
 138
 139     if (!register_count) {
 140         rtnetlink_destroy(rtn);
 141         rtn = NULL;
 142
 143         route_map_clear();
 144         hmap_destroy(&route_map);
 145     }
 146 }
 147
 148 /* Run periodically to update the locally maintained routing table. */
 149 void
 150 route_table_run(void)
 151 {
 152     if (rtn) {
 153         rtnetlink_notifier_run(rtn);
 154     }
 155 }
 156
 157 /* Causes poll_block() to wake up when route_table updates are required. */
 158 void
 159 route_table_wait(void)
 160 {
 161     if (rtn) {
 162         rtnetlink_notifier_wait(rtn);
 163     }
 164 }
 165
 166 static int
 167 route_table_reset(void)
 168 {
 169     int error;
 170     struct nl_dump dump;
 171     struct rtgenmsg *rtmsg;
 172     struct ofpbuf request, reply;
 173     static struct nl_sock *rtnl_sock;
 174
 175     route_map_clear();
 176
 177     error = nl_sock_create(NETLINK_ROUTE, 0, 0, 0, &rtnl_sock);
 178     if (error) {
 179         VLOG_WARN_RL(&rl, "failed to reset routing table, "
 180                      "cannot create RTNETLINK_ROUTE socket");
 181         return error;
 182     }
 183
 184     ofpbuf_init(&request, 0);
 185
 186     nl_msg_put_nlmsghdr(&request, sizeof *rtmsg, RTM_GETROUTE, NLM_F_REQUEST);
 187
 188     rtmsg = ofpbuf_put_zeros(&request, sizeof *rtmsg);
 189     rtmsg->rtgen_family = AF_INET;
 190
 191     nl_dump_start(&dump, rtnl_sock, &request);
 192
 193     while (nl_dump_next(&dump, &reply)) {
 194         struct route_table_msg msg;
 195
 196         if (route_table_parse(&reply, &msg)) {
 197             route_table_change(&msg, NULL);
 198         }
 199     }
 200
 201     error = nl_dump_done(&dump);
 202     nl_sock_destroy(rtnl_sock);
 203
 204     return error;
 205 }
 206
 207
 208 static bool
 209 route_table_parse(struct ofpbuf *buf, struct route_table_msg *change)
 210 {
 211     bool parsed;
 212
 213     static const struct nl_policy policy[] = {
 214         [RTA_DST] = { .type = NL_A_U32, .optional = true  },
 215         [RTA_OIF] = { .type = NL_A_U32, .optional = false },
 216     };
 217
 218     static struct nlattr *attrs[ARRAY_SIZE(policy)];
 219
 220     parsed = nl_policy_parse(buf, NLMSG_HDRLEN + sizeof(struct rtmsg),
 221                              policy, attrs, ARRAY_SIZE(policy));
 222
 223     if (parsed) {
 224         const struct rtmsg *rtm;
 225         const struct nlmsghdr *nlmsg;
 226
 227         nlmsg = buf->data;
 228         rtm = (const struct rtmsg *) ((const char *) buf->data + NLMSG_HDRLEN);
 229
 230         if (rtm->rtm_family != AF_INET) {
 231             VLOG_DBG_RL(&rl, "received non AF_INET rtnetlink route message");
 232             return false;
 233         }
 234
 235         memset(change, 0, sizeof *change);
 236         change->relevant = true;
 237
 238         if (rtm->rtm_scope == RT_SCOPE_NOWHERE) {
 239             change->relevant = false;
 240         }
 241
 242         if (rtm->rtm_type != RTN_UNICAST &&
 243             rtm->rtm_type != RTN_LOCAL) {
 244             change->relevant = false;
 245         }
 246
 247         change->nlmsg_type     = nlmsg->nlmsg_type;
 248         change->rd.rtm_dst_len = rtm->rtm_dst_len;
 249         change->rd.rta_oif     = nl_attr_get_u32(attrs[RTA_OIF]);
 250
 251         if (attrs[RTA_DST]) {
 252             change->rd.rta_dst = ntohl(nl_attr_get_be32(attrs[RTA_DST]));
 253         }
 254
 255     } else {
 256         VLOG_DBG_RL(&rl, "received unparseable rtnetlink route message");
 257     }
 258
 259     return parsed;
 260 }
 261
 262 static void
 263 route_table_change(const struct route_table_msg *change, void *aux OVS_UNUSED)
 264 {
 265     if (!change) {
 266         VLOG_DBG_RL(&rl, "received NULL change message");
 267         route_table_reset();
 268     } else if (!change->relevant) {
 269         VLOG_DBG_RL(&rl, "ignoring irrelevant change message");
 270     } else if (change->nlmsg_type == RTM_NEWROUTE) {
 271         if (!route_node_lookup(&change->rd)) {
 272             struct route_node *rn;
 273
 274             rn = xzalloc(sizeof *rn);
 275             memcpy(&rn->rd, &change->rd, sizeof change->rd);
 276
 277             hmap_insert(&route_map, &rn->node, hash_route_data(&rn->rd));
 278         } else {
 279             VLOG_DBG_RL(&rl, "skipping insertion of duplicate route entry");
 280         }
 281     } else if (change->nlmsg_type == RTM_DELROUTE) {
 282         struct route_node *rn;
 283
 284         rn = route_node_lookup(&change->rd);
 285
 286         if (rn) {
 287             hmap_remove(&route_map, &rn->node);
 288             free(rn);
 289         } else {
 290             VLOG_DBG_RL(&rl, "skipping deletion of non-existent route entry");
 291         }
 292     }
 293 }
 294
 295 static struct route_node *
 296 route_node_lookup(const struct route_data *rd)
 297 {
 298     struct route_node *rn;
 299
 300     HMAP_FOR_EACH_WITH_HASH(rn, node, hash_route_data(rd), &route_map) {
 301         if (!memcmp(&rn->rd, rd, sizeof *rd)) {
 302             return rn;
 303         }
 304     }
 305
 306     return NULL;
 307 }
 308
 309 static struct route_node *
 310 route_node_lookup_by_ip(uint32_t ip)
 311 {
 312     int dst_len;
 313     struct route_node *rn, *rn_ret;
 314
 315     dst_len = -1;
 316     rn_ret  = NULL;
 317
 318     HMAP_FOR_EACH(rn, node, &route_map) {
 319         uint32_t mask = 0xffffffff << (32 - rn->rd.rtm_dst_len);
 320
 321         if (rn->rd.rta_dst == 0 && rn->rd.rtm_dst_len == 0) {
 322             /* Default route. */
 323             continue;
 324         }
 325
 326         if (rn->rd.rtm_dst_len > dst_len &&
 327             (ip & mask) == (rn->rd.rta_dst & mask)) {
 328             rn_ret  = rn;
 329             dst_len = rn->rd.rtm_dst_len;
 330         }
 331     }
 332
 333     return rn_ret;
 334 }
 335
 336 static void
 337 route_map_clear(void)
 338 {
 339     struct route_node *rn, *rn_next;
 340
 341     HMAP_FOR_EACH_SAFE(rn, rn_next, node, &route_map) {
 342         hmap_remove(&route_map, &rn->node);
 343         free(rn);
 344     }
 345 }
 346
 347 static uint32_t
 348 hash_route_data(const struct route_data *rd)
 349 {
 350     return hash_bytes(rd, sizeof *rd, 0);
 351 }