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