The page-pool as a component for XDP forwarding


Jesper Dangaard Brouer
 

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.

Below I propose that we use XDP eBPF in a new fashion, based on the
state of the feedback loop that the page-pool offer. With eBPF hooks
at both RX and page-return-time, we can implement a super powerful DDoS
protection mechanism. Does it make sense?

--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Designing the page-pool
=======================
:Version: 0.1.1
:Authors: Jesper Dangaard Brouer

Introduction
============

Motivation for page recycling is primarily performance related (due to
network stack use-cases), as bottlenecks exist in both the page
allocator and DMA APIs.

It was agreed at MM-summit 2016, that the ideas developed to speedup
the per CPU caching layer, should be integrated into the page
allocator, where possible. And we should try to share data
structures. (https://lwn.net/Articles/684616/)

The page-pool per device, still have merits, as it can:
1) solve the DMA API (IOMMU) overhead issue, which
2) in-directly make pages writable by network-stack,
3) provide a feedback-loop at the device level

Referring to MM-summit presentation, for the DMA use-case, and why
larger order pages are considered problematic.

MM-summit 2016 presentation avail here:
* http://people.netfilter.org/hawk/presentations/MM-summit2016/generic_page_pool_mm_summit2016.pdf


XDP (eXpress Data Path)
-----------------------

The page-pool is a component that XDP need in-order to perform packet
forwarding at the page level.

* https://github.com/iovisor/bpf-docs/raw/master/Express_Data_Path.pdf
* http://lwn.net/Articles/682538/


Avoid NUMA problems, return to same CPU
=======================================

A classical problem, especially for NUMA systems, is that in a
asymmetric workload memory can be allocated on one CPU but free'ed on
a remote CPU (worst-case a remote NUMA node). (Thus, CPU "local"
recycling on free is problematic).

Upfront, our design solves this issue, by requiring pages are recycled
back to the originating CPU. (This feature is also beneficial for the
feedback-loop and associated accounting.)


Reduce page (buddy) fragmentation
=================================

Another benefit of a page-pool layer on-top of a driver, which can
maintain a steady-state working-set, is that the page allocator have
less chances of getting fragmented.


Feedback loop
=============

With drivers current approach (of calling the page allocator directly)
the number of pages a driver can hand-out is unbounded.

The page-pool provide the ability to get a feedback loop facility, at
the device level.

A classical problem is that a single device can take up an unfair
large portion of the shared memory resources, if e.g. an application
(or guest VM) does not free the resources (fast-enough). Thus,
negatively impacting the entire system, possibly leading to
Out-Of-Memory (OOM) conditions.

The protection mechanism the page-pool can provide (at the device
level) MUST not be seen as a congestion-control mechanism. It should
be seen as a "circuit-breaker" last resort facility to protect other
parts of the system.

Congestion-control aware traffic usually handle the situation (and
adjust their rate to stabilize the network). Thus, a circuit-breaker
must allow sufficient time for congestion-control aware traffic to
stabilize.

The situations that are relevant for the circuit-breaker, are
excessive and persistent non-congestion-controlled traffic, that
affect other parts of the system.

Drop policy
-----------

When the circuit-breaker is in effect (e.g. dropping all packets and
recycling the page directly), then XDP/eBPF hook could decide to
change the drop verdict.

With the XDP hook in-place, it is possible to implement arbitrarily
drop policies. If the XDP hook, gets the RX HW-hash, then it can
implement flow based policies without touching packet data.


Detecting driver overload
-------------------------

It might be difficult to determine when the circuit-breaker should
kick-in, based on an excessive working-set size of pages.

But at the driver level, it is easy to detect when the system is
overloaded, to such an extend that it cannot process packets
fast-enough. This is simply indicated by the driver cannot empty the
RX queue fast-enough, thus HW is RX dropping packets (FIFO taildrop).

This indication could be passed to a XDP hook, which can implement a
drop policy. Filtering packets at this level can likely restore
normal system operation. Building on the principal of spending as few
CPU cycles as possible on packets that need to be dropped anyhow (by a
deeper layer).

It is important to realize that, dropping the the XDP driver level is
extremely efficient. Experiments show that, the filter capacity of
XDP filter is 14.8Mpps (DDIO touching packet and updating up an eBPF
map), while iptables-raw is 6Mpps, and hitting socket limit is around
0.7Mpps. Thus, an attacker can actually consume significant CPU
resources by simply sending UDP packets to a closed port.


Performance vs feedback-loop accounting
---------------------------------------

For performance reasons, the accounting should be kept as per CPU
structures.

For NIC drivers it actually makes sense to keep accounting 100% per
CPU. In essence, we would like the circuit-breaker to kick-in per RX
HW queue, as that would allow remaining RX queue traffic flow.

RX queues are usually bound to a specific CPU, to avoid packet
reordering (and NIC RSS hashing (try-to) keep flows per RX queue).
Thus, keeping page recycling and stats per CPU structures, basically
achieves the same as binding a page-pool per RX queue.

If RX queue SMP affinity change runtime, then it does not matter. A
RX ring-queue can contain pages "belonging" to another CPU, but it
does not matter, as eventually they will be returned to the owning
CPU.


It would be possible to also keep a more central state for a
page-pool, because the number of pages it manage only change when
(re)filling or returning pages to the page allocator, which should be
a more infrequent event. I would prefer not to.


Determining steady-state working-set
------------------------------------

For optimal performance and to minimize memory usage, the page-pool
should only maintain the number of pages required for the steady-state
working-set.

The size of the steady-state working-set will vary depending on the
workload. E.g. in a forwarding workload it will be fairly small.
E.g. for a TCP (local)host delivery workload it will be bigger. Thus,
the steady-state working-set should be dynamically determined.

Detecting steady-state by realizing, that in steady state, no
(re)filling have occurred for a while, and the number of "free" pages
in the pool is not excessive.

Idea: could we track number of page-pool recycle alloc and free's
within N x jiffies, and if the numbers (rate) are approx the same,
record number of outstanding pages as the steady-state number? (Could
be implemented as single signed counter reset every N jiffies, inc/dec
for alloc/free, approaching zero (at reset point) == stable)


If RX rate is bigger than TX/consumption rate, queue theory says a
queue will form. While the queue builds (somewhere outside out our
control), the page-pool need to request more and more pages from
page-allocator. The number of outstanding pages increase, seen from
the page-pool, proportional to the queue in the system.

This, RX > TX is an overload situation. Congestion-control aware
traffic will self stabilize. Assuming dealing with
non-congestion-controlled traffic, some different scenarios exist:

1. (good-queue) Overload only exist for a short period of time, like a
traffic burst. This is "good-queue", where we absorb bursts.

2. (bad-queue) Situation persists, but some other limit is hit, and
packets get dropped. Like qdisc limit on forwarding, or local
socket limit. This could be interpreted as a "steady-steady", as
page-recycling reach a certain level, and maybe it should?

3. (OOM) Situation persists, and no natural resource limit is hit.
Eventually system runs dry of memory pages and OOM. This situation
should be caught by our circuit-breaker mechanism, before OOM.

4. For forwarding, the hole code path from RX to TX, takes longer than
the packet arrival rate. Drops happen at HW level by overflowing
RX queue (as it is not emptied fast enough). Possible to detect
inside driver, and we could start a eBPF program to filter?

After an overload situation, when RX decrease (or stop), so RX < TX
(likely for a short period of time). Then, we have the opportunity to
return/free objects/pages back to the page-allocator.

Q: How quickly should we do so (return pages)?
Q: How much slack to handle bursts?
Q: Is "steady-state" number of pages an absolute limit?


XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).

The XDP eBPF hook can maintain it's own internal data structure, to
track pages.

We could saved the RX HW hash (maybe in struct-page), then eBPF could
implement flow metering without touching packet data.

The eBPF prog can even do it's own timestamping on RX and compare at
pool "return" point. Essentially implementing a CoDel like scheme,
measuring "time-spend-in-network-stack". (For this to make sense, it
would likely need to group by RX-HW-hash, as multiple ways through the
netstack exist, thus it cannot be viewed as a FIFO).


Conclusion
----------

The resource limitation/protection feature offered by the page-pool,
is primarily a circuit-breaker facility for protecting other parts of
the system. Combined with a XDP/eBPF hook, it offers a powerful and
more fine-grained control.

It requires more work and research if we want to react
"earlier". e.g. before the circuit-breaker kicks in. Here one should
be careful not to interfere with congestion aware traffic, by giving
it sufficient time to reach.

At the driver level it is also possible to detect, if system is not
processing RX packets fast-enough. This is not an inherent feature of
the page-pool, but it would be useful input for a eBPF filter.

For the XDP/eBPF hook, this means that it should take a "signal" as
input of how the current operating machine state is.

Considering the states:
* State:"circuit-breaker"- eBPF can choose to approve packets, else stack drop
* State:"RX-overload" - eBPF can choose to drop packets to restore operation

Relating to page allocator
==========================

The current page allocator have a per CPU caching layer for
order-0 pages, called PCP (per CPU pages) ::

struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
int batch; /* chunk size for buddy add/remove */

/* Lists of pages, one per migrate type stored on the pcp-lists */
struct list_head lists[MIGRATE_PCPTYPES];
};

The "high" watermark, can be compared to (dynamic) steady-state
number, which determine how many cached (order-0) pages are kept,
before they are returned to the page allocator.

For PCP once the "high" watermark is hit, then "batch" number of
pages are returned. (Using a batch (re)moves the pathological
case of two object working-set being recycles on the "edge" of
the "high" watermark, causing too much interaction with the page
alloactor).

On my 8 core (i7-4790K CPU @ 4.00GHz) with 16GB RAM, the values
for PCP are high=186 and batch=31 (note 31*6 = 186). These
setting are likely not optimal for networking, as e.g. TX DMA
completion is default allowed to freeing up-to 256 pages.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?


Background material
===================

Circuit Breaker
---------------

Quotes from:

.. _RFC-Circuit-Breaker:
https://tools.ietf.org/html/draft-ietf-tsvwg-circuit-breaker-14

RFC-Circuit-Breaker_ ::

[...] non-congestion-controlled traffic, including many applications
using the User Datagram Protocol (UDP), can form a significant
proportion of the total traffic traversing a link. The current
Internet therefore requires that non-congestion-controlled traffic is
considered to avoid persistent excessive congestion


RFC-Circuit-Breaker_ ::

This longer period is needed to provide sufficient time for transport
congestion control (or applications) to adjust their rate following
congestion, and for the network load to stabilize after any
adjustment.


RFC-Circuit-Breaker_ ::

In contrast, Circuit Breakers are recommended for non-congestion-
controlled Internet flows and for traffic aggregates, e.g., traffic
sent using a network tunnel. They operate on timescales much longer
than the packet RTT, and trigger under situations of abnormal
(excessive) congestion.


Tom Herbert <tom@...>
 

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.

Below I propose that we use XDP eBPF in a new fashion, based on the
state of the feedback loop that the page-pool offer. With eBPF hooks
at both RX and page-return-time, we can implement a super powerful DDoS
protection mechanism. Does it make sense?
Mostly ;-). I like the idea of returning an index from eBPF which
basically just gives a queue to transmit. Presumably, each receive
queue would have it's own XDP transmit queue that it can use lockless.
Also, I think it is reasonable that we could cross devices but within
the _same_ driver (like supporting forwarding between two Mellanox
NICs). In that case each RX queue has one dedicated XDP TX queue for
each device.

For forwarding on a non XDP queue (like 3B or crossing different type
devices) I don't think we should do anything special. Just pass the
packet to the stack like in the olden days and use the stack
forwarding path. This is obviously slow path, but not really very
interesting to optimize in XDP.

One thing I am not sure how to deal with is flow control. i.e. if the
transmit queue is being blocked who should do the drop. Preferably,
we'd want the to know the queue occupancy in BPF to do an intelligent
drop (some crude fq-codel or the like?)

Tom

--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Designing the page-pool
=======================
:Version: 0.1.1
:Authors: Jesper Dangaard Brouer

Introduction
============

Motivation for page recycling is primarily performance related (due to
network stack use-cases), as bottlenecks exist in both the page
allocator and DMA APIs.

It was agreed at MM-summit 2016, that the ideas developed to speedup
the per CPU caching layer, should be integrated into the page
allocator, where possible. And we should try to share data
structures. (https://lwn.net/Articles/684616/)

The page-pool per device, still have merits, as it can:
1) solve the DMA API (IOMMU) overhead issue, which
2) in-directly make pages writable by network-stack,
3) provide a feedback-loop at the device level

Referring to MM-summit presentation, for the DMA use-case, and why
larger order pages are considered problematic.

MM-summit 2016 presentation avail here:
* http://people.netfilter.org/hawk/presentations/MM-summit2016/generic_page_pool_mm_summit2016.pdf


XDP (eXpress Data Path)
-----------------------

The page-pool is a component that XDP need in-order to perform packet
forwarding at the page level.

* https://github.com/iovisor/bpf-docs/raw/master/Express_Data_Path.pdf
* http://lwn.net/Articles/682538/


Avoid NUMA problems, return to same CPU
=======================================

A classical problem, especially for NUMA systems, is that in a
asymmetric workload memory can be allocated on one CPU but free'ed on
a remote CPU (worst-case a remote NUMA node). (Thus, CPU "local"
recycling on free is problematic).

Upfront, our design solves this issue, by requiring pages are recycled
back to the originating CPU. (This feature is also beneficial for the
feedback-loop and associated accounting.)


Reduce page (buddy) fragmentation
=================================

Another benefit of a page-pool layer on-top of a driver, which can
maintain a steady-state working-set, is that the page allocator have
less chances of getting fragmented.


Feedback loop
=============

With drivers current approach (of calling the page allocator directly)
the number of pages a driver can hand-out is unbounded.

The page-pool provide the ability to get a feedback loop facility, at
the device level.

A classical problem is that a single device can take up an unfair
large portion of the shared memory resources, if e.g. an application
(or guest VM) does not free the resources (fast-enough). Thus,
negatively impacting the entire system, possibly leading to
Out-Of-Memory (OOM) conditions.

The protection mechanism the page-pool can provide (at the device
level) MUST not be seen as a congestion-control mechanism. It should
be seen as a "circuit-breaker" last resort facility to protect other
parts of the system.

Congestion-control aware traffic usually handle the situation (and
adjust their rate to stabilize the network). Thus, a circuit-breaker
must allow sufficient time for congestion-control aware traffic to
stabilize.

The situations that are relevant for the circuit-breaker, are
excessive and persistent non-congestion-controlled traffic, that
affect other parts of the system.

Drop policy
-----------

When the circuit-breaker is in effect (e.g. dropping all packets and
recycling the page directly), then XDP/eBPF hook could decide to
change the drop verdict.

With the XDP hook in-place, it is possible to implement arbitrarily
drop policies. If the XDP hook, gets the RX HW-hash, then it can
implement flow based policies without touching packet data.


Detecting driver overload
-------------------------

It might be difficult to determine when the circuit-breaker should
kick-in, based on an excessive working-set size of pages.

But at the driver level, it is easy to detect when the system is
overloaded, to such an extend that it cannot process packets
fast-enough. This is simply indicated by the driver cannot empty the
RX queue fast-enough, thus HW is RX dropping packets (FIFO taildrop).

This indication could be passed to a XDP hook, which can implement a
drop policy. Filtering packets at this level can likely restore
normal system operation. Building on the principal of spending as few
CPU cycles as possible on packets that need to be dropped anyhow (by a
deeper layer).

It is important to realize that, dropping the the XDP driver level is
extremely efficient. Experiments show that, the filter capacity of
XDP filter is 14.8Mpps (DDIO touching packet and updating up an eBPF
map), while iptables-raw is 6Mpps, and hitting socket limit is around
0.7Mpps. Thus, an attacker can actually consume significant CPU
resources by simply sending UDP packets to a closed port.


Performance vs feedback-loop accounting
---------------------------------------

For performance reasons, the accounting should be kept as per CPU
structures.

For NIC drivers it actually makes sense to keep accounting 100% per
CPU. In essence, we would like the circuit-breaker to kick-in per RX
HW queue, as that would allow remaining RX queue traffic flow.

RX queues are usually bound to a specific CPU, to avoid packet
reordering (and NIC RSS hashing (try-to) keep flows per RX queue).
Thus, keeping page recycling and stats per CPU structures, basically
achieves the same as binding a page-pool per RX queue.

If RX queue SMP affinity change runtime, then it does not matter. A
RX ring-queue can contain pages "belonging" to another CPU, but it
does not matter, as eventually they will be returned to the owning
CPU.


It would be possible to also keep a more central state for a
page-pool, because the number of pages it manage only change when
(re)filling or returning pages to the page allocator, which should be
a more infrequent event. I would prefer not to.


Determining steady-state working-set
------------------------------------

For optimal performance and to minimize memory usage, the page-pool
should only maintain the number of pages required for the steady-state
working-set.

The size of the steady-state working-set will vary depending on the
workload. E.g. in a forwarding workload it will be fairly small.
E.g. for a TCP (local)host delivery workload it will be bigger. Thus,
the steady-state working-set should be dynamically determined.

Detecting steady-state by realizing, that in steady state, no
(re)filling have occurred for a while, and the number of "free" pages
in the pool is not excessive.

Idea: could we track number of page-pool recycle alloc and free's
within N x jiffies, and if the numbers (rate) are approx the same,
record number of outstanding pages as the steady-state number? (Could
be implemented as single signed counter reset every N jiffies, inc/dec
for alloc/free, approaching zero (at reset point) == stable)


If RX rate is bigger than TX/consumption rate, queue theory says a
queue will form. While the queue builds (somewhere outside out our
control), the page-pool need to request more and more pages from
page-allocator. The number of outstanding pages increase, seen from
the page-pool, proportional to the queue in the system.

This, RX > TX is an overload situation. Congestion-control aware
traffic will self stabilize. Assuming dealing with
non-congestion-controlled traffic, some different scenarios exist:

1. (good-queue) Overload only exist for a short period of time, like a
traffic burst. This is "good-queue", where we absorb bursts.

2. (bad-queue) Situation persists, but some other limit is hit, and
packets get dropped. Like qdisc limit on forwarding, or local
socket limit. This could be interpreted as a "steady-steady", as
page-recycling reach a certain level, and maybe it should?

3. (OOM) Situation persists, and no natural resource limit is hit.
Eventually system runs dry of memory pages and OOM. This situation
should be caught by our circuit-breaker mechanism, before OOM.

4. For forwarding, the hole code path from RX to TX, takes longer than
the packet arrival rate. Drops happen at HW level by overflowing
RX queue (as it is not emptied fast enough). Possible to detect
inside driver, and we could start a eBPF program to filter?

After an overload situation, when RX decrease (or stop), so RX < TX
(likely for a short period of time). Then, we have the opportunity to
return/free objects/pages back to the page-allocator.

Q: How quickly should we do so (return pages)?
Q: How much slack to handle bursts?
Q: Is "steady-state" number of pages an absolute limit?


XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).

The XDP eBPF hook can maintain it's own internal data structure, to
track pages.

We could saved the RX HW hash (maybe in struct-page), then eBPF could
implement flow metering without touching packet data.

The eBPF prog can even do it's own timestamping on RX and compare at
pool "return" point. Essentially implementing a CoDel like scheme,
measuring "time-spend-in-network-stack". (For this to make sense, it
would likely need to group by RX-HW-hash, as multiple ways through the
netstack exist, thus it cannot be viewed as a FIFO).


Conclusion
----------

The resource limitation/protection feature offered by the page-pool,
is primarily a circuit-breaker facility for protecting other parts of
the system. Combined with a XDP/eBPF hook, it offers a powerful and
more fine-grained control.

It requires more work and research if we want to react
"earlier". e.g. before the circuit-breaker kicks in. Here one should
be careful not to interfere with congestion aware traffic, by giving
it sufficient time to reach.

At the driver level it is also possible to detect, if system is not
processing RX packets fast-enough. This is not an inherent feature of
the page-pool, but it would be useful input for a eBPF filter.

For the XDP/eBPF hook, this means that it should take a "signal" as
input of how the current operating machine state is.

Considering the states:
* State:"circuit-breaker"- eBPF can choose to approve packets, else stack drop
* State:"RX-overload" - eBPF can choose to drop packets to restore operation

Relating to page allocator
==========================

The current page allocator have a per CPU caching layer for
order-0 pages, called PCP (per CPU pages) ::

struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
int batch; /* chunk size for buddy add/remove */

/* Lists of pages, one per migrate type stored on the pcp-lists */
struct list_head lists[MIGRATE_PCPTYPES];
};

The "high" watermark, can be compared to (dynamic) steady-state
number, which determine how many cached (order-0) pages are kept,
before they are returned to the page allocator.

For PCP once the "high" watermark is hit, then "batch" number of
pages are returned. (Using a batch (re)moves the pathological
case of two object working-set being recycles on the "edge" of
the "high" watermark, causing too much interaction with the page
alloactor).

On my 8 core (i7-4790K CPU @ 4.00GHz) with 16GB RAM, the values
for PCP are high=186 and batch=31 (note 31*6 = 186). These
setting are likely not optimal for networking, as e.g. TX DMA
completion is default allowed to freeing up-to 256 pages.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?


Background material
===================

Circuit Breaker
---------------

Quotes from:

.. _RFC-Circuit-Breaker:
https://tools.ietf.org/html/draft-ietf-tsvwg-circuit-breaker-14

RFC-Circuit-Breaker_ ::

[...] non-congestion-controlled traffic, including many applications
using the User Datagram Protocol (UDP), can form a significant
proportion of the total traffic traversing a link. The current
Internet therefore requires that non-congestion-controlled traffic is
considered to avoid persistent excessive congestion


RFC-Circuit-Breaker_ ::

This longer period is needed to provide sufficient time for transport
congestion control (or applications) to adjust their rate following
congestion, and for the network load to stabilize after any
adjustment.


RFC-Circuit-Breaker_ ::

In contrast, Circuit Breakers are recommended for non-congestion-
controlled Internet flows and for traffic aggregates, e.g., traffic
sent using a network tunnel. They operate on timescales much longer
than the packet RTT, and trigger under situations of abnormal
(excessive) congestion.


Jesper Dangaard Brouer
 

On Wed, 4 May 2016 09:52:08 -0700
Tom Herbert <tom@...> wrote:

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.

Below I propose that we use XDP eBPF in a new fashion, based on the
state of the feedback loop that the page-pool offer. With eBPF hooks
at both RX and page-return-time, we can implement a super powerful DDoS
protection mechanism. Does it make sense?
Mostly ;-). I like the idea of returning an index from eBPF which
basically just gives a queue to transmit. Presumably, each receive
queue would have it's own XDP transmit queue that it can use lockless.
Also, I think it is reasonable that we could cross devices but within
the _same_ driver (like supporting forwarding between two Mellanox
NICs). In that case each RX queue has one dedicated XDP TX queue for
each device.
I'm not sure how you can get lockless TX with only one XDP-TX queue.

Remember we have to build in bulk TX from day one. Why? Remember the
TX tailptr write is costing in the area of 100ns. Thus, too expensive
to send single TX frames.


For forwarding on a non XDP queue (like 3B or crossing different type
devices) I don't think we should do anything special. Just pass the
packet to the stack like in the olden days and use the stack
forwarding path. This is obviously slow path, but not really very
interesting to optimize in XDP.
Yes for 3B.
For 3A I want to support cross device driver.

One thing I am not sure how to deal with is flow control. i.e. if the
transmit queue is being blocked who should do the drop. Preferably,
we'd want the to know the queue occupancy in BPF to do an intelligent
drop (some crude fq-codel or the like?)
Flow control or push-back is an interesting problem to solve.


--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Designing the page-pool
=======================
:Version: 0.1.1
:Authors: Jesper Dangaard Brouer

Introduction
============

Motivation for page recycling is primarily performance related (due to
network stack use-cases), as bottlenecks exist in both the page
allocator and DMA APIs.

It was agreed at MM-summit 2016, that the ideas developed to speedup
the per CPU caching layer, should be integrated into the page
allocator, where possible. And we should try to share data
structures. (https://lwn.net/Articles/684616/)

The page-pool per device, still have merits, as it can:
1) solve the DMA API (IOMMU) overhead issue, which
2) in-directly make pages writable by network-stack,
3) provide a feedback-loop at the device level

Referring to MM-summit presentation, for the DMA use-case, and why
larger order pages are considered problematic.

MM-summit 2016 presentation avail here:
* http://people.netfilter.org/hawk/presentations/MM-summit2016/generic_page_pool_mm_summit2016.pdf


XDP (eXpress Data Path)
-----------------------

The page-pool is a component that XDP need in-order to perform packet
forwarding at the page level.

* https://github.com/iovisor/bpf-docs/raw/master/Express_Data_Path.pdf
* http://lwn.net/Articles/682538/


Avoid NUMA problems, return to same CPU
=======================================

A classical problem, especially for NUMA systems, is that in a
asymmetric workload memory can be allocated on one CPU but free'ed on
a remote CPU (worst-case a remote NUMA node). (Thus, CPU "local"
recycling on free is problematic).

Upfront, our design solves this issue, by requiring pages are recycled
back to the originating CPU. (This feature is also beneficial for the
feedback-loop and associated accounting.)


Reduce page (buddy) fragmentation
=================================

Another benefit of a page-pool layer on-top of a driver, which can
maintain a steady-state working-set, is that the page allocator have
less chances of getting fragmented.


Feedback loop
=============

With drivers current approach (of calling the page allocator directly)
the number of pages a driver can hand-out is unbounded.

The page-pool provide the ability to get a feedback loop facility, at
the device level.

A classical problem is that a single device can take up an unfair
large portion of the shared memory resources, if e.g. an application
(or guest VM) does not free the resources (fast-enough). Thus,
negatively impacting the entire system, possibly leading to
Out-Of-Memory (OOM) conditions.

The protection mechanism the page-pool can provide (at the device
level) MUST not be seen as a congestion-control mechanism. It should
be seen as a "circuit-breaker" last resort facility to protect other
parts of the system.

Congestion-control aware traffic usually handle the situation (and
adjust their rate to stabilize the network). Thus, a circuit-breaker
must allow sufficient time for congestion-control aware traffic to
stabilize.

The situations that are relevant for the circuit-breaker, are
excessive and persistent non-congestion-controlled traffic, that
affect other parts of the system.

Drop policy
-----------

When the circuit-breaker is in effect (e.g. dropping all packets and
recycling the page directly), then XDP/eBPF hook could decide to
change the drop verdict.

With the XDP hook in-place, it is possible to implement arbitrarily
drop policies. If the XDP hook, gets the RX HW-hash, then it can
implement flow based policies without touching packet data.


Detecting driver overload
-------------------------

It might be difficult to determine when the circuit-breaker should
kick-in, based on an excessive working-set size of pages.

But at the driver level, it is easy to detect when the system is
overloaded, to such an extend that it cannot process packets
fast-enough. This is simply indicated by the driver cannot empty the
RX queue fast-enough, thus HW is RX dropping packets (FIFO taildrop).

This indication could be passed to a XDP hook, which can implement a
drop policy. Filtering packets at this level can likely restore
normal system operation. Building on the principal of spending as few
CPU cycles as possible on packets that need to be dropped anyhow (by a
deeper layer).

It is important to realize that, dropping the the XDP driver level is
extremely efficient. Experiments show that, the filter capacity of
XDP filter is 14.8Mpps (DDIO touching packet and updating up an eBPF
map), while iptables-raw is 6Mpps, and hitting socket limit is around
0.7Mpps. Thus, an attacker can actually consume significant CPU
resources by simply sending UDP packets to a closed port.


Performance vs feedback-loop accounting
---------------------------------------

For performance reasons, the accounting should be kept as per CPU
structures.

For NIC drivers it actually makes sense to keep accounting 100% per
CPU. In essence, we would like the circuit-breaker to kick-in per RX
HW queue, as that would allow remaining RX queue traffic flow.

RX queues are usually bound to a specific CPU, to avoid packet
reordering (and NIC RSS hashing (try-to) keep flows per RX queue).
Thus, keeping page recycling and stats per CPU structures, basically
achieves the same as binding a page-pool per RX queue.

If RX queue SMP affinity change runtime, then it does not matter. A
RX ring-queue can contain pages "belonging" to another CPU, but it
does not matter, as eventually they will be returned to the owning
CPU.


It would be possible to also keep a more central state for a
page-pool, because the number of pages it manage only change when
(re)filling or returning pages to the page allocator, which should be
a more infrequent event. I would prefer not to.


Determining steady-state working-set
------------------------------------

For optimal performance and to minimize memory usage, the page-pool
should only maintain the number of pages required for the steady-state
working-set.

The size of the steady-state working-set will vary depending on the
workload. E.g. in a forwarding workload it will be fairly small.
E.g. for a TCP (local)host delivery workload it will be bigger. Thus,
the steady-state working-set should be dynamically determined.

Detecting steady-state by realizing, that in steady state, no
(re)filling have occurred for a while, and the number of "free" pages
in the pool is not excessive.

Idea: could we track number of page-pool recycle alloc and free's
within N x jiffies, and if the numbers (rate) are approx the same,
record number of outstanding pages as the steady-state number? (Could
be implemented as single signed counter reset every N jiffies, inc/dec
for alloc/free, approaching zero (at reset point) == stable)


If RX rate is bigger than TX/consumption rate, queue theory says a
queue will form. While the queue builds (somewhere outside out our
control), the page-pool need to request more and more pages from
page-allocator. The number of outstanding pages increase, seen from
the page-pool, proportional to the queue in the system.

This, RX > TX is an overload situation. Congestion-control aware
traffic will self stabilize. Assuming dealing with
non-congestion-controlled traffic, some different scenarios exist:

1. (good-queue) Overload only exist for a short period of time, like a
traffic burst. This is "good-queue", where we absorb bursts.

2. (bad-queue) Situation persists, but some other limit is hit, and
packets get dropped. Like qdisc limit on forwarding, or local
socket limit. This could be interpreted as a "steady-steady", as
page-recycling reach a certain level, and maybe it should?

3. (OOM) Situation persists, and no natural resource limit is hit.
Eventually system runs dry of memory pages and OOM. This situation
should be caught by our circuit-breaker mechanism, before OOM.

4. For forwarding, the hole code path from RX to TX, takes longer than
the packet arrival rate. Drops happen at HW level by overflowing
RX queue (as it is not emptied fast enough). Possible to detect
inside driver, and we could start a eBPF program to filter?

After an overload situation, when RX decrease (or stop), so RX < TX
(likely for a short period of time). Then, we have the opportunity to
return/free objects/pages back to the page-allocator.

Q: How quickly should we do so (return pages)?
Q: How much slack to handle bursts?
Q: Is "steady-state" number of pages an absolute limit?


XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).

The XDP eBPF hook can maintain it's own internal data structure, to
track pages.

We could saved the RX HW hash (maybe in struct-page), then eBPF could
implement flow metering without touching packet data.

The eBPF prog can even do it's own timestamping on RX and compare at
pool "return" point. Essentially implementing a CoDel like scheme,
measuring "time-spend-in-network-stack". (For this to make sense, it
would likely need to group by RX-HW-hash, as multiple ways through the
netstack exist, thus it cannot be viewed as a FIFO).


Conclusion
----------

The resource limitation/protection feature offered by the page-pool,
is primarily a circuit-breaker facility for protecting other parts of
the system. Combined with a XDP/eBPF hook, it offers a powerful and
more fine-grained control.

It requires more work and research if we want to react
"earlier". e.g. before the circuit-breaker kicks in. Here one should
be careful not to interfere with congestion aware traffic, by giving
it sufficient time to reach.

At the driver level it is also possible to detect, if system is not
processing RX packets fast-enough. This is not an inherent feature of
the page-pool, but it would be useful input for a eBPF filter.

For the XDP/eBPF hook, this means that it should take a "signal" as
input of how the current operating machine state is.

Considering the states:
* State:"circuit-breaker"- eBPF can choose to approve packets, else stack drop
* State:"RX-overload" - eBPF can choose to drop packets to restore operation

Relating to page allocator
==========================

The current page allocator have a per CPU caching layer for
order-0 pages, called PCP (per CPU pages) ::

struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
int batch; /* chunk size for buddy add/remove */

/* Lists of pages, one per migrate type stored on the pcp-lists */
struct list_head lists[MIGRATE_PCPTYPES];
};

The "high" watermark, can be compared to (dynamic) steady-state
number, which determine how many cached (order-0) pages are kept,
before they are returned to the page allocator.

For PCP once the "high" watermark is hit, then "batch" number of
pages are returned. (Using a batch (re)moves the pathological
case of two object working-set being recycles on the "edge" of
the "high" watermark, causing too much interaction with the page
alloactor).

On my 8 core (i7-4790K CPU @ 4.00GHz) with 16GB RAM, the values
for PCP are high=186 and batch=31 (note 31*6 = 186). These
setting are likely not optimal for networking, as e.g. TX DMA
completion is default allowed to freeing up-to 256 pages.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?


Background material
===================

Circuit Breaker
---------------

Quotes from:

.. _RFC-Circuit-Breaker:
https://tools.ietf.org/html/draft-ietf-tsvwg-circuit-breaker-14

RFC-Circuit-Breaker_ ::

[...] non-congestion-controlled traffic, including many applications
using the User Datagram Protocol (UDP), can form a significant
proportion of the total traffic traversing a link. The current
Internet therefore requires that non-congestion-controlled traffic is
considered to avoid persistent excessive congestion


RFC-Circuit-Breaker_ ::

This longer period is needed to provide sufficient time for transport
congestion control (or applications) to adjust their rate following
congestion, and for the network load to stabilize after any
adjustment.


RFC-Circuit-Breaker_ ::

In contrast, Circuit Breakers are recommended for non-congestion-
controlled Internet flows and for traffic aggregates, e.g., traffic
sent using a network tunnel. They operate on timescales much longer
than the packet RTT, and trigger under situations of abnormal
(excessive) congestion.


--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Tom Herbert <tom@...>
 

On Wed, May 4, 2016 at 11:13 AM, Jesper Dangaard Brouer
<brouer@...> wrote:
On Wed, 4 May 2016 09:52:08 -0700
Tom Herbert <tom@...> wrote:

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.

Below I propose that we use XDP eBPF in a new fashion, based on the
state of the feedback loop that the page-pool offer. With eBPF hooks
at both RX and page-return-time, we can implement a super powerful DDoS
protection mechanism. Does it make sense?
Mostly ;-). I like the idea of returning an index from eBPF which
basically just gives a queue to transmit. Presumably, each receive
queue would have it's own XDP transmit queue that it can use lockless.
Also, I think it is reasonable that we could cross devices but within
the _same_ driver (like supporting forwarding between two Mellanox
NICs). In that case each RX queue has one dedicated XDP TX queue for
each device.
I'm not sure how you can get lockless TX with only one XDP-TX queue.
One XDP-TX queue per receiving CPU. Also, we might have even more
queues for priority. We don't want to bake in any assumption of 1-1
relationship between RX and TX queues either, there's more benefit to
#TX >= #RX

Remember we have to build in bulk TX from day one. Why? Remember the
TX tailptr write is costing in the area of 100ns. Thus, too expensive
to send single TX frames.
That can be done in the backend driver, although would be nice if BPF
code can request flush.

For forwarding on a non XDP queue (like 3B or crossing different type
devices) I don't think we should do anything special. Just pass the
packet to the stack like in the olden days and use the stack
forwarding path. This is obviously slow path, but not really very
interesting to optimize in XDP.
Yes for 3B.
For 3A I want to support cross device driver.
Maybe we can get basic forwarding to work first ;-). From a system
design point of view mixing different types of NICs on the same server
is not very good anyway.

Tom

One thing I am not sure how to deal with is flow control. i.e. if the
transmit queue is being blocked who should do the drop. Preferably,
we'd want the to know the queue occupancy in BPF to do an intelligent
drop (some crude fq-codel or the like?)
Flow control or push-back is an interesting problem to solve.


--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Designing the page-pool
=======================
:Version: 0.1.1
:Authors: Jesper Dangaard Brouer

Introduction
============

Motivation for page recycling is primarily performance related (due to
network stack use-cases), as bottlenecks exist in both the page
allocator and DMA APIs.

It was agreed at MM-summit 2016, that the ideas developed to speedup
the per CPU caching layer, should be integrated into the page
allocator, where possible. And we should try to share data
structures. (https://lwn.net/Articles/684616/)

The page-pool per device, still have merits, as it can:
1) solve the DMA API (IOMMU) overhead issue, which
2) in-directly make pages writable by network-stack,
3) provide a feedback-loop at the device level

Referring to MM-summit presentation, for the DMA use-case, and why
larger order pages are considered problematic.

MM-summit 2016 presentation avail here:
* http://people.netfilter.org/hawk/presentations/MM-summit2016/generic_page_pool_mm_summit2016.pdf


XDP (eXpress Data Path)
-----------------------

The page-pool is a component that XDP need in-order to perform packet
forwarding at the page level.

* https://github.com/iovisor/bpf-docs/raw/master/Express_Data_Path.pdf
* http://lwn.net/Articles/682538/


Avoid NUMA problems, return to same CPU
=======================================

A classical problem, especially for NUMA systems, is that in a
asymmetric workload memory can be allocated on one CPU but free'ed on
a remote CPU (worst-case a remote NUMA node). (Thus, CPU "local"
recycling on free is problematic).

Upfront, our design solves this issue, by requiring pages are recycled
back to the originating CPU. (This feature is also beneficial for the
feedback-loop and associated accounting.)


Reduce page (buddy) fragmentation
=================================

Another benefit of a page-pool layer on-top of a driver, which can
maintain a steady-state working-set, is that the page allocator have
less chances of getting fragmented.


Feedback loop
=============

With drivers current approach (of calling the page allocator directly)
the number of pages a driver can hand-out is unbounded.

The page-pool provide the ability to get a feedback loop facility, at
the device level.

A classical problem is that a single device can take up an unfair
large portion of the shared memory resources, if e.g. an application
(or guest VM) does not free the resources (fast-enough). Thus,
negatively impacting the entire system, possibly leading to
Out-Of-Memory (OOM) conditions.

The protection mechanism the page-pool can provide (at the device
level) MUST not be seen as a congestion-control mechanism. It should
be seen as a "circuit-breaker" last resort facility to protect other
parts of the system.

Congestion-control aware traffic usually handle the situation (and
adjust their rate to stabilize the network). Thus, a circuit-breaker
must allow sufficient time for congestion-control aware traffic to
stabilize.

The situations that are relevant for the circuit-breaker, are
excessive and persistent non-congestion-controlled traffic, that
affect other parts of the system.

Drop policy
-----------

When the circuit-breaker is in effect (e.g. dropping all packets and
recycling the page directly), then XDP/eBPF hook could decide to
change the drop verdict.

With the XDP hook in-place, it is possible to implement arbitrarily
drop policies. If the XDP hook, gets the RX HW-hash, then it can
implement flow based policies without touching packet data.


Detecting driver overload
-------------------------

It might be difficult to determine when the circuit-breaker should
kick-in, based on an excessive working-set size of pages.

But at the driver level, it is easy to detect when the system is
overloaded, to such an extend that it cannot process packets
fast-enough. This is simply indicated by the driver cannot empty the
RX queue fast-enough, thus HW is RX dropping packets (FIFO taildrop).

This indication could be passed to a XDP hook, which can implement a
drop policy. Filtering packets at this level can likely restore
normal system operation. Building on the principal of spending as few
CPU cycles as possible on packets that need to be dropped anyhow (by a
deeper layer).

It is important to realize that, dropping the the XDP driver level is
extremely efficient. Experiments show that, the filter capacity of
XDP filter is 14.8Mpps (DDIO touching packet and updating up an eBPF
map), while iptables-raw is 6Mpps, and hitting socket limit is around
0.7Mpps. Thus, an attacker can actually consume significant CPU
resources by simply sending UDP packets to a closed port.


Performance vs feedback-loop accounting
---------------------------------------

For performance reasons, the accounting should be kept as per CPU
structures.

For NIC drivers it actually makes sense to keep accounting 100% per
CPU. In essence, we would like the circuit-breaker to kick-in per RX
HW queue, as that would allow remaining RX queue traffic flow.

RX queues are usually bound to a specific CPU, to avoid packet
reordering (and NIC RSS hashing (try-to) keep flows per RX queue).
Thus, keeping page recycling and stats per CPU structures, basically
achieves the same as binding a page-pool per RX queue.

If RX queue SMP affinity change runtime, then it does not matter. A
RX ring-queue can contain pages "belonging" to another CPU, but it
does not matter, as eventually they will be returned to the owning
CPU.


It would be possible to also keep a more central state for a
page-pool, because the number of pages it manage only change when
(re)filling or returning pages to the page allocator, which should be
a more infrequent event. I would prefer not to.


Determining steady-state working-set
------------------------------------

For optimal performance and to minimize memory usage, the page-pool
should only maintain the number of pages required for the steady-state
working-set.

The size of the steady-state working-set will vary depending on the
workload. E.g. in a forwarding workload it will be fairly small.
E.g. for a TCP (local)host delivery workload it will be bigger. Thus,
the steady-state working-set should be dynamically determined.

Detecting steady-state by realizing, that in steady state, no
(re)filling have occurred for a while, and the number of "free" pages
in the pool is not excessive.

Idea: could we track number of page-pool recycle alloc and free's
within N x jiffies, and if the numbers (rate) are approx the same,
record number of outstanding pages as the steady-state number? (Could
be implemented as single signed counter reset every N jiffies, inc/dec
for alloc/free, approaching zero (at reset point) == stable)


If RX rate is bigger than TX/consumption rate, queue theory says a
queue will form. While the queue builds (somewhere outside out our
control), the page-pool need to request more and more pages from
page-allocator. The number of outstanding pages increase, seen from
the page-pool, proportional to the queue in the system.

This, RX > TX is an overload situation. Congestion-control aware
traffic will self stabilize. Assuming dealing with
non-congestion-controlled traffic, some different scenarios exist:

1. (good-queue) Overload only exist for a short period of time, like a
traffic burst. This is "good-queue", where we absorb bursts.

2. (bad-queue) Situation persists, but some other limit is hit, and
packets get dropped. Like qdisc limit on forwarding, or local
socket limit. This could be interpreted as a "steady-steady", as
page-recycling reach a certain level, and maybe it should?

3. (OOM) Situation persists, and no natural resource limit is hit.
Eventually system runs dry of memory pages and OOM. This situation
should be caught by our circuit-breaker mechanism, before OOM.

4. For forwarding, the hole code path from RX to TX, takes longer than
the packet arrival rate. Drops happen at HW level by overflowing
RX queue (as it is not emptied fast enough). Possible to detect
inside driver, and we could start a eBPF program to filter?

After an overload situation, when RX decrease (or stop), so RX < TX
(likely for a short period of time). Then, we have the opportunity to
return/free objects/pages back to the page-allocator.

Q: How quickly should we do so (return pages)?
Q: How much slack to handle bursts?
Q: Is "steady-state" number of pages an absolute limit?


XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).

The XDP eBPF hook can maintain it's own internal data structure, to
track pages.

We could saved the RX HW hash (maybe in struct-page), then eBPF could
implement flow metering without touching packet data.

The eBPF prog can even do it's own timestamping on RX and compare at
pool "return" point. Essentially implementing a CoDel like scheme,
measuring "time-spend-in-network-stack". (For this to make sense, it
would likely need to group by RX-HW-hash, as multiple ways through the
netstack exist, thus it cannot be viewed as a FIFO).


Conclusion
----------

The resource limitation/protection feature offered by the page-pool,
is primarily a circuit-breaker facility for protecting other parts of
the system. Combined with a XDP/eBPF hook, it offers a powerful and
more fine-grained control.

It requires more work and research if we want to react
"earlier". e.g. before the circuit-breaker kicks in. Here one should
be careful not to interfere with congestion aware traffic, by giving
it sufficient time to reach.

At the driver level it is also possible to detect, if system is not
processing RX packets fast-enough. This is not an inherent feature of
the page-pool, but it would be useful input for a eBPF filter.

For the XDP/eBPF hook, this means that it should take a "signal" as
input of how the current operating machine state is.

Considering the states:
* State:"circuit-breaker"- eBPF can choose to approve packets, else stack drop
* State:"RX-overload" - eBPF can choose to drop packets to restore operation

Relating to page allocator
==========================

The current page allocator have a per CPU caching layer for
order-0 pages, called PCP (per CPU pages) ::

struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
int batch; /* chunk size for buddy add/remove */

/* Lists of pages, one per migrate type stored on the pcp-lists */
struct list_head lists[MIGRATE_PCPTYPES];
};

The "high" watermark, can be compared to (dynamic) steady-state
number, which determine how many cached (order-0) pages are kept,
before they are returned to the page allocator.

For PCP once the "high" watermark is hit, then "batch" number of
pages are returned. (Using a batch (re)moves the pathological
case of two object working-set being recycles on the "edge" of
the "high" watermark, causing too much interaction with the page
alloactor).

On my 8 core (i7-4790K CPU @ 4.00GHz) with 16GB RAM, the values
for PCP are high=186 and batch=31 (note 31*6 = 186). These
setting are likely not optimal for networking, as e.g. TX DMA
completion is default allowed to freeing up-to 256 pages.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?


Background material
===================

Circuit Breaker
---------------

Quotes from:

.. _RFC-Circuit-Breaker:
https://tools.ietf.org/html/draft-ietf-tsvwg-circuit-breaker-14

RFC-Circuit-Breaker_ ::

[...] non-congestion-controlled traffic, including many applications
using the User Datagram Protocol (UDP), can form a significant
proportion of the total traffic traversing a link. The current
Internet therefore requires that non-congestion-controlled traffic is
considered to avoid persistent excessive congestion


RFC-Circuit-Breaker_ ::

This longer period is needed to provide sufficient time for transport
congestion control (or applications) to adjust their rate following
congestion, and for the network load to stabilize after any
adjustment.


RFC-Circuit-Breaker_ ::

In contrast, Circuit Breakers are recommended for non-congestion-
controlled Internet flows and for traffic aggregates, e.g., traffic
sent using a network tunnel. They operate on timescales much longer
than the packet RTT, and trigger under situations of abnormal
(excessive) congestion.


--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Thomas Monjalon <thomas.monjalon@...>
 

2016-05-04 12:47, Tom Herbert:
On Wed, May 4, 2016 at 11:13 AM, Jesper Dangaard Brouer
<brouer@...> wrote:
Tom Herbert <tom@...> wrote:
For forwarding on a non XDP queue (like 3B or crossing different type
devices) I don't think we should do anything special. Just pass the
packet to the stack like in the olden days and use the stack
forwarding path. This is obviously slow path, but not really very
interesting to optimize in XDP.
Yes for 3B.
For 3A I want to support cross device driver.
Maybe we can get basic forwarding to work first ;-). From a system
design point of view mixing different types of NICs on the same server
is not very good anyway.
Mixing NICs on a server is probably not common. But I wonder wether it
could allow to leverage different offload capabilities for an asymmetrical
traffic?
Please could you elaborate why mixing is not very good?


Tom Herbert <tom@...>
 

On Wed, May 4, 2016 at 12:55 PM, Thomas Monjalon
<thomas.monjalon@...> wrote:
2016-05-04 12:47, Tom Herbert:
On Wed, May 4, 2016 at 11:13 AM, Jesper Dangaard Brouer
<brouer@...> wrote:
Tom Herbert <tom@...> wrote:
For forwarding on a non XDP queue (like 3B or crossing different type
devices) I don't think we should do anything special. Just pass the
packet to the stack like in the olden days and use the stack
forwarding path. This is obviously slow path, but not really very
interesting to optimize in XDP.
Yes for 3B.
For 3A I want to support cross device driver.
Maybe we can get basic forwarding to work first ;-). From a system
design point of view mixing different types of NICs on the same server
is not very good anyway.
Mixing NICs on a server is probably not common. But I wonder wether it
could allow to leverage different offload capabilities for an asymmetrical
traffic?
Maybe, but it's a lot of complexity. Do you have a specific use case in mind?

Please could you elaborate why mixing is not very good?
Harder to design, test, don't see much value in it. Supporting such
things forces us to continually raise the abstraction and generalize
interfaces more and more which is exactly how we wind up with things
like 400 bytes skbuffs, locking, soft queues, etc. XDP is expressly
not meant to be a general solution, and that gives us liberty to cut
out anything that doesn't yield performance like trying to preserve a
high performance interface between two arbitrary drivers (but still
addressing the 90% case).


Alexei Starovoitov
 

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
More sophisticated selection of ifindex and/or tx queue can be built
on top.

Avoid NUMA problems, return to same CPU
I think at this stage the numa part can be ignored.
We should assume one socket and deal with numa later,
since such things are out of bpf control and not part of
API that we need to stabilize right now.
We may have some sysctl knobs or ethtool in the future.

For performance reasons, the accounting should be kept as per CPU
structures.
In general that's absolutely correct, but by default XDP should
not have any counters. It's up to the program to keep the stats
on number of dropped packets. Thankfully per-cpu hash maps
already exist.

XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).
I think we don't have cycles to do anything sophisticated
at 'pool return' point. Something like hard limit (ethtool configurable)
on number of recycle-able pages should be good enough.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?
I think we'll try to pick the good default for most of the use cases,
but ultimately it's another knob. If program processing time
is high, the user would have to increase this knob to keep
all pages in the recycle-able pool instead of talking to
main page-allocator. Even when this knob is not optimal,
the performance will still be acceptable, since the cost
of page_alloc+mmap-s will be amortized.


Tom Herbert <tom@...>
 

On Wed, May 4, 2016 at 10:22 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
I'm not sure what this means. In XDP the driver should not be making
any decisions (i.e. driver does not implement any). If there is a
choice of TX queue that should be made by the BPF code. Maybe for the
first instantiation there is only one queue and BPF always returns
index of zero-- this will be sufficient for most L4 load balancers and
ILA router.

Tom

More sophisticated selection of ifindex and/or tx queue can be built
on top.

Avoid NUMA problems, return to same CPU
I think at this stage the numa part can be ignored.
We should assume one socket and deal with numa later,
since such things are out of bpf control and not part of
API that we need to stabilize right now.
We may have some sysctl knobs or ethtool in the future.

For performance reasons, the accounting should be kept as per CPU
structures.
In general that's absolutely correct, but by default XDP should
not have any counters. It's up to the program to keep the stats
on number of dropped packets. Thankfully per-cpu hash maps
already exist.

XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).
I think we don't have cycles to do anything sophisticated
at 'pool return' point. Something like hard limit (ethtool configurable)
on number of recycle-able pages should be good enough.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?
I think we'll try to pick the good default for most of the use cases,
but ultimately it's another knob. If program processing time
is high, the user would have to increase this knob to keep
all pages in the recycle-able pool instead of talking to
main page-allocator. Even when this knob is not optimal,
the performance will still be acceptable, since the cost
of page_alloc+mmap-s will be amortized.


Alexei Starovoitov
 

On Thu, May 05, 2016 at 10:06:40AM -0700, Tom Herbert wrote:
On Wed, May 4, 2016 at 10:22 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
I'm not sure what this means. In XDP the driver should not be making
any decisions (i.e. driver does not implement any). If there is a
choice of TX queue that should be made by the BPF code. Maybe for the
first instantiation there is only one queue and BPF always returns
index of zero-- this will be sufficient for most L4 load balancers and
ILA router.
There are always multiple rx and tx queues.
It makes the program portable across different nics and hw configuration
when it doesn't know rx queue number and doesn't make decision about tx queues.
I don't see a use case for selecting tx queue. The driver side
should be making this decision to make sure the performance is optimal
and everything is lock-less. Like it can allocate N+M TX queues and N RX
queues where N is multiple of cpu count and use M TX queues for normal
tcp stack tx traffic. Then everything is collision free and lockless.


Tom Herbert <tom@...>
 

On Thu, May 5, 2016 at 10:41 AM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Thu, May 05, 2016 at 10:06:40AM -0700, Tom Herbert wrote:
On Wed, May 4, 2016 at 10:22 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
I'm not sure what this means. In XDP the driver should not be making
any decisions (i.e. driver does not implement any). If there is a
choice of TX queue that should be made by the BPF code. Maybe for the
first instantiation there is only one queue and BPF always returns
index of zero-- this will be sufficient for most L4 load balancers and
ILA router.
There are always multiple rx and tx queues.
It makes the program portable across different nics and hw configuration
when it doesn't know rx queue number and doesn't make decision about tx queues.
I don't see a use case for selecting tx queue. The driver side
should be making this decision to make sure the performance is optimal
and everything is lock-less. Like it can allocate N+M TX queues and N RX
queues where N is multiple of cpu count and use M TX queues for normal
tcp stack tx traffic. Then everything is collision free and lockless.
Right, the TX queues used by the stack need to be completely
independent of those used by XDP. If an XDP instance (e.g. an RX
queue) has exclusive access to a TX queue there is no locking and no
collisions. Neither is there any need for the instance to transmit on
multiple queues except in the case that the different COS is offered
by different queues (e.g. priority), but again COS would be decided by
the BPF not the driver. In other words, for XDP we need one TX queue
per COS per each instance (RX queue) of XDP. There should be at most
one RX queue serviced per CPU also.

Tom


Jesper Dangaard Brouer
 

On Thu, 5 May 2016 11:01:52 -0700
Tom Herbert <tom@...> wrote:

On Thu, May 5, 2016 at 10:41 AM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Thu, May 05, 2016 at 10:06:40AM -0700, Tom Herbert wrote:
On Wed, May 4, 2016 at 10:22 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
I'm not sure what this means. In XDP the driver should not be making
any decisions (i.e. driver does not implement any). If there is a
choice of TX queue that should be made by the BPF code. Maybe for the
first instantiation there is only one queue and BPF always returns
index of zero-- this will be sufficient for most L4 load balancers and
ILA router.
There are always multiple rx and tx queues.
It makes the program portable across different nics and hw configuration
when it doesn't know rx queue number and doesn't make decision about tx queues.
I don't see a use case for selecting tx queue. The driver side
should be making this decision to make sure the performance is optimal
and everything is lock-less. Like it can allocate N+M TX queues and N RX
queues where N is multiple of cpu count and use M TX queues for normal
tcp stack tx traffic. Then everything is collision free and lockless.
Right, the TX queues used by the stack need to be completely
independent of those used by XDP. If an XDP instance (e.g. an RX
queue) has exclusive access to a TX queue there is no locking and no
collisions. Neither is there any need for the instance to transmit on
multiple queues except in the case that the different COS is offered
by different queues (e.g. priority), but again COS would be decided by
the BPF not the driver. In other words, for XDP we need one TX queue
per COS per each instance (RX queue) of XDP. There should be at most
one RX queue serviced per CPU also.
I almost agree, but there are some details ;-)

Yes, for XDP-TX we likely cannot piggy-back on the normal stack TX
queues (like we do on the RX queues). Thus, when a driver support the
XDP-TX feature, they need to provide some more TX queue's for XDP. For
lockless TX I assume we need a XDP-TX queue per CPU.

The way I understand you, you want the BPF program to choose the TX
queue number. I disagree, as BPF should have no knowledge about TX
queue numbers. (It would be hard to get lockless TX queue's if BPF
program chooses). IMHO the BPF program can choose the egress netdevice
(e.g. via ifindex). Then we call the NDO "XDP-page-fwd", inside that
call, the actual TX queue is chosen based on the current-running-CPU
(maybe simply via a this_cpu_xxx call).


Getting TX queues lockless, have one problem: TX DMA completion
interrupts. Today TX completion, "cleanup" of TX ring-queue can run on
another CPU. This breaks the lockless scheme. We need deal with this
somehow, and setup our XDP-TX-queue "more-strict" somehow from the
kernel side, and not allow userspace to change smp_affinity (simply
chmod the proc file ;-)).

--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Jesper Dangaard Brouer
 

On Wed, 4 May 2016 22:22:07 -0700
Alexei Starovoitov <alexei.starovoitov@...> wrote:

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
More sophisticated selection of ifindex and/or tx queue can be built
on top.
I agree that driver choose TX queue to use to avoid conflicts, allowing
lockless access.

I think XDP/BPF "forward"-mode" should always select an egress/TX
ifindex/netdevice. If the ifindex happen to match the driver itself,
then driver can to the superfast TX into a driver TX-ring queue. But
if the ifindex is for another device (that does not support this) then
we fallback to full-SKB alloc and normal stack TX towards that
ifindex/netdevice (likely bypassing the rx_handler).


Avoid NUMA problems, return to same CPU
I think at this stage the numa part can be ignored.
We should assume one socket and deal with numa later,
since such things are out of bpf control and not part of
API that we need to stabilize right now.
We may have some sysctl knobs or ethtool in the future.
You misunderstood me. This was about the page-pool design. It
absolutely needs this "return _page_ to same CPU". Don't worry about
this part.


For performance reasons, the accounting should be kept as per CPU
structures.
In general that's absolutely correct, but by default XDP should
not have any counters. It's up to the program to keep the stats
on number of dropped packets. Thankfully per-cpu hash maps
already exist.
Also think you misunderstood me here. This is also about the page-pool
design. Of-cause, the XDP should not have any counters.


XDP pool return hook
--------------------

What about allowing a eBPF hook at page-pool "return" point? That
would allow eBPF to function as an "egress" meter (in circuit-breaker
terminology).
I think we don't have cycles to do anything sophisticated
at 'pool return' point. Something like hard limit (ethtool configurable)
on number of recycle-able pages should be good enough.

The question is, whether the PCP "high" watermark could be
dynamically determined by the same method proposed for
determining the steady-state criteria?
I think we'll try to pick the good default for most of the use cases,
but ultimately it's another knob. If program processing time
is high, the user would have to increase this knob to keep
all pages in the recycle-able pool instead of talking to
main page-allocator. Even when this knob is not optimal,
the performance will still be acceptable, since the cost
of page_alloc+mmap-s will be amortized.
Also think you misunderstood me here. This was about bringing some of
the ideas from the page-pool into the page allocator itself. In
general I'm very much against adding more knobs to the kernel. It have
become one of the big pitfalls of the kernel.

--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Tom Herbert <tom@...>
 

On Thu, May 5, 2016 at 12:11 PM, Jesper Dangaard Brouer
<brouer@...> wrote:
On Thu, 5 May 2016 11:01:52 -0700
Tom Herbert <tom@...> wrote:

On Thu, May 5, 2016 at 10:41 AM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Thu, May 05, 2016 at 10:06:40AM -0700, Tom Herbert wrote:
On Wed, May 4, 2016 at 10:22 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
I'm not sure what this means. In XDP the driver should not be making
any decisions (i.e. driver does not implement any). If there is a
choice of TX queue that should be made by the BPF code. Maybe for the
first instantiation there is only one queue and BPF always returns
index of zero-- this will be sufficient for most L4 load balancers and
ILA router.
There are always multiple rx and tx queues.
It makes the program portable across different nics and hw configuration
when it doesn't know rx queue number and doesn't make decision about tx queues.
I don't see a use case for selecting tx queue. The driver side
should be making this decision to make sure the performance is optimal
and everything is lock-less. Like it can allocate N+M TX queues and N RX
queues where N is multiple of cpu count and use M TX queues for normal
tcp stack tx traffic. Then everything is collision free and lockless.
Right, the TX queues used by the stack need to be completely
independent of those used by XDP. If an XDP instance (e.g. an RX
queue) has exclusive access to a TX queue there is no locking and no
collisions. Neither is there any need for the instance to transmit on
multiple queues except in the case that the different COS is offered
by different queues (e.g. priority), but again COS would be decided by
the BPF not the driver. In other words, for XDP we need one TX queue
per COS per each instance (RX queue) of XDP. There should be at most
one RX queue serviced per CPU also.
I almost agree, but there are some details ;-)

Yes, for XDP-TX we likely cannot piggy-back on the normal stack TX
queues (like we do on the RX queues). Thus, when a driver support the
XDP-TX feature, they need to provide some more TX queue's for XDP. For
lockless TX I assume we need a XDP-TX queue per CPU.

The way I understand you, you want the BPF program to choose the TX
queue number. I disagree, as BPF should have no knowledge about TX
queue numbers. (It would be hard to get lockless TX queue's if BPF
program chooses). IMHO the BPF program can choose the egress netdevice
(e.g. via ifindex). Then we call the NDO "XDP-page-fwd", inside that
call, the actual TX queue is chosen based on the current-running-CPU
(maybe simply via a this_cpu_xxx call).
I think we're saying the same the thing just using different notation.
BPF program returns an index which the driver maps to a queue, but
this index is relative to XDP instance. So if a device offers 3 levels
priority queues then BPF program can return 0,1, or 2. The driver can
map this return value to a queue (probably from a set of three queues
dedicated to the XDP instance). What I am saying is that this driver
mapping should be trivial and does not implement any policy other than
restricting the XDP instance to its set-- like mapping to actual queue
number could be 3*N+R where N in instance # of XDP and R is return
index. Egress on a different interface can work the same way, for
instance 0 index might queue for local interface, 1 index might queue
for interface. This simple return value to queue mapping is lot easier
for crossing devices if they are managed by the same driver I think.


Getting TX queues lockless, have one problem: TX DMA completion
interrupts. Today TX completion, "cleanup" of TX ring-queue can run on
another CPU. This breaks the lockless scheme. We need deal with this
somehow, and setup our XDP-TX-queue "more-strict" somehow from the
kernel side, and not allow userspace to change smp_affinity (simply
chmod the proc file ;-)).
Hmm, how does DPDK deal with this? Hopefully you wouldn't need an
actual lock for this either, atomic ops on producer/consumer pointers
should work for most devices?

Tom

--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer


Thomas Monjalon <thomas.monjalon@...>
 

2016-05-04 14:01, Tom Herbert:
On Wed, May 4, 2016 at 12:55 PM, Thomas Monjalon
<thomas.monjalon@...> wrote:
2016-05-04 12:47, Tom Herbert:
Maybe we can get basic forwarding to work first ;-). From a system
design point of view mixing different types of NICs on the same server
is not very good anyway.
Mixing NICs on a server is probably not common. But I wonder wether it
could allow to leverage different offload capabilities for an asymmetrical
traffic?
Maybe, but it's a lot of complexity. Do you have a specific use case in mind?
No real use case now but offload in NICs are becoming more and more complex
and really different depending of the vendor.
I think tunnel encapsulation offload use case is becoming real.
We can also think to different flow steering depending of the tunnel type.

Please could you elaborate why mixing is not very good?
Harder to design, test, don't see much value in it. Supporting such
things forces us to continually raise the abstraction and generalize
interfaces more and more which is exactly how we wind up with things
like 400 bytes skbuffs, locking, soft queues, etc. XDP is expressly
not meant to be a general solution, and that gives us liberty to cut
out anything that doesn't yield performance like trying to preserve a
high performance interface between two arbitrary drivers (but still
addressing the 90% case).
Interesting point of view. Thanks


Tom Herbert <tom@...>
 

On Thu, May 5, 2016 at 1:46 PM, Thomas Monjalon
<thomas.monjalon@...> wrote:
2016-05-04 14:01, Tom Herbert:
On Wed, May 4, 2016 at 12:55 PM, Thomas Monjalon
<thomas.monjalon@...> wrote:
2016-05-04 12:47, Tom Herbert:
Maybe we can get basic forwarding to work first ;-). From a system
design point of view mixing different types of NICs on the same server
is not very good anyway.
Mixing NICs on a server is probably not common. But I wonder wether it
could allow to leverage different offload capabilities for an asymmetrical
traffic?
Maybe, but it's a lot of complexity. Do you have a specific use case in mind?
No real use case now but offload in NICs are becoming more and more complex
and really different depending of the vendor.
We're trying hard to discourage vendors from doing that. All these
complex HW offloads aren't helping matters! (e.g. see the continuing
saga of getting vendors to give us protocol generic checksum
offload...). Other than checksum offload and RSS, I'm not seeing much
we can leverage from the HW offloads for XDP. Of course when can
offload the BPF program to HW that might be a different story.

I think tunnel encapsulation offload use case is becoming real.
We can also think to different flow steering depending of the tunnel type.
Won't we be able to implement encap/decap in XDP just as easily but in
a way that is completely user programmable?

Tom


Please could you elaborate why mixing is not very good?
Harder to design, test, don't see much value in it. Supporting such
things forces us to continually raise the abstraction and generalize
interfaces more and more which is exactly how we wind up with things
like 400 bytes skbuffs, locking, soft queues, etc. XDP is expressly
not meant to be a general solution, and that gives us liberty to cut
out anything that doesn't yield performance like trying to preserve a
high performance interface between two arbitrary drivers (but still
addressing the 90% case).
Interesting point of view. Thanks


Alexei Starovoitov
 

On Thu, May 05, 2016 at 01:19:37PM -0700, Tom Herbert wrote:
I think we're saying the same the thing just using different notation.
BPF program returns an index which the driver maps to a queue, but
this index is relative to XDP instance. So if a device offers 3 levels
priority queues then BPF program can return 0,1, or 2. The driver can
map this return value to a queue (probably from a set of three queues
dedicated to the XDP instance). What I am saying is that this driver
mapping should be trivial and does not implement any policy other than
restricting the XDP instance to its set-- like mapping to actual queue
number could be 3*N+R where N in instance # of XDP and R is return
index. Egress on a different interface can work the same way, for
instance 0 index might queue for local interface, 1 index might queue
for interface. This simple return value to queue mapping is lot easier
for crossing devices if they are managed by the same driver I think.
+1
we'd need a way to specify priority queue from bpf program.
Probably not as a first step though.
Something like
BPF_XDP_DROP 0
BPF_XDP_PASS 1
BPF_XDP_TX 2
BPF_XDP_TX_PRIO 3 | upper bits used for prio
BPF_XDP_TX_PHYS_IFINDEX 4 | upper bits for ifindex
BPF_XDP_RX_NETDEV_IFINDEX 5 | upper bits for ifindex of veth or any netdev
lower 8-bits to encode action should be enough.
First merge-able step is to do 0,1,2 in one driver (like mlx4) and
start building it in other drivers.


Alexei Starovoitov
 

On Thu, May 05, 2016 at 09:32:32PM +0200, Jesper Dangaard Brouer wrote:
On Wed, 4 May 2016 22:22:07 -0700
Alexei Starovoitov <alexei.starovoitov@...> wrote:

On Wed, May 4, 2016 at 2:15 AM, Jesper Dangaard Brouer
<brouer@...> wrote:

I've started a separate document for designing my page-pool idea.

I see the page-pool as a component, for allowing fast forwarding with
XDP, at the packet-page level, cross device.

I want your input on how you imagine XDP/eBPF forwarding would work?
I could imagine,
1) eBPF returns an ifindex it want to forward to,
2) look if netdevice supports new NDO for XDP-page-fwd
3A) call XDP-page-fwd with packet-page,
3B) No XDP-page-fwd, then construct SKB and xmit directly on device,
4) (for both above cases) later at TX-DMA completion, return to page-pool.
I think the first step is option 0 where program will return
single return code 'TX' and driver side will figure out which tx queue
to use to avoid conflicts.
More sophisticated selection of ifindex and/or tx queue can be built
on top.
I agree that driver choose TX queue to use to avoid conflicts, allowing
lockless access.

I think XDP/BPF "forward"-mode" should always select an egress/TX
ifindex/netdevice. If the ifindex happen to match the driver itself,
then driver can to the superfast TX into a driver TX-ring queue. But
if the ifindex is for another device (that does not support this) then
we fallback to full-SKB alloc and normal stack TX towards that
ifindex/netdevice (likely bypassing the rx_handler).
NO. See my ongoing rant on performance vs generality.
'then it looks so generic and nice' arguments are not applicable to XDP.
Even if ifindex check didn't cost any performance, it still doesn't
make sense to do it, since ifindex is dynamic, so the program
would need to be tailored for specific ifindex. Either compiled
on-the-fly when ifindex is known or extra map lookup to figure out
which ifindex to use. For load balancer/ila router use cases it's
unnecessary, so program will not be dealing with ifindex.


Daniel Borkmann
 

On 05/05/2016 11:44 PM, Alexei Starovoitov via iovisor-dev wrote:
On Thu, May 05, 2016 at 01:19:37PM -0700, Tom Herbert wrote:
I think we're saying the same the thing just using different notation.
BPF program returns an index which the driver maps to a queue, but
this index is relative to XDP instance. So if a device offers 3 levels
priority queues then BPF program can return 0,1, or 2. The driver can
map this return value to a queue (probably from a set of three queues
dedicated to the XDP instance). What I am saying is that this driver
mapping should be trivial and does not implement any policy other than
restricting the XDP instance to its set-- like mapping to actual queue
number could be 3*N+R where N in instance # of XDP and R is return
index. Egress on a different interface can work the same way, for
instance 0 index might queue for local interface, 1 index might queue
for interface. This simple return value to queue mapping is lot easier
for crossing devices if they are managed by the same driver I think.
+1
we'd need a way to specify priority queue from bpf program.
Probably not as a first step though.
Something like
BPF_XDP_DROP 0
BPF_XDP_PASS 1
BPF_XDP_TX 2
BPF_XDP_TX_PRIO 3 | upper bits used for prio
BPF_XDP_TX_PHYS_IFINDEX 4 | upper bits for ifindex
BPF_XDP_RX_NETDEV_IFINDEX 5 | upper bits for ifindex of veth or any netdev
lower 8-bits to encode action should be enough.
First merge-able step is to do 0,1,2 in one driver (like mlx4) and
start building it in other drivers.
Can't this be done in a second step, with some per-cpu scratch data
as we have for redirect? That would seem easier to use to me, and easier
to extend with further data required to tx or rx to stack ... The return
code could have a flag to tell to look at the scratch data, for example.


Alexei Starovoitov
 

On Fri, May 06, 2016 at 12:00:57AM +0200, Daniel Borkmann wrote:
On 05/05/2016 11:44 PM, Alexei Starovoitov via iovisor-dev wrote:
On Thu, May 05, 2016 at 01:19:37PM -0700, Tom Herbert wrote:
I think we're saying the same the thing just using different notation.
BPF program returns an index which the driver maps to a queue, but
this index is relative to XDP instance. So if a device offers 3 levels
priority queues then BPF program can return 0,1, or 2. The driver can
map this return value to a queue (probably from a set of three queues
dedicated to the XDP instance). What I am saying is that this driver
mapping should be trivial and does not implement any policy other than
restricting the XDP instance to its set-- like mapping to actual queue
number could be 3*N+R where N in instance # of XDP and R is return
index. Egress on a different interface can work the same way, for
instance 0 index might queue for local interface, 1 index might queue
for interface. This simple return value to queue mapping is lot easier
for crossing devices if they are managed by the same driver I think.
+1
we'd need a way to specify priority queue from bpf program.
Probably not as a first step though.
Something like
BPF_XDP_DROP 0
BPF_XDP_PASS 1
BPF_XDP_TX 2
BPF_XDP_TX_PRIO 3 | upper bits used for prio
BPF_XDP_TX_PHYS_IFINDEX 4 | upper bits for ifindex
BPF_XDP_RX_NETDEV_IFINDEX 5 | upper bits for ifindex of veth or any netdev
lower 8-bits to encode action should be enough.
First merge-able step is to do 0,1,2 in one driver (like mlx4) and
start building it in other drivers.
Can't this be done in a second step, with some per-cpu scratch data
as we have for redirect? That would seem easier to use to me, and easier
to extend with further data required to tx or rx to stack ... The return
code could have a flag to tell to look at the scratch data, for example.
yes. 3,4,5,6,7,.. code can look at per-cpu scratch data too.
My point that for step one we define semantic for opcodes 0,1,2 in
the first 8 bits of return value. Everything else is reserved and
defaults to drop.


Daniel Borkmann
 

On 05/06/2016 12:04 AM, Alexei Starovoitov wrote:
On Fri, May 06, 2016 at 12:00:57AM +0200, Daniel Borkmann wrote:
On 05/05/2016 11:44 PM, Alexei Starovoitov via iovisor-dev wrote:
On Thu, May 05, 2016 at 01:19:37PM -0700, Tom Herbert wrote:
I think we're saying the same the thing just using different notation.
BPF program returns an index which the driver maps to a queue, but
this index is relative to XDP instance. So if a device offers 3 levels
priority queues then BPF program can return 0,1, or 2. The driver can
map this return value to a queue (probably from a set of three queues
dedicated to the XDP instance). What I am saying is that this driver
mapping should be trivial and does not implement any policy other than
restricting the XDP instance to its set-- like mapping to actual queue
number could be 3*N+R where N in instance # of XDP and R is return
index. Egress on a different interface can work the same way, for
instance 0 index might queue for local interface, 1 index might queue
for interface. This simple return value to queue mapping is lot easier
for crossing devices if they are managed by the same driver I think.
+1
we'd need a way to specify priority queue from bpf program.
Probably not as a first step though.
Something like
BPF_XDP_DROP 0
BPF_XDP_PASS 1
BPF_XDP_TX 2
BPF_XDP_TX_PRIO 3 | upper bits used for prio
BPF_XDP_TX_PHYS_IFINDEX 4 | upper bits for ifindex
BPF_XDP_RX_NETDEV_IFINDEX 5 | upper bits for ifindex of veth or any netdev
lower 8-bits to encode action should be enough.
First merge-able step is to do 0,1,2 in one driver (like mlx4) and
start building it in other drivers.
Can't this be done in a second step, with some per-cpu scratch data
as we have for redirect? That would seem easier to use to me, and easier
to extend with further data required to tx or rx to stack ... The return
code could have a flag to tell to look at the scratch data, for example.
yes. 3,4,5,6,7,.. code can look at per-cpu scratch data too.
My point that for step one we define semantic for opcodes 0,1,2 in
the first 8 bits of return value. Everything else is reserved and
defaults to drop.
Yep, first step with opcodes 0=drop, 1=pass/stack, 2=tx/fwd defined sounds
reasonable to me with rest as drop.