external/bsd/ntp/dist/ntpd/ntp_monitor.c

   1 /*      $NetBSD$        */
   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 }