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