summaryrefslogtreecommitdiffhomepage
path: root/internal/pkg
diff options
context:
space:
mode:
Diffstat (limited to 'internal/pkg')
-rw-r--r--internal/pkg/table/roa.go273
-rw-r--r--internal/pkg/table/roa_test.go240
2 files changed, 513 insertions, 0 deletions
diff --git a/internal/pkg/table/roa.go b/internal/pkg/table/roa.go
index fe08fe54..88f81705 100644
--- a/internal/pkg/table/roa.go
+++ b/internal/pkg/table/roa.go
@@ -18,6 +18,12 @@ package table
import (
"fmt"
"net"
+ "sort"
+
+ radix "github.com/armon/go-radix"
+ "github.com/osrg/gobgp/internal/pkg/config"
+ "github.com/osrg/gobgp/pkg/packet/bgp"
+ log "github.com/sirupsen/logrus"
)
type IPPrefix struct {
@@ -58,3 +64,270 @@ func (r *ROA) Equal(roa *ROA) bool {
}
return false
}
+
+type roaBucket struct {
+ Prefix *IPPrefix
+ entries []*ROA
+}
+
+func (r *roaBucket) GetEntries() []*ROA {
+ return r.entries
+}
+
+type ROATable struct {
+ Roas map[bgp.RouteFamily]*radix.Tree
+}
+
+func NewROATable() *ROATable {
+ m := make(map[bgp.RouteFamily]*radix.Tree)
+ m[bgp.RF_IPv4_UC] = radix.New()
+ m[bgp.RF_IPv6_UC] = radix.New()
+ return &ROATable{
+ Roas: m,
+ }
+}
+
+func (rt *ROATable) roa2tree(roa *ROA) (*radix.Tree, string) {
+ tree := rt.Roas[bgp.RF_IPv4_UC]
+ if roa.Family == bgp.AFI_IP6 {
+ tree = rt.Roas[bgp.RF_IPv6_UC]
+ }
+ return tree, IpToRadixkey(roa.Prefix.Prefix, roa.Prefix.Length)
+}
+
+func (rt *ROATable) Add(roa *ROA) {
+ tree, key := rt.roa2tree(roa)
+ b, _ := tree.Get(key)
+ var bucket *roaBucket
+ if b == nil {
+ bucket = &roaBucket{
+ Prefix: roa.Prefix,
+ entries: make([]*ROA, 0),
+ }
+ tree.Insert(key, bucket)
+ } else {
+ bucket = b.(*roaBucket)
+ for _, r := range bucket.entries {
+ if r.Equal(roa) {
+ // we already have the same one
+ return
+ }
+ }
+ }
+ bucket.entries = append(bucket.entries, roa)
+}
+
+func (rt *ROATable) Delete(roa *ROA) {
+ tree, key := rt.roa2tree(roa)
+ b, _ := tree.Get(key)
+ if b != nil {
+ bucket := b.(*roaBucket)
+ newEntries := make([]*ROA, 0, len(bucket.entries))
+ for _, r := range bucket.entries {
+ if !r.Equal(roa) {
+ newEntries = append(newEntries, r)
+ }
+ }
+ if len(newEntries) != len(bucket.entries) {
+ bucket.entries = newEntries
+ if len(newEntries) == 0 {
+ tree.Delete(key)
+ }
+ return
+ }
+ }
+ log.WithFields(log.Fields{
+ "Topic": "rpki",
+ "Prefix": roa.Prefix.Prefix.String(),
+ "Prefix Length": roa.Prefix.Length,
+ "AS": roa.AS,
+ "Max Length": roa.MaxLen,
+ }).Info("Can't withdraw a ROA")
+}
+
+func (rt *ROATable) DeleteAll(network string) {
+ for _, tree := range rt.Roas {
+ deleteKeys := make([]string, 0, tree.Len())
+ tree.Walk(func(s string, v interface{}) bool {
+ b, _ := v.(*roaBucket)
+ newEntries := make([]*ROA, 0, len(b.entries))
+ for _, r := range b.entries {
+ if r.Src != network {
+ newEntries = append(newEntries, r)
+ }
+ }
+ if len(newEntries) > 0 {
+ b.entries = newEntries
+ } else {
+ deleteKeys = append(deleteKeys, s)
+ }
+ return false
+ })
+ for _, key := range deleteKeys {
+ tree.Delete(key)
+ }
+ }
+}
+
+func validatePath(ownAs uint32, tree *radix.Tree, cidr string, asPath *bgp.PathAttributeAsPath) *Validation {
+ var as uint32
+
+ validation := &Validation{
+ Status: config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND,
+ Reason: RPKI_VALIDATION_REASON_TYPE_NONE,
+ Matched: make([]*ROA, 0),
+ UnmatchedLength: make([]*ROA, 0),
+ UnmatchedAs: make([]*ROA, 0),
+ }
+
+ if asPath == nil || len(asPath.Value) == 0 {
+ as = ownAs
+ } else {
+ param := asPath.Value[len(asPath.Value)-1]
+ switch param.GetType() {
+ case bgp.BGP_ASPATH_ATTR_TYPE_SEQ:
+ asList := param.GetAS()
+ if len(asList) == 0 {
+ as = ownAs
+ } else {
+ as = asList[len(asList)-1]
+ }
+ case bgp.BGP_ASPATH_ATTR_TYPE_CONFED_SET, bgp.BGP_ASPATH_ATTR_TYPE_CONFED_SEQ:
+ as = ownAs
+ default:
+ return validation
+ }
+ }
+ _, n, _ := net.ParseCIDR(cidr)
+ ones, _ := n.Mask.Size()
+ prefixLen := uint8(ones)
+ key := IpToRadixkey(n.IP, prefixLen)
+ _, b, _ := tree.LongestPrefix(key)
+ if b == nil {
+ return validation
+ }
+
+ var bucket *roaBucket
+ fn := radix.WalkFn(func(k string, v interface{}) bool {
+ bucket, _ = v.(*roaBucket)
+ for _, r := range bucket.entries {
+ if prefixLen <= r.MaxLen {
+ if r.AS != 0 && r.AS == as {
+ validation.Matched = append(validation.Matched, r)
+ } else {
+ validation.UnmatchedAs = append(validation.UnmatchedAs, r)
+ }
+ } else {
+ validation.UnmatchedLength = append(validation.UnmatchedLength, r)
+ }
+ }
+ return false
+ })
+ tree.WalkPath(key, fn)
+
+ if len(validation.Matched) != 0 {
+ validation.Status = config.RPKI_VALIDATION_RESULT_TYPE_VALID
+ validation.Reason = RPKI_VALIDATION_REASON_TYPE_NONE
+ } else if len(validation.UnmatchedAs) != 0 {
+ validation.Status = config.RPKI_VALIDATION_RESULT_TYPE_INVALID
+ validation.Reason = RPKI_VALIDATION_REASON_TYPE_AS
+ } else if len(validation.UnmatchedLength) != 0 {
+ validation.Status = config.RPKI_VALIDATION_RESULT_TYPE_INVALID
+ validation.Reason = RPKI_VALIDATION_REASON_TYPE_LENGTH
+ } else {
+ validation.Status = config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND
+ validation.Reason = RPKI_VALIDATION_REASON_TYPE_NONE
+ }
+
+ return validation
+}
+
+func (rt *ROATable) Validate(path *Path) *Validation {
+ if path.IsWithdraw || path.IsEOR() {
+ // RPKI isn't enabled or invalid path
+ return nil
+ }
+ if tree, ok := rt.Roas[path.GetRouteFamily()]; ok {
+ return validatePath(path.OriginInfo().source.LocalAS, tree, path.GetNlri().String(), path.GetAsPath())
+ }
+ return nil
+}
+
+func (rt *ROATable) Info(family bgp.RouteFamily) (map[string]uint32, map[string]uint32) {
+ records := make(map[string]uint32)
+ prefixes := make(map[string]uint32)
+
+ tree := rt.Roas[family]
+ tree.Walk(func(s string, v interface{}) bool {
+ b, _ := v.(*roaBucket)
+ tmpRecords := make(map[string]uint32)
+ for _, roa := range b.entries {
+ tmpRecords[roa.Src]++
+ }
+
+ for src, r := range tmpRecords {
+ if r > 0 {
+ records[src] += r
+ prefixes[src]++
+ }
+ }
+ return false
+ })
+ return records, prefixes
+}
+
+func (rt *ROATable) List(family bgp.RouteFamily) ([]*ROA, error) {
+ var rfList []bgp.RouteFamily
+ switch family {
+ case bgp.RF_IPv4_UC:
+ rfList = []bgp.RouteFamily{bgp.RF_IPv4_UC}
+ case bgp.RF_IPv6_UC:
+ rfList = []bgp.RouteFamily{bgp.RF_IPv6_UC}
+ default:
+ rfList = []bgp.RouteFamily{bgp.RF_IPv4_UC, bgp.RF_IPv6_UC}
+ }
+ l := make([]*ROA, 0)
+ for _, rf := range rfList {
+ if tree, ok := rt.Roas[rf]; ok {
+ tree.Walk(func(s string, v interface{}) bool {
+ b, _ := v.(*roaBucket)
+ var roaList roas
+ for _, r := range b.entries {
+ roaList = append(roaList, r)
+ }
+ sort.Sort(roaList)
+ for _, roa := range roaList {
+ l = append(l, roa)
+ }
+ return false
+ })
+ }
+ }
+ return l, nil
+}
+
+type roas []*ROA
+
+func (r roas) Len() int {
+ return len(r)
+}
+
+func (r roas) Swap(i, j int) {
+ r[i], r[j] = r[j], r[i]
+}
+
+func (r roas) Less(i, j int) bool {
+ r1 := r[i]
+ r2 := r[j]
+
+ if r1.MaxLen < r2.MaxLen {
+ return true
+ } else if r1.MaxLen > r2.MaxLen {
+ return false
+ }
+
+ if r1.AS < r2.AS {
+ return true
+ }
+ return false
+}
diff --git a/internal/pkg/table/roa_test.go b/internal/pkg/table/roa_test.go
new file mode 100644
index 00000000..6b98269e
--- /dev/null
+++ b/internal/pkg/table/roa_test.go
@@ -0,0 +1,240 @@
+package table
+
+import (
+ "net"
+ "strconv"
+ "strings"
+ "testing"
+
+ radix "github.com/armon/go-radix"
+ "github.com/osrg/gobgp/internal/pkg/config"
+ "github.com/osrg/gobgp/pkg/packet/bgp"
+ "github.com/stretchr/testify/assert"
+)
+
+func strToASParam(str string) *bgp.PathAttributeAsPath {
+ toList := func(asstr, sep string) []uint32 {
+ as := make([]uint32, 0)
+ l := strings.Split(asstr, sep)
+ for _, s := range l {
+ v, _ := strconv.ParseUint(s, 10, 32)
+ as = append(as, uint32(v))
+ }
+ return as
+ }
+ var atype uint8
+ var as []uint32
+ if strings.HasPrefix(str, "{") {
+ atype = bgp.BGP_ASPATH_ATTR_TYPE_SET
+ as = toList(str[1:len(str)-1], ",")
+ } else if strings.HasPrefix(str, "(") {
+ atype = bgp.BGP_ASPATH_ATTR_TYPE_CONFED_SET
+ as = toList(str[1:len(str)-1], " ")
+ } else {
+ atype = bgp.BGP_ASPATH_ATTR_TYPE_SEQ
+ as = toList(str, " ")
+ }
+
+ return bgp.NewPathAttributeAsPath([]bgp.AsPathParamInterface{bgp.NewAs4PathParam(atype, as)})
+}
+
+func validateOne(tree *radix.Tree, cidr, aspathStr string) config.RpkiValidationResultType {
+ r := validatePath(65500, tree, cidr, strToASParam(aspathStr))
+ return r.Status
+}
+
+func TestValidate0(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("192.168.0.0").To4(), 24, 32, 100, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("192.168.0.0").To4(), 24, 24, 200, ""))
+
+ var r config.RpkiValidationResultType
+
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "192.168.0.0/24", "100")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "192.168.0.0/24", "100 200")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "192.168.0.0/24", "300")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+
+ r = validateOne(tree, "192.168.0.0/25", "100")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "192.168.0.0/25", "200")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+
+ r = validateOne(tree, "192.168.0.0/25", "300")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+}
+
+func TestValidate1(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 16, 65000, ""))
+
+ var r config.RpkiValidationResultType
+
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/16", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "10.0.0.0/16", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+}
+
+func TestValidate2(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+
+ var r config.RpkiValidationResultType
+
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/16", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+
+ r = validateOne(tree, "10.0.0.0/16", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+}
+
+func TestValidate3(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 16, 65000, ""))
+
+ var r config.RpkiValidationResultType
+
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/8", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+
+ r = validateOne(tree, "10.0.0.0/17", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+
+ table = NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 65000, ""))
+
+ tree = table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/17", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+}
+
+func TestValidate4(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 16, 65000, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 16, 65001, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/16", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "10.0.0.0/16", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+}
+
+func TestValidate5(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 17, 17, 65000, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.128.0").To4(), 17, 17, 65000, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/16", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+}
+
+func TestValidate6(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 8, 32, 0, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/7", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+
+ r = validateOne(tree, "10.0.0.0/8", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+
+ r = validateOne(tree, "10.0.0.0/24", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+}
+
+func TestValidate7(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 65000, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/24", "{65000}")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+
+ r = validateOne(tree, "10.0.0.0/24", "{65001}")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+
+ r = validateOne(tree, "10.0.0.0/24", "{65000,65001}")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_NOT_FOUND)
+}
+
+func TestValidate8(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 0, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 65000, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/24", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "10.0.0.0/24", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+}
+
+func TestValidate9(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 24, 24, 65000, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 65001, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/24", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+
+ r = validateOne(tree, "10.0.0.0/24", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+}
+
+func TestValidate10(t *testing.T) {
+ assert := assert.New(t)
+
+ table := NewROATable()
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 24, 24, 0, ""))
+ table.Add(NewROA(bgp.AFI_IP, net.ParseIP("10.0.0.0").To4(), 16, 24, 65001, ""))
+
+ var r config.RpkiValidationResultType
+ tree := table.Roas[bgp.RF_IPv4_UC]
+ r = validateOne(tree, "10.0.0.0/24", "65000")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_INVALID)
+
+ r = validateOne(tree, "10.0.0.0/24", "65001")
+ assert.Equal(r, config.RPKI_VALIDATION_RESULT_TYPE_VALID)
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 08:50:34 +0000