Discussion on state machines

[SiliconWizard]

It is more than likely that somebody will code "state++;" to move onto the next state.

Cannot do "state++" if state is a function pointer.

Sure, but state could just be an integer indexing a function pointers' table.

[tggzzz]

It is more than likely that somebody will code "state++;" to move onto the next state.

Cannot do "state++" if state is a function pointer.

"stateIndex++", should you have insufficient taste to do that.

[tggzzz]

As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.

Regarding that article I agree with the first comment "This is an excellent troll and strawman argument.".
(...)

Pretty much so. This article has been posted to the comp.lang.c newsgroup and has elicited a fair amount of posts.

Attention whores (whether this is done on purpose or not) live on this kind of negative-sided, fallacious articles, that unfortunately tend to generate a lot more traction than constructive ones.

I wonder what proportion of C programmers read comp.lang.c. ?
I wonder whether those that do are more competant than the majority of C programmers?
The difference between theory and practice is that in theory there is no difference, whereas...

[tggzzz]

An excellent point and one of the many reasons I prefer C for most things.  It's easy to understand the rules and what will actually happen.

Er, no. Or at least only at a superficial level.

As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.

Of course, for numerical work FORTRAN is better.  Lex, yacc, awk and MATLAB/Octave all have their places too.

Er, yes

Sadly, I would not disagree about the knowledge level of the generic programmer.  My general observation is that the entire compile, link, execute cycle is magic to most for any language, even K&R C or C89.

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

Programmers have even less of a clue what C++ does.  In fact, I assert that no one understands C++. 

And that included the people designing and specifying C++ templates. They thought they did until their noses were very publicly rubbed in their ignorance. They refused to believe their own C++ template language was itself Turing-complete.

While I disagree with the use of "discovered" in this statement...
"Historically TMP is something of an accident; it was discovered during the process of standardizing the C++ language that its template system happens to be Turing-complete"[1]
it does indicate that the tool itself was beyond its designers comprehension.

[1]https://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming#History_of_TMP

<Snipped sensible observations>

[tggzzz]

OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."

That's an indication that C is part of the problem; I prefer tools that are part of the solution.

No, it was trick question.

The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero?   Yes / No / Don't know

No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).

That's very revealing because, if you think about it, what you claim to be able to do is simply impossible.

Hint: you might be able to make your point for one compiler with one target machine with one set of compiler flags - for one version of that compiler (because C compilers/linkers can and do change the code they emit).

I'll bite....

This will ALWAYS have zeros in the padding (The 'Yes' example):

Sigh. I've omitted your code which indicates that you didn't understand the hint, let alone the point.

[SiliconWizard]

Regarding structure padding: the ISO C standard states it clearly:

When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.

Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.

If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.

[NorthGuy]

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

The set of skills to get the job is different from the set of skill to do the job, often even opposite.

It may bot be obvious with programmers. A more intuitive example is presidential elections. The set of skills necessary for election complain is almost entirely opposite to what a good president needs to do the job.

[NiHaoMike]

Regarding structure padding: the ISO C standard states it clearly:

When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.

Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.

If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.

Sounds like a potential security vulnerability in that it may allow bits of highly secret information to leak into unexpected places where protecting access is not considered.

[NorthGuy]

It is more than likely that somebody will code "state++;" to move onto the next state.

Cannot do "state++" if state is a function pointer.

Sure, but state could just be an integer indexing a function pointers' table.

I guess function pointers are not only more flexible, faster and use less memory compared to the tables, function pointers are also safer.

[SiliconWizard]

There are myriads of other potential ways of hiding stuff in memory, and unless your software permanently checks whether any memory area has been modified unexpectedly (using CRCs for instance, but even so, the CRCs could be compromised in the right way), you have no real means of controlling this if the areas in question are not protected anyway.

You still have a portable way of forcing padding bytes to zero.
Every time you write to a struct member, zero out the following padding bytes after the write (dummy bytes between this member and the next member) with a call to memset(). You can use offsetof() to get the index of each member inside the struct. Granted it would be cumbersome, but it works. You could then also check if the padding bytes have changed values by accessing them as bytes, again using offsetof() to compute the pointer to the padding bytes, and compare them to zero. This should do the trick in a fairly portable way, but you'd still be in a kind of gray area. Here we're assuming that only writes to struct members could be the cause of modification of padding bytes. This assumption is reasonable. But you may encounter some platform that still can't guarantee that padding bytes' values are retained even if no write occurs. It's probably very unlikely, but you have no guarantee.

[NorthGuy]

You still have a portable way of forcing padding bytes to zero.

How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.

Even if you can't avoid padding, you can always add reserved structure members where the padding would be.

[SiliconWizard]

You still have a portable way of forcing padding bytes to zero.

How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.
Even if you can't avoid padding, you can always add reserved structure members where the padding would be.

That's right
But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).

That said, you don't necessarily have to be perfectly portable if you intend not to and you document it properly, especially for embedded stuff. In this case, I would suggest doing what you said AND forcing struct alignment with '__attribute__((aligned(xx))' (with GCC) or the more pervasive #pragma pack(xx) which still happens to work with most compilers. Thus you'll guarantee proper alignment and no padding.

[rhb]

You still have a portable way of forcing padding bytes to zero.

How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.
Even if you can't avoid padding, you can always add reserved structure members where the padding would be.

That's right
But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).

That said, you don't necessarily have to be perfectly portable if you intend not to and you document it properly, especially for embedded stuff. In this case, I would suggest doing what you said AND forcing struct alignment with '__attribute__((aligned(xx))' (with GCC) or the more pervasive #pragma pack(xx) which still happens to work with most compilers. Thus you'll guarantee proper alignment and no padding.

Avoiding padding is trivial on everything I've ever used which was pretty much every participant in the Unix wars.

You allocate members from largest to smallest.  If you do that no padding is required and the structure is portable across everything.

[Bassman59]

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?

(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)

[Nominal Animal]

Avoiding padding is trivial on everything I've ever used which was pretty much every participant in the Unix wars. You allocate members from largest to smallest.

That works only as long as you do not need a new version of the library, with added members in the same structure, to be backwards compatible with older binaries. (So, basically, stuff in the standard C library, or used between userspace and the kernel.)

On the other hand, the only structure that I am aware of that has been sensitive to padding bytes, is struct sigaction. Rather than relying on e.g. struct sigaction act = {0}, it should be cleared to zero using e.g. memset(&act, 0, sizeof act). Quite possibly its usual implementation via union and preprocessor macros is a culprit... All the other structures seem to have explicit "padding" members that can be reused for future extension, like struct stat64 on most systems.

[rhb]

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?

(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)

When run times are measured in tens of thousands of CPU days, everything matters.  I wrote a seismic processing code which used a double stride through the array and temporary variables for the A and B portions of the stride because it got me a 5% speedup on a DEC Alpha which at the time was faster than x86 by a factor of 5x.  This also was the only instance in my life where i used a computed GOTO in FORTRAN.  That saved me a long it-then-else with the attendant conditional delays.

In the end, what matters most is what type of problem are you solving.

In high performance computing you worry about every detail of the processor and compiler.  Small changes in code or machine can have very large impacts upon performance.  You study the hardware, the compiler and the program and then run test cases to find the best solution.

[NorthGuy]

But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).

It is not portable in theory, but in practice if you align 64-bit members to 8-byte boundaries, 32-bit members to 4-byte boundaries and 16-bit members to 2-byte boundaries (all relative to the beginning of the structure), and then round up the size of the structure (by adding reserved items), you won't need any padding.

[tggzzz]

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?

(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)

There are myriad other questions in the same vein that are applicable to "high level programmers", such as "what caches there are in the system you have used, and what are their principal characteristics", "what is a two phase commit, and why is it necessary", "where have you used/seen an FSM" etc etc etc.

The answers to such questions indicate whether the candidate understands theory and how it informs/shapes practice, whether they are curious about technology or simply time-serving sheep. That's enlightening.

[tggzzz]

A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers

Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?

(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)

When run times are measured in tens of thousands of CPU days, everything matters.  I wrote a seismic processing code which used a double stride through the array and temporary variables for the A and B portions of the stride because it got me a 5% speedup on a DEC Alpha which at the time was faster than x86 by a factor of 5x.  This also was the only instance in my life where i used a computed GOTO in FORTRAN.  That saved me a long it-then-else with the attendant conditional delays.

In the end, what matters most is what type of problem are you solving.

In high performance computing you worry about every detail of the processor and compiler.  Small changes in code or machine can have very large impacts upon performance.  You study the hardware, the compiler and the program and then run test cases to find the best solution.

Well said.

From my experience I'll add high-availability telecoms systems.

For example, I've seen other people come an almighty cropper (with two companies CEOs in contact about it) because they didn't understand sufficient theory and practice to be able to ask the salesman necessary pointed questions about a disc system's operation and its effects on performance.

[hamster_nz]

Regarding structure padding: the ISO C standard states it clearly:

When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.

Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.

If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.

Even the technical correct answer to the question "Will any padding be filled with zeros?" is "I do not know", it is ambiguous.

Does it mean "I am ignorant of the answer to the question" or is it "I cannot make any assumption about the values of padding, it may or may not be filled with zeros, so the answer isn't yes or no".

It is a trick question.

[rhb]

"It is implementation defined." is the strictly correct answer.   I'm not going to look it up in the standard, but I am highly sensitized to the "implementation defined" and "undefined" clauses.  Padding is one of them.

I was offered a job at Digital Switch as CASE tools lead for a 600 person group.  A 15 minute conversation with the hiring manager in a borrowed cubicle in another building followed by a meeting with an HR flack to discuss salary.  I never met or even saw anyone I would be working with.I initially accepted, but after going through the drug testing and a bunch of other BS I got cold feet and backed out.  I felt very much like a lamb being led to slaughter to satisfy the hiring manager's superiors.  This was not long after the big SS7 meltdown in the 90's.

The thing I find sad is I wrote a couple of 15,000 line libraries which included a parser built with lex and yacc and the FORTRAN calling C calling FORTRAN table of function pointers.  It ran in operation without any maintenance for about half the  15-16 years it was in use.  The first year the system it was deployed  I wrote the release notes.  We had fewer than a dozen user submitted bug reports.  By the time the company merged to form a super major there were almost no bug reports at all.  Most of the work was done by me and one other contractor.  He suggested we have a regression test facility, so I built one which we ran every time the system was built. Any time we wrote a piece of code the next activity was to create a basic test suite and compile and test on a couple of systems.  The whole thing was a port of scientist written code from VMS to Unix. Ulimately it would compile on 6 systems, Sun, SGI, IBM, DEC, Intergraph and HP. The only #ifdefs were for byte sex and RECL=. Initial port was SunOS 4.1.1 and Intergraph CLIX, a very bare bones (15 or 16 character file names) Sys V implementation.  The IBM took a month or two because the IBM compiler would not allow branching into conditionals.  The HP port took 2-3 weeks.  I did the Ultrix and Irix ports in about 4 hours on an idle afternoon.  The official stance was it was supported on any platform that that the business affiliate would pay for validating the test suite.  That did a marvelous job of cutting off people complaining about the "lack of support" on whatever systems they had bought.

[obiwanjacobi]

I have always found the switch/case way of implementing a state machine kind of a hack.
I know you are all C fanboys but I personally like the async-await pattern (C#/TypeScript) very much (as an example).
It implements a state machine in the background to keep track of to where execution was progressed.

So in that light I seldom write naked switch/case state machines and although I try to avoid macros like the plague, in this case they enable a cleaner syntax. The state machine becomes a task that codes the functionality as sequential list of statements.

[2c]

[tggzzz]

I have always found the switch/case way of implementing a state machine kind of a hack.
I know you are all C fanboys but I personally like the async-await pattern (C#/TypeScript) very much (as an example).
It implements a state machine in the background to keep track of to where execution was progressed.

Switch/if-then-else is adequate for very simple FSMs, but rapidly becomes incomprehensible and unmaintainable.

The half-sync half-async design pattern (by wiatever name ) is indeed very powerful, comprehensible and scalable in terms of performance. However it is completely language independent and does not favour "Microsoft's Java", even if Microsoft does use it a lot in their frameworks built on top of their language.

[Howardlong]

It’s also resource hungry on low powered devices, not to mention adding even more indeterminism for real time systems.

But then, if you’re writing in C# under CLR, you won’t be doing deterministic real time systems, let alone on resource limited platforms.

[obiwanjacobi]

It’s also resource hungry on low powered devices, not to mention adding even more indeterminism for real time systems.

But then, if you’re writing in C# under CLR, you won’t be doing deterministic real time systems, let alone on resource limited platforms.

I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.

Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.

Also there is nothing wrong with abstraction or indeterminism (assuming you mean roughly the same as abstraction-ism with that).
C and C++ are abstractions or do you code in ASM? 
Any good library is an abstraction. I think you should be careful to chuck things on the "too expensive" (resources/learning curve/etc.) wagon and not consider it any further. It may not be more expensive that you trying to do it yourself.
Also, It may be worth the cost of using more resources for having more readable (understandable/maintainable) code. Depends.
Perhaps only a very small portion of the code needs to be close to the metal...?