kube-proxy iptables code clarity cleanups

[thockin]

Looking at PRs in the iptables code makes my heart ache. I stared at this code for a while and have been looking for ways to make it more manageable without making it significantly less readable.

This PR explores some of the "low hanging fruit".

/kind cleanup

NONE

[k8s-ci-robot]

@thockin: This issue is currently awaiting triage.

If a SIG or subproject determines this is a relevant issue, they will accept it by applying the triage/accepted label and provide further guidance.

The triage/accepted label can be added by org members by writing /triage accepted in a comment.

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: thockin

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

• pkg/proxy/OWNERS [thockin]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

[thockin]

OK to review this now

[aojea]

yeah, this was a bit obscure

[aojea]

/lgtm

[danwinship]

so this breaks the "not reallocating args thing we had before". args was initialized as

	args := make([]string, 64)

at the top of syncProxyRules, before the start of the range proxier.serviceMap loop, and then each time we started a new arg list, it would do args = args[:0] to truncate it while keeping the underlying storage.

but a single args = prepend(...) breaks that for the entire rest of the current syncProxyRules. So we will now be doing A LOT more memory allocations than we had been doing before.

[aojea]

great catch

package main

import (
	"testing"
)

func BenchmarkPrependAlloc(b *testing.B) {
	a := make([]int, b.N)

	for i := 0; i < b.N; i++ {
		a = prepend(a, i)
	}
}

func BenchmarkAlloc(b *testing.B) {
	a := make([]int, b.N)

	for i := 0; i < b.N; i++ {
		a = append(a, i)
	}
}

func prepend(sl []int, args ...int) []int {
	return append(args, sl...)
}

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz
BenchmarkPrependAlloc-12    	  112240	    171318 ns/op
BenchmarkAlloc-12           	164673328	         6.298 ns/op
PASS

[thockin]

We can either a) change prepend to allocate the full capacity of args (so it allocs but only once); b) change prepend to shuffle the elements down and insert into the same slice; c) change Write to take a [][]string (scatter-gather style). The truth is that every time we do Write() with a list of args, we cause a slice allocation behind the scenes. I'm skeptical that re-using args is a big win.

If we want to take this seriously, we should explore how to do it better in all cases.

[danwinship]

change Write to take a [][]string (scatter-gather style). The truth is that every time we do

Your sentence got cut off, but whatever you were going to say, that idea sounds really good...

matchClusterIP := []string{
	"-m", protocol, "-p", protocol,
	"-d", utilproxy.ToCIDR(svcInfo.ClusterIP()),
	"--dport", strconv.Itoa(svcInfo.Port()),
}

if hasEndpoints {
	comment := utilproxy.Comment("%s cluster IP"`, svcNameString)
	if proxier.masqueradeAll {
		proxier.natRules.Write(
			[]string{"-A", string(svcChain)},
			comment,
			matchClusterIP,
			[]string{"-j", string(KubeMarkMasqChain)},
		)
	} else if proxier.localDetector.Implemented() {
		// ...
		proxier.natRules.Write(
			[]string{"-A", string(svcChain)},
			comment,
			proxier.localDetector.JumpIfNotLocal(KubeMarkMasqChain),
		)
	}
	proxier.natRules.Write(
		[]string{"-A", string(kubeServicesChain)},
		comment,
		matchClusterIP,
		[]string{"-j", string(svcChain)},
	)
} else {
	// No endpoints.
	proxier.filterRules.Write(
		[]string{"-A", string(kubeServicesChain)},
		utilproxy.Comment("%s has no endpoints", svcNameString),
		matchClusterIP,
		[]string{"-j", "REJECT"},
	)
}

(utilproxy.Comment is left as an exercise to the reader). Maybe even

func addToChain(chain utiliptables.Chain) []string {
	return []string{"-A", string(chain)}
}

func jumpToChain(chain utiliptables.Chain) []string{
	return []string{"-j", string(chain)}
}

[danwinship]

Or even have Write(args ...interface{}) and let you pass an arbitrary combination of string, []string, and utiliptables.Chain...

	proxier.filterRules.Write(
		"-A", kubeServicesChain,
		utilproxy.Comment("%s has no endpoints", svcNameString),
		matchClusterIP,
		"-j", "REJECT",
	)

[thockin]

Adding a string-or-slice mode to write seems plausible, and makes the net diff smaller AND opens further opportunities.

I want to be careful not to make this code any less readable than it already is. Let me try a couple things.

[thockin]

Updated. I'll take it apart:

BenchmarkOneAppend-6                   	12719592	        95.78 ns/op	      48 B/op	       1 allocs/op
BenchmarkOneVariadic-6                 	13332460	        90.14 ns/op	      48 B/op	       1 allocs/op
BenchmarkOnePrepend-6                  	 6574177	       183.5 ns/op	     176 B/op	       2 allocs/op
BenchmarkOnePrependInPlace-6           	11058524	       108.8 ns/op	      48 B/op	       1 allocs/op
BenchmarkOneSG-6                       	11836407	       100.9 ns/op	      48 B/op	       1 allocs/op
BenchmarkOneIntf-6                     	12110347	        98.34 ns/op	      48 B/op	       1 allocs/op

No penalty for variadic calls. Prepend is bad. In-place prepend is not bad but surprising. Scatter-gather and using an interface both are within spitting distance of no-op.

Run these under more load to see amortize overhead out:

BenchmarkAppend-6                      	 3696194	       286.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrepend-6                     	  394273	      2944 ns/op	    6464 B/op	      32 allocs/op
BenchmarkPrependInPlaceManual-6        	 1438062	       747.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrependInPlaceCopy-6          	 2344239	       519.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkScatterGatherFlat-6           	 1000000	      1064 ns/op	     608 B/op	      17 allocs/op
BenchmarkScatterGatherDeep-6           	  897902	      1352 ns/op	    1120 B/op	      33 allocs/op

Append doesn't actually work, but it sets the bar. Prepend is 10x slower. In-place prepend is only 2x slower. Scatter-gather turns into a different form of the prepend problem. These results are not very interesting.

A more representative test (look at the gist for code):

BenchmarkReprSGAsFewAsPossible-6       	11684551	        92.63 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprSGMany-6                  	 3608090	       333.5 ns/op	     288 B/op	       5 allocs/op
BenchmarkReprSGManyInline-6            	10851805	       100.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfAsFewAsPossible-6   	11803284	        91.16 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfMany-6              	 5385872	       235.8 ns/op	     160 B/op	       3 allocs/op
BenchmarkReprIntfManyInline-6        	10768394	        98.16 ns/op	       0 B/op	       0 allocs/op

These show that both SG and intf are viable, and depending how we use them can perform well. Some code readability considerations...

To explore code reading:

BenchmarkReprClauseAsFewAsPossible-6   	11474544	        91.50 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprClauseMany-6              	 4877307	       244.6 ns/op	     128 B/op	       4 allocs/op
BenchmarkReprClauseManyInline-6        	 6517003	       182.9 ns/op	      72 B/op	       2 allocs/op

This adds a function-type argument. I like the code but perf leaves something to be desired.

BenchmarkReprFuncAsFewAsPossible-6     	11681811	        91.60 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprFuncAsFewAsPossible2-6    	10203375	       103.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprFuncMany-6                	 5535034	       216.0 ns/op	     160 B/op	       3 allocs/op
BenchmarkReprFuncManyInline-6          	10537470	       101.1 ns/op	       0 B/op	       0 allocs/op

This is more or less Intf with function helpers. I am not sure it makes the code any clearer.

Take a look and tell me what you think

[thockin]

One more:

We could define a "WordList" and "WordSlice" type, which manage an offset slice underneath so prepends are free. Code would look like:

wl := NewWordList(64, 8) // capacity and zero-offset
// ... later
sl := a.Slice(0, 0)  // a view into wl
sl = sl.Append("-m", protocol, "-p", protocol)
sl = sl.Append("-d", ip, "--dport", port)
sl = sl.Append("-j", "FOOBAR")
proxier.natRules.write(sl.Prepend("-X", "CHAIN").Slice())

We could user helper funcs if we think it is cleaner:

sl = sl.Append(protocolFunc(protocol)...)
sl = sl.Append(destFunc(ip, port)...)
sl = sl.Append(jumpFunc("FOOBAR")...)
proxier.natRules.write(sl.Prepend(appendFunc("CHAIN")...).Slice())

We could maybe drop the ....

We could maybe even get more DSLish, maybe?

I wrote a simple form of the code, it's only 80 LOC. Scatter-gather and Intf are simpler (less LOC) but maybe this is cleaner? Not sure.

[danwinship]

These show that both SG and intf are viable, and depending how we use them can perform well. Some code readability considerations...

BenchmarkReprIntfManyInline is using arrays that it doesn't need to use though:

		writeIntf(&buf,
			"-A", "CHAIN",
			[]string{"-m", protocol, "-p", protocol},
			[]string{"-d", ip, "--dport", port},
			[]string{"-j", "FOOBAR"})

This could just be

		writeIntf(&buf,
			"-A", "CHAIN",
			"-m", protocol, "-p", protocol,
			"-d", ip, "--dport", port,
			"-j", "FOOBAR")

which doesn't seem unreadable to me at all.

Of course, it also doesn't test the interface{} functionality. But we could do:

		matchService := []string{
			"-m", protocol, "-p", protocol,
			"-d", ip, "--dport", port,
		}
		writeIntf(&buf,
			"-A", "CHAIN",
			matchService,
			"-j", "FOOBAR")

which again seems readable to me.

FTR

BenchmarkReprIntfAsFewAsPossible-12            	15124519	        80.31 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfManyInlinePreArray-12         	14044212	        82.45 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfManyInlineNoExtraArrays-12    	14103712	        84.79 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfManyInlineNonRecursive-12     	13345648	        88.40 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfManyInline-12                 	12820171	        90.49 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfMany-12                       	 2739234	       437.9 ns/op	     424 B/op	       8 allocs/op

(PreArray is the one with matchService, NoExtraArrays is the one with all the arrays replaced with individual strings. NonRecursive was another experiment, with making writeIntf loop over []string{} arguments itself rather than doing write(buf, x...).)

https://gist.github.com/danwinship/b5524b557dc8ab8b544ab25f0df9ecf7

We could define a "WordList" and "WordSlice" type, which manage an offset slice underneath so prepends are free.

I think we can just avoid needing to do prepends

We could maybe even get more DSLish, maybe?

Yeah, I was wondering about that when I suggested utilproxy.Comment, jumpToChain etc... I'm not sure if it's a good idea, because we're not going to be able to completely abstract away iptables syntax, so we'd probably just end up making it so that people need to learn both iptables syntax and our DSL if they want to hack on the code. It may be better to just keep all the iptables syntax explicit, but just make it easier to efficiently reuse bits and pieces of it as needed.

[thockin]

using arrays that it doesn't need to use

I was just trying to push the pattern and see where it broke down. Using many slices allows the proliferation of "builder" functions which each return a []string.

It may be better to just keep all the iptables syntax explicit, but just make it easier to efficiently reuse bits and pieces of it as needed.

+1

The main downside of interface{} is that it changes a compile time error (passing the wrong type) into a runtime error.

Shall we agree that everything but scatter-gather and interface models are ruled out?

[thockin]

all names subject to revision :)

type WordList struct {
	words []string
	zero  int // index into words
}

//FIXME: uint?
func NewWordList(capacity, zero int) *WordList {
	wl := &WordList{}
	wl.words = make([]string, capacity)
	wl.zero = zero
	return wl
}

func (wl *WordList) append(idx int, words ...string) {
	wl.maybeGrowRight(idx, len(words))
	copy(wl.words[wl.zero+idx:], words)
}

func (wl *WordList) maybeGrowRight(idx, n int) {
	if len(wl.words)-(wl.zero+idx) >= n {
		return
	}
	if n < len(wl.words)-wl.zero {
		n = len(wl.words) - wl.zero
	}
	tmp := make([]string, len(wl.words)+n)
	copy(tmp[wl.zero:], wl.words[wl.zero:])
	wl.words = tmp
}

func (wl *WordList) prepend(idx int, words ...string) {
	wl.maybeGrowLeft(idx, len(words))
	copy(wl.words[wl.zero+idx:], words)
}

//FIXME: if idx is neg, prepend.  one func?
func (wl *WordList) maybeGrowLeft(idx, n int) {
	if wl.zero+idx >= 0 {
		return
	}
	if n < wl.zero {
		n = wl.zero
	}
	tmp := make([]string, len(wl.words)+n)
	copy(tmp[n:], wl.words)
	wl.words = tmp
	wl.zero += n
}

type WordSlice struct {
	wl    *WordList
	start int // index into wl.words[wl.zero:]
	size  int
}

//FIXME: uint?
func (wl *WordList) Slice(start, size int) WordSlice {
	return WordSlice{
		wl:    wl,
		start: start,
		size:  size,
	}
}

func (ws WordSlice) Append(words ...string) WordSlice {
	ws.wl.append(ws.start+ws.size, words...)
	ws.size += len(words)
	return ws
}

func (ws WordSlice) Prepend(words ...string) WordSlice {
	ws.wl.prepend(ws.start-len(words), words...)
	ws.start -= len(words)
	ws.size += len(words)
	return ws
}

func (ws WordSlice) Slice() []string {
	//FIXME: hide zero stuff in WL
	return ws.wl.words[ws.wl.zero+ws.start : ws.wl.zero+ws.start+ws.size]
}

[thockin]

Updated to just play with SG and Intf:

https://gist.github.com/thockin/8fc599cc4adc7aba72a367057704a798#file-bench2_test-go

Each "Repr" test covers all 3 patterns of usage.

BenchmarkOneAppend-6                   	12585250	        94.25 ns/op	      48 B/op	       1 allocs/op
BenchmarkOneVariadic-6                 	13252210	        90.64 ns/op	      48 B/op	       1 allocs/op
BenchmarkOnePrepend-6                  	 6501661	       184.9 ns/op	     176 B/op	       2 allocs/op
BenchmarkOneSG-6                       	12065289	        99.08 ns/op	      48 B/op	       1 allocs/op
BenchmarkOneIntf-6                     	11805279	       101.4 ns/op	      48 B/op	       1 allocs/op

This shows intf and SG are same ballpark as append and variadic.

BenchmarkReprSGMinSlices-6             	 3983193	       264.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprSGMinSlicesHelpers-6      	 4134222	       296.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprSGManySlices-6            	 1709065	       706.9 ns/op	     480 B/op	       9 allocs/op
BenchmarkReprSGManySlicesHelpers-6     	 1701709	       703.9 ns/op	     480 B/op	       9 allocs/op
BenchmarkReprIntfMinSlices-6           	 3839482	       278.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfMinSlicesHelpers-6    	 3778912	       298.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkReprIntfManySlices-6          	 1266530	       904.1 ns/op	     600 B/op	      15 allocs/op
BenchmarkReprIntfManySlicesHelpers-6   	 1327848	       901.1 ns/op	     600 B/op	      15 allocs/op

Whether we use helper funcs or not doesn't matter WRT allocs. That is a code-clarity question.

SG vs Intf is neglible - both are fine if we minimize number of slices and don't try to accumulate a slice of slices.

BenchmarkIntf-6                        	10762976	        99.28 ns/op	       0 B/op	       0 allocs/op
BenchmarkIntf2-6                       	10822875	        96.12 ns/op	       0 B/op	       0 allocs/op

Your intf2 is not notably faster

[thockin]

My feeling is that the strong typing of SG makes it a better choice at (to me) a low price. Agree or disagree?

…

On Sun, Nov 7, 2021, 12:23 PM Tim Hockin ***@***.***> wrote: Updated to just play with SG and Intf: https://gist.github.com/thockin/8fc599cc4adc7aba72a367057704a798#file-bench2_test-go Each "Repr" test covers all 3 patterns of usage. BenchmarkOneAppend-6 12585250 94.25 ns/op 48 B/op 1 allocs/op BenchmarkOneVariadic-6 13252210 90.64 ns/op 48 B/op 1 allocs/op BenchmarkOnePrepend-6 6501661 184.9 ns/op 176 B/op 2 allocs/op BenchmarkOneSG-6 12065289 99.08 ns/op 48 B/op 1 allocs/op BenchmarkOneIntf-6 11805279 101.4 ns/op 48 B/op 1 allocs/op This shows intf and SG are same ballpark as append and variadic. BenchmarkReprSGMinSlices-6 3983193 264.5 ns/op 0 B/op 0 allocs/op BenchmarkReprSGMinSlicesHelpers-6 4134222 296.4 ns/op 0 B/op 0 allocs/op BenchmarkReprSGManySlices-6 1709065 706.9 ns/op 480 B/op 9 allocs/op BenchmarkReprSGManySlicesHelpers-6 1701709 703.9 ns/op 480 B/op 9 allocs/op BenchmarkReprIntfMinSlices-6 3839482 278.0 ns/op 0 B/op 0 allocs/op BenchmarkReprIntfMinSlicesHelpers-6 3778912 298.8 ns/op 0 B/op 0 allocs/op BenchmarkReprIntfManySlices-6 1266530 904.1 ns/op 600 B/op 15 allocs/op BenchmarkReprIntfManySlicesHelpers-6 1327848 901.1 ns/op 600 B/op 15 allocs/op Whether we use helper funcs or not doesn't matter WRT allocs. That is a code-clarity question. SG vs Intf is neglible - both are fine if we minimize number of slices and don't try to accumulate a slice of slices. BenchmarkIntf-6 10762976 99.28 ns/op 0 B/op 0 allocs/op BenchmarkIntf2-6 10822875 96.12 ns/op 0 B/op 0 allocs/op Your intf2 is not notably faster — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#106158 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABKWAVETMKQBUZBJM5KE3OLUK3N4FANCNFSM5HLZDQSQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[thockin]

https://github.com/kubernetes/kubernetes/pull/106214/files for a PoC.

I admit that adding []string{} around things is annoying.

We could do the Intf model after all. Or we could do WriteWords() and WriteSlices() (or something).

Some of the append(args could become extra lines, if we think it reads better. E.g.:

-                        proxier.natRules.Write(append(args,
-                               "-s", utilproxy.ToCIDR(netutils.ParseIPSloppy(epInfo.IP())),
-                               "-j", string(KubeMarkMasqChain)))
+                        proxier.natRules.Write(
+                               args,
+                               []string{
+                                   "-s", utilproxy.ToCIDR(netutils.ParseIPSloppy(epInfo.IP())),
+                                   "-j", string(KubeMarkMasqChain),
+                               })

or:

                         proxier.natRules.Write(
-                                []string{"-A", string(svcChain)},
-                                append(args, "-j", string(KubeMarkMasqChain)))
+                                []string{"-A", string(svcChain)},
+                                args,
+                                []string{"-j", string(KubeMarkMasqChain)}
+                        )

...because those are all on-stack, they are zero-alloc.

[danwinship]

My feeling is that the strong typing of SG makes it a better choice at (to me) a low price. Agree or disagree?

I don't oppose SG, but I still prefer Intf. If the unit test is comprehensive enough (which it nearly is) then that should catch any type errors in the Intf version. (And we want a very comprehensive unit test to catch logic errors anyway, so relying on it to also catch type errors is not awful.)

[thockin]

Let's move discussion to #106214 ?