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 37 def generate_digraph(self): 38 """ 39 Start correlation lookup. 40 """ 41 source_ranges = [] 42 source_ranges = \ 43 self.get_source_ranges(self.actions_list, source_ranges) 44 45 self.get_intersections_dict(source_ranges) 46 # Start ordering. 47 topo_logical = TopoLogical(self) 48 action_stack = topo_logical.stack() 49 new_action_list = [] 50 for action in action_stack: 51 action.order = len(new_action_list) 52 new_action_list.append(action) 53 self.actions_list = new_action_list 54 55 def get_intersections_dict(self, source_ranges): 56 """ 57 Get the intersections_dict. 58 :param source_ranges: source blocks 59 :return: 60 """ 61 for each_action in self.actions_list: 62 intersections = OrderedDict() 63 for start_value, end_value in each_action.tgt_block_set: 64 for i in range(start_value, end_value): 65 if i >= len(source_ranges): 66 break 67 if source_ranges[i] is not None: 68 for j in source_ranges[i]: 69 intersections[j] = None 70 71 self.update_goes_before_and_after(each_action, intersections) 72 73 @staticmethod 74 def update_goes_before_and_after(each_action, intersections): 75 """ 76 Update "goes before" and "goes after". 77 :param each_action: action to be processed 78 :param intersections: intersections dict 79 :return: 80 """ 81 for each_intersection in intersections: 82 if each_action is each_intersection: 83 continue 84 85 intersect_range = \ 86 each_action.tgt_block_set.get_intersect_with_other( 87 each_intersection.src_block_set) 88 if intersect_range: 89 if each_intersection.src_name == "__ZERO": 90 size = 0 91 else: 92 size = intersect_range.size() 93 each_intersection.child[each_action] = size 94 each_action.parent[each_intersection] = size 95 96 @staticmethod 97 def get_source_ranges(transfers, source_ranges): 98 """ 99 Update "goes before" and "goes after". 100 :param transfers: actions list 101 :param source_ranges: source blocks 102 :return: 103 """ 104 for each_action in transfers: 105 for start_value, end_value in each_action.src_block_set: 106 if end_value > len(source_ranges): 107 source_ranges.extend( 108 [None] * (end_value - len(source_ranges))) 109 for i in range(start_value, end_value): 110 if source_ranges[i] is None: 111 source_ranges[i] = \ 112 OrderedDict.fromkeys([each_action]) 113 else: 114 source_ranges[i][each_action] = None 115 return source_ranges 116 117 def stash_process(self): 118 """ 119 Stash processing 120 """ 121 UPDATE_LOGGER.print_log("Reversing backward edges...") 122 stash_raw_id = 0 123 for each_action in self.actions_list: 124 each_child_dict = each_action.child.copy() 125 for each_before in each_child_dict: 126 if each_action.order >= each_before.order: 127 intersect_block_set = \ 128 each_action.src_block_set.get_intersect_with_other( 129 each_before.tgt_block_set) 130 131 each_before.stash_before.append( 132 (stash_raw_id, intersect_block_set)) 133 each_action.use_stash.append( 134 (stash_raw_id, intersect_block_set)) 135 stash_raw_id += 1 136 each_action.child.pop(each_before) 137 each_before.parent.pop(each_action) 138 each_action.parent[each_before] = None 139 each_before.child[each_action] = None 140 UPDATE_LOGGER.print_log("Reversing backward edges completed!") 141 142 143class DirectedCycle(object): 144 def __init__(self, graph): 145 self.graph = graph 146 self.marked = [False for _ in range(self.graph.vertices)] 147 self.has_cycle = False 148 self.ontrack = [False for _ in range(self.graph.vertices)] 149 150 151class DepthFirstOrder: 152 def __init__(self, graph): 153 self.graph = graph 154 self.marked = {} 155 self.stack = [] 156 157 for each_action in self.graph.actions_list: 158 self.marked[each_action] = False 159 160 def dfs(self): 161 def dfs(index): 162 self.marked[index] = True 163 for each_child in index.child: 164 if not self.marked[each_child]: 165 dfs(each_child) 166 self.stack.insert(0, index) 167 168 for each_action in self.graph.actions_list: 169 if not self.marked[each_action]: 170 dfs(each_action) 171 return self.stack 172 173 def sort_vertices(self): 174 return self.dfs() 175 176 177class TopoLogical(object): 178 def __init__(self, graph): 179 self.order = None 180 self.cycle = DirectedCycle(graph) 181 if not self.cycle.has_cycle: 182 dfo = DepthFirstOrder(graph) 183 self.order = dfo.sort_vertices() 184 185 def stack(self): 186 return self.order 187