path: root/shared/n-acd/src/n-acd-probe.c

/*
 * IPv4 Address Conflict Detection
 *
 * This file implements the probe object. A probe is basically the
 * state-machine of a single ACD run. It takes an address to probe for, checks
 * for conflicts and then defends it once configured.
 */

#include <assert.h>
#include <c-rbtree.h>
#include <c-stdaux.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 are 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 */

/**
 * n_acd_probe_config_new() - create probe configuration
 * @configp:                    output argument for new probe configuration
 *
 * This creates a new probe configuration. It will be returned in @configp to
 * the caller, which upon return fully owns the object.
 *
 * A probe configuration collects parameters for probes. It never validates the
 * input, but this is left to the consumer of the configuration to do.
 *
 * Return: 0 on success, negative error code on failure.
 */
_c_public_ int n_acd_probe_config_new(NAcdProbeConfig **configp) {
        _c_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;
}

/**
 * n_acd_probe_config_free() - destroy probe configuration
 * @config:                     configuration to operate on, or NULL
 *
 * This destroys the probe configuration and all associated objects. If @config
 * is NULL, this is a no-op.
 *
 * Return: NULL is returned.
 */
_c_public_ NAcdProbeConfig *n_acd_probe_config_free(NAcdProbeConfig *config) {
        if (!config)
                return NULL;

        free(config);

        return NULL;
}

/**
 * n_acd_probe_config_set_ip() - set ip property
 * @config:                     configuration to operate on
 * @ip:                         ip to set
 *
 * This sets the IP property to the value `ip`. The address is copied into the
 * configuration object. No validation is performed.
 *
 * The IP property selects the IP address that a probe checks for. It is the
 * caller's responsibility to guarantee the address is valid and can be used.
 */
_c_public_ void n_acd_probe_config_set_ip(NAcdProbeConfig *config, struct in_addr ip) {
        config->ip = ip;
}

/**
 * n_acd_probe_config_set_timeout() - set timeout property
 * @config:                     configuration to operate on
 * @msecs:                      timeout to set, in milliseconds
 *
 * This sets the timeout to use for a conflict detection probe. The
 * specification default is provided as `N_ACD_TIMEOUT_RFC5227` and corresponds
 * to 9 seconds.
 *
 * If set to 0, conflict detection is skipped and the address is immediately
 * advertised and defended.
 *
 * Depending on the transport used, the API user should select a suitable
 * timeout. Since `ACD` only operates on the link layer, timeouts in the
 * hundreds of milliseconds range should be more than enough for any modern
 * network. Note that increasing this value directly affects the time it takes
 * to connect to a network, since an address should not be used unless conflict
 * detection finishes.
 *
 * Using the specification default is **discouraged**. It is way too slow and
 * not appropriate for modern networks.
 *
 * Default value is `N_ACD_TIMEOUT_RFC5227`.
 */
_c_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);
                c_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) {
        _c_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;
}

/**
 * n_acd_probe_free() - destroy a probe
 * @probe:                      probe to operate on, or NULL
 *
 * This destroys the probe specified by @probe. All operations are immediately
 * ceded and all associated objects are released.
 *
 * If @probe is NULL, this is a no-op.
 *
 * This function will flush all events associated with @probe from the event
 * queue. That is, no events will be returned for this @probe anymore.
 *
 * Return: NULL is returned.
 */
_c_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) {
        _c_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:
                c_assert(0);
                return -ENOTRECOVERABLE;
        }

        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.
                 */
                c_assert(0);
                return -ENOTRECOVERABLE;
        }

        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.
                 */
                c_assert(0);
                return -ENOTRECOVERABLE;
        }

        return 0;
}

/**
 * n_acd_probe_set_userdata - set userdata
 * @probe:                      probe to operate on
 * @userdata:                   userdata pointer
 *
 * This can be used to set a caller-controlled user-data pointer on @probe. The
 * value of the pointer is never inspected or used by `n-acd` and is fully
 * under control of the caller.
 *
 * The default value is NULL.
 */
_c_public_ void n_acd_probe_set_userdata(NAcdProbe *probe, void *userdata) {
        probe->userdata = userdata;
}

/**
 * n_acd_probe_get_userdata - get userdata
 * @probe:                      probe to operate on
 *
 * This queries the userdata pointer that was previously set through
 * n_acd_probe_set_userdata().
 *
 * The default value is NULL.
 *
 * Return: The stored userdata pointer is returned.
 */
_c_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 to operate on
 * @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.
 */
_c_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;
}