1. 09 Sep, 2016 6 commits
    • Daniel Borkmann's avatar
      bpf: fix range propagation on direct packet access · 2d2be8ca
      Daniel Borkmann authored
      LLVM can generate code that tests for direct packet access via
      skb->data/data_end in a way that currently gets rejected by the
      verifier, example:
      
        [...]
         7: (61) r3 = *(u32 *)(r6 +80)
         8: (61) r9 = *(u32 *)(r6 +76)
         9: (bf) r2 = r9
        10: (07) r2 += 54
        11: (3d) if r3 >= r2 goto pc+12
         R1=inv R2=pkt(id=0,off=54,r=0) R3=pkt_end R4=inv R6=ctx
         R9=pkt(id=0,off=0,r=0) R10=fp
        12: (18) r4 = 0xffffff7a
        14: (05) goto pc+430
        [...]
      
        from 11 to 24: R1=inv R2=pkt(id=0,off=54,r=0) R3=pkt_end R4=inv
                       R6=ctx R9=pkt(id=0,off=0,r=0) R10=fp
        24: (7b) *(u64 *)(r10 -40) = r1
        25: (b7) r1 = 0
        26: (63) *(u32 *)(r6 +56) = r1
        27: (b7) r2 = 40
        28: (71) r8 = *(u8 *)(r9 +20)
        invalid access to packet, off=20 size=1, R9(id=0,off=0,r=0)
      
      The reason why this gets rejected despite a proper test is that we
      currently call find_good_pkt_pointers() only in case where we detect
      tests like rX > pkt_end, where rX is of type pkt(id=Y,off=Z,r=0) and
      derived, for example, from a register of type pkt(id=Y,off=0,r=0)
      pointing to skb->data. find_good_pkt_pointers() then fills the range
      in the current branch to pkt(id=Y,off=0,r=Z) on success.
      
      For above case, we need to extend that to recognize pkt_end >= rX
      pattern and mark the other branch that is taken on success with the
      appropriate pkt(id=Y,off=0,r=Z) type via find_good_pkt_pointers().
      Since eBPF operates on BPF_JGT (>) and BPF_JGE (>=), these are the
      only two practical options to test for from what LLVM could have
      generated, since there's no such thing as BPF_JLT (<) or BPF_JLE (<=)
      that we would need to take into account as well.
      
      After the fix:
      
        [...]
         7: (61) r3 = *(u32 *)(r6 +80)
         8: (61) r9 = *(u32 *)(r6 +76)
         9: (bf) r2 = r9
        10: (07) r2 += 54
        11: (3d) if r3 >= r2 goto pc+12
         R1=inv R2=pkt(id=0,off=54,r=0) R3=pkt_end R4=inv R6=ctx
         R9=pkt(id=0,off=0,r=0) R10=fp
        12: (18) r4 = 0xffffff7a
        14: (05) goto pc+430
        [...]
      
        from 11 to 24: R1=inv R2=pkt(id=0,off=54,r=54) R3=pkt_end R4=inv
                       R6=ctx R9=pkt(id=0,off=0,r=54) R10=fp
        24: (7b) *(u64 *)(r10 -40) = r1
        25: (b7) r1 = 0
        26: (63) *(u32 *)(r6 +56) = r1
        27: (b7) r2 = 40
        28: (71) r8 = *(u8 *)(r9 +20)
        29: (bf) r1 = r8
        30: (25) if r8 > 0x3c goto pc+47
         R1=inv56 R2=imm40 R3=pkt_end R4=inv R6=ctx R8=inv56
         R9=pkt(id=0,off=0,r=54) R10=fp
        31: (b7) r1 = 1
        [...]
      
      Verifier test cases are also added in this work, one that demonstrates
      the mentioned example here and one that tries a bad packet access for
      the current/fall-through branch (the one with types pkt(id=X,off=Y,r=0),
      pkt(id=X,off=0,r=0)), then a case with good and bad accesses, and two
      with both test variants (>, >=).
      
      Fixes: 969bf05e ("bpf: direct packet access")
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      2d2be8ca
    • Yaogong Wang's avatar
      tcp: use an RB tree for ooo receive queue · 9f5afeae
      Yaogong Wang authored
      Over the years, TCP BDP has increased by several orders of magnitude,
      and some people are considering to reach the 2 Gbytes limit.
      
      Even with current window scale limit of 14, ~1 Gbytes maps to ~740,000
      MSS.
      
      In presence of packet losses (or reorders), TCP stores incoming packets
      into an out of order queue, and number of skbs sitting there waiting for
      the missing packets to be received can be in the 10^5 range.
      
      Most packets are appended to the tail of this queue, and when
      packets can finally be transferred to receive queue, we scan the queue
      from its head.
      
      However, in presence of heavy losses, we might have to find an arbitrary
      point in this queue, involving a linear scan for every incoming packet,
      throwing away cpu caches.
      
      This patch converts it to a RB tree, to get bounded latencies.
      
      Yaogong wrote a preliminary patch about 2 years ago.
      Eric did the rebase, added ofo_last_skb cache, polishing and tests.
      
      Tested with network dropping between 1 and 10 % packets, with good
      success (about 30 % increase of throughput in stress tests)
      
      Next step would be to also use an RB tree for the write queue at sender
      side ;)
      Signed-off-by: default avatarYaogong Wang <wygivan@google.com>
      Signed-off-by: default avatarEric Dumazet <edumazet@google.com>
      Cc: Yuchung Cheng <ycheng@google.com>
      Cc: Neal Cardwell <ncardwell@google.com>
      Cc: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
      Acked-By: default avatarIlpo Järvinen <ilpo.jarvinen@helsinki.fi>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      9f5afeae
    • David S. Miller's avatar
      Merge branch 'ovs-802.1ad' · 3b61075b
      David S. Miller authored
      Eric Garver says:
      
      ====================
      openvswitch: add 802.1ad support
      
      This series adds 802.1ad support to openvswitch. It is a continuation of the
      work originally started by Thomas F Herbert - hence the large rev number.
      
      The extra VLAN is implemented by using an additional level of the
      OVS_KEY_ATTR_ENCAP netlink attribute.
      In OVS flow speak, this looks like
      
         eth_type(0x88a8),vlan(vid=100),encap(eth_type(0x8100), vlan(vid=200),
                                              encap(eth_type(0x0800), ...))
      
      The userspace counterpart has also seen recent activity on the ovs-dev mailing
      lists. There are some new 802.1ad OVS tests being added - also on the ovs-dev
      list. This patch series has been tested using the most recent version of
      userspace (v3) and tests (v2).
      
      v22 changes:
        - merge patch 4 into patch 3
        - fix checkpatch.pl errors
          - Still some 80 char warnings for long string literals
        - refresh pointer after pskb_may_pull()
        - refactor vlan nlattr parsing to remove some double checks
        - introduce ovs_nla_put_vlan()
        - move triple VLAN check to after ethertype serialization
        - WARN_ON_ONCE() on triple VLAN and unexpected encap values
      
      v21 changes:
        - Fix (and simplify) netlink attribute parsing
        - re-add handling of truncated VLAN tags
        - fix if/else dangling assignment in {push,pop}_vlan()
        - simplify parse_vlan()
      ====================
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      3b61075b
    • Eric Garver's avatar
      openvswitch: 802.1AD Flow handling, actions, vlan parsing, netlink attributes · 018c1dda
      Eric Garver authored
      Add support for 802.1ad including the ability to push and pop double
      tagged vlans. Add support for 802.1ad to netlink parsing and flow
      conversion. Uses double nested encap attributes to represent double
      tagged vlan. Inner TPID encoded along with ctci in nested attributes.
      
      This is based on Thomas F Herbert's original v20 patch. I made some
      small clean ups and bug fixes.
      Signed-off-by: default avatarThomas F Herbert <thomasfherbert@gmail.com>
      Signed-off-by: default avatarEric Garver <e@erig.me>
      Acked-by: default avatarPravin B Shelar <pshelar@ovn.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      018c1dda
    • Eric Garver's avatar
      vlan: Check for vlan ethernet types for 8021.q or 802.1ad · fe19c4f9
      Eric Garver authored
      This is to simplify using double tagged vlans. This function allows all
      valid vlan ethertypes to be checked in a single function call.
      Also replace some instances that check for both ETH_P_8021Q and
      ETH_P_8021AD.
      
      Patch based on one originally by Thomas F Herbert.
      Signed-off-by: default avatarThomas F Herbert <thomasfherbert@gmail.com>
      Signed-off-by: default avatarEric Garver <e@erig.me>
      Acked-by: default avatarPravin B Shelar <pshelar@ovn.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      fe19c4f9
    • Thomas F Herbert's avatar
      openvswitch: 802.1ad uapi changes. · 8c146bb9
      Thomas F Herbert authored
      openvswitch: Add support for 8021.AD
      
      Change the description of the VLAN tpid field.
      Signed-off-by: default avatarThomas F Herbert <thomasfherbert@gmail.com>
      Acked-by: default avatarPravin B Shelar <pshelar@ovn.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      8c146bb9
  2. 08 Sep, 2016 22 commits
  3. 07 Sep, 2016 10 commits
    • David Howells's avatar
      rxrpc: Add tracepoint for working out where aborts happen · 5a42976d
      David Howells authored
      Add a tracepoint for working out where local aborts happen.  Each
      tracepoint call is labelled with a 3-letter code so that they can be
      distinguished - and the DATA sequence number is added too where available.
      
      rxrpc_kernel_abort_call() also takes a 3-letter code so that AFS can
      indicate the circumstances when it aborts a call.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      5a42976d
    • David Howells's avatar
      rxrpc: Fix returns of call completion helpers · e8d6bbb0
      David Howells authored
      rxrpc_set_call_completion() returns bool, not int, so the ret variable
      should match this.
      
      rxrpc_call_completed() and __rxrpc_call_completed() should return the value
      of rxrpc_set_call_completion().
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      e8d6bbb0
    • David Howells's avatar
      rxrpc: Calls shouldn't hold socket refs · 8d94aa38
      David Howells authored
      rxrpc calls shouldn't hold refs on the sock struct.  This was done so that
      the socket wouldn't go away whilst the call was in progress, such that the
      call could reach the socket's queues.
      
      However, we can mark the socket as requiring an RCU release and rely on the
      RCU read lock.
      
      To make this work, we do:
      
       (1) rxrpc_release_call() removes the call's call user ID.  This is now
           only called from socket operations and not from the call processor:
      
      	rxrpc_accept_call() / rxrpc_kernel_accept_call()
      	rxrpc_reject_call() / rxrpc_kernel_reject_call()
      	rxrpc_kernel_end_call()
      	rxrpc_release_calls_on_socket()
      	rxrpc_recvmsg()
      
           Though it is also called in the cleanup path of
           rxrpc_accept_incoming_call() before we assign a user ID.
      
       (2) Pass the socket pointer into rxrpc_release_call() rather than getting
           it from the call so that we can get rid of uninitialised calls.
      
       (3) Fix call processor queueing to pass a ref to the work queue and to
           release that ref at the end of the processor function (or to pass it
           back to the work queue if we have to requeue).
      
       (4) Skip out of the call processor function asap if the call is complete
           and don't requeue it if the call is complete.
      
       (5) Clean up the call immediately that the refcount reaches 0 rather than
           trying to defer it.  Actual deallocation is deferred to RCU, however.
      
       (6) Don't hold socket refs for allocated calls.
      
       (7) Use the RCU read lock when queueing a message on a socket and treat
           the call's socket pointer according to RCU rules and check it for
           NULL.
      
           We also need to use the RCU read lock when viewing a call through
           procfs.
      
       (8) Transmit the final ACK/ABORT to a client call in rxrpc_release_call()
           if this hasn't been done yet so that we can then disconnect the call.
           Once the call is disconnected, it won't have any access to the
           connection struct and the UDP socket for the call work processor to be
           able to send the ACK.  Terminal retransmission will be handled by the
           connection processor.
      
       (9) Release all calls immediately on the closing of a socket rather than
           trying to defer this.  Incomplete calls will be aborted.
      
      The call refcount model is much simplified.  Refs are held on the call by:
      
       (1) A socket's user ID tree.
      
       (2) A socket's incoming call secureq and acceptq.
      
       (3) A kernel service that has a call in progress.
      
       (4) A queued call work processor.  We have to take care to put any call
           that we failed to queue.
      
       (5) sk_buffs on a socket's receive queue.  A future patch will get rid of
           this.
      
      Whilst we're at it, we can do:
      
       (1) Get rid of the RXRPC_CALL_EV_RELEASE event.  Release is now done
           entirely from the socket routines and never from the call's processor.
      
       (2) Get rid of the RXRPC_CALL_DEAD state.  Calls now end in the
           RXRPC_CALL_COMPLETE state.
      
       (3) Get rid of the rxrpc_call::destroyer work item.  Calls are now torn
           down when their refcount reaches 0 and then handed over to RCU for
           final cleanup.
      
       (4) Get rid of the rxrpc_call::deadspan timer.  Calls are cleaned up
           immediately they're finished with and don't hang around.
           Post-completion retransmission is handled by the connection processor
           once the call is disconnected.
      
       (5) Get rid of the dead call expiry setting as there's no longer a timer
           to set.
      
       (6) rxrpc_destroy_all_calls() can just check that the call list is empty.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      8d94aa38
    • David Howells's avatar
      rxrpc: Use rxrpc_is_service_call() rather than rxrpc_conn_is_service() · 6543ac52
      David Howells authored
      Use rxrpc_is_service_call() rather than rxrpc_conn_is_service() if the call
      is available just in case call->conn is NULL.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      6543ac52
    • David Howells's avatar
      rxrpc: Pass the connection pointer to rxrpc_post_packet_to_call() · 8b7fac50
      David Howells authored
      Pass the connection pointer to rxrpc_post_packet_to_call() as the call
      might get disconnected whilst we're looking at it, but the connection
      pointer determined by rxrpc_data_read() is guaranteed by RCU for the
      duration of the call.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      8b7fac50
    • David Howells's avatar
      rxrpc: Cache the security index in the rxrpc_call struct · 278ac0cd
      David Howells authored
      Cache the security index in the rxrpc_call struct so that we can get at it
      even when the call has been disconnected and the connection pointer
      cleared.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      278ac0cd
    • David Howells's avatar
      rxrpc: Use call->peer rather than call->conn->params.peer · f4fdb352
      David Howells authored
      Use call->peer rather than call->conn->params.peer to avoid the possibility
      of call->conn being NULL and, whilst we're at it, check it for NULL before we
      access it.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      f4fdb352
    • David Howells's avatar
      rxrpc: Improve the call tracking tracepoint · fff72429
      David Howells authored
      Improve the call tracking tracepoint by showing more differentiation
      between some of the put and get events, including:
      
        (1) Getting and putting refs for the socket call user ID tree.
      
        (2) Getting and putting refs for queueing and failing to queue the call
            processor work item.
      
      Note that these aren't necessarily used in this patch, but will be taken
      advantage of in future patches.
      
      An enum is added for the event subtype numbers rather than coding them
      directly as decimal numbers and a table of 3-letter strings is provided
      rather than a sequence of ?: operators.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      fff72429
    • David Howells's avatar
      rxrpc: Delete unused rxrpc_kernel_free_skb() · e796cb41
      David Howells authored
      Delete rxrpc_kernel_free_skb() as it's unused.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      e796cb41
    • David Howells's avatar
      rxrpc: Whitespace cleanup · 71a17de3
      David Howells authored
      Remove some whitespace.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      71a17de3
  4. 06 Sep, 2016 2 commits