Bug 1523562 [wpt PR 14420] - [WebLocks]: Modifying weblocks algos to be O(1), a=testonly
authorAndreas Butler <andreasbutler@google.com>
Thu, 31 Jan 2019 18:59:35 +0000
changeset 458094 6c55703c50d5699d7dfdc12a049c3a0de2190a92
parent 458093 60cb26127b7329e8ce1fade50a6e9c5ed136cdc2
child 458095 ab47a3aae64d7ed015afad184344cb35b147505a
push id35518
push useropoprus@mozilla.com
push dateFri, 08 Feb 2019 09:55:14 +0000
treeherdermozilla-central@3a3e393396f4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerstestonly
bugs1523562, 14420, 913014, 1367910, 621833
milestone67.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1523562 [wpt PR 14420] - [WebLocks]: Modifying weblocks algos to be O(1), a=testonly Automatic update from web-platform-tests [WebLocks]: Modifying weblocks algos to be O(1) The behaviour of the request/release operations of web locks are modified to be O(1) instead of their currently O(n) worst case runtime. Additionally the query-order wpt is modified to reflect the new spec requirement that the state returned by navigator.locks.query need only respect ordering for requested locks per resource. Bug: 913014 Change-Id: I819f8c27c995cb698a7c8b2c75ee80d32c744f07 Spec: https://wicg.github.io/web-locks/#algorithms Reviewed-on: https://chromium-review.googlesource.com/c/1367910 Commit-Queue: Andreas Butler <andreasbutler@google.com> Reviewed-by: Victor Costan <pwnall@chromium.org> Reviewed-by: Joshua Bell <jsbell@chromium.org> Reviewed-by: Daniel Murphy <dmurph@chromium.org> Cr-Commit-Position: refs/heads/master@{#621833} -- wpt-commits: 27085bc4fef9a55a5f5dd530c6e8ff798ff8c6c4 wpt-pr: 14420
testing/web-platform/tests/web-locks/query-order.tentative.https.any.js
testing/web-platform/tests/web-locks/query-ordering.tentative.https.html
testing/web-platform/tests/web-locks/resources/helpers.js
testing/web-platform/tests/web-locks/resources/iframe.html
deleted file mode 100644
--- a/testing/web-platform/tests/web-locks/query-order.tentative.https.any.js
+++ /dev/null
@@ -1,110 +0,0 @@
-// META: title=Web Locks API: navigator.locks.query ordering
-// META: script=resources/helpers.js
-// META: global=window,dedicatedworker,sharedworker,serviceworker
-
-'use strict';
-
-// Grab a lock and hold until a release function is called. Resolves
-// to a release function.
-function getLockAndHoldUntilReleased(name, options) {
-  let release;
-  const promise = new Promise(resolve => { release = resolve; });
-  return new Promise(resolve => {
-    navigator.locks.request(name, options || {}, lock => {
-      resolve(release);
-      return promise;
-    }).catch(_ => {});
-  });
-}
-
-promise_test(async t => {
-  const res1 = uniqueName(t);
-  const res2 = uniqueName(t);
-  const res3 = uniqueName(t);
-
-  // These will never be released.
-  await Promise.all([
-    getLockAndHoldUntilReleased(res1),
-    getLockAndHoldUntilReleased(res2),
-    getLockAndHoldUntilReleased(res3)
-  ]);
-
-  // These requests should be blocked.
-  navigator.locks.request(res3, {mode: 'shared'}, lock => {});
-  navigator.locks.request(res2, {mode: 'shared'}, lock => {});
-  navigator.locks.request(res1, {mode: 'shared'}, lock => {});
-
-  const state = await navigator.locks.query();
-
-  const relevant_pending_names = state.pending.map(lock => lock.name)
-                        .filter(name => [res1, res2, res3].includes(name));
-
-  assert_array_equals(relevant_pending_names, [res3, res2, res1],
-                      'Pending locks should appear in order.');
-}, 'Requests appear in state in order made');
-
-promise_test(async t => {
-  const res1 = uniqueName(t);
-  const res2 = uniqueName(t);
-  const res3 = uniqueName(t);
-
-  // These should be granted, and will be held until released.
-  const [release1, release2, release3] = await Promise.all([
-    getLockAndHoldUntilReleased(res1),
-    getLockAndHoldUntilReleased(res2),
-    getLockAndHoldUntilReleased(res3)
-  ]);
-
-  // These requests should be blocked.
-  const requests = [
-    getLockAndHoldUntilReleased(res1),
-    getLockAndHoldUntilReleased(res2),
-    getLockAndHoldUntilReleased(res3)
-  ];
-
-  // Ensure the requests have had a chance to get queued by
-  // waiting for something else to make it through the queue.
-  await navigator.locks.request(uniqueName(t), lock => {});
-
-  // Now release the previous holders.
-  release2();
-  release3();
-  release1();
-
-  // Wait until the subsequent requests make it through.
-  await Promise.all(requests);
-
-  const state = await navigator.locks.query();
-  const relevant_held_names = state.held.map(lock => lock.name)
-                        .filter(name => [res1, res2, res3].includes(name));
-
-  assert_array_equals(relevant_held_names, [res2, res3, res1],
-                      'Held locks should appear in granted order.');
-}, 'Held locks appear in state in order granted');
-
-promise_test(async t => {
-  const res1 = uniqueName(t);
-  const res2 = uniqueName(t);
-  const res3 = uniqueName(t);
-
-  // These should be granted, and will be held until stolen.
-  await Promise.all([
-    getLockAndHoldUntilReleased(res1),
-    getLockAndHoldUntilReleased(res2),
-    getLockAndHoldUntilReleased(res3)
-  ]);
-
-  // Steal in a different order.
-  await Promise.all([
-    getLockAndHoldUntilReleased(res3, {steal: true}),
-    getLockAndHoldUntilReleased(res1, {steal: true}),
-    getLockAndHoldUntilReleased(res2, {steal: true})
-  ]);
-
-  const state = await navigator.locks.query();
-  const relevant_held_names = state.held.map(lock => lock.name)
-                        .filter(name => [res1, res2, res3].includes(name));
-
-  assert_array_equals(relevant_held_names, [res3, res1, res2],
-                      'Held locks should appear in granted order.');
-}, 'Held locks appear in state in order granted, including when stolen');
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/web-locks/query-ordering.tentative.https.html
@@ -0,0 +1,130 @@
+<!DOCTYPE html>
+<meta charset=utf-8>
+<title>Web Locks API: navigator.locks.query ordering</title>
+<link rel=help href="https://wicg.github.io/web-locks/">
+<script src="/resources/testharness.js"></script>
+<script src="/resources/testharnessreport.js"></script>
+<script src="resources/helpers.js"></script>
+<style>iframe { display: none; }</style>
+<script>
+'use strict';
+
+// Grab a lock and hold until a release function is called. Resolves
+// to a release function.
+function getLockAndHoldUntilReleased(name, options) {
+  let release;
+  const promise = new Promise(resolve => { release = resolve; });
+  return new Promise(resolve => {
+    navigator.locks.request(name, options || {}, lock => {
+      resolve(release);
+      return promise;
+    }).catch(_ => {});
+  });
+}
+
+// Returns a promise resolved by the next message event.
+function nextMessage() {
+  return new Promise(resolve => {
+    window.addEventListener('message', event => {
+      resolve(event.data);
+    }, {once: true});
+  });
+}
+
+// Tests the ordering constraints on the requested lock state returned by
+// navigator.locks.query(). Three separate iframes are instantiated to make
+// lock requests on the same resource, first in one order and then in another,
+// different order. For each set of requests, it is verified that the requests
+// appear in the result of navigator.locks.query() in the same order in which
+// they were made.
+//
+// It is necessary to use separate iframes here so that the lock requests have
+// distinguishable client_ids (otherwise it would not be possible to
+// distinguish the requests and thus impossible to verify ordering).
+promise_test(async testCase => {
+  const resourceName = uniqueName(testCase);
+
+  // Set up clients.
+  const frame1 = await iframe('resources/iframe.html');
+  const frame2 = await iframe('resources/iframe.html');
+  const frame3 = await iframe('resources/iframe.html');
+  testCase.add_cleanup(() => { frame1.remove(); });
+  testCase.add_cleanup(() => { frame2.remove(); });
+  testCase.add_cleanup(() => { frame3.remove(); });
+
+  // Collect the client ids.
+  const clientId1 =
+      (await postToFrameAndWait(frame1, {op: 'client_id',
+                                         name: resourceName})).client_id;
+  const clientId2 =
+      (await postToFrameAndWait(frame2, {op: 'client_id',
+                                         name: resourceName})).client_id;
+  const clientId3 =
+      (await postToFrameAndWait(frame3, {op: 'client_id',
+                                         name: resourceName})).client_id;
+
+  // Preemptively take the lock.
+  const firstRequestGroupReleaseFunction =
+      await getLockAndHoldUntilReleased(resourceName);
+
+  // Queue the first group of lock requests from the different clients. These
+  // will be blocked until firstRequestGroupReleaseFunction() is called.
+  let lockId1;
+  let lockId2;
+  const lockPromise1 =
+      postToFrameAndWait(frame1, {op: 'request', name: resourceName})
+          .then(val => {lockId1 = val.lock_id;});
+  const lockPromise2 =
+      postToFrameAndWait(frame2, {op: 'request', name: resourceName})
+          .then(val => {lockId2 = val.lock_id;});
+
+  // This third request will later be granted and held in order to block a
+  // second group of requests to test a different client ordering. It is not
+  // meant to be released.
+  postToFrameAndWait(frame3, {op: 'request', name: resourceName});
+
+  // Request and wait for the release of a separate lock to ensure all previous
+  // requests are processed.
+  const checkpointName = uniqueName(testCase, 'checkpoint');
+  const checkpointId = (await postToFrameAndWait(
+                                  frame3,
+                                  {op: 'request', name: checkpointName})).lock_id;
+  await postToFrameAndWait(frame3, {op: 'release', lock_id: checkpointId});
+
+  // Query the state and test the ordering of requested locks.
+  const state = await navigator.locks.query();
+  const relevant_pending_ids = state.pending
+      .filter(lock => [clientId1, clientId2, clientId3].includes(lock.clientId))
+      .map(lock => lock.clientId);
+  assert_array_equals(
+      [clientId1, clientId2, clientId3],
+      relevant_pending_ids,
+      'Querying the state should return requested locks in the order they were '
+      + 'requested.');
+
+  // Add the second group of requests from the clients in a new order.
+  postToFrameAndWait(frame3, {op: 'request', name: resourceName});
+  postToFrameAndWait(frame1, {op: 'request', name: resourceName});
+  postToFrameAndWait(frame2, {op: 'request', name: resourceName});
+
+  // Release locks such that only the newly added locks are requested. This
+  // acts like a checkpoint for the newly queued requests.
+  firstRequestGroupReleaseFunction();
+  await lockPromise1;
+  await postToFrameAndWait(frame1, {op: 'release', lock_id: lockId1});
+  await lockPromise2;
+  await postToFrameAndWait(frame2, {op: 'release', lock_id: lockId2});
+
+  // Query the state and test the new ordering.
+  const state2 = await navigator.locks.query();
+  const relevant_pending_ids2 = state2.pending
+      .filter(lock => [clientId1, clientId2, clientId3].includes(lock.clientId))
+      .map(lock => lock.clientId);
+  assert_array_equals(
+      [clientId3, clientId1, clientId2],
+      relevant_pending_ids2,
+      'Querying the state should return requested locks in the order they were '
+      + 'requested.');
+
+}, 'Requests appear in state in order made.');
+</script>
--- a/testing/web-platform/tests/web-locks/resources/helpers.js
+++ b/testing/web-platform/tests/web-locks/resources/helpers.js
@@ -1,17 +1,17 @@
 // Test helpers used by multiple Web Locks API tests.
 (() => {
 
   // Generate a unique resource identifier, using the script path and
   // test case name. This is useful to avoid lock interference between
   // test cases.
   let res_num = 0;
-  self.uniqueName = testCase => {
-    return `${self.location.pathname}-${testCase.name}-${++res_num}`;
+  self.uniqueName = (testCase, prefix) => {
+    return `${self.location.pathname}-${prefix}-${testCase.name}-${++res_num}`;
   };
 
   // Inject an iframe showing the given url into the page, and resolve
   // the returned promise when the frame is loaded.
   self.iframe = url => new Promise(resolve => {
     const element = document.createElement('iframe');
     element.addEventListener(
       'load', () => { resolve(element); }, { once: true });
--- a/testing/web-platform/tests/web-locks/resources/iframe.html
+++ b/testing/web-platform/tests/web-locks/resources/iframe.html
@@ -33,11 +33,20 @@ self.addEventListener('message', e => {
         });
       break;
 
     case 'release':
       held.get(e.data.lock_id)();
       held.delete(e.data.lock_id);
       respond({ack: 'release', lock_id: e.data.lock_id});
       break;
+
+    case 'client_id':
+      navigator.locks.request(e.data.name, async lock => {
+        const lock_state = await navigator.locks.query();
+        const held_lock =
+            lock_state.held.filter(l => l.name === lock.name)[0];
+        respond({ack: 'client_id', client_id: held_lock.clientId});
+      });
+      break;
   }
 });
 </script>