2 * IRC - Internet Relay Chat, ircd/list.c
3 * Copyright (C) 1990 Jarkko Oikarinen and
4 * University of Oulu, Finland
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)
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.
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.
21 * @brief Singly and doubly linked list manipulation implementation.
29 #include "ircd_alloc.h"
30 #include "ircd_events.h"
32 #include "ircd_reply.h"
33 #include "ircd_string.h"
48 /* #include <assert.h> -- Now using assert in ircd_log.h */
49 #include <stddef.h> /* offsetof */
50 #include <unistd.h> /* close */
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;
60 /** Linked list of currently unused Client structures. */
61 static struct Client* clientFreeList;
63 /** Linked list of currently unused Connection structures. */
64 static struct Connection* connectionFreeList;
66 /** Linked list of currently unused SLink structures. */
67 static struct SLink* slinkFreeList;
69 /** Initialize the list manipulation support system.
70 * Pre-allocate MAXCONNECTIONS Client and Connection structures.
75 struct Connection* con;
78 * pre-allocate MAXCONNECTIONS clients and connections
80 for (i = 0; i < MAXCONNECTIONS; ++i) {
81 cptr = (struct Client*) MyMalloc(sizeof(struct Client));
82 cli_next(cptr) = clientFreeList;
83 clientFreeList = cptr;
86 con = (struct Connection*) MyMalloc(sizeof(struct Connection));
87 con_next(con) = connectionFreeList;
88 connectionFreeList = con;
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.
98 static struct Client* alloc_client(void)
100 struct Client* cptr = clientFreeList;
103 cptr = (struct Client*) MyMalloc(sizeof(struct Client));
106 clientFreeList = cli_next(cptr);
110 memset(cptr, 0, sizeof(struct Client));
115 /** Release a Client structure by prepending it to #clientFreeList.
116 * @param[in] cptr Client that is no longer being used.
118 static void dealloc_client(struct Client* cptr)
120 assert(cli_verify(cptr));
121 assert(0 == cli_connect(cptr));
125 cli_next(cptr) = clientFreeList;
126 clientFreeList = cptr;
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.
136 static struct Connection* alloc_connection(void)
138 struct Connection* con = connectionFreeList;
141 con = (struct Connection*) MyMalloc(sizeof(struct Connection));
144 connectionFreeList = con_next(con);
148 memset(con, 0, sizeof(struct Connection));
149 timer_init(&(con_proc(con)));
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.
160 static void dealloc_connection(struct Connection* con)
162 assert(con_verify(con));
163 assert(!t_active(&(con_proc(con))));
164 assert(!t_onqueue(&(con_proc(con))));
166 Debug((DEBUG_LIST, "Deallocating connection %p", con));
168 if (con_dns_reply(con)) {
169 MyFree(con_dns_reply(con));
170 con_dns_reply(con) = 0;
172 if (-1 < 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));
182 con_next(con) = connectionFreeList;
183 connectionFreeList = con;
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
194 * @param[in] status Initial Client::cli_status value.
195 * @return Newly allocated and initialized Client.
197 struct Client* make_client(struct Client *from, int status)
199 struct Client* cptr = 0;
201 assert(!from || cli_verify(from));
203 cptr = alloc_client();
206 assert(!cli_magic(cptr));
207 assert(0 == from || 0 != cli_connect(from));
209 if (!from) { /* local client, allocate a struct Connection */
210 struct Connection *con = alloc_connection();
213 assert(!con_magic(con));
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;
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;
228 cli_connect(cptr) = cli_connect(from); /* use 'from's connection */
230 assert(con_verify(cli_connect(cptr)));
232 cli_magic(cptr) = CLIENT_MAGIC;
233 cli_status(cptr) = status;
234 cli_hnext(cptr) = cptr;
235 strcpy(cli_username(cptr), "unknown");
240 /** Release a Connection.
241 * @param[in] con Connection to free.
243 void free_connection(struct Connection* con)
248 assert(con_verify(con));
249 assert(0 == con_client(con));
251 dealloc_connection(con); /* deallocate the connection */
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.
260 void free_client(struct Client* cptr)
265 * forget to remove the client from the hash table?
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);
273 Debug((DEBUG_LIST, "Freeing client %s [%p], connection %p", cli_name(cptr),
274 cptr, cli_connect(cptr)));
277 destroy_auth_request(cli_auth(cptr), 0);
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);
283 if (cli_from(cptr) == cptr) { /* in other words, we're local */
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 */
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 */
296 cli_connect(cptr) = 0;
298 dealloc_client(cptr); /* actually destroy the client */
301 /** Allocate a new Server object for a client.
302 * If Client::cli_serv == NULL, allocate a Server structure for it and
304 * @param[in] cptr %Client to make into a server.
305 * @return The value of cli_serv(\a cptr).
307 struct Server *make_server(struct Client *cptr)
309 struct Server *serv = cli_serv(cptr);
311 assert(cli_verify(cptr));
315 serv = (struct Server*) MyMalloc(sizeof(struct Server));
317 memset(serv, 0, sizeof(struct Server)); /* All variables are 0 by default */
320 cli_serv(cptr) = serv;
321 cli_serv(cptr)->lag = 60000;
323 DupString(serv->last_error_msg, "<>"); /* String must be non-empty */
325 return cli_serv(cptr);
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.
334 void remove_client_from_list(struct Client *cptr)
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)));
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
349 cli_next(cli_prev(cptr)) = cli_next(cptr);
351 GlobalClientList = cli_next(cptr);
352 cli_prev(GlobalClientList) = 0;
354 cli_prev(cli_next(cptr)) = cli_prev(cptr);
356 cli_next(cptr) = cli_prev(cptr) = 0;
358 if (IsUser(cptr) && cli_user(cptr)) {
359 add_history(cptr, 0);
362 if (cli_user(cptr)) {
363 free_user(cli_user(cptr));
367 if (cli_serv(cptr)) {
368 if (cli_serv(cptr)->user) {
369 free_user(cli_serv(cptr)->user);
370 cli_serv(cptr)->user = 0;
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));
382 /** Link \a cptr into #GlobalClientList.
383 * @param[in] cptr Client to link into the global list.
385 void add_client_to_list(struct Client *cptr)
387 assert(cli_verify(cptr));
388 assert(cli_next(cptr) == 0);
389 assert(cli_prev(cptr) == 0);
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
397 cli_next(cptr) = GlobalClientList;
398 GlobalClientList = cptr;
400 cli_prev(cli_next(cptr)) = cptr;
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.
409 void verify_client_list(void)
411 struct Client *client, *prev = 0;
412 unsigned int visited = 0;
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 */
426 #endif /* DEBUGMODE */
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.
433 struct SLink* make_link(void)
435 struct SLink* lp = slinkFreeList;
437 slinkFreeList = lp->next;
439 lp = (struct SLink*) MyMalloc(sizeof(struct SLink));
447 /** Release a singly linked list element.
448 * @param[in] lp List element to mark as unused.
450 void free_link(struct SLink* lp)
453 lp->next = slinkFreeList;
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).
467 struct DLink *add_dlink(struct DLink **lpp, struct Client *cp)
469 struct DLink* lp = (struct DLink*) MyMalloc(sizeof(struct DLink));
473 if ((lp->next = *lpp))
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.
483 void remove_dlink(struct DLink **lpp, struct DLink *lp)
489 if ((lp->prev->next = lp->next))
490 lp->next->prev = lp->prev;
492 else if ((*lpp = lp->next))
493 lp->next->prev = NULL;
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.
503 void send_liststats(struct Client *cptr, const struct liststats *lstats,
504 const char *itemname, struct liststats *totals)
506 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":%s: inuse %zu(%zu) alloc %zu",
507 itemname, lstats->inuse, lstats->mem, lstats->alloc);
510 totals->inuse += lstats->inuse;
511 totals->alloc += lstats->alloc;
512 totals->mem += lstats->mem;
516 /** Report memory usage of list elements to \a cptr.
517 * @param[in] cptr Client requesting information.
518 * @param[in] name Unused pointer.
520 void send_listinfo(struct Client *cptr, char *name)
522 struct liststats total;
523 struct liststats confs;
524 struct ConfItem *conf;
526 memset(&total, 0, sizeof(total));
528 clients.mem = clients.inuse * sizeof(struct Client);
529 send_liststats(cptr, &clients, "Clients", &total);
531 connections.mem = connections.inuse * sizeof(struct Connection);
532 send_liststats(cptr, &connections, "Connections", &total);
534 servs.mem = servs.inuse * sizeof(struct Server);
535 send_liststats(cptr, &servs, "Servers", &total);
537 links.mem = links.inuse * sizeof(struct SLink);
538 send_liststats(cptr, &links, "Links", &total);
540 confs.alloc = GlobalConfCount;
541 confs.mem = confs.alloc * sizeof(GlobalConfCount);
542 for (confs.inuse = 0, conf = GlobalConfList; conf; conf = conf->next)
544 send_liststats(cptr, &confs, "Confs", &total);
546 send_liststats(cptr, &total, "Totals", NULL);