util/buffer.c

   1 /*
   2  * QEMU generic buffers
   3  *
   4  * Copyright (c) 2015 Red Hat, Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  18  *
  19  */
  20
  21 #include "qemu/osdep.h"
  22 #include "qemu/buffer.h"
  23 #include "trace.h"
  24
  25 #define BUFFER_MIN_INIT_SIZE     4096
  26 #define BUFFER_MIN_SHRINK_SIZE  65536
  27
  28 /* define the factor alpha for the exponential smoothing
  29  * that is used in the average size calculation. a shift
  30  * of 7 results in an alpha of 1/2^7. */
  31 #define BUFFER_AVG_SIZE_SHIFT       7
  32
  33 static size_t buffer_req_size(Buffer *buffer, size_t len)
  34 {
  35     return MAX(BUFFER_MIN_INIT_SIZE,
  36                pow2ceil(buffer->offset + len));
  37 }
  38
  39 static void buffer_adj_size(Buffer *buffer, size_t len)
  40 {
  41     size_t old = buffer->capacity;
  42     buffer->capacity = buffer_req_size(buffer, len);
  43     buffer->buffer = g_realloc(buffer->buffer, buffer->capacity);
  44     trace_buffer_resize(buffer->name ?: "unnamed",
  45                         old, buffer->capacity);
  46
  47     /* make it even harder for the buffer to shrink, reset average size
  48      * to current capacity if it is larger than the average. */
  49     buffer->avg_size = MAX(buffer->avg_size,
  50                            buffer->capacity << BUFFER_AVG_SIZE_SHIFT);
  51 }
  52
  53 void buffer_init(Buffer *buffer, const char *name, ...)
  54 {
  55     va_list ap;
  56
  57     va_start(ap, name);
  58     buffer->name = g_strdup_vprintf(name, ap);
  59     va_end(ap);
  60 }
  61
  62 static uint64_t buffer_get_avg_size(Buffer *buffer)
  63 {
  64     return buffer->avg_size >> BUFFER_AVG_SIZE_SHIFT;
  65 }
  66
  67 void buffer_shrink(Buffer *buffer)
  68 {
  69     size_t new;
  70
  71     /* Calculate the average size of the buffer as
  72      * avg_size = avg_size * ( 1 - a ) + required_size * a
  73      * where a is 1 / 2 ^ BUFFER_AVG_SIZE_SHIFT. */
  74     buffer->avg_size *= (1 << BUFFER_AVG_SIZE_SHIFT) - 1;
  75     buffer->avg_size >>= BUFFER_AVG_SIZE_SHIFT;
  76     buffer->avg_size += buffer_req_size(buffer, 0);
  77
  78     /* And then only shrink if the average size of the buffer is much
  79      * too big, to avoid bumping up & down the buffers all the time.
  80      * realloc() isn't exactly cheap ...  */
  81     new = buffer_req_size(buffer, buffer_get_avg_size(buffer));
  82     if (new < buffer->capacity >> 3 &&
  83         new >= BUFFER_MIN_SHRINK_SIZE) {
  84         buffer_adj_size(buffer, buffer_get_avg_size(buffer));
  85     }
  86
  87     buffer_adj_size(buffer, 0);
  88 }
  89
  90 void buffer_reserve(Buffer *buffer, size_t len)
  91 {
  92     if ((buffer->capacity - buffer->offset) < len) {
  93         buffer_adj_size(buffer, len);
  94     }
  95 }
  96
  97 gboolean buffer_empty(Buffer *buffer)
  98 {
  99     return buffer->offset == 0;
 100 }
 101
 102 uint8_t *buffer_end(Buffer *buffer)
 103 {
 104     return buffer->buffer + buffer->offset;
 105 }
 106
 107 void buffer_reset(Buffer *buffer)
 108 {
 109     buffer->offset = 0;
 110     buffer_shrink(buffer);
 111 }
 112
 113 void buffer_free(Buffer *buffer)
 114 {
 115     trace_buffer_free(buffer->name ?: "unnamed", buffer->capacity);
 116     g_free(buffer->buffer);
 117     g_free(buffer->name);
 118     buffer->offset = 0;
 119     buffer->capacity = 0;
 120     buffer->buffer = NULL;
 121     buffer->name = NULL;
 122 }
 123
 124 void buffer_append(Buffer *buffer, const void *data, size_t len)
 125 {
 126     memcpy(buffer->buffer + buffer->offset, data, len);
 127     buffer->offset += len;
 128 }
 129
 130 void buffer_advance(Buffer *buffer, size_t len)
 131 {
 132     memmove(buffer->buffer, buffer->buffer + len,
 133             (buffer->offset - len));
 134     buffer->offset -= len;
 135     buffer_shrink(buffer);
 136 }
 137
 138 void buffer_move_empty(Buffer *to, Buffer *from)
 139 {
 140     trace_buffer_move_empty(to->name ?: "unnamed",
 141                             from->offset,
 142                             from->name ?: "unnamed");
 143     assert(to->offset == 0);
 144
 145     g_free(to->buffer);
 146     to->offset = from->offset;
 147     to->capacity = from->capacity;
 148     to->buffer = from->buffer;
 149
 150     from->offset = 0;
 151     from->capacity = 0;
 152     from->buffer = NULL;
 153 }
 154
 155 void buffer_move(Buffer *to, Buffer *from)
 156 {
 157     if (to->offset == 0) {
 158         buffer_move_empty(to, from);
 159         return;
 160     }
 161
 162     trace_buffer_move(to->name ?: "unnamed",
 163                       from->offset,
 164                       from->name ?: "unnamed");
 165     buffer_reserve(to, from->offset);
 166     buffer_append(to, from->buffer, from->offset);
 167
 168     g_free(from->buffer);
 169     from->offset = 0;
 170     from->capacity = 0;
 171     from->buffer = NULL;
 172 }