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.1 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/host-utils.h"
  23 #include "qemu/buffer.h"
  24 #include "trace.h"
  25
  26 #define BUFFER_MIN_INIT_SIZE     4096
  27 #define BUFFER_MIN_SHRINK_SIZE  65536
  28
  29 /* define the factor alpha for the exponential smoothing
  30  * that is used in the average size calculation. a shift
  31  * of 7 results in an alpha of 1/2^7. */
  32 #define BUFFER_AVG_SIZE_SHIFT       7
  33
  34 static size_t buffer_req_size(Buffer *buffer, size_t len)
  35 {
  36     return MAX(BUFFER_MIN_INIT_SIZE,
  37                pow2ceil(buffer->offset + len));
  38 }
  39
  40 static void buffer_adj_size(Buffer *buffer, size_t len)
  41 {
  42     size_t old = buffer->capacity;
  43     buffer->capacity = buffer_req_size(buffer, len);
  44     buffer->buffer = g_realloc(buffer->buffer, buffer->capacity);
  45     trace_buffer_resize(buffer->name ?: "unnamed",
  46                         old, buffer->capacity);
  47
  48     /* make it even harder for the buffer to shrink, reset average size
  49      * to current capacity if it is larger than the average. */
  50     buffer->avg_size = MAX(buffer->avg_size,
  51                            buffer->capacity << BUFFER_AVG_SIZE_SHIFT);
  52 }
  53
  54 void buffer_init(Buffer *buffer, const char *name, ...)
  55 {
  56     va_list ap;
  57
  58     va_start(ap, name);
  59     buffer->name = g_strdup_vprintf(name, ap);
  60     va_end(ap);
  61 }
  62
  63 static uint64_t buffer_get_avg_size(Buffer *buffer)
  64 {
  65     return buffer->avg_size >> BUFFER_AVG_SIZE_SHIFT;
  66 }
  67
  68 void buffer_shrink(Buffer *buffer)
  69 {
  70     size_t new;
  71
  72     /* Calculate the average size of the buffer as
  73      * avg_size = avg_size * ( 1 - a ) + required_size * a
  74      * where a is 1 / 2 ^ BUFFER_AVG_SIZE_SHIFT. */
  75     buffer->avg_size *= (1 << BUFFER_AVG_SIZE_SHIFT) - 1;
  76     buffer->avg_size >>= BUFFER_AVG_SIZE_SHIFT;
  77     buffer->avg_size += buffer_req_size(buffer, 0);
  78
  79     /* And then only shrink if the average size of the buffer is much
  80      * too big, to avoid bumping up & down the buffers all the time.
  81      * realloc() isn't exactly cheap ...  */
  82     new = buffer_req_size(buffer, buffer_get_avg_size(buffer));
  83     if (new < buffer->capacity >> 3 &&
  84         new >= BUFFER_MIN_SHRINK_SIZE) {
  85         buffer_adj_size(buffer, buffer_get_avg_size(buffer));
  86     }
  87
  88     buffer_adj_size(buffer, 0);
  89 }
  90
  91 void buffer_reserve(Buffer *buffer, size_t len)
  92 {
  93     if ((buffer->capacity - buffer->offset) < len) {
  94         buffer_adj_size(buffer, len);
  95     }
  96 }
  97
  98 gboolean buffer_empty(Buffer *buffer)
  99 {
 100     return buffer->offset == 0;
 101 }
 102
 103 uint8_t *buffer_end(Buffer *buffer)
 104 {
 105     return buffer->buffer + buffer->offset;
 106 }
 107
 108 void buffer_reset(Buffer *buffer)
 109 {
 110     buffer->offset = 0;
 111     buffer_shrink(buffer);
 112 }
 113
 114 void buffer_free(Buffer *buffer)
 115 {
 116     trace_buffer_free(buffer->name ?: "unnamed", buffer->capacity);
 117     g_free(buffer->buffer);
 118     g_free(buffer->name);
 119     buffer->offset = 0;
 120     buffer->capacity = 0;
 121     buffer->buffer = NULL;
 122     buffer->name = NULL;
 123 }
 124
 125 void buffer_append(Buffer *buffer, const void *data, size_t len)
 126 {
 127     memcpy(buffer->buffer + buffer->offset, data, len);
 128     buffer->offset += len;
 129 }
 130
 131 void buffer_advance(Buffer *buffer, size_t len)
 132 {
 133     memmove(buffer->buffer, buffer->buffer + len,
 134             (buffer->offset - len));
 135     buffer->offset -= len;
 136     buffer_shrink(buffer);
 137 }
 138
 139 void buffer_move_empty(Buffer *to, Buffer *from)
 140 {
 141     trace_buffer_move_empty(to->name ?: "unnamed",
 142                             from->offset,
 143                             from->name ?: "unnamed");
 144     assert(to->offset == 0);
 145
 146     g_free(to->buffer);
 147     to->offset = from->offset;
 148     to->capacity = from->capacity;
 149     to->buffer = from->buffer;
 150
 151     from->offset = 0;
 152     from->capacity = 0;
 153     from->buffer = NULL;
 154 }
 155
 156 void buffer_move(Buffer *to, Buffer *from)
 157 {
 158     if (to->offset == 0) {
 159         buffer_move_empty(to, from);
 160         return;
 161     }
 162
 163     trace_buffer_move(to->name ?: "unnamed",
 164                       from->offset,
 165                       from->name ?: "unnamed");
 166     buffer_reserve(to, from->offset);
 167     buffer_append(to, from->buffer, from->offset);
 168
 169     g_free(from->buffer);
 170     from->offset = 0;
 171     from->capacity = 0;
 172     from->buffer = NULL;
 173 }