lib/gnutls_mbuffers.c

   1 /*
   2  * Copyright (C) 2009-2012 Free Software Foundation, Inc.
   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 3 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 License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  20  *
  21  */
  22
  23 #include "gnutls_mbuffers.h"
  24 #include "gnutls_errors.h"
  25
  26 /* Here be mbuffers */
  27
  28 /* A note on terminology:
  29  *
  30  * Variables named bufel designate a single buffer segment (mbuffer_st
  31  * type). This type is textually referred to as a "segment" or a
  32  * "buffer element".
  33  *
  34  * Variables named buf desigate a chain of buffer segments
  35  * (mbuffer_head_st type).  This type is textually referred to as a
  36  * "buffer head" or simply as "buffer".
  37  *
  38  * Design objectives:
  39  *
  40  * - Make existing code easier to understand.
  41  * - Make common operations more efficient by avoiding unnecessary
  42  *    copying.
  43  * - Provide a common datatype with a well-known interface to move
  44  *    data around and through the multiple protocol layers.
  45  * - Enable a future implementation of DTLS, which needs the concept
  46  *    of record boundaries.
  47  */
  48
  49
  50 /* Initialize a buffer head.
  51  *
  52  * Cost: O(1)
  53  */
  54 void
  55 _mbuffer_head_init (mbuffer_head_st * buf)
  56 {
  57   buf->head = NULL;
  58   buf->tail = NULL;
  59
  60   buf->length = 0;
  61   buf->byte_length = 0;
  62 }
  63
  64 /* Deallocate all buffer segments and reset the buffer head.
  65  *
  66  * Cost: O(n)
  67  * n: Number of segments currently in the buffer.
  68  */
  69 void
  70 _mbuffer_head_clear (mbuffer_head_st * buf)
  71 {
  72   mbuffer_st *bufel, *next;
  73
  74   for (bufel = buf->head; bufel != NULL; bufel = next)
  75     {
  76       next = bufel->next;
  77       gnutls_free (bufel);
  78     }
  79
  80   _mbuffer_head_init (buf);
  81 }
  82
  83 /* Append a segment to the end of this buffer.
  84  *
  85  * Cost: O(1)
  86  */
  87 void
  88 _mbuffer_enqueue (mbuffer_head_st * buf, mbuffer_st * bufel)
  89 {
  90   bufel->next = NULL;
  91   bufel->prev = buf->tail;
  92
  93   buf->length++;
  94   buf->byte_length += bufel->msg.size - bufel->mark;
  95
  96   if (buf->tail != NULL)
  97     buf->tail->next = bufel;
  98   else
  99     buf->head = bufel;
 100   buf->tail = bufel;
 101 }
 102
 103 /* Remove a segment from the buffer.
 104  *
 105  * Cost: O(1)
 106  *
 107  * Returns the buffer following it.
 108  */
 109 mbuffer_st *
 110 _mbuffer_dequeue (mbuffer_head_st * buf, mbuffer_st * bufel)
 111 {
 112 mbuffer_st* ret = bufel->next;
 113
 114   if (buf->tail == bufel) /* if last */
 115     buf->tail = bufel->prev;
 116
 117   if (buf->head == bufel) /* if first */
 118     buf->head = bufel->next;
 119
 120   if (bufel->prev)
 121     bufel->prev->next = bufel->next;
 122
 123   if (bufel->next)
 124     bufel->next->prev = NULL;
 125
 126   buf->length--;
 127   buf->byte_length -= bufel->msg.size - bufel->mark;
 128
 129   bufel->next = bufel->prev = NULL;
 130
 131   return ret;
 132 }
 133
 134 /* Get a reference to the first segment of the buffer and
 135  * remove it from the list.
 136  *
 137  * Used to start iteration.
 138  *
 139  * Cost: O(1)
 140  */
 141 mbuffer_st *
 142 _mbuffer_head_pop_first (mbuffer_head_st * buf)
 143 {
 144   mbuffer_st *bufel = buf->head;
 145
 146   if (buf->head == NULL)
 147     return NULL;
 148
 149   _mbuffer_dequeue(buf, bufel);
 150
 151   return bufel;
 152 }
 153
 154 /* Get a reference to the first segment of the buffer and its data.
 155  *
 156  * Used to start iteration or to peek at the data.
 157  *
 158  * Cost: O(1)
 159  */
 160 mbuffer_st *
 161 _mbuffer_head_get_first (mbuffer_head_st * buf, gnutls_datum_t * msg)
 162 {
 163   mbuffer_st *bufel = buf->head;
 164
 165   if (msg)
 166     {
 167       if (bufel)
 168         {
 169           msg->data = bufel->msg.data + bufel->mark;
 170           msg->size = bufel->msg.size - bufel->mark;
 171       }
 172     else
 173       {
 174         msg->data = NULL;
 175         msg->size = 0;
 176       }
 177     }
 178   return bufel;
 179 }
 180
 181 /* Get a reference to the next segment of the buffer and its data.
 182  *
 183  * Used to iterate over the buffer segments.
 184  *
 185  * Cost: O(1)
 186  */
 187 mbuffer_st *
 188 _mbuffer_head_get_next (mbuffer_st * cur, gnutls_datum_t * msg)
 189 {
 190   mbuffer_st *bufel = cur->next;
 191
 192   if (msg)
 193     {
 194       if (bufel)
 195         {
 196           msg->data = bufel->msg.data + bufel->mark;
 197           msg->size = bufel->msg.size - bufel->mark;
 198         }
 199       else
 200         {
 201           msg->data = NULL;
 202           msg->size = 0;
 203         }
 204     }
 205   return bufel;
 206 }
 207
 208 /* Remove the first segment from the buffer.
 209  *
 210  * Used to dequeue data from the buffer. Not yet exposed in the
 211  * internal interface since it is not yet needed outside of this unit.
 212  *
 213  * Cost: O(1)
 214  */
 215 static inline void
 216 remove_front (mbuffer_head_st * buf)
 217 {
 218   mbuffer_st *bufel = buf->head;
 219
 220   if (!bufel)
 221     return;
 222
 223   _mbuffer_dequeue(buf, bufel);
 224   gnutls_free (bufel);
 225 }
 226
 227 /* Remove a specified number of bytes from the start of the buffer.
 228  *
 229  * Useful for uses that treat the buffer as a simple array of bytes.
 230  *
 231  * If more than one mbuffer_st have been removed it
 232  * returns 1, 0 otherwise and an error code on error.
 233  *
 234  * Cost: O(n)
 235  * n: Number of segments needed to remove the specified amount of data.
 236  */
 237 int
 238 _mbuffer_head_remove_bytes (mbuffer_head_st * buf, size_t bytes)
 239 {
 240   size_t left = bytes;
 241   mbuffer_st *bufel, *next;
 242   int ret = 0;
 243
 244   if (bytes > buf->byte_length)
 245     {
 246       gnutls_assert ();
 247       return GNUTLS_E_INVALID_REQUEST;
 248     }
 249
 250   for (bufel = buf->head; bufel != NULL && left > 0; bufel = next)
 251     {
 252       next = bufel->next;
 253
 254       if (left >= (bufel->msg.size - bufel->mark))
 255         {
 256           left -= (bufel->msg.size - bufel->mark);
 257           remove_front (buf);
 258           ret = 1;
 259         }
 260       else
 261         {
 262           bufel->mark += left;
 263           buf->byte_length -= left;
 264           left = 0;
 265         }
 266     }
 267   return ret;
 268 }
 269
 270 /* Allocate a buffer segment. The segment is not initially "owned" by
 271  * any buffer.
 272  *
 273  * maximum_size: Amount of data that this segment can contain.
 274  * size: Amount of useful data that is contained in this
 275  *  buffer. Generally 0, but this is a shortcut when a fixed amount of
 276  *  data will immediately be added to this segment.
 277  *
 278  * Returns the segment or NULL on error.
 279  *
 280  * Cost: O(1)
 281  */
 282 mbuffer_st *
 283 _mbuffer_alloc (size_t payload_size, size_t maximum_size)
 284 {
 285   mbuffer_st *st;
 286
 287   st = gnutls_calloc (1, maximum_size + sizeof (mbuffer_st));
 288   if (st == NULL)
 289     {
 290       gnutls_assert ();
 291       return NULL;
 292     }
 293
 294   /* payload points after the mbuffer_st structure */
 295   st->msg.data = (uint8_t *) st + sizeof (mbuffer_st);
 296   st->msg.size = payload_size;
 297   st->maximum_size = maximum_size;
 298
 299   return st;
 300 }
 301
 302 /* Copy data into a segment. The segment must not be part of a buffer
 303  * head when using this function.
 304  *
 305  * Bounds checking is performed by this function.
 306  *
 307  * Returns 0 on success or an error code otherwise.
 308  *
 309  * Cost: O(n)
 310  * n: number of bytes to copy
 311  */
 312 int
 313 _mbuffer_append_data (mbuffer_st * bufel, void *newdata, size_t newdata_size)
 314 {
 315   if (bufel->msg.size + newdata_size <= bufel->maximum_size)
 316     {
 317       memcpy (&bufel->msg.data[bufel->msg.size], newdata, newdata_size);
 318       bufel->msg.size += newdata_size;
 319     }
 320   else
 321     {
 322       gnutls_assert ();
 323       return GNUTLS_E_INVALID_REQUEST;
 324     }
 325
 326   return 0;
 327 }
 328
 329 /* Takes a buffer in multiple chunks and puts all the data in a single
 330  * contiguous segment.
 331  *
 332  * Returns 0 on success or an error code otherwise.
 333  *
 334  * Cost: O(n)
 335  * n: number of segments initially in the buffer
 336  */
 337 int
 338 _mbuffer_linearize (mbuffer_head_st * buf)
 339 {
 340   mbuffer_st *bufel, *cur;
 341   gnutls_datum_t msg;
 342   size_t pos = 0;
 343
 344   if (buf->length <= 1)
 345     /* Nothing to do */
 346     return 0;
 347
 348   bufel = _mbuffer_alloc (buf->byte_length, buf->byte_length);
 349   if (!bufel)
 350     {
 351       gnutls_assert ();
 352       return GNUTLS_E_MEMORY_ERROR;
 353     }
 354
 355   for (cur = _mbuffer_head_get_first (buf, &msg);
 356        msg.data != NULL; cur = _mbuffer_head_get_next (cur, &msg))
 357     {
 358       memcpy (&bufel->msg.data[pos], msg.data, msg.size);
 359       pos += msg.size;
 360     }
 361
 362   _mbuffer_head_clear (buf);
 363   _mbuffer_enqueue (buf, bufel);
 364
 365   return 0;
 366 }