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;
  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_POP (node, exp_node, &expired) {
  90             cmap_remove(&id_map, &node->id_node, node->id);
  91             ovsrcu_postpone(free, node);
  92         }
  93
  94         if (!list_is_empty(&expiring)) {
  95             /* 'expired' is now empty, move nodes in 'expiring' to it. */
  96             list_splice(&expired, list_front(&expiring), &expiring);
  97         }
  98     }
  99     ovs_mutex_unlock(&mutex);
 100 }
 101
 102 /* We use the id as the hash value, which works due to cmap internal rehashing.
 103  * We also only insert nodes with unique IDs, so all possible hash collisions
 104  * remain internal to the cmap. */
 105 static struct recirc_id_node *
 106 recirc_find__(uint32_t id)
 107     OVS_REQUIRES(mutex)
 108 {
 109     struct cmap_node *node = cmap_find_protected(&id_map, id);
 110
 111     return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
 112 }
 113
 114 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 115  * state, caller should copy the contents. */
 116 const struct recirc_id_node *
 117 recirc_id_node_find(uint32_t id)
 118 {
 119     const struct cmap_node *node = cmap_find(&id_map, id);
 120
 121     return node
 122         ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
 123         : NULL;
 124 }
 125
 126 static uint32_t
 127 recirc_metadata_hash(const struct recirc_state *state)
 128 {
 129     uint32_t hash;
 130
 131     hash = hash_pointer(state->ofproto, 0);
 132     hash = hash_int(state->table_id, hash);
 133     hash = hash_words64((const uint64_t *) &state->metadata,
 134                         sizeof state->metadata / sizeof(uint64_t),
 135                         hash);
 136     if (state->stack && state->stack->size != 0) {
 137         hash = hash_words64((const uint64_t *) state->stack->data,
 138                             state->stack->size / sizeof(uint64_t), hash);
 139     }
 140     hash = hash_int(state->mirrors, hash);
 141     hash = hash_int(state->action_set_len, hash);
 142     if (state->ofpacts_len) {
 143         hash = hash_words64(ALIGNED_CAST(const uint64_t *, state->ofpacts),
 144                             state->ofpacts_len / sizeof(uint64_t),
 145                             hash);
 146     }
 147     return hash;
 148 }
 149
 150 static bool
 151 recirc_metadata_equal(const struct recirc_state *a,
 152                       const struct recirc_state *b)
 153 {
 154     return (a->table_id == b->table_id
 155             && a->ofproto == b->ofproto
 156             && !memcmp(&a->metadata, &b->metadata, sizeof a->metadata)
 157             && (((!a->stack || !a->stack->size) &&
 158                  (!b->stack || !b->stack->size))
 159                 || (a->stack && b->stack && ofpbuf_equal(a->stack, b->stack)))
 160             && a->mirrors == b->mirrors
 161             && a->action_set_len == b->action_set_len
 162             && ofpacts_equal(a->ofpacts, a->ofpacts_len,
 163                              b->ofpacts, b->ofpacts_len));
 164 }
 165
 166 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 167  * state, caller should take a reference. */
 168 static struct recirc_id_node *
 169 recirc_find_equal(const struct recirc_state *target, uint32_t hash)
 170 {
 171     struct recirc_id_node *node;
 172
 173     CMAP_FOR_EACH_WITH_HASH (node, metadata_node, hash, &metadata_map) {
 174         if (recirc_metadata_equal(&node->state, target)) {
 175             return node;
 176         }
 177     }
 178     return NULL;
 179 }
 180
 181 static struct recirc_id_node *
 182 recirc_ref_equal(const struct recirc_state *target, uint32_t hash)
 183 {
 184     struct recirc_id_node *node;
 185
 186     do {
 187         node = recirc_find_equal(target, hash);
 188
 189         /* Try again if the node was released before we get the reference. */
 190     } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
 191
 192     return node;
 193 }
 194
 195 static void
 196 recirc_state_clone(struct recirc_state *new, const struct recirc_state *old)
 197 {
 198     *new = *old;
 199     if (new->stack) {
 200         new->stack = new->stack->size ? ofpbuf_clone(new->stack) : NULL;
 201     }
 202     if (new->ofpacts) {
 203         new->ofpacts = (new->ofpacts_len
 204                         ? xmemdup(new->ofpacts, new->ofpacts_len)
 205                         : NULL);
 206     }
 207 }
 208
 209 /* Allocate a unique recirculation id for the given set of flow metadata.
 210  * The ID space is 2^^32, so there should never be a situation in which all
 211  * the IDs are used up.  We loop until we find a free one.
 212  * hash is recomputed if it is passed in as 0. */
 213 static struct recirc_id_node *
 214 recirc_alloc_id__(const struct recirc_state *state, uint32_t hash)
 215 {
 216     ovs_assert(state->action_set_len <= state->ofpacts_len);
 217
 218     struct recirc_id_node *node = xzalloc(sizeof *node);
 219     node->hash = hash;
 220     ovs_refcount_init(&node->refcount);
 221     recirc_state_clone(CONST_CAST(struct recirc_state *, &node->state), state);
 222
 223     ovs_mutex_lock(&mutex);
 224     for (;;) {
 225         /* Claim the next ID.  The ID space should be sparse enough for the
 226            allocation to succeed at the first try.  We do skip the first
 227            RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
 228            the initial allocations may be for long term uses (like bonds). */
 229         node->id = next_id++;
 230         if (OVS_UNLIKELY(!node->id)) {
 231             next_id = RECIRC_POOL_STATIC_IDS + 1;
 232             node->id = next_id++;
 233         }
 234         /* Find if the id is free. */
 235         if (OVS_LIKELY(!recirc_find__(node->id))) {
 236             break;
 237         }
 238     }
 239     cmap_insert(&id_map, &node->id_node, node->id);
 240     cmap_insert(&metadata_map, &node->metadata_node, node->hash);
 241     ovs_mutex_unlock(&mutex);
 242     return node;
 243 }
 244
 245 /* Look up an existing ID for the given flow's metadata and optional actions.
 246  */
 247 uint32_t
 248 recirc_find_id(const struct recirc_state *target)
 249 {
 250     uint32_t hash = recirc_metadata_hash(target);
 251     struct recirc_id_node *node = recirc_find_equal(target, hash);
 252     return node ? node->id : 0;
 253 }
 254
 255 /* Allocate a unique recirculation id for the given set of flow metadata and
 256    optional actions. */
 257 uint32_t
 258 recirc_alloc_id_ctx(const struct recirc_state *state)
 259 {
 260     uint32_t hash = recirc_metadata_hash(state);
 261     struct recirc_id_node *node = recirc_ref_equal(state, hash);
 262     if (!node) {
 263         node = recirc_alloc_id__(state, hash);
 264     }
 265     return node->id;
 266 }
 267
 268 /* Allocate a unique recirculation id. */
 269 uint32_t
 270 recirc_alloc_id(struct ofproto_dpif *ofproto)
 271 {
 272     struct recirc_state state = {
 273         .table_id = TBL_INTERNAL,
 274         .ofproto = ofproto,
 275         .metadata = { .in_port = OFPP_NONE },
 276     };
 277     return recirc_alloc_id__(&state, recirc_metadata_hash(&state))->id;
 278 }
 279
 280 void
 281 recirc_id_node_unref(const struct recirc_id_node *node_)
 282     OVS_EXCLUDED(mutex)
 283 {
 284     struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
 285
 286     if (node && ovs_refcount_unref(&node->refcount) == 1) {
 287         ovs_mutex_lock(&mutex);
 288         /* Prevent re-use of this node by removing the node from 'metadata_map'
 289          */
 290         cmap_remove(&metadata_map, &node->metadata_node, node->hash);
 291         /* We keep the node in the 'id_map' so that it can be found as long
 292          * as it lingers, and add it to the 'expiring' list. */
 293         list_insert(&expiring, &node->exp_node);
 294         ovs_mutex_unlock(&mutex);
 295     }
 296 }
 297
 298 void
 299 recirc_free_id(uint32_t id)
 300 {
 301     const struct recirc_id_node *node;
 302
 303     node = recirc_id_node_find(id);
 304     if (node) {
 305         recirc_id_node_unref(node);
 306     } else {
 307         VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
 308     }
 309 }
 310
 311 /* Called when 'ofproto' is destructed.  Checks for and clears any
 312  * recirc_id leak.
 313  * No other thread may have access to the 'ofproto' being destructed.
 314  * All related datapath flows must be deleted before calling this. */
 315 void
 316 recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
 317 {
 318     struct recirc_id_node *n;
 319
 320     CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
 321         if (n->state.ofproto == ofproto) {
 322             VLOG_ERR("recirc_id %"PRIu32
 323                      " left allocated when ofproto (%s)"
 324                      " is destructed", n->id, ofproto_name);
 325         }
 326     }
 327 }