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   } else
 249     cli_connect(cptr) = cli_connect(from); /* use 'from's connection */
 250
 251   assert(con_verify(cli_connect(cptr)));
 252
 253   cli_magic(cptr) = CLIENT_MAGIC;
 254   cli_status(cptr) = status;
 255   cli_hnext(cptr) = cptr;
 256   strcpy(cli_username(cptr), "unknown");
 257
 258   return cptr;
 259 }
 260
 261 /** Release a Connection.
 262  * @param[in] con Connection to free.
 263  */
 264 void free_connection(struct Connection* con)
 265 {
 266   if (!con)
 267     return;
 268
 269   assert(con_verify(con));
 270   assert(0 == con_client(con));
 271
 272   dealloc_connection(con); /* deallocate the connection */
 273 }
 274
 275 /** Release a Client.
 276  * In addition to the cleanup done by dealloc_client(), this will free
 277  * any pending auth request, free the connection for local clients,
 278  * and delete the processing timer for the client.
 279  * @param[in] cptr Client to free.
 280  */
 281 void free_client(struct Client* cptr)
 282 {
 283   if (!cptr)
 284     return;
 285   /*
 286    * forget to remove the client from the hash table?
 287    */
 288   assert(cli_verify(cptr));
 289   assert(cli_hnext(cptr) == cptr);
 290   /* or from linked list? */
 291   assert(cli_next(cptr) == 0);
 292   assert(cli_prev(cptr) == 0);
 293
 294   Debug((DEBUG_LIST, "Freeing client %s [%p], connection %p", cli_name(cptr),
 295          cptr, cli_connect(cptr)));
 296
 297   if (cli_auth(cptr))
 298     destroy_auth_request(cli_auth(cptr), 0);
 299
 300   /* Make sure we didn't magically get re-added to the list */
 301   assert(cli_next(cptr) == 0);
 302   assert(cli_prev(cptr) == 0);
 303
 304   if (cli_from(cptr) == cptr) { /* in other words, we're local */
 305     cli_from(cptr) = 0;
 306     /* timer must be marked as not active */
 307     if (!cli_freeflag(cptr) && !t_active(&(cli_proc(cptr))))
 308       dealloc_connection(cli_connect(cptr)); /* connection not open anymore */
 309     else {
 310       if (-1 < cli_fd(cptr) && cli_freeflag(cptr) & FREEFLAG_SOCKET)
 311         socket_del(&(cli_socket(cptr))); /* queue a socket delete */
 312       if (cli_freeflag(cptr) & FREEFLAG_TIMER)
 313         timer_del(&(cli_proc(cptr))); /* queue a timer delete */
 314     }
 315   }
 316
 317   cli_connect(cptr) = 0;
 318
 319   dealloc_client(cptr); /* actually destroy the client */
 320 }
 321
 322 /** Allocate a new Server object for a client.
 323  * If Client::cli_serv == NULL, allocate a Server structure for it and
 324  * initialize it.
 325  * @param[in] cptr %Client to make into a server.
 326  * @return The value of cli_serv(\a cptr).
 327  */
 328 struct Server *make_server(struct Client *cptr)
 329 {
 330   struct Server *serv = cli_serv(cptr);
 331
 332   assert(cli_verify(cptr));
 333
 334   if (!serv)
 335   {
 336     serv = (struct Server*) MyMalloc(sizeof(struct Server));
 337     assert(0 != serv);
 338     memset(serv, 0, sizeof(struct Server)); /* All variables are 0 by default */
 339 #ifdef  DEBUGMODE
 340     servs.inuse++;
 341 #endif
 342     cli_serv(cptr) = serv;
 343     cli_serv(cptr)->lag = 60000;
 344     *serv->by = '\0';
 345     DupString(serv->last_error_msg, "<>");      /* String must be non-empty */
 346   }
 347   return cli_serv(cptr);
 348 }
 349
 350 /** Remove \a cptr from lists that it is a member of.
 351  * Specifically, this delinks \a cptr from #GlobalClientList, updates
 352  * the whowas history list, frees its Client::cli_user and
 353  * Client::cli_serv fields, and finally calls free_client() on it.
 354  * @param[in] cptr Client to remove from lists and free.
 355  */
 356 void remove_client_from_list(struct Client *cptr)
 357 {
 358   assert(cli_verify(cptr));
 359   assert(con_verify(cli_connect(cptr)));
 360   assert(!cli_prev(cptr) || cli_verify(cli_prev(cptr)));
 361   assert(!cli_next(cptr) || cli_verify(cli_next(cptr)));
 362   assert(!IsMe(cptr));
 363
 364   /* Only try remove cptr from the list if it IS in the list.
 365    * cli_next(cptr) cannot be NULL here, as &me is always the end
 366    * the list, and we never remove &me.    -GW
 367    */
 368   if(cli_next(cptr))
 369   {
 370     if (cli_prev(cptr))
 371       cli_next(cli_prev(cptr)) = cli_next(cptr);
 372     else {
 373       GlobalClientList = cli_next(cptr);
 374       cli_prev(GlobalClientList) = 0;
 375     }
 376     cli_prev(cli_next(cptr)) = cli_prev(cptr);
 377   }
 378   cli_next(cptr) = cli_prev(cptr) = 0;
 379
 380   if (IsUser(cptr) && cli_user(cptr)) {
 381     add_history(cptr, 0);
 382     off_history(cptr);
 383   }
 384   if (cli_user(cptr)) {
 385     free_user(cli_user(cptr));
 386     cli_user(cptr) = 0;
 387   }
 388
 389   if (cli_serv(cptr)) {
 390     if (cli_serv(cptr)->user) {
 391       free_user(cli_serv(cptr)->user);
 392       cli_serv(cptr)->user = 0;
 393     }
 394     if (cli_serv(cptr)->client_list)
 395       MyFree(cli_serv(cptr)->client_list);
 396     MyFree(cli_serv(cptr)->last_error_msg);
 397     MyFree(cli_serv(cptr));
 398 #ifdef  DEBUGMODE
 399     --servs.inuse;
 400 #endif
 401   }
 402   free_client(cptr);
 403 }
 404
 405 /** Link \a cptr into #GlobalClientList.
 406  * @param[in] cptr Client to link into the global list.
 407  */
 408 void add_client_to_list(struct Client *cptr)
 409 {
 410   assert(cli_verify(cptr));
 411   assert(cli_next(cptr) == 0);
 412   assert(cli_prev(cptr) == 0);
 413
 414   /*
 415    * Since we always insert new clients to the top of the list,
 416    * this should mean the "me" is the bottom most item in the list.
 417    * XXX - don't always count on the above, things change
 418    */
 419   cli_prev(cptr) = 0;
 420   cli_next(cptr) = GlobalClientList;
 421   GlobalClientList = cptr;
 422   if (cli_next(cptr))
 423     cli_prev(cli_next(cptr)) = cptr;
 424 }
 425
 426 #if 0
 427 /** Perform a very CPU-intensive verification of %GlobalClientList.
 428  * This checks the Client::cli_magic and Client::cli_prev field for
 429  * each element in the list, and also checks that there are no loops.
 430  * Any detected error will lead to an assertion failure.
 431  */
 432 void verify_client_list(void)
 433 {
 434   struct Client *client, *prev = 0;
 435   unsigned int visited = 0;
 436
 437   for (client = GlobalClientList; client; client = cli_next(client), ++visited) {
 438     /* Verify that this is a valid client, not a free'd one */
 439     assert(cli_verify(client));
 440     /* Verify that the list hasn't suddenly jumped around */
 441     assert(cli_prev(client) == prev);
 442     /* Verify that the list hasn't become circular */
 443     assert(cli_next(client) != GlobalClientList);
 444     assert(visited <= clientAllocCount);
 445     /* Remember what should preceed us */
 446     prev = client;
 447   }
 448 }
 449 #endif /* DEBUGMODE */
 450
 451 /** Find the list element that corresponds to a client.
 452  * @param[in] lp Head of singly linked list.
 453  * @param[in] ptr %Client to search for.
 454  * @return SLink element from \a lp that contains \a ptr, or NULL if none exist.
 455  */
 456 struct SLink *find_user_link(struct SLink *lp, struct Client *ptr)
 457 {
 458   if (ptr) {
 459     while (lp) {
 460       if (lp->value.cptr == ptr)
 461         return (lp);
 462       lp = lp->next;
 463     }
 464   }
 465   return NULL;
 466 }
 467
 468 /** Allocate a new SLink element.
 469  * Pulls from #slinkFreeList if it contains anything, else it
 470  * allocates a new one from the heap.
 471  * @return Newly allocated list element.
 472  */
 473 struct SLink* make_link(void)
 474 {
 475   struct SLink* lp = slinkFreeList;
 476   if (lp)
 477     slinkFreeList = lp->next;
 478   else {
 479     lp = (struct SLink*) MyMalloc(sizeof(struct SLink));
 480     ++slinkAllocCount;
 481   }
 482   assert(0 != lp);
 483 #ifdef  DEBUGMODE
 484   links.inuse++;
 485 #endif
 486   return lp;
 487 }
 488
 489 /** Release a singly linked list element.
 490  * @param[in] lp List element to mark as unused.
 491  */
 492 void free_link(struct SLink* lp)
 493 {
 494   if (lp) {
 495     lp->next = slinkFreeList;
 496     slinkFreeList = lp;
 497   }
 498 #ifdef  DEBUGMODE
 499   links.inuse--;
 500 #endif
 501 }
 502
 503 /** Add an element to a doubly linked list.
 504  * If \a lpp points to a non-NULL pointer, its DLink::prev field is
 505  * updated to point to the newly allocated element.  Regardless,
 506  * \a lpp is overwritten with the pointer to the new link.
 507  * @param[in,out] lpp Pointer to insertion location.
 508  * @param[in] cp %Client to put in newly allocated element.
 509  * @return Allocated link structure (same as \a lpp on output).
 510  */
 511 struct DLink *add_dlink(struct DLink **lpp, struct Client *cp)
 512 {
 513   struct DLink* lp = (struct DLink*) MyMalloc(sizeof(struct DLink));
 514   assert(0 != lp);
 515   lp->value.cptr = cp;
 516   lp->prev = 0;
 517   if ((lp->next = *lpp))
 518     lp->next->prev = lp;
 519   *lpp = lp;
 520   return lp;
 521 }
 522
 523 /** Remove a node from a doubly linked list.
 524  * @param[out] lpp Pointer to next list element.
 525  * @param[in] lp List node to unlink.
 526  */
 527 void remove_dlink(struct DLink **lpp, struct DLink *lp)
 528 {
 529   assert(0 != lpp);
 530   assert(0 != lp);
 531
 532   if (lp->prev) {
 533     if ((lp->prev->next = lp->next))
 534       lp->next->prev = lp->prev;
 535   }
 536   else if ((*lpp = lp->next))
 537     lp->next->prev = NULL;
 538   MyFree(lp);
 539 }
 540
 541 #ifdef  DEBUGMODE
 542 /** Report memory usage of list elements to \a cptr.
 543  * @param[in] cptr Client requesting information.
 544  * @param[in] name Unused pointer.
 545  */
 546 void send_listinfo(struct Client *cptr, char *name)
 547 {
 548   int inuse = 0, mem = 0, tmp = 0;
 549
 550   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Clients: inuse: %d(%d)",
 551              clients.inuse, tmp = clients.inuse * sizeof(struct Client));
 552   mem += tmp;
 553   inuse += clients.inuse;
 554   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, "Connections: inuse: %d(%d)",
 555              connections.inuse,
 556              tmp = connections.inuse * sizeof(struct Connection));
 557   mem += tmp;
 558   inuse += connections.inuse;
 559   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Users: inuse: %d(%d)",
 560              users.inuse, tmp = users.inuse * sizeof(struct User));
 561   mem += tmp;
 562   inuse += users.inuse;
 563   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Servs: inuse: %d(%d)",
 564              servs.inuse, tmp = servs.inuse * sizeof(struct Server));
 565   mem += tmp;
 566   inuse += servs.inuse;
 567   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Links: inuse: %d(%d)",
 568              links.inuse, tmp = links.inuse * sizeof(struct SLink));
 569   mem += tmp;
 570   inuse += links.inuse;
 571   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Confs: inuse: %d(%d)",
 572              GlobalConfCount, tmp = GlobalConfCount * sizeof(struct ConfItem));
 573   mem += tmp;
 574   inuse += GlobalConfCount;
 575   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Totals: inuse %d %d",
 576              inuse, mem);
 577 }
 578
 579 #endif