[PATCH] d80211: add ieee80211_stop_queues()

[PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

Add ieee80211_stop_queues() to stop all queues
with a single call.
I will submit a patch for bcm43xx to use this function
as soon as this got merged.

Signed-off-by: Michael Buesch <mb@bu3sch.de>

Index: wireless-dev/include/net/d80211.h
===================================================================
--- wireless-dev.orig/include/net/d80211.h	2006-08-19 18:26:05.000000000 +0200
+++ wireless-dev/include/net/d80211.h	2006-08-23 13:38:41.000000000 +0200
@@ -826,6 +826,15 @@
 void ieee80211_start_queues(struct net_device *dev);
 
 /**
+ * ieee80211_stop_queues - stop all queues
+ * @dev: pointer to $struct net_device as obtained from
+ *       ieee80211_alloc_hw().
+ *
+ * Drivers should use this function instead of netif_stop_queue.
+ */
+void ieee80211_stop_queues(struct net_device *dev);
+
+/**
  * ieee80211_get_mc_list_item - iteration over items in multicast list
  * @dev: pointer to &struct net_device as obtained from
  *	ieee80211_alloc_hw().
Index: wireless-dev/net/d80211/ieee80211.c
===================================================================
--- wireless-dev.orig/net/d80211/ieee80211.c	2006-08-19 18:26:05.000000000 +0200
+++ wireless-dev/net/d80211/ieee80211.c	2006-08-23 13:41:34.000000000 +0200
@@ -4690,6 +4690,15 @@
 		clear_bit(IEEE80211_LINK_STATE_XOFF, &local->state[i]);
 }
 
+void ieee80211_stop_queues(struct net_device *dev)
+{
+	struct ieee80211_local *local = dev->ieee80211_ptr;
+	int i;
+
+	for (i = 0; i < local->hw->queues; i++)
+		ieee80211_stop_queue(dev, i);
+}
+
 void * ieee80211_dev_hw_data(struct net_device *dev)
 {
 	struct ieee80211_local *local = dev->ieee80211_ptr;
@@ -4819,6 +4828,7 @@
 EXPORT_SYMBOL(ieee80211_wake_queue);
 EXPORT_SYMBOL(ieee80211_stop_queue);
 EXPORT_SYMBOL(ieee80211_start_queues);
+EXPORT_SYMBOL(ieee80211_stop_queues);
 EXPORT_SYMBOL(ieee80211_dev_hw_data);
 EXPORT_SYMBOL(ieee80211_dev_stats);
 EXPORT_SYMBOL(ieee80211_get_hw_conf);

-- 
Greetings Michael.

RE: [PATCH] d80211: add ieee80211_stop_queues()

[Simon Barber]

One question - in most hardware implementations today the queues are DMA
rings. In this case the right length of the queue is determined by the
interrupt/tx_softirq latency required to keep the queue from becoming
empty. With 802.11 there are large differences in the time it takes to
transmit different frames - a full size 1Mbit frame vs. a short 54Mbit
frame. Would it be worth optimizing the DMA queue length to be a
function of the amount of time rather than number of frames?

Simon


-----Original Message-----
From: netdev-owner@vger.kernel.org [mailto:netdev-owner@vger.kernel.org]
On Behalf Of Michael Buesch
Sent: Wednesday, August 23, 2006 4:44 AM
To: Jiri Benc
Cc: linville@tuxdriver.com; netdev@vger.kernel.org
Subject: [PATCH] d80211: add ieee80211_stop_queues()

Add ieee80211_stop_queues() to stop all queues with a single call.
I will submit a patch for bcm43xx to use this function as soon as this
got merged.

Signed-off-by: Michael Buesch <mb@bu3sch.de>

Index: wireless-dev/include/net/d80211.h
===================================================================
--- wireless-dev.orig/include/net/d80211.h	2006-08-19
18:26:05.000000000 +0200
+++ wireless-dev/include/net/d80211.h	2006-08-23 13:38:41.000000000
+0200
@@ -826,6 +826,15 @@
 void ieee80211_start_queues(struct net_device *dev);
 
 /**
+ * ieee80211_stop_queues - stop all queues
+ * @dev: pointer to $struct net_device as obtained from
+ *       ieee80211_alloc_hw().
+ *
+ * Drivers should use this function instead of netif_stop_queue.
+ */
+void ieee80211_stop_queues(struct net_device *dev);
+
+/**
  * ieee80211_get_mc_list_item - iteration over items in multicast list
  * @dev: pointer to &struct net_device as obtained from
  *	ieee80211_alloc_hw().
Index: wireless-dev/net/d80211/ieee80211.c
===================================================================
--- wireless-dev.orig/net/d80211/ieee80211.c	2006-08-19
18:26:05.000000000 +0200
+++ wireless-dev/net/d80211/ieee80211.c	2006-08-23 13:41:34.000000000
+0200
@@ -4690,6 +4690,15 @@
 		clear_bit(IEEE80211_LINK_STATE_XOFF, &local->state[i]);
}
 
+void ieee80211_stop_queues(struct net_device *dev) {
+	struct ieee80211_local *local = dev->ieee80211_ptr;
+	int i;
+
+	for (i = 0; i < local->hw->queues; i++)
+		ieee80211_stop_queue(dev, i);
+}
+
 void * ieee80211_dev_hw_data(struct net_device *dev)  {
 	struct ieee80211_local *local = dev->ieee80211_ptr; @@ -4819,6
+4828,7 @@  EXPORT_SYMBOL(ieee80211_wake_queue);
 EXPORT_SYMBOL(ieee80211_stop_queue);
 EXPORT_SYMBOL(ieee80211_start_queues);
+EXPORT_SYMBOL(ieee80211_stop_queues);
 EXPORT_SYMBOL(ieee80211_dev_hw_data);
 EXPORT_SYMBOL(ieee80211_dev_stats);
 EXPORT_SYMBOL(ieee80211_get_hw_conf);

--
Greetings Michael.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in the
body of a message to majordomo@vger.kernel.org More majordomo info at
http://vger.kernel.org/majordomo-info.html

Re: [PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

On Wednesday 23 August 2006 21:30, Simon Barber wrote:
> One question - in most hardware implementations today the queues are DMA
> rings. In this case the right length of the queue is determined by the
> interrupt/tx_softirq latency required to keep the queue from becoming
> empty. With 802.11 there are large differences in the time it takes to
> transmit different frames - a full size 1Mbit frame vs. a short 54Mbit
> frame. Would it be worth optimizing the DMA queue length to be a
> function of the amount of time rather than number of frames?

I doubt that the added complexity would do any good.
We should look at what a ring actually is.
A ring is an allocated memory space with dma descriptors in it.
The ring size if the number of dma descriptors. So theoretically
the number of descriptors adds up to the size to allocate.
In practice we have alignment issues (at least for bcm43xx).
For a ring we always allocate one page of memory. Regardless
of how much of it is actually used by descriptors.
One wireless-specific thing remains, though. We store meta
data for each descriptor (The ieee80211_tx_control at least).
So basically only the memory consumption of the meta data
could be optimized.

We used to have 512 TX descriptors for each ring until I recently
submitted a patch to lower it to 128. I did this because after
doing stress tests the maximum amount of used descriptors did
not go over about 80 on my machines.

I think it basically comes down to the question:
Do we want to save 1 kb of memory[*] but pay the price of
additional code complexity?

[*] 1kb is a random value invented by me. I did not calculate
    it, but it should be somewhere around that value.

-- 
Greetings Michael.

RE: [PATCH] d80211: add ieee80211_stop_queues()

[Simon Barber]

I'd agree the memory benefit is not worth the work and complexity. The
additional benefit is tighter queue control - reducing the latency
between the software qdisc (and whatever scheduling/rate controlling/etc
work they are doing) and the frames coming out of the hardware. A 100
frame DMA queue can be 1.2 seconds of transmit time, or it can be 30ms
of transmit time depending on frame size and transmission rate. This
disparity will only get larger as rates go up with 11n.

A further benefit in reducing this latency - is to keep the latency
between the software rate control algorithm (which sees frames before
they hit the DMA queue) and the hardware tx down. This allows the
software rate control to be more responsive.

Simon

-----Original Message-----
From: Michael Buesch [mailto:mb@bu3sch.de] 
Sent: Wednesday, August 23, 2006 12:45 PM
To: Simon Barber
Cc: Jiri Benc; linville@tuxdriver.com; netdev@vger.kernel.org
Subject: Re: [PATCH] d80211: add ieee80211_stop_queues()

On Wednesday 23 August 2006 21:30, Simon Barber wrote:
> One question - in most hardware implementations today the queues are 
> DMA rings. In this case the right length of the queue is determined by

> the interrupt/tx_softirq latency required to keep the queue from 
> becoming empty. With 802.11 there are large differences in the time it

> takes to transmit different frames - a full size 1Mbit frame vs. a 
> short 54Mbit frame. Would it be worth optimizing the DMA queue length 
> to be a function of the amount of time rather than number of frames?

I doubt that the added complexity would do any good.
We should look at what a ring actually is.
A ring is an allocated memory space with dma descriptors in it.
The ring size if the number of dma descriptors. So theoretically the
number of descriptors adds up to the size to allocate.
In practice we have alignment issues (at least for bcm43xx).
For a ring we always allocate one page of memory. Regardless of how much
of it is actually used by descriptors.
One wireless-specific thing remains, though. We store meta data for each
descriptor (The ieee80211_tx_control at least).
So basically only the memory consumption of the meta data could be
optimized.

We used to have 512 TX descriptors for each ring until I recently
submitted a patch to lower it to 128. I did this because after doing
stress tests the maximum amount of used descriptors did not go over
about 80 on my machines.

I think it basically comes down to the question:
Do we want to save 1 kb of memory[*] but pay the price of additional
code complexity?

[*] 1kb is a random value invented by me. I did not calculate
    it, but it should be somewhere around that value.

--
Greetings Michael.

Re: [PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

On Wednesday 23 August 2006 21:54, Simon Barber wrote:
> I'd agree the memory benefit is not worth the work and complexity. The
> additional benefit is tighter queue control - reducing the latency
> between the software qdisc (and whatever scheduling/rate controlling/etc
> work they are doing) and the frames coming out of the hardware. A 100
> frame DMA queue can be 1.2 seconds of transmit time, or it can be 30ms
> of transmit time depending on frame size and transmission rate. This
> disparity will only get larger as rates go up with 11n.
> 
> A further benefit in reducing this latency - is to keep the latency
> between the software rate control algorithm (which sees frames before
> they hit the DMA queue) and the hardware tx down. This allows the
> software rate control to be more responsive.

Hm, I don't really see how a larger DMA ring adds latency.
A DMA ring is endless. From the device and driver point
of view it only goes forward. If we reach the physical end
while going forward, we simply start at the beginning again.
Both, device and driver maintain very simple pointers into the
ring that are simply incremented.

TX notification latency is only controlled by a flag in the
descriptor control. We currently request an IRQ for each frame,
so latency is as low as possible here.

Maybe I don't understand what you are trying to explain, but I
don't see a benefit other than lower memory usage by reducing
DMA ring length.

-- 
Greetings Michael.

RE: [PATCH] d80211: add ieee80211_stop_queues()

[Simon Barber]

The DMA ring forms a queue of frames. Frames live in that queue for some
time before they are transmitted. This is a source of latency between
the software process that puts  the frames in the queue and the point in
time when they are actually transmitted.

Simon


-----Original Message-----
From: Michael Buesch [mailto:mb@bu3sch.de] 
Sent: Wednesday, August 23, 2006 1:05 PM
To: Simon Barber
Cc: Jiri Benc; linville@tuxdriver.com; netdev@vger.kernel.org
Subject: Re: [PATCH] d80211: add ieee80211_stop_queues()

On Wednesday 23 August 2006 21:54, Simon Barber wrote:
> I'd agree the memory benefit is not worth the work and complexity. The

> additional benefit is tighter queue control - reducing the latency 
> between the software qdisc (and whatever scheduling/rate 
> controlling/etc work they are doing) and the frames coming out of the 
> hardware. A 100 frame DMA queue can be 1.2 seconds of transmit time, 
> or it can be 30ms of transmit time depending on frame size and 
> transmission rate. This disparity will only get larger as rates go up
with 11n.
> 
> A further benefit in reducing this latency - is to keep the latency 
> between the software rate control algorithm (which sees frames before 
> they hit the DMA queue) and the hardware tx down. This allows the 
> software rate control to be more responsive.

Hm, I don't really see how a larger DMA ring adds latency.
A DMA ring is endless. From the device and driver point of view it only
goes forward. If we reach the physical end while going forward, we
simply start at the beginning again.
Both, device and driver maintain very simple pointers into the ring that
are simply incremented.

TX notification latency is only controlled by a flag in the descriptor
control. We currently request an IRQ for each frame, so latency is as
low as possible here.

Maybe I don't understand what you are trying to explain, but I don't see
a benefit other than lower memory usage by reducing DMA ring length.

--
Greetings Michael.

Re: [PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

On Wednesday 23 August 2006 22:10, Simon Barber wrote:
> The DMA ring forms a queue of frames. Frames live in that queue for some
> time before they are transmitted. This is a source of latency between
> the software process that puts  the frames in the queue and the point in
> time when they are actually transmitted.

Yes, sure. But I don't see how shortening that queue reduces
the time. Frames are always processed by the device as fast as
possible to a given "end-pointer". That end-pointer is updated
on the fly as packets come in. So if enough packets come in
the device keeps circling the ring. No matter how large it is.
The issue that we must prevent is a ring overflow by providing
a sufficiently _large_ (not small) ring. The larger the ring
the better. Theoretically an infinite ring size would be perfect,
but we don't want that for obvious memory issues. ;)
So we try to keep ring size down to a sane amount, where it's
damn unlikely to ever overflow, to reduce memory usage (and only
memory usage).

-- 
Greetings Michael.

RE: [PATCH] d80211: add ieee80211_stop_queues()

[Simon Barber]

Right - and what I'm proposing is that we don't just count the number of
frames in the ring - but also count the amount of frame time the ring
takes too. This way if there are a number of large, slow frames we can
stop adding more frames into the ring well before we reach the limit on
the number of frames. 

Simon

-----Original Message-----
From: Michael Buesch [mailto:mb@bu3sch.de] 
Sent: Wednesday, August 23, 2006 1:20 PM
To: Simon Barber
Cc: Jiri Benc; linville@tuxdriver.com; netdev@vger.kernel.org
Subject: Re: [PATCH] d80211: add ieee80211_stop_queues()

On Wednesday 23 August 2006 22:10, Simon Barber wrote:
> The DMA ring forms a queue of frames. Frames live in that queue for 
> some time before they are transmitted. This is a source of latency 
> between the software process that puts  the frames in the queue and 
> the point in time when they are actually transmitted.

Yes, sure. But I don't see how shortening that queue reduces the time.
Frames are always processed by the device as fast as possible to a given
"end-pointer". That end-pointer is updated on the fly as packets come
in. So if enough packets come in the device keeps circling the ring. No
matter how large it is.
The issue that we must prevent is a ring overflow by providing a
sufficiently _large_ (not small) ring. The larger the ring the better.
Theoretically an infinite ring size would be perfect, but we don't want
that for obvious memory issues. ;) So we try to keep ring size down to a
sane amount, where it's damn unlikely to ever overflow, to reduce memory
usage (and only memory usage).

--
Greetings Michael.

Re: [PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

On Wednesday 23 August 2006 22:32, Simon Barber wrote:
> Right - and what I'm proposing is that we don't just count the number of
> frames in the ring - but also count the amount of frame time the ring
> takes too. This way if there are a number of large, slow frames we can
> stop adding more frames into the ring well before we reach the limit on
> the number of frames. 

Ah, now I understand what you are trying to explain. :)
But why do we actually _want_ to stop a DMA ring, if it's
not full (has free descriptors)? I can't see any benefit on
it. Adding frames to the ring is done on the fly without
stopping or otherwise interferring with any running transmissions
queued earlier.
I would say we don't care about the time it takes for the
ring to go into idle on the d80211 level. I think the only thing
we care at d80211 level is: Can we queue another frame?
We have that logic. If a queue is not stopped, we can queue another
frame.

Or do you want to make the qdisc intelligent? Say, it drops
a few beacons, if there are already packets queued for the next
300ms, for example. Do you want to optimize latency of payload
data by dropping low-priority packets while the queue is
heavily loaded?
I can't see another usage for time based DMA ring accounting
in d80211, yet.

-- 
Greetings Michael.

RE: [PATCH] d80211: add ieee80211_stop_queues()

[Simon Barber]

We already do have intelligent qdiscs - via TC. Anyone using htb for
rate pacing, will achieve better control (less jitter) if the DMA queue
latency is kept down.

One very important issue for 802.11 is the software rate control. At a
certain point in time the rate control algorithm may determine it's time
to start transmitting frames at a much lower rate - now all the frames
already in the DMA queue will be transmitted at the old higher rate -
and hence will suffer a lower probability of being received correctly.
If the number of frames in the DMA queue can be kept down then the rate
change happens faster. Obviously the limiting factor is keeping the DMA
queue full enough that the hardware is not starved in the worst case of
softirq latency. This is a time based limit.

Simon


-----Original Message-----
From: Michael Buesch [mailto:mb@bu3sch.de] 
Sent: Wednesday, August 23, 2006 1:57 PM
To: Simon Barber
Cc: Jiri Benc; linville@tuxdriver.com; netdev@vger.kernel.org
Subject: Re: [PATCH] d80211: add ieee80211_stop_queues()

On Wednesday 23 August 2006 22:32, Simon Barber wrote:
> Right - and what I'm proposing is that we don't just count the number 
> of frames in the ring - but also count the amount of frame time the 
> ring takes too. This way if there are a number of large, slow frames 
> we can stop adding more frames into the ring well before we reach the 
> limit on the number of frames.

Ah, now I understand what you are trying to explain. :) But why do we
actually _want_ to stop a DMA ring, if it's not full (has free
descriptors)? I can't see any benefit on it. Adding frames to the ring
is done on the fly without stopping or otherwise interferring with any
running transmissions queued earlier.
I would say we don't care about the time it takes for the ring to go
into idle on the d80211 level. I think the only thing we care at d80211
level is: Can we queue another frame?
We have that logic. If a queue is not stopped, we can queue another
frame.

Or do you want to make the qdisc intelligent? Say, it drops a few
beacons, if there are already packets queued for the next 300ms, for
example. Do you want to optimize latency of payload data by dropping
low-priority packets while the queue is heavily loaded?
I can't see another usage for time based DMA ring accounting in d80211,
yet.

--
Greetings Michael.

Re: [PATCH] d80211: add ieee80211_stop_queues()

[Michael Buesch]

On Wednesday 23 August 2006 23:12, Simon Barber wrote:
> We already do have intelligent qdiscs - via TC. Anyone using htb for
> rate pacing, will achieve better control (less jitter) if the DMA queue
> latency is kept down.
> 
> One very important issue for 802.11 is the software rate control. At a
> certain point in time the rate control algorithm may determine it's time
> to start transmitting frames at a much lower rate - now all the frames
> already in the DMA queue will be transmitted at the old higher rate -
> and hence will suffer a lower probability of being received correctly.
> If the number of frames in the DMA queue can be kept down then the rate
> change happens faster. Obviously the limiting factor is keeping the DMA
> queue full enough that the hardware is not starved in the worst case of
> softirq latency. This is a time based limit.

Yes, that makes sense.
What about the following:

We don't remove the ieee80211_stop/wake_queue() mechanism, as it's
simply used to protect the hard bounds of the ring.

I think determining the ring latency might be possible without changing
the API or even changing the low level driver.

We have the ieee80211_tx_status() callback. We must simply
assume any packet that's gone through hw->tx() but not yet
got back through ieee80211_tx_status() is on the device queue.
And I think that's a valid assumption.

So accounting can be done before calling hw->tx()
and in ieee80211_tx_status().

At ieee80211_tx_status() time we have all needed information.
The frame length (skb), the transmission rate from the tx_control
array in the status report. We have that information in hw->tx(),
too, of course. So we can calculate the time (latency) the
current ring state has in O(1) time.

-- 
Greetings Michael.