Changeset 92468 in webkit

Timestamp:

Aug 5, 2011 1:42:56 AM (13 years ago)

Author:

hans@chromium.org

Message:

IndexedDB: Stop using free-lists for database/object store/index ids.
​https://bugs.webkit.org/show_bug.cgi?id=65678

Reviewed by Tony Chang.

Don't use free-lists for database/object store/index ids,
just assign increasing numbers.

It turns out that deleting an object store and creating a new one with
the same id would cause the delete markers from the old object store to
slow down lookups into the new one. Therefore we should generate
a new id every time. Running out of ids (64 bits for databases and
object stores, 32 bits for indices) is not realistic.

Also make functions that generate new ids report errors, and make the
callers of those functions check the return values.

We must still delete free-lists when deleting an object store, and we
must keep the code for encoding/decoding/comparison of free-list keys
since users might have them in their databases.

This is just a performance optimization, so no new tests.

• storage/IDBLevelDBBackingStore.cpp:

(WebCore::getNewDatabaseId):
(WebCore::IDBLevelDBBackingStore::setIDBDatabaseMetaData):
(WebCore::getNewObjectStoreId):
(WebCore::IDBLevelDBBackingStore::createObjectStore):
(WebCore::IDBLevelDBBackingStore::deleteObjectStore):
(WebCore::getNewIndexId):
(WebCore::IDBLevelDBBackingStore::createIndex):
(WebCore::IDBLevelDBBackingStore::deleteIndex):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• storage/IDBLevelDBBackingStore.cpp (modified) (11 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-08-04  Hans Wennborg  <hans@chromium.org>
+
+        IndexedDB: Stop using free-lists for database/object store/index ids.
+        https://bugs.webkit.org/show_bug.cgi?id=65678
+
+        Reviewed by Tony Chang.
+
+        Don't use free-lists for database/object store/index ids,
+        just assign increasing numbers.
+
+        It turns out that deleting an object store and creating a new one with
+        the same id would cause the delete markers from the old object store to
+        slow down lookups into the new one. Therefore we should generate
+        a new id every time. Running out of ids (64 bits for databases and
+        object stores, 32 bits for indices) is not realistic.
+
+        Also make functions that generate new ids report errors, and make the
+        callers of those functions check the return values.
+
+        We must still delete free-lists when deleting an object store, and we
+        must keep the code for encoding/decoding/comparison of free-list keys
+        since users might have them in their databases.
+
+        This is just a performance optimization, so no new tests.
+
+        * storage/IDBLevelDBBackingStore.cpp:
+        (WebCore::getNewDatabaseId):
+        (WebCore::IDBLevelDBBackingStore::setIDBDatabaseMetaData):
+        (WebCore::getNewObjectStoreId):
+        (WebCore::IDBLevelDBBackingStore::createObjectStore):
+        (WebCore::IDBLevelDBBackingStore::deleteObjectStore):
+        (WebCore::getNewIndexId):
+        (WebCore::IDBLevelDBBackingStore::createIndex):
+        (WebCore::IDBLevelDBBackingStore::deleteIndex):
+
 2011-08-05  Roland Steiner  <rolandsteiner@chromium.org>
 

trunk/Source/WebCore/storage/IDBLevelDBBackingStore.cpp

@@ -182 +182 @@
 static int64_t getNewDatabaseId(LevelDBDatabase* db)
 {
-    const Vector<char> freeListStartKey = DatabaseFreeListKey::encode(0);
-    const Vector<char> freeListStopKey = DatabaseFreeListKey::encodeMaxKey();
-
-    OwnPtr<LevelDBIterator> it = db->createIterator();
-    for (it->seek(freeListStartKey); it->isValid() && compareKeys(it->key(), freeListStopKey) < 0; it->next()) {
-        const char *p = it->key().begin();
-        const char *limit = it->key().end();
-
-        DatabaseFreeListKey freeListKey;
-        p = DatabaseFreeListKey::decode(p, limit, &freeListKey);
-        ASSERT(p);
-
-        bool ok = db->remove(it->key());
-        ASSERT_UNUSED(ok, ok);
-
-        return freeListKey.databaseId();
-    }
-
-    // If we got here, there was no free-list.
     int64_t maxDatabaseId = -1;
     if (!getInt(db, MaxDatabaseIdKey::encode(), maxDatabaseId))
@@ -208 +189 @@
 
     int64_t databaseId = maxDatabaseId + 1;
-    bool ok = putInt(db, MaxDatabaseIdKey::encode(), databaseId);
-    ASSERT_UNUSED(ok, ok);
+    if (!putInt(db, MaxDatabaseIdKey::encode(), databaseId))
+        return -1;
 
     return databaseId;
-
 }
 
@@ -219 +199 @@
     if (invalidRowId) {
         rowId = getNewDatabaseId(m_db.get());
+        if (rowId < 0)
+            return false;
 
         const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
@@ -290 +272 @@
 static int64_t getNewObjectStoreId(LevelDBTransaction* transaction, int64_t databaseId)
 {
-    const Vector<char> freeListStartKey = ObjectStoreFreeListKey::encode(databaseId, 0);
-    const Vector<char> freeListStopKey = ObjectStoreFreeListKey::encodeMaxKey(databaseId);
-
-    OwnPtr<LevelDBIterator> it = transaction->createIterator();
-    for (it->seek(freeListStartKey); it->isValid() && compareKeys(it->key(), freeListStopKey) < 0; it->next()) {
-        const char* p = it->key().begin();
-        const char* limit = it->key().end();
-
-        ObjectStoreFreeListKey freeListKey;
-        p = ObjectStoreFreeListKey::decode(p, limit, &freeListKey);
-        ASSERT(p);
-
-        bool ok = transaction->remove(it->key());
-        ASSERT_UNUSED(ok, ok);
-
-        return freeListKey.objectStoreId();
-    }
-
     int64_t maxObjectStoreId = -1;
     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::kMaxObjectStoreId);
@@ -316 +280 @@
 
     int64_t objectStoreId = maxObjectStoreId + 1;
-    bool ok = putInt(transaction, maxObjectStoreIdKey, objectStoreId);
-    ASSERT_UNUSED(ok, ok);
+    if (!putInt(transaction, maxObjectStoreIdKey, objectStoreId))
+        return -1;
 
     return objectStoreId;
@@ -326 +290 @@
     ASSERT(m_currentTransaction);
     int64_t objectStoreId = getNewObjectStoreId(m_currentTransaction.get(), databaseId);
+    if (objectStoreId < 0)
+        return false;
 
     const Vector<char> nameKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 0);
@@ -403 +369 @@
         return; // FIXME: Report error.
 
-    putString(m_currentTransaction.get(), ObjectStoreFreeListKey::encode(databaseId, objectStoreId), "");
     m_currentTransaction->remove(ObjectStoreNamesKey::encode(databaseId, objectStoreName));
 
@@ -642 +607 @@
 static int64_t getNewIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
 {
-    const Vector<char> startKey = IndexFreeListKey::encode(databaseId, objectStoreId, 0);
-    const Vector<char> stopKey = IndexFreeListKey::encodeMaxKey(databaseId, objectStoreId);
-
-    OwnPtr<LevelDBIterator> it = transaction->createIterator();
-    for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
-        const char* p = it->key().begin();
-        const char* limit = it->key().end();
-
-        IndexFreeListKey freeListKey;
-        p = IndexFreeListKey::decode(p, limit, &freeListKey);
-        ASSERT(p);
-
-        bool ok = transaction->remove(it->key());
-        ASSERT_UNUSED(ok, ok);
-
-        ASSERT(freeListKey.indexId() >= kMinimumIndexId);
-        return freeListKey.indexId();
-    }
-
     int64_t maxIndexId = -1;
     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 5);
@@ -669 +615 @@
 
     int64_t indexId = maxIndexId + 1;
-    bool ok = putInt(transaction, maxIndexIdKey, indexId);
-    if (!ok)
-        return false;
+    if (!putInt(transaction, maxIndexIdKey, indexId))
+        return -1;
 
     return indexId;
@@ -680 +625 @@
     ASSERT(m_currentTransaction);
     indexId = getNewIndexId(m_currentTransaction.get(), databaseId, objectStoreId);
+    if (indexId < 0)
+        return false;
 
     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
@@ -731 +678 @@
 
     if (!deleteRange(m_currentTransaction.get(), indexDataStart, indexDataEnd)) {
-        LOG_ERROR("Internal Indexed DB error.");
-        return;
-    }
-
-    const Vector<char> freeListKey = IndexFreeListKey::encode(databaseId, objectStoreId, indexId);
-    if (!putInt(m_currentTransaction.get(), freeListKey, 0)) {
         LOG_ERROR("Internal Indexed DB error.");
         return;