ircd/hash.c

   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 }