Languages, is popularity dominating engineering?

On Sun, 14 Dec 2014 12:56:08 -0700, Don Y <this@is.not.me.com> wrote:

>> For larger allocations returning a NULL pointer makes sense, since it
>> might be perfectly reasonable to try a smaller allocation in some
>> cases.
>
>Or delay the attempt and try again.  The language has no knowledge of how
>it will be applied.

That might be sensible, if the attempted allocation is 20-40 % of the
total dynamic memory, but if you are so low in memory that 1-10 % of
dynamic memory will fail, you are just creating interesting deadlock
situations :-).

On 12/14/2014 1:25 PM, upsidedown@downunder.com wrote:
> On Sun, 14 Dec 2014 12:56:08 -0700, Don Y <this@is.not.me.com> wrote:
>
>>> For larger allocations returning a NULL pointer makes sense, since it
>>> might be perfectly reasonable to try a smaller allocation in some
>>> cases.
>>
>> Or delay the attempt and try again.  The language has no knowledge of how
>> it will be applied.
>
> That might be sensible, if the attempted allocation is 20-40 % of the
> total dynamic memory, but if you are so low in memory that 1-10 % of
> dynamic memory will fail, you are just creating interesting deadlock
> situations :-).

You don't know what other consumers (of that same resource) are doing
AT THIS MOMENT.  Your allocation could succeed if it had been requested
a few microseconds hence -- and *fail* if many more microseconds later.

I allow requests to queue at the allocator in much the same way that you can
queue up for any other resource.  This allows "the most important" request
to proceed *when* the resource (eventually) becomes available and, thus,
avoids lots of "interesting" priority-inversion-type deadlocks (where the
most important consumer didn't happen to make his request at the "opportune"
time).  A timer in each request allows you to decide how long you want to
pend for that request to be satisfied.   (i.e., it can return several
different error *codes* -- not just "NULL" to indicate "failed")

The point is to allow the system *designer* (deliberate emphasis) to come
up with an approach that "works" -- instead of throwing things together and
hoping entropy is on your side...

Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:
>> But if you're allocating buffers or other large objects on the stack,
>> you have to do very careful accounting of the possible call trees, 
>
> As I said before, you need to do that accounting anyway, so that's not
> really much of an argument either way.

Yes it is, if you have 8k of memory and your account says you're using
2872 bytes of stack, then maybe you allocate 3k to it in case you missed
something.  But that's not much of a safety factor.  While if your
account says you're using 82 bytes of stack (because you put those large
objects in static regions instead), you can allocate 1k giving yourself
a safety factor of over 10x.  It's much harder then for anything to go
wrong.

> Compilers for small-ish embedded systems worth their salt usually come
> with a static stack analyzer for that purpose.

How do they do that if the program is using callbacks?

[in other message]
> Stack overflow is something you have to protect against, anyway.

I don't think that is right, see:

http://www.edn.com/design/automotive/4423428/Toyota-s-killer-firmware--Bad-design-and-its-consequences
http://embeddedgurus.com/state-space/2014/02/are-we-shooting-ourselves-in-the-foot-with-stack-overflow/

Am 14.12.2014 um 22:05 schrieb Paul Rubin:
> Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:

>> As I said before, you need to do that accounting anyway, so that's not
>> really much of an argument either way.

> Yes it is, if you have 8k of memory and your account says you're using
> 2872 bytes of stack, then maybe you allocate 3k to it in case you missed
> something.

Or maybe I'll allocate the entire rest of RAM not used by other static 
data to it, because there's no sane reason to leave any RAM go 
completely unused in such a tight situation.

Or I allocate 2875 bytes, depending on how precise my stack size 
determination is.  Static size determination _can_ be perfectly 
accurate, depending on how clever the compiler is, and how strictly some 
coding guidelines are enforced.

> But that's not much of a safety factor.

Rigidly proven upper bounds don't need safety factors.

> While if your account says you're using 82 bytes of stack (because
> you put those large objects in static regions instead),

If i moved 1890 bytes stack consumption's worth of large objects to 
static storage, it's practically guaranteed that the program would fail 
to link, and that would be the end of that.  I would never have to worry 
about stack size again, because the RAM will not even be able to hold 
all those statics, let alone have any space for stack left.

 > you can allocate 1k giving yourself
> a safety factor of over 10x.  It's much harder then for anything to go
> wrong.

It's not, because the underlying assumption that safety lies in factors 
as far as stack usage is concerned is false.  Stacks fail by being one 
byte too small, not by being 10% too small.

>> Compilers for small-ish embedded systems worth their salt usually come
>> with a static stack analyzer for that purpose.

> How do they do that if the program is using callbacks?

Callbacks as such are trivial.  It's calls through function pointers 
that are hard.  And recursion is effectively impossible.  If you avoid 
both (or supply the analysis tool with extra input), the problem becomes 
tractable.

>> Stack overflow is something you have to protect against, anyway.

> I don't think that is right, see:

> http://www.edn.com/design/automotive/4423428/Toyota-s-killer-firmware--Bad-design-and-its-consequences
> http://embeddedgurus.com/state-space/2014/02/are-we-shooting-ourselves-in-the-foot-with-stack-overflow/

Huh?  Did you seriously just link two explanations of why protection 
against stack overflow is absolutely crucial, to back up a claim of 
"It's not needed"?

Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:
> Or maybe I'll allocate the entire rest of RAM not used by other static
> data to it, because there's no sane reason to leave any RAM go
> completely unused in such a tight situation.

Doesn't matter, if your estimate can be off at all, it can be off by
enough to exceed the total remaining ram, especially if that amount is
small.  You can reduce the likelihood if the amount is small.

> Rigidly proven upper bounds don't need safety factors.

Let me know when you manage to rigidly prove anything about a C program.

> If i moved 1890 bytes stack consumption's worth of large objects to
> static storage, it's practically guaranteed that the program would
> fail to link, and that would be the end of that.

OK, then you're in a situation where you have to juggle memory more,
which introduces hazards.  I think that's what Les was getting at.  If
you can't avoid that situation then you have to deal with it, but if you
can avoid it, there are sane arguments for doing so.

> Stacks fail by being one byte too small, not by being 10% too small.

That makes no sense, do you have any examples?  If they can be 1 byte
too small, they can be 2 bytes too small, or 3 bytes, etc.  In the
Toyota case they apparently forgot to take library functions into
account when accounting for stack space.  That's much more than 1 byte.

> Callbacks as such are trivial.  It's calls through function pointers
> that are hard.

How do you think callbacks are normally implemented?  Maybe you're using
that word to mean something different from what I thought it means.

> Huh?  Did you seriously just link two explanations of why protection
> against stack overflow is absolutely crucial, to back up a claim of
> "It's not needed"?

Oh ok, I apparently misunderstood what you were saying, sorry.  But,
that type of problem can be very hard to find statically.  Dynamic
testing in a simulation environment might have had better chance of
spotting the issue, but it can never be guaranteed to cover every
possible input.

Hans-Bernhard Br�ker wrote:
> Am 13.12.2014 um 21:22 schrieb Les Cargill:
>> Hans-Bernhard Br�ker wrote:
>
>>> Making variables static when they don't need to be blows up memory
>>> consumption
>>> considerably.
>
>> This varies.
>
> Not really. Supposing you start out with a correct program and
> compiler, making previously automatic variables static can never reduce
> memory consumption.  It can only increase it.
>

That's absolutely true. I didn't want to insult people's intelligence
and state the obvious - that if you *can't* do something, you probably
shouldn't :)

>> This being said, I haven't seen an 8 bit micro in some time. Even for
>> PIC, they've been 16 or 32 bit and not all that memory constrained.
>
> Careful you don't fall for Microchip's marketing ploys too easily,
> there.  Those 32-bit "PICs" have less of a meaningful relation to the
> original PIC than the doomed Itanium had with the 8086.
>

Heh - pretty much.

-- 
Les Cargill

On 2014-12-14, Don Y <this@is.not.me.com> wrote:
> Hi Simon,
>
> On 12/14/2014 6:55 AM, Simon Clubley wrote:
>>
>> Don't forget that in the message which started this sub-thread I mentioned
>> this was for 8 bit MCUs with limited memory resources available and hence
>> the goal for me is to try and use development techniques which expose
>> problems as early on in the process as possible and do it in a more
>> predictable deterministic way as possible.
>>
>> In 32 bit MCUs with more resources available I go for a much more
>> traditional stack based approach and it's only the big buffers I tend
>> to keep as static.
>
> It really doesn't matter how big the processor is.
>

Hello Don,

That's true. I suppose what's really at play here in my mind is the
percentage of memory resources used by my code and how I have much
more headroom available in the 32 bit MCUs I use.

> Do you only have to verify the brakes work on "fast cars" but not "slow
> cars"?
>
> The stack can overflow on a big MCU just as easily as on a small MCU.
> (probably *more* likely as you may have many more stacks on that big
> MCU -- any of which can be problematic)
>
>> In even larger 32 bit MCUs even the large buffers tend to get dynamically
>> created at run-time in my code.
>
> Let's be clear:  there are three types of memory in play, here.
>

Yes there are and my apologies for confusing you. What I wrongly called
dynamically allocated should have been called stack allocated in the
examples I was thinking of. I do as little true dynamic (malloc style)
allocation as possible.

>
> There is a camp that frowns upon use of (true) dynamic memory allocation
> (because of the "run with scissors" argument:  you can get hurt if you
> aren't careful).  It, however, gives the programmer the most run-time
> flexibility over memory usage (you can create a persistent object *in*
> a function -- like a static would do; *or* an object with limited
> lifetime -- like an auto variable;  you can control that object's
> visibility -- by only "telling" the folks you want to have access to
> it where it is located; etc.)
>

The reason I don't like true dynamic memory allocation in an embedded
system is the risk of fragmented memory if you are freeing the allocations
during normal operations and using a malloc() style allocator. However,
I am aware of the usage cases in which the memory is allocated at startup
and never freed - I do this myself in a couple of cases.

One thing I have done with true dynamic memory allocation in some 32 bit
projects is to use a simple allocator I wrote which allocates fixed size
memory blocks from a pool so there can never be any memory fragmentation
when the memory gets released.

>
> Using statics, you can get the compiler (linkage editor) to tell you
> how much "data" you are consuming.  If this ever exceeds the amount of
> "RAM" in your system, you're screwed.
>
> But, what about when it *doesn't* exceed the amount of RAM?  How do you
> decide how large the stack(s) and heap(s) should be?  (I mean this
> seriously!  Do you just make an arbitrary GUESS and see if the code
> runs?  If it does, how confident are you that every possible combination
> of execution paths/orders will *still* yield a functional system?
>

In my embedded projects, I control everything from the startup code to
the library code to the application code so I can have a good feeling
for how much stack space is required. I also don't really use recursion
all that much in my embedded projects.

That's only an informed estimate however, but if I think I'm going to
use somewhere in the region of (say) 10K-15K bytes of stack space and
my linker map tells me I've got 50K of memory spare then that isn't
something I need to worry about.

However, this breaks down with larger 8-bit MCU projects because of the
much smaller resources available so I can't be 100% confident I will get
the analysis right during design hence my tendency towards static
allocation in that case.

> You still have to know what your maximum stack penetration will be
> (and, in many environments, stack and heap share a memory region;
> stack can grow if heap is shrinking -- retreating towards the opposite
> end of the region -- so this is a tougher metric to evaluate).
>
> Assume you use statics exclusively!  (no recursion, no reentrancy, single
> threaded, etc.)  How do you "count" the stack space consumed by each
> function invocation?  I.e., the "return address" silently pushed onto
> the stack?  Do you have some metric that will TELL you the maximum
> *number* of nested subroutine/function invocations?  Or, do you have
> to look at the code to determine that?
>

Shock, horror, I actually like to do an initial design before writing
any code and think about approximately what memory resources I will
need versus what are available. :-)

> Or, would you study the problem and implementation and come up with
> hard numbers -- backed by data -- that indicate WHY each of your
> design decisions (coding decisions) are appropriate?

Yes.

I most certainly do _not_ pick a number at random and then use that.

My comments above show the kind of thinking I use and that thinking
is geared towards correct functioning of the code and using the tools
I have available to help me with that.

In situations where I can't be confident in my manual stack analysis
I use design techniques designed to minimise that risk. Yes, I accept
that may use more memory, but the technique means I can be more
confident of the code.

Simon.

-- 
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Microsoft: Bringing you 1980s technology to a 21st century world

Les Cargill <lcargill99@comcast.com> writes:
> Sort of. I don't like the idea that RAII is only specific to
> C++... The point of it is to make sure everything is properly
> initialized to a reasonable value.

I think that misstates what RAII means, at least in the C++ world,
as Dombo explained.  For example, in C you might open a file and do
stuff with the contents like this:

   void foo(char *filename) {
      FILE *fd = fopen(filename, "r");
      // compute stuff and read from the file
      close (fd);
   }

but that leaves you with the issue of what happens in case of an
abnormal return, a return from the middle of the function, etc.  You
have to carefully navigate all those possibilities to make sure the file
gets closed instead of leaking the file descriptor.  RAII style in C++
looks like this:

   void foo(string &filename) {
     std::ifstream fs(filename);
     // compute stuff and read from the stream
   }

Note the absence of any call to explicitly close the stream before
returning.  That's because the ifstream object destructor automatically
closes it when the ifstream goes out of scope.  That means if the
function returns from the middle or some lower level throws an
exception, the file still gets closed.  There's not an equivalent for
this in C unless you build a bunch of special machinery into your
application.

> The point is to break calculations, especially those that invoke
> division into manageable chunks for clarity and to control
> divide-by-zero problems. Have the declarations tell the story
> of how the ratio is derived one step at a time.

Sure, that's good style, resembling functional programming; but the term
RAII usually means something different, described above.

>> Hmm, ok a lot of the time, though idioms like
>>    for (p = list_head; p != NULL; p = p->next) { ... }
>> seem perfectly fine.
> I am being very specific to 'C' here.

The above is idiomatic C, I think.

> It's an iterator, so it goes well with the integer-index
> approach. What I've found is that "for every time you need to
> use allocated pointers, there is a cleaner implementation using
> static arrays and indexing into them."

It depends on what you're doing though yeah, dynamic structures are
probably less important in MCU applications.

> It depends. Default signature of functions is void return. I prefer
> to have function returns be used for a list of constraint violations
> until the last one, which is the happy path.

I'd be interested in seeing an example application in this style, if
you've got one you can release.

> This is another fine approach, but it's not one I think you can use as
> much in 'C'. I don't automatically assume "stateful is bad"; it's
> just something that must be managed properly. That probably means "kept
> to a miniumum."

It's easier with garbage collection, but those environments aren't well
suited to small embedded systems.

> You can often allocate buffers and intermediate values statically and
> this helps with serializing for testing.

True.

Hi Simon,

On 12/14/2014 7:21 PM, Simon Clubley wrote:

>> There is a camp that frowns upon use of (true) dynamic memory allocation
>> (because of the "run with scissors" argument:  you can get hurt if you
>> aren't careful).  It, however, gives the programmer the most run-time
>> flexibility over memory usage (you can create a persistent object *in*
>> a function -- like a static would do; *or* an object with limited
>> lifetime -- like an auto variable;  you can control that object's
>> visibility -- by only "telling" the folks you want to have access to
>> it where it is located; etc.)
>
> The reason I don't like true dynamic memory allocation in an embedded
> system is the risk of fragmented memory if you are freeing the allocations
> during normal operations and using a malloc() style allocator. However,
> I am aware of the usage cases in which the memory is allocated at startup
> and never freed - I do this myself in a couple of cases.

It depends on your understanding of how *you* will be using the heap.
Along with your understanding of the strategies that the memory manager
employs in satisfying alloc/free requests.  (along with how many consumers
are prodding that particular heap!)

> One thing I have done with true dynamic memory allocation in some 32 bit
> projects is to use a simple allocator I wrote which allocates fixed size
> memory blocks from a pool so there can never be any memory fragmentation
> when the memory gets released.

My manager moves much of the policy decisions into the hands of the developer.
It is just "mechanism" -- I decide how that mechanism is applied (on each
invocation).

To create a "partition/buffer pool", I use the allocator (on the heap from
which I want to allocate the pool) to first allocate a piece of memory big
enough for the buffer pool.  Then, I claim *this* is a heap and iteratively
allocate N buffers of size M.  These are then free()-d back into that heap
(now a buffer pool -- but still managed with the same allocator!).  But,
in free()-ing them, I tell the memory manager to just insert each of them
at the head of the free list (this is a fixed cost operation -- predictable
performance) and NOT try to coallesce "segments" from the free list into
larger contiguous blocks of memory.  I.e., they *remain* as fixed size
blocks linked together by the free list that the memory manager maintains
*for* me!

Now, any operation requesting a block can use the same allocator, point it
at that "buffer pool" (which, AFAICT, is just another heap!) and request
the "first fitting block" from the pool -- knowing that they are all the
same size -- in yet another constant time operation.

Change the allocation policy -- or free-ing policy -- and the same set
of alloc/free routines can behave differently.

When done with the buffer pool, pass it back to the heap from which
it was allocated via "free" with an appropriate release policy and
now it can be used as "general memory" for other needs.

Having *one* set of routines to manage ALL my memory needs makes it
easier.  E.g., when I create a new process, the same routines create
the initial stack and heap for that process from the "system heap".
Funneling all memory management activities through one interface means
I can make the same capabilities available to every "memory consumer".

E.g., if you want a (arbitrary size) chunk of memory off a particular heap,
you can block waiting for such a chunk to become available.  Because the
same code is involved in doling out "buffers" from that buffer pool, you
can just as easily block waiting for a buffer to become available!  And,
in each case, specify a timeout beyond which you no longer are willing to
wait.  (the alternative is to just "spin" constantly trying to get the
allocator to grant your request... why spin when you can block and let
other/lower priority tasks execute and free up those resources?)

[different mechanisms for OS's that support protection domains]

>> Using statics, you can get the compiler (linkage editor) to tell you
>> how much "data" you are consuming.  If this ever exceeds the amount of
>> "RAM" in your system, you're screwed.
>>
>> But, what about when it *doesn't* exceed the amount of RAM?  How do you
>> decide how large the stack(s) and heap(s) should be?  (I mean this
>> seriously!  Do you just make an arbitrary GUESS and see if the code
>> runs?  If it does, how confident are you that every possible combination
>> of execution paths/orders will *still* yield a functional system?
>
> In my embedded projects, I control everything from the startup code to
> the library code to the application code so I can have a good feeling
> for how much stack space is required. I also don't really use recursion
> all that much in my embedded projects.
>
> That's only an informed estimate however, but if I think I'm going to
> use somewhere in the region of (say) 10K-15K bytes of stack space and
> my linker map tells me I've got 50K of memory spare then that isn't
> something I need to worry about.
>
> However, this breaks down with larger 8-bit MCU projects because of the
> much smaller resources available so I can't be 100% confident I will get
> the analysis right during design hence my tendency towards static
> allocation in that case.

I design the algorithms to optimize whatever resource is most pertinent
(in some cases space, others speed, others writeable store, etc.).  Then,
figure out what drives the algorithm's worst case performance.  And, create
a test case that will stress the algorithm in that manner.  Finally, *measure*
stack penetration (previous methods described) to verify my estimate.

As most of my projects are real-time, there's a certain amount of uncertainty
involved in trying to collect data from a running system *without* altering
the behavior of that system.  So, I debug and characterize algorithms
algorithms in simulators at "D.C." and then crank up the clock in the
run-time environment.

>> You still have to know what your maximum stack penetration will be
>> (and, in many environments, stack and heap share a memory region;
>> stack can grow if heap is shrinking -- retreating towards the opposite
>> end of the region -- so this is a tougher metric to evaluate).
>>
>> Assume you use statics exclusively!  (no recursion, no reentrancy, single
>> threaded, etc.)  How do you "count" the stack space consumed by each
>> function invocation?  I.e., the "return address" silently pushed onto
>> the stack?  Do you have some metric that will TELL you the maximum
>> *number* of nested subroutine/function invocations?  Or, do you have
>> to look at the code to determine that?
>
> Shock, horror, I actually like to do an initial design before writing
> any code and think about approximately what memory resources I will
> need versus what are available. :-)

I suspect you will find this is the exception and not the rule.  Most
folks (esp desktop coders) probably can't tell you *anything* about what
their memory usage looks like with "hard numbers".  Or, even an expression
that they could "massage" to get those numbers!

>> Or, would you study the problem and implementation and come up with
>> hard numbers -- backed by data -- that indicate WHY each of your
>> design decisions (coding decisions) are appropriate?
>
> Yes.
>
> I most certainly do _not_ pick a number at random and then use that.
>
> My comments above show the kind of thinking I use and that thinking
> is geared towards correct functioning of the code and using the tools
> I have available to help me with that.
>
> In situations where I can't be confident in my manual stack analysis
> I use design techniques designed to minimise that risk. Yes, I accept
> that may use more memory, but the technique means I can be more
> confident of the code.

Try some of the techniques I mentioned to see what sorts of numbers
they yield vs. the numbers you get "on paper".  If you don't have access
to compiler sources, you can instrument function/procedure invocations
(clumsily) by creating a macro for each function *definition* that
essentially imposes a short preamble on each function call before
dispatching *to* the specific function.  That preamble can record the
current stack pointer "somewhere" (compare against "worst thus far").
Matching postamble can scan the stack to see how much of it has been
"altered" (from some previously "filled" pattern).

Any time you get stuck using libraries (or any "foreign code"), you're
at the mercy of the developer of those libraries/foreign code.  Most of
this stuff is rarely documented (because the language has no provisions
for documenting internal behavior -- just "interfaces"!)

Back to my baking.  Another 17 dozens tonight.  Not enough days left!  :<

On Sun, 14 Dec 2014 12:56:08 -0700, Don Y <this@is.not.me.com> wrote:

>On 12/14/2014 12:15 PM, upsidedown@downunder.com wrote:
>> On Sun, 14 Dec 2014 11:07:43 -0700, Don Y <this@is.not.me.com> wrote:
>>
>>> There is a camp that frowns upon use of (true) dynamic memory allocation
>>> (because of the "run with scissors" argument:  you can get hurt if you
>>> aren't careful).  It, however, gives the programmer the most run-time
>>> flexibility over memory usage (you can create a persistent object *in*
>>> a function -- like a static would do; *or* an object with limited
>>> lifetime -- like an auto variable;  you can control that object's
>>> visibility -- by only "telling" the folks you want to have access to
>>> it where it is located; etc.)
>>
>> In real time control systems, I use some malloc() but try not to use
>> free() and the system runs for years without reboots :-).
>
>The devil is *always* in the details.
>
>With more "modern" languages (where dynamically allocation is done "for you"),
>you tend to end up with lots of smaller alloc/free actions -- every object
>instantiation potentially poking a hole in the heap's freelist.
>
>In C (explicit allocation/release), the programmer has more control over
>where these allocations are done.   E.g., you almost assuredly wouldn't
>malloc 4 bytes for an int -- and then free it some time later.
>
>> With small systems, there is always the risk of dynamic memory
>> fragmentation. Frequently allocating and freeing variable sized
>> objects, you can easily end up in a situation, in which there are no
>> single _continuous_ memory for new allocations, even if there would be
>> a lot of free heap bytes available.
>
>Again, depends on the allocation pattern.  I have a character-based UI
>that I frequently use in small products.  It lets me create menus, list
>boxes, radio buttons, check boxes, etc. "on the cheap".  It would be
>foolish to static allocate each POSSIBLE UI "control/widget" and just
>let *most* of them sit idle while the interface is running (and ALL of
>them sit idle while the interface is OFF!).
>
>Each object is different size (as each menu, list, etc. can vary based
>on whatever the developer thinks appropriate for *this* control when
>invoked in *this* manner from *this* menu, etc.).
>
>*BUT*, objects tend to be created and deleted (free'd) in complementary
>orders.  So, you don't create 1, 2, 3, 4 and free 2, 4, 1, 3 (which could
>lead to the fragmentation problem you describe).  Rather, 1, 2, 3, 4 are
>deleted as 4, 3, 2, 1.  I.e., a LIFO/stack ordering.

If you are going to have such simple stack access, why don't you use
automatic variables, possibly using alloca() ?

With multiple threads and a single heap, there are no guaranties in
which order memory segments are allocated or released.