[ovs-dev] [next 03/35] vlan-bitmap: New data structure.
Ethan Jackson
ethan at nicira.com
Mon May 2 17:54:24 UTC 2011
Looks Good.
Ethan
On Tue, Apr 26, 2011 at 09:24, Ben Pfaff <blp at nicira.com> wrote:
> ---
> 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
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
>
More information about the dev
mailing list