kvstore/allocator: Optimize ID allocation #5036

iffyio · 2018-07-29T02:19:15Z

This patch improves on the current brute-force mechanism by maintaining
a pool of IDs that accounts for both local ID usages and incoming
identity events, and uses this information to allocate IDs.

Add idpool.go backing ID allocation.
Add idpool_test.go to verify correctness of idpool.
Update allocator.go and cache.go to use idpool.
Update test cases that use selectAvailableID() in allocator_test.go

Fixes #4574

Happy to change anything that isn't right!

This change is

houndci-bot · 2018-07-29T02:19:22Z

pkg/kvstore/allocator/idpool.go

+	leased map[ID]bool
+}
+
+func newIdCache(minID ID, maxID ID) *idCache {


func newIdCache should be newIDCache

houndci-bot · 2018-07-29T02:19:22Z

pkg/kvstore/allocator/idpool.go

+	nextIdCache *idCache
+}
+
+func newIdPool(minID ID, maxID ID) *idPool {


func newIdPool should be newIDPool

houndci-bot · 2018-07-29T02:19:22Z

pkg/kvstore/allocator/idpool.go

+
+	// Upon a refresh of the pool, idCache will be pointed to
+	// nextCache.
+	nextIdCache *idCache


struct field nextIdCache should be nextIDCache

houndci-bot · 2018-07-29T02:19:23Z

pkg/kvstore/allocator/allocator.go

 	if id == 0 {
 		return 0, false, fmt.Errorf("no more available IDs in configured space")
 	}

 	kvstore.Trace("Selected available key", nil, logrus.Fields{fieldID: id})

+	releaseKeyAndId := func() {


var releaseKeyAndId should be releaseKeyAndID

tgraf · 2018-07-30T11:20:14Z

test-me-please

tgraf · 2018-07-30T11:22:59Z

pkg/kvstore/allocator/allocator_test.go

 		a.mainCache.cache[id] = TestType(fmt.Sprintf("key-%d", i))
 	}

 	// we should be out of IDs
-	id, val := a.selectAvailableID()
+	id, val, id2 := a.selectAvailableID()


I would call this unmaskedID instead of id2 to make it clear

rlenglet

Finished reviewing idpool.go. Will finish reviewing the rest ASAP.

rlenglet · 2018-08-03T18:14:51Z

pkg/kvstore/allocator/idpool.go

+	// index tracks the position of IDs in the above ids slice.
+	index map[ID]int
+
+	// leased is a slice of IDs that are leased in this idCache.


a slice of -> the set of

rlenglet · 2018-08-03T18:15:27Z

pkg/kvstore/allocator/idpool.go

+}
+
+func newIDCache(minID ID, maxID ID) *idCache {
+	N := int(maxID - minID + 1)


rlenglet · 2018-08-03T18:16:17Z

pkg/kvstore/allocator/idpool.go

+
+	c := &idCache{
+		ids:    make([]ID, N),
+		index:  make(map[ID]int),


Pre-allocate the maps:

index: make(map[ID]int, n), leased: make(map[ID]struct{}, n),

rlenglet · 2018-08-03T18:17:19Z

pkg/kvstore/allocator/idpool.go

+	index map[ID]int
+
+	// leased is a slice of IDs that are leased in this idCache.
+	leased map[ID]bool


You don't take advantage of the fact that your map values are always true. So you might as well have no value, to make the intent clearer:

leased map[ID]struct{}

rlenglet · 2018-08-03T18:17:54Z

pkg/kvstore/allocator/idpool.go

+	id := c.ids[random.Intn(len(c.ids))]
+	c.doRemove(id)
+	// Mark the selected ID as leased.
+	c.leased[id] = true


After changing the type of the map:

c.leased[id] = struct{}{}

rlenglet · 2018-08-03T18:27:52Z

pkg/kvstore/allocator/idpool.go

+	}
+
+	i := len(c.ids)
+	c.ids = c.ids[:i+1]


This doesn't do what you think. If the slice is already at capacity (e.g. len(c.ids) == N), this panics.
Use append instead:

c.ids = append(c.ids, id)

And add a unit test to insert an ID into a freshly created idCache with all its N ID still available. This shouldn't panic anymore.

Done :) The previous intent was to avoid allocating a new array based on the assumption that if an inserted ID falls beyond the min,max range, then the caller's code is faulty or the pool is being misused.

rlenglet

The rest of this PR looks good to me. Thanks!

rlenglet · 2018-08-03T20:37:46Z

pkg/kvstore/allocator/idpool.go

+
+	delete(c.index, id)
+
+	N := len(c.ids)


rlenglet · 2018-08-03T20:48:00Z

pkg/kvstore/allocator/idpool.go

+	return true
+}
+
+// insert makes the ID available by adding it back


Rephrase, since you have no way to tell whether the ID was ever available in the cache in the first place:
adding it back to the cache -> adding it into the cache

rlenglet · 2018-08-03T20:48:50Z

pkg/kvstore/allocator/idpool.go

+	p.idCache = p.nextIDCache
+}
+
+// SelectAvailableID returns an available ID at random from the pool.


Remove the period at the end of the line.

rlenglet · 2018-08-03T20:49:36Z

pkg/kvstore/allocator/idpool.go

+// SelectAvailableID returns an available ID at random from the pool.
+// that is leased to the caller.
+// Returns an ID of NoID if no there is no available ID in the pool.
+func (p *idPool) SelectAvailableID() ID {


I would find it less confusing if you renamed this into LeaseAvailableID, in order to be consistent with your (really good) documentation of the state machine above.

iffyio · 2018-08-04T15:08:12Z

updated! Thanks for the review :)

rlenglet · 2018-08-04T15:16:35Z

test-me-please

rlenglet · 2018-08-04T15:17:36Z

@iffyio please also rebase your branch against master.

This patch improves on the current brute-force mechanism by maintaining a pool of IDs that accounts for both local ID usages and incoming identity events, and uses this information to allocate IDs. * Add idpool.go backing ID allocation. * Add idpool_test.go to verify correctness of idpool. * Update allocator.go and cache.go to use idpool. * Update test cases that use selectAvailableID() in allocator_test.go Fixes cilium#4574 Signed-off-by: ifeanyi <ify1992@yahoo.com>

rlenglet · 2018-08-04T15:57:38Z

pkg/kvstore/allocator/cache.go

@@ -200,6 +203,7 @@ func (c *cache) start(a *Allocator) waitChan {
 						}

 						delete(c.nextCache, id)
+						a.idPool.Insert(id)


I don’t understand how that is supposed to work after the initial List is done. This is modifying the “next ID cache” so none of those updates will be visible to Lease, Use, and Release operations after the initial “refresh”.

After the initial List has completed, the Insert and remove operations must be done on the current ID cache.

Ok. I just realized that the next and current ID caches point to the same instance after refresh. That’s fine then.

wrote this before seeing your follow up ^^
After the initial list is completed, the call to 'FinishRefresh' causes the 'current ID cache' to point to the 'next ID cache' so that the Insert and Remove operations continue to be done on the 'current ID cache'. The pointers to the caches will only differ during the list operation.

rlenglet · 2018-08-04T15:57:48Z

pkg/kvstore/allocator/cache.go

@@ -180,6 +182,7 @@ func (c *cache) start(a *Allocator) waitChan {
 						if key != nil {
 							c.nextKeyCache[key.GetKey()] = id
 						}
+						a.idPool.Remove(id)


I don’t understand how that is supposed to work after the initial List is done. This is modifying the “next ID cache” so none of those updates will be visible to Lease, Use, and Release operations after the initial “refresh”.

rlenglet · 2018-08-11T15:27:22Z

test-me-please

As the previous commit mentions, this does not occur on main, v1.16, and v1.15 due to cilium#29036. However, in v1.14 and v1.13, we need to take special care because the NameManager and SelectorCache lock can be taken while the Endpoint lock is held during Endpoint deletion. Here are the relevant stacktraces regarding the deadlock: ``` 1: sync.Mutex.Lock [75 minutes] [Created by http.(*Server).Serve in goroutine 1699 @ server.go:3086] sync sema.go:77 runtime_SemacquireMutex(*uint32(0x5), false, 43690) sync mutex.go:171 (*Mutex).lockSlow(*Mutex(cilium#1733)) sync mutex.go:90 (*Mutex).Lock(...) sync rwmutex.go:147 (*RWMutex).Lock(*RWMutex(0xb0)) fqdn name_manager.go:70 (*NameManager).Lock(0xffffffffffffffff) policy selectorcache.go:964 (*SelectorCache).RemoveSelectors(cilium#1088, {cilium#28569, 0xb, 1}, {cilium#643, cilium#32582}) policy l4.go:810 (*L4Filter).removeSelectors(cilium#32582, cilium#29992) policy l4.go:817 (*L4Filter).detach(cilium#719, cilium#29993) policy l4.go:988 L4PolicyMap.Detach(...) policy l4.go:1179 (*L4Policy).Detach(cilium#20318, cilium#1383) policy resolve.go:103 (*selectorPolicy).Detach(...) policy distillery.go:81 (*PolicyCache).delete(cilium#1354, cilium#19354) policy distillery.go:138 (*PolicyCache).LocalEndpointIdentityRemoved(cilium#523, cilium#1163) identitymanager manager.go:167 (*IdentityManager).remove(cilium#706, cilium#19354) identitymanager manager.go:147 (*IdentityManager).Remove(cilium#706, cilium#19354) identitymanager manager.go:52 Remove(...) endpoint endpoint.go:1146 (*Endpoint).leaveLocked(cilium#1883, cilium#12221, {0x30, 0}) endpoint endpoint.go:2192 (*Endpoint).Delete(cilium#1883, {0x80, 0xaa}) endpointmanager manager.go:380 (*EndpointManager).removeEndpoint(cilium#1161, 0, {0xff, 0xff}) endpointmanager manager.go:394 (*EndpointManager).RemoveEndpoint(...) cmd endpoint.go:684 (*Daemon).deleteEndpointQuiet(...) cmd endpoint.go:666 (*Daemon).deleteEndpoint(cilium#1155, cilium#1883) cmd endpoint.go:713 (*Daemon).DeleteEndpoint(cilium#1155, {cilium#27399, cilium#8108}) cmd endpoint.go:770 (*deleteEndpointID).Handle(cilium#21193, {cilium#2452, {cilium#27399, 0x4d}}) endpoint delete_endpoint_id.go:66 (*DeleteEndpointID).ServeHTTP(cilium#5934, {cilium#666, cilium#2242}, cilium#2452) middleware operation.go:28 (*Context).RoutesHandler.NewOperationExecutor.func1({cilium#666, cilium#2242}, cilium#2452) http server.go:2136 HandlerFunc.ServeHTTP(ReadCloser(cilium#130), func{cilium#2242, 0x3}) middleware router.go:78 NewRouter.func1({cilium#666, cilium#2242}, cilium#2451) http server.go:2136 HandlerFunc.ServeHTTP(ReadCloser(cilium#718), func{cilium#2242, #59}) middleware redoc.go:72 Redoc.func1({cilium#666, cilium#2242}, cilium#1251) http server.go:2136 HandlerFunc.ServeHTTP(ReadCloser(cilium#4920), func{cilium#2242, #45}) middleware spec.go:46 Spec.func1({cilium#666, cilium#2242}, cilium#4921) http server.go:2136 HandlerFunc.ServeHTTP(ReadCloser(cilium#10532), func{cilium#2242, cilium#23015}) metrics middleware.go:64 (*APIEventTSHelper).ServeHTTP(cilium#1459, {cilium#668, cilium#10533}, cilium#2451) api apipanic.go:42 (*APIPanicHandler).ServeHTTP(cilium#722, {cilium#668, cilium#10533}, cilium#4922) http server.go:2938 serverHandler.ServeHTTP(*Server(cilium#8105), cilium#668, cilium#10533, 0x6) http server.go:2009 (*conn).serve(*conn(cilium#16005), Context{cilium#673, cilium#1554}) 8: sync.Mutex.Lock [74 minutes] [Created by http.(*Server).Serve in goroutine 1699 @ server.go:3086] sync sema.go:77 runtime_SemacquireMutex(*, 0x47, cilium#1154) sync mutex.go:171 (*Mutex).lockSlow(cilium#706) sync mutex.go:90 (*Mutex).Lock(...) sync rwmutex.go:147 (*RWMutex).Lock(*) identitymanager manager.go:99 (*IdentityManager).RemoveOldAddNew(cilium#706, 0, cilium#1154) identitymanager manager.go:123 RemoveOldAddNew(...) endpoint policy.go:852 (*Endpoint).SetIdentity(*, cilium#1154, 0) endpoint endpoint.go:1932 (*Endpoint).identityLabelsChanged(*, {cilium#674, *}, 1) endpoint endpoint.go:1780 (*Endpoint).runIdentityResolver(*, {cilium#674, *}, 1, 1) endpoint endpoint.go:1720 (*Endpoint).UpdateLabels(*, {cilium#674, *}, *, *, 8) cmd endpoint.go:477 (*Daemon).createEndpoint(cilium#1155, {cilium#673, *}, {cilium#683, cilium#1155}, *) cmd endpoint.go:542 (*putEndpointID).Handle(cilium#21192, {*, *, {*, 0xe}}) endpoint put_endpoint_id.go:58 (*PutEndpointID).ServeHTTP(cilium#3961, {cilium#666, *}, *) middleware operation.go:28 (*Context).RoutesHandler.NewOperationExecutor.func1({cilium#666, *}, *) http server.go:2136 HandlerFunc.ServeHTTP(*, {cilium#666, *}, *) middleware router.go:78 NewRouter.func1({cilium#666, *}, *) http server.go:2136 HandlerFunc.ServeHTTP(*, {cilium#666, *}, *) middleware redoc.go:72 Redoc.func1({cilium#666, *}, cilium#1251) http server.go:2136 HandlerFunc.ServeHTTP(*, {cilium#666, *}, #45) middleware spec.go:46 Spec.func1({cilium#666, *}, *) http server.go:2136 HandlerFunc.ServeHTTP(*, {cilium#666, *}, *) metrics middleware.go:64 (*APIEventTSHelper).ServeHTTP(cilium#1459, {cilium#668, *}, *) api apipanic.go:42 (*APIPanicHandler).ServeHTTP(#49, {cilium#668, *}, *) http server.go:2938 serverHandler.ServeHTTP({cilium#653}, {cilium#668, *}, 6) http server.go:2009 (*conn).serve(*, {cilium#673, cilium#1554}) 5: sync.Mutex.Lock [75 minutes] [Created by eventqueue.(*EventQueue).Run in goroutine 1482 @ eventqueue.go:229] sync sema.go:77 runtime_SemacquireMutex(cilium#142, 0xe8, *) sync mutex.go:171 (*Mutex).lockSlow(cilium#1733) sync mutex.go:90 (*Mutex).Lock(...) sync rwmutex.go:147 (*RWMutex).Lock(0x68) fqdn name_manager.go:70 (*NameManager).Lock(*) policy selectorcache.go:798 (*SelectorCache).AddFQDNSelector(cilium#1088, {cilium#643, *}, {{*, 0x4d}, {0, 0}}) policy l4.go:628 (*L4Filter).cacheFQDNSelector(...) policy l4.go:623 (*L4Filter).cacheFQDNSelectors(*, {*, 4, cilium#193}, cilium#536) policy l4.go:725 createL4Filter({cilium#680, *}, {*, 1, 1}, 0, {cilium#660, *}, {{*, 4}, ...}, ...) policy l4.go:879 createL4EgressFilter(...) policy rule.go:717 mergeEgressPortProto({cilium#680, *}, #44, {*, 0xa, 0}, *, {cilium#660, *}, {{*, ...}, ...}, ...) policy rule.go:672 mergeEgress.func1({cilium#660, *}) api l4.go:284 PortRules.Iterate({*, 1, cilium#546}, *) policy rule.go:624 mergeEgress({cilium#680, *}, *, {*, 1, 1}, 0, {cilium#661, *}, {cilium#662, ...}, ...) policy rule.go:753 (*rule).resolveEgressPolicy(*, {cilium#680, *}, *, *, *, {0, 0, 0}, {0, ...}) policy rules.go:103 ruleSlice.resolveL4EgressPolicy({*, *, *}, {cilium#680, *}, *) policy repository.go:718 (*Repository).resolvePolicyLocked(cilium#1089, *) policy distillery.go:119 (*PolicyCache).updateSelectorPolicy(cilium#1354, *) policy distillery.go:153 (*PolicyCache).UpdatePolicy(...) endpoint policy.go:262 (*Endpoint).regeneratePolicy(*) endpoint bpf.go:744 (*Endpoint).runPreCompilationSteps(*, *, *) endpoint bpf.go:589 (*Endpoint).regenerateBPF(*, *) endpoint policy.go:457 (*Endpoint).regenerate(*, *) endpoint events.go:53 (*EndpointRegenerationEvent).Handle(*, *) eventqueue eventqueue.go:245 (*EventQueue).run.func1() sync once.go:74 (*Once).doSlow(*, *) sync once.go:65 (*Once).Do(...) eventqueue eventqueue.go:233 (*EventQueue).run(*) 1: select [75 minutes] [Created by eventqueue.(*EventQueue).Run in goroutine 1482 @ eventqueue.go:229] semaphore semaphore.go:60 (*Weighted).Acquire(cilium#1092, {cilium#671, cilium#722}, cilium#766) lock semaphored_mutex.go:30 (*SemaphoredMutex).Lock(...) ipcache ipcache.go:140 (*IPCache).Lock(...) ipcache cidr.go:56 (*IPCache).AllocateCIDRs(cilium#1316, {0, 0, cilium#2037}, {0, 0, 0}, 0) ipcache cidr.go:103 (*IPCache).AllocateCIDRsForIPs(0, {0, cilium#697, 0}, 0xffffffffffffffff) cmd identity.go:114 cachingIdentityAllocator.AllocateCIDRsForIPs(...) policy selectorcache.go:509 (*SelectorCache).allocateIdentityMappings(cilium#1088, {{0, 0}, {cilium#5036, 0x2b}}, #45) policy selectorcache.go:843 (*SelectorCache).AddFQDNSelector(cilium#1088, {cilium#643, cilium#27811}, {{0, 0}, {cilium#5036, 0x2b}}) policy l4.go:628 (*L4Filter).cacheFQDNSelector(...) policy l4.go:623 (*L4Filter).cacheFQDNSelectors(cilium#27811, {#42936, 0x287, cilium#193}, cilium#536) policy l4.go:725 createL4Filter({cilium#680, cilium#22826}, {cilium#22828, 1, 1}, 0, {cilium#660, cilium#24510}, {{cilium#4487, 3}, ...}, ...) policy l4.go:879 createL4EgressFilter(...) policy rule.go:717 mergeEgressPortProto({cilium#680, cilium#22826}, #44, {cilium#22828, 0xa, #78536}, #79633, {cilium#660, cilium#24510}, {{cilium#4487, ...}, ...}, ...) policy rule.go:672 mergeEgress.func1({cilium#660, cilium#24510}) api l4.go:284 PortRules.Iterate({cilium#24510, 1, cilium#546}, cilium#11741) policy rule.go:624 mergeEgress({cilium#680, cilium#22826}, cilium#18687, {cilium#22828, 1, 1}, 0, {cilium#661, cilium#5624}, {cilium#662, ...}, ...) policy rule.go:753 (*rule).resolveEgressPolicy(cilium#24575, {cilium#680, cilium#22826}, cilium#18687, cilium#29345, cilium#4782, {0, 0, 0}, {0, ...}) policy rules.go:103 ruleSlice.resolveL4EgressPolicy({cilium#10690, 0xb, 5}, {cilium#680, cilium#22826}, cilium#18687) policy repository.go:718 (*Repository).resolvePolicyLocked(cilium#1089, cilium#18461) policy distillery.go:119 (*PolicyCache).updateSelectorPolicy(cilium#1354, cilium#18461) policy distillery.go:153 (*PolicyCache).UpdatePolicy(...) endpoint policy.go:262 (*Endpoint).regeneratePolicy(cilium#1748) endpoint bpf.go:744 (*Endpoint).runPreCompilationSteps(cilium#1748, cilium#27542, cilium#4781) endpoint bpf.go:589 (*Endpoint).regenerateBPF(cilium#1748, cilium#27542) endpoint policy.go:457 (*Endpoint).regenerate(cilium#1748, cilium#27542) endpoint events.go:53 (*EndpointRegenerationEvent).Handle(cilium#18609, cilium#703) eventqueue eventqueue.go:245 (*EventQueue).run.func1() sync once.go:74 (*Once).doSlow(*Once(#45414), func(cilium#69)) sync once.go:65 (*Once).Do(...) eventqueue eventqueue.go:233 (*EventQueue).run(cilium#6023) ``` Generated from pp tool: https://github.com/maruel/panicparse Signed-off-by: Chris Tarazi <chris@isovalent.com>

iffyio requested a review from a team as a code owner July 29, 2018 02:19

houndci-bot reviewed Jul 29, 2018

View reviewed changes

iffyio force-pushed the pkg/kvstore/allocator branch from 8f5ba69 to 6812015 Compare July 29, 2018 02:24

tgraf added kind/enhancement This would improve or streamline existing functionality. pending-review labels Jul 29, 2018

tgraf reviewed Jul 30, 2018

View reviewed changes

iffyio force-pushed the pkg/kvstore/allocator branch from 6812015 to e1a475a Compare July 30, 2018 14:06

rlenglet suggested changes Aug 3, 2018

View reviewed changes

iffyio force-pushed the pkg/kvstore/allocator branch 2 times, most recently from 3004464 to 6bdb0f7 Compare August 4, 2018 15:01

rlenglet suggested changes Aug 4, 2018

View reviewed changes

iffyio force-pushed the pkg/kvstore/allocator branch from 6bdb0f7 to 874bc48 Compare August 4, 2018 16:21

rlenglet approved these changes Aug 11, 2018

View reviewed changes

rlenglet merged commit 0639a42 into cilium:master Aug 11, 2018

iffyio deleted the pkg/kvstore/allocator branch September 20, 2018 07:14

kvstore/allocator: Optimize ID allocation #5036

kvstore/allocator: Optimize ID allocation #5036

Uh oh!

Conversation

iffyio commented Jul 29, 2018 • edited by tgraf Loading Uh oh! There was an error while loading. Please reload this page.

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!

tgraf commented Jul 30, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rlenglet 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!

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!

rlenglet 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

iffyio commented Aug 4, 2018

Uh oh!

rlenglet commented Aug 4, 2018

Uh oh!

rlenglet commented Aug 4, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rlenglet Aug 4, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

iffyio Aug 4, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rlenglet commented Aug 11, 2018

Uh oh!

Uh oh!

iffyio commented Jul 29, 2018 •

edited by tgraf

Loading

rlenglet Aug 4, 2018 •

edited

Loading

iffyio Aug 4, 2018 •

edited

Loading