What does prevent DOMTimerCoordinator::NextID from entering a endless loop?

Question

I had a look into the Blink codebase to answer this question about the maximum possible number of timers in JavaScript.

New timers are created by DOMTimerCoordinator::InstallNewTimeout(). It calls NextID() to retrieve an available integer key. Then, it inserts the new timer and the corresponding key into timers_.

int timeout_id = NextID();
timers_.insert(timeout_id, DOMTimer::Create(context, action, timeout,
                                            single_shot, timeout_id));

NextID() gets the next id in a circular sequence from 1 to 2³¹-1:

int DOMTimerCoordinator::NextID() {
  while (true) {
    ++circular_sequential_id_;

    if (circular_sequential_id_ <= 0)
      circular_sequential_id_ = 1;

    if (!timers_.Contains(circular_sequential_id_))
      return circular_sequential_id_;
  }
}

What happen if all the IDs are in use?
What does prevent NextID() from entering in a endless loop?

The whole process is explained with more detail in my answer to that question.

Answer 1

I needed a bit to understand this but I believe I got it.

These are the steps which turned it into sense for me.

1. circular_sequential_id_ is used as unique identifier. It's not exposed but from the other info I suspect it's an int with 32 bit (e.g. std::int32_t).

2. I suspect circular_sequential_id_ is a member variable of class (or struct) DOMTimerCoordinator. Hence, after each call of NextID() it “remembers” the last returned value. When NextID() is entered circular_sequential_id_ is incremented first:

       ++circular_sequential_id_;

3. The increment ++circular_sequential_id_; may sooner or later cause an overflow (Uuuh. If I remember right this is considered as Undefined Behavior but in real world it mostly simply wraps around.) and becomes negative. To handle this, the next line is good for:

       if (circular_sequential_id_ <= 0)
         circular_sequential_id_ = 1;

4. The last statement in loop checks whether the generated ID is still in use in any timer:

       if (!timers_.Contains(circular_sequential_id_))
         return circular_sequential_id_;

   If not used the ID is returned. Otherwise, “Play it again, Sam.”

This brings me to the most reasonable answer:

Yes, this can become an endless loop...

...if 2³¹ - 1 timers have been occupied and, hence, all IDs have been consumed.

1. I assume with 2³¹ - 1 timers you have much more essential other problems. (Alone, imaging the storage that those timers may need and the time to handle all of them...)

2. Even if 2³¹ - 1 timers are not a fatal problem, the function may cycle further until one of the timers releases it's ID and it can be occupied again. So, NextID() would be blocking if a resource (a free ID for a timer) is temporarily not available.

Thinking twice, the 2. option is rather theoretically. I cannot believe that somebody would manage limited resources this way.

I guess, this code works under assumption that there will never be 2³¹ - 1 timers concurrently and hence it will find a free ID with a few iterations.