Skip to contentSkip to conversation

tc filter insertion rate degradation

DISCUSSION Vlad Buslov 4 participants 6 messages Jan 21, 2019 – Jan 29, 2019

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

Hi Eric,

I've been investigating significant tc filter insertion rate degradation and it seems it is caused by your commit 001c96db0181 ("net: align gnet_stats_basic_cpu struct"). With this commit insertion rate is reduced from ~65k rules/sec to ~43k rules/sec when inserting 1m rules from file in tc batch mode on my machine.

Tc perf profile indicates that pcpu allocator now consumes 2x CPU:

1) Before:

Samples: 63K of event 'cycles:ppp', Event count (approx.): 48796480071

  Children      Self  Co  Shared Object     Symbol
+   21.19%     3.38%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+    3.45%     0.25%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

2) After:

Samples1: 92K of event 'cycles:ppp', Event count (approx.): 71446806550

  Children      Self  Co  Shared Object     Symbol
+   44.67%     3.99%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+   19.25%     0.22%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

It seems that it takes much more work for pcpu allocator to perform allocation with new stricter alignment requirements. Not sure if it is expected behavior or not in this case.

Regards,
Vlad

#1 lore raw
Quoted 25 lines · Vlad Buslov

Hi Eric,

I've been investigating significant tc filter insertion rate degradation and it seems it is caused by your commit 001c96db0181 ("net: align gnet_stats_basic_cpu struct"). With this commit insertion rate is reduced from ~65k rules/sec to ~43k rules/sec when inserting 1m rules from file in tc batch mode on my machine.

Tc perf profile indicates that pcpu allocator now consumes 2x CPU:

1) Before:

Samples: 63K of event 'cycles:ppp', Event count (approx.): 48796480071
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   21.19%     3.38%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+    3.45%     0.25%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

2) After:

Samples1: 92K of event 'cycles:ppp', Event count (approx.): 71446806550
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   44.67%     3.99%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+   19.25%     0.22%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area
Quoted 6 lines

It seems that it takes much more work for pcpu allocator to perform allocation with new stricter alignment requirements. Not sure if it is expected behavior or not in this case.

Regards,
Vlad

Hi Vlad

I guess this is more a question for per-cpu allocator experts / maintainers ?

16-bytes alignment for 16-bytes objects sound quite reasonable [1]

It also means that if your workload is mostly being able to setup / dismantle tc filters,
instead of really using them, you might go back to atomics instead of expensive per cpu storage.

(Ie optimize control path instead of data path)

Thanks !

[1] We even might make this generic as in :

mm/percpu.c +0 -0
index 27a25bf1275b7233d28cc0b126256e0f8a2b7f4f..bbf4ad37ae893fc1da5523889dd147f046852cc7

100644

mm/percpu.c +0 -0
@@ -1362,7 +1362,11 @@ static void __percpu *pcpu_alloc(size_t size,

size_t align, bool reserved,

         */
        if (unlikely(align < PCPU_MIN_ALLOC_SIZE))
                align = PCPU_MIN_ALLOC_SIZE;

-
+ while (align < L1_CACHE_BYTES && (align << 1) <= size) {
+ if (size % (align << 1))
+ break;
+ align <<= 1;
+ }

        size = ALIGN(size, PCPU_MIN_ALLOC_SIZE);
        bits = size >> PCPU_MIN_ALLOC_SHIFT;
        bit_align = align >> PCPU_MIN_ALLOC_SHIFT;
maintainer
#2 lore raw

Hello,

Quoted 7 lines · Eric Dumazet
Quoted 7 lines

1) Before:

Samples: 63K of event 'cycles:ppp', Event count (approx.): 48796480071
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   21.19%     3.38%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+    3.45%     0.25%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area
Quoted 6 lines

Review

Quoted 6 lines

2) After:

Samples1: 92K of event 'cycles:ppp', Event count (approx.): 71446806550
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   44.67%     3.99%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+   19.25%     0.22%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

The allocator hint only remembers the max available size per chunk but not the alignment, so depending on the allocation pattern, alignment requirement change can lead to way more scanning per alloc attempt. Shouldn't be too difficult to improve tho.

Quoted 21 lines

I guess this is more a question for per-cpu allocator experts / maintainers ?

16-bytes alignment for 16-bytes objects sound quite reasonable [1]

It also means that if your workload is mostly being able to setup / dismantle tc filters,
instead of really using them, you might go back to atomics instead of expensive per cpu storage.

(Ie optimize control path instead of data path)

Thanks !

[1] We even might make this generic as in :

mm/percpu.c +0 -0
index 27a25bf1275b7233d28cc0b126256e0f8a2b7f4f..bbf4ad37ae893fc1da5523889dd147f046852cc7

100644

mm/percpu.c static void __percpu *pcpu_alloc(size_t size, · line 1370

Quoted 10 lines
mm/percpu.c +5 -1
@@ -1362,7 +1362,11 @@ static void __percpu *pcpu_alloc(size_t size,
 size_t align, bool reserved,
         */
        if (unlikely(align < PCPU_MIN_ALLOC_SIZE))
                align = PCPU_MIN_ALLOC_SIZE;
-
+       while (align < L1_CACHE_BYTES && (align << 1) <= size) {
+               if (size % (align << 1))
+                       break;
+               align <<= 1;
+       }

Percpu storage is expensive and cache line sharing tends to be less of a problem (cuz they're per-cpu), so it is useful to support custom alignments for tighter packing.

Thanks.

Signature · 1 line
tejun
#3 lore raw
Quoted 8 lines · Tejun Heo

Hello,

Percpu storage is expensive and cache line sharing tends to be less of a problem (cuz they're per-cpu), so it is useful to support custom alignments for tighter packing.

We have BPF percpu maps of two 8-byte counters (packets and bytes counter), with millions of slots.

We update the pair for every packet sent on the hosts.

BPF uses an alignment of 8 (that can not be changed/tuned, at least all call sites from kernel/bpf/hashtab.c )

If we are lucky, all these pairs are allocated using a single cache line. But when we are not lucky, 25% of the pairs are crossing a cache line, reducing performance under DDOS.

Using a nicer alignment in our case does not consume more ram, and we did not notice
extra cost of per-cpu allocations because we keep them in the slow path (control path)

maintainer
#4 lore raw
In reply to Eric Dumazet

Hi Vlad and Eric,

Quoted 26 lines · Eric Dumazet
Quoted 25 lines · Vlad Buslov

Hi Eric,

I've been investigating significant tc filter insertion rate degradation and it seems it is caused by your commit 001c96db0181 ("net: align gnet_stats_basic_cpu struct"). With this commit insertion rate is reduced from ~65k rules/sec to ~43k rules/sec when inserting 1m rules from file in tc batch mode on my machine.

Tc perf profile indicates that pcpu allocator now consumes 2x CPU:

1) Before:

Samples: 63K of event 'cycles:ppp', Event count (approx.): 48796480071
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   21.19%     3.38%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+    3.45%     0.25%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

2) After:

Samples1: 92K of event 'cycles:ppp', Event count (approx.): 71446806550
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   44.67%     3.99%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+   19.25%     0.22%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area
Quoted 6 lines
Quoted 6 lines

It seems that it takes much more work for pcpu allocator to perform allocation with new stricter alignment requirements. Not sure if it is expected behavior or not in this case.

Regards,
Vlad

Would you mind sharing a little more information with me:
1) output before and after a run of /sys/kernel/debug/percpu_stats
2) a full perf output
3) a reproducer

I'm a little surprised we're spending time in pcpu_alloc_area(), but it might be due to constantly breaking the hint as an immediate guess.

Quoted 7 lines

Hi Vlad

I guess this is more a question for per-cpu allocator experts / maintainers ?

16-bytes alignment for 16-bytes objects sound quite reasonable [1]

The alignment request seems reasonable. But as Tejun mentioned in a reply to this, the overhead of forced alignment would be both in percpu memory itself and in allocation time due to the stricter requirement.

Thanks,
Dennis

#5 lore raw
Quoted 33 lines · Dennis Zhou

Hi Vlad and Eric,

Quoted 30 lines · Eric Dumazet
Quoted 29 lines · Vlad Buslov

Hi Eric,

I've been investigating significant tc filter insertion rate degradation and it seems it is caused by your commit 001c96db0181 ("net: align gnet_stats_basic_cpu struct"). With this commit insertion rate is reduced from ~65k rules/sec to ~43k rules/sec when inserting 1m rules from file in tc batch mode on my machine.

Tc perf profile indicates that pcpu allocator now consumes 2x CPU:

1) Before:

Samples: 63K of event 'cycles:ppp', Event count (approx.): 48796480071
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   21.19%     3.38%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+    3.45%     0.25%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

2) After:

Samples1: 92K of event 'cycles:ppp', Event count (approx.): 71446806550
Children Self Co Shared Object Symbol

(quoted diff) +2 -0
+   44.67%     3.99%  tc  [kernel.vmlinux]  [k] pcpu_alloc
+   19.25%     0.22%  tc  [kernel.vmlinux]  [k] pcpu_alloc_area

It seems that it takes much more work for pcpu allocator to perform allocation with new stricter alignment requirements. Not sure if it is expected behavior or not in this case.

Quoted 5 lines
Quoted 2 lines
Quoted 2 lines

Regards,
Vlad

Would you mind sharing a little more information with me:
1) output before and after a run of /sys/kernel/debug/percpu_stats

Hi Dennis,

Some of these files are quite large, so I put them to my Dropbox.

Output before:

Percpu Memory Statistics
Allocation Info:
----------------------------------------

  unit_size           :       262144
  static_size         :       139160
  reserved_size       :         8192
  dyn_size            :        28776
  atom_size           :      2097152
  alloc_size          :      2097152

Global Stats:
----------------------------------------

  nr_alloc            :         3343
  nr_dealloc          :          752
  nr_cur_alloc        :         2591
  nr_max_alloc        :         2598
  nr_chunks           :            3
  nr_max_chunks       :            3
  min_alloc_size      :            4
  max_alloc_size      :         8208
  empty_pop_pages     :            3

Per Chunk Stats:
----------------------------------------
Chunk: <- Reserved Chunk

  nr_alloc            :            5
  max_alloc_size      :          320
  empty_pop_pages     :            0
  first_bit           :         1002
  free_bytes          :         7448
  contig_bytes        :         7424
  sum_frag            :           24
  max_frag            :           24
  cur_min_alloc       :           16
  cur_med_alloc       :           64
  cur_max_alloc       :          320

Chunk: <- First Chunk

  nr_alloc            :          479
  max_alloc_size      :         8208
  empty_pop_pages     :            0
  first_bit           :         8192
  free_bytes          :            0
  contig_bytes        :            0
  sum_frag            :            0
  max_frag            :            0
  cur_min_alloc       :            4
  cur_med_alloc       :           24
  cur_max_alloc       :         8208

Chunk:

  nr_alloc            :         1925
  max_alloc_size      :         8208
  empty_pop_pages     :            0
  first_bit           :        63102
  free_bytes          :          852
  contig_bytes        :           12
  sum_frag            :          852
  max_frag            :           12
  cur_min_alloc       :            4
  cur_med_alloc       :            8
  cur_max_alloc       :         8208

Chunk:

  nr_alloc            :          182
  max_alloc_size      :          936
  empty_pop_pages     :            3
  first_bit           :           21
  free_bytes          :       256452
  contig_bytes        :       255120
  sum_frag            :         1332
  max_frag            :          368
  cur_min_alloc       :            8
  cur_med_alloc       :           20
  cur_max_alloc       :          320

After: https://www.dropbox.com/s/unyzhx4vgo2x30e/stats_after?dl=0

Quoted 1 line

2) a full perf output

https://www.dropbox.com/s/isfcxca3npn5slx/perf.data?dl=0

Quoted 1 line

3) a reproducer

$ sudo tc -b add.0

Example batch file: https://www.dropbox.com/s/ey7cbl5nwu5p0tg/add.0?dl=0

Thanks,
Vlad