datapath: Add basic MPLS support to kernel

Allow datapath to recognize and extract MPLS labels into flow keys
and execute actions which push, pop, and set labels on packets.

Based heavily on work by Leo Alterman and Ravi K.

Cc: Ravi K <rkerur@gmail.com>
Cc: Leo Alterman <lalterman@nicira.com>
Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* As suggested by Jarno Rajahalme
  - Rename mpls_bos element of ovs_skb_cb as l2_size as it is set and used
    regardless of if an MPLS stack is present or not. Update the name of
    helper functions and documentation accordingly.
  - Ensure that skb_cb_mpls_bos() never returns NULL
* Correct endieness in eth_p_mpls()

v2.12
* Update skb and network header on MPLS extraction in ovs_flow_extract()
* Use NULL in skb_cb_mpls_bos()
* Add eth_p_mpls helper

v2.11
* No change

v2.10
* No change

v2.9
* datapath: Always update the mpls bos if  vlan_pop is successful

  Regardless of the details of how a successful
  vlan_pop is achieved, the mpls bos needs to be updated.

  Without this fix it has been observed that the following
  results in malformed packets

v2.8
* No change

v2.7
* Rebase

v2.6
* As suggested by Yamahata-san
  - Do not guard against label == 0 for
    OVS_ACTION_ATTR_SET_MPLS in validate_actions().
    A label of 0 is valid
  - Remove comment stupulating that if
    the top_label element of struct sw_flow_key is 0 then
    there is no MPLS label. An MPLS label of 0 is valid
    and the correct check if ethertype is
    ntohs(ETH_TYPE_MPLS) or ntohs(ETH_TYPE_MPLS_MCAST)

v2.5
* No change

v2.4
* No change

v2.3
* s/mpls_stack/mpls_bos/
  This is in keeping with the naming used in the OpenFlow 1.3 specification

v2.2
* Call skb_reset_mac_header() in skb_cb_set_mpls_stack()
  eth_hdr(skb) is non-NULL when called in skb_cb_set_mpls_stack().
* Add a call to skb_cb_set_mpls_stack() in ovs_packet_cmd_execute().
  I apologise that I have mislaid my notes on this but
  it avoids a kernel panic. I can investigate again if necessary.
* Use struct ovs_action_push_mpls instead of
  __be16 to decode OVS_ACTION_ATTR_PUSH_MPLS in validate_actions(). This is
  consistent with the data format for the attribute.
* Indentation fix in skb_cb_mpls_stack(). [cosmetic]

v2.1
* Manual rebase
datapath: Split ovs_flow_extract

Allow repeated extraction of flow from packets

Split the L3 and above portion of ovs_flow_extract() out into
ovs_flow_extract_l3_onwards() and call ovs_flow_extract_l3_onwards()
from ovs_flow_extract().

This is to allow re-extraction of L3 and higher information using
an ethernet type supplied by actions, for example the mpls_pop.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* As suggested by Jarno Rajahalme
  - Update change log to more closely reflect the extent of the
    changes in the patch

v2.12
* Rebase

v2.11
* First post
datapath: Inner And Outer Flows

Allow a flow to be visible in two forms, an outer flow and an inner flow.
This may occur if the actions allow further decoding of a packet to
provide a more fine-grained match. In this case the first-pass
coarse-grained match will hit the outer-flow and the second-pass
fined-grained match will hit the inner-flow.

Inner-flows are not visible to user-space. Rather, they are just an
internal representation to handle the case of actions allowing further
packet decoding. An inner-flow is associated with its outer-flow and
deleted when the outer-flow is deleted. An outer-flow may have more than
one inner-flow but an inner-flow may only have one outer-flow.

For example:

In the case of MPLS, L3 and L4 information may not initially be decoded
from the frame as the ethernet type of the frame is an MPLS type and no
information is known about the type of the inner frame.

However, the type of the inner frame may be provided by an mpls_pop action
in which case L3 and L4 information may be decoded providing a finer
grained match than is otherwise possible.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* Merge "datapath: Allow inner_flows" and
  "datapath: re-lookup a flow if actions allow a more fine grained match"
  and rename the resulting patch "datapath: Inner and Outer Flows".
* As suggested by Jarno Rajahalme
  - Add encap_eth_type to struct sw_flow and use it to store the
    ethernet type supplied by actions of a flow if any. This is
    an optimisation to avoid scanning the actions for each packet.

v2.12
* No change

v2.11
* First post
datapath: ovs_flow_to_nlattrs: use encap_eth_type

The ethernet type of an encapsulated frame may be obtained from
actions. If so it should be used to allow a richer conversion
of a flow to nlattrs.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* No change

v2.11
* First post
datapath: ovs_flow_used: use encap_eth_type

The ethernet type of an encapsulated frame may be obtained from
actions. If so it should be used to correct decoding of L3 and L4
packet data.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* As suggested by Jarno Rajahalme
  - Initialise encap_eth_type as 0 in ovs_dp_process_received_packet()

v2.12
* No change

v2.11
* First post

flow: Split flow_extract

Split the L3 and above portion of flow_extract() out into
flow_extract_l3_onwards() and call flow_extract_l3_onwards()
from flow_extract().

This is to allow re-extraction of l3 and higher information using
flow->encap_dl_type which may be set using information contained
in actions.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.12
* Rebase
* Add dl_type parameter to flow_extract_l3_onwards,
  allowing this patch to be applied independently of
  the rest of the MPLS patch-set.

v2.11
* First post
datapath: Allow IP actions for MPLS

Allow copy_ttl_in to function in the case where:
a) The outer header is MPLS;
b) The next-outer header is IP and;
c) The resulting nw ttl will be different from its existing value

In this circumstance a set ipv4 action will be used to adjust the TTL
but the dl_type of the match will be ETH_P_MPLS_UC or ETH_P_MPLS_MC.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Use eth_p_mpls helper

v2.11
* First post
User-Space MPLS actions and matches

This patch implements use-space datapath and non-datapath code
to match and use the datapath API set out in Leo Alterman's patch
"user-space datapath: Add basic MPLS support to kernel".

The resulting MPLS implementation supports:
* Pushing a single MPLS label
* Poping a single MPLS label
* Modifying an MPLS lable using set-field or load actions
  that act on the label value, tc and bos bit.
* There is no support for manipulating the TTL
  this is considered future work.

The single-level push pop limitation is implemented by processing
push, pop and set-field/load actions in order and discarding information
that would require multiple levels of push/pop to be supported.

e.g.
   push,push -> the first push is discarded
   pop,pop -> the first pop is discarded

This patch is based heavily on work by Ravi K.

Cc: Ravi K <rkerur@gmail.com>
Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* As suggested by Jarno Rajahalme
  - Update ofputil_usable_protocols to allow MPLS matches for OpenFlow 1.3.
  - Update ofpact_check__ to only copy the flow when checking
    OFPACT_REG_LOAD if (*dl_type != flow->dl_type)
* Fix inverted logic in flow_innermost_dl_type

v2.12
* Rebase
* Add eth_type_mpls helper
* Add flow_innermost_dl_type helper
* calculate MPLS fitness over entire flow
  - It is sufficient to just calculate the fitness of an MPLS frame once.
  - Previously a fitness calculation was made based on expectations calculated
    on L1 and L2 data. However, this may not be correct as it will return
    ODP_FIT_TOO_MUCH in the case where the key contains L3 attributes.
* Pass MPLS lse to push_mpls
  - When push_mpls() the LSE of the flow is always already known,
    so pass it to push_mpls and set it directly. This avoids:
    + The need to re-compose an default LSE, allowing
      the removal of get_lse()
    + The need to follow each call to push_mpls() with
      a call to set_mpls_lse()
  - This fixes the previously bogus usage of push_mpls
    in dp_netdev_execute_actions, allowing push_mpls to work
    in conjunction with the user-space datapath.

v2.11
* No change

v2.10
* Rebase

v2.9
* Rebase
* Update tests for upstream changes

v2.8
* Rebase, update for upstream OFPUTIL_P_* changes

v2.7
* No change

v2.6
* Non-trivial rebase
* Track dl_type changes in ofpact_check__() and ofpacts_check()
  to allow pre-requisite checks to work correctly in the presence
  of mpls_push and mpls_pop actions.
* Do not modify datapath.
  Accordingly, the changes suggested by Yamahata-san which were
  incorporated in v2.5 to the datapath patch "datapath: Add basic MPLS
  support to kernel"

v2.5
* As suggested by Yamahata-san
  - Do not guard against label == 0 for
    OVS_ACTION_ATTR_SET_MPLS in validate_actions().
    A label of 0 is valid
  - Remove comment stipulating that if
    the top_label element of struct sw_flow_key is 0 then
    there is no MPLS label. An MPLS label of 0 is valid
    and the correct check if ethertype is
    ntohs(ETH_TYPE_MPLS) or ntohs(ETH_TYPE_MPLS_MCAST)
* Update tests for TTL fix provided by
  "flow: Set ip_ttl in flow_compose()"
* Do not initialise ih and ih6 in flow_extract()
  until after calling parse_mpls() and parse_remaining_mpls()
  as those functions may change the value of b.data.
* Do not add spurious debug code to execute_controller_action()
* Do not reset packet->l3 in pop_mpls(),
  it is already the correct value

v2.4
* Make use of set_mpls_lse_*() in flow_set_mpls_*()

v2.3
* As suggested by Ben Pfaff
  - Remove noise-only change from execute_set_action()
  - Guard against running off the end of packets in parse_remaining_mpls()
  - Ensure there is sufficient data before reading IP header in flow_extract()
  - Omit formating mpls in flow_format if there is no MPLS header
  - Fix spelling errors in parse_mpls_onward()
  - Fix coding style in flow_compose()
  - Use inner_dl_type where possible in flow_compose()
  - Correct bitwise logic in mpls_set_any_*()
  - Do not define NXM constants for MPLS as the OXM constants may be used
    with NXM.
  - Disable writing of MPLS BOS by setting 'writable' to false for
    OXM_OF_MPLS_BOS.
  - Rename format_mpls_lse_values() as mpls_lse_from_components()
    as it is not a format helper.
  - Fix coding style in mpls_lse_from_components()
  - Evaluate check_expectations() outside of MAX
    as MAX evaluates its arguments more than once.
  - Remove noise-change from parse_8021q_onward()
  - Remove noise-change from commit_set_nw_action()
  - Move action checking logic from ofpact_check__() to
    ofpact_from_openflow11() and ofpact_from_nxast()
  - Remove noise-change from ofpact_format
  - Fix typos in ofpact_push
  - Correct comment in ofputil_usable_protocols()
    MPLS BoS bit match was added in OpenFlow 1.3
  - Add a helper function to return the pointer to the eth_type of a packet
    and use this to vastly simplify set_ethertype() and get_ethertype()
  - Correct size logic in get_label_ttl_and_tc() using
    ofpbuf_tail(packet) - packet->l3
  - Refactor get_label_ttl_and_tc to return an MPLS tag
    rather than broken out TTL, TC and value. Also,
    rename as get_lse()
  - Remove set_new_mpls_lse and open code its logic.
  - Correct code style of if block in pop_mpls()
  - Do not add unused IP6_TC()
  - Do not make spurious change to subfacet_should_install()
  - Remove assert() from execute_controller_action() as it
    is not obviously useful.
  - Make use of set_mpls_lse_values() in compose_mpls_push_action()
  - Do not make spurious change for REG_LOAD in do_xlate_actions()
  - Do not at test-mpls, it is not used
* As suggested by Yamahata-san
  - Use MPLS_xxx_MASK >> MPLS_xxx_SHIFT in mf_is_value_valid() and
  - Track MPLS stack depth and use it to determine if the MPLS label should
    be pushed, popped or modified
  - No longer use 0 as a special MPLS LSE value
* s/mpls_stack/mpls_bos/
  This is in keeping with the naming used in the OpenFlow 1.3 specification
* Fold user-space datapath back into this patch,
  there seem to be mutual dependencies.
* Remove stray structure definitions: nx_action_mpls_label,
  nx_action_mpls_tc, nx_action_mpls_ttl
* Remove check_expectations_mpls() and use check_expectations() directly
  instead.  The logic of check_expectations_mpls() is not relevant to the
  current incantation of the patch-set as it includes support for MPLS
  matches in the datapath.
* Removed unused TTL manipulation code

v2.2
* Manual Rebase

v2.1
* Reinstate user-space datapath changes
* Update to use datapath API set out in Leo Alterman's
  kernel datapath patch "datapath: Add basic MPLS support to kernel"
* Do not add:
  - OFPAT11_COPY_TTL_OUT/NXAST_COPY_TTL_OUT,
  - OFPAT11_COPY_TTL_IN/NXAST_COPY_TTL_IN.
  - OFPAT11_DEC_MPLS_TTL/NXAST_DEC_MPLS_TTL
  Add support for these later. Jesse Gross has commented that "It is envisaged
  this will be done "using set and some form of resubmit if necessary (as we do
  for IP)"
* Do not add:
  - OFPAT11_SET_MPLS_LABEL/NXAST_SET_MPLS_LABEL
  - OFPAT11_SET_MPLS_TC/NXAST_SET_MPLS_TC
  - OFPAT11_SET_MPLS_TTL/NXAST_SET_MPLS_TTL
  These may be handled by load/set-field actions.
* Remove inner_mpls_lse from struct flow
  - The new objective is to only support one layer of MPLS labels at this time
* Rearrange action handling logic (again):
  - Logic to commit commit all MPLS actions is now in commit_mpls_action()
    which is called by commit_odp_actions().
  - Logic to compose push actions is in compose_mpls_push_action()
  - Logic to compose pop actions is in compose_mpls_pop_action()
  - There is no logic to compose mpls_set actions,
    compose_mpls_lse_action() has been removed.
  - This seems consistent with the handling of other actions.
* Correct mpls formatting in format_odp_action(),
  an error introduced by me.
* s/commit_mpls_/compose_mpls_/
  This seems to be more in keeping with the current naming convention.
* s/mpls_stack/mpls_bos/i
  This seems to be more in keeping with the wording in
  the OpenFlow 1.3 specification

v2.0
* Rebase to current master
  - First by Isaku Yamahata in July;
  - Then by me more recently.
* Remove datapath changes
  - This is intended to provide a first step for
    merging MPLS. The uers-space chagges seem
    largely uncontroversial while the datapath
    changes were incomplete with respect to
    agreement on the implementation for TTL actions
    and offloads.
* Correct dec_mpls_ttl to decrement TTL by 1 rather than 2
  - Fix by Isaku Yamahata
* Bug fixes to allow test suite to pass
* Make sparse clean
* Introduce encap_dl_type element to struct flow.
  This is used to store the dl_type of the encapsulated packet
  and is used by odp_flow_key_to_flow() and flow_compose() to
  allow eth_from_packet_or_flow() to be able to handle
  e.g. an MPLS encoded IPv4 packet.
* update packet.c:get_label_ttl_and_tc() to treat unknown eth type
  asn an error.
* Remove datapath changes

Previous Revisions by Ravi K
odp-util: commit_set_nw_action: use flow's innermost dl_type

Use the innermost dl_type when decoding L3 and L4 data from a packet.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Use flow_innermost_dl_type helper

v2.11
* First post
packet: packet_get_tcp_flags: use flow's innermost dl_type

Use the innermost dl_type when decoding L3 and L4 data from a packet.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Use flow_innermost_dl_type helper

v2.11
* First post
actions: Allow secondary decoding of a flow

Actions may provide information to allow further decoding of
a flow.

For example:

In the case of MPLS, L3 and L4 information may not initially be decoded
from the frame as the ethernet type of the frame is an MPLS type and no
information is known about the type of the inner frame.

However, the type of the inner frame may be provided by an mpls_pop action
in which case L3 and L4 information may be decoded providing a finer
grained match than is otherwise possible.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* As suggested by Jarno Rajahalme
  - Use flow->encap_dl_type instead of of obtaining the value
    by scanning the actions.

v2.12
* No change

v2.11
* First post

fix
ofproto: Allow actions richer matches based on actions

If the actions of a flow allow further decoding of L3 and L4 data to
provide a richer match then use this richer match.

For example:

In the case of MPLS, L3 and L4 information may not initially be decoded
from the frame as the ethernet type of the frame is an MPLS type and no
information is known about the type of the inner frame.

However, the type of the inner frame may be provided by an mpls_pop action
in which case L3 and L4 information may be decoded providing a finer
grained match than is otherwise possible.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* Correct indentation in handle_flow_miss_l3_extraction()
* Rebase: Pass encap_dl_type argument to flow_extract_l3_onwards()

v2.12
* Use eth_type_mpls helper

v2.11
* First post
dpif-netdev: Inner And Outer Flows

This is the user-space datapath component of this change

Allow a flow to be visible in two forms, an outer flow and an inner flow.
This may occur if the actions allow further decoding of a packet to
provide a more fine-grained match. In this case the first-pass
coarse-grained match will hit the outer-flow and the second-pass
fined-grained match will hit the inner-flow.

Inner-flows are not visible to user-space. Rather, they are just an
internal representation to handle the case of actions allowing further
packet decoding. An inner-flow is associated with its outer-flow and
deleted when the outer-flow is deleted. An outer-flow may have more than
one inner-flow but an inner-flow may only have one outer-flow.

For example:

In the case of MPLS, L3 and L4 information may not initially be decoded
from the frame as the ethernet type of the frame is an MPLS type and no
information is known about the type of the inner frame.

However, the type of the inner frame may be provided by an mpls_pop action
in which case L3 and L4 information may be decoded providing a finer
grained match than is otherwise possible.

Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* First post
Add support for dec_mpls_ttl action

This adds support for the OpenFlow 1.1+ dec_mpls_ttl action.
And also adds an NX dec_mpls_ttl action.

The handling of the TTL modification is entirely handled in userspace.

Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Use eth_type_mpls() helper

v2.11
* No change

v2.10
* No change

v2.9
* Update tests for upstream changes

v2.8
* No change

v2.7
* Encode action as OFP11 action in OFP11+ messages

v2.6
* Rebase

v2.5
* First post
Add support for set_mpls_ttl action

This adds support for the OpenFlow 1.1+ set_mpls_ttl action.
And also adds an NX set_mpls_ttl action.

The handling of the TTL modification is entirely handled in userspace.

Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Use eth_type_mpls() helper

v2.11
* No change

v2.10
* Check the size of nx_action_mpls_ttl.
  nx_action_pop_mpls was being checked
  due to a cut-and-paste error

v2.9
* Update tests for upstream changes

v2.8
* No change

v2.7
* Encode action as OFP11 action in OFP11+ messages

v2.6
* Rebase

v2.5
* First post
Add support for copy_ttl_out action

This adds support for the OpenFlow 1.1+ copy_ttl_out action.
And also adds an NX copy_ttl_out action.

The implementation does not support copying in the case where the outermost
header is IP as it is unclear to me that Open vSwtich has a notion of an
inner IP header to copy the TLL from.

The handling of the TTL modification is entirely handled in userspace.

Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* Remove bogus test. copy_ttl_out from IP to MPLS only makes sense
  if the dl_type of the encapsulated frame is known, which implies
  that the original frame was IP and an mpls_push action has been applied.

v2.12
* No change

v2.10
* No change

v2.9
* Increment FLOW_WC_SEQ
* Update tests for upstream changes

v2.8
* No change

v2.7
* Encode action as OFP11 action in OFP11+ messages

v2.6
* Non-trivial rebase

v2.5
* First post
Add support for copy_ttl_in action

This adds support for the OpenFlow 1.1+ copy_ttl_in action.
And also adds an NX copy_ttl_out action.

The implementation does not support copying in the case where the outermost
header is IP as it is unclear to me that Open vSwtich has a notion of an
inner IP header to copy the TLL from.

The implementation does not support copying in the case where the
outermost and next-to-otermost header is MPLS due to limitations
in the current MPLS implementation which only supports modifying
the outermost MPLS header.

The handling of the TTL modification is entirely handled in userspace.

Reviewed-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>

---

v2.13
* No change

v2.12
* Rebase
* Use eth_type_mpls() helper

v2.11
* No change

v2.10
* No change

v2.9
* Update tests for upstream changes

v2.8
* No change

v2.7
* Correct typo in changelog
* Encode action as OFP11 action in OFP11+ messages

v2.6
* Non-trivial rebase

v2.5
* First post