From 473c84604708aff44b883892bac84f33d9d5b3bc Mon Sep 17 00:00:00 2001 From: Florin Coras Date: Mon, 16 Nov 2020 18:11:51 -0800 Subject: [PATCH] svm: fifo segment cleanup - consolidate chunk freelist functions - remove redundant functions Type: improvement Signed-off-by: Florin Coras Change-Id: Idd7e6700e2cc98a0fb9cfe20a2b739218fd48043 --- src/svm/fifo_segment.c | 546 +++++++++++++++++++------------------------------ 1 file changed, 205 insertions(+), 341 deletions(-) diff --git a/src/svm/fifo_segment.c b/src/svm/fifo_segment.c index a5ffd4af2ed..473cdf31b64 100644 --- a/src/svm/fifo_segment.c +++ b/src/svm/fifo_segment.c @@ -133,6 +133,70 @@ fsh_check_mem (fifo_segment_header_t * fsh) fsh_update_free_bytes (fsh); } +static inline int +fss_chunk_fl_index_is_valid (fifo_segment_slice_t * fss, u32 fl_index) +{ + return (fl_index < vec_len (fss->free_chunks)); +} + +static void +fss_chunk_free_list_push (fifo_segment_slice_t * fss, u32 fl_index, + svm_fifo_chunk_t * c) +{ + c->next = fss->free_chunks[fl_index]; + fss->free_chunks[fl_index] = c; +} + +static void +fss_chunk_free_list_push_list (fifo_segment_slice_t * fss, u32 fl_index, + svm_fifo_chunk_t * head, + svm_fifo_chunk_t * tail) +{ + tail->next = fss->free_chunks[fl_index]; + fss->free_chunks[fl_index] = head; +} + +static svm_fifo_chunk_t * +fss_chunk_free_list_pop (fifo_segment_slice_t * fss, u32 fl_index) +{ + svm_fifo_chunk_t *c; + + ASSERT (fss_chunk_fl_index_is_valid (fss, fl_index)); + + if (!fss->free_chunks[fl_index]) + return 0; + + c = fss->free_chunks[fl_index]; + fss->free_chunks[fl_index] = c->next; + + return c; +} + +static inline void +fss_fifo_add_active_list (fifo_segment_slice_t * fss, svm_fifo_t * f) +{ + if (fss->fifos) + { + fss->fifos->prev = f; + f->next = fss->fifos; + } + fss->fifos = f; +} + +static inline void +fss_fifo_del_active_list (fifo_segment_slice_t * fss, svm_fifo_t * f) +{ + if (f->flags & SVM_FIFO_F_LL_TRACKED) + { + if (f->prev) + f->prev->next = f->next; + else + fss->fifos = f->next; + if (f->next) + f->next->prev = f->prev; + } +} + /** * Initialize fifo segment shared header */ @@ -318,30 +382,6 @@ fs_chunk_size_is_valid (fifo_segment_header_t * fsh, u32 size) && size <= (1ULL << fsh->max_log2_chunk_size); } -static svm_fifo_t * -fs_try_alloc_fifo_freelist (fifo_segment_slice_t * fss, u32 fl_index) -{ - svm_fifo_chunk_t *c; - svm_fifo_t *f; - - f = fss->free_fifos; - c = fss->free_chunks[fl_index]; - - if (!f || !c) - return 0; - - fss->free_fifos = f->next; - fss->free_chunks[fl_index] = c->next; - c->next = 0; - c->start_byte = 0; - memset (f, 0, sizeof (*f)); - f->start_chunk = c; - f->end_chunk = c; - - fss->n_fl_chunk_bytes -= fs_freelist_index_to_size (fl_index); - return f; -} - svm_fifo_chunk_t * fs_try_alloc_multi_chunk (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss, u32 data_bytes) @@ -357,10 +397,9 @@ fs_try_alloc_multi_chunk (fifo_segment_header_t * fsh, while (req_bytes) { - c = fss->free_chunks[fl_index]; + c = fss_chunk_free_list_pop (fss, fl_index); if (c) { - fss->free_chunks[fl_index] = c->next; c->next = first; first = c; n_alloc += fl_size; @@ -371,28 +410,29 @@ fs_try_alloc_multi_chunk (fifo_segment_header_t * fsh, /* Failed to allocate with smaller chunks */ if (fl_index == 0) { - /* free all chunks if any allocated */ + /* Free all chunks if any allocated */ c = first; while (c) { fl_index = fs_freelist_for_size (c->length); - fl_size = fs_freelist_index_to_size (fl_index); next = c->next; - c->next = fss->free_chunks[fl_index]; - fss->free_chunks[fl_index] = c; - fss->n_fl_chunk_bytes += fl_size; + fss_chunk_free_list_push (fss, fl_index, c); c = next; } n_alloc = 0; first = 0; - fl_index = fs_freelist_for_size (data_bytes); - if (fss->free_chunks[fl_index + 1]) + /* As last attempt, try allocating a chunk larger than + * the requested size, if possible */ + fl_index = fs_freelist_for_size (data_bytes) + 1; + if (!fss_chunk_fl_index_is_valid (fss, fl_index)) + return 0; + first = fss_chunk_free_list_pop (fss, fl_index); + if (first) { - fl_index += 1; - fl_size = fs_freelist_index_to_size (fl_index); - continue; + first->next = 0; + n_alloc = fs_freelist_index_to_size (fl_index); + goto done; } - return 0; } fl_index -= 1; @@ -400,100 +440,45 @@ fs_try_alloc_multi_chunk (fifo_segment_header_t * fsh, } } +done: fss->n_fl_chunk_bytes -= n_alloc; fsh_cached_bytes_sub (fsh, n_alloc); return first; } -static svm_fifo_t * -fs_try_alloc_fifo_freelist_multi_chunk (fifo_segment_header_t * fsh, - fifo_segment_slice_t * fss, - u32 data_bytes) +static int +fsh_try_alloc_fifo_hdr_batch (fifo_segment_header_t * fsh, + fifo_segment_slice_t * fss, u32 batch_size) { - svm_fifo_chunk_t *c, *first = 0, *last = 0, *next; - u32 fl_index, fl_size, n_alloc = 0; svm_fifo_t *f; + void *oldheap; + uword size; + u8 *fmem; + int i; - f = fss->free_fifos; - if (!f) - { - if (PREDICT_FALSE (fsh_n_free_bytes (fsh) < sizeof (svm_fifo_t))) - return 0; - - void *oldheap = ssvm_push_heap (fsh->ssvm_sh); - f = clib_mem_alloc_aligned_or_null (sizeof (*f), CLIB_CACHE_LINE_BYTES); - ssvm_pop_heap (oldheap); - if (!f) - return 0; - memset (f, 0, sizeof (*f)); - fsh_free_bytes_sub (fsh, sizeof (*f)); - } - else - { - fss->free_fifos = f->next; - } + size = (uword) sizeof (*f) * batch_size; - fl_index = fs_freelist_for_size (data_bytes); - if (fl_index > 0) - fl_index -= 1; + oldheap = ssvm_push_heap (fsh->ssvm_sh); + fmem = clib_mem_alloc_aligned_at_offset (size, CLIB_CACHE_LINE_BYTES, + 0 /* align_offset */ , + 0 /* os_out_of_memory */ ); + ssvm_pop_heap (oldheap); - fl_size = fs_freelist_index_to_size (fl_index); + /* Out of space.. */ + if (fmem == 0) + return -1; - while (data_bytes) + /* Carve fifo hdr space */ + for (i = 0; i < batch_size; i++) { - c = fss->free_chunks[fl_index]; - if (c) - { - fss->free_chunks[fl_index] = c->next; - if (!last) - last = c; - c->next = first; - first = c; - n_alloc += fl_size; - data_bytes -= clib_min (fl_size, data_bytes); - } - else - { - /* Failed to allocate with smaller chunks */ - if (fl_index == 0) - { - /* free all chunks if any allocated */ - c = first; - while (c) - { - fl_index = fs_freelist_for_size (c->length); - fl_size = fs_freelist_index_to_size (fl_index); - next = c->next; - c->next = fss->free_chunks[fl_index]; - fss->free_chunks[fl_index] = c; - fss->n_fl_chunk_bytes += fl_size; - n_alloc -= fl_size; - data_bytes += fl_size; - c = next; - } - first = last = 0; - fl_index = fs_freelist_for_size (data_bytes); - if (fss->free_chunks[fl_index + 1]) - { - fl_index += 1; - fl_size = fs_freelist_index_to_size (fl_index); - continue; - } - - f->next = fss->free_fifos; - fss->free_fifos = f; - return 0; - } - fl_index -= 1; - fl_size = fl_size >> 1; - } + f = (svm_fifo_t *) fmem; + memset (f, 0, sizeof (*f)); + f->next = fss->free_fifos; + fss->free_fifos = f; + fmem += sizeof (*f); } - f->start_chunk = first; - f->end_chunk = last; - fss->n_fl_chunk_bytes -= n_alloc; - fsh_cached_bytes_sub (fsh, n_alloc); - return f; + return 0; } static int @@ -502,7 +487,7 @@ fsh_try_alloc_chunk_batch (fifo_segment_header_t * fsh, u32 fl_index, u32 batch_size) { u32 rounded_data_size; - svm_fifo_chunk_t *c; + svm_fifo_chunk_t *c, *head = 0, *tail; void *oldheap; uword size; u8 *cmem; @@ -522,18 +507,20 @@ fsh_try_alloc_chunk_batch (fifo_segment_header_t * fsh, return -1; /* Carve fifo + chunk space */ + tail = c = (svm_fifo_chunk_t *) cmem; for (i = 0; i < batch_size; i++) { - c = (svm_fifo_chunk_t *) cmem; c->start_byte = 0; c->length = rounded_data_size; c->enq_rb_index = RBTREE_TNIL_INDEX; c->deq_rb_index = RBTREE_TNIL_INDEX; - c->next = fss->free_chunks[fl_index]; - fss->free_chunks[fl_index] = c; + c->next = head; + head = c; cmem += sizeof (*c) + rounded_data_size; + c = (svm_fifo_chunk_t *) cmem; } + fss_chunk_free_list_push_list (fss, fl_index, head, tail); fss->num_chunks[fl_index] += batch_size; fss->n_fl_chunk_bytes += batch_size * rounded_data_size; fsh_cached_bytes_add (fsh, batch_size * rounded_data_size); @@ -547,57 +534,93 @@ fs_try_alloc_fifo_batch (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss, u32 fl_index, u32 batch_size) { - u32 hdrs, rounded_data_size; - svm_fifo_chunk_t *c; + if (fsh_try_alloc_fifo_hdr_batch (fsh, fss, batch_size)) + return 0; + return fsh_try_alloc_chunk_batch (fsh, fss, fl_index, batch_size); +} + +static svm_fifo_t * +fsh_try_alloc_fifo_hdr (fifo_segment_header_t * fsh, + fifo_segment_slice_t * fss) +{ svm_fifo_t *f; - void *oldheap; - uword size; - u8 *fmem; - int i; - rounded_data_size = fs_freelist_index_to_size (fl_index); - hdrs = sizeof (*f) + sizeof (*c); - size = (uword) (hdrs + rounded_data_size) * batch_size; + if (!fss->free_fifos) + { + if (fsh_try_alloc_fifo_hdr_batch (fsh, fss, + FIFO_SEGMENT_ALLOC_BATCH_SIZE)) + return 0; + } - oldheap = ssvm_push_heap (fsh->ssvm_sh); - fmem = clib_mem_alloc_aligned_at_offset (size, CLIB_CACHE_LINE_BYTES, - 0 /* align_offset */ , - 0 /* os_out_of_memory */ ); - ssvm_pop_heap (oldheap); + f = fss->free_fifos; + fss->free_fifos = f->next; + memset (f, 0, sizeof (*f)); + return f; +} - /* Out of space.. */ - if (fmem == 0) - return -1; +static svm_fifo_chunk_t * +fsh_try_alloc_chunk (fifo_segment_header_t * fsh, + fifo_segment_slice_t * fss, u32 data_bytes) +{ + svm_fifo_chunk_t *c; + u32 fl_index; - /* Carve fifo hdr space */ - for (i = 0; i < batch_size; i++) + fl_index = fs_freelist_for_size (data_bytes); + +free_list: + c = fss_chunk_free_list_pop (fss, fl_index); + if (c) { - f = (svm_fifo_t *) fmem; - memset (f, 0, sizeof (*f)); - f->next = fss->free_fifos; - fss->free_fifos = f; - fmem += sizeof (*f); + c->next = 0; + fss->n_fl_chunk_bytes -= fs_freelist_index_to_size (fl_index); + fsh_cached_bytes_sub (fsh, fs_freelist_index_to_size (fl_index)); } - - /* Carve chunk space */ - for (i = 0; i < batch_size; i++) + else { - c = (svm_fifo_chunk_t *) fmem; - c->start_byte = 0; - c->length = rounded_data_size; - c->enq_rb_index = RBTREE_TNIL_INDEX; - c->deq_rb_index = RBTREE_TNIL_INDEX; - c->next = fss->free_chunks[fl_index]; - fss->free_chunks[fl_index] = c; - fmem += sizeof (svm_fifo_chunk_t) + rounded_data_size; + u32 chunk_size, batch = FIFO_SEGMENT_ALLOC_BATCH_SIZE; + uword n_free; + + chunk_size = fs_freelist_index_to_size (fl_index); + n_free = fsh_n_free_bytes (fsh); + + if (chunk_size <= n_free) + { + batch = chunk_size * batch <= n_free ? batch : 1; + if (!fsh_try_alloc_chunk_batch (fsh, fss, fl_index, batch)) + goto free_list; + } + /* Failed to allocate larger chunk, try to allocate multi-chunk + * that is close to what was actually requested */ + if (data_bytes <= fss->n_fl_chunk_bytes) + { + c = fs_try_alloc_multi_chunk (fsh, fss, data_bytes); + if (c) + goto done; + batch = n_free / FIFO_SEGMENT_MIN_FIFO_SIZE; + if (!batch || fsh_try_alloc_chunk_batch (fsh, fss, 0, batch)) + { + fsh_check_mem (fsh); + goto done; + } + } + if (data_bytes <= fss->n_fl_chunk_bytes + n_free) + { + u32 min_size = FIFO_SEGMENT_MIN_FIFO_SIZE; + + batch = (data_bytes - fss->n_fl_chunk_bytes) / min_size; + batch = clib_min (batch + 1, n_free / min_size); + if (fsh_try_alloc_chunk_batch (fsh, fss, 0, batch)) + { + fsh_check_mem (fsh); + goto done; + } + c = fs_try_alloc_multi_chunk (fsh, fss, data_bytes); + } } - fss->num_chunks[fl_index] += batch_size; - fss->n_fl_chunk_bytes += batch_size * rounded_data_size; - fsh_cached_bytes_add (fsh, batch_size * rounded_data_size); - fsh_free_bytes_sub (fsh, size); +done: - return 0; + return c; } /** @@ -613,69 +636,37 @@ static svm_fifo_t * fs_try_alloc_fifo (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss, u32 data_bytes) { - u32 fifo_sz, fl_index; + u32 fl_index; + svm_fifo_chunk_t *c; svm_fifo_t *f = 0; - uword n_free_bytes; u32 min_size; min_size = clib_max ((fsh->pct_first_alloc * data_bytes) / 100, 4096); fl_index = fs_freelist_for_size (min_size); - if (fl_index >= vec_len (fss->free_chunks)) + if (!fss_chunk_fl_index_is_valid (fss, fl_index)) return 0; clib_spinlock_lock (&fss->chunk_lock); - if (fss->free_fifos && fss->free_chunks[fl_index]) - { - f = fs_try_alloc_fifo_freelist (fss, fl_index); - if (f) - { - fsh_cached_bytes_sub (fsh, fs_freelist_index_to_size (fl_index)); - goto done; - } - } - - fifo_sz = sizeof (svm_fifo_t) + sizeof (svm_fifo_chunk_t); - fifo_sz += 1 << max_log2 (min_size); - n_free_bytes = fsh_n_free_bytes (fsh); + f = fsh_try_alloc_fifo_hdr (fsh, fss); + if (!f) + goto done; - if (fifo_sz * FIFO_SEGMENT_ALLOC_BATCH_SIZE < n_free_bytes) + c = fsh_try_alloc_chunk (fsh, fss, min_size); + if (c) { - if (!fs_try_alloc_fifo_batch (fsh, fss, fl_index, - FIFO_SEGMENT_ALLOC_BATCH_SIZE)) - { - f = fs_try_alloc_fifo_freelist (fss, fl_index); - if (f) - { - fsh_cached_bytes_sub (fsh, - fs_freelist_index_to_size (fl_index)); - goto done; - } - } - else - { - fsh_check_mem (fsh); - n_free_bytes = fsh_n_free_bytes (fsh); - } + f->start_chunk = c; + while (c->next) + c = c->next; + f->end_chunk = c; } - if (fifo_sz <= n_free_bytes) + else { - void *oldheap = ssvm_push_heap (fsh->ssvm_sh); - f = svm_fifo_alloc (min_size); - ssvm_pop_heap (oldheap); - if (f) - { - clib_atomic_fetch_add_rel (&fss->num_chunks[fl_index], 1); - fsh_free_bytes_sub (fsh, fifo_sz); - goto done; - } - fsh_check_mem (fsh); + f->next = fss->free_fifos; + fss->free_fifos = f; + f = 0; } - /* All failed, try to allocate min of data bytes and fifo sz */ - fifo_sz = clib_min (fifo_sz, data_bytes); - if (fifo_sz <= fss->n_fl_chunk_bytes) - f = fs_try_alloc_fifo_freelist_multi_chunk (fsh, fss, fifo_sz); done: clib_spinlock_unlock (&fss->chunk_lock); @@ -693,77 +684,11 @@ fsh_alloc_chunk (fifo_segment_header_t * fsh, u32 slice_index, u32 chunk_size) { fifo_segment_slice_t *fss; svm_fifo_chunk_t *c; - int fl_index; - fl_index = fs_freelist_for_size (chunk_size); fss = fsh_slice_get (fsh, slice_index); clib_spinlock_lock (&fss->chunk_lock); - - ASSERT (vec_len (fss->free_chunks) > fl_index); - c = fss->free_chunks[fl_index]; - - if (c) - { - fss->free_chunks[fl_index] = c->next; - c->next = 0; - fss->n_fl_chunk_bytes -= fs_freelist_index_to_size (fl_index); - fsh_cached_bytes_sub (fsh, fs_freelist_index_to_size (fl_index)); - } - else - { - void *oldheap; - uword n_free; - u32 batch; - - chunk_size = fs_freelist_index_to_size (fl_index); - n_free = fsh_n_free_bytes (fsh); - - if (chunk_size <= n_free) - { - oldheap = ssvm_push_heap (fsh->ssvm_sh); - c = svm_fifo_chunk_alloc (chunk_size); - ssvm_pop_heap (oldheap); - - if (c) - { - clib_atomic_fetch_add_rel (&fss->num_chunks[fl_index], 1); - fsh_free_bytes_sub (fsh, chunk_size + sizeof (*c)); - goto done; - } - - fsh_check_mem (fsh); - n_free = fsh_n_free_bytes (fsh); - } - if (chunk_size <= fss->n_fl_chunk_bytes) - { - c = fs_try_alloc_multi_chunk (fsh, fss, chunk_size); - if (c) - goto done; - batch = n_free / FIFO_SEGMENT_MIN_FIFO_SIZE; - if (!batch || fsh_try_alloc_chunk_batch (fsh, fss, 0, batch)) - { - fsh_check_mem (fsh); - goto done; - } - } - if (chunk_size <= fss->n_fl_chunk_bytes + n_free) - { - u32 min_size = FIFO_SEGMENT_MIN_FIFO_SIZE; - - batch = (chunk_size - fss->n_fl_chunk_bytes) / min_size; - batch = clib_min (batch + 1, n_free / min_size); - if (fsh_try_alloc_chunk_batch (fsh, fss, 0, batch)) - { - fsh_check_mem (fsh); - goto done; - } - c = fs_try_alloc_multi_chunk (fsh, fss, chunk_size); - } - } - -done: - + c = fsh_try_alloc_chunk (fsh, fss, chunk_size); clib_spinlock_unlock (&fss->chunk_lock); return c; @@ -773,9 +698,8 @@ static void fsh_slice_collect_chunks (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss, svm_fifo_chunk_t * c) { + u32 n_collect = 0, fl_index; svm_fifo_chunk_t *next; - int fl_index; - u32 n_collect = 0; clib_spinlock_lock (&fss->chunk_lock); @@ -784,10 +708,9 @@ fsh_slice_collect_chunks (fifo_segment_header_t * fsh, CLIB_MEM_UNPOISON (c, sizeof (*c)); next = c->next; fl_index = fs_freelist_for_size (c->length); - c->next = fss->free_chunks[fl_index]; c->enq_rb_index = RBTREE_TNIL_INDEX; c->deq_rb_index = RBTREE_TNIL_INDEX; - fss->free_chunks[fl_index] = c; + fss_chunk_free_list_push (fss, fl_index, c); n_collect += fs_freelist_index_to_size (fl_index); c = next; } @@ -807,31 +730,6 @@ fsh_collect_chunks (fifo_segment_header_t * fsh, u32 slice_index, fsh_slice_collect_chunks (fsh, fss, c); } -static inline void -fss_fifo_add_active_list (fifo_segment_slice_t * fss, svm_fifo_t * f) -{ - if (fss->fifos) - { - fss->fifos->prev = f; - f->next = fss->fifos; - } - fss->fifos = f; -} - -static inline void -fss_fifo_del_active_list (fifo_segment_slice_t * fss, svm_fifo_t * f) -{ - if (f->flags & SVM_FIFO_F_LL_TRACKED) - { - if (f->prev) - f->prev->next = f->next; - else - fss->fifos = f->next; - if (f->next) - f->next->prev = f->prev; - } -} - /** * Allocate fifo in fifo segment */ @@ -1014,13 +912,8 @@ fifo_segment_prealloc_fifo_chunks (fifo_segment_t * fs, u32 slice_index, u32 chunk_size, u32 batch_size) { fifo_segment_header_t *fsh = fs->h; - u32 rounded_data_size, fl_index; fifo_segment_slice_t *fss; - svm_fifo_chunk_t *c; - void *oldheap; - uword size; - u8 *cmem; - int i; + u32 fl_index; if (!fs_chunk_size_is_valid (fsh, chunk_size)) { @@ -1029,38 +922,9 @@ fifo_segment_prealloc_fifo_chunks (fifo_segment_t * fs, u32 slice_index, } fl_index = fs_freelist_for_size (chunk_size); - rounded_data_size = fs_freelist_index_to_size (fl_index); - size = (uword) (sizeof (*c) + rounded_data_size) * batch_size; - - oldheap = ssvm_push_heap (fsh->ssvm_sh); - cmem = clib_mem_alloc_aligned_at_offset (size, CLIB_CACHE_LINE_BYTES, - 0 /* align_offset */ , - 0 /* os_out_of_memory */ ); - ssvm_pop_heap (oldheap); - - /* Out of space.. */ - if (cmem == 0) - return -1; - fss = fsh_slice_get (fsh, slice_index); - /* Carve fifo + chunk space */ - for (i = 0; i < batch_size; i++) - { - c = (svm_fifo_chunk_t *) cmem; - c->start_byte = 0; - c->length = rounded_data_size; - c->next = fss->free_chunks[fl_index]; - fss->free_chunks[fl_index] = c; - cmem += sizeof (*c) + rounded_data_size; - fsh_cached_bytes_add (fsh, rounded_data_size); - } - - fss->num_chunks[fl_index] += batch_size; - fss->n_fl_chunk_bytes += batch_size * rounded_data_size; - fsh_free_bytes_sub (fsh, size); - - return 0; + return fsh_try_alloc_chunk_batch (fsh, fss, fl_index, batch_size); } /** -- 2.16.6