Instead of allocating memory for all the keys at device attach,

create reasonably large cache for the keys that is filled when
needed. The previous version was problematic for very large providers
(hundreds of terabytes or serval petabytes). Every terabyte of data
needs around 256kB for keys. Make the default cache limit big enough
to fit all the keys needed for 4TB providers, which will eat at most
1MB of memory.

MFC after:	2 weeks

8 files changed, 387 insertions, 138 deletions

diff --git a/sys/geom/eli/g_eli.c b/sys/geom/eli/g_eli.c
index 9f712cf..8edd147 100644
--- a/sys/geom/eli/g_eli.c
+++ b/sys/geom/eli/g_eli.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -329,7 +329,7 @@ g_eli_newsession(struct g_eli_worker *wr)
 	crie.cri_klen = sc->sc_ekeylen;
 	if (sc->sc_ealgo == CRYPTO_AES_XTS)
 		crie.cri_klen <<= 1;
-	crie.cri_key = sc->sc_ekeys[0];
+	crie.cri_key = sc->sc_ekey;
 	if (sc->sc_flags & G_ELI_FLAG_AUTH) {
 		bzero(&cria, sizeof(cria));
 		cria.cri_alg = sc->sc_aalgo;
@@ -522,34 +522,6 @@ again:
 }
 
 /*
- * Select encryption key. If G_ELI_FLAG_SINGLE_KEY is present we only have one
- * key available for all the data. If the flag is not present select the key
- * based on data offset.
- */
-uint8_t *
-g_eli_crypto_key(struct g_eli_softc *sc, off_t offset, size_t blocksize)
-{
-	u_int nkey;
-
-	if (sc->sc_nekeys == 1)
-		return (sc->sc_ekeys[0]);
-
-	KASSERT(sc->sc_nekeys > 1, ("%s: sc_nekeys=%u", __func__,
-	    sc->sc_nekeys));
-	KASSERT((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) == 0,
-	    ("%s: SINGLE_KEY flag set, but sc_nekeys=%u", __func__,
-	    sc->sc_nekeys));
-
-	/* We switch key every 2^G_ELI_KEY_SHIFT blocks. */
-	nkey = (offset >> G_ELI_KEY_SHIFT) / blocksize;
-
-	KASSERT(nkey < sc->sc_nekeys, ("%s: nkey=%u >= sc_nekeys=%u", __func__,
-	    nkey, sc->sc_nekeys));
-
-	return (sc->sc_ekeys[nkey]);
-}
-
-/*
  * Here we generate IV. It is unique for every sector.
  */
 void
@@ -766,6 +738,7 @@ g_eli_create(struct gctl_req *req, struct g_class *mp, struct g_provider *bpp,
 
 	bioq_init(&sc->sc_queue);
 	mtx_init(&sc->sc_queue_mtx, "geli:queue", NULL, MTX_DEF);
+	mtx_init(&sc->sc_ekeys_lock, "geli:ekeys", NULL, MTX_DEF);
 
 	pp = NULL;
 	cp = g_new_consumer(gp);
@@ -909,11 +882,7 @@ failed:
 	}
 	g_destroy_consumer(cp);
 	g_destroy_geom(gp);
-	if (sc->sc_ekeys != NULL) {
-		bzero(sc->sc_ekeys,
-		    sc->sc_nekeys * (sizeof(uint8_t *) + G_ELI_DATAKEYLEN));
-		free(sc->sc_ekeys, M_ELI);
-	}
+	g_eli_key_destroy(sc);
 	bzero(sc, sizeof(*sc));
 	free(sc, M_ELI);
 	return (NULL);
@@ -953,12 +922,7 @@ g_eli_destroy(struct g_eli_softc *sc, boolean_t force)
 	}
 	mtx_destroy(&sc->sc_queue_mtx);
 	gp->softc = NULL;
-	if (sc->sc_ekeys != NULL) {
-		/* The sc_ekeys field can be NULL is device is suspended. */
-		bzero(sc->sc_ekeys,
-		    sc->sc_nekeys * (sizeof(uint8_t *) + G_ELI_DATAKEYLEN));
-		free(sc->sc_ekeys, M_ELI);
-	}
+	g_eli_key_destroy(sc);
 	bzero(sc, sizeof(*sc));
 	free(sc, M_ELI);
 
@@ -1191,6 +1155,11 @@ g_eli_dumpconf(struct sbuf *sb, const char *indent, struct g_geom *gp,
 		return;
 	if (pp != NULL || cp != NULL)
 		return;	/* Nothing here. */
+
+	sbuf_printf(sb, "%s<KeysTotal>%ju</KeysTotal>", indent,
+	    (uintmax_t)sc->sc_ekeys_total);
+	sbuf_printf(sb, "%s<KeysAllocated>%ju</KeysAllocated>", indent,
+	    (uintmax_t)sc->sc_ekeys_allocated);
 	sbuf_printf(sb, "%s<Flags>", indent);
 	if (sc->sc_flags == 0)
 		sbuf_printf(sb, "NONE");
diff --git a/sys/geom/eli/g_eli.h b/sys/geom/eli/g_eli.h
index d67e436..e0fa616 100644
--- a/sys/geom/eli/g_eli.h
+++ b/sys/geom/eli/g_eli.h
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -37,6 +37,10 @@
 #ifdef _KERNEL
 #include <sys/bio.h>
 #include <sys/libkern.h>
+#include <sys/lock.h>
+#include <sys/mutex.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <geom/geom.h>
 #else
 #include <stdio.h>
@@ -150,31 +154,35 @@ struct g_eli_worker {
 };
 
 struct g_eli_softc {
-	struct g_geom	 *sc_geom;
-	u_int		  sc_crypto;
-	uint8_t		  sc_mkey[G_ELI_DATAIVKEYLEN];
-	uint8_t		**sc_ekeys;
-	u_int		  sc_nekeys;
-	u_int		  sc_ealgo;
-	u_int		  sc_ekeylen;
-	uint8_t		  sc_akey[G_ELI_AUTHKEYLEN];
-	u_int		  sc_aalgo;
-	u_int		  sc_akeylen;
-	u_int		  sc_alen;
-	SHA256_CTX	  sc_akeyctx;
-	uint8_t		  sc_ivkey[G_ELI_IVKEYLEN];
-	SHA256_CTX	  sc_ivctx;
-	int		  sc_nkey;
-	uint32_t	  sc_flags;
-	int		  sc_inflight;
-	off_t		  sc_mediasize;
-	size_t		  sc_sectorsize;
-	u_int		  sc_bytes_per_sector;
-	u_int		  sc_data_per_sector;
+	struct g_geom	*sc_geom;
+	u_int		 sc_crypto;
+	uint8_t		 sc_mkey[G_ELI_DATAIVKEYLEN];
+	uint8_t		 sc_ekey[G_ELI_DATAKEYLEN];
+	TAILQ_HEAD(, g_eli_key) sc_ekeys_queue;
+	RB_HEAD(g_eli_key_tree, g_eli_key) sc_ekeys_tree;
+	struct mtx	 sc_ekeys_lock;
+	uint64_t	 sc_ekeys_total;
+	uint64_t	 sc_ekeys_allocated;
+	u_int		 sc_ealgo;
+	u_int		 sc_ekeylen;
+	uint8_t		 sc_akey[G_ELI_AUTHKEYLEN];
+	u_int		 sc_aalgo;
+	u_int		 sc_akeylen;
+	u_int		 sc_alen;
+	SHA256_CTX	 sc_akeyctx;
+	uint8_t		 sc_ivkey[G_ELI_IVKEYLEN];
+	SHA256_CTX	 sc_ivctx;
+	int		 sc_nkey;
+	uint32_t	 sc_flags;
+	int		 sc_inflight;
+	off_t		 sc_mediasize;
+	size_t		 sc_sectorsize;
+	u_int		 sc_bytes_per_sector;
+	u_int		 sc_data_per_sector;
 
 	/* Only for software cryptography. */
 	struct bio_queue_head sc_queue;
-	struct mtx	  sc_queue_mtx;
+	struct mtx	 sc_queue_mtx;
 	LIST_HEAD(, g_eli_worker) sc_workers;
 };
 #define	sc_name		 sc_geom->name
@@ -539,4 +547,11 @@ void g_eli_crypto_hmac_update(struct hmac_ctx *ctx, const uint8_t *data,
 void g_eli_crypto_hmac_final(struct hmac_ctx *ctx, uint8_t *md, size_t mdsize);
 void g_eli_crypto_hmac(const uint8_t *hkey, size_t hkeysize,
     const uint8_t *data, size_t datasize, uint8_t *md, size_t mdsize);
+
+#ifdef _KERNEL
+void g_eli_key_init(struct g_eli_softc *sc);
+void g_eli_key_destroy(struct g_eli_softc *sc);
+uint8_t *g_eli_key_hold(struct g_eli_softc *sc, off_t offset, size_t blocksize);
+void g_eli_key_drop(struct g_eli_softc *sc, uint8_t *rawkey);
+#endif
 #endif	/* !_G_ELI_H_ */
diff --git a/sys/geom/eli/g_eli_ctl.c b/sys/geom/eli/g_eli_ctl.c
index 2413918..a5de30b 100644
--- a/sys/geom/eli/g_eli_ctl.c
+++ b/sys/geom/eli/g_eli_ctl.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -739,10 +739,7 @@ g_eli_suspend_one(struct g_eli_softc *sc, struct gctl_req *req)
 	 * Clear sensitive data on suspend, they will be recovered on resume.
 	 */
 	bzero(sc->sc_mkey, sizeof(sc->sc_mkey));
-	bzero(sc->sc_ekeys,
-	    sc->sc_nekeys * (sizeof(uint8_t *) + G_ELI_DATAKEYLEN));
-	free(sc->sc_ekeys, M_ELI);
-	sc->sc_ekeys = NULL;
+	g_eli_key_destroy(sc);
 	bzero(sc->sc_akey, sizeof(sc->sc_akey));
 	bzero(&sc->sc_akeyctx, sizeof(sc->sc_akeyctx));
 	bzero(sc->sc_ivkey, sizeof(sc->sc_ivkey));
diff --git a/sys/geom/eli/g_eli_integrity.c b/sys/geom/eli/g_eli_integrity.c
index 24586bd..d37bacb 100644
--- a/sys/geom/eli/g_eli_integrity.c
+++ b/sys/geom/eli/g_eli_integrity.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -148,12 +148,13 @@ g_eli_auth_read_done(struct cryptop *crp)
 		if (bp->bio_error == 0)
 			bp->bio_error = crp->crp_etype;
 	}
+	sc = bp->bio_to->geom->softc;
+	g_eli_key_drop(sc, crp->crp_desc->crd_key);
 	/*
 	 * Do we have all sectors already?
 	 */
 	if (bp->bio_inbed < bp->bio_children)
 		return (0);
-	sc = bp->bio_to->geom->softc;
 	if (bp->bio_error == 0) {
 		u_int i, lsec, nsec, data_secsize, decr_secsize, encr_secsize;
 		u_char *srcdata, *dstdata, *auth;
@@ -272,12 +273,13 @@ g_eli_auth_write_done(struct cryptop *crp)
 		if (bp->bio_error == 0)
 			bp->bio_error = crp->crp_etype;
 	}
+	sc = bp->bio_to->geom->softc;
+	g_eli_key_drop(sc, crp->crp_desc->crd_key);
 	/*
 	 * All sectors are already encrypted?
 	 */
 	if (bp->bio_inbed < bp->bio_children)
 		return (0);
-	sc = bp->bio_to->geom->softc;
 	if (bp->bio_error != 0) {
 		G_ELI_LOGREQ(0, bp, "Crypto WRITE request failed (error=%d).",
 		    bp->bio_error);
@@ -514,7 +516,7 @@ g_eli_auth_run(struct g_eli_worker *wr, struct bio *bp)
 		if (bp->bio_cmd == BIO_WRITE)
 			crde->crd_flags |= CRD_F_ENCRYPT;
 		crde->crd_alg = sc->sc_ealgo;
-		crde->crd_key = g_eli_crypto_key(sc, dstoff, encr_secsize);
+		crde->crd_key = g_eli_key_hold(sc, dstoff, encr_secsize);
 		crde->crd_klen = sc->sc_ekeylen;
 		if (sc->sc_ealgo == CRYPTO_AES_XTS)
 			crde->crd_klen <<= 1;
diff --git a/sys/geom/eli/g_eli_key.c b/sys/geom/eli/g_eli_key.c
index 37b2ad3..3696e2e 100644
--- a/sys/geom/eli/g_eli_key.c
+++ b/sys/geom/eli/g_eli_key.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -181,46 +181,6 @@ g_eli_mkey_encrypt(unsigned algo, const unsigned char *key, unsigned keylen,
 }
 
 #ifdef _KERNEL
-static void
-g_eli_ekeys_generate(struct g_eli_softc *sc)
-{
-	uint8_t *keys;
-	u_int kno;
-	off_t mediasize;
-	size_t blocksize;
-	struct {
-		char magic[4];
-		uint8_t keyno[8];
-	} __packed hmacdata;
-
-	KASSERT((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) == 0,
-	    ("%s: G_ELI_FLAG_SINGLE_KEY flag present", __func__));
-
-	if ((sc->sc_flags & G_ELI_FLAG_AUTH) != 0) {
-		struct g_provider *pp;
-
-		pp = LIST_FIRST(&sc->sc_geom->consumer)->provider;
-		mediasize = pp->mediasize;
-		blocksize = pp->sectorsize;
-	} else {
-		mediasize = sc->sc_mediasize;
-		blocksize = sc->sc_sectorsize;
-	}
-	sc->sc_nekeys = ((mediasize - 1) >> G_ELI_KEY_SHIFT) / blocksize + 1;
-	sc->sc_ekeys =
-	    malloc(sc->sc_nekeys * (sizeof(uint8_t *) + G_ELI_DATAKEYLEN),
-	    M_ELI, M_WAITOK);
-	keys = (uint8_t *)(sc->sc_ekeys + sc->sc_nekeys);
-	bcopy("ekey", hmacdata.magic, 4);
-	for (kno = 0; kno < sc->sc_nekeys; kno++, keys += G_ELI_DATAKEYLEN) {
-		sc->sc_ekeys[kno] = keys;
-		le64enc(hmacdata.keyno, (uint64_t)kno);
-		g_eli_crypto_hmac(sc->sc_mkey, G_ELI_MAXKEYLEN,
-		    (uint8_t *)&hmacdata, sizeof(hmacdata),
-		    sc->sc_ekeys[kno], 0);
-	}
-}
-
 /*
  * When doing encryption only, copy IV key and encryption key.
  * When doing encryption and authentication, copy IV key, generate encryption
@@ -246,24 +206,8 @@ g_eli_mkey_propagate(struct g_eli_softc *sc, const unsigned char *mkey)
 		arc4rand(sc->sc_akey, sizeof(sc->sc_akey), 0);
 	}
 
-	if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) {
-		sc->sc_nekeys = 1;
-		sc->sc_ekeys = malloc(sc->sc_nekeys *
-		    (sizeof(uint8_t *) + G_ELI_DATAKEYLEN), M_ELI, M_WAITOK);
-		sc->sc_ekeys[0] = (uint8_t *)(sc->sc_ekeys + sc->sc_nekeys);
-		if ((sc->sc_flags & G_ELI_FLAG_AUTH) == 0)
-			bcopy(mkey, sc->sc_ekeys[0], G_ELI_DATAKEYLEN);
-		else {
-			/*
-			 * The encryption key is: ekey = HMAC_SHA512(Master-Key, 0x10)
-			 */
-			g_eli_crypto_hmac(mkey, G_ELI_MAXKEYLEN, "\x10", 1,
-			    sc->sc_ekeys[0], 0);
-		}
-	} else {
-		/* Generate all encryption keys. */
-		g_eli_ekeys_generate(sc);
-	}
+	/* Initialize encryption keys. */
+	g_eli_key_init(sc);
 
 	if (sc->sc_flags & G_ELI_FLAG_AUTH) {
 		/*
diff --git a/sys/geom/eli/g_eli_key_cache.c b/sys/geom/eli/g_eli_key_cache.c
new file mode 100644
index 0000000..eab45ac
--- /dev/null
+++ b/sys/geom/eli/g_eli_key_cache.c
@@ -0,0 +1,319 @@
+/*-
+ * Copyright (c) 2011 Pawel Jakub Dawidek <pawel@dawidek.net>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/queue.h>
+#include <sys/sysctl.h>
+#include <sys/systm.h>
+#include <sys/tree.h>
+
+#include <geom/geom.h>
+
+#include <geom/eli/g_eli.h>
+
+MALLOC_DECLARE(M_ELI);
+
+SYSCTL_DECL(_kern_geom_eli);
+/*
+ * The default limit (8192 keys) will allow to cache all keys for 4TB
+ * provider with 512 bytes sectors and will take around 1MB of memory.
+ */
+static u_int g_eli_key_cache_limit = 8192;
+TUNABLE_INT("kern.geom.eli.key_cache_limit", &g_eli_key_cache_limit);
+SYSCTL_UINT(_kern_geom_eli, OID_AUTO, key_cache_limit, CTLFLAG_RDTUN,
+    &g_eli_key_cache_limit, 0, "Maximum number of encryption keys to cache");
+static uint64_t g_eli_key_cache_hits;
+SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_hits, CTLFLAG_RW,
+    &g_eli_key_cache_hits, 0, "Key cache hits");
+static uint64_t g_eli_key_cache_misses;
+SYSCTL_UQUAD(_kern_geom_eli, OID_AUTO, key_cache_misses, CTLFLAG_RW,
+    &g_eli_key_cache_misses, 0, "Key cache misses");
+
+struct g_eli_key {
+	/* Key value, must be first in the structure. */
+	uint8_t		gek_key[G_ELI_DATAKEYLEN];
+	/* Key number. */
+	uint64_t	gek_keyno;
+	/* Reference counter. */
+	int		gek_count;
+	/* Keeps keys sorted by most recent use. */
+	TAILQ_ENTRY(g_eli_key) gek_next;
+	/* Keeps keys sorted by number. */
+	RB_ENTRY(g_eli_key) gek_link;
+};
+
+static int
+g_eli_key_cmp(const struct g_eli_key *a, const struct g_eli_key *b)
+{
+
+	if (a->gek_keyno > b->gek_keyno)
+		return (1);
+	else if (a->gek_keyno < b->gek_keyno)
+		return (-1);
+	return (0);
+}
+
+RB_PROTOTYPE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp);
+RB_GENERATE(g_eli_key_tree, g_eli_key, gek_link, g_eli_key_cmp);
+
+static void
+g_eli_key_fill(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno)
+{
+	struct {
+		char magic[4];
+		uint8_t keyno[8];
+	} __packed hmacdata;
+
+	bcopy("ekey", hmacdata.magic, 4);
+	le64enc(hmacdata.keyno, keyno);
+	g_eli_crypto_hmac(sc->sc_mkey, G_ELI_MAXKEYLEN, (uint8_t *)&hmacdata,
+	    sizeof(hmacdata), key->gek_key, 0);
+	key->gek_keyno = keyno;
+	key->gek_count = 0;
+}
+
+static struct g_eli_key *
+g_eli_key_allocate(struct g_eli_softc *sc, uint64_t keyno)
+{
+	struct g_eli_key *key, *ekey, keysearch;
+
+	mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
+	mtx_unlock(&sc->sc_ekeys_lock);
+
+	key = malloc(sizeof(*key), M_ELI, M_WAITOK);
+	g_eli_key_fill(sc, key, keyno);
+
+	mtx_lock(&sc->sc_ekeys_lock);
+	/*
+	 * Recheck if the key wasn't added while we weren't holding the lock.
+	 */
+	keysearch.gek_keyno = keyno;
+	ekey = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch);
+	if (ekey != NULL) {
+		bzero(key, sizeof(*key));
+		key = ekey;
+		TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
+	} else {
+		RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key);
+		sc->sc_ekeys_allocated++;
+	}
+	TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
+
+	return (key);
+}
+
+static struct g_eli_key *
+g_eli_key_find_last(struct g_eli_softc *sc)
+{
+	struct g_eli_key *key;
+
+	mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
+
+	TAILQ_FOREACH(key, &sc->sc_ekeys_queue, gek_next) {
+		if (key->gek_count == 0)
+			break;
+	}
+
+	return (key);
+}
+
+static void
+g_eli_key_replace(struct g_eli_softc *sc, struct g_eli_key *key, uint64_t keyno)
+{
+
+	mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
+
+	RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key);
+	TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
+
+	KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count));
+
+	g_eli_key_fill(sc, key, keyno);
+
+	RB_INSERT(g_eli_key_tree, &sc->sc_ekeys_tree, key);
+	TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
+}
+
+static void
+g_eli_key_remove(struct g_eli_softc *sc, struct g_eli_key *key)
+{
+
+	mtx_assert(&sc->sc_ekeys_lock, MA_OWNED);
+
+	KASSERT(key->gek_count == 0, ("gek_count=%d", key->gek_count));
+
+	RB_REMOVE(g_eli_key_tree, &sc->sc_ekeys_tree, key);
+	TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
+	sc->sc_ekeys_allocated--;
+	bzero(key, sizeof(*key));
+	free(key, M_ELI);
+}
+
+void
+g_eli_key_init(struct g_eli_softc *sc)
+{
+
+	mtx_lock(&sc->sc_ekeys_lock);
+	if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) {
+		uint8_t *mkey;
+
+		mkey = sc->sc_mkey + sizeof(sc->sc_ivkey);
+
+		sc->sc_ekeys_total = 1;
+		sc->sc_ekeys_allocated = 0;
+		if ((sc->sc_flags & G_ELI_FLAG_AUTH) == 0)
+			bcopy(mkey, sc->sc_ekey, G_ELI_DATAKEYLEN);
+		else {
+			/*
+			 * The encryption key is: ekey = HMAC_SHA512(Master-Key, 0x10)
+			 */
+			g_eli_crypto_hmac(mkey, G_ELI_MAXKEYLEN, "\x10", 1,
+			    sc->sc_ekey, 0);
+		}
+	} else {
+		off_t mediasize;
+		size_t blocksize;
+
+		if ((sc->sc_flags & G_ELI_FLAG_AUTH) != 0) {
+			struct g_provider *pp;
+
+			pp = LIST_FIRST(&sc->sc_geom->consumer)->provider;
+			mediasize = pp->mediasize;
+			blocksize = pp->sectorsize;
+		} else {
+			mediasize = sc->sc_mediasize;
+			blocksize = sc->sc_sectorsize;
+		}
+		sc->sc_ekeys_total =
+		    ((mediasize - 1) >> G_ELI_KEY_SHIFT) / blocksize + 1;
+		sc->sc_ekeys_allocated = 0;
+		TAILQ_INIT(&sc->sc_ekeys_queue);
+		RB_INIT(&sc->sc_ekeys_tree);
+	}
+	mtx_unlock(&sc->sc_ekeys_lock);
+}
+
+void
+g_eli_key_destroy(struct g_eli_softc *sc)
+{
+
+	mtx_lock(&sc->sc_ekeys_lock);
+	if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0) {
+		bzero(sc->sc_ekey, sizeof(sc->sc_ekey));
+	} else {
+		struct g_eli_key *key;
+
+		while ((key = TAILQ_FIRST(&sc->sc_ekeys_queue)) != NULL)
+			g_eli_key_remove(sc, key);
+		TAILQ_INIT(&sc->sc_ekeys_queue);
+		RB_INIT(&sc->sc_ekeys_tree);
+	}
+	mtx_unlock(&sc->sc_ekeys_lock);
+}
+
+/*
+ * Select encryption key. If G_ELI_FLAG_SINGLE_KEY is present we only have one
+ * key available for all the data. If the flag is not present select the key
+ * based on data offset.
+ */
+uint8_t *
+g_eli_key_hold(struct g_eli_softc *sc, off_t offset, size_t blocksize)
+{
+	struct g_eli_key *key, keysearch;
+	uint64_t keyno;
+
+	if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0)
+		return (sc->sc_ekey);
+
+	KASSERT(sc->sc_ekeys_total > 1, ("%s: sc_ekeys_total=%ju", __func__,
+	    (uintmax_t)sc->sc_ekeys_total));
+	KASSERT((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) == 0,
+	    ("%s: SINGLE_KEY flag set, but sc_ekeys_total=%ju", __func__,
+	    (uintmax_t)sc->sc_ekeys_total));
+
+	/* We switch key every 2^G_ELI_KEY_SHIFT blocks. */
+	keyno = (offset >> G_ELI_KEY_SHIFT) / blocksize;
+
+	KASSERT(keyno < sc->sc_ekeys_total,
+	    ("%s: keyno=%ju >= sc_ekeys_total=%ju",
+	    __func__, (uintmax_t)keyno, (uintmax_t)sc->sc_ekeys_total));
+
+	keysearch.gek_keyno = keyno;
+
+	mtx_lock(&sc->sc_ekeys_lock);
+	key = RB_FIND(g_eli_key_tree, &sc->sc_ekeys_tree, &keysearch);
+	if (key != NULL) {
+		g_eli_key_cache_hits++;
+		TAILQ_REMOVE(&sc->sc_ekeys_queue, key, gek_next);
+		TAILQ_INSERT_TAIL(&sc->sc_ekeys_queue, key, gek_next);
+	} else {
+		/*
+		 * No key in cache, find the least recently unreferenced key
+		 * or allocate one if we haven't reached our limit yet.
+		 */
+		if (sc->sc_ekeys_allocated < g_eli_key_cache_limit) {
+			key = g_eli_key_allocate(sc, keyno);
+		} else {
+			g_eli_key_cache_misses++;
+			key = g_eli_key_find_last(sc);
+			if (key != NULL) {
+				g_eli_key_replace(sc, key, keyno);
+			} else {
+				/* All keys are referenced? Allocate one. */
+				key = g_eli_key_allocate(sc, keyno);
+			}
+		}
+	}
+	key->gek_count++;
+	mtx_unlock(&sc->sc_ekeys_lock);
+
+	return (key->gek_key);
+}
+
+void
+g_eli_key_drop(struct g_eli_softc *sc, uint8_t *rawkey)
+{
+	struct g_eli_key *key = (struct g_eli_key *)rawkey;
+
+	if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) != 0)
+		return;
+
+	mtx_lock(&sc->sc_ekeys_lock);
+	KASSERT(key->gek_count > 0, ("key->gek_count=%d", key->gek_count));
+	key->gek_count--;
+	while (sc->sc_ekeys_allocated > g_eli_key_cache_limit) {
+		key = g_eli_key_find_last(sc);
+		if (key == NULL)
+			break;
+		g_eli_key_remove(sc, key);
+	}
+	mtx_unlock(&sc->sc_ekeys_lock);
+}
diff --git a/sys/geom/eli/g_eli_privacy.c b/sys/geom/eli/g_eli_privacy.c
index ee133c6..cad3881 100644
--- a/sys/geom/eli/g_eli_privacy.c
+++ b/sys/geom/eli/g_eli_privacy.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2005-2010 Pawel Jakub Dawidek <pjd@FreeBSD.org>
+ * Copyright (c) 2005-2011 Pawel Jakub Dawidek <pawel@dawidek.net>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -87,6 +87,8 @@ g_eli_crypto_read_done(struct cryptop *crp)
 		if (bp->bio_error == 0)
 			bp->bio_error = crp->crp_etype;
 	}
+	sc = bp->bio_to->geom->softc;
+	g_eli_key_drop(sc, crp->crp_desc->crd_key);
 	/*
 	 * Do we have all sectors already?
 	 */
@@ -102,7 +104,6 @@ g_eli_crypto_read_done(struct cryptop *crp)
 	/*
 	 * Read is finished, send it up.
 	 */
-	sc = bp->bio_to->geom->softc;
 	g_io_deliver(bp, bp->bio_error);
 	atomic_subtract_int(&sc->sc_inflight, 1);
 	return (0);
@@ -136,6 +137,9 @@ g_eli_crypto_write_done(struct cryptop *crp)
 		if (bp->bio_error == 0)
 			bp->bio_error = crp->crp_etype;
 	}
+	gp = bp->bio_to->geom;
+	sc = gp->softc;
+	g_eli_key_drop(sc, crp->crp_desc->crd_key);
 	/*
 	 * All sectors are already encrypted?
 	 */
@@ -145,14 +149,12 @@ g_eli_crypto_write_done(struct cryptop *crp)
 	bp->bio_children = 1;
 	cbp = bp->bio_driver1;
 	bp->bio_driver1 = NULL;
-	gp = bp->bio_to->geom;
 	if (bp->bio_error != 0) {
 		G_ELI_LOGREQ(0, bp, "Crypto WRITE request failed (error=%d).",
 		    bp->bio_error);
 		free(bp->bio_driver2, M_ELI);
 		bp->bio_driver2 = NULL;
 		g_destroy_bio(cbp);
-		sc = gp->softc;
 		g_io_deliver(bp, bp->bio_error);
 		atomic_subtract_int(&sc->sc_inflight, 1);
 		return (0);
@@ -307,12 +309,12 @@ g_eli_crypto_run(struct g_eli_worker *wr, struct bio *bp)
 		crd->crd_skip = 0;
 		crd->crd_len = secsize;
 		crd->crd_flags = CRD_F_IV_EXPLICIT | CRD_F_IV_PRESENT;
-		if (sc->sc_nekeys > 1)
+		if ((sc->sc_flags & G_ELI_FLAG_SINGLE_KEY) == 0)
 			crd->crd_flags |= CRD_F_KEY_EXPLICIT;
 		if (bp->bio_cmd == BIO_WRITE)
 			crd->crd_flags |= CRD_F_ENCRYPT;
 		crd->crd_alg = sc->sc_ealgo;
-		crd->crd_key = g_eli_crypto_key(sc, dstoff, secsize);
+		crd->crd_key = g_eli_key_hold(sc, dstoff, secsize);
 		crd->crd_klen = sc->sc_ekeylen;
 		if (sc->sc_ealgo == CRYPTO_AES_XTS)
 			crd->crd_klen <<= 1;
diff --git a/sys/modules/geom/geom_eli/Makefile b/sys/modules/geom/geom_eli/Makefile
index ec71a32..51d821a 100644
--- a/sys/modules/geom/geom_eli/Makefile
+++ b/sys/modules/geom/geom_eli/Makefile
@@ -8,6 +8,7 @@ SRCS+=	g_eli_crypto.c
 SRCS+=	g_eli_ctl.c
 SRCS+=	g_eli_integrity.c
 SRCS+=	g_eli_key.c
+SRCS+=	g_eli_key_cache.c
 SRCS+=	g_eli_privacy.c
 SRCS+=	pkcs5v2.c
 SRCS+=	vnode_if.h