RE: [PATCH] can: length: add definitions for frame lengths in bits

[Thomas.Kopp]

Hi Vincent,

> On Mon. 8 May 2023 at 21:29, Marc Kleine-Budde <mkl@xxxxxxxxxxxxxx>
> wrote:
> > On 08.05.2023 00:55:06, Vincent Mailhol wrote:
> > > When created in [1], frames length definitions were added to implement
> > > byte queue limits (bql). Because bql expects lengths in bytes, bit
> > > length definitions were not considered back then.
> > >
> > > Recently, a need to refer to the exact frame length in bits, with CAN
> > > bit stuffing, appeared in [2].
> > >
> > > Add 9 frames length definitions:
> > >
> > >  - CAN_FRAME_OVERHEAD_SFF_BITS:
> > >  - CAN_FRAME_OVERHEAD_EFF_BITS
> > >  - CANFD_FRAME_OVERHEAD_SFF_BITS
> > >  - CANFD_FRAME_OVERHEAD_EFF_BITS
> > >  - CAN_BIT_STUFFING_OVERHEAD
> > >  - CAN_FRAME_LEN_MAX_BITS_NO_STUFFING
> > >  - CAN_FRAME_LEN_MAX_BITS_STUFFING
> > >  - CANFD_FRAME_LEN_MAX_BITS_NO_STUFFING
> > >  - CANFD_FRAME_LEN_MAX_BITS_STUFFING
> > >
> > > CAN_FRAME_LEN_MAX_BITS_STUFFING and
> CANFD_FRAME_LEN_MAX_BITS_STUFFING
> > > define respectively the maximum number of bits in a classical CAN and
> > > CAN-FD frame including bit stuffing. The other definitions are
> > > intermediate values.
> > >
> > > In addition to the above:
> > >
> > >  - Include linux/bits.h and then replace the value 8 by BITS_PER_BYTE
> > >    whenever relevant.
> > >  - Include linux/math.h because of DIV_ROUND_UP(). N.B: the use of
> > >    DIV_ROUND_UP() is not new to this patch, but the include was
> > >    previously omitted.
> > >  - Update the existing length definitions to use the newly defined values.
> > >  - Add myself as copyright owner for 2020 (as coauthor of the initial
> > >    version, c.f. [1]) and for 2023 (this patch).
> > >
> > > [1] commit 85d99c3e2a13 ("can: length: can_skb_get_frame_len():
> introduce
> > >     function to get data length of frame in data link layer")
> > > Link: https://git.kernel.org/torvalds/c/85d99c3e2a13
> > >
> > > [2] RE: [PATCH] can: mcp251xfd: Increase poll timeout
> > > Link: https://lore.kernel.org/linux-
> can/BL3PR11MB64846C83ACD04E9330B0FE66FB729@BL3PR11MB6484.n
> amprd11.prod.outlook.com/
> > >
> > > Signed-off-by: Vincent Mailhol <mailhol.vincent@xxxxxxxxxx>
> > > ---
> > > As always, let me know if you have better inspiration than me for the
> > > naming.
> > > ---
> > >  include/linux/can/length.h | 84
> ++++++++++++++++++++++++++++++++------
> > >  1 file changed, 72 insertions(+), 12 deletions(-)
> > >
> > > diff --git a/include/linux/can/length.h b/include/linux/can/length.h
> > > index 6995092b774e..60492fcbe34d 100644
> > > --- a/include/linux/can/length.h
> > > +++ b/include/linux/can/length.h
> > > @@ -1,13 +1,17 @@
> > >  /* SPDX-License-Identifier: GPL-2.0 */
> > >  /* Copyright (C) 2020 Oliver Hartkopp <socketcan@xxxxxxxxxxxx>
> > >   * Copyright (C) 2020 Marc Kleine-Budde <kernel@xxxxxxxxxxxxxx>
> > > + * Copyright (C) 2020, 2023 Vincent Mailhol
> <mailhol.vincent@xxxxxxxxxx>
> > >   */
> > >
> > >  #ifndef _CAN_LENGTH_H
> > >  #define _CAN_LENGTH_H
> > >
> > > +#include <linux/bits.h>
> > > +#include <linux/math.h>
> > > +
> > >  /*
> > > - * Size of a Classical CAN Standard Frame
> > > + * Size of a Classical CAN Standard Frame in bits
> > >   *
> > >   * Name of Field                     Bits
> > >   * ---------------------------------------------------------
> > > @@ -25,12 +29,19 @@
> > >   * End-of-frame (EOF)                        7
> > >   * Inter frame spacing                       3
> > >   *
> > > - * rounded up and ignoring bitstuffing
> > > + * ignoring bitstuffing
> > >   */
> > > -#define CAN_FRAME_OVERHEAD_SFF DIV_ROUND_UP(47, 8)
> > > +#define CAN_FRAME_OVERHEAD_SFF_BITS 47
> > >
> > >  /*
> > > - * Size of a Classical CAN Extended Frame
> > > + * Size of a Classical CAN Standard Frame
> > > + * (rounded up and ignoring bitstuffing)
> > > + */
> > > +#define CAN_FRAME_OVERHEAD_SFF \
> > > +     DIV_ROUND_UP(CAN_FRAME_OVERHEAD_SFF_BITS, BITS_PER_BYTE)
> > > +
> > > +/*
> > > + * Size of a Classical CAN Extended Frame in bits
> > >   *
> > >   * Name of Field                     Bits
> > >   * ---------------------------------------------------------
> > > @@ -50,12 +61,19 @@
> > >   * End-of-frame (EOF)                        7
> > >   * Inter frame spacing                       3
> > >   *
> > > - * rounded up and ignoring bitstuffing
> > > + * ignoring bitstuffing
> > >   */
> > > -#define CAN_FRAME_OVERHEAD_EFF DIV_ROUND_UP(67, 8)
> > > +#define CAN_FRAME_OVERHEAD_EFF_BITS 67
> > >
> > >  /*
> > > - * Size of a CAN-FD Standard Frame
> > > + * Size of a Classical CAN Extended Frame
> > > + * (rounded up and ignoring bitstuffing)
> > > + */
> > > +#define CAN_FRAME_OVERHEAD_EFF \
> > > +     DIV_ROUND_UP(CAN_FRAME_OVERHEAD_EFF_BITS, BITS_PER_BYTE)
> > > +
> > > +/*
> > > + * Size of a CAN-FD Standard Frame in bits
> > >   *
> > >   * Name of Field                     Bits
> > >   * ---------------------------------------------------------
> > > @@ -77,12 +95,19 @@
> > >   * End-of-frame (EOF)                        7
> > >   * Inter frame spacing                       3
> > >   *
> > > - * assuming CRC21, rounded up and ignoring bitstuffing
> > > + * assuming CRC21 and ignoring bitstuffing
> > >   */
> > > -#define CANFD_FRAME_OVERHEAD_SFF DIV_ROUND_UP(61, 8)
> > > +#define CANFD_FRAME_OVERHEAD_SFF_BITS 61
> > >
> > >  /*
> > > - * Size of a CAN-FD Extended Frame
> > > + * Size of a CAN-FD Standard Frame
> > > + * (assuming CRC21, rounded up and ignoring bitstuffing)
> > > + */
> > > +#define CANFD_FRAME_OVERHEAD_SFF \
> > > +     DIV_ROUND_UP(CANFD_FRAME_OVERHEAD_SFF_BITS,
> BITS_PER_BYTE)
> > > +
> > > +/*
> > > + * Size of a CAN-FD Extended Frame in bits
> > >   *
> > >   * Name of Field                     Bits
> > >   * ---------------------------------------------------------
> > > @@ -106,9 +131,32 @@
> > >   * End-of-frame (EOF)                        7
> > >   * Inter frame spacing                       3
> > >   *
> > > - * assuming CRC21, rounded up and ignoring bitstuffing
> > > + * assuming CRC21 and ignoring bitstuffing
> > > + */
> > > +#define CANFD_FRAME_OVERHEAD_EFF_BITS 80
> > > +
> > > +/*
> > > + * Size of a CAN-FD Extended Frame
> > > + * (assuming CRC21, rounded up and ignoring bitstuffing)
> > > + */
> > > +#define CANFD_FRAME_OVERHEAD_EFF \
> > > +     DIV_ROUND_UP(CANFD_FRAME_OVERHEAD_EFF_BITS,
> BITS_PER_BYTE)
> > > +
> > > +/* CAN bit stuffing overhead multiplication factor */
> > > +#define CAN_BIT_STUFFING_OVERHEAD 1.2
> > > +
> > > +/*
> > > + * Maximum size of a Classical CAN frame in bits, ignoring bitstuffing
> > >   */
> > > -#define CANFD_FRAME_OVERHEAD_EFF DIV_ROUND_UP(80, 8)
> > > +#define CAN_FRAME_LEN_MAX_BITS_NO_STUFFING \
> > > +     (CAN_FRAME_OVERHEAD_EFF_BITS + CAN_MAX_DLEN *
> BITS_PER_BYTE)
> > > +
> > > +/*
> > > + * Maximum size of a Classical CAN frame in bits, including bitstuffing
> > > + */
> > > +#define CAN_FRAME_LEN_MAX_BITS_STUFFING                              \
> > > +     ((unsigned int)(CAN_FRAME_LEN_MAX_BITS_NO_STUFFING *    \
> > > +                     CAN_BIT_STUFFING_OVERHEAD))
> >
> > The 1.2 overhead doesn't apply to the whole frame, according to
> > https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8338047.
> 
> You are right. In fact, I realized this mistake before reading your
> message (while I was studying the standard to answer Thomas).
> 
> ISO 11898-1:2015 section 10.5 "Frame coding" says:
> 
>   the frame segment as SOF, arbitration field, control field,
>   data field, and CRC sequence shall be coded by the method of
>   bit stuffing.
> 
> and:
> 
>   The remaining bit fields of the DF or RF (CRC delimiter, ACK
>   field and EOF) shall be of fixed form and not stuffed.
> 
> So, indeed, the bit stuffing does not apply to the last 10 bits (1 + 1 + 1 + 7).
> Furthermore, for FD frames, the CRC field already contains the fixed
> stuff bits. So the overhead shall not be applied again or else, stuff
> bits would be counted twice. In conclusion, for FD frames, the
> otherhead for dynamic bit stuffing overhead should apply to the SOF,
> arbitration field, control field and data field segments.
> 
> After reading the standard, I thought again about the overhead ratio
> and it is more complicated than we all thought.
> 
> Let's use below nomenclature in the following examples (borrowed from ISO):
> 
>   - "0": dominant bit
>   - "o": dominant stuff bit
>   - "1": recessive bit
>   - "i": recessive stuff bit
> 
> We probably all though below example to be the worst case:
> 
>   Destuffed: 11111  11111  11111  11111
>   Stuffed:   11111o 11111o 11111o 11111o
> 
> Here, indeed, one stuff bit is added every five bits giving us an
> overhead of 6/5 = 1.2.
> 
> However, ISO 11898-1:2015 section 10.5 "Frame coding" also says:
> 
>   Whenever a transmitter detects five consecutive bits (*including
>   stuff bits*) of identical value in the bit stream to be
>   transmitted, it shall automatically insert a complementary
>   bit (called stuff bit) ...
> 
> Pay attention to the *including stuff bits* part. The worst case is
> actually a sequence in which dominant and recessive alternate every
> four bits:
> 
>   Destuffed: 1 1111  0000  1111  0000  1111
>   Stuffed:   1 1111o 0000i 1111o 0000i 1111o
>
> Ignoring the first bit, one stuff bit is added every four bits giving
> us an overhead of 5/4 = 1.25.

Duh, absolutely right.

> The exact formula taking in account the first bit we previously ignored then:
> 
>   Number of dynamic stuff bit = 1 + round_down((len(stream) - 5) / 4)
>                               = round_down((len(stream) - 1) / 4)
> 
Right, do you plan on separating this for Arbitration bitrate and databitrate? It would probably make sense to use a fixed number of worst case stuffbits for the arbitration phase and the formula for the data phase.
 
Best Regards,
Thomas