/* * Copyright (c) 2019 Cisco and/or its affiliates. * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at: * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * TCP byte tracker that can generate delivery rate estimates. Based on * draft-cheng-iccrg-delivery-rate-estimation-00 */ #include #include #include static tcp_bt_sample_t * bt_get_sample (tcp_byte_tracker_t * bt, u32 bts_index) { if (pool_is_free_index (bt->samples, bts_index)) return 0; return pool_elt_at_index (bt->samples, bts_index); } static tcp_bt_sample_t * bt_next_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts) { return bt_get_sample (bt, bts->next); } static tcp_bt_sample_t * bt_prev_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts) { return bt_get_sample (bt, bts->prev); } static u32 bt_sample_index (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts) { if (!bts) return TCP_BTS_INVALID_INDEX; return bts - bt->samples; } static inline int bt_seq_lt (u32 a, u32 b) { return seq_lt (a, b); } static tcp_bt_sample_t * bt_alloc_sample (tcp_byte_tracker_t * bt, u32 min_seq, u32 max_seq) { tcp_bt_sample_t *bts; pool_get_zero (bt->samples, bts); bts->next = bts->prev = TCP_BTS_INVALID_INDEX; bts->min_seq = min_seq; bts->max_seq = max_seq; rb_tree_add_custom (&bt->sample_lookup, bts->min_seq, bts - bt->samples, bt_seq_lt); return bts; } static void bt_free_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts) { if (bts->prev != TCP_BTS_INVALID_INDEX) { tcp_bt_sample_t *prev = bt_prev_sample (bt, bts); prev->next = bts->next; } else bt->head = bts->next; if (bts->next != TCP_BTS_INVALID_INDEX) { tcp_bt_sample_t *next = bt_next_sample (bt, bts); next->prev = bts->prev; } else bt->tail = bts->prev; rb_tree_del_custom (&bt->sample_lookup, bts->min_seq, bt_seq_lt); if (CLIB_DEBUG) memset (bts, 0xfc, sizeof (*bts)); pool_put (bt->samples, bts); } static tcp_bt_sample_t * bt_split_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts, u32 seq) { tcp_bt_sample_t *ns, *next; u32 bts_index; bts_index = bt_sample_index (bt, bts); ASSERT (seq_leq (bts->min_seq, seq) && seq_lt (seq, bts->max_seq)); ns = bt_alloc_sample (bt, seq, bts->max_seq); bts = bt_get_sample (bt, bts_index); *ns = *bts; ns->min_seq = seq; bts->max_seq = seq; next = bt_next_sample (bt, bts); if (next) next->prev = bt_sample_index (bt, ns); else bt->tail = bt_sample_index (bt, ns); bts->next = bt_sample_index (bt, ns); ns->prev = bt_sample_index (bt, bts); return ns; } static tcp_bt_sample_t * bt_merge_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * prev, tcp_bt_sample_t * cur) { ASSERT (prev->max_seq == cur->min_seq); prev->max_seq = cur->max_seq; if (bt_sample_index (bt, cur) == bt->tail) bt->tail = bt_sample_index (bt, prev); bt_free_sample (bt, cur); return prev; } static tcp_bt_sample_t * bt_lookup_seq (tcp_byte_tracker_t * bt, u32 seq) { rb_tree_t *rt = &bt->sample_lookup; rb_node_t *cur, *prev; tcp_bt_sample_t *bts; cur = rb_node (rt, rt->root); if (rb_node_is_tnil (rt, cur)) return 0; while (seq != cur->key) { prev = cur; if (seq_lt (seq, cur->key)) cur = rb_node_left (rt, cur); else cur = rb_node_right (rt, cur); if (rb_node_is_tnil (rt, cur)) { /* Hit tnil as a left child. Find predecessor */ if (seq_lt (seq, prev->key)) { cur = rb_tree_predecessor (rt, prev); if (rb_node_is_tnil (rt, cur)) return 0; bts = bt_get_sample (bt, cur->opaque); } /* Hit tnil as a right child */ else { bts = bt_get_sample (bt, prev->opaque); } if (seq_geq (seq, bts->min_seq)) return bts; return 0; } } if (!rb_node_is_tnil (rt, cur)) return bt_get_sample (bt, cur->opaque); return 0; } static void bt_update_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts, u32 seq) { rb_tree_del_custom (&bt->sample_lookup, bts->min_seq, bt_seq_lt); bts->min_seq = seq; rb_tree_add_custom (&bt->sample_lookup, bts->min_seq, bt_sample_index (bt, bts), bt_seq_lt); } static tcp_bt_sample_t * bt_fix_overlapped (tcp_byte_tracker_t * bt, tcp_bt_sample_t * start, u32 seq, u8 is_end) { tcp_bt_sample_t *cur, *next; cur = start; while (cur && seq_leq (cur->max_seq, seq)) { next = bt_next_sample (bt, cur); bt_free_sample (bt, cur); cur = next; } if (cur && seq_lt (cur->min_seq, seq)) bt_update_sample (bt, cur, seq); return cur; } int tcp_bt_is_sane (tcp_byte_tracker_t * bt) { tcp_bt_sample_t *bts, *tmp; if (pool_elts (bt->samples) != pool_elts (bt->sample_lookup.nodes) - 1) return 0; if (bt->head == TCP_BTS_INVALID_INDEX) { if (bt->tail != TCP_BTS_INVALID_INDEX) return 0; if (pool_elts (bt->samples) != 0) return 0; return 1; } bts = bt_get_sample (bt, bt->tail); if (!bts) return 0; bts = bt_get_sample (bt, bt->head); if (!bts || bts->prev != TCP_BTS_INVALID_INDEX) return 0; while (bts) { tmp = bt_lookup_seq (bt, bts->min_seq); if (!tmp) return 0; if (tmp != bts) return 0; tmp = bt_next_sample (bt, bts); if (tmp) { if (tmp->prev != bt_sample_index (bt, bts)) { clib_warning ("next %u thinks prev is %u should be %u", bts->next, tmp->prev, bt_sample_index (bt, bts)); return 0; } if (!seq_lt (bts->min_seq, tmp->min_seq)) return 0; } else { if (bt->tail != bt_sample_index (bt, bts)) return 0; if (bts->next != TCP_BTS_INVALID_INDEX) return 0; } bts = tmp; } return 1; } static tcp_bt_sample_t * tcp_bt_alloc_tx_sample (tcp_connection_t * tc, u32 min_seq, u32 max_seq) { tcp_bt_sample_t *bts; bts = bt_alloc_sample (tc->bt, min_seq, max_seq); bts->delivered = tc->delivered; bts->delivered_time = tc->delivered_time; bts->tx_time = tcp_time_now_us (tc->c_thread_index); bts->first_tx_time = tc->first_tx_time; bts->flags |= tc->app_limited ? TCP_BTS_IS_APP_LIMITED : 0; bts->tx_in_flight = tcp_flight_size (tc); bts->tx_lost = tc->lost; return bts; } void tcp_bt_check_app_limited (tcp_connection_t * tc) { u32 available_bytes, flight_size; available_bytes = transport_max_tx_dequeue (&tc->connection); flight_size = tcp_flight_size (tc); /* Not enough bytes to fill the cwnd */ if (available_bytes + flight_size + tc->snd_mss < tc->cwnd /* Bytes considered lost have been retransmitted */ && tc->sack_sb.lost_bytes <= tc->snd_rxt_bytes) tc->app_limited = tc->delivered + flight_size ? : 1; } void tcp_bt_track_tx (tcp_connection_t * tc, u32 len) { tcp_byte_tracker_t *bt = tc->bt; tcp_bt_sample_t *bts, *tail; u32 bts_index; tail = bt_get_sample (bt, bt->tail); if (tail && tail->max_seq == tc->snd_nxt && !(tail->flags & TCP_BTS_IS_SACKED) && tail->tx_time == tcp_time_now_us (tc->c_thread_index)) { tail->max_seq += len; return; } if (tc->snd_una == tc->snd_nxt) { tc->delivered_time = tcp_time_now_us (tc->c_thread_index); tc->first_tx_time = tc->delivered_time; } bts = tcp_bt_alloc_tx_sample (tc, tc->snd_nxt, tc->snd_nxt + len); bts_index = bt_sample_index (bt, bts); tail = bt_get_sample (bt, bt->tail); if (tail) { tail->next = bts_index; bts->prev = bt->tail; bt->tail = bts_index; } else { bt->tail = bt->head = bts_index; } } void tcp_bt_track_rxt (tcp_connection_t * tc, u32 start, u32 end) { tcp_byte_tracker_t *bt = tc->bt; tcp_bt_sample_t *bts, *next, *cur, *prev, *nbts; u32 bts_index, cur_index, next_index, prev_index, max_seq; u8 is_end = end == tc->snd_nxt; tcp_bts_flags_t bts_flags; /* Contiguous blocks retransmitted at the same time */ bts = bt_get_sample (bt, bt->last_ooo); if (bts && bts->max_seq == start && bts->tx_time == tcp_time_now_us (tc->c_thread_index)) { bts->max_seq = end; next = bt_next_sample (bt, bts); if (next) bt_fix_overlapped (bt, next, end, is_end); return; }