Changeset 208771 in webkit


Ignore:
Timestamp:
Nov 15, 2016, 4:25:28 PM (9 years ago)
Author:
beidson@apple.com
Message:

IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
​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.
Location:
trunk
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r208770 r208771  
     12016-11-15  Brady Eidson  <beidson@apple.com>
     2
     3        IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
     4        https://bugs.webkit.org/show_bug.cgi?id=164754
     5
     6        Reviewed by Alex Christensen.
     7
     8        * TestExpectations: Unskip a test that passes even in debug builds, and re-classify
     9          a test that used to be too-slow everywhere to be too-slow only in debug builds.
     10
    1112016-11-15  Simon Fraser  <simon.fraser@apple.com>
    212

  • trunk/LayoutTests/TestExpectations

    r208662 r208771  
    849849storage/indexeddb/properties-disabled-at-runtime.html [ Failure ]
    850850
    851 # Completes with passing results, but too slowly for our test timeouts.
    852 imported/w3c/web-platform-tests/IndexedDB/idbindex-multientry-big.htm [ Failure ]
    853 imported/w3c/web-platform-tests/IndexedDB/idbcursor_iterating.htm [ Failure ]
     851# In debug builds, runs too slowly for the test timeout.
     852[ Debug ] imported/w3c/web-platform-tests/IndexedDB/idbindex-multientry-big.htm [ Failure ]
    854853
    855854# SQLite backend tests that timeout

  • trunk/Source/WebCore/ChangeLog

    r208765 r208771  
     12016-11-15  Brady Eidson  <beidson@apple.com>
     2
     3        IndexedDB 2.0: Key collation during SQLite lookups is insanely slow.
     4        https://bugs.webkit.org/show_bug.cgi?id=164754
     5
     6        Reviewed by Alex Christensen.
     7
     8        No new tests (Covered by *all* existing tests, and unskips a previously-too-slow test)
     9
     10        The new serialization format is straight forward enough to get back with minimal documentation
     11        in a comment with the code itself being the rest of the documentation.
     12       
     13        It handles all current IDB key types and leaves room for future key types.
     14
     15        * Modules/indexeddb/IDBKeyData.cpp:
     16        (WebCore::IDBKeyData::setBinaryValue):
     17        * Modules/indexeddb/IDBKeyData.h:
     18        (WebCore::IDBKeyData::binary):
     19       
     20        * Modules/indexeddb/server/IDBSerialization.cpp:
     21        (WebCore::serializedTypeForKeyType):
     22        (WebCore::writeLittleEndian):
     23        (WebCore::readLittleEndian):
     24        (WebCore::writeDouble):
     25        (WebCore::readDouble):
     26        (WebCore::encodeKey):
     27        (WebCore::serializeIDBKeyData):
     28        (WebCore::decodeKey):
     29        (WebCore::deserializeIDBKeyData):
     30        * Modules/indexeddb/server/IDBSerialization.h:
     31       
     32        * Modules/indexeddb/server/SQLiteIDBBackingStore.cpp:
     33        (WebCore::IDBServer::SQLiteIDBBackingStore::uncheckedPutIndexKey): Verify that Type == Invalid
     34          keys don't get into the database. This was happening before and the previous serialization
     35          supported it, but there's clearly no point in supporting it with the new serialization.
     36
    1372016-11-15  Brent Fulgham  <bfulgham@apple.com>
    238

  • trunk/Source/WebCore/Modules/indexeddb/IDBKeyData.cpp

    r208349 r208771  
    387387}
    388388
     389void IDBKeyData::setBinaryValue(const ThreadSafeDataBuffer& value)
     390{
     391    *this = IDBKeyData();
     392    m_value = value;
     393    m_type = KeyType::Binary;
     394    m_isNull = false;
     395}
     396
    389397void IDBKeyData::setStringValue(const String& value)
    390398{

  • trunk/Source/WebCore/Modules/indexeddb/IDBKeyData.h

    r208500 r208771  
    8080
    8181    void setArrayValue(const Vector<IDBKeyData>&);
     82    void setBinaryValue(const ThreadSafeDataBuffer&);
    8283    void setStringValue(const String&);
    8384    void setDateValue(double);
    … …  
    173174    }
    174175
     176    const ThreadSafeDataBuffer& binary() const
     177    {
     178        ASSERT(m_type == KeyType::Binary);
     179        return WTF::get<ThreadSafeDataBuffer>(m_value);
     180    }
     181
    175182    const Vector<IDBKeyData>& array() const
    176183    {

  • trunk/Source/WebCore/Modules/indexeddb/server/IDBSerialization.cpp

    r207931 r208771  
    9595}
    9696
     97// This is the magic character that begins serialized PropertyLists, and tells us whether
     98// the key we're looking at is an old-style key.
     99static const uint8_t LegacySerializedKeyVersion = 'b';
     100
     101// FIXME: Linux ports uses KeyedEncoderGlib for their IDBKeys.
     102// When a Glib maintainer comes along to enable the new serialization they'll need to
     103// denote a Glib magic character here.
     104
     105/*
     106The IDBKeyData serialization format is as follows:
     107[1 byte version header][Key Buffer]
     108
     109The Key Buffer serialization format is as follows:
     110[1 byte key type][Type specific data]
     111
     112Type specific serialization formats are as follows for each of the types:
     113Min:
     114[0 bytes]
     115
     116Number:
     117[8 bytes representing a double encoded in little endian]
     118
     119Date:
     120[8 bytes representing a double encoded in little endian]
     121
     122String:
     123[4 bytes representing string "length" in little endian]["length" number of 2-byte pairs representing ECMAScript 16-bit code units]
     124
     125Binary:
     126[8 bytes representing the "size" of the binary blob]["size" bytes]
     127
     128Array:
     129[8 bytes representing the "length" of the key array]["length" individual Key Buffer entries]
     130
     131Max:
     132[0 bytes]
     133*/
     134
     135// FIXME: If the GLib magic character ends up being 0x00, we should consider changing
     136// this 0x00 so we can support Glib keyed encoding, also.
     137static const uint8_t SIDBKeyVersion = 0x00;
     138enum class SIDBKeyType : uint8_t {
     139    Min = 0x00,
     140    Number = 0x20,
     141    Date = 0x40,
     142    String = 0x60,
     143    Binary = 0x80,
     144    Array = 0xA0,
     145    Max = 0xFF,
     146};
     147
     148static SIDBKeyType serializedTypeForKeyType(IndexedDB::KeyType type)
     149{
     150    switch (type) {
     151    case IndexedDB::KeyType::Min:
     152        return SIDBKeyType::Min;
     153    case IndexedDB::KeyType::Number:
     154        return SIDBKeyType::Number;
     155    case IndexedDB::KeyType::Date:
     156        return SIDBKeyType::Date;
     157    case IndexedDB::KeyType::String:
     158        return SIDBKeyType::String;
     159    case IndexedDB::KeyType::Binary:
     160        return SIDBKeyType::Binary;
     161    case IndexedDB::KeyType::Array:
     162        return SIDBKeyType::Array;
     163    case IndexedDB::KeyType::Max:
     164        return SIDBKeyType::Max;
     165    case IndexedDB::KeyType::Invalid:
     166        RELEASE_ASSERT_NOT_REACHED();
     167    };
     168
     169    RELEASE_ASSERT_NOT_REACHED();
     170}
     171
     172#if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) || CPU(NEEDS_ALIGNED_ACCESS)
     173template <typename T> static void writeLittleEndian(Vector<char>& buffer, T value)
     174{
     175    for (unsigned i = 0; i < sizeof(T); i++) {
     176        buffer.append(value & 0xFF);
     177        value >>= 8;
     178    }
     179}
     180
     181template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
     182{
     183    if (ptr > end - sizeof(value))
     184        return false;
     185
     186    value = 0;
     187    for (size_t i = 0; i < sizeof(T); i++)
     188        value += ((T)*ptr++) << (i * 8);
     189    return true;
     190}
     191#else
     192template <typename T> static void writeLittleEndian(Vector<char>& buffer, T value)
     193{
     194    buffer.append(reinterpret_cast<uint8_t*>(&value), sizeof(value));
     195}
     196
     197template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
     198{
     199    if (ptr > end - sizeof(value))
     200        return false;
     201
     202    value = *reinterpret_cast<const T*>(ptr);
     203    ptr += sizeof(T);
     204
     205    return true;
     206}
     207#endif
     208
     209static void writeDouble(Vector<char>& data, double d)
     210{
     211    writeLittleEndian(data, *reinterpret_cast<uint64_t*>(&d));
     212}
     213
     214static bool readDouble(const uint8_t*& data, const uint8_t* end, double& d)
     215{
     216    return readLittleEndian(data, end, *reinterpret_cast<uint64_t*>(&d));
     217}
     218
     219static void encodeKey(Vector<char>& data, const IDBKeyData& key)
     220{
     221    SIDBKeyType type = serializedTypeForKeyType(key.type());
     222    data.append(static_cast<char>(type));
     223
     224    switch (type) {
     225    case SIDBKeyType::Number:
     226        writeDouble(data, key.number());
     227        break;
     228    case SIDBKeyType::Date:
     229        writeDouble(data, key.date());
     230        break;
     231    case SIDBKeyType::String: {
     232        auto string = key.string();
     233        uint32_t length = string.length();
     234        writeLittleEndian(data, length);
     235
     236        for (size_t i = 0; i < length; ++i)
     237            writeLittleEndian(data, string[i]);
     238
     239        break;
     240    }
     241    case SIDBKeyType::Binary: {
     242        auto& buffer = key.binary();
     243        uint64_t size = buffer.size();
     244        writeLittleEndian(data, size);
     245
     246        auto* bufferData = buffer.data();
     247        ASSERT(bufferData || !size);
     248        if (bufferData)
     249            data.append(bufferData->data(), bufferData->size());
     250
     251        break;
     252    }
     253    case SIDBKeyType::Array: {
     254        auto& array = key.array();
     255        uint64_t size = array.size();
     256        writeLittleEndian(data, size);
     257        for (auto& key : array)
     258            encodeKey(data, key);
     259
     260        break;
     261    }
     262    case SIDBKeyType::Min:
     263    case SIDBKeyType::Max:
     264        break;
     265    }
     266}
     267
    97268RefPtr<SharedBuffer> serializeIDBKeyData(const IDBKeyData& key)
    98269{
     270#if USE(CF)
     271    Vector<char> data;
     272    data.append(SIDBKeyVersion);
     273
     274    encodeKey(data, key);
     275    return SharedBuffer::adoptVector(data);
     276#else
    99277    auto encoder = KeyedEncoder::encoder();
    100278    key.encode(*encoder);
    101279    return encoder->finishEncoding();
     280#endif
     281
     282}
     283
     284static bool decodeKey(const uint8_t*& data, const uint8_t* end, IDBKeyData& result)
     285{
     286    if (!data || data >= end)
     287        return false;
     288
     289    SIDBKeyType type = static_cast<SIDBKeyType>(data++[0]);
     290    switch (type) {
     291    case SIDBKeyType::Min:
     292        result = IDBKeyData::minimum();
     293        return true;
     294    case SIDBKeyType::Max:
     295        result = IDBKeyData::maximum();
     296        return true;
     297    case SIDBKeyType::Number: {
     298        double d;
     299        if (!readDouble(data, end, d))
     300            return false;
     301
     302        result.setNumberValue(d);
     303        return true;
     304    }
     305    case SIDBKeyType::Date: {
     306        double d;
     307        if (!readDouble(data, end, d))
     308            return false;
     309
     310        result.setDateValue(d);
     311        return true;
     312    }
     313    case SIDBKeyType::String: {
     314        uint32_t length;
     315        if (!readLittleEndian(data, end, length))
     316            return false;
     317
     318        if (static_cast<uint64_t>(end - data) < length * 2)
     319            return false;
     320
     321        Vector<UChar> buffer;
     322        buffer.reserveInitialCapacity(length);
     323        for (size_t i = 0; i < length; i++) {
     324            uint16_t ch;
     325            if (!readLittleEndian(data, end, ch))
     326                return false;
     327            buffer.uncheckedAppend(ch);
     328        }
     329
     330        result.setStringValue(String::adopt(WTFMove(buffer)));
     331
     332        return true;
     333    }
     334    case SIDBKeyType::Binary: {
     335        uint64_t size64;
     336        if (!readLittleEndian(data, end, size64))
     337            return false;
     338
     339        if (static_cast<uint64_t>(end - data) < size64)
     340            return false;
     341
     342        if (size64 > std::numeric_limits<size_t>::max())
     343            return false;
     344
     345        size_t size = static_cast<size_t>(size64);
     346        Vector<uint8_t> dataVector;
     347
     348        dataVector.append(data, size);
     349        data += size;
     350
     351        result.setBinaryValue(ThreadSafeDataBuffer::adoptVector(dataVector));
     352        return true;
     353    }
     354    case SIDBKeyType::Array: {
     355        uint64_t size64;
     356        if (!readLittleEndian(data, end, size64))
     357            return false;
     358
     359        if (size64 > std::numeric_limits<size_t>::max())
     360            return false;
     361
     362        size_t size = static_cast<size_t>(size64);
     363        Vector<IDBKeyData> array;
     364        array.reserveInitialCapacity(size);
     365
     366        for (size_t i = 0; i < size; ++i) {
     367            IDBKeyData keyData;
     368            if (!decodeKey(data, end, keyData))
     369                return false;
     370
     371            ASSERT(keyData.isValid());
     372            array.uncheckedAppend(WTFMove(keyData));
     373        }
     374
     375        result.setArrayValue(array);
     376
     377        return true;
     378    }
     379    default:
     380        LOG_ERROR("decodeKey encountered unexpected type: %i", (int)type);
     381        return false;
     382    }
    102383}
    103384
    … …  
    107388        return false;
    108389
     390#if USE(CF)
     391    if (data[0] == LegacySerializedKeyVersion) {
     392        auto decoder = KeyedDecoder::decoder(data, size);
     393        return IDBKeyData::decode(*decoder, result);
     394    }
     395
     396    // Verify this is a SerializedIDBKey version we understand.
     397    const uint8_t* current = data;
     398    const uint8_t* end = data + size;
     399    if (current++[0] != SIDBKeyVersion)
     400        return false;
     401
     402    if (decodeKey(current, end, result)) {
     403        // Even if we successfully decoded a key, the deserialize is only successful
     404        // if we actually consumed all input data.
     405        return current == end;
     406    }
     407
     408    return false;
     409#else
    109410    auto decoder = KeyedDecoder::decoder(data, size);
    110411    return IDBKeyData::decode(*decoder, result);
     412#endif
    111413}
    112414

  • trunk/Source/WebCore/Modules/indexeddb/server/SQLiteIDBBackingStore.cpp

    r208500 r208771  
    11841184        IDBError error;
    11851185        for (auto& indexKey : indexKeys) {
     1186            if (!indexKey.isValid())
     1187                continue;
    11861188            error = uncheckedHasIndexRecord(info, indexKey, hasRecord);
    11871189            if (!error.isNull())
    … …  
    11931195
    11941196    for (auto& indexKey : indexKeys) {
     1197        if (!indexKey.isValid())
     1198            continue;
    11951199        auto error = uncheckedPutIndexRecord(info.objectStoreIdentifier(), info.identifier(), key, indexKey);
    11961200        if (!error.isNull()) {
Note: See TracChangeset for help on using the changeset viewer.