id-pool: Re-factor recirculation id allocator into standalone id pool.

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)
OpenFlow 1.5 groups.

ONF-JIRA: EXT-350
Signed-off-by: Simon Horman <simon.horman@netronome.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

4 files changed, 203 insertions, 122 deletions

diff --git a/lib/automake.mk b/lib/automake.mk
index 1256af13f..40c0241a8 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 000000000..625cd52d8
--- /dev/null
+++ b/lib/id-pool.c
@@ -0,0 +1,151 @@
+/*
+ * 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 "id-pool.h"
+#include "hmap.h"
+#include "hash.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 000000000..a68b0a2e2
--- /dev/null
+++ b/lib/id-pool.h
@@ -0,0 +1,44 @@
+/*
+ * 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 *);
+uint32_t id_pool_alloc_id(struct id_pool *);
+void id_pool_free_id(struct id_pool *, uint32_t id);
+void id_pool_add(struct id_pool *, uint32_t id);
+
+/*
+ * ID pool.
+ * ========
+ *
+ * Pool of unique 32bit ids.
+ *
+ *
+ * Thread-safety
+ * =============
+ *
+ * APIs are not thread safe.
+ */
+#endif  /* id-pool.h */
diff --git a/ofproto/ofproto-dpif-rid.c b/ofproto/ofproto-dpif-rid.c
index 236de4d7f..55d5c2bef 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);
-        }
-    }
-}