Reorganize source tree to use single autotools instance

Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23
Signed-off-by: Damjan Marion <damarion@cisco.com>

1 files changed, 405 insertions, 0 deletions

diff --git a/src/vppinfra/pool.h b/src/vppinfra/pool.h
new file mode 100644
index 00000000000..e1c89e0a5fa
--- /dev/null
+++ b/src/vppinfra/pool.h
@@ -0,0 +1,405 @@
+/*
+ * 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, 2004 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.
+*/
+/** @file
+ * @brief Fixed length block allocator.
+   Pools are built from clib vectors and bitmaps. Use pools when
+   repeatedly allocating and freeing fixed-size data. Pools are
+   fast, and avoid memory fragmentation.
+ */
+
+#ifndef included_pool_h
+#define included_pool_h
+
+#include <vppinfra/bitmap.h>
+#include <vppinfra/error.h>
+#include <vppinfra/mheap.h>
+
+
+typedef struct
+{
+  /** Bitmap of indices of free objects. */
+  uword *free_bitmap;
+
+  /** Vector of free indices.  One element for each set bit in bitmap. */
+  u32 *free_indices;
+} pool_header_t;
+
+/** Align pool header so that pointers are naturally aligned. */
+#define pool_aligned_header_bytes \
+  vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))
+
+/** Get pool header from user pool pointer */
+always_inline pool_header_t *
+pool_header (void *v)
+{
+  return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *));
+}
+
+/** Validate a pool */
+always_inline void
+pool_validate (void *v)
+{
+  pool_header_t *p = pool_header (v);
+  uword i, n_free_bitmap;
+
+  if (!v)
+    return;
+
+  n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
+  ASSERT (n_free_bitmap == vec_len (p->free_indices));
+  for (i = 0; i < vec_len (p->free_indices); i++)
+    ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
+}
+
+always_inline void
+pool_header_validate_index (void *v, uword index)
+{
+  pool_header_t *p = pool_header (v);
+
+  if (v)
+    vec_validate (p->free_bitmap, index / BITS (uword));
+}
+
+#define pool_validate_index(v,i)				\
+do {								\
+  uword __pool_validate_index = (i);				\
+  vec_validate_ha ((v), __pool_validate_index,			\
+		   pool_aligned_header_bytes, /* align */ 0);		\
+  pool_header_validate_index ((v), __pool_validate_index);	\
+} while (0)
+
+/** Number of active elements in a pool.
+ * @return Number of active elements in a pool
+ */
+always_inline uword
+pool_elts (void *v)
+{
+  uword ret = vec_len (v);
+  if (v)
+    ret -= vec_len (pool_header (v)->free_indices);
+  return ret;
+}
+
+/** Number of elements in pool vector.
+
+    @note You probably want to call pool_elts() instead.
+*/
+#define pool_len(p)	vec_len(p)
+
+/** Number of elements in pool vector (usable as an lvalue)
+
+    @note You probably don't want to use this macro.
+*/
+#define _pool_len(p)	_vec_len(p)
+
+/** Memory usage of pool header. */
+always_inline uword
+pool_header_bytes (void *v)
+{
+  pool_header_t *p = pool_header (v);
+
+  if (!v)
+    return 0;
+
+  return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
+}
+
+/** Memory usage of pool. */
+#define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
+
+/** Local variable naming macro. */
+#define _pool_var(v) _pool_##v
+
+/** Queries whether pool has at least N_FREE free elements. */
+always_inline uword
+pool_free_elts (void *v)
+{
+  pool_header_t *p = pool_header (v);
+  uword n_free = 0;
+
+  if (v)
+    {
+      n_free += vec_len (p->free_indices);
+
+      /* Space left at end of vector? */
+      n_free += vec_capacity (v, sizeof (p[0])) - vec_len (v);
+    }
+
+  return n_free;
+}
+
+/** Allocate an object E from a pool P (general version).
+
+   First search free list.  If nothing is free extend vector of objects.
+*/
+#define pool_get_aligned(P,E,A)						\
+do {									\
+  pool_header_t * _pool_var (p) = pool_header (P);			\
+  uword _pool_var (l);							\
+									\
+  _pool_var (l) = 0;							\
+  if (P)								\
+    _pool_var (l) = vec_len (_pool_var (p)->free_indices);		\
+									\
+  if (_pool_var (l) > 0)						\
+    {									\
+      /* Return free element from free list. */				\
+      uword _pool_var (i) = _pool_var (p)->free_indices[_pool_var (l) - 1]; \
+      (E) = (P) + _pool_var (i);					\
+      _pool_var (p)->free_bitmap =					\
+	clib_bitmap_andnoti (_pool_var (p)->free_bitmap, _pool_var (i)); \
+      _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;	\
+    }									\
+  else									\
+    {									\
+      /* Nothing on free list, make a new element and return it. */	\
+      P = _vec_resize (P,						\
+		       /* length_increment */ 1,			\
+		       /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
+		       pool_aligned_header_bytes,				\
+		       /* align */ (A));				\
+      E = vec_end (P) - 1;						\
+    }									\
+} while (0)
+
+/** Allocate an object E from a pool P (unspecified alignment). */
+#define pool_get(P,E) pool_get_aligned(P,E,0)
+
+/** Use free bitmap to query whether given element is free. */
+#define pool_is_free(P,E)						\
+({									\
+  pool_header_t * _pool_var (p) = pool_header (P);			\
+  uword _pool_var (i) = (E) - (P);					\
+  (_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \
+})
+
+/** Use free bitmap to query whether given index is free */
+#define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
+
+/** Free an object E in pool P. */
+#define pool_put(P,E)							\
+do {									\
+  pool_header_t * _pool_var (p) = pool_header (P);			\
+  uword _pool_var (l) = (E) - (P);					\
+  ASSERT (vec_is_member (P, E));					\
+  ASSERT (! pool_is_free (P, E));					\
+									\
+  /* Add element to free bitmap and to free list. */			\
+  _pool_var (p)->free_bitmap =						\
+    clib_bitmap_ori (_pool_var (p)->free_bitmap, _pool_var (l));	\
+  vec_add1 (_pool_var (p)->free_indices, _pool_var (l));		\
+} while (0)
+
+/** Free pool element with given index. */
+#define pool_put_index(p,i)			\
+do {						\
+  typeof (p) _e = (p) + (i);			\
+  pool_put (p, _e);				\
+} while (0)
+
+/** Allocate N more free elements to pool (general version). */
+#define pool_alloc_aligned(P,N,A)					\
+do {									\
+  pool_header_t * _p;							\
+  (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]),	\
+		     pool_aligned_header_bytes,				\
+		     (A));						\
+  _p = pool_header (P);							\
+  vec_resize (_p->free_indices, (N));					\
+  _vec_len (_p->free_indices) -= (N);					\
+} while (0)
+
+/** Allocate N more free elements to pool (unspecified alignment). */
+#define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
+
+/** Low-level free pool operator (do not call directly). */
+always_inline void *
+_pool_free (void *v)
+{
+  pool_header_t *p = pool_header (v);
+  if (!v)
+    return v;
+  clib_bitmap_free (p->free_bitmap);
+  vec_free (p->free_indices);
+  vec_free_h (v, pool_aligned_header_bytes);
+  return 0;
+}
+
+/** Free a pool. */
+#define pool_free(p) (p) = _pool_free(p)
+
+/** Optimized iteration through pool.
+
+    @param LO pointer to first element in chunk
+    @param HI pointer to last element in chunk
+    @param POOL pool to iterate across
+    @param BODY operation to perform
+
+    Optimized version which assumes that BODY is smart enough to
+    process multiple (LOW,HI) chunks. See also pool_foreach().
+ */
+#define pool_foreach_region(LO,HI,POOL,BODY)				\
+do {									\
+  uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len);	\
+  uword _pool_var (bl), * _pool_var (b);				\
+  pool_header_t * _pool_var (p);					\
+									\
+  _pool_var (p) = pool_header (POOL);					\
+  _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0;		\
+  _pool_var (bl) = vec_len (_pool_var (b));				\
+  _pool_var (len) = vec_len (POOL);					\
+  _pool_var (lo) = 0;							\
+									\
+  for (_pool_var (i) = 0;						\
+       _pool_var (i) <= _pool_var (bl);					\
+       _pool_var (i)++)							\
+    {									\
+      uword _pool_var (m), _pool_var (f);				\
+      _pool_var (m) = (_pool_var (i) < _pool_var (bl)			\
+		       ? _pool_var (b) [_pool_var (i)]			\
+		       : 1);						\
+      while (_pool_var (m) != 0)					\
+	{								\
+	  _pool_var (f) = first_set (_pool_var (m));			\
+	  _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0])	\
+			    + min_log2 (_pool_var (f)));		\
+	  _pool_var (hi) = (_pool_var (i) < _pool_var (bl)		\
+			    ? _pool_var (hi) : _pool_var (len));	\
+	  _pool_var (m) ^= _pool_var (f);				\
+	  if (_pool_var (hi) > _pool_var (lo))				\
+	    {								\
+	      (LO) = _pool_var (lo);					\
+	      (HI) = _pool_var (hi);					\
+	      do { BODY; } while (0);					\
+	    }								\
+	  _pool_var (lo) = _pool_var (hi) + 1;				\
+	}								\
+    }									\
+} while (0)
+
+/** Iterate through pool.
+
+    @param VAR A variable of same type as pool vector to be used as an
+               iterator.
+    @param POOL The pool to iterate across.
+    @param BODY The operation to perform, typically a code block. See
+                the example below.
+
+    This macro will call @c BODY with each active pool element.
+
+    It is a bad idea to allocate or free pool element from within
+    @c pool_foreach. Build a vector of indices and dispose of them later.
+
+
+    @par Example
+    @code{.c}
+    proc_t *procs;   // a pool of processes.
+    proc_t *proc;    // pointer to one process; used as the iterator.
+
+    pool_foreach (proc, procs, ({
+        if (proc->state != PROC_STATE_RUNNING)
+            continue;
+
+        // check a running proc in some way
+        ...
+    }));
+    @endcode
+
+    @warning Because @c pool_foreach is a macro, syntax errors can be
+    difficult to find inside @c BODY, let alone actual code bugs. One
+    can temporarily split a complex @c pool_foreach into a trivial
+    @c pool_foreach which builds a vector of active indices, and a
+    vec_foreach() (or plain for-loop) to walk the active index vector.
+ */
+#define pool_foreach(VAR,POOL,BODY)					\
+do {									\
+  uword _pool_foreach_lo, _pool_foreach_hi;				\
+  pool_foreach_region (_pool_foreach_lo, _pool_foreach_hi, (POOL),	\
+    ({									\
+      for ((VAR) = (POOL) + _pool_foreach_lo;				\
+	   (VAR) < (POOL) + _pool_foreach_hi;				\
+	   (VAR)++)							\
+	do { BODY; } while (0);						\
+    }));								\
+} while (0)
+
+/** Returns pointer to element at given index.
+
+    ASSERTs that the supplied index is valid.
+    Even though one can write correct code of the form
+    @code
+        p = pool_base + index;
+    @endcode
+    use of @c pool_elt_at_index is strongly suggested.
+ */
+#define pool_elt_at_index(p,i)			\
+({						\
+  typeof (p) _e = (p) + (i);			\
+  ASSERT (! pool_is_free (p, _e));		\
+  _e;						\
+})
+
+/** Return next occupied pool index after @c i, useful for safe iteration. */
+#define pool_next_index(P,I)                                            \
+({                                                                      \
+  pool_header_t * _pool_var (p) = pool_header (P);                      \
+  uword _pool_var (rv) = (I) + 1;                                       \
+                                                                        \
+  _pool_var(rv) =                                                       \
+    (_pool_var (rv) < vec_len (P) ?                                     \
+     clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
+     : ~0);                                                             \
+  _pool_var(rv);                                                        \
+})
+
+/** Iterate pool by index. */
+#define pool_foreach_index(i,v,body)		\
+  for ((i) = 0; (i) < vec_len (v); (i)++)	\
+    {						\
+      if (! pool_is_free_index ((v), (i)))	\
+	do { body; } while (0);			\
+    }
+
+#endif /* included_pool_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */