cat /dev/random

Page Table Hacking in P.O.S.

2009-04-09T09:11:00.000-07:00

This post covers what I think is a clever way to handle the paging data used in 32 bit x86 architectures, specifically when PAE is not enabled. It requires 4MB of the linear address range (<0.1%) and is trivially easy to setup.

In order to access the memory associated with a linear address LA, the CPU must figure out what physical address PA coresponds to that linear address. This is done through some paging circutry that maps linear pages (aligned 4K regions of the linear address range) to physical page frames (aligned 4K regions of the physical RAM.) This circutry uses a 2-level tree of tables that are stored in RAM. The root node of this tree is called the page directory, it contains 1024 pointers to the physical addresses of the secondary tables (called page tables) and the page directory takes up one page frame (4K = 1024 entries x 4 bytes per entry.) The CPU keeps track of the physical location of the page directory in the cr0 CPU register. The page tables pointed to by the page directory have the same structure: 1024 pointers to the physical addresses of individual page frames. (The pointers used in these tables are only concerned with the address of a page frame, which are aligned on 4K boundaries, so the bottom 12 bits aren't useful for finding a page and are instead used as flags and to controll permissions and things like special large 4M pages that I won't go into here.)

It's important to note here that the structure of the page directory and the page tables are identical.

With 1024 entries in the page directory (the root node) and the page tables (the leaf nodes), 10 bits of the address can be used as an index into these tables. The way this works in practice is to use the highest order 10 bits of LA as the index for the page directory, and the next 10 bits of LA as the index in the page table. This is enough to get a physical page frame (as I'll show below), and then the last 12 bits of LA are used as an offset within that page frame. We can break LA down, then, into 3 values: the highest order 10 bits will be called LAd (d for directory), the next 10 will be called LAt (t for table) and the last 12 will be called LAo (o for offset).

A single entry in a page table points to a single page frame (4K). Since a page table has 1024 of these entries, each page table maps 4M of the linear address range. Similarly, since each page table maps 4M, each entry in the page directory (which points to a page table) is associated with that 4M of the linear address range, and there being 1024 of these entries in the page directory, the entire page directory maps 4G of linear addresses, which is what we'd expect with 32 bit addresses.

For the sake of shorter examples, let's call the physical address of the page directory PD.

In order to convert the linear LA into the physical address PA, the CPU computes the following: PT (page table) = PD[LAd]; PF (page frame) = PT[LAt]; PA = PF + LAo.

What would happen if an entry in the page directory pointed to the page directory itself, rather than to a page table?

Let's assume that the last entry in PD points to PD itself (PD[0x3FF] = PD).

Now, let's figure out what memory we would be reading to/writing from if we used the linear address LA=0xFFFFFF004. Using the above notation, LAd=0x3FF, LAt=0x3FF, LA0=0x001;

First, PT = PD[PAd] = PD[0x3FF] = PD.
Then, PF = PT[LAt] = PD[0x3FF] = PD.
Finally, PA = PF + LAo = PD + 0x004

So, the linear address 0xFFFFF004 points to 4 bytes after the beginning of the page directory. Treating the page directory as an array of 1024 4-byte objects, this then coresponds to the 2nd entry in the page directory. Interpret LA as a pointer to an entry in a page directory, and *LA equates to the physical address of the page table used to map the 2nd 4MB range of linear addresses.

What about the linear address LA = 0xFFC02008? Here, LAd = 0x3FF, LAt = 0x002, LAo = 0x00B.
First, PT = PD[PAd] = PD[0x3FF] = PD.
Then, PF = PT[LAt] = PD[0x002]
Finally, PA = PF + LAo = PD[0x002] + 0x00B.

Now, the physical address you get coresponds to the 4th entry in the page table pointed to by the 3rd entry in the page directory, or, the entry that handles which physical page is used for all memory reference in the range 0x00C08000 through 0x00C08FFF.

So, if PD[0x3FF] = PD, you can do the following:

To control what physical page some 4K linear page (LA) is mapped to, write to the linear address:
0xFFC00000|((LA&0xFFFFF000)>>10)

To control which page frame the page directory points to for use as a page table for some 4MB region of linear addresses (LA), write to the linear address:
0xFFFFF000|((LA&0xFFC00000)>>20)

If one ever writes to 0xFFFFFFFC, it will break this system.

This will work on any system, even ones that use trees that are 3 or 4 levels deep, so long as the following 2 conditions hold:

Each 'node' in the tree is the same size, and covers the same number of bits in the linear address.
The size of the nodes is the same as the size of the page frames pointed to by the leaf nodes.

This doesn't seem to be an option on x86_64 machines, but I haven't looked too much into that (as I'm writing code on a 32 bit machine, I'm not worried)

Music Conversion

2005-09-30T08:31:00.000-07:00

Me and Ducore (or Ducore and I)are working on tidying up and standardizing/sychronizing our music libraries, and I figured this would be a good place to brainstorm ideas/get stuff written down so its not just in our heads.

Here is the agreed upon format:

/[music root]/[Artist]/[Album]/[track number (zero padded)] - [Track Name].mp3|ogg

if you dont know the track number or if it is not applicable, then it is "xx"

There are more specifics for special cases that can be added later in comments. Eventually, a document should be written up to capture all of the rules. If I were more proactive and had more time right now, this post would be that document. However, I mainly wanted to use this post to propose a method of automating filename conversion, which Ducore thinks is imprcatical, and I intend to find a method to prove him wrong.

here is my newest idea:

1)use some program (eg, Amarok, rhythmbox, cantus, etc) to determine any tracks that do not have Artist/Album/TrackNumber/TrackName in the id3 tag. use said program to retreive this information from cddb if possible. Also, at this point try to identify duplicates and trash files as much as possible.

2)create a playlist containing only the files that have the aformentioned id3 tags. extract a list of filenames from the playlist file.

3)write a script that will loop through this file list and for each file extract the track name and number using "id3info" and rename the track to "[number] - [name]". We could also be more proactive and move it to the appropriate directory as well, but for teh most part, things should already be in the right place. This removes any reliance on file names already being formatted in any particular way. after this is done, only a relatively (hopefully) small number of files will need to be done by hand.

Building a computer

2005-05-26T10:56:00.000-07:00

So I'm not that up to speed on building computers. Sure, I know what the different parts do, but I'm not sure which motherboards are good, where the current AMD v. Intel debate stands, and so forth, but if you're reading this you probably do. My brother wants to build a computer for college, and he's asking me (quite ungrammatically) for help. The only real stress test he'll be doing is gaming. So, here are my (his) questions:

What is a good price for a CPU?
AMD versus Intel?
Motherboards: here's the last email he sent me... it's interesting to see how far English has been degraded for online communication:

so the other mother board that supports intel is intel is that good or
bad like how do their products fair in comparrison to others? its
specs are 800/533MHz fsb, and as far as expansion slots it has
PCI-E x16 :1
PCI-E x1 :2
PCI Slots :4
So the two mother boards are as following (AMD then Intel with prices)
could you tell me which seems better for more specifics go to
newegg.com
ASUS A8N SLI Deluxe Socket 939 NVidia nforce4 SLI ATX AMD Motherboard
Intel BoxD915PBLL Socket T(LGA 775) Intel 915P ATX Intel Motherboard thanks

If you can figure that out, advice will be paid for in wampum.

Posts Make Blogs Better

2005-04-05T18:44:00.000-07:00

When I lost my hard drive last summer, I also lost all my work on the web server I was writing. Well, ever the glutton for punishment, I've jumped back in again. So far, I've got the request parsing for HTTP/0.9 and HTTP/1.0 complete, and 1.1 will be added soon. However, I've hit a conceptual logjam. Here's the deal: my server works thusly:

A server socket starts up, listening for connections.

The new socket is passed to a connection thread.

The connection thread activates a parser, which returns an HTTPRequest object, containing all the info on the request

The request is passed to the selected HTTPHandler objects, generating an HTTPReply.

The HTTPReply is sent.

If the connection is persistent, start parsing the next request.

As if the bold weren't hint enough, that's the part that is frsustrating me. In the old version the requested URI was split into four parts, thusly: [http://<server>]/<path>/<item>[?<query_string>] and the appropriate handler was selected by item. There was a special file & directory catch-all handler which was run if item didn't match any other defined handler. But this ignores the fact that handling should be different if the request method is, say, PUT instead of GET. Or if the request contains certain headers, or even specific body data. So then I figured I'd just pass the data to each handler in time, and let them decide whether or not they should deal with the request. That's lovely and all, but it doesn't scale well.

So now we get to the question: how do I decide which handlers are used on a given request? Keep in mind that it needs to be extensibile, so a new handler can easily be added. But I'm stumped, which presents a problem, because right now all you get back is a Invalid Request or No Content response, which does not make a very good server. Suggestions will be stolen and implemented with no repayment, credit, or even thanks given. Who can resist such an offer?

Does anybody actually read this?

2004-12-14T13:31:00.000-08:00

None of us have posted anything in a while. We really are squatting. That, or when we come up with a good idea our first impulse is not to tell the whole internet about it, thereby preventing us from making any money from it. So, who reads this, anyway?

clusterfuck modules

2004-07-03T10:35:00.000-07:00

I have version 0.1 working. It supports packing, unpacking, and executing clusterfuck tasks, which are represented as tar files containing the template filesystem (I didn't follow the first idea of having a filesystem image, and all the metadata in other files, all wrapped up in a tarball.) The new filesystem must contain the file /run, which will be executed to run the task, and the filesystem MUST NOT contain the file /.run, it will be created as the secure entrance point for the task. So now, modules. I think they will be determined by a file named "/etc/modules" which will contain a new-line delimeted list of required modules (java, perl, etc.) The /.run program will set the appropriate environment variables to make all the modules available through the path, and may setup any special environment variables needed by modules, like paths to packages in java or perl. The modules will (probably) go into either /bin/modules or /modules, whichever I decide I like better. The hope is that by having commonly used modules cached and inserted into the tasks that need them, the overall size of the task files will decrease, lowering network traffic. Sofar, here's the list of modules I think would be usefull.

clusterfuck (to create and submit tasks to the clusterfuck server, which still needs to be writen)

coreutils

java

perl

proc (just mounts the /proc filesystem; I need to check the security implications of this first.)

Any ideas on what else would be useful?

So Close, Yet So Far

2004-06-17T05:17:00.000-07:00

Check out bstorer.blogpsot.com (note the transposed letters). Could it be more of the antithesis of Ben?

Sidenote: My brother Drew thought one of his teachers was stupid because she pronounced "antithesis" as "an-tith-a-sis". We had to explain to him that she was right, and that it was not pronounced "anti-thesis".

Anyway, I think it'll work for <anything>.blogpsot.com. I know it works with aducore, too, which might be even funnier. Or as funny. Or less funny. Or some fourth thing.

The point is, there is funniness with aducore, too. Unless there isn't. But there should be. Unless there shouldn't.

Break Out the Geometry Books

2004-06-11T06:56:00.000-07:00

So I want to write a program that will, in the course of its work, plot approximately 10,000 points in 3D space. I'm writing it in Java, and I need to optimize the drawing routines so that I can allow rotating, and possibly moving of the observation point.

One solution would be to use the Java3D API. But that is a separate download, and doesn't even work on my computer's shitty vid card. So that's out. Anybody know a fast way to do affine transformations?

Clusterfuck

2004-05-14T14:20:00.000-07:00

I'm thinking about writing some programs to let jobs that can be split up into small tasks that run independently (think S.E.T.I., genetic algorithms, neural networks, etc.) be run on any number of available computers. The basic idea is this: a client would check out a task from some server, run it in a sandbox, and then tar up and return the result data. I'm thinking about using chroot, and a bunch of mount -binds and hard links to get the needed binaries in place. For security purposes, all mounts would be done -ro, and only hard links to files which couldn't be editable would be allowed. Also, no suid executables would be allowed and the client would su to nobody and cd into the new /, since otherwise the application could break out of jail. Eventually, I'd like to set it up so that standard utilities could be requested based on some ID.

A task would consist of a template filesystem (which chroot would set / to), a set of utility package requests (later version, probably), an command to run (in the new chrooted pathspace, of course), and a path to tar up and return as the result. A server for this system would, in effect, turn tasks into results, pushing the actual cpu grunt work to the client machines. The clients would probably have to be run through nice, since it will likely eat up the CPU, and if this is to be run to sop up extra CPU cycles it should be done politely.

I'll probably get started on this within a few weeks, any suggestions before I start?

I know!

2004-05-13T12:58:00.000-07:00

How about an operating system where the kernel just acts as a big switch board and there are kernel modules that register what they do. Each service (filesystem, process communication, etc.) could have a type, and perhaps subtype, and modules could communicate with eachother by ID, so it wouldn't matter what version of a module you have as long as it supports the published API for that module type and subtype. What a Piece Of S#!t idea...

I'm For It

2004-05-13T12:42:00.000-07:00

Look, ma! No hands!

Frist Post

2004-05-13T12:33:00.000-07:00

Perhaps we could squat on some blogspot subdomains. I can't imagine that would piss anybody off.