1#!/usr/bin/env python3 2# -*- coding: utf-8 -*- 3 4# Copyright (c) 2021 Huawei Device Co., Ltd. 5# Licensed under the Apache License, Version 2.0 (the "License"); 6# you may not use this file except in compliance with the License. 7# You may obtain a copy of the License at 8# 9# http://www.apache.org/licenses/LICENSE-2.0 10# 11# Unless required by applicable law or agreed to in writing, software 12# distributed under the License is distributed on an "AS IS" BASIS, 13# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14# See the License for the specific language governing permissions and 15# limitations under the License. 16from collections import OrderedDict 17 18from log_exception import UPDATE_LOGGER 19 20# 50% of the data partition, in KB x 1024. 21DATA_SIZE = 1374024 * 1024 22 23 24class GigraphProcess(object): 25 def __init__(self, actions_list, src_image, tgt_image): 26 self.actions_list = actions_list 27 if len(self.actions_list) == 0: 28 raise RuntimeError 29 self.size_of_source_list = 0 30 self.src_img_obj = src_image 31 self.tgt_img_obj = tgt_image 32 self.vertices = len(self.actions_list) 33 self.data_size = DATA_SIZE 34 35 self.generate_digraph() 36 self.stash_process() 37 38 def generate_digraph(self): 39 """ 40 Start correlation lookup. 41 """ 42 source_ranges = [] 43 source_ranges = \ 44 self.get_source_ranges(self.actions_list, source_ranges) 45 46 self.get_intersections_dict(source_ranges) 47 # Start ordering. 48 topo_logical = TopoLogical(self) 49 action_stack = topo_logical.stack() 50 new_action_list = [] 51 for action in action_stack: 52 action.order = len(new_action_list) 53 new_action_list.append(action) 54 self.actions_list = new_action_list 55 56 def get_intersections_dict(self, source_ranges): 57 """ 58 Get the intersections_dict. 59 :param source_ranges: source blocks 60 :return: 61 """ 62 for each_action in self.actions_list: 63 intersections = OrderedDict() 64 for start_value, end_value in each_action.tgt_block_set: 65 for i in range(start_value, end_value): 66 if i >= len(source_ranges): 67 break 68 if source_ranges[i] is not None: 69 for j in source_ranges[i]: 70 intersections[j] = None 71 72 self.update_goes_before_and_after(each_action, intersections) 73 74 @staticmethod 75 def update_goes_before_and_after(each_action, intersections): 76 """ 77 Update "goes before" and "goes after". 78 :param each_action: action to be processed 79 :param intersections: intersections dict 80 :return: 81 """ 82 for each_intersection in intersections: 83 if each_action is each_intersection: 84 continue 85 86 intersect_range = \ 87 each_action.tgt_block_set.get_intersect_with_other( 88 each_intersection.src_block_set) 89 if intersect_range: 90 if each_intersection.src_name == "__ZERO": 91 size = 0 92 else: 93 size = intersect_range.size() 94 each_intersection.child[each_action] = size 95 each_action.parent[each_intersection] = size 96 97 @staticmethod 98 def get_source_ranges(transfers, source_ranges): 99 """ 100 Update "goes before" and "goes after". 101 :param transfers: actions list 102 :param source_ranges: source blocks 103 :return: 104 """ 105 for each_action in transfers: 106 for start_value, end_value in each_action.src_block_set: 107 if end_value > len(source_ranges): 108 source_ranges.extend( 109 [None] * (end_value - len(source_ranges))) 110 for i in range(start_value, end_value): 111 if source_ranges[i] is None: 112 source_ranges[i] = \ 113 OrderedDict.fromkeys([each_action]) 114 else: 115 source_ranges[i][each_action] = None 116 return source_ranges 117 118 def stash_process(self): 119 """ 120 Stash processing 121 """ 122 UPDATE_LOGGER.print_log("Reversing backward edges...") 123 stash_raw_id = 0 124 for each_action in self.actions_list: 125 each_child_dict = each_action.child.copy() 126 for each_before in each_child_dict: 127 if each_action.order >= each_before.order: 128 intersect_block_set = \ 129 each_action.src_block_set.get_intersect_with_other( 130 each_before.tgt_block_set) 131 132 each_before.stash_before.append( 133 (stash_raw_id, intersect_block_set)) 134 each_action.use_stash.append( 135 (stash_raw_id, intersect_block_set)) 136 stash_raw_id += 1 137 each_action.child.pop(each_before) 138 each_before.parent.pop(each_action) 139 each_action.parent[each_before] = None 140 each_before.child[each_action] = None 141 UPDATE_LOGGER.print_log("Reversing backward edges completed!") 142 143 144class DirectedCycle(object): 145 def __init__(self, graph): 146 self.graph = graph 147 self.marked = [False for _ in range(self.graph.vertices)] 148 self.has_cycle = False 149 self.ontrack = [False for _ in range(self.graph.vertices)] 150 151 152class DepthFirstOrder: 153 def __init__(self, graph): 154 self.graph = graph 155 self.marked = {} 156 self.stack = [] 157 158 for each_action in self.graph.actions_list: 159 self.marked[each_action] = False 160 161 def dfs(self): 162 def dfs(index): 163 self.marked[index] = True 164 for each_child in index.child: 165 if not self.marked[each_child]: 166 dfs(each_child) 167 self.stack.insert(0, index) 168 169 for each_action in self.graph.actions_list: 170 if not self.marked[each_action]: 171 dfs(each_action) 172 return self.stack 173 174 def sort_vertices(self): 175 return self.dfs() 176 177 178class TopoLogical(object): 179 def __init__(self, graph): 180 self.order = None 181 self.cycle = DirectedCycle(graph) 182 if not self.cycle.has_cycle: 183 dfo = DepthFirstOrder(graph) 184 self.order = dfo.sort_vertices() 185 186 def stack(self): 187 return self.order 188