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