Repository: spidernet-io/spiderpool
Pull request #3628 (2024-06-21 07:20:49)

fix: it is so slow to create a Pod requiring IP from a super big CIDR
git-cherry-pick #3583

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io) Report
Attention: Patch coverage is `74.60317%` with `16 lines` in your changes missing coverage. Please review.
> Project coverage is 80.93%. Comparing base [(`0d89c39`)](https://app.codecov.io/gh/spidernet-io/spiderpool/commit/0d89c39c19def2af61432ff03128ed28c3719f06?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io) to head [(`87adc5a`)](https://app.codecov.io/gh/spidernet-io/spiderpool/commit/87adc5a527aeaf607a342a54c37899ba23ef0f33?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io).

<details><summary>Additional details and impacted files</summary>


[![Impacted file tree graph](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628/graphs/tree.svg?width=650&height=150&src=pr&token=YKXY2E4Q8G&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io)](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io)

```diff
@@               Coverage Diff                @@
##           release-v0.8    #3628      +/-   ##
================================================
- Coverage         81.01%   80.93%   -0.08%     
================================================
  Files                49       49              
  Lines              5340     5382      +42     
================================================
+ Hits               4326     4356      +30     
- Misses              856      864       +8     
- Partials            158      162       +4     
```

| [Flag](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io) | Coverage Δ | |
|---|---|---|
| [unittests](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io) | `80.93% <74.60%> (-0.08%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Files](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io) | Coverage Δ | |
|---|---|---|
| [pkg/ippoolmanager/ippool\_manager.go](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?src=pr&el=tree&filepath=pkg%2Fippoolmanager%2Fippool_manager.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io#diff-cGtnL2lwcG9vbG1hbmFnZXIvaXBwb29sX21hbmFnZXIuZ28=) | `85.88% <100.00%> (ø)` | |
| [pkg/subnetmanager/subnet\_validate.go](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?src=pr&el=tree&filepath=pkg%2Fsubnetmanager%2Fsubnet_validate.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io#diff-cGtnL3N1Ym5ldG1hbmFnZXIvc3VibmV0X3ZhbGlkYXRlLmdv) | `93.00% <100.00%> (-0.03%)` | :arrow_down: |
| [pkg/subnetmanager/subnet\_manager.go](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?src=pr&el=tree&filepath=pkg%2Fsubnetmanager%2Fsubnet_manager.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io#diff-cGtnL3N1Ym5ldG1hbmFnZXIvc3VibmV0X21hbmFnZXIuZ28=) | `41.48% <0.00%> (ø)` | |
| [pkg/ip/ip.go](https://app.codecov.io/gh/spidernet-io/spiderpool/pull/3628?src=pr&el=tree&filepath=pkg%2Fip%2Fip.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=spidernet-io#diff-cGtnL2lwL2lwLmdv) | `87.64% <74.57%> (-5.27%)` | :arrow_down: |

</details>
ty-dc: ci problem is being processed
weizhoublue: @ty-dc upgrade ci
ty-dc: rebase #https://github.com/spidernet-io/spiderpool/pull/3636, thx.

Patch:
diff --git a/pkg/ip/ip.go b/pkg/ip/ip.go
index f6a83175a..443a84259 100644
--- a/pkg/ip/ip.go
+++ b/pkg/ip/ip.go
@@ -84,32 +84,103 @@ func IsIP(version types.IPVersion, s string) error {
 // [172.18.40.2 172.18.40.3] is [172.18.40.1].
 //
 // If sorted is true, the result set of IP addresses will be sorted.
-func IPsDiffSet(ips1, ips2 []net.IP, sorted bool) []net.IP {
-	var ips []net.IP
-	marks := make(map[string]bool)
-	for _, ip := range ips1 {
+func IPsDiffSet(ipSourceList, ipExcludeList []net.IP, sorted bool) []net.IP {
+	return getIPDiffSet(ipSourceList, ipExcludeList, sorted, -1)
+}
+
+func IsDiffIPSet(ipSourceList, ipExcludeList []net.IP) bool {
+	diff := getIPDiffSet(ipSourceList, ipExcludeList, false, 1)
+	return len(diff) > 0
+}
+
+// getIPDiffSet returns a list of IPs from ipSourceList that are not in ipExcludeList. Parameters:
+// - ipSourceList: a slice of net.IP that represents the source list of IPs.
+// - ipExcludeList: a slice of net.IP that represents the list of IPs to be excluded.
+// - sorted: a boolean indicating whether the resulting list should be sorted.
+// - expectCount: an integer specifying the maximum number of IPs to return. If expectCount <= 0, all IPs will be returned.
+func getIPDiffSet(ipSourceList, ipExcludeList []net.IP, sorted bool, expectCount int) []net.IP {
+	ips2Map := make(map[[16]byte]struct{}, len(ipExcludeList))
+	for _, ip := range ipExcludeList {
 		if ip != nil {
-			marks[ip.String()] = true
+			ips2Map[[16]byte(ip.To16())] = struct{}{}
 		}
 	}
 
-	for _, ip := range ips2 {
+	var result []net.IP
+	for _, ip := range ipSourceList {
 		if ip != nil {
-			delete(marks, ip.String())
+			if _, ok := ips2Map[[16]byte(ip.To16())]; !ok {
+				result = append(result, ip)
+				if expectCount > 0 && len(result) >= expectCount {
+					break
+				}
+			}
 		}
 	}
 
-	for k := range marks {
-		ips = append(ips, net.ParseIP(k))
+	if sorted && len(result) > 1 {
+		sort.Slice(result, func(i, j int) bool {
+			return bytes.Compare(result[i].To16(), result[j].To16()) < 0
+		})
 	}
 
-	if sorted {
-		sort.Slice(ips, func(i, j int) bool {
-			return bytes.Compare(ips[i].To16(), ips[j].To16()) < 0
-		})
+	return result
+}
+
+// FindAvailableIPs find available ip list in range
+func FindAvailableIPs(ipRanges []string, ipList []net.IP, count int) []net.IP {
+	ipMap := make(map[[16]byte]struct{}, len(ipList))
+	for _, ip := range ipList {
+		if ip != nil {
+			ipMap[[16]byte(ip.To16())] = struct{}{}
+		}
 	}
 
-	return ips
+	var availableIPs []net.IP
+
+	for _, ipRange := range ipRanges {
+		if count == 0 {
+			break
+		}
+
+		ips := strings.Split(ipRange, "-")
+		startIP := net.ParseIP(ips[0])
+		var endIP net.IP
+		if len(ips) == 2 {
+			endIP = net.ParseIP(ips[1])
+		} else {
+			endIP = startIP
+		}
+		if startIP == nil || endIP == nil {
+			continue
+		}
+		if bytes.Compare(startIP, endIP) == 1 {
+			continue
+		}
+
+		stop := nextIP(endIP)
+		for ip := startIP; !ip.Equal(stop) && count > 0; ip = nextIP(ip) {
+			if _, exists := ipMap[[16]byte(ip.To16())]; !exists {
+				availableIPs = append(availableIPs, ip)
+				count--
+			}
+		}
+	}
+
+	return availableIPs
+}
+
+func nextIP(ip net.IP) net.IP {
+	next := make(net.IP, len(ip))
+	copy(next, ip)
+
+	for i := len(next) - 1; i >= 0; i-- {
+		next[i]++
+		if next[i] != 0 {
+			break
+		}
+	}
+	return next
 }
 
 // IPsUnionSet calculates the union set of two IP address slices.
diff --git a/pkg/ippoolmanager/ippool_manager.go b/pkg/ippoolmanager/ippool_manager.go
index 4aa7609bb..641e22170 100644
--- a/pkg/ippoolmanager/ippool_manager.go
+++ b/pkg/ippoolmanager/ippool_manager.go
@@ -173,12 +173,12 @@ func (im *ipPoolManager) genRandomIP(ctx context.Context, ipPool *spiderpoolv2be
 		return nil, err
 	}
 
-	totalIPs, err := spiderpoolip.AssembleTotalIPs(*ipPool.Spec.IPVersion, ipPool.Spec.IPs, ipPool.Spec.ExcludeIPs)
+	unAvailableIPs, err := spiderpoolip.ParseIPRanges(*ipPool.Spec.IPVersion, ipPool.Spec.ExcludeIPs)
 	if err != nil {
 		return nil, err
 	}
 
-	availableIPs := spiderpoolip.IPsDiffSet(totalIPs, append(reservedIPs, usedIPs...), false)
+	availableIPs := spiderpoolip.FindAvailableIPs(ipPool.Spec.IPs, append(unAvailableIPs, append(reservedIPs, usedIPs...)...), 1)
 	if len(availableIPs) == 0 {
 		// traverse the usedIPs to find the previous allocated IPs if there be
 		// reference issue: https://github.com/spidernet-io/spiderpool/issues/2517
diff --git a/pkg/subnetmanager/subnet_manager.go b/pkg/subnetmanager/subnet_manager.go
index bf2af54c8..6c120ae8e 100644
--- a/pkg/subnetmanager/subnet_manager.go
+++ b/pkg/subnetmanager/subnet_manager.go
@@ -259,7 +259,7 @@ func (sm *subnetManager) preAllocateIPsFromSubnet(ctx context.Context, subnet *s
 			// TODO(Icarus9913): optimize it
 			// If we have difference sets, which means the subnet updated its status successfully in the last shrink operation but the next ippool update operation failed.
 			// In the situation, the ippool may allocate or release one of ips that subnet updated. So, we should correct the subnet status.
-			if len(spiderpoolip.IPsDiffSet(poolAllocatedIPs, subnetPoolIPs, false)) != 0 {
+			if spiderpoolip.IsDiffIPSet(poolAllocatedIPs, subnetPoolIPs) {
 				log.Sugar().Warnf("the last whole auto-created pool scale operation interrupted, try to correct SpiderSubnet %s status %s IP allocations", subnet.Name, pool.Name)
 				poolTotalIPs, err := spiderpoolip.ParseIPRanges(ipVersion, pool.Spec.IPs)
 				if nil != err {
diff --git a/pkg/subnetmanager/subnet_validate.go b/pkg/subnetmanager/subnet_validate.go
index 84effa05c..8b0a03156 100644
--- a/pkg/subnetmanager/subnet_validate.go
+++ b/pkg/subnetmanager/subnet_validate.go
@@ -247,8 +247,7 @@ func (sw *SubnetWebhook) validateOrphanIPPool(ctx context.Context, subnet *spide
 			if nil != err {
 				return field.InternalError(ipsField, fmt.Errorf("failed to assemble the total IP addresses of the Subnet '%s', error: %v", subnet.Name, err))
 			}
-			diffSet := spiderpoolip.IPsDiffSet(poolIPs, subnetIPs, false)
-			if len(diffSet) != 0 {
+			if spiderpoolip.IsDiffIPSet(poolIPs, subnetIPs) {
 				return field.Invalid(ipsField, subnet.Spec.IPs, fmt.Sprintf("SpiderIPPool '%s' owns some IP addresses that SpiderSubnet '%s' can't control", tmpPool.Name, subnet.Name))
 			}
 		}


Test patch:
diff --git a/pkg/ip/ip_test.go b/pkg/ip/ip_test.go
index 8caf3a6ba..a7cb32983 100644
--- a/pkg/ip/ip_test.go
+++ b/pkg/ip/ip_test.go
@@ -5,6 +5,7 @@ package ip_test
 
 import (
 	"net"
+	"testing"
 
 	. "github.com/onsi/ginkgo/v2"
 	. "github.com/onsi/gomega"
@@ -383,3 +384,72 @@ var _ = Describe("IP", Label("ip_test"), func() {
 		})
 	})
 })
+
+func TestFindAvailableIPs(t *testing.T) {
+	tests := []struct {
+		name     string
+		ipRanges []string
+		ipList   []net.IP
+		count    int
+		expected []net.IP
+	}{
+		{
+			name:     "IPv4",
+			ipRanges: []string{"172.18.40.40"},
+			ipList:   []net.IP{},
+			count:    1,
+			expected: []net.IP{net.ParseIP("172.18.40.40")},
+		},
+		{
+			name:     "IPv4 range with some used IPs",
+			ipRanges: []string{"192.168.1.1-192.168.1.5"},
+			ipList:   []net.IP{net.ParseIP("192.168.1.2"), net.ParseIP("192.168.1.4")},
+			count:    3,
+			expected: []net.IP{net.ParseIP("192.168.1.1"), net.ParseIP("192.168.1.3"), net.ParseIP("192.168.1.5")},
+		},
+		{
+			name:     "IPv4 range with all IPs available",
+			ipRanges: []string{"10.0.0.1-10.0.0.3"},
+			ipList:   []net.IP{},
+			count:    2,
+			expected: []net.IP{net.ParseIP("10.0.0.1"), net.ParseIP("10.0.0.2")},
+		},
+		{
+			name:     "IPv6 range with some used IPs",
+			ipRanges: []string{"2001:db8::1-2001:db8::5"},
+			ipList:   []net.IP{net.ParseIP("2001:db8::2"), net.ParseIP("2001:db8::4")},
+			count:    3,
+			expected: []net.IP{net.ParseIP("2001:db8::1"), net.ParseIP("2001:db8::3"), net.ParseIP("2001:db8::5")},
+		},
+		{
+			name:     "IPv6 range with all IPs available",
+			ipRanges: []string{"2001:db8::1-2001:db8::3"},
+			ipList:   []net.IP{},
+			count:    2,
+			expected: []net.IP{net.ParseIP("2001:db8::1"), net.ParseIP("2001:db8::2")},
+		},
+		{
+			name:     "Mixed IPv4 and IPv6 ranges",
+			ipRanges: []string{"192.168.1.1-192.168.1.3", "2001:db8::1-2001:db8::3"},
+			ipList:   []net.IP{net.ParseIP("192.168.1.2"), net.ParseIP("2001:db8::2")},
+			count:    4,
+			expected: []net.IP{net.ParseIP("192.168.1.1"), net.ParseIP("192.168.1.3"), net.ParseIP("2001:db8::1"), net.ParseIP("2001:db8::3")},
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			got := spiderpoolip.FindAvailableIPs(tt.ipRanges, tt.ipList, tt.count)
+			if len(got) != len(tt.expected) {
+				t.Errorf("expected %v, got %v", tt.expected, got)
+				return
+			}
+			for i := range got {
+				if !got[i].Equal(tt.expected[i]) {
+					t.Errorf("expected %v, got %v", tt.expected, got)
+					break
+				}
+			}
+		})
+	}
+}
diff --git a/test/e2e/common/spidersubnet.go b/test/e2e/common/spidersubnet.go
index d0c57a3fe..42c2dfe8c 100644
--- a/test/e2e/common/spidersubnet.go
+++ b/test/e2e/common/spidersubnet.go
@@ -378,8 +378,7 @@ LOOP:
 							return err
 						}
 
-						diffIps := ip.IPsDiffSet(ips1, ips2, false)
-						if diffIps != nil {
+						if ip.IsDiffIPSet(ips1, ips2) {
 							GinkgoWriter.Printf("inconsistent ip records in subnet %v/%v and pool %v/%v \n", subnetName, ips2, pool.Name, ips1)
 							continue LOOP
 						}