2 * Copyright (c) 2016-2018 Netflix, Inc.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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
26 #include <sys/cdefs.h>
27 __FBSDID("$FreeBSD$");
30 #include "opt_inet6.h"
31 #include "opt_tcpdebug.h"
33 * Some notes about usage.
35 * The tcp_hpts system is designed to provide a high precision timer
36 * system for tcp. Its main purpose is to provide a mechanism for
37 * pacing packets out onto the wire. It can be used in two ways
38 * by a given TCP stack (and those two methods can be used simultaneously).
40 * First, and probably the main thing its used by Rack and BBR, it can
41 * be used to call tcp_output() of a transport stack at some time in the future.
42 * The normal way this is done is that tcp_output() of the stack schedules
43 * itself to be called again by calling tcp_hpts_insert(tcpcb, slot). The
44 * slot is the time from now that the stack wants to be called but it
45 * must be converted to tcp_hpts's notion of slot. This is done with
46 * one of the macros HPTS_MS_TO_SLOTS or HPTS_USEC_TO_SLOTS. So a typical
47 * call from the tcp_output() routine might look like:
49 * tcp_hpts_insert(tp, HPTS_USEC_TO_SLOTS(550));
51 * The above would schedule tcp_ouput() to be called in 550 useconds.
52 * Note that if using this mechanism the stack will want to add near
53 * its top a check to prevent unwanted calls (from user land or the
54 * arrival of incoming ack's). So it would add something like:
56 * if (inp->inp_in_hpts)
59 * to prevent output processing until the time alotted has gone by.
60 * Of course this is a bare bones example and the stack will probably
61 * have more consideration then just the above.
63 * Now the second function (actually two functions I guess :D)
64 * the tcp_hpts system provides is the ability to either abort
65 * a connection (later) or process input on a connection.
66 * Why would you want to do this? To keep processor locality
67 * and or not have to worry about untangling any recursive
68 * locks. The input function now is hooked to the new LRO
71 * In order to use the input redirection function the
72 * tcp stack must define an input function for
73 * tfb_do_queued_segments(). This function understands
74 * how to dequeue a array of packets that were input and
75 * knows how to call the correct processing routine.
77 * Locking in this is important as well so most likely the
78 * stack will need to define the tfb_do_segment_nounlock()
79 * splitting tfb_do_segment() into two parts. The main processing
80 * part that does not unlock the INP and returns a value of 1 or 0.
81 * It returns 0 if all is well and the lock was not released. It
82 * returns 1 if we had to destroy the TCB (a reset received etc).
83 * The remains of tfb_do_segment() then become just a simple call
84 * to the tfb_do_segment_nounlock() function and check the return
85 * code and possibly unlock.
87 * The stack must also set the flag on the INP that it supports this
88 * feature i.e. INP_SUPPORTS_MBUFQ. The LRO code recoginizes
89 * this flag as well and will queue packets when it is set.
90 * There are other flags as well INP_MBUF_QUEUE_READY and
91 * INP_DONT_SACK_QUEUE. The first flag tells the LRO code
92 * that we are in the pacer for output so there is no
93 * need to wake up the hpts system to get immediate
94 * input. The second tells the LRO code that its okay
95 * if a SACK arrives you can still defer input and let
96 * the current hpts timer run (this is usually set when
97 * a rack timer is up so we know SACK's are happening
98 * on the connection already and don't want to wakeup yet).
100 * There is a common functions within the rack_bbr_common code
101 * version i.e. ctf_do_queued_segments(). This function
102 * knows how to take the input queue of packets from
103 * tp->t_in_pkts and process them digging out
104 * all the arguments, calling any bpf tap and
105 * calling into tfb_do_segment_nounlock(). The common
106 * function (ctf_do_queued_segments()) requires that
107 * you have defined the tfb_do_segment_nounlock() as
110 * The second feature of the input side of hpts is the
111 * dropping of a connection. This is due to the way that
112 * locking may have occured on the INP_WLOCK. So if
113 * a stack wants to drop a connection it calls:
115 * tcp_set_inp_to_drop(tp, ETIMEDOUT)
117 * To schedule the tcp_hpts system to call
119 * tcp_drop(tp, drop_reason)
121 * at a future point. This is quite handy to prevent locking
122 * issues when dropping connections.
126 #include <sys/param.h>
128 #include <sys/interrupt.h>
129 #include <sys/module.h>
130 #include <sys/kernel.h>
131 #include <sys/hhook.h>
132 #include <sys/malloc.h>
133 #include <sys/mbuf.h>
134 #include <sys/proc.h> /* for proc0 declaration */
135 #include <sys/socket.h>
136 #include <sys/socketvar.h>
137 #include <sys/sysctl.h>
138 #include <sys/systm.h>
139 #include <sys/refcount.h>
140 #include <sys/sched.h>
141 #include <sys/queue.h>
143 #include <sys/counter.h>
144 #include <sys/time.h>
145 #include <sys/kthread.h>
146 #include <sys/kern_prefetch.h>
151 #include <net/route.h>
152 #include <net/vnet.h>
154 #define TCPSTATES /* for logging */
156 #include <netinet/in.h>
157 #include <netinet/in_kdtrace.h>
158 #include <netinet/in_pcb.h>
159 #include <netinet/ip.h>
160 #include <netinet/ip_icmp.h> /* required for icmp_var.h */
161 #include <netinet/icmp_var.h> /* for ICMP_BANDLIM */
162 #include <netinet/ip_var.h>
163 #include <netinet/ip6.h>
164 #include <netinet6/in6_pcb.h>
165 #include <netinet6/ip6_var.h>
166 #include <netinet/tcp.h>
167 #include <netinet/tcp_fsm.h>
168 #include <netinet/tcp_seq.h>
169 #include <netinet/tcp_timer.h>
170 #include <netinet/tcp_var.h>
171 #include <netinet/tcpip.h>
172 #include <netinet/cc/cc.h>
173 #include <netinet/tcp_hpts.h>
174 #include <netinet/tcp_log_buf.h>
177 #include <netinet/tcp_debug.h>
178 #endif /* tcpdebug */
180 #include <netinet/tcp_offload.h>
185 MALLOC_DEFINE(M_TCPHPTS, "tcp_hpts", "TCP hpts");
187 static int tcp_bind_threads = 1;
189 static int tcp_bind_threads = 2;
191 TUNABLE_INT("net.inet.tcp.bind_hptss", &tcp_bind_threads);
193 static struct tcp_hptsi tcp_pace;
194 static int hpts_does_tp_logging = 0;
196 static void tcp_wakehpts(struct tcp_hpts_entry *p);
197 static void tcp_wakeinput(struct tcp_hpts_entry *p);
198 static void tcp_input_data(struct tcp_hpts_entry *hpts, struct timeval *tv);
199 static void tcp_hptsi(struct tcp_hpts_entry *hpts);
200 static void tcp_hpts_thread(void *ctx);
201 static void tcp_init_hptsi(void *st);
203 int32_t tcp_min_hptsi_time = DEFAULT_MIN_SLEEP;
204 static int32_t tcp_hpts_callout_skip_swi = 0;
206 SYSCTL_NODE(_net_inet_tcp, OID_AUTO, hpts, CTLFLAG_RW, 0, "TCP Hpts controls");
208 #define timersub(tvp, uvp, vvp) \
210 (vvp)->tv_sec = (tvp)->tv_sec - (uvp)->tv_sec; \
211 (vvp)->tv_usec = (tvp)->tv_usec - (uvp)->tv_usec; \
212 if ((vvp)->tv_usec < 0) { \
214 (vvp)->tv_usec += 1000000; \
218 static int32_t tcp_hpts_precision = 120;
220 struct hpts_domain_info {
225 struct hpts_domain_info hpts_domains[MAXMEMDOM];
227 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, precision, CTLFLAG_RW,
228 &tcp_hpts_precision, 120,
229 "Value for PRE() precision of callout");
231 counter_u64_t hpts_hopelessly_behind;
233 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts, OID_AUTO, hopeless, CTLFLAG_RD,
234 &hpts_hopelessly_behind,
235 "Number of times hpts could not catch up and was behind hopelessly");
237 counter_u64_t hpts_loops;
239 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts, OID_AUTO, loops, CTLFLAG_RD,
240 &hpts_loops, "Number of times hpts had to loop to catch up");
243 counter_u64_t back_tosleep;
245 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts, OID_AUTO, no_tcbsfound, CTLFLAG_RD,
246 &back_tosleep, "Number of times hpts found no tcbs");
248 counter_u64_t combined_wheel_wrap;
250 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts, OID_AUTO, comb_wheel_wrap, CTLFLAG_RD,
251 &combined_wheel_wrap, "Number of times the wheel lagged enough to have an insert see wrap");
253 counter_u64_t wheel_wrap;
255 SYSCTL_COUNTER_U64(_net_inet_tcp_hpts, OID_AUTO, wheel_wrap, CTLFLAG_RD,
256 &wheel_wrap, "Number of times the wheel lagged enough to have an insert see wrap");
258 static int32_t out_ts_percision = 0;
260 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, out_tspercision, CTLFLAG_RW,
261 &out_ts_percision, 0,
262 "Do we use a percise timestamp for every output cts");
263 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, logging, CTLFLAG_RW,
264 &hpts_does_tp_logging, 0,
265 "Do we add to any tp that has logging on pacer logs");
267 static int32_t max_pacer_loops = 10;
268 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, loopmax, CTLFLAG_RW,
269 &max_pacer_loops, 10,
270 "What is the maximum number of times the pacer will loop trying to catch up");
272 #define HPTS_MAX_SLEEP_ALLOWED (NUM_OF_HPTSI_SLOTS/2)
274 static uint32_t hpts_sleep_max = HPTS_MAX_SLEEP_ALLOWED;
278 sysctl_net_inet_tcp_hpts_max_sleep(SYSCTL_HANDLER_ARGS)
283 new = hpts_sleep_max;
284 error = sysctl_handle_int(oidp, &new, 0, req);
285 if (error == 0 && req->newptr) {
286 if ((new < (NUM_OF_HPTSI_SLOTS / 4)) ||
287 (new > HPTS_MAX_SLEEP_ALLOWED))
290 hpts_sleep_max = new;
295 SYSCTL_PROC(_net_inet_tcp_hpts, OID_AUTO, maxsleep,
296 CTLTYPE_UINT | CTLFLAG_RW,
298 &sysctl_net_inet_tcp_hpts_max_sleep, "IU",
299 "Maximum time hpts will sleep");
301 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, minsleep, CTLFLAG_RW,
302 &tcp_min_hptsi_time, 0,
303 "The minimum time the hpts must sleep before processing more slots");
305 SYSCTL_INT(_net_inet_tcp_hpts, OID_AUTO, skip_swi, CTLFLAG_RW,
306 &tcp_hpts_callout_skip_swi, 0,
307 "Do we have the callout call directly to the hpts?");
310 tcp_hpts_log(struct tcp_hpts_entry *hpts, struct tcpcb *tp, struct timeval *tv,
311 int ticks_to_run, int idx)
313 union tcp_log_stackspecific log;
315 memset(&log.u_bbr, 0, sizeof(log.u_bbr));
316 log.u_bbr.flex1 = hpts->p_nxt_slot;
317 log.u_bbr.flex2 = hpts->p_cur_slot;
318 log.u_bbr.flex3 = hpts->p_prev_slot;
319 log.u_bbr.flex4 = idx;
320 log.u_bbr.flex5 = hpts->p_curtick;
321 log.u_bbr.flex6 = hpts->p_on_queue_cnt;
322 log.u_bbr.use_lt_bw = 1;
323 log.u_bbr.inflight = ticks_to_run;
324 log.u_bbr.applimited = hpts->overidden_sleep;
325 log.u_bbr.delivered = hpts->saved_curtick;
326 log.u_bbr.timeStamp = tcp_tv_to_usectick(tv);
327 log.u_bbr.epoch = hpts->saved_curslot;
328 log.u_bbr.lt_epoch = hpts->saved_prev_slot;
329 log.u_bbr.pkts_out = hpts->p_delayed_by;
330 log.u_bbr.lost = hpts->p_hpts_sleep_time;
331 log.u_bbr.cur_del_rate = hpts->p_runningtick;
332 TCP_LOG_EVENTP(tp, NULL,
333 &tp->t_inpcb->inp_socket->so_rcv,
334 &tp->t_inpcb->inp_socket->so_snd,
340 hpts_timeout_swi(void *arg)
342 struct tcp_hpts_entry *hpts;
344 hpts = (struct tcp_hpts_entry *)arg;
345 swi_sched(hpts->ie_cookie, 0);
349 hpts_timeout_dir(void *arg)
351 tcp_hpts_thread(arg);
355 hpts_sane_pace_remove(struct tcp_hpts_entry *hpts, struct inpcb *inp, struct hptsh *head, int clear)
358 if (mtx_owned(&hpts->p_mtx) == 0) {
359 /* We don't own the mutex? */
360 panic("%s: hpts:%p inp:%p no hpts mutex", __FUNCTION__, hpts, inp);
362 if (hpts->p_cpu != inp->inp_hpts_cpu) {
363 /* It is not the right cpu/mutex? */
364 panic("%s: hpts:%p inp:%p incorrect CPU", __FUNCTION__, hpts, inp);
366 if (inp->inp_in_hpts == 0) {
367 /* We are not on the hpts? */
368 panic("%s: hpts:%p inp:%p not on the hpts?", __FUNCTION__, hpts, inp);
371 TAILQ_REMOVE(head, inp, inp_hpts);
372 hpts->p_on_queue_cnt--;
373 if (hpts->p_on_queue_cnt < 0) {
374 /* Count should not go negative .. */
376 panic("Hpts goes negative inp:%p hpts:%p",
379 hpts->p_on_queue_cnt = 0;
382 inp->inp_hpts_request = 0;
383 inp->inp_in_hpts = 0;
388 hpts_sane_pace_insert(struct tcp_hpts_entry *hpts, struct inpcb *inp, struct hptsh *head, int line, int noref)
391 if (mtx_owned(&hpts->p_mtx) == 0) {
392 /* We don't own the mutex? */
393 panic("%s: hpts:%p inp:%p no hpts mutex", __FUNCTION__, hpts, inp);
395 if (hpts->p_cpu != inp->inp_hpts_cpu) {
396 /* It is not the right cpu/mutex? */
397 panic("%s: hpts:%p inp:%p incorrect CPU", __FUNCTION__, hpts, inp);
399 if ((noref == 0) && (inp->inp_in_hpts == 1)) {
400 /* We are already on the hpts? */
401 panic("%s: hpts:%p inp:%p already on the hpts?", __FUNCTION__, hpts, inp);
404 TAILQ_INSERT_TAIL(head, inp, inp_hpts);
405 inp->inp_in_hpts = 1;
406 hpts->p_on_queue_cnt++;
413 hpts_sane_input_remove(struct tcp_hpts_entry *hpts, struct inpcb *inp, int clear)
416 if (mtx_owned(&hpts->p_mtx) == 0) {
417 /* We don't own the mutex? */
418 panic("%s: hpts:%p inp:%p no hpts mutex", __FUNCTION__, hpts, inp);
420 if (hpts->p_cpu != inp->inp_input_cpu) {
421 /* It is not the right cpu/mutex? */
422 panic("%s: hpts:%p inp:%p incorrect CPU", __FUNCTION__, hpts, inp);
424 if (inp->inp_in_input == 0) {
425 /* We are not on the input hpts? */
426 panic("%s: hpts:%p inp:%p not on the input hpts?", __FUNCTION__, hpts, inp);
429 TAILQ_REMOVE(&hpts->p_input, inp, inp_input);
430 hpts->p_on_inqueue_cnt--;
431 if (hpts->p_on_inqueue_cnt < 0) {
433 panic("Hpts in goes negative inp:%p hpts:%p",
436 hpts->p_on_inqueue_cnt = 0;
439 if (TAILQ_EMPTY(&hpts->p_input) &&
440 (hpts->p_on_inqueue_cnt != 0)) {
441 /* We should not be empty with a queue count */
442 panic("%s hpts:%p in_hpts input empty but cnt:%d",
443 __FUNCTION__, hpts, hpts->p_on_inqueue_cnt);
447 inp->inp_in_input = 0;
451 hpts_sane_input_insert(struct tcp_hpts_entry *hpts, struct inpcb *inp, int line)
454 if (mtx_owned(&hpts->p_mtx) == 0) {
455 /* We don't own the mutex? */
456 panic("%s: hpts:%p inp:%p no hpts mutex", __FUNCTION__, hpts, inp);
458 if (hpts->p_cpu != inp->inp_input_cpu) {
459 /* It is not the right cpu/mutex? */
460 panic("%s: hpts:%p inp:%p incorrect CPU", __FUNCTION__, hpts, inp);
462 if (inp->inp_in_input == 1) {
463 /* We are already on the input hpts? */
464 panic("%s: hpts:%p inp:%p already on the input hpts?", __FUNCTION__, hpts, inp);
467 TAILQ_INSERT_TAIL(&hpts->p_input, inp, inp_input);
468 inp->inp_in_input = 1;
469 hpts->p_on_inqueue_cnt++;
474 tcp_wakehpts(struct tcp_hpts_entry *hpts)
476 HPTS_MTX_ASSERT(hpts);
477 if (hpts->p_hpts_wake_scheduled == 0) {
478 hpts->p_hpts_wake_scheduled = 1;
479 swi_sched(hpts->ie_cookie, 0);
484 tcp_wakeinput(struct tcp_hpts_entry *hpts)
486 HPTS_MTX_ASSERT(hpts);
487 if (hpts->p_hpts_wake_scheduled == 0) {
488 hpts->p_hpts_wake_scheduled = 1;
489 swi_sched(hpts->ie_cookie, 0);
493 struct tcp_hpts_entry *
494 tcp_cur_hpts(struct inpcb *inp)
497 struct tcp_hpts_entry *hpts;
499 hpts_num = inp->inp_hpts_cpu;
500 hpts = tcp_pace.rp_ent[hpts_num];
504 struct tcp_hpts_entry *
505 tcp_hpts_lock(struct inpcb *inp)
507 struct tcp_hpts_entry *hpts;
511 hpts_num = inp->inp_hpts_cpu;
512 hpts = tcp_pace.rp_ent[hpts_num];
514 if (mtx_owned(&hpts->p_mtx)) {
515 panic("Hpts:%p owns mtx prior-to lock line:%d",
519 mtx_lock(&hpts->p_mtx);
520 if (hpts_num != inp->inp_hpts_cpu) {
521 mtx_unlock(&hpts->p_mtx);
527 struct tcp_hpts_entry *
528 tcp_input_lock(struct inpcb *inp)
530 struct tcp_hpts_entry *hpts;
534 hpts_num = inp->inp_input_cpu;
535 hpts = tcp_pace.rp_ent[hpts_num];
537 if (mtx_owned(&hpts->p_mtx)) {
538 panic("Hpts:%p owns mtx prior-to lock line:%d",
542 mtx_lock(&hpts->p_mtx);
543 if (hpts_num != inp->inp_input_cpu) {
544 mtx_unlock(&hpts->p_mtx);
551 tcp_remove_hpts_ref(struct inpcb *inp, struct tcp_hpts_entry *hpts, int line)
555 if (inp->inp_flags2 & INP_FREED) {
557 * Need to play a special trick so that in_pcbrele_wlocked
558 * does not return 1 when it really should have returned 0.
561 inp->inp_flags2 &= ~INP_FREED;
565 #ifndef INP_REF_DEBUG
566 if (in_pcbrele_wlocked(inp)) {
568 * This should not happen. We have the inpcb referred to by
569 * the main socket (why we are called) and the hpts. It
570 * should always return 0.
572 panic("inpcb:%p release ret 1",
576 if (__in_pcbrele_wlocked(inp, line)) {
578 * This should not happen. We have the inpcb referred to by
579 * the main socket (why we are called) and the hpts. It
580 * should always return 0.
582 panic("inpcb:%p release ret 1",
587 inp->inp_flags2 |= INP_FREED;
592 tcp_hpts_remove_locked_output(struct tcp_hpts_entry *hpts, struct inpcb *inp, int32_t flags, int32_t line)
594 if (inp->inp_in_hpts) {
595 hpts_sane_pace_remove(hpts, inp, &hpts->p_hptss[inp->inp_hptsslot], 1);
596 tcp_remove_hpts_ref(inp, hpts, line);
601 tcp_hpts_remove_locked_input(struct tcp_hpts_entry *hpts, struct inpcb *inp, int32_t flags, int32_t line)
603 HPTS_MTX_ASSERT(hpts);
604 if (inp->inp_in_input) {
605 hpts_sane_input_remove(hpts, inp, 1);
606 tcp_remove_hpts_ref(inp, hpts, line);
611 * Called normally with the INP_LOCKED but it
612 * does not matter, the hpts lock is the key
613 * but the lock order allows us to hold the
614 * INP lock and then get the hpts lock.
616 * Valid values in the flags are
617 * HPTS_REMOVE_OUTPUT - remove from the output of the hpts.
618 * HPTS_REMOVE_INPUT - remove from the input of the hpts.
619 * Note that you can use one or both values together
620 * and get two actions.
623 __tcp_hpts_remove(struct inpcb *inp, int32_t flags, int32_t line)
625 struct tcp_hpts_entry *hpts;
627 INP_WLOCK_ASSERT(inp);
628 if (flags & HPTS_REMOVE_OUTPUT) {
629 hpts = tcp_hpts_lock(inp);
630 tcp_hpts_remove_locked_output(hpts, inp, flags, line);
631 mtx_unlock(&hpts->p_mtx);
633 if (flags & HPTS_REMOVE_INPUT) {
634 hpts = tcp_input_lock(inp);
635 tcp_hpts_remove_locked_input(hpts, inp, flags, line);
636 mtx_unlock(&hpts->p_mtx);
641 hpts_tick(uint32_t wheel_tick, uint32_t plus)
644 * Given a slot on the wheel, what slot
645 * is that plus ticks out?
647 KASSERT(wheel_tick < NUM_OF_HPTSI_SLOTS, ("Invalid tick %u not on wheel", wheel_tick));
648 return ((wheel_tick + plus) % NUM_OF_HPTSI_SLOTS);
652 tick_to_wheel(uint32_t cts_in_wticks)
655 * Given a timestamp in wheel ticks (10usec inc's)
656 * map it to our limited space wheel.
658 return (cts_in_wticks % NUM_OF_HPTSI_SLOTS);
662 hpts_ticks_diff(int prev_tick, int tick_now)
665 * Given two ticks that are someplace
666 * on our wheel. How far are they apart?
668 if (tick_now > prev_tick)
669 return (tick_now - prev_tick);
670 else if (tick_now == prev_tick)
672 * Special case, same means we can go all of our
673 * wheel less one slot.
675 return (NUM_OF_HPTSI_SLOTS - 1);
677 return ((NUM_OF_HPTSI_SLOTS - prev_tick) + tick_now);
681 * Given a tick on the wheel that is the current time
682 * mapped to the wheel (wheel_tick), what is the maximum
683 * distance forward that can be obtained without
684 * wrapping past either prev_tick or running_tick
685 * depending on the htps state? Also if passed
686 * a uint32_t *, fill it with the tick location.
688 * Note if you do not give this function the current
689 * time (that you think it is) mapped to the wheel
690 * then the results will not be what you expect and
691 * could lead to invalid inserts.
693 static inline int32_t
694 max_ticks_available(struct tcp_hpts_entry *hpts, uint32_t wheel_tick, uint32_t *target_tick)
696 uint32_t dis_to_travel, end_tick, pacer_to_now, avail_on_wheel;
698 if ((hpts->p_hpts_active == 1) &&
699 (hpts->p_wheel_complete == 0)) {
700 end_tick = hpts->p_runningtick;
701 /* Back up one tick */
703 end_tick = NUM_OF_HPTSI_SLOTS - 1;
707 *target_tick = end_tick;
710 * For the case where we are
711 * not active, or we have
712 * completed the pass over
713 * the wheel, we can use the
714 * prev tick and subtract one from it. This puts us
715 * as far out as possible on the wheel.
717 end_tick = hpts->p_prev_slot;
719 end_tick = NUM_OF_HPTSI_SLOTS - 1;
723 *target_tick = end_tick;
725 * Now we have close to the full wheel left minus the
726 * time it has been since the pacer went to sleep. Note
727 * that wheel_tick, passed in, should be the current time
728 * from the perspective of the caller, mapped to the wheel.
730 if (hpts->p_prev_slot != wheel_tick)
731 dis_to_travel = hpts_ticks_diff(hpts->p_prev_slot, wheel_tick);
735 * dis_to_travel in this case is the space from when the
736 * pacer stopped (p_prev_slot) and where our wheel_tick
737 * is now. To know how many slots we can put it in we
738 * subtract from the wheel size. We would not want
739 * to place something after p_prev_slot or it will
742 return (NUM_OF_HPTSI_SLOTS - dis_to_travel);
745 * So how many slots are open between p_runningtick -> p_cur_slot
746 * that is what is currently un-available for insertion. Special
747 * case when we are at the last slot, this gets 1, so that
748 * the answer to how many slots are available is all but 1.
750 if (hpts->p_runningtick == hpts->p_cur_slot)
753 dis_to_travel = hpts_ticks_diff(hpts->p_runningtick, hpts->p_cur_slot);
755 * How long has the pacer been running?
757 if (hpts->p_cur_slot != wheel_tick) {
758 /* The pacer is a bit late */
759 pacer_to_now = hpts_ticks_diff(hpts->p_cur_slot, wheel_tick);
761 /* The pacer is right on time, now == pacers start time */
765 * To get the number left we can insert into we simply
766 * subract the distance the pacer has to run from how
767 * many slots there are.
769 avail_on_wheel = NUM_OF_HPTSI_SLOTS - dis_to_travel;
771 * Now how many of those we will eat due to the pacer's
772 * time (p_cur_slot) of start being behind the
773 * real time (wheel_tick)?
775 if (avail_on_wheel <= pacer_to_now) {
777 * Wheel wrap, we can't fit on the wheel, that
778 * is unusual the system must be way overloaded!
779 * Insert into the assured tick, and return special
782 counter_u64_add(combined_wheel_wrap, 1);
783 *target_tick = hpts->p_nxt_slot;
787 * We know how many slots are open
788 * on the wheel (the reverse of what
789 * is left to run. Take away the time
790 * the pacer started to now (wheel_tick)
791 * and that tells you how many slots are
792 * open that can be inserted into that won't
793 * be touched by the pacer until later.
795 return (avail_on_wheel - pacer_to_now);
800 tcp_queue_to_hpts_immediate_locked(struct inpcb *inp, struct tcp_hpts_entry *hpts, int32_t line, int32_t noref)
802 uint32_t need_wake = 0;
804 HPTS_MTX_ASSERT(hpts);
805 if (inp->inp_in_hpts == 0) {
806 /* Ok we need to set it on the hpts in the current slot */
807 inp->inp_hpts_request = 0;
808 if ((hpts->p_hpts_active == 0) ||
809 (hpts->p_wheel_complete)) {
811 * A sleeping hpts we want in next slot to run
812 * note that in this state p_prev_slot == p_cur_slot
814 inp->inp_hptsslot = hpts_tick(hpts->p_prev_slot, 1);
815 if ((hpts->p_on_min_sleep == 0) && (hpts->p_hpts_active == 0))
817 } else if ((void *)inp == hpts->p_inp) {
819 * The hpts system is running and the caller
820 * was awoken by the hpts system.
821 * We can't allow you to go into the same slot we
822 * are in (we don't want a loop :-D).
824 inp->inp_hptsslot = hpts->p_nxt_slot;
826 inp->inp_hptsslot = hpts->p_runningtick;
827 hpts_sane_pace_insert(hpts, inp, &hpts->p_hptss[inp->inp_hptsslot], line, noref);
830 * Activate the hpts if it is sleeping and its
833 hpts->p_direct_wake = 1;
841 __tcp_queue_to_hpts_immediate(struct inpcb *inp, int32_t line)
844 struct tcp_hpts_entry *hpts;
846 INP_WLOCK_ASSERT(inp);
847 hpts = tcp_hpts_lock(inp);
848 ret = tcp_queue_to_hpts_immediate_locked(inp, hpts, line, 0);
849 mtx_unlock(&hpts->p_mtx);
855 check_if_slot_would_be_wrong(struct tcp_hpts_entry *hpts, struct inpcb *inp, uint32_t inp_hptsslot, int line)
858 * Sanity checks for the pacer with invariants
861 if (inp_hptsslot >= NUM_OF_HPTSI_SLOTS)
862 panic("hpts:%p inp:%p slot:%d > max",
863 hpts, inp, inp_hptsslot);
864 if ((hpts->p_hpts_active) &&
865 (hpts->p_wheel_complete == 0)) {
867 * If the pacer is processing a arc
868 * of the wheel, we need to make
869 * sure we are not inserting within
872 int distance, yet_to_run;
874 distance = hpts_ticks_diff(hpts->p_runningtick, inp_hptsslot);
875 if (hpts->p_runningtick != hpts->p_cur_slot)
876 yet_to_run = hpts_ticks_diff(hpts->p_runningtick, hpts->p_cur_slot);
878 yet_to_run = 0; /* processing last slot */
879 if (yet_to_run > distance) {
880 panic("hpts:%p inp:%p slot:%d distance:%d yet_to_run:%d rs:%d cs:%d",
881 hpts, inp, inp_hptsslot,
882 distance, yet_to_run,
883 hpts->p_runningtick, hpts->p_cur_slot);
890 tcp_hpts_insert_locked(struct tcp_hpts_entry *hpts, struct inpcb *inp, uint32_t slot, int32_t line,
891 struct hpts_diag *diag, struct timeval *tv)
893 uint32_t need_new_to = 0;
894 uint32_t wheel_cts, last_tick;
895 int32_t wheel_tick, maxticks;
896 int8_t need_wakeup = 0;
898 HPTS_MTX_ASSERT(hpts);
900 memset(diag, 0, sizeof(struct hpts_diag));
901 diag->p_hpts_active = hpts->p_hpts_active;
902 diag->p_prev_slot = hpts->p_prev_slot;
903 diag->p_runningtick = hpts->p_runningtick;
904 diag->p_nxt_slot = hpts->p_nxt_slot;
905 diag->p_cur_slot = hpts->p_cur_slot;
906 diag->p_curtick = hpts->p_curtick;
907 diag->p_lasttick = hpts->p_lasttick;
908 diag->slot_req = slot;
909 diag->p_on_min_sleep = hpts->p_on_min_sleep;
910 diag->hpts_sleep_time = hpts->p_hpts_sleep_time;
912 if (inp->inp_in_hpts == 0) {
915 tcp_queue_to_hpts_immediate_locked(inp, hpts, line, 0);
918 /* Get the current time relative to the wheel */
919 wheel_cts = tcp_tv_to_hptstick(tv);
920 /* Map it onto the wheel */
921 wheel_tick = tick_to_wheel(wheel_cts);
922 /* Now what's the max we can place it at? */
923 maxticks = max_ticks_available(hpts, wheel_tick, &last_tick);
925 diag->wheel_tick = wheel_tick;
926 diag->maxticks = maxticks;
927 diag->wheel_cts = wheel_cts;
930 /* The pacer is in a wheel wrap behind, yikes! */
933 * Reduce by 1 to prevent a forever loop in
934 * case something else is wrong. Note this
935 * probably does not hurt because the pacer
936 * if its true is so far behind we will be
937 * > 1second late calling anyway.
941 inp->inp_hptsslot = last_tick;
942 inp->inp_hpts_request = slot;
943 } else if (maxticks >= slot) {
944 /* It all fits on the wheel */
945 inp->inp_hpts_request = 0;
946 inp->inp_hptsslot = hpts_tick(wheel_tick, slot);
948 /* It does not fit */
949 inp->inp_hpts_request = slot - maxticks;
950 inp->inp_hptsslot = last_tick;
953 diag->slot_remaining = inp->inp_hpts_request;
954 diag->inp_hptsslot = inp->inp_hptsslot;
957 check_if_slot_would_be_wrong(hpts, inp, inp->inp_hptsslot, line);
959 hpts_sane_pace_insert(hpts, inp, &hpts->p_hptss[inp->inp_hptsslot], line, 0);
960 if ((hpts->p_hpts_active == 0) &&
961 (inp->inp_hpts_request == 0) &&
962 (hpts->p_on_min_sleep == 0)) {
964 * The hpts is sleeping and not on a minimum
965 * sleep time, we need to figure out where
966 * it will wake up at and if we need to reschedule
969 uint32_t have_slept, yet_to_sleep;
971 /* Now do we need to restart the hpts's timer? */
972 have_slept = hpts_ticks_diff(hpts->p_prev_slot, wheel_tick);
973 if (have_slept < hpts->p_hpts_sleep_time)
974 yet_to_sleep = hpts->p_hpts_sleep_time - have_slept;
976 /* We are over-due */
981 diag->have_slept = have_slept;
982 diag->yet_to_sleep = yet_to_sleep;
985 (yet_to_sleep > slot)) {
987 * We need to reschedule the hpts's time-out.
989 hpts->p_hpts_sleep_time = slot;
990 need_new_to = slot * HPTS_TICKS_PER_USEC;
994 * Now how far is the hpts sleeping to? if active is 1, its
995 * up and ticking we do nothing, otherwise we may need to
996 * reschedule its callout if need_new_to is set from above.
999 hpts->p_direct_wake = 1;
1002 diag->need_new_to = 0;
1003 diag->co_ret = 0xffff0000;
1005 } else if (need_new_to) {
1012 while (need_new_to > HPTS_USEC_IN_SEC) {
1014 need_new_to -= HPTS_USEC_IN_SEC;
1016 tv.tv_usec = need_new_to;
1018 if (tcp_hpts_callout_skip_swi == 0) {
1019 co_ret = callout_reset_sbt_on(&hpts->co, sb, 0,
1020 hpts_timeout_swi, hpts, hpts->p_cpu,
1021 (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
1023 co_ret = callout_reset_sbt_on(&hpts->co, sb, 0,
1024 hpts_timeout_dir, hpts,
1026 C_PREL(tcp_hpts_precision));
1029 diag->need_new_to = need_new_to;
1030 diag->co_ret = co_ret;
1035 panic("Hpts:%p tp:%p already on hpts and add?", hpts, inp);
1041 tcp_hpts_insert_diag(struct inpcb *inp, uint32_t slot, int32_t line, struct hpts_diag *diag)
1043 struct tcp_hpts_entry *hpts;
1048 * We now return the next-slot the hpts will be on, beyond its
1049 * current run (if up) or where it was when it stopped if it is
1052 INP_WLOCK_ASSERT(inp);
1053 hpts = tcp_hpts_lock(inp);
1055 tcp_hpts_insert_locked(hpts, inp, slot, line, diag, &tv);
1056 slot_on = hpts->p_nxt_slot;
1057 mtx_unlock(&hpts->p_mtx);
1062 __tcp_hpts_insert(struct inpcb *inp, uint32_t slot, int32_t line){
1063 return (tcp_hpts_insert_diag(inp, slot, line, NULL));
1066 __tcp_queue_to_input_locked(struct inpcb *inp, struct tcp_hpts_entry *hpts, int32_t line)
1070 HPTS_MTX_ASSERT(hpts);
1071 if (inp->inp_in_input == 0) {
1072 /* Ok we need to set it on the hpts in the current slot */
1073 hpts_sane_input_insert(hpts, inp, line);
1075 if (hpts->p_hpts_active == 0) {
1077 * Activate the hpts if it is sleeping.
1080 hpts->p_direct_wake = 1;
1081 tcp_wakeinput(hpts);
1083 } else if (hpts->p_hpts_active == 0) {
1085 hpts->p_direct_wake = 1;
1086 tcp_wakeinput(hpts);
1092 __tcp_queue_to_input(struct inpcb *inp, int line)
1094 struct tcp_hpts_entry *hpts;
1097 hpts = tcp_input_lock(inp);
1098 ret = __tcp_queue_to_input_locked(inp, hpts, line);
1099 mtx_unlock(&hpts->p_mtx);
1104 __tcp_set_inp_to_drop(struct inpcb *inp, uint16_t reason, int32_t line)
1106 struct tcp_hpts_entry *hpts;
1109 tp = intotcpcb(inp);
1110 hpts = tcp_input_lock(tp->t_inpcb);
1111 if (inp->inp_in_input == 0) {
1112 /* Ok we need to set it on the hpts in the current slot */
1113 hpts_sane_input_insert(hpts, inp, line);
1114 if (hpts->p_hpts_active == 0) {
1116 * Activate the hpts if it is sleeping.
1118 hpts->p_direct_wake = 1;
1119 tcp_wakeinput(hpts);
1121 } else if (hpts->p_hpts_active == 0) {
1122 hpts->p_direct_wake = 1;
1123 tcp_wakeinput(hpts);
1125 inp->inp_hpts_drop_reas = reason;
1126 mtx_unlock(&hpts->p_mtx);
1130 hpts_random_cpu(struct inpcb *inp){
1132 * No flow type set distribute the load randomly.
1138 * If one has been set use it i.e. we want both in and out on the
1141 if (inp->inp_input_cpu_set) {
1142 return (inp->inp_input_cpu);
1143 } else if (inp->inp_hpts_cpu_set) {
1144 return (inp->inp_hpts_cpu);
1146 /* Nothing set use a random number */
1148 cpuid = (ran & 0xffff) % mp_ncpus;
1153 hpts_cpuid(struct inpcb *inp){
1156 struct hpts_domain_info *di;
1160 * If one has been set use it i.e. we want both in and out on the
1163 if (inp->inp_input_cpu_set) {
1164 return (inp->inp_input_cpu);
1165 } else if (inp->inp_hpts_cpu_set) {
1166 return (inp->inp_hpts_cpu);
1168 /* If one is set the other must be the same */
1170 cpuid = rss_hash2cpuid(inp->inp_flowid, inp->inp_flowtype);
1171 if (cpuid == NETISR_CPUID_NONE)
1172 return (hpts_random_cpu(inp));
1177 * We don't have a flowid -> cpuid mapping, so cheat and just map
1178 * unknown cpuids to curcpu. Not the best, but apparently better
1179 * than defaulting to swi 0.
1182 if (inp->inp_flowtype == M_HASHTYPE_NONE)
1183 return (hpts_random_cpu(inp));
1185 * Hash to a thread based on the flowid. If we are using numa,
1186 * then restrict the hash to the numa domain where the inp lives.
1189 if (tcp_bind_threads == 2 && inp->inp_numa_domain != M_NODOM) {
1190 di = &hpts_domains[inp->inp_numa_domain];
1191 cpuid = di->cpu[inp->inp_flowid % di->count];
1194 cpuid = inp->inp_flowid % mp_ncpus;
1201 tcp_drop_in_pkts(struct tcpcb *tp)
1210 tp->t_in_pkt = NULL;
1220 * Do NOT try to optimize the processing of inp's
1221 * by first pulling off all the inp's into a temporary
1222 * list (e.g. TAILQ_CONCAT). If you do that the subtle
1223 * interactions of switching CPU's will kill because of
1224 * problems in the linked list manipulation. Basically
1225 * you would switch cpu's with the hpts mutex locked
1226 * but then while you were processing one of the inp's
1227 * some other one that you switch will get a new
1228 * packet on the different CPU. It will insert it
1229 * on the new hpts's input list. Creating a temporary
1230 * link in the inp will not fix it either, since
1231 * the other hpts will be doing the same thing and
1232 * you will both end up using the temporary link.
1234 * You will die in an ASSERT for tailq corruption if you
1235 * run INVARIANTS or you will die horribly without
1236 * INVARIANTS in some unknown way with a corrupt linked
1240 tcp_input_data(struct tcp_hpts_entry *hpts, struct timeval *tv)
1244 uint16_t drop_reason;
1246 uint32_t did_prefetch = 0;
1248 struct epoch_tracker et;
1250 HPTS_MTX_ASSERT(hpts);
1252 INP_INFO_RLOCK_ET(&V_tcbinfo, et);
1254 while ((inp = TAILQ_FIRST(&hpts->p_input)) != NULL) {
1255 HPTS_MTX_ASSERT(hpts);
1256 hpts_sane_input_remove(hpts, inp, 0);
1257 if (inp->inp_input_cpu_set == 0) {
1263 drop_reason = inp->inp_hpts_drop_reas;
1264 inp->inp_in_input = 0;
1265 mtx_unlock(&hpts->p_mtx);
1268 CURVNET_SET(inp->inp_vnet);
1269 INP_INFO_RLOCK_ET(&V_tcbinfo, et);
1271 if ((inp->inp_flags & (INP_TIMEWAIT | INP_DROPPED)) ||
1272 (inp->inp_flags2 & INP_FREED)) {
1275 if (in_pcbrele_wlocked(inp) == 0) {
1279 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1282 mtx_lock(&hpts->p_mtx);
1285 tp = intotcpcb(inp);
1286 if ((tp == NULL) || (tp->t_inpcb == NULL)) {
1290 /* This tcb is being destroyed for drop_reason */
1291 tcp_drop_in_pkts(tp);
1292 tp = tcp_drop(tp, drop_reason);
1296 if (in_pcbrele_wlocked(inp) == 0)
1299 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1302 mtx_lock(&hpts->p_mtx);
1307 * Setup so the next time we will move to the right
1308 * CPU. This should be a rare event. It will
1309 * sometimes happens when we are the client side
1310 * (usually not the server). Somehow tcp_output()
1311 * gets called before the tcp_do_segment() sets the
1312 * intial state. This means the r_cpu and r_hpts_cpu
1313 * is 0. We get on the hpts, and then tcp_input()
1314 * gets called setting up the r_cpu to the correct
1315 * value. The hpts goes off and sees the mis-match.
1316 * We simply correct it here and the CPU will switch
1317 * to the new hpts nextime the tcb gets added to the
1318 * the hpts (not this time) :-)
1322 if (tp->t_fb_ptr != NULL) {
1323 kern_prefetch(tp->t_fb_ptr, &did_prefetch);
1326 if ((inp->inp_flags2 & INP_SUPPORTS_MBUFQ) && tp->t_in_pkt) {
1327 if (inp->inp_in_input)
1328 tcp_hpts_remove(inp, HPTS_REMOVE_INPUT);
1329 dropped = (*tp->t_fb->tfb_do_queued_segments)(inp->inp_socket, tp, 0);
1331 /* Re-acquire the wlock so we can release the reference */
1334 } else if (tp->t_in_pkt) {
1336 * We reach here only if we had a
1337 * stack that supported INP_SUPPORTS_MBUFQ
1338 * and then somehow switched to a stack that
1339 * does not. The packets are basically stranded
1340 * and would hang with the connection until
1341 * cleanup without this code. Its not the
1342 * best way but I know of no other way to
1343 * handle it since the stack needs functions
1344 * it does not have to handle queued packets.
1346 tcp_drop_in_pkts(tp);
1348 if (in_pcbrele_wlocked(inp) == 0)
1350 INP_UNLOCK_ASSERT(inp);
1352 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1355 mtx_lock(&hpts->p_mtx);
1359 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1360 INP_INFO_UNLOCK_ASSERT(&V_tcbinfo);
1365 tcp_hptsi(struct tcp_hpts_entry *hpts)
1367 struct epoch_tracker et;
1369 struct inpcb *inp = NULL, *ninp;
1371 int32_t ticks_to_run, i, error;
1372 int32_t paced_cnt = 0;
1373 int32_t loop_cnt = 0;
1374 int32_t did_prefetch = 0;
1375 int32_t prefetch_ninp = 0;
1376 int32_t prefetch_tp = 0;
1377 int32_t wrap_loop_cnt = 0;
1380 HPTS_MTX_ASSERT(hpts);
1381 /* record previous info for any logging */
1382 hpts->saved_lasttick = hpts->p_lasttick;
1383 hpts->saved_curtick = hpts->p_curtick;
1384 hpts->saved_curslot = hpts->p_cur_slot;
1385 hpts->saved_prev_slot = hpts->p_prev_slot;
1387 hpts->p_lasttick = hpts->p_curtick;
1388 hpts->p_curtick = tcp_gethptstick(&tv);
1389 hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1390 if ((hpts->p_on_queue_cnt == 0) ||
1391 (hpts->p_lasttick == hpts->p_curtick)) {
1393 * No time has yet passed,
1396 hpts->p_prev_slot = hpts->p_cur_slot;
1397 hpts->p_lasttick = hpts->p_curtick;
1401 hpts->p_wheel_complete = 0;
1402 HPTS_MTX_ASSERT(hpts);
1403 ticks_to_run = hpts_ticks_diff(hpts->p_prev_slot, hpts->p_cur_slot);
1404 if (((hpts->p_curtick - hpts->p_lasttick) > ticks_to_run) &&
1405 (hpts->p_on_queue_cnt != 0)) {
1407 * Wheel wrap is occuring, basically we
1408 * are behind and the distance between
1409 * run's has spread so much it has exceeded
1410 * the time on the wheel (1.024 seconds). This
1411 * is ugly and should NOT be happening. We
1412 * need to run the entire wheel. We last processed
1413 * p_prev_slot, so that needs to be the last slot
1414 * we run. The next slot after that should be our
1415 * reserved first slot for new, and then starts
1416 * the running postion. Now the problem is the
1417 * reserved "not to yet" place does not exist
1418 * and there may be inp's in there that need
1419 * running. We can merge those into the
1420 * first slot at the head.
1423 hpts->p_nxt_slot = hpts_tick(hpts->p_prev_slot, 1);
1424 hpts->p_runningtick = hpts_tick(hpts->p_prev_slot, 2);
1426 * Adjust p_cur_slot to be where we are starting from
1427 * hopefully we will catch up (fat chance if something
1428 * is broken this bad :( )
1430 hpts->p_cur_slot = hpts->p_prev_slot;
1432 * The next slot has guys to run too, and that would
1433 * be where we would normally start, lets move them into
1434 * the next slot (p_prev_slot + 2) so that we will
1435 * run them, the extra 10usecs of late (by being
1436 * put behind) does not really matter in this situation.
1440 * To prevent a panic we need to update the inpslot to the
1441 * new location. This is safe since it takes both the
1442 * INP lock and the pacer mutex to change the inp_hptsslot.
1444 TAILQ_FOREACH(inp, &hpts->p_hptss[hpts->p_nxt_slot], inp_hpts) {
1445 inp->inp_hptsslot = hpts->p_runningtick;
1448 TAILQ_CONCAT(&hpts->p_hptss[hpts->p_runningtick],
1449 &hpts->p_hptss[hpts->p_nxt_slot], inp_hpts);
1450 ticks_to_run = NUM_OF_HPTSI_SLOTS - 1;
1451 counter_u64_add(wheel_wrap, 1);
1454 * Nxt slot is always one after p_runningtick though
1455 * its not used usually unless we are doing wheel wrap.
1457 hpts->p_nxt_slot = hpts->p_prev_slot;
1458 hpts->p_runningtick = hpts_tick(hpts->p_prev_slot, 1);
1461 if (TAILQ_EMPTY(&hpts->p_input) &&
1462 (hpts->p_on_inqueue_cnt != 0)) {
1463 panic("tp:%p in_hpts input empty but cnt:%d",
1464 hpts, hpts->p_on_inqueue_cnt);
1467 HPTS_MTX_ASSERT(hpts);
1468 if (hpts->p_on_queue_cnt == 0) {
1471 HPTS_MTX_ASSERT(hpts);
1473 INP_INFO_RLOCK_ET(&V_tcbinfo, et);
1475 for (i = 0; i < ticks_to_run; i++) {
1477 * Calculate our delay, if there are no extra ticks there
1478 * was not any (i.e. if ticks_to_run == 1, no delay).
1480 hpts->p_delayed_by = (ticks_to_run - (i + 1)) * HPTS_TICKS_PER_USEC;
1481 HPTS_MTX_ASSERT(hpts);
1482 while ((inp = TAILQ_FIRST(&hpts->p_hptss[hpts->p_runningtick])) != NULL) {
1487 if (hpts->p_runningtick != inp->inp_hptsslot) {
1488 panic("Hpts:%p inp:%p slot mis-aligned %u vs %u",
1489 hpts, inp, hpts->p_runningtick, inp->inp_hptsslot);
1493 if (inp->inp_hpts_cpu_set == 0) {
1498 hpts_sane_pace_remove(hpts, inp, &hpts->p_hptss[hpts->p_runningtick], 0);
1499 if ((ninp = TAILQ_FIRST(&hpts->p_hptss[hpts->p_runningtick])) != NULL) {
1500 /* We prefetch the next inp if possible */
1501 kern_prefetch(ninp, &prefetch_ninp);
1504 if (inp->inp_hpts_request) {
1506 * This guy is deferred out further in time
1507 * then our wheel had available on it.
1508 * Push him back on the wheel or run it
1511 uint32_t maxticks, last_tick, remaining_slots;
1513 remaining_slots = ticks_to_run - (i + 1);
1514 if (inp->inp_hpts_request > remaining_slots) {
1516 * How far out can we go?
1518 maxticks = max_ticks_available(hpts, hpts->p_cur_slot, &last_tick);
1519 if (maxticks >= inp->inp_hpts_request) {
1520 /* we can place it finally to be processed */
1521 inp->inp_hptsslot = hpts_tick(hpts->p_runningtick, inp->inp_hpts_request);
1522 inp->inp_hpts_request = 0;
1524 /* Work off some more time */
1525 inp->inp_hptsslot = last_tick;
1526 inp->inp_hpts_request-= maxticks;
1528 hpts_sane_pace_insert(hpts, inp, &hpts->p_hptss[inp->inp_hptsslot], __LINE__, 1);
1532 inp->inp_hpts_request = 0;
1533 /* Fall through we will so do it now */
1536 * We clear the hpts flag here after dealing with
1537 * remaining slots. This way anyone looking with the
1538 * TCB lock will see its on the hpts until just
1541 inp->inp_in_hpts = 0;
1542 mtx_unlock(&hpts->p_mtx);
1544 if (in_pcbrele_wlocked(inp)) {
1545 mtx_lock(&hpts->p_mtx);
1549 if ((inp->inp_flags & (INP_TIMEWAIT | INP_DROPPED)) ||
1550 (inp->inp_flags2 & INP_FREED)) {
1553 if (mtx_owned(&hpts->p_mtx)) {
1554 panic("Hpts:%p owns mtx prior-to lock line:%d",
1559 mtx_lock(&hpts->p_mtx);
1563 tp = intotcpcb(inp);
1564 if ((tp == NULL) || (tp->t_inpcb == NULL)) {
1569 * Setup so the next time we will move to
1570 * the right CPU. This should be a rare
1571 * event. It will sometimes happens when we
1572 * are the client side (usually not the
1573 * server). Somehow tcp_output() gets called
1574 * before the tcp_do_segment() sets the
1575 * intial state. This means the r_cpu and
1576 * r_hpts_cpu is 0. We get on the hpts, and
1577 * then tcp_input() gets called setting up
1578 * the r_cpu to the correct value. The hpts
1579 * goes off and sees the mis-match. We
1580 * simply correct it here and the CPU will
1581 * switch to the new hpts nextime the tcb
1582 * gets added to the the hpts (not this one)
1588 CURVNET_SET(inp->inp_vnet);
1589 INP_INFO_RLOCK_ET(&V_tcbinfo, et);
1591 /* Lets do any logging that we might want to */
1592 if (hpts_does_tp_logging && (tp->t_logstate != TCP_LOG_STATE_OFF)) {
1593 tcp_hpts_log(hpts, tp, &tv, ticks_to_run, i);
1596 * There is a hole here, we get the refcnt on the
1597 * inp so it will still be preserved but to make
1598 * sure we can get the INP we need to hold the p_mtx
1599 * above while we pull out the tp/inp, as long as
1600 * fini gets the lock first we are assured of having
1601 * a sane INP we can lock and test.
1604 if (mtx_owned(&hpts->p_mtx)) {
1605 panic("Hpts:%p owns mtx before tcp-output:%d",
1609 if (tp->t_fb_ptr != NULL) {
1610 kern_prefetch(tp->t_fb_ptr, &did_prefetch);
1613 if ((inp->inp_flags2 & INP_SUPPORTS_MBUFQ) && tp->t_in_pkt) {
1614 error = (*tp->t_fb->tfb_do_queued_segments)(inp->inp_socket, tp, 0);
1616 /* The input killed the connection */
1620 inp->inp_hpts_calls = 1;
1621 error = tp->t_fb->tfb_tcp_output(tp);
1622 inp->inp_hpts_calls = 0;
1623 if (ninp && ninp->inp_ppcb) {
1625 * If we have a nxt inp, see if we can
1626 * prefetch its ppcb. Note this may seem
1627 * "risky" since we have no locks (other
1628 * than the previous inp) and there no
1629 * assurance that ninp was not pulled while
1630 * we were processing inp and freed. If this
1631 * occured it could mean that either:
1633 * a) Its NULL (which is fine we won't go
1634 * here) <or> b) Its valid (which is cool we
1635 * will prefetch it) <or> c) The inp got
1636 * freed back to the slab which was
1637 * reallocated. Then the piece of memory was
1638 * re-used and something else (not an
1639 * address) is in inp_ppcb. If that occurs
1640 * we don't crash, but take a TLB shootdown
1641 * performance hit (same as if it was NULL
1642 * and we tried to pre-fetch it).
1644 * Considering that the likelyhood of <c> is
1645 * quite rare we will take a risk on doing
1646 * this. If performance drops after testing
1647 * we can always take this out. NB: the
1648 * kern_prefetch on amd64 actually has
1649 * protection against a bad address now via
1650 * the DMAP_() tests. This will prevent the
1651 * TLB hit, and instead if <c> occurs just
1652 * cause us to load cache with a useless
1655 kern_prefetch(ninp->inp_ppcb, &prefetch_tp);
1661 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1664 INP_UNLOCK_ASSERT(inp);
1666 if (mtx_owned(&hpts->p_mtx)) {
1667 panic("Hpts:%p owns mtx prior-to lock line:%d",
1671 mtx_lock(&hpts->p_mtx);
1674 HPTS_MTX_ASSERT(hpts);
1676 hpts->p_runningtick++;
1677 if (hpts->p_runningtick >= NUM_OF_HPTSI_SLOTS) {
1678 hpts->p_runningtick = 0;
1682 INP_INFO_RUNLOCK_ET(&V_tcbinfo, et);
1685 HPTS_MTX_ASSERT(hpts);
1686 hpts->p_delayed_by = 0;
1688 * Check to see if we took an excess amount of time and need to run
1689 * more ticks (if we did not hit eno-bufs).
1692 if (TAILQ_EMPTY(&hpts->p_input) &&
1693 (hpts->p_on_inqueue_cnt != 0)) {
1694 panic("tp:%p in_hpts input empty but cnt:%d",
1695 hpts, hpts->p_on_inqueue_cnt);
1698 hpts->p_prev_slot = hpts->p_cur_slot;
1699 hpts->p_lasttick = hpts->p_curtick;
1700 if (loop_cnt > max_pacer_loops) {
1702 * Something is serious slow we have
1703 * looped through processing the wheel
1704 * and by the time we cleared the
1705 * needs to run max_pacer_loops time
1706 * we still needed to run. That means
1707 * the system is hopelessly behind and
1708 * can never catch up :(
1710 * We will just lie to this thread
1711 * and let it thing p_curtick is
1712 * correct. When it next awakens
1713 * it will find itself further behind.
1715 counter_u64_add(hpts_hopelessly_behind, 1);
1718 hpts->p_curtick = tcp_gethptstick(&tv);
1719 hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1720 if ((wrap_loop_cnt < 2) &&
1721 (hpts->p_lasttick != hpts->p_curtick)) {
1722 counter_u64_add(hpts_loops, 1);
1728 * Set flag to tell that we are done for
1729 * any slot input that happens during
1732 hpts->p_wheel_complete = 1;
1734 * Run any input that may be there not covered
1737 if (!TAILQ_EMPTY(&hpts->p_input)) {
1738 tcp_input_data(hpts, &tv);
1740 * Now did we spend too long running
1741 * input and need to run more ticks?
1743 KASSERT(hpts->p_prev_slot == hpts->p_cur_slot,
1744 ("H:%p p_prev_slot:%u not equal to p_cur_slot:%u", hpts,
1745 hpts->p_prev_slot, hpts->p_cur_slot));
1746 KASSERT(hpts->p_lasttick == hpts->p_curtick,
1747 ("H:%p p_lasttick:%u not equal to p_curtick:%u", hpts,
1748 hpts->p_lasttick, hpts->p_curtick));
1749 hpts->p_curtick = tcp_gethptstick(&tv);
1750 if (hpts->p_lasttick != hpts->p_curtick) {
1751 counter_u64_add(hpts_loops, 1);
1752 hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1757 uint32_t t = 0, i, fnd = 0;
1759 if ((hpts->p_on_queue_cnt) && (wrap_loop_cnt < 2)) {
1761 * Find next slot that is occupied and use that to
1762 * be the sleep time.
1764 for (i = 0, t = hpts_tick(hpts->p_cur_slot, 1); i < NUM_OF_HPTSI_SLOTS; i++) {
1765 if (TAILQ_EMPTY(&hpts->p_hptss[t]) == 0) {
1769 t = (t + 1) % NUM_OF_HPTSI_SLOTS;
1772 hpts->p_hpts_sleep_time = min((i + 1), hpts_sleep_max);
1775 panic("Hpts:%p cnt:%d but none found", hpts, hpts->p_on_queue_cnt);
1777 counter_u64_add(back_tosleep, 1);
1778 hpts->p_on_queue_cnt = 0;
1781 } else if (wrap_loop_cnt >= 2) {
1782 /* Special case handling */
1783 hpts->p_hpts_sleep_time = tcp_min_hptsi_time;
1785 /* No one on the wheel sleep for all but 400 slots or sleep max */
1787 hpts->p_hpts_sleep_time = hpts_sleep_max;
1793 __tcp_set_hpts(struct inpcb *inp, int32_t line)
1795 struct tcp_hpts_entry *hpts;
1797 INP_WLOCK_ASSERT(inp);
1798 hpts = tcp_hpts_lock(inp);
1799 if ((inp->inp_in_hpts == 0) &&
1800 (inp->inp_hpts_cpu_set == 0)) {
1801 inp->inp_hpts_cpu = hpts_cpuid(inp);
1802 inp->inp_hpts_cpu_set = 1;
1804 mtx_unlock(&hpts->p_mtx);
1805 hpts = tcp_input_lock(inp);
1806 if ((inp->inp_input_cpu_set == 0) &&
1807 (inp->inp_in_input == 0)) {
1808 inp->inp_input_cpu = hpts_cpuid(inp);
1809 inp->inp_input_cpu_set = 1;
1811 mtx_unlock(&hpts->p_mtx);
1815 tcp_hpts_delayedby(struct inpcb *inp){
1816 return (tcp_pace.rp_ent[inp->inp_hpts_cpu]->p_delayed_by);
1820 tcp_hpts_thread(void *ctx)
1822 struct tcp_hpts_entry *hpts;
1826 hpts = (struct tcp_hpts_entry *)ctx;
1827 mtx_lock(&hpts->p_mtx);
1828 if (hpts->p_direct_wake) {
1829 /* Signaled by input */
1830 callout_stop(&hpts->co);
1833 if (callout_pending(&hpts->co) ||
1834 !callout_active(&hpts->co)) {
1835 mtx_unlock(&hpts->p_mtx);
1838 callout_deactivate(&hpts->co);
1840 hpts->p_hpts_wake_scheduled = 0;
1841 hpts->p_hpts_active = 1;
1843 HPTS_MTX_ASSERT(hpts);
1845 tv.tv_usec = hpts->p_hpts_sleep_time * HPTS_TICKS_PER_USEC;
1846 if (tcp_min_hptsi_time && (tv.tv_usec < tcp_min_hptsi_time)) {
1847 hpts->overidden_sleep = tv.tv_usec;
1848 tv.tv_usec = tcp_min_hptsi_time;
1849 hpts->p_on_min_sleep = 1;
1851 /* Clear the min sleep flag */
1852 hpts->overidden_sleep = 0;
1853 hpts->p_on_min_sleep = 0;
1855 hpts->p_hpts_active = 0;
1857 if (tcp_hpts_callout_skip_swi == 0) {
1858 callout_reset_sbt_on(&hpts->co, sb, 0,
1859 hpts_timeout_swi, hpts, hpts->p_cpu,
1860 (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
1862 callout_reset_sbt_on(&hpts->co, sb, 0,
1863 hpts_timeout_dir, hpts,
1865 C_PREL(tcp_hpts_precision));
1867 hpts->p_direct_wake = 0;
1868 mtx_unlock(&hpts->p_mtx);
1874 tcp_init_hptsi(void *st)
1876 int32_t i, j, error, bound = 0, created = 0;
1880 struct tcp_hpts_entry *hpts;
1884 uint32_t ncpus = mp_ncpus ? mp_ncpus : MAXCPU;
1887 tcp_pace.rp_proc = NULL;
1888 tcp_pace.rp_num_hptss = ncpus;
1889 hpts_hopelessly_behind = counter_u64_alloc(M_WAITOK);
1890 hpts_loops = counter_u64_alloc(M_WAITOK);
1891 back_tosleep = counter_u64_alloc(M_WAITOK);
1892 combined_wheel_wrap = counter_u64_alloc(M_WAITOK);
1893 wheel_wrap = counter_u64_alloc(M_WAITOK);
1894 sz = (tcp_pace.rp_num_hptss * sizeof(struct tcp_hpts_entry *));
1895 tcp_pace.rp_ent = malloc(sz, M_TCPHPTS, M_WAITOK | M_ZERO);
1896 asz = sizeof(struct hptsh) * NUM_OF_HPTSI_SLOTS;
1897 for (i = 0; i < tcp_pace.rp_num_hptss; i++) {
1898 tcp_pace.rp_ent[i] = malloc(sizeof(struct tcp_hpts_entry),
1899 M_TCPHPTS, M_WAITOK | M_ZERO);
1900 tcp_pace.rp_ent[i]->p_hptss = malloc(asz,
1901 M_TCPHPTS, M_WAITOK);
1902 hpts = tcp_pace.rp_ent[i];
1904 * Init all the hpts structures that are not specifically
1905 * zero'd by the allocations. Also lets attach them to the
1906 * appropriate sysctl block as well.
1908 mtx_init(&hpts->p_mtx, "tcp_hpts_lck",
1909 "hpts", MTX_DEF | MTX_DUPOK);
1910 TAILQ_INIT(&hpts->p_input);
1911 for (j = 0; j < NUM_OF_HPTSI_SLOTS; j++) {
1912 TAILQ_INIT(&hpts->p_hptss[j]);
1914 sysctl_ctx_init(&hpts->hpts_ctx);
1915 sprintf(unit, "%d", i);
1916 hpts->hpts_root = SYSCTL_ADD_NODE(&hpts->hpts_ctx,
1917 SYSCTL_STATIC_CHILDREN(_net_inet_tcp_hpts),
1922 SYSCTL_ADD_INT(&hpts->hpts_ctx,
1923 SYSCTL_CHILDREN(hpts->hpts_root),
1924 OID_AUTO, "in_qcnt", CTLFLAG_RD,
1925 &hpts->p_on_inqueue_cnt, 0,
1926 "Count TCB's awaiting input processing");
1927 SYSCTL_ADD_INT(&hpts->hpts_ctx,
1928 SYSCTL_CHILDREN(hpts->hpts_root),
1929 OID_AUTO, "out_qcnt", CTLFLAG_RD,
1930 &hpts->p_on_queue_cnt, 0,
1931 "Count TCB's awaiting output processing");
1932 SYSCTL_ADD_U16(&hpts->hpts_ctx,
1933 SYSCTL_CHILDREN(hpts->hpts_root),
1934 OID_AUTO, "active", CTLFLAG_RD,
1935 &hpts->p_hpts_active, 0,
1936 "Is the hpts active");
1937 SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1938 SYSCTL_CHILDREN(hpts->hpts_root),
1939 OID_AUTO, "curslot", CTLFLAG_RD,
1940 &hpts->p_cur_slot, 0,
1941 "What the current running pacers goal");
1942 SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1943 SYSCTL_CHILDREN(hpts->hpts_root),
1944 OID_AUTO, "runtick", CTLFLAG_RD,
1945 &hpts->p_runningtick, 0,
1946 "What the running pacers current slot is");
1947 SYSCTL_ADD_UINT(&hpts->hpts_ctx,
1948 SYSCTL_CHILDREN(hpts->hpts_root),
1949 OID_AUTO, "curtick", CTLFLAG_RD,
1950 &hpts->p_curtick, 0,
1951 "What the running pacers last tick mapped to the wheel was");
1952 hpts->p_hpts_sleep_time = hpts_sleep_max;
1954 hpts->p_curtick = tcp_gethptstick(&tv);
1955 hpts->p_prev_slot = hpts->p_cur_slot = tick_to_wheel(hpts->p_curtick);
1956 hpts->p_cpu = 0xffff;
1957 hpts->p_nxt_slot = hpts_tick(hpts->p_cur_slot, 1);
1958 callout_init(&hpts->co, 1);
1961 /* Don't try to bind to NUMA domains if we don't have any */
1962 if (vm_ndomains == 1 && tcp_bind_threads == 2)
1963 tcp_bind_threads = 0;
1966 * Now lets start ithreads to handle the hptss.
1969 hpts = tcp_pace.rp_ent[i];
1971 error = swi_add(&hpts->ie, "hpts",
1972 tcp_hpts_thread, (void *)hpts,
1973 SWI_NET, INTR_MPSAFE, &hpts->ie_cookie);
1975 panic("Can't add hpts:%p i:%d err:%d",
1979 if (tcp_bind_threads == 1) {
1980 if (intr_event_bind(hpts->ie, i) == 0)
1982 } else if (tcp_bind_threads == 2) {
1984 domain = pc->pc_domain;
1985 CPU_COPY(&cpuset_domain[domain], &cs);
1986 if (intr_event_bind_ithread_cpuset(hpts->ie, &cs)
1989 count = hpts_domains[domain].count;
1990 hpts_domains[domain].cpu[count] = i;
1991 hpts_domains[domain].count++;
1995 tv.tv_usec = hpts->p_hpts_sleep_time * HPTS_TICKS_PER_USEC;
1997 if (tcp_hpts_callout_skip_swi == 0) {
1998 callout_reset_sbt_on(&hpts->co, sb, 0,
1999 hpts_timeout_swi, hpts, hpts->p_cpu,
2000 (C_DIRECT_EXEC | C_PREL(tcp_hpts_precision)));
2002 callout_reset_sbt_on(&hpts->co, sb, 0,
2003 hpts_timeout_dir, hpts,
2005 C_PREL(tcp_hpts_precision));
2009 * If we somehow have an empty domain, fall back to choosing
2010 * among all htps threads.
2012 for (i = 0; i < vm_ndomains; i++) {
2013 if (hpts_domains[i].count == 0) {
2014 tcp_bind_threads = 0;
2019 printf("TCP Hpts created %d swi interrupt threads and bound %d to %s\n",
2021 tcp_bind_threads == 2 ? "NUMA domains" : "cpus");
2024 SYSINIT(tcphptsi, SI_SUB_KTHREAD_IDLE, SI_ORDER_ANY, tcp_init_hptsi, NULL);
2025 MODULE_VERSION(tcphpts, 1);