[dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[Sanford, Robert]

Here is our proposed patch:

Lib rte_malloc stores free blocks in singly-linked lists.
This results in O(n), i.e., poor performance when freeing memory
to a heap that contains thousands of free blocks.

A simple solution is to store free blocks on doubly-linked lists.
- Space-wise, we add one new pointer to struct malloc_elem.
 This does not affect its size, since it is cache-aligned and
 currently has room for another pointer.
- We perform all free list adds and deletes in functions
 malloc_elem_add_to_free_list and remove_from_free_list.
- We clean up internal malloc functions that push or
 return pointers to previous blocks in the free list.


---
 lib/librte_malloc/malloc_elem.c |   82
+++++++++++++++++++++++---------------
 lib/librte_malloc/malloc_elem.h |    6 ++-
 lib/librte_malloc/malloc_heap.c |   19 +++------
 3 files changed, 60 insertions(+), 47 deletions(-)

diff --git a/lib/librte_malloc/malloc_elem.c
b/lib/librte_malloc/malloc_elem.c
index f0da640..9a14e23 100644
--- a/lib/librte_malloc/malloc_elem.c
+++ b/lib/librte_malloc/malloc_elem.c
@@ -60,7 +60,7 @@ malloc_elem_init(struct malloc_elem *elem,
 {
 	elem->heap = heap;
 	elem->mz = mz;
-	elem->prev = elem->next_free = NULL;
+	elem->prev = elem->next_free = elem->prev_free = NULL;
 	elem->state = ELEM_FREE;
 	elem->size = size;
 	elem->pad = 0;
@@ -125,14 +125,58 @@ split_elem(struct malloc_elem *elem, struct
malloc_elem *split_pt)
 }
 
 /*
+ * Add the specified element to its heap's free list.
+ */
+void
+malloc_elem_add_to_free_list(struct malloc_elem *elem)
+{
+	elem->state = ELEM_FREE;
+	elem->prev_free = NULL;
+	if (!!(elem->next_free = elem->heap->free_head))
+		elem->next_free->prev_free = elem;
+	elem->heap->free_head = elem;
+}
+
+/*
+ * Remove the specified element from its heap's free list.
+ */
+static inline void
+remove_from_free_list(struct malloc_elem *elem)
+{
+	struct malloc_elem *next_free_elem = elem->next_free;
+	struct malloc_elem *prev_free_elem = elem->prev_free;
+
+	if (!!next_free_elem) {
+#ifdef RTE_LIBRTE_MALLOC_DEBUG
+		RTE_VERIFY(next_free_elem->prev_free == elem);
+#endif
+		next_free_elem->prev_free = prev_free_elem;
+	}
+
+	if (!!prev_free_elem) {
+#ifdef RTE_LIBRTE_MALLOC_DEBUG
+		RTE_VERIFY(prev_free_elem->next_free == elem);
+#endif
+		prev_free_elem->next_free = next_free_elem;
+	}
+	else {
+		struct malloc_heap *heap = elem->heap;
+
+#ifdef RTE_LIBRTE_MALLOC_DEBUG
+		RTE_VERIFY(heap->free_head == elem);
+#endif
+		heap->free_head = next_free_elem;
+	}
+}
+
+/*
  * reserve a block of data in an existing malloc_elem. If the malloc_elem
  * 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
checking
  * 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 = elem_start_pt(elem, size, align);
 	const unsigned old_elem_size = (uintptr_t)new_elem - (uintptr_t)elem;
@@ -151,10 +195,7 @@ malloc_elem_alloc(struct malloc_elem *elem, size_t
size,
 			set_header(new_elem);
 		}
 		/* remove element from free list */
-		if (prev_free == NULL)
-			elem->heap->free_head = elem->next_free;
-		else
-			prev_free->next_free = elem->next_free;
+		remove_from_free_list(elem);
 
 		return new_elem;
 	}
@@ -182,25 +223,6 @@ join_elem(struct malloc_elem *elem1, struct
malloc_elem *elem2)
 }
 
 /*
- * 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 == elem->heap->free_head)
-		elem->heap->free_head = elem->next_free;
-	else{
-		struct malloc_elem *prev_free = elem->heap->free_head;
-		while (prev_free && prev_free->next_free != elem)
-			prev_free = prev_free->next_free;
-		if (!prev_free)
-			rte_panic("Corrupted free list\n");
-		prev_free->next_free = 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 block
  * are also free, the blocks are merged together.
@@ -226,9 +248,7 @@ malloc_elem_free(struct malloc_elem *elem)
 		join_elem(elem->prev, elem);
 	/* otherwise add ourselves to the free list */
 	else {
-		elem->next_free = elem->heap->free_head;
-		elem->heap->free_head = elem;
-		elem->state = ELEM_FREE;
+		malloc_elem_add_to_free_list(elem);
 		elem->pad = 0;
 	}
 	/* decrease heap's count of allocated elements */
@@ -269,9 +289,7 @@ malloc_elem_resize(struct malloc_elem *elem, size_t
size)
 		struct malloc_elem *split_pt = RTE_PTR_ADD(elem, new_size);
 		split_pt = RTE_PTR_ALIGN_CEIL(split_pt, CACHE_LINE_SIZE);
 		split_elem(elem, split_pt);
-		split_pt->state = ELEM_FREE;
-		split_pt->next_free = elem->heap->free_head;
-		elem->heap->free_head = split_pt;
+		malloc_elem_add_to_free_list(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..6d2d7db 100644
--- a/lib/librte_malloc/malloc_elem.h
+++ b/lib/librte_malloc/malloc_elem.h
@@ -47,6 +47,7 @@ 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
*/
+	struct malloc_elem *volatile prev_free; /* make free list doubly-linked
*/
 	const struct rte_memzone *mz;
 	volatile enum elem_state state;
 	uint32_t pad;
@@ -156,8 +157,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);
 
 /*
  * free a malloc_elem block by adding it to the free list. If the
@@ -174,4 +174,6 @@ malloc_elem_free(struct malloc_elem *elem);
 int
 malloc_elem_resize(struct malloc_elem *elem, size_t size);
 
+void malloc_elem_add_to_free_list(struct malloc_elem *elem);
+
 #endif /* MALLOC_ELEM_H_ */
diff --git a/lib/librte_malloc/malloc_heap.c
b/lib/librte_malloc/malloc_heap.c
index f4a0294..bc146e1 100644
--- a/lib/librte_malloc/malloc_heap.c
+++ b/lib/librte_malloc/malloc_heap.c
@@ -112,9 +112,8 @@ malloc_heap_add_memzone(struct malloc_heap *heap,
size_t size, unsigned align)
 	const unsigned elem_size = (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_add_to_free_list(start_elem);
 
-	start_elem->next_free = heap->free_head;
-	heap->free_head = start_elem;
 	/* increase heap total size by size of new memzone */
 	heap->total_size+=mz_size - MALLOC_ELEM_OVERHEAD;
 	return 0;
@@ -160,27 +159,22 @@ malloc_heap_init(struct malloc_heap *heap)
  * (to make removing the element from the free list faster).
  */
 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;
+	struct malloc_elem *elem, *min_elem;
 	size_t min_sz;
 
 	elem = heap->free_head;
 	min_elem = NULL;
-	min_prev = NULL;
 	min_sz = (size_t) SIZE_MAX;
-	*prev = NULL;
 
 	while(elem){
 		if (malloc_elem_can_hold(elem, size, align)) {
 			if (min_sz > elem->size) {
 				min_elem = elem;
-				*prev = min_prev;
 				min_sz = elem->size;
 			}
 		}
-		min_prev = elem;
 		elem = elem->next_free;
 	}
 	return (min_elem);
@@ -202,15 +196,14 @@ malloc_heap_alloc(struct malloc_heap *heap,
 	size = CACHE_LINE_ROUNDUP(size);
 	align = CACHE_LINE_ROUNDUP(align);
 	rte_spinlock_lock(&heap->lock);
-	struct malloc_elem *prev, *elem = find_suitable_element(heap,
-			size, align, &prev);
+	struct malloc_elem *elem = find_suitable_element(heap, size, align);
 	if (elem == NULL){
 		if ((malloc_heap_add_memzone(heap, size, align)) == 0)
-			elem = find_suitable_element(heap, size, align, &prev);
+			elem = find_suitable_element(heap, size, align);
 	}
 
 	if (elem != NULL){
-		elem = malloc_elem_alloc(elem, size, align, prev);
+		elem = malloc_elem_alloc(elem, size, align);
 		/* increase heap's count of allocated elements */
 		heap->alloc_count++;
 	}
-- 
1.7.1

Signed-off-by: Robert Sanford <rsanford@akamai.com>

Re: [dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[Sanford, Robert]

I haven't heard anything regarding this patch.
In general, how does your team keep track of outstanding patch requests or
RFCs?

Thanks,
Robert


>Here is our proposed patch:
>
>Lib rte_malloc stores free blocks in singly-linked lists.
>This results in O(n), i.e., poor performance when freeing memory
>to a heap that contains thousands of free blocks.
>
>A simple solution is to store free blocks on doubly-linked lists.
>- Space-wise, we add one new pointer to struct malloc_elem.
> This does not affect its size, since it is cache-aligned and
> currently has room for another pointer.
>- We perform all free list adds and deletes in functions
> malloc_elem_add_to_free_list and remove_from_free_list.
>- We clean up internal malloc functions that push or
> return pointers to previous blocks in the free list.
>
>
>---
> lib/librte_malloc/malloc_elem.c |   82
>+++++++++++++++++++++++---------------
> lib/librte_malloc/malloc_elem.h |    6 ++-
> lib/librte_malloc/malloc_heap.c |   19 +++------
> 3 files changed, 60 insertions(+), 47 deletions(-)
>
>diff --git a/lib/librte_malloc/malloc_elem.c
>b/lib/librte_malloc/malloc_elem.c
>index f0da640..9a14e23 100644
>--- a/lib/librte_malloc/malloc_elem.c
>+++ b/lib/librte_malloc/malloc_elem.c
>@@ -60,7 +60,7 @@ malloc_elem_init(struct malloc_elem *elem,
> {
> 	elem->heap = heap;
> 	elem->mz = mz;
>-	elem->prev = elem->next_free = NULL;
>+	elem->prev = elem->next_free = elem->prev_free = NULL;
> 	elem->state = ELEM_FREE;
> 	elem->size = size;
> 	elem->pad = 0;
>@@ -125,14 +125,58 @@ split_elem(struct malloc_elem *elem, struct
>malloc_elem *split_pt)
> }
> 
> /*
>+ * Add the specified element to its heap's free list.
>+ */
>+void
>+malloc_elem_add_to_free_list(struct malloc_elem *elem)
>+{
>+	elem->state = ELEM_FREE;
>+	elem->prev_free = NULL;
>+	if (!!(elem->next_free = elem->heap->free_head))
>+		elem->next_free->prev_free = elem;
>+	elem->heap->free_head = elem;
>+}
>+
>+/*
>+ * Remove the specified element from its heap's free list.
>+ */
>+static inline void
>+remove_from_free_list(struct malloc_elem *elem)
>+{
>+	struct malloc_elem *next_free_elem = elem->next_free;
>+	struct malloc_elem *prev_free_elem = elem->prev_free;
>+
>+	if (!!next_free_elem) {
>+#ifdef RTE_LIBRTE_MALLOC_DEBUG
>+		RTE_VERIFY(next_free_elem->prev_free == elem);
>+#endif
>+		next_free_elem->prev_free = prev_free_elem;
>+	}
>+
>+	if (!!prev_free_elem) {
>+#ifdef RTE_LIBRTE_MALLOC_DEBUG
>+		RTE_VERIFY(prev_free_elem->next_free == elem);
>+#endif
>+		prev_free_elem->next_free = next_free_elem;
>+	}
>+	else {
>+		struct malloc_heap *heap = elem->heap;
>+
>+#ifdef RTE_LIBRTE_MALLOC_DEBUG
>+		RTE_VERIFY(heap->free_head == elem);
>+#endif
>+		heap->free_head = next_free_elem;
>+	}
>+}
>+
>+/*
>  * reserve a block of data in an existing malloc_elem. If the malloc_elem
>  * 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
>checking
>  * 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 = elem_start_pt(elem, size, align);
> 	const unsigned old_elem_size = (uintptr_t)new_elem - (uintptr_t)elem;
>@@ -151,10 +195,7 @@ malloc_elem_alloc(struct malloc_elem *elem, size_t
>size,
> 			set_header(new_elem);
> 		}
> 		/* remove element from free list */
>-		if (prev_free == NULL)
>-			elem->heap->free_head = elem->next_free;
>-		else
>-			prev_free->next_free = elem->next_free;
>+		remove_from_free_list(elem);
> 
> 		return new_elem;
> 	}
>@@ -182,25 +223,6 @@ join_elem(struct malloc_elem *elem1, struct
>malloc_elem *elem2)
> }
> 
> /*
>- * 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 == elem->heap->free_head)
>-		elem->heap->free_head = elem->next_free;
>-	else{
>-		struct malloc_elem *prev_free = elem->heap->free_head;
>-		while (prev_free && prev_free->next_free != elem)
>-			prev_free = prev_free->next_free;
>-		if (!prev_free)
>-			rte_panic("Corrupted free list\n");
>-		prev_free->next_free = 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
>block
>  * are also free, the blocks are merged together.
>@@ -226,9 +248,7 @@ malloc_elem_free(struct malloc_elem *elem)
> 		join_elem(elem->prev, elem);
> 	/* otherwise add ourselves to the free list */
> 	else {
>-		elem->next_free = elem->heap->free_head;
>-		elem->heap->free_head = elem;
>-		elem->state = ELEM_FREE;
>+		malloc_elem_add_to_free_list(elem);
> 		elem->pad = 0;
> 	}
> 	/* decrease heap's count of allocated elements */
>@@ -269,9 +289,7 @@ malloc_elem_resize(struct malloc_elem *elem, size_t
>size)
> 		struct malloc_elem *split_pt = RTE_PTR_ADD(elem, new_size);
> 		split_pt = RTE_PTR_ALIGN_CEIL(split_pt, CACHE_LINE_SIZE);
> 		split_elem(elem, split_pt);
>-		split_pt->state = ELEM_FREE;
>-		split_pt->next_free = elem->heap->free_head;
>-		elem->heap->free_head = split_pt;
>+		malloc_elem_add_to_free_list(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..6d2d7db 100644
>--- a/lib/librte_malloc/malloc_elem.h
>+++ b/lib/librte_malloc/malloc_elem.h
>@@ -47,6 +47,7 @@ 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
>*/
>+	struct malloc_elem *volatile prev_free; /* make free list doubly-linked
>*/
> 	const struct rte_memzone *mz;
> 	volatile enum elem_state state;
> 	uint32_t pad;
>@@ -156,8 +157,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);
> 
> /*
>  * free a malloc_elem block by adding it to the free list. If the
>@@ -174,4 +174,6 @@ malloc_elem_free(struct malloc_elem *elem);
> int
> malloc_elem_resize(struct malloc_elem *elem, size_t size);
> 
>+void malloc_elem_add_to_free_list(struct malloc_elem *elem);
>+
> #endif /* MALLOC_ELEM_H_ */
>diff --git a/lib/librte_malloc/malloc_heap.c
>b/lib/librte_malloc/malloc_heap.c
>index f4a0294..bc146e1 100644
>--- a/lib/librte_malloc/malloc_heap.c
>+++ b/lib/librte_malloc/malloc_heap.c
>@@ -112,9 +112,8 @@ malloc_heap_add_memzone(struct malloc_heap *heap,
>size_t size, unsigned align)
> 	const unsigned elem_size = (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_add_to_free_list(start_elem);
> 
>-	start_elem->next_free = heap->free_head;
>-	heap->free_head = start_elem;
> 	/* increase heap total size by size of new memzone */
> 	heap->total_size+=mz_size - MALLOC_ELEM_OVERHEAD;
> 	return 0;
>@@ -160,27 +159,22 @@ malloc_heap_init(struct malloc_heap *heap)
>  * (to make removing the element from the free list faster).
>  */
> 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;
>+	struct malloc_elem *elem, *min_elem;
> 	size_t min_sz;
> 
> 	elem = heap->free_head;
> 	min_elem = NULL;
>-	min_prev = NULL;
> 	min_sz = (size_t) SIZE_MAX;
>-	*prev = NULL;
> 
> 	while(elem){
> 		if (malloc_elem_can_hold(elem, size, align)) {
> 			if (min_sz > elem->size) {
> 				min_elem = elem;
>-				*prev = min_prev;
> 				min_sz = elem->size;
> 			}
> 		}
>-		min_prev = elem;
> 		elem = elem->next_free;
> 	}
> 	return (min_elem);
>@@ -202,15 +196,14 @@ malloc_heap_alloc(struct malloc_heap *heap,
> 	size = CACHE_LINE_ROUNDUP(size);
> 	align = CACHE_LINE_ROUNDUP(align);
> 	rte_spinlock_lock(&heap->lock);
>-	struct malloc_elem *prev, *elem = find_suitable_element(heap,
>-			size, align, &prev);
>+	struct malloc_elem *elem = find_suitable_element(heap, size, align);
> 	if (elem == NULL){
> 		if ((malloc_heap_add_memzone(heap, size, align)) == 0)
>-			elem = find_suitable_element(heap, size, align, &prev);
>+			elem = find_suitable_element(heap, size, align);
> 	}
> 
> 	if (elem != NULL){
>-		elem = malloc_elem_alloc(elem, size, align, prev);
>+		elem = malloc_elem_alloc(elem, size, align);
> 		/* increase heap's count of allocated elements */
> 		heap->alloc_count++;
> 	}
>-- 
>1.7.1
>
>Signed-off-by: Robert Sanford <rsanford@akamai.com>
>

Re: [dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[Thomas Monjalon]

Hi Robert,

2014-05-08 16:17, Sanford, Robert:
> I haven't heard anything regarding this patch.
> In general, how does your team keep track of outstanding patch requests or
> RFCs?

If nobody complains, it means that everybody agree on the idea.
So it should be accepted after review.
Some patches like this one are not yet reviewed because efforts were focused 
on release 1.6.0r2. This enhancement must be integrated in 1.7.0.
I know that patchwork service is desired and I hope it will be available soon.

By the way, looking at librte_malloc, it seems implementation of lists could 
be simpler. Don't you think we could improve (in another patch) this whole 
code by using BSD macros for lists?

Thanks
-- 
Thomas

Re: [dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[Sanford, Robert]

Hi Thomas,

>Some patches like this one are not yet reviewed because efforts were
>focused 
>on release 1.6.0r2. This enhancement must be integrated in 1.7.0.
>I know that patchwork service is desired and I hope it will be available
>soon.

I realized that you guys had been very busy with 1.6.0r2. I just wanted to
make
sure that lower-priority patches didn't fall through the cracks.

>By the way, looking at librte_malloc, it seems implementation of lists
>could
>be simpler. Don't you think we could improve (in another patch) this
>whole 
>code by using BSD macros for lists?

Yes, I was surprised to find the malloc code not using any kind of list
functions/macros. I am willing to rework the patch. By BSD list macros, I
believe you are referring to QUEUE(3) and sys/queue.h. It that right?

Thanks,
Robert

Re: [dpdk-dev] [PATCH] malloc: fix rte_free run time in O(n) free blocks

[Thomas Monjalon]

2014-05-09 09:24, Sanford, Robert:
> Hi Thomas,
> 
> >Some patches like this one are not yet reviewed because efforts were
> >focused
> >on release 1.6.0r2. This enhancement must be integrated in 1.7.0.
> >I know that patchwork service is desired and I hope it will be available
> >soon.
> 
> I realized that you guys had been very busy with 1.6.0r2. I just wanted to
> make
> sure that lower-priority patches didn't fall through the cracks.
> 
> >By the way, looking at librte_malloc, it seems implementation of lists
> >could
> >be simpler. Don't you think we could improve (in another patch) this
> >whole
> >code by using BSD macros for lists?
> 
> Yes, I was surprised to find the malloc code not using any kind of list
> functions/macros. I am willing to rework the patch. By BSD list macros, I
> believe you are referring to QUEUE(3) and sys/queue.h. It that right?

Yes I'm referring to QUEUE(3).
So I wait for your rework.

Thanks
-- 
Thomas