Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Fri 10 Aug 2018 at 21:45, Cong Wang wrote: > On Fri, Aug 10, 2018 at 3:29 AM Vlad Buslov wrote: >> >> Approach you suggest is valid, but has its own trade-offs: >> >> - As you noted, lock granularity becomes coarse-grained due to per-netns >> scope. > > Sure, you acquire idrinfo->lock too, the only difference is how long > you take it. > > The bottleneck of your approach is the same, also you take idrinfo->lock > twice, so the contention is heavier. > > >> >> - I am not sure it is possible to call idr_replace() without obtaining >> idrinfo->lock in this particular case. Concurrent delete of action with >> same id is possible and, according to idr_replace() description, >> unlocked execution is not supported for such use-case: > > But we can hold its refcnt before releasing idrinfo->lock, so > idr_replace() can't race with concurrent delete. Yes, for concurrent delete case I agree. Action is removed from idr only when last reference is released and, in case of existing action update, init holds a reference. What about case when multiple task race to update the same existing action? I assume idr_replace() can be used for such case, but what would be the algorithm in case init replaced some other action, and not the action it actually copied before calling idr_replace()? > > >> >> - High rate or replace request will generate a lot of unnecessary memory >> allocations and deallocations. >> > > Yes, this is literally how RCU works, always allocate and copy, > release upon error. > > Also, if this is really a problem, we have SLAB_TYPESAFE_BY_RCU > too. ;) Current action update implementation is in-place, so there is no "copy" stage, besides members of some actions that are RCU-pointers. But I guess it makes sense if your goal is to refactor all actions to be updated with RCU.
Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Fri, Aug 10, 2018 at 3:29 AM Vlad Buslov wrote: > > Approach you suggest is valid, but has its own trade-offs: > > - As you noted, lock granularity becomes coarse-grained due to per-netns > scope. Sure, you acquire idrinfo->lock too, the only difference is how long you take it. The bottleneck of your approach is the same, also you take idrinfo->lock twice, so the contention is heavier. > > - I am not sure it is possible to call idr_replace() without obtaining > idrinfo->lock in this particular case. Concurrent delete of action with > same id is possible and, according to idr_replace() description, > unlocked execution is not supported for such use-case: But we can hold its refcnt before releasing idrinfo->lock, so idr_replace() can't race with concurrent delete. > > - High rate or replace request will generate a lot of unnecessary memory > allocations and deallocations. > Yes, this is literally how RCU works, always allocate and copy, release upon error. Also, if this is really a problem, we have SLAB_TYPESAFE_BY_RCU too. ;)
Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Thu 09 Aug 2018 at 23:43, Cong Wang wrote: > On Wed, Aug 8, 2018 at 5:06 AM Vlad Buslov wrote: >> >> >> On Wed 08 Aug 2018 at 01:20, Cong Wang wrote: >> > On Thu, Jul 5, 2018 at 7:24 AM Vlad Buslov wrote: >> >> >> >> Implement function that atomically checks if action exists and either >> >> takes >> >> reference to it, or allocates idr slot for action index to prevent >> >> concurrent allocations of actions with same index. Use EBUSY error pointer >> >> to indicate that idr slot is reserved. >> > >> > A dumb question: >> > >> > How could "concurrent allocations of actions with same index" happen >> > as you already take idrinfo->lock for the whole >> > tcf_idr_check_alloc()?? >> >> I guess my changelog is not precise enough in this description. >> Let look into sequence of events of initialization of new action: >> 1) tcf_idr_check_alloc() is called by action init. >> 2) idrinfo->lock is taken. >> 3) Lookup in idr is performed to determine if action with specified >> index already exists. >> 4) EBUSY pointer is inserted to indicate that id is taken. >> 5) idrinfo->lock is released. >> 6) tcf_idr_check_alloc() returns to action init code. >> 7) New action is allocated and initialized. >> 8) tcf_idr_insert() is called. >> 9) idrinfo->lock is taken. >> 10) EBUSY pointer is substituted with pointer to new action. >> 11) idrinfo->lock is released. >> 12) tcf_idr_insert() returns. >> >> So in this case "concurrent allocations of actions with same index" >> means not the allocation with same index during tcf_idr_check_alloc(), >> but during the period when idrinfo->lock was released(6-8). > > Yes but it is unnecessary: > > a) When adding a new action, you can actually allocate and init it before > touching idrinfo, therefore the check and insert can be done in one step > instead of breaking down it into multiple steps, which means you can > acquire idrinfo->lock once. > > b) When updating an existing action, it is slightly complicated. > However, you can still allocate a new one first, then find the old one > and copy it into the new one and finally replace it. > > In summary, we can do the following: > > 1. always allocate a new action > 2. acquire idrinfo->lock > 3a. if it is an add operation: allocate a new ID and insert the new action > 3b. if it is a replace operation: find the old one with ID, copy it into the > new one and replace it > 4. release idrinfo->lock > 5. If 3a or 3b fails, free the allocation. Otherwise succeed. > > I know, the locking scope is now per netns rather than per action, > but this can be optimized for replacing, you can hold the old action > and then release the idrinfo->lock, as idr_replace() later doesn't > require idrinfo->lock AFAIK. > > Is there anything I miss here? Approach you suggest is valid, but has its own trade-offs: - As you noted, lock granularity becomes coarse-grained due to per-netns scope. - I am not sure it is possible to call idr_replace() without obtaining idrinfo->lock in this particular case. Concurrent delete of action with same id is possible and, according to idr_replace() description, unlocked execution is not supported for such use-case: /** * idr_replace() - replace pointer for given ID. * @idr: IDR handle. * @ptr: New pointer to associate with the ID. * @id: ID to change. * * Replace the pointer registered with an ID and return the old value. * This function can be called under the RCU read lock concurrently with * idr_alloc() and idr_remove() (as long as the ID being removed is not * the one being replaced!). * * Returns: the old value on success. %-ENOENT indicates that @id was not * found. %-EINVAL indicates that @ptr was not valid. */ - High rate or replace request will generate a lot of unnecessary memory allocations and deallocations. > > >> >> > >> > For me, it should be only one allocation could succeed, all others >> > should fail. >> >> Correct! And this change is made specifically to enforce that rule. >> >> Otherwise, multiple processes could try to create new action with same >> id at the same time, and all processes that executed 3, before any >> process reached 10, will "succeed" by overwriting each others action in >> idr. (and leak memory while doing so) > > I know but again it doesn't look necessary to achieve a same goal. > > >> >> > >> > Maybe you are trying to prevent others treat it like existing one, >> > but in that case you can just hold the idinfo->lock for all idr operations. >> > >> > And more importantly, upper layer is able to tell it is a creation or >> > just replace, you don't have to check this in this complicated way. >> > >> > IOW, all of these complicated code should not exist. >> >> Original code was simpler and didn't involve temporary EBUSY pointer. >> This change was made according to Jiri's request. He wanted to have >> unified API to be used by all actions and suggested this approach >> specifically. > > I will work on this, as this is aligned to my work to make > it
Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Wed, Aug 8, 2018 at 5:06 AM Vlad Buslov wrote: > > > On Wed 08 Aug 2018 at 01:20, Cong Wang wrote: > > On Thu, Jul 5, 2018 at 7:24 AM Vlad Buslov wrote: > >> > >> Implement function that atomically checks if action exists and either takes > >> reference to it, or allocates idr slot for action index to prevent > >> concurrent allocations of actions with same index. Use EBUSY error pointer > >> to indicate that idr slot is reserved. > > > > A dumb question: > > > > How could "concurrent allocations of actions with same index" happen > > as you already take idrinfo->lock for the whole > > tcf_idr_check_alloc()?? > > I guess my changelog is not precise enough in this description. > Let look into sequence of events of initialization of new action: > 1) tcf_idr_check_alloc() is called by action init. > 2) idrinfo->lock is taken. > 3) Lookup in idr is performed to determine if action with specified > index already exists. > 4) EBUSY pointer is inserted to indicate that id is taken. > 5) idrinfo->lock is released. > 6) tcf_idr_check_alloc() returns to action init code. > 7) New action is allocated and initialized. > 8) tcf_idr_insert() is called. > 9) idrinfo->lock is taken. > 10) EBUSY pointer is substituted with pointer to new action. > 11) idrinfo->lock is released. > 12) tcf_idr_insert() returns. > > So in this case "concurrent allocations of actions with same index" > means not the allocation with same index during tcf_idr_check_alloc(), > but during the period when idrinfo->lock was released(6-8). Yes but it is unnecessary: a) When adding a new action, you can actually allocate and init it before touching idrinfo, therefore the check and insert can be done in one step instead of breaking down it into multiple steps, which means you can acquire idrinfo->lock once. b) When updating an existing action, it is slightly complicated. However, you can still allocate a new one first, then find the old one and copy it into the new one and finally replace it. In summary, we can do the following: 1. always allocate a new action 2. acquire idrinfo->lock 3a. if it is an add operation: allocate a new ID and insert the new action 3b. if it is a replace operation: find the old one with ID, copy it into the new one and replace it 4. release idrinfo->lock 5. If 3a or 3b fails, free the allocation. Otherwise succeed. I know, the locking scope is now per netns rather than per action, but this can be optimized for replacing, you can hold the old action and then release the idrinfo->lock, as idr_replace() later doesn't require idrinfo->lock AFAIK. Is there anything I miss here? > > > > > For me, it should be only one allocation could succeed, all others > > should fail. > > Correct! And this change is made specifically to enforce that rule. > > Otherwise, multiple processes could try to create new action with same > id at the same time, and all processes that executed 3, before any > process reached 10, will "succeed" by overwriting each others action in > idr. (and leak memory while doing so) I know but again it doesn't look necessary to achieve a same goal. > > > > > Maybe you are trying to prevent others treat it like existing one, > > but in that case you can just hold the idinfo->lock for all idr operations. > > > > And more importantly, upper layer is able to tell it is a creation or > > just replace, you don't have to check this in this complicated way. > > > > IOW, all of these complicated code should not exist. > > Original code was simpler and didn't involve temporary EBUSY pointer. > This change was made according to Jiri's request. He wanted to have > unified API to be used by all actions and suggested this approach > specifically. I will work on this, as this is aligned to my work to make it RCU-complete.
Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Wed 08 Aug 2018 at 01:20, Cong Wang wrote: > On Thu, Jul 5, 2018 at 7:24 AM Vlad Buslov wrote: >> >> Implement function that atomically checks if action exists and either takes >> reference to it, or allocates idr slot for action index to prevent >> concurrent allocations of actions with same index. Use EBUSY error pointer >> to indicate that idr slot is reserved. > > A dumb question: > > How could "concurrent allocations of actions with same index" happen > as you already take idrinfo->lock for the whole > tcf_idr_check_alloc()?? I guess my changelog is not precise enough in this description. Let look into sequence of events of initialization of new action: 1) tcf_idr_check_alloc() is called by action init. 2) idrinfo->lock is taken. 3) Lookup in idr is performed to determine if action with specified index already exists. 4) EBUSY pointer is inserted to indicate that id is taken. 5) idrinfo->lock is released. 6) tcf_idr_check_alloc() returns to action init code. 7) New action is allocated and initialized. 8) tcf_idr_insert() is called. 9) idrinfo->lock is taken. 10) EBUSY pointer is substituted with pointer to new action. 11) idrinfo->lock is released. 12) tcf_idr_insert() returns. So in this case "concurrent allocations of actions with same index" means not the allocation with same index during tcf_idr_check_alloc(), but during the period when idrinfo->lock was released(6-8). > > For me, it should be only one allocation could succeed, all others > should fail. Correct! And this change is made specifically to enforce that rule. Otherwise, multiple processes could try to create new action with same id at the same time, and all processes that executed 3, before any process reached 10, will "succeed" by overwriting each others action in idr. (and leak memory while doing so) > > Maybe you are trying to prevent others treat it like existing one, > but in that case you can just hold the idinfo->lock for all idr operations. > > And more importantly, upper layer is able to tell it is a creation or > just replace, you don't have to check this in this complicated way. > > IOW, all of these complicated code should not exist. Original code was simpler and didn't involve temporary EBUSY pointer. This change was made according to Jiri's request. He wanted to have unified API to be used by all actions and suggested this approach specifically.
Re: [PATCH net-next v6 10/11] net: sched: atomically check-allocate action
On Thu, Jul 5, 2018 at 7:24 AM Vlad Buslov wrote: > > Implement function that atomically checks if action exists and either takes > reference to it, or allocates idr slot for action index to prevent > concurrent allocations of actions with same index. Use EBUSY error pointer > to indicate that idr slot is reserved. A dumb question: How could "concurrent allocations of actions with same index" happen as you already take idrinfo->lock for the whole tcf_idr_check_alloc()?? For me, it should be only one allocation could succeed, all others should fail. Maybe you are trying to prevent others treat it like existing one, but in that case you can just hold the idinfo->lock for all idr operations. And more importantly, upper layer is able to tell it is a creation or just replace, you don't have to check this in this complicated way. IOW, all of these complicated code should not exist.
[PATCH net-next v6 10/11] net: sched: atomically check-allocate action
Implement function that atomically checks if action exists and either takes
reference to it, or allocates idr slot for action index to prevent
concurrent allocations of actions with same index. Use EBUSY error pointer
to indicate that idr slot is reserved.
Implement cleanup helper function that removes temporary error pointer from
idr. (in case of error between idr allocation and insertion of newly
created action to specified index)
Refactor all action init functions to insert new action to idr using this
API.
Reviewed-by: Marcelo Ricardo Leitner
Signed-off-by: Vlad Buslov
Signed-off-by: Jiri Pirko
---
Changes from V1 to V2:
- Remove unique idr insertion function. Change original idr insert to do
the same thing.
- Refactor action check-alloc code into standalone function.
include/net/act_api.h | 3 ++
net/sched/act_api.c| 92 --
net/sched/act_bpf.c| 11 --
net/sched/act_connmark.c | 10 +++--
net/sched/act_csum.c | 11 --
net/sched/act_gact.c | 11 --
net/sched/act_ife.c| 6 ++-
net/sched/act_ipt.c| 13 ++-
net/sched/act_mirred.c | 16 ++--
net/sched/act_nat.c| 11 --
net/sched/act_pedit.c | 12 --
net/sched/act_police.c | 9 -
net/sched/act_sample.c | 11 --
net/sched/act_simple.c | 11 +-
net/sched/act_skbedit.c| 11 +-
net/sched/act_skbmod.c | 11 +-
net/sched/act_tunnel_key.c | 9 -
net/sched/act_vlan.c | 17 -
18 files changed, 216 insertions(+), 59 deletions(-)
diff --git a/include/net/act_api.h b/include/net/act_api.h
index b9ed2b8256a5..8090de2edab7 100644
--- a/include/net/act_api.h
+++ b/include/net/act_api.h
@@ -154,6 +154,9 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index,
struct nlattr *est,
int bind, bool cpustats);
void tcf_idr_insert(struct tc_action_net *tn, struct tc_action *a);
+void tcf_idr_cleanup(struct tc_action_net *tn, u32 index);
+int tcf_idr_check_alloc(struct tc_action_net *tn, u32 *index,
+ struct tc_action **a, int bind);
int tcf_idr_delete_index(struct tc_action_net *tn, u32 index);
int __tcf_idr_release(struct tc_action *a, bool bind, bool strict);
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index eefe8c2fe667..9511502e1cbb 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -303,7 +303,9 @@ static bool __tcf_idr_check(struct tc_action_net *tn, u32
index,
spin_lock(>lock);
p = idr_find(>action_idr, index);
- if (p) {
+ if (IS_ERR(p)) {
+ p = NULL;
+ } else if (p) {
refcount_inc(>tcfa_refcnt);
if (bind)
atomic_inc(>tcfa_bindcnt);
@@ -371,7 +373,6 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index,
struct nlattr *est,
{
struct tc_action *p = kzalloc(ops->size, GFP_KERNEL);
struct tcf_idrinfo *idrinfo = tn->idrinfo;
- struct idr *idr = >action_idr;
int err = -ENOMEM;
if (unlikely(!p))
@@ -389,20 +390,6 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index,
struct nlattr *est,
goto err2;
}
spin_lock_init(>tcfa_lock);
- idr_preload(GFP_KERNEL);
- spin_lock(>lock);
- /* user doesn't specify an index */
- if (!index) {
- index = 1;
- err = idr_alloc_u32(idr, NULL, , UINT_MAX, GFP_ATOMIC);
- } else {
- err = idr_alloc_u32(idr, NULL, , index, GFP_ATOMIC);
- }
- spin_unlock(>lock);
- idr_preload_end();
- if (err)
- goto err3;
-
p->tcfa_index = index;
p->tcfa_tm.install = jiffies;
p->tcfa_tm.lastuse = jiffies;
@@ -412,7 +399,7 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index,
struct nlattr *est,
>tcfa_rate_est,
>tcfa_lock, NULL, est);
if (err)
- goto err4;
+ goto err3;
}
p->idrinfo = idrinfo;
@@ -420,8 +407,6 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index,
struct nlattr *est,
INIT_LIST_HEAD(>list);
*a = p;
return 0;
-err4:
- idr_remove(idr, index);
err3:
free_percpu(p->cpu_qstats);
err2:
@@ -437,11 +422,78 @@ void tcf_idr_insert(struct tc_action_net *tn, struct
tc_action *a)
struct tcf_idrinfo *idrinfo = tn->idrinfo;
spin_lock(>lock);
- idr_replace(>action_idr, a, a->tcfa_index);
+ /* Replace ERR_PTR(-EBUSY) allocated by tcf_idr_check_alloc */
+ WARN_ON(!IS_ERR(idr_replace(>action_idr, a, a->tcfa_index)));
spin_unlock(>lock);
}
EXPORT_SYMBOL(tcf_idr_insert);
+/* Cleanup idr index that was allocated but not initialized. */
+
+void tcf_idr_cleanup(struct tc_action_net *tn, u32 index)
+{
+ struct
