datapath/table.c

   1 #include "flow.h"
   2 #include "datapath.h"
   3
   4 #include <linux/gfp.h>
   5 #include <linux/jhash.h>
   6 #include <linux/slab.h>
   7 #include <linux/vmalloc.h>
   8 #include <linux/mm.h>
   9 #include <linux/highmem.h>
  10 #include <asm/pgtable.h>
  11
  12 static void free_table(struct sw_flow ***flows, unsigned int n_buckets,
  13                        int free_flows)
  14 {
  15         unsigned int i;
  16
  17         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  18                 struct sw_flow **l2 = flows[i];
  19                 if (free_flows) {
  20                         unsigned int j;
  21                         for (j = 0; j < DP_L1_SIZE; j++) {
  22                                 if (l2[j])
  23                                         flow_free(l2[j]);
  24                         }
  25                 }
  26                 free_page((unsigned long)l2);
  27         }
  28         kfree(flows);
  29 }
  30
  31 static struct sw_flow ***alloc_table(unsigned int n_buckets)
  32 {
  33         struct sw_flow ***flows;
  34         unsigned int i;
  35
  36         flows = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct sw_flow**),
  37                         GFP_KERNEL);
  38         if (!flows)
  39                 return NULL;
  40         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
  41                 flows[i] = (struct sw_flow **)get_zeroed_page(GFP_KERNEL);
  42                 if (!flows[i]) {
  43                         free_table(flows, i << DP_L1_BITS, 0);
  44                         return NULL;
  45                 }
  46         }
  47         return flows;
  48 }
  49
  50 struct dp_table *dp_table_create(unsigned int n_buckets)
  51 {
  52         struct dp_table *table;
  53
  54         table = kzalloc(sizeof *table, GFP_KERNEL);
  55         if (!table)
  56                 goto err;
  57
  58         table->n_buckets = n_buckets;
  59         table->flows[0] = alloc_table(n_buckets);
  60         if (!table[0].flows)
  61                 goto err_free_tables;
  62
  63         table->flows[1] = alloc_table(n_buckets);
  64         if (!table->flows[1])
  65                 goto err_free_flows0;
  66
  67         return table;
  68
  69 err_free_flows0:
  70         free_table(table->flows[0], table->n_buckets, 0);
  71 err_free_tables:
  72         kfree(table);
  73 err:
  74         return NULL;
  75 }
  76
  77 void dp_table_destroy(struct dp_table *table, int free_flows)
  78 {
  79         int i;
  80         for (i = 0; i < 2; i++)
  81                 free_table(table->flows[i], table->n_buckets, free_flows);
  82         kfree(table);
  83 }
  84
  85 static struct sw_flow **find_bucket(struct dp_table *table,
  86                                     struct sw_flow ***flows, u32 hash)
  87 {
  88         unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
  89         unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
  90         return &flows[l1][l2];
  91 }
  92
  93 static struct sw_flow *lookup_table(struct dp_table *table,
  94                                     struct sw_flow ***flows, u32 hash,
  95                                     const struct odp_flow_key *key)
  96 {
  97         struct sw_flow **bucket = find_bucket(table, flows, hash);
  98         struct sw_flow *flow = rcu_dereference(*bucket);
  99         if (flow && !memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
 100                 return flow;
 101         return NULL;
 102 }
 103
 104 static u32 flow_hash0(const struct odp_flow_key *key)
 105 {
 106         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0xaaaaaaaa);
 107 }
 108
 109 static u32 flow_hash1(const struct odp_flow_key *key)
 110 {
 111         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0x55555555);
 112 }
 113
 114 static void find_buckets(struct dp_table *table,
 115                          const struct odp_flow_key *key,
 116                          struct sw_flow **buckets[2])
 117 {
 118         buckets[0] = find_bucket(table, table->flows[0], flow_hash0(key));
 119         buckets[1] = find_bucket(table, table->flows[1], flow_hash1(key));
 120 }
 121
 122 struct sw_flow *dp_table_lookup(struct dp_table *table,
 123                                 const struct odp_flow_key *key)
 124 {
 125         struct sw_flow *flow;
 126         flow = lookup_table(table, table->flows[0], flow_hash0(key), key);
 127         if (!flow)
 128                 flow = lookup_table(table, table->flows[1],
 129                                     flow_hash1(key), key);
 130         return flow;
 131 }
 132
 133 int dp_table_foreach(struct dp_table *table,
 134                      int (*callback)(struct sw_flow *flow, void *aux),
 135                      void *aux)
 136 {
 137         unsigned int i, j, k;
 138         for (i = 0; i < 2; i++) {
 139                 for (j = 0; j < table->n_buckets >> DP_L1_BITS; j++) {
 140                         struct sw_flow **l2 = table->flows[i][j];
 141                         for (k = 0; k < DP_L1_SIZE; k++) {
 142                                 struct sw_flow *flow = rcu_dereference(l2[k]);
 143                                 if (flow) {
 144                                         int error = callback(flow, aux);
 145                                         if (error)
 146                                                 return error;
 147                                 }
 148                         }
 149                 }
 150         }
 151         return 0;
 152 }
 153
 154 static int insert_flow(struct sw_flow *flow, void *new_table_)
 155 {
 156         struct dp_table *new_table = new_table_;
 157         struct sw_flow **buckets[2];
 158         int i;
 159
 160         find_buckets(new_table, &flow->key, buckets);
 161         for (i = 0; i < 2; i++) {
 162                 if (!*buckets[i]) {
 163                         rcu_assign_pointer(*buckets[i], flow);
 164                         return 0;
 165                 }
 166         }
 167         WARN_ON_ONCE(1);
 168         return 0;
 169 }
 170
 171 static void dp_free_table_rcu(struct rcu_head *rcu)
 172 {
 173         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 174         dp_table_destroy(table, 0);
 175 }
 176
 177 int dp_table_expand(struct datapath *dp)
 178 {
 179         struct dp_table *old_table = rcu_dereference(dp->table);
 180         struct dp_table *new_table = dp_table_create(old_table->n_buckets * 2);
 181         if (!new_table)
 182                 return -ENOMEM;
 183         dp_table_foreach(old_table, insert_flow, new_table);
 184         rcu_assign_pointer(dp->table, new_table);
 185         call_rcu(&old_table->rcu, dp_free_table_rcu);
 186         return 0;
 187 }
 188
 189 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
 190 {
 191         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
 192         dp_table_destroy(table, 1);
 193 }
 194
 195 int dp_table_flush(struct datapath *dp)
 196 {
 197         struct dp_table *old_table = rcu_dereference(dp->table);
 198         struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
 199         if (!new_table)
 200                 return -ENOMEM;
 201         rcu_assign_pointer(dp->table, new_table);
 202         call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
 203         return 0;
 204 }
 205
 206 struct sw_flow **
 207 dp_table_lookup_for_insert(struct dp_table *table,
 208                            const struct odp_flow_key *target)
 209 {
 210         struct sw_flow **buckets[2];
 211         struct sw_flow **empty_bucket = NULL;
 212         int i;
 213
 214         find_buckets(table, target, buckets);
 215         for (i = 0; i < 2; i++) {
 216                 struct sw_flow *f = rcu_dereference(*buckets[i]);
 217                 if (f) {
 218                         if (!memcmp(&f->key, target, sizeof(struct odp_flow_key)))
 219                                 return buckets[i];
 220                 } else if (!empty_bucket)
 221                         empty_bucket = buckets[i];
 222         }
 223         return empty_bucket;
 224 }
 225
 226 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
 227 {
 228         struct sw_flow **buckets[2];
 229         int i;
 230
 231         find_buckets(table, &target->key, buckets);
 232         for (i = 0; i < 2; i++) {
 233                 struct sw_flow *flow = rcu_dereference(*buckets[i]);
 234                 if (flow == target) {
 235                         rcu_assign_pointer(*buckets[i], NULL);
 236                         return 0;
 237                 }
 238         }
 239         return -ENOENT;
 240 }