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 "s_debug.h"
  38 #include "send.h"
  39 #include "struct.h"
  40 #include "sys.h"
  41
  42 /* #include <assert.h> -- Now using assert in ircd_log.h */
  43 #include <limits.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46
  47
  48 /** @file
  49  * @brief Hash table management.
  50  * @version $Id: hash.c 1841 2007-11-05 03:01:34Z entrope $
  51  *
  52  * This file used to use some very complicated hash function.  Now it
  53  * uses CRC-32, but effectively remaps each input byte according to a
  54  * table initialized at startup.
  55  */
  56
  57 /** Hash table for clients. */
  58 static struct Client *clientTable[HASHSIZE];
  59 /** Hash table for channels. */
  60 static struct Channel *channelTable[HASHSIZE];
  61 /** CRC-32 update table. */
  62 static uint32_t crc32hash[256];
  63
  64 /** Initialize the map used by the hash function. */
  65 void init_hash(void)
  66 {
  67   unsigned int ii, jj, rand, poly;
  68
  69   /* First calculate a normal CRC-32 table. */
  70   for (ii = 0, poly = 0xedb88320; ii < 256; ii++)
  71   {
  72     rand = ii;
  73     for (jj = 0; jj < 8; jj++)
  74       rand = (rand & 1) ? poly ^ (rand >> 1) : rand >> 1;
  75     crc32hash[ii] = rand;
  76   }
  77
  78   /* Now reorder the hash table. */
  79   for (ii = 0, rand = 0; ii < 256; ii++)
  80   {
  81     if (!rand)
  82       rand = ircrandom();
  83     poly = ii + rand % (256 - ii);
  84     jj = crc32hash[ii];
  85     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[ToLower(*n++) & 255];
 101   while (*n)
 102     hash = (hash >> 8) ^ crc32hash[(hash ^ ToLower(*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 which 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       for (pos = 0; pos < JUPEHASHSIZE; pos++) {
 357       //if (0 == ircd_strcmp(nick, jupeTable[pos]))
 358       //Debug((DEBUG_DEBUG, "NickJupe match: %s %s %i",jupeTable[pos], nick, match(jupeTable[pos], nick)));
 359       if (0 == match(jupeTable[pos], nick))
 360         return 1;
 361     }
 362   }
 363   return 0;                     /* A bogus pointer is NOT a juped nick, right ? :) */
 364 }
 365
 366 /** Add a comma-separated list of nick jupes.
 367  * @param[in] nicks List of nicks to jupe, separated by commas.
 368  * @return Zero on success, non-zero on error.
 369  */
 370 int addNickJupes(const char *nicks)
 371 {
 372   static char temp[BUFSIZE + 1];
 373   char* one;
 374   char* p;
 375   int   pos;
 376
 377   if (nicks && *nicks)
 378   {
 379     ircd_strncpy(temp, nicks, BUFSIZE);
 380     temp[BUFSIZE] = '\0';
 381     p = NULL;
 382     for (one = ircd_strtok(&p, temp, ","); one; one = ircd_strtok(&p, NULL, ","))
 383     {
 384       if (!*one)
 385         continue;
 386       pos = strhash(one);
 387 loop:
 388       pos &= JUPEHASHMASK;
 389       if (!jupeTable[pos][0])
 390       {
 391         if (jupesCount == JUPEMAX)
 392           return 1;             /* Error: Jupe table is full ! */
 393         jupesCount++;
 394         ircd_strncpy(jupeTable[pos], one, NICKLEN);
 395         jupeTable[pos][NICKLEN] = '\000';       /* Better safe than sorry :) */
 396         continue;
 397       }
 398       if (0 == ircd_strcmp(one, jupeTable[pos]))
 399         continue;
 400       ++pos;
 401       goto loop;
 402     }
 403   }
 404   return 0;
 405 }
 406
 407 /** Empty the table of juped nicknames. */
 408 void clearNickJupes(void)
 409 {
 410   int i;
 411   jupesCount = 0;
 412   for (i = 0; i < JUPEHASHSIZE; i++)
 413     jupeTable[i][0] = '\000';
 414 }
 415
 416 /** Report all nick jupes to a user.
 417  * @param[in] to Client requesting statistics.
 418  * @param[in] sd Stats descriptor for request (ignored).
 419  * @param[in] param Extra parameter from user (ignored).
 420  */
 421 void
 422 stats_nickjupes(struct Client* to, const struct StatDesc* sd, char* param)
 423 {
 424   int i;
 425   for (i = 0; i < JUPEHASHSIZE; i++)
 426     if (jupeTable[i][0])
 427       send_reply(to, RPL_STATSJLINE, jupeTable[i]);
 428 }
 429
 430 /** Send more channels to a client in mid-LIST.
 431  * @param[in] cptr Client to send the list to.
 432  */
 433 void list_next_channels(struct Client *cptr)
 434 {
 435   struct ListingArgs *args;
 436   struct Channel *chptr;
 437
 438   /* Walk consecutive buckets until we hit the end. */
 439   for (args = cli_listing(cptr); args->bucket < HASHSIZE; args->bucket++)
 440   {
 441     /* Send all the matching channels in the bucket. */
 442     for (chptr = channelTable[args->bucket]; chptr; chptr = chptr->hnext)
 443     {
 444       if (chptr->users > args->min_users
 445           && chptr->users < args->max_users
 446           && chptr->creationtime > args->min_time
 447           && chptr->creationtime < args->max_time
 448           && (!args->wildcard[0] || (args->flags & LISTARG_NEGATEWILDCARD) ||
 449               (!match(args->wildcard, chptr->chname)))
 450           && (!(args->flags & LISTARG_NEGATEWILDCARD) ||
 451               match(args->wildcard, chptr->chname))
 452           && (!(args->flags & LISTARG_TOPICLIMITS)
 453               || (chptr->topic[0]
 454                   && chptr->topic_time > args->min_topic_time
 455                   && chptr->topic_time < args->max_topic_time))
 456           && ((args->flags & LISTARG_SHOWSECRET)
 457               || ShowChannel(cptr, chptr)))
 458       {
 459         if (args->flags & LISTARG_SHOWMODES) {
 460           char modebuf[MODEBUFLEN];
 461           char parabuf[MODEBUFLEN];
 462
 463           modebuf[0] = modebuf[1] = parabuf[0] = '\0';
 464           channel_modes(cptr, modebuf, parabuf, sizeof(parabuf), chptr, NULL);
 465           send_reply(cptr, RPL_LIST | SND_EXPLICIT, "%s %u %s %s :%s",
 466                      chptr->chname, chptr->users, modebuf, parabuf, chptr->topic);
 467         } else {
 468           send_reply(cptr, RPL_LIST, chptr->chname, chptr->users, chptr->topic);
 469         }
 470       }
 471     }
 472     /* If, at the end of the bucket, client sendq is more than half
 473      * full, stop. */
 474     if (MsgQLength(&cli_sendQ(cptr)) > cli_max_sendq(cptr) / 2)
 475       break;
 476   }
 477
 478   /* If we did all buckets, clean the client and send RPL_LISTEND. */
 479   if (args->bucket >= HASHSIZE)
 480   {
 481     MyFree(cli_listing(cptr));
 482     cli_listing(cptr) = NULL;
 483     send_reply(cptr, RPL_LISTEND);
 484   }
 485 }