2 * Author: Steven Barth <steven at midlink.org>
4 * Copyright 2015 Deutsche Telekom AG
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
26 // Group comparator for AVL-tree
27 static int compare_groups(const void *k1
, const void *k2
, __unused
void *ptr
)
29 return memcmp(k1
, k2
, sizeof(struct in6_addr
));
32 // Remove a source-definition for a group
33 static void querier_remove_source(struct group
*group
, struct group_source
*source
)
35 --group
->source_count
;
36 list_del(&source
->head
);
40 // Clear all sources of a certain group
41 static void querier_clear_sources(struct group
*group
)
43 struct group_source
*s
, *n
;
44 list_for_each_entry_safe(s
, n
, &group
->sources
, head
)
45 querier_remove_source(group
, s
);
48 // Remove a group and all associated sources from the group state
49 static void querier_remove_group(struct groups
*groups
, struct group
*group
, omgp_time_t now
)
51 querier_clear_sources(group
);
52 group
->exclude_until
= 0;
54 if (groups
->cb_update
)
55 groups
->cb_update(groups
, group
, now
);
57 avl_delete(&groups
->groups
, &group
->node
);
61 // Expire a group and / or its associated sources depending on the current time
62 static omgp_time_t
expire_group(struct groups
*groups
, struct group
*group
,
63 omgp_time_t now
, omgp_time_t next_event
)
65 struct groups_config
*cfg
= IN6_IS_ADDR_V4MAPPED(&group
->addr
) ? &groups
->cfg_v4
: &groups
->cfg_v6
;
66 omgp_time_t llqi
= now
+ cfg
->last_listener_query_interval
;
67 omgp_time_t llqt
= now
+ (cfg
->last_listener_query_interval
* cfg
->last_listener_query_count
);
69 // Handle group and source-specific query retransmission
70 struct list_head suppressed
= LIST_HEAD_INIT(suppressed
);
71 struct list_head unsuppressed
= LIST_HEAD_INIT(unsuppressed
);
72 struct group_source
*s
, *s2
;
74 if (group
->next_source_transmit
> 0 && group
->next_source_transmit
<= now
) {
75 group
->next_source_transmit
= 0;
77 list_for_each_entry_safe(s
, s2
, &group
->sources
, head
) {
78 if (s
->retransmit
> 0) {
79 list_move_tail(&s
->head
, (s
->include_until
> llqt
) ? &suppressed
: &unsuppressed
);
83 if (s
->retransmit
> 0)
84 group
->next_source_transmit
= llqi
;
88 if (group
->next_source_transmit
> 0 && group
->next_source_transmit
< next_event
)
89 next_event
= group
->next_source_transmit
;
91 // Handle group-specific query retransmission
92 if (group
->retransmit
> 0 && group
->next_generic_transmit
<= now
) {
93 group
->next_generic_transmit
= 0;
96 groups
->cb_query(groups
, &group
->addr
, NULL
, group
->exclude_until
> llqt
);
100 if (group
->retransmit
> 0)
101 group
->next_generic_transmit
= llqi
;
103 // Skip suppresed source-specific query (RFC 3810 7.6.3.2)
104 list_splice_init(&suppressed
, &group
->sources
);
107 if (group
->next_generic_transmit
> 0 && group
->next_generic_transmit
< next_event
)
108 next_event
= group
->next_generic_transmit
;
110 if (!list_empty(&suppressed
)) {
111 if (groups
->cb_query
)
112 groups
->cb_query(groups
, &group
->addr
, &suppressed
, true);
114 list_splice(&suppressed
, &group
->sources
);
117 if (!list_empty(&unsuppressed
)) {
118 if (groups
->cb_query
)
119 groups
->cb_query(groups
, &group
->addr
, &unsuppressed
, false);
121 list_splice(&unsuppressed
, &group
->sources
);
124 // Handle source and group expiry
125 bool changed
= false;
126 if (group
->exclude_until
> 0) {
127 if (group_is_included(group
, now
)) {
128 // Leaving exclude mode
129 group
->exclude_until
= 0;
131 } else if (group
->exclude_until
< next_event
) {
132 next_event
= group
->exclude_until
;
136 list_for_each_entry_safe(s
, s2
, &group
->sources
, head
) {
137 if (s
->include_until
> 0) {
138 if (!source_is_included(s
, now
)) {
139 s
->include_until
= 0;
141 } else if (s
->include_until
< next_event
) {
142 next_event
= s
->include_until
;
146 if (group
->exclude_until
== 0 && s
->include_until
== 0)
147 querier_remove_source(group
, s
);
150 if (group
->exclude_until
== 0 && group
->source_count
== 0)
151 querier_remove_group(groups
, group
, now
);
152 else if (changed
&& groups
->cb_update
)
153 groups
->cb_update(groups
, group
, now
);
158 // Rearm the global groups-timer if the next event is before timer expiration
159 static void rearm_timer(struct groups
*groups
, int msecs
)
161 int64_t remain
= uloop_timeout_remaining64(&groups
->timer
);
162 if (remain
< 0 || remain
>= msecs
)
163 uloop_timeout_set(&groups
->timer
, msecs
);
166 // Expire all groups of a group-state (called by timer as callback)
167 static void expire_groups(struct uloop_timeout
*t
)
169 struct groups
*groups
= container_of(t
, struct groups
, timer
);
170 omgp_time_t now
= omgp_time();
171 omgp_time_t next_event
= now
+ 3600 * OMGP_TIME_PER_SECOND
;
173 struct group
*group
, *n
;
174 avl_for_each_element_safe(&groups
->groups
, group
, node
, n
)
175 next_event
= expire_group(groups
, group
, now
, next_event
);
177 rearm_timer(groups
, (next_event
> now
) ? next_event
- now
: 0);
180 // Initialize a group-state
181 void groups_init(struct groups
*groups
)
183 avl_init(&groups
->groups
, compare_groups
, false, NULL
);
184 groups
->timer
.cb
= expire_groups
;
186 groups_update_config(groups
, false, OMGP_TIME_PER_SECOND
/ 10,
187 125 * OMGP_TIME_PER_SECOND
, 2);
188 groups_update_config(groups
, true, OMGP_TIME_PER_SECOND
/ 10,
189 125 * OMGP_TIME_PER_SECOND
, 2);
192 // Cleanup a group-state
193 void groups_deinit(struct groups
*groups
)
195 omgp_time_t now
= omgp_time();
196 struct group
*group
, *safe
;
197 avl_for_each_element_safe(&groups
->groups
, group
, node
, safe
)
198 querier_remove_group(groups
, group
, now
);
199 uloop_timeout_cancel(&groups
->timer
);
202 // Get group-object for a given group, create if requested
203 static struct group
* groups_get_group(struct groups
*groups
,
204 const struct in6_addr
*addr
, bool *created
)
206 struct group
*group
= avl_find_element(&groups
->groups
, addr
, group
, node
);
207 if (!group
&& created
&& (group
= calloc(1, sizeof(*group
)))) {
209 group
->node
.key
= &group
->addr
;
210 avl_insert(&groups
->groups
, &group
->node
);
212 INIT_LIST_HEAD(&group
->sources
);
214 } else if (created
) {
220 // Get source-object for a given source, create if requested
221 static struct group_source
* groups_get_source(struct groups
*groups
,
222 struct group
*group
, const struct in6_addr
*addr
, bool *created
)
224 struct group_source
*c
, *source
= NULL
;
225 group_for_each_source(c
, group
)
226 if (IN6_ARE_ADDR_EQUAL(&c
->addr
, addr
))
229 if (!source
&& created
&& group
->source_count
< groups
->source_limit
&&
230 (source
= calloc(1, sizeof(*source
)))) {
231 source
->addr
= *addr
;
232 list_add_tail(&source
->head
, &group
->sources
);
233 ++group
->source_count
;
235 } else if (created
) {
242 // Update the IGMP/MLD timers of a group-state
243 void groups_update_config(struct groups
*groups
, bool v6
,
244 omgp_time_t query_response_interval
, omgp_time_t query_interval
, int robustness
)
246 struct groups_config
*cfg
= v6
? &groups
->cfg_v6
: &groups
->cfg_v4
;
247 cfg
->query_response_interval
= query_response_interval
;
248 cfg
->query_interval
= query_interval
;
249 cfg
->robustness
= robustness
;
250 cfg
->last_listener_query_count
= cfg
->robustness
;
251 cfg
->last_listener_query_interval
= 1 * OMGP_TIME_PER_SECOND
;
254 // Update timers for a given group (called when receiving queries from other queriers)
255 void groups_update_timers(struct groups
*groups
,
256 const struct in6_addr
*groupaddr
,
257 const struct in6_addr
*addrs
, size_t len
)
259 char addrbuf
[INET6_ADDRSTRLEN
];
260 inet_ntop(AF_INET6
, groupaddr
, addrbuf
, sizeof(addrbuf
));
261 struct group
*group
= groups_get_group(groups
, groupaddr
, NULL
);
263 L_WARN("%s: failed to update timer: no such group %s", __FUNCTION__
, addrbuf
);
267 struct groups_config
*cfg
= IN6_IS_ADDR_V4MAPPED(&group
->addr
) ? &groups
->cfg_v4
: &groups
->cfg_v6
;
268 omgp_time_t now
= omgp_time();
269 omgp_time_t llqt
= now
+ (cfg
->last_listener_query_count
* cfg
->last_listener_query_interval
);
272 if (group
->exclude_until
> llqt
)
273 group
->exclude_until
= llqt
;
275 for (size_t i
= 0; i
< len
; ++i
) {
276 struct group_source
*source
= groups_get_source(groups
, group
, &addrs
[i
], NULL
);
278 L_WARN("%s: failed to update timer: unknown sources for group %s", __FUNCTION__
, addrbuf
);
282 if (source
->include_until
> llqt
)
283 source
->include_until
= llqt
;
287 rearm_timer(groups
, llqt
- now
);
290 // Update state of a given group (on reception of node's IGMP/MLD packets)
291 void groups_update_state(struct groups
*groups
,
292 const struct in6_addr
*groupaddr
,
293 const struct in6_addr
*addrs
, size_t len
,
294 enum groups_update update
)
296 bool created
= false, changed
= false;
297 char addrbuf
[INET6_ADDRSTRLEN
];
298 inet_ntop(AF_INET6
, groupaddr
, addrbuf
, sizeof(addrbuf
));
299 L_DEBUG("%s: %s (+%d sources) => %d", __FUNCTION__
, addrbuf
, (int)len
, update
);
301 struct group
*group
= groups_get_group(groups
, groupaddr
, &created
);
303 L_ERR("querier_state: failed to allocate group for %s", addrbuf
);
310 omgp_time_t now
= omgp_time();
311 omgp_time_t next_event
= OMGP_TIME_MAX
;
312 struct groups_config
*cfg
= IN6_IS_ADDR_V4MAPPED(&group
->addr
) ? &groups
->cfg_v4
: &groups
->cfg_v6
;
314 // Backwards compatibility modes
315 if (group
->compat_v2_until
> now
|| group
->compat_v1_until
> now
) {
316 if (update
== UPDATE_BLOCK
)
319 if (group
->compat_v1_until
> now
&& (update
== UPDATE_DONE
|| update
== UPDATE_TO_IN
))
322 if (update
== UPDATE_TO_EX
)
326 if (update
== UPDATE_REPORT
|| update
== UPDATE_REPORT_V1
|| update
== UPDATE_DONE
) {
327 omgp_time_t compat_until
= now
+ cfg
->query_response_interval
+
328 (cfg
->robustness
* cfg
->query_interval
);
330 if (update
== UPDATE_REPORT_V1
)
331 group
->compat_v1_until
= compat_until
;
332 else if (update
== UPDATE_REPORT
)
333 group
->compat_v2_until
= compat_until
;
335 update
= (update
== UPDATE_DONE
) ? UPDATE_TO_IN
: UPDATE_IS_EXCLUDE
;
339 bool include
= group
->exclude_until
<= now
;
340 bool is_include
= update
== UPDATE_IS_INCLUDE
|| update
== UPDATE_TO_IN
|| update
== UPDATE_ALLOW
;
342 int llqc
= cfg
->last_listener_query_count
;
343 omgp_time_t mali
= now
+ (cfg
->robustness
* cfg
->query_interval
) + cfg
->query_response_interval
;
344 omgp_time_t llqt
= now
+ (cfg
->last_listener_query_interval
* llqc
);
347 struct list_head saved
= LIST_HEAD_INIT(saved
);
348 struct list_head queried
= LIST_HEAD_INIT(queried
);
349 for (size_t i
= 0; i
< len
; ++i
) {
350 bool *create
= (include
&& update
== UPDATE_BLOCK
) ? NULL
: &created
;
351 struct group_source
*source
= groups_get_source(groups
, group
, &addrs
[i
], create
);
353 if (include
&& update
== UPDATE_BLOCK
) {
355 list_move_tail(&source
->head
, &queried
);
359 groups_update_state(groups
, groupaddr
, NULL
, 0, false);
360 L_WARN("querier: failed to allocate source for %s, fallback to ASM", addrbuf
);
366 else if (include
&& update
== UPDATE_TO_EX
)
369 if (source
->include_until
<= now
&& update
== UPDATE_SET_IN
) {
370 source
->include_until
= mali
;
372 } else if (source
->include_until
> now
&& update
== UPDATE_SET_EX
) {
373 source
->include_until
= now
;
377 if (!include
&& (update
== UPDATE_BLOCK
|| update
== UPDATE_TO_EX
) &&
378 (created
|| source
->include_until
> now
))
381 if ((is_include
|| (!include
&& created
))) {
382 if (source
->include_until
<= now
)
385 source
->include_until
= (is_include
|| update
== UPDATE_IS_EXCLUDE
)
386 ? mali
: group
->exclude_until
;
388 if (next_event
> mali
)
393 list_move_tail(&source
->head
, &queried
);
394 else if (update
== UPDATE_IS_EXCLUDE
|| update
== UPDATE_TO_EX
||
395 update
== UPDATE_SET_EX
|| update
== UPDATE_SET_IN
)
396 list_move_tail(&source
->head
, &saved
);
400 if (update
== UPDATE_IS_EXCLUDE
|| update
== UPDATE_TO_EX
|| update
== UPDATE_SET_EX
) {
401 if (include
|| !list_empty(&group
->sources
))
404 querier_clear_sources(group
);
405 list_splice(&saved
, &group
->sources
);
406 group
->exclude_until
= mali
;
408 if (next_event
> mali
)
412 if (update
== UPDATE_SET_IN
) {
413 if (!include
|| !list_empty(&group
->sources
)) {
418 querier_clear_sources(group
);
419 list_splice(&saved
, &group
->sources
);
420 group
->exclude_until
= now
;
424 if (update
== UPDATE_TO_IN
) {
425 struct group_source
*source
, *n
;
426 list_for_each_entry_safe(source
, n
, &group
->sources
, head
) {
427 if (source
->include_until
<= now
)
431 for (i
= 0; i
< len
&& !IN6_ARE_ADDR_EQUAL(&source
->addr
, &addrs
[i
]); ++i
);
433 list_move_tail(&source
->head
, &queried
);
437 if (!list_empty(&queried
)) {
438 struct group_source
*source
;
439 list_for_each_entry(source
, &queried
, head
) {
440 if (source
->include_until
> llqt
)
441 source
->include_until
= llqt
;
443 group
->next_source_transmit
= now
;
444 source
->retransmit
= llqc
;
448 list_splice(&queried
, &group
->sources
);
451 if (!include
&& update
== UPDATE_TO_IN
) {
452 if (group
->exclude_until
> llqt
)
453 group
->exclude_until
= llqt
;
455 group
->next_generic_transmit
= now
;
456 group
->retransmit
= llqc
;
460 if (changed
&& groups
->cb_update
)
461 groups
->cb_update(groups
, group
, now
);
463 if (group_is_included(group
, now
) && group
->source_count
== 0)
466 if (next_event
< OMGP_TIME_MAX
)
467 rearm_timer(groups
, next_event
- now
);
470 L_DEBUG("%s: %s => %s (+%d sources)", __FUNCTION__
, addrbuf
,
471 (group_is_included(group
, now
)) ? "included" : "excluded",
472 (int)group
->source_count
);
476 // Get group object of a given group
477 const struct group
* groups_get(struct groups
*groups
, const struct in6_addr
*addr
)
479 return groups_get_group(groups
, addr
, NULL
);
482 // Test if a group (and source) is requested in the current group state
483 // (i.e. for deciding if it should be routed / forwarded)
484 bool groups_includes_group(struct groups
*groups
, const struct in6_addr
*addr
,
485 const struct in6_addr
*src
, omgp_time_t time
)
487 struct group
*group
= groups_get_group(groups
, addr
, NULL
);
489 if (!src
&& (!group_is_included(group
, time
) || group
->source_count
> 0))
492 struct group_source
*source
= groups_get_source(groups
, group
, src
, NULL
);
493 if ((!group_is_included(group
, time
) && (!source
|| source_is_included(source
, time
))) ||
494 (group_is_included(group
, time
) && source
&& source_is_included(source
, time
)))