Index: crypto/aesni/aesni.h
===================================================================
--- crypto/aesni/aesni.h
+++ crypto/aesni/aesni.h
@@ -32,6 +32,7 @@
 #include <sys/types.h>
 #include <sys/malloc.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 
 #include <opencrypto/cryptodev.h>
 
@@ -63,11 +64,11 @@
 	/* uint8_t *ses_ictx; */
 	/* uint8_t *ses_octx; */
 	/* int ses_mlen; */
-	int used;
 	int auth_algo;
 	int mlen;
 	uint32_t id;
 	TAILQ_ENTRY(aesni_session) next;
+	RB_ENTRY(aesni_session) entry;
 };
 
 /*
Index: crypto/aesni/aesni.c
===================================================================
--- crypto/aesni/aesni.c
+++ crypto/aesni/aesni.c
@@ -74,10 +74,25 @@
 	uint32_t sid;
 	bool	has_aes;
 	bool	has_sha;
-	TAILQ_HEAD(aesni_sessions_head, aesni_session) sessions;
+	TAILQ_HEAD(aesni_sessions_head, aesni_session) free_sessions;
+	RB_HEAD(aesni_session_tree, aesni_session) sessions;
 	struct rwlock lock;
 };
 
+
+static __inline int
+aesni_session_id_cmp(struct aesni_session *a, struct aesni_session *b)
+{
+
+	if (a->id > b->id)
+		return (1);
+	else if (a->id < b->id)
+		return (-1);
+	return (0);
+}
+
+RB_GENERATE_STATIC(aesni_session_tree, aesni_session, entry, aesni_session_id_cmp);
+
 #define ACQUIRE_CTX(i, ctx)					\
 	do {							\
 		(i) = PCPU_GET(cpuid);				\
@@ -173,7 +188,8 @@
 
 	sc = device_get_softc(dev);
 	sc->dieing = 0;
-	TAILQ_INIT(&sc->sessions);
+	TAILQ_INIT(&sc->free_sessions);
+	RB_INIT(&sc->sessions);
 	sc->sid = 1;
 
 	sc->cid = crypto_get_driverid(dev, CRYPTOCAP_F_HARDWARE |
@@ -222,17 +238,15 @@
 	sc = device_get_softc(dev);
 
 	rw_wlock(&sc->lock);
-	TAILQ_FOREACH(ses, &sc->sessions, next) {
-		if (ses->used) {
-			rw_wunlock(&sc->lock);
-			device_printf(dev,
-			    "Cannot detach, sessions still active.\n");
-			return (EBUSY);
-		}
+	if (!RB_EMPTY(&sc->sessions)) {
+		rw_wunlock(&sc->lock);
+		device_printf(dev,
+		    "Cannot detach, sessions still active.\n");
+		return (EBUSY);
 	}
 	sc->dieing = 1;
-	while ((ses = TAILQ_FIRST(&sc->sessions)) != NULL) {
-		TAILQ_REMOVE(&sc->sessions, ses, next);
+	while ((ses = TAILQ_FIRST(&sc->free_sessions)) != NULL) {
+		TAILQ_REMOVE(&sc->free_sessions, ses, next);
 		free(ses, M_AESNI);
 	}
 	rw_wunlock(&sc->lock);
@@ -326,12 +340,9 @@
 		rw_wunlock(&sc->lock);
 		return (EINVAL);
 	}
-	/*
-	 * Free sessions are inserted at the head of the list.  So if the first
-	 * session is used, none are free and we must allocate a new one.
-	 */
-	ses = TAILQ_FIRST(&sc->sessions);
-	if (ses == NULL || ses->used) {
+
+	ses = TAILQ_FIRST(&sc->free_sessions);
+	if (ses == NULL) {
 		ses = malloc(sizeof(*ses), M_AESNI, M_NOWAIT | M_ZERO);
 		if (ses == NULL) {
 			rw_wunlock(&sc->lock);
@@ -339,10 +350,9 @@
 		}
 		ses->id = sc->sid++;
 	} else {
-		TAILQ_REMOVE(&sc->sessions, ses, next);
+		TAILQ_REMOVE(&sc->free_sessions, ses, next);
 	}
-	ses->used = 1;
-	TAILQ_INSERT_TAIL(&sc->sessions, ses, next);
+	RB_INSERT(aesni_session_tree, &sc->sessions, ses);
 	rw_wunlock(&sc->lock);
 
 	if (encini != NULL)
@@ -371,10 +381,10 @@
 	rw_assert(&sc->lock, RA_WLOCKED);
 
 	sid = ses->id;
-	TAILQ_REMOVE(&sc->sessions, ses, next);
+	RB_REMOVE(aesni_session_tree, &sc->sessions, ses);
 	explicit_bzero(ses, sizeof(*ses));
 	ses->id = sid;
-	TAILQ_INSERT_HEAD(&sc->sessions, ses, next);
+	TAILQ_INSERT_HEAD(&sc->free_sessions, ses, next);
 }
 
 static int
@@ -382,15 +392,12 @@
 {
 	struct aesni_softc *sc;
 	struct aesni_session *ses;
-	uint32_t sid;
+	struct aesni_session find;
 
 	sc = device_get_softc(dev);
-	sid = ((uint32_t)tid) & 0xffffffff;
+	find.id = CRYPTO_SESID2LID(tid);
 	rw_wlock(&sc->lock);
-	TAILQ_FOREACH_REVERSE(ses, &sc->sessions, aesni_sessions_head, next) {
-		if (ses->id == sid)
-			break;
-	}
+	ses = RB_FIND(aesni_session_tree, &sc->sessions, &find);
 	if (ses == NULL) {
 		rw_wunlock(&sc->lock);
 		return (EINVAL);
@@ -405,6 +412,7 @@
 {
 	struct aesni_softc *sc;
 	struct aesni_session *ses;
+	struct aesni_session find;
 	struct cryptodesc *crd, *enccrd, *authcrd;
 	int error, needauth;
 
@@ -472,11 +480,9 @@
 		goto out;
 	}
 
+	find.id = CRYPTO_SESID2LID(crp->crp_sid);
 	rw_rlock(&sc->lock);
-	TAILQ_FOREACH_REVERSE(ses, &sc->sessions, aesni_sessions_head, next) {
-		if (ses->id == (crp->crp_sid & 0xffffffff))
-			break;
-	}
+	ses = RB_FIND(aesni_session_tree, &sc->sessions, &find);
 	rw_runlock(&sc->lock);
 	if (ses == NULL) {
 		error = EINVAL;