[ovs-dev] [prelearning 1/5] packets: Add more utility functions for IPv4 and IPv6 addresses.
Ethan Jackson
ethan at nicira.com
Wed Aug 17 20:12:25 UTC 2011
Looks fine to me.
Ethan
On Wed, Aug 17, 2011 at 10:59, Ben Pfaff <blp at nicira.com> wrote:
> On Tue, Aug 16, 2011 at 05:41:46PM -0700, Ethan Jackson wrote:
>> I would be inclined to implement a "clz" function similar to what
>> log_2_floor() does in util. We could use it both for log_2_floor()
>> and ip_count_cidr_bits(). That way we would only have to deal with
>> the ugly GNUC ifdefing in one place.
>
> It's a good idea, but ip_count_cidr_bits() actually wants ctz(), not
> clz().
>
> Here's a revised version.
>
> --8<--------------------------cut here-------------------------->8--
>
> From: Ben Pfaff <blp at nicira.com>
> Date: Wed, 17 Aug 2011 10:55:15 -0700
> Subject: [PATCH] packets: Add more utility functions for IPv4 and IPv6
> addresses.
>
> We had these functions scattered around the source tree anyway. packets.h
> is a good place to centralize them.
>
> I do plan to introduce some additional callers.
> ---
> lib/classifier.c | 22 ++------------------
> lib/ofp-util.c | 16 ++------------
> lib/packets.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++-----
> lib/packets.h | 4 +++
> lib/util.c | 33 +++++++++++++++++++++++++++++++
> lib/util.h | 3 +-
> tests/test-util.c | 31 ++++++++++++++++++++++++-----
> 7 files changed, 119 insertions(+), 45 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c
> index d1f9d5d..9c71b85 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -421,15 +421,8 @@ format_ip_netmask(struct ds *s, const char *name, ovs_be32 ip,
> ovs_be32 netmask)
> {
> if (netmask) {
> - ds_put_format(s, "%s="IP_FMT, name, IP_ARGS(&ip));
> - if (netmask != htonl(UINT32_MAX)) {
> - if (ip_is_cidr(netmask)) {
> - int wcbits = ofputil_netmask_to_wcbits(netmask);
> - ds_put_format(s, "/%d", 32 - wcbits);
> - } else {
> - ds_put_format(s, "/"IP_FMT, IP_ARGS(&netmask));
> - }
> - }
> + ds_put_format(s, "%s=", name);
> + ip_format_masked(ip, netmask, s);
> ds_put_char(s, ',');
> }
> }
> @@ -441,16 +434,7 @@ format_ipv6_netmask(struct ds *s, const char *name,
> {
> if (!ipv6_mask_is_any(netmask)) {
> ds_put_format(s, "%s=", name);
> - print_ipv6_addr(s, addr);
> - if (!ipv6_mask_is_exact(netmask)) {
> - if (ipv6_is_cidr(netmask)) {
> - int cidr_bits = ipv6_count_cidr_bits(netmask);
> - ds_put_format(s, "/%d", cidr_bits);
> - } else {
> - ds_put_char(s, '/');
> - print_ipv6_addr(s, netmask);
> - }
> - }
> + print_ipv6_masked(s, addr, netmask);
> ds_put_char(s, ',');
> }
> }
> diff --git a/lib/ofp-util.c b/lib/ofp-util.c
> index b0e7405..cdb12e6 100644
> --- a/lib/ofp-util.c
> +++ b/lib/ofp-util.c
> @@ -59,22 +59,12 @@ ofputil_wcbits_to_netmask(int wcbits)
> }
>
> /* Given the IP netmask 'netmask', returns the number of bits of the IP address
> - * that it wildcards. 'netmask' must be a CIDR netmask (see ip_is_cidr()). */
> + * that it wildcards, that is, the number of 0-bits in 'netmask'. 'netmask'
> + * must be a CIDR netmask (see ip_is_cidr()). */
> int
> ofputil_netmask_to_wcbits(ovs_be32 netmask)
> {
> - assert(ip_is_cidr(netmask));
> -#if __GNUC__ >= 4
> - return netmask == htonl(0) ? 32 : __builtin_ctz(ntohl(netmask));
> -#else
> - int wcbits;
> -
> - for (wcbits = 32; netmask; wcbits--) {
> - netmask &= netmask - 1;
> - }
> -
> - return wcbits;
> -#endif
> + return 32 - ip_count_cidr_bits(netmask);
> }
>
> /* A list of the FWW_* and OFPFW_ bits that have the same value, meaning, and
> diff --git a/lib/packets.c b/lib/packets.c
> index e05e3eb..881ef45 100644
> --- a/lib/packets.c
> +++ b/lib/packets.c
> @@ -105,6 +105,30 @@ eth_set_vlan_tci(struct ofpbuf *packet, ovs_be16 tci)
> packet->l2 = packet->data;
> }
>
> +/* Given the IP netmask 'netmask', returns the number of bits of the IP address
> + * that it specifies, that is, the number of 1-bits in 'netmask'. 'netmask'
> + * must be a CIDR netmask (see ip_is_cidr()). */
> +int
> +ip_count_cidr_bits(ovs_be32 netmask)
> +{
> + assert(ip_is_cidr(netmask));
> + return 32 - ctz(ntohl(netmask));
> +}
> +
> +void
> +ip_format_masked(ovs_be32 ip, ovs_be32 mask, struct ds *s)
> +{
> + ds_put_format(s, IP_FMT, IP_ARGS(&ip));
> + if (mask != htonl(UINT32_MAX)) {
> + if (ip_is_cidr(mask)) {
> + ds_put_format(s, "/%d", ip_count_cidr_bits(mask));
> + } else {
> + ds_put_format(s, "/"IP_FMT, IP_ARGS(&mask));
> + }
> + }
> +}
> +
> +
> /* Stores the string representation of the IPv6 address 'addr' into the
> * character array 'addr_str', which must be at least INET6_ADDRSTRLEN
> * bytes long. */
> @@ -117,10 +141,29 @@ format_ipv6_addr(char *addr_str, const struct in6_addr *addr)
> void
> print_ipv6_addr(struct ds *string, const struct in6_addr *addr)
> {
> - char addr_str[INET6_ADDRSTRLEN];
> + char *dst;
> +
> + ds_reserve(string, string->length + INET6_ADDRSTRLEN);
> +
> + dst = string->string + string->length;
> + format_ipv6_addr(dst, addr);
> + string->length += strlen(dst);
> +}
>
> - format_ipv6_addr(addr_str, addr);
> - ds_put_format(string, "%s", addr_str);
> +void
> +print_ipv6_masked(struct ds *s, const struct in6_addr *addr,
> + const struct in6_addr *mask)
> +{
> + print_ipv6_addr(s, addr);
> + if (mask && !ipv6_mask_is_exact(mask)) {
> + if (ipv6_is_cidr(mask)) {
> + int cidr_bits = ipv6_count_cidr_bits(mask);
> + ds_put_format(s, "/%d", cidr_bits);
> + } else {
> + ds_put_char(s, '/');
> + print_ipv6_addr(s, mask);
> + }
> + }
> }
>
> struct in6_addr ipv6_addr_bitand(const struct in6_addr *a,
> @@ -164,9 +207,9 @@ ipv6_create_mask(int mask)
> return netmask;
> }
>
> -/* Given the IPv6 netmask 'netmask', returns the number of bits of the
> - * IPv6 address that it wildcards. 'netmask' must be a CIDR netmask (see
> - * ipv6_is_cidr()). */
> +/* Given the IPv6 netmask 'netmask', returns the number of bits of the IPv6
> + * address that it specifies, that is, the number of 1-bits in 'netmask'.
> + * 'netmask' must be a CIDR netmask (see ipv6_is_cidr()). */
> int
> ipv6_count_cidr_bits(const struct in6_addr *netmask)
> {
> diff --git a/lib/packets.h b/lib/packets.h
> index a389e6a..304cd9d 100644
> --- a/lib/packets.h
> +++ b/lib/packets.h
> @@ -291,6 +291,8 @@ ip_is_cidr(ovs_be32 netmask)
> uint32_t x = ~ntohl(netmask);
> return !(x & (x + 1));
> }
> +int ip_count_cidr_bits(ovs_be32 netmask);
> +void ip_format_masked(ovs_be32 ip, ovs_be32 mask, struct ds *);
>
> #define IP_VER(ip_ihl_ver) ((ip_ihl_ver) >> 4)
> #define IP_IHL(ip_ihl_ver) ((ip_ihl_ver) & 15)
> @@ -423,6 +425,8 @@ static inline bool ipv6_mask_is_exact(const struct in6_addr *mask) {
>
> void format_ipv6_addr(char *addr_str, const struct in6_addr *addr);
> void print_ipv6_addr(struct ds *string, const struct in6_addr *addr);
> +void print_ipv6_masked(struct ds *string, const struct in6_addr *addr,
> + const struct in6_addr *mask);
> struct in6_addr ipv6_addr_bitand(const struct in6_addr *src,
> const struct in6_addr *mask);
> struct in6_addr ipv6_create_mask(int mask);
> diff --git a/lib/util.c b/lib/util.c
> index e6d57da..5e90ecb 100644
> --- a/lib/util.c
> +++ b/lib/util.c
> @@ -663,3 +663,36 @@ log_2_floor(uint32_t n)
> }
> #endif
> }
> +
> +/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
> +int
> +ctz(uint32_t n)
> +{
> + if (!n) {
> + return 32;
> + } else {
> +#if !defined(UINT_MAX) || !defined(UINT32_MAX)
> +#error "Someone screwed up the #includes."
> +#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
> + return __builtin_ctz(n);
> +#else
> + unsigned int k;
> + int count = 31;
> +
> +#define CTZ_STEP(X) \
> + k = n << (X); \
> + if (k) { \
> + count -= X; \
> + n = k; \
> + }
> + CTZ_STEP(16);
> + CTZ_STEP(8);
> + CTZ_STEP(4);
> + CTZ_STEP(2);
> + CTZ_STEP(1);
> +#undef CTZ_STEP
> +
> + return count;
> +#endif
> + }
> +}
> diff --git a/lib/util.h b/lib/util.h
> index 1649c59..5c8618d 100644
> --- a/lib/util.h
> +++ b/lib/util.h
> @@ -194,7 +194,8 @@ char *base_name(const char *file_name);
> char *abs_file_name(const char *dir, const char *file_name);
>
> void ignore(bool x OVS_UNUSED);
> -int log_2_floor(uint32_t n);
> +int log_2_floor(uint32_t);
> +int ctz(uint32_t);
>
> #ifdef __cplusplus
> }
> diff --git a/tests/test-util.c b/tests/test-util.c
> index e9a827a..bc4af23 100644
> --- a/tests/test-util.c
> +++ b/tests/test-util.c
> @@ -17,6 +17,7 @@
> #include <config.h>
>
> #include <inttypes.h>
> +#include <limits.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> @@ -24,7 +25,7 @@
> #include "util.h"
>
> static void
> -check(uint32_t x, int n)
> +check_log_2_floor(uint32_t x, int n)
> {
> if (log_2_floor(x) != n) {
> fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n",
> @@ -33,20 +34,38 @@ check(uint32_t x, int n)
> }
> }
>
> +static void
> +check_ctz(uint32_t x, int n)
> +{
> + if (ctz(x) != n) {
> + fprintf(stderr, "ctz(%"PRIu32") is %d but should be %d\n",
> + x, ctz(x), n);
> + abort();
> + }
> +}
> +
> int
> main(void)
> {
> int n;
>
> for (n = 0; n < 32; n++) {
> - /* Check minimum x that has log2(x) == n. */
> - check(1 << n, n);
> + /* Check minimum x such that f(x) == n. */
> + check_log_2_floor(1 << n, n);
> + check_ctz(1 << n, n);
>
> - /* Check maximum x that has log2(x) == n. */
> - check((1 << n) | ((1 << n) - 1), n);
> + /* Check maximum x such that f(x) == n. */
> + check_log_2_floor((1 << n) | ((1 << n) - 1), n);
> + check_ctz(UINT32_MAX << n, n);
>
> /* Check a random value in the middle. */
> - check((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
> + check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
> + check_ctz((random_uint32() | 1) << n, n);
> }
> +
> + /* Check ctz(0).
> + * (log_2_floor(0) is undefined.) */
> + check_ctz(0, 32);
> +
> return 0;
> }
> --
> 1.7.4.4
>
>
More information about the dev
mailing list