| OLD | NEW |
|---|
| 1 <!doctype html> | 1 <!doctype html> |
| 2 <meta charset="utf-8"> | 2 <meta charset="utf-8"> |
| 3 <meta name="timeout" content="long"> | 3 <meta name="timeout" content="long"> |
| 4 <title>IndexedDB: Interleaved iteration of multiple cursors</title> | 4 <title>IndexedDB: Interleaved iteration of multiple cursors over disjoint data r
anges</title> |
| 5 <link rel="author" href="pwnall@chromium.org" title="Victor Costan"> | 5 <link rel="author" href="pwnall@chromium.org" title="Victor Costan"> |
| 6 <script src="/resources/testharness.js"></script> | 6 <script src="/resources/testharness.js"></script> |
| 7 <script src="/resources/testharnessreport.js"></script> | 7 <script src="/resources/testharnessreport.js"></script> |
| 8 <script src="support-promises.js"></script> | 8 <script src="support-promises.js"></script> |
| 9 <script src="interleaved-cursors-support.js"></script> |
| 9 <script> | 10 <script> |
| 11 'use strict'; |
| 12 |
| 10 // Number of objects that each iterator goes over. | 13 // Number of objects that each iterator goes over. |
| 11 const itemCount = 10; | 14 const itemCount = 8; |
| 12 | 15 |
| 13 // Ratio of small objects to large objects. | 16 // Ratio of small objects to large objects. |
| 14 const largeObjectRatio = 5; | 17 const largeObjectRatio = 3; |
| 15 | |
| 16 // Size of large objects. This should exceed the size of a block in the storage | |
| 17 // method underlying the browser's IndexedDB implementation. For example, this | |
| 18 // needs to exceed the LevelDB block size on Chrome, and the SQLite block size | |
| 19 // on Firefox. | |
| 20 const largeObjectSize = 48 * 1024; | |
| 21 | 18 |
| 22 function objectKey(cursorIndex, itemIndex) { | 19 function objectKey(cursorIndex, itemIndex) { |
| 23 return `${cursorIndex}-key-${itemIndex}`; | 20 const cursorString = cursorIndex.toString().padStart(5, '0'); |
| 21 const itemString = itemIndex.toString().padStart(5, '0'); |
| 22 return `${cursorString}-key-${itemString}`; |
| 24 } | 23 } |
| 25 | 24 |
| 26 function objectValue(cursorIndex, itemIndex) { | 25 function objectValue(cursorIndex, itemIndex) { |
| 27 if ((cursorIndex * itemCount + itemIndex) % largeObjectRatio === 0) { | 26 if ((cursorIndex * itemCount + itemIndex) % largeObjectRatio === 0) |
| 28 // We use a typed array (as opposed to a string) because IndexedDB | 27 return largeObjectValue(cursorIndex, itemIndex); |
| 29 // implementations may serialize strings using UTF-8 or UTF-16, yielding | |
| 30 // larger IndexedDB entries than we'd expect. It's very unlikely that an | |
| 31 // IndexedDB implementation would use anything other than the raw buffer to | |
| 32 // serialize a typed array. | |
| 33 const buffer = new Uint8Array(largeObjectSize); | |
| 34 | |
| 35 // Some IndexedDB implementations, like LevelDB, compress their data blocks | |
| 36 // before storing them to disk. We use a simple 32-bit xorshift PRNG, which | |
| 37 // should be sufficient to foil any fast generic-purpose compression scheme. | |
| 38 | |
| 39 // 32-bit xorshift - the seed can't be zero | |
| 40 let state = 1000 + (cursorIndex * itemCount + itemIndex); | |
| 41 | |
| 42 for (let i = 0; i < largeObjectSize; ++i) { | |
| 43 state ^= state << 13; | |
| 44 state ^= state >> 17; | |
| 45 state ^= state << 5; | |
| 46 buffer[i] = state & 0xff; | |
| 47 } | |
| 48 | |
| 49 return buffer; | |
| 50 } | |
| 51 return [cursorIndex, 'small', itemIndex]; | 28 return [cursorIndex, 'small', itemIndex]; |
| 52 } | 29 } |
| 53 | 30 |
| 54 // Writes the objects to be read by one cursor. Returns a promise that resolves | |
| 55 // when the write completes. | |
| 56 // | |
| 57 // We want to avoid creating a large transaction, because that is outside the | |
| 58 // test's scope, and it's a bad practice. So we break up the writes across | |
| 59 // multiple transactions. For simplicity, each transaction writes all the | |
| 60 // objects that will be read by a cursor. | |
| 61 function writeCursorObjects(database, cursorIndex) { | |
| 62 return new Promise((resolve, reject) => { | |
| 63 const transaction = database.transaction('cache', 'readwrite'); | |
| 64 transaction.onabort = () => { reject(transaction.error); }; | |
| 65 | |
| 66 const store = transaction.objectStore('cache'); | |
| 67 for (let i = 0; i < itemCount; ++i) { | |
| 68 store.put({ | |
| 69 key: objectKey(cursorIndex, i), value: objectValue(cursorIndex, i)}); | |
| 70 } | |
| 71 transaction.oncomplete = resolve; | |
| 72 }); | |
| 73 } | |
| 74 | |
| 75 // Returns a promise that resolves when the store has been populated. | |
| 76 function populateTestStore(testCase, database, cursorCount) { | |
| 77 let promiseChain = Promise.resolve(); | |
| 78 | |
| 79 for (let i = 0; i < cursorCount; ++i) | |
| 80 promiseChain = promiseChain.then(() => writeCursorObjects(database, i)); | |
| 81 | |
| 82 return promiseChain; | |
| 83 } | |
| 84 | |
| 85 // Reads cursors in an interleaved fashion, as shown below. | |
| 86 // | |
| 87 // Given N cursors, each of which points to the beginning of a K-item sequence, | |
| 88 // the following accesses will be made. | |
| 89 // | |
| 90 // OC(i) = open cursor i | |
| 91 // RD(i, j) = read result of cursor i, which should be at item j | |
| 92 // CC(i) = continue cursor i | |
| 93 // | = wait for onsuccess on the previous OC or CC | |
| 94 // | |
| 95 // OC(1) | RD(1, 1) OC(2) | RD(2, 1) OC(3) | ... | RD(n-1, 1) CC(n) | | |
| 96 // RD(n, 1) CC(1) | RD(1, 2) CC(2) | RD(2, 2) CC(3) | ... | RD(n-1, 2) CC(n) | | |
| 97 // RD(n, 2) CC(1) | RD(1, 3) CC(2) | RD(2, 3) CC(3) | ... | RD(n-1, 3) CC(n) | | |
| 98 // ... | |
| 99 // RD(n, k-1) CC(1) | RD(1, k) CC(2) | RD(2, k) CC(3) | ... | RD(n-1, k) CC(n) | | |
| 100 // RD(n, k) done | |
| 101 function interleaveCursors(testCase, store, cursorCount) { | |
| 102 return new Promise((resolve, reject) => { | |
| 103 // The cursors used for iteration are stored here so each cursor's onsuccess | |
| 104 // handler can call continue() on the next cursor. | |
| 105 const cursors = []; | |
| 106 | |
| 107 // The results of IDBObjectStore.openCursor() calls are stored here so we | |
| 108 // we can change the requests' onsuccess handler after every | |
| 109 // IDBCursor.continue() call. | |
| 110 const requests = []; | |
| 111 | |
| 112 const checkCursorState = (cursorIndex, itemIndex) => { | |
| 113 const cursor = cursors[cursorIndex]; | |
| 114 assert_equals(cursor.key, objectKey(cursorIndex, itemIndex)); | |
| 115 assert_equals(cursor.value.key, objectKey(cursorIndex, itemIndex)); | |
| 116 assert_equals( | |
| 117 cursor.value.value.join('-'), | |
| 118 objectValue(cursorIndex, itemIndex).join('-')); | |
| 119 }; | |
| 120 | |
| 121 const openCursor = (cursorIndex, callback) => { | |
| 122 const request = store.openCursor( | |
| 123 IDBKeyRange.lowerBound(objectKey(cursorIndex, 0))); | |
| 124 requests[cursorIndex] = request; | |
| 125 | |
| 126 request.onsuccess = testCase.step_func(() => { | |
| 127 const cursor = request.result; | |
| 128 cursors[cursorIndex] = cursor; | |
| 129 checkCursorState(cursorIndex, 0); | |
| 130 callback(); | |
| 131 }); | |
| 132 request.onerror = event => reject(request.error); | |
| 133 }; | |
| 134 | |
| 135 const readItemFromCursor = (cursorIndex, itemIndex, callback) => { | |
| 136 const request = requests[cursorIndex]; | |
| 137 request.onsuccess = testCase.step_func(() => { | |
| 138 const cursor = request.result; | |
| 139 cursors[cursorIndex] = cursor; | |
| 140 checkCursorState(cursorIndex, itemIndex); | |
| 141 callback(); | |
| 142 }); | |
| 143 | |
| 144 const cursor = cursors[cursorIndex]; | |
| 145 cursor.continue(); | |
| 146 }; | |
| 147 | |
| 148 // We open all the cursors one at a time, then cycle through the cursors and | |
| 149 // call continue() on each of them. This access pattern causes maximal | |
| 150 // trashing to an LRU cursor cache. Eviction scheme aside, any cache will | |
| 151 // have to evict some cursors, and this access pattern verifies that the | |
| 152 // cache correctly restores the state of evicted cursors. | |
| 153 const steps = []; | |
| 154 for (let cursorIndex = 0; cursorIndex < cursorCount; ++cursorIndex) | |
| 155 steps.push(openCursor.bind(null, cursorIndex)); | |
| 156 for (let itemIndex = 1; itemIndex < itemCount; ++itemIndex) { | |
| 157 for (let cursorIndex = 0; cursorIndex < cursorCount; ++cursorIndex) | |
| 158 steps.push(readItemFromCursor.bind(null, cursorIndex, itemIndex)); | |
| 159 } | |
| 160 | |
| 161 const runStep = (stepIndex) => { | |
| 162 if (stepIndex === steps.length) { | |
| 163 resolve(); | |
| 164 return; | |
| 165 } | |
| 166 steps[stepIndex](() => { runStep(stepIndex + 1); }); | |
| 167 }; | |
| 168 runStep(0); | |
| 169 }); | |
| 170 } | |
| 171 | |
| 172 for (let cursorCount of [1, 10, 100, 500]) { | 31 for (let cursorCount of [1, 10, 100, 500]) { |
| 173 promise_test(testCase => { | 32 promise_test(testCase => { |
| 174 return createDatabase(testCase, (database, transaction) => { | 33 return createDatabase(testCase, (database, transaction) => { |
| 175 const store = database.createObjectStore('cache', | 34 const store = database.createObjectStore('cache', { keyPath: 'key' }); |
| 176 { keyPath: 'key', autoIncrement: true }); | |
| 177 }).then(database => { | 35 }).then(database => { |
| 178 return populateTestStore(testCase, database, cursorCount).then( | 36 return populateTestStore(testCase, database, cursorCount).then( |
| 179 () => database); | 37 () => database); |
| 180 }).then(database => { | 38 }).then(database => { |
| 181 database.close(); | 39 database.close(); |
| 182 }).then(() => { | 40 }).then(() => { |
| 183 return openDatabase(testCase); | 41 return openDatabase(testCase); |
| 184 }).then(database => { | 42 }).then(database => { |
| 185 const transaction = database.transaction('cache', 'readonly'); | 43 const transaction = database.transaction('cache', 'readonly'); |
| 186 transaction.onabort = () => { reject(transaction.error); }; | 44 transaction.onabort = () => { reject(transaction.error); }; |
| 187 | 45 |
| 188 const store = transaction.objectStore('cache'); | 46 const store = transaction.objectStore('cache'); |
| 189 return interleaveCursors(testCase, store, cursorCount).then( | 47 return interleaveCursors(testCase, store, cursorCount, itemCount).then( |
| 190 () => database); | 48 () => database); |
| 191 }).then(database => { | 49 }).then(database => { |
| 192 database.close(); | 50 database.close(); |
| 193 }); | 51 }); |
| 194 }, `${cursorCount} cursors`); | 52 }, `${cursorCount} cursors`); |
| 195 } | 53 } |
| 54 |
| 196 </script> | 55 </script> |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2781623008:
More thorough overlapping cursor tests. (Closed)
