123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527 |
- #include <linux/mm.h>
- #include <linux/module.h>
- #include <linux/math64.h>
- #include <net/tcp.h>
- #define BICTCP_BETA_SCALE 1024
- #define BICTCP_HZ 10
- #define HYSTART_ACK_TRAIN 0x1
- #define HYSTART_DELAY 0x2
- #define HYSTART_MIN_SAMPLES 8
- #define HYSTART_DELAY_MIN (4U<<3)
- #define HYSTART_DELAY_MAX (16U<<3)
- #define HYSTART_DELAY_THRESH(x) clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
- static int fast_convergence __read_mostly = 1;
- static int beta __read_mostly = 717; /* = 717/1024 (BICTCP_BETA_SCALE) */
- static int initial_ssthresh __read_mostly;
- static int bic_scale __read_mostly = 41;
- static int tcp_friendliness __read_mostly = 1;
- static int hystart __read_mostly = 1;
- static int hystart_detect __read_mostly = HYSTART_ACK_TRAIN | HYSTART_DELAY;
- static int hystart_low_window __read_mostly = 16;
- static int hystart_ack_delta __read_mostly = 2;
- static u32 cube_rtt_scale __read_mostly;
- static u32 beta_scale __read_mostly;
- static u64 cube_factor __read_mostly;
- /* Note parameters that are used for precomputing scale factors are read-only */
- module_param(fast_convergence, int, 0644);
- MODULE_PARM_DESC(fast_convergence, "turn on/off fast convergence");
- module_param(beta, int, 0644);
- MODULE_PARM_DESC(beta, "beta for multiplicative increase");
- module_param(initial_ssthresh, int, 0644);
- MODULE_PARM_DESC(initial_ssthresh, "initial value of slow start threshold");
- module_param(bic_scale, int, 0444);
- MODULE_PARM_DESC(bic_scale, "scale (scaled by 1024) value for bic function (bic_scale/1024)");
- module_param(tcp_friendliness, int, 0644);
- MODULE_PARM_DESC(tcp_friendliness, "turn on/off tcp friendliness");
- module_param(hystart, int, 0644);
- MODULE_PARM_DESC(hystart, "turn on/off hybrid slow start algorithm");
- module_param(hystart_detect, int, 0644);
- MODULE_PARM_DESC(hystart_detect, "hyrbrid slow start detection mechanisms"
- " 1: packet-train 2: delay 3: both packet-train and delay");
- module_param(hystart_low_window, int, 0644);
- MODULE_PARM_DESC(hystart_low_window, "lower bound cwnd for hybrid slow start");
- module_param(hystart_ack_delta, int, 0644);
- MODULE_PARM_DESC(hystart_ack_delta, "spacing between ack's indicating train (msecs)");
- /* BIC TCP Parameters */
- struct bictcp {
- u32 cnt; /* increase cwnd by 1 after ACKs */
- u32 last_max_cwnd; /* last maximum snd_cwnd */
- u32 loss_cwnd; /* congestion window at last loss */
- u32 last_cwnd; /* the last snd_cwnd */
- u32 last_time; /* time when updated last_cwnd */
- u32 bic_origin_point;/* origin point of bic function */
- u32 bic_K; /* time to origin point
- from the beginning of the current epoch */
- u32 delay_min; /* min delay (msec << 3) */
- u32 epoch_start; /* beginning of an epoch */
- u32 ack_cnt; /* number of acks */
- u32 tcp_cwnd; /* estimated tcp cwnd */
- u16 unused;
- u8 sample_cnt; /* number of samples to decide curr_rtt */
- u8 found; /* the exit point is found? */
- u32 round_start; /* beginning of each round */
- u32 end_seq; /* end_seq of the round */
- u32 last_ack; /* last time when the ACK spacing is close */
- u32 curr_rtt; /* the minimum rtt of current round */
- };
- static inline void bictcp_reset(struct bictcp *ca)
- {
- ca->cnt = 0;
- ca->last_max_cwnd = 0;
- ca->last_cwnd = 0;
- ca->last_time = 0;
- ca->bic_origin_point = 0;
- ca->bic_K = 0;
- ca->delay_min = 0;
- ca->epoch_start = 0;
- ca->ack_cnt = 0;
- ca->tcp_cwnd = 0;
- ca->found = 0;
- }
- static inline u32 bictcp_clock(void)
- {
- #if HZ < 1000
- return ktime_to_ms(ktime_get_real());
- #else
- return jiffies_to_msecs(jiffies);
- #endif
- }
- static inline void bictcp_hystart_reset(struct sock *sk)
- {
- struct tcp_sock *tp = tcp_sk(sk);
- struct bictcp *ca = inet_csk_ca(sk);
- ca->round_start = ca->last_ack = bictcp_clock();
- ca->end_seq = tp->snd_nxt;
- ca->curr_rtt = 0;
- ca->sample_cnt = 0;
- }
- static void bictcp_init(struct sock *sk)
- {
- struct bictcp *ca = inet_csk_ca(sk);
- bictcp_reset(ca);
- ca->loss_cwnd = 0;
- if (hystart)
- bictcp_hystart_reset(sk);
- if (!hystart && initial_ssthresh)
- tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
- }
- static void bictcp_cwnd_event(struct sock *sk, enum tcp_ca_event event)
- {
- if (event == CA_EVENT_TX_START) {
- struct bictcp *ca = inet_csk_ca(sk);
- u32 now = tcp_time_stamp;
- s32 delta;
- delta = now - tcp_sk(sk)->lsndtime;
-
- if (ca->epoch_start && delta > 0) {
- ca->epoch_start += delta;
- if (after(ca->epoch_start, now))
- ca->epoch_start = now;
- }
- return;
- }
- }
- static u32 cubic_root(u64 a)
- {
- u32 x, b, shift;
-
- static const u8 v[] = {
- 0, 54, 54, 54, 118, 118, 118, 118,
- 123, 129, 134, 138, 143, 147, 151, 156,
- 157, 161, 164, 168, 170, 173, 176, 179,
- 181, 185, 187, 190, 192, 194, 197, 199,
- 200, 202, 204, 206, 209, 211, 213, 215,
- 217, 219, 221, 222, 224, 225, 227, 229,
- 231, 232, 234, 236, 237, 239, 240, 242,
- 244, 245, 246, 248, 250, 251, 252, 254,
- };
- b = fls64(a);
- if (b < 7) {
-
- return ((u32)v[(u32)a] + 35) >> 6;
- }
- b = ((b * 84) >> 8) - 1;
- shift = (a >> (b * 3));
- x = ((u32)(((u32)v[shift] + 10) << b)) >> 6;
-
- x = (2 * x + (u32)div64_u64(a, (u64)x * (u64)(x - 1)));
- x = ((x * 341) >> 10);
- return x;
- }
- static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
- {
- u32 delta, bic_target, max_cnt;
- u64 offs, t;
- ca->ack_cnt += acked;
- if (ca->last_cwnd == cwnd &&
- (s32)(tcp_time_stamp - ca->last_time) <= HZ / 32)
- return;
-
- if (ca->epoch_start && tcp_time_stamp == ca->last_time)
- goto tcp_friendliness;
- ca->last_cwnd = cwnd;
- ca->last_time = tcp_time_stamp;
- if (ca->epoch_start == 0) {
- ca->epoch_start = tcp_time_stamp;
- ca->ack_cnt = acked;
- ca->tcp_cwnd = cwnd;
- if (ca->last_max_cwnd <= cwnd) {
- ca->bic_K = 0;
- ca->bic_origin_point = cwnd;
- } else {
-
- ca->bic_K = cubic_root(cube_factor
- * (ca->last_max_cwnd - cwnd));
- ca->bic_origin_point = ca->last_max_cwnd;
- }
- }
-
-
- t = (s32)(tcp_time_stamp - ca->epoch_start);
- t += msecs_to_jiffies(ca->delay_min >> 3);
-
- t <<= BICTCP_HZ;
- do_div(t, HZ);
- if (t < ca->bic_K)
- offs = ca->bic_K - t;
- else
- offs = t - ca->bic_K;
-
- delta = (cube_rtt_scale * offs * offs * offs) >> (10+3*BICTCP_HZ);
- if (t < ca->bic_K)
- bic_target = ca->bic_origin_point - delta;
- else
- bic_target = ca->bic_origin_point + delta;
-
- if (bic_target > cwnd) {
- ca->cnt = cwnd / (bic_target - cwnd);
- } else {
- ca->cnt = 100 * cwnd;
- }
-
- if (ca->last_max_cwnd == 0 && ca->cnt > 20)
- ca->cnt = 20;
- tcp_friendliness:
-
- if (tcp_friendliness) {
- u32 scale = beta_scale;
- delta = (cwnd * scale) >> 3;
- while (ca->ack_cnt > delta) {
- ca->ack_cnt -= delta;
- ca->tcp_cwnd++;
- }
- if (ca->tcp_cwnd > cwnd) {
- delta = ca->tcp_cwnd - cwnd;
- max_cnt = cwnd / delta;
- if (ca->cnt > max_cnt)
- ca->cnt = max_cnt;
- }
- }
-
- ca->cnt = max(ca->cnt, 2U);
- }
- static void bictcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
- {
- struct tcp_sock *tp = tcp_sk(sk);
- struct bictcp *ca = inet_csk_ca(sk);
- if (!tcp_is_cwnd_limited(sk))
- return;
- if (tcp_in_slow_start(tp)) {
- if (hystart && after(ack, ca->end_seq))
- bictcp_hystart_reset(sk);
- acked = tcp_slow_start(tp, acked);
- if (!acked)
- return;
- }
- bictcp_update(ca, tp->snd_cwnd, acked);
- tcp_cong_avoid_ai(tp, ca->cnt, acked);
- }
- static u32 bictcp_recalc_ssthresh(struct sock *sk)
- {
- const struct tcp_sock *tp = tcp_sk(sk);
- struct bictcp *ca = inet_csk_ca(sk);
- ca->epoch_start = 0;
-
- if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence)
- ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta))
- / (2 * BICTCP_BETA_SCALE);
- else
- ca->last_max_cwnd = tp->snd_cwnd;
- ca->loss_cwnd = tp->snd_cwnd;
- return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U);
- }
- static u32 bictcp_undo_cwnd(struct sock *sk)
- {
- struct bictcp *ca = inet_csk_ca(sk);
- return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd);
- }
- static void bictcp_state(struct sock *sk, u8 new_state)
- {
- if (new_state == TCP_CA_Loss) {
- bictcp_reset(inet_csk_ca(sk));
- bictcp_hystart_reset(sk);
- }
- }
- static void hystart_update(struct sock *sk, u32 delay)
- {
- struct tcp_sock *tp = tcp_sk(sk);
- struct bictcp *ca = inet_csk_ca(sk);
- if (ca->found & hystart_detect)
- return;
- if (hystart_detect & HYSTART_ACK_TRAIN) {
- u32 now = bictcp_clock();
-
- if ((s32)(now - ca->last_ack) <= hystart_ack_delta) {
- ca->last_ack = now;
- if ((s32)(now - ca->round_start) > ca->delay_min >> 4) {
- ca->found |= HYSTART_ACK_TRAIN;
- NET_INC_STATS(sock_net(sk),
- LINUX_MIB_TCPHYSTARTTRAINDETECT);
- NET_ADD_STATS(sock_net(sk),
- LINUX_MIB_TCPHYSTARTTRAINCWND,
- tp->snd_cwnd);
- tp->snd_ssthresh = tp->snd_cwnd;
- }
- }
- }
- if (hystart_detect & HYSTART_DELAY) {
-
- if (ca->sample_cnt < HYSTART_MIN_SAMPLES) {
- if (ca->curr_rtt == 0 || ca->curr_rtt > delay)
- ca->curr_rtt = delay;
- ca->sample_cnt++;
- } else {
- if (ca->curr_rtt > ca->delay_min +
- HYSTART_DELAY_THRESH(ca->delay_min >> 3)) {
- ca->found |= HYSTART_DELAY;
- NET_INC_STATS(sock_net(sk),
- LINUX_MIB_TCPHYSTARTDELAYDETECT);
- NET_ADD_STATS(sock_net(sk),
- LINUX_MIB_TCPHYSTARTDELAYCWND,
- tp->snd_cwnd);
- tp->snd_ssthresh = tp->snd_cwnd;
- }
- }
- }
- }
- static void bictcp_acked(struct sock *sk, const struct ack_sample *sample)
- {
- const struct tcp_sock *tp = tcp_sk(sk);
- struct bictcp *ca = inet_csk_ca(sk);
- u32 delay;
-
- if (sample->rtt_us < 0)
- return;
-
- if (ca->epoch_start && (s32)(tcp_time_stamp - ca->epoch_start) < HZ)
- return;
- delay = (sample->rtt_us << 3) / USEC_PER_MSEC;
- if (delay == 0)
- delay = 1;
-
- if (ca->delay_min == 0 || ca->delay_min > delay)
- ca->delay_min = delay;
-
- if (hystart && tcp_in_slow_start(tp) &&
- tp->snd_cwnd >= hystart_low_window)
- hystart_update(sk, delay);
- }
- static struct tcp_congestion_ops cubictcp __read_mostly = {
- .init = bictcp_init,
- .ssthresh = bictcp_recalc_ssthresh,
- .cong_avoid = bictcp_cong_avoid,
- .set_state = bictcp_state,
- .undo_cwnd = bictcp_undo_cwnd,
- .cwnd_event = bictcp_cwnd_event,
- .pkts_acked = bictcp_acked,
- .owner = THIS_MODULE,
- .name = "cubic",
- };
- static int __init cubictcp_register(void)
- {
- BUILD_BUG_ON(sizeof(struct bictcp) > ICSK_CA_PRIV_SIZE);
-
- beta_scale = 8*(BICTCP_BETA_SCALE+beta) / 3
- / (BICTCP_BETA_SCALE - beta);
- cube_rtt_scale = (bic_scale * 10);
-
-
- cube_factor = 1ull << (10+3*BICTCP_HZ);
-
- do_div(cube_factor, bic_scale * 10);
- return tcp_register_congestion_control(&cubictcp);
- }
- static void __exit cubictcp_unregister(void)
- {
- tcp_unregister_congestion_control(&cubictcp);
- }
- module_init(cubictcp_register);
- module_exit(cubictcp_unregister);
- MODULE_AUTHOR("Sangtae Ha, Stephen Hemminger");
- MODULE_LICENSE("GPL");
- MODULE_DESCRIPTION("CUBIC TCP");
- MODULE_VERSION("2.3");
|