Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
       3                 :            :  *
       4                 :            :  * Licensed under the Apache License, Version 2.0 (the "License").
       5                 :            :  * You may not use this file except in compliance with the License.
       6                 :            :  * A copy of the License is located at
       7                 :            :  *
       8                 :            :  *  http://aws.amazon.com/apache2.0
       9                 :            :  *
      10                 :            :  * or in the "license" file accompanying this file. This file is distributed
      11                 :            :  * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
      12                 :            :  * express or implied. See the License for the specific language governing
      13                 :            :  * permissions and limitations under the License.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "utils/s2n_map.h"
      17                 :            : 
      18                 :            : #include <stdio.h>
      19                 :            : #include <string.h>
      20                 :            : 
      21                 :            : #include "api/s2n.h"
      22                 :            : #include "crypto/s2n_hash.h"
      23                 :            : #include "error/s2n_errno.h"
      24                 :            : #include "utils/s2n_blob.h"
      25                 :            : #include "utils/s2n_map_internal.h"
      26                 :            : #include "utils/s2n_mem.h"
      27                 :            : #include "utils/s2n_result.h"
      28                 :            : #include "utils/s2n_safety.h"
      29                 :            : 
      30                 :          3 : #define S2N_INITIAL_TABLE_SIZE 1024
      31                 :            : 
      32                 :            : static S2N_RESULT s2n_map_slot(const struct s2n_map *map, struct s2n_blob *key, uint32_t *slot)
      33                 :      26599 : {
      34 [ #  # ][ -  + ]:      26599 :     RESULT_ENSURE_REF(map);
      35 [ -  + ][ #  # ]:      26599 :     RESULT_ENSURE(map->capacity != 0, S2N_ERR_SAFETY);
      36                 :      26599 :     union {
      37                 :      26599 :         uint8_t u8[32];
      38                 :      26599 :         uint32_t u32[8];
      39                 :      26599 :     } digest;
      40                 :            : 
      41                 :      26599 :     DEFER_CLEANUP(struct s2n_hash_state sha256 = { 0 }, s2n_hash_free);
      42         [ -  + ]:      26599 :     RESULT_GUARD_POSIX(s2n_hash_new(&sha256));
      43         [ -  + ]:      26599 :     RESULT_GUARD_POSIX(s2n_hash_init(&sha256, S2N_HASH_SHA256));
      44         [ -  + ]:      26599 :     RESULT_GUARD_POSIX(s2n_hash_update(&sha256, key->data, key->size));
      45         [ -  + ]:      26599 :     RESULT_GUARD_POSIX(s2n_hash_digest(&sha256, digest.u8, sizeof(digest)));
      46                 :            : 
      47                 :      26599 :     *slot = digest.u32[0] % map->capacity;
      48                 :      26599 :     return S2N_RESULT_OK;
      49                 :      26599 : }
      50                 :            : 
      51                 :            : static S2N_RESULT s2n_map_embiggen(struct s2n_map *map, uint32_t capacity)
      52                 :       2706 : {
      53 [ #  # ][ -  + ]:       2706 :     RESULT_ENSURE_REF(map);
      54                 :       2706 :     struct s2n_blob mem = { 0 };
      55                 :       2706 :     struct s2n_map tmp = { 0 };
      56                 :            : 
      57 [ #  # ][ -  + ]:       2706 :     RESULT_ENSURE(!map->immutable, S2N_ERR_MAP_IMMUTABLE);
      58                 :            : 
      59         [ -  + ]:       2706 :     RESULT_GUARD_POSIX(s2n_alloc(&mem, (capacity * sizeof(struct s2n_map_entry))));
      60         [ -  + ]:       2706 :     RESULT_GUARD_POSIX(s2n_blob_zero(&mem));
      61                 :            : 
      62                 :       2706 :     tmp.capacity = capacity;
      63                 :       2706 :     tmp.size = 0;
      64                 :       2706 :     tmp.table = (void *) mem.data;
      65                 :       2706 :     tmp.immutable = 0;
      66                 :            : 
      67         [ +  + ]:      19121 :     for (size_t i = 0; i < map->capacity; i++) {
      68         [ +  + ]:      16415 :         if (map->table[i].key.size) {
      69         [ -  + ]:       8237 :             RESULT_GUARD(s2n_map_add(&tmp, &map->table[i].key, &map->table[i].value));
      70         [ -  + ]:       8237 :             RESULT_GUARD_POSIX(s2n_free(&map->table[i].key));
      71         [ -  + ]:       8237 :             RESULT_GUARD_POSIX(s2n_free(&map->table[i].value));
      72                 :       8237 :         }
      73                 :      16415 :     }
      74         [ -  + ]:       2706 :     RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) &map->table, map->capacity * sizeof(struct s2n_map_entry)));
      75                 :            : 
      76                 :            :     /* Clone the temporary map */
      77                 :       2706 :     map->capacity = tmp.capacity;
      78                 :       2706 :     map->size = tmp.size;
      79                 :       2706 :     map->table = tmp.table;
      80                 :       2706 :     map->immutable = 0;
      81                 :            : 
      82                 :       2706 :     return S2N_RESULT_OK;
      83                 :       2706 : }
      84                 :            : 
      85                 :            : struct s2n_map *s2n_map_new()
      86                 :          3 : {
      87                 :          3 :     return s2n_map_new_with_initial_capacity(S2N_INITIAL_TABLE_SIZE);
      88                 :          3 : }
      89                 :            : 
      90                 :            : struct s2n_map *s2n_map_new_with_initial_capacity(uint32_t capacity)
      91                 :       2662 : {
      92 [ +  - ][ +  + ]:       2662 :     PTR_ENSURE(capacity != 0, S2N_ERR_MAP_INVALID_MAP_SIZE);
      93                 :       2661 :     struct s2n_blob mem = { 0 };
      94                 :       2661 :     struct s2n_map *map = NULL;
      95                 :            : 
      96         [ -  + ]:       2661 :     PTR_GUARD_POSIX(s2n_alloc(&mem, sizeof(struct s2n_map)));
      97                 :            : 
      98                 :       2661 :     map = (void *) mem.data;
      99                 :       2661 :     map->capacity = 0;
     100                 :       2661 :     map->size = 0;
     101                 :       2661 :     map->immutable = 0;
     102                 :       2661 :     map->table = NULL;
     103                 :            : 
     104         [ -  + ]:       2661 :     PTR_GUARD_RESULT(s2n_map_embiggen(map, capacity));
     105                 :            : 
     106                 :       2661 :     return map;
     107                 :       2661 : }
     108                 :            : 
     109                 :            : S2N_RESULT s2n_map_add(struct s2n_map *map, struct s2n_blob *key, struct s2n_blob *value)
     110                 :      17290 : {
     111 [ -  + ][ #  # ]:      17290 :     RESULT_ENSURE_REF(map);
     112 [ +  - ][ +  + ]:      17290 :     RESULT_ENSURE(!map->immutable, S2N_ERR_MAP_IMMUTABLE);
     113                 :            : 
     114         [ +  + ]:      17289 :     if (map->capacity < (map->size * 2)) {
     115                 :            :         /* Embiggen the map */
     116         [ -  + ]:         45 :         RESULT_GUARD(s2n_map_embiggen(map, map->capacity * 2));
     117                 :         45 :     }
     118                 :            : 
     119                 :      17289 :     uint32_t slot = 0;
     120         [ -  + ]:      17289 :     RESULT_GUARD(s2n_map_slot(map, key, &slot));
     121                 :            : 
     122                 :            :     /* Linear probing until we find an empty slot */
     123         [ +  + ]:      25283 :     while (map->table[slot].key.size) {
     124 [ +  + ][ +  + ]:       8004 :         if (key->size != map->table[slot].key.size || memcmp(key->data, map->table[slot].key.data, key->size)) {
     125                 :       7994 :             slot++;
     126                 :       7994 :             slot %= map->capacity;
     127                 :       7994 :             continue;
     128                 :       7994 :         }
     129                 :            : 
     130                 :            :         /* We found a duplicate key */
     131         [ +  - ]:         10 :         RESULT_BAIL(S2N_ERR_MAP_DUPLICATE);
     132                 :         10 :     }
     133                 :            : 
     134         [ +  + ]:      17279 :     RESULT_GUARD_POSIX(s2n_dup(key, &map->table[slot].key));
     135         [ -  + ]:      17278 :     RESULT_GUARD_POSIX(s2n_dup(value, &map->table[slot].value));
     136                 :      17278 :     map->size++;
     137                 :            : 
     138                 :      17278 :     return S2N_RESULT_OK;
     139                 :      17278 : }
     140                 :            : 
     141                 :            : S2N_RESULT s2n_map_put(struct s2n_map *map, struct s2n_blob *key, struct s2n_blob *value)
     142                 :         21 : {
     143 [ #  # ][ -  + ]:         21 :     RESULT_ENSURE_REF(map);
     144 [ -  + ][ #  # ]:         21 :     RESULT_ENSURE(!map->immutable, S2N_ERR_MAP_IMMUTABLE);
     145                 :            : 
     146         [ -  + ]:         21 :     if (map->capacity < (map->size * 2)) {
     147                 :            :         /* Embiggen the map */
     148         [ #  # ]:          0 :         RESULT_GUARD(s2n_map_embiggen(map, map->capacity * 2));
     149                 :          0 :     }
     150                 :            : 
     151                 :         21 :     uint32_t slot = 0;
     152         [ -  + ]:         21 :     RESULT_GUARD(s2n_map_slot(map, key, &slot));
     153                 :            : 
     154                 :            :     /* Linear probing until we find an empty slot */
     155         [ +  + ]:         21 :     while (map->table[slot].key.size) {
     156 [ -  + ][ -  + ]:         10 :         if (key->size != map->table[slot].key.size || memcmp(key->data, map->table[slot].key.data, key->size)) {
     157                 :          0 :             slot++;
     158                 :          0 :             slot %= map->capacity;
     159                 :          0 :             continue;
     160                 :          0 :         }
     161                 :            : 
     162                 :            :         /* We found a duplicate key that will be overwritten */
     163         [ -  + ]:         10 :         RESULT_GUARD_POSIX(s2n_free(&map->table[slot].key));
     164         [ -  + ]:         10 :         RESULT_GUARD_POSIX(s2n_free(&map->table[slot].value));
     165                 :         10 :         map->size--;
     166                 :         10 :         break;
     167                 :         10 :     }
     168                 :            : 
     169         [ +  + ]:         21 :     RESULT_GUARD_POSIX(s2n_dup(key, &map->table[slot].key));
     170         [ -  + ]:         20 :     RESULT_GUARD_POSIX(s2n_dup(value, &map->table[slot].value));
     171                 :         20 :     map->size++;
     172                 :            : 
     173                 :         20 :     return S2N_RESULT_OK;
     174                 :         20 : }
     175                 :            : 
     176                 :            : S2N_RESULT s2n_map_complete(struct s2n_map *map)
     177                 :       3511 : {
     178 [ -  + ][ #  # ]:       3511 :     RESULT_ENSURE_REF(map);
     179                 :       3511 :     map->immutable = 1;
     180                 :            : 
     181                 :       3511 :     return S2N_RESULT_OK;
     182                 :       3511 : }
     183                 :            : 
     184                 :            : S2N_RESULT s2n_map_unlock(struct s2n_map *map)
     185                 :        851 : {
     186 [ #  # ][ -  + ]:        851 :     RESULT_ENSURE_REF(map);
     187                 :        851 :     map->immutable = 0;
     188                 :            : 
     189                 :        851 :     return S2N_RESULT_OK;
     190                 :        851 : }
     191                 :            : 
     192                 :            : S2N_RESULT s2n_map_lookup(const struct s2n_map *map, struct s2n_blob *key, struct s2n_blob *value, bool *key_found)
     193                 :       9291 : {
     194 [ -  + ][ #  # ]:       9291 :     RESULT_ENSURE_REF(map);
     195 [ +  + ][ +  - ]:       9291 :     RESULT_ENSURE(map->immutable, S2N_ERR_MAP_MUTABLE);
     196                 :            : 
     197                 :       9289 :     uint32_t slot = 0;
     198         [ -  + ]:       9289 :     RESULT_GUARD(s2n_map_slot(map, key, &slot));
     199                 :       9289 :     const uint32_t initial_slot = slot;
     200                 :            : 
     201         [ +  + ]:      13495 :     while (map->table[slot].key.size) {
     202 [ +  + ][ +  + ]:      12670 :         if (key->size != map->table[slot].key.size || memcmp(key->data, map->table[slot].key.data, key->size)) {
     203                 :       4329 :             slot++;
     204                 :       4329 :             slot %= map->capacity;
     205                 :            :             /* We went over all the slots but found no match */
     206         [ +  + ]:       4329 :             if (slot == initial_slot) {
     207                 :        123 :                 break;
     208                 :        123 :             }
     209                 :       4206 :             continue;
     210                 :       4329 :         }
     211                 :            : 
     212                 :            :         /* We found a match */
     213                 :       8341 :         struct s2n_blob entry_value = map->table[slot].value;
     214         [ -  + ]:       8341 :         RESULT_GUARD_POSIX(s2n_blob_init(value, entry_value.data, entry_value.size));
     215                 :            : 
     216                 :       8341 :         *key_found = true;
     217                 :            : 
     218                 :       8341 :         return S2N_RESULT_OK;
     219                 :       8341 :     }
     220                 :            : 
     221                 :        948 :     *key_found = false;
     222                 :            : 
     223                 :        948 :     return S2N_RESULT_OK;
     224                 :       9289 : }
     225                 :            : 
     226                 :            : S2N_RESULT s2n_map_free(struct s2n_map *map)
     227                 :       3206 : {
     228         [ +  + ]:       3206 :     if (map == NULL) {
     229                 :        545 :         return S2N_RESULT_OK;
     230                 :        545 :     }
     231                 :            : 
     232                 :            :     /* Free the keys and values */
     233                 :            :     /* cppcheck has a false positive warning for checking the pointer here */
     234                 :            :     /* cppcheck-suppress nullPointerRedundantCheck */
     235         [ +  + ]:      24806 :     for (size_t i = 0; i < map->capacity; i++) {
     236         [ +  + ]:      22145 :         if (map->table[i].key.size) {
     237         [ -  + ]:       9053 :             RESULT_GUARD_POSIX(s2n_free(&map->table[i].key));
     238         [ -  + ]:       9053 :             RESULT_GUARD_POSIX(s2n_free(&map->table[i].value));
     239                 :       9053 :         }
     240                 :      22145 :     }
     241                 :            : 
     242                 :            :     /* Free the table */
     243         [ -  + ]:       2661 :     RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) &map->table, map->capacity * sizeof(struct s2n_map_entry)));
     244                 :            : 
     245                 :            :     /* And finally the map */
     246         [ -  + ]:       2661 :     RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) &map, sizeof(struct s2n_map)));
     247                 :            : 
     248                 :       2661 :     return S2N_RESULT_OK;
     249                 :       2661 : }
     250                 :            : 
     251                 :            : S2N_RESULT s2n_map_size(struct s2n_map *map, uint32_t *size)
     252                 :          5 : {
     253 [ -  + ][ #  # ]:          5 :     RESULT_ENSURE_REF(map);
     254                 :          5 :     *size = map->size;
     255                 :          5 :     return S2N_RESULT_OK;
     256                 :          5 : }
     257                 :            : 
     258                 :            : /* Update the internal state so that `current_index` will point to the next value
     259                 :            :  * in the table or set iter->consumed equal to true if there are no more elements
     260                 :            :  * in the map. 
     261                 :            :  */
     262                 :            : S2N_RESULT s2n_map_iterator_advance(struct s2n_map_iterator *iter)
     263                 :         25 : {
     264 [ #  # ][ -  + ]:         25 :     RESULT_ENSURE_REF(iter);
     265 [ -  + ][ #  # ]:         25 :     RESULT_ENSURE_REF(iter->map);
     266 [ -  + ][ #  # ]:         25 :     RESULT_ENSURE(s2n_map_iterator_has_next(iter), S2N_ERR_ARRAY_INDEX_OOB);
     267                 :            : 
     268                 :         25 :     iter->current_index++;
     269         [ +  + ]:       3125 :     while (iter->current_index < iter->map->capacity) {
     270                 :            :         /* a value was found in the map */
     271         [ +  + ]:       3112 :         if (iter->map->table[iter->current_index].key.size) {
     272                 :         12 :             return S2N_RESULT_OK;
     273                 :         12 :         }
     274                 :       3100 :         iter->current_index++;
     275                 :       3100 :     }
     276                 :            :     /* no more values were found in the map */
     277                 :         13 :     iter->consumed = true;
     278                 :         13 :     return S2N_RESULT_OK;
     279                 :         25 : }
     280                 :            : 
     281                 :            : S2N_RESULT s2n_map_iterator_init(struct s2n_map_iterator *iter, const struct s2n_map *map)
     282                 :         16 : {
     283 [ #  # ][ -  + ]:         16 :     RESULT_ENSURE_REF(iter);
     284 [ -  + ][ #  # ]:         16 :     RESULT_ENSURE_REF(map);
     285 [ +  - ][ +  + ]:         16 :     RESULT_ENSURE(map->immutable, S2N_ERR_MAP_MUTABLE);
     286                 :            : 
     287                 :         14 :     iter->map = map;
     288                 :         14 :     iter->current_index = 0;
     289                 :            : 
     290                 :            :     /* Advance the index to point to the first value in the map. This isn't 
     291                 :            :      * necessary if the slot at index 0 already contains a value.
     292                 :            :      */
     293         [ +  + ]:         14 :     if (iter->map->table[0].key.size == 0) {
     294         [ -  + ]:          4 :         RESULT_GUARD(s2n_map_iterator_advance(iter));
     295                 :          4 :     }
     296                 :            : 
     297                 :         14 :     return S2N_RESULT_OK;
     298                 :         14 : }
     299                 :            : 
     300                 :            : S2N_RESULT s2n_map_iterator_next(struct s2n_map_iterator *iter, struct s2n_blob *value)
     301                 :         24 : {
     302 [ -  + ][ #  # ]:         24 :     RESULT_ENSURE_REF(iter);
     303 [ -  + ][ #  # ]:         24 :     RESULT_ENSURE_REF(iter->map);
     304 [ -  + ][ #  # ]:         24 :     RESULT_ENSURE(iter->map->immutable, S2N_ERR_MAP_MUTABLE);
     305 [ +  - ][ +  + ]:         24 :     RESULT_ENSURE(s2n_map_iterator_has_next(iter), S2N_ERR_ARRAY_INDEX_OOB);
     306                 :            : 
     307 [ -  + ][ #  # ]:         22 :     RESULT_ENSURE(iter->current_index < iter->map->capacity, S2N_ERR_ARRAY_INDEX_OOB);
     308                 :         22 :     struct s2n_blob entry_value = iter->map->table[iter->current_index].value;
     309         [ +  + ]:         22 :     RESULT_GUARD_POSIX(s2n_blob_init(value, entry_value.data, entry_value.size));
     310                 :            : 
     311         [ -  + ]:         21 :     RESULT_GUARD(s2n_map_iterator_advance(iter));
     312                 :            : 
     313                 :         21 :     return S2N_RESULT_OK;
     314                 :         21 : }
     315                 :            : 
     316                 :            : bool s2n_map_iterator_has_next(const struct s2n_map_iterator *iter)
     317                 :         81 : {
     318 [ +  - ][ +  + ]:         81 :     return iter && !iter->consumed;
     319                 :         81 : }