2 * net/dccp/ccids/lib/loss_interval.c
4 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
14 #include <linux/module.h>
16 #include "../../dccp.h"
17 #include "loss_interval.h"
18 #include "packet_history.h"
21 struct kmem_cache *dccp_li_cachep __read_mostly;
23 static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio)
25 return kmem_cache_alloc(dccp_li_cachep, prio);
28 static inline void dccp_li_hist_entry_delete(struct dccp_li_hist_entry *entry)
31 kmem_cache_free(dccp_li_cachep, entry);
34 void dccp_li_hist_purge(struct list_head *list)
36 struct dccp_li_hist_entry *entry, *next;
38 list_for_each_entry_safe(entry, next, list, dccplih_node) {
39 list_del_init(&entry->dccplih_node);
40 kmem_cache_free(dccp_li_cachep, entry);
44 EXPORT_SYMBOL_GPL(dccp_li_hist_purge);
46 /* Weights used to calculate loss event rate */
48 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
51 static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = {
52 4, 4, 4, 4, 3, 2, 1, 1,
55 u32 dccp_li_hist_calc_i_mean(struct list_head *list)
57 struct dccp_li_hist_entry *li_entry, *li_next;
64 list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
65 if (li_entry->dccplih_interval != ~0U) {
66 i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
67 w_tot += dccp_li_hist_w[i];
69 i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];
73 if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
77 if (i != DCCP_LI_HIST_IVAL_F_LENGTH)
80 i_tot = max(i_tot0, i_tot1);
83 DCCP_WARN("w_tot = 0\n");
90 EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean);
92 static int dccp_li_hist_interval_new(struct list_head *list,
93 const u64 seq_loss, const u8 win_loss)
95 struct dccp_li_hist_entry *entry;
98 for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) {
99 entry = dccp_li_hist_entry_new(GFP_ATOMIC);
101 dccp_li_hist_purge(list);
102 DCCP_BUG("loss interval list entry is NULL");
105 entry->dccplih_interval = ~0;
106 list_add(&entry->dccplih_node, list);
109 entry->dccplih_seqno = seq_loss;
110 entry->dccplih_win_count = win_loss;
114 /* calculate first loss interval
116 * returns estimated loss interval in usecs */
117 static u32 dccp_li_calc_first_li(struct sock *sk,
118 struct list_head *hist_list,
119 struct timeval *last_feedback,
120 u16 s, u32 bytes_recv,
123 struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
125 suseconds_t rtt, delta;
126 struct timeval tstamp = { 0, 0 };
132 list_for_each_entry_safe(entry, next, hist_list, dccphrx_node) {
133 if (dccp_rx_hist_entry_data_packet(entry)) {
138 tstamp = entry->dccphrx_tstamp;
139 win_count = entry->dccphrx_ccval;
143 interval = win_count - entry->dccphrx_ccval;
145 interval += TFRC_WIN_COUNT_LIMIT;
153 if (unlikely(step == 0)) {
154 DCCP_WARN("%s(%p), packet history has no data packets!\n",
159 if (unlikely(interval == 0)) {
160 DCCP_WARN("%s(%p), Could not find a win_count interval > 0."
161 "Defaulting to 1\n", dccp_role(sk), sk);
166 DCCP_CRIT("tail is null\n");
170 delta = timeval_delta(&tstamp, &tail->dccphrx_tstamp);
171 DCCP_BUG_ON(delta < 0);
173 rtt = delta * 4 / interval;
174 dccp_pr_debug("%s(%p), approximated RTT to %dus\n",
175 dccp_role(sk), sk, (int)rtt);
178 * Determine the length of the first loss interval via inverse lookup.
179 * Assume that X_recv can be computed by the throughput equation
183 * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1].
185 if (rtt == 0) { /* would result in divide-by-zero */
186 DCCP_WARN("RTT==0\n");
190 dccp_timestamp(sk, &tstamp);
191 delta = timeval_delta(&tstamp, last_feedback);
192 DCCP_BUG_ON(delta <= 0);
194 x_recv = scaled_div32(bytes_recv, delta);
195 if (x_recv == 0) { /* would also trigger divide-by-zero */
196 DCCP_WARN("X_recv==0\n");
197 if (previous_x_recv == 0) {
198 DCCP_BUG("stored value of X_recv is zero");
201 x_recv = previous_x_recv;
204 fval = scaled_div(s, rtt);
205 fval = scaled_div32(fval, x_recv);
206 p = tfrc_calc_x_reverse_lookup(fval);
208 dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
209 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
217 void dccp_li_update_li(struct sock *sk,
218 struct list_head *li_hist_list,
219 struct list_head *hist_list,
220 struct timeval *last_feedback, u16 s, u32 bytes_recv,
221 u32 previous_x_recv, u64 seq_loss, u8 win_loss)
223 struct dccp_li_hist_entry *head;
226 if (list_empty(li_hist_list)) {
227 if (!dccp_li_hist_interval_new(li_hist_list, seq_loss,
231 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
233 head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list,
238 struct dccp_li_hist_entry *entry;
239 struct list_head *tail;
241 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
243 /* FIXME win count check removed as was wrong */
244 /* should make this check with receive history */
245 /* and compare there as per section 10.2 of RFC4342 */
247 /* new loss event detected */
248 /* calculate last interval length */
249 seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss);
250 entry = dccp_li_hist_entry_new(GFP_ATOMIC);
253 DCCP_BUG("out of memory - can not allocate entry");
257 list_add(&entry->dccplih_node, li_hist_list);
259 tail = li_hist_list->prev;
261 kmem_cache_free(dccp_li_cachep, tail);
263 /* Create the newest interval */
264 entry->dccplih_seqno = seq_loss;
265 entry->dccplih_interval = seq_temp;
266 entry->dccplih_win_count = win_loss;
270 EXPORT_SYMBOL_GPL(dccp_li_update_li);
272 static __init int dccp_li_init(void)
274 dccp_li_cachep = kmem_cache_create("dccp_li_hist",
275 sizeof(struct dccp_li_hist_entry),
276 0, SLAB_HWCACHE_ALIGN, NULL, NULL);
277 return dccp_li_cachep == NULL ? -ENOBUFS : 0;
280 static __exit void dccp_li_exit(void)
282 kmem_cache_destroy(dccp_li_cachep);
285 module_init(dccp_li_init);
286 module_exit(dccp_li_exit);