Line data Source code
1 : /*
2 : * Copyright (c) 2021 Project CHIP Authors
3 : *
4 : * Licensed under the Apache License, Version 2.0 (the "License");
5 : * you may not use this file except in compliance with the License.
6 : * You may obtain a copy of the License at
7 : *
8 : * http://www.apache.org/licenses/LICENSE-2.0
9 : *
10 : * Unless required by applicable law or agreed to in writing, software
11 : * distributed under the License is distributed on an "AS IS" BASIS,
12 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : * See the License for the specific language governing permissions and
14 : * limitations under the License.
15 : */
16 :
17 : #include "lib/support/CHIPMem.h"
18 : #include "lib/support/CodeUtils.h"
19 : #include "lib/support/ScopedBuffer.h"
20 : #include <access/AuthMode.h>
21 : #include <lib/support/Defer.h>
22 : #include <transport/SecureSession.h>
23 : #include <transport/SecureSessionTable.h>
24 :
25 : namespace chip {
26 : namespace Transport {
27 :
28 1484 : Optional<SessionHandle> SecureSessionTable::CreateNewSecureSessionForTest(SecureSession::Type secureSessionType,
29 : uint16_t localSessionId, NodeId localNodeId,
30 : NodeId peerNodeId, CATValues peerCATs,
31 : uint16_t peerSessionId, FabricIndex fabricIndex,
32 : const ReliableMessageProtocolConfig & config)
33 : {
34 1484 : if (secureSessionType == SecureSession::Type::kCASE)
35 : {
36 71 : if ((fabricIndex == kUndefinedFabricIndex) || (localNodeId == kUndefinedNodeId) || (peerNodeId == kUndefinedNodeId))
37 : {
38 0 : return Optional<SessionHandle>::Missing();
39 : }
40 : }
41 1413 : else if (secureSessionType == SecureSession::Type::kPASE)
42 : {
43 1413 : if ((fabricIndex != kUndefinedFabricIndex) || (localNodeId != kUndefinedNodeId) || (peerNodeId != kUndefinedNodeId))
44 : {
45 : // TODO: This secure session type is infeasible! We must fix the tests
46 : if (false)
47 : {
48 : return Optional<SessionHandle>::Missing();
49 : }
50 :
51 : (void) fabricIndex;
52 : }
53 : }
54 :
55 1484 : SecureSession * result = mEntries.CreateObject(*this, secureSessionType, localSessionId, localNodeId, peerNodeId, peerCATs,
56 : peerSessionId, fabricIndex, config);
57 1484 : return result != nullptr ? MakeOptional<SessionHandle>(*result) : Optional<SessionHandle>::Missing();
58 : }
59 :
60 133750 : Optional<SessionHandle> SecureSessionTable::CreateNewSecureSession(SecureSession::Type secureSessionType,
61 : ScopedNodeId sessionEvictionHint)
62 : {
63 133750 : Optional<SessionHandle> rv = Optional<SessionHandle>::Missing();
64 133750 : SecureSession * allocated = nullptr;
65 :
66 133750 : auto sessionId = FindUnusedSessionId();
67 133750 : VerifyOrReturnValue(sessionId.HasValue(), Optional<SessionHandle>::Missing());
68 :
69 : //
70 : // We allocate a new session out of the pool if we have space in it. If we don't, we need
71 : // to run the eviction algorithm to get a free slot. We shall ALWAYS be guaranteed to evict
72 : // an existing session in the table in normal operating circumstances.
73 : //
74 133750 : if (mEntries.Allocated() < GetMaxSessionTableSize())
75 : {
76 133737 : allocated = mEntries.CreateObject(*this, secureSessionType, sessionId.Value());
77 : }
78 : else
79 : {
80 13 : allocated = EvictAndAllocate(sessionId.Value(), secureSessionType, sessionEvictionHint);
81 : }
82 :
83 133750 : VerifyOrReturnValue(allocated != nullptr, Optional<SessionHandle>::Missing());
84 :
85 133750 : rv = MakeOptional<SessionHandle>(*allocated);
86 133750 : mNextSessionId = sessionId.Value() == kMaxSessionID ? static_cast<uint16_t>(kUnsecuredSessionId + 1)
87 133748 : : static_cast<uint16_t>(sessionId.Value() + 1);
88 :
89 133750 : return rv;
90 133750 : }
91 :
92 13 : SecureSession * SecureSessionTable::EvictAndAllocate(uint16_t localSessionId, SecureSession::Type secureSessionType,
93 : const ScopedNodeId & sessionEvictionHint)
94 : {
95 13 : VerifyOrDieWithMsg(!mRunningEvictionLogic, SecureChannel,
96 : "EvictAndAllocate isn't re-entrant, yet someone called us while we're already running");
97 :
98 13 : mRunningEvictionLogic = true;
99 :
100 13 : auto cleanup = MakeDefer([this]() { mRunningEvictionLogic = false; });
101 :
102 13 : ChipLogProgress(SecureChannel, "Evicting a slot for session with LSID: %d, type: %u", localSessionId,
103 : (uint8_t) secureSessionType);
104 :
105 13 : VerifyOrDie(mEntries.Allocated() <= GetMaxSessionTableSize());
106 :
107 : //
108 : // Create a temporary list of objects each of which points to a session in the existing
109 : // session table, but are swappable. This allows them to then be used with a sorting algorithm
110 : // without affecting the sessions in the table itself.
111 : //
112 : // The size of this shouldn't place significant demands on the stack if using the default
113 : // configuration for CHIP_CONFIG_SECURE_SESSION_POOL_SIZE (17). Each item is
114 : // 8 bytes in size (on a 32-bit platform), and 16 bytes in size (on a 64-bit platform,
115 : // including padding).
116 : //
117 : // Total size of this stack variable = 17 * 8 = 136bytes (32-bit platform), 272 bytes (64-bit platform).
118 : //
119 : // Even if the define is set to a large value, it's likely not so bad on the sort of platform setup
120 : // that would have that sort of pool size.
121 : //
122 : // We need to sort (as opposed to just a linear search for the smallest/largest item)
123 : // since it is possible that the candidate selected for eviction may not actually be
124 : // released once marked for expiration (see comments below for more details).
125 : //
126 : // Consequently, we may need to walk the candidate list till we find one that is.
127 : // Sorting provides a better overall performance model in this scheme.
128 : //
129 : // (#19967): Investigate doing linear search instead.
130 : //
131 : //
132 : SortableSession sortableSessions[CHIP_CONFIG_SECURE_SESSION_POOL_SIZE];
133 :
134 13 : unsigned int index = 0;
135 :
136 : //
137 : // Compute two key stats for each session - the number of other sessions that
138 : // match its fabric, as well as the number of other sessions that match its peer.
139 : //
140 : // This will be used by the session eviction algorithm later.
141 : //
142 13 : ForEachSession([&index, &sortableSessions, this](auto * session) {
143 84 : sortableSessions[index].mSession = session;
144 84 : sortableSessions[index].mNumMatchingOnFabric = 0;
145 84 : sortableSessions[index].mNumMatchingOnPeer = 0;
146 :
147 84 : ForEachSession([session, index, &sortableSessions](auto * otherSession) {
148 576 : if (session != otherSession)
149 : {
150 492 : if (session->GetFabricIndex() == otherSession->GetFabricIndex())
151 : {
152 246 : sortableSessions[index].mNumMatchingOnFabric++;
153 :
154 246 : if (session->GetPeerNodeId() == otherSession->GetPeerNodeId())
155 : {
156 78 : sortableSessions[index].mNumMatchingOnPeer++;
157 : }
158 : }
159 : }
160 :
161 576 : return Loop::Continue;
162 : });
163 :
164 84 : index++;
165 84 : return Loop::Continue;
166 : });
167 :
168 13 : auto sortableSessionSpan = Span<SortableSession>(sortableSessions, mEntries.Allocated());
169 13 : EvictionPolicyContext policyContext(sortableSessionSpan, sessionEvictionHint);
170 :
171 13 : DefaultEvictionPolicy(policyContext);
172 13 : ChipLogProgress(SecureChannel, "Sorted sessions for eviction...");
173 :
174 13 : const auto numSessions = mEntries.Allocated();
175 :
176 : #if CHIP_DETAIL_LOGGING
177 13 : ChipLogDetail(SecureChannel, "Sorted Eviction Candidates (ranked from best candidate to worst):");
178 97 : for (auto * session = sortableSessions; session != (sortableSessions + numSessions); session++)
179 : {
180 84 : ChipLogDetail(SecureChannel,
181 : "\t%ld: [%p] -- Peer: [%u:" ChipLogFormatX64
182 : "] State: '%s', NumMatchingOnFabric: %d NumMatchingOnPeer: %d ActivityTime: %lu",
183 : static_cast<long int>(session - sortableSessions), session->mSession,
184 : session->mSession->GetPeer().GetFabricIndex(), ChipLogValueX64(session->mSession->GetPeer().GetNodeId()),
185 : session->mSession->GetStateStr(), session->mNumMatchingOnFabric, session->mNumMatchingOnPeer,
186 : static_cast<unsigned long>(session->mSession->GetLastActivityTime().count()));
187 : }
188 : #endif
189 :
190 13 : for (auto * session = sortableSessions; session != (sortableSessions + numSessions); session++)
191 : {
192 13 : if (session->mSession->IsPendingEviction())
193 : {
194 0 : continue;
195 : }
196 :
197 13 : ChipLogProgress(SecureChannel, "Candidate Session[%p] - Attempting to evict...", session->mSession);
198 :
199 13 : auto prevCount = mEntries.Allocated();
200 :
201 : //
202 : // SessionHolders act like weak-refs on a session, but since they do still add to the ref-count of a SecureSession, we
203 : // cannot actually tell whether there are truly any strong-refs (SessionHandles) on this session because if we did, we'd
204 : // avoid evicting it since it's pointless to do so.
205 : //
206 : // However, we don't actually have SessionHolders implemented correctly as weak-refs, requiring us to go ahead and 'try' to
207 : // evict it, and see if it still remains in the table. If it does, we have to try the next one. If it doesn't, we know we've
208 : // earned a free spot.
209 : //
210 : // See #19495.
211 : //
212 13 : session->mSession->MarkForEviction();
213 :
214 13 : auto newCount = mEntries.Allocated();
215 :
216 13 : if (newCount < prevCount)
217 : {
218 13 : ChipLogProgress(SecureChannel, "Successfully evicted a session!");
219 13 : auto * retSession = mEntries.CreateObject(*this, secureSessionType, localSessionId);
220 13 : VerifyOrDie(session != nullptr);
221 13 : return retSession;
222 : }
223 : }
224 :
225 0 : VerifyOrDieWithMsg(false, SecureChannel, "We couldn't find any session to evict at all, something's wrong!");
226 : return nullptr;
227 13 : }
228 :
229 13 : void SecureSessionTable::DefaultEvictionPolicy(EvictionPolicyContext & evictionContext)
230 : {
231 : //
232 : // This implements a spec-compliant sorting policy that ensures both guarantees for sessions per-fabric as
233 : // mandated by the spec as well as fairness in terms of selecting the most appropriate session to evict
234 : // based on multiple criteria.
235 : //
236 : // See the description of this function in the header for more details on each sorting key below.
237 : //
238 13 : evictionContext.Sort([&evictionContext](const SortableSession & a, const SortableSession & b) -> bool {
239 : //
240 : // Sorting on Key1
241 : //
242 173 : if (a.mNumMatchingOnFabric != b.mNumMatchingOnFabric)
243 : {
244 24 : return a.mNumMatchingOnFabric > b.mNumMatchingOnFabric;
245 : }
246 :
247 : bool doesAMatchSessionHintFabric =
248 149 : a.mSession->GetPeer().GetFabricIndex() == evictionContext.GetSessionEvictionHint().GetFabricIndex();
249 : bool doesBMatchSessionHintFabric =
250 149 : b.mSession->GetPeer().GetFabricIndex() == evictionContext.GetSessionEvictionHint().GetFabricIndex();
251 :
252 : //
253 : // Sorting on Key2
254 : //
255 149 : if (doesAMatchSessionHintFabric != doesBMatchSessionHintFabric)
256 : {
257 35 : return doesAMatchSessionHintFabric > doesBMatchSessionHintFabric;
258 : }
259 :
260 : //
261 : // Sorting on Key3
262 : //
263 114 : if (a.mNumMatchingOnPeer != b.mNumMatchingOnPeer)
264 : {
265 3 : return a.mNumMatchingOnPeer > b.mNumMatchingOnPeer;
266 : }
267 :
268 : // We have an evicton hint in two cases:
269 : //
270 : // 1) When we just established CASE as a responder, the hint is the node
271 : // we just established CASE to.
272 : // 2) When starting to establish CASE as an initiator, the hint is the
273 : // node we are going to establish CASE to.
274 : //
275 : // In case 2, we should not end up here if there is an active session to
276 : // the peer at all (because that session should have been used instead
277 : // of establishing a new one).
278 : //
279 : // In case 1, we know we have a session matching the hint, but we don't
280 : // want to pick that one for eviction, because we just established it.
281 : // So we should not consider a session as matching a hint if it's active
282 : // and is the only session to our peer.
283 : //
284 : // Checking for the "active" state in addition to the "only session to
285 : // peer" state allows us to prioritize evicting defuct sessions that
286 : // match the hint against other defunct sessions.
287 222 : auto sessionMatchesEvictionHint = [&evictionContext](const SortableSession & session) -> int {
288 222 : if (session.mSession->GetPeer() != evictionContext.GetSessionEvictionHint())
289 : {
290 180 : return false;
291 : }
292 42 : bool isOnlyActiveSessionToPeer = session.mSession->IsActiveSession() && session.mNumMatchingOnPeer == 0;
293 42 : return !isOnlyActiveSessionToPeer;
294 111 : };
295 111 : int doesAMatchSessionHint = sessionMatchesEvictionHint(a);
296 111 : int doesBMatchSessionHint = sessionMatchesEvictionHint(b);
297 :
298 : //
299 : // Sorting on Key4
300 : //
301 111 : if (doesAMatchSessionHint != doesBMatchSessionHint)
302 : {
303 8 : return doesAMatchSessionHint > doesBMatchSessionHint;
304 : }
305 :
306 103 : int aStateScore = 0, bStateScore = 0;
307 206 : auto assignStateScore = [](auto & score, const auto & session) {
308 206 : if (session.IsDefunct())
309 : {
310 9 : score = 2;
311 : }
312 197 : else if (session.IsActiveSession())
313 : {
314 194 : score = 1;
315 : }
316 : else
317 : {
318 3 : score = 0;
319 : }
320 206 : };
321 :
322 103 : assignStateScore(aStateScore, *a.mSession);
323 103 : assignStateScore(bStateScore, *b.mSession);
324 :
325 : //
326 : // Sorting on Key5
327 : //
328 103 : if (aStateScore != bStateScore)
329 : {
330 4 : return (aStateScore > bStateScore);
331 : }
332 :
333 : //
334 : // Sorting on Key6
335 : //
336 99 : return (a->GetLastActivityTime() < b->GetLastActivityTime());
337 : });
338 13 : }
339 :
340 9648 : Optional<SessionHandle> SecureSessionTable::FindSecureSessionByLocalKey(uint16_t localSessionId)
341 : {
342 9648 : SecureSession * result = nullptr;
343 9648 : mEntries.ForEachActiveObject([&](auto session) {
344 15200 : if (session->GetLocalSessionId() == localSessionId)
345 : {
346 9636 : result = session;
347 9636 : return Loop::Break;
348 : }
349 5564 : return Loop::Continue;
350 : });
351 9648 : return result != nullptr ? MakeOptional<SessionHandle>(*result) : Optional<SessionHandle>::Missing();
352 : }
353 :
354 133750 : Optional<uint16_t> SecureSessionTable::FindUnusedSessionId()
355 : {
356 133750 : uint16_t candidate_base = 0;
357 133750 : uint64_t candidate_mask = 0;
358 133750 : for (uint32_t i = 0; i <= kMaxSessionID; i += 64)
359 : {
360 : // candidate_base is the base session ID we are searching from.
361 : // We have a 64-bit mask anchored at this ID and iterate over the
362 : // whole session table, setting bits in the mask for in-use IDs.
363 : // If we can iterate through the entire session table and have
364 : // any bits clear in the mask, we have available session IDs.
365 133750 : candidate_base = static_cast<uint16_t>(i + mNextSessionId);
366 133750 : candidate_mask = 0;
367 : {
368 133750 : uint16_t shift = static_cast<uint16_t>(kUnsecuredSessionId - candidate_base);
369 133750 : if (shift <= 63)
370 : {
371 126 : candidate_mask |= (1ULL << shift); // kUnsecuredSessionId is never available
372 : }
373 : }
374 133750 : mEntries.ForEachActiveObject([&](auto session) {
375 3269846 : uint16_t shift = static_cast<uint16_t>(session->GetLocalSessionId() - candidate_base);
376 3269846 : if (shift <= 63)
377 : {
378 3100 : candidate_mask |= (1ULL << shift);
379 : }
380 3269846 : if (candidate_mask == UINT64_MAX)
381 : {
382 0 : return Loop::Break; // No bits clear means this bucket is full.
383 : }
384 3269846 : return Loop::Continue;
385 : });
386 133750 : if (candidate_mask != UINT64_MAX)
387 : {
388 133750 : break; // Any bit clear means we have an available ID in this bucket.
389 : }
390 : }
391 133750 : if (candidate_mask != UINT64_MAX)
392 : {
393 133750 : uint16_t offset = 0;
394 133799 : while (candidate_mask & 1)
395 : {
396 49 : candidate_mask >>= 1;
397 49 : ++offset;
398 : }
399 133750 : uint16_t available = static_cast<uint16_t>(candidate_base + offset);
400 133750 : return MakeOptional<uint16_t>(available);
401 : }
402 :
403 0 : return NullOptional;
404 : }
405 :
406 : } // namespace Transport
407 : } // namespace chip
|
