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