Switching to the Dockstar

I discovered the Seagate Dockstar, too late, when it was almost impossible to find one. I could put my hands on 4 of them, 3 of which were for friends. This device is tiny, uses the same CPU as the GuruPlug, can be powered from a single USB port with an easy mod, has free space to add a serial port, and is cheap. I always carry it with me everywhere and it's my network testing peer. It's much more convenient than the GuruPlug when a single ethernet port is required, and it can be powered by the GuruPlug's USB port when both are needed. Unfortunately it's impossible to find it now, and if you have one you don't use anymore, feel free to send it to me, I will be really pleased. Here are a few photos of the mods I made to a few devices.

Elastic Binary Trees - ebtree

Administrivia

This article was initially posted on Wikipedia in 2008, which explains why it's written at the 3rd person and looks familiar to articles on binary trees. A few moderators decided that the article was only self-promotion and removed it without notification a few days after its publication. After many arguments with them, I was told that Wikipedia cannot hold original work, only copies of what can be found somewhere else, and I gave up the fight, realizing that for once I found dumber than me! At least they accepted to let me retrieve the original work so that I can publish it somewhere else (I didn't even have a copy of it). Needless to say I have stopped donating to Wikipedia since then. Three years later, I spent part of a week-end putting this online here. When I have time, I'll rewrite it differently.

Introduction

In computer science, an elastic binary tree (or EB tree or EBtree) is a binary search tree specially optimized to very frequently store, retrieve and delete discrete integer or binary data without having to deal with memory allocation. It is particularly well suited for operating system schedulers where fast time-ordering and priority-ordering are strong requirements. Insertion and lookups are performed in O(log n) while removal is done in O(1). The tree is not balanced but its height is bound by the type of data to store in it. Ordered duplicate entries are also natively supported.

The elastic binary tree was invented between 2002 and 2007 by Willy Tarreau as part of a research work on an event-based task scheduler for user-space network applications. This type of components require a sorted list of future events, and insertion and removal are very common operations which must be optimized. An early implementation relied on a naive linked list approach, soon replaced with a fast radix tree. The disadvantages of the radix tree is that it is often necessary to allocate memory for one node to store a value, and that some garbage collection must be performed after removal in order to eliminate unused nodes. There are situations where this is not desirable nor even possible. An alternative was to use a balanced tree, but the very frequent removal operation costs O(log n).

The solution was to find some sort of hybrid type of tree between both, where each inserted entry would carry both an intermediate nodes and a leaf, both of which would stray from each other as the tree leaves, thus stretching the initial node across levels, hence the name "elastic binary tree".

License

The concept and algorithms have been released under public domain. The author's implementation was first released under GPL then switched to LGPL for more openness. The algorithm is simple enough to allow other implementations to be initiated for very specific needs.

Definitions

In an EB tree, data are stored in EB nodes. An EB node contains two parts :

• the node part, which is responsible for tying together upper and lower nodes or leaves ;
• the leaf part, which carries the data (an integer key), and keeps a pointer to its upper node (leaf_p).

The node part itself is composed of a parent pointer (node_p), a level (bit), and a root, which itself links to lower nodes constituting a subtree.

The level part represents the lowest bit position in the key, above which all bits are equal for all keys in the lower subtrees.

A root only contains two links called branches, which represent the value of the bit below current node's. There is always a left and a right branch, except for the top of the tree. Left branch represents bit value 0 while right branch reprensents value 1.

Branches are typed. This means that a node knows whether its branches point to other nodes or to leaves. Parent pointers are typed too. This means that each node or leaf knows if it is attached to the left or the right branches of the upper root.

A typical EB tree begins with a root at its head, containing 0 or 1 branch, below which the tree is complete. The right branch of an EB tree root is always empty.

Features

EB trees offer a wide range of useful data manipulation features :

• Lookup :
• lookup first or last key
• exact match: lookup exact key (signed/unsigned integer, poitner, string or memory block)
• longest match: lookup longest matching key (network address match)
• lookup first matching prefix: retrieve first entry matching the beginning of a key
• lookup closest smaller value
• lookup closest greater value
• lookup previous or next different value: quickly skip duplicates
• lookups of duplicate keys always performed in key insertion order
• Insertion :
• standard key insertion : if the key exists, create a duplicate entry
• unique key insertion : if the key exists, return the existing one

Complexity

EB trees algorithmic complexity can be derived from 3 variables :

• the number of possible different keys in the tree : P
• the number of entries in the tree : N
• the number of duplicates for one key : D

EB trees are deliberately not balanced. For this reason, the worst case may happen with a small tree (for instance, 32 distinct keys of one bit). But the operations required to manage such data are so much cheap that they make it worth using these trees even under such conditions. For instance, a balanced tree may require only 6 levels to store those 32 keys when an EB tree will require 32. But if per-level operations are 5 times cheaper, EB tree wins.
Minimal, Maximal and Average times are specified in number of operations. Minimal is given for best condition, maximal for worst condition, and the average is reported for a tree containing random keys. An operation generally consists in jumping from one node to another.
Complexity :

• lookup  : min=1, max=log(P), avg=log(N)
• insertion from root : min=1, max=log(P), avg=log(N)
• insertion of dups  : min=1, max=log(D), avg=log(D)/2 after lookup
• deletion  : min=1, max=1, avg=1
• prev/next  : min=1, max=log(P), avg=2 :

 N/2 nodes need 1 hop=> 1*N/2
 N/4 nodes need 2 hops => 2*N/4
 N/8 nodes need 3 hops => 3*N/8
 ...
 N/x nodes need log(x) hops => log2(x)*N/x
 Total cost for all N nodes : sum[i=1..N](log2(i)*N/i) = N*sum[i=1..N](log2(i)/i)
 Average cost across N nodes = total / N = sum[i=1..N](log2(i)/i) = 2

Current EB tree design is limited to only two branches per node. Most of the tree descent algorithm would be compatible with more branches (eg: 4, to cut the height in half), but this would probably require more complex operations and the deletion algorithm would be problematic.

Properties

EB trees have several useful properties :

• a node is always added above the leaf it is tied to, and never can get below nor in another branch. This implies that leaves directly attached to the root do not use their node part, which is indicated by a NULL value in node_p. This also enhances the cache efficiency when walking down the tree, because when the leaf is reached, its node part will already have been visited (unless it's the first leaf in the tree).

• pointers to lower nodes or leaves are stored in "branch" pointers. Only the root node may have a NULL in either branch, it is not possible for other branches. Since the nodes are attached to the left branch of the root, it is not possible to see a NULL left branch when walking up a tree. Thus, an empty tree is immediately identified by a NULL left branch at the root. Conversely, the one and only way to identify the root node is to check that it right branch is NULL. Note that the NULL pointer may have a few low-order bits set on some implementations.

• a node connected to its own leaf will have one and only one of its branches pointing to itself, and leaf_p pointing to itself.

• a node can never have node_p pointing to itself.

• a node is linked in a tree if and only if it has a non-null leaf_p.

• a node can never have both branches equal, except for the root which can have them both NULL.

• deletion only applies to leaves. When a leaf is deleted, its parent must be released too (unless it's the root), and its sibling must attach to the grand-parent, replacing the parent. Also, when a leaf is deleted, the node tied to this leaf will be removed and must be released too. If this node is different from the leaf's parent, the freshly released leaf's parent will be used to replace the node which must go. A released node will never be used anymore, so there's no point in tracking it.

• the bit index in a node indicates the bit position in the key which is represented by the branches. That means that a node with (bit == 0) is just above two leaves. Negative bit values are used to build a duplicate tree. The first node above two identical leaves gets (bit == -1). This value logarithmically decreases as the duplicate tree grows. During duplicate insertion, a node is inserted above the highest bit value (the lowest absolute value) in the tree during the right-sided walk. If bit -1 is not encountered (highest < -1), we insert above last leaf. Otherwise, we insert above the node with the highest value which was not equal to the one of its parent + 1.

• the "eb_next" primitive walks from left to right, which means from lower to higher keys. It returns duplicates in the order they were inserted. The "eb_first" primitive returns the left-most entry.

• the "eb_prev" primitive walks from right to left, which means from higher to lower keys. It returns duplicates in the opposite order they were inserted. The "eb_last" primitive returns the right-most entry.

• a tree which has 1 in the lower bit of its root's right branch is a tree with unique nodes. This means that when a node is inserted with a key which already exists will not be inserted, and the previous entry will be returned.

Principles of operations

Insertion

Initially, a tree is empty. It only consists in a root with two NULL pointers (one for each branch).

When the first EB node is inserted, its leaf is directly linked to the root 's left branch. Thus, its node part is not used. It is the only situation where a node part is not used. After that, a new EB node is inserted. A node part is needed between the root and existing leaf to connect the new leaf. This is where the node part provided with the new EB node will be used. The second EB node's node part will have one of its branch pointing to the previous leaf, and the other branch pointing to its own leaf. For this reason, it is not possible to have an empty branch below a node.

When the third EB node is added, it may very well insert itself between the node and the leaf of previous EB node, which will be stretched by the operation. It is important to note that the node part of a stretched EB node is always located somewhere between the root and the leaf of the same EB node. The same principle goes on with further keys, as shown on the diagrams below.

An EB tree with keys 1 to 5

Adding keys 21 to 25 to a previous tree. In Yellow, the links which changed.

Insertion of duplicates

An EB tree supports duplicates and keeps them ordered. This is a very important property for a fair scheduler because events stored with the same wake-up date must be processed in the same sequence to avoid risks of starvation.
In order to store a duplicate key, we grow a binary sub-tree at the place where the leaf was to be located, using the same algorithm as for the upper tree, but with negative bit offsets. This allows duplicates to be stored without overhead data, and to be walked through using the same functions, without any processing overhead. The nodes order is respected and all nodes will be walked in their insertion order.

Deletion

When a leaf is deleted, its parent must be released too (unless it's the root), and its sibling must attach to the grand-parent, replacing the parent. Also, when a leaf is deleted, the node tied to this leaf will be removed and must be released too. If this node is different from the leaf's parent, the freshly released leaf's parent will be used to replace the node which must go. EB trees do not need to be rebalanced after deletion. This results in tree deletion being performed in O(1). A released node will never be used anymore, so there's no point in tracking it.

In yellow, links affected by the removal of key 1 from previous EB tree.

In yellow, links affected by removal of keys 2 to 5 from previous tree.

Tree walk

A tree walk may be performed from left to right or right to left, always following numerical order and duplicates insertion order if applicable. It relies on the following primitives :

• eb_first(root): return the first node of the tree starting at [root]
• eb_last(root): return the last node of the tree starting at [root]
• eb_next(node): return next node after [node]
• eb_prev(node): return previous node before [node]

All of these functions return either a node or NULL when the end of tree is reached. Additionnally, two primitives are particularly useful to skip duplicates :

• eb_next_unique(node) : return the next node with a different key from current [node].
• eb_prev_unique(node) : return the previous node with a different key from current [node].

Implementation specifics

The only currently known implementation is the author's. It works on 32- and 64-bit platforms, either little or big endian. It uses the fact that pointer storage is 32-bit aligned at least, causing structure pointers to always have their two lowest bits cleared. This allows for pointer type to be stored in the pointer itself :

• a node pointer will be stored verbatim (with lowest bit cleared)
• a leaf pointer will be stored with lowest bit set (which equals pointer + 1)
• a parent pointer in a left branch will be stored verbatim (with lowest bit cleared)
• a parent pointer in a right branch will be stored with lowest bit set (which equals pointer + 1)

This is an important optimisation which reduces the number of memory dereferences and the memory structures sizes.
The right branch of the root must always be NULL. However, applying the same principle as above lets us put global flags in this location. Currently, the only used flag is EB_ROOT_UNIQUE, indicated by setting the lowest bit of the right branch pointer in the root. It indicates that duplicates are not desired and that when a key already exists during an insertion, nothing may be inserted and the existing node will be returned instead.
The current implementation is split between generic code and type-specific code. This makes it easier to later add support for newer types. Currently, pointers, signed/ unsigned 32/64 bit integers, strings and arbitrary memory blocks are supported.
Sixth version of the author's implementation brought support for prefix-based matching of memory blocks, which supports prefix insertion and longest match which are still compatible with the rest of the common features (walk, duplicates, delete, ...). This is typically used for network address matching or route selection. This update is not (yet) covered by this document.
Seventh version of the author's implementation brings support for a remappable variant of the ebtree called rebtree (rremappable elastic binary tree). This version is slightly slower but works on relative pointers, making it suitable for use in mapped files.
The current implementation distinguishes between eb_node which is type-agnostic and ebXX_nodewhich is a node of type XX. In practise, an eb_node has everything except the key itself. Only insertion and lookup need the key, all other operations only operate on the structure of the tree. This allows most primitives to be shared between type-specific implementations :

/* generic types */
typedef void eb_troot_t;

struct eb_root {
 eb_troot_t*b[EB_NODE_BRANCHES]; /* left and right branches */
};

struct eb_node {
 struct eb_root branches; /* branches, must be at the beginning */
 eb_troot_t*node_p; /* link node's parent */
 eb_troot_t*leaf_p; /* leaf node's parent */
 int bit; /* link's bit position. */
};

/* 32-bit specific types */
typedef unsigned int u32;

struct eb32_node {
 struct eb_node node; /* the tree node, must be at the beginning */
 u32 key;
};

The structures were designed to be located at the very beginning of any structure making use of EB trees. It is important for cache efficiency and memory access time that the EB tree data are located at the beginning of a CPU cache line, especially the 4 first pointers.

Performance considerations

The author uses EB trees in areas where red-black trees were burning too many CPU cycles. The haproxy load balancer has switched to EB trees and shows minor CPU usage at speeds up to 500000 insertions/removals per second, and a firewall log analyser relies on it to sort logs at speeds above one million lines per second. An insertion typically takes less than 100 nanoseconds on modern machines.
EB trees are much faster than conventional balanced trees when looking up strings or memory blocks because during the tree descent, only the bits specific to the new node are compared, while in a balanced tree, the string compare has to be performed on the whole string for each step. This advantage is emphasized in the halog log analyser which is able to process more than 4 million lines per second while indexing URLs.
The ability to lookup prefixes has made EB trees able to perform an operation which previously was possible only in radix trees but not in binary trees. Having the ability to use the same tree for various purposes can sensibly reduce complexity in some implementations, and reduce the number of operations (eg: network routing and filtering). Tests have shown that network lookups within a BGP table containing 450000 routes could be performed several million times a second on a modern machine.
However, a tree node is typically 20-bytes long on a 32-bit system. On systems with very small caches or low memory bandwidth, EB trees can be slower than red-black trees if insertions/removals are not much frequent and do not compensate for the increased bandwidth usage. Also, red-black trees rely on the ability to compare values, which make them suitable for many data types. Conversely, EB trees heavily rely on bit-addressable data (typically integers), which confer them a very high performance due to the cheap operations involved, but limit their application field. Trying to use EB trees to store non-bit-adressable data would completely defeat their purpose and will likely provide poor performance.

Practical uses

The HAProxy load balancer uses EB trees for the following features :

• timers: timers are stored ordered, which ensures that checks for timeouts are always performed in O(1).
• scheduler: the scheduler maintains the list of runnable tasks by weighting their wake-up order with their nice value. EB trees make this operation very cheap, typically O(Log(N)), allowing priorities to be used with huge amounts of tasks without any noticeable cost.
• ACL: string and IP address matches rely on EB trees so that even very large pattern file do not cause any noticeable slowdown (eg: full internet BGP routing table).
• stick-tables: data learned from traffic (cookies, SSL ID, headers, URLs, ...) are stored and retrieved using EB trees
• The multi-peer sync protocol uses the ability to lookup ranges in EB trees.

The halog log analyser provided with HAProxy uses EB trees to sort counters, stats, URLs and servers.
The Scalable TLS Unwrapping Daemon (stud) uses EB trees for its shared session cache.
At least one proprietary log analysis solution makes extensive use of the remappable version of the EB trees for fast log indexing and lookup.
At least one thread-safe variant is known to exist, though very little is known about it at this time.

See also

• Binary tree
• Binary search tree
• Radix tree
• Red-black tree
• Compact Elastic Binary Trees (cebtree): only two pointers per node!
  

External links

• EB tree reference implementation
• The HAProxy load balancer
• The Scalable TLS Unwrapping Daemon (stud)

GuruPlug Server Plus : don't waste your money on it!

Introduction

Guruplug Server and Guruplug Server Plus are small computers that fit into a power plug and which are made by GlobalScale. I was first informed about them from someone who asked on the haproxy mailing list if haproxy had ever been tested on them. These devices run on a Marvell 88F6281 processor, which is a system-on-chip (SoC) powered by an ARM-derived Sheeva processor core at 1.2 GHz, coming with 512 MB of RAM and as much of flash. The Server Plus also has 2 Gigabit Ethernet ports, and the whole is supposed to consume just a few watts, so I found it very appealing for building high performance, low consumption haproxy servers.
I pre-ordered one at NewIT about two months ago and it finally arrived on Friday. The packaging was clean and the device looked compact and solid. A free JTAG+console adapter board was also provided, which is absolutely required to be able to connect to the serial port. The box also contains a european plug, as well as power and Ethernet cables. The devices come pre-installed with a debian system so that it's not needed to install anything to test it.

First connection

I plugged my Guruplug on my network and observed my DHCP server's logs in order to find the address I should connect to (no doc is shipped with the device, everything has to be downloaded from the net or guessed). Well, the dhcp client looked a bit buggy, it was sending DHCP_DISCOVER packets forever, ignoring the DHCP_OFFER it got in response to all of its packets. So I couldn't connect to the device over the network. I had to use the serial console.
Trying to connect using the serial console was another adventure. The JTAG adapter was detected by the usbserial driver, but all I got were endless "1". I finally found that I had to build and load the ftdi_siodriver too to use the JTAG adapter. Nice, I can now connect via minicom, using login root and password nosoup4u. I manually killed dhclient3 and restarted it by hand without all the strange arguments on its command line and this time it worked. I did not spend more time investigating this, probably that some of these args passed via the init script are not very functional.

First network test

Being interested in running haproxy on it, I had to run a benchmark. I installed the haproxy-1.4.4 package which was already packaged for this distro, because it was faster than building a cross-compiler on my machine. I started it with a simple test configuration which only forwards traffic to a single server without logging nor playing with headers or cookies. This is the configuration with which I push my ALIX to 2700 hits/s, and a Celeron 1.3 GHz to about 11000 hits/s. Being running at 1.2 GHz with some DDR2 memory, I expected to see something between 8000 and 10000 hits/s. I carefully unloaded iptables and fired the test. What a disappointment : 2200 hits/s at 100% CPU ! Even 20% less than my ALIX running at 500 MHz on DDR-400 and 100 Mbps ports ! I tried changing some TCP optimisations in the configuration but I could only hardly reach 2400 hits/s with a config in which my ALIX reaches 3000. Still 20% less.
Then I decided to run a bit rate test which should favor this CPU which integrates the network controllers. Instead of fetching empty objects, I fetch large ones (10 MB). Result : only 310 Mbps at 100% CPU where the ALIX gives 200 Mbps with some CPU margin (two 100 Mbps ports), and the Celeron slightly more than 800. Quite obviously this CPU is a donkey !

Test on other kernels

I finally decided to give this box a second chance by booting another distro's kernel on it, just in case we'd have a problem with debian's 2.6.32. Fedora and Slackware have pre-built kernels and images that should be able to run there. Following the Slackware's howto hangs at boot. The howto also says that some plugs were shipped with a buggy bootloader which hangs during USB detection. Mine does and is 6 months old. A new bootloader is available on plugcomputer.org so I carefully updated it, hoping not to brick the box. That was successful, I could boot the Slackware and run my test with the same haproxy binary.It was slightly faster, 2250 hits/s and 320 Mbps, but still far from what I'd expect.
After a reboot, I discovered that the debian kernel shipped from factory does not boot anymore after the bootloader has been upgraded. There is a platform identifier which is different between what is documented as being a Guruplug (0x0A63) and what was installed in this beast (0x0A29). I was starting to get a bit fed up with the low level of platform preparation at GlobalScale, so I unplugged the thing.

Massive heat dissipation

While unplugging wires, I burnt my fingers on the RJ45 plug! The metal was at something like 70 or 80 degrees celsius, I don't know. It was simply untouchable, even after a long idle period. The Geode in my ALIX runs under less than 1W at full load and around 0.1W when in idle. It does not even have a heatsink. Many people have reported major heating issues on these Guruplugs in the past, with power supplies dying after less than 3 months, but GlobalScale said they had replaced the PSUs in recent units. Check here for photos taken with a thermal camera and reporting more than 72 degrees C on external parts.

So I decided to open the unit to see how it was inside. There were two signs that the power supply got replaced. The first one is that the "Warranty void" seal was a new one stuck over the previous one, whose remains were pinched in the plastic. So this box was reopened, closed and had a new stick on it.






The second sign is that two plastic legs in it were cut to accomodate the new, larger power supply. Click on the images on the right to get a full sized view.






I ran the tests again with the box open. This power supply does not heat at all. It's only the CPU which heats like mad. The small aluminum plate it completely untouchable, it really hurts to touch it even half a second. And the power supply is located just on top of that plate. So now I realized that it was not the power supply that was killing the Guruplugs, but the CPU which is cooking the power supplies. I can't leave that running when I'm not at home, I would fear that it puts my flat into fire !

Poor design

Considering the amount of heat emitted by this Marvell CPU, the box would have needed a large heatsink. I don't think anybody would have complained if the box had been 1.5cm thicker to accept a normal heatsink, with aeration holes on the sides so that the heat dissipates. Instead we have dangerous plugs which are too hot to touch, and which die in a few months of idling because capacitors can't stand sustained heat.
Also, the internal wiring is of poor quality. Two of the power output wires broke while I was taking photos of them, and a third one is about to break too. The mains input wires are similarly bad and risk to break too. And it looks like the PSU was modded by adding resistors to it, maybe to slightly increase output power. This PSU features a 105 degree capacitor though, so it may last slightly longer than previous ones.

Close-up of the 5V connector Inscriptions at the bottom The PSU in the bottom block Bottom with battery, SD connector, Blutooth controller and WiFi Connectors side Left side with UART and JTAG connectors Right side with reset button and Micro-SD Motherboard at the top PSU cover removed PSU removed The 105°C capacitor The PSU was partched The PSU First 5V wire broke instantly Second 5V wire followed Next one will be the ground wire Mains wire about to break

Conclusion

The Guruplug was announced by some sites as the NSLU2 killer, but for me it's just right now a Slow Heater, and by no way will it replace even one NSLU2 as long as it heats like that. It's slower than my old ALIX, and heats a lot more. I think that one of the reasons for it to be so slow despite the high frequency is the RAM bus width : at first I thought it would be a fast system because it runs on DDR2-800, but when you see that it's only a 16-bit bus, it is equivalent to only 200 MHz for a 64-bit bus, but with higher latencies due to DDR2. My ALIX's Geode LX processor runs on a 64-bit, 400 MHz bus, so it has twice the memory bandwidth the Guruplug has. Marvell also has another CPU in the family (MV78200) with a 64-bit RAM bus, which should be better, but I have not seen it anywhere yet. The fact that the Marvell CPU consumes 5 times more power than the Geode LX and is slower is also an indication of something wrong with the design. Apparently this CPU makes it way into entry-level NAS appliances. It's probably one of the applications where the heat issues and limited memory bandwidth will not be too much of a concern. I'm really disappointed, I would have expected it either to replace my old NSLU2 (but it heats too much) or to become sort of an ALIX upgrade with Gigabit ports, but now I think that if I need Gigabit, I'll turn to these dual-gigabit mini-PCI cards. They will give me about the same level of performance without having an overheating CPU.

I don't even think I will waste my time trying to repair and adapt that Guruplug, it will probably spend the next 10 years lying in a box with other dead boards, waiting for my solering iron to pick some components out of it. However, I think that if/when the manufacturer finally decides to do a complete redesign of the product (ie include a BIG heatsink and leave some holes for airflow), then it may be an acceptable replacement for the NSLU2.

External links

• https://wtarreau.blogspot.com/2013/02/mirabox-much-better-than-guruplug.html : Better than the GuruPlug, see the Mirabox.
• http://plugcomputer.org/plugforum/index.php?topic=1735.msg10695#msg10695 : photos taken with a thermal camera showing external parts above 72 degrees C
• http://blog.tensin.org/index.php?post/2010/10/02/Guru-Plug-Server-Plus-%3A-bonne-petite-machine%2C-mais-trop-bruyante : the new version has a very noisy fan to get rid of the heat (check the video on the site). I received two complaints the same day from two new victims of this ongoing scam from GlobalScale.
• http://plugcomputer.org/plugforum/index.php?topic=2295.msg12908#msg12908 : photos of their new failuremodel with the internal fan, 80% obturated by the USB plugs !
• http://www.globalscaletechnologies.com/c-4-guruplugs.aspx : the manufacturer's page for this room heater.
• http://www.marvell.com/products/processors/embedded/kirkwood/ : the Marvell 88F6281 processor.
• http://pcengines.ch/alix.htm : the ALIX motherboards at PC Engines.

How to add a capacitor to keep RTC running on PC Engines ALIX

Introduction

ALIX is the name of a nice motherboard family designed by PC Engines to build small fanless, quiet, cheap and still powerful servers. Those motherboards are sold without battery for the RTC clock, so as soon as the power is lost, the clock is lost and at next boot, the clock will be set to Jan 1st 2000.
When working on packaging a Linux distribution for these motherboards, it is normal to encounter various boot errors and to have to power cycle the board tens of times a day. After a while, having to set the clock manually becomes irritating, and at least being able to keep it running for a few minutes would be very useful.

Solution

Since the RTC clock is known to run from very low power, I decided to experiment with a few capacitors with pretty interesting results. A 1000µF charged at 3V3 and connected to the 3V battery input is able to keep the clock running for about 30 minutes. This is more than enough for most of the power cycles I have to run through.
This capacitor will have to be charged during operation. Since the power supply does not charge the battery, a diode will have to be connected between the 3V3 power line and the capacitor. Unfortunately, a silicon diode shows an important voltage drop (0V6) which considerably reduces the efficiency of the solution.
Experiments with a germanium diode with a lower drop (0V3) connected to the 3V3 power line charges the capacitor to 3V. Another test with a silicon diode connected to the 5V power line charges the capacitor to 4V4, providing slightly increase longevity.
I finally decided that both of my 2C3 motherboards used as servers will have a 1000µF capacitor charged at 3V through a Ge diode, to power the clock for about 30 minutes. The 3C2 board which I carry everywhere with me for development and experimentation purposes will have a bigger 0.1F capacitor charged at 4V4, managing to keep the clock running for two days.

Installation on the 2C3 motherboard

Locate the power lines

 On the 2C3 motherboard, it is very easy to locate the power lines. The 3V3 is available on C172, very close to the battery connector, and a small capacitor already brings the ground even closer, basically at the distance of a capacitor, so this will be quite helpful. Click on the image on the right to get a full size view.

Identify the connection points

Here is a close-up of the work area enlightened above. The view has been rotated for easier identification. The components will be connected as indicated on the image. Click on the image to get a full size view. First, prepare the terminals with some solder. Put a drop of solder on the pin of C172 facing U12, as the diode will be connected there. Do the same on the "-" pin of C26, which is also facing U12 ; the capacitor will be connected there.

Prepare the components

Prepare a Germanium (or Schottky) diode as indicated on the image (click for a closer view). The pins must be bent several times for the diode to pass over U12 and provide a connection for the capacitor.

Then, get a 1000µF 6V3 radial capacitor, cut its pins to 8mm, and bend the positive terminal perpendicularly for horizontal soldering (not shown on the image).

Install the diode

Solder the diode first. Its anode connects to C172, on the pin facing U12, and the cathode connects to the battery's connector, in the hole designated as BT1+ (in fact it's the + terminal of battery BT1). It is important to leave the cathode exposed (not isolated), because the positive pin of the capacitor will be soldered directly on it.

Install the capacitor

Solder the negative pin of the capacitor to the negative pin of C26. Orientate it so that the positive pin joins the diode's cathode on BT1+.

Installation on the 3C2 motherboard

Install the diode

Here on this photo, the +5V is taken from the left pin of C23. The diode is not easily identifiable, it is the small black plastic thing located just above the R20 printing. Its anode is connected to the +5V via the yellow wire, and its cathode is connected to the BT1+ pin on the board.

Install the capacitor

The capacitor is what is sometimes called a "SuperCap". Its capacity is 0.1F, or 100000µF, which is 100 times the capacity of the ones used on the 2C3 motherboards. It is slightly bigger and there was no easy place to install it. I finally decided to stick it on top of the CS5536 (U11) which is approximately the same size and is perfectly flat.


Another advantage of this location is that the power line from the BT1+pin enters the CS5536 via the C38 capacitor, which provides an easy access to both the positive and negative terminals. Also, it is important to note that BT1+ is not directly connected to C38, but passes through R20 first, a 47 ohm resistor.

In the end, it is a good thing that there is a small resistor between the power supply and this capacitor. It has a very big capacity and a small internal resistance, and having R20in the path ensures that it does not pull too much power through the diode at start-up.

Connect the capacitor to C38 as on the image on the right, with the negative pin to the left ot C38 and the positive pin on the right. That's all, you're done.

Various links

• http://pcengines.ch/ : PC Engines's web site.
• http://pcengines.ch/alix.htm : the ALIX motherboards at PC Engines.
• http://www.st.com/stonline/products/literature/an/5226.htm : an interesting application note for SuperCaps and time-keeping I found while writing this article.

How to build a cheap UPS for PC Engines ALIX

Introduction

ALIX is the name of a nice motherboard family designed by PC Engines to build small fanless, quiet, cheap and still powerful servers. Those motherboards drain so little power that they can be powered by a simple 9V battery ! Typical power usage sits around 3W for a 500 MHz processor.

I recently experienced a power outage which made me realize that not having a battery backup for such servers is a shame, given how easy it is to power them. I experienced a bit with complex circuits involving MOSFETs and transistors in order to achieve the lowest power drop but finally went back to a very simple 3-component design.

Schematics

Circuit diagram

The principle is very simple. The ALIX power supply delivers 18V to the motherboard. In parallel, a 9V rechargeable battery (B1) is installed in series with a current-limiting resistor (R1). The charging current is defined as the the difference between the power supply's voltage and the battery's voltage, divided by the resistor. I chose 1k5 for R1, which sets the charging current to (18-9)/1500 = 6mA.

A Zener diode installed in parallel with the battery prevents it from over-charging, by draining all the charging current when the battery is fully charged. The diode's voltage must equal the battery's full charge voltage. 9V NiCd battery packs are not 9V in reality, but 8V4 assembled from 7 1V2 batteries. Since they reach 9V6 when fully charged, I used the same value for the diode. The diode may heat a little bit depending on the charging current and the voltage. The power dissipated by the diode equals the difference between the power supply's voltage and the diode's multiplied by the current, which is (18-9.6)²/1500 = 47mW. A small 100mW diode is enough.
A low voltage drop Schottky diode is installed in the discharge path between the battery and the power line so that nearly all of the battery power goes to the motherboard during power outages. The diode has to support at least 1A of continuous current depending on how the motherboard will operate. Also, since the motherboard is equipped with a switching voltage regulator, it will drain a higher current when the battery is low. The diode I used only shows a drop of 0V2, which is quite acceptable.

Test results

My first tests show that the cheapest 120mAh battery maintains the motherboard online for about 10 minutes until the voltage drops to 7V. It requires about 24 hours for a complete charge with the 1k5 resistor. The charging rate may be increased to 10mA with a 820 ohms resistor, but above, a bigger Zener diode will be required.
I also noticed that my SpeedTouch ADSL modem uses a 9V input... I tried the same module on it. Bingo! it worked too. This means that with a few of those modules, I can maintain my network access up during short power outages.

Possible improvements

The 8V4 nominal voltage of this battery pack is very close to the low voltage limit of the motherboard (7V). This leaves a very small work margin. Other battery packs from 9V6 to 12V may be more interesting to experiment with. However, they will require a bigger Zener diode and will probably cost much more.
An interesting enhancement consists in daisy-chaining as many of such modules as there are motherboards to power. This will ensure that all power supplies are able to backup any one which would fail, and it will also optimize the offline duration of the batteries in the even that some batteries are less sollicited. In this case, it would also make sense to use a bigger battery such as a 12V/7Ah as commonly found in medium-sized UPS. Such a battery could power an ALIX motherboard for a full day!

Approximative cost

I got this 9V battery for 1 Euro, but they are generally sold around 5 Euros. There are between 1 and 2 Euros of components, including the male and female jacks. A small plastic box and a PCB to hold the battery and the connectors would be a nice improvement. What would be very nice would be if PC Engines could sell such a module as an option, just as they do with the PoE injector.

Various links

• http://pcengines.ch/ : PC Engines's web site.
• http://pcengines.ch/alix.htm : the ALIX motherboards at PC Engines.