datapath/flow_table.c

   1 /*
   2  * Copyright (c) 2007-2013 Nicira, Inc.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of version 2 of the GNU General Public
   6  * License as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  16  * 02110-1301, USA
  17  */
  18
  19 #include "flow.h"
  20 #include "datapath.h"
  21 #include <linux/uaccess.h>
  22 #include <linux/netdevice.h>
  23 #include <linux/etherdevice.h>
  24 #include <linux/if_ether.h>
  25 #include <linux/if_vlan.h>
  26 #include <net/llc_pdu.h>
  27 #include <linux/kernel.h>
  28 #include <linux/jhash.h>
  29 #include <linux/jiffies.h>
  30 #include <linux/llc.h>
  31 #include <linux/module.h>
  32 #include <linux/in.h>
  33 #include <linux/rcupdate.h>
  34 #include <linux/if_arp.h>
  35 #include <linux/ip.h>
  36 #include <linux/ipv6.h>
  37 #include <linux/sctp.h>
  38 #include <linux/tcp.h>
  39 #include <linux/udp.h>
  40 #include <linux/icmp.h>
  41 #include <linux/icmpv6.h>
  42 #include <linux/rculist.h>
  43 #include <net/ip.h>
  44 #include <net/ipv6.h>
  45 #include <net/ndisc.h>
  46
  47 #include "vlan.h"
  48
  49 static struct kmem_cache *flow_cache;
  50
  51 static u16 range_n_bytes(const struct sw_flow_key_range *range)
  52 {
  53         return range->end - range->start;
  54 }
  55
  56 void ovs_flow_mask_key(struct sw_flow_key *dst, const struct sw_flow_key *src,
  57                        const struct sw_flow_mask *mask)
  58 {
  59         const long *m = (long *)((u8 *)&mask->key + mask->range.start);
  60         const long *s = (long *)((u8 *)src + mask->range.start);
  61         long *d = (long *)((u8 *)dst + mask->range.start);
  62         int i;
  63
  64         /* The memory outside of the 'mask->range' are not set since
  65          * further operations on 'dst' only uses contents within
  66          * 'mask->range'.
  67          */
  68         for (i = 0; i < range_n_bytes(&mask->range); i += sizeof(long))
  69                 *d++ = *s++ & *m++;
  70 }
  71
  72 struct sw_flow *ovs_flow_alloc(void)
  73 {
  74         struct sw_flow *flow;
  75
  76         flow = kmem_cache_alloc(flow_cache, GFP_KERNEL);
  77         if (!flow)
  78                 return ERR_PTR(-ENOMEM);
  79
  80         spin_lock_init(&flow->lock);
  81         flow->sf_acts = NULL;
  82         flow->mask = NULL;
  83
  84         return flow;
  85 }
  86
  87 static struct flex_array *alloc_buckets(unsigned int n_buckets)
  88 {
  89         struct flex_array *buckets;
  90         int i, err;
  91
  92         buckets = flex_array_alloc(sizeof(struct hlist_head),
  93                                    n_buckets, GFP_KERNEL);
  94         if (!buckets)
  95                 return NULL;
  96
  97         err = flex_array_prealloc(buckets, 0, n_buckets, GFP_KERNEL);
  98         if (err) {
  99                 flex_array_free(buckets);
 100                 return NULL;
 101         }
 102
 103         for (i = 0; i < n_buckets; i++)
 104                 INIT_HLIST_HEAD((struct hlist_head *)
 105                                         flex_array_get(buckets, i));
 106
 107         return buckets;
 108 }
 109
 110 static void flow_free(struct sw_flow *flow)
 111 {
 112         kfree((struct sf_flow_acts __force *)flow->sf_acts);
 113         kmem_cache_free(flow_cache, flow);
 114 }
 115
 116 static void rcu_free_flow_callback(struct rcu_head *rcu)
 117 {
 118         struct sw_flow *flow = container_of(rcu, struct sw_flow, rcu);
 119
 120         flow_free(flow);
 121 }
 122
 123 void ovs_flow_free(struct sw_flow *flow, bool deferred)
 124 {
 125         if (!flow)
 126                 return;
 127
 128         ovs_sw_flow_mask_del_ref(flow->mask, deferred);
 129
 130         if (deferred)
 131                 call_rcu(&flow->rcu, rcu_free_flow_callback);
 132         else
 133                 flow_free(flow);
 134 }
 135
 136 static void free_buckets(struct flex_array *buckets)
 137 {
 138         flex_array_free(buckets);
 139 }
 140
 141 static void __flow_tbl_destroy(struct flow_table *table)
 142 {
 143         int i;
 144
 145         if (table->keep_flows)
 146                 goto skip_flows;
 147
 148         for (i = 0; i < table->n_buckets; i++) {
 149                 struct sw_flow *flow;
 150                 struct hlist_head *head = flex_array_get(table->buckets, i);
 151                 struct hlist_node *n;
 152                 int ver = table->node_ver;
 153
 154                 hlist_for_each_entry_safe(flow, n, head, hash_node[ver]) {
 155                         hlist_del(&flow->hash_node[ver]);
 156                         ovs_flow_free(flow, false);
 157                 }
 158         }
 159
 160         BUG_ON(!list_empty(table->mask_list));
 161         kfree(table->mask_list);
 162
 163 skip_flows:
 164         free_buckets(table->buckets);
 165         kfree(table);
 166 }
 167
 168 static struct flow_table *__flow_tbl_alloc(int new_size)
 169 {
 170         struct flow_table *table = kmalloc(sizeof(*table), GFP_KERNEL);
 171
 172         if (!table)
 173                 return NULL;
 174
 175         table->buckets = alloc_buckets(new_size);
 176
 177         if (!table->buckets) {
 178                 kfree(table);
 179                 return NULL;
 180         }
 181         table->n_buckets = new_size;
 182         table->count = 0;
 183         table->node_ver = 0;
 184         table->keep_flows = false;
 185         get_random_bytes(&table->hash_seed, sizeof(u32));
 186         table->mask_list = NULL;
 187
 188         return table;
 189 }
 190
 191 struct flow_table *ovs_flow_tbl_alloc(int new_size)
 192 {
 193         struct flow_table *table = __flow_tbl_alloc(new_size);
 194
 195         if (!table)
 196                 return NULL;
 197
 198         table->mask_list = kmalloc(sizeof(struct list_head), GFP_KERNEL);
 199         if (!table->mask_list) {
 200                 table->keep_flows = true;
 201                 __flow_tbl_destroy(table);
 202                 return NULL;
 203         }
 204         INIT_LIST_HEAD(table->mask_list);
 205
 206         return table;
 207 }
 208
 209 static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu)
 210 {
 211         struct flow_table *table = container_of(rcu, struct flow_table, rcu);
 212
 213         __flow_tbl_destroy(table);
 214 }
 215
 216 void ovs_flow_tbl_destroy(struct flow_table *table, bool deferred)
 217 {
 218         if (!table)
 219                 return;
 220
 221         if (deferred)
 222                 call_rcu(&table->rcu, flow_tbl_destroy_rcu_cb);
 223         else
 224                 __flow_tbl_destroy(table);
 225 }
 226
 227 struct sw_flow *ovs_flow_tbl_dump_next(struct flow_table *table,
 228                                        u32 *bucket, u32 *last)
 229 {
 230         struct sw_flow *flow;
 231         struct hlist_head *head;
 232         int ver;
 233         int i;
 234
 235         ver = table->node_ver;
 236         while (*bucket < table->n_buckets) {
 237                 i = 0;
 238                 head = flex_array_get(table->buckets, *bucket);
 239                 hlist_for_each_entry_rcu(flow, head, hash_node[ver]) {
 240                         if (i < *last) {
 241                                 i++;
 242                                 continue;
 243                         }
 244                         *last = i + 1;
 245                         return flow;
 246                 }
 247                 (*bucket)++;
 248                 *last = 0;
 249         }
 250
 251         return NULL;
 252 }
 253
 254 static struct hlist_head *find_bucket(struct flow_table *table, u32 hash)
 255 {
 256         hash = jhash_1word(hash, table->hash_seed);
 257         return flex_array_get(table->buckets,
 258                                 (hash & (table->n_buckets - 1)));
 259 }
 260
 261 static void __tbl_insert(struct flow_table *table, struct sw_flow *flow)
 262 {
 263         struct hlist_head *head;
 264
 265         head = find_bucket(table, flow->hash);
 266         hlist_add_head_rcu(&flow->hash_node[table->node_ver], head);
 267
 268         table->count++;
 269 }
 270
 271 static void flow_table_copy_flows(struct flow_table *old,
 272                                   struct flow_table *new)
 273 {
 274         int old_ver;
 275         int i;
 276
 277         old_ver = old->node_ver;
 278         new->node_ver = !old_ver;
 279
 280         /* Insert in new table. */
 281         for (i = 0; i < old->n_buckets; i++) {
 282                 struct sw_flow *flow;
 283                 struct hlist_head *head;
 284
 285                 head = flex_array_get(old->buckets, i);
 286
 287                 hlist_for_each_entry(flow, head, hash_node[old_ver])
 288                         __tbl_insert(new, flow);
 289         }
 290
 291         new->mask_list = old->mask_list;
 292         old->keep_flows = true;
 293 }
 294
 295 static struct flow_table *__flow_tbl_rehash(struct flow_table *table,
 296                                             int n_buckets)
 297 {
 298         struct flow_table *new_table;
 299
 300         new_table = __flow_tbl_alloc(n_buckets);
 301         if (!new_table)
 302                 return ERR_PTR(-ENOMEM);
 303
 304         flow_table_copy_flows(table, new_table);
 305
 306         return new_table;
 307 }
 308
 309 struct flow_table *ovs_flow_tbl_rehash(struct flow_table *table)
 310 {
 311         return __flow_tbl_rehash(table, table->n_buckets);
 312 }
 313
 314 struct flow_table *ovs_flow_tbl_expand(struct flow_table *table)
 315 {
 316         return __flow_tbl_rehash(table, table->n_buckets * 2);
 317 }
 318
 319 static u32 flow_hash(const struct sw_flow_key *key, int key_start,
 320                      int key_end)
 321 {
 322         u32 *hash_key = (u32 *)((u8 *)key + key_start);
 323         int hash_u32s = (key_end - key_start) >> 2;
 324
 325         /* Make sure number of hash bytes are multiple of u32. */
 326         BUILD_BUG_ON(sizeof(long) % sizeof(u32));
 327
 328         return jhash2(hash_key, hash_u32s, 0);
 329 }
 330
 331 static int flow_key_start(const struct sw_flow_key *key)
 332 {
 333         if (key->tun_key.ipv4_dst)
 334                 return 0;
 335         else
 336                 return rounddown(offsetof(struct sw_flow_key, phy),
 337                                           sizeof(long));
 338 }
 339
 340 static bool cmp_key(const struct sw_flow_key *key1,
 341                     const struct sw_flow_key *key2,
 342                     int key_start, int key_end)
 343 {
 344         const long *cp1 = (long *)((u8 *)key1 + key_start);
 345         const long *cp2 = (long *)((u8 *)key2 + key_start);
 346         long diffs = 0;
 347         int i;
 348
 349         for (i = key_start; i < key_end;  i += sizeof(long))
 350                 diffs |= *cp1++ ^ *cp2++;
 351
 352         return diffs == 0;
 353 }
 354
 355 static bool flow_cmp_masked_key(const struct sw_flow *flow,
 356                                 const struct sw_flow_key *key,
 357                                 int key_start, int key_end)
 358 {
 359         return cmp_key(&flow->key, key, key_start, key_end);
 360 }
 361
 362 bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow,
 363                                struct sw_flow_match *match)
 364 {
 365         struct sw_flow_key *key = match->key;
 366         int key_start = flow_key_start(key);
 367         int key_end = match->range.end;
 368
 369         return cmp_key(&flow->unmasked_key, key, key_start, key_end);
 370 }
 371
 372 static struct sw_flow *masked_flow_lookup(struct flow_table *table,
 373                                           const struct sw_flow_key *unmasked,
 374                                           struct sw_flow_mask *mask)
 375 {
 376         struct sw_flow *flow;
 377         struct hlist_head *head;
 378         int key_start = mask->range.start;
 379         int key_end = mask->range.end;
 380         u32 hash;
 381         struct sw_flow_key masked_key;
 382
 383         ovs_flow_mask_key(&masked_key, unmasked, mask);
 384         hash = flow_hash(&masked_key, key_start, key_end);
 385         head = find_bucket(table, hash);
 386         hlist_for_each_entry_rcu(flow, head, hash_node[table->node_ver]) {
 387                 if (flow->mask == mask &&
 388                     flow_cmp_masked_key(flow, &masked_key,
 389                                           key_start, key_end))
 390                         return flow;
 391         }
 392         return NULL;
 393 }
 394
 395 struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl,
 396                                     const struct sw_flow_key *key)
 397 {
 398         struct sw_flow *flow = NULL;
 399         struct sw_flow_mask *mask;
 400
 401         list_for_each_entry_rcu(mask, tbl->mask_list, list) {
 402                 flow = masked_flow_lookup(tbl, key, mask);
 403                 if (flow)  /* Found */
 404                         break;
 405         }
 406
 407         return flow;
 408 }
 409
 410 void ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow)
 411 {
 412         flow->hash = flow_hash(&flow->key, flow->mask->range.start,
 413                         flow->mask->range.end);
 414         __tbl_insert(table, flow);
 415 }
 416
 417 void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
 418 {
 419         BUG_ON(table->count == 0);
 420         hlist_del_rcu(&flow->hash_node[table->node_ver]);
 421         table->count--;
 422 }
 423
 424 struct sw_flow_mask *ovs_sw_flow_mask_alloc(void)
 425 {
 426         struct sw_flow_mask *mask;
 427
 428         mask = kmalloc(sizeof(*mask), GFP_KERNEL);
 429         if (mask)
 430                 mask->ref_count = 0;
 431
 432         return mask;
 433 }
 434
 435 void ovs_sw_flow_mask_add_ref(struct sw_flow_mask *mask)
 436 {
 437         mask->ref_count++;
 438 }
 439
 440 static void rcu_free_sw_flow_mask_cb(struct rcu_head *rcu)
 441 {
 442         struct sw_flow_mask *mask = container_of(rcu, struct sw_flow_mask, rcu);
 443
 444         kfree(mask);
 445 }
 446
 447 void ovs_sw_flow_mask_del_ref(struct sw_flow_mask *mask, bool deferred)
 448 {
 449         if (!mask)
 450                 return;
 451
 452         BUG_ON(!mask->ref_count);
 453         mask->ref_count--;
 454
 455         if (!mask->ref_count) {
 456                 list_del_rcu(&mask->list);
 457                 if (deferred)
 458                         call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
 459                 else
 460                         kfree(mask);
 461         }
 462 }
 463
 464 static bool mask_equal(const struct sw_flow_mask *a,
 465                        const struct sw_flow_mask *b)
 466 {
 467         u8 *a_ = (u8 *)&a->key + a->range.start;
 468         u8 *b_ = (u8 *)&b->key + b->range.start;
 469
 470         return  (a->range.end == b->range.end)
 471                 && (a->range.start == b->range.start)
 472                 && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0);
 473 }
 474
 475 struct sw_flow_mask *ovs_sw_flow_mask_find(const struct flow_table *tbl,
 476                                            const struct sw_flow_mask *mask)
 477 {
 478         struct list_head *ml;
 479
 480         list_for_each(ml, tbl->mask_list) {
 481                 struct sw_flow_mask *m;
 482                 m = container_of(ml, struct sw_flow_mask, list);
 483                 if (mask_equal(mask, m))
 484                         return m;
 485         }
 486
 487         return NULL;
 488 }
 489
 490 /**
 491  * add a new mask into the mask list.
 492  * The caller needs to make sure that 'mask' is not the same
 493  * as any masks that are already on the list.
 494  */
 495 void ovs_sw_flow_mask_insert(struct flow_table *tbl, struct sw_flow_mask *mask)
 496 {
 497         list_add_rcu(&mask->list, tbl->mask_list);
 498 }
 499
 500 /* Initializes the flow module.
 501  * Returns zero if successful or a negative error code. */
 502 int ovs_flow_init(void)
 503 {
 504         BUILD_BUG_ON(__alignof__(struct sw_flow_key) % __alignof__(long));
 505         BUILD_BUG_ON(sizeof(struct sw_flow_key) % sizeof(long));
 506
 507         flow_cache = kmem_cache_create("sw_flow", sizeof(struct sw_flow), 0,
 508                                         0, NULL);
 509         if (flow_cache == NULL)
 510                 return -ENOMEM;
 511
 512         return 0;
 513 }
 514
 515 /* Uninitializes the flow module. */
 516 void ovs_flow_exit(void)
 517 {
 518         kmem_cache_destroy(flow_cache);
 519 }