1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* lib/krb5/rcache/memrcache.c - in-memory replay cache implementation */
3 /*
4 * Copyright (C) 2019 by the Massachusetts Institute of Technology.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
24 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30 * OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #include "k5-int.h"
34 #include "k5-queue.h"
35 #include "k5-hashtab.h"
36 #include "memrcache.h"
37
38 struct entry {
39 K5_TAILQ_ENTRY(entry) links;
40 krb5_timestamp timestamp;
41 krb5_data tag;
42 };
43
44 K5_LIST_HEAD(entry_list, entry);
45 K5_TAILQ_HEAD(entry_queue, entry);
46
47 struct k5_memrcache_st {
48 struct k5_hashtab *hash_table;
49 struct entry_queue expiration_queue;
50 };
51
52 static krb5_error_code
insert_entry(krb5_context context,k5_memrcache mrc,const krb5_data * tag,krb5_timestamp now)53 insert_entry(krb5_context context, k5_memrcache mrc, const krb5_data *tag,
54 krb5_timestamp now)
55 {
56 krb5_error_code ret;
57 struct entry *entry = NULL;
58
59 entry = calloc(1, sizeof(*entry));
60 if (entry == NULL)
61 return ENOMEM;
62 entry->timestamp = now;
63
64 ret = krb5int_copy_data_contents(context, tag, &entry->tag);
65 if (ret)
66 goto error;
67
68 ret = k5_hashtab_add(mrc->hash_table, entry->tag.data, entry->tag.length,
69 entry);
70 if (ret)
71 goto error;
72 K5_TAILQ_INSERT_TAIL(&mrc->expiration_queue, entry, links);
73
74 return 0;
75
76 error:
77 if (entry != NULL) {
78 krb5_free_data_contents(context, &entry->tag);
79 free(entry);
80 }
81 return ret;
82 }
83
84
85 /* Remove entry from its hash bucket and the expiration queue, and free it. */
86 static void
discard_entry(krb5_context context,k5_memrcache mrc,struct entry * entry)87 discard_entry(krb5_context context, k5_memrcache mrc, struct entry *entry)
88 {
89 k5_hashtab_remove(mrc->hash_table, entry->tag.data, entry->tag.length);
90 K5_TAILQ_REMOVE(&mrc->expiration_queue, entry, links);
91 krb5_free_data_contents(context, &entry->tag);
92 free(entry);
93 }
94
95 /* Initialize the lookaside cache structures and randomize the hash seed. */
96 krb5_error_code
k5_memrcache_create(krb5_context context,k5_memrcache * mrc_out)97 k5_memrcache_create(krb5_context context, k5_memrcache *mrc_out)
98 {
99 krb5_error_code ret;
100 k5_memrcache mrc;
101 uint8_t seed[K5_HASH_SEED_LEN];
102 krb5_data seed_data = make_data(seed, sizeof(seed));
103
104 *mrc_out = NULL;
105
106 ret = krb5_c_random_make_octets(context, &seed_data);
107 if (ret)
108 return ret;
109
110 mrc = calloc(1, sizeof(*mrc));
111 if (mrc == NULL)
112 return ENOMEM;
113 ret = k5_hashtab_create(seed, 64, &mrc->hash_table);
114 if (ret) {
115 free(mrc);
116 return ret;
117 }
118 K5_TAILQ_INIT(&mrc->expiration_queue);
119
120 *mrc_out = mrc;
121 return 0;
122 }
123
124 krb5_error_code
k5_memrcache_store(krb5_context context,k5_memrcache mrc,const krb5_data * tag)125 k5_memrcache_store(krb5_context context, k5_memrcache mrc,
126 const krb5_data *tag)
127 {
128 krb5_error_code ret;
129 krb5_timestamp now;
130 struct entry *e, *next;
131
132 ret = krb5_timeofday(context, &now);
133 if (ret)
134 return ret;
135
136 /* Check if we already have a matching entry. */
137 e = k5_hashtab_get(mrc->hash_table, tag->data, tag->length);
138 if (e != NULL)
139 return KRB5KRB_AP_ERR_REPEAT;
140
141 /* Discard stale entries. */
142 K5_TAILQ_FOREACH_SAFE(e, &mrc->expiration_queue, links, next) {
143 if (!ts_after(now, ts_incr(e->timestamp, context->clockskew)))
144 break;
145 discard_entry(context, mrc, e);
146 }
147
148 /* Add the new entry. */
149 return insert_entry(context, mrc, tag, now);
150 }
151
152 /* Free all entries in the lookaside cache. */
153 void
k5_memrcache_free(krb5_context context,k5_memrcache mrc)154 k5_memrcache_free(krb5_context context, k5_memrcache mrc)
155 {
156 struct entry *e, *next;
157
158 if (mrc == NULL)
159 return;
160 K5_TAILQ_FOREACH_SAFE(e, &mrc->expiration_queue, links, next) {
161 discard_entry(context, mrc, e);
162 }
163 k5_hashtab_free(mrc->hash_table);
164 free(mrc);
165 }
166