Fix last_devices to be quieter, and improve device affinity.

build/android/pylib/perf/setup.py

 # Copyright 2013 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Generates test runner factory and tests for performance tests."""
 
 import json
 import fnmatch
+import hashlib
+import itertools
 import logging
 import os
 import shutil
 
 from pylib import constants
 from pylib import forwarder
 from pylib.device import device_list
 from pylib.device import device_utils
 from pylib.perf import test_runner
 from pylib.utils import test_environment
 
 
-def _GetAllDevices():
-  devices_path = os.path.join(os.environ.get('CHROMIUM_OUT_DIR', 'out'),
-                              device_list.LAST_DEVICES_FILENAME)
-  try:
-    devices = [device_utils.DeviceUtils(s)
-               for s in device_list.GetPersistentDeviceList(devices_path)]
-  except IOError as e:
-    logging.error('Unable to find %s [%s]', devices_path, e)
-    devices = device_utils.DeviceUtils.HealthyDevices()
-  return sorted(devices)
-
-
 def _GetStepsDictFromSingleStep(test_options):
   # Running a single command, build the tests structure.
   steps_dict = {
     'version': 1,
     'steps': {
         'single_step': {
           'device_affinity': 0,
           'cmd': test_options.single_step
         },
     }
   }
   return steps_dict
 
 
 def _GetStepsDict(test_options):
   if test_options.single_step:
     return _GetStepsDictFromSingleStep(test_options)
   if test_options.steps:
     with file(test_options.steps, 'r') as f:
       steps = json.load(f)
 
       # Already using the new format.
       assert steps['version'] == 1
       return steps
 
 
+def DistributeAffinities(devices):
+  """Create a mapping from device to affinity using a round-robin hash scheme.
+
+  Args:
+    devices: a list of device serials.
+
+  Returns: a dictionary mapping each of the given device serials to a list
+    of affinities (numbers between 0 and NUM_DEVICE_AFFINITIES-1) it should
+    run.
+
+  This function implements an algorithm to assign affinities to devices in a
+  relatively stable way while still maximizing the use of resources.
+
+  We begin with all affinities unassigned.  We cycle through the list of device
+  serials, and for each one we assign a yet-unassigned affinity.  We choose the
+  affinity to assign by hashing the device serial, so that changes in the set of
+  devices will produce minimal changes in the assignments.  We resolve
+  collisions by incrementing the affinity until we find one that is free.
+  """
+  affinities = test_runner.NUM_DEVICE_AFFINITIES
+
+  if not devices:
+    return {}
+
+  affinity_to_device = {}
+
+  devices = sorted(devices)
+  device_cycle = itertools.islice(itertools.cycle(devices), affinities)
+  for device in device_cycle:
+    # Hash the device ID to get a unique affinity.
+    start_affinity = int(int(hashlib.md5(device).hexdigest(), 16) % affinities)
+    affinity_cycle = itertools.islice(
+        itertools.cycle(range(affinities)),
+        start_affinity, start_affinity+affinities)
+
+    # "Increment" the affinity repeatedly until we find an available slot.
+    for affinity in affinity_cycle:
+      if affinity not in affinity_to_device:
+        affinity_to_device[affinity] = device
+        break
+    else:
+      raise Exception('Impossibly failed to find unassigned affinity')
+
+  # Invert the dictionary we just built.
+  device_to_affinity = {}
+  for k, v in affinity_to_device.iteritems():
+    if v not in device_to_affinity:
+      device_to_affinity[v] = []
+    device_to_affinity[v].append(k)
+
+  return device_to_affinity
+
 def Setup(test_options):
   """Create and return the test runner factory and tests.
 
   Args:
     test_options: A PerformanceOptions object.
 
   Returns:
     A tuple of (TestRunnerFactory, tests, devices).
   """
   # TODO(bulach): remove this once the bot side lands. BUG=318369
   constants.SetBuildType('Release')
   if os.path.exists(constants.PERF_OUTPUT_DIR):
     shutil.rmtree(constants.PERF_OUTPUT_DIR)
   os.makedirs(constants.PERF_OUTPUT_DIR)
 
   # Before running the tests, kill any leftover server.
   test_environment.CleanupLeftoverProcesses()
 
-  # We want to keep device affinity, so return all devices ever seen.
-  all_devices = _GetAllDevices()
+  all_devices = [d.adb.GetDeviceSerial()
+                 for d in device_utils.DeviceUtils.HealthyDevices()]
+  affinity_map = DistributeAffinities(all_devices)
 
   steps_dict = _GetStepsDict(test_options)
   sorted_step_names = sorted(steps_dict['steps'].keys())
 
   if test_options.test_filter:
     sorted_step_names = fnmatch.filter(sorted_step_names,
                                        test_options.test_filter)
 
   flaky_steps = []
   if test_options.flaky_steps:
     with file(test_options.flaky_steps, 'r') as f:
       flaky_steps = json.load(f)
 
-  def TestRunnerFactory(device, shard_index):
+  def TestRunnerFactory(device, _):
+    affinities = affinity_map[device]
     return test_runner.TestRunner(
-        test_options, device, shard_index, len(all_devices),
-        steps_dict, flaky_steps)
+        test_options, device, affinities, steps_dict, flaky_steps)
 
   return (TestRunnerFactory, sorted_step_names, all_devices)