[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 at akamai.com>