X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_malloc%2Fmalloc_elem.c;h=fd0532e539d6a645a1d02fd2075d737d6bbe9747;hb=66e1591687ac;hp=0d2fdb6beae84e2dd986d54c0b6039aa07cfa947;hpb=70dce764786add35b88ca2ca0fc16a13a1223ca8;p=dpdk.git diff --git a/lib/librte_malloc/malloc_elem.c b/lib/librte_malloc/malloc_elem.c index 0d2fdb6bea..fd0532e539 100644 --- a/lib/librte_malloc/malloc_elem.c +++ b/lib/librte_malloc/malloc_elem.c @@ -1,44 +1,43 @@ /*- * BSD LICENSE - * - * Copyright(c) 2010-2012 Intel Corporation. All rights reserved. + * + * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions * are met: - * - * * Redistributions of source code must retain the above copyright + * + * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the * distribution. - * * Neither the name of Intel Corporation nor the names of its - * contributors may be used to endorse or promote products derived + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * */ #include #include #include +#include #include #include #include -#include #include #include #include @@ -50,17 +49,19 @@ #include "malloc_elem.h" #include "malloc_heap.h" -#define MIN_DATA_SIZE (CACHE_LINE_SIZE * 2) +#define MIN_DATA_SIZE (RTE_CACHE_LINE_SIZE) /* * initialise a general malloc_elem header structure */ void malloc_elem_init(struct malloc_elem *elem, - struct malloc_heap *heap, size_t size) + struct malloc_heap *heap, const struct rte_memzone *mz, size_t size) { elem->heap = heap; - elem->prev = elem->next_free = NULL; + elem->mz = mz; + elem->prev = NULL; + memset(&elem->free_list, 0, sizeof(elem->free_list)); elem->state = ELEM_FREE; elem->size = size; elem->pad = 0; @@ -74,7 +75,7 @@ malloc_elem_init(struct malloc_elem *elem, void malloc_elem_mkend(struct malloc_elem *elem, struct malloc_elem *prev) { - malloc_elem_init(elem, prev->heap, 0); + malloc_elem_init(elem, prev->heap, prev->mz, 0); elem->prev = prev; elem->state = ELEM_BUSY; /* mark busy so its never merged */ } @@ -117,13 +118,71 @@ split_elem(struct malloc_elem *elem, struct malloc_elem *split_pt) const unsigned old_elem_size = (uintptr_t)split_pt - (uintptr_t)elem; const unsigned new_elem_size = elem->size - old_elem_size; - malloc_elem_init(split_pt, elem->heap, new_elem_size); + malloc_elem_init(split_pt, elem->heap, elem->mz, new_elem_size); split_pt->prev = elem; next_elem->prev = split_pt; elem->size = old_elem_size; set_trailer(elem); } +/* + * Given an element size, compute its freelist index. + * We free an element into the freelist containing similarly-sized elements. + * 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^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] + */ +size_t +malloc_elem_free_list_index(size_t size) +{ +#define MALLOC_MINSIZE_LOG2 8 +#define MALLOC_LOG2_INCREMENT 2 + + size_t log2; + size_t index; + + if (size <= (1UL << MALLOC_MINSIZE_LOG2)) + return 0; + + /* Find next power of 2 >= size. */ + log2 = sizeof(size) * 8 - __builtin_clzl(size-1); + + /* Compute freelist index, based on log2(size). */ + index = (log2 - MALLOC_MINSIZE_LOG2 + MALLOC_LOG2_INCREMENT - 1) / + MALLOC_LOG2_INCREMENT; + + return (index <= 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 = malloc_elem_free_list_index(elem->size - MALLOC_ELEM_HEADER_LEN); + + elem->state = 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_elem * is much larger than the data block requested, we split the element in two. @@ -131,13 +190,12 @@ split_elem(struct malloc_elem *elem, struct malloc_elem *split_pt) * 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; - if (old_elem_size <= MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE){ + if (old_elem_size < MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE){ /* don't split it, pad the element instead */ elem->state = ELEM_BUSY; elem->pad = old_elem_size; @@ -151,20 +209,20 @@ 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; + elem_free_list_remove(elem); return new_elem; } /* 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 = ELEM_BUSY; + malloc_elem_free_list_insert(elem); return new_elem; } @@ -181,25 +239,6 @@ join_elem(struct malloc_elem *elem1, struct malloc_elem *elem2) next->prev = elem1; } -/* - * 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 @@ -214,24 +253,28 @@ malloc_elem_free(struct malloc_elem *elem) rte_spinlock_lock(&(elem->heap->lock)); struct malloc_elem *next = RTE_PTR_ADD(elem, elem->size); if (next->state == 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); } /* 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 != NULL && elem->prev->state == ELEM_FREE) + if (elem->prev != NULL && elem->prev->state == 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 = elem->heap->free_head; - elem->heap->free_head = elem; - elem->state = ELEM_FREE; + malloc_elem_free_list_insert(elem); elem->pad = 0; } + /* decrease heap's count of allocated elements */ + elem->heap->alloc_count--; rte_spinlock_unlock(&(elem->heap->lock)); + return 0; } @@ -255,20 +298,18 @@ malloc_elem_resize(struct malloc_elem *elem, size_t size) if (current_size + next->size < new_size) goto err_return; - /* 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); - if (elem->size - new_size > MIN_DATA_SIZE + MALLOC_ELEM_OVERHEAD){ + 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 = RTE_PTR_ADD(elem, new_size); - split_pt = RTE_PTR_ALIGN_CEIL(split_pt, CACHE_LINE_SIZE); + split_pt = RTE_PTR_ALIGN_CEIL(split_pt, RTE_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_free_list_insert(split_pt); } rte_spinlock_unlock(&elem->heap->lock); return 0;