crypto/stack/stack.c

   1 /*
   2  * Copyright 1995-2016 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 <stdio.h>
  11 #include "internal/cryptlib.h"
  12 #include "internal/numbers.h"
  13 #include <openssl/stack.h>
  14 #include <openssl/objects.h>
  15
  16 struct stack_st {
  17     int num;
  18     const char **data;
  19     int sorted;
  20     size_t num_alloc;
  21     OPENSSL_sk_compfunc comp;
  22 };
  23
  24 #undef MIN_NODES
  25 #define MIN_NODES       4
  26
  27 #include <errno.h>
  28
  29 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
  30 {
  31     OPENSSL_sk_compfunc old = sk->comp;
  32
  33     if (sk->comp != c)
  34         sk->sorted = 0;
  35     sk->comp = c;
  36
  37     return old;
  38 }
  39
  40 OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
  41 {
  42     OPENSSL_STACK *ret;
  43
  44     if (sk->num < 0)
  45         return NULL;
  46
  47     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  48         return NULL;
  49
  50     /* direct structure assignment */
  51     *ret = *sk;
  52
  53     if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)
  54         goto err;
  55     memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
  56     return ret;
  57  err:
  58     OPENSSL_sk_free(ret);
  59     return NULL;
  60 }
  61
  62 OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
  63                              OPENSSL_sk_copyfunc copy_func,
  64                              OPENSSL_sk_freefunc free_func)
  65 {
  66     OPENSSL_STACK *ret;
  67     int i;
  68
  69     if (sk->num < 0)
  70         return NULL;
  71
  72     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  73         return NULL;
  74
  75     /* direct structure assignment */
  76     *ret = *sk;
  77
  78     ret->num_alloc = sk->num > MIN_NODES ? (size_t)sk->num : MIN_NODES;
  79     ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);
  80     if (ret->data == NULL) {
  81         OPENSSL_free(ret);
  82         return NULL;
  83     }
  84
  85     for (i = 0; i < ret->num; ++i) {
  86         if (sk->data[i] == NULL)
  87             continue;
  88         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
  89             while (--i >= 0)
  90                 if (ret->data[i] != NULL)
  91                     free_func((void *)ret->data[i]);
  92             OPENSSL_sk_free(ret);
  93             return NULL;
  94         }
  95     }
  96     return ret;
  97 }
  98
  99 OPENSSL_STACK *OPENSSL_sk_new_null(void)
 100 {
 101     return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL);
 102 }
 103
 104 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
 105 {
 106     OPENSSL_STACK *ret;
 107
 108     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
 109         goto err;
 110     if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL)
 111         goto err;
 112     ret->comp = c;
 113     ret->num_alloc = MIN_NODES;
 114     return (ret);
 115
 116  err:
 117     OPENSSL_free(ret);
 118     return (NULL);
 119 }
 120
 121 int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
 122 {
 123     if (st == NULL || st->num < 0 || st->num == INT_MAX) {
 124         return 0;
 125     }
 126
 127     if (st->num_alloc <= (size_t)(st->num + 1)) {
 128         size_t doub_num_alloc = st->num_alloc * 2;
 129
 130         /* Overflow checks */
 131         if (doub_num_alloc < st->num_alloc)
 132             return 0;
 133
 134         /* Avoid overflow due to multiplication by sizeof(char *) */
 135         if (doub_num_alloc > SIZE_MAX / sizeof(char *))
 136             return 0;
 137
 138         st->data = OPENSSL_realloc((char *)st->data,
 139                                    sizeof(char *) * doub_num_alloc);
 140         if (st->data == NULL) {
 141             /*
 142              * Reset these counters to prevent subsequent operations on
 143              * (now non-existing) heap memory
 144              */
 145             st->num_alloc = 0;
 146             st->num = 0;
 147             return 0;
 148         }
 149         st->num_alloc = doub_num_alloc;
 150     }
 151     if ((loc >= st->num) || (loc < 0)) {
 152         st->data[st->num] = data;
 153     } else {
 154         memmove(&st->data[loc + 1], &st->data[loc],
 155                 sizeof(st->data[0]) * (st->num - loc));
 156         st->data[loc] = data;
 157     }
 158     st->num++;
 159     st->sorted = 0;
 160     return st->num;
 161 }
 162
 163 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
 164 {
 165     int i;
 166
 167     for (i = 0; i < st->num; i++)
 168         if (st->data[i] == p)
 169             return OPENSSL_sk_delete(st, i);
 170     return NULL;
 171 }
 172
 173 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 174 {
 175     const char *ret;
 176
 177     if (st == NULL || loc < 0 || loc >= st->num)
 178         return NULL;
 179
 180     ret = st->data[loc];
 181     if (loc != st->num - 1)
 182          memmove(&st->data[loc], &st->data[loc + 1],
 183                  sizeof(st->data[0]) * (st->num - loc - 1));
 184     st->num--;
 185     return (void *)ret;
 186 }
 187
 188 static int internal_find(OPENSSL_STACK *st, const void *data,
 189                          int ret_val_options)
 190 {
 191     const void *r;
 192     int i;
 193
 194     if (st == NULL)
 195         return -1;
 196
 197     if (st->comp == NULL) {
 198         for (i = 0; i < st->num; i++)
 199             if (st->data[i] == data)
 200                 return (i);
 201         return (-1);
 202     }
 203     OPENSSL_sk_sort(st);
 204     if (data == NULL)
 205         return (-1);
 206     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 207                         ret_val_options);
 208     if (r == NULL)
 209         return (-1);
 210     return (int)((const char **)r - st->data);
 211 }
 212
 213 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 214 {
 215     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 216 }
 217
 218 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 219 {
 220     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 221 }
 222
 223 int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
 224 {
 225     return (OPENSSL_sk_insert(st, data, st->num));
 226 }
 227
 228 int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
 229 {
 230     return (OPENSSL_sk_insert(st, data, 0));
 231 }
 232
 233 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 234 {
 235     if (st == NULL)
 236         return (NULL);
 237     if (st->num <= 0)
 238         return (NULL);
 239     return (OPENSSL_sk_delete(st, 0));
 240 }
 241
 242 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 243 {
 244     if (st == NULL)
 245         return (NULL);
 246     if (st->num <= 0)
 247         return (NULL);
 248     return (OPENSSL_sk_delete(st, st->num - 1));
 249 }
 250
 251 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 252 {
 253     if (st == NULL)
 254         return;
 255     if (st->num <= 0)
 256         return;
 257     memset(st->data, 0, sizeof(*st->data) * st->num);
 258     st->num = 0;
 259 }
 260
 261 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 262 {
 263     int i;
 264
 265     if (st == NULL)
 266         return;
 267     for (i = 0; i < st->num; i++)
 268         if (st->data[i] != NULL)
 269             func((char *)st->data[i]);
 270     OPENSSL_sk_free(st);
 271 }
 272
 273 void OPENSSL_sk_free(OPENSSL_STACK *st)
 274 {
 275     if (st == NULL)
 276         return;
 277     OPENSSL_free(st->data);
 278     OPENSSL_free(st);
 279 }
 280
 281 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 282 {
 283     if (st == NULL)
 284         return -1;
 285     return st->num;
 286 }
 287
 288 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 289 {
 290     if (st == NULL || i < 0 || i >= st->num)
 291         return NULL;
 292     return (void *)st->data[i];
 293 }
 294
 295 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
 296 {
 297     if (st == NULL || i < 0 || i >= st->num)
 298         return NULL;
 299     st->data[i] = data;
 300     return (void *)st->data[i];
 301 }
 302
 303 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 304 {
 305     if (st && !st->sorted && st->comp != NULL) {
 306         qsort(st->data, st->num, sizeof(char *), st->comp);
 307         st->sorted = 1;
 308     }
 309 }
 310
 311 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 312 {
 313     if (st == NULL)
 314         return 1;
 315     return st->sorted;
 316 }