src/hash.c

   1 /*
   2  *  ircd-ratbox: A slightly useful ircd.
   3  *  hash.c: Maintains hashtables.
   4  *
   5  *  Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
   6  *  Copyright (C) 1996-2002 Hybrid Development Team
   7  *  Copyright (C) 2002-2005 ircd-ratbox development team
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
  22  *  USA
  23  *
  24  *  $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $
  25  */
  26
  27 #include "stdinc.h"
  28 #include "ircd_defs.h"
  29 #include "tools.h"
  30 #include "s_conf.h"
  31 #include "channel.h"
  32 #include "client.h"
  33 #include "common.h"
  34 #include "hash.h"
  35 #include "irc_string.h"
  36 #include "ircd.h"
  37 #include "numeric.h"
  38 #include "send.h"
  39 #include "memory.h"
  40 #include "msg.h"
  41 #include "cache.h"
  42 #include "s_newconf.h"
  43
  44 rb_dlink_list *clientTable;
  45 rb_dlink_list *channelTable;
  46 rb_dlink_list *idTable;
  47 rb_dlink_list *resvTable;
  48 rb_dlink_list *hostTable;
  49
  50 /*
  51  * look in whowas.c for the missing ...[WW_MAX]; entry
  52  */
  53
  54 /*
  55  * Hashing.
  56  *
  57  *   The server uses a chained hash table to provide quick and efficient
  58  * hash table maintenance (providing the hash function works evenly over
  59  * the input range).  The hash table is thus not susceptible to problems
  60  * of filling all the buckets or the need to rehash.
  61  *    It is expected that the hash table would look something like this
  62  * during use:
  63  *                   +-----+    +-----+    +-----+   +-----+
  64  *                ---| 224 |----| 225 |----| 226 |---| 227 |---
  65  *                   +-----+    +-----+    +-----+   +-----+
  66  *                      |          |          |
  67  *                   +-----+    +-----+    +-----+
  68  *                   |  A  |    |  C  |    |  D  |
  69  *                   +-----+    +-----+    +-----+
  70  *                      |
  71  *                   +-----+
  72  *                   |  B  |
  73  *                   +-----+
  74  *
  75  * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
  76  *
  77  * The order shown above is just one instant of the server.
  78  *
  79  *
  80  * The hash functions currently used are based Fowler/Noll/Vo hashes
  81  * which work amazingly well and have a extremely low collision rate
  82  * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
  83  *
  84  *
  85  */
  86
  87 /* init_hash()
  88  *
  89  * clears the various hashtables
  90  */
  91 void
  92 init_hash(void)
  93 {
  94         clientTable = MyMalloc(sizeof(rb_dlink_list) * U_MAX);
  95         idTable = MyMalloc(sizeof(rb_dlink_list) * U_MAX);
  96         channelTable = MyMalloc(sizeof(rb_dlink_list) * CH_MAX);
  97         hostTable = MyMalloc(sizeof(rb_dlink_list) * HOST_MAX);
  98         resvTable = MyMalloc(sizeof(rb_dlink_list) * R_MAX);
  99 }
 100
 101 #ifndef RICER_HASHING
 102 u_int32_t
 103 fnv_hash_upper(const unsigned char *s, int bits)
 104 {
 105         u_int32_t h = FNV1_32_INIT;
 106
 107         while (*s)
 108         {
 109                 h ^= ToUpper(*s++);
 110                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 111         }
 112         if (bits < 32)
 113                 h = ((h >> bits) ^ h) & ((1<<bits)-1);
 114         return h;
 115 }
 116
 117 u_int32_t
 118 fnv_hash(const unsigned char *s, int bits)
 119 {
 120         u_int32_t h = FNV1_32_INIT;
 121
 122         while (*s)
 123         {
 124                 h ^= *s++;
 125                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 126         }
 127         if (bits < 32)
 128                 h = ((h >> bits) ^ h) & ((1<<bits)-1);
 129         return h;
 130 }
 131
 132 u_int32_t
 133 fnv_hash_len(const unsigned char *s, int bits, int len)
 134 {
 135         u_int32_t h = FNV1_32_INIT;
 136         const unsigned char *x = s + len;
 137         while (*s && s < x)
 138         {
 139                 h ^= *s++;
 140                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 141         }
 142         if (bits < 32)
 143                 h = ((h >> bits) ^ h) & ((1<<bits)-1);
 144         return h;
 145 }
 146
 147 u_int32_t
 148 fnv_hash_upper_len(const unsigned char *s, int bits, int len)
 149 {
 150         u_int32_t h = FNV1_32_INIT;
 151         const unsigned char *x = s + len;
 152         while (*s && s < x)
 153         {
 154                 h ^= ToUpper(*s++);
 155                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 156         }
 157         if (bits < 32)
 158                 h = ((h >> bits) ^ h) & ((1<<bits)-1);
 159         return h;
 160 }
 161 #endif
 162
 163 /* hash_nick()
 164  *
 165  * hashes a nickname, first converting to lowercase
 166  */
 167 static u_int32_t
 168 hash_nick(const char *name)
 169 {
 170         return fnv_hash_upper((const unsigned char *) name, U_MAX_BITS);
 171 }
 172
 173 /* hash_id()
 174  *
 175  * hashes an id, case is kept
 176  */
 177 static u_int32_t
 178 hash_id(const char *name)
 179 {
 180         return fnv_hash((const unsigned char *) name, U_MAX_BITS);
 181 }
 182
 183 /* hash_channel()
 184  *
 185  * hashes a channel name, based on first 30 chars only for efficiency
 186  */
 187 static u_int32_t
 188 hash_channel(const char *name)
 189 {
 190         return fnv_hash_upper_len((const unsigned char *) name, CH_MAX_BITS, 30);
 191 }
 192
 193 /* hash_hostname()
 194  *
 195  * hashes a hostname, based on first 30 chars only, as thats likely to
 196  * be more dynamic than rest.
 197  */
 198 static u_int32_t
 199 hash_hostname(const char *name)
 200 {
 201         return fnv_hash_upper_len((const unsigned char *) name, HOST_MAX_BITS, 30);
 202 }
 203
 204 /* hash_resv()
 205  *
 206  * hashes a resv channel name, based on first 30 chars only
 207  */
 208 static u_int32_t
 209 hash_resv(const char *name)
 210 {
 211         return fnv_hash_upper_len((const unsigned char *) name, R_MAX_BITS, 30);
 212 }
 213
 214 /* add_to_id_hash()
 215  *
 216  * adds an entry to the id hash table
 217  */
 218 void
 219 add_to_id_hash(const char *name, struct Client *client_p)
 220 {
 221         unsigned int hashv;
 222
 223         if(EmptyString(name) || (client_p == NULL))
 224                 return;
 225
 226         hashv = hash_id(name);
 227         rb_dlinkAddAlloc(client_p, &idTable[hashv]);
 228 }
 229
 230 /* add_to_client_hash()
 231  *
 232  * adds an entry (client/server) to the client hash table
 233  */
 234 void
 235 add_to_client_hash(const char *name, struct Client *client_p)
 236 {
 237         unsigned int hashv;
 238
 239         s_assert(name != NULL);
 240         s_assert(client_p != NULL);
 241         if(EmptyString(name) || (client_p == NULL))
 242                 return;
 243
 244         hashv = hash_nick(name);
 245         rb_dlinkAddAlloc(client_p, &clientTable[hashv]);
 246 }
 247
 248 /* add_to_hostname_hash()
 249  *
 250  * adds a client entry to the hostname hash table
 251  */
 252 void
 253 add_to_hostname_hash(const char *hostname, struct Client *client_p)
 254 {
 255         unsigned int hashv;
 256
 257         s_assert(hostname != NULL);
 258         s_assert(client_p != NULL);
 259         if(EmptyString(hostname) || (client_p == NULL))
 260                 return;
 261
 262         hashv = hash_hostname(hostname);
 263         rb_dlinkAddAlloc(client_p, &hostTable[hashv]);
 264 }
 265
 266 /* add_to_resv_hash()
 267  *
 268  * adds a resv channel entry to the resv hash table
 269  */
 270 void
 271 add_to_resv_hash(const char *name, struct ConfItem *aconf)
 272 {
 273         unsigned int hashv;
 274
 275         s_assert(!EmptyString(name));
 276         s_assert(aconf != NULL);
 277         if(EmptyString(name) || aconf == NULL)
 278                 return;
 279
 280         hashv = hash_resv(name);
 281         rb_dlinkAddAlloc(aconf, &resvTable[hashv]);
 282 }
 283
 284 /* del_from_id_hash()
 285  *
 286  * removes an id from the id hash table
 287  */
 288 void
 289 del_from_id_hash(const char *id, struct Client *client_p)
 290 {
 291         unsigned int hashv;
 292
 293         s_assert(id != NULL);
 294         s_assert(client_p != NULL);
 295         if(EmptyString(id) || client_p == NULL)
 296                 return;
 297
 298         hashv = hash_id(id);
 299         rb_dlinkFindDestroy(client_p, &idTable[hashv]);
 300 }
 301
 302 /* del_from_client_hash()
 303  *
 304  * removes a client/server from the client hash table
 305  */
 306 void
 307 del_from_client_hash(const char *name, struct Client *client_p)
 308 {
 309         unsigned int hashv;
 310
 311         /* no s_asserts, this can happen when removing a client that
 312          * is unregistered.
 313          */
 314         if(EmptyString(name) || client_p == NULL)
 315                 return;
 316
 317         hashv = hash_nick(name);
 318         rb_dlinkFindDestroy(client_p, &clientTable[hashv]);
 319 }
 320
 321 /* del_from_channel_hash()
 322  *
 323  * removes a channel from the channel hash table
 324  */
 325 void
 326 del_from_channel_hash(const char *name, struct Channel *chptr)
 327 {
 328         unsigned int hashv;
 329
 330         s_assert(name != NULL);
 331         s_assert(chptr != NULL);
 332
 333         if(EmptyString(name) || chptr == NULL)
 334                 return;
 335
 336         hashv = hash_channel(name);
 337         rb_dlinkFindDestroy(chptr, &channelTable[hashv]);
 338 }
 339
 340 /* del_from_hostname_hash()
 341  *
 342  * removes a client entry from the hostname hash table
 343  */
 344 void
 345 del_from_hostname_hash(const char *hostname, struct Client *client_p)
 346 {
 347         unsigned int hashv;
 348
 349         if(hostname == NULL || client_p == NULL)
 350                 return;
 351
 352         hashv = hash_hostname(hostname);
 353
 354         rb_dlinkFindDestroy(client_p, &hostTable[hashv]);
 355 }
 356
 357 /* del_from_resv_hash()
 358  *
 359  * removes a resv entry from the resv hash table
 360  */
 361 void
 362 del_from_resv_hash(const char *name, struct ConfItem *aconf)
 363 {
 364         unsigned int hashv;
 365
 366         s_assert(name != NULL);
 367         s_assert(aconf != NULL);
 368         if(EmptyString(name) || aconf == NULL)
 369                 return;
 370
 371         hashv = hash_resv(name);
 372
 373         rb_dlinkFindDestroy(aconf, &resvTable[hashv]);
 374 }
 375
 376 /* find_id()
 377  *
 378  * finds a client entry from the id hash table
 379  */
 380 struct Client *
 381 find_id(const char *name)
 382 {
 383         struct Client *target_p;
 384         rb_dlink_node *ptr;
 385         unsigned int hashv;
 386
 387         if(EmptyString(name))
 388                 return NULL;
 389
 390         hashv = hash_id(name);
 391
 392         DLINK_FOREACH(ptr, idTable[hashv].head)
 393         {
 394                 target_p = ptr->data;
 395
 396                 if(strcmp(name, target_p->id) == 0)
 397                         return target_p;
 398         }
 399
 400         return NULL;
 401 }
 402
 403 /* find_client()
 404  *
 405  * finds a client/server entry from the client hash table
 406  */
 407 struct Client *
 408 find_client(const char *name)
 409 {
 410         struct Client *target_p;
 411         rb_dlink_node *ptr;
 412         unsigned int hashv;
 413
 414         s_assert(name != NULL);
 415         if(EmptyString(name))
 416                 return NULL;
 417
 418         /* hunting for an id, not a nick */
 419         if(IsDigit(*name))
 420                 return (find_id(name));
 421
 422         hashv = hash_nick(name);
 423
 424         DLINK_FOREACH(ptr, clientTable[hashv].head)
 425         {
 426                 target_p = ptr->data;
 427
 428                 if(irccmp(name, target_p->name) == 0)
 429                         return target_p;
 430         }
 431
 432         return NULL;
 433 }
 434
 435 /* find_named_client()
 436  *
 437  * finds a client/server entry from the client hash table
 438  */
 439 struct Client *
 440 find_named_client(const char *name)
 441 {
 442         struct Client *target_p;
 443         rb_dlink_node *ptr;
 444         unsigned int hashv;
 445
 446         s_assert(name != NULL);
 447         if(EmptyString(name))
 448                 return NULL;
 449
 450         hashv = hash_nick(name);
 451
 452         DLINK_FOREACH(ptr, clientTable[hashv].head)
 453         {
 454                 target_p = ptr->data;
 455
 456                 if(irccmp(name, target_p->name) == 0)
 457                         return target_p;
 458         }
 459
 460         return NULL;
 461 }
 462
 463 /* find_server()
 464  *
 465  * finds a server from the client hash table
 466  */
 467 struct Client *
 468 find_server(struct Client *source_p, const char *name)
 469 {
 470         struct Client *target_p;
 471         rb_dlink_node *ptr;
 472         unsigned int hashv;
 473
 474         if(EmptyString(name))
 475                 return NULL;
 476
 477         if((source_p == NULL || !MyClient(source_p)) &&
 478            IsDigit(*name) && strlen(name) == 3)
 479         {
 480                 target_p = find_id(name);
 481                 return(target_p);
 482         }
 483
 484         hashv = hash_nick(name);
 485
 486         DLINK_FOREACH(ptr, clientTable[hashv].head)
 487         {
 488                 target_p = ptr->data;
 489
 490                 if((IsServer(target_p) || IsMe(target_p)) &&
 491                    irccmp(name, target_p->name) == 0)
 492                                 return target_p;
 493         }
 494
 495         return NULL;
 496 }
 497
 498 /* find_hostname()
 499  *
 500  * finds a hostname rb_dlink list from the hostname hash table.
 501  * we return the full rb_dlink list, because you can have multiple
 502  * entries with the same hostname
 503  */
 504 rb_dlink_node *
 505 find_hostname(const char *hostname)
 506 {
 507         unsigned int hashv;
 508
 509         if(EmptyString(hostname))
 510                 return NULL;
 511
 512         hashv = hash_hostname(hostname);
 513
 514         return hostTable[hashv].head;
 515 }
 516
 517 /* find_channel()
 518  *
 519  * finds a channel from the channel hash table
 520  */
 521 struct Channel *
 522 find_channel(const char *name)
 523 {
 524         struct Channel *chptr;
 525         rb_dlink_node *ptr;
 526         unsigned int hashv;
 527
 528         s_assert(name != NULL);
 529         if(EmptyString(name))
 530                 return NULL;
 531
 532         hashv = hash_channel(name);
 533
 534         DLINK_FOREACH(ptr, channelTable[hashv].head)
 535         {
 536                 chptr = ptr->data;
 537
 538                 if(irccmp(name, chptr->chname) == 0)
 539                         return chptr;
 540         }
 541
 542         return NULL;
 543 }
 544
 545 /*
 546  * get_or_create_channel
 547  * inputs       - client pointer
 548  *              - channel name
 549  *              - pointer to int flag whether channel was newly created or not
 550  * output       - returns channel block or NULL if illegal name
 551  *              - also modifies *isnew
 552  *
 553  *  Get Channel block for chname (and allocate a new channel
 554  *  block, if it didn't exist before).
 555  */
 556 struct Channel *
 557 get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)
 558 {
 559         struct Channel *chptr;
 560         rb_dlink_node *ptr;
 561         unsigned int hashv;
 562         int len;
 563         const char *s = chname;
 564
 565         if(EmptyString(s))
 566                 return NULL;
 567
 568         len = strlen(s);
 569         if(len > CHANNELLEN)
 570         {
 571                 char *t;
 572                 if(IsServer(client_p))
 573                 {
 574                         sendto_realops_snomask(SNO_DEBUG, L_ALL,
 575                                              "*** Long channel name from %s (%d > %d): %s",
 576                                              client_p->name, len, CHANNELLEN, s);
 577                 }
 578                 len = CHANNELLEN;
 579                 t = LOCAL_COPY(s);
 580                 *(t + CHANNELLEN) = '\0';
 581                 s = t;
 582         }
 583
 584         hashv = hash_channel(s);
 585
 586         DLINK_FOREACH(ptr, channelTable[hashv].head)
 587         {
 588                 chptr = ptr->data;
 589
 590                 if(irccmp(s, chptr->chname) == 0)
 591                 {
 592                         if(isnew != NULL)
 593                                 *isnew = 0;
 594                         return chptr;
 595                 }
 596         }
 597
 598         if(isnew != NULL)
 599                 *isnew = 1;
 600
 601         chptr = allocate_channel(s);
 602
 603         rb_dlinkAdd(chptr, &chptr->node, &global_channel_list);
 604
 605         chptr->channelts = CurrentTime; /* doesn't hurt to set it here */
 606
 607         rb_dlinkAddAlloc(chptr, &channelTable[hashv]);
 608
 609         return chptr;
 610 }
 611
 612 /* hash_find_resv()
 613  *
 614  * hunts for a resv entry in the resv hash table
 615  */
 616 struct ConfItem *
 617 hash_find_resv(const char *name)
 618 {
 619         struct ConfItem *aconf;
 620         rb_dlink_node *ptr;
 621         unsigned int hashv;
 622
 623         s_assert(name != NULL);
 624         if(EmptyString(name))
 625                 return NULL;
 626
 627         hashv = hash_resv(name);
 628
 629         DLINK_FOREACH(ptr, resvTable[hashv].head)
 630         {
 631                 aconf = ptr->data;
 632
 633                 if(!irccmp(name, aconf->name))
 634                 {
 635                         aconf->port++;
 636                         return aconf;
 637                 }
 638         }
 639
 640         return NULL;
 641 }
 642
 643 void
 644 clear_resv_hash(void)
 645 {
 646         struct ConfItem *aconf;
 647         rb_dlink_node *ptr;
 648         rb_dlink_node *next_ptr;
 649         int i;
 650
 651         HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
 652         {
 653                 aconf = ptr->data;
 654
 655                 /* skip temp resvs */
 656                 if(aconf->hold)
 657                         continue;
 658
 659                 free_conf(ptr->data);
 660                 rb_dlinkDestroy(ptr, &resvTable[i]);
 661         }
 662         HASH_WALK_END
 663 }
 664
 665 static void
 666 output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)
 667 {
 668         unsigned long total = 0;
 669         int i;
 670
 671         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 672                         "B :%s Hash Statistics", name);
 673
 674         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 675                         "B :Size: %d Empty: %d (%.3f%%)",
 676                         length, counts[0],
 677                         (float) ((counts[0]*100) / (float) length));
 678
 679         for(i = 1; i < 11; i++)
 680         {
 681                 total += (counts[i] * i);
 682         }
 683
 684         /* dont want to divide by 0! --fl */
 685         if(counts[0] != length)
 686                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 687                                 "B :Average depth: %.3f/%.3f Highest depth: %d",
 688                                 (float) (total / (length - counts[0])),
 689                                 (float) (total / length), deepest);
 690
 691         for(i = 0; i < 11; i++)
 692         {
 693                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 694                                 "B :Nodes with %d entries: %d",
 695                                 i, counts[i]);
 696         }
 697 }
 698
 699
 700 static void
 701 count_hash(struct Client *source_p, rb_dlink_list *table, int length, const char *name)
 702 {
 703         int counts[11];
 704         int deepest = 0;
 705         int i;
 706
 707         memset(counts, 0, sizeof(counts));
 708
 709         for(i = 0; i < length; i++)
 710         {
 711                 if(rb_dlink_list_length(&table[i]) >= 10)
 712                         counts[10]++;
 713                 else
 714                         counts[rb_dlink_list_length(&table[i])]++;
 715
 716                 if(rb_dlink_list_length(&table[i]) > deepest)
 717                         deepest = rb_dlink_list_length(&table[i]);
 718         }
 719
 720         output_hash(source_p, name, length, counts, deepest);
 721 }
 722
 723 void
 724 hash_stats(struct Client *source_p)
 725 {
 726         count_hash(source_p, channelTable, CH_MAX, "Channel");
 727         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 728         count_hash(source_p, clientTable, U_MAX, "Client");
 729         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 730         count_hash(source_p, idTable, U_MAX, "ID");
 731         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 732         count_hash(source_p, hostTable, HOST_MAX, "Hostname");
 733 }