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