xref: /freebsd/sys/netinet/tcp_hpts.c (revision 4b9d6057)
1 /*-
2  * Copyright (c) 2016-2018 Netflix, Inc.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
23  * SUCH DAMAGE.
24  *
25  */
26 #include <sys/cdefs.h>
27 #include "opt_inet.h"
28 #include "opt_inet6.h"
29 #include "opt_rss.h"
30 
31 /**
32  * Some notes about usage.
33  *
34  * The tcp_hpts system is designed to provide a high precision timer
35  * system for tcp. Its main purpose is to provide a mechanism for
36  * pacing packets out onto the wire. It can be used in two ways
37  * by a given TCP stack (and those two methods can be used simultaneously).
38  *
39  * First, and probably the main thing its used by Rack and BBR, it can
40  * be used to call tcp_output() of a transport stack at some time in the future.
41  * The normal way this is done is that tcp_output() of the stack schedules
42  * itself to be called again by calling tcp_hpts_insert(tcpcb, slot). The
43  * slot is the time from now that the stack wants to be called but it
44  * must be converted to tcp_hpts's notion of slot. This is done with
45  * one of the macros HPTS_MS_TO_SLOTS or HPTS_USEC_TO_SLOTS. So a typical
46  * call from the tcp_output() routine might look like:
47  *
48  * tcp_hpts_insert(tp, HPTS_USEC_TO_SLOTS(550));
49  *
50  * The above would schedule tcp_ouput() to be called in 550 useconds.
51  * Note that if using this mechanism the stack will want to add near
52  * its top a check to prevent unwanted calls (from user land or the
53  * arrival of incoming ack's). So it would add something like:
54  *
55  * if (tcp_in_hpts(inp))
56  *    return;
57  *
58  * to prevent output processing until the time alotted has gone by.
59  * Of course this is a bare bones example and the stack will probably
60  * have more consideration then just the above.
61  *
62  * In order to run input queued segments from the HPTS context the
63  * tcp stack must define an input function for
64  * tfb_do_queued_segments(). This function understands
65  * how to dequeue a array of packets that were input and
66  * knows how to call the correct processing routine.
67  *
68  * Locking in this is important as well so most likely the
69  * stack will need to define the tfb_do_segment_nounlock()
70  * splitting tfb_do_segment() into two parts. The main processing
71  * part that does not unlock the INP and returns a value of 1 or 0.
72  * It returns 0 if all is well and the lock was not released. It
73  * returns 1 if we had to destroy the TCB (a reset received etc).
74  * The remains of tfb_do_segment() then become just a simple call
75  * to the tfb_do_segment_nounlock() function and check the return
76  * code and possibly unlock.
77  *
78  * The stack must also set the flag on the INP that it supports this
79  * feature i.e. INP_SUPPORTS_MBUFQ. The LRO code recoginizes
80  * this flag as well and will queue packets when it is set.
81  * There are other flags as well INP_MBUF_QUEUE_READY and
82  * INP_DONT_SACK_QUEUE. The first flag tells the LRO code
83  * that we are in the pacer for output so there is no
84  * need to wake up the hpts system to get immediate
85  * input. The second tells the LRO code that its okay
86  * if a SACK arrives you can still defer input and let
87  * the current hpts timer run (this is usually set when
88  * a rack timer is up so we know SACK's are happening
89  * on the connection already and don't want to wakeup yet).
90  *
91  * There is a common functions within the rack_bbr_common code
92  * version i.e. ctf_do_queued_segments(). This function
93  * knows how to take the input queue of packets from tp->t_inqueue
94  * and process them digging out all the arguments, calling any bpf tap and
95  * calling into tfb_do_segment_nounlock(). The common
96  * function (ctf_do_queued_segments())  requires that
97  * you have defined the tfb_do_segment_nounlock() as
98  * described above.
99  */
100 
101 #include <sys/param.h>
102 #include <sys/bus.h>
103 #include <sys/interrupt.h>
104 #include <sys/module.h>
105 #include <sys/kernel.h>
106 #include <sys/hhook.h>
107 #include <sys/malloc.h>
108 #include <sys/mbuf.h>
109 #include <sys/proc.h>		/* for proc0 declaration */
110 #include <sys/socket.h>
111 #include <sys/socketvar.h>
112 #include <sys/sysctl.h>
113 #include <sys/systm.h>
114 #include <sys/refcount.h>
115 #include <sys/sched.h>
116 #include <sys/queue.h>
117 #include <sys/smp.h>
118 #include <sys/counter.h>
119 #include <sys/time.h>
120 #include <sys/kthread.h>
121 #include <sys/kern_prefetch.h>
122 
123 #include <vm/uma.h>
124 #include <vm/vm.h>
125 
126 #include <net/route.h>
127 #include <net/vnet.h>
128 
129 #ifdef RSS
130 #include <net/netisr.h>
131 #include <net/rss_config.h>
132 #endif
133 
134 #define TCPSTATES		/* for logging */
135 
136 #include <netinet/in.h>
137 #include <netinet/in_kdtrace.h>
138 #include <netinet/in_pcb.h>
139 #include <netinet/ip.h>
140 #include <netinet/ip_icmp.h>	/* required for icmp_var.h */
141 #include <netinet/icmp_var.h>	/* for ICMP_BANDLIM */
142 #include <netinet/ip_var.h>
143 #include <netinet/ip6.h>
144 #include <netinet6/in6_pcb.h>
145 #include <netinet6/ip6_var.h>
146 #include <netinet/tcp.h>
147 #include <netinet/tcp_fsm.h>
148 #include <netinet/tcp_seq.h>
149 #include <netinet/tcp_timer.h>
150 #include <netinet/tcp_var.h>
151 #include <netinet/tcpip.h>
152 #include <netinet/cc/cc.h>
153 #include <netinet/tcp_hpts.h>
154 #include <netinet/tcp_log_buf.h>
155 
156 #ifdef tcp_offload
157 #include <netinet/tcp_offload.h>
158 #endif
159 
160 /*
161  * The hpts uses a 102400 wheel. The wheel
162  * defines the time in 10 usec increments (102400 x 10).
163  * This gives a range of 10usec - 1024ms to place
164  * an entry within. If the user requests more than
165  * 1.024 second, a remaineder is attached and the hpts
166  * when seeing the remainder will re-insert the
167  * inpcb forward in time from where it is until
168  * the remainder is zero.
169  */
170 
171 #define NUM_OF_HPTSI_SLOTS 102400
172 
173 /* Each hpts has its own p_mtx which is used for locking */
174 #define	HPTS_MTX_ASSERT(hpts)	mtx_assert(&(hpts)->p_mtx, MA_OWNED)
175 #define	HPTS_LOCK(hpts)		mtx_lock(&(hpts)->p_mtx)
176 #define	HPTS_UNLOCK(hpts)	mtx_unlock(&(hpts)->p_mtx)
177 struct tcp_hpts_entry {
178 	/* Cache line 0x00 */
179 	struct mtx p_mtx;	/* Mutex for hpts */
180 	struct timeval p_mysleep;	/* Our min sleep time */
181 	uint64_t syscall_cnt;
182 	uint64_t sleeping;	/* What the actual sleep was (if sleeping) */
183 	uint16_t p_hpts_active; /* Flag that says hpts is awake  */
184 	uint8_t p_wheel_complete; /* have we completed the wheel arc walk? */
185 	uint32_t p_curtick;	/* Tick in 10 us the hpts is going to */
186 	uint32_t p_runningslot; /* Current tick we are at if we are running */
187 	uint32_t p_prev_slot;	/* Previous slot we were on */
188 	uint32_t p_cur_slot;	/* Current slot in wheel hpts is draining */
189 	uint32_t p_nxt_slot;	/* The next slot outside the current range of
190 				 * slots that the hpts is running on. */
191 	int32_t p_on_queue_cnt;	/* Count on queue in this hpts */
192 	uint32_t p_lasttick;	/* Last tick before the current one */
193 	uint8_t p_direct_wake :1, /* boolean */
194 		p_on_min_sleep:1, /* boolean */
195 		p_hpts_wake_scheduled:1, /* boolean */
196 		p_avail:5;
197 	uint8_t p_fill[3];	  /* Fill to 32 bits */
198 	/* Cache line 0x40 */
199 	struct hptsh {
200 		TAILQ_HEAD(, tcpcb)	head;
201 		uint32_t		count;
202 		uint32_t		gencnt;
203 	} *p_hptss;			/* Hptsi wheel */
204 	uint32_t p_hpts_sleep_time;	/* Current sleep interval having a max
205 					 * of 255ms */
206 	uint32_t overidden_sleep;	/* what was overrided by min-sleep for logging */
207 	uint32_t saved_lasttick;	/* for logging */
208 	uint32_t saved_curtick;		/* for logging */
209 	uint32_t saved_curslot;		/* for logging */
210 	uint32_t saved_prev_slot;       /* for logging */
211 	uint32_t p_delayed_by;	/* How much were we delayed by */
212 	/* Cache line 0x80 */
213 	struct sysctl_ctx_list hpts_ctx;
214 	struct sysctl_oid *hpts_root;
215 	struct intr_event *ie;
216 	void *ie_cookie;
217 	uint16_t p_num;		/* The hpts number one per cpu */
218 	uint16_t p_cpu;		/* The hpts CPU */
219 	/* There is extra space in here */
220 	/* Cache line 0x100 */
221 	struct callout co __aligned(CACHE_LINE_SIZE);
222 }               __aligned(CACHE_LINE_SIZE);
223 
224 static struct tcp_hptsi {
225 	struct cpu_group **grps;
226 	struct tcp_hpts_entry **rp_ent;	/* Array of hptss */
227 	uint32_t *cts_last_ran;
228 	uint32_t grp_cnt;
229 	uint32_t rp_num_hptss;	/* Number of hpts threads */
230 } tcp_pace;
231 
232 MALLOC_DEFINE(M_TCPHPTS, "tcp_hpts", "TCP hpts");
233 #ifdef RSS
234 static int tcp_bind_threads = 1;
235 #else
236 static int tcp_bind_threads = 2;
237 #endif
238 static int tcp_use_irq_cpu = 0;
239 static uint32_t *cts_last_ran;
240 static int hpts_does_tp_logging = 0;
241 
242 static int32_t tcp_hptsi(struct tcp_hpts_entry *hpts, int from_callout);
243 static void tcp_hpts_thread(void *ctx);
244 static void tcp_init_hptsi(void *st);
245 
246 int32_t tcp_min_hptsi_time = DEFAULT_MIN_SLEEP;
247 static int conn_cnt_thresh = DEFAULT_CONNECTION_THESHOLD;
248 static int32_t dynamic_min_sleep = DYNAMIC_MIN_SLEEP;
249 static int32_t dynamic_max_sleep = DYNAMIC_MAX_SLEEP;
250 
251 
252 SYSCTL_NODE(_net_inet_tcp, OID_AUTO, hpts, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
253     "TCP Hpts controls");
254 SYSCTL_NODE(_net_inet_tcp_hpts, OID_AUTO, stats, CTLFLAG_RD | CTLFLAG_MPSAFE, 0,
255     "TCP Hpts statistics");
256 
257 #define	timersub(tvp, uvp, vvp)						\
258 	do {								\
259 		(vvp)->tv_sec = (tvp)->tv_sec - (uvp)->tv_sec;		\
260 		(vvp)->tv_usec = (tvp)->tv_usec - (uvp)->tv_usec;	\
261 		if ((vvp)->tv_usec < 0) {				\
262 			(vvp)->tv_sec--;				\
263 			(vvp)->tv_usec += 1000000;			\
264 		}							\
265 	} while (0)
266 
267 static int32_t tcp_hpts_precision = 120;
268 
269 static struct hpts_domain_info {
270 	int count;
271 	int cpu[MAXCPU];
272 } hpts_domains[MAXMEMDOM];
273 
274 counter_u64_t hpts_hopelessly_behind;
275 
276 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, hopeless, CTLFLAG_RD,
277     &hpts_hopelessly_behind,
278     "Number of times hpts could not catch up and was behind hopelessly");
279 
280 counter_u64_t hpts_loops;
281 
282 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, loops, CTLFLAG_RD,
283     &hpts_loops, "Number of times hpts had to loop to catch up");
284 
285 counter_u64_t back_tosleep;
286 
287 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, no_tcbsfound, CTLFLAG_RD,
288     &back_tosleep, "Number of times hpts found no tcbs");
289 
290 counter_u64_t combined_wheel_wrap;
291 
292 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, comb_wheel_wrap, CTLFLAG_RD,
293     &combined_wheel_wrap, "Number of times the wheel lagged enough to have an insert see wrap");
294 
295 counter_u64_t wheel_wrap;
296 
297 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, wheel_wrap, CTLFLAG_RD,
298     &wheel_wrap, "Number of times the wheel lagged enough to have an insert see wrap");
299 
300 counter_u64_t hpts_direct_call;
301 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, direct_call, CTLFLAG_RD,
302     &hpts_direct_call, "Number of times hpts was called by syscall/trap or other entry");
303 
304 counter_u64_t hpts_wake_timeout;
305 
306 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, timeout_wakeup, CTLFLAG_RD,
307     &hpts_wake_timeout, "Number of times hpts threads woke up via the callout expiring");
308 
309 counter_u64_t hpts_direct_awakening;
310 
311 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, direct_awakening, CTLFLAG_RD,
312     &hpts_direct_awakening, "Number of times hpts threads woke up via the callout expiring");
313 
314 counter_u64_t hpts_back_tosleep;
315 
316 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, back_tosleep, CTLFLAG_RD,
317     &hpts_back_tosleep, "Number of times hpts threads woke up via the callout expiring and went back to sleep no work");
318 
319 counter_u64_t cpu_uses_flowid;
320 counter_u64_t cpu_uses_random;
321 
322 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, cpusel_flowid, CTLFLAG_RD,
323     &cpu_uses_flowid, "Number of times when setting cpuid we used the flowid field");
324 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts_stats, OID_AUTO, cpusel_random, CTLFLAG_RD,
325     &cpu_uses_random, "Number of times when setting cpuid we used the a random value");
326 
327 TUNABLE_INT("net.inet.tcp.bind_hptss", &tcp_bind_threads);
328 TUNABLE_INT("net.inet.tcp.use_irq", &tcp_use_irq_cpu);
329 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, bind_hptss, CTLFLAG_RD,
330     &tcp_bind_threads, 2,
331     "Thread Binding tunable");
332 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, use_irq, CTLFLAG_RD,
333     &tcp_use_irq_cpu, 0,
334     "Use of irq CPU  tunable");
335 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, precision, CTLFLAG_RW,
336     &tcp_hpts_precision, 120,
337     "Value for PRE() precision of callout");
338 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, cnt_thresh, CTLFLAG_RW,
339     &conn_cnt_thresh, 0,
340     "How many connections (below) make us use the callout based mechanism");
341 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, logging, CTLFLAG_RW,
342     &hpts_does_tp_logging, 0,
343     "Do we add to any tp that has logging on pacer logs");
344 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, dyn_minsleep, CTLFLAG_RW,
345     &dynamic_min_sleep, 250,
346     "What is the dynamic minsleep value?");
347 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, dyn_maxsleep, CTLFLAG_RW,
348     &dynamic_max_sleep, 5000,
349     "What is the dynamic maxsleep value?");
350 
351 static int32_t max_pacer_loops = 10;
352 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, loopmax, CTLFLAG_RW,
353     &max_pacer_loops, 10,
354     "What is the maximum number of times the pacer will loop trying to catch up");
355 
356 #define HPTS_MAX_SLEEP_ALLOWED (NUM_OF_HPTSI_SLOTS/2)
357 
358 static uint32_t hpts_sleep_max = HPTS_MAX_SLEEP_ALLOWED;
359 
360 static int
361 sysctl_net_inet_tcp_hpts_max_sleep(SYSCTL_HANDLER_ARGS)
362 {
363 	int error;
364 	uint32_t new;
365 
366 	new = hpts_sleep_max;
367 	error = sysctl_handle_int(oidp, &new, 0, req);
368 	if (error == 0 && req->newptr) {
369 		if ((new < (dynamic_min_sleep/HPTS_TICKS_PER_SLOT)) ||
370 		     (new > HPTS_MAX_SLEEP_ALLOWED))
371 			error = EINVAL;
372 		else
373 			hpts_sleep_max = new;
374 	}
375 	return (error);
376 }
377 
378 static int
379 sysctl_net_inet_tcp_hpts_min_sleep(SYSCTL_HANDLER_ARGS)
380 {
381 	int error;
382 	uint32_t new;
383 
384 	new = tcp_min_hptsi_time;
385 	error = sysctl_handle_int(oidp, &new, 0, req);
386 	if (error == 0 && req->newptr) {
387 		if (new < LOWEST_SLEEP_ALLOWED)
388 			error = EINVAL;
389 		else
390 			tcp_min_hptsi_time = new;
391 	}
392 	return (error);
393 }
394 
395 SYSCTL_PROC(_net_inet_tcp_hpts, OID_AUTO, maxsleep,
396     CTLTYPE_UINT | CTLFLAG_RW,
397     &hpts_sleep_max, 0,
398     &sysctl_net_inet_tcp_hpts_max_sleep, "IU",
399     "Maximum time hpts will sleep in slots");
400 
401 SYSCTL_PROC(_net_inet_tcp_hpts, OID_AUTO, minsleep,
402     CTLTYPE_UINT | CTLFLAG_RW,
403     &tcp_min_hptsi_time, 0,
404     &sysctl_net_inet_tcp_hpts_min_sleep, "IU",
405     "The minimum time the hpts must sleep before processing more slots");
406 
407 static int ticks_indicate_more_sleep = TICKS_INDICATE_MORE_SLEEP;
408 static int ticks_indicate_less_sleep = TICKS_INDICATE_LESS_SLEEP;
409 static int tcp_hpts_no_wake_over_thresh = 1;
410 
411 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, more_sleep, CTLFLAG_RW,
412     &ticks_indicate_more_sleep, 0,
413     "If we only process this many or less on a timeout, we need longer sleep on the next callout");
414 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, less_sleep, CTLFLAG_RW,
415     &ticks_indicate_less_sleep, 0,
416     "If we process this many or more on a timeout, we need less sleep on the next callout");
417 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, nowake_over_thresh, CTLFLAG_RW,
418     &tcp_hpts_no_wake_over_thresh, 0,
419     "When we are over the threshold on the pacer do we prohibit wakeups?");
420 
421 static uint16_t
422 hpts_random_cpu(void)
423 {
424 	uint16_t cpuid;
425 	uint32_t ran;
426 
427 	ran = arc4random();
428 	cpuid = (((ran & 0xffff) % mp_ncpus) % tcp_pace.rp_num_hptss);
429 	return (cpuid);
430 }
431 
432 static void
433 tcp_hpts_log(struct tcp_hpts_entry *hpts, struct tcpcb *tp, struct timeval *tv,
434 	     int slots_to_run, int idx, int from_callout)
435 {
436 	union tcp_log_stackspecific log;
437 	/*
438 	 * Unused logs are
439 	 * 64 bit - delRate, rttProp, bw_inuse
440 	 * 16 bit - cwnd_gain
441 	 *  8 bit - bbr_state, bbr_substate, inhpts;
442 	 */
443 	memset(&log.u_bbr, 0, sizeof(log.u_bbr));
444 	log.u_bbr.flex1 = hpts->p_nxt_slot;
445 	log.u_bbr.flex2 = hpts->p_cur_slot;
446 	log.u_bbr.flex3 = hpts->p_prev_slot;
447 	log.u_bbr.flex4 = idx;
448 	log.u_bbr.flex5 = hpts->p_curtick;
449 	log.u_bbr.flex6 = hpts->p_on_queue_cnt;
450 	log.u_bbr.flex7 = hpts->p_cpu;
451 	log.u_bbr.flex8 = (uint8_t)from_callout;
452 	log.u_bbr.inflight = slots_to_run;
453 	log.u_bbr.applimited = hpts->overidden_sleep;
454 	log.u_bbr.delivered = hpts->saved_curtick;
455 	log.u_bbr.timeStamp = tcp_tv_to_usectick(tv);
456 	log.u_bbr.epoch = hpts->saved_curslot;
457 	log.u_bbr.lt_epoch = hpts->saved_prev_slot;
458 	log.u_bbr.pkts_out = hpts->p_delayed_by;
459 	log.u_bbr.lost = hpts->p_hpts_sleep_time;
460 	log.u_bbr.pacing_gain = hpts->p_cpu;
461 	log.u_bbr.pkt_epoch = hpts->p_runningslot;
462 	log.u_bbr.use_lt_bw = 1;
463 	TCP_LOG_EVENTP(tp, NULL,
464 		       &tptosocket(tp)->so_rcv,
465 		       &tptosocket(tp)->so_snd,
466 		       BBR_LOG_HPTSDIAG, 0,
467 		       0, &log, false, tv);
468 }
469 
470 static void
471 tcp_wakehpts(struct tcp_hpts_entry *hpts)
472 {
473 	HPTS_MTX_ASSERT(hpts);
474 
475 	if (tcp_hpts_no_wake_over_thresh && (hpts->p_on_queue_cnt >= conn_cnt_thresh)) {
476 		hpts->p_direct_wake = 0;
477 		return;
478 	}
479 	if (hpts->p_hpts_wake_scheduled == 0) {
480 		hpts->p_hpts_wake_scheduled = 1;
481 		swi_sched(hpts->ie_cookie, 0);
482 	}
483 }
484 
485 static void
486 hpts_timeout_swi(void *arg)
487 {
488 	struct tcp_hpts_entry *hpts;
489 
490 	hpts = (struct tcp_hpts_entry *)arg;
491 	swi_sched(hpts->ie_cookie, 0);
492 }
493 
494 static void
495 tcp_hpts_insert_internal(struct tcpcb *tp, struct tcp_hpts_entry *hpts)
496 {
497 	struct inpcb *inp = tptoinpcb(tp);
498 	struct hptsh *hptsh;
499 
500 	INP_WLOCK_ASSERT(inp);
501 	HPTS_MTX_ASSERT(hpts);
502 	MPASS(hpts->p_cpu == tp->t_hpts_cpu);
503 	MPASS(!(inp->inp_flags & INP_DROPPED));
504 
505 	hptsh = &hpts->p_hptss[tp->t_hpts_slot];
506 
507 	if (tp->t_in_hpts == IHPTS_NONE) {
508 		tp->t_in_hpts = IHPTS_ONQUEUE;
509 		in_pcbref(inp);
510 	} else if (tp->t_in_hpts == IHPTS_MOVING) {
511 		tp->t_in_hpts = IHPTS_ONQUEUE;
512 	} else
513 		MPASS(tp->t_in_hpts == IHPTS_ONQUEUE);
514 	tp->t_hpts_gencnt = hptsh->gencnt;
515 
516 	TAILQ_INSERT_TAIL(&hptsh->head, tp, t_hpts);
517 	hptsh->count++;
518 	hpts->p_on_queue_cnt++;
519 }
520 
521 static struct tcp_hpts_entry *
522 tcp_hpts_lock(struct tcpcb *tp)
523 {
524 	struct tcp_hpts_entry *hpts;
525 
526 	INP_LOCK_ASSERT(tptoinpcb(tp));
527 
528 	hpts = tcp_pace.rp_ent[tp->t_hpts_cpu];
529 	HPTS_LOCK(hpts);
530 
531 	return (hpts);
532 }
533 
534 static void
535 tcp_hpts_release(struct tcpcb *tp)
536 {
537 	bool released __diagused;
538 
539 	tp->t_in_hpts = IHPTS_NONE;
540 	released = in_pcbrele_wlocked(tptoinpcb(tp));
541 	MPASS(released == false);
542 }
543 
544 /*
545  * Initialize tcpcb to get ready for use with HPTS.  We will know which CPU
546  * is preferred on the first incoming packet.  Before that avoid crowding
547  * a single CPU with newborn connections and use a random one.
548  * This initialization is normally called on a newborn tcpcb, but potentially
549  * can be called once again if stack is switched.  In that case we inherit CPU
550  * that the previous stack has set, be it random or not.  In extreme cases,
551  * e.g. syzkaller fuzzing, a tcpcb can already be in HPTS in IHPTS_MOVING state
552  * and has never received a first packet.
553  */
554 void
555 tcp_hpts_init(struct tcpcb *tp)
556 {
557 
558 	if (__predict_true(tp->t_hpts_cpu == HPTS_CPU_NONE)) {
559 		tp->t_hpts_cpu = hpts_random_cpu();
560 		MPASS(!(tp->t_flags2 & TF2_HPTS_CPU_SET));
561 	}
562 }
563 
564 /*
565  * Called normally with the INP_LOCKED but it
566  * does not matter, the hpts lock is the key
567  * but the lock order allows us to hold the
568  * INP lock and then get the hpts lock.
569  */
570 void
571 tcp_hpts_remove(struct tcpcb *tp)
572 {
573 	struct tcp_hpts_entry *hpts;
574 	struct hptsh *hptsh;
575 
576 	INP_WLOCK_ASSERT(tptoinpcb(tp));
577 
578 	hpts = tcp_hpts_lock(tp);
579 	if (tp->t_in_hpts == IHPTS_ONQUEUE) {
580 		hptsh = &hpts->p_hptss[tp->t_hpts_slot];
581 		tp->t_hpts_request = 0;
582 		if (__predict_true(tp->t_hpts_gencnt == hptsh->gencnt)) {
583 			TAILQ_REMOVE(&hptsh->head, tp, t_hpts);
584 			MPASS(hptsh->count > 0);
585 			hptsh->count--;
586 			MPASS(hpts->p_on_queue_cnt > 0);
587 			hpts->p_on_queue_cnt--;
588 			tcp_hpts_release(tp);
589 		} else {
590 			/*
591 			 * tcp_hptsi() now owns the TAILQ head of this inp.
592 			 * Can't TAILQ_REMOVE, just mark it.
593 			 */
594 #ifdef INVARIANTS
595 			struct tcpcb *tmp;
596 
597 			TAILQ_FOREACH(tmp, &hptsh->head, t_hpts)
598 				MPASS(tmp != tp);
599 #endif
600 			tp->t_in_hpts = IHPTS_MOVING;
601 			tp->t_hpts_slot = -1;
602 		}
603 	} else if (tp->t_in_hpts == IHPTS_MOVING) {
604 		/*
605 		 * Handle a special race condition:
606 		 * tcp_hptsi() moves inpcb to detached tailq
607 		 * tcp_hpts_remove() marks as IHPTS_MOVING, slot = -1
608 		 * tcp_hpts_insert() sets slot to a meaningful value
609 		 * tcp_hpts_remove() again (we are here!), then in_pcbdrop()
610 		 * tcp_hptsi() finds pcb with meaningful slot and INP_DROPPED
611 		 */
612 		tp->t_hpts_slot = -1;
613 	}
614 	HPTS_UNLOCK(hpts);
615 }
616 
617 static inline int
618 hpts_slot(uint32_t wheel_slot, uint32_t plus)
619 {
620 	/*
621 	 * Given a slot on the wheel, what slot
622 	 * is that plus ticks out?
623 	 */
624 	KASSERT(wheel_slot < NUM_OF_HPTSI_SLOTS, ("Invalid tick %u not on wheel", wheel_slot));
625 	return ((wheel_slot + plus) % NUM_OF_HPTSI_SLOTS);
626 }
627 
628 static inline int
629 tick_to_wheel(uint32_t cts_in_wticks)
630 {
631 	/*
632 	 * Given a timestamp in ticks (so by
633 	 * default to get it to a real time one
634 	 * would multiply by 10.. i.e the number
635 	 * of ticks in a slot) map it to our limited
636 	 * space wheel.
637 	 */
638 	return (cts_in_wticks % NUM_OF_HPTSI_SLOTS);
639 }
640 
641 static inline int
642 hpts_slots_diff(int prev_slot, int slot_now)
643 {
644 	/*
645 	 * Given two slots that are someplace
646 	 * on our wheel. How far are they apart?
647 	 */
648 	if (slot_now > prev_slot)
649 		return (slot_now - prev_slot);
650 	else if (slot_now == prev_slot)
651 		/*
652 		 * Special case, same means we can go all of our
653 		 * wheel less one slot.
654 		 */
655 		return (NUM_OF_HPTSI_SLOTS - 1);
656 	else
657 		return ((NUM_OF_HPTSI_SLOTS - prev_slot) + slot_now);
658 }
659 
660 /*
661  * Given a slot on the wheel that is the current time
662  * mapped to the wheel (wheel_slot), what is the maximum
663  * distance forward that can be obtained without
664  * wrapping past either prev_slot or running_slot
665  * depending on the htps state? Also if passed
666  * a uint32_t *, fill it with the slot location.
667  *
668  * Note if you do not give this function the current
669  * time (that you think it is) mapped to the wheel slot
670  * then the results will not be what you expect and
671  * could lead to invalid inserts.
672  */
673 static inline int32_t
674 max_slots_available(struct tcp_hpts_entry *hpts, uint32_t wheel_slot, uint32_t *target_slot)
675 {
676 	uint32_t dis_to_travel, end_slot, pacer_to_now, avail_on_wheel;
677 
678 	if ((hpts->p_hpts_active == 1) &&
679 	    (hpts->p_wheel_complete == 0)) {
680 		end_slot = hpts->p_runningslot;
681 		/* Back up one tick */
682 		if (end_slot == 0)
683 			end_slot = NUM_OF_HPTSI_SLOTS - 1;
684 		else
685 			end_slot--;
686 		if (target_slot)
687 			*target_slot = end_slot;
688 	} else {
689 		/*
690 		 * For the case where we are
691 		 * not active, or we have
692 		 * completed the pass over
693 		 * the wheel, we can use the
694 		 * prev tick and subtract one from it. This puts us
695 		 * as far out as possible on the wheel.
696 		 */
697 		end_slot = hpts->p_prev_slot;
698 		if (end_slot == 0)
699 			end_slot = NUM_OF_HPTSI_SLOTS - 1;
700 		else
701 			end_slot--;
702 		if (target_slot)
703 			*target_slot = end_slot;
704 		/*
705 		 * Now we have close to the full wheel left minus the
706 		 * time it has been since the pacer went to sleep. Note
707 		 * that wheel_tick, passed in, should be the current time
708 		 * from the perspective of the caller, mapped to the wheel.
709 		 */
710 		if (hpts->p_prev_slot != wheel_slot)
711 			dis_to_travel = hpts_slots_diff(hpts->p_prev_slot, wheel_slot);
712 		else
713 			dis_to_travel = 1;
714 		/*
715 		 * dis_to_travel in this case is the space from when the
716 		 * pacer stopped (p_prev_slot) and where our wheel_slot
717 		 * is now. To know how many slots we can put it in we
718 		 * subtract from the wheel size. We would not want
719 		 * to place something after p_prev_slot or it will
720 		 * get ran too soon.
721 		 */
722 		return (NUM_OF_HPTSI_SLOTS - dis_to_travel);
723 	}
724 	/*
725 	 * So how many slots are open between p_runningslot -> p_cur_slot
726 	 * that is what is currently un-available for insertion. Special
727 	 * case when we are at the last slot, this gets 1, so that
728 	 * the answer to how many slots are available is all but 1.
729 	 */
730 	if (hpts->p_runningslot == hpts->p_cur_slot)
731 		dis_to_travel = 1;
732 	else
733 		dis_to_travel = hpts_slots_diff(hpts->p_runningslot, hpts->p_cur_slot);
734 	/*
735 	 * How long has the pacer been running?
736 	 */
737 	if (hpts->p_cur_slot != wheel_slot) {
738 		/* The pacer is a bit late */
739 		pacer_to_now = hpts_slots_diff(hpts->p_cur_slot, wheel_slot);
740 	} else {
741 		/* The pacer is right on time, now == pacers start time */
742 		pacer_to_now = 0;
743 	}
744 	/*
745 	 * To get the number left we can insert into we simply
746 	 * subtract the distance the pacer has to run from how
747 	 * many slots there are.
748 	 */
749 	avail_on_wheel = NUM_OF_HPTSI_SLOTS - dis_to_travel;
750 	/*
751 	 * Now how many of those we will eat due to the pacer's
752 	 * time (p_cur_slot) of start being behind the
753 	 * real time (wheel_slot)?
754 	 */
755 	if (avail_on_wheel <= pacer_to_now) {
756 		/*
757 		 * Wheel wrap, we can't fit on the wheel, that
758 		 * is unusual the system must be way overloaded!
759 		 * Insert into the assured slot, and return special
760 		 * "0".
761 		 */
762 		counter_u64_add(combined_wheel_wrap, 1);
763 		*target_slot = hpts->p_nxt_slot;
764 		return (0);
765 	} else {
766 		/*
767 		 * We know how many slots are open
768 		 * on the wheel (the reverse of what
769 		 * is left to run. Take away the time
770 		 * the pacer started to now (wheel_slot)
771 		 * and that tells you how many slots are
772 		 * open that can be inserted into that won't
773 		 * be touched by the pacer until later.
774 		 */
775 		return (avail_on_wheel - pacer_to_now);
776 	}
777 }
778 
779 
780 #ifdef INVARIANTS
781 static void
782 check_if_slot_would_be_wrong(struct tcp_hpts_entry *hpts, struct tcpcb *tp,
783     uint32_t hptsslot, int line)
784 {
785 	/*
786 	 * Sanity checks for the pacer with invariants
787 	 * on insert.
788 	 */
789 	KASSERT(hptsslot < NUM_OF_HPTSI_SLOTS,
790 		("hpts:%p tp:%p slot:%d > max", hpts, tp, hptsslot));
791 	if ((hpts->p_hpts_active) &&
792 	    (hpts->p_wheel_complete == 0)) {
793 		/*
794 		 * If the pacer is processing a arc
795 		 * of the wheel, we need to make
796 		 * sure we are not inserting within
797 		 * that arc.
798 		 */
799 		int distance, yet_to_run;
800 
801 		distance = hpts_slots_diff(hpts->p_runningslot, hptsslot);
802 		if (hpts->p_runningslot != hpts->p_cur_slot)
803 			yet_to_run = hpts_slots_diff(hpts->p_runningslot, hpts->p_cur_slot);
804 		else
805 			yet_to_run = 0;	/* processing last slot */
806 		KASSERT(yet_to_run <= distance, ("hpts:%p tp:%p slot:%d "
807 		    "distance:%d yet_to_run:%d rs:%d cs:%d", hpts, tp,
808 		    hptsslot, distance, yet_to_run, hpts->p_runningslot,
809 		    hpts->p_cur_slot));
810 	}
811 }
812 #endif
813 
814 uint32_t
815 tcp_hpts_insert_diag(struct tcpcb *tp, uint32_t slot, int32_t line, struct hpts_diag *diag)
816 {
817 	struct tcp_hpts_entry *hpts;
818 	struct timeval tv;
819 	uint32_t slot_on, wheel_cts, last_slot, need_new_to = 0;
820 	int32_t wheel_slot, maxslots;
821 	bool need_wakeup = false;
822 
823 	INP_WLOCK_ASSERT(tptoinpcb(tp));
824 	MPASS(!(tptoinpcb(tp)->inp_flags & INP_DROPPED));
825 	MPASS(!tcp_in_hpts(tp));
826 
827 	/*
828 	 * We now return the next-slot the hpts will be on, beyond its
829 	 * current run (if up) or where it was when it stopped if it is
830 	 * sleeping.
831 	 */
832 	hpts = tcp_hpts_lock(tp);
833 	microuptime(&tv);
834 	if (diag) {
835 		memset(diag, 0, sizeof(struct hpts_diag));
836 		diag->p_hpts_active = hpts->p_hpts_active;
837 		diag->p_prev_slot = hpts->p_prev_slot;
838 		diag->p_runningslot = hpts->p_runningslot;
839 		diag->p_nxt_slot = hpts->p_nxt_slot;
840 		diag->p_cur_slot = hpts->p_cur_slot;
841 		diag->p_curtick = hpts->p_curtick;
842 		diag->p_lasttick = hpts->p_lasttick;
843 		diag->slot_req = slot;
844 		diag->p_on_min_sleep = hpts->p_on_min_sleep;
845 		diag->hpts_sleep_time = hpts->p_hpts_sleep_time;
846 	}
847 	if (slot == 0) {
848 		/* Ok we need to set it on the hpts in the current slot */
849 		tp->t_hpts_request = 0;
850 		if ((hpts->p_hpts_active == 0) || (hpts->p_wheel_complete)) {
851 			/*
852 			 * A sleeping hpts we want in next slot to run
853 			 * note that in this state p_prev_slot == p_cur_slot
854 			 */
855 			tp->t_hpts_slot = hpts_slot(hpts->p_prev_slot, 1);
856 			if ((hpts->p_on_min_sleep == 0) &&
857 			    (hpts->p_hpts_active == 0))
858 				need_wakeup = true;
859 		} else
860 			tp->t_hpts_slot = hpts->p_runningslot;
861 		if (__predict_true(tp->t_in_hpts != IHPTS_MOVING))
862 			tcp_hpts_insert_internal(tp, hpts);
863 		if (need_wakeup) {
864 			/*
865 			 * Activate the hpts if it is sleeping and its
866 			 * timeout is not 1.
867 			 */
868 			hpts->p_direct_wake = 1;
869 			tcp_wakehpts(hpts);
870 		}
871 		slot_on = hpts->p_nxt_slot;
872 		HPTS_UNLOCK(hpts);
873 
874 		return (slot_on);
875 	}
876 	/* Get the current time relative to the wheel */
877 	wheel_cts = tcp_tv_to_hptstick(&tv);
878 	/* Map it onto the wheel */
879 	wheel_slot = tick_to_wheel(wheel_cts);
880 	/* Now what's the max we can place it at? */
881 	maxslots = max_slots_available(hpts, wheel_slot, &last_slot);
882 	if (diag) {
883 		diag->wheel_slot = wheel_slot;
884 		diag->maxslots = maxslots;
885 		diag->wheel_cts = wheel_cts;
886 	}
887 	if (maxslots == 0) {
888 		/* The pacer is in a wheel wrap behind, yikes! */
889 		if (slot > 1) {
890 			/*
891 			 * Reduce by 1 to prevent a forever loop in
892 			 * case something else is wrong. Note this
893 			 * probably does not hurt because the pacer
894 			 * if its true is so far behind we will be
895 			 * > 1second late calling anyway.
896 			 */
897 			slot--;
898 		}
899 		tp->t_hpts_slot = last_slot;
900 		tp->t_hpts_request = slot;
901 	} else 	if (maxslots >= slot) {
902 		/* It all fits on the wheel */
903 		tp->t_hpts_request = 0;
904 		tp->t_hpts_slot = hpts_slot(wheel_slot, slot);
905 	} else {
906 		/* It does not fit */
907 		tp->t_hpts_request = slot - maxslots;
908 		tp->t_hpts_slot = last_slot;
909 	}
910 	if (diag) {
911 		diag->slot_remaining = tp->t_hpts_request;
912 		diag->inp_hptsslot = tp->t_hpts_slot;
913 	}
914 #ifdef INVARIANTS
915 	check_if_slot_would_be_wrong(hpts, tp, tp->t_hpts_slot, line);
916 #endif
917 	if (__predict_true(tp->t_in_hpts != IHPTS_MOVING))
918 		tcp_hpts_insert_internal(tp, hpts);
919 	if ((hpts->p_hpts_active == 0) &&
920 	    (tp->t_hpts_request == 0) &&
921 	    (hpts->p_on_min_sleep == 0)) {
922 		/*
923 		 * The hpts is sleeping and NOT on a minimum
924 		 * sleep time, we need to figure out where
925 		 * it will wake up at and if we need to reschedule
926 		 * its time-out.
927 		 */
928 		uint32_t have_slept, yet_to_sleep;
929 
930 		/* Now do we need to restart the hpts's timer? */
931 		have_slept = hpts_slots_diff(hpts->p_prev_slot, wheel_slot);
932 		if (have_slept < hpts->p_hpts_sleep_time)
933 			yet_to_sleep = hpts->p_hpts_sleep_time - have_slept;
934 		else {
935 			/* We are over-due */
936 			yet_to_sleep = 0;
937 			need_wakeup = 1;
938 		}
939 		if (diag) {
940 			diag->have_slept = have_slept;
941 			diag->yet_to_sleep = yet_to_sleep;
942 		}
943 		if (yet_to_sleep &&
944 		    (yet_to_sleep > slot)) {
945 			/*
946 			 * We need to reschedule the hpts's time-out.
947 			 */
948 			hpts->p_hpts_sleep_time = slot;
949 			need_new_to = slot * HPTS_TICKS_PER_SLOT;
950 		}
951 	}
952 	/*
953 	 * Now how far is the hpts sleeping to? if active is 1, its
954 	 * up and ticking we do nothing, otherwise we may need to
955 	 * reschedule its callout if need_new_to is set from above.
956 	 */
957 	if (need_wakeup) {
958 		hpts->p_direct_wake = 1;
959 		tcp_wakehpts(hpts);
960 		if (diag) {
961 			diag->need_new_to = 0;
962 			diag->co_ret = 0xffff0000;
963 		}
964 	} else if (need_new_to) {
965 		int32_t co_ret;
966 		struct timeval tv;
967 		sbintime_t sb;
968 
969 		tv.tv_sec = 0;
970 		tv.tv_usec = 0;
971 		while (need_new_to > HPTS_USEC_IN_SEC) {
972 			tv.tv_sec++;
973 			need_new_to -= HPTS_USEC_IN_SEC;
974 		}
975 		tv.tv_usec = need_new_to;
976 		sb = tvtosbt(tv);
977 		co_ret = callout_reset_sbt_on(&hpts->co, sb, 0,
978 					      hpts_timeout_swi, hpts, hpts->p_cpu,
979 					      (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
980 		if (diag) {
981 			diag->need_new_to = need_new_to;
982 			diag->co_ret = co_ret;
983 		}
984 	}
985 	slot_on = hpts->p_nxt_slot;
986 	HPTS_UNLOCK(hpts);
987 
988 	return (slot_on);
989 }
990 
991 static uint16_t
992 hpts_cpuid(struct tcpcb *tp, int *failed)
993 {
994 	struct inpcb *inp = tptoinpcb(tp);
995 	u_int cpuid;
996 #ifdef NUMA
997 	struct hpts_domain_info *di;
998 #endif
999 
1000 	*failed = 0;
1001 	if (tp->t_flags2 & TF2_HPTS_CPU_SET) {
1002 		return (tp->t_hpts_cpu);
1003 	}
1004 	/*
1005 	 * If we are using the irq cpu set by LRO or
1006 	 * the driver then it overrides all other domains.
1007 	 */
1008 	if (tcp_use_irq_cpu) {
1009 		if (tp->t_lro_cpu == HPTS_CPU_NONE) {
1010 			*failed = 1;
1011 			return (0);
1012 		}
1013 		return (tp->t_lro_cpu);
1014 	}
1015 	/* If one is set the other must be the same */
1016 #ifdef RSS
1017 	cpuid = rss_hash2cpuid(inp->inp_flowid, inp->inp_flowtype);
1018 	if (cpuid == NETISR_CPUID_NONE)
1019 		return (hpts_random_cpu());
1020 	else
1021 		return (cpuid);
1022 #endif
1023 	/*
1024 	 * We don't have a flowid -> cpuid mapping, so cheat and just map
1025 	 * unknown cpuids to curcpu.  Not the best, but apparently better
1026 	 * than defaulting to swi 0.
1027 	 */
1028 	if (inp->inp_flowtype == M_HASHTYPE_NONE) {
1029 		counter_u64_add(cpu_uses_random, 1);
1030 		return (hpts_random_cpu());
1031 	}
1032 	/*
1033 	 * Hash to a thread based on the flowid.  If we are using numa,
1034 	 * then restrict the hash to the numa domain where the inp lives.
1035 	 */
1036 
1037 #ifdef NUMA
1038 	if ((vm_ndomains == 1) ||
1039 	    (inp->inp_numa_domain == M_NODOM)) {
1040 #endif
1041 		cpuid = inp->inp_flowid % mp_ncpus;
1042 #ifdef NUMA
1043 	} else {
1044 		/* Hash into the cpu's that use that domain */
1045 		di = &hpts_domains[inp->inp_numa_domain];
1046 		cpuid = di->cpu[inp->inp_flowid % di->count];
1047 	}
1048 #endif
1049 	counter_u64_add(cpu_uses_flowid, 1);
1050 	return (cpuid);
1051 }
1052 
1053 static void
1054 tcp_hpts_set_max_sleep(struct tcp_hpts_entry *hpts, int wrap_loop_cnt)
1055 {
1056 	uint32_t t = 0, i;
1057 
1058 	if ((hpts->p_on_queue_cnt) && (wrap_loop_cnt < 2)) {
1059 		/*
1060 		 * Find next slot that is occupied and use that to
1061 		 * be the sleep time.
1062 		 */
1063 		for (i = 0, t = hpts_slot(hpts->p_cur_slot, 1); i < NUM_OF_HPTSI_SLOTS; i++) {
1064 			if (TAILQ_EMPTY(&hpts->p_hptss[t].head) == 0) {
1065 				break;
1066 			}
1067 			t = (t + 1) % NUM_OF_HPTSI_SLOTS;
1068 		}
1069 		KASSERT((i != NUM_OF_HPTSI_SLOTS), ("Hpts:%p cnt:%d but none found", hpts, hpts->p_on_queue_cnt));
1070 		hpts->p_hpts_sleep_time = min((i + 1), hpts_sleep_max);
1071 	} else {
1072 		/* No one on the wheel sleep for all but 400 slots or sleep max  */
1073 		hpts->p_hpts_sleep_time = hpts_sleep_max;
1074 	}
1075 }
1076 
1077 static int32_t
1078 tcp_hptsi(struct tcp_hpts_entry *hpts, int from_callout)
1079 {
1080 	struct tcpcb *tp;
1081 	struct timeval tv;
1082 	int32_t slots_to_run, i, error;
1083 	int32_t loop_cnt = 0;
1084 	int32_t did_prefetch = 0;
1085 	int32_t prefetch_tp = 0;
1086 	int32_t wrap_loop_cnt = 0;
1087 	int32_t slot_pos_of_endpoint = 0;
1088 	int32_t orig_exit_slot;
1089 	int8_t completed_measure = 0, seen_endpoint = 0;
1090 
1091 	HPTS_MTX_ASSERT(hpts);
1092 	NET_EPOCH_ASSERT();
1093 	/* record previous info for any logging */
1094 	hpts->saved_lasttick = hpts->p_lasttick;
1095 	hpts->saved_curtick = hpts->p_curtick;
1096 	hpts->saved_curslot = hpts->p_cur_slot;
1097 	hpts->saved_prev_slot = hpts->p_prev_slot;
1098 
1099 	hpts->p_lasttick = hpts->p_curtick;
1100 	hpts->p_curtick = tcp_gethptstick(&tv);
1101 	cts_last_ran[hpts->p_num] = tcp_tv_to_usectick(&tv);
1102 	orig_exit_slot = hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1103 	if ((hpts->p_on_queue_cnt == 0) ||
1104 	    (hpts->p_lasttick == hpts->p_curtick)) {
1105 		/*
1106 		 * No time has yet passed,
1107 		 * or nothing to do.
1108 		 */
1109 		hpts->p_prev_slot = hpts->p_cur_slot;
1110 		hpts->p_lasttick = hpts->p_curtick;
1111 		goto no_run;
1112 	}
1113 again:
1114 	hpts->p_wheel_complete = 0;
1115 	HPTS_MTX_ASSERT(hpts);
1116 	slots_to_run = hpts_slots_diff(hpts->p_prev_slot, hpts->p_cur_slot);
1117 	if (((hpts->p_curtick - hpts->p_lasttick) >
1118 	     ((NUM_OF_HPTSI_SLOTS-1) * HPTS_TICKS_PER_SLOT)) &&
1119 	    (hpts->p_on_queue_cnt != 0)) {
1120 		/*
1121 		 * Wheel wrap is occuring, basically we
1122 		 * are behind and the distance between
1123 		 * run's has spread so much it has exceeded
1124 		 * the time on the wheel (1.024 seconds). This
1125 		 * is ugly and should NOT be happening. We
1126 		 * need to run the entire wheel. We last processed
1127 		 * p_prev_slot, so that needs to be the last slot
1128 		 * we run. The next slot after that should be our
1129 		 * reserved first slot for new, and then starts
1130 		 * the running position. Now the problem is the
1131 		 * reserved "not to yet" place does not exist
1132 		 * and there may be inp's in there that need
1133 		 * running. We can merge those into the
1134 		 * first slot at the head.
1135 		 */
1136 		wrap_loop_cnt++;
1137 		hpts->p_nxt_slot = hpts_slot(hpts->p_prev_slot, 1);
1138 		hpts->p_runningslot = hpts_slot(hpts->p_prev_slot, 2);
1139 		/*
1140 		 * Adjust p_cur_slot to be where we are starting from
1141 		 * hopefully we will catch up (fat chance if something
1142 		 * is broken this bad :( )
1143 		 */
1144 		hpts->p_cur_slot = hpts->p_prev_slot;
1145 		/*
1146 		 * The next slot has guys to run too, and that would
1147 		 * be where we would normally start, lets move them into
1148 		 * the next slot (p_prev_slot + 2) so that we will
1149 		 * run them, the extra 10usecs of late (by being
1150 		 * put behind) does not really matter in this situation.
1151 		 */
1152 		TAILQ_FOREACH(tp, &hpts->p_hptss[hpts->p_nxt_slot].head,
1153 		    t_hpts) {
1154 			MPASS(tp->t_hpts_slot == hpts->p_nxt_slot);
1155 			MPASS(tp->t_hpts_gencnt ==
1156 			    hpts->p_hptss[hpts->p_nxt_slot].gencnt);
1157 			MPASS(tp->t_in_hpts == IHPTS_ONQUEUE);
1158 
1159 			/*
1160 			 * Update gencnt and nextslot accordingly to match
1161 			 * the new location. This is safe since it takes both
1162 			 * the INP lock and the pacer mutex to change the
1163 			 * t_hptsslot and t_hpts_gencnt.
1164 			 */
1165 			tp->t_hpts_gencnt =
1166 			    hpts->p_hptss[hpts->p_runningslot].gencnt;
1167 			tp->t_hpts_slot = hpts->p_runningslot;
1168 		}
1169 		TAILQ_CONCAT(&hpts->p_hptss[hpts->p_runningslot].head,
1170 		    &hpts->p_hptss[hpts->p_nxt_slot].head, t_hpts);
1171 		hpts->p_hptss[hpts->p_runningslot].count +=
1172 		    hpts->p_hptss[hpts->p_nxt_slot].count;
1173 		hpts->p_hptss[hpts->p_nxt_slot].count = 0;
1174 		hpts->p_hptss[hpts->p_nxt_slot].gencnt++;
1175 		slots_to_run = NUM_OF_HPTSI_SLOTS - 1;
1176 		counter_u64_add(wheel_wrap, 1);
1177 	} else {
1178 		/*
1179 		 * Nxt slot is always one after p_runningslot though
1180 		 * its not used usually unless we are doing wheel wrap.
1181 		 */
1182 		hpts->p_nxt_slot = hpts->p_prev_slot;
1183 		hpts->p_runningslot = hpts_slot(hpts->p_prev_slot, 1);
1184 	}
1185 	if (hpts->p_on_queue_cnt == 0) {
1186 		goto no_one;
1187 	}
1188 	for (i = 0; i < slots_to_run; i++) {
1189 		struct tcpcb *tp, *ntp;
1190 		TAILQ_HEAD(, tcpcb) head = TAILQ_HEAD_INITIALIZER(head);
1191 		struct hptsh *hptsh;
1192 		uint32_t runningslot;
1193 
1194 		/*
1195 		 * Calculate our delay, if there are no extra ticks there
1196 		 * was not any (i.e. if slots_to_run == 1, no delay).
1197 		 */
1198 		hpts->p_delayed_by = (slots_to_run - (i + 1)) *
1199 		    HPTS_TICKS_PER_SLOT;
1200 
1201 		runningslot = hpts->p_runningslot;
1202 		hptsh = &hpts->p_hptss[runningslot];
1203 		TAILQ_SWAP(&head, &hptsh->head, tcpcb, t_hpts);
1204 		hpts->p_on_queue_cnt -= hptsh->count;
1205 		hptsh->count = 0;
1206 		hptsh->gencnt++;
1207 
1208 		HPTS_UNLOCK(hpts);
1209 
1210 		TAILQ_FOREACH_SAFE(tp, &head, t_hpts, ntp) {
1211 			struct inpcb *inp = tptoinpcb(tp);
1212 			bool set_cpu;
1213 
1214 			if (ntp != NULL) {
1215 				/*
1216 				 * If we have a next tcpcb, see if we can
1217 				 * prefetch it. Note this may seem
1218 				 * "risky" since we have no locks (other
1219 				 * than the previous inp) and there no
1220 				 * assurance that ntp was not pulled while
1221 				 * we were processing tp and freed. If this
1222 				 * occurred it could mean that either:
1223 				 *
1224 				 * a) Its NULL (which is fine we won't go
1225 				 * here) <or> b) Its valid (which is cool we
1226 				 * will prefetch it) <or> c) The inp got
1227 				 * freed back to the slab which was
1228 				 * reallocated. Then the piece of memory was
1229 				 * re-used and something else (not an
1230 				 * address) is in inp_ppcb. If that occurs
1231 				 * we don't crash, but take a TLB shootdown
1232 				 * performance hit (same as if it was NULL
1233 				 * and we tried to pre-fetch it).
1234 				 *
1235 				 * Considering that the likelyhood of <c> is
1236 				 * quite rare we will take a risk on doing
1237 				 * this. If performance drops after testing
1238 				 * we can always take this out. NB: the
1239 				 * kern_prefetch on amd64 actually has
1240 				 * protection against a bad address now via
1241 				 * the DMAP_() tests. This will prevent the
1242 				 * TLB hit, and instead if <c> occurs just
1243 				 * cause us to load cache with a useless
1244 				 * address (to us).
1245 				 *
1246 				 * XXXGL: this comment and the prefetch action
1247 				 * could be outdated after tp == inp change.
1248 				 */
1249 				kern_prefetch(ntp, &prefetch_tp);
1250 				prefetch_tp = 1;
1251 			}
1252 
1253 			/* For debugging */
1254 			if (seen_endpoint == 0) {
1255 				seen_endpoint = 1;
1256 				orig_exit_slot = slot_pos_of_endpoint =
1257 				    runningslot;
1258 			} else if (completed_measure == 0) {
1259 				/* Record the new position */
1260 				orig_exit_slot = runningslot;
1261 			}
1262 
1263 			INP_WLOCK(inp);
1264 			if ((tp->t_flags2 & TF2_HPTS_CPU_SET) == 0) {
1265 				set_cpu = true;
1266 			} else {
1267 				set_cpu = false;
1268 			}
1269 
1270 			if (__predict_false(tp->t_in_hpts == IHPTS_MOVING)) {
1271 				if (tp->t_hpts_slot == -1) {
1272 					tp->t_in_hpts = IHPTS_NONE;
1273 					if (in_pcbrele_wlocked(inp) == false)
1274 						INP_WUNLOCK(inp);
1275 				} else {
1276 					HPTS_LOCK(hpts);
1277 					tcp_hpts_insert_internal(tp, hpts);
1278 					HPTS_UNLOCK(hpts);
1279 					INP_WUNLOCK(inp);
1280 				}
1281 				continue;
1282 			}
1283 
1284 			MPASS(tp->t_in_hpts == IHPTS_ONQUEUE);
1285 			MPASS(!(inp->inp_flags & INP_DROPPED));
1286 			KASSERT(runningslot == tp->t_hpts_slot,
1287 				("Hpts:%p inp:%p slot mis-aligned %u vs %u",
1288 				 hpts, inp, runningslot, tp->t_hpts_slot));
1289 
1290 			if (tp->t_hpts_request) {
1291 				/*
1292 				 * This guy is deferred out further in time
1293 				 * then our wheel had available on it.
1294 				 * Push him back on the wheel or run it
1295 				 * depending.
1296 				 */
1297 				uint32_t maxslots, last_slot, remaining_slots;
1298 
1299 				remaining_slots = slots_to_run - (i + 1);
1300 				if (tp->t_hpts_request > remaining_slots) {
1301 					HPTS_LOCK(hpts);
1302 					/*
1303 					 * How far out can we go?
1304 					 */
1305 					maxslots = max_slots_available(hpts,
1306 					    hpts->p_cur_slot, &last_slot);
1307 					if (maxslots >= tp->t_hpts_request) {
1308 						/* We can place it finally to
1309 						 * be processed.  */
1310 						tp->t_hpts_slot = hpts_slot(
1311 						    hpts->p_runningslot,
1312 						    tp->t_hpts_request);
1313 						tp->t_hpts_request = 0;
1314 					} else {
1315 						/* Work off some more time */
1316 						tp->t_hpts_slot = last_slot;
1317 						tp->t_hpts_request -=
1318 						    maxslots;
1319 					}
1320 					tcp_hpts_insert_internal(tp, hpts);
1321 					HPTS_UNLOCK(hpts);
1322 					INP_WUNLOCK(inp);
1323 					continue;
1324 				}
1325 				tp->t_hpts_request = 0;
1326 				/* Fall through we will so do it now */
1327 			}
1328 
1329 			tcp_hpts_release(tp);
1330 			if (set_cpu) {
1331 				/*
1332 				 * Setup so the next time we will move to
1333 				 * the right CPU. This should be a rare
1334 				 * event. It will sometimes happens when we
1335 				 * are the client side (usually not the
1336 				 * server). Somehow tcp_output() gets called
1337 				 * before the tcp_do_segment() sets the
1338 				 * intial state. This means the r_cpu and
1339 				 * r_hpts_cpu is 0. We get on the hpts, and
1340 				 * then tcp_input() gets called setting up
1341 				 * the r_cpu to the correct value. The hpts
1342 				 * goes off and sees the mis-match. We
1343 				 * simply correct it here and the CPU will
1344 				 * switch to the new hpts nextime the tcb
1345 				 * gets added to the hpts (not this one)
1346 				 * :-)
1347 				 */
1348 				tcp_set_hpts(tp);
1349 			}
1350 			CURVNET_SET(inp->inp_vnet);
1351 			/* Lets do any logging that we might want to */
1352 			if (hpts_does_tp_logging && tcp_bblogging_on(tp)) {
1353 				tcp_hpts_log(hpts, tp, &tv, slots_to_run, i, from_callout);
1354 			}
1355 
1356 			if (tp->t_fb_ptr != NULL) {
1357 				kern_prefetch(tp->t_fb_ptr, &did_prefetch);
1358 				did_prefetch = 1;
1359 			}
1360 			/*
1361 			 * We set TF2_HPTS_CALLS before any possible output.
1362 			 * The contract with the transport is that if it cares
1363 			 * about hpts calling it should clear the flag. That
1364 			 * way next time it is called it will know it is hpts.
1365 			 *
1366 			 * We also only call tfb_do_queued_segments() <or>
1367 			 * tcp_output().  It is expected that if segments are
1368 			 * queued and come in that the final input mbuf will
1369 			 * cause a call to output if it is needed.
1370 			 */
1371 			tp->t_flags2 |= TF2_HPTS_CALLS;
1372 			if ((tp->t_flags2 & TF2_SUPPORTS_MBUFQ) &&
1373 			    !STAILQ_EMPTY(&tp->t_inqueue)) {
1374 				error = (*tp->t_fb->tfb_do_queued_segments)(tp, 0);
1375 				if (error) {
1376 					/* The input killed the connection */
1377 					goto skip_pacing;
1378 				}
1379 			}
1380 			error = tcp_output(tp);
1381 			if (error < 0)
1382 				goto skip_pacing;
1383 			INP_WUNLOCK(inp);
1384 		skip_pacing:
1385 			CURVNET_RESTORE();
1386 		}
1387 		if (seen_endpoint) {
1388 			/*
1389 			 * We now have a accurate distance between
1390 			 * slot_pos_of_endpoint <-> orig_exit_slot
1391 			 * to tell us how late we were, orig_exit_slot
1392 			 * is where we calculated the end of our cycle to
1393 			 * be when we first entered.
1394 			 */
1395 			completed_measure = 1;
1396 		}
1397 		HPTS_LOCK(hpts);
1398 		hpts->p_runningslot++;
1399 		if (hpts->p_runningslot >= NUM_OF_HPTSI_SLOTS) {
1400 			hpts->p_runningslot = 0;
1401 		}
1402 	}
1403 no_one:
1404 	HPTS_MTX_ASSERT(hpts);
1405 	hpts->p_delayed_by = 0;
1406 	/*
1407 	 * Check to see if we took an excess amount of time and need to run
1408 	 * more ticks (if we did not hit eno-bufs).
1409 	 */
1410 	hpts->p_prev_slot = hpts->p_cur_slot;
1411 	hpts->p_lasttick = hpts->p_curtick;
1412 	if ((from_callout == 0) || (loop_cnt > max_pacer_loops)) {
1413 		/*
1414 		 * Something is serious slow we have
1415 		 * looped through processing the wheel
1416 		 * and by the time we cleared the
1417 		 * needs to run max_pacer_loops time
1418 		 * we still needed to run. That means
1419 		 * the system is hopelessly behind and
1420 		 * can never catch up :(
1421 		 *
1422 		 * We will just lie to this thread
1423 		 * and let it thing p_curtick is
1424 		 * correct. When it next awakens
1425 		 * it will find itself further behind.
1426 		 */
1427 		if (from_callout)
1428 			counter_u64_add(hpts_hopelessly_behind, 1);
1429 		goto no_run;
1430 	}
1431 	hpts->p_curtick = tcp_gethptstick(&tv);
1432 	hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1433 	if (seen_endpoint == 0) {
1434 		/* We saw no endpoint but we may be looping */
1435 		orig_exit_slot = hpts->p_cur_slot;
1436 	}
1437 	if ((wrap_loop_cnt < 2) &&
1438 	    (hpts->p_lasttick != hpts->p_curtick)) {
1439 		counter_u64_add(hpts_loops, 1);
1440 		loop_cnt++;
1441 		goto again;
1442 	}
1443 no_run:
1444 	cts_last_ran[hpts->p_num] = tcp_tv_to_usectick(&tv);
1445 	/*
1446 	 * Set flag to tell that we are done for
1447 	 * any slot input that happens during
1448 	 * input.
1449 	 */
1450 	hpts->p_wheel_complete = 1;
1451 	/*
1452 	 * Now did we spend too long running input and need to run more ticks?
1453 	 * Note that if wrap_loop_cnt < 2 then we should have the conditions
1454 	 * in the KASSERT's true. But if the wheel is behind i.e. wrap_loop_cnt
1455 	 * is greater than 2, then the condtion most likely are *not* true.
1456 	 * Also if we are called not from the callout, we don't run the wheel
1457 	 * multiple times so the slots may not align either.
1458 	 */
1459 	KASSERT(((hpts->p_prev_slot == hpts->p_cur_slot) ||
1460 		 (wrap_loop_cnt >= 2) || (from_callout == 0)),
1461 		("H:%p p_prev_slot:%u not equal to p_cur_slot:%u", hpts,
1462 		 hpts->p_prev_slot, hpts->p_cur_slot));
1463 	KASSERT(((hpts->p_lasttick == hpts->p_curtick)
1464 		 || (wrap_loop_cnt >= 2) || (from_callout == 0)),
1465 		("H:%p p_lasttick:%u not equal to p_curtick:%u", hpts,
1466 		 hpts->p_lasttick, hpts->p_curtick));
1467 	if (from_callout && (hpts->p_lasttick != hpts->p_curtick)) {
1468 		hpts->p_curtick = tcp_gethptstick(&tv);
1469 		counter_u64_add(hpts_loops, 1);
1470 		hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1471 		goto again;
1472 	}
1473 
1474 	if (from_callout){
1475 		tcp_hpts_set_max_sleep(hpts, wrap_loop_cnt);
1476 	}
1477 	if (seen_endpoint)
1478 		return(hpts_slots_diff(slot_pos_of_endpoint, orig_exit_slot));
1479 	else
1480 		return (0);
1481 }
1482 
1483 void
1484 __tcp_set_hpts(struct tcpcb *tp, int32_t line)
1485 {
1486 	struct tcp_hpts_entry *hpts;
1487 	int failed;
1488 
1489 	INP_WLOCK_ASSERT(tptoinpcb(tp));
1490 
1491 	hpts = tcp_hpts_lock(tp);
1492 	if (tp->t_in_hpts == IHPTS_NONE && !(tp->t_flags2 & TF2_HPTS_CPU_SET)) {
1493 		tp->t_hpts_cpu = hpts_cpuid(tp, &failed);
1494 		if (failed == 0)
1495 			tp->t_flags2 |= TF2_HPTS_CPU_SET;
1496 	}
1497 	mtx_unlock(&hpts->p_mtx);
1498 }
1499 
1500 static struct tcp_hpts_entry *
1501 tcp_choose_hpts_to_run(void)
1502 {
1503 	int i, oldest_idx, start, end;
1504 	uint32_t cts, time_since_ran, calc;
1505 
1506 	cts = tcp_get_usecs(NULL);
1507 	time_since_ran = 0;
1508 	/* Default is all one group */
1509 	start = 0;
1510 	end = tcp_pace.rp_num_hptss;
1511 	/*
1512 	 * If we have more than one L3 group figure out which one
1513 	 * this CPU is in.
1514 	 */
1515 	if (tcp_pace.grp_cnt > 1) {
1516 		for (i = 0; i < tcp_pace.grp_cnt; i++) {
1517 			if (CPU_ISSET(curcpu, &tcp_pace.grps[i]->cg_mask)) {
1518 				start = tcp_pace.grps[i]->cg_first;
1519 				end = (tcp_pace.grps[i]->cg_last + 1);
1520 				break;
1521 			}
1522 		}
1523 	}
1524 	oldest_idx = -1;
1525 	for (i = start; i < end; i++) {
1526 		if (TSTMP_GT(cts, cts_last_ran[i]))
1527 			calc = cts - cts_last_ran[i];
1528 		else
1529 			calc = 0;
1530 		if (calc > time_since_ran) {
1531 			oldest_idx = i;
1532 			time_since_ran = calc;
1533 		}
1534 	}
1535 	if (oldest_idx >= 0)
1536 		return(tcp_pace.rp_ent[oldest_idx]);
1537 	else
1538 		return(tcp_pace.rp_ent[(curcpu % tcp_pace.rp_num_hptss)]);
1539 }
1540 
1541 static void
1542 __tcp_run_hpts(void)
1543 {
1544 	struct epoch_tracker et;
1545 	struct tcp_hpts_entry *hpts;
1546 	int ticks_ran;
1547 
1548 	hpts = tcp_choose_hpts_to_run();
1549 
1550 	if (hpts->p_hpts_active) {
1551 		/* Already active */
1552 		return;
1553 	}
1554 	if (mtx_trylock(&hpts->p_mtx) == 0) {
1555 		/* Someone else got the lock */
1556 		return;
1557 	}
1558 	NET_EPOCH_ENTER(et);
1559 	if (hpts->p_hpts_active)
1560 		goto out_with_mtx;
1561 	hpts->syscall_cnt++;
1562 	counter_u64_add(hpts_direct_call, 1);
1563 	hpts->p_hpts_active = 1;
1564 	ticks_ran = tcp_hptsi(hpts, 0);
1565 	/* We may want to adjust the sleep values here */
1566 	if (hpts->p_on_queue_cnt >= conn_cnt_thresh) {
1567 		if (ticks_ran > ticks_indicate_less_sleep) {
1568 			struct timeval tv;
1569 			sbintime_t sb;
1570 
1571 			hpts->p_mysleep.tv_usec /= 2;
1572 			if (hpts->p_mysleep.tv_usec < dynamic_min_sleep)
1573 				hpts->p_mysleep.tv_usec = dynamic_min_sleep;
1574 			/* Reschedule with new to value */
1575 			tcp_hpts_set_max_sleep(hpts, 0);
1576 			tv.tv_sec = 0;
1577 			tv.tv_usec = hpts->p_hpts_sleep_time * HPTS_TICKS_PER_SLOT;
1578 			/* Validate its in the right ranges */
1579 			if (tv.tv_usec < hpts->p_mysleep.tv_usec) {
1580 				hpts->overidden_sleep = tv.tv_usec;
1581 				tv.tv_usec = hpts->p_mysleep.tv_usec;
1582 			} else if (tv.tv_usec > dynamic_max_sleep) {
1583 				/* Lets not let sleep get above this value */
1584 				hpts->overidden_sleep = tv.tv_usec;
1585 				tv.tv_usec = dynamic_max_sleep;
1586 			}
1587 			/*
1588 			 * In this mode the timer is a backstop to
1589 			 * all the userret/lro_flushes so we use
1590 			 * the dynamic value and set the on_min_sleep
1591 			 * flag so we will not be awoken.
1592 			 */
1593 			sb = tvtosbt(tv);
1594 			/* Store off to make visible the actual sleep time */
1595 			hpts->sleeping = tv.tv_usec;
1596 			callout_reset_sbt_on(&hpts->co, sb, 0,
1597 					     hpts_timeout_swi, hpts, hpts->p_cpu,
1598 					     (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
1599 		} else if (ticks_ran < ticks_indicate_more_sleep) {
1600 			/* For the further sleep, don't reschedule  hpts */
1601 			hpts->p_mysleep.tv_usec *= 2;
1602 			if (hpts->p_mysleep.tv_usec > dynamic_max_sleep)
1603 				hpts->p_mysleep.tv_usec = dynamic_max_sleep;
1604 		}
1605 		hpts->p_on_min_sleep = 1;
1606 	}
1607 	hpts->p_hpts_active = 0;
1608 out_with_mtx:
1609 	HPTS_MTX_ASSERT(hpts);
1610 	mtx_unlock(&hpts->p_mtx);
1611 	NET_EPOCH_EXIT(et);
1612 }
1613 
1614 static void
1615 tcp_hpts_thread(void *ctx)
1616 {
1617 	struct tcp_hpts_entry *hpts;
1618 	struct epoch_tracker et;
1619 	struct timeval tv;
1620 	sbintime_t sb;
1621 	int ticks_ran;
1622 
1623 	hpts = (struct tcp_hpts_entry *)ctx;
1624 	mtx_lock(&hpts->p_mtx);
1625 	if (hpts->p_direct_wake) {
1626 		/* Signaled by input or output with low occupancy count. */
1627 		callout_stop(&hpts->co);
1628 		counter_u64_add(hpts_direct_awakening, 1);
1629 	} else {
1630 		/* Timed out, the normal case. */
1631 		counter_u64_add(hpts_wake_timeout, 1);
1632 		if (callout_pending(&hpts->co) ||
1633 		    !callout_active(&hpts->co)) {
1634 			mtx_unlock(&hpts->p_mtx);
1635 			return;
1636 		}
1637 	}
1638 	callout_deactivate(&hpts->co);
1639 	hpts->p_hpts_wake_scheduled = 0;
1640 	NET_EPOCH_ENTER(et);
1641 	if (hpts->p_hpts_active) {
1642 		/*
1643 		 * We are active already. This means that a syscall
1644 		 * trap or LRO is running in behalf of hpts. In that case
1645 		 * we need to double our timeout since there seems to be
1646 		 * enough activity in the system that we don't need to
1647 		 * run as often (if we were not directly woken).
1648 		 */
1649 		if (hpts->p_direct_wake == 0) {
1650 			counter_u64_add(hpts_back_tosleep, 1);
1651 			if (hpts->p_on_queue_cnt >= conn_cnt_thresh) {
1652 				hpts->p_mysleep.tv_usec *= 2;
1653 				if (hpts->p_mysleep.tv_usec > dynamic_max_sleep)
1654 					hpts->p_mysleep.tv_usec = dynamic_max_sleep;
1655 				tv.tv_usec = hpts->p_mysleep.tv_usec;
1656 				hpts->p_on_min_sleep = 1;
1657 			} else {
1658 				/*
1659 				 * Here we have low count on the wheel, but
1660 				 * somehow we still collided with one of the
1661 				 * connections. Lets go back to sleep for a
1662 				 * min sleep time, but clear the flag so we
1663 				 * can be awoken by insert.
1664 				 */
1665 				hpts->p_on_min_sleep = 0;
1666 				tv.tv_usec = tcp_min_hptsi_time;
1667 			}
1668 		} else {
1669 			/*
1670 			 * Directly woken most likely to reset the
1671 			 * callout time.
1672 			 */
1673 			tv.tv_sec = 0;
1674 			tv.tv_usec = hpts->p_mysleep.tv_usec;
1675 		}
1676 		goto back_to_sleep;
1677 	}
1678 	hpts->sleeping = 0;
1679 	hpts->p_hpts_active = 1;
1680 	ticks_ran = tcp_hptsi(hpts, 1);
1681 	tv.tv_sec = 0;
1682 	tv.tv_usec = hpts->p_hpts_sleep_time * HPTS_TICKS_PER_SLOT;
1683 	if (hpts->p_on_queue_cnt >= conn_cnt_thresh) {
1684 		if(hpts->p_direct_wake == 0) {
1685 			/*
1686 			 * Only adjust sleep time if we were
1687 			 * called from the callout i.e. direct_wake == 0.
1688 			 */
1689 			if (ticks_ran < ticks_indicate_more_sleep) {
1690 				hpts->p_mysleep.tv_usec *= 2;
1691 				if (hpts->p_mysleep.tv_usec > dynamic_max_sleep)
1692 					hpts->p_mysleep.tv_usec = dynamic_max_sleep;
1693 			} else if (ticks_ran > ticks_indicate_less_sleep) {
1694 				hpts->p_mysleep.tv_usec /= 2;
1695 				if (hpts->p_mysleep.tv_usec < dynamic_min_sleep)
1696 					hpts->p_mysleep.tv_usec = dynamic_min_sleep;
1697 			}
1698 		}
1699 		if (tv.tv_usec < hpts->p_mysleep.tv_usec) {
1700 			hpts->overidden_sleep = tv.tv_usec;
1701 			tv.tv_usec = hpts->p_mysleep.tv_usec;
1702 		} else if (tv.tv_usec > dynamic_max_sleep) {
1703 			/* Lets not let sleep get above this value */
1704 			hpts->overidden_sleep = tv.tv_usec;
1705 			tv.tv_usec = dynamic_max_sleep;
1706 		}
1707 		/*
1708 		 * In this mode the timer is a backstop to
1709 		 * all the userret/lro_flushes so we use
1710 		 * the dynamic value and set the on_min_sleep
1711 		 * flag so we will not be awoken.
1712 		 */
1713 		hpts->p_on_min_sleep = 1;
1714 	} else if (hpts->p_on_queue_cnt == 0)  {
1715 		/*
1716 		 * No one on the wheel, please wake us up
1717 		 * if you insert on the wheel.
1718 		 */
1719 		hpts->p_on_min_sleep = 0;
1720 		hpts->overidden_sleep = 0;
1721 	} else {
1722 		/*
1723 		 * We hit here when we have a low number of
1724 		 * clients on the wheel (our else clause).
1725 		 * We may need to go on min sleep, if we set
1726 		 * the flag we will not be awoken if someone
1727 		 * is inserted ahead of us. Clearing the flag
1728 		 * means we can be awoken. This is "old mode"
1729 		 * where the timer is what runs hpts mainly.
1730 		 */
1731 		if (tv.tv_usec < tcp_min_hptsi_time) {
1732 			/*
1733 			 * Yes on min sleep, which means
1734 			 * we cannot be awoken.
1735 			 */
1736 			hpts->overidden_sleep = tv.tv_usec;
1737 			tv.tv_usec = tcp_min_hptsi_time;
1738 			hpts->p_on_min_sleep = 1;
1739 		} else {
1740 			/* Clear the min sleep flag */
1741 			hpts->overidden_sleep = 0;
1742 			hpts->p_on_min_sleep = 0;
1743 		}
1744 	}
1745 	HPTS_MTX_ASSERT(hpts);
1746 	hpts->p_hpts_active = 0;
1747 back_to_sleep:
1748 	hpts->p_direct_wake = 0;
1749 	sb = tvtosbt(tv);
1750 	/* Store off to make visible the actual sleep time */
1751 	hpts->sleeping = tv.tv_usec;
1752 	callout_reset_sbt_on(&hpts->co, sb, 0,
1753 			     hpts_timeout_swi, hpts, hpts->p_cpu,
1754 			     (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
1755 	NET_EPOCH_EXIT(et);
1756 	mtx_unlock(&hpts->p_mtx);
1757 }
1758 
1759 #undef	timersub
1760 
1761 static int32_t
1762 hpts_count_level(struct cpu_group *cg)
1763 {
1764 	int32_t count_l3, i;
1765 
1766 	count_l3 = 0;
1767 	if (cg->cg_level == CG_SHARE_L3)
1768 		count_l3++;
1769 	/* Walk all the children looking for L3 */
1770 	for (i = 0; i < cg->cg_children; i++) {
1771 		count_l3 += hpts_count_level(&cg->cg_child[i]);
1772 	}
1773 	return (count_l3);
1774 }
1775 
1776 static void
1777 hpts_gather_grps(struct cpu_group **grps, int32_t *at, int32_t max, struct cpu_group *cg)
1778 {
1779 	int32_t idx, i;
1780 
1781 	idx = *at;
1782 	if (cg->cg_level == CG_SHARE_L3) {
1783 		grps[idx] = cg;
1784 		idx++;
1785 		if (idx == max) {
1786 			*at = idx;
1787 			return;
1788 		}
1789 	}
1790 	*at = idx;
1791 	/* Walk all the children looking for L3 */
1792 	for (i = 0; i < cg->cg_children; i++) {
1793 		hpts_gather_grps(grps, at, max, &cg->cg_child[i]);
1794 	}
1795 }
1796 
1797 static void
1798 tcp_init_hptsi(void *st)
1799 {
1800 	struct cpu_group *cpu_top;
1801 	int32_t error __diagused;
1802 	int32_t i, j, bound = 0, created = 0;
1803 	size_t sz, asz;
1804 	struct timeval tv;
1805 	sbintime_t sb;
1806 	struct tcp_hpts_entry *hpts;
1807 	struct pcpu *pc;
1808 	char unit[16];
1809 	uint32_t ncpus = mp_ncpus ? mp_ncpus : MAXCPU;
1810 	int count, domain;
1811 
1812 #ifdef SMP
1813 	cpu_top = smp_topo();
1814 #else
1815 	cpu_top = NULL;
1816 #endif
1817 	tcp_pace.rp_num_hptss = ncpus;
1818 	hpts_hopelessly_behind = counter_u64_alloc(M_WAITOK);
1819 	hpts_loops = counter_u64_alloc(M_WAITOK);
1820 	back_tosleep = counter_u64_alloc(M_WAITOK);
1821 	combined_wheel_wrap = counter_u64_alloc(M_WAITOK);
1822 	wheel_wrap = counter_u64_alloc(M_WAITOK);
1823 	hpts_wake_timeout = counter_u64_alloc(M_WAITOK);
1824 	hpts_direct_awakening = counter_u64_alloc(M_WAITOK);
1825 	hpts_back_tosleep = counter_u64_alloc(M_WAITOK);
1826 	hpts_direct_call = counter_u64_alloc(M_WAITOK);
1827 	cpu_uses_flowid = counter_u64_alloc(M_WAITOK);
1828 	cpu_uses_random = counter_u64_alloc(M_WAITOK);
1829 
1830 	sz = (tcp_pace.rp_num_hptss * sizeof(struct tcp_hpts_entry *));
1831 	tcp_pace.rp_ent = malloc(sz, M_TCPHPTS, M_WAITOK | M_ZERO);
1832 	sz = (sizeof(uint32_t) * tcp_pace.rp_num_hptss);
1833 	cts_last_ran = malloc(sz, M_TCPHPTS, M_WAITOK);
1834 	tcp_pace.grp_cnt = 0;
1835 	if (cpu_top == NULL) {
1836 		tcp_pace.grp_cnt = 1;
1837 	} else {
1838 		/* Find out how many cache level 3 domains we have */
1839 		count = 0;
1840 		tcp_pace.grp_cnt = hpts_count_level(cpu_top);
1841 		if (tcp_pace.grp_cnt == 0) {
1842 			tcp_pace.grp_cnt = 1;
1843 		}
1844 		sz = (tcp_pace.grp_cnt * sizeof(struct cpu_group *));
1845 		tcp_pace.grps = malloc(sz, M_TCPHPTS, M_WAITOK);
1846 		/* Now populate the groups */
1847 		if (tcp_pace.grp_cnt == 1) {
1848 			/*
1849 			 * All we need is the top level all cpu's are in
1850 			 * the same cache so when we use grp[0]->cg_mask
1851 			 * with the cg_first <-> cg_last it will include
1852 			 * all cpu's in it. The level here is probably
1853 			 * zero which is ok.
1854 			 */
1855 			tcp_pace.grps[0] = cpu_top;
1856 		} else {
1857 			/*
1858 			 * Here we must find all the level three cache domains
1859 			 * and setup our pointers to them.
1860 			 */
1861 			count = 0;
1862 			hpts_gather_grps(tcp_pace.grps, &count, tcp_pace.grp_cnt, cpu_top);
1863 		}
1864 	}
1865 	asz = sizeof(struct hptsh) * NUM_OF_HPTSI_SLOTS;
1866 	for (i = 0; i < tcp_pace.rp_num_hptss; i++) {
1867 		tcp_pace.rp_ent[i] = malloc(sizeof(struct tcp_hpts_entry),
1868 		    M_TCPHPTS, M_WAITOK | M_ZERO);
1869 		tcp_pace.rp_ent[i]->p_hptss = malloc(asz, M_TCPHPTS, M_WAITOK);
1870 		hpts = tcp_pace.rp_ent[i];
1871 		/*
1872 		 * Init all the hpts structures that are not specifically
1873 		 * zero'd by the allocations. Also lets attach them to the
1874 		 * appropriate sysctl block as well.
1875 		 */
1876 		mtx_init(&hpts->p_mtx, "tcp_hpts_lck",
1877 		    "hpts", MTX_DEF | MTX_DUPOK);
1878 		for (j = 0; j < NUM_OF_HPTSI_SLOTS; j++) {
1879 			TAILQ_INIT(&hpts->p_hptss[j].head);
1880 			hpts->p_hptss[j].count = 0;
1881 			hpts->p_hptss[j].gencnt = 0;
1882 		}
1883 		sysctl_ctx_init(&hpts->hpts_ctx);
1884 		sprintf(unit, "%d", i);
1885 		hpts->hpts_root = SYSCTL_ADD_NODE(&hpts->hpts_ctx,
1886 		    SYSCTL_STATIC_CHILDREN(_net_inet_tcp_hpts),
1887 		    OID_AUTO,
1888 		    unit,
1889 		    CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
1890 		    "");
1891 		SYSCTL_ADD_INT(&hpts->hpts_ctx,
1892 		    SYSCTL_CHILDREN(hpts->hpts_root),
1893 		    OID_AUTO, "out_qcnt", CTLFLAG_RD,
1894 		    &hpts->p_on_queue_cnt, 0,
1895 		    "Count TCB's awaiting output processing");
1896 		SYSCTL_ADD_U16(&hpts->hpts_ctx,
1897 		    SYSCTL_CHILDREN(hpts->hpts_root),
1898 		    OID_AUTO, "active", CTLFLAG_RD,
1899 		    &hpts->p_hpts_active, 0,
1900 		    "Is the hpts active");
1901 		SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1902 		    SYSCTL_CHILDREN(hpts->hpts_root),
1903 		    OID_AUTO, "curslot", CTLFLAG_RD,
1904 		    &hpts->p_cur_slot, 0,
1905 		    "What the current running pacers goal");
1906 		SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1907 		    SYSCTL_CHILDREN(hpts->hpts_root),
1908 		    OID_AUTO, "runtick", CTLFLAG_RD,
1909 		    &hpts->p_runningslot, 0,
1910 		    "What the running pacers current slot is");
1911 		SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1912 		    SYSCTL_CHILDREN(hpts->hpts_root),
1913 		    OID_AUTO, "curtick", CTLFLAG_RD,
1914 		    &hpts->p_curtick, 0,
1915 		    "What the running pacers last tick mapped to the wheel was");
1916 		SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1917 		    SYSCTL_CHILDREN(hpts->hpts_root),
1918 		    OID_AUTO, "lastran", CTLFLAG_RD,
1919 		    &cts_last_ran[i], 0,
1920 		    "The last usec tick that this hpts ran");
1921 		SYSCTL_ADD_LONG(&hpts->hpts_ctx,
1922 		    SYSCTL_CHILDREN(hpts->hpts_root),
1923 		    OID_AUTO, "cur_min_sleep", CTLFLAG_RD,
1924 		    &hpts->p_mysleep.tv_usec,
1925 		    "What the running pacers is using for p_mysleep.tv_usec");
1926 		SYSCTL_ADD_U64(&hpts->hpts_ctx,
1927 		    SYSCTL_CHILDREN(hpts->hpts_root),
1928 		    OID_AUTO, "now_sleeping", CTLFLAG_RD,
1929 		    &hpts->sleeping, 0,
1930 		    "What the running pacers is actually sleeping for");
1931 		SYSCTL_ADD_U64(&hpts->hpts_ctx,
1932 		    SYSCTL_CHILDREN(hpts->hpts_root),
1933 		    OID_AUTO, "syscall_cnt", CTLFLAG_RD,
1934 		    &hpts->syscall_cnt, 0,
1935 		    "How many times we had syscalls on this hpts");
1936 
1937 		hpts->p_hpts_sleep_time = hpts_sleep_max;
1938 		hpts->p_num = i;
1939 		hpts->p_curtick = tcp_gethptstick(&tv);
1940 		cts_last_ran[i] = tcp_tv_to_usectick(&tv);
1941 		hpts->p_prev_slot = hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1942 		hpts->p_cpu = 0xffff;
1943 		hpts->p_nxt_slot = hpts_slot(hpts->p_cur_slot, 1);
1944 		callout_init(&hpts->co, 1);
1945 	}
1946 	/* Don't try to bind to NUMA domains if we don't have any */
1947 	if (vm_ndomains == 1 && tcp_bind_threads == 2)
1948 		tcp_bind_threads = 0;
1949 
1950 	/*
1951 	 * Now lets start ithreads to handle the hptss.
1952 	 */
1953 	for (i = 0; i < tcp_pace.rp_num_hptss; i++) {
1954 		hpts = tcp_pace.rp_ent[i];
1955 		hpts->p_cpu = i;
1956 
1957 		error = swi_add(&hpts->ie, "hpts",
1958 		    tcp_hpts_thread, (void *)hpts,
1959 		    SWI_NET, INTR_MPSAFE, &hpts->ie_cookie);
1960 		KASSERT(error == 0,
1961 			("Can't add hpts:%p i:%d err:%d",
1962 			 hpts, i, error));
1963 		created++;
1964 		hpts->p_mysleep.tv_sec = 0;
1965 		hpts->p_mysleep.tv_usec = tcp_min_hptsi_time;
1966 		if (tcp_bind_threads == 1) {
1967 			if (intr_event_bind(hpts->ie, i) == 0)
1968 				bound++;
1969 		} else if (tcp_bind_threads == 2) {
1970 			/* Find the group for this CPU (i) and bind into it */
1971 			for (j = 0; j < tcp_pace.grp_cnt; j++) {
1972 				if (CPU_ISSET(i, &tcp_pace.grps[j]->cg_mask)) {
1973 					if (intr_event_bind_ithread_cpuset(hpts->ie,
1974 						&tcp_pace.grps[j]->cg_mask) == 0) {
1975 						bound++;
1976 						pc = pcpu_find(i);
1977 						domain = pc->pc_domain;
1978 						count = hpts_domains[domain].count;
1979 						hpts_domains[domain].cpu[count] = i;
1980 						hpts_domains[domain].count++;
1981 						break;
1982 					}
1983 				}
1984 			}
1985 		}
1986 		tv.tv_sec = 0;
1987 		tv.tv_usec = hpts->p_hpts_sleep_time * HPTS_TICKS_PER_SLOT;
1988 		hpts->sleeping = tv.tv_usec;
1989 		sb = tvtosbt(tv);
1990 		callout_reset_sbt_on(&hpts->co, sb, 0,
1991 				     hpts_timeout_swi, hpts, hpts->p_cpu,
1992 				     (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
1993 	}
1994 	/*
1995 	 * If we somehow have an empty domain, fall back to choosing
1996 	 * among all htps threads.
1997 	 */
1998 	for (i = 0; i < vm_ndomains; i++) {
1999 		if (hpts_domains[i].count == 0) {
2000 			tcp_bind_threads = 0;
2001 			break;
2002 		}
2003 	}
2004 	tcp_hpts_softclock = __tcp_run_hpts;
2005 	tcp_lro_hpts_init();
2006 	printf("TCP Hpts created %d swi interrupt threads and bound %d to %s\n",
2007 	    created, bound,
2008 	    tcp_bind_threads == 2 ? "NUMA domains" : "cpus");
2009 #ifdef INVARIANTS
2010 	printf("HPTS is in INVARIANT mode!!\n");
2011 #endif
2012 }
2013 
2014 SYSINIT(tcphptsi, SI_SUB_SOFTINTR, SI_ORDER_ANY, tcp_init_hptsi, NULL);
2015 MODULE_VERSION(tcphpts, 1);
2016