diff --git a/SOURCES/0278-manager-reduce-complexity-of-unit_gc_sweep-3507.patch b/SOURCES/0278-manager-reduce-complexity-of-unit_gc_sweep-3507.patch
new file mode 100644
index 0000000..1ecb187
--- /dev/null
+++ b/SOURCES/0278-manager-reduce-complexity-of-unit_gc_sweep-3507.patch
@@ -0,0 +1,62 @@
+From 8994877c8c0d2cab6e5c7e8cf98df5ff580d87a8 Mon Sep 17 00:00:00 2001
+From: =?UTF-8?q?Luk=C3=A1=C5=A1=20Nykr=C3=BDn?= <lnykryn@redhat.com>
+Date: Tue, 14 Jun 2016 14:20:56 +0200
+Subject: [PATCH] manager: reduce complexity of unit_gc_sweep (#3507)
+
+When unit is marked as UNSURE, we are trying to find if it state was
+changed over and over again. So lets not go through the UNSURE states
+again. Also when we find a GOOD unit lets propagate the GOOD state to
+all units that this unit reference.
+
+This is a problem on machines with a lot of initscripts with different
+starting priority, since those units will reference each other and the
+original algorithm might get to n! complexity.
+
+Thanks HATAYAMA Daisuke for the expand_good_state code.
+Cherry-picked from: 4892084f096c19da0e83f28f250ca187b58c22b2
+Resolves: #1344556
+---
+ src/core/manager.c | 16 +++++++++++++++-
+ 1 file changed, 15 insertions(+), 1 deletion(-)
+
+diff --git a/src/core/manager.c b/src/core/manager.c
+index 7483a96..45ca540 100644
+--- a/src/core/manager.c
++++ b/src/core/manager.c
+@@ -765,6 +765,19 @@ enum {
+         _GC_OFFSET_MAX
+ };
+ 
++static void unit_gc_mark_good(Unit *u, unsigned gc_marker)
++{
++        Iterator i;
++        Unit *other;
++
++        u->gc_marker = gc_marker + GC_OFFSET_GOOD;
++
++        /* Recursively mark referenced units as GOOD as well */
++        SET_FOREACH(other, u->dependencies[UNIT_REFERENCES], i)
++                if (other->gc_marker == gc_marker + GC_OFFSET_UNSURE)
++                        unit_gc_mark_good(other, gc_marker);
++}
++
+ static void unit_gc_sweep(Unit *u, unsigned gc_marker) {
+         Iterator i;
+         Unit *other;
+@@ -774,6 +787,7 @@ static void unit_gc_sweep(Unit *u, unsigned gc_marker) {
+ 
+         if (u->gc_marker == gc_marker + GC_OFFSET_GOOD ||
+             u->gc_marker == gc_marker + GC_OFFSET_BAD ||
++            u->gc_marker == gc_marker + GC_OFFSET_UNSURE ||
+             u->gc_marker == gc_marker + GC_OFFSET_IN_PATH)
+                 return;
+ 
+@@ -814,7 +828,7 @@ bad:
+         return;
+ 
+ good:
+-        u->gc_marker = gc_marker + GC_OFFSET_GOOD;
++        unit_gc_mark_good(u, gc_marker);
+ }
+ 
+ static unsigned manager_dispatch_gc_queue(Manager *m) {
diff --git a/SPECS/systemd.spec b/SPECS/systemd.spec
index 8f9e64f..2942307 100644
--- a/SPECS/systemd.spec
+++ b/SPECS/systemd.spec
@@ -7,7 +7,7 @@
 Name:           systemd
 Url:            http://www.freedesktop.org/wiki/Software/systemd
 Version:        219
-Release:        19%{?dist}.11
+Release:        19%{?dist}.12
 # For a breakdown of the licensing, see README
 License:        LGPLv2+ and MIT and GPLv2+
 Summary:        A System and Service Manager
@@ -305,6 +305,7 @@ Patch0274: 0274-Revert-journald-turn-ForwardToSyslog-off-by-default.patch
 Patch0275: 0275-journal-fix-error-handling-when-compressing-journal-.patch
 Patch0276: 0276-journal-irrelevant-coding-style-fixes.patch
 Patch0277: 0277-fstab-generator-cescape-device-name-in-root-fsck-ser.patch
+Patch0278: 0278-manager-reduce-complexity-of-unit_gc_sweep-3507.patch
 
 
 %global num_patches %{lua: c=0; for i,p in ipairs(patches) do c=c+1; end; print(c);}
@@ -1265,6 +1266,9 @@ getent passwd systemd-resolve >/dev/null 2>&1 || useradd -r -l -g systemd-resolv
 %{_mandir}/man8/systemd-resolved.*
 
 %changelog
+* Tue Jun 14 2016 Lukas Nykryn <lnykryn@redhat.com> - 219-19.12
+- manager: reduce complexity of unit_gc_sweep (#3507) (#1344556)
+
 * Thu May 26 2016 Lukas Nykryn <lnykryn@redhat.com> - 219-19.11
 - fstab-generator: cescape device name in root-fsck service (#1306126)