1 /** @file
2 * @brief Trickle timer library
3 *
4 * This implements Trickle timer as specified in RFC 6206
5 */
6
7 /*
8 * Copyright (c) 2016 Intel Corporation
9 *
10 * SPDX-License-Identifier: Apache-2.0
11 */
12
13 #include <zephyr/logging/log.h>
14 LOG_MODULE_REGISTER(net_trickle, CONFIG_NET_TRICKLE_LOG_LEVEL);
15
16 #include <errno.h>
17 #include <zephyr/sys/util.h>
18 #include <zephyr/random/random.h>
19
20 #include <zephyr/net/net_core.h>
21 #include <zephyr/net/trickle.h>
22
23 #define TICK_MAX ~0
24
25 static void trickle_timeout(struct k_work *work);
26
is_suppression_disabled(struct net_trickle * trickle)27 static inline bool is_suppression_disabled(struct net_trickle *trickle)
28 {
29 return trickle->k == NET_TRICKLE_INFINITE_REDUNDANCY;
30 }
31
is_tx_allowed(struct net_trickle * trickle)32 static inline bool is_tx_allowed(struct net_trickle *trickle)
33 {
34 return is_suppression_disabled(trickle) ||
35 (trickle->c < trickle->k);
36 }
37
get_end(struct net_trickle * trickle)38 static inline uint32_t get_end(struct net_trickle *trickle)
39 {
40 return trickle->Istart + trickle->I;
41 }
42
43 /* Returns a random time point t in [I/2 , I) */
get_t(uint32_t I)44 static uint32_t get_t(uint32_t I)
45 {
46 I >>= 1;
47
48 NET_DBG("[%d, %d)", I, I << 1);
49
50 return I + (sys_rand32_get() % I);
51 }
52
double_interval_timeout(struct net_trickle * trickle)53 static void double_interval_timeout(struct net_trickle *trickle)
54 {
55 uint32_t rand_time;
56 uint32_t last_end = get_end(trickle);
57
58 trickle->c = 0U;
59
60 NET_DBG("now %u (was at %u)", k_uptime_get_32(), last_end);
61
62 /* Check if we need to double the interval */
63 if (trickle->I <= (trickle->Imax_abs >> 1)) {
64 /* Double if I <= Imax/2 */
65 trickle->I <<= 1;
66
67 NET_DBG("double I %u", trickle->I);
68 } else {
69 trickle->I = trickle->Imax_abs;
70
71 NET_DBG("I %u", trickle->I);
72 }
73
74 /* Random t in [I/2, I) */
75 rand_time = get_t(trickle->I);
76
77 NET_DBG("doubling time %u", rand_time);
78
79 trickle->Istart = k_uptime_get_32() + rand_time;
80 trickle->double_to = false;
81
82 k_work_reschedule(&trickle->timer, K_MSEC(rand_time));
83
84 NET_DBG("last end %u new end %u for %u I %u",
85 last_end, get_end(trickle), trickle->Istart, trickle->I);
86 }
87
reschedule(struct net_trickle * trickle)88 static inline void reschedule(struct net_trickle *trickle)
89 {
90 uint32_t now = k_uptime_get_32();
91 uint32_t diff = get_end(trickle) - now;
92
93 NET_DBG("now %d end in %d", now, diff);
94
95 /* Did the clock wrap */
96 if ((int32_t)diff < 0) {
97 diff = 0U;
98 NET_DBG("Clock wrap");
99 }
100
101 trickle->double_to = true;
102
103 k_work_reschedule(&trickle->timer, K_MSEC(diff));
104 }
105
interval_timeout(struct net_trickle * trickle)106 static void interval_timeout(struct net_trickle *trickle)
107 {
108 NET_DBG("Trickle timeout at %d", k_uptime_get_32());
109
110 if (trickle->cb) {
111 NET_DBG("TX ok %d c(%u) < k(%u)",
112 is_tx_allowed(trickle), trickle->c, trickle->k);
113
114 trickle->cb(trickle, is_tx_allowed(trickle),
115 trickle->user_data);
116 }
117
118 if (net_trickle_is_running(trickle)) {
119 reschedule(trickle);
120 }
121 }
122
trickle_timeout(struct k_work * work)123 static void trickle_timeout(struct k_work *work)
124 {
125 struct k_work_delayable *dwork = k_work_delayable_from_work(work);
126 struct net_trickle *trickle = CONTAINER_OF(dwork,
127 struct net_trickle,
128 timer);
129
130 if (trickle->double_to) {
131 double_interval_timeout(trickle);
132 } else {
133 interval_timeout(trickle);
134 }
135 }
136
setup_new_interval(struct net_trickle * trickle)137 static void setup_new_interval(struct net_trickle *trickle)
138 {
139 uint32_t t;
140
141 trickle->c = 0U;
142
143 t = get_t(trickle->I);
144
145 trickle->Istart = k_uptime_get_32();
146
147 k_work_reschedule(&trickle->timer, K_MSEC(t));
148
149 NET_DBG("new interval at %d ends %d t %d I %d",
150 trickle->Istart,
151 get_end(trickle),
152 t,
153 trickle->I);
154 }
155
156 #define CHECK_IMIN(Imin) \
157 ((Imin < 2) || (Imin > (TICK_MAX >> 1)))
158
net_trickle_create(struct net_trickle * trickle,uint32_t Imin,uint8_t Imax,uint8_t k)159 int net_trickle_create(struct net_trickle *trickle,
160 uint32_t Imin,
161 uint8_t Imax,
162 uint8_t k)
163 {
164 if (!(trickle && Imax > 0 && k > 0 && !CHECK_IMIN(Imin))) {
165 return -EINVAL;
166 }
167
168 (void)memset(trickle, 0, sizeof(struct net_trickle));
169
170 trickle->Imin = Imin;
171 trickle->Imax = Imax;
172 trickle->Imax_abs = Imin << Imax;
173 trickle->k = k;
174
175 if (!trickle->Imax_abs) {
176 return -EINVAL;
177 }
178
179 NET_DBG("Imin %d Imax %u k %u Imax_abs %u",
180 trickle->Imin, trickle->Imax, trickle->k,
181 trickle->Imax_abs);
182
183 k_work_init_delayable(&trickle->timer, trickle_timeout);
184
185 return 0;
186 }
187
net_trickle_start(struct net_trickle * trickle,net_trickle_cb_t cb,void * user_data)188 int net_trickle_start(struct net_trickle *trickle,
189 net_trickle_cb_t cb,
190 void *user_data)
191 {
192 if (!(trickle && cb)) {
193 return -EINVAL;
194 }
195
196 trickle->cb = cb;
197 trickle->user_data = user_data;
198 trickle->double_to = false;
199
200 /* Random I in [Imin , Imax] */
201 trickle->I = trickle->Imin +
202 (sys_rand32_get() % (trickle->Imax_abs - trickle->Imin + 1));
203
204 setup_new_interval(trickle);
205
206 NET_DBG("start %d end %d in [%d , %d)",
207 trickle->Istart, get_end(trickle),
208 trickle->I >> 1, trickle->I);
209
210 return 0;
211 }
212
net_trickle_stop(struct net_trickle * trickle)213 int net_trickle_stop(struct net_trickle *trickle)
214 {
215 if (trickle == NULL) {
216 return -EINVAL;
217 }
218
219 k_work_cancel_delayable(&trickle->timer);
220
221 trickle->I = 0U;
222
223 return 0;
224 }
225
net_trickle_consistency(struct net_trickle * trickle)226 void net_trickle_consistency(struct net_trickle *trickle)
227 {
228 if (trickle == NULL) {
229 return;
230 }
231
232 if (trickle->c < 0xFF) {
233 trickle->c++;
234 }
235
236 NET_DBG("consistency %u", trickle->c);
237 }
238
net_trickle_inconsistency(struct net_trickle * trickle)239 void net_trickle_inconsistency(struct net_trickle *trickle)
240 {
241 if (trickle == NULL) {
242 return;
243 }
244
245 if (trickle->I != trickle->Imin) {
246 NET_DBG("inconsistency");
247
248 trickle->I = trickle->Imin;
249 }
250
251 setup_new_interval(trickle);
252 }
253
