ipset: Proposed improvements to the kernel code

ipset: Proposed improvements to the kernel code

[Sergey Popovich]

Hello community.

I have a lot of changes to the kernel code of ipset subsystem for current
nf-next (and upstream kernel therefore) split into the following major
categories in order I wish to supply them to the upstream.

  * Bugfixes
      There is not too much, but exists in upstream, few of which is stability
      critical.

  * Code cleanups
      Changes to make code more readable, and other things.

  * Improvements to the ipset core set/type/variant 
    registration/deregistration and other parts of the core.
     
  * Improvements for bitmap:* set types where two variants implemented:
    one for set without extensions and another for set with extensions.

  * Improvements for hash:*, where hash buckets still stores array
    of set elements, but all element iterations is done via bitmap using
    ffs()/ffz(). There is no error prone memcpy() of elements within bucket.

  * Improvements for list:set, where main change is to move to the
    standard linux linked lists implementation.

  * Improve counters extension implementation to move from
    atomic64_t variables used to store statistics to per-CPU variables.

All of these changes are made with primary goal in mind: prepare
code for conversion from read/write locking to the RCU.

Currently my patch series consists of nearly 170 patches. I wish to
supply each of them divided into categories I described above.

I choose to send patches against current nf-next instead of
ipset upstream as last one seems already constains some attempts
to implement RCU in the ipset. On this mailing list I found discussion
about some weakness in proposed RCU implementation.

I think my implementation after all code prepare is ready for review.

All commits contains meaningful descriptions (I hope) and code
is well commented where it is really necessary.

Main development is done for 3.2.x series of kernel, and adopted
to the current upstream (actually cosmetics changes to apply patches).

As userspace ipset 6.23 utility is used and all changes does not
include any kernel<->user space API/ABI breaks.

Tests are performed on both 32/64 bit arches with kernel compiled
for debugging running ipset regression test suite. Only i386/x86_64 
architectures are used for tests.

Thanks for your patience for reading this, please take time to review
and possibly accept my work.

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

Hi Sergey,

On Mon, 16 Mar 2015, Sergey Popovich wrote:

> I have a lot of changes to the kernel code of ipset subsystem for current
> nf-next (and upstream kernel therefore) split into the following major
> categories in order I wish to supply them to the upstream.
> 
>   * Bugfixes
>       There is not too much, but exists in upstream, few of which is stability
>       critical.
> 
>   * Code cleanups
>       Changes to make code more readable, and other things.
> 
>   * Improvements to the ipset core set/type/variant 
>     registration/deregistration and other parts of the core.
>      
>   * Improvements for bitmap:* set types where two variants implemented:
>     one for set without extensions and another for set with extensions.
> 
>   * Improvements for hash:*, where hash buckets still stores array
>     of set elements, but all element iterations is done via bitmap using
>     ffs()/ffz(). There is no error prone memcpy() of elements within bucket.
> 
>   * Improvements for list:set, where main change is to move to the
>     standard linux linked lists implementation.
> 
>   * Improve counters extension implementation to move from
>     atomic64_t variables used to store statistics to per-CPU variables.
> 
> All of these changes are made with primary goal in mind: prepare
> code for conversion from read/write locking to the RCU.
> 
> Currently my patch series consists of nearly 170 patches. I wish to
> supply each of them divided into categories I described above.
> 
> I choose to send patches against current nf-next instead of
> ipset upstream as last one seems already constains some attempts
> to implement RCU in the ipset. On this mailing list I found discussion
> about some weakness in proposed RCU implementation.
> 
> I think my implementation after all code prepare is ready for review.
> 
> All commits contains meaningful descriptions (I hope) and code
> is well commented where it is really necessary.
> 
> Main development is done for 3.2.x series of kernel, and adopted
> to the current upstream (actually cosmetics changes to apply patches).
> 
> As userspace ipset 6.23 utility is used and all changes does not
> include any kernel<->user space API/ABI breaks.
> 
> Tests are performed on both 32/64 bit arches with kernel compiled
> for debugging running ipset regression test suite. Only i386/x86_64 
> architectures are used for tests.
> 
> Thanks for your patience for reading this, please take time to review
> and possibly accept my work.

Please rebase your patches against the ipset git tree: the development 
happens there and patches are submitted from the ipset git tree to 
nf-next. Also, do not forget to create numbered patches in the future. 
Thanks!

I'm able to apply one single patch from your current series.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

> 
> Please rebase your patches against the ipset git tree: the development
> happens there and patches are submitted from the ipset git tree to
> nf-next. Also, do not forget to create numbered patches in the future.
> Thanks!

Hello Jozsef.

I known that main development of the ipset is done in ipset git tree.
However current it's state is far from my branch. I guess there is excessive
number of conflicts on rebase.

Currently I'm able to do less or more clear rebase to the ipset git tree
until commit 920ddfa09efbd72a0fe43251cd19bc2c27aa3662
(Introduce RCU in all set types instead of rwlock per set).

As I wrote earlier I have series of 170 patches, rebase may take more
time than development of the my series. But even that's not main concern.
I can't warranty that everything after applying small series will be 
consistent at all, only after applying final series.

Maybe you are in interest of creating some branch on top of the
current ipset git tree to look at my work in the whole? Im not wery
happy with idea of rebasing my whole series to the ipset git tree
due to massive conflicts.

Sure there will be much less of work if you decide to merge branches.

Thanks for your interest for my series.

Sorry, forget to note in the original mail one category:

  * Using memory cache to store set elements (i.e. kmem_cache).

----

Also I did not do deep analysis of the current ipset git tree RCU 
implementation since patch introducing it looks monolitics, but I think
it has some number of problems.

For example quick overview of the current RCU implementation in the 
ip_set_core.c gives no hint on how all further readers are prevented from 
entering set before it is being destroyed (i.e. we can destroy core set data 
structures with ip_set_destroy_set() while they being accessed by the 
ip_set_test().

Also I don't think there is a good idea to modify cidr book keeping data
without any protection from the concurrent readers.

Using rcu_dereference_protected() with spin_is_locked() as condition
may be is not best choise, kernel has lockdep support for now, which
is more proven technique for locking issue debugging.

Using test_bit() in the fastpath loops to skip empty entries with bitmap
probably wastes more time than using ffs()/ffz().

Providing additionall variant callback ->uref() to handle references
seems confusing in aspects of set dump: we release set items
prior to dumping them. Furthermore due to netlink_dump_start()
nature (callbacks) there is no guarantee that we do not get
pointer to the new table after resize (for hashes) where all dumps
become inconsistent anyway. Running via callbacks implies no locking on the 
entire ipset structures (checked with lockdep), only first call of the callback 
may be locked with NFNL.

> 
> I'm able to apply one single patch from your current series.
> 
> Best regards,
> Jozsef
> -
> E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
> PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
> Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
>           H-1525 Budapest 114, POB. 49, Hungary

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

Hi Sergey,

On Tue, 17 Mar 2015, Sergey Popovich wrote:

> > Please rebase your patches against the ipset git tree: the development 
> > happens there and patches are submitted from the ipset git tree to 
> > nf-next. Also, do not forget to create numbered patches in the future. 
> > Thanks!
> 
> I known that main development of the ipset is done in ipset git tree. 
> However current it's state is far from my branch. I guess there is 
> excessive number of conflicts on rebase.

I cannot do much about it.

> Currently I'm able to do less or more clear rebase to the ipset git tree
> until commit 920ddfa09efbd72a0fe43251cd19bc2c27aa3662
> (Introduce RCU in all set types instead of rwlock per set).

That's before ipset 6.24 was released.
 
> As I wrote earlier I have series of 170 patches, rebase may take more
> time than development of the my series. But even that's not main concern.
> I can't warranty that everything after applying small series will be 
> consistent at all, only after applying final series.

170 patches are a lot. You should not have let to accumulate so many in 
your tree.

> Maybe you are in interest of creating some branch on top of the
> current ipset git tree to look at my work in the whole? Im not wery
> happy with idea of rebasing my whole series to the ipset git tree
> due to massive conflicts.
> 
> Sure there will be much less of work if you decide to merge branches.
> 
> Thanks for your interest for my series.

I'm really interested in your patches, but... do you expect me to roll 
back all of the patches in the ipset git tree, to go back before commit 
920ddfa09efbd72a0fe43251cd19bc2c27aa3662? Or to handle and resolve all 
conflicts when merging the ipset and your branch - instead of you?
 
> Sorry, forget to note in the original mail one category:
> 
>   * Using memory cache to store set elements (i.e. kmem_cache).
> 
> Also I did not do deep analysis of the current ipset git tree RCU 
> implementation since patch introducing it looks monolitics, but I think
> it has some number of problems.

As far as I know the only unresolved issue is the proper RCU handling of 
the comment extension.

> For example quick overview of the current RCU implementation in the 
> ip_set_core.c gives no hint on how all further readers are prevented from 
> entering set before it is being destroyed (i.e. we can destroy core set data 
> structures with ip_set_destroy_set() while they being accessed by the 
> ip_set_test().

That's excluded by the set references: set can be destroyed only when it's 
reference counter is zero and ip_set_test() can be called for referenced 
sets only.
 
> Also I don't think there is a good idea to modify cidr book keeping data
> without any protection from the concurrent readers.

cidr book keeping was changed so that it is safe to modify it without any 
protection. The worst case is that a reader loops at the same cidr value 
twice.
 
> Using rcu_dereference_protected() with spin_is_locked() as condition
> may be is not best choise, kernel has lockdep support for now, which
> is more proven technique for locking issue debugging.

The main point of the ipset git tree is to keep and maintain support 
kernel versions back to the last (i.e. 2.6.32) longterm kernel tree.
That means that a new feature from the mainline kernel is used when it can 
easily be backported or can be worked around by (fall back to) an old 
method.

> Using test_bit() in the fastpath loops to skip empty entries with bitmap
> probably wastes more time than using ffs()/ffz().

I'm sure patches for that can be applied without any problem.

> Providing additionall variant callback ->uref() to handle references 
> seems confusing in aspects of set dump: we release set items prior to 
> dumping them. Furthermore due to netlink_dump_start() nature (callbacks) 
> there is no guarantee that we do not get pointer to the new table after 
> resize (for hashes) where all dumps become inconsistent anyway. Running 
> via callbacks implies no locking on the entire ipset structures (checked 
> with lockdep), only first call of the callback may be locked with NFNL.

The uref() callback is required for the parallel resizing and dumping: 
dumping keeps the original hash table and the uref referecen counter tells 
the system which function should destroy it: resizing (because there are 
no parallel dump using the old hash table) or the dumping (because 
resizing successfully created a new hash table).

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

Hi Jozsef

> 
> I'm really interested in your patches, but... do you expect me to roll
> back all of the patches in the ipset git tree, to go back before commit
> 920ddfa09efbd72a0fe43251cd19bc2c27aa3662? Or to handle and resolve all
> conflicts when merging the ipset and your branch - instead of you?

I did not say that you should do anything, I just give an option (like branch) 
to let you quickly see changes I made if you wish. Maybe you find them totally 
useless:)

On the other hand I'm worry about if I start supplying my patch series (say 
this takes one month) there is no major changes will be entered to the master
ipset git tree, so I get rebase again and again, as actually happened before
commit 920ddfa09 where I have made some changes (bug fixes at that moment).

I will think on how to perform such rebase much painless and if you give no
other option I will try to perform repase for the master of ipset git tree.

I still think that having custom branch (say ipset-pending, ipset-current,
ipset-experimental etc.) would be a nice option. But this is only my point of
view:)

Thanks for your time.

> 
> > Sorry, forget to note in the original mail one category:
> >   * Using memory cache to store set elements (i.e. kmem_cache).
> > 
> > Also I did not do deep analysis of the current ipset git tree RCU
> > implementation since patch introducing it looks monolitics, but I think
> > it has some number of problems.
> 
> As far as I know the only unresolved issue is the proper RCU handling of
> the comment extension.
> 

> > For example quick overview of the current RCU implementation in the
> > ip_set_core.c gives no hint on how all further readers are prevented from
> > entering set before it is being destroyed (i.e. we can destroy core set
> > data structures with ip_set_destroy_set() while they being accessed by
> > the ip_set_test().
> 
> That's excluded by the set references: set can be destroyed only when it's
> reference counter is zero and ip_set_test() can be called for referenced
> sets only.

I did not agree with this since ip_set.c:ip_set_destroy_set() after checking
of reference counters is called, but ip_set(inst, index) = NULL (which itself
looks unclear since pointer assignments alone not guaranteed to be atomic,
thus rcu_assign_pointer() and friends exists) used without any RCU grace 
period waiters like synchronize_rcu(). Yes I see rcu_barrier() is used in each
set module, however it is more for waiting of callbacks to complete (or 
kfree_rcu).

Therefore ip_set_test() could easily enter set structures before ip_set(inst, 
index) = NULL and destroyed in the ip_set_destroy_set() at the same time.

There is other things to consider: ip_set_add()/ip_set_del() and of course
timeout enabled set gc routine (I known del_timer_sync() is the first
in ->destroy() method).

set_bit(j, n->used);
	if (old != ERR_PTR(-ENOENT)) {
		rcu_assign_pointer(hbucket(t, key), n);

This looks as data publishing prior to using it where bit is set before 
pointer to the new data assigned to the bucket.

Calling ip_set_ext_destroy() concurrently with readers seems also not
friendly. Currently this is only for commens, but if any other extension,
used by the readers is added problems will arise.

In general any modification to the data should be consistent for concurrent
readers all times, and should be only modified/released after RCU grace
period (or in case of RCU-bh after one softirq scheduling). Modification
data inline seems worse to me.

I didn't go deeper with current ipset git tree code, but sure there other
problems here.

> 
> > Also I don't think there is a good idea to modify cidr book keeping data
> > without any protection from the concurrent readers.
> 
> cidr book keeping was changed so that it is safe to modify it without any
> protection. The worst case is that a reader loops at the same cidr value
> twice.

Anyway this seems worse to me.

> 
> > Using rcu_dereference_protected() with spin_is_locked() as condition
> > may be is not best choise, kernel has lockdep support for now, which
> > is more proven technique for locking issue debugging.
> 
> The main point of the ipset git tree is to keep and maintain support
> kernel versions back to the last (i.e. 2.6.32) longterm kernel tree.
> That means that a new feature from the mainline kernel is used when it can
> easily be backported or can be worked around by (fall back to) an old
> method.

Yes I fully agree with you in this point and see no problem on backporting
up to the 2.6.32. I could even do some testings for major distros using such
kernels. No problem here.

I'm using 3.2.x series + nf-next version of ipset (which is sync to 6.23) for 
this development and it is works perfectly with wery few things backported.

However debugging locking issues without lockdep is much harder and
having one when it is available seems good.

> 
> > Using test_bit() in the fastpath loops to skip empty entries with bitmap
> > probably wastes more time than using ffs()/ffz().
> 
> I'm sure patches for that can be applied without any problem.

With minimal, since ffs()/ffz() may be architecture specific, or even generic 
taking unsigned long. However on 32 bit arches sizeof(unsigned long) == 4,
but net:iface uses up to 64 slots, so u64 type should be used with __ffs64().

As for optimizations I have many other small ones:)

> 
> > Providing additionall variant callback ->uref() to handle references
> > seems confusing in aspects of set dump: we release set items prior to
> > dumping them. Furthermore due to netlink_dump_start() nature (callbacks)
> > there is no guarantee that we do not get pointer to the new table after
> > resize (for hashes) where all dumps become inconsistent anyway. Running
> > via callbacks implies no locking on the entire ipset structures (checked
> > with lockdep), only first call of the callback may be locked with NFNL.
> 
> The uref() callback is required for the parallel resizing and dumping:
> dumping keeps the original hash table and the uref referecen counter tells
> the system which function should destroy it: resizing (because there are
> no parallel dump using the old hash table) or the dumping (because
> resizing successfully created a new hash table).

Yes, I'm already aware of this problem.

> 
> Best regards,
> Jozsef
> -
> E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
> PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
> Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
>           H-1525 Budapest 114, POB. 49, Hungary

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

On Tue, 17 Mar 2015, Sergey Popovich wrote:

> I did not say that you should do anything, I just give an option (like 
> branch) to let you quickly see changes I made if you wish. Maybe you 
> find them totally useless:)

I see - a branch costs nothing, so that's no problem. Then create a 
numbered list of the patches, put them in a tar file and let me know from 
where I can download it.
 
> On the other hand I'm worry about if I start supplying my patch series 
> (say this takes one month) there is no major changes will be entered to 
> the master ipset git tree, so I get rebase again and again, as actually 
> happened before commit 920ddfa09 where I have made some changes (bug 
> fixes at that moment).

Such things may happen when multiple patches flow in and some parts are 
just modified. But in such a case like this, changes can be communicated 
back and forth.

> > > For example quick overview of the current RCU implementation in the 
> > > ip_set_core.c gives no hint on how all further readers are prevented 
> > > from entering set before it is being destroyed (i.e. we can destroy 
> > > core set data structures with ip_set_destroy_set() while they being 
> > > accessed by the ip_set_test().
> > 
> > That's excluded by the set references: set can be destroyed only when it's
> > reference counter is zero and ip_set_test() can be called for referenced
> > sets only.
> 
> I did not agree with this since ip_set.c:ip_set_destroy_set() after 
> checking of reference counters is called, but ip_set(inst, index) = NULL 
> (which itself looks unclear since pointer assignments alone not 
> guaranteed to be atomic, thus rcu_assign_pointer() and friends exists) 
> used without any RCU grace period waiters like synchronize_rcu().

No. Please check xt_set.c and all the checkentry functions: sets are 
referenced there and until such reference is not created, no 
ip_set_test|add|del() function can use the set. The reference is released 
in the match/target destroy functions - and the set can be destroyed only 
after that. When the pointer assigment happens above, there cannot be any 
user of the set, there's no need for any protection.

> Yes I see rcu_barrier() is used in each set module, however it is more 
> for waiting of callbacks to complete (or kfree_rcu).

It's called from the module unload path. Actually, at that time there 
isn't any set belonging to the given set type (because otherwise the 
module could not be removed).
 
> Therefore ip_set_test() could easily enter set structures before 
> ip_set(inst, index) = NULL and destroyed in the ip_set_destroy_set() at 
> the same time.

That simply cannot happen due to the reference counter protection.

> There is other things to consider: ip_set_add()/ip_set_del() and of course
> timeout enabled set gc routine (I known del_timer_sync() is the first
> in ->destroy() method).
> 
> set_bit(j, n->used);
> 	if (old != ERR_PTR(-ENOENT)) {
> 		rcu_assign_pointer(hbucket(t, key), n);
> 
> This looks as data publishing prior to using it where bit is set before 
> pointer to the new data assigned to the bucket.

When new hashbucket is created, the set_bit() call is actually an 
initialization.
 
> Calling ip_set_ext_destroy() concurrently with readers seems also not
> friendly. Currently this is only for commens, but if any other extension,
> used by the readers is added problems will arise.

As I mentioned, that's the only part which needs fixing.
 
> In general any modification to the data should be consistent for 
> concurrent readers all times, and should be only modified/released after 
> RCU grace period (or in case of RCU-bh after one softirq scheduling). 
> Modification data inline seems worse to me.

When data can safely be modified, then that's the better approach.
 
> > > Also I don't think there is a good idea to modify cidr book keeping 
> > > data without any protection from the concurrent readers.
> > 
> > cidr book keeping was changed so that it is safe to modify it without 
> > any protection. The worst case is that a reader loops at the same cidr 
> > value twice.
> 
> Anyway this seems worse to me.

Why? No data corruption can happen and that's the fastest way. The worst 
case scenario is not the common case.
 
> > The main point of the ipset git tree is to keep and maintain support
> > kernel versions back to the last (i.e. 2.6.32) longterm kernel tree.
> 
> However debugging locking issues without lockdep is much harder and
> having one when it is available seems good.

It can probably be added in a wrapper which gives noop for older kernels.
 
> > > Using test_bit() in the fastpath loops to skip empty entries with 
> > > bitmap probably wastes more time than using ffs()/ffz().
> > 
> > I'm sure patches for that can be applied without any problem.
> 
> With minimal, since ffs()/ffz() may be architecture specific, or even 
> generic taking unsigned long. However on 32 bit arches sizeof(unsigned 
> long) == 4, but net:iface uses up to 64 slots, so u64 type should be 
> used with __ffs64().
> 
> As for optimizations I have many other small ones:)

Great, I'm looking forward for improvements!

> > > Providing additionall variant callback ->uref() to handle references
> > > seems confusing in aspects of set dump: we release set items prior to
> > > dumping them. Furthermore due to netlink_dump_start() nature (callbacks)
> > > there is no guarantee that we do not get pointer to the new table after
> > > resize (for hashes) where all dumps become inconsistent anyway. Running
> > > via callbacks implies no locking on the entire ipset structures (checked
> > > with lockdep), only first call of the callback may be locked with NFNL.
> > 
> > The uref() callback is required for the parallel resizing and dumping:
> > dumping keeps the original hash table and the uref referecen counter tells
> > the system which function should destroy it: resizing (because there are
> > no parallel dump using the old hash table) or the dumping (because
> > resizing successfully created a new hash table).
> 
> Yes, I'm already aware of this problem.

The problem is already solved in the current ipset git tree.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

> > I did not say that you should do anything, I just give an option (like
> > branch) to let you quickly see changes I made if you wish. Maybe you
> > find them totally useless:)
> 
> I see - a branch costs nothing, so that's no problem. Then create a
> numbered list of the patches, put them in a tar file and let me know from
> where I can download it.

Thanks Jozsef, I have prepare patches for you and put link to the series.

http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015031701.tar

These patches will be against nf-next for simplicity and I'm already rebase
them, so for first review just fresh nf-next will be needed.

> > > > For example quick overview of the current RCU implementation in the
> > > > ip_set_core.c gives no hint on how all further readers are prevented
> > > > from entering set before it is being destroyed (i.e. we can destroy
> > > > core set data structures with ip_set_destroy_set() while they being
> > > > accessed by the ip_set_test().
> > > 
> > > That's excluded by the set references: set can be destroyed only when
> > > it's
> > > reference counter is zero and ip_set_test() can be called for referenced
> > > sets only.
> > 
> > I did not agree with this since ip_set.c:ip_set_destroy_set() after
> > checking of reference counters is called, but ip_set(inst, index) = NULL
> > (which itself looks unclear since pointer assignments alone not
> > guaranteed to be atomic, thus rcu_assign_pointer() and friends exists)
> > used without any RCU grace period waiters like synchronize_rcu().
> 
> No. Please check xt_set.c and all the checkentry functions: sets are
> referenced there and until such reference is not created, no
> ip_set_test|add|del() function can use the set. The reference is released
> in the match/target destroy functions - and the set can be destroyed only
> after that. When the pointer assigment happens above, there cannot be any
> user of the set, there's no need for any protection.

If you mean ip_set*nfnl*() then they just needed to be used in the properly
written code (such as xt_set.c and em_ipset.c). However they just reference
set to prevent it from deletion. Set already published in netns ip_set_list
and available to ip_set_add() and ip_set_del() (sure anyone should not call 
these functions from the kernel without first referencing the set with 
ip_set*nfnl*()).

On the other hand, code using ip_set_{add,del,test}() should also ensure
there is no callers to such ones after ip_set*nfnl*().

I reviewed all of such code in xt_set.c and em_ipset.c and you are right.
Im just try to be more paranoid in the subsystem implementation.

> 
> > Yes I see rcu_barrier() is used in each set module, however it is more
> > for waiting of callbacks to complete (or kfree_rcu).
> 
> It's called from the module unload path. Actually, at that time there
> isn't any set belonging to the given set type (because otherwise the
> module could not be removed).

I think it is not necessary at all if no outstanding rcu callbacks are used
in favor to kfree_rcu() which itselfs rcu callback to kfree() to just free
data without any actions taken (for which rcu callbacks intended).

In my series callbacks used to destroy memory cache allocations and
extensions.

I like to take full copy of the bucket before modification with extensions
and not rely on set_bit()/clear_bit() it gives on guarantee on reordering on 
arches other than x86 (see comment in include/asm-generic/atomic.h).

So adding new element takes copy of the full bucket (which is up to 12
positions for all hash:* except netiface, where it 64 positions) and
extensions.

Yes, it seems expensive, but correct in all aspects including extensions. 
Previous copies destroyed with rcu callbacks. Callbacks itself wery simple 
pose minimal overhead.

I split implementation of bitmap:* sets to the two variants: ordinary
array of bits when set created w/o extensions and array of pointers (hash 
table w/o collisions) for sets w/ extensions, since having bitmap:* with
extensions anyway uses array of extensions data and accessing pointer
is a cheap on most platforms. This also simplifies my RCU implementation.

For bitmap:* where bitmap (array of bits, no extensions) is used there is no 
RCU needed since whenever we have bit set or bit clear for concurrent
readers on modify does not play any significant role.

For bitmap:* implemented as array of pointers (element is in set if pointer
points to the data) this is much like for hash:* sets.

For list:set it is standard linux double linked list RCU variant.

Destroy procedure is split into parts:
  hide set from the new readers

  flush all elements from the set, and mark it as inactive under set lock,
  so other writers (ip_set_test() -EAGAIN for bitmap:ipmac and 
  ip_set_{add,del}() and gc routine) won't modify it. Current readers
  may still use set data.

  wait for RCU grace period to let readers to finish with set structures

  wait for RCU callbacks to complete (after flushing elements)

  finally destroy set data without any lock.

All tests I made are done on relatively ancient hardware (Pentium D 2.8Ghz,
DDR 2 for SMP x86, x86_64 and PIII 1Ghz for UP).

> > There is other things to consider: ip_set_add()/ip_set_del() and of course
> > timeout enabled set gc routine (I known del_timer_sync() is the first
> > in ->destroy() method).
> > 
> > set_bit(j, n->used);
> > 
> > 	if (old != ERR_PTR(-ENOENT)) {
> > 	
> > 		rcu_assign_pointer(hbucket(t, key), n);
> > 
> > This looks as data publishing prior to using it where bit is set before
> > pointer to the new data assigned to the bucket.
> 
> When new hashbucket is created, the set_bit() call is actually an
> initialization.

Yes, sorry for that, n is an unpublished bucket. Correct.

But what about memcpy()? Extensions assignment? These operations
is not atomic.

> 
> > Calling ip_set_ext_destroy() concurrently with readers seems also not
> > friendly. Currently this is only for commens, but if any other extension,
> > used by the readers is added problems will arise.
> 
> As I mentioned, that's the only part which needs fixing.
> 
> > In general any modification to the data should be consistent for
> > concurrent readers all times, and should be only modified/released after
> > RCU grace period (or in case of RCU-bh after one softirq scheduling).
> > Modification data inline seems worse to me.
> 
> When data can safely be modified, then that's the better approach.
> 
> > > > Also I don't think there is a good idea to modify cidr book keeping
> > > > data without any protection from the concurrent readers.
> > > 
> > > cidr book keeping was changed so that it is safe to modify it without
> > > any protection. The worst case is that a reader loops at the same cidr
> > > value twice.
> > 
> > Anyway this seems worse to me.
> 
> Why? No data corruption can happen and that's the fastest way. The worst
> case scenario is not the common case.
> 
> > > The main point of the ipset git tree is to keep and maintain support
> > > kernel versions back to the last (i.e. 2.6.32) longterm kernel tree.
> > 
> > However debugging locking issues without lockdep is much harder and
> > having one when it is available seems good.
> 
> It can probably be added in a wrapper which gives noop for older kernels.

Yes, supporting old kernels is a good choise.

On the other hand I think that it would be nice to have branch, similar to the 
nf-next (say ipset-next) for supplying patches to the upstream and make all 
code in this branch inline with upstream kernel.

I think this eases work for supplying patches from ipset to nf-next, or
request for pull may be send to mailing list instead of individual patches
(this is how nf-next pulled by DM into net-next).

Then new changes from the ipset-next could be backported into ipset git tree
(say it would be named as ipset-stable to the analogy with linux-stable etc.).

> 
> Best regards,
> Jozsef
> -
> E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
> PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
> Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
>           H-1525 Budapest 114, POB. 49, Hungary

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

On Tue, 17 Mar 2015, Sergey Popovich wrote:

> Thanks Jozsef, I have prepare patches for you and put link to the series.
> 
> http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015031701.tar
> 
> These patches will be against nf-next for simplicity and I'm already rebase
> them, so for first review just fresh nf-next will be needed.

Thanks, I have downloaded it and started to review the patches.
 
> > No. Please check xt_set.c and all the checkentry functions: sets are
> > referenced there and until such reference is not created, no
> > ip_set_test|add|del() function can use the set. The reference is released
> > in the match/target destroy functions - and the set can be destroyed only
> > after that. When the pointer assigment happens above, there cannot be any
> > user of the set, there's no need for any protection.
> 
> If you mean ip_set*nfnl*() then they just needed to be used in the properly
> written code (such as xt_set.c and em_ipset.c). However they just reference
> set to prevent it from deletion. Set already published in netns ip_set_list
> and available to ip_set_add() and ip_set_del() (sure anyone should not call 
> these functions from the kernel without first referencing the set with 
> ip_set*nfnl*()).
> 
> On the other hand, code using ip_set_{add,del,test}() should also ensure
> there is no callers to such ones after ip_set*nfnl*().
> 
> I reviewed all of such code in xt_set.c and em_ipset.c and you are right.
> Im just try to be more paranoid in the subsystem implementation.

There are countless ways to break the kernel from inside when the API is 
violated in a module.

> > > Yes I see rcu_barrier() is used in each set module, however it is more
> > > for waiting of callbacks to complete (or kfree_rcu).
> > 
> > It's called from the module unload path. Actually, at that time there
> > isn't any set belonging to the given set type (because otherwise the
> > module could not be removed).
> 
> I think it is not necessary at all if no outstanding rcu callbacks are used
> in favor to kfree_rcu() which itselfs rcu callback to kfree() to just free
> data without any actions taken (for which rcu callbacks intended).

When Pablo reviewed the RCU patches he suggested to add the calls to 
rcu_barrier() for the clarity.

> In my series callbacks used to destroy memory cache allocations and
> extensions.
> 
> I like to take full copy of the bucket before modification with extensions
> and not rely on set_bit()/clear_bit() it gives on guarantee on reordering on 
> arches other than x86 (see comment in include/asm-generic/atomic.h).

Reordering can be prevented with smp_mb__before_atomic() and alike.

> So adding new element takes copy of the full bucket (which is up to 12
> positions for all hash:* except netiface, where it 64 positions) and
> extensions.
>
> Yes, it seems expensive, but correct in all aspects including extensions. 
> Previous copies destroyed with rcu callbacks. Callbacks itself wery simple 
> pose minimal overhead.

The memory allocations are expensive operations!

> I split implementation of bitmap:* sets to the two variants: ordinary
> array of bits when set created w/o extensions and array of pointers (hash 
> table w/o collisions) for sets w/ extensions, since having bitmap:* with
> extensions anyway uses array of extensions data and accessing pointer
> is a cheap on most platforms. This also simplifies my RCU implementation.
> 
> For bitmap:* where bitmap (array of bits, no extensions) is used there is no 
> RCU needed since whenever we have bit set or bit clear for concurrent
> readers on modify does not play any significant role.
> 
> For bitmap:* implemented as array of pointers (element is in set if pointer
> points to the data) this is much like for hash:* sets.
> 
> For list:set it is standard linux double linked list RCU variant.

This is quite similar how RCU is introduced in ipset.

> Destroy procedure is split into parts:
>   hide set from the new readers
> 
>   flush all elements from the set, and mark it as inactive under set lock,
>   so other writers (ip_set_test() -EAGAIN for bitmap:ipmac and 
>   ip_set_{add,del}() and gc routine) won't modify it. Current readers
>   may still use set data.
> 
>   wait for RCU grace period to let readers to finish with set structures
> 
>   wait for RCU callbacks to complete (after flushing elements)
> 
>   finally destroy set data without any lock.

There are NO READERS when the destroy function is called.

> All tests I made are done on relatively ancient hardware (Pentium D 2.8Ghz,
> DDR 2 for SMP x86, x86_64 and PIII 1Ghz for UP).
> 
> > > There is other things to consider: ip_set_add()/ip_set_del() and of course
> > > timeout enabled set gc routine (I known del_timer_sync() is the first
> > > in ->destroy() method).
> > > 
> > > set_bit(j, n->used);
> > > 
> > > 	if (old != ERR_PTR(-ENOENT)) {
> > > 	
> > > 		rcu_assign_pointer(hbucket(t, key), n);
> > > 
> > > This looks as data publishing prior to using it where bit is set before
> > > pointer to the new data assigned to the bucket.
> > 
> > When new hashbucket is created, the set_bit() call is actually an
> > initialization.
> 
> Yes, sorry for that, n is an unpublished bucket. Correct.
> 
> But what about memcpy()? Extensions assignment? These operations
> is not atomic.

Those are also initializations in the code part you refer to.

Also please note, the comment extension is alone which needs special 
treatment. At the same time it is not used by the kernel functions at all 
- except when dumping the set. Therefore I want to avoid any *unnecessary* 
overhead (both in processing and memory usage) about it.

> > > However debugging locking issues without lockdep is much harder and
> > > having one when it is available seems good.
> > 
> > It can probably be added in a wrapper which gives noop for older kernels.
> 
> Yes, supporting old kernels is a good choise.
> 
> On the other hand I think that it would be nice to have branch, similar to the 
> nf-next (say ipset-next) for supplying patches to the upstream and make all 
> code in this branch inline with upstream kernel.

That's a maintenance question. So far the backported/wrapped things could 
be kept to a minimum number which made possible to keep a single branch.

> I think this eases work for supplying patches from ipset to nf-next, or
> request for pull may be send to mailing list instead of individual patches
> (this is how nf-next pulled by DM into net-next).

I maintain an nf-next tree in order to make possible the simple pulling of 
the patches, but that is independent from the ipset git tree (because of 
the backward compatibility stuff).

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

> > > I did not say that you should do anything, I just give an option (like
> > > branch) to let you quickly see changes I made if you wish. Maybe you
> > > find them totally useless:)
> > 
> > I see - a branch costs nothing, so that's no problem. Then create a
> > numbered list of the patches, put them in a tar file and let me know from
> > where I can download it.
> 
> Thanks Jozsef, I have prepare patches for you and put link to the series.
> 
> http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015031701.tar
> 
> These patches will be against nf-next for simplicity and I'm already rebase
> them, so for first review just fresh nf-next will be needed.
> 

Fixes to the first series. One of the most important is the fixes to set and 
their data netlink dumping consistency. Just to complete series.

Netlink dumping consistency was inspired by the recent ipset git tree fixes
to this problem. However I think there are other problems with consistent
data dumping exists which my series tries to addess.

As the first series this is for nf-next git tree, not ipset git tree.

http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015032501.tar

> Then new changes from the ipset-next could be backported into ipset git tree
> (say it would be named as ipset-stable to the analogy with linux-stable
> etc.).
> > Best regards,
> > Jozsef
> > -
> > E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
> > PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
> > Address : Wigner Research Centre for Physics, Hungarian Academy of
> > Sciences
> > 
> >           H-1525 Budapest 114, POB. 49, Hungary

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Pablo Neira Ayuso]

On Wed, Mar 25, 2015 at 04:54:54PM +0200, Sergey Popovich wrote:
> > > > I did not say that you should do anything, I just give an option (like
> > > > branch) to let you quickly see changes I made if you wish. Maybe you
> > > > find them totally useless:)
> > > 
> > > I see - a branch costs nothing, so that's no problem. Then create a
> > > numbered list of the patches, put them in a tar file and let me know from
> > > where I can download it.
> > 
> > Thanks Jozsef, I have prepare patches for you and put link to the series.
> > 
> > http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015031701.tar
> > 
> > These patches will be against nf-next for simplicity and I'm already rebase
> > them, so for first review just fresh nf-next will be needed.
> > 
> 
> Fixes to the first series. One of the most important is the fixes to set and 
> their data netlink dumping consistency. Just to complete series.
> 
> Netlink dumping consistency was inspired by the recent ipset git tree fixes
> to this problem. However I think there are other problems with consistent
> data dumping exists which my series tries to addess.
> 
> As the first series this is for nf-next git tree, not ipset git tree.
> 
> http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015032501.tar

Could please send small batch (not more than 10 patches in one go,
please) to the mailing list so everyone can help in reviewing this?

Thanks.

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

> On Wed, Mar 25, 2015 at 04:54:54PM +0200, Sergey Popovich wrote:

> Could please send small batch (not more than 10 patches in one go,
> please) to the mailing list so everyone can help in reviewing this?

Not a problem.

My series of patches for nf-next, while Jozsef would like to receive
patches against ipset git tree and rebase may take a while.

Main problem with rebase is that my series implementing RCU, but
this implementation differs from one found in the current ipset git
tree.

This causes excessive number of conflicts, requiring lot of porting
to ipset git tree.

As option I could send only bugfixes to the current nf-next, of course
if Jozsef acknowledges them.

Thanks for the interest.

> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel"
> in the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Pablo Neira Ayuso]

On Wed, Mar 25, 2015 at 06:11:26PM +0200, Sergey Popovich wrote:
> > On Wed, Mar 25, 2015 at 04:54:54PM +0200, Sergey Popovich wrote:
> 
> > Could please send small batch (not more than 10 patches in one go,
> > please) to the mailing list so everyone can help in reviewing this?
> 
> Not a problem.
> 
> My series of patches for nf-next, while Jozsef would like to receive
> patches against ipset git tree and rebase may take a while.
> 
> Main problem with rebase is that my series implementing RCU, but
> this implementation differs from one found in the current ipset git
> tree.
> 
> This causes excessive number of conflicts, requiring lot of porting
> to ipset git tree.
> 
> As option I could send only bugfixes to the current nf-next, of course
> if Jozsef acknowledges them.

Jozsef wants that you route the patches through the ipset tree, so
please use that tree as reference.

Sending bugfixes in first place make sense to me, Cc'ing
netfilter-devel as inline patches (eg. git-send-mail) so everyone here
can help reviewing them.

Thanks.

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

On Wed, 25 Mar 2015, Sergey Popovich wrote:

> > > > I did not say that you should do anything, I just give an option (like
> > > > branch) to let you quickly see changes I made if you wish. Maybe you
> > > > find them totally useless:)
> > > 
> > > I see - a branch costs nothing, so that's no problem. Then create a
> > > numbered list of the patches, put them in a tar file and let me know from
> > > where I can download it.
> > 
> > Thanks Jozsef, I have prepare patches for you and put link to the series.
> > 
> > http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015031701.tar
> > 
> > These patches will be against nf-next for simplicity and I'm already rebase
> > them, so for first review just fresh nf-next will be needed.
> 
> Fixes to the first series. One of the most important is the fixes to set and 
> their data netlink dumping consistency. Just to complete series.
> 
> Netlink dumping consistency was inspired by the recent ipset git tree fixes
> to this problem. However I think there are other problems with consistent
> data dumping exists which my series tries to addess.
> 
> As the first series this is for nf-next git tree, not ipset git tree.
> 
> http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015032501.tar

I can review them but the patches need to be ported to the ipset git tree.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: ipset: Proposed improvements to the kernel code

[Sergey Popovich]

> On Wed, 25 Mar 2015, Sergey Popovich wrote:

> > Netlink dumping consistency was inspired by the recent ipset git tree
> > fixes
> > to this problem. However I think there are other problems with consistent
> > data dumping exists which my series tries to addess.
> > 
> > As the first series this is for nf-next git tree, not ipset git tree.
> > 
> > http://ftp.payport.com.ua/users/sergey/public/netfilter-devel-2015032501.t
> > ar
> I can review them but the patches need to be ported to the ipset git tree.
> 

I'm fully understand your point of view. And aggree with you as maintainer
and core developer of the ipset project.

However from my point of view this looks just horrible. I'm not happy with
taking much of time of making same work two times and rebase patches
against new tree.

So I decide to give my patch series status "works for me" and leave anything
as is. Without any rebase to the ipset git tree.

>From private mails I known about your plans about in kernel ipset tree 
(especially nf-next and mainline kernel therefore) and I'm compliment
these changes.

Thanks for interest and reviewing of my series.

> Best regards,
> Jozsef
> -
> E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
> PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
> Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
>           H-1525 Budapest 114, POB. 49, Hungary
> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel"
> in the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

-- 
SP5474-RIPE
Sergey Popovich

Re: ipset: Proposed improvements to the kernel code

[Jozsef Kadlecsik]

On Fri, 27 Mar 2015, Sergey Popovich wrote:

> > I can review them but the patches need to be ported to the ipset git 
> > tree.
> 
> I'm fully understand your point of view. And aggree with you as 
> maintainer and core developer of the ipset project.
> 
> However from my point of view this looks just horrible. I'm not happy 
> with taking much of time of making same work two times and rebase 
> patches against new tree.
> 
> So I decide to give my patch series status "works for me" and leave anything
> as is. Without any rebase to the ipset git tree.
> 
> >From private mails I known about your plans about in kernel ipset tree 
> (especially nf-next and mainline kernel therefore) and I'm compliment
> these changes.
> 
> Thanks for interest and reviewing of my series.

I do appreciate your work. However I cannot undo your decision not to base 
your patches on the ipset git tree.

I'll review your patches and apply what can be or logically fit, keeping 
your credits.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary