Refactor the lock-free portion of the recirculation id allocator
into stand-alone id pool. This is in preparation for re-using
that portion to allocate bucket ids which are part of (draft)
Open Flow 1.5 groups.
EXT-350
Signed-off-by: Simon Horman <simon.hor...@netronome.com>
---
lib/automake.mk | 2 +
lib/id-pool.c | 152 +++++++++++++++++++++++++++++++++++++++++++++
lib/id-pool.h | 42 +++++++++++++
ofproto/ofproto-dpif-rid.c | 128 ++------------------------------------
4 files changed, 202 insertions(+), 122 deletions(-)
create mode 100644 lib/id-pool.c
create mode 100644 lib/id-pool.h
diff --git a/lib/automake.mk b/lib/automake.mk
index 1256af1..40c0241 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -84,6 +84,8 @@ lib_libopenvswitch_la_SOURCES = \
lib/hmap.h \
lib/hmapx.c \
lib/hmapx.h \
+ lib/id-pool.c \
+ lib/id-pool.h \
lib/jhash.c \
lib/jhash.h \
lib/json.c \
diff --git a/lib/id-pool.c b/lib/id-pool.c
new file mode 100644
index 0000000..e6d7827
--- /dev/null
+++ b/lib/id-pool.c
@@ -0,0 +1,152 @@
+/*
+ * Copyright (c) 2014 Nicira, Inc.
+ * Copyright (c) 2014 Netronome.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "hmap.h"
+#include "hash.h"
+#include "id-pool.h"
+
+struct id_node {
+ struct hmap_node node;
+ uint32_t id;
+};
+
+struct id_pool {
+ struct hmap map;
+ uint32_t base; /* IDs in the range of [base, base + n_ids). */
+ uint32_t n_ids; /* Total number of ids in the pool. */
+ uint32_t next_free_id; /* Possible next free id. */
+};
+
+static void id_pool_init(struct id_pool *pool,
+ uint32_t base, uint32_t n_ids);
+static void id_pool_uninit(struct id_pool *pool);
+static struct id_node *id_pool_find(struct id_pool *pool, uint32_t id);
+
+struct id_pool *
+id_pool_create(uint32_t base, uint32_t n_ids)
+{
+ struct id_pool *pool;
+
+ pool = xmalloc(sizeof *pool);
+ id_pool_init(pool, base, n_ids);
+
+ return pool;
+}
+
+void
+id_pool_destroy(struct id_pool *pool)
+{
+ id_pool_uninit(pool);
+ free(pool);
+}
+
+static void
+id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids)
+{
+ pool->base = base;
+ pool->n_ids = n_ids;
+ pool->next_free_id = base;
+ hmap_init(&pool->map);
+}
+
+static void
+id_pool_uninit(struct id_pool *pool)
+{
+ struct id_node *rid, *next;
+
+ HMAP_FOR_EACH_SAFE(rid, next, node, &pool->map) {
+ hmap_remove(&pool->map, &rid->node);
+ free(rid);
+ }
+
+ hmap_destroy(&pool->map);
+}
+
+static struct id_node *
+id_pool_find(struct id_pool *pool, uint32_t id)
+{
+ size_t hash;
+ struct id_node *rid;
+
+ hash = hash_int(id, 0);
+ HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &pool->map) {
+ if (id == rid->id) {
+ return rid;
+ }
+ }
+ return NULL;
+}
+
+void
+id_pool_add(struct id_pool *pool, uint32_t id)
+{
+ struct id_node *rid = xmalloc(sizeof *rid);
+ size_t hash;
+
+ rid->id = id;
+ hash = hash_int(id, 0);
+ hmap_insert(&pool->map, &rid->node, hash);
+}
+
+uint32_t
+id_pool_alloc_id(struct id_pool *pool)
+{
+ uint32_t id;
+
+ if (pool->n_ids == 0) {
+ return 0;
+ }
+
+ if (!(id_pool_find(pool, pool->next_free_id))) {
+ id = pool->next_free_id;
+ goto found_free_id;
+ }
+
+ for(id = pool->base; id < pool->base + pool->n_ids; id++) {
+ if (id_pool_find(pool, id)) {
+ goto found_free_id;
+ }
+ }
+
+ /* Not available. */
+ return 0;
+
+found_free_id:
+ id_pool_add(pool, id);
+
+ if (id < pool->base + pool->n_ids) {
+ pool->next_free_id = id + 1;
+ } else {
+ pool->next_free_id = pool->base;
+ }
+
+ return id;
+}
+
+void
+id_pool_free_id(struct id_pool *pool, uint32_t id)
+{
+ struct id_node *rid;
+ if (id > pool->base && (id <= pool->base + pool->n_ids)) {
+ rid = id_pool_find(pool, id);
+ if (rid) {
+ hmap_remove(&pool->map, &rid->node);
+ }
+ }
+}
diff --git a/lib/id-pool.h b/lib/id-pool.h
new file mode 100644
index 0000000..71784ba
--- /dev/null
+++ b/lib/id-pool.h
@@ -0,0 +1,42 @@
+/*
+ * Copyright (c) 2014 Nicira, Inc.
+ * Copyright (c) 2014 Netronome.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ID_POOL_H
+#define ID_POOL_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+struct id_pool;
+
+struct id_pool *id_pool_create(uint32_t base, uint32_t n_ids);
+void id_pool_destroy(struct id_pool *pool);
+uint32_t id_pool_alloc_id(struct id_pool *pool);
+void id_pool_free_id(struct id_pool *pool, uint32_t id);
+void id_pool_add(struct id_pool *pool, uint32_t id);
+
+/*
+ * ID pool.
+ * ========
+ *
+ * Pool of unique 32bit ids.
+ * =============
+ *
+ * APIs are not thread safe.
+ *
+ */
+#endif
diff --git a/ofproto/ofproto-dpif-rid.c b/ofproto/ofproto-dpif-rid.c
index 236de4d..55d5c2b 100644
--- a/ofproto/ofproto-dpif-rid.c
+++ b/ofproto/ofproto-dpif-rid.c
@@ -16,46 +16,25 @@
#include <config.h>
-#include "hmap.h"
-#include "hash.h"
+#include "id-pool.h"
#include "ovs-thread.h"
#include "ofproto-dpif-rid.h"
-struct rid_node {
- struct hmap_node node;
- uint32_t recirc_id;
-};
-
-struct rid_pool {
- struct hmap map;
- uint32_t base; /* IDs in the range of [base, base + n_ids). */
- uint32_t n_ids; /* Total number of ids in the pool. */
- uint32_t next_free_id; /* Possible next free id. */
-};
-
struct recirc_id_pool {
struct ovs_mutex lock;
- struct rid_pool rids;
+ struct id_pool *rids;
};
#define RECIRC_ID_BASE 300
#define RECIRC_ID_N_IDS 1024
-static void rid_pool_init(struct rid_pool *rids,
- uint32_t base, uint32_t n_ids);
-static void rid_pool_uninit(struct rid_pool *pool);
-static uint32_t rid_pool_alloc_id(struct rid_pool *pool);
-static void rid_pool_free_id(struct rid_pool *rids, uint32_t rid);
-static struct rid_node *rid_pool_find(struct rid_pool *rids, uint32_t id);
-static void rid_pool_add(struct rid_pool *rids, uint32_t id);
-
struct recirc_id_pool *
recirc_id_pool_create(void)
{
struct recirc_id_pool *pool;
pool = xmalloc(sizeof *pool);
- rid_pool_init(&pool->rids, RECIRC_ID_BASE, RECIRC_ID_N_IDS);
+ pool->rids = id_pool_create(RECIRC_ID_BASE, RECIRC_ID_N_IDS);
ovs_mutex_init(&pool->lock);
return pool;
@@ -64,7 +43,7 @@ recirc_id_pool_create(void)
void
recirc_id_pool_destroy(struct recirc_id_pool *pool)
{
- rid_pool_uninit(&pool->rids);
+ id_pool_destroy(pool->rids);
ovs_mutex_destroy(&pool->lock);
free(pool);
}
@@ -75,7 +54,7 @@ recirc_id_alloc(struct recirc_id_pool *pool)
uint32_t id;
ovs_mutex_lock(&pool->lock);
- id = rid_pool_alloc_id(&pool->rids);
+ id = id_pool_alloc_id(pool->rids);
ovs_mutex_unlock(&pool->lock);
return id;
@@ -85,101 +64,6 @@ void
recirc_id_free(struct recirc_id_pool *pool, uint32_t id)
{
ovs_mutex_lock(&pool->lock);
- rid_pool_free_id(&pool->rids, id);
+ id_pool_free_id(pool->rids, id);
ovs_mutex_unlock(&pool->lock);
}
-
-static void
-rid_pool_init(struct rid_pool *rids, uint32_t base, uint32_t n_ids)
-{
- rids->base = base;
- rids->n_ids = n_ids;
- rids->next_free_id = base;
- hmap_init(&rids->map);
-}
-
-static void
-rid_pool_uninit(struct rid_pool *rids)
-{
- struct rid_node *rid, *next;
-
- HMAP_FOR_EACH_SAFE(rid, next, node, &rids->map) {
- hmap_remove(&rids->map, &rid->node);
- free(rid);
- }
-
- hmap_destroy(&rids->map);
-}
-
-static struct rid_node *
-rid_pool_find(struct rid_pool *rids, uint32_t id)
-{
- size_t hash;
- struct rid_node *rid;
-
- hash = hash_int(id, 0);
- HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &rids->map) {
- if (id == rid->recirc_id) {
- return rid;
- }
- }
- return NULL;
-}
-
-static void
-rid_pool_add(struct rid_pool *rids, uint32_t id)
-{
- struct rid_node *rid = xmalloc(sizeof *rid);
- size_t hash;
-
- rid->recirc_id = id;
- hash = hash_int(id, 0);
- hmap_insert(&rids->map, &rid->node, hash);
-}
-
-static uint32_t
-rid_pool_alloc_id(struct rid_pool *rids)
-{
- uint32_t id;
-
- if (rids->n_ids == 0) {
- return 0;
- }
-
- if (!(rid_pool_find(rids, rids->next_free_id))) {
- id = rids->next_free_id;
- goto found_free_id;
- }
-
- for(id = rids->base; id < rids->base + rids->n_ids; id++) {
- if (!rid_pool_find(rids, id)) {
- goto found_free_id;
- }
- }
-
- /* Not available. */
- return 0;
-
-found_free_id:
- rid_pool_add(rids, id);
-
- if (id < rids->base + rids->n_ids) {
- rids->next_free_id = id + 1;
- } else {
- rids->next_free_id = rids->base;
- }
-
- return id;
-}
-
-static void
-rid_pool_free_id(struct rid_pool *rids, uint32_t id)
-{
- struct rid_node *rid;
- if (id > rids->base && (id <= rids->base + rids->n_ids)) {
- rid = rid_pool_find(rids, id);
- if (rid) {
- hmap_remove(&rids->map, &rid->node);
- }
- }
-}
--
2.1.1
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
