[Qemu-devel] [PATCH 0/2] vnc buffer enhancements for 2.5

[Qemu-devel] [PATCH 0/2] vnc buffer enhancements for 2.5

[Peter Lieven]

These are 2 patches on top of Gerds improve buffer handling series.

Patch 1 is an updated version of the patch included in Gerds series and
Patch 2 is a further optimization open for discussion.

Peter

Peter Lieven (2):
  io/buffer: allow a buffer to shrink gracefully
  io/buffer: avoid memmove at each qio_buffer_advance

 include/io/buffer.h |  3 ++
 io/buffer.c         | 81 +++++++++++++++++++++++++++++++++++++++++------------
 2 files changed, 66 insertions(+), 18 deletions(-)

-- 
1.9.1

[Qemu-devel] [PATCH 1/2] io/buffer: allow a buffer to shrink gracefully

[Peter Lieven]

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 <pl@kamp.de>
---
 include/io/buffer.h |  1 +
 io/buffer.c         | 42 +++++++++++++++++++++++++++++++++---------
 2 files changed, 34 insertions(+), 9 deletions(-)

diff --git a/include/io/buffer.h b/include/io/buffer.h
index f6668cb..f63869e 100644
--- a/include/io/buffer.h
+++ b/include/io/buffer.h
@@ -37,6 +37,7 @@ struct QIOBuffer {
     char *name;
     size_t capacity;
     size_t offset;
+    uint64_t avg_size;
     uint8_t *buffer;
 };
 
diff --git a/io/buffer.c b/io/buffer.c
index 0fd3cea..d2a6043 100644
--- a/io/buffer.c
+++ b/io/buffer.c
@@ -23,6 +23,10 @@
 
 #define QIO_BUFFER_MIN_INIT_SIZE     4096
 #define QIO_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 QIO_BUFFER_AVG_SIZE_SHIFT       7
 
 static size_t buf_req_size(QIOBuffer *buffer, size_t len)
 {
@@ -37,6 +41,11 @@ static void buf_adj_size(QIOBuffer *buffer, size_t len)
     buffer->buffer = g_realloc(buffer->buffer, buffer->capacity);
     trace_qio_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 << QIO_BUFFER_AVG_SIZE_SHIFT);
 }
 
 void qio_buffer_init(QIOBuffer *buffer, const char *name, ...)
@@ -48,21 +57,34 @@ void qio_buffer_init(QIOBuffer *buffer, const char *name, ...)
     va_end(ap);
 }
 
-void qio_buffer_shrink(QIOBuffer *buffer)
+static uint64_t get_buf_avg_size(QIOBuffer *buffer)
 {
-    /*
-     * Only shrink in case the used size is *much* smaller than the
-     * capacity, to avoid bumping up & down the buffers all the time.
+    return buffer->avg_size >> QIO_BUFFER_AVG_SIZE_SHIFT;
+}
+
+void qio_buffer_shrink(QIOBuffer *buffer)
+ {
+    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 ^ QIO_BUFFER_AVG_SIZE_SHIFT. */
+    buffer->avg_size *= (1 << QIO_BUFFER_AVG_SIZE_SHIFT) - 1;
+    buffer->avg_size >>= QIO_BUFFER_AVG_SIZE_SHIFT;
+    buffer->avg_size += buf_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 ...
      */
-    if (buffer->offset < (buffer->capacity >> 3) &&
-        buffer->capacity > QIO_BUFFER_MIN_SHRINK_SIZE) {
-        return;
+    new = buf_req_size(buffer, get_buf_avg_size(buffer));
+    if (new < buffer->capacity >> 3 &&
+        new >= QIO_BUFFER_MIN_SHRINK_SIZE) {
+        buf_adj_size(buffer, get_buf_avg_size(buffer));
     }
-
-    buf_adj_size(buffer, 0);
 }
 
+
 void qio_buffer_reserve(QIOBuffer *buffer, size_t len)
 {
     if ((buffer->capacity - buffer->offset) < len) {
@@ -83,6 +105,7 @@ uint8_t *qio_buffer_end(QIOBuffer *buffer)
 void qio_buffer_reset(QIOBuffer *buffer)
 {
     buffer->offset = 0;
+    qio_buffer_shrink(buffer);
 }
 
 void qio_buffer_free(QIOBuffer *buffer)
@@ -107,6 +130,7 @@ void qio_buffer_advance(QIOBuffer *buffer, size_t len)
     memmove(buffer->buffer, buffer->buffer + len,
             (buffer->offset - len));
     buffer->offset -= len;
+    qio_buffer_shrink(buffer);
 }
 
 void qio_buffer_move_empty(QIOBuffer *to, QIOBuffer *from)
-- 
1.9.1

Re: [Qemu-devel] [PATCH 1/2] io/buffer: allow a buffer to shrink gracefully

[Gerd Hoffmann]

On Di, 2015-11-03 at 10:01 +0100, Peter Lieven wrote:
> diff --git a/io/buffer.c b/io/buffer.c
> index 0fd3cea..d2a6043 100644
> --- a/io/buffer.c
> +++ b/io/buffer.c
> @@ -23,6 +23,10 @@

Needs a rebase (current wip branch is available at
https://www.kraxel.org/cgit/qemu/log/?h=work/vnc-buffers)

cheers,
  Gerd

Re: [Qemu-devel] [PATCH 1/2] io/buffer: allow a buffer to shrink gracefully

[Peter Lieven]

[-- Attachment #1: Type: text/plain, Size: 456 bytes --]

Am 03.11.2015 um 11:40 schrieb Gerd Hoffmann:
> On Di, 2015-11-03 at 10:01 +0100, Peter Lieven wrote:
>> diff --git a/io/buffer.c b/io/buffer.c
>> index 0fd3cea..d2a6043 100644
>> --- a/io/buffer.c
>> +++ b/io/buffer.c
>> @@ -23,6 +23,10 @@
> Needs a rebase (current wip branch is available at
> https://www.kraxel.org/cgit/qemu/log/?h=work/vnc-buffers)

I found that the version is ok, just the comment above the BUFFER_AVG_SIZE_SHIFT is missing.

Peter


[-- Attachment #2: Type: text/html, Size: 1094 bytes --]

[Qemu-devel] [PATCH 2/2] io/buffer: avoid memmove at each qio_buffer_advance

[Peter Lieven]

memmove isn't exactly cheap at it involves temporary buffers
if the memory areas are overlapping. So make qio_buffer_advance
basically a pointer adjustment, but still keep the wasted memory
in reasonable limits.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 include/io/buffer.h |  2 ++
 io/buffer.c         | 43 ++++++++++++++++++++++++++++++++-----------
 2 files changed, 34 insertions(+), 11 deletions(-)

diff --git a/include/io/buffer.h b/include/io/buffer.h
index f63869e..43688cc 100644
--- a/include/io/buffer.h
+++ b/include/io/buffer.h
@@ -39,6 +39,8 @@ struct QIOBuffer {
     size_t offset;
     uint64_t avg_size;
     uint8_t *buffer;
+    size_t base_offs;
+    uint8_t *base_ptr;
 };
 
 /**
diff --git a/io/buffer.c b/io/buffer.c
index d2a6043..f1e4570 100644
--- a/io/buffer.c
+++ b/io/buffer.c
@@ -21,24 +21,27 @@
 #include "io/buffer.h"
 #include "trace.h"
 
-#define QIO_BUFFER_MIN_INIT_SIZE     4096
-#define QIO_BUFFER_MIN_SHRINK_SIZE  65536
+#define QIO_BUFFER_MIN_INIT_SIZE        4096
+#define QIO_BUFFER_MIN_SHRINK_SIZE     65536
+#define QIO_BUFFER_MAX_WASTED_SIZE   1048576
 /* 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 QIO_BUFFER_AVG_SIZE_SHIFT       7
+#define QIO_BUFFER_AVG_SIZE_SHIFT          7
 
 static size_t buf_req_size(QIOBuffer *buffer, size_t len)
 {
     return MAX(QIO_BUFFER_MIN_INIT_SIZE,
-               pow2ceil(buffer->offset + len));
+               pow2ceil(buffer->base_offs + buffer->offset + len));
 }
 
 static void buf_adj_size(QIOBuffer *buffer, size_t len)
 {
     size_t old = buffer->capacity;
     buffer->capacity = buf_req_size(buffer, len);
-    buffer->buffer = g_realloc(buffer->buffer, buffer->capacity);
+    buffer->base_ptr = g_realloc(buffer->base_ptr, buffer->capacity);
+    buffer->buffer = buffer->base_ptr + buffer->base_offs;
+
     trace_qio_buffer_resize(buffer->name ?: "unnamed",
                             old, buffer->capacity);
 
@@ -105,17 +108,21 @@ uint8_t *qio_buffer_end(QIOBuffer *buffer)
 void qio_buffer_reset(QIOBuffer *buffer)
 {
     buffer->offset = 0;
+    buffer->base_offs = 0;
+    buffer->buffer = buffer->base_ptr;
     qio_buffer_shrink(buffer);
 }
 
 void qio_buffer_free(QIOBuffer *buffer)
 {
     trace_qio_buffer_free(buffer->name ?: "unnamed", buffer->capacity);
-    g_free(buffer->buffer);
+    g_free(buffer->base_ptr);
     g_free(buffer->name);
     buffer->offset = 0;
+    buffer->base_offs = 0;
     buffer->capacity = 0;
     buffer->buffer = NULL;
+    buffer->base_ptr = NULL;
     buffer->name = NULL;
 }
 
@@ -127,10 +134,18 @@ void qio_buffer_append(QIOBuffer *buffer, const void *data, size_t len)
 
 void qio_buffer_advance(QIOBuffer *buffer, size_t len)
 {
-    memmove(buffer->buffer, buffer->buffer + len,
-            (buffer->offset - len));
+    if (buffer->offset - len == 0) {
+        return qio_buffer_reset(buffer);
+    }
+    buffer->buffer += len;
+    buffer->base_offs += len;
     buffer->offset -= len;
-    qio_buffer_shrink(buffer);
+    if (buffer->base_offs > QIO_BUFFER_MAX_WASTED_SIZE) {
+        memmove(buffer->base_ptr, buffer->buffer, buffer->offset);
+        buffer->buffer = buffer->base_ptr;
+        buffer->base_offs = 0;
+        qio_buffer_shrink(buffer);
+    }
 }
 
 void qio_buffer_move_empty(QIOBuffer *to, QIOBuffer *from)
@@ -140,14 +155,18 @@ void qio_buffer_move_empty(QIOBuffer *to, QIOBuffer *from)
                                 from->name ?: "unnamed");
     assert(to->offset == 0);
 
-    g_free(to->buffer);
+    g_free(to->base_ptr);
     to->offset = from->offset;
     to->capacity = from->capacity;
     to->buffer = from->buffer;
+    to->base_offs = from->base_offs;
+    to->base_ptr = from->base_ptr;
 
     from->offset = 0;
     from->capacity = 0;
     from->buffer = NULL;
+    from->base_offs = 0;
+    from->base_ptr = NULL;
 }
 
 void qio_buffer_move(QIOBuffer *to, QIOBuffer *from)
@@ -164,8 +183,10 @@ void qio_buffer_move(QIOBuffer *to, QIOBuffer *from)
     qio_buffer_reserve(to, from->offset);
     qio_buffer_append(to, from->buffer, from->offset);
 
-    g_free(from->buffer);
+    g_free(from->base_ptr);
     from->offset = 0;
     from->capacity = 0;
     from->buffer = NULL;
+    from->base_offs = 0;
+    from->base_ptr = NULL;
 }
-- 
1.9.1

Re: [Qemu-devel] [PATCH 2/2] io/buffer: avoid memmove at each qio_buffer_advance

[Gerd Hoffmann]

> diff --git a/include/io/buffer.h b/include/io/buffer.h
> index f63869e..43688cc 100644
> --- a/include/io/buffer.h
> +++ b/include/io/buffer.h
> @@ -39,6 +39,8 @@ struct QIOBuffer {
>      size_t offset;
>      uint64_t avg_size;
>      uint8_t *buffer;
> +    size_t base_offs;
> +    uint8_t *base_ptr;

Why a separate base_ptr?

While being at it I'd much prefer to replace offset with start & end.
The buffer content is buffer[start] ... buffer[end-1] then.

We can allow the buffer to wrap around, i.e. end < start.  Buffer
content is buf[start] ... buffer[size-1] and buffer[0] .. buffer[end-1]
then.  Makes the buffer management a bit more complicated, but we never
have to memmove then (except when changing buffer size) and the
WASTED_SIZE logic isn't needed too ...

cheers,
  Gerd

Re: [Qemu-devel] [PATCH 2/2] io/buffer: avoid memmove at each qio_buffer_advance

[Peter Lieven]

Am 03.11.2015 um 11:52 schrieb Gerd Hoffmann:
>> diff --git a/include/io/buffer.h b/include/io/buffer.h
>> index f63869e..43688cc 100644
>> --- a/include/io/buffer.h
>> +++ b/include/io/buffer.h
>> @@ -39,6 +39,8 @@ struct QIOBuffer {
>>       size_t offset;
>>       uint64_t avg_size;
>>       uint8_t *buffer;
>> +    size_t base_offs;
>> +    uint8_t *base_ptr;
> Why a separate base_ptr?
>
> While being at it I'd much prefer to replace offset with start & end.
> The buffer content is buffer[start] ... buffer[end-1] then.
>
> We can allow the buffer to wrap around, i.e. end < start.  Buffer
> content is buf[start] ... buffer[size-1] and buffer[0] .. buffer[end-1]
> then.  Makes the buffer management a bit more complicated, but we never
> have to memmove then (except when changing buffer size) and the
> WASTED_SIZE logic isn't needed too ...

Then drop this patch and try to use your approach for 2.6+

Peter

Re: [Qemu-devel] [PATCH 2/2] io/buffer: avoid memmove at each qio_buffer_advance

[Markus Armbruster]

Peter Lieven <pl@kamp.de> writes:

> memmove isn't exactly cheap at it involves temporary buffers
> if the memory areas are overlapping.

Really?  The memmove() I've seen detect whether to copy forward or
backward.  None of them copies through a bounce buffer.

Avoiding it can be worthwhile regardless.

>                                      So make qio_buffer_advance
> basically a pointer adjustment, but still keep the wasted memory
> in reasonable limits.