[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