]>
Commit | Line | Data |
---|---|---|
189935b1 | 1 | /* |
2 | * IRC - Internet Relay Chat, ircd/hash.c | |
3 | * Copyright (C) 1998 Andrea Cocito, completely rewritten version. | |
4 | * Previous version was Copyright (C) 1991 Darren Reed, the concept | |
5 | * of linked lists for each hash bucket and the move-to-head | |
6 | * optimization has been borrowed from there. | |
7 | * | |
8 | * This program 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 1, or (at your option) | |
11 | * any later version. | |
12 | * | |
13 | * This program 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 this program; if not, write to the Free Software | |
20 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
21 | */ | |
22 | #include "config.h" | |
23 | ||
24 | #include "hash.h" | |
25 | #include "client.h" | |
26 | #include "channel.h" | |
27 | #include "ircd_alloc.h" | |
28 | #include "ircd_chattr.h" | |
29 | #include "ircd_log.h" | |
30 | #include "ircd_reply.h" | |
31 | #include "ircd_string.h" | |
32 | #include "ircd.h" | |
33 | #include "match.h" | |
34 | #include "msg.h" | |
35 | #include "numeric.h" | |
36 | #include "random.h" | |
37 | #include "send.h" | |
38 | #include "struct.h" | |
39 | #include "sys.h" | |
40 | ||
41 | /* #include <assert.h> -- Now using assert in ircd_log.h */ | |
42 | #include <limits.h> | |
43 | #include <stdlib.h> | |
44 | #include <string.h> | |
45 | ||
46 | ||
47 | /** @file | |
48 | * @brief Hash table management. | |
49 | * @version $Id: hash.c,v 1.18 2005/06/27 13:25:51 entrope Exp $ | |
50 | * | |
51 | * This file used to use some very complicated hash function. Now it | |
52 | * uses CRC-32, but effectively remaps each input byte according to a | |
53 | * table initialized at startup. | |
54 | */ | |
55 | ||
56 | /** Hash table for clients. */ | |
57 | static struct Client *clientTable[HASHSIZE]; | |
58 | /** Hash table for channels. */ | |
59 | static struct Channel *channelTable[HASHSIZE]; | |
60 | /** CRC-32 update table. */ | |
61 | static uint32_t crc32hash[256]; | |
62 | ||
63 | /** Initialize the map used by the hash function. */ | |
64 | void init_hash(void) | |
65 | { | |
66 | unsigned int ii, jj, rand, poly; | |
67 | ||
68 | /* First calculate a normal CRC-32 table. */ | |
69 | for (ii = 0, poly = 0xedb88320; ii < 256; ii++) | |
70 | { | |
71 | rand = ii; | |
72 | for (jj = 0; jj < 8; jj++) | |
73 | rand = (rand & 1) ? poly ^ (rand >> 1) : rand >> 1; | |
74 | crc32hash[ii] = rand; | |
75 | } | |
76 | ||
77 | /* Now reorder the hash table. */ | |
78 | for (ii = 0, rand = 0; ii < 256; ii++) | |
79 | { | |
80 | if (!rand) | |
81 | rand = ircrandom(); | |
82 | poly = ii + rand % (256 - ii); | |
83 | jj = crc32hash[ii]; | |
84 | crc32hash[ii] = crc32hash[poly]; | |
85 | crc32hash[poly] = jj; | |
86 | rand >>= 8; | |
87 | } | |
88 | } | |
89 | ||
90 | /** Output type of hash function. */ | |
91 | typedef unsigned int HASHREGS; | |
92 | ||
93 | /** Calculate hash value for a string. | |
94 | * @param[in] n String to hash. | |
95 | * @return Hash value for string. | |
96 | */ | |
97 | static HASHREGS strhash(const char *n) | |
98 | { | |
99 | HASHREGS hash = crc32hash[ToLower(*n++) & 255]; | |
100 | while (*n) | |
101 | hash = (hash >> 8) ^ crc32hash[(hash ^ ToLower(*n++)) & 255]; | |
102 | return hash % HASHSIZE; | |
103 | } | |
104 | ||
105 | /************************** Externally visible functions ********************/ | |
106 | ||
107 | /* Optimization note: in these functions I supposed that the CSE optimization | |
108 | * (Common Subexpression Elimination) does its work decently, this means that | |
109 | * I avoided introducing new variables to do the work myself and I did let | |
110 | * the optimizer play with more free registers, actual tests proved this | |
111 | * solution to be faster than doing things like tmp2=tmp->hnext... and then | |
112 | * use tmp2 myself which would have given less freedom to the optimizer. | |
113 | */ | |
114 | ||
115 | /** Prepend a client to the appropriate hash bucket. | |
116 | * @param[in] cptr Client to add to hash table. | |
117 | * @return Zero. | |
118 | */ | |
119 | int hAddClient(struct Client *cptr) | |
120 | { | |
121 | HASHREGS hashv = strhash(cli_name(cptr)); | |
122 | ||
123 | cli_hnext(cptr) = clientTable[hashv]; | |
124 | clientTable[hashv] = cptr; | |
125 | ||
126 | return 0; | |
127 | } | |
128 | ||
129 | /** Prepend a channel to the appropriate hash bucket. | |
130 | * @param[in] chptr Channel to add to hash table. | |
131 | * @return Zero. | |
132 | */ | |
133 | int hAddChannel(struct Channel *chptr) | |
134 | { | |
135 | HASHREGS hashv = strhash(chptr->chname); | |
136 | ||
137 | chptr->hnext = channelTable[hashv]; | |
138 | channelTable[hashv] = chptr; | |
139 | ||
140 | return 0; | |
141 | } | |
142 | ||
143 | /** Remove a client from its hash bucket. | |
144 | * @param[in] cptr Client to remove from hash table. | |
145 | * @return Zero if the client is found and removed, -1 if not found. | |
146 | */ | |
147 | int hRemClient(struct Client *cptr) | |
148 | { | |
149 | HASHREGS hashv = strhash(cli_name(cptr)); | |
150 | struct Client *tmp = clientTable[hashv]; | |
151 | ||
152 | if (tmp == cptr) { | |
153 | clientTable[hashv] = cli_hnext(cptr); | |
154 | cli_hnext(cptr) = cptr; | |
155 | return 0; | |
156 | } | |
157 | ||
158 | while (tmp) { | |
159 | if (cli_hnext(tmp) == cptr) { | |
160 | cli_hnext(tmp) = cli_hnext(cli_hnext(tmp)); | |
161 | cli_hnext(cptr) = cptr; | |
162 | return 0; | |
163 | } | |
164 | tmp = cli_hnext(tmp); | |
165 | } | |
166 | return -1; | |
167 | } | |
168 | ||
169 | /** Rename a client in the hash table. | |
170 | * @param[in] cptr Client whose nickname is changing. | |
171 | * @param[in] newname New nickname for client. | |
172 | * @return Zero. | |
173 | */ | |
174 | int hChangeClient(struct Client *cptr, const char *newname) | |
175 | { | |
176 | HASHREGS newhash = strhash(newname); | |
177 | ||
178 | assert(0 != cptr); | |
179 | hRemClient(cptr); | |
180 | ||
181 | cli_hnext(cptr) = clientTable[newhash]; | |
182 | clientTable[newhash] = cptr; | |
183 | return 0; | |
184 | } | |
185 | ||
186 | /** Remove a channel from its hash bucket. | |
187 | * @param[in] chptr Channel to remove from hash table. | |
188 | * @return Zero if the channel is found and removed, -1 if not found. | |
189 | */ | |
190 | int hRemChannel(struct Channel *chptr) | |
191 | { | |
192 | HASHREGS hashv = strhash(chptr->chname); | |
193 | struct Channel *tmp = channelTable[hashv]; | |
194 | ||
195 | if (tmp == chptr) { | |
196 | channelTable[hashv] = chptr->hnext; | |
197 | chptr->hnext = chptr; | |
198 | return 0; | |
199 | } | |
200 | ||
201 | while (tmp) { | |
202 | if (tmp->hnext == chptr) { | |
203 | tmp->hnext = tmp->hnext->hnext; | |
204 | chptr->hnext = chptr; | |
205 | return 0; | |
206 | } | |
207 | tmp = tmp->hnext; | |
208 | } | |
209 | ||
210 | return -1; | |
211 | } | |
212 | ||
213 | /** Find a client by name, filtered by status mask. | |
214 | * If a client is found, it is moved to the top of its hash bucket. | |
215 | * @param[in] name Client name to search for. | |
216 | * @param[in] TMask Bitmask of status bits, any of which are needed to match. | |
217 | * @return Matching client, or NULL if none. | |
218 | */ | |
219 | struct Client* hSeekClient(const char *name, int TMask) | |
220 | { | |
221 | HASHREGS hashv = strhash(name); | |
222 | struct Client *cptr = clientTable[hashv]; | |
223 | ||
224 | if (cptr) { | |
225 | if (0 == (cli_status(cptr) & TMask) || 0 != ircd_strcmp(name, cli_name(cptr))) { | |
226 | struct Client* prev; | |
227 | while (prev = cptr, cptr = cli_hnext(cptr)) { | |
228 | if ((cli_status(cptr) & TMask) && (0 == ircd_strcmp(name, cli_name(cptr)))) { | |
229 | cli_hnext(prev) = cli_hnext(cptr); | |
230 | cli_hnext(cptr) = clientTable[hashv]; | |
231 | clientTable[hashv] = cptr; | |
232 | break; | |
233 | } | |
234 | } | |
235 | } | |
236 | } | |
237 | return cptr; | |
238 | } | |
239 | ||
240 | /** Find a channel by name. | |
241 | * If a channel is found, it is moved to the top of its hash bucket. | |
242 | * @param[in] name Channel name to search for. | |
243 | * @return Matching channel, or NULL if none. | |
244 | */ | |
245 | struct Channel* hSeekChannel(const char *name) | |
246 | { | |
247 | HASHREGS hashv = strhash(name); | |
248 | struct Channel *chptr = channelTable[hashv]; | |
249 | ||
250 | if (chptr) { | |
251 | if (0 != ircd_strcmp(name, chptr->chname)) { | |
252 | struct Channel* prev; | |
253 | while (prev = chptr, chptr = chptr->hnext) { | |
254 | if (0 == ircd_strcmp(name, chptr->chname)) { | |
255 | prev->hnext = chptr->hnext; | |
256 | chptr->hnext = channelTable[hashv]; | |
257 | channelTable[hashv] = chptr; | |
258 | break; | |
259 | } | |
260 | } | |
261 | } | |
262 | } | |
263 | return chptr; | |
264 | ||
265 | } | |
266 | ||
267 | /* I will add some useful(?) statistics here one of these days, | |
268 | but not for DEBUGMODE: just to let the admins play with it, | |
269 | coders are able to SIGCORE the server and look into what goes | |
270 | on themselves :-) */ | |
271 | ||
272 | /** Report hash table statistics to a client. | |
273 | * @param[in] cptr Client that sent us this message. | |
274 | * @param[in] sptr Client that originated the message. | |
275 | * @param[in] parc Number of arguments. | |
276 | * @param[in] parv Argument array. | |
277 | * @return Zero. | |
278 | */ | |
279 | int m_hash(struct Client *cptr, struct Client *sptr, int parc, char *parv[]) | |
280 | { | |
281 | int max_chain = 0; | |
282 | int buckets = 0; | |
283 | int count = 0; | |
284 | struct Client* cl; | |
285 | struct Channel* ch; | |
286 | int i; | |
287 | ||
288 | sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Hash Table Statistics", sptr); | |
289 | ||
290 | for (i = 0; i < HASHSIZE; ++i) { | |
291 | if ((cl = clientTable[i])) { | |
292 | int len = 0; | |
293 | ++buckets; | |
294 | for ( ; cl; cl = cli_hnext(cl)) | |
295 | ++len; | |
296 | if (len > max_chain) | |
297 | max_chain = len; | |
298 | count += len; | |
299 | } | |
300 | } | |
301 | ||
302 | sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Client: entries: %d buckets: %d " | |
303 | "max chain: %d", sptr, count, buckets, max_chain); | |
304 | ||
305 | buckets = 0; | |
306 | count = 0; | |
307 | max_chain = 0; | |
308 | ||
309 | for (i = 0; i < HASHSIZE; ++i) { | |
310 | if ((ch = channelTable[i])) { | |
311 | int len = 0; | |
312 | ++buckets; | |
313 | for ( ; ch; ch = ch->hnext) | |
314 | ++len; | |
315 | if (len > max_chain) | |
316 | max_chain = len; | |
317 | count += len; | |
318 | } | |
319 | } | |
320 | ||
321 | sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Channel: entries: %d buckets: %d " | |
322 | "max chain: %d", sptr, count, buckets, max_chain); | |
323 | return 0; | |
324 | } | |
325 | ||
326 | /* Nick jupe utilities, these are in a static hash table with entry/bucket | |
327 | ratio of one, collision shift up and roll in a circular fashion, the | |
328 | lowest 12 bits of the hash value are used, deletion is not supported, | |
329 | only addition, test for existence and cleanup of the table are.. */ | |
330 | ||
331 | /** Number of bits in jupe hash value. */ | |
332 | #define JUPEHASHBITS 12 /* 4096 entries, 64 nick jupes allowed */ | |
333 | /** Size of jupe hash table. */ | |
334 | #define JUPEHASHSIZE (1<<JUPEHASHBITS) | |
335 | /** Bitmask to select into jupe hash table. */ | |
336 | #define JUPEHASHMASK (JUPEHASHSIZE-1) | |
337 | /** Maximum number of jupes allowed. */ | |
338 | #define JUPEMAX (1<<(JUPEHASHBITS-6)) | |
339 | ||
340 | /** Hash table for jupes. */ | |
341 | static char jupeTable[JUPEHASHSIZE][NICKLEN + 1]; /* About 40k */ | |
342 | /** Count of jupes. */ | |
343 | static int jupesCount; | |
344 | ||
345 | /** Check whether a nickname is juped. | |
346 | * @param[in] nick Nickname to check. | |
347 | * @return Non-zero of the nickname is juped, zero if not. | |
348 | */ | |
349 | int isNickJuped(const char *nick) | |
350 | { | |
351 | int pos; | |
352 | ||
353 | if (nick && *nick) { | |
354 | for (pos = strhash(nick); (pos &= JUPEHASHMASK), jupeTable[pos][0]; pos++) { | |
355 | if (0 == ircd_strcmp(nick, jupeTable[pos])) | |
356 | return 1; | |
357 | } | |
358 | } | |
359 | return 0; /* A bogus pointer is NOT a juped nick, right ? :) */ | |
360 | } | |
361 | ||
362 | /** Add a comma-separated list of nick jupes. | |
363 | * @param[in] nicks List of nicks to jupe, separated by commas. | |
364 | * @return Zero on success, non-zero on error. | |
365 | */ | |
366 | int addNickJupes(const char *nicks) | |
367 | { | |
368 | static char temp[BUFSIZE + 1]; | |
369 | char* one; | |
370 | char* p; | |
371 | int pos; | |
372 | ||
373 | if (nicks && *nicks) | |
374 | { | |
375 | ircd_strncpy(temp, nicks, BUFSIZE); | |
376 | temp[BUFSIZE] = '\0'; | |
377 | p = NULL; | |
378 | for (one = ircd_strtok(&p, temp, ","); one; one = ircd_strtok(&p, NULL, ",")) | |
379 | { | |
380 | if (!*one) | |
381 | continue; | |
382 | pos = strhash(one); | |
383 | loop: | |
384 | pos &= JUPEHASHMASK; | |
385 | if (!jupeTable[pos][0]) | |
386 | { | |
387 | if (jupesCount == JUPEMAX) | |
388 | return 1; /* Error: Jupe table is full ! */ | |
389 | jupesCount++; | |
390 | ircd_strncpy(jupeTable[pos], one, NICKLEN); | |
391 | jupeTable[pos][NICKLEN] = '\000'; /* Better safe than sorry :) */ | |
392 | continue; | |
393 | } | |
394 | if (0 == ircd_strcmp(one, jupeTable[pos])) | |
395 | continue; | |
396 | ++pos; | |
397 | goto loop; | |
398 | } | |
399 | } | |
400 | return 0; | |
401 | } | |
402 | ||
403 | /** Empty the table of juped nicknames. */ | |
404 | void clearNickJupes(void) | |
405 | { | |
406 | int i; | |
407 | jupesCount = 0; | |
408 | for (i = 0; i < JUPEHASHSIZE; i++) | |
409 | jupeTable[i][0] = '\000'; | |
410 | } | |
411 | ||
412 | /** Report all nick jupes to a user. | |
413 | * @param[in] to Client requesting statistics. | |
414 | * @param[in] sd Stats descriptor for request (ignored). | |
415 | * @param[in] param Extra parameter from user (ignored). | |
416 | */ | |
417 | void | |
418 | stats_nickjupes(struct Client* to, const struct StatDesc* sd, char* param) | |
419 | { | |
420 | int i; | |
421 | for (i = 0; i < JUPEHASHSIZE; i++) | |
422 | if (jupeTable[i][0]) | |
423 | send_reply(to, RPL_STATSJLINE, jupeTable[i]); | |
424 | } | |
425 | ||
426 | /** Send more channels to a client in mid-LIST. | |
427 | * @param[in] cptr Client to send the list to. | |
428 | */ | |
429 | void list_next_channels(struct Client *cptr) | |
430 | { | |
431 | struct ListingArgs *args; | |
432 | struct Channel *chptr; | |
433 | ||
434 | /* Walk consecutive buckets until we hit the end. */ | |
435 | for (args = cli_listing(cptr); args->bucket < HASHSIZE; args->bucket++) | |
436 | { | |
437 | /* Send all the matching channels in the bucket. */ | |
438 | for (chptr = channelTable[args->bucket]; chptr; chptr = chptr->hnext) | |
439 | { | |
440 | if (chptr->users > args->min_users | |
441 | && chptr->users < args->max_users | |
442 | && chptr->creationtime > args->min_time | |
443 | && chptr->creationtime < args->max_time | |
444 | && (!args->wildcard[0] || (args->flags & LISTARG_NEGATEWILDCARD) || | |
445 | (!match(args->wildcard, chptr->chname))) | |
446 | && (!(args->flags & LISTARG_NEGATEWILDCARD) || | |
447 | match(args->wildcard, chptr->chname)) | |
448 | && (!(args->flags & LISTARG_TOPICLIMITS) | |
449 | || (chptr->topic[0] | |
450 | && chptr->topic_time > args->min_topic_time | |
451 | && chptr->topic_time < args->max_topic_time)) | |
452 | && ((args->flags & LISTARG_SHOWSECRET) | |
453 | || ShowChannel(cptr, chptr))) | |
454 | { | |
455 | send_reply(cptr, RPL_LIST, chptr->chname, chptr->users, chptr->topic); | |
456 | } | |
457 | } | |
458 | /* If, at the end of the bucket, client sendq is more than half | |
459 | * full, stop. */ | |
460 | if (MsgQLength(&cli_sendQ(cptr)) > cli_max_sendq(cptr) / 2) | |
461 | break; | |
462 | } | |
463 | ||
464 | /* If we did all buckets, clean the client and send RPL_LISTEND. */ | |
465 | if (args->bucket >= HASHSIZE) | |
466 | { | |
467 | MyFree(cli_listing(cptr)); | |
468 | cli_listing(cptr) = NULL; | |
469 | send_reply(cptr, RPL_LISTEND); | |
470 | } | |
471 | } |