pw_sync_freertos: Add optimized ThreadNotification backend

Adds an optimized thread notification backend using native
FreeRTOS Task Notifications, just like Stream and Message Buffers.

Also fills out the missing pw_sync_freertos documentation.

Change-Id: I44899875a7f61fa0be30d50ac06b9016dde6ecf1
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/67024
Commit-Queue: Ewout van Bekkum <ewout@google.com>
Pigweed-Auto-Submit: Ewout van Bekkum <ewout@google.com>
Reviewed-by: Keir Mierle <keir@google.com>

12 files changed, 755 insertions, 13 deletions

diff --git a/pw_sync_freertos/BUILD.bazel b/pw_sync_freertos/BUILD.bazel
index 5faf55369..aca4016da 100644
--- a/pw_sync_freertos/BUILD.bazel
+++ b/pw_sync_freertos/BUILD.bazel
@@ -37,8 +37,9 @@ pw_cc_library(
         "//pw_build/constraints/rtos:freertos",
     ],
     deps = [
-        # TODO: This should depend on FreeRTOS but our third parties currently
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties currently
         # do not have Bazel support.
+        "//pw_assert",
         "//pw_chrono:system_clock",
         "//pw_chrono_freertos:system_clock_headers",
     ],
@@ -54,6 +55,7 @@ pw_cc_library(
     ],
     deps = [
         ":binary_semaphore_headers",
+        "//pw_assert",
         "//pw_interrupt:context",
         "//pw_sync:binary_semaphore_facade",
     ],
@@ -75,8 +77,10 @@ pw_cc_library(
         "//pw_build/constraints/rtos:freertos",
     ],
     deps = [
-        # TODO: This should depend on FreeRTOS but our third parties currently
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties currently
         # do not have Bazel support.
+        "//pw_assert",
+        "//pw_sync:counting_semaphore_facade",
         "//pw_chrono:system_clock",
         "//pw_chrono_freertos:system_clock_headers",
     ],
@@ -92,6 +96,7 @@ pw_cc_library(
     ],
     deps = [
         ":counting_semaphore_headers",
+        "//pw_assert",
         "//pw_interrupt:context",
         "//pw_sync:counting_semaphore_facade",
     ],
@@ -113,9 +118,9 @@ pw_cc_library(
         "//pw_build/constraints/rtos:freertos",
     ],
     deps = [
-        # TODO: This should depend on FreeRTOS but our third parties currently
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties currently
         # do not have Bazel support.
-        "//pw_sync:mutex_facade",
+        "//pw_assert",
     ],
 )
 
@@ -131,6 +136,83 @@ pw_cc_library(
 )
 
 pw_cc_library(
+    name = "thread_notification_headers",
+    hdrs = [
+        "public/pw_sync_freertos/config.h",
+        "public/pw_sync_freertos/thread_notification_inline.h",
+        "public/pw_sync_freertos/thread_notification_native.h",
+        "public_overrides/thread_notification/pw_sync_backend/thread_notification_inline.h",
+        "public_overrides/thread_notification/pw_sync_backend/thread_notification_native.h",
+    ],
+    includes = [
+        "public",
+        "public_overrides/thread_notification",
+    ],
+    target_compatible_with = [
+        "//pw_build/constraints/rtos:freertos",
+    ],
+    deps = [
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties
+        # currently do not have Bazel support.
+        "//pw_interrupt:context",
+    ],
+)
+
+pw_cc_library(
+    name = "thread_notification",
+    srcs = [
+        "thread_notification.cc",
+    ],
+    target_compatible_with = [
+        "//pw_build/constraints/rtos:freertos",
+    ],
+    deps = [
+        ":thread_notification_headers",
+        "//pw_assert",
+        "//pw_interrupt:context",
+        "//pw_sync:thread_notification_facade",
+    ],
+)
+
+pw_cc_library(
+    name = "timed_thread_notification_headers",
+    hdrs = [
+        "public/pw_sync_freertos/timed_thread_notification_inline.h",
+        "public_overrides/timed_thread_notification/pw_sync_backend/timed_thread_notification_inline.h",
+    ],
+    includes = [
+        "public",
+        "public_overrides/timed_thread_notification",
+    ],
+    target_compatible_with = [
+        "//pw_build/constraints/rtos:freertos",
+    ],
+    deps = [
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties
+        # currently do not have Bazel support.
+        "//pw_chrono:system_clock",
+        "//pw_sync:timed_thread_notification_facade",
+    ],
+)
+
+pw_cc_library(
+    name = "timed_thread_notification",
+    srcs = [
+        "timed_thread_notification.cc",
+    ],
+    target_compatible_with = [
+        "//pw_build/constraints/rtos:freertos",
+    ],
+    deps = [
+        ":timed_thread_notification_headers",
+        "//pw_assert",
+        "//pw_chrono_freertos:system_clock_headers",
+        "//pw_interrupt:context",
+        "//pw_sync:timed_thread_notification_facade",
+    ],
+)
+
+pw_cc_library(
     name = "timed_mutex_headers",
     hdrs = [
         "public/pw_sync_freertos/timed_mutex_inline.h",
@@ -144,10 +226,9 @@ pw_cc_library(
         "//pw_build/constraints/rtos:freertos",
     ],
     deps = [
-        # TODO: This should depend on FreeRTOS but our third parties currently
-        # do not have Bazel support.
+        # TODO(pwbug/317): This should depend on FreeRTOS but our third parties
+        # currently do not have Bazel support.
         "//pw_chrono:system_clock",
-        "//pw_chrono_freertos:system_clock_headers",
         "//pw_sync:timed_mutex_facade",
     ],
 )
@@ -162,6 +243,8 @@ pw_cc_library(
     ],
     deps = [
         ":timed_mutex_headers",
+        "//pw_assert",
+        "//pw_chrono_freertos:system_clock_headers",
         "//pw_interrupt:context",
         "//pw_sync:timed_mutex_facade",
     ],
@@ -182,8 +265,8 @@ pw_cc_library(
     target_compatible_with = [
         "//pw_build/constraints/rtos:freertos",
     ],
-    # TODO: This should depend on FreeRTOS but our third parties currently
-    # do not have Bazel support.
+    # TODO(pwbug/317): This should depend on FreeRTOS but our third parties
+    # currently do not have Bazel support.
 )
 
 pw_cc_library(
@@ -196,6 +279,7 @@ pw_cc_library(
     ],
     deps = [
         ":interrupt_spin_lock_headers",
+        "//pw_assert",
         "//pw_interrupt:context",
         "//pw_sync:interrupt_spin_lock_facade",
     ],
diff --git a/pw_sync_freertos/BUILD.gn b/pw_sync_freertos/BUILD.gn
index 425ef4a16..82665f113 100644
--- a/pw_sync_freertos/BUILD.gn
+++ b/pw_sync_freertos/BUILD.gn
@@ -14,10 +14,18 @@
 
 import("//build_overrides/pigweed.gni")
 
+import("$dir_pw_build/module_config.gni")
 import("$dir_pw_build/target_types.gni")
 import("$dir_pw_chrono/backend.gni")
 import("$dir_pw_docgen/docs.gni")
 
+declare_args() {
+  # The build target that overrides the default configuration options for this
+  # module. This should point to a source set that provides defines through a
+  # public config (which may -include a file or add defines directly).
+  pw_sync_freertos_CONFIG = pw_build_DEFAULT_MODULE_CONFIG
+}
+
 config("public_include_path") {
   include_dirs = [ "public" ]
   visibility = [ ":*" ]
@@ -28,6 +36,15 @@ config("backend_config") {
   visibility = [ ":*" ]
 }
 
+pw_source_set("config") {
+  public = [ "public/pw_sync_freertos/config.h" ]
+  public_configs = [ ":public_include_path" ]
+  public_deps = [
+    "$dir_pw_third_party/freertos",
+    pw_sync_freertos_CONFIG,
+  ]
+}
+
 # This target provides the backend for pw::sync::BinarySemaphore.
 pw_source_set("binary_semaphore") {
   public_configs = [
@@ -104,6 +121,72 @@ pw_source_set("mutex") {
   ]
 }
 
+config("public_overrides_thread_notification_include_path") {
+  include_dirs = [ "public_overrides/thread_notification" ]
+  visibility = [ ":thread_notification" ]
+}
+
+# This target provides the backend for pw::sync::ThreadNotification based on
+# task notifications.
+pw_source_set("thread_notification") {
+  public_configs = [
+    ":public_include_path",
+    ":public_overrides_thread_notification_include_path",
+  ]
+  public = [
+    "public/pw_sync_freertos/thread_notification_inline.h",
+    "public/pw_sync_freertos/thread_notification_native.h",
+    "public_overrides/thread_notification/pw_sync_backend/thread_notification_inline.h",
+    "public_overrides/thread_notification/pw_sync_backend/thread_notification_native.h",
+  ]
+  public_deps = [
+    "$dir_pw_interrupt:context",
+    "$dir_pw_sync:thread_notification.facade",
+    "$dir_pw_third_party/freertos",
+  ]
+  sources = [ "thread_notification.cc" ]
+  deps = [
+    ":config",
+    dir_pw_assert,
+  ]
+}
+
+config("public_overrides_timed_thread_notification_include_path") {
+  include_dirs = [ "public_overrides/timed_thread_notification" ]
+  visibility = [ ":timed_thread_notification" ]
+}
+
+# This target provides the backend for pw::sync::TimedThreadNotification based
+# on task notifications.
+pw_source_set("timed_thread_notification") {
+  public_configs = [
+    ":public_include_path",
+    ":public_overrides_timed_thread_notification_include_path",
+  ]
+  public = [
+    "public/pw_sync_freertos/timed_thread_notification_inline.h",
+    "public_overrides/timed_thread_notification/pw_sync_backend/timed_thread_notification_inline.h",
+  ]
+  public_deps = [
+    ":thread_notification",
+    "$dir_pw_chrono:system_clock",
+    "$dir_pw_sync:timed_thread_notification.facade",
+  ]
+  sources = [ "timed_thread_notification.cc" ]
+  deps = [
+    ":config",
+    "$dir_pw_assert",
+    "$dir_pw_chrono_freertos:system_clock",
+    "$dir_pw_interrupt:context",
+    "$dir_pw_third_party/freertos",
+  ]
+  assert(pw_chrono_SYSTEM_CLOCK_BACKEND == "" ||
+             pw_chrono_SYSTEM_CLOCK_BACKEND ==
+                 "$dir_pw_chrono_freertos:system_clock",
+         "The FreeRTOS pw::sync::Mutex backend only works with the FreeRTOS " +
+             "pw::chrono::SystemClock backend.")
+}
+
 # This target provides the backend for pw::sync::TimedMutex.
 pw_source_set("timed_mutex") {
   public_configs = [
diff --git a/pw_sync_freertos/docs.rst b/pw_sync_freertos/docs.rst
index 0053f02f9..a4fd5917e 100644
--- a/pw_sync_freertos/docs.rst
+++ b/pw_sync_freertos/docs.rst
@@ -1,8 +1,150 @@
 .. _module-pw_sync_freertos:
 
-----------------
+================
 pw_sync_freertos
-----------------
-This is a set of backends for pw_sync based on FreeRTOS. It is not ready for
-use, and is under construction.
+================
+This is a set of backends for pw_sync based on FreeRTOS.
+
+--------------------------------
+Critical Section Lock Primitives
+--------------------------------
+
+Mutex & TimedMutex
+==================
+The FreeRTOS backend for the Mutex and TimedMutex use ``StaticSemaphore_t`` as
+the underlying type. It is created using ``xSemaphoreCreateMutexStatic`` as part
+of the constructors and cleaned up using ``vSemaphoreDelete`` in the
+destructors.
+
+.. Note::
+  Static allocation support is required in your FreeRTOS configuration, i.e.
+  ``configSUPPORT_STATIC_ALLOCATION == 1``.
+
+InterruptSpinLock
+=================
+The FreeRTOS backend for InterruptSpinLock is backed by ``UBaseType_t`` and a
+``bool`` which permits these objects to stash the saved interrupt mask and to
+detect accidental recursive locking.
+
+This object uses ``taskENTER_CRITICAL_FROM_ISR`` and
+``taskEXIT_CRITICAL_FROM_ISR`` from interrupt contexts and
+``taskENTER_CRITICAL`` and ``taskEXIT_CRITICAL`` from other contexts.
+
+--------------------
+Signaling Primitives
+--------------------
+
+ThreadNotification & TimedThreadNotification
+============================================
+An optimized FreeRTOS backend for the ThreadNotification and
+TimedThreadNotification is provided using Task Notifications. It is backed by a
+``TaskHandle_t`` and a ``bool`` which permits these objects to track the
+notification value outside of the task's TCB (AKA FreeRTOS Task Notification
+State and Value).
+
+.. Warning::
+  By default this backend uses the task notification at index 0, just like
+  FreeRTOS Stream and Message Buffers. If you want to maintain the state of a
+  task notification across blocking acquiring calls to ThreadNotifications, then
+  you must do one of the following:
+
+  1. Adjust ``PW_SYNC_FREERTOS_CONFIG_THREAD_NOTIFICATION_INDEX`` to an index
+     which does not collide with existing incompatible use.
+  2. Migrate your existing use of task notifications away from index 0.
+  3. Do not use this optimized backend and instead use the binary semaphore
+     backends for ThreadNotifications
+     (``pw_sync:binary_semaphore_thread_notification_backend``).
+
+  You are using any of the following Task Notification APIs, it means you are
+  using notification indices:
+
+  - ``xTaskNotify`` / ``xTaskNotifyIndexed``
+  - ``xTaskNotifyFromISR`` / ``xTaskNotifyIndexedFromISR``
+  - ``xTaskNotifyGive`` / ``xTaskNotifyGiveIndexed``
+  - ``xTaskNotifyGiveFromISR`` / ``xTaskNotifyGiveIndexedFromISR``
+  - ``xTaskNotifyAndQuery`` / ``xTaskNotifyAndQueryIndexed``
+  - ``xTaskNotifyAndQueryFromISR`` / ``xTaskNotifyAndQueryIndexedFromISR``
+  - ``ulTaskNotifyTake`` / ``ulTaskNotifyTakeIndexed``
+  - ``xTaskNotifyWait`` / ``xTaskNotifyWaitIndexed``
+  - ``xTaskNotifyStateClear`` / ``xTaskNotifyStateClearIndexed``
+  - ``ulTaskNotifyValueClear`` / ``ulTaskNotifyValueClearIndexed``
+
+  APIs without ``Indexed`` in the name use index 0 implicitly.
+
+  Prior to FreeRTOS V10.4.0 each task had a single "notification index", and all
+  task notification API functions operated on that implicit index of 0.
+
+This backend is compatible with sharing the notification index
+with native FreeRTOS
+`Stream and Message Buffers <https://www.freertos.org/RTOS-task-notifications.html>`_
+at index 0.
+
+Just like FreeRTOS Stream and Message Buffers, this backend uses the task
+notification index only within callsites where the task must block until a
+notification is received or a timeout occurs. The notification index's state is
+always cleaned up before returning. The notification index is never used when
+the acquiring task is not going to block.
+
+.. Note::
+  Task notification support is required in your FreeRTOS configuration, i.e.
+  ``configUSE_TASK_NOTIFICATIONS == 1``.
+
+Design Notes
+------------
+You may ask, why are Task Notifications used at all given the risk associated
+with global notification index allocations? It turns out there's no other
+lightweight mechanism to unblock a task in FreeRTOS.
+
+Task suspension (i.e. ``vTaskSuspend``, ``vTaskResume``, &
+``vTaskResumeFromISR``) seems like a good fit, however ``xTaskResumeAll`` does
+not participate in reference counting and will wake up all suspended tasks
+whether you want it to or not.
+
+Lastly, there's also ``xTaskAbortDelay`` but there is no interrupt safe
+equivalent of this API. Note that it uses ``vTaskSuspendAll`` internally for
+the critical section which is not interrupt safe. If in the future an interrupt
+safe version of this API is offerred, then this would be a great alternative!
+
+Lastly, we want to briefly explain how Task Notifications actually work in
+FreeRTOS to show why you cannot directly share notification indeces even if the
+bits used in the ``ulNotifiedValue`` are unique. This is a very common source of
+bugs when using FreeRTOS and partially why Pigweed does not recommend using the
+native Task Notification APIs directly.
+
+FreeRTOS Task Notifications use a task's TCB's ``ucNotifyState`` to capture the
+notification state even when the task is not blocked. This state transitions
+``taskNOT_WAITING_NOTIFICATION`` to ``task_NOTIFICATION_RECEIVED`` if the task
+ever notified. This notification state is used to determine whether the next
+task notification wait call should block, irrespective of the notification
+value.
+
+In order to enable this optimized backend, native task notifications are only
+used when the task needs to block. If a timeout occurs the task unregisters for
+notifications and clears the notification state before returning. This exact
+mechanism is used by FreeRTOS internally for their Stream and Message Buffer
+implementations.
+
+BinarySemaphore
+===============
+The FreeRTOS backend for the BinarySemaphore uses ``StaticSemaphore_t`` as the
+underlying type. It is created using ``xSemaphoreCreateBinaryStatic`` as part
+of the constructor and cleaned up using ``vSemaphoreDelete`` in the destructor.
+
+.. Note::
+  Static allocation support is required in your FreeRTOS configuration, i.e.
+  ``configSUPPORT_STATIC_ALLOCATION == 1``.
+
+CountingSemaphore
+=================
+The FreeRTOS backend for the CountingSemaphore uses ``StaticSemaphore_t`` as the
+underlying type. It is created using ``xSemaphoreCreateCountingStatic`` as part
+of the constructor and cleaned up using ``vSemaphoreDelete`` in the destructor.
+
+.. Note::
+  Counting semaphore support is required in your FreeRTOS configuration, i.e.
+  ``configUSE_COUNTING_SEMAPHORES == 1``.
+.. Note::
+  Static allocation support is required in your FreeRTOS configuration, i.e.
+  ``configSUPPORT_STATIC_ALLOCATION == 1``.
+
 
diff --git a/pw_sync_freertos/public/pw_sync_freertos/config.h b/pw_sync_freertos/public/pw_sync_freertos/config.h
new file mode 100644
index 000000000..6bd34e37e
--- /dev/null
+++ b/pw_sync_freertos/public/pw_sync_freertos/config.h
@@ -0,0 +1,51 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+// Configuration macros for the tokenizer module.
+#pragma once
+
+#include "FreeRTOS.h"
+
+// Just like FreeRTOS Stream and Message Buffers, by default the optimized
+// pw::sync::ThreadNotification uses the task notification at array index 0.
+// This optimized backend is compatible with sharing the notification with
+// Stream and Message Buffers and any other users which ONLY notify the task
+// while the task is blocked and the task consumes the notification state
+// before returning.
+//
+// The task's TCB uses a ucNotifyState which captures notification state even
+// when the task is not waiting (taskNOT_WAITING_NOTIFICATION vs
+// task_NOTIFICATION_RECEIVED). This notification state is used to determine
+// whether the next task notification wait call should block, irrespective of
+// the notification value. This means that one must ensure not just that
+// the bits in the ulNotifiedValue are mutually exclusive, but also that the
+// notification state is mutually exclusive!
+#ifndef PW_SYNC_FREERTOS_CONFIG_THREAD_NOTIFICATION_INDEX
+#define PW_SYNC_FREERTOS_CONFIG_THREAD_NOTIFICATION_INDEX 0
+#endif  // PW_SYNC_FREERTOS_CONFIG_THREAD_NOTIFICATION_INDEX
+
+namespace pw::sync::freertos::config {
+
+inline constexpr UBaseType_t kThreadNotificationIndex =
+    PW_SYNC_FREERTOS_CONFIG_THREAD_NOTIFICATION_INDEX;
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+// Ensure the index fits within the FreeRTOS configuration of the task
+// notification array.
+static_assert(kThreadNotificationIndex < configTASK_NOTIFICATION_ARRAY_ENTRIES);
+#else   // !defined(configTASK_NOTIFICATION_ARRAY_ENTRIES)
+// This version of FreeRTOS does not support multiple task notifications, ensure
+// the index is the default of 0.
+static_assert(kThreadNotificationIndex == 0);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+
+}  // namespace pw::sync::freertos::config
diff --git a/pw_sync_freertos/public/pw_sync_freertos/thread_notification_inline.h b/pw_sync_freertos/public/pw_sync_freertos/thread_notification_inline.h
new file mode 100644
index 000000000..2f4fad89d
--- /dev/null
+++ b/pw_sync_freertos/public/pw_sync_freertos/thread_notification_inline.h
@@ -0,0 +1,52 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "FreeRTOS.h"
+#include "pw_assert/assert.h"
+#include "pw_interrupt/context.h"
+#include "pw_sync/thread_notification.h"
+#include "task.h"
+
+namespace pw::sync {
+namespace backend {
+
+static_assert(configUSE_TASK_NOTIFICATIONS != 0,
+              "Task Notifications aren't enabled.");
+
+}  // namespace backend
+
+inline ThreadNotification::ThreadNotification()
+    : native_type_{
+          .blocked_thread = nullptr,
+          .notified = false,
+      } {}
+
+inline ThreadNotification::~ThreadNotification() = default;
+
+inline bool ThreadNotification::try_acquire() {
+  PW_DASSERT(!interrupt::InInterruptContext());
+  taskENTER_CRITICAL();
+  const bool notified = native_type_.notified;
+  native_type_.notified = false;
+  taskEXIT_CRITICAL();
+  return notified;
+}
+
+inline ThreadNotification::native_handle_type
+ThreadNotification::native_handle() {
+  return native_type_;
+}
+
+}  // namespace pw::sync
diff --git a/pw_sync_freertos/public/pw_sync_freertos/thread_notification_native.h b/pw_sync_freertos/public/pw_sync_freertos/thread_notification_native.h
new file mode 100644
index 000000000..9cc0a6a52
--- /dev/null
+++ b/pw_sync_freertos/public/pw_sync_freertos/thread_notification_native.h
@@ -0,0 +1,27 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "FreeRTOS.h"
+#include "task.h"
+
+namespace pw::sync::backend {
+
+struct NativeThreadNotification {
+  TaskHandle_t blocked_thread;
+  bool notified;
+};
+using NativeThreadNotificationHandle = NativeThreadNotification&;
+
+}  // namespace pw::sync::backend
diff --git a/pw_sync_freertos/public/pw_sync_freertos/timed_thread_notification_inline.h b/pw_sync_freertos/public/pw_sync_freertos/timed_thread_notification_inline.h
new file mode 100644
index 000000000..671fe4d41
--- /dev/null
+++ b/pw_sync_freertos/public/pw_sync_freertos/timed_thread_notification_inline.h
@@ -0,0 +1,28 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "pw_chrono/system_clock.h"
+#include "pw_sync/timed_thread_notification.h"
+
+namespace pw::sync {
+
+inline bool TimedThreadNotification::try_acquire_until(
+    chrono::SystemClock::time_point deadline) {
+  // Note that if this deadline is in the future, it will get rounded up by
+  // one whole tick due to how try_lock_for is implemented.
+  return try_acquire_for(deadline - chrono::SystemClock::now());
+}
+
+}  // namespace pw::sync
diff --git a/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_inline.h b/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_inline.h
new file mode 100644
index 000000000..fdd508943
--- /dev/null
+++ b/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_inline.h
@@ -0,0 +1,16 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "pw_sync_freertos/thread_notification_inline.h"
diff --git a/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_native.h b/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_native.h
new file mode 100644
index 000000000..2798150bf
--- /dev/null
+++ b/pw_sync_freertos/public_overrides/thread_notification/pw_sync_backend/thread_notification_native.h
@@ -0,0 +1,16 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "pw_sync_freertos/thread_notification_native.h"
diff --git a/pw_sync_freertos/public_overrides/timed_thread_notification/pw_sync_backend/timed_thread_notification_inline.h b/pw_sync_freertos/public_overrides/timed_thread_notification/pw_sync_backend/timed_thread_notification_inline.h
new file mode 100644
index 000000000..d2c388298
--- /dev/null
+++ b/pw_sync_freertos/public_overrides/timed_thread_notification/pw_sync_backend/timed_thread_notification_inline.h
@@ -0,0 +1,16 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include "pw_sync_freertos/timed_thread_notification_inline.h"
diff --git a/pw_sync_freertos/thread_notification.cc b/pw_sync_freertos/thread_notification.cc
new file mode 100644
index 000000000..bb1bc8b38
--- /dev/null
+++ b/pw_sync_freertos/thread_notification.cc
@@ -0,0 +1,119 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+#include "pw_sync/thread_notification.h"
+
+#include "FreeRTOS.h"
+#include "pw_assert/check.h"
+#include "pw_interrupt/context.h"
+#include "pw_sync_freertos/config.h"
+#include "task.h"
+
+namespace pw::sync {
+namespace {
+
+BaseType_t WaitForNotification(TickType_t xTicksToWait) {
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+  return xTaskNotifyWaitIndexed(
+      pw::sync::freertos::config::kThreadNotificationIndex,
+      0,        // Clear no bits on entry.
+      0,        // Clear no bits on exit.
+      nullptr,  // Don't care about the notification value.
+      xTicksToWait);
+#else   // !configTASK_NOTIFICATION_ARRAY_ENTRIES
+  return xTaskNotifyWait(0,        // Clear no bits on entry.
+                         0,        // Clear no bits on exit.
+                         nullptr,  // Don't care about the notification value.
+                         xTicksToWait);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+}
+
+}  // namespace
+
+void ThreadNotification::acquire() {
+  PW_DCHECK(!interrupt::InInterruptContext());
+  PW_DCHECK(native_type_.blocked_thread == nullptr);
+
+  taskENTER_CRITICAL();
+  if (native_type_.notified) {
+    native_type_.notified = false;
+    taskEXIT_CRITICAL();
+    return;
+  }
+  // Not notified yet, set the task handle for a one-time notification.
+  native_type_.blocked_thread = xTaskGetCurrentTaskHandle();
+  taskEXIT_CRITICAL();
+
+#if INCLUDE_vTaskSuspend == 1  // This means portMAX_DELAY is indefinite.
+  const BaseType_t result = WaitForNotification(portMAX_DELAY);
+  PW_DCHECK_UINT_EQ(result, pdTRUE);
+#else   // INCLUDE_vTaskSuspend != 1
+  while (WaitForNotification(portMAX_DELAY) == pdFALSE) {
+  }
+#endif  // INCLUDE_vTaskSuspend
+
+  taskENTER_CRITICAL();
+  // The task handle was cleared by the notifier.
+  // Note that this may hide another notification, however this is considered
+  // a form of notification saturation just like as if this happened before
+  // acquire() was invoked.
+  native_type_.notified = false;
+  taskEXIT_CRITICAL();
+}
+
+void ThreadNotification::release() {
+  if (!interrupt::InInterruptContext()) {  // Task context
+    taskENTER_CRITICAL();
+    if (native_type_.blocked_thread != nullptr) {
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+      xTaskNotifyIndexed(native_type_.blocked_thread,
+                         pw::sync::freertos::config::kThreadNotificationIndex,
+                         0u,
+                         eNoAction);
+#else   // !configTASK_NOTIFICATION_ARRAY_ENTRIES
+      xTaskNotify(native_type_.blocked_thread, 0u, eNoAction);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+
+      native_type_.blocked_thread = nullptr;
+    }
+    native_type_.notified = true;
+    taskEXIT_CRITICAL();
+    return;
+  }
+
+  // Interrupt context
+  const UBaseType_t saved_interrupt_mask = taskENTER_CRITICAL_FROM_ISR();
+  if (native_type_.blocked_thread != nullptr) {
+    BaseType_t woke_higher_task = pdFALSE;
+
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+    xTaskNotifyIndexedFromISR(
+        native_type_.blocked_thread,
+        pw::sync::freertos::config::kThreadNotificationIndex,
+        0u,
+        eNoAction,
+        &woke_higher_task);
+#else   // !configTASK_NOTIFICATION_ARRAY_ENTRIES
+    xTaskNotifyFromISR(
+        native_type_.blocked_thread, 0u, eNoAction, &woke_higher_task);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+
+    native_type_.blocked_thread = nullptr;
+    portYIELD_FROM_ISR(woke_higher_task);
+  }
+  native_type_.notified = true;
+  taskEXIT_CRITICAL_FROM_ISR(saved_interrupt_mask);
+}
+
+}  // namespace pw::sync
diff --git a/pw_sync_freertos/timed_thread_notification.cc b/pw_sync_freertos/timed_thread_notification.cc
new file mode 100644
index 000000000..5af1a0b5c
--- /dev/null
+++ b/pw_sync_freertos/timed_thread_notification.cc
@@ -0,0 +1,108 @@
+// Copyright 2021 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+#include "pw_sync/timed_thread_notification.h"
+
+#include "FreeRTOS.h"
+#include "pw_assert/check.h"
+#include "pw_chrono/system_clock.h"
+#include "pw_chrono_freertos/system_clock_constants.h"
+#include "pw_interrupt/context.h"
+#include "pw_sync_freertos/config.h"
+#include "task.h"
+
+using pw::chrono::SystemClock;
+
+namespace pw::sync {
+namespace {
+
+BaseType_t WaitForNotification(TickType_t xTicksToWait) {
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+  return xTaskNotifyWaitIndexed(
+      pw::sync::freertos::config::kThreadNotificationIndex,
+      0,        // Clear no bits on entry.
+      0,        // Clear no bits on exit.
+      nullptr,  // Don't care about the notification value.
+      xTicksToWait);
+#else   // !configTASK_NOTIFICATION_ARRAY_ENTRIES
+  return xTaskNotifyWait(0,        // Clear no bits on entry.
+                         0,        // Clear no bits on exit.
+                         nullptr,  // Don't care about the notification value.
+                         xTicksToWait);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+}
+
+}  // namespace
+
+bool TimedThreadNotification::try_acquire_for(SystemClock::duration timeout) {
+  PW_DCHECK(!interrupt::InInterruptContext());
+  PW_DCHECK(native_handle().blocked_thread == nullptr);
+
+  taskENTER_CRITICAL();
+  if (native_handle().notified) {
+    native_handle().notified = false;
+    taskEXIT_CRITICAL();
+    return true;
+  }
+  // Not notified yet, set the task handle for a one-time notification.
+  native_handle().blocked_thread = xTaskGetCurrentTaskHandle();
+  taskEXIT_CRITICAL();
+
+  const bool notified = [&]() {
+    // On a tick based kernel we cannot tell how far along we are on the current
+    // tick, ergo we add one whole tick to the final duration.
+    constexpr SystemClock::duration kMaxTimeoutMinusOne =
+        pw::chrono::freertos::kMaxTimeout - SystemClock::duration(1);
+    // In case the timeout is too long for us to express through the native
+    // FreeRTOS API, we repeatedly wait with shorter durations.
+    while (timeout > kMaxTimeoutMinusOne) {
+      if (WaitForNotification(
+              static_cast<TickType_t>(kMaxTimeoutMinusOne.count())) == pdTRUE) {
+        return true;
+      }
+      timeout -= kMaxTimeoutMinusOne;
+    }
+
+    return WaitForNotification(static_cast<TickType_t>(timeout.count())) ==
+           pdTRUE;
+  }();
+
+  taskENTER_CRITICAL();
+  if (notified) {
+    // Note that this may hide another notification, however this is considered
+    // a form of notification saturation just like as if this happened before
+    // acquire() was invoked.
+    native_handle().notified = false;
+    // The task handle and notification state were cleared by the notifier.
+  } else {
+    // Note that we do NOT want to clear the notified value so the next call
+    // can detect the notification which came after we timed out but before this
+    // critical section.
+    //
+    // However, we do need to clear the task handle if we weren't notified and
+    // the notification state in case we were notified to ensure we can block
+    // in the future.
+    native_handle().blocked_thread = nullptr;
+#ifdef configTASK_NOTIFICATION_ARRAY_ENTRIES
+    xTaskNotifyStateClearIndexed(
+        pw::sync::freertos::config::kThreadNotificationIndex, nullptr);
+#else   // !configTASK_NOTIFICATION_ARRAY_ENTRIES
+    xTaskNotifyStateClear(nullptr);
+#endif  // configTASK_NOTIFICATION_ARRAY_ENTRIES
+  }
+  taskEXIT_CRITICAL();
+  return notified;
+}
+
+}  // namespace pw::sync