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_chattr.h"
  28 #include "ircd_string.h"
  29 #include "ircd.h"
  30 #include "msg.h"
  31 #include "random.h"
  32 #include "send.h"
  33 #include "struct.h"
  34 #include "sys.h"
  35
  36 #include <assert.h>
  37 #include <limits.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41
  42 /** @file
  43  * @brief Hash table management.
  44  * @version $Id$
  45  *
  46  * This file used to use some very complicated hash function.  Now it
  47  * uses CRC-32, but effectively remaps each input byte according to a
  48  * table initialized at startup.
  49  */
  50
  51 /** Hash table for clients. */
  52 static struct Client *clientTable[HASHSIZE];
  53 /** Hash table for channels. */
  54 static struct Channel *channelTable[HASHSIZE];
  55 /** CRC-32 update table. */
  56 static uint32_t crc32hash[256];
  57
  58 /** Initialize the map used by the hash function. */
  59 void init_hash(void)
  60 {
  61   unsigned int ii, jj, rand, poly;
  62
  63   /* First calculate a normal CRC-32 table. */
  64   for (ii = 0, poly = 0xedb88320; ii < 256; ii++)
  65   {
  66     rand = ii;
  67     for (jj = 0; jj < 8; jj++)
  68       rand = (rand & 1) ? poly ^ (rand >> 1) : rand >> 1;
  69     crc32hash[ii] = rand;
  70   }
  71
  72   /* Now reorder the hash table.  To make it case-insensitive, skip
  73    * upper-case letters, and have lower-case letters write to the
  74    * corresponding upper-case character.
  75    */
  76   for (ii = 0, rand = 0; ii < 256; ii++)
  77   {
  78     char ch = ii + CHAR_MIN;
  79     if (ch != ToLower(ch))
  80       continue;
  81     if (!rand)
  82       rand = ircrandom();
  83     poly = ii + rand % (256 - ii);
  84     jj = crc32hash[ii];
  85     crc32hash[ToUpper(ch) - CHAR_MIN] = crc32hash[ii] = crc32hash[poly];
  86     crc32hash[poly] = jj;
  87     rand >>= 8;
  88   }
  89 }
  90
  91 /** Output type of hash function. */
  92 typedef unsigned int HASHREGS;
  93
  94 /** Calculate hash value for a string.
  95  * @param[in] n String to hash.
  96  * @return Hash value for string.
  97  */
  98 static HASHREGS strhash(const char *n)
  99 {
 100   HASHREGS hash = crc32hash[*n++ & 255];
 101   while (*n)
 102     hash = (hash >> 8) ^ crc32hash[(hash ^ *n++) & 255];
 103   return hash % HASHSIZE;
 104 }
 105
 106 /************************** Externally visible functions ********************/
 107
 108 /* Optimization note: in these functions I supposed that the CSE optimization
 109  * (Common Subexpression Elimination) does its work decently, this means that
 110  * I avoided introducing new variables to do the work myself and I did let
 111  * the optimizer play with more free registers, actual tests proved this
 112  * solution to be faster than doing things like tmp2=tmp->hnext... and then
 113  * use tmp2 myself wich would have given less freedom to the optimizer.
 114  */
 115
 116 /** Prepend a client to the appropriate hash bucket.
 117  * @param[in] cptr Client to add to hash table.
 118  * @return Zero.
 119  */
 120 int hAddClient(struct Client *cptr)
 121 {
 122   HASHREGS hashv = strhash(cli_name(cptr));
 123
 124   cli_hnext(cptr) = clientTable[hashv];
 125   clientTable[hashv] = cptr;
 126
 127   return 0;
 128 }
 129
 130 /** Prepend a channel to the appropriate hash bucket.
 131  * @param[in] chptr Channel to add to hash table.
 132  * @return Zero.
 133  */
 134 int hAddChannel(struct Channel *chptr)
 135 {
 136   HASHREGS hashv = strhash(chptr->chname);
 137
 138   chptr->hnext = channelTable[hashv];
 139   channelTable[hashv] = chptr;
 140
 141   return 0;
 142 }
 143
 144 /** Remove a client from its hash bucket.
 145  * @param[in] cptr Client to remove from hash table.
 146  * @return Zero if the client is found and removed, -1 if not found.
 147  */
 148 int hRemClient(struct Client *cptr)
 149 {
 150   HASHREGS hashv = strhash(cli_name(cptr));
 151   struct Client *tmp = clientTable[hashv];
 152
 153   if (tmp == cptr) {
 154     clientTable[hashv] = cli_hnext(cptr);
 155     cli_hnext(cptr) = cptr;
 156     return 0;
 157   }
 158
 159   while (tmp) {
 160     if (cli_hnext(tmp) == cptr) {
 161       cli_hnext(tmp) = cli_hnext(cli_hnext(tmp));
 162       cli_hnext(cptr) = cptr;
 163       return 0;
 164     }
 165     tmp = cli_hnext(tmp);
 166   }
 167   return -1;
 168 }
 169
 170 /** Rename a client in the hash table.
 171  * @param[in] cptr Client whose nickname is changing.
 172  * @param[in] newname New nickname for client.
 173  * @return Zero.
 174  */
 175 int hChangeClient(struct Client *cptr, const char *newname)
 176 {
 177   HASHREGS newhash = strhash(newname);
 178
 179   assert(0 != cptr);
 180   hRemClient(cptr);
 181
 182   cli_hnext(cptr) = clientTable[newhash];
 183   clientTable[newhash] = cptr;
 184   return 0;
 185 }
 186
 187 /** Remove a channel from its hash bucket.
 188  * @param[in] chptr Channel to remove from hash table.
 189  * @return Zero if the channel is found and removed, -1 if not found.
 190  */
 191 int hRemChannel(struct Channel *chptr)
 192 {
 193   HASHREGS hashv = strhash(chptr->chname);
 194   struct Channel *tmp = channelTable[hashv];
 195
 196   if (tmp == chptr) {
 197     channelTable[hashv] = chptr->hnext;
 198     chptr->hnext = chptr;
 199     return 0;
 200   }
 201
 202   while (tmp) {
 203     if (tmp->hnext == chptr) {
 204       tmp->hnext = tmp->hnext->hnext;
 205       chptr->hnext = chptr;
 206       return 0;
 207     }
 208     tmp = tmp->hnext;
 209   }
 210
 211   return -1;
 212 }
 213
 214 /** Find a client by name, filtered by status mask.
 215  * If a client is found, it is moved to the top of its hash bucket.
 216  * @param[in] name Client name to search for.
 217  * @param[in] TMask Bitmask of status bits, any of which are needed to match.
 218  * @return Matching client, or NULL if none.
 219  */
 220 struct Client* hSeekClient(const char *name, int TMask)
 221 {
 222   HASHREGS hashv      = strhash(name);
 223   struct Client *cptr = clientTable[hashv];
 224
 225   if (cptr) {
 226     if (0 == (cli_status(cptr) & TMask) || 0 != ircd_strcmp(name, cli_name(cptr))) {
 227       struct Client* prev;
 228       while (prev = cptr, cptr = cli_hnext(cptr)) {
 229         if ((cli_status(cptr) & TMask) && (0 == ircd_strcmp(name, cli_name(cptr)))) {
 230           cli_hnext(prev) = cli_hnext(cptr);
 231           cli_hnext(cptr) = clientTable[hashv];
 232           clientTable[hashv] = cptr;
 233           break;
 234         }
 235       }
 236     }
 237   }
 238   return cptr;
 239 }
 240
 241 /** Find a channel by name.
 242  * If a channel is found, it is moved to the top of its hash bucket.
 243  * @param[in] name Channel name to search for.
 244  * @return Matching channel, or NULL if none.
 245  */
 246 struct Channel* hSeekChannel(const char *name)
 247 {
 248   HASHREGS hashv = strhash(name);
 249   struct Channel *chptr = channelTable[hashv];
 250
 251   if (chptr) {
 252     if (0 != ircd_strcmp(name, chptr->chname)) {
 253       struct Channel* prev;
 254       while (prev = chptr, chptr = chptr->hnext) {
 255         if (0 == ircd_strcmp(name, chptr->chname)) {
 256           prev->hnext = chptr->hnext;
 257           chptr->hnext = channelTable[hashv];
 258           channelTable[hashv] = chptr;
 259           break;
 260         }
 261       }
 262     }
 263   }
 264   return chptr;
 265
 266 }
 267
 268 /* I will add some useful(?) statistics here one of these days,
 269    but not for DEBUGMODE: just to let the admins play with it,
 270    coders are able to SIGCORE the server and look into what goes
 271    on themselves :-) */
 272
 273 /** Report hash table statistics to a client.
 274  * @param[in] cptr Client that sent us this message.
 275  * @param[in] sptr Client that originated the message.
 276  * @param[in] parc Number of arguments.
 277  * @param[in] parv Argument array.
 278  * @return Zero.
 279  */
 280 int m_hash(struct Client *cptr, struct Client *sptr, int parc, char *parv[])
 281 {
 282   int max_chain = 0;
 283   int buckets   = 0;
 284   int count     = 0;
 285   struct Client*  cl;
 286   struct Channel* ch;
 287   int i;
 288
 289   sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Hash Table Statistics", sptr);
 290
 291   for (i = 0; i < HASHSIZE; ++i) {
 292     if ((cl = clientTable[i])) {
 293       int len = 0;
 294       ++buckets;
 295       for ( ; cl; cl = cli_hnext(cl))
 296         ++len;
 297       if (len > max_chain)
 298         max_chain = len;
 299       count += len;
 300     }
 301   }
 302
 303   sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Client: entries: %d buckets: %d "
 304                 "max chain: %d", sptr, count, buckets, max_chain);
 305
 306   buckets = 0;
 307   count   = 0;
 308   max_chain = 0;
 309
 310   for (i = 0; i < HASHSIZE; ++i) {
 311     if ((ch = channelTable[i])) {
 312       int len = 0;
 313       ++buckets;
 314       for ( ; ch; ch = ch->hnext)
 315         ++len;
 316       if (len > max_chain)
 317         max_chain = len;
 318       count += len;
 319     }
 320   }
 321
 322   sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Channel: entries: %d buckets: %d "
 323                 "max chain: %d", sptr, count, buckets, max_chain);
 324   return 0;
 325 }
 326
 327 /* Nick jupe utilities, these are in a static hash table with entry/bucket
 328    ratio of one, collision shift up and roll in a circular fashion, the
 329    lowest 12 bits of the hash value are used, deletion is not supported,
 330    only addition, test for existence and cleanup of the table are.. */
 331
 332 /** Number of bits in jupe hash value. */
 333 #define JUPEHASHBITS 12         /* 4096 entries, 64 nick jupes allowed */
 334 /** Size of jupe hash table. */
 335 #define JUPEHASHSIZE (1<<JUPEHASHBITS)
 336 /** Bitmask to select into jupe hash table. */
 337 #define JUPEHASHMASK (JUPEHASHSIZE-1)
 338 /** Maximum number of jupes allowed. */
 339 #define JUPEMAX      (1<<(JUPEHASHBITS-6))
 340
 341 /** Hash table for jupes. */
 342 static char jupeTable[JUPEHASHSIZE][NICKLEN + 1];       /* About 40k */
 343 /** Count of jupes. */
 344 static int jupesCount;
 345
 346 /** Check whether a nickname is juped.
 347  * @param[in] nick Nickname to check.
 348  * @return Non-zero of the nickname is juped, zero if not.
 349  */
 350 int isNickJuped(const char *nick)
 351 {
 352   int pos;
 353
 354   if (nick && *nick) {
 355     for (pos = strhash(nick); (pos &= JUPEHASHMASK), jupeTable[pos][0]; pos++) {
 356       if (0 == ircd_strcmp(nick, jupeTable[pos]))
 357         return 1;
 358     }
 359   }
 360   return 0;                     /* A bogus pointer is NOT a juped nick, right ? :) */
 361 }
 362
 363 /** Add a comma-separated list of nick jupes.
 364  * @param[in] nicks List of nicks to jupe, separated by commas.
 365  * @return Zero on success, non-zero on error.
 366  */
 367 int addNickJupes(const char *nicks)
 368 {
 369   static char temp[BUFSIZE + 1];
 370   char* one;
 371   char* p;
 372   int   pos;
 373
 374   if (nicks && *nicks)
 375   {
 376     ircd_strncpy(temp, nicks, BUFSIZE);
 377     temp[BUFSIZE] = '\0';
 378     p = NULL;
 379     for (one = ircd_strtok(&p, temp, ","); one; one = ircd_strtok(&p, NULL, ","))
 380     {
 381       if (!*one)
 382         continue;
 383       pos = strhash(one);
 384 loop:
 385       pos &= JUPEHASHMASK;
 386       if (!jupeTable[pos][0])
 387       {
 388         if (jupesCount == JUPEMAX)
 389           return 1;             /* Error: Jupe table is full ! */
 390         jupesCount++;
 391         ircd_strncpy(jupeTable[pos], one, NICKLEN);
 392         jupeTable[pos][NICKLEN] = '\000';       /* Better safe than sorry :) */
 393         continue;
 394       }
 395       if (0 == ircd_strcmp(one, jupeTable[pos]))
 396         continue;
 397       ++pos;
 398       goto loop;
 399     }
 400   }
 401   return 0;
 402 }
 403
 404 /** Empty the table of juped nicknames. */
 405 void clearNickJupes(void)
 406 {
 407   int i;
 408   jupesCount = 0;
 409   for (i = 0; i < JUPEHASHSIZE; i++)
 410     jupeTable[i][0] = '\000';
 411 }