1 /* 2 * net/dccp/ccids/lib/loss_interval.c 3 * 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> 7 * 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. 12 */ 13 14 #include <linux/module.h> 15 #include <net/sock.h> 16 #include "../../dccp.h" 17 #include "loss_interval.h" 18 #include "packet_history.h" 19 #include "tfrc.h" 20 21 #define DCCP_LI_HIST_IVAL_F_LENGTH 8 22 23 struct dccp_li_hist_entry { 24 struct list_head dccplih_node; 25 u64 dccplih_seqno:48, 26 dccplih_win_count:4; 27 u32 dccplih_interval; 28 }; 29 30 static struct kmem_cache *dccp_li_cachep __read_mostly; 31 32 static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio) 33 { 34 return kmem_cache_alloc(dccp_li_cachep, prio); 35 } 36 37 static inline void dccp_li_hist_entry_delete(struct dccp_li_hist_entry *entry) 38 { 39 if (entry != NULL) 40 kmem_cache_free(dccp_li_cachep, entry); 41 } 42 43 void dccp_li_hist_purge(struct list_head *list) 44 { 45 struct dccp_li_hist_entry *entry, *next; 46 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); 50 } 51 } 52 53 EXPORT_SYMBOL_GPL(dccp_li_hist_purge); 54 55 /* Weights used to calculate loss event rate */ 56 /* 57 * These are integers as per section 8 of RFC3448. We can then divide by 4 * 58 * when we use it. 59 */ 60 static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = { 61 4, 4, 4, 4, 3, 2, 1, 1, 62 }; 63 64 u32 dccp_li_hist_calc_i_mean(struct list_head *list) 65 { 66 struct dccp_li_hist_entry *li_entry, *li_next; 67 int i = 0; 68 u32 i_tot; 69 u32 i_tot0 = 0; 70 u32 i_tot1 = 0; 71 u32 w_tot = 0; 72 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]; 77 if (i != 0) 78 i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1]; 79 } 80 81 82 if (++i > DCCP_LI_HIST_IVAL_F_LENGTH) 83 break; 84 } 85 86 if (i != DCCP_LI_HIST_IVAL_F_LENGTH) 87 return 0; 88 89 i_tot = max(i_tot0, i_tot1); 90 91 if (!w_tot) { 92 DCCP_WARN("w_tot = 0\n"); 93 return 1; 94 } 95 96 return i_tot / w_tot; 97 } 98 99 EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean); 100 101 static int dccp_li_hist_interval_new(struct list_head *list, 102 const u64 seq_loss, const u8 win_loss) 103 { 104 struct dccp_li_hist_entry *entry; 105 int i; 106 107 for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) { 108 entry = dccp_li_hist_entry_new(GFP_ATOMIC); 109 if (entry == NULL) { 110 dccp_li_hist_purge(list); 111 DCCP_BUG("loss interval list entry is NULL"); 112 return 0; 113 } 114 entry->dccplih_interval = ~0; 115 list_add(&entry->dccplih_node, list); 116 } 117 118 entry->dccplih_seqno = seq_loss; 119 entry->dccplih_win_count = win_loss; 120 return 1; 121 } 122 123 /* calculate first loss interval 124 * 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, 130 u32 previous_x_recv) 131 { 132 struct dccp_rx_hist_entry *entry, *next, *tail = NULL; 133 u32 x_recv, p; 134 suseconds_t rtt, delta; 135 ktime_t tstamp = ktime_set(0, 0); 136 int interval = 0; 137 int win_count = 0; 138 int step = 0; 139 u64 fval; 140 141 list_for_each_entry_safe(entry, next, hist_list, dccphrx_node) { 142 if (dccp_rx_hist_entry_data_packet(entry)) { 143 tail = entry; 144 145 switch (step) { 146 case 0: 147 tstamp = entry->dccphrx_tstamp; 148 win_count = entry->dccphrx_ccval; 149 step = 1; 150 break; 151 case 1: 152 interval = win_count - entry->dccphrx_ccval; 153 if (interval < 0) 154 interval += TFRC_WIN_COUNT_LIMIT; 155 if (interval > 4) 156 goto found; 157 break; 158 } 159 } 160 } 161 162 if (unlikely(step == 0)) { 163 DCCP_WARN("%s(%p), packet history has no data packets!\n", 164 dccp_role(sk), sk); 165 return ~0; 166 } 167 168 if (unlikely(interval == 0)) { 169 DCCP_WARN("%s(%p), Could not find a win_count interval > 0." 170 "Defaulting to 1\n", dccp_role(sk), sk); 171 interval = 1; 172 } 173 found: 174 if (!tail) { 175 DCCP_CRIT("tail is null\n"); 176 return ~0; 177 } 178 179 delta = ktime_us_delta(tstamp, tail->dccphrx_tstamp); 180 DCCP_BUG_ON(delta < 0); 181 182 rtt = delta * 4 / interval; 183 dccp_pr_debug("%s(%p), approximated RTT to %dus\n", 184 dccp_role(sk), sk, (int)rtt); 185 186 /* 187 * Determine the length of the first loss interval via inverse lookup. 188 * Assume that X_recv can be computed by the throughput equation 189 * s 190 * X_recv = -------- 191 * R * fval 192 * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1]. 193 */ 194 if (rtt == 0) { /* would result in divide-by-zero */ 195 DCCP_WARN("RTT==0\n"); 196 return ~0; 197 } 198 199 delta = ktime_us_delta(ktime_get_real(), last_feedback); 200 DCCP_BUG_ON(delta <= 0); 201 202 x_recv = scaled_div32(bytes_recv, delta); 203 if (x_recv == 0) { /* would also trigger divide-by-zero */ 204 DCCP_WARN("X_recv==0\n"); 205 if (previous_x_recv == 0) { 206 DCCP_BUG("stored value of X_recv is zero"); 207 return ~0; 208 } 209 x_recv = previous_x_recv; 210 } 211 212 fval = scaled_div(s, rtt); 213 fval = scaled_div32(fval, x_recv); 214 p = tfrc_calc_x_reverse_lookup(fval); 215 216 dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " 217 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); 218 219 if (p == 0) 220 return ~0; 221 else 222 return 1000000 / p; 223 } 224 225 void dccp_li_update_li(struct sock *sk, 226 struct list_head *li_hist_list, 227 struct list_head *hist_list, 228 ktime_t last_feedback, u16 s, u32 bytes_recv, 229 u32 previous_x_recv, u64 seq_loss, u8 win_loss) 230 { 231 struct dccp_li_hist_entry *head; 232 u64 seq_temp; 233 234 if (list_empty(li_hist_list)) { 235 if (!dccp_li_hist_interval_new(li_hist_list, seq_loss, 236 win_loss)) 237 return; 238 239 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, 240 dccplih_node); 241 head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list, 242 last_feedback, 243 s, bytes_recv, 244 previous_x_recv); 245 } else { 246 struct dccp_li_hist_entry *entry; 247 struct list_head *tail; 248 249 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, 250 dccplih_node); 251 /* FIXME win count check removed as was wrong */ 252 /* should make this check with receive history */ 253 /* and compare there as per section 10.2 of RFC4342 */ 254 255 /* new loss event detected */ 256 /* calculate last interval length */ 257 seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); 258 entry = dccp_li_hist_entry_new(GFP_ATOMIC); 259 260 if (entry == NULL) { 261 DCCP_BUG("out of memory - can not allocate entry"); 262 return; 263 } 264 265 list_add(&entry->dccplih_node, li_hist_list); 266 267 tail = li_hist_list->prev; 268 list_del(tail); 269 kmem_cache_free(dccp_li_cachep, tail); 270 271 /* Create the newest interval */ 272 entry->dccplih_seqno = seq_loss; 273 entry->dccplih_interval = seq_temp; 274 entry->dccplih_win_count = win_loss; 275 } 276 } 277 278 EXPORT_SYMBOL_GPL(dccp_li_update_li); 279 280 static __init int dccp_li_init(void) 281 { 282 dccp_li_cachep = kmem_cache_create("dccp_li_hist", 283 sizeof(struct dccp_li_hist_entry), 284 0, SLAB_HWCACHE_ALIGN, NULL); 285 return dccp_li_cachep == NULL ? -ENOBUFS : 0; 286 } 287 288 static __exit void dccp_li_exit(void) 289 { 290 kmem_cache_destroy(dccp_li_cachep); 291 } 292 293 module_init(dccp_li_init); 294 module_exit(dccp_li_exit); 295