2 * ntp_monitor - monitor ntpd statistics
11 #include "ntp_lists.h"
12 #include "ntp_stdlib.h"
13 #include <ntp_random.h>
17 #ifdef HAVE_SYS_IOCTL_H
18 # include <sys/ioctl.h>
22 * Record statistics based on source address, mode and version. The
23 * receive procedure calls us with the incoming rbufp before it does
24 * anything else. While at it, implement rate controls for inbound
27 * Each entry is doubly linked into two lists, a hash table and a most-
28 * recently-used (MRU) list. When a packet arrives it is looked up in
29 * the hash table. If found, the statistics are updated and the entry
30 * relinked at the head of the MRU list. If not found, a new entry is
31 * allocated, initialized and linked into both the hash table and at the
32 * head of the MRU list.
34 * Memory is usually allocated by grabbing a big chunk of new memory and
35 * cutting it up into littler pieces. The exception to this when we hit
36 * the memory limit. Then we free memory by grabbing entries off the
37 * tail for the MRU list, unlinking from the hash table, and
40 * INC_MONLIST is the default allocation granularity in entries.
41 * INIT_MONLIST is the default initial allocation in entries.
43 #ifdef MONMEMINC /* old name */
44 # define INC_MONLIST MONMEMINC
45 #elif !defined(INC_MONLIST)
46 # define INC_MONLIST (4 * 1024 / sizeof(mon_entry))
49 # define INIT_MONLIST (4 * 1024 / sizeof(mon_entry))
51 #ifndef MRU_MAXDEPTH_DEF
52 # define MRU_MAXDEPTH_DEF (1024 * 1024 / sizeof(mon_entry))
61 * Pointers to the hash table and the MRU list. Memory for the hash
62 * table is allocated only if monitoring is enabled.
64 mon_entry ** mon_hash; /* MRU hash table */
65 mon_entry mon_mru_list; /* mru listhead */
68 * List of free structures structures, and counters of in-use and total
69 * structures. The free structures are linked with the hash_next field.
71 static mon_entry *mon_free; /* free list or null if none */
72 u_int mru_alloc; /* mru list + free list count */
73 u_int mru_entries; /* mru list count */
74 u_int mru_peakentries; /* highest mru_entries seen */
75 u_int mru_initalloc = INIT_MONLIST;/* entries to preallocate */
76 u_int mru_incalloc = INC_MONLIST;/* allocation batch factor */
77 static u_int mon_mem_increments; /* times called malloc() */
80 * Parameters of the RES_LIMITED restriction option. We define headway
81 * as the idle time between packets. A packet is discarded if the
82 * headway is less than the minimum, as well as if the average headway
83 * is less than eight times the increment.
85 int ntp_minpkt = NTP_MINPKT; /* minimum (log 2 s) */
86 u_char ntp_minpoll = NTP_MINPOLL; /* increment (log 2 s) */
89 * Initialization state. We may be monitoring, we may not. If
90 * we aren't, we may not even have allocated any memory yet.
92 u_int mon_enabled; /* enable switch */
93 u_int mru_mindepth = 600; /* preempt above this */
94 int mru_maxage = 64; /* for entries older than */
95 u_int mru_maxdepth = /* MRU count hard limit */
97 int mon_age = 3000; /* preemption limit */
99 static void mon_getmoremem(void);
100 static void remove_from_hash(mon_entry *);
101 static inline void mon_free_entry(mon_entry *);
102 static inline void mon_reclaim_entry(mon_entry *);
106 * init_mon - initialize monitoring global data
112 * Don't do much of anything here. We don't allocate memory
115 mon_enabled = MON_OFF;
116 INIT_DLIST(mon_mru_list, mru);
121 * remove_from_hash - removes an entry from the address hash table and
122 * decrements mru_entries.
130 mon_entry *punlinked;
133 hash = MON_HASH(&mon->rmtadr);
134 UNLINK_SLIST(punlinked, mon_hash[hash], mon, hash_next,
136 NTP_ENSURE(punlinked == mon);
146 LINK_SLIST(mon_free, m, hash_next);
151 * mon_reclaim_entry - Remove an entry from the MRU list and from the
152 * hash array, then zero-initialize it. Indirectly
153 * decrements mru_entries.
155 * The entry is prepared to be reused. Before return, in
156 * remove_from_hash(), mru_entries is decremented. It is the caller's
157 * responsibility to increment it again.
164 DEBUG_INSIST(NULL != m);
166 UNLINK_DLIST(m, mru);
173 * mon_getmoremem - get more memory and put it on the free list
181 entries = (0 == mon_mem_increments)
186 chunk = eallocarray(entries, sizeof(*chunk));
187 mru_alloc += entries;
188 for (chunk += entries; entries; entries--)
189 mon_free_entry(--chunk);
191 mon_mem_increments++;
197 * mon_start - start up the monitoring software
205 u_int min_hash_slots;
207 if (MON_OFF == mode) /* MON_OFF is 0 */
213 if (0 == mon_mem_increments)
216 * Select the MRU hash table size to limit the average count
217 * per bucket at capacity (mru_maxdepth) to 8, if possible
218 * given our hash is limited to 16 bits.
220 min_hash_slots = (mru_maxdepth / 8) + 1;
222 while (min_hash_slots >>= 1)
224 mon_hash_bits = max(4, mon_hash_bits);
225 mon_hash_bits = min(16, mon_hash_bits);
226 octets = sizeof(*mon_hash) * MON_HASH_SIZE;
227 mon_hash = erealloc_zero(mon_hash, octets, 0);
234 * mon_stop - stop the monitoring software
243 if (MON_OFF == mon_enabled)
245 if ((mon_enabled & mode) == 0 || mode == MON_OFF)
248 mon_enabled &= ~mode;
249 if (mon_enabled != MON_OFF)
253 * Move everything on the MRU list to the free list quickly,
254 * without bothering to remove each from either the MRU list or
257 ITER_DLIST_BEGIN(mon_mru_list, mon, mru, mon_entry)
261 /* empty the MRU list and hash table. */
263 INIT_DLIST(mon_mru_list, mru);
264 zero_mem(mon_hash, sizeof(*mon_hash) * MON_HASH_SIZE);
269 * mon_clearinterface -- remove mru entries referring to a local address
270 * which is going away.
279 /* iterate mon over mon_mru_list */
280 ITER_DLIST_BEGIN(mon_mru_list, mon, mru, mon_entry)
281 if (mon->lcladr == lcladr) {
282 /* remove from mru list */
283 UNLINK_DLIST(mon, mru);
284 /* remove from hash list, adjust mru_entries */
285 remove_from_hash(mon);
286 /* put on free list */
294 * ntp_monitor - record stats about this packet
296 * Returns supplied restriction flags, with RES_LIMITED and RES_KOD
297 * cleared unless the packet should not be responded to normally
298 * (RES_LIMITED) and possibly should trigger a KoD response (RES_KOD).
299 * The returned flags are saved in the MRU entry, so that it reflects
300 * whether the last packet from that source triggered rate limiting,
301 * and if so, possible KoD response. This implies you can not tell
302 * whether a given address is eligible for rate limiting/KoD from the
303 * monlist restrict bits, only whether or not the last packet triggered
304 * such responses. ntpdc -c reslist lets you see whether RES_LIMITED
305 * or RES_KOD is lit for a particular address before ntp_monitor()'s
310 struct recvbuf *rbufp,
320 u_short restrict_mask;
324 int head; /* headway increment */
325 int leak; /* new headway */
326 int limit; /* average threshold */
328 if (mon_enabled == MON_OFF)
329 return ~(RES_LIMITED | RES_KOD) & flags;
331 pkt = &rbufp->recv_pkt;
332 hash = MON_HASH(&rbufp->recv_srcadr);
333 mode = PKT_MODE(pkt->li_vn_mode);
334 version = PKT_VERSION(pkt->li_vn_mode);
335 mon = mon_hash[hash];
338 * We keep track of all traffic for a given IP in one entry,
339 * otherwise cron'ed ntpdate or similar evades RES_LIMITED.
342 for (; mon != NULL; mon = mon->hash_next)
343 if (SOCK_EQ(&mon->rmtadr, &rbufp->recv_srcadr))
347 interval_fp = rbufp->recv_time;
348 L_SUB(&interval_fp, &mon->last);
349 /* add one-half second to round up */
350 L_ADDUF(&interval_fp, 0x80000000);
351 interval = interval_fp.l_i;
352 mon->last = rbufp->recv_time;
353 NSRCPORT(&mon->rmtadr) = NSRCPORT(&rbufp->recv_srcadr);
355 restrict_mask = flags;
356 mon->vn_mode = VN_MODE(version, mode);
358 /* Shuffle to the head of the MRU list. */
359 UNLINK_DLIST(mon, mru);
360 LINK_DLIST(mon_mru_list, mon, mru);
363 * At this point the most recent arrival is first in the
364 * MRU list. Decrease the counter by the headway, but
365 * not less than zero.
367 mon->leak -= interval;
368 mon->leak = max(0, mon->leak);
369 head = 1 << ntp_minpoll;
370 leak = mon->leak + head;
371 limit = NTP_SHIFT * head;
373 DPRINTF(2, ("MRU: interval %d headway %d limit %d\n",
374 interval, leak, limit));
377 * If the minimum and average thresholds are not
378 * exceeded, douse the RES_LIMITED and RES_KOD bits and
379 * increase the counter by the headway increment. Note
380 * that we give a 1-s grace for the minimum threshold
381 * and a 2-s grace for the headway increment. If one or
382 * both thresholds are exceeded and the old counter is
383 * less than the average threshold, set the counter to
384 * the average threshold plus the increment and leave
385 * the RES_LIMITED and RES_KOD bits lit. Otherwise,
386 * leave the counter alone and douse the RES_KOD bit.
387 * This rate-limits the KoDs to no less than the average
390 if (interval + 1 >= ntp_minpkt && leak < limit) {
391 mon->leak = leak - 2;
392 restrict_mask &= ~(RES_LIMITED | RES_KOD);
393 } else if (mon->leak < limit)
394 mon->leak = limit + head;
396 restrict_mask &= ~RES_KOD;
398 mon->flags = restrict_mask;
404 * If we got here, this is the first we've heard of this
405 * guy. Get him some memory, either from the free list
406 * or from the tail of the MRU list.
408 * The following ntp.conf "mru" knobs come into play determining
409 * the depth (or count) of the MRU list:
410 * - mru_mindepth ("mru mindepth") is a floor beneath which
411 * entries are kept without regard to their age. The
412 * default is 600 which matches the longtime implementation
413 * limit on the total number of entries.
414 * - mru_maxage ("mru maxage") is a ceiling on the age in
415 * seconds of entries. Entries older than this are
416 * reclaimed once mon_mindepth is exceeded. 64s default.
417 * Note that entries older than this can easily survive
418 * as they are reclaimed only as needed.
419 * - mru_maxdepth ("mru maxdepth") is a hard limit on the
421 * - "mru maxmem" sets mru_maxdepth to the number of entries
422 * which fit in the given number of kilobytes. The default is
423 * 1024, or 1 megabyte.
424 * - mru_initalloc ("mru initalloc" sets the count of the
425 * initial allocation of MRU entries.
426 * - "mru initmem" sets mru_initalloc in units of kilobytes.
428 * - mru_incalloc ("mru incalloc" sets the number of entries to
429 * allocate on-demand each time the free list is empty.
430 * - "mru incmem" sets mru_incalloc in units of kilobytes.
432 * Whichever of "mru maxmem" or "mru maxdepth" occurs last in
433 * ntp.conf controls. Similarly for "mru initalloc" and "mru
434 * initmem", and for "mru incalloc" and "mru incmem".
436 if (mru_entries < mru_mindepth) {
437 if (NULL == mon_free)
439 UNLINK_HEAD_SLIST(mon, mon_free, hash_next);
441 oldest = TAIL_DLIST(mon_mru_list, mru);
442 oldest_age = 0; /* silence uninit warning */
443 if (oldest != NULL) {
444 interval_fp = rbufp->recv_time;
445 L_SUB(&interval_fp, &oldest->last);
446 /* add one-half second to round up */
447 L_ADDUF(&interval_fp, 0x80000000);
448 oldest_age = interval_fp.l_i;
450 /* note -1 is legal for mru_maxage (disables) */
451 if (oldest != NULL && mru_maxage < oldest_age) {
452 mon_reclaim_entry(oldest);
454 } else if (mon_free != NULL || mru_alloc <
456 if (NULL == mon_free)
458 UNLINK_HEAD_SLIST(mon, mon_free, hash_next);
459 /* Preempt from the MRU list if old enough. */
460 } else if (ntp_random() / (2. * FRAC) >
461 (double)oldest_age / mon_age) {
462 return ~(RES_LIMITED | RES_KOD) & flags;
464 mon_reclaim_entry(oldest);
470 * Got one, initialize it
473 mru_peakentries = max(mru_peakentries, mru_entries);
474 mon->last = rbufp->recv_time;
475 mon->first = mon->last;
477 mon->flags = ~(RES_LIMITED | RES_KOD) & flags;
479 memcpy(&mon->rmtadr, &rbufp->recv_srcadr, sizeof(mon->rmtadr));
480 mon->vn_mode = VN_MODE(version, mode);
481 mon->lcladr = rbufp->dstadr;
482 mon->cast_flags = (u_char)(((rbufp->dstadr->flags &
483 INT_MCASTOPEN) && rbufp->fd == mon->lcladr->fd) ? MDF_MCAST
484 : rbufp->fd == mon->lcladr->bfd ? MDF_BCAST : MDF_UCAST);
487 * Drop him into front of the hash table. Also put him on top of
490 LINK_SLIST(mon_hash[hash], mon, hash_next);
491 LINK_DLIST(mon_mru_list, mon, mru);