[30272] in CVS-changelog-for-Kerberos-V5
krb5 commit: Use a hash table for MEMORY ccache resolution
daemon@ATHENA.MIT.EDU (Greg Hudson)
Wed Aug 22 13:51:37 2018
Date: Wed, 22 Aug 2018 13:49:25 -0400
From: Greg Hudson <ghudson@mit.edu>
Message-Id: <201808221749.w7MHnPVJ013818@drugstore.mit.edu>
To: cvs-krb5@mit.edu
Reply-To: krbdev@mit.edu
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: cvs-krb5-bounces@mit.edu
https://github.com/krb5/krb5/commit/088ba228acce4fd55bbb7c30122fe2703b8beeb8
commit 088ba228acce4fd55bbb7c30122fe2703b8beeb8
Author: Greg Hudson <ghudson@mit.edu>
Date: Sat Aug 4 23:55:18 2018 -0400
Use a hash table for MEMORY ccache resolution
In cc_memory.c, replace the linked list of caches with a hash table,
for better performance with large numbers of memory caches.
ticket: 8722 (new)
src/lib/krb5/ccache/cc_memory.c | 77 +++++++++++++++++----------------------
1 files changed, 34 insertions(+), 43 deletions(-)
diff --git a/src/lib/krb5/ccache/cc_memory.c b/src/lib/krb5/ccache/cc_memory.c
index cfd5c63..114ef69 100644
--- a/src/lib/krb5/ccache/cc_memory.c
+++ b/src/lib/krb5/ccache/cc_memory.c
@@ -26,6 +26,7 @@
#include "cc-int.h"
#include "../krb/int-proto.h"
+#include "k5-hashtab.h"
#include <errno.h>
static krb5_error_code KRB5_CALLCONV krb5_mcc_close
@@ -118,12 +119,6 @@ typedef struct _krb5_mcc_data {
int generation; /* Incremented at each initialize */
} krb5_mcc_data;
-/* List of memory caches. */
-typedef struct krb5_mcc_list_node {
- struct krb5_mcc_list_node *next;
- krb5_mcc_data *cache;
-} krb5_mcc_list_node;
-
/* Iterator over credentials in a memory cache. */
struct mcc_cursor {
int generation;
@@ -136,10 +131,27 @@ struct krb5_mcc_ptcursor_data {
};
k5_cc_mutex krb5int_mcc_mutex = K5_CC_MUTEX_PARTIAL_INITIALIZER;
-static krb5_mcc_list_node *mcc_head = 0;
+static struct k5_hashtab *mcc_hashtab = NULL;
static void update_mcc_change_time(krb5_mcc_data *);
+/* Ensure that mcc_hashtab is initialized. Call with krb5int_mcc_mutex
+ * locked. */
+static krb5_error_code
+init_table(krb5_context context)
+{
+ krb5_error_code ret;
+ uint8_t seed[K5_HASH_SEED_LEN];
+ krb5_data d = make_data(seed, sizeof(seed));
+
+ if (mcc_hashtab != NULL)
+ return 0;
+ ret = krb5_c_random_make_octets(context, &d);
+ if (ret)
+ return ret;
+ return k5_hashtab_create(seed, 64, &mcc_hashtab);
+}
+
/* Remove creds from d, invalidate any existing cursors, and unset the client
* principal. The caller is responsible for locking. */
static void
@@ -230,21 +242,13 @@ krb5_mcc_close(krb5_context context, krb5_ccache id)
krb5_error_code KRB5_CALLCONV
krb5_mcc_destroy(krb5_context context, krb5_ccache id)
{
- krb5_mcc_list_node **curr, *node;
krb5_mcc_data *d = id->data;
krb5_boolean removed_from_table = FALSE;
+ /* Remove this node from the table if it is still present. */
k5_cc_mutex_lock(context, &krb5int_mcc_mutex);
-
- for (curr = &mcc_head; *curr; curr = &(*curr)->next) {
- if ((*curr)->cache == d) {
- node = *curr;
- *curr = node->next;
- free(node);
- removed_from_table = TRUE;
- break;
- }
- }
+ if (k5_hashtab_remove(mcc_hashtab, d->name, strlen(d->name)))
+ removed_from_table = TRUE;
k5_cc_mutex_unlock(context, &krb5int_mcc_mutex);
/* Empty the cache and remove the reference for the table slot. There will
@@ -289,16 +293,13 @@ krb5_mcc_resolve (krb5_context context, krb5_ccache *id, const char *residual)
{
krb5_os_context os_ctx = &context->os_context;
krb5_ccache lid;
- krb5_mcc_list_node *ptr;
krb5_error_code err;
krb5_mcc_data *d;
k5_cc_mutex_lock(context, &krb5int_mcc_mutex);
- for (ptr = mcc_head; ptr; ptr=ptr->next)
- if (!strcmp(ptr->cache->name, residual))
- break;
- if (ptr != NULL) {
- d = ptr->cache;
+ init_table(context);
+ d = k5_hashtab_get(mcc_hashtab, residual, strlen(residual));
+ if (d != NULL) {
k5_cc_mutex_lock(context, &d->lock);
d->refcount++;
k5_cc_mutex_unlock(context, &d->lock);
@@ -438,18 +439,17 @@ krb5_mcc_end_seq_get(krb5_context context, krb5_ccache id, krb5_cc_cursor *curso
}
/*
- * Utility routine: Creates the back-end data for a memory cache, and threads
- * it into the global linked list. Give the new object two references, one for
- * the table slot and one for the caller's handle.
+ * Utility routine: Creates the back-end data for a memory cache, and adds it
+ * to the global table. Give the new object two references, one for the table
+ * slot and one for the caller's handle.
*
- * Call with the global list lock held.
+ * Call with the global table lock held.
*/
static krb5_error_code
new_mcc_data (const char *name, krb5_mcc_data **dataptr)
{
krb5_error_code err;
krb5_mcc_data *d;
- krb5_mcc_list_node *n;
d = malloc(sizeof(krb5_mcc_data));
if (d == NULL)
@@ -476,18 +476,13 @@ new_mcc_data (const char *name, krb5_mcc_data **dataptr)
d->generation = 0;
update_mcc_change_time(d);
- n = malloc(sizeof(krb5_mcc_list_node));
- if (n == NULL) {
+ if (k5_hashtab_add(mcc_hashtab, d->name, strlen(d->name), d) != 0) {
free(d->name);
k5_cc_mutex_destroy(&d->lock);
free(d);
return KRB5_CC_NOMEM;
}
- n->cache = d;
- n->next = mcc_head;
- mcc_head = n;
-
*dataptr = d;
return 0;
}
@@ -522,11 +517,10 @@ krb5_mcc_generate_new (krb5_context context, krb5_ccache *id)
lid->ops = &krb5_mcc_ops;
k5_cc_mutex_lock(context, &krb5int_mcc_mutex);
+ init_table(context);
/* Check for uniqueness with mutex locked to avoid race conditions */
while (1) {
- krb5_mcc_list_node *ptr;
-
err = krb5int_random_string (context, uniquename, sizeof (uniquename));
if (err) {
k5_cc_mutex_unlock(context, &krb5int_mcc_mutex);
@@ -534,12 +528,9 @@ krb5_mcc_generate_new (krb5_context context, krb5_ccache *id)
return err;
}
- for (ptr = mcc_head; ptr; ptr=ptr->next) {
- if (!strcmp(ptr->cache->name, uniquename)) {
- break; /* got a match, loop again */
- }
- }
- if (!ptr) break; /* got to the end without finding a match */
+ if (k5_hashtab_get(mcc_hashtab, uniquename,
+ strlen(uniquename)) == NULL)
+ break;
}
err = new_mcc_data(uniquename, &d);
_______________________________________________
cvs-krb5 mailing list
cvs-krb5@mit.edu
https://mailman.mit.edu/mailman/listinfo/cvs-krb5
