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