Adds multiple checks to avoid buffer over reads
[openssl.git] / ssl / pqueue.c
1 /*
2  * Copyright 2005-2017 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include "ssl_locl.h"
11 #include <openssl/bn.h>
12
13 struct pqueue_st {
14     pitem *items;
15     int count;
16 };
17
18 pitem *pitem_new(unsigned char *prio64be, void *data)
19 {
20     pitem *item = OPENSSL_malloc(sizeof(*item));
21     if (item == NULL)
22         return NULL;
23
24     memcpy(item->priority, prio64be, sizeof(item->priority));
25
26     item->data = data;
27     item->next = NULL;
28
29     return item;
30 }
31
32 void pitem_free(pitem *item)
33 {
34     OPENSSL_free(item);
35 }
36
37 pqueue *pqueue_new()
38 {
39     pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
40
41     return pq;
42 }
43
44 void pqueue_free(pqueue *pq)
45 {
46     OPENSSL_free(pq);
47 }
48
49 pitem *pqueue_insert(pqueue *pq, pitem *item)
50 {
51     pitem *curr, *next;
52
53     if (pq->items == NULL) {
54         pq->items = item;
55         return item;
56     }
57
58     for (curr = NULL, next = pq->items;
59          next != NULL; curr = next, next = next->next) {
60         /*
61          * we can compare 64-bit value in big-endian encoding with memcmp:-)
62          */
63         int cmp = memcmp(next->priority, item->priority, 8);
64         if (cmp > 0) {          /* next > item */
65             item->next = next;
66
67             if (curr == NULL)
68                 pq->items = item;
69             else
70                 curr->next = item;
71
72             return item;
73         }
74
75         else if (cmp == 0)      /* duplicates not allowed */
76             return NULL;
77     }
78
79     item->next = NULL;
80     curr->next = item;
81
82     return item;
83 }
84
85 pitem *pqueue_peek(pqueue *pq)
86 {
87     return pq->items;
88 }
89
90 pitem *pqueue_pop(pqueue *pq)
91 {
92     pitem *item = pq->items;
93
94     if (pq->items != NULL)
95         pq->items = pq->items->next;
96
97     return item;
98 }
99
100 pitem *pqueue_find(pqueue *pq, unsigned char *prio64be)
101 {
102     pitem *next;
103     pitem *found = NULL;
104
105     if (pq->items == NULL)
106         return NULL;
107
108     for (next = pq->items; next->next != NULL; next = next->next) {
109         if (memcmp(next->priority, prio64be, 8) == 0) {
110             found = next;
111             break;
112         }
113     }
114
115     /* check the one last node */
116     if (memcmp(next->priority, prio64be, 8) == 0)
117         found = next;
118
119     if (!found)
120         return NULL;
121
122     return found;
123 }
124
125 pitem *pqueue_iterator(pqueue *pq)
126 {
127     return pqueue_peek(pq);
128 }
129
130 pitem *pqueue_next(piterator *item)
131 {
132     pitem *ret;
133
134     if (item == NULL || *item == NULL)
135         return NULL;
136
137     /* *item != NULL */
138     ret = *item;
139     *item = (*item)->next;
140
141     return ret;
142 }
143
144 size_t pqueue_size(pqueue *pq)
145 {
146     pitem *item = pq->items;
147     size_t count = 0;
148
149     while (item != NULL) {
150         count++;
151         item = item->next;
152     }
153     return count;
154 }