diff options
Diffstat (limited to 'shared/n-acd/src/n-acd-probe.c')
| -rw-r--r-- | shared/n-acd/src/n-acd-probe.c | 636 |
1 files changed, 636 insertions, 0 deletions
diff --git a/shared/n-acd/src/n-acd-probe.c b/shared/n-acd/src/n-acd-probe.c new file mode 100644 index 00000000..8c233b56 --- /dev/null +++ b/shared/n-acd/src/n-acd-probe.c @@ -0,0 +1,636 @@ +/* + * IPv4 Address Conflict Detection + */ + +#include <assert.h> +#include <c-rbtree.h> +#include <endian.h> +#include <errno.h> +#include <inttypes.h> +#include <limits.h> +#include <netinet/if_ether.h> +#include <netinet/in.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <unistd.h> +#include "n-acd.h" +#include "n-acd-private.h" + +/* + * These parameters and timing intervals specified in RFC-5227. The original + * values are: + * + * PROBE_NUM 3 + * PROBE_WAIT 1s + * PROBE_MIN 1s + * PROBE_MAX 3s + * ANNOUNCE_NUM 3 + * ANNOUNCE_WAIT 2s + * ANNOUNCE_INTERVAL 2s + * MAX_CONFLICTS 10 + * RATE_LIMIT_INTERVAL 60s + * DEFEND_INTERVAL 10s + * + * If we assume a best-case and worst-case scenario for non-conflicted runs, we + * end up with a runtime between 4s and 9s to finish the probe. Then it still + * takes a fixed 4s to finish the announcements. + * + * RFC 5227 section 1.1: + * [...] (Note that the values listed here are fixed constants; they are + * not intended to be modifiable by implementers, operators, or end users. + * These constants are given symbolic names here to facilitate the writing + * of future standards that may want to reference this document with + * different values for these named constants; however, at the present time + * no such future standards exist.) [...] + * + * Unfortunately, no-one ever stepped up to write a "future standard" to revise + * the timings. A 9s timeout for successful link setups is not acceptable today. + * Hence, we will just go forward and ignore the proposed values. On both + * wired and wireless local links round-trip latencies of below 3ms are common. + * We require the caller to set a timeout multiplier, where 1 corresponds to a + * total probe time between 0.5 ms and 1.0 ms. On modern networks a multiplier + * of about 100 should be a reasonable default. To comply with the RFC select a + * multiplier of 9000. + */ +#define N_ACD_RFC_PROBE_NUM (3) +#define N_ACD_RFC_PROBE_WAIT_NSEC (UINT64_C(111111)) /* 1/9 ms */ +#define N_ACD_RFC_PROBE_MIN_NSEC (UINT64_C(111111)) /* 1/9 ms */ +#define N_ACD_RFC_PROBE_MAX_NSEC (UINT64_C(333333)) /* 3/9 ms */ +#define N_ACD_RFC_ANNOUNCE_NUM (3) +#define N_ACD_RFC_ANNOUNCE_WAIT_NSEC (UINT64_C(222222)) /* 2/9 ms */ +#define N_ACD_RFC_ANNOUNCE_INTERVAL_NSEC (UINT64_C(222222)) /* 2/9 ms */ +#define N_ACD_RFC_MAX_CONFLICTS (10) +#define N_ACD_RFC_RATE_LIMIT_INTERVAL_NSEC (UINT64_C(60000000000)) /* 60s */ +#define N_ACD_RFC_DEFEND_INTERVAL_NSEC (UINT64_C(10000000000)) /* 10s */ + +/** + * XXX + */ +_public_ int n_acd_probe_config_new(NAcdProbeConfig **configp) { + _cleanup_(n_acd_probe_config_freep) NAcdProbeConfig *config = NULL; + + config = malloc(sizeof(*config)); + if (!config) + return -ENOMEM; + + *config = (NAcdProbeConfig)N_ACD_PROBE_CONFIG_NULL(*config); + + *configp = config; + config = NULL; + return 0; +} + +/** + * XXX + */ +_public_ NAcdProbeConfig *n_acd_probe_config_free(NAcdProbeConfig *config) { + if (!config) + return NULL; + + free(config); + + return NULL; +} + +/** + * XXX + */ +_public_ void n_acd_probe_config_set_ip(NAcdProbeConfig *config, struct in_addr ip) { + config->ip = ip; +} + +/** + * XXX + */ +_public_ void n_acd_probe_config_set_timeout(NAcdProbeConfig *config, uint64_t msecs) { + config->timeout_msecs = msecs; +} + +static void n_acd_probe_schedule(NAcdProbe *probe, uint64_t n_timeout, unsigned int n_jitter) { + uint64_t n_time; + + timer_now(&probe->acd->timer, &n_time); + n_time += n_timeout; + + /* + * ACD specifies jitter values to reduce packet storms on the local + * link. This call accepts the maximum relative jitter value in + * nanoseconds as @n_jitter. We then use rand_r(3p) to get a + * pseudo-random jitter on top of the real timeout given as @n_timeout. + */ + if (n_jitter) { + uint64_t random; + + random = ((uint64_t)rand_r(&probe->acd->seed) << 32) | (uint64_t)rand_r(&probe->acd->seed); + n_time += random % n_jitter; + } + + timeout_schedule(&probe->timeout, &probe->acd->timer, n_time); +} + +static void n_acd_probe_unschedule(NAcdProbe *probe) { + timeout_unschedule(&probe->timeout); +} + +static bool n_acd_probe_is_unique(NAcdProbe *probe) { + NAcdProbe *sibling; + + if (!c_rbnode_is_linked(&probe->ip_node)) + return false; + + sibling = c_rbnode_entry(c_rbnode_next(&probe->ip_node), NAcdProbe, ip_node); + if (sibling && sibling->ip.s_addr == probe->ip.s_addr) + return false; + + sibling = c_rbnode_entry(c_rbnode_prev(&probe->ip_node), NAcdProbe, ip_node); + if (sibling && sibling->ip.s_addr == probe->ip.s_addr) + return false; + + return true; +} + +static int n_acd_probe_link(NAcdProbe *probe) { + int r; + + /* + * Make sure the kernel bpf map has space for at least one more + * entry. + */ + r = n_acd_ensure_bpf_map_space(probe->acd); + if (r) + return r; + + /* + * Link entry into context, indexed by its IP. Note that we allow + * duplicates just fine. It is up to you to decide whether to avoid + * duplicates, if you don't want them. Duplicates on the same context + * do not conflict with each other, though. + */ + { + CRBNode **slot, *parent; + NAcdProbe *other; + + slot = &probe->acd->ip_tree.root; + parent = NULL; + while (*slot) { + other = c_rbnode_entry(*slot, NAcdProbe, ip_node); + parent = *slot; + if (probe->ip.s_addr < other->ip.s_addr) + slot = &(*slot)->left; + else + slot = &(*slot)->right; + } + + c_rbtree_add(&probe->acd->ip_tree, parent, slot, &probe->ip_node); + } + + /* + * Add the ip address to the map, if it is not already there. + */ + if (n_acd_probe_is_unique(probe)) { + r = n_acd_bpf_map_add(probe->acd->fd_bpf_map, &probe->ip); + if (r) { + /* + * Make sure the IP address is linked in userspace iff + * it is linked in the kernel. + */ + c_rbnode_unlink(&probe->ip_node); + return r; + } + ++probe->acd->n_bpf_map; + } + + return 0; +} + +static void n_acd_probe_unlink(NAcdProbe *probe) { + int r; + + /* + * If this is the only probe for a given IP, remove the IP from the + * kernel BPF map. + */ + if (n_acd_probe_is_unique(probe)) { + r = n_acd_bpf_map_remove(probe->acd->fd_bpf_map, &probe->ip); + assert(r >= 0); + --probe->acd->n_bpf_map; + } + c_rbnode_unlink(&probe->ip_node); +} + +int n_acd_probe_new(NAcdProbe **probep, NAcd *acd, NAcdProbeConfig *config) { + _cleanup_(n_acd_probe_freep) NAcdProbe *probe = NULL; + int r; + + if (!config->ip.s_addr) + return N_ACD_E_INVALID_ARGUMENT; + + probe = malloc(sizeof(*probe)); + if (!probe) + return -ENOMEM; + + *probe = (NAcdProbe)N_ACD_PROBE_NULL(*probe); + probe->acd = n_acd_ref(acd); + probe->ip = config->ip; + + /* + * We use the provided timeout-length as multiplier for all our + * timeouts. The provided timeout defines the maximum length of an + * entire probe-interval until the first announcement. Given the + * spec-provided parameters, this ends up as: + * + * PROBE_WAIT + PROBE_MAX + PROBE_MAX + ANNOUNCE_WAIT + * = 1s + 3s + 3s + 2s + * = 9s + * + * Hence, the default value for this timeout is 9000ms, which just + * ends up matching the spec-provided values. + * + * What we now semantically do is divide this timeout by 1ns/1000000. + * This first turns it into nanoseconds, then strips the unit by + * turning it into a multiplier. However, rather than performing the + * division here, we multiplier all our timeouts by 1000000 statically + * at compile time. Therefore, we can use the user-provided timeout as + * unmodified multiplier. No conversion necessary. + */ + probe->timeout_multiplier = config->timeout_msecs; + + r = n_acd_probe_link(probe); + if (r) + return r; + + /* + * Now that everything is set up, we have to send the first probe. This + * is done after ~PROBE_WAIT seconds, hence we schedule our timer. + * In case no timeout-multiplier is set, we pretend we already sent all + * probes successfully and schedule the timer so we proceed with the + * announcements. We must schedule a fake timer there, since we are not + * allowed to advance the state machine outside of n_acd_dispatch(). + */ + if (probe->timeout_multiplier) { + probe->n_iteration = 0; + n_acd_probe_schedule(probe, + 0, + probe->timeout_multiplier * N_ACD_RFC_PROBE_WAIT_NSEC); + } else { + probe->n_iteration = N_ACD_RFC_PROBE_NUM; + n_acd_probe_schedule(probe, 0, 0); + } + + *probep = probe; + probe = NULL; + return 0; +} + +/** + * XXX + */ +_public_ NAcdProbe *n_acd_probe_free(NAcdProbe *probe) { + NAcdEventNode *node, *t_node; + + if (!probe) + return NULL; + + c_list_for_each_entry_safe(node, t_node, &probe->event_list, probe_link) + n_acd_event_node_free(node); + + n_acd_probe_unschedule(probe); + n_acd_probe_unlink(probe); + probe->acd = n_acd_unref(probe->acd); + free(probe); + + return NULL; +} + +int n_acd_probe_raise(NAcdProbe *probe, NAcdEventNode **nodep, unsigned int event) { + _cleanup_(n_acd_event_node_freep) NAcdEventNode *node = NULL; + int r; + + r = n_acd_raise(probe->acd, &node, event); + if (r) + return r; + + switch (event) { + case N_ACD_EVENT_READY: + node->event.ready.probe = probe; + break; + case N_ACD_EVENT_USED: + node->event.used.probe = probe; + break; + case N_ACD_EVENT_DEFENDED: + node->event.defended.probe = probe; + break; + case N_ACD_EVENT_CONFLICT: + node->event.conflict.probe = probe; + break; + default: + assert(0); + return -EIO; + } + + c_list_link_tail(&probe->event_list, &node->probe_link); + + if (nodep) + *nodep = node; + node = NULL; + return 0; +} + +int n_acd_probe_handle_timeout(NAcdProbe *probe) { + int r; + + switch (probe->state) { + case N_ACD_PROBE_STATE_PROBING: + /* + * We are still PROBING. We send 3 probes with a random timeout + * scheduled between each. If, after a fixed timeout, we did + * not receive any conflict we consider the probing successful. + */ + if (probe->n_iteration < N_ACD_RFC_PROBE_NUM) { + /* + * We have not sent all 3 probes, yet. A timer fired, + * so we are ready to send the next probe. If this is + * the third probe, schedule a timer for ANNOUNCE_WAIT + * to give other peers a chance to answer. If this is + * not the third probe, wait between PROBE_MIN and + * PROBE_MAX for the next probe. + */ + + r = n_acd_send(probe->acd, &probe->ip, NULL); + if (r) { + if (r != -N_ACD_E_DROPPED) + return r; + + /* + * Packet was dropped, and we know about it. It + * never reached the network. Reasons are + * manifold, and n_acd_send() raises events if + * necessary. + * From a probe-perspective, we simply pretend + * we never sent the probe and schedule a + * timeout for the next probe, effectively + * doubling a single probe-interval. + */ + } else { + /* Successfully sent, so advance counter. */ + ++probe->n_iteration; + } + + if (probe->n_iteration < N_ACD_RFC_PROBE_NUM) + n_acd_probe_schedule(probe, + probe->timeout_multiplier * N_ACD_RFC_PROBE_MIN_NSEC, + probe->timeout_multiplier * (N_ACD_RFC_PROBE_MAX_NSEC - N_ACD_RFC_PROBE_MIN_NSEC)); + else + n_acd_probe_schedule(probe, + probe->timeout_multiplier * N_ACD_RFC_ANNOUNCE_WAIT_NSEC, + 0); + } else { + /* + * All 3 probes succeeded and we waited enough to + * consider this address usable by now. Do not announce + * the address, yet. We must first give the caller a + * chance to configure the address (so they can answer + * ARP requests), before announcing it. + */ + r = n_acd_probe_raise(probe, NULL, N_ACD_EVENT_READY); + if (r) + return r; + + probe->state = N_ACD_PROBE_STATE_CONFIGURING; + } + + break; + + case N_ACD_PROBE_STATE_ANNOUNCING: + /* + * We are ANNOUNCING, meaning the caller configured the address + * on the interface and is actively using it. We send 3 + * announcements out, in a short interval, and then just + * perform passive conflict detection. + * Note that once all 3 announcements are sent, we no longer + * schedule a timer, so this part should not trigger, anymore. + */ + + r = n_acd_send(probe->acd, &probe->ip, &probe->ip); + if (r) { + if (r != -N_ACD_E_DROPPED) + return r; + + /* + * See above in STATE_PROBING for details. We know the + * packet was never sent, so we simply try again after + * extending the timer. + */ + } else { + /* Successfully sent, so advance counter. */ + ++probe->n_iteration; + } + + if (probe->n_iteration < N_ACD_RFC_ANNOUNCE_NUM) { + /* + * Announcements are always scheduled according to the + * time-intervals specified in the spec. We always use + * the RFC5227-mandated multiplier. + * If you reconsider this, note that timeout_multiplier + * might be 0 here. + */ + n_acd_probe_schedule(probe, + N_ACD_TIMEOUT_RFC5227 * N_ACD_RFC_ANNOUNCE_INTERVAL_NSEC, + 0); + } + + break; + + case N_ACD_PROBE_STATE_CONFIGURING: + case N_ACD_PROBE_STATE_FAILED: + default: + /* + * There are no timeouts in these states. If we trigger one, + * something is fishy. + */ + assert(0); + return -EIO; + } + + return 0; +} + +int n_acd_probe_handle_packet(NAcdProbe *probe, struct ether_arp *packet, bool hard_conflict) { + NAcdEventNode *node; + uint64_t now; + int r; + + timer_now(&probe->acd->timer, &now); + + switch (probe->state) { + case N_ACD_PROBE_STATE_PROBING: + /* + * Regardless whether this is a hard or soft conflict, we must + * treat this as a probe failure. That is, notify the caller of + * the conflict and wait for further instructions. We do not + * react to this, until the caller tells us what to do, but we + * do stop sending further probes. + */ + r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_USED); + if (r) + return r; + + node->event.used.sender = node->sender; + node->event.used.n_sender = ETH_ALEN; + memcpy(node->sender, packet->arp_sha, ETH_ALEN); + + n_acd_probe_unschedule(probe); + n_acd_probe_unlink(probe); + probe->state = N_ACD_PROBE_STATE_FAILED; + + break; + + case N_ACD_PROBE_STATE_CONFIGURING: + /* + * We are waiting for the caller to configure the interface and + * start ANNOUNCING. In this state, we cannot defend the + * address as that would indicate that it is ready to be used, + * and we cannot signal CONFLICT or USED as the caller may + * already have started to use the address (and may have + * configured the engine to always defend it, which means they + * should be able to rely on never losing it after READY). + * Simply drop the event, and rely on the anticipated ANNOUNCE + * to trigger it again. + */ + + break; + + case N_ACD_PROBE_STATE_ANNOUNCING: { + /* + * We were already instructed to announce the address, which + * means the address is configured and in use. Hence, the + * caller is responsible to serve regular ARP queries. Meaning, + * we can ignore any soft conflicts (other peers doing ACD). + * + * But if we see a hard-conflict, we either defend the address + * according to the caller's instructions, or we report the + * conflict and bail out. + */ + bool conflict = false, rate_limited = false; + + if (!hard_conflict) + break; + + rate_limited = now < probe->last_defend + N_ACD_RFC_DEFEND_INTERVAL_NSEC; + + switch (probe->defend) { + case N_ACD_DEFEND_NEVER: + conflict = true; + break; + case N_ACD_DEFEND_ONCE: + if (rate_limited) { + conflict = true; + break; + } + + /* fallthrough */ + case N_ACD_DEFEND_ALWAYS: + if (!rate_limited) { + r = n_acd_send(probe->acd, &probe->ip, &probe->ip); + if (r) { + if (r != -N_ACD_E_DROPPED) + return r; + + if (probe->defend == N_ACD_DEFEND_ONCE) { + conflict = true; + break; + } + } + + if (r != -N_ACD_E_DROPPED) + probe->last_defend = now; + } + + r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_DEFENDED); + if (r) + return r; + + node->event.defended.sender = node->sender; + node->event.defended.n_sender = ETH_ALEN; + memcpy(node->sender, packet->arp_sha, ETH_ALEN); + + break; + } + + if (conflict) { + r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_CONFLICT); + if (r) + return r; + + node->event.conflict.sender = node->sender; + node->event.conflict.n_sender = ETH_ALEN; + memcpy(node->sender, packet->arp_sha, ETH_ALEN); + + n_acd_probe_unschedule(probe); + n_acd_probe_unlink(probe); + probe->state = N_ACD_PROBE_STATE_FAILED; + } + + break; + } + + case N_ACD_PROBE_STATE_FAILED: + default: + /* + * We are not listening for packets in these states. If we receive one, + * something is fishy. + */ + assert(0); + return -EIO; + } + + return 0; +} + +/** + * n_acd_probe_set_userdata - XXX + */ +_public_ void n_acd_probe_set_userdata(NAcdProbe *probe, void *userdata) { + probe->userdata = userdata; +} + +/** + * n_acd_probe_get_userdata - XXX + */ +_public_ void n_acd_probe_get_userdata(NAcdProbe *probe, void **userdatap) { + *userdatap = probe->userdata; +} + +/** + * n_acd_probe_announce() - announce the configured IP address + * @probe: probe object + * @defend: defence policy + * + * Announce the IP address on the local link, and start defending it according + * to the given policy, which mut be one of N_ACD_DEFEND_ONCE, + * N_ACD_DEFEND_NEVER, or N_ACD_DEFEND_ALWAYS. + * + * This must be called in response to an N_ACD_EVENT_READY event, and only + * after the given address has been configured on the given network interface. + * + * Return: 0 on success, N_ACD_E_INVALID_ARGUMENT in case the defence policy + * is invalid, negative error code on failure. + */ +_public_ int n_acd_probe_announce(NAcdProbe *probe, unsigned int defend) { + if (defend >= _N_ACD_DEFEND_N) + return N_ACD_E_INVALID_ARGUMENT; + + probe->state = N_ACD_PROBE_STATE_ANNOUNCING; + probe->defend = defend; + probe->n_iteration = 0; + + /* + * We must schedule a fake-timeout, since we are not allowed to + * advance the state-machine outside of n_acd_dispatch(). + */ + n_acd_probe_schedule(probe, 0, 0); + + return 0; +} |