1 /* hash.c - Manage hashes for cached dns records
2
3 Copyright (C) 2000, 2001 Thomas Moestl
4 Copyright (C) 2003, 2005 Paul A. Rombouts
5
6 This file is part of the pdnsd package.
7
8 pdnsd is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
12
13 pdnsd is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with pdnsd; see the file COPYING. If not, see
20 <http://www.gnu.org/licenses/>.
21 */
22
23 #include <config.h>
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27 #include <ctype.h>
28 #include "hash.h"
29 #include "cache.h"
30 #include "error.h"
31 #include "helpers.h"
32 #include "consts.h"
33
34
35 /* This is not a perfect hash, but I hope it holds. It is designed for 1024 hash
36 * buckets, and hashes strings with case-insensitivity.
37 * It is position-aware in a limited way.
38 * It is exactly seen a two-way hash: because I do not want to exaggerate
39 * the hash buckets (i do have 1024), but I hash strings and string-comparisons
40 * are expensive, I save another 32 bit hash in each hash element that is checked
41 * before the string. The 32 bit hash is also used to order the entries in a hash chain.
42 * I hope not to have all too much collision concentration.
43 *
44 * The ip hash was removed. I don't think it concentrated the collisions too much.
45 * If it does, the hash algorithm needs to be changed, rather than using another
46 * hash.
47 * Some measurements seem to indicate that the hash algorithm is doing reasonable well.
48 */
49
50 dns_hash_ent_t *hash_buckets[HASH_NUM_BUCKETS];
51
52
53 /*
54 * Hash a dns name (length-byte string format) to HASH_SZ bit.
55 * *rhash is set to a long int hash.
56 */
dns_hash(const unsigned char * str,unsigned long * rhash)57 static unsigned dns_hash(const unsigned char *str, unsigned long *rhash)
58 {
59 unsigned s,i,lb,c;
60 unsigned long r;
61 s=0; r=0;
62 i=0;
63 while((lb=str[i])) {
64 s+=lb<<(i%(HASH_SZ-5));
65 r+=((unsigned long)lb)<<(i%(8*sizeof(unsigned long)-7));
66 ++i;
67 do {
68 c=toupper(str[i]);
69 s+=c<<(i%(HASH_SZ-5));
70 r+=((unsigned long)c)<<(i%(8*sizeof(unsigned long)-7));
71 ++i;
72 } while(--lb);
73 }
74 s=(s&HASH_BITMASK)+((s&(~HASH_BITMASK))>>HASH_SZ);
75 s=(s&HASH_BITMASK)+((s&(~HASH_BITMASK))>>HASH_SZ);
76 s &= HASH_BITMASK;
77 #ifdef DEBUG_HASH
78 {
79 unsigned char buf[DNSNAMEBUFSIZE];
80 printf("Diagnostic: hashes for %s: %03x,%04lx\n",rhn2str(str,buf,sizeof(buf)),s,r);
81 }
82 #endif
83 if(rhash) *rhash=r;
84 return s;
85 }
86
87 /*
88 * Initialize hash to hold a dns hash table
89 */
90 /* This is now defined as an inline function in hash.h */
91 #if 0
92 void mk_dns_hash()
93 {
94 int i;
95 for(i=0;i<HASH_NUM_BUCKETS;i++)
96 hash_buckets[i]=NULL;
97 }
98 #endif
99
100 /*
101 Lookup in the hash table for key. If it is found, return the pointer to the cache entry.
102 If no entry is found, return 0.
103 If loc is not NULL, it will used to store information about the location within the hash table
104 This can be used to add an entry with add_dns_hash() or delete the entry with del_dns_hash_ent().
105 */
dns_lookup(const unsigned char * key,dns_hash_loc_t * loc)106 dns_cent_t *dns_lookup(const unsigned char *key, dns_hash_loc_t *loc)
107 {
108 dns_cent_t *retval=NULL;
109 unsigned idx;
110 unsigned long rh;
111 dns_hash_ent_t **hep,*he;
112
113 idx = dns_hash(key,&rh);
114 hep = &hash_buckets[idx];
115 while ((he= *hep) && he->rhash<=rh) {
116 if (he->rhash==rh && rhnicmp(key,he->data->qname)) {
117 retval = he->data;
118 break;
119 }
120 hep = &he->next;
121 }
122 if(loc) {
123 loc->pos = hep;
124 loc->rhash = rh;
125 }
126 return retval;
127 }
128
129 /*
130 Add a cache entry to the hash table.
131
132 loc must contain the location where the the new entry should be inserted
133 (this location can be obtained with dns_lookup).
134
135 add_dns_hash returns 1 on success, or 0 if out of memory.
136 */
add_dns_hash(dns_cent_t * data,dns_hash_loc_t * loc)137 int add_dns_hash(dns_cent_t *data, dns_hash_loc_t *loc)
138 {
139 dns_hash_ent_t *he = malloc(sizeof(dns_hash_ent_t));
140
141 if(!he)
142 return 0;
143
144 he->next = *(loc->pos);
145 he->rhash = loc->rhash;
146 he->data = data;
147 *(loc->pos) = he;
148
149 return 1;
150 }
151
152 /*
153 Delete the hash entry indentified by the location returned by dns_lookup().
154 */
del_dns_hash_ent(dns_hash_loc_t * loc)155 dns_cent_t *del_dns_hash_ent(dns_hash_loc_t *loc)
156 {
157 dns_hash_ent_t *he = *(loc->pos);
158 dns_cent_t *data;
159
160 *(loc->pos) = he->next;
161 data = he->data;
162 free(he);
163 return data;
164 }
165
166 /*
167 * Delete the first entry indexed by key from the hash. Returns the data field or NULL.
168 * Since two cents are not allowed to be for the same host name, there will be only one.
169 */
del_dns_hash(const unsigned char * key)170 dns_cent_t *del_dns_hash(const unsigned char *key)
171 {
172 unsigned idx;
173 unsigned long rh;
174 dns_hash_ent_t **hep,*he;
175 dns_cent_t *data;
176
177 idx = dns_hash(key,&rh);
178 hep = &hash_buckets[idx];
179 while ((he= *hep) && he->rhash<=rh) {
180 if (he->rhash==rh && rhnicmp(key,he->data->qname)) {
181 *hep = he->next;
182 data = he->data;
183 free(he);
184 return data;
185 }
186 hep = &he->next;
187 }
188 return NULL; /* not found */
189 }
190
191
192 /*
193 * Delete all entries in a hash bucket.
194 */
free_dns_hash_bucket(int i)195 void free_dns_hash_bucket(int i)
196 {
197 dns_hash_ent_t *he,*hen;
198
199 he=hash_buckets[i];
200 hash_buckets[i]=NULL;
201 while (he) {
202 hen=he->next;
203 del_cent(he->data);
204 free(he);
205 he=hen;
206 }
207 }
208
209 /*
210 * Delete all entries in a hash bucket whose names match those in
211 * an include/exclude list.
212 */
free_dns_hash_selected(int i,slist_array sla)213 void free_dns_hash_selected(int i, slist_array sla)
214 {
215 dns_hash_ent_t **hep,*he,*hen;
216 int j,m=DA_NEL(sla);
217
218 hep= &hash_buckets[i];
219 he= *hep;
220
221 while (he) {
222 unsigned char *name=he->data->qname;
223 for(j=0;j<m;++j) {
224 slist_t *sl=&DA_INDEX(sla,j);
225 unsigned int nrem,lrem;
226 domain_match(name,sl->domain,&nrem,&lrem);
227 if(!lrem && (!sl->exact || !nrem)) {
228 if(sl->rule==C_INCLUDED)
229 goto delete_entry;
230 else
231 break;
232 }
233 }
234 /* default policy is not to delete */
235 hep= &he->next;
236 he= *hep;
237 continue;
238
239 delete_entry:
240 *hep=hen=he->next;;
241 del_cent(he->data);
242 free(he);
243 he=hen;
244 }
245 }
246
247 /*
248 * Delete the whole hash table, freeing all memory
249 */
free_dns_hash()250 void free_dns_hash()
251 {
252 int i;
253 dns_hash_ent_t *he,*hen;
254 for (i=0;i<HASH_NUM_BUCKETS;i++) {
255 he=hash_buckets[i];
256 hash_buckets[i]=NULL;
257 while (he) {
258 hen=he->next;
259 del_cent(he->data);
260 free(he);
261 he=hen;
262 }
263 }
264 }
265
266 /*
267 * The following functions are for iterating over the hash.
268 * fetch_first returns the data field of the first element (or NULL if there is none), and fills pos
269 * for subsequent calls of fetch_next.
270 * fetch_next returns the data field of the element after the element that was returned by the last
271 * call with the same position argument (or NULL if there is none)
272 *
273 * Note that these are designed so that you may actually delete the elements you retrieved from the hash.
274 */
fetch_first(dns_hash_pos_t * pos)275 dns_cent_t *fetch_first(dns_hash_pos_t *pos)
276 {
277 int i;
278 for (i=0;i<HASH_NUM_BUCKETS;i++) {
279 dns_hash_ent_t *he=hash_buckets[i];
280 if (he) {
281 pos->bucket=i;
282 pos->ent=he->next;
283 return he->data;
284 }
285 }
286 return NULL;
287 }
288
fetch_next(dns_hash_pos_t * pos)289 dns_cent_t *fetch_next(dns_hash_pos_t *pos)
290 {
291 dns_hash_ent_t *he=pos->ent;
292 int i;
293 if (he) {
294 pos->ent=he->next;
295 return he->data;
296 }
297
298 for (i=pos->bucket+1;i<HASH_NUM_BUCKETS;i++) {
299 he=hash_buckets[i];
300 if (he) {
301 pos->bucket=i;
302 pos->ent=he->next;
303 return he->data;
304 }
305 }
306 return NULL;
307 }
308
309 #ifdef DEBUG_HASH
dumphash()310 void dumphash()
311 {
312 if(debug_p) {
313 int i, j;
314 dns_hash_ent_t *he;
315
316 for (i=0; i<HASH_NUM_BUCKETS; i++) {
317 for (j=0, he=hash_buckets[i]; he; he=he->next, j++) ;
318 DEBUG_MSG("bucket %d: %d entries\n", i, j);
319 }
320 }
321 }
322 #endif
323