From efc775b4c8d8ebe3c0674693feba0b2d7eea5511 Mon Sep 17 00:00:00 2001
From: David van Moolenbroek <david@minix3.org>
Date: Tue, 29 Dec 2015 15:37:11 +0000
Subject: [PATCH] libsys: use linked list for free grants

With this change, obtaining an existing free grant is no longer an
operation of O(n) complexity.  As a result, the now-deprecated
getgrant/setgrant part of the grants API also no longer has a
performance advantage.

Change-Id: Ic19308a76924c6242f9784244a6b3600e561e0fe
---
 minix/include/minix/safecopies.h |  4 ++++
 minix/lib/libsys/safecopies.c    | 33 ++++++++++++++++++++++----------
 2 files changed, 27 insertions(+), 10 deletions(-)

diff --git a/minix/include/minix/safecopies.h b/minix/include/minix/safecopies.h
index 1276cc6bf..53580ff3d 100644
--- a/minix/include/minix/safecopies.h
+++ b/minix/include/minix/safecopies.h
@@ -31,6 +31,10 @@ typedef struct {
 			size_t		cp_len;		/* size in bytes */
 			char		cp_reserved[8]; /* future use */
 		} cp_magic;
+		struct {
+			/* (free slot) */
+			int		cp_next;	/* next free or -1 */
+		} cp_free;
 	} cp_u;
 	int cp_seq;					/* sequence number */
 	char cp_reserved[4];				/* future use */
diff --git a/minix/lib/libsys/safecopies.c b/minix/lib/libsys/safecopies.c
index f5b33c223..cec339f6a 100644
--- a/minix/lib/libsys/safecopies.c
+++ b/minix/lib/libsys/safecopies.c
@@ -42,6 +42,7 @@
 static cp_grant_t static_grants[NR_STATIC_GRANTS];
 static cp_grant_t *grants = NULL;
 static int ngrants = 0;
+static int freelist = -1;
 
 static void
 cpf_grow(void)
@@ -78,10 +79,16 @@ cpf_grow(void)
 	 * Make sure new slots are marked unused (CPF_USED is clear).
 	 * Also start with a zero sequence number, for consistency; since the
 	 * grant table is never shrunk, this introduces no issues by itself.
+	 * Finally, form a new free list, in ascending order so that the lowest
+	 * IDs get allocated first.  Both the zeroed sequence number and the
+	 * ascending order are necessary so that the first grant to be
+	 * allocated has a zero ID (see the live update comment below).
 	 */
 	for(g = ngrants; g < new_size; g++) {
 		new_grants[g].cp_flags = 0;
 		new_grants[g].cp_seq = 0;
+		new_grants[g].cp_u.cp_free.cp_next =
+		    (g < new_size - 1) ? (g + 1) : freelist;
 	}
 
 	/* Inform kernel about new size (and possibly new location). */
@@ -92,6 +99,7 @@ cpf_grow(void)
 
 	/* Update internal data. */
 	if(grants && ngrants > 0 && grants != static_grants) free(grants);
+	freelist = ngrants;
 	grants = new_grants;
 	ngrants = new_size;
 }
@@ -105,17 +113,11 @@ cpf_new_grantslot(void)
  */
 	int g;
 
-	/* Find free slot. */
-	for(g = 0; g < ngrants && (grants[g].cp_flags & CPF_USED); g++)
-		;
-
-	assert(g <= ngrants);
-
-	/* No free slot found? */
-	if(g == ngrants) {
+	/* Obtain a free slot. */
+	if ((g = freelist) == -1) {
+		/* Table full - try to make the table larger. */
 		cpf_grow();
-		assert(g <= ngrants); /* ngrants can't shrink. */
-		if(g == ngrants) {
+		if ((g = freelist) == -1) {
 			/* ngrants hasn't increased. */
 			errno = ENOSPC;
 			return -1;
@@ -129,6 +131,9 @@ cpf_new_grantslot(void)
 	assert(g < ngrants);
 	assert(!(grants[g].cp_flags & CPF_USED));
 
+	/* Take the slot off the free list, and return its slot number. */
+	freelist = grants[g].cp_u.cp_free.cp_next;
+
 	return g;
 }
 
@@ -226,6 +231,14 @@ cpf_revoke(cp_grant_id_t grant)
 	else
 		grants[g].cp_seq = 0;
 
+	/*
+	 * Put the grant back on the free list.  The list is single-headed, so
+	 * the last freed grant will be the first to be reused.  Especially
+	 * given the presence of sequence numbers, this is not a problem.
+	 */
+	grants[g].cp_u.cp_free.cp_next = freelist;
+	freelist = g;
+
 	return 0;
 }
 
-- 
2.44.0