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