1// Copyright 2013 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#ifndef CONTENT_BROWSER_RENDERER_DATA_MEMOIZING_STORE_H_
6#define CONTENT_BROWSER_RENDERER_DATA_MEMOIZING_STORE_H_
7
8#include <map>
9
10#include "base/bind.h"
11#include "base/synchronization/lock.h"
12#include "content/public/browser/browser_thread.h"
13#include "content/public/browser/render_process_host.h"
14#include "content/public/browser/render_process_host_observer.h"
15
16namespace content {
17
18// RendererDataMemoizingStore is a thread-safe container that retains reference
19// counted objects that are associated with one or more render processes.
20// Objects are identified by an int and only a single reference to a given
21// object is retained. RendererDataMemoizingStore watches for render process
22// termination and releases objects that are no longer associated with any
23// render process.
24//
25// TODO(jcampan): Rather than watching for render process termination, we should
26//                instead be listening to events such as resource cached/
27//                removed from cache, and remove the items when we know they
28//                are not used anymore.
29template <typename T>
30class RendererDataMemoizingStore : public RenderProcessHostObserver {
31 public:
32  RendererDataMemoizingStore() : next_item_id_(1) {
33  }
34
35  ~RendererDataMemoizingStore() {
36    DCHECK_EQ(0U, id_to_item_.size()) << "Failed to outlive render processes";
37  }
38
39  // Store adds |item| to this collection, associates it with the given render
40  // process id and returns an opaque identifier for it. If |item| is already
41  // known, the same identifier will be returned.
42  int Store(T* item, int process_id) {
43    DCHECK(item);
44    base::AutoLock auto_lock(lock_);
45
46    int item_id;
47
48    // Do we already know this item?
49    typename ReverseItemMap::iterator item_iter = item_to_id_.find(item);
50    if (item_iter == item_to_id_.end()) {
51      item_id = next_item_id_++;
52      // We use 0 as an invalid item_id value.  In the unlikely event that
53      // next_item_id_ wraps around, we reset it to 1.
54      if (next_item_id_ == 0)
55        next_item_id_ = 1;
56      id_to_item_[item_id] = item;
57      item_to_id_[item] = item_id;
58    } else {
59      item_id = item_iter->second;
60    }
61
62    // Let's update process_id_to_item_id_.
63    std::pair<IDMap::iterator, IDMap::iterator> process_ids =
64        process_id_to_item_id_.equal_range(process_id);
65    bool already_watching_process = (process_ids.first != process_ids.second);
66    if (std::find_if(process_ids.first, process_ids.second,
67                     MatchSecond<int>(item_id)) == process_ids.second) {
68      process_id_to_item_id_.insert(std::make_pair(process_id, item_id));
69    }
70
71    // And item_id_to_process_id_.
72    std::pair<IDMap::iterator, IDMap::iterator> item_ids =
73        item_id_to_process_id_.equal_range(item_id);
74    if (std::find_if(item_ids.first, item_ids.second,
75                     MatchSecond<int>(process_id)) == item_ids.second) {
76      item_id_to_process_id_.insert(std::make_pair(item_id, process_id));
77    }
78
79    // If we're not doing so already, keep an eye for the process host deletion.
80    if (!already_watching_process) {
81      if (BrowserThread::CurrentlyOn(BrowserThread::UI)) {
82        StartObservingProcess(process_id);
83      } else {
84        BrowserThread::PostTask(
85            BrowserThread::UI,
86            FROM_HERE,
87            base::Bind(&RendererDataMemoizingStore::StartObservingProcess,
88                       base::Unretained(this),
89                       process_id));
90      }
91    }
92
93    DCHECK(item_id);
94    return item_id;
95  }
96
97  // Retrieve fetches a previously Stored() item, identified by |item_id|.
98  // If |item_id| is recognized, |item| will be updated and Retrieve() will
99  // return true, it will otherwise return false.
100  bool Retrieve(int item_id, scoped_refptr<T>* item) {
101    base::AutoLock auto_lock(lock_);
102
103    typename ItemMap::iterator iter = id_to_item_.find(item_id);
104    if (iter == id_to_item_.end())
105      return false;
106    if (item)
107      *item = iter->second;
108    return true;
109  }
110
111 private:
112  typedef std::multimap<int, int> IDMap;
113  typedef std::map<int, scoped_refptr<T> > ItemMap;
114  typedef std::map<T*, int, typename T::LessThan> ReverseItemMap;
115
116  template <typename M>
117  struct MatchSecond {
118    explicit MatchSecond(const M& t) : value(t) {}
119
120    template <typename Pair>
121    bool operator()(const Pair& p) const {
122      return (value == p.second);
123    }
124
125    M value;
126  };
127
128  void StartObservingProcess(int process_id) {
129    DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
130    RenderProcessHost* host = RenderProcessHost::FromID(process_id);
131    if (!host) {
132      // We lost the race to observe the host before it was destroyed. Since
133      // this function was called because we're managing objects tied to that
134      // (now destroyed) RenderProcessHost, let's clean up.
135      RemoveRenderProcessItems(process_id);
136      return;
137    }
138
139    host->AddObserver(this);
140  }
141
142  // Remove the item specified by |item_id| from id_to_item_ and item_to_id_.
143  // NOTE: the caller (RemoveRenderProcessItems) must hold lock_.
144  void RemoveInternal(int item_id) {
145    typename ItemMap::iterator item_iter = id_to_item_.find(item_id);
146    DCHECK(item_iter != id_to_item_.end());
147
148    typename ReverseItemMap::iterator id_iter =
149        item_to_id_.find(item_iter->second.get());
150    DCHECK(id_iter != item_to_id_.end());
151    item_to_id_.erase(id_iter);
152
153    id_to_item_.erase(item_iter);
154  }
155
156  void RenderProcessHostDestroyed(RenderProcessHost* host) {
157    DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
158    RemoveRenderProcessItems(host->GetID());
159  }
160
161  // Removes all the items associated with the specified process from the store.
162  void RemoveRenderProcessItems(int process_id) {
163    base::AutoLock auto_lock(lock_);
164
165    // We iterate through all the item ids for that process.
166    std::pair<IDMap::iterator, IDMap::iterator> process_ids =
167        process_id_to_item_id_.equal_range(process_id);
168    for (IDMap::iterator ids_iter = process_ids.first;
169         ids_iter != process_ids.second; ++ids_iter) {
170      int item_id = ids_iter->second;
171      // Find all the processes referring to this item id in
172      // item_id_to_process_id_, then locate the process being removed within
173      // that range.
174      std::pair<IDMap::iterator, IDMap::iterator> item_ids =
175          item_id_to_process_id_.equal_range(item_id);
176      IDMap::iterator proc_iter = std::find_if(
177          item_ids.first, item_ids.second, MatchSecond<int>(process_id));
178      DCHECK(proc_iter != item_ids.second);
179
180      // Before removing, determine if no other processes refer to the current
181      // item id. If |proc_iter| (the current process) is the lower bound of
182      // processes containing the current item id and if |next_proc_iter| is the
183      // upper bound (the first process that does not), then only one process,
184      // the one being removed, refers to the item id.
185      IDMap::iterator next_proc_iter = proc_iter;
186      ++next_proc_iter;
187      bool last_process_for_item_id =
188          (proc_iter == item_ids.first && next_proc_iter == item_ids.second);
189      item_id_to_process_id_.erase(proc_iter);
190
191      if (last_process_for_item_id) {
192        // The current item id is not referenced by any other processes, so
193        // remove it from id_to_item_ and item_to_id_.
194        RemoveInternal(item_id);
195      }
196    }
197    if (process_ids.first != process_ids.second)
198      process_id_to_item_id_.erase(process_ids.first, process_ids.second);
199  }
200
201  IDMap process_id_to_item_id_;
202  IDMap item_id_to_process_id_;
203  ItemMap id_to_item_;
204  ReverseItemMap item_to_id_;
205
206  int next_item_id_;
207
208  // This lock protects: process_id_to_item_id_, item_id_to_process_id_,
209  //                     id_to_item_, and item_to_id_.
210  base::Lock lock_;
211};
212
213}  // namespace content
214
215#endif  // CONTENT_BROWSER_RENDERER_DATA_MEMOIZING_STORE_H_
216