VisitedLinkProvider.cpp revision 65f03d4f644ce73618e5f4f50dd694b26f55ae12 
1/*
2 * Copyright (C) 2010 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "VisitedLinkProvider.h"
27
28#include "SharedMemory.h"
29#include "VisitedLinkTable.h"
30#include "WebContext.h"
31#include "WebProcessMessages.h"
32
33using namespace WebCore;
34
35namespace WebKit {
36
37static const int VisitedLinkTableMaxLoad = 2;
38
39VisitedLinkProvider::VisitedLinkProvider(WebContext* context)
40    : m_context(context)
41    , m_visitedLinksPopulated(false)
42    , m_webProcessHasVisitedLinkState(false)
43    , m_keyCount(0)
44    , m_tableSize(0)
45    , m_pendingVisitedLinksTimer(RunLoop::main(), this, &VisitedLinkProvider::pendingVisitedLinksTimerFired)
46{
47}
48
49void VisitedLinkProvider::processDidFinishLaunching()
50{
51    m_webProcessHasVisitedLinkState = false;
52
53    if (m_keyCount)
54        m_pendingVisitedLinksTimer.startOneShot(0);
55
56    if (m_visitedLinksPopulated)
57        return;
58
59    m_context->populateVisitedLinks();
60
61    m_visitedLinksPopulated = true;
62}
63
64void VisitedLinkProvider::addVisitedLink(LinkHash linkHash)
65{
66    m_pendingVisitedLinks.add(linkHash);
67
68    if (!m_pendingVisitedLinksTimer.isActive())
69        m_pendingVisitedLinksTimer.startOneShot(0);
70}
71
72void VisitedLinkProvider::processDidClose()
73{
74    m_pendingVisitedLinksTimer.stop();
75}
76
77static unsigned nextPowerOf2(unsigned v)
78{
79    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
80    // Devised by Sean Anderson, Sepember 14, 2001
81
82    v--;
83    v |= v >> 1;
84    v |= v >> 2;
85    v |= v >> 4;
86    v |= v >> 8;
87    v |= v >> 16;
88    v++;
89
90    return v;
91}
92
93static unsigned tableSizeForKeyCount(unsigned keyCount)
94{
95    // We want the table to be at least half empty.
96    unsigned tableSize = nextPowerOf2(keyCount * VisitedLinkTableMaxLoad);
97
98    // Ensure that the table size is at least the size of a page.
99    size_t minimumTableSize = SharedMemory::systemPageSize() / sizeof(LinkHash);
100    if (tableSize < minimumTableSize)
101        return minimumTableSize;
102
103    return tableSize;
104}
105
106void VisitedLinkProvider::pendingVisitedLinksTimerFired()
107{
108    Vector<WebCore::LinkHash> pendingVisitedLinks;
109    copyToVector(m_pendingVisitedLinks, pendingVisitedLinks);
110    m_pendingVisitedLinks.clear();
111
112    unsigned currentTableSize = m_tableSize;
113    unsigned newTableSize = tableSizeForKeyCount(m_keyCount + pendingVisitedLinks.size());
114
115    // Links that were added.
116    Vector<WebCore::LinkHash> addedVisitedLinks;
117
118    if (currentTableSize != newTableSize) {
119        // Create a new table.
120        RefPtr<SharedMemory> newTableMemory = SharedMemory::create(newTableSize * sizeof(LinkHash));
121
122        // We failed to create the shared memory.
123        if (!newTableMemory)
124            return;
125
126        memset(newTableMemory->data(), 0, newTableMemory->size());
127
128        RefPtr<SharedMemory> currentTableMemory = m_table.sharedMemory();
129
130        m_table.setSharedMemory(newTableMemory);
131        m_tableSize = newTableSize;
132
133        if (currentTableMemory) {
134            ASSERT(currentTableMemory->size() == currentTableSize * sizeof(LinkHash));
135
136            // Go through the current hash table and re-add all entries to the new hash table.
137            const LinkHash* currentLinkHashes = static_cast<const LinkHash*>(currentTableMemory->data());
138            for (unsigned i = 0; i < currentTableSize; ++i) {
139                LinkHash linkHash = currentLinkHashes[i];
140
141                if (!linkHash)
142                    continue;
143
144                // It should always be possible to add the link hash to a new table.
145                if (!m_table.addLinkHash(linkHash))
146                    ASSERT_NOT_REACHED();
147            }
148        }
149    }
150
151    for (size_t i = 0; i < pendingVisitedLinks.size(); ++i) {
152        if (m_table.addLinkHash(pendingVisitedLinks[i]))
153            addedVisitedLinks.append(pendingVisitedLinks[i]);
154    }
155
156    m_keyCount += pendingVisitedLinks.size();
157
158    if (!m_webProcessHasVisitedLinkState || currentTableSize != newTableSize) {
159        // Send the new visited link table.
160
161        SharedMemory::Handle handle;
162        if (!m_table.sharedMemory()->createHandle(handle, SharedMemory::ReadOnly))
163            return;
164
165        m_context->process()->send(Messages::WebProcess::SetVisitedLinkTable(handle), 0);
166    }
167
168    // We now need to let the web process know that we've added links.
169    if (m_webProcessHasVisitedLinkState && addedVisitedLinks.size() <= 20) {
170        m_context->process()->send(Messages::WebProcess::VisitedLinkStateChanged(addedVisitedLinks), 0);
171        return;
172    }
173
174    // Just recalculate all the visited links.
175    m_context->process()->send(Messages::WebProcess::AllVisitedLinkStateChanged(), 0);
176    m_webProcessHasVisitedLinkState = true;
177}
178
179} // namespace WebKit
180