| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <BL3PR11MB64841417866BA13DFEA3E373FB769@BL3PR11MB6484.namprd11.prod.outlook.com>
Date: Tue, 9 May 2023 07:12:47 +0000
From: <Thomas.Kopp@...rochip.com>
To: <mailhol.vincent@...adoo.fr>, <mkl@...gutronix.de>
CC: <linux-can@...r.kernel.org>, <marex@...x.de>,
<linux-kernel@...r.kernel.org>
Subject: RE: [PATCH] can: length: add definitions for frame lengths in bits
Hi Vincent,
> On Mon. 8 May 2023 at 21:29, Marc Kleine-Budde <mkl@...gutronix.de>
> 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@...PR11MB6484.n
> amprd11.prod.outlook.com/
> > >
> > > Signed-off-by: Vincent Mailhol <mailhol.vincent@...adoo.fr>
> > > ---
> > > 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@...tkopp.net>
> > > * Copyright (C) 2020 Marc Kleine-Budde <kernel@...gutronix.de>
> > > + * Copyright (C) 2020, 2023 Vincent Mailhol
> <mailhol.vincent@...adoo.fr>
> > > */
> > >
> > > #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
Powered by blists - more mailing lists