@Test public void testFindBlockingLines_AclAclLine() { Ip ip1 = Ip.parse("1.1.1.1"); Ip ip2 = Ip.parse("2.2.2.2"); Prefix prefix1 = Prefix.create(ip1, 24); Prefix prefix2 = Prefix.create(ip2, 24); HeaderSpaceToBDD headerSpaceToBDD = new HeaderSpaceToBDD(PKT, ImmutableMap.of()); BDD ip1Bdd = headerSpaceToBDD.toBDD(HeaderSpace.builder().setDstIps(ip1.toIpSpace()).build()); BDD ip2Bdd = headerSpaceToBDD.toBDD(HeaderSpace.builder().setDstIps(ip2.toIpSpace()).build()); BDD prefix1Bdd = headerSpaceToBDD.toBDD(HeaderSpace.builder().setDstIps(prefix1.toIpSpace()).build()); BDD prefix2Bdd = headerSpaceToBDD.toBDD(HeaderSpace.builder().setDstIps(prefix2.toIpSpace()).build()); List<PermitAndDenyBdds> permitAndDenyBdds = ImmutableList.of( new PermitAndDenyBdds(prefix1Bdd, prefix2Bdd), new PermitAndDenyBdds(ip1Bdd, ip2Bdd)); BlockingProperties blockingProperties = findBlockingPropsForLine(1, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(0)); assertFalse(blockingProperties.getDiffAction()); permitAndDenyBdds = ImmutableList.of( new PermitAndDenyBdds(prefix1Bdd.or(prefix2Bdd), ZERO), new PermitAndDenyBdds(ip1Bdd, ip2Bdd)); blockingProperties = findBlockingPropsForLine(1, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(0)); assertTrue(blockingProperties.getDiffAction()); permitAndDenyBdds = ImmutableList.of( new PermitAndDenyBdds(prefix1Bdd, prefix2Bdd), new PermitAndDenyBdds(ip1Bdd.or(ip2Bdd), ZERO)); blockingProperties = findBlockingPropsForLine(1, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(0)); assertTrue(blockingProperties.getDiffAction()); }
@VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); @Override TableAnswerElement answer(NetworkSnapshot snapshot); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); @Override TableAnswerElement answer(NetworkSnapshot snapshot);  }