From 5c10dbb7b577370e86ff459973b06d530c3777cf Mon Sep 17 00:00:00 2001 From: Peter Lieven Date: Fri, 30 Oct 2015 12:09:56 +0100 Subject: buffer: make the Buffer capacity increase in powers of two This makes sure the number of reallocs is in O(log N). Signed-off-by: Peter Lieven Reviewed-by: Daniel P. Berrange Signed-off-by: Gerd Hoffmann Message-id: 1446203414-4013-2-git-send-email-kraxel@redhat.com [ rebased to util/buffer.c ] Signed-off-by: Gerd Hoffmann --- util/buffer.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index cedd055..7ddd693 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -20,10 +20,13 @@ #include "qemu/buffer.h" +#define BUFFER_MIN_INIT_SIZE 4096 + void buffer_reserve(Buffer *buffer, size_t len) { if ((buffer->capacity - buffer->offset) < len) { - buffer->capacity += (len + 1024); + buffer->capacity = pow2ceil(buffer->offset + len); + buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_INIT_SIZE); buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); } } -- cgit v1.1 From 810082d15c244b8b29470d3bb1c6b11fc9a40c25 Mon Sep 17 00:00:00 2001 From: Gerd Hoffmann Date: Fri, 30 Oct 2015 12:09:57 +0100 Subject: buffer: add buffer_init Signed-off-by: Gerd Hoffmann Reviewed-by: Peter Lieven Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-3-git-send-email-kraxel@redhat.com --- util/buffer.c | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index 7ddd693..12bf2d7 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -22,6 +22,15 @@ #define BUFFER_MIN_INIT_SIZE 4096 +void buffer_init(Buffer *buffer, const char *name, ...) +{ + va_list ap; + + va_start(ap, name); + buffer->name = g_strdup_vprintf(name, ap); + va_end(ap); +} + void buffer_reserve(Buffer *buffer, size_t len) { if ((buffer->capacity - buffer->offset) < len) { @@ -49,9 +58,11 @@ void buffer_reset(Buffer *buffer) void buffer_free(Buffer *buffer) { g_free(buffer->buffer); + g_free(buffer->name); buffer->offset = 0; buffer->capacity = 0; buffer->buffer = NULL; + buffer->name = NULL; } void buffer_append(Buffer *buffer, const void *data, size_t len) -- cgit v1.1 From 4d1eb5fdb141c9100eb82e1dc7d4547fb1decd8b Mon Sep 17 00:00:00 2001 From: Gerd Hoffmann Date: Fri, 30 Oct 2015 12:09:58 +0100 Subject: buffer: add buffer_move_empty Signed-off-by: Gerd Hoffmann Reviewed-by: Peter Lieven Reviewed-by: Daniel Berrange Message-id: 1446203414-4013-4-git-send-email-kraxel@redhat.com --- util/buffer.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index 12bf2d7..c7a39ec 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -77,3 +77,17 @@ void buffer_advance(Buffer *buffer, size_t len) (buffer->offset - len)); buffer->offset -= len; } + +void buffer_move_empty(Buffer *to, Buffer *from) +{ + assert(to->offset == 0); + + g_free(to->buffer); + to->offset = from->offset; + to->capacity = from->capacity; + to->buffer = from->buffer; + + from->offset = 0; + from->capacity = 0; + from->buffer = NULL; +} -- cgit v1.1 From 830a9583206a051c240b74c3f688a015dc5d2967 Mon Sep 17 00:00:00 2001 From: Gerd Hoffmann Date: Fri, 30 Oct 2015 12:09:59 +0100 Subject: buffer: add buffer_move Signed-off-by: Gerd Hoffmann Reviewed-by: Peter Lieven Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-5-git-send-email-kraxel@redhat.com --- util/buffer.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index c7a39ec..e8f798e 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -91,3 +91,19 @@ void buffer_move_empty(Buffer *to, Buffer *from) from->capacity = 0; from->buffer = NULL; } + +void buffer_move(Buffer *to, Buffer *from) +{ + if (to->offset == 0) { + buffer_move_empty(to, from); + return; + } + + buffer_reserve(to, from->offset); + buffer_append(to, from->buffer, from->offset); + + g_free(from->buffer); + from->offset = 0; + from->capacity = 0; + from->buffer = NULL; +} -- cgit v1.1 From 1ff36b5d4d00a4e3633eb960bf2be562f5e47dbf Mon Sep 17 00:00:00 2001 From: Gerd Hoffmann Date: Fri, 30 Oct 2015 12:10:00 +0100 Subject: buffer: add buffer_shrink Signed-off-by: Gerd Hoffmann Reviewed-by: Peter Lieven Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-6-git-send-email-kraxel@redhat.com --- util/buffer.c | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index e8f798e..234e33d 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -20,7 +20,8 @@ #include "qemu/buffer.h" -#define BUFFER_MIN_INIT_SIZE 4096 +#define BUFFER_MIN_INIT_SIZE 4096 +#define BUFFER_MIN_SHRINK_SIZE 65536 void buffer_init(Buffer *buffer, const char *name, ...) { @@ -31,6 +32,23 @@ void buffer_init(Buffer *buffer, const char *name, ...) va_end(ap); } +void buffer_shrink(Buffer *buffer) +{ + /* + * Only shrink in case the used size is *much* smaller than the + * capacity, to avoid bumping up & down the buffers all the time. + * realloc() isn't exactly cheap ... + */ + if (buffer->offset < (buffer->capacity >> 3) && + buffer->capacity > BUFFER_MIN_SHRINK_SIZE) { + return; + } + + buffer->capacity = pow2ceil(buffer->offset); + buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_SHRINK_SIZE); + buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); +} + void buffer_reserve(Buffer *buffer, size_t len) { if ((buffer->capacity - buffer->offset) < len) { -- cgit v1.1 From d2b90718d25ed6dc8a2bb7f06504e6500dcc7bae Mon Sep 17 00:00:00 2001 From: Gerd Hoffmann Date: Fri, 30 Oct 2015 12:10:01 +0100 Subject: buffer: add tracing Signed-off-by: Gerd Hoffmann Reviewed-by: Peter Lieven Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-7-git-send-email-kraxel@redhat.com --- util/buffer.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index 234e33d..ae2907e 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -19,6 +19,7 @@ */ #include "qemu/buffer.h" +#include "trace.h" #define BUFFER_MIN_INIT_SIZE 4096 #define BUFFER_MIN_SHRINK_SIZE 65536 @@ -34,6 +35,8 @@ void buffer_init(Buffer *buffer, const char *name, ...) void buffer_shrink(Buffer *buffer) { + size_t old; + /* * Only shrink in case the used size is *much* smaller than the * capacity, to avoid bumping up & down the buffers all the time. @@ -44,17 +47,25 @@ void buffer_shrink(Buffer *buffer) return; } + old = buffer->capacity; buffer->capacity = pow2ceil(buffer->offset); buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_SHRINK_SIZE); buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); + trace_buffer_resize(buffer->name ?: "unnamed", + old, buffer->capacity); } void buffer_reserve(Buffer *buffer, size_t len) { + size_t old; + if ((buffer->capacity - buffer->offset) < len) { + old = buffer->capacity; buffer->capacity = pow2ceil(buffer->offset + len); buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_INIT_SIZE); buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); + trace_buffer_resize(buffer->name ?: "unnamed", + old, buffer->capacity); } } @@ -75,6 +86,7 @@ void buffer_reset(Buffer *buffer) void buffer_free(Buffer *buffer) { + trace_buffer_free(buffer->name ?: "unnamed", buffer->capacity); g_free(buffer->buffer); g_free(buffer->name); buffer->offset = 0; @@ -98,6 +110,9 @@ void buffer_advance(Buffer *buffer, size_t len) void buffer_move_empty(Buffer *to, Buffer *from) { + trace_buffer_move_empty(to->name ?: "unnamed", + from->offset, + from->name ?: "unnamed"); assert(to->offset == 0); g_free(to->buffer); @@ -117,6 +132,9 @@ void buffer_move(Buffer *to, Buffer *from) return; } + trace_buffer_move(to->name ?: "unnamed", + from->offset, + from->name ?: "unnamed"); buffer_reserve(to, from->offset); buffer_append(to, from->buffer, from->offset); -- cgit v1.1 From fd95243372f7657c2d24aed269e3be01bed1b87c Mon Sep 17 00:00:00 2001 From: Peter Lieven Date: Fri, 30 Oct 2015 12:10:12 +0100 Subject: buffer: factor out buffer_req_size Signed-off-by: Peter Lieven Signed-off-by: Gerd Hoffmann Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-18-git-send-email-kraxel@redhat.com --- util/buffer.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index ae2907e..31f1d9f 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -24,6 +24,13 @@ #define BUFFER_MIN_INIT_SIZE 4096 #define BUFFER_MIN_SHRINK_SIZE 65536 +static size_t buffer_req_size(Buffer *buffer, size_t len) +{ + return MAX(BUFFER_MIN_INIT_SIZE, + pow2ceil(buffer->offset + len)); +} + + void buffer_init(Buffer *buffer, const char *name, ...) { va_list ap; @@ -61,8 +68,7 @@ void buffer_reserve(Buffer *buffer, size_t len) if ((buffer->capacity - buffer->offset) < len) { old = buffer->capacity; - buffer->capacity = pow2ceil(buffer->offset + len); - buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_INIT_SIZE); + buffer->capacity = buffer_req_size(buffer, len); buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); trace_buffer_resize(buffer->name ?: "unnamed", old, buffer->capacity); -- cgit v1.1 From 4ec5ba151ff3f2ac8dc44dabd058eca5846654a6 Mon Sep 17 00:00:00 2001 From: Peter Lieven Date: Fri, 30 Oct 2015 12:10:13 +0100 Subject: buffer: factor out buffer_adj_size Signed-off-by: Peter Lieven Signed-off-by: Gerd Hoffmann Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-19-git-send-email-kraxel@redhat.com --- util/buffer.c | 25 ++++++++++--------------- 1 file changed, 10 insertions(+), 15 deletions(-) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index 31f1d9f..fe5a44e 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -30,6 +30,14 @@ static size_t buffer_req_size(Buffer *buffer, size_t len) pow2ceil(buffer->offset + len)); } +static void buffer_adj_size(Buffer *buffer, size_t len) +{ + size_t old = buffer->capacity; + buffer->capacity = buffer_req_size(buffer, len); + buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); + trace_buffer_resize(buffer->name ?: "unnamed", + old, buffer->capacity); +} void buffer_init(Buffer *buffer, const char *name, ...) { @@ -42,8 +50,6 @@ void buffer_init(Buffer *buffer, const char *name, ...) void buffer_shrink(Buffer *buffer) { - size_t old; - /* * Only shrink in case the used size is *much* smaller than the * capacity, to avoid bumping up & down the buffers all the time. @@ -54,24 +60,13 @@ void buffer_shrink(Buffer *buffer) return; } - old = buffer->capacity; - buffer->capacity = pow2ceil(buffer->offset); - buffer->capacity = MAX(buffer->capacity, BUFFER_MIN_SHRINK_SIZE); - buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); - trace_buffer_resize(buffer->name ?: "unnamed", - old, buffer->capacity); + buffer_adj_size(buffer, 0); } void buffer_reserve(Buffer *buffer, size_t len) { - size_t old; - if ((buffer->capacity - buffer->offset) < len) { - old = buffer->capacity; - buffer->capacity = buffer_req_size(buffer, len); - buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); - trace_buffer_resize(buffer->name ?: "unnamed", - old, buffer->capacity); + buffer_adj_size(buffer, len); } } -- cgit v1.1 From f14c3d85b003d8614144ae67a26157667c1e1245 Mon Sep 17 00:00:00 2001 From: Peter Lieven Date: Fri, 30 Oct 2015 12:10:14 +0100 Subject: buffer: allow a buffer to shrink gracefully the idea behind this patch is to allow the buffer to shrink, but make this a seldom operation. The buffers average size is measured exponentionally smoothed with am alpha of 1/128. Signed-off-by: Peter Lieven Signed-off-by: Gerd Hoffmann Reviewed-by: Daniel P. Berrange Message-id: 1446203414-4013-20-git-send-email-kraxel@redhat.com --- util/buffer.c | 41 +++++++++++++++++++++++++++++++++-------- 1 file changed, 33 insertions(+), 8 deletions(-) (limited to 'util') diff --git a/util/buffer.c b/util/buffer.c index fe5a44e..8b27c08 100644 --- a/util/buffer.c +++ b/util/buffer.c @@ -24,6 +24,11 @@ #define BUFFER_MIN_INIT_SIZE 4096 #define BUFFER_MIN_SHRINK_SIZE 65536 +/* define the factor alpha for the expentional smoothing + * that is used in the average size calculation. a shift + * of 7 results in an alpha of 1/2^7. */ +#define BUFFER_AVG_SIZE_SHIFT 7 + static size_t buffer_req_size(Buffer *buffer, size_t len) { return MAX(BUFFER_MIN_INIT_SIZE, @@ -37,6 +42,11 @@ static void buffer_adj_size(Buffer *buffer, size_t len) buffer->buffer = g_realloc(buffer->buffer, buffer->capacity); trace_buffer_resize(buffer->name ?: "unnamed", old, buffer->capacity); + + /* make it even harder for the buffer to shrink, reset average size + * to currenty capacity if it is larger than the average. */ + buffer->avg_size = MAX(buffer->avg_size, + buffer->capacity << BUFFER_AVG_SIZE_SHIFT); } void buffer_init(Buffer *buffer, const char *name, ...) @@ -48,16 +58,29 @@ void buffer_init(Buffer *buffer, const char *name, ...) va_end(ap); } +static uint64_t buffer_get_avg_size(Buffer *buffer) +{ + return buffer->avg_size >> BUFFER_AVG_SIZE_SHIFT; +} + void buffer_shrink(Buffer *buffer) { - /* - * Only shrink in case the used size is *much* smaller than the - * capacity, to avoid bumping up & down the buffers all the time. - * realloc() isn't exactly cheap ... - */ - if (buffer->offset < (buffer->capacity >> 3) && - buffer->capacity > BUFFER_MIN_SHRINK_SIZE) { - return; + size_t new; + + /* Calculate the average size of the buffer as + * avg_size = avg_size * ( 1 - a ) + required_size * a + * where a is 1 / 2 ^ BUFFER_AVG_SIZE_SHIFT. */ + buffer->avg_size *= (1 << BUFFER_AVG_SIZE_SHIFT) - 1; + buffer->avg_size >>= BUFFER_AVG_SIZE_SHIFT; + buffer->avg_size += buffer_req_size(buffer, 0); + + /* And then only shrink if the average size of the buffer is much + * too big, to avoid bumping up & down the buffers all the time. + * realloc() isn't exactly cheap ... */ + new = buffer_req_size(buffer, buffer_get_avg_size(buffer)); + if (new < buffer->capacity >> 3 && + new >= BUFFER_MIN_SHRINK_SIZE) { + buffer_adj_size(buffer, buffer_get_avg_size(buffer)); } buffer_adj_size(buffer, 0); @@ -83,6 +106,7 @@ uint8_t *buffer_end(Buffer *buffer) void buffer_reset(Buffer *buffer) { buffer->offset = 0; + buffer_shrink(buffer); } void buffer_free(Buffer *buffer) @@ -107,6 +131,7 @@ void buffer_advance(Buffer *buffer, size_t len) memmove(buffer->buffer, buffer->buffer + len, (buffer->offset - len)); buffer->offset -= len; + buffer_shrink(buffer); } void buffer_move_empty(Buffer *to, Buffer *from) -- cgit v1.1