# BFD module {#bfd_doc}
## Overview
Bidirectional Forwarding Detection in VPP currently supports single-hop UDP
transport based on RFC 5880 and RFC 5881.
## Usage
### General usage
BFD sessions are created using APIs only. The following CLIs are implemented,
which call the APIs to manipulate the BFD:
#### Show commands:
> show bfd [keys|sessions|echo-source]
Show the existing keys, sessions or echo-source.
#### Key manipulation
##### Create a new key or modify an existing key
> bfd key set conf-key-id <id> type <keyed-sha1|meticulous-keyed-sha1> secret <secret>
Parameters:
* conf-key-id - local configuration key ID, used to uniquely identify this key
* type - type of the key
* secret - shared secret (hex data)
Example:
> bfd key set conf-key-id 2368880803 type meticulous-keyed-sha1 secret 69d685b0d990cdba46872706dc
Notes:
* in-use key cannot be modified
##### Delete an existing key
> bfd key del conf-key-id <id>
Parameters:
* conf-key-id - local configuration key ID, used to uniquely identify this key
Example:
> bfd key del conf-key-id 2368880803
Notes:
* in-use key cannot be deleted
##### Create a new (plain or authenticated) BFD session
> bfd udp session add interface <interface> local-addr <address> peer-addr <address> desired-min-tx <interval> required-min-rx <interval> detect-mult <multiplier> [ conf-key-id <ID> bfd-key-id <ID> ]
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
* desired-min-tx - desired minimum tx interval (microseconds)
* required-min-rx - required minimum rx interval (microseconds)
* detect-mult - detect multiplier (must be non-zero)
* conf-key-id - local configuration key ID
* bfd-key-id - BFD key ID, as carried in BFD control frames
Example:
> bfd udp session add interface pg0 local-addr fd01:1::1 peer-addr fd01:1::2 desired-min-tx 100000 required-min-rx 100000 detect-mult 3 conf-key-id 1029559112 bfd-key-id 13
Notes:
* if conf-key-id and bfd-key-id are not specified, session is non-authenticated
* desired-min-tx controls desired transmission rate of both control frames and echo packets
##### Modify BFD session
> bfd udp session mod interface <interface> local-addr <address> peer-addr <address> desired-min-tx <interval> required-min-rx <interval> detect-mult <multiplier>
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
* desired-min-tx - desired minimum tx interval (microseconds)
* required-min-rx - required minimum rx interval (microseconds)
* detect-mult - detect multiplier (must be non-zero)
Example:
> bfd udp session mod interface pg0 local-addr 172.16.1.1 peer-addr 172.16.1.2 desired-min-tx 300000 required-min-rx 200000 detect-mult 12
Notes:
* desired-min-tx controls desired transmission rate of both control frames and echo packets
##### Delete an existing BFD session
> bfd udp session del interface <interface> local-addr <address> peer-addr<address>
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
Example:
> bfd udp session del interface pg0 local-addr 172.16.1.1 peer-addr 172.16.1.2
##### Set session admin-up or admin-down
> bfd udp session set-flags interface <interface> local-addr <address> peer-addr <address> admin <up|down>
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
* admin - up/down based on desired action
Example:
> bfd udp session set-flags admin down interface pg0 local-addr 172.16.1.1 peer-addr 172.16.1.2
##### Activate/change authentication for existing session
> bfd udp session auth activate interface <interface> local-addr <address> peer-addr <address> conf-key-id <ID> bfd-key-id <ID> [ delayed <yes|no> ]
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
* conf-key-id - local configuration key ID
* bfd-key-id - BFD key ID, as carried in BFD control frames
* delayed - is yes then this action is delayed until the peer performs the same action
Example:
> bfd udp session auth activate interface pg0 local-addr 172.16.1.1 peer-addr 172.16.1.2 conf-key-id 540928695 bfd-key-id 239 delayed yes
Notes:
* see [Delayed option] for more information
##### Deactivate authentication for existing session
> bfd udp session auth deactivate interface <interface> local-addr <address> peer-addr <address> [ delayed <yes|no> ]
Parameters:
* interface - interface to which this session is tied to
* local-addr - local address (ipv4 or ipv6)
* peer-addr - peer address (ipv4 or ipv6, must match local-addr family)
* delayed - is yes then this action is delayed until the peer performs the same action
Example:
> bfd udp session auth deactivate interface pg0 local-addr 172.16.1.1 peer-addr 172.16.1.2
Notes:
* see [Delayed option] for more information
###/*
* Copyright (c) 2015 Cisco and/or its affiliates.
* 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.
*/
/*
Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef included_clib_bitmap_h
#define included_clib_bitmap_h
/** \file
Bitmaps built as vectors of machine words
*/
#include <vppinfra/vec.h>
#include <vppinfra/random.h>
#include <vppinfra/error.h>
#include <vppinfra/bitops.h> /* for count_set_bits */
typedef uword clib_bitmap_t;
/** predicate function; is an entire bitmap empty?
@param ai - pointer to a bitmap
@returns 1 if the entire bitmap is zero, 0 otherwise
*/
always_inline uword
clib_bitmap_is_zero (uword * ai)
{
uword i;
for (i = 0; i < vec_len (ai); i++)
if (ai[i] != 0)
return 0;
return 1;
}
/** predicate function; are two bitmaps equal?
@param a - pointer to a bitmap
@param b - pointer to a bitmap
@returns 1 if the bitmaps are equal, 0 otherwise
*/
always_inline uword
clib_bitmap_is_equal (uword * a, uword * b)
{
uword i;
if (vec_len (a) != vec_len (b))
return 0;
for (i = 0; i < vec_len (a); i++)
if (a[i] != b[i])
return 0;
return 1;
}
/** Duplicate a bitmap
@param v - pointer to a bitmap
@returns a duplicate of the bitmap
*/
#define clib_bitmap_dup(v) vec_dup(v)
/** Free a bitmap
@param v - pointer to the bitmap to free
*/
#define clib_bitmap_free(v) vec_free(v)
/** Number of bytes in a bitmap
@param v - pointer to the bitmap
*/
#define clib_bitmap_bytes(v) vec_bytes(v)
/** Clear a bitmap
@param v - pointer to the bitmap to clear
*/
#define clib_bitmap_zero(v) vec_zero(v)
/** Allocate a bitmap with the supplied number of bits
@param [out] v - the resulting bitmap
@param n_bits - the required number of bits
*/
#define clib_bitmap_alloc(v,n_bits) \
v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
#define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
/* Make sure that a bitmap is at least n_bits in size */
#define clib_bitmap_validate(v,n_bits) \
clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
/* low-level routine to remove trailing zeros from a bitmap */
always_inline uword *
_clib_bitmap_remove_trailing_zeros (uword * a)
{
word i;
if (a)
{
for (i = _vec_len (a) - 1; i >= 0; i--)
if (a[i] != 0)
break;
_vec_len (a) = i + 1;
}
return a;
}
/** Sets the ith bit of a bitmap to new_value.
No sanity checking. Be careful.
@param a - pointer to the bitmap
@param i - the bit position to interrogate
@param new_value - new value for the bit
@returns the old value of the bit
*/
always_inline uword
clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
{
uword i0 = i / BITS (a[0]);
uword i1 = i % BITS (a[0]);
uword bit = (uword) 1 << i1;
uword ai, old_value;
/* Removed ASSERT since uword * a may not be a vector. */
/* ASSERT (i0 < vec_len (a)); */
ai = a[i0];
old_value = (ai & bit) != 0;
ai &= ~bit;
ai |= ((uword) (new_value != 0)) << i1;
a[i0] = ai;
return old_value;
}
/** Sets the ith bit of a bitmap to new_value
Removes trailing zeros from the bitmap
@param ai - pointer to the bitmap
@param i - the bit position to interrogate
@param value - new value for the bit
@returns the old value of the bit
*/
always_inline uword *
clib_bitmap_set (uword * ai, uword i, uword value)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
uword a;
/* Check for writing a zero to beyond end of bitmap. */
if (value == 0 && i0 >= vec_len (ai))
return ai; /* Implied trailing zeros. */
clib_bitmap_vec_validate (ai, i0);
a = ai[i0];
a &= ~((uword) 1 << i1);
a |= ((uword) (value != 0)) << i1;
ai[i0] = a;
/* If bits have been cleared, test for zero. */
if (a == 0)
ai = _clib_bitmap_remove_trailing_zeros (ai);
return ai;
}
/** Gets the ith bit value from a bitmap
@param ai - pointer to the bitmap
@param i - the bit position to interrogate
@returns the indicated bit value
*/
always_inline uword
clib_bitmap_get (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
}
/** Gets the ith bit value from a bitmap
Does not sanity-check the bit position. Be careful.
@param ai - pointer to the bitmap
@param i - the bit position to interrogate
@returns the indicated bit value, or garbage if the bit position is
out of range.
*/
always_inline uword
clib_bitmap_get_no_check (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
return 0 != ((ai[i0] >> i1) & 1);
}
always_inline uword
clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
ASSERT (i1 + n_bits <= BITS (uword));
return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
}
/** Gets the ith through ith + n_bits bit values from a bitmap
@param bitmap - pointer to the bitmap
@param i - the first bit position to retrieve
@param n_bits - the number of bit positions to retrieve
@returns the indicated range of bits
*/
always_inline uword
clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
{
uword i0, i1, result;
uword l = vec_len (bitmap);
ASSERT (n_bits <= BITS (result));
i0 = i / BITS (bitmap[0]);
i1 = i % BITS (bitmap[0]);
/* Check first word. */
result = 0;
if (i0 < l)
{
result |= (bitmap[i0] >> i1);
if (n_bits < BITS (bitmap[0]))
result &= (((uword) 1 << n_bits) - 1);
}
/* Check for overlap into next word. */
i0++;
if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
{
n_bits -= BITS (bitmap[0]) - i1;
result |=
(bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
}
return result;
}
/** sets the ith through ith + n_bits bits in a bitmap
@param bitmap - pointer to the bitmap
@param i - the first bit position to retrieve
@param value - the values to set
@param n_bits - the number of bit positions to set
@returns a pointer to the updated bitmap, which may expand and move
*/
always_inline uword *
clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
{
uword i0, i1, l, t, m;
ASSERT (n_bits <= BITS (value));
i0 = i / BITS (bitmap[0]);
i1 = i % BITS (bitmap[0]);
/* Allocate bitmap. */
clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
l = vec_len (bitmap);
m = ~0;
if (n_bits < BITS (value))
m = (((uword) 1 << n_bits) - 1);
value &= m;
/* Insert into first word. */
t = bitmap[i0];
t &= ~(m << i1);
t |= value << i1;
bitmap[i0] = t;
/* Insert into second word. */
i0++;
if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
{
t = BITS (bitmap[0]) - i1;
value >>= t;
n_bits -= t;
t = bitmap[i0];
m = ((uword) 1 << n_bits) - 1;
t &= ~m;
t |= value;
bitmap[i0] = t;
}
return bitmap;
}
always_inline uword *
clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
{
uword a0, a1, b0;
uword i_end, mask;
a0 = i / BITS (bitmap[0]);
a1 = i % BITS (bitmap[0]);
i_end = i + n_bits;
b0 = i_end / BITS (bitmap[0]);
clib_bitmap_vec_validate (bitmap, b0);
/* First word. */
mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
mask <<= a1;
if (value)
bitmap[a0] |= mask;
else
bitmap[a0] &= ~mask;
for (a0++; a0 < b0; a0++)
bitmap[a0] = value ? ~0 : 0;
if (a0 == b0)
{
word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
mask = pow2_mask (n_bits_left);
if (value)
bitmap[a0] |= mask;
else
bitmap[a0] &= ~mask;
}
return bitmap;
}
/** Macro to iterate across set bits in a bitmap
@param i - the current set bit
@param ai - the bitmap
@param body - the expression to evaluate for each set bit
*/
#define clib_bitmap_foreach(i,ai,body) \
do { \
uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \
__bitmap_len = vec_len ((ai)); \
for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \
{ \
__bitmap_ai = (ai)[__bitmap_i]; \
while (__bitmap_ai != 0) \
{ \
__bitmap_first_set = first_set (__bitmap_ai); \
(i) = (__bitmap_i * BITS ((ai)[0]) \
+ min_log2 (__bitmap_first_set)); \
do { body; } while (0); \
__bitmap_ai ^= __bitmap_first_set; \
} \
} \
} while (0)
/** Return the lowest numbered set bit in a bitmap
@param ai - pointer to the bitmap
@returns lowest numbered set bit, or ~0 if the entire bitmap is zero
*/
always_inline uword
clib_bitmap_first_set (uword * ai)
{
uword i = 0;
#if uword_bits == 64
#if defined(CLIB_HAVE_VEC256)
while (i + 7 < vec_len (ai))
{
u64x4 v;
v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
if (!u64x4_is_all_zero (v))
break;
i += 8;
}
#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
while (i + 3 < vec_len (ai))
{
u64x2 v;
v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
if (!u64x2_is_all_zero (v))
break;
i += 4;
}
#endif
#endif
for (; i < vec_len (ai); i++)
{
uword x = ai[i];
if (x != 0)
return i * BITS (ai[0]) + log2_first_set (x);
}
return ~0;
}
/** Return the higest numbered set bit in a bitmap
@param ai - pointer to the bitmap
@returns lowest numbered set bit, or ~0 if the entire bitmap is zero
*/
always_inline uword
clib_bitmap_last_set (uword * ai)
{
uword i;
for (i = vec_len (ai); i > 0; i--)
{
uword x = ai[i - 1];
if (x != 0)
{
uword first_bit;
first_bit = count_leading_zeros (x);
return (i) * BITS (ai[0]) - first_bit - 1;
}
}
return ~0;
}
/** Return the lowest numbered clear bit in a bitmap
@param ai - pointer to the bitmap
@returns lowest numbered clear bit
*/
always_inline uword
clib_bitmap_first_clear (uword * ai)
{
uword i;
for (i = 0; i < vec_len (ai); i++)
{
uword x = ~ai[i];
if (x != 0)
return i * BITS (ai[0]) + log2_first_set (x);
}
return i * BITS (ai[0]);
}
/** Return the number of set bits in a bitmap
@param ai - pointer to the bitmap
@returns the number of set bits in the bitmap
*/
always_inline uword
clib_bitmap_count_set_bits (uword * ai)
{
uword i;
uword n_set = 0;
for (i = 0; i < vec_len (ai); i++)
n_set += count_set_bits (ai[i]);
return n_set;
}
/** Logical operator across two bitmaps
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns ai = ai and bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
/** Logical operator across two bitmaps
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns ai = ai & ~bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
/** Logical operator across two bitmaps
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns ai = ai & ~bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
/** Logical operator across two bitmaps
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns ai = ai or bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
/** Logical operator across two bitmaps
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns ai = ai xor bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
/* ALU function definition macro for functions taking two bitmaps. */
#define _(name, body, check_zero) \
always_inline uword * \
clib_bitmap_##name (uword * ai, uword * bi) \
{ \
uword i, a, b, bi_len, n_trailing_zeros; \
\
n_trailing_zeros = 0; \
bi_len = vec_len (bi); \
if (bi_len > 0) \
clib_bitmap_vec_validate (ai, bi_len - 1); \
for (i = 0; i < vec_len (ai); i++) \
{ \
a = ai[i]; \
b = i < bi_len ? bi[i] : 0; \
do { body; } while (0); \
ai[i] = a; \
if (check_zero) \
n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
} \
if (check_zero) \
_vec_len (ai) -= n_trailing_zeros; \
return ai; \
}
/* ALU functions: */
/* *INDENT-OFF* */
_(and, a = a & b, 1)
_(andnot, a = a & ~b, 1)
_(or, a = a | b, 0)
_(xor, a = a ^ b, 1)
/* *INDENT-ON* */
#undef _
/** Logical operator across two bitmaps which duplicates the first bitmap
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns aiDup = ai and bi. Neither ai nor bi are modified
*/
always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
/** Logical operator across two bitmaps which duplicates the first bitmap
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns aiDup = ai & ~bi. Neither ai nor bi are modified
*/
always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
/** Logical operator across two bitmaps which duplicates the first bitmap
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns aiDup = ai or bi. Neither ai nor bi are modified
*/
always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
/** Logical operator across two bitmaps which duplicates the first bitmap
@param ai - pointer to the destination bitmap
@param bi - pointer to the source bitmap
@returns aiDup = ai xor bi. Neither ai nor bi are modified
*/
always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
#define _(name) \
always_inline uword * \
clib_bitmap_dup_##name (uword * ai, uword * bi) \
{ return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
/* *INDENT-OFF* */
_(and);
_(andnot);
_(or);
_(xor);
/* *INDENT-ON* */
#undef _
/* ALU function definition macro for functions taking one bitmap and an
* immediate. */
#define _(name, body, check_zero) \
always_inline uword * \
clib_bitmap_##name (uword * ai, uword i) \
{ \
uword i0 = i / BITS (ai[0]); \
uword i1 = i % BITS (ai[0]); \
uword a, b; \
clib_bitmap_vec_validate (ai, i0); \
a = ai[i0]; \
b = (uword) 1 << i1; \
do { body; } while (0); \
ai[i0] = a; \
if (check_zero && a == 0) \
ai = _clib_bitmap_remove_trailing_zeros (ai); \
return ai; \
}
/* ALU functions immediate: */
/* *INDENT-OFF* */
_(andi, a = a & b, 1)
_(andnoti, a = a & ~b, 1)
_(ori, a = a | b, 0)
_(xori, a = a ^ b, 1)
/* *INDENT-ON* */
#undef _
/* ALU function definition macro for functions taking one bitmap and an
* immediate. No tail trimming */
#define _(name, body) \
always_inline uword * \
clib_bitmap_##name##_notrim (uword * ai, uword i) \
{ \
uword i0 = i / BITS (ai[0]); \
uword i1 = i % BITS (ai[0]); \
uword a, b; \
clib_bitmap_vec_validate (ai, i0); \
a = ai[i0]; \
b = (uword) 1 << i1; \
do { body; } while (0); \
ai[i0] = a; \
return ai; \
}
/* ALU functions immediate: */
/* *INDENT-OFF* */
_(andi, a = a & b)
_(andnoti, a = a & ~b)
_(ori, a = a | b)
_(xori, a = a ^ b)
#undef _
/* *INDENT-ON* */
/** Return a random bitmap of the requested length
@param ai - pointer to the destination bitmap
@param n_bits - number of bits to allocate
@param [in,out] seed - pointer to the random number seed
@returns a reasonably random bitmap based. See random.h.
*/
always_inline uword *
clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
{
vec_reset_length (ai);
if (n_bits > 0)
{
uword i = n_bits - 1;
uword i0, i1;
uword log2_rand_max;
log2_rand_max = min_log2 (random_u32_max ());
i0 = i / BITS (ai[0]);
i1 = i % BITS (ai[0]);
clib_bitmap_vec_validate (ai, i0);
for (i = 0; i <= i0; i++)
{
uword n;
for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
ai[i] |= random_u32 (seed) << n;
}
if (i1 + 1 < BITS (ai[0]))
ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
}
return ai;
}
/** Return the next set bit in a bitmap starting at bit i
@param ai - pointer to the bitmap
@param i - first bit position to test
@returns first set bit position at or after i,
~0 if no further set bits are found
*/
always_inline uword
clib_bitmap_next_set (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
uword t;
if (i0 < vec_len (ai))
{
t = (ai[i0] >> i1) << i1;
if (t)
return log2_first_set (t) + i0 * BITS (ai[0]);
for (i0++; i0 < vec_len (ai); i0++)
{
t = ai[i0];
if (t)
return log2_first_set (t) + i0 * BITS (ai[0]);
}
}
return ~0;
}
/** Return the next clear bit in a bitmap starting at bit i
@param ai - pointer to the bitmap
@param i - first bit position to test
@returns first clear bit position at or after i
*/
always_inline uword
clib_bitmap_next_clear (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
uword t;
if (i0 < vec_len (ai))
{
t = (~ai[i0] >> i1) << i1;
if (t)
return log2_first_set (t) + i0 * BITS (ai[0]);
for (i0++; i0 < vec_len (ai); i0++)
{
t = ~ai[i0];
if (t)
return log2_first_set (t) + i0 * BITS (ai[0]);
}
/* no clear bit left in bitmap, return bit just beyond bitmap */
return (i0 + 1) * BITS (ai[0]);
}
return i;
}
/** unformat an any sized hexadecimal bitmask into a bitmap
uword * bitmap;
rv = unformat ("%U", unformat_bitmap_mask, &bitmap);
Standard unformat_function_t arguments
@param input - pointer an unformat_input_t
@param va - varargs list comprising a single uword **
@returns 1 on success, 0 on failure
*/
static inline uword
unformat_bitmap_mask (unformat_input_t * input, va_list * va)
{
u8 *v = 0; /* hexadecimal vector */
uword **bitmap_return = va_arg (*va, uword **);
uword *bitmap = 0;
if (unformat (input, "%U", unformat_hex_string, &v))
{
int i, s = vec_len (v) - 1; /* 's' for significance or shift */
/* v[0] holds the most significant byte */
for (i = 0; s >= 0; i++, s--)
bitmap = clib_bitmap_set_multiple (bitmap,
s * BITS (v[i]), v[i],
BITS (v[i]));
vec_free (v);
*bitmap_return = bitmap;
return 1;
}
return 0;
}
/** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
uword * bitmap;
rv = unformat ("%U", unformat_bitmap_list, &bitmap);
Standard unformat_function_t arguments
@param input - pointer an unformat_input_t
@param va - varargs list comprising a single uword **
@returns 1 on success, 0 on failure
*/
static inline uword
unformat_bitmap_list (unformat_input_t * input, va_list * va)
{
uword **bitmap_return = va_arg (*va, uword **);
uword *bitmap = 0;
u32 a, b;
while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
{
int i;
if (unformat (input, "%u-%u,", &a, &b))
;
else if (unformat (input, "%u,", &a))
b = a;
else if (unformat (input, "%u-%u", &a, &b))
;
else if (unformat (input, "%u", &a))
b = a;
else if (bitmap)
{
unformat_put_input (input);
break;
}
else
goto error;
if (b < a)
goto error;
for (i = a; i <= b; i++)
bitmap = clib_bitmap_set (bitmap, i, 1);
}
*bitmap_return = bitmap;
return 1;
error:
clib_bitmap_free (bitmap);
return 0;
}
/** Format a bitmap as a string of hex bytes
uword * bitmap;
s = format ("%U", format_bitmap_hex, bitmap);
Standard format_function_t arguments
@param s - string under construction
@param args - varargs list comprising a single uword *
@returns string under construction
*/
static inline u8 *
format_bitmap_hex (u8 * s, va_list * args)
{
uword *bitmap = va_arg (*args, uword *);
int i, is_trailing_zero = 1;
if (!bitmap)
return format (s, "0");
i = vec_bytes (bitmap) * 2;
while (i > 0)
{
u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
if (x && is_trailing_zero)
is_trailing_zero = 0;
if (x || !is_trailing_zero)
s = format (s, "%x", x);
}
return s;
}
#endif /* included_clib_bitmap_h */
/*
* fd.io coding-style-patch-verification: ON
*
* Local Variables:
* eval: (c-set-style "gnu")
* End:
*/
