Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/32468/?format=api
{ "id": 32468, "url": "https://patches.dpdk.org/api/patches/32468/?format=api", "web_url": "https://patches.dpdk.org/project/dpdk/patch/ee393950b6b2038a9d98b210bb8fd46c2174804a.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": "<ee393950b6b2038a9d98b210bb8fd46c2174804a.1513681966.git.anatoly.burakov@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/ee393950b6b2038a9d98b210bb8fd46c2174804a.1513681966.git.anatoly.burakov@intel.com", "date": "2017-12-19T11:14:33", "name": "[dpdk-dev,RFC,v2,06/23] eal: make malloc a doubly-linked list", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "cc9589b2ba10aa1fe2e2c07b9f0b30e2e009b881", "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/ee393950b6b2038a9d98b210bb8fd46c2174804a.1513681966.git.anatoly.burakov@intel.com/mbox/", "series": [], "comments": "https://patches.dpdk.org/api/patches/32468/comments/", "check": "fail", "checks": "https://patches.dpdk.org/api/patches/32468/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 93A1C1B1D8;\n\tTue, 19 Dec 2017 12:15:24 +0100 (CET)", "from mga01.intel.com (mga01.intel.com [192.55.52.88])\n\tby dpdk.org (Postfix) with ESMTP id 911561B020\n\tfor <dev@dpdk.org>; Tue, 19 Dec 2017 12:14:56 +0100 (CET)", "from fmsmga007.fm.intel.com ([10.253.24.52])\n\tby fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t19 Dec 2017 03:14:54 -0800", "from irvmail001.ir.intel.com ([163.33.26.43])\n\tby fmsmga007.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\tvBJBEphN003101; 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 vBJBEpLZ010215;\n\tTue, 19 Dec 2017 11:14:51 GMT", "(from aburakov@localhost)\n\tby sivswdev01.ir.intel.com with LOCAL id vBJBEpkk010211;\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=\"3584772\"", "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:33 +0000", "Message-Id": "<ee393950b6b2038a9d98b210bb8fd46c2174804a.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 06/23] eal: make malloc a doubly-linked list", "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": "As we are preparing for dynamic memory allocation, we need to be\nable to handle holes in our malloc heap, hence we're switching to\ndoubly linked list, and prepare infrastructure to support it.\n\nSince our heap is now aware where are our first and last elements,\nthere is no longer any need to have a dummy element at the end of\neach heap, so get rid of that as well. Instead, let insert/remove/\njoin/split operations handle end-of-list conditions automatically.\n\nSigned-off-by: Anatoly Burakov <anatoly.burakov@intel.com>\n---\n lib/librte_eal/common/include/rte_malloc_heap.h | 6 +\n lib/librte_eal/common/malloc_elem.c | 196 +++++++++++++++++++-----\n lib/librte_eal/common/malloc_elem.h | 7 +-\n lib/librte_eal/common/malloc_heap.c | 8 +-\n 4 files changed, 170 insertions(+), 47 deletions(-)", "diff": "diff --git a/lib/librte_eal/common/include/rte_malloc_heap.h b/lib/librte_eal/common/include/rte_malloc_heap.h\nindex b270356..48a46c9 100644\n--- a/lib/librte_eal/common/include/rte_malloc_heap.h\n+++ b/lib/librte_eal/common/include/rte_malloc_heap.h\n@@ -42,12 +42,18 @@\n /* Number of free lists per heap, grouped by size. */\n #define RTE_HEAP_NUM_FREELISTS 13\n \n+/* dummy definition, for pointers */\n+struct malloc_elem;\n+\n /**\n * Structure to hold malloc heap\n */\n struct malloc_heap {\n \trte_spinlock_t lock;\n \tLIST_HEAD(, malloc_elem) free_head[RTE_HEAP_NUM_FREELISTS];\n+\tstruct malloc_elem *first;\n+\tstruct malloc_elem *last;\n+\n \tunsigned alloc_count;\n \tsize_t total_size;\n } __rte_cache_aligned;\ndiff --git a/lib/librte_eal/common/malloc_elem.c b/lib/librte_eal/common/malloc_elem.c\nindex 6b4f2a5..7609a9b 100644\n--- a/lib/librte_eal/common/malloc_elem.c\n+++ b/lib/librte_eal/common/malloc_elem.c\n@@ -60,6 +60,7 @@ malloc_elem_init(struct malloc_elem *elem,\n \telem->heap = heap;\n \telem->ms = ms;\n \telem->prev = NULL;\n+\telem->next = NULL;\n \tmemset(&elem->free_list, 0, sizeof(elem->free_list));\n \telem->state = ELEM_FREE;\n \telem->size = size;\n@@ -68,15 +69,56 @@ malloc_elem_init(struct malloc_elem *elem,\n \tset_trailer(elem);\n }\n \n-/*\n- * Initialize a dummy malloc_elem header for the end-of-memseg marker\n- */\n void\n-malloc_elem_mkend(struct malloc_elem *elem, struct malloc_elem *prev)\n+malloc_elem_insert(struct malloc_elem *elem)\n {\n-\tmalloc_elem_init(elem, prev->heap, prev->ms, 0);\n-\telem->prev = prev;\n-\telem->state = ELEM_BUSY; /* mark busy so its never merged */\n+\tstruct malloc_elem *prev_elem, *next_elem;\n+\tstruct malloc_heap *heap = elem->heap;\n+\n+\tif (heap->first == NULL && heap->last == NULL) {\n+\t\t/* if empty heap */\n+\t\theap->first = elem;\n+\t\theap->last = elem;\n+\t\tprev_elem = NULL;\n+\t\tnext_elem = NULL;\n+\t} else if (elem < heap->first) {\n+\t\t/* if lower than start */\n+\t\tprev_elem = NULL;\n+\t\tnext_elem = heap->first;\n+\t\theap->first = elem;\n+\t} else if (elem > heap->last) {\n+\t\t/* if higher than end */\n+\t\tprev_elem = heap->last;\n+\t\tnext_elem = NULL;\n+\t\theap->last = elem;\n+\t} else {\n+\t\t/* the new memory is somewhere inbetween start and end */\n+\t\tuint64_t dist_from_start, dist_from_end;\n+\n+\t\tdist_from_end = RTE_PTR_DIFF(heap->last, elem);\n+\t\tdist_from_start = RTE_PTR_DIFF(elem, heap->first);\n+\n+\t\t/* check which is closer, and find closest list entries */\n+\t\tif (dist_from_start < dist_from_end) {\n+\t\t\tprev_elem = heap->first;\n+\t\t\twhile (prev_elem->next < elem)\n+\t\t\t\tprev_elem = prev_elem->next;\n+\t\t\tnext_elem = prev_elem->next;\n+\t\t} else {\n+\t\t\tnext_elem = heap->last;\n+\t\t\twhile (next_elem->prev > elem)\n+\t\t\t\tnext_elem = next_elem->prev;\n+\t\t\tprev_elem = next_elem->prev;\n+\t\t}\n+\t}\n+\n+\t/* insert new element */\n+\telem->prev = prev_elem;\n+\telem->next = next_elem;\n+\tif (prev_elem)\n+\t\tprev_elem->next = elem;\n+\tif (next_elem)\n+\t\tnext_elem->prev = elem;\n }\n \n /*\n@@ -126,18 +168,55 @@ malloc_elem_can_hold(struct malloc_elem *elem, size_t size,\tunsigned align,\n static void\n split_elem(struct malloc_elem *elem, struct malloc_elem *split_pt)\n {\n-\tstruct malloc_elem *next_elem = RTE_PTR_ADD(elem, elem->size);\n+\tstruct malloc_elem *next_elem = elem->next;\n \tconst size_t old_elem_size = (uintptr_t)split_pt - (uintptr_t)elem;\n \tconst size_t new_elem_size = elem->size - old_elem_size;\n \n \tmalloc_elem_init(split_pt, elem->heap, elem->ms, new_elem_size);\n \tsplit_pt->prev = elem;\n-\tnext_elem->prev = split_pt;\n+\tsplit_pt->next = next_elem;\n+\tif (next_elem)\n+\t\tnext_elem->prev = split_pt;\n+\telse\n+\t\telem->heap->last = split_pt;\n+\telem->next = split_pt;\n \telem->size = old_elem_size;\n \tset_trailer(elem);\n }\n \n /*\n+ * our malloc heap is a doubly linked list, so doubly remove our element.\n+ */\n+static void __rte_unused\n+remove_elem(struct malloc_elem *elem) {\n+\tstruct malloc_elem *next, *prev;\n+\tnext = elem->next;\n+\tprev = elem->prev;\n+\n+\tif (next)\n+\t\tnext->prev = prev;\n+\telse\n+\t\telem->heap->last = prev;\n+\tif (prev)\n+\t\tprev->next = next;\n+\telse\n+\t\telem->heap->first = next;\n+\n+\telem->prev = NULL;\n+\telem->next = NULL;\n+}\n+\n+static int\n+next_elem_is_adjacent(struct malloc_elem *elem) {\n+\treturn elem->next == RTE_PTR_ADD(elem, elem->size);\n+}\n+\n+static int\n+prev_elem_is_adjacent(struct malloc_elem *elem) {\n+\treturn elem == RTE_PTR_ADD(elem->prev, elem->prev->size);\n+}\n+\n+/*\n * Given an element size, compute its freelist index.\n * We free an element into the freelist containing similarly-sized elements.\n * We try to allocate elements starting with the freelist containing\n@@ -220,6 +299,9 @@ malloc_elem_alloc(struct malloc_elem *elem, size_t size, unsigned align,\n \n \t\tsplit_elem(elem, new_free_elem);\n \t\tmalloc_elem_free_list_insert(new_free_elem);\n+\n+\t\tif (elem == elem->heap->last)\n+\t\t\telem->heap->last = new_free_elem;\n \t}\n \n \tif (old_elem_size < MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE) {\n@@ -258,9 +340,61 @@ malloc_elem_alloc(struct malloc_elem *elem, size_t size, unsigned align,\n static inline void\n join_elem(struct malloc_elem *elem1, struct malloc_elem *elem2)\n {\n-\tstruct malloc_elem *next = RTE_PTR_ADD(elem2, elem2->size);\n+\tstruct malloc_elem *next = elem2->next;\n \telem1->size += elem2->size;\n-\tnext->prev = elem1;\n+\tif (next)\n+\t\tnext->prev = elem1;\n+\telse\n+\t\telem1->heap->last = elem1;\n+\telem1->next = next;\n+}\n+\n+static struct malloc_elem *\n+elem_join_adjacent_free(struct malloc_elem *elem) {\n+\t/*\n+\t * check if next element exists, is adjacent and is free, if so join\n+\t * with it, need to remove from free list.\n+\t */\n+\tif (elem->next != NULL && elem->next->state == ELEM_FREE &&\n+\t\t\tnext_elem_is_adjacent(elem)){\n+\t\tvoid *erase;\n+\n+\t\t/* we will want to erase the trailer and header */\n+\t\terase = RTE_PTR_SUB(elem->next, MALLOC_ELEM_TRAILER_LEN);\n+\n+\t\t/* remove from free list, join to this one */\n+\t\telem_free_list_remove(elem->next);\n+\t\tjoin_elem(elem, elem->next);\n+\n+\t\t/* erase header and trailer */\n+\t\tmemset(erase, 0, MALLOC_ELEM_OVERHEAD);\n+\t}\n+\n+\t/*\n+\t * check if prev element exists, is adjacent and is free, if so join\n+\t * with it, need to remove from free list.\n+\t */\n+\tif (elem->prev != NULL && elem->prev->state == ELEM_FREE &&\n+\t\t\tprev_elem_is_adjacent(elem)) {\n+\t\tstruct malloc_elem *new_elem;\n+\t\tvoid *erase;\n+\n+\t\t/* we will want to erase trailer and header */\n+\t\terase = RTE_PTR_SUB(elem, MALLOC_ELEM_TRAILER_LEN);\n+\n+\t\t/* remove from free list, join to this one */\n+\t\telem_free_list_remove(elem->prev);\n+\n+\t\tnew_elem = elem->prev;\n+\t\tjoin_elem(new_elem, elem);\n+\n+\t\t/* erase header and trailer */\n+\t\tmemset(erase, 0, MALLOC_ELEM_OVERHEAD);\n+\n+\t\telem = new_elem;\n+\t}\n+\n+\treturn elem;\n }\n \n /*\n@@ -271,32 +405,20 @@ join_elem(struct malloc_elem *elem1, struct malloc_elem *elem2)\n int\n malloc_elem_free(struct malloc_elem *elem)\n {\n-\tsize_t sz = elem->size - sizeof(*elem) - MALLOC_ELEM_TRAILER_LEN;\n-\tuint8_t *ptr = (uint8_t *)&elem[1];\n-\tstruct malloc_elem *next = RTE_PTR_ADD(elem, elem->size);\n-\tif (next->state == ELEM_FREE){\n-\t\t/* remove from free list, join to this one */\n-\t\telem_free_list_remove(next);\n-\t\tjoin_elem(elem, next);\n-\t\tsz += (sizeof(*elem) + MALLOC_ELEM_TRAILER_LEN);\n-\t}\n+\tvoid *ptr;\n+\tsize_t data_len;\n+\n+\tptr = RTE_PTR_ADD(elem, sizeof(*elem));\n+\tdata_len = elem->size - MALLOC_ELEM_OVERHEAD;\n+\n+\telem = elem_join_adjacent_free(elem);\n \n-\t/* check if previous element is free, if so join with it and return,\n-\t * need to re-insert in free list, as that element's size is changing\n-\t */\n-\tif (elem->prev != NULL && elem->prev->state == ELEM_FREE) {\n-\t\telem_free_list_remove(elem->prev);\n-\t\tjoin_elem(elem->prev, elem);\n-\t\tsz += (sizeof(*elem) + MALLOC_ELEM_TRAILER_LEN);\n-\t\tptr -= (sizeof(*elem) + MALLOC_ELEM_TRAILER_LEN);\n-\t\telem = elem->prev;\n-\t}\n \tmalloc_elem_free_list_insert(elem);\n \n \t/* decrease heap's count of allocated elements */\n \telem->heap->alloc_count--;\n \n-\tmemset(ptr, 0, sz);\n+\tmemset(ptr, 0, data_len);\n \n \treturn 0;\n }\n@@ -309,21 +431,23 @@ int\n malloc_elem_resize(struct malloc_elem *elem, size_t size)\n {\n \tconst size_t new_size = size + elem->pad + MALLOC_ELEM_OVERHEAD;\n+\n \t/* if we request a smaller size, then always return ok */\n \tif (elem->size >= new_size)\n \t\treturn 0;\n \n-\tstruct malloc_elem *next = RTE_PTR_ADD(elem, elem->size);\n-\tif (next ->state != ELEM_FREE)\n+\t/* check if there is a next element, it's free and adjacent */\n+\tif (!elem->next || elem->next->state != ELEM_FREE ||\n+\t\t\t!next_elem_is_adjacent(elem))\n \t\treturn -1;\n-\tif (elem->size + next->size < new_size)\n+\tif (elem->size + elem->next->size < new_size)\n \t\treturn -1;\n \n \t/* we now know the element fits, so remove from free list,\n \t * join the two\n \t */\n-\telem_free_list_remove(next);\n-\tjoin_elem(elem, next);\n+\telem_free_list_remove(elem->next);\n+\tjoin_elem(elem, elem->next);\n \n \tif (elem->size - new_size >= MIN_DATA_SIZE + MALLOC_ELEM_OVERHEAD) {\n \t\t/* now we have a big block together. Lets cut it down a bit, by splitting */\ndiff --git a/lib/librte_eal/common/malloc_elem.h b/lib/librte_eal/common/malloc_elem.h\nindex ce39129..b3d39c0 100644\n--- a/lib/librte_eal/common/malloc_elem.h\n+++ b/lib/librte_eal/common/malloc_elem.h\n@@ -48,6 +48,7 @@ enum elem_state {\n struct malloc_elem {\n \tstruct malloc_heap *heap;\n \tstruct malloc_elem *volatile prev; /* points to prev elem in memseg */\n+\tstruct malloc_elem *volatile next; /* points to next elem in memseg */\n \tLIST_ENTRY(malloc_elem) free_list; /* list of free elements in heap */\n \tconst struct rte_memseg *ms;\n \tvolatile enum elem_state state;\n@@ -139,12 +140,8 @@ malloc_elem_init(struct malloc_elem *elem,\n \t\tconst struct rte_memseg *ms,\n \t\tsize_t size);\n \n-/*\n- * initialise a dummy malloc_elem header for the end-of-memseg marker\n- */\n void\n-malloc_elem_mkend(struct malloc_elem *elem,\n-\t\tstruct malloc_elem *prev_free);\n+malloc_elem_insert(struct malloc_elem *elem);\n \n /*\n * return true if the current malloc_elem can hold a block of data\ndiff --git a/lib/librte_eal/common/malloc_heap.c b/lib/librte_eal/common/malloc_heap.c\nindex b3a1043..1b35468 100644\n--- a/lib/librte_eal/common/malloc_heap.c\n+++ b/lib/librte_eal/common/malloc_heap.c\n@@ -99,15 +99,11 @@ check_hugepage_sz(unsigned flags, uint64_t hugepage_sz)\n static void\n malloc_heap_add_memseg(struct malloc_heap *heap, struct rte_memseg *ms)\n {\n-\t/* allocate the memory block headers, one at end, one at start */\n \tstruct malloc_elem *start_elem = (struct malloc_elem *)ms->addr;\n-\tstruct malloc_elem *end_elem = RTE_PTR_ADD(ms->addr,\n-\t\t\tms->len - MALLOC_ELEM_OVERHEAD);\n-\tend_elem = RTE_PTR_ALIGN_FLOOR(end_elem, RTE_CACHE_LINE_SIZE);\n-\tconst size_t elem_size = (uintptr_t)end_elem - (uintptr_t)start_elem;\n+\tconst size_t elem_size = ms->len - MALLOC_ELEM_OVERHEAD;\n \n \tmalloc_elem_init(start_elem, heap, ms, elem_size);\n-\tmalloc_elem_mkend(end_elem, start_elem);\n+\tmalloc_elem_insert(start_elem);\n \tmalloc_elem_free_list_insert(start_elem);\n \n \theap->total_size += elem_size;\n", "prefixes": [ "dpdk-dev", "RFC", "v2", "06/23" ] }