IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
authorbeidson@apple.com <beidson@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 16 Nov 2016 00:25:28 +0000 (00:25 +0000)
committerbeidson@apple.com <beidson@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 16 Nov 2016 00:25:28 +0000 (00:25 +0000)
https://bugs.webkit.org/show_bug.cgi?id=164754

Reviewed by Alex Christensen.

Source/WebCore:

No new tests (Covered by *all* existing tests, and unskips a previously-too-slow test)

The new serialization format is straight forward enough to get back with minimal documentation
in a comment with the code itself being the rest of the documentation.

It handles all current IDB key types and leaves room for future key types.

* Modules/indexeddb/IDBKeyData.cpp:
(WebCore::IDBKeyData::setBinaryValue):
* Modules/indexeddb/IDBKeyData.h:
(WebCore::IDBKeyData::binary):

* Modules/indexeddb/server/IDBSerialization.cpp:
(WebCore::serializedTypeForKeyType):
(WebCore::writeLittleEndian):
(WebCore::readLittleEndian):
(WebCore::writeDouble):
(WebCore::readDouble):
(WebCore::encodeKey):
(WebCore::serializeIDBKeyData):
(WebCore::decodeKey):
(WebCore::deserializeIDBKeyData):
* Modules/indexeddb/server/IDBSerialization.h:

* Modules/indexeddb/server/SQLiteIDBBackingStore.cpp:
(WebCore::IDBServer::SQLiteIDBBackingStore::uncheckedPutIndexKey): Verify that Type == Invalid
  keys don't get into the database. This was happening before and the previous serialization
  supported it, but there's clearly no point in supporting it with the new serialization.

LayoutTests:

* TestExpectations: Unskip a test that passes even in debug builds, and re-classify
  a test that used to be too-slow everywhere to be too-slow only in debug builds.

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

LayoutTests/ChangeLog
LayoutTests/TestExpectations
Source/WebCore/ChangeLog
Source/WebCore/Modules/indexeddb/IDBKeyData.cpp
Source/WebCore/Modules/indexeddb/IDBKeyData.h
Source/WebCore/Modules/indexeddb/server/IDBSerialization.cpp
Source/WebCore/Modules/indexeddb/server/SQLiteIDBBackingStore.cpp

index a34a4d4..8bab132 100644 (file)
@@ -1,3 +1,13 @@
+2016-11-15  Brady Eidson  <beidson@apple.com>
+
+        IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
+        https://bugs.webkit.org/show_bug.cgi?id=164754
+
+        Reviewed by Alex Christensen.
+
+        * TestExpectations: Unskip a test that passes even in debug builds, and re-classify
+          a test that used to be too-slow everywhere to be too-slow only in debug builds.
+
 2016-11-15  Simon Fraser  <simon.fraser@apple.com>
 
         UIScriptController: script with no async tasks fails if an earlier script registered a callback
index 97eefd9..b6aea0c 100644 (file)
@@ -848,9 +848,8 @@ storage/indexeddb/deletedatabase-delayed-by-versionchange.html [ Skip ]
 # It's unclear if we need to continue supporting this.
 storage/indexeddb/properties-disabled-at-runtime.html [ Failure ]
 
-# Completes with passing results, but too slowly for our test timeouts.
-imported/w3c/web-platform-tests/IndexedDB/idbindex-multientry-big.htm [ Failure ]
-imported/w3c/web-platform-tests/IndexedDB/idbcursor_iterating.htm [ Failure ]
+# In debug builds, runs too slowly for the test timeout.
+[ Debug ] imported/w3c/web-platform-tests/IndexedDB/idbindex-multientry-big.htm [ Failure ]
 
 # SQLite backend tests that timeout
 storage/indexeddb/modern/transaction-scheduler-1.html [ Skip ]
index 08d9988..f8d5860 100644 (file)
@@ -1,3 +1,39 @@
+2016-11-15  Brady Eidson  <beidson@apple.com>
+
+        IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
+        https://bugs.webkit.org/show_bug.cgi?id=164754
+
+        Reviewed by Alex Christensen.
+
+        No new tests (Covered by *all* existing tests, and unskips a previously-too-slow test)
+
+        The new serialization format is straight forward enough to get back with minimal documentation
+        in a comment with the code itself being the rest of the documentation.
+        
+        It handles all current IDB key types and leaves room for future key types.
+
+        * Modules/indexeddb/IDBKeyData.cpp:
+        (WebCore::IDBKeyData::setBinaryValue):
+        * Modules/indexeddb/IDBKeyData.h:
+        (WebCore::IDBKeyData::binary):
+        
+        * Modules/indexeddb/server/IDBSerialization.cpp:
+        (WebCore::serializedTypeForKeyType):
+        (WebCore::writeLittleEndian):
+        (WebCore::readLittleEndian):
+        (WebCore::writeDouble):
+        (WebCore::readDouble):
+        (WebCore::encodeKey):
+        (WebCore::serializeIDBKeyData):
+        (WebCore::decodeKey):
+        (WebCore::deserializeIDBKeyData):
+        * Modules/indexeddb/server/IDBSerialization.h:
+        
+        * Modules/indexeddb/server/SQLiteIDBBackingStore.cpp:
+        (WebCore::IDBServer::SQLiteIDBBackingStore::uncheckedPutIndexKey): Verify that Type == Invalid 
+          keys don't get into the database. This was happening before and the previous serialization
+          supported it, but there's clearly no point in supporting it with the new serialization.
+
 2016-11-15  Brent Fulgham  <bfulgham@apple.com>
 
         Ensure sufficient buffer for worst-case URL encoding
index d8d5395..3d5abf3 100644 (file)
@@ -386,6 +386,14 @@ void IDBKeyData::setArrayValue(const Vector<IDBKeyData>& value)
     m_isNull = false;
 }
 
+void IDBKeyData::setBinaryValue(const ThreadSafeDataBuffer& value)
+{
+    *this = IDBKeyData();
+    m_value = value;
+    m_type = KeyType::Binary;
+    m_isNull = false;
+}
+
 void IDBKeyData::setStringValue(const String& value)
 {
     *this = IDBKeyData();
index 0bafd54..98f0b73 100644 (file)
@@ -79,6 +79,7 @@ public:
     WEBCORE_EXPORT int compare(const IDBKeyData& other) const;
 
     void setArrayValue(const Vector<IDBKeyData>&);
+    void setBinaryValue(const ThreadSafeDataBuffer&);
     void setStringValue(const String&);
     void setDateValue(double);
     WEBCORE_EXPORT void setNumberValue(double);
@@ -172,6 +173,12 @@ public:
         return WTF::get<double>(m_value);
     }
 
+    const ThreadSafeDataBuffer& binary() const
+    {
+        ASSERT(m_type == KeyType::Binary);
+        return WTF::get<ThreadSafeDataBuffer>(m_value);
+    }
+
     const Vector<IDBKeyData>& array() const
     {
         ASSERT(m_type == KeyType::Array);
index 580e351..1a310b9 100644 (file)
@@ -94,11 +94,292 @@ bool deserializeIDBKeyPath(const uint8_t* data, size_t size, Optional<IDBKeyPath
     return true;
 }
 
+// This is the magic character that begins serialized PropertyLists, and tells us whether
+// the key we're looking at is an old-style key.
+static const uint8_t LegacySerializedKeyVersion = 'b';
+
+// FIXME: Linux ports uses KeyedEncoderGlib for their IDBKeys.
+// When a Glib maintainer comes along to enable the new serialization they'll need to
+// denote a Glib magic character here.
+
+/*
+The IDBKeyData serialization format is as follows:
+[1 byte version header][Key Buffer]
+
+The Key Buffer serialization format is as follows:
+[1 byte key type][Type specific data]
+
+Type specific serialization formats are as follows for each of the types:
+Min:
+[0 bytes]
+
+Number:
+[8 bytes representing a double encoded in little endian]
+
+Date:
+[8 bytes representing a double encoded in little endian]
+
+String:
+[4 bytes representing string "length" in little endian]["length" number of 2-byte pairs representing ECMAScript 16-bit code units]
+
+Binary:
+[8 bytes representing the "size" of the binary blob]["size" bytes]
+
+Array:
+[8 bytes representing the "length" of the key array]["length" individual Key Buffer entries]
+
+Max:
+[0 bytes]
+*/
+
+// FIXME: If the GLib magic character ends up being 0x00, we should consider changing
+// this 0x00 so we can support Glib keyed encoding, also.
+static const uint8_t SIDBKeyVersion = 0x00;
+enum class SIDBKeyType : uint8_t {
+    Min = 0x00,
+    Number = 0x20,
+    Date = 0x40,
+    String = 0x60,
+    Binary = 0x80,
+    Array = 0xA0,
+    Max = 0xFF,
+};
+
+static SIDBKeyType serializedTypeForKeyType(IndexedDB::KeyType type)
+{
+    switch (type) {
+    case IndexedDB::KeyType::Min:
+        return SIDBKeyType::Min;
+    case IndexedDB::KeyType::Number:
+        return SIDBKeyType::Number;
+    case IndexedDB::KeyType::Date:
+        return SIDBKeyType::Date;
+    case IndexedDB::KeyType::String:
+        return SIDBKeyType::String;
+    case IndexedDB::KeyType::Binary:
+        return SIDBKeyType::Binary;
+    case IndexedDB::KeyType::Array:
+        return SIDBKeyType::Array;
+    case IndexedDB::KeyType::Max:
+        return SIDBKeyType::Max;
+    case IndexedDB::KeyType::Invalid:
+        RELEASE_ASSERT_NOT_REACHED();
+    };
+
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+#if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) || CPU(NEEDS_ALIGNED_ACCESS)
+template <typename T> static void writeLittleEndian(Vector<char>& buffer, T value)
+{
+    for (unsigned i = 0; i < sizeof(T); i++) {
+        buffer.append(value & 0xFF);
+        value >>= 8;
+    }
+}
+
+template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
+{
+    if (ptr > end - sizeof(value))
+        return false;
+
+    value = 0;
+    for (size_t i = 0; i < sizeof(T); i++)
+        value += ((T)*ptr++) << (i * 8);
+    return true;
+}
+#else
+template <typename T> static void writeLittleEndian(Vector<char>& buffer, T value)
+{
+    buffer.append(reinterpret_cast<uint8_t*>(&value), sizeof(value));
+}
+
+template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
+{
+    if (ptr > end - sizeof(value))
+        return false;
+
+    value = *reinterpret_cast<const T*>(ptr);
+    ptr += sizeof(T);
+
+    return true;
+}
+#endif
+
+static void writeDouble(Vector<char>& data, double d)
+{
+    writeLittleEndian(data, *reinterpret_cast<uint64_t*>(&d));
+}
+
+static bool readDouble(const uint8_t*& data, const uint8_t* end, double& d)
+{
+    return readLittleEndian(data, end, *reinterpret_cast<uint64_t*>(&d));
+}
+
+static void encodeKey(Vector<char>& data, const IDBKeyData& key)
+{
+    SIDBKeyType type = serializedTypeForKeyType(key.type());
+    data.append(static_cast<char>(type));
+
+    switch (type) {
+    case SIDBKeyType::Number:
+        writeDouble(data, key.number());
+        break;
+    case SIDBKeyType::Date:
+        writeDouble(data, key.date());
+        break;
+    case SIDBKeyType::String: {
+        auto string = key.string();
+        uint32_t length = string.length();
+        writeLittleEndian(data, length);
+
+        for (size_t i = 0; i < length; ++i)
+            writeLittleEndian(data, string[i]);
+
+        break;
+    }
+    case SIDBKeyType::Binary: {
+        auto& buffer = key.binary();
+        uint64_t size = buffer.size();
+        writeLittleEndian(data, size);
+
+        auto* bufferData = buffer.data();
+        ASSERT(bufferData || !size);
+        if (bufferData)
+            data.append(bufferData->data(), bufferData->size());
+
+        break;
+    }
+    case SIDBKeyType::Array: {
+        auto& array = key.array();
+        uint64_t size = array.size();
+        writeLittleEndian(data, size);
+        for (auto& key : array)
+            encodeKey(data, key);
+
+        break;
+    }
+    case SIDBKeyType::Min:
+    case SIDBKeyType::Max:
+        break;
+    }
+}
+
 RefPtr<SharedBuffer> serializeIDBKeyData(const IDBKeyData& key)
 {
+#if USE(CF)
+    Vector<char> data;
+    data.append(SIDBKeyVersion);
+
+    encodeKey(data, key);
+    return SharedBuffer::adoptVector(data);
+#else
     auto encoder = KeyedEncoder::encoder();
     key.encode(*encoder);
     return encoder->finishEncoding();
+#endif
+
+}
+
+static bool decodeKey(const uint8_t*& data, const uint8_t* end, IDBKeyData& result)
+{
+    if (!data || data >= end)
+        return false;
+
+    SIDBKeyType type = static_cast<SIDBKeyType>(data++[0]);
+    switch (type) {
+    case SIDBKeyType::Min:
+        result = IDBKeyData::minimum();
+        return true;
+    case SIDBKeyType::Max:
+        result = IDBKeyData::maximum();
+        return true;
+    case SIDBKeyType::Number: {
+        double d;
+        if (!readDouble(data, end, d))
+            return false;
+
+        result.setNumberValue(d);
+        return true;
+    }
+    case SIDBKeyType::Date: {
+        double d;
+        if (!readDouble(data, end, d))
+            return false;
+
+        result.setDateValue(d);
+        return true;
+    }
+    case SIDBKeyType::String: {
+        uint32_t length;
+        if (!readLittleEndian(data, end, length))
+            return false;
+
+        if (static_cast<uint64_t>(end - data) < length * 2)
+            return false;
+
+        Vector<UChar> buffer;
+        buffer.reserveInitialCapacity(length);
+        for (size_t i = 0; i < length; i++) {
+            uint16_t ch;
+            if (!readLittleEndian(data, end, ch))
+                return false;
+            buffer.uncheckedAppend(ch);
+        }
+
+        result.setStringValue(String::adopt(WTFMove(buffer)));
+
+        return true;
+    }
+    case SIDBKeyType::Binary: {
+        uint64_t size64;
+        if (!readLittleEndian(data, end, size64))
+            return false;
+
+        if (static_cast<uint64_t>(end - data) < size64)
+            return false;
+
+        if (size64 > std::numeric_limits<size_t>::max())
+            return false;
+
+        size_t size = static_cast<size_t>(size64);
+        Vector<uint8_t> dataVector;
+
+        dataVector.append(data, size);
+        data += size;
+
+        result.setBinaryValue(ThreadSafeDataBuffer::adoptVector(dataVector));
+        return true;
+    }
+    case SIDBKeyType::Array: {
+        uint64_t size64;
+        if (!readLittleEndian(data, end, size64))
+            return false;
+
+        if (size64 > std::numeric_limits<size_t>::max())
+            return false;
+
+        size_t size = static_cast<size_t>(size64);
+        Vector<IDBKeyData> array;
+        array.reserveInitialCapacity(size);
+
+        for (size_t i = 0; i < size; ++i) {
+            IDBKeyData keyData;
+            if (!decodeKey(data, end, keyData))
+                return false;
+
+            ASSERT(keyData.isValid());
+            array.uncheckedAppend(WTFMove(keyData));
+        }
+
+        result.setArrayValue(array);
+
+        return true;
+    }
+    default:
+        LOG_ERROR("decodeKey encountered unexpected type: %i", (int)type);
+        return false;
+    }
 }
 
 bool deserializeIDBKeyData(const uint8_t* data, size_t size, IDBKeyData& result)
@@ -106,8 +387,29 @@ bool deserializeIDBKeyData(const uint8_t* data, size_t size, IDBKeyData& result)
     if (!data || !size)
         return false;
 
+#if USE(CF)
+    if (data[0] == LegacySerializedKeyVersion) {
+        auto decoder = KeyedDecoder::decoder(data, size);
+        return IDBKeyData::decode(*decoder, result);
+    }
+
+    // Verify this is a SerializedIDBKey version we understand.
+    const uint8_t* current = data;
+    const uint8_t* end = data + size;
+    if (current++[0] != SIDBKeyVersion)
+        return false;
+
+    if (decodeKey(current, end, result)) {
+        // Even if we successfully decoded a key, the deserialize is only successful
+        // if we actually consumed all input data.
+        return current == end;
+    }
+
+    return false;
+#else
     auto decoder = KeyedDecoder::decoder(data, size);
     return IDBKeyData::decode(*decoder, result);
+#endif
 }
 
 } // namespace WebCore
index 3df8352..a2cccad 100644 (file)
@@ -1183,6 +1183,8 @@ IDBError SQLiteIDBBackingStore::uncheckedPutIndexKey(const IDBIndexInfo& info, c
         bool hasRecord;
         IDBError error;
         for (auto& indexKey : indexKeys) {
+            if (!indexKey.isValid())
+                continue;
             error = uncheckedHasIndexRecord(info, indexKey, hasRecord);
             if (!error.isNull())
                 return error;
@@ -1192,6 +1194,8 @@ IDBError SQLiteIDBBackingStore::uncheckedPutIndexKey(const IDBIndexInfo& info, c
     }
 
     for (auto& indexKey : indexKeys) {
+        if (!indexKey.isValid())
+            continue;
         auto error = uncheckedPutIndexRecord(info.objectStoreIdentifier(), info.identifier(), key, indexKey);
         if (!error.isNull()) {
             LOG_ERROR("Unable to put index record for newly created index");