116d7a5204e347855b1c3a68c982c22f931a12866Yuheng Long# Copyright (c) 2013 The Chromium OS Authors. All rights reserved. 216d7a5204e347855b1c3a68c982c22f931a12866Yuheng Long# Use of this source code is governed by a BSD-style license that can be 316d7a5204e347855b1c3a68c982c22f931a12866Yuheng Long# found in the LICENSE file. 449358b75c25a44760e884245440dc96e55812d04Yuheng Long"""Steering stage unittest. 549358b75c25a44760e884245440dc96e55812d04Yuheng Long 649358b75c25a44760e884245440dc96e55812d04Yuheng LongPart of the Chrome build flags optimization. 749358b75c25a44760e884245440dc96e55812d04Yuheng Long""" 8f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 9f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long__author__ = 'yuhenglong@google.com (Yuheng Long)' 10f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 11a5712a2c71aa665dcca808963d152228890c8364Yuheng Longimport multiprocessing 12f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Longimport unittest 13f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 14a5712a2c71aa665dcca808963d152228890c8364Yuheng Longfrom generation import Generation 15a5712a2c71aa665dcca808963d152228890c8364Yuheng Longfrom mock_task import IdentifierMockTask 16a5712a2c71aa665dcca808963d152228890c8364Yuheng Longimport pipeline_process 17f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Longimport steering 18f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 19a5712a2c71aa665dcca808963d152228890c8364Yuheng Long# Pick an integer at random. 20a5712a2c71aa665dcca808963d152228890c8364Yuheng LongSTEERING_TEST_STAGE = -8 21a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 22a5712a2c71aa665dcca808963d152228890c8364Yuheng Long# The number of generations to be used to do the testing. 23a5712a2c71aa665dcca808963d152228890c8364Yuheng LongNUMBER_OF_GENERATIONS = 20 24a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 25a5712a2c71aa665dcca808963d152228890c8364Yuheng Long# The number of tasks to be put in each generation to be tested. 26a5712a2c71aa665dcca808963d152228890c8364Yuheng LongNUMBER_OF_TASKS = 20 27a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 28a5712a2c71aa665dcca808963d152228890c8364Yuheng Long# The stride of permutation used to shuffle the input list of tasks. Should be 29a5712a2c71aa665dcca808963d152228890c8364Yuheng Long# relatively prime with NUMBER_OF_TASKS. 30a5712a2c71aa665dcca808963d152228890c8364Yuheng LongSTRIDE = 7 31a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 32a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 33a5712a2c71aa665dcca808963d152228890c8364Yuheng Longclass MockGeneration(Generation): 34a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """This class emulates an actual generation. 35a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 36a5712a2c71aa665dcca808963d152228890c8364Yuheng Long It will output the next_generations when the method Next is called. The 37a5712a2c71aa665dcca808963d152228890c8364Yuheng Long next_generations is initiated when the MockGeneration instance is constructed. 38a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """ 39a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 40a5712a2c71aa665dcca808963d152228890c8364Yuheng Long def __init__(self, tasks, next_generations): 41a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """Set up the next generations for this task. 42a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 43a5712a2c71aa665dcca808963d152228890c8364Yuheng Long Args: 44a5712a2c71aa665dcca808963d152228890c8364Yuheng Long tasks: A set of tasks to be run. 45a5712a2c71aa665dcca808963d152228890c8364Yuheng Long next_generations: A list of generations as the next generation of the 46a5712a2c71aa665dcca808963d152228890c8364Yuheng Long current generation. 47a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """ 48a5712a2c71aa665dcca808963d152228890c8364Yuheng Long Generation.__init__(self, tasks, None) 49a5712a2c71aa665dcca808963d152228890c8364Yuheng Long self._next_generations = next_generations 50a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 51a5712a2c71aa665dcca808963d152228890c8364Yuheng Long def Next(self, _): 52a5712a2c71aa665dcca808963d152228890c8364Yuheng Long return self._next_generations 53a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 54c01232264caccaffe6302414b7e901a96d3b18bfYuheng Long def IsImproved(self): 55a5712a2c71aa665dcca808963d152228890c8364Yuheng Long if self._next_generations: 56a5712a2c71aa665dcca808963d152228890c8364Yuheng Long return True 57a5712a2c71aa665dcca808963d152228890c8364Yuheng Long return False 58a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 59a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 60f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Longclass SteeringTest(unittest.TestCase): 61a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """This class test the steering method. 62f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 63a5712a2c71aa665dcca808963d152228890c8364Yuheng Long The steering algorithm should return if there is no new task in the initial 64a5712a2c71aa665dcca808963d152228890c8364Yuheng Long generation. The steering algorithm should send all the tasks to the next stage 65a5712a2c71aa665dcca808963d152228890c8364Yuheng Long and should terminate once there is no pending generation. A generation is 66a5712a2c71aa665dcca808963d152228890c8364Yuheng Long pending if it contains pending task. A task is pending if its (test) result 67a5712a2c71aa665dcca808963d152228890c8364Yuheng Long is not ready. 68f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long """ 69f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 70a5712a2c71aa665dcca808963d152228890c8364Yuheng Long def testSteering(self): 71a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """Test that the steering algorithm processes all the tasks properly. 72a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 73a5712a2c71aa665dcca808963d152228890c8364Yuheng Long Test that the steering algorithm sends all the tasks to the next stage. Test 74a5712a2c71aa665dcca808963d152228890c8364Yuheng Long that the steering algorithm terminates once all the tasks have been 75a5712a2c71aa665dcca808963d152228890c8364Yuheng Long processed, i.e., the results for the tasks are all ready. 76a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """ 77a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 78a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # A list of generations used to test the steering stage. 79a5712a2c71aa665dcca808963d152228890c8364Yuheng Long generations = [] 80a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 81a5712a2c71aa665dcca808963d152228890c8364Yuheng Long task_index = 0 82a5712a2c71aa665dcca808963d152228890c8364Yuheng Long previous_generations = None 83a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 84a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Generate a sequence of generations to be tested. Each generation will 85a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # output the next generation in reverse order of the list when the "Next" 86a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # method is called. 87a5712a2c71aa665dcca808963d152228890c8364Yuheng Long for _ in range(NUMBER_OF_GENERATIONS): 88a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Use a consecutive sequence of numbers as identifiers for the set of 89a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # tasks put into a generation. 90a5712a2c71aa665dcca808963d152228890c8364Yuheng Long test_ranges = range(task_index, task_index + NUMBER_OF_TASKS) 91a5712a2c71aa665dcca808963d152228890c8364Yuheng Long tasks = [IdentifierMockTask(STEERING_TEST_STAGE, t) for t in test_ranges] 92a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_tasks = set(tasks) 93a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 94a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Let the previous generation as the offspring generation of the current 95a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # generation. 96a5712a2c71aa665dcca808963d152228890c8364Yuheng Long current_generation = MockGeneration(steering_tasks, previous_generations) 97a5712a2c71aa665dcca808963d152228890c8364Yuheng Long generations.insert(0, current_generation) 98a5712a2c71aa665dcca808963d152228890c8364Yuheng Long previous_generations = [current_generation] 99a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 100a5712a2c71aa665dcca808963d152228890c8364Yuheng Long task_index += NUMBER_OF_TASKS 101a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 102a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # If there is no generation at all, the unittest returns right away. 103a5712a2c71aa665dcca808963d152228890c8364Yuheng Long if not current_generation: 104a5712a2c71aa665dcca808963d152228890c8364Yuheng Long return 105a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 106a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Set up the input and result queue for the steering method. 107a5712a2c71aa665dcca808963d152228890c8364Yuheng Long manager = multiprocessing.Manager() 108a5712a2c71aa665dcca808963d152228890c8364Yuheng Long input_queue = manager.Queue() 109a5712a2c71aa665dcca808963d152228890c8364Yuheng Long result_queue = manager.Queue() 110a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 111f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano steering_process = multiprocessing.Process( 112f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano target=steering.Steering, 113f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano args=(set(), [current_generation], input_queue, result_queue)) 114a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_process.start() 115a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 116a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Test that each generation is processed properly. I.e., the generations are 117a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # processed in order. 118a5712a2c71aa665dcca808963d152228890c8364Yuheng Long while generations: 119a5712a2c71aa665dcca808963d152228890c8364Yuheng Long generation = generations.pop(0) 120a5712a2c71aa665dcca808963d152228890c8364Yuheng Long tasks = [task for task in generation.Pool()] 121a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 122a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Test that all the tasks are processed once and only once. 123a5712a2c71aa665dcca808963d152228890c8364Yuheng Long while tasks: 124a5712a2c71aa665dcca808963d152228890c8364Yuheng Long task = result_queue.get() 125a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 126a5712a2c71aa665dcca808963d152228890c8364Yuheng Long assert task in tasks 127a5712a2c71aa665dcca808963d152228890c8364Yuheng Long tasks.remove(task) 128a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 129a5712a2c71aa665dcca808963d152228890c8364Yuheng Long input_queue.put(task) 130a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 131a5712a2c71aa665dcca808963d152228890c8364Yuheng Long task = result_queue.get() 132a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 133a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Test that the steering algorithm returns properly after processing all 134a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # the generations. 135a5712a2c71aa665dcca808963d152228890c8364Yuheng Long assert task == pipeline_process.POISONPILL 136a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 137a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_process.join() 138a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 139a5712a2c71aa665dcca808963d152228890c8364Yuheng Long def testCache(self): 140a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """The steering algorithm returns immediately if there is no new tasks. 141a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 142a5712a2c71aa665dcca808963d152228890c8364Yuheng Long If all the new tasks have been cached before, the steering algorithm does 143a5712a2c71aa665dcca808963d152228890c8364Yuheng Long not have to execute these tasks again and thus can terminate right away. 144a5712a2c71aa665dcca808963d152228890c8364Yuheng Long """ 145a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 146a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Put a set of tasks in the cache and add this set to initial generation. 147a5712a2c71aa665dcca808963d152228890c8364Yuheng Long test_ranges = range(NUMBER_OF_TASKS) 148a5712a2c71aa665dcca808963d152228890c8364Yuheng Long tasks = [IdentifierMockTask(STEERING_TEST_STAGE, t) for t in test_ranges] 149a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_tasks = set(tasks) 150a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 151a5712a2c71aa665dcca808963d152228890c8364Yuheng Long current_generation = MockGeneration(steering_tasks, None) 152a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 153a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Set up the input and result queue for the steering method. 154a5712a2c71aa665dcca808963d152228890c8364Yuheng Long manager = multiprocessing.Manager() 155a5712a2c71aa665dcca808963d152228890c8364Yuheng Long input_queue = manager.Queue() 156a5712a2c71aa665dcca808963d152228890c8364Yuheng Long result_queue = manager.Queue() 157a5712a2c71aa665dcca808963d152228890c8364Yuheng Long 158f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano steering_process = multiprocessing.Process( 159f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano target=steering.Steering, 160f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano args=(steering_tasks, [current_generation], input_queue, result_queue)) 161f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 162a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_process.start() 163f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 164a5712a2c71aa665dcca808963d152228890c8364Yuheng Long # Test that the steering method returns right away. 165a5712a2c71aa665dcca808963d152228890c8364Yuheng Long assert result_queue.get() == pipeline_process.POISONPILL 166a5712a2c71aa665dcca808963d152228890c8364Yuheng Long steering_process.join() 167f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long 168f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 169f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Longif __name__ == '__main__': 170f20cffac082e3d920818f230ffc80ae6976267c0Yuheng Long unittest.main() 171