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