Arnaldo Carvalho de Melo | ae6706f | 2005-08-27 23:03:09 -0300 | [diff] [blame] | 1 | /* |
| 2 | * net/dccp/ccids/lib/loss_interval.c |
| 3 | * |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 4 | * Copyright (c) 2007 The University of Aberdeen, Scotland, UK |
Ian McDonald | b2f41ff | 2007-05-28 12:23:29 -0300 | [diff] [blame] | 5 | * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. |
| 6 | * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> |
Arnaldo Carvalho de Melo | ae6706f | 2005-08-27 23:03:09 -0300 | [diff] [blame] | 7 | * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> |
| 8 | * |
| 9 | * This program is free software; you can redistribute it and/or modify |
| 10 | * it under the terms of the GNU General Public License as published by |
| 11 | * the Free Software Foundation; either version 2 of the License, or |
| 12 | * (at your option) any later version. |
| 13 | */ |
Ian McDonald | 66a377c | 2006-08-26 23:40:50 -0700 | [diff] [blame] | 14 | #include <net/sock.h> |
Arnaldo Carvalho de Melo | cc0a910 | 2007-06-14 17:41:28 -0300 | [diff] [blame] | 15 | #include "tfrc.h" |
Arnaldo Carvalho de Melo | ae6706f | 2005-08-27 23:03:09 -0300 | [diff] [blame] | 16 | |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 17 | static struct kmem_cache *tfrc_lh_slab __read_mostly; |
| 18 | /* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */ |
| 19 | static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 }; |
| 20 | |
| 21 | /* implements LIFO semantics on the array */ |
| 22 | static inline u8 LIH_INDEX(const u8 ctr) |
| 23 | { |
| 24 | return (LIH_SIZE - 1 - (ctr % LIH_SIZE)); |
| 25 | } |
| 26 | |
| 27 | /* the `counter' index always points at the next entry to be populated */ |
| 28 | static inline struct tfrc_loss_interval *tfrc_lh_peek(struct tfrc_loss_hist *lh) |
| 29 | { |
| 30 | return lh->counter ? lh->ring[LIH_INDEX(lh->counter - 1)] : NULL; |
| 31 | } |
| 32 | |
| 33 | /* given i with 0 <= i <= k, return I_i as per the rfc3448bis notation */ |
| 34 | static inline u32 tfrc_lh_get_interval(struct tfrc_loss_hist *lh, const u8 i) |
| 35 | { |
| 36 | BUG_ON(i >= lh->counter); |
| 37 | return lh->ring[LIH_INDEX(lh->counter - i - 1)]->li_length; |
| 38 | } |
| 39 | |
| 40 | /* |
| 41 | * On-demand allocation and de-allocation of entries |
| 42 | */ |
| 43 | static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh) |
| 44 | { |
| 45 | if (lh->ring[LIH_INDEX(lh->counter)] == NULL) |
| 46 | lh->ring[LIH_INDEX(lh->counter)] = kmem_cache_alloc(tfrc_lh_slab, |
| 47 | GFP_ATOMIC); |
| 48 | return lh->ring[LIH_INDEX(lh->counter)]; |
| 49 | } |
| 50 | |
| 51 | void tfrc_lh_cleanup(struct tfrc_loss_hist *lh) |
| 52 | { |
| 53 | if (!tfrc_lh_is_initialised(lh)) |
| 54 | return; |
| 55 | |
| 56 | for (lh->counter = 0; lh->counter < LIH_SIZE; lh->counter++) |
| 57 | if (lh->ring[LIH_INDEX(lh->counter)] != NULL) { |
| 58 | kmem_cache_free(tfrc_lh_slab, |
| 59 | lh->ring[LIH_INDEX(lh->counter)]); |
| 60 | lh->ring[LIH_INDEX(lh->counter)] = NULL; |
| 61 | } |
| 62 | } |
| 63 | EXPORT_SYMBOL_GPL(tfrc_lh_cleanup); |
| 64 | |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 65 | static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) |
| 66 | { |
| 67 | u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; |
| 68 | int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */ |
| 69 | |
| 70 | for (i=0; i <= k; i++) { |
| 71 | i_i = tfrc_lh_get_interval(lh, i); |
| 72 | |
| 73 | if (i < k) { |
| 74 | i_tot0 += i_i * tfrc_lh_weights[i]; |
| 75 | w_tot += tfrc_lh_weights[i]; |
| 76 | } |
| 77 | if (i > 0) |
| 78 | i_tot1 += i_i * tfrc_lh_weights[i-1]; |
| 79 | } |
| 80 | |
| 81 | BUG_ON(w_tot == 0); |
| 82 | lh->i_mean = max(i_tot0, i_tot1) / w_tot; |
| 83 | } |
| 84 | |
| 85 | /** |
| 86 | * tfrc_lh_update_i_mean - Update the `open' loss interval I_0 |
| 87 | * For recomputing p: returns `true' if p > p_prev <=> 1/p < 1/p_prev |
| 88 | */ |
| 89 | u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) |
| 90 | { |
| 91 | struct tfrc_loss_interval *cur = tfrc_lh_peek(lh); |
| 92 | u32 old_i_mean = lh->i_mean; |
Gerrit Renker | 2eeea7b | 2008-07-13 11:51:40 +0100 | [diff] [blame] | 93 | s64 len; |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 94 | |
| 95 | if (cur == NULL) /* not initialised */ |
| 96 | return 0; |
| 97 | |
Gerrit Renker | 2eeea7b | 2008-07-13 11:51:40 +0100 | [diff] [blame] | 98 | len = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq) + 1; |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 99 | |
Gerrit Renker | 2eeea7b | 2008-07-13 11:51:40 +0100 | [diff] [blame] | 100 | if (len - (s64)cur->li_length <= 0) /* duplicate or reordered */ |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 101 | return 0; |
| 102 | |
| 103 | if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4) |
| 104 | /* |
| 105 | * Implements RFC 4342, 10.2: |
| 106 | * If a packet S (skb) exists whose seqno comes `after' the one |
| 107 | * starting the current loss interval (cur) and if the modulo-16 |
| 108 | * distance from C(cur) to C(S) is greater than 4, consider all |
| 109 | * subsequent packets as belonging to a new loss interval. This |
| 110 | * test is necessary since CCVal may wrap between intervals. |
| 111 | */ |
| 112 | cur->li_is_closed = 1; |
| 113 | |
| 114 | if (tfrc_lh_length(lh) == 1) /* due to RFC 3448, 6.3.1 */ |
| 115 | return 0; |
| 116 | |
Gerrit Renker | 2eeea7b | 2008-07-13 11:51:40 +0100 | [diff] [blame] | 117 | cur->li_length = len; |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 118 | tfrc_lh_calc_i_mean(lh); |
| 119 | |
| 120 | return (lh->i_mean < old_i_mean); |
| 121 | } |
| 122 | EXPORT_SYMBOL_GPL(tfrc_lh_update_i_mean); |
| 123 | |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 124 | /* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */ |
| 125 | static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur, |
| 126 | struct tfrc_rx_hist_entry *new_loss) |
| 127 | { |
| 128 | return dccp_delta_seqno(cur->li_seqno, new_loss->tfrchrx_seqno) > 0 && |
| 129 | (cur->li_is_closed || SUB16(new_loss->tfrchrx_ccval, cur->li_ccval) > 4); |
| 130 | } |
| 131 | |
| 132 | /** tfrc_lh_interval_add - Insert new record into the Loss Interval database |
| 133 | * @lh: Loss Interval database |
| 134 | * @rh: Receive history containing a fresh loss event |
| 135 | * @calc_first_li: Caller-dependent routine to compute length of first interval |
| 136 | * @sk: Used by @calc_first_li in caller-specific way (subtyping) |
| 137 | * Updates I_mean and returns 1 if a new interval has in fact been added to @lh. |
| 138 | */ |
| 139 | int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh, |
| 140 | u32 (*calc_first_li)(struct sock *), struct sock *sk) |
| 141 | { |
| 142 | struct tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new; |
| 143 | |
| 144 | if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh))) |
| 145 | return 0; |
| 146 | |
| 147 | new = tfrc_lh_demand_next(lh); |
| 148 | if (unlikely(new == NULL)) { |
| 149 | DCCP_CRIT("Cannot allocate/add loss record."); |
| 150 | return 0; |
| 151 | } |
| 152 | |
| 153 | new->li_seqno = tfrc_rx_hist_loss_prev(rh)->tfrchrx_seqno; |
| 154 | new->li_ccval = tfrc_rx_hist_loss_prev(rh)->tfrchrx_ccval; |
| 155 | new->li_is_closed = 0; |
| 156 | |
| 157 | if (++lh->counter == 1) |
| 158 | lh->i_mean = new->li_length = (*calc_first_li)(sk); |
| 159 | else { |
| 160 | cur->li_length = dccp_delta_seqno(cur->li_seqno, new->li_seqno); |
| 161 | new->li_length = dccp_delta_seqno(new->li_seqno, |
Gerrit Renker | 2eeea7b | 2008-07-13 11:51:40 +0100 | [diff] [blame] | 162 | tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno) + 1; |
Gerrit Renker | 8a9c7e9 | 2007-12-12 13:50:51 -0200 | [diff] [blame] | 163 | if (lh->counter > (2*LIH_SIZE)) |
| 164 | lh->counter -= LIH_SIZE; |
| 165 | |
| 166 | tfrc_lh_calc_i_mean(lh); |
| 167 | } |
| 168 | return 1; |
| 169 | } |
| 170 | EXPORT_SYMBOL_GPL(tfrc_lh_interval_add); |
| 171 | |
Gerrit Renker | 954c2db | 2007-12-12 14:06:14 -0200 | [diff] [blame] | 172 | int __init tfrc_li_init(void) |
Arnaldo Carvalho de Melo | cc4d6a3 | 2007-05-28 18:53:08 -0300 | [diff] [blame] | 173 | { |
Gerrit Renker | 954c2db | 2007-12-12 14:06:14 -0200 | [diff] [blame] | 174 | tfrc_lh_slab = kmem_cache_create("tfrc_li_hist", |
| 175 | sizeof(struct tfrc_loss_interval), 0, |
| 176 | SLAB_HWCACHE_ALIGN, NULL); |
| 177 | return tfrc_lh_slab == NULL ? -ENOBUFS : 0; |
Arnaldo Carvalho de Melo | cc4d6a3 | 2007-05-28 18:53:08 -0300 | [diff] [blame] | 178 | } |
| 179 | |
Gerrit Renker | 954c2db | 2007-12-12 14:06:14 -0200 | [diff] [blame] | 180 | void tfrc_li_exit(void) |
Arnaldo Carvalho de Melo | cc4d6a3 | 2007-05-28 18:53:08 -0300 | [diff] [blame] | 181 | { |
Gerrit Renker | 954c2db | 2007-12-12 14:06:14 -0200 | [diff] [blame] | 182 | if (tfrc_lh_slab != NULL) { |
| 183 | kmem_cache_destroy(tfrc_lh_slab); |
| 184 | tfrc_lh_slab = NULL; |
Arnaldo Carvalho de Melo | 276f2ed | 2007-11-28 11:15:40 -0200 | [diff] [blame] | 185 | } |
Arnaldo Carvalho de Melo | cc4d6a3 | 2007-05-28 18:53:08 -0300 | [diff] [blame] | 186 | } |