core: Try to prevent infinite recursive template instantiation

To prevent situations like in #17602 from happening, let's drop
direct recursive template dependencies. These will almost certainly
lead to infinite recursion so let's drop them immediately to avoid
instantiating potentially thousands of irrelevant units.

Example of a template that would lead to infinite recursion which
is caught by this check:

notify@.service:

```
[Unit]
Wants=notify@%n.service
```

7 files changed, 210 insertions, 2 deletions

diff --git a/man/systemd.unit.xml b/man/systemd.unit.xml
index b6e4a2233c..dbf56c26a5 100644
--- a/man/systemd.unit.xml
+++ b/man/systemd.unit.xml
@@ -2256,8 +2256,12 @@ OnFailure=failure-handler@%N.service
     services will have acquired an <varname>OnFailure=</varname> dependency on
     <filename index='false'>failure-handler@%N.service</filename>. The
     template instance units will also have gained the dependency which results
-    in the creation of a recursive dependency chain. We can break the chain by
-    disabling the drop-in for the template instance units via a symlink to
+    in the creation of a recursive dependency chain. systemd will try to detect
+    these recursive dependency chains where a template unit directly and
+    recursively depends on itself and will remove such dependencies
+    automatically if it finds them. If systemd doesn't detect the recursive
+    dependency chain, we can break the chain ourselves by disabling the drop-in
+    for the template instance units via a symlink to
     <filename index='false'>/dev/null</filename>:</para>
 
     <programlisting>
diff --git a/src/basic/unit-name.c b/src/basic/unit-name.c
index 1deead7458..671e30a53f 100644
--- a/src/basic/unit-name.c
+++ b/src/basic/unit-name.c
@@ -8,6 +8,7 @@
 #include "alloc-util.h"
 #include "glob-util.h"
 #include "hexdecoct.h"
+#include "memory-util.h"
 #include "path-util.h"
 #include "special.h"
 #include "string-util.h"
@@ -797,3 +798,26 @@ bool slice_name_is_valid(const char *name) {
 
         return true;
 }
+
+bool unit_name_prefix_equal(const char *a, const char *b) {
+        const char *p, *q;
+
+        assert(a);
+        assert(b);
+
+        if (!unit_name_is_valid(a, UNIT_NAME_ANY) || !unit_name_is_valid(b, UNIT_NAME_ANY))
+                return false;
+
+        p = strchr(a, '@');
+        if (!p)
+                p = strrchr(a, '.');
+
+        q = strchr(b, '@');
+        if (!q)
+                q = strrchr(b, '.');
+
+        assert(p);
+        assert(q);
+
+        return memcmp_nn(a, p - a, b, q - b) == 0;
+}
diff --git a/src/basic/unit-name.h b/src/basic/unit-name.h
index f6af01c9bd..b62b3e034e 100644
--- a/src/basic/unit-name.h
+++ b/src/basic/unit-name.h
@@ -62,3 +62,5 @@ static inline int unit_name_mangle(const char *name, UnitNameMangle flags, char
 int slice_build_parent_slice(const char *slice, char **ret);
 int slice_build_subslice(const char *slice, const char *name, char **subslice);
 bool slice_name_is_valid(const char *name);
+
+bool unit_name_prefix_equal(const char *a, const char *b);
diff --git a/src/core/load-fragment.c b/src/core/load-fragment.c
index 18d9bb377c..b33be5d5ba 100644
--- a/src/core/load-fragment.c
+++ b/src/core/load-fragment.c
@@ -150,6 +150,84 @@ DEFINE_CONFIG_PARSE_ENUM_WITH_DEFAULT(config_parse_numa_policy, mpol, int, -1, "
 DEFINE_CONFIG_PARSE_ENUM(config_parse_status_unit_format, status_unit_format, StatusUnitFormat, "Failed to parse status unit format");
 DEFINE_CONFIG_PARSE_ENUM_FULL(config_parse_socket_timestamping, socket_timestamping_from_string_harder, SocketTimestamping, "Failed to parse timestamping precision");
 
+bool contains_instance_specifier_superset(const char *s) {
+        const char *p, *q;
+        bool percent = false;
+
+        assert(s);
+
+        p = strchr(s, '@');
+        if (!p)
+                return false;
+
+        p++; /* Skip '@' */
+
+        q = strrchr(p, '.');
+        if (!q)
+                q = p + strlen(p);
+
+        /* If the string is just the instance specifier, it's not a superset of the instance. */
+        if (memcmp_nn(p, q - p, "%i", strlen("%i")) == 0)
+                return false;
+
+        /* %i, %n and %N all expand to the instance or a superset of it. */
+        for (; p < q; p++) {
+                if (*p == '%')
+                        percent = !percent;
+                else if (percent) {
+                        if (IN_SET(*p, 'n', 'N', 'i'))
+                                return true;
+                        percent = false;
+                }
+        }
+
+        return false;
+}
+
+/* `name` is the rendered version of `format` via `unit_printf` or similar functions. */
+int unit_is_likely_recursive_template_dependency(Unit *u, const char *name, const char *format) {
+        const char *fragment_path;
+        int r;
+
+        assert(u);
+        assert(name);
+
+        /* If a template unit has a direct dependency on itself that includes the unit instance as part of
+         * the template instance via a unit specifier (%i, %n or %N), this will almost certainly lead to
+         * infinite recursion as systemd will keep instantiating new instances of the template unit.
+         * https://github.com/systemd/systemd/issues/17602 shows a good example of how this can happen in
+         * practice. To guard against this, we check for templates that depend on themselves and have the
+         * instantiated unit instance included as part of the template instance of the dependency via a
+         * specifier.
+         *
+         * For example, if systemd-notify@.service depends on systemd-notify@%n.service, this will result in
+         * infinite recursion.
+         */
+
+        if (!unit_name_is_valid(name, UNIT_NAME_INSTANCE))
+                return false;
+
+        if (!unit_name_prefix_equal(u->id, name))
+                return false;
+
+        if (u->type != unit_name_to_type(name))
+                return false;
+
+        r = unit_file_find_fragment(u->manager->unit_id_map, u->manager->unit_name_map, name, &fragment_path, NULL);
+        if (r < 0)
+                return r;
+
+        /* Fragment paths should also be equal as a custom fragment for a specific template instance
+         * wouldn't necessarily lead to infinite recursion. */
+        if (!path_equal_ptr(u->fragment_path, fragment_path))
+                return false;
+
+        if (!contains_instance_specifier_superset(format))
+                return false;
+
+        return true;
+}
+
 int config_parse_unit_deps(
                 const char *unit,
                 const char *filename,
@@ -189,6 +267,18 @@ int config_parse_unit_deps(
                         continue;
                 }
 
+                r = unit_is_likely_recursive_template_dependency(u, k, word);
+                if (r < 0) {
+                        log_syntax(unit, LOG_WARNING, filename, line, r, "Failed to determine if '%s' is a recursive dependency, ignoring: %m", k);
+                        continue;
+                }
+                if (r > 0) {
+                        log_syntax(unit, LOG_DEBUG, filename, line, 0,
+                                   "Dropping dependency %s=%s that likely leads to infinite recursion.",
+                                   unit_dependency_to_string(d), word);
+                        continue;
+                }
+
                 r = unit_add_dependency_by_name(u, d, k, true, UNIT_DEPENDENCY_FILE);
                 if (r < 0)
                         log_syntax(unit, LOG_WARNING, filename, line, r, "Failed to add dependency on %s, ignoring: %m", k);
diff --git a/src/core/load-fragment.h b/src/core/load-fragment.h
index 96ccb426e6..9ff550410f 100644
--- a/src/core/load-fragment.h
+++ b/src/core/load-fragment.h
@@ -4,6 +4,10 @@
 #include "conf-parser.h"
 #include "unit.h"
 
+/* These functions are declared in the header to make them accessible to unit tests. */
+bool contains_instance_specifier_superset(const char *s);
+int unit_is_likely_recursive_template_dependency(Unit *u, const char *name, const char *format);
+
 /* Config-parsing helpers relevant only for sources under src/core/ */
 int parse_crash_chvt(const char *value, int *data);
 int parse_confirm_spawn(const char *value, char **console);
diff --git a/src/test/test-load-fragment.c b/src/test/test-load-fragment.c
index e0ba99199c..124832cdc9 100644
--- a/src/test/test-load-fragment.c
+++ b/src/test/test-load-fragment.c
@@ -829,6 +829,71 @@ static void test_config_parse_memory_limit(void) {
 
 }
 
+static void test_contains_instance_specifier_superset(void) {
+        assert_se(contains_instance_specifier_superset("foobar@a%i"));
+        assert_se(contains_instance_specifier_superset("foobar@%ia"));
+        assert_se(contains_instance_specifier_superset("foobar@%n"));
+        assert_se(contains_instance_specifier_superset("foobar@%n.service"));
+        assert_se(contains_instance_specifier_superset("foobar@%N"));
+        assert_se(contains_instance_specifier_superset("foobar@%N.service"));
+        assert_se(contains_instance_specifier_superset("foobar@baz.%N.service"));
+        assert_se(contains_instance_specifier_superset("@%N.service"));
+        assert_se(contains_instance_specifier_superset("@%N"));
+        assert_se(contains_instance_specifier_superset("@%a%N"));
+
+        assert_se(!contains_instance_specifier_superset("foobar@%i.service"));
+        assert_se(!contains_instance_specifier_superset("foobar%ia.service"));
+        assert_se(!contains_instance_specifier_superset("foobar@%%n.service"));
+        assert_se(!contains_instance_specifier_superset("foobar@baz.service"));
+        assert_se(!contains_instance_specifier_superset("%N.service"));
+        assert_se(!contains_instance_specifier_superset("%N"));
+        assert_se(!contains_instance_specifier_superset("@%aN"));
+        assert_se(!contains_instance_specifier_superset("@%a%b"));
+}
+
+static void test_unit_is_recursive_template_dependency(void) {
+        _cleanup_(manager_freep) Manager *m = NULL;
+        Unit *u;
+        int r;
+
+        r = manager_new(UNIT_FILE_USER, MANAGER_TEST_RUN_MINIMAL, &m);
+        if (manager_errno_skip_test(r)) {
+                log_notice_errno(r, "Skipping test: manager_new: %m");
+                return;
+        }
+
+        assert_se(r >= 0);
+        assert_se(manager_startup(m, NULL, NULL, NULL) >= 0);
+
+        assert_se(u = unit_new(m, sizeof(Service)));
+        assert_se(unit_add_name(u, "foobar@1.service") == 0);
+        u->fragment_path = strdup("/foobar@.service");
+
+        assert_se(hashmap_put_strdup(&m->unit_id_map, "foobar@foobar@123.service", "/foobar@.service"));
+        assert_se(hashmap_put_strdup(&m->unit_id_map, "foobar@foobar@456.service", "/custom.service"));
+
+        /* Test that %n, %N and any extension of %i specifiers in the instance are detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%N.service") == 1);
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%n.service") == 1);
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@a%i.service") == 1);
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%ia.service") == 1);
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%x%n.service") == 1);
+        /* Test that %i on its own is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%i.service") == 0);
+        /* Test that a specifier other than %i, %n and %N is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@%xn.service") == 0);
+        /* Test that an expanded specifier is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.service", "foobar@foobar@123.service") == 0);
+        /* Test that a dependency with a custom fragment path is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@456.service", "foobar@%n.service") == 0);
+        /* Test that a dependency without a fragment path is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@789.service", "foobar@%n.service") == 0);
+        /* Test that a dependency with a different prefix is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "quux@foobar@123.service", "quux@%n.service") == 0);
+        /* Test that a dependency of a different type is not detected as recursive. */
+        assert_se(unit_is_likely_recursive_template_dependency(u, "foobar@foobar@123.mount", "foobar@%n.mount") == 0);
+}
+
 int main(int argc, char *argv[]) {
         _cleanup_(rm_rf_physical_and_freep) char *runtime_dir = NULL;
         int r;
@@ -850,6 +915,8 @@ int main(int argc, char *argv[]) {
         TEST_REQ_RUNNING_SYSTEMD(test_install_printf());
         test_unit_dump_config_items();
         test_config_parse_memory_limit();
+        test_contains_instance_specifier_superset();
+        test_unit_is_recursive_template_dependency();
 
         return r;
 }
diff --git a/src/test/test-unit-name.c b/src/test/test-unit-name.c
index 0077c4c5e3..665e7b7933 100644
--- a/src/test/test-unit-name.c
+++ b/src/test/test-unit-name.c
@@ -870,6 +870,22 @@ static void test_unit_name_from_dbus_path(void) {
         test_unit_name_from_dbus_path_one("/org/freedesktop/systemd1/unit/wpa_5fsupplicant_2eservice", 0, "wpa_supplicant.service");
 }
 
+static void test_unit_name_prefix_equal(void) {
+        log_info("/* %s */", __func__);
+
+        assert_se(unit_name_prefix_equal("a.service", "a.service"));
+        assert_se(unit_name_prefix_equal("a.service", "a.mount"));
+        assert_se(unit_name_prefix_equal("a@b.service", "a.service"));
+        assert_se(unit_name_prefix_equal("a@b.service", "a@c.service"));
+
+        assert_se(!unit_name_prefix_equal("a.service", "b.service"));
+        assert_se(!unit_name_prefix_equal("a.service", "b.mount"));
+        assert_se(!unit_name_prefix_equal("a@a.service", "b.service"));
+        assert_se(!unit_name_prefix_equal("a@a.service", "b@a.service"));
+        assert_se(!unit_name_prefix_equal("a", "b"));
+        assert_se(!unit_name_prefix_equal("a", "a"));
+}
+
 int main(int argc, char* argv[]) {
         _cleanup_(rm_rf_physical_and_freep) char *runtime_dir = NULL;
         int r, rc = 0;
@@ -902,6 +918,7 @@ int main(int argc, char* argv[]) {
         test_unit_name_path_unescape();
         test_unit_name_to_prefix();
         test_unit_name_from_dbus_path();
+        test_unit_name_prefix_equal();
 
         return rc;
 }