]>
Commit | Line | Data |
---|---|---|
189935b1 | 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. | |
9f8856e9 | 22 | * @version $Id: list.c,v 1.34.2.3 2006/05/08 01:30:24 entrope Exp $ |
189935b1 | 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 (-1 < con_fd(con)) | |
169 | close(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)); | |
175 | ||
176 | --connections.inuse; | |
177 | ||
178 | con_next(con) = connectionFreeList; | |
179 | connectionFreeList = con; | |
180 | ||
181 | con_magic(con) = 0; | |
182 | } | |
183 | ||
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 | |
189 | * NULL). | |
190 | * @param[in] status Initial Client::cli_status value. | |
191 | * @return Newly allocated and initialized Client. | |
192 | */ | |
193 | struct Client* make_client(struct Client *from, int status) | |
194 | { | |
195 | struct Client* cptr = 0; | |
196 | ||
197 | assert(!from || cli_verify(from)); | |
198 | ||
199 | cptr = alloc_client(); | |
200 | ||
201 | assert(0 != cptr); | |
202 | assert(!cli_magic(cptr)); | |
203 | assert(0 == from || 0 != cli_connect(from)); | |
204 | ||
205 | if (!from) { /* local client, allocate a struct Connection */ | |
206 | struct Connection *con = alloc_connection(); | |
207 | ||
208 | assert(0 != con); | |
209 | assert(!con_magic(con)); | |
210 | ||
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; | |
218 | ||
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(); | |
189935b1 | 222 | } else |
223 | cli_connect(cptr) = cli_connect(from); /* use 'from's connection */ | |
224 | ||
225 | assert(con_verify(cli_connect(cptr))); | |
226 | ||
227 | cli_magic(cptr) = CLIENT_MAGIC; | |
228 | cli_status(cptr) = status; | |
229 | cli_hnext(cptr) = cptr; | |
230 | strcpy(cli_username(cptr), "unknown"); | |
231 | ||
232 | return cptr; | |
233 | } | |
234 | ||
235 | /** Release a Connection. | |
236 | * @param[in] con Connection to free. | |
237 | */ | |
238 | void free_connection(struct Connection* con) | |
239 | { | |
240 | if (!con) | |
241 | return; | |
242 | ||
243 | assert(con_verify(con)); | |
244 | assert(0 == con_client(con)); | |
245 | ||
246 | dealloc_connection(con); /* deallocate the connection */ | |
247 | } | |
248 | ||
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. | |
254 | */ | |
255 | void free_client(struct Client* cptr) | |
256 | { | |
257 | if (!cptr) | |
258 | return; | |
259 | /* | |
260 | * forget to remove the client from the hash table? | |
261 | */ | |
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); | |
267 | ||
268 | Debug((DEBUG_LIST, "Freeing client %s [%p], connection %p", cli_name(cptr), | |
269 | cptr, cli_connect(cptr))); | |
270 | ||
271 | if (cli_auth(cptr)) | |
9f8856e9 | 272 | destroy_auth_request(cli_auth(cptr)); |
189935b1 | 273 | |
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); | |
277 | ||
278 | if (cli_from(cptr) == cptr) { /* in other words, we're local */ | |
279 | cli_from(cptr) = 0; | |
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 */ | |
283 | else { | |
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 */ | |
288 | } | |
289 | } | |
290 | ||
291 | cli_connect(cptr) = 0; | |
292 | ||
293 | dealloc_client(cptr); /* actually destroy the client */ | |
294 | } | |
295 | ||
296 | /** Allocate a new Server object for a client. | |
297 | * If Client::cli_serv == NULL, allocate a Server structure for it and | |
298 | * initialize it. | |
299 | * @param[in] cptr %Client to make into a server. | |
300 | * @return The value of cli_serv(\a cptr). | |
301 | */ | |
302 | struct Server *make_server(struct Client *cptr) | |
303 | { | |
304 | struct Server *serv = cli_serv(cptr); | |
305 | ||
306 | assert(cli_verify(cptr)); | |
307 | ||
308 | if (!serv) | |
309 | { | |
310 | serv = (struct Server*) MyMalloc(sizeof(struct Server)); | |
311 | assert(0 != serv); | |
312 | memset(serv, 0, sizeof(struct Server)); /* All variables are 0 by default */ | |
313 | servs.inuse++; | |
314 | servs.alloc++; | |
315 | cli_serv(cptr) = serv; | |
316 | cli_serv(cptr)->lag = 60000; | |
317 | *serv->by = '\0'; | |
318 | DupString(serv->last_error_msg, "<>"); /* String must be non-empty */ | |
319 | } | |
320 | return cli_serv(cptr); | |
321 | } | |
322 | ||
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. | |
328 | */ | |
329 | void remove_client_from_list(struct Client *cptr) | |
330 | { | |
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))); | |
335 | assert(!IsMe(cptr)); | |
336 | ||
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 | |
340 | */ | |
341 | if(cli_next(cptr)) | |
342 | { | |
343 | if (cli_prev(cptr)) | |
344 | cli_next(cli_prev(cptr)) = cli_next(cptr); | |
345 | else { | |
346 | GlobalClientList = cli_next(cptr); | |
347 | cli_prev(GlobalClientList) = 0; | |
348 | } | |
349 | cli_prev(cli_next(cptr)) = cli_prev(cptr); | |
350 | } | |
351 | cli_next(cptr) = cli_prev(cptr) = 0; | |
352 | ||
353 | if (IsUser(cptr) && cli_user(cptr)) { | |
354 | add_history(cptr, 0); | |
355 | off_history(cptr); | |
356 | } | |
357 | if (cli_user(cptr)) { | |
358 | free_user(cli_user(cptr)); | |
359 | cli_user(cptr) = 0; | |
360 | } | |
361 | ||
362 | if (cli_serv(cptr)) { | |
363 | if (cli_serv(cptr)->user) { | |
364 | free_user(cli_serv(cptr)->user); | |
365 | cli_serv(cptr)->user = 0; | |
366 | } | |
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)); | |
371 | --servs.inuse; | |
372 | --servs.alloc; | |
373 | } | |
374 | free_client(cptr); | |
375 | } | |
376 | ||
377 | /** Link \a cptr into #GlobalClientList. | |
378 | * @param[in] cptr Client to link into the global list. | |
379 | */ | |
380 | void add_client_to_list(struct Client *cptr) | |
381 | { | |
382 | assert(cli_verify(cptr)); | |
383 | assert(cli_next(cptr) == 0); | |
384 | assert(cli_prev(cptr) == 0); | |
385 | ||
386 | /* | |
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 | |
390 | */ | |
391 | cli_prev(cptr) = 0; | |
392 | cli_next(cptr) = GlobalClientList; | |
393 | GlobalClientList = cptr; | |
394 | if (cli_next(cptr)) | |
395 | cli_prev(cli_next(cptr)) = cptr; | |
396 | } | |
397 | ||
398 | #if 0 | |
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. | |
403 | */ | |
404 | void verify_client_list(void) | |
405 | { | |
406 | struct Client *client, *prev = 0; | |
407 | unsigned int visited = 0; | |
408 | ||
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 */ | |
418 | prev = client; | |
419 | } | |
420 | } | |
421 | #endif /* DEBUGMODE */ | |
422 | ||
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. | |
427 | */ | |
428 | struct SLink* make_link(void) | |
429 | { | |
430 | struct SLink* lp = slinkFreeList; | |
431 | if (lp) | |
432 | slinkFreeList = lp->next; | |
433 | else { | |
434 | lp = (struct SLink*) MyMalloc(sizeof(struct SLink)); | |
435 | links.alloc++; | |
436 | } | |
437 | assert(0 != lp); | |
438 | links.inuse++; | |
9f8856e9 | 439 | memset(lp, 0, sizeof(*lp)); |
189935b1 | 440 | return lp; |
441 | } | |
442 | ||
443 | /** Release a singly linked list element. | |
444 | * @param[in] lp List element to mark as unused. | |
445 | */ | |
446 | void free_link(struct SLink* lp) | |
447 | { | |
448 | if (lp) { | |
449 | lp->next = slinkFreeList; | |
450 | slinkFreeList = lp; | |
451 | } | |
452 | links.inuse--; | |
453 | } | |
454 | ||
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). | |
462 | */ | |
463 | struct DLink *add_dlink(struct DLink **lpp, struct Client *cp) | |
464 | { | |
465 | struct DLink* lp = (struct DLink*) MyMalloc(sizeof(struct DLink)); | |
466 | assert(0 != lp); | |
467 | lp->value.cptr = cp; | |
468 | lp->prev = 0; | |
469 | if ((lp->next = *lpp)) | |
470 | lp->next->prev = lp; | |
471 | *lpp = lp; | |
472 | return lp; | |
473 | } | |
474 | ||
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. | |
478 | */ | |
479 | void remove_dlink(struct DLink **lpp, struct DLink *lp) | |
480 | { | |
481 | assert(0 != lpp); | |
482 | assert(0 != lp); | |
483 | ||
484 | if (lp->prev) { | |
485 | if ((lp->prev->next = lp->next)) | |
486 | lp->next->prev = lp->prev; | |
487 | } | |
488 | else if ((*lpp = lp->next)) | |
489 | lp->next->prev = NULL; | |
490 | MyFree(lp); | |
491 | } | |
492 | ||
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. | |
498 | */ | |
499 | void send_liststats(struct Client *cptr, const struct liststats *lstats, | |
500 | const char *itemname, struct liststats *totals) | |
501 | { | |
502 | send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":%s: inuse %zu(%zu) alloc %zu", | |
503 | itemname, lstats->inuse, lstats->mem, lstats->alloc); | |
504 | if (totals) | |
505 | { | |
506 | totals->inuse += lstats->inuse; | |
507 | totals->alloc += lstats->alloc; | |
508 | totals->mem += lstats->mem; | |
509 | } | |
510 | } | |
511 | ||
512 | /** Report memory usage of list elements to \a cptr. | |
513 | * @param[in] cptr Client requesting information. | |
514 | * @param[in] name Unused pointer. | |
515 | */ | |
516 | void send_listinfo(struct Client *cptr, char *name) | |
517 | { | |
518 | struct liststats total; | |
519 | struct liststats confs; | |
520 | struct ConfItem *conf; | |
521 | ||
522 | memset(&total, 0, sizeof(total)); | |
523 | ||
524 | clients.mem = clients.inuse * sizeof(struct Client); | |
525 | send_liststats(cptr, &clients, "Clients", &total); | |
526 | ||
527 | connections.mem = connections.inuse * sizeof(struct Connection); | |
528 | send_liststats(cptr, &connections, "Connections", &total); | |
529 | ||
530 | servs.mem = servs.inuse * sizeof(struct Server); | |
531 | send_liststats(cptr, &servs, "Servers", &total); | |
532 | ||
533 | links.mem = links.inuse * sizeof(struct SLink); | |
534 | send_liststats(cptr, &links, "Links", &total); | |
535 | ||
536 | confs.alloc = GlobalConfCount; | |
537 | confs.mem = confs.alloc * sizeof(GlobalConfCount); | |
538 | for (confs.inuse = 0, conf = GlobalConfList; conf; conf = conf->next) | |
539 | confs.inuse++; | |
540 | send_liststats(cptr, &confs, "Confs", &total); | |
541 | ||
542 | send_liststats(cptr, &total, "Totals", NULL); | |
543 | } |