ofproto/ofproto-dpif-rid.c

   1 /*
   2  * Copyright (c) 2014, 2015, 2016 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 static void recirc_id_node_free(struct recirc_id_node *);
  40
  41 void
  42 recirc_init(void)
  43 {
  44     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
  45
  46     if (ovsthread_once_start(&once)) {
  47         ovs_mutex_init(&mutex);
  48         ovs_mutex_lock(&mutex);
  49         next_id = 1; /* 0 is not a valid ID. */
  50         cmap_init(&id_map);
  51         cmap_init(&metadata_map);
  52         list_init(&expiring);
  53         list_init(&expired);
  54         ovs_mutex_unlock(&mutex);
  55
  56         ovsthread_once_done(&once);
  57     }
  58
  59 }
  60
  61 /* This should be called by the revalidator once at each round (every 500ms or
  62  * more). */
  63 void
  64 recirc_run(void)
  65 {
  66     static long long int last = 0;
  67     long long int now = time_msec();
  68
  69     /* Do maintenance at most 4 times / sec. */
  70     ovs_mutex_lock(&mutex);
  71     if (now - last > 250) {
  72         struct recirc_id_node *node;
  73
  74         last = now;
  75
  76         /* Nodes in 'expiring' and 'expired' lists have the refcount of zero,
  77          * which means that while they can still be found (by id), no new
  78          * references can be taken on them.  We have removed the entry from the
  79          * 'metadata_map', at the time when refcount reached zero, causing any
  80          * new translations to allocate a new ID.  This allows the expiring
  81          * entry to be safely deleted while any sudden new use of the similar
  82          * recirculation will safely start using a new recirculation ID.  When
  83          * the refcount gets to zero, the node is also added to the 'expiring'
  84          * list.  At any time after that the nodes in the 'expiring' list can
  85          * be moved to the 'expired' list, from which they are deleted at least
  86          * 250ms afterwards. */
  87
  88         /* Delete the expired.  These have been lingering for at least 250 ms,
  89          * which should be enough for any ongoing recirculations to be
  90          * finished. */
  91         LIST_FOR_EACH_POP (node, exp_node, &expired) {
  92             cmap_remove(&id_map, &node->id_node, node->id);
  93             ovsrcu_postpone(recirc_id_node_free, node);
  94         }
  95
  96         if (!list_is_empty(&expiring)) {
  97             /* 'expired' is now empty, move nodes in 'expiring' to it. */
  98             list_splice(&expired, list_front(&expiring), &expiring);
  99         }
 100     }
 101     ovs_mutex_unlock(&mutex);
 102 }
 103
 104 /* We use the id as the hash value, which works due to cmap internal rehashing.
 105  * We also only insert nodes with unique IDs, so all possible hash collisions
 106  * remain internal to the cmap. */
 107 static struct recirc_id_node *
 108 recirc_find__(uint32_t id)
 109     OVS_REQUIRES(mutex)
 110 {
 111     struct cmap_node *node = cmap_find_protected(&id_map, id);
 112
 113     return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
 114 }
 115
 116 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 117  * state, caller should copy the contents. */
 118 const struct recirc_id_node *
 119 recirc_id_node_find(uint32_t id)
 120 {
 121     const struct cmap_node *node = cmap_find(&id_map, id);
 122
 123     return node
 124         ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
 125         : NULL;
 126 }
 127
 128 static uint32_t
 129 frozen_state_hash(const struct frozen_state *state)
 130 {
 131     uint32_t hash;
 132
 133     hash = uuid_hash(&state->ofproto_uuid);
 134     hash = hash_int(state->table_id, hash);
 135     if (flow_tnl_dst_is_set(state->metadata.tunnel)) {
 136         /* We may leave remainder bytes unhashed, but that is unlikely as
 137          * the tunnel is not in the datapath format. */
 138         hash = hash_bytes64((const uint64_t *) state->metadata.tunnel,
 139                             flow_tnl_size(state->metadata.tunnel), hash);
 140     }
 141     hash = hash_boolean(state->conntracked, hash);
 142     hash = hash_bytes64((const uint64_t *) &state->metadata.metadata,
 143                         sizeof state->metadata - sizeof state->metadata.tunnel,
 144                         hash);
 145     if (state->stack && state->n_stack) {
 146         hash = hash_bytes64((const uint64_t *) state->stack,
 147                             state->n_stack * sizeof *state->stack, hash);
 148     }
 149     hash = hash_int(state->mirrors, hash);
 150     hash = hash_int(state->action_set_len, hash);
 151     if (state->action_set_len) {
 152         hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->action_set),
 153                             state->action_set_len, hash);
 154     }
 155     if (state->ofpacts_len) {
 156         hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->ofpacts),
 157                             state->ofpacts_len, hash);
 158     }
 159     return hash;
 160 }
 161
 162 static bool
 163 frozen_state_equal(const struct frozen_state *a, const struct frozen_state *b)
 164 {
 165     return (a->table_id == b->table_id
 166             && uuid_equals(&a->ofproto_uuid, &b->ofproto_uuid)
 167             && flow_tnl_equal(a->metadata.tunnel, b->metadata.tunnel)
 168             && !memcmp(&a->metadata.metadata, &b->metadata.metadata,
 169                        sizeof a->metadata - sizeof a->metadata.tunnel)
 170             && a->n_stack == b->n_stack
 171             && !memcmp(a->stack, b->stack, a->n_stack * sizeof *a->stack)
 172             && a->mirrors == b->mirrors
 173             && a->conntracked == b->conntracked
 174             && ofpacts_equal(a->ofpacts, a->ofpacts_len,
 175                              b->ofpacts, b->ofpacts_len)
 176             && ofpacts_equal(a->action_set, a->action_set_len,
 177                              b->action_set, b->action_set_len));
 178 }
 179
 180 /* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 181  * state, caller should take a reference. */
 182 static struct recirc_id_node *
 183 recirc_find_equal(const struct frozen_state *target, uint32_t hash)
 184 {
 185     struct recirc_id_node *node;
 186
 187     CMAP_FOR_EACH_WITH_HASH (node, metadata_node, hash, &metadata_map) {
 188         if (frozen_state_equal(&node->state, target)) {
 189             return node;
 190         }
 191     }
 192     return NULL;
 193 }
 194
 195 static struct recirc_id_node *
 196 recirc_ref_equal(const struct frozen_state *target, uint32_t hash)
 197 {
 198     struct recirc_id_node *node;
 199
 200     do {
 201         node = recirc_find_equal(target, hash);
 202
 203         /* Try again if the node was released before we get the reference. */
 204     } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
 205
 206     return node;
 207 }
 208
 209 static void
 210 frozen_state_clone(struct frozen_state *new, const struct frozen_state *old,
 211                    struct flow_tnl *tunnel)
 212 {
 213     *new = *old;
 214     flow_tnl_copy__(tunnel, old->metadata.tunnel);
 215     new->metadata.tunnel = tunnel;
 216
 217     new->stack = (new->n_stack
 218                   ? xmemdup(new->stack, new->n_stack * sizeof *new->stack)
 219                   : NULL);
 220     new->ofpacts = (new->ofpacts_len
 221                     ? xmemdup(new->ofpacts, new->ofpacts_len)
 222                     : NULL);
 223     new->action_set = (new->action_set_len
 224                        ? xmemdup(new->action_set, new->action_set_len)
 225                        : NULL);
 226 }
 227
 228 static void
 229 frozen_state_free(struct frozen_state *state)
 230 {
 231     free(state->stack);
 232     free(state->ofpacts);
 233     free(state->action_set);
 234 }
 235
 236 /* Allocate a unique recirculation id for the given set of flow metadata.
 237  * The ID space is 2^^32, so there should never be a situation in which all
 238  * the IDs are used up.  We loop until we find a free one.
 239  * hash is recomputed if it is passed in as 0. */
 240 static struct recirc_id_node *
 241 recirc_alloc_id__(const struct frozen_state *state, uint32_t hash)
 242 {
 243     ovs_assert(state->action_set_len <= state->ofpacts_len);
 244
 245     struct recirc_id_node *node = xzalloc(sizeof *node);
 246
 247     node->hash = hash;
 248     ovs_refcount_init(&node->refcount);
 249     frozen_state_clone(CONST_CAST(struct frozen_state *, &node->state), state,
 250                        &node->state_metadata_tunnel);
 251
 252     ovs_mutex_lock(&mutex);
 253     for (;;) {
 254         /* Claim the next ID.  The ID space should be sparse enough for the
 255            allocation to succeed at the first try.  We do skip the first
 256            RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
 257            the initial allocations may be for long term uses (like bonds). */
 258         node->id = next_id++;
 259         if (OVS_UNLIKELY(!node->id)) {
 260             next_id = RECIRC_POOL_STATIC_IDS + 1;
 261             node->id = next_id++;
 262         }
 263         /* Find if the id is free. */
 264         if (OVS_LIKELY(!recirc_find__(node->id))) {
 265             break;
 266         }
 267     }
 268     cmap_insert(&id_map, &node->id_node, node->id);
 269     cmap_insert(&metadata_map, &node->metadata_node, node->hash);
 270     ovs_mutex_unlock(&mutex);
 271     return node;
 272 }
 273
 274 /* Look up an existing ID for the given flow's metadata and optional actions.
 275  */
 276 uint32_t
 277 recirc_find_id(const struct frozen_state *target)
 278 {
 279     uint32_t hash = frozen_state_hash(target);
 280     struct recirc_id_node *node = recirc_find_equal(target, hash);
 281     return node ? node->id : 0;
 282 }
 283
 284 /* Allocate a unique recirculation id for the given set of flow metadata and
 285    optional actions. */
 286 uint32_t
 287 recirc_alloc_id_ctx(const struct frozen_state *state)
 288 {
 289     uint32_t hash = frozen_state_hash(state);
 290     struct recirc_id_node *node = recirc_ref_equal(state, hash);
 291     if (!node) {
 292         node = recirc_alloc_id__(state, hash);
 293     }
 294     return node->id;
 295 }
 296
 297 /* Allocate a unique recirculation id. */
 298 uint32_t
 299 recirc_alloc_id(struct ofproto_dpif *ofproto)
 300 {
 301     struct flow_tnl tunnel;
 302     tunnel.ip_dst = htonl(0);
 303     tunnel.ipv6_dst = in6addr_any;
 304     struct frozen_state state = {
 305         .table_id = TBL_INTERNAL,
 306         .ofproto_uuid = *ofproto_dpif_get_uuid(ofproto),
 307         .metadata = { .tunnel = &tunnel, .in_port = OFPP_NONE },
 308     };
 309     return recirc_alloc_id__(&state, frozen_state_hash(&state))->id;
 310 }
 311
 312 static void
 313 recirc_id_node_free(struct recirc_id_node *node)
 314 {
 315     frozen_state_free(CONST_CAST(struct frozen_state *, &node->state));
 316     free(node);
 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     const struct uuid *ofproto_uuid = ofproto_dpif_get_uuid(ofproto);
 360     CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
 361         if (uuid_equals(&n->state.ofproto_uuid, ofproto_uuid)) {
 362             VLOG_ERR("recirc_id %"PRIu32
 363                      " left allocated when ofproto (%s)"
 364                      " is destructed", n->id, ofproto_name);
 365         }
 366     }
 367 }