epoll - What does level triggered and edge triggered mean?

[Chicken Mcnuggets]

Hi,

I'm busy implementing a simple networking application in C++ and I want
to use epoll for async network IO on Linux.

But having read through the man page for epoll I'm not entirely sure I
understand what edge triggered and level triggered mean. Can anyone
provide an explanation at all?

I know this is probably a stupid question but I'd be grateful for an answer.

[Jorgen Grahn]

It's worth discussing (I'm not quite sure myself, and only use
traditional level-triggered) but have you read the fairly long
description in epoll(7), "Level-Triggered and Edge-Triggered"?

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paul]

Wiki has the answer.

http://en.wikipedia.org/wiki/Epoll

"Triggering modes

epoll provides both edge-triggered and level-triggered modes.

In edge-triggered mode, a call to epoll_wait will return only
when a new event is enqueued with the epoll object

In level-triggered mode, epoll_wait will return as long
as the condition holds.
"

These are vague references to hardware interrupt types. Hardware
interrupts also had edge triggered and level sensitive options.
On a level sensitive interrupt, if you attempt to clear
the interrupt and do a return-from-interrupt, if the level
is still present, you immediately take the interrupt again.
It was something like that. You can see an example here, so
it's still an occasional topic of discussion.

http://www.qnx.com/developers/docs/qnxcar2/index.jsp?topic=%2Fcom.qnx.doc.neutrino.prog%2Ftopic%2Finthandler_Source_of_interrupt.html

Paul

[Joe Pfeiffer]

Well, hardware interrupts didn't "used to" have either edge or level
triggers, they still do.

Suppose you have more interrupting devices than you have interrupt input
pins on a microcontroller (a very common situation), so you've got two
devices on a single pin. Now suppose both devices need service, so they
both assert the interrupt request line. An interrupt will be requested.

Now suppose you service one of the devices' requests, and it stops
asserting the line. The other one is still asserting.

If you are using level-triggered interrupts, the microcontroller will
notice that the interrupt is still being requested, and you will then go
to service the other device's interrupt. On edge-triggered, a new
assert would be required, so the other device's interrupt will be
ignored.

The two modes on epoll are defined by analogy.

[twent...@b-mint.net]

> Suppose you have more interrupting devices than you have interrupt input
> pins on a microcontroller (a very common situation), so you've got two
> devices on a single pin. Now suppose both devices need service, so they
> both assert the interrupt request line. An interrupt will be requested.

Interesting stuff. How would the microcontroller code know which
device needs to be serviced? Would it have to poll both of them?

I've only got as far as flashing a few leds on an Arduino.

[Joe Pfeiffer]

"twent...@b-mint.net" <twent...@b-mint.net> writes:

>> Suppose you have more interrupting devices than you have interrupt input
>> pins on a microcontroller (a very common situation), so you've got two
>> devices on a single pin. Now suppose both devices need service, so they
>> both assert the interrupt request line. An interrupt will be requested.
>
> Interesting stuff. How would the microcontroller code know which
> device needs to be serviced? Would it have to poll both of them?

Yes.

I'm currently working on a project using a PIC microcontroller -- in
spite of having boatloads of pins that can be used as interrupt inputs,
it has exactly one interrupt vector and one reset vector. When an
interrupt comes in, it's up to software to poll the devices to figure
out why.

[Paul]

Joe Pfeiffer wrote:

>
> Well, hardware interrupts didn't "used to" have either edge or level
> triggers, they still do.

I was thinking along the lines, of whether I have
to know this stuff any more or not :-) At one time,
I had to be very aware of it. It hasn't come up as
a topic of conversation for a while.

Paul

[Chicken Mcnuggets]

Cool. Thanks for that. So it seems that it is just different ways to
notify when the socket has data pending. Makes sense.

Thanks all. I guess I just assumed that there was just one method of
finding out if there was data to be read rather than two which is what
caused the confusion.

Now the decision comes as to which is best to use in my program. I'm
thinking that level-triggered is what I am looking for.

[Eric Sosman]

Keep in mind that the epoll behavior is not dictated by a
piece of hardware you may or may not care about, but is a feature
that allows the programmer to choose how notifications are
handled. The structure of the program may be more amenable to
one style than the other.

--
eso...@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[Rainer Weikusat]

Chicken Mcnuggets <chi...@mcnuggets.com> writes:
> On 27/11/14 14:03, Paul wrote:
>> Chicken Mcnuggets wrote:
>>> Hi,
>>>
>>> I'm busy implementing a simple networking application in C++ and I
>>> want to use epoll for async network IO on Linux.
>>>
>>> But having read through the man page for epoll I'm not entirely sure I
>>> understand what edge triggered and level triggered mean. Can anyone
>>> provide an explanation at all?

[...]

>> "Triggering modes
>>
>> epoll provides both edge-triggered and level-triggered modes.
>>
>> In edge-triggered mode, a call to epoll_wait will return only
>> when a new event is enqueued with the epoll object
>>
>> In level-triggered mode, epoll_wait will return as long
>> as the condition holds.

[...]

> Cool. Thanks for that. So it seems that it is just different ways to
> notify when the socket has data pending. Makes sense.

Not really: 'Edge triggered' means 'the application gets notified when
the state changes' (from 'no input available' to 'input available' or
from 'cannot accept new output' to 'can accept new output'),
'level-triggered' means 'epoll blocks while the state is not ... and
returns immediately while it is'.

The main difference is that an application using edge-triggered
notification must always consume all available input (or send output
until this isn't possible anymore) before invoking epoll again, ie, it
has to use non-blocking I/O and work on its own until an EAGAIN error is
encountered, otherwise, it risks blocking forever despite data is
available. Another would be that there might be 'spurious wakeups':
Assuming an application empties the socket read buffer and a new
data arrives while the application is still busy, it will see the new
data during its next read call. If the next one after that returns
again, it will immediately get an 'input available' notification despite
there is no input because of the 'hidden' state transition which occured
while it processed the second-to-last chunk of data.

[Rainer Weikusat]

Chicken Mcnuggets <chi...@mcnuggets.com> writes:
> On 27/11/14 14:03, Paul wrote:
>> Chicken Mcnuggets wrote:
>>> Hi,
>>>
>>> I'm busy implementing a simple networking application in C++ and I
>>> want to use epoll for async network IO on Linux.
>>>
>>> But having read through the man page for epoll I'm not entirely sure I
>>> understand what edge triggered and level triggered mean. Can anyone
>>> provide an explanation at all?

[...]

>> "Triggering modes
>>
>> epoll provides both edge-triggered and level-triggered modes.
>>
>> In edge-triggered mode, a call to epoll_wait will return only
>> when a new event is enqueued with the epoll object
>>
>> In level-triggered mode, epoll_wait will return as long
>> as the condition holds.

[...]

> Cool. Thanks for that. So it seems that it is just different ways to
> notify when the socket has data pending. Makes sense.

Not really: 'Edge triggered' means 'the application gets notified when
the state changes' (from 'no input available' to 'input available' or
from 'cannot accept new output' to 'can accept new output'),
'level-triggered' means 'epoll blocks while the state is not ... and
returns immediately while it is'.

The main difference is that an application using edge-triggered
notification must always consume all available input (or send output
until this isn't possible anymore) before invoking epoll again, ie, it
has to use non-blocking I/O and work on its own until an EAGAIN error is
encountered, otherwise, it risks blocking forever despite data is
available. Another would be that there might be 'spurious wakeups':
Assuming an application empties the socket read buffer and a new
data arrives while the application is still busy, it will see the new
data during its next read call. If the next one after that returns

EAGAIN, it will immediately get an 'input available' notification on
epoll despite there is no input because of the 'hidden' state transition

[Kaz Kylheku]

A device is "triggered" if has a "trigger" input which governs some
action, such as the the sampling of its remaining input. A single input can't
be triggered.

A device is "level triggered" if it continuously samples its inputs,
or takes some other action, while the trigger input is at the triggering logic
level. A device is "edge triggered" if it samples its inputs only for a brief
moment in time when the trigger is transitioning between logic levels (usually
in a particular direction: rising ("positive edge trigger") or falling
("negative edge trigger")).

Edge triggering is useful because it allows sequential circuits to be easily
constructed which feed their outputs back to their inputs. The narrow sampling
period of the edge trigger means that devices can sample their own outputs so
fast, that those outputs have no time to change by the time the sampling is
done, preventing feedback chaos. Under level triggering, it is more
complicated. The feedback circuit has to be split into interlocking parts
which react to opposite levels of the trigger (or "phases of the clock"), so at
no point in time is there a closed feedback loop leading to chaos. The end
result is that edge-triggering is simulated, using more paorts. As an example,
an edge-triggered D-flip-flop can be constructed from two level-triggered D
flip-flops. They are cascaded together, and one of them gets the trigger signal
inverted relative to the other. This is called the "master-slave
edge-triggered D flip-flop", and it is called "edge triggered" because the
arrangement de-facto looks like edge triggering.

In software, level triggering corresponds to polling a trigger input
continously and taking spontaneous actions based on its instantaneous value.
Keypad example: while an arrow key is held down, a counter on the display
keeps decrementing.

Edge triggering corresponds to getting an event. Keypad example:
the keypad driver generates "key up" and "key down" events for the key
as it changes state. The software decrements the display when it receives
a "key down" event designating the arrow key as the source, and so
that key acts as an edge trigger. This could be done by hardware: we could
have a hardware circuit which debounces the key, and also have the hardware
generate an interrupt when the pin changes state. Or the processor could do all
this in software: periodically sample the pin, debounce the samples and
announce the event.

[Rainer Weikusat]

[more explanations along this]

My explanation was supposed to refer to 'I/O notification'. The other
usual one would be (for PCs at least) 'extension card interrupts': ISA
cards use edge-triggered interrupt signalling: When the 'device' wants
to report something of interest, it generates a pulse (with apologies
for my incorrect use of terminology --- for me 'hardware' manifests
itself as 'programming interface' and I don't care if it works by water
power or because little green slaves run around inside of it or
whatever else) on its interrupt pin. The CPU has to detect that while it
occurs, otherwise, the interrupt was lost. In contrast to this, PCI uses
'level-triggered signallinhg': A card asserts its interrupt line and it
stays high until told to go low again.

[James K. Lowden]

On Fri, 28 Nov 2014 20:26:38 +0000
Rainer Weikusat <rwei...@mobileactivedefense.com> wrote:

> I don't care if it works by water power or because little green
> slaves run around inside

Why are the slaves green? I heard that they're what makes the PCI
cards green, but I don't understand what use chlorophyll is inside the
computer.

--jkl

[Kaz Kylheku]

http://electronics.stackexchange.com/questions/82669/why-are-circuitboards-traditionally-green

--
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1

[Scott Lurndal]

ARMv8 has two pins to the core. IRQ (Interrupt Request) and FIQ (Fast
Interrupt Request). Typically the FIQ signal is used by the most
privileged (secure) software and IRQ is used by the bare-metal OS or
hypervisor.

The Interrupt Controller (GIC) has registers that track the state of
the interrupt sources (around 970 direct wired device interrupts which
may be either level-sensitive or edge-triggered and up to 24 bits of
message-based interrupt numbers that may only be edge-triggered).

When an eligible interrupt is asserted, and the core has not masked
the source interrupt or the IRQ signal, the interrupt vector will be
invoked and the interrupt vector can interrogate a GIC register
(ICC_IAR1_EL1) to determine which source interrupt caused the interrupt
vector to be invoked. Given a system with thousands of interrupt
sources, polling each device would be prohibitively expensive.

The Burroughs B3500 had a single interrupt vector. When an I/O request
was completed on a channel, the channel result-descriptor words in low
core would be updated with the result of the I/O and the interrupt vector
would be invoked. The interrupt routine would scan the result descriptors
for configured channels using the SRD (Scan Result Descriptor) instruction
which would follow link words in the R/D until one was found with the completion
bit set. The order in which the channel R/D's were linked together
controlled the interrupt priority (since SRD generally started at the head of the
list).

The Omega architecture changes to the B4955 added a dedicated hardware
I/O processor that operated asynchronously on IOCB's queued by the OS
to the hardware.

[Rainer Weikusat]

"James K. Lowden" <jklo...@speakeasy.net> writes:
> On Fri, 28 Nov 2014 20:26:38 +0000
> Rainer Weikusat <rwei...@mobileactivedefense.com> wrote:
>
>> I don't care if it works by water power or because little green
>> slaves run around inside
>
> Why are the slaves green?

Because they come from plants.

[Nobody]

On Fri, 28 Nov 2014 17:27:44 +0000, Rainer Weikusat wrote:

> The main difference is that an application using edge-triggered
> notification must always consume all available input (or send output until
> this isn't possible anymore) before invoking epoll again, ie, it has to
> use non-blocking I/O and work on its own until an EAGAIN error is
> encountered, otherwise, it risks blocking forever despite data is
> available.

There's still the possibility of a race condition, i.e. more data arriving
between read() failing with EAGAIN and calling epoll().

[Rainer Weikusat]

I don't quite understand what you're up to: The application must ensure
that the state actually changed from 'data available' to 'no more data
available' in order to fulfill its part of the contract. This has
happened once the kernel told it so, ie, it got an EAGAIN error. It is
then supposed to receive a new 'data available' notification which will
be queued as soon as data arrives and which will be delivered once the
application asks for it.

The 'ISA card and interrupts disabled' analogy obviously breaks down
here although it could be simulated for Linux: Use signal-driven I/O
readiness notification and set the signal disposition to 'ignore' while
processing data. In this case, a signal could be dropped before the
application got around to re-enabling notifications.