1980s computer controls GRPS heat and AC
Who Has Your Back? — An annual report looking at how different major companies react to government requests for data.
Mega-processor — A project to build a micro-processor using discrete transistors.
Stevey’s Google Platforms Rant — A rant by a Googler about Google’s failure to understand platforms (vs. products).
On three or four occasions over the past 4 years, I had a use for simple file system spec. Either to teach people about file systems, or to have a simple file system to implement to learn the idiosyncracies of an operating system’s VFS layer. This is what I came up with back in 2011 when helping a friend learn about file systems.
The structure is really simple. All multi-byte integers are stored as big endian.
A disk is a linear sequence of blocks. Each block is 512 bytes long. You can read/write a block at a time. The first block on the disk is number 0, the second is 1, etc.
The following is the file system structure. First of all, the file system uses 1024 byte blocks, and therefore you need to issue two disk I/Os to process a file system block worth of data.
The first fs block (disk blocks 0 & 1) is reserved, you should not change it in any way.
The second block contains the superblock:
struct superblock {
uint32_t magic; /* == 0x42420374 */
uint32_t root_inode; /* the disk block containing the root inode */
uint32_t nblocks; /* number of block on the disk */
uint32_t _pad[253]; /* unused (should be '\0' filled) */
};
Starting at the third block is the block allocation map. The most significant bit of the first byte of this block represents fs block 0. The next bit represents block 1, etc.
Each file is represented by an inode. The inode contains a number of data block pointers. The first pointer (blocks[0]) contains the first 1024 bytes of the file, blocks[1] the second, etc. The timestamps are in microseconds since 00:00:00 Jan 1, 1900 UTC.
sturct inode {
uint32_t size; /* file length in bytes */
uint32_t _pad0; /* unused (should be 0) */
uint64_t ctime; /* creation time stamp */
uint64_t mtime; /* last modification time stamp */
uint16_t nblocks; /* number of data blocks in this file */
uint16_t _pad1; /* unused (should be 0) */
uint32_t _pad2; /* unused (should be 0) */
uint32_t blocks[248]; /* file block ptrs */
};
The root directory is represented by an inode, the data pointed to by this inode’s blocks[] have a special format. They should be treated as arrays of directory entries. The filename is space padded (so, “foo.txt” would be stored as “foo.txt ”).
struct direntry {
char fname[28]; /* the filename */
uint32_t inode; /* the inode block ptr */
};
So, graphically, the file system looks something like:
sb -> rootinode
|-> direntries
| |-> <"foo.txt", inodeptr>
| | \-> inode
| | |-> data
| | |-> data
| | \-> data
| |-> <"bar.txt", inodeptr>
| | \-> inode
| | |-> data
| | |-> data
| | \-> data
| | .
| | .
| | .
| \-> <"xyz.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
| .
| .
| .
\-> direntries
|-> <"aaa.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
|-> <"bbb.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
| .
| .
| .
\-> <"ccc.txt", inodeptr>
\-> inode
|-> data
|-> data
\-> data
I just had an interesting realization about tail call optimization. Often when people talk about it, they simply describe it as an optimization that the compiler does whenever you end a function with a function call whose return value is propagated up as is. Technically this is true. Practically, people use examples like this:
int foo(int increment)
{
if (increment)
return bar() + 1; /* NOT a tail-call */
return bar(); /* a tail-call */
}
It sounds like a very solid example of a tail-call vs. not. I.e., if you “post process” the value before returning it is not a tail-call.
Going back to my realization, I think people often forget about one type of “post processing” — casts. Consider the following code:
extern short bar();
int foo()
{
return bar();
}
Did you spot it? This is not a tail-call.
The integer promotion from short to int is done after bar returns but before foo returns.
For fun, here’s the disassembly:
$ gcc -Wall -O2 -c test.c
$ dis test.o
...
foo()
foo: 55 pushl %ebp
foo+0x1: 89 e5 movl %esp,%ebp
foo+0x3: 83 ec 08 subl $0x8,%esp
foo+0x6: e8 fc ff ff ff call -0x4 <foo+0x7>
foo+0xb: c9 leave
foo+0xc: 98 cwtl
foo+0xd: c3 ret
For completeness, if we change the return value of bar to int:
$ gcc -Wall -O2 -c test.c
$ dis test.o
...
foo()
foo: e9 fc ff ff ff jmp -0x4 <foo+0x1>
I wonder how many people think they are tail-call optimizing, but in reality they are “wasting” a stack frame because of this silly reason.
Going under the hood of Inbox — translating Java to ObjC and Javascript
Open-sourcing Facebook Infer: Identify bugs before you ship — a static analysis tool for C, ObjC, and Java
TrainFever — a game inspired by 
Transport Tycoon
How Computers Work: A Journey Into the Walk-Through Computer
Why “Agile” and especially Scrum are terrible — a thorough “rant” about agile and scrum and their effects on overall productivity
O(n) binary search for when O(log n) is just too fast.
A Constructive Look At TempleOS
D3 gallery — chock full of neat visualizations.
The Apollo Guidance Computer: Architecture and Operation seems to be a nice book.
Powered by blahgd