Bug 1503

Summary:	BlockAckManager infinite loop
Product:	ns-3	Reporter:	gbadawy
Component:	wifi	Assignee:	Nicola Baldo <nicola>
Status:	RESOLVED FIXED
Severity:	normal	CC:	mk.banchi, ns-bugs, ruben
Priority:	P5
Version:	ns-3.15
Hardware:	All
OS:	All
Attachments:	A patch to solve the issue diff file Diff file with the requested updates Fix invalid iterator dereference

Description gbadawy 2012-09-07 08:55:48 UTC

Line 597 in CleanupBuffers in block-ack-manager.cc leads to an infinite loop. The reason behind that is when line 597 is executed the iterator "it" points to the data that was after the deleted data (i.e. as if the iterator has proceeded) then it is incremented inside the for loop without checking the current content of "it" so if the deleted data was the end of the list the condition in the for loop will never be met and the for loop will run indefinitely.

Comment 1 gbadawy 2012-09-07 08:59:55 UTC

Created attachment 1447 [details]
A patch to solve the issue

The attached patch solves this issue but modifying the for loop in CleanupBuffers to

for (list<PacketQueueI>::iterator it = m_retryPackets.begin (); it != m_retryPackets.end ();)
                {
                  if ((*it)->hdr.GetAddr1 () == j->second.first.GetPeer ()
                      && (*it)->hdr.GetQosTid () == j->second.first.GetTid ()
                      && (*it)->hdr.GetSequenceNumber () == i->hdr.GetSequenceNumber ())
                    {
                      m_retryPackets.erase (it);
                    }
                  else
                    it++;
                }

This way all the contents in the list are checked correctly by the condition in the for loop

Comment 2 Nicola Baldo 2012-09-10 11:54:34 UTC

Hi Ghada,

thank you for your effort in reporting this bug and posting a fix. In order to make the work of reviewers easier, could you please post a patch generated with "hg diff" or with plain diff (instead of the whole .cc file)?

Comment 3 Nicola Baldo 2012-09-10 11:55:33 UTC

Additionally, can you please let us know exactly with which version/changeset of ns-3 you are working?

Comment 4 gbadawy 2012-09-10 15:02:08 UTC

Created attachment 1448 [details]
diff file

Hi,
Here is the requested diff file

Comment 5 gbadawy 2012-09-10 15:02:59 UTC

I am working with ns-3.13

Comment 6 Nicola Baldo 2012-09-12 07:19:39 UTC

Hi Ghada,

thanks for the diff file. I agree with the interpretation of the bug and in general with the proposed solution, I just have a couple of comments about the implementation:

1) according to the docs of std::list::erase, an iterator pointing to an element which is deleted gets invalidated:
http://www.cplusplus.com/reference/stl/list/erase/
so I think we should use the return value of erase () to get an iterator to the next element after the deleted one, i.e., 

it = m_retryPackets.erase (it);

2) you need to use brackets {} for the body of "else", in order to comply with the ns-3 coding style

once these two issues are addressed, the patch would be ok for me. Did you already ask Tom for permission to push changes on ns-3-dev?

Comment 7 gbadawy 2012-09-12 09:06:50 UTC

Created attachment 1450 [details]
Diff file with the requested updates

Hi Nicola,
Thanks for your comments. Please find attached a new diff file with the requested updates. I just sent an email to Tom to ask for permission to push changes on ns-3-dev.

Comment 8 Mirko Banchi 2013-02-10 13:49:29 UTC

Hi Ghada and Nicola,

the problem is not the infinite loop (it can't happen) because std::list are implemented as doubly linked circular lists so the problem would be only some useless iterations. Here, the real problem is about the way is used std::list::erase. In fact, after that erase is called on an iterator, it becomes invalid so calling operator++ on it could arise in a segfault. I attached the patch (bug1503.patch) that should fix the problem. After review, i think Ghada could apply it and push all on ns-3-dev.

Comment 9 Mirko Banchi 2013-02-10 13:50:53 UTC

Created attachment 1510 [details]
Fix invalid iterator dereference

Comment 10 Mirko Banchi 2013-03-15 16:28:26 UTC

Fixed in ns-3-dev changeset: be33f29782ab