hardware/firmware powersave help, Broadcom scheme

hardware/firmware powersave help, Broadcom scheme

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 2149 bytes --]

Hi,

After my previous mail about atheros's powersave help I thought about it
a bit more.

The basic problem this solves is the race condition between software
noticing a station went to sleep and stopping to send frames to it. The
software will obviously stop sending frames to that station right away,
but there may be frames already pending in hardware/DMA fifos/queues.

mac80211 contains code that assumes if a packet fails and the station is
in powersave mode then this packet failed because of that, but that is
obviously suboptimal because the packet will be transmitted even though
the station is asleep. Hence the need for hardware/firmware help.

For Atheros hardware, this seems to be implemented by having a hardware
filter which (I guess) is software controlled. When the station goes to
sleep you insert it into the filter and frames that already are in the
(DMA) queue/fifo will be filtered instead of transmitted. This still
leaves a small window for the race condition because of the processing
delay in the stack. Unless of course the filter table is hardware
controlled, but then it can only ever *insert* stations into the table,
not delete them, it appears that the plan is to handle the delete step
by the IEEE80211_TXCTL_CLEAR_DST_MASK tx control flag.

Broadcom hardware, on the other hand, has a slightly more complicated
scheme. All powersave transitions are registered by the firmware (!) in
a hardware FIFO (really a ring buffer I think), the "power management
queue". I'm not entirely sure how entries are deleted again, but IIUC
they can only be deleted once there are no frames "in flight" for any
powersave station any more.

The atheros scheme seems to be implemented in mac80211, but I think we
might also want to implement the Broadcom scheme. This could be done
fully in the driver but that has a chance that the PS flags get out of
sync between the firmware, driver and mac80211. To fix this, we'd have
to export a new function to set/clear the PS flag (i.e. invoke
ap_sta_ps_start/ap_sta_ps_end) on driver request rather than on received
frames.

Thoughts?

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: hardware/firmware powersave help, Broadcom scheme

[Zhu Yi]

On Wed, 2008-02-20 at 16:18 +0100, Johannes Berg wrote:
> 
> Broadcom hardware, on the other hand, has a slightly more complicated
> scheme. All powersave transitions are registered by the firmware (!)
> in
> a hardware FIFO (really a ring buffer I think), the "power management
> queue". I'm not entirely sure how entries are deleted again, but IIUC
> they can only be deleted once there are no frames "in flight" for any
> powersave station any more.
> 
> The atheros scheme seems to be implemented in mac80211, but I think we
> might also want to implement the Broadcom scheme. This could be done
> fully in the driver but that has a chance that the PS flags get out of
> sync between the firmware, driver and mac80211. To fix this, we'd have
> to export a new function to set/clear the PS flag (i.e. invoke
> ap_sta_ps_start/ap_sta_ps_end) on driver request rather than on
> received
> frames.
> 
> Thoughts?

Hey, and there is also ipw firmware!

As broadcom, the iwl4965AGN firmware is also aware of the powersave
state for the station/stations (consider about the master mode). In
stead of having a special "power management queue", the 4965 firmware
still use the normal 4 QoS queues for frames destined to powersaved
STAs. But these frames will be dropped by firmware eventually. In this
case, mac80211 ieee80211_tx_status() will get these SKBs with a tx error
state DST_STA_IN_POWERSAVE so that it can requeue them (to send them
later when STA wakes up). Note, this scheme is to resolve the race
condition you mentioned that in the small window the STA powersave state
mismatches between mac80211 and firmware. After mac80211 receives the PS
frame, it stops to Tx more frames to hardware.

This scheme works well but we have one requirement for mac80211. That
is, in the master mode, when the destined STA wakes up from powersave
mode, mac80211 should not begin to Tx frames to hardware until the
current h/w Tx queues are drained. Otherwise we can expect frames out of
order issue happens (for example, some frames in h/w queues are requeued
but others are left when mac80211 begins to Tx).

It's good that you look into mac80211 powersave now. We also have code
that enables master mode PS poll and uAPSD based on an early version of
mac80211. We will merge it to the latest mac80211 and submit but it
takes some time. I can point you the patch if you are interested.

Thanks,
-yi

Re: hardware/firmware powersave help, Broadcom scheme

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 4290 bytes --]


> Hey, and there is also ipw firmware!

Yeah but I know nothing about it and you haven't published anything
yet :)

> As broadcom, the iwl4965AGN firmware is also aware of the powersave
> state for the station/stations (consider about the master mode). In
> stead of having a special "power management queue", 

"Power management queue" is a bit misleading, it's not a frame queue,
it's a queue/fifo of power management status notifications.

> the 4965 firmware
> still use the normal 4 QoS queues for frames destined to powersaved
> STAs. 

Yes, same for Broadcom.

> But these frames will be dropped by firmware eventually. 

Yeah, they're suppressed by firmware if the STA has gone to sleep
between the frame being queued by the driver and processed by the
firmware.

> In this
> case, mac80211 ieee80211_tx_status() will get these SKBs with a tx error
> state DST_STA_IN_POWERSAVE so that it can requeue them (to send them
> later when STA wakes up). 

You should indicate that to mac80211 by using the TX_FILTERED TX status
flag.

> Note, this scheme is to resolve the race
> condition you mentioned that in the small window the STA powersave state
> mismatches between mac80211 and firmware. After mac80211 receives the PS
> frame, it stops to Tx more frames to hardware.

Right. This completely solves the race, there's a possible scheme where
the host notifies the firmware of powersave status changes which will
still help because this can be made faster than the TX queues, but still
leaves a small window. That was hypothetical though, I guess nobody
implements such a scheme.

> This scheme works well but we have one requirement for mac80211. That
> is, in the master mode, when the destined STA wakes up from powersave
> mode, mac80211 should not begin to Tx frames to hardware until the
> current h/w Tx queues are drained. Otherwise we can expect frames out of
> order issue happens (for example, some frames in h/w queues are requeued
> but others are left when mac80211 begins to Tx).

Good point. Completely draining isn't really possible when we're
communicating with another station nor is it necessary, inserting a sort
of "barrier" into the queue (any frame would be sufficient) would be
good enough so that you know when all frames inserted before the
powersave status change are drained.

On the other hand, even that is not necessary. Because we stop TX to a
STA right away once we see a STA going to sleep it would be sufficient
to insert a barrier into all queues when the STA goes to sleep and later
wait for those barriers to complete, which in most cases they will
already have.

[continuing below]

> It's good that you look into mac80211 powersave now. We also have code
> that enables master mode PS poll and uAPSD based on an early version of
> mac80211. We will merge it to the latest mac80211 and submit but it
> takes some time. I can point you the patch if you are interested.

I'm somewhat interested, I was trying to get my N810 to perform well
with a Broadcom/mac80211 based AP. I'd be much more interested in having
an iwl4965 ucode image and driver patches to get master mode working
there though :)

As for implementing the "barrier" scheme, the following could work:

When a STA goes to sleep, mac80211 calls a new
	ops->insert_queue_barrier(hw, u8 *sta, u32 cookie)

callback in the driver. This callback takes note of all current queue
status and inserts the status information into a list. mac80211 has
created a cookie (probably just based on an increasing per-sta counter)
and saves that cookie in the sta_info for that particular sta (this
barrier cookie is to allow having two barriers for the same STA in
flight at the same time).

As part of TX status processing, the driver now checks whether any of
the barriers completed by comparing the TX queue status to the list of
barriers. It then calls a new

	void ieee80211_barrier_completed(u8 *sta, u32 cookie)

mac80211 function. mac80211 looks up the sta and clears the cookie if it
matches, and if so also schedules all outstanding frames for
transmission.

Additionally, mac80211 is changed to not transmit if the sta has a
barrier cookie assigned.

What do you think?

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: hardware/firmware powersave help, Broadcom scheme

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 1934 bytes --]


> As for implementing the "barrier" scheme, the following could work:
> 
> When a STA goes to sleep, mac80211 calls a new
> 	ops->insert_queue_barrier(hw, u8 *sta, u32 cookie)
> 
> callback in the driver. This callback takes note of all current queue
> status and inserts the status information into a list. mac80211 has
> created a cookie (probably just based on an increasing per-sta counter)
> and saves that cookie in the sta_info for that particular sta (this
> barrier cookie is to allow having two barriers for the same STA in
> flight at the same time).
> 
> As part of TX status processing, the driver now checks whether any of
> the barriers completed by comparing the TX queue status to the list of
> barriers. It then calls a new
> 
> 	void ieee80211_barrier_completed(u8 *sta, u32 cookie)
> 
> mac80211 function. mac80211 looks up the sta and clears the cookie if it
> matches, and if so also schedules all outstanding frames for
> transmission.
> 
> Additionally, mac80211 is changed to not transmit if the sta has a
> barrier cookie assigned.

Now, let me explain how I'd implement this:

The driver is first changed to always keep track of the frame cookie/ID
for the last frame inserted into each queue. This needs a single u32 per
hardware queue.

Then, when insert_queue_barrier() is called, the driver saves the
following information in a list:
 * sta mac addr
 * cookie
 * last frame cookie for all possible queues

On TX status/completion notification, the driver checks for the first
barrier in the list whether all frame cookies have been completed. This
can either be implemented by making the cookies be increasing numbers or
walking the barrier list for each completed cookie and clearing those
that have been processed. When a barrier has been processed completely,
it calls the ieee80211_barrier_completed() function and removes it from
the list.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: hardware/firmware powersave help, Broadcom scheme

[Zhu Yi]

On Thu, 2008-02-21 at 11:58 +0100, Johannes Berg wrote:
> Right. This completely solves the race, there's a possible scheme
> where
> the host notifies the firmware of powersave status changes which will
> still help because this can be made faster than the TX queues, but
> still
> leaves a small window. That was hypothetical though, I guess nobody
> implements such a scheme.

Maybe to your surprise, the iwlwifi firmware implemented this. But the
major purpose is not the speed, again, it's for the out of order issue.
So the STA wake -> sleep state is controlled by the firmware. The small
window of the states mismatch between firmware and mac80211 is
dangerous, so we need to avoid it by mac80211 requeuing discarded
frames. The STA sleep -> wake state is controlled by mac80211. We send
host command to notify firmware about the change. But the small window
is safe because it is OK we delay some time for packets sending after
the STA wakes up.

> Good point. Completely draining isn't really possible when we're
> communicating with another station nor is it necessary, inserting a
> sort
> of "barrier" into the queue (any frame would be sufficient) would be
> good enough so that you know when all frames inserted before the
> powersave status change are drained.
> 
> On the other hand, even that is not necessary. Because we stop TX to a
> STA right away once we see a STA going to sleep it would be sufficient
> to insert a barrier into all queues when the STA goes to sleep and
> later
> wait for those barriers to complete, which in most cases they will
> already have.

Right. Sorry if my previous "drain queue" comment is misleading, I
actually mean "begin to send until there are no frames to the target STA
in the h/w queues". So my "drain queue" is per DA.

> [continuing below]
> 
> > It's good that you look into mac80211 powersave now. We also have
> code
> > that enables master mode PS poll and uAPSD based on an early version
> of
> > mac80211. We will merge it to the latest mac80211 and submit but it
> > takes some time. I can point you the patch if you are interested.
> 
> I'm somewhat interested, I was trying to get my N810 to perform well
> with a Broadcom/mac80211 based AP. I'd be much more interested in
> having
> an iwl4965 ucode image and driver patches to get master mode working
> there though :)
> 
> As for implementing the "barrier" scheme, the following could work:
> 
> When a STA goes to sleep, mac80211 calls a new
>         ops->insert_queue_barrier(hw, u8 *sta, u32 cookie)
> 
> callback in the driver. This callback takes note of all current queue
> status and inserts the status information into a list. mac80211 has
> created a cookie (probably just based on an increasing per-sta
> counter)
> and saves that cookie in the sta_info for that particular sta (this
> barrier cookie is to allow having two barriers for the same STA in
> flight at the same time).
> 
> As part of TX status processing, the driver now checks whether any of
> the barriers completed by comparing the TX queue status to the list of
> barriers. It then calls a new
> 
>         void ieee80211_barrier_completed(u8 *sta, u32 cookie)
> 
> mac80211 function. mac80211 looks up the sta and clears the cookie if
> it
> matches, and if so also schedules all outstanding frames for
> transmission.
> 
> Additionally, mac80211 is changed to not transmit if the sta has a
> barrier cookie assigned.
> 
> What do you think?

With the STA sleep -> wake state controlled by mac80211, I think we can
avoid the hw callbacks and handle all these in mac80211. What we do is
we add an atomic hw_pending_count in sta_info. We increase the count for
every successfull ops->tx() and decrease it in ieee80211_tx_status
(whatever success or fail). When mac80211 decides to switch STA state
from sleep to wake (and send host command to firmware), it must wait
until hw_pending_count is zero. (BTW, wait here is not accurate. We
actually handled this asynchronously).

Thanks,
-yi

Re: hardware/firmware powersave help, Broadcom scheme

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 1426 bytes --]


> > Right. This completely solves the race, there's a possible scheme
> > where
> > the host notifies the firmware of powersave status changes which will
> > still help because this can be made faster than the TX queues, but
> > still
> > leaves a small window. That was hypothetical though, I guess nobody
> > implements such a scheme.
> 
> Maybe to your surprise, the iwlwifi firmware implemented this. 

I thought you just said the firmware follows the powersave transitions
by itself (by looking at the frames)? In my hypothetical scheme the
driver/stack notifies the firmware about them.

> Right. Sorry if my previous "drain queue" comment is misleading, I
> actually mean "begin to send until there are no frames to the target STA
> in the h/w queues". So my "drain queue" is per DA.

Right.

> With the STA sleep -> wake state controlled by mac80211, I think we can
> avoid the hw callbacks and handle all these in mac80211. What we do is
> we add an atomic hw_pending_count in sta_info. We increase the count for
> every successfull ops->tx() and decrease it in ieee80211_tx_status
> (whatever success or fail). When mac80211 decides to switch STA state
> from sleep to wake (and send host command to firmware), it must wait
> until hw_pending_count is zero. (BTW, wait here is not accurate. We
> actually handled this asynchronously).

Hmm, yes, good point, much simpler.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: hardware/firmware powersave help, Broadcom scheme

[Zhu Yi]

On Fri, 2008-02-22 at 14:58 +0100, Johannes Berg wrote:
> I thought you just said the firmware follows the powersave transitions
> by itself (by looking at the frames)? In my hypothetical scheme the
> driver/stack notifies the firmware about them.

Alright, the iwlwifi firmware works partially by itself on powersave. It
switches from wake to sleep by looking at the frames and from sleep to
wake by driver/stack notification.

BTW, I've put our iwl4965 AP code at below address. We tested it on
2.6.22 kernel. The code is not very up to date but you can at least get
a working AP with an iwl4965 card.
http://www.kernel.org/pub/linux/kernel/people/chuyee/wireless/iwl4965_ap/

To install mac80211:

$ cd mac80211
$ make patch_kernel
$ recompile your kernel and modules && install

To compile and run the hostapd:

$ cd hostapd
$ make KSRC=/lib/modules/`uname -r`/build
$ ./hostapd hostapd.conf

Thanks,
-yi