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