with some nits. We should backport this.

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @stevendanna and @sumeerbhola)

pkg/util/admission/work_queue.go, line 298 at r1 (raw file):

		// where the tenantInfo struct is declared.
		tenant, ok = q.mu.tenants[tenantID]
		if (!ok || prevTenant != tenant) && !q.usesTokens {

[nit] I'd consolidate this block and the third block

  if !q.usesTokens {
    if !ok || prevTenant != tenant { panic }
    if tenant.used == 0 { panic }
    tenant.used--
  } else if !ok {
    tenant = newTenantInfo(tenantID)
    q.mu.tenants[tenantID] = tenant
}

pkg/util/admission/work_queue_test.go, line 307 at r1 (raw file):

			select {
			case <-stopCh:
				done = true

[nit] can just return

pkg/util/admission/work_queue_test.go, line 309 at r1 (raw file):

				done = true
			default:
				q.gcTenantsAndResetTokens()

This will run in a hot loop, no? IMO we should add a short time.Sleep to make sure other code has a bigger chance to get the lock

pkg/util/admission/work_queue_test.go, line 313 at r1 (raw file):

		}
	}()
	time.Sleep(time.Second * 10)

10 seconds is a lot for a random test. Does it (at least sometimes) catch the problem with shorter time (e.g. 1 second)?

pkg/util/admission/work_queue_test.go, line 316 at r1 (raw file):

	close(stopCh)
	q.close()
	fmt.Printf("total: %d, err: %d\n", totalCount, errCount)

t.Log?

Reviewed 2 of 2 files at r1, all commit messages.
Reviewable status: complete! 2 of 0 LGTMs obtained (waiting on @sumeerbhola)

a discussion (no related file):
Thanks for tracking this down. I don't have any nits not already mentioned by Radu.

pkg/util/admission/work_queue.go, line 299 at r1 (raw file):

		tenant, ok = q.mu.tenants[tenantID]
		if (!ok || prevTenant != tenant) && !q.usesTokens {
			panic("prev tenantInfo no longer in map")

note to self: This should be impossible because we incremented tenant.used under lock and tenant.used must be 0 for us to GC (and we aren't using tokens, so no periodic reset). For the same reason, tenant.used == 0 below should be impossible.

pkg/util/admission/work_queue.go, line 357 at r1 (raw file):

					panic("tenant.used is already zero")
				}
				tenant.used--

note to self: This is safe to do not under the lock since we know that len(tenant.waitingWorkHeap) > 0 and thus the tenant we are referencing here can't have been gc'd.

pkg/util/admission/work_queue.go, line 538 at r1 (raw file):

if the request was cancelled

It looks to me like we don't do used-- for the token case if the fast-path acquisition fails, even in the non-cancellation case? Or have I misread?

TFTRs!

Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @RaduBerinde, @stevendanna, and @sumeerbhola)

pkg/util/admission/work_queue.go, line 298 at r1 (raw file):

Done

pkg/util/admission/work_queue.go, line 357 at r1 (raw file):

We do reacquire the lock just above this. And yes, because used > 0, because of the earlier increment, the tenant object must be the same.

pkg/util/admission/work_queue.go, line 538 at r1 (raw file):

Good catch. I overlooked that when revising through various iterations of the code.
I've fixed it to not decrement if it is already 0. This also introduces a bit of inaccuracy, but it is more contained -- we don't want the optimistic fast path to over count.

pkg/util/admission/work_queue_test.go, line 307 at r1 (raw file):

Done

pkg/util/admission/work_queue_test.go, line 309 at r1 (raw file):

It needs to squeeze in multiple times to first reset used=0 and then do the gc -- I've added a comment. The other code does manage to run ~9000 times in 10s.

pkg/util/admission/work_queue_test.go, line 313 at r1 (raw file):

Reduced to 1s since it is sufficient.

pkg/util/admission/work_queue_test.go, line 316 at r1 (raw file):

Done