netns: fix net_generic() "id - 1" bloat

PATCH In review Alexey Dobriyan 2 participants 8 messages Dec 1, 2016 – Dec 14, 2016

Subsystems (2)

Networking Network drivers

lore

Share & tools

lore

Alexey Dobriyan

author

2016-12-01 23:21 UTC #0 lore raw

PATCH 3/3 netns: fix net_generic() "id - 1" bloat

net_generic() function is both a) inline and b) used ~600 times.

It has the following code inside

		...
	ptr = ng->ptr[id - 1];
		...

"id" is never compile time constant so compiler is forced to subtract 1. And those decrements or LEA [r32 - 1] instructions add up.

We also start id'ing from 1 to catch bugs where pernet sybsystem id is not initialized and 0. This is quite pointless idea (nothing will work or immediate interference with first registered subsystem) in general but it hints what needs to be done for code size reduction.

Namely, overlaying allocation of pointer array and fixed part of structure in the beginning and using usual base-0 addressing.

Ids are just cookies, their exact values do not matter, so lets start with 3 on x86_64.

Code size savings (oh boy): -4.2 KB

As usual, ignore the initial compiler stupidity part of the table.

add/remove: 0/0 grow/shrink: 12/670 up/down: 89/-4297 (-4208)
function old new delta
tipc_nametbl_insert_publ 1250 1270 +20
nlmclnt_lookup_host 686 703 +17
nfsd4_encode_fattr 5930 5941 +11
nfs_get_client 1050 1061 +11
register_pernet_operations 333 342 +9
tcf_mirred_init 843 849 +6
tcf_bpf_init 1143 1149 +6
gss_setup_upcall 990 994 +4
idmap_name_to_id 432 434 +2
ops_init 274 275 +1
nfsd_inject_forget_client 259 260 +1
nfs4_alloc_client 612 613 +1
tunnel_key_walker 164 163 -1

...

tipc_bcbase_select_primary 392 360 -32
mac80211_hwsim_new_radio 2808 2767 -41
ipip6_tunnel_ioctl 2228 2186 -42
tipc_bcast_rcv 715 672 -43
tipc_link_build_proto_msg 1140 1089 -51
nfsd4_lock 3851 3796 -55
tipc_mon_rcv 1012 956 -56
Total: Before=156643951, After=156639743, chg -0.00%

Signed-off-by Alexey Dobriyan <[email protected]>

---

 include/net/netns/generic.h |   16 +++++++++-------
 net/core/net_namespace.c    |   20 ++++++++++++--------
 2 files changed, 21 insertions(+), 15 deletions(-)

include/net/netns/generic.h +9 -7

@@ -25,12 +25,14 @@
  */
 
 struct net_generic {
-	struct {
-		unsigned int len;
-		struct rcu_head rcu;
-	} s;
-
-	void *ptr[0];
+	union {
+		struct {
+			unsigned int len;
+			struct rcu_head rcu;
+		} s;
+
+		void *ptr[0];
+	};
 };
 
 static inline void *net_generic(const struct net *net, unsigned int id)

@@ -40,7 +42,7 @@ static inline void *net_generic(const struct net *net, unsigned int id)
 
 	rcu_read_lock();
 	ng = rcu_dereference(net->gen);
-	ptr = ng->ptr[id - 1];
+	ptr = ng->ptr[id];
 	rcu_read_unlock();
 
 	return ptr;

net/core/net_namespace.c +12 -8

@@ -39,6 +39,9 @@ EXPORT_SYMBOL(init_net);
 
 static bool init_net_initialized;
 
+#define MIN_PERNET_OPS_ID	\
+	((sizeof(struct net_generic) + sizeof(void *) - 1) / sizeof(void *))
+
 #define INITIAL_NET_GEN_PTRS	13 /* +1 for len +2 for rcu_head */
 
 static unsigned int max_gen_ptrs = INITIAL_NET_GEN_PTRS;

@@ -46,7 +49,7 @@ static unsigned int max_gen_ptrs = INITIAL_NET_GEN_PTRS;
 static struct net_generic *net_alloc_generic(void)
 {
 	struct net_generic *ng;
-	size_t generic_size = offsetof(struct net_generic, ptr[max_gen_ptrs]);
+	unsigned int generic_size = offsetof(struct net_generic, ptr[max_gen_ptrs]);
 
 	ng = kzalloc(generic_size, GFP_KERNEL);
 	if (ng)

@@ -60,12 +63,12 @@ static int net_assign_generic(struct net *net, unsigned int id, void *data)
 	struct net_generic *ng, *old_ng;
 
 	BUG_ON(!mutex_is_locked(&net_mutex));
-	BUG_ON(id == 0);
+	BUG_ON(id < MIN_PERNET_OPS_ID);
 
 	old_ng = rcu_dereference_protected(net->gen,
 					   lockdep_is_held(&net_mutex));
-	if (old_ng->s.len >= id) {
-		old_ng->ptr[id - 1] = data;
+	if (old_ng->s.len > id) {
+		old_ng->ptr[id] = data;
 		return 0;
 	}

@@ -84,8 +87,9 @@ static int net_assign_generic(struct net *net, unsigned int id, void *data)
 	 * the old copy for kfree after a grace period.
 	 */
 
-	memcpy(&ng->ptr, &old_ng->ptr, old_ng->s.len * sizeof(void*));
-	ng->ptr[id - 1] = data;
+	memcpy(&ng->ptr[MIN_PERNET_OPS_ID], &old_ng->ptr[MIN_PERNET_OPS_ID],
+	       (old_ng->s.len - MIN_PERNET_OPS_ID) * sizeof(void *));
+	ng->ptr[id] = data;
 
 	rcu_assign_pointer(net->gen, ng);
 	kfree_rcu(old_ng, s.rcu);

@@ -874,7 +878,7 @@ static int register_pernet_operations(struct list_head *list,
 
 	if (ops->id) {
 again:
-		error = ida_get_new_above(&net_generic_ids, 1, ops->id);
+		error = ida_get_new_above(&net_generic_ids, MIN_PERNET_OPS_ID, ops->id);
 		if (error < 0) {
 			if (error == -EAGAIN) {
 				ida_pre_get(&net_generic_ids, GFP_KERNEL);

@@ -882,7 +886,7 @@ static int register_pernet_operations(struct list_head *list,
 			}
 			return error;
 		}
-		max_gen_ptrs = max(max_gen_ptrs, *ops->id);
+		max_gen_ptrs = max(max_gen_ptrs, *ops->id + 1);
 	}
 	error = __register_pernet_operations(list, ops);
 	if (error) {

David Laight

2016-12-05 12:49 UTC #1 lore raw

From: Alexey Dobriyan

Quoted 22 lines

Sent: 02 December 2016 01:22
net_generic() function is both a) inline and b) used ~600 times.
It has the following code inside
		...
	ptr = ng->ptr[id - 1];
		...
"id" is never compile time constant so compiler is forced to subtract 1. And those decrements or LEA [r32 - 1] instructions add up.
We also start id'ing from 1 to catch bugs where pernet sybsystem id is not initialized and 0. This is quite pointless idea (nothing will work or immediate interference with first registered subsystem) in general but it hints what needs to be done for code size reduction.
Namely, overlaying allocation of pointer array and fixed part of structure in the beginning and using usual base-0 addressing.
Ids are just cookies, their exact values do not matter, so lets start with 3 on x86_64.

...

Quoted 6 lines

struct net_generic {
include/net/netns/generic.h +0 -5
-	struct {
-		unsigned int len;
-		struct rcu_head rcu;
-	} s;
-

include/net/netns/generic.h line 36

Quoted 10 lines

include/net/netns/generic.h +8 -1

-	void *ptr[0];
+	union {
+		struct {
+			unsigned int len;
+			struct rcu_head rcu;
+		} s;
+
+		void *ptr[0];
+	};
 };

That union is an accident waiting to happen.
What might work is to offset the Ids by
(offsetof(struct net_generic, ptr)/sizeof (void *)) instead of by 1. The subtract from the offset will then counter the structure offset
- which is what you are trying to achieve.

David.

Alexey Dobriyan

author

2016-12-05 14:48 UTC #2 lore raw

Quoted 34 lines · David Laight

From: Alexey Dobriyan
Quoted 22 lines
Sent: 02 December 2016 01:22
net_generic() function is both a) inline and b) used ~600 times.
It has the following code inside
              ...
      ptr = ng->ptr[id - 1];
              ...
"id" is never compile time constant so compiler is forced to subtract 1. And those decrements or LEA [r32 - 1] instructions add up.
We also start id'ing from 1 to catch bugs where pernet sybsystem id is not initialized and 0. This is quite pointless idea (nothing will work or immediate interference with first registered subsystem) in general but it hints what needs to be done for code size reduction.
Namely, overlaying allocation of pointer array and fixed part of structure in the beginning and using usual base-0 addressing.
Ids are just cookies, their exact values do not matter, so lets start with 3 on x86_64.
...
Quoted 10 lines
struct net_generic {
include/net/netns/generic.h +3 -6
-     struct {
-             unsigned int len;
-             struct rcu_head rcu;
-     } s;
-
-     void *ptr[0];
+     union {
+             struct {
+                     unsigned int len;

Quoted 8 lines

include/net/netns/generic.h line 36
Quoted 6 lines
include/net/netns/generic.h +5 -0
+                     struct rcu_head rcu;
+             } s;
+
+             void *ptr[0];
+     };
 };
That union is an accident waiting to happen.

I kind of disagree. Module authors should not be given matches, but it is hard to screw up if net_generic() is all you're given.

Quoted 4 lines

What might work is to offset the Ids by
(offsetof(struct net_generic, ptr)/sizeof (void *)) instead of by 1. The subtract from the offset will then counter the structure offset
- which is what you are trying to achieve.

If you suggest this layout

struct net_generic {
        struct {
        } s;
        void *ptr[0];
};

then is it not optimal because offset of "ptr" needs to be somewhere in code either in some LEA or imm8 of the final MOV which is 1 byte more bloaty.

Here is test program

struct ng1 {
        union {
                struct {
                        unsigned int len;
                } s;
                void *ptr[0];
        };
};
struct ng2 {
        struct {
                unsigned int len;
        } s;
        void *ptr[0];
};
struct net {
        int x;
        struct ng1 *gen1;
        struct ng2 *gen2;
};
void *ng1(const struct net *net, unsigned int id)
{
        return net->gen1->ptr[id];
}
void *ng2(const struct net *net, unsigned int id)
{
        return net->gen2->ptr[id];
}

0000000000000000 <ng1>:

   0:   48 8b 47 08             mov    rax,QWORD PTR [rdi+0x8]
   4:   89 f6                   mov    esi,esi
   6:   48 8b 04 f0             mov    rax,QWORD PTR [rax+rsi*8]
   a:   c3                      ret

0000000000000010 <ng2>:

  10:   48 8b 47 10             mov    rax,QWORD PTR [rdi+0x10]
  14:   89 f6                   mov    esi,esi
  16:   48 8b 44 f0 [[[08]]]          mov    rax,QWORD PTR [rax+rsi*8+0x8]
  1b:   c3                      ret

I can send more type checking if you can tolerate "_" identifier

    struct {
        unsigned int _;
    } pernet_ops_id_t;

David Laight

2016-12-07 10:49 UTC #3 lore raw

From: Alexey Dobriyan

Quoted 102 lines

Sent: 05 December 2016 14:48
Quoted 34 lines · David Laight
From: Alexey Dobriyan
Quoted 22 lines
Sent: 02 December 2016 01:22
net_generic() function is both a) inline and b) used ~600 times.
It has the following code inside
              ...
      ptr = ng->ptr[id - 1];
              ...
"id" is never compile time constant so compiler is forced to subtract 1. And those decrements or LEA [r32 - 1] instructions add up.
We also start id'ing from 1 to catch bugs where pernet sybsystem id is not initialized and 0. This is quite pointless idea (nothing will work or immediate interference with first registered subsystem) in general but it hints what needs to be done for code size reduction.
Namely, overlaying allocation of pointer array and fixed part of structure in the beginning and using usual base-0 addressing.
Ids are just cookies, their exact values do not matter, so lets start with 3 on x86_64.
...
Quoted 10 lines
struct net_generic {
include/net/netns/generic.h +3 -6
-     struct {
-             unsigned int len;
-             struct rcu_head rcu;
-     } s;
-
-     void *ptr[0];
+     union {
+             struct {
+                     unsigned int len;
Quoted 8 lines
include/net/netns/generic.h line 36
Quoted 6 lines
include/net/netns/generic.h +5 -0
+                     struct rcu_head rcu;
+             } s;
+
+             void *ptr[0];
+     };
 };
That union is an accident waiting to happen.
I kind of disagree. Module authors should not be given matches, but it is hard to screw up if net_generic() is all you're given.
Quoted 4 lines
What might work is to offset the Ids by
(offsetof(struct net_generic, ptr)/sizeof (void *)) instead of by 1. The subtract from the offset will then counter the structure offset
- which is what you are trying to achieve.
If you suggest this layout
struct net_generic {
        struct {
        } s;
        void *ptr[0];
};
then is it not optimal because offset of "ptr" needs to be somewhere in code either in some LEA or imm8 of the final MOV which is 1 byte more bloaty.
Here is test program
struct ng1 {
        union {
                struct {
                        unsigned int len;
                } s;
                void *ptr[0];
        };
};
struct ng2 {
        struct {
                unsigned int len;
        } s;
        void *ptr[0];
};
struct net {
        int x;
        struct ng1 *gen1;
        struct ng2 *gen2;
};
void *ng1(const struct net *net, unsigned int id)
{
        return net->gen1->ptr[id];
}
void *ng2(const struct net *net, unsigned int id)
{
        return net->gen2->ptr[id];
}
0000000000000000 <ng1>:
   0:   48 8b 47 08             mov    rax,QWORD PTR [rdi+0x8]
   4:   89 f6                   mov    esi,esi
   6:   48 8b 04 f0             mov    rax,QWORD PTR [rax+rsi*8]
   a:   c3                      ret

Quoted 5 lines

0000000000000010 <ng2>:

  10:   48 8b 47 10             mov    rax,QWORD PTR [rdi+0x10]
  14:   89 f6                   mov    esi,esi
  16:   48 8b 44 f0 [[[08]]]          mov    rax,QWORD PTR [rax+rsi*8+0x8]
  1b:   c3                      ret

On x86 that will make ~0 difference since the offset (in that sequence) doesn't require an extra instruction.

However if you offset the 'id' values so that only values 2 up are valid the code becomes:

	return net->gen2->ptr[id - 2];
which will be exactly the same code as:
	return net->gen1->ptr[id];

but it is much more obvious that 'id' values must be >= 2.

The '2' should be generated from the structure offset, but with my method is doesn't actually matter if it is wrong.

David

Alexey Dobriyan

author

2016-12-13 14:23 UTC #4 lore raw

Quoted 103 lines · David Laight

From: Alexey Dobriyan
Quoted 102 lines
Sent: 05 December 2016 14:48
Quoted 34 lines · David Laight
From: Alexey Dobriyan
Quoted 22 lines
Sent: 02 December 2016 01:22
net_generic() function is both a) inline and b) used ~600 times.
It has the following code inside
              ...
      ptr = ng->ptr[id - 1];
              ...
"id" is never compile time constant so compiler is forced to subtract 1. And those decrements or LEA [r32 - 1] instructions add up.
We also start id'ing from 1 to catch bugs where pernet sybsystem id is not initialized and 0. This is quite pointless idea (nothing will work or immediate interference with first registered subsystem) in general but it hints what needs to be done for code size reduction.
Namely, overlaying allocation of pointer array and fixed part of structure in the beginning and using usual base-0 addressing.
Ids are just cookies, their exact values do not matter, so lets start with 3 on x86_64.
...
Quoted 10 lines
struct net_generic {
include/net/netns/generic.h +3 -6
-     struct {
-             unsigned int len;
-             struct rcu_head rcu;
-     } s;
-
-     void *ptr[0];
+     union {
+             struct {
+                     unsigned int len;
Quoted 8 lines
include/net/netns/generic.h line 36
Quoted 6 lines
include/net/netns/generic.h +5 -0
+                     struct rcu_head rcu;
+             } s;
+
+             void *ptr[0];
+     };
 };
That union is an accident waiting to happen.
I kind of disagree. Module authors should not be given matches, but it is hard to screw up if net_generic() is all you're given.
Quoted 4 lines
What might work is to offset the Ids by
(offsetof(struct net_generic, ptr)/sizeof (void *)) instead of by 1. The subtract from the offset will then counter the structure offset
- which is what you are trying to achieve.
If you suggest this layout
struct net_generic {
        struct {
        } s;
        void *ptr[0];
};
then is it not optimal because offset of "ptr" needs to be somewhere in code either in some LEA or imm8 of the final MOV which is 1 byte more bloaty.
Here is test program
struct ng1 {
        union {
                struct {
                        unsigned int len;
                } s;
                void *ptr[0];
        };
};
struct ng2 {
        struct {
                unsigned int len;
        } s;
        void *ptr[0];
};
struct net {
        int x;
        struct ng1 *gen1;
        struct ng2 *gen2;
};
void *ng1(const struct net *net, unsigned int id)
{
        return net->gen1->ptr[id];
}
void *ng2(const struct net *net, unsigned int id)
{
        return net->gen2->ptr[id];
}
0000000000000000 <ng1>:
   0:   48 8b 47 08             mov    rax,QWORD PTR [rdi+0x8]
   4:   89 f6                   mov    esi,esi
   6:   48 8b 04 f0             mov    rax,QWORD PTR [rax+rsi*8]
   a:   c3                      ret

Quoted 8 lines

Quoted 5 lines
0000000000000010 <ng2>:
  10:   48 8b 47 10             mov    rax,QWORD PTR [rdi+0x10]
  14:   89 f6                   mov    esi,esi
  16:   48 8b 44 f0 [[[08]]]          mov    rax,QWORD PTR [rax+rsi*8+0x8]
  1b:   c3                      ret
On x86 that will make ~0 difference since the offset (in that sequence) doesn't require an extra instruction.

Well, the point of the patch is to save .text, so might as well save as much as possible. Any form other than "ptr[id]" is going
to be either bigger or bigger and slower and "ptr" should be the first field.

Quoted 9 lines

However if you offset the 'id' values so that only values 2 up are valid the code becomes:
        return net->gen2->ptr[id - 2];
which will be exactly the same code as:
        return net->gen1->ptr[id];
but it is much more obvious that 'id' values must be >= 2.
The '2' should be generated from the structure offset, but with my method is doesn't actually matter if it is wrong.

David Laight

2016-12-13 14:43 UTC #5 lore raw

From: Alexey Dobriyan

Quoted 1 line

Sent: 13 December 2016 14:23

...

Quoted 3 lines

Well, the point of the patch is to save .text, so might as well save as much as possible. Any form other than "ptr[id]" is going
to be either bigger or bigger and slower and "ptr" should be the first field.

You've not read and understood the next bit:

Quoted 9 lines

Quoted 9 lines
However if you offset the 'id' values so that only values 2 up are valid the code becomes:
        return net->gen2->ptr[id - 2];
which will be exactly the same code as:
        return net->gen1->ptr[id];
but it is much more obvious that 'id' values must be >= 2.
The '2' should be generated from the structure offset, but with my method is doesn't actually matter if it is wrong.

If you have foo->bar[id - const] then the compiler has to add the offset of 'bar' and subtract for 'const'.
If the numbers match no add or subtract is needed.

It is much cleaner to do this by explicitly removing the offset on the accesses than using a union.

David

Alexey Dobriyan

author

2016-12-14 13:19 UTC #6 lore raw

Quoted 19 lines · David Laight

From: Alexey Dobriyan
Quoted 1 line
Sent: 13 December 2016 14:23
...
Quoted 3 lines
Well, the point of the patch is to save .text, so might as well save as much as possible. Any form other than "ptr[id]" is going
to be either bigger or bigger and slower and "ptr" should be the first field.
You've not read and understood the next bit:
Quoted 9 lines
Quoted 9 lines
However if you offset the 'id' values so that only values 2 up are valid the code becomes:
        return net->gen2->ptr[id - 2];
which will be exactly the same code as:
        return net->gen1->ptr[id];
but it is much more obvious that 'id' values must be >= 2.
The '2' should be generated from the structure offset, but with my method is doesn't actually matter if it is wrong.

Quoted 6 lines

If you have foo->bar[id - const] then the compiler has to add the offset of 'bar' and subtract for 'const'.
If the numbers match no add or subtract is needed.
It is much cleaner to do this by explicitly removing the offset on the accesses than using a union.

Surprisingly, the trick only works if array index is cast to "unsigned long" before subtracting.

Code becomes

    ...
    ptr = ng->ptr[(unsigned long)id - 3];
    ...

I'll post a patch when net-next reopens.

David Laight

2016-12-14 14:42 UTC #7 lore raw

From: Alexey Dobriyan

Quoted 1 line

Sent: 14 December 2016 13:20

...

Quoted 7 lines

Quoted 6 lines
If you have foo->bar[id - const] then the compiler has to add the offset of 'bar' and subtract for 'const'.
If the numbers match no add or subtract is needed.
It is much cleaner to do this by explicitly removing the offset on the accesses than using a union.

Quoted 8 lines

Surprisingly, the trick only works if array index is cast to "unsigned long" before subtracting.
Code becomes
    ...
    ptr = ng->ptr[(unsigned long)id - 3];
    ...

The compiler may also be able to optimise it away if 'id' is 'int' rather than 'unsigned int'.

Oh, if you need casts like that use an accessor function.

David