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 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 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 _mbuffer_head_init(mbuffer_head_st * buf)
  55 {
  56         buf->head = NULL;
  57         buf->tail = NULL;
  58
  59         buf->length = 0;
  60         buf->byte_length = 0;
  61 }
  62
  63 /* Deallocate all buffer segments and reset the buffer head.
  64  *
  65  * Cost: O(n)
  66  * n: Number of segments currently in the buffer.
  67  */
  68 void _mbuffer_head_clear(mbuffer_head_st * buf)
  69 {
  70         mbuffer_st *bufel, *next;
  71
  72         for (bufel = buf->head; bufel != NULL; bufel = next) {
  73                 next = bufel->next;
  74                 gnutls_free(bufel);
  75         }
  76
  77         _mbuffer_head_init(buf);
  78 }
  79
  80 /* Append a segment to the end of this buffer.
  81  *
  82  * Cost: O(1)
  83  */
  84 void _mbuffer_enqueue(mbuffer_head_st * buf, mbuffer_st * bufel)
  85 {
  86         bufel->next = NULL;
  87         bufel->prev = buf->tail;
  88
  89         buf->length++;
  90         buf->byte_length += bufel->msg.size - bufel->mark;
  91
  92         if (buf->tail != NULL)
  93                 buf->tail->next = bufel;
  94         else
  95                 buf->head = bufel;
  96         buf->tail = bufel;
  97 }
  98
  99 /* Remove a segment from the buffer.
 100  *
 101  * Cost: O(1)
 102  *
 103  * Returns the buffer following it.
 104  */
 105 mbuffer_st *_mbuffer_dequeue(mbuffer_head_st * buf, mbuffer_st * bufel)
 106 {
 107         mbuffer_st *ret = bufel->next;
 108
 109         if (buf->tail == bufel) /* if last */
 110                 buf->tail = bufel->prev;
 111
 112         if (buf->head == bufel) /* if first */
 113                 buf->head = bufel->next;
 114
 115         if (bufel->prev)
 116                 bufel->prev->next = bufel->next;
 117
 118         if (bufel->next)
 119                 bufel->next->prev = NULL;
 120
 121         buf->length--;
 122         buf->byte_length -= bufel->msg.size - bufel->mark;
 123
 124         bufel->next = bufel->prev = NULL;
 125
 126         return ret;
 127 }
 128
 129 /* Get a reference to the first segment of the buffer and
 130  * remove it from the list.
 131  *
 132  * Used to start iteration.
 133  *
 134  * Cost: O(1)
 135  */
 136 mbuffer_st *_mbuffer_head_pop_first(mbuffer_head_st * buf)
 137 {
 138         mbuffer_st *bufel = buf->head;
 139
 140         if (buf->head == NULL)
 141                 return NULL;
 142
 143         _mbuffer_dequeue(buf, bufel);
 144
 145         return bufel;
 146 }
 147
 148 /* Get a reference to the first segment of the buffer and its data.
 149  *
 150  * Used to start iteration or to peek at the data.
 151  *
 152  * Cost: O(1)
 153  */
 154 mbuffer_st *_mbuffer_head_get_first(mbuffer_head_st * buf,
 155                                     gnutls_datum_t * msg)
 156 {
 157         mbuffer_st *bufel = buf->head;
 158
 159         if (msg) {
 160                 if (bufel) {
 161                         msg->data = bufel->msg.data + bufel->mark;
 162                         msg->size = bufel->msg.size - bufel->mark;
 163                 } else {
 164                         msg->data = NULL;
 165                         msg->size = 0;
 166                 }
 167         }
 168         return bufel;
 169 }
 170
 171 /* Get a reference to the next segment of the buffer and its data.
 172  *
 173  * Used to iterate over the buffer segments.
 174  *
 175  * Cost: O(1)
 176  */
 177 mbuffer_st *_mbuffer_head_get_next(mbuffer_st * cur, gnutls_datum_t * msg)
 178 {
 179         mbuffer_st *bufel = cur->next;
 180
 181         if (msg) {
 182                 if (bufel) {
 183                         msg->data = bufel->msg.data + bufel->mark;
 184                         msg->size = bufel->msg.size - bufel->mark;
 185                 } else {
 186                         msg->data = NULL;
 187                         msg->size = 0;
 188                 }
 189         }
 190         return bufel;
 191 }
 192
 193 /* Remove the first segment from the buffer.
 194  *
 195  * Used to dequeue data from the buffer. Not yet exposed in the
 196  * internal interface since it is not yet needed outside of this unit.
 197  *
 198  * Cost: O(1)
 199  */
 200 static inline void remove_front(mbuffer_head_st * buf)
 201 {
 202         mbuffer_st *bufel = buf->head;
 203
 204         if (!bufel)
 205                 return;
 206
 207         _mbuffer_dequeue(buf, bufel);
 208         gnutls_free(bufel);
 209 }
 210
 211 /* Remove a specified number of bytes from the start of the buffer.
 212  *
 213  * Useful for uses that treat the buffer as a simple array of bytes.
 214  *
 215  * If more than one mbuffer_st have been removed it
 216  * returns 1, 0 otherwise and an error code on error.
 217  *
 218  * Cost: O(n)
 219  * n: Number of segments needed to remove the specified amount of data.
 220  */
 221 int _mbuffer_head_remove_bytes(mbuffer_head_st * buf, size_t bytes)
 222 {
 223         size_t left = bytes;
 224         mbuffer_st *bufel, *next;
 225         int ret = 0;
 226
 227         if (bytes > buf->byte_length) {
 228                 gnutls_assert();
 229                 return GNUTLS_E_INVALID_REQUEST;
 230         }
 231
 232         for (bufel = buf->head; bufel != NULL && left > 0; bufel = next) {
 233                 next = bufel->next;
 234
 235                 if (left >= (bufel->msg.size - bufel->mark)) {
 236                         left -= (bufel->msg.size - bufel->mark);
 237                         remove_front(buf);
 238                         ret = 1;
 239                 } else {
 240                         bufel->mark += left;
 241                         buf->byte_length -= left;
 242                         left = 0;
 243                 }
 244         }
 245         return ret;
 246 }
 247
 248 /* Allocate a buffer segment. The segment is not initially "owned" by
 249  * any buffer.
 250  *
 251  * maximum_size: Amount of data that this segment can contain.
 252  *
 253  * Returns the segment or NULL on error.
 254  *
 255  * Cost: O(1)
 256  */
 257 mbuffer_st *_mbuffer_alloc(size_t maximum_size)
 258 {
 259         mbuffer_st *st;
 260
 261         st = gnutls_malloc(maximum_size + sizeof(mbuffer_st));
 262         if (st == NULL) {
 263                 gnutls_assert();
 264                 return NULL;
 265         }
 266
 267         /* set the structure to zero */
 268         memset(st, 0, sizeof(*st));
 269
 270         /* payload points after the mbuffer_st structure */
 271         st->msg.data = (uint8_t *) st + sizeof(mbuffer_st);
 272         st->msg.size = 0;
 273         st->maximum_size = maximum_size;
 274
 275         return st;
 276 }
 277
 278
 279 /* Copy data into a segment. The segment must not be part of a buffer
 280  * head when using this function.
 281  *
 282  * Bounds checking is performed by this function.
 283  *
 284  * Returns 0 on success or an error code otherwise.
 285  *
 286  * Cost: O(n)
 287  * n: number of bytes to copy
 288  */
 289 int
 290 _mbuffer_append_data(mbuffer_st * bufel, void *newdata,
 291                      size_t newdata_size)
 292 {
 293         if (bufel->msg.size + newdata_size <= bufel->maximum_size) {
 294                 memcpy(&bufel->msg.data[bufel->msg.size], newdata,
 295                        newdata_size);
 296                 bufel->msg.size += newdata_size;
 297         } else {
 298                 gnutls_assert();
 299                 return GNUTLS_E_INVALID_REQUEST;
 300         }
 301
 302         return 0;
 303 }
 304
 305 #ifdef ENABLE_ALIGN16
 306 # define ALIGN_SIZE 16
 307
 308 /* Allocate a 16-byte alligned buffer segment. The segment is not initially "owned" by
 309  * any buffer.
 310  *
 311  * maximum_size: Amount of data that this segment can contain.
 312  * align_pos: identifies the position of the buffer that will be aligned at 16-bytes
 313  *
 314  * This function should be used to ensure that encrypted data or data to
 315  * be encrypted are properly aligned.
 316  *
 317  * Returns the segment or NULL on error.
 318  *
 319  * Cost: O(1)
 320  */
 321 mbuffer_st *_mbuffer_alloc_align16(size_t maximum_size, unsigned align_pos)
 322 {
 323         mbuffer_st *st;
 324         size_t cur_alignment;
 325
 326         st = gnutls_malloc(maximum_size + sizeof(mbuffer_st) + ALIGN_SIZE);
 327         if (st == NULL) {
 328                 gnutls_assert();
 329                 return NULL;
 330         }
 331
 332         /* set the structure to zero */
 333         memset(st, 0, sizeof(*st));
 334
 335         /* payload points after the mbuffer_st structure */
 336         st->msg.data = (uint8_t *) st + sizeof(mbuffer_st);
 337
 338         cur_alignment = ((size_t)(st->msg.data+align_pos)) % ALIGN_SIZE;
 339         if (cur_alignment > 0)
 340                 st->msg.data += ALIGN_SIZE - cur_alignment;
 341
 342         st->msg.size = 0;
 343         st->maximum_size = maximum_size;
 344
 345         return st;
 346 }
 347
 348 static unsigned is_aligned16(mbuffer_st * bufel, unsigned align_pos)
 349 {
 350 uint8_t * ptr = _mbuffer_get_udata_ptr(bufel);
 351
 352         if (((size_t)(ptr+align_pos)) % ALIGN_SIZE == 0)
 353                 return 1;
 354         else
 355                 return 0;
 356 }
 357
 358 /* Takes a buffer in multiple chunks and puts all the data in a single
 359  * contiguous segment, ensuring that the @align_pos is 16-byte aligned.
 360  *
 361  * Returns 0 on success or an error code otherwise.
 362  *
 363  * Cost: O(n)
 364  * n: number of segments initially in the buffer
 365  */
 366 int _mbuffer_linearize_align16(mbuffer_head_st * buf, unsigned align_pos)
 367 {
 368         mbuffer_st *bufel, *cur;
 369         gnutls_datum_t msg;
 370         size_t pos = 0;
 371
 372         if (buf->length == 0) {
 373                 /* Nothing to do */
 374                 return 0;
 375         }
 376
 377         bufel = _mbuffer_head_get_first(buf, NULL);
 378         if (buf->length == 1 && is_aligned16(bufel, align_pos))
 379                 return 0;
 380
 381         bufel = _mbuffer_alloc_align16(buf->byte_length, align_pos);
 382         if (!bufel) {
 383                 gnutls_assert();
 384                 return GNUTLS_E_MEMORY_ERROR;
 385         }
 386
 387         for (cur = _mbuffer_head_get_first(buf, &msg);
 388              msg.data != NULL; cur = _mbuffer_head_get_next(cur, &msg)) {
 389                 memcpy(&bufel->msg.data[pos], msg.data, msg.size);
 390                 bufel->msg.size += msg.size;
 391                 pos += msg.size;
 392         }
 393
 394         _mbuffer_head_clear(buf);
 395         _mbuffer_enqueue(buf, bufel);
 396
 397         return 0;
 398 }
 399 #else
 400 int _mbuffer_linearize(mbuffer_head_st * buf)
 401 {
 402         mbuffer_st *bufel, *cur;
 403         gnutls_datum_t msg;
 404         size_t pos = 0;
 405
 406         if (buf->length <= 1) {
 407                 /* Nothing to do */
 408                 return 0;
 409         }
 410
 411         bufel = _mbuffer_alloc(buf->byte_length);
 412         if (!bufel) {
 413                 gnutls_assert();
 414                 return GNUTLS_E_MEMORY_ERROR;
 415         }
 416
 417         for (cur = _mbuffer_head_get_first(buf, &msg);
 418              msg.data != NULL; cur = _mbuffer_head_get_next(cur, &msg)) {
 419                 memcpy(&bufel->msg.data[pos], msg.data, msg.size);
 420                 bufel->msg.size += msg.size;
 421                 pos += msg.size;
 422         }
 423
 424         _mbuffer_head_clear(buf);
 425         _mbuffer_enqueue(buf, bufel);
 426
 427         return 0;
 428 }
 429 #endif