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