1. 24 May, 2019 17 commits
  2. 23 May, 2019 23 commits
    • Daniel Borkmann's avatar
      Merge branch 'bpf-explored-states' · 5762a20b
      Daniel Borkmann authored
      Alexei Starovoitov says:
      
      ====================
      Convert explored_states array into hash table and use simple hash
      to reduce verifier peak memory consumption for programs with bpf2bpf
      calls. More details in patch 3.
      
      v1->v2: fixed Jakub's small nit in patch 1
      ====================
      Acked-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      5762a20b
    • Alexei Starovoitov's avatar
      bpf: convert explored_states to hash table · dc2a4ebc
      Alexei Starovoitov authored
      All prune points inside a callee bpf function most likely will have
      different callsites. For example, if function foo() is called from
      two callsites the half of explored states in all prune points in foo()
      will be useless for subsequent walking of one of those callsites.
      Fortunately explored_states pruning heuristics keeps the number of states
      per prune point small, but walking these states is still a waste of cpu
      time when the callsite of the current state is different from the callsite
      of the explored state.
      
      To improve pruning logic convert explored_states into hash table and
      use simple insn_idx ^ callsite hash to select hash bucket.
      This optimization has no effect on programs without bpf2bpf calls
      and drastically improves programs with calls.
      In the later case it reduces total memory consumption in 1M scale tests
      by almost 3 times (peak_states drops from 5752 to 2016).
      
      Care should be taken when comparing the states for equivalency.
      Since the same hash bucket can now contain states with different indices
      the insn_idx has to be part of verifier_state and compared.
      
      Different hash table sizes and different hash functions were explored,
      but the results were not significantly better vs this patch.
      They can be improved in the future.
      
      Hit/miss heuristic is not counting index miscompare as a miss.
      Otherwise verifier stats become unstable when experimenting
      with different hash functions.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      dc2a4ebc
    • Alexei Starovoitov's avatar
      bpf: split explored_states · a8f500af
      Alexei Starovoitov authored
      split explored_states into prune_point boolean mark
      and link list of explored states.
      This removes STATE_LIST_MARK hack and allows marks to be separate from states.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      a8f500af
    • Alexei Starovoitov's avatar
      bpf: cleanup explored_states · 5d839021
      Alexei Starovoitov authored
      clean up explored_states to prep for introduction of hashtable
      No functional changes.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      5d839021
    • Daniel Borkmann's avatar
      Merge branch 'bpf-jmp-seq-limit' · 29c677c8
      Daniel Borkmann authored
      Alexei Starovoitov says:
      
      ====================
      Patch 1 - jmp sequence limit
      Patch 2 - improve existing tests
      Patch 3 - add pyperf-based realistic bpf program that takes
                advantage of higher limit and use it as a stress test
      
      v1->v2: fixed nit in patch 3. added Andrii's acks
      ====================
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      29c677c8
    • Alexei Starovoitov's avatar
      selftests/bpf: add pyperf scale test · 7c944106
      Alexei Starovoitov authored
      Add a snippet of pyperf bpf program used to collect python stack traces
      as a scale test for the verifier.
      
      At 189 loop iterations llvm 9.0 starts ignoring '#pragma unroll'
      and generates partially unrolled loop instead.
      Hence use 50, 100, and 180 loop iterations to stress test.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      7c944106
    • Alexei Starovoitov's avatar
      selftests/bpf: adjust verifier scale test · 7c0c6095
      Alexei Starovoitov authored
      Adjust scale tests to check for new jmp sequence limit.
      
      BPF_JGT had to be changed to BPF_JEQ because the verifier was
      too smart. It tracked the known safe range of R0 values
      and pruned the search earlier before hitting exact 8192 limit.
      bpf_semi_rand_get() was too (un)?lucky.
      
      k = 0; was missing in bpf_fill_scale2.
      It was testing a bit shorter sequence of jumps than intended.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      7c0c6095
    • Alexei Starovoitov's avatar
      bpf: bump jmp sequence limit · b285fcb7
      Alexei Starovoitov authored
      The limit of 1024 subsequent jumps was causing otherwise valid
      programs to be rejected. Bump it to 8192 and make the error more verbose.
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      b285fcb7
    • Andrii Nakryiko's avatar
      libbpf: emit diff of mismatched public API, if any · 9efc7794
      Andrii Nakryiko authored
      It's easy to have a mismatch of "intended to be public" vs really
      exposed API functions. While Makefile does check for this mismatch, if
      it actually occurs it's not trivial to determine which functions are
      accidentally exposed. This patch dumps out a diff showing what's not
      supposed to be exposed facilitating easier fixing.
      Signed-off-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      9efc7794
    • Sunil Muthuswamy's avatar
      hv_sock: perf: loop in send() to maximize bandwidth · 14a1eaa8
      Sunil Muthuswamy authored
      Currently, the hv_sock send() iterates once over the buffer, puts data into
      the VMBUS channel and returns. It doesn't maximize on the case when there
      is a simultaneous reader draining data from the channel. In such a case,
      the send() can maximize the bandwidth (and consequently minimize the cpu
      cycles) by iterating until the channel is found to be full.
      
      Perf data:
      Total Data Transfer: 10GB/iteration
      Single threaded reader/writer, Linux hvsocket writer with Windows hvsocket
      reader
      Packet size: 64KB
      CPU sys time was captured using the 'time' command for the writer to send
      10GB of data.
      'Send Buffer Loop' is with the patch applied.
      The values below are over 10 iterations.
      
      |--------------------------------------------------------|
      |        |        Current        |   Send Buffer Loop    |
      |--------------------------------------------------------|
      |        | Throughput | CPU sys  | Throughput | CPU sys  |
      |        | (MB/s)     | time (s) | (MB/s)     | time (s) |
      |--------------------------------------------------------|
      | Min    |     407    |   7.048  |    401     |  5.958   |
      |--------------------------------------------------------|
      | Max    |     455    |   7.563  |    542     |  6.993   |
      |--------------------------------------------------------|
      | Avg    |     440    |   7.411  |    451     |  6.639   |
      |--------------------------------------------------------|
      | Median |     446    |   7.417  |    447     |  6.761   |
      |--------------------------------------------------------|
      
      Observation:
      1. The avg throughput doesn't really change much with this change for this
      scenario. This is most probably because the bottleneck on throughput is
      somewhere else.
      2. The average system (or kernel) cpu time goes down by 10%+ with this
      change, for the same amount of data transfer.
      Signed-off-by: default avatarSunil Muthuswamy <sunilmut@microsoft.com>
      Reviewed-by: default avatarDexuan Cui <decui@microsoft.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      14a1eaa8
    • Sunil Muthuswamy's avatar
      hv_sock: perf: Allow the socket buffer size options to influence the actual socket buffers · ac383f58
      Sunil Muthuswamy authored
      Currently, the hv_sock buffer size is static and can't scale to the
      bandwidth requirements of the application. This change allows the
      applications to influence the socket buffer sizes using the SO_SNDBUF and
      the SO_RCVBUF socket options.
      
      Few interesting points to note:
      1. Since the VMBUS does not allow a resize operation of the ring size, the
      socket buffer size option should be set prior to establishing the
      connection for it to take effect.
      2. Setting the socket option comes with the cost of that much memory being
      reserved/allocated by the kernel, for the lifetime of the connection.
      
      Perf data:
      Total Data Transfer: 1GB
      Single threaded reader/writer
      Results below are summarized over 10 iterations.
      
      Linux hvsocket writer + Windows hvsocket reader:
      |---------------------------------------------------------------------------------------------|
      |Packet size ->   |      128B       |       1KB       |       4KB       |        64KB         |
      |---------------------------------------------------------------------------------------------|
      |SO_SNDBUF size | |                 Throughput in MB/s (min/max/avg/median):                  |
      |               v |                                                                           |
      |---------------------------------------------------------------------------------------------|
      |      Default    | 109/118/114/116 | 636/774/701/700 | 435/507/480/476 |   410/491/462/470   |
      |      16KB       | 110/116/112/111 | 575/705/662/671 | 749/900/854/869 |   592/824/692/676   |
      |      32KB       | 108/120/115/115 | 703/823/767/772 | 718/878/850/866 | 1593/2124/2000/2085 |
      |      64KB       | 108/119/114/114 | 592/732/683/688 | 805/934/903/911 | 1784/1943/1862/1843 |
      |---------------------------------------------------------------------------------------------|
      
      Windows hvsocket writer + Linux hvsocket reader:
      |---------------------------------------------------------------------------------------------|
      |Packet size ->   |     128B    |      1KB        |          4KB        |        64KB         |
      |---------------------------------------------------------------------------------------------|
      |SO_RCVBUF size | |               Throughput in MB/s (min/max/avg/median):                    |
      |               v |                                                                           |
      |---------------------------------------------------------------------------------------------|
      |      Default    | 69/82/75/73 | 313/343/333/336 |   418/477/446/445   |   659/701/676/678   |
      |      16KB       | 69/83/76/77 | 350/401/375/382 |   506/548/517/516   |   602/624/615/615   |
      |      32KB       | 62/83/73/73 | 471/529/496/494 |   830/1046/935/939  | 944/1180/1070/1100  |
      |      64KB       | 64/70/68/69 | 467/533/501/497 | 1260/1590/1430/1431 | 1605/1819/1670/1660 |
      |---------------------------------------------------------------------------------------------|
      Signed-off-by: default avatarSunil Muthuswamy <sunilmut@microsoft.com>
      Reviewed-by: default avatarDexuan Cui <decui@microsoft.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      ac383f58
    • Eric Dumazet's avatar
      ipv4/igmp: shrink struct ip_sf_list · 0db355d4
      Eric Dumazet authored
      Removing two 4 bytes holes allows to use kmalloc-32
      kmem cache instead of kmalloc-64 on 64bit kernels.
      Signed-off-by: default avatarEric Dumazet <edumazet@google.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      0db355d4
    • David Ahern's avatar
      neighbor: Add tracepoint to __neigh_create · fc651001
      David Ahern authored
      Add tracepoint to __neigh_create to enable debugging of new entries.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      fc651001
    • David Ahern's avatar
      selftests: pmtu: Simplify cleanup and namespace names · a92a0a7b
      David Ahern authored
      The point of the pause-on-fail argument is to leave the setup as is after
      a test fails to allow a user to debug why it failed. Move the cleanup
      after posting the result to the user to make it so.
      
      Random names for the namespaces are not user friendly when trying to
      debug a failure. Make them simpler and more direct for the tests. Run
      cleanup at the beginning to ensure they are cleaned up if they already
      exist.
      
      Remove cleanup_done. There is no harm in doing cleanup twice; just
      ignore any errors related to not existing - which is already done.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a92a0a7b
    • David Ahern's avatar
      selftests: fib-onlink: Make quiet by default · 9b7e94e6
      David Ahern authored
      Add VERBOSE argument to fib-onlink-tests.sh and make output quiet by
      default. Add getopt parsing of inputs and support for -v (verbose) and
      -p (pause on fail).
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      9b7e94e6
    • David Ahern's avatar
      net: Set strict_start_type for routes and rules · 75425657
      David Ahern authored
      New userspace on an older kernel can send unknown and unsupported
      attributes resulting in an incompelete config which is almost
      always wrong for routing (few exceptions are passthrough settings
      like the protocol that installed the route).
      
      Set strict_start_type in the policies for IPv4 and IPv6 routes and
      rules to detect new, unsupported attributes and fail the route add.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      75425657
    • David S. Miller's avatar
      Merge branch 'net-Export-functions-for-nexthop-code' · e38f7cbd
      David S. Miller authored
      David Ahern says:
      
      ====================
      net: Export functions for nexthop code
      
      This set exports ipv4 and ipv6 fib functions for use by the nexthop
      code. It also adds new ones to send route notifications if a nexthop
      configuration changes.
      
      v2
      - repost of patches dropped at the end of the last dev window
        added patch 8 which exports nh_update_mtu since it is inline with
        the other patches
      ====================
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      e38f7cbd
    • David Ahern's avatar
      ipv4: Rename and export nh_update_mtu · 06c77c3e
      David Ahern authored
      Rename nh_update_mtu to fib_nhc_update_mtu and export for use by the
      nexthop code.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      06c77c3e
    • David Ahern's avatar
      ipv4: export fib_info_update_nh_saddr · c3669486
      David Ahern authored
      Add scope as input argument versus relying on fib_info reference in
      fib_nh, and export fib_info_update_nh_saddr.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      c3669486
    • David Ahern's avatar
      ipv4: export fib_flush · 9bd83667
      David Ahern authored
      As nexthops are deleted, fib entries referencing it are marked dead.
      Export fib_flush so those entries can be removed in a timely manner.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      9bd83667
    • David Ahern's avatar
      ipv4: export fib_check_nh · ac1fab2d
      David Ahern authored
      Change fib_check_nh to take net, table and scope as input arguments
      over struct fib_config and export for use by nexthop code.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      ac1fab2d
    • David Ahern's avatar
      ipv4: Add function to send route updates · 1bff1a0c
      David Ahern authored
      Add fib_info_notify_update to walk the fib and send RTM_NEWROUTE
      notifications with NLM_F_REPLACE set for entries linked to a fib_info
      that have nh_updated flag set. This helper will be used by the nexthop
      code to notify userspace of routes that are impacted when a nexthop
      config is updated via replace. The new function and its helper are
      similar to how fib_flush and fib_table_flush work for address delete
      and link down events.
      
      This notification is needed for legacy apps that do not understand
      the new nexthop object. Apps that are nexthop aware can use the
      RTA_NH_ID attribute in the route notification to just ignore it.
      
      In the future this should be wrapped in a sysctl to allow OS'es that
      are fully updated to avoid the notificaton storm.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      1bff1a0c
    • David Ahern's avatar
      ipv6: export function to send route updates · 19a3b7ee
      David Ahern authored
      Add fib6_rt_update to send RTM_NEWROUTE with NLM_F_REPLACE set. This
      helper will be used by the nexthop code to notify userspace of routes
      that are impacted when a nexthop config is updated via replace.
      
      This notification is needed for legacy apps that do not understand
      the new nexthop object. Apps that are nexthop aware can use the
      RTA_NH_ID attribute in the route notification to just ignore it.
      
      In the future this should be wrapped in a sysctl to allow OS'es that
      are fully updated to avoid the notificaton storm.
      Signed-off-by: default avatarDavid Ahern <dsahern@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      19a3b7ee