← Back to branch summary

~ubuntu-branches/ubuntu/wily/openvswitch/wily

« back to all changes in this revision

Viewing changes to ofproto/ofproto-dpif-rid.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2015-08-10 11:35:15 UTC
  • mfrom: (1.1.30)
  • Revision ID: package-import@ubuntu.com-20150810113515-575vj06oq29emxsn
Tags: 2.4.0~git20150810.97bab95-0ubuntu1
* New upstream snapshot from 2.4 branch:
  - d/*: Align any relevant packaging changes with upstream.
* d/*: wrap-and-sort.
* d/openvswitch-{common,vswitch}.install: Correct install location for
  bash completion files.
* d/tests/openflow.py: Explicitly use ovs-testcontroller as provided
  by 2.4.0 release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ofproto/ofproto-dpif-rid.c
1
1
/*
2
 
 * Copyright (c) 2014 Nicira, Inc.
 
2
 * Copyright (c) 2014, 2015 Nicira, Inc.
3
3
 *
4
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
5
 * you may not use this file except in compliance with the License.
16
16
 
17
17
#include <config.h>
18
18
 
19
 
#include "hmap.h"
20
 
#include "hash.h"
21
 
#include "ovs-thread.h"
 
19
#include "ofpbuf.h"
 
20
#include "ofproto-dpif.h"
22
21
#include "ofproto-dpif-rid.h"
23
 
 
24
 
struct rid_map {
25
 
    struct hmap map;
26
 
};
27
 
 
28
 
struct rid_node {
29
 
    struct hmap_node node;
30
 
    uint32_t recirc_id;
31
 
};
32
 
 
33
 
struct rid_pool {
34
 
    struct rid_map ridmap;
35
 
    uint32_t base;         /* IDs in the range of [base, base + n_ids). */
36
 
    uint32_t n_ids;        /* Total number of ids in the pool. */
37
 
    uint32_t next_free_id; /* Possible next free id. */
38
 
};
39
 
 
40
 
struct recirc_id_pool {
41
 
    struct ovs_mutex lock;
42
 
    struct rid_pool rids;
43
 
};
44
 
 
45
 
#define RECIRC_ID_BASE  300
46
 
#define RECIRC_ID_N_IDS  1024
47
 
 
48
 
static void rid_pool_init(struct rid_pool *rids,
49
 
                         uint32_t base, uint32_t n_ids);
50
 
static void rid_pool_uninit(struct rid_pool *pool);
51
 
static uint32_t rid_pool_alloc_id(struct rid_pool *pool);
52
 
static void rid_pool_free_id(struct rid_pool *rids, uint32_t rid);
53
 
static struct rid_node *rid_pool_find(struct rid_pool *rids, uint32_t id);
54
 
static struct rid_node *rid_pool_add(struct rid_pool *rids, uint32_t id);
55
 
 
56
 
struct recirc_id_pool *
57
 
recirc_id_pool_create(void)
58
 
{
59
 
    struct recirc_id_pool *pool;
60
 
 
61
 
    pool = xmalloc(sizeof *pool);
62
 
    rid_pool_init(&pool->rids, RECIRC_ID_BASE, RECIRC_ID_N_IDS);
63
 
    ovs_mutex_init(&pool->lock);
64
 
 
65
 
    return pool;
66
 
}
67
 
 
68
 
void
69
 
recirc_id_pool_destroy(struct recirc_id_pool *pool)
70
 
{
71
 
    rid_pool_uninit(&pool->rids);
72
 
    ovs_mutex_destroy(&pool->lock);
73
 
    free(pool);
74
 
}
75
 
 
76
 
uint32_t
77
 
recirc_id_alloc(struct recirc_id_pool *pool)
78
 
{
79
 
    uint32_t id;
80
 
 
81
 
    ovs_mutex_lock(&pool->lock);
82
 
    id = rid_pool_alloc_id(&pool->rids);
83
 
    ovs_mutex_unlock(&pool->lock);
84
 
 
85
 
    return id;
86
 
}
87
 
 
88
 
void
89
 
recirc_id_free(struct recirc_id_pool *pool, uint32_t id)
90
 
{
91
 
    ovs_mutex_lock(&pool->lock);
92
 
    rid_pool_free_id(&pool->rids, id);
93
 
    ovs_mutex_unlock(&pool->lock);
94
 
}
95
 
 
96
 
static void
97
 
rid_pool_init(struct rid_pool *rids, uint32_t base, uint32_t n_ids)
98
 
{
99
 
    rids->base = base;
100
 
    rids->n_ids = n_ids;
101
 
    rids->next_free_id = base;
102
 
    hmap_init(&rids->ridmap.map);
103
 
}
104
 
 
105
 
static void
106
 
rid_pool_uninit(struct rid_pool *rids)
107
 
{
108
 
    struct rid_node *rid, *next;
109
 
 
110
 
    HMAP_FOR_EACH_SAFE(rid, next, node, &rids->ridmap.map) {
111
 
        hmap_remove(&rids->ridmap.map, &rid->node);
112
 
        free(rid);
113
 
    }
114
 
 
115
 
    hmap_destroy(&rids->ridmap.map);
116
 
}
117
 
 
118
 
static struct rid_node *
119
 
rid_pool_find(struct rid_pool *rids, uint32_t id)
120
 
{
121
 
    size_t hash;
122
 
    struct rid_node *rid;
123
 
 
124
 
    hash = hash_int(id, 0);
125
 
    HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &rids->ridmap.map) {
126
 
        if (id == rid->recirc_id) {
127
 
            return rid;
 
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(struct ofproto_dpif *ofproto, uint8_t table_id,
 
128
                     struct recirc_metadata *md, struct ofpbuf *stack,
 
129
                     uint32_t action_set_len, uint32_t ofpacts_len,
 
130
                     const struct ofpact *ofpacts)
 
131
{
 
132
    uint32_t hash;
 
133
 
 
134
    BUILD_ASSERT(OFPACT_ALIGNTO == sizeof(uint64_t));
 
135
 
 
136
    hash = hash_pointer(ofproto, 0);
 
137
    hash = hash_int(table_id, hash);
 
138
    hash = hash_words64((const uint64_t *)md, sizeof *md / sizeof(uint64_t),
 
139
                        hash);
 
140
    if (stack && stack->size != 0) {
 
141
        hash = hash_words64((const uint64_t *)stack->data,
 
142
                            stack->size / sizeof(uint64_t), hash);
 
143
    }
 
144
    hash = hash_int(action_set_len, hash);
 
145
    if (ofpacts_len) {
 
146
        hash = hash_words64(ALIGNED_CAST(const uint64_t *, ofpacts),
 
147
                            OFPACT_ALIGN(ofpacts_len) / sizeof(uint64_t),
 
148
                            hash);
 
149
    }
 
150
    return hash;
 
151
}
 
152
 
 
153
static bool
 
154
recirc_metadata_equal(const struct recirc_id_node *node,
 
155
                      struct ofproto_dpif *ofproto, uint8_t table_id,
 
156
                      struct recirc_metadata *md, struct ofpbuf *stack,
 
157
                      uint32_t action_set_len, uint32_t ofpacts_len,
 
158
                      const struct ofpact *ofpacts)
 
159
{
 
160
    return node->ofproto == ofproto
 
161
        && node->table_id == table_id
 
162
        && !memcmp(&node->metadata, md, sizeof *md)
 
163
        && ((!node->stack && (!stack || stack->size == 0))
 
164
            || (node->stack && stack && ofpbuf_equal(node->stack, stack)))
 
165
        && node->action_set_len == action_set_len
 
166
        && node->ofpacts_len == ofpacts_len
 
167
        && (ofpacts_len == 0 || !memcmp(node->ofpacts, ofpacts, ofpacts_len));
 
168
}
 
169
 
 
170
/* Lockless RCU protected lookup.  If node is needed accross RCU quiescent
 
171
 * state, caller should take a reference. */
 
172
static struct recirc_id_node *
 
173
recirc_find_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
 
174
                  struct recirc_metadata *md, struct ofpbuf *stack,
 
175
                  uint32_t action_set_len, uint32_t ofpacts_len,
 
176
                  const struct ofpact *ofpacts, uint32_t hash)
 
177
{
 
178
    struct recirc_id_node *node;
 
179
 
 
180
    CMAP_FOR_EACH_WITH_HASH(node, metadata_node, hash, &metadata_map) {
 
181
        if (recirc_metadata_equal(node, ofproto, table_id, md, stack,
 
182
                                  action_set_len, ofpacts_len, ofpacts)) {
 
183
            return node;
128
184
        }
129
185
    }
130
186
    return NULL;
131
187
}
132
188
 
133
 
static struct rid_node *
134
 
rid_pool_add(struct rid_pool *rids, uint32_t id)
135
 
{
136
 
    struct rid_node *rid = xmalloc(sizeof *rid);
137
 
    size_t hash;
138
 
 
139
 
    rid->recirc_id = id;
140
 
    hash = hash_int(id, 0);
141
 
    hmap_insert(&rids->ridmap.map, &rid->node, hash);
142
 
    return rid;
143
 
}
144
 
 
145
 
static uint32_t
146
 
rid_pool_alloc_id(struct rid_pool *rids)
147
 
{
148
 
    uint32_t id;
149
 
 
150
 
    if (rids->n_ids == 0) {
151
 
        return 0;
152
 
    }
153
 
 
154
 
    if (!(rid_pool_find(rids, rids->next_free_id))) {
155
 
        id = rids->next_free_id;
156
 
        goto found_free_id;
157
 
    }
158
 
 
159
 
    for(id = rids->base; id < rids->base + rids->n_ids; id++) {
160
 
        if (!rid_pool_find(rids, id)) {
161
 
            goto found_free_id;
162
 
        }
163
 
    }
164
 
 
165
 
    /* Not available. */
166
 
    return 0;
167
 
 
168
 
found_free_id:
169
 
    rid_pool_add(rids, id);
170
 
 
171
 
    if (id < rids->base + rids->n_ids) {
172
 
        rids->next_free_id = id + 1;
 
189
static struct recirc_id_node *
 
190
recirc_ref_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
 
191
                 struct recirc_metadata *md, struct ofpbuf *stack,
 
192
                 uint32_t action_set_len, uint32_t ofpacts_len,
 
193
                 const struct ofpact *ofpacts, uint32_t hash)
 
194
{
 
195
    struct recirc_id_node *node;
 
196
 
 
197
    do {
 
198
        node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
 
199
                                 ofpacts_len, ofpacts, hash);
 
200
 
 
201
        /* Try again if the node was released before we get the reference. */
 
202
    } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
 
203
 
 
204
    return node;
 
205
}
 
206
 
 
207
/* Allocate a unique recirculation id for the given set of flow metadata.
 
208
 * The ID space is 2^^32, so there should never be a situation in which all
 
209
 * the IDs are used up.  We loop until we find a free one.
 
210
 * hash is recomputed if it is passed in as 0. */
 
211
static struct recirc_id_node *
 
212
recirc_alloc_id__(struct ofproto_dpif *ofproto, uint8_t table_id,
 
213
                  struct recirc_metadata *md, struct ofpbuf *stack,
 
214
                  uint32_t action_set_len, uint32_t ofpacts_len,
 
215
                  const struct ofpact *ofpacts, uint32_t hash)
 
216
{
 
217
    struct recirc_id_node *node = xzalloc(sizeof *node +
 
218
                                          OFPACT_ALIGN(ofpacts_len));
 
219
    node->hash = hash;
 
220
    ovs_refcount_init(&node->refcount);
 
221
 
 
222
    node->ofproto = ofproto;
 
223
    node->table_id = table_id;
 
224
    memcpy(&node->metadata, md, sizeof node->metadata);
 
225
    node->stack = (stack && stack->size) ? ofpbuf_clone(stack) : NULL;
 
226
    node->action_set_len = action_set_len;
 
227
    node->ofpacts_len = ofpacts_len;
 
228
    if (ofpacts_len) {
 
229
        memcpy(node->ofpacts, ofpacts, ofpacts_len);
 
230
    }
 
231
 
 
232
    ovs_mutex_lock(&mutex);
 
233
    for (;;) {
 
234
        /* Claim the next ID.  The ID space should be sparse enough for the
 
235
           allocation to succeed at the first try.  We do skip the first
 
236
           RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
 
237
           the initial allocations may be for long term uses (like bonds). */
 
238
        node->id = next_id++;
 
239
        if (OVS_UNLIKELY(!node->id)) {
 
240
            next_id = RECIRC_POOL_STATIC_IDS + 1;
 
241
            node->id = next_id++;
 
242
        }
 
243
        /* Find if the id is free. */
 
244
        if (OVS_LIKELY(!recirc_find__(node->id))) {
 
245
            break;
 
246
        }
 
247
    }
 
248
    cmap_insert(&id_map, &node->id_node, node->id);
 
249
    cmap_insert(&metadata_map, &node->metadata_node, node->hash);
 
250
    ovs_mutex_unlock(&mutex);
 
251
    return node;
 
252
}
 
253
 
 
254
/* Look up an existing ID for the given flow's metadata and optional actions.
 
255
 */
 
256
uint32_t
 
257
recirc_find_id(struct ofproto_dpif *ofproto, uint8_t table_id,
 
258
               struct recirc_metadata *md, struct ofpbuf *stack,
 
259
               uint32_t action_set_len, uint32_t ofpacts_len,
 
260
               const struct ofpact *ofpacts)
 
261
{
 
262
    /* Check if an ID with the given metadata already exists. */
 
263
    struct recirc_id_node *node;
 
264
    uint32_t hash;
 
265
 
 
266
    hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
 
267
                                ofpacts_len, ofpacts);
 
268
    node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
 
269
                             ofpacts_len, ofpacts, hash);
 
270
 
 
271
    return node ? node->id : 0;
 
272
}
 
273
 
 
274
/* Allocate a unique recirculation id for the given set of flow metadata and
 
275
   optional actions. */
 
276
uint32_t
 
277
recirc_alloc_id_ctx(struct ofproto_dpif *ofproto, uint8_t table_id,
 
278
                    struct recirc_metadata *md, struct ofpbuf *stack,
 
279
                    uint32_t action_set_len, uint32_t ofpacts_len,
 
280
                    const struct ofpact *ofpacts)
 
281
{
 
282
    struct recirc_id_node *node;
 
283
    uint32_t hash;
 
284
 
 
285
    /* Look up an existing ID. */
 
286
    hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
 
287
                                ofpacts_len, ofpacts);
 
288
    node = recirc_ref_equal(ofproto, table_id, md, stack, action_set_len,
 
289
                            ofpacts_len, ofpacts, hash);
 
290
 
 
291
    /* Allocate a new recirc ID if needed. */
 
292
    if (!node) {
 
293
        ovs_assert(action_set_len <= ofpacts_len);
 
294
 
 
295
        node = recirc_alloc_id__(ofproto, table_id, md, stack, action_set_len,
 
296
                                 ofpacts_len, ofpacts, hash);
 
297
    }
 
298
 
 
299
    return node->id;
 
300
}
 
301
 
 
302
/* Allocate a unique recirculation id. */
 
303
uint32_t
 
304
recirc_alloc_id(struct ofproto_dpif *ofproto)
 
305
{
 
306
    struct recirc_metadata md;
 
307
    struct recirc_id_node *node;
 
308
    uint32_t hash;
 
309
 
 
310
    memset(&md, 0, sizeof md);
 
311
    md.in_port = OFPP_NONE;
 
312
    hash = recirc_metadata_hash(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL);
 
313
    node = recirc_alloc_id__(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL,
 
314
                             hash);
 
315
    return node->id;
 
316
}
 
317
 
 
318
void
 
319
recirc_id_node_unref(const struct recirc_id_node *node_)
 
320
    OVS_EXCLUDED(mutex)
 
321
{
 
322
    struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
 
323
 
 
324
    if (node && ovs_refcount_unref(&node->refcount) == 1) {
 
325
        ovs_mutex_lock(&mutex);
 
326
        /* Prevent re-use of this node by removing the node from 'metadata_map'
 
327
         */
 
328
        cmap_remove(&metadata_map, &node->metadata_node, node->hash);
 
329
        /* We keep the node in the 'id_map' so that it can be found as long
 
330
         * as it lingers, and add it to the 'expiring' list. */
 
331
        list_insert(&expiring, &node->exp_node);
 
332
        ovs_mutex_unlock(&mutex);
 
333
    }
 
334
}
 
335
 
 
336
void
 
337
recirc_free_id(uint32_t id)
 
338
{
 
339
    const struct recirc_id_node *node;
 
340
 
 
341
    node = recirc_id_node_find(id);
 
342
    if (node) {
 
343
        recirc_id_node_unref(node);
173
344
    } else {
174
 
        rids->next_free_id = rids->base;
 
345
        VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
175
346
    }
176
 
 
177
 
    return id;
178
347
}
179
348
 
180
 
static void
181
 
rid_pool_free_id(struct rid_pool *rids, uint32_t id)
 
349
/* Called when 'ofproto' is destructed.  Checks for and clears any
 
350
 * recirc_id leak.
 
351
 * No other thread may have access to the 'ofproto' being destructed.
 
352
 * All related datapath flows must be deleted before calling this. */
 
353
void
 
354
recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
182
355
{
183
 
    struct rid_node *rid;
184
 
    if (id > rids->base && (id <= rids->base + rids->n_ids)) {
185
 
        rid = rid_pool_find(rids, id);
186
 
        if (rid) {
187
 
            hmap_remove(&rids->ridmap.map, &rid->node);
188
 
            free(rid);
 
356
    struct recirc_id_node *n;
 
357
 
 
358
    CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
 
359
        if (n->ofproto == ofproto) {
 
360
            VLOG_ERR("recirc_id %"PRIu32
 
361
                     " left allocated when ofproto (%s)"
 
362
                     " is destructed", n->id, ofproto_name);
189
363
        }
190
364
    }
191
365
}