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 */
54 /** Stores linked list statistics for various types of lists. */
55 static struct liststats {
57 } clients, connections, users, servs, links;
60 /** Count of allocated Client structures. */
61 static unsigned int clientAllocCount;
62 /** Linked list of currently unused Client structures. */
63 static struct Client* clientFreeList;
65 /** Count of allocated Connection structures. */
66 static unsigned int connectionAllocCount;
67 /** Linked list of currently unused Connection structures. */
68 static struct Connection* connectionFreeList;
70 /** Count of allocated SLink structures. */
71 static unsigned int slinkAllocCount;
72 /** Linked list of currently unused SLink structures. */
73 static struct SLink* slinkFreeList;
75 /** Initialize the list manipulation support system.
76 * Pre-allocate MAXCONNECTIONS Client and Connection structures.
81 struct Connection* con;
84 * pre-allocate MAXCONNECTIONS clients and connections
86 for (i = 0; i < MAXCONNECTIONS; ++i) {
87 cptr = (struct Client*) MyMalloc(sizeof(struct Client));
88 cli_next(cptr) = clientFreeList;
89 clientFreeList = cptr;
92 con = (struct Connection*) MyMalloc(sizeof(struct Connection));
93 con_next(con) = connectionFreeList;
94 connectionFreeList = con;
95 ++connectionAllocCount;
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));
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.
112 static struct Client* alloc_client(void)
114 struct Client* cptr = clientFreeList;
117 cptr = (struct Client*) MyMalloc(sizeof(struct Client));
120 clientFreeList = cli_next(cptr);
126 memset(cptr, 0, sizeof(struct Client));
131 /** Release a Client structure by prepending it to #clientFreeList.
132 * @param[in] cptr Client that is no longer being used.
134 static void dealloc_client(struct Client* cptr)
136 assert(cli_verify(cptr));
137 assert(0 == cli_connect(cptr));
143 cli_next(cptr) = clientFreeList;
144 clientFreeList = cptr;
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.
154 static struct Connection* alloc_connection(void)
156 struct Connection* con = connectionFreeList;
159 con = (struct Connection*) MyMalloc(sizeof(struct Connection));
160 ++connectionAllocCount;
162 connectionFreeList = con_next(con);
168 memset(con, 0, sizeof(struct Connection));
169 timer_init(&(con_proc(con)));
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.
180 static void dealloc_connection(struct Connection* con)
182 assert(con_verify(con));
183 assert(!t_active(&(con_proc(con))));
184 assert(!t_onqueue(&(con_proc(con))));
186 Debug((DEBUG_LIST, "Deallocating connection %p", con));
188 if (con_dns_reply(con)) {
189 MyFree(con_dns_reply(con));
190 con_dns_reply(con) = 0;
192 if (-1 < 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));
204 con_next(con) = connectionFreeList;
205 connectionFreeList = con;
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
216 * @param[in] status Initial Client::cli_status value.
217 * @return Newly allocated and initialized Client.
219 struct Client* make_client(struct Client *from, int status)
221 struct Client* cptr = 0;
223 assert(!from || cli_verify(from));
225 cptr = alloc_client();
228 assert(!cli_magic(cptr));
229 assert(0 == from || 0 != cli_connect(from));
231 if (!from) { /* local client, allocate a struct Connection */
232 struct Connection *con = alloc_connection();
235 assert(!con_magic(con));
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;
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 cli_unreg(cptr) = CLIREG_INIT;
250 cli_connect(cptr) = cli_connect(from); /* use 'from's connection */
252 assert(con_verify(cli_connect(cptr)));
254 cli_magic(cptr) = CLIENT_MAGIC;
255 cli_status(cptr) = status;
256 cli_hnext(cptr) = cptr;
257 strcpy(cli_username(cptr), "unknown");
262 /** Release a Connection.
263 * @param[in] con Connection to free.
265 void free_connection(struct Connection* con)
270 assert(con_verify(con));
271 assert(0 == con_client(con));
273 dealloc_connection(con); /* deallocate the connection */
276 /** Release a Client.
277 * In addition to the cleanup done by dealloc_client(), this will free
278 * any pending auth request, free the connection for local clients,
279 * and delete the processing timer for the client.
280 * @param[in] cptr Client to free.
282 void free_client(struct Client* cptr)
287 * forget to remove the client from the hash table?
289 assert(cli_verify(cptr));
290 assert(cli_hnext(cptr) == cptr);
291 /* or from linked list? */
292 assert(cli_next(cptr) == 0);
293 assert(cli_prev(cptr) == 0);
295 Debug((DEBUG_LIST, "Freeing client %s [%p], connection %p", cli_name(cptr),
296 cptr, cli_connect(cptr)));
299 destroy_auth_request(cli_auth(cptr), 0);
301 /* Make sure we didn't magically get re-added to the list */
302 assert(cli_next(cptr) == 0);
303 assert(cli_prev(cptr) == 0);
305 if (cli_from(cptr) == cptr) { /* in other words, we're local */
307 /* timer must be marked as not active */
308 if (!cli_freeflag(cptr) && !t_active(&(cli_proc(cptr))))
309 dealloc_connection(cli_connect(cptr)); /* connection not open anymore */
311 if (-1 < cli_fd(cptr) && cli_freeflag(cptr) & FREEFLAG_SOCKET)
312 socket_del(&(cli_socket(cptr))); /* queue a socket delete */
313 if (cli_freeflag(cptr) & FREEFLAG_TIMER)
314 timer_del(&(cli_proc(cptr))); /* queue a timer delete */
318 cli_connect(cptr) = 0;
320 dealloc_client(cptr); /* actually destroy the client */
323 /** Allocate a new Server object for a client.
324 * If Client::cli_serv == NULL, allocate a Server structure for it and
326 * @param[in] cptr %Client to make into a server.
327 * @return The value of cli_serv(\a cptr).
329 struct Server *make_server(struct Client *cptr)
331 struct Server *serv = cli_serv(cptr);
333 assert(cli_verify(cptr));
337 serv = (struct Server*) MyMalloc(sizeof(struct Server));
339 memset(serv, 0, sizeof(struct Server)); /* All variables are 0 by default */
343 cli_serv(cptr) = serv;
344 cli_serv(cptr)->lag = 60000;
346 DupString(serv->last_error_msg, "<>"); /* String must be non-empty */
348 return cli_serv(cptr);
351 /** Remove \a cptr from lists that it is a member of.
352 * Specifically, this delinks \a cptr from #GlobalClientList, updates
353 * the whowas history list, frees its Client::cli_user and
354 * Client::cli_serv fields, and finally calls free_client() on it.
355 * @param[in] cptr Client to remove from lists and free.
357 void remove_client_from_list(struct Client *cptr)
359 assert(cli_verify(cptr));
360 assert(con_verify(cli_connect(cptr)));
361 assert(!cli_prev(cptr) || cli_verify(cli_prev(cptr)));
362 assert(!cli_next(cptr) || cli_verify(cli_next(cptr)));
365 /* Only try remove cptr from the list if it IS in the list.
366 * cli_next(cptr) cannot be NULL here, as &me is always the end
367 * the list, and we never remove &me. -GW
372 cli_next(cli_prev(cptr)) = cli_next(cptr);
374 GlobalClientList = cli_next(cptr);
375 cli_prev(GlobalClientList) = 0;
377 cli_prev(cli_next(cptr)) = cli_prev(cptr);
379 cli_next(cptr) = cli_prev(cptr) = 0;
381 if (IsUser(cptr) && cli_user(cptr)) {
382 add_history(cptr, 0);
385 if (cli_user(cptr)) {
386 free_user(cli_user(cptr));
390 if (cli_serv(cptr)) {
391 if (cli_serv(cptr)->user) {
392 free_user(cli_serv(cptr)->user);
393 cli_serv(cptr)->user = 0;
395 if (cli_serv(cptr)->client_list)
396 MyFree(cli_serv(cptr)->client_list);
397 MyFree(cli_serv(cptr)->last_error_msg);
398 MyFree(cli_serv(cptr));
406 /** Link \a cptr into #GlobalClientList.
407 * @param[in] cptr Client to link into the global list.
409 void add_client_to_list(struct Client *cptr)
411 assert(cli_verify(cptr));
412 assert(cli_next(cptr) == 0);
413 assert(cli_prev(cptr) == 0);
416 * Since we always insert new clients to the top of the list,
417 * this should mean the "me" is the bottom most item in the list.
418 * XXX - don't always count on the above, things change
421 cli_next(cptr) = GlobalClientList;
422 GlobalClientList = cptr;
424 cli_prev(cli_next(cptr)) = cptr;
428 /** Perform a very CPU-intensive verification of %GlobalClientList.
429 * This checks the Client::cli_magic and Client::cli_prev field for
430 * each element in the list, and also checks that there are no loops.
431 * Any detected error will lead to an assertion failure.
433 void verify_client_list(void)
435 struct Client *client, *prev = 0;
436 unsigned int visited = 0;
438 for (client = GlobalClientList; client; client = cli_next(client), ++visited) {
439 /* Verify that this is a valid client, not a free'd one */
440 assert(cli_verify(client));
441 /* Verify that the list hasn't suddenly jumped around */
442 assert(cli_prev(client) == prev);
443 /* Verify that the list hasn't become circular */
444 assert(cli_next(client) != GlobalClientList);
445 assert(visited <= clientAllocCount);
446 /* Remember what should preceed us */
450 #endif /* DEBUGMODE */
452 /** Find the list element that corresponds to a client.
453 * @param[in] lp Head of singly linked list.
454 * @param[in] ptr %Client to search for.
455 * @return SLink element from \a lp that contains \a ptr, or NULL if none exist.
457 struct SLink *find_user_link(struct SLink *lp, struct Client *ptr)
461 if (lp->value.cptr == ptr)
469 /** Allocate a new SLink element.
470 * Pulls from #slinkFreeList if it contains anything, else it
471 * allocates a new one from the heap.
472 * @return Newly allocated list element.
474 struct SLink* make_link(void)
476 struct SLink* lp = slinkFreeList;
478 slinkFreeList = lp->next;
480 lp = (struct SLink*) MyMalloc(sizeof(struct SLink));
490 /** Release a singly linked list element.
491 * @param[in] lp List element to mark as unused.
493 void free_link(struct SLink* lp)
496 lp->next = slinkFreeList;
504 /** Add an element to a doubly linked list.
505 * If \a lpp points to a non-NULL pointer, its DLink::prev field is
506 * updated to point to the newly allocated element. Regardless,
507 * \a lpp is overwritten with the pointer to the new link.
508 * @param[in,out] lpp Pointer to insertion location.
509 * @param[in] cp %Client to put in newly allocated element.
510 * @return Allocated link structure (same as \a lpp on output).
512 struct DLink *add_dlink(struct DLink **lpp, struct Client *cp)
514 struct DLink* lp = (struct DLink*) MyMalloc(sizeof(struct DLink));
518 if ((lp->next = *lpp))
524 /** Remove a node from a doubly linked list.
525 * @param[out] lpp Pointer to next list element.
526 * @param[in] lp List node to unlink.
528 void remove_dlink(struct DLink **lpp, struct DLink *lp)
534 if ((lp->prev->next = lp->next))
535 lp->next->prev = lp->prev;
537 else if ((*lpp = lp->next))
538 lp->next->prev = NULL;
543 /** Report memory usage of list elements to \a cptr.
544 * @param[in] cptr Client requesting information.
545 * @param[in] name Unused pointer.
547 void send_listinfo(struct Client *cptr, char *name)
549 int inuse = 0, mem = 0, tmp = 0;
551 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Clients: inuse: %d(%d)",
552 clients.inuse, tmp = clients.inuse * sizeof(struct Client));
554 inuse += clients.inuse;
555 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, "Connections: inuse: %d(%d)",
557 tmp = connections.inuse * sizeof(struct Connection));
559 inuse += connections.inuse;
560 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Users: inuse: %d(%d)",
561 users.inuse, tmp = users.inuse * sizeof(struct User));
563 inuse += users.inuse;
564 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Servs: inuse: %d(%d)",
565 servs.inuse, tmp = servs.inuse * sizeof(struct Server));
567 inuse += servs.inuse;
568 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Links: inuse: %d(%d)",
569 links.inuse, tmp = links.inuse * sizeof(struct SLink));
571 inuse += links.inuse;
572 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Confs: inuse: %d(%d)",
573 GlobalConfCount, tmp = GlobalConfCount * sizeof(struct ConfItem));
575 inuse += GlobalConfCount;
576 send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":Totals: inuse %d %d",