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 #define DCCP_LI_HIST_IVAL_F_LENGTH 8
23 struct dccp_li_hist_entry {
24 struct list_head dccplih_node;
30 static struct kmem_cache *dccp_li_cachep __read_mostly;
32 static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio)
34 return kmem_cache_alloc(dccp_li_cachep, prio);
37 static inline void dccp_li_hist_entry_delete(struct dccp_li_hist_entry *entry)
40 kmem_cache_free(dccp_li_cachep, entry);
43 void dccp_li_hist_purge(struct list_head *list)
45 struct dccp_li_hist_entry *entry, *next;
47 list_for_each_entry_safe(entry, next, list, dccplih_node) {
48 list_del_init(&entry->dccplih_node);
49 kmem_cache_free(dccp_li_cachep, entry);
53 EXPORT_SYMBOL_GPL(dccp_li_hist_purge);
55 /* Weights used to calculate loss event rate */
57 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
60 static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = {
61 4, 4, 4, 4, 3, 2, 1, 1,
64 u32 dccp_li_hist_calc_i_mean(struct list_head *list)
66 struct dccp_li_hist_entry *li_entry, *li_next;
73 list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
74 if (li_entry->dccplih_interval != ~0U) {
75 i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
76 w_tot += dccp_li_hist_w[i];
78 i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];
82 if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
86 if (i != DCCP_LI_HIST_IVAL_F_LENGTH)
89 i_tot = max(i_tot0, i_tot1);
92 DCCP_WARN("w_tot = 0\n");
99 EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean);
101 static int dccp_li_hist_interval_new(struct list_head *list,
102 const u64 seq_loss, const u8 win_loss)
104 struct dccp_li_hist_entry *entry;
107 for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) {
108 entry = dccp_li_hist_entry_new(GFP_ATOMIC);
110 dccp_li_hist_purge(list);
111 DCCP_BUG("loss interval list entry is NULL");
114 entry->dccplih_interval = ~0;
115 list_add(&entry->dccplih_node, list);
118 entry->dccplih_seqno = seq_loss;
119 entry->dccplih_win_count = win_loss;
123 /* calculate first loss interval
125 * returns estimated loss interval in usecs */
126 static u32 dccp_li_calc_first_li(struct sock *sk,
127 struct list_head *hist_list,
128 ktime_t last_feedback,
129 u16 s, u32 bytes_recv,
134 * Will be rewritten in the upcoming new loss intervals code.
135 * Has to be commented ou because it relies on the old rx history
139 struct tfrc_rx_hist_entry *entry, *next, *tail = NULL;
141 suseconds_t rtt, delta;
142 ktime_t tstamp = ktime_set(0, 0);
148 list_for_each_entry_safe(entry, next, hist_list, tfrchrx_node) {
149 if (tfrc_rx_hist_entry_data_packet(entry)) {
154 tstamp = entry->tfrchrx_tstamp;
155 win_count = entry->tfrchrx_ccval;
159 interval = win_count - entry->tfrchrx_ccval;
161 interval += TFRC_WIN_COUNT_LIMIT;
169 if (unlikely(step == 0)) {
170 DCCP_WARN("%s(%p), packet history has no data packets!\n",
175 if (unlikely(interval == 0)) {
176 DCCP_WARN("%s(%p), Could not find a win_count interval > 0. "
177 "Defaulting to 1\n", dccp_role(sk), sk);
182 DCCP_CRIT("tail is null\n");
186 delta = ktime_us_delta(tstamp, tail->tfrchrx_tstamp);
187 DCCP_BUG_ON(delta < 0);
189 rtt = delta * 4 / interval;
190 dccp_pr_debug("%s(%p), approximated RTT to %dus\n",
191 dccp_role(sk), sk, (int)rtt);
194 * Determine the length of the first loss interval via inverse lookup.
195 * Assume that X_recv can be computed by the throughput equation
199 * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1].
201 if (rtt == 0) { /* would result in divide-by-zero */
202 DCCP_WARN("RTT==0\n");
206 delta = ktime_us_delta(ktime_get_real(), last_feedback);
207 DCCP_BUG_ON(delta <= 0);
209 x_recv = scaled_div32(bytes_recv, delta);
210 if (x_recv == 0) { /* would also trigger divide-by-zero */
211 DCCP_WARN("X_recv==0\n");
212 if (previous_x_recv == 0) {
213 DCCP_BUG("stored value of X_recv is zero");
216 x_recv = previous_x_recv;
219 fval = scaled_div(s, rtt);
220 fval = scaled_div32(fval, x_recv);
221 p = tfrc_calc_x_reverse_lookup(fval);
223 dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
224 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
232 void dccp_li_update_li(struct sock *sk,
233 struct list_head *li_hist_list,
234 struct list_head *hist_list,
235 ktime_t last_feedback, u16 s, u32 bytes_recv,
236 u32 previous_x_recv, u64 seq_loss, u8 win_loss)
238 struct dccp_li_hist_entry *head;
241 if (list_empty(li_hist_list)) {
242 if (!dccp_li_hist_interval_new(li_hist_list, seq_loss,
246 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
248 head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list,
253 struct dccp_li_hist_entry *entry;
254 struct list_head *tail;
256 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
258 /* FIXME win count check removed as was wrong */
259 /* should make this check with receive history */
260 /* and compare there as per section 10.2 of RFC4342 */
262 /* new loss event detected */
263 /* calculate last interval length */
264 seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss);
265 entry = dccp_li_hist_entry_new(GFP_ATOMIC);
268 DCCP_BUG("out of memory - can not allocate entry");
272 list_add(&entry->dccplih_node, li_hist_list);
274 tail = li_hist_list->prev;
276 kmem_cache_free(dccp_li_cachep, tail);
278 /* Create the newest interval */
279 entry->dccplih_seqno = seq_loss;
280 entry->dccplih_interval = seq_temp;
281 entry->dccplih_win_count = win_loss;
285 EXPORT_SYMBOL_GPL(dccp_li_update_li);
287 int __init dccp_li_init(void)
289 dccp_li_cachep = kmem_cache_create("dccp_li_hist",
290 sizeof(struct dccp_li_hist_entry),
291 0, SLAB_HWCACHE_ALIGN, NULL);
292 return dccp_li_cachep == NULL ? -ENOBUFS : 0;
295 void dccp_li_exit(void)
297 if (dccp_li_cachep != NULL) {
298 kmem_cache_destroy(dccp_li_cachep);
299 dccp_li_cachep = NULL;