a very occasional diary

A macro.

2012-05-11T20:20:00.000Z

C language is wonderfully profound. After almost 20 years, I still find new ways to (ab-)use it. Here is a little problem:

Define a macro IN(x, set), called as

IN(x, (v0, v1, ..., vn))
that expands into an expression

((x) == (v0) || (x) == (v1) || ... (x) == (vn))
which evaluates to true iff x is a member of set {v0, ..., vn}, where the type of x and all vs is the same. Alternatively, define a macro IN1(x, ...) that expands to the same expression as IN(x, (...)).

You won't see this post (or maybe you will).

2012-05-11T20:06:00.001Z

My ISP is blocking my blog. Am I an unwitting beacon of revolution?

Riemann hypothesis, DIY

2012-03-03T14:09:00.000Z

Continuing with useless exercises, let's look at prime numbers. We shall use Haskell this time.

-- prime numbers: [2,3,5,7,11,13,17,19, ...]
pr :: [Int]
pr = [p | p <- [2 .. ], maximum [d | d <- [1 .. p - 1], p `mod` d == 0] == 1]

The first line, starting with '--' is a comment. The second line declares 'pr' to have type "list of Int". Typings are optional in Haskell. The last line, uses "list comprehension" (yes, it is related to "set comprehension" used in one of the recent posts) to define 'pr' as those elements of the infinite list [2, 3, 4, 5, ...] (denoted [2 ...]), whose maximal proper divisor is 1. This is a very inefficient, quadratic way to build the list of all primes.

In addition, define a list of all twin primes:

-- twin primes, primes whose difference is 2
twinp :: [Int]
twinp = [n | n <- pr, (n + 2) `elem` (take (n + 4) pr)]

"x `elem` s" is true iff x is en element of list s. Ugly '(n + 2) `elem` (take (n + 4) pr)' is needed because for an infinite s, "x `elem` s" either returns True or never returns: without some additional knowledge about the list, the only way to determine whether x belongs to it is by linear search, which might never terminate. In our case, 'pr' is strictly ascending and hence the search can be limited to some finite prefix of the list ((take n s) returns first n elements of s). Perhaps there is a way to specify list properties that `elem` can rely on, I don't know, I opened the Haskell specification an only hour ago.

Let's do some "visualisation":

-- an (infinite) string containing a '+' for each element of s and '.' for each
-- element not in s, assuming that s is ascending and s !! n > n.
-- dot pr == "..++.+.+...+.+.. ..."
dot :: [Int] -> [Char]
dot s = [ if (x `elem` (take (x + 2) s)) then '+' else '.' | x <- [0 ..]]

For example, (dot pr) is an infinite string containing "+" for each prime number and "." for each composite.

By printing (dot s) in rows, k columns each, some hopefully interesting information about distribution of elements of s can be obtained. First, split s into sub-lists of length k:

-- (dot s), sliced into sub-strings of length k, separated by newlines
sl :: [Int] -> Int -> [[Char]]
sl s k = ['\n' : [ (dot s) !! i | i <- [j*k .. (j+1)*k - 1]] | j <- [0 ..]]

then, concatenate them all:

-- concatenation of slices
outp :: [Int] -> Int -> [Char]
outp s k = concat (sl s k)

A few examples:

putStr (outp pr 6)

..++.+
.+...+
.+...+
.+...+
.....+
.+....
.+...+
.+...+
.....+
.....+
.+....
.+...+

immediately one sees that, with the exception 2 and 3, prime numbers have remainder 1 or 5 when divided by 6. For 7, the picture is

putStr (outp pr 7)

..++.+.
+...+.+
...+.+.
..+....
.+.+...
..+...+
.+...+.
....+..
...+.+.
....+..
.+.+...
..+...+
.....+.
......+
...+.+.
..+.+..
.+.....
.......
.+...+.
....+.+
.......
..+.+..
...+...
..+...+

it's easy to see that "vertical" lines of "+", corresponding to a particular remainder are now (unsurprisingly) replaced with slopes. By changing the width of the picture, one can see how regular pattern changes its shape periodically

putStr (outp pr 23)

..++.+.+...+.+...+.+...
+.....+.+.....+...+.+..
.+.....+.....+.+.....+.
..+.+.....+...+.....+..
.....+...+.+...+.+...+.
............+...+.....+
.+.........+.+.....+...
..+...+.....+.....+.+..
.......+.+...+.+.......
....+...........+...+.+
...+.....+.+.........+.
....+.....+.....+.+....
.+...+.+.........+.....
........+...+.+...+....
.........+.....+.......
..+.+...+.....+.......+
.....+.....+...+.....+.
......+...+.......+....
.....+.+.........+.+...
..+...+.....+.......+..
.+.+...+...........+...

putStr (outp pr 24)

..++.+.+...+.+...+.+...+
.....+.+.....+...+.+...+
.....+.....+.+.....+...+
.+.....+...+.....+......
.+...+.+...+.+...+......
.......+...+.....+.+....
.....+.+.....+.....+...+
.....+.....+.+.........+
.+...+.+...........+....
.......+...+.+...+.....+
.+.........+.....+.....+
.....+.+.....+...+.+....
.....+.............+...+
.+...+.............+....
.+.........+.+...+.....+
.......+.....+.....+...+
.....+.......+...+......
.+.........+.+.........+
.+.....+...+.....+......
.+...+.+...+...........+
.......+...+.......+...+

One of the more striking examples is with twin primes:

putStr (outp twinp 6)

...+.+
.....+
.....+
......
.....+
......
.....+
......
......
.....+
......
.....+
......
......
......
......
.....+
.....+
......
......

Every pair of twin primes except for (3, 5) has a form (6*n - 1, 6*n + 1).

As Gauss reportedly quipped (when refusing to work on the last Fermat's theorem): "number theory is full of problems whose difficulty is only surpassed by their uselessness".

Cue a key

2011-12-24T21:50:00.000Z

There is a typical problem with Emacs experienced by people frequently switching between different keyboard mappings, for example, to work with non ASCII languages: fundamental Emacs keyboard shortcuts (and one has to invoke them a lot to use Emacs efficiently) all use ASCII keys. For example, when I want to save my work, while entering some Russian text, I have to do something like Alt-Space (switch to the US keyboard layout) Control-x-s (a Emacs shortcut to save buffers) Alt-Space (shift back to the Cyrillic keyboard layout). Switching out and back to a keyboard layout only to tap a short key sequence is really annoying.

Two solutions are usually proposed:

Duplicate standard key sequences in other keyboard layouts. For example,
```
(global-set-key [(control ?ч ?ы)] 'save-some-buffers)
```
expression in .emacs binds Control-ч-ы to the same command as Control-x-s is usually bound. This eliminates the need to switch layout, because ч-x (and ы-s) symbols are located on the same key (in QWERTY and JCUKEN layouts respectively).

Another solution employs the fact that Emacs is a complete operating system and, therefore, has its own keyboard layout switching mechanism (bound to Control-\ by default). When this mechanism is used, Emacs re-interprets normals keys according to its internal layout, so that typing s inserts ы when in internal Russian mode, while all command sequences continue to work independently of layout. The mere idea of having two independent layout switching mechanisms and two associated keyboard state indicators is clearly ugly beyond words (except for people who use Emacs as their /sbin/init).

Fortunately, there is another way:

; Map Modifier-CyrillicLetter to the underlying Modifier-LatinLetter, so that
; control sequences can be used when keyboard mapping is changed outside of
; Emacs.
;
; For this to work correctly, .emacs must be encoded in the default coding
; system.
;
(mapcar* 
 (lambda (r e) ; R and E are matching Russian and English keysyms
   ; iterate over modifiers
   (mapc (lambda (mod)
    (define-key input-decode-map 
      (vector (list mod r)) (vector (list mod e))))
  '(control meta super hyper))
   ; finally, if Russian key maps nowhere, remap it to the English key without
   ; any modifiers
   (define-key local-function-key-map (vector r) (vector e)))
   "йцукенгшщзхъфывапролджэячсмитьбю"
   "qwertyuiop[]asdfghjkl;'zxcvbnm,.")

(Inspired by a cryptic remark about "Translation Keymaps" in vvv's .emacs.)

Unintentionally yours.

2011-12-09T01:00:00.000Z

Extension.

This post is about set theory, which is a framework to reason about collections, elements and membership.

We start with a informal and naïve outline, which is (very loosely) based on a Godel-Bernays version of set theory. This theory is about sets (collections) which contain elements, which can in turn be sets. When a set $X$ contains an element $t$, it is written $t\in X$.

First, set equality has to be defined:

E0 Axiom of extensionality:
$$X = Y \equiv (t \in X \equiv t \in Y)$$
(Here $\equiv$ is a logical equivalence, pronounced "if and only if".) This axiom means that sets are equal if and only if they have the same elements. (In this and following formulae, free variables are implicitly universally quantified.)

Subsets are defined by $X \subseteq Y \equiv (t\in X \Rightarrow t\in Y)$, that is, X is a subset of Y when every element of X is also an element of Y. It's easy to check that $X = Y \equiv (X\subseteq Y \wedge Y\subseteq X)$, where $\wedge$ means "and".

Next, a way to build new sets is needed:

E1 Axiom of (extensional) comprehension:
$$t \in \{u \mid P(u)\} \equiv P(t)$$
This axiom introduces a "set-builder notation" $\{u \mid P(u) \}$ and states that $\{u \mid P(u) \}$ is exactly the set of all $t$ such that $P(t)$ holds.

Now, there is already enough machinery for two famous collections to be immediately constructed: empty set, $\varnothing = \{t \mid false \}$, which contains no elements, and the collection of all sets: $U = \{t \mid true \}$, which contains all possible elements.

With these axioms, conventional set operations can be defined:

singleton: $\{t\} = \{u\mid u = t\}$, for each $t$ a singleton set $\{t\}$ can be constructed that contains $t$ as its only element. Note that $t\in\{t\}$
union: $X\cup Y = \{t\mid t \in X \vee t \in Y\}$ ($\vee$ means "or")
intersection: $X\cap Y = \{t\mid t\in X \wedge t\in Y\}$
complement: $\complement X = \{t \mid t \notin X\}$
(unordered) pair: $\{t,u\} = \{t\}\cup\{u\}$
ordered pair: $(t,u) = \{t, \{t, u\}\}$
power set: $\mathfrak{P}(X) = \{t \mid t \subseteq X\}$

From here, one can build hierarchical sets, representing all traditional mathematical structures, starting with natural numbers:

$$0 = \varnothing, 1 = \{0\}, 2 = \{0, 1\}, \ldots n + 1 = \{0, \ldots, n\}, \ldots$$

then integers, rationals, reals, &c., adding more axioms (of infinity, of foundation, of replacement, &c.) along the way.

It was discovered quite early that this system is not entirely satisfactory. First defect is that it is impossible to have elements which are not sets themselves. For example, one would like to talk about a "set of all inhabited planets in the Solar system". Elements of this set (planets) are not sets, they are called ur-elements. Unfortunately, the axiom of extensionality makes all ur-elements equal to the empty set. Note, that this indicates that the axiom of extensionality doesn't work well with sets that have very few (none) elements. This was never considered a problem, because all sets of interest to mathematics can be constructed without ur-elements.

Another, more serious drawback, arises in the area of very large sets: existence of a set $\{t\mid t\notin t\}$ directly leads to a contradiction known as Russel's paradox.

Among several methods to deal with this, one separates sets into two types: "smaller" collections which are continued to be called "sets" and "proper classes", which are collections so large that they cannot be a member of any collection. Axiom of comprehension is carefully modified so that set-builder never produces a collection having some class as its element. In this setup Russel's paradox becomes a theorem: $\{t\mid t\notin t\}$ is a proper class.

Intention.

The axiom of extensionality states that sets are equal when they contain the same elements. What would happen, if set theory were based on a dual notion of intentional equality (which will be denoted by $\sim$ to tell it from extensional one), where sets are equal when they are contained in the same collections?

I0 Axiom of intensionality:
$$X \sim Y \equiv (X \in t \equiv Y\in t)$$
This looks bizarre: for any "normal" set $X$ a collection of all sets containing $X$ as element is unmanageably huge. But as a matter of fact, intentional equality is much older than extensional, it is variously known as Leibniz's law, identity of indiscernibles and, in less enlightened age, as duck typing.

There is a nice symmetry: while intensional equality myopically confuses small sets (ur-elements), extensional equality cannot tell very large collections (proper classes) from each other, because they are not members of anything and, therefore, intentionally equal.

The whole extensional theory buildup can be mirrored easily by moving things around $\in$ sign:

Intensional subsets: $X \unlhd Y \equiv (X\in t \Rightarrow Y\in t)$

I1 Axiom of intensional comprehension (incomprehension):
$$[u \mid P(u)]\in t \equiv P(t)$$

And associated operations:

uniqum (or should it have been "s-ex-gleton?): $[t] = [u\mid u \sim t]$, note that $[t]\in t$.
intentional union: $X\triangledown Y = [t\mid X \in t \vee Y \in t]$
intentional intersection: $X\triangle Y = [t\mid X \in t \wedge Y \in t]$
intentional complement: $\Game X = [t \mid X \notin t]$
intentional pair: $[t,u] = [t]\triangledown [u]$
intentional ordered pair: $<t,u> = [t, [t, u]]$
intentional power set: $\mathfrak{J}(X) = [t \mid X \unlhd t\}$

What do all these things mean? In extensional world, a set is a container, where elements are stored. In intensional world, a set is a property, which other sets might or might not enjoy. If $t$ has property $P$, it is written as $t\in P$. In the traditional notation, $P$ is called a predicate and $t\in P$ is written as $P(t)$. The axiom of intentional equality claims that sets are equal when they have exactly the same properties (quite natural, right?). $X$ is an intentional subset of $Y$ when $Y$ has all properties of $X$ and perhaps some more (this looks like a nice way to express LSP). Intentional comprehension $[u \mid P(u)]$ is a set having exactly all properties $t$ for which $P(t)$ holds and no other properties. Intentional union of two sets is a set having properties of either and their intentional intersection is a set having properties of both, &c. Uniqum $[P]$ is the set that has property $P$ and no other properties.

Because intensional theory is a perfect dual of extensional nothing interesting is obtained by repeating extensional construction, for example, by building "intensional natural numbers" as

$$0' = U, 1' = [0'], 2' = [0', 1'], \ldots (n + 1)' = [0', \ldots, n'], \ldots$$

What is more interesting, is how intensional and extensional twins meet. With some filial affection it seems:

by uniqum property $[\varnothing] \in\varnothing$, which contradicts the definition of $\varnothing$, also
set $[t\mid false]$ is not a member of any set (perhaps it's a proper class) and set $[t\mid true]$ is a member of every set, which is strange;

a set of which a singleton can be formed has very shallow intentional structure. Indeed:

	$x \unlhd y$
$\equiv$	{ definition of intensional subset }
	$x\in t \Rightarrow y\in t$
$\Rightarrow$	{ substitute $\{x\}$ for $t$}
	$x\in \{x\} \Rightarrow y\in \{x\}$
$\equiv$	{ $x\in \{x\}$ is true by the singleton property, modus ponens }
	$y\in \{x\}$
$\equiv$	{ the singleton property, again }
	$x = y$

To get rid of contradictions and to allow intensional and extensional sets to co-exist peacefully, domains on which singleton and uniqum operations are defined must be narrowed. To be continued.

From the traveller diary.

2010-12-29T19:42:00.002Z

Note to oneself: general anaesthesia is a very efficient cure for jet lag.

2010-02-18T19:20:00.000Z

An obscure generalisation: a redundancy domain should be transversal (better yet, orthogonal) to a potential failure vector. Hello, Karmarkar!

The Hunt for Addi(c)tive Monster 2.

2010-02-04T21:20:00.004Z

In the previous post, we were looking for a monster—a nonlinear additive function. We found that such a function is extremely pathological: it is nowhere locally monotone, nowhere continuous and nowhere locally bounded. Worse than that, it's easy to prove that the graph of a monster is dense in , that is, for every x and y, an arbitrary neighborhood of x contains a point that monster sends arbitrarily close to y.

Recall our attempt to construct a monster. Any additive function is linear on any -set and is fully determined on this set by a value it has in any single of its points. Our Direchlet function derived monster failed (or rather fell) because the slopes an additive function has on different -sets are not independent. Indeed, given that f has a slope on a -set and a slope on a -set , it has to have a slope on a -set . This shows a way to construct a monster: one has to find a collection B of real numbers such that (i) every real number can be represented as a sum , with rational coefficients of which only finite number is non-zero (so that the sum is defined) and (ii) that such representation is unique. Then one can select arbitrary values on elements of B and take moster's value on to be , which is well-defined thanks to (ii).

Looks familiar? It should be: the definition of B is exactly the definition of a basis of a vector space. Real numbers can be added to each other and multiplied by rationals and, therefore, form a vector space over . This space is very different from a usual one-dimensional vector space real numbers form over (i.e., over themselves).

After a streak of bad and unlikely properties that a monster has, we now got something positive: a monster exists if and only if as a vector space over has a basis. Does it?

But of course. Any vector space has a basis—this is a general theorem almost immediately following from the Zorn's lemma. The basis we are looking for even got a name of its own: Hamel basis.

At last we stumbled across the whole family on monsters. Specifically, there exists a set and a function such that every real number r can be uniquely represented as

where only finite number of are non-zero for a given r. From this it immediately follows that .

Take an arbitrary function , and define

Now,

that is, f is additive. Intuitively, is a slope f has at the -set . f is linear if and only if is a constant function, in all other cases f is a monster. If one takes , then

is an especially weird monster function: it takes only rational values!

Note that almost all additive functions are, after all, monsters—only very small sub-set of them is linear.

The Hunt for Addi(c)tive Monster

2010-01-12T15:12:00.042Z

This is another spurious post about mathematics that happened instead of something more useful. Let's talk about one of the most common mathematical objects: a function that maps real numbers () to real numbers. We shall call such a function additive iff for any real x and y

This is a natural and simple condition. Well-known examples of additive functions are provided by linear functions , where k is called a slope. Are there other, non-linear additive functions? And if so, how do they look like? A bit of thinking convinces one that a non-linear additive function is not trivial to find. In fact, as we shall show below, should such a function exist, it would exhibit extremely weird features. Hence, we shall call a non-linear additive function a monster. In the following, some properties that a monster function has to possess are investigated, until a monster is cornered either out of existence or into an example. Out of misplaced spite we shall use technique in some proofs.

First, some trivial remarks about the collection of all additive functions (which will be denoted ).

If , are two additive functions and — an arbitrary real number, then , and are additive. This means that additive functions form a vector space over field with constant zero additive function as a zero vector. This vector space is a sub-space of a vector space of all functions from to . Product of two additive functions is not in general additive (when it is?), but their composition is:

Unfortunately, composition is not compatible with scalars (i.e., ), and additive functions are not an algebra over a field , but see below.

Looking at an individual additive function , it's easy to see that even it is not clear that it must be linear everywhere, there are some subsets of on which is obviously has to be linear:

For any real number x and for any natural number n,

that is, restriction of f to any subset is linear and in particular, f is linear when restricted to the natural numbers. Specifically, , from this

Similarly,

Combining these results, for any rational number ,

That is, f is linear when restricted to any subset of the form . We shall call such subset a -set.

Notice that we just proved that composition of linear functions is compatible with multiplication on rational scalars (see above), so that is an algebra over .

Having briefly looked over the landscape of , let's start converging on our prey. How bad a monster function must be? A linear function has all the good qualities one might wish for: it is monotonic, continuous, differentiable, smooth, it's even... linear. Which of these it enjoys together with a monster? It's intuitively very unlikely that an additive, but non-linear function might happen to be differentiable, so let's start with checking continuity.

Statement 0. If an additive function is continuous at point x, then .

Indeed,

That is, an additive function is linear everywhere it is continuous. This means that a monster must be discontinuous at least in one point. Note that linear functions are precisely everywhere continuous additive functions. Can a monster function be discontinuous in a single point? Or, even, can it be continuous somewhere? It is easy to show that property of additivity constrains structure of sets on which function is continuous severely:

Statement 1. If an additive function is continuous at point x, it is linear.

Take an arbitrary non-zero point y. By statement 0, . By definition of continuity at x,

,

For any natural n, take and find a rational number , such that . Such always exists due to density of rationals. By choice of we have:

and by the sandwich theorem, converges: . Now, again, by choice of : , so y satisfies the condition on x' above and

Taking the (obviously existing) limits of both sides of this inequality, one gets

The case of y being 0 is trivial.

Oh. A monster function cannot be continuous even at a single point—it is discontinuous everywhere. Additive functions are divided into two separated classes: nice, everywhere continuous linear functions and unseemly, everywhere discontinuous monsters. (We still don't know whether the latter class is populated, though.) Our expectations of capturing a monster and placing a trophy in a hall must be adjusted: even if we prove that a monster exists and construct it, an idea of drawing its graph must be abandoned—it's too ugly to be depicted.

Let's think for a moment how a monster might look like. Every additive function is linear on any -set. If it is linear with the same slope on all -sets—it is linear. A monster must have different slopes for at least some of -sets. In the simplest case there is a single -set with a slope different from the others. There is a famous function (a freshman nightmare and examiner delight) immediately coming into a mind: the Dirichlet function, , equal 1 on rationals and 0 on irrationals. The function is identity (and hence linear) when restricted to rationals and is constant zero (again linear) when restricted to irrationals. Looks promising? Unfortunately,

Also, d is continuous at 0 and thus disqualified from monstrousness by statement 1. This shot into darkness missed. At at least we now see that not only monster must have different slopes at different -sets, but these slopes must be selected to be consistent with addition.

Let's return to monster properties. A monster function is discontinuous everywhere, but how badly is it discontinuous? E.g., a function is locally bounded at every point where it is continuous. A monster is continuous nowhere, but is it still locally bounded anywhere or somewhere? In a way similar to statement 1 it's easy to prove the

Statement 2. If an additive function is bounded on any segment [a, b], a < b, then it is linear.

First, by using that , and restricting segment if necessary, one can assume that , and .

Let's prove that f is continuous at 0, then it will be linear by the statement 1. For arbitrary , let's select , such that (this choice is a typical magician hat trick of proofs). For arbitrary x from the -vicinity of 0 there is always a rational q, such that . For such q we have:

on the other hand, we have:

establishing that f is continuous at 0.

This indicates that a monster is not just a bad function, it's a very bad function, that takes arbitrarily large absolute values in arbitrarily small segments. Too bad. As a byproduct, a monster cannot be monotonic on any segment, because a function monotonic on [a, b] is bounded there: (for increasing function, similarly for decreasing).

[continued.]

To the Lustre Group people

2009-09-20T14:33:00.002Z

With the best wishes to Sun^WOracle, and sapienti sat.

a trivial exercise.

2009-08-21T11:07:00.015Z

Let's find a sum

There is a well-know standard way, that I managed to recall eventually. Given that

the sum can be re-written as

with almost all terms canceling each other, leaving

While this is easy to check, very little help is given on understanding how to arrive to the solution in the first place. Indeed, the first (and crucial) step is a rabbit pulled sans motif out of a conjurer hat. The solution, fortunately, can be found in a more systematic fashion, by a relatively generic method. Enter generating functions.

First, introduce a function

The series on the right converge absolutely when |t| < 1, so one can define

with the sum in question being

Definition of the g function follows immediately from the form of the original sum, and there is a limited set of operations (integration, differentiation, etc.) applicable to g to produce f.

The rest is more or less automatic. Note that

so that

therefore

where the integral is standard. Now,

Voilà!

And just to check that things are not too far askew, a sub-exercise in a pointless programming:

scala> (1 to 10000).map(x => 1.0/(x*(x+2))).reduceLeft(_+_)
res0: Double = 0.749900014997506

PS: of course this post is an exercise in tex2img usage.

A Modest Proposal: For Generalizing the Field Access in C Programming Language, and for Making It Beneficial to the Public.

2009-04-23T09:23:00.006Z

[This is an old and never finished draft. HTML produced by asciidoc.]

A Modest Proposal: For Generalizing the Field Access in C Programming Language, and for Making It Beneficial to the Public.

2009.04.22

Nikita Danilov <danilov@gmail.com> v0.1, September 2007

Abstract

A proposal is made to modify C language to make accessing struct and union fields (s.f and p->f) more flexible. To that end, instead of considering .f and ->f as families of unary postfix operators applicable to the values of struct and union types and pointers, respectively, fields are treated as values or special member designator types introduced for this purpose, while . and -> become binary operators. Typing rules for the field types and examples of their usage are proposed.

References in square brackets are to the ISO/IEC C standard.

Overview

One of the important advantages of C language is the (relative) simplicity and cleanness of its memory model: data structures eventually boil down to the “objects” [3.15], addressable by pointers and contiguous in address space. This is most evident in the case of array subscription [6.5.2.1], that is defined through the pointer arithmetic:

[6.5.2.1] International Standard ISO/IEC 9899

       Semantics

 [#2] A postfix expression followed by an expression in square
 brackets [] is a subscripted designation of an element of an
 array object.  The definition of the subscript operator [] is
 that E1[E2] is identical to (*((E1)+(E2))).  Because of the
 conversion rules that apply to the binary + operator, if E1 is
 an array object (equivalently, a pointer to the initial element
 of an array object) and E2 is an integer, E1[E2] designates the
 E2-th element of E1 (counting from zero).

Not only array subscription thus defined makes arrays and pointers mostly equivalent, but it also inherits all the good properties of addition (commutativity, associativity), and automatically defines the meaning of multidimensional arrays.

Another fundamental operation, structure and union member de-reference [6.5.2.3] is not, however, similarly reduced to the pointer manipulations. Instead, the “Types” [6.2.5] section defines types of a sequential (structure) and overlapping (union) sets of member objects, and operations are later described abstractly as accessing member objects:

[6.5.2.3] International Standard ISO/IEC 9899

 Semantics
 
 [#3] A postfix expression followed by the . operator and  an
 identifier  designates  a  member  of  a  structure or union
 object.  The value is that of the named member,  and  is  an
 lvalue  if  the first expression is an lvalue.

The inflexibility of this definition is clear when compared with what one can do with the arrays: C permits nothing similar to foo(a0,a1)[bar(b0.b1)] for structure and union member access. Standard offsetof() macro [7.17] converts member designator to an integer constant, equal to the member byte offset within the structure of union, but no support at the syntax level exists.

We propose to introduce a family of scalar types representing member designators and to define . and -> operations in terms of values of these types, in fact, in the way very similar to how array subscription is defined.

The perceived advantages of this are:

array and structure operations become similar;
structure and union operations are reduced to (already defined) pointer manipulations, improving orthogonality of the language;
more generic structure-like data types are introduced for free, see below.

Note that in some sense this is not a new development. Vintage C code fragments sport usage like

v6root/usr/sys/ken/iget.c

 iupdat(p, tm)
  int *p;
  int *tm;
  {
         register *ip1, *ip2, *rp;
        int *bp, i;

        rp = p;
        if((rp->i_flag&(IUPD|IACC)) != 0) {
         ...

indicating that member designators (i_flag in this case, look at the interesting declaration of rp) weren't originally tied to a specific structure or union type. They were, in fact, existing by themselves in a special global namespace—a property that led to the custom of prefixing field names with a unique prefix.

Informal proposal

A new derived type constructor -> is introduced. A declarator

       TYPE0 -> TYPE1

specifies a type of a member designator for a member object with a type TYPE1 in a type TYPE0.

A declarator

       TYPE0 -> TYPE1 :N:M

where N and M are integer constants, specifies a type of a member designator for a bit-field of a member object starting at Nth bit and containing M bits.

Values of any member designator type can be cast to int and back without loss of information, passed to and returned from the functions, etc. A declaration of the form

       STRUCT-OR-UNION IDENTIFIER {
               TYPE0 FIELD0;
               TYPE1 FIELD1;
               ...
       };

implicitly defines constants of the corresponding member designator types for all members of STRUCT-OR-UNION IDENTIFIER type. Defined constants have values designating their eponymous structure of union members. For example,

 struct F {
               int              F_x;
               float            F_y[10];
               void          *(*F_f)(int, struct F *);
               unsigned char    F_b:1;
 };

implicitly defines

       const struct F -> int                        F_x;
       const struct F -> float[10]                  F_y;
       const struct F -> void *(*)(int, struct F *) F_f;
       const struct F -> unsigned char :X:1         F_b; /* for some X */

For any non bit-field member FIELD it holds that

       offsetof(STRUCT-OR-UNION IDENTIFIER, FIELD) == (int)FIELD

Following operations are defined on values of member designator types:

given an expression E0 of type “pointer to T0”, and an expression E1 of type T0 -> T1, E0->E1 is equivalent to
```
           *(T1 *)(((char *)E0) + E1)
   
```
where E1 is implicitly converted to an integer type;
given an expression E0 of type A -> B and an expression E1 of type B -> C, expression E0.E1 has type A -> C, and corresponds to the member of B, viewed as a member of A;
given an expression E of type A -> B, a unary expression -E has type B -> A, and designates an instance of A in which an instance of B designated by E is embedded;
a compound assignment E0 ->= E1 is defined as an abbreviation for E0 = E0->E1, with E0 evaluated only once.

Examples

Example: Basic usage

struct F {
       int F_x;
};

struct G {
       int      G_y;
       struct F G_f;
};

void foo() {
       struct G  g;
       struct F *nested;

       printf("designators: %i %i %i\n", F_x, G_y, G_f);
       g.G_y = 1;     /* defined as *(g + G_y) = 1; */
       g.G_f.F_x = 2; /* defined as *(g + G_f.F_x) = 2; */
       nested = &g.G_f;
       /* nested->(-G_f) is g */
       assert(nested->(-G_f).G_y == 1);
       /* or... */
       assert(nested->(-G_f.G_y) == 1);
}

Example: Searching for an item in a linked list


struct list_link {
       struct list_link *ll_next;
}

struct list_item {
       struct list_link li_next;
       int               li_value;
};

struct list_link *search(struct list_link *s, int key) {
       for (; s && s->-li_next.li_value != key; s ->= li_next) {
              ;
       }
       return s;
}

Note that foo->-bar subsumes container_of() macro (as used in the Linux kernel).

C is traditionally used as a language for the system programming—a domain where one has often to deal with formatted data on the storage or network. As a typical example let's imagine a system that keeps formatted meta-data, e.g., a list of directory entries for a file system or index entries for a data-base in a block device block. Different devices have different block sizes, which means that in general case format of a device block cannot be described by a C structure type. With member designator types, however, something similar to the following can be done:

/* variable sized device block */
typedef char * block_contents_t;

struct block_format {
       /* magic number at the beginning of the block */
       block_contents_t -> uint32_t bf_start_magic;
       /* array of keys in the index block, growing to the right */
       block_contents_t -> key_t[]  bf_keys;
       /* array of values, corresponding to the keys, growing to the left */
       block_contents_t -> val_t[]  bf_values;
       /* magic number at the end of the block */
       block_contents_t -> uint32_t bf_end_magic;
};

struct system_descriptor {
      ...
      struct block_format sd_format;
      ...
};

void init(struct system_descriptor *desc, int block_size) {
      switch (block_size) {
             case 512:
                    desc->sd_format.bf_keys      = ...;
                    desc->sd_format.bf_values    = ...;
                    desc->sd_format.bf_end_magic = ...;
                    break;
             case 1024:
                    ...
      }
}

int block_search(struct system_descriptor *desc, block_contents_t block,
                key_t *key) {
       int i;

       assert(block->(desc->bf_start_magic) == START_MAGIC);
       assert(block->(desc->sd_format.bf_end_magic) == END_MAGIC);

       for (i = 0; i < NUM_KEYS; ++i) {
               if (key_cmp(&(block->(desc->sd_format.bf_keys))[i], key) {
                       ...
}

Clearly, quite generic yet type-safe data structures can be built this way.

Problems

Backward compatibility is broken because field names must be unique within a compilation unit now (as they have constants declared for them). This is “safe” violation of compatibility in that it doesn't change the semantics of an existing code silently.

Meaning of E0.E1 for a non-lvalue E0 is awkward to define.

It _could_ be done

2009-03-25T14:20:00.005Z

The late André Bensoussan worked with me on the Multics [...]. We were working on a major change to the file system [...].

André took on the job of design, implementation, and test of the VTOC manager. He started by sitting at his desk and drawing a lot of diagrams. I was the project coordinator, so I used to drop in on him and ask how things were going. "Still designing," he'd say. He wanted the diagrams to look beautiful and symmetrical as well as capturing all the state information. [...] I was glad when he finally began writing code. He wrote in pencil, at his desk, instead of using a terminal. [...]

Finally André took his neat final pencil copy to a terminal and typed the whole program in. His first compilation attempt failed; he corrected three typos, tried again, and the code compiled. We bound it into the system and tried it out, and it worked the first time.

In fact, the VTOC manager worked perfectly from then on. [...]

How did André do this, with no tool but a pencil?

Those people were programming operating system kernel that supported kernel level multi-threading and SMP (in 60s!), had most features UNIX kernels have now and some that no later operating system has, like transparent HSM. All under hardware constraints that would make modern washing machine to look like a super-computer. Of course they were thinking, then typing.

Leisure pace of progress

2007-08-08T22:53:00.000Z

Recently I found a paper in ACM Library describing two distributed file systems with the following features:

distributed read-write locking at the byte granularity;
user visible distributed transactions with isolation and roll-back;
capability based authentication;
files implemented as B-trees;
distributed garbage collection of unreferenced objects;
atomicity through COW (aka shadow writes, aka wandering logs);
intent logging of file system updates (hello, ZFS);
storage failure resilience methods, similar to ones in TileFS;
directories implemented as separate service, using the same interface as usual clients.

Quite impressive and obviously matched by nothing publicly available currently. How it happened that these marvels are not trumpeted about on every corner? Very simple: these systems were put in production before 1981. AD, that is. Funny enough, one of them is even named CFS.

[0] James G. Mitchell, Jeremy Dion A comparison of two network-based file servers
[1] Jeremy Dion The Cambridge File Server

Denver Zoo

2007-07-18T19:47:00.000Z

How to keep a couple of linux kernel developers busy for a day:

And now to the subject of death.

2007-06-27T21:20:00.001Z

As little as I want to go into this, some misunderstanding is to be cleared. Recent interview [/.] with jailed Hans Reiser, by Joshua Davis, concludes with the following, presumably ominous paragraph:

While he launches into the intricacies of database science, I'm thinking, "Where is the front passenger seat of your car?" He has never explained this. It seems a fundamental hole in his defense. But he won't stop talking. When I try to interrupt, he insists I let him finish. It's as if the file system holds all the answers. So I take the hint, and that night, in my office, I start scouring the 80,496 lines of the Reiser4 source code. Eventually I stumble across a passage that starts at line 78,077. It's not part of the program itself — it's an annotation, a piece of non-executable text in plain English. It's there for the benefit of someone who has chosen to read this far into the code. The passage explains how memory structures are born, grow, and eventually die. It concludes: "Death is a complex process."

The phrase in question is a part of a large top-of-the-file comment in znode.c, describing, indeed, among other things, a life-cycle of znode (Zam's node) data-structure. But

It is not quoted verbatim (for a better effect, as one is left to assume). Grammatically incorrect original reads:

znode.c

   ...
   5. His death.

   Death is complex process.

   When we irrevocably commit ourselves to decision to remove node from the
   tree, JNODE_HEARD_BANSHEE bit is set in zjnode.state of corresponding
   znode. This is done either in ->kill_hook() of internal item or in
   kill_root() function when tree root is removed.
   ...

and, it was me rather than Hans who wrote this. It was long, long time ago, but I believe SCM logs are still here to prove this.

File system replacement algorithms (cont.)

2006-10-30T19:00:00.000Z

Previous item.

3. User level tools.

Replacement algorithms simulator is in replacement.c. It consists of conventional main loop that reads preprocessed trace records and feeds them to selected replacement algorithm. Replacement algorithms (struct repalg) are executed in the following standard environment:

Primary storage (memory) which is an array (mm.m_frames[]) of a given (through command line option) number of equal sized frames (struct frame). Some frames are occupied by pages, others are free. Replacement algorithm may maintain some private information for each frame.
Secondary storage which is an array mm.m_vpages[] of a given number of pages (struct vpage). This can be thought as a set of all distinct pages ever accessed by a trace being processed. Each page, in addition to its index in this array, is uniquely identified by a file and logical offset within this file. At any given moment in time page is either resident (i.e., loaded into some frame in memory) or non-resident. Replacement algorithm may maintain some private information for each page.
Array (mm.m_objects[]) of files (struct object). Each file maintains a list of all its pages (not frames!). This is needed for efficient emulation of truncate, see below.

These data structures simplify implementation of replacement algorithms, but do not directly match information available in the trace. This gap is filled by preprocessing script fslog.awk that reads in whole trace and generates unique numeric identifiers for pages and files (these identifiers are used as array indices by replacement emulator). Script also does some additional book-keeping, collects few statistical counters, and does rudimentary sanity checking of the trace. Key point is to reliably tell when pages belong to the same or to the different files. Obvious solution of using (dev, ino) pair as a unique file identifier doesn't work, because certain popular file systems tend to reuse inode numbers immediately after file deletion, leading to false positives. This is why trace record contains additional ->fr_gen and ->fr_name fields: tuple (dev, ino, generation, name) is reliable file identity.

Another complication arises with truncate handling. In all other cases trace records produced by kernel map one to one into page accesses, handled by replacement algorithm. But in the case of truncate, kernel walks a list of resident pages only. Producing trace records for each walked page isn't what we want, because this list depends on a replacement policy implemented by kernel. Instead, tracing patch generates only one record for whole truncate operation, with ->fr_index field indicating the first page to be truncated. For such record replacement.c walks a list of all pages, associated with corresponding file and calls page based truncate entry point (repalg.m_punch()) of replacement algorithm. It is to implement this walking efficiently that files exist as a first class entities in replacement.c.

The only remaining bit is converting binary trace records into form suitable for fslog.awk. This is done by fslog.c based on exported-global.c sample program from relayfs package.

4. Results.

4.0. Experiment description.

Analyzed trace was obtained by running

$ make defconfig && make -j4 bzImage modules

on a single processor machine (other machine characteristics such as memory size and available secondary storage do not matter, as was explained above) in 2.6.18-rc2 kernel source directory. In addition trace contains records generated during system boot-up. To avoid cluttering the trace with records generated by fslog.c writes, its output was transferred to other machine by netcat(1). Total amount of output was 2.7GB (not provided due to size).

fslog.awk processed 25927993 records, accessing total of 2356222 pages in 86839 distinct files. Resulting trace, suitable as input to replacement.c is here (79MB), file identities are here.

Following replacement algorithms were tested:

RANDOM
LRU (least recently used)
FIFO (first in, first out)
FIFO2 (fifo, second chance)
SFIFO (segmented fifo, by Rollins Turner and Henry Levy)
2Q (by Theodore Johnson and Dennis Shasha)
CAR (by Sorav Bansal and Dharmendra S. Modha)
ARC (by Nimrod Megiddo, Dharmendra Modha)
LINUX (emulation of mm/vmscan.c)
WORST (theoretically worst possible replacement)
OPT (theoretically optimal clairvoyant algorithm by Belady)

RANDOM, FIFO, FIFO2, LRU and Segmented FIFO are „classical“ replacement algorithms invented and extensively studied in 60s. 2Q, CAR and ARC are „new“ algorithms developed recently as interest to replacement policies reappeared. OPT and WORST algorithms cannot be implemented in practice, because they are both „clairvoyant“ — they look ahead through the trace. LINUX algorithm tries to emulate mm/vmscan.c with the following limitations and simplifications:

no mapped or anonymous pages;
no kswapd, only direct reclaim;
all allocations are with GFP_FS;
no non-fs caches;
no low_page reserves;
single zone.

which is reasonable for comparison of file system dominated non-degenerate work-loads.

2Q and SFIFO have tunable parameters (see their papers referenced above for description of parameters). 2Q was tested with kin of 25, and kout ranging from 10 to 50 with step 10. kout of 10 proved to produce best results, and this value was used in comparison with other algorithms. SFIFO was tested „tail lru percentage“ from 0 (pure FIFO) to 20, with very small observed effect on results. All other algorithms are self-tuning.

All algorithms were ran against the same trace, and tested with the same set of memory sizes (varying from 5 to 4M frames, which corresponds to 20KB—16GB range of memory sizes with 4K frame).

Results, together with shell commands used to produce them are available here. A couple of notes:

OPT algorithm is extremely slow (as expected);
LINUX algorithm fails for very small memories (less than 64 frames).

4.1. Graphs: overall.

Below are few graphs, created by gnuplot script (input files for gnuplot are generated by process.hits, and PNG images are generated from postscript by generate-png). Everywhere X-axis (horizontal) is memory size (logarithmical), and Y-axis (vertical) is hit ratio in percents, unless specified otherwise.

First, all algorithms on the single graph:

One immediate observation is that for memories larger than 28MB difference between algorithms is very small. Another notable thing is that in 56KB—6MB range LINUX algorithms is worse than everything except WORST. Remarkably it's even worse than RANDOM, which surely is quite a feat of engineering.

Next graph shows how algorithms improve upon WORST. Here Y-axis is difference between hit ratio of algorithm and WORST for corresponding memory size.

As it is by definition impossible to not beat WORST, improvement (or lack thereof) against RANDOM is also useful measure:

Next graph shows how far algorithms fall behind OPT. In this graph Y-axis is given by 100.0 - hit_ratio(OPT) + hit_ratio(ALG), that is, OPT corresponds to 100.0.

Revealed behavior is quite interesting. For very small memory sizes, all algorithms perform more or less equally bad, but as memory size increases, OPT quickly outperforms everything else. This corresponds to the initial dip in the 32KB—512KB range. After that point, non-OPT algorithms really start „working“ and gradually approach OPT, reaching (in concert!) local optimum somewhere in 32MB—64MB range. But as memory size increases even more, all of them start lagging behind OPT more and more again. In 512MB—16GB range all algorithms converge, because in this here where total working set of the work load in question lies, and once work set fits into memory it is hard to behave too bad.

Second local minimum is rather strange. As it happens for all non-OPT algorithms in a regular manner, it's logical to assume that it is result of some property of the work-load in question. One might hypothesize, that in this range of memory sizes, OPT algorithm is able to exploit some long-term patterns in file system accesses during kernel build.

4.2. Graphs: tunable parameters.

Next, let's look how tunable parameters affect 2Q and SFIFO performance:

Labels are in 2Q:kin:kout format. Obviously, the smaller kout the better, and 2Q indeed beats LRU most of the time, in accordance with claims of its authors.

The same for SFIFO.

Segmented FIFO keeps frames in two lists: head and tail. Head list (containing „hot“ pages) is maintained in FIFO discipline, and tail list — in LRU discipline. Size of the tail list is set to fixed percentage of full memory (when this percentage is 0, SFIFO degenerates into FIFO. When it is 100.0, SFIFO becomes LRU.). The logic behind this is that by making tail LRU list sufficiently small it becomes practically feasible to implement LRU in it by un-mapping pages on entry to tail list. Our results show that for all reasonable sizes of tail list, difference in hit ratio is negligible.

4.2. Graphs: classical algorithms.

Let's look at some data of historical interest: how „classical“ replacement algorithms (LRU, FIFO, and FIFO2) behave relative to OPT, WORST, and RANDOM (LINUX is shown here too, because it basically falls into the same class of algorithms).

Classical algorithms versus WORST:

And versus OPT:

It's interesting to look how these algorithms behave in the memory ranges typical for the time when they were actively researched:

2MB—32MB range:

At some points difference in hit ratios can reach 5%, but as we move to larger memories (16MB—4GB)...

difference shrinks to ~1% range and remains there (256MB—4GB):

4.3. Graphs: LINUX.

At last, compare how LINUX fares relative to other algorithms. We shall concentrate on data for large memories (64MB—4GB range), because behavior of LINUX algorithm in low memory setups is clearly visible at the overall graph: it loses to everyone.

The natural question arises: why LINUX algorithm is so... not brilliant (albeit, keep in mind that all this happens only few percent within OPT, so not too much is at the stake)? As was noted at the beginning, unified FS/VM caching forces replacement algorithm to use only bare minimum of available per-page information. In particular, it so happens that for clean file system pages, LINUX is equivalent to FIFO (known bad algorithm), and for dirty pages — to FIFO2.

5. Conclusion.

Assorted miscellaneous notes, actually.

One thing obvious from traces, but not mentioned above is that larger portion of all trace records is for page faults. Absolute majority of them are compulsory misses that happen because every new process maps all standard libraries into its address space. By looking at the traces, it seems that optimizations in this area (e.g., pre-mapping all already resident pages of the given library) would be clearly advantageous.

Handling of file system pages by LINUX algorithms can definitely be improved.

6. Future directions.

More algorithms are to be implemented in replacement.c: LFU, LRU/k, LIRS, etc. Also, more statistics (working set size, page fault rate, etc.) can be collected.

File system replacement algorithms.

2006-10-29T22:08:00.000Z

1. Introduction.

This article describes results of a bit of research I made on efficiency of file system cache replacement algorithms. As everybody knows file system tries to keep some portions of its backing secondary storage (disk) cached in the primary storage (memory). In particular portion of file system data or meta-data that is being accessed right now has to be present in the memory, because kernel cannot directly manipulate data on the disk. Replacement problem occurs when this cache grows too large (which it tends to do sooner or later, as secondary storage is usually much larger than memory). When cache cannot grow anymore, and new data have to be accessed, something has to be thrown out of the cache. The selection of cache item to be removed is made by replacement algorithm. Choice of this algorithm affects file system performance, because if/when item removed from cache is re-accessed, file system has to wait for disk IO to read it again. Replacement algorithms try to minimize this overhead, by using various statistical information and trying to predict future accesses. The very possibility of such predictions is based on assumed regularities in file system accesses, most notable being locality of reference and access patterns, such as sequential file scanning. Research in replacement algorithms is as old as file systems, but few last decades in was mainly done in the context of data base engines (that also cache part of database in the memory). The reason for this is that in most modern operating system kernels file system caching was unified with VM caching. Perceived advantages of this unification are:

simplification,
support of mmap(2) style accesses to file system, and
sharing of memory between file system and VM, without imposing artificial limits on size of each cache.

The latter goal was never fully achieved: all existing implementations treat file system and VM pages differently to some extent, because system performance is miserable otherwise. This hints that access patterns are so different for file system and VM pages, that unified caching is not necessary the best solution. Another problem with unified caching is that the same replacement algorithm has to be used, and this basically means that replacement algorithm may rely only on information available for both file system and VM pages to make its decisions. As a set of attributes that file system can maintain for its pages is a strict superset of attributes maintained for VM pages, unified replacement algorithm degenerates into a VM replacement algorithm and all additional hints that file system can provide are thrown away. Experiments described below are an attempt to determine whether separate replacement algorithm can improve file system performance. To measure efficiency of replacement algorithms file system traces were collected, and then processed by a user-level simulator. Trace is a sequence of records each describing a particular access to some page of a file (see details below). User level simulator processes trace record by record, emulating both memory and secondary storage, keeping track of currently cached pages, and performing replacement decisions when necessary (also, see below for details).

2. Tracing method.

An important point in collecting file system traces is to make them independent from caching and replacement algorithms implemented in the kernel being traced. This, for example, rules out placing tracepoints at the level of struct address_space_operations (or below), because code at that level is invoked by VM, and as a result sequence of event depends on algorithms used by VM. On the other hand, placing tracepoints at the syscall/VFS level is not very convenient either, because, while usable for tracing access to data pages (read/write/truncate), it is not adequate for tracing meta-data. The only remaining possibility is to put tracepoints into file system driver, but that would require changing all file systems. As a compromise, tracepoints were placed in mm/filemap.c, mm/readahead.c and mm/truncate.c "generic" code that is used by many file systems:

do_generic_mapping_read(): intercepts reads

filemap_nopage(): intercepts page faults on file system pages
__grab_cache_page(): intercepts writes
truncate_inode_pages_range(): intercepts truncates
__do_page_cache_readahead(): intercepts readahead

All tracepoints look exactly the same:

tracepoint

 fslog(mapping, index, page, opcode);

Where mapping is an object (inode) on which operation is preformed, index is a logical offset of accessed page within object, page is a page itself, if present, NULL otherwise, and opcode is operation code, one of

enum fslog_rec_type

enum fslog_rec_type {
        FSLOG_READ,    /* read */
        FSLOG_RA,      /* read-ahead */
        FSLOG_WRITE,   /* write */
        FSLOG_PFAULT,  /* page-fault */
        FSLOG_PUNCH    /* page truncate */
};

fslog() packs arguments into standard event record:

struct fslog_record

struct fslog_record {
        __u32 fr_no;       /* monotonically increasing event counter.
                              Used to detect lost events. */
        __u32 fr_time;     /* event time in microseconds. */

        __u32 fr_dev;      /* major:minor of device, where file is located. */
        __u32 fr_ino;      /* file inode number */

        __u32 fr_gen;      /* file inode generation. */
        __u32 fr_index;    /* logical index of accessed page. */

        __u16 fr_pid;      /* pid of process. */
        __u8  fr_type;     /* access type, taken from enum fslog_rec_type. */
        __u8  fr_bits;     /* miscellaneous page bits. */
        __u32 fr_pad;      /* alignment padding. */

        char  fr_comm[16]; /* "process name". */
        char  fr_name[16]; /* "file name". */
};

That might looks like awfully excessive amount of information, but it's necessary to reliably identify unique pages and files, as will be shown below. Once record is composed, it is exported to the user space through relayfs. Tracing patch for 2.6.18-rc2 kernel is available here. Continued.

A voice of the reason from the distant past

2006-07-22T19:33:00.000Z

Dedicated to VM and file system developers and researches...

It is immediately apparent from these figures that moving-arm disks should never be used, neither for paging applications nor for any other heavy-traffic auxiliary memory applications.

Peter J. Denning -- Virtual Memory.

--Tags:-[Kernel]-[VM]-----------

reiser4: 1. internal tree

2006-03-26T20:01:00.000Z

reiser4: 1. internal tree

This continues previous entry: introduction

0. B-trees overview
1. lookup and modification
2. lookup optimizations

0. B-trees overview

B-tree is am umbrella term for a variety of similar algorithms used to implement dictionary abstraction suitable in a form suitable for external storage. Reiser4 version of this algorithms, officially known as a dancing tree is closest to the B⁺-tree. Basically, in B⁺-tree user-supplied data records are stored in leaf nodes. Each leaf node keeps records from some particular key range (adjusted dynamically). Each leaf node is referenced from its parent: this reference is a pointer to the child (block number usually) and the smallest key in the key range covered by this leaf. Parent node contains multiple references to its children nodes, again from some particular key range. Parent node may have its own parent and so on until whole key space is covered.

Compare this with B-trees proper, where data records are stored at the levels other than leaf one. Also compare this with radix tree (aka PATRICIA) where key range covered by given node is uniquely determined by its level rather than adjusted dynamically as in B-trees.

Contents of reiser4 internal tree are initially stored on the disk. As file system operations go on, some blocks from the tree are read into memory and cached there. When new node is added to the tree, it first exists as a block-size buffer in memory. Under some conditions portions of tree are written out from memory back to the stable storage. During write-out, nodes that were marked dirty (either as a result of a modification, or because they are newly created), are written to the appropriate disk block and marked clean. Clean nodes can be discarded from memory.

1. lookup and modification

Lookup operation locates a record with a given key in a tree, or locates a place where such record will be inserted (this place is uniquely identified by a key) if it doesn't exist yet. All other tree operations start with lookup, because they have to find a place in a tree identified by given key.

Roughly speaking, lookup starts from the top of the tree, searches through index node to find it which of its children given key falls, loads that child node and repeats until it gets to the leaf level. One can say that lookup is top-to-bottom tree operation.

This poses two questions:

What is the top of a tree and how to find it?
How to find out which child node to proceed with?

First question seems trivial, because every tree has a root node, right? The problem is that, as will be explained below, concurrent tree modification operation may grow the tree by adding new root to it (so that old root becomes child of a new one), or shrink it by killing existing root. To avoid this, reiser4 tree has special imaginary node, existing only in memory that logically hangs just above root node. First of all, lookup locks this node and learns location of root node from it. After this, it loads root node in memory and releases the lock. This imaginary node is called uber-node. Curiously enough, Sun ZFS uses exactly the same term for the very similar thing. They even have 0x00babl0c magic number in their disk format, that is supposed to be as close as possible to the pronunciation of "uber block" (even more funny, "bablo" is Russian slang word for money, bucks).

To make search for a child node containing given key efficient, keys in the parent node are stored in an ordered array, so that binary search can be used. That binary search is (under many workloads) the single most critical CPU operation.

Now we known enough to code reiser4 lookup algorithm:

reiser4/search.c:traverse_tree()

traverse_tree(key) {
        node     *parent; /* parent node */
        node     *child;  /* child node */
        position  ptr;    /* position of record within node */

        child = ubernode;
        ptr   = ubernode.root; /* put root block number in ptr */

        while (!node_is_leaf(child)) {
                parent = child;
                /* load node, stored at the given block, into memory */
                child = node_at(ptr);
                lock(child);
                ptr = binary_search(child, key);
                unlock(parent);
        }
        return ptr;
}

Few comments:

position identifies a record within node. For leaf level this is actual record with user data, for non-leaf levels, record contains pointers to the child node.
note that lock on the child node is acquired before lock on the parent is released, that is, two locks are held at some moment. This is traditional tree traversal technique called lock coupling or lock crabbing.
traverse_tree() returns with ptr positioned at the record with required key (or at the place where such record would be inserted) and with appropriate leaf node locked.

As was already mentioned above, tree lookup is comparatively expensive (computationally, if nothing more) operation. At the same time, almost everything in reiser4 uses it extensively. As a result, significant effort has been put into making tree lookup more efficient. Algorithm itself doesn't leave much to be desired: its core is binary search and it can be optimized only that far. Instead, multiple mechanisms were developed that allows to bypass full tree lookup under some conditions. These mechanisms are:

seals
vroot
look-aside cache (cbk cache)

1.1. seals

A seal is a weak pointer to a record in the tree. Every node in a tree maintains version counter, that is incremented on each node modification. After lookup for a given key was performed, seal can be created that remembers block number of found leaf node and its version counter at the moment of lookup. Seal verification process checks that node recorded in the seal is still in the tree and that its version counter is still the same as recorded. If both conditions are met, pointer to the record returned by lookup can still be used, and additional lookup for the same key can be avoided.

1.2. vroot

Higher-level file system object such as regular files and directories is represented as a set of tree records. Keys of these records are usually confined in some key range, and, due to the nature of B-trees, are all stored in the nodes having common ancestor node that is not necessary root. That is, records constituting given object are located in some subtree of reiser4 internal tree. Idea of vroot (virtual root) optimization is to track root of that sub-tree and to start lookups for object records from vroot rather than from real tree root. vroot is updated lazily: when lookup finds that tree was modified so that object subtree is no longer rooted at vroot, tree traversal restarts from real tree root and vroot is determined during descent.

Additional important advantage of vroot is that is decreases lock contention for the root node.

1.3. look-aside cache

Look-aside cache is simply a list of last N leaf nodes returned by tree lookup. This list is consulted before embarking into full-blown top-to-bottom traversal. This simple mechanism works due to locality of reference for tree accesses.

To be continued:

2. concurrency control: lock ordering, hi-lo ordering
3. eottl
4. node format

--Tags:-[reiser4]-[Kernel]-----------

Jon Beck dies

2006-03-22T07:59:00.000Z

Jon Beck, author of Beck's condition, died suddenly on March 11.

--Tags:-[Mathematics]-----------

Why windows will collapse ultimately

2006-03-03T18:31:00.000Z

Subject: [ntdev] WdfUsbTargetDeviceSendControlTransferSynchronously and timeouts

update: Like this wasn't enough. Below are excerpts from

find . -name \*dll |        xargs strings -- |        grep -i '^[a-z0-9_]*$' |        awk '{ print length($1) "\t" $1 }' |        sort -n

output (executed in WinXP system directory):

50      ZwAccessCheckByTypeResultListAndAuditAlarmByHandle
51      Java_NPDS_npDSJavaPeer_SetSendMouseClickEvents_stub
51      Java_NPDS_npDSJavaPeer_SetShowPositionControls_stub
51      JET_errDistributedTransactionNotYetPreparedToCommit
52      ACTIVATION_CONTEXT_SECTION_COM_INTERFACE_REDIRECTION
52      ConvertSecurityDescriptorToStringSecurityDescriptorA
52      ConvertSecurityDescriptorToStringSecurityDescriptorW
53      ACTIVATION_CONTEXT_SECTION_GLOBAL_OBJECT_RENAME_TABLE
55      ACTIVATION_CONTEXT_SECTION_COM_TYPE_LIBRARY_REDIRECTION
55      SxspComProgIdRedirectionStringSectionGenerationCallback
56      Java_NPDS_npDSJavaPeer_GetSendOpenStateChangeEvents_stub
56      Java_NPDS_npDSJavaPeer_GetSendPlayStateChangeEvents_stub
56      SxspComTypeLibRedirectionStringSectionGenerationCallback
57      SxspComputeInternalAssemblyIdentityAttributeBytesRequired
57      SxspWindowClassRedirectionStringSectionGenerationCallback
62      SxspComputeInternalAssemblyIdentityAttributeEncodedTextualSize
62      SxspGenerateTextuallyEncodedPolicyIdentityFromAssemblyIdentity
64      RtlpQueryAssemblyInformationActivationContextDetailedInformation
71      RtlpQueryFilesInAssemblyInformationActivationContextDetailedInformation

which probably gives us the champion. As a comparison, for linux-2.6.15

find . -type f -follow -name '*.[chS]' |        xargs grep -hi '[a-z0-9_]\{70,\}' -- /dev/null

gives:

70 ZORRO_PROD_PHASE5_BLIZZARD_1230_II_FASTLANE_Z3_CYBERSCSI_CYBERSTORM060

So windows is one character closer to hell than linux.

--Tags:-[Programming]-[Windows]-----------

ext3: magic, more magic.

2006-02-01T20:02:00.000Z

ext3 htree code in Linux kernel implements peculiar version of balanced tree used to efficiently handle large directories.

htree directory consists of block sized nodes. Some of them (leaf nodes) contain directory entries in the same format as ext2. Other nodes contain index: they are filled with hashes and pointers to other nodes.

When new file is created in a directory, a directory entry is inserted in one of leaf nodes. When leaf node has not enough space for new entry, new node is appended to the tree, and part of directory entries is moved there. This process is known as a split. Pointer to new node is then inserted into some index node, and new node can overflow at this point, causing another split and so on.

If splits occur whole way up to the root of the tree, new root has to be added (tree grows).

It's obvious that in the worst case (extremely rare in practice) insertion of a new entry may require a new block on each tree level, plus new root, right? Now, looking at the ext3_dx_add_entry() function we see something strange:

fs/ext3/namei.c:ext3_dx_add_entry()

                 } else {
                         dxtrace(printk("Creating second level index...\n"));
                         memcpy((char *) entries2, (char *) entries,
                                icount * sizeof(struct dx_entry));
                         dx_set_limit(entries2, dx_node_limit(dir));
 
                         /* Set up root */
                         dx_set_count(entries, 1);
                         dx_set_block(entries + 0, newblock);
                         ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
 
                         /* Add new access path frame */
                         frame = frames + 1;
                         frame->at = at = at - entries + entries2;
                         frame->entries = entries = entries2;
                         frame->bh = bh2;
                         err = ext3_journal_get_write_access(handle,
                                                              frame->bh);
                         if (err)
                                 goto journal_error;
                 }

At this moment entries points to the already existing full node and entries2 to the newly created one. As one can see, contents of entries is shifted into entries2, and entries is declared to be new root of the tree. So now tree has a root node with a single pointer to the index node that... still has not enough free space (remember entries2 got everything entries had). Omitted code that follows proceeds with splitting leaf node, assuming that its parent has enough space to insert a pointer to the new leaf. So how this is supposed to work? Or, does this work at all? That's tricky part and the curious reader is invited to try to infer what's going on without looking at the rest of this post.

[full text follows]

The answer is simple: by ext3 htree design, capacity of the root node is smaller than that of non-root index one. This is a byproduct of binary compatibility between htree and old ext2 format: root node is always the first block in the directory and it always contains dot and dotdot directory entries. As a result, when contents of old root is copied into new node, that node ends up having enough space for two additional entries.

This is obviously one of the worst hacks and least documented at that. Shame.

Thanks to Alex Tomas for clearing this mystery for me. As he says: "Htree code is simple to understand: it only takes to tune yourself to Daniel Phillips brain-waves frequency".

--Tags:-[Linux]-[Kernel]-----------

A bit of out-of-context quoting

2006-01-11T16:38:00.000Z

Lessons Learned

Solaris has been functioning, essentially, by accident, for over one year.
We realize this again and again, every so often...

It is amazing that anything works at all

It's all broken

...

--Tags:-[Solaris]-[Kernel]-----------

A visit to the countryside.

2006-01-11T13:17:00.000Z

The Hidden Church

Oka riverside

An interior of a room of Polenov's house.

A painting by Polenov.

An ice tree.

Landscapes.

A wisent.

--Tags:-[Russia]-[Oka]-----------

	\(x \unlhd y\)
\(\equiv\)	{ definition of intensional subset }
	\(x\in t \Rightarrow y\in t\)
\(\Rightarrow\)	{ substitute \(\{x\}\) for \(t\)}
	\(x\in \{x\} \Rightarrow y\in \{x\}\)
\(\equiv\)	{ \(x\in \{x\}\) is true by the singleton property, modus ponens }
	\(y\in \{x\}\)
\(\equiv\)	{ the singleton property, again }
	\(x = y\)