ofproto/ofproto-dpif-rid.c

   1 /*
   2  * Copyright (c) 2014, 2015 Nicira, Inc.
   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 "ofpbuf.h"
  20 #include "ofproto-dpif.h"
  21 #include "ofproto-dpif-rid.h"
  22 #include "ofproto-provider.h"
  23 #include "openvswitch/vlog.h"
  24
  25 VLOG_DEFINE_THIS_MODULE(ofproto_dpif_rid);
  26
  27 static struct ovs_mutex mutex;
  28
  29 static struct cmap id_map;
  30 static struct cmap metadata_map;
  31
  32 static struct ovs_list expiring OVS_GUARDED_BY(mutex);
  33 static struct ovs_list expired OVS_GUARDED_BY(mutex);
  34
  35 static uint32_t next_id OVS_GUARDED_BY(mutex); /* Possible next free id. */
  36
  37 #define RECIRC_POOL_STATIC_IDS 1024
  38
  39 void
  40 recirc_init(void)
  41 {
  42     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
  43
  44     if (ovsthread_once_start(&once)) {
  45         ovs_mutex_init(&mutex);
  46         ovs_mutex_lock(&mutex);
  47         next_id = 1; /* 0 is not a valid ID. */
  48         cmap_init(&id_map);
  49         cmap_init(&metadata_map);
  50         list_init(&expiring);
  51         list_init(&expired);
  52         ovs_mutex_unlock(&mutex);
  53
  54         ovsthread_once_done(&once);
  55     }
  56
  57 }
  58
  59 /* This should be called by the revalidator once at each round (every 500ms or
  60  * more). */
  61 void
  62 recirc_run(void)
  63 {
  64     static long long int last = 0;
  65     long long int now = time_msec();
  66
  67     /* Do maintenance at most 4 times / sec. */
  68     ovs_mutex_lock(&mutex);
  69     if (now - last > 250) {
  70         struct recirc_id_node *node, *next;
  71
  72         last = now;
  73
  74         /* Nodes in 'expiring' and 'expired' lists have the refcount of zero,
  75          * which means that while they can still be found (by id), no new
  76          * references can be taken on them.  We have removed the entry from the
  77          * 'metadata_map', at the time when refcount reached zero, causing any
  78          * new translations to allocate a new ID.  This allows the expiring
  79          * entry to be safely deleted while any sudden new use of the similar
  80          * recirculation will safely start using a new recirculation ID.  When
  81          * the refcount gets to zero, the node is also added to the 'expiring'
  82          * list.  At any time after that the nodes in the 'expiring' list can
  83          * be moved to the 'expired' list, from which they are deleted at least
  84          * 250ms afterwards. */
  85
  86         /* Delete the expired.  These have been lingering for at least 250 ms,
  87          * which should be enough for any ongoing recirculations to be
  88          * finished. */
  89         LIST_FOR_EACH_SAFE (node, next, exp_node, &expired) {
  90             list_remove(&node->exp_node);
  91             cmap_remove(&id_map, &node->id_node, node->id);
  92             ovsrcu_postpone(free, node);
  93         }
  94
  95         if (!list_is_empty(&expiring)) {
  96             /* 'expired' is now empty, move nodes in 'expiring' to it. */
  97             list_splice(&expired, list_front(&expiring), &expiring);
  98         }
  99     }
 100     ovs_mutex_unlock(&mutex);
 101 }
 102
 103 /* We use the id as the hash value, which works due to cmap internal rehashing.
 104  * We also only insert nodes with unique IDs, so all possible hash collisions
 105  * remain internal to the cmap. */
 106 static struct recirc_id_node *
 107 recirc_find__(uint32_t id)
 108     OVS_REQUIRES(mutex)
 109 {
 110     struct cmap_node *node = cmap_find_protected(&id_map, id);
 111
 112     return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
 113 }
 114
 115 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 116  * state, caller should copy the contents. */
 117 const struct recirc_id_node *
 118 recirc_id_node_find(uint32_t id)
 119 {
 120     const struct cmap_node *node = cmap_find(&id_map, id);
 121
 122     return node
 123         ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
 124         : NULL;
 125 }
 126
 127 static uint32_t
 128 recirc_metadata_hash(struct ofproto_dpif *ofproto, uint8_t table_id,
 129                      struct recirc_metadata *md, struct ofpbuf *stack,
 130                      uint32_t action_set_len, uint32_t ofpacts_len,
 131                      const struct ofpact *ofpacts)
 132 {
 133     uint32_t hash;
 134
 135     BUILD_ASSERT(OFPACT_ALIGNTO == sizeof(uint64_t));
 136
 137     hash = hash_pointer(ofproto, 0);
 138     hash = hash_int(table_id, hash);
 139     hash = hash_words64((const uint64_t *)md, sizeof *md / sizeof(uint64_t),
 140                         hash);
 141     if (stack && stack->size != 0) {
 142         hash = hash_words64((const uint64_t *)stack->data,
 143                             stack->size / sizeof(uint64_t), hash);
 144     }
 145     hash = hash_int(action_set_len, hash);
 146     if (ofpacts_len) {
 147         hash = hash_words64(ALIGNED_CAST(const uint64_t *, ofpacts),
 148                             OFPACT_ALIGN(ofpacts_len) / sizeof(uint64_t),
 149                             hash);
 150     }
 151     return hash;
 152 }
 153
 154 static bool
 155 recirc_metadata_equal(const struct recirc_id_node *node,
 156                       struct ofproto_dpif *ofproto, uint8_t table_id,
 157                       struct recirc_metadata *md, struct ofpbuf *stack,
 158                       uint32_t action_set_len, uint32_t ofpacts_len,
 159                       const struct ofpact *ofpacts)
 160 {
 161     return node->ofproto == ofproto
 162         && node->table_id == table_id
 163         && !memcmp(&node->metadata, md, sizeof *md)
 164         && ((!node->stack && (!stack || stack->size == 0))
 165             || (node->stack && stack && ofpbuf_equal(node->stack, stack)))
 166         && node->action_set_len == action_set_len
 167         && node->ofpacts_len == ofpacts_len
 168         && (ofpacts_len == 0 || !memcmp(node->ofpacts, ofpacts, ofpacts_len));
 169 }
 170
 171 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 172  * state, caller should take a reference. */
 173 static struct recirc_id_node *
 174 recirc_find_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
 175                   struct recirc_metadata *md, struct ofpbuf *stack,
 176                   uint32_t action_set_len, uint32_t ofpacts_len,
 177                   const struct ofpact *ofpacts, uint32_t hash)
 178 {
 179     struct recirc_id_node *node;
 180
 181     CMAP_FOR_EACH_WITH_HASH(node, metadata_node, hash, &metadata_map) {
 182         if (recirc_metadata_equal(node, ofproto, table_id, md, stack,
 183                                   action_set_len, ofpacts_len, ofpacts)) {
 184             return node;
 185         }
 186     }
 187     return NULL;
 188 }
 189
 190 static struct recirc_id_node *
 191 recirc_ref_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
 192                  struct recirc_metadata *md, struct ofpbuf *stack,
 193                  uint32_t action_set_len, uint32_t ofpacts_len,
 194                  const struct ofpact *ofpacts, uint32_t hash)
 195 {
 196     struct recirc_id_node *node;
 197
 198     do {
 199         node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
 200                                  ofpacts_len, ofpacts, hash);
 201
 202         /* Try again if the node was released before we get the reference. */
 203     } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
 204
 205     return node;
 206 }
 207
 208 /* Allocate a unique recirculation id for the given set of flow metadata.
 209  * The ID space is 2^^32, so there should never be a situation in which all
 210  * the IDs are used up.  We loop until we find a free one.
 211  * hash is recomputed if it is passed in as 0. */
 212 static struct recirc_id_node *
 213 recirc_alloc_id__(struct ofproto_dpif *ofproto, uint8_t table_id,
 214                   struct recirc_metadata *md, struct ofpbuf *stack,
 215                   uint32_t action_set_len, uint32_t ofpacts_len,
 216                   const struct ofpact *ofpacts, uint32_t hash)
 217 {
 218     struct recirc_id_node *node = xzalloc(sizeof *node +
 219                                           OFPACT_ALIGN(ofpacts_len));
 220     node->hash = hash;
 221     ovs_refcount_init(&node->refcount);
 222
 223     node->ofproto = ofproto;
 224     node->table_id = table_id;
 225     memcpy(&node->metadata, md, sizeof node->metadata);
 226     node->stack = (stack && stack->size) ? ofpbuf_clone(stack) : NULL;
 227     node->action_set_len = action_set_len;
 228     node->ofpacts_len = ofpacts_len;
 229     if (ofpacts_len) {
 230         memcpy(node->ofpacts, ofpacts, ofpacts_len);
 231     }
 232
 233     ovs_mutex_lock(&mutex);
 234     for (;;) {
 235         /* Claim the next ID.  The ID space should be sparse enough for the
 236            allocation to succeed at the first try.  We do skip the first
 237            RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
 238            the initial allocations may be for long term uses (like bonds). */
 239         node->id = next_id++;
 240         if (OVS_UNLIKELY(!node->id)) {
 241             next_id = RECIRC_POOL_STATIC_IDS + 1;
 242             node->id = next_id++;
 243         }
 244         /* Find if the id is free. */
 245         if (OVS_LIKELY(!recirc_find__(node->id))) {
 246             break;
 247         }
 248     }
 249     cmap_insert(&id_map, &node->id_node, node->id);
 250     cmap_insert(&metadata_map, &node->metadata_node, node->hash);
 251     ovs_mutex_unlock(&mutex);
 252     return node;
 253 }
 254
 255 /* Look up an existing ID for the given flow's metadata and optional actions.
 256  */
 257 uint32_t
 258 recirc_find_id(struct ofproto_dpif *ofproto, uint8_t table_id,
 259                struct recirc_metadata *md, struct ofpbuf *stack,
 260                uint32_t action_set_len, uint32_t ofpacts_len,
 261                const struct ofpact *ofpacts)
 262 {
 263     /* Check if an ID with the given metadata already exists. */
 264     struct recirc_id_node *node;
 265     uint32_t hash;
 266
 267     hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
 268                                 ofpacts_len, ofpacts);
 269     node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
 270                              ofpacts_len, ofpacts, hash);
 271
 272     return node ? node->id : 0;
 273 }
 274
 275 /* Allocate a unique recirculation id for the given set of flow metadata and
 276    optional actions. */
 277 uint32_t
 278 recirc_alloc_id_ctx(struct ofproto_dpif *ofproto, uint8_t table_id,
 279                     struct recirc_metadata *md, struct ofpbuf *stack,
 280                     uint32_t action_set_len, uint32_t ofpacts_len,
 281                     const struct ofpact *ofpacts)
 282 {
 283     struct recirc_id_node *node;
 284     uint32_t hash;
 285
 286     /* Look up an existing ID. */
 287     hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
 288                                 ofpacts_len, ofpacts);
 289     node = recirc_ref_equal(ofproto, table_id, md, stack, action_set_len,
 290                             ofpacts_len, ofpacts, hash);
 291
 292     /* Allocate a new recirc ID if needed. */
 293     if (!node) {
 294         ovs_assert(action_set_len <= ofpacts_len);
 295
 296         node = recirc_alloc_id__(ofproto, table_id, md, stack, action_set_len,
 297                                  ofpacts_len, ofpacts, hash);
 298     }
 299
 300     return node->id;
 301 }
 302
 303 /* Allocate a unique recirculation id. */
 304 uint32_t
 305 recirc_alloc_id(struct ofproto_dpif *ofproto)
 306 {
 307     struct recirc_metadata md;
 308     struct recirc_id_node *node;
 309     uint32_t hash;
 310
 311     memset(&md, 0, sizeof md);
 312     md.in_port = OFPP_NONE;
 313     hash = recirc_metadata_hash(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL);
 314     node = recirc_alloc_id__(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL,
 315                              hash);
 316     return node->id;
 317 }
 318
 319 void
 320 recirc_id_node_unref(const struct recirc_id_node *node_)
 321     OVS_EXCLUDED(mutex)
 322 {
 323     struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
 324
 325     if (node && ovs_refcount_unref(&node->refcount) == 1) {
 326         ovs_mutex_lock(&mutex);
 327         /* Prevent re-use of this node by removing the node from 'metadata_map'
 328          */
 329         cmap_remove(&metadata_map, &node->metadata_node, node->hash);
 330         /* We keep the node in the 'id_map' so that it can be found as long
 331          * as it lingers, and add it to the 'expiring' list. */
 332         list_insert(&expiring, &node->exp_node);
 333         ovs_mutex_unlock(&mutex);
 334     }
 335 }
 336
 337 void
 338 recirc_free_id(uint32_t id)
 339 {
 340     const struct recirc_id_node *node;
 341
 342     node = recirc_id_node_find(id);
 343     if (node) {
 344         recirc_id_node_unref(node);
 345     } else {
 346         VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
 347     }
 348 }
 349
 350 /* Called when 'ofproto' is destructed.  Checks for and clears any
 351  * recirc_id leak.
 352  * No other thread may have access to the 'ofproto' being destructed.
 353  * All related datapath flows must be deleted before calling this. */
 354 void
 355 recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
 356 {
 357     struct recirc_id_node *n;
 358
 359     CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
 360         if (n->ofproto == ofproto) {
 361             VLOG_ERR("recirc_id %"PRIu32
 362                      " left allocated when ofproto (%s)"
 363                      " is destructed", n->id, ofproto_name);
 364         }
 365     }
 366 }