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 dlink_list *clientTable;
  45 dlink_list *channelTable;
  46 dlink_list *idTable;
  47 dlink_list *resvTable;
  48 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(dlink_list) * U_MAX);
  95         idTable = MyMalloc(sizeof(dlink_list) * U_MAX);
  96         channelTable = MyMalloc(sizeof(dlink_list) * CH_MAX);
  97         hostTable = MyMalloc(sizeof(dlink_list) * HOST_MAX);
  98         resvTable = MyMalloc(sizeof(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         h = (h >> bits) ^ (h & ((2^bits)-1));
 113         return h;
 114 }
 115
 116 u_int32_t
 117 fnv_hash(const unsigned char *s, int bits)
 118 {
 119         u_int32_t h = FNV1_32_INIT;
 120
 121         while (*s)
 122         {
 123                 h ^= *s++;
 124                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 125         }
 126         h = (h >> bits) ^ (h & ((2^bits)-1));
 127         return h;
 128 }
 129
 130 u_int32_t
 131 fnv_hash_len(const unsigned char *s, int bits, int len)
 132 {
 133         u_int32_t h = FNV1_32_INIT;
 134         const unsigned char *x = s + len;
 135         while (*s && s < x)
 136         {
 137                 h ^= *s++;
 138                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 139         }
 140         h = (h >> bits) ^ (h & ((2^bits)-1));
 141         return h;
 142 }
 143
 144 u_int32_t
 145 fnv_hash_upper_len(const unsigned char *s, int bits, int len)
 146 {
 147         u_int32_t h = FNV1_32_INIT;
 148         const unsigned char *x = s + len;
 149         while (*s && s < x)
 150         {
 151                 h ^= ToUpper(*s++);
 152                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 153         }
 154         h = (h >> bits) ^ (h & ((2^bits)-1));
 155         return h;
 156 }
 157 #endif
 158
 159 /* hash_nick()
 160  *
 161  * hashes a nickname, first converting to lowercase
 162  */
 163 static u_int32_t
 164 hash_nick(const char *name)
 165 {
 166         return fnv_hash_upper((const unsigned char *) name, U_MAX_BITS);
 167 }
 168
 169 /* hash_id()
 170  *
 171  * hashes an id, case is kept
 172  */
 173 static u_int32_t
 174 hash_id(const char *name)
 175 {
 176         return fnv_hash((const unsigned char *) name, U_MAX_BITS);
 177 }
 178
 179 /* hash_channel()
 180  *
 181  * hashes a channel name, based on first 30 chars only for efficiency
 182  */
 183 static u_int32_t
 184 hash_channel(const char *name)
 185 {
 186         return fnv_hash_upper_len((const unsigned char *) name, CH_MAX_BITS, 30);
 187 }
 188
 189 /* hash_hostname()
 190  *
 191  * hashes a hostname, based on first 30 chars only, as thats likely to
 192  * be more dynamic than rest.
 193  */
 194 static u_int32_t
 195 hash_hostname(const char *name)
 196 {
 197         return fnv_hash_upper_len((const unsigned char *) name, HOST_MAX_BITS, 30);
 198 }
 199
 200 /* hash_resv()
 201  *
 202  * hashes a resv channel name, based on first 30 chars only
 203  */
 204 static u_int32_t
 205 hash_resv(const char *name)
 206 {
 207         return fnv_hash_upper_len((const unsigned char *) name, R_MAX_BITS, 30);
 208 }
 209
 210 /* add_to_id_hash()
 211  *
 212  * adds an entry to the id hash table
 213  */
 214 void
 215 add_to_id_hash(const char *name, struct Client *client_p)
 216 {
 217         unsigned int hashv;
 218
 219         if(EmptyString(name) || (client_p == NULL))
 220                 return;
 221
 222         hashv = hash_id(name);
 223         dlinkAddAlloc(client_p, &idTable[hashv]);
 224 }
 225
 226 /* add_to_client_hash()
 227  *
 228  * adds an entry (client/server) to the client hash table
 229  */
 230 void
 231 add_to_client_hash(const char *name, struct Client *client_p)
 232 {
 233         unsigned int hashv;
 234
 235         s_assert(name != NULL);
 236         s_assert(client_p != NULL);
 237         if(EmptyString(name) || (client_p == NULL))
 238                 return;
 239
 240         hashv = hash_nick(name);
 241         dlinkAddAlloc(client_p, &clientTable[hashv]);
 242 }
 243
 244 /* add_to_hostname_hash()
 245  *
 246  * adds a client entry to the hostname hash table
 247  */
 248 void
 249 add_to_hostname_hash(const char *hostname, struct Client *client_p)
 250 {
 251         unsigned int hashv;
 252
 253         s_assert(hostname != NULL);
 254         s_assert(client_p != NULL);
 255         if(EmptyString(hostname) || (client_p == NULL))
 256                 return;
 257
 258         hashv = hash_hostname(hostname);
 259         dlinkAddAlloc(client_p, &hostTable[hashv]);
 260 }
 261
 262 /* add_to_resv_hash()
 263  *
 264  * adds a resv channel entry to the resv hash table
 265  */
 266 void
 267 add_to_resv_hash(const char *name, struct ConfItem *aconf)
 268 {
 269         unsigned int hashv;
 270
 271         s_assert(!EmptyString(name));
 272         s_assert(aconf != NULL);
 273         if(EmptyString(name) || aconf == NULL)
 274                 return;
 275
 276         hashv = hash_resv(name);
 277         dlinkAddAlloc(aconf, &resvTable[hashv]);
 278 }
 279
 280 /* del_from_id_hash()
 281  *
 282  * removes an id from the id hash table
 283  */
 284 void
 285 del_from_id_hash(const char *id, struct Client *client_p)
 286 {
 287         unsigned int hashv;
 288
 289         s_assert(id != NULL);
 290         s_assert(client_p != NULL);
 291         if(EmptyString(id) || client_p == NULL)
 292                 return;
 293
 294         hashv = hash_id(id);
 295         dlinkFindDestroy(client_p, &idTable[hashv]);
 296 }
 297
 298 /* del_from_client_hash()
 299  *
 300  * removes a client/server from the client hash table
 301  */
 302 void
 303 del_from_client_hash(const char *name, struct Client *client_p)
 304 {
 305         unsigned int hashv;
 306
 307         /* no s_asserts, this can happen when removing a client that
 308          * is unregistered.
 309          */
 310         if(EmptyString(name) || client_p == NULL)
 311                 return;
 312
 313         hashv = hash_nick(name);
 314         dlinkFindDestroy(client_p, &clientTable[hashv]);
 315 }
 316
 317 /* del_from_channel_hash()
 318  *
 319  * removes a channel from the channel hash table
 320  */
 321 void
 322 del_from_channel_hash(const char *name, struct Channel *chptr)
 323 {
 324         unsigned int hashv;
 325
 326         s_assert(name != NULL);
 327         s_assert(chptr != NULL);
 328
 329         if(EmptyString(name) || chptr == NULL)
 330                 return;
 331
 332         hashv = hash_channel(name);
 333         dlinkFindDestroy(chptr, &channelTable[hashv]);
 334 }
 335
 336 /* del_from_hostname_hash()
 337  *
 338  * removes a client entry from the hostname hash table
 339  */
 340 void
 341 del_from_hostname_hash(const char *hostname, struct Client *client_p)
 342 {
 343         unsigned int hashv;
 344
 345         if(hostname == NULL || client_p == NULL)
 346                 return;
 347
 348         hashv = hash_hostname(hostname);
 349
 350         dlinkFindDestroy(client_p, &hostTable[hashv]);
 351 }
 352
 353 /* del_from_resv_hash()
 354  *
 355  * removes a resv entry from the resv hash table
 356  */
 357 void
 358 del_from_resv_hash(const char *name, struct ConfItem *aconf)
 359 {
 360         unsigned int hashv;
 361
 362         s_assert(name != NULL);
 363         s_assert(aconf != NULL);
 364         if(EmptyString(name) || aconf == NULL)
 365                 return;
 366
 367         hashv = hash_resv(name);
 368
 369         dlinkFindDestroy(aconf, &resvTable[hashv]);
 370 }
 371
 372 /* find_id()
 373  *
 374  * finds a client entry from the id hash table
 375  */
 376 struct Client *
 377 find_id(const char *name)
 378 {
 379         struct Client *target_p;
 380         dlink_node *ptr;
 381         unsigned int hashv;
 382
 383         if(EmptyString(name))
 384                 return NULL;
 385
 386         hashv = hash_id(name);
 387
 388         DLINK_FOREACH(ptr, idTable[hashv].head)
 389         {
 390                 target_p = ptr->data;
 391
 392                 if(strcmp(name, target_p->id) == 0)
 393                         return target_p;
 394         }
 395
 396         return NULL;
 397 }
 398
 399 /* find_client()
 400  *
 401  * finds a client/server entry from the client hash table
 402  */
 403 struct Client *
 404 find_client(const char *name)
 405 {
 406         struct Client *target_p;
 407         dlink_node *ptr;
 408         unsigned int hashv;
 409
 410         s_assert(name != NULL);
 411         if(EmptyString(name))
 412                 return NULL;
 413
 414         /* hunting for an id, not a nick */
 415         if(IsDigit(*name))
 416                 return (find_id(name));
 417
 418         hashv = hash_nick(name);
 419
 420         DLINK_FOREACH(ptr, clientTable[hashv].head)
 421         {
 422                 target_p = ptr->data;
 423
 424                 if(irccmp(name, target_p->name) == 0)
 425                         return target_p;
 426         }
 427
 428         return NULL;
 429 }
 430
 431 /* find_named_client()
 432  *
 433  * finds a client/server entry from the client hash table
 434  */
 435 struct Client *
 436 find_named_client(const char *name)
 437 {
 438         struct Client *target_p;
 439         dlink_node *ptr;
 440         unsigned int hashv;
 441
 442         s_assert(name != NULL);
 443         if(EmptyString(name))
 444                 return NULL;
 445
 446         hashv = hash_nick(name);
 447
 448         DLINK_FOREACH(ptr, clientTable[hashv].head)
 449         {
 450                 target_p = ptr->data;
 451
 452                 if(irccmp(name, target_p->name) == 0)
 453                         return target_p;
 454         }
 455
 456         return NULL;
 457 }
 458
 459 /* find_server()
 460  *
 461  * finds a server from the client hash table
 462  */
 463 struct Client *
 464 find_server(struct Client *source_p, const char *name)
 465 {
 466         struct Client *target_p;
 467         dlink_node *ptr;
 468         unsigned int hashv;
 469
 470         if(EmptyString(name))
 471                 return NULL;
 472
 473         if((source_p == NULL || !MyClient(source_p)) &&
 474            IsDigit(*name) && strlen(name) == 3)
 475         {
 476                 target_p = find_id(name);
 477                 return(target_p);
 478         }
 479
 480         hashv = hash_nick(name);
 481
 482         DLINK_FOREACH(ptr, clientTable[hashv].head)
 483         {
 484                 target_p = ptr->data;
 485
 486                 if((IsServer(target_p) || IsMe(target_p)) &&
 487                    irccmp(name, target_p->name) == 0)
 488                                 return target_p;
 489         }
 490
 491         return NULL;
 492 }
 493
 494 /* find_hostname()
 495  *
 496  * finds a hostname dlink list from the hostname hash table.
 497  * we return the full dlink list, because you can have multiple
 498  * entries with the same hostname
 499  */
 500 dlink_node *
 501 find_hostname(const char *hostname)
 502 {
 503         unsigned int hashv;
 504
 505         if(EmptyString(hostname))
 506                 return NULL;
 507
 508         hashv = hash_hostname(hostname);
 509
 510         return hostTable[hashv].head;
 511 }
 512
 513 /* find_channel()
 514  *
 515  * finds a channel from the channel hash table
 516  */
 517 struct Channel *
 518 find_channel(const char *name)
 519 {
 520         struct Channel *chptr;
 521         dlink_node *ptr;
 522         unsigned int hashv;
 523
 524         s_assert(name != NULL);
 525         if(EmptyString(name))
 526                 return NULL;
 527
 528         hashv = hash_channel(name);
 529
 530         DLINK_FOREACH(ptr, channelTable[hashv].head)
 531         {
 532                 chptr = ptr->data;
 533
 534                 if(irccmp(name, chptr->chname) == 0)
 535                         return chptr;
 536         }
 537
 538         return NULL;
 539 }
 540
 541 /*
 542  * get_or_create_channel
 543  * inputs       - client pointer
 544  *              - channel name
 545  *              - pointer to int flag whether channel was newly created or not
 546  * output       - returns channel block or NULL if illegal name
 547  *              - also modifies *isnew
 548  *
 549  *  Get Channel block for chname (and allocate a new channel
 550  *  block, if it didn't exist before).
 551  */
 552 struct Channel *
 553 get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)
 554 {
 555         struct Channel *chptr;
 556         dlink_node *ptr;
 557         unsigned int hashv;
 558         int len;
 559         const char *s = chname;
 560
 561         if(EmptyString(s))
 562                 return NULL;
 563
 564         len = strlen(s);
 565         if(len > CHANNELLEN)
 566         {
 567                 char *t;
 568                 if(IsServer(client_p))
 569                 {
 570                         sendto_realops_snomask(SNO_DEBUG, L_ALL,
 571                                              "*** Long channel name from %s (%d > %d): %s",
 572                                              client_p->name, len, CHANNELLEN, s);
 573                 }
 574                 len = CHANNELLEN;
 575                 t = LOCAL_COPY(s);
 576                 *(t + CHANNELLEN) = '\0';
 577                 s = t;
 578         }
 579
 580         hashv = hash_channel(s);
 581
 582         DLINK_FOREACH(ptr, channelTable[hashv].head)
 583         {
 584                 chptr = ptr->data;
 585
 586                 if(irccmp(s, chptr->chname) == 0)
 587                 {
 588                         if(isnew != NULL)
 589                                 *isnew = 0;
 590                         return chptr;
 591                 }
 592         }
 593
 594         if(isnew != NULL)
 595                 *isnew = 1;
 596
 597         chptr = allocate_channel(s);
 598
 599         dlinkAdd(chptr, &chptr->node, &global_channel_list);
 600
 601         chptr->channelts = CurrentTime; /* doesn't hurt to set it here */
 602
 603         dlinkAddAlloc(chptr, &channelTable[hashv]);
 604
 605         return chptr;
 606 }
 607
 608 /* hash_find_resv()
 609  *
 610  * hunts for a resv entry in the resv hash table
 611  */
 612 struct ConfItem *
 613 hash_find_resv(const char *name)
 614 {
 615         struct ConfItem *aconf;
 616         dlink_node *ptr;
 617         unsigned int hashv;
 618
 619         s_assert(name != NULL);
 620         if(EmptyString(name))
 621                 return NULL;
 622
 623         hashv = hash_resv(name);
 624
 625         DLINK_FOREACH(ptr, resvTable[hashv].head)
 626         {
 627                 aconf = ptr->data;
 628
 629                 if(!irccmp(name, aconf->name))
 630                 {
 631                         aconf->port++;
 632                         return aconf;
 633                 }
 634         }
 635
 636         return NULL;
 637 }
 638
 639 void
 640 clear_resv_hash(void)
 641 {
 642         struct ConfItem *aconf;
 643         dlink_node *ptr;
 644         dlink_node *next_ptr;
 645         int i;
 646
 647         HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
 648         {
 649                 aconf = ptr->data;
 650
 651                 /* skip temp resvs */
 652                 if(aconf->hold)
 653                         continue;
 654
 655                 free_conf(ptr->data);
 656                 dlinkDestroy(ptr, &resvTable[i]);
 657         }
 658         HASH_WALK_END
 659 }
 660
 661 static void
 662 output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)
 663 {
 664         unsigned long total = 0;
 665         int i;
 666
 667         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 668                         "B :%s Hash Statistics", name);
 669
 670         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 671                         "B :Size: %d Empty: %d (%.3f%%)",
 672                         length, counts[0],
 673                         (float) ((counts[0]*100) / (float) length));
 674
 675         for(i = 1; i < 11; i++)
 676         {
 677                 total += (counts[i] * i);
 678         }
 679
 680         /* dont want to divide by 0! --fl */
 681         if(counts[0] != length)
 682                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 683                                 "B :Average depth: %.3f/%.3f Highest depth: %d",
 684                                 (float) (total / (length - counts[0])),
 685                                 (float) (total / length), deepest);
 686
 687         for(i = 0; i < 11; i++)
 688         {
 689                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 690                                 "B :Nodes with %d entries: %d",
 691                                 i, counts[i]);
 692         }
 693 }
 694
 695
 696 static void
 697 count_hash(struct Client *source_p, dlink_list *table, int length, const char *name)
 698 {
 699         int counts[11];
 700         int deepest = 0;
 701         int i;
 702
 703         memset(counts, 0, sizeof(counts));
 704
 705         for(i = 0; i < length; i++)
 706         {
 707                 if(dlink_list_length(&table[i]) >= 10)
 708                         counts[10]++;
 709                 else
 710                         counts[dlink_list_length(&table[i])]++;
 711
 712                 if(dlink_list_length(&table[i]) > deepest)
 713                         deepest = dlink_list_length(&table[i]);
 714         }
 715
 716         output_hash(source_p, name, length, counts, deepest);
 717 }
 718
 719 void
 720 hash_stats(struct Client *source_p)
 721 {
 722         count_hash(source_p, channelTable, CH_MAX, "Channel");
 723         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 724         count_hash(source_p, clientTable, U_MAX, "Client");
 725         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 726         count_hash(source_p, idTable, U_MAX, "ID");
 727         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 728         count_hash(source_p, hostTable, HOST_MAX, "Hostname");
 729 }