Hello.

Related Issues: #13

The network compare ("82.253.252.7/14", "82.252.0.0/14") will cause the trie recursive call by the following code:

package main

import (
	"math/rand"
	"net"

	"github.com/yl2chen/cidranger"
)

func main() {
	trie := cidranger.NewPCTrieRanger()
	rand.Seed(1)

	addr := net.IP{
		82, 253, 252, 7,
	}

	mask := net.IPMask{0xff, 0xff, 0xff, 0xfc}
	err := trie.Insert(cidranger.NewBasicRangerEntry(net.IPNet{
		IP:   addr,
		Mask: mask,
	}))
	if err != nil {
		panic(err)
	}

	mask = net.IPMask{0xff, 0xfc, 0x00, 0x00}
	err = trie.Insert(cidranger.NewBasicRangerEntry(net.IPNet{
		IP:   addr,
		Mask: mask,
	}))
	if err != nil {
		panic(err)
	}
}

Signed-off-by: detailyang [email protected]

include #37 but remove unnecessary changes, add the benchmark on this as well. before

BenchmarkNetworkEqualIPv4-16          	 5917344	       198 ns/op	      64 B/op	       6 allocs/op
BenchmarkNetworkEqualIPv6-16          	 4486786	       273 ns/op	      42 B/op	       6 allocs/op

after

BenchmarkNetworkEqualIPv4-16          	100000000	        10.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkNetworkEqualIPv6-16          	100000000	        10.9 ns/op	       0 B/op	       0 allocs/op

change newPathprefixTrie to not call newPrefixTree, save time on extra parseCIDR and NewNetwork before

BenchmarkNewPathprefixTriev4-16                                    	 2731194	       440 ns/op	     288 B/op	      12 allocs/op
BenchmarkNewPathprefixTriev6-16                                    	 1610536	       743 ns/op	     456 B/op	      16 allocs/op

after

BenchmarkNewPathprefixTriev4-16                                    	13315774	        88.3 ns/op	      16 B/op	       4 allocs/op
BenchmarkNewPathprefixTriev6-16                                    	 7967464	       153 ns/op	      64 B/op	       4 allocs/op

I'm noticing a behavior where deleted entries seem to not get reaped by garbage collection(runnable example below). For example if I add 1,000,000 entries and then Remove() them all and force a garbage collection, the ranger hangs onto the majority of the memory. If runs to 5 or so, you will see that it just grows and grows. Is this known? I took a look at the code but it's a bit hard for me to follow (as is most code I didn't write ;)

Usage

./cidrtest -ips 1000000 -runs 5

Sample Output

STARTING RUN 0
Starting Inserts
1000000 Inserts Complete
Observe Memory START Alloc = 615 MiB	TotalAlloc = 1828 MiB	Sys = 823 MiB	NumGC = 23
Starting Removes
ENDING RUN 0
Observe Memory END Alloc = 546 MiB	TotalAlloc = 2688 MiB	Sys = 3624 MiB	NumGC = 26
...
STARTING RUN 4
Starting Inserts
1000000 Inserts Complete
Observe Memory START Alloc = 1164 MiB	TotalAlloc = 11699 MiB	Sys = 4585 MiB	NumGC = 39
Starting Removes
ENDING RUN 4
Observe Memory END Alloc = 898 MiB	TotalAlloc = 12350 MiB	Sys = 4654 MiB	NumGC = 40

Code

package main

import (
	"encoding/binary"
	"flag"
	"fmt"
	"math/rand"
	"net"
	"runtime"
	"time"

	"github.com/yl2chen/cidranger"
)

func main() {

	ips := flag.Int("ips", 1000, "Number of IPs.  Default 1000")
	runs := flag.Int("runs", 1000, "Number of runs.  Default 2")
	flag.Parse()

	mask := net.CIDRMask(32, 32)
	trie := cidranger.NewPCTrieRanger()

	// Main loop
	for i := 0; i < *runs; i++ {
		fmt.Printf("STARTING RUN %d\n", i)
		fmt.Printf("Starting Inserts\n")
		for n := 0; n < *ips; n++ {
			trie.Insert(cidranger.NewBasicRangerEntry(net.IPNet{
				IP:   GenIPV4(),
				Mask: mask,
			}))
		}

		fmt.Printf("%d Inserts Complete\n", *ips)
		time.Sleep(5 * time.Second)
		fmt.Printf("Observe Memory START ")
		PrintMemUsage()
		fmt.Printf("Starting Removes\n")
		_, all, _ := net.ParseCIDR("0.0.0.0/0")
		ll, _ := trie.CoveredNetworks(*all)
		for i := 0; i < len(ll); i++ {
			trie.Remove(ll[i].Network())
		}
		ll = nil
		fmt.Printf("ENDING RUN %d\n", i)
		fmt.Printf("Observe Memory END ")
		runtime.GC()
		PrintMemUsage()
		time.Sleep(5 * time.Second)
	}
}

// GenIPV4 generates an IPV4 address
func GenIPV4() net.IP {
	rand.Seed(time.Now().UnixNano())
	var min, max int
	min = 1
	max = 4294967295
	nn := rand.Intn(max-min) + min
	ip := make(net.IP, 4)
	binary.BigEndian.PutUint32(ip, uint32(nn))
	return ip
}

// PrintMemUsage dumps memory stats for the process
func PrintMemUsage() {
	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	fmt.Printf("Alloc = %v MiB", bToMb(m.Alloc))
	fmt.Printf("\tTotalAlloc = %v MiB", bToMb(m.TotalAlloc))
	fmt.Printf("\tSys = %v MiB", bToMb(m.Sys))
	fmt.Printf("\tNumGC = %v\n", m.NumGC)
}

func bToMb(b uint64) uint64 {
	return b / 1024 / 1024
}

Thanks for the wonderful package, @yl2chen .

Go's go mod tooling is pulling the wrong v1.0.0 of cidranger from : https://pkg.go.dev/github.com/yl2chen/[email protected]?tab=doc

Notice the release date of 21-December-2019 above, and that cidranger.AllIPv4 and cidranger.AllIPv6 including the iterator implementation is missing from both sources and the documentation.

This is in variance from the Github releases area, where v1.0.0 with date 24-December-2019, has all the above enhancements: https://github.com/yl2chen/cidranger/releases

Hello!

I am getting an error trying to go get this code.

sum.golang.org: SECURITY ERROR
This download does NOT match the one reported by the checksum server.
The bits may have been replaced on the origin server, or an attacker may\nhave intercepted the download attempt.

For more information, see 'go help module-auth'.
" http-method=GET http-path=/github.com/yl2chen/cidranger/@v/v1.0.0.info http-url=/github.com/yl2chen/cidranger/@v/v1.0.0.info kind="Internal Server Error" module=github.com/yl2chen/cidranger operation=download.InfoHandler ops="[download.InfoHandler pool.Info protocol.Info protocol.processDownload redis.Stash stash.Pool stasher.Stash stasher.fetchModule goGetFetcher.Fetch module.downloadModule]" version=v1.0.0

Did you overwrite the 1.0.0 tag when you updated the coverage recently? I think bumping the tag to 1.0.1 might fix the problem.

Hi!

Two questions:

I created a ranger and inserted a few entries. Is there a way to iterate over the list of CIDR blocks?

Also, is there something like ranger.Contains() that returns the data instead of a bool? I'm using something that implements the RangerEntry interface and I'd like to get back the entire thing.

Thanks!

Example code

func main() {
	ranger = cidranger.NewPCTrieRanger()
	_, network1, _ := net.ParseCIDR("1.2.3.4/32")
	ranger.Insert(cidranger.NewBasicRangerEntry(*network1))

	_, network2, _ := net.ParseCIDR("1.2.3.5/32") // next IP
	ranger.Insert(cidranger.NewBasicRangerEntry(*network2))
}

causes panic: runtime error: index out of range

1. include https://github.com/yl2chen/cidranger/pull/37 but remove unnecessary changes, add the benchmark on this as well.

before

BenchmarkNetworkEqualIPv4-16          	 5917344	       198 ns/op	      64 B/op	       6 allocs/op
BenchmarkNetworkEqualIPv6-16          	 4486786	       273 ns/op	      42 B/op	       6 allocs/op

after

BenchmarkNetworkEqualIPv4-16          	100000000	        10.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkNetworkEqualIPv6-16          	100000000	        10.9 ns/op	       0 B/op	       0 allocs/op

2. change newPathprefixTrie to not call newPrefixTree, save time on extra parseCIDR and NewNetwork

before

BenchmarkNewPathprefixTriev4-16                                    	 2731194	       440 ns/op	     288 B/op	      12 allocs/op
BenchmarkNewPathprefixTriev6-16                                    	 1610536	       743 ns/op	     456 B/op	      16 allocs/op

after

BenchmarkNewPathprefixTriev4-16                                    	13315774	        88.3 ns/op	      16 B/op	       4 allocs/op
BenchmarkNewPathprefixTriev6-16                                    	 7967464	       153 ns/op	      64 B/op	       4 allocs/op

Hi,

I love the library - thanks for sharing it.

I initially assumed that if I inserted duplicate range entries, then both would be returned by ContainingNetworks(), but it appears that duplicates are eliminated. Looking at this code, I guess that's intentional? https://github.com/yl2chen/cidranger/blob/928b519e5268fe386d0f7decce320205cc09ca95/trie_test.go#L38-L41

Following code will produce an out of memory fatal error:

        trie := cidranger.NewPCTrieRanger()
        rand.Seed(1)
        addr := make([]byte, net.IPv4len)
        for n := 0; n < 1000; n += 1 {
                rand.Read(addr)
                cidr := int(rand.Uint32() % uint32(net.IPv4len*8))
                mask := net.CIDRMask(cidr, net.IPv4len*8)
                trie.Insert(cidranger.NewBasicRangerEntry(net.IPNet{
                        IP:   addr,
                        Mask: mask,
                }))
        }

Log shows that it's likely due to too many (*prefixTrie).insert recursive calls.

Recent version of dep - 0.5.0 produces errors on dep status:

◦ dep status
Gopkg.lock is out of sync with imports and/or Gopkg.toml. Run `dep check` for details.
PROJECT  MISSING PACKAGES
input-digest mismatch

This commit updates Gopkg.lock to recent dep format

I essentially ran dep ensure.

Addition of the CoveringNetworks() and CoveringOrCoveredNetworks() methods. I'm certainly open to better name choices if you have something better in mind.

This lib is useful to me and I use these additions, especially CoveringOrCoveredNetworks(). I'm happy if they can benefit others too.

-Hidden

This PR moves cidranger from using the IP address/prefix values from the "net" module in the Go standard libary to using the equivalents from the newer "net/netip" in the standard library. This allows for some code simplification:

• no need to check for invalid underlying []byte lengths or nil pointers
• netip.Prefix can be used directly as a map key in bruteranger as opposed to a net.IPNet's .String() value
• address comparisons can be done directly with ==/!= as opposed to via bytes.Equal()

The tests were updated to use net/netip, and run successfully. TestInsertError and TestRemoveError were removed, as the error they are testing for is impossible to induce with net/netip

This is a fairly big update, and since it changes a good chunk of the API, likely warrants a version bump, though I am opening this PR to at least see if this is a change that you are interested in and if you have any changes in mind. net/netip was introduced in 1.18, and, as 1.19 is out now, all officially supported versions of Go (the last two releases) support this, though applications and libraries making use of cidranger would need to be rewritten or at least add wrapper code to handle this, if this version is used.

Having the ability to supply custom insertion/removal function hooks would be really useful if the data being added was a complex object like a map/slice/struct where specific merge behavior could be specified. This is primarily for the use case where I'm inserting multiple times for the same network with different data as this prevents the need to buffer and merge before inserting into the trie.

func (p *prefixTrie) insert(network rnet.Network, entry RangerEntry) (bool, error) {
        
            *                *                   *

	// No existing child, insert new leaf trie.
	if existingChild == nil || existingChild.network.Number == nil {

          *                   *                   *

	}

          *                  *                  *

	// Check whether it is necessary to insert additional path prefix between current trie and existing child,
	// in the case that inserted network diverges on its path to existing child.
	if lcb, err := network.LeastCommonBitPosition(existingChild.network); err == nil {

          *                   *                  *

	} else {
		return false, err
	}

	return existingChild.insert(network, entry)
}

As posted below, you indicate that there is a way to handle overlapping CIDRs with a custom RangerEntry type. However, it doesn't seem to be possible from what I can tell.

We have a use case where we have multiple subnets that overlap, but are in different VRFs. We want to be able to load all these networks, enriched with the VRF in a custom RangerEntry type, and then retreive this data based on the VRF information.

Please review the code here to see if there is a way to do what we are looking for. - https://play.golang.org/p/9_1PKzEixkr Thanks!

Yes, deduplication were intentional, the idea behind it is that this will any metadata that you would like to attach to a CIDR block could be done through implementing your own custom type that implements the RangerEntry interface https://github.com/yl2chen/cidranger/blob/928b519e5268fe386d0f7decce320205cc09ca95/cidranger.go#L48

Does that fit your use case?

Originally posted by @yl2chen in https://github.com/yl2chen/cidranger/issues/14#issuecomment-487434204