lib/gnutls_mbuffers.c

   1 /*
   2  * Copyright (C) 2009 Free Software Foundation
   3  *
   4  * Author: Jonathan Bastien-Filiatrault
   5  *
   6  * This file is part of GNUTLS.
   7  *
   8  * The GNUTLS library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation; either version 2.1 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  21  * USA
  22  *
  23  */
  24
  25 #include "gnutls_mbuffers.h"
  26 #include "gnutls_errors.h"
  27
  28 /* Here be mbuffers */
  29
  30 /* A note on terminology:
  31  *
  32  * Variables named bufel designate a single buffer segment (mbuffer_st
  33  * type). This type is textually referred to as a "segment" or a
  34  * "buffer element".
  35  *
  36  * Variables named buf desigate a chain of buffer segments
  37  * (mbuffer_head_st type).  This type is textually referred to as a
  38  * "buffer head" or simply as "buffer".
  39  *
  40  * Design objectives:
  41  *
  42  * - Make existing code easier to understand.
  43  * - Make common operations more efficient by avoiding unnecessary
  44  *    copying.
  45  * - Provide a common datatype with a well-known interface to move
  46  *    data around and through the multiple protocol layers.
  47  * - Enable a future implementation of DTLS, which needs the concept
  48  *    of record boundaries.
  49  */
  50
  51
  52 /* Initialize a buffer head.
  53  *
  54  * Cost: O(1)
  55  */
  56 void
  57 _mbuffer_init (mbuffer_head_st * buf)
  58 {
  59   buf->head = NULL;
  60   buf->tail = &buf->head;
  61
  62   buf->length = 0;
  63   buf->byte_length = 0;
  64 }
  65
  66 /* Deallocate all buffer segments and reset the buffer head.
  67  *
  68  * Cost: O(n)
  69  * n: Number of segments currently in the buffer.
  70  */
  71 void
  72 _mbuffer_clear (mbuffer_head_st * buf)
  73 {
  74   mbuffer_st *bufel, *next;
  75
  76   for (bufel = buf->head; bufel != NULL; bufel = next)
  77     {
  78       next = bufel->next;
  79       gnutls_free (bufel);
  80     }
  81
  82   _mbuffer_init (buf);
  83 }
  84
  85 /* Append a segment to the end of this buffer.
  86  *
  87  * Cost: O(1)
  88  */
  89 void
  90 _mbuffer_enqueue (mbuffer_head_st * buf, mbuffer_st * bufel)
  91 {
  92   bufel->next = NULL;
  93
  94   buf->length++;
  95   buf->byte_length += bufel->msg.size - bufel->mark;
  96
  97   *(buf->tail) = bufel;
  98   buf->tail = &bufel->next;
  99 }
 100
 101 /* Get a reference to the first segment of the buffer and its data.
 102  *
 103  * Used to start iteration or to peek at the data.
 104  *
 105  * Cost: O(1)
 106  */
 107 mbuffer_st *
 108 _mbuffer_get_first (mbuffer_head_st * buf, gnutls_datum_t * msg)
 109 {
 110   mbuffer_st *bufel = buf->head;
 111
 112   if (bufel)
 113     {
 114       msg->data = bufel->msg.data + bufel->mark;
 115       msg->size = bufel->msg.size - bufel->mark;
 116     }
 117   else
 118     {
 119       msg->data = NULL;
 120       msg->size = 0;
 121     }
 122   return bufel;
 123 }
 124
 125 /* Get a reference to the next segment of the buffer and its data.
 126  *
 127  * Used to iterate over the buffer segments.
 128  *
 129  * Cost: O(1)
 130  */
 131 mbuffer_st *
 132 _mbuffer_get_next (mbuffer_st * cur, gnutls_datum_t * msg)
 133 {
 134   mbuffer_st *bufel = cur->next;
 135
 136   if (bufel)
 137     {
 138       msg->data = bufel->msg.data + bufel->mark;
 139       msg->size = bufel->msg.size - bufel->mark;
 140     }
 141   else
 142     {
 143       msg->data = NULL;
 144       msg->size = 0;
 145     }
 146   return bufel;
 147 }
 148
 149 /* Remove the first segment from the buffer.
 150  *
 151  * Used to dequeue data from the buffer. Not yet exposed in the
 152  * internal interface since it is not yet needed outside of this unit.
 153  *
 154  * Cost: O(1)
 155  */
 156 static inline void
 157 remove_front (mbuffer_head_st * buf)
 158 {
 159   mbuffer_st *bufel;
 160
 161   if (!buf->head)
 162     return;
 163
 164   bufel = buf->head;
 165   buf->head = bufel->next;
 166
 167   buf->byte_length -= (bufel->msg.size - bufel->mark);
 168   buf->length -= 1;
 169   gnutls_free (bufel);
 170
 171   if (!buf->head)
 172     buf->tail = &buf->head;
 173 }
 174
 175 /* Remove a specified number of bytes from the start of the buffer.
 176  *
 177  * Useful for uses that treat the buffer as a simple array of bytes.
 178  *
 179  * Returns 0 on success or an error code otherwise.
 180  *
 181  * Cost: O(n)
 182  * n: Number of segments needed to remove the specified amount of data.
 183  */
 184 int
 185 _mbuffer_remove_bytes (mbuffer_head_st * buf, size_t bytes)
 186 {
 187   size_t left = bytes;
 188   mbuffer_st *bufel, *next;
 189
 190   if (bytes > buf->byte_length)
 191     {
 192       gnutls_assert ();
 193       return GNUTLS_E_INVALID_REQUEST;
 194     }
 195
 196   for (bufel = buf->head; bufel != NULL && left > 0; bufel = next)
 197     {
 198       next = bufel->next;
 199
 200       if (left >= (bufel->msg.size - bufel->mark))
 201         {
 202           left -= (bufel->msg.size - bufel->mark);
 203           remove_front (buf);
 204         }
 205       else
 206         {
 207           bufel->mark += left;
 208           buf->byte_length -= left;
 209           left = 0;
 210         }
 211     }
 212
 213   return 0;
 214 }
 215
 216 /* Allocate a buffer segment. The segment is not initially "owned" by
 217  * any buffer.
 218  *
 219  * maximum_size: Amount of data that this segment can contain.
 220  * size: Amount of useful data that is contained in this
 221  *  buffer. Generally 0, but this is a shortcut when a fixed amount of
 222  *  data will immediately be added to this segment.
 223  *
 224  * Returns the segment or NULL on error.
 225  *
 226  * Cost: O(1)
 227  */
 228 mbuffer_st *
 229 _mbuffer_alloc (size_t payload_size, size_t maximum_size)
 230 {
 231   mbuffer_st *st;
 232
 233   st = gnutls_malloc (maximum_size + sizeof (mbuffer_st));
 234   if (st == NULL)
 235     {
 236       gnutls_assert ();
 237       return NULL;
 238     }
 239
 240   //payload points after the mbuffer_st structure
 241   st->msg.data = (opaque *) st + sizeof (mbuffer_st);
 242   st->msg.size = payload_size;
 243   st->mark = 0;
 244   st->user_mark = 0;
 245   st->next = NULL;
 246   st->maximum_size = maximum_size;
 247
 248   return st;
 249 }
 250
 251 /* Copy data into a segment. The segment must not be part of a buffer
 252  * head when using this function.
 253  *
 254  * Bounds checking is performed by this function.
 255  *
 256  * Returns 0 on success or an error code otherwise.
 257  *
 258  * Cost: O(n)
 259  * n: number of bytes to copy
 260  */
 261 int
 262 _mbuffer_append_data (mbuffer_st * bufel, void *newdata, size_t newdata_size)
 263 {
 264   if (bufel->msg.size + newdata_size <= bufel->maximum_size)
 265     {
 266       memcpy (&bufel->msg.data[bufel->msg.size], newdata, newdata_size);
 267       bufel->msg.size += newdata_size;
 268     }
 269   else
 270     {
 271       gnutls_assert ();
 272       return GNUTLS_E_INVALID_REQUEST;
 273     }
 274
 275   return 0;
 276 }
 277
 278 /* Takes a buffer in multiple chunks and puts all the data in a single
 279  * contiguous segment.
 280  *
 281  * Returns 0 on success or an error code otherwise.
 282  *
 283  * Cost: O(n)
 284  * n: number of segments initially in the buffer
 285  */
 286 int
 287 _mbuffer_linearize (mbuffer_head_st * buf)
 288 {
 289   mbuffer_st *bufel, *cur;
 290   gnutls_datum_t msg;
 291   size_t pos = 0;
 292
 293   if (buf->length <= 1)
 294     /* Nothing to do */
 295     return 0;
 296
 297   bufel = _mbuffer_alloc (buf->byte_length, buf->byte_length);
 298   if (!bufel)
 299     {
 300       gnutls_assert ();
 301       return GNUTLS_E_MEMORY_ERROR;
 302     }
 303
 304   for (cur = _mbuffer_get_first (buf, &msg);
 305        msg.data != NULL; cur = _mbuffer_get_next (cur, &msg))
 306     {
 307       memcpy (&bufel->msg.data[pos], msg.data, cur->msg.size);
 308       pos += cur->msg.size;
 309     }
 310
 311   _mbuffer_clear (buf);
 312   _mbuffer_enqueue (buf, bufel);
 313
 314   return 0;
 315 }