Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: net/netip: add netip.Prefix.Range #53236

Closed
gaissmai opened this issue Jun 4, 2022 · 18 comments
Closed

proposal: net/netip: add netip.Prefix.Range #53236

gaissmai opened this issue Jun 4, 2022 · 18 comments
Labels
Projects
Milestone

Comments

@gaissmai
Copy link

@gaissmai gaissmai commented Jun 4, 2022

When working with IP addresses and Prefixes (a.k.a CIDRs) often you have to merge and split address ranges. The current implementation hides for good reasons the internal IP address representation, but then it is unnecessary hard to calculate the last address of a prefix. Within the netip package it is very easy to calc the last address of a prefix.

// last = base | ^netmask

And for symmetry, please also add a netip.Prefix.Base method, even if this is already covered with netip.Prefix.Masked().Addr()

@gopherbot gopherbot added this to the Proposal milestone Jun 4, 2022
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 4, 2022

CC @bradfitz @josharian

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Jun 4, 2022
@josharian
Copy link
Contributor

@josharian josharian commented Jun 4, 2022

When bringing netip into std, there was an explicit decision to leave out the IP address calculation support in netaddr. I think if we want to start adding it, we should consider adding the full suite rather than nickel and diming it.

IPRange seems like the perfect fit for this particular use case. See https://pkg.go.dev/inet.af/netaddr#IPPrefix.Range

(netaddr might still need some updating for netip; I haven’t kept track of it recently.)

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 5, 2022

@josharian I can fully understand that the first reflex is: no feature creep in stdlib!

But, if tailscale would rebuild their inet-af/netaddr/IPRange on top of stdlib, they would also depend on certain additional methods from net/netip, if they want to be performant for large IP address input sets.

I don't want IPRange and IPSet to be put in the stdlib, I just suggest that the minimum useful methods be included, so that third party libs can build on them without having to implement/copy their own uint128 math module

With the already public methods netip.Addr.Compare, netip.Addr.Next/.Prev you can compute all meaningful needed methods for IPranges and IPSets, but if you want to use netip.ParsePrefix as input for ranges, then you need the Prefix.LastIP. Without uint128 and mask6 from the internal representation you have must convert to bytes, to use bitlen to process bytes and set bits in a for loop, convert back to uint128, which all is really not efficient compared to a logical operation on (uint64,unit64).

@gaissmai gaissmai closed this as completed Jun 5, 2022
@gaissmai gaissmai reopened this Jun 5, 2022
@gaissmai

This comment was marked as off-topic.

@josharian
Copy link
Contributor

@josharian josharian commented Jun 5, 2022

cc @danderson

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 5, 2022

One possible effective implementation would be (file netip.go)

// Range returns the base Addr and last Addr in the prefix.
//
// If p is zero or otherwise invalid, Range returns zero values.
func (p Prefix) Range() (base, last Addr) {
  if !p.IsValid() {
    return
  }

  effectiveBits := p.bits
  if p.ip.z == z4 { 
    effectiveBits += 96
  }

  mask128 := mask6(int(effectiveBits))
  base128 := p.ip.addr.and(mask128)
  last128 := base128.or(mask128.not())

  return Addr{addr: base128, z: p.ip.z}, Addr{addr: last128, z: p.ip.z}
}

and some tests (file netip_test.go):

func TestPrefixRange(t *testing.T) {
  tests := []struct {
    prefix Prefix
    base   Addr
    last   Addr
  }{
    {
      prefix: mustPrefix("192.168.0.255/24"),
      base:   mustIP("192.168.0.0"),
      last:   mustIP("192.168.0.255"),
    },
    {
      prefix: mustPrefix("::ffff:10.0.0.0/104"),
      base:   mustIP("::ffff:10.0.0.0"),
      last:   mustIP("::ffff:10.255.255.255"),
    },
    {
      prefix: mustPrefix("2100::/3"),
      base:   mustIP("2000::"),
      last:   mustIP("3fff:ffff:ffff:ffff:ffff:ffff:ffff:ffff"),
    },
    {
      prefix: PrefixFrom(mustIP("2000::"), 129),
      base:   netip.Addr{},
      last:   netip.Addr{},
    },
    {    
      prefix: PrefixFrom(mustIP("::ffff:10.0.0.0"), 80), 
      base:   netip.Addr{},
      last:   netip.Addr{},
    },   
    {
      prefix: PrefixFrom(mustIP("1.2.3.4"), 33),
      base:   netip.Addr{},
      last:   netip.Addr{},
    },
  }
  for _, test := range tests {
    t.Run(test.prefix.String(), func(t *testing.T) {
      base, last := test.prefix.Range()
      if base != test.base && last != test.last {
        t.Errorf("Range=(%s, %s), want (%s, %s)", base, last, test.base, test.last)
      }
    })
  }
}

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 5, 2022

please see also my bug report for ParsePrefix and 4in6 prefixes with bits < 96
net/netip: Prefix, the range of bits for 4in6 addresses must be restricted to [96,128] #53153

@gaissmai gaissmai changed the title proposal: net/netip: add netip.Prefix.Last proposal: net/netip: add netip.Prefix.Range Jun 5, 2022
@rsc
Copy link
Contributor

@rsc rsc commented Jun 15, 2022

If we leave this out of the standard library (which I'm happy to do), what is the suggestion for how people should write this code today?

@rsc
Copy link
Contributor

@rsc rsc commented Jun 15, 2022

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@rsc rsc moved this from Incoming to Active in Proposals Jun 15, 2022
@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 16, 2022

If we leave this out of the standard library (which I'm happy to do), what is the suggestion for how people should write this code today?

here is a possible implementation without netip.Prefix.Range:

Päambel to explain the code for FromPrefix()

// Block is an IP-network or IP-range, e.g.
//
//  192.168.0.1/24              // network, with CIDR mask
//  ::1/128                     // network, with CIDR mask
//  10.0.0.3-10.0.17.134        // range
//  2001:db8::1-2001:db8::f6    // range
//
// This Block representation is comparable and can be used as key in maps
// and fast sorted without conversions to/from the different IP versions.
//
// Each Block object stores two IP addresses, the base and last address of the range or network.
type Block struct {
  base netip.Addr
  last netip.Addr
}

... here we go

// FromPrefix returns a Block from the standard library's netip.Prefix type.
// It returns an error if the prefix isn't valid or when the prefix has a 4in6 address and the bits are < 96.
func FromPrefix(p netip.Prefix) (Block, error) {
  if !p.IsValid() {
    return Block{}, errors.New("invalid prefix")
  }

  maskBits := p.Bits()
  if p.Addr().Is4In6() && maskBits < 96 {
    return Block{}, errors.New("prefix with 4in6 address must have mask >= 96")
  }

  // prefix must be masked to canonical form, host bits masked off
  base := p.Masked().Addr()

  // the internal 128bit representation is privat
  // all calculations must be done in the bytes representation
  a16 := base.As16()

  if base.Is4() {
    maskBits += 96
  }

  // set host bits to 1
  for b := maskBits; b < 128; b++ {
    byteNum, bitInByte := b/8, 7-(b%8)
    a16[byteNum] |= 1 << uint(bitInByte)
  }

  // back to internal 128bit representation
  last := netip.AddrFrom16(a16)

  // unmap last to v4 if base is v4
  if base.Is4() {
    last = last.Unmap()
  }

  return Block{base, last}, nil
}

BUT, before you decide pro/contra, we should define the API of IP blocks(aka IP Range), maybe other parts would also need access to the underlying 128 bit representation, e.g. Block.IsCIDR()

It would be preferable if golang would get an IP Range library in the standard lib.

@rsc
Copy link
Contributor

@rsc rsc commented Jun 22, 2022

For now it seems like we should probably err on the side of not adding it. https://pkg.go.dev/inet.af/netaddr#IPPrefix.Range already provides this for now for people who need it.

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 22, 2022

Of course I accept your decision, it is your work and time that you would have to invest and with the overall project Go you have done wonderful over the past years with an incredible number of man-years.
Therefore, please consider my comments only as a suggestion.

netaddr.IPPrefix.Range would be an alternative if this library would be based on the now stdlib net/netip, but as you know this is practically the same but not interchangeable..
So assuming there is no IPRange in the stdlib, then it would be desirable if the net/netip stdlib would provide the necessary primitives, that others can develop a third party solution based on it. The sufficient primitives would be:

func (p Prefix) Range() (base, last Addr)
func Prefix(base, last Addr) (prefix Prefix, ok bool)
func Prefixes(base, last Addr) []Prefix

Together with the already existing methods Addr.Next() and Addr.Prev() all necessary methods for an IPRange third party library, based on the stdlib net/netip can be written. With this, tailscale could then also easily rewrite their IPRange/IPSet to the stdlib, because all further methods don't need access to the underlying uint128 representation and the encapsulation would be complete.

@rsc
Copy link
Contributor

@rsc rsc commented Jun 29, 2022

It seems like what would be needed is a constructor in netaddr to accept a netip.Prefix to make a netaddr.IPPrefix. I think @bradfitz intends to do this in a new netip-aware netaddr package (perhaps with a different import path).

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jun 29, 2022

If you prefer this path, netaddr needs at least also an constructur accepting netip.Addr for e.g. netaddr.IPRange and then you have a third party lib doubling the inherents of the stdlib netip, not my prefered solution.

@rsc rsc moved this from Active to Likely Decline in Proposals Jul 1, 2022
@rsc
Copy link
Contributor

@rsc rsc commented Jul 1, 2022

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jul 1, 2022

If desired and helpful I could also formulate a complete proposal and create a test implementation.

@rsc rsc moved this from Likely Decline to Declined in Proposals Jul 13, 2022
@rsc
Copy link
Contributor

@rsc rsc commented Jul 13, 2022

No change in consensus, so declined.
— rsc for the proposal review group

@gaissmai
Copy link
Author

@gaissmai gaissmai commented Jul 19, 2022

for the sake of completeness: after the decline I wrote an extension library for public use with a tiny API,

func Range(p netip.Prefix) (first, last netip.Addr)

func Prefix(first, last netip.Addr) (prefix netip.Prefix, ok bool)

func Prefixes(first, last netip.Addr) []netip.Prefix

func PrefixesAppend(dst []netip.Prefix, first, last netip.Addr) []netip.Prefix

if you are interested, you find it at https://github.com/gaissmai/extnetip

happy coding

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Proposals
Declined
Development

No branches or pull requests

5 participants