Dynamic memory allocation is not widely used by embedded software developers—and for good reasons. One of those is the problem of fragmentation of the heap.

All data structures created via C’s malloc() standard library routine or C++’s new keyword live on the heap. The heap is a specific area in RAM of a pre-determined maximum size. Initially, each allocation from the heap reduces the amount of remaining “free” space by the same number of bytes. For example, the heap in a particular system might span 10 KB starting from address 0×20200000. An allocation of a pair of 4-KB data structures would leave 2 KB of free space.

The storage for data structures that are no longer needed can be returned to the heap by a call to free() or use of the delete keyword. In theory this makes that storage space available for reuse during subsequent allocations. But the order of allocations and deletions is generally at least pseudo-random—leading the heap to become a mess of smaller fragments.

To see how fragmentation can be a problem, consider what would happen if the first of the above 4 KB data structures is free. Now the heap consists of one 4-KB free chunk and another 2-KB free chunk; they are not adjacent and cannot be combined. So our heap is already fragmented. Despite 6 KB of total free space, allocations of more than 4 KB will fail.

Fragmentation is similar to entropy: both increase over time. In a long running system (i.e., most every embedded system ever created), fragmentation may eventually cause some allocation requests to fail. And what then? How should your firmware handle the case of a failed heap allocation request?

Best Practice: Avoiding all use of the heap may is a sure way of preventing this bug. But if dynamic memory allocation is either necessary or convenient in your system, there is an alternative way of structuring the heap that will prevent fragmentation. The key observation is that the problem is caused by variable sized requests.

If all of the requests were of the same size, then any free block is as good as any other—even if it happens not to be adjacent to any of the other free blocks. Thus it is possible to use multiple “heaps”—each for allocation requests of a specific size—can using a “memory pool” data structure.

If you like you can write your own fixed-sized memory pool API. You’ll just need three functions:

• handle = pool_create(block_size, num_blocks) – to create a new pool (of size M chunks by N bytes)


• p_block = pool_alloc(handle) – to allocate one chunk (from a specified pool)


• pool_free(handle, p_block)

But note that many real-time operating systems (RTOSes) feature a fixed-size memory pool API. If you have access to one of those, use it instead of the compiler’s malloc() and free() or your own implementation.

In several of my previous posts I have written about the fact that embedded virtualization has low overhead, maintains determinism and all that good stuff. I have also written about some of the benefits of virtualization due to partitioning, scalability and such.

However, there is one aspect of virtualization that gets little 'air time' and that is the fact that there the hypervisor really is a nice, lean, partitioned management layer of your multicore (or single core) hardware.

You may wonder why that is important. Well, take a 'system of old', you would have a single core, with an OS and on top of that OS a piece of software that monitors 'sanity' of the system. Sanity here is in relation to the sanity of the hardware and the sanity of the application. This monitor keeps track of exceptions thrown by the processor, the operating system and the application and based on its state decides how and whether to continue operations. It does this by installing fault handler to handle the exceptions. Often these handlers try to correct the problem and log the occurrence of the problem as well, so an off-line engineer can look at the log later and try to debug the problem if that becomes necessary.

Now, the true problem comes when a fault occurs in a fault handler. This can happen if things are really broken, maybe due to faulty hardware, or maybe due to memory corruption. If this happens, there often is no other solution but to reboot, a fairly heavy handed solution. One could of course use a JTAG connection to the system if available, but if the system is already fielded, then this is simply not available.

Project this situation to a system built on a Hypervisor. The operating system with the application and the fault handlers is actually running on top of a Hypervisor. The operating system is strongly separated from the Hypervisor in terms of memory areas. So if a fault happens, the Hypervisor is still available and in a sane state unless the problem is truly hardware related, in which case you are out of luck. If the problem is software related, then the Hypervisor can step in when one of these fault situations happens.

The hypervisor contains the fault and can actually be used to explore the state of the partition (the Virtual Board) and find out what happens. The Hypervisor has a record of interrupts received and acknowledged, can walk the memory and dump the memory out over an network connection. It is often not possible to correct the fault, but the hypervisor provides additional debugging capabilities, either manual (by using the Hypervisor debugging shell) or automated by writing fault handlers and recovery code as part of your Hypervisor BSP.

There are a couple of neat ways of using this fault containment. Firstly, as stated, one can elaborate the fault handler in the Hypervisor to do funky things, handle the code, log the code. However, that is really not an elegant solution, you are adding code to the Hypervisor which should really not be there. The more elegant design would be separate the gathering of information (something the Hypervisor should do) and the actioning on that information, which can be done in a separate Virtual Board that gets a tiny slice of one of the processors in the system.

An example of a problem that could benefit from a fault handler in a hypervisor is the stack overflow detection and handling described by Michael Barr in his post.

All in all, another example of how virtualization is changing the way people develop embedded systems.

With all the traffic lighting being converted to LEDs as well as all the brake and tail lighting being converted, you get a chance to stare at a lot of LEDs. Maybe it is just me, but it does seem that not all of them are lit when they should be. In my less than scientific sampling, it seems the green lights are the ones with the most led drop out and then red is next. I don’t think I get a chance to look at the yellow lights long enough to tell if any of them are out.

The green lights seem to fail in irregular patterns. The red lights seem to have a few randomly scattered LEDs out. The largest number of red led samplings come from the tail and break lights, which it seems that I get much more time to observe. I would think that with LEDs, the days of driving behind cars with nonfunctional rear lights should be coming to a close, but there still appears to be some work ahead.

Most often, it's the whole tail lamp that's not working. But occasionally, I do see a few with just some LEDs out. I wonder if it's just statistics, more bulbs so a higher chance of failure. I Googled the number of LEDs in a traffic light and could not find an answer. I did find out that traffic lights were bigger than I thought, 8 inches or even bigger. I counted the LEDs in an eight inch light and came up with 174. It could have been 175, I only counted once.

Next time you are stuck at a traffic light or just setting in traffic, look around and see if you find LEDs that are out. There might just be an opportunity to fix something.

Every programmer knows that a stack overflow is a Very Bad Thing™. The effect of each stack overflow varies, though. The nature of the damage and the timing of the misbehavior depend entirely on which data or instructions are clobbered and how they are used. Importantly, the length of time between a stack overflow and its negative effects on the system depends on how long it is before the clobbered bits are used.

Unfortunately, stack overflow afflicts embedded systems far more often than it does desktop computers. This is for several reasons, including:

1. embedded systems usually have to get by on a smaller amount of RAM


2. there is typically no virtual memory to fall back on (because there is no disk)


3. firmware designs based on RTOS tasks utilize multiple stacks (one per task), each of which must be sized sufficiently to ensure against unique worst-case stack depth


4. interrupt handlers may try to use those same stacks

Further complicating this issue, there is no amount of testing that can ensure that a particular stack is sufficiently large. You can test your system under all sorts of loading conditions but you can only test it for so long. A stack overflow that only occurs “once in a blue moon” may not be witnessed by tests that run for only “half a blue moon.” Demonstrating that a stack overflow will never occur can, under algorithmic limitations (such as no recursion), be done with a top down analysis of the control flow of the code. But a top down analysis will need to be redone every time the code is changed.

Best Practice: On startup, paint an unlikely memory pattern throughout the stack(s). (I like to use hex 23 3D 3D 23, which looks like a fence ‘#==#’ in an ASCII memory dump.) At runtime, have a supervisor task periodically check that none of the paint above some pre-established high water mark has been changed. If something is found to be amiss with a stack, log the specific error (e.g., which stack and how high the flood) in non-volatile memory and do something safe for users of the product (e.g., controlled shut down or reset) before a true overflow can occur. This is a nice additional safety feature to add to the watchdog task.

As a member of the IEEE Standards Association’s Corporate Advisory Group, I had the pleasure of traveling to India to participate in a seminar, “Global Standards at IEEE,” and in outreach meetings with various organizations and companies. This was my first trip to India, and I must say it was amazing.

During the outreach with the India Semiconductor Association (ISA), I was intrigued by Mr. Anil Gupta’s discussion about challenges facing India in the electronics market and potential solutions to address them. Mr. Gupta is currently a board member of the executive council of the ISA and an eloquent speaker. I was educated by his brief talk - which included a standards element - and I’d like to share a summary with you.

Presently, India’s consumption of electronic products is roughly $40-45B. Its engineering contribution to this market is around 4%. (That’s a fairly small number.) Over the next 10-12 years, India’s electronics consumption could rise to $400B. If the contribution rate continues at its current level – around 4-5% – India’s foreign exchange reserve of $280B would get exhausted just by its electronics consumption, presenting another challenge to the country’s economic condition.

The Indian government recognizes this situation and is thinking about what India can do to better balance the contribution side. The government doesn’t want to create a barrier to entry of foreign products to their own consumers. If Indian consumers are not prohibited from purchasing good products from anywhere, this benefits the Indian consumers. The Indian government thinks (and I agree) that instead of setting up trade barriers, a better way to balance their foreign exchange is to boost local (quality) production. Giving incentives to increase local production could be one of several avenues to make this happen over the next decade. Standards, too, are able to help a lot when it comes to increasing product development. Instead of Indian engineers having to come up with everything on their own, they can leverage standards to contribute right away.

In India today, there are some pockets of local production for the electronics market, and in the EDA space there’s quite a bit of activity, such as PDK development and IP creation with SystemVerilog. There’s also increasing production in embedded software and application software. In academia, there is some research going on, but it’s still limited.

India’s future could include lots of integration – i.e., product components coming to the country for assembly into complete products. Infrastructure is needed, of course, but standards would help integrators take advantage of product integration industries.

India’s future could also include a larger number of PhD candidates. The ISA would like to incentivize an increase in the number of PhDs. Presently, there isn’t much need for PhD’s to do “regular” work – tasks that could be considered menial. There’s not much demand today for PhDs because organizations (companies) are mainly performing implementation as opposed to research and development. And Indian PhD candidates are trained mainly in the theoretical instead of in applied fields which can help improve local product development and production. To effect the end of PhDs ready to aid in boosting local production, the starting place is with the faculty – improving their knowledge base and their teaching materials (curricula).
The next decade is critical to India. The ISA believes the shift in academia is coming and industry will also move forward.

The plan was to post a blog from APEC 2010, ok that did not happen. APEC is one of those conferences where you never get to do all that you want. With all the networking, meeting up with old buddies, and the great technical sessions, I for one always fall short of my intentions. Hey, there is always next year in Fort Worth, Texas for 2011.

APEC 2010 has been over for about two weeks and I am about through reading one third of the papers covering connecting power to the “Grid.” This year had a bumper crop of about 20 technical papers about grid connected power out of more than 370 papers. One paper, “Efficiency Improvement of Grid-tied Inverters at Low Input Power Using Pulse Skipping Control Strategy” covering pulse skipping techniques for lower power into the grid is very interesting.

Although most think of the peak power when thinking about PV systems there are many times when the sun is up but the power is about 1/10 of the peak, cloudy days for example. In Dallas, we think most days are sunny, but according to Weather Today, we only average about 135 days per year. Recently, it seems that we are closer to one sunny day out of every five. So low light power operation is important.

It's not that every “non-sunny” day is about 1/10 sun, but that there are a significant number of days where we are operating at the less than 20% of peak. So for renewable energy solutions, we need to consider light power efficiency just like other applications consider light load operation. For the solar industry, every day is a sun day but not every day is a sunny day in more than just one way.

Dave Freeman is a system engineering manager in the Power business at Texas Instruments. He also manages the company's Solar Energy Systems Lab.

I received a bunch of emails today pointing to this blog from Jason Perlow. Jason has an interesting thought with regards to the Apple and HTC lawsuit that is brewing. Let me first say that I understand that companies have to protect their IP and that there are clearly important and enforceable patents out there, say Coca Cola's formula for well, Coca Cola. Apple certainly has a lot of valuable IP as well and they are spending a lot of dollars in making the user experience better. Some of these patents are vague at best, so I have mixed feelings on this and since I am not a lawyer I am going to leave it at that.

Jason's blog evolves around hypervisors and his fantasy world in which they can change the way we build mobile phones. This is not a fantasy world, in the fact that what Jason wants is technically very possible. However, it would also require alliances between some of the fiercest competitors in one of the biggest markets in the world. Unlikely to happen, however, allow me to dream with him.

Virtualization can be used separate the nuts (the piece that makes a phone talk over the network) from the glory (the piece that makes it looks pretty and provides applications), no nuts no glory, they are both needed, but they need to be kept separate. The nuts would be real-time, need to be kept secure and are proprietary to the hand-set, it contains drivers and logic to make the phone talk 3G, or 4G, whatever. The nuts is very hardware specific, it would use an RTOS.

The glory would be the user-interface, it could be any OS, it could use Java, Flash, be built by Apple, Google, Wind River, Microsoft, a hobbyist. What the glory needs is a well-defined API to talk to the nuts. Unlikely to be standardized as I mentioned above, but possible. The glory is the part that you could install as per Jason's story.

The important part is the separation, many mobile operating systems currently have nuts and glory combined into one (Android for example), but to make Jason's blog a reality, would require to split them.

Mobile is only one of the markets that can benefit from a story like the one Jason mentions. Generalizing the solution here, what we are really doing is enabling multi-OS on a single piece of hardware. That hardware can be multicore or single core.

The enabling technology for Multi-OS is virtualization through a hypervisor. A hypervisor allows one to run multiple different operating systems, strongly partitioned, fairly scheduled. It is a breakthrough technology for the embedded market and it enables new thinking.

To give another example in industrial control: Many industrial control devices currently consists of 2 separate boxes, talking together over ethernet to provide a single solution, one box handles real-time (RTOS) the other the UI (Windows, Linux). Ethernet is notoriously not real-time, but if your timing requirements are in the milliseconds, then Ethernet is ok.

Moving to a single multi-OS solution on a single chip (single- or multicore) would remove the need for ethernet and replace it with communication over shared memory. All of a sudden the latency for communication improves dramatically. It goes from milliseconds to microseconds and this drastically changes what this particular device could do, giving the manufacturer a strong leg up over the competition.

These types of examples exist for virtually every industry that uses embedded systems and I spend my days talking to customer explaining how they need to get on the virtualization band wagon or they will miss the next revolution in embedded systems.

The revolution is happening now, thanks Jason for your views on this and thanks for calling my video 'geeky', that was kind of the intent :)

It may not be the Wild West, but there are some similarities. I'm moderating (or is it refereeing) a discussion between two (opinionated?) personalities, Jim Turley and Clive "Max" Maxfield. The topic of the debate is embedded vs. discrete processors. The topic arises from a recent announcement by Actel, who built an FPGA around an ARM Cortex M3 core. Hence, is it better to embed or not to embed?

The panel will be held at the Embedded Systems Conference (ESC) in San Jose, April 27, at 4:30. Jim likes the discrete approach, while Max is more of an embedded guy. Shouldn't be any surprise there. But if you have an opinion in the matter, or just want to see these two guys go at each other (which promises to be a lot of fun), stop by and throw a question or two into the mix.

Max also offers his take on the panel as well as some other events happening at ESC.

When I first heard about Altium's NanoBoard 3000 development kit, I thought it would be far too involved for me, both in the kit's complexity as well as the time investment I'd have to make to really get to know the kit. But I was pleasantly surprised. I followed the simple direction to put the hardware together, then installed the software, and was on my way pretty quickly.

The kit has lots of different options, but the one I got has a pair of Xilinx Spartan FPGAs at its core (the main device is a Spartan-3AN). The other FPGAs the board could come with are an Altera Cyclone III or a Lattice ECP2. The kit also includes stereo speakers, a small touchscreen color LCD, a bunch of LEDs, an IR remote, and just about every kind of I/O that you could need.

I just went through some basic steps and I was able to program it to the point that I could get an image on the display, get the LEDs to light up, and get some sounds out of the speakers. I could easily see how you could take this kit pretty far down the road in terms of a prototype. Obviously it's way over-built, but you could get just about all your code written and deployed on this platform (assuming you're good with the hardware mix that Altium has assembled).

Altium has out a lot of time and effort into the kit to ensure a good (and simple) user experience. There's a lot of collateral on their web site, so you should be off and running pretty quickly. The complete kits costs around $400.

The first of many MCU announcements are upon us, from ARM with its M4 core. This one is a little different obviously as it's just a core and not a real microcontroller. But with the M0 and M3, and now the M4, ARM is going full bore after the MCU market. The margins for MCUs can be razor thin, but the potential number of units can be staggering.

Expect to see a bunch of MCU announcements next week as Embedded World opens in Nuremberg, then a bunch more as we get closer to the Embedded Systems Conference in late April. In general, and to the credit of the vendors, most of the new MCUs you'll see is specialized for a certain aspect, such as wireless capability, super low-power, higher performance, etc.

Stay tuned, as I'll be writing about the first batch next week from Nuremberg.