FIFO

FIFO

[Frank Buss]

I need a FIFO with a fixed size, for buffering serial data on an 
embedded system. The FIFO will be filled in an interrupt and read from 
the main function.

I guess I could implement this myself, using a simple array of e.g. 256 
bytes, and then a read index and a write index. If I specify it with 
"pragma Volatile", nothing bad should happen.

But I read about bounded vectors. Could I use this as well and save a 
few lines of code and testing work? I'm a bit worried about if the 
behavior is standardized, such that e.g. Delete_First doesn't physically 
move all elements, because this would be bad when writing it at the same 
time from the interrupt. Because it is bounded, it could be implemented 
as the simple ringbuffer as I would implement it.

-- 
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss

Re: FIFO

[Jacob Sparre Andersen]

Frank Buss <fb@frank-buss.de> writes:

> I need a FIFO with a fixed size, for buffering serial data on an
> embedded system. The FIFO will be filled in an interrupt and read from
> the main function.

Maybe something like a bounded, synchronised queue
(http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-29.html)?

Greetings,

Jacob
-- 
"How may I be honest with you today?"

Re: FIFO

[Dmitry A. Kazakov]

On 2017-09-16 18:19, Jacob Sparre Andersen wrote:
> Frank Buss <fb@frank-buss.de> writes:
> 
>> I need a FIFO with a fixed size, for buffering serial data on an
>> embedded system. The FIFO will be filled in an interrupt and read from
>> the main function.
> 
> Maybe something like a bounded, synchronised queue
> (http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-29.html)?

Interrupt handler is a protected procedure. So, it is probably a 
bounded-error to use the queue from here (ARM 9.5.1/11).

I don't see anything wrong with ring buffer, provided read/write indices 
are declared atomic and there is only one reader.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: FIFO

[Frank Buss]

On 09/16/2017 06:19 PM, Jacob Sparre Andersen wrote:
> Frank Buss <fb@frank-buss.de> writes:
>
>> I need a FIFO with a fixed size, for buffering serial data on an
>> embedded system. The FIFO will be filled in an interrupt and read from
>> the main function.
>
> Maybe something like a bounded, synchronised queue
> (http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-29.html)?

Bit cumbersome to define the right type, but otherwise looks like what I 
was searching for. Unfortunately not supported for my implementation of 
ravenscar:

http://www.adacore.com/developers/development-log/NF-74-O619-005-gnat/

Oh well, I'll write my own package for it then. On the plus side it 
wouldn't have all these interface stuff overhead and might be smaller 
and faster, just a simple generic with the type and the size.

-- 
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss

Re: FIFO

[Dmitry A. Kazakov]

On 2017-09-16 19:12, Frank Buss wrote:

> Oh well, I'll write my own package for it then. On the plus side it 
> wouldn't have all these interface stuff overhead and might be smaller 
> and faster, just a simple generic with the type and the size.

You can borrow code from here:

    http://www.dmitry-kazakov.de/ada/components.htm#Generic_FIFO

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: FIFO

[Frank Buss]

On 09/16/2017 07:22 PM, Dmitry A. Kazakov wrote:
> On 2017-09-16 19:12, Frank Buss wrote:
>
>> Oh well, I'll write my own package for it then. On the plus side it
>> wouldn't have all these interface stuff overhead and might be smaller
>> and faster, just a simple generic with the type and the size.
>
> You can borrow code from here:
>
>    http://www.dmitry-kazakov.de/ada/components.htm#Generic_FIFO

Thanks, looks similar. I tried my own version, without looking at your 
version :-) Would this work for interrupts with the volatile? Good idea 
to use the size generic argument inside the package.

And everyone feel free to criticize my code, as I'm very new to Ada. For 
example, I saw that when you want to package something neatly, but it 
consists mainly of one type, then the package is named plural of the 
type, like I did: "Ringbuffers" and "Ringbuffer" for the type. Is this 
common practice?

For testing I wrote a small program. How do Ada programmers usually test 
their libraries and programs? For Java I often use JUnit.

My version:

ringbuffers.ads:

generic
    Size : Positive;
    type Item is private;
package Ringbuffers is

    type Ringbuffer is tagged private;

    procedure Write (Self : in out Ringbuffer; e : Item);
    function Read (Self : in out Ringbuffer) return Item;
    function Is_Empty (Self : Ringbuffer) return Boolean;

private

    type Item_Array is array (1 .. Size) of Item;
    pragma Volatile (Item_Array);
    type Ringbuffer is tagged record
       Read_Index  : Positive := 1;
       Write_Index : Positive := 1;
       Items       : Item_Array;
    end record;
    pragma Volatile (Ringbuffer);

end Ringbuffers;


ringbuffers.adb:

package body Ringbuffers is

    procedure Write (Self : in out Ringbuffer; e : Item) is
    begin
       Self.Items (Self.Write_Index) := e;
       Self.Write_Index := Self.Write_Index + 1;
       if (Self.Write_Index = Size) then
          Self.Write_Index := 1;
       end if;
    end Write;

    function Read (Self : in out Ringbuffer) return Item is
       Result : Item;
    begin
       Result := Self.Items (Self.Read_Index);
       Self.Read_Index := Self.Read_Index + 1;
       if (Self.Read_Index = Size) then
          Self.Read_Index := 1;
       end if;
       return Result;
    end Read;

    function Is_Empty (Self : Ringbuffer) return Boolean is
    begin
       return Self.Write_Index = Self.Read_Index;
    end Is_Empty;

end Ringbuffers;


test_ringbuffer.adb:

with Interfaces;  use Interfaces;
with Ada.Text_IO; use Ada.Text_IO;
with Ringbuffers;

procedure Test_Ringbuffer is
    package FIFO_Package is new Ringbuffers (256, Unsigned_8);
    subtype FIFO is FIFO_Package.Ringbuffer;
    Test : FIFO;

begin
    Test.Write (1);
    Test.Write (7);
    while not Test.Is_Empty loop
       Put_Line (Unsigned_8'Image (Test.Read));
    end loop;
end Test_Ringbuffer;


-- 
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss

Re: FIFO

[Jacob Sparre Andersen]

Frank Buss wrote:

> And everyone feel free to criticize my code, as I'm very new to
> Ada. For example, I saw that when you want to package something
> neatly, but it consists mainly of one type, then the package is named
> plural of the type, like I did: "Ringbuffers" and "Ringbuffer" for the
> type. Is this common practice?

It is one of three common practices:

1)
   package Noun is
      subtype Parent is ...;
      type Instance is new Parent with ...;
      subtype Class is Instance'Class;

2)
   package Plural_Noun is
      type Noun is ...;

3)
   package ... is
      type Noun_Type is ...;

The last of the three practices is explicitly frowned upon by the "Ada
(95) Quality and Style Guide", while the first two are listed as
suggested practices.

> For testing I wrote a small program. How do Ada programmers usually
> test their libraries and programs? For Java I often use JUnit.

I usually use Ahven.

There is also AUnit, but when I tried to use it, I found that the tool,
which should make it easier to use than Ahven didn't work on my system.

> generic
>    Size : Positive;
>    type Item is private;
> package Ringbuffers is

Another option is:

   generic
      type Index   is mod <>;
      type Element is private;
   package Ring_Buffer is
      type Instance is tagged private;
      subtype Class is Instance'Class;

      procedure Write (Buffer   : in out Instance;
                       New_Item : in     Element);
      function Read (Buffer : in out Instance) return Element;
      function Is_Empty (Buffer : Instance) return Boolean;
   private
      type Element_Array is array (Index) of Element
        with Volatile; --  I'm not sure this does what you want.

      type Instance is tagged
         record
            Head, Tail : Index := Index'First;
            Elements   : Element_Array;
         end record
           with Volatile; --  I'm not sure this does what you want either.
   end Ring_Buffer;

Notice that "Volatile" is a bit tricky.  I'm not sure if that is what
you need.  Nor if it makes sense to declare both types volatile.

Greetings,

Jacob
-- 
"In space, no-one can press CTRL-ALT-DEL"
                                        -- An Ada programmer

Re: FIFO

[Jacob Sparre Andersen]

Jacob Sparre Andersen wrote:

> 1)
>    package Noun is
>       subtype Parent is ...;
>       type Instance is new Parent with ...;
>       subtype Class is Instance'Class;

Just to be precise: The "Parent" part of this construct is not included
in the "Ada (95) Quality and Style Guide".

Greetings,

Jacob
-- 
PNG: Pretty Nice Graphics

Re: FIFO

[Niklas Holsti]

On 17-09-17 10:39 , Jacob Sparre Andersen wrote:
> Frank Buss wrote:
>
>> And everyone feel free to criticize my code, as I'm very new to
>> Ada.

    [snip]

>> generic
>>    Size : Positive;
>>    type Item is private;
>> package Ringbuffers is
>
> Another option is:
>
>    generic
>       type Index   is mod <>;
>       type Element is private;
>    package Ring_Buffer is
>       type Instance is tagged private;
>       subtype Class is Instance'Class;
>
>       procedure Write (Buffer   : in out Instance;
>                        New_Item : in     Element);
>       function Read (Buffer : in out Instance) return Element;
>       function Is_Empty (Buffer : Instance) return Boolean;
>    private
>       type Element_Array is array (Index) of Element
>         with Volatile; --  I'm not sure this does what you want.
>
>       type Instance is tagged
>          record
>             Head, Tail : Index := Index'First;
>             Elements   : Element_Array;
>          end record
>            with Volatile; --  I'm not sure this does what you want either.
>    end Ring_Buffer;
>
> Notice that "Volatile" is a bit tricky.  I'm not sure if that is what
> you need.  Nor if it makes sense to declare both types volatile.

I would use pragma Atomic on Head and Tail, pragma Volatile_Components 
on Element_Array, and no pragma on the (whole) Instance record type.

In May of this year there was a long and profound thread on 
comp.lang.ada about the Atomic/Volatile issue, with the subject 
"Portable memory barrier?". Worth reading if you intend to use those 
pragmas.

On the functional level, it seems to me that the ring-buffer package 
examples given so far are missing a check for overflow (full queue) in 
the "write" (enqueue) operation. I would augment the Write procedure to 
make this check and return a success/failure result to the caller (the 
interrupt handler) and/or increment a "lost elements" counter in the 
queue Instance, for use by the queue-reading task,

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: FIFO

[AdaMagica]

Am Samstag, 16. September 2017 20:32:36 UTC+2 schrieb Frank Buss:
> generic
>     Size : Positive;
>     type Item is private;
> package Ringbuffers is
> 
>     type Ringbuffer is tagged private;
> 
>     procedure Write (Self : in out Ringbuffer; e : Item);
>     function Read (Self : in out Ringbuffer) return Item;
>     function Is_Empty (Self : Ringbuffer) return Boolean;
> 
> private
> 
>     type Item_Array is array (1 .. Size) of Item;
>     pragma Volatile (Item_Array);
>     type Ringbuffer is tagged record
>        Read_Index  : Positive := 1;
>        Write_Index : Positive := 1;
>        Items       : Item_Array;
>     end record;
>     pragma Volatile (Ringbuffer);

Please check Volatile in the RM.

> 
> end Ringbuffers;
> 
> 
> ringbuffers.adb:
> 
> package body Ringbuffers is
> 
>     procedure Write (Self : in out Ringbuffer; e : Item) is

Check for overflow is missing.

>     begin
>        Self.Items (Self.Write_Index) := e;
>        Self.Write_Index := Self.Write_Index + 1;
>        if (Self.Write_Index = Size) then

Seems the true size is Size -1 , component with index Size will never be written (nor read, see below).

>           Self.Write_Index := 1;
>        end if;
>     end Write;
> 
>     function Read (Self : in out Ringbuffer) return Item is

Check for emptiness is missing.

>        Result : Item;
>     begin
>        Result := Self.Items (Self.Read_Index);
>        Self.Read_Index := Self.Read_Index + 1;
>        if (Self.Read_Index = Size) then
>           Self.Read_Index := 1;
>        end if;
>        return Result;
>     end Read;
> 
>     function Is_Empty (Self : Ringbuffer) return Boolean is
>     begin
>        return Self.Write_Index = Self.Read_Index;
>     end Is_Empty;
> 
> end Ringbuffers;
> 
> 
> test_ringbuffer.adb:
> 
> with Interfaces;  use Interfaces;
> with Ada.Text_IO; use Ada.Text_IO;
> with Ringbuffers;
> 
> procedure Test_Ringbuffer is
>     package FIFO_Package is new Ringbuffers (256, Unsigned_8);
>     subtype FIFO is FIFO_Package.Ringbuffer;
>     Test : FIFO;
> 
> begin
>     Test.Write (1);
>     Test.Write (7);
>     while not Test.Is_Empty loop
>        Put_Line (Unsigned_8'Image (Test.Read));
>     end loop;
> end Test_Ringbuffer;
> 
> 
> -- 
> Frank Buss, http://www.frank-buss.de
> electronics and more: http://www.youtube.com/user/frankbuss

Re: FIFO

[Niklas Holsti]

On 17-09-19 13:04 , Frank Buss wrote:
> On 09/19/2017 08:33 AM, Niklas Holsti wrote:
>> If one task or interrupt handler is pushing data into the buffer at some
>> rate, with some burstiness, and another task or interrupt handler is
>> pulling data from the buffer at some rate, with some burstiness, I do
>> not believe that GNATprove can show that the buffer never overflows.
>>
>> I'll be glad to be proven wrong, though.
>
> Right, this is what I meant. A real world example: This package reads
> data into my buffer:
>
> https://github.com/FrankBuss/Ada_Synth/blob/master/ada/discovery/serial_io.adb#L67
>
>
> Another unrelated problem: I think there could be a race condition, if
> the FIFO is not empty, but then the interrupt is called and the FIFO
> gets empty, and then the next byte is added to the FIFO in the else
> branch, which then will never be sent, and even worse, no more bytes at
> all will be sent after this bug. How could I prevent this? I guess I
> should disable interrupts while in the Write procedure, or is this done
> by Ada automatically because I'm in a protected body?

Yes, automatically. RM C.3.1(13): "When a handler is attached to an 
interrupt, the interrupt is blocked (subject to the Implementation 
Permission in C.3 [that is, if "the underlying system or hardware" 
allows blocking interrupts]) during the execution of every protected 
action on the protected object containing the handler."

I haven't reviewed your code in detail, but I glanced at it and wonder 
about some things:

- Serial_Port_Controller.Write checks if the Output FIFO Is_Empty, but 
it does not check if a transmission is going on. How do you intend to 
prevent the writer task(s) from calling Write too often, overwriting an 
on-going transmission with a new transmission?

- In fact, the code only puts something into the Output FIFO if the 
Output FIFO is non-empty. I assume the FIFO is empty initially, so it 
seems to me that it will always be empty. That can't be intended.

- If I understand the code correctly, 
Serial_Port_Controller.Interrupt_Handler clears the "transmission 
completed" status _after_ it has started a new transmission. This 
creates a race condition: if the UART is very fast, it might complete 
the transmission before the code clears the "transmission completed" 
status, in which case the "transmission completed" status would be lost. 
I suggest to clear the "tranmission completed" status _before_ starting 
the new transmission.

I think the protected object should have a flag variable showing if a 
transmission is going on. The flag should be set when a transmission is 
started, and be cleared in the Interrupt_Handler when it detects the 
completion of the transmission. The Write procedure should start a 
transmission if, and only if, no transmission is already going on. If a 
transmission is going on when Write is called, Write should put the Data 
into the Output FIFO, for Interrupt_Handler to transmit later.

Perhaps you intended that "not Output.Is_Empty" would mean "transmission 
going on", but that is not the way the code works. The octet currently 
being transmitted is _not_ in the Output FIFO.

(By the way, if the Rinbguffer objects are protected variables, it is 
not necessary to have pragma Volatile etc. on them, because the 
protected object does whatever is needed for multi-task access. Pragma 
Volatile etc. is needed only for _unprotected_ variables that are 
nevertheless accessed from multiple tasks.)

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: FIFO

[Robert A Duff]

Frank Buss <fb@frank-buss.de> writes:

> I need a FIFO with a fixed size,...

Does Ada.Containers.Bounded_Synchronized_Queues meet your needs?

- Bob

Re: FIFO

[Frank Buss]

On 09/16/2017 07:52 PM, Robert A Duff wrote:
> Frank Buss <fb@frank-buss.de> writes:
>
>> I need a FIFO with a fixed size,...
>
> Does Ada.Containers.Bounded_Synchronized_Queues meet your needs?

I guess it would work, but not available in ravenscar full for GNAT.

-- 
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss

Re: FIFO

[Simon Wright]

Robert A Duff <bobduff@TheWorld.com> writes:

> Frank Buss <fb@frank-buss.de> writes:
>
>> I need a FIFO with a fixed size,...
>
> Does Ada.Containers.Bounded_Synchronized_Queues meet your needs?
>
> - Bob

The implementation in GNAT GPL 2017 is not legal under Ravenscar
restrictions (the protected type Queue has two entries).

Also, what's the behaviour when the queue is already full? It blocks on
Enqueue, which would be a Bad Idea if called from an interrupt handler.

Re: FIFO

[Jeffrey R. Carter]

On 09/16/2017 05:24 PM, Frank Buss wrote:
> I need a FIFO with a fixed size, for buffering serial data on an embedded 
> system. The FIFO will be filled in an interrupt and read from the main function.

You could use an instance of PragmARC.Queue_Bounded_Unprotected:

https://github.com/jrcarter/PragmARC

-- 
Jeff Carter
"When danger reared its ugly head, he bravely
turned his tail and fled."
Monty Python and the Holy Grail
60