From 7353ee7344b45426b921b91c56aa211ab0e58a89 Mon Sep 17 00:00:00 2001 From: Anatoly Burakov Date: Fri, 22 Feb 2019 16:14:01 +0000 Subject: [PATCH] fbarray: add API to find biggest used or free chunks Currently, while there is a way to find total amount of used/free space in an fbarray, there is no way to find biggest contiguous chunk. Add such API, as well as unit tests to test this API. Signed-off-by: Anatoly Burakov --- app/test/test_fbarray.c | 159 ++++++++++++++++++++ lib/librte_eal/common/eal_common_fbarray.c | 109 ++++++++++++++ lib/librte_eal/common/include/rte_fbarray.h | 70 +++++++++ lib/librte_eal/rte_eal_version.map | 4 + 4 files changed, 342 insertions(+) diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c index 8c44e2c7e1..d2b041887c 100644 --- a/app/test/test_fbarray.c +++ b/app/test/test_fbarray.c @@ -97,6 +97,8 @@ static int empty_msk_test_setup(void) { /* do not fill anything in */ reset_array(); + param.start = -1; + param.end = -1; return 0; } @@ -456,6 +458,157 @@ static int test_basic(void) return TEST_SUCCESS; } +static int test_biggest(struct rte_fbarray *arr, int first, int last) +{ + int lo_free_space_first, lo_free_space_last, lo_free_space_len; + int hi_free_space_first, hi_free_space_last, hi_free_space_len; + int max_free_space_first, max_free_space_last, max_free_space_len; + int len = last - first + 1; + + /* first and last must either be both -1, or both not -1 */ + TEST_ASSERT((first == -1) == (last == -1), + "Invalid arguments provided\n"); + + /* figure out what we expect from the low chunk of free space */ + if (first == -1) { + /* special case: if there are no occupied elements at all, + * consider both free spaces to consume the entire array. + */ + lo_free_space_first = 0; + lo_free_space_last = arr->len - 1; + lo_free_space_len = arr->len; + /* if there's no used space, length should be invalid */ + len = -1; + } else if (first == 0) { + /* if occupied items start at 0, there's no free space */ + lo_free_space_first = -1; + lo_free_space_last = -1; + lo_free_space_len = 0; + } else { + lo_free_space_first = 0; + lo_free_space_last = first - 1; + lo_free_space_len = lo_free_space_last - + lo_free_space_first + 1; + } + + /* figure out what we expect from the high chunk of free space */ + if (last == -1) { + /* special case: if there are no occupied elements at all, + * consider both free spaces to consume the entire array. + */ + hi_free_space_first = 0; + hi_free_space_last = arr->len - 1; + hi_free_space_len = arr->len; + /* if there's no used space, length should be invalid */ + len = -1; + } else if (last == ((int)arr->len - 1)) { + /* if occupied items end at array len, there's no free space */ + hi_free_space_first = -1; + hi_free_space_last = -1; + hi_free_space_len = 0; + } else { + hi_free_space_first = last + 1; + hi_free_space_last = arr->len - 1; + hi_free_space_len = hi_free_space_last - + hi_free_space_first + 1; + } + + /* find which one will be biggest */ + if (lo_free_space_len > hi_free_space_len) { + max_free_space_first = lo_free_space_first; + max_free_space_last = lo_free_space_last; + max_free_space_len = lo_free_space_len; + } else { + /* if they are equal, we'll just use the high chunk */ + max_free_space_first = hi_free_space_first; + max_free_space_last = hi_free_space_last; + max_free_space_len = hi_free_space_len; + } + + /* check used regions - these should produce identical results */ + TEST_ASSERT_EQUAL(rte_fbarray_find_biggest_used(arr, 0), first, + "Used space index is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_biggest_used(arr, arr->len - 1), + first, + "Used space index is wrong\n"); + /* len may be -1, but function will return error anyway */ + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(arr, first), len, + "Used space length is wrong\n"); + + /* check if biggest free region is the one we expect to find. It can be + * -1 if there's no free space - we've made sure we use one or the + * other, even if both are invalid. + */ + TEST_ASSERT_EQUAL(rte_fbarray_find_biggest_free(arr, 0), + max_free_space_first, + "Biggest free space index is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_biggest_free(arr, arr->len - 1), + max_free_space_first, + "Biggest free space index is wrong\n"); + + /* if biggest region exists, check its length */ + if (max_free_space_first != -1) { + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(arr, + max_free_space_first), + max_free_space_len, + "Biggest free space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(arr, + max_free_space_last), + max_free_space_len, + "Biggest free space length is wrong\n"); + } + + /* find if we see what we expect to see in the low region. if there is + * no free space, the function should still match expected value, as + * we've set it to -1. we're scanning backwards to avoid accidentally + * hitting the high free space region. if there is no occupied space, + * there's nothing to do. + */ + if (last != -1) { + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_biggest_free(arr, last), + lo_free_space_first, + "Low free space index is wrong\n"); + } + + if (lo_free_space_first != -1) { + /* if low free region exists, check its length */ + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(arr, + lo_free_space_first), + lo_free_space_len, + "Low free space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(arr, + lo_free_space_last), + lo_free_space_len, + "Low free space length is wrong\n"); + } + + /* find if we see what we expect to see in the high region. if there is + * no free space, the function should still match expected value, as + * we've set it to -1. we're scanning forwards to avoid accidentally + * hitting the low free space region. if there is no occupied space, + * there's nothing to do. + */ + if (first != -1) { + TEST_ASSERT_EQUAL(rte_fbarray_find_biggest_free(arr, first), + hi_free_space_first, + "High free space index is wrong\n"); + } + + /* if high free region exists, check its length */ + if (hi_free_space_first != -1) { + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(arr, + hi_free_space_first), + hi_free_space_len, + "High free space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(arr, + hi_free_space_last), + hi_free_space_len, + "High free space length is wrong\n"); + } + + return 0; +} + static int ensure_correct(struct rte_fbarray *arr, int first, int last, bool used) { @@ -537,6 +690,9 @@ static int test_find(void) if (ensure_correct(¶m.arr, param.end + 1, FBARRAY_TEST_LEN - 1, false)) return TEST_FAILED; + /* test if find_biggest API's work correctly */ + if (test_biggest(¶m.arr, param.start, param.end)) + return TEST_FAILED; return TEST_SUCCESS; } @@ -546,6 +702,9 @@ static int test_empty(void) /* ensure space is free */ if (ensure_correct(¶m.arr, 0, FBARRAY_TEST_LEN - 1, false)) return TEST_FAILED; + /* test if find_biggest API's work correctly */ + if (test_biggest(¶m.arr, param.start, param.end)) + return TEST_FAILED; return TEST_SUCCESS; } diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index 819d097bfa..0e7366e5e9 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -1308,6 +1308,115 @@ out: return ret; } +static int +fbarray_find_biggest(struct rte_fbarray *arr, unsigned int start, bool used, + bool rev) +{ + int cur_idx, next_idx, cur_len, biggest_idx, biggest_len; + /* don't stack if conditions, use function pointers instead */ + int (*find_func)(struct rte_fbarray *, unsigned int); + int (*find_contig_func)(struct rte_fbarray *, unsigned int); + + if (arr == NULL || start >= arr->len) { + rte_errno = EINVAL; + return -1; + } + /* the other API calls already do their fair share of cheap checks, so + * no need to do them here. + */ + + /* the API's called are thread-safe, but something may still happen + * inbetween the API calls, so lock the fbarray. all other API's are + * read-locking the fbarray, so read lock here is OK. + */ + rte_rwlock_read_lock(&arr->rwlock); + + /* pick out appropriate functions */ + if (used) { + if (rev) { + find_func = rte_fbarray_find_prev_used; + find_contig_func = rte_fbarray_find_rev_contig_used; + } else { + find_func = rte_fbarray_find_next_used; + find_contig_func = rte_fbarray_find_contig_used; + } + } else { + if (rev) { + find_func = rte_fbarray_find_prev_free; + find_contig_func = rte_fbarray_find_rev_contig_free; + } else { + find_func = rte_fbarray_find_next_free; + find_contig_func = rte_fbarray_find_contig_free; + } + } + + cur_idx = start; + biggest_idx = -1; /* default is error */ + biggest_len = 0; + for (;;) { + cur_idx = find_func(arr, cur_idx); + + /* block found, check its length */ + if (cur_idx >= 0) { + cur_len = find_contig_func(arr, cur_idx); + /* decide where we go next */ + next_idx = rev ? cur_idx - cur_len : cur_idx + cur_len; + /* move current index to start of chunk */ + cur_idx = rev ? next_idx + 1 : cur_idx; + + if (cur_len > biggest_len) { + biggest_idx = cur_idx; + biggest_len = cur_len; + } + cur_idx = next_idx; + /* in reverse mode, next_idx may be -1 if chunk started + * at array beginning. this means there's no more work + * to do. + */ + if (cur_idx < 0) + break; + } else { + /* nothing more to find, stop. however, a failed API + * call has set rte_errno, which we want to ignore, as + * reaching the end of fbarray is not an error. + */ + rte_errno = 0; + break; + } + } + /* if we didn't find anything at all, set rte_errno */ + if (biggest_idx < 0) + rte_errno = used ? ENOENT : ENOSPC; + + rte_rwlock_read_unlock(&arr->rwlock); + return biggest_idx; +} + +int __rte_experimental +rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_biggest(arr, start, false, false); +} + +int __rte_experimental +rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_biggest(arr, start, true, false); +} + +int __rte_experimental +rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_biggest(arr, start, false, true); +} + +int __rte_experimental +rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_biggest(arr, start, true, true); +} + + int __rte_experimental rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) { diff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h index 5d88055153..33841ca9a6 100644 --- a/lib/librte_eal/common/include/rte_fbarray.h +++ b/lib/librte_eal/common/include/rte_fbarray.h @@ -451,6 +451,76 @@ int __rte_experimental rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start); +/** + * Find index of biggest chunk of free elements, starting at specified index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start); + + +/** + * Find index of biggest chunk of used elements, starting at specified index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start); + + +/** + * Find index of biggest chunk of free elements before a specified index (like + * ``rte_fbarray_find_biggest_free``, but going in reverse). + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start); + + +/** + * Find index of biggest chunk of used elements before a specified index (like + * ``rte_fbarray_find_biggest_used``, but going in reverse). + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start); + + /** * Dump ``rte_fbarray`` metadata. * diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map index 8d1269e5db..0c69af073c 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -305,6 +305,8 @@ EXPERIMENTAL { rte_fbarray_detach; rte_fbarray_dump_metadata; rte_fbarray_find_idx; + rte_fbarray_find_biggest_free; + rte_fbarray_find_biggest_used; rte_fbarray_find_next_free; rte_fbarray_find_next_used; rte_fbarray_find_next_n_free; @@ -315,6 +317,8 @@ EXPERIMENTAL { rte_fbarray_find_prev_n_used; rte_fbarray_find_contig_free; rte_fbarray_find_contig_used; + rte_fbarray_find_rev_biggest_free; + rte_fbarray_find_rev_biggest_used; rte_fbarray_find_rev_contig_free; rte_fbarray_find_rev_contig_used; rte_fbarray_get; -- 2.20.1