1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "components/sync_sessions/tab_node_pool.h"
6
7 #include <algorithm>
8 #include <limits>
9 #include <utility>
10
11 #include "base/logging.h"
12 #include "components/sync/base/model_type.h"
13 #include "components/sync/protocol/session_specifics.pb.h"
14 #include "components/sync/protocol/sync.pb.h"
15 #include "components/sync_sessions/synced_tab_delegate.h"
16
17 namespace sync_sessions {
18
19 const size_t TabNodePool::kFreeNodesLowWatermark = 25;
20 const size_t TabNodePool::kFreeNodesHighWatermark = 100;
21
22 const base::Feature kTabNodePoolImmediateDeletion{
23 "TabNodePoolImmediateDeletion", base::FEATURE_ENABLED_BY_DEFAULT};
24
TabNodePool()25 TabNodePool::TabNodePool() : max_used_tab_node_id_(kInvalidTabNodeID) {}
26
27 // static
28 // We start vending tab node IDs at 0.
29 const int TabNodePool::kInvalidTabNodeID = -1;
30
~TabNodePool()31 TabNodePool::~TabNodePool() {}
32
AddTabNode(int tab_node_id)33 void TabNodePool::AddTabNode(int tab_node_id) {
34 DCHECK_GT(tab_node_id, kInvalidTabNodeID);
35 DCHECK_LE(tab_node_id, max_used_tab_node_id_);
36 DCHECK(nodeid_tabid_map_.find(tab_node_id) == nodeid_tabid_map_.end());
37 DVLOG(1) << "Adding tab node " << tab_node_id << " to pool.";
38 free_nodes_pool_.insert(tab_node_id);
39 missing_nodes_pool_.erase(tab_node_id);
40 }
41
AssociateTabNode(int tab_node_id,SessionID tab_id)42 void TabNodePool::AssociateTabNode(int tab_node_id, SessionID tab_id) {
43 DCHECK_GT(tab_node_id, kInvalidTabNodeID);
44 DCHECK(tab_id.is_valid());
45
46 // This is a new node association, the sync node should be free.
47 // Remove node from free node pool and then associate it with the tab.
48 auto it = free_nodes_pool_.find(tab_node_id);
49 DCHECK(it != free_nodes_pool_.end());
50 free_nodes_pool_.erase(it);
51
52 DCHECK(nodeid_tabid_map_.find(tab_node_id) == nodeid_tabid_map_.end());
53 DVLOG(1) << "Associating tab node " << tab_node_id << " with tab "
54 << tab_id.id();
55 nodeid_tabid_map_.emplace(tab_node_id, tab_id);
56 tabid_nodeid_map_[tab_id] = tab_node_id;
57 }
58
GetTabNodeIdFromTabId(SessionID tab_id) const59 int TabNodePool::GetTabNodeIdFromTabId(SessionID tab_id) const {
60 auto it = tabid_nodeid_map_.find(tab_id);
61 if (it != tabid_nodeid_map_.end()) {
62 return it->second;
63 }
64 return kInvalidTabNodeID;
65 }
66
FreeTab(SessionID tab_id)67 void TabNodePool::FreeTab(SessionID tab_id) {
68 DCHECK(tab_id.is_valid());
69 auto it = tabid_nodeid_map_.find(tab_id);
70 if (it == tabid_nodeid_map_.end()) {
71 return; // Already freed.
72 }
73
74 int tab_node_id = it->second;
75 DVLOG(1) << "Freeing tab " << tab_id.id() << " at node " << tab_node_id;
76 nodeid_tabid_map_.erase(nodeid_tabid_map_.find(tab_node_id));
77 tabid_nodeid_map_.erase(it);
78 free_nodes_pool_.insert(tab_node_id);
79 }
80
AssociateWithFreeTabNode(SessionID tab_id)81 int TabNodePool::AssociateWithFreeTabNode(SessionID tab_id) {
82 DCHECK_EQ(0U, tabid_nodeid_map_.count(tab_id));
83
84 int tab_node_id;
85 if (free_nodes_pool_.empty() && missing_nodes_pool_.empty()) {
86 // Tab pool has neither free nodes nor "holes" within the ID range, so
87 // allocate a new one by extending the range.
88 tab_node_id = ++max_used_tab_node_id_;
89 AddTabNode(tab_node_id);
90 } else {
91 tab_node_id = std::numeric_limits<int>::max();
92 // Take the smallest available, either from the freed pool or from IDs that
93 // were never associated before (but are within 0..max_used_tab_node_id_).
94 if (!free_nodes_pool_.empty()) {
95 tab_node_id = *free_nodes_pool_.begin();
96 DCHECK_LE(tab_node_id, max_used_tab_node_id_);
97 }
98 if (!missing_nodes_pool_.empty() &&
99 *missing_nodes_pool_.begin() < tab_node_id) {
100 tab_node_id = *missing_nodes_pool_.begin();
101 DCHECK_LE(tab_node_id, max_used_tab_node_id_);
102 AddTabNode(tab_node_id);
103 }
104 }
105
106 AssociateTabNode(tab_node_id, tab_id);
107 return tab_node_id;
108 }
109
ReassociateTabNode(int tab_node_id,SessionID tab_id)110 void TabNodePool::ReassociateTabNode(int tab_node_id, SessionID tab_id) {
111 DCHECK_GT(tab_node_id, kInvalidTabNodeID);
112 DCHECK(tab_id.is_valid());
113
114 auto tabid_it = tabid_nodeid_map_.find(tab_id);
115 if (tabid_it != tabid_nodeid_map_.end()) {
116 if (tabid_it->second == tab_node_id) {
117 return; // Already associated properly.
118 } else {
119 // Another node is already associated with this tab. Free it.
120 FreeTab(tab_id);
121 }
122 }
123
124 auto nodeid_it = nodeid_tabid_map_.find(tab_node_id);
125 if (nodeid_it != nodeid_tabid_map_.end()) {
126 // This node was already associated with another tab. Free it.
127 FreeTab(nodeid_it->second);
128 } else {
129 // This is a new tab node. Add it before association. We also need to
130 // remember the "holes".
131 for (int missing_tab_node_id = max_used_tab_node_id_ + 1;
132 missing_tab_node_id < tab_node_id; ++missing_tab_node_id) {
133 missing_nodes_pool_.insert(missing_tab_node_id);
134 }
135 max_used_tab_node_id_ = std::max(max_used_tab_node_id_, tab_node_id);
136 AddTabNode(tab_node_id);
137 }
138
139 AssociateTabNode(tab_node_id, tab_id);
140 }
141
GetTabIdFromTabNodeId(int tab_node_id) const142 SessionID TabNodePool::GetTabIdFromTabNodeId(int tab_node_id) const {
143 auto it = nodeid_tabid_map_.find(tab_node_id);
144 if (it != nodeid_tabid_map_.end()) {
145 return it->second;
146 }
147 return SessionID::InvalidValue();
148 }
149
CleanupFreeTabNodes()150 std::set<int> TabNodePool::CleanupFreeTabNodes() {
151 if (base::FeatureList::IsEnabled(kTabNodePoolImmediateDeletion)) {
152 // Convert all free nodes into missing nodes, each representing a deletion.
153 missing_nodes_pool_.insert(free_nodes_pool_.begin(),
154 free_nodes_pool_.end());
155 std::set<int> deleted_node_ids = std::move(free_nodes_pool_);
156 free_nodes_pool_.clear();
157
158 // As an optimization to save memory, update |max_used_tab_node_id_| and
159 // shrink |missing_nodes_pool_| appropriately.
160 if (nodeid_tabid_map_.empty()) {
161 max_used_tab_node_id_ = kInvalidTabNodeID;
162 } else {
163 max_used_tab_node_id_ = nodeid_tabid_map_.rbegin()->first;
164 }
165
166 missing_nodes_pool_.erase(
167 missing_nodes_pool_.upper_bound(max_used_tab_node_id_),
168 missing_nodes_pool_.end());
169
170 return deleted_node_ids;
171 }
172
173 // If number of free nodes exceed kFreeNodesHighWatermark,
174 // delete sync nodes till number reaches kFreeNodesLowWatermark.
175 // Note: This logic is to mitigate temporary disassociation issues with old
176 // clients: https://crbug.com/259918. Newer versions do not need this.
177 if (free_nodes_pool_.size() <= kFreeNodesHighWatermark) {
178 return std::set<int>();
179 }
180
181 std::set<int> deleted_node_ids;
182 while (free_nodes_pool_.size() > kFreeNodesLowWatermark) {
183 // We delete the largest IDs first, to achieve more compaction.
184 const int tab_node_id = *free_nodes_pool_.rbegin();
185 deleted_node_ids.insert(tab_node_id);
186 missing_nodes_pool_.insert(tab_node_id);
187 free_nodes_pool_.erase(tab_node_id);
188 }
189 return deleted_node_ids;
190 }
191
DeleteTabNode(int tab_node_id)192 void TabNodePool::DeleteTabNode(int tab_node_id) {
193 auto it = nodeid_tabid_map_.find(tab_node_id);
194 if (it == nodeid_tabid_map_.end()) {
195 free_nodes_pool_.erase(tab_node_id);
196 return;
197 }
198
199 DCHECK_EQ(0U, free_nodes_pool_.count(tab_node_id));
200
201 SessionID tab_id = it->second;
202 DVLOG(1) << "Deleting node " << tab_node_id << " with tab ID " << tab_id;
203 tabid_nodeid_map_.erase(tab_id);
204 nodeid_tabid_map_.erase(it);
205 }
206
GetAllTabNodeIds() const207 std::set<int> TabNodePool::GetAllTabNodeIds() const {
208 std::set<int> tab_node_ids = free_nodes_pool_;
209 for (const auto& entry : nodeid_tabid_map_) {
210 tab_node_ids.insert(entry.first);
211 }
212 return tab_node_ids;
213 }
214
GetMaxUsedTabNodeIdForTest() const215 int TabNodePool::GetMaxUsedTabNodeIdForTest() const {
216 return max_used_tab_node_id_;
217 }
218
219 } // namespace sync_sessions
220