sys/geom/eli/g_eli_key_cache.c

   1 /*-
   2  * Copyright (c) 2011 Pawel Jakub Dawidek <pawel@dawidek.net>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  29
  30 #include <sys/param.h>
  31 #include <sys/kernel.h>
  32 #include <sys/malloc.h>
  33 #include <sys/queue.h>
  34 #include <sys/sysctl.h>
  35 #include <sys/systm.h>
  36 #include <sys/tree.h>
  37
  38 #include <geom/geom.h>
  39
  40 #include <geom/eli/g_eli.h>
  41
  42 MALLOC_DECLARE(M_ELI);
  43
  44 SYSCTL_DECL(_kern_geom_eli);
  45 /*
  46  * The default limit (8192 keys) will allow to cache all keys for 4TB
  47  * provider with 512 bytes sectors and will take around 1MB of memory.
  48  */
  49 static u_int g_eli_key_cache_limit = 8192;
  50 TUNABLE_INT("kern.geom.eli.key_cache_limit", &g_eli_key_cache_limit);
  51 SYSCTL_UINT(_kern_geom_eli, OID_AUTO, key_cache_limit, CTLFLAG_RDTUN,
  52     &g_eli_key_cache_limit, 0, "Maximum number of encryption keys to cache");
  53 static uint64_t g_eli_key_cache_hits;
  54 SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_hits, CTLFLAG_RW,
  55     &g_eli_key_cache_hits, 0, "Key cache hits");
  56 static uint64_t g_eli_key_cache_misses;
  57 SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_misses, CTLFLAG_RW,
  58     &g_eli_key_cache_misses, 0, "Key cache misses");
  59
  60 #define G_ELI_KEY_MAGIC 0xe11341c
  61
  62 struct g_eli_key {
  63         /* Key value, must be first in the structure. */
  64         uint8_t         gek_key[G_ELI_DATAKEYLEN];
  65         /* Magic. */
  66         int             gek_magic;
  67         /* Key number. */
  68         uint64_t        gek_keyno;
  69         /* Reference counter. */
  70         int             gek_count;
  71         /* Keeps keys sorted by most recent use. */
  72         TAILQ_ENTRY(g_eli_key) gek_next;
  73         /* Keeps keys sorted by number. */
  74         RB_ENTRY(g_eli_key) gek_link;
  75 };
  76
  77 static int
  78 g_eli_key_cmp(const struct g_eli_key *a, const struct g_eli_key *b)
  79 {
  80
  81         if (a->gek_keyno > b->gek_keyno)
  82                 return (1);
  83         else if (a->gek_keyno < b->gek_keyno)
  84                 return (-1);
  85         return (0);
  86 }
  87
  88 RB_PROTOTYPE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp);
  89 RB_GENERATE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp);
  90
  91 static void
  92 g_eli_key_fill(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno)
  93 {
  94         const uint8_t *ekey;
  95         struct {
  96                 char magic[4];
  97                 uint8_t keyno[8];
  98         } __packed hmacdata;
  99
 100         if ((sc->sc_flags & G_ELI_FLAG_ENC_IVKEY) != 0)
 101                 ekey = sc->sc_mkey;
 102         else
 103                 ekey = sc->sc_ekey;
 104
 105         bcopy("ekey", hmacdata.magic, 4);
 106         le64enc(hmacdata.keyno, keyno);
 107         g_eli_crypto_hmac(ekey, G_ELI_MAXKEYLEN, (uint8_t *)&hmacdata,
 108             sizeof(hmacdata), key->gek_key, 0);
 109         key->gek_keyno = keyno;
 110         key->gek_count = 0;
 111         key->gek_magic = G_ELI_KEY_MAGIC;
 112 }
 113
 114 static struct g_eli_key *
 115 g_eli_key_allocate(struct g_eli_softc *sc, uint64_t keyno)
 116 {
 117         struct g_eli_key *key, *ekey, keysearch;
 118
 119         mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
 120         mtx_unlock(&sc->sc_ekeys_lock);
 121
 122         key = malloc(sizeof(*key), M_ELI, M_WAITOK);
 123         g_eli_key_fill(sc, key, keyno);
 124
 125         mtx_lock(&sc->sc_ekeys_lock);
 126         /*
 127          * Recheck if the key wasn't added while we weren't holding the lock.
 128          */
 129         keysearch.gek_keyno = keyno;
 130         ekey = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch);
 131         if (ekey != NULL) {
 132                 bzero(key, sizeof(*key));
 133                 free(key, M_ELI);
 134                 key = ekey;
 135                 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
 136         } else {
 137                 RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key);
 138                 sc->sc_ekeys_allocated++;
 139         }
 140         TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
 141
 142         return (key);
 143 }
 144
 145 static struct g_eli_key *
 146 g_eli_key_find_last(struct g_eli_softc *sc)
 147 {
 148         struct g_eli_key *key;
 149
 150         mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
 151
 152         TAILQ_FOREACH(key, &sc->sc_ekeys_queue, gek_next) {
 153                 if (key->gek_count == 0)
 154                         break;
 155         }
 156
 157         return (key);
 158 }
 159
 160 static void
 161 g_eli_key_replace(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno)
 162 {
 163
 164         mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
 165         KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid magic."));
 166
 167         RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key);
 168         TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
 169
 170         KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count));
 171
 172         g_eli_key_fill(sc, key, keyno);
 173
 174         RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key);
 175         TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
 176 }
 177
 178 static void
 179 g_eli_key_remove(struct g_eli_softc *sc, struct g_eli_key *key)
 180 {
 181
 182         mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
 183         KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid magic."));
 184         KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count));
 185
 186         RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key);
 187         TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
 188         sc->sc_ekeys_allocated--;
 189         bzero(key, sizeof(*key));
 190         free(key, M_ELI);
 191 }
 192
 193 void
 194 g_eli_key_init(struct g_eli_softc *sc)
 195 {
 196         uint8_t *mkey;
 197
 198         mtx_lock(&sc->sc_ekeys_lock);
 199
 200         mkey = sc->sc_mkey + sizeof(sc->sc_ivkey);
 201         if ((sc->sc_flags & G_ELI_FLAG_AUTH) == 0)
 202                 bcopy(mkey, sc->sc_ekey, G_ELI_DATAKEYLEN);
 203         else {
 204                 /*
 205                  * The encryption key is: ekey = HMAC_SHA512(Data-Key, 0x10)
 206                  */
 207                 g_eli_crypto_hmac(mkey, G_ELI_MAXKEYLEN, "\x10", 1,
 208                     sc->sc_ekey, 0);
 209         }
 210
 211         if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) {
 212                 sc->sc_ekeys_total = 1;
 213                 sc->sc_ekeys_allocated = 0;
 214         } else {
 215                 off_t mediasize;
 216                 size_t blocksize;
 217
 218                 if ((sc->sc_flags & G_ELI_FLAG_AUTH) != 0) {
 219                         struct g_provider *pp;
 220
 221                         pp = LIST_FIRST(&sc->sc_geom->consumer)->provider;
 222                         mediasize = pp->mediasize;
 223                         blocksize = pp->sectorsize;
 224                 } else {
 225                         mediasize = sc->sc_mediasize;
 226                         blocksize = sc->sc_sectorsize;
 227                 }
 228                 sc->sc_ekeys_total =
 229                     ((mediasize - 1) >> G_ELI_KEY_SHIFT) / blocksize + 1;
 230                 sc->sc_ekeys_allocated = 0;
 231                 TAILQ_INIT(&sc->sc_ekeys_queue);
 232                 RB_INIT(&sc->sc_ekeys_tree);
 233                 if (sc->sc_ekeys_total <= g_eli_key_cache_limit) {
 234                         uint64_t keyno;
 235
 236                         for (keyno = 0; keyno < sc->sc_ekeys_total; keyno++)
 237                                 (void)g_eli_key_allocate(sc, keyno);
 238                         KASSERT(sc->sc_ekeys_total == sc->sc_ekeys_allocated,
 239                             ("sc_ekeys_total=%ju != sc_ekeys_allocated=%ju",
 240                             (uintmax_t)sc->sc_ekeys_total,
 241                             (uintmax_t)sc->sc_ekeys_allocated));
 242                 }
 243         }
 244
 245         mtx_unlock(&sc->sc_ekeys_lock);
 246 }
 247
 248 void
 249 g_eli_key_destroy(struct g_eli_softc *sc)
 250 {
 251
 252         mtx_lock(&sc->sc_ekeys_lock);
 253         if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) {
 254                 bzero(sc->sc_ekey, sizeof(sc->sc_ekey));
 255         } else {
 256                 struct g_eli_key *key;
 257
 258                 while ((key = TAILQ_FIRST(&sc->sc_ekeys_queue)) != NULL)
 259                         g_eli_key_remove(sc, key);
 260                 TAILQ_INIT(&sc->sc_ekeys_queue);
 261                 RB_INIT(&sc->sc_ekeys_tree);
 262         }
 263         mtx_unlock(&sc->sc_ekeys_lock);
 264 }
 265
 266 /*
 267  * Select encryption key. If G_ELI_FLAG_SINGLE_KEY is present we only have one
 268  * key available for all the data. If the flag is not present select the key
 269  * based on data offset.
 270  */
 271 uint8_t *
 272 g_eli_key_hold(struct g_eli_softc *sc, off_t offset, size_t blocksize)
 273 {
 274         struct g_eli_key *key, keysearch;
 275         uint64_t keyno;
 276
 277         if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0)
 278                 return (sc->sc_ekey);
 279
 280         /* We switch key every 2^G_ELI_KEY_SHIFT blocks. */
 281         keyno = (offset >> G_ELI_KEY_SHIFT) / blocksize;
 282
 283         KASSERT(keyno < sc->sc_ekeys_total,
 284             ("%s: keyno=%ju >= sc_ekeys_total=%ju",
 285             __func__, (uintmax_t)keyno, (uintmax_t)sc->sc_ekeys_total));
 286
 287         keysearch.gek_keyno = keyno;
 288
 289         if (sc->sc_ekeys_total == sc->sc_ekeys_allocated) {
 290                 /* We have all the keys, so avoid some overhead. */
 291                 key = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch);
 292                 KASSERT(key != NULL, ("No key %ju found.", (uintmax_t)keyno));
 293                 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC,
 294                     ("Invalid key magic."));
 295                 return (key->gek_key);
 296         }
 297
 298         mtx_lock(&sc->sc_ekeys_lock);
 299         key = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch);
 300         if (key != NULL) {
 301                 g_eli_key_cache_hits++;
 302                 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
 303                 TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
 304         } else {
 305                 /*
 306                  * No key in cache, find the least recently unreferenced key
 307                  * or allocate one if we haven't reached our limit yet.
 308                  */
 309                 if (sc->sc_ekeys_allocated < g_eli_key_cache_limit) {
 310                         key = g_eli_key_allocate(sc, keyno);
 311                 } else {
 312                         g_eli_key_cache_misses++;
 313                         key = g_eli_key_find_last(sc);
 314                         if (key != NULL) {
 315                                 g_eli_key_replace(sc, key, keyno);
 316                         } else {
 317                                 /* All keys are referenced? Allocate one. */
 318                                 key = g_eli_key_allocate(sc, keyno);
 319                         }
 320                 }
 321         }
 322         key->gek_count++;
 323         mtx_unlock(&sc->sc_ekeys_lock);
 324
 325         KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid key magic."));
 326
 327         return (key->gek_key);
 328 }
 329
 330 void
 331 g_eli_key_drop(struct g_eli_softc *sc, uint8_t *rawkey)
 332 {
 333         struct g_eli_key *key = (struct g_eli_key *)rawkey;
 334
 335         if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0)
 336                 return;
 337
 338         KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid key magic."));
 339
 340         if (sc->sc_ekeys_total == sc->sc_ekeys_allocated)
 341                 return;
 342
 343         mtx_lock(&sc->sc_ekeys_lock);
 344         KASSERT(key->gek_count > 0, ("key->gek_count=%d", key->gek_count));
 345         key->gek_count--;
 346         while (sc->sc_ekeys_allocated > g_eli_key_cache_limit) {
 347                 key = g_eli_key_find_last(sc);
 348                 if (key == NULL)
 349                         break;
 350                 g_eli_key_remove(sc, key);
 351         }
 352         mtx_unlock(&sc->sc_ekeys_lock);
 353 }