The Long, Hard Road out of Segmentation

As of last night’s Pre-MAGUS check-in, ArcanOS now uses paging rather than segmentation.  Of course, this is a pretty critical step in the MAGUS goals.  Segmentation is really just a legacy aspect of x86 these days, and there are really no meaningful examples of its use in modern OS development.  So, why did I ever use segmentation in the first place?  Well, the biggest reason is that I inherited it.  Remember that ArcanOS began life as an early coursework lab for a teaching operating system called JOS, and very specifically an early introductory form of it that focused on the boot loader.  ArcanOS, like JOS, and like a lot of other operating systems, is designed to be a “higher half” kernel, which means that it is linked to 0xC00000, but it’s actually loaded at a much lower address (right at 1MB, for those playing along at home).  If you really want to split hairs, ArcanOS is linked at 0xC0100000 (which will change soon, possibly in the next check-in).  In order to really “run” ArcanOS, the x86 processor has to be set so that address 0xC0100000 is mapped to 0x00100000.

This was originally done with something the hobby OS community generally calls “the GDT trick“.  In order to run in 32-bit mode, an x86 requires you set up a GDT, and this will set the values of the segment registers.  These registers will be added to every address to get a final result that goes out onto the memory bus.  It turns out that, in this addition process, overflowing 32 bits will just cause a wrap-around.  So, you can exploit this to get your kernel’s link addresses to refer to its actual load addresses (0xC0000000 + 0x4000000 = 0x00000000 after wrap-around).  It’s good for getting things up and running, but you can’t really stake much on it after that.  Segmentation is inflexible and you can’t do any swapping with it.  On top of that, there are all sorts of memory addresses that correspond to physical hardware, and you have to remember to adjust those addresses to compensate for your segmentation trick.  Even more so, though, it seems that the GDT trick isn’t universally supported.  ArcanOS uses Bochs as its reference platform, but it would appear that VirtualBox doesn’t support the GDT trick.  Long story short– getting onto paging is pretty important.

So, this left me with some questions about how I wanted to get onto paging.  My first thought was to employ the GDT trick to jump into my proper kernel code, then set up paging and reload the GDT with segment descriptors that used a base of 0x00000000 (effectively turning off segmentation).  The more I considered this, though, the less I liked it.  Part of the reason ArcanOS started out using the GDT trick was because it also started out with its own boot loader and you have to set up a GDT to get into 32-bit mode in the first place.  ArcanOS now uses GRUB for its boot loader, though, and GRUB already sets up 32-bit mode and installs a GDT to support a flat memory model.  Why was I going to change the GDT only end up setting it back the way it was before?  No, this was a good opportunity to separate ArcanOS from its roots by just going straight to paging.

Setting up paging, it turns out, is a little bit easier than I thought.  You need about 12KB of memory to establish some initial page tables, and if you’re loading the kernel at 1MB, there’s usually plenty of room just under the kernel to use for those purposes.  After that, it’s really just zeroing-out the memory and stuffing some values in the tables.  Info on the layout of the tables, with reference for making a higher half kernel, is in an article on the OSDev Wiki.  The sticky wicket, in my mind, was that I would really just rather not write it in assembly.  I don’t mind writing in assembly, but for anything non-trivial (especially in a hobby project where my free time is at a premium), I trust a compiler more.  But…if I wanted to do this in C, wouldn’t I have to write it in the kernel proper, thus requiring I rely on the GDT trick?  As it turns out, the answer is “no.”  What I realized is that the code would be location-independent as long as all I did was write some simple loops and not refer to any memory except the page tables which I was trying to fill.  All of the control flow would be PC-relative (based on adding offsets to the current code location), so it would never care where it was really located as long as I called into it correctly.  The result is the init_paging( ) function in kernel/memmgr.c.  All I have to do to call the function is to store its address in a register, adjust its link address to its load address, and then call the function from the register.  I call this function, let it do its thing, and then I finish up setting paging in assembly.

Originally, I paged the first megabyte to itself and paged 0x00100000 to 0xC0100000.  This makes the hardware exposed in low memory easy to access, ensures my first page tables are mapped in, etc, and it ensures the symbols in the kernel were all mapped in.  And, then I set up paging and….crash.  Why?  Well, because I’m already running my code at 0x00100000…which is in the second megabyte.  The address of the current instruction was not mapped to anything!  So, once paging was turned on, my own code became inaccessible.  In the end, I ended up deciding to map the first four megabytes to themselves.  I’ll want to clean that out eventually, but for initialization, it’s something I can live with.  So, this was enough to get me into the ArcanOS kernel proper, but then…crash.  What was it this time?  Well…GRUB put the multiboot info struct below 0xC0100000, so that wasn’t mapped in.  Again, just to keep the bases covered, I mapped the first four megabytes to the address space starting at 0xC0000000.  This does mean there are currently two ways to access the same 4MB of memory, but it gets ArcanOS up and booting, and there should be some easy ways to clean this up.

Technically, with this view of memory, ArcanOS would have run just like the GDT trick was still being used, but I still did due diligence and I went through and stopped referring to addresses as being relative to KERNBASE.  My word of advice to any OS hobbyist who’s starting out– I really encourage you to consider doing rudimentary paging right from the start.  If you don’t, you’re going to get married to an address management scheme you’re likely to throw away later, and if you’ve been using it for a while, then it’ll take a harder portage effort to get off of it.  Just page your memory in from the get go.  If you’re using GRUB, even more to the point, because GRUB already set up the GDT for you to use paging with a flat memory model.  The biggest concern I had with setting up paging was that it looked hard at a time when I just wanted to get a kernel booting and doing some interesting things.  In reality, I was able to sling together a C function which would set up the page tables, and this made things very easy indeed.  Don’t get into using segmentation.  If you do, it’ll be a long, hard road getting back out.

So, from here, what I really need to do is clean up the paging a little bit.  Once I’m jumped into the kernel, I can stop identity-paging the first 4MB.  I also want to map only enough pages to hold the kernel.  Also, I don’t see a good reason to link the kernel at 0xC01000000 any more, since doing that was mostly to make the GDT trick a little bit simpler.  I have a good map of physical memory thanks to GRUB and I can make and manipulate pages, so this is everything the memory manager needs to be pretty full-featured.

Perry v Schwarzenegger (Prop 8 Trial) Motion to Vacate Denied

I have been waiting all day to type that headline.  I deleted it and then typed it again.  It felt good both times.

Here’s a link to the order.  It contains a lot references you can follow if you want to go into the case law behind what’s written here.

In reality, we’re talking about a fairly small tributary of the long river that is the Perry v Schwarzenegger case, which is fairly commonly called the “Prop 8 case.”  The case is in a bit of a holding pattern as it waits in appeal in the 9th Circuit.  The 9th Circuit has certified a question to the California Supreme Court to determine if the intervening defendants in the case, broadly called “the Prop 8 proponents,” actually have standing.  I’m actually not going to go too much into that aspect of things today, though it would come as a surprise to nobody that I have opinions on the subject.  I just mention the state of affairs to set the stage a little.  Look for something interesting on that front in (hopefully) early autumn.

No.  Today we’re talking about an extra motion that was filed while everyone waits to wrestle with the question of standing.  The judge which presided over the case, Vaughn Walker, made a public statement this past April stating that he has been in a same-sex relationship for the past decade.  Proponents of Prop 8 subsequently filed a motion to vacate Walker’s judgment.  As the name implies, it’s a request to throw out the judgment.  The basis for this motion was that Walker, being in a same-sex relationship, had an obligation to disclose his relationship and, ultimately, recuse himself from the case.  I’m fairly sure that most people who’ve followed the case considered this motion to be fairly frivolous, but I still want to dig into it a little bit because I think it helps to clarify some things about judicial impartiality and the integrity of the judiciary.

It’s important to understand that the starting point, and indeed the default state, is the impartial nature of a judge.  Impartiality is part of the oath of a judge, and it’s affirmed repeatedly through case law.  In fact, impartiality is an essential component of maintaining a nation of laws in the first place, and if no officer can be found who stands by the law first and foremost, then the whole system falls apart.  Therefore, it’s important that judges be treated as impartial and that rules be established that allow the transparent testing for partiality in the minority of cases where a judge genuinely cannot be trusted to act in an impartial fashion.  To that end, we have something commonly known as Section 455 which lays out criteria on which a judge may be disqualified.  This motion to vacate focuses on two aspects of Section 455, which I’ll include here:

(a) Any justice, judge, or magistrate judge of the United States shall disqualify himself in any proceeding in which his impartiality might reasonably be questioned.

[…](b) He shall also disqualify himself in the following circumstances:

[…](4) He knows that he, individually or as a fiduciary, or his spouse or minor child residing in his household, has a financial interest in the subject matter in controversy or in a party to the proceeding, or any other interest that could be substantially affected by the outcome of the proceeding[.]

The proponents of Prop 8 challenged Walker’s impartiality based on the fact that he announced he was in a long-term same-sex relationship, citing violations of Section 455(a) and Section 455 (b)(4).  Let’s look at each of these in turn.

Section 455(b)(4) disqualifies a judge based on his or her potential to have a financial interest in a case, and that form of conflict of interest is undoubtedly the sort of thing that you try to avoid in an orderly and fair judicial system.  For example, if a judge (or the judge’s family) owns stock in a company involved in a case, then there’s a clear conflict of interest.  Other interesting cases that have come up in the past include things like the judge’s family possibly being in the class of a class-action suit.  Of the options available for disqualifying a judge, this is one of the more objective ones that can be put forward.

In the live blog of the oral arguments, you’ll see the attempt at pinning Walker’s relationship status to Section 455(b)(4).  Essentially, it goes like this: Walker’s in a ten-year relationship, which means he wants to get marries, which means that he wants to enjoy the financial benefits of marriage, which means he has a conflict of interests.  To put it another way, Walker isn’t capable of being impartial in a trial about gay marriage because marriage is financially advantageous and he could, if Prop 8 were ruled against, marry his partner.  Of course, this breaks down on a number of fronts.  There’s no evidence of intent to marry, for example, and there’s no reliable way to test it.  There’s the fact that marriage requires two people who want to marry and not just one, so you’d also have to test Walker’s partner.  There’s the fact that people change their minds quite a bit.  The fact that the Prop 8 proponents took the intent to marry as given ultimately broke their chain of logic.  See pages 9-10 for what I consider the more bash-it-with-a-hammer part of the order.  I’d quote it, but really…just read the whole thing.

So, this leaves Section 455(a).  The language for this rule requires a little bit of clarification.  It does not leave the door open to personal speculation, even if it seems “reasonable” for the party doing the speculation.  Instead, there is a test known as the “reasonable person” test that helps to make concrete the concept of Section 455(a) and to provide a test.  I’ll quote from the order:

In this context,the “reasonable person” is not someone who is “hypersensitive or unduly suspicious,” but rather a“well-informed, thoughtful observer” who “understand[s] all the relevant facts” and “has examined the record and law.”  United States v. Holland, 519 F.3d 909, 914 (9th Cir. 2008) (citations omitted).15  This standard does not mandate recusal upon the mere “unsubstantiated suspicion of personal bias or prejudice.”  Id. (citation omitted). […] In addition, the Court recognizes that a fact is not necessarily a basis for questioning a judge’s impartiality merely because that fact might lead a segment of the public to question the judge’s impartiality.  Reasonableness is not determined on the basis of what a particular group of individuals may think, nor even on the basis of what a majority of individuals in a group believe to be the case.

This is something you see in law from time to time.  In order to provide a test of a concept, a sort of hypothetical person, with certain qualities, is conjured up and a discussion is held about what this person would conclude or know.  These constructed people are a method of trying to project the concepts of law into a hypothetical third party whose thoughts the parties in the case may discuss.

Very similar reasons were given for why Walker should have been dismissed under Section 455(a): he’s in a long-term same-sex relationship, which means his impartiality is in question.  To really reach this point, it would have to be demonstrated that his personal desire to marry his partner would have to be sufficient that he could not preside over the case in a professional and impartial fashion.  Again, however, there is no fact that can be pointed to in this instance, since the Prop 8 proponents are again basing this conclusion on the fact that he is in a long-term partnership.  If you review the live blog (linked above) at the 10:39 timestamp (and the ones slightly earlier), there is a distinct pattern where it is concluded that having a long-term partnership immediately implies a powerful desire to marry.  Walker never said one way or the other, though, and his silence, absent of any other evidence, can’t be construed as proof of partiality.  In the court’s order denying the motion to vacate, it exposes the crux of the issue:

A well-informed,thoughtful observer would recognize that the mere fact that a judge is in a relationship with anotherperson–whether of the same or the opposite sex–does not ipso facto imply that the judge must be sointerested in marrying that person that he would be unable to exhibit the impartiality which, it is presumed, all federal judges maintain.

Things might have been different if Walker had issued remarks in the public record about an obsession with marriage, with how the case was the only thing standing between him and being married, etc.  It’d show a massive emotional investiture in a major outcome.  He didn’t.  Furthermore, there is a lingering suspicion on the part of the proponents of Prop 8 that all same-sex couples must be practically obsessed with their ability to marry, to the point that Prop 8 is the only thing stopping them.  I’m pleased to see sexual orientation invoked in the “reasonable observer” test, because one can point to many unmarried long-term opposite-sex couples.  Why would a same-sex couple be any different?  People choose to marry for their own reasons in their own time.

That really seals it, but there are some extra parts with respect to the argument that Walker’s failure to disclose creates reasonable doubts about his impartiality.  Such an argument is, effectively, flipping the script.  It makes the assumption that, should you find out something about a judge you consider a threat to impartiality, the judge must have already known this, too, and decided to remain silent on the subject.  Silence, however, does not imply motive.  You can easily make an alternative motive the the one presented– the judge considered everything and concluded that s/he didn’t have any threats to being impartial.  Silence cannot be considered automatic evasion, and to accept this argument basically means that it’s possible to accuse a judge of being impartial whenever one of the parties finds something that s/he doesn’t like.  This completely subverts the system of presuming judges can take their oaths seriously and creating rules for challenging that assumption.  To adopt such a stance would be damaging to the integrity of the judiciary:

Contrary to the intent of Section 455, which was designed to preserve judicial integrity through practices of transparency, it is clear that fostering the practice of commencing a judicial proceeding with an extensive exploration into the history and psyche of the presiding judge would produce the spurious appearance that irrelevant personal information could impact the judge’s decision-making, which would be harmful to the integrity of the courts.

And that pretty much sews it up.  I see this not only as a positive result for marriage equality but a major re-affirmation of judicial integrity and impartiality in light of questions about sexual orientation, which itself is somewhat novel and relevant.  In addition, and this could just be my own armchair quarterbacking here, I think that the motion to vacate was an intentional tactic on the part of the Prop 8 proponents.  It’s been many months since I read Walker’s judgment, but I seem to recall it having a large number of findings of fact that leave the proponents’ case significantly wanting.  Under a de novo standard of review, the 9th Circuit would be able to provide an independent conclusion regarding questions of the law in the ruling but they would be working with the lower court’s records and findings of fact.  While I found Walker’s application of law in the case fascinating and damning, I could envision debate about it.  By comparison, the findings of fact will be the basis for review, and the Prop 8 proponents don’t want that.  Their only hope is to vacate the judgment and get a new trial and better facts.  That tack failed.

I do believe this is good all around.  Aside from any further motions, the next battleground will be regarding standing.  I’ll, hopefully, be back in autumn on that.

ArcanOS PRE-MAGUS Update

With most of the “fun” of buying a house and moving to a new part of the Bay behind me, I’ve finally had some leisure time to turn my attention to something I’ve really missed doing…namely, developing ArcanOS.  What have I been up to on that front?

Well, after having been off the project for several months due to the whole “becoming a homeowner” thing, I took a not-so-long look at the project and concluded that I needed to be more realistic about the boot loader situation.  When we last left our hero, he was intending to continue development on his boot loader until such time as it could produce a working memory map, at which point ArcanOS would be ported to the Multiboot Specification so that it could be booted by GRUB.  While I still think it would have been a lot of fun to do that, I ultimately had to be realistic about what I was getting myself into.  I’d be building multiple boot loader stages, making a new build process to support them, and enjoying the hair-pulling process of chain loading and making sure I hold onto the memory map in the process.  That would have been a good learning experience, but it would take a lot of time to do and I already lost a lot of momentum over the past few months.  Doing a lot of work only to throw it away and do a portage effort just didn’t look as appetizing.

So, as of a recent commit, ArcanOS now boots via GRUB.  The current commit will generate a disk image file for Bochs which contains the GRUB stage1 and stage2 boot loaders already.  As of tonight’s commit, ArcanOS now receives an accurate memory map from GRUB and this will give me the material I need to make a frame allocator and then work on enabling paging.

Part of me is tempted to take a side trip and include some bells and whistles to make the boot process easier.  I’m getting tired of typing in the block list of the kernel on every test boot.  I’m fairly sure that much of that sort of thing, though, requires a file system GRUB understands, and if I leap onto a canonical file system, I might never get out.  I should also note that my build process needs some tweaking…right now I have to regenerate the file in boot/post_pad every time the kernel size changes!

Since I’m back to proper feature development for the MAGUS goals, I’ve changed the version name to PRE-MAGUS.