From mboxrd@z Thu Jan  1 00:00:00 1970
From: Robert Sanford <rsanford2-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
Subject: [PATCH v3 0/2] malloc: fix malloc and free linear
	complexity
Date: Mon, 23 Jun 2014 17:17:08 -0400
Message-ID: <1403558230-40042-1-git-send-email-rsanford2@gmail.com>
References: <1400245141-10938-1-git-send-email-rsanford2@gmail.com>
To: dev-VfR2kkLFssw@public.gmane.org
Return-path: <dev-bounces-VfR2kkLFssw@public.gmane.org>
In-Reply-To: <1400245141-10938-1-git-send-email-rsanford2-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
List-Id: patches and discussions about DPDK <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
 <mailto:dev-request-VfR2kkLFssw@public.gmane.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev-VfR2kkLFssw@public.gmane.org>
List-Help: <mailto:dev-request-VfR2kkLFssw@public.gmane.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request-VfR2kkLFssw@public.gmane.org?subject=subscribe>
Errors-To: dev-bounces-VfR2kkLFssw@public.gmane.org
Sender: "dev" <dev-bounces-VfR2kkLFssw@public.gmane.org>

Comments on previous versions of this patch:
http://dpdk.org/ml/archives/dev/2014-May/002297.html
http://dpdk.org/ml/archives/dev/2014-June/003518.html

Additional changes from original to v3:
* Reduce the minimum-sized block that we put on a free list when
  splitting a larger block, from 192 to 64. Although memory is
  plentiful, why waste 64 and 128-byte (plus overhead) blocks?

-#define MIN_DATA_SIZE (CACHE_LINE_SIZE * 2)
+#define MIN_DATA_SIZE (CACHE_LINE_SIZE)

-       if (old_elem_size <= MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE){
+       if (old_elem_size < MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE){

-       if (elem->size - new_size > MIN_DATA_SIZE + MALLOC_ELEM_OVERHEAD){
+       if (elem->size - new_size >= MIN_DATA_SIZE + MALLOC_ELEM_OVERHEAD){

Changes from v2 to v3:
* Change the size ranges of the five free lists per heap. The first
  list will effectively contain blocks of size [64,256].

-  *   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]
+  *   heap->free_head[0] - (0   , 2^8]
+  *   heap->free_head[1] - (2^8 , 2^10]
+  *   heap->free_head[2] - (2^10 ,2^12]
+  *   heap->free_head[3] - (2^12, 2^14]
+  *   heap->free_head[4] - (2^14, MAX_SIZE]

- #define MALLOC_MINSIZE_LOG2   7
+ #define MALLOC_MINSIZE_LOG2   8

* Fix typos and false assumptions in malloc unit tests. Even without
  linked-list enhancements to lib rte_malloc, malloc autotest fails
  every second (2nd) run.