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 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 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 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 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 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 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 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 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 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