2 * IRC - Internet Relay Chat, ircd/whowas.c
3 * Copyright (C) 1990 Markku Savela
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 1, or (at your option)
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 * --- avalon --- 6th April 1992
20 * rewritten to scrap linked lists and use a table of structures which
21 * is referenced like a circular loop. Should be faster and more efficient.
23 * --- comstud --- 25th March 1997
24 * Everything rewritten from scratch. Avalon's code was bad. My version
25 * is faster and more efficient. No more hangs on /squits and you can
26 * safely raise NICKNAMEHISTORYLENGTH to a higher value without hurting
29 * --- comstud --- 5th August 1997
30 * Fixed for Undernet..
32 * --- Run --- 27th August 1997
33 * Speeded up the code, added comments.
40 #include "ircd_alloc.h"
41 #include "ircd_chattr.h"
42 #include "ircd_features.h"
44 #include "ircd_string.h"
55 /* #include <assert.h> -- Now using assert in ircd_log.h */
60 /** Keeps track of whowas least-recently-used list. */
62 struct Whowas
*ww_list
; /**< list of whowas structures */
63 struct Whowas
*ww_tail
; /**< tail of list for getting structures */
64 unsigned int ww_alloc
; /**< alloc count */
65 } wwList
= { 0, 0, 0 };
67 /** Hash table of Whowas entries by nickname. */
68 struct Whowas
* whowashash
[WW_MAX
];
71 * @brief Manipulation functions for the whowas list.
72 * @version $Id: whowas.c,v 1.17 2005/03/20 16:06:30 entrope Exp $
74 * Since the introduction of numeric nicks (at least for upstream messages,
75 * like MODE +o <nick>, KICK #chan <nick>, KILL <nick> etc), there is no
76 * real important reason for a nick history anymore.
77 * Nevertheless, there are two reason why we might want to keep it:
78 * @li The /WHOWAS command, which is often useful to catch harassing
79 * users or abusers in general.
80 * @li Clients still use the normal nicks in the client-server protocol,
81 * and it might be considered a nice feature that here we still have
84 * Note however that BOTH reasons make it redundant to keep a whowas history
85 * for users that split off.
87 * The rewrite of comstud was many to safe cpu during net.breaks and therefore
88 * a bit redundant imho (Run).
90 * But - it was written anyway. So lets look at the structure of the
93 * We still have a static table of 'struct Whowas' structures in which we add
94 * new nicks (plus info) as in a rotating buffer. We keep a global pointer
95 * `whowas_next' that points to the next entry to be overwritten - or to
96 * the oldest entry in the table (which is the same).
98 * Each entry keeps pointers for two doubly linked lists (thus four pointers):
99 * A list of the entries that have the same hash value ('hashv list'), and
100 * a list of the entries that have the same online pointer (`online list').
101 * Note that the last list (pointers) is only updated as long as online points
102 * to the corresponding client: As soon as the client signs off, this list
103 * is not anymore maintained (and hopefully not used anymore either ;).
105 * So now we have two ways of accessing this database:
106 * @li Given a <nick> we can calculate a hashv and then whowashash[hashv] will
107 * point to the start of the 'hash list': all entries with the same hashv.
108 * We'll have to search this list to find the entry with the correct <nick>.
109 * Once we found the correct whowas entry, we have a pointer to the
110 * corresponding client - if still online - for nick chasing purposes.
111 * Note that the same nick can occur multiple times in the whowas history,
112 * each of these having the same hash value of course. While a /WHOWAS on
113 * just a nick will return all entries, nick chasing will only find the
114 * first in the list. Because new entries are added at the start of the
115 * 'hash list' we will always find the youngest entry, which is what we want.
116 * @li Given an online client we have a pointer to the first whowas entry
117 * of the linked list of whowas entries that all belong to this client.
118 * We ONLY need this to reset all `online' pointers when this client
123 * Note that following:
125 * @li We *only* (need to) change the 'hash list' and the 'online' list
127 * @li There we always ADD an entry to the BEGINNING of the 'hash list'
128 * and the 'online list': *new* entries are at the start of the lists.
129 * The oldest entries are at the end of the lists.
130 * @li We always REMOVE the oldest entry we have (whowas_next), this means
131 * that this is always an entry that is at the *end* of the 'hash list'
132 * and 'online list' that it is a part of: the next pointer will
134 * @li The previous pointer is *only* used to update the next pointer of the
135 * previous entry, therefore we could better use a pointer to this
136 * next pointer: That is faster - saves us a 'if' test (it will never be
137 * NULL because the last added entry will point to the pointer that
138 * points to the start of the list) and we won't need special code to
139 * update the list start pointers.
141 * I incorporated these considerations into the code below.
146 /** Unlink a Whowas structure and free everything inside it.
147 * @param[in,out] ww The whowas record to free.
148 * @return The pointer \a ww.
150 static struct Whowas
*
151 whowas_clean(struct Whowas
*ww
)
156 Debug((DEBUG_LIST
, "Cleaning whowas structure for %s", ww
->name
));
158 if (ww
->online
) { /* unlink from client */
159 if (ww
->cnext
) /* shouldn't happen, but I'm not confident of that */
160 ww
->cnext
->cprevnextp
= ww
->cprevnextp
;
161 *ww
->cprevnextp
= ww
->cnext
;
164 if (ww
->hnext
) /* now unlink from hash table */
165 ww
->hnext
->hprevnextp
= ww
->hprevnextp
;
166 *ww
->hprevnextp
= ww
->hnext
;
168 if (ww
->wnext
) /* unlink from whowas linked list... */
169 ww
->wnext
->wprev
= ww
->wprev
;
171 ww
->wprev
->wnext
= ww
->wnext
;
173 if (wwList
.ww_tail
== ww
) /* update tail pointer appropriately */
174 wwList
.ww_tail
= ww
->wprev
;
180 MyFree(ww
->username
);
182 MyFree(ww
->hostname
);
184 MyFree(ww
->realhost
);
186 MyFree(ww
->servername
);
188 MyFree(ww
->realname
);
195 /** Clean and free a whowas record.
196 * @param[in] ww Whowas record to free.
199 whowas_free(struct Whowas
*ww
)
204 Debug((DEBUG_LIST
, "Destroying whowas structure for %s", ww
->name
));
212 /** Initialize a whowas record.
213 * @param[in,out] ww Whowas record to initialize.
214 * @return The pointer \a ww.
216 static struct Whowas
*
217 whowas_init(struct Whowas
*ww
)
220 memset(ww
, 0, sizeof(*ww
));
224 /** Return a fresh Whowas record.
225 * If the total number of records is smaller than determined by
226 * FEAT_NICKNAMEHISTORYLENGTH, allocate a new one. Otherwise,
227 * reuse the oldest record in use.
228 * @return A pointer to a clean Whowas.
230 static struct Whowas
*
233 if (wwList
.ww_alloc
>= feature_int(FEAT_NICKNAMEHISTORYLENGTH
))
234 return whowas_init(whowas_clean(wwList
.ww_tail
));
236 wwList
.ww_alloc
++; /* going to allocate a new one... */
237 return whowas_init((struct Whowas
*) MyMalloc(sizeof(struct Whowas
)));
240 /** If necessary, trim the whowas list.
241 * This function trims the whowas list until it contains no more than
242 * FEAT_NICKNAMEHISTORYLENGTH records.
247 Debug((DEBUG_LIST
, "whowas_realloc() called with alloc count %d, "
248 "history length %d, tail pointer %p", wwList
.ww_alloc
,
249 feature_int(FEAT_NICKNAMEHISTORYLENGTH
), wwList
.ww_tail
));
251 while (wwList
.ww_alloc
> feature_int(FEAT_NICKNAMEHISTORYLENGTH
)) {
252 if (!wwList
.ww_tail
) { /* list is empty... */
253 Debug((DEBUG_LIST
, "whowas list emptied with alloc count %d",
258 whowas_free(wwList
.ww_tail
); /* free oldest element of whowas list */
262 /** Add a client to the whowas list.
263 * @param[in] cptr Client to add.
264 * @param[in] still_on If non-zero, link the record to the client's personal history.
266 void add_history(struct Client
*cptr
, int still_on
)
270 if (!(ww
= whowas_alloc()))
271 return; /* couldn't get a structure */
273 ww
->hashv
= hash_whowas_name(cli_name(cptr
)); /* initialize struct */
274 ww
->logoff
= CurrentTime
;
275 DupString(ww
->name
, cli_name(cptr
));
276 DupString(ww
->username
, cli_user(cptr
)->username
);
277 DupString(ww
->hostname
, cli_user(cptr
)->host
);
278 if (HasHiddenHost(cptr
))
279 DupString(ww
->realhost
, cli_user(cptr
)->realhost
);
280 DupString(ww
->servername
, cli_name(cli_user(cptr
)->server
));
281 DupString(ww
->realname
, cli_info(cptr
));
282 if (cli_user(cptr
)->away
)
283 DupString(ww
->away
, cli_user(cptr
)->away
);
285 if (still_on
) { /* user changed nicknames... */
287 if ((ww
->cnext
= cli_whowas(cptr
)))
288 ww
->cnext
->cprevnextp
= &ww
->cnext
;
289 ww
->cprevnextp
= &(cli_whowas(cptr
));
290 cli_whowas(cptr
) = ww
;
291 } else /* user quit */
294 /* link new whowas structure to list */
295 ww
->wnext
= wwList
.ww_list
;
297 wwList
.ww_list
->wprev
= ww
;
300 if (!wwList
.ww_tail
) /* update the tail pointer... */
303 /* Now link it into the hash table */
304 if ((ww
->hnext
= whowashash
[ww
->hashv
]))
305 ww
->hnext
->hprevnextp
= &ww
->hnext
;
306 ww
->hprevnextp
= &whowashash
[ww
->hashv
];
307 whowashash
[ww
->hashv
] = ww
;
310 /** Clear all Whowas::online pointers that point to a client.
311 * @param[in] cptr Client who is going offline.
313 void off_history(const struct Client
*cptr
)
317 for (temp
= cli_whowas(cptr
); temp
; temp
= temp
->cnext
)
321 /** Find a client who has recently used a particular nickname.
322 * @param[in] nick Nickname to find.
323 * @param[in] timelimit Maximum age for entry.
324 * @return User's online client, or NULL if none is found.
326 struct Client
*get_history(const char *nick
, time_t timelimit
)
328 struct Whowas
*temp
= whowashash
[hash_whowas_name(nick
)];
329 timelimit
= CurrentTime
- timelimit
;
331 for (; temp
; temp
= temp
->hnext
)
332 if (0 == ircd_strcmp(nick
, temp
->name
) && temp
->logoff
> timelimit
)
338 /** Count memory used by whowas list.
339 * @param[out] wwu Number of entries in whowas list.
340 * @param[out] wwum Total number of bytes used by nickname, username,
341 * hostname and servername fields.
342 * @param[out] wwa Number of away strings in whowas list.
343 * @param[out] wwam Total number of bytes used by away strings.
345 void count_whowas_memory(int *wwu
, size_t *wwum
, int *wwa
, size_t *wwam
)
357 for (tmp
= wwList
.ww_list
; tmp
; tmp
= tmp
->wnext
) {
359 um
+= (strlen(tmp
->name
) + 1);
360 um
+= (strlen(tmp
->username
) + 1);
361 um
+= (strlen(tmp
->hostname
) + 1);
362 um
+= (strlen(tmp
->servername
) + 1);
365 am
+= (strlen(tmp
->away
) + 1);
374 /** Initialize whowas table. */
375 void initwhowas(void)
379 for (i
= 0; i
< WW_MAX
; i
++)
383 /** Calculate a hash value for a string.
384 * @param[in] name Nickname to calculate hash over.
385 * @return Calculated hash value.
387 unsigned int hash_whowas_name(const char *name
)
389 unsigned int hash
= 0;
390 unsigned int hash2
= 0;
395 lower
= ToLower(*name
);
396 hash
= (hash
<< 1) + lower
;
397 hash2
= (hash2
>> 1) + lower
;
401 return ((hash
& WW_MAX_INITIAL_MASK
) << BITS_PER_COL
) +
402 (hash2
& BITS_PER_COL_MASK
);