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