Re: [PATCH v3 00/11] Modify action API for implementing lockless actions
On Tue 29 May 2018 at 04:26, Cong Wang wrote: >> Currently, all netlink protocol handlers for updating rules, actions and >> qdiscs are protected with single global rtnl lock which removes any >> possibility for parallelism. This patch set is a first step to remove >> rtnl lock dependency from TC rules update path. >> >> Recently, new rtnl registration flag RTNL_FLAG_DOIT_UNLOCKED was added. >> Handlers registered with this flag are called without RTNL taken. End >> goal is to have rule update handlers(RTM_NEWTFILTER, RTM_DELTFILTER, >> etc.) to be registered with UNLOCKED flag to allow parallel execution. >> However, there is no intention to completely remove or split rtnl lock >> itself. This patch set addresses specific problems in action API that >> prevents it from being executed concurrently. > > > Great, your goal is much clear now! So can I expect this patchset is to > _completely_ get rid of RTNL lock from action update paths, correct? No, this patch set is preparation only and deals with specific issues in act API. I guess I should specify it in cover letter. There is one more patch set that changes individual actions and... > > I ask because this is your first step, RTNL is still acquired on upper layer, > that is, filter update paths. ... several more patch sets that update cls API, including filter update path. > > >> >> As a preparation for executing TC rules update handlers without rtnl >> lock, action API code was audited to determine areas that assume >> external synchronization with rtnl lock and must be changed to allow >> safe concurrent access with following results: >> >> 1. Action idr is already protected with spinlock. However, some code >>paths assume that idr state is not changes between several >>consecutive tcf_idr_* function calls. >> 2. tc_action reference and bind counters are implemented as plain >>integers. They purpose was to allow single actions to be shared >>between multiple filters, not to provide means for concurrent >>modification. >> 3. tc_action 'cookie' pointer field is not protected against >>modification. >> 4. Action API functions, that work with set of actions, use intrusive >>linked list, which cannot be used concurrently without additional >>synchronization. >> 5. Action API functions don't take reference to actions while using >>them, assuming external synchronization with rtnl lock. > > > Fair enough, thanks for the details, but some high-level things are still > missing: > > 1. What lock protects action updates with your patches? Since you remove > RTNL from these paths, I assume no lock at all except the existing spinlock? > Please state here in your cover letter. Next patch set updates every action implementation. However, it is safe to apply this patchset without next one because I didn't re-register any handlers with UNLOCKED flag yet, so all rules/actions update paths are still synchronized with RTNL. > > > 2. Assume 1) is correct, how do you guarantee an action update is atomic? > Let's say I have action foo: > > struct act_foo > { > int a; > int b; > }; > > With RTNL: > > rtnl_lock(); > act_foo->a = a; > if (a == X) > act_foo->b = b; > rtnl_unlock(); > > Without any lock (as I assumed): > > > act_foo->a = a; > // fast path now reads new ->a but old ->b > if (act_foo->a == X) > // Other slow path may be changing ->a too > act_foo->b = b; > > If my assumption is correct, please explain the above question in your > cover letter, it is very important for understanding your 11 patches. > > If my assumption is wrong, please be specific on which lock protects > which paths here. Your observation, that this patch is not enough and individual actions must be updates in order to be executed concurrently, is correct. This issue is dealt with in next patch set. For most of actions that require additional synchronization, I used tcf_spinlock or rcu + atomic exchange. > > > 3. How are actions like act_mirred and act_ipt updated w/o RTNL? > > act_mirred requires to hold a refcnt for target device: > > if (dev != NULL) { > if (ret != ACT_P_CREATED) > dev_put(rcu_dereference_protected(m->tcfm_dev, 1)); > dev_hold(dev); > rcu_assign_pointer(m->tcfm_dev, dev); > m->tcfm_mac_header_xmit = mac_header_xmit; > } > > Without RTNL, how is dev_put()+dev_hold() be atomic in !CREATED case? Again, next set. > > act_ipt calls xt_request_find_target() and xt_check_target(), I guess both > assumes RTNL? Do they? Internally, target list is protected with mutex. Anyway, third patch in this series adds 'rtnl_held' argument to action init function, that allows actions to take(or release) rtnl lock when necessary. It is intended to be used specifically in this kind of situations when some external API requires caller to have rtnl lock. I guess I should also add this info to cover letter. I have omitted it because that argument
Re: [PATCH v3 00/11] Modify action API for implementing lockless actions
On Sun, May 27, 2018 at 2:17 PM, Vlad Buslov wrote: > Currently, all netlink protocol handlers for updating rules, actions and > qdiscs are protected with single global rtnl lock which removes any > possibility for parallelism. This patch set is a first step to remove > rtnl lock dependency from TC rules update path. > > Recently, new rtnl registration flag RTNL_FLAG_DOIT_UNLOCKED was added. > Handlers registered with this flag are called without RTNL taken. End > goal is to have rule update handlers(RTM_NEWTFILTER, RTM_DELTFILTER, > etc.) to be registered with UNLOCKED flag to allow parallel execution. > However, there is no intention to completely remove or split rtnl lock > itself. This patch set addresses specific problems in action API that > prevents it from being executed concurrently. Great, your goal is much clear now! So can I expect this patchset is to _completely_ get rid of RTNL lock from action update paths, correct? I ask because this is your first step, RTNL is still acquired on upper layer, that is, filter update paths. > > As a preparation for executing TC rules update handlers without rtnl > lock, action API code was audited to determine areas that assume > external synchronization with rtnl lock and must be changed to allow > safe concurrent access with following results: > > 1. Action idr is already protected with spinlock. However, some code >paths assume that idr state is not changes between several >consecutive tcf_idr_* function calls. > 2. tc_action reference and bind counters are implemented as plain >integers. They purpose was to allow single actions to be shared >between multiple filters, not to provide means for concurrent >modification. > 3. tc_action 'cookie' pointer field is not protected against >modification. > 4. Action API functions, that work with set of actions, use intrusive >linked list, which cannot be used concurrently without additional >synchronization. > 5. Action API functions don't take reference to actions while using >them, assuming external synchronization with rtnl lock. Fair enough, thanks for the details, but some high-level things are still missing: 1. What lock protects action updates with your patches? Since you remove RTNL from these paths, I assume no lock at all except the existing spinlock? Please state here in your cover letter. 2. Assume 1) is correct, how do you guarantee an action update is atomic? Let's say I have action foo: struct act_foo { int a; int b; }; With RTNL: rtnl_lock(); act_foo->a = a; if (a == X) act_foo->b = b; rtnl_unlock(); Without any lock (as I assumed): act_foo->a = a; // fast path now reads new ->a but old ->b if (act_foo->a == X) // Other slow path may be changing ->a too act_foo->b = b; If my assumption is correct, please explain the above question in your cover letter, it is very important for understanding your 11 patches. If my assumption is wrong, please be specific on which lock protects which paths here. 3. How are actions like act_mirred and act_ipt updated w/o RTNL? act_mirred requires to hold a refcnt for target device: if (dev != NULL) { if (ret != ACT_P_CREATED) dev_put(rcu_dereference_protected(m->tcfm_dev, 1)); dev_hold(dev); rcu_assign_pointer(m->tcfm_dev, dev); m->tcfm_mac_header_xmit = mac_header_xmit; } Without RTNL, how is dev_put()+dev_hold() be atomic in !CREATED case? act_ipt calls xt_request_find_target() and xt_check_target(), I guess both assumes RTNL? Or you just leave these exceptions as they are but make the rest actions lockless? If so, please list all of them here and describe why are they special. Last, since your end goal is to remove RTNL from filter update paths, how does it work if a tc filter block shared among different qdiscs? Assume a tc filter block can be shared by different qdiscs on different devs. Thanks!
[PATCH v3 00/11] Modify action API for implementing lockless actions
Currently, all netlink protocol handlers for updating rules, actions and qdiscs are protected with single global rtnl lock which removes any possibility for parallelism. This patch set is a first step to remove rtnl lock dependency from TC rules update path. Recently, new rtnl registration flag RTNL_FLAG_DOIT_UNLOCKED was added. Handlers registered with this flag are called without RTNL taken. End goal is to have rule update handlers(RTM_NEWTFILTER, RTM_DELTFILTER, etc.) to be registered with UNLOCKED flag to allow parallel execution. However, there is no intention to completely remove or split rtnl lock itself. This patch set addresses specific problems in action API that prevents it from being executed concurrently. As a preparation for executing TC rules update handlers without rtnl lock, action API code was audited to determine areas that assume external synchronization with rtnl lock and must be changed to allow safe concurrent access with following results: 1. Action idr is already protected with spinlock. However, some code paths assume that idr state is not changes between several consecutive tcf_idr_* function calls. 2. tc_action reference and bind counters are implemented as plain integers. They purpose was to allow single actions to be shared between multiple filters, not to provide means for concurrent modification. 3. tc_action 'cookie' pointer field is not protected against modification. 4. Action API functions, that work with set of actions, use intrusive linked list, which cannot be used concurrently without additional synchronization. 5. Action API functions don't take reference to actions while using them, assuming external synchronization with rtnl lock. Following solutions to these problems are implemented: 1. To remove assumption that idr state doesn't change between tcf_idr_* calls, implement new functions that atomically perform several operations on idr without releasing idr spinlock. (function to atomically lookup and delete action by index, function to atomically check if action exists and allocate new one if necessary, etc.) 2. Use atomic operations on counters to make them suitable for concurrent get/put operations. 3. Data that 'cookie' points to is never modified, so it enough to refactor it to rcu pointer to prevent concurrent de-allocation. 4. Action API doesn't actually use any linked list specific operations on actions intrusive linked list, so it can be refactored to array in straightforward manner. 5. Always take reference to action while accessing it in action API. tcf_idr_search function modified to take reference to action before returning it, so there is no way to lookup an action without incrementing its reference counter. All users of this function are modified to release the reference, after they done using action. With all users using reference counting, it is now safe to concurrently delete actions. Since only shared state in action API module are actions themselves and action idr, these changes are sufficient to not to rely on global rtnl lock for protection of internal action API data structures. Changes from V1 to V2: - Removed redundant actions ops lookup during delete. - Merge action ops delete definition and implementation. - Assume all actions have delete implemented and don't check for it explicitly. - Resplit action lookup/release code to prevent memory leaks in individual patches. - Make __tcf_idr_check function static - Remove unique idr insertion function. Change original idr insert to do the same thing. - Merge changes that take reference to action when performing lookup and changes that account for this additional reference when dumping action to user space into single patch. - Change convoluted commit message. - Rename "unlocked" to "rtnl_held" for clarity. - Remove estimator lock add patch. - Refactor action check-alloc code into standalone function. - Rename tcf_idr_find_delete to tcf_idr_delete_index. - Rearrange variable definitions in tc_action_delete. - Add patch that refactors action API code to use array of pointers to actions instead of intrusive linked list. - Expand cover letter. Vlad Buslov (11): net: sched: use rcu for action cookie update net: sched: change type of reference and bind counters net: sched: implement unlocked action init API net: sched: always take reference to action net: sched: implement action API that deletes action by index net: sched: add 'delete' function to action ops net: sched: implement reference counted action release net: sched: don't release reference on action overwrite net: sched: use reference counting action init net: sched: atomically check-allocate action net: sched: change action API to use array of pointers to actions include/net/act_api.h | 25 ++- include/net/pkt_cls.h | 1 + net/sched/act_api.c| 408 +++--