From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga03.intel.com (mga03.intel.com [143.182.124.21]) by dpdk.org (Postfix) with ESMTP id 4564FAFCA for ; Tue, 17 Jun 2014 18:06:32 +0200 (CEST) Received: from azsmga001.ch.intel.com ([10.2.17.19]) by azsmga101.ch.intel.com with ESMTP; 17 Jun 2014 09:05:10 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.01,494,1400050800"; d="scan'208";a="446579205" Received: from irsmsx102.ger.corp.intel.com ([163.33.3.155]) by azsmga001.ch.intel.com with ESMTP; 17 Jun 2014 09:05:08 -0700 Received: from irsmsx103.ger.corp.intel.com ([169.254.3.58]) by IRSMSX102.ger.corp.intel.com ([169.254.2.105]) with mapi id 14.03.0123.003; Tue, 17 Jun 2014 17:05:07 +0100 From: "De Lara Guarch, Pablo" To: "rsanford2@gmail.com" , "dev@dpdk.org" Thread-Topic: [dpdk-dev] [PATCH v2] malloc: fix malloc and free linear complexity Thread-Index: AQHPcQa4ByKPLA9s1kaUEL4cPFh8yJt1qExg Date: Tue, 17 Jun 2014 16:05:06 +0000 Message-ID: References: <1400245141-10938-1-git-send-email-rsanford2@gmail.com> In-Reply-To: <1400245141-10938-1-git-send-email-rsanford2@gmail.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [163.33.239.180] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v2] malloc: fix malloc and free linear complexity X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Jun 2014 16:06:33 -0000 > -----Original Message----- > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of > rsanford2@gmail.com > Sent: Friday, May 16, 2014 1:59 PM > To: dev@dpdk.org > Subject: [dpdk-dev] [PATCH v2] malloc: fix malloc and free linear complex= ity >=20 > Problems with lib rte_malloc: > 1. Rte_malloc searches a heap's entire free list looking for > the best fit, resulting in linear complexity. > 2. Heaps store free blocks in a singly-linked list, resulting > in linear complexity when rte_free needs to remove an > adjacent block. > 3. The library inserts and removes free blocks with ad hoc, > in-line code, rather than using linked-list functions or > macros. >=20 > This patch addresses those problems as follows: > 1. Replace single free list with a handful of free lists. > Each free list contains blocks of a specified size range, > for example: > list[0]: (0 , 2^7] > list[1]: (2^7 , 2^9] > list[2]: (2^9 , 2^11] > list[3]: (2^11, 2^13] > list[4]: (2^13, MAX_SIZE] >=20 > When allocating a block, start at the first list that can > contain a big enough block. Search subsequent lists, if > necessary. Terminate the search as soon as we find a block > that is big enough. > 2. Use doubly-linked lists, so that we can remove free blocks > in constant time. > 3. Use BSD LIST macros, as defined in sys/queue.h and the > QUEUE(3) man page. >=20 > Signed-off-by: Robert Sanford > --- > lib/librte_eal/common/include/rte_malloc_heap.h | 6 +- > lib/librte_malloc/malloc_elem.c | 121 +++++++++++++++--= ------ > lib/librte_malloc/malloc_elem.h | 17 +++- > lib/librte_malloc/malloc_heap.c | 67 ++++++------- > 4 files changed, 128 insertions(+), 83 deletions(-) >=20 > diff --git a/lib/librte_eal/common/include/rte_malloc_heap.h > b/lib/librte_eal/common/include/rte_malloc_heap.h > index 5e139cf..1f5d653 100644 > --- a/lib/librte_eal/common/include/rte_malloc_heap.h > +++ b/lib/librte_eal/common/include/rte_malloc_heap.h > @@ -35,14 +35,18 @@ > #define _RTE_MALLOC_HEAP_H_ >=20 > #include > +#include > #include >=20 > +/* Number of free lists per heap, grouped by size. */ > +#define RTE_HEAP_NUM_FREELISTS 5 > + > /** > * Structure to hold malloc heap > */ > struct malloc_heap { > rte_spinlock_t lock; > - struct malloc_elem * volatile free_head; > + LIST_HEAD(, malloc_elem) free_head[RTE_HEAP_NUM_FREELISTS]; > unsigned mz_count; > unsigned alloc_count; > size_t total_size; > diff --git a/lib/librte_malloc/malloc_elem.c b/lib/librte_malloc/malloc_e= lem.c > index f0da640..13cd5d3 100644 > --- a/lib/librte_malloc/malloc_elem.c > +++ b/lib/librte_malloc/malloc_elem.c > @@ -33,6 +33,7 @@ > #include > #include > #include > +#include > #include >=20 > #include > @@ -60,7 +61,8 @@ malloc_elem_init(struct malloc_elem *elem, > { > elem->heap =3D heap; > elem->mz =3D mz; > - elem->prev =3D elem->next_free =3D NULL; > + elem->prev =3D NULL; > + memset(&elem->free_list, 0, sizeof(elem->free_list)); > elem->state =3D ELEM_FREE; > elem->size =3D size; > elem->pad =3D 0; > @@ -125,14 +127,71 @@ split_elem(struct malloc_elem *elem, struct > malloc_elem *split_pt) > } >=20 > /* > + * Given an element size, compute its freelist index. > + * We free an element into the freelist containing similarly-sized eleme= nts. > + * We try to allocate elements starting with the freelist containing > + * similarly-sized elements, and if necessary, we search freelists > + * containing larger elements. > + * > + * Example element size ranges for a heap with five free lists: > + * heap->free_head[0] - (0 , 2^7] > + * heap->free_head[1] - (2^7 , 2^9] > + * heap->free_head[2] - (2^9 , 2^11] > + * heap->free_head[3] - (2^11, 2^13] > + * heap->free_head[4] - (2^13, MAX_SIZE] > + */ > +size_t > +malloc_elem_free_list_index(size_t size) > +{ > +#define MALLOC_MINSIZE_LOG2 7 > +#define MALLOC_LOG2_INCREMENT 2 > + > + size_t log2; > + size_t index; > + > + if (size <=3D (1UL << MALLOC_MINSIZE_LOG2)) > + return 0; > + > + /* Find next power of 2 >=3D size. */ > + log2 =3D sizeof(size) * 8 - __builtin_clzl(size-1); > + > + /* Compute freelist index, based on log2(size). */ > + index =3D (log2 - MALLOC_MINSIZE_LOG2 + > MALLOC_LOG2_INCREMENT - 1) / > + MALLOC_LOG2_INCREMENT; > + > + return (index <=3D RTE_HEAP_NUM_FREELISTS-1? > + index: RTE_HEAP_NUM_FREELISTS-1); > +} > + > +/* > + * Add the specified element to its heap's free list. > + */ > +void > +malloc_elem_free_list_insert(struct malloc_elem *elem) > +{ > + size_t idx =3D malloc_elem_free_list_index(elem->size - > MALLOC_ELEM_HEADER_LEN); > + > + elem->state =3D ELEM_FREE; > + LIST_INSERT_HEAD(&elem->heap->free_head[idx], elem, free_list); > +} > + > +/* > + * Remove the specified element from its heap's free list. > + */ > +static void > +elem_free_list_remove(struct malloc_elem *elem) > +{ > + LIST_REMOVE(elem, free_list); > +} > + > +/* > * reserve a block of data in an existing malloc_elem. If the malloc_ele= m > * is much larger than the data block requested, we split the element in= two. > * This function is only called from malloc_heap_alloc so parameter chec= king > * is not done here, as it's done there previously. > */ > struct malloc_elem * > -malloc_elem_alloc(struct malloc_elem *elem, size_t size, > - unsigned align, struct malloc_elem *prev_free) > +malloc_elem_alloc(struct malloc_elem *elem, size_t size, unsigned align) > { > struct malloc_elem *new_elem =3D elem_start_pt(elem, size, align); > const unsigned old_elem_size =3D (uintptr_t)new_elem - > (uintptr_t)elem; > @@ -151,20 +210,20 @@ malloc_elem_alloc(struct malloc_elem *elem, > size_t size, > set_header(new_elem); > } > /* remove element from free list */ > - if (prev_free =3D=3D NULL) > - elem->heap->free_head =3D elem->next_free; > - else > - prev_free->next_free =3D elem->next_free; > + elem_free_list_remove(elem); >=20 > return new_elem; > } >=20 > /* we are going to split the element in two. The original element > - * remains free, and the new element is the one allocated, so no free > list > - * changes need to be made. > + * remains free, and the new element is the one allocated. > + * Re-insert original element, in case its new size makes it > + * belong on a different list. > */ > + elem_free_list_remove(elem); > split_elem(elem, new_elem); > new_elem->state =3D ELEM_BUSY; > + malloc_elem_free_list_insert(elem); >=20 > return new_elem; > } > @@ -182,25 +241,6 @@ join_elem(struct malloc_elem *elem1, struct > malloc_elem *elem2) > } >=20 > /* > - * scan the free list, and remove the request element from that > - * free list. (Free list to scan is got from heap pointer in element) > - */ > -static inline void > -remove_from_free_list(struct malloc_elem *elem) > -{ > - if (elem =3D=3D elem->heap->free_head) > - elem->heap->free_head =3D elem->next_free; > - else{ > - struct malloc_elem *prev_free =3D elem->heap->free_head; > - while (prev_free && prev_free->next_free !=3D elem) > - prev_free =3D prev_free->next_free; > - if (!prev_free) > - rte_panic("Corrupted free list\n"); > - prev_free->next_free =3D elem->next_free; > - } > -} > - > -/* > * free a malloc_elem block by adding it to the free list. If the > * blocks either immediately before or immediately after newly freed blo= ck > * are also free, the blocks are merged together. > @@ -214,21 +254,22 @@ malloc_elem_free(struct malloc_elem *elem) > rte_spinlock_lock(&(elem->heap->lock)); > struct malloc_elem *next =3D RTE_PTR_ADD(elem, elem->size); > if (next->state =3D=3D ELEM_FREE){ > - /* join to this one, and remove from free list */ > + /* remove from free list, join to this one */ > + elem_free_list_remove(next); > join_elem(elem, next); > - remove_from_free_list(next); > } >=20 > /* check if previous element is free, if so join with it and return, > - * no need to update free list, as that element is already there > + * need to re-insert in free list, as that element's size is changing > */ > - if (elem->prev !=3D NULL && elem->prev->state =3D=3D ELEM_FREE) > + if (elem->prev !=3D NULL && elem->prev->state =3D=3D ELEM_FREE) { > + elem_free_list_remove(elem->prev); > join_elem(elem->prev, elem); > + malloc_elem_free_list_insert(elem->prev); > + } > /* otherwise add ourselves to the free list */ > else { > - elem->next_free =3D elem->heap->free_head; > - elem->heap->free_head =3D elem; > - elem->state =3D ELEM_FREE; > + malloc_elem_free_list_insert(elem); > elem->pad =3D 0; > } > /* decrease heap's count of allocated elements */ > @@ -258,20 +299,18 @@ malloc_elem_resize(struct malloc_elem *elem, > size_t size) > if (current_size + next->size < new_size) > goto err_return; >=20 > - /* we now know the element fits, so join the two, then remove from > free > - * list > + /* we now know the element fits, so remove from free list, > + * join the two > */ > + elem_free_list_remove(next); > join_elem(elem, next); > - remove_from_free_list(next); >=20 > if (elem->size - new_size > MIN_DATA_SIZE + > MALLOC_ELEM_OVERHEAD){ > /* now we have a big block together. Lets cut it down a bit, > by splitting */ > struct malloc_elem *split_pt =3D RTE_PTR_ADD(elem, > new_size); > split_pt =3D RTE_PTR_ALIGN_CEIL(split_pt, CACHE_LINE_SIZE); > split_elem(elem, split_pt); > - split_pt->state =3D ELEM_FREE; > - split_pt->next_free =3D elem->heap->free_head; > - elem->heap->free_head =3D split_pt; > + malloc_elem_free_list_insert(split_pt); > } > rte_spinlock_unlock(&elem->heap->lock); > return 0; > diff --git a/lib/librte_malloc/malloc_elem.h > b/lib/librte_malloc/malloc_elem.h > index eadecf9..63c69e1 100644 > --- a/lib/librte_malloc/malloc_elem.h > +++ b/lib/librte_malloc/malloc_elem.h > @@ -46,7 +46,7 @@ enum elem_state { > struct malloc_elem { > struct malloc_heap *heap; > struct malloc_elem *volatile prev; /* points to prev elem in > memzone */ > - struct malloc_elem *volatile next_free; /* to make list of free > elements */ > + LIST_ENTRY(malloc_elem) free_list; /* list of free elements in hea= p > */ > const struct rte_memzone *mz; > volatile enum elem_state state; > uint32_t pad; > @@ -156,8 +156,7 @@ malloc_elem_can_hold(struct malloc_elem *elem, > size_t size, unsigned align); > * is much larger than the data block requested, we split the element in= two. > */ > struct malloc_elem * > -malloc_elem_alloc(struct malloc_elem *elem, size_t size, > - unsigned align, struct malloc_elem *prev_free); > +malloc_elem_alloc(struct malloc_elem *elem, size_t size, unsigned align)= ; >=20 > /* > * free a malloc_elem block by adding it to the free list. If the > @@ -174,4 +173,16 @@ malloc_elem_free(struct malloc_elem *elem); > int > malloc_elem_resize(struct malloc_elem *elem, size_t size); >=20 > +/* > + * Given an element size, compute its freelist index. > + */ > +size_t > +malloc_elem_free_list_index(size_t size); > + > +/* > + * Add element to its heap's free list. > + */ > +void > +malloc_elem_free_list_insert(struct malloc_elem *elem); > + > #endif /* MALLOC_ELEM_H_ */ > diff --git a/lib/librte_malloc/malloc_heap.c b/lib/librte_malloc/malloc_h= eap.c > index 882749c..cfc02f1 100644 > --- a/lib/librte_malloc/malloc_heap.c > +++ b/lib/librte_malloc/malloc_heap.c > @@ -114,9 +114,8 @@ malloc_heap_add_memzone(struct malloc_heap > *heap, size_t size, unsigned align) > const unsigned elem_size =3D (uintptr_t)end_elem - > (uintptr_t)start_elem; > malloc_elem_init(start_elem, heap, mz, elem_size); > malloc_elem_mkend(end_elem, start_elem); > + malloc_elem_free_list_insert(start_elem); >=20 > - start_elem->next_free =3D heap->free_head; > - heap->free_head =3D start_elem; > /* increase heap total size by size of new memzone */ > heap->total_size+=3Dmz_size - MALLOC_ELEM_OVERHEAD; > return 0; > @@ -125,35 +124,25 @@ malloc_heap_add_memzone(struct malloc_heap > *heap, size_t size, unsigned align) > /* > * Iterates through the freelist for a heap to find a free element > * which can store data of the required size and with the requested > alignment. > - * Returns null on failure, or pointer to element on success, with the p= ointer > - * to the previous element in the list, if any, being returned in a para= meter > - * (to make removing the element from the free list faster). > + * Returns null on failure, or pointer to element on success. > */ > static struct malloc_elem * > -find_suitable_element(struct malloc_heap *heap, size_t size, > - unsigned align, struct malloc_elem **prev) > +find_suitable_element(struct malloc_heap *heap, size_t size, unsigned > align) > { > - struct malloc_elem *elem, *min_elem, *min_prev; > - size_t min_sz; > - > - elem =3D heap->free_head; > - min_elem =3D NULL; > - min_prev =3D NULL; > - min_sz =3D (size_t) SIZE_MAX; > - *prev =3D NULL; > - > - while(elem){ > - if (malloc_elem_can_hold(elem, size, align)) { > - if (min_sz > elem->size) { > - min_elem =3D elem; > - *prev =3D min_prev; > - min_sz =3D elem->size; > - } > + size_t idx; > + struct malloc_elem *elem; > + > + for (idx =3D malloc_elem_free_list_index(size); > + idx < RTE_HEAP_NUM_FREELISTS; idx++) > + { > + for (elem =3D LIST_FIRST(&heap->free_head[idx]); > + !!elem; elem =3D LIST_NEXT(elem, free_list)) > + { > + if (malloc_elem_can_hold(elem, size, align)) > + return elem; > } > - min_prev =3D elem; > - elem =3D elem->next_free; > } > - return (min_elem); > + return NULL; > } >=20 > /* > @@ -169,15 +158,14 @@ malloc_heap_alloc(struct malloc_heap *heap, > size =3D CACHE_LINE_ROUNDUP(size); > align =3D CACHE_LINE_ROUNDUP(align); > rte_spinlock_lock(&heap->lock); > - struct malloc_elem *prev, *elem =3D find_suitable_element(heap, > - size, align, &prev); > + struct malloc_elem *elem =3D find_suitable_element(heap, size, align); > if (elem =3D=3D NULL){ > if ((malloc_heap_add_memzone(heap, size, align)) =3D=3D 0) > - elem =3D find_suitable_element(heap, size, align, > &prev); > + elem =3D find_suitable_element(heap, size, align); > } >=20 > if (elem !=3D NULL){ > - elem =3D malloc_elem_alloc(elem, size, align, prev); > + elem =3D malloc_elem_alloc(elem, size, align); > /* increase heap's count of allocated elements */ > heap->alloc_count++; > } > @@ -193,7 +181,8 @@ int > malloc_heap_get_stats(const struct malloc_heap *heap, > struct rte_malloc_socket_stats *socket_stats) > { > - struct malloc_elem *elem =3D heap->free_head; > + size_t idx; > + struct malloc_elem *elem; >=20 > /* Initialise variables for heap */ > socket_stats->free_count =3D 0; > @@ -201,13 +190,15 @@ malloc_heap_get_stats(const struct malloc_heap > *heap, > socket_stats->greatest_free_size =3D 0; >=20 > /* Iterate through free list */ > - while(elem) { > - socket_stats->free_count++; > - socket_stats->heap_freesz_bytes +=3D elem->size; > - if (elem->size > socket_stats->greatest_free_size) > - socket_stats->greatest_free_size =3D elem->size; > - > - elem =3D elem->next_free; > + for (idx =3D 0; idx < RTE_HEAP_NUM_FREELISTS; idx++) { > + for (elem =3D LIST_FIRST(&heap->free_head[idx]); > + !!elem; elem =3D LIST_NEXT(elem, free_list)) > + { > + socket_stats->free_count++; > + socket_stats->heap_freesz_bytes +=3D elem->size; > + if (elem->size > socket_stats->greatest_free_size) > + socket_stats->greatest_free_size =3D elem- > >size; > + } > } > /* Get stats on overall heap and allocated memory on this heap */ > socket_stats->heap_totalsz_bytes =3D heap->total_size; > -- > 1.7.1 Hi Robert, Overall patch looks OK, but malloc unit tests fail on the last test (test_m= ulti_alloc_statistics). Apparently, the biggest free chunk size changes as = it allocates some memory, whereas in the previous implementation, this size= did not change. I wonder if unit test is wrong or if there is actually an = issue here. Could you look at this as well? Thanks, Pablo