netaddr.IP: a new IP address type for Go

Brad Fitzpatrick on
Photo of Brad Fitzpatrick

Tailscale needed a better IP address type

Tailscale is a networking application so naturally we need to work with and manipulate IP addresses and sets of IP addresses often.

Being written almost entirely in Go, the obvious choice would be for Tailscale to use the Go standard library’s net.IP address type for individual IPs and net.IPNet type for networks. Unfortunately, the standard library’s types have a number of problems, so we wrote a new package, inet.af/netaddr (github) containing a new IP type and more.

What’s wrong with Go’s net.IP type?

When I was working on Go full time, I filed Go issue #18804 to track some things that aren’t great about Go’s IP address:

Some of this was by design at the time, before Go 1 locked in the compatibility promise in 2012, but much of it was just never considered well or predated enough experience with Go to learn what patterns worked well and which didn’t. In any case, the Go standard library can’t change much now.

What do we want?

In summary, this is what we want, and how Go’s net.IP fares:

FeatureGo's net.IP
Immutable❌, slice
Comparable❌, slice
Small❌, 28-56 bytes
Allocation free❌, slice's underlying array
Supports IPv4 & IPv6
Can distinguish IPv4/IPv6❌, #37921
Supports IPv6 zones❌, has separate net.IPAddr type
Opaque type❌, defined as []byte
Interops with standard library

So, let’s do better.

This story has several parts:

Take 1: wgcfg.IP

The story begins in April 2019 with 89476f8cb5 in which David Crawshaw, aware of all these problems, created an IP type like:

// Internally the address is always represented in its IPv6 form.
// IPv4 addresses use the IPv4-in-IPv6 syntax.
type IP struct {
       Addr [16]byte
}

That’s a bit better:

Featurenet.IPwgcfg.IP
Immutable❌, slice
Comparable❌, slice
Small❌, 28-56B ✅, 16B
Allocation free
Supports IPv4 & IPv6
Can distinguish IPv4/IPv6
Supports IPv6 zones
Opaque type
Interops with standard library ❌, with adapters

We used that for quite a bit in some places but it wasn’t quite good enough to start using more widely.

Making it opaque would be easy enough (unexporting the Addr field, renaming it to addr), but that still would leave us with the lost address family bit and lack of IPv6 zones.

Take 2: netaddr.IP, opaque comparable interfaces

One bit about the Go language specification that many people don’t know is is that interfaces are comparable (support == & being map keys), but they panic at runtime if the underlying value in the interface is not comparable.

Taking advantage of that to be comparable, the first version of netaddr.IP was represented like this:

type IP struct {
     ipImpl
}

type ipImpl interface {
     is4() bool
     is6() bool
     String() string
}

type v4Addr [4]byte
type v6Addr [16]byte
type v6AddrZone struct {
      v6Addr
      zone string
}

Notably, the IP type there is an opaque struct embedding an interface. An interface, being 2 words wide, is 16 bytes on 64-bit machines, so the IP type here is 16 bytes. That’s better than the standard library’s 24 byte (3 word) slice header used for net.IP. But both still need to a pointer to the actual bytes of the IP address. At least with this representation, the interface’s type word encodes whether the address is IPv4, IPv6, or IPv6 with a zone scope.

It was good in some ways, but not perfect:

Feature net.IP wgcfg.IP "Take 2"
Immutable❌, slice
Comparable❌, slice
Small❌, 28-56B ✅, 16B 🤷, 20-32B
Allocation free
Supports IPv4 & IPv6
Can distinguish IPv4/IPv6
Supports IPv6 zones
Opaque type
Interops with standard library ❌, with adapters ❌, with adapters

I got the impression that Crawshaw in particular was very “meh” on this representation needing to allocate compared to our existing wgcfg.IP type.

Let’s do better.

Take 3: allocation-free 24 byte representation

At some point I realized that the maximum tolerable size of our IP address type was 24 bytes: that’s the same size as Go’s net.IP slice header, and Go slices are very common. A time.Time is also a 24 byte value type, so surely the compiler deals with 24 byte value types just fine. But mostly I didn’t want our new IP type to be worse in any dimension compared to the standard library’s net.IP, which is (in part) 24 bytes. So I somewhat arbitrarily decreed that 24 bytes was our limit.

Since an IPv6 address is already 16 bytes, that leaves us 8 bytes remaining in which to encode the following things:

Also, we need to be comparable.

Using an interface is out: that’s two words (16 bytes), so that’s too big. Likewise, a string is also two words (a pointer and length), so that’s out.

We could play bit-packing games like:

type IP struct {
   addr          [16]byte
   zoneAndFamily uint64
}

… and try to encode the address family and zone into the 64 zoneAndFamily bits, but how?

If we have 1 or 2 bits for the address family, we have 62 or 63 bits left. Various options included:

So, I didn’t like any of those options.

But then I thought of something gross. Or awesome.

We could use a pointer!

type IP struct {
    addr          [16]byte
    zoneAndFamily *T
}

Ignoring the zone and actual definition of T for now, the address family is easy: we make three sentinel pointer values to represent the family, and whether the IP address is the zero value (as opposed to, say, actually "0.0.0.0").

var (
     z0 *T        // nil for the zero value
     z4 = new(T)  // sentinel value to mean IPv4
     z6 = new(T)  // sentinel value to mean IPv6 with no zone
)

But how do we represent the zone string such that it’s comparable so Go’s == works and IP values can be map keys?

Remember, our goal is that this prints true:

   ip1, _ := netaddr.ParseIP("fe80::2%eth0")
   ip2, _ := netaddr.ParseIP("fe80::2%eth0")
   fmt.Println(ip1 == ip2) // want true

But comparisons on Go pointers compare the pointer values, not what they point to. That is, new(string) != new(string).

So we need to make sure that two separate ParseIP calls with same "eth0" zone at any point and any time in the program always return the same pointer value for that process.

That implies we need a mapping between these pointer values and their process-wide-unique names ("eth0", etc). If this sounds a lot like the earlier problem with the zone indexes, it is, but there’s one thing that’s different: when shoving a zone index into an integer above, we didn’t have a way to do any cleanup of the mapping table. But with a pointer, we can use runtime.SetFinalizer. Using SetFinalizer is gross and scary and you should think twice before using it. We sure did. But sometimes gross and scary things are the right tool for the job.

What we ended up writing was the go4.org/intern package to hide the bodies so our inet.af/netaddr package could have plausible deniability as to its innocence.

The go4.org/intern package is tiny and worth reading in full (and perhaps worthy of a future blog post on its own), but the core of it is this ungodliness:

var (
	// mu guards valMap, a weakref map of *Value by underlying value.
	// It also guards the resurrected field of all *Values.
	mu      sync.Mutex
	valMap  = map[key]uintptr{} // to uintptr(*Value)
)

// A Value pointer is the handle to an underlying comparable value.
// See func Get for how Value pointers may be used.
type Value struct {
	_      [0]func() // prevent people from accidentally using value type as comparable
	cmpVal interface{}
	// resurrected is guarded by mu (for all instances of Value).
	// It is set true whenever v is synthesized from a uintptr.
	resurrected bool
}

func GetByString(s string) *Value {
	return get(key{s: s, isString: true})
}

// We play unsafe games that violate Go's rules (and assume a non-moving
// collector). So we quiet Go here.
// See the comment below Get for more implementation details.
//go:nocheckptr
func get(k key) *Value {
	mu.Lock()
	defer mu.Unlock()

	var v *Value
	if addr, ok := valMap[k]; ok {
		v = (*Value)((unsafe.Pointer)(addr))
		v.resurrected = true
	}
	if v != nil {
		return v
	}
	v = k.Value()
	runtime.SetFinalizer(v, finalize)
	valMap[k] = uintptr(unsafe.Pointer(v))
	return v
}

func finalize(v *Value) {
	mu.Lock()
	defer mu.Unlock()
	if v.resurrected {
		// We lost the race. Somebody resurrected it while we
		// were about to finalize it. Try again next round.
		v.resurrected = false
		runtime.SetFinalizer(v, finalize)
		return
	}
	delete(valMap, keyFor(v.cmpVal))
}

Basically, it’s playing unsafe games behind the Go garbage collector’s back, hiding pointers in untyped uintptr integers so Go will be forced to eventually garbage collect things which then causes the finalizer to be invoked to step in and either clean up its lies or clean up the map.

But the end result is that this is now true:

   intern.GetByString("eth0") == intern.GetByString("eth0")

So our IP representation can be:

type IP struct {
    addr [16]byte
    z    *intern.Value // zone and family
}

var (
     z0    *intern.Value        // nil for the zero value
     z4    = new(intern.Value)  // sentinel value to mean IPv4
     z6noz = new(intern.Value)  // sentinel value to mean IPv6 with no zone
)

The accessors to get/set the zone are then:

// Zone returns ip's IPv6 scoped addressing zone, if any.
func (ip IP) Zone() string {
	if ip.z == nil {
		return ""
	}
	zone, _ := ip.z.Get().(string)
	return zone
}

// WithZone returns an IP that's the same as ip but with the provided
// zone. If zone is empty, the zone is removed. If ip is an IPv4
// address it's returned unchanged.
func (ip IP) WithZone(zone string) IP {
	if !ip.Is6() {
		return ip
	}
	if zone == "" {
		ip.z = z6noz
		return ip
	}
	ip.z = intern.GetByString(zone)
	return ip
}

How we’d do?

Feature net.IP netaddr.IP
Immutable❌, slice
Comparable❌, slice
Small❌, 28-56B ✅, 24B, always
Allocation free
Supports IPv4 & IPv6
Can distinguish IPv4/IPv6
Supports IPv6 zones
Opaque type
Interops with standard library 🤷, adaptor methods

Nailed it.

Take 4: uint64s for speed

We were pretty happy, but Dave Anderson took advantage of the type’s opaque representation and changed the representation to make it faster in 4eb479db13, replacing the addr [16]byte with a pair of uint64 values:

type IP struct {
	// hi and lo are the bits of an IPv6 address. If z==z4, hi and lo
	// contain the IPv4-mapped IPv6 address.
	//
	// hi and lo are constructed by interpreting a 16-byte IPv6
	// address as a big-endian 128-bit number. The most significant
	// bits of that number go into hi, the rest into lo.
	//
	// For example, 0011:2233:4455:6677:8899:aabb:ccdd:eeff is stored as:
	//  hi = 0x0011223344556677
	//  lo = 0x8899aabbccddeeff
	//
	// We store IPs like this, rather than as [16]byte, because it
	// turns most operations on IPs into arithmetic and bit-twiddling
	// operations on 64-bit registers, which is much faster than
	// bytewise processing.
	hi, lo uint64

	// z is a combination of the address family and the IPv6 zone.
	z *intern.Value
}

The compiler liked that much more.

Take 5: a uint128 type

But why stop there? Being able to change the representation without affecting the API is too much fun, so in 318330f177 I replaced the uint64 pair with a new uint128 type, as Go doesn’t have a native one.

We’re now at:

type uint128 [2]uint64

type IP struct {
	addr uint128
	z    *intern.Value
}

But the compiler didn’t like that, so bf0e22f9f3 broke it back down into:

type uint128 struct {
	hi uint64
	lo uint64
}

And that’s basically where we’re at today.

We’re talking about breaking out the uint128 type into its own package but haven’t done so yet.

Other inet.af/netaddr fun

In addition to just IP addresses, inet.af/netaddr contains:

As one contrived example, this code:

var b netaddr.IPSetBuilder
b.AddPrefix(netaddr.MustParseIPPrefix("10.0.0.0/8"))
b.Remove(netaddr.MustParseIP("10.2.3.4"))
s, _ := b.IPSet()
fmt.Println(s.Ranges())
fmt.Println(s.Prefixes())

Outputs:

[10.0.0.0-10.2.3.3 10.2.3.5-10.255.255.255]
[10.0.0.0/15 10.2.0.0/23 10.2.2.0/24 10.2.3.0/30 10.2.3.5/32 10.2.3.6/31 10.2.3.8/29 10.2.3.16/28 10.2.3.32/27 10.2.3.64/26 10.2.3.128/25 10.2.4.0/22 10.2.8.0/21 10.2.16.0/20 10.2.32.0/19 10.2.64.0/18 10.2.128.0/17 10.3.0.0/16 10.4.0.0/14 10.8.0.0/13 10.16.0.0/12 10.32.0.0/11 10.64.0.0/10 10.128.0.0/9]

FAQ

Should you use netaddr.IP?

If you work with a lot of IP addresses and sets, ranges, and prefixes thereof, you’d probably benefit from using netaddr.IP over the standard library’s types.

Is the API stable?

Mostly. We haven’t done a 1.0.0 yet and we might yet change a few minor things, but it’s pretty much done at this point.

What’s with the package name’s inet.af?

AF_INET, of course.

Was IPv6 worth it?

It is what it is.

This was too many words.

If you’d like this blog post in video form, my FOSDEM 2021 talk, “Go at Tailscale” discusses this starting at time 18:45.

Thanks

Writing the inet.af/netaddr package was a fun collaboration with @crawshaw, @danderson, @josharian, @mdlayher, and @tklauser.

Subscribe for monthly updates

Product updates, blog posts, company news, and more.

Too much email? RSS Twitter