Commit | Line | Data |
---|---|---|
ae6706f0 ACM |
1 | /* |
2 | * net/dccp/ccids/lib/loss_interval.c | |
3 | * | |
8a9c7e92 | 4 | * Copyright (c) 2007 The University of Aberdeen, Scotland, UK |
b2f41ff4 IM |
5 | * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. |
6 | * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> | |
ae6706f0 ACM |
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 | */ | |
66a377c5 | 14 | #include <net/sock.h> |
cc0a910b | 15 | #include "tfrc.h" |
ae6706f0 | 16 | |
8a9c7e92 GR |
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 | } | |
8a9c7e92 | 63 | |
8a9c7e92 GR |
64 | static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) |
65 | { | |
66 | u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; | |
67 | int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */ | |
68 | ||
959fd992 GR |
69 | if (k <= 0) |
70 | return; | |
71 | ||
72 | for (i = 0; i <= k; i++) { | |
8a9c7e92 GR |
73 | i_i = tfrc_lh_get_interval(lh, i); |
74 | ||
75 | if (i < k) { | |
76 | i_tot0 += i_i * tfrc_lh_weights[i]; | |
77 | w_tot += tfrc_lh_weights[i]; | |
78 | } | |
79 | if (i > 0) | |
80 | i_tot1 += i_i * tfrc_lh_weights[i-1]; | |
81 | } | |
82 | ||
8a9c7e92 GR |
83 | lh->i_mean = max(i_tot0, i_tot1) / w_tot; |
84 | } | |
85 | ||
86 | /** | |
87 | * tfrc_lh_update_i_mean - Update the `open' loss interval I_0 | |
410e27a4 | 88 | * For recomputing p: returns `true' if p > p_prev <=> 1/p < 1/p_prev |
8a9c7e92 | 89 | */ |
410e27a4 | 90 | u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) |
8a9c7e92 GR |
91 | { |
92 | struct tfrc_loss_interval *cur = tfrc_lh_peek(lh); | |
410e27a4 | 93 | u32 old_i_mean = lh->i_mean; |
2eeea7ba | 94 | s64 len; |
8a9c7e92 GR |
95 | |
96 | if (cur == NULL) /* not initialised */ | |
410e27a4 | 97 | return 0; |
8a9c7e92 | 98 | |
2eeea7ba | 99 | len = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq) + 1; |
8a9c7e92 | 100 | |
2eeea7ba | 101 | if (len - (s64)cur->li_length <= 0) /* duplicate or reordered */ |
410e27a4 | 102 | return 0; |
8a9c7e92 GR |
103 | |
104 | if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4) | |
105 | /* | |
106 | * Implements RFC 4342, 10.2: | |
107 | * If a packet S (skb) exists whose seqno comes `after' the one | |
108 | * starting the current loss interval (cur) and if the modulo-16 | |
109 | * distance from C(cur) to C(S) is greater than 4, consider all | |
110 | * subsequent packets as belonging to a new loss interval. This | |
111 | * test is necessary since CCVal may wrap between intervals. | |
112 | */ | |
113 | cur->li_is_closed = 1; | |
114 | ||
115 | if (tfrc_lh_length(lh) == 1) /* due to RFC 3448, 6.3.1 */ | |
410e27a4 | 116 | return 0; |
8a9c7e92 | 117 | |
2eeea7ba | 118 | cur->li_length = len; |
8a9c7e92 | 119 | tfrc_lh_calc_i_mean(lh); |
410e27a4 GR |
120 | |
121 | return (lh->i_mean < old_i_mean); | |
8a9c7e92 | 122 | } |
8a9c7e92 | 123 | |
8a9c7e92 GR |
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 | */ | |
410e27a4 GR |
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) | |
8a9c7e92 GR |
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))) | |
410e27a4 | 145 | return 0; |
8a9c7e92 GR |
146 | |
147 | new = tfrc_lh_demand_next(lh); | |
148 | if (unlikely(new == NULL)) { | |
149 | DCCP_CRIT("Cannot allocate/add loss record."); | |
410e27a4 | 150 | return 0; |
8a9c7e92 GR |
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, | |
2eeea7ba | 162 | tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno) + 1; |
8a9c7e92 GR |
163 | if (lh->counter > (2*LIH_SIZE)) |
164 | lh->counter -= LIH_SIZE; | |
165 | ||
166 | tfrc_lh_calc_i_mean(lh); | |
167 | } | |
410e27a4 | 168 | return 1; |
8a9c7e92 | 169 | } |
8a9c7e92 | 170 | |
954c2db8 | 171 | int __init tfrc_li_init(void) |
cc4d6a3a | 172 | { |
954c2db8 GR |
173 | tfrc_lh_slab = kmem_cache_create("tfrc_li_hist", |
174 | sizeof(struct tfrc_loss_interval), 0, | |
175 | SLAB_HWCACHE_ALIGN, NULL); | |
176 | return tfrc_lh_slab == NULL ? -ENOBUFS : 0; | |
cc4d6a3a ACM |
177 | } |
178 | ||
954c2db8 | 179 | void tfrc_li_exit(void) |
cc4d6a3a | 180 | { |
954c2db8 GR |
181 | if (tfrc_lh_slab != NULL) { |
182 | kmem_cache_destroy(tfrc_lh_slab); | |
183 | tfrc_lh_slab = NULL; | |
276f2edc | 184 | } |
cc4d6a3a | 185 | } |