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 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 REQUIRE(rbufp != NULL);
330 if (mon_enabled == MON_OFF)
331 return ~(RES_LIMITED | RES_KOD) & flags;
333 pkt = &rbufp->recv_pkt;
334 hash = MON_HASH(&rbufp->recv_srcadr);
335 mode = PKT_MODE(pkt->li_vn_mode);
336 version = PKT_VERSION(pkt->li_vn_mode);
337 mon = mon_hash[hash];
340 * We keep track of all traffic for a given IP in one entry,
341 * otherwise cron'ed ntpdate or similar evades RES_LIMITED.
344 for (; mon != NULL; mon = mon->hash_next)
345 if (SOCK_EQ(&mon->rmtadr, &rbufp->recv_srcadr))
349 interval_fp = rbufp->recv_time;
350 L_SUB(&interval_fp, &mon->last);
351 /* add one-half second to round up */
352 L_ADDUF(&interval_fp, 0x80000000);
353 interval = interval_fp.l_i;
354 mon->last = rbufp->recv_time;
355 NSRCPORT(&mon->rmtadr) = NSRCPORT(&rbufp->recv_srcadr);
357 restrict_mask = flags;
358 mon->vn_mode = VN_MODE(version, mode);
360 /* Shuffle to the head of the MRU list. */
361 UNLINK_DLIST(mon, mru);
362 LINK_DLIST(mon_mru_list, mon, mru);
365 * At this point the most recent arrival is first in the
366 * MRU list. Decrease the counter by the headway, but
367 * not less than zero.
369 mon->leak -= interval;
370 mon->leak = max(0, mon->leak);
371 head = 1 << ntp_minpoll;
372 leak = mon->leak + head;
373 limit = NTP_SHIFT * head;
375 DPRINTF(2, ("MRU: interval %d headway %d limit %d\n",
376 interval, leak, limit));
379 * If the minimum and average thresholds are not
380 * exceeded, douse the RES_LIMITED and RES_KOD bits and
381 * increase the counter by the headway increment. Note
382 * that we give a 1-s grace for the minimum threshold
383 * and a 2-s grace for the headway increment. If one or
384 * both thresholds are exceeded and the old counter is
385 * less than the average threshold, set the counter to
386 * the average threshold plus the increment and leave
387 * the RES_LIMITED and RES_KOD bits lit. Otherwise,
388 * leave the counter alone and douse the RES_KOD bit.
389 * This rate-limits the KoDs to no less than the average
392 if (interval + 1 >= ntp_minpkt && leak < limit) {
393 mon->leak = leak - 2;
394 restrict_mask &= ~(RES_LIMITED | RES_KOD);
395 } else if (mon->leak < limit)
396 mon->leak = limit + head;
398 restrict_mask &= ~RES_KOD;
400 mon->flags = restrict_mask;
406 * If we got here, this is the first we've heard of this
407 * guy. Get him some memory, either from the free list
408 * or from the tail of the MRU list.
410 * The following ntp.conf "mru" knobs come into play determining
411 * the depth (or count) of the MRU list:
412 * - mru_mindepth ("mru mindepth") is a floor beneath which
413 * entries are kept without regard to their age. The
414 * default is 600 which matches the longtime implementation
415 * limit on the total number of entries.
416 * - mru_maxage ("mru maxage") is a ceiling on the age in
417 * seconds of entries. Entries older than this are
418 * reclaimed once mon_mindepth is exceeded. 64s default.
419 * Note that entries older than this can easily survive
420 * as they are reclaimed only as needed.
421 * - mru_maxdepth ("mru maxdepth") is a hard limit on the
423 * - "mru maxmem" sets mru_maxdepth to the number of entries
424 * which fit in the given number of kilobytes. The default is
425 * 1024, or 1 megabyte.
426 * - mru_initalloc ("mru initalloc" sets the count of the
427 * initial allocation of MRU entries.
428 * - "mru initmem" sets mru_initalloc in units of kilobytes.
430 * - mru_incalloc ("mru incalloc" sets the number of entries to
431 * allocate on-demand each time the free list is empty.
432 * - "mru incmem" sets mru_incalloc in units of kilobytes.
434 * Whichever of "mru maxmem" or "mru maxdepth" occurs last in
435 * ntp.conf controls. Similarly for "mru initalloc" and "mru
436 * initmem", and for "mru incalloc" and "mru incmem".
438 if (mru_entries < mru_mindepth) {
439 if (NULL == mon_free)
441 UNLINK_HEAD_SLIST(mon, mon_free, hash_next);
443 oldest = TAIL_DLIST(mon_mru_list, mru);
444 oldest_age = 0; /* silence uninit warning */
445 if (oldest != NULL) {
446 interval_fp = rbufp->recv_time;
447 L_SUB(&interval_fp, &oldest->last);
448 /* add one-half second to round up */
449 L_ADDUF(&interval_fp, 0x80000000);
450 oldest_age = interval_fp.l_i;
452 /* note -1 is legal for mru_maxage (disables) */
453 if (oldest != NULL && mru_maxage < oldest_age) {
454 mon_reclaim_entry(oldest);
456 } else if (mon_free != NULL || mru_alloc <
458 if (NULL == mon_free)
460 UNLINK_HEAD_SLIST(mon, mon_free, hash_next);
461 /* Preempt from the MRU list if old enough. */
462 } else if (ntp_random() / (2. * FRAC) >
463 (double)oldest_age / mon_age) {
464 return ~(RES_LIMITED | RES_KOD) & flags;
466 mon_reclaim_entry(oldest);
474 * Got one, initialize it
477 mru_peakentries = max(mru_peakentries, mru_entries);
478 mon->last = rbufp->recv_time;
479 mon->first = mon->last;
481 mon->flags = ~(RES_LIMITED | RES_KOD) & flags;
483 memcpy(&mon->rmtadr, &rbufp->recv_srcadr, sizeof(mon->rmtadr));
484 mon->vn_mode = VN_MODE(version, mode);
485 mon->lcladr = rbufp->dstadr;
486 mon->cast_flags = (u_char)(((rbufp->dstadr->flags &
487 INT_MCASTOPEN) && rbufp->fd == mon->lcladr->fd) ? MDF_MCAST
488 : rbufp->fd == mon->lcladr->bfd ? MDF_BCAST : MDF_UCAST);
491 * Drop him into front of the hash table. Also put him on top of
494 LINK_SLIST(mon_hash[hash], mon, hash_next);
495 LINK_DLIST(mon_mru_list, mon, mru);