REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer

https://bugs.webkit.org/show_bug.cgi?id=172406
<rdar://32109532>

Reviewed by Brady Eidson.

Source/WebCore:

CachedRawResource::calculateIncrementalDataChunk was calling SharedBuffer::data each time the data
was appended to the SharedBuffer. This causes the data to be copied from two segments to one segment,
which causes the O(n^2) behavior I was worried about in r215686. These append/data/append/data calls
used to cause O(1) copies per byte which was amortized because of the exponential growth of the buffer.
After this change, there should be 0 copies per byte here, and instead a O(log(n)) binary search in the
call to std::upper_bound to find the next segment of data with a given starting location in the SharedBuffer.
We need to store the additional information of the offsets of the beginnings of the segments in a
SharedBuffer. This doesn't asymptotically increase our memory usage, but it does allow us to asymptotically
decrease the amount of time it takes to find data at a given offset in a SharedBuffer from O(n) to O(log(n)).

This allows us to complete http://speedtest.xfinity.com and new functionality in SharedBuffer is covered by API tests.

* loader/TextTrackLoader.cpp:
(WebCore::TextTrackLoader::processNewCueData):
* loader/cache/CachedRawResource.cpp:
(WebCore::CachedRawResource::calculateIncrementalDataChunk):
(WebCore::CachedRawResource::addDataBuffer):
(WebCore::CachedRawResource::finishLoading):
* loader/cache/CachedRawResource.h:
* platform/SharedBuffer.cpp:
(WebCore::SharedBuffer::SharedBuffer):
(WebCore::SharedBuffer::combineIntoOneSegment):
(WebCore::SharedBuffer::data):
(WebCore::SharedBuffer::getSomeData):
(WebCore::SharedBuffer::tryCreateArrayBuffer):
(WebCore::SharedBuffer::append):
(WebCore::SharedBuffer::clear):
(WebCore::SharedBuffer::copy):
(WebCore::SharedBuffer::internallyConsistent):
(WebCore::SharedBuffer::hintMemoryNotNeededSoon):
(WebCore::SharedBufferDataView::SharedBufferDataView):
(WebCore::SharedBufferDataView::size):
(WebCore::SharedBufferDataView::data):
* platform/SharedBuffer.h:
* platform/cf/SharedBufferCF.cpp:
(WebCore::SharedBuffer::createCFData):
(WebCore::SharedBuffer::hintMemoryNotNeededSoon):
(WebCore::SharedBuffer::append):
* platform/cocoa/SharedBufferCocoa.mm:
(WebCore::SharedBuffer::createNSData):
(WebCore::SharedBuffer::createCFData):
(WebCore::SharedBuffer::createNSDataArray):

Source/WebKit2:

* Platform/IPC/DataReference.cpp:
(IPC::SharedBufferDataReference::encode):
* WebProcess/Plugins/PluginView.cpp:
(WebKit::PluginView::redeliverManualStream):

Tools:

* TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp:
(TestWebKitAPI::checkBuffer):
(TestWebKitAPI::TEST_F):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@217260 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index c573c2d..1eb48c6 100644 (file)
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,54 @@
+2017-05-20  Alex Christensen  <achristensen@webkit.org>
+
+        REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer
+        https://bugs.webkit.org/show_bug.cgi?id=172406
+        <rdar://32109532>
+
+        Reviewed by Brady Eidson.
+
+        CachedRawResource::calculateIncrementalDataChunk was calling SharedBuffer::data each time the data
+        was appended to the SharedBuffer. This causes the data to be copied from two segments to one segment,
+        which causes the O(n^2) behavior I was worried about in r215686. These append/data/append/data calls
+        used to cause O(1) copies per byte which was amortized because of the exponential growth of the buffer.
+        After this change, there should be 0 copies per byte here, and instead a O(log(n)) binary search in the
+        call to std::upper_bound to find the next segment of data with a given starting location in the SharedBuffer.
+        We need to store the additional information of the offsets of the beginnings of the segments in a
+        SharedBuffer. This doesn't asymptotically increase our memory usage, but it does allow us to asymptotically
+        decrease the amount of time it takes to find data at a given offset in a SharedBuffer from O(n) to O(log(n)).
+
+        This allows us to complete http://speedtest.xfinity.com and new functionality in SharedBuffer is covered by API tests.
+
+        * loader/TextTrackLoader.cpp:
+        (WebCore::TextTrackLoader::processNewCueData):
+        * loader/cache/CachedRawResource.cpp:
+        (WebCore::CachedRawResource::calculateIncrementalDataChunk):
+        (WebCore::CachedRawResource::addDataBuffer):
+        (WebCore::CachedRawResource::finishLoading):
+        * loader/cache/CachedRawResource.h:
+        * platform/SharedBuffer.cpp:
+        (WebCore::SharedBuffer::SharedBuffer):
+        (WebCore::SharedBuffer::combineIntoOneSegment):
+        (WebCore::SharedBuffer::data):
+        (WebCore::SharedBuffer::getSomeData):
+        (WebCore::SharedBuffer::tryCreateArrayBuffer):
+        (WebCore::SharedBuffer::append):
+        (WebCore::SharedBuffer::clear):
+        (WebCore::SharedBuffer::copy):
+        (WebCore::SharedBuffer::internallyConsistent):
+        (WebCore::SharedBuffer::hintMemoryNotNeededSoon):
+        (WebCore::SharedBufferDataView::SharedBufferDataView):
+        (WebCore::SharedBufferDataView::size):
+        (WebCore::SharedBufferDataView::data):
+        * platform/SharedBuffer.h:
+        * platform/cf/SharedBufferCF.cpp:
+        (WebCore::SharedBuffer::createCFData):
+        (WebCore::SharedBuffer::hintMemoryNotNeededSoon):
+        (WebCore::SharedBuffer::append):
+        * platform/cocoa/SharedBufferCocoa.mm:
+        (WebCore::SharedBuffer::createNSData):
+        (WebCore::SharedBuffer::createCFData):
+        (WebCore::SharedBuffer::createNSDataArray):
+
 2017-05-22  Chris Dumez  <cdumez@apple.com>
 
         Resources in cached parsed stylesheets may bypass content blockers

diff --git a/Source/WebCore/loader/TextTrackLoader.cpp b/Source/WebCore/loader/TextTrackLoader.cpp
index 742c3a1..227f095 100644 (file)
--- a/Source/WebCore/loader/TextTrackLoader.cpp
+++ b/Source/WebCore/loader/TextTrackLoader.cpp
@@ -91,16 +91,10 @@ void TextTrackLoader::processNewCueData(CachedResource& resource)
     if (!m_cueParser)
         m_cueParser = std::make_unique<WebVTTParser>(static_cast<WebVTTParserClient*>(this), m_scriptExecutionContext);
 
-    auto bytesToSkip = m_parseOffset;
-    for (const auto& segment : *buffer) {
-        if (bytesToSkip > segment->size()) {
-            bytesToSkip -= segment->size();
-            continue;
-        }
-        auto bytesToUse = segment->size() - bytesToSkip;
-        m_cueParser->parseBytes(segment->data() + bytesToSkip, bytesToUse);
-        bytesToSkip = 0;
-        m_parseOffset += bytesToUse;
+    while (m_parseOffset < buffer->size()) {
+        auto data = buffer->getSomeData(m_parseOffset);
+        m_cueParser->parseBytes(data.data(), data.size());
+        m_parseOffset += data.size();
     }
 }
 

diff --git a/Source/WebCore/loader/cache/CachedRawResource.cpp b/Source/WebCore/loader/cache/CachedRawResource.cpp
index 05b9de1..15040a8 100644 (file)
--- a/Source/WebCore/loader/cache/CachedRawResource.cpp
+++ b/Source/WebCore/loader/cache/CachedRawResource.cpp
@@ -44,16 +44,12 @@ CachedRawResource::CachedRawResource(CachedResourceRequest&& request, Type type,
     ASSERT(isMainOrMediaOrRawResource());
 }
 
-const char* CachedRawResource::calculateIncrementalDataChunk(SharedBuffer* data, unsigned& incrementalDataLength)
+std::optional<SharedBufferDataView> CachedRawResource::calculateIncrementalDataChunk(const SharedBuffer* data) const
 {
-    incrementalDataLength = 0;
-    if (!data)
-        return nullptr;
-
-    unsigned previousDataLength = encodedSize();
-    ASSERT(data->size() >= previousDataLength);
-    incrementalDataLength = data->size() - previousDataLength;
-    return data->data() + previousDataLength;
+    size_t previousDataLength = encodedSize();
+    if (!data || data->size() <= previousDataLength)
+        return std::nullopt;
+    return data->getSomeData(previousDataLength);
 }
 
 void CachedRawResource::addDataBuffer(SharedBuffer& data)
@@ -62,10 +58,10 @@ void CachedRawResource::addDataBuffer(SharedBuffer& data)
     ASSERT(dataBufferingPolicy() == BufferData);
     m_data = &data;
 
-    unsigned incrementalDataLength;
-    const char* incrementalData = calculateIncrementalDataChunk(&data, incrementalDataLength);
+    auto incrementalData = calculateIncrementalDataChunk(&data);
     setEncodedSize(data.size());
-    notifyClientsDataWasReceived(incrementalData, incrementalDataLength);
+    if (incrementalData)
+        notifyClientsDataWasReceived(incrementalData->data(), incrementalData->size());
     if (dataBufferingPolicy() == DoNotBufferData) {
         if (m_loader)
             m_loader->setDataBufferingPolicy(DoNotBufferData);
@@ -90,11 +86,10 @@ void CachedRawResource::finishLoading(SharedBuffer* data)
     if (dataBufferingPolicy == BufferData) {
         m_data = data;
 
-        unsigned incrementalDataLength;
-        const char* incrementalData = calculateIncrementalDataChunk(data, incrementalDataLength);
-        if (data)
+        if (auto incrementalData = calculateIncrementalDataChunk(data)) {
             setEncodedSize(data->size());
-        notifyClientsDataWasReceived(incrementalData, incrementalDataLength);
+            notifyClientsDataWasReceived(incrementalData->data(), incrementalData->size());
+        }
     }
 
 #if USE(QUICK_LOOK)

diff --git a/Source/WebCore/loader/cache/CachedRawResource.h b/Source/WebCore/loader/cache/CachedRawResource.h
index 7d7468c..a03e36d 100644 (file)
--- a/Source/WebCore/loader/cache/CachedRawResource.h
+++ b/Source/WebCore/loader/cache/CachedRawResource.h
@@ -28,6 +28,7 @@ namespace WebCore {
 
 class CachedResourceClient;
 class ResourceTiming;
+class SharedBufferDataView;
 class SubresourceLoader;
 
 class CachedRawResource final : public CachedResource {
@@ -69,7 +70,7 @@ private:
     void switchClientsToRevalidatedResource() override;
     bool mayTryReplaceEncodedData() const override { return m_allowEncodedDataReplacement; }
 
-    const char* calculateIncrementalDataChunk(SharedBuffer*, unsigned& incrementalDataLength);
+    std::optional<SharedBufferDataView> calculateIncrementalDataChunk(const SharedBuffer*) const;
     void notifyClientsDataWasReceived(const char* data, unsigned length);
 
 #if USE(SOUP)

diff --git a/Source/WebCore/platform/SharedBuffer.cpp b/Source/WebCore/platform/SharedBuffer.cpp
index 283e7a3..25bab15 100644 (file)
--- a/Source/WebCore/platform/SharedBuffer.cpp
+++ b/Source/WebCore/platform/SharedBuffer.cpp
@@ -50,7 +50,7 @@ SharedBuffer::SharedBuffer(const unsigned char* data, size_t size)
 SharedBuffer::SharedBuffer(MappedFileData&& fileData)
     : m_size(fileData.size())
 {
-    m_segments.append(DataSegment::create(WTFMove(fileData)));
+    m_segments.append({0, DataSegment::create(WTFMove(fileData))});
 }
 
 SharedBuffer::SharedBuffer(Vector<char>&& data)
@@ -76,17 +76,23 @@ Ref<SharedBuffer> SharedBuffer::create(Vector<char>&& vector)
 
 void SharedBuffer::combineIntoOneSegment() const
 {
+#if !ASSERT_DISABLED
+    // FIXME: We ought to be able to set this to true and have no assertions fire.
+    // Remove all instances of appending after calling this, because they are all O(n^2) algorithms since r215686.
+    // m_hasBeenCombinedIntoOneSegment = true;
+#endif
     if (m_segments.size() <= 1)
         return;
 
     Vector<char> combinedData;
     combinedData.reserveInitialCapacity(m_size);
     for (const auto& segment : m_segments)
-        combinedData.append(segment->data(), segment->size());
+        combinedData.append(segment.segment->data(), segment.segment->size());
     ASSERT(combinedData.size() == m_size);
     m_segments.clear();
-    m_segments.append(DataSegment::create(WTFMove(combinedData)));
+    m_segments.append({0, DataSegment::create(WTFMove(combinedData))});
     ASSERT(m_segments.size() == 1);
+    ASSERT(internallyConsistent());
 }
 
 const char* SharedBuffer::data() const
@@ -94,7 +100,19 @@ const char* SharedBuffer::data() const
     if (!m_segments.size())
         return nullptr;
     combineIntoOneSegment();
-    return m_segments[0]->data();
+    ASSERT(internallyConsistent());
+    return m_segments[0].segment->data();
+}
+
+SharedBufferDataView SharedBuffer::getSomeData(size_t position) const
+{
+    RELEASE_ASSERT(position < m_size);
+    auto comparator = [](const size_t& position, const DataSegmentVectorEntry& entry) {
+        return position < entry.beginPosition;
+    };
+    const DataSegmentVectorEntry* element = std::upper_bound(m_segments.begin(), m_segments.end(), position, comparator);
+    element--; // std::upper_bound gives a pointer to the element that is greater than position. We want the element just before that.
+    return { element->segment.copyRef(), position - element->beginPosition };
 }
 
 RefPtr<ArrayBuffer> SharedBuffer::tryCreateArrayBuffer() const
@@ -107,40 +125,50 @@ RefPtr<ArrayBuffer> SharedBuffer::tryCreateArrayBuffer() const
 
     size_t position = 0;
     for (const auto& segment : m_segments) {
-        memcpy(static_cast<char*>(arrayBuffer->data()) + position, segment->data(), segment->size());
-        position += segment->size();
+        memcpy(static_cast<char*>(arrayBuffer->data()) + position, segment.segment->data(), segment.segment->size());
+        position += segment.segment->size();
     }
 
     ASSERT(position == m_size);
+    ASSERT(internallyConsistent());
     return arrayBuffer;
 }
 
 void SharedBuffer::append(const SharedBuffer& data)
 {
-    m_size += data.m_size;
+    ASSERT(!m_hasBeenCombinedIntoOneSegment);
     m_segments.reserveCapacity(m_segments.size() + data.m_segments.size());
-    for (const auto& segment : data.m_segments)
-        m_segments.uncheckedAppend(segment.copyRef());
+    for (const auto& element : data.m_segments) {
+        m_segments.uncheckedAppend({m_size, element.segment.copyRef()});
+        m_size += element.segment->size();
+    }
+    ASSERT(internallyConsistent());
 }
 
 void SharedBuffer::append(const char* data, size_t length)
 {
-    m_size += length;
+    ASSERT(!m_hasBeenCombinedIntoOneSegment);
     Vector<char> vector;
     vector.append(data, length);
-    m_segments.append(DataSegment::create(WTFMove(vector)));
+    m_segments.append({m_size, DataSegment::create(WTFMove(vector))});
+    m_size += length;
+    ASSERT(internallyConsistent());
 }
 
 void SharedBuffer::append(Vector<char>&& data)
 {
-    m_size += data.size();
-    m_segments.append(DataSegment::create(WTFMove(data)));
+    ASSERT(!m_hasBeenCombinedIntoOneSegment);
+    auto dataSize = data.size();
+    m_segments.append({m_size, DataSegment::create(WTFMove(data))});
+    m_size += dataSize;
+    ASSERT(internallyConsistent());
 }
 
 void SharedBuffer::clear()
 {
     m_size = 0;
     m_segments.clear();
+    ASSERT(internallyConsistent());
 }
 
 Ref<SharedBuffer> SharedBuffer::copy() const
@@ -148,11 +176,26 @@ Ref<SharedBuffer> SharedBuffer::copy() const
     Ref<SharedBuffer> clone = adoptRef(*new SharedBuffer);
     clone->m_size = m_size;
     clone->m_segments.reserveInitialCapacity(m_segments.size());
-    for (const auto& segment : m_segments)
-        clone->m_segments.uncheckedAppend(segment.copyRef());
+    for (const auto& element : m_segments)
+        clone->m_segments.uncheckedAppend({element.beginPosition, element.segment.copyRef()});
+    ASSERT(clone->internallyConsistent());
+    ASSERT(internallyConsistent());
     return clone;
 }
 
+#if !ASSERT_DISABLED
+bool SharedBuffer::internallyConsistent() const
+{
+    size_t position = 0;
+    for (const auto& element : m_segments) {
+        if (element.beginPosition != position)
+            return false;
+        position += element.segment->size();
+    }
+    return position == m_size;
+}
+#endif
+
 const char* SharedBuffer::DataSegment::data() const
 {
     auto visitor = WTF::makeVisitor(
@@ -169,7 +212,7 @@ const char* SharedBuffer::DataSegment::data() const
 }
 
 #if !USE(CF)
-void SharedBuffer::hintMemoryNotNeededSoon()
+void SharedBuffer::hintMemoryNotNeededSoon() const
 {
 }
 #endif
@@ -189,6 +232,23 @@ size_t SharedBuffer::DataSegment::size() const
     return WTF::visit(visitor, m_immutableData);
 }
 
+SharedBufferDataView::SharedBufferDataView(Ref<SharedBuffer::DataSegment>&& segment, size_t positionWithinSegment)
+    : m_positionWithinSegment(positionWithinSegment)
+    , m_segment(WTFMove(segment))
+{
+    ASSERT(positionWithinSegment < m_segment->size());
+}
+
+size_t SharedBufferDataView::size() const
+{
+    return m_segment->size() - m_positionWithinSegment;
+}
+
+const char* SharedBufferDataView::data() const
+{
+    return m_segment->data() + m_positionWithinSegment;
+}
+
 RefPtr<SharedBuffer> utf8Buffer(const String& string)
 {
     // Allocate a buffer big enough to hold all the characters.

diff --git a/Source/WebCore/platform/SharedBuffer.h b/Source/WebCore/platform/SharedBuffer.h
index ab6feed..68e0fe2 100644 (file)
--- a/Source/WebCore/platform/SharedBuffer.h
+++ b/Source/WebCore/platform/SharedBuffer.h
@@ -49,7 +49,9 @@ OBJC_CLASS NSData;
 #endif
 
 namespace WebCore {
-    
+
+class SharedBufferDataView;
+
 class WEBCORE_EXPORT SharedBuffer : public RefCounted<SharedBuffer> {
 public:
     static Ref<SharedBuffer> create() { return adoptRef(*new SharedBuffer); }
@@ -60,12 +62,12 @@ public:
     static Ref<SharedBuffer> create(Vector<char>&&);
     
 #if USE(FOUNDATION)
-    RetainPtr<NSData> createNSData();
+    RetainPtr<NSData> createNSData() const;
     RetainPtr<NSArray> createNSDataArray() const;
     static Ref<SharedBuffer> create(NSData *);
 #endif
 #if USE(CF)
-    RetainPtr<CFDataRef> createCFData();
+    RetainPtr<CFDataRef> createCFData() const;
     static Ref<SharedBuffer> create(CFDataRef);
     void append(CFDataRef);
 #endif
@@ -138,11 +140,18 @@ public:
         friend class SharedBuffer;
     };
 
-    using DataSegmentVector = Vector<Ref<DataSegment>, 1>;
+    struct DataSegmentVectorEntry {
+        size_t beginPosition;
+        Ref<DataSegment> segment;
+    };
+    using DataSegmentVector = Vector<DataSegmentVectorEntry, 1>;
     DataSegmentVector::const_iterator begin() const { return m_segments.begin(); }
     DataSegmentVector::const_iterator end() const { return m_segments.end(); }
+    
+    // begin and end take O(1) time, this takes O(log(N)) time.
+    SharedBufferDataView getSomeData(size_t position) const;
 
-    void hintMemoryNotNeededSoon();
+    void hintMemoryNotNeededSoon() const;
 
 private:
     explicit SharedBuffer() = default;
@@ -163,6 +172,21 @@ private:
 
     size_t m_size { 0 };
     mutable DataSegmentVector m_segments;
+
+#if !ASSERT_DISABLED
+    mutable bool m_hasBeenCombinedIntoOneSegment { false };
+    bool internallyConsistent() const;
+#endif
+};
+
+class WEBCORE_EXPORT SharedBufferDataView {
+public:
+    SharedBufferDataView(Ref<SharedBuffer::DataSegment>&&, size_t);
+    size_t size() const;
+    const char* data() const;
+private:
+    size_t m_positionWithinSegment;
+    Ref<SharedBuffer::DataSegment> m_segment;
 };
 
 RefPtr<SharedBuffer> utf8Buffer(const String&);

diff --git a/Source/WebCore/platform/cf/SharedBufferCF.cpp b/Source/WebCore/platform/cf/SharedBufferCF.cpp
index 430c9e3..a110d13 100644 (file)
--- a/Source/WebCore/platform/cf/SharedBufferCF.cpp
+++ b/Source/WebCore/platform/cf/SharedBufferCF.cpp
@@ -41,10 +41,10 @@ SharedBuffer::SharedBuffer(CFDataRef data)
 // Using Foundation allows for an even more efficient implementation of this function,
 // so only use this version for non-Foundation.
 #if !USE(FOUNDATION)
-RetainPtr<CFDataRef> SharedBuffer::createCFData()
+RetainPtr<CFDataRef> SharedBuffer::createCFData() const
 {
     if (m_segments.size() == 1) {
-        if (auto data = WTF::get_if<RetainPtr<CFDataRef>>(m_segments[0]->m_immutableData))
+        if (auto data = WTF::get_if<RetainPtr<CFDataRef>>(m_segments[0].segment->m_immutableData))
             return *data;
     }
     return adoptCF(CFDataCreate(nullptr, reinterpret_cast<const UInt8*>(data()), size()));
@@ -56,11 +56,11 @@ Ref<SharedBuffer> SharedBuffer::create(CFDataRef data)
     return adoptRef(*new SharedBuffer(data));
 }
 
-void SharedBuffer::hintMemoryNotNeededSoon()
+void SharedBuffer::hintMemoryNotNeededSoon() const
 {
-    for (const auto& segment : m_segments) {
-        if (segment->hasOneRef()) {
-            if (auto data = WTF::get_if<RetainPtr<CFDataRef>>(segment->m_immutableData))
+    for (const auto& entry : m_segments) {
+        if (entry.segment->hasOneRef()) {
+            if (auto data = WTF::get_if<RetainPtr<CFDataRef>>(entry.segment->m_immutableData))
                 OSAllocator::hintMemoryNotNeededSoon(const_cast<UInt8*>(CFDataGetBytePtr(data->get())), CFDataGetLength(data->get()));
         }
     }
@@ -68,10 +68,12 @@ void SharedBuffer::hintMemoryNotNeededSoon()
 
 void SharedBuffer::append(CFDataRef data)
 {
+    ASSERT(!m_hasBeenCombinedIntoOneSegment);
     if (data) {
+        m_segments.append({m_size, DataSegment::create(data)});
         m_size += CFDataGetLength(data);
-        m_segments.append(DataSegment::create(data));
     }
+    ASSERT(internallyConsistent());
 }
 
 }

diff --git a/Source/WebCore/platform/cocoa/SharedBufferCocoa.mm b/Source/WebCore/platform/cocoa/SharedBufferCocoa.mm
index b4801de..f2ebd86 100644 (file)
--- a/Source/WebCore/platform/cocoa/SharedBufferCocoa.mm
+++ b/Source/WebCore/platform/cocoa/SharedBufferCocoa.mm
@@ -88,18 +88,18 @@ Ref<SharedBuffer> SharedBuffer::create(NSData *nsData)
     return adoptRef(*new SharedBuffer((CFDataRef)nsData));
 }
 
-RetainPtr<NSData> SharedBuffer::createNSData()
+RetainPtr<NSData> SharedBuffer::createNSData() const
 {
     return adoptNS((NSData *)createCFData().leakRef());
 }
 
-RetainPtr<CFDataRef> SharedBuffer::createCFData()
+RetainPtr<CFDataRef> SharedBuffer::createCFData() const
 {
     combineIntoOneSegment();
     if (!m_segments.size())
         return adoptCF(CFDataCreate(nullptr, nullptr, 0));
     ASSERT(m_segments.size() == 1);
-    return adoptCF((CFDataRef)adoptNS([[WebCoreSharedBufferData alloc] initWithSharedBufferDataSegment:m_segments[0]]).leakRef());
+    return adoptCF((CFDataRef)adoptNS([[WebCoreSharedBufferData alloc] initWithSharedBufferDataSegment:m_segments[0].segment]).leakRef());
 }
 
 RefPtr<SharedBuffer> SharedBuffer::createFromReadingFile(const String& filePath)
@@ -114,7 +114,7 @@ RetainPtr<NSArray> SharedBuffer::createNSDataArray() const
 {
     auto dataArray = adoptNS([[NSMutableArray alloc] initWithCapacity:m_segments.size()]);
     for (const auto& segment : m_segments)
-        [dataArray addObject:adoptNS([[WebCoreSharedBufferData alloc] initWithSharedBufferDataSegment:segment]).get()];
+        [dataArray addObject:adoptNS([[WebCoreSharedBufferData alloc] initWithSharedBufferDataSegment:segment.segment]).get()];
     return WTFMove(dataArray);
 }
 

diff --git a/Source/WebCore/platform/graphics/gstreamer/WebKitWebSourceGStreamer.cpp b/Source/WebCore/platform/graphics/gstreamer/WebKitWebSourceGStreamer.cpp
index c613009..c9adf8c 100644 (file)
--- a/Source/WebCore/platform/graphics/gstreamer/WebKitWebSourceGStreamer.cpp
+++ b/Source/WebCore/platform/graphics/gstreamer/WebKitWebSourceGStreamer.cpp
@@ -1206,8 +1206,8 @@ void ResourceHandleStreamingClient::didReceiveBuffer(ResourceHandle*, Ref<Shared
     if (!m_resource)
         return;
 
-    for (const auto& segment : buffer.get())
-        handleDataReceived(segment->data(), segment->size());
+    for (const auto& element : buffer.get())
+        handleDataReceived(element.segment->data(), element.segment->size());
 }
 
 void ResourceHandleStreamingClient::didFinishLoading(ResourceHandle*)

diff --git a/Source/WebCore/platform/image-decoders/ImageDecoder.cpp b/Source/WebCore/platform/image-decoders/ImageDecoder.cpp
index c2bed3c..4ba4db2 100644 (file)
--- a/Source/WebCore/platform/image-decoders/ImageDecoder.cpp
+++ b/Source/WebCore/platform/image-decoders/ImageDecoder.cpp
@@ -45,13 +45,13 @@ namespace {
 static unsigned copyFromSharedBuffer(char* buffer, unsigned bufferLength, const SharedBuffer& sharedBuffer)
 {
     unsigned bytesExtracted = 0;
-    for (const auto& segment : sharedBuffer) {
-        if (bytesExtracted + segment->size() <= bufferLength) {
-            memcpy(buffer + bytesExtracted, segment->data(), segment->size());
-            bytesExtracted += segment->size();
+    for (const auto& element : sharedBuffer) {
+        if (bytesExtracted + element.segment->size() <= bufferLength) {
+            memcpy(buffer + bytesExtracted, element.segment->data(), element.segment->size());
+            bytesExtracted += element.segment->size();
         } else {
-            ASSERT(bufferLength - bytesExtracted < segment->size());
-            memcpy(buffer + bytesExtracted, segment->data(), bufferLength - bytesExtracted);
+            ASSERT(bufferLength - bytesExtracted < element.segment->size());
+            memcpy(buffer + bytesExtracted, element.segment->data(), bufferLength - bytesExtracted);
             bytesExtracted = bufferLength;
             break;
         }

diff --git a/Source/WebCore/platform/image-decoders/png/PNGImageDecoder.cpp b/Source/WebCore/platform/image-decoders/png/PNGImageDecoder.cpp
index 8a4f711..8070f64 100644 (file)
--- a/Source/WebCore/platform/image-decoders/png/PNGImageDecoder.cpp
+++ b/Source/WebCore/platform/image-decoders/png/PNGImageDecoder.cpp
@@ -158,15 +158,17 @@ public:
             return decoder->setFailed();
 
         auto bytesToSkip = m_readOffset;
-        for (const auto& segment : data) {
-            if (bytesToSkip > segment->size()) {
-                bytesToSkip -= segment->size();
+        
+        // FIXME: Use getSomeData which is O(log(n)) instead of skipping bytes which is O(n).
+        for (const auto& element : data) {
+            if (bytesToSkip > element.segment->size()) {
+                bytesToSkip -= element.segment->size();
                 continue;
             }
-            auto bytesToUse = segment->size() - bytesToSkip;
+            auto bytesToUse = element.segment->size() - bytesToSkip;
             m_readOffset += bytesToUse;
             m_currentBufferSize = m_readOffset;
-            png_process_data(m_png, m_info, reinterpret_cast<png_bytep>(const_cast<char*>(segment->data() + bytesToSkip)), bytesToUse);
+            png_process_data(m_png, m_info, reinterpret_cast<png_bytep>(const_cast<char*>(element.segment->data() + bytesToSkip)), bytesToUse);
             bytesToSkip = 0;
             // We explicitly specify the superclass encodedDataStatus() because we
             // merely want to check if we've managed to set the size, not

diff --git a/Source/WebCore/platform/soup/SharedBufferSoup.cpp b/Source/WebCore/platform/soup/SharedBufferSoup.cpp
index 9c0bf79..17ad247 100644 (file)
--- a/Source/WebCore/platform/soup/SharedBufferSoup.cpp
+++ b/Source/WebCore/platform/soup/SharedBufferSoup.cpp
@@ -30,7 +30,7 @@ SharedBuffer::SharedBuffer(SoupBuffer* soupBuffer)
 {
     ASSERT(soupBuffer);
     m_size = soupBuffer->length;
-    m_segments.append(DataSegment::create(GUniquePtr<SoupBuffer>(soupBuffer)));
+    m_segments.append({0, DataSegment::create(GUniquePtr<SoupBuffer>(soupBuffer))});
 }
 
 Ref<SharedBuffer> SharedBuffer::wrapSoupBuffer(SoupBuffer* soupBuffer)

diff --git a/Source/WebKit2/ChangeLog b/Source/WebKit2/ChangeLog
index 7ae4276..87e0ca4 100644 (file)
--- a/Source/WebKit2/ChangeLog
+++ b/Source/WebKit2/ChangeLog
@@ -1,3 +1,16 @@
+2017-05-20  Alex Christensen  <achristensen@webkit.org>
+
+        REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer
+        https://bugs.webkit.org/show_bug.cgi?id=172406
+        <rdar://32109532>
+
+        Reviewed by Brady Eidson.
+
+        * Platform/IPC/DataReference.cpp:
+        (IPC::SharedBufferDataReference::encode):
+        * WebProcess/Plugins/PluginView.cpp:
+        (WebKit::PluginView::redeliverManualStream):
+
 2017-05-22  Yongjun Zhang  <yongjun_zhang@apple.com>
 
         Need a way to allow WKWebView to load request with ShouldOpenExternalURLsPolicy::ShouldAllow.

diff --git a/Source/WebKit2/Platform/IPC/DataReference.cpp b/Source/WebKit2/Platform/IPC/DataReference.cpp
index 7da38d6..977e9d2 100644 (file)
--- a/Source/WebKit2/Platform/IPC/DataReference.cpp
+++ b/Source/WebKit2/Platform/IPC/DataReference.cpp
@@ -47,8 +47,8 @@ void SharedBufferDataReference::encode(Encoder& encoder) const
     encoder.reserve(bufferSize + sizeof(uint64_t));
     encoder << bufferSize;
 
-    for (const auto& segment : *m_buffer)
-        encoder.encodeFixedLengthData(reinterpret_cast<const uint8_t*>(segment->data()), segment->size(), 1);
+    for (const auto& element : *m_buffer)
+        encoder.encodeFixedLengthData(reinterpret_cast<const uint8_t*>(element.segment->data()), element.segment->size(), 1);
 }
 
 } // namespace IPC

diff --git a/Source/WebKit2/WebProcess/Plugins/PluginView.cpp b/Source/WebKit2/WebProcess/Plugins/PluginView.cpp
index 45bdc19..3b6f9d0 100644 (file)
--- a/Source/WebKit2/WebProcess/Plugins/PluginView.cpp
+++ b/Source/WebKit2/WebProcess/Plugins/PluginView.cpp
@@ -1311,8 +1311,8 @@ void PluginView::redeliverManualStream()
 
     // Deliver the data.
     if (m_manualStreamData) {
-        for (const auto& segment : *m_manualStreamData)
-            manualLoadDidReceiveData(segment->data(), segment->size());
+        for (const auto& element : *m_manualStreamData)
+            manualLoadDidReceiveData(element.segment->data(), element.segment->size());
         m_manualStreamData = nullptr;
     }
 

diff --git a/Tools/ChangeLog b/Tools/ChangeLog
index 6cf67d3..c957de1 100644 (file)
--- a/Tools/ChangeLog
+++ b/Tools/ChangeLog
@@ -1,3 +1,15 @@
+2017-05-20  Alex Christensen  <achristensen@webkit.org>
+
+        REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer
+        https://bugs.webkit.org/show_bug.cgi?id=172406
+        <rdar://32109532>
+
+        Reviewed by Brady Eidson.
+
+        * TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp:
+        (TestWebKitAPI::checkBuffer):
+        (TestWebKitAPI::TEST_F):
+
 2017-05-22  Jason Marcell  <jmarcell@apple.com>
 
         Do not enter Subversion-specific logic when parsing Git-based Trac data.

diff --git a/Tools/TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp b/Tools/TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp
index 0a7dd38..8d8ccab 100644 (file)
--- a/Tools/TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp
+++ b/Tools/TestWebKitAPI/Tests/WebCore/SharedBuffer.cpp
@@ -160,4 +160,42 @@ TEST_F(SharedBufferTest, copy)
     ASSERT_EQ(length * 5, clone->size());
 }
 
+static void checkBuffer(const char* buffer, size_t bufferLength, const char* expected)
+{
+    // expected is null terminated, buffer is not.
+    size_t length = strlen(expected);
+    EXPECT_EQ(length, bufferLength);
+    for (size_t i = 0; i < length; ++i)
+        EXPECT_EQ(buffer[i], expected[i]);
+}
+
+TEST_F(SharedBufferTest, getSomeData)
+{
+    Vector<char> s1 = {'a', 'b', 'c', 'd'};
+    Vector<char> s2 = {'e', 'f', 'g', 'h'};
+    Vector<char> s3 = {'i', 'j', 'k', 'l'};
+    
+    auto buffer = SharedBuffer::create();
+    buffer->append(WTFMove(s1));
+    buffer->append(WTFMove(s2));
+    buffer->append(WTFMove(s3));
+    
+    auto abcd = buffer->getSomeData(0);
+    auto gh = buffer->getSomeData(6);
+    auto h = buffer->getSomeData(7);
+    auto ijkl = buffer->getSomeData(8);
+    auto kl = buffer->getSomeData(10);
+    auto abcdefghijkl = buffer->data();
+    auto ghijkl = buffer->getSomeData(6);
+    auto l = buffer->getSomeData(11);
+    checkBuffer(abcd.data(), abcd.size(), "abcd");
+    checkBuffer(gh.data(), gh.size(), "gh");
+    checkBuffer(h.data(), h.size(), "h");
+    checkBuffer(ijkl.data(), ijkl.size(), "ijkl");
+    checkBuffer(kl.data(), kl.size(), "kl");
+    checkBuffer(abcdefghijkl, buffer->size(), "abcdefghijkl");
+    checkBuffer(ghijkl.data(), ghijkl.size(), "ghijkl");
+    checkBuffer(l.data(), l.size(), "l");
+}
+
 }