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