Introduce AttributeAccessInterface lookup cache (#32414)
* Introduce AttributeAccessInterface lookup cache
- Running TC_DeviceBasicComposition test caused, for a single Wildcard read,
44622 iterations through the AttributeAccessInterface (AAI) lookup loop. This
is significant runtime cost on embedded devices, when a wildcard subscription
is established or when trying to iterate over changes of attributes.
- Instrumented analysis showed that significant locality exists within
the lookup, which could be exploited by a cache.
- This PR introduces a cache, and its use, in AAI lookups. On same workload as
the initial investigation, the total number of iterations of the costly loop
went from 44622 --> 4864, a factor of almost 10, for very little additional
RAM usage (single entry in cache).
Issue #31405
Testing done:
- Added unit tests
- Integration tests still pass
- TC_BasicDeviceComposition still succeeds
* Restyled by clang-format
* Appease the Gods of Lint with a BUILD.gn entry
* Address review comments by simplifying interface
* Restyled by clang-format
* Update src/app/AttributeAccessInterfaceCache.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
---------
Co-authored-by: Restyled.io <commits@restyled.io>
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
diff --git a/src/app/AttributeAccessInterfaceCache.h b/src/app/AttributeAccessInterfaceCache.h
new file mode 100644
index 0000000..9268a70
--- /dev/null
+++ b/src/app/AttributeAccessInterfaceCache.h
@@ -0,0 +1,145 @@
+/*
+ *
+ * Copyright (c) 2024 Project CHIP Authors
+ * All rights reserved.
+ *
+ * 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
+ *
+ * http://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 <stddef.h>
+
+#include <app/AttributeAccessInterface.h>
+#include <lib/core/DataModelTypes.h>
+
+namespace chip {
+namespace app {
+
+/**
+ * @brief Cache to make look-up of AttributeAccessInterface (AAI) instances faster.
+ *
+ * This cache makes use of the fact that looking-up AttributeAccessInterface
+ * instances is usually done in loops, during read/subscription wildcard
+ * expansion, and there is a significant amount of locality.
+ *
+ * This cache records both "used" (i.e. uses AAI) and the single last
+ * "unused" (i.e. does NOT use AAI) entries. Combining positive/negative
+ * lookup led to factor of ~10 reduction of AAI lookups in total for wildcard
+ * reads on chip-all-clusters-app, with a cache size of 1. Increasing the size did not
+ * significantly improve the performance.
+ */
+class AttributeAccessInterfaceCache
+{
+public:
+ enum class CacheResult
+ {
+ kCacheMiss,
+ kDefinitelyUnused,
+ kDefinitelyUsed
+ };
+
+ AttributeAccessInterfaceCache() { Invalidate(); }
+
+ /**
+ * @brief Invalidate the whole cache. Must be called every time list of AAI registrations changes.
+ */
+ void Invalidate()
+ {
+ for (auto & entry : mCacheSlots)
+ {
+ entry.Invalidate();
+ }
+ mLastUnusedEntry.Invalidate();
+ }
+
+ /**
+ * @brief Mark that we know a given <`endpointId`, `clusterId`> uses AAI, with instance `attrInterface`
+ */
+ void MarkUsed(EndpointId endpointId, ClusterId clusterId, AttributeAccessInterface * attrInterface)
+ {
+ GetCacheSlot(endpointId, clusterId)->Set(endpointId, clusterId, attrInterface);
+ }
+
+ /**
+ * @brief Mark that we know a given <`endpointId`, `clusterId`> does NOT use AAI.
+ */
+ void MarkUnused(EndpointId endpointId, ClusterId clusterId) { mLastUnusedEntry.Set(endpointId, clusterId, nullptr); }
+
+ /**
+ * @brief Get the AttributeAccessInterface instance for a given <`endpointId`, `clusterId`>, if present in cache.
+ *
+ * @param endpointId - Endpoint ID to look-up.
+ * @param clusterId - Cluster ID to look-up.
+ * @param outAttributeAccess - If not null, and Get returns `kDefinitelyUsed`, then this is set to the instance pointer.
+ * @return a for whether the entry is actually used or not.
+ */
+ CacheResult Get(EndpointId endpointId, ClusterId clusterId, AttributeAccessInterface ** outAttributeAccess)
+ {
+ if (mLastUnusedEntry.Matches(endpointId, clusterId))
+ {
+ return CacheResult::kDefinitelyUnused;
+ }
+
+ AttributeAccessCacheEntry * cacheSlot = GetCacheSlot(endpointId, clusterId);
+ if (cacheSlot->Matches(endpointId, clusterId) && (cacheSlot->accessor != nullptr))
+ {
+ if (outAttributeAccess != nullptr)
+ {
+ *outAttributeAccess = cacheSlot->accessor;
+ }
+ return CacheResult::kDefinitelyUsed;
+ }
+
+ return CacheResult::kCacheMiss;
+ }
+
+private:
+ struct AttributeAccessCacheEntry
+ {
+ EndpointId endpointId = kInvalidEndpointId;
+ ClusterId clusterId = kInvalidClusterId;
+ AttributeAccessInterface * accessor = nullptr;
+
+ void Invalidate()
+ {
+ endpointId = kInvalidEndpointId;
+ clusterId = kInvalidClusterId;
+ accessor = nullptr;
+ }
+
+ void Set(EndpointId theEndpointId, ClusterId theClusterId, AttributeAccessInterface * theAccessor)
+ {
+ endpointId = theEndpointId;
+ clusterId = theClusterId;
+ accessor = theAccessor;
+ }
+
+ bool Matches(EndpointId theEndpointId, ClusterId theClusterId) const
+ {
+ return (endpointId == theEndpointId) && (clusterId == theClusterId);
+ }
+ };
+
+ AttributeAccessCacheEntry * GetCacheSlot(EndpointId endpointId, ClusterId clusterId)
+ {
+ (void) endpointId;
+ (void) clusterId;
+ return &mCacheSlots[0];
+ }
+
+ AttributeAccessCacheEntry mCacheSlots[1];
+ AttributeAccessCacheEntry mLastUnusedEntry;
+};
+
+} // namespace app
+} // namespace chip
diff --git a/src/app/BUILD.gn b/src/app/BUILD.gn
index 618e51d..1d76b5b 100644
--- a/src/app/BUILD.gn
+++ b/src/app/BUILD.gn
@@ -250,6 +250,7 @@
sources = [
"AttributeAccessInterface.cpp",
+ "AttributeAccessInterfaceCache.h",
"AttributePathExpandIterator.cpp",
"AttributePathExpandIterator.h",
"AttributePersistenceProvider.h",
diff --git a/src/app/tests/BUILD.gn b/src/app/tests/BUILD.gn
index e4ab603..78b9c8f 100644
--- a/src/app/tests/BUILD.gn
+++ b/src/app/tests/BUILD.gn
@@ -125,6 +125,7 @@
test_sources = [
"TestAclEvent.cpp",
+ "TestAttributeAccessInterfaceCache.cpp",
"TestAttributePathExpandIterator.cpp",
"TestAttributePersistenceProvider.cpp",
"TestAttributeValueDecoder.cpp",
diff --git a/src/app/tests/TestAttributeAccessInterfaceCache.cpp b/src/app/tests/TestAttributeAccessInterfaceCache.cpp
new file mode 100644
index 0000000..47b8e6d
--- /dev/null
+++ b/src/app/tests/TestAttributeAccessInterfaceCache.cpp
@@ -0,0 +1,129 @@
+/*
+ *
+ * Copyright (c) 2024 Project CHIP Authors
+ * All rights reserved.
+ *
+ * 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
+ *
+ * http://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 <app/AttributeAccessInterface.h>
+#include <app/AttributeAccessInterfaceCache.h>
+#include <lib/support/UnitTestRegistration.h>
+#include <nlunit-test.h>
+
+using namespace chip;
+using namespace chip::app;
+
+namespace {
+
+void TestBasicLifecycle(nlTestSuite * inSuite, void * inContext)
+{
+ using CacheResult = AttributeAccessInterfaceCache::CacheResult;
+
+ int data1 = 1;
+ int data2 = 2;
+
+ // We alias the pointers to given locations to avoid needing to implement anything
+ // since the AttributeAccessInterfaceCache only deals in pointers, and never calls
+ // the API itself.
+ AttributeAccessInterface * accessor1 = reinterpret_cast<AttributeAccessInterface *>(&data1);
+ AttributeAccessInterface * accessor2 = reinterpret_cast<AttributeAccessInterface *>(&data2);
+
+ AttributeAccessInterfaceCache cache;
+
+ // Cache can keep track of at least 1 entry,
+ AttributeAccessInterface * entry = nullptr;
+
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 1, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, entry == nullptr);
+ cache.MarkUsed(1, 1, accessor1);
+
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 1, &entry) == CacheResult::kDefinitelyUsed);
+ NL_TEST_ASSERT(inSuite, entry == accessor1);
+
+ entry = nullptr;
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, entry == nullptr);
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 1, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, entry == nullptr);
+
+ cache.MarkUsed(1, 2, accessor1);
+
+ entry = nullptr;
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, &entry) == CacheResult::kDefinitelyUsed);
+ NL_TEST_ASSERT(inSuite, entry == accessor1);
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 1, &entry) == CacheResult::kCacheMiss);
+
+ cache.MarkUsed(1, 2, accessor2);
+
+ entry = nullptr;
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, &entry) == CacheResult::kDefinitelyUsed);
+ NL_TEST_ASSERT(inSuite, entry == accessor2);
+ // The following should not crash (e.g. output not used if nullptr).
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, nullptr) == CacheResult::kDefinitelyUsed);
+
+ // Setting used to nullptr == does not mark used.
+ cache.MarkUsed(1, 2, nullptr);
+ entry = nullptr;
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, entry == nullptr);
+
+ cache.Invalidate();
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 1, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, entry == nullptr);
+ NL_TEST_ASSERT(inSuite, cache.Get(1, 2, &entry) == CacheResult::kCacheMiss);
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 1, &entry) == CacheResult::kCacheMiss);
+
+ // Marking unused works, keeps single entry, and is invalidated when invalidated fully.
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 2, nullptr) != CacheResult::kDefinitelyUnused);
+ NL_TEST_ASSERT(inSuite, cache.Get(3, 3, nullptr) != CacheResult::kDefinitelyUnused);
+ cache.MarkUnused(2, 2);
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 2, nullptr) == CacheResult::kDefinitelyUnused);
+ NL_TEST_ASSERT(inSuite, cache.Get(3, 3, nullptr) != CacheResult::kDefinitelyUnused);
+
+ cache.MarkUnused(3, 3);
+ NL_TEST_ASSERT(inSuite, cache.Get(2, 2, nullptr) != CacheResult::kDefinitelyUnused);
+ NL_TEST_ASSERT(inSuite, cache.Get(3, 3, nullptr) == CacheResult::kDefinitelyUnused);
+
+ cache.Invalidate();
+ NL_TEST_ASSERT(inSuite, cache.Get(3, 3, nullptr) != CacheResult::kDefinitelyUnused);
+}
+
+// clang-format off
+const nlTest sTests[] =
+{
+ NL_TEST_DEF("Basic AttributeAccessInterfaceCache lifecycle works", TestBasicLifecycle),
+ NL_TEST_SENTINEL()
+};
+// clang-format on
+
+} // namespace
+
+int TestAttributeAccessInterfaceCache()
+{
+ // clang-format off
+ nlTestSuite theSuite =
+ {
+ "Test for AttributeAccessInterface cache utility",
+ &sTests[0],
+ nullptr,
+ nullptr
+ };
+ // clang-format on
+
+ nlTestRunner(&theSuite, nullptr);
+
+ return (nlTestRunnerStats(&theSuite));
+}
+
+CHIP_REGISTER_TEST_SUITE(TestAttributeAccessInterfaceCache)
diff --git a/src/app/util/attribute-storage.cpp b/src/app/util/attribute-storage.cpp
index 35fd9ce..431f309 100644
--- a/src/app/util/attribute-storage.cpp
+++ b/src/app/util/attribute-storage.cpp
@@ -17,6 +17,7 @@
#include <app/util/attribute-storage.h>
+#include <app/AttributeAccessInterfaceCache.h>
#include <app/AttributePersistenceProvider.h>
#include <app/InteractionModelEngine.h>
#include <app/reporting/reporting.h>
@@ -136,6 +137,7 @@
DataVersion fixedEndpointDataVersions[ZAP_FIXED_ENDPOINT_DATA_VERSION_COUNT];
AttributeAccessInterface * gAttributeAccessOverrides = nullptr;
+AttributeAccessInterfaceCache gAttributeAccessInterfaceCache;
// shouldUnregister returns true if the given AttributeAccessInterface should be
// unregistered.
@@ -1364,6 +1366,7 @@
bool registerAttributeAccessOverride(AttributeAccessInterface * attrOverride)
{
+ gAttributeAccessInterfaceCache.Invalidate();
for (auto * cur = gAttributeAccessOverrides; cur; cur = cur->GetNext())
{
if (cur->Matches(*attrOverride))
@@ -1379,19 +1382,39 @@
void unregisterAttributeAccessOverride(AttributeAccessInterface * attrOverride)
{
+ gAttributeAccessInterfaceCache.Invalidate();
UnregisterMatchingAttributeAccessInterfaces([attrOverride](AttributeAccessInterface * entry) { return entry == attrOverride; });
}
namespace chip {
namespace app {
+
app::AttributeAccessInterface * GetAttributeAccessOverride(EndpointId endpointId, ClusterId clusterId)
{
- for (app::AttributeAccessInterface * cur = gAttributeAccessOverrides; cur; cur = cur->GetNext())
+ using CacheResult = AttributeAccessInterfaceCache::CacheResult;
+
+ AttributeAccessInterface * cached = nullptr;
+ CacheResult result = gAttributeAccessInterfaceCache.Get(endpointId, clusterId, &cached);
+ switch (result)
{
- if (cur->Matches(endpointId, clusterId))
+ case CacheResult::kDefinitelyUnused:
+ return nullptr;
+ case CacheResult::kDefinitelyUsed:
+ return cached;
+ case CacheResult::kCacheMiss:
+ default:
+ // Did not cache yet, search set of AAI registered, and cache if found.
+ for (app::AttributeAccessInterface * cur = gAttributeAccessOverrides; cur; cur = cur->GetNext())
{
- return cur;
+ if (cur->Matches(endpointId, clusterId))
+ {
+ gAttributeAccessInterfaceCache.MarkUsed(endpointId, clusterId, cur);
+ return cur;
+ }
}
+
+ // Did not find AAI registered: mark as definitely not using.
+ gAttributeAccessInterfaceCache.MarkUnused(endpointId, clusterId);
}
return nullptr;
