summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/basic/c-rbtree.c679
-rw-r--r--src/basic/c-rbtree.h297
-rw-r--r--src/libudev/libudev-device-private.c8
-rw-r--r--src/resolve/resolved-def.h6
-rw-r--r--src/resolve/resolved-dns-cache.c40
-rw-r--r--src/resolve/resolved-dns-cache.h3
-rw-r--r--src/resolve/resolved-dns-packet.c55
-rw-r--r--src/resolve/resolved-dns-packet.h6
-rw-r--r--src/resolve/resolved-dns-rr.h8
-rw-r--r--src/resolve/resolved-dns-scope.c56
-rw-r--r--src/resolve/resolved-dns-scope.h1
-rw-r--r--src/resolve/resolved-dns-transaction.c337
-rw-r--r--src/resolve/resolved-dns-transaction.h8
-rw-r--r--src/resolve/resolved-link.c24
-rw-r--r--src/resolve/resolved-link.h3
-rw-r--r--src/resolve/resolved-manager.c23
-rw-r--r--src/resolve/resolved-manager.h8
-rw-r--r--src/resolve/resolved-mdns.c288
-rw-r--r--src/resolve/resolved-mdns.h32
-rw-r--r--src/test/test-rbtree.c362
-rw-r--r--src/test/test-rlimit-util.c69
-rw-r--r--src/udev/udev-event.c8
22 files changed, 2208 insertions, 113 deletions
diff --git a/src/basic/c-rbtree.c b/src/basic/c-rbtree.c
new file mode 100644
index 0000000000..914d7e5229
--- /dev/null
+++ b/src/basic/c-rbtree.c
@@ -0,0 +1,679 @@
+/***
+ This file is part of systemd. See COPYING for details.
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * RB-Tree Implementation
+ * This implements the insertion/removal of elements in RB-Trees. You're highly
+ * recommended to have an RB-Tree documentation at hand when reading this. Both
+ * insertion and removal can be split into a handful of situations that can
+ * occur. Those situations are enumerated as "Case 1" to "Case n" here, and
+ * follow closely the cases described in most RB-Tree documentations. This file
+ * does not explain why it is enough to handle just those cases, nor does it
+ * provide a proof of correctness. Dig out your algorithm 101 handbook if
+ * you're interested.
+ *
+ * This implementation is *not* straightforward. Usually, a handful of
+ * rotation, reparent, swap and link helpers can be used to implement the
+ * rebalance operations. However, those often perform unnecessary writes.
+ * Therefore, this implementation hard-codes all the operations. You're highly
+ * recommended to look at the two basic helpers before reading the code:
+ * c_rbtree_swap_child()
+ * c_rbtree_set_parent_and_color()
+ * Those are the only helpers used, hence, you should really know what they do
+ * before digging into the code.
+ *
+ * For a highlevel documentation of the API, see the header file and docbook
+ * comments.
+ */
+
+#include <assert.h>
+#include <stddef.h>
+#include "c-rbtree.h"
+
+enum {
+ C_RBNODE_RED = 0,
+ C_RBNODE_BLACK = 1,
+};
+
+static inline unsigned long c_rbnode_color(CRBNode *n) {
+ return (unsigned long)n->__parent_and_color & 1UL;
+}
+
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+ return c_rbnode_color(n) == C_RBNODE_RED;
+}
+
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+ return c_rbnode_color(n) == C_RBNODE_BLACK;
+}
+
+/**
+ * c_rbnode_leftmost() - return leftmost child
+ * @n: current node, or NULL
+ *
+ * This returns the leftmost child of @n. If @n is NULL, this will return NULL.
+ * In all other cases, this function returns a valid pointer. That is, if @n
+ * does not have any left children, this returns @n.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to leftmost child, or NULL.
+ */
+CRBNode *c_rbnode_leftmost(CRBNode *n) {
+ if (n)
+ while (n->left)
+ n = n->left;
+ return n;
+}
+
+/**
+ * c_rbnode_rightmost() - return rightmost child
+ * @n: current node, or NULL
+ *
+ * This returns the rightmost child of @n. If @n is NULL, this will return
+ * NULL. In all other cases, this function returns a valid pointer. That is, if
+ * @n does not have any right children, this returns @n.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to rightmost child, or NULL.
+ */
+CRBNode *c_rbnode_rightmost(CRBNode *n) {
+ if (n)
+ while (n->right)
+ n = n->right;
+ return n;
+}
+
+/**
+ * c_rbnode_next() - return next node
+ * @n: current node, or NULL
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically next node to @n. If @n is NULL, the last node or
+ * unlinked, this returns NULL.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to next node, or NULL.
+ */
+CRBNode *c_rbnode_next(CRBNode *n) {
+ CRBNode *p;
+
+ if (!c_rbnode_is_linked(n))
+ return NULL;
+ if (n->right)
+ return c_rbnode_leftmost(n->right);
+
+ while ((p = c_rbnode_parent(n)) && n == p->right)
+ n = p;
+
+ return p;
+}
+
+/**
+ * c_rbnode_prev() - return previous node
+ * @n: current node, or NULL
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically previous node to @n. If @n is NULL, the first node or
+ * unlinked, this returns NULL.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to previous node, or NULL.
+ */
+CRBNode *c_rbnode_prev(CRBNode *n) {
+ CRBNode *p;
+
+ if (!c_rbnode_is_linked(n))
+ return NULL;
+ if (n->left)
+ return c_rbnode_rightmost(n->left);
+
+ while ((p = c_rbnode_parent(n)) && n == p->left)
+ n = p;
+
+ return p;
+}
+
+/**
+ * c_rbtree_first() - return first node
+ * @t: tree to operate on
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically first node in @t. If @t is empty, NULL is returned.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to first node, or NULL.
+ */
+CRBNode *c_rbtree_first(CRBTree *t) {
+ assert(t);
+ return c_rbnode_leftmost(t->root);
+}
+
+/**
+ * c_rbtree_last() - return last node
+ * @t: tree to operate on
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically last node in @t. If @t is empty, NULL is returned.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to last node, or NULL.
+ */
+CRBNode *c_rbtree_last(CRBTree *t) {
+ assert(t);
+ return c_rbnode_rightmost(t->root);
+}
+
+/*
+ * Set the color and parent of a node. This should be treated as a simple
+ * assignment of the 'color' and 'parent' fields of the node. No other magic is
+ * applied. But since both fields share its backing memory, this helper
+ * function is provided.
+ */
+static inline void c_rbnode_set_parent_and_color(CRBNode *n, CRBNode *p, unsigned long c) {
+ assert(!((unsigned long)p & 1));
+ assert(c < 2);
+ n->__parent_and_color = (CRBNode*)((unsigned long)p | c);
+}
+
+/* same as c_rbnode_set_parent_and_color(), but keeps the current parent */
+static inline void c_rbnode_set_color(CRBNode *n, unsigned long c) {
+ c_rbnode_set_parent_and_color(n, c_rbnode_parent(n), c);
+}
+
+/* same as c_rbnode_set_parent_and_color(), but keeps the current color */
+static inline void c_rbnode_set_parent(CRBNode *n, CRBNode *p) {
+ c_rbnode_set_parent_and_color(n, p, c_rbnode_color(n));
+}
+
+/*
+ * This function partially replaces an existing child pointer to a new one. The
+ * existing child must be given as @old, the new child as @new. @p must be the
+ * parent of @old (or NULL if it has no parent).
+ * This function ensures that the parent of @old now points to @new. However,
+ * it does *NOT* change the parent pointer of @new. The caller must ensure
+ * this.
+ * If @p is NULL, this function ensures that the root-pointer is adjusted
+ * instead (given as @t).
+ */
+static inline void c_rbtree_swap_child(CRBTree *t, CRBNode *p, CRBNode *old, CRBNode *new) {
+ if (p) {
+ if (p->left == old)
+ p->left = new;
+ else
+ p->right = new;
+ } else {
+ t->root = new;
+ }
+}
+
+static inline CRBNode *c_rbtree_paint_one(CRBTree *t, CRBNode *n) {
+ CRBNode *p, *g, *gg, *u, *x;
+
+ /*
+ * Paint a single node according to RB-Tree rules. The node must
+ * already be linked into the tree and painted red.
+ * We repaint the node or rotate the tree, if required. In case a
+ * recursive repaint is required, the next node to be re-painted
+ * is returned.
+ * p: parent
+ * g: grandparent
+ * gg: grandgrandparent
+ * u: uncle
+ * x: temporary
+ */
+
+ /* node is red, so we can access the parent directly */
+ p = n->__parent_and_color;
+
+ if (!p) {
+ /* Case 1:
+ * We reached the root. Mark it black and be done. As all
+ * leaf-paths share the root, the ratio of black nodes on each
+ * path stays the same. */
+ c_rbnode_set_parent_and_color(n, p, C_RBNODE_BLACK);
+ n = NULL;
+ } else if (c_rbnode_is_black(p)) {
+ /* Case 2:
+ * The parent is already black. As our node is red, we did not
+ * change the number of black nodes on any path, nor do we have
+ * multiple consecutive red nodes. */
+ n = NULL;
+ } else if (p == p->__parent_and_color->left) { /* parent is red, so grandparent exists */
+ g = p->__parent_and_color;
+ gg = c_rbnode_parent(g);
+ u = g->right;
+
+ if (u && c_rbnode_is_red(u)) {
+ /* Case 3:
+ * Parent and uncle are both red. We know the
+ * grandparent must be black then. Repaint parent and
+ * uncle black, the grandparent red and recurse into
+ * the grandparent. */
+ c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
+ n = g;
+ } else {
+ /* parent is red, uncle is black */
+
+ if (n == p->right) {
+ /* Case 4:
+ * We're the right child. Rotate on parent to
+ * become left child, so we can handle it the
+ * same as case 5. */
+ x = n->left;
+ p->right = n->left;
+ n->left = p;
+ if (x)
+ c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
+ p = n;
+ }
+
+ /* 'n' is invalid from here on! */
+ n = NULL;
+
+ /* Case 5:
+ * We're the red left child or a red parent, black
+ * grandparent and uncle. Rotate on grandparent and
+ * switch color with parent. Number of black nodes on
+ * each path stays the same, but we got rid of the
+ * double red path. As the grandparent is still black,
+ * we're done. */
+ x = p->right;
+ g->left = x;
+ p->right = g;
+ if (x)
+ c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
+ c_rbtree_swap_child(t, gg, g, p);
+ }
+ } else /* if (p == p->__parent_and_color->left) */ { /* same as above, but mirrored */
+ g = p->__parent_and_color;
+ gg = c_rbnode_parent(g);
+ u = g->left;
+
+ if (u && c_rbnode_is_red(u)) {
+ c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
+ n = g;
+ } else {
+ if (n == p->left) {
+ x = n->right;
+ p->left = n->right;
+ n->right = p;
+ if (x)
+ c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
+ p = n;
+ }
+
+ n = NULL;
+
+ x = p->left;
+ g->right = x;
+ p->left = g;
+ if (x)
+ c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
+ c_rbtree_swap_child(t, gg, g, p);
+ }
+ }
+
+ return n;
+}
+
+static inline void c_rbtree_paint(CRBTree *t, CRBNode *n) {
+ assert(t);
+ assert(n);
+
+ while (n)
+ n = c_rbtree_paint_one(t, n);
+}
+
+/**
+ * c_rbtree_add() - add node to tree
+ * @t: tree to operate one
+ * @p: parent node to link under, or NULL
+ * @l: left/right slot of @p (or root) to link at
+ * @n: node to add
+ *
+ * This links @n into the tree given as @t. The caller must provide the exact
+ * spot where to link the node. That is, the caller must traverse the tree
+ * based on their search order. Once they hit a leaf where to insert the node,
+ * call this function to link it and rebalance the tree.
+ *
+ * A typical insertion would look like this (@t is your tree, @n is your node):
+ *
+ * CRBNode **i, *p;
+ *
+ * i = &t->root;
+ * p = NULL;
+ * while (*i) {
+ * p = *i;
+ * if (compare(n, *i) < 0)
+ * i = &(*i)->left;
+ * else
+ * i = &(*i)->right;
+ * }
+ *
+ * c_rbtree_add(t, p, i, n);
+ *
+ * Once the node is linked into the tree, a simple lookup on the same tree can
+ * be coded like this:
+ *
+ * CRBNode *i;
+ *
+ * i = t->root;
+ * while (i) {
+ * int v = compare(n, i);
+ * if (v < 0)
+ * i = (*i)->left;
+ * else if (v > 0)
+ * i = (*i)->right;
+ * else
+ * break;
+ * }
+ *
+ * When you add nodes to a tree, the memory contents of the node do not matter.
+ * That is, there is no need to initialize the node via c_rbnode_init().
+ * However, if you relink nodes multiple times during their lifetime, it is
+ * usually very convenient to use c_rbnode_init() and c_rbtree_remove_init().
+ * In those cases, you should validate that a node is unlinked before you call
+ * c_rbtree_add().
+ */
+void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) {
+ assert(t);
+ assert(l);
+ assert(n);
+ assert(!p || l == &p->left || l == &p->right);
+ assert(p || l == &t->root);
+
+ c_rbnode_set_parent_and_color(n, p, C_RBNODE_RED);
+ n->left = n->right = NULL;
+ *l = n;
+
+ c_rbtree_paint(t, n);
+}
+
+static inline CRBNode *c_rbtree_rebalance_one(CRBTree *t, CRBNode *p, CRBNode *n) {
+ CRBNode *s, *x, *y, *g;
+
+ /*
+ * Rebalance tree after a node was removed. This happens only if you
+ * remove a black node and one path is now left with an unbalanced
+ * number or black nodes.
+ * This function assumes all paths through p and n have one black node
+ * less than all other paths. If recursive fixup is required, the
+ * current node is returned.
+ */
+
+ if (n == p->left) {
+ s = p->right;
+ if (c_rbnode_is_red(s)) {
+ /* Case 3:
+ * We have a red node as sibling. Rotate it onto our
+ * side so we can later on turn it black. This way, we
+ * gain the additional black node in our path. */
+ g = c_rbnode_parent(p);
+ x = s->left;
+ p->right = x;
+ s->left = p;
+ c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+ c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
+ c_rbtree_swap_child(t, g, p, s);
+ s = x;
+ }
+
+ x = s->right;
+ if (!x || c_rbnode_is_black(x)) {
+ y = s->left;
+ if (!y || c_rbnode_is_black(y)) {
+ /* Case 4:
+ * Our sibling is black and has only black
+ * children. Flip it red and turn parent black.
+ * This way we gained a black node in our path,
+ * or we fix it recursively one layer up, which
+ * will rotate the red sibling as parent. */
+ c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
+ if (c_rbnode_is_black(p))
+ return p;
+
+ c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
+ return NULL;
+ }
+
+ /* Case 5:
+ * Left child of our sibling is red, right one is black.
+ * Rotate on parent so the right child of our sibling is
+ * now red, and we can fall through to case 6. */
+ x = y->right;
+ s->left = y->right;
+ y->right = s;
+ p->right = y;
+ if (x)
+ c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+ x = s;
+ s = y;
+ }
+
+ /* Case 6:
+ * The right child of our sibling is red. Rotate left and flip
+ * colors, which gains us an additional black node in our path,
+ * that was previously on our sibling. */
+ g = c_rbnode_parent(p);
+ y = s->left;
+ p->right = y;
+ s->left = p;
+ c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+ if (y)
+ c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
+ c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+ c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
+ c_rbtree_swap_child(t, g, p, s);
+ } else /* if (!n || n == p->right) */ { /* same as above, but mirrored */
+ s = p->left;
+ if (c_rbnode_is_red(s)) {
+ g = c_rbnode_parent(p);
+ x = s->right;
+ p->left = x;
+ s->right = p;
+ c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(s, g, C_RBNODE_BLACK);
+ c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
+ c_rbtree_swap_child(t, g, p, s);
+ s = x;
+ }
+
+ x = s->left;
+ if (!x || c_rbnode_is_black(x)) {
+ y = s->right;
+ if (!y || c_rbnode_is_black(y)) {
+ c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
+ if (c_rbnode_is_black(p))
+ return p;
+
+ c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
+ return NULL;
+ }
+
+ x = y->left;
+ s->right = y->left;
+ y->left = s;
+ p->left = y;
+ if (x)
+ c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+ x = s;
+ s = y;
+ }
+
+ g = c_rbnode_parent(p);
+ y = s->right;
+ p->left = y;
+ s->right = p;
+ c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+ if (y)
+ c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
+ c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+ c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
+ c_rbtree_swap_child(t, g, p, s);
+ }
+
+ return NULL;
+}
+
+static inline void c_rbtree_rebalance(CRBTree *t, CRBNode *p) {
+ CRBNode *n = NULL;
+
+ assert(t);
+ assert(p);
+
+ do {
+ n = c_rbtree_rebalance_one(t, p, n);
+ p = n ? c_rbnode_parent(n) : NULL;
+ } while (p);
+}
+
+/**
+ * c_rbtree_remove() - remove node from tree
+ * @t: tree to operate one
+ * @n: node to remove
+ *
+ * This removes the given node from its tree. Once unlinked, the tree is
+ * rebalanced.
+ * The caller *must* ensure that the given tree is actually the tree it is
+ * linked on. Otherwise, behavior is undefined.
+ *
+ * This does *NOT* reset @n to being unlinked (for performance reason, this
+ * function *never* modifies @n at all). If you need this, use
+ * c_rbtree_remove_init().
+ */
+void c_rbtree_remove(CRBTree *t, CRBNode *n) {
+ CRBNode *p, *s, *gc, *x, *next = NULL;
+ unsigned long c;
+
+ assert(t);
+ assert(n);
+ assert(c_rbnode_is_linked(n));
+
+ /*
+ * There are three distinct cases during node removal of a tree:
+ * * The node has no children, in which case it can simply be removed.
+ * * The node has exactly one child, in which case the child displaces
+ * its parent.
+ * * The node has two children, in which case there is guaranteed to
+ * be a successor to the node (successor being the node ordered
+ * directly after it). This successor cannot have two children by
+ * itself (two interior nodes can never be successive). Therefore,
+ * we can simply swap the node with its successor (including color)
+ * and have reduced this case to either of the first two.
+ *
+ * Whenever the node we removed was black, we have to rebalance the
+ * tree. Note that this affects the actual node we _remove_, not @n (in
+ * case we swap it).
+ *
+ * p: parent
+ * s: successor
+ * gc: grand-...-child
+ * x: temporary
+ * next: next node to rebalance on
+ */
+
+ if (!n->left) {
+ /*
+ * Case 1:
+ * The node has no left child. If it neither has a right child,
+ * it is a leaf-node and we can simply unlink it. If it also
+ * was black, we have to rebalance, as always if we remove a
+ * black node.
+ * But if the node has a right child, the child *must* be red
+ * (otherwise, the right path has more black nodes as the
+ * non-existing left path), and the node to be removed must
+ * hence be black. We simply replace the node with its child,
+ * turning the red child black, and thus no rebalancing is
+ * required.
+ */
+ p = c_rbnode_parent(n);
+ c = c_rbnode_color(n);
+ c_rbtree_swap_child(t, p, n, n->right);
+ if (n->right)
+ c_rbnode_set_parent_and_color(n->right, p, c);
+ else
+ next = (c == C_RBNODE_BLACK) ? p : NULL;
+ } else if (!n->right) {
+ /*
+ * Case 1.1:
+ * The node has exactly one child, and it is on the left. Treat
+ * it as mirrored case of Case 1 (i.e., replace the node by its
+ * child).
+ */
+ p = c_rbnode_parent(n);
+ c = c_rbnode_color(n);
+ c_rbtree_swap_child(t, p, n, n->left);
+ c_rbnode_set_parent_and_color(n->left, p, c);
+ } else {
+ /*
+ * Case 2:
+ * We are dealing with a full interior node with a child not on
+ * both sides. Find its successor and swap it. Then remove the
+ * node similar to Case 1. For performance reasons we don't
+ * perform the full swap, but skip links that are about to be
+ * removed, anyway.
+ */
+ s = n->right;
+ if (!s->left) {
+ /* right child is next, no need to touch grandchild */
+ p = s;
+ gc = s->right;
+ } else {
+ /* find successor and swap partially */
+ s = c_rbnode_leftmost(s);
+ p = c_rbnode_parent(s);
+
+ gc = s->right;
+ p->left = s->right;
+ s->right = n->right;
+ c_rbnode_set_parent(n->right, s);
+ }
+
+ /* node is partially swapped, now remove as in Case 1 */
+ s->left = n->left;
+ c_rbnode_set_parent(n->left, s);
+
+ x = c_rbnode_parent(n);
+ c = c_rbnode_color(n);
+ c_rbtree_swap_child(t, x, n, s);
+ if (gc)
+ c_rbnode_set_parent_and_color(gc, p, C_RBNODE_BLACK);
+ else
+ next = c_rbnode_is_black(s) ? p : NULL;
+ c_rbnode_set_parent_and_color(s, x, c);
+ }
+
+ if (next)
+ c_rbtree_rebalance(t, next);
+}
diff --git a/src/basic/c-rbtree.h b/src/basic/c-rbtree.h
new file mode 100644
index 0000000000..20c5515ca1
--- /dev/null
+++ b/src/basic/c-rbtree.h
@@ -0,0 +1,297 @@
+#pragma once
+
+/***
+ This file is part of systemd. See COPYING for details.
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * Standalone Red-Black-Tree Implementation in Standard ISO-C11
+ *
+ * This header provides an RB-Tree API, that is fully implemented in ISO-C11
+ * and has no external dependencies. Furthermore, tree traversal, memory
+ * allocations, and key comparisons a fully in control of the API user. The
+ * implementation only provides the RB-Tree specific rebalancing and coloring.
+ *
+ * A tree is represented by the "CRBTree" structure. It contains a *singly*
+ * field, which is a pointer to the root node. If NULL, the tree is empty. If
+ * non-NULL, there is at least a single element in the tree.
+ *
+ * Each node of the tree is represented by the "CRBNode" structure. It has
+ * three fields. The @left and @right members can be accessed by the API user
+ * directly to traverse the tree. The third member is an implementation detail
+ * and encodes the parent pointer and color of the node.
+ * API users are required to embed the CRBNode object into their own objects
+ * and then use offsetof() (i.e., container_of() and friends) to turn CRBNode
+ * pointers into pointers to their own structure.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct CRBNode CRBNode;
+typedef struct CRBTree CRBTree;
+
+/**
+ * struct CRBNode - Node of a Red-Black Tree
+ * @__parent_and_color: internal state
+ * @left: left child, or NULL
+ * @right: right child, or NULL
+ *
+ * Each node in an RB-Tree must embed an CRBNode object. This object contains
+ * pointers to its left and right child, which can be freely accessed by the
+ * API user at any time. They are NULL, if the node does not have a left/right
+ * child.
+ *
+ * The @__parent_and_color field must never be accessed directly. It encodes
+ * the pointer to the parent node, and the color of the node. Use the accessor
+ * functions instead.
+ *
+ * There is no reason to initialize a CRBNode object before linking it.
+ * However, if you need a boolean state that tells you whether the node is
+ * linked or not, you should initialize the node via c_rbnode_init() or
+ * C_RBNODE_INIT.
+ */
+struct CRBNode {
+ CRBNode *__parent_and_color;
+ CRBNode *left;
+ CRBNode *right;
+};
+
+#define C_RBNODE_INIT(_var) { .__parent_and_color = &(_var) }
+
+CRBNode *c_rbnode_leftmost(CRBNode *n);
+CRBNode *c_rbnode_rightmost(CRBNode *n);
+CRBNode *c_rbnode_next(CRBNode *n);
+CRBNode *c_rbnode_prev(CRBNode *n);
+
+/**
+ * struct CRBTree - Red-Black Tree
+ * @root: pointer to the root node, or NULL
+ *
+ * Each Red-Black Tree is rooted in an CRBTree object. This object contains a
+ * pointer to the root node of the tree. The API user is free to access the
+ * @root member at any time, and use it to traverse the tree.
+ *
+ * To initialize an RB-Tree, set it to NULL / all zero.
+ */
+struct CRBTree {
+ CRBNode *root;
+};
+
+CRBNode *c_rbtree_first(CRBTree *t);
+CRBNode *c_rbtree_last(CRBTree *t);
+
+void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n);
+void c_rbtree_remove(CRBTree *t, CRBNode *n);
+
+/**
+ * c_rbnode_init() - mark a node as unlinked
+ * @n: node to operate on
+ *
+ * This marks the node @n as unlinked. The node will be set to a valid state
+ * that can never happen if the node is linked in a tree. Furthermore, this
+ * state is fully known to the implementation, and as such handled gracefully
+ * in all cases.
+ *
+ * You are *NOT* required to call this on your node. c_rbtree_add() can handle
+ * uninitialized nodes just fine. However, calling this allows to use
+ * c_rbnode_is_linked() to check for the state of a node. Furthermore,
+ * iterators and accessors can be called on initialized (yet unlinked) nodes.
+ *
+ * Use the C_RBNODE_INIT macro if you want to initialize static variables.
+ */
+static inline void c_rbnode_init(CRBNode *n) {
+ *n = (CRBNode)C_RBNODE_INIT(*n);
+}
+
+/**
+ * c_rbnode_is_linked() - check whether a node is linked
+ * @n: node to check, or NULL
+ *
+ * This checks whether the passed node is linked. If you pass NULL, or if the
+ * node is not linked into a tree, this will return false. Otherwise, this
+ * returns true.
+ *
+ * Note that you must have either linked the node or initialized it, before
+ * calling this function. Never call this function on uninitialized nodes.
+ * Furthermore, removing a node via c_rbtree_remove() does *NOT* mark the node
+ * as unlinked. You have to call c_rbnode_init() yourself after removal, or use
+ * the c_rbtree_remove_init() helper.
+ *
+ * Return: true if the node is linked, false if not.
+ */
+static inline _Bool c_rbnode_is_linked(CRBNode *n) {
+ return n && n->__parent_and_color != n;
+}
+
+/**
+ * c_rbnode_parent() - return parent pointer
+ * @n node to access
+ *
+ * This returns a pointer to the parent of the given node @n. If @n does not
+ * have a parent, NULL is returned. If @n is not linked, @n itself is returned.
+ *
+ * You should not call this on unlinked or uninitialized nodes! If you do, you
+ * better know how its semantics.
+ *
+ * Return: Pointer to parent.
+ */
+static inline CRBNode *c_rbnode_parent(CRBNode *n) {
+ return (CRBNode*)((unsigned long)n->__parent_and_color & ~1UL);
+}
+
+/**
+ * c_rbtree_remove_init() - safely remove node from tree and reinitialize it
+ * @t: tree to operate on
+ * @n: node to remove, or NULL
+ *
+ * This is almost the same as c_rbtree_remove(), but extends it slightly, to be
+ * more convenient to use in many cases:
+ * - if @n is unlinked or NULL, this is a no-op
+ * - @n is reinitialized after being removed
+ */
+static inline void c_rbtree_remove_init(CRBTree *t, CRBNode *n) {
+ if (c_rbnode_is_linked(n)) {
+ c_rbtree_remove(t, n);
+ c_rbnode_init(n);
+ }
+}
+
+/**
+ * CRBCompareFunc - compare a node to a key
+ * @t: tree where the node is linked to
+ * @k: key to compare
+ * @n: node to compare
+ *
+ * If you use the tree-traversal helpers (which are optional), you need to
+ * provide this callback so they can compare nodes in a tree to the key you
+ * look for.
+ *
+ * The tree @t is provided as optional context to this callback. The key you
+ * look for is provided as @k, the current node that should be compared to is
+ * provided as @n. This function should work like strcmp(), that is, return -1
+ * if @key orders before @n, 0 if both compare equal, and 1 if it orders after
+ * @n.
+ */
+typedef int (*CRBCompareFunc) (CRBTree *t, void *k, CRBNode *n);
+
+/**
+ * c_rbtree_find_node() - find node
+ * @t: tree to search through
+ * @f: comparison function
+ * @k: key to search for
+ *
+ * This searches through @t for a node that compares equal to @k. The function
+ * @f must be provided by the caller, which is used to compare nodes to @k. See
+ * the documentation of CRBCompareFunc for details.
+ *
+ * If there are multiple entries that compare equal to @k, this will return a
+ * pseudo-randomly picked node. If you need stable lookup functions for trees
+ * where duplicate entries are allowed, you better code your own lookup.
+ *
+ * Return: Pointer to matching node, or NULL.
+ */
+static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const void *k) {
+ CRBNode *i;
+
+ assert(t);
+ assert(f);
+
+ i = t->root;
+ while (i) {
+ int v = f(t, (void *)k, i);
+ if (v < 0)
+ i = i->left;
+ else if (v > 0)
+ i = i->right;
+ else
+ return i;
+ }
+
+ return NULL;
+}
+
+/**
+ * c_rbtree_find_entry() - find entry
+ * @_t: tree to search through
+ * @_f: comparison function
+ * @_k: key to search for
+ * @_t: type of the structure that embeds the nodes
+ * @_o: name of the node-member in type @_t
+ *
+ * This is very similar to c_rbtree_find_node(), but instead of returning a
+ * pointer to the CRBNode, it returns a pointer to the surrounding object. This
+ * object must embed the CRBNode object. The type of the surrounding object
+ * must be given as @_t, and the name of the embedded CRBNode member as @_o.
+ *
+ * See c_rbtree_find_node() for more details.
+ *
+ * Return: Pointer to found entry, NULL if not found.
+ */
+#define c_rbtree_find_entry(_m, _f, _k, _t, _o) \
+ ((_t *)(((char *)c_rbtree_find_node((_m), (_f), (_k)) ?: \
+ (char *)NULL + offsetof(_t, _o)) - offsetof(_t, _o)))
+
+/**
+ * c_rbtree_find_slot() - find slot to insert new node
+ * @t: tree to search through
+ * @f: comparison function
+ * @k: key to search for
+ * @p: output storage for parent pointer
+ *
+ * This searches through @t just like c_rbtree_find_node() does. However,
+ * instead of returning a pointer to a node that compares equal to @k, this
+ * searches for a slot to insert a node with key @k. A pointer to the slot is
+ * returned, and a pointer to the parent of the slot is stored in @p. Both
+ * can be passed directly to c_rbtree_add(), together with your node to insert.
+ *
+ * If there already is a node in the tree, that compares equal to @k, this will
+ * return NULL and store the conflicting node in @p. In all other cases,
+ * this will return a pointer (non-NULL) to the empty slot to insert the node
+ * at. @p will point to the parent node of that slot.
+ *
+ * If you want trees that allow duplicate nodes, you better code your own
+ * insertion function.
+ *
+ * Return: Pointer to slot to insert node, or NULL on conflicts.
+ */
+static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) {
+ CRBNode **i;
+
+ assert(t);
+ assert(f);
+ assert(p);
+
+ i = &t->root;
+ *p = NULL;
+ while (*i) {
+ int v = f(t, (void *)k, *i);
+ *p = *i;
+ if (v < 0)
+ i = &(*i)->left;
+ else if (v > 0)
+ i = &(*i)->right;
+ else
+ return NULL;
+ }
+
+ return i;
+}
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/src/libudev/libudev-device-private.c b/src/libudev/libudev-device-private.c
index 2d3e62410c..2aae0726c1 100644
--- a/src/libudev/libudev-device-private.c
+++ b/src/libudev/libudev-device-private.c
@@ -137,14 +137,10 @@ gid_t udev_device_get_devnode_gid(struct udev_device *udev_device) {
}
void udev_device_ensure_usec_initialized(struct udev_device *udev_device, struct udev_device *udev_device_old) {
- sd_device *device_old = NULL;
-
assert(udev_device);
- if (udev_device_old)
- device_old = udev_device_old->device;
-
- device_ensure_usec_initialized(udev_device->device, device_old);
+ device_ensure_usec_initialized(udev_device->device,
+ udev_device_old ? udev_device_old->device : NULL);
}
char **udev_device_get_properties_envp(struct udev_device *udev_device) {
diff --git a/src/resolve/resolved-def.h b/src/resolve/resolved-def.h
index db5ee57b51..6014d345f3 100644
--- a/src/resolve/resolved-def.h
+++ b/src/resolve/resolved-def.h
@@ -24,6 +24,8 @@
#define SD_RESOLVED_DNS (UINT64_C(1) << 0)
#define SD_RESOLVED_LLMNR_IPV4 (UINT64_C(1) << 1)
#define SD_RESOLVED_LLMNR_IPV6 (UINT64_C(1) << 2)
+#define SD_RESOLVED_MDNS_IPV4 (UINT64_C(1) << 3)
+#define SD_RESOLVED_MDNS_IPV6 (UINT64_C(1) << 4)
#define SD_RESOLVED_NO_CNAME (UINT64_C(1) << 5)
#define SD_RESOLVED_NO_TXT (UINT64_C(1) << 6)
#define SD_RESOLVED_NO_ADDRESS (UINT64_C(1) << 7)
@@ -31,4 +33,6 @@
#define SD_RESOLVED_AUTHENTICATED (UINT64_C(1) << 9)
#define SD_RESOLVED_LLMNR (SD_RESOLVED_LLMNR_IPV4|SD_RESOLVED_LLMNR_IPV6)
-#define SD_RESOLVED_PROTOCOLS_ALL (SD_RESOLVED_LLMNR|SD_RESOLVED_DNS)
+#define SD_RESOLVED_MDNS (SD_RESOLVED_MDNS_IPV4|SD_RESOLVED_MDNS_IPV6)
+
+#define SD_RESOLVED_PROTOCOLS_ALL (SD_RESOLVED_MDNS|SD_RESOLVED_LLMNR|SD_RESOLVED_DNS)
diff --git a/src/resolve/resolved-dns-cache.c b/src/resolve/resolved-dns-cache.c
index bcb9994a8c..6124ff659c 100644
--- a/src/resolve/resolved-dns-cache.c
+++ b/src/resolve/resolved-dns-cache.c
@@ -459,7 +459,12 @@ int dns_cache_put(
/* Second, add in positive entries for all contained RRs */
for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
- r = dns_cache_put_positive(c, answer->items[i].rr, authenticated, timestamp, owner_family, owner_address);
+ DnsResourceRecord *rr = answer->items[i].rr;
+
+ if (rr->key->cache_flush)
+ dns_cache_remove(c, rr->key);
+
+ r = dns_cache_put_positive(c, rr, authenticated, timestamp, owner_family, owner_address);
if (r < 0)
goto fail;
}
@@ -726,6 +731,39 @@ int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_
return 1;
}
+int dns_cache_export_shared_to_packet(DnsCache *cache, DnsPacket *p) {
+ unsigned ancount = 0;
+ Iterator iterator;
+ DnsCacheItem *i;
+ int r;
+
+ assert(cache);
+
+ HASHMAP_FOREACH(i, cache->by_key, iterator) {
+ DnsCacheItem *j;
+
+ LIST_FOREACH(by_key, j, i) {
+ _cleanup_free_ char *t = NULL;
+
+ if (!j->rr)
+ continue;
+
+ if (!dns_key_is_shared(j->rr->key))
+ continue;
+
+ r = dns_packet_append_rr(p, j->rr, NULL, NULL);
+ if (r < 0)
+ return r;
+
+ ancount ++;
+ }
+ }
+
+ DNS_PACKET_HEADER(p)->ancount = htobe16(ancount);
+
+ return 0;
+}
+
void dns_cache_dump(DnsCache *cache, FILE *f) {
Iterator iterator;
DnsCacheItem *i;
diff --git a/src/resolve/resolved-dns-cache.h b/src/resolve/resolved-dns-cache.h
index 5f91164785..0f28bbe543 100644
--- a/src/resolve/resolved-dns-cache.h
+++ b/src/resolve/resolved-dns-cache.h
@@ -32,6 +32,7 @@ typedef struct DnsCache {
} DnsCache;
#include "resolved-dns-answer.h"
+#include "resolved-dns-packet.h"
#include "resolved-dns-question.h"
#include "resolved-dns-rr.h"
@@ -45,3 +46,5 @@ int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_
void dns_cache_dump(DnsCache *cache, FILE *f);
bool dns_cache_is_empty(DnsCache *cache);
+
+int dns_cache_export_shared_to_packet(DnsCache *cache, DnsPacket *p);
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
index ea776f7916..9bd08eeec2 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -88,6 +88,16 @@ int dns_packet_new_query(DnsPacket **ret, DnsProtocol protocol, size_t mtu, bool
0 /* ad */,
0 /* cd */,
0 /* rcode */));
+ else if (protocol == DNS_PROTOCOL_MDNS)
+ h->flags = htobe16(DNS_PACKET_MAKE_FLAGS(0 /* qr */,
+ 0 /* opcode */,
+ 0 /* aa */,
+ 0 /* tc */,
+ 0 /* rd (ask for recursion) */,
+ 0 /* ra */,
+ 0 /* ad */,
+ 0 /* cd */,
+ 0 /* rcode */));
else
h->flags = htobe16(DNS_PACKET_MAKE_FLAGS(0 /* qr */,
0 /* opcode */,
@@ -182,6 +192,13 @@ int dns_packet_validate_reply(DnsPacket *p) {
break;
+ case DNS_PROTOCOL_MDNS:
+ /* RFC 6762, Section 18 */
+ if (DNS_PACKET_RCODE(p) != 0)
+ return -EBADMSG;
+
+ break;
+
default:
break;
}
@@ -223,6 +240,18 @@ int dns_packet_validate_query(DnsPacket *p) {
break;
+ case DNS_PROTOCOL_MDNS:
+ /* RFC 6762, Section 18 */
+ if (DNS_PACKET_AA(p) != 0 ||
+ DNS_PACKET_RD(p) != 0 ||
+ DNS_PACKET_RA(p) != 0 ||
+ DNS_PACKET_AD(p) != 0 ||
+ DNS_PACKET_CD(p) != 0 ||
+ DNS_PACKET_RCODE(p) != 0)
+ return -EBADMSG;
+
+ break;
+
default:
break;
}
@@ -1392,6 +1421,7 @@ fail:
int dns_packet_read_key(DnsPacket *p, DnsResourceKey **ret, size_t *start) {
_cleanup_free_ char *name = NULL;
+ bool cache_flush = false;
uint16_t class, type;
DnsResourceKey *key;
size_t saved_rindex;
@@ -1414,12 +1444,23 @@ int dns_packet_read_key(DnsPacket *p, DnsResourceKey **ret, size_t *start) {
if (r < 0)
goto fail;
+ if (p->protocol == DNS_PROTOCOL_MDNS) {
+ /* See RFC6762, Section 10.2 */
+
+ if (class & MDNS_RR_CACHE_FLUSH) {
+ class &= ~MDNS_RR_CACHE_FLUSH;
+ cache_flush = true;
+ }
+ }
+
key = dns_resource_key_new_consume(class, type, name);
if (!key) {
r = -ENOMEM;
goto fail;
}
+ key->cache_flush = cache_flush;
+
name = NULL;
*ret = key;
@@ -1778,8 +1819,16 @@ int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start) {
break;
- case DNS_TYPE_NSEC:
- r = dns_packet_read_name(p, &rr->nsec.next_domain_name, false, NULL);
+ case DNS_TYPE_NSEC: {
+
+ /*
+ * RFC6762, section 18.14 explicly states mDNS should use name compression.
+ * This contradicts RFC3845, section 2.1.1
+ */
+
+ bool allow_compressed = p->protocol == DNS_PROTOCOL_MDNS;
+
+ r = dns_packet_read_name(p, &rr->nsec.next_domain_name, allow_compressed, NULL);
if (r < 0)
goto fail;
@@ -1792,7 +1841,7 @@ int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start) {
* without the NSEC bit set. */
break;
-
+ }
case DNS_TYPE_NSEC3: {
uint8_t size;
diff --git a/src/resolve/resolved-dns-packet.h b/src/resolve/resolved-dns-packet.h
index aa2823cfb9..48b3572cb4 100644
--- a/src/resolve/resolved-dns-packet.h
+++ b/src/resolve/resolved-dns-packet.h
@@ -225,6 +225,9 @@ DnsProtocol dns_protocol_from_string(const char *s) _pure_;
#define LLMNR_MULTICAST_IPV4_ADDRESS ((struct in_addr) { .s_addr = htobe32(224U << 24 | 252U) })
#define LLMNR_MULTICAST_IPV6_ADDRESS ((struct in6_addr) { .s6_addr = { 0xFF, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x03 } })
+#define MDNS_MULTICAST_IPV4_ADDRESS ((struct in_addr) { .s_addr = htobe32(224U << 24 | 251U) })
+#define MDNS_MULTICAST_IPV6_ADDRESS ((struct in6_addr) { .s6_addr = { 0xFF, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0xfb } })
+
static inline uint64_t SD_RESOLVED_FLAGS_MAKE(DnsProtocol protocol, int family, bool authenticated) {
uint64_t f;
@@ -239,6 +242,9 @@ static inline uint64_t SD_RESOLVED_FLAGS_MAKE(DnsProtocol protocol, int family,
case DNS_PROTOCOL_LLMNR:
return f|(family == AF_INET6 ? SD_RESOLVED_LLMNR_IPV6 : SD_RESOLVED_LLMNR_IPV4);
+ case DNS_PROTOCOL_MDNS:
+ return family == AF_INET6 ? SD_RESOLVED_MDNS_IPV6 : SD_RESOLVED_MDNS_IPV4;
+
default:
break;
}
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index b82fa77562..5c2306ba96 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -45,6 +45,9 @@ enum {
#define DNSKEY_FLAG_ZONE_KEY (UINT16_C(1) << 8)
#define DNSKEY_FLAG_SEP (UINT16_C(1) << 0)
+/* mDNS RR flags */
+#define MDNS_RR_CACHE_FLUSH (UINT16_C(1) << 15)
+
/* DNSSEC algorithm identifiers, see
* http://tools.ietf.org/html/rfc4034#appendix-A.1 and
* https://www.iana.org/assignments/dns-sec-alg-numbers/dns-sec-alg-numbers.xhtml */
@@ -76,6 +79,7 @@ struct DnsResourceKey {
unsigned n_ref;
uint16_t class, type;
char *_name; /* don't access directy, use DNS_RESOURCE_KEY_NAME()! */
+ bool cache_flush:1;
};
/* Creates a temporary resource key. This is only useful to quickly
@@ -246,6 +250,10 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec
int dns_resource_key_to_string(const DnsResourceKey *key, char **ret);
DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceKey*, dns_resource_key_unref);
+static inline bool dns_key_is_shared(const DnsResourceKey *key) {
+ return IN_SET(key->type, DNS_TYPE_PTR);
+}
+
DnsResourceRecord* dns_resource_record_new(DnsResourceKey *key);
DnsResourceRecord* dns_resource_record_new_full(uint16_t class, uint16_t type, const char *name);
DnsResourceRecord* dns_resource_record_ref(DnsResourceRecord *rr);
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index a90692cdf4..eae903526b 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -30,6 +30,7 @@
#include "random-util.h"
#include "resolved-dns-scope.h"
#include "resolved-llmnr.h"
+#include "resolved-mdns.h"
#include "socket-util.h"
#include "strv.h"
@@ -59,6 +60,7 @@ int dns_scope_new(Manager *m, DnsScope **ret, Link *l, DnsProtocol protocol, int
LIST_PREPEND(scopes, m->dns_scopes, s);
dns_scope_llmnr_membership(s, true);
+ dns_scope_mdns_membership(s, true);
log_debug("New scope on link %s, protocol %s, family %s", l ? l->name : "*", dns_protocol_to_string(protocol), family == AF_UNSPEC ? "*" : af_to_name(family));
@@ -95,6 +97,7 @@ DnsScope* dns_scope_free(DnsScope *s) {
log_debug("Removing scope on link %s, protocol %s, family %s", s->link ? s->link->name : "*", dns_protocol_to_string(s->protocol), s->family == AF_UNSPEC ? "*" : af_to_name(s->family));
dns_scope_llmnr_membership(s, false);
+ dns_scope_mdns_membership(s, false);
dns_scope_abort_transactions(s);
while (s->query_candidates)
@@ -162,7 +165,6 @@ int dns_scope_emit(DnsScope *s, int fd, DnsServer *server, DnsPacket *p) {
union in_addr_union addr;
int ifindex = 0, r;
int family;
- uint16_t port;
uint32_t mtu;
size_t saved_size = 0;
@@ -228,7 +230,6 @@ int dns_scope_emit(DnsScope *s, int fd, DnsServer *server, DnsPacket *p) {
return -EBUSY;
family = s->family;
- port = LLMNR_PORT;
if (family == AF_INET) {
addr.in = LLMNR_MULTICAST_IPV4_ADDRESS;
@@ -241,7 +242,30 @@ int dns_scope_emit(DnsScope *s, int fd, DnsServer *server, DnsPacket *p) {
if (fd < 0)
return fd;
- r = manager_send(s->manager, fd, ifindex, family, &addr, port, p);
+ r = manager_send(s->manager, fd, ifindex, family, &addr, LLMNR_PORT, p);
+ if (r < 0)
+ return r;
+
+ break;
+
+ case DNS_PROTOCOL_MDNS:
+ if (!ratelimit_test(&s->ratelimit))
+ return -EBUSY;
+
+ family = s->family;
+
+ if (family == AF_INET) {
+ addr.in = MDNS_MULTICAST_IPV4_ADDRESS;
+ fd = manager_mdns_ipv4_fd(s->manager);
+ } else if (family == AF_INET6) {
+ addr.in6 = MDNS_MULTICAST_IPV6_ADDRESS;
+ fd = manager_mdns_ipv6_fd(s->manager);
+ } else
+ return -EAFNOSUPPORT;
+ if (fd < 0)
+ return fd;
+
+ r = manager_send(s->manager, fd, ifindex, family, &addr, MDNS_PORT, p);
if (r < 0)
return r;
@@ -477,19 +501,15 @@ int dns_scope_good_key(DnsScope *s, DnsResourceKey *key) {
return true;
}
-int dns_scope_llmnr_membership(DnsScope *s, bool b) {
+static int dns_scope_multicast_membership(DnsScope *s, bool b, struct in_addr in, struct in6_addr in6) {
int fd;
assert(s);
-
- if (s->protocol != DNS_PROTOCOL_LLMNR)
- return 0;
-
assert(s->link);
if (s->family == AF_INET) {
struct ip_mreqn mreqn = {
- .imr_multiaddr = LLMNR_MULTICAST_IPV4_ADDRESS,
+ .imr_multiaddr = in,
.imr_ifindex = s->link->ifindex,
};
@@ -508,7 +528,7 @@ int dns_scope_llmnr_membership(DnsScope *s, bool b) {
} else if (s->family == AF_INET6) {
struct ipv6_mreq mreq = {
- .ipv6mr_multiaddr = LLMNR_MULTICAST_IPV6_ADDRESS,
+ .ipv6mr_multiaddr = in6,
.ipv6mr_interface = s->link->ifindex,
};
@@ -527,6 +547,22 @@ int dns_scope_llmnr_membership(DnsScope *s, bool b) {
return 0;
}
+int dns_scope_llmnr_membership(DnsScope *s, bool b) {
+
+ if (s->protocol != DNS_PROTOCOL_LLMNR)
+ return 0;
+
+ return dns_scope_multicast_membership(s, b, LLMNR_MULTICAST_IPV4_ADDRESS, LLMNR_MULTICAST_IPV6_ADDRESS);
+}
+
+int dns_scope_mdns_membership(DnsScope *s, bool b) {
+
+ if (s->protocol != DNS_PROTOCOL_MDNS)
+ return 0;
+
+ return dns_scope_multicast_membership(s, b, MDNS_MULTICAST_IPV4_ADDRESS, MDNS_MULTICAST_IPV6_ADDRESS);
+}
+
static int dns_scope_make_reply_packet(
DnsScope *s,
uint16_t id,
diff --git a/src/resolve/resolved-dns-scope.h b/src/resolve/resolved-dns-scope.h
index 15d9a1fd6f..2fc2e07deb 100644
--- a/src/resolve/resolved-dns-scope.h
+++ b/src/resolve/resolved-dns-scope.h
@@ -93,6 +93,7 @@ DnsServer *dns_scope_get_dns_server(DnsScope *s);
void dns_scope_next_dns_server(DnsScope *s);
int dns_scope_llmnr_membership(DnsScope *s, bool b);
+int dns_scope_mdns_membership(DnsScope *s, bool b);
void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p);
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index 1103a34c6f..90f07e6c4b 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -24,6 +24,7 @@
#include "dns-domain.h"
#include "fd-util.h"
#include "random-util.h"
+#include "resolved-dns-cache.h"
#include "resolved-dns-transaction.h"
#include "resolved-llmnr.h"
#include "string-table.h"
@@ -243,7 +244,7 @@ static int on_stream_complete(DnsStream *s, int error) {
}
if (dns_packet_validate_reply(p) <= 0) {
- log_debug("Invalid LLMNR TCP packet.");
+ log_debug("Invalid TCP reply packet.");
dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
return 0;
}
@@ -384,6 +385,18 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
break;
+ case DNS_PROTOCOL_MDNS:
+ assert(t->scope->link);
+
+ /* For mDNS we will not accept any packets from other interfaces */
+ if (p->ifindex != t->scope->link->ifindex)
+ return;
+
+ if (p->family != t->scope->family)
+ return;
+
+ break;
+
case DNS_PROTOCOL_DNS:
break;
@@ -446,6 +459,13 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
}
if (DNS_PACKET_TC(p)) {
+
+ /* Truncated packets for mDNS are not allowed. Give up immediately. */
+ if (t->scope->protocol == DNS_PROTOCOL_MDNS) {
+ dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+ return;
+ }
+
/* Response was truncated, let's try again with good old TCP */
r = dns_transaction_open_tcp(t);
if (r == -ESRCH) {
@@ -454,7 +474,7 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
return;
}
if (r < 0) {
- /* On LLMNR, if we cannot connect to the host,
+ /* On LLMNR and mDNS, if we cannot connect to the host,
* we immediately give up */
if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
@@ -481,29 +501,31 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
return;
}
- /* Only consider responses with equivalent query section to the request */
- if (p->question->n_keys != 1 || dns_resource_key_equal(p->question->keys[0], t->key) <= 0) {
- dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
- return;
- }
+ if (t->scope->protocol == DNS_PROTOCOL_DNS) {
+ /* Only consider responses with equivalent query section to the request */
+ if (p->question->n_keys != 1 || dns_resource_key_equal(p->question->keys[0], t->key) <= 0) {
+ dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+ return;
+ }
- /* Install the answer as answer to the transaction */
- dns_answer_unref(t->answer);
- t->answer = dns_answer_ref(p->answer);
- t->answer_rcode = DNS_PACKET_RCODE(p);
- t->answer_authenticated = t->scope->dnssec_mode == DNSSEC_TRUST && DNS_PACKET_AD(p);
-
- /* According to RFC 4795, section 2.9. only the RRs from the answer section shall be cached */
- if (DNS_PACKET_SHALL_CACHE(p))
- dns_cache_put(&t->scope->cache,
- t->key,
- DNS_PACKET_RCODE(p),
- p->answer,
- DNS_PACKET_ANCOUNT(p),
- t->answer_authenticated,
- 0,
- p->family,
- &p->sender);
+ /* Install the answer as answer to the transaction */
+ dns_answer_unref(t->answer);
+ t->answer = dns_answer_ref(p->answer);
+ t->answer_rcode = DNS_PACKET_RCODE(p);
+ t->answer_authenticated = t->scope->dnssec_mode == DNSSEC_TRUST && DNS_PACKET_AD(p);
+
+ /* According to RFC 4795, section 2.9. only the RRs from the answer section shall be cached */
+ if (DNS_PACKET_SHALL_CACHE(p))
+ dns_cache_put(&t->scope->cache,
+ t->key,
+ DNS_PACKET_RCODE(p),
+ p->answer,
+ DNS_PACKET_ANCOUNT(p),
+ t->answer_authenticated,
+ 0,
+ p->family,
+ &p->sender);
+ }
if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
dns_transaction_complete(t, DNS_TRANSACTION_SUCCESS);
@@ -571,21 +593,26 @@ static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdat
assert(s);
assert(t);
- /* Timeout reached? Increase the timeout for the server used */
- switch (t->scope->protocol) {
- case DNS_PROTOCOL_DNS:
- assert(t->server);
+ if (!t->initial_jitter_scheduled || t->initial_jitter_elapsed) {
+ /* Timeout reached? Increase the timeout for the server used */
+ switch (t->scope->protocol) {
+ case DNS_PROTOCOL_DNS:
+ assert(t->server);
- dns_server_packet_lost(t->server, t->current_features, usec - t->start_usec);
+ dns_server_packet_lost(t->server, t->current_features, usec - t->start_usec);
- break;
- case DNS_PROTOCOL_LLMNR:
- case DNS_PROTOCOL_MDNS:
- dns_scope_packet_lost(t->scope, usec - t->start_usec);
+ break;
+ case DNS_PROTOCOL_LLMNR:
+ case DNS_PROTOCOL_MDNS:
+ dns_scope_packet_lost(t->scope, usec - t->start_usec);
- break;
- default:
- assert_not_reached("Invalid DNS protocol.");
+ break;
+ default:
+ assert_not_reached("Invalid DNS protocol.");
+ }
+
+ if (t->initial_jitter_scheduled)
+ t->initial_jitter_elapsed = true;
}
/* ...and try again with a new server */
@@ -598,38 +625,6 @@ static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdat
return 0;
}
-static int dns_transaction_make_packet(DnsTransaction *t) {
- _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
- int r;
-
- assert(t);
-
- if (t->sent)
- return 0;
-
- r = dns_packet_new_query(&p, t->scope->protocol, 0, t->scope->dnssec_mode == DNSSEC_YES);
- if (r < 0)
- return r;
-
- r = dns_scope_good_key(t->scope, t->key);
- if (r < 0)
- return r;
- if (r == 0)
- return -EDOM;
-
- r = dns_packet_append_key(p, t->key, NULL);
- if (r < 0)
- return r;
-
- DNS_PACKET_HEADER(p)->qdcount = htobe16(1);
- DNS_PACKET_HEADER(p)->id = t->id;
-
- t->sent = p;
- p = NULL;
-
- return 0;
-}
-
static usec_t transaction_get_resend_timeout(DnsTransaction *t) {
assert(t);
assert(t->scope);
@@ -639,17 +634,18 @@ static usec_t transaction_get_resend_timeout(DnsTransaction *t) {
assert(t->server);
return t->server->resend_timeout;
- case DNS_PROTOCOL_LLMNR:
case DNS_PROTOCOL_MDNS:
+ assert(t->n_attempts > 0);
+ return (1 << (t->n_attempts - 1)) * USEC_PER_SEC;
+ case DNS_PROTOCOL_LLMNR:
return t->scope->resend_timeout;
default:
assert_not_reached("Invalid DNS protocol.");
}
}
-int dns_transaction_go(DnsTransaction *t) {
+static int dns_transaction_prepare_next_attempt(DnsTransaction *t, usec_t ts) {
bool had_stream;
- usec_t ts;
int r;
assert(t);
@@ -658,11 +654,6 @@ int dns_transaction_go(DnsTransaction *t) {
dns_transaction_stop(t);
- log_debug("Excercising transaction on scope %s on %s/%s",
- dns_protocol_to_string(t->scope->protocol),
- t->scope->link ? t->scope->link->name : "*",
- t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
-
if (t->n_attempts >= TRANSACTION_ATTEMPTS_MAX(t->scope->protocol)) {
dns_transaction_complete(t, DNS_TRANSACTION_ATTEMPTS_MAX_REACHED);
return 0;
@@ -675,8 +666,6 @@ int dns_transaction_go(DnsTransaction *t) {
return 0;
}
- assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &ts) >= 0);
-
t->n_attempts++;
t->start_usec = ts;
t->received = dns_packet_unref(t->received);
@@ -739,31 +728,203 @@ int dns_transaction_go(DnsTransaction *t) {
}
}
- if (t->scope->protocol == DNS_PROTOCOL_LLMNR && !t->initial_jitter) {
- usec_t jitter;
+ return 1;
+}
+
+static int dns_transaction_make_packet_mdns(DnsTransaction *t) {
+
+ _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
+ bool add_known_answers = false;
+ DnsTransaction *other;
+ unsigned qdcount;
+ usec_t ts;
+ int r;
+
+ assert(t);
+ assert(t->scope->protocol == DNS_PROTOCOL_MDNS);
+
+ /* Discard any previously prepared packet, so we can start over and coaleasce again */
+ t->sent = dns_packet_unref(t->sent);
+
+ r = dns_packet_new_query(&p, t->scope->protocol, 0, false);
+ if (r < 0)
+ return r;
+
+ r = dns_packet_append_key(p, t->key, NULL);
+ if (r < 0)
+ return r;
+
+ qdcount = 1;
+
+ if (dns_key_is_shared(t->key))
+ add_known_answers = true;
+
+ /*
+ * For mDNS, we want to coalesce as many open queries in pending transactions into one single
+ * query packet on the wire as possible. To achieve that, we iterate through all pending transactions
+ * in our current scope, and see whether their timing contraints allow them to be sent.
+ */
+
+ assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &ts) >= 0);
+
+ LIST_FOREACH(transactions_by_scope, other, t->scope->transactions) {
+
+ /* Skip ourselves */
+ if (other == t)
+ continue;
+
+ if (other->state != DNS_TRANSACTION_PENDING)
+ continue;
+
+ if (other->next_attempt_after > ts)
+ continue;
+
+ if (qdcount >= UINT16_MAX)
+ break;
+
+ r = dns_packet_append_key(p, other->key, NULL);
+
+ /*
+ * If we can't stuff more questions into the packet, just give up.
+ * One of the 'other' transactions will fire later and take care of the rest.
+ */
+ if (r == -EMSGSIZE)
+ break;
+
+ if (r < 0)
+ return r;
+
+ r = dns_transaction_prepare_next_attempt(other, ts);
+ if (r <= 0)
+ continue;
+
+ ts += transaction_get_resend_timeout(other);
+
+ r = sd_event_add_time(
+ other->scope->manager->event,
+ &other->timeout_event_source,
+ clock_boottime_or_monotonic(),
+ ts, 0,
+ on_transaction_timeout, other);
+ if (r < 0)
+ return r;
+
+ other->state = DNS_TRANSACTION_PENDING;
+ other->next_attempt_after = ts;
+
+ qdcount ++;
+
+ if (dns_key_is_shared(other->key))
+ add_known_answers = true;
+ }
+
+ DNS_PACKET_HEADER(p)->qdcount = htobe16(qdcount);
+ DNS_PACKET_HEADER(p)->id = t->id;
+
+ /* Append known answer section if we're asking for any shared record */
+ if (add_known_answers) {
+ r = dns_cache_export_shared_to_packet(&t->scope->cache, p);
+ if (r < 0)
+ return r;
+ }
+
+ t->sent = p;
+ p = NULL;
+
+ return 0;
+}
+
+static int dns_transaction_make_packet(DnsTransaction *t) {
+ _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
+ int r;
+
+ assert(t);
+
+ if (t->scope->protocol == DNS_PROTOCOL_MDNS)
+ return dns_transaction_make_packet_mdns(t);
+
+ if (t->sent)
+ return 0;
+
+ r = dns_packet_new_query(&p, t->scope->protocol, 0, t->scope->dnssec_mode == DNSSEC_YES);
+ if (r < 0)
+ return r;
+
+ r = dns_scope_good_key(t->scope, t->key);
+ if (r < 0)
+ return r;
+ if (r == 0)
+ return -EDOM;
+
+ r = dns_packet_append_key(p, t->key, NULL);
+ if (r < 0)
+ return r;
+
+ DNS_PACKET_HEADER(p)->qdcount = htobe16(1);
+ DNS_PACKET_HEADER(p)->id = t->id;
+
+ t->sent = p;
+ p = NULL;
+
+ return 0;
+}
+
+int dns_transaction_go(DnsTransaction *t) {
+ usec_t ts;
+ int r;
+
+ assert(t);
+
+ assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &ts) >= 0);
+ r = dns_transaction_prepare_next_attempt(t, ts);
+ if (r <= 0)
+ return r;
+
+ log_debug("Excercising transaction on scope %s on %s/%s",
+ dns_protocol_to_string(t->scope->protocol),
+ t->scope->link ? t->scope->link->name : "*",
+ t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
+
+ if (!t->initial_jitter_scheduled &&
+ (t->scope->protocol == DNS_PROTOCOL_LLMNR ||
+ t->scope->protocol == DNS_PROTOCOL_MDNS)) {
+ usec_t jitter, accuracy;
/* RFC 4795 Section 2.7 suggests all queries should be
* delayed by a random time from 0 to JITTER_INTERVAL. */
- t->initial_jitter = true;
+ t->initial_jitter_scheduled = true;
random_bytes(&jitter, sizeof(jitter));
- jitter %= LLMNR_JITTER_INTERVAL_USEC;
+
+ switch (t->scope->protocol) {
+ case DNS_PROTOCOL_LLMNR:
+ jitter %= LLMNR_JITTER_INTERVAL_USEC;
+ accuracy = LLMNR_JITTER_INTERVAL_USEC;
+ break;
+ case DNS_PROTOCOL_MDNS:
+ jitter %= MDNS_JITTER_RANGE_USEC;
+ jitter += MDNS_JITTER_MIN_USEC;
+ accuracy = MDNS_JITTER_RANGE_USEC;
+ break;
+ default:
+ assert_not_reached("bad protocol");
+ }
r = sd_event_add_time(
t->scope->manager->event,
&t->timeout_event_source,
clock_boottime_or_monotonic(),
- ts + jitter,
- LLMNR_JITTER_INTERVAL_USEC,
+ ts + jitter, accuracy,
on_transaction_timeout, t);
if (r < 0)
return r;
t->n_attempts = 0;
+ t->next_attempt_after = ts;
t->state = DNS_TRANSACTION_PENDING;
- log_debug("Delaying LLMNR transaction for " USEC_FMT "us.", jitter);
+ log_debug("Delaying %s transaction for " USEC_FMT "us.", dns_protocol_to_string(t->scope->protocol), jitter);
return 0;
}
@@ -810,16 +971,20 @@ int dns_transaction_go(DnsTransaction *t) {
return dns_transaction_go(t);
}
+ ts += transaction_get_resend_timeout(t);
+
r = sd_event_add_time(
t->scope->manager->event,
&t->timeout_event_source,
clock_boottime_or_monotonic(),
- ts + transaction_get_resend_timeout(t), 0,
+ ts, 0,
on_transaction_timeout, t);
if (r < 0)
return r;
t->state = DNS_TRANSACTION_PENDING;
+ t->next_attempt_after = ts;
+
return 1;
}
diff --git a/src/resolve/resolved-dns-transaction.h b/src/resolve/resolved-dns-transaction.h
index a3058ce6e8..af08b20e44 100644
--- a/src/resolve/resolved-dns-transaction.h
+++ b/src/resolve/resolved-dns-transaction.h
@@ -62,7 +62,8 @@ struct DnsTransaction {
DnsTransactionState state;
uint16_t id;
- bool initial_jitter;
+ bool initial_jitter_scheduled;
+ bool initial_jitter_elapsed;
DnsPacket *sent, *received;
@@ -72,6 +73,7 @@ struct DnsTransaction {
bool answer_authenticated;
usec_t start_usec;
+ usec_t next_attempt_after;
sd_event_source *timeout_event_source;
unsigned n_attempts;
@@ -119,6 +121,10 @@ DnsTransactionSource dns_transaction_source_from_string(const char *s) _pure_;
/* LLMNR Jitter interval, see RFC 4795 Section 7 */
#define LLMNR_JITTER_INTERVAL_USEC (100 * USEC_PER_MSEC)
+/* mDNS Jitter interval, see RFC 6762 Section 5.2 */
+#define MDNS_JITTER_MIN_USEC (20 * USEC_PER_MSEC)
+#define MDNS_JITTER_RANGE_USEC (100 * USEC_PER_MSEC)
+
/* Maximum attempts to send DNS requests, across all DNS servers */
#define DNS_TRANSACTION_ATTEMPTS_MAX 16
diff --git a/src/resolve/resolved-link.c b/src/resolve/resolved-link.c
index ddd9427dab..84100bd988 100644
--- a/src/resolve/resolved-link.c
+++ b/src/resolve/resolved-link.c
@@ -77,6 +77,8 @@ Link *link_free(Link *l) {
dns_scope_free(l->unicast_scope);
dns_scope_free(l->llmnr_ipv4_scope);
dns_scope_free(l->llmnr_ipv6_scope);
+ dns_scope_free(l->mdns_ipv4_scope);
+ dns_scope_free(l->mdns_ipv6_scope);
free(l);
return NULL;
@@ -118,6 +120,28 @@ static void link_allocate_scopes(Link *l) {
}
} else
l->llmnr_ipv6_scope = dns_scope_free(l->llmnr_ipv6_scope);
+
+ if (link_relevant(l, AF_INET) &&
+ l->mdns_support != SUPPORT_NO &&
+ l->manager->mdns_support != SUPPORT_NO) {
+ if (!l->mdns_ipv4_scope) {
+ r = dns_scope_new(l->manager, &l->mdns_ipv4_scope, l, DNS_PROTOCOL_MDNS, AF_INET);
+ if (r < 0)
+ log_warning_errno(r, "Failed to allocate mDNS IPv4 scope: %m");
+ }
+ } else
+ l->mdns_ipv4_scope = dns_scope_free(l->mdns_ipv4_scope);
+
+ if (link_relevant(l, AF_INET6) &&
+ l->mdns_support != SUPPORT_NO &&
+ l->manager->mdns_support != SUPPORT_NO) {
+ if (!l->mdns_ipv6_scope) {
+ r = dns_scope_new(l->manager, &l->mdns_ipv6_scope, l, DNS_PROTOCOL_MDNS, AF_INET6);
+ if (r < 0)
+ log_warning_errno(r, "Failed to allocate mDNS IPv6 scope: %m");
+ }
+ } else
+ l->mdns_ipv6_scope = dns_scope_free(l->mdns_ipv6_scope);
}
void link_add_rrs(Link *l, bool force_remove) {
diff --git a/src/resolve/resolved-link.h b/src/resolve/resolved-link.h
index eb00015bd5..a3b406bbc2 100644
--- a/src/resolve/resolved-link.h
+++ b/src/resolve/resolved-link.h
@@ -67,10 +67,13 @@ struct Link {
unsigned n_search_domains;
Support llmnr_support;
+ Support mdns_support;
DnsScope *unicast_scope;
DnsScope *llmnr_ipv4_scope;
DnsScope *llmnr_ipv6_scope;
+ DnsScope *mdns_ipv4_scope;
+ DnsScope *mdns_ipv6_scope;
char name[IF_NAMESIZE];
uint32_t mtu;
diff --git a/src/resolve/resolved-manager.c b/src/resolve/resolved-manager.c
index 5a3696ccb0..a2677f442a 100644
--- a/src/resolve/resolved-manager.c
+++ b/src/resolve/resolved-manager.c
@@ -40,6 +40,7 @@
#include "resolved-llmnr.h"
#include "resolved-manager.h"
#include "resolved-resolv-conf.h"
+#include "resolved-mdns.h"
#include "socket-util.h"
#include "string-table.h"
#include "string-util.h"
@@ -472,6 +473,7 @@ int manager_new(Manager **ret) {
m->llmnr_ipv4_udp_fd = m->llmnr_ipv6_udp_fd = -1;
m->llmnr_ipv4_tcp_fd = m->llmnr_ipv6_tcp_fd = -1;
+ m->mdns_ipv4_fd = m->mdns_ipv6_fd = -1;
m->hostname_fd = -1;
m->llmnr_support = SUPPORT_YES;
@@ -528,6 +530,10 @@ int manager_start(Manager *m) {
if (r < 0)
return r;
+ r = manager_mdns_start(m);
+ if (r < 0)
+ return r;
+
return 0;
}
@@ -559,6 +565,7 @@ Manager *manager_free(Manager *m) {
sd_event_source_unref(m->rtnl_event_source);
manager_llmnr_stop(m);
+ manager_mdns_stop(m);
sd_bus_slot_unref(m->prepare_for_sleep_slot);
sd_event_source_unref(m->bus_retry_event_source);
@@ -1024,11 +1031,25 @@ DnsScope* manager_find_scope(Manager *m, DnsPacket *p) {
if (!l)
return NULL;
- if (p->protocol == DNS_PROTOCOL_LLMNR) {
+ switch (p->protocol) {
+ case DNS_PROTOCOL_LLMNR:
if (p->family == AF_INET)
return l->llmnr_ipv4_scope;
else if (p->family == AF_INET6)
return l->llmnr_ipv6_scope;
+
+ break;
+
+ case DNS_PROTOCOL_MDNS:
+ if (p->family == AF_INET)
+ return l->mdns_ipv4_scope;
+ else if (p->family == AF_INET6)
+ return l->mdns_ipv6_scope;
+
+ break;
+
+ default:
+ break;
}
return NULL;
diff --git a/src/resolve/resolved-manager.h b/src/resolve/resolved-manager.h
index 1056f23ab7..b52273403a 100644
--- a/src/resolve/resolved-manager.h
+++ b/src/resolve/resolved-manager.h
@@ -54,6 +54,7 @@ struct Manager {
sd_event *event;
Support llmnr_support;
+ Support mdns_support;
/* Network */
Hashmap *links;
@@ -102,6 +103,13 @@ struct Manager {
sd_event_source *llmnr_ipv4_tcp_event_source;
sd_event_source *llmnr_ipv6_tcp_event_source;
+ /* mDNS */
+ int mdns_ipv4_fd;
+ int mdns_ipv6_fd;
+
+ sd_event_source *mdns_ipv4_event_source;
+ sd_event_source *mdns_ipv6_event_source;
+
/* dbus */
sd_bus *bus;
sd_event_source *bus_retry_event_source;
diff --git a/src/resolve/resolved-mdns.c b/src/resolve/resolved-mdns.c
new file mode 100644
index 0000000000..096a4b1fe5
--- /dev/null
+++ b/src/resolve/resolved-mdns.c
@@ -0,0 +1,288 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2015 Daniel Mack
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+ ***/
+
+#include <resolv.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+
+#include "fd-util.h"
+#include "resolved-manager.h"
+#include "resolved-mdns.h"
+
+void manager_mdns_stop(Manager *m) {
+ assert(m);
+
+ m->mdns_ipv4_event_source = sd_event_source_unref(m->mdns_ipv4_event_source);
+ m->mdns_ipv4_fd = safe_close(m->mdns_ipv4_fd);
+
+ m->mdns_ipv6_event_source = sd_event_source_unref(m->mdns_ipv6_event_source);
+ m->mdns_ipv6_fd = safe_close(m->mdns_ipv6_fd);
+}
+
+int manager_mdns_start(Manager *m) {
+ int r;
+
+ assert(m);
+
+ if (m->mdns_support == SUPPORT_NO)
+ return 0;
+
+ r = manager_mdns_ipv4_fd(m);
+ if (r == -EADDRINUSE)
+ goto eaddrinuse;
+ if (r < 0)
+ return r;
+
+ if (socket_ipv6_is_supported()) {
+ r = manager_mdns_ipv6_fd(m);
+ if (r == -EADDRINUSE)
+ goto eaddrinuse;
+ if (r < 0)
+ return r;
+ }
+
+ return 0;
+
+eaddrinuse:
+ log_warning("There appears to be another mDNS responder running. Turning off mDNS support.");
+ m->mdns_support = SUPPORT_NO;
+ manager_mdns_stop(m);
+
+ return 0;
+}
+
+static int on_mdns_packet(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
+ _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
+ Manager *m = userdata;
+ DnsScope *scope;
+ int r;
+
+ r = manager_recv(m, fd, DNS_PROTOCOL_MDNS, &p);
+ if (r <= 0)
+ return r;
+
+ scope = manager_find_scope(m, p);
+ if (!scope) {
+ log_warning("Got mDNS UDP packet on unknown scope. Ignoring.");
+ return 0;
+ }
+
+ if (dns_packet_validate_reply(p) > 0) {
+ unsigned i;
+
+ log_debug("Got mDNS reply packet");
+
+ /*
+ * mDNS is different from regular DNS and LLMNR with regard to handling responses.
+ * While on other protocols, we can ignore every answer that doesn't match a question
+ * we broadcast earlier, RFC6762, section 18.1 recommends looking at and caching all
+ * incoming information, regardless of the DNS packet ID.
+ *
+ * Hence, extract the packet here, and try to find a transaction for answer the we got
+ * and complete it. Also store the new information in scope's cache.
+ */
+ r = dns_packet_extract(p);
+ if (r < 0) {
+ log_debug("mDNS packet extraction failed.");
+ return 0;
+ }
+
+ dns_scope_check_conflicts(scope, p);
+
+ for (i = 0; i < p->answer->n_rrs; i++) {
+ DnsResourceRecord *rr;
+ DnsTransaction *t;
+
+ rr = p->answer->items[i].rr;
+
+ t = dns_scope_find_transaction(scope, rr->key, false);
+ if (t)
+ dns_transaction_process_reply(t, p);
+ }
+
+ dns_cache_put(&scope->cache, NULL, DNS_PACKET_RCODE(p), p->answer,
+ p->answer->n_rrs, false, 0, p->family, &p->sender);
+
+ } else if (dns_packet_validate_query(p) > 0) {
+ log_debug("Got mDNS query packet for id %u", DNS_PACKET_ID(p));
+
+ dns_scope_process_query(scope, NULL, p);
+ } else
+ log_debug("Invalid mDNS UDP packet.");
+
+ return 0;
+}
+
+int manager_mdns_ipv4_fd(Manager *m) {
+ union sockaddr_union sa = {
+ .in.sin_family = AF_INET,
+ .in.sin_port = htobe16(MDNS_PORT),
+ };
+ static const int one = 1, pmtu = IP_PMTUDISC_DONT, ttl = 255;
+ int r;
+
+ assert(m);
+
+ if (m->mdns_ipv4_fd >= 0)
+ return m->mdns_ipv4_fd;
+
+ m->mdns_ipv4_fd = socket(AF_INET, SOCK_DGRAM|SOCK_CLOEXEC|SOCK_NONBLOCK, 0);
+ if (m->mdns_ipv4_fd < 0)
+ return -errno;
+
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_TTL, &ttl, sizeof(ttl));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_MULTICAST_TTL, &ttl, sizeof(ttl));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_MULTICAST_LOOP, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv4_fd, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_PKTINFO, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_RECVTTL, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ /* Disable Don't-Fragment bit in the IP header */
+ r = setsockopt(m->mdns_ipv4_fd, IPPROTO_IP, IP_MTU_DISCOVER, &pmtu, sizeof(pmtu));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = bind(m->mdns_ipv4_fd, &sa.sa, sizeof(sa.in));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = sd_event_add_io(m->event, &m->mdns_ipv4_event_source, m->mdns_ipv4_fd, EPOLLIN, on_mdns_packet, m);
+ if (r < 0)
+ goto fail;
+
+ return m->mdns_ipv4_fd;
+
+fail:
+ m->mdns_ipv4_fd = safe_close(m->mdns_ipv4_fd);
+ return r;
+}
+
+int manager_mdns_ipv6_fd(Manager *m) {
+ union sockaddr_union sa = {
+ .in6.sin6_family = AF_INET6,
+ .in6.sin6_port = htobe16(MDNS_PORT),
+ };
+ static const int one = 1, ttl = 255;
+ int r;
+
+ assert(m);
+
+ if (m->mdns_ipv6_fd >= 0)
+ return m->mdns_ipv6_fd;
+
+ m->mdns_ipv6_fd = socket(AF_INET6, SOCK_DGRAM|SOCK_CLOEXEC|SOCK_NONBLOCK, 0);
+ if (m->mdns_ipv6_fd < 0)
+ return -errno;
+
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_UNICAST_HOPS, &ttl, sizeof(ttl));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ /* RFC 4795, section 2.5 recommends setting the TTL of UDP packets to 255. */
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_MULTICAST_HOPS, &ttl, sizeof(ttl));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_MULTICAST_LOOP, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_V6ONLY, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv6_fd, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_RECVPKTINFO, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = setsockopt(m->mdns_ipv6_fd, IPPROTO_IPV6, IPV6_RECVHOPLIMIT, &one, sizeof(one));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = bind(m->mdns_ipv6_fd, &sa.sa, sizeof(sa.in6));
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ r = sd_event_add_io(m->event, &m->mdns_ipv6_event_source, m->mdns_ipv6_fd, EPOLLIN, on_mdns_packet, m);
+ if (r < 0) {
+ r = -errno;
+ goto fail;
+ }
+
+ return m->mdns_ipv6_fd;
+
+fail:
+ m->mdns_ipv6_fd = safe_close(m->mdns_ipv6_fd);
+ return r;
+}
diff --git a/src/resolve/resolved-mdns.h b/src/resolve/resolved-mdns.h
new file mode 100644
index 0000000000..8a84010615
--- /dev/null
+++ b/src/resolve/resolved-mdns.h
@@ -0,0 +1,32 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+ This file is part of systemd.
+
+ Copyright 2015 Daniel Mack
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "resolved-manager.h"
+
+#define MDNS_PORT 5353
+
+int manager_mdns_ipv4_fd(Manager *m);
+int manager_mdns_ipv6_fd(Manager *m);
+
+void manager_mdns_stop(Manager *m);
+int manager_mdns_start(Manager *m);
diff --git a/src/test/test-rbtree.c b/src/test/test-rbtree.c
new file mode 100644
index 0000000000..8ae416c557
--- /dev/null
+++ b/src/test/test-rbtree.c
@@ -0,0 +1,362 @@
+/***
+ This file is part of systemd. See COPYING for details.
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * Tests for RB-Tree
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include "c-rbtree.h"
+
+/* verify that all API calls are exported */
+static void test_api(void) {
+ CRBTree t = {};
+ CRBNode n = C_RBNODE_INIT(n);
+
+ assert(!c_rbnode_is_linked(&n));
+
+ /* init, is_linked, add, remove, remove_init */
+
+ c_rbtree_add(&t, NULL, &t.root, &n);
+ assert(c_rbnode_is_linked(&n));
+
+ c_rbtree_remove_init(&t, &n);
+ assert(!c_rbnode_is_linked(&n));
+
+ c_rbtree_add(&t, NULL, &t.root, &n);
+ assert(c_rbnode_is_linked(&n));
+
+ c_rbtree_remove(&t, &n);
+ assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */
+
+ c_rbnode_init(&n);
+ assert(!c_rbnode_is_linked(&n));
+
+ /* first, last, leftmost, rightmost, next, prev */
+
+ assert(!c_rbtree_first(&t));
+ assert(!c_rbtree_last(&t));
+ assert(&n == c_rbnode_leftmost(&n));
+ assert(&n == c_rbnode_rightmost(&n));
+ assert(!c_rbnode_next(&n));
+ assert(!c_rbnode_prev(&n));
+}
+
+/* copied from c-rbtree.c, relies on internal representation */
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+ return !((unsigned long)n->__parent_and_color & 1UL);
+}
+
+/* copied from c-rbtree.c, relies on internal representation */
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+ return !!((unsigned long)n->__parent_and_color & 1UL);
+}
+
+static size_t validate(CRBTree *t) {
+ unsigned int i_black, n_black;
+ CRBNode *n, *p, *o;
+ size_t count = 0;
+
+ assert(t);
+ assert(!t->root || c_rbnode_is_black(t->root));
+
+ /* traverse to left-most child, count black nodes */
+ i_black = 0;
+ n = t->root;
+ while (n && n->left) {
+ if (c_rbnode_is_black(n))
+ ++i_black;
+ n = n->left;
+ }
+ n_black = i_black;
+
+ /*
+ * Traverse tree and verify correctness:
+ * 1) A node is either red or black
+ * 2) The root is black
+ * 3) All leaves are black
+ * 4) Every red node must have two black child nodes
+ * 5) Every path to a leaf contains the same number of black nodes
+ *
+ * Note that NULL nodes are considered black, which is why we don't
+ * check for 3).
+ */
+ o = NULL;
+ while (n) {
+ ++count;
+
+ /* verify natural order */
+ assert(n > o);
+ o = n;
+
+ /* verify consistency */
+ assert(!n->right || c_rbnode_parent(n->right) == n);
+ assert(!n->left || c_rbnode_parent(n->left) == n);
+
+ /* verify 2) */
+ if (!c_rbnode_parent(n))
+ assert(c_rbnode_is_black(n));
+
+ if (c_rbnode_is_red(n)) {
+ /* verify 4) */
+ assert(!n->left || c_rbnode_is_black(n->left));
+ assert(!n->right || c_rbnode_is_black(n->right));
+ } else {
+ /* verify 1) */
+ assert(c_rbnode_is_black(n));
+ }
+
+ /* verify 5) */
+ if (!n->left && !n->right)
+ assert(i_black == n_black);
+
+ /* get next node */
+ if (n->right) {
+ n = n->right;
+ if (c_rbnode_is_black(n))
+ ++i_black;
+
+ while (n->left) {
+ n = n->left;
+ if (c_rbnode_is_black(n))
+ ++i_black;
+ }
+ } else {
+ while ((p = c_rbnode_parent(n)) && n == p->right) {
+ n = p;
+ if (c_rbnode_is_black(p->right))
+ --i_black;
+ }
+
+ n = p;
+ if (p && c_rbnode_is_black(p->left))
+ --i_black;
+ }
+ }
+
+ return count;
+}
+
+static void insert(CRBTree *t, CRBNode *n) {
+ CRBNode **i, *p;
+
+ assert(t);
+ assert(n);
+ assert(!c_rbnode_is_linked(n));
+
+ i = &t->root;
+ p = NULL;
+ while (*i) {
+ p = *i;
+ if (n < *i) {
+ i = &(*i)->left;
+ } else {
+ assert(n > *i);
+ i = &(*i)->right;
+ }
+ }
+
+ c_rbtree_add(t, p, i, n);
+}
+
+static void shuffle(void **nodes, size_t n_memb) {
+ unsigned int i, j;
+ void *t;
+
+ for (i = 0; i < n_memb; ++i) {
+ j = rand() % n_memb;
+ t = nodes[j];
+ nodes[j] = nodes[i];
+ nodes[i] = t;
+ }
+}
+
+/* run some pseudo-random tests on the tree */
+static void test_shuffle(void) {
+ CRBNode *nodes[256];
+ CRBTree t = {};
+ unsigned int i, j;
+ size_t n;
+
+ /* allocate and initialize all nodes */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ nodes[i] = malloc(sizeof(*nodes[i]));
+ assert(nodes[i]);
+ c_rbnode_init(nodes[i]);
+ }
+
+ /* shuffle nodes and validate *empty* tree */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+ n = validate(&t);
+ assert(n == 0);
+
+ /* add all nodes and validate after each insertion */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ insert(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == i + 1);
+ }
+
+ /* shuffle nodes again */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+ /* remove all nodes (in different order) and validate on each round */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ c_rbtree_remove(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+ c_rbnode_init(nodes[i]);
+ }
+
+ /* shuffle nodes and validate *empty* tree again */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+ n = validate(&t);
+ assert(n == 0);
+
+ /* add all nodes again */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ insert(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == i + 1);
+ }
+
+ /* 4 times, remove half of the nodes and add them again */
+ for (j = 0; j < 4; ++j) {
+ /* shuffle nodes again */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+ /* remove half of the nodes */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+ c_rbtree_remove(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+ c_rbnode_init(nodes[i]);
+ }
+
+ /* shuffle the removed half */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes) / 2);
+
+ /* add the removed half again */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+ insert(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
+ }
+ }
+
+ /* shuffle nodes again */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+ /* remove all */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ c_rbtree_remove(&t, nodes[i]);
+ n = validate(&t);
+ assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+ c_rbnode_init(nodes[i]);
+ }
+
+ /* free nodes again */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+ free(nodes[i]);
+}
+
+typedef struct {
+ unsigned long key;
+ CRBNode rb;
+} Node;
+
+#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
+
+static int compare(CRBTree *t, void *k, CRBNode *n) {
+ unsigned long key = (unsigned long)k;
+ Node *node = node_from_rb(n);
+
+ return (key < node->key) ? -1 : (key > node->key) ? 1 : 0;
+}
+
+/* run tests against the c_rbtree_find*() helpers */
+static void test_map(void) {
+ CRBNode **slot, *p;
+ CRBTree t = {};
+ Node *nodes[2048];
+ unsigned long i;
+
+ /* allocate and initialize all nodes */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ nodes[i] = malloc(sizeof(*nodes[i]));
+ assert(nodes[i]);
+ nodes[i]->key = i;
+ c_rbnode_init(&nodes[i]->rb);
+ }
+
+ /* shuffle nodes */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+ /* add all nodes, and verify that each node is linked */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ assert(!c_rbnode_is_linked(&nodes[i]->rb));
+ assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+
+ slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p);
+ assert(slot);
+ c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+
+ assert(c_rbnode_is_linked(&nodes[i]->rb));
+ assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+ }
+
+ /* shuffle nodes again */
+ shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+ /* remove all nodes (in different order) */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+ assert(c_rbnode_is_linked(&nodes[i]->rb));
+ assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+
+ c_rbtree_remove_init(&t, &nodes[i]->rb);
+
+ assert(!c_rbnode_is_linked(&nodes[i]->rb));
+ assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+ }
+
+ /* free nodes again */
+ for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+ free(nodes[i]);
+}
+
+int main(int argc, char **argv) {
+ unsigned int i;
+
+ /* we want stable tests, so use fixed seed */
+ srand(0xdeadbeef);
+
+ test_api();
+
+ /*
+ * The tests are pseudo random; run them multiple times, each run will
+ * have different orders and thus different results.
+ */
+ for (i = 0; i < 4; ++i) {
+ test_shuffle();
+ test_map();
+ }
+
+ return 0;
+}
diff --git a/src/test/test-rlimit-util.c b/src/test/test-rlimit-util.c
new file mode 100644
index 0000000000..00d3ecc0de
--- /dev/null
+++ b/src/test/test-rlimit-util.c
@@ -0,0 +1,69 @@
+/***
+ This file is part of systemd
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <sys/resource.h>
+
+#include "capability-util.h"
+#include "macro.h"
+#include "rlimit-util.h"
+#include "string-util.h"
+#include "util.h"
+
+int main(int argc, char *argv[]) {
+ struct rlimit old, new, high;
+ struct rlimit err = {
+ .rlim_cur = 10,
+ .rlim_max = 5,
+ };
+
+ log_parse_environment();
+ log_open();
+
+ assert_se(drop_capability(CAP_SYS_RESOURCE) == 0);
+
+ assert_se(getrlimit(RLIMIT_NOFILE, &old) == 0);
+ new.rlim_cur = MIN(5U, old.rlim_max);
+ new.rlim_max = MIN(10U, old.rlim_max);
+ assert_se(setrlimit(RLIMIT_NOFILE, &new) >= 0);
+
+ assert_se(rlimit_from_string("LimitNOFILE") == RLIMIT_NOFILE);
+ assert_se(rlimit_from_string("DefaultLimitNOFILE") == -1);
+
+ assert_se(streq_ptr(rlimit_to_string(RLIMIT_NOFILE), "LimitNOFILE"));
+ assert_se(rlimit_to_string(-1) == NULL);
+
+ assert_se(getrlimit(RLIMIT_NOFILE, &old) == 0);
+ assert_se(setrlimit_closest(RLIMIT_NOFILE, &old) == 0);
+ assert_se(getrlimit(RLIMIT_NOFILE, &new) == 0);
+ assert_se(old.rlim_cur == new.rlim_cur);
+ assert_se(old.rlim_max == new.rlim_max);
+
+ assert_se(getrlimit(RLIMIT_NOFILE, &old) == 0);
+ high = RLIMIT_MAKE_CONST(old.rlim_max + 1);
+ assert_se(setrlimit_closest(RLIMIT_NOFILE, &high) == 0);
+ assert_se(getrlimit(RLIMIT_NOFILE, &new) == 0);
+ assert_se(new.rlim_max == old.rlim_max);
+ assert_se(new.rlim_cur == new.rlim_max);
+
+ assert_se(getrlimit(RLIMIT_NOFILE, &old) == 0);
+ assert_se(setrlimit_closest(RLIMIT_NOFILE, &err) == -EINVAL);
+ assert_se(getrlimit(RLIMIT_NOFILE, &new) == 0);
+ assert_se(old.rlim_cur == new.rlim_cur);
+ assert_se(old.rlim_max == new.rlim_max);
+
+ return 0;
+}
diff --git a/src/udev/udev-event.c b/src/udev/udev-event.c
index 12ba2025f4..c1dcee6c73 100644
--- a/src/udev/udev-event.c
+++ b/src/udev/udev-event.c
@@ -850,11 +850,11 @@ void udev_event_execute_rules(struct udev_event *event,
/* disable watch during event processing */
if (major(udev_device_get_devnum(dev)) != 0)
udev_watch_end(event->udev, event->dev_db);
- }
- if (major(udev_device_get_devnum(dev)) == 0 &&
- streq(udev_device_get_action(dev), "move"))
- udev_device_copy_properties(dev, event->dev_db);
+ if (major(udev_device_get_devnum(dev)) == 0 &&
+ streq(udev_device_get_action(dev), "move"))
+ udev_device_copy_properties(dev, event->dev_db);
+ }
udev_rules_apply_to_event(rules, event,
timeout_usec, timeout_warn_usec,