tag:blogger.com,1999:blog-91841450655286101992024-02-20T03:43:31.083+01:00Mr Footuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-9184145065528610199.post-66797950767929311792017-05-20T15:40:00.002+02:002017-05-20T15:42:54.961+02:00Mecrisp Stellaris on Maple Mini cloneBlimey. Been a while since I posted anything, and I'm mainly posting this as a reminder to myself. <br />
<br />
Setting up Maple Mini clones (Baite logo) to run mecrisp-stellaris.<br />
<br />
Binary from https://github.com/jeelabs/embello/tree/master/explore/1608-forth/suf<br />
<br />
The built-in maple bootloader and dfu-util are mostly sufficient and easy to use for uploading stuff to the maple mini, but are <i>not</i> sufficient for uploading mecrisp. Mecrisp needs to load at 0x0, and thus kills the maple bootloader. You need stm32loader.py or similar, and upload using the ST bootloader built into the chip itself.<br />
<br />
Setup :<br />
<br />
- 3.3v serial port connected to rx1/tx1 (and, in my case, powering the board via vcc and gnd).<br />
- jumper from boot1 to gnd<br />
- hold the user button down, and power up.<br />
- keep the user button held down, I think. I did, anyway, but you may not need to.<br />
<br />
You can now use stm32loader.py as follows<br />
<br />
stm32loader.py -p <serial-port-here> -e -w -v -a 0x08000000 usb-maplemini.bin<br />
<br />
And that will get you mecrisp stellaris installed on the maple mini<i> communicating over the usb port</i>. That's pretty fucking nifty, right there. tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-57557424610783517922014-07-05T22:02:00.001+02:002014-07-05T22:02:49.008+02:00Osprey backpacks<br />
<div style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em; text-align: left;">
</div>
<br />
<span style="font-family: Trebuchet MS, sans-serif;">Well, here's a thing. More of a rant, actually.</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">As some of you may know, I live in the French Alps, and work as a chairlift driver. When I'm not working, coding, or playing ice hockey, I can often be found trekking up and down mountains. Backpacks, and particularly <i>technical</i> backpacks, are a pretty large part of my life. I've got a good few of them, and use them almost daily.</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">So, anyway, my old 30L pack has died. My last trip involved 3 days with the damned thing held together with bits of string. Not fun, especially as it was mostly raining, so my stuff was getting wet. Time to replace. List of requirements:</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<br />
<ul>
<li><span style="font-family: 'Trebuchet MS', sans-serif;">30L ±</span></li>
<li><span style="font-family: 'Trebuchet MS', sans-serif;">Ventilated back (gets hot around here in the summer)</span></li>
<li><span style="font-family: 'Trebuchet MS', sans-serif;">Integrated rain cover</span></li>
<li><span style="font-family: 'Trebuchet MS', sans-serif;">Hydration system</span></li>
</ul>
<br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">Now, I'm a fan of Osprey packs, and have been since I bought a "Variant" 52 litre pack. Well designed, comfortable, and built to last. So the first place I started looking was Osprey. I ended up looking seriously at Osprey's "Manta 28" pack, which had pretty much everything I wanted, a few things I hadn't thought of, and one thing I didn't really want but could live with (it's a framed pack). It's sold as a "hydraulics" hydration pack. All the reviews mention the included 3 litre hydration sleeve as being one of the best on the market. The goddamned Osprey website mentions its "Internal Hydration Sleeve". So, when I ordered one (not direct from Osprey, but through an Amazon seller, tight-ass that i am) for 85 euros, I was expecting to find a hydration sleeve in the pack or its packaging.</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">I was disappointed.</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">"Hrm", I thought. "The seller must have forgotten it. Or maybe 'forgotten' it". So I contacted them. </span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">"Osprey don't include the hydration sleeve in Europe. We can sell you one for 35 euros plus shipping"</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">What the <i>fuck</i>? Osprey's official Eurozone price of 100 euros is very close to the US-market price. Nothing on the Osprey europe site indicates that the hydration sleeve isn't included. "Maybe I've misread", I thought, and went off to compare between osprey-europe.com and ospreypacks.com. Problem - ospreypacks.com redirects to osprey-europe.com immediately. In order to hit ospreypacks.com without a redirect, I eventually had to use a US-based proxy.</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<span style="font-family: Trebuchet MS, sans-serif;">Keep that in mind. A european client <i>cannot</i> hit ospreypacks.com without taking specific and non-obvious technical steps to do so. Which is a shame, because on the ospreypacks.com page for the Manta 28, we find the following, in bold italic text :</span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span>
<em style="background-color: white; color: #4d4d4f; line-height: 18px;"><strong><span style="font-family: Trebuchet MS, sans-serif;">Reservoir sold separately in European and Asian markets</span></strong></em><br />
<em style="background-color: white; color: #4d4d4f; line-height: 18px;"><strong><span style="font-family: Trebuchet MS, sans-serif;"><br /></span></strong></em>
<span style="color: #4d4d4f; font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; line-height: 18px;">Yep. The one thing a customer from Europe might want to know, before ordering, about this pack, is not available to them. A bit more "spot the difference" gives us the following 2 images from ospreypacks.com on the left, and from ospreyeurope.com on the right. Can you see the difference? </span></span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;"><img border="0" src="http://www.ospreypacks.com/images_products/352_865_lg.jpg" height="320" width="212" /><a href="http://www.ospreyeurope.com/media/catalog/product/cache/3/image/9df78eab33525d08d6e5fb8d27136e95/m/a/manta-28-tahoe-blue-web-new_1.jpg" imageanchor="1" style="clear: right; display: inline !important; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://www.ospreyeurope.com/media/catalog/product/cache/3/image/9df78eab33525d08d6e5fb8d27136e95/m/a/manta-28-tahoe-blue-web-new_1.jpg" height="320" width="212" /></a></span><br />
<br />
<span style="font-family: Trebuchet MS, sans-serif;">That's right. The ospreyeurope.com version has had the visible bit of hydration tube photoshopped out. Well, nearly all of it, anyway - there's still a bit visible on the right shoulder strap. Beyond that, and the fact that the euro site doesn't explicitly say "Hydration system" as opposed to "internal hydration sleeve", which latter apparently means the place in the pack where you'd put an - ahem - hydration sleeve, there's bugger all difference.</span></div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span><span style="font-family: Trebuchet MS, sans-serif;">So I've got a new pack (and, if I might say so, a bloody good one), but I'm feeling ripped off. Because my "Hydraulics" "hydration pack" has a 75cl bottle of water in each side pocket, rather than the 3l hydration pack I was supposed to have.</span></div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;">Adding in the supposedly supplied 3l sleeve is going to cost me half what I paid for the pack itself, and bring the price up to twice that of a more or less equivalent pack with a separately bought sleeve.</span></div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div style="text-align: left;">
<span style="font-family: Trebuchet MS, sans-serif;">So FUCK YOU, Osprey. You've lost a client. Yeah, I know. First world problems. Call a whaaaambulance. But fuck you anyway.</span></div>
tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com1tag:blogger.com,1999:blog-9184145065528610199.post-3583393626275183832014-04-19T15:20:00.001+02:002014-04-19T15:20:39.038+02:00What the *fuck* are Microsoft smoking?So, seeing as I'm blogging again, here's a bit of a rant.<br />
<div>
<br /></div>
<div>
Boy #1, who is now 14, decided that his computer, which had been happily running some form of Ubuntu, wasn't up to scratch. Specifically, that he couldn't get in on the F2P revolution - his friends had moved on from Minecraft to League of Legends. As such, he *needed* Windows.</div>
<div>
<br /></div>
<div>
"Okay", say I. I have a valid license for Win7 Pro that I don't use (came with my new laptop, which is *ahem* hackintoshed *ahem*), you can use that. But beyond doing the install and owning the administrator password, as they say around here, "demerdez-vous". I deal with Macs and unix boxes, I know nothing much about Windows apart from "when I have to use it, I don't like it". In short, I'm willing to set him up a machine, and occasionally bung in the administrator password, but it it gets pwnt, or stops working, or generally starts buggering about, the response is going to be "Reinstall. From scratch."</div>
<div>
<br /></div>
<div>
Now, as he's 14, computer time is restricted. With Ubuntu, I'd installed timekpr, which is an impressively flexible tool for managing computer time usage.</div>
<div>
<br /></div>
<div>
Windows 7 comes with "parental controls", which purport to do something similar. Well, on the surface, it looks like they do, anyway. Once you've scratched the surface, it becomes patently clear that Microsoft's parental controls are seriously lacking.</div>
<div>
<br /></div>
<div>
Time usage controls come down to "user x can use the computer between hour y and hour z".</div>
<div>
<br /></div>
<div>
That's it. Nothing more. Want to allow your kid to use the computer between 10am and midday, and from 6 to 8 pm, with a maximum screen time of 2 hours? No, can't do that. Even better is Microsoft's response to its customers. It's "brillant", for those who remember The Daily WTF :</div>
<div>
<br /></div>
<blockquote class="tr_bq">
<span style="background-color: white; color: #333333; font-family: 'Segoe UI', Arial, sans-serif; font-size: 13px;">Only administrators can set the parental control and not the standard user. So if you wnat to set the time frame of 3 hours per day usage, you will have to ask the user first as to when they want to use the computer and set it under parental controls.</span></blockquote>
<div>
<br /></div>
<div>
http://answers.microsoft.com/en-us/windows/forum/windows_vista-security/parental-control-time-limit-question/98543dfa-783b-4ae8-b464-c274bce895ec</div>
<div>
<br /></div>
<div>
This shows a(nother) complete misunderstanding of what people might actually want to do with their computers.</div>
<div>
<br /></div>
<div>
So, anyway, parental controls are out. They suck, and MS don't seem to understand why, or care enough about their clients to try and improve them. Which leaves 3rd party solutions.</div>
<div>
<br /></div>
<div>
The only one I've found which doesn't suck (indeed, it's better than timekpr, which I considered to be pretty damned good) is timeboss, from http://nicekit.com</div>
<div>
<br /></div>
<div>
Time limits, times when you can't use the computer at all, forced breaks, it's got everything you need to properly restrict usage.</div>
<div>
<br /></div>
<div>
The *only* downside to it is that, even allowing for the massive flexibility it provides, the UI is over-confusing and cluttered.</div>
<div>
<br /></div>
<div>
It's an enormously powerful piece of software, reasonably priced for the peace of mind it provides (although it should be said that no piece of software can replace proper parental oversight); Microsoft would do well to ask themselves why companies like nicekit are making money providing something that should be standard.</div>
<div>
<br /></div>
<div>
Still, if you're a parent who, like most of the world, is tied to Windows, it's definitely software to have.</div>
tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-36707564542817947262014-04-18T13:04:00.001+02:002014-04-19T19:43:59.969+02:00Intuos tablet resurrection - the story, and the gory bits.So, I'm going to tell you a story. Are you sitting comfortably? Then I'll begin...<br />
<br />
A long time ago, in a land far, far away (well, in the year 1999 or so, and on holiday in Paris), I bought myself a Wacom tablet. An ADB Wacom tablet to go with the Mac IIfx I was using at the time. Or it might have been the G3 desktop, thinking about it. Whatever, it was a ripsnortin' fast Mac with several screens attached and an ADB connector. The tablet was, as I recall, a UD-0608-A, and I bought it on sale from "Surcouf". And I was mightily happy with it.<br />
<br />
That tablet stayed with me for 14 years, but its utility was massively reduced by Wacom "Steving" it when Apple moved to MacOS X. In fact, it was turned into a tablet-shaped paperweight. <br />
<br />
At that time, I, amongst many other Wacom users, contacted Wacom to ask if we could please get an OSX driver. Could we hell. "OSX can't handle the throughput on ADB", they said. "It's Apple's fault", they said. "Buy a USB tablet, ya cheap bastard", they said. <br />
<br />
At the same time, I was running Linux/PPC on my Wallstreet, so I contacted Wacom's developer people, asking if I could get the technical details on how the ADB tablets worked, in order to write a linux driver. Dave Fleck, who was (I believe) responsible for writing much of the Classic Mac code for the ADB tablets, got back to me and explained that:<br />
<br />
1 - Can't do that, souper-sekrit eye-pee.<br />
2 - You'll never understand how it works<br />
3 - "XXX can't handle the throughput on ADB"<br />
4 - Buy a USB tablet, ya cheap bastard<br />
<br />
... and that was that for a good few years. The trusty ultrapad went back into its box, and gathered dust.<br />
<br />
Around 2004/2005, I randomly came across a tool for dumping ADB traffic, using 2 classic macs, a butchered serial cable, and some resistors. Can't remember what I was looking for at the time, but there it was. The tool I needed to be able to dump ADB traffic to and from the tablet. I got inspired, and got dumping, 50 packets at a time (if I remember the limits of the tool). A horrible job, and with no way of actually saving the dump, got writer's cramp. The result of this, however, was a pretty good understanding of how the UD-xxxx-A series talked. There was nothing "difficult" about it; it was, in fact, pretty much trivial. So I wrote an OSX 10.2.x driver for it, and it worked. The first work that cme out of this was an image saying "fuck you wacom!". Yes, very mature.<br />
<br />
10.3 arrived, and buggered things up. No longer were ADB-equipped Macs supported.<br />
<br />
So I wrote, with a fair amount of help, a driver for the iMate ADB converter, which also included a tablet driver (which then got expanded by others to cover not only the ultrapads, but also the Calcomp slates).<br />
<br />
It got hammered by, successively, 10.4, 10.5 (which removed ADB entirely), 10.6, etc etc.<br />
<br />
The tablet went back into its box.<br />
<br />
Bernard contacted me, sometime 2009/2010. He took my code, with my blessing, and turned it into a part of Waxbee. I rejoiced, got a couple of teensys, and hooked up my ultrapad.<br />
<br />
Then Bernard started asking questions about the intuos tablets. They were not the same as the ultrapads. They were - wierd. Random. My interest was piqued. So I bought one. Cheap as chips, obviously, as they no longer fucking work with /anything/. I looked at the packet stream, and cried. And put the tablet away again.<br />
<br />
Every now and then, I'd pull it out, have a poke, and get discouraged.<br />
<br />
Then I had a revelation. I started dumping packets in binary, rather than hex, and started seeing patterns. The veil started to lift, ever so slightly.<br />
<br />
At this point, Bernard and I knew what happened when you plugged an intuos tablet in (the identification packet was pretty similar to the ultrapad one), and what happened when a pen came into proximity (a pair of messages, the forst of which was obviously tool-specific, and the second of which, again, looked similar-ish to the UD series). But the rest was gibberish. A constant stream of 3, 6, or 8 bytes at a time, regardless of pen movement, and seemingly random, followed by 2 bytes 0xfe00 as an obvious out-of-proximity marker.<br />
<br />
That stream of bytes, however, started to make some sense when dumped in binary. Move the pen up, and one bit was always set. Down, and the same bit was always clear. Left, another bit set. Right, clear. Odd, but more or less consistent sets of 4 bits inbetween. Lean left, another bit. Lean up, another one. Press a button, an 8 byte packet happens. Release it, another one happens. And so on.<br />
<br />
It became clear to me that Wacom were somehow crushing down location data into 5 bit chunks, tilt into 4, probably pressure into another 4. the encoding was opaque, but the meaning was clear.<br />
<br />
I forced myself to do something with it, mainly by giving my trusty ultrapad, which was now working under Bernard's waxbee code, to a colleague, leaving myself with only the non-working intuos. I had 2 choices. Fix it, or live without a tablet.<br />
<br />
So, I had this stream of data, and I thought I knew what some of it meant. I got quite excited about that, and contacted Bernard. We ummed and arred over what the 3 byte and 6 byte packets were all about.<br />
<br />
What was obvious was this: Per 3 bytes, regardless of whether it was a 3 byte or a 6 byte packet, data looked like this ...<br />
<pre>00xx xxxy yyyy pppp hhhh vvvv
</pre>
... where x, y, p, h and v are related to x delta, y delta, pressure delta, horizontal tilt delta and vertical tilt delta.<br />
<br />
But what were the 6 byte packets? And what of the occasional 8-byte packets that weren't triggered by button state changes? Bernard was of the opinion that the 6 byte packets were simply 2x3 byte packets munged together. I thought they were, more likely, delta and error correction, and that the 8-byters were "reset" packets of some sort. Bernard got his o-scope out, and it suddenly became much clearer what was going on.<br />
<br />
The intuos marketing material clearly marks the data rate as being /maximum/ 200 samples per second. I'd initially considered this to be rather ambitious - maybe the USB and serial tablets could hit it, but no way the ADB tablets could go that fast. Turns out the Wacom engineers were smart enough, and cared enough, to hit that 200 samples per second, pretty much all the time. Which, in the end, makes sense - the guts of the tablets are identical, it's only the interface and interface firmware that changes between models. By modifying the ADB polling speed in Waxbee, we could get more, or less, 3-byte, 6-byte and 8-byte packets, and, within reason, we were getting absolutely 200 samples per second. If 3 bytes wasn't fast enough, 2 packets were munged together into a 6-byte packet. If that wasn't fast enough, lose the tilt information for a packet, and munge 3 packets together into 8 bytes. Sheer, insane, genius.<br />
<br />
The "packaging" of the pen packets sorted out, this only left the content. It was obvious that there was some sort of delta information in there, but testing quickly revealed it wasn't trivial. Neither simple addition nor "static shift and addition" worked. Time to start diving into code.<br />
<br />
This is where things got hard, and fast. I didn't have the tools required to even unpack the code resources from the "Classic" mac driver. So I wrote a resource unpacker in C. Which eventually netted me a 300K+ chunk of 68k binary. And, not having the tools to rip that down or even look at the names, I wrote myself a disassembler in scheme. I used scheme because I could run it from the REPL, and change things on the fly. A bit of intelligent function prologue matching got me down to a bunch of disassembled functions, and a big bunch of data. Traps were, with a bit of help from my old MPW discs, decoded, and that enabled me to find the code dealing with talking to ADB tablets, and, from there, the ADB state machine. Which was hideous.<br />
<br />
At this point, I was working from the 4.5.5 driver, which deals with *all* mac-connectable Wacom tablets. UD, SD, GD, XD series, ADB, serial and USB connections. And the damn thing is written in C++. It was too complex to even think about breaking down. So I went looking for earlier drivers. Google and wayback failed me, although I now knew what driver I needed. And eventually, I managed to source one from someone selling a boxed adb intuos on the french equivalent of eBay.<br />
<br />
Back to work. Rinse and repeat what I'd done with the 4.5.5 driver on 4.1.2, get to the ADB state machine, and, eventually, to the handler for "Talk Register 0" commands (the ADB polling mechanism). And the slow task of picking through the various bits of internal state. Decoding the structure of the class instances, and the class vtables. Tedious, mind-numbing code-sifting.<br />
<br />
The structure of the r0 handler is horrible. Cascading branches based on "if this bit set, then this, else this". But I'd managed to get it labelled up based on the bits being tested, so started manually walking through the code with my packet dumps. And here's how it works:<br />
<br />
When a tool first comes into proximity, there is a 7 byte packet sent containing tool type and tool serial number. I knew this already; this packet is identified by having it's top nybble set to 100x, where x is the tool index (0 for the first tool, 1 for a second tool in "dual tracking" mode).<br />
<br />
When a tool goes out of proximity, there is a 2 byte packet (which may well be part of a "stream" of deltas (i.e. appended after other packets) of the form 0xfe00 | (tool_index << 8). I knew that one as well.<br />
<br />
After the "in proximity" packet, we get one or more "tool major" packets. These vary by tool, and contain "raw" sensor data. The high bit is aways set, and the type of the packet is determined by masking various bits in the top byte. Size and content vary by packet type, from 6 to 8 bytes each. At this point, I only had access to standard styli, so I was only seeing "pen major" packets, which encode location, pressure, tilt, orientation and pen button state. agin, I knew this packet, and had it ripped to bits already.<br />
<br />
After the major packets, we get delta packets. The encoding is different per tool, but these are either 2 or 3 bytes each. They *all* encode a location delta as described above, the rest varies by tool type. And, for some tools, there's an alternating sequence of delta packet types. The 4d mouse, for example, alternates between "location and rotation" and "location and wheel" deltas.<br />
<br />
When some state changes that *isn't* encoded in the delta packets, we get a new "tool major" packet of the relevant type. Button state, for example (and, for obscure reasons, when the 4d mouse wheel goes from +ve to -ve nd vice versa).<br />
<br />
The encoded deltas themselves are of the form "sign + magnitude". For each data element (for example, horizontal tilt), the driver keeps a "shift" value, which is initialised to a "magic" number when we hit a tool major packet. The delta is calculated by shifting the magnitude left by "shift" number of bits, and this is then added or subtracted from the accumulated value according to the sign bit. So far, so (relatively) simple. But then comes the clever bit. The shift value is manipulated according to the magnitude field. So, for tilt, if the magnitude is 0b111, we add 2 to the shift value. 0b110, add 1. 0b010 or 0b011, subtract 1. 0b001, subtract 2. 0b000, subtract 3.<br />
<br />
It's what I'd describe as "adaptive shift delta encoding". It's not general, as such - the magic numbers need to be both synchronised between hosts, and probably hand-tuned according to scale and expected delta magnitudes per sensor reading, but it's absolutely brilliant.<br />
<br />
So, how does this "adaptive shift" stuff work, then?<br />
<br />
In a naive tablet protocol, for example that of the ultrapads and earlier, we transmit all the data, all the time. If the stylus has moved from x location 0x1000 to 0x1010, then to 0x1015, we transmit first 0x1000, then 0x1010, then 0x1015. Wacom could have done this for the intuos tablets, were it not for the combination of ADB's low throughput, and the "required" 200 samples/second thing.<br />
<br />
Given that losing samples was presumbly not acceptable, Wacom thus needed to trim down the amount of data being sent per sample. The obvious thing to do is to send deltas where possible. A simple delta encoding scheme sends a first packet containing the "full" data, and then a number of smaller difference packets. In the above example, we could imagine 0x1000, 0x10, 0x05, for example. This works extremely well for messages which are coherent, where each message is likely to be very similar to the preceding one.<br />
<br />
There is, however, a catch. If the difference is too big to fit in the fixed size delta packet, it becomes necessary to send a full-size "reset" packet, which "fattens up" the stream again. So, in order to be able to deal with a range of differences (for co-ordinates, these can be thought of as velocities), and thus avoid reset packets, the delta packets must be quite large. And Wacom didn't have the luxury of being able to make the deltas large. Timing constraints mean that the total size of the delta packets for *all* the relevant sensor outputs for a tool can be, maximum, 3 bytes. <br />
<br />
So, another approach is needed. A commonly used option is to increase or decrease the delta packet size "on the fly" dependent on the data to be encoded, but, again, that pesky fixed packet size kicks in. So that's out.<br />
<br />
Absolute accuracy 100% of the time is not needed, as long as the deltas approximate to, and rapidly converge on, the correct value. The most important measure is transducer location, and Wacom are measuring these to 1/2540 inch (or, if you prefer, 1/100 mm). That's pretty damn precise, a little bit of jitter isn't going to hurt that much as long as it converges fast.<br />
<br />
So, what wacom have done is change the range of delta measurements on the fly by shifting the delta value to the right, at the cost of reduced accuracy as the range increases (as we lose the lower significance bits). Let's look at that 5-bit location delta. Remember, it's 1 sign bit plus 4 bits of magnitude.<br />
<br />
<pre>shift vMin vMax error (mm)
----- ---- ---- ----------
0 0 15 0
1 0 31 0.001
2 0 63 0.002
3 0 127 0.004
4 0 255 0.008
5 0 511 0.016
6 0 1023 0.032
...
</pre>
<br />
In other words, with a shift value of 4 (which, by chance, is wacom's "starting" value for location delta shifts), it's possible to accommodate a pen velocity of ~ 25 cm / sec, whilst staying within a tolerance of 8/100ths of a mm of the "real" value. That's pretty good as it stands, and Wacom probably could have got away with leaving it at that, at least for the smaller tablets.<br />
<br />
Where the genius comes in, though, is how they've dealt with convergence / divergence.<br />
<br />
Effectively, what happens is this:<br />
<br />
If the delta magnitude is at the upper end of the scale (15 in the case of location deltas), the driver assumes it has "undershot" the target, and increments the shift. At the expense of absolute accuracy, this allows the next delta to encompass a larger range, approaching the assumed "far away" target value faster. If the actual value *was* 15, the next delta can still address it directly.<br />
<br />
At the lower end of the range, (say, 1 or 2), the driver decrements the shift, reducing range and thus increasing accuracy, and so converges on the "correct" value faster.<br />
<br />
At the *absolute* low end of the range, the driver assumes it has "overshot", and "downshifts" faster, reducing the shift value by 2 or more, allowing the "real" value to catch up.<br />
<br />
So, for any given delta magnitude, we "upshift" with maximum value, "downshift" for low-end values, and downshift faster for zeros. The only tuning needed is to decide where, and by how much, to downshift, and what the initial shift value should be.<br />
<br />
Like I said before - it's genius.tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com1tag:blogger.com,1999:blog-9184145065528610199.post-22139333082695493322014-04-18T12:59:00.000+02:002014-04-18T12:59:40.375+02:00Resurrecting Wacom's ADB-connected Intuos TabletsBloody hell. This has been the work, on and off, of over a decade. An ongoing thing that I'd prod at from time to time, a "let's have a look at that sodding thing again" project. Proof, if any were needed, that I'm persistent bastard, and that once something gets under my skin, it stays there.<br />
<br />
I've no idea what I'm gonna do now. Because it works. I currently have my (originally) adb-connected Y2k-era intuos hooked up, via USB, to my modern Mac running Mavericks.<br />
<br />
Enough blathering.<br />
<br />
https://github.com/tufty/adb-intuos<br />
<br />
I wouldn't have got this far if it wasn't for the work done by Bernard Poulin, both<br />
on the waxbee project, and the help he's given me in figuring out what the <br />
packet stream means. <br />
<br />
The technical requirements are (apart from an ADB Intuos) identical to those for<br />
Bernard's waxbee converter, even down to the pins used for the ADB connection on<br />
the Teensy. There's reasons for that, most of which boil down to me "borrowing"<br />
Bernard's ADB codec code. In any case, if you already have a Teensy wired up for<br />
an Intuos in the vague hope someone would eventually make the damned thing work,<br />
you're good to go. If you haven't, get one and wire it up.<br />
<br />
What does this do?<br />
<br />
It converts an ADB intuos tablet into the equivalent sized USB-equipped Intuos 2, <br />
thus enabling the use of stock Wacom drivers (up to v6.20, the last version handling<br />
Intuos 2 tablets; this may preclude being able to use the tablet on Windows Cool<br />
on your computer. <br />
<br />
I like the sound of that. What does it handle?<br />
<br />
I *believe* it handles all ADB intuos tablets without any need for configuration. <br />
It certainly handles the features of my GD-0608-A, including dual tracking, button <br />
bar, standard pen and 4D mouse.<br />
<br />
Sounds ace. What's the catch?<br />
<br />
It *certainly* doesn't handle any other tools. That's because I don't have any of<br />
them, so I can't work out how they work. Yes, that /is/ a hint. Please contact me <br />
if you have other Intuos 1 tools you can either lend me (I'm in France) or can <br />
hook up to an ADB intuos and dump the output.<br />
<br />
How do I make it work?<br />
<br />
Get yourself a Teensy 2.0 from pjrc.com<br />
Wire it up : https://code.google.com/p/waxbee/wiki/InterfacingADB<br />
Get yourself an AVR toolset. The rest is based on having a command line toolset and some sort of *n*x. Got a Windows? I have no idea what you do.<br />
Get the code : git clone https://github.com/tufty/adb-intuos.git<br />
Go to the 'converter' subdirectory, and type 'make'<br />
Load the resulting intuos_converter.hex onto your teensy using pjrc's teensy loader<br />
Unplug and replug the teensy, and you're off<br />
tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com2tag:blogger.com,1999:blog-9184145065528610199.post-46355856564617240922014-01-09T09:59:00.003+01:002014-01-09T10:06:15.678+01:00going back to snow leopard from mavericksSo, like a moron, I decided to upgrade my 2008 24" iMac from snow leopard to Mavericks. After all, Apple's updates make shit run faster (or, at least, have done in the past, and I've been doing OSX since the DP).
Step one was to go to Mountain Lion. 29 bucks later, I had a mac that ran like shit. So, get myself 4GB of memory, find one chip is dead (the dangers of second user memory). and a 3GB mac that sorta ran acceptably. hrm. Mavericks, then. A fuxking huge download and install, and, again, a mac. that runs like shit. Beachball frenzy.
Of course, this is the point at which my time machine disk decides to die.
Now, my time machine disk is not formatted as a single volume, but has a bunch of extra stuff on a now inaccessible volume. Crap.
time to pull out ddrescue, at least to recover that extra stuff. ddrescue is the number 1 go-to tool for recoveribg data, it's free, and I can't recommend it highly enough. It took 7 passes to do its thing, but I have my data back.
Next up is to try and get my external disk to come back to life. More ddrescue, copying /dev/zero to the freshly partitioned disk. 750gb takes a bit of time, good job I'm off work with a sciatica (2 injections ov valium & profenid per day, makes life more or less tolerable). I will, of course, blame spalling pisstakes, grandmatikal erorz and other crap on being drugged out of my tiny box, as well as entering this on an iphone's poxy osk.
next step. export contacts and diary entries from Mavericks.
then clone the internal disk to the external drive, and disconnect the fucker.
Boot 10.5 from the original disks (my 10.6 DVD won't even boot with Mavericks installed) and reformat the internal disk to zero. Install 10.5 and restore the 'original' extras, upgrade to 10.6, then manually restore all my data from the external drive (importing the stuff Mavericks has shat all over).
And then. Recompiling my 5 cross-deveopment toolkits.
yes, I'm a happy bunny. Not
tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-35466952235127164412012-07-09T14:10:00.001+02:002014-05-05T11:54:36.415+02:00Atomic setting on ARM<span style="font-family: Arial, Helvetica, sans-serif;">Back to our scheduled programming. Big gobs of ugly assembly code.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">When implementing a multitasking operating system, there is a need for dealing with mutating shared state. It's one of the unpleasant realities of the world of multitasking (and, indeed, multithreading), and it's fraught with danger.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">One of the basic functions we need to implement is the "atomic set" operation - setting a variable to a given value.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">Let's take the example of incrementing a variable. Naively, we might do this:</span><br />
<br />
<code>
ldr r0, [r1]<br />
add r0, r0, #1<br />
str r0, [r1]<br />
</code>
<br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">In most cases, this will work. However, there exists a case where, in fact, this can fail - if two threads of execution are trying to increment the value, and a task swap happens whilst one is actually doing the increment, the possibility is that the value will be (incorrectly) incremented only once, as follows:</span><br />
<br />
<code>
; Assume r1 points at a given address, holding the value 0<br />
[thread 1]<br />
ldr r0, [r1] ; r0 in thread 1 is now 0<br />
<interrupt></interrupt><br />
[thread 2]<br />
ldr r0, [r1] ; r0 in thread 2 is now 0<br />
add r0, r0, #1 ; r0 in thread 2 is now 1<br />
str r0, [r1] ; memory is now 1<br />
...<br />
<interrupt></interrupt><br />
[thread 1]<br />
add r0, r0, #1 ; r0 in thread 1 is now 1<br />
str r0, [r1] ; memory is now 1<br /><span style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></code><br />
<code><span style="font-family: Arial, Helvetica, sans-serif;">Obviously, we would expect memory to be set to 2, not to 1. So somehow we need to either stop the interrupts happening (easy enough, turn interrupts off, but that has fairly big impacts elsewhere) or somehow deal with the case where we are interrupted mid-operation. <br />
<br />
As luck would have it, ARMv6 provides us with 3 handy opcodes for this : ldrex, strex and clrex. Basically, we use ldrex to signal that we want to have exclusive write access to a memory location, strex signals that we're going to write to a location and close that exclusive access, with a test for success, and clrex says "hey, we're no longer interested". So, how do we use these to do what we want?<br />
<br />
Let's go back to our example above - incrementing a value in memory. Using ldrex / strex it would look like this:</span>
<br />
<code>
try_increment:<br />
ldrex r0, [r1]<br />
add r0, r0, #1<br />
strex r2, r0, r1<br />
cmp r2, #0<br />
bne try_increment<br />
</code>
<br /><span style="font-family: Arial, Helvetica, sans-serif;">
What happens here is:</span></code><br />
<br />
<ul>
<li><span style="font-family: Arial, Helvetica, sans-serif;">the initial ldrex loads the memory, and indicates that it wants an exclusive access to the memory itself.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">We then increment our value, as usual.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">We write the value back using strex - this will only succeed if:</span></li>
</ul>
<span style="font-family: Arial, Helvetica, sans-serif;"></span><br />
<ol><span style="font-family: Arial, Helvetica, sans-serif;">
<li>we still have an exclusive lock on the memory</li>
<li>no newer writes to that memory have happened since we established our exclusive lock</li>
</span></ol>
<span style="font-family: Arial, Helvetica, sans-serif;">
</span>
<ul>
<li><span style="font-family: Arial, Helvetica, sans-serif;">success of strex is indicated by register r2 (the "extra" operand that strex uses) being set to 0.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">If strex has failed, we go back and try again from the point where we loaded the initial value.</span></li>
</ul>
<span style="font-family: Arial, Helvetica, sans-serif;">
<br />
For our super-simple increment case, this will probably catch 99.99% of cases. We add a "belt-and-braces" approach, however, by making our task scheduler explicitly invalidate all exclusive reads, using the clrex opcode. This has the possibility of making any in-process ldrex-strex blocks restart (and thus take more time), but covers all the bases.<br />
<br />
Now, that's all fine and well, but we may want to use this method in our C code, without resorting to subroutine calls (by their very nature, exclusive operations happen at a very low level, and probably want to be inlined). So we're going to want to use some of that nastiest of nasties, inline assembler in gcc. Believe me, it's vile.<br />
<br />
Here's an implementation of an inline atomic increment using gcc inline assembler:</span>
<br />
<code>
inline uint32_t atomic_increment(uint32_t * memory) {<br />
uint32_t temp1, temp2;<br />
__asm__ __volatile__ (<br />
"1:\n"<br />
"\tldrex\t%[t1],[%[m]]\n"<br />
"\tadd\t%[t1],%[t1],#1\n"<br />
"\tstrex\t%[t2],%[t1],[%[m]]\n"<br />
"\tcmp\t%[t2],#0\n"<br />
"\tbne\t1b"<br />
: [t1] "=&r" (temp1), [t2] "=&r" (temp2)<br />
: [m] "r" (memory)<br />
);<br />
return temp1;<br />
}<br />
</code><span style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<code><span style="font-family: Arial, Helvetica, sans-serif;">Horrible, no? Note the use of local labels ('1:' and then branching to '1b' to indicate the latest local label called '1'), having to use encoded tabs and newlines to stop the assembler itself barfing, and the horrible workaround of multiple names for the same variables because gcc is, quite simply, broken. Still, it works, and the C optimiser can deal with it.<br />
<br /><br />
If you want to get more complex, I'd suggest looking at the ARM site for the example implementations of mutexes and condition variables using ldrex/strex. You'll have to deal with converting from ARM assembler to GNU, but as long as you don't try inlining them, you should be fine.</span></code>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com8tag:blogger.com,1999:blog-9184145065528610199.post-46231785416671277462012-05-09T22:10:00.002+02:002012-05-09T22:18:13.932+02:00An aside. Vector maths for games<br />
Most people, when they start writing games, run up against having to rotate and move objects. Generally speaking, they attack this problem "head on" using using trigonometry, specifically using sines, cosines and arctangents. This is a direct application of the SOH/CAH/TOA trigonometry you learned (or are in the process of learning, or will be learning later on) at secondary school.<br />
<br />
Although simple and easy to understand, this approach has a few drawbacks. <br />
<br />
<br />
<ul>
<li>The first (and usually most noticeable) of these is that it's quite slow. It's manageable for a small amount of objects, but if, for example, you're trying to do something like "Geometry Wars" with thousands of objects rotating and moving at the same time, you're soon going to find that all the trig rapidly becomes a bit of a bottleneck. It gets even worse if you move into 3 dimensions.</li>
<li>The second is related to the first, and, in these days where GPU acceleration and multi-core processing are commonplace, can be a major sticking point - Trigonometry can be hard to efficiently parallelise.</li>
<li>The third, and perhaps most important despite being the least obvious, is accuracy. Floating point calculations are never exact, and the errors in a purely trigonometric approach are usually cumulative. Generally speaking, this means that if you rotate an object by 1° clockwise, 360 times, it will not end up where it started.</li>
</ul>
<br />
<br />
Luckily, there exists a way to almost totally bypass the trigonometry. Let's recap what state we usually end up using for an object.<br />
<br />
<br />
<ul>
<li>We keep track of its location in space. We typically do this using a pair of co-ordinates.</li>
<li>We keep track of the direction it's facing. Typically using an angle.</li>
<li>We keep track of the direction in which it is moving, again using an angle.</li>
<li>We keep track of its current speed.</li>
</ul>
<br />
<br />
We also know how to convert from <i>cartesian</i> co-ordinates (x and y) to <i>polar</i> coordinates (angle and size) and vice versa, we know that polar co-ordinates are equivalent to cartesian co-ordinates, and we've seen that, for some tasks, it's easier to use polar co-ordinates than cartesian ones.<br />
<br />
What we're going to do is get rid of all the references to angles, and all the trigonometry. We're going to do this by using <i>vector</i> mathematics.<br />
<br />
So, we have <i>location</i>. This is a set of co-ordinates, and thus a <i>vector</i>. So far, so good.<br />
<br />
By combining direction of movement and speed into a single conceptual value, we get <i>velocity</i>, which is a set of (polar) co-ordinates, and also a <i>vector</i>. Unfortunately, it has an angle embedded in it, but as we know that polar and cartesian co-ordinates are equivalent, we can represent it in cartesian form (velocity-x and velocity-y).<br />
<br />
Which leaves us with that unfortunate direction we're facing, which is a single value indicating angle, and thus a <i>scalar</i>. However, the only bit we're interested in is the angle, so we can convert it into a vector with a size of 1 (a <i>unit vector</i>), and then get rid of the 'angle' part by converting it to cartesian form (facing-x and facing-y).<br />
<br />
So what does that get us?<br />
<br />
Well, let's look at the tasks we have done so far.<br />
<br />
<h3>
<b>Moving an object from its current location to the next location</b></h3>
<br />
This is the most basic task we want to do, and it's also the most simple. It's a trivial vector addition of location and velocity, which is to say :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>location-x = location-x + velocity-x<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>location-y = location-y + velocity-y<br />
<br />
<h3>
Accelerating an object in a particular direction</h3>
<br />
Again, this is pretty simple. We represent the acceleration as a vector quantity, and add it to velocity :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-x = velocity-x + acceleration-x<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-y = velocity-y + acceleration-y<br />
<br />
That's the basics of acceleration, but how do we get the acceleration value?<br />
<br />
I'm going to explain a basic model of Newtonian physics. Newton's Second Law is most commonly stated as *F=ma*, where F is the force applied to an object, m is its mass, and a is the acceleration - it can be restated as *a=F/m*. So to calculate the acceleration of each object, we need to know the force acting on it, and its mass.<br />
<br />
We'll assume the mass of the object is constant, for the moment (no near-light-speed effects here, thank you), so what wee need to calculate is the force acting on the object. Force is a vector value, and the overall force acting on the object is simply the addition of all the forces acting on it. So, we'll start each "step" of the game with a clean slate, and add the forces up as we go:<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-x = 0<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-y<span class="Apple-tab-span" style="white-space: pre;"> </span>= 0<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>... Accumulate forces<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>acceleration-x = force-x / mass<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>acceleration-y = force-y / mass<br />
<br />
So, let's look at the common forces we might<br />
<h4>
"Thrusting"</h4>
<br />
To apply a "thrust" in the direction we're facing, we can use the unit vector *facing*, multiplied by some constant of "thrust strength", as follows (remember, *facing* is a unit vector, so it always has a length of 1) :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-x += facing-x * thrust-strength<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-y += facing-y * thrust-strength<br />
<br />
<h4>
Acceleration towards the floor due to gravity</h4>
<br />
Assuming that gravity always works downwards, and that our co-ordinate system starts at the bottom left, we can make gravity work as follows (obviously, the value of gravity-constant should be chosen to work with whatever system of units we're using):<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-y -= gravity-constant<br />
<br />
<h4>
Acceleration towards (or away from) other objects</h4>
<br />
There's 2 cases here. <br />
<br />
The first is a very simplistic "chasing" behaviour, where an object "chases" another one. This is usually best done by rotating the object to point at its target (see later) and then "thrusting" as above, but it can also be useful to carry out a simple "go that way" approach.<br />
<br />
The second is a more complex simulation of gravity - if we were implementing something like Geometry Wars, we might have "black holes" that pull objects towards them. In this case, gravity is a bit more complex, as it not only works in a different direction for each pair of objects, but it gets stronger depending on how close the objects are to each other.<br />
<br />
In both cases, the first thing we do is to create a vector that gives both the direction in which we are going to be pulled, and the distance between the objects:<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>vector-x = other.location-x - location-x<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>vector-y = other.location-y - location-y<br />
<br />
In both cases, we need to know the distance between the two objects. For the simple chasing case, we'll calculate it directly:<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>distance = size(vector)<br />
<br />
Now, gravity usually works according to what's known as an <i>inverse square law</i>, which is to say that it's inversely proportional to the square of the distance between the two objects.<br />
<br />
Remember, Pythagorus tells us that, for any right angled triangle, <i>the sum of the squares on the short sides are equal to the square on the hypotenuse</i> - the square on the hypotenuse is, in this case, equal to the distance squared, so rather that calculating the distance in a single step, we do it in 2 steps so that we can keep the "distance-squared" value :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>distance-squared = (vector.x * vector.x) + (vector.y * vector.y)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>distance = sqrt(distance)<br />
<br />
Now, in both cases, we want to scale the vector by a factor. To do this, we need to scale the vector to a unit size, and then multiply it by our factor. To scale to a unit size, we divide each co-ordinate by "distance" :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>vector-x = vector-x / distance<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>vector-y = vector-y / distance<br />
<br />
For the simple chasing case, we now multiply by our "chasing strength", and we have our force :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-x = vector-x * chase-strength<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-y = vector-y * chase-strength<br />
<br />
For the attraction due to gravity case, we divide by the distance squared, and then multiply by some constant to get a usable value :<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-x = (vector-x * gravity-constant) / distance-squared<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>force-y = (vector-y * gravity-constant) / distance-squared<br />
<br />
<h3>
Braking / Friction</h3>
<br />
Braking is a special case. We could implement it by making a force vector that points in the opposite direction to the current velocity, but it's simpler (and faster) to simply multiply the current velocity by a factor.<br />
<br />
"Proportional" braking is very simple. If we wanted, for example, to brake by 5% every "step", we would do this:<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>braking-factor = 0.95<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-x = velocity-x * 0.95<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-y = velocity-y * 0.95<br />
<br />
This makes a very realistic simulation of friction.<br />
<br />
"Fixed amount" braking is a tiny bit more tricky - we need to know the size of the current velocity (using Pythagoras' theorem) and work out the factor from there:<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>speed = size(velocity)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if speed < braking-amount<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>braking-factor = 0<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>else<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>braking-factor = (speed - braking-amount) / speed<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>endif<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-x = (velocity-x * braking-factor)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>velocity-y = (velocity-y * braking-factor)<br />
<br />
<h3>
Rotating</h3>
<br />
Now, so far, everything we've done is incredibly simple - the most complex thing we've come across is a square root, and we haven't had to bother with angles *at all*.<br />
<br />
Rotating objects is a bit more complex. After all, how can we rotate something to a given angle if we don't know what angle it's already at?<br />
<br />
The short answer to this is<br />
<br />
<blockquote class="tr_bq">
I lied. It's not complex at all.</blockquote>
<br />
but the short answer isn't very interesting (and, above all, doesn't tell us anything useful). The long answer follows, and is based on matrix multiplication. As a reminder (or a first taste, if you've never seen this before), a matrix is a (conceptually) rectangular grid of values.<br />
<br />
Given that we're dealing with 2 dimensions, one of the most useful matrices we can imagine is a 2 x 2 matrix; we can multiply a vector (x, y) by such a matrix as follows :<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| a b | |x| = |(x * a) + (y * b)|</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| c d | |y| |(x * c) + (y * d)|</span><br />
<br />
Now, that's pretty simple to understand, and it's trivially simple to implement in code. So, multiplying a matrix by a vector is going to return a vector with (potentially) different values, depending on what's in the matrix. So far, so good, right?<br />
<br />
Now, let's go back to rotating stuff using SOHCAHTOA, keeping that in mind. When we rotate a point (x, y) by an angle θ, we get a point whose x co-ordinate is given by (x * cos(θ)) - (y * sin(θ)), and whose y co-ordinate is given by (x * sin(θ)) + (y * cos(θ)). Now that looks a lot like the matrix multiplication above, and indeed it is. We can encode a rotation by some arbitrary angle θ as a matrix, as follows:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| cos θ -sin θ |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| sin θ cos θ |</span><br />
<br />
This is, in fact so useful that the majority of graphical toolkits (OpenGL, DirectX and so on) provide an API that uses matrices (actually, an extension of the rotation vector given above, but we'll see that later)<br />
<br />
Now that in itself is pretty nifty, but here's where the real magick occurs. Remember SOHCAHTOA? Remember what it means?<br />
<br />
<br />
<ul>
<li>Sin of angle = length of Opposite / length of Hypotenuse</li>
<li>Cos of angle = length of Adjacent / length of Hypotenuse</li>
<li>Tan of angle = length of Opposite / length of Adjacent</li>
</ul>
<br />
<br />
We've already used the TOA bit, when we used atan2 beforehand. We're about to use the SOH and CAH bits to our profit. <br />
<br />
Consider a <i>unit vector</i>. The length of its hypotenuse will always be 1. And as any number divided by 1 is <i>unchanged</i>, we can see that the sin of the angle of that vector is given by the <i>length of the opposite</i> and the cos of the angle of that vector is given by the <i>length of the adjacent</i>. And we know those values already - they are, quite simply, the co-ordinates of the vector.<br />
<br />
So, rather than talking about angles, we can talk about unit vectors, and do away with all that messy trigonometry. Well, at least when we're talking about taking something that's aligned at an angle of zero, and rotating it to a particular angle as described by a unit vector v - we use a rotation matrix like this:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| v.x -v.y |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| v.y v.x |</span><br />
<br />
giving us<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>new-x = v.x * x - v.y * y</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>new-y = v.y * x + v.x * y</span><br />
<br />
What does this mean?<br />
<br />
<br />
<ul>
<li>We can, using our handy unit "facing" vector, draw a graphic of our object, rotated to the correct angle, without having to call any trigonometric functions whatsoever.</li>
<li>We can make an object A point at another object B by calculating the vector A->B (trivial, this is given by B.location - A.location) and then scaling it to unit size (again, pretty easy - divide each coordinate by the length of the original vector), and using that as the new "facing" vector for object A.</li>
<li>If we need "increment" or "decrement" ability (for example, "rotate by 5° CCW") we can precalculate unit vectors describing the angles we need (obviously, this would need to be done using trigonometric functions, but it would only need to be done once), and then use those vectors to create our rotation matrices.</li>
</ul>
<br />
<br />
The only thing that's really left is rotating one object rotate <i>towards</i> another (think turret slowly rotating to face player) in increments. To do this we need to know whether we are going to rotate clockwise or anticlockwise. The easiest (although probably not the fastest) way to do this is to use atan2() to get the angles of the current "facing" vector and the vector A->B, to decide which way to rotate, and then use the incremental approach above.<br />
<br />
Earlier, I touched on the fact that the various toolkits all provide matrix APIs. How these work is by combining both a rotation and translation matrix (yes, we can deal with translations too) into one matrix. For a 2-d case, we would do something like this:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| cosθ -sinθ t.x | | x |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| sinθ cosθ t.y | * | y |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| 0 0 1 | | 1 |</span><br />
<br />
Ignoring the pointless result given by the 1 in the vector, we would get :<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x = (x * cosθ) - (y * sinθ) + t.x</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>y = (x * sinθ) + (y * cosθ) + t.y</span><br />
<br />
This is, simply put, the value we had before, with the x and y values of t added on. The matrix therefore rotates an object by *θ*, and then translates the result by *t*.<br />
<br />
The matrices used by OpenGL and so on are not, in fact, 2D specific. Everything is generalised to the 3D case, so we use :<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| cosθ -sinθ 0 t.x |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| sinθ cosθ 0 t.y |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| 0 0 1 0 |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>| 0 0 0 1 |</span><br />
<br />
This is actually a matrix for 3D translations and rotations, with all the z axis stuff left out.<br />
<br />tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-11541388661972679772012-04-29T16:45:00.004+02:002012-04-29T16:45:56.162+02:00Back to Tech : Building for ARM "on the metal"It's been a while since I posted anything technical, what with the winter season and moaning about the launch of the Pi, price gouging on ebay, playing hockey, teaching my 12 year old to program, and a whole load of other stuff. Fear not, though; LambdaPi is still moving onwards, I have a branch on my machine that separates everything that is Lisp from everything that is kernel, and is moving towards a more solidly real-time base.<br />
<br />
Anyway. I had a request from Angus Hammond asking about build scripts, as follows:<br />
<br />
<blockquote class="tr_bq">
Would you be able to do a blog post at some point explaining how the build script you use in lambdapi works? The linking needed for an OS is obviously different to that needed normally if only because of the interrupts table, and that script is completely beyond my understanding. It would be greatly appreciated if you could explain any of the working behind it.</blockquote>
The answer to this is, of course, "of course". So let's have a look at what's required.<br />
<br />
Firstly, we need to understand what we want. The way the Pi boots (and the way I'm using qemu) is to (eventually) load a binary image into memory at location 0x00000000. This binary image is required to start with a standard ARM vector table, which we have already seen. Execution actually starts by transferring control to the ARM with the PC set to 0x00000000, the standard "reset" vector.<br />
<br />
So, what's going on in the build process?<br />
<br />
Well, firstly, we compile and assemble everything we need into object files. So far, so standard. The tricky bits come with the following Makefile rules :<br />
<br />
<code>
bin/kernel.img: bin/kernel.elf<br />
${OBJCOPY} -O binary $< $@<br />
<br />
bin/kernel.elf: lambdapi.ld $(OBJ) $(SYSLIBS)<br />
${LD} ${LDFLAGS} -T lambdapi.ld $(OBJ) $(SYSLIBS) -o $@<br />
</code>
<br />
<br />
<div>
The first of these to be executed is the one that builds bin/kernel.elf - this is dependent on the link script <span style="font-family: 'Courier New', Courier, monospace;">lambdapi.ld</span>, all the object files <span style="font-family: 'Courier New', Courier, monospace;">$(OBJ)</span>, and all the assorted libraries we're using <span style="font-family: 'Courier New', Courier, monospace;">$(SYSLIBS)</span>. We call the linker <span style="font-family: 'Courier New', Courier, monospace;">${LD}</span> with a set of flags <span style="font-family: 'Courier New', Courier, monospace;">${LDFLAGS}</span>, using a linker script <span style="font-family: 'Courier New', Courier, monospace;">lambdapi.ld</span>, passing in all the object files and system libraries. <span style="font-family: 'Courier New', Courier, monospace;">LDFLAGS</span> are set to </div>
<div>
<br /></div>
<code>
-nostdlib -static --error-unresolved-symbols</code>
<br />
<code><br /></code><br />
<div>
Which means "don't try and link any standard libraries, link everything statically, and throw an error if there's anything you can't find". </div>
<br />
So, at the end of that step, we should have a properly formatted elf-format file. Unfortunately, that's not what we want, we need to lose all the elf stuff and end up with a raw image to be loaded at a particular location, hence the objcopy stage, which takes the binary bit of the elf image and spits it out, standalone.<br />
<br />
Now, all we need to know is how to make the linker file. A standard ld script takes a bunch of object files and munges them all together, keeping the .text (code) sections together, then appending a load of other stuff at the end, notably the bss and data sections. Unfortunately, it doesn't guarantee any particular order of entry, and we *need* our reset table to be the very first entry. So, we need a custom link script. Let's look at it.<br />
<br />
<code>
ENTRY(__reset)<br />
SECTIONS<br />
{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>. = 0x0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>.text : {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>*(.reset)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>*(.text)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>__exidx_start = .;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>.ARM.exidx : { *(.ARM.exidx* .gnu.linkonce.armexidx.*) }<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>__exidx_end = .;<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>.data : { *(.data) }<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_start__ = .;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>.bss : { *(.bss) }<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_end__ = .;<span style="white-space: pre;"><br /></span>
}<br />
</code>
<br />
<br />
The first thing we do is tell the linker where the entry point is : symbol <span style="font-family: 'Courier New', Courier, monospace;">__reset</span>. In reality, we only need this if we'll ever be using the elf file directly, which we won't, but it doesn't hurt.<br />
<br />
Now for the meat of the script. We start by setting the link location to be 0x0, and then we create a text (code) section. The first part of this will be the vector table, which we have handily tagged in vector_table.s with a .section directive as follows:<br />
<br />
<code>.section .reset, "ax"</code><br />
<div>
<br /></div>
<div>
This tells the assembler that the code assembled should be placed in a section of code with a name of .reset (which I made up, I could equally well have used .simon, .foo, or anything else, as long as I was consistent between the ld script and the section name in the code itself).</div>
<div>
<br /></div>
<div>
In fact, we're linking all code labeled with a .reset section name first, but as there's only one of these, we can guarantee it will be first.</div>
<div>
<br /></div>
<div>
After that, and still within the .text section, comes anything linked as .text. Basically, that's everything "code" spat out of the C compiler, along with everything else we've labelled as code in the assembler.</div>
<div>
<br /></div>
<div>
Then we have a .ARM.exidx section, that's required for C++ exception handling if we ever need it. We don't, at the moment, but might do later.</div>
<div>
<br /></div>
<div>
Then we have the .data section - that's for any pre-defined, read-only values.</div>
<div>
<br /></div>
<div>
And finally, we have the .bss section - space allocated for unassigned data we might write to.</div>
<div>
<br /></div>
<div>
You'll also note that we set a couple of variables, __bss_start__ and __bss_end__ to the current link location "." - these are referred to in the code (so that we know where bss starts and ends, and thus where free memory starts) and will be replaced by the linker with the correct values.</div>
<div>
<br /></div>
<div>
And that's pretty much it. It looks scary, but it's not.</div>
<div>
<br /></div>
<div>
If you want chapter and verse on this, check out <a href="http://www.state-machine.com/arm/Building_bare-metal_ARM_with_GNU.pdf">this article</a> which is much more explicit, and covers using system libraries and so on. Also, it's worth looking at <a href="http://balau82.wordpress.com/2010/12/16/using-newlib-in-arm-bare-metal-programs/">balau's blog entry on newlib</a> (and all of balau's other bare metal articles, which are highly instructive). And, of course, the gnu binutils documentation.</div>
<div>
<br /></div>
<div>
Simon</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-224142506172943902012-03-03T14:19:00.002+01:002012-03-03T19:43:28.276+01:00Radio silence and gouging (A follow-up to Black Piday)It seems that the raspberrypi.org forums are back up, and have been for 12 hours or so. So far, there's only 2 people on the forums who seem to have got confirmed orders for Pis from the first batch. Given that there were upwards of 12K people registered on the forum, and most of them were probably frantically trying to get orders in from 06:01 on the 1st, we can safely say that demand was "underestimated".<br />
<br />
Oddly, there seems to be very little spleen being vented towards the Foundation, but some not inconsiderable anger directed at Farnell and RS, mainly over their incompetent and inconsistent handling of ordering and preordering. This anger is, I believe, misplaced - there's far more wrong with what RS (to a lesser extent) and Farnell are doing than being simply incompetent.<br />
<br />
I'll say it now. I feel that handing over control to Farnell and RS was a massive mistake, and it may cost the foundation much of the goodwill they have accumulated even whilst they were missing their hoped-for delivery dates.<br />
<br />
RS are seemingly not acknowledging anything. Nobody is reporting any response at all from them. "Register interest" and - nothing, nada, que chi.<br />
<br />
Farnell are, logistically speaking, doing better - they (if you can find the link to order in your country) are accepting preorders. However, they are:<br />
<br />
<ul>
<li>Giving wildly optimistic delivery dates on order, which are then being modified in email</li>
<li>Advertising and confirming orders at one price, and then subsequently modifying the price (which, as far as I understand it, but IANAL, is contrary to the Sale of Goods Act, at least in the UK)</li>
<li>Selling the Pi at inflated prices. This is the worst, as the price point was the one thing the Foundation have stuck to, and was a major selling point. The Model B (which is all that's on "sale" at the moment) was supposed to be 35 USD plus locally applicable taxes. In France (and, I believe, the rest of Europe), Farnell are quoting 33.07 EUR before tax, which comes to 42.65 USD. That's a 21% markup. The UK gets an advertised 24.65 GBP, or 39.03 USD, but a reportedly subsequently modified price of 26.65 GBP, or 42.20 USD. Again, a >20% markup.</li>
</ul>
<div>
I cannot understand why the Foundation are allowing this. RS are advertising at 21.60 GBP, which is, at least, at the 35 USD price point.</div>
<div>
<br /></div>
<div>
Farnell are destroying the Foundation's year-long commitment to a given price point. The Foundation should pull their licence NOW.<br />
<br />
It has been pointed out that, in their defence, Farnell are merely rolling the shipping cost into the purchase price and shipping for free, but that's actually fairly dishonest - it's a "reverse eBay" (i.e. the reverse of the situation where an article is listed with a low price and then the rest is made up by gouging the shipping). If you were (able) to order more Pis than one, you effectively pay for single item shipping on each and every one (or, put simply, overpay your shipping cost massively).</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-12765099036392794122012-03-03T08:46:00.002+01:002012-03-03T09:52:52.346+01:00Black PidaySo, I didn't get a Raspberry Pi. I'm not feeling overly bitter about it, as I wasn't actually expecting to, if nothing else because I was already at work before the 6AM GMT deadline. What I am mildly miffed about is that I can't currently do anything other than "express an interest in buying one" (or, in supplier-speak, "become a mailing list asset") from the major suppliers. I've had an interest since May last year.<br />
<br />
As I type this, the Raspberry Pi site is still showing a static page. There's no official news about what happened, who got one, who didn't, what the details of the deal with Farnell and RS are, apart from Twitter. The unofficial news (i.e. the stuff in print) is almost all wrong in fundamental details.<br />
<br />
I wouldn't want to have been one of the inhabitants of #1 Fruity Loop recently. It was becoming increasingly evident that there was no way 10,000 Pis were going to suffice. With every hour, new "news sites" were picking up on the Pi as a "$25 computer that does XBMC". None of them were picking up on the actual goal of the Pi itself, or mentioning the limitations of the Pi as an XBMC machine, or even any of the actual hardware features of the Pi beyond "it does XBMC". The wave upon wave of new users descending on the Pi forums and asking if they can install Windows on the Pi bore witness to this. What had started as a dream was rapidly becoming a monster. It was totally out of control, and there was no way the foundation would ever be able to meet the demand. Hence, I guess, the throwing up of hands and handing control of the hardware delivery side of things to a pair of corporate rapists[1]<br />
<br />
When people start realising what the limitations of the Pi as an XBMC machine is, the nerd rage will be spectacular. We probably have a week or so before they start being delivered to homes around the globe, and the "this thing's a fucking pile of shit" threads on the already overloaded forums start sprouting up by the thousand.<br />
<br />
The foundation themselves are largely to blame for this turn of events, as recent news has all been about multimedia and XBMC, and nothing to do with education at all. Indeed, the "About Us" page on the Raspberry Pi site has been changed from a short and sweet statement of the goals of the foundation into a bunch of word salad. From being about teaching programming, it's suddenly become<br />
<blockquote class="tr_bq">
<span style="background-color: white; color: #373737; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 24px;">We want owning a truly personal computer to be normal for children.</span></blockquote>
So, when 6AM GMT ran around, Farnell, RS and Raspberry Pi.org went down simultaneously. Not taken down by wave upon wave of pent up demand for educational computers, but by scalpers and people from hotukdeals.co.uk. These are not people who are going to do educational projects with the board, they are going to stick them to the back of the telly with blu-tac. the foundation wanted "the community" to take the board and supplied software, run with it, and create interesting projects. Installing XBMC is no more interesting in terms of computer science than editing a document in Microsoft Word, the kind of crap that's being taught in ICT, the kind of thing the Raspberry Pi was suposed to fix.<br />
<br />
<b>None of the people I know who are planning educational projects managed to get one from the first batch. Only one of them managed to get a preorder rather than "expressing an interest".</b><br />
<br />
There are probably less than a hundred people on the forums who are planning interesting stuff. putting aside 1% of the first batch "for them", even if it was done behind the scenes, would have done far more for the foundation's erstwhile goals than selling a million Pis to people who want to make Mame machines and set top boxes.<br />
<br />
So, like I said, I'm not bitter. But I am fucking angry. The emphasis has gone from producing something important, i.e. a machine that helps in teaching kids (and adults) how to actually control the hardware they own, on to simply producing another gadget. That emphasis has been changing slowly since around December. The sale itself was a total fucking mess, and, it appears, fucked up by both the foundation (setting a solid date and time for server meltdown, days in advance, and thus further engorging the until-then self-sustaining hype machine, was never gonna be a good idea), and RS/Farnell, by all accounts, don't appear to have been even close to ready (from denying the existence of the Pi through to stating that they will only be available to resellers).<br />
<br />
I remain totally committed to the originally stated goals of the foundation. The ones that don't appear on the site any more. I truly believe the Pi could change the nature of computing in a way that no other computer has ever done, that it could make an understanding of computer <i>science</i> part of basic education. Indeed, even if the foundation had never managed to get a single board out of the door, it has highlighted fundamental issues in education today, raised questions, and shown that, with a bit of will, something can be done.<br />
<br />
But all that is being lost, being driven into obscurity by a botched sale of millions of cheap, credit card sized computers running XBMC.<br />
<br />
Badly.<br />
<br />
I hope the foundation people at least get to pay off their personal loans, but I assume Farnell and RS are taking a substantial cut of the already slim margins.<br />
<br />
[1] Arguably, the handing over of sales to people like RS and Farnell should have happened around December, when the beta boards landed. At that point, the hype was containable. But that's with hindsight, and I guess at that point the foundation guys and girls still wanted to (and believe they could) keep control, which is understandable.tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-56604862691641905372012-01-31T12:53:00.001+01:002012-02-01T10:10:57.500+01:00CAR, CDR, CONS - an asideCommenter pcpete has been following the ARM OS stuff, but was having some trouble with my <a href="http://stm8sdiscovery.blogspot.com/2011/12/developing-multitasking-os-for-arm-part_14.html">CAR/CDR/etc macros</a>. I figured I'd do a little writeup for those who aren't totally au fait with what that's all about.<br />
<br />
<br />
CAR, CDR and CONS are terminology which has stuck around since the '50s. It's not going away, so if you want to Lisp, you need to get used to it.<br />
<br />
<br />
The original Lisp was implemented on the IBM 704 computer. This was a machine which had a 36 bit word (peculiar, but useful) and a 15 bit address bus. 36 bit words could be split into 4 parts (and hardware support was provided for doing so) known as the <b>address</b> (a 15 bit value), the <b>decrement</b> (again, 15 bits), the <b>tag</b> (3 bits) and the <b>flags</b> (3 bits). The very earliest work on Lisp provided operators to extract these 4 parts (Contents of Address part of Register or CAR, and likewise for Decrement, Tag and Flags, providing CDR, CTR and CFR). Later work (before the first implementation of Lisp) dropped direct manipulation of flags and tag, leaving CAR and CDR, and a "Construct" operator, CONS, which took values for the address and decrement parts respectively and stuffed them into a machine word.<br />
<br />
The fact that a machine word was bigger than the size of the address of a machine word meant that it was possible to implement <i>pairs of values</i> and <i>singly linked list cells </i>within one machine word. A pair of values (for example, 1 & 2) could be created as follows:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">CONS(1, 2)</span><br />
<br />
and singly linked lists by treating the 'address' part (paradoxically enough) as a value, and the 'decrement' part as the address of the next cell in the list. By setting the last pointer to some easily-recognised value (known as 'nil'), it is possible to find the end of a list. Thus, creating a list containing the numbers 1, 2 and 3, looks like this:<br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">CONS(1, CONS(2, CONS(3, nil)))</span><br />
<br />
Binary trees are also easy to construct using pairs - for example:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">CONS(CONS(1, 2), CONS(3, 4))</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">I'm generally the last one to point people at Wikipedia, but there's a reasonable and rather more graphical explanation of what have become known as <a href="http://en.wikipedia.org/wiki/Cons">'cons cells' over there</a>. </span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">It's worth noting that Lisp also allows you to use the notation '</span><span style="font-family: 'Courier New', Courier, monospace;">first</span><span style="font-family: Times, 'Times New Roman', serif;">' and '</span><span style="font-family: 'Courier New', Courier, monospace;">rest</span><span style="font-family: Times, 'Times New Roman', serif;">' instead of '</span><span style="font-family: 'Courier New', Courier, monospace;">car</span><span style="font-family: Times, 'Times New Roman', serif;">' and '</span><span style="font-family: 'Courier New', Courier, monospace;">cdr</span><span style="font-family: Times, 'Times New Roman', serif;">', although this only really makes sense when in list context, and doesn't allow for composition (</span><span style="font-family: 'Courier New', Courier, monospace;">caar</span><span style="font-family: Times, 'Times New Roman', serif;">, </span><span style="font-family: 'Courier New', Courier, monospace;">cadr</span><span style="font-family: Times, 'Times New Roman', serif;">, </span><span style="font-family: 'Courier New', Courier, monospace;">cdar</span><span style="font-family: Times, 'Times New Roman', serif;">, etc). Pretty much nobody uses </span><span style="font-family: 'Courier New', Courier, monospace;">first</span><span style="font-family: Times, 'Times New Roman', serif;"> and </span><span style="font-family: 'Courier New', Courier, monospace;">rest</span><span style="font-family: Times, 'Times New Roman', serif;">.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">So, Lisp uses what is, in effect, a pair (or list) oriented memory model as opposed to the more usual (these days) approach of addressing single memory cells individually. And if one is implementing a Lisp (as I am), it makes a certain amount of sense for the low level memory allocation and manipulation functions to operate in this way. Unfortunately, "modern" machines in general don't have words that are larger than their address bus size, and ARM is no exception to this. ARM is a 32 bit machine - we could restrict addressing within our lisp to 16 bits (maximum 64Kwords or 256KB) and all values to 16 bits, or, more sensibly, use "virtual" words of 2 machine words (or maybe more) in size. Usefully, ARM has </span><span style="font-family: 'Courier New', Courier, monospace;">LDRD</span><span style="font-family: Times, 'Times New Roman', serif;"> (Load Register Dual) and </span><span style="font-family: 'Courier New', Courier, monospace;">STRD</span><span style="font-family: Times, 'Times New Roman', serif;"> (Store Register Dual) operands that make this a snip to do.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">So, we can define cons cells as 8-byte aligned pairs of 32-bit values, manipulate them as pairs using </span><span style="font-family: 'Courier New', Courier, monospace;">LDRD</span><span style="font-family: Times, 'Times New Roman', serif;">/</span><span style="font-family: 'Courier New', Courier, monospace;">STRD</span><span style="font-family: Times, 'Times New Roman', serif;">, and we're a long way towards implementing a Lisp. </span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">But what of the Flags and Tag stuff that was originally in Lisp? Although, by the time Lisp came out, you had no way of directly manipulating them, they were still used to differentiate between pointers, direct values, and constants, amongst other things. And this is something we need to be able to do as well, otherwise we can't tell if (for example) the value 0x00000000 in the CDR of a cell is a pointer to a cell at the address 0x00000000, the integer value zero, or some special value indicating nil/end of list.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">As it happens, all is well. </span><span style="font-family: 'Courier New', Courier, monospace;">LDRD/STRD</span><span style="font-family: Times, 'Times New Roman', serif;"> require an 8-byte aligned address, which means the low 3 bits of a pointer will *always* be 0. We can, therefore, use those 3 bits as flags to indicate various other types, and, if we're careful, we can encode the majority of types in such a way as to keep their values "boxed" (i.e. containable in a 32 bit value). Values requiring more than 32 bits to encode (strings, large numbers, rational numbers, etc) can either be encoded as lists of boxed values, pairs, or using any other encoding the programmer deems useful as long as they are easily recognisable.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">So, back to the code I posted, which uses CAR, CDR, SET_CAR and SET_CDR macros.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">/* linked list structure */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef struct task_list {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> task_t * _car;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> struct task_list * _cdr;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">} task_list_t;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* some LISPy primitives */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">#define CAR(x) (x)->_car</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">#define CDR(x) (x)->_cdr</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">#define SET_CAR(x,y) CAR(x)=(y)</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;">#define SET_CDR(x,y) CDR(x)=(y)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">As we can see, task_list_t is an analogue for the cons cell, being simply 2 address-bus sized values held together. Indeed, my code elsewhere looks like this:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef cons_t task_list_t;</span><br />
<br />
<span style="font-family: Times, 'Times New Roman', serif;">but the original formulation is perhaps easier to grok at first.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">So, given a pointer </span><span style="font-family: 'Courier New', Courier, monospace;">x</span><span style="font-family: Times, 'Times New Roman', serif;"> to a cons cell </span><span style="font-family: 'Courier New', Courier, monospace;">c</span><span style="font-family: Times, 'Times New Roman', serif;">, we can see that </span><span style="font-family: 'Courier New', Courier, monospace;">CAR(x)</span><span style="font-family: Times, 'Times New Roman', serif;"> expands to</span><span style="font-family: 'Courier New', Courier, monospace;">(x)->_car</span><span style="font-family: Times, 'Times New Roman', serif;">, in other words returning the </span><span style="font-family: 'Courier New', Courier, monospace;">_car</span><span style="font-family: Times, 'Times New Roman', serif;"> element of the cell </span><span style="font-family: 'Courier New', Courier, monospace;">c</span><span style="font-family: Times, 'Times New Roman', serif;"> pointed to by </span><span style="font-family: 'Courier New', Courier, monospace;">x</span><span style="font-family: Times, 'Times New Roman', serif;">. Likewise </span><span style="font-family: 'Courier New', Courier, monospace;">SET_CAR(x, y)</span><span style="font-family: Times, 'Times New Roman', serif;"> becomes </span><span style="font-family: 'Courier New', Courier, monospace;">(x)->_car = (y)</span><span style="font-family: Times, 'Times New Roman', serif;">, assigning the value </span><span style="font-family: 'Courier New', Courier, monospace;">y</span><span style="font-family: Times, 'Times New Roman', serif;"> to the _car element of the cell </span><span style="font-family: 'Courier New', Courier, monospace;">c</span><span style="font-family: Times, 'Times New Roman', serif;"> pointed to by </span><span style="font-family: 'Courier New', Courier, monospace;">x</span><span style="font-family: Times, 'Times New Roman', serif;">. Doing this as macros is probably premature optimisation, but it's "the done thing".</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Our task scheduler uses a list (actually, a plurality of lists) of tasks to execute, and considers them for execution in a "round robin" style. So, assuming we have 4 tasks, a, b, c and d, we might have a list that looks, in lisp syntax, like this:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">(a b c d)</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">or, in diagram form, where the top row is the CDR of the cell, and the bottom the CAR, and * indicates a pointer to the next cell</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">* - * - * - nil</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">| | | |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">a b c d</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">We need to rotate the list as we consider each task, so that the next time through we consider the next task. So after considering task a for execution, we want the list to look like this:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">(b c d a)</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<br />
<span style="font-family: Times, 'Times New Roman', serif;">or, in diagram form</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">* - * - * - nil</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">| | | |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">b c d a</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<br />
<span style="font-family: Times, 'Times New Roman', serif;">In true lisp style, we'll use a singly linked list for this, with the CAR of each cell being a pointer to the task, and the CDR being a pointer to the next cell, or nil for end of list. </span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">So, we come in, and we find the CAR and CDR of the (original) list. CAR is, obviously enough, task 'a', the task we want to consider for execution. CDR, however, is not task b, but the <i>rest of the list</i> (hence the alternative 'rest' in Lisp) - i.e.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">(b c d)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<br />
<span style="font-family: Times, 'Times New Roman', serif;">or, in diagram form</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">* - * - nil</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">| | |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">b c d</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<br />
<span style="font-family: Times, 'Times New Roman', serif;">So our next step is to put 'a' onto the end of the list. This is not as simple as it seems - CONS can only be used to push items onto the front of a list - CONS(list, a) would result in this:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">((bcd) . a)</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<br />
<span style="font-family: Times, 'Times New Roman', serif;">or, in diagram form</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">a</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">|</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">* - * - nil</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">| | |</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">b c d</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<br />
<span style="font-family: Times, 'Times New Roman', serif;">which is not a true list in Lisp terms (it's a "dotted pair" with a list as its first element). W</span><span style="font-family: Times, 'Times New Roman', serif;">e need some sort of APPEND operator that adds an element to the end of a list, a sort of 'reverse cons'. Lisp has one of those, it's (oddly enough) called APPEND, it's usually defined recursively, and it always creates new cons cells all over the place. </span><span style="font-family: Times, 'Times New Roman', serif;"> We <i>really</i> don't want to go allocating new memory in a function that's going to be called thousands of times per second simply to move a few values about - we want to keep the same cons cells and simply swap their CDR values around. The algorithm thus becomes:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">first := list</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">if CDR(first) != NIL</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> list, end := CDR(first)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> end := CDR(end) while CDR(end) != NIL</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CDR(first, NIL)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CDR(end, first)</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">With that in mind, have another read through http://stm8sdiscovery.blogspot.com/2011/12/developing-multitasking-os-for-arm-part_14.html</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Simon</span></div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com1tag:blogger.com,1999:blog-9184145065528610199.post-2607060636527853332012-01-16T09:32:00.002+01:002012-01-31T12:53:32.248+01:00Developing a multitasking OS for ARM part 3 3/4So, we looked at how to do the difficult part of task swapping last time, now let's look at how we go about handling interrupts and the syscall layer.<br />
<br />
Firstly, interrupts. We'll not bother with FIQs for the moment, we'll stick with IRQs.<br />
<br />
Despite having an ARM1176 core, the Raspberry Pi (or, rather, its Broadcom SoC) doesn't have a vectored interrupt controller - instead it has 3 "standard" ARM interrupt controllers. That makes things a bit more complex for interrupt handling, but it's not too arduous. As a quick reminder, here's the IRQ code we had before, with a little bit of meat in the middle:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _irq_handler</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">_irq_handler:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>lr, lr, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save adjusted LR_IRQ */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>srsdb<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!, #SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* save LR_irq and SPSR_irq to system mode stack */</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsid<span class="Apple-tab-span" style="white-space: pre;"> </span>i,#SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Go to system mode */</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save registers */</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>and<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, sp, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* align the stack and save adjustment with LR_user */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Identify and clear interrupt source */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Should return handler address in r0 */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bl<span class="Apple-tab-span" style="white-space: pre;"> </span>identify_and_clear_irq</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>blxne<span class="Apple-tab-span" style="white-space: pre;"> </span>r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* go handle our interrupt if we have a handler */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* An interruptible handler should disable / enable irqs */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Exit is via context switcher */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>b<span class="Apple-tab-span" style="white-space: pre;"> </span>switch_context_do</span><br />
<div>
<br /></div>
<div>
and the context switcher looks like this:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global switch_context_do</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">switch_context_do:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Do we need to switch context? */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, #0x0c<span class="Apple-tab-span" style="white-space: pre;"> </span>/* offset to fourth word of task block */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__current_task</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__next_task</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, [r0]</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, #0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* If there's no next task, we can't switch */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>beq<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lswitch_context_exit</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, #0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* In the normal case, we will have a __current_task */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bne<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lnormal_case<span class="Apple-tab-span" style="white-space: pre;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* When we get here, we're either idling in system mode at startup, or we've <span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* just voluntarily terminated a task. In either case, we need to remove the<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* return information we just pushed onto the stack, as we're never, ever going */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* back.<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, r1}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* remove any potential stack alignment */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, #0x3c<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and the other registers that should be there */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* r0-r12, interrupted pc & spsr<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Now we can do our first actual task swap */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__next_task<span class="Apple-tab-span" style="white-space: pre;"> </span>/* swap out the task */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__current_task</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, [r2, r3]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and restore stack pointer */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>b<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lswitch_context_exit<span class="Apple-tab-span" style="white-space: pre;"> </span>/* bail */<span class="Apple-tab-span" style="white-space: pre;"> </span></span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Lnormal_case:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, r2<span class="Apple-tab-span" style="white-space: pre;"> </span>/* otherwise, compare current task to next */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>beq<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lswitch_context_exit</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>clrex<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Clear all mutexes */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* At this point we have everything we need on the sysmode (user) stack<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* {stack adjust, lr}_user, {r0-r12}_user, {SPSR, LR}_irq <span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save our stack pointer, and swap in the new one before returning<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__current_task<span class="Apple-tab-span" style="white-space: pre;"> </span>/* save current stack pointer */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, [r0, r3]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* stack pointer is second word of task object */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__next_task<span class="Apple-tab-span" style="white-space: pre;"> </span>/* swap out the task */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =__current_task</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, [r2, r3]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and restore stack pointer */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Lswitch_context_exit:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* restore LR_user and readjust stack */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and other registers */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>rfeia<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!<span class="Apple-tab-span" style="white-space: pre;"> </span>/* before returning */</span></div>
</div>
<div>
<br /></div>
<div>
The context switcher looks complex, but it isn't really. There's 4 cases to cater for, viz:</div>
<div>
<br /></div>
<div>
<ul>
<li>No 'next' task, don't switch</li>
<li>No 'current' task, switch to 'next' task, cleanup stack and switch to 'next' task</li>
<li>'next' task is the same as 'current' task, don't switch</li>
<li>'next' task is different from 'current' task, switch</li>
</ul>
</div>
<div>
Obviously, the meat of the interrupt handler is held in 'identify_and_clear_interrupt', which does pretty much what it says on the tin. In this article, I'll show the handler for the qemu platform, which is significantly simpler than that for the Pi, but the Pi handler looks largely the same modulo having to deal with 3 controllers.</div>
<div>
</div>
<div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global<span class="Apple-tab-span" style="white-space: pre;"> </span>identify_and_clear_irq</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">identify_and_clear_irq:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"></span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;">FUNC<span class="Apple-tab-span" style="white-space: pre;"> </span>identify_and_clear_irq</span></div>
<span style="font-family: 'Courier New', Courier, monospace;">
</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r4, =.Lirq_base</span></div>
<span style="font-family: 'Courier New', Courier, monospace;">
</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r4, [r4]</span></div>
<span style="font-family: 'Courier New', Courier, monospace;">
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>/* read the vector address to indicate we're handling the interrupt */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r4, #IRQ_HANDLER]</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>/* which IRQs are asserted? */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r4, #IRQ_STATUS]</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r5, =__irq_handlers</div>
<div>
<br /></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>clz<span class="Apple-tab-span" style="white-space: pre;"> </span>r6, r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* which IRQ was asserted? */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, #1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* make a mask */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>bic<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, r0, r1, lsl r6<span class="Apple-tab-span" style="white-space: pre;"> </span>/* clear flag */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r4, #IRQ_ACK]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Now acknowledge the interrupt */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r4, #IRQ_SOFTCLEAR]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and make sure we clear software irqs too */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r5, r6, lsl #2]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* load handler address */</div>
<div>
.Lret:<span class="Apple-tab-span" style="white-space: pre;"> </span>bx<span class="Apple-tab-span" style="white-space: pre;"> </span>lr<span class="Apple-tab-span" style="white-space: pre;"> </span>/* exit */</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
.Lirq_base:</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>IRQ_BASE</div>
<div>
<br /></div>
<div>
<div>
.bss</div>
<div>
.global __irq_handlers</div>
<div>
__irq_handlers:<span class="Apple-tab-span" style="white-space: pre;"> </span>.skip<span class="Apple-tab-span" style="white-space: pre;"> </span>32 * 4</div>
</div>
<div>
<br /></div>
</span></div>
</div>
</div>
<div>
and patching in a hander is as simple as setting the address for the interrupt handler into __irq_handlers at the appropriate place. Simples, as they say in internet-land.</div>
<div>
<br /></div>
<div>
Syscalls are very similar. Here's the syscall handler:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global<span class="Apple-tab-span" style="white-space: pre;"> </span>_svc_handler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">_svc_handler:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>srsdb<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!, #SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* save LR_svc and SPSR_svc to sys mode stack */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsid<span class="Apple-tab-span" style="white-space: pre;"> </span>i,#SYS_MODE</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save registers */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>and<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, sp, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* align the stack and save adjustment with LR_user */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0,[lr,#-4]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Calculate address of SVC instruction */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* and load it into R0. */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>and<span class="Apple-tab-span" style="white-space: pre;"> </span>r0,r0,#0x000000ff<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Mask off top 24 bits of instruction */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* to give SVC number. */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, =__syscall_table<span class="Apple-tab-span" style="white-space: pre;"> </span>/* get the syscall */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r2, r0, lsl#2]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, #0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>beq<span class="Apple-tab-span" style="white-space: pre;"> </span>_syscall_exit</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>tst<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, #0x01<span class="Apple-tab-span" style="white-space: pre;"> </span>/* what linkage are we using */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bxeq<span class="Apple-tab-span" style="white-space: pre;"> </span>r3<span class="Apple-tab-span" style="white-space: pre;"> </span>/* ASM, just run away */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bic<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, r3, #0x01</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>blx<span class="Apple-tab-span" style="white-space: pre;"> </span>r3<span class="Apple-tab-span" style="white-space: pre;"> </span>/* C, must come back here */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global _syscall_exit</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">_syscall_exit:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* restore LR_user and readjust stack */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and other registers */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>rfeia<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!<span class="Apple-tab-span" style="white-space: pre;"> </span>/* before returning */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.section .bss</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global __syscall_table</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">__syscall_table:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* leave space for 256 syscall addresses */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>.skip<span class="Apple-tab-span" style="white-space: pre;"> </span>2048</span></div>
</div>
<div>
<br /></div>
<div>
The fun bit is how we go about getting the syscall number into the handler. I've taken the "canonical" approach of using the svc operand, hence the bit where we get the instruction and extract the number. Other ways include using a register, a global variable, pushing onto the stack, or some combination of these.</div>
<div>
<br /></div>
<div>
The other twist here is that I allow for both C and assembler syscall functions by setting (or not) bit 0 of the function address in the syscall table. Assembler syscall handlers must, of course, exit via _syscall_exit or equivalent, but that's down to the programmer to get it right.</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com3tag:blogger.com,1999:blog-9184145065528610199.post-19038507064765058462012-01-07T10:16:00.002+01:002012-01-31T12:54:03.319+01:00Developing a multitasking OS for ARM part 3 1/2Okay, so last time we looked at what we need to schedule and store top level information about tasks in our fledgling OS. And it was pretty easy to do, because we could do all of it in C. Unfortunately, things are about to get complicated again, because we're about to dive down into assembler again.<br />
<br />
Whoopee! I can almost hear the sound of "back" buttons being clicked as I type this.<br />
<br />
So. Multitasking. How's that gonna work, then? Largely speaking, there's 2 types of multitasking - preemptive multitasking, where tasks run for a specified amount of time then get forcibly swapped out, and cooperative multitasking, where tasks run until they decide to give some time to someone else. We're going to implement (because there's precious little overhead in doing so) a hybrid where tasks can be "nice" and give time to others, but where the absolute maximum time they get is capped by a preemptive scheduler.<br />
<br />
So. Let's look at the sequence of events for a user-triggered task swap. We want the user to use a line of code that looks like this (remember, I'm developing something that runs scheme...)<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">(task-swap-out)</span><br />
<br />
However, the user's code is running in user mode (remember the ARM processor states), and it can't directly access the task scheduler. This is where software interrupts / SVC calls come in - the user's code *can* use the <span style="font-family: 'Courier New', Courier, monospace;">svc</span> instruction. This, in fact, is the beginning of what is known as a syscall interface, the way that unprivileged user code calls (or causes to happen) kernel functions. <br />
<br />
Executing the svc instruction causes the following to happen:<br />
<br />
<ul>
<li>CPSR_usr is transferred to SPSR_svc</li>
<li>PC is stored in LR_svc</li>
<li>Processor switches to SVC mode (SP_usr and LR_usr are now hidden by SP_svc and LR_svc, CPSR is identical except for processor state change)</li>
<li>PC is loaded with the address of the SVC exception handler</li>
</ul>
<br />
At this point, what we need to do is store R0-R12, LR_usr and PC (before entry to svc handler) into the user stack, in a known order, then save the user stack pointer to the task's "housekeeping" information, load the equivalents back in for the next task, and jump out of the handler back to user code. We'll get onto that in a minute.<br />
<br />
Preemptive task swapping will be done by using a timer interrupt. Thus, for a preemptive task swap, the situation is quasi-identical, with _svc above replaced by _irq. The only difference is that the PC stored to LR_svc is actually 4 bytes on from where we want to restart, so we need to remember to take that into account.<br />
<br />
So. How do we go about saving our information to the user stack? This is made quite easy by the fact the user mode register are identical to the system mode registers. So we need to save the svc/irq mode stuff (LR, SPSR) into the system mode stack, then swap into system mode and save the rest. The first bit is covered by one instruction, which might have been made for the task:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">srs (Store Return State) - store LR and SPSR of the current mode onto the stack of a specified mode</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">and, of course, its "twin"</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">rfe (Return From Exception) - load PC and CPSR from address</span><br />
<br />
So, the preamble for the svc handler is as follows:<br />
<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">FUNC<span class="Apple-tab-span" style="white-space: pre;"> </span>_svc_handler</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>srsdb<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!, #SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* save LR_svc and SPSR_svc to svc mode stack */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsid<span class="Apple-tab-span" style="white-space: pre;"> </span>i,#SYS_MODE /* go sys mode, interrupts disabled */</span><br />
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save registers */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>and<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, sp, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* align the stack and save adjustment with LR_user */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}</span><br />
<div>
<br /></div>
<div>
and for an irq:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">FUNC _irq_handler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>lr, lr, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save adjusted LR_IRQ */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>srsdb<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!, #SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* save LR_irq and SPSR_irq to system mode stack */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsid<span class="Apple-tab-span" style="white-space: pre;"> </span>i,#SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Go to system mode */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Save registers */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>and<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, sp, #4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* align the stack and save adjustment with LR_user */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>push<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}</span></div>
</div>
<div>
<br /></div>
<div>
Note that the only difference is that the irq handler adjusts the return address (as we want to go back to the interrupted instruction, not the next one).</div>
<div>
<br /></div>
<div>
Given that we are now *always* in system mode, exiting from either handler is identical:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0, lr}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* restore LR_user and readjust stack */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, sp, r0</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>pop<span class="Apple-tab-span" style="white-space: pre;"> </span>{r0-r12}<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and other registers */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>rfeia<span class="Apple-tab-span" style="white-space: pre;"> </span>sp!<span class="Apple-tab-span" style="white-space: pre;"> </span>/* before returning */</span></div>
</div>
<div>
<br /></div>
<div>
I'll move onto how to implement the guts of the two handlers in the next post. But before we go, here's how we set up a task in "C" land. <br />
<br />
Remember, when we switch into a task, we will be pulling a stored process state from the task's stack into the registers, and then restoring the PC and CPSR, also from the task's stack. Setting up a task, then, involves "faking" the preamble of the exception handlers above. Note the use of exit_fn as the value of LR_usr, this is where we go when a task dies, and is used to clean up after task exit, and the use of 'entry' (the address of the task's entry function) as the value of LR_svc/irq, which will be used as the "return" address from the exception handler. <br />
<br />
The use of exit_fn means we can schedule "one-shot" tasks (which not all realtime OSs can do). Hooray for us.</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> // Allocate stack space and the actual object</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task_t * task = malloc( sizeof(task_t) );</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> void * stack = malloc( stack_size * 4 );</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> unsigned int * sp = stack + stack_size;</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task->stack_top = stack;</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task->priority = priority;</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task->state = TASK_SLEEP;</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task->id = (unsigned int)task & 0x3fffffff;</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> </span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x00000010; // CPSR (user mode with interrupts enabled)</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = (unsigned int)entry; // 'return' address (i.e. where we come in)</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x0c0c0c0c; // r12</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x0b0b0b0b; // r11</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x0a0a0a0a; // r10</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x09090909; // r9</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x08080808; // r8</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x07070707; // r7</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x06060606; // r6</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x05050505; // r5</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x04040404; // r4</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x03030303; // r3</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x02020202; // r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x01010101; // r1</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = (unsigned int) env; // r0, i.e. arg to entry function</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> if ((unsigned int)sp & 0x07) {</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0xdeadc0de; // Stack filler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = (unsigned int)exit_fn; // lr, where we go on exit</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x00000004; // Stack Adjust</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> } else {</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = (unsigned int)exit_fn; // lr, where we go on exit</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> *(--sp) = 0x00000000; // Stack Adjust</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> }</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> </span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> task->stack_pointer = sp;</span></div>
</div>
<div>
<br /></div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-1243729552691589072011-12-14T10:49:00.002+01:002012-01-31T12:52:04.288+01:00Developing a multitasking OS for ARM part 3Okay. We're almost done with the big bits of scary assembler. Indeed, this post is almost totally assembler free, and will deal with some C functions and definitions we need for later.<br />
<br />
We want to do something useful with what we have at the moment. We could simply implement "something useful" as a C language routine called <span style="font-family: 'Courier New', Courier, monospace;">c_entry()</span>, which would run in SVC mode with interrupts off. In some cases, that would be sufficient. But it would hardly count as an OS, let alone a multitasking one.<br />
<br />
So, let's look at what we want to do, make some definitions. We want tasks that run in an unprivileged mode (i.e user mode) and are either preemptively swapped out by the OS in order to run another task, or which periodically yield control of the processor to another task. They must be able to terminate. For the moment, we won't worry too much about protected memory spaces, IPC, or any of that jazz (which complicate matters, but which will come later).<br />
<br />
A task, must have its own, inviolate, set of registers, and its own stack. It must also have some other information - entry point, state, and potentially priority. My implementation is based on scheme, so a task must also have an environment, but that's not absolutely necessary.<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">/* function pointer type returning void and taking a pointer to an environment */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef void(*task_entry_point_t)(void * environment);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* potential task states */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef enum {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> TASK_RUNNABLE,</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> TASK_SLEEPING,</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">} task_state_t;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* And the task itself */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef struct {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> void * stack_top; /* limit of the task stack */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> void * stack_pointer; /* current stack pointer */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> uint32_t priority:5; /* priority, 0-31 */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> uint32_t state:1; /* state, task_state_t */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> uint32_t id:26; /* task id */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">} task_t;</span><br />
<br />
Obviously, we need to know what the current task is, and have a list of other tasks that might want to run. This is not identical to my code, as tasks are actually scheme objects, but you get the idea.<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">/* linked list structure */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">typedef struct task_list {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> task_t * _car;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> struct task_list * _cdr;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">} task_list_t;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* some LISPy primitives */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">#define CAR(x) (x)->_car</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">#define CDR(x) (x)->_cdr</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">#define SET_CAR(x,y) CAR(x)=(y)</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;">#define SET_CDR(x,y) CDR(x)=(y)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* We'll need these later */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">#define nil (task_list_t*)0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">#define skip (task_t*)0</span></div>
<br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* And the bits we need for the actual lists */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">task_t * __current_task;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">task_list_t * __priority_lists[31];</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Now, the approach we'll be taking to multitasking is this:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Each task is created with a prority, and positioned as such in one of the priority lists. Every time we need to find a task, we go through the priority lists, starting at zero, and ending at 31. We look at each element in turn of the list by removing it from the head of the list and then grafting it onto the end of the list. This way we round-robin schedule within each priority. Only "runnable" tasks get scheduled, obviously. If the task is actually the placeholder "skip", we will skip onto the next lowest priority. Th</span><span style="font-family: Times, 'Times New Roman', serif;">is way, all tasks eventually get a bite of CPU, with high priority tasks getting vastly more than the low priority ones.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Obviously, the initial setup of the lists is critical, and should be done in </span><span style="font-family: 'Courier New', Courier, monospace;">c_entry</span><span style="font-family: Times, 'Times New Roman', serif;">:</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">task_t * __sleep_task;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">for (int i = 0; i < 31; i++) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> __priority_lists[i] = (task_list_t *)malloc(sizeof(task_list_t));</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CAR(__priority_lists[i], skip);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CDR(__priority_lists[i], nil);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">__priority_lists[31] = </span><span style="font-family: 'Courier New', Courier, monospace;">(task_list_t *)</span><span style="font-family: 'Courier New', Courier, monospace;">malloc(sizeof(task_list_t));</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">SET_CAR(__priority_lists[31], __sleep_task);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">SET_CDR(__priority_lists[31], nil);</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<br />
<span style="font-family: Times, 'Times New Roman', serif;">The astute amongst you will notice the use of the C library function </span><span style="font-family: 'Courier New', Courier, monospace;">malloc()</span><span style="font-family: Times, 'Times New Roman', serif;"> in there, despite not having a c library. Don't worry about it. It'll come later. Do worry about me not checking for errors :)</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Note that priority 31 has *no* 'skip' entry, and points to a real task. This task should not, under any circumstances, be missed out.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Now that's all done, we can find the next runnable task.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">/* lispish function */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">task_list_t * nconc(task_list_t * car, task_list_t * cdr) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> if (car == nil) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return cdr;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> } else {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> task_list_t * x = car;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> while (CAR(x) != nil) x = CAR(x);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CDR(x, cdr);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return car;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">task_t * next_runnable_task() {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> for (int i = 0; i < 32; i++) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> while(CAR(__priority_lists[i] != skip)) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> /* rotate the list */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> task_list_t * car = CAR(__priority_lists[i]);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> task_list_t * cdr = CDR(__priority_lists[i]);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> SET_CDR(car, nil);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> __priority_lists[i] = nconc(cdr, car);</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> /* check runnability */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> if (car->_car->state == TASK_RUNNABLE)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return car->_car;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> /* we should never get here, but just in case, eh? */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return __sleep_task;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Now, that's all fine and well, but what about setting up tasks and actually making them swap? Ah. That's a bit more complex, and we're gonna have to delve down into assembler again. I'll get into that next time round.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: Times, 'Times New Roman', serif;">Until then, though, here's a couple of little functions we needed before.</span><br />
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">void * malloc(size_t size) {</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;"> extern char * __heap_top;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> extern char * __memtop;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> char * prev_heap_top = __heap_top;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> </span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> if (__heap_top + size > __memtop) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return (void *)0;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> </span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> __heap_top += size;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> return (void *) prev_heap_top;</span><br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">void sys_sleep() {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> for(;;){</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> // ARMv6 Wait For Interrupt (WFI)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> uint32_t * reg = 0;</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> __asm__ __volatile__ ("MCR p15,0,%[t],c7,c0,4" :: [t] "r" (reg));</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com2tag:blogger.com,1999:blog-9184145065528610199.post-63913158658627408702011-12-11T18:08:00.001+01:002011-12-14T10:50:43.150+01:00Developing a multitasking OS for ARM part 2Okay, kids, gather around and we'll carry on where we left off.<br />
<br />
Now, we have the ARM booting, jumping to a reset handler, and dropping into an endless loop. That's a pretty good start. But really, we'd like to do something more - well - how to put this - "more".<br />
<br />
In order to do this, we need to have a bit more understanding about how the ARM itself works.<br />
<br />
If we go to the ARMv7AR Architecture Reference Manual (which can be had by registering at arm.com, or by downloading a hooky copy off the internets, either approach is feasible, and one at least of which is recommended), we see, in section B1 (the System Level Programmer's Model) a certain amount of interesting reading. Forget the "privilege" aspect for the moment, and let's skip ahead to section B1.3.<br />
<br />
We find that the processor has 8 separate operating modes. These are:<br />
<br />
User Mode, System Mode, Supervisor Mode, Monitor Mode, Abort Mode, Undefined Mode, IRQ Mode, and FIQ Mode<br />
<br />
If we look back at the set of vectors we set up earlier, a lot of these "cross over". So when we drop into the IRQ vector, we will be in IRQ mode. FIQ, FIQ mode. Either of the aborts, Abort mode. Undefined instruction, undefined mode, and so on. What's interesting is how the machine registers are shared between modes, and particularly the fact that all but system/user modes have their own stack pointers.<br />
<br />
Now, when the ARM starts up, it is in SVC mode. That's the way it is, and you can't change that. And when it starts up, <i>no stack has been defined</i>. So you need to be really damned careful in the first bits of the reset code.<br />
<br />
Stacks on the ARM grow downwards, so the best thing to do generally is to put them at the top of memory. As such, a typical reset routine will start by finding out how much memory is available, then setting up stack pointers for each of the operating modes. We're nothing if not typical, so let's look at how we do that.<br />
<br />
First thing - sizing memory. On the versatile baseboard as emulated by qemu, this is easy. We try writing to a bit of memory, then read back - if the value is set, there's memory there, if there's not, then we are above the top of memory. It's not quite so simple on the Pi, as trying to write outside of physical RAM will cause an exception. However, we're going to be a bit clever, and try to kill 2 birds with one stone.<br />
<br />
Firstly, we need to set up some big fat global variables.<br />
<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">.global<span class="Apple-tab-span" style="white-space: pre;"> </span>__memtop</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__memtop:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>0x00400000<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Start checking memory from 4MB */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global<span class="Apple-tab-span" style="white-space: pre;"> </span>__system_ram</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__system_ram:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>0x00000000<span class="Apple-tab-span" style="white-space: pre;"> </span>/* System memory in MB */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global<span class="Apple-tab-span" style="white-space: pre;"> </span>__heap_start</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__heap_start:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_end__<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Start of the dynamic heap */</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global __heap_top</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__heap_top:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_end__<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Current end of dynamic heap */</span><br />
<div>
<br /></div>
<div>
__bss_end__ is set up by the linker, and it would be much better of me to use that for the initial value of __memtop (rounded up to the nearest megabyte) as well. But hey, I'm lazy. It'll come back to bite me later, I'm sure.</div>
<div>
<br /></div>
<div>
Now, as the Pi causes an exception on writes outside memory, we need to patch in a handler, temporarily. Here's the handler:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* temporary data abort handler that sets r4 to zero */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* this will force the "normal" check to work in the */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* case (as, I believe, on RasPi) where access 'out */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* of bounds' causes a page fault */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">temp_abort_handler:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>r4, #0x00000000</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>lr, lr, #0x08</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>movs<span class="Apple-tab-span" style="white-space: pre;"> </span>pc, lr</span></div>
</div>
<div>
<br /></div>
<div>
Note how the comment indicates I'm not absolutely sure this will work. This is, frankly, because <i>I'm not sure if this will work on a real Pi</i>, and nobody wants to let me get my hands on one. Still, let's pretend, eh?</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* This tries to work out how much memory we have available<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* Should work on both Pi and qemu targets<span class="Apple-tab-span" style="white-space: pre;"> </span>*/</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">FUNC<span class="Apple-tab-span" style="white-space: pre;"> </span>_size_memory</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* patch in temporary fault handler */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r5, =.Ldaha</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r5, [r5]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r6, [r5]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r7, =temp_abort_handler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r7, [r5] </span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>DMB<span class="Apple-tab-span" style="white-space: pre;"> </span>r12</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Try and work out how much memory we have */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, .Lmemtop</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, .Lmem_page_size</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, [r1]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, .Lsystem_ram</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Lmem_check:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, r3, #0x04</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r3]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Try and store a value above current __memtop */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>DMB<span class="Apple-tab-span" style="white-space: pre;"> </span>r12<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Data memory barrier, in case */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r4, [r3]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Test if it stored */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, r4<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Did it work? */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bne<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lmem_done</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>add<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, r3, r1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Add block size onto __memtop and try again */<span class="Apple-tab-span" style="white-space: pre;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>b<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lmem_check</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Lmem_done:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r0]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* get final memory size */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>lsr<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, #0x14<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Get number of megabytes */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r3, [r2]<span class="Apple-tab-span" style="white-space: pre;"> </span>/* And store it */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* unpatch handlers */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r6, [r5]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>DMB<span class="Apple-tab-span" style="white-space: pre;"> </span>r12</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bx<span class="Apple-tab-span" style="white-space: pre;"> </span>lr</span></div>
</div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"></span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Lmemtop:</span></div>
<span style="font-family: 'Courier New', Courier, monospace;">
<div>
.extern __memtop</div>
<div>
.word<span class="Apple-tab-span" style="white-space: pre;"> </span>__memtop</div>
<div>
<br /></div>
<div>
.Lmem_page_size:</div>
<div>
.extern __mem_page_size</div>
<div>
.word __mem_page_size</div>
<div>
<br /></div>
<div>
.Lsystem_ram:</div>
<div>
.extern __system_ram</div>
<div>
.word __system_ram</div>
<div>
<br /></div>
<div>
<div style="font-family: Times;">
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.Ldaha:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.extern<span class="Apple-tab-span" style="white-space: pre;"> </span>data_abort_handler_address</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.word<span class="Apple-tab-span" style="white-space: pre;"> </span>data_abort_handler_address</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
</div>
</div>
</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;">We see a few things here. Firstly, how to patch in and out the handler. Also, that I've got fed up with doing the whole .code 32; .global foo; foo: rigmarole and defined a macro called FUNC. We also see a macro called DMB, which implements the ARMv6 Data Memory Barrier (ARMv7 has a 'dmb' instruction, to do that, we don't). For what it's worth, these are the macros:</span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.macro FUNC name</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.text</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.code 32</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global \name</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">\name:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.endm</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* Data memory barrier */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">/* pass in a spare register */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.macro DMB reg</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>\reg, #0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mcr<span class="Apple-tab-span" style="white-space: pre;"> </span>p15,0,\reg,c7,c10,5<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Data memory barrier on ARMv6 */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.endm</span></div>
<div style="font-family: Times, 'Times New Roman', serif;">
<br /></div>
<div style="font-family: Times, 'Times New Roman', serif;">
So, we can hopefully now find out how much memory we have, with __memtop containing the actual top of memory and __system_ram containing the number of megabytes in case it's useful to know.</div>
</div>
<div style="font-family: Times, 'Times New Roman', serif;">
<br /></div>
<div style="font-family: Times, 'Times New Roman', serif;">
So let's look at the start of _reset...</div>
<div style="font-family: Times, 'Times New Roman', serif;">
<br /></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ MODE_BITS, 0x1F<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Bit mask for mode bits in CPSR */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ USR_MODE, 0x10<span class="Apple-tab-span" style="white-space: pre;"> </span> /* User mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ FIQ_MODE, 0x11<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Fast Interrupt Request mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ IRQ_MODE, 0x12<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Interrupt Request mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ SVC_MODE, 0x13<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Supervisor mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ ABT_MODE, 0x17<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Abort mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ UND_MODE, 0x1B<span class="Apple-tab-span" style="white-space: pre;"> </span> /* Undefined Instruction mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.equ SYS_MODE, 0x1F<span class="Apple-tab-span" style="white-space: pre;"> </span> /* System mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">FUNC<span class="Apple-tab-span" style="white-space: pre;"> </span>_reset</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Do any hardware intialisation that absolutely must be done first */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* No stack set up at this point - be careful */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, =.Lsize_memory</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, [r0]</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cmp<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, #0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>blxne<span class="Apple-tab-span" style="white-space: pre;"> </span>r0</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Assume that at this point, __memtop and __system_ram are populated</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Let's get on with initialising our stacks */</span></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mrs<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, cpsr<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Original PSR value */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, __memtop<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Top of memory */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bic<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, r0, #MODE_BITS<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Clear the mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>orr<span class="Apple-tab-span" style="white-space: pre;"> </span>r0, r0, #IRQ_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Set IRQ mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>msr<span class="Apple-tab-span" style="white-space: pre;"> </span>cpsr_c, r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Change the mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>sp, r1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* End of IRQ_STACK */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Subtract IRQ stack size */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, __irq_stack_size</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sbc<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, r1, r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bic r0, r0, #MODE_BITS<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Clear the mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>orr r0, r0, #SYS_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Set SYS mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>msr cpsr_c, r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Change the mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov sp, r1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* End of SYS_STACK */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Subtract SYS stack size */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, __sys_stack_size</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sbc<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, r1, r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bic r0, r0, #MODE_BITS<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Clear the mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>orr r0, r0, #FIQ_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Set FIQ mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>msr cpsr_c, r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Change the mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov sp, r1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* End of FIQ_STACK */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Subtract FIQ stack size */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, __fiq_stack_size</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sbc<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, r1, r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bic r0, r0, #MODE_BITS<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Clear the mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>orr r0, r0, #SVC_MODE<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Set Supervisor mode bits */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>msr cpsr_c, r0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Change the mode */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov sp, r1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* End of stack */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* And finally subtract Kernel stack size to get final __memtop */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>r2, __svc_stack_size</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sbc<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, r1, r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>str<span class="Apple-tab-span" style="white-space: pre;"> </span>r1, __memtop</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/*-- Leave core in SVC mode ! */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Zero the memory in the .bss section. */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov <span class="Apple-tab-span" style="white-space: pre;"> </span>a2, #0<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Second arg: fill value */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>mov<span class="Apple-tab-span" style="white-space: pre;"> </span>fp, a2<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Null frame pointer */</span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"><span style="font-family: 'Courier New', Courier, monospace;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>a1, .Lbss_start<span class="Apple-tab-span" style="white-space: pre;"> </span>/* First arg: start of memory block */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr<span class="Apple-tab-span" style="white-space: pre;"> </span>a3, .Lbss_end<span class="Apple-tab-span" style="white-space: pre;"> </span></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>sub<span class="Apple-tab-span" style="white-space: pre;"> </span>a3, a3, a1<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Third arg: length of block */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>bl<span class="Apple-tab-span" style="white-space: pre;"> </span>memset</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr r2, .Lc_entry<span class="Apple-tab-span" style="white-space: pre;"> </span>/* Let C coder have at initialisation */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> mov lr, pc</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> bx r2</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsie<span class="Apple-tab-span" style="white-space: pre;"> </span>i<span class="Apple-tab-span" style="white-space: pre;"> </span>/* enable irq */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cpsie<span class="Apple-tab-span" style="white-space: pre;"> </span>f<span class="Apple-tab-span" style="white-space: pre;"> </span>/* and fiq */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Initialisation done, sleep */</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>ldr r2, .Lsleep</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> mov lr, pc</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> bx r2</span></div>
</div>
</div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"></span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<span style="font-family: 'Courier New', Courier, monospace;">
<div>
<div>
.Lbss_start:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_start__</div>
<div>
.Lbss_end:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>__bss_end__</div>
.Lc_entry:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>c_entry</div>
<div>
.Lsleep:<span class="Apple-tab-span" style="white-space: pre;"> </span>.word<span class="Apple-tab-span" style="white-space: pre;"> </span>sys_sleep</div>
<div>
<br /></div>
</span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;">Note the use of </span><span style="font-family: 'Courier New', Courier, monospace;">msr cpsr_c, rx</span><span style="font-family: Times, 'Times New Roman', serif;"> - this is how we change mode. We can change mode this way from any mode <i>except</i> user mode. Luckily, the user mode stack pointer is shared with system mode, so we don't need to drop into user mode at all. So we go off, find how much memory we have, then for certain of the operating modes, we set up a stack pointer. We then use a pre-written implementation of </span><span style="font-family: 'Courier New', Courier, monospace;">memset()</span><span style="font-family: Times, 'Times New Roman', serif;"> to zero out the bss section, let the 'c' code have a go at initialising its stuff via </span><span style="font-family: 'Courier New', Courier, monospace;">c_entry()</span><span style="font-family: Times, 'Times New Roman', serif;">, turn on interrupts, and go to sleep via </span><span style="font-family: 'Courier New', Courier, monospace;">sys_sleep()</span><span style="font-family: Times, 'Times New Roman', serif;">.</span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;"><br /></span></div>
<div>
<span style="font-family: Times, 'Times New Roman', serif;">Next up, how we go about doing useful work...</span></div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-52042432763218260452011-12-07T10:11:00.001+01:002011-12-07T10:54:03.390+01:00Developing a multitasking OS for ARM part 1My Scheme OS for the <a href="http://www.raspberrypi.org/">Raspberry Pi SBC</a> is coming along nicely (code at https://gitorious.org/lambdapi), and a couple of comments on the Raspberry Pi forum kinda kicked me into actually documenting some of the process of what I've been doing. So, here goes.<br />
<br />
Firstly, the toolset.<br />
<br />
The first thing we'll be needing is development tools. Yeah, there's "off the peg" toolsets available, but I wanted to be up at the bleeding edge. So, off to GNU's site, and let's get cracking.<br />
<br />
I built and installed the latest versions of libtools (which includes the assembler and linker), gcc, g++, newlib and gdb, all for target arm-none-eabi. If you want to know how to do this, googling "arm bare metal" should elucidate. Otherwise, there's always codesourcery.<br />
<br />
Now, booting. Obviously, the first thing we need to do is boot the board. In my case, it's very uncomplicated. No first-stage booters, no relocating stuff from flash, just a bunch of RAM that your binary gets loaded into, starting at address 0x00000000. Easy peasy.<br />
<br />
So. How does ARM (specifically, the ARM1176jzf-s processor on the Raspberry Pi) boot? Well, there's chapter and verse on the <a href="http://infocenter.arm.com/">ARM site</a>, but here's the TL;DR version.<br />
<br />
<i>When the ARM powers on, it executes ARM (32 bit) instructions starting from address 0x00000000. </i><br />
<br />
Simples, right? Well, not quite. Address 0x00000000 is the start of what's known as the exception vector table, which contains 8 bytes for each of 8 potential exceptions. 8 bytes (or 2 words) is enough to store an absolute jump instruction, or an instruction to move an address from memory into the program counter. So the simplest vector table would look like this:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">.section .reset</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.code 32</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global __reset</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__reset:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _reset @ Power on reset</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _undef @ Undefined instruction</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _swi @ Software interrupt</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _prefetch_abort @ Prefetch Abort</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _data_abort @ Data abort</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b . @ Unused</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _irq @ IRQ</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _fiq @ "fast interrupt"</span><br />
<br />
And that would be fine. However, that's not how it's normally done, mainly because it's impossible, with this setup, to change the vectors on the fly. So what we do is this:<br />
<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">.section .reset, "ax"</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.code 32</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global __reset</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">__reset:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _reset_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _undef_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _swi_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _prefetch_abort_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _data_abort_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b .</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> ldr pc, _irq_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _fiq</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_fiq:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> @ Fast interrupt handler starts here</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _no_handler</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _no_handler</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_no_handler:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> b _no_handler</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_reset_address: .word _reset</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_undef_address: .word _undef</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_swi_address: .word _swi</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_prefetch_abort_address: .word _prefetch_abort</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_data_abort_address: .word _data_abort</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">_irq_address: .word _irq</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _reset_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _undef_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _swi_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _prefetch_abort_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _data_abort_address</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">.global _irq_address</span><br />
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.weak _undef</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.set _undef, _no_handler</span></div>
</div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.weak _prefetch_abort</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.set _prefetch_abort, _no_handler</span></div>
</div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.weak _data_abort</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.set _data_abort, _no_handler</span></div>
</div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global _reset</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">_reset:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> b _no_handler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global _swi</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">_swi:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> b _no_handler</span></div>
</div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">.global _irq</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">_irq:</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;"> b _no_handler</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br /></span></div>
<div>
<br /></div>
<br />
That's loads bigger, but what does it change, exactly?<br />
<br />
The "fast interrupt" code gets to miss an indirection, so it's faster. We simply start the interrupt handler directly at the end of the vector table. I'm not actually doing this at the moment, but it's possible.<br />
<br />
The other exceptions load their address from an indirection table, so we can repatch them on the fly.<br />
<br />
We have a "generic" handler for unhandled exceptions. The way that gets patched in is to do with the linker. A .weak directive for a symbol will allow us to simply not define a symbol in our code, and the linker will replace it with zero instead of barfing. The .set directive enables us to use a different default to zero. Thus, any of the _undef, _prefetch_abort or _data_abort entry points (in the code above) will redirect to _no_handler unless we define those entry points elsewhere. This is a trick we'll use again later. Note _reset, _swi and _irq have no defaults, and thus must be defined elsewhere (I've defined them to simply jump to _no_handler for the moment.<br />
<br />
All we need to do is assemble that and link it to load at 0x00000000, and we have a booter. It will do bugger all, but it will work.tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com2tag:blogger.com,1999:blog-9184145065528610199.post-80115439949574682122011-10-19T21:29:00.000+02:002011-10-20T10:42:43.618+02:00Garbage collection for an SD/MMC-based persistent store<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">My Lisp/Scheme based OS is moving on apace. I've actually got a basic OS running on STM32, but it's feeling a bit cramped, and there's a new game in town - <a href="http://www.raspberrypi.org/">Raspberry Pi</a>. Raspberry Pi (or, to shorten it a bit, RasPi) is a credit-card sized ARM11 based machine intended for educational use. And it's cheap. Really, really, cheap. there's a few oddities to it; it's actually based on a Broadcom SoC that's, in reality, a top whack GPU with a sorta old-hat ARM core bolted on as a bit of an afterthought. As such, it boots "oddly", GPU first and then ARM, but hey. The board itself has no onboard flash; persistent storage is SD card only (or, I guess, USB mass storage).</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">As could probably be guessed, it's coming with Linux on board, but hey, who cares about Linux?</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Never one to make things easy on myself, I've expanded the scope of my OS. The Lisp/Scheme core is still there, the concept of syscalls as closures, all that good stuff. But I keep coming back to the Newton. Ah, my beloved NewtonOS. A totally persistent OS, one that takes power failures and years sitting in a drawer in its stride, a system where you whack new batteries in and you're back <span style="font-style: italic;">exactly</span> where you were almost the moment you've let go of the power toggle switch. This is exactly what <a href="http://www.loper-os.org/">Stanislav</a> is talking about in his <a href="http://www.loper-os.org/?p=231">third law of sane computing</a>.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<div>
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So. Persistence, then. How's that gonna work? </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><i>Before we start, I should note that the following technical stuff is nothing to do with wear levelling (which task is carried out quite adequately by the onboard controller of the SD card).</i></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">We have a quantity of RAM (256MB in the case of the Pi) which we want to use as a read / write cache for a larger quantity of persistent storage. In this case, Flash memory accessed through an SD/MMC card interface.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">We could take a naïve approach, and simply page stuff in and out, but there is a significant performance overhead, particularly with flash memory. Not only are writes to flash slow, but you can only write to a block once, and then it needs to be erased before you write again. And erasing is <i>really</i> slow.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Any given SD card is split into a number of sectors (typically between 512 bytes and 2K long). A sector is the smallest unit we can read. Those sectors are grouped into erase groups (typically in the 128KB - 2MB range). An erase group is the smallest unit we can erase. We can write to a sector, but if we try to write to it twice, the entire erase group has to be erased and the old contents (plus the new contents of our sector) written back. This is a positively <i>glacial</i> operation.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">If we take a sane approach, we block everything at the erase group size, and control when (and how) we write back to the card. If we take the approach of writing data back to a different erase group, we can put off the pain of erasing the old one, and do it at our (or the card's) leisure.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Now, as we don't know exactly where an erase group will be paged into memory (and we can't restrict it to a specific location, as the card storage is potentially bigger than real memory), we have to use an indirect addressing method, using a "logical erase group number" (which can't be the actual erase group number, as that will change underneath us) and an index or address into the block of memory. This adds some overhead to pointer dereferencing, of course, but it's mainly done using shifts and masks; dropping to assembler to do this should make it at least tolerable.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The bigger pain is garbage collection. </span><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Lisp and Scheme are garbage collected languages, and we need a garbage collector that doesn't hurt us. </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">At this point, I should probably set out some requirements for garbage collection:</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<br />
<ul>
<li><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-size: x-small;">It should reclaim as much memory as possible (duh)</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-size: x-small;">It should not require paging in gigabytes of memory (that costs potentially enormous amounts of time).</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-size: x-small;">It should never (if possible) force data to be written back to storage (which would be worse than paging in).</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-size: x-small;">It should (if possible) be concurrent with application usage.</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-size: x-small;">It should have a bounded worst case time per cycle (Java, I'm looking at you)</span></span></li>
</ul>
<br />
<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">A traditional garbage collector is gonna hurt us plenty. Why is that?</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The way most garbage collectors work is by tracing from a group of accessible objects to find all objects in the heap that are addressable. These addressable objects are then copied somewhere "safe", and the rest thrown away. That's pretty much the gist of it (there are various complications, but the reader is referred to <a href="http://www.amazon.fr/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484">the relevant literature</a> for further detail).</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Now, that whole "copying" thing means that, for every garbage collection cycle, the erase group(s) containing the "live" objects will have to be written back to the SD card, whether the objects themselves have changed or not. Ouch.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">But surely, you say, there exists a way of collecting garbage <i>without</i> moving objects around? As it happens, dear reader, there does. <a href="http://www.pipeline.com/~hbaker1/NoMotionGC.html">H.G. Baker's "Treadmill" non-copying garbage collector</a> is a particularly good (and easy to code) example. It comes with a certain amount of hurt itself, but it gets rid of the copying requirement, and that's a good start.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The main hurt of Baker's treadmill is the requirement to hold every object in a doubly-linked list. For a lisp implementation where objects generally look like this:</span><br />
<code><br /></code><br />
<code>struct cell { </code><br />
<code> uint32_t car;</code><br />
<code> uint32_t cdr;</code><br />
<code>};</code><br />
<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">adding in the doubly-linked list produces this, which has twice the storage requirement:</span><br />
<code><br /></code><br />
<code>struct cell { </code><br />
<code> struct cell * next; </code><br />
<code> struct cell * prev; </code><br />
<code> uint32_t car; </code><br />
<code> uint32_t cdr; </code><br />
<code>};</code><br />
<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Ouch, again. But hey, memory's cheap, and we're doing this in order to use RAM as a window on the bigger, persistent store - not really an issue. It should be noted that the structure above is only indicative; the links don't need to be persisted and can be kept separate of the actual cell contents. The overhead, of course, remains the same.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The other hurt is not to do with Baker's algorithm, but is more general - GC tends to want to access <i>all</i> your heap. And when your heap is feasibly orders of magnitude larger than real memory, that's gonna cause a load of thrashing.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So I started with the idea of not GCing non-swapped-in erase groups. Do your garbage collection on what you have in memory at the time, don't try and pull in any non-swapped-in erase blocks, and leave it at that - the other erase groups will get GCed when they eventually get swapped back in. Great, said I, coded about half of it up, and went to bed. And then woke up in the middle of the night.</span><br />
<blockquote>
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><i>"What about objects in a swapped in erase group which are only pointed to by objects in erase groups that are not swapped in? How the hell do I distinguish them from free objects if I don't know where they come from, or even that they are being pointed to?"</i></span></blockquote>
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"> Ah, <b>tits!</b></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Yep, if we're doing things in a naive way, but not swapping in every erase group as we traverse, we're gonna lose objects, and corrupt structures that are partially swapped in.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">We need to get clever.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Firstly, let's stick with the idea of erase groups, and not garbage collecting the "world". Indeed, let's not even try collecting our entire heap, we can restrict ourselves to a single erase group, or even a single sector if we like. All we have to do is decide not to follow links outside the (relatively) little block of memory we're looking at. We take our set of system roots, for every one that's in our block, we trace its links until we get to leaves or a link outside the block. The rest is totally normal as per Baker's algorithm. </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">By restricting ourselves to a single block of memory, we can obviate the need to have a full doubly-linked list for our entire heap; all we need is a doubly linked list for the block we're currently collecting, and that can be generated trivially at the beginning of the GC. This buggers the simplicity of allocating under Baker (which is a dereference and pointer increment), but rather than holding a full list all we need to hold is a bitmap.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Still, that hasn't solved the issue of links into our collected block.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">As it turns out, the solution to that is incredibly simple, and falls back to one of the oldest forms of garbage collection - reference counting. Along with our cell data, we carry a reference count variable, which counts the number of times a cell is referenced by cells outside the block. This looks a bit like this:</span><br />
<br />
<code>struct cell { </code><br />
<span class="Apple-style-span" style="font-family: monospace;"> uint32_t car; </span><br />
<code> uint32_t cdr; </code><br />
<code> uint16_t refcount;</code><br />
<code>};</code><br />
<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">If we create a cross-block link, we increment the reference count, if we destroy one (either by explicitly removing the link in code, or by freeing the referencing object during a garbage collection), we decrement it. As part of building our list of root objects, we scan the block for those objects with a non-zero refcount, and push those direct into the list of roots.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Now, maintaining refcounts is a pain in the ass, but with the granularity of allocation blocks we're talking about here (between 128KB and 2MB, remember), the number of cross-block references are liable to be very small. We can help this by preferring allocation of new objects in the block their "owner" inhabits (which will also help reduce object scattering, and thus paging issues).</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So. what does the solution look like?</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Firstly, we have some basic types:</span><br />
<br />
<span class="Apple-style-span" style="font-family: monospace;">typedef struct cell {</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> uint32_t car;</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> uint32_t cdr;</span><br />
<span class="Apple-style-span" style="font-family: monospace;">} cell_t;</span><br />
<span class="Apple-style-span" style="font-family: monospace;"><br /></span><br />
<span class="Apple-style-span" style="font-family: monospace;">typedef struct reference_count {</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> uint16_t colour:1; // indicator for gc, see Baker</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> uint16_t count:15;</span><br />
<span class="Apple-style-span" style="font-family: monospace;">} reference_count_t;</span><br />
<span class="Apple-style-span" style="font-family: monospace;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Some calculations:</span><br />
<br />
<span class="Apple-style-span" style="font-family: monospace;">// Every erase group must store :</span><br />
<span class="Apple-style-span" style="font-family: monospace;">// n cells (8 bytes each),</span><span class="Apple-style-span" style="font-family: monospace;"> n refcounts (2 bytes each) </span><br />
<span class="Apple-style-span" style="font-family: monospace;">// and n / 32 free cell bitmaps (4 bytes each)</span><br />
<span class="Apple-style-span" style="font-family: monospace;">#define CELLS_PER_BLOCK (erase_group_size * 8) / (64 + 16 + 1)</span><br />
<span class="Apple-style-span" style="font-family: monospace;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Therefore cell storage within an erase group looks like this (it's not actually defined like this, as CELLS_PER_BLOCK is dynamically calculated based on actual card characteristics):</span><br />
<br />
<span class="Apple-style-span" style="font-family: monospace;">cell_t cells[CELLS_PER_BLOCK];</span><br />
<span class="Apple-style-span" style="font-family: monospace;">reference_count_t refcounts[CELLS_PER_BLOCK];</span><br />
<span class="Apple-style-span" style="font-family: monospace;">uint8_t bitmaps[CELLS_PER_BLOCK];</span><br />
<span class="Apple-style-span" style="font-family: monospace;"><br /></span><br />
<div>
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The garbage collection algorithm is thus (using a single, transient, doubly linked list for CELLS_PER_BLOCK elements) :</span></div>
<div>
<br /></div>
<div>
<span class="Apple-style-span" style="font-family: monospace;">- For each cell in the erase group</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - if cell is in set of root objects, or has a refcount != 0, add to "grey" objects</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - else add to "ecru" objects</span><br />
<span class="Apple-style-span" style="font-family: monospace;">- Do Baker's treadmill algorithm, restricting ourselves to intra-block links</span><br />
<span class="Apple-style-span" style="font-family: monospace;">- For each free object</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - set "free" indicator in bitmaps</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - if object has extra-group link(s)</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - decrement refcount(s) on externally referenced groups (may require paging)</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - reinitialize to NIL . NIL or similar</span><br />
<span class="Apple-style-span" style="font-family: monospace;"> - flag group as "dirty"</span><br />
<span class="Apple-style-span" style="font-family: monospace;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">And that's about it. Allocating involves finding a free cell in the relevant erase group (made relatively easy using ARM's CLZ operator), assignment has to check for cross-erase-group links.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Note that the only time garbage collection will require the erase group to be flushed back to storage is in the (rare) case where we free a cell that has extra-group links. The "free" bitmap may be out of date on loading a group from flash, but it will never indicate that a non-free cell is free (allocation of a cell will update the bitmap to indicate the non-free status of that cell, and require a flush). The bitmap will be updated on the first gc cycle for the group, at which point it should be up-to-date.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">As an added bonus, as long as everything is persisted, suspending a process is simply a case of incrementing the reference counts of all its root objects and stopping the process. Starting it again is decrementing those counts, and you're back to <i>exactly where you were.</i></span><br />
<i><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br /></span></i><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">How d'ya like them apples?</span></div>
</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com1tag:blogger.com,1999:blog-9184145065528610199.post-76626889383413635452010-12-17T18:01:00.000+01:002011-12-07T20:02:52.783+01:00TiVo^H^H^H^HAndroidizationA few years back there was a big hoo-hah in the open source world, and it was at least partially responsible for the creation of the GPLv3. That hoo-hah was the <i>TiVoization</i> of the Linux kernel.<br />
<div>
<br /></div>
<div>
In short, what happened was this:</div>
<div>
<br /></div>
<div>
TiVo, inc. created their famous PVR device, which took the world (especially the geek world) by storm. At the heart of the device was a bunch of GPL software, including the Linux kernel. This later fact was, IMO, a large part of <i>why</i> TiVo took the geek world by storm, but that's another argument.</div>
<div>
<br /></div>
<div>
TiVo did what any good company using GPLed software should do - they delivered the source of their modifications to the GPLed software, and kept their non-GPLed software scrupulously away from the GPLed stuff. </div>
<div>
<br /></div>
<div>
So far, so good, right? Wrong.</div>
<div>
<br /></div>
<div>
Whilst it was possible for anyone to recompile their own version of the TiVo firmware, it was <i>not</i> possible to flash that recompiled firmware onto a TiVo branded device. The firmware images used to flash the TiVo were cryptographically signed, and the means to do that was not public. There were, of course, good reasons for this, not least of which was that the media companies would have, legally speaking, shat upon TiVo, inc. from a great height if it were not so.</div>
<div>
<br /></div>
<div>
There was much oohing and aahing from the GPL advocates over this, and it was generally decided that this was somehow wrong, and it was going to kill the GPL, and other such crap. And thus was born the GPLv3, which "protected" not only the software, but also the hardware it was designed to run on. Linus and the other kernel developers, who saw little wrong with what TiVo had done, decided to stick with the old GPLv2 anyway, and to hell with V3. </div>
<div>
<br /></div>
<div>
Fast forward a few years. The Linux kernel has not died. The GPL has not died. But now there <i>is</i> a threat to the GPL, and it is attacking both v2 and v3. It's a real and present danger, and it's being ignored (at best) or cheered on (at worst). That threat has a name. Its name is <b><i>Android</i></b>.</div>
<div>
<br /></div>
<div>
It's not Android as such that is the threat, but the market in which it is being used - mobile devices. An open system is anæthema to the hermetically closed world of mobile phones and telecoms carriers. Android is being claimed as the saviour of the open source world from the big bad ogres at Apple and MS. I believe this claim is wrong.<br />
<br />
Even Google aren't being the open source heros they are claimed. The (non-GPL parts of the) source for Android 4.x (Ice Cream Sandwich) was released months after the first devices hit the street, and I'm not sure if the 3.x series has ever been made public.<br />
<br />
Telephony providers are absolutely against people reflashing their devices (or even rooting them), and many mobiles are every bit as TiVoised as the original TiVo. And that inability to reflash is being used as a marketing device by the providers / manufacturers. "Benefit from Android x.x", they trumpet, "get yourself a new contract with handset / tablet X.1", quietly ignoring the fact that handset / tablet X.0 could quite happily run Android x.x should they bother to take a little time to provide a firmware upgrade. And yet Apple are "evil", and "push you to consume", although they have a policy of supporting hardware for a decent amount of time. No, Apple are evil because they are "closed source", and to avoid that we'll happily get fucked up the arse by someone waving a GPL banner.<br />
<br />
But the worst, the absolute worst, of the lot, are the Chinese manufacturers of cheap Android enabled devices, motherboards, and chipsets. It is absolutely impossible to get them to release the slightest piece of source code, despite the fact they are obliged to do so.<br />
<br />
Android is nothing more than a system for pushing ads to your mobile device. It's nothing to do with freedom, unless you're talking about Google's freedom to rape your private data. The telephony providers are using it because it costs them jack shit. Nothing to do with consumer benefit, nothing to do with freedom, simple bottom line accounting. The Chinese manufacturers are using it for the same reason, and because MS have got harder on hooky copies of WinCE.<br />
<br />
None of them give a flying fuck about "freedom", but between them, they may bring the GPL down.</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-40578744776597231772010-12-17T14:41:00.000+01:002010-12-17T15:10:15.512+01:00How good is your hashing?<div>As promised in my last post, I'm working on an embedded lisp-based OS. Yeah, <i>another</i> one. Because what the world really needs is yet another geek's idea of what an OS should look like.</div><div><br /></div><div>Well, fuck the world, I'm scratching an itch.</div><div><br /></div><div>Now, if I were being sensible, I'd target something usable, like my Wits A81 tablet device. A little lispy tablet could be really neat (and, indeed, it may well end up being so). However, I decided to start a bit smaller.</div><div><br /></div><div>A lot smaller, actually.</div><div><br /></div><div>Yep, a lisp-based OS on a microcontroller. Not, I might add, the st8ms this blog originally started with (and is titled as), but it's bigger brother, the stm32. It's an ARM Cortex-M3 processor, and the one I have in hand has 128K of flash and 8K of RAM, which is quite nifty.</div><div><br /></div><div>Now, anything that's gonna fit into that little space is gonna have to be tight. Sure, I can push as much code as possible into flash and execute from there, but that 8K is a really tight limit for something like a Lisp, even a cut down one. And so, I started thinking about what takes up lots of space in lisp. </div><div><br /></div><div>Firstly, there's objects. A naive implementation of boxed objects in Lisp means that even the humblest character takes up a significant amount of space, with 24 bytes not being unheard-of. Well, bollocks to that. I'm being as tight as I can.</div><div><br /></div><div>Once you've squeezed stuff like characters and numbers and so on down, though, you start looking at what you can get shot of. Symbols, for example. They are used as unique identifiers, and ar generally stored as a hash value and a literal string. Now, the hash value is what's used most of the time, and the string is only really used when "exploding" the symbol out into an array of characters. So if I'm willing not to do that, I can get away with *just* holding the hash. That's a significant saving.</div><div><br /></div><div>So. What hash to use?</div><div><br /></div><div>I need something that can be pushed into a single word of space (4 bytes), and which will allow me to detect collisions. By which I mean that if "a" and "b" resolve to the same hash value, I need to be able to tell. The first bit is easy enough, but the second is hard as nails</div><div><br /></div><div>A google for hashing algorithms will generally end up pointing you to Dan Bernstein's venerable djb2. Unfortunately, it's not really very good, and it certainly doesn't handle the second case. For that, what I need is an algorithm that pushes out *two* hash values, a primary and a secondary.</div><div><br /></div><div>Enter <a href="http://burtleburtle.net/bob/c/lookup3.c">Bob Jenkins' 'lookup3.c', particularly 'hashlittle2()'</a>. This is a rather nice hashing algorithm that throws out a pair of hash values, has very good characteristics, and runs fast.</div><div>But, oh noes! Compiling it for the STM32 results in over 1K of code. Surely we can do better than that? Yes, we can.</div><br /><code>.global hash<br />.type hash, %function<br />.align 2<br />@ Hash Function<br />@ Thumb-2 implementation of 'hashlittle2' by Bob Jenkins.<br />@ In : R0 -> pointer to string<br />@ R1 -> length of string<br />@ R2 -> Initial value for 'hash c'<br />@ R3 -> Initial value for 'hash b'<br />@ Out : R0 -> 'hash c', the main hash value<br />@ R1 -> 'hash b', the secondary hash value<br />@ Clobbers R2, R3, flags <br />hash: push {r4-r7,lr}<br /> @ Within the function, we use registers as follows:<br /> @ r1 : length<br /> @ r2-r4 : temporary for character loading<br /> @ r5-r7 : a, b, c<br /> <br /> @ initial setup<br /> adr r7, hash_constant @ a = b = c = 0xdeadbeef + length + hash c<br /> ldr r7, [r7]<br /> adds r7, r1<br /> adds r7, r2<br /> mov r5, r7<br /> mov r6, r7<br /> adds r7, r3 @ c += hash b<br /> <br />hash_loop:<br /> cmp r1, #0x0c @ Is r4 <= 12?<br /> it le<br /> ble hash_tail @ If so, go do the tail part<br /> <br /> ldmia r0!, {r2, r3, r4} @ Load values<br /> adds r5, r2<br /> adds r6, r3<br /> adds r7, r4<br /> subs r1, #0x0c @ Subtract 12 from length<br /> <br /> @ Mix<br /> subs r5, r7 @ a -= c<br /> eor.W r5, r5, r7, ror #28 @ a ^= rot(c,4)<br /> adds r7, r6 @ c += b<br /> <br /> subs r6, r5 @ b -= a<br /> eor.W r6, r6, r5, ror #26 @ b ^= rot(a,6)<br /> adds r5, r7 @ a += c;<br /> <br /> subs r7, r6 @ c -= b; <br /> eor.W r7, r7, r6, ror #24 @ c ^= rot(b, 8); <br /> adds r6, r5 @ b += a;<br /> <br /> subs r5, r7 @ a -= c<br /> eor.W r5, r5, r7, ror #16 @ a ^= rot(c,16)<br /> adds r7, r6 @ c += b<br /> <br /> subs r6, r5 @ b -= a<br /> eor.W r6, r6, r5, ror #13 @ b ^= rot(a,19)<br /> adds r5, r7 @ a += c;<br /> <br /> subs r7, r6 @ c -= b; <br /> eor.W r7, r7, r6, ror #28 @ c ^= rot(b, 4); <br /> adds r6, r5 @ b += a; <br /> <br /> b hash_loop<br />hash_tail:<br /> cbz r1, hash_done @ length 0 requires no extra work<br /> <br /> ldmia r0!, {r2, r3, r4} @ Load values<br /> adr r0, do_hash_mask<br /> add r0, r0, r1, lsl #2<br /> <br />do_hash_mask:<br /> mov.W pc, r0 @ doubles for count 0 entry in masking table, *must* be 4 bytes hence .W<br /> @ Here we mask off the bits we don't want according to <br /> @ what data we have<br /> bic r2, #0x0000ff00 @ count is 1, mask off all but least significant byte<br /> bic r2, #0x00ff0000 @ etc etc<br /> bic r2, #0xff000000 <br /> bic r3, #0x000000ff<br /> bic r3, #0x0000ff00<br /> bic r3, #0x00ff0000<br /> bic r3, #0xff000000<br /> bic r4, #0x000000ff<br /> bic r4, #0x0000ff00<br /> bic r4, #0x00ff0000<br /> bic r4, #0xff000000<br /> bic r4, #0x00000000<br /><br /> adds r5, r2 @ Add masked vales before final mix<br /> adds r6, r3<br /> adds r7, r4<br /> <br /> @ Final mix<br /> eors r7, r6 @ c ^= b<br /> sub r7, r7, r6, ror #18 @ c -= rot(b,14)<br /> eors r5, r7 @ a ^= c<br /> sub r5, r5, r7, ror #21 @ c -= rot(c,11)<br /> eors r6, r5 @ b ^= a<br /> sub r6, r6, r5, ror #7 @ b -= rot(a,25)<br /> eors r7, r6 @ c ^= b<br /> sub r7, r7, r6, ror #16 @ c -= rot(b,16)<br /> eors r5, r7 @ a ^= c<br /> sub r5, r5, r7, ror #28 @ c -= rot(c,4)<br /> eors r6, r5 @ b ^= a<br /> sub r6, r6, r5, ror #18 @ b -= rot(a,14)<br /> eors r7, r6 @ c ^= b<br /> sub r7, r7, r6, ror #8 @ c -= rot(b,24)<br /> <br />hash_done:<br /> mov r0, r7<br /> mov r1, r6<br /> pop {r4-r7, pc}<br /><br />hash_constant:<br /> .word 0xdeadbeef<br /><br />.ltorg<br /></code><br /><div>There you go. 206 bytes of hash function. There's probably a few bytes to shave off here and there, but it works pretty well.</div><div><br /></div><div>As it happens, I'm only using 30 bits of the main hash, with the lowest 2 bits being used to indicate type, in order that symbols fit completely into a single machine word.</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-78411711154931900542010-10-29T12:45:00.001+02:002010-10-29T16:52:50.024+02:00All modern operating systems are shite.<div>"Modern" operating systems are, to my eyes, fundamentally broken. Indeed, there's very little that's "modern" about them, when it comes down to it.</div><div><br /></div><div>They are seemingly all mired in the concept of being nothing more than a layer over hardware, something that allows single-purpose "applications" to access that hardware in a consistent manner. The focus is wholeheartedly on the applications, and not on the data those applications use.</div><div><br /></div><div>Admittedly, some of those systems are better than others. Apple's OSX is nice enough to use, mainly because it's decent enough to get out of the way when you need it to. But even so, it's conceptually no different to Microsoft's Win7, or even Vista, XP, Win2K (go back down the MS lineage as far as you want here) or any other "desktop" operating system - the only real distinguishing factor apart from what applications are compatible is how you get on with the UI. Personally, I find OSX tolerable, and Windows execrable, but that's personal preference, and not really much different to preferring a Ford over a Fiat.</div><div><br /></div><div>Even the handheld market, one which was all-but invented by Apples ground-breaking Newton, has taken masive steps backwards from the beauty and simplicity of Newton, or even the sparse functionalism of Palm; "handheld devices", say Jobs, Brin and Ballmer, "are for consumption of pre-rendered media". Forget using them as extensions of your computing environment, forget using them for anything useful (except, perhaps, as a poor replacement for a spirit level), they're there as status symbol, toy, and above all, conduit for advertising.</div><div><br /></div><div>Yeah, I keep coming back to the Newton. Funny, that.</div><div><br /></div><div>So, anyway, whilst fiddling with Android, and trying to make mobile devices actually useful again, and generally buggering about with my Wits A81, I've been doing a fair amount of thinking about this. And, indeed, I've been thinking about going further than that, and actually doing something about it.</div><div><br /></div><div>I started by thinking that something could be done by using the linux kernel as a starting point. After all, it's already developed, and it runs everywhere - why bother reinventing the wheel? Just make a performant "shim" OS over the top of it, and a file system that does what you want, and you're laughing.</div><div><br /></div><div>But that's suboptimal. Linux (the kernel) is tied to the Unix concept that "everything is a file". Which is a nice enough abstraction, but it doesn't work for me. The reason it doesn't work for me is that "a file" is far from being a rich enough concept. Part of this is to do with metadata (or, more particularly, the lack of it) - it's very difficult to implement interesting inter-application behaviour without metadata and (even more importantly) transparent, dynamic, access methods for that data and metadata.</div><div><br /></div><div>As an example, let's consider Apple's OSX, and the interaction between AddressBook.app, Mail.app and iCal.app. This is, pretty much, state of the (current) art - you send me an email suggesting a lunch date tomorrow at midday, I double click on the "midday" text and get a "lunch" appointment added to my calendar with you as an "attendee". Pretty damn slick. But all that interaction knows about is those 3 apps - it's hard-coded to only work between those three. This is because the processing is contained in the aplications, and not "owned" by the data. I can't make MyFunkyApp.app do this without linking to a bunch of Apple-provided frameworks (and even then, it's hard, as a lot of the behaviour is not externally exposed), and even when I do, Mail.app doesn't suddenly inherit the ability to do what MyFunkyApp.app does - the interaction only goes one way.</div><div><br /></div><div>We shouldn't be living in a world where metadata and behaviour is application specific. Developers should be developing behaviour, interfaces and transforms for specific data types, not reinventing the "application" over and over. Users should be able to edit an image directly in an email, and send it back to the sender, without having to save it, open it in anoother application, edit it there, save it again, then send it back. Data should be automatically versioned. It should follow you around. Your mobile device should be an extension of your desktop, able to take important data with you and merge changes back when you return, able to contact your machine over the 'net and fetch data you "forgot". And so on.</div><div><br /></div><div>Desktop computing hasn't advanced that much since 1984. There have been a few attempts to make things better, but they have, by and large, failed, at least if we measure success in a commercial sense. Newton was one of these. Computing has failed on several of its promises. We are slaves to the machine, not the other way around.</div><div><br /></div><div>It is clear to me, at least, that we need a change. And the idea has been buzzing around my head for some time. I had considered that much of this could be accomplished by layering something over the Linux kernel, with a metadata-storing file system backing everything up. The problem with this approach is that the two worlds can never be allowed to collide - Linux provides a hardware abstraction layer and nothing else. Everything else the kernel does, including scheduling, would be surplus to requirements. So why not, I thought to myself, develop an OS directly "on the metal" in a dynamic language, do it all from the ground up? After all, it's been done before. The <a href="http://en.wikipedia.org/wiki/Jupiter_Ace">Jupiter Ace</a> was a "home micro" which was coded purely in FORTH. The <a href="http://www.sts.tu-harburg.de/~r.f.moeller/symbolics-info/">Symbolics Lisp Machines</a> were coded, from the ground up, in Lisp.</div><div><br /></div><div>And that hooked me. I've always loved Lisp. It has a beauty which is transcendental, a purity of purpose which is unrivalled in any (non-Lisp) language that's come since. A lot of people get scared by the syntax, but then people get scared by the fact Objective-C uses square brackets and colons, so fuck 'em. Result - I started looking at Lisp-based OSes, to see if it had all been done before. And I found this:</div><div><br /></div><div><a href="http://bywicket.com/users/mikel/weblog/fbc2a/Closos.html">Closos</a></div><div><br /></div><div>Now, this started to tickle my interest. Not only was I not insane (or, at least, not insane and alone), but Mikel is one of the original guys on the Newton (<a href="http://lispm.dyndns.org/news?ID=NEWS-2004-08-14-1">and pre-Newton</a>) project at Apple. One of the guys who worked on <a href="http://en.wikipedia.org/wiki/SK8">SK8</a> at Apple. An insanely talented guy, who seemingly thinks much the same way as I do. Sure, it's not much further advanced than I am, but it at least shows I'm (possibly) not utterly wrong.</div><div><br /></div><div>So, I'm not mad. And I *am* gonna do this. Stop thinking, start acting.</div>tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-71936532119265721352010-07-31T09:56:00.001+02:002010-07-31T10:07:22.983+02:00OpenEmbedded under OSX.So, as a result of getting the little android tablet I mentioned before, I've been playing with OpenEmbedded. Unfortunately (for me), it's not supported (or at least not fully) under OSX - even getting the native tools up and running is painful. There's a *load* of gnu-isms in the source, which break strict POSIX compliance, and frankly make it a massive pain to get stuff working.<br /><br />Much of this can be got around by using precompiled stuff (either pulled from one of the OSX package repositories, fink etc, or, in my case, compiled manually), and then explicitly removed from the OE build system using ASSUME_PROVIDED.<br /><br />This doesn't fix a few overall issues, though, much of which comes from OE assuming it's built on a system that uses ELF as its binary format.<br /><br />A large part of this can be fixed with one patch, which I've attached here. $OEBASE/$CHECKOUT/classes/relocatable.bbclass tries to fix up the <span style="font-family:courier new;">rpath</span> in any binaries having it, but simply assumes all binaries are ELF format. Obviously, this crashes and burns horribly under OSX, where the runtime format for native binaries is Mach-O. Patch below, apply from $OEBASE/$CHECKOUT with patch -p1<br /><br /><pre><br />diff --git a/classes/relocatable.bbclass b/classes/relocatable.bbclass<br />index 2af3a7a..3a4c119 100644<br />--- a/classes/relocatable.bbclass<br />+++ b/classes/relocatable.bbclass<br />@@ -3,6 +3,19 @@ SYSROOT_PREPROCESS_FUNCS += "relocatable_binaries_preprocess"<br />CHRPATH_BIN ?= "chrpath"<br />PREPROCESS_RELOCATE_DIRS ?= ""<br /><br />+def is_elf_file (fullpath):<br />+ import subprocess as sub<br />+ <br />+ p = sub.Popen(['file', '-b', fullpath],stdout=sub.PIPE,stderr=sub.PIPE)<br />+ err, out = p.communicate()<br />+ if p.returncode != 0:<br />+ return 0<br />+ <br />+ if out.startswith('ELF'):<br />+ return 1<br />+ else:<br />+ return 0<br />+ <br />def process_dir (directory, d):<br /> import subprocess as sub<br /> import stat<br />@@ -24,7 +37,8 @@ def process_dir (directory, d):<br /><br /> if os.path.isdir(fpath):<br /> process_dir(fpath, d)<br />- else:<br />+ if is_elf_file(fpath) == 1:<br />+ # only try to relocate ELF files<br /> #bb.note("Testing %s for relocatability" % fpath)<br /><br /> # We need read and write permissions for chrpath, if we don't have<br />@@ -85,7 +99,7 @@ def rpath_replace (path, d):<br /> bindirs = bb.data.expand("${bindir} ${sbindir} ${base_sbindir} ${base_bindir} ${libdir} ${base_libdir} ${PREPROCESS_RELOCATE_DIRS}", d).split()<br /><br /> for bindir in bindirs:<br />- #bb.note ("Processing directory " + bindir)<br />+ bb.note ("Processing directory " + bindir)<br /> directory = path + "/" + bindir<br /> process_dir (directory, d)<br /><br /></pre><br /><br />I'll post more in a little while, including full instructions on getting oe up and running under OSX, but I'm off on holiday for a week.tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com1tag:blogger.com,1999:blog-9184145065528610199.post-33078888446020453412010-07-11T10:03:00.000+02:002010-07-11T13:52:09.080+02:00Android on tablets, rights and wrongsThis is likely to be a relatively contentious post. I've spent a bit of time trying to get to like Android, and, in short, I can't do it. I don't like Android. I'm sure it's OK as a <span style="font-weight:bold;">smartphone</span> OS, but on a tablet, it simply doesn't work for me.<br /><br />Now, I'm aware that I'm probably not the average user, but I'm (humbly enough) pretty well attuned to what people need to make computers work. That comes from 20+ years in "the biz", using pretty much every operating system there's ever been, including some real wierdos that most people haven't even heard of.<br /><br />Now, to start hammering on what Android's got wrong, we really need to look at a comparable system that's got it *right*. And it needs to be something I have near me, so out comes the trusty Newton. Yep, that's right. The Newton. A 13 year old, underpowered "pocketable" that was ridiculed in its earlier incarnations for its pisspoor handwriting recognition. Android's gotta be better than that, right? Read on for a load of words on why I think the way I do, but the executive summary is "No, wrong".<br /><br /><h2>Philosophy</h2><br />Before we get to the "nitty gritty" of little things, we need to look at the design rationales of the systems, or, for want of a better phrase, their "philosophy".<br /><br />Newton came from a real intention to make a computer that was different, that was better. A radical shift from the 100lb hulking monoliths that lived on or under our desks at the time. A powerful computer that could be dropped into your pocket. A computer that anyone could use. A computer that didn't need a keyboard. It may have been a commercial failure (it cost Apple a lot of money at a time it couldn't afford it), but opened a whole range of new business markets and the whole concept of a pocketable "real computer" made a lot of money for other people.<br /><br />Android comes from Google. In short, it can be summed up as a device for getting more eyes to Google's primary business, i.e. advertising. Google want to hit a new market (originally smartphones), so they leverage a bunch of open source software and try to make something that looks like what the current market leader (iPhone, in this case) looks like, and dump out a beta. Being "open" means that the hardware manufacturers can make it work on their chips, being free means that the carriers don't have to pay license fees, and being free means the consumer gets a cheaper device. Everyone wins, right? Well, in reality, not quite. Hardware manufacturers have mainly made *one* version work for *one* generation of chips, and have often not lived up to the GPL requirements so that their initial work could be carried on by the public. Carriers couldn't care less about updates, because they'd rather sell you a new phone with a new contract, and realistically, it's hardware costs that drive the pricepoint anyway. Net result is a messy market with a ~33/33/33 split of the 3 current major versions of Android, and most platforms not being upgradeable.<br /><br />Then along came iPad, and with it a sudden rush of android-running tablets. Because a tablet is just like a scaled-up smartphone, right? Again, "No, wrong".<br /><br />The problem here, I think, is that Android doesn't really fit in with the use case for a tablet device, and particularly not for the pocketable type of tablet. At least, not for *my* use case, but it's my post so I'll stick with my requirements, thank you very much. The iPad succeeds because it's a tightly controlled device with a tightly controlled market, aiming at <span style="font-style:italic;">consumption of media</span>. It's not a general purpose computer, really - apps live in their own little walled gardens, and you can't run what you want on it. It's a fucking good little gadget, though.<br /><br />Android thinks it's a phone. Except when it thinks it's an iPad. it dosn't have the same overall control that the iPad/iPhone has, and where Google have tried to enforce certain hardware requirements, they often don't make sense (for a phone *or* for a tablet) except when you look at it from an advertising <span style="font-style:italic;">pusher</span>'s point of view. I mean, really, why does a phone, or a tablet, <span style="font-style:italic;">need</span> a GPS? Sure, it might be <span style="font-style:italic;">useful</span>, but I fail to see the absolute necessity. Why restrict to a specific set of screen sizes? Why <span style="font-style:italic;">must</span> it have a camera? After all, anyone who cares about the photos they take won't be using a phone camera anyway. but I digress slightly.<br /><br />To sum it up: IMO, android is a "me too" iPhone/iPad clone, and not a very good one. It suffers from Google's "permanent beta" mania. Get it out fast and dirty, and fuck the early adopters.<br /><br /><h2>User interface</h2><br />The overall user interface of Newton is *tight*. It's intended to be used with a stylus, although most selections can be made with a finger. Here's what it looks like, more or less (in reality, it's a lot more "green"):<br /><br /><img src="http://www.guidebookgallery.org/pics/gui/extra/newton/controlpanel.png"/> <img src="http://www.guidebookgallery.org/pics/gui/extra/newton/dates.png"/><br /><br />What we see at the bottom of these two screens is the stuff that's always available, viz: a "menu bar" for the current application, and a "Dock" (to use OSX terminology) for a few common apps and functions (undo, find, assist, more on these later). That uses up a fair amount of available screen space, but the rest belongs to your app. What's important here is that the interface is consistent. From the supplied calendar application to 3rd party web browser, you always know where to go.<br /><br />Here's another one, with an "add-on" backdrop, and rotated into landscape mode (the green is a little overbearing, probably as it was pulled from an emulator)<br /><a href="http://www.flickr.com/photos/raparker/3558905798/in/photostream/"><img src="http://farm4.static.flickr.com/3563/3558905798_a451c3047f.jpg" /></a><br /><br />The little star at the top of the screen is the "notification" icon for Newton. What Android mainly uses its waste of space "status bar" for.<br /><br />Android is chaotic. It's mainly intended to be used with a finger, but that doesn't always work. One app might grab full screen and require some sort of gesture to pull up menus, another leaves menus and stuff on screen. Mostly apps leave the status bar at the top of the screen, but it's pretty much a waste of space - there's very little you can do with it. Admittedly, most apps respond to the "menu" button, but not all devices <span style="font-weight:bold;">have</span> a hardware menu button. Menu widgets don't seem to be standardised, and some are so small as to be unselectable without using a stylus. If nothing else, it's more food for the "open source can't do UIs" crowd.<br /><br />Scrolling is standardised on both platforms - on Newton you use the up-down arrow keys, on Android you "swipe". I find that my swipes are taken as clicks or some other UI action about 50% of the time, and although the "inertial" scrolling thing looks cool initially, it's intensely frustrating as your swipe goes that bit too far and zooms waaaaaaaay past what you were looking for.<br /><br />Closing apps is more or less standardised - the Newt has a little X at the bottom left corner, that closes your app. Android recognises the "back" and "home" buttons, but, again, <span style="font-style:italic;">not all devices have them</span>.<br /><br />Rotation hits some little glitches, as well. Android assumes you have an accelerometer, and auto-rotates the screen to fit. That's nice, as long as you have an accelerometer. I don't, and there doesn't seem to be any standard "rotate" widget as per the Newton. Which is not to say that the Newt is perfect in this respect, some apps behave very badly when rotated. I would argue, however, that Android should at least provide a widget as a sop to those who don't have an accelerometer.<br /><br /><h2>Finding your data</h2><br />Newton has a "find" button. It works. It <span style="font-weight:bold;">always</span> works. 'nuff said.<br /><br />Android has a filesystem. A filesystem that you can't access without some sort of file browser. I have 3 on my device already - one works for one thing, one works better for another, and so on. Gah. <span style="font-style:italic;">I don't want to fuck about with filesystems, dammit!</span><br /><br />Otherwise, you must find your data from <span style="font-style:italic;">within</span> the application you want to use. Interfaces vary. It's messy. It's inconsistent.<br /><br />This reveals another philosophical thing. Newton doesn't have a "filesystem" as such. No hierarchy, no structure. A big searchable "soup" of data and applications. Everything is data, everything has a bunch of attributes, you can search it. It's a database. While this is somewhat shocking to those used to the current way of doing things, it's hardly new : "Pick" did this in the 60s, BeOS did this to a certain extent, so did Apple to a very limited extent with the "classic" MacOS (and also with OSX). <br /><br />The current "hierarchical" way of doing things is massively backwards, and it's holding us back. We use the name and location of a file to indicate its metadata. This makes no sense (as, for example, those who've been hit with Windows-based trojans and email viruses can testify). It works for certain system-level applications, but for user data manpulation, it's utter pants. <br /><br />Currently, this need is covered to a certain extent inside individual applications (think, for example, iTunes), but that data can't be easily shared to other apps without intrinsic knowledge of how to "get at" the database, and upgrades to one app often break other stuff further down the chain. <br /><br />It would be much nicer to simply have something where you could query aong the lines of "show me all the emails I sent to fred over the last month, sorted by date". "Okay, now show me the emails in that list which had attachments". "Now show me the attachments which pertained to project 'foo'". Etc etc.<br /><br />It's about time someone came up with a filesystem that is completely non-hierarchical (I'm currently working on a fusefs that does exactly this, actually).<br /><h2>App launching</h2><br />On the Newton, click on the "extras" button, go to the tab for stuff *you* have classified as applications, click your app. Or use "find". Or click on an associated piece of data. Or you might use "Assist".<br /><br />On Android, go back to the home screen, go to the right tab, click your app.<br /><br />To me, the whole "application centric" way of doing things smacks of "desktop computing metaphor crammed into a handheld device" with little thought. But maybe that's just me.<br /><h2>Data input</h2><br />With Newton, you write on the screen. That's pretty much it. Really. Just write directly in the boxes. Newton <span style="font-style:italic;">usually</span> turns it into a textual representation of what you wrote. Special characters and all. No special voodoo ways of writing a la "graffiti" on the Palm. Made a mistake? Scribble it out, it goes away. Or you can opt to have your text remain as a set of handwritten strokes, and have it recognised later (very handy for note taking in meetings, as the "usually" above implies - Newton's HWR doesn't always get it right, and might need some nudging in the right direction, which you can't do when scribbling at full speed).<br /><br />Alternatively, there are on-screen keyboards, or, in extremis, the newton serial keyboard, which is very handy for programming direct on the device.<br /><br />With HWR, you get around 20-30wpm, about the same as a *fast* typist on a good keyboard. With OSK, 3-10wpm. The newton keyboard is a bit craptacular though, and you can count on about 15-20wpm using it, along with cramp in the fingers.<br /><br />With Android on a tablet, you don't have much choice. It's on screen keyboards pretty much all the way unless your device supports hardware keyboards. For standard OSK with prediction, I got about the same as on the Newton (the prediction side of things only seemed to be able to predict one word - "android"). I've heard of 10-15wpm with predictive OSK and a fast OSK replacement you're trained to use (Swype, for example) - about as fast as a "slow" typist. With more training you might get a bit faster.<br /><br />HWR is good technology. It's fast, and discreet (speech recognition has the potential of being fast, but makes you look like a git, and you can't easily use it in meetings or noisy environments). If you want *really* fast, shorthand recognition could get you into massive wpm speeds - at least as fast as speech and maybe faster. The hardware can do it (my cheapo chinese tablet is, at a conservative guess, 6-10 times as fast as the Newton without taking into account the vector unit and GPU). Fast, accurate HWR is no idle dream.<br /><br />There's other failings with Android's input methods: they hide the entire screen when you're using them, so you have no context - try entering data into a form, and you'll be given a "next" button indicating that entering the current data will take you to the next form field, but <span style="font-style:italic;">there's no indication of what this, or the next, form field actually are</span>. Barking bloody mad, that is. Maybe it's fixed in Froyo.<br /><h2>Inter-app communications</h2><br />Nothing standard under Android. Some apps share, some don't.<br /><br />This is more or less the system under Newton as well, but it also has "Assist", and that's available to all apps. Yep, that button that looks like a question mark. What does it do?<br /><br />From some app, maybe a word processor, scribble "send to Mark", and select it. Hit "assist". Newton goes off and looks, finds that Mark might mean 2 people, and that sending might mean faxing or emailing. Asks who, and how. And then goes off and does it. "Call Fred", Assist, and the telephone dialer fires up, dials the number, and then puts a call logger up, allowing you to scribble notes whilst chatting.<br /><br />"Assist" is mad cool, and it was available in the early '90s. <br /><br />The built in apps under Newton *do* share data, and the interface for sharing that data back and forth was available to other developers' apps. the same is more or less the case under Android, although it's hard / impossible for a developer to shoehorn additional stuff into an existing app (as could be done under Newton) without modifying and recompiling.<br /><br /><h2>Synchronisation and so on</h2><br />The Newton synchronises nicely with desktop apps via serial, ethernet, wifi, bluetooth. As long as you have a sync app, of course. They're pretty hard to come by these days, and it's getting difficult to use a newt with a "modern" desktop OS. You now need need 3rd party software to sync with a Mac, but I'll give the Newton a pass on that as the OS the Apple-supplied software ran on hasn't been current for nearly 10 years. Dunno if the windows sync stuff works on Vista/7, but it certainly ran on XP. 64 bit might be what fraks it totally.<br /><br />Android mainly syncs, as far as I can tell, with "the cloud", which can largely be considered a euphemism for "Google's ads". Well, frankly, fuck the cloud. Desktop syncing is payware, so fuck that too. It really shouldn't be something one needs 3rd party software for - there *should* be some sort of extendable conduit for syncing - hell, OSX provides most of that anyway.<br /><br /><h2>Other stuff</h2><br />Let's be honest, Android does have a bunch of stuff it can do waaaaay better than the Newt. Video and audio playback is potentially loads better, mainly down to 12 years of additional hardware development. My cheapo tablet has more hardware potential than a top-of-the-range laptop from the Newton era, after all. That said, video playback under Android leaves a lot to be desired. the hardware should have the power to do NLE on video, and in most cases you can't even play stuff back unless it's in a specific format with a specific size. You can't assume codecs are there. A mess, in short.<br /><br />The web experience on Android is loads better than on the Newt, too, even if it can't easily do embedded flash video (something I heave a sigh of relief over).<br /><br />eBooks look nicer under Android. Higher DPI, colour screen. Fine. PDFs don't work at all under Newton, so even having an option to read badly-rendered PDFs slowly under Android is a blessing. That applies to 3rd party readers - I've not used the Adobe reader for 2 reasons:<br /><br />- On the desktop it's a pile of bloatware crap<br />- My android device doesn't have Google Market, so I can't get to it.<br /><br />Photos, idem. Colour screen, higher DPI. Win for Android by default and the inexorable march of progress.<br /><br />One area the Newton wins on is startup. From "press of button" to the "Happy Newton" chime and a usable device is measured in single digits of seconds. Android takes an age. In addition, the Newton comes back to *exactly* where you were when you turned it off or the batteries ran out, no matter how much time has passed between the two. No data loss, nothing. you're back. No finding files, you're still there. In 15 years of using Newtons, I've *never* lost data (not something I can say of PalmOS devices, for example).<br /><br />Wakeup - I can't compare. Newton is instant, but my tablet doesn't seem to have any PM stuff enabled, so I don't know if it works or not. I have to hard power cycle it. Sucks, but probably not an Android flaw as such.<br /><br />As far as gaming goes, Android is more modern. But 99% (or more) of the "games" I've found so far available under Android are made of suck. A lot of this is down to Google's utterly braindead decision to use Java, of all things, as a systems programming language. I mean, really. Gaming suck on a platform that uses a garbage collected langauge with no JIT? Who'd ever have thought it?<br /><br />And finally, performance.<br /><br />I have in front of me 2 ARM devices. <br />One has a 162MHz StrongARM 110 processor, giving 1 DMips/MHz. It has 4MB of RAM and 4MB of flash, with 16MB of additional flash in one of the PCMCIA slots for a total of 20MB *total storage*. It's running a 12 year old, interpreted, prototype based, language.<br /><br />The other has a 600MHz Cortex-A8 processor, which gives 2 DMips/MHz, and has, in adddition, a vector floating point unit, NEON FP extensions, and an OpenCL-enabled GPU. Even without using the addons, it's nearly *10 times* as fast as the Newton. It has a 13 stage superscalar pipeline and more cache than the Newton has main memory. It has 256MB of Main memory and 2GB of flash, with another 8GB of flash in the SD card slot for a total of 10GB storage. It's running software that's mainly written in Java. Oh, did I mention that the processor itself is optimised for Java?<br /><br />Guess which one feels "snappy"? Yep, you're right - the hardware specs don't make up for the software implementation.<br /><br />The "feel" of Android 2.1 makes me believe that the vaunted 450% speedup of Froyo's improved Dalvik are probably not overstated. IUt also makes me wonder why, if there was that much speedup to be had, why it wasn't "had" before initial launch of Android. And how much more there is to be had under the hood. Android's been out for over 2 years now; I'm hardly an early adopter.<br /><br />No, really. Four hundred and fifty fucking percent faster. What the fuck?tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com2tag:blogger.com,1999:blog-9184145065528610199.post-24997250377537659582010-07-10T16:19:00.000+02:002010-07-19T08:40:00.853+02:00Teardown, and comparison to the Newton.So, I tore the wits almost all the way down, and at least far enough to get a look at both sides of the motherboard. I didn't get closeups of the chips, because the little button boards are glued in place and removing them looked like it was gonna be a bit too delicate for a slightly inebriate hardware tech...<br /><br />Photos are in <a href="http://www.flickr.com/photos/28888140@N04/sets/72157624338560583/"> this set</a>, and here's a taster:<br /><br /><a href="http://www.flickr.com/photos/28888140@N04/4780096330/" title="Newton & Wits by tufty tufty tufty, on Flickr"><img src="http://farm5.static.flickr.com/4093/4780096330_9ef620b805.jpg" width="500" height="375" alt="Newton & Wits" /></a><br /><br />The hardware is impressive, The case has brass inserts for the screws rather than being the usual self-tapping crap, and the motherboard is *not* the mess of patch wires and crappy soldering I was led to expect.<br /><br />Comparison time. Let's look at the witstech A81 vs a Newton 2x00. Remember, I am biased, so I may be appearing to be harsh, but I will try to at least explain *why*.<br /><br /><h2>Form Factor</h2><br />Although the Newton is slightly longer for a smaller screen, it wins on ergonomics as opposed to aesthetics. The big "chin" gives something to hold onto in landscape mode, and the slightly "slimmer in the middle" case suggests (and indeed gives) a comfortable "portrait" mode grip. The wits, on the other hand, has nothing much to hold onto, and the case is slippery as oppoed to the Newton's slightly "rubbery" feel. "How do I hold this" was one of my first thoughts when I picked it up.<br /><br />The Newton also scores highly for its removable flip-over hard lid (screen protection), large stylus and pop-out stylus holder. Even the power supply scores well, with a bunch of adaptors supplied and easily interchangeable on the wall-wart.<br /><br /><h2>Screen</h2><br />No contest here. The chinaman takes it hands-down, in terms of clarity, resolution, brightness (although the Newton's backlight *is* 12 years old, so...) and so on. It also beats the Newton in terms of touchscreen performance, mainly because this particular example has a bad case of "the jaggies".<br /><br /><h2>Other hardware issues</h2><br />The wits has a useful stand. I'm tempted to cancel this out with the Newton's ability to run on 4 AA pencells if you need it to. Newton's (single) speaker is pretty good, but the hardware behind it lets it down.<br /><br /><h2>Battery life</h2><br />No contest. Newton, hands down. *Weeks* on a set of pencells, and you can happily let it simply run out of power, leave it for months, shove in a new set of batteries and you're *exactly* where you were when you put it down. That said, the wits does get an honourable mention for having a removable, and relatively high-capacity, battery. It's far better than most; I got 4 hours 45 minutes running "Operation Sandstorm" continuously ( load average 4, exercising the GPU and CPU pretty hard).<br /><br /><h2>Networking</h2><br />Both Wits and Newton can do bluetooth and wifi (although it's getting hard to find 5V PCMCIA wifi cards these days, and you're not gonna get anything other than 802.11b). The newt can happily do dialup, fax, or direct serial connection (this one is usually used as a serial terminal on my Sun Netra, actually). Oh, and IRDA. And Localtalk. That said, you can probably do most of that with the wits, given a usb device, some drivers, and a following wind, but would you actually *want* to?<br /><br />I'll give this one to the wits, as Wifi and bluetooth on the Newt are "kinda neat", but painful to set up. I'm assuming there will eventually be some android support for the wits' bluetooth chipset here...<br /><br /><h2>Expandability</h2><br />Grudgingly, the wits takes this. The newt has 2 PCMCIA slots, but in real world usage, one of those is gonna be taken up by a flash card. The little serial dongle on the newt is a pain in the ass, too. USB and a microSD slot show that some things *have* oved on in 12 years.<br /><br /><h2>Cool Factor</h2><br />Are you Joking? Newton by a mile. It's still got a multicoloured Apple on it, for ${DEITY}'s sake.<br /><br />If I'm honest, the Wits is a nicer machine overall, and undoubtedly massively more powerful, but the Newton shows areas where it could have been vastly better in a purely hardware sense. A shame, because wits have obviously poured some love into this - it's not crap.<br /><br />I will return to this later, with Newton vs Android in a software sense.tuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0tag:blogger.com,1999:blog-9184145065528610199.post-58948525258042003092010-07-07T20:26:00.001+02:002010-07-09T14:12:29.138+02:00A New ToyWell, I finally cracked. I'd been staying away from the Apple store, lest I inadvertantly find myself the owner of an iPad, when I came across Archos' 7 Home Tablet - a nifty looking little 7" screened "mobile internet device", running Android.<br /><br />So I ordered one.<br /><br />After a while (quite a while, actually), and 3 calls from Archos telling me my order had been put back again, I got a bit steamed with Archos and told them where they could stuff their 7" rigid object. If you catch my drift.<br /><br />However, I'd sort of got hooked on the idea of a 7" replacement for my ageing Newton MP2100, so I started casting around and eventually found <a href="http://www.witstech.com.cn">witstech</a>, who produce the A81, a nifty looking 7" device with GPS, a Cortex-A8 processor, and all for less moolah than the Archos. Score!<br /><br />So I contacted them, and purchased a brand spanking new, hot off the presses A81(E) (The E meaning that it has extra buttons for Android usage, but more on that later).<br /><br />So, sure as eggs is eggs, it got a bit delayed. But it did eventually get here.<br /><br />Review time.<br /><br />Out of the box, I find: One 7" tablet, half of the back removable, and a replaceable battery that slips nicely behind the back. Okay. One mini USB B to female USB A cable, one generic 5v, 1.5A charger (and they were kind enough to send one that had the right sort of plug for France, score one for Wits tech people), and (as I have a developer model), a little mini-USB B to 1.8V serial adaptor. The latter item looks like a mini-USB plug with 3 hand-labelled wires hanging out of it. Oh, and a nice enough little semi-hard-case.<br /><br />shanzai.com's unboxing video and overall photos <a href="http://shanzai.com/index.php/bandit-gadgets/tablets/1360-first-look-a81-sub-usd-200-mountable-tablet-sports-removable-battery-android-21-cortex-8-processor-and-features-galore">can be found here</a>. Note that hey got a few extra goodies that I didn't like a car charger (already got one) and holder (don't need one).<br /><br />In terms of finish, the outside of the hardware is not so bad, considering the price. It's lightweight, and has a relatively clean look overall. Although lightweight, it feels tough enough. A bit "chubby" in terms of depth if you're used to looking at Apple gear, but that's tolerable. <br /><br />Battery is marked 3000mAh, 3.8v. That's a couple of massive plus points - not only is it a load more beefy than the majority of the competitors' offerings, but it's also removable / replaceable. More on battery life later.<br /><br />The stylus (which is tiny, about the same size as a DS stylus) has a tendency to jam in the holder if you don't push it in "just so" (and it has nothing to help you with alignment - 1 point for industrial design there).<br /><br />Nothing much to say about the power and USB ports, which seem solid enough. The audio out port looks "odd", or rather "cheap". We'll come to audio later.<br /><br />The MicroSD card slot hides behind a little rubber grommet, which is normal, although it doesn't look overly waterproof. It's a push/push slot, but seems to be mounted a little too far out, it's hard to get the rubber grommet in place with a card in there. Half a mm further in wouldn't have hurt.<br /><br />The stand is a nice addition, pulls out from the back and holds the unit at a usable angle.<br /><br />Button-wise, on the "top" of the unit we have a power button, which (being clear, and retro-lit with LEDs) also doubles as a charging / level indicator as far as I can tell. Green for fully charged, orange for charging, I think. Next to that, there's a pair of left-right buttons, one unit as a "rocker". Looks very nuch like a volume up/down pair, and, oddly enough, that appears to be what it's intended as. On the front, at the bottom left, there are 3 more buttons, with icons corresponding to "home", "back", and "menu". The thin plastic sheet over the fasia around these buttons is already coming away, and from photos it appears that this is endemic - I haven't had the guts to completely remove the sheet and see if it's just "packing protection" though.<br /><br />Touchscreen is shiny, and has the slightly greasy feel that is common to most resistive devices. The LCD panel itself is bright (20% brightness is more than enough in most circumstances), clear, and (at least on mine) has no dead pixels. The 800x480 resolution gives roughly 135dpi, which makes for a nice enough display. Viewing angle range is "OK", at about 90° horizontally and 60° vertically before it's difficult to see. <br /><br />On the back we have 2 speakers, oddly positioned vertically (assuming a "widescreen" mode of usage), one over the other. Left and right would have been tricky with the battery placement, I guess, and I'm not expecting hifi quality sound from built in speakers anyway.<br /><br />On firing the device up, we find, horror of horrors, WinCE. Never has a user experience been so well summed up by its name. Wikipedia tells me that winCE has been out for 13 years, but it doesn't appear to have moved on at all - it still feels like Win 3.0 badly shoehorned into a portable device. It gets everything wrong. *Everything* runs full screen. Microscopic close buttons right next to other microscopic buttons - even with the stylus it's hard to hit the right one (and the touchscreen calibration is pretty much pixel perfect). This is obviously the build for the previous A81 with no buttons, because the buttons themselves don't do anything other than make a "click" noise. Even though I've told WinCE not to click. At all. Bastarding pile of shite.<br /><br />Wifi performance is fine, it picked up my access point straight away and gave me decent speed. The antennae don't seem overly sensitive (I'd like an external antenna port, myself), but hey - it works. Bluetooth appears functional, although the godawful WinCE interface (particularly the disappearing keyboard) meant that I couldn't actually get the device to pair with my mac more than once. <br /><br />WinCE, surprisingly enough, managed to use a USB keyboard and mouse through the supplied USB cable. Nice. Couldn't make my Mac see it as a USB storage device through a standard USB cable though. This may be an issue with the Mac, as I had the same problems with Adroid. <br /><br />Before we do away with WinCE, though, let's look at the quality of the speakers (and the reasons for this will be come obvious later). Playing through the speakers sound quality is at least "OK", at least up to about 80% volume (about the volume of a relatively "loud" radio), at which point things start to distort badly. Cheap speakers, don't expect to use them for much.<br /><br />So, we hate WinCE. Still alpha quality after 13 years. But we knew that.<br /><br />Let's reflash with Android and see where we get. After all, Wits have just released an english language Android 2.1.<br /><br />Reflashing is a piece of piss, once you have the SD card formatted properly (a bit tricky on the Mac, as it craps all over the disk as soon as it's formatted and the booter needs to be the very first item in the FAT, but a bit of VirtualBox voodoo gets us there). Power on, whilst holding down the "left" button, and leave it alone for a few minutes.<br /><br />Now, some of my gripes about Android are related to the fact the Android I have here is a beta. Some are to do with Android itself, which I'm not really a fan of. Bear this in mind as you read on.<br /><br />So, we power on, and we get a 4-colour quadrant display as the kernel loads, followed by a bunch of android robots, and finally an animated "android" logo. Boot is pretty quick, but it should be, it's solid-state after all.<br /><br />Out of the box, we don't have much. For some reason, wits have left "phone" and "camera" functionality in place despite the tablet having neither. A bit daft, that.<br /><br />No google Apps, (particularly "market").<br /><br />Bluetooth doesn't want to play, at all. this is, I suspect, a wits issue, or quite likely something to do with kernel drivers for the WL1271 wifi/bluetooth/fm chip. The end result is the same - no bluetooth.<br /><br />Battery status monitoring is also not included, it seems - the unit reports itself as being on charge, 100% charged, all the time. That sucks, but at least the power button indicates the charging state.<br /><br />Sleep doesn't appear to function - I suspect that there's no power management going on at all. Surprisingly, this still allows the unit to function for 7-8 hours with wireless turned on and decoding music (but not playing it through the speakers - my wife would have killed me for leaving it turned on all night making noise).<br /><br />Sound drivers give almost zero volume on the external speakers. That's gonna be a wits bad as well.<br /><br />For the rest, everything seems to function properly. Calibration is good, again (although the fucking idiot who decided recalibration of the touch panel should require a reboot wants taking out back, shooting, and burying next to the bloke that decided changing network settings in WinNT required a reboot).<br /><br />I find Android *very* difficult to get along with. Swipes are taken as taps, taps as swipes, and the keyboard / input handling is painful. I've found this to be the case on Android phones, too, but it sometimes makes me want to throw the damned thing at a wall.<br /><br />The onboard browser is pretty good (no flash, thankfully), renders pretty fast, and appears to work OK. I might try mini opera to get some adblocking, though.<br /><br />Although the onboard speakers are not properly driven by Android, the external audio is plenty loud enough, and without the usual underlying low-level hiss of cheap audio gear (tested with FLAC rips of Om's "At Giza" and Miles Davis' "Jeru"), and doesn't overload even with some really nasty noise pushed through it (Mainliner's "Black Sky"). As an audio player it's pretty good.<br /><br />Gaming-wise, Quake3 runs nicely at 30-40fps, and Modern Combat:Sandstorm is equally playable (although multi-touch would be handy for this). Radiant Lite is a nice little "old school" shooter, too.<br /><br />I haven't tested video playback, but given the gaming performance, it shouldn't be an issue.<br /><br />Other apps were less endearing, and indicative of what the average android experience might be, regardless of platform. Many apps don't bother to check screen size, and run in a little window on the screen. That's just lazy coding. Others crash with no explanation, or simply hang. Again, bad coding - if they are crashing because of missing features, there should be some sort of feedback.<br /><br />The device does miss a few features that Google, in their wisdom, have deemed "compulsory" for Android devices, namely: accelerometer, compass (and, to my chagrin, in my case, GPS). Not that I really need another GPS enabled device, but hey, I was kinda looking forward to playing "Zombies! Run!".<br /><br />Overall, Android still feels part-finished, even allowing for the missing functionality of a beta release. That's part of the overall Google "permanent beta" thing, I guess. It's not awful, and it's certainly better than Wince, but that's not saying much.<br /><br />More later. Hopefully I'll be able to find my spudgers and do a teardown, and I'll do a side-by side comparison versus my Venerable Newton.<br /><br />Later<br /><br />Simontuftyhttp://www.blogger.com/profile/00602829823862264815noreply@blogger.com0