ircd/list.c

   1 /*
   2  * IRC - Internet Relay Chat, ircd/list.c
   3  * Copyright (C) 1990 Jarkko Oikarinen and
   4  *                    University of Oulu, Finland
   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 1, or (at your option)
   9  * 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., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  */
  20 /** @file
  21  * @brief Singly and doubly linked list manipulation implementation.
  22  * @version $Id$
  23  */
  24 #include "config.h"
  25
  26 #include "list.h"
  27 #include "client.h"
  28 #include "ircd.h"
  29 #include "ircd_alloc.h"
  30 #include "ircd_events.h"
  31 #include "ircd_log.h"
  32 #include "ircd_reply.h"
  33 #include "ircd_string.h"
  34 #include "listener.h"
  35 #include "match.h"
  36 #include "numeric.h"
  37 #include "res.h"
  38 #include "s_auth.h"
  39 #include "s_bsd.h"
  40 #include "s_conf.h"
  41 #include "s_debug.h"
  42 #include "s_misc.h"
  43 #include "s_user.h"
  44 #include "send.h"
  45 #include "struct.h"
  46 #include "whowas.h"
  47
  48 /* #include <assert.h> -- Now using assert in ircd_log.h */
  49 #include <stddef.h>  /* offsetof */
  50 #include <unistd.h>  /* close */
  51 #include <string.h>
  52
  53 #ifdef DEBUGMODE
  54 /** Stores linked list statistics for various types of lists. */
  55 static struct liststats {
  56   int inuse;
  57 } clients, connections, users, servs, links;
  58 #endif
  59
  60 /** Count of allocated Client structures. */
  61 static unsigned int clientAllocCount;
  62 /** Linked list of currently unused Client structures. */
  63 static struct Client* clientFreeList;
  64
  65 /** Count of allocated Connection structures. */
  66 static unsigned int connectionAllocCount;
  67 /** Linked list of currently unused Connection structures. */
  68 static struct Connection* connectionFreeList;
  69
  70 /** Count of allocated SLink structures. */
  71 static unsigned int slinkAllocCount;
  72 /** Linked list of currently unused SLink structures. */
  73 static struct SLink* slinkFreeList;
  74
  75 /** Initialize the list manipulation support system.
  76  * Pre-allocate MAXCONNECTIONS Client and Connection structures.
  77  */
  78 void init_list(void)
  79 {
  80   struct Client* cptr;
  81   struct Connection* con;
  82   int i;
  83   /*
  84    * pre-allocate MAXCONNECTIONS clients and connections
  85    */
  86   for (i = 0; i < MAXCONNECTIONS; ++i) {
  87     cptr = (struct Client*) MyMalloc(sizeof(struct Client));
  88     cli_next(cptr) = clientFreeList;
  89     clientFreeList = cptr;
  90     ++clientAllocCount;
  91
  92     con = (struct Connection*) MyMalloc(sizeof(struct Connection));
  93     con_next(con) = connectionFreeList;
  94     connectionFreeList = con;
  95     ++connectionAllocCount;
  96   }
  97
  98 #ifdef DEBUGMODE
  99   memset(&clients, 0, sizeof(clients));
 100   memset(&connections, 0, sizeof(connections));
 101   memset(&users, 0, sizeof(users));
 102   memset(&servs, 0, sizeof(servs));
 103   memset(&links, 0, sizeof(links));
 104 #endif
 105 }
 106
 107 /** Allocate a new Client structure.
 108  * If #clientFreeList != NULL, use the head of that list.
 109  * Otherwise, allocate a new structure.
 110  * @return Newly allocated Client.
 111  */
 112 static struct Client* alloc_client(void)
 113 {
 114   struct Client* cptr = clientFreeList;
 115
 116   if (!cptr) {
 117     cptr = (struct Client*) MyMalloc(sizeof(struct Client));
 118     ++clientAllocCount;
 119   } else
 120     clientFreeList = cli_next(cptr);
 121
 122 #ifdef DEBUGMODE
 123   clients.inuse++;
 124 #endif
 125
 126   memset(cptr, 0, sizeof(struct Client));
 127
 128   return cptr;
 129 }
 130
 131 /** Release a Client structure by prepending it to #clientFreeList.
 132  * @param[in] cptr Client that is no longer being used.
 133  */
 134 static void dealloc_client(struct Client* cptr)
 135 {
 136   assert(cli_verify(cptr));
 137   assert(0 == cli_connect(cptr));
 138
 139 #ifdef DEBUGMODE
 140   --clients.inuse;
 141 #endif
 142
 143   cli_next(cptr) = clientFreeList;
 144   clientFreeList = cptr;
 145
 146   cli_magic(cptr) = 0;
 147 }
 148
 149 /** Allocate a new Connection structure.
 150  * If #connectionFreeList != NULL, use the head of that list.
 151  * Otherwise, allocate a new structure.
 152  * @return Newly allocated Connection.
 153  */
 154 static struct Connection* alloc_connection(void)
 155 {
 156   struct Connection* con = connectionFreeList;
 157
 158   if (!con) {
 159     con = (struct Connection*) MyMalloc(sizeof(struct Connection));
 160     ++connectionAllocCount;
 161   } else
 162     connectionFreeList = con_next(con);
 163
 164 #ifdef DEBUGMODE
 165   connections.inuse++;
 166 #endif
 167
 168   memset(con, 0, sizeof(struct Connection));
 169   timer_init(&(con_proc(con)));
 170
 171   return con;
 172 }
 173
 174 /** Release a Connection and all memory associated with it.
 175  * The connection's DNS reply field is freed, its file descriptor is
 176  * closed, its msgq and sendq are cleared, and its associated Listener
 177  * is dereferenced.  Then it is prepended to #connectionFreeList.
 178  * @param[in] con Connection to free.
 179  */
 180 static void dealloc_connection(struct Connection* con)
 181 {
 182   assert(con_verify(con));
 183   assert(!t_active(&(con_proc(con))));
 184   assert(!t_onqueue(&(con_proc(con))));
 185
 186   Debug((DEBUG_LIST, "Deallocating connection %p", con));
 187
 188   if (con_dns_reply(con)) {
 189     MyFree(con_dns_reply(con));
 190     con_dns_reply(con) = 0;
 191   }
 192   if (-1 < con_fd(con))
 193     close(con_fd(con));
 194   MsgQClear(&(con_sendQ(con)));
 195   client_drop_sendq(con);
 196   DBufClear(&(con_recvQ(con)));
 197   if (con_listener(con))
 198     release_listener(con_listener(con));
 199
 200 #ifdef DEBUGMODE
 201   --connections.inuse;
 202 #endif
 203
 204   con_next(con) = connectionFreeList;
 205   connectionFreeList = con;
 206
 207   con_magic(con) = 0;
 208 }
 209
 210 /** Allocate a new client and initialize it.
 211  * If \a from == NULL, initialize the fields for a local client,
 212  * including allocating a Connection for him; otherwise initialize the
 213  * fields for a remote client..
 214  * @param[in] from Server connection that introduced the client (or
 215  * NULL).
 216  * @param[in] status Initial Client::cli_status value.
 217  * @return Newly allocated and initialized Client.
 218  */
 219 struct Client* make_client(struct Client *from, int status)
 220 {
 221   struct Client* cptr = 0;
 222
 223   assert(!from || cli_verify(from));
 224
 225   cptr = alloc_client();
 226
 227   assert(0 != cptr);
 228   assert(!cli_magic(cptr));
 229   assert(0 == from || 0 != cli_connect(from));
 230
 231   if (!from) { /* local client, allocate a struct Connection */
 232     struct Connection *con = alloc_connection();
 233
 234     assert(0 != con);
 235     assert(!con_magic(con));
 236
 237     con_magic(con) = CONNECTION_MAGIC;
 238     con_fd(con) = -1; /* initialize struct Connection */
 239     con_freeflag(con) = 0;
 240     con_nextnick(con) = CurrentTime - NICK_DELAY;
 241     con_nexttarget(con) = CurrentTime - (TARGET_DELAY * (STARTTARGETS - 1));
 242     con_handler(con) = UNREGISTERED_HANDLER;
 243     con_client(con) = cptr;
 244
 245     cli_connect(cptr) = con; /* set the connection and other fields */
 246     cli_since(cptr) = cli_lasttime(cptr) = cli_firsttime(cptr) = CurrentTime;
 247     cli_lastnick(cptr) = TStime();
 248     cli_unreg(cptr) = CLIREG_INIT;
 249   } else
 250     cli_connect(cptr) = cli_connect(from); /* use 'from's connection */
 251
 252   assert(con_verify(cli_connect(cptr)));
 253
 254   cli_magic(cptr) = CLIENT_MAGIC;
 255   cli_status(cptr) = status;
 256   cli_hnext(cptr) = cptr;
 257   strcpy(cli_username(cptr), "unknown");
 258
 259   return cptr;
 260 }
 261
 262 /** Release a Connection.
 263  * @param[in] con Connection to free.
 264  */
 265 void free_connection(struct Connection* con)
 266 {
 267   if (!con)
 268     return;
 269
 270   assert(con_verify(con));
 271   assert(0 == con_client(con));
 272
 273   dealloc_connection(con); /* deallocate the connection */
 274 }
 275
 276 /** Release a Client.
 277  * In addition to the cleanup done by dealloc_client(), this will free
 278  * any pending auth request, free the connection for local clients,
 279  * and delete the processing timer for the client.
 280  * @param[in] cptr Client to free.
 281  */
 282 void free_client(struct Client* cptr)
 283 {
 284   if (!cptr)
 285     return;
 286   /*
 287    * forget to remove the client from the hash table?
 288    */
 289   assert(cli_verify(cptr));
 290   assert(cli_hnext(cptr) == cptr);
 291   /* or from linked list? */
 292   assert(cli_next(cptr) == 0);
 293   assert(cli_prev(cptr) == 0);
 294
 295   Debug((DEBUG_LIST, "Freeing client %s [%p], connection %p", cli_name(cptr),
 296          cptr, cli_connect(cptr)));
 297
 298   if (cli_auth(cptr))
 299     destroy_auth_request(cli_auth(cptr), 0);
 300
 301   /* Make sure we didn't magically get re-added to the list */
 302   assert(cli_next(cptr) == 0);
 303   assert(cli_prev(cptr) == 0);
 304
 305   if (cli_from(cptr) == cptr) { /* in other words, we're local */
 306     cli_from(cptr) = 0;
 307     /* timer must be marked as not active */
 308     if (!cli_freeflag(cptr) && !t_active(&(cli_proc(cptr))))
 309       dealloc_connection(cli_connect(cptr)); /* connection not open anymore */
 310     else {
 311       if (-1 < cli_fd(cptr) && cli_freeflag(cptr) & FREEFLAG_SOCKET)
 312         socket_del(&(cli_socket(cptr))); /* queue a socket delete */
 313       if (cli_freeflag(cptr) & FREEFLAG_TIMER)
 314         timer_del(&(cli_proc(cptr))); /* queue a timer delete */
 315     }
 316   }
 317
 318   cli_connect(cptr) = 0;
 319
 320   dealloc_client(cptr); /* actually destroy the client */
 321 }
 322
 323 /** Allocate a new Server object for a client.
 324  * If Client::cli_serv == NULL, allocate a Server structure for it and
 325  * initialize it.
 326  * @param[in] cptr %Client to make into a server.
 327  * @return The value of cli_serv(\a cptr).
 328  */
 329 struct Server *make_server(struct Client *cptr)
 330 {
 331   struct Server *serv = cli_serv(cptr);
 332
 333   assert(cli_verify(cptr));
 334
 335   if (!serv)
 336   {
 337     serv = (struct Server*) MyMalloc(sizeof(struct Server));
 338     assert(0 != serv);
 339     memset(serv, 0, sizeof(struct Server)); /* All variables are 0 by default */
 340 #ifdef  DEBUGMODE
 341     servs.inuse++;
 342 #endif
 343     cli_serv(cptr) = serv;
 344     cli_serv(cptr)->lag = 60000;
 345     *serv->by = '\0';
 346     DupString(serv->last_error_msg, "<>");      /* String must be non-empty */
 347   }
 348   return cli_serv(cptr);
 349 }
 350
 351 /** Remove \a cptr from lists that it is a member of.
 352  * Specifically, this delinks \a cptr from #GlobalClientList, updates
 353  * the whowas history list, frees its Client::cli_user and
 354  * Client::cli_serv fields, and finally calls free_client() on it.
 355  * @param[in] cptr Client to remove from lists and free.
 356  */
 357 void remove_client_from_list(struct Client *cptr)
 358 {
 359   assert(cli_verify(cptr));
 360   assert(con_verify(cli_connect(cptr)));
 361   assert(!cli_prev(cptr) || cli_verify(cli_prev(cptr)));
 362   assert(!cli_next(cptr) || cli_verify(cli_next(cptr)));
 363   assert(!IsMe(cptr));
 364
 365   /* Only try remove cptr from the list if it IS in the list.
 366    * cli_next(cptr) cannot be NULL here, as &me is always the end
 367    * the list, and we never remove &me.    -GW
 368    */
 369   if(cli_next(cptr))
 370   {
 371     if (cli_prev(cptr))
 372       cli_next(cli_prev(cptr)) = cli_next(cptr);
 373     else {
 374       GlobalClientList = cli_next(cptr);
 375       cli_prev(GlobalClientList) = 0;
 376     }
 377     cli_prev(cli_next(cptr)) = cli_prev(cptr);
 378   }
 379   cli_next(cptr) = cli_prev(cptr) = 0;
 380
 381   if (IsUser(cptr) && cli_user(cptr)) {
 382     add_history(cptr, 0);
 383     off_history(cptr);
 384   }
 385   if (cli_user(cptr)) {
 386     free_user(cli_user(cptr));
 387     cli_user(cptr) = 0;
 388   }
 389
 390   if (cli_serv(cptr)) {
 391     if (cli_serv(cptr)->user) {
 392       free_user(cli_serv(cptr)->user);
 393       cli_serv(cptr)->user = 0;
 394     }
 395     if (cli_serv(cptr)->client_list)
 396       MyFree(cli_serv(cptr)->client_list);
 397     MyFree(cli_serv(cptr)->last_error_msg);
 398     MyFree(cli_serv(cptr));
 399 #ifdef  DEBUGMODE
 400     --servs.inuse;
 401 #endif
 402   }
 403   free_client(cptr);
 404 }
 405
 406 /** Link \a cptr into #GlobalClientList.
 407  * @param[in] cptr Client to link into the global list.
 408  */
 409 void add_client_to_list(struct Client *cptr)
 410 {
 411   assert(cli_verify(cptr));
 412   assert(cli_next(cptr) == 0);
 413   assert(cli_prev(cptr) == 0);
 414
 415   /*
 416    * Since we always insert new clients to the top of the list,
 417    * this should mean the "me" is the bottom most item in the list.
 418    * XXX - don't always count on the above, things change
 419    */
 420   cli_prev(cptr) = 0;
 421   cli_next(cptr) = GlobalClientList;
 422   GlobalClientList = cptr;
 423   if (cli_next(cptr))
 424     cli_prev(cli_next(cptr)) = cptr;
 425 }
 426
 427 #if 0
 428 /** Perform a very CPU-intensive verification of %GlobalClientList.
 429  * This checks the Client::cli_magic and Client::cli_prev field for
 430  * each element in the list, and also checks that there are no loops.
 431  * Any detected error will lead to an assertion failure.
 432  */
 433 void verify_client_list(void)
 434 {
 435   struct Client *client, *prev = 0;
 436   unsigned int visited = 0;
 437
 438   for (client = GlobalClientList; client; client = cli_next(client), ++visited) {
 439     /* Verify that this is a valid client, not a free'd one */
 440     assert(cli_verify(client));
 441     /* Verify that the list hasn't suddenly jumped around */
 442     assert(cli_prev(client) == prev);
 443     /* Verify that the list hasn't become circular */
 444     assert(cli_next(client) != GlobalClientList);
 445     assert(visited <= clientAllocCount);
 446     /* Remember what should precede us */
 447     prev = client;
 448   }
 449 }
 450 #endif /* DEBUGMODE */
 451
 452 /** Allocate a new SLink element.
 453  * Pulls from #slinkFreeList if it contains anything, else it
 454  * allocates a new one from the heap.
 455  * @return Newly allocated list element.
 456  */
 457 struct SLink* make_link(void)
 458 {
 459   struct SLink* lp = slinkFreeList;
 460   if (lp)
 461     slinkFreeList = lp->next;
 462   else {
 463     lp = (struct SLink*) MyMalloc(sizeof(struct SLink));
 464     ++slinkAllocCount;
 465   }
 466   assert(0 != lp);
 467 #ifdef  DEBUGMODE
 468   links.inuse++;
 469 #endif
 470   return lp;
 471 }
 472
 473 /** Release a singly linked list element.
 474  * @param[in] lp List element to mark as unused.
 475  */
 476 void free_link(struct SLink* lp)
 477 {
 478   if (lp) {
 479     lp->next = slinkFreeList;
 480     slinkFreeList = lp;
 481   }
 482 #ifdef  DEBUGMODE
 483   links.inuse--;
 484 #endif
 485 }
 486
 487 /** Add an element to a doubly linked list.
 488  * If \a lpp points to a non-NULL pointer, its DLink::prev field is
 489  * updated to point to the newly allocated element.  Regardless,
 490  * \a lpp is overwritten with the pointer to the new link.
 491  * @param[in,out] lpp Pointer to insertion location.
 492  * @param[in] cp %Client to put in newly allocated element.
 493  * @return Allocated link structure (same as \a lpp on output).
 494  */
 495 struct DLink *add_dlink(struct DLink **lpp, struct Client *cp)
 496 {
 497   struct DLink* lp = (struct DLink*) MyMalloc(sizeof(struct DLink));
 498   assert(0 != lp);
 499   lp->value.cptr = cp;
 500   lp->prev = 0;
 501   if ((lp->next = *lpp))
 502     lp->next->prev = lp;
 503   *lpp = lp;
 504   return lp;
 505 }
 506
 507 /** Remove a node from a doubly linked list.
 508  * @param[out] lpp Pointer to next list element.
 509  * @param[in] lp List node to unlink.
 510  */
 511 void remove_dlink(struct DLink **lpp, struct DLink *lp)
 512 {
 513   assert(0 != lpp);
 514   assert(0 != lp);
 515
 516   if (lp->prev) {
 517     if ((lp->prev->next = lp->next))
 518       lp->next->prev = lp->prev;
 519   }
 520   else if ((*lpp = lp->next))
 521     lp->next->prev = NULL;
 522   MyFree(lp);
 523 }
 524
 525 #ifdef  DEBUGMODE
 526 /** Report memory usage of list elements to \a cptr.
 527  * @param[in] cptr Client requesting information.
 528  * @param[in] name Unused pointer.
 529  */
 530 void send_listinfo(struct Client *cptr, char *name)
 531 {
 532   int inuse = 0, mem = 0, tmp = 0;
 533
 534   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Clients: inuse: %d(%d)",
 535              clients.inuse, tmp = clients.inuse * sizeof(struct Client));
 536   mem += tmp;
 537   inuse += clients.inuse;
 538   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, "Connections: inuse: %d(%d)",
 539              connections.inuse,
 540              tmp = connections.inuse * sizeof(struct Connection));
 541   mem += tmp;
 542   inuse += connections.inuse;
 543   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Users: inuse: %d(%d)",
 544              users.inuse, tmp = users.inuse * sizeof(struct User));
 545   mem += tmp;
 546   inuse += users.inuse;
 547   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Servs: inuse: %d(%d)",
 548              servs.inuse, tmp = servs.inuse * sizeof(struct Server));
 549   mem += tmp;
 550   inuse += servs.inuse;
 551   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Links: inuse: %d(%d)",
 552              links.inuse, tmp = links.inuse * sizeof(struct SLink));
 553   mem += tmp;
 554   inuse += links.inuse;
 555   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Confs: inuse: %d(%d)",
 556              GlobalConfCount, tmp = GlobalConfCount * sizeof(struct ConfItem));
 557   mem += tmp;
 558   inuse += GlobalConfCount;
 559   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Totals: inuse %d %d",
 560              inuse, mem);
 561 }
 562
 563 #endif