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
entry_size(const krb5_data * req,const krb5_data * rep)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 *
insert_entry(krb5_context context,krb5_data * req,krb5_data * rep,krb5_timestamp time)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
discard_entry(krb5_context context,struct entry * entry)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
kdc_init_lookaside(krb5_context context)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
kdc_remove_lookaside(krb5_context kcontext,krb5_data * req_packet)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
kdc_check_lookaside(krb5_context kcontext,krb5_data * req_packet,krb5_data ** reply_packet_out)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
kdc_insert_lookaside(krb5_context kcontext,krb5_data * req_packet,krb5_data * reply_packet)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
kdc_free_lookaside(krb5_context kcontext)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