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 SYSCTL_UINT(_kern_geom_eli, OID_AUTO, key_cache_limit, CTLFLAG_RDTUN, 51 &g_eli_key_cache_limit, 0, "Maximum number of encryption keys to cache"); 52 static uint64_t g_eli_key_cache_hits; 53 SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_hits, CTLFLAG_RW, 54 &g_eli_key_cache_hits, 0, "Key cache hits"); 55 static uint64_t g_eli_key_cache_misses; 56 SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_misses, CTLFLAG_RW, 57 &g_eli_key_cache_misses, 0, "Key cache misses"); 58 59 #define G_ELI_KEY_MAGIC 0xe11341c 60 61 struct g_eli_key { 62 /* Key value, must be first in the structure. */ 63 uint8_t gek_key[G_ELI_DATAKEYLEN]; 64 /* Magic. */ 65 int gek_magic; 66 /* Key number. */ 67 uint64_t gek_keyno; 68 /* Reference counter. */ 69 int gek_count; 70 /* Keeps keys sorted by most recent use. */ 71 TAILQ_ENTRY(g_eli_key) gek_next; 72 /* Keeps keys sorted by number. */ 73 RB_ENTRY(g_eli_key) gek_link; 74 }; 75 76 static int 77 g_eli_key_cmp(const struct g_eli_key *a, const struct g_eli_key *b) 78 { 79 80 if (a->gek_keyno > b->gek_keyno) 81 return (1); 82 else if (a->gek_keyno < b->gek_keyno) 83 return (-1); 84 return (0); 85 } 86 87 RB_PROTOTYPE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp); 88 RB_GENERATE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp); 89 90 static void 91 g_eli_key_fill(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno) 92 { 93 const uint8_t *ekey; 94 struct { 95 char magic[4]; 96 uint8_t keyno[8]; 97 } __packed hmacdata; 98 99 if ((sc->sc_flags & G_ELI_FLAG_ENC_IVKEY) != 0) 100 ekey = sc->sc_mkey; 101 else 102 ekey = sc->sc_ekey; 103 104 bcopy("ekey", hmacdata.magic, 4); 105 le64enc(hmacdata.keyno, keyno); 106 g_eli_crypto_hmac(ekey, G_ELI_MAXKEYLEN, (uint8_t *)&hmacdata, 107 sizeof(hmacdata), key->gek_key, 0); 108 key->gek_keyno = keyno; 109 key->gek_count = 0; 110 key->gek_magic = G_ELI_KEY_MAGIC; 111 } 112 113 static struct g_eli_key * 114 g_eli_key_allocate(struct g_eli_softc *sc, uint64_t keyno) 115 { 116 struct g_eli_key *key, *ekey, keysearch; 117 118 mtx_assert(&sc->sc_ekeys_lock, MA_OWNED); 119 mtx_unlock(&sc->sc_ekeys_lock); 120 121 key = malloc(sizeof(*key), M_ELI, M_WAITOK); 122 g_eli_key_fill(sc, key, keyno); 123 124 mtx_lock(&sc->sc_ekeys_lock); 125 /* 126 * Recheck if the key wasn't added while we weren't holding the lock. 127 */ 128 keysearch.gek_keyno = keyno; 129 ekey = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch); 130 if (ekey != NULL) { 131 bzero(key, sizeof(*key)); 132 free(key, M_ELI); 133 key = ekey; 134 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next); 135 } else { 136 RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key); 137 sc->sc_ekeys_allocated++; 138 } 139 TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next); 140 141 return (key); 142 } 143 144 static struct g_eli_key * 145 g_eli_key_find_last(struct g_eli_softc *sc) 146 { 147 struct g_eli_key *key; 148 149 mtx_assert(&sc->sc_ekeys_lock, MA_OWNED); 150 151 TAILQ_FOREACH(key, &sc->sc_ekeys_queue, gek_next) { 152 if (key->gek_count == 0) 153 break; 154 } 155 156 return (key); 157 } 158 159 static void 160 g_eli_key_replace(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno) 161 { 162 163 mtx_assert(&sc->sc_ekeys_lock, MA_OWNED); 164 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid magic.")); 165 166 RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key); 167 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next); 168 169 KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count)); 170 171 g_eli_key_fill(sc, key, keyno); 172 173 RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key); 174 TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next); 175 } 176 177 static void 178 g_eli_key_remove(struct g_eli_softc *sc, struct g_eli_key *key) 179 { 180 181 mtx_assert(&sc->sc_ekeys_lock, MA_OWNED); 182 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid magic.")); 183 KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count)); 184 185 RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key); 186 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next); 187 sc->sc_ekeys_allocated--; 188 bzero(key, sizeof(*key)); 189 free(key, M_ELI); 190 } 191 192 void 193 g_eli_key_init(struct g_eli_softc *sc) 194 { 195 uint8_t *mkey; 196 197 mtx_lock(&sc->sc_ekeys_lock); 198 199 mkey = sc->sc_mkey + sizeof(sc->sc_ivkey); 200 if ((sc->sc_flags & G_ELI_FLAG_AUTH) == 0) 201 bcopy(mkey, sc->sc_ekey, G_ELI_DATAKEYLEN); 202 else { 203 /* 204 * The encryption key is: ekey = HMAC_SHA512(Data-Key, 0x10) 205 */ 206 g_eli_crypto_hmac(mkey, G_ELI_MAXKEYLEN, "\x10", 1, 207 sc->sc_ekey, 0); 208 } 209 210 if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) { 211 sc->sc_ekeys_total = 1; 212 sc->sc_ekeys_allocated = 0; 213 } else { 214 off_t mediasize; 215 size_t blocksize; 216 217 if ((sc->sc_flags & G_ELI_FLAG_AUTH) != 0) { 218 struct g_provider *pp; 219 220 pp = LIST_FIRST(&sc->sc_geom->consumer)->provider; 221 mediasize = pp->mediasize; 222 blocksize = pp->sectorsize; 223 } else { 224 mediasize = sc->sc_mediasize; 225 blocksize = sc->sc_sectorsize; 226 } 227 sc->sc_ekeys_total = 228 ((mediasize - 1) >> G_ELI_KEY_SHIFT) / blocksize + 1; 229 sc->sc_ekeys_allocated = 0; 230 TAILQ_INIT(&sc->sc_ekeys_queue); 231 RB_INIT(&sc->sc_ekeys_tree); 232 if (sc->sc_ekeys_total <= g_eli_key_cache_limit) { 233 uint64_t keyno; 234 235 for (keyno = 0; keyno < sc->sc_ekeys_total; keyno++) 236 (void)g_eli_key_allocate(sc, keyno); 237 KASSERT(sc->sc_ekeys_total == sc->sc_ekeys_allocated, 238 ("sc_ekeys_total=%ju != sc_ekeys_allocated=%ju", 239 (uintmax_t)sc->sc_ekeys_total, 240 (uintmax_t)sc->sc_ekeys_allocated)); 241 } 242 } 243 244 mtx_unlock(&sc->sc_ekeys_lock); 245 } 246 247 void 248 g_eli_key_destroy(struct g_eli_softc *sc) 249 { 250 251 mtx_lock(&sc->sc_ekeys_lock); 252 if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) { 253 bzero(sc->sc_ekey, sizeof(sc->sc_ekey)); 254 } else { 255 struct g_eli_key *key; 256 257 while ((key = TAILQ_FIRST(&sc->sc_ekeys_queue)) != NULL) 258 g_eli_key_remove(sc, key); 259 TAILQ_INIT(&sc->sc_ekeys_queue); 260 RB_INIT(&sc->sc_ekeys_tree); 261 } 262 mtx_unlock(&sc->sc_ekeys_lock); 263 } 264 265 /* 266 * Select encryption key. If G_ELI_FLAG_SINGLE_KEY is present we only have one 267 * key available for all the data. If the flag is not present select the key 268 * based on data offset. 269 */ 270 uint8_t * 271 g_eli_key_hold(struct g_eli_softc *sc, off_t offset, size_t blocksize) 272 { 273 struct g_eli_key *key, keysearch; 274 uint64_t keyno; 275 276 if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) 277 return (sc->sc_ekey); 278 279 /* We switch key every 2^G_ELI_KEY_SHIFT blocks. */ 280 keyno = (offset >> G_ELI_KEY_SHIFT) / blocksize; 281 282 KASSERT(keyno < sc->sc_ekeys_total, 283 ("%s: keyno=%ju >= sc_ekeys_total=%ju", 284 __func__, (uintmax_t)keyno, (uintmax_t)sc->sc_ekeys_total)); 285 286 keysearch.gek_keyno = keyno; 287 288 if (sc->sc_ekeys_total == sc->sc_ekeys_allocated) { 289 /* We have all the keys, so avoid some overhead. */ 290 key = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch); 291 KASSERT(key != NULL, ("No key %ju found.", (uintmax_t)keyno)); 292 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, 293 ("Invalid key magic.")); 294 return (key->gek_key); 295 } 296 297 mtx_lock(&sc->sc_ekeys_lock); 298 key = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch); 299 if (key != NULL) { 300 g_eli_key_cache_hits++; 301 TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next); 302 TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next); 303 } else { 304 /* 305 * No key in cache, find the least recently unreferenced key 306 * or allocate one if we haven't reached our limit yet. 307 */ 308 if (sc->sc_ekeys_allocated < g_eli_key_cache_limit) { 309 key = g_eli_key_allocate(sc, keyno); 310 } else { 311 g_eli_key_cache_misses++; 312 key = g_eli_key_find_last(sc); 313 if (key != NULL) { 314 g_eli_key_replace(sc, key, keyno); 315 } else { 316 /* All keys are referenced? Allocate one. */ 317 key = g_eli_key_allocate(sc, keyno); 318 } 319 } 320 } 321 key->gek_count++; 322 mtx_unlock(&sc->sc_ekeys_lock); 323 324 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid key magic.")); 325 326 return (key->gek_key); 327 } 328 329 void 330 g_eli_key_drop(struct g_eli_softc *sc, uint8_t *rawkey) 331 { 332 struct g_eli_key *key = (struct g_eli_key *)rawkey; 333 334 if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) 335 return; 336 337 KASSERT(key->gek_magic == G_ELI_KEY_MAGIC, ("Invalid key magic.")); 338 339 if (sc->sc_ekeys_total == sc->sc_ekeys_allocated) 340 return; 341 342 mtx_lock(&sc->sc_ekeys_lock); 343 KASSERT(key->gek_count > 0, ("key->gek_count=%d", key->gek_count)); 344 key->gek_count--; 345 while (sc->sc_ekeys_allocated > g_eli_key_cache_limit) { 346 key = g_eli_key_find_last(sc); 347 if (key == NULL) 348 break; 349 g_eli_key_remove(sc, key); 350 } 351 mtx_unlock(&sc->sc_ekeys_lock); 352 } 353