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 over disjoint data r
anges</title> | 4 <title>IndexedDB: Interleaved iteration of multiple cursors</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> | |
10 <script> | 9 <script> |
11 'use strict'; | |
12 | |
13 // Number of objects that each iterator goes over. | 10 // Number of objects that each iterator goes over. |
14 const itemCount = 8; | 11 const itemCount = 10; |
15 | 12 |
16 // Ratio of small objects to large objects. | 13 // Ratio of small objects to large objects. |
17 const largeObjectRatio = 3; | 14 const largeObjectRatio = 5; |
| 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; |
18 | 21 |
19 function objectKey(cursorIndex, itemIndex) { | 22 function objectKey(cursorIndex, itemIndex) { |
20 const cursorString = cursorIndex.toString().padStart(5, '0'); | 23 return `${cursorIndex}-key-${itemIndex}`; |
21 const itemString = itemIndex.toString().padStart(5, '0'); | |
22 return `${cursorString}-key-${itemString}`; | |
23 } | 24 } |
24 | 25 |
25 function objectValue(cursorIndex, itemIndex) { | 26 function objectValue(cursorIndex, itemIndex) { |
26 if ((cursorIndex * itemCount + itemIndex) % largeObjectRatio === 0) | 27 if ((cursorIndex * itemCount + itemIndex) % largeObjectRatio === 0) { |
27 return largeObjectValue(cursorIndex, itemIndex); | 28 // We use a typed array (as opposed to a string) because IndexedDB |
| 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 } |
28 return [cursorIndex, 'small', itemIndex]; | 51 return [cursorIndex, 'small', itemIndex]; |
29 } | 52 } |
30 | 53 |
| 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 |
31 for (let cursorCount of [1, 10, 100, 500]) { | 172 for (let cursorCount of [1, 10, 100, 500]) { |
32 promise_test(testCase => { | 173 promise_test(testCase => { |
33 return createDatabase(testCase, (database, transaction) => { | 174 return createDatabase(testCase, (database, transaction) => { |
34 const store = database.createObjectStore('cache', { keyPath: 'key' }); | 175 const store = database.createObjectStore('cache', |
| 176 { keyPath: 'key', autoIncrement: true }); |
35 }).then(database => { | 177 }).then(database => { |
36 return populateTestStore(testCase, database, cursorCount).then( | 178 return populateTestStore(testCase, database, cursorCount).then( |
37 () => database); | 179 () => database); |
38 }).then(database => { | 180 }).then(database => { |
39 database.close(); | 181 database.close(); |
40 }).then(() => { | 182 }).then(() => { |
41 return openDatabase(testCase); | 183 return openDatabase(testCase); |
42 }).then(database => { | 184 }).then(database => { |
43 const transaction = database.transaction('cache', 'readonly'); | 185 const transaction = database.transaction('cache', 'readonly'); |
44 transaction.onabort = () => { reject(transaction.error); }; | 186 transaction.onabort = () => { reject(transaction.error); }; |
45 | 187 |
46 const store = transaction.objectStore('cache'); | 188 const store = transaction.objectStore('cache'); |
47 return interleaveCursors(testCase, store, cursorCount, itemCount).then( | 189 return interleaveCursors(testCase, store, cursorCount).then( |
48 () => database); | 190 () => database); |
49 }).then(database => { | 191 }).then(database => { |
50 database.close(); | 192 database.close(); |
51 }); | 193 }); |
52 }, `${cursorCount} cursors`); | 194 }, `${cursorCount} cursors`); |
53 } | 195 } |
54 | |
55 </script> | 196 </script> |
OLD | NEW |