1/*
2 * ntp_monitor - monitor ntpd statistics
3 */
4#ifdef HAVE_CONFIG_H
5# include <config.h>
6#endif
7
8#include "ntpd.h"
9#include "ntp_io.h"
10#include "ntp_if.h"
11#include "ntp_stdlib.h"
12#include <ntp_random.h>
13
14#include <stdio.h>
15#include <signal.h>
16#ifdef HAVE_SYS_IOCTL_H
17# include <sys/ioctl.h>
18#endif
19
20/*
21 * Record statistics based on source address, mode and version. The
22 * receive procedure calls us with the incoming rbufp before it does
23 * anything else. While at it, implement rate controls for inbound
24 * traffic.
25 *
26 * Each entry is doubly linked into two lists, a hash table and a most-
27 * recently-used (MRU) list. When a packet arrives it is looked up in
28 * the hash table. If found, the statistics are updated and the entry
29 * relinked at the head of the MRU list. If not found, a new entry is
30 * allocated, initialized and linked into both the hash table and at the
31 * head of the MRU list.
32 *
33 * Memory is usually allocated by grabbing a big chunk of new memory and
34 * cutting it up into littler pieces. The exception to this when we hit
35 * the memory limit. Then we free memory by grabbing entries off the
36 * tail for the MRU list, unlinking from the hash table, and
37 * reinitializing.
38 */
39/*
40 * Limits on the number of structures allocated.  This limit is picked
41 * with the illicit knowlege that we can only return somewhat less than
42 * 8K bytes in a mode 7 response packet, and that each structure will
43 * require about 20 bytes of space in the response.
44 *
45 * ... I don't believe the above is true anymore ... jdg
46 */
47#ifndef MAXMONMEM
48#define	MAXMONMEM	600	/* we allocate up to 600 structures */
49#endif
50#ifndef MONMEMINC
51#define	MONMEMINC	40	/* allocate them 40 at a time */
52#endif
53
54/*
55 * Hashing stuff
56 */
57#define	MON_HASH_SIZE	NTP_HASH_SIZE
58#define	MON_HASH_MASK	NTP_HASH_MASK
59#define	MON_HASH(addr)	NTP_HASH_ADDR(addr)
60
61/*
62 * Pointers to the hash table, the MRU list and the count table.  Memory
63 * for the hash and count tables is only allocated if monitoring is
64 * turned on.
65 */
66static	struct mon_data *mon_hash[MON_HASH_SIZE];  /* list ptrs */
67struct	mon_data mon_mru_list;
68
69/*
70 * List of free structures structures, and counters of free and total
71 * structures. The free structures are linked with the hash_next field.
72 */
73static  struct mon_data *mon_free;      /* free list or null if none */
74static	int mon_total_mem;		/* total structures allocated */
75static	int mon_mem_increments;		/* times called malloc() */
76
77/*
78 * Parameters of the RES_LIMITED restriction option. We define headway
79 * as the idle time between packets. A packet is discarded if the
80 * headway is less than the minimum, as well as if the average headway
81 * is less than eight times the increment.
82 */
83int	ntp_minpkt = NTP_MINPKT;	/* minimum (log 2 s) */
84int	ntp_minpoll = NTP_MINPOLL;	/* increment (log 2 s) */
85
86/*
87 * Initialization state.  We may be monitoring, we may not.  If
88 * we aren't, we may not even have allocated any memory yet.
89 */
90int	mon_enabled;			/* enable switch */
91int	mon_age = 3000;			/* preemption limit */
92static	int mon_have_memory;
93static	void	mon_getmoremem	(void);
94static	void	remove_from_hash (struct mon_data *);
95
96/*
97 * init_mon - initialize monitoring global data
98 */
99void
100init_mon(void)
101{
102	/*
103	 * Don't do much of anything here.  We don't allocate memory
104	 * until someone explicitly starts us.
105	 */
106	mon_enabled = MON_OFF;
107	mon_have_memory = 0;
108	mon_total_mem = 0;
109	mon_mem_increments = 0;
110	mon_free = NULL;
111	memset(&mon_hash[0], 0, sizeof mon_hash);
112	memset(&mon_mru_list, 0, sizeof mon_mru_list);
113}
114
115
116/*
117 * mon_start - start up the monitoring software
118 */
119void
120mon_start(
121	int mode
122	)
123{
124
125	if (mon_enabled != MON_OFF) {
126		mon_enabled |= mode;
127		return;
128	}
129	if (mode == MON_OFF)
130	    return;
131
132	if (!mon_have_memory) {
133		mon_total_mem = 0;
134		mon_mem_increments = 0;
135		mon_free = NULL;
136		mon_getmoremem();
137		mon_have_memory = 1;
138	}
139
140	mon_mru_list.mru_next = &mon_mru_list;
141	mon_mru_list.mru_prev = &mon_mru_list;
142	mon_enabled = mode;
143}
144
145
146/*
147 * mon_stop - stop the monitoring software
148 */
149void
150mon_stop(
151	int mode
152	)
153{
154	register struct mon_data *md, *md_next;
155	register int i;
156
157	if (mon_enabled == MON_OFF)
158		return;
159	if ((mon_enabled & mode) == 0 || mode == MON_OFF)
160		return;
161
162	mon_enabled &= ~mode;
163	if (mon_enabled != MON_OFF)
164		return;
165
166	/*
167	 * Put everything back on the free list
168	 */
169	for (i = 0; i < MON_HASH_SIZE; i++) {
170		md = mon_hash[i];               /* get next list */
171		mon_hash[i] = NULL;             /* zero the list head */
172		while (md != NULL) {
173			md_next = md->hash_next;
174			md->hash_next = mon_free;
175			mon_free = md;
176			md = md_next;
177		}
178	}
179	mon_mru_list.mru_next = &mon_mru_list;
180	mon_mru_list.mru_prev = &mon_mru_list;
181}
182
183void
184ntp_monclearinterface(struct interface *interface)
185{
186        struct mon_data *md;
187
188	for (md = mon_mru_list.mru_next; md != &mon_mru_list;
189	    md = md->mru_next) {
190		if (md->interface == interface) {
191		      /* dequeue from mru list and put to free list */
192		      md->mru_prev->mru_next = md->mru_next;
193		      md->mru_next->mru_prev = md->mru_prev;
194		      remove_from_hash(md);
195		      md->hash_next = mon_free;
196		      mon_free = md;
197		}
198	}
199}
200
201
202/*
203 * ntp_monitor - record stats about this packet
204 *
205 * Returns flags
206 */
207int
208ntp_monitor(
209	struct recvbuf *rbufp,
210	int	flags
211	)
212{
213	register struct pkt *pkt;
214	register struct mon_data *md;
215	sockaddr_u addr;
216	register u_int hash;
217	register int mode;
218	int	interval;
219
220	if (mon_enabled == MON_OFF)
221		return (flags);
222
223	pkt = &rbufp->recv_pkt;
224	memset(&addr, 0, sizeof(addr));
225	memcpy(&addr, &(rbufp->recv_srcadr), sizeof(addr));
226	hash = MON_HASH(&addr);
227	mode = PKT_MODE(pkt->li_vn_mode);
228	md = mon_hash[hash];
229	while (md != NULL) {
230		int	head;		/* headway increment */
231		int	leak;		/* new headway */
232		int	limit;		/* average threshold */
233
234		/*
235		 * Match address only to conserve MRU size.
236		 */
237		if (SOCK_EQ(&md->rmtadr, &addr)) {
238			interval = current_time - md->lasttime;
239			md->lasttime = current_time;
240			md->count++;
241			md->flags = flags;
242			md->rmtport = NSRCPORT(&rbufp->recv_srcadr);
243			md->mode = (u_char) mode;
244			md->version = PKT_VERSION(pkt->li_vn_mode);
245
246			/*
247			 * Shuffle to the head of the MRU list.
248			 */
249			md->mru_next->mru_prev = md->mru_prev;
250			md->mru_prev->mru_next = md->mru_next;
251			md->mru_next = mon_mru_list.mru_next;
252			md->mru_prev = &mon_mru_list;
253			mon_mru_list.mru_next->mru_prev = md;
254			mon_mru_list.mru_next = md;
255
256			/*
257			 * At this point the most recent arrival is
258			 * first in the MRU list. Decrease the counter
259			 * by the headway, but not less than zero.
260			 */
261			md->leak -= interval;
262			if (md->leak < 0)
263				md->leak = 0;
264			head = 1 << ntp_minpoll;
265			leak = md->leak + head;
266			limit = NTP_SHIFT * head;
267#ifdef DEBUG
268			if (debug > 1)
269				printf("restrict: interval %d headway %d limit %d\n",
270				    interval, leak, limit);
271#endif
272
273			/*
274			 * If the minimum and average thresholds are not
275			 * exceeded, douse the RES_LIMITED and RES_KOD
276			 * bits and increase the counter by the headway
277			 * increment. Note that we give a 1-s grace for
278			 * the minimum threshold and a 2-s grace for the
279			 * headway increment. If one or both thresholds
280			 * are exceeded and the old counter is less than
281			 * the average threshold, set the counter to the
282			 * average threshold plus the inrcrment and
283			 * leave the RES_KOD bit lit. Othewise, leave
284			 * the counter alone and douse the RES_KOD bit.
285			 * This rate-limits the KoDs to no less than the
286			 * average headway.
287			 */
288			if (interval + 1 >= (1 << ntp_minpkt) &&
289			    leak < limit) {
290				md->leak = leak - 2;
291				md->flags &= ~(RES_LIMITED | RES_KOD);
292			} else if (md->leak < limit) {
293				md->leak = limit + head;
294			} else {
295				md->flags &= ~RES_KOD;
296			}
297			return (md->flags);
298		}
299		md = md->hash_next;
300	}
301
302	/*
303	 * If we got here, this is the first we've heard of this
304	 * guy.  Get him some memory, either from the free list
305	 * or from the tail of the MRU list.
306	 */
307	if (mon_free == NULL && mon_total_mem >= MAXMONMEM) {
308
309		/*
310		 * Preempt from the MRU list if old enough.
311		 */
312		md = mon_mru_list.mru_prev;
313		if (md->count == 1 || ntp_random() / (2. * FRAC) >
314		    (double)(current_time - md->lasttime) / mon_age)
315			return (flags & ~RES_LIMITED);
316
317		md->mru_prev->mru_next = &mon_mru_list;
318		mon_mru_list.mru_prev = md->mru_prev;
319		remove_from_hash(md);
320	} else {
321		if (mon_free == NULL)
322			mon_getmoremem();
323		md = mon_free;
324		mon_free = md->hash_next;
325	}
326
327	/*
328	 * Got one, initialize it
329	 */
330	md->lasttime = md->firsttime = current_time;
331	md->count = 1;
332	md->flags = flags & ~RES_LIMITED;
333	md->leak = 0;
334	memset(&md->rmtadr, 0, sizeof(md->rmtadr));
335	memcpy(&md->rmtadr, &addr, sizeof(addr));
336	md->rmtport = NSRCPORT(&rbufp->recv_srcadr);
337	md->mode = (u_char) mode;
338	md->version = PKT_VERSION(pkt->li_vn_mode);
339	md->interface = rbufp->dstadr;
340	md->cast_flags = (u_char)(((rbufp->dstadr->flags &
341	    INT_MCASTOPEN) && rbufp->fd == md->interface->fd) ?
342	    MDF_MCAST: rbufp->fd == md->interface->bfd ? MDF_BCAST :
343	    MDF_UCAST);
344
345	/*
346	 * Drop him into front of the hash table. Also put him on top of
347	 * the MRU list.
348	 */
349	md->hash_next = mon_hash[hash];
350	mon_hash[hash] = md;
351	md->mru_next = mon_mru_list.mru_next;
352	md->mru_prev = &mon_mru_list;
353	mon_mru_list.mru_next->mru_prev = md;
354	mon_mru_list.mru_next = md;
355	return (md->flags);
356}
357
358
359/*
360 * mon_getmoremem - get more memory and put it on the free list
361 */
362static void
363mon_getmoremem(void)
364{
365	register struct mon_data *md;
366	register int i;
367	struct mon_data *freedata;      /* 'old' free list (null) */
368
369	md = (struct mon_data *)emalloc(MONMEMINC *
370	    sizeof(struct mon_data));
371	freedata = mon_free;
372	mon_free = md;
373	for (i = 0; i < (MONMEMINC-1); i++) {
374		md->hash_next = (md + 1);
375		md++;
376	}
377
378	/*
379	 * md now points at the last.  Link in the rest of the chain.
380	 */
381	md->hash_next = freedata;
382	mon_total_mem += MONMEMINC;
383	mon_mem_increments++;
384}
385
386static void
387remove_from_hash(
388	struct mon_data *md
389	)
390{
391	register u_int hash;
392	register struct mon_data *md_prev;
393
394	hash = MON_HASH(&md->rmtadr);
395	if (mon_hash[hash] == md) {
396		mon_hash[hash] = md->hash_next;
397	} else {
398		md_prev = mon_hash[hash];
399		while (md_prev->hash_next != md) {
400			md_prev = md_prev->hash_next;
401			if (md_prev == NULL) {
402				/* logic error */
403				return;
404			}
405		}
406		md_prev->hash_next = md->hash_next;
407	}
408}
409