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 #define TBL_MIN_BUCKETS         1024
  50 #define MASK_ARRAY_SIZE_MIN     16
  51 #define REHASH_INTERVAL         (10 * 60 * HZ)
  52
  53 #define MC_HASH_SHIFT           8
  54 #define MC_HASH_ENTRIES         (1u << MC_HASH_SHIFT)
  55 #define MC_HASH_SEGS            ((sizeof(uint32_t) * 8) / MC_HASH_SHIFT)
  56
  57 static struct kmem_cache *flow_cache;
  58 struct kmem_cache *flow_stats_cache __read_mostly;
  59
  60 static u16 range_n_bytes(const struct sw_flow_key_range *range)
  61 {
  62         return range->end - range->start;
  63 }
  64
  65 void ovs_flow_mask_key(struct sw_flow_key *dst, const struct sw_flow_key *src,
  66                        const struct sw_flow_mask *mask)
  67 {
  68         const long *m = (const long *)((const u8 *)&mask->key +
  69                                 mask->range.start);
  70         const long *s = (const long *)((const u8 *)src +
  71                                 mask->range.start);
  72         long *d = (long *)((u8 *)dst + mask->range.start);
  73         int i;
  74
  75         /* The memory outside of the 'mask->range' are not set since
  76          * further operations on 'dst' only uses contents within
  77          * 'mask->range'.
  78          */
  79         for (i = 0; i < range_n_bytes(&mask->range); i += sizeof(long))
  80                 *d++ = *s++ & *m++;
  81 }
  82
  83 struct sw_flow *ovs_flow_alloc(void)
  84 {
  85         struct sw_flow *flow;
  86         struct flow_stats *stats;
  87         int node;
  88
  89         flow = kmem_cache_alloc(flow_cache, GFP_KERNEL);
  90         if (!flow)
  91                 return ERR_PTR(-ENOMEM);
  92
  93         flow->sf_acts = NULL;
  94         flow->mask = NULL;
  95         flow->id.ufid_len = 0;
  96         flow->id.unmasked_key = NULL;
  97         flow->stats_last_writer = NUMA_NO_NODE;
  98
  99         /* Initialize the default stat node. */
 100         stats = kmem_cache_alloc_node(flow_stats_cache,
 101                                       GFP_KERNEL | __GFP_ZERO, 0);
 102         if (!stats)
 103                 goto err;
 104
 105         spin_lock_init(&stats->lock);
 106
 107         RCU_INIT_POINTER(flow->stats[0], stats);
 108
 109         for_each_node(node)
 110                 if (node != 0)
 111                         RCU_INIT_POINTER(flow->stats[node], NULL);
 112
 113         return flow;
 114 err:
 115         kmem_cache_free(flow_cache, flow);
 116         return ERR_PTR(-ENOMEM);
 117 }
 118
 119 int ovs_flow_tbl_count(const struct flow_table *table)
 120 {
 121         return table->count;
 122 }
 123
 124 static struct flex_array *alloc_buckets(unsigned int n_buckets)
 125 {
 126         struct flex_array *buckets;
 127         int i, err;
 128
 129         buckets = flex_array_alloc(sizeof(struct hlist_head),
 130                                    n_buckets, GFP_KERNEL);
 131         if (!buckets)
 132                 return NULL;
 133
 134         err = flex_array_prealloc(buckets, 0, n_buckets, GFP_KERNEL);
 135         if (err) {
 136                 flex_array_free(buckets);
 137                 return NULL;
 138         }
 139
 140         for (i = 0; i < n_buckets; i++)
 141                 INIT_HLIST_HEAD((struct hlist_head *)
 142                                         flex_array_get(buckets, i));
 143
 144         return buckets;
 145 }
 146
 147 static void flow_free(struct sw_flow *flow)
 148 {
 149         int node;
 150
 151         if (ovs_identifier_is_key(&flow->id))
 152                 kfree(flow->id.unmasked_key);
 153         kfree(rcu_dereference_raw(flow->sf_acts));
 154         for_each_node(node)
 155                 if (flow->stats[node])
 156                         kmem_cache_free(flow_stats_cache,
 157                                         rcu_dereference_raw(flow->stats[node]));
 158         kmem_cache_free(flow_cache, flow);
 159 }
 160
 161 static void rcu_free_flow_callback(struct rcu_head *rcu)
 162 {
 163         struct sw_flow *flow = container_of(rcu, struct sw_flow, rcu);
 164
 165         flow_free(flow);
 166 }
 167
 168 static void rcu_free_sw_flow_mask_cb(struct rcu_head *rcu)
 169 {
 170         struct sw_flow_mask *mask = container_of(rcu, struct sw_flow_mask, rcu);
 171
 172         kfree(mask);
 173 }
 174
 175 void ovs_flow_free(struct sw_flow *flow, bool deferred)
 176 {
 177         if (!flow)
 178                 return;
 179
 180         if (deferred)
 181                 call_rcu(&flow->rcu, rcu_free_flow_callback);
 182         else
 183                 flow_free(flow);
 184 }
 185
 186 static void free_buckets(struct flex_array *buckets)
 187 {
 188         flex_array_free(buckets);
 189 }
 190
 191
 192 static void __table_instance_destroy(struct table_instance *ti)
 193 {
 194         free_buckets(ti->buckets);
 195         kfree(ti);
 196 }
 197
 198 static struct table_instance *table_instance_alloc(int new_size)
 199 {
 200         struct table_instance *ti = kmalloc(sizeof(*ti), GFP_KERNEL);
 201
 202         if (!ti)
 203                 return NULL;
 204
 205         ti->buckets = alloc_buckets(new_size);
 206
 207         if (!ti->buckets) {
 208                 kfree(ti);
 209                 return NULL;
 210         }
 211         ti->n_buckets = new_size;
 212         ti->node_ver = 0;
 213         ti->keep_flows = false;
 214         get_random_bytes(&ti->hash_seed, sizeof(u32));
 215
 216         return ti;
 217 }
 218
 219 static void mask_array_rcu_cb(struct rcu_head *rcu)
 220 {
 221         struct mask_array *ma = container_of(rcu, struct mask_array, rcu);
 222
 223         kfree(ma);
 224 }
 225
 226 static struct mask_array *tbl_mask_array_alloc(int size)
 227 {
 228         struct mask_array *new;
 229
 230         size = max(MASK_ARRAY_SIZE_MIN, size);
 231         new = kzalloc(sizeof(struct mask_array) +
 232                       sizeof(struct sw_flow_mask *) * size, GFP_KERNEL);
 233         if (!new)
 234                 return NULL;
 235
 236         new->count = 0;
 237         new->max = size;
 238
 239         return new;
 240 }
 241
 242 static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
 243 {
 244         struct mask_array *old;
 245         struct mask_array *new;
 246
 247         new = tbl_mask_array_alloc(size);
 248         if (!new)
 249                 return -ENOMEM;
 250
 251         old = ovsl_dereference(tbl->mask_array);
 252         if (old) {
 253                 int i, count = 0;
 254
 255                 for (i = 0; i < old->max; i++) {
 256                         if (ovsl_dereference(old->masks[i]))
 257                                 new->masks[count++] = old->masks[i];
 258                 }
 259
 260                 new->count = count;
 261         }
 262         rcu_assign_pointer(tbl->mask_array, new);
 263
 264         if (old)
 265                 call_rcu(&old->rcu, mask_array_rcu_cb);
 266
 267         return 0;
 268 }
 269
 270 int ovs_flow_tbl_init(struct flow_table *table)
 271 {
 272         struct table_instance *ti, *ufid_ti;
 273         struct mask_array *ma;
 274
 275         table->mask_cache = __alloc_percpu(sizeof(struct mask_cache_entry) *
 276                                           MC_HASH_ENTRIES, __alignof__(struct mask_cache_entry));
 277         if (!table->mask_cache)
 278                 return -ENOMEM;
 279
 280         ma = tbl_mask_array_alloc(MASK_ARRAY_SIZE_MIN);
 281         if (!ma)
 282                 goto free_mask_cache;
 283
 284         ti = table_instance_alloc(TBL_MIN_BUCKETS);
 285         if (!ti)
 286                 goto free_mask_array;
 287
 288         ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS);
 289         if (!ufid_ti)
 290                 goto free_ti;
 291
 292         rcu_assign_pointer(table->ti, ti);
 293         rcu_assign_pointer(table->ufid_ti, ufid_ti);
 294         rcu_assign_pointer(table->mask_array, ma);
 295         table->last_rehash = jiffies;
 296         table->count = 0;
 297         table->ufid_count = 0;
 298         return 0;
 299
 300 free_ti:
 301         __table_instance_destroy(ti);
 302 free_mask_array:
 303         kfree(ma);
 304 free_mask_cache:
 305         free_percpu(table->mask_cache);
 306         return -ENOMEM;
 307 }
 308
 309 static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu)
 310 {
 311         struct table_instance *ti = container_of(rcu, struct table_instance, rcu);
 312
 313         __table_instance_destroy(ti);
 314 }
 315
 316 static void table_instance_destroy(struct table_instance *ti,
 317                                    struct table_instance *ufid_ti,
 318                                    bool deferred)
 319 {
 320         int i;
 321
 322         if (!ti)
 323                 return;
 324
 325         BUG_ON(!ufid_ti);
 326         if (ti->keep_flows)
 327                 goto skip_flows;
 328
 329         for (i = 0; i < ti->n_buckets; i++) {
 330                 struct sw_flow *flow;
 331                 struct hlist_head *head = flex_array_get(ti->buckets, i);
 332                 struct hlist_node *n;
 333                 int ver = ti->node_ver;
 334                 int ufid_ver = ufid_ti->node_ver;
 335
 336                 hlist_for_each_entry_safe(flow, n, head, flow_table.node[ver]) {
 337                         hlist_del_rcu(&flow->flow_table.node[ver]);
 338                         if (ovs_identifier_is_ufid(&flow->id))
 339                                 hlist_del_rcu(&flow->ufid_table.node[ufid_ver]);
 340                         ovs_flow_free(flow, deferred);
 341                 }
 342         }
 343
 344 skip_flows:
 345         if (deferred) {
 346                 call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb);
 347                 call_rcu(&ufid_ti->rcu, flow_tbl_destroy_rcu_cb);
 348         } else {
 349                 __table_instance_destroy(ti);
 350                 __table_instance_destroy(ufid_ti);
 351         }
 352 }
 353
 354 /* No need for locking this function is called from RCU callback or
 355  * error path.
 356  */
 357 void ovs_flow_tbl_destroy(struct flow_table *table)
 358 {
 359         struct table_instance *ti = rcu_dereference_raw(table->ti);
 360         struct table_instance *ufid_ti = rcu_dereference_raw(table->ufid_ti);
 361
 362         free_percpu(table->mask_cache);
 363         kfree(rcu_dereference_raw(table->mask_array));
 364         table_instance_destroy(ti, ufid_ti, false);
 365 }
 366
 367 struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
 368                                        u32 *bucket, u32 *last)
 369 {
 370         struct sw_flow *flow;
 371         struct hlist_head *head;
 372         int ver;
 373         int i;
 374
 375         ver = ti->node_ver;
 376         while (*bucket < ti->n_buckets) {
 377                 i = 0;
 378                 head = flex_array_get(ti->buckets, *bucket);
 379                 hlist_for_each_entry_rcu(flow, head, flow_table.node[ver]) {
 380                         if (i < *last) {
 381                                 i++;
 382                                 continue;
 383                         }
 384                         *last = i + 1;
 385                         return flow;
 386                 }
 387                 (*bucket)++;
 388                 *last = 0;
 389         }
 390
 391         return NULL;
 392 }
 393
 394 static struct hlist_head *find_bucket(struct table_instance *ti, u32 hash)
 395 {
 396         hash = jhash_1word(hash, ti->hash_seed);
 397         return flex_array_get(ti->buckets,
 398                                 (hash & (ti->n_buckets - 1)));
 399 }
 400
 401 static void table_instance_insert(struct table_instance *ti,
 402                                   struct sw_flow *flow)
 403 {
 404         struct hlist_head *head;
 405
 406         head = find_bucket(ti, flow->flow_table.hash);
 407         hlist_add_head_rcu(&flow->flow_table.node[ti->node_ver], head);
 408 }
 409
 410 static void ufid_table_instance_insert(struct table_instance *ti,
 411                                        struct sw_flow *flow)
 412 {
 413         struct hlist_head *head;
 414
 415         head = find_bucket(ti, flow->ufid_table.hash);
 416         hlist_add_head_rcu(&flow->ufid_table.node[ti->node_ver], head);
 417 }
 418
 419 static void flow_table_copy_flows(struct table_instance *old,
 420                                   struct table_instance *new, bool ufid)
 421 {
 422         int old_ver;
 423         int i;
 424
 425         old_ver = old->node_ver;
 426         new->node_ver = !old_ver;
 427
 428         /* Insert in new table. */
 429         for (i = 0; i < old->n_buckets; i++) {
 430                 struct sw_flow *flow;
 431                 struct hlist_head *head;
 432
 433                 head = flex_array_get(old->buckets, i);
 434
 435                 if (ufid)
 436                         hlist_for_each_entry(flow, head,
 437                                              ufid_table.node[old_ver])
 438                                 ufid_table_instance_insert(new, flow);
 439                 else
 440                         hlist_for_each_entry(flow, head,
 441                                              flow_table.node[old_ver])
 442                                 table_instance_insert(new, flow);
 443         }
 444
 445         old->keep_flows = true;
 446 }
 447
 448 static struct table_instance *table_instance_rehash(struct table_instance *ti,
 449                                                     int n_buckets, bool ufid)
 450 {
 451         struct table_instance *new_ti;
 452
 453         new_ti = table_instance_alloc(n_buckets);
 454         if (!new_ti)
 455                 return NULL;
 456
 457         flow_table_copy_flows(ti, new_ti, ufid);
 458
 459         return new_ti;
 460 }
 461
 462 int ovs_flow_tbl_flush(struct flow_table *flow_table)
 463 {
 464         struct table_instance *old_ti, *new_ti;
 465         struct table_instance *old_ufid_ti, *new_ufid_ti;
 466
 467         new_ti = table_instance_alloc(TBL_MIN_BUCKETS);
 468         if (!new_ti)
 469                 return -ENOMEM;
 470         new_ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS);
 471         if (!new_ufid_ti)
 472                 goto err_free_ti;
 473
 474         old_ti = ovsl_dereference(flow_table->ti);
 475         old_ufid_ti = ovsl_dereference(flow_table->ufid_ti);
 476
 477         rcu_assign_pointer(flow_table->ti, new_ti);
 478         rcu_assign_pointer(flow_table->ufid_ti, new_ufid_ti);
 479         flow_table->last_rehash = jiffies;
 480         flow_table->count = 0;
 481         flow_table->ufid_count = 0;
 482
 483         table_instance_destroy(old_ti, old_ufid_ti, true);
 484         return 0;
 485
 486 err_free_ti:
 487         __table_instance_destroy(new_ti);
 488         return -ENOMEM;
 489 }
 490
 491 static u32 flow_hash(const struct sw_flow_key *key,
 492                      const struct sw_flow_key_range *range)
 493 {
 494         int key_start = range->start;
 495         int key_end = range->end;
 496         const u32 *hash_key = (const u32 *)((const u8 *)key + key_start);
 497         int hash_u32s = (key_end - key_start) >> 2;
 498
 499         /* Make sure number of hash bytes are multiple of u32. */
 500         BUILD_BUG_ON(sizeof(long) % sizeof(u32));
 501
 502         return jhash2(hash_key, hash_u32s, 0);
 503 }
 504
 505 static int flow_key_start(const struct sw_flow_key *key)
 506 {
 507         if (key->tun_key.ipv4_dst)
 508                 return 0;
 509         else
 510                 return rounddown(offsetof(struct sw_flow_key, phy),
 511                                           sizeof(long));
 512 }
 513
 514 static bool cmp_key(const struct sw_flow_key *key1,
 515                     const struct sw_flow_key *key2,
 516                     int key_start, int key_end)
 517 {
 518         const long *cp1 = (const long *)((const u8 *)key1 + key_start);
 519         const long *cp2 = (const long *)((const u8 *)key2 + key_start);
 520         long diffs = 0;
 521         int i;
 522
 523         for (i = key_start; i < key_end;  i += sizeof(long))
 524                 diffs |= *cp1++ ^ *cp2++;
 525
 526         return diffs == 0;
 527 }
 528
 529 static bool flow_cmp_masked_key(const struct sw_flow *flow,
 530                                 const struct sw_flow_key *key,
 531                                 const struct sw_flow_key_range *range)
 532 {
 533         return cmp_key(&flow->key, key, range->start, range->end);
 534 }
 535
 536 bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow,
 537                                const struct sw_flow_match *match)
 538 {
 539         struct sw_flow_key *key = match->key;
 540         int key_start = flow_key_start(key);
 541         int key_end = match->range.end;
 542
 543         BUG_ON(ovs_identifier_is_ufid(&flow->id));
 544         return cmp_key(flow->id.unmasked_key, key, key_start, key_end);
 545 }
 546
 547 static struct sw_flow *masked_flow_lookup(struct table_instance *ti,
 548                                           const struct sw_flow_key *unmasked,
 549                                           const struct sw_flow_mask *mask,
 550                                           u32 *n_mask_hit)
 551 {
 552         struct sw_flow *flow;
 553         struct hlist_head *head;
 554         u32 hash;
 555         struct sw_flow_key masked_key;
 556
 557         ovs_flow_mask_key(&masked_key, unmasked, mask);
 558         hash = flow_hash(&masked_key, &mask->range);
 559         head = find_bucket(ti, hash);
 560         (*n_mask_hit)++;
 561         hlist_for_each_entry_rcu(flow, head, flow_table.node[ti->node_ver]) {
 562                 if (flow->mask == mask && flow->flow_table.hash == hash &&
 563                     flow_cmp_masked_key(flow, &masked_key, &mask->range))
 564                         return flow;
 565         }
 566         return NULL;
 567 }
 568
 569 /* Flow lookup does full lookup on flow table. It starts with
 570  * mask from index passed in *index.
 571  */
 572 static struct sw_flow *flow_lookup(struct flow_table *tbl,
 573                                    struct table_instance *ti,
 574                                    const struct mask_array *ma,
 575                                    const struct sw_flow_key *key,
 576                                    u32 *n_mask_hit,
 577                                    u32 *index)
 578 {
 579         struct sw_flow_mask *mask;
 580         struct sw_flow *flow;
 581         int i;
 582
 583         if (*index < ma->max) {
 584                 mask = rcu_dereference_ovsl(ma->masks[*index]);
 585                 if (mask) {
 586                         flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
 587                         if (flow)
 588                                 return flow;
 589                 }
 590         }
 591
 592         for (i = 0; i < ma->max; i++)  {
 593
 594                 if (i == *index)
 595                         continue;
 596
 597                 mask = rcu_dereference_ovsl(ma->masks[i]);
 598                 if (!mask)
 599                         continue;
 600
 601                 flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
 602                 if (flow) { /* Found */
 603                         *index = i;
 604                         return flow;
 605                 }
 606         }
 607
 608         return NULL;
 609 }
 610
 611 /*
 612  * mask_cache maps flow to probable mask. This cache is not tightly
 613  * coupled cache, It means updates to  mask list can result in inconsistent
 614  * cache entry in mask cache.
 615  * This is per cpu cache and is divided in MC_HASH_SEGS segments.
 616  * In case of a hash collision the entry is hashed in next segment.
 617  */
 618 struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
 619                                           const struct sw_flow_key *key,
 620                                           u32 skb_hash,
 621                                           u32 *n_mask_hit)
 622 {
 623         struct mask_array *ma = rcu_dereference(tbl->mask_array);
 624         struct table_instance *ti = rcu_dereference(tbl->ti);
 625         struct mask_cache_entry *entries, *ce;
 626         struct sw_flow *flow;
 627         u32 hash;
 628         int seg;
 629
 630         *n_mask_hit = 0;
 631         if (unlikely(!skb_hash)) {
 632                 u32 mask_index = 0;
 633
 634                 return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
 635         }
 636
 637         /* Pre and post recirulation flows usually have the same skb_hash
 638          * value. To avoid hash collisions, rehash the 'skb_hash' with
 639          * 'recirc_id'.  */
 640         if (key->recirc_id)
 641                 skb_hash = jhash_1word(skb_hash, key->recirc_id);
 642
 643         ce = NULL;
 644         hash = skb_hash;
 645         entries = this_cpu_ptr(tbl->mask_cache);
 646
 647         /* Find the cache entry 'ce' to operate on. */
 648         for (seg = 0; seg < MC_HASH_SEGS; seg++) {
 649                 int index = hash & (MC_HASH_ENTRIES - 1);
 650                 struct mask_cache_entry *e;
 651
 652                 e = &entries[index];
 653                 if (e->skb_hash == skb_hash) {
 654                         flow = flow_lookup(tbl, ti, ma, key, n_mask_hit,
 655                                            &e->mask_index);
 656                         if (!flow)
 657                                 e->skb_hash = 0;
 658                         return flow;
 659                 }
 660
 661                 if (!ce || e->skb_hash < ce->skb_hash)
 662                         ce = e;  /* A better replacement cache candidate. */
 663
 664                 hash >>= MC_HASH_SHIFT;
 665         }
 666
 667         /* Cache miss, do full lookup. */
 668         flow = flow_lookup(tbl, ti, ma, key, n_mask_hit, &ce->mask_index);
 669         if (flow)
 670                 ce->skb_hash = skb_hash;
 671
 672         return flow;
 673 }
 674
 675 struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl,
 676                                     const struct sw_flow_key *key)
 677 {
 678         struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
 679         struct mask_array *ma = rcu_dereference_ovsl(tbl->mask_array);
 680         u32 __always_unused n_mask_hit;
 681         u32 index = 0;
 682
 683         return flow_lookup(tbl, ti, ma, key, &n_mask_hit, &index);
 684 }
 685
 686 struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl,
 687                                           const struct sw_flow_match *match)
 688 {
 689         struct mask_array *ma = ovsl_dereference(tbl->mask_array);
 690         int i;
 691
 692         /* Always called under ovs-mutex. */
 693         for (i = 0; i < ma->max; i++) {
 694                 struct table_instance *ti = ovsl_dereference(tbl->ti);
 695                 u32 __always_unused n_mask_hit;
 696                 struct sw_flow_mask *mask;
 697                 struct sw_flow *flow;
 698
 699                 mask = ovsl_dereference(ma->masks[i]);
 700                 if (!mask)
 701                         continue;
 702                 flow = masked_flow_lookup(ti, match->key, mask, &n_mask_hit);
 703                 if (flow && ovs_identifier_is_key(&flow->id) &&
 704                     ovs_flow_cmp_unmasked_key(flow, match))
 705                         return flow;
 706         }
 707         return NULL;
 708 }
 709
 710 static u32 ufid_hash(const struct sw_flow_id *sfid)
 711 {
 712         return jhash(sfid->ufid, sfid->ufid_len, 0);
 713 }
 714
 715 static bool ovs_flow_cmp_ufid(const struct sw_flow *flow,
 716                               const struct sw_flow_id *sfid)
 717 {
 718         if (flow->id.ufid_len != sfid->ufid_len)
 719                 return false;
 720
 721         return !memcmp(flow->id.ufid, sfid->ufid, sfid->ufid_len);
 722 }
 723
 724 bool ovs_flow_cmp(const struct sw_flow *flow, const struct sw_flow_match *match)
 725 {
 726         if (ovs_identifier_is_ufid(&flow->id))
 727                 return flow_cmp_masked_key(flow, match->key, &match->range);
 728
 729         return ovs_flow_cmp_unmasked_key(flow, match);
 730 }
 731
 732 struct sw_flow *ovs_flow_tbl_lookup_ufid(struct flow_table *tbl,
 733                                          const struct sw_flow_id *ufid)
 734 {
 735         struct table_instance *ti = rcu_dereference_ovsl(tbl->ufid_ti);
 736         struct sw_flow *flow;
 737         struct hlist_head *head;
 738         u32 hash;
 739
 740         hash = ufid_hash(ufid);
 741         head = find_bucket(ti, hash);
 742         hlist_for_each_entry_rcu(flow, head, ufid_table.node[ti->node_ver]) {
 743                 if (flow->ufid_table.hash == hash &&
 744                     ovs_flow_cmp_ufid(flow, ufid))
 745                         return flow;
 746         }
 747         return NULL;
 748 }
 749
 750 int ovs_flow_tbl_num_masks(const struct flow_table *table)
 751 {
 752         struct mask_array *ma;
 753
 754         ma = rcu_dereference_ovsl(table->mask_array);
 755         return ma->count;
 756 }
 757
 758 static struct table_instance *table_instance_expand(struct table_instance *ti,
 759                                                     bool ufid)
 760 {
 761         return table_instance_rehash(ti, ti->n_buckets * 2, ufid);
 762 }
 763
 764 static void tbl_mask_array_delete_mask(struct mask_array *ma,
 765                                        struct sw_flow_mask *mask)
 766 {
 767         int i;
 768
 769         /* Remove the deleted mask pointers from the array */
 770         for (i = 0; i < ma->max; i++) {
 771                 if (mask == ovsl_dereference(ma->masks[i])) {
 772                         RCU_INIT_POINTER(ma->masks[i], NULL);
 773                         ma->count--;
 774                         call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
 775                         return;
 776                 }
 777         }
 778         BUG();
 779 }
 780
 781 /* Remove 'mask' from the mask list, if it is not needed any more. */
 782 static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
 783 {
 784         if (mask) {
 785                 /* ovs-lock is required to protect mask-refcount and
 786                  * mask list.
 787                  */
 788                 ASSERT_OVSL();
 789                 BUG_ON(!mask->ref_count);
 790                 mask->ref_count--;
 791
 792                 if (!mask->ref_count) {
 793                         struct mask_array *ma;
 794
 795                         ma = ovsl_dereference(tbl->mask_array);
 796                         tbl_mask_array_delete_mask(ma, mask);
 797
 798                         /* Shrink the mask array if necessary. */
 799                         if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) &&
 800                             ma->count <= (ma->max / 3))
 801                                 tbl_mask_array_realloc(tbl, ma->max / 2);
 802
 803                 }
 804         }
 805 }
 806
 807 /* Must be called with OVS mutex held. */
 808 void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
 809 {
 810         struct table_instance *ti = ovsl_dereference(table->ti);
 811         struct table_instance *ufid_ti = ovsl_dereference(table->ufid_ti);
 812
 813         BUG_ON(table->count == 0);
 814         hlist_del_rcu(&flow->flow_table.node[ti->node_ver]);
 815         table->count--;
 816         if (ovs_identifier_is_ufid(&flow->id)) {
 817                 hlist_del_rcu(&flow->ufid_table.node[ufid_ti->node_ver]);
 818                 table->ufid_count--;
 819         }
 820
 821         /* RCU delete the mask. 'flow->mask' is not NULLed, as it should be
 822          * accessible as long as the RCU read lock is held.
 823          */
 824         flow_mask_remove(table, flow->mask);
 825 }
 826
 827 static struct sw_flow_mask *mask_alloc(void)
 828 {
 829         struct sw_flow_mask *mask;
 830
 831         mask = kmalloc(sizeof(*mask), GFP_KERNEL);
 832         if (mask)
 833                 mask->ref_count = 1;
 834
 835         return mask;
 836 }
 837
 838 static bool mask_equal(const struct sw_flow_mask *a,
 839                        const struct sw_flow_mask *b)
 840 {
 841         const u8 *a_ = (const u8 *)&a->key + a->range.start;
 842         const u8 *b_ = (const u8 *)&b->key + b->range.start;
 843
 844         return  (a->range.end == b->range.end)
 845                 && (a->range.start == b->range.start)
 846                 && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0);
 847 }
 848
 849 static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl,
 850                                            const struct sw_flow_mask *mask)
 851 {
 852         struct mask_array *ma;
 853         int i;
 854
 855         ma = ovsl_dereference(tbl->mask_array);
 856         for (i = 0; i < ma->max; i++) {
 857                 struct sw_flow_mask *t;
 858
 859                 t = ovsl_dereference(ma->masks[i]);
 860                 if (t && mask_equal(mask, t))
 861                         return t;
 862         }
 863
 864         return NULL;
 865 }
 866
 867 /* Add 'mask' into the mask list, if it is not already there. */
 868 static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
 869                             const struct sw_flow_mask *new)
 870 {
 871         struct sw_flow_mask *mask;
 872
 873         mask = flow_mask_find(tbl, new);
 874         if (!mask) {
 875                 struct mask_array *ma;
 876                 int i;
 877
 878                 /* Allocate a new mask if none exsits. */
 879                 mask = mask_alloc();
 880                 if (!mask)
 881                         return -ENOMEM;
 882
 883                 mask->key = new->key;
 884                 mask->range = new->range;
 885
 886                 /* Add mask to mask-list. */
 887                 ma = ovsl_dereference(tbl->mask_array);
 888                 if (ma->count >= ma->max) {
 889                         int err;
 890
 891                         err = tbl_mask_array_realloc(tbl, ma->max +
 892                                                           MASK_ARRAY_SIZE_MIN);
 893                         if (err) {
 894                                 kfree(mask);
 895                                 return err;
 896                         }
 897                         ma = ovsl_dereference(tbl->mask_array);
 898                 }
 899
 900                 for (i = 0; i < ma->max; i++) {
 901                         struct sw_flow_mask *t;
 902
 903                         t = ovsl_dereference(ma->masks[i]);
 904                         if (!t) {
 905                                 rcu_assign_pointer(ma->masks[i], mask);
 906                                 ma->count++;
 907                                 break;
 908                         }
 909                 }
 910
 911         } else {
 912                 BUG_ON(!mask->ref_count);
 913                 mask->ref_count++;
 914         }
 915
 916         flow->mask = mask;
 917         return 0;
 918 }
 919
 920 /* Must be called with OVS mutex held. */
 921 static void flow_key_insert(struct flow_table *table, struct sw_flow *flow)
 922 {
 923         struct table_instance *new_ti = NULL;
 924         struct table_instance *ti;
 925
 926         flow->flow_table.hash = flow_hash(&flow->key, &flow->mask->range);
 927         ti = ovsl_dereference(table->ti);
 928         table_instance_insert(ti, flow);
 929         table->count++;
 930
 931         /* Expand table, if necessary, to make room. */
 932         if (table->count > ti->n_buckets)
 933                 new_ti = table_instance_expand(ti, false);
 934         else if (time_after(jiffies, table->last_rehash + REHASH_INTERVAL))
 935                 new_ti = table_instance_rehash(ti, ti->n_buckets, false);
 936
 937         if (new_ti) {
 938                 rcu_assign_pointer(table->ti, new_ti);
 939                 call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb);
 940                 table->last_rehash = jiffies;
 941         }
 942 }
 943
 944 /* Must be called with OVS mutex held. */
 945 static void flow_ufid_insert(struct flow_table *table, struct sw_flow *flow)
 946 {
 947         struct table_instance *ti;
 948
 949         flow->ufid_table.hash = ufid_hash(&flow->id);
 950         ti = ovsl_dereference(table->ufid_ti);
 951         ufid_table_instance_insert(ti, flow);
 952         table->ufid_count++;
 953
 954         /* Expand table, if necessary, to make room. */
 955         if (table->ufid_count > ti->n_buckets) {
 956                 struct table_instance *new_ti;
 957
 958                 new_ti = table_instance_expand(ti, true);
 959                 if (new_ti) {
 960                         rcu_assign_pointer(table->ufid_ti, new_ti);
 961                         call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb);
 962                 }
 963         }
 964 }
 965
 966 /* Must be called with OVS mutex held. */
 967 int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
 968                         const struct sw_flow_mask *mask)
 969 {
 970         int err;
 971
 972         err = flow_mask_insert(table, flow, mask);
 973         if (err)
 974                 return err;
 975         flow_key_insert(table, flow);
 976         if (ovs_identifier_is_ufid(&flow->id))
 977                 flow_ufid_insert(table, flow);
 978
 979         return 0;
 980 }
 981
 982 /* Initializes the flow module.
 983  * Returns zero if successful or a negative error code.
 984  */
 985 int ovs_flow_init(void)
 986 {
 987         BUILD_BUG_ON(__alignof__(struct sw_flow_key) % __alignof__(long));
 988         BUILD_BUG_ON(sizeof(struct sw_flow_key) % sizeof(long));
 989
 990         flow_cache = kmem_cache_create("sw_flow", sizeof(struct sw_flow)
 991                                        + (num_possible_nodes()
 992                                           * sizeof(struct flow_stats *)),
 993                                        0, 0, NULL);
 994         if (flow_cache == NULL)
 995                 return -ENOMEM;
 996
 997         flow_stats_cache
 998                 = kmem_cache_create("sw_flow_stats", sizeof(struct flow_stats),
 999                                     0, SLAB_HWCACHE_ALIGN, NULL);
1000         if (flow_stats_cache == NULL) {
1001                 kmem_cache_destroy(flow_cache);
1002                 flow_cache = NULL;
1003                 return -ENOMEM;
1004         }
1005
1006         return 0;
1007 }
1008
1009 /* Uninitializes the flow module. */
1010 void ovs_flow_exit(void)
1011 {
1012         kmem_cache_destroy(flow_stats_cache);
1013         kmem_cache_destroy(flow_cache);
1014 }