diff --git a/utils/gssd/gssd.h b/utils/gssd/gssd.h
index ae0355bb..1e8c58d4 100644
--- a/utils/gssd/gssd.h
+++ b/utils/gssd/gssd.h
@@ -62,7 +62,6 @@ extern int			root_uses_machine_creds;
 extern unsigned int 		context_timeout;
 extern unsigned int rpc_timeout;
 extern char			*preferred_realm;
-extern pthread_mutex_t ple_lock;
 
 struct clnt_info {
 	TAILQ_ENTRY(clnt_info)	list;
diff --git a/utils/gssd/gssd_proc.c b/utils/gssd/gssd_proc.c
index 05c1da64..addac318 100644
--- a/utils/gssd/gssd_proc.c
+++ b/utils/gssd/gssd_proc.c
@@ -548,7 +548,7 @@ krb5_use_machine_creds(struct clnt_info *clp, uid_t uid,
 		uid, tgtname);
 
 	do {
-		gssd_refresh_krb5_machine_credential(clp->servername, NULL,
+		gssd_refresh_krb5_machine_credential(clp->servername,
 						     service, srchost);
 	/*
 	 * Get a list of credential cache names and try each
diff --git a/utils/gssd/krb5_util.c b/utils/gssd/krb5_util.c
index b1e48241..7908c10f 100644
--- a/utils/gssd/krb5_util.c
+++ b/utils/gssd/krb5_util.c
@@ -130,9 +130,28 @@
 #include "gss_util.h"
 #include "krb5_util.h"
 
+/*
+ * List of principals from our keytab that we
+ * will try to use to obtain credentials
+ * (known as a principal list entry (ple))
+ */
+struct gssd_k5_kt_princ {
+	struct gssd_k5_kt_princ *next;
+	// Only protect against deletion, not modification
+	int refcount;
+	// Only set during creation in new_ple()
+	krb5_principal princ;
+	char *realm;
+	// Modified during usage by gssd_get_single_krb5_cred()
+	char *ccname;
+	krb5_timestamp endtime;
+};
+
+
 /* Global list of principals/cache file names for machine credentials */
-struct gssd_k5_kt_princ *gssd_k5_kt_princ_list = NULL;
-pthread_mutex_t ple_lock = PTHREAD_MUTEX_INITIALIZER;
+static struct gssd_k5_kt_princ *gssd_k5_kt_princ_list = NULL;
+/* This mutex protects list modification & ple->ccname */
+static pthread_mutex_t ple_lock = PTHREAD_MUTEX_INITIALIZER;
 
 #ifdef HAVE_SET_ALLOWABLE_ENCTYPES
 int limit_to_legacy_enctypes = 0;
@@ -150,6 +169,18 @@ static int gssd_get_single_krb5_cred(krb5_context context,
 static int query_krb5_ccache(const char* cred_cache, char **ret_princname,
 		char **ret_realm);
 
+static void release_ple(krb5_context context, struct gssd_k5_kt_princ *ple)
+{
+	if (--ple->refcount)
+		return;
+
+	printerr(3, "freeing cached principal (ccname=%s, realm=%s)\n", ple->ccname, ple->realm);
+	krb5_free_principal(context, ple->princ);
+	free(ple->ccname);
+	free(ple->realm);
+	free(ple);
+}
+
 /*
  * Called from the scandir function to weed out potential krb5
  * credentials cache files
@@ -377,12 +408,15 @@ gssd_get_single_krb5_cred(krb5_context context,
 	 * 300 because clock skew must be within 300sec for kerberos
 	 */
 	now += 300;
+	pthread_mutex_lock(&ple_lock);
 	if (ple->ccname && ple->endtime > now && !nocache) {
 		printerr(3, "INFO: Credentials in CC '%s' are good until %d\n",
 			 ple->ccname, ple->endtime);
 		code = 0;
+		pthread_mutex_unlock(&ple_lock);
 		goto out;
 	}
+	pthread_mutex_unlock(&ple_lock);
 
 	if ((code = krb5_kt_get_name(context, kt, kt_name, BUFSIZ))) {
 		printerr(0, "ERROR: Unable to get keytab name in "
@@ -435,6 +469,7 @@ gssd_get_single_krb5_cred(krb5_context context,
 	 * Initialize cache file which we're going to be using
 	 */
 
+	pthread_mutex_lock(&ple_lock);
 	if (use_memcache)
 	    cache_type = "MEMORY";
 	else
@@ -444,15 +479,18 @@ gssd_get_single_krb5_cred(krb5_context context,
 		ccachesearch[0], GSSD_DEFAULT_CRED_PREFIX,
 		GSSD_DEFAULT_MACHINE_CRED_SUFFIX, ple->realm);
 	ple->endtime = my_creds.times.endtime;
-	if (ple->ccname != NULL)
+	if (ple->ccname == NULL || strcmp(ple->ccname, cc_name) != 0) {
 		free(ple->ccname);
-	ple->ccname = strdup(cc_name);
-	if (ple->ccname == NULL) {
-		printerr(0, "ERROR: no storage to duplicate credentials "
-			    "cache name '%s'\n", cc_name);
-		code = ENOMEM;
-		goto out;
+		ple->ccname = strdup(cc_name);
+		if (ple->ccname == NULL) {
+			printerr(0, "ERROR: no storage to duplicate credentials "
+				    "cache name '%s'\n", cc_name);
+			code = ENOMEM;
+			pthread_mutex_unlock(&ple_lock);
+			goto out;
+		}
 	}
+	pthread_mutex_unlock(&ple_lock);
 	if ((code = krb5_cc_resolve(context, cc_name, &ccache))) {
 		k5err = gssd_k5_err_msg(context, code);
 		printerr(0, "ERROR: %s while opening credential cache '%s'\n",
@@ -490,6 +528,7 @@ gssd_get_single_krb5_cred(krb5_context context,
 
 /*
  * Given a principal, find a matching ple structure
+ * Called with mutex held
  */
 static struct gssd_k5_kt_princ *
 find_ple_by_princ(krb5_context context, krb5_principal princ)
@@ -506,6 +545,7 @@ find_ple_by_princ(krb5_context context, krb5_principal princ)
 
 /*
  * Create, initialize, and add a new ple structure to the global list
+ * Called with mutex held
  */
 static struct gssd_k5_kt_princ *
 new_ple(krb5_context context, krb5_principal princ)
@@ -557,6 +597,7 @@ new_ple(krb5_context context, krb5_principal princ)
 			p->next = ple;
 	}
 
+	ple->refcount = 1;
 	return ple;
 outerr:
 	if (ple) {
@@ -575,13 +616,14 @@ get_ple_by_princ(krb5_context context, krb5_principal princ)
 {
 	struct gssd_k5_kt_princ *ple;
 
-	/* Need to serialize list if we ever become multi-threaded! */
-
 	pthread_mutex_lock(&ple_lock);
 	ple = find_ple_by_princ(context, princ);
 	if (ple == NULL) {
 		ple = new_ple(context, princ);
 	}
+	if (ple != NULL) {
+		ple->refcount++;
+	}
 	pthread_mutex_unlock(&ple_lock);
 
 	return ple;
@@ -746,6 +788,8 @@ gssd_search_krb5_keytab(krb5_context context, krb5_keytab kt,
 				retval = ENOMEM;
 				k5_free_kt_entry(context, kte);
 			} else {
+				release_ple(context, ple);
+				ple = NULL;
 				retval = 0;
 				*found = 1;
 			}
@@ -1078,6 +1122,93 @@ err_cache:
 	return (*ret_princname && *ret_realm);
 }
 
+/*
+ * Obtain (or refresh if necessary) Kerberos machine credentials
+ * If a ple is passed in, it's reference will be released
+ */
+static int
+gssd_refresh_krb5_machine_credential_internal(char *hostname,
+				     struct gssd_k5_kt_princ *ple,
+				     char *service, char *srchost)
+{
+	krb5_error_code code = 0;
+	krb5_context context;
+	krb5_keytab kt = NULL;;
+	int retval = 0;
+	char *k5err = NULL;
+	const char *svcnames[] = { "$", "root", "nfs", "host", NULL };
+
+	printerr(2, "%s: hostname=%s ple=%p service=%s srchost=%s\n",
+		__func__, hostname, ple, service, srchost);
+
+	/*
+	 * If a specific service name was specified, use it.
+	 * Otherwise, use the default list.
+	 */
+	if (service != NULL && strcmp(service, "*") != 0) {
+		svcnames[0] = service;
+		svcnames[1] = NULL;
+	}
+	if (hostname == NULL && ple == NULL)
+		return EINVAL;
+
+	code = krb5_init_context(&context);
+	if (code) {
+		k5err = gssd_k5_err_msg(NULL, code);
+		printerr(0, "ERROR: %s: %s while initializing krb5 context\n",
+			 __func__, k5err);
+		retval = code;
+		goto out;
+	}
+
+	if ((code = krb5_kt_resolve(context, keytabfile, &kt))) {
+		k5err = gssd_k5_err_msg(context, code);
+		printerr(0, "ERROR: %s: %s while resolving keytab '%s'\n",
+			 __func__, k5err, keytabfile);
+		goto out_free_context;
+	}
+
+	if (ple == NULL) {
+		krb5_keytab_entry kte;
+
+		code = find_keytab_entry(context, kt, srchost, hostname,
+					 &kte, svcnames);
+		if (code) {
+			printerr(0, "ERROR: %s: no usable keytab entry found "
+				 "in keytab %s for connection with host %s\n",
+				 __FUNCTION__, keytabfile, hostname);
+			retval = code;
+			goto out_free_kt;
+		}
+
+		ple = get_ple_by_princ(context, kte.principal);
+		k5_free_kt_entry(context, &kte);
+		if (ple == NULL) {
+			char *pname;
+			if ((krb5_unparse_name(context, kte.principal, &pname))) {
+				pname = NULL;
+			}
+			printerr(0, "ERROR: %s: Could not locate or create "
+				 "ple struct for principal %s for connection "
+				 "with host %s\n",
+				 __FUNCTION__, pname ? pname : "<unparsable>",
+				 hostname);
+			if (pname) k5_free_unparsed_name(context, pname);
+			goto out_free_kt;
+		}
+	}
+	retval = gssd_get_single_krb5_cred(context, kt, ple, 0);
+out_free_kt:
+	krb5_kt_close(context, kt);
+out_free_context:
+	if (ple)
+		release_ple(context, ple);
+	krb5_free_context(context);
+out:
+	free(k5err);
+	return retval;
+}
+
 /*==========================*/
 /*===  External routines ===*/
 /*==========================*/
@@ -1171,37 +1302,56 @@ gssd_get_krb5_machine_cred_list(char ***list)
 		goto out;
 	}
 
-	/* Need to serialize list if we ever become multi-threaded! */
-
+	pthread_mutex_lock(&ple_lock);
 	for (ple = gssd_k5_kt_princ_list; ple; ple = ple->next) {
-		if (ple->ccname) {
-			/* Make sure cred is up-to-date before returning it */
-			retval = gssd_refresh_krb5_machine_credential(NULL, ple,
-								      NULL, NULL);
-			if (retval)
-				continue;
-			if (i + 1 > listsize) {
-				listsize += listinc;
-				l = (char **)
-					realloc(l, listsize * sizeof(char *));
-				if (l == NULL) {
-					retval = ENOMEM;
-					goto out;
-				}
-			}
-			if ((l[i++] = strdup(ple->ccname)) == NULL) {
+		if (!ple->ccname)
+			continue;
+
+		/* Take advantage of the fact we only remove the ple
+		 * from the list during shutdown. If it's modified
+		 * concurrently at worst we'll just miss a new entry
+		 * before the current ple
+		 *
+		 * gssd_refresh_krb5_machine_credential_internal() will
+		 * release the ple refcount
+		 */
+		ple->refcount++;
+		pthread_mutex_unlock(&ple_lock);
+		/* Make sure cred is up-to-date before returning it */
+		retval = gssd_refresh_krb5_machine_credential_internal(NULL, ple,
+								       NULL, NULL);
+		pthread_mutex_lock(&ple_lock);
+		if (gssd_k5_kt_princ_list == NULL) {
+			/* Looks like we did shutdown... abort */
+			l[i] = NULL;
+			gssd_free_krb5_machine_cred_list(l);
+			retval = ENOMEM;
+			goto out_lock;
+		}
+		if (retval)
+			continue;
+		if (i + 1 > listsize) {
+			listsize += listinc;
+			l = (char **)
+				realloc(l, listsize * sizeof(char *));
+			if (l == NULL) {
 				retval = ENOMEM;
-				goto out;
+				goto out_lock;
 			}
 		}
+		if ((l[i++] = strdup(ple->ccname)) == NULL) {
+			retval = ENOMEM;
+			goto out_lock;
+		}
 	}
 	if (i > 0) {
 		l[i] = NULL;
 		*list = l;
 		retval = 0;
-		goto out;
 	} else
 		free((void *)l);
+out_lock:
+	pthread_mutex_unlock(&ple_lock);
   out:
 	return retval;
 }
@@ -1266,10 +1416,7 @@ gssd_destroy_krb5_principals(int destroy_machine_creds)
 			}
 		}
 
-		krb5_free_principal(context, ple->princ);
-		free(ple->ccname);
-		free(ple->realm);
-		free(ple);
+		release_ple(context, ple);
 	}
 	pthread_mutex_unlock(&ple_lock);
 	krb5_free_context(context);
@@ -1280,83 +1427,10 @@ gssd_destroy_krb5_principals(int destroy_machine_creds)
  */
 int
 gssd_refresh_krb5_machine_credential(char *hostname,
-				     struct gssd_k5_kt_princ *ple, 
 				     char *service, char *srchost)
 {
-	krb5_error_code code = 0;
-	krb5_context context;
-	krb5_keytab kt = NULL;;
-	int retval = 0;
-	char *k5err = NULL;
-	const char *svcnames[] = { "$", "root", "nfs", "host", NULL };
-
-	printerr(2, "%s: hostname=%s ple=%p service=%s srchost=%s\n",
-		__func__, hostname, ple, service, srchost);
-
-	/*
-	 * If a specific service name was specified, use it.
-	 * Otherwise, use the default list.
-	 */
-	if (service != NULL && strcmp(service, "*") != 0) {
-		svcnames[0] = service;
-		svcnames[1] = NULL;
-	}
-	if (hostname == NULL && ple == NULL)
-		return EINVAL;
-
-	code = krb5_init_context(&context);
-	if (code) {
-		k5err = gssd_k5_err_msg(NULL, code);
-		printerr(0, "ERROR: %s: %s while initializing krb5 context\n",
-			 __func__, k5err);
-		retval = code;
-		goto out;
-	}
-
-	if ((code = krb5_kt_resolve(context, keytabfile, &kt))) {
-		k5err = gssd_k5_err_msg(context, code);
-		printerr(0, "ERROR: %s: %s while resolving keytab '%s'\n",
-			 __func__, k5err, keytabfile);
-		goto out_free_context;
-	}
-
-	if (ple == NULL) {
-		krb5_keytab_entry kte;
-
-		code = find_keytab_entry(context, kt, srchost, hostname,
-					 &kte, svcnames);
-		if (code) {
-			printerr(0, "ERROR: %s: no usable keytab entry found "
-				 "in keytab %s for connection with host %s\n",
-				 __FUNCTION__, keytabfile, hostname);
-			retval = code;
-			goto out_free_kt;
-		}
-
-		ple = get_ple_by_princ(context, kte.principal);
-		k5_free_kt_entry(context, &kte);
-		if (ple == NULL) {
-			char *pname;
-			if ((krb5_unparse_name(context, kte.principal, &pname))) {
-				pname = NULL;
-			}
-			printerr(0, "ERROR: %s: Could not locate or create "
-				 "ple struct for principal %s for connection "
-				 "with host %s\n",
-				 __FUNCTION__, pname ? pname : "<unparsable>",
-				 hostname);
-			if (pname) k5_free_unparsed_name(context, pname);
-			goto out_free_kt;
-		}
-	}
-	retval = gssd_get_single_krb5_cred(context, kt, ple, 0);
-out_free_kt:
-	krb5_kt_close(context, kt);
-out_free_context:
-	krb5_free_context(context);
-out:
-	free(k5err);
-	return retval;
+    return gssd_refresh_krb5_machine_credential_internal(hostname, NULL,
+							 service, srchost);
 }
 
 /*
diff --git a/utils/gssd/krb5_util.h b/utils/gssd/krb5_util.h
index e127cc84..2415205a 100644
--- a/utils/gssd/krb5_util.h
+++ b/utils/gssd/krb5_util.h
@@ -9,19 +9,6 @@
 #include "gss_oids.h"
 #endif
 
-/*
- * List of principals from our keytab that we
- * will try to use to obtain credentials
- * (known as a principal list entry (ple))
- */
-struct gssd_k5_kt_princ {
-	struct gssd_k5_kt_princ *next;
-	krb5_principal princ;
-	char *ccname;
-	char *realm;
-	krb5_timestamp endtime;
-};
-
 
 int gssd_setup_krb5_user_gss_ccache(uid_t uid, char *servername,
 				     char *dirname);
@@ -29,7 +16,6 @@ int  gssd_get_krb5_machine_cred_list(char ***list);
 void gssd_free_krb5_machine_cred_list(char **list);
 void gssd_destroy_krb5_principals(int destroy_machine_creds);
 int  gssd_refresh_krb5_machine_credential(char *hostname,
-					  struct gssd_k5_kt_princ *ple, 
 					  char *service, char *srchost);
 char *gssd_k5_err_msg(krb5_context context, krb5_error_code code);
 void gssd_k5_get_default_realm(char **def_realm);
