About File system logging

This is a note @MIT OCW 6.824 Lecture 7:

The main point of a log is make complex operations atomic.

I.e. operations that involve many individule writes. You want all writes or none, even if a crash in the middle.

A "transaction" is multi-write operation that should be atomic. The logging system needs to know which set of write from a transication.

Re-do with checkpoint:

Most logs work like this, e.g. FSD,
allows much faster recovery: ca use on-disk data
write-ahead rule:

delay flushing dirty block from in-memory data cache until corresponding commit recore is on disk

Check point rules:

all data writes before check point must be stable on disk checkpoint may not advance beyond first uncommitted Begin

Recovery:

for each block mentioned in the log
find the last xaction that wrote that block
if committed: re-do
if not committed: un-do

Why is logging fast:

group commit -- batched log writes.
could delay flushing log -- may lost committed transactions but at least you have a prefix.

Single seek to implement a transaction.
maybe less if no intervening disk activity, or group commit

Write-behind of data allows batched/schedules.
one data block may reflect many transactions, i.e. create many files in a directory.
don't have to be so careful since the log is the real infomation.

How can we avoid delete/create inconsistency?

This is a file system note: @MIT 6.824 2006 Lecture 6

Think this satiation,

unlink("f1");
create("f2");
Create happens to re-use the i-node freed by the unlink.
suppose only create write goes to disk, but none of the unlink's writes.

Crash.

After re-start, what does recovery see?

The file system looks correct! Nothing to fix!
But file f1 actually has file f2's contents!

Serious *undetected* inconsisency.

This is *not* a state the file system counld have been in if the crash had occured slightly earlier or later. And fsck did not notify the user there was an unfixable problem!

How can we avoid this delete/create inconsistency?

Observation: We only care about what's visible in the file system tree.

Goal: on-disk directory entry must always point to correct on-disk i-node.

Unlink Rule: remove dirent *on disk* before freeing i-node.

Create Rule: initialize new i-node *on disk* before creating directory entry.

In general, directory entry writes should be commit points.
Crash just before leves us with unused allocated i-node.
Crash just after is fine.

八皇后问题的实现

最近重新复习了一下沙特人的算法书， 根据他的算法实现了8皇后问题，
自己用C做了一个实现。
12个皇后的问题在我的机器（AMD 3000＋， 256，LINUX 2.6）上运行了4.7秒左右，
后来在忘上又找了一个实现,这是链接， 他的竟然只用0.04秒。SO 快。
佩服。
贴上代码：
我的：

#include <string.h>
#include <assert.h>

long nqueens(int);
int test_queens(const char *,const int , const int);

int main(void)
{
assert (nqueens(12) == 14200);
//assert (nqueens(13) == 73712);
}

long
nqueens(int n)
{
register int key = 0;
int scount = 0;
char retv[20];
int test_val;
memset(retv, 0, 20);
while( key >= 0) {
while( retv[key] <= n-1) { // n-1 means zero was a position
retv[key] = retv[key] + 1;
if ( (test_val = test_queens(retv,key, n)) == 1) //part answer
key++;
else if (test_val == 0)
{
scount++;
}
}
retv[key] = 0;
key--;
}
outter:
return(scount);
}

// if queens is illegel result return -1
// else if queens is legel return 0
// or part result return 1
int test_queens(const register char *v,const int key, const register int n)
{
for (int i = 0; i < n; i++) {
char vi = v[i], vk = v[key];
if (vi == 0 || vk == 0 )return 1;
if( i == key ) continue;
if (vi == vk || vk-vi == key - i || vk-vi == i - key)
return -1;
}
return 0;
}

>time ./my
real 0m0.556s
user 0m0.552s
sys 0m0.000s

那位兄台的

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef unsigned long ulong;
static const ulong ulong_bit = sizeof(ulong) * CHAR_BIT;

static inline ulong search(ulong lb, ulong cb, ulong rb, ulong cnt) {
if (~0ul == cb)
cnt += 1;
else
for (ulong bs = lb | cb | rb; ~0ul != bs;) {
ulong b = ~bs & (bs+1);
bs |= b;
cnt = search((lb | b) << 1, cb | b, (rb | b) >> 1, cnt);
}
return cnt;
}static inline ulong nQs(ulong m) { return search(0, ~0ul >> m, 0, 0); }int main(int argc, char* argv[]) {
ulong a = argc < 2 ? ulong_bit : atol(argv[1]);
ulong n = a < ulong_bit ? a : ulong_bit; // n = min(a, ulong_bit)
printf("%li: %li total solutions\n", 12, nQs(12));
return 0;
}

>time ./internet
12: 14200 total solutions

real 0m0.081s
user 0m0.024s
sys 0m0.004s