IPAM: handle subnets bigger than "/64" by robmry · Pull Request #49223 · moby/moby

robmry · 2025-01-07T00:13:34Z

- What I did

The default IPAM allocator is unable to represent subnets larger than 64-bits (subnets with a smaller prefix), because it uses a Bitmap that's limited to 64-bits.

When it's used to represent a 64-bit subnet, the top address can't be allocated (because bitmap.Bitmap is initialised with the number of bits it needs to represent in a uint64, so it's one short).

The rest of the daemon doesn't know about these limitations, so strange things happen when a large IPv6 subnet is used. No errors are reported, addresses/subnets are just set up incorrectly. The IPAM code calculates offsets into the bitmap itself, details it shouldn't need to understand and, because it's working on offsets into a range it doesn't always notice when it's asked to set a bit outside the range (see the notes about "offset" in #48319).

It's unusual to need a big subnet but, for example, it may be useful for modelling an ISP network, or an ISP's gateway may be in a "/56" subnet that's outside a 64-bit range used by hosts.

- How I did it

Don't increment "unselected" in Bitmap when clearing a 0
- Bug fix in the bitmap.Bitmap code
Add addrset.AddrSet to track a set of IP addresses
- A new internal package to track IP addresses.
- It owns a bitmap.Bitmap for each range of up to 63-bits that has a bit set, within the subnet it's asked to represent.
Use addrset.AddrSet instead of bitmap.Bitmap in IPAM

- How to verify it

New unit tests for AddrSet, plus existing tests (including the two "XFAIL" tests that now pass).

- Description for the changelog

- IPAM now handles subnets bigger than "/64".

corhere · 2025-01-14T17:47:46Z

+// Add adds address addr to the set. If addr is already in the set, it returns a
+// wrapped [ErrAllocated]. If addr is not in the set's address range, it returns
+// an error.
+func (as AddrSet) Add(addr netip.Addr) error {


Although technically we can get away with value receivers while mutating the map, Go consensus is to use a pointer receiver on methods which mutate the receiver for clarity of API.

Changed to pointers.

corhere · 2025-01-14T17:50:54Z

+// no addresses are available, it returns a wrapped [ErrNotAvailable].
+//
+// When serial=true, the set is scanned starting from the address following
+// the address most recently set by [AddrSet.SetAny] or [AddrSet.SetAnyInRange].


Suggested change

// the address most recently set by [AddrSet.SetAny] or [AddrSet.SetAnyInRange].

// the address most recently set by [AddrSet.AddAny] or [AddrSet.AddAnyInRange].

corhere · 2025-01-14T17:52:30Z

+	// If the pool has maxBitsPerBitmap or fewer, the key for the only bitmap is the pool's address.
+	// If there's more than one bitmap, they all have maxBitsPerBitmap. So, assume there's a free
+	// address in the bitmap keyed on the pool's address (no need to search other bitmaps, or work
+	// out if more bitmaps could be created).


Clarify that this assumption is unsound, with rationale

The "unsound" assumption would be that anything in libnetwork is capable of tracking, or needs to track, 2^63 different IP addresses (9,223,372,036,854,775,808 addresses). Let alone more than that.

But, for the overly ambitious or concerned, I've reworded and included it in the godoc comment.

corhere · 2025-01-14T18:00:10Z

+}
+
+// AddAny adds an arbitrary address to the set, and returns that address. Or, if
+// no addresses are available, it returns a wrapped [ErrNotAvailable].


Document the limitations of this function. An ErrNotAvailable returned from this function does not necessarily mean that all host IDs in the prefix have been allocated.

corhere · 2025-01-14T18:00:33Z

+// If ipr is not fully contained within the set's range, it returns an error.
+//
+// When serial=true, the set is scanned starting from the address following
+// the address most recently set by [AddrSet.SetAny] or [AddrSet.SetAnyInRange].


Suggested change

// the address most recently set by [AddrSet.SetAny] or [AddrSet.SetAnyInRange].

// the address most recently set by [AddrSet.AddAny] or [AddrSet.AddAnyInRange].

robmry · 2025-01-15T12:20:30Z

I've added an extra commit, just to clarify the code that reserves network/broadcast addresses.

thaJeztah

LGTM

akerouanton

Small nit, otherwise LGTM

akerouanton · 2025-01-20T16:17:09Z

+	// Add an address that's already present. Expect an error.
+	err = as.Add(netip.MustParseAddr("10.20.255.255"))
+	assert.Check(t, is.ErrorIs(err, ErrAllocated))
+	assert.Check(t, is.ErrorIs(err, ErrAllocated))


Suggested change

assert.Check(t, is.ErrorIs(err, ErrAllocated))

Oops, thank you - fixed.

Signed-off-by: Rob Murray <[email protected]>

The default IPAM allocator is unable to represent subnets larger than 64-bits (subnets with a smaller prefix), because it uses a Bitmap that's limited to 64-bits. When it's used to represent a 64-bit subnet, the top address can't be allocated (because bitmap.Bitmap is initialised with the number of bits it needs to represent in a uint64, so it's one short). The rest of the daemon doesn't know about these limitations, so strange things happen when a large IPv6 subnet is used. No errors are reported, addresses/subnets are just set up incorrectly. The IPAM code calculates offsets into the bitmap itself, details it shouldn't need to understand and, because it's working on offsets into a range it doesn't always notice when it's asked to set a bit outside the range. It's unusual to need a big subnet but, for example, it may be useful for modelling an ISP network, or an ISP's gateway may be in a "/56" subnet that's outside a 64-bit range used by hosts. So, use addrset.AddrSet instead of bitmap.Bitmap. Signed-off-by: Rob Murray <[email protected]>

The first address in an IPv6 range was reserved, but that wasn't clear from comments or the code. Signed-off-by: Rob Murray <[email protected]>

robmry added area/networking Networking kind/bugfix PR's that fix bugs area/networking/ipv6 Networking area/networking/ipam Networking labels Jan 7, 2025

robmry self-assigned this Jan 7, 2025

robmry force-pushed the ipam_with_more_bits branch 6 times, most recently from 93754fa to cc0af4d Compare January 9, 2025 11:28

robmry added this to the 28.0.0 milestone Jan 9, 2025

robmry marked this pull request as ready for review January 9, 2025 11:52

robmry changed the title ~~WIP - handle subnets bigger than "/64"~~ IPAM: handle subnets bigger than "/64" Jan 9, 2025

robmry requested review from akerouanton and thaJeztah January 9, 2025 12:01

robmry added impact/changelog version/23.0 version/1.10 and removed version/23.0 labels Jan 9, 2025

thaJeztah reviewed Jan 9, 2025

View reviewed changes

Comment thread libnetwork/bitmap/sequence.go Outdated

Comment thread libnetwork/bitmap/sequence_test.go

Comment thread libnetwork/ipams/defaultipam/allocator_test.go

Comment thread libnetwork/internal/addrset/addrset.go Outdated

Comment thread libnetwork/internal/addrset/addrset.go

robmry force-pushed the ipam_with_more_bits branch 2 times, most recently from 70ee756 to 8924145 Compare January 9, 2025 18:37

corhere reviewed Jan 14, 2025

View reviewed changes

robmry force-pushed the ipam_with_more_bits branch 2 times, most recently from daa5440 to 9a2d5df Compare January 15, 2025 12:19

thompson-shaun requested a review from thaJeztah January 17, 2025 17:19

thaJeztah approved these changes Jan 18, 2025

View reviewed changes

akerouanton approved these changes Jan 20, 2025

View reviewed changes

robmry added 4 commits January 20, 2025 16:48

Don't increment "unselected" in Bitmap when clearing a 0

46e290f

Signed-off-by: Rob Murray <[email protected]>

Add addrset.AddrSet to track a set of IP addresses

7e247e8

Signed-off-by: Rob Murray <[email protected]>

Clarify code/comments in defaultipam.newPoolData

366f2b5

The first address in an IPv6 range was reserved, but that wasn't clear from comments or the code. Signed-off-by: Rob Murray <[email protected]>

robmry force-pushed the ipam_with_more_bits branch from 9a2d5df to 366f2b5 Compare January 20, 2025 16:49

thaJeztah added status/4-merge and removed version/1.10 labels Jan 20, 2025

thaJeztah merged commit 29e2353 into moby:master Jan 21, 2025

robmry deleted the ipam_with_more_bits branch January 21, 2025 10:24

	// the address most recently set by [AddrSet.SetAny] or [AddrSet.SetAnyInRange].
	// the address most recently set by [AddrSet.AddAny] or [AddrSet.AddAnyInRange].

Conversation

robmry commented Jan 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

robmry commented Jan 15, 2025

Uh oh!

thaJeztah left a comment

Choose a reason for hiding this comment

Uh oh!

akerouanton left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

robmry commented Jan 7, 2025 •

edited

Loading