Index: uspace/lib/cpp/include/__bits/thread/packaged_task.hpp
===================================================================
--- uspace/lib/cpp/include/__bits/thread/packaged_task.hpp	(revision 09170ab826b11b2c153e5784c371c8545d3eee94)
+++ uspace/lib/cpp/include/__bits/thread/packaged_task.hpp	(revision 5ea9dd2fb33c37356a027edb7c8ba8a90dae12ad)
@@ -32,4 +32,5 @@
 #include <__bits/exception.hpp>
 #include <__bits/functional/function.hpp>
+#include <__bits/memory/allocator_traits.hpp>
 #include <__bits/thread/future.hpp>
 #include <__bits/thread/future_common.hpp>
@@ -74,7 +75,12 @@
             >
             explicit packaged_task(allocator_arg_t, const Allocator& a, F&& f)
-                : packaged_task{forward<F>(f)}
-            {
-                // TODO: use the allocator
+                : func_{forward<F>(f)}, state_{}
+            {
+                auto rebound = allocator_traits<Allocator>::rebind<
+                    aux::shared_state<R>
+                >{a};
+
+                state_ = rebound.allocate(1);
+                rebound.construct(state_);
             }
 
Index: uspace/lib/cpp/include/__bits/thread/promise.hpp
===================================================================
--- uspace/lib/cpp/include/__bits/thread/promise.hpp	(revision 09170ab826b11b2c153e5784c371c8545d3eee94)
+++ uspace/lib/cpp/include/__bits/thread/promise.hpp	(revision 5ea9dd2fb33c37356a027edb7c8ba8a90dae12ad)
@@ -31,4 +31,5 @@
 
 #include <__bits/exception.hpp>
+#include <__bits/memory/allocator_traits.hpp>
 #include <__bits/thread/future.hpp>
 #include <__bits/thread/shared_state.hpp>
@@ -54,7 +55,12 @@
                 template<class Allocator>
                 promise_base(allocator_arg_t, const Allocator& a)
-                    : promise_base{}
-                {
-                    // TODO: Use the allocator.
+                    : state_{}
+                {
+                    auto rebound = allocator_traits<Allocator>::rebind<
+                        aux::shared_state<R>
+                    >{a};
+
+                    state_ = rebound.allocate(1);
+                    rebound.construct(state_);
                 }
 
@@ -148,9 +154,7 @@
 
             template<class Allocator>
-            promise(allocator_arg_t, const Allocator& a)
-                : aux::promise_base<R>{}
-            {
-                // TODO: Use the allocator.
-            }
+            promise(allocator_arg_t tag, const Allocator& a)
+                : aux::promise_base<R>{tag, a}
+            { /* DUMMY BODY */ }
 
             promise(promise&& rhs) noexcept
@@ -250,9 +254,7 @@
 
             template<class Allocator>
-            promise(allocator_arg_t, const Allocator& a)
-                : aux::promise_base<R*>{}
-            {
-                // TODO: Use the allocator.
-            }
+            promise(allocator_arg_t tag, const Allocator& a)
+                : aux::promise_base<R*>{tag, a}
+            { /* DUMMY BODY */ }
 
             promise(promise&& rhs) noexcept
@@ -323,9 +325,7 @@
 
             template<class Allocator>
-            promise(allocator_arg_t, const Allocator& a)
-                : aux::promise_base<void>{}
-            {
-                // TODO: Use the allocator.
-            }
+            promise(allocator_arg_t tag, const Allocator& a)
+                : aux::promise_base<void>{tag, a}
+            { /* DUMMY BODY */ }
 
             promise(promise&& rhs) noexcept