[Git][NTPsec/ntpsec][master] Fix MRU list hash table size
Hal Murray
gitlab at mg.gitlab.com
Thu Jan 2 09:10:48 UTC 2020
Hal Murray pushed to branch master at NTPsec / ntpsec
Commits:
c40d9c8a by Hal Murray at 2020-01-01T20:22:53-08:00
Fix MRU list hash table size
An interesting tangle. The hash table was getting
allocated before processing the config file so it
was sized for the default parameters. That was 8K
hash slots so there was a lot of list walking if you
set things up for a large number of addresses.
- - - - -
10 changed files:
- include/ntp_stdlib.h
- include/ntpd.h
- libntp/socktoa.c
- ntpclients/ntpq.py
- ntpd/ntp_control.c
- ntpd/ntp_monitor.c
- ntpd/ntp_proto.c
- ntpd/ntp_restrict.c
- ntpd/ntp_util.c
- ntpd/ntpd.c
Changes:
=====================================
include/ntp_stdlib.h
=====================================
@@ -101,7 +101,7 @@ extern const char * socktoa (const sockaddr_u *);
extern const char * socktoa_r (const sockaddr_u *sock, char *buf, size_t buflen);
extern const char * sockporttoa(const sockaddr_u *);
extern const char * sockporttoa_r(const sockaddr_u *sock, char *buf, size_t buflen);
-extern unsigned short sock_hash(const sockaddr_u *) __attribute__((pure));
+extern unsigned int sock_hash(const sockaddr_u *) __attribute__((pure));
extern const char *refid_str (uint32_t, int);
extern int decodenetnum (const char *, sockaddr_u *);
=====================================
include/ntpd.h
=====================================
@@ -121,15 +121,15 @@ extern unsigned int sys_tai;
extern int freq_cnt;
/* ntp_monitor.c */
-#define MON_HASH_SIZE (1U << mon_data.mon_hash_bits)
-#define MON_HASH_MASK (MON_HASH_SIZE - 1)
-#define MON_HASH(addr) (sock_hash(addr) & MON_HASH_MASK)
-extern void init_mon (void);
-extern void mon_start (int);
-extern void mon_stop (int);
+extern void init_mon(void);
+extern void mon_setup(int);
+extern void mon_setdown(int);
+extern void mon_start(void);
+extern void mon_stop(void);
extern unsigned short ntp_monitor (struct recvbuf *, unsigned short);
extern void mon_clearinterface(endpt *interface);
extern int mon_get_oldest_age(l_fp);
+extern mon_entry *mon_get_slot(sockaddr_u *);
/* ntp_peer.c */
extern void init_peer (void);
@@ -333,6 +333,7 @@ struct monitor_data {
mon_entry ** mon_hash; /* MRU hash table */
mon_entry mon_mru_list; /* mru listhead */
uint64_t mru_entries; /* mru list count */
+ uint64_t mru_hashslots; /* hash slots in use */
/*
* Initialization state. We may be monitoring, we may not. If
* we aren't, we may not even have allocated any memory yet.
=====================================
libntp/socktoa.c
=====================================
@@ -108,7 +108,7 @@ sockporttoa_r(
/*
* sock_hash - hash a sockaddr_u structure
*/
-unsigned short
+unsigned int
sock_hash(
const sockaddr_u *addr
)
@@ -150,5 +150,5 @@ sock_hash(
hashVal = 37 * hashVal + pch[j];
}
- return (unsigned short)(hashVal & USHRT_MAX);
+ return hashVal;
}
=====================================
ntpclients/ntpq.py
=====================================
@@ -1436,21 +1436,22 @@ usage: sysstats
def do_monstats(self, _line):
"display monitor (mrulist) counters and limits"
monstats = (
- ("mru_enabled", "enabled: ", NTP_INT),
- ("mru_depth", "addresses: ", NTP_INT),
- ("mru_deepest", "peak addresses: ", NTP_INT),
- ("mru_maxdepth", "maximum addresses: ", NTP_INT),
- ("mru_mindepth", "reclaim above count: ", NTP_INT),
- ("mru_maxage", "reclaim maxage: ", NTP_INT),
- ("mru_minage", "reclaim minage: ", NTP_INT),
- ("mru_mem", "kilobytes: ", NTP_INT),
- ("mru_maxmem", "maximum kilobytes: ", NTP_INT),
- ("mru_exists", "alloc: exists: ", NTP_INT),
- ("mru_new", "alloc: new: ", NTP_INT),
- ("mru_recycleold", "alloc: recycle old: ", NTP_INT),
+ ("mru_enabled", "enabled: ", NTP_INT),
+ ("mru_hashslots", "hash slots in use: ", NTP_INT),
+ ("mru_depth", "addresses in use: ", NTP_INT),
+ ("mru_deepest", "peak addresses: ", NTP_INT),
+ ("mru_maxdepth", "maximum addresses: ", NTP_INT),
+ ("mru_mindepth", "reclaim above count: ", NTP_INT),
+ ("mru_maxage", "reclaim maxage: ", NTP_INT),
+ ("mru_minage", "reclaim minage: ", NTP_INT),
+ ("mru_mem", "kilobytes: ", NTP_INT),
+ ("mru_maxmem", "maximum kilobytes: ", NTP_INT),
+ ("mru_exists", "alloc: exists: ", NTP_INT),
+ ("mru_new", "alloc: new: ", NTP_INT),
+ ("mru_recycleold", "alloc: recycle old: ", NTP_INT),
("mru_recyclefull", "alloc: recycle full: ", NTP_INT),
- ("mru_none", "alloc: none: ", NTP_INT),
- ("mru_oldest_age", "age of oldest slot: ", NTP_INT),
+ ("mru_none", "alloc: none: ", NTP_INT),
+ ("mru_oldest_age", "age of oldest slot: ", NTP_INT),
)
self.collect_display(associd=0, variables=monstats, decodestatus=False)
=====================================
ntpd/ntp_control.c
=====================================
@@ -176,7 +176,7 @@ static const struct ctl_var sys_var[] = {
#define CS_MRU_ENABLED 24
{ CS_MRU_ENABLED, RO, "mru_enabled" },
#define CS_MRU_DEPTH 25
- { CS_MRU_DEPTH, RO, "mru_depth" },
+ { CS_MRU_DEPTH, RO, "mru_depth" }, /* mru_entries */
#define CS_MRU_DEEPEST 26
{ CS_MRU_DEEPEST, RO, "mru_deepest" },
#define CS_MRU_MINDEPTH 27
@@ -377,6 +377,8 @@ static const struct ctl_var sys_var[] = {
{ CS_nts_ke_probes_good, RO, "nts_ke_probes_good" },
#define CS_nts_ke_probes_bad 120
{ CS_nts_ke_probes_bad, RO, "nts_ke_probes_bad" },
+#define CS_MRU_HASHSLOTS 121
+ { CS_MRU_HASHSLOTS, RO, "mru_hashslots" },
#define CS_MAXCODE ((sizeof(sys_var)/sizeof(sys_var[0])) - 1)
{ 0, EOV, "" }
};
@@ -1594,10 +1596,14 @@ ctl_putsys(
ctl_puthex(sys_var[varid].text, mon_data.mon_enabled);
break;
- case CS_MRU_DEPTH:
+ case CS_MRU_DEPTH: /* mru_entries */
ctl_putuint(sys_var[varid].text, mon_data.mru_entries);
break;
+ case CS_MRU_HASHSLOTS:
+ ctl_putuint(sys_var[varid].text, mon_data.mru_hashslots);
+ break;
+
case CS_MRU_MEM: {
uint64_t u;
u = mon_data.mru_entries * sizeof(mon_entry);
@@ -3442,7 +3448,6 @@ static void read_mru_list(
int nonce_valid;
size_t i;
int priors;
- unsigned short hash;
mon_entry * mon;
mon_entry * prior_mon;
l_fp now;
@@ -3592,16 +3597,10 @@ static void read_mru_list(
*/
mon = NULL;
for (i = 0; i < (size_t)priors; i++) {
- hash = MON_HASH(&addr[i]);
- for (mon = mon_data.mon_hash[hash];
- mon != NULL;
- mon = mon->hash_next)
- if (ADDR_PORT_EQ(&mon->rmtadr, &addr[i]))
- break;
+ mon = mon_get_slot(&addr[i]);
if (mon != NULL) {
if (mon->last == last[i])
break;
- mon = NULL;
}
}
=====================================
ntpd/ntp_monitor.c
=====================================
@@ -41,8 +41,16 @@
# define MRU_MAXDEPTH_DEF (1024 * 1024 / sizeof(mon_entry))
#endif
+#define MON_HASH_SLOTS (1U << mon_data.mon_hash_bits)
+#define MON_HASH_MASK (MON_HASH_SLOTS - 1)
+#define MON_HASH(addr) (sock_hash(addr) & MON_HASH_MASK)
+
+
struct monitor_data mon_data = {
- .mru_mindepth = 600, /* preempt above this */
+ .mon_enabled = MON_ON, /* default to ON */
+ .mru_entries = 0,
+ .mru_hashslots = 0,
+ .mru_mindepth = 600, /* preempt above this */
.mru_maxage = 3600, /* recycle if older than this */
.mru_minage = 64, /* recycle if full and older than this */
.mru_maxdepth = MRU_MAXDEPTH_DEF, /* MRU count hard limit */
@@ -79,7 +87,6 @@ init_mon(void)
* Don't do much of anything here. We don't allocate memory
* until mon_start().
*/
- mon_data.mon_enabled = MON_OFF;
INIT_DLIST(mon_data.mon_mru_list, mru);
}
@@ -101,6 +108,8 @@ remove_from_hash(
UNLINK_SLIST(punlinked, mon_data.mon_hash[hash], mon, hash_next,
mon_entry);
ENSURE(punlinked == mon);
+ if (NULL == mon_data.mon_hash[hash])
+ mon_data.mru_hashslots--;
}
@@ -162,40 +171,47 @@ mon_getmoremem(void)
}
+void
+mon_setup(int mode)
+{
+ mon_data.mon_enabled |= mode;
+}
+
+void
+mon_setdown(int mode)
+{
+ mon_data.mon_enabled &= ~mode;
+}
+
/*
* mon_start - start up the monitoring software
*/
void
-mon_start(
- int mode
- )
+mon_start(void)
{
size_t octets;
unsigned int min_hash_slots;
- if (MON_OFF == mode) /* MON_OFF is 0 */
- return;
- if (mon_data.mon_enabled) {
- mon_data.mon_enabled |= (unsigned int)mode;
+ if (MON_OFF == mon_data.mon_enabled)
return;
- }
if (0 == mon_mem_increments)
mon_getmoremem();
- /*
- * Select the MRU hash table size to limit the average count
- * per bucket at capacity (mru_maxdepth) to 8, if possible
- * given our hash is limited to 16 bits.
+ /* There used to be a 16 bit limit to mon_hash_bits.
+ * and a target of 8 entries per hash slot.
+ * That was not good with large MRU lists.
+ * There was also a startup timing bug that got 13 bits.
*/
- min_hash_slots = (mon_data.mru_maxdepth / 8) + 1;
+ min_hash_slots = mon_data.mru_maxdepth; /* 1 hash slot per entry */
mon_data.mon_hash_bits = 0;
while (min_hash_slots >>= 1)
mon_data.mon_hash_bits++;
mon_data.mon_hash_bits = max(4, mon_data.mon_hash_bits);
- mon_data.mon_hash_bits = min(16, mon_data.mon_hash_bits);
- octets = sizeof(*mon_data.mon_hash) * MON_HASH_SIZE;
+ mon_data.mon_hash_bits = min(24, mon_data.mon_hash_bits);
+ octets = sizeof(*mon_data.mon_hash) * MON_HASH_SLOTS;
+ msyslog(LOG_INFO, "INIT: MRU %llu entries, %d hash bits, %llu bytes",
+ (unsigned long long)mon_data.mru_maxdepth,
+ mon_data.mon_hash_bits, (unsigned long long)octets);
mon_data.mon_hash = erealloc_zero(mon_data.mon_hash, octets, 0);
-
- mon_data.mon_enabled = (unsigned int)mode;
}
@@ -203,20 +219,12 @@ mon_start(
* mon_stop - stop the monitoring software
*/
void
-mon_stop(
- int mode
- )
+mon_stop(void)
{
mon_entry *mon;
if (MON_OFF == mon_data.mon_enabled)
return;
- if ((mon_data.mon_enabled & (unsigned int)mode) == 0 || mode == MON_OFF)
- return;
-
- mon_data.mon_enabled &= (unsigned int)~mode;
- if (mon_data.mon_enabled != MON_OFF)
- return;
/*
* Move everything on the MRU list to the free list quickly,
@@ -229,8 +237,9 @@ mon_stop(
/* empty the MRU list and hash table. */
mon_data.mru_entries = 0;
+ mon_data.mru_hashslots = 0;
INIT_DLIST(mon_data.mon_mru_list, mru);
- memset(mon_data.mon_hash, '\0', sizeof(*mon_data.mon_hash) * MON_HASH_SIZE);
+ memset(mon_data.mon_hash, '\0', sizeof(*mon_data.mon_hash) * MON_HASH_SLOTS);
}
@@ -258,6 +267,17 @@ mon_clearinterface(
ITER_DLIST_END()
}
+mon_entry *mon_get_slot(sockaddr_u *addr)
+{
+ mon_entry *mon;
+
+ mon = mon_data.mon_hash[MON_HASH(addr)];
+ for (; mon != NULL; mon = mon->hash_next)
+ if (SOCK_EQ(&mon->rmtadr, addr))
+ break;
+ return mon;
+}
+
int mon_get_oldest_age(l_fp now)
{
mon_entry * oldest;
@@ -269,6 +289,7 @@ int mon_get_oldest_age(l_fp now)
now += 0x80000000;
return lfpsint(now);
}
+
/*
* ntp_monitor - record stats about this packet
*
@@ -460,6 +481,8 @@ ntp_monitor(
* Drop him into front of the hash table. Also put him on top of
* the MRU list.
*/
+ if (NULL == mon_data.mon_hash[hash])
+ mon_data.mru_hashslots++;
LINK_SLIST(mon_data.mon_hash[hash], mon, hash_next);
LINK_DLIST(mon_data.mon_mru_list, mon, mru);
=====================================
ntpd/ntp_proto.c
=====================================
@@ -2861,9 +2861,9 @@ proto_config(
case PROTO_MONITOR: /* monitoring (monitor) */
if (value) {
- mon_start(MON_ON);
+ mon_setup(MON_ON);
} else {
- mon_stop(MON_ON);
+ mon_setdown(MON_ON);
if (mon_data.mon_enabled)
msyslog(LOG_WARNING,
"CONFIG: 'monitor' cannot be disabled while 'limited' is enabled");
=====================================
ntpd/ntp_restrict.c
=====================================
@@ -245,7 +245,7 @@ static void
inc_res_limited(void)
{
if (!res_limited_refcnt)
- mon_start(MON_RES);
+ mon_setup(MON_RES);
res_limited_refcnt++;
}
@@ -255,7 +255,7 @@ dec_res_limited(void)
{
res_limited_refcnt--;
if (!res_limited_refcnt)
- mon_stop(MON_RES);
+ mon_setdown(MON_RES);
}
=====================================
ntpd/ntp_util.c
=====================================
@@ -61,6 +61,7 @@ static FILEGEN loopstats;
static FILEGEN peerstats;
static FILEGEN protostats;
static FILEGEN rawstats;
+static FILEGEN refstats;
static FILEGEN sysstats;
static FILEGEN usestats;
@@ -108,6 +109,7 @@ uninit_util(void)
filegen_unregister("clockstats");
filegen_unregister("loopstats");
filegen_unregister("rawstats");
+ filegen_unregister("refstats");
filegen_unregister("sysstats");
filegen_unregister("peerstats");
filegen_unregister("protostats");
@@ -125,6 +127,7 @@ init_util(void)
filegen_register(statsdir, "clockstats", &clockstats);
filegen_register(statsdir, "loopstats", &loopstats);
filegen_register(statsdir, "rawstats", &rawstats);
+ filegen_register(statsdir, "refstats", &refstats);
filegen_register(statsdir, "sysstats", &sysstats);
filegen_register(statsdir, "peerstats", &peerstats);
filegen_register(statsdir, "protostats", &protostats);
@@ -558,6 +561,50 @@ record_raw_stats(
}
}
+/*
+ * record_ref_stats - write refclock timestamps to file
+ *
+ * file format
+ * day (MJD)
+ * time (s past midnight)
+ * peer ip address
+ * i, j, n from refclock_sample
+ * t1 t2 t3 t4 t5, timestamps
+ * jitter, std_dev, std_dev_all
+ */
+
+void record_ref_stats(
+ const struct peer *peer,
+ int n, /* Number of samples */
+ int i, /* Index of first sample used */
+ int j, /* Index of last sample used */
+ double t1, /* Value of first sample */
+ double t2, /* Value of first sample used */
+ double t3, /* answer/median */
+ double t4, /* Value of last sample used */
+ double t5, /* Value of last sample */
+ double jitter,
+ double std_dev, /* std deviation of trimmed subset */
+ double std_dev_all /* std deviation of everything */
+ )
+{
+ struct timespec now;
+
+ if (!stats_control)
+ return;
+
+ clock_gettime(CLOCK_REALTIME, &now);
+ filegen_setup(&refstats, now.tv_sec);
+ if (refstats.fp != NULL) {
+ fprintf(refstats.fp,
+ "%s %s %d %d %d %.9f %.9f %.9f %.9f %.9f %.9f %.9f %.9f\n",
+ timespec_to_MJDtime(&now), peerlabel(peer),
+ n, i, j,
+ t1, t2, t3, t4, t5, jitter, std_dev, std_dev_all);
+ fflush(refstats.fp);
+ }
+}
+
/*
* record_sys_stats - write system statistics to file
@@ -773,15 +820,13 @@ getauthkeys(
*/
void
ntpd_time_stepped(void) {
- unsigned int saved_mon_enabled;
/*
* flush the monitor MRU list which contains l_fp timestamps
* which should not be compared across the step.
*/
if (MON_OFF != mon_data.mon_enabled) {
- saved_mon_enabled = mon_data.mon_enabled;
- mon_stop(MON_OFF);
- mon_start((int)saved_mon_enabled);
+ mon_stop();
+ mon_start();
}
}
=====================================
ntpd/ntpd.c
=====================================
@@ -641,8 +641,6 @@ main(
init_io();
init_loopfilter();
init_readconfig(); /* see readconfig() */
- mon_start(MON_ON); /* monitor on by default now */
- /* turn off in config if unwanted */
/*
* Some option settings have to be deferred until after
@@ -863,6 +861,7 @@ main(
msyslog(LOG_NOTICE, "INIT: This ntpd will fail on 2038-01-19T03:14:07Z.");
}
+ mon_start();
loop_config(LOOP_DRIFTINIT, 0);
report_event(EVNT_SYSRESTART, NULL, NULL);
View it on GitLab: https://gitlab.com/NTPsec/ntpsec/commit/c40d9c8ae0c501a7648499ffd642e2a52a90c30c
--
View it on GitLab: https://gitlab.com/NTPsec/ntpsec/commit/c40d9c8ae0c501a7648499ffd642e2a52a90c30c
You're receiving this email because of your account on gitlab.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ntpsec.org/pipermail/vc/attachments/20200102/50433d69/attachment-0001.htm>
More information about the vc
mailing list