get:
Show a patch.

patch:
Update a patch.

put:
Update a patch.

GET /api/patches/40990/?format=api
HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "id": 40990,
    "url": "http://patchwork.dpdk.org/api/patches/40990/?format=api",
    "web_url": "http://patchwork.dpdk.org/project/dpdk/patch/1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com/",
    "project": {
        "id": 1,
        "url": "http://patchwork.dpdk.org/api/projects/1/?format=api",
        "name": "DPDK",
        "link_name": "dpdk",
        "list_id": "dev.dpdk.org",
        "list_email": "dev@dpdk.org",
        "web_url": "http://core.dpdk.org",
        "scm_url": "git://dpdk.org/dpdk",
        "webscm_url": "http://git.dpdk.org/dpdk",
        "list_archive_url": "https://inbox.dpdk.org/dev",
        "list_archive_url_format": "https://inbox.dpdk.org/dev/{}",
        "commit_url_format": ""
    },
    "msgid": "<1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com>",
    "list_archive_url": "https://inbox.dpdk.org/dev/1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com",
    "date": "2018-06-11T20:55:39",
    "name": "[6/9] fbarray: add reverse find n used/free",
    "commit_ref": null,
    "pull_url": null,
    "state": "accepted",
    "archived": true,
    "hash": "eb8f1c25bd9bb9acf0a3b699f44aef2dab6b91d1",
    "submitter": {
        "id": 4,
        "url": "http://patchwork.dpdk.org/api/people/4/?format=api",
        "name": "Burakov, Anatoly",
        "email": "anatoly.burakov@intel.com"
    },
    "delegate": {
        "id": 1,
        "url": "http://patchwork.dpdk.org/api/users/1/?format=api",
        "username": "tmonjalo",
        "first_name": "Thomas",
        "last_name": "Monjalon",
        "email": "thomas@monjalon.net"
    },
    "mbox": "http://patchwork.dpdk.org/project/dpdk/patch/1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com/mbox/",
    "series": [
        {
            "id": 85,
            "url": "http://patchwork.dpdk.org/api/series/85/?format=api",
            "web_url": "http://patchwork.dpdk.org/project/dpdk/list/?series=85",
            "date": "2018-06-11T20:55:33",
            "name": "mem: reduce memory fragmentation",
            "version": 1,
            "mbox": "http://patchwork.dpdk.org/series/85/mbox/"
        }
    ],
    "comments": "http://patchwork.dpdk.org/api/patches/40990/comments/",
    "check": "success",
    "checks": "http://patchwork.dpdk.org/api/patches/40990/checks/",
    "tags": {},
    "related": [],
    "headers": {
        "Return-Path": "<dev-bounces@dpdk.org>",
        "X-Original-To": "patchwork@dpdk.org",
        "Delivered-To": "patchwork@dpdk.org",
        "Received": [
            "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 2FDC21DE8D;\n\tMon, 11 Jun 2018 22:55:58 +0200 (CEST)",
            "from mga11.intel.com (mga11.intel.com [192.55.52.93])\n\tby dpdk.org (Postfix) with ESMTP id 826C81DB16\n\tfor <dev@dpdk.org>; Mon, 11 Jun 2018 22:55:46 +0200 (CEST)",
            "from fmsmga008.fm.intel.com ([10.253.24.58])\n\tby fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t11 Jun 2018 13:55:44 -0700",
            "from irvmail001.ir.intel.com ([163.33.26.43])\n\tby fmsmga008.fm.intel.com with ESMTP; 11 Jun 2018 13:55:44 -0700",
            "from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com\n\t[10.237.217.45])\n\tby irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id\n\tw5BKth4V026383 for <dev@dpdk.org>; Mon, 11 Jun 2018 21:55:43 +0100",
            "from sivswdev01.ir.intel.com (localhost [127.0.0.1])\n\tby sivswdev01.ir.intel.com with ESMTP id w5BKthAg021610\n\tfor <dev@dpdk.org>; Mon, 11 Jun 2018 21:55:43 +0100",
            "(from aburakov@localhost)\n\tby sivswdev01.ir.intel.com with LOCAL id w5BKthMn021606\n\tfor dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100"
        ],
        "X-Amp-Result": "SKIPPED(no attachment in message)",
        "X-Amp-File-Uploaded": "False",
        "X-ExtLoop1": "1",
        "X-IronPort-AV": "E=Sophos;i=\"5.51,211,1526367600\"; d=\"scan'208\";a=\"46964667\"",
        "From": "Anatoly Burakov <anatoly.burakov@intel.com>",
        "To": "dev@dpdk.org",
        "Date": "Mon, 11 Jun 2018 21:55:39 +0100",
        "Message-Id": "<1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com>",
        "X-Mailer": "git-send-email 1.7.0.7",
        "In-Reply-To": [
            "<cover.1528749451.git.anatoly.burakov@intel.com>",
            "<cover.1528749451.git.anatoly.burakov@intel.com>"
        ],
        "References": [
            "<cover.1528749451.git.anatoly.burakov@intel.com>",
            "<cover.1528749451.git.anatoly.burakov@intel.com>"
        ],
        "Subject": "[dpdk-dev] [PATCH 6/9] fbarray: add reverse find n used/free",
        "X-BeenThere": "dev@dpdk.org",
        "X-Mailman-Version": "2.1.15",
        "Precedence": "list",
        "List-Id": "DPDK patches and discussions <dev.dpdk.org>",
        "List-Unsubscribe": "<https://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>",
        "List-Archive": "<http://dpdk.org/ml/archives/dev/>",
        "List-Post": "<mailto:dev@dpdk.org>",
        "List-Help": "<mailto:dev-request@dpdk.org?subject=help>",
        "List-Subscribe": "<https://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>",
        "Errors-To": "dev-bounces@dpdk.org",
        "Sender": "\"dev\" <dev-bounces@dpdk.org>"
    },
    "content": "Add a function to look for N used/free slots, but going backwards\ninstead of forwards. All semantics are kept similar to the existing\nfunction, with the difference being that given the same input, the\nsame results will be returned in reverse order.\n\nSigned-off-by: Anatoly Burakov <anatoly.burakov@intel.com>\n---\n lib/librte_eal/common/eal_common_fbarray.c  | 198 +++++++++++++++++++-\n lib/librte_eal/common/include/rte_fbarray.h |  44 +++++\n lib/librte_eal/rte_eal_version.map          |   2 +\n 3 files changed, 237 insertions(+), 7 deletions(-)",
    "diff": "diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c\nindex d5d72e37b..a2e01148b 100644\n--- a/lib/librte_eal/common/eal_common_fbarray.c\n+++ b/lib/librte_eal/common/eal_common_fbarray.c\n@@ -352,6 +352,169 @@ find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)\n \treturn result;\n }\n \n+static int\n+find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,\n+\t\tbool used)\n+{\n+\tconst struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,\n+\t\t\tarr->len);\n+\tunsigned int msk_idx, lookbehind_idx, first, first_mod;\n+\tuint64_t ignore_msk;\n+\n+\t/*\n+\t * mask only has granularity of MASK_ALIGN, but start may not be aligned\n+\t * on that boundary, so construct a special mask to exclude anything we\n+\t * don't want to see to avoid confusing ctz.\n+\t */\n+\tfirst = MASK_LEN_TO_IDX(start);\n+\tfirst_mod = MASK_LEN_TO_MOD(start);\n+\t/* we're going backwards, so mask must start from the top */\n+\tignore_msk = first_mod == MASK_ALIGN - 1 ?\n+\t\t\t\t-1ULL : /* prevent overflow */\n+\t\t\t\t~(-1ULL << (first_mod + 1));\n+\n+\t/* go backwards, include zero */\n+\tmsk_idx = first;\n+\tdo {\n+\t\tuint64_t cur_msk, lookbehind_msk;\n+\t\tunsigned int run_start, run_end, ctz, left;\n+\t\tbool found = false;\n+\t\t/*\n+\t\t * The process of getting n consecutive bits from the top for\n+\t\t * arbitrary n is a bit involved, but here it is in a nutshell:\n+\t\t *\n+\t\t *  1. let n be the number of consecutive bits we're looking for\n+\t\t *  2. check if n can fit in one mask, and if so, do n-1\n+\t\t *     lshift-ands to see if there is an appropriate run inside\n+\t\t *     our current mask\n+\t\t *    2a. if we found a run, bail out early\n+\t\t *    2b. if we didn't find a run, proceed\n+\t\t *  3. invert the mask and count trailing zeroes (that is, count\n+\t\t *     how many consecutive set bits we had starting from the\n+\t\t *     start of current mask) as k\n+\t\t *    3a. if k is 0, continue to next mask\n+\t\t *    3b. if k is not 0, we have a potential run\n+\t\t *  4. to satisfy our requirements, next mask must have n-k\n+\t\t *     consecutive set bits at the end, so we will do (n-k-1)\n+\t\t *     lshift-ands and check if last bit is set.\n+\t\t *\n+\t\t * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until\n+\t\t * we either run out of masks, lose the run, or find what we\n+\t\t * were looking for.\n+\t\t */\n+\t\tcur_msk = msk->data[msk_idx];\n+\t\tleft = n;\n+\n+\t\t/* if we're looking for free spaces, invert the mask */\n+\t\tif (!used)\n+\t\t\tcur_msk = ~cur_msk;\n+\n+\t\t/* if we have an ignore mask, ignore once */\n+\t\tif (ignore_msk) {\n+\t\t\tcur_msk &= ignore_msk;\n+\t\t\tignore_msk = 0;\n+\t\t}\n+\n+\t\t/* if n can fit in within a single mask, do a search */\n+\t\tif (n <= MASK_ALIGN) {\n+\t\t\tuint64_t tmp_msk = cur_msk;\n+\t\t\tunsigned int s_idx;\n+\t\t\tfor (s_idx = 0; s_idx < n - 1; s_idx++)\n+\t\t\t\ttmp_msk &= tmp_msk << 1ULL;\n+\t\t\t/* we found what we were looking for */\n+\t\t\tif (tmp_msk != 0) {\n+\t\t\t\t/* clz will give us offset from end of mask, and\n+\t\t\t\t * we only get the end of our run, not start,\n+\t\t\t\t * so adjust result to point to where start\n+\t\t\t\t * would have been.\n+\t\t\t\t */\n+\t\t\t\trun_start = MASK_ALIGN -\n+\t\t\t\t\t\t__builtin_clzll(tmp_msk) - n;\n+\t\t\t\treturn MASK_GET_IDX(msk_idx, run_start);\n+\t\t\t}\n+\t\t}\n+\n+\t\t/*\n+\t\t * we didn't find our run within the mask, or n > MASK_ALIGN,\n+\t\t * so we're going for plan B.\n+\t\t */\n+\n+\t\t/* count trailing zeroes on inverted mask */\n+\t\tif (~cur_msk == 0)\n+\t\t\tctz = sizeof(cur_msk) * 8;\n+\t\telse\n+\t\t\tctz = __builtin_ctzll(~cur_msk);\n+\n+\t\t/* if there aren't any runs at the start either, just\n+\t\t * continue\n+\t\t */\n+\t\tif (ctz == 0)\n+\t\t\tcontinue;\n+\n+\t\t/* we have a partial run at the start, so try looking behind */\n+\t\trun_end = MASK_GET_IDX(msk_idx, ctz);\n+\t\tleft -= ctz;\n+\n+\t\t/* go backwards, include zero */\n+\t\tlookbehind_idx = msk_idx - 1;\n+\n+\t\t/* we can't lookbehind as we've run out of masks, so stop */\n+\t\tif (msk_idx == 0)\n+\t\t\tbreak;\n+\n+\t\tdo {\n+\t\t\tconst uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);\n+\t\t\tunsigned int s_idx, need;\n+\n+\t\t\tlookbehind_msk = msk->data[lookbehind_idx];\n+\n+\t\t\t/* if we're looking for free space, invert the mask */\n+\t\t\tif (!used)\n+\t\t\t\tlookbehind_msk = ~lookbehind_msk;\n+\n+\t\t\t/* figure out how many consecutive bits we need here */\n+\t\t\tneed = RTE_MIN(left, MASK_ALIGN);\n+\n+\t\t\tfor (s_idx = 0; s_idx < need - 1; s_idx++)\n+\t\t\t\tlookbehind_msk &= lookbehind_msk << 1ULL;\n+\n+\t\t\t/* if last bit is not set, we've lost the run */\n+\t\t\tif ((lookbehind_msk & last_bit) == 0) {\n+\t\t\t\t/*\n+\t\t\t\t * we've scanned this far, so we know there are\n+\t\t\t\t * no runs in the space we've lookbehind-scanned\n+\t\t\t\t * as well, so skip that on next iteration.\n+\t\t\t\t */\n+\t\t\t\tignore_msk = -1ULL << need;\n+\t\t\t\tmsk_idx = lookbehind_idx;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\tleft -= need;\n+\n+\t\t\t/* check if we've found what we were looking for */\n+\t\t\tif (left == 0) {\n+\t\t\t\tfound = true;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} while ((lookbehind_idx--) != 0); /* decrement after check to\n+\t\t\t\t\t\t    * include zero\n+\t\t\t\t\t\t    */\n+\n+\t\t/* we didn't find anything, so continue */\n+\t\tif (!found)\n+\t\t\tcontinue;\n+\n+\t\t/* we've found what we were looking for, but we only know where\n+\t\t * the run ended, so calculate start position.\n+\t\t */\n+\t\treturn run_end - n;\n+\t} while (msk_idx-- != 0); /* decrement after check to include zero */\n+\t/* we didn't find anything */\n+\trte_errno = used ? ENOENT : ENOSPC;\n+\treturn -1;\n+}\n+\n static int\n find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)\n {\n@@ -797,7 +960,7 @@ rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)\n \n static int\n fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,\n-\t\tbool used)\n+\t\tbool next, bool used)\n {\n \tint ret = -1;\n \n@@ -805,7 +968,11 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,\n \t\trte_errno = EINVAL;\n \t\treturn -1;\n \t}\n-\tif (arr->len - start < n) {\n+\tif (next && (arr->len - start) < n) {\n+\t\trte_errno = used ? ENOENT : ENOSPC;\n+\t\treturn -1;\n+\t}\n+\tif (!next && start < (n - 1)) {\n \t\trte_errno = used ? ENOENT : ENOSPC;\n \t\treturn -1;\n \t}\n@@ -820,7 +987,7 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,\n \t\t\tgoto out;\n \t\t}\n \t\tif (arr->count == 0) {\n-\t\t\tret = start;\n+\t\t\tret = next ? start : start - n + 1;\n \t\t\tgoto out;\n \t\t}\n \t} else {\n@@ -829,12 +996,15 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,\n \t\t\tgoto out;\n \t\t}\n \t\tif (arr->count == arr->len) {\n-\t\t\tret = start;\n+\t\t\tret = next ? start : start - n + 1;\n \t\t\tgoto out;\n \t\t}\n \t}\n \n-\tret = find_next_n(arr, start, n, used);\n+\tif (next)\n+\t\tret = find_next_n(arr, start, n, used);\n+\telse\n+\t\tret = find_prev_n(arr, start, n, used);\n out:\n \trte_rwlock_read_unlock(&arr->rwlock);\n \treturn ret;\n@@ -844,14 +1014,28 @@ int __rte_experimental\n rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,\n \t\tunsigned int n)\n {\n-\treturn fbarray_find_n(arr, start, n, false);\n+\treturn fbarray_find_n(arr, start, n, true, false);\n }\n \n int __rte_experimental\n rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,\n \t\tunsigned int n)\n {\n-\treturn fbarray_find_n(arr, start, n, true);\n+\treturn fbarray_find_n(arr, start, n, true, true);\n+}\n+\n+int __rte_experimental\n+rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,\n+\t\tunsigned int n)\n+{\n+\treturn fbarray_find_n(arr, start, n, false, false);\n+}\n+\n+int __rte_experimental\n+rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,\n+\t\tunsigned int n)\n+{\n+\treturn fbarray_find_n(arr, start, n, false, true);\n }\n \n static int\ndiff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h\nindex 54abe938a..980b4969f 100644\n--- a/lib/librte_eal/common/include/rte_fbarray.h\n+++ b/lib/librte_eal/common/include/rte_fbarray.h\n@@ -370,6 +370,50 @@ int __rte_experimental\n rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start);\n \n \n+/**\n+ * Find lowest start index of chunk of ``n`` free elements, down from specified\n+ * index.\n+ *\n+ * @param arr\n+ *   Valid pointer to allocated and correctly set up ``rte_fbarray`` structure.\n+ *\n+ * @param start\n+ *   Element index to start search from.\n+ *\n+ * @param n\n+ *   Number of free elements to look for.\n+ *\n+ * @return\n+ *  - non-negative integer on success.\n+ *  - -1 on failure, with ``rte_errno`` indicating reason for failure.\n+ */\n+int __rte_experimental\n+rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,\n+\t\tunsigned int n);\n+\n+\n+/**\n+ * Find lowest start index of chunk of ``n`` used elements, down from specified\n+ * index.\n+ *\n+ * @param arr\n+ *   Valid pointer to allocated and correctly set up ``rte_fbarray`` structure.\n+ *\n+ * @param start\n+ *   Element index to start search from.\n+ *\n+ * @param n\n+ *   Number of used elements to look for.\n+ *\n+ * @return\n+ *  - non-negative integer on success.\n+ *  - -1 on failure, with ``rte_errno`` indicating reason for failure.\n+ */\n+int __rte_experimental\n+rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,\n+\t\tunsigned int n);\n+\n+\n \n /**\n  * Dump ``rte_fbarray`` metadata.\ndiff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map\nindex 79b87f504..3a1b93e12 100644\n--- a/lib/librte_eal/rte_eal_version.map\n+++ b/lib/librte_eal/rte_eal_version.map\n@@ -271,6 +271,8 @@ EXPERIMENTAL {\n \trte_fbarray_find_next_n_used;\n \trte_fbarray_find_prev_free;\n \trte_fbarray_find_prev_used;\n+\trte_fbarray_find_prev_n_free;\n+\trte_fbarray_find_prev_n_used;\n \trte_fbarray_find_contig_free;\n \trte_fbarray_find_contig_used;\n \trte_fbarray_get;\n",
    "prefixes": [
        "6/9"
    ]
}