[ovs-dev] [next 03/35] vlan-bitmap: New data structure.
Ben Pfaff
blp at nicira.com
Tue Apr 26 16:24:29 UTC 2011
---
lib/automake.mk | 2 +
lib/mac-learning.c | 8 ++----
lib/vlan-bitmap.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/vlan-bitmap.h | 40 ++++++++++++++++++++++++++++++++++
vswitchd/bridge.c | 44 ++++++--------------------------------
5 files changed, 112 insertions(+), 42 deletions(-)
create mode 100644 lib/vlan-bitmap.c
create mode 100644 lib/vlan-bitmap.h
diff --git a/lib/automake.mk b/lib/automake.mk
index 802cc99..c87ee5f 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -169,6 +169,8 @@ lib_libopenvswitch_a_SOURCES = \
lib/vconn-stream.c \
lib/vconn.c \
lib/vconn.h \
+ lib/vlan-bitmap.c \
+ lib/vlan-bitmap.h \
lib/vlog.c \
lib/vlog.h
nodist_lib_libopenvswitch_a_SOURCES = \
diff --git a/lib/mac-learning.c b/lib/mac-learning.c
index 42864ce..a57bbc7 100644
--- a/lib/mac-learning.c
+++ b/lib/mac-learning.c
@@ -29,6 +29,7 @@
#include "tag.h"
#include "timeval.h"
#include "util.h"
+#include "vlan-bitmap.h"
#include "vlog.h"
VLOG_DEFINE_THIS_MODULE(mac_learning);
@@ -143,10 +144,7 @@ mac_learning_destroy(struct mac_learning *ml)
bool
mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap)
{
- bool ret = (bitmap == NULL
- ? ml->flood_vlans != NULL
- : (ml->flood_vlans == NULL
- || !bitmap_equal(bitmap, ml->flood_vlans, 4096)));
+ bool ret = vlan_bitmap_equal(ml->flood_vlans, bitmap);
bitmap_free(ml->flood_vlans);
ml->flood_vlans = bitmap;
@@ -157,7 +155,7 @@ mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap)
static bool
is_learning_vlan(const struct mac_learning *ml, uint16_t vlan)
{
- return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan));
+ return vlan_bitmap_contains(ml->flood_vlans, vlan);
}
/* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'.
diff --git a/lib/vlan-bitmap.c b/lib/vlan-bitmap.c
new file mode 100644
index 0000000..94059c7
--- /dev/null
+++ b/lib/vlan-bitmap.c
@@ -0,0 +1,60 @@
+/* Copyright (c) 2011 Nicira Networks
+ *
+ * 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 "vlan-bitmap.h"
+
+/* Allocates and returns a new 4096-bit bitmap that has 1-bit in positions in
+ * the 'n_vlans' bits indicated in 'vlans' and 0-bits everywhere else. Returns
+ * a null pointer if there are no (valid) VLANs in 'vlans'. */
+unsigned long *
+vlan_bitmap_from_array(const int64_t *vlans, size_t n_vlans)
+{
+ unsigned long *b;
+ size_t i, n;
+
+ if (!n_vlans) {
+ return NULL;
+ }
+
+ b = bitmap_allocate(4096);
+ n = 0;
+ for (i = 0; i < n_vlans; i++) {
+ int64_t vlan = vlans[i];
+
+ if (vlan >= 0 && vlan < 4096) {
+ bitmap_set1(b, vlan);
+ n++;
+ }
+ }
+
+ if (!n) {
+ free(b);
+ return NULL;
+ }
+
+ return b;
+}
+
+/* Returns true if 'a' and 'b' are the same: either both null or both the same
+ * 4096-bit bitmap.
+ *
+ * (We assume that a nonnull bitmap is not all 0-bits.) */
+bool
+vlan_bitmap_equal(const unsigned long *a, const unsigned long *b)
+{
+ return (!a && !b) || (a && b && bitmap_equal(a, b, 4096));
+}
diff --git a/lib/vlan-bitmap.h b/lib/vlan-bitmap.h
new file mode 100644
index 0000000..eca42fe
--- /dev/null
+++ b/lib/vlan-bitmap.h
@@ -0,0 +1,40 @@
+/* Copyright (c) 2011 Nicira Networks
+ *
+ * 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 VLAN_BITMAP_H
+#define VLAN_BITMAP_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "bitmap.h"
+
+/* A "VLAN bitmap" is a 4096-bit bitmap that represents a set. A 1-bit
+ * indicates that the respective VLAN is a member of the set, a 0-bit indicates
+ * that it is not. There is one wrinkle: NULL indicates that every VLAN is a
+ * member of the set.
+ *
+ * This is empirically a useful data structure. */
+
+unsigned long *vlan_bitmap_from_array(const int64_t *vlans, size_t n_vlans);
+bool vlan_bitmap_equal(const unsigned long *a, const unsigned long *b);
+
+/* Returns true if 'vid', in the range [0,4095], is a member of 'vlans'. */
+static inline bool
+vlan_bitmap_contains(const unsigned long *vlans, uint16_t vid)
+{
+ return !vlans || bitmap_is_set(vlans, vid);
+}
+
+#endif /* lib/vlan-bitmap.h */
diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c
index eb10cf0..e3e5a4c 100644
--- a/vswitchd/bridge.c
+++ b/vswitchd/bridge.c
@@ -73,6 +73,7 @@
#include "xenserver.h"
#include "vlog.h"
#include "sflow_api.h"
+#include "vlan-bitmap.h"
VLOG_DEFINE_THIS_MODULE(bridge);
@@ -2225,8 +2226,7 @@ dst_is_duplicate(const struct dst_set *set, const struct dst *test)
static bool
port_trunks_vlan(const struct port *port, uint16_t vlan)
{
- return (port->vlan < 0
- && (!port->trunks || bitmap_is_set(port->trunks, vlan)));
+ return (port->vlan < 0 || vlan_bitmap_contains(port->trunks, vlan));
}
static bool
@@ -2980,35 +2980,16 @@ port_reconfigure(struct port *port, const struct ovsrec_port *cfg)
/* Get trunked VLANs. */
trunks = NULL;
if (vlan < 0 && cfg->n_trunks) {
- size_t n_errors;
-
- trunks = bitmap_allocate(4096);
- n_errors = 0;
- for (i = 0; i < cfg->n_trunks; i++) {
- int trunk = cfg->trunks[i];
- if (trunk >= 0) {
- bitmap_set1(trunks, trunk);
- } else {
- n_errors++;
- }
- }
- if (n_errors) {
- VLOG_ERR("port %s: invalid values for %zu trunk VLANs",
- port->name, cfg->n_trunks);
- }
- if (n_errors == cfg->n_trunks) {
+ trunks = vlan_bitmap_from_array(cfg->trunks, cfg->n_trunks);
+ if (!trunks) {
VLOG_ERR("port %s: no valid trunks, trunking all VLANs",
port->name);
- bitmap_free(trunks);
- trunks = NULL;
}
} else if (vlan >= 0 && cfg->n_trunks) {
VLOG_ERR("port %s: ignoring trunks in favor of implicit vlan",
port->name);
}
- if (trunks == NULL
- ? port->trunks != NULL
- : port->trunks == NULL || !bitmap_equal(trunks, port->trunks, 4096)) {
+ if (!vlan_bitmap_equal(trunks, port->trunks)) {
need_flush = true;
}
bitmap_free(port->trunks);
@@ -3633,19 +3614,8 @@ mirror_reconfigure(struct bridge *br)
/* Update flooded vlans (for RSPAN). */
rspan_vlans = NULL;
if (br->cfg->n_flood_vlans) {
- rspan_vlans = bitmap_allocate(4096);
-
- for (i = 0; i < br->cfg->n_flood_vlans; i++) {
- int64_t vlan = br->cfg->flood_vlans[i];
- if (vlan >= 0 && vlan < 4096) {
- bitmap_set1(rspan_vlans, vlan);
- VLOG_INFO("bridge %s: disabling learning on vlan %"PRId64,
- br->name, vlan);
- } else {
- VLOG_ERR("bridge %s: invalid value %"PRId64 "for flood VLAN",
- br->name, vlan);
- }
- }
+ rspan_vlans = vlan_bitmap_from_array(br->cfg->flood_vlans,
+ br->cfg->n_flood_vlans);
}
if (mac_learning_set_flood_vlans(br->ml, rspan_vlans)) {
bridge_flush(br);
--
1.7.4.4
More information about the dev
mailing list