trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 1997-2015 ircd-hybrid development team
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA
 */

/*! \file hash.c
 * \brief Hash table management.
 * \version $Id$
 */

#include "stdinc.h"
#include "list.h"
#include "conf.h"
#include "channel.h"
#include "channel_mode.h"
#include "client.h"
#include "modules.h"
#include "hash.h"
#include "id.h"
#include "resv.h"
#include "rng_mt.h"
#include "userhost.h"
#include "irc_string.h"
#include "ircd.h"
#include "numeric.h"
#include "send.h"
#include "memory.h"
#include "mempool.h"
#include "dbuf.h"
#include "user.h"


static mp_pool_t *userhost_pool;
static mp_pool_t *namehost_pool;

static unsigned int hashf_xor_key;

/* The actual hash tables, They MUST be of the same HASHSIZE, variable
 * size tables could be supported but the rehash routine should also
 * rebuild the transformation maps, I kept the tables of equal size
 * so that I can use one hash function.
 */
static struct Client *idTable[HASHSIZE];
static struct Client *clientTable[HASHSIZE];
static struct Channel *channelTable[HASHSIZE];
static struct UserHost *userhostTable[HASHSIZE];


/* init_hash()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - Initialize the maps used by hash
 *                functions and clear the tables
 */
void
hash_init(void)
{
  userhost_pool = mp_pool_new(sizeof(struct UserHost), MP_CHUNK_SIZE_USERHOST);
  namehost_pool = mp_pool_new(sizeof(struct NameHost), MP_CHUNK_SIZE_NAMEHOST);

  hashf_xor_key = genrand_int32() % 256;  /* better than nothing --adx */
}

/*
 * New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
 * http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * Here, we use the FNV-1 method, which gives slightly better results
 * than FNV-1a.   -Michael
 */
unsigned int
strhash(const char *name)
{
  const unsigned char *p = (const unsigned char *)name;
  unsigned int hval = FNV1_32_INIT;

  if (EmptyString(p))
    return 0;

  for (; *p; ++p)
  {
    hval += (hval << 1) + (hval <<  4) + (hval << 7) +
            (hval << 8) + (hval << 24);
    hval ^= (ToLower(*p) ^ hashf_xor_key);
  }

  return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
}

/************************** Externally visible functions ********************/

/* Optimization note: in these functions I supposed that the CSE optimization
 * (Common Subexpression Elimination) does its work decently, this means that
 * I avoided introducing new variables to do the work myself and I did let
 * the optimizer play with more free registers, actual tests proved this
 * solution to be faster than doing things like tmp2=tmp->hnext... and then
 * use tmp2 myself which would have given less freedom to the optimizer.
 */

/* hash_add_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Adds a client's name in the proper hash linked
 *                list, can't fail, client_p must have a non-null
 *                name or expect a coredump, the name is infact
 *                taken from client_p->name
 */
void
hash_add_client(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->name);

  client_p->hnext = clientTable[hashv];
  clientTable[hashv] = client_p;
}

/* hash_add_channel()
 *
 * inputs       - pointer to channel
 * output       - NONE
 * side effects - Adds a channel's name in the proper hash linked
 *                list, can't fail. chptr must have a non-null name
 *                or expect a coredump. As before the name is taken
 *                from chptr->name, we do hash its entire lenght
 *                since this proved to be statistically faster
 */
void
hash_add_channel(struct Channel *chptr)
{
  const unsigned int hashv = strhash(chptr->name);

  chptr->hnextch = channelTable[hashv];
  channelTable[hashv] = chptr;
}

void
hash_add_userhost(struct UserHost *userhost)
{
  const unsigned int hashv = strhash(userhost->host);

  userhost->next = userhostTable[hashv];
  userhostTable[hashv] = userhost;
}

void
hash_add_id(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->id);

  client_p->idhnext = idTable[hashv];
  idTable[hashv] = client_p;
}

/* hash_del_id()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes an ID from the hash linked list
 */
void
hash_del_id(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->id);
  struct Client *tmp = idTable[hashv];

  if (tmp)
  {
    if (tmp == client_p)
    {
      idTable[hashv] = client_p->idhnext;
      client_p->idhnext = client_p;
    }
    else
    {
      while (tmp->idhnext != client_p)
        if ((tmp = tmp->idhnext) == NULL)
          return;

      tmp->idhnext = tmp->idhnext->idhnext;
      client_p->idhnext = client_p;
    }
  }
}

/* hash_del_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes a Client's name from the hash linked list
 */
void
hash_del_client(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->name);
  struct Client *tmp = clientTable[hashv];

  if (tmp)
  {
    if (tmp == client_p)
    {
      clientTable[hashv] = client_p->hnext;
      client_p->hnext = client_p;
    }
    else
    {
      while (tmp->hnext != client_p)
        if ((tmp = tmp->hnext) == NULL)
          return;

      tmp->hnext = tmp->hnext->hnext;
      client_p->hnext = client_p;
    }
  }
}

/* hash_del_userhost()
 *
 * inputs       - pointer to userhost
 * output       - NONE
 * side effects - Removes a userhost from the hash linked list
 */
void
hash_del_userhost(struct UserHost *userhost)
{
  const unsigned int hashv = strhash(userhost->host);
  struct UserHost *tmp = userhostTable[hashv];

  if (tmp)
  {
    if (tmp == userhost)
    {
      userhostTable[hashv] = userhost->next;
      userhost->next = userhost;
    }
    else
    {
      while (tmp->next != userhost)
        if ((tmp = tmp->next) == NULL)
          return;

      tmp->next = tmp->next->next;
      userhost->next = userhost;
    }
  }
}

/* hash_del_channel()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes the channel's name from the corresponding
 *                hash linked list
 */
void
hash_del_channel(struct Channel *chptr)
{
  const unsigned int hashv = strhash(chptr->name);
  struct Channel *tmp = channelTable[hashv];

  if (tmp)
  {
    if (tmp == chptr)
    {
      channelTable[hashv] = chptr->hnextch;
      chptr->hnextch = chptr;
    }
    else
    {
      while (tmp->hnextch != chptr)
        if ((tmp = tmp->hnextch) == NULL)
          return;

      tmp->hnextch = tmp->hnextch->hnextch;
      chptr->hnextch = chptr;
    }
  }
}

/* hash_find_client()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a client whose name is 'name'
 *                if can't find one returns NULL. If it finds one moves
 *                it to the top of the list and returns it.
 */
struct Client *
hash_find_client(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Client *client_p;

  if ((client_p = clientTable[hashv]))
  {
    if (irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext))
      {
        if (!irccmp(name, client_p->name))
        {
          prev->hnext = client_p->hnext;
          client_p->hnext = clientTable[hashv];
          clientTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

struct Client *
hash_find_id(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Client *client_p;

  if ((client_p = idTable[hashv]))
  {
    if (strcmp(name, client_p->id))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->idhnext))
      {
        if (!strcmp(name, client_p->id))
        {
          prev->idhnext = client_p->idhnext;
          client_p->idhnext = idTable[hashv];
          idTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

struct Client *
hash_find_server(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Client *client_p = NULL;

  if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
    return hash_find_id(name);

  if ((client_p = clientTable[hashv]))
  {
    if ((!IsServer(client_p) && !IsMe(client_p)) ||
        irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext))
      {
        if ((IsServer(client_p) || IsMe(client_p)) &&
            !irccmp(name, client_p->name))
        {
          prev->hnext = client_p->hnext;
          client_p->hnext = clientTable[hashv];
          clientTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

/* hash_find_channel()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a channel whose name is 'name',
 *                if can't find one returns NULL, if can find it moves
 *                it to the top of the list and returns it.
 */
struct Channel *
hash_find_channel(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Channel *chptr = NULL;

  if ((chptr = channelTable[hashv]))
  {
    if (irccmp(name, chptr->name))
    {
      struct Channel *prev;

      while (prev = chptr, (chptr = chptr->hnextch))
      {
        if (!irccmp(name, chptr->name))
        {
          prev->hnextch = chptr->hnextch;
          chptr->hnextch = channelTable[hashv];
          channelTable[hashv] = chptr;
          break;
        }
      }
    }
  }

  return chptr;
}

/* hash_get_bucket(int type, unsigned int hashv)
 *
 * inputs       - hash value (must be between 0 and HASHSIZE - 1)
 * output       - NONE
 * returns      - pointer to first channel in channelTable[hashv]
 *                if that exists;
 *                NULL if there is no channel in that place;
 *                NULL if hashv is an invalid number.
 * side effects - NONE
 */
void *
hash_get_bucket(int type, unsigned int hashv)
{
  assert(hashv < HASHSIZE);

  if (hashv >= HASHSIZE)
      return NULL;

  switch (type)
  {
    case HASH_TYPE_ID:
      return idTable[hashv];
      break;
    case HASH_TYPE_CHANNEL:
      return channelTable[hashv];
      break;
    case HASH_TYPE_CLIENT:
      return clientTable[hashv];
      break;
    case HASH_TYPE_USERHOST:
      return userhostTable[hashv];
      break;
    default:
      assert(0);
  }

  return NULL;
}

struct UserHost *
hash_find_userhost(const char *host)
{
  const unsigned int hashv = strhash(host);
  struct UserHost *userhost;

  if ((userhost = userhostTable[hashv]))
  {
    if (irccmp(host, userhost->host))
    {
      struct UserHost *prev;

      while (prev = userhost, (userhost = userhost->next))
      {
        if (!irccmp(host, userhost->host))
        {
          prev->next = userhost->next;
          userhost->next = userhostTable[hashv];
          userhostTable[hashv] = userhost;
          break;
        }
      }
    }
  }

  return userhost;
}

/* count_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 *              - pointer to where global count should go
 *              - pointer to where local count should go
 *              - pointer to where identd count should go (local clients only)
 * output       - none
 * side effects -
 */
void
count_user_host(const char *user, const char *host, unsigned int *global_p,
                unsigned int *local_p, unsigned int *icount_p)
{
  dlink_node *node = NULL;
  struct UserHost *found_userhost;

  if ((found_userhost = hash_find_userhost(host)) == NULL)
    return;

  DLINK_FOREACH(node, found_userhost->list.head)
  {
    struct NameHost *nameh = node->data;

    if (!irccmp(user, nameh->name))
    {
      if (global_p)
        *global_p = nameh->gcount;
      if (local_p)
        *local_p  = nameh->lcount;
      if (icount_p)
        *icount_p = nameh->icount;

      return;
    }
  }
}

/* find_or_add_userhost()
 *
 * inputs       - host name
 * output       - none
 * side effects - find UserHost * for given host name
 */
static struct UserHost *
find_or_add_userhost(const char *host)
{
  struct UserHost *userhost = NULL;

  if ((userhost = hash_find_userhost(host)))
    return userhost;

  userhost = mp_pool_get(userhost_pool);

  strlcpy(userhost->host, host, sizeof(userhost->host));
  hash_add_userhost(userhost);

  return userhost;
}

/* add_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 * output       - none
 * side effects - add given user@host to hash tables
 */
void
add_user_host(const char *user, const char *host, int global)
{
  dlink_node *node = NULL;
  struct UserHost *found_userhost;
  struct NameHost *nameh;
  unsigned int hasident = 1;

  if (*user == '~')
  {
    hasident = 0;
    ++user;
  }

  if ((found_userhost = find_or_add_userhost(host)) == NULL)
    return;

  DLINK_FOREACH(node, found_userhost->list.head)
  {
    nameh = node->data;

    if (!irccmp(user, nameh->name))
    {
      nameh->gcount++;

      if (!global)
      {
        if (hasident)
          nameh->icount++;
        nameh->lcount++;
      }

      return;
    }
  }

  nameh = mp_pool_get(namehost_pool);
  nameh->gcount = 1;
  strlcpy(nameh->name, user, sizeof(nameh->name));

  if (!global)
  {
    if (hasident)
      nameh->icount = 1;

    nameh->lcount = 1;
  }

  dlinkAdd(nameh, &nameh->node, &found_userhost->list);
}

/* delete_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 * output       - none
 * side effects - delete given user@host to hash tables
 */
void
delete_user_host(const char *user, const char *host, int global)
{
  dlink_node *node = NULL;
  struct UserHost *found_userhost = NULL;
  unsigned int hasident = 1;

  if (*user == '~')
  {
    hasident = 0;
    ++user;
  }

  if ((found_userhost = hash_find_userhost(host)) == NULL)
    return;

  DLINK_FOREACH(node, found_userhost->list.head)
  {
    struct NameHost *nameh = node->data;

    if (!irccmp(user, nameh->name))
    {
      if (nameh->gcount > 0)
        nameh->gcount--;

      if (!global)
      {
        if (nameh->lcount > 0)
          nameh->lcount--;

        if (hasident && nameh->icount > 0)
          nameh->icount--;
      }

      if (nameh->gcount == 0 && nameh->lcount == 0)
      {
        dlinkDelete(&nameh->node, &found_userhost->list);
        mp_pool_release(nameh);
      }

      if (dlink_list_length(&found_userhost->list) == 0)
      {
        hash_del_userhost(found_userhost);
        mp_pool_release(found_userhost);
      }

      return;
    }
  }
}

/*
 * Safe list code.
 *
 * The idea is really quite simple. As the link lists pointed to in
 * each "bucket" of the channel hash table are traversed atomically
 * there is no locking needed. Overall, yes, inconsistent reported
 * state can still happen, but normally this isn't a big deal.
 * I don't like sticking the code into hash.c but oh well. Moreover,
 * if a hash isn't used in future, oops.
 *
 * - Dianora
 */

/* exceeding_sendq()
 *
 * inputs       - pointer to client to check
 * output       - 1 if client is in danger of blowing its sendq
 *                0 if it is not.
 * side effects -
 *
 * Sendq limit is fairly conservative at 1/2 (In original anyway)
 */
static int
exceeding_sendq(const struct Client *to)
{
  if (dbuf_length(&to->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
    return 1;
  else
    return 0;
}

void
free_list_task(struct Client *source_p)
{
  struct ListTask *const lt = source_p->connection->list_task;
  dlink_node *node = NULL, *node_next = NULL;

  if ((node = dlinkFindDelete(&listing_client_list, source_p)))
    free_dlink_node(node);

  DLINK_FOREACH_SAFE(node, node_next, lt->show_mask.head)
  {
    MyFree(node->data);
    free_dlink_node(node);
  }

  DLINK_FOREACH_SAFE(node, node_next, lt->hide_mask.head)
  {
    MyFree(node->data);
    free_dlink_node(node);
  }

  MyFree(lt);
  source_p->connection->list_task = NULL;
}

/* list_allow_channel()
 *
 * inputs       - channel name
 *              - pointer to a list task
 * output       - 1 if the channel is to be displayed
 *                0 otherwise
 * side effects -
 */
static int
list_allow_channel(const char *name, const struct ListTask *lt)
{
  const dlink_node *node = NULL;

  DLINK_FOREACH(node, lt->show_mask.head)
    if (match(node->data, name) != 0)
      return 0;

  DLINK_FOREACH(node, lt->hide_mask.head)
    if (match(node->data, name) == 0)
      return 0;

  return 1;
}

/* list_one_channel()
 *
 * inputs       - client pointer to return result to
 *              - pointer to channel to list
 *              - pointer to ListTask structure
 * output       - none
 * side effects -
 */
static void
list_one_channel(struct Client *source_p, struct Channel *chptr)
{
  const struct ListTask *const lt = source_p->connection->list_task;
  char listbuf[MODEBUFLEN] = "";
  char modebuf[MODEBUFLEN] = "";
  char parabuf[MODEBUFLEN] = "";

  if (SecretChannel(chptr) &&
      !(HasUMode(source_p, UMODE_ADMIN) || IsMember(source_p, chptr)))
    return;

  if (dlink_list_length(&chptr->members) < lt->users_min ||
      dlink_list_length(&chptr->members) > lt->users_max ||
      (chptr->creationtime != 0 &&
       ((unsigned int)chptr->creationtime < lt->created_min ||
        (unsigned int)chptr->creationtime > lt->created_max)) ||
      (unsigned int)chptr->topic_time < lt->topicts_min ||
      (chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
      lt->topicts_max)
    return;

  if (lt->topic[0] && match(lt->topic, chptr->topic))
    return;

  if (!list_allow_channel(chptr->name, lt))
    return;

  channel_modes(chptr, source_p, modebuf, parabuf);

  if (chptr->topic[0])
    snprintf(listbuf, sizeof(listbuf), "[%s] ", modebuf);
  else
    snprintf(listbuf, sizeof(listbuf), "[%s]",  modebuf);

  sendto_one_numeric(source_p, &me, RPL_LIST, chptr->name,
                     dlink_list_length(&chptr->members),
                     listbuf, chptr->topic);
}

/* safe_list_channels()
 *
 * inputs       - pointer to client requesting list
 * output       - 0/1
 * side effects - safely list all channels to source_p
 *
 * Walk the channel buckets, ensure all pointers in a bucket are
 * traversed before blocking on a sendq. This means, no locking is needed.
 *
 * - Dianora
 */
void
safe_list_channels(struct Client *source_p, int only_unmasked_channels)
{
  struct ListTask *const lt = source_p->connection->list_task;
  struct Channel *chptr = NULL;

  if (!only_unmasked_channels)
  {
    for (unsigned int i = lt->hash_index; i < HASHSIZE; ++i)
    {
      if (exceeding_sendq(source_p))
      {
        lt->hash_index = i;
        return;  /* Still more to do */
      }

      for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
        list_one_channel(source_p, chptr);
    }
  }
  else
  {
    dlink_node *node = NULL;

    DLINK_FOREACH(node, lt->show_mask.head)
      if ((chptr = hash_find_channel(node->data)))
        list_one_channel(source_p, chptr);
  }

  free_list_task(source_p);
  sendto_one_numeric(source_p, &me, RPL_LISTEND);
}
Revision:	6161
Committed:	Thu Jun 18 10:55:29 2015 UTC (10 years, 2 months ago) by michael
Content type:	text/x-csrc
File size:	19988 byte(s)
Log Message:	- Move all SID/UID related code to id.c
#	Content
1	/*
2	* ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3	*
4	* Copyright (c) 1997-2015 ircd-hybrid development team
5	*
6	* This program is free software; you can redistribute it and/or modify
7	* it under the terms of the GNU General Public License as published by
8	* the Free Software Foundation; either version 2 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with this program; if not, write to the Free Software
18	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
19	* USA
20	*/
21
22	/*! \file hash.c
23	* \brief Hash table management.
24	* \version $Id$
25	*/
26
27	#include "stdinc.h"
28	#include "list.h"
29	#include "conf.h"
30	#include "channel.h"
31	#include "channel_mode.h"
32	#include "client.h"
33	#include "modules.h"
34	#include "hash.h"
35	#include "id.h"
36	#include "resv.h"
37	#include "rng_mt.h"
38	#include "userhost.h"
39	#include "irc_string.h"
40	#include "ircd.h"
41	#include "numeric.h"
42	#include "send.h"
43	#include "memory.h"
44	#include "mempool.h"
45	#include "dbuf.h"
46	#include "user.h"
47
48
49	static mp_pool_t *userhost_pool;
50	static mp_pool_t *namehost_pool;
51
52	static unsigned int hashf_xor_key;
53
54	/* The actual hash tables, They MUST be of the same HASHSIZE, variable
55	* size tables could be supported but the rehash routine should also
56	* rebuild the transformation maps, I kept the tables of equal size
57	* so that I can use one hash function.
58	*/
59	static struct Client *idTable[HASHSIZE];
60	static struct Client *clientTable[HASHSIZE];
61	static struct Channel *channelTable[HASHSIZE];
62	static struct UserHost *userhostTable[HASHSIZE];
63
64
65	/* init_hash()
66	*
67	* inputs - NONE
68	* output - NONE
69	* side effects - Initialize the maps used by hash
70	* functions and clear the tables
71	*/
72	void
73	hash_init(void)
74	{
75	userhost_pool = mp_pool_new(sizeof(struct UserHost), MP_CHUNK_SIZE_USERHOST);
76	namehost_pool = mp_pool_new(sizeof(struct NameHost), MP_CHUNK_SIZE_NAMEHOST);
77
78	hashf_xor_key = genrand_int32() % 256; /* better than nothing --adx */
79	}
80
81	/*
82	* New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
83	* http://www.isthe.com/chongo/tech/comp/fnv/
84	*
85	* Here, we use the FNV-1 method, which gives slightly better results
86	* than FNV-1a. -Michael
87	*/
88	unsigned int
89	strhash(const char *name)
90	{
91	const unsigned char p = (const unsigned char )name;
92	unsigned int hval = FNV1_32_INIT;
93
94	if (EmptyString(p))
95	return 0;
96
97	for (; *p; ++p)
98	{
99	hval += (hval << 1) + (hval << 4) + (hval << 7) +
100	(hval << 8) + (hval << 24);
101	hval ^= (ToLower(*p) ^ hashf_xor_key);
102	}
103
104	return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
105	}
106
107	/************************ Externally visible functions ******************/
108
109	/* Optimization note: in these functions I supposed that the CSE optimization
110	* (Common Subexpression Elimination) does its work decently, this means that
111	* I avoided introducing new variables to do the work myself and I did let
112	* the optimizer play with more free registers, actual tests proved this
113	* solution to be faster than doing things like tmp2=tmp->hnext... and then
114	* use tmp2 myself which would have given less freedom to the optimizer.
115	*/
116
117	/* hash_add_client()
118	*
119	* inputs - pointer to client
120	* output - NONE
121	* side effects - Adds a client's name in the proper hash linked
122	* list, can't fail, client_p must have a non-null
123	* name or expect a coredump, the name is infact
124	* taken from client_p->name
125	*/
126	void
127	hash_add_client(struct Client *client_p)
128	{
129	const unsigned int hashv = strhash(client_p->name);
130
131	client_p->hnext = clientTable[hashv];
132	clientTable[hashv] = client_p;
133	}
134
135	/* hash_add_channel()
136	*
137	* inputs - pointer to channel
138	* output - NONE
139	* side effects - Adds a channel's name in the proper hash linked
140	* list, can't fail. chptr must have a non-null name
141	* or expect a coredump. As before the name is taken
142	* from chptr->name, we do hash its entire lenght
143	* since this proved to be statistically faster
144	*/
145	void
146	hash_add_channel(struct Channel *chptr)
147	{
148	const unsigned int hashv = strhash(chptr->name);
149
150	chptr->hnextch = channelTable[hashv];
151	channelTable[hashv] = chptr;
152	}
153
154	void
155	hash_add_userhost(struct UserHost *userhost)
156	{
157	const unsigned int hashv = strhash(userhost->host);
158
159	userhost->next = userhostTable[hashv];
160	userhostTable[hashv] = userhost;
161	}
162
163	void
164	hash_add_id(struct Client *client_p)
165	{
166	const unsigned int hashv = strhash(client_p->id);
167
168	client_p->idhnext = idTable[hashv];
169	idTable[hashv] = client_p;
170	}
171
172	/* hash_del_id()
173	*
174	* inputs - pointer to client
175	* output - NONE
176	* side effects - Removes an ID from the hash linked list
177	*/
178	void
179	hash_del_id(struct Client *client_p)
180	{
181	const unsigned int hashv = strhash(client_p->id);
182	struct Client *tmp = idTable[hashv];
183
184	if (tmp)
185	{
186	if (tmp == client_p)
187	{
188	idTable[hashv] = client_p->idhnext;
189	client_p->idhnext = client_p;
190	}
191	else
192	{
193	while (tmp->idhnext != client_p)
194	if ((tmp = tmp->idhnext) == NULL)
195	return;
196
197	tmp->idhnext = tmp->idhnext->idhnext;
198	client_p->idhnext = client_p;
199	}
200	}
201	}
202
203	/* hash_del_client()
204	*
205	* inputs - pointer to client
206	* output - NONE
207	* side effects - Removes a Client's name from the hash linked list
208	*/
209	void
210	hash_del_client(struct Client *client_p)
211	{
212	const unsigned int hashv = strhash(client_p->name);
213	struct Client *tmp = clientTable[hashv];
214
215	if (tmp)
216	{
217	if (tmp == client_p)
218	{
219	clientTable[hashv] = client_p->hnext;
220	client_p->hnext = client_p;
221	}
222	else
223	{
224	while (tmp->hnext != client_p)
225	if ((tmp = tmp->hnext) == NULL)
226	return;
227
228	tmp->hnext = tmp->hnext->hnext;
229	client_p->hnext = client_p;
230	}
231	}
232	}
233
234	/* hash_del_userhost()
235	*
236	* inputs - pointer to userhost
237	* output - NONE
238	* side effects - Removes a userhost from the hash linked list
239	*/
240	void
241	hash_del_userhost(struct UserHost *userhost)
242	{
243	const unsigned int hashv = strhash(userhost->host);
244	struct UserHost *tmp = userhostTable[hashv];
245
246	if (tmp)
247	{
248	if (tmp == userhost)
249	{
250	userhostTable[hashv] = userhost->next;
251	userhost->next = userhost;
252	}
253	else
254	{
255	while (tmp->next != userhost)
256	if ((tmp = tmp->next) == NULL)
257	return;
258
259	tmp->next = tmp->next->next;
260	userhost->next = userhost;
261	}
262	}
263	}
264
265	/* hash_del_channel()
266	*
267	* inputs - pointer to client
268	* output - NONE
269	* side effects - Removes the channel's name from the corresponding
270	* hash linked list
271	*/
272	void
273	hash_del_channel(struct Channel *chptr)
274	{
275	const unsigned int hashv = strhash(chptr->name);
276	struct Channel *tmp = channelTable[hashv];
277
278	if (tmp)
279	{
280	if (tmp == chptr)
281	{
282	channelTable[hashv] = chptr->hnextch;
283	chptr->hnextch = chptr;
284	}
285	else
286	{
287	while (tmp->hnextch != chptr)
288	if ((tmp = tmp->hnextch) == NULL)
289	return;
290
291	tmp->hnextch = tmp->hnextch->hnextch;
292	chptr->hnextch = chptr;
293	}
294	}
295	}
296
297	/* hash_find_client()
298	*
299	* inputs - pointer to name
300	* output - NONE
301	* side effects - New semantics: finds a client whose name is 'name'
302	* if can't find one returns NULL. If it finds one moves
303	* it to the top of the list and returns it.
304	*/
305	struct Client *
306	hash_find_client(const char *name)
307	{
308	const unsigned int hashv = strhash(name);
309	struct Client *client_p;
310
311	if ((client_p = clientTable[hashv]))
312	{
313	if (irccmp(name, client_p->name))
314	{
315	struct Client *prev;
316
317	while (prev = client_p, (client_p = client_p->hnext))
318	{
319	if (!irccmp(name, client_p->name))
320	{
321	prev->hnext = client_p->hnext;
322	client_p->hnext = clientTable[hashv];
323	clientTable[hashv] = client_p;
324	break;
325	}
326	}
327	}
328	}
329
330	return client_p;
331	}
332
333	struct Client *
334	hash_find_id(const char *name)
335	{
336	const unsigned int hashv = strhash(name);
337	struct Client *client_p;
338
339	if ((client_p = idTable[hashv]))
340	{
341	if (strcmp(name, client_p->id))
342	{
343	struct Client *prev;
344
345	while (prev = client_p, (client_p = client_p->idhnext))
346	{
347	if (!strcmp(name, client_p->id))
348	{
349	prev->idhnext = client_p->idhnext;
350	client_p->idhnext = idTable[hashv];
351	idTable[hashv] = client_p;
352	break;
353	}
354	}
355	}
356	}
357
358	return client_p;
359	}
360
361	struct Client *
362	hash_find_server(const char *name)
363	{
364	const unsigned int hashv = strhash(name);
365	struct Client *client_p = NULL;
366
367	if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
368	return hash_find_id(name);
369
370	if ((client_p = clientTable[hashv]))
371	{
372	if ((!IsServer(client_p) && !IsMe(client_p)) \|\|
373	irccmp(name, client_p->name))
374	{
375	struct Client *prev;
376
377	while (prev = client_p, (client_p = client_p->hnext))
378	{
379	if ((IsServer(client_p) \|\| IsMe(client_p)) &&
380	!irccmp(name, client_p->name))
381	{
382	prev->hnext = client_p->hnext;
383	client_p->hnext = clientTable[hashv];
384	clientTable[hashv] = client_p;
385	break;
386	}
387	}
388	}
389	}
390
391	return client_p;
392	}
393
394	/* hash_find_channel()
395	*
396	* inputs - pointer to name
397	* output - NONE
398	* side effects - New semantics: finds a channel whose name is 'name',
399	* if can't find one returns NULL, if can find it moves
400	* it to the top of the list and returns it.
401	*/
402	struct Channel *
403	hash_find_channel(const char *name)
404	{
405	const unsigned int hashv = strhash(name);
406	struct Channel *chptr = NULL;
407
408	if ((chptr = channelTable[hashv]))
409	{
410	if (irccmp(name, chptr->name))
411	{
412	struct Channel *prev;
413
414	while (prev = chptr, (chptr = chptr->hnextch))
415	{
416	if (!irccmp(name, chptr->name))
417	{
418	prev->hnextch = chptr->hnextch;
419	chptr->hnextch = channelTable[hashv];
420	channelTable[hashv] = chptr;
421	break;
422	}
423	}
424	}
425	}
426
427	return chptr;
428	}
429
430	/* hash_get_bucket(int type, unsigned int hashv)
431	*
432	* inputs - hash value (must be between 0 and HASHSIZE - 1)
433	* output - NONE
434	* returns - pointer to first channel in channelTable[hashv]
435	* if that exists;
436	* NULL if there is no channel in that place;
437	* NULL if hashv is an invalid number.
438	* side effects - NONE
439	*/
440	void *
441	hash_get_bucket(int type, unsigned int hashv)
442	{
443	assert(hashv < HASHSIZE);
444
445	if (hashv >= HASHSIZE)
446	return NULL;
447
448	switch (type)
449	{
450	case HASH_TYPE_ID:
451	return idTable[hashv];
452	break;
453	case HASH_TYPE_CHANNEL:
454	return channelTable[hashv];
455	break;
456	case HASH_TYPE_CLIENT:
457	return clientTable[hashv];
458	break;
459	case HASH_TYPE_USERHOST:
460	return userhostTable[hashv];
461	break;
462	default:
463	assert(0);
464	}
465
466	return NULL;
467	}
468
469	struct UserHost *
470	hash_find_userhost(const char *host)
471	{
472	const unsigned int hashv = strhash(host);
473	struct UserHost *userhost;
474
475	if ((userhost = userhostTable[hashv]))
476	{
477	if (irccmp(host, userhost->host))
478	{
479	struct UserHost *prev;
480
481	while (prev = userhost, (userhost = userhost->next))
482	{
483	if (!irccmp(host, userhost->host))
484	{
485	prev->next = userhost->next;
486	userhost->next = userhostTable[hashv];
487	userhostTable[hashv] = userhost;
488	break;
489	}
490	}
491	}
492	}
493
494	return userhost;
495	}
496
497	/* count_user_host()
498	*
499	* inputs - user name
500	* - hostname
501	* - int flag 1 if global, 0 if local
502	* - pointer to where global count should go
503	* - pointer to where local count should go
504	* - pointer to where identd count should go (local clients only)
505	* output - none
506	* side effects -
507	*/
508	void
509	count_user_host(const char user, const char host, unsigned int *global_p,
510	unsigned int local_p, unsigned int icount_p)
511	{
512	dlink_node *node = NULL;
513	struct UserHost *found_userhost;
514
515	if ((found_userhost = hash_find_userhost(host)) == NULL)
516	return;
517
518	DLINK_FOREACH(node, found_userhost->list.head)
519	{
520	struct NameHost *nameh = node->data;
521
522	if (!irccmp(user, nameh->name))
523	{
524	if (global_p)
525	*global_p = nameh->gcount;
526	if (local_p)
527	*local_p = nameh->lcount;
528	if (icount_p)
529	*icount_p = nameh->icount;
530
531	return;
532	}
533	}
534	}
535
536	/* find_or_add_userhost()
537	*
538	* inputs - host name
539	* output - none
540	* side effects - find UserHost * for given host name
541	*/
542	static struct UserHost *
543	find_or_add_userhost(const char *host)
544	{
545	struct UserHost *userhost = NULL;
546
547	if ((userhost = hash_find_userhost(host)))
548	return userhost;
549
550	userhost = mp_pool_get(userhost_pool);
551
552	strlcpy(userhost->host, host, sizeof(userhost->host));
553	hash_add_userhost(userhost);
554
555	return userhost;
556	}
557
558	/* add_user_host()
559	*
560	* inputs - user name
561	* - hostname
562	* - int flag 1 if global, 0 if local
563	* output - none
564	* side effects - add given user@host to hash tables
565	*/
566	void
567	add_user_host(const char user, const char host, int global)
568	{
569	dlink_node *node = NULL;
570	struct UserHost *found_userhost;
571	struct NameHost *nameh;
572	unsigned int hasident = 1;
573
574	if (*user == '~')
575	{
576	hasident = 0;
577	++user;
578	}
579
580	if ((found_userhost = find_or_add_userhost(host)) == NULL)
581	return;
582
583	DLINK_FOREACH(node, found_userhost->list.head)
584	{
585	nameh = node->data;
586
587	if (!irccmp(user, nameh->name))
588	{
589	nameh->gcount++;
590
591	if (!global)
592	{
593	if (hasident)
594	nameh->icount++;
595	nameh->lcount++;
596	}
597
598	return;
599	}
600	}
601
602	nameh = mp_pool_get(namehost_pool);
603	nameh->gcount = 1;
604	strlcpy(nameh->name, user, sizeof(nameh->name));
605
606	if (!global)
607	{
608	if (hasident)
609	nameh->icount = 1;
610
611	nameh->lcount = 1;
612	}
613
614	dlinkAdd(nameh, &nameh->node, &found_userhost->list);
615	}
616
617	/* delete_user_host()
618	*
619	* inputs - user name
620	* - hostname
621	* - int flag 1 if global, 0 if local
622	* output - none
623	* side effects - delete given user@host to hash tables
624	*/
625	void
626	delete_user_host(const char user, const char host, int global)
627	{
628	dlink_node *node = NULL;
629	struct UserHost *found_userhost = NULL;
630	unsigned int hasident = 1;
631
632	if (*user == '~')
633	{
634	hasident = 0;
635	++user;
636	}
637
638	if ((found_userhost = hash_find_userhost(host)) == NULL)
639	return;
640
641	DLINK_FOREACH(node, found_userhost->list.head)
642	{
643	struct NameHost *nameh = node->data;
644
645	if (!irccmp(user, nameh->name))
646	{
647	if (nameh->gcount > 0)
648	nameh->gcount--;
649
650	if (!global)
651	{
652	if (nameh->lcount > 0)
653	nameh->lcount--;
654
655	if (hasident && nameh->icount > 0)
656	nameh->icount--;
657	}
658
659	if (nameh->gcount == 0 && nameh->lcount == 0)
660	{
661	dlinkDelete(&nameh->node, &found_userhost->list);
662	mp_pool_release(nameh);
663	}
664
665	if (dlink_list_length(&found_userhost->list) == 0)
666	{
667	hash_del_userhost(found_userhost);
668	mp_pool_release(found_userhost);
669	}
670
671	return;
672	}
673	}
674	}
675
676	/*
677	* Safe list code.
678	*
679	* The idea is really quite simple. As the link lists pointed to in
680	* each "bucket" of the channel hash table are traversed atomically
681	* there is no locking needed. Overall, yes, inconsistent reported
682	* state can still happen, but normally this isn't a big deal.
683	* I don't like sticking the code into hash.c but oh well. Moreover,
684	* if a hash isn't used in future, oops.
685	*
686	* - Dianora
687	*/
688
689	/* exceeding_sendq()
690	*
691	* inputs - pointer to client to check
692	* output - 1 if client is in danger of blowing its sendq
693	* 0 if it is not.
694	* side effects -
695	*
696	* Sendq limit is fairly conservative at 1/2 (In original anyway)
697	*/
698	static int
699	exceeding_sendq(const struct Client *to)
700	{
701	if (dbuf_length(&to->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
702	return 1;
703	else
704	return 0;
705	}
706
707	void
708	free_list_task(struct Client *source_p)
709	{
710	struct ListTask *const lt = source_p->connection->list_task;
711	dlink_node node = NULL, node_next = NULL;
712
713	if ((node = dlinkFindDelete(&listing_client_list, source_p)))
714	free_dlink_node(node);
715
716	DLINK_FOREACH_SAFE(node, node_next, lt->show_mask.head)
717	{
718	MyFree(node->data);
719	free_dlink_node(node);
720	}
721
722	DLINK_FOREACH_SAFE(node, node_next, lt->hide_mask.head)
723	{
724	MyFree(node->data);
725	free_dlink_node(node);
726	}
727
728	MyFree(lt);
729	source_p->connection->list_task = NULL;
730	}
731
732	/* list_allow_channel()
733	*
734	* inputs - channel name
735	* - pointer to a list task
736	* output - 1 if the channel is to be displayed
737	* 0 otherwise
738	* side effects -
739	*/
740	static int
741	list_allow_channel(const char name, const struct ListTask lt)
742	{
743	const dlink_node *node = NULL;
744
745	DLINK_FOREACH(node, lt->show_mask.head)
746	if (match(node->data, name) != 0)
747	return 0;
748
749	DLINK_FOREACH(node, lt->hide_mask.head)
750	if (match(node->data, name) == 0)
751	return 0;
752
753	return 1;
754	}
755
756	/* list_one_channel()
757	*
758	* inputs - client pointer to return result to
759	* - pointer to channel to list
760	* - pointer to ListTask structure
761	* output - none
762	* side effects -
763	*/
764	static void
765	list_one_channel(struct Client source_p, struct Channel chptr)
766	{
767	const struct ListTask *const lt = source_p->connection->list_task;
768	char listbuf[MODEBUFLEN] = "";
769	char modebuf[MODEBUFLEN] = "";
770	char parabuf[MODEBUFLEN] = "";
771
772	if (SecretChannel(chptr) &&
773	!(HasUMode(source_p, UMODE_ADMIN) \|\| IsMember(source_p, chptr)))
774	return;
775
776	if (dlink_list_length(&chptr->members) < lt->users_min \|\|
777	dlink_list_length(&chptr->members) > lt->users_max \|\|
778	(chptr->creationtime != 0 &&
779	((unsigned int)chptr->creationtime < lt->created_min \|\|
780	(unsigned int)chptr->creationtime > lt->created_max)) \|\|
781	(unsigned int)chptr->topic_time < lt->topicts_min \|\|
782	(chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
783	lt->topicts_max)
784	return;
785
786	if (lt->topic[0] && match(lt->topic, chptr->topic))
787	return;
788
789	if (!list_allow_channel(chptr->name, lt))
790	return;
791
792	channel_modes(chptr, source_p, modebuf, parabuf);
793
794	if (chptr->topic[0])
795	snprintf(listbuf, sizeof(listbuf), "[%s] ", modebuf);
796	else
797	snprintf(listbuf, sizeof(listbuf), "[%s]", modebuf);
798
799	sendto_one_numeric(source_p, &me, RPL_LIST, chptr->name,
800	dlink_list_length(&chptr->members),
801	listbuf, chptr->topic);
802	}
803
804	/* safe_list_channels()
805	*
806	* inputs - pointer to client requesting list
807	* output - 0/1
808	* side effects - safely list all channels to source_p
809	*
810	* Walk the channel buckets, ensure all pointers in a bucket are
811	* traversed before blocking on a sendq. This means, no locking is needed.
812	*
813	* - Dianora
814	*/
815	void
816	safe_list_channels(struct Client *source_p, int only_unmasked_channels)
817	{
818	struct ListTask *const lt = source_p->connection->list_task;
819	struct Channel *chptr = NULL;
820
821	if (!only_unmasked_channels)
822	{
823	for (unsigned int i = lt->hash_index; i < HASHSIZE; ++i)
824	{
825	if (exceeding_sendq(source_p))
826	{
827	lt->hash_index = i;
828	return; /* Still more to do */
829	}
830
831	for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
832	list_one_channel(source_p, chptr);
833	}
834	}
835	else
836	{
837	dlink_node *node = NULL;
838
839	DLINK_FOREACH(node, lt->show_mask.head)
840	if ((chptr = hash_find_channel(node->data)))
841	list_one_channel(source_p, chptr);
842	}
843
844	free_list_task(source_p);
845	sendto_one_numeric(source_p, &me, RPL_LISTEND);
846	}