From 276f2edc52e309b38a216245952e05880e182c83 Mon Sep 17 00:00:00 2001 From: Arnaldo Carvalho de Melo Date: Wed, 28 Nov 2007 11:15:40 -0200 Subject: [TFRC]: Migrate TX history to singly-linked lis This patch was based on another made by Gerrit Renker, his changelog was: ------------------------------------------------------ The patch set migrates TFRC TX history to a singly-linked list. The details are: * use of a consistent naming scheme (all TFRC functions now begin with `tfrc_'); * allocation and cleanup are taken care of internally; * provision of a lookup function, which is used by the CCID TX infrastructure to determine the time a packet was sent (in turn used for RTT sampling); * integration of the new interface with the present use in CCID3. ------------------------------------------------------ Simplifications I did: . removing the tfrc_tx_hist_head that had a pointer to the list head and another for the slabcache. . No need for creating a slabcache for each CCID that wants to use the TFRC tx history routines, create a single slabcache when the dccp_tfrc_lib module init routine is called. Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/lib/loss_interval.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index d26b88dbbb45..f2ca4eb74ddb 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -277,7 +277,7 @@ void dccp_li_update_li(struct sock *sk, EXPORT_SYMBOL_GPL(dccp_li_update_li); -static __init int dccp_li_init(void) +int __init dccp_li_init(void) { dccp_li_cachep = kmem_cache_create("dccp_li_hist", sizeof(struct dccp_li_hist_entry), @@ -285,10 +285,10 @@ static __init int dccp_li_init(void) return dccp_li_cachep == NULL ? -ENOBUFS : 0; } -static __exit void dccp_li_exit(void) +void dccp_li_exit(void) { - kmem_cache_destroy(dccp_li_cachep); + if (dccp_li_cachep != NULL) { + kmem_cache_destroy(dccp_li_cachep); + dccp_li_cachep = NULL; + } } - -module_init(dccp_li_init); -module_exit(dccp_li_exit); -- cgit v1.2.3 From d58d1af03a6a3ddf296ae3aeb4ff234af4b15958 Mon Sep 17 00:00:00 2001 From: Arnaldo Carvalho de Melo Date: Thu, 6 Dec 2007 12:28:39 -0200 Subject: [TFRC]: Rename dccp_rx_ to tfrc_rx_ This is in preparation for merging the new rx history code written by Gerrit Renker. Signed-off-by: Gerrit Renker Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid3.c | 32 ++++++------- net/dccp/ccids/lib/loss_interval.c | 14 +++--- net/dccp/ccids/lib/packet_history.c | 90 ++++++++++++++++++------------------- net/dccp/ccids/lib/packet_history.h | 48 ++++++++++---------- 4 files changed, 92 insertions(+), 92 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 2ba0a7c470d1..e0f87f22719e 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -677,7 +677,7 @@ static void ccid3_hc_rx_send_feedback(struct sock *sk) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct dccp_rx_hist_entry *packet; + struct tfrc_rx_hist_entry *packet; ktime_t now; suseconds_t delta; @@ -701,7 +701,7 @@ static void ccid3_hc_rx_send_feedback(struct sock *sk) return; } - packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist); + packet = tfrc_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist); if (unlikely(packet == NULL)) { DCCP_WARN("%s(%p), no data packet in history!\n", dccp_role(sk), sk); @@ -709,7 +709,7 @@ static void ccid3_hc_rx_send_feedback(struct sock *sk) } hcrx->ccid3hcrx_tstamp_last_feedback = now; - hcrx->ccid3hcrx_ccval_last_counter = packet->dccphrx_ccval; + hcrx->ccid3hcrx_ccval_last_counter = packet->tfrchrx_ccval; hcrx->ccid3hcrx_bytes_recv = 0; if (hcrx->ccid3hcrx_p == 0) @@ -752,12 +752,12 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) } static int ccid3_hc_rx_detect_loss(struct sock *sk, - struct dccp_rx_hist_entry *packet) + struct tfrc_rx_hist_entry *packet) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - struct dccp_rx_hist_entry *rx_hist = - dccp_rx_hist_head(&hcrx->ccid3hcrx_hist); - u64 seqno = packet->dccphrx_seqno; + struct tfrc_rx_hist_entry *rx_hist = + tfrc_rx_hist_head(&hcrx->ccid3hcrx_hist); + u64 seqno = packet->tfrchrx_seqno; u64 tmp_seqno; int loss = 0; u8 ccval; @@ -766,9 +766,9 @@ static int ccid3_hc_rx_detect_loss(struct sock *sk, tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss; if (!rx_hist || - follows48(packet->dccphrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { + follows48(packet->tfrchrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval; + hcrx->ccid3hcrx_ccval_nonloss = packet->tfrchrx_ccval; goto detect_out; } @@ -789,7 +789,7 @@ static int ccid3_hc_rx_detect_loss(struct sock *sk, dccp_inc_seqno(&tmp_seqno); hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; dccp_inc_seqno(&tmp_seqno); - while (dccp_rx_hist_find_entry(&hcrx->ccid3hcrx_hist, + while (tfrc_rx_hist_find_entry(&hcrx->ccid3hcrx_hist, tmp_seqno, &ccval)) { hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; hcrx->ccid3hcrx_ccval_nonloss = ccval; @@ -799,13 +799,13 @@ static int ccid3_hc_rx_detect_loss(struct sock *sk, /* FIXME - this code could be simplified with above while */ /* but works at moment */ - if (follows48(packet->dccphrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { + if (follows48(packet->tfrchrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval; + hcrx->ccid3hcrx_ccval_nonloss = packet->tfrchrx_ccval; } detect_out: - dccp_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, + tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, &hcrx->ccid3hcrx_li_hist, packet, hcrx->ccid3hcrx_seqno_nonloss); return loss; @@ -815,7 +815,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); const struct dccp_options_received *opt_recv; - struct dccp_rx_hist_entry *packet; + struct tfrc_rx_hist_entry *packet; u32 p_prev, r_sample, rtt_prev; int loss, payload_size; ktime_t now; @@ -850,7 +850,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) return; } - packet = dccp_rx_hist_entry_new(opt_recv->dccpor_ndp, skb, GFP_ATOMIC); + packet = tfrc_rx_hist_entry_new(opt_recv->dccpor_ndp, skb, GFP_ATOMIC); if (unlikely(packet == NULL)) { DCCP_WARN("%s(%p), Not enough mem to add rx packet " "to history, consider it lost!\n", dccp_role(sk), sk); @@ -933,7 +933,7 @@ static void ccid3_hc_rx_exit(struct sock *sk) ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM); /* Empty packet history */ - dccp_rx_hist_purge(&hcrx->ccid3hcrx_hist); + tfrc_rx_hist_purge(&hcrx->ccid3hcrx_hist); /* Empty loss interval history */ dccp_li_hist_purge(&hcrx->ccid3hcrx_li_hist); diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index f2ca4eb74ddb..a5f59af8df43 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -129,7 +129,7 @@ static u32 dccp_li_calc_first_li(struct sock *sk, u16 s, u32 bytes_recv, u32 previous_x_recv) { - struct dccp_rx_hist_entry *entry, *next, *tail = NULL; + struct tfrc_rx_hist_entry *entry, *next, *tail = NULL; u32 x_recv, p; suseconds_t rtt, delta; ktime_t tstamp = ktime_set(0, 0); @@ -138,18 +138,18 @@ static u32 dccp_li_calc_first_li(struct sock *sk, int step = 0; u64 fval; - list_for_each_entry_safe(entry, next, hist_list, dccphrx_node) { - if (dccp_rx_hist_entry_data_packet(entry)) { + list_for_each_entry_safe(entry, next, hist_list, tfrchrx_node) { + if (tfrc_rx_hist_entry_data_packet(entry)) { tail = entry; switch (step) { case 0: - tstamp = entry->dccphrx_tstamp; - win_count = entry->dccphrx_ccval; + tstamp = entry->tfrchrx_tstamp; + win_count = entry->tfrchrx_ccval; step = 1; break; case 1: - interval = win_count - entry->dccphrx_ccval; + interval = win_count - entry->tfrchrx_ccval; if (interval < 0) interval += TFRC_WIN_COUNT_LIMIT; if (interval > 4) @@ -176,7 +176,7 @@ found: return ~0; } - delta = ktime_us_delta(tstamp, tail->dccphrx_tstamp); + delta = ktime_us_delta(tstamp, tail->tfrchrx_tstamp); DCCP_BUG_ON(delta < 0); rtt = delta * 4 / interval; diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c index e1ab853c38df..255cca1ca737 100644 --- a/net/dccp/ccids/lib/packet_history.c +++ b/net/dccp/ccids/lib/packet_history.c @@ -116,58 +116,58 @@ EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt); */ static struct kmem_cache *tfrc_rx_hist_slab; -struct dccp_rx_hist_entry *dccp_rx_hist_entry_new(const u32 ndp, +struct tfrc_rx_hist_entry *tfrc_rx_hist_entry_new(const u32 ndp, const struct sk_buff *skb, const gfp_t prio) { - struct dccp_rx_hist_entry *entry = kmem_cache_alloc(tfrc_rx_hist_slab, + struct tfrc_rx_hist_entry *entry = kmem_cache_alloc(tfrc_rx_hist_slab, prio); if (entry != NULL) { const struct dccp_hdr *dh = dccp_hdr(skb); - entry->dccphrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; - entry->dccphrx_ccval = dh->dccph_ccval; - entry->dccphrx_type = dh->dccph_type; - entry->dccphrx_ndp = ndp; - entry->dccphrx_tstamp = ktime_get_real(); + entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + entry->tfrchrx_ccval = dh->dccph_ccval; + entry->tfrchrx_type = dh->dccph_type; + entry->tfrchrx_ndp = ndp; + entry->tfrchrx_tstamp = ktime_get_real(); } return entry; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_entry_new); +EXPORT_SYMBOL_GPL(tfrc_rx_hist_entry_new); -static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist_entry *entry) +static inline void tfrc_rx_hist_entry_delete(struct tfrc_rx_hist_entry *entry) { kmem_cache_free(tfrc_rx_hist_slab, entry); } -int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, +int tfrc_rx_hist_find_entry(const struct list_head *list, const u64 seq, u8 *ccval) { - struct dccp_rx_hist_entry *packet = NULL, *entry; + struct tfrc_rx_hist_entry *packet = NULL, *entry; - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_seqno == seq) { + list_for_each_entry(entry, list, tfrchrx_node) + if (entry->tfrchrx_seqno == seq) { packet = entry; break; } if (packet) - *ccval = packet->dccphrx_ccval; + *ccval = packet->tfrchrx_ccval; return packet != NULL; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry); -struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list) +EXPORT_SYMBOL_GPL(tfrc_rx_hist_find_entry); +struct tfrc_rx_hist_entry * + tfrc_rx_hist_find_data_packet(const struct list_head *list) { - struct dccp_rx_hist_entry *entry, *packet = NULL; + struct tfrc_rx_hist_entry *entry, *packet = NULL; - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK) { + list_for_each_entry(entry, list, tfrchrx_node) + if (entry->tfrchrx_type == DCCP_PKT_DATA || + entry->tfrchrx_type == DCCP_PKT_DATAACK) { packet = entry; break; } @@ -175,29 +175,29 @@ struct dccp_rx_hist_entry * return packet; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); +EXPORT_SYMBOL_GPL(tfrc_rx_hist_find_data_packet); -void dccp_rx_hist_add_packet(struct list_head *rx_list, +void tfrc_rx_hist_add_packet(struct list_head *rx_list, struct list_head *li_list, - struct dccp_rx_hist_entry *packet, + struct tfrc_rx_hist_entry *packet, u64 nonloss_seqno) { - struct dccp_rx_hist_entry *entry, *next; + struct tfrc_rx_hist_entry *entry, *next; u8 num_later = 0; - list_add(&packet->dccphrx_node, rx_list); + list_add(&packet->tfrchrx_node, rx_list); num_later = TFRC_RECV_NUM_LATE_LOSS + 1; if (!list_empty(li_list)) { - list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { + list_for_each_entry_safe(entry, next, rx_list, tfrchrx_node) { if (num_later == 0) { if (after48(nonloss_seqno, - entry->dccphrx_seqno)) { - list_del_init(&entry->dccphrx_node); - dccp_rx_hist_entry_delete(entry); + entry->tfrchrx_seqno)) { + list_del_init(&entry->tfrchrx_node); + tfrc_rx_hist_entry_delete(entry); } - } else if (dccp_rx_hist_entry_data_packet(entry)) + } else if (tfrc_rx_hist_entry_data_packet(entry)) --num_later; } } else { @@ -208,7 +208,7 @@ void dccp_rx_hist_add_packet(struct list_head *rx_list, * We have no loss interval history so we need at least one * rtt:s of data packets to approximate rtt. */ - list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { + list_for_each_entry_safe(entry, next, rx_list, tfrchrx_node) { if (num_later == 0) { switch (step) { case 0: @@ -220,10 +220,10 @@ void dccp_rx_hist_add_packet(struct list_head *rx_list, step = 2; /* OK, find next data packet */ num_later = 1; - win_count = entry->dccphrx_ccval; + win_count = entry->tfrchrx_ccval; break; case 2: - tmp = win_count - entry->dccphrx_ccval; + tmp = win_count - entry->tfrchrx_ccval; if (tmp < 0) tmp += TFRC_WIN_COUNT_LIMIT; if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { @@ -236,29 +236,29 @@ void dccp_rx_hist_add_packet(struct list_head *rx_list, num_later = 1; break; case 3: - list_del_init(&entry->dccphrx_node); - dccp_rx_hist_entry_delete(entry); + list_del_init(&entry->tfrchrx_node); + tfrc_rx_hist_entry_delete(entry); break; } - } else if (dccp_rx_hist_entry_data_packet(entry)) + } else if (tfrc_rx_hist_entry_data_packet(entry)) --num_later; } } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); +EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); -void dccp_rx_hist_purge(struct list_head *list) +void tfrc_rx_hist_purge(struct list_head *list) { - struct dccp_rx_hist_entry *entry, *next; + struct tfrc_rx_hist_entry *entry, *next; - list_for_each_entry_safe(entry, next, list, dccphrx_node) { - list_del_init(&entry->dccphrx_node); - dccp_rx_hist_entry_delete(entry); + list_for_each_entry_safe(entry, next, list, tfrchrx_node) { + list_del_init(&entry->tfrchrx_node); + tfrc_rx_hist_entry_delete(entry); } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); +EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); __init int packet_history_init(void) { @@ -269,7 +269,7 @@ __init int packet_history_init(void) goto out_err; tfrc_rx_hist_slab = kmem_cache_create("tfrc_rx_hist", - sizeof(struct dccp_rx_hist_entry), 0, + sizeof(struct tfrc_rx_hist_entry), 0, SLAB_HWCACHE_ALIGN, NULL); if (tfrc_rx_hist_slab == NULL) goto out_free_tx; diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h index 34b180b0edaa..5b0b9834340d 100644 --- a/net/dccp/ccids/lib/packet_history.h +++ b/net/dccp/ccids/lib/packet_history.h @@ -57,51 +57,51 @@ extern u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, /* * Receiver History data structures and declarations */ -struct dccp_rx_hist_entry { - struct list_head dccphrx_node; - u64 dccphrx_seqno:48, - dccphrx_ccval:4, - dccphrx_type:4; - u32 dccphrx_ndp; /* In fact it is from 8 to 24 bits */ - ktime_t dccphrx_tstamp; +struct tfrc_rx_hist_entry { + struct list_head tfrchrx_node; + u64 tfrchrx_seqno:48, + tfrchrx_ccval:4, + tfrchrx_type:4; + u32 tfrchrx_ndp; /* In fact it is from 8 to 24 bits */ + ktime_t tfrchrx_tstamp; }; -extern struct dccp_rx_hist_entry * - dccp_rx_hist_entry_new(const u32 ndp, +extern struct tfrc_rx_hist_entry * + tfrc_rx_hist_entry_new(const u32 ndp, const struct sk_buff *skb, const gfp_t prio); -static inline struct dccp_rx_hist_entry * - dccp_rx_hist_head(struct list_head *list) +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_head(struct list_head *list) { - struct dccp_rx_hist_entry *head = NULL; + struct tfrc_rx_hist_entry *head = NULL; if (!list_empty(list)) - head = list_entry(list->next, struct dccp_rx_hist_entry, - dccphrx_node); + head = list_entry(list->next, struct tfrc_rx_hist_entry, + tfrchrx_node); return head; } -extern int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, +extern int tfrc_rx_hist_find_entry(const struct list_head *list, const u64 seq, u8 *ccval); -extern struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list); +extern struct tfrc_rx_hist_entry * + tfrc_rx_hist_find_data_packet(const struct list_head *list); -extern void dccp_rx_hist_add_packet(struct list_head *rx_list, +extern void tfrc_rx_hist_add_packet(struct list_head *rx_list, struct list_head *li_list, - struct dccp_rx_hist_entry *packet, + struct tfrc_rx_hist_entry *packet, u64 nonloss_seqno); -extern void dccp_rx_hist_purge(struct list_head *list); +extern void tfrc_rx_hist_purge(struct list_head *list); static inline int - dccp_rx_hist_entry_data_packet(const struct dccp_rx_hist_entry *entry) + tfrc_rx_hist_entry_data_packet(const struct tfrc_rx_hist_entry *entry) { - return entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK; + return entry->tfrchrx_type == DCCP_PKT_DATA || + entry->tfrchrx_type == DCCP_PKT_DATAACK; } -extern u64 dccp_rx_hist_detect_loss(struct list_head *rx_list, +extern u64 tfrc_rx_hist_detect_loss(struct list_head *rx_list, struct list_head *li_list, u8 *win_loss); #endif /* _DCCP_PKT_HIST_ */ -- cgit v1.2.3 From b84a2189c4e1835c51fd6b974a0497be9bc4ba87 Mon Sep 17 00:00:00 2001 From: Arnaldo Carvalho de Melo Date: Thu, 6 Dec 2007 13:18:11 -0200 Subject: [TFRC]: New rx history code Credit here goes to Gerrit Renker, that provided the initial implementation for this new codebase. I modified it just to try to make it closer to the existing API, renaming some functions, add namespacing and fix one bug where the tfrc_rx_hist_alloc was not freeing the allocated ring entries on the error path. Original changeset comment from Gerrit: ----------- This provides a new, self-contained and generic RX history service for TFRC based protocols. Details: * new data structure, initialisation and cleanup routines; * allocation of dccp_rx_hist entries local to packet_history.c, as a service exported by the dccp_tfrc_lib module. * interface to automatically track highest-received seqno; * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1); * a generic function to test for `data packets' as per RFC 4340, sec. 7.7. Signed-off-by: Gerrit Renker Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid3.c | 282 ++++++++++++----------------------- net/dccp/ccids/ccid3.h | 14 +- net/dccp/ccids/lib/loss_interval.c | 13 +- net/dccp/ccids/lib/packet_history.c | 290 ++++++++++++++++++++++-------------- net/dccp/ccids/lib/packet_history.h | 83 +++++------ 5 files changed, 327 insertions(+), 355 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index f5cfc2e2d7b2..bf95c3292d5b 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -641,6 +641,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, /* * Receiver Half-Connection Routines */ + +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE +}; + #ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { @@ -667,59 +676,60 @@ static void ccid3_hc_rx_set_state(struct sock *sk, hcrx->ccid3hcrx_state = state; } -static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len) -{ - if (likely(len > 0)) /* don't update on empty packets (e.g. ACKs) */ - hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, len, 9); -} - -static void ccid3_hc_rx_send_feedback(struct sock *sk) +static void ccid3_hc_rx_send_feedback(struct sock *sk, + const struct sk_buff *skb, + enum ccid3_fback_type fbtype) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct tfrc_rx_hist_entry *packet; ktime_t now; - suseconds_t delta; + s64 delta = 0; ccid3_pr_debug("%s(%p) - entry \n", dccp_role(sk), sk); + if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_TERM)) + return; + now = ktime_get_real(); - switch (hcrx->ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: + switch (fbtype) { + case CCID3_FBACK_INITIAL: hcrx->ccid3hcrx_x_recv = 0; + hcrx->ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: - delta = ktime_us_delta(now, - hcrx->ccid3hcrx_tstamp_last_feedback); - DCCP_BUG_ON(delta < 0); - hcrx->ccid3hcrx_x_recv = - scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta); + case CCID3_FBACK_PARAM_CHANGE: + /* + * When parameters change (new loss or p > p_prev), we do not + * have a reliable estimate for R_m of [RFC 3448, 6.2] and so + * need to reuse the previous value of X_recv. However, when + * X_recv was 0 (due to early loss), this would kill X down to + * s/t_mbi (i.e. one packet in 64 seconds). + * To avoid such drastic reduction, we approximate X_recv as + * the number of bytes since last feedback. + * This is a safe fallback, since X is bounded above by X_calc. + */ + if (hcrx->ccid3hcrx_x_recv > 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hcrx->ccid3hcrx_tstamp_last_feedback); + if (delta <= 0) + DCCP_BUG("delta (%ld) <= 0", (long)delta); + else + hcrx->ccid3hcrx_x_recv = + scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta); break; - case TFRC_RSTATE_TERM: - DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk); + default: return; } - packet = tfrc_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist); - if (unlikely(packet == NULL)) { - DCCP_WARN("%s(%p), no data packet in history!\n", - dccp_role(sk), sk); - return; - } + ccid3_pr_debug("Interval %ldusec, X_recv=%u, 1/p=%u\n", (long)delta, + hcrx->ccid3hcrx_x_recv, hcrx->ccid3hcrx_pinv); hcrx->ccid3hcrx_tstamp_last_feedback = now; - hcrx->ccid3hcrx_ccval_last_counter = packet->tfrchrx_ccval; + hcrx->ccid3hcrx_last_counter = dccp_hdr(skb)->dccph_ccval; hcrx->ccid3hcrx_bytes_recv = 0; - if (hcrx->ccid3hcrx_p == 0) - hcrx->ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ - else if (hcrx->ccid3hcrx_p > 1000000) { - DCCP_WARN("p (%u) > 100%%\n", hcrx->ccid3hcrx_p); - hcrx->ccid3hcrx_pinv = 1; /* use 100% in this case */ - } else - hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p; - dp->dccps_hc_rx_insert_options = 1; dccp_send_ack(sk); } @@ -750,165 +760,74 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) return 0; } -static int ccid3_hc_rx_detect_loss(struct sock *sk, - struct tfrc_rx_hist_entry *packet) +static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - struct tfrc_rx_hist_entry *rx_hist = - tfrc_rx_hist_head(&hcrx->ccid3hcrx_hist); - u64 seqno = packet->tfrchrx_seqno; - u64 tmp_seqno; - int loss = 0; - u8 ccval; - - - tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss; - - if (!rx_hist || - follows48(packet->tfrchrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { - hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->tfrchrx_ccval; - goto detect_out; - } - - - while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) - > TFRC_RECV_NUM_LATE_LOSS) { - loss = 1; - dccp_li_update_li(sk, - &hcrx->ccid3hcrx_li_hist, - &hcrx->ccid3hcrx_hist, - hcrx->ccid3hcrx_tstamp_last_feedback, - hcrx->ccid3hcrx_s, - hcrx->ccid3hcrx_bytes_recv, - hcrx->ccid3hcrx_x_recv, - hcrx->ccid3hcrx_seqno_nonloss, - hcrx->ccid3hcrx_ccval_nonloss); - tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss; - dccp_inc_seqno(&tmp_seqno); - hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; - dccp_inc_seqno(&tmp_seqno); - while (tfrc_rx_hist_find_entry(&hcrx->ccid3hcrx_hist, - tmp_seqno, &ccval)) { - hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; - hcrx->ccid3hcrx_ccval_nonloss = ccval; - dccp_inc_seqno(&tmp_seqno); + enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE; + const u32 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp; + const bool is_data_packet = dccp_data_packet(skb); + + if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) { + if (is_data_packet) { + const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4; + do_feedback = CCID3_FBACK_INITIAL; + ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA); + hcrx->ccid3hcrx_s = payload; + /* + * Not necessary to update ccid3hcrx_bytes_recv here, + * since X_recv = 0 for the first feedback packet (cf. + * RFC 3448, 6.3) -- gerrit + */ } + goto update_records; } - /* FIXME - this code could be simplified with above while */ - /* but works at moment */ - if (follows48(packet->tfrchrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { - hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->tfrchrx_ccval; - } - -detect_out: - tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, - &hcrx->ccid3hcrx_li_hist, packet, - hcrx->ccid3hcrx_seqno_nonloss); - return loss; -} - -static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) -{ - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - const struct dccp_options_received *opt_recv; - struct tfrc_rx_hist_entry *packet; - u32 p_prev, r_sample, rtt_prev; - int loss, payload_size; - ktime_t now; - - opt_recv = &dccp_sk(sk)->dccps_options_received; + if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb)) + return; /* done receiving */ - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case DCCP_PKT_ACK: - if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA) - return; - case DCCP_PKT_DATAACK: - if (opt_recv->dccpor_timestamp_echo == 0) - break; - r_sample = dccp_timestamp() - opt_recv->dccpor_timestamp_echo; - rtt_prev = hcrx->ccid3hcrx_rtt; - r_sample = dccp_sample_rtt(sk, 10 * r_sample); - - if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA) - hcrx->ccid3hcrx_rtt = r_sample; - else - hcrx->ccid3hcrx_rtt = (hcrx->ccid3hcrx_rtt * 9) / 10 + - r_sample / 10; - - if (rtt_prev != hcrx->ccid3hcrx_rtt) - ccid3_pr_debug("%s(%p), New RTT=%uus, elapsed time=%u\n", - dccp_role(sk), sk, hcrx->ccid3hcrx_rtt, - opt_recv->dccpor_elapsed_time); - break; - case DCCP_PKT_DATA: - break; - default: /* We're not interested in other packet types, move along */ - return; - } - - packet = tfrc_rx_hist_entry_new(opt_recv->dccpor_ndp, skb, GFP_ATOMIC); - if (unlikely(packet == NULL)) { - DCCP_WARN("%s(%p), Not enough mem to add rx packet " - "to history, consider it lost!\n", dccp_role(sk), sk); - return; + if (is_data_packet) { + const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4; + /* + * Update moving-average of s and the sum of received payload bytes + */ + hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload, 9); + hcrx->ccid3hcrx_bytes_recv += payload; } - loss = ccid3_hc_rx_detect_loss(sk, packet); - - if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK) - return; - - payload_size = skb->len - dccp_hdr(skb)->dccph_doff * 4; - ccid3_hc_rx_update_s(hcrx, payload_size); + /* + * Handle pending losses and otherwise check for new loss + */ + if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp)) + goto update_records; - switch (hcrx->ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: - ccid3_pr_debug("%s(%p, state=%s), skb=%p, sending initial " - "feedback\n", dccp_role(sk), sk, - dccp_state_name(sk->sk_state), skb); - ccid3_hc_rx_send_feedback(sk); - ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA); - return; - case TFRC_RSTATE_DATA: - hcrx->ccid3hcrx_bytes_recv += payload_size; - if (loss) - break; + /* + * Handle data packets: RTT sampling and monitoring p + */ + if (unlikely(!is_data_packet)) + goto update_records; - now = ktime_get_real(); - if ((ktime_us_delta(now, hcrx->ccid3hcrx_tstamp_last_ack) - - (s64)hcrx->ccid3hcrx_rtt) >= 0) { - hcrx->ccid3hcrx_tstamp_last_ack = now; - ccid3_hc_rx_send_feedback(sk); - } - return; - case TFRC_RSTATE_TERM: - DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk); - return; + if (list_empty(&hcrx->ccid3hcrx_li_hist)) { /* no loss so far: p = 0 */ + const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_hist, skb); + /* + * Empty loss history: no loss so far, hence p stays 0. + * Sample RTT values, since an RTT estimate is required for the + * computation of p when the first loss occurs; RFC 3448, 6.3.1. + */ + if (sample != 0) + hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9); } - /* Dealing with packet loss */ - ccid3_pr_debug("%s(%p, state=%s), data loss! Reacting...\n", - dccp_role(sk), sk, dccp_state_name(sk->sk_state)); - - p_prev = hcrx->ccid3hcrx_p; - - /* Calculate loss event rate */ - if (!list_empty(&hcrx->ccid3hcrx_li_hist)) { - u32 i_mean = dccp_li_hist_calc_i_mean(&hcrx->ccid3hcrx_li_hist); + /* + * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3 + */ + if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3) + do_feedback = CCID3_FBACK_PERIODIC; - /* Scaling up by 1000000 as fixed decimal */ - if (i_mean != 0) - hcrx->ccid3hcrx_p = 1000000 / i_mean; - } else - DCCP_BUG("empty loss history"); +update_records: + tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp); - if (hcrx->ccid3hcrx_p > p_prev) { - ccid3_hc_rx_send_feedback(sk); - return; - } + if (do_feedback) + ccid3_hc_rx_send_feedback(sk, skb, do_feedback); } static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk) @@ -918,11 +837,8 @@ static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk) ccid3_pr_debug("entry\n"); hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA; - INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist); INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist); - hcrx->ccid3hcrx_tstamp_last_feedback = - hcrx->ccid3hcrx_tstamp_last_ack = ktime_get_real(); - return 0; + return tfrc_rx_hist_alloc(&hcrx->ccid3hcrx_hist); } static void ccid3_hc_rx_exit(struct sock *sk) diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h index b842a7dd99de..3c33dc670cf9 100644 --- a/net/dccp/ccids/ccid3.h +++ b/net/dccp/ccids/ccid3.h @@ -1,7 +1,8 @@ /* * net/dccp/ccids/ccid3.h * - * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * * An implementation of the DCCP protocol * @@ -135,9 +136,7 @@ enum ccid3_hc_rx_states { * @ccid3hcrx_x_recv - Receiver estimate of send rate (RFC 3448 4.3) * @ccid3hcrx_rtt - Receiver estimate of rtt (non-standard) * @ccid3hcrx_p - current loss event rate (RFC 3448 5.4) - * @ccid3hcrx_seqno_nonloss - Last received non-loss sequence number - * @ccid3hcrx_ccval_nonloss - Last received non-loss Window CCVal - * @ccid3hcrx_ccval_last_counter - Tracks window counter (RFC 4342, 8.1) + * @ccid3hcrx_last_counter - Tracks window counter (RFC 4342, 8.1) * @ccid3hcrx_state - receiver state, one of %ccid3_hc_rx_states * @ccid3hcrx_bytes_recv - Total sum of DCCP payload bytes * @ccid3hcrx_tstamp_last_feedback - Time at which last feedback was sent @@ -152,14 +151,11 @@ struct ccid3_hc_rx_sock { #define ccid3hcrx_x_recv ccid3hcrx_tfrc.tfrcrx_x_recv #define ccid3hcrx_rtt ccid3hcrx_tfrc.tfrcrx_rtt #define ccid3hcrx_p ccid3hcrx_tfrc.tfrcrx_p - u64 ccid3hcrx_seqno_nonloss:48, - ccid3hcrx_ccval_nonloss:4, - ccid3hcrx_ccval_last_counter:4; + u8 ccid3hcrx_last_counter:4; enum ccid3_hc_rx_states ccid3hcrx_state:8; u32 ccid3hcrx_bytes_recv; ktime_t ccid3hcrx_tstamp_last_feedback; - ktime_t ccid3hcrx_tstamp_last_ack; - struct list_head ccid3hcrx_hist; + struct tfrc_rx_hist ccid3hcrx_hist; struct list_head ccid3hcrx_li_hist; u16 ccid3hcrx_s; u32 ccid3hcrx_pinv; diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index a5f59af8df43..c0a933a1d28e 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -129,6 +129,13 @@ static u32 dccp_li_calc_first_li(struct sock *sk, u16 s, u32 bytes_recv, u32 previous_x_recv) { +/* + * FIXME: + * Will be rewritten in the upcoming new loss intervals code. + * Has to be commented ou because it relies on the old rx history + * data structures + */ +#if 0 struct tfrc_rx_hist_entry *entry, *next, *tail = NULL; u32 x_recv, p; suseconds_t rtt, delta; @@ -216,10 +223,10 @@ found: dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); - if (p == 0) - return ~0; - else + if (p != 0) return 1000000 / p; +#endif + return ~0; } void dccp_li_update_li(struct sock *sk, diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c index 255cca1ca737..4eddb2da8334 100644 --- a/net/dccp/ccids/lib/packet_history.c +++ b/net/dccp/ccids/lib/packet_history.c @@ -36,7 +36,9 @@ */ #include +#include #include "packet_history.h" +#include "../../dccp.h" /** * tfrc_tx_hist_entry - Simple singly-linked TX history list @@ -111,154 +113,214 @@ u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno, } EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt); + +/** + * tfrc_rx_hist_index - index to reach n-th entry after loss_start + */ +static inline u8 tfrc_rx_hist_index(const struct tfrc_rx_hist *h, const u8 n) +{ + return (h->loss_start + n) & TFRC_NDUPACK; +} + +/** + * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist *h) +{ + return h->ring[tfrc_rx_hist_index(h, h->loss_count)]; +} + /* * Receiver History Routines */ static struct kmem_cache *tfrc_rx_hist_slab; -struct tfrc_rx_hist_entry *tfrc_rx_hist_entry_new(const u32 ndp, - const struct sk_buff *skb, - const gfp_t prio) +void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, + const u32 ndp) { - struct tfrc_rx_hist_entry *entry = kmem_cache_alloc(tfrc_rx_hist_slab, - prio); - - if (entry != NULL) { - const struct dccp_hdr *dh = dccp_hdr(skb); - - entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; - entry->tfrchrx_ccval = dh->dccph_ccval; - entry->tfrchrx_type = dh->dccph_type; - entry->tfrchrx_ndp = ndp; - entry->tfrchrx_tstamp = ktime_get_real(); - } - - return entry; + struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); + const struct dccp_hdr *dh = dccp_hdr(skb); + + entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + entry->tfrchrx_ccval = dh->dccph_ccval; + entry->tfrchrx_type = dh->dccph_type; + entry->tfrchrx_ndp = ndp; + entry->tfrchrx_tstamp = ktime_get_real(); } -EXPORT_SYMBOL_GPL(tfrc_rx_hist_entry_new); +EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); static inline void tfrc_rx_hist_entry_delete(struct tfrc_rx_hist_entry *entry) { kmem_cache_free(tfrc_rx_hist_slab, entry); } -int tfrc_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval) +/** + * tfrc_rx_hist_entry - return the n-th history entry after loss_start + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_entry(const struct tfrc_rx_hist *h, const u8 n) { - struct tfrc_rx_hist_entry *packet = NULL, *entry; + return h->ring[tfrc_rx_hist_index(h, n)]; +} - list_for_each_entry(entry, list, tfrchrx_node) - if (entry->tfrchrx_seqno == seq) { - packet = entry; - break; - } +/** + * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist *h) +{ + return h->ring[h->loss_start]; +} + +/* has the packet contained in skb been seen before? */ +int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) +{ + const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; + int i; + + if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0) + return 1; - if (packet) - *ccval = packet->tfrchrx_ccval; + for (i = 1; i <= h->loss_count; i++) + if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq) + return 1; - return packet != NULL; + return 0; } +EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate); -EXPORT_SYMBOL_GPL(tfrc_rx_hist_find_entry); -struct tfrc_rx_hist_entry * - tfrc_rx_hist_find_data_packet(const struct list_head *list) +/* initialise loss detection and disable RTT sampling */ +static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h) { - struct tfrc_rx_hist_entry *entry, *packet = NULL; + h->loss_count = 1; +} - list_for_each_entry(entry, list, tfrchrx_node) - if (entry->tfrchrx_type == DCCP_PKT_DATA || - entry->tfrchrx_type == DCCP_PKT_DATAACK) { - packet = entry; - break; - } +/* indicate whether previously a packet was detected missing */ +static inline int tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist *h) +{ + return h->loss_count; +} + +/* any data packets missing between last reception and skb ? */ +int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h, + const struct sk_buff *skb, u32 ndp) +{ + int delta = dccp_delta_seqno(tfrc_rx_hist_last_rcv(h)->tfrchrx_seqno, + DCCP_SKB_CB(skb)->dccpd_seq); + + if (delta > 1 && ndp < delta) + tfrc_rx_hist_loss_indicated(h); - return packet; + return tfrc_rx_hist_loss_pending(h); } +EXPORT_SYMBOL_GPL(tfrc_rx_hist_new_loss_indicated); -EXPORT_SYMBOL_GPL(tfrc_rx_hist_find_data_packet); +int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) +{ + int i; + + for (i = 0; i <= TFRC_NDUPACK; i++) { + h->ring[i] = kmem_cache_alloc(tfrc_rx_hist_slab, GFP_ATOMIC); + if (h->ring[i] == NULL) + goto out_free; + } + + h->loss_count = h->loss_start = 0; + return 0; + +out_free: + while (i-- != 0) { + kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); + h->ring[i] = NULL; + } + return -ENOBUFS; +} +EXPORT_SYMBOL_GPL(tfrc_rx_hist_alloc); -void tfrc_rx_hist_add_packet(struct list_head *rx_list, - struct list_head *li_list, - struct tfrc_rx_hist_entry *packet, - u64 nonloss_seqno) +void tfrc_rx_hist_purge(struct tfrc_rx_hist *h) { - struct tfrc_rx_hist_entry *entry, *next; - u8 num_later = 0; - - list_add(&packet->tfrchrx_node, rx_list); - - num_later = TFRC_RECV_NUM_LATE_LOSS + 1; - - if (!list_empty(li_list)) { - list_for_each_entry_safe(entry, next, rx_list, tfrchrx_node) { - if (num_later == 0) { - if (after48(nonloss_seqno, - entry->tfrchrx_seqno)) { - list_del_init(&entry->tfrchrx_node); - tfrc_rx_hist_entry_delete(entry); - } - } else if (tfrc_rx_hist_entry_data_packet(entry)) - --num_later; - } - } else { - int step = 0; - u8 win_count = 0; /* Not needed, but lets shut up gcc */ - int tmp; - /* - * We have no loss interval history so we need at least one - * rtt:s of data packets to approximate rtt. - */ - list_for_each_entry_safe(entry, next, rx_list, tfrchrx_node) { - if (num_later == 0) { - switch (step) { - case 0: - step = 1; - /* OK, find next data packet */ - num_later = 1; - break; - case 1: - step = 2; - /* OK, find next data packet */ - num_later = 1; - win_count = entry->tfrchrx_ccval; - break; - case 2: - tmp = win_count - entry->tfrchrx_ccval; - if (tmp < 0) - tmp += TFRC_WIN_COUNT_LIMIT; - if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { - /* - * We have found a packet older - * than one rtt remove the rest - */ - step = 3; - } else /* OK, find next data packet */ - num_later = 1; - break; - case 3: - list_del_init(&entry->tfrchrx_node); - tfrc_rx_hist_entry_delete(entry); - break; - } - } else if (tfrc_rx_hist_entry_data_packet(entry)) - --num_later; + int i; + + for (i = 0; i <= TFRC_NDUPACK; ++i) + if (h->ring[i] != NULL) { + kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); + h->ring[i] = NULL; } - } } +EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); -EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); +/** + * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist *h) +{ + return h->ring[0]; +} -void tfrc_rx_hist_purge(struct list_head *list) +/** + * tfrc_rx_hist_rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist *h) { - struct tfrc_rx_hist_entry *entry, *next; + return h->ring[h->rtt_sample_prev]; +} - list_for_each_entry_safe(entry, next, list, tfrchrx_node) { - list_del_init(&entry->tfrchrx_node); - tfrc_rx_hist_entry_delete(entry); +/** + * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal + * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able + * to compute a sample with given data - calling function should check this. + */ +u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) +{ + u32 sample = 0, + delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + + if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */ + if (h->rtt_sample_prev == 2) { /* previous candidate stored */ + sample = SUB16(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + if (sample) + sample = 4 / sample * + ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_tstamp, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp); + else /* + * FIXME: This condition is in principle not + * possible but occurs when CCID is used for + * two-way data traffic. I have tried to trace + * it, but the cause does not seem to be here. + */ + DCCP_BUG("please report to dccp@vger.kernel.org" + " => prev = %u, last = %u", + tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + } else if (delta_v < 1) { + h->rtt_sample_prev = 1; + goto keep_ref_for_next_time; + } + + } else if (delta_v == 4) /* optimal match */ + sample = ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp)); + else { /* suboptimal match */ + h->rtt_sample_prev = 2; + goto keep_ref_for_next_time; } -} -EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); + if (unlikely(sample > DCCP_SANE_RTT_MAX)) { + DCCP_WARN("RTT sample %u too large, using max\n", sample); + sample = DCCP_SANE_RTT_MAX; + } + + h->rtt_sample_prev = 0; /* use current entry as next reference */ +keep_ref_for_next_time: + + return sample; +} +EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); __init int packet_history_init(void) { diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h index 5b0b9834340d..3dfd182b0e64 100644 --- a/net/dccp/ccids/lib/packet_history.h +++ b/net/dccp/ccids/lib/packet_history.h @@ -37,15 +37,9 @@ #define _DCCP_PKT_HIST_ #include -#include -#include -#include "tfrc.h" +#include -/* Number of later packets received before one is considered lost */ -#define TFRC_RECV_NUM_LATE_LOSS 3 - -#define TFRC_WIN_COUNT_PER_RTT 4 -#define TFRC_WIN_COUNT_LIMIT 16 +struct sk_buff; struct tfrc_tx_hist_entry; @@ -54,11 +48,20 @@ extern void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp); extern u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno, const ktime_t now); -/* - * Receiver History data structures and declarations +/* Subtraction a-b modulo-16, respects circular wrap-around */ +#define SUB16(a, b) (((a) + 16 - (b)) & 0xF) + +/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */ +#define TFRC_NDUPACK 3 + +/** + * tfrc_rx_hist_entry - Store information about a single received packet + * @tfrchrx_seqno: DCCP packet sequence number + * @tfrchrx_ccval: window counter value of packet (RFC 4342, 8.1) + * @tfrchrx_ndp: the NDP count (if any) of the packet + * @tfrchrx_tstamp: actual receive time of packet */ struct tfrc_rx_hist_entry { - struct list_head tfrchrx_node; u64 tfrchrx_seqno:48, tfrchrx_ccval:4, tfrchrx_type:4; @@ -66,42 +69,30 @@ struct tfrc_rx_hist_entry { ktime_t tfrchrx_tstamp; }; -extern struct tfrc_rx_hist_entry * - tfrc_rx_hist_entry_new(const u32 ndp, - const struct sk_buff *skb, - const gfp_t prio); - -static inline struct tfrc_rx_hist_entry * - tfrc_rx_hist_head(struct list_head *list) -{ - struct tfrc_rx_hist_entry *head = NULL; - - if (!list_empty(list)) - head = list_entry(list->next, struct tfrc_rx_hist_entry, - tfrchrx_node); - return head; -} - -extern int tfrc_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval); -extern struct tfrc_rx_hist_entry * - tfrc_rx_hist_find_data_packet(const struct list_head *list); - -extern void tfrc_rx_hist_add_packet(struct list_head *rx_list, - struct list_head *li_list, - struct tfrc_rx_hist_entry *packet, - u64 nonloss_seqno); - -extern void tfrc_rx_hist_purge(struct list_head *list); +/** + * tfrc_rx_hist - RX history structure for TFRC-based protocols + * + * @ring: Packet history for RTT sampling and loss detection + * @loss_count: Number of entries in circular history + * @loss_start: Movable index (for loss detection) + * @rtt_sample_prev: Used during RTT sampling, points to candidate entry + */ +struct tfrc_rx_hist { + struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1]; + u8 loss_count:2, + loss_start:2; +#define rtt_sample_prev loss_start +}; -static inline int - tfrc_rx_hist_entry_data_packet(const struct tfrc_rx_hist_entry *entry) -{ - return entry->tfrchrx_type == DCCP_PKT_DATA || - entry->tfrchrx_type == DCCP_PKT_DATAACK; -} +extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, const u32 ndp); -extern u64 tfrc_rx_hist_detect_loss(struct list_head *rx_list, - struct list_head *li_list, u8 *win_loss); +extern int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb); +extern int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h, + const struct sk_buff *skb, u32 ndp); +extern u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, + const struct sk_buff *skb); +extern int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h); +extern void tfrc_rx_hist_purge(struct tfrc_rx_hist *h); #endif /* _DCCP_PKT_HIST_ */ -- cgit v1.2.3 From 8a9c7e92e0ca97632126feee32ba2698b4eb6c8f Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 12 Dec 2007 13:50:51 -0200 Subject: [TFRC]: Ringbuffer to track loss interval history A ringbuffer-based implementation of loss interval history is easier to maintain, allocate, and update. The `swap' routine to keep the RX history sorted is due to and was written by Arnaldo Carvalho de Melo, simplifying an earlier macro-based variant. Details: * access to the Loss Interval Records via macro wrappers (with safety checks); * simplified, on-demand allocation of entries (no extra memory consumption on lossless links); cache allocation is local to the module / exported as service; * provision of RFC-compliant algorithm to re-compute average loss interval; * provision of comprehensive, new loss detection algorithm - support for all cases of loss, including re-ordered/duplicate packets; - waiting for NDUPACK=3 packets to fill the hole; - updating loss records when a late-arriving packet fills a hole. Signed-off-by: Gerrit Renker Signed-off-by: Ian McDonald Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/lib/loss_interval.c | 161 +++++++++++++++++++++++++- net/dccp/ccids/lib/loss_interval.h | 56 ++++++++- net/dccp/ccids/lib/packet_history.c | 218 +++++++++++++++++++++++++++++++++++- net/dccp/ccids/lib/packet_history.h | 11 +- net/dccp/ccids/lib/tfrc.h | 3 + 5 files changed, 435 insertions(+), 14 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index c0a933a1d28e..39980d1f5352 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -1,6 +1,7 @@ /* * net/dccp/ccids/lib/loss_interval.c * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. * Copyright (c) 2005-7 Ian McDonald * Copyright (c) 2005 Arnaldo Carvalho de Melo @@ -10,12 +11,7 @@ * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. */ - -#include #include -#include "../../dccp.h" -#include "loss_interval.h" -#include "packet_history.h" #include "tfrc.h" #define DCCP_LI_HIST_IVAL_F_LENGTH 8 @@ -27,6 +23,54 @@ struct dccp_li_hist_entry { u32 dccplih_interval; }; +static struct kmem_cache *tfrc_lh_slab __read_mostly; +/* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */ +static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 }; + +/* implements LIFO semantics on the array */ +static inline u8 LIH_INDEX(const u8 ctr) +{ + return (LIH_SIZE - 1 - (ctr % LIH_SIZE)); +} + +/* the `counter' index always points at the next entry to be populated */ +static inline struct tfrc_loss_interval *tfrc_lh_peek(struct tfrc_loss_hist *lh) +{ + return lh->counter ? lh->ring[LIH_INDEX(lh->counter - 1)] : NULL; +} + +/* given i with 0 <= i <= k, return I_i as per the rfc3448bis notation */ +static inline u32 tfrc_lh_get_interval(struct tfrc_loss_hist *lh, const u8 i) +{ + BUG_ON(i >= lh->counter); + return lh->ring[LIH_INDEX(lh->counter - i - 1)]->li_length; +} + +/* + * On-demand allocation and de-allocation of entries + */ +static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh) +{ + if (lh->ring[LIH_INDEX(lh->counter)] == NULL) + lh->ring[LIH_INDEX(lh->counter)] = kmem_cache_alloc(tfrc_lh_slab, + GFP_ATOMIC); + return lh->ring[LIH_INDEX(lh->counter)]; +} + +void tfrc_lh_cleanup(struct tfrc_loss_hist *lh) +{ + if (!tfrc_lh_is_initialised(lh)) + return; + + for (lh->counter = 0; lh->counter < LIH_SIZE; lh->counter++) + if (lh->ring[LIH_INDEX(lh->counter)] != NULL) { + kmem_cache_free(tfrc_lh_slab, + lh->ring[LIH_INDEX(lh->counter)]); + lh->ring[LIH_INDEX(lh->counter)] = NULL; + } +} +EXPORT_SYMBOL_GPL(tfrc_lh_cleanup); + static struct kmem_cache *dccp_li_cachep __read_mostly; static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio) @@ -98,6 +142,65 @@ u32 dccp_li_hist_calc_i_mean(struct list_head *list) EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean); +static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) +{ + u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; + int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */ + + for (i=0; i <= k; i++) { + i_i = tfrc_lh_get_interval(lh, i); + + if (i < k) { + i_tot0 += i_i * tfrc_lh_weights[i]; + w_tot += tfrc_lh_weights[i]; + } + if (i > 0) + i_tot1 += i_i * tfrc_lh_weights[i-1]; + } + + BUG_ON(w_tot == 0); + lh->i_mean = max(i_tot0, i_tot1) / w_tot; +} + +/** + * tfrc_lh_update_i_mean - Update the `open' loss interval I_0 + * For recomputing p: returns `true' if p > p_prev <=> 1/p < 1/p_prev + */ +u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) +{ + struct tfrc_loss_interval *cur = tfrc_lh_peek(lh); + u32 old_i_mean = lh->i_mean; + s64 length; + + if (cur == NULL) /* not initialised */ + return 0; + + length = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq); + + if (length - cur->li_length <= 0) /* duplicate or reordered */ + return 0; + + if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4) + /* + * Implements RFC 4342, 10.2: + * If a packet S (skb) exists whose seqno comes `after' the one + * starting the current loss interval (cur) and if the modulo-16 + * distance from C(cur) to C(S) is greater than 4, consider all + * subsequent packets as belonging to a new loss interval. This + * test is necessary since CCVal may wrap between intervals. + */ + cur->li_is_closed = 1; + + if (tfrc_lh_length(lh) == 1) /* due to RFC 3448, 6.3.1 */ + return 0; + + cur->li_length = length; + tfrc_lh_calc_i_mean(lh); + + return (lh->i_mean < old_i_mean); +} +EXPORT_SYMBOL_GPL(tfrc_lh_update_i_mean); + static int dccp_li_hist_interval_new(struct list_head *list, const u64 seq_loss, const u8 win_loss) { @@ -284,6 +387,54 @@ void dccp_li_update_li(struct sock *sk, EXPORT_SYMBOL_GPL(dccp_li_update_li); +/* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */ +static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur, + struct tfrc_rx_hist_entry *new_loss) +{ + return dccp_delta_seqno(cur->li_seqno, new_loss->tfrchrx_seqno) > 0 && + (cur->li_is_closed || SUB16(new_loss->tfrchrx_ccval, cur->li_ccval) > 4); +} + +/** tfrc_lh_interval_add - Insert new record into the Loss Interval database + * @lh: Loss Interval database + * @rh: Receive history containing a fresh loss event + * @calc_first_li: Caller-dependent routine to compute length of first interval + * @sk: Used by @calc_first_li in caller-specific way (subtyping) + * Updates I_mean and returns 1 if a new interval has in fact been added to @lh. + */ +int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh, + u32 (*calc_first_li)(struct sock *), struct sock *sk) +{ + struct tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new; + + if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh))) + return 0; + + new = tfrc_lh_demand_next(lh); + if (unlikely(new == NULL)) { + DCCP_CRIT("Cannot allocate/add loss record."); + return 0; + } + + new->li_seqno = tfrc_rx_hist_loss_prev(rh)->tfrchrx_seqno; + new->li_ccval = tfrc_rx_hist_loss_prev(rh)->tfrchrx_ccval; + new->li_is_closed = 0; + + if (++lh->counter == 1) + lh->i_mean = new->li_length = (*calc_first_li)(sk); + else { + cur->li_length = dccp_delta_seqno(cur->li_seqno, new->li_seqno); + new->li_length = dccp_delta_seqno(new->li_seqno, + tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno); + if (lh->counter > (2*LIH_SIZE)) + lh->counter -= LIH_SIZE; + + tfrc_lh_calc_i_mean(lh); + } + return 1; +} +EXPORT_SYMBOL_GPL(tfrc_lh_interval_add); + int __init dccp_li_init(void) { dccp_li_cachep = kmem_cache_create("dccp_li_hist", diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h index 27bee92dae13..5e3c5c54a495 100644 --- a/net/dccp/ccids/lib/loss_interval.h +++ b/net/dccp/ccids/lib/loss_interval.h @@ -3,6 +3,7 @@ /* * net/dccp/ccids/lib/loss_interval.h * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. * Copyright (c) 2005-7 Ian McDonald * Copyright (c) 2005 Arnaldo Carvalho de Melo @@ -12,11 +13,64 @@ * Software Foundation; either version 2 of the License, or (at your option) * any later version. */ - #include #include +#include + +/* + * Number of loss intervals (RFC 4342, 8.6.1). The history size is one more than + * NINTERVAL, since the `open' interval I_0 is always stored as the first entry. + */ +#define NINTERVAL 8 +#define LIH_SIZE (NINTERVAL + 1) + +/** + * tfrc_loss_interval - Loss history record for TFRC-based protocols + * @li_seqno: Highest received seqno before the start of loss + * @li_ccval: The CCVal belonging to @li_seqno + * @li_is_closed: Whether @li_seqno is older than 1 RTT + * @li_length: Loss interval sequence length + */ +struct tfrc_loss_interval { + u64 li_seqno:48, + li_ccval:4, + li_is_closed:1; + u32 li_length; +}; + +/** + * tfrc_loss_hist - Loss record database + * @ring: Circular queue managed in LIFO manner + * @counter: Current count of entries (can be more than %LIH_SIZE) + * @i_mean: Current Average Loss Interval [RFC 3448, 5.4] + */ +struct tfrc_loss_hist { + struct tfrc_loss_interval *ring[LIH_SIZE]; + u8 counter; + u32 i_mean; +}; + +static inline void tfrc_lh_init(struct tfrc_loss_hist *lh) +{ + memset(lh, 0, sizeof(struct tfrc_loss_hist)); +} + +static inline u8 tfrc_lh_is_initialised(struct tfrc_loss_hist *lh) +{ + return lh->counter > 0; +} + +static inline u8 tfrc_lh_length(struct tfrc_loss_hist *lh) +{ + return min(lh->counter, (u8)LIH_SIZE); +} extern void dccp_li_hist_purge(struct list_head *list); +struct tfrc_rx_hist; +extern int tfrc_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *, + u32 (*first_li)(struct sock *), struct sock *); +extern u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *); +extern void tfrc_lh_cleanup(struct tfrc_loss_hist *lh); extern u32 dccp_li_hist_calc_i_mean(struct list_head *list); diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c index dd2cf2d6b8fc..5b10a1ecf138 100644 --- a/net/dccp/ccids/lib/packet_history.c +++ b/net/dccp/ccids/lib/packet_history.c @@ -151,11 +151,10 @@ void tfrc_rx_packet_history_exit(void) } } -void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, - const struct sk_buff *skb, - const u32 ndp) +static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry, + const struct sk_buff *skb, + const u32 ndp) { - struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); const struct dccp_hdr *dh = dccp_hdr(skb); entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; @@ -164,6 +163,15 @@ void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, entry->tfrchrx_ndp = ndp; entry->tfrchrx_tstamp = ktime_get_real(); } + +void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, + const u32 ndp) +{ + struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); + + tfrc_rx_hist_entry_from_skb(entry, skb, ndp); +} EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); /* has the packet contained in skb been seen before? */ @@ -209,6 +217,208 @@ int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h, } EXPORT_SYMBOL_GPL(tfrc_rx_hist_new_loss_indicated); +static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) +{ + const u8 idx_a = tfrc_rx_hist_index(h, a), + idx_b = tfrc_rx_hist_index(h, b); + struct tfrc_rx_hist_entry *tmp = h->ring[idx_a]; + + h->ring[idx_a] = h->ring[idx_b]; + h->ring[idx_b] = tmp; +} + +/* + * Private helper functions for loss detection. + * + * In the descriptions, `Si' refers to the sequence number of entry number i, + * whose NDP count is `Ni' (lower case is used for variables). + * Note: All __after_loss functions expect that a test against duplicates has + * been performed already: the seqno of the skb must not be less than the + * seqno of loss_prev; and it must not equal that of any valid hist_entry. + */ +static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2) +{ + u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, + s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = DCCP_SKB_CB(skb)->dccpd_seq; + int n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp, + d12 = dccp_delta_seqno(s1, s2), d2; + + if (d12 > 0) { /* S1 < S2 */ + h->loss_count = 2; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n2); + return; + } + + /* S0 < S2 < S1 */ + d2 = dccp_delta_seqno(s0, s2); + + if (d2 == 1 || n2 >= d2) { /* S2 is direct successor of S0 */ + int d21 = -d12; + + if (d21 == 1 || n1 >= d21) { + /* hole is filled: S0, S2, and S1 are consecutive */ + h->loss_count = 0; + h->loss_start = tfrc_rx_hist_index(h, 1); + } else + /* gap between S2 and S1: just update loss_prev */ + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2); + + } else { /* hole between S0 and S2 */ + /* + * Reorder history to insert S2 between S0 and s1 + */ + tfrc_rx_hist_swap(h, 0, 3); + h->loss_start = tfrc_rx_hist_index(h, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n2); + h->loss_count = 2; + } +} + +/* return 1 if a new loss event has been identified */ +static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3) +{ + u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, + s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, + s3 = DCCP_SKB_CB(skb)->dccpd_seq; + int n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp, + d23 = dccp_delta_seqno(s2, s3), d13, d3, d31; + + if (d23 > 0) { /* S2 < S3 */ + h->loss_count = 3; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3), skb, n3); + return 1; + } + + /* S3 < S2 */ + d13 = dccp_delta_seqno(s1, s3); + + if (d13 > 0) { + /* + * The sequence number order is S1, S3, S2 + * Reorder history to insert entry between S1 and S2 + */ + tfrc_rx_hist_swap(h, 2, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n3); + h->loss_count = 3; + return 1; + } + + /* S0 < S3 < S1 */ + d31 = -d13; + d3 = dccp_delta_seqno(s0, s3); + + if (d3 == 1 || n3 >= d3) { /* S3 is a successor of S0 */ + + if (d31 == 1 || n1 >= d31) { + /* hole between S0 and S1 filled by S3 */ + int d2 = dccp_delta_seqno(s1, s2), + n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp; + + if (d2 == 1 || n2 >= d2) { + /* entire hole filled by S0, S3, S1, S2 */ + h->loss_start = tfrc_rx_hist_index(h, 2); + h->loss_count = 0; + } else { + /* gap remains between S1 and S2 */ + h->loss_start = tfrc_rx_hist_index(h, 1); + h->loss_count = 1; + } + + } else /* gap exists between S3 and S1, loss_count stays at 2 */ + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n3); + + return 0; + } + + /* + * The remaining case: S3 is not a successor of S0. + * Sequence order is S0, S3, S1, S2; reorder to insert between S0 and S1 + */ + tfrc_rx_hist_swap(h, 0, 3); + h->loss_start = tfrc_rx_hist_index(h, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); + h->loss_count = 3; + + return 1; +} + +/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */ +static s64 tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist *h, u8 e1, u8 e2) +{ + DCCP_BUG_ON(e1 > h->loss_count || e2 > h->loss_count); + + return dccp_delta_seqno(tfrc_rx_hist_entry(h, e1)->tfrchrx_seqno, + tfrc_rx_hist_entry(h, e2)->tfrchrx_seqno); +} + +/* recycle RX history records to continue loss detection if necessary */ +static void __three_after_loss(struct tfrc_rx_hist *h) +{ + /* + * The distance between S0 and S1 is always greater than 1 and the NDP + * count of S1 is smaller than this distance. Otherwise there would + * have been no loss. Hence it is only necessary to see whether there + * are further missing data packets between S1/S2 and S2/S3. + */ + int d2 = tfrc_rx_hist_delta_seqno(h, 1, 2), + d3 = tfrc_rx_hist_delta_seqno(h, 2, 3), + n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp, + n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp; + + if (d2 == 1 || n2 >= d2) { /* S2 is successor to S1 */ + + if (d3 == 1 || n3 >= d3) { + /* S3 is successor of S2: entire hole is filled */ + h->loss_start = tfrc_rx_hist_index(h, 3); + h->loss_count = 0; + } else { + /* gap between S2 and S3 */ + h->loss_start = tfrc_rx_hist_index(h, 2); + h->loss_count = 1; + } + + } else { /* gap between S1 and S2 */ + h->loss_start = tfrc_rx_hist_index(h, 1); + h->loss_count = 2; + } +} + +/** + * tfrc_rx_handle_loss - Loss detection and further processing + * @h: The non-empty RX history object + * @lh: Loss Intervals database to update + * @skb: Currently received packet + * @ndp: The NDP count belonging to @skb + * @calc_first_li: Caller-dependent computation of first loss interval in @lh + * @sk: Used by @calc_first_li (see tfrc_lh_interval_add) + * Chooses action according to pending loss, updates LI database when a new + * loss was detected, and does required post-processing. Returns 1 when caller + * should send feedback, 0 otherwise. + */ +int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, + struct tfrc_loss_hist *lh, + struct sk_buff *skb, u32 ndp, + u32 (*calc_first_li)(struct sock *), struct sock *sk) +{ + int is_new_loss = 0; + + if (h->loss_count == 1) { + __one_after_loss(h, skb, ndp); + } else if (h->loss_count != 2) { + DCCP_BUG("invalid loss_count %d", h->loss_count); + } else if (__two_after_loss(h, skb, ndp)) { + /* + * Update Loss Interval database and recycle RX records + */ + is_new_loss = tfrc_lh_interval_add(lh, h, calc_first_li, sk); + __three_after_loss(h); + } + return is_new_loss; +} +EXPORT_SYMBOL_GPL(tfrc_rx_handle_loss); + int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) { int i; diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h index e58b0fcdc6ae..24edd8df54b9 100644 --- a/net/dccp/ccids/lib/packet_history.h +++ b/net/dccp/ccids/lib/packet_history.h @@ -36,10 +36,9 @@ #ifndef _DCCP_PKT_HIST_ #define _DCCP_PKT_HIST_ -#include -#include - -struct sk_buff; +#include +#include +#include "tfrc.h" struct tfrc_tx_hist_entry; @@ -125,6 +124,10 @@ extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, extern int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb); extern int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h, const struct sk_buff *skb, u32 ndp); +struct tfrc_loss_hist; +extern int tfrc_rx_handle_loss(struct tfrc_rx_hist *, struct tfrc_loss_hist *, + struct sk_buff *skb, u32 ndp, + u32 (*first_li)(struct sock *), struct sock *); extern u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb); extern int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h); diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h index ab8848c0f8c9..1fb1187bbf1c 100644 --- a/net/dccp/ccids/lib/tfrc.h +++ b/net/dccp/ccids/lib/tfrc.h @@ -17,6 +17,9 @@ #include #include #include "../../dccp.h" +/* internal includes that this module exports: */ +#include "loss_interval.h" +#include "packet_history.h" #ifdef CONFIG_IP_DCCP_TFRC_DEBUG extern int tfrc_debug; -- cgit v1.2.3 From 954c2db868ce896325dced91d5fba5e2226897a4 Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 12 Dec 2007 14:06:14 -0200 Subject: [CCID3]: Interface CCID3 code with newer Loss Intervals Database This hooks up the TFRC Loss Interval database with CCID 3 packet reception. In addition, it makes the CCID-specific computation of the first loss interval (which requires access to all the guts of CCID3) local to ccid3.c. The patch also fixes an omission in the DCCP code, that of a default / fallback RTT value (defined in section 3.4 of RFC 4340 as 0.2 sec); while at it, the upper bound of 4 seconds for an RTT sample has been reduced to match the initial TCP RTO value of 3 seconds from[RFC 1122, 4.2.3.1]. Signed-off-by: Gerrit Renker Signed-off-by: Ian McDonald Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid3.c | 72 +++++++++++++++++++++++++++++++------- net/dccp/ccids/ccid3.h | 10 +++--- net/dccp/ccids/lib/loss_interval.c | 18 +++++----- net/dccp/ccids/lib/tfrc.c | 10 +++--- net/dccp/dccp.h | 7 ++-- 5 files changed, 84 insertions(+), 33 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 8266dfde89c1..8f112d18d450 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -1,6 +1,7 @@ /* * net/dccp/ccids/ccid3.c * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. * Copyright (c) 2005-7 Ian McDonald * @@ -33,11 +34,7 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -#include "../ccid.h" #include "../dccp.h" -#include "lib/packet_history.h" -#include "lib/loss_interval.h" -#include "lib/tfrc.h" #include "ccid3.h" #include @@ -757,6 +754,46 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) return 0; } +/** ccid3_first_li - Implements [RFC 3448, 6.3.1] + * + * Determine the length of the first loss interval via inverse lookup. + * Assume that X_recv can be computed by the throughput equation + * s + * X_recv = -------- + * R * fval + * Find some p such that f(p) = fval; return 1/p (scaled). + */ +static u32 ccid3_first_li(struct sock *sk) +{ + struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); + u32 x_recv, p, delta; + u64 fval; + + if (hcrx->ccid3hcrx_rtt == 0) { + DCCP_WARN("No RTT estimate available, using fallback RTT\n"); + hcrx->ccid3hcrx_rtt = DCCP_FALLBACK_RTT; + } + + delta = ktime_to_us(net_timedelta(hcrx->ccid3hcrx_tstamp_last_feedback)); + x_recv = scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta); + if (x_recv == 0) { /* would also trigger divide-by-zero */ + DCCP_WARN("X_recv==0\n"); + if ((x_recv = hcrx->ccid3hcrx_x_recv) == 0) { + DCCP_BUG("stored value of X_recv is zero"); + return ~0U; + } + } + + fval = scaled_div(hcrx->ccid3hcrx_s, hcrx->ccid3hcrx_rtt); + fval = scaled_div32(fval, x_recv); + p = tfrc_calc_x_reverse_lookup(fval); + + ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied " + "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); + + return p == 0 ? ~0U : scaled_div(1, p); +} + static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); @@ -794,6 +831,14 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) /* * Handle pending losses and otherwise check for new loss */ + if (tfrc_rx_hist_loss_pending(&hcrx->ccid3hcrx_hist) && + tfrc_rx_handle_loss(&hcrx->ccid3hcrx_hist, + &hcrx->ccid3hcrx_li_hist, + skb, ndp, ccid3_first_li, sk) ) { + do_feedback = CCID3_FBACK_PARAM_CHANGE; + goto done_receiving; + } + if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp)) goto update_records; @@ -803,7 +848,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) if (unlikely(!is_data_packet)) goto update_records; - if (list_empty(&hcrx->ccid3hcrx_li_hist)) { /* no loss so far: p = 0 */ + if (!tfrc_lh_is_initialised(&hcrx->ccid3hcrx_li_hist)) { const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_hist, skb); /* * Empty loss history: no loss so far, hence p stays 0. @@ -812,6 +857,13 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) */ if (sample != 0) hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9); + + } else if (tfrc_lh_update_i_mean(&hcrx->ccid3hcrx_li_hist, skb)) { + /* + * Step (3) of [RFC 3448, 6.1]: Recompute I_mean and, if I_mean + * has decreased (resp. p has increased), send feedback now. + */ + do_feedback = CCID3_FBACK_PARAM_CHANGE; } /* @@ -823,6 +875,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) update_records: tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp); +done_receiving: if (do_feedback) ccid3_hc_rx_send_feedback(sk, skb, do_feedback); } @@ -831,10 +884,8 @@ static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk) { struct ccid3_hc_rx_sock *hcrx = ccid_priv(ccid); - ccid3_pr_debug("entry\n"); - hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA; - INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist); + tfrc_lh_init(&hcrx->ccid3hcrx_li_hist); return tfrc_rx_hist_alloc(&hcrx->ccid3hcrx_hist); } @@ -844,11 +895,8 @@ static void ccid3_hc_rx_exit(struct sock *sk) ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM); - /* Empty packet history */ tfrc_rx_hist_purge(&hcrx->ccid3hcrx_hist); - - /* Empty loss interval history */ - dccp_li_hist_purge(&hcrx->ccid3hcrx_li_hist); + tfrc_lh_cleanup(&hcrx->ccid3hcrx_li_hist); } static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info) diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h index 6ceeb8013f58..e9f6ff4f0552 100644 --- a/net/dccp/ccids/ccid3.h +++ b/net/dccp/ccids/ccid3.h @@ -41,7 +41,7 @@ #include #include #include -#include "lib/packet_history.h" +#include "lib/tfrc.h" #include "../ccid.h" /* Two seconds as per RFC 3448 4.2 */ @@ -141,8 +141,8 @@ enum ccid3_hc_rx_states { * @ccid3hcrx_bytes_recv - Total sum of DCCP payload bytes * @ccid3hcrx_tstamp_last_feedback - Time at which last feedback was sent * @ccid3hcrx_tstamp_last_ack - Time at which last feedback was sent - * @ccid3hcrx_hist - Packet history - * @ccid3hcrx_li_hist - Loss Interval History + * @ccid3hcrx_hist - Packet history (loss detection + RTT sampling) + * @ccid3hcrx_li_hist - Loss Interval database * @ccid3hcrx_s - Received packet size in bytes * @ccid3hcrx_pinv - Inverse of Loss Event Rate (RFC 4342, sec. 8.5) */ @@ -156,9 +156,9 @@ struct ccid3_hc_rx_sock { u32 ccid3hcrx_bytes_recv; ktime_t ccid3hcrx_tstamp_last_feedback; struct tfrc_rx_hist ccid3hcrx_hist; - struct list_head ccid3hcrx_li_hist; + struct tfrc_loss_hist ccid3hcrx_li_hist; u16 ccid3hcrx_s; - u32 ccid3hcrx_pinv; +#define ccid3hcrx_pinv ccid3hcrx_li_hist.i_mean }; static inline struct ccid3_hc_rx_sock *ccid3_hc_rx_sk(const struct sock *sk) diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index 39980d1f5352..8b962c1f14b8 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -435,18 +435,18 @@ int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh, } EXPORT_SYMBOL_GPL(tfrc_lh_interval_add); -int __init dccp_li_init(void) +int __init tfrc_li_init(void) { - dccp_li_cachep = kmem_cache_create("dccp_li_hist", - sizeof(struct dccp_li_hist_entry), - 0, SLAB_HWCACHE_ALIGN, NULL); - return dccp_li_cachep == NULL ? -ENOBUFS : 0; + tfrc_lh_slab = kmem_cache_create("tfrc_li_hist", + sizeof(struct tfrc_loss_interval), 0, + SLAB_HWCACHE_ALIGN, NULL); + return tfrc_lh_slab == NULL ? -ENOBUFS : 0; } -void dccp_li_exit(void) +void tfrc_li_exit(void) { - if (dccp_li_cachep != NULL) { - kmem_cache_destroy(dccp_li_cachep); - dccp_li_cachep = NULL; + if (tfrc_lh_slab != NULL) { + kmem_cache_destroy(tfrc_lh_slab); + tfrc_lh_slab = NULL; } } diff --git a/net/dccp/ccids/lib/tfrc.c b/net/dccp/ccids/lib/tfrc.c index 20763fa75d44..d1dfbb8de64c 100644 --- a/net/dccp/ccids/lib/tfrc.c +++ b/net/dccp/ccids/lib/tfrc.c @@ -19,12 +19,12 @@ extern void tfrc_tx_packet_history_exit(void); extern int tfrc_rx_packet_history_init(void); extern void tfrc_rx_packet_history_exit(void); -extern int dccp_li_init(void); -extern void dccp_li_exit(void); +extern int tfrc_li_init(void); +extern void tfrc_li_exit(void); static int __init tfrc_module_init(void) { - int rc = dccp_li_init(); + int rc = tfrc_li_init(); if (rc) goto out; @@ -41,7 +41,7 @@ static int __init tfrc_module_init(void) out_free_tx_history: tfrc_tx_packet_history_exit(); out_free_loss_intervals: - dccp_li_exit(); + tfrc_li_exit(); out: return rc; } @@ -50,7 +50,7 @@ static void __exit tfrc_module_exit(void) { tfrc_rx_packet_history_exit(); tfrc_tx_packet_history_exit(); - dccp_li_exit(); + tfrc_li_exit(); } module_init(tfrc_module_init); diff --git a/net/dccp/dccp.h b/net/dccp/dccp.h index f4a5ea116e34..07dcbe73b50c 100644 --- a/net/dccp/dccp.h +++ b/net/dccp/dccp.h @@ -74,9 +74,12 @@ extern void dccp_time_wait(struct sock *sk, int state, int timeo); #define DCCP_RTO_MAX ((unsigned)(120 * HZ)) /* FIXME: using TCP value */ -/* bounds for sampled RTT values from packet exchanges (in usec) */ +/* + * RTT sampling: sanity bounds and fallback RTT value from RFC 4340, section 3.4 + */ #define DCCP_SANE_RTT_MIN 100 -#define DCCP_SANE_RTT_MAX (4 * USEC_PER_SEC) +#define DCCP_FALLBACK_RTT (USEC_PER_SEC / 5) +#define DCCP_SANE_RTT_MAX (3 * USEC_PER_SEC) /* Maximal interval between probes for local resources. */ #define DCCP_RESOURCE_PROBE_INTERVAL ((unsigned)(HZ / 2U)) -- cgit v1.2.3 From 3f71c81ac37b27b824e9ce18fe17438dc2af4a16 Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 12 Dec 2007 14:23:08 -0200 Subject: [TFRC]: Remove previous loss intervals implementation Signed-off-by: Gerrit Renker Signed-off-by: Ian McDonald Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/lib/loss_interval.c | 266 ------------------------------------- net/dccp/ccids/lib/loss_interval.h | 10 +- 2 files changed, 1 insertion(+), 275 deletions(-) (limited to 'net/dccp/ccids/lib/loss_interval.c') diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index 8b962c1f14b8..849e181e698f 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -14,15 +14,6 @@ #include #include "tfrc.h" -#define DCCP_LI_HIST_IVAL_F_LENGTH 8 - -struct dccp_li_hist_entry { - struct list_head dccplih_node; - u64 dccplih_seqno:48, - dccplih_win_count:4; - u32 dccplih_interval; -}; - static struct kmem_cache *tfrc_lh_slab __read_mostly; /* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */ static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 }; @@ -71,77 +62,6 @@ void tfrc_lh_cleanup(struct tfrc_loss_hist *lh) } EXPORT_SYMBOL_GPL(tfrc_lh_cleanup); -static struct kmem_cache *dccp_li_cachep __read_mostly; - -static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio) -{ - return kmem_cache_alloc(dccp_li_cachep, prio); -} - -static inline void dccp_li_hist_entry_delete(struct dccp_li_hist_entry *entry) -{ - if (entry != NULL) - kmem_cache_free(dccp_li_cachep, entry); -} - -void dccp_li_hist_purge(struct list_head *list) -{ - struct dccp_li_hist_entry *entry, *next; - - list_for_each_entry_safe(entry, next, list, dccplih_node) { - list_del_init(&entry->dccplih_node); - kmem_cache_free(dccp_li_cachep, entry); - } -} - -EXPORT_SYMBOL_GPL(dccp_li_hist_purge); - -/* Weights used to calculate loss event rate */ -/* - * These are integers as per section 8 of RFC3448. We can then divide by 4 * - * when we use it. - */ -static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = { - 4, 4, 4, 4, 3, 2, 1, 1, -}; - -u32 dccp_li_hist_calc_i_mean(struct list_head *list) -{ - struct dccp_li_hist_entry *li_entry, *li_next; - int i = 0; - u32 i_tot; - u32 i_tot0 = 0; - u32 i_tot1 = 0; - u32 w_tot = 0; - - list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) { - if (li_entry->dccplih_interval != ~0U) { - i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i]; - w_tot += dccp_li_hist_w[i]; - if (i != 0) - i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1]; - } - - - if (++i > DCCP_LI_HIST_IVAL_F_LENGTH) - break; - } - - if (i != DCCP_LI_HIST_IVAL_F_LENGTH) - return 0; - - i_tot = max(i_tot0, i_tot1); - - if (!w_tot) { - DCCP_WARN("w_tot = 0\n"); - return 1; - } - - return i_tot / w_tot; -} - -EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean); - static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) { u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; @@ -201,192 +121,6 @@ u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) } EXPORT_SYMBOL_GPL(tfrc_lh_update_i_mean); -static int dccp_li_hist_interval_new(struct list_head *list, - const u64 seq_loss, const u8 win_loss) -{ - struct dccp_li_hist_entry *entry; - int i; - - for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) { - entry = dccp_li_hist_entry_new(GFP_ATOMIC); - if (entry == NULL) { - dccp_li_hist_purge(list); - DCCP_BUG("loss interval list entry is NULL"); - return 0; - } - entry->dccplih_interval = ~0; - list_add(&entry->dccplih_node, list); - } - - entry->dccplih_seqno = seq_loss; - entry->dccplih_win_count = win_loss; - return 1; -} - -/* calculate first loss interval - * - * returns estimated loss interval in usecs */ -static u32 dccp_li_calc_first_li(struct sock *sk, - struct list_head *hist_list, - ktime_t last_feedback, - u16 s, u32 bytes_recv, - u32 previous_x_recv) -{ -/* - * FIXME: - * Will be rewritten in the upcoming new loss intervals code. - * Has to be commented ou because it relies on the old rx history - * data structures - */ -#if 0 - struct tfrc_rx_hist_entry *entry, *next, *tail = NULL; - u32 x_recv, p; - suseconds_t rtt, delta; - ktime_t tstamp = ktime_set(0, 0); - int interval = 0; - int win_count = 0; - int step = 0; - u64 fval; - - list_for_each_entry_safe(entry, next, hist_list, tfrchrx_node) { - if (tfrc_rx_hist_entry_data_packet(entry)) { - tail = entry; - - switch (step) { - case 0: - tstamp = entry->tfrchrx_tstamp; - win_count = entry->tfrchrx_ccval; - step = 1; - break; - case 1: - interval = win_count - entry->tfrchrx_ccval; - if (interval < 0) - interval += TFRC_WIN_COUNT_LIMIT; - if (interval > 4) - goto found; - break; - } - } - } - - if (unlikely(step == 0)) { - DCCP_WARN("%s(%p), packet history has no data packets!\n", - dccp_role(sk), sk); - return ~0; - } - - if (unlikely(interval == 0)) { - DCCP_WARN("%s(%p), Could not find a win_count interval > 0. " - "Defaulting to 1\n", dccp_role(sk), sk); - interval = 1; - } -found: - if (!tail) { - DCCP_CRIT("tail is null\n"); - return ~0; - } - - delta = ktime_us_delta(tstamp, tail->tfrchrx_tstamp); - DCCP_BUG_ON(delta < 0); - - rtt = delta * 4 / interval; - dccp_pr_debug("%s(%p), approximated RTT to %dus\n", - dccp_role(sk), sk, (int)rtt); - - /* - * Determine the length of the first loss interval via inverse lookup. - * Assume that X_recv can be computed by the throughput equation - * s - * X_recv = -------- - * R * fval - * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1]. - */ - if (rtt == 0) { /* would result in divide-by-zero */ - DCCP_WARN("RTT==0\n"); - return ~0; - } - - delta = ktime_us_delta(ktime_get_real(), last_feedback); - DCCP_BUG_ON(delta <= 0); - - x_recv = scaled_div32(bytes_recv, delta); - if (x_recv == 0) { /* would also trigger divide-by-zero */ - DCCP_WARN("X_recv==0\n"); - if (previous_x_recv == 0) { - DCCP_BUG("stored value of X_recv is zero"); - return ~0; - } - x_recv = previous_x_recv; - } - - fval = scaled_div(s, rtt); - fval = scaled_div32(fval, x_recv); - p = tfrc_calc_x_reverse_lookup(fval); - - dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " - "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); - - if (p != 0) - return 1000000 / p; -#endif - return ~0; -} - -void dccp_li_update_li(struct sock *sk, - struct list_head *li_hist_list, - struct list_head *hist_list, - ktime_t last_feedback, u16 s, u32 bytes_recv, - u32 previous_x_recv, u64 seq_loss, u8 win_loss) -{ - struct dccp_li_hist_entry *head; - u64 seq_temp; - - if (list_empty(li_hist_list)) { - if (!dccp_li_hist_interval_new(li_hist_list, seq_loss, - win_loss)) - return; - - head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, - dccplih_node); - head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list, - last_feedback, - s, bytes_recv, - previous_x_recv); - } else { - struct dccp_li_hist_entry *entry; - struct list_head *tail; - - head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, - dccplih_node); - /* FIXME win count check removed as was wrong */ - /* should make this check with receive history */ - /* and compare there as per section 10.2 of RFC4342 */ - - /* new loss event detected */ - /* calculate last interval length */ - seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); - entry = dccp_li_hist_entry_new(GFP_ATOMIC); - - if (entry == NULL) { - DCCP_BUG("out of memory - can not allocate entry"); - return; - } - - list_add(&entry->dccplih_node, li_hist_list); - - tail = li_hist_list->prev; - list_del(tail); - kmem_cache_free(dccp_li_cachep, tail); - - /* Create the newest interval */ - entry->dccplih_seqno = seq_loss; - entry->dccplih_interval = seq_temp; - entry->dccplih_win_count = win_loss; - } -} - -EXPORT_SYMBOL_GPL(dccp_li_update_li); - /* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */ static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur, struct tfrc_rx_hist_entry *new_loss) diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h index 5e3c5c54a495..246018a3b269 100644 --- a/net/dccp/ccids/lib/loss_interval.h +++ b/net/dccp/ccids/lib/loss_interval.h @@ -65,19 +65,11 @@ static inline u8 tfrc_lh_length(struct tfrc_loss_hist *lh) return min(lh->counter, (u8)LIH_SIZE); } -extern void dccp_li_hist_purge(struct list_head *list); struct tfrc_rx_hist; + extern int tfrc_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *, u32 (*first_li)(struct sock *), struct sock *); extern u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *); extern void tfrc_lh_cleanup(struct tfrc_loss_hist *lh); -extern u32 dccp_li_hist_calc_i_mean(struct list_head *list); - -extern void dccp_li_update_li(struct sock *sk, - struct list_head *li_hist_list, - struct list_head *hist_list, - ktime_t last_feedback, u16 s, - u32 bytes_recv, u32 previous_x_recv, - u64 seq_loss, u8 win_loss); #endif /* _DCCP_LI_HIST_ */ -- cgit v1.2.3