@Test public void testBufferedStatement() { RoutingPolicy policy = _policyBuilder .addStatement(new BufferedStatement(new SetLocalPreference(new LiteralLong(42)))) .addStatement(new StaticStatement(Statements.ExitAccept)) .build(); _g = new Graph(_batfish, _batfish.getSnapshot(), true); TransferBDD tbdd = new TransferBDD(_g, _baseConfig, policy.getStatements()); TransferReturn result = tbdd.compute(ImmutableSet.of()).getReturnValue(); BDD acceptedAnnouncements = result.getSecond(); BDDRoute outAnnouncements = result.getFirst(); assertTrue(acceptedAnnouncements.isOne()); BDDRoute expected = new BDDRoute(_anyRoute); BDDInteger localPref = expected.getLocalPref(); expected.setLocalPref(BDDInteger.makeFromValue(localPref.getFactory(), 32, 42)); assertEquals(expected, outAnnouncements); }
private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) { if (expr instanceof MatchIpv4) { p.debug("MatchIpv4"); TransferReturn ret = new TransferReturn(p.getData(), factory.one()); p.debug("MatchIpv4 Result: " + ret); return fromExpr(ret); } if (expr instanceof MatchIpv6) { p.debug("MatchIpv6"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } if (expr instanceof Conjunction) { p.debug("Conjunction"); Conjunction c = (Conjunction) expr; BDD acc = factory.one(); for (BooleanExpr be : c.getConjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.and(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Conjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof Disjunction) { p.debug("Disjunction"); Disjunction d = (Disjunction) expr; BDD acc = factory.zero(); for (BooleanExpr be : d.getDisjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.or(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Disjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof ConjunctionChain) { p.debug("ConjunctionChain"); ConjunctionChain d = (ConjunctionChain) expr; List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); conjuncts.add(be); } if (conjuncts.isEmpty()) { TransferReturn ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); } else { TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = conjuncts.size() - 1; i >= 0; i--) { BooleanExpr conjunct = conjuncts.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(conjunct, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } } if (expr instanceof FirstMatchChain) { p.debug("FirstMatchChain"); FirstMatchChain chain = (FirstMatchChain) expr; List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); chainPolicies.add(be); } if (chainPolicies.isEmpty()) { throw new BatfishException("Default policy is not set"); } TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = chainPolicies.size() - 1; i >= 0; i--) { BooleanExpr policyMatcher = chainPolicies.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(policyMatcher, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } if (expr instanceof Not) { p.debug("mkNot"); Not n = (Not) expr; TransferResult result = compute(n.getExpr(), p); TransferReturn r = result.getReturnValue(); TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not()); return new TransferResult(ret, factory.zero()); } if (expr instanceof MatchProtocol) { MatchProtocol mp = (MatchProtocol) expr; Set<RoutingProtocol> rps = mp.getProtocols(); if (rps.size() > 1) { List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList()); return compute(new Disjunction(mps), p); } RoutingProtocol rp = Iterables.getOnlyElement(rps); Protocol proto = Protocol.fromRoutingProtocol(rp); if (proto == null) { p.debug("MatchProtocol(" + rp.protocolName() + "): false"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } BDD protoMatch = p.getData().getProtocolHistory().value(proto); p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch); TransferReturn ret = new TransferReturn(p.getData(), protoMatch); return fromExpr(ret); } if (expr instanceof MatchPrefixSet) { p.debug("MatchPrefixSet"); MatchPrefixSet m = (MatchPrefixSet) expr; BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), r); return fromExpr(ret); } else if (expr instanceof MatchPrefix6Set) { p.debug("MatchPrefix6Set"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } else if (expr instanceof CallExpr) { p.debug("CallExpr"); CallExpr c = (CallExpr) expr; String router = _conf.getHostname(); String name = c.getCalledPolicyName(); TransferResult r = CACHE.get(router, name); if (r != null) { return r; } RoutingPolicy pol = _conf.getRoutingPolicies().get(name); r = compute( pol.getStatements(), p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name)); CACHE.put(router, name, r); return r; } else if (expr instanceof WithEnvironmentExpr) { p.debug("WithEnvironmentExpr"); WithEnvironmentExpr we = (WithEnvironmentExpr) expr; return compute(we.getExpr(), p.deepCopy()); } else if (expr instanceof MatchCommunitySet) { p.debug("MatchCommunitySet"); MatchCommunitySet mcs = (MatchCommunitySet) expr; BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), c); return fromExpr(ret); } else if (expr instanceof MatchCommunities) { p.debug("MatchCommunities"); MatchCommunities mc = (MatchCommunities) expr; if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) { throw new BatfishException( "Matching for communities other than the input communities is not supported: " + mc); } BDD mcPredicate = mc.getCommunitySetMatchExpr() .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData())); TransferReturn ret = new TransferReturn(p.getData(), mcPredicate); return fromExpr(ret); } else if (expr instanceof BooleanExprs.StaticBooleanExpr) { BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr; TransferReturn ret; switch (b.getType()) { case CallExprContext: p.debug("CallExprContext"); BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL); ret = new TransferReturn(p.getData(), x1); return fromExpr(ret); case CallStatementContext: p.debug("CallStmtContext"); BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL); ret = new TransferReturn(p.getData(), x2); return fromExpr(ret); case True: p.debug("True"); ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); case False: p.debug("False"); ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); default: throw new BatfishException( "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType()); } } else if (expr instanceof MatchAsPath) { p.debug("MatchAsPath"); MatchAsPath matchAsPathNode = (MatchAsPath) expr; BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate); return fromExpr(ret); } throw new BatfishException("TODO: compute expr transfer function: " + expr); }
TransferBDD { private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) { if (expr instanceof MatchIpv4) { p.debug("MatchIpv4"); TransferReturn ret = new TransferReturn(p.getData(), factory.one()); p.debug("MatchIpv4 Result: " + ret); return fromExpr(ret); } if (expr instanceof MatchIpv6) { p.debug("MatchIpv6"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } if (expr instanceof Conjunction) { p.debug("Conjunction"); Conjunction c = (Conjunction) expr; BDD acc = factory.one(); for (BooleanExpr be : c.getConjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.and(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Conjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof Disjunction) { p.debug("Disjunction"); Disjunction d = (Disjunction) expr; BDD acc = factory.zero(); for (BooleanExpr be : d.getDisjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.or(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Disjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof ConjunctionChain) { p.debug("ConjunctionChain"); ConjunctionChain d = (ConjunctionChain) expr; List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); conjuncts.add(be); } if (conjuncts.isEmpty()) { TransferReturn ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); } else { TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = conjuncts.size() - 1; i >= 0; i--) { BooleanExpr conjunct = conjuncts.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(conjunct, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } } if (expr instanceof FirstMatchChain) { p.debug("FirstMatchChain"); FirstMatchChain chain = (FirstMatchChain) expr; List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); chainPolicies.add(be); } if (chainPolicies.isEmpty()) { throw new BatfishException("Default policy is not set"); } TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = chainPolicies.size() - 1; i >= 0; i--) { BooleanExpr policyMatcher = chainPolicies.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(policyMatcher, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } if (expr instanceof Not) { p.debug("mkNot"); Not n = (Not) expr; TransferResult result = compute(n.getExpr(), p); TransferReturn r = result.getReturnValue(); TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not()); return new TransferResult(ret, factory.zero()); } if (expr instanceof MatchProtocol) { MatchProtocol mp = (MatchProtocol) expr; Set<RoutingProtocol> rps = mp.getProtocols(); if (rps.size() > 1) { List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList()); return compute(new Disjunction(mps), p); } RoutingProtocol rp = Iterables.getOnlyElement(rps); Protocol proto = Protocol.fromRoutingProtocol(rp); if (proto == null) { p.debug("MatchProtocol(" + rp.protocolName() + "): false"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } BDD protoMatch = p.getData().getProtocolHistory().value(proto); p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch); TransferReturn ret = new TransferReturn(p.getData(), protoMatch); return fromExpr(ret); } if (expr instanceof MatchPrefixSet) { p.debug("MatchPrefixSet"); MatchPrefixSet m = (MatchPrefixSet) expr; BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), r); return fromExpr(ret); } else if (expr instanceof MatchPrefix6Set) { p.debug("MatchPrefix6Set"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } else if (expr instanceof CallExpr) { p.debug("CallExpr"); CallExpr c = (CallExpr) expr; String router = _conf.getHostname(); String name = c.getCalledPolicyName(); TransferResult r = CACHE.get(router, name); if (r != null) { return r; } RoutingPolicy pol = _conf.getRoutingPolicies().get(name); r = compute( pol.getStatements(), p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name)); CACHE.put(router, name, r); return r; } else if (expr instanceof WithEnvironmentExpr) { p.debug("WithEnvironmentExpr"); WithEnvironmentExpr we = (WithEnvironmentExpr) expr; return compute(we.getExpr(), p.deepCopy()); } else if (expr instanceof MatchCommunitySet) { p.debug("MatchCommunitySet"); MatchCommunitySet mcs = (MatchCommunitySet) expr; BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), c); return fromExpr(ret); } else if (expr instanceof MatchCommunities) { p.debug("MatchCommunities"); MatchCommunities mc = (MatchCommunities) expr; if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) { throw new BatfishException( "Matching for communities other than the input communities is not supported: " + mc); } BDD mcPredicate = mc.getCommunitySetMatchExpr() .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData())); TransferReturn ret = new TransferReturn(p.getData(), mcPredicate); return fromExpr(ret); } else if (expr instanceof BooleanExprs.StaticBooleanExpr) { BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr; TransferReturn ret; switch (b.getType()) { case CallExprContext: p.debug("CallExprContext"); BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL); ret = new TransferReturn(p.getData(), x1); return fromExpr(ret); case CallStatementContext: p.debug("CallStmtContext"); BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL); ret = new TransferReturn(p.getData(), x2); return fromExpr(ret); case True: p.debug("True"); ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); case False: p.debug("False"); ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); default: throw new BatfishException( "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType()); } } else if (expr instanceof MatchAsPath) { p.debug("MatchAsPath"); MatchAsPath matchAsPathNode = (MatchAsPath) expr; BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate); return fromExpr(ret); } throw new BatfishException("TODO: compute expr transfer function: " + expr); } }
TransferBDD { private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) { if (expr instanceof MatchIpv4) { p.debug("MatchIpv4"); TransferReturn ret = new TransferReturn(p.getData(), factory.one()); p.debug("MatchIpv4 Result: " + ret); return fromExpr(ret); } if (expr instanceof MatchIpv6) { p.debug("MatchIpv6"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } if (expr instanceof Conjunction) { p.debug("Conjunction"); Conjunction c = (Conjunction) expr; BDD acc = factory.one(); for (BooleanExpr be : c.getConjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.and(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Conjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof Disjunction) { p.debug("Disjunction"); Disjunction d = (Disjunction) expr; BDD acc = factory.zero(); for (BooleanExpr be : d.getDisjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.or(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Disjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof ConjunctionChain) { p.debug("ConjunctionChain"); ConjunctionChain d = (ConjunctionChain) expr; List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); conjuncts.add(be); } if (conjuncts.isEmpty()) { TransferReturn ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); } else { TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = conjuncts.size() - 1; i >= 0; i--) { BooleanExpr conjunct = conjuncts.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(conjunct, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } } if (expr instanceof FirstMatchChain) { p.debug("FirstMatchChain"); FirstMatchChain chain = (FirstMatchChain) expr; List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); chainPolicies.add(be); } if (chainPolicies.isEmpty()) { throw new BatfishException("Default policy is not set"); } TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = chainPolicies.size() - 1; i >= 0; i--) { BooleanExpr policyMatcher = chainPolicies.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(policyMatcher, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } if (expr instanceof Not) { p.debug("mkNot"); Not n = (Not) expr; TransferResult result = compute(n.getExpr(), p); TransferReturn r = result.getReturnValue(); TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not()); return new TransferResult(ret, factory.zero()); } if (expr instanceof MatchProtocol) { MatchProtocol mp = (MatchProtocol) expr; Set<RoutingProtocol> rps = mp.getProtocols(); if (rps.size() > 1) { List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList()); return compute(new Disjunction(mps), p); } RoutingProtocol rp = Iterables.getOnlyElement(rps); Protocol proto = Protocol.fromRoutingProtocol(rp); if (proto == null) { p.debug("MatchProtocol(" + rp.protocolName() + "): false"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } BDD protoMatch = p.getData().getProtocolHistory().value(proto); p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch); TransferReturn ret = new TransferReturn(p.getData(), protoMatch); return fromExpr(ret); } if (expr instanceof MatchPrefixSet) { p.debug("MatchPrefixSet"); MatchPrefixSet m = (MatchPrefixSet) expr; BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), r); return fromExpr(ret); } else if (expr instanceof MatchPrefix6Set) { p.debug("MatchPrefix6Set"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } else if (expr instanceof CallExpr) { p.debug("CallExpr"); CallExpr c = (CallExpr) expr; String router = _conf.getHostname(); String name = c.getCalledPolicyName(); TransferResult r = CACHE.get(router, name); if (r != null) { return r; } RoutingPolicy pol = _conf.getRoutingPolicies().get(name); r = compute( pol.getStatements(), p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name)); CACHE.put(router, name, r); return r; } else if (expr instanceof WithEnvironmentExpr) { p.debug("WithEnvironmentExpr"); WithEnvironmentExpr we = (WithEnvironmentExpr) expr; return compute(we.getExpr(), p.deepCopy()); } else if (expr instanceof MatchCommunitySet) { p.debug("MatchCommunitySet"); MatchCommunitySet mcs = (MatchCommunitySet) expr; BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), c); return fromExpr(ret); } else if (expr instanceof MatchCommunities) { p.debug("MatchCommunities"); MatchCommunities mc = (MatchCommunities) expr; if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) { throw new BatfishException( "Matching for communities other than the input communities is not supported: " + mc); } BDD mcPredicate = mc.getCommunitySetMatchExpr() .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData())); TransferReturn ret = new TransferReturn(p.getData(), mcPredicate); return fromExpr(ret); } else if (expr instanceof BooleanExprs.StaticBooleanExpr) { BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr; TransferReturn ret; switch (b.getType()) { case CallExprContext: p.debug("CallExprContext"); BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL); ret = new TransferReturn(p.getData(), x1); return fromExpr(ret); case CallStatementContext: p.debug("CallStmtContext"); BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL); ret = new TransferReturn(p.getData(), x2); return fromExpr(ret); case True: p.debug("True"); ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); case False: p.debug("False"); ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); default: throw new BatfishException( "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType()); } } else if (expr instanceof MatchAsPath) { p.debug("MatchAsPath"); MatchAsPath matchAsPathNode = (MatchAsPath) expr; BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate); return fromExpr(ret); } throw new BatfishException("TODO: compute expr transfer function: " + expr); } TransferBDD(Graph g, Configuration conf, List<Statement> statements); }
TransferBDD { private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) { if (expr instanceof MatchIpv4) { p.debug("MatchIpv4"); TransferReturn ret = new TransferReturn(p.getData(), factory.one()); p.debug("MatchIpv4 Result: " + ret); return fromExpr(ret); } if (expr instanceof MatchIpv6) { p.debug("MatchIpv6"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } if (expr instanceof Conjunction) { p.debug("Conjunction"); Conjunction c = (Conjunction) expr; BDD acc = factory.one(); for (BooleanExpr be : c.getConjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.and(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Conjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof Disjunction) { p.debug("Disjunction"); Disjunction d = (Disjunction) expr; BDD acc = factory.zero(); for (BooleanExpr be : d.getDisjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.or(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Disjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof ConjunctionChain) { p.debug("ConjunctionChain"); ConjunctionChain d = (ConjunctionChain) expr; List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); conjuncts.add(be); } if (conjuncts.isEmpty()) { TransferReturn ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); } else { TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = conjuncts.size() - 1; i >= 0; i--) { BooleanExpr conjunct = conjuncts.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(conjunct, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } } if (expr instanceof FirstMatchChain) { p.debug("FirstMatchChain"); FirstMatchChain chain = (FirstMatchChain) expr; List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); chainPolicies.add(be); } if (chainPolicies.isEmpty()) { throw new BatfishException("Default policy is not set"); } TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = chainPolicies.size() - 1; i >= 0; i--) { BooleanExpr policyMatcher = chainPolicies.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(policyMatcher, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } if (expr instanceof Not) { p.debug("mkNot"); Not n = (Not) expr; TransferResult result = compute(n.getExpr(), p); TransferReturn r = result.getReturnValue(); TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not()); return new TransferResult(ret, factory.zero()); } if (expr instanceof MatchProtocol) { MatchProtocol mp = (MatchProtocol) expr; Set<RoutingProtocol> rps = mp.getProtocols(); if (rps.size() > 1) { List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList()); return compute(new Disjunction(mps), p); } RoutingProtocol rp = Iterables.getOnlyElement(rps); Protocol proto = Protocol.fromRoutingProtocol(rp); if (proto == null) { p.debug("MatchProtocol(" + rp.protocolName() + "): false"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } BDD protoMatch = p.getData().getProtocolHistory().value(proto); p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch); TransferReturn ret = new TransferReturn(p.getData(), protoMatch); return fromExpr(ret); } if (expr instanceof MatchPrefixSet) { p.debug("MatchPrefixSet"); MatchPrefixSet m = (MatchPrefixSet) expr; BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), r); return fromExpr(ret); } else if (expr instanceof MatchPrefix6Set) { p.debug("MatchPrefix6Set"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } else if (expr instanceof CallExpr) { p.debug("CallExpr"); CallExpr c = (CallExpr) expr; String router = _conf.getHostname(); String name = c.getCalledPolicyName(); TransferResult r = CACHE.get(router, name); if (r != null) { return r; } RoutingPolicy pol = _conf.getRoutingPolicies().get(name); r = compute( pol.getStatements(), p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name)); CACHE.put(router, name, r); return r; } else if (expr instanceof WithEnvironmentExpr) { p.debug("WithEnvironmentExpr"); WithEnvironmentExpr we = (WithEnvironmentExpr) expr; return compute(we.getExpr(), p.deepCopy()); } else if (expr instanceof MatchCommunitySet) { p.debug("MatchCommunitySet"); MatchCommunitySet mcs = (MatchCommunitySet) expr; BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), c); return fromExpr(ret); } else if (expr instanceof MatchCommunities) { p.debug("MatchCommunities"); MatchCommunities mc = (MatchCommunities) expr; if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) { throw new BatfishException( "Matching for communities other than the input communities is not supported: " + mc); } BDD mcPredicate = mc.getCommunitySetMatchExpr() .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData())); TransferReturn ret = new TransferReturn(p.getData(), mcPredicate); return fromExpr(ret); } else if (expr instanceof BooleanExprs.StaticBooleanExpr) { BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr; TransferReturn ret; switch (b.getType()) { case CallExprContext: p.debug("CallExprContext"); BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL); ret = new TransferReturn(p.getData(), x1); return fromExpr(ret); case CallStatementContext: p.debug("CallStmtContext"); BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL); ret = new TransferReturn(p.getData(), x2); return fromExpr(ret); case True: p.debug("True"); ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); case False: p.debug("False"); ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); default: throw new BatfishException( "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType()); } } else if (expr instanceof MatchAsPath) { p.debug("MatchAsPath"); MatchAsPath matchAsPathNode = (MatchAsPath) expr; BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate); return fromExpr(ret); } throw new BatfishException("TODO: compute expr transfer function: " + expr); } TransferBDD(Graph g, Configuration conf, List<Statement> statements); static BDD firstBitsEqual(BDD[] bits, Prefix p, int length); static BDD isRelevantFor(BDDRoute record, PrefixRange range); TransferResult compute(@Nullable Set<Prefix> ignoredNetworks); Map<CommunityVar, Set<Integer>> getCommunityAtomicPredicates(); Configuration getConfiguration(); Graph getGraph(); }
TransferBDD { private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) { if (expr instanceof MatchIpv4) { p.debug("MatchIpv4"); TransferReturn ret = new TransferReturn(p.getData(), factory.one()); p.debug("MatchIpv4 Result: " + ret); return fromExpr(ret); } if (expr instanceof MatchIpv6) { p.debug("MatchIpv6"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } if (expr instanceof Conjunction) { p.debug("Conjunction"); Conjunction c = (Conjunction) expr; BDD acc = factory.one(); for (BooleanExpr be : c.getConjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.and(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Conjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof Disjunction) { p.debug("Disjunction"); Disjunction d = (Disjunction) expr; BDD acc = factory.zero(); for (BooleanExpr be : d.getDisjuncts()) { TransferResult r = compute(be, p.indent()); acc = acc.or(r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(p.getData(), acc); p.debug("Disjunction return: " + acc); return new TransferResult(ret, factory.zero()); } if (expr instanceof ConjunctionChain) { p.debug("ConjunctionChain"); ConjunctionChain d = (ConjunctionChain) expr; List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); conjuncts.add(be); } if (conjuncts.isEmpty()) { TransferReturn ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); } else { TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = conjuncts.size() - 1; i >= 0; i--) { BooleanExpr conjunct = conjuncts.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(conjunct, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } } if (expr instanceof FirstMatchChain) { p.debug("FirstMatchChain"); FirstMatchChain chain = (FirstMatchChain) expr; List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines()); if (p.getDefaultPolicy() != null) { BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy()); chainPolicies.add(be); } if (chainPolicies.isEmpty()) { throw new BatfishException("Default policy is not set"); } TransferResult result = new TransferResult(p.getData()); TransferParam<BDDRoute> record = p; BDD acc = factory.zero(); for (int i = chainPolicies.size() - 1; i >= 0; i--) { BooleanExpr policyMatcher = chainPolicies.get(i); TransferParam<BDDRoute> param = record .setDefaultPolicy(null) .setChainContext(TransferParam.ChainContext.CONJUNCTION) .indent(); TransferResult r = compute(policyMatcher, param); record = record.setData(r.getReturnValue().getFirst()); acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond()); } TransferReturn ret = new TransferReturn(record.getData(), acc); return result.setReturnValue(ret); } if (expr instanceof Not) { p.debug("mkNot"); Not n = (Not) expr; TransferResult result = compute(n.getExpr(), p); TransferReturn r = result.getReturnValue(); TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not()); return new TransferResult(ret, factory.zero()); } if (expr instanceof MatchProtocol) { MatchProtocol mp = (MatchProtocol) expr; Set<RoutingProtocol> rps = mp.getProtocols(); if (rps.size() > 1) { List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList()); return compute(new Disjunction(mps), p); } RoutingProtocol rp = Iterables.getOnlyElement(rps); Protocol proto = Protocol.fromRoutingProtocol(rp); if (proto == null) { p.debug("MatchProtocol(" + rp.protocolName() + "): false"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } BDD protoMatch = p.getData().getProtocolHistory().value(proto); p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch); TransferReturn ret = new TransferReturn(p.getData(), protoMatch); return fromExpr(ret); } if (expr instanceof MatchPrefixSet) { p.debug("MatchPrefixSet"); MatchPrefixSet m = (MatchPrefixSet) expr; BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), r); return fromExpr(ret); } else if (expr instanceof MatchPrefix6Set) { p.debug("MatchPrefix6Set"); TransferReturn ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); } else if (expr instanceof CallExpr) { p.debug("CallExpr"); CallExpr c = (CallExpr) expr; String router = _conf.getHostname(); String name = c.getCalledPolicyName(); TransferResult r = CACHE.get(router, name); if (r != null) { return r; } RoutingPolicy pol = _conf.getRoutingPolicies().get(name); r = compute( pol.getStatements(), p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name)); CACHE.put(router, name, r); return r; } else if (expr instanceof WithEnvironmentExpr) { p.debug("WithEnvironmentExpr"); WithEnvironmentExpr we = (WithEnvironmentExpr) expr; return compute(we.getExpr(), p.deepCopy()); } else if (expr instanceof MatchCommunitySet) { p.debug("MatchCommunitySet"); MatchCommunitySet mcs = (MatchCommunitySet) expr; BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), c); return fromExpr(ret); } else if (expr instanceof MatchCommunities) { p.debug("MatchCommunities"); MatchCommunities mc = (MatchCommunities) expr; if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) { throw new BatfishException( "Matching for communities other than the input communities is not supported: " + mc); } BDD mcPredicate = mc.getCommunitySetMatchExpr() .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData())); TransferReturn ret = new TransferReturn(p.getData(), mcPredicate); return fromExpr(ret); } else if (expr instanceof BooleanExprs.StaticBooleanExpr) { BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr; TransferReturn ret; switch (b.getType()) { case CallExprContext: p.debug("CallExprContext"); BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL); ret = new TransferReturn(p.getData(), x1); return fromExpr(ret); case CallStatementContext: p.debug("CallStmtContext"); BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL); ret = new TransferReturn(p.getData(), x2); return fromExpr(ret); case True: p.debug("True"); ret = new TransferReturn(p.getData(), factory.one()); return fromExpr(ret); case False: p.debug("False"); ret = new TransferReturn(p.getData(), factory.zero()); return fromExpr(ret); default: throw new BatfishException( "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType()); } } else if (expr instanceof MatchAsPath) { p.debug("MatchAsPath"); MatchAsPath matchAsPathNode = (MatchAsPath) expr; BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData()); TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate); return fromExpr(ret); } throw new BatfishException("TODO: compute expr transfer function: " + expr); } TransferBDD(Graph g, Configuration conf, List<Statement> statements); static BDD firstBitsEqual(BDD[] bits, Prefix p, int length); static BDD isRelevantFor(BDDRoute record, PrefixRange range); TransferResult compute(@Nullable Set<Prefix> ignoredNetworks); Map<CommunityVar, Set<Integer>> getCommunityAtomicPredicates(); Configuration getConfiguration(); Graph getGraph();  }