[ovs-dev] [threaded-learning 12/25] guarded-list: New data structure for thread-safe queue.
Ben Pfaff
blp at nicira.com
Wed Sep 11 05:27:12 UTC 2013
We already had two queues that were suitable for replacement by this data
structure, and I intend to add another one later on.
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
lib/automake.mk | 2 ++
lib/guarded-list.c | 65 +++++++++++++++++++++++++++++++++++++++++++
lib/guarded-list.h | 36 ++++++++++++++++++++++++
ofproto/ofproto-dpif.c | 72 +++++++++++-------------------------------------
4 files changed, 119 insertions(+), 56 deletions(-)
create mode 100644 lib/guarded-list.c
create mode 100644 lib/guarded-list.h
diff --git a/lib/automake.mk b/lib/automake.mk
index da1896a..92cfc13 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -58,6 +58,8 @@ lib_libopenvswitch_a_SOURCES = \
lib/fatal-signal.h \
lib/flow.c \
lib/flow.h \
+ lib/guarded-list.c \
+ lib/guarded-list.h \
lib/hash.c \
lib/hash.h \
lib/hindex.c \
diff --git a/lib/guarded-list.c b/lib/guarded-list.c
new file mode 100644
index 0000000..a79c294
--- /dev/null
+++ b/lib/guarded-list.c
@@ -0,0 +1,65 @@
+/*
+ * Copyright (c) 2013 Nicira, Inc.
+ *
+ * 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 "guarded-list.h"
+
+void
+guarded_list_init(struct guarded_list *list)
+{
+ ovs_mutex_init(&list->mutex);
+ list_init(&list->list);
+ list->n = 0;
+}
+
+void
+guarded_list_destroy(struct guarded_list *list)
+{
+ ovs_mutex_destroy(&list->mutex);
+}
+
+bool
+guarded_list_append(struct guarded_list *list, struct list *node, size_t max)
+{
+ bool add;
+
+ ovs_mutex_lock(&list->mutex);
+ add = list->n < max;
+ if (add) {
+ list_push_back(&list->list, node);
+ list->n++;
+ }
+ ovs_mutex_unlock(&list->mutex);
+
+ return add;
+}
+
+size_t
+guarded_list_steal_all(struct guarded_list *list, struct list *elements)
+{
+ size_t n;
+
+ ovs_mutex_lock(&list->mutex);
+ list_move(elements, &list->list);
+ n = list->n;
+
+ list_init(&list->list);
+ list->n = 0;
+ ovs_mutex_unlock(&list->mutex);
+
+ return n;
+}
diff --git a/lib/guarded-list.h b/lib/guarded-list.h
new file mode 100644
index 0000000..d31fdb8
--- /dev/null
+++ b/lib/guarded-list.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (c) 2013 Nicira, Inc.
+ *
+ * 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 GUARDED_LIST_H
+#define GUARDED_LIST_H 1
+
+#include <stddef.h>
+#include "list.h"
+#include "ovs-thread.h"
+
+struct guarded_list {
+ struct ovs_mutex mutex;
+ struct list list;
+ size_t n;
+};
+
+void guarded_list_init(struct guarded_list *);
+void guarded_list_destroy(struct guarded_list *);
+
+bool guarded_list_append(struct guarded_list *, struct list *, size_t max);
+size_t guarded_list_steal_all(struct guarded_list *, struct list *);
+
+#endif /* guarded-list.h */
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 2b2fe62..eab5533 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -31,6 +31,7 @@
#include "dpif.h"
#include "dynamic-string.h"
#include "fail-open.h"
+#include "guarded-list.h"
#include "hmapx.h"
#include "lacp.h"
#include "learn.h"
@@ -507,13 +508,8 @@ struct ofproto_dpif {
uint64_t n_missed;
/* Work queues. */
- struct ovs_mutex flow_mod_mutex;
- struct list flow_mods OVS_GUARDED;
- size_t n_flow_mods OVS_GUARDED;
-
- struct ovs_mutex pin_mutex;
- struct list pins OVS_GUARDED;
- size_t n_pins OVS_GUARDED;
+ struct guarded_list flow_mods; /* Contains "struct flow_mod"s. */
+ struct guarded_list pins; /* Contains "struct ofputil_packet_in"s. */
};
/* By default, flows in the datapath are wildcarded (megaflows). They
@@ -560,18 +556,11 @@ void
ofproto_dpif_flow_mod(struct ofproto_dpif *ofproto,
struct ofputil_flow_mod *fm)
{
- ovs_mutex_lock(&ofproto->flow_mod_mutex);
- if (ofproto->n_flow_mods > 1024) {
- ovs_mutex_unlock(&ofproto->flow_mod_mutex);
+ if (!guarded_list_append(&ofproto->flow_mods, &fm->list_node, 1024)) {
COVERAGE_INC(flow_mod_overflow);
free(fm->ofpacts);
free(fm);
- return;
}
-
- list_push_back(&ofproto->flow_mods, &fm->list_node);
- ofproto->n_flow_mods++;
- ovs_mutex_unlock(&ofproto->flow_mod_mutex);
}
/* Appends 'pin' to the queue of "packet ins" to be sent to the controller.
@@ -580,18 +569,11 @@ void
ofproto_dpif_send_packet_in(struct ofproto_dpif *ofproto,
struct ofputil_packet_in *pin)
{
- ovs_mutex_lock(&ofproto->pin_mutex);
- if (ofproto->n_pins > 1024) {
- ovs_mutex_unlock(&ofproto->pin_mutex);
+ if (!guarded_list_append(&ofproto->pins, &pin->list_node, 1024)) {
COVERAGE_INC(packet_in_overflow);
free(CONST_CAST(void *, pin->packet));
free(pin);
- return;
}
-
- list_push_back(&ofproto->pins, &pin->list_node);
- ofproto->n_pins++;
- ovs_mutex_unlock(&ofproto->pin_mutex);
}
/* Factory functions. */
@@ -1286,17 +1268,8 @@ construct(struct ofproto *ofproto_)
classifier_init(&ofproto->facets);
ofproto->consistency_rl = LLONG_MIN;
- ovs_mutex_init(&ofproto->flow_mod_mutex);
- ovs_mutex_lock(&ofproto->flow_mod_mutex);
- list_init(&ofproto->flow_mods);
- ofproto->n_flow_mods = 0;
- ovs_mutex_unlock(&ofproto->flow_mod_mutex);
-
- ovs_mutex_init(&ofproto->pin_mutex);
- ovs_mutex_lock(&ofproto->pin_mutex);
- list_init(&ofproto->pins);
- ofproto->n_pins = 0;
- ovs_mutex_unlock(&ofproto->pin_mutex);
+ guarded_list_init(&ofproto->flow_mods);
+ guarded_list_init(&ofproto->pins);
ofproto_dpif_unixctl_init();
@@ -1422,6 +1395,7 @@ destruct(struct ofproto *ofproto_)
struct ofputil_packet_in *pin, *next_pin;
struct ofputil_flow_mod *fm, *next_fm;
struct facet *facet, *next_facet;
+ struct list flow_mods, pins;
struct cls_cursor cursor;
struct oftable *table;
@@ -1452,25 +1426,21 @@ destruct(struct ofproto *ofproto_)
ovs_rwlock_unlock(&table->cls.rwlock);
}
- ovs_mutex_lock(&ofproto->flow_mod_mutex);
- LIST_FOR_EACH_SAFE (fm, next_fm, list_node, &ofproto->flow_mods) {
+ guarded_list_steal_all(&ofproto->flow_mods, &flow_mods);
+ LIST_FOR_EACH_SAFE (fm, next_fm, list_node, &flow_mods) {
list_remove(&fm->list_node);
- ofproto->n_flow_mods--;
free(fm->ofpacts);
free(fm);
}
- ovs_mutex_unlock(&ofproto->flow_mod_mutex);
- ovs_mutex_destroy(&ofproto->flow_mod_mutex);
+ guarded_list_destroy(&ofproto->flow_mods);
- ovs_mutex_lock(&ofproto->pin_mutex);
- LIST_FOR_EACH_SAFE (pin, next_pin, list_node, &ofproto->pins) {
+ guarded_list_steal_all(&ofproto->pins, &pins);
+ LIST_FOR_EACH_SAFE (pin, next_pin, list_node, &pins) {
list_remove(&pin->list_node);
- ofproto->n_pins--;
free(CONST_CAST(void *, pin->packet));
free(pin);
}
- ovs_mutex_unlock(&ofproto->pin_mutex);
- ovs_mutex_destroy(&ofproto->pin_mutex);
+ guarded_list_destroy(&ofproto->pins);
mbridge_unref(ofproto->mbridge);
@@ -1508,12 +1478,7 @@ run_fast(struct ofproto *ofproto_)
return 0;
}
- ovs_mutex_lock(&ofproto->flow_mod_mutex);
- list_move(&flow_mods, &ofproto->flow_mods);
- list_init(&ofproto->flow_mods);
- ofproto->n_flow_mods = 0;
- ovs_mutex_unlock(&ofproto->flow_mod_mutex);
-
+ guarded_list_steal_all(&ofproto->flow_mods, &flow_mods);
LIST_FOR_EACH_SAFE (fm, next_fm, list_node, &flow_mods) {
int error = ofproto_flow_mod(&ofproto->up, fm);
if (error && !VLOG_DROP_WARN(&rl)) {
@@ -1526,12 +1491,7 @@ run_fast(struct ofproto *ofproto_)
free(fm);
}
- ovs_mutex_lock(&ofproto->pin_mutex);
- list_move(&pins, &ofproto->pins);
- list_init(&ofproto->pins);
- ofproto->n_pins = 0;
- ovs_mutex_unlock(&ofproto->pin_mutex);
-
+ guarded_list_steal_all(&ofproto->pins, &pins);
LIST_FOR_EACH_SAFE (pin, next_pin, list_node, &pins) {
connmgr_send_packet_in(ofproto->up.connmgr, pin);
list_remove(&pin->list_node);
--
1.7.10.4
More information about the dev
mailing list