etf: Use cached rb_root
authorJesus Sanchez-Palencia <jesus.sanchez-palencia@intel.com>
Thu, 15 Nov 2018 01:26:33 +0000 (17:26 -0800)
committerDavid S. Miller <davem@davemloft.net>
Sat, 17 Nov 2018 04:39:34 +0000 (20:39 -0800)
commit09fd4860ea258d9666f852c213875e6bcdb1204e
tree6d76770738c3a02fbb7b9e4e1716887348abf383
parent3fcbdaee3b5c4a7f8ea4c7c11fecc009d2a1e7e4
etf: Use cached rb_root

ETF's peek() operation is heavily used so use an rb_root_cached instead
and leverage rb_first_cached() which will run in O(1) instead of
O(log n).

Even if on 'timesortedlist_clear()' we could be using rb_erase(), we
choose to use rb_erase_cached(), because if in the future we allow
runtime changes to ETF parameters, and need to do a '_clear()', this
might cause some hard to debug issues.

Signed-off-by: Jesus Sanchez-Palencia <jesus.s.palencia@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/sched/sch_etf.c