fbarray: add API to find biggest used or free chunks
authorAnatoly Burakov <anatoly.burakov@intel.com>
Fri, 22 Feb 2019 16:14:01 +0000 (16:14 +0000)
committerThomas Monjalon <thomas@monjalon.net>
Thu, 28 Mar 2019 22:28:52 +0000 (23:28 +0100)
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 <anatoly.burakov@intel.com>
app/test/test_fbarray.c
lib/librte_eal/common/eal_common_fbarray.c
lib/librte_eal/common/include/rte_fbarray.h
lib/librte_eal/rte_eal_version.map

index 8c44e2c..d2b0418 100644 (file)
@@ -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(&param.arr, param.end + 1, FBARRAY_TEST_LEN - 1,
                        false))
                return TEST_FAILED;
+       /* test if find_biggest API's work correctly */
+       if (test_biggest(&param.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(&param.arr, 0, FBARRAY_TEST_LEN - 1, false))
                return TEST_FAILED;
+       /* test if find_biggest API's work correctly */
+       if (test_biggest(&param.arr, param.start, param.end))
+               return TEST_FAILED;
        return TEST_SUCCESS;
 }
 
index 819d097..0e7366e 100644 (file)
@@ -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)
 {
index 5d88055..33841ca 100644 (file)
@@ -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.
  *
index 8d1269e..0c69af0 100644 (file)
@@ -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;