Priority Queue has an infinite Loop bug

[hafus]

Your environment.

• Version: v0.1.36
• Browser: no browser

What did you do?

The code snippet below is a test case that catches the reported bug.

t.Run("Infinite loop", func(*testing.T) {
		q := NewQueue()
		pkt := &rtp.Packet{Header: rtp.Header{SequenceNumber: 5000, Timestamp: 500}, Payload: []byte{0x02}}
		q.Push(pkt, pkt.SequenceNumber)
		q.Push(pkt, pkt.SequenceNumber)
		assert.Equal(uint16(1), q.Length())
		popped, _ := q.PopAt(uint16(5012))
		assert.Equal(popped.SequenceNumber, uint16(5000))
		assert.Equal(uint16(0), q.Length())

	})

What did you expect?

Priority queue should have a length of one after inserting a duplicate packet of the first packet in the queue or at least not enter into an infinite loop.

What happened?

The Push func runs for infinite time because the duplicated packet has head and prev pointers pointing into the head packet, resulting in a loop.

interceptor/pkg/jitterbuffer/priority_queue.go

Lines 80 to 100 in 0eab188

	head := q.next
	prev := q.next
	for head != nil {
	if priority <= head.priority {
	break
	}
	prev = head
	head = head.next
	}
	if head == nil {
	if prev != nil {
	prev.next = newPq
	}
	newPq.prev = prev
	} else {
	newPq.next = head
	newPq.prev = prev
	if prev != nil {
	prev.next = newPq
	}
	head.prev = newPq

suggestions

I suggest dropping any duplicated packet because it already exists in the queue.

[hafus]

@Sean-Der, please have a look at the issue above.

[Sean-Der]

Hey @hafus I would really appreciate your help on this.

I want to drop the Priority Queue and instead have the JitterBuffer and NACK Responder powered by the same data structure. Would you be interested in helping me with this?

[hafus]

Hello @Sean-Der

Of course, that's my pleasure. I will start working on it. If you have any suggestions or known issues about the current implementation, please share them with me.