music-core/src/main/java/org/onap/music/main/DeadlockDetectionUtil.java

   1 /*
   2  * ============LICENSE_START==========================================
   3  * org.onap.music
   4  * ===================================================================
   5  *  Copyright (c) 2019 AT&T Intellectual Property
   6  * ===================================================================
   7  *  Licensed under the Apache License, Version 2.0 (the "License");
   8  *  you may not use this file except in compliance with the License.
   9  *  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  *  Unless required by applicable law or agreed to in writing, software
  14  *  distributed under the License is distributed on an "AS IS" BASIS,
  15  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  *  See the License for the specific language governing permissions and
  17  *  limitations under the License.
  18  *
  19  * ============LICENSE_END=============================================
  20  * ====================================================================
  21  */
  22 package org.onap.music.main;
  23
  24 import java.util.ArrayList;
  25 import java.util.HashMap;
  26 import java.util.List;
  27 import java.util.Map;
  28
  29 public class DeadlockDetectionUtil {
  30         private Map<String, Node> nodeList = null;
  31         public enum OwnershipType {NONE, CREATED, ACQUIRED};
  32
  33         private class Node implements Comparable<Node> {
  34                 private String id;
  35                 private List<Node> links;
  36                 private boolean visited = false;
  37                 private boolean onStack = false;
  38
  39                 @Override
  40                 public String toString() {
  41                         StringBuffer sb = new StringBuffer();
  42                         for (Node link : links) sb.append(link.id);
  43                         return "Node [id=" + id + ", links=" + sb.toString() + ", visited=" + visited + ", onStack=" + onStack + "]";
  44                 }
  45
  46                 public Node(String id) {
  47                         super();
  48                         this.id = id;
  49                         this.links = new ArrayList<Node>();
  50                 }
  51
  52                 public List<Node> getLinks() {
  53                         return links;
  54                 }
  55
  56                 public void addLink(Node link) {
  57                         this.links.add(link);
  58                 }
  59
  60                 public void removeLink(Node link) {
  61                         this.links.remove(link);
  62                 }
  63
  64                 public boolean isVisited() {
  65                         return visited;
  66                 }
  67
  68                 public boolean isOnStack() {
  69                         return onStack;
  70                 }
  71
  72                 public void setVisited(boolean visited) {
  73                         this.visited = visited;
  74                 }
  75
  76                 public void setOnStack(boolean onStack) {
  77                         this.onStack = onStack;
  78                 }
  79
  80                 @Override
  81                 public int compareTo(Node arg0) {
  82                         return id.compareTo(arg0.id);
  83                 }
  84         }
  85
  86         public DeadlockDetectionUtil() {
  87                 this.nodeList = new HashMap<String, Node>();
  88         }
  89
  90         public void listAllNodes() {
  91                 System.out.println("In DeadlockDetectionUtil: ");
  92                 for (String key : nodeList.keySet()) {
  93                         System.out.println("    " + key + " : " + nodeList.get(key));
  94                 }
  95         }
  96
  97         public boolean checkForDeadlock(String resource, String owner, OwnershipType operation) {
  98                 setExisting(resource, owner, operation);
  99
 100                 Node currentNode = null;
 101                 if (operation.equals(OwnershipType.ACQUIRED)) {
 102                         currentNode = nodeList.get("r" + resource);
 103                 } else if (operation.equals(OwnershipType.CREATED)) {
 104                         currentNode = nodeList.get("o" + owner);
 105                 }
 106
 107                 boolean cycle = findCycle(currentNode);
 108                 return cycle;
 109         }
 110
 111         private boolean findCycle(Node currentNode) {
 112                 if (currentNode==null) return false;
 113                 if (currentNode.isOnStack()) return true;
 114                 if (currentNode.isVisited()) return false;
 115                 currentNode.setOnStack(true);
 116                 currentNode.setVisited(true);
 117                 for (Node childNode : currentNode.getLinks()) {
 118                         if (findCycle(childNode)) return true;
 119                 }
 120                 currentNode.setOnStack(false);
 121                 return false;
 122         }
 123
 124         public void setExisting(String resource, String owner, OwnershipType operation) {
 125                 String resourceKey = "r" + resource;
 126                 Node resourceNode = nodeList.get(resourceKey);
 127                 if (resourceNode==null) {
 128                         resourceNode = new Node(resourceKey);
 129                         nodeList.put(resourceKey, resourceNode);
 130                 }
 131
 132                 String ownerKey = "o" + owner;
 133                 Node ownerNode = nodeList.get(ownerKey);
 134                 if (ownerNode==null) {
 135                         ownerNode = new Node(ownerKey);
 136                         nodeList.put(ownerKey, ownerNode);
 137                 }
 138
 139                 if (operation.equals(OwnershipType.ACQUIRED)) {
 140                         resourceNode.addLink(ownerNode);
 141                         ownerNode.removeLink(resourceNode);
 142                 } else if (operation.equals(OwnershipType.CREATED)) {
 143                         ownerNode.addLink(resourceNode);
 144                         resourceNode.removeLink(ownerNode);
 145                 }
 146         }
 147
 148 }