aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/fib/mpls_fib.h
blob: 33eaa88ca9de38209a73e20f3f1858132493cd59 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
 * mpls_fib.h: The Label/MPLS FIB
 *
 * Copyright (c) 2012 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.
 */

#ifndef __MPLS_FIB_TABLE_H__
#define __MPLS_FIB_TABLE_H__

#include <vnet/vnet.h>
#include <vnet/mpls/mpls.h>
#include <vnet/fib/fib_types.h>
#include <vnet/dpo/dpo.h>
#include <vnet/mpls/mpls.h>
#include <vnet/fib/fib_table.h>

#define MPLS_FIB_DEFAULT_TABLE_ID 0

/**
 * Type exposure is to allow the DP fast/inlined access
 */
#define MPLS_FIB_KEY_SIZE 21
#define MPLS_FIB_DB_SIZE (1 << (MPLS_FIB_KEY_SIZE-1))

/**
 * There are no options for controlling the MPLS flow hash,
 * but since it mostly entails using IP data to create one, use that.
 */
#define MPLS_FLOW_HASH_DEFAULT IP_FLOW_HASH_DEFAULT

typedef struct mpls_fib_t_
{
  /**
   * Required for pool_get_aligned
   */
  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);

  /**
   * A hash table of entries. 21 bit key
   * Hash table for reduced memory footprint
   */
  uword * mf_entries;

  /**
   * The load-balance indices keyed by 21 bit label+eos bit.
   * A flat array for maximum lookup performace.
   */
  index_t mf_lbs[MPLS_FIB_DB_SIZE];
} mpls_fib_t;

static inline mpls_fib_t*
mpls_fib_get (fib_node_index_t index)
{
    return (pool_elt_at_index(mpls_main.mpls_fibs, index));
}

extern u32 mpls_fib_table_find_or_create_and_lock(u32 table_id,
                                                  fib_source_t src);
extern u32 mpls_fib_table_create_and_lock(fib_source_t src);
// extern mpls_fib_t * mpls_fib_find(u32 table_id);
extern u32 mpls_fib_index_from_table_id(u32 table_id);

extern u8 *format_mpls_fib_table_name(u8 * s, va_list * args);

extern fib_node_index_t mpls_fib_table_entry_add_from_ip_fib_entry (
    u32 table_id,
    mpls_label_t label,
    mpls_eos_bit_t eos,
    fib_node_index_t fib_entry_index);


extern fib_node_index_t mpls_fib_table_lookup(const mpls_fib_t *mf,
					      mpls_label_t label,
					      mpls_eos_bit_t eos);

extern void mpls_fib_table_entry_remove(mpls_fib_t *mf,
					mpls_label_t label,
					mpls_eos_bit_t eos);
extern void mpls_fib_table_entry_insert(mpls_fib_t *mf,
					mpls_label_t label,
					mpls_eos_bit_t eos,
					fib_node_index_t fei);
extern void mpls_fib_table_destroy(u32 fib_index);


extern void mpls_fib_forwarding_table_update(mpls_fib_t *mf,
					     mpls_label_t label,
					     mpls_eos_bit_t eos,
					     const dpo_id_t *dpo);
extern void mpls_fib_forwarding_table_reset(mpls_fib_t *mf,
					    mpls_label_t label,
					    mpls_eos_bit_t eos);

/**
 * @brief Walk all entries in a FIB table
 * N.B: This is NOT safe to deletes. If you need to delete walk the whole
 * table and store elements in a vector, then delete the elements
 */
extern void mpls_fib_table_walk(mpls_fib_t *fib,
                                fib_table_walk_fn_t fn,
                                void *ctx);

extern u8 *format_mpls_fib_table_memory(u8 * s, va_list * args);

/**
 * @brief
 *  Lookup a label and EOS bit in the MPLS_FIB table to retrieve the
 *  load-balance index to be used for packet forwarding.
 */
static inline index_t
mpls_fib_table_forwarding_lookup (u32 mpls_fib_index,
				  const mpls_unicast_header_t *hdr)
{
    mpls_label_t label;
    mpls_fib_t *mf;
    u32 key;

    label = clib_net_to_host_u32(hdr->label_exp_s_ttl);
    key = (vnet_mpls_uc_get_label(label) << 1) | vnet_mpls_uc_get_s(label);

    mf = mpls_fib_get(mpls_fib_index);

    return (mf->mf_lbs[key]);
}

static inline u32
mpls_fib_table_get_index_for_sw_if_index (u32 sw_if_index)
{
    mpls_main_t *mm = &mpls_main;

    ASSERT(vec_len(mm->fib_index_by_sw_if_index) > sw_if_index);

    return (mm->fib_index_by_sw_if_index[sw_if_index]);
}

#endif
n705' href='#n705'>705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867
/*
 * 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:
 */