contrib/ntp/ntpd/ntp_monitor.c

   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