From 0fb7b9156ac7d319a51890630857698ad1877335 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 8 Apr 2011 13:19:33 -0700 Subject: [PATCH] vlan-bitmap: New data structure. --- 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 802cc992..c87ee5f4 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 42864ce0..a57bbc75 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 00000000..94059c75 --- /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 + +#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 00000000..eca42fea --- /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 +#include +#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 eb10cf0a..e3e5a4c7 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); -- 2.30.2