diff options
| -rw-r--r-- | src/plugins/unittest/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/plugins/unittest/llist_test.c | 353 | ||||
| -rw-r--r-- | src/vppinfra/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/vppinfra/llist.h | 254 |
4 files changed, 609 insertions, 0 deletions
diff --git a/src/plugins/unittest/CMakeLists.txt b/src/plugins/unittest/CMakeLists.txt index 2afe5e781da..5ba21bd7acb 100644 --- a/src/plugins/unittest/CMakeLists.txt +++ b/src/plugins/unittest/CMakeLists.txt @@ -26,6 +26,7 @@ add_vpp_plugin(unittest ipsec_test.c interface_test.c lisp_cp_test.c + llist_test.c mactime_test.c mfib_test.c punt_test.c diff --git a/src/plugins/unittest/llist_test.c b/src/plugins/unittest/llist_test.c new file mode 100644 index 00000000000..bd8f6c074c5 --- /dev/null +++ b/src/plugins/unittest/llist_test.c @@ -0,0 +1,353 @@ +/* + * Copyright (c) 2019 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. + */ +#include <vppinfra/llist.h> +#include <vlib/vlib.h> + +#define LLIST_TEST_I(_cond, _comment, _args...) \ +({ \ + int _evald = (_cond); \ + if (!(_evald)) { \ + fformat(stderr, "FAIL:%d: " _comment "\n", \ + __LINE__, ##_args); \ + } else { \ + fformat(stderr, "PASS:%d: " _comment "\n", \ + __LINE__, ##_args); \ + } \ + _evald; \ +}) + +#define LLIST_TEST(_cond, _comment, _args...) \ +{ \ + if (!LLIST_TEST_I(_cond, _comment, ##_args)) { \ + return 1; \ + } \ +} + +typedef struct list_elt +{ + clib_llist_anchor_t ll_test; + clib_llist_anchor_t ll_test2; + u32 data; +} list_elt_t; + +#define list_elt_is_sane(pl,name,E,P,N) \ + (E->name.next == (N) - pl \ + && E->name.prev == (P) - pl \ + && P->name.next == (E) - pl \ + && N->name.prev == (E) - pl) + +#define list_test_is_sane(pl,name,h) \ +do { \ + typeof (pl) e; \ + int rv; \ + clib_llist_foreach (pl, name, h, e, ({ \ + rv = list_elt_is_sane ((pl), name, (e), \ + clib_llist_prev (pl,name,e), \ + clib_llist_next (pl,name,e)); \ + if (!rv) \ + LLIST_TEST (0, "invalid elt %u prev %u/%u next %u/%u", e - pl, \ + e->name.prev, clib_llist_prev (pl,name,e) - pl, \ + e->name.next, clib_llist_next (pl,name,e) - pl); \ + })); \ +} while (0) + +static int +llist_test_basic (vlib_main_t * vm, unformat_input_t * input) +{ + list_elt_t *pelts = 0, *he, *he2, *he3, *e, *next, *nnext; + int __clib_unused verbose, i, rv; + clib_llist_index_t head, head2, head3; + u32 old_tail; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "verbose")) + verbose = 1; + else + { + vlib_cli_output (vm, "parse error: '%U'", format_unformat_error, + input); + return -1; + } + } + + head = clib_llist_make_head (pelts, ll_test); + he = pool_elt_at_index (pelts, head); + + LLIST_TEST (he->ll_test.next == head, "head next points to itself"); + LLIST_TEST (he->ll_test.prev == head, "head prev points to itself"); + LLIST_TEST (he == clib_llist_next (pelts, ll_test, he), + "should be the same"); + LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he), + "should be the same"); + + /* + * Add and remove one element + */ + pool_get (pelts, e); + e->data = 1; + he = pool_elt_at_index (pelts, head); + clib_llist_add (pelts, ll_test, e, he); + + LLIST_TEST (e->ll_test.next == head, "next should be head"); + LLIST_TEST (e->ll_test.prev == head, "prev should be head"); + LLIST_TEST (he->ll_test.prev == e - pelts, "prev should be new"); + LLIST_TEST (he->ll_test.next == e - pelts, "prev should be new"); + + clib_llist_remove (pelts, ll_test, e); + pool_put (pelts, e); + LLIST_TEST (he->ll_test.prev == head, "prev should be head"); + LLIST_TEST (he->ll_test.prev == head, "next should be head"); + LLIST_TEST (he == clib_llist_next (pelts, ll_test, he), + "should be the same"); + LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he), + "should be the same"); + + /* + * Add multiple head elements and test insertion + */ + for (i = 0; i < 100; i++) + { + pool_get (pelts, e); + e->data = i; + he = pool_elt_at_index (pelts, head); + clib_llist_add (pelts, ll_test, e, he); + } + + he = pool_elt_at_index (pelts, head); + LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he), + "shoud not be empty"); + list_test_is_sane (pelts, ll_test, he); + + i--; + /* *INDENT-OFF* */ + clib_llist_foreach (pelts, ll_test, he, e, ({ + if (i != e->data) + LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data); + i--; + })); + /* *INDENT-ON* */ + + LLIST_TEST (i == -1, "head insertion works i = %d", i); + + /* + * Remove elements from head + */ + i = 99; + e = clib_llist_next (pelts, ll_test, he); + while (e != he) + { + next = clib_llist_next (pelts, ll_test, e); + clib_llist_remove (pelts, ll_test, e); + pool_put (pelts, e); + i--; + e = next; + } + + he = pool_elt_at_index (pelts, head); + list_test_is_sane (pelts, ll_test, he); + LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he), + "list should be empty"); + LLIST_TEST (pool_elts (pelts) == 1, "pool should have only 1 element"); + + /* + * Add tail elements to ll_test2 and test + */ + head2 = clib_llist_make_head (pelts, ll_test2); + for (i = 0; i < 100; i++) + { + pool_get (pelts, e); + e->data = i; + he2 = pool_elt_at_index (pelts, head2); + clib_llist_add_tail (pelts, ll_test2, e, he2); + } + + he2 = pool_elt_at_index (pelts, head2); + list_test_is_sane (pelts, ll_test2, he2); + LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2), + "list should not be empty"); + + i--; + /* *INDENT-OFF* */ + clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({ + if (i != e->data) + LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data); + i--; + })); + /* *INDENT-ON* */ + LLIST_TEST (i == -1, "tail insertion works"); + + /* + * Remove in from ll_test2 and add to ll_test + */ + i = 0; + he = pool_elt_at_index (pelts, head); + e = clib_llist_next (pelts, ll_test2, he2); + while (e != he2) + { + next = clib_llist_next (pelts, ll_test2, e); + + if (e->data != i) + LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data); + + clib_llist_remove (pelts, ll_test2, e); + clib_llist_add_tail (pelts, ll_test, e, he); + i++; + e = next; + } + + he = pool_elt_at_index (pelts, head); + he2 = pool_elt_at_index (pelts, head2); + list_test_is_sane (pelts, ll_test, he); + LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he), + "shoud not be empty"); + LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty"); + + i = 0; + + /* *INDENT-OFF* */ + clib_llist_foreach (pelts, ll_test, he, e, ({ + if (i != e->data) + LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data); + i++; + })); + /* *INDENT-ON* */ + + LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i); + + /* + * Delete and insert at random position + */ + e = pool_elt_at_index (pelts, head); + for (i = 0; i < 10; i++) + e = clib_llist_next (pelts, ll_test, e); + + next = clib_llist_next (pelts, ll_test, e); + nnext = clib_llist_next (pelts, ll_test, next); + + LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data); + LLIST_TEST (next->data == 10, "data should be 10"); + LLIST_TEST (nnext->data == 11, "data should be 11"); + + clib_llist_remove (pelts, ll_test, next); + pool_put (pelts, next); + memset (next, 0xfc, sizeof (*next)); + + next = clib_llist_next (pelts, ll_test, e); + LLIST_TEST (next->data == 11, "data should be 11"); + LLIST_TEST (next == nnext, "should be nnext"); + + pool_get (pelts, next); + next->data = 10; + clib_llist_insert (pelts, ll_test, next, e); + + next = clib_llist_next (pelts, ll_test, e); + LLIST_TEST (next->data == 10, "new next data should be 10"); + next = clib_llist_next (pelts, ll_test, next); + LLIST_TEST (nnext == next, "next should be linked to old nnext"); + + he = pool_elt_at_index (pelts, head); + list_test_is_sane (pelts, ll_test, he); + + /* + * Make a new list that uses ll_test anchor + */ + + head3 = clib_llist_make_head (pelts, ll_test); + for (i = 0; i < 10; i++) + { + pool_get (pelts, e); + e->data = 300 + i; + he3 = pool_elt_at_index (pelts, head3); + clib_llist_add (pelts, ll_test, e, he3); + } + + he = pool_elt_at_index (pelts, head); + he3 = pool_elt_at_index (pelts, head3); + list_test_is_sane (pelts, ll_test, he3); + e = clib_llist_prev (pelts, ll_test, he); + old_tail = e->data; + + /* + * Splice third list into the tail of the first + */ + clib_llist_splice (pelts, ll_test, e, he3); + + list_test_is_sane (pelts, ll_test, he); + LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty"); + + e = clib_llist_prev (pelts, ll_test, he); + LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u", + e->data); + for (i = 0; i < 10; i++) + { + if (e->data != 300 + i) + LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data); + e = clib_llist_prev (pelts, ll_test, e); + } + + LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u", + old_tail, e->data); + + /* + * Cleanup + */ + pool_free (pelts); + return 0; +} + +static clib_error_t * +llist_test (vlib_main_t * vm, + unformat_input_t * input, vlib_cli_command_t * cmd_arg) +{ + int res = 0; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "basic")) + { + res = llist_test_basic (vm, input); + } + else if (unformat (input, "all")) + { + if ((res = llist_test_basic (vm, input))) + goto done; + } + else + break; + } + +done: + if (res) + return clib_error_return (0, "llist unit test failed"); + return 0; +} + +/* *INDENT-OFF* */ +VLIB_CLI_COMMAND (llist_test_command, static) = +{ + .path = "test llist", + .short_help = "internal llist unit tests", + .function = llist_test, +}; +/* *INDENT-ON* */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt index d8b302cf399..9c5804602a1 100644 --- a/src/vppinfra/CMakeLists.txt +++ b/src/vppinfra/CMakeLists.txt @@ -123,6 +123,7 @@ set(VPPINFRA_HEADERS hash.h heap.h lb_hash_hash.h + llist.h lock.h longjmp.h macros.h diff --git a/src/vppinfra/llist.h b/src/vppinfra/llist.h new file mode 100644 index 00000000000..1648021681f --- /dev/null +++ b/src/vppinfra/llist.h @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2019 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. + * + * @file + * @brief Circular doubly linked list with head sentinel. + * List entries are allocated out of a "supporting" pool and all pool entries + * must contain a list anchor struct for each list they pertain to. + */ + +#ifndef SRC_VPPINFRA_CLIB_LLIST_H_ +#define SRC_VPPINFRA_CLIB_LLIST_H_ + +#include <vppinfra/types.h> +#include <vppinfra/pool.h> + +typedef u32 clib_llist_index_t; + +typedef struct clib_llist_anchor +{ + clib_llist_index_t prev; + clib_llist_index_t next; +} clib_llist_anchor_t; + +#define CLIB_LLIST_INVALID_INDEX ((u32)~0) + +/** + * Local variable naming macro. + */ +#define _ll_var(v) _llist_##v +/** + * Local macros to grab llist anchor next and prev from pool entry + */ +#define _lnext(E,name) ((E)->name).next +#define _lprev(E,name) ((E)->name).prev +/** + * Get list entry index + * + * @param LP linked list pool + * @param E pool entry + * @return pool entry index + */ +#define clib_llist_entry_index(LP,E) ((E) - (LP)) +/** + * Get next pool entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E pool entry + * @return next pool entry + */ +#define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name)) +/** + * Get previous pool entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E pool entry + * @return previous pool entry + */ +#define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name)) +/** + * Initialize element in llist for entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E entry whose ll anchor is to be initialized + */ +#define clib_llist_anchor_init(LP,name,E) \ +do { \ + _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \ + _lnext ((E),name) = _lprev ((E),name); \ +} while (0) +/** + * Initialize llist head + * + * @param LP linked list pool + * @param name list anchor name + */ +#define clib_llist_make_head(LP,name) \ +({ \ + typeof (LP) _ll_var (head); \ + pool_get_zero ((LP), _ll_var (head)); \ + clib_llist_anchor_init ((LP),name,_ll_var (head)); \ + clib_llist_entry_index ((LP), _ll_var (head)); \ +}) +/** + * Check is list is empty + * + * @param LP linked list pool + * @param name list anchor name + * @param H list head + * @return 1 if sentinel is the only node part of the list, 0 otherwise + */ +#define clib_llist_is_empty(LP,name,H) ((H) == clib_llist_next((LP),name,(H))) +/** + * Insert entry between previous and next + * + * Internal use. + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param P previous in list + * @param N next in list + */ +#define _llist_insert(LP,name,E,P,N) \ +do { \ + _lprev (E,name) = _lprev(N,name); \ + _lnext (E,name) = _lnext(P,name); \ + _lprev ((N),name) = clib_llist_entry_index ((LP),(E)); \ + _lnext ((P),name) = clib_llist_entry_index ((LP),(E)); \ +} while (0) +/** + * Insert entry after previous + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param P previous in list + */ +#define clib_llist_insert(LP,name,E,P) \ +do { \ + typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \ + _llist_insert ((LP),name,(E),(P), _ll_var (N)); \ +} while (0) + +/** + * Add entry after head + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param H list head + */ +#define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H)) +/** + * Add entry after tail + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param H list head + */ +#define clib_llist_add_tail(LP,name,E,H) \ +do { \ + typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \ + _llist_insert ((LP),name,(E),_ll_var (P),(H)); \ +} while (0) +/** + * Remove entry from list + * + * @param LP linked list pool + * @param name list anchor name + * @param E entry to be removed + */ +#define clib_llist_remove(LP,name,E) \ +do { \ + ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\ + ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX); \ + ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX); \ + typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E); \ + typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E); \ + _lnext (_ll_var (P),name) = _lnext (E,name); \ + _lprev (_ll_var (N),name) = _lprev (E,name); \ + _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX; \ +}while (0) + +/** + * Splice two lists at a given position + * + * List spliced into destination list is left with 0 entries, i.e., head + * is made to point to itself. + * + * @param LP linked list pool + * @param name list anchor name + * @param P position in destination where source list is spliced + * @param H head of source list that will be spliced into destination + */ +#define clib_llist_splice(LP,name,P,H) \ +do { \ + typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \ + if (_ll_var (fe) != (H)) \ + { \ + typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H); \ + typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P); \ + _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P); \ + _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\ + _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe)); \ + _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\ + _lnext (H,name) = clib_llist_entry_index(LP,H); \ + _lprev (H,name) = _lnext (H,name); \ + } \ +} while (0) +/** + * Walk list starting at head + * + * @param LP linked list pool + * @param name list anchor name + * @param H head entry + * @param E entry iterator + * @param body code to be executed + */ +#define clib_llist_foreach(LP,name,H,E,body) \ +do { \ + typeof (LP) _ll_var (n); \ + (E) = clib_llist_next (LP,name,H); \ + while (E != H) \ + { \ + _ll_var (n) = clib_llist_next (LP,name,E); \ + do { body; } while (0); \ + (E) = _ll_var (n); \ + } \ +} while (0) +/** + * Walk list starting at head in reverse order + * + * @param LP linked list pool + * @param name list anchor name + * @param H head entry + * @param E entry iterator + * @param body code to be executed + */ +#define clib_llist_foreach_reverse(LP,name,H,E,body) \ +do { \ + typeof (LP) _ll_var (p); \ + (E) = clib_llist_prev (LP,name,H); \ + while (E != H) \ + { \ + _ll_var (p) = clib_llist_prev (LP,name,E); \ + do { body; } while (0); \ + (E) = _ll_var (p); \ + } \ +} while (0) + +#endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |