1 // Copyright 2019 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef NET_REPORTING_REPORTING_CACHE_IMPL_H_ 6 #define NET_REPORTING_REPORTING_CACHE_IMPL_H_ 7 8 #include <map> 9 #include <memory> 10 #include <set> 11 #include <string> 12 #include <unordered_set> 13 #include <utility> 14 #include <vector> 15 16 #include "base/containers/flat_map.h" 17 #include "base/containers/flat_set.h" 18 #include "base/containers/unique_ptr_adapters.h" 19 #include "base/memory/raw_ptr.h" 20 #include "base/sequence_checker.h" 21 #include "base/time/time.h" 22 #include "base/unguessable_token.h" 23 #include "base/values.h" 24 #include "net/base/isolation_info.h" 25 #include "net/reporting/reporting_cache.h" 26 #include "net/reporting/reporting_context.h" 27 #include "net/reporting/reporting_endpoint.h" 28 #include "net/reporting/reporting_header_parser.h" 29 #include "net/reporting/reporting_report.h" 30 #include "third_party/abseil-cpp/absl/types/optional.h" 31 #include "url/gurl.h" 32 #include "url/origin.h" 33 34 namespace net { 35 36 class ReportingCacheImpl : public ReportingCache { 37 public: 38 explicit ReportingCacheImpl(ReportingContext* context); 39 40 ReportingCacheImpl(const ReportingCacheImpl&) = delete; 41 ReportingCacheImpl& operator=(const ReportingCacheImpl&) = delete; 42 43 ~ReportingCacheImpl() override; 44 45 // ReportingCache implementation 46 void AddReport(const absl::optional<base::UnguessableToken>& reporting_source, 47 const NetworkAnonymizationKey& network_anonymization_key, 48 const GURL& url, 49 const std::string& user_agent, 50 const std::string& group_name, 51 const std::string& type, 52 base::Value::Dict body, 53 int depth, 54 base::TimeTicks queued, 55 int attempts) override; 56 void GetReports( 57 std::vector<const ReportingReport*>* reports_out) const override; 58 base::Value GetReportsAsValue() const override; 59 std::vector<const ReportingReport*> GetReportsToDeliver() override; 60 std::vector<const ReportingReport*> GetReportsToDeliverForSource( 61 const base::UnguessableToken& reporting_source) override; 62 void ClearReportsPending( 63 const std::vector<const ReportingReport*>& reports) override; 64 void IncrementReportsAttempts( 65 const std::vector<const ReportingReport*>& reports) override; 66 base::flat_map<url::Origin, std::vector<ReportingEndpoint>> 67 GetV1ReportingEndpointsByOrigin() const override; 68 void IncrementEndpointDeliveries(const ReportingEndpointGroupKey& group_key, 69 const GURL& url, 70 int reports_delivered, 71 bool successful) override; 72 void SetExpiredSource( 73 const base::UnguessableToken& reporting_source) override; 74 const base::flat_set<base::UnguessableToken>& GetExpiredSources() 75 const override; 76 void RemoveReports( 77 const std::vector<const ReportingReport*>& reports) override; 78 void RemoveReports(const std::vector<const ReportingReport*>& reports, 79 bool delivery_success) override; 80 void RemoveAllReports() override; 81 size_t GetFullReportCountForTesting() const override; 82 size_t GetReportCountWithStatusForTesting( 83 ReportingReport::Status status) const override; 84 bool IsReportPendingForTesting(const ReportingReport* report) const override; 85 bool IsReportDoomedForTesting(const ReportingReport* report) const override; 86 void OnParsedHeader( 87 const NetworkAnonymizationKey& network_anonymization_key, 88 const url::Origin& origin, 89 std::vector<ReportingEndpointGroup> parsed_header) override; 90 void OnParsedReportingEndpointsHeader( 91 const base::UnguessableToken& reporting_source, 92 const IsolationInfo& isolation_info, 93 std::vector<ReportingEndpoint> parsed_header) override; 94 std::set<url::Origin> GetAllOrigins() const override; 95 void RemoveClient(const NetworkAnonymizationKey& network_anonymization_key, 96 const url::Origin& origin) override; 97 void RemoveClientsForOrigin(const url::Origin& origin) override; 98 void RemoveAllClients() override; 99 void RemoveEndpointGroup(const ReportingEndpointGroupKey& group_key) override; 100 void RemoveEndpointsForUrl(const GURL& url) override; 101 void RemoveSourceAndEndpoints( 102 const base::UnguessableToken& reporting_source) override; 103 void AddClientsLoadedFromStore( 104 std::vector<ReportingEndpoint> loaded_endpoints, 105 std::vector<CachedReportingEndpointGroup> loaded_endpoint_groups) 106 override; 107 std::vector<ReportingEndpoint> GetCandidateEndpointsForDelivery( 108 const ReportingEndpointGroupKey& group_key) override; 109 base::Value GetClientsAsValue() const override; 110 size_t GetEndpointCount() const override; 111 void Flush() override; 112 ReportingEndpoint GetV1EndpointForTesting( 113 const base::UnguessableToken& reporting_source, 114 const std::string& endpoint_name) const override; 115 ReportingEndpoint GetEndpointForTesting( 116 const ReportingEndpointGroupKey& group_key, 117 const GURL& url) const override; 118 bool EndpointGroupExistsForTesting(const ReportingEndpointGroupKey& group_key, 119 OriginSubdomains include_subdomains, 120 base::Time expires) const override; 121 bool ClientExistsForTesting( 122 const NetworkAnonymizationKey& network_anonymization_key, 123 const url::Origin& origin) const override; 124 size_t GetEndpointGroupCountForTesting() const override; 125 size_t GetClientCountForTesting() const override; 126 size_t GetReportingSourceCountForTesting() const override; 127 void SetEndpointForTesting(const ReportingEndpointGroupKey& group_key, 128 const GURL& url, 129 OriginSubdomains include_subdomains, 130 base::Time expires, 131 int priority, 132 int weight) override; 133 void SetV1EndpointForTesting(const ReportingEndpointGroupKey& group_key, 134 const base::UnguessableToken& reporting_source, 135 const IsolationInfo& isolation_info, 136 const GURL& url) override; 137 IsolationInfo GetIsolationInfoForEndpoint( 138 const ReportingEndpoint& endpoint) const override; 139 140 private: 141 // Represents the entire Report-To configuration for a (NIK, origin) pair. 142 struct Client { 143 Client(const NetworkAnonymizationKey& network_anonymization_key, 144 const url::Origin& origin); 145 146 Client(const Client& other); 147 Client(Client&& other); 148 149 Client& operator=(const Client& other); 150 Client& operator=(Client&& other); 151 152 ~Client(); 153 154 // NIK of the context associated with this client. Needed to prevent leaking 155 // third party contexts across sites. 156 NetworkAnonymizationKey network_anonymization_key; 157 158 // Origin that configured this client. 159 url::Origin origin; 160 161 // Total number of endpoints for this origin. Should stay in sync with the 162 // sum of endpoint counts for all the groups within this client. 163 size_t endpoint_count = 0; 164 165 // Last time that any of the groups for this origin was accessed for a 166 // delivery or updated via a new header. Should stay in sync with the latest 167 // |last_used| of all the groups within this client. 168 base::Time last_used; 169 170 // Set of endpoint group names for this origin. 171 std::set<std::string> endpoint_group_names; 172 }; 173 174 using ReportSet = base::flat_set<std::unique_ptr<ReportingReport>, 175 base::UniquePtrComparator>; 176 using ClientMap = std::multimap<std::string, Client>; 177 using EndpointGroupMap = 178 std::map<ReportingEndpointGroupKey, CachedReportingEndpointGroup>; 179 using EndpointMap = 180 std::multimap<ReportingEndpointGroupKey, ReportingEndpoint>; 181 182 ReportSet::const_iterator FindReportToEvict() const; 183 184 // Consistency-checks the entire data structure of clients, groups, and 185 // endpoints, if DCHECK is on. The cached clients should pass this consistency 186 // check after completely parsing a header (i.e. not after the intermediate 187 // steps), and before and after any of the public methods that remove or 188 // retrieve client info. Also calls |sequence_checker_| to DCHECK that we are 189 // being called on a valid sequence. 190 void ConsistencyCheckClients() const; 191 192 // Helper methods for ConsistencyCheckClients(): 193 #if DCHECK_IS_ON() 194 // Returns number of endpoint groups found in |client|. 195 size_t ConsistencyCheckClient(const std::string& domain, 196 const Client& client) const; 197 198 // Returns the number of endpoints found in |group|. 199 size_t ConsistencyCheckEndpointGroup( 200 const ReportingEndpointGroupKey& key, 201 const CachedReportingEndpointGroup& group) const; 202 203 void ConsistencyCheckEndpoint(const ReportingEndpointGroupKey& key, 204 const ReportingEndpoint& endpoint, 205 EndpointMap::const_iterator endpoint_it) const; 206 #endif // DCHECK_IS_ON() 207 208 // Finds iterator to the client with the given |network_anonymization_key| and 209 // |origin|, if one exists. Returns |clients_.end()| if none is found. 210 ClientMap::iterator FindClientIt( 211 const NetworkAnonymizationKey& network_anonymization_key, 212 const url::Origin& origin); 213 214 // Overload that takes a ReportingEndpointGroupKey and finds the client 215 // to which a group specified by the |group_key| would belong. The group name 216 // of the key is ignored. 217 ClientMap::iterator FindClientIt(const ReportingEndpointGroupKey& group_key); 218 219 // Finds iterator to the endpoint group identified by |group_key| (origin and 220 // name), if one exists. Returns |endpoint_groups_.end()| if none is found. 221 EndpointGroupMap::iterator FindEndpointGroupIt( 222 const ReportingEndpointGroupKey& group_key); 223 224 // Finds iterator to the endpoint for the given |group_key| (origin and group 225 // name) and |url|, if one exists. Returns |endpoints_.end()| if none is 226 // found. 227 EndpointMap::iterator FindEndpointIt( 228 const ReportingEndpointGroupKey& group_key, 229 const GURL& url); 230 231 // Adds a new client, endpoint group, or endpoint to the cache, if none 232 // exists. If one already exists, updates the existing entry to match the new 233 // one. Returns iterator to newly added client. 234 ClientMap::iterator AddOrUpdateClient(Client new_client); 235 void AddOrUpdateEndpointGroup(CachedReportingEndpointGroup new_group); 236 void AddOrUpdateEndpoint(ReportingEndpoint new_endpoint); 237 238 // Remove all the endpoints configured for |origin| and |group| whose urls are 239 // not in |endpoints_to_keep_urls|. Does not guarantee that all the endpoints 240 // in |endpoints_to_keep_urls| exist in the cache for that group. 241 void RemoveEndpointsInGroupOtherThan( 242 const ReportingEndpointGroupKey& group_key, 243 const std::set<GURL>& endpoints_to_keep_urls); 244 245 // Remove all the endpoint groups for the NIK and origin whose names are not 246 // in |groups_to_keep_names|. Does not guarantee that all the groups in 247 // |groups_to_keep_names| exist in the cache for that client. 248 void RemoveEndpointGroupsForClientOtherThan( 249 const NetworkAnonymizationKey& network_anonymization_key, 250 const url::Origin& origin, 251 const std::set<std::string>& groups_to_keep_names); 252 253 // Gets the endpoints in the given group. 254 std::vector<ReportingEndpoint> GetEndpointsInGroup( 255 const ReportingEndpointGroupKey& group_key) const; 256 257 // Gets the number of endpoints for the given origin and group. 258 size_t GetEndpointCountInGroup( 259 const ReportingEndpointGroupKey& group_key) const; 260 261 // Updates the last_used time for the given origin and endpoint group. 262 void MarkEndpointGroupAndClientUsed(ClientMap::iterator client_it, 263 EndpointGroupMap::iterator group_it, 264 base::Time now); 265 266 // Removes the endpoint at the given iterator, which must exist in the cache. 267 // Also takes iterators to the client and endpoint group to avoid repeated 268 // lookups. May cause the client and/or group to be removed if they become 269 // empty, which would invalidate those iterators. 270 // Returns the iterator following the endpoint removed, or absl::nullopt if 271 // either of |group_it| or |client_it| were invalidated. (If |client_it| is 272 // invalidated, then so must |group_it|). 273 absl::optional<EndpointMap::iterator> RemoveEndpointInternal( 274 ClientMap::iterator client_it, 275 EndpointGroupMap::iterator group_it, 276 EndpointMap::iterator endpoint_it); 277 278 // Removes the endpoint group at the given iterator (which must exist in the 279 // cache). Also takes iterator to the client to avoid repeated lookups. May 280 // cause the client to be removed if it becomes empty, which would 281 // invalidate |client_it|. If |num_endpoints_removed| is not null, then 282 // |*num_endpoints_removed| is incremented by the number of endpoints 283 // removed. 284 // Returns the iterator following the endpoint group removed, or absl::nullopt 285 // if |client_it| was invalidated. 286 absl::optional<EndpointGroupMap::iterator> RemoveEndpointGroupInternal( 287 ClientMap::iterator client_it, 288 EndpointGroupMap::iterator group_it, 289 size_t* num_endpoints_removed = nullptr); 290 291 // Removes the client at the given iterator (which must exist in the cache), 292 // along with all of its endpoint groups and endpoints. Invalidates 293 // |client_it|. 294 // Returns the iterator following the client removed. 295 ClientMap::iterator RemoveClientInternal(ClientMap::iterator client_it); 296 297 // Evict endpoints from the specified client and globally, if necessary to 298 // obey the per-client and global endpoint limits set in the ReportingPolicy. 299 // 300 // To evict from a client: First evicts any stale or expired groups for that 301 // origin. If that removes enough endpoints, then stop. Otherwise, find the 302 // stalest group (which has not been accessed for a delivery in the longest 303 // time) with the most endpoints, and evict the least important endpoints from 304 // that group. 305 // To evict globally: Find the stalest client with the most endpoints and do 306 // the above. 307 void EnforcePerClientAndGlobalEndpointLimits(ClientMap::iterator client_it); 308 309 // Evicts endpoints from a client until it has evicted |endpoints_to_evict| 310 // endpoints. First tries to remove expired and stale groups. If that fails to 311 // satisfy the limit, finds the stalest group with the most endpoints and 312 // evicts the least important endpoints from it. 313 void EvictEndpointsFromClient(ClientMap::iterator client_it, 314 size_t endpoints_to_evict); 315 316 // Evicts the least important endpoint from a group (the endpoint with lowest 317 // priority and lowest weight). May cause the group and/or client to be 318 // deleted and the iterators invalidated. 319 void EvictEndpointFromGroup(ClientMap::iterator client_it, 320 EndpointGroupMap::iterator group_it); 321 322 // Removes all expired or stale groups from the given client. May delete the 323 // client and invalidate |client_it| if it becomes empty. 324 // Increments |*num_endpoints_removed| by the number of endpoints removed. 325 // Returns true if |client_it| was invalidated. 326 bool RemoveExpiredOrStaleGroups(ClientMap::iterator client_it, 327 size_t* num_endpoints_removed); 328 329 // Adds/removes (if it exists) |endpoint_it| from |endpoint_its_by_url_|. 330 void AddEndpointItToIndex(EndpointMap::iterator endpoint_it); 331 void RemoveEndpointItFromIndex(EndpointMap::iterator endpoint_it); 332 333 // Helper method for IncrementEndpointDeliveries 334 ReportingEndpoint::Statistics* GetEndpointStats( 335 const ReportingEndpointGroupKey& group_key, 336 const GURL& url); 337 338 // Helper methods for GetClientsAsValue(). 339 base::Value GetClientAsValue(const Client& client) const; 340 base::Value GetEndpointGroupAsValue( 341 const CachedReportingEndpointGroup& group) const; 342 base::Value GetEndpointAsValue(const ReportingEndpoint& endpoint) const; 343 344 // Convenience methods for fetching things from the context_. clock()345 const base::Clock& clock() const { return context_->clock(); } tick_clock()346 const base::TickClock& tick_clock() const { return context_->tick_clock(); } store()347 PersistentReportingStore* store() { return context_->store(); } 348 349 raw_ptr<ReportingContext> context_; 350 351 // Reports that have not yet been successfully uploaded. 352 ReportSet reports_; 353 354 // Reporting API V0 Cache: 355 // The |clients_|, |endpoint_groups_| and |endpoints_| members all hold 356 // endpoint group configuration for the V0 API. These endpoint groups are 357 // configured through the Report-To HTTP header, and are currently used for 358 // both document and network reports. 359 360 // Map of clients for all configured origins and NIKs, keyed on domain name 361 // (there may be multiple NIKs and origins per domain name). 362 ClientMap clients_; 363 364 // Map of endpoint groups, keyed on origin and group name. Keys and values 365 // must only contain V0 endpoint group keys. 366 EndpointGroupMap endpoint_groups_; 367 368 // Map of endpoints, keyed on origin and group name (there may be multiple 369 // endpoints for a given origin and group, with different urls). Keys must 370 // only contain V0 endpoint group keys. 371 EndpointMap endpoints_; 372 373 // Index of endpoints stored in |endpoints_| keyed on URL, for easier lookup 374 // during RemoveEndpointsForUrl(). Should stay in sync with |endpoints_|. 375 std::multimap<GURL, EndpointMap::iterator> endpoint_its_by_url_; 376 377 // Reporting API V1 Cache: 378 // The `document_endpoints_` member holds endpoint configuration for the V1 379 // API, configured through the Reporting-Endpoints HTTP header. These 380 // endpoints are strongly associated with the resource which configured them, 381 // and are only used for document reports. 382 383 // Map of endpoints for each reporting source, keyed on the reporting source 384 // token. This contains only V1 document endpoints. 385 std::map<base::UnguessableToken, std::vector<ReportingEndpoint>> 386 document_endpoints_; 387 388 // Isolation info for each reporting source. Used for determining credentials 389 // to send when delivering reports. This contains only V1 document endpoints. 390 std::map<base::UnguessableToken, IsolationInfo> isolation_info_; 391 392 // Reporting source tokens representing sources which have been destroyed. 393 // The configuration in `document_endpoints_` and `isolation_info_` for these 394 // sources can be removed once all outstanding reports are delivered (or 395 // expired). 396 base::flat_set<base::UnguessableToken> expired_sources_; 397 398 SEQUENCE_CHECKER(sequence_checker_); 399 }; 400 401 } // namespace net 402 403 #endif // NET_REPORTING_REPORTING_CACHE_IMPL_H_ 404