[Tinyos-devel] thoughts on buffer management....

Eric Decker cire831 at gmail.com
Mon Oct 7 02:07:08 PDT 2013


On Mon, Oct 7, 2013 at 1:56 AM, Miklos Maroti <mmaroti at math.u-szeged.hu>wrote:

> Hi Eric,
>
> On Mon, Oct 7, 2013 at 10:47 AM, Eric Decker <cire831 at gmail.com> wrote:
> >
> > On Mon, Oct 7, 2013 at 1:04 AM, Miklos Maroti <mmaroti at math.u-szeged.hu>
> > wrote:
> >>
> >> Hi Eric,
> >>
> >> basically you want to make receive to be asyncronous:
> >>
> >> event void receive(message_t *message);
> >> command void receiveDone(message_t *message);
> >
> >
> > Ah not sure if that fits.
> >
> > Right now receive is already asynchronous and why packet reception occurs
> > using a signal.  Nothing synchrounous about it.
>
> Sorry, I have used the synchronous adjective in the javascript sense:
> currently receive is a single phase operation, once it returns we have
> the new buffer. The other option is to use a two phase operation:
> first we get the receive event, and if we managed to process that
> event and store the message somewhere, then you would call receiveDone
> with the new buffer pointer.
>

okay.   now I get it.   I see it now.


>
> I am not arguing to use this smart buffer management, but I think the
> receive/receiveDone is a better approach than your return NULL and an
> explicit enable. I think your proposal would produce better code, and
> mine would be easier to understand, for me at least :), but they are
> operationally equivalent.


> Anyhow, I think this would think would not buy us too much, but I am
> ready to be convinced with hard measured data :)
>

That makes sense.  Let's table  the request.   I'm tending towards the view
it may not be worth dealing with because it doesn't buy that much.  So
the study should be done if it really is a problem.

Reminds me of what one of my old co-workers used to say... "Just exactly
what problem are you solving?"


thanks for your input.

eric



> Miklos
>
> >
> >>
> >>
> >> It is possible, but I also do not see such a big benefit. There is a
> >> single place now that holds 2 buffers (ActiveMessageLayer), which is
> >> actually taking the messages produced in tasklet context and turns
> >> them into messages in task context. Of course if tasks do not consume
> >> the messages fast enough, then it has to "drop" messages (and since
> >> acks a emitted higher up, so no acks will be sent back for packets
> >> that are dropped).
> >>
> >> However, we have to look at the message starvation scenario. It means
> >> that the MCU is fully busy processing messages, and it is not fast
> >> enough.
> >
> >
> > I don't buy this.  It depends on how the message buffers are being used.
>  It
> > may not involve active
> > message processing at all.   Rather the buffers may be getting hung onto
> due
> > to protocol
> > issues or for other reasons.   Depends on what higher layers are doing.
> >
> > So I'd argue that whether the main MCU is busy or not really depends on
> what
> > is going on, what protocols are implemented, and what the network packet
> > data
> > flow looks like.
> >
> > Now that said, yes the radio will be busy, the premise is it is getting
> > hammered.  But the driver
> > given the current structure is required to keep the MCU busier than
> > otherwise coping data up
> > that will get pitched.
> >
> > Let's assume that the MCU would otherwise be quiesent, using the current
> > scheme
> > the MCU will continue to burn energy when it could be sleeping.
> >
> >>
> >> This means that you are in the operation phase which is
> >> actively burning power.
> >
> >
> > Not necessarily.   See above.
> >
> >>
> >> With your optimization you cannot prevent the
> >> radio from doing all the signal processing in the receive side, so you
> >> are not going to save power on the radio side,
> >
> >
> > agreed.   The premise is the radio is getting hammered.
> >
> >>
> >> and you are not saving
> >> much power either on the MCU side because it is always on.
> >
> >
> > see above.
> >
> >>
> >>
> >>  What you
> >> are saving is time. Also, it is possible to argue that the higher
> >> layer cannot inform the lower layer fast enough in this situation to
> >> avoid dropping of packets. It is entirely possible that the upper
> >> layer buffers are full, but we still go ahead and start to download
> >> the message, and by the time we actually download it, then there will
> >> be an empty message slot higher up.
> >
> >
> > that is a reasonable argument.   However, it is more valid considering
> the
> > interarrival time of inbound packets, arriving at ~ 250Kbps.   The busy
> > work occurs at SPI bus speeds and is what keeps the MCU busy.
> >
> > But thinking this through, it is starting to look silly.   The SPI bus
> I'm
> > using is running at 4MHz so we are seeing something like 1-2 Mbps
> > considering the overhead.  Haven't actually measured it.  Probably
> > should at some point.
> >
> > Also the rxfifo can at most hold 128 bytes (multiple packets not
> exceeding
> > 128 bytes).   So uploading time isn't that nasty.   But it would be so
> much
> > simpler if I can simply blow all the packets away with a simple
> instruction.
> >
> > So I still think the optiization is probably worth it, but am convinced
> that
> > it probably wouldn't save that much in actual behaviour of the system.
> >
> >
> >>
> >>
> >>  If you preemptively discard
> >> messages, then you might discard something that you could have
> >> processed.
> >
> >
> > good point.   Significant energy is spent by the radio getting the
> packet on
> > board.
> >
> >>
> >>
> >> One more thing, I am not sure how the CC2520 buffer management works,
> >> but on the silabs radio you could not just flush the fifo, because you
> >> would be out of sync, and you might discard only half of the last
> >> packet and the packet length of the next packet would be garbage and
> >> you are completely out of sync with the hardware. Do you have this
> >> problem with the cc2520 too? On the silabs the only reliable way to
> >> flush the buffer is to read it out.
> >
> >
> > I'll have to make sure this works.   It is my understanding that the 2520
> > is smarter about this.  If the rxfifo is flushed with SRXFLUSH then it
> > aborts
> > the current packet and goes back to searching for a Preamble and a new
> > SFD.
> >
> > However I need to verify that is indeed true.   It is only implied by the
> > documentation
> > which isn't that great.   I do know that if we go into RX_OVERFLOW
> receive
> > stops and the rxfifo is frozen.   It won't start back up again until the
> > fifo is flushed which
> > restarts the looking for Preamble and SFD.   It would make sense for it
> to
> > work
> > that way anytime SRXFLUSH occurs.  But it needs to be verified.
> >
> >>
> >>
> >> Miklos
> >>
> >>
> >> On Mon, Oct 7, 2013 at 9:17 AM, Eric Decker <cire831 at gmail.com> wrote:
> >> >
> >> >
> >> >
> >> > On Sun, Oct 6, 2013 at 6:37 PM, Philip Levis <pal at cs.stanford.edu>
> >> > wrote:
> >> >>
> >> >> I don't think the cost of a single buffer is significant enough to
> >> >> warrant
> >> >> a different software architecture.
> >> >
> >> >
> >> > agreed.
> >> >
> >> > But it isn't really a different software architecture.   A simple
> >> > addition
> >> > to RadioReceive would allow the interface to evolve gracefully.
> >> >
> >> >
> >> >>
> >> >> The upper layer can always tell it to discard packets by passing it
> >> >> back.
> >> >
> >> >
> >> > The upper layer discards the packet but the LLD doesn't but
> continuously
> >> > copies new packets into a buffer and then passes it up.
> >> >
> >> >>
> >> >> The 'extra work' here is pretty minimal, unless you're thinking there
> >> >> are
> >> >> power implications.
> >> >
> >> >
> >> > Definitely power implications.    But the details of what it costs
> >> > depends
> >> > on how the driver is implemented.  For example, the cc2420x driver
> does
> >> > busy
> >> > waits waiting for each incoming byte.   It doesn't have to do it this
> >> > way
> >> > but is how it is currently implemented.  So if it is moving data into
> a
> >> > buffer that just then gets tossed, that is much more expensive then if
> >> > the
> >> > LLD knows to just drop the packet via RXFLUSH.   If RXFLUSH is used,
> the
> >> > cpu
> >> > will spend a whole bunch more time sleeping.
> >> >
> >> > Now even if the 2420x driver is implemented in lets say a more
> efficient
> >> > fashion, there is still a bunch of work it actually has to do moving
> the
> >> > packet bytes out of the on chip fifo into the memory buffer.  The SPI
> >> > bus is
> >> > on and the cpu is moving things via the interface.
> >> >
> >> >>
> >> >> Not to mention that a given driver might not be able to make this
> >> >> judgement, instead having to get it from network layers.
> >> >
> >> >
> >> > The LLD can never make this judgement.  It has to be told by buffer
> >> > management/network layers what is going on.
> >> >
> >> > I'm interested in adding a simple change that would make the
> interface a
> >> > superset of the current one that can be used to gracefully evolve the
> >> > interface.  Existing code wouldn't need to support it.
> >> >
> >> >>
> >> >>
> >> >> Can you be more precise what you mean by 'better tuning'?
> >> >
> >> >
> >> > I'm thinking about the problems the system faces under load and ways
> for
> >> > a
> >> > given node to gracefully shed so that nodes continue to be able to
> >> > perform
> >> > in real deployed environments.  Yeah yeah, motherhood and apple pie.
> >> >
> >> > The situation in particular that I'm thinking of starts with the
> premise
> >> > that the radio is seeing lots of traffic.  The new C2520 driver
> >> > (cc2520-v2)
> >> > actually uses what the h/w provides to minimizes
> >> >
> >> > The tuning I'm referring to is designing in mechanisms that allow if
> >> > desired
> >> > for the system to adapt to what is happening.  i.e.. being able to
> tell
> >> > the
> >> > driver to really stop copying packets into a buffer that will
> basically
> >> > get
> >> > thrown away so that the driver can do things differently that helps
> the
> >> > system deal with getting hammered.
> >> >
> >> > So consider, the rxfifo on the 2520 can hold multiple packets.  And
> the
> >> > premise is that the interface is being inundated but we have
> temporarily
> >> > run
> >> > out of buffers upstairs.   Using the current interface we will need to
> >> > process each packet one by one, including extracting the packet data
> >> > from
> >> > the rxfifo and moving it into the packet buffer (which is then thrown
> >> > away
> >> > upstairs).
> >> >
> >> > If the LLD on the other hand, knows that we are in a buffer starvation
> >> > situation, it can on the other hand simply flush the rxfifo rather
> than
> >> > actually processing each packet.  This results in a significantly
> >> > reduced
> >> > load on the driver and the cpu when the system starts getting
> hammered.
> >> >
> >> > This is what I mean by tuning.   The system has the knobs to change
> how
> >> > different parts behave as conditions change.
> >> >
> >> >
> >> > Now in particular, here is what I'd like to add to RadioReceive
> >> >
> >> > first, if the upper layer (the event handler for RadioReceive.receive)
> >> > is in
> >> > a buffer starvation condition it can return NULL indicating no buffers
> >> > available.
> >> >
> >> > And we also need a new call into the LLD that tells the driver about
> >> > what
> >> > buffer it should use for receiving into.  Call it
> >> > RadioReceive.buffAvail(message_t *newbuff).
> >> >
> >> >
> >> > Clearly the upper layer and a given driver have to agree to use this
> >> > part of
> >> > the interface.   And if so, the optimization can be accomplished.
> But
> >> > existing layers and drivers don't have to use the new stuff.  And
> having
> >> > the
> >> > interface can allow improvements in the behavior of the driver when
> in a
> >> > saturated environment.
> >> >
> >> >
> >> >>
> >> >>
> >> >> Phil
> >> >>
> >> >> -------
> >> >> Philip Levis
> >> >> Associate Professor
> >> >> Computer Science and Electrical Engineering
> >> >> Stanford University
> >> >> http://csl.stanford.edu/~pal
> >> >>
> >> >> On Oct 6, 2013, at 6:19 PM, Eric Decker <cire831 at gmail.com> wrote:
> >> >>
> >> >> >
> >> >> > I've been rewriting the CC2520 driver and have been looking at how
> we
> >> >> > receive packets and the interactions with upper layers.   In
> >> >> > particular
> >> >> > buffer management.
> >> >> >
> >> >> > By default, a low level driver has a buffer (usually defined in the
> >> >> > driver itself) that is "parked" and available for use by the low
> >> >> > level
> >> >> > driver (LLD).   When the packet is filled in RadioReceive.receive
> is
> >> >> > signaled.  On return the LLD is handed the next buffer to use for
> the
> >> >> > next
> >> >> > receive.
> >> >> >
> >> >> > Now if we are in buffer starvation, the upper layer is forced to
> hand
> >> >> > back the buffer that it has just been handed.  There are no other
> >> >> > provisions
> >> >> > for upper layer and/or buffer management code to inform a LLD that
> >> >> > the
> >> >> > system is in buffer starvation and it should just discard incoming
> >> >> > packets.
> >> >> >
> >> >> > Is first any LLD in the systems will each be holding onto buffers
> >> >> > (one
> >> >> > per LLD) and 2nd the LLD will be doing work copying packets into
> its
> >> >> > only
> >> >> > buffer and handing it off to the upper layer where it is thrown
> away.
> >> >> > Not
> >> >> > doing the extra work would be better.
> >> >> >
> >> >> > Clearly, this is how the current system works.   And it is clear
> that
> >> >> > it
> >> >> > does work and is stable enough.
> >> >> >
> >> >> > However, buffer starvation and mechanisms for flow control push
> back
> >> >> > as
> >> >> > well as buffer management mechanisms would allow for better tuning
> in
> >> >> > system
> >> >> > behaviour.   And they don't have to be complex.
> >> >> >
> >> >> > Do we want LLD to continue to behave this way or is it desireable
> to
> >> >> > add
> >> >> > slightly more capability to better deal  with buffer starvation
> >> >> > issues?
> >> >> >
> >> >> >
> >> >> > thoughts?
> >> >> >
> >> >> > eric
> >> >> >
> >> >> >
> >> >> >
> >> >> > --
> >> >> > Eric B. Decker
> >> >> > Senior (over 50 :-) Researcher
> >> >> >
> >> >>
> >> >
> >> >
> >> >
> >> > --
> >> > Eric B. Decker
> >> > Senior (over 50 :-) Researcher
> >> >
> >
> >
> >
> >
> > --
> > Eric B. Decker
> > Senior (over 50 :-) Researcher
> >
>



-- 
Eric B. Decker
Senior (over 50 :-) Researcher
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/tinyos-devel/attachments/20131007/82031525/attachment-0001.htm 


More information about the Tinyos-devel mailing list