1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* kdc/replay.c - Replay lookaside cache for the KDC, to avoid extra work */ 3 /* 4 * Copyright 1991 by the Massachusetts Institute of Technology. 5 * All Rights Reserved. 6 * 7 * Export of this software from the United States of America may 8 * require a specific license from the United States Government. 9 * It is the responsibility of any person or organization contemplating 10 * export to obtain such a license before exporting. 11 * 12 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and 13 * distribute this software and its documentation for any purpose and 14 * without fee is hereby granted, provided that the above copyright 15 * notice appear in all copies and that both that copyright notice and 16 * this permission notice appear in supporting documentation, and that 17 * the name of M.I.T. not be used in advertising or publicity pertaining 18 * to distribution of the software without specific, written prior 19 * permission. Furthermore if you modify this software you must label 20 * your software as modified software and not distribute it in such a 21 * fashion that it might be confused with the original M.I.T. software. 22 * M.I.T. makes no representations about the suitability of 23 * this software for any purpose. It is provided "as is" without express 24 * or implied warranty. 25 */ 26 27 #include "k5-int.h" 28 #include "k5-queue.h" 29 #include "k5-hashtab.h" 30 #include "kdc_util.h" 31 #include "extern.h" 32 33 #ifndef NOCACHE 34 35 struct entry { 36 K5_TAILQ_ENTRY(entry) links; 37 int num_hits; 38 krb5_timestamp timein; 39 krb5_data req_packet; 40 krb5_data reply_packet; 41 }; 42 43 #ifndef LOOKASIDE_MAX_SIZE 44 #define LOOKASIDE_MAX_SIZE (10 * 1024 * 1024) 45 #endif 46 47 K5_LIST_HEAD(entry_list, entry); 48 K5_TAILQ_HEAD(entry_queue, entry); 49 50 static struct k5_hashtab *hash_table; 51 static struct entry_queue expiration_queue; 52 53 static int hits = 0; 54 static int calls = 0; 55 static int max_hits_per_entry = 0; 56 static int num_entries = 0; 57 static size_t total_size = 0; 58 59 #define STALE_TIME (2*60) /* two minutes */ 60 #define STALE(ptr, now) (ts_after(now, ts_incr((ptr)->timein, STALE_TIME))) 61 62 /* Return the rough memory footprint of an entry containing req and rep. */ 63 static size_t 64 entry_size(const krb5_data *req, const krb5_data *rep) 65 { 66 return sizeof(struct entry) + req->length + 67 ((rep == NULL) ? 0 : rep->length); 68 } 69 70 /* Insert an entry into the cache. */ 71 static struct entry * 72 insert_entry(krb5_context context, krb5_data *req, krb5_data *rep, 73 krb5_timestamp time) 74 { 75 krb5_error_code ret; 76 struct entry *entry; 77 size_t esize = entry_size(req, rep); 78 79 entry = calloc(1, sizeof(*entry)); 80 if (entry == NULL) 81 goto error; 82 entry->timein = time; 83 84 ret = krb5int_copy_data_contents(context, req, &entry->req_packet); 85 if (ret) 86 goto error; 87 88 if (rep != NULL) { 89 ret = krb5int_copy_data_contents(context, rep, &entry->reply_packet); 90 if (ret) 91 goto error; 92 } 93 94 ret = k5_hashtab_add(hash_table, entry->req_packet.data, 95 entry->req_packet.length, entry); 96 if (ret) 97 goto error; 98 K5_TAILQ_INSERT_TAIL(&expiration_queue, entry, links); 99 num_entries++; 100 total_size += esize; 101 102 return entry; 103 104 error: 105 if (entry != NULL) { 106 krb5_free_data_contents(context, &entry->req_packet); 107 krb5_free_data_contents(context, &entry->reply_packet); 108 free(entry); 109 } 110 return NULL; 111 } 112 113 114 /* Remove entry from its hash bucket and the expiration queue, and free it. */ 115 static void 116 discard_entry(krb5_context context, struct entry *entry) 117 { 118 total_size -= entry_size(&entry->req_packet, &entry->reply_packet); 119 num_entries--; 120 k5_hashtab_remove(hash_table, entry->req_packet.data, 121 entry->req_packet.length); 122 K5_TAILQ_REMOVE(&expiration_queue, entry, links); 123 krb5_free_data_contents(context, &entry->req_packet); 124 krb5_free_data_contents(context, &entry->reply_packet); 125 free(entry); 126 } 127 128 /* Initialize the lookaside cache structures and randomize the hash seed. */ 129 krb5_error_code 130 kdc_init_lookaside(krb5_context context) 131 { 132 krb5_error_code ret; 133 uint8_t seed[K5_HASH_SEED_LEN]; 134 krb5_data d = make_data(seed, sizeof(seed)); 135 136 ret = krb5_c_random_make_octets(context, &d); 137 if (ret) 138 return ret; 139 ret = k5_hashtab_create(seed, 8192, &hash_table); 140 if (ret) 141 return ret; 142 K5_TAILQ_INIT(&expiration_queue); 143 return 0; 144 } 145 146 /* Remove the lookaside cache entry for a packet. */ 147 void 148 kdc_remove_lookaside(krb5_context kcontext, krb5_data *req_packet) 149 { 150 struct entry *e; 151 152 e = k5_hashtab_get(hash_table, req_packet->data, req_packet->length); 153 if (e != NULL) 154 discard_entry(kcontext, e); 155 } 156 157 /* 158 * Return true and fill in reply_packet_out if req_packet is in the lookaside 159 * cache; otherwise return false. 160 * 161 * If the request was inserted with a NULL reply_packet to indicate that a 162 * request is still being processed, then return TRUE with reply_packet_out set 163 * to NULL. 164 */ 165 krb5_boolean 166 kdc_check_lookaside(krb5_context kcontext, krb5_data *req_packet, 167 krb5_data **reply_packet_out) 168 { 169 struct entry *e; 170 171 *reply_packet_out = NULL; 172 calls++; 173 174 e = k5_hashtab_get(hash_table, req_packet->data, req_packet->length); 175 if (e == NULL) 176 return FALSE; 177 178 e->num_hits++; 179 hits++; 180 181 /* Leave *reply_packet_out as NULL for an in-progress entry. */ 182 if (e->reply_packet.length == 0) 183 return TRUE; 184 185 return (krb5_copy_data(kcontext, &e->reply_packet, 186 reply_packet_out) == 0); 187 } 188 189 /* 190 * Insert a request and reply into the lookaside cache. Assumes it's not 191 * already there, and can fail silently on memory exhaustion. Also discard old 192 * entries in the cache. 193 * 194 * The reply_packet may be NULL to indicate a request that is still processing. 195 */ 196 void 197 kdc_insert_lookaside(krb5_context kcontext, krb5_data *req_packet, 198 krb5_data *reply_packet) 199 { 200 struct entry *e, *next; 201 krb5_timestamp timenow; 202 size_t esize = entry_size(req_packet, reply_packet); 203 204 if (krb5_timeofday(kcontext, &timenow)) 205 return; 206 207 /* Purge stale entries and limit the total size of the entries. */ 208 K5_TAILQ_FOREACH_SAFE(e, &expiration_queue, links, next) { 209 if (!STALE(e, timenow) && total_size + esize <= LOOKASIDE_MAX_SIZE) 210 break; 211 max_hits_per_entry = max(max_hits_per_entry, e->num_hits); 212 discard_entry(kcontext, e); 213 } 214 215 insert_entry(kcontext, req_packet, reply_packet, timenow); 216 return; 217 } 218 219 /* Free all entries in the lookaside cache. */ 220 void 221 kdc_free_lookaside(krb5_context kcontext) 222 { 223 struct entry *e, *next; 224 225 K5_TAILQ_FOREACH_SAFE(e, &expiration_queue, links, next) { 226 discard_entry(kcontext, e); 227 } 228 k5_hashtab_free(hash_table); 229 } 230 231 #endif /* NOCACHE */ 232