]>
jfr.im git - irc/quakenet/snircd.git/blob - ircd/list.c
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.
22 * @version $Id: list.c,v 1.34.2.3 2006/05/08 01:30:24 entrope Exp $
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 (-1 < con_fd(con
))
170 MsgQClear(&(con_sendQ(con
)));
171 client_drop_sendq(con
);
172 DBufClear(&(con_recvQ(con
)));
173 if (con_listener(con
))
174 release_listener(con_listener(con
));
178 con_next(con
) = connectionFreeList
;
179 connectionFreeList
= con
;
184 /** Allocate a new client and initialize it.
185 * If \a from == NULL, initialize the fields for a local client,
186 * including allocating a Connection for him; otherwise initialize the
187 * fields for a remote client..
188 * @param[in] from Server connection that introduced the client (or
190 * @param[in] status Initial Client::cli_status value.
191 * @return Newly allocated and initialized Client.
193 struct Client
* make_client(struct Client
*from
, int status
)
195 struct Client
* cptr
= 0;
197 assert(!from
|| cli_verify(from
));
199 cptr
= alloc_client();
202 assert(!cli_magic(cptr
));
203 assert(0 == from
|| 0 != cli_connect(from
));
205 if (!from
) { /* local client, allocate a struct Connection */
206 struct Connection
*con
= alloc_connection();
209 assert(!con_magic(con
));
211 con_magic(con
) = CONNECTION_MAGIC
;
212 con_fd(con
) = -1; /* initialize struct Connection */
213 con_freeflag(con
) = 0;
214 con_nextnick(con
) = CurrentTime
- NICK_DELAY
;
215 con_nexttarget(con
) = CurrentTime
- (TARGET_DELAY
* (STARTTARGETS
- 1));
216 con_handler(con
) = UNREGISTERED_HANDLER
;
217 con_client(con
) = cptr
;
219 cli_connect(cptr
) = con
; /* set the connection and other fields */
220 cli_since(cptr
) = cli_lasttime(cptr
) = cli_firsttime(cptr
) = CurrentTime
;
221 cli_lastnick(cptr
) = TStime();
223 cli_connect(cptr
) = cli_connect(from
); /* use 'from's connection */
225 assert(con_verify(cli_connect(cptr
)));
227 cli_magic(cptr
) = CLIENT_MAGIC
;
228 cli_status(cptr
) = status
;
229 cli_hnext(cptr
) = cptr
;
230 strcpy(cli_username(cptr
), "unknown");
235 /** Release a Connection.
236 * @param[in] con Connection to free.
238 void free_connection(struct Connection
* con
)
243 assert(con_verify(con
));
244 assert(0 == con_client(con
));
246 dealloc_connection(con
); /* deallocate the connection */
249 /** Release a Client.
250 * In addition to the cleanup done by dealloc_client(), this will free
251 * any pending auth request, free the connection for local clients,
252 * and delete the processing timer for the client.
253 * @param[in] cptr Client to free.
255 void free_client(struct Client
* cptr
)
260 * forget to remove the client from the hash table?
262 assert(cli_verify(cptr
));
263 assert(cli_hnext(cptr
) == cptr
);
264 /* or from linked list? */
265 assert(cli_next(cptr
) == 0);
266 assert(cli_prev(cptr
) == 0);
268 Debug((DEBUG_LIST
, "Freeing client %s [%p], connection %p", cli_name(cptr
),
269 cptr
, cli_connect(cptr
)));
272 destroy_auth_request(cli_auth(cptr
));
274 /* Make sure we didn't magically get re-added to the list */
275 assert(cli_next(cptr
) == 0);
276 assert(cli_prev(cptr
) == 0);
278 if (cli_from(cptr
) == cptr
) { /* in other words, we're local */
280 /* timer must be marked as not active */
281 if (!cli_freeflag(cptr
) && !t_active(&(cli_proc(cptr
))))
282 dealloc_connection(cli_connect(cptr
)); /* connection not open anymore */
284 if (-1 < cli_fd(cptr
) && cli_freeflag(cptr
) & FREEFLAG_SOCKET
)
285 socket_del(&(cli_socket(cptr
))); /* queue a socket delete */
286 if (cli_freeflag(cptr
) & FREEFLAG_TIMER
)
287 timer_del(&(cli_proc(cptr
))); /* queue a timer delete */
291 cli_connect(cptr
) = 0;
293 dealloc_client(cptr
); /* actually destroy the client */
296 /** Allocate a new Server object for a client.
297 * If Client::cli_serv == NULL, allocate a Server structure for it and
299 * @param[in] cptr %Client to make into a server.
300 * @return The value of cli_serv(\a cptr).
302 struct Server
*make_server(struct Client
*cptr
)
304 struct Server
*serv
= cli_serv(cptr
);
306 assert(cli_verify(cptr
));
310 serv
= (struct Server
*) MyMalloc(sizeof(struct Server
));
312 memset(serv
, 0, sizeof(struct Server
)); /* All variables are 0 by default */
315 cli_serv(cptr
) = serv
;
316 cli_serv(cptr
)->lag
= 60000;
318 DupString(serv
->last_error_msg
, "<>"); /* String must be non-empty */
320 return cli_serv(cptr
);
323 /** Remove \a cptr from lists that it is a member of.
324 * Specifically, this delinks \a cptr from #GlobalClientList, updates
325 * the whowas history list, frees its Client::cli_user and
326 * Client::cli_serv fields, and finally calls free_client() on it.
327 * @param[in] cptr Client to remove from lists and free.
329 void remove_client_from_list(struct Client
*cptr
)
331 assert(cli_verify(cptr
));
332 assert(con_verify(cli_connect(cptr
)));
333 assert(!cli_prev(cptr
) || cli_verify(cli_prev(cptr
)));
334 assert(!cli_next(cptr
) || cli_verify(cli_next(cptr
)));
337 /* Only try remove cptr from the list if it IS in the list.
338 * cli_next(cptr) cannot be NULL here, as &me is always the end
339 * the list, and we never remove &me. -GW
344 cli_next(cli_prev(cptr
)) = cli_next(cptr
);
346 GlobalClientList
= cli_next(cptr
);
347 cli_prev(GlobalClientList
) = 0;
349 cli_prev(cli_next(cptr
)) = cli_prev(cptr
);
351 cli_next(cptr
) = cli_prev(cptr
) = 0;
353 if (IsUser(cptr
) && cli_user(cptr
)) {
354 add_history(cptr
, 0);
357 if (cli_user(cptr
)) {
358 free_user(cli_user(cptr
));
362 if (cli_serv(cptr
)) {
363 if (cli_serv(cptr
)->user
) {
364 free_user(cli_serv(cptr
)->user
);
365 cli_serv(cptr
)->user
= 0;
367 if (cli_serv(cptr
)->client_list
)
368 MyFree(cli_serv(cptr
)->client_list
);
369 MyFree(cli_serv(cptr
)->last_error_msg
);
370 MyFree(cli_serv(cptr
));
377 /** Link \a cptr into #GlobalClientList.
378 * @param[in] cptr Client to link into the global list.
380 void add_client_to_list(struct Client
*cptr
)
382 assert(cli_verify(cptr
));
383 assert(cli_next(cptr
) == 0);
384 assert(cli_prev(cptr
) == 0);
387 * Since we always insert new clients to the top of the list,
388 * this should mean the "me" is the bottom most item in the list.
389 * XXX - don't always count on the above, things change
392 cli_next(cptr
) = GlobalClientList
;
393 GlobalClientList
= cptr
;
395 cli_prev(cli_next(cptr
)) = cptr
;
399 /** Perform a very CPU-intensive verification of %GlobalClientList.
400 * This checks the Client::cli_magic and Client::cli_prev field for
401 * each element in the list, and also checks that there are no loops.
402 * Any detected error will lead to an assertion failure.
404 void verify_client_list(void)
406 struct Client
*client
, *prev
= 0;
407 unsigned int visited
= 0;
409 for (client
= GlobalClientList
; client
; client
= cli_next(client
), ++visited
) {
410 /* Verify that this is a valid client, not a free'd one */
411 assert(cli_verify(client
));
412 /* Verify that the list hasn't suddenly jumped around */
413 assert(cli_prev(client
) == prev
);
414 /* Verify that the list hasn't become circular */
415 assert(cli_next(client
) != GlobalClientList
);
416 assert(visited
<= clients
.alloc
);
417 /* Remember what should precede us */
421 #endif /* DEBUGMODE */
423 /** Allocate a new SLink element.
424 * Pulls from #slinkFreeList if it contains anything, else it
425 * allocates a new one from the heap.
426 * @return Newly allocated list element.
428 struct SLink
* make_link(void)
430 struct SLink
* lp
= slinkFreeList
;
432 slinkFreeList
= lp
->next
;
434 lp
= (struct SLink
*) MyMalloc(sizeof(struct SLink
));
439 memset(lp
, 0, sizeof(*lp
));
443 /** Release a singly linked list element.
444 * @param[in] lp List element to mark as unused.
446 void free_link(struct SLink
* lp
)
449 lp
->next
= slinkFreeList
;
455 /** Add an element to a doubly linked list.
456 * If \a lpp points to a non-NULL pointer, its DLink::prev field is
457 * updated to point to the newly allocated element. Regardless,
458 * \a lpp is overwritten with the pointer to the new link.
459 * @param[in,out] lpp Pointer to insertion location.
460 * @param[in] cp %Client to put in newly allocated element.
461 * @return Allocated link structure (same as \a lpp on output).
463 struct DLink
*add_dlink(struct DLink
**lpp
, struct Client
*cp
)
465 struct DLink
* lp
= (struct DLink
*) MyMalloc(sizeof(struct DLink
));
469 if ((lp
->next
= *lpp
))
475 /** Remove a node from a doubly linked list.
476 * @param[out] lpp Pointer to next list element.
477 * @param[in] lp List node to unlink.
479 void remove_dlink(struct DLink
**lpp
, struct DLink
*lp
)
485 if ((lp
->prev
->next
= lp
->next
))
486 lp
->next
->prev
= lp
->prev
;
488 else if ((*lpp
= lp
->next
))
489 lp
->next
->prev
= NULL
;
493 /** Report memory usage of a list to \a cptr.
494 * @param[in] cptr Client requesting information.
495 * @param[in] lstats List statistics descriptor.
496 * @param[in] itemname Plural name of item type.
497 * @param[in,out] totals If non-null, accumulates item counts and memory usage.
499 void send_liststats(struct Client
*cptr
, const struct liststats
*lstats
,
500 const char *itemname
, struct liststats
*totals
)
502 send_reply(cptr
, SND_EXPLICIT
| RPL_STATSDEBUG
, ":%s: inuse %zu(%zu) alloc %zu",
503 itemname
, lstats
->inuse
, lstats
->mem
, lstats
->alloc
);
506 totals
->inuse
+= lstats
->inuse
;
507 totals
->alloc
+= lstats
->alloc
;
508 totals
->mem
+= lstats
->mem
;
512 /** Report memory usage of list elements to \a cptr.
513 * @param[in] cptr Client requesting information.
514 * @param[in] name Unused pointer.
516 void send_listinfo(struct Client
*cptr
, char *name
)
518 struct liststats total
;
519 struct liststats confs
;
520 struct ConfItem
*conf
;
522 memset(&total
, 0, sizeof(total
));
524 clients
.mem
= clients
.inuse
* sizeof(struct Client
);
525 send_liststats(cptr
, &clients
, "Clients", &total
);
527 connections
.mem
= connections
.inuse
* sizeof(struct Connection
);
528 send_liststats(cptr
, &connections
, "Connections", &total
);
530 servs
.mem
= servs
.inuse
* sizeof(struct Server
);
531 send_liststats(cptr
, &servs
, "Servers", &total
);
533 links
.mem
= links
.inuse
* sizeof(struct SLink
);
534 send_liststats(cptr
, &links
, "Links", &total
);
536 confs
.alloc
= GlobalConfCount
;
537 confs
.mem
= confs
.alloc
* sizeof(GlobalConfCount
);
538 for (confs
.inuse
= 0, conf
= GlobalConfList
; conf
; conf
= conf
->next
)
540 send_liststats(cptr
, &confs
, "Confs", &total
);
542 send_liststats(cptr
, &total
, "Totals", NULL
);