Search Results: "stone"

29 January 2008

Simon Richter: Milestone 0.9

The not-yet-so-mighty project build tool I'm writing (codenamed "dammit") just compiled itself for the first time (took 40 seconds :-P ). It is probably not that usable yet, as it lacks dependency checking and thus always recompiles everything -- fixing that is the plan for tonight. So far, all it does is compile everything it can find and recognise in a directory and link it to a program; the plan for the future is not to add too much to that, mainly new project types like libraries and new input languages.

28 January 2008

Simon Richter: Building software II: now with more evil

As written earlier, I'm switching build system for one of my projects. In the end, I decided to roll my own. Yes, another build system out there. The general idea is to combine the strengths of automake and MSBuild, and take them to new extremes by not compromising where they have (that makes my build system a tad inflexible though). Automake's biggest strength is that it is descriptive, rather than imperative, and while it allows for rules to be entered directly to allow for some flexibility, this is usually the point where the Makefiles that are produced become unportable. But in general, the idea of having a tool deduce what exactly should be done to transform a set of input files into a set of output files is a good one, I think. From MSBuild, I stole the idea of making an explicit distinction between higher-level integration projects ("solutions" in their lingo) and actual build projects. Build projects only have one (main) output, which usually is a program or a library, and several auxiliary outputs (development files, translation templates, ...), while integration projects coordinate the build process (for example, if one of the build projects builds a tool, all projects using that need to be re-run if the tool is rebuilt, but only then. Automake's biggest downfall is stuff that is not explicitly supported. One of my projects uses IDL extensively, which leads to quite a lot of explicit rules supporting different ORBs. If I wanted to teach automake about that, I'd have to understand lots of perl code that emits code fragments that, when combined, will do the right thing. In a way, automake is a compiler, but based around the idea that since we start out from a Makefile compatible syntax, just adding things will magically work. Where it doesn't, special cases are invented, such as for libtool support, but stacking special cases is really difficult. MSBuild, on the other hand, leaves a lot to be desired when it comes to project-to-project integration. There is no way to tell it "publish these include files under the such-and-such directory for use by other projects", rather, you are expected to have the project using them explicitly reference your project in the include directories. If a project uses includes that reference includes from yet another project, it gets worse. Milestone 1 is going to be when the main binary can build itself on Windows and Linux.

21 January 2008

Rudy Godoy: involucrate.org - the first release

For the time being offline I've been doing a lot of things, and some of them involve free software of course. I'm glad to announce that this march Peru will be heading the direction from its current status-quo to, what we expect, is the first step into a real and sustainable ecosystem where our talented people (from academy, and others) get their hands dirty into to real contribution to free software projects. involucrate.org has born as a project focused on building an environment to foster a real free software community focused on technical contribution and making our country have a larger spot on the free software contributors world-map. The lack of appropiate models and the inhability to stablish a link between the real actors on such scenary have led to a poor involvement and groups atomization for "ideological" or political means, making room for "religionization" of a very technical and licensing model matter where debate over technical aspects have gone 0. Our manifesto (in Spanish) explains our vision and mission, and also how we expect to achieve such a challenging goal. Is in our will to link our academic people, who was somehow behind the walls (a luxury for a country like mine), and the other actors here and globally. We want our talented people to see globally, and offer our life-experience on the field to make them aware and show them the opportunities that they can have and how other people near us who are making it right!. This time, thanks to the wonderful guys at GNOME Foundation, we are having our very first international conference called involucrate+GOME focused on free software development and, as we expect to be, be the first step of a series of world-class events where we expect to set a yearly world-known free software event here in Peru. Something we dodn't have after more than 10 years since the first group of people gathered together to discuss which is the best distro or something like that and the discussion is still ongoing. As noted the conference will be focused mostly, well almost 90%, in GNOME, but we expect to have more editions dedicated to one or more projects. So, I invite you to check our program and our cool speakers, all from south america and all contributing on GNOME. Of course you are invited to attend to, if you happen to like us! Bring your questions and contributions to this initiative to both our project web or DebianPeru web who is coordinating this initiative, I mean this is almost a debianite sub-project ;) I want to say as a side-note, that despite what media has made people think, we are making a real cool relationship with the chilean community. Expect to hear from us soon, and not because we've buying more wine from Chile and they are importing real pisco from Peru, or because we'll mimic our presidents. I really like this time, it comes 10 years late, however!

7 January 2008

David Nusinow: Finally

A few years back I asked Branden Robinson for access to the X Strike Force SVN repository in order to improve the X server's autodetection, with the goal of stealing what I could from knoppix. At the time, users were constantly wandering in to #debian saying that they had used knoppix to create an XF86Config-4 and then they used that file on their Debian installations. They were also constantly whining about how Debian wasn't doing as good a job. So I decided to do something about it, and took a look at what knoppix was actually doing so much better than us, and I was surprised to find that they pretty much just wrote a skeleton configuration file and let the X server fill in the details. I had no idea the server was capable of such things. So Branden graciously gave me SVN access and I began comparing the knoppix method to the script called by "dpkg-reconfigure xserver-xfree86" and realized that we probably couldn't adopt the same method because we had tons of checks for portability. So I put the problem on the backburner for few weeks and worked on something else for a while.

Well, somewhere in between then and now I got sucked in to transitioning Debian to X.org (using the aforementioned SVN access) and then working on all the things that went along with maintaining X in Debian, some well and others less so. Between transitioning to Xorg, and then transitioning to a modular Xorg, even with the ability to steal Ubuntu's packages it still took about two full years with me being a rookie and all that. There were tons of people who worked on this with me, but it was just a damn big job. Eventually though, etch released with modular X packages, and we were running at a pretty good pace with upstream, so it was time to revisit the problem of configuration again after the two year detour.

The problem of configuration had been reframed for me by having looked at what knoppix was doing and discussions with upstream. Upstream was starting to come to the conclusion that we shouldn't have a config file at all, and that the server should be smart enough to do everything by itself. It was already partially there, it just needed a push in the right direction. This was a major shift in how I thought of it. Coming from a Debian background, where the answer is to always just regenerate or edit your config file, having the server work things out for you was a totally alien idea. But I have my deepest roots in the Macintosh world, so immediately fell in love with it. The problem was that the server had a whole body of code to use if you had no config file at all, and another, with far less automagic goodness, if you had a config file, even if it was a 0 byte file. The goal became to have the server work really well with a minimal config file, so you could override what you don't like in the defaults and let the server figure things out for itself at boot. The way forward was to translate as much of the logic in our configure script in to the X server itself as possible.

Ubuntu had put in a lot of work in to the configuration setup that we automatically benefitted from, so given that most users were happy with things as they were, I was able to carve away at the problem without disrupting anything. And there was a lot to carve out, as the script that runs the config is an absolute mess that was slated by Branden for a rewrite all those years ago. Early on I picked off the low hanging fruits like the font path and modules. Similarly, Redhat's Adam Jackson had also been working on this problem, and he killed off the ServerLayout section as well as putting in lots of critical fixes all over the place elsewhere. More recently, I've gone and cut explicit modesetting out of the configure script. Hardcoding this information is generally a bad idea in the randr 1.2 world, and most of the drivers will do as good or better job of figuring out the modes than our config script would. This let us jettison using the xresprobe program to ask the monitor for the settings to use. This cut out a lot of the code that we had to deal with, simplifying the configure script and letting us all benefit from upstream's work. This leaves a big gaping hole in user configuration, which is something I'm looking to address in a few weeks, but for now there are workarounds like editing your xorg.conf manually to make things work.

Finally, yesterday I was able to upload a version of the script that no longer uses the discover program to figure out what driver to load. I've patched the server to do this at runtime. If there's no driver listed it simply scans the PCI bus, picks out your primary video card, and loads the first driver that claims to support that PCI ID. This let us jettison the last external dependency that the configure script had, so now we have a relatively small chunk of shell script with no external C code and a simplified setup. At this point we're now shipping a more skeletal config file than knoppix ever did simply because it wasn't possible to ship something like this before and have the server work at all. This is a huge milestone for me because finally, after over three years, the problem I originally set out to work on with X is done. There's still bugs to uncover and fix with all of this, but I'm convinced that what we have now is superior to our old method. Eventually, with any luck, xorg.conf will just fade away for most people. There's a lot to work on before that happens though, but I'm happy to have finally gotten here.

31 December 2007

Amaya Rodrigo: Still remains - Stone Temple Pilots

Our bed we live, our bed we sleep
Making love and I become you
Flesh is warm with naked feet
Stabbing thorns and you become me
Oh, Id beg for you, you know I ll beg for you
Pick a song and sing a yellow nectarine
Take a bath, I ll drink the water that you leave
If you should die before me
Ask if you can bring a friend
Pick a flower, hold you breath
And drift away...

She holds my hand we share a laugh
Sipping orange blossom breezes
Love is still and sweat remains
A cherished gift, unselfish feelings...
Oh, Id beg for you, you know I ll beg for you

Happy Gnu Year, Holgi! You know I d love to be there with you :*

21 December 2007

Andrew Pollock: [tech] Waiting for a software RAID-1 to resync is like watching paint dry

I'm so annoyed with myself. So today was the day I was going to upgrade the disks in daedalus. I'd finally managed to convince Dell to sell me two new 140Gb disks to replace to two 70Gb disks that were fast approaching capacity. I'd organised for access to the datacentre from 10am. I arrived early. I didn't manage to get into the datacentre until about 11am, because they were having problems remotely unlocking the door, and I had to wait until an air conditioning repair guy turned up, who was fixing some air conditioning problem. I hadn't had a lot of time to plan how I was going to do the upgrade, but I figured it was going to be pretty straightforward. Each disk is partitioned into three partitions, all of which are mirrored using software RAID. The first partition is the root filesystem, which is just an ext3 filesystem, mirrored. The second partition is swap, also mirrored, and the third partition is an LVM physical volume. The first two partitions are only a couple of gigabytes. So the basic plan was to remove the second disk (disk 1, aka /dev/sdb), put in the new bigger disk, load the partition table from the original disk 1, resync the three mirrors, and then boot off the new disk 1, and rinse and repeat with disk 0. This was all going swimmingly, when right at the end (in fact after the third partition finished syncing according to the kernel), /dev/sda decided it had a few unreadable sectors. This made the software mirroring have a dummy-spit, and decide it needed to restart the syncing from scratch. I'd seen this before with a bad disk. So I wishfully hoped it was something to do with the new disk being bigger than the old disk, so tried to roll back to the original disk 1. As was pretty much expected, disk 0 exhibited the same problems at the same point. So the problem was disk 0, not the new disk 1. So it seemed like I just managed to pick the wrong half of the mirror to work from. I thought I'd try manually dd'ing the third partition from /dev/sda to /dev/sdb, ignoring the errors, but that didn't result in a usable half of a mirror either. Interestingly, these bad sectors hadn't made themselves known until this point. The RAID array had been otherwise healthy, and SMART hadn't uttered a peep. I think at this point, after spending about 3 hours fighting with it, I decided to move up a layer. I could successfully sync /dev/md0 (the root filesystem) and /dev/md1 (the swap device), and the only reason I could think of these bad sectors not giving me grief already, was because they were right at the end of the disk, and I hadn't quite used all the free physical extents in LVM yet. Lucky I hadn't decided to grow things any further. So I decided that rather than trying to convince this existing /dev/md2 to sync with the new /dev/sdb3, I'd just build a new degraded RAID-1 on /dev/sdb3 and move all the physical extents from the degraded RAID-1 on /dev/sda3 to the new degraded RAID-1 on /dev/sdb3. I tried the logical volume with /tmp on it first, since it was fairly sacrificial. It worked fine. So I tried the largest logical volume, /srv, which was 30Gb. That went fine as well, so I moved the rest. All of them went without complaint. So then I removed the now unused /dev/md2 from the volume group, and finally managed to boot with just the new disk 1. Then I was able to put in the new disk 0, and just do a standard RAID-1 rebuild onto it. Hooray for LVM saving the day yet again. And this is where I should have stopped. At this point it was about 3pm. I'd been aiming to leave by 4pm to pick up a rental car that I had to get by 5pm. I'd wanted to also upgrade to Etch while I was physically in front of the box, in case there were any nasty kernel/udev issues that made the box unbootable. The catch was, I needed to grow /var, which was quite full. The intention had been that once I'd got the two new disks in and all synced up, I'd create a fourth mirrored partition, and add this to LVM as a new physical volume, then I could just keep merrily growing things. It felt a little bit dirty having to make a new partition to get at the extra space, and I'd reading about mdadm's "grow" mode, whilst I was sitting around waiting for things to sync. So I thought to myself, I'd just delete the third partition, and recreate it using the remaining additional cylinders I now had at my disposal, then use this grow feature of mdadm to tell Linux the array was now bigger, then resize the physical volume, and go from there. This is where things went a bit pear-shaped. I deleted and recreated (larger) the third partition on each disk, and rebooted. I was then messing around with mdadm trying to update /etc/mdadm/mdadm.conf, since the UUID of /dev/md2 had changed, when I discovered that /dev/md2 had completely disappeared. It seems that recreating that partition made Linux completely fail to see /dev/sda3 and /dev/sdb3 as RAID-1 members, and so because of the fairly transparent nature of Linux's RAID-1, LVM had seen the underlying physical volumes, and just decided to run with /dev/sda3 as the physical volume, and everything had continued to work. I just had no redundancy any more. So it was about 3:20pm at this stage, and I was starting to panic, thinking I'd never get this sorted out before I had to leave, and I'd end up returning to the US with a non-redundant mess on my hands. Then I remembered that I had the backups of the partition tables of the old disks, from before I removed them. So I thought I'd go back to that state, and just have the additional cylinders unallocated. I hadn't yet attempted to grow the RAID-1 (partly because it had vanished), so in my haste, I didn't see this being a problem. The problem was, I'd booted into multi-user mode, and things had merrily been operating on just half the mirror. I restored the partitions, and rebooted, and lo and behold, /dev/md2 magically reappeared, already 100% consistent according to /proc/mdstat. I was somewhat surprised by that, but I booted back into multi-user mode again, only to discover that the /var filesystem was panicking and remounting itself into read-only mode. This was pretty weird, given that during boot, it was considered clean by e2fsck. So I was really getting bothered by this stage, so I rebooted into emergency mode (single-user mode in Debian starts way too much), and manually started up LVM, and forcibly fscked everything. There was a bit of filesystem damage to /var, /home and /srv. Thinking I'd now fixed the problem, I rebooted into multi-user mode again, but again /var, which was considered clean during the fscking/mounting phase of booting, panicked shortly after mounting, and remounted itself read-only. So I rebooted again, broke the mirror, and forcibly fscked the filesystems again (only operating on what was on /dev/sda3. Then I rebooted without incident into multi-user mode and resynced the mirror. At this point I ran away. So I'm really annoyed with myself. This should have been a blog post about how crap Linux's software RAID is at error recovery, and how LVM saved the day yet again, but it was overshadowed by me overreaching in my haste, and managing to cause silent data corruption. The morals of this story: I think that is all. I'm just so pissed off that what could have been a perfect (enough) upgrade with zero data-loss, even considering I had a bum disk, wasn't.

13 December 2007

Joey Hess: if all you have is a hammer

David's post about programming languages and hand tools reminded me about the old saw about the hammer and the nail. The funny thing about that saying is that the hammer is actually one of the more versatile tools there is. A few things I've done or seen done with hammers: So don't knock the hammer. Indeed it doesn't have the complexity of a programming language, but the variety of ways it can be used, number of varients that can be chosen for different purposes, and beauty of a well-designed one makes it at least comprable to a hash table, regexp engine, or the like.

11 December 2007

Adrian von Bidder: Handbook of Applied Cryptography: Free Download

The Handbook of Applied Cryptography (Menezes, Oorschot, Vanstone; 2001) is now available as a free (as in beer) download. It's from 2001, so it wouldn't include all the latest stuff like MD5 being broken and SHA1 being slowly weakened, also estimates on how long a computer takes to break DES will be seriously outdated, but the fundamentals haven't changed. I haven't had the chance to read it yet, but I guess now's the time to close that gap.

29 November 2007

Daniel Burrows: Moved to ikiwiki

As of this posting, my blog has moved to an ikiwiki instance on my own server. I made this change for several reasons, with the primary ones being that
  • I can edit my posts offline in any editor I want. Since I often work offline, this is a huge advantage for me.
  • I can use revision control to manage the site.
  • The data that is valuable to me (i.e., my posts) is under my control and in a format that is easy to extract.
  • ikiwiki is also a nice tool for managing a Web site, so I can kill two birds with one stone (once I actually write a Web site, that is).
Obviously some of those could be acheived using blogspot, with a sufficiently complicated workflow, but ikiwiki makes this painless and natural. The major downsides seem to be:
  • ikiwiki doesn't support blog comments. For the time being, please email me with any comments on my blog posts and I'll post them myself. My email address is Daniel_Burrows@alumni.brown.edu.
  • The Emacs Markdown mode has some annoying flaws, such as not understanding Markdown lists.
I haven't set gitweb up yet, so there are no history links available. Once I feel confident that I understand the security implications of using gitweb, I'll see how to enable it.

26 November 2007

Daniel Stone: felicitations

A special birthday shoutout to Ross Burtonini, who's 31 today.

30 October 2007

Andrew McMillan: Getting Blood from a Stone

Last week I installed Ubuntu Gutsy onto Heather's laptop. While Gutsy seems to be an easy task for most situations, installing it onto a Pentium 366 laptop with 200M of RAM and (particularly) an 800x600 screen was harder than it perhaps should have been. I'm sure that most installations these days aren't 800x600, but the graphical installer in Gutsy seems determined to make this painful. I had to move the toolbars to the sides of the screen, and then I could see the top half of the buttons on each page. It was like the page was sized for 600 vertical pixels, but the designer had forgotten about toolbars and title bars - not that I could see any screens in the process I followed that needed more than 5/6 of that screen anyway. Eventually I got it installed, and it even seemed to run OK once we booted into it. That's "OK for a 200M P366 with an 800x600 screen" though. Looking around at the price of a new laptop made putting up with that sort of performance a whole lot less palatable. The Acer Aspire 5310 (with free RAM upgrade) was $898 at Dick Smith, with a $99 cashback offer. A quick google shows that it's using the Broadcom 43xx wireless which isn't even close to being the best, but can be made to work with Linux. Everything else seemed likely to work, so we bought it. Installing Gutsy on it was nearly trivial, though I had to install bcm43xx-fwcutter on a different PC (my laptop, which is running Debian, in fact) to get the firmware for the WLAN before I could get the wireless working. I'm surprised that Broadcom still don't make that firmware publicly available somewhere, rather than forcing people to jump through the sort of hoops that would get them wanting an Intel chipset next time. Anyway, everything installed very easily, and the laptop is working quite nicely. Strangely neither sound, nor suspend to ram are working out of the box, but perhaps I'll get them going in due course. They're not so important in this case fortunately, but perhaps in due course I'll try and get them working and post some details about it. Much harder has been getting the fabled 'cashback' from Acer. I think I now know what I'm being paid $99 for. Firstly the only way to get your cashback is by registering through a webpage. Heather's first attempt to do this resulted in an error from our proxy about a malformed request, so I got called in. I tried registering using on my laptop, but couldn't even get to the cashback page. I then tried using IE6, with similar results. So perhaps it's my PC? I tried using a different PC, with the same result again! We tried ringing them up, but they were absolutely determined that (even after 20 minutes on the phone) they were not going to accept that information over the phone. So the only way to get the cashback from Acer was via their thoroughly broken website. Even their Contact Acer page is broken in firefox just showing a blank. Firefox users need not apply. Eventually, while spending some time in front of Heather's main computer (which had made it all the way through to submitting their on-line form before failing) I realised that the error she was getting was a proxy error from some in-form javascript submitting an invalid request, so I disabled the proxy, the form finally worked, and I managed to apply for the cashback. Now we just have to send the printed form in, along with some blood from our firstborn, the ashes of my grandmother, various barcodes, receipts and toenail clippings and we're sweet. They say they'll send us some money within 30 days. I think we should maybe frame it or something. I just know I'm going to feel really inclined to take advantage of cashback offers in future. In Other News: DVD Slideshow Meanwhile I've been playing with DVD Slideshow which seems to be just what my parents have been after for a while, so they don't have to keep their favourite photos on the camera to be able to show them off on someone's TV. It's great! At least it is great now after I changed all the calls to ffmpeg to add a 'k' after the bitrate parameter. But that's Open Source Software, I guess. I'll send a patch to them... :-)

25 October 2007

Daniel Jacobowitz: An adventure in Unicode PC fonts

I have always had some trouble with my eyes. One bizarre side effect of this is that switching fonts is very unpleasant. I recently got fed up with fighting things to live in the stone age of pre-Unicode fonts and locales and started hunting for a new console font. First I looked for nice new ones already designed for Unicode, with a selection of accented characters and so forth. The nicest I found was Terminus, but I’ve had trouble adjusting to it. So eventually I decided to stick with the font I’d been using - at least for now. I have been using the same font for my consoles since before 1997. This is, or at least was, the default Linux console font back when I did all my work on a VT on Linux/PPC: /usr/share/consolefonts/default8x16.psf.gz. When I started using X routinely I missed it quite a lot. Mostly that was because I used BitchX, and BitchX is written for an IBM437 code page set of line drawing characters. So I opened up that console font in xmbdfed and converted it to a PCF file. If you have Debian’s BitchX package installed, you’ve got a copy of this work in /usr/share/fonts/X11/misc/default8x16.pcf.gz. So I’ve done the same trick again. Here’s the steps I followed: Actually, after all that I was having trouble with the font’s name and eventually getting scary resource errors from X. I opened the font in gbdfed and saved it, which added some attributes and modified the bitmaps. Then I tried again and it worked. And now, I can use a UTF-8 locale and gcc’s error messages come out with foo’ (”angled” quotes) instead of display corruption! The resulting font is uni8×16, if anyone else would like it. I have switched to using it for all my terminals other than the one I run BitchX in; BitchX still needs the IBM437 version in order to display correctly. Of course, as soon as I finished this Paul Brook informed me that Konsole includes basically the same sort of font. I do not know the origins of KDE’s console8×16, but I do know that it’s a slightly different font (the @ has a smaller center, for example). And I know that I’m mighty annoyed it didn’t get added to my font path correctly when I installed konsole ages ago, since I might otherwise have found it!

24 October 2007

Daniel Stone: you can't hide from the truth

Dear Zeeshan,

yep, that's zeeshan

Ahem.

8 October 2007

Daniel Stone: painfully true

< eikke> is there any "small" thing which I could be able to do, now?
< eikke> if possible wihtout breaking my hardware as there's no major company behind my back :p
< marcheu> eikke: the most likely way your hardware breaks when doing driver stuff is because you throw it out of the window

18 September 2007

Daniel Stone: git and changelogs

Every time I see a post about changelogs (sorry Behdad, nothing personal), I die a little bit inside.

There are three problems here:

12 September 2007

Daniel Stone: concrete

Matthew Tippett just threw a CD full of AMD/ATI specs to Dave Airlie, approved for public release with no NDA. I'm now holding one of those CDs as well. Thanks, AMD.

In the past five hours, we've pushed 72,000 PDFs, for a total of around 1TB. This ... turns out to actually push the limits of our new fd.o setup.

10 September 2007

Daniel Stone: amd rejoins the open source fold

I'm sitting here at XDS, and John Bridgman and Matthew Tippett are announcing AMD's open source plans. In three words: 'specifications without NDA'. 2D very soon, 3D coming when the legal issues have been taken care of. Specs for the r3xx core will probably be coming later on down the track.

I don't need to say how awesome this is.

8 September 2007

Clint Adams: See Siemens first

Maintenant j'ouvre la fen tre et une mouche la chambre entre
Ni la moche ni l'italienne ne peut  tre trouv e plus   son centre
This place with its wood and its shingles, this place
with birdshit splattered down the bricks
This place with drunken girls screaming Meat Loaf lyrics
and behaving like abject pricks
Maintenant je suis bien loin
But yet oh so close
Cerca de la criatura del lago
Not Iago as has been previously claimed
Humming, screeching, gurgling, squeaking
Not unlike Barbie's mom on a Thursday night
It goes through the motions of accomplishing something
When really it is advancing its own sinister agenda
An agenda so sinister that you'd name it Dexter if you could.
You can't.
Then, as the disruptive forces destabilize reality, like
they destabilize the rhyme and scansion and hyperlinklessness
of
This Poem
Then, like
Mike Stone
expressing
gratitude,
like something demanding its $3.50 (but oh, oh, it does not want its $3.50; it wants
something far more visceral and ephemeral), it makes a simple statement.
F01.
Natuurlijk.

5 September 2007

Ian Wienand: Short review of guarded page-tables

Anyone who has done an operating systems 101 course is familiar with the standard hierarchical page-table structure. This is essentially a radix-tree where bits of the virtual address are taken as indexes into an array of pointers, each pointing to the next level down or, at the leaves, to a physical entry. Hierarchical page-table One potential issue with this style of page-table is with a very large, very sparse address space (such as in a single address-space operating system) there will be many intermediate steps with possibly only a single translation at the end (i.e. lots of single pages scattered all around your address-space). Thus we can add a bit-field guard to each of the entries in the page table (Liedtke, 1994) to help indicate only those paths through the tree which are valid (similar to a Patricia tree). Translation first proceeds as usual; the top bits are used as an index into the top level table. However, each entry now contains extra information about further valid addresses. The guard is masked against the next bits in the virtual address; if it matches (e.g. in our example is 0x2) the next step can proceed directly to the leaf node, bypassing the middle look-up. The entry can be marked as either final (i.e. pointing to a leaf node) or intermediate, in which case the process continues with the next level (which also has its own guard, and so forth). Any entry that does not match the guard is known to be false, and therefore a fault can be raised. Hierarchical page-table with guard To examine this further, consider that we know that each page in our 24-bit address space above is 4KiB, thanks to the 212 = 4KiB offset. Therefore each of the 16 possible values of the top four bits selects 1MiB of the 224 = 16MiB address space; e.g. 0x0 selects the first megabyte, 0x1 the second and so forth. The second 4 bits selects a 64KiB region of this 1MiB, and the last 4 bits selects a 4KiB region of this 64KiB region. This scheme could work quite well if we were using only 16 pages each separated by 1MiB. Each of these pages would only require an entry in the top level with an appropriate guard which could then be marked as final and point directly to a physical frame. Once things become less sparse however, we need to start filling in middle levels. If you have 2 pages within a 16MiB region, you need at least one extra bit of address to tell them apart. If you have 3 or 4 pages, you need at least 2 bits to tell them apart, and so forth. It would therefore be beneficial to have variable level sizes to dynamically adapt and create the most efficient lookup possible given the address space layout of a process. For example, if you knew your process was only going map pages 0x123 (100100011) and 0x124 (100100100) a good option would be to make your top-level only two entries (i.e. check the top bit) with a guard on the entry at index 0x1 of 00100. You then need a second level with 8 pointers to differentiate the remaining 3 bits (each of these would be final and hence point directly to a physical page). The more pages you start mapping, the less bits you can discard with the guard. If you follow this through to a guard of 0 bits you end up with a linear page-table. It has been shown (Elphinstone, 1999) that fixed level sizes with 16 entries tends to work well. For a 32-bit address-space with 4KiB pages (e.g. 12 bits offset) this leaves 20 bits to be mapped by the page-tables; with each level mapping 24 bits this means a 5 level tree. The guard values provide enough path-compression that the table is not constantly walked. The disadvantage is that it may "over-allocate" meaning more space is dedicated to page-tables than strictly required. Deciding where and when to split levels, what size indexes to put at each level and updating all the guard values dynamically to make the smallest, most efficient page-table would create a variable-radix page-table (Szmajda and Heiser, 2003). In summary, a guarded page-table is more useful the more sparse your address space is. A variable-radix guarded page-table is complex, but could offer advantages for implementing variable page-size support and thus having positive effects on TLB coverage.

2 September 2007

MJ Ray: Current Issues / Re: Recycling

How are you lot getting on with North Somerset Recycling?

Badly.  I thought West Norfolk recycling was pretty awful (glass not collected at doorstep) but North Somerset is worse. Do this with one thing, that with another.  Why the blue blazes can't we have national consistency like Spain and Germany seem to?

Let me see if I've got this right:-

Paper, tins and glass can just go in the green boxes. Cloth has to be bagged and put in the green boxes.

Garden waste and corrugated cardboard can go in the green bags, but you have to remove all tape (even bio-degradable) from cardboard, put your address in the little pouch and put out a stone to weigh the bag down, else they'll not empty it.

Non-corrugated cardboard, plastics types 1 and 2 and electrical equipment have to be taken to the tip (which is awkward without using a car - try it some time).

Drinks cartons have to be put into a special wheeliebin next to Tesco's car park.

Finally, batteries have to posted to Norfolk in an envelope you can get from Sainsburys.

Figuring that out has only taken me a year... Did I miss anything? :-/

Next.

Previous.