<s> from sts . fingerprints . messages import * <EOL> from sts . replay_event import * <EOL> import logging <EOL> import time <EOL> from collections import defaultdict <EOL> log = logging . getLogger ( "<STR_LIT>" ) <EOL> def split_list ( l , split_ways ) : <EOL> '''<STR_LIT>''' <EOL> if split_ways < <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> splits = [ ] <EOL> split_interval = len ( l ) / split_ways <EOL> remainder = len ( l ) % split_ways <EOL> start_idx = <NUM_LIT:0> <EOL> while len ( splits ) < split_ways : <EOL> split_idx = start_idx + split_interval <EOL> if remainder > <NUM_LIT:0> : <EOL> split_idx += <NUM_LIT:1> <EOL> remainder -= <NUM_LIT:1> <EOL> splits . append ( l [ start_idx : split_idx ] ) <EOL> start_idx = split_idx <EOL> return splits <EOL> class AtomicInput ( object ) : <EOL> def __init__ ( self , failure , recoveries ) : <EOL> self . failure = failure <EOL> self . recoveries = recoveries <EOL> @ property <EOL> def label ( self ) : <EOL> return "<STR_LIT>" % ( self . failure . label , [ r . label for r in self . recoveries ] ) <EOL> def __repr__ ( self ) : <EOL> return "<STR_LIT>" % ( self . failure , self . recoveries ) <EOL> class EventDagView ( object ) : <EOL> def __init__ ( self , parent , events_list ) : <EOL> '''<STR_LIT>''' <EOL> self . _parent = parent <EOL> self . _events_list = list ( events_list ) <EOL> self . _events_set = set ( self . _events_list ) <EOL> @ property <EOL> def events ( self ) : <EOL> '''<STR_LIT>''' <EOL> return self . _events_list <EOL> @ property <EOL> def input_events ( self ) : <EOL> return [ e for e in self . _events_list if isinstance ( e , InputEvent ) and e . prunable ] <EOL> @ property <EOL> def atomic_input_events ( self ) : <EOL> return self . _parent . _atomic_input_events ( self . input_events ) <EOL> def input_subset ( self , subset ) : <EOL> '''<STR_LIT>''' <EOL> return self . _parent . input_subset ( subset ) <EOL> def atomic_input_subset ( self , subset ) : <EOL> '''<STR_LIT>''' <EOL> return self . _parent . atomic_input_subset ( subset ) <EOL> def input_complement ( self , subset ) : <EOL> return self . _parent . input_complement ( subset , self . _events_list ) <EOL> def insert_atomic_inputs ( self , inputs ) : <EOL> return self . _parent . insert_atomic_inputs ( inputs , events_list = self . _events_list ) <EOL> def add_inputs ( self , inputs ) : <EOL> return self . _parent . add_inputs ( inputs , self . _events_list ) <EOL> def next_state_change ( self , index ) : <EOL> return self . _parent . next_state_change ( index , events = self . events ) <EOL> def get_original_index_for_event ( self , event ) : <EOL> return self . _parent . get_original_index_for_event ( event ) <EOL> def get_last_invariant_violation ( self ) : <EOL> return self . _parent . get_last_invariant_violation ( ) <EOL> def set_events_as_timed_out ( self , timed_out_event_labels ) : <EOL> return self . _parent . set_events_as_timed_out ( timed_out_event_labels ) <EOL> def filter_timeouts ( self ) : <EOL> return self . _parent . filter_timeouts ( events_list = self . _events_list ) <EOL> def __len__ ( self ) : <EOL> return len ( self . _events_list ) <EOL> def migrations_per_host ( events ) : <EOL> host2migrations = defaultdict ( list ) <EOL> for e in events : <EOL> if type ( e ) == HostMigration : <EOL> host2migrations [ e . host_id ] . append ( e ) <EOL> return host2migrations <EOL> def replace_migration ( replacee , old_location , new_location , event_list ) : <EOL> new_migration = HostMigration ( old_location [ <NUM_LIT:0> ] , old_location [ <NUM_LIT:1> ] , <EOL> new_location [ <NUM_LIT:0> ] , new_location [ <NUM_LIT:1> ] , <EOL> host_id = replacee . host_id , <EOL> time = replacee . time , label = replacee . label ) <EOL> index = event_list . index ( replacee ) <EOL> event_list [ index ] = new_migration <EOL> return new_migration <EOL> class EventDag ( object ) : <EOL> '''<STR_LIT>''' <EOL> _peek_seconds = <NUM_LIT> <EOL> _failure_types = set ( [ SwitchFailure , LinkFailure , ControllerFailure , <EOL> ControlChannelBlock , BlockControllerPair ] ) <EOL> _recovery_types = set ( [ SwitchRecovery , LinkRecovery , ControllerRecovery , <EOL> ControlChannelUnblock , UnblockControllerPair ] ) <EOL> _ignored_input_types = set ( [ WaitTime ] ) <EOL> def __init__ ( self , events , prefix_trie = None ) : <EOL> '''<STR_LIT>''' <EOL> self . _prefix_trie = prefix_trie <EOL> self . _events_list = events <EOL> self . _events_set = set ( self . _events_list ) <EOL> self . _label2event = { <EOL> event . label : event <EOL> for event in self . _events_list <EOL> } <EOL> self . _event2idx = { <EOL> event : i <EOL> for i , event in enumerate ( self . _events_list ) <EOL> } <EOL> self . _host2initial_location = { <EOL> host : migrations [ <NUM_LIT:0> ] . old_location <EOL> for host , migrations in migrations_per_host ( self . _events_list ) . iteritems ( ) <EOL> } <EOL> self . _last_violation = None <EOL> @ property <EOL> def events ( self ) : <EOL> '''<STR_LIT>''' <EOL> return self . _events_list <EOL> @ property <EOL> def input_events ( self ) : <EOL> return [ e for e in self . _events_list if isinstance ( e , InputEvent ) and e . prunable ] <EOL> @ property <EOL> def atomic_input_events ( self ) : <EOL> return self . _atomic_input_events ( self . input_events ) <EOL> def _get_event ( self , label ) : <EOL> if label not in self . _label2event : <EOL> raise ValueError ( "<STR_LIT>" % str ( label ) ) <EOL> return self . _label2event [ label ] <EOL> def _atomic_input_events ( self , inputs ) : <EOL> skipped_recoveries = set ( ) <EOL> atomic_inputs = [ ] <EOL> for e in inputs : <EOL> if e in skipped_recoveries : <EOL> continue <EOL> if type ( e ) in self . _failure_types and e . dependent_labels != [ ] : <EOL> recoveries = [ ] <EOL> for label in e . dependent_labels : <EOL> recovery = self . _label2event [ label ] <EOL> skipped_recoveries . add ( recovery ) <EOL> recoveries . append ( recovery ) <EOL> atomic_inputs . append ( AtomicInput ( e , recoveries ) ) <EOL> else : <EOL> atomic_inputs . append ( e ) <EOL> return atomic_inputs <EOL> def _expand_atomics ( self , atomic_inputs ) : <EOL> inputs = [ ] <EOL> for e in atomic_inputs : <EOL> if type ( e ) == AtomicInput : <EOL> inputs . append ( e . failure ) <EOL> for recovery in e . recoveries : <EOL> inputs . append ( recovery ) <EOL> else : <EOL> inputs . append ( e ) <EOL> inputs . sort ( key = lambda e : self . _event2idx [ e ] ) <EOL> return inputs <EOL> def filter_unsupported_input_types ( self ) : <EOL> return EventDagView ( self , ( e for e in self . _events_list <EOL> if type ( e ) not in self . _ignored_input_types ) ) <EOL> def compute_remaining_input_events ( self , ignored_portion , events_list = None ) : <EOL> '''<STR_LIT>''' <EOL> if events_list is None : <EOL> events_list = self . events <EOL> remaining = [ ] <EOL> for event in events_list : <EOL> if event not in ignored_portion : <EOL> remaining . append ( event ) <EOL> else : <EOL> for label in event . dependent_labels : <EOL> dependent_event = self . _label2event [ label ] <EOL> ignored_portion . add ( dependent_event ) <EOL> self . update_migrations ( remaining , ignored_portion , events_list ) <EOL> return remaining <EOL> def update_migrations ( self , remaining , ignored_portion , events_list ) : <EOL> '''<STR_LIT>''' <EOL> currentloc2unprunedloc = { } <EOL> for m in [ e for e in events_list if type ( e ) == HostMigration ] : <EOL> src = m . old_location <EOL> dst = m . new_location <EOL> if m in ignored_portion : <EOL> if src in currentloc2unprunedloc : <EOL> unprunedlocation = currentloc2unprunedloc [ src ] <EOL> del currentloc2unprunedloc [ src ] <EOL> currentloc2unprunedloc [ dst ] = unprunedlocation <EOL> else : <EOL> currentloc2unprunedloc [ dst ] = src <EOL> else : <EOL> if src in currentloc2unprunedloc : <EOL> unpruned_loc = currentloc2unprunedloc [ src ] <EOL> del currentloc2unprunedloc [ src ] <EOL> new_loc = dst <EOL> replace_migration ( m , unpruned_loc , new_loc , remaining ) <EOL> def _ignored_except_internals_and_recoveries ( self , ignored_portion ) : <EOL> return set ( e for e in ignored_portion <EOL> if ( isinstance ( e , InputEvent ) and e . prunable and <EOL> type ( e ) not in self . _recovery_types ) ) <EOL> def _ignored_except_internals ( self , ignored_portion ) : <EOL> return set ( e for e in ignored_portion if isinstance ( e , InputEvent ) and <EOL> e . prunable ) <EOL> def input_subset ( self , subset ) : <EOL> '''<STR_LIT>''' <EOL> ignored = self . _events_set - set ( subset ) <EOL> ignored = self . _ignored_except_internals_and_recoveries ( ignored ) <EOL> remaining_events = self . compute_remaining_input_events ( ignored ) <EOL> return EventDagView ( self , remaining_events ) <EOL> def atomic_input_subset ( self , subset ) : <EOL> '''<STR_LIT>''' <EOL> subset = self . _expand_atomics ( subset ) <EOL> ignored = self . _events_set - set ( subset ) <EOL> ignored = self . _ignored_except_internals ( ignored ) <EOL> remaining_events = self . compute_remaining_input_events ( ignored ) <EOL> return EventDagView ( self , remaining_events ) <EOL> def input_complement ( self , subset , events_list = None ) : <EOL> '''<STR_LIT>''' <EOL> subset = self . _ignored_except_internals_and_recoveries ( subset ) <EOL> remaining_events = self . compute_remaining_input_events ( subset , events_list ) <EOL> return EventDagView ( self , remaining_events ) <EOL> def _straighten_inserted_migrations ( self , remaining_events ) : <EOL> '''<STR_LIT>''' <EOL> host2migrations = migrations_per_host ( remaining_events ) <EOL> for host , migrations in host2migrations . iteritems ( ) : <EOL> previous_location = self . _host2initial_location [ host ] <EOL> for m in migrations : <EOL> if m . old_location != previous_location : <EOL> replacement = replace_migration ( m , previous_location , <EOL> m . new_location , remaining_events ) <EOL> else : <EOL> replacement = m <EOL> previous_location = replacement . new_location <EOL> return remaining_events <EOL> def insert_atomic_inputs ( self , atomic_inputs , events_list = None ) : <EOL> '''<STR_LIT>''' <EOL> if events_list is None : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> inputs = self . _expand_atomics ( atomic_inputs ) <EOL> if not all ( e in self . _event2idx for e in inputs ) : <EOL> raise ValueError ( "<STR_LIT>" % <EOL> [ e for e in input if e not in self . _event2idx ] ) <EOL> if not all ( e in self . _event2idx for e in events_list ) : <EOL> raise ValueError ( "<STR_LIT>" % <EOL> [ e for e in events_list if e not in self . _event2idx ] ) <EOL> result = [ ] <EOL> for _ , successor in enumerate ( events_list ) : <EOL> orig_successor_idx = self . _event2idx [ successor ] <EOL> while len ( inputs ) > <NUM_LIT:0> and orig_successor_idx > self . _event2idx [ inputs [ <NUM_LIT:0> ] ] : <EOL> input = inputs . pop ( <NUM_LIT:0> ) <EOL> result . append ( input ) <EOL> result . append ( successor ) <EOL> result += inputs <EOL> result = self . _straighten_inserted_migrations ( result ) <EOL> return EventDagView ( self , result ) <EOL> def mark_invalid_input_sequences ( self ) : <EOL> '''<STR_LIT>''' <EOL> fingerprint2previousfailure = { } <EOL> for event in self . _events_list : <EOL> if hasattr ( event , '<STR_LIT>' ) : <EOL> fingerprint = event . fingerprint [ <NUM_LIT:1> : ] <EOL> if type ( event ) in self . _failure_types : <EOL> fingerprint2previousfailure [ fingerprint ] = event <EOL> elif type ( event ) in self . _recovery_types : <EOL> if fingerprint in fingerprint2previousfailure : <EOL> failure = fingerprint2previousfailure [ fingerprint ] <EOL> failure . dependent_labels . append ( event . label ) <EOL> def next_state_change ( self , index , events = None ) : <EOL> '''<STR_LIT>''' <EOL> if events is None : <EOL> events = self . events <EOL> for event in events [ index : ] : <EOL> if type ( event ) == ControllerStateChange : <EOL> return event <EOL> return None <EOL> def get_original_index_for_event ( self , event ) : <EOL> return self . _event2idx [ event ] <EOL> def __len__ ( self ) : <EOL> return len ( self . _events_list ) <EOL> def get_last_invariant_violation ( self ) : <EOL> if self . _last_violation is not None : <EOL> return self . _last_violation <EOL> for event in reversed ( self . _events_list ) : <EOL> if type ( event ) == InvariantViolation and event . persistent : <EOL> self . _last_violation = event <EOL> return event <EOL> return None <EOL> def set_events_as_timed_out ( self , timed_out_event_labels ) : <EOL> for event in self . _events_list : <EOL> event . timed_out = False <EOL> for label in timed_out_event_labels : <EOL> self . _get_event ( label ) . timed_out = True <EOL> def filter_timeouts ( self , events_list = None ) : <EOL> if events_list is None : <EOL> events_list = self . _events_list <EOL> no_timeouts = [ e for e in events_list if not e . timed_out ] <EOL> return EventDagView ( self , no_timeouts ) </s>
