error detection rate with crc-16 CCITT

On Mar 29, 10:17=A0am, D Yuniskis <not.going.to...@seen.com> wrote:
> Hi Chris,
>
> On 3/29/2011 8:01 AM, ChrisQ wrote:
>
>
>
>
>
> > upsided...@downunder.com wrote:
>
> >> From the system point of view, including the end of frame detection
> >> (and hence also autobauding) in the ISR makes a lot of sense, since it
> >> reduces the number of times the RT tasks needs to be rescheduled.
>
> > There are arguments for and against and there are tradeoffs, different
> > if, for example, you are running a state driven loop, rather than an
> > rtos. One way to get round the problem is to have an incoming fifo big
> > enough to handle data between polling, then a polling function within
> > the fifo module that takes two args, start of frame and end of frame.
> > The function just scans the fifo from time to time, skipping over
> > duplicate sof until a complete frame is recognised, which is then passe=
d
> > to the deframer / protocol handler. The interrupt handler never needs t=
o
> > be disabled and in the unlikely event of fifo full, the data just wraps
> > round, deleting the least recent byte. Acks, nacks, timeouts and retrie=
s
> > at the next level up then keep the link reliable. You can drive this
> > sort of thing in many ways, for example, from a timer callback. This is
> > more or less how it's been done for decades...
>
> I think the OP is pretty much stuck with having logic in the ISR.
> Consider, the upstream Rx IRQ has to push the received packet into
> the downstream Rx FIFO to propagate the message around that ring.
> At the very least, the Rx ISR needs to decide if the message
> "looks" correct -- at least, "correct enough" to warrant passing
> it along (presumably, you don't want to propagate errors that
> were picked up locally -- since those errors can then become
> UNerrors on the next op...)


The traditional way to lower latency in a ring is to start
transmitting to the next node early - at least as soon as you see that
the address (hopefully at the front of the frame) isn't yours.  If the
frame is bad, you can force that to be passed on by making sure the
ending delimiter is transmitted with an indication of error.  If you
do it right, then in the worst case the bad frame will be pruned at
each node, so even if the address has been damaged* (or it was
addressed to a non-existent node), it'll get removed in a reasonable
amount of time.


*And exactly where the frame is removed from the ring is a design
question.  Often the sender removes frames it had sent, when they make
their way back around, in which case the critical item for removal is
the source address (and usually in that case the destination node sets
a "copied" bit in the trailer, thus verifying physical transmission of
the frame to the destination).

On Mar 29, 12:39=A0pm, ChrisQ <m...@devnull.com> wrote:
> D Yuniskis wrote:
> > Hi Chris,
>
> > I think the OP is pretty much stuck with having logic in the ISR.
> > Consider, the upstream Rx IRQ has to push the received packet into
> > the downstream Rx FIFO to propagate the message around that ring.
> > At the very least, the Rx ISR needs to decide if the message
> > "looks" correct -- at least, "correct enough" to warrant passing
> > it along (presumably, you don't want to propagate errors that
> > were picked up locally -- since those errors can then become
> > UNerrors on the next op...)
>
> > If the Rx ISR had to require the intervention of user-land code
> > (or, any higher level of the protocol stack) to move the received
> > packet "out", then the time spent *in* the node would increase
> > dramatically which is reflected in the RTT of the entire ring(s).
>
> One could ask about the wisdom of using a ring topology, which will
> always involve more latency than a multidrop network using some sort of
> poll / select or request / response protocol. You must have more than one
> comms link for redundancy, as any break in the ring isolates any node
> past the fault. You need double the comms hardware, as each node needs
> an rx and tx uart.



You only need double the comm hardware if you want redundant rings
(I'm not sure if that was the point you were making or not).  On a
single ring (or one one of a pair of double rings), you just need a
funky cable, and connect Tx clockwise, and Rx counterclockwise (or
vice versa) on the ring.  You can add some redundancy by adding some
relays to physically bypass inactive nodes from the ring, and deal
with wire breaks too with an additional pair of wires, and some more
switch gear, but...

...at what point does one just give up on all that custom work, and
just toss on a cheap Ethernet port, and invest in a basic switch?
After all, you can get single quantities of a PIC with Ethernet for
$4.50 (including pretty much everything except the magnetics).  And
that neatly solves bandwidth issues too (if 10Mb isn't enough for some
nodes, you can always give those nodes faster interfaces, and two
nodes talking don't take bandwidth away from other nodes that might
want to talk (assuming a proper switch).

Hi Robert,

On 3/29/2011 3:40 PM, robertwessel2@yahoo.com wrote:

[attributions elided]

>>>>  From the system point of view, including the end of frame detection
>>>> (and hence also autobauding) in the ISR makes a lot of sense, since it
>>>> reduces the number of times the RT tasks needs to be rescheduled.
>>
>>> There are arguments for and against and there are tradeoffs, different
>>> if, for example, you are running a state driven loop, rather than an
>>> rtos. One way to get round the problem is to have an incoming fifo big
>>> enough to handle data between polling, then a polling function within
>>> the fifo module that takes two args, start of frame and end of frame.
>>> The function just scans the fifo from time to time, skipping over
>>> duplicate sof until a complete frame is recognised, which is then passed
>>> to the deframer / protocol handler. The interrupt handler never needs to
>>> be disabled and in the unlikely event of fifo full, the data just wraps
>>> round, deleting the least recent byte. Acks, nacks, timeouts and retries
>>> at the next level up then keep the link reliable. You can drive this
>>> sort of thing in many ways, for example, from a timer callback. This is
>>> more or less how it's been done for decades...
>>
>> I think the OP is pretty much stuck with having logic in the ISR.
>> Consider, the upstream Rx IRQ has to push the received packet into
>> the downstream Rx FIFO to propagate the message around that ring.
>> At the very least, the Rx ISR needs to decide if the message
>> "looks" correct -- at least, "correct enough" to warrant passing
>> it along (presumably, you don't want to propagate errors that
>> were picked up locally -- since those errors can then become
>> UNerrors on the next op...)
>
> The traditional way to lower latency in a ring is to start
> transmitting to the next node early - at least as soon as you see that
> the address (hopefully at the front of the frame) isn't yours.  If the
> frame is bad, you can force that to be passed on by making sure the
> ending delimiter is transmitted with an indication of error.  If you

Yes, but this only makes sense in an environment where errors
are "infrequent".  Note that the OP is talking of error rates
as high as "19 bytes out of 60".  In that case, there's just too
great a chance that you will start passing a corrupted message
with little chance to RELIABLY mark it as such "on the tail
end" (i.e., your error indication stands a good chance of
being corrupted -- what I playfully called "UNerrors")

As a policy, I don't like (implicitly) "blessing" anything
that I don't have a high degree of confidence in ("I" being
code that I write).

> do it right, then in the worst case the bad frame will be pruned at
> each node, so even if the address has been damaged* (or it was
> addressed to a non-existent node), it'll get removed in a reasonable
> amount of time.
>
> *And exactly where the frame is removed from the ring is a design
> question.  Often the sender removes frames it had sent, when they make
> their way back around, in which case the critical item for removal is
> the source address (and usually in that case the destination node sets
> a "copied" bit in the trailer, thus verifying physical transmission of
> the frame to the destination).

Hi Chris,

On 3/29/2011 3:31 PM, ChrisQ wrote:
> D Yuniskis wrote:

>> I know of at least one such design in which the "master(s)" had
>> the ability to impress a high voltage on the bus with the
>> intent that a malfunctioning node wouldn't be smart enough to
>> galvanically isolate itself from the bus during this event
>> (this would blow fuses that would, thereafter, isolate the
>> offending node :> ).
>
> Horrifying, though I guess you could implement that using zener diodes and
> limiting r on each node for protection, placed after, say, 50mA fuses,
> which would be easy to open circuit. Sounds a bit extreme though...

I don't know if it was a result of a client requirement or just
paranoia on the part of the system designer(s) -- the system was
designed for 24/7/365 unattended operation in a hostile physical
environment (with no on-site personnel to even determine if something
was "malfunctioning").  <shrug>  When you have no *practical*
alternatives, I guess you just do the best you can!

On Mar 30, 6:39=A0am, ChrisQ <m...@devnull.com> wrote:
>
> One could ask about the wisdom of using a ring topology, which will
> always involve more latency than a multidrop network using some sort of
> poll / select or request / response protocol. You must have more than one
> comms link for redundancy, as any break in the ring isolates any node
> past the fault. You need double the comms hardware, as each node needs
> an rx and tx uart. In the presence of faults, a ring topology doesn't
> degrade anything like as gracefully, as multidrop either. Finally, where
> does ddcmp fit into the picture ?. Ddcmp is more than just a frame
> format, it's a complete protocol spec with defined messages flows, state
> transitions, error recovery etc...

I found out today ddcmp was used purely because it calculated the CRC
for us.  All it does is the framing.  All the state transition and
error recovery stuff is turned off.  Using ddcmp was probably a
mistake because ccitt crc can be calculated quickly enough and soon
we'll be doing a new version of this device with a different micro
which will have to be compatible with the existing device so will
still have to ddcmp but without the hardware support.

I'm trying to improve the propagation delay of messages around the
ring without requiring the customer to fit twisted pair cable
everywhere and I'm also trying to improve the error monitoring so we
can signal when a connection isn't performing well enough without
creating nuisance faults, hence my interest in the error detection
capability of crc16-ccitt.

We actually already do have an RS485 multi-drop version of this
protocol but it's non-deterministic and doesn't work very well.  I
don't really want to go into that...

On Mar 30, 4:09=A0am, D Yuniskis <not.going.to...@seen.com> wrote:
> Hi Shane,
>
> On 3/28/2011 3:28 AM, Shane williams wrote:
>
> > On Mar 28, 6:23 pm, D Yuniskis<not.going.to...@seen.com> =A0wrote:
> >> Regardless... =A0consider that if you twiddle with the baud rate
> >> on any link, you will either need to make sure *all* links
> >> "simultaneously" update their baud-rates (taking into
> >> consideration any packets "in the pipe")
>
> >> -- or --
>
> >> you have to provide an elastic store in each node and some
> >> smarts to decide what data that node can *drop* (since it's
> >> outbound connection may not? be at the same rate as it's
> >> inbound connection)
>
> >> [this last bit applies iff there is a real second channel
> >> in each node like:
>
> >> =A0 =A0AAAA ----> BBBB ----> CCCC ----> DDDD
> >> =A0 =A0AAAA =A0 =A0 =A0 BBBB =A0 =A0 =A0 CCCC =A0 =A0 =A0 DDDD
> >> =A0 =A0AAAA <---- BBBB <---- CCCC <---- DDDD
>
> > It's physically a 2 wire half duplex ring with messages going in both
> > directions around the ring to provide redundancy. =A0Say 8 nodes 1 to
> > 8. =A0Node 1 talks to nodes 2 and 8, node 2 talks to nodes 1 and 3 etc.
>
> Is this a synchronous protocol? =A0Or, are you just using a pair
> of UARTs on each device to implement the CW & CCW links?


Asynchronous with a pair of uarts, one for clockwise, one for counter-
clockwise.

>
> If that's the case, you have to remember to include all the
> "overhead bit(-time)s" in your evaluation of the error rate
> and your performance thereunder.
>
> E.g., a start bit error is considerably different than a
> *data* bit error (think about it).

Hmm.  I forgot about that.  A start or stop bit error means the whole
message is rejected which is good.


>
> > However we may end up with 3 ports per node making it a collection of
> > rings or a mesh. =A0The loading at the slowest baud rate is approx 10%
>
> [scratches head] then why are you worrying about running at
> a higher rate? =A0

Because not all sites can wire as a mesh.  The third port is optional
but helps the propagation delay a lot.


> Latency might be a reason -- assuming you
> don't circulate messages effectively as they pass *through*
> a node. =A0But, recall that you only have to pass through
> 32 nodes, worst case, to get *a* copy of a message to any
> other node...
>
> > for 64 nodes. =A0If we decide to allow mixed baud rates, each node will
> > have the ability to tell its adjacent nodes to slow down when its
> > message queue gets to a certain level, allowing it to cope with a
> > brief surge in messages.
>
> Depending on how you chose to allocate the Tx&Rx devices in each
> link -- and, whether or not your baudrate generator allows
> the Tx and Rx to run at different baudrates -- you have to:
> * make sure your Tx FIFO (hardware and software) is empty before
> =A0 =A0changing Tx baudrate
> * make sure your "neighbor" isn't sending data to you when you
> =A0 =A0change your Rx baudrate (!)

This is assured.  It's half duplex and the hardware sends a whole
message at a time.


>
> Consider that a link (a connection to *a* neighbor) that "gives you
> problems" will probably (?) cause problems in all communications
> with that neighbor (Tx & Rx). =A0So, you probably want to tie the
> Tx and Rx channels of *one* device to that neighbor (vs. splitting
> the Rx with the upstream and Tx with the downstream IN A GIVEN RING)

Not sure I follow but a single uart does both the tx and rx to the
same neighbor.

>
> [this may seem intuitive -- or not! =A0For the *other* case, see end]
>
> Now, when you change the Rx baudrate for the upstream CW neighbor,
> you are also (?) changing the Tx baudrate for the downstream CCW
> neighbor (the "neighbor" is the same physical node in each case).

Yes

> Also, you have to consider if you will be changing the baudrate
> for the "other" ring simultaneously (so you have to consider the
> RTT in your switching calculations).

What is RTT?


>
> Chances are (bet dollars to donuts?), the two rings are in different
> points of their message exchange (since the distance from message
> originator to that particular node is different in the CW ring
> vs. the CCW ring). =A0I.e., this may be a convenient time to change
> the baudrate (thereby INTERRUPTING the flow of data around the ring)
> for the CW ring -- but, probably *not* for the CCW ring.


I'm lost here.

>
> [recall, changing baudrate is probably going to result in lots
> of errors for the communications to/from the affected neighbor(s)]
>
> So, you really have to wait for the entire ring to become idle
> before you change baudrates -- and then must have all nodes do
> so more or less concurrently (for that ring). =A0If you've split the
> Tx and Rx like I described, then this must also happen on the
> "other" ring at the same time.
>
> Regarding the "other" way to split the Tx&Rx... have the Tx
> always talk to the downstream neighbor and Rx the upstream
> IN THE SAME RING. =A0In this case, changes to Tx+Rx baudrates
> apply only to a certain ring. =A0So, you can change baudrate
> when it is convenient (temporally) for that *ring*.
>
> But, now the two rings are potentially operating at different
> rates. =A0So, the "other" ring will eventually ALSO have to
> have its baudrate adjusted to match (or, pass different traffic)
>

I think there must be a misunderstanding somewhere  - not sure where.

On Mar 31, 1:12=A0am, Shane williams <shane.2471...@gmail.com> wrote:
>
> > > It's physically a 2 wire half duplex ring with messages going in both
> > > directions around the ring to provide redundancy. =A0Say 8 nodes 1 to
> > > 8. =A0Node 1 talks to nodes 2 and 8, node 2 talks to nodes 1 and 3 et=
c.
>
> > Is this a synchronous protocol? =A0Or, are you just using a pair
> > of UARTs on each device to implement the CW & CCW links?
>
> Asynchronous with a pair of uarts, one for clockwise, one for counter-
> clockwise.
>

oops, I made a mistake here  - one uart for neighbour one, another
uart for neighbour 2.  Tx to neighbour one is the CW data (say) and tx
to neighbour 2 is the CCW data.

Hi i am trying to implement bus mastering with the OC PCI Bridge with
a linux (Ubuntu Kernel 2.6.32-24) on a x86. The Bridge is working ok,
but on the PC side i am having a problem. I am trying to allocate the
buffer where the PCI card wil read/write from/to. But when i am
calling pci_alloc_consistent i am getting the following error:

BUG: unable to handle kernel NULL pointer dereference at 00000004
IP: [<c010797f>] dma_generic_alloc_coherent+0xaf/0xc0
*pde = 0a417067 *pte = 00000000
Oops: 0002 [#1] SMP

The code where the function is being called is like

#define TX_BUFFER_FLAGS	 	0x00
#define RX_BUFFER_FLAGS 	0x00
#define TX_DATA_LEN		0x04
#define RX_DATA_LEN		0x04
#define TX_BUFFER_OFFSET 	0x0c
#define RX_BUFFER_OFFSET 	0x0c
#define TX_BUFFER_SIZE 		4096
#define RX_BUFFER_SIZE		4096
#define WB_RX_BUFFER_AM		0xFF000000
#define WB_TX_BUFFER_AM		0xFF000000

static void dma_descriptor_setup(struct pci_dev *pdev)
{
	unsigned long current_address;
	unsigned int  register_value;
	int error = 0;
	unsigned int c_tx_data;
	printk("DMA ALLOC ROUTINE STARTED\n");
	c_memory_map->dma_buffer_rx = pci_alloc_consistent(pdev,
RX_BUFFER_SIZE+RX_BUFFER_OFFSET, &c_memory_map->dma_bus_rx);
	printk("RX DMA BUFFER READY\n");
	c_memory_map->dma_buffer_tx = pci_alloc_consistent(pdev,
TX_BUFFER_SIZE+TX_BUFFER_OFFSET, &c_memory_map->dma_bus_tx);
	printk("TX DMA BUFFER READY\n");
	pci_bridge_devices->current_resource = 0;
	if ( (error = open_mem_mapped(pci_bridge_devices)) )
	{
		pci_bridge_devices->current_resource = -1;
		printk("Could not set BAR0 on DMA alloc\n");
		return;
	}
	printk("PCI ADDRESS FOR TX IS %d AND PCI ADDRESS FOR RX IS %d\n",
c_memory_map->dma_bus_rx, c_memory_map->dma_bus_tx);
	current_address = pci_bridge_devices->page_addr + pci_bridge_devices-
>base_page_offset + BRIDGE_W_AM1_ADDR;
	register_value = WB_RX_BUFFER_AM;
	memcpy_toio(current_address, &register_value, 4);
	current_address = pci_bridge_devices->page_addr + pci_bridge_devices-
>base_page_offset + BRIDGE_W_AM2_ADDR;
	register_value = WB_TX_BUFFER_AM;
	memcpy_toio(current_address, &register_value, 4);
}



It is being called by the init function that is:



static int __init pci_bridge_init(void)
{
	struct pci_bridge_dev *dev;
	dev_t devno;
	int result;
	unsigned short num_of_bases;
	u32 base_address;
	printk("pci_bridge_init called ...\n");

	/*
	* Allocate the per-device structure(s).
	*/
	pci_bridge_devices = kmalloc(sizeof(struct pci_bridge_dev),
GFP_KERNEL);
	if(pci_bridge_devices == NULL)
	{
		result = -ENOMEM;
		goto fail;
	}

	/*
	* Get a range of minor numbers to work with, asking for a dynamic
	* major unless directed otherwise at load time.
	*/
	if(pci_bridge_init_major)
	{
		pci_bridge_major = pci_bridge_init_major;
		devno = MKDEV(pci_bridge_major, 0);
		result = register_chrdev_region(devno, 1, PCI_DRIVER_NAME);
	}
	else
	{
		result = alloc_chrdev_region(&devno, 0, 1, PCI_DRIVER_NAME);
		pci_bridge_major = MAJOR(devno);
	}
	if(result < 0)
	{
		printk(KERN_NOTICE "pci_bridge: can't get major %d\n",
pci_bridge_major);
		goto fail;
	}

	dev = pci_bridge_devices;/* only one device for now */

	/*
	* Initialize and add this device's character device table entry.
	*/
	dev->pcidev = NULL;
	cdev_init(&dev->cdev, &pci_bridge_fops);
	dev->cdev.owner = THIS_MODULE;
	dev->cdev.ops = &pci_bridge_fops;
	dev->offset = 0;
	result = cdev_add(&dev->cdev, devno, 1);
	if(result)
	{
		printk(KERN_NOTICE "Error %d adding %s device", result,
PCI_DRIVER_NAME);
		goto fail;
	}

	if((result = pci_register_driver(&pci_bridge_driver)) != 0)
	{
		printk(KERN_NOTICE "Error %d registering %s PCI device",result,
PCI_DRIVER_NAME);
		goto fail;
	}

	if(dev->pcidev == NULL)
	{
		printk(KERN_NOTICE "PCI DEV is NULL, probe failed?\n");
		goto fail;
	}

	base_address = pci_resource_start(dev->pcidev, 0);

	printk("<1> First base address register found at %08X \n ",
pci_resource_start(dev->pcidev, 0));
	num_of_bases = 0;

	while
	((base_address = pci_resource_start(dev->pcidev, num_of_bases))!=
0x00000000 && (num_of_bases < 6))
	{
		unsigned long flags;
		flags = pci_resource_flags(dev->pcidev, num_of_bases);
		dev->bases[num_of_bases] = base_address;
		dev->base_size[num_of_bases] = pci_resource_end(dev->pcidev,
num_of_bases) - base_address + 1;
		// check if resource is IO mapped
		if (flags & IORESOURCE_IO)
		    dev->base_map[num_of_bases] = BRIDGE_IO_MAPPED;
		else
		    dev->base_map[num_of_bases] = BRIDGE_MEM_MAPPED;
		num_of_bases++;
	}

	if (num_of_bases < 1)
		printk("<1>No implemented base address registers found! \n ");

	dev->current_resource = - 1;

	// store number of bases in structure
	dev->num_of_bases = num_of_bases;
	printk("num_of_bases found %d \n", num_of_bases);
	// display information about all base addresses found in this
procedure
	for (num_of_bases = 0; num_of_bases < dev->num_of_bases; num_of_bases+
+)
	{
		printk("<1>BAR%d range from %08X to %08X \n ", num_of_bases, dev-
>bases[num_of_bases], dev->bases[num_of_bases] + dev-
>base_size[num_of_bases]);
	}

	if(pci_read_config_byte(dev->pcidev,PCI_INTERRUPT_LINE, &dev-
>interrupt_line))
	{
		printk("Could not get interrupt line");
		}
	else
	{
		printk("Interrupt Line is %d \n", dev->interrupt_line);
		}
	dma_descriptor_setup(dev->pcidev);


	return 0;

fail:
		pci_bridge_exit();
		return result;
}

Thank you!

Shane williams wrote:

> 
> I found out today ddcmp was used purely because it calculated the CRC
> for us.  All it does is the framing.  All the state transition and
> error recovery stuff is turned off.  Using ddcmp was probably a
> mistake because ccitt crc can be calculated quickly enough and soon
> we'll be doing a new version of this device with a different micro
> which will have to be compatible with the existing device so will
> still have to ddcmp but without the hardware support.
>

So you using some hardware device with internal crc hw ?. Just
curious, which device ?.

> 
> I'm trying to improve the propagation delay of messages around the
> ring without requiring the customer to fit twisted pair cable
> everywhere and I'm also trying to improve the error monitoring so we
> can signal when a connection isn't performing well enough without
> creating nuisance faults, hence my interest in the error detection
> capability of crc16-ccitt.
>

Two unknowns: Max cable length between nodes and max baud rate ?. Assume
that you are currently running unbalanced rs232 style cabling ?.

If you are limited on baud rate due to cable length, you might be able to
compress the data. A recent project for led road signs was limited to 9600
bauds, but the screen update requirement of 1 second max meant that we 
had no
option but to use compression.

> 
> We actually already do have an RS485 multi-drop version of this
> protocol but it's non-deterministic and doesn't work very well.  I
> don't really want to go into that...
> 

Sounds like a better place to start, from a technical point of view :-)...


Regards,

Chris

On Mar 30, 11:40=A0am, "robertwess...@yahoo.com"
<robertwess...@yahoo.com> wrote:
>
> The traditional way to lower latency in a ring is to start
> transmitting to the next node early - at least as soon as you see that
> the address (hopefully at the front of the frame) isn't yours. =A0If the
> frame is bad, you can force that to be passed on by making sure the
> ending delimiter is transmitted with an indication of error. =A0If you
> do it right, then in the worst case the bad frame will be pruned at
> each node, so even if the address has been damaged* (or it was
> addressed to a non-existent node), it'll get removed in a reasonable
> amount of time.

It's half duplex so we can't start transmitting early.


>
> *And exactly where the frame is removed from the ring is a design
> question. =A0Often the sender removes frames it had sent, when they make
> their way back around, in which case the critical item for removal is
> the source address (and usually in that case the destination node sets
> a "copied" bit in the trailer, thus verifying physical transmission of
> the frame to the destination).

In our case, there are two logical rings and each message placed on
the ring is sent in both directions.  When the two messages meet up
approximately half-way round they annihilate each other - but if the
annihilation fails, the sender removes them as well.