change passwd caches to be 4-way "associative". still primitive, but a

little better than winner take all caching.

1 files changed, 62 insertions, 24 deletions

diff --git a/lib/libc/gen/pwcache.c b/lib/libc/gen/pwcache.c
index 373b0843c04..e65112447ba 100644
--- a/lib/libc/gen/pwcache.c
+++ b/lib/libc/gen/pwcache.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pwcache.c,v 1.10 2015/10/26 15:04:51 tedu Exp $ */
+/*	$OpenBSD: pwcache.c,v 1.11 2015/11/17 17:49:09 tedu Exp $ */
 /*
  * Copyright (c) 1989, 1993
  *	The Regents of the University of California.  All rights reserved.
@@ -35,32 +35,52 @@
 #include <stdio.h>
 #include <string.h>
 
-#define	NCACHE	64			/* power of 2 */
+#define	NCACHE	16			/* power of 2 */
+#define	NLINES	4			/* associativity */
 #define	MASK	(NCACHE - 1)		/* bits to store with */
+#define	IDX(x, i)	((x & MASK) + i * NCACHE)
 
 char *
 user_from_uid(uid_t uid, int nouser)
 {
 	static struct ncache {
 		uid_t	uid;
+		short	noname;
 		char	name[_PW_NAME_LEN + 1];
-	} c_uid[NCACHE];
+	} c_uid[NLINES * NCACHE];
 	static char nbuf[15];		/* 32 bits == 10 digits */
 	struct passwd *pw;
 	struct ncache *cp;
+	unsigned int i;
 
-	cp = c_uid + (uid & MASK);
-	if (cp->uid != uid || !*cp->name) {
-		if ((pw = getpwuid(uid)) == NULL) {
-			if (nouser)
-				return (NULL);
-			(void)snprintf(nbuf, sizeof(nbuf), "%u", uid);
-			return (nbuf);
+	for (i = 0; i < NLINES; i++) {
+		cp = &c_uid[IDX(uid, i)];
+		if (!*cp->name) {
+fillit:
+			cp->uid = uid;
+			if ((pw = getpwuid(uid)) == NULL) {
+				snprintf(cp->name, sizeof(cp->name), "%u", uid);
+				cp->noname = 1;
+			} else {
+				strlcpy(cp->name, pw->pw_name, sizeof(cp->name));
+			}
 		}
-		cp->uid = uid;
-		strlcpy(cp->name, pw->pw_name, sizeof(cp->name));
+		if (cp->uid == uid) {
+			if (nouser && cp->noname)
+				return NULL;
+			return cp->name;
+		}
+	}
+	/* move everybody down a slot */
+	for (i = 0; i < NLINES - 1; i++) {
+		struct ncache *next;
+
+		cp = &c_uid[IDX(uid, i)];
+		next = &c_uid[IDX(uid, i + 1)];
+		memcpy(next, cp, sizeof(*cp));
 	}
-	return (cp->name);
+	cp = &c_uid[IDX(uid, 0)];
+	goto fillit;
 }
 
 char *
@@ -68,22 +88,40 @@ group_from_gid(gid_t gid, int nogroup)
 {
 	static struct ncache {
 		gid_t	gid;
+		short 	noname;
 		char	name[_PW_NAME_LEN + 1];
-	} c_gid[NCACHE];
+	} c_gid[NLINES * NCACHE];
 	static char nbuf[15];		/* 32 bits == 10 digits */
 	struct group *gr;
 	struct ncache *cp;
+	unsigned int i;
 
-	cp = c_gid + (gid & MASK);
-	if (cp->gid != gid || !*cp->name) {
-		if ((gr = getgrgid(gid)) == NULL) {
-			if (nogroup)
-				return (NULL);
-			(void)snprintf(nbuf, sizeof(nbuf), "%u", gid);
-			return (nbuf);
+	for (i = 0; i < NLINES; i++) {
+		cp = &c_gid[IDX(gid, i)];
+		if (!*cp->name) {
+fillit:
+			cp->gid = gid;
+			if ((gr = getgrgid(gid)) == NULL) {
+				snprintf(cp->name, sizeof(cp->name), "%u", gid);
+				cp->noname = 1;
+			} else {
+				strlcpy(cp->name, gr->gr_name, sizeof(cp->name));
+			}
 		}
-		cp->gid = gid;
-		strlcpy(cp->name, gr->gr_name, sizeof(cp->name));
+		if (cp->gid == gid) {
+			if (nogroup && cp->noname)
+				return NULL;
+			return cp->name;
+		}
+	}
+	/* move everybody down a slot */
+	for (i = 0; i < NLINES - 1; i++) {
+		struct ncache *next;
+
+		cp = &c_gid[IDX(gid, i)];
+		next = &c_gid[IDX(gid, i + 1)];
+		memcpy(next, cp, sizeof(*cp));
 	}
-	return (cp->name);
+	cp = &c_gid[IDX(gid, 0)];
+	goto fillit;
 }