CPU Hog by control-node in membership manager

[Ananth Suryanarayana]

This cpu hog issue was originally reported by Vinoth Kannan Ganapathy <email address hidden> and Senthilnathan Murugappan <email address hidden>

    Do not call std::list::size() repeatedly as it may not run in O(1) time

    Until C++11, std::list::size() complexity is not necessarily O(1). It could O(N)
    as it computes size() as std::distance(begin(), end()), by traversing the entire
    list.

    In membership manager code, there are asserts() to verify equality for sets and
    maps which contain the same elements. This can churn cpu, especially when there
    is a very large number of RibStates to process.

    Fixed by maintaining a counter per std::list in membership manager code itself.

    TODO Scan entire contrail-code base for std::list::size() and apply similar fix.

    Reference: http://en.cppreference.com/w/cpp/container/list/size (See Complexity)

e.g.

Thread 9 (Thread 0x7fb2c4e6f700 (LWP 16842)):
Python Exception <class 'ValueError'> Cannot find type std::_List_const_iterator<BgpMembershipManager::RibState*>::_Node:
#0 __distance<std::_List_const_iterator<BgpMembershipManager::RibState*> > (__last=..., __first=) at /usr/include/c++/4.8/bits/stl_iterator_base_funcs.h:83
#1 distance<std::_List_const_iterator<BgpMembershipManager::RibState*> > (__last=..., __first=...) at /usr/include/c++/4.8/bits/stl_iterator_base_funcs.h:118
#2 size (this=0x310ee78) at /usr/include/c++/4.8/bits/stl_list.h:874
#3 BgpMembershipManager::Walker::WalkStart (this=this@entry=0x310ee40) at controller/src/bgp/bgp_membership.cc:1104
#4 0x000000000089f7a8 in BgpMembershipManager::Walker::WalkTrigger (this=0x310ee40) at controller/src/bgp/bgp_membership.cc:1238
#5 0x00000000006e3c27 in operator() (this=<optimized out>) at /usr/include/boost/function/function_template.hpp:767
#6 TaskTrigger::WorkerTask::Run (this=0x7faf20ef9d40) at controller/src/base/task_trigger.cc:22
#7 0x00000000006db4c7 in TaskImpl::execute (this=0x7fb2aeecd340) at controller/src/base/task.cc:264
#8 0x00007fb2cebd5b3a in ?? () from /usr/lib/libtbb.so.2
#9 0x00007fb2cebd1816 in ?? () from /usr/lib/libtbb.so.2
#10 0x00007fb2cebd0f4b in ?? () from /usr/lib/libtbb.so.2
#11 0x00007fb2cebcd0ff in ?? () from /usr/lib/libtbb.so.2
#12 0x00007fb2cebcd2f9 in ?? () from /usr/lib/libtbb.so.2
#13 0x00007fb2cedf1184 in start_thread () from /lib/x86_64-linux-gnu/libpthread.so.0
#14 0x00007fb2cdec237d in clone () from /lib/x86_64-linux-gnu/libc.so.6

[OpenContrail Admin (ci-admin-f)]

Review in progress for https://review.opencontrail.org/33958
Submitter: Ananth Suryanarayana (<email address hidden>)

[OpenContrail Admin (ci-admin-f)]

Review in progress for https://review.opencontrail.org/33959
Submitter: Ananth Suryanarayana (<email address hidden>)

[OpenContrail Admin (ci-admin-f)]

Review in progress for https://review.opencontrail.org/33960
Submitter: Ananth Suryanarayana (<email address hidden>)

[OpenContrail Admin (ci-admin-f)]

Review in progress for https://review.opencontrail.org/33961
Submitter: Ananth Suryanarayana (<email address hidden>)

[OpenContrail Admin (ci-admin-f)]

Review in progress for https://review.opencontrail.org/33962
Submitter: Ananth Suryanarayana (<email address hidden>)

[OpenContrail Admin (ci-admin-f)]

Reviewed: https://review.opencontrail.org/33961
Committed: http://github.com/Juniper/contrail-controller/commit/efef973dfb2500afdecf9bea08b5f732ca9a577e
Submitter: Zuul (<email address hidden>)
Branch: R3.1

commit efef973dfb2500afdecf9bea08b5f732ca9a577e
Author: Ananth Suryanarayana <email address hidden>
Date: Mon Jul 24 17:06:16 2017 -0700

Do not call std::list::size() repeatedly as it may not run in O(1) time

Until C++11, std::list::size() complexity is not necessarily O(1). It could O(N)
as it computes size() as std::distance(begin(), end()), by traversing the entire
list.

In membership manager code, there are asserts() to verify equality for sets and
maps which contain the same elements. This can churn cpu, especially when there
is a very large number of RibStates to process.

Fixed by maintaining a counter per std::list in membership manager code itself.

TODO Scan entire contrail-code base for std::list::size() and apply similar fix.

Reference: http://en.cppreference.com/w/cpp/container/list/size (See Complexity)

Change-Id: Ic24725298e512f089cdc5dbaf607054842ed5e23
Closes-Bug: 1706225

[OpenContrail Admin (ci-admin-f)]

Reviewed: https://review.opencontrail.org/33958
Committed: http://github.com/Juniper/contrail-controller/commit/6661b27a0b3e404d7947916b6518aad24bc93bc4
Submitter: Zuul (<email address hidden>)
Branch: R3.2

commit 6661b27a0b3e404d7947916b6518aad24bc93bc4
Author: Ananth Suryanarayana <email address hidden>
Date: Mon Jul 24 17:06:16 2017 -0700

Do not call std::list::size() repeatedly as it may not run in O(1) time

Until C++11, std::list::size() complexity is not necessarily O(1). It could O(N)
as it computes size() as std::distance(begin(), end()), by traversing the entire
list.

In membership manager code, there are asserts() to verify equality for sets and
maps which contain the same elements. This can churn cpu, especially when there
is a very large number of RibStates to process.

Fixed by maintaining a counter per std::list in membership manager code itself.

TODO Scan entire contrail-code base for std::list::size() and apply similar fix.

Reference: http://en.cppreference.com/w/cpp/container/list/size (See Complexity)

Change-Id: Ic24725298e512f089cdc5dbaf607054842ed5e23
Closes-Bug: 1706225

[OpenContrail Admin (ci-admin-f)]

Reviewed: https://review.opencontrail.org/33960
Committed: http://github.com/Juniper/contrail-controller/commit/5ecf49e2b131f008af502707edda333db9453d61
Submitter: Zuul (<email address hidden>)
Branch: master

commit 5ecf49e2b131f008af502707edda333db9453d61
Author: Ananth Suryanarayana <email address hidden>
Date: Mon Jul 24 17:06:16 2017 -0700

Do not call std::list::size() repeatedly as it may not run in O(1) time

Until C++11, std::list::size() complexity is not necessarily O(1). It could O(N)
as it computes size() as std::distance(begin(), end()), by traversing the entire
list.

In membership manager code, there are asserts() to verify equality for sets and
maps which contain the same elements. This can churn cpu, especially when there
is a very large number of RibStates to process.

Fixed by maintaining a counter per std::list in membership manager code itself.

TODO Scan entire contrail-code base for std::list::size() and apply similar fix.

Reference: http://en.cppreference.com/w/cpp/container/list/size (See Complexity)

Change-Id: Ic24725298e512f089cdc5dbaf607054842ed5e23
Closes-Bug: 1706225

[OpenContrail Admin (ci-admin-f)]

Reviewed: https://review.opencontrail.org/33959
Committed: http://github.com/Juniper/contrail-controller/commit/a3abf93444affe1cb910839e74de4ce57da0c696
Submitter: Zuul (<email address hidden>)
Branch: R4.0

commit a3abf93444affe1cb910839e74de4ce57da0c696
Author: Ananth Suryanarayana <email address hidden>
Date: Mon Jul 24 17:06:16 2017 -0700

Do not call std::list::size() repeatedly as it may not run in O(1) time

Until C++11, std::list::size() complexity is not necessarily O(1). It could O(N)
as it computes size() as std::distance(begin(), end()), by traversing the entire
list.

In membership manager code, there are asserts() to verify equality for sets and
maps which contain the same elements. This can churn cpu, especially when there
is a very large number of RibStates to process.

Fixed by maintaining a counter per std::list in membership manager code itself.

TODO Scan entire contrail-code base for std::list::size() and apply similar fix.

Reference: http://en.cppreference.com/w/cpp/container/list/size (See Complexity)

Change-Id: Ic24725298e512f089cdc5dbaf607054842ed5e23
Closes-Bug: 1706225