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 <openssl/stack.h>
  13 #include <openssl/objects.h>
  14
  15 struct stack_st {
  16     int num;
  17     const char **data;
  18     int sorted;
  19     int num_alloc;
  20     OPENSSL_sk_compfunc comp;
  21 };
  22
  23 #undef MIN_NODES
  24 #define MIN_NODES       4
  25
  26 #include <errno.h>
  27
  28 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
  29 {
  30     OPENSSL_sk_compfunc old = sk->comp;
  31
  32     if (sk->comp != c)
  33         sk->sorted = 0;
  34     sk->comp = c;
  35
  36     return old;
  37 }
  38
  39 OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
  40 {
  41     OPENSSL_STACK *ret;
  42     if ( sk->num_alloc < 0 || sk->num < 0 ) {
  43         return NULL;
  44     }
  45
  46     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  47         return NULL;
  48
  49     /* direct structure assignment */
  50     *ret = *sk;
  51
  52     if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)
  53         goto err;
  54     memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
  55     return ret;
  56  err:
  57     OPENSSL_sk_free(ret);
  58     return NULL;
  59 }
  60
  61 OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
  62                              OPENSSL_sk_copyfunc copy_func,
  63                              OPENSSL_sk_freefunc free_func)
  64 {
  65     OPENSSL_STACK *ret;
  66     int i;
  67
  68     if ( sk->num < 0 ) {
  69         return NULL;
  70     }
  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 ? 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 || st->num_alloc < 0 ) {
 124         return 0;
 125     }
 126
 127     if (st->num_alloc <= st->num + 1) {
 128
 129         /* Overflow checks by Guido
 130         *  Cast to size_t to avoid triggering -ftrapv via overflow of st->num_alloc
 131         */
 132         if ( (size_t)(st->num_alloc) * 2 < (size_t)(st->num_alloc) ) {
 133             return 0;
 134         }
 135
 136         if ( (size_t)(st->num_alloc) * 2 > INT_MAX )
 137         {
 138             return 0;
 139         }
 140
 141         /* Avond overflow due to multiplication by sizeof(char*) */
 142         if ( (size_t)(st->num_alloc) * 2 > (~(size_t)0) / sizeof(char*) ) {
 143             return 0;
 144         }
 145
 146         /* Remove cast to unsigned int to avoid undersized allocations on > 32 bit. */
 147         st->data = OPENSSL_realloc((char *)st->data,
 148                             sizeof(char *) * st->num_alloc * 2);
 149         if (st->data == NULL) {
 150             /* Reset these counters to prevent subsequent operations on
 151              * (now non-existing) heap memory
 152             */
 153             st->num_alloc = 0;
 154             st->num = 0;
 155             return (0);
 156         }
 157         st->num_alloc *= 2;
 158     }
 159     if ((loc >= (int)st->num) || (loc < 0))
 160         st->data[st->num] = data;
 161     else {
 162         if ( loc == INT_MAX ) {
 163             return 0;
 164         }
 165         memmove(&st->data[loc + 1], &st->data[loc],
 166                 sizeof(st->data[0]) * (st->num - loc));
 167         st->data[loc] = data;
 168     }
 169     st->num++;
 170     st->sorted = 0;
 171     return (st->num);
 172 }
 173
 174 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
 175 {
 176     int i;
 177
 178     for (i = 0; i < st->num; i++)
 179         if (st->data[i] == p)
 180             return OPENSSL_sk_delete(st, i);
 181     return NULL;
 182 }
 183
 184 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 185 {
 186     const char *ret;
 187
 188     if (st == NULL || loc < 0 || loc >= st->num )
 189         return NULL;
 190
 191     ret = st->data[loc];
 192     if (loc != st->num - 1)
 193          memmove(&st->data[loc], &st->data[loc + 1],
 194                  sizeof(st->data[0]) * (st->num - loc - 1));
 195     st->num--;
 196     return (void *)ret;
 197 }
 198
 199 static int internal_find(OPENSSL_STACK *st, const void *data,
 200                          int ret_val_options)
 201 {
 202     const void *r;
 203     int i;
 204
 205     if (st == NULL)
 206         return -1;
 207
 208     if (st->comp == NULL) {
 209         for (i = 0; i < st->num; i++)
 210             if (st->data[i] == data)
 211                 return (i);
 212         return (-1);
 213     }
 214     OPENSSL_sk_sort(st);
 215     if (data == NULL)
 216         return (-1);
 217     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 218                         ret_val_options);
 219     if (r == NULL)
 220         return (-1);
 221     return (int)((const char **)r - st->data);
 222 }
 223
 224 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 225 {
 226     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 227 }
 228
 229 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 230 {
 231     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 232 }
 233
 234 int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
 235 {
 236     return (OPENSSL_sk_insert(st, data, st->num));
 237 }
 238
 239 int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
 240 {
 241     return (OPENSSL_sk_insert(st, data, 0));
 242 }
 243
 244 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 245 {
 246     if (st == NULL)
 247         return (NULL);
 248     if (st->num <= 0)
 249         return (NULL);
 250     return (OPENSSL_sk_delete(st, 0));
 251 }
 252
 253 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 254 {
 255     if (st == NULL)
 256         return (NULL);
 257     if (st->num <= 0)
 258         return (NULL);
 259     return (OPENSSL_sk_delete(st, st->num - 1));
 260 }
 261
 262 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 263 {
 264     if (st == NULL)
 265         return;
 266     if (st->num <= 0)
 267         return;
 268     memset(st->data, 0, sizeof(*st->data) * st->num);
 269     st->num = 0;
 270 }
 271
 272 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 273 {
 274     int i;
 275
 276     if (st == NULL)
 277         return;
 278     for (i = 0; i < st->num; i++)
 279         if (st->data[i] != NULL)
 280             func((char *)st->data[i]);
 281     OPENSSL_sk_free(st);
 282 }
 283
 284 void OPENSSL_sk_free(OPENSSL_STACK *st)
 285 {
 286     if (st == NULL)
 287         return;
 288     OPENSSL_free(st->data);
 289     OPENSSL_free(st);
 290 }
 291
 292 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 293 {
 294     if (st == NULL)
 295         return -1;
 296     return st->num;
 297 }
 298
 299 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 300 {
 301     if (st == NULL || i < 0 || i >= st->num)
 302         return NULL;
 303     return (void *)st->data[i];
 304 }
 305
 306 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
 307 {
 308     if (st == NULL || i < 0 || i >= st->num)
 309         return NULL;
 310     st->data[i] = data;
 311     return (void *)st->data[i];
 312 }
 313
 314 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 315 {
 316     if (st && !st->sorted && st->comp != NULL) {
 317         qsort(st->data, st->num, sizeof(char *), st->comp);
 318         st->sorted = 1;
 319     }
 320 }
 321
 322 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 323 {
 324     if (st == NULL)
 325         return 1;
 326     return st->sorted;
 327 }