gerrit.opnfv Code Review - onosfw.git/blob

   1 /*
   2  * Copyright 2015 Open Networking Laboratory
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.onosproject.net.flowobjective.impl.composition;
  17
  18 import org.onlab.packet.IpPrefix;
  19 import org.onosproject.net.flow.DefaultTrafficSelector;
  20 import org.onosproject.net.flow.DefaultTrafficTreatment;
  21 import org.onosproject.net.flow.TrafficSelector;
  22 import org.onosproject.net.flow.TrafficTreatment;
  23 import org.onosproject.net.flow.criteria.Criterion;
  24 import org.onosproject.net.flow.criteria.LambdaCriterion;
  25 import org.onosproject.net.flow.criteria.OchSignalCriterion;
  26 import org.onosproject.net.flow.criteria.EthCriterion;
  27 import org.onosproject.net.flow.criteria.VlanIdCriterion;
  28 import org.onosproject.net.flow.criteria.VlanPcpCriterion;
  29 import org.onosproject.net.flow.criteria.MplsCriterion;
  30 import org.onosproject.net.flow.criteria.IPCriterion;
  31 import org.onosproject.net.flow.criteria.IPv6FlowLabelCriterion;
  32 import org.onosproject.net.flow.criteria.Criteria;
  33 import org.onosproject.net.flow.instructions.Instruction;
  34 import org.onosproject.net.flow.instructions.L0ModificationInstruction;
  35 import org.onosproject.net.flow.instructions.L2ModificationInstruction;
  36 import org.onosproject.net.flow.instructions.L3ModificationInstruction;
  37 import org.onosproject.net.flowobjective.DefaultForwardingObjective;
  38 import org.onosproject.net.flowobjective.ForwardingObjective;
  39
  40 import java.util.ArrayList;
  41 import java.util.Collection;
  42 import java.util.HashMap;
  43 import java.util.HashSet;
  44 import java.util.List;
  45 import java.util.Map;
  46 import java.util.Set;
  47 import java.util.Stack;
  48
  49 /**
  50  * Provide util functions for FlowObjectiveComposition.
  51  */
  52 public final class FlowObjectiveCompositionUtil {
  53
  54     private FlowObjectiveCompositionUtil() {}
  55
  56     // only work with VERSATILE
  57     public static ForwardingObjective composeParallel(ForwardingObjective fo1, ForwardingObjective fo2) {
  58
  59         TrafficSelector trafficSelector = intersectTrafficSelector(fo1.selector(), fo2.selector());
  60         if (trafficSelector == null) {
  61             return null;
  62         }
  63
  64         TrafficTreatment trafficTreatment = unionTrafficTreatment(fo1.treatment(), fo2.treatment());
  65
  66         return DefaultForwardingObjective.builder()
  67                 .fromApp(fo1.appId())
  68                 .makePermanent()
  69                 .withFlag(ForwardingObjective.Flag.VERSATILE)
  70                 .withPriority(fo1.priority() + fo2.priority())
  71                 .withSelector(trafficSelector)
  72                 .withTreatment(trafficTreatment)
  73                 .add();
  74     }
  75
  76     public static ForwardingObjective composeSequential(ForwardingObjective fo1,
  77                                                         ForwardingObjective fo2,
  78                                                         int priorityMultiplier) {
  79
  80         TrafficSelector revertTrafficSelector = revertTreatmentSelector(fo1.treatment(), fo2.selector());
  81         if (revertTrafficSelector == null) {
  82             return null;
  83         }
  84
  85         TrafficSelector trafficSelector = intersectTrafficSelector(fo1.selector(), revertTrafficSelector);
  86         if (trafficSelector == null) {
  87             return null;
  88         }
  89
  90         TrafficTreatment trafficTreatment = unionTrafficTreatment(fo1.treatment(), fo2.treatment());
  91
  92         return DefaultForwardingObjective.builder()
  93                 .fromApp(fo1.appId())
  94                 .makePermanent()
  95                 .withFlag(ForwardingObjective.Flag.VERSATILE)
  96                 .withPriority(fo1.priority() * priorityMultiplier + fo2.priority())
  97                 .withSelector(trafficSelector)
  98                 .withTreatment(trafficTreatment)
  99                 .add();
 100     }
 101
 102     public static ForwardingObjective composeOverride(ForwardingObjective fo, int priorityAddend) {
 103         return DefaultForwardingObjective.builder()
 104                 .fromApp(fo.appId())
 105                 .makePermanent()
 106                 .withFlag(fo.flag())
 107                 .withPriority(fo.priority() + priorityAddend)
 108                 .withSelector(fo.selector())
 109                 .withTreatment(fo.treatment())
 110                 .add();
 111     }
 112
 113     public static TrafficSelector intersectTrafficSelector(TrafficSelector ts1, TrafficSelector ts2) {
 114
 115         TrafficSelector.Builder selectorBuilder = DefaultTrafficSelector.builder();
 116
 117         Set<Criterion.Type> ts1IntersectTs2 = getTypeSet(ts1);
 118         ts1IntersectTs2.retainAll(getTypeSet(ts2));
 119         for (Criterion.Type type : ts1IntersectTs2) {
 120             Criterion criterion = intersectCriterion(ts1.getCriterion(type), ts2.getCriterion(type));
 121             if (criterion == null) {
 122                 return null;
 123             } else {
 124                 selectorBuilder.add(criterion);
 125             }
 126         }
 127
 128         Set<Criterion.Type> ts1MinusTs2 = getTypeSet(ts1);
 129         ts1MinusTs2.removeAll(getTypeSet(ts2));
 130         for (Criterion.Type type : ts1MinusTs2) {
 131             selectorBuilder.add(ts1.getCriterion(type));
 132         }
 133
 134         Set<Criterion.Type> ts2MinusTs1 = getTypeSet(ts2);
 135         ts2MinusTs1.removeAll(getTypeSet(ts1));
 136         for (Criterion.Type type : ts2MinusTs1) {
 137             selectorBuilder.add(ts2.getCriterion(type));
 138         }
 139
 140         return selectorBuilder.build();
 141     }
 142
 143     public static TrafficTreatment unionTrafficTreatment(TrafficTreatment tt1, TrafficTreatment tt2) {
 144
 145         TrafficTreatment.Builder treatmentBuilder = DefaultTrafficTreatment.builder();
 146
 147         for (Instruction instruction : tt1.allInstructions()) {
 148             treatmentBuilder.add(instruction);
 149         }
 150
 151         for (Instruction instruction : tt2.allInstructions()) {
 152             treatmentBuilder.add(instruction);
 153         }
 154
 155         return treatmentBuilder.build();
 156     }
 157
 158     public static TrafficSelector revertTreatmentSelector(TrafficTreatment trafficTreatment,
 159                                                           TrafficSelector trafficSelector) {
 160
 161         TrafficSelector.Builder selectorBuilder = DefaultTrafficSelector.builder();
 162
 163         Map<Criterion.Type, Criterion> criterionMap = new HashMap<>();
 164         for (Criterion criterion : trafficSelector.criteria()) {
 165             criterionMap.put(criterion.type(), criterion);
 166         }
 167
 168         for (Instruction instruction : trafficTreatment.allInstructions()) {
 169             switch (instruction.type()) {
 170                 case DROP:
 171                     return null;
 172                 case OUTPUT:
 173                     break;
 174                 case GROUP:
 175                     break;
 176                 case L0MODIFICATION: {
 177                     L0ModificationInstruction l0 = (L0ModificationInstruction) instruction;
 178                     switch (l0.subtype()) {
 179                         case LAMBDA:
 180                             if (criterionMap.containsKey(Criterion.Type.OCH_SIGID)) {
 181                                 if (((LambdaCriterion) criterionMap.get((Criterion.Type.OCH_SIGID))).lambda()
 182                                         == ((L0ModificationInstruction.ModLambdaInstruction) l0).lambda()) {
 183                                     criterionMap.remove(Criterion.Type.OCH_SIGID);
 184                                 } else {
 185                                     return null;
 186                                 }
 187                             } else {
 188                                 break;
 189                             }
 190                         case OCH:
 191                             if (criterionMap.containsKey(Criterion.Type.OCH_SIGID)) {
 192                                 if (((OchSignalCriterion) criterionMap.get((Criterion.Type.OCH_SIGID))).lambda()
 193                                         .equals(((L0ModificationInstruction.ModOchSignalInstruction) l0).lambda())) {
 194                                     criterionMap.remove(Criterion.Type.OCH_SIGID);
 195                                 } else {
 196                                     return null;
 197                                 }
 198                             } else {
 199                                 break;
 200                             }
 201                         default:
 202                             break;
 203                     }
 204                     break;
 205                 }
 206                 case L2MODIFICATION: {
 207                     L2ModificationInstruction l2 = (L2ModificationInstruction) instruction;
 208                     switch (l2.subtype()) {
 209                         case ETH_SRC:
 210                             if (criterionMap.containsKey(Criterion.Type.ETH_SRC)) {
 211                                 if (((EthCriterion) criterionMap.get((Criterion.Type.ETH_SRC))).mac()
 212                                         .equals(((L2ModificationInstruction.ModEtherInstruction) l2).mac())) {
 213                                     criterionMap.remove(Criterion.Type.ETH_SRC);
 214                                 } else {
 215                                     return null;
 216                                 }
 217                             } else {
 218                                 break;
 219                             }
 220                         case ETH_DST:
 221                             if (criterionMap.containsKey(Criterion.Type.ETH_DST)) {
 222                                 if (((EthCriterion) criterionMap.get((Criterion.Type.ETH_DST))).mac()
 223                                         .equals(((L2ModificationInstruction.ModEtherInstruction) l2).mac())) {
 224                                     criterionMap.remove(Criterion.Type.ETH_DST);
 225                                 } else {
 226                                     return null;
 227                                 }
 228                             } else {
 229                                 break;
 230                             }
 231                         case VLAN_ID:
 232                             if (criterionMap.containsKey(Criterion.Type.VLAN_VID)) {
 233                                 if (((VlanIdCriterion) criterionMap.get((Criterion.Type.VLAN_VID))).vlanId()
 234                                         .equals(((L2ModificationInstruction.ModVlanIdInstruction) l2).vlanId())) {
 235                                     criterionMap.remove(Criterion.Type.VLAN_VID);
 236                                 } else {
 237                                     return null;
 238                                 }
 239                             } else {
 240                                 break;
 241                             }
 242                         case VLAN_PCP:
 243                             if (criterionMap.containsKey(Criterion.Type.VLAN_PCP)) {
 244                                 if (((VlanPcpCriterion) criterionMap.get((Criterion.Type.VLAN_PCP))).priority()
 245                                         == ((L2ModificationInstruction.ModVlanPcpInstruction) l2).vlanPcp()) {
 246                                     criterionMap.remove(Criterion.Type.VLAN_PCP);
 247                                 } else {
 248                                     return null;
 249                                 }
 250                             } else {
 251                                 break;
 252                             }
 253                         case MPLS_LABEL:
 254                             if (criterionMap.containsKey(Criterion.Type.MPLS_LABEL)) {
 255                                 if (((MplsCriterion) criterionMap.get((Criterion.Type.MPLS_LABEL))).label()
 256                                         .equals(((L2ModificationInstruction.ModMplsLabelInstruction) l2).mplsLabel())) {
 257                                     criterionMap.remove(Criterion.Type.ETH_DST);
 258                                 } else {
 259                                     return null;
 260                                 }
 261                             } else {
 262                                 break;
 263                             }
 264                         default:
 265                             break;
 266                     }
 267                     break;
 268                 }
 269                 case TABLE:
 270                     break;
 271                 case L3MODIFICATION: {
 272                     L3ModificationInstruction l3 = (L3ModificationInstruction) instruction;
 273                     switch (l3.subtype()) {
 274                         case IPV4_SRC:
 275                             if (criterionMap.containsKey(Criterion.Type.IPV4_SRC)) {
 276                                 if (((IPCriterion) criterionMap.get(Criterion.Type.IPV4_SRC)).ip()
 277                                         .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) {
 278                                     criterionMap.remove(Criterion.Type.IPV4_SRC);
 279                                 } else {
 280                                     return null;
 281                                 }
 282                             } else {
 283                                 break;
 284                             }
 285                         case IPV4_DST:
 286                             if (criterionMap.containsKey(Criterion.Type.IPV4_DST)) {
 287                                 if (((IPCriterion) criterionMap.get(Criterion.Type.IPV4_DST)).ip()
 288                                         .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) {
 289                                     criterionMap.remove(Criterion.Type.IPV4_DST);
 290                                 } else {
 291                                     return null;
 292                                 }
 293                             } else {
 294                                 break;
 295                             }
 296                         case IPV6_SRC:
 297                             if (criterionMap.containsKey(Criterion.Type.IPV6_SRC)) {
 298                                 if (((IPCriterion) criterionMap.get(Criterion.Type.IPV6_SRC)).ip()
 299                                         .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) {
 300                                     criterionMap.remove(Criterion.Type.IPV6_SRC);
 301                                 } else {
 302                                     return null;
 303                                 }
 304                             } else {
 305                                 break;
 306                             }
 307                         case IPV6_DST:
 308                             if (criterionMap.containsKey(Criterion.Type.IPV6_DST)) {
 309                                 if (((IPCriterion) criterionMap.get(Criterion.Type.IPV6_DST)).ip()
 310                                         .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) {
 311                                     criterionMap.remove(Criterion.Type.IPV6_DST);
 312                                 } else {
 313                                     return null;
 314                                 }
 315                             } else {
 316                                 break;
 317                             }
 318                         case IPV6_FLABEL:
 319                             if (criterionMap.containsKey(Criterion.Type.IPV6_FLABEL)) {
 320                                 if (((IPv6FlowLabelCriterion) criterionMap.get(Criterion.Type.IPV6_FLABEL)).flowLabel()
 321                                         == (((L3ModificationInstruction.ModIPv6FlowLabelInstruction) l3).flowLabel())) {
 322                                     criterionMap.remove(Criterion.Type.IPV4_SRC);
 323                                 } else {
 324                                     return null;
 325                                 }
 326                             } else {
 327                                 break;
 328                             }
 329                         default:
 330                             break;
 331                     }
 332                     break;
 333                 }
 334                 case METADATA:
 335                     break;
 336                 default:
 337                     break;
 338             }
 339         }
 340
 341         for (Criterion criterion : criterionMap.values()) {
 342             selectorBuilder.add(criterion);
 343         }
 344
 345         return selectorBuilder.build();
 346     }
 347
 348     public static Set<Criterion.Type> getTypeSet(TrafficSelector trafficSelector) {
 349         Set<Criterion.Type> typeSet = new HashSet<>();
 350         for (Criterion criterion : trafficSelector.criteria()) {
 351             typeSet.add(criterion.type());
 352         }
 353         return typeSet;
 354     }
 355
 356     public static Criterion intersectCriterion(Criterion c1, Criterion c2) {
 357         switch (c1.type()) {
 358             case IPV4_SRC: {
 359                 IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip());
 360                 if (ipPrefix == null) {
 361                     return null;
 362                 } else {
 363                     return Criteria.matchIPSrc(ipPrefix);
 364                 }
 365             }
 366             case IPV4_DST: {
 367                 IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip());
 368                 if (ipPrefix == null) {
 369                     return null;
 370                 } else {
 371                     return Criteria.matchIPDst(ipPrefix);
 372                 }
 373             }
 374             case IPV6_SRC: {
 375                 IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip());
 376                 if (ipPrefix == null) {
 377                     return null;
 378                 } else {
 379                     return Criteria.matchIPv6Src(ipPrefix);
 380                 }
 381             }
 382             case IPV6_DST: {
 383                 IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip());
 384                 if (ipPrefix == null) {
 385                     return null;
 386                 } else {
 387                     return Criteria.matchIPv6Dst(ipPrefix);
 388                 }
 389             }
 390             default:
 391                 if (!c1.equals(c2)) {
 392                     return null;
 393                 } else {
 394                     return c1;
 395                 }
 396         }
 397     }
 398
 399     public static IpPrefix intersectIpPrefix(IpPrefix ip1, IpPrefix ip2) {
 400         if (ip1.contains(ip2)) {
 401             return ip1;
 402         } else if (ip2.contains(ip1)) {
 403             return ip2;
 404         } else {
 405             return null;
 406         }
 407     }
 408
 409     public static FlowObjectiveCompositionTree parsePolicyString(String policy) {
 410         List<FlowObjectiveCompositionTree> postfix = transformToPostfixForm(policy);
 411         return buildPolicyTree(postfix);
 412     }
 413
 414     private static List<FlowObjectiveCompositionTree> transformToPostfixForm(String policy) {
 415         Stack<Character> stack = new Stack<>();
 416         List<FlowObjectiveCompositionTree> postfix = new ArrayList<>();
 417
 418         for (int i = 0; i < policy.length(); i++) {
 419             Character ch = policy.charAt(i);
 420             if (Character.isDigit(ch)) {
 421
 422                 int applicationId = ch - '0';
 423                 while (i + 1 < policy.length() && Character.isDigit(policy.charAt(i + 1))) {
 424                     i++;
 425                     applicationId = applicationId * 10 + policy.charAt(i) - '0';
 426                 }
 427
 428                 postfix.add(new FlowObjectiveCompositionTree((short) applicationId));
 429             } else if (ch == '(') {
 430                 stack.push(ch);
 431             } else if (ch == ')') {
 432                 while (stack.peek() != '(') {
 433                     postfix.add(new FlowObjectiveCompositionTree(stack.pop()));
 434                 }
 435                 stack.pop();
 436             } else {
 437                 while (!stack.isEmpty() && compareOperatorPriority(stack.peek(), ch)) {
 438                     postfix.add(new FlowObjectiveCompositionTree(stack.pop()));
 439                 }
 440                 stack.push(ch);
 441             }
 442         }
 443         while (!stack.isEmpty()) {
 444             postfix.add(new FlowObjectiveCompositionTree(stack.pop()));
 445         }
 446
 447         return postfix;
 448     }
 449
 450     private static boolean compareOperatorPriority(char peek, char cur) {
 451         if (peek == '/' && (cur == '+' || cur == '>' || cur == '/')) {
 452             return true;
 453         } else if (peek == '>' && (cur == '+' || cur == '>')) {
 454             return true;
 455         } else if (peek == '+' && cur == '+') {
 456             return true;
 457         }
 458         return false;
 459     }
 460
 461     private static FlowObjectiveCompositionTree buildPolicyTree(List<FlowObjectiveCompositionTree> postfix) {
 462         Stack<FlowObjectiveCompositionTree> stack = new Stack<>();
 463         for (FlowObjectiveCompositionTree node : postfix) {
 464             if (node.operator == FlowObjectiveCompositionManager.PolicyOperator.Application) {
 465                 stack.push(node);
 466             } else {
 467                 node.rightChild = stack.pop();
 468                 node.leftChild = stack.pop();
 469                 stack.push(node);
 470             }
 471         }
 472         return stack.pop();
 473     }
 474
 475     public static Collection<ForwardingObjective> minusForwardingObjectives(Collection<ForwardingObjective> fo1,
 476                                                                             Collection<ForwardingObjective> fo2) {
 477         Map<Integer, ForwardingObjective> map = new HashMap<>();
 478         for (ForwardingObjective fo : fo1) {
 479             map.put(fo.id(), fo);
 480         }
 481         for (ForwardingObjective fo : fo2) {
 482             map.remove(fo.id());
 483         }
 484         return map.values();
 485     }
 486
 487
 488 }