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_lists.h"
12 #include "ntp_stdlib.h"
13 #include <ntp_random.h>
14
15 #include <stdio.h>
16 #include <signal.h>
17 #ifdef HAVE_SYS_IOCTL_H
18 # include <sys/ioctl.h>
19 #endif
20
21 /*
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
25 * traffic.
26 *
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.
33 *
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
38 * reinitializing.
39 *
40 * INC_MONLIST is the default allocation granularity in entries.
41 * INIT_MONLIST is the default initial allocation in entries.
42 */
43 #ifdef MONMEMINC /* old name */
44 # define INC_MONLIST MONMEMINC
45 #elif !defined(INC_MONLIST)
46 # define INC_MONLIST (4 * 1024 / sizeof(mon_entry))
47 #endif
48 #ifndef INIT_MONLIST
49 # define INIT_MONLIST (4 * 1024 / sizeof(mon_entry))
50 #endif
51 #ifndef MRU_MAXDEPTH_DEF
52 # define MRU_MAXDEPTH_DEF (1024 * 1024 / sizeof(mon_entry))
53 #endif
54
55 /*
56 * Hashing stuff
57 */
58 u_char mon_hash_bits;
59
60 /*
61 * Pointers to the hash table and the MRU list. Memory for the hash
62 * table is allocated only if monitoring is enabled.
63 */
64 mon_entry ** mon_hash; /* MRU hash table */
65 mon_entry mon_mru_list; /* mru listhead */
66
67 /*
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.
70 */
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() */
78
79 /*
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.
84 */
85 int ntp_minpkt = NTP_MINPKT; /* minimum (log 2 s) */
86 u_char ntp_minpoll = NTP_MINPOLL; /* increment (log 2 s) */
87
88 /*
89 * Initialization state. We may be monitoring, we may not. If
90 * we aren't, we may not even have allocated any memory yet.
91 */
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 */
96 MRU_MAXDEPTH_DEF;
97 int mon_age = 3000; /* preemption limit */
98
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 *);
103
104
105 /*
106 * init_mon - initialize monitoring global data
107 */
108 void
init_mon(void)109 init_mon(void)
110 {
111 /*
112 * Don't do much of anything here. We don't allocate memory
113 * until mon_start().
114 */
115 mon_enabled = MON_OFF;
116 INIT_DLIST(mon_mru_list, mru);
117 }
118
119
120 /*
121 * remove_from_hash - removes an entry from the address hash table and
122 * decrements mru_entries.
123 */
124 static void
remove_from_hash(mon_entry * mon)125 remove_from_hash(
126 mon_entry *mon
127 )
128 {
129 u_int hash;
130 mon_entry *punlinked;
131
132 mru_entries--;
133 hash = MON_HASH(&mon->rmtadr);
134 UNLINK_SLIST(punlinked, mon_hash[hash], mon, hash_next,
135 mon_entry);
136 ENSURE(punlinked == mon);
137 }
138
139
140 static inline void
mon_free_entry(mon_entry * m)141 mon_free_entry(
142 mon_entry *m
143 )
144 {
145 ZERO(*m);
146 LINK_SLIST(mon_free, m, hash_next);
147 }
148
149
150 /*
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.
154
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.
158 */
159 static inline void
mon_reclaim_entry(mon_entry * m)160 mon_reclaim_entry(
161 mon_entry *m
162 )
163 {
164 DEBUG_INSIST(NULL != m);
165
166 UNLINK_DLIST(m, mru);
167 remove_from_hash(m);
168 ZERO(*m);
169 }
170
171
172 /*
173 * mon_getmoremem - get more memory and put it on the free list
174 */
175 static void
mon_getmoremem(void)176 mon_getmoremem(void)
177 {
178 mon_entry *chunk;
179 u_int entries;
180
181 entries = (0 == mon_mem_increments)
182 ? mru_initalloc
183 : mru_incalloc;
184
185 if (entries) {
186 chunk = eallocarray(entries, sizeof(*chunk));
187 mru_alloc += entries;
188 for (chunk += entries; entries; entries--)
189 mon_free_entry(--chunk);
190
191 mon_mem_increments++;
192 }
193 }
194
195
196 /*
197 * mon_start - start up the monitoring software
198 */
199 void
mon_start(int mode)200 mon_start(
201 int mode
202 )
203 {
204 size_t octets;
205 u_int min_hash_slots;
206
207 if (MON_OFF == mode) /* MON_OFF is 0 */
208 return;
209 if (mon_enabled) {
210 mon_enabled |= mode;
211 return;
212 }
213 if (0 == mon_mem_increments)
214 mon_getmoremem();
215 /*
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.
219 */
220 min_hash_slots = (mru_maxdepth / 8) + 1;
221 mon_hash_bits = 0;
222 while (min_hash_slots >>= 1)
223 mon_hash_bits++;
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);
228
229 mon_enabled = mode;
230 }
231
232
233 /*
234 * mon_stop - stop the monitoring software
235 */
236 void
mon_stop(int mode)237 mon_stop(
238 int mode
239 )
240 {
241 mon_entry *mon;
242
243 if (MON_OFF == mon_enabled)
244 return;
245 if ((mon_enabled & mode) == 0 || mode == MON_OFF)
246 return;
247
248 mon_enabled &= ~mode;
249 if (mon_enabled != MON_OFF)
250 return;
251
252 /*
253 * Move everything on the MRU list to the free list quickly,
254 * without bothering to remove each from either the MRU list or
255 * the hash table.
256 */
257 ITER_DLIST_BEGIN(mon_mru_list, mon, mru, mon_entry)
258 mon_free_entry(mon);
259 ITER_DLIST_END()
260
261 /* empty the MRU list and hash table. */
262 mru_entries = 0;
263 INIT_DLIST(mon_mru_list, mru);
264 zero_mem(mon_hash, sizeof(*mon_hash) * MON_HASH_SIZE);
265 }
266
267
268 /*
269 * mon_clearinterface -- remove mru entries referring to a local address
270 * which is going away.
271 */
272 void
mon_clearinterface(endpt * lcladr)273 mon_clearinterface(
274 endpt *lcladr
275 )
276 {
277 mon_entry *mon;
278
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 */
287 mon_free_entry(mon);
288 }
289 ITER_DLIST_END()
290 }
291
292
293 /*
294 * ntp_monitor - record stats about this packet
295 *
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
306 * typical dousing.
307 */
308 u_short
ntp_monitor(struct recvbuf * rbufp,u_short flags)309 ntp_monitor(
310 struct recvbuf *rbufp,
311 u_short flags
312 )
313 {
314 l_fp interval_fp;
315 struct pkt * pkt;
316 mon_entry * mon;
317 mon_entry * oldest;
318 int oldest_age;
319 u_int hash;
320 u_short restrict_mask;
321 u_char mode;
322 u_char version;
323 int interval;
324 int head; /* headway increment */
325 int leak; /* new headway */
326 int limit; /* average threshold */
327
328 REQUIRE(rbufp != NULL);
329
330 if (mon_enabled == MON_OFF)
331 return ~(RES_LIMITED | RES_KOD) & flags;
332
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];
338
339 /*
340 * We keep track of all traffic for a given IP in one entry,
341 * otherwise cron'ed ntpdate or similar evades RES_LIMITED.
342 */
343
344 for (; mon != NULL; mon = mon->hash_next)
345 if (SOCK_EQ(&mon->rmtadr, &rbufp->recv_srcadr))
346 break;
347
348 if (mon != NULL) {
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);
356 mon->count++;
357 restrict_mask = flags;
358 mon->vn_mode = VN_MODE(version, mode);
359
360 /* Shuffle to the head of the MRU list. */
361 UNLINK_DLIST(mon, mru);
362 LINK_DLIST(mon_mru_list, mon, mru);
363
364 /*
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.
368 */
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;
374
375 DPRINTF(2, ("MRU: interval %d headway %d limit %d\n",
376 interval, leak, limit));
377
378 /*
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
390 * headway.
391 */
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;
397 else
398 restrict_mask &= ~RES_KOD;
399
400 mon->flags = restrict_mask;
401
402 return mon->flags;
403 }
404
405 /*
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.
409 *
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
422 * number of entries.
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.
429 * The default is 4.
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.
433 * The default is 4.
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".
437 */
438 if (mru_entries < mru_mindepth) {
439 if (NULL == mon_free)
440 mon_getmoremem();
441 UNLINK_HEAD_SLIST(mon, mon_free, hash_next);
442 } else {
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;
451 }
452 /* note -1 is legal for mru_maxage (disables) */
453 if (oldest != NULL && mru_maxage < oldest_age) {
454 mon_reclaim_entry(oldest);
455 mon = oldest;
456 } else if (mon_free != NULL || mru_alloc <
457 mru_maxdepth) {
458 if (NULL == mon_free)
459 mon_getmoremem();
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;
465 } else {
466 mon_reclaim_entry(oldest);
467 mon = oldest;
468 }
469 }
470
471 INSIST(mon != NULL);
472
473 /*
474 * Got one, initialize it
475 */
476 mru_entries++;
477 mru_peakentries = max(mru_peakentries, mru_entries);
478 mon->last = rbufp->recv_time;
479 mon->first = mon->last;
480 mon->count = 1;
481 mon->flags = ~(RES_LIMITED | RES_KOD) & flags;
482 mon->leak = 0;
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);
489
490 /*
491 * Drop him into front of the hash table. Also put him on top of
492 * the MRU list.
493 */
494 LINK_SLIST(mon_hash[hash], mon, hash_next);
495 LINK_DLIST(mon_mru_list, mon, mru);
496
497 return mon->flags;
498 }
499
500
501