Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/32462/?format=api
{ "id": 32462, "url": "https://patches.dpdk.org/api/patches/32462/?format=api", "web_url": "https://patches.dpdk.org/project/dpdk/patch/ce35beab540a3fa5e8927dadf368f70b88ffa9da.1513681966.git.anatoly.burakov@intel.com/", "project": { "id": 1, "url": "https://patches.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": "<ce35beab540a3fa5e8927dadf368f70b88ffa9da.1513681966.git.anatoly.burakov@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/ce35beab540a3fa5e8927dadf368f70b88ffa9da.1513681966.git.anatoly.burakov@intel.com", "date": "2017-12-19T11:14:30", "name": "[dpdk-dev,RFC,v2,03/23] eal: add rte_fbarray", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "0ef938d2f46e6631ba937c104d5393c93de1e52f", "submitter": { "id": 4, "url": "https://patches.dpdk.org/api/people/4/?format=api", "name": "Anatoly Burakov", "email": "anatoly.burakov@intel.com" }, "delegate": null, "mbox": "https://patches.dpdk.org/project/dpdk/patch/ce35beab540a3fa5e8927dadf368f70b88ffa9da.1513681966.git.anatoly.burakov@intel.com/mbox/", "series": [], "comments": "https://patches.dpdk.org/api/patches/32462/comments/", "check": "fail", "checks": "https://patches.dpdk.org/api/patches/32462/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 245121B1C3;\n\tTue, 19 Dec 2017 12:15:15 +0100 (CET)", "from mga01.intel.com (mga01.intel.com [192.55.52.88])\n\tby dpdk.org (Postfix) with ESMTP id 638551B017\n\tfor <dev@dpdk.org>; Tue, 19 Dec 2017 12:14:55 +0100 (CET)", "from fmsmga006.fm.intel.com ([10.253.24.20])\n\tby fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t19 Dec 2017 03:14:53 -0800", "from irvmail001.ir.intel.com ([163.33.26.43])\n\tby fmsmga006.fm.intel.com with ESMTP; 19 Dec 2017 03:14:52 -0800", "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\tvBJBEp2K003092; Tue, 19 Dec 2017 11:14:51 GMT", "from sivswdev01.ir.intel.com (localhost [127.0.0.1])\n\tby sivswdev01.ir.intel.com with ESMTP id vBJBEpeo010192;\n\tTue, 19 Dec 2017 11:14:51 GMT", "(from aburakov@localhost)\n\tby sivswdev01.ir.intel.com with LOCAL id vBJBEpRi010188;\n\tTue, 19 Dec 2017 11:14:51 GMT" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.45,426,1508828400\"; d=\"scan'208\";a=\"188280521\"", "From": "Anatoly Burakov <anatoly.burakov@intel.com>", "To": "dev@dpdk.org", "Cc": "andras.kovacs@ericsson.com, laszlo.vadkeri@ericsson.com,\n\tkeith.wiles@intel.com, benjamin.walker@intel.com,\n\tbruce.richardson@intel.com, thomas@monjalon.net", "Date": "Tue, 19 Dec 2017 11:14:30 +0000", "Message-Id": "<ce35beab540a3fa5e8927dadf368f70b88ffa9da.1513681966.git.anatoly.burakov@intel.com>", "X-Mailer": "git-send-email 1.7.0.7", "In-Reply-To": [ "<cover.1513681966.git.anatoly.burakov@intel.com>", "<cover.1513681966.git.anatoly.burakov@intel.com>" ], "References": [ "<cover.1513681966.git.anatoly.burakov@intel.com>", "<cover.1513681966.git.anatoly.burakov@intel.com>" ], "Subject": "[dpdk-dev] [RFC v2 03/23] eal: add rte_fbarray", "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": "rte_fbarray is a simple resizable array, not unlike vectors in\nhigher-level languages. Rationale for its existence is the\nfollowing: since we are going to map memory page-by-page, there\ncould be quite a lot of memory segments to keep track of (for\nsmaller page sizes, page count can easily reach thousands). We\ncan't really make page lists truly dynamic and infinitely expandable,\nbecause that involves reallocating memory (which is a big no-no in\nmultiprocess). What we can do instead is have a maximum capacity as\nsomething really, really large, and preallocate address space for\nthat, but only use a small portion of that memory as needed, via\nmmap()'ing portions of the address space to an actual file. This\nalso doubles as a mechanism to share fbarrays between processes\n(although multiprocess is neither implemented nor tested at the\nmoment). Hence the name: file-backed array.\n\nIn addition, in understanding that we will frequently need to scan\nthis array for free space and iterating over array linearly can\nbecome slow, rte_fbarray provides facilities to index array's\nusage. The following use cases are covered:\n - find next free/used slot (useful either for adding new elements\n to fbarray, or walking the list)\n - find starting index for next N free/used slots (useful for when\n we want to allocate chunk of VA-contiguous memory composed of\n several pages)\n - find how many contiguous free/used slots there are, starting\n from specified index (useful for when we want to figure out\n how many pages we have until next hole in allocated memory, to\n speed up some bulk operations where we would otherwise have to\n walk the array and add pages one by one)\n\nThis is accomplished by storing a usage mask in-memory, right\nafter the data section of the array, and using some bit-level\nmagic to figure out the info we need.\n\nrte_fbarray is a bit clunky to use and its primary purpose is to\nbe used within EAL for certain things, but hopefully it is (or\ncan be made so) generic enough to be useful in other contexts.\n\nNote that current implementation is leaking fd's whenever new\nallocations happen.\n\nSigned-off-by: Anatoly Burakov <anatoly.burakov@intel.com>\n---\n lib/librte_eal/common/Makefile | 2 +-\n lib/librte_eal/common/eal_common_fbarray.c | 585 ++++++++++++++++++++++++++++\n lib/librte_eal/common/eal_filesystem.h | 13 +\n lib/librte_eal/common/include/rte_fbarray.h | 98 +++++\n lib/librte_eal/linuxapp/eal/Makefile | 1 +\n 5 files changed, 698 insertions(+), 1 deletion(-)\n create mode 100755 lib/librte_eal/common/eal_common_fbarray.c\n create mode 100755 lib/librte_eal/common/include/rte_fbarray.h", "diff": "diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile\nindex 9effd0d..7868698 100644\n--- a/lib/librte_eal/common/Makefile\n+++ b/lib/librte_eal/common/Makefile\n@@ -43,7 +43,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h rte_dev.h\n INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h\n INC += rte_malloc.h rte_keepalive.h rte_time.h\n INC += rte_service.h rte_service_component.h\n-INC += rte_bitmap.h rte_vfio.h\n+INC += rte_bitmap.h rte_vfio.h rte_fbarray.h\n \n GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h\n GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h\ndiff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c\nnew file mode 100755\nindex 0000000..6e71909\n--- /dev/null\n+++ b/lib/librte_eal/common/eal_common_fbarray.c\n@@ -0,0 +1,585 @@\n+/*-\n+ * BSD LICENSE\n+ *\n+ * Copyright(c) 2017 Intel Corporation. All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or without\n+ * modification, are permitted provided that the following conditions\n+ * are met:\n+ *\n+ * * Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ * * Redistributions in binary form must reproduce the above copyright\n+ * notice, this list of conditions and the following disclaimer in\n+ * the documentation and/or other materials provided with the\n+ * distribution.\n+ * * Neither the name of Intel Corporation nor the names of its\n+ * contributors may be used to endorse or promote products derived\n+ * from this software without specific prior written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\n+ * \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\n+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\n+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\n+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\n+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+#include <inttypes.h>\n+#include <sys/mman.h>\n+#include <stdint.h>\n+#include <errno.h>\n+#include <sys/file.h>\n+#include <string.h>\n+\n+#include <rte_common.h>\n+#include <rte_log.h>\n+\n+#include \"eal_filesystem.h\"\n+#include \"eal_private.h\"\n+\n+#include \"rte_fbarray.h\"\n+\n+#define MASK_SHIFT 6ULL\n+#define MASK_ALIGN (1 << MASK_SHIFT)\n+#define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)\n+#define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN))\n+#define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod)\n+\n+/*\n+ * This is a mask that is always stored at the end of array, to provide fast\n+ * way of finding free/used spots without looping through each element.\n+ */\n+\n+struct used_mask {\n+\tint n_masks;\n+\tuint64_t data[];\n+};\n+\n+static size_t\n+calc_mask_size(int len) {\n+\treturn sizeof(struct used_mask) + sizeof(uint64_t) * MASK_LEN_TO_IDX(len);\n+}\n+\n+static size_t\n+calc_data_size(size_t page_sz, int elt_sz, int len) {\n+\tsize_t data_sz = elt_sz * len;\n+\tsize_t msk_sz = calc_mask_size(len);\n+\treturn RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);\n+}\n+\n+static struct used_mask *\n+get_used_mask(void *data, int elt_sz, int len) {\n+\treturn (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);\n+}\n+\n+static void\n+move_mask(void *data, int elt_sz, int old_len, int new_len) {\n+\tstruct used_mask *old_msk, *new_msk;\n+\n+\told_msk = get_used_mask(data, elt_sz, old_len);\n+\tnew_msk = get_used_mask(data, elt_sz, new_len);\n+\n+\tmemset(new_msk, 0, calc_mask_size(new_len));\n+\tmemcpy(new_msk, old_msk, calc_mask_size(old_len));\n+\tmemset(old_msk, 0, calc_mask_size(old_len));\n+\tnew_msk->n_masks = MASK_LEN_TO_IDX(new_len);\n+}\n+\n+static int\n+expand_and_map(void *addr, const char *name, size_t old_len, size_t new_len) {\n+\tchar path[PATH_MAX];\n+\tvoid *map_addr, *adj_addr;\n+\tsize_t map_len;\n+\tint fd, ret = 0;\n+\n+\tmap_len = new_len - old_len;\n+\tadj_addr = RTE_PTR_ADD(addr, old_len);\n+\n+\teal_get_fbarray_path(path, sizeof(path), name);\n+\n+\t/* open our file */\n+\tfd = open(path, O_CREAT | O_RDWR, 0600);\n+\tif (fd < 0) {\n+\t\tRTE_LOG(ERR, EAL, \"Cannot open %s\\n\", path);\n+\t\treturn -1;\n+\t}\n+\tif (ftruncate(fd, new_len)) {\n+\t\tRTE_LOG(ERR, EAL, \"Cannot truncate %s\\n\", path);\n+\t\tret = -1;\n+\t\tgoto out;\n+\t}\n+\n+\tmap_addr = mmap(adj_addr, map_len, PROT_READ | PROT_WRITE,\n+\t\t\tMAP_SHARED | MAP_POPULATE | MAP_FIXED, fd, old_len);\n+\tif (map_addr != adj_addr) {\n+\t\tRTE_LOG(ERR, EAL, \"mmap() failed: %s\\n\", strerror(errno));\n+\t\tret = -1;\n+\t\tgoto out;\n+\t}\n+out:\n+\tclose(fd);\n+\treturn ret;\n+}\n+\n+static int\n+find_next_n(const struct used_mask *msk, int start, int n, bool used) {\n+\tint msk_idx, lookahead_idx, first, first_mod;\n+\tuint64_t first_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+\tfirst_msk = ~((1ULL << first_mod) - 1);\n+\n+\tfor (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {\n+\t\tuint64_t cur_msk, lookahead_msk;\n+\t\tint run_start, clz, left;\n+\t\tbool found = false;\n+\t\t/*\n+\t\t * The process of getting n consecutive bits for arbitrary n is\n+\t\t * 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 * rshift-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 leading zeroes (that is, count\n+\t\t * how many consecutive set bits we had starting from the\n+\t\t * end 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 right at the start, so we will do\n+\t\t * (n-k-1) rshift-ands and check if first 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/* ignore everything before start on first iteration */\n+\t\tif (msk_idx == first)\n+\t\t\tcur_msk &= first_msk;\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\tint 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}\n+\t\t\t/* we found what we were looking for */\n+\t\t\tif (tmp_msk != 0) {\n+\t\t\t\trun_start = __builtin_ctzll(tmp_msk);\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 leading zeroes on inverted mask */\n+\t\tclz = __builtin_clzll(~cur_msk);\n+\n+\t\t/* if there aren't any runs at the end either, just continue */\n+\t\tif (clz == 0)\n+\t\t\tcontinue;\n+\n+\t\t/* we have a partial run at the end, so try looking ahead */\n+\t\trun_start = MASK_ALIGN - clz;\n+\t\tleft -= clz;\n+\n+\t\tfor (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;\n+\t\t\t\tlookahead_idx++) {\n+\t\t\tint s_idx, need;\n+\t\t\tlookahead_msk = msk->data[lookahead_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\tlookahead_msk = ~lookahead_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\tlookahead_msk &= lookahead_msk >> 1ULL;\n+\n+\t\t\t/* if first bit is not set, we've lost the run */\n+\t\t\tif ((lookahead_msk & 1) == 0)\n+\t\t\t\tbreak;\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}\n+\n+\t\t/* we didn't find anything, so continue */\n+\t\tif (!found) {\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\treturn MASK_GET_IDX(msk_idx, run_start);\n+\t}\n+\treturn used ? -ENOENT : -ENOSPC;\n+}\n+\n+static int\n+find_next(const struct used_mask *msk, int start, bool used) {\n+\tint idx, first, first_mod;\n+\tuint64_t first_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+\tfirst_msk = ~((1ULL << first_mod) - 1ULL);\n+\n+\tfor (idx = first; idx < msk->n_masks; idx++) {\n+\t\tuint64_t cur = msk->data[idx];\n+\t\tint found;\n+\n+\t\t/* if we're looking for free entries, invert mask */\n+\t\tif (!used) {\n+\t\t\tcur = ~cur;\n+\t\t}\n+\n+\t\t/* ignore everything before start on first iteration */\n+\t\tif (idx == first)\n+\t\t\tcur &= first_msk;\n+\n+\t\t/* check if we have any entries */\n+\t\tif (cur == 0)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * find first set bit - that will correspond to whatever it is\n+\t\t * that we're looking for.\n+\t\t */\n+\t\tfound = __builtin_ctzll(cur);\n+\t\treturn MASK_GET_IDX(idx, found);\n+\t}\n+\treturn used ? -ENOENT : -ENOSPC;\n+}\n+\n+static int\n+find_contig(const struct used_mask *msk, int start, bool used) {\n+\tint idx, first;\n+\tint need_len, result = 0;\n+\n+\tfirst = MASK_LEN_TO_IDX(start);\n+\tfor (idx = first; idx < msk->n_masks; idx++, result += need_len) {\n+\t\tuint64_t cur = msk->data[idx];\n+\t\tint run_len;\n+\n+\t\tneed_len = MASK_ALIGN;\n+\n+\t\t/* if we're looking for free entries, invert mask */\n+\t\tif (!used) {\n+\t\t\tcur = ~cur;\n+\t\t}\n+\n+\t\t/* ignore everything before start on first iteration */\n+\t\tif (idx == first) {\n+\t\t\tcur >>= start;\n+\t\t\t/* at the start, we don't need the full mask len */\n+\t\t\tneed_len -= start;\n+\t\t}\n+\n+\t\t/* we will be looking for zeroes, so invert the mask */\n+\t\tcur = ~cur;\n+\n+\t\t/* if mask is zero, we have a complete run */\n+\t\tif (cur == 0)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * see if current run ends before mask end.\n+\t\t */\n+\t\trun_len = __builtin_ctzll(cur);\n+\n+\t\t/* add however many zeroes we've had in the last run and quit */\n+\t\tif (run_len < need_len) {\n+\t\t\tresult += run_len;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\treturn result;\n+}\n+\n+int\n+rte_fbarray_alloc(struct rte_fbarray *arr, const char *name, int cur_len,\n+\t\tint max_len, int elt_sz) {\n+\tsize_t max_mmap_len, cur_mmap_len, page_sz;\n+\tchar path[PATH_MAX];\n+\tstruct used_mask *msk;\n+\tvoid *data;\n+\n+\t// TODO: validation\n+\n+\t/* lengths must be aligned */\n+\tcur_len = RTE_ALIGN_CEIL(cur_len, MASK_ALIGN);\n+\tmax_len = RTE_ALIGN_CEIL(max_len, MASK_ALIGN);\n+\n+\tpage_sz = sysconf(_SC_PAGESIZE);\n+\n+\tcur_mmap_len = calc_data_size(page_sz, elt_sz, cur_len);\n+\tmax_mmap_len = calc_data_size(page_sz, elt_sz, max_len);\n+\n+\tdata = eal_get_virtual_area(NULL, &max_mmap_len, page_sz, 0);\n+\tif (data == NULL)\n+\t\treturn -1;\n+\n+\teal_get_fbarray_path(path, sizeof(path), name);\n+\tunlink(path);\n+\n+\tif (expand_and_map(data, name, 0, cur_mmap_len)) {\n+\t\treturn -1;\n+\t}\n+\n+\t/* populate data structure */\n+\tsnprintf(arr->name, sizeof(arr->name), \"%s\", name);\n+\tarr->data = data;\n+\tarr->capacity = max_len;\n+\tarr->len = cur_len;\n+\tarr->elt_sz = elt_sz;\n+\tarr->count = 0;\n+\n+\tmsk = get_used_mask(data, elt_sz, cur_len);\n+\tmsk->n_masks = MASK_LEN_TO_IDX(cur_len);\n+\n+\treturn 0;\n+}\n+\n+int\n+rte_fbarray_attach(const struct rte_fbarray *arr) {\n+\tuint64_t max_mmap_len, cur_mmap_len, page_sz;\n+\tvoid *data;\n+\n+\tpage_sz = sysconf(_SC_PAGESIZE);\n+\n+\tcur_mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);\n+\tmax_mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->capacity);\n+\n+\tdata = eal_get_virtual_area(arr->data, &max_mmap_len, page_sz, 0);\n+\tif (data == NULL)\n+\t\treturn -1;\n+\n+\tif (expand_and_map(data, arr->name, 0, cur_mmap_len)) {\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+void\n+rte_fbarray_free(struct rte_fbarray *arr) {\n+\tsize_t page_sz = sysconf(_SC_PAGESIZE);\n+\tmunmap(arr->data, calc_data_size(page_sz, arr->elt_sz, arr->capacity));\n+\tmemset(arr, 0, sizeof(*arr));\n+}\n+\n+int\n+rte_fbarray_resize(struct rte_fbarray *arr, int new_len) {\n+\tsize_t cur_mmap_len, new_mmap_len, page_sz;\n+\n+\t// TODO: validation\n+\tif (arr->len >= new_len) {\n+\t\tRTE_LOG(ERR, EAL, \"Invalid length: %i >= %i\\n\", arr->len, new_len);\n+\t\treturn -1;\n+\t}\n+\n+\tpage_sz = sysconf(_SC_PAGESIZE);\n+\n+\tnew_len = RTE_ALIGN_CEIL(new_len, MASK_ALIGN);\n+\n+\tcur_mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);\n+\tnew_mmap_len = calc_data_size(page_sz, arr->elt_sz, new_len);\n+\n+\tif (cur_mmap_len != new_mmap_len &&\n+\t\t\texpand_and_map(arr->data, arr->name, cur_mmap_len,\n+\t\t\t\tnew_mmap_len)) {\n+\t\treturn -1;\n+\t}\n+\n+\tmove_mask(arr->data, arr->elt_sz, arr->len, new_len);\n+\n+\tarr->len = new_len;\n+\n+\treturn 0;\n+}\n+\n+void *\n+rte_fbarray_get(const struct rte_fbarray *arr, int idx) {\n+\tif (idx >= arr->len || idx < 0)\n+\t\treturn NULL;\n+\treturn RTE_PTR_ADD(arr->data, idx * arr->elt_sz);\n+}\n+\n+// TODO: replace -1 with debug sanity checks\n+int\n+rte_fbarray_set_used(struct rte_fbarray *arr, int idx, bool used) {\n+\tstruct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, arr->len);\n+\tbool already_used;\n+\tint msk_idx = MASK_LEN_TO_IDX(idx);\n+\tuint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);\n+\n+\tif (idx >= arr->len || idx < 0)\n+\t\treturn -1;\n+\n+\talready_used = (msk->data[msk_idx] & msk_bit) != 0;\n+\n+\t/* nothing to be done */\n+\tif (used == already_used)\n+\t\treturn 0;\n+\n+\tif (used) {\n+\t\tmsk->data[msk_idx] |= msk_bit;\n+\t\tarr->count++;\n+\t} else {\n+\t\tmsk->data[msk_idx] &= ~msk_bit;\n+\t\tarr->count--;\n+\t}\n+\n+\treturn 0;\n+}\n+int\n+rte_fbarray_is_used(const struct rte_fbarray *arr, int idx) {\n+\tstruct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, arr->len);\n+\tint msk_idx = MASK_LEN_TO_IDX(idx);\n+\tuint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);\n+\n+\tif (idx >= arr->len || idx < 0)\n+\t\treturn -1;\n+\n+\treturn (msk->data[msk_idx] & msk_bit) != 0;\n+}\n+\n+int\n+rte_fbarray_find_next_free(const struct rte_fbarray *arr, int start) {\n+\tif (start >= arr->len || start < 0)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->len == arr->count)\n+\t\treturn -ENOSPC;\n+\n+\treturn find_next(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, false);\n+}\n+\n+int\n+rte_fbarray_find_next_used(const struct rte_fbarray *arr, int start) {\n+\tif (start >= arr->len || start < 0)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->count == 0)\n+\t\treturn -1;\n+\n+\treturn find_next(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, true);\n+}\n+\n+int\n+rte_fbarray_find_next_n_free(const struct rte_fbarray *arr, int start, int n) {\n+\tif (start >= arr->len || start < 0 || n > arr->len)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->len == arr->count || arr->len - arr->count < n)\n+\t\treturn -ENOSPC;\n+\n+\treturn find_next_n(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, n, false);\n+}\n+\n+int\n+rte_fbarray_find_next_n_used(const struct rte_fbarray *arr, int start, int n) {\n+\tif (start >= arr->len || start < 0 || n > arr->len)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->count < n)\n+\t\treturn -ENOENT;\n+\n+\treturn find_next_n(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, n, true);\n+}\n+\n+int\n+rte_fbarray_find_contig_free(const struct rte_fbarray *arr, int start) {\n+\tif (start >= arr->len || start < 0)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->len == arr->count)\n+\t\treturn -ENOSPC;\n+\n+\tif (arr->count == 0)\n+\t\treturn arr->len - start;\n+\n+\treturn find_contig(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, false);\n+}\n+\n+int\n+rte_fbarray_find_contig_used(const struct rte_fbarray *arr, int start) {\n+\tif (start >= arr->len || start < 0)\n+\t\treturn -EINVAL;\n+\n+\tif (arr->count == 0)\n+\t\treturn -ENOENT;\n+\n+\treturn find_contig(get_used_mask(arr->data, arr->elt_sz, arr->len),\n+\t\t\tstart, true);\n+}\n+\n+int\n+rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt) {\n+\tvoid *end;\n+\n+\tend = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);\n+\n+\tif (elt < arr->data || elt >= end)\n+\t\treturn -EINVAL;\n+\treturn RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;\n+}\n+\n+void\n+rte_fbarray_dump_metadata(const struct rte_fbarray *arr, FILE *f) {\n+\tconst struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, arr->len);\n+\n+\tfprintf(f, \"File-backed array: %s\\n\", arr->name);\n+\tfprintf(f, \"size: %i occupied: %i capacity: %i elt_sz: %i\\n\",\n+\t arr->len, arr->count, arr->capacity, arr->elt_sz);\n+\tif (!arr->data) {\n+\t\tfprintf(f, \"not allocated\\n\");\n+\t\treturn;\n+\t}\n+\n+\tfor (int i = 0; i < msk->n_masks; i++) {\n+\t\tfprintf(f, \"msk idx %i: 0x%016lx\\n\", i, msk->data[i]);\n+\t}\n+}\ndiff --git a/lib/librte_eal/common/eal_filesystem.h b/lib/librte_eal/common/eal_filesystem.h\nindex 8acbd99..10e7474 100644\n--- a/lib/librte_eal/common/eal_filesystem.h\n+++ b/lib/librte_eal/common/eal_filesystem.h\n@@ -42,6 +42,7 @@\n \n /** Path of rte config file. */\n #define RUNTIME_CONFIG_FMT \"%s/.%s_config\"\n+#define FBARRAY_FMT \"%s/%s_%s\"\n \n #include <stdint.h>\n #include <limits.h>\n@@ -67,6 +68,18 @@ eal_runtime_config_path(void)\n \treturn buffer;\n }\n \n+static inline const char *\n+eal_get_fbarray_path(char *buffer, size_t buflen, const char *name) {\n+\tconst char *directory = default_config_dir;\n+\tconst char *home_dir = getenv(\"HOME\");\n+\n+\tif (getuid() != 0 && home_dir != NULL)\n+\t\tdirectory = home_dir;\n+\tsnprintf(buffer, buflen - 1, FBARRAY_FMT, directory,\n+\t\t\tinternal_config.hugefile_prefix, name);\n+\treturn buffer;\n+}\n+\n /** Path of hugepage info file. */\n #define HUGEPAGE_INFO_FMT \"%s/.%s_hugepage_info\"\n \ndiff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h\nnew file mode 100755\nindex 0000000..d06c1ac\n--- /dev/null\n+++ b/lib/librte_eal/common/include/rte_fbarray.h\n@@ -0,0 +1,98 @@\n+/*-\n+ * BSD LICENSE\n+ *\n+ * Copyright(c) 2017 Intel Corporation. All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or without\n+ * modification, are permitted provided that the following conditions\n+ * are met:\n+ *\n+ * * Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ * * Redistributions in binary form must reproduce the above copyright\n+ * notice, this list of conditions and the following disclaimer in\n+ * the documentation and/or other materials provided with the\n+ * distribution.\n+ * * Neither the name of Intel Corporation nor the names of its\n+ * contributors may be used to endorse or promote products derived\n+ * from this software without specific prior written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\n+ * \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\n+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\n+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\n+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\n+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+#ifndef RTE_FBARRAY_H\n+#define RTE_FBARRAY_H\n+\n+#include <stdbool.h>\n+#include <stdio.h>\n+\n+#define RTE_FBARRAY_NAME_LEN 64\n+\n+struct rte_fbarray {\n+\tchar name[RTE_FBARRAY_NAME_LEN]; /**< name associated with an array */\n+\tint count; /**< number of entries stored */\n+\tint len; /**< current length of the array */\n+\tint capacity; /**< maximum length of the array */\n+\tint elt_sz; /**< size of each element */\n+\tvoid *data; /**< data pointer */\n+};\n+\n+// TODO: tmp? shmget?\n+\n+int\n+rte_fbarray_alloc(struct rte_fbarray *arr, const char *name, int cur_len,\n+\t\tint max_len, int elt_sz);\n+\n+int\n+rte_fbarray_attach(const struct rte_fbarray *arr);\n+\n+void\n+rte_fbarray_free(struct rte_fbarray *arr);\n+\n+int\n+rte_fbarray_resize(struct rte_fbarray *arr, int new_len);\n+\n+void *\n+rte_fbarray_get(const struct rte_fbarray *arr, int idx);\n+\n+int\n+rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt);\n+\n+int\n+rte_fbarray_set_used(struct rte_fbarray *arr, int idx, bool used);\n+\n+int\n+rte_fbarray_is_used(const struct rte_fbarray *arr, int idx);\n+\n+int\n+rte_fbarray_find_next_free(const struct rte_fbarray *arr, int start);\n+\n+int\n+rte_fbarray_find_next_used(const struct rte_fbarray *arr, int start);\n+\n+int\n+rte_fbarray_find_next_n_free(const struct rte_fbarray *arr, int start, int n);\n+\n+int\n+rte_fbarray_find_next_n_used(const struct rte_fbarray *arr, int start, int n);\n+\n+int\n+rte_fbarray_find_contig_free(const struct rte_fbarray *arr, int start);\n+\n+int\n+rte_fbarray_find_contig_used(const struct rte_fbarray *arr, int start);\n+\n+void\n+rte_fbarray_dump_metadata(const struct rte_fbarray *arr, FILE *f);\n+\n+#endif // RTE_FBARRAY_H\ndiff --git a/lib/librte_eal/linuxapp/eal/Makefile b/lib/librte_eal/linuxapp/eal/Makefile\nindex 5a7b8b2..782e1ad 100644\n--- a/lib/librte_eal/linuxapp/eal/Makefile\n+++ b/lib/librte_eal/linuxapp/eal/Makefile\n@@ -86,6 +86,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += eal_common_dev.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += eal_common_options.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += eal_common_thread.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += eal_common_proc.c\n+SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += eal_common_fbarray.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += rte_malloc.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += malloc_elem.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUXAPP) += malloc_heap.c\n", "prefixes": [ "dpdk-dev", "RFC", "v2", "03/23" ] }