a very occasional diary

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]-----------

reiser4: 0. introduction

2005-12-18T21:58:00.000Z

reiser4: 0. introduction

This is an introduction to the series of entries I am going to write about reiser4 file system. The plan, for the time being, goes like this:

0. introduction
- 0. trivia
- 1. reiser4 strong points
- 2. architecture overview
1. internal tree
- 0. B-trees overview
- 1. lookup and modification
- 2. concurrency control: lock ordering, hi-lo ordering
- 3. eottl
- 4. node format
2. tree clients
- 0. regular file
- 1. tail to extent conversion
3. transaction engine
- 0. goals: atomicity, no isolation, durability
- 1. log structure
- 2. shadow updates
4. directory code
- 0. overview of hashed directories
- 1. key structure and its motivation
- 2. lookup readdir
- 3. NFS?
5. delayed allocation and the flush algorithm
- 0. delayed allocation motivation
- 1. flush algorithm
- 2. overview of interaction with VM
- 3. emergency flush
6. round up

0. trivia

Reiser4 is a relatively new file system for Linux developed by namesys. Its development started early in 2001, and currently reiser4 is included into -mm patch series. Reiser4 is a next version of well-known reiserfs v3 file system (also known as simply reiserfs) that was first and for a long time the only journalled file system for Linux. While reiser4 is based on the same basic architectural ideas as reiserfs v3 it was written completely from scratch and its on-disk format is not compatible with reiserfs. Note on naming: namesys insists that file system is referred to as reiser4 and not reiserfs v4, or reiser4fs, or reiserfs4, or r4fs. Development of reiser4 was sponsored by DARPA, take a look at the namesys front page for a legal statement, and a list of other sponsors.

Technically speaking reiser4 can be briefly discussed as a file system using

global shared balanced lazily compacted tree to store all data and meta-data
bitmaps for block allocation
redo-only WAL (write ahead logging) with shadows updates (called "wandered logs" in reiser4)
delayed allocation in parent-first tree ordering

I shall (hopefully) describe these topics in more details in the future entries.

One last trivia point: I was amongst reiser4 developers from the very beginning of this project. At the mid-2004 I left namesys, at that point reiser4 was in more or less debugged state, and no significant design changes occurred since.

1. reiser4 strong points

Together with the unique design, reiser4 inherited reiserfs' strengths and weaknesses:

efficient support for very small files: multiple small files can be stored in the same disk block. This saves disk space, and much more importantly IO traffic between secondary and primary storage;
support for very large directories: due to balanced tree (to be described later), file system can handle directories with hundreds of million of files. The utility of this (and small files support) is often questioned, because "nobody uses file system in that way". Reiser4 design is based on the assumption, that cause-and-effect goes in the opposite direction here: applications do not use large directories and small files precisely because existing file system didn't provide efficient means for this. Instead, application developers had to resort to various hacks from configuration files (that have obvious hierarchical structure asking for being mapped onto file system), to artificially splitting large directory into smaller ones (look at /usr/share/terminfo/ directory as an example);
no hard limit on the number of objects on the file system. Traditional UNIX file systems (s5fs,ffs,ufs,ext2,ext3) fix total number of objects that can exist on a file system during file system creation. Correct estimation of this number is a tricky business. Reiser4, on the other hand, creates on-disk inodes (called "stat data" for historical reasons) dynamically;
previous item can be seen as a weakness, because it means that reiser4 on-disk format is more complex than that of its brethren. Other advanced reiser4 features also come not without an increase of format complexity. As a result, reiser4 can be corrupted in much more complicated ways than other file systems, requiring quite sophisticated fsck.

2. architecture overview

As was already hinted above reiser4 is quite different from other file systems architecturally. The most important difference, perhaps, is that reiser4 introduces another layer ("storage layer") between file system and block device. This layer provides an abstraction of persistent "container" into which pieces of data (called "units") can be placed and later retrieved. Units are identified by "keys": when unit is placed into container a key is given, and unit can later be retrieved by providing its key. Unit key is just a fixed-length sequence of bits.

In reiser4 this container abstraction is implemented in a form of special flavor of B-tree. There is one instance of such tree (referred to as "internal tree") per file system.

Entities from which file system is composed (regular files, directories, symlinks, on-disk inodes, etc.) are stored in the internal tree as sequences of units.

In addition to presenting container abstraction, storage layer is responsible for block allocation. That is, as units are inserted and deleted, tree grows and shrinks, taking blocks from block allocator and returning them back. Block allocation policy implemented by storage layer is very simple:

units with close keys are kept as close on disk as possible, and
units should be placed in the disk blocks so that key ordering corresponds to the block ordering on disk.

This allows higher layers of the system to influence location of units on disk by selecting unit keys appropriately.

While this doesn't sound especially exciting, key-based block allocation allows reiser4 to implement one extremely important feature: global block allocation policies. For example, by assigning to units of all objects in a given directory keys with the same prefix, higher layer code can assure that all objects located in this directory will be located close to each other on the disk. Moreover, by selecting next few bits of key based on --say-- file name it is possible to arrange all objects in the directory in the same order as readdir returns their names, so that commands like

$ cp -a * /somewhere

will not cause a single seek during read. More on this in the section on "delayed allocation and the flush algorithm".

So the highest layer in reiser4 implements file system semantics using storage layer as a container. Storage layer uses block allocator to manage disk space and transaction engine to keep file system consistent in case of a crash. Transaction layer talks to block device layer to send data to the storage.

To Be Continued by: internal tree.

opahead patch

2005-11-23T19:45:00.000Z

Here is a 2.6.15-rc1 version of opahead patch that was sleeping in my patch-scripts series file for some time.

opahead stands for operation-ahead by analogy with read-ahead. An inspiration for this patch was a USENIX paper that discusses a smarter than usual read-ahead algorithm. Kroeger and Long implemented a sub-system that kept track of read accesses to files and, according to certain stochastic model uses collected information to try to predict future accesses.

opahead uses much simpler model known as Shannon Oracle. (Unfortunately, I failed to find any online reference. I read a description of this algorithm many years ago in a book I no longer have.) It basically maintains enough data to answer following question: for a given sequence of N reads, what reads have been seen to follow this sequence in the past and how many times? Read that followed the sequence most, is assumed to be most likely to happen, and appropriate read-ahead is issued.

If N equals 1 we get familiar Markov Chain model. This is why the patch is sometimes called Markov read-ahead. But Markov chains have one fundamental disadvantage that makes them unsuitable for the read-ahead implementation: to make efficient read-ahead it's necessary to saturate IO layer and for this one has to look more than one event ahead in the future. That is, we have to predict next read, then assume that it did happen, and made new prediction based on that assumption. Obviously, the reliability of consecutive predictions deteriorates quickly, so it's very important to make initial prediction as reliable as possible. To this end, predictions are made on the basis of N previous reads, rather than on the basis of single one as in Markov model.

Another observation is that this algorithm doesn't depend on the nature of the events that are tracked and predicted. It can be generalized to the module that tracks and predicts abstract events that can be compared for equality (and it is that generalized form that is implemented in the patch).

That module can be used to do read-ahead at the different layers: VFS, file system, VM (page cache read-ahead), block layer (physical read-ahead); or it can be used for things completely unrelated to the read-ahead like, god forbid... predicting scheduling activity..

This patch was used to drive read-ahead at the file system layer (by plugging calls to opahead_{happens,predict}() into ext2_file_read()), but even though speed up of kernel compilation was measurable, this turned out to be dead-end, because to read a page from file one has to bring inode it memory first, but currently there is no an API for asynchronous inode loading.

Below is a top-level comment from opahead.h header with the general description of API (at least my effort of typing it in wouldn't be wasted).

opahead API

/*
 * This file is an interface to the op-ahead: a generic prediction engine.
 *
 * op-ahead implementation is in lib/opahead.c
 *
 * General description.
 *
 * op-ahead makes predictions in a certain domain consisting of events. Events
 * happen sequentially. op-head clients notify engine about events that
 * happen, and engine keeps track of event patterns. Engine then can be asked
 * a question: "Given a sequence of N last events, what is the next event to
 * happen most likely?"
 *
 * To answer this question, op-ahead keeps track of all sequences of N events
 * ever observed in the domain. N is called domain depth, and said sequences
 * are called paths. For each path op-ahead maintains a list of events that
 * were observed to follow this path (that is, to happen immediately after
 * events in the path happened in order). These following events (called
 * guesses) are weighted: the weight is a guess is a number of times it was
 * observed to follow this path.
 *
 * op-ahead operation is quite simple: when event E happens, op-ahead finds a
 * path corresponding to last happened events, and increases the weight of
 * guess corresponding to E (creating new guess if necessary).
 *
 * When asked to predict what event will follow given N events, op-ahead finds
 * path corresponding to these events and returns the guess with the largest
 * weight. If there are multiple guesses with the equal weight---random one is
 * selected.
 *
 * When domain depth is 1, paths degenerate into events and op-ahead into
 * modeling Markov chains.
 *
 * op-ahead algorithm is known as "Shannon Oracle". It is reported that in the
 * domain of two events "tail" and "head", and with the depth of 5, Shannon
 * Oracle robustly beats human player in the game of head and tails (that is,
 * after some period of learning it's able to predict next move with the
 * probability higher than 0.5). You are hereby requested to spend at least 10
 * percent of proceeds obtained from playing head and tails with the help of
 * this kernel code to buy hardware and to provide it to Linux kernel
 * developers.
 *
 * Usage.
 *
 * To use op-ahead client creates an instance of struct opa_domain with
 * methods appropriate for its events.
 *
 * Predictions are made in the "context" which is an array of domain->depth
 * pointers to events. This context is created by client (initialized by NULL
 * pointers) and is passed to opa_{predict,happen}(). It is used to record
 * latest events. When context is no longer needed, client calls
 * opa_context_put().
 *
 * When new event happens, client calls opa_happens() to record it. To predict
 * future events opa_predict() is used.
 *
 * Related work.
 *
 * In http://www.usenix.org/events/usenix01/kroeger.html a similar (albeit
 * more mathematically sophisticated) model is used to predict future file
 * accesses and to drive inter-file read-ahead.
 *
 * TODO:
 *
 * Helper functions for reference-counted events.
 *
 */

To be Continued?

--Tags:-[Kernel]-[Filesystems]-----------

An exercise

2005-11-12T16:35:00.000Z

Here is a little problem. Given an array A of N integers, find a sub-array (determined by a pair of indices within A) such that sum of elements in that sub-array is maximal among all sub-arrays of A.

Sounds pretty easy? It is, but just to set a little standard for solutions: there is a way (shown to me by 15-year-old boy) to do this in one pass over A and without using any additional storage except for few integer variables.

So much for dynamic programming...

update

That exercise is interesting, because while superfluously similar to the well-known tasks like finding longest common substring, etc. it can be solved in one pass. Indeed Matti presented exactly the same solution that I had in mind. And it is possible (and instructive) to get a rigorous proof that this algorithm solves the problem.

Definition 0

Let A = (i, j) be a sub-array (i <= j), then S(A) = S(i, j) denotes a sum of elements in A. S(A) will be called „sum of A“

Definition 1

Let A = (i, j) be a sub-array (i <= j), then for any

0 <= p < i < q < j < r < N

sub-array (p, i - 1) is called left outfix of A, (i, q) --- left infix of A, (q + 1, j) --- right infix of A, and (j + 1, r) --- right outfix of A.

Definition 2

A sub-array is called optimal if all its infixes have positive sums, and all its outfixes have negative sums.

It's easy to prove the following:

Statement 0

A sub-array with the maximal sum is optimal.

Indeed, any non-optimal sub-array by definition has either negative infix, or positive prefix, and, hence, can be shrunken or expanded to another sub-array that has larger sum. As an obvious corollary we get:

Statement 1

To find a sub-array with the maximal sum it's enough to find a sub-array with the maximal sun among all optimal sub-arrays.

The key fact that explains why our problem can be solved in one pass is captured in the following:

Statement 2

Optimal sub-arrays are not overlapping.

Also easily proved by observing that when two sub-arrays A and B overlap there always is an sub-array C that is an infix of A and an outfix of B. And, now the only thing left to do is to prove that Matti's algorithm calculates sums of (at least) all optimal sub-arrays. Which is easy to do:

first prove that possibly except for the initial value, new_start always points to the index at which at least one (and, therefore, exactly one) optimal array starts. This is easily proved by induction.
then prove that once particular value of new_start has been reached, new_start is not modified until i reaches upper index of optimal array starting at new_start. This follows directly from the definition of optimal sub-array, because all its left infixes have positive sums.
this means that for any optimal sub-array (p, q) there is an iteration of the loop at which
new_start == p && i == q
As algorithm finds maximal sum among all (new_start, i) sub-arrays, it finds maximal sum among all optimal arrays, and, by Statement 1, maximal sum among all sub-arrays.

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

Update of my kernel patches for 2.6.14-rc5

2005-10-24T10:02:00.001Z

New version of patches is uploaded here.

This series include:

vm_02-skip-writepage.patch
Don't call ->writepage from VM scanner when page is met for the first time during scan. New page flag PG_skipped is used for this. This flag is TestSet-ed just before calling ->writepage and is cleaned when page enters inactive list. One can see this as „second chance“ algorithm for the dirty pages on the inactive list. BSD does the same: src/sys/vm/vm_pageout.c:vm_pageout_scan(), PG_WINATCFLS flag. Reason behind this is that ->writepages() will perform more efficient writeout than ->writepage(). Skipping of page can be conditioned on zone->pressure. On the other hand, avoiding ->writepage() increases amount of scanning performed by kswapd. (Possible drawback: executable text pages are evicted earlier.): vm_04-__alloc_pages-inject-failure.patch
Force artificial failures in page allocator. I used this to harden some kernel code.: async-writepage.patch
Perform calls to the ->writepage() asynchronously. VM scanner starts pageout for dirty pages found at tail of the inactive list during scan. It is supposed (or at least desired) that under normal conditions amount of such write back is small. Even if few pages are paged out by scanner, they still stall "direct reclaim" path (__alloc_pages() -> try_to_free_pages() -> ... -> shrink_list() -> writepage()), and to decrease allocation latency it makes sense to perform pageout asynchronously. Current design is very simple: asynchronous page-out is done through pdflush operation kpgout(). If shrink_list() decides that page is eligible for the asynchronous pageout, it is placed into shared queue and later processed by one of pdflush threads. Most interesting part of this patch is async_writepage() that decides when page should be paged out asynchronously. Currently this function allows asynchronous writepage only from direct reclaim, only if zone memory pressure is not too high, and only if expected number of dirty pages in the scanned chunk is larger than some threshold: if there are only few dirty pages on the list, context switch to the pdflush outwieghts advantages of asynchronous writepage.: vm_05-page_referenced-move-dirty.patch
transfer dirtiness from pte to the struct page in page_referenced(). This makes pages dirtied through mmap „visible“ to the file system, that can write them out through ->writepages() (otherwise pages are written from ->writepage() from tail of the inactive list).: vm_06-cluster-pageout.patch
Implement pageout clustering at the VM level. With this patch VM scanner calls pageout_cluster() instead of ->writepage(). pageout_cluster() tries to find a group of dirty pages around target page, called „pivot“ page of the cluster. If group of suitable size is found, ->writepages() is called for it, otherwise, page_cluster() falls back to ->writepage(). This is supposed to help in work-loads with significant page-out of file-system pages from tail of the inactive list (for example, heavy dirtying through mmap), because file system usually writes multiple pages more efficiently. Should also be advantageous for file-systems doing delayed allocation, as in this case they will allocate whole extents at once. Few points: swap-cache pages are not clustered (although they can be, but by page->private rather than page->index) only kswapd do clustering, because direct reclaim path should be low latency. Original version of this patch added new fields to struct writeback_control and expected ->writepages() to interpret them. This led to hard-to-fix races against inode reclamation. Current version simply calls ->writepage() in the "correct" order, i.e., in the order of increasing page indices..: vm_07-proc-stack.patch
Export kernel backtrace in /proc/<pid>/task/<tid>/stack. Useful when debugging deadlocks. This somewhat duplicates functionality of SysRq-T, but is less intrusive to the system operation and can be used in the scripts. Exporting kernel stack of a thread is probably unsound security-wise. Use with care. Instead of adding yet another architecture specific function to output thread stack through seq_file API, it introduces „iterator“ void do_with_stack(struct task_struct *tsk, int (*actor)(int, void *, void *, void *), void *opaque) that has to be implemented by each architecture, so that generic code can iterate over stack frames in architecture-independent way. lib/do_with_stack.c is provided for archituctures that don't implement their own. It is based on __builtin_{frame,return}_address().: vm_08-proc-sleep.patch
export per-process blocking statistics in /proc/<pid>/task/<tid>/sleep and global sleeping statistics in /proc/sleep. Statistics collection for given file is activated on the first read of corresponding /proc file. When statistics collection is on on each context switch current back-trace is built (through __builtin_return_address()). For each monitored process there is a LRU list of such back-traces. Useful when trying to understand where elapsed time is spent.: export-filemap_populate-in-proper-place.patch
move EXPORT_SYMBOL(filemap_populate) to the proper place: just after function itself: it's easy to miss that function is exported otherwise.: throttle-against-free-memory.patch
Fix write throttling to calculate its thresholds from amount of memory that can be consumed by file system and swap caches, rather than from the total amount of physical memory. This avoids situations (among other things) when memory consumed by kernel slab allocator prevents write throttling from ever happening.: BUILD_BUG_ON-fix-comment.patch
Fix comment describing BUILD_BUG_ON: BUG_ON is not an assertion (unfortunately). Also implement BUILD_BUG_ON in a way that can be used outside of a function scope, so that compile time checks can be placed in convenient places (like in a header, close to the definition of related constants and data-types).

zoneinfo.patch, deadline-iosched.c-cleanup.patch and ll_merge_requests_fn-cleanup.patch were merged into Linus tree.

dont-rotate-active-list.patch was dropped: it seems to cause inactive list exhaustion for certain wrodloads.

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

Грозный

2005-10-16T10:15:00.000Z

"Чешский археолог Бедржих Грозный (1879--1952), который в 1915 г. расшифровал хеттскую клинопись, и именем которого был назван город в южной России."

--Tags:-[History]-[Quotes]-----------

Get me out of here!

2005-10-13T16:00:00.000Z

Everything a traveler has to know to get into China and, more importantly, back.

Всё, что необходимо знать для путешествия в Китай и обратно.

--Tags:-[China]------------

plug & crash

2005-09-13T19:15:00.000Z

I had some problems in my local network to-day, so I had to turn off the switch. Bang! My workstation hang immediately as power cord was unplugged from the D-Link. Initially I thought that something is wrong with the grounding, but a series of painful experiments proved that electricity has nothing to do with this: workstation hung whenever Ethernet cable was pulled off the socket. This looks like complete magic^[1] isn't it? Fortunately I was advised to boot kernel with nmi_watchdog=1 (before I went insane, that is), and with the first stack-trace problem became obvious:

when cable is pulled, rtl8139 driver receives an interrupt and the first thing it does is grabbing of spin-lock, protecting struct rtl8139_private...
after that it goes to print „link-down“ message to the console...
but I am using netconsole^[2], and to print that message netconsole calls back into rtl8139 driver...
and the first thing it does is grabbing of spin-lock... which is already grabbed by that very thread---deadlock.

[1] when I'll have a time, I'll also record a true story that happened during reiserfs debugging: how saving file in emacs made all processes in the system invisible to ps(1) and top(1).

[2] a console driver that sends kernel messages over network in UDP packets---very useful for debugging.

--Tags:-[Linux]-[Networking]-----------

A look at several memory management units...

2005-08-24T15:06:00.000Z

An interesting paper (via Muli Ben-Yehuda) that describes, in particular, VM organization of several platforms. A bit I didn't knew: ULTRIX uses two level page tables that are traversed bottom-up: leaf level of the tree lives in the virtual space and is contiguous in it. As a result, to handle TLB miss at the virtual address A it's enough to do:

ULTRIX page-fault handler. V0

        phys_address = LEAF_TABLE[A >> PTABLE_SHIFT_LEAF];

Obviously it is somewhat more involved in reality, because appropriate portion of LEAF_TABLE[] can be not in the TLB itself. In the latter case, root node of the tree is consulted:

ULTRIX page-fault handler. V1

        if (tlb_miss(LEAF_TABLE + (A >> PTABLE_SHIFT_LEAF))
                tlb_load(ROOT_NODE[A >> PTABLE_SHIFT_ROOT],
                         LEAF_TABLE + (A >> PTABLE_SHIFT_LEAF));
        phys_address = LEAF_TABLE[A >> PTABLE_SHIFT_LEAF];

Root node is wired down into unmapped (physical) memory.

This design provides following advantages:

TLB miss handling requires one memory access in the best case, and two in the worst. In top-to-bottom page tables a la Intel, two (or three) accesses are necessary for every TLB refill;
This integrates nicely with virtually indexed processor caches;
This allows parts of page tables to be paged out easily.

Unfortunately Digital screwed this design by using slow software filled TLB.

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

named formals

2005-08-18T08:38:00.000Z

Another C99 abuse: „named formal parameters“:

named formal parameters

int foo(int a, char b)
{
        printf("foo: a: %i, b: %c (%i)\n", a, b, b);
}

/* 
 * NOTE: imagine that following macro definition is properly backslashified.
 *       And blame Google/Blogger for my not being able to do this.
 */
#define foo(...) ({                 
          struct {                  
                   int  a;          
                   char b;          
          } __fa = { __VA_ARGS__ }; 
          foo(__fa.a, __fa.b);      
})

int main(int argc, char **argv)
{
        foo(.b = 'b', .a = 42);
        foo();
}

This outputs:

foo: a: 42, b: b (98)
foo: a: 0, b:  (0)

By combining compound literals and __VA_ARGS__ (again!) it is possible to explicitly name function arguments, specify them in arbitrary order, and omit some of them (omitted arguments are initialized by corresponding default initializers).

--Tags:-[C]-[Programming]-----------

A monster desktop

2005-08-12T20:17:00.000Z

Screenshot of my desktop while running 5 node UML cluster:

--Tags:-[UML]-[Desktop]-----------

kernel stack overflow.

2005-08-11T20:42:00.000Z

Linux kernel traditionally has very spartan run-time environment. This is because kernel code is only written by real programmers, impeccable thinkers with boundless capacity for analysis, like yours... err, I got carried away.

In particular, in good old days, when world was simpler, kernel thread stack size used to be just 8K (two 4K pages) on x86. As kernel grew larger, and started to employ more complex algorithms, kernel stack of course shrunk. Right---shrunk: now it is 4K (one page) by default. This was justified by the following considerations:

In newer kernels, interrupts can be served on special per-processor interrupt stack (not all architectures allow this, though).
Linux slab allocator is efficient and scalable enough to dynamically allocate many data-structures that used to be allocated on the stack.
Main reason is that allocation of stacks larger than page size --which is the basic allocation unit of low-level buddy allocator--, fragments page allocator bitmaps, and can lead to out-of-memory situations. With large number of threads this problems becomes severe.

But I digressed again: to-day I got stack overflow in UML configured with CONFIG_KERNEL_STACK_ORDER=3, that is with stack occupying 2**3 = 8 pages (32K)!:

stack

0xa005632c __alloc_pages+636
0xa02172e4 sigemptyset+36
0xa0056427 __get_free_pages+39
0xa00599d8 cache_grow+152
0xa0059d48 cache_alloc_refill+312
0xa005a0cd __kmalloc+125
0xa01a0e58 alloc_skb+72
0xa00257e6 uml_net_rx+38
0xa002595f uml_net_interrupt+47
0xa0016b05 handle_IRQ_event+53
0xa0016cb6 do_IRQ+118
0xa001748a sigio_handler+218
0xa0021b31 sig_handler_common_tt+161
0xa001bf20 enable_mask+80
0xa001de48 sig_handler+24
0xa0217098 __restore
0xa0217212 __sigprocmask+34
0xa001bdda change_sig+90
0xa001be63 change_signals+115
0xa00173ed sigio_handler+61
0xa0021b31 sig_handler_common_tt+161
0xa001de48 sig_handler+24
0xa0217098 __restore
0xa0217212 __sigprocmask+34
0xa001bf20 enable_mask+80
0xa02172e4 sigemptyset+36
0xa001c011 set_signals+129
0xa001be63 change_signals+115
0xa001bf20 enable_mask+80
0xa02172e4 sigemptyset+36
0xa001c011 set_signals+129
0xa001bf68 get_signals+40
0xa005a098 __kmalloc+72
0xa01a0e58 alloc_skb+72
0xa01d2062 tcp_send_ack+50
0xa01cdb04 tcp_rcv_established+612
0xa01d67da tcp_v4_do_rcv+282
0xa01d6e0c tcp_v4_rcv+1580
0xa001bf20 enable_mask+80
0xa02172e4 sigemptyset+36
0xa01bb21a ip_local_deliver+282
0xa01bb706 ip_rcv+870
0xa01a62c5 netif_receive_skb+389
0xa01a63a7 process_backlog+135
0xa01a64b6 net_rx_action+118
0xa003c1b5 __do_softirq+165
0xa003c205 do_softirq+69
0xa0016d0b do_IRQ+203
0xa001748a sigio_handler+218
0xa0021b31 sig_handler_common_tt+161
0xa001be63 change_signals+115
0xa001de48 sig_handler+24
0xa0217098 __restore
0xa0217212 __sigprocmask+34
0xa003c1fe do_softirq+62
0xa0016d0b do_IRQ+203
0xa00173ed sigio_handler+61
0xa0021b31 sig_handler_common_tt+161
0xa001de48 sig_handler+24
0xa0217098 __restore
0xa0217212 __sigprocmask+34
0xa02172e4 sigemptyset+36
0xa001be63 change_signals+115
0xa001bec2 unblock_signals+18
0xa0050aaa find_get_pages_tag+122
0xa005b9d3 pagevec_lookup_tag+51
0xa001bfd5 set_signals+69
0xa001be63 change_signals+115
0xa001bf74 get_signals+52
0xa0058147 mapping_tagged+55
0xa008e841 wake_up_inode+17
0xa00945d1 __sync_single_inode+161
0xa008e387 iput+87
0xa0094932 sync_sb_inodes+450
0xa001c011 set_signals+129
0xa0094af0 writeback_inodes+160
0xa005766a wb_kupdate+186
0xa02172e4 sigemptyset+36
0xa005822f __pdflush+207
0xa001bec2 unblock_signals+18
0xa0058310 pdflush
0xa0058339 pdflush+41
0xa00575b0 wb_kupdate
0xa0058310 pdflush
0xa004aee9 kthread+169
0xa004ae40 kthread
0xa0019909 run_kernel_thread+73
0xa02172e4 sigemptyset+36
0xa004ae40 kthread
0xa00198ee run_kernel_thread+46
0xa004ae40 kthread
0xa001fa50 new_thread_handler+304
0xa004ae40 kthread
0xa001fa90 new_thread_proc
0xa0217098 __restore
0xa001fa90 new_thread_proc
0xa022faad syscall+29
0xa022fab1 syscall+33

Of course, UML is unusual platform: it doesn't support separate interrupt stack, and interrupt trampoline code (including host signal frames) is expensive stack-wise, but still: beware of stack consumption.

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

Glenn Gould

2005-08-06T21:34:00.000Z

An absolutely unbelievable thing: on the Variation 24. Canon on the octave, from 1981 Goldberg Variations performed by Glenn Gould, one can distinctly hear human voice just on the edge of audibility. Glenn Gould is singing his Bach.

Невероятно, но факт: в Вариации 24, канон в октаве, в исполнении Глена Гоулда 1981-го года, можно, на пороге слышимости различить слабый человеческий голос. Гоулд подпевает.

--Tags:-[Music]-[Bach]-----------

Confessions of Microsoft developer

2005-08-02T22:31:00.000Z

As a simple example, when Windows started up, it increased the size of MS-DOS’s internal file table (the SFT, that’s the table that was created by the FILES= line in config.sys). It did that to allow more than 20 files to be opened on the windows system (a highly desirable goal for a multi-tasking operating system). But it did that by using an undocumented API call, which returned a pointer to a set of “interesting” pointers in MS-DOS. It then indexed a known offset relative to that pointer, and replaced the value of the master SFT table with its own version of the SFT. When I was working on MS-DOS 4.0, we needed to support Windows. Well, it was relatively easy to guarantee that our SFT was at the location that Windows was expecting. But the problem was that the MS-DOS 4.0 SFT was 2 bytes larger than the MS-DOS 3.1 SFT. In order to get Windows to work, I had to change the DOS loader to detect when win.com was being loaded, and if it was being loaded, I looked at the code at an offset relative to the base code segment, and if it was a “MOV” instruction, and the amount being moved was the old size of the SFT, I patched the instruction in memory to reflect the new size of the SFT! Yup, MS-DOS 4.0 patched the running windows binary to make sure Windows would still continue to work.

And these are the people who design and implement most widely used software in the world. Which is a scary place indeed.

--Tags:-[Microsoft]-[Software]-----------

Wikipedia

2005-07-31T19:10:00.000Z

I added a bit of material to the Wikipedia entry on Page replacement algorithms: a bit of history, precleaning, global vs. local replacement, description of LRU degradation for cyclic access patterns, random replacement, links to the modern algorithms, unification of VM with file system cache, etc. Original entry was more or less re-hash of section from Tannenbaum's „Operating Systems“.

--Tags:-[Wikipedia]-----------

The Question of Life, The Universe, and Everything.

2005-07-31T17:49:00.000Z

'How old is that horse, my friend?' inquired Mr. Pickwick,
rubbing his nose with the shilling he had reserved for the fare.

'Forty-two,' replied the driver, eyeing him askant.

--Tags:-[42]-[Dickens]-----------

__VA_ARGS__ + C99 compound literals = safe variadic functions

2005-07-30T12:48:00.000Z

It occurred to me that new C features added by C99 standard can be used to implement „safe variadic functions“ that is, something syntactically looking like normal call of function with variable number of arguments, but in effect calling function with all arguments packed into array, and with array size explicitly supplied:

safe variadic functions

#define sizeof_array(arr) ((sizeof (arr))/(sizeof (arr)[0]))

/* 
 * NOTE: imagine that following macro definition is properly backslashified.
 *       And blame Google/Blogger for my not being able to do this.
 */
#define FOO(a, ...)
       foo((a), (char *[]){ __VA_ARGS__, 0 }, sizeof_array(((char *[]){ __VA_ARGS__ })))

int foo(int x, char **str, int n)
{
 printf("%i %i\n", x, n);
 while (n--)
  printf("%s\n", *(str++));
 printf("last: %s\n", *str);
}

int main(int argc, char **argv)
{
 FOO(1, "a", "boo", "cooo", "dd", argv[0]);
}

this outputs

1 5
a
boo
cooo
dd
./a.out
last: (null)

Expect me to use this shortly somewhere.

--Tags:-[Programming]-[C]-----------

Repaging in AIX VM

2005-07-25T23:11:00.000Z

„Repaging“ was mentioned to me by Rik van Riel long time ago. How this can be implemented in Linux? E.g., add ->repage_tree radix-tree to struct address_space. (We get 32 bits per-page this way, while we need only one!) Insert entry into this tree on each page fault. Do _not_ remove entry when page is reclaimed. As a result, ->repage_tree keeps history of page faults. Check it on page fault. If there is an entry for page being faulted in---we have „repage“. Maintain global counter of elements in ->repage_tree's. When it's higher than some threshold (AIX uses total number of frames in the primary storage), start removing ->repage_tree elements on reclaim. Disadvantage: history is lost when struct address_space is destroyed.

--Tags:-[Kernel]-[AIX]-----------

inactive_dirty and inactive_clean are considered harmful

2005-07-25T23:06:00.000Z

Found interesting discussion on linux-mm (Sept. 2002):

AKPM and Rik („inactive_dirty list“)

[AKPM proposed separate inactive_dirty and inactive_clean lists to avoid excessive scanning of pages that cannot be reclaimed (due to then-new non-blocking VM scanner]:

    Riel:
    > AKPM:
    > > - inactive_dirty holds pages which are dirty or under writeback.
    > 
    > > - everywhere where we add a page to the inactive list will now
    > >   add it to either inactive_clean or inactive_dirty, based on
    > >   its PageDirty || PageWriteback state.
    > 
    > If I had veto power I'd use it here ;)
    > 
    > We did this in early 2.4 kernels and it was a disaster. The
    > reason it was a disaster was that in many workloads we'd
    > always have some clean pages and we'd end up always reclaiming
    > those before even starting writeout on any of the dirty pages.
    > 
    > It also meant we could have dirty (or formerly dirty) inactive
    > pages eating up memory and never being recycled for more active
    > data.

And later in the same thread:

    AKPM:
    > You're proposing that we get that IO underway sooner if there
    > is page reclaim pressure, and that one way to do that is to
    > write one page for every reclaimed one.  Guess that makes
    > sense as much as anything else ;)

(decrease dirty cache balancing rules when hitting memory pressure, so that balance_dirty_pages() and pdflush do write-out in scanner's stead)

And further more:

    Daniel Phillips
    > On Saturday 07 September 2002 01:34, Andrew Morton wrote:
    > > You're proposing that we get that IO underway sooner if there
    > > is page reclaim pressure, and that one way to do that is to
    > > write one page for every reclaimed one.  Guess that makes
    > > sense as much as anything else ;)
    > 
    > Not really.  The correct formula will incorporate the allocation rate
    > and the inactive dirty/clean balance.  The reclaim rate is not
    > relevant, it is a time-delayed consequence of the above.  Relying on
    > it in a control loop is simply asking for oscillation.

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

XNU VM

2005-07-25T23:02:00.000Z

XNU (OSX kernel) VM scanner marks vnodes as (vp->v_flag & VHASBEENPAGED). write(2) path checks for this and sends all dirty pages for this vnode down the pipe if this flags is set. Reason:

/*
* this vnode had pages cleaned to it by
* the pager which indicates that either
* it's not very 'hot', or the system is
* being overwhelmed by a lot of dirty
* data being delayed in the VM cache...
* in either event, we'll push our remaining
* delayed data at this point... this will
* be more efficient than paging out 1 page at
* a time, and will also act as a throttle
* by delaying this client from writing any
* more data until all his delayed data has
* at least been queued to the uderlying driver.
*/

--Tags:-[OSX]-[Kernel]-----------

BSD VM scanner

2005-07-25T22:57:00.000Z

BSD vm analyzes object reference counter in page scanner:

vm/vm_pageout.c:vm_pageout_scan()

/*
* If the object is not being used, we ignore previous
* references.
*/
if (m->object->ref_count == 0) {
        vm_page_flag_clear(m, PG_REFERENCED);
        pmap_clear_reference(m);
}
....
/*
* Only if an object is currently being used, do we use the
* page activation count stats.
*/
if (actcount && (m->object->ref_count != 0)) {
        vm_pageq_requeue(m);
}
....

--Tags:-[Kernel]-[BSD]-----------

Concurrency Control and Recovery in Database Systems

2005-07-25T22:40:00.000Z

Concurrency Control and Recovery in Database Systems by Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman.

Delayed commit as an alternative to keeping „commit-time“ locks: when transaction T1 is accessing a resource modified by active transaction T2, it just proceeds hoping that T2 will commit. If T1 tries to commit while T2 is still active, its commit is delayed until T2 commits or aborts. If T2 aborts, T1 has to abort too (and can be restarted). One can imagine "abort-rate" tracked for each resource, and delayed commits are used only if it is low enough.

Pragmatically, this means that read locks can be released when the transaction terminates (i.e., when the scheduler receives the transaction's Commit or Abort), but write locks must be held until after the transaction commits or aborts (i.e., after the DM processes the transaction's Commit or Abort).

This strategy („Static 2PL scheduler“) generates strict histories. How it generalizes to other types of locks?

Interesting section on thrashing:

pure restart policy (abort transaction when it tries to acquire already held lock) works well when data contention is high.
a measure of thrashing:
W = k * k * N / D,
where N - multiprogramming level,
k - number of locks required by transaction,
D - number of lockable entities.
thrashing starts when W >= 1.5.
Can be applied to resource (memory) trashing too.

--Tags:-[Databases]-[Concurrency]-----------

limit and evaluation

2005-07-24T15:30:00.001Z

Let D be a category with functorial limits of functors from some category C. That is, there is a functor

lim : Cat(C, D) -> D.

For each object x from C, there is a functor

ev_x : Cat(C, D) -> D,

sending functor

F : C -> D

to F(x), and sending natural transformation

r : F -> G : C ->D

to its component at x (r_x : F(x) -> G(x)). By mapping x to ev_x and morphism f : x -> y to an obvious natural transformation from ev_x to ev_y we obtain a functor

EV : C -> Cat(Cat(C, D), D).

Amusing and trivially checkable fact is that

lim = Lim EV.

That is, limits are always point-wise.

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

working set is not relevant

2005-07-24T04:35:00.000Z

[Updated: 2005.07.24]

The key point of working set algorithm is not „virtual time“ relative to which recently used pages are defined. Virtual time is a problem rather than a solution. At the time when working set algorithm was designed, there was one to one mapping between address spaces and threads. In such setup virtual time based scanning ties memory scheduling and processor scheduling and, hence, avoids thrashing, which is a situation when one resource (processor) is scheduled to achieve its maximal utilization, ignoring constraints imposed by other resource (memory) (See Dijkstra papers EWD408 and EWD462 for as always lucid an explanation).

In modern systems there is no such one to one mapping anymore. There are multiple threads executing within the same address space. There are memory consumers that are not readily identifiable with any execution context at all: file system cache (which is merged with VM in any self-respecting kernel), general in-kernel memory allocator, etc. It means that:

there is no relevant notion of virtual time to be used during scanning;
working set control fails to bind memory and processor scheduling together, which will decrease its effectiveness.

One extreme case is to consider whole system as one entity. Then virtual time degenerates into physical one, and working set algorithm into active/inactive queue.

Moreover, working set is not page replacement algorithms at all. That is, it doesn't answer to the question „System is low on memory, what page should be reclaimed?“ Instead it vaguely points to some address space and proposes to reclaim some unknown page from it. This made sense for the time-shared server running large number of tasks with disjoint address spaces, but for the modern system working set algorithm will be most likely finger-pointing to the Mozilla (or OpenOffice, or...) on the client and Apache (or Oracle, or...) on the server. Which is completely useless, because we still don't know what page is to be reclaimed.

--Tags:-[OS-]-[Kernel]-----------

Travel to the land of Juyed Awk Yacc

2005-07-23T19:03:00.000Z

Travel to the land of Juyed Awk Yacc

Nethack is a single-user role playing, dungeon exploring game. This is probably most complex RPG ever built. Nethack consists of a core game engine (however no such term existed at the time of game creation), and a number of front-ends (windowing systems) providing a view into the game world. Although many GUI-based front-ends for nethack were written over time, original TTY-based one is still the best: difference between graphic and text-based games is like difference between watching TV and reading a book. In the latter case it's completely up to the reader to create and maintain the world in its imagination. As a result reader/player feels much greater attachment to the constructed reality, and is emotionally bound to it.

Another crucial difference between nethack and other RPG games is what can be termed its orthogonality: nethack objects (monsters, tools, magic items, dungeon elements, weaponry and armor, etc.) can be used in a ways and combinations well beyond any fixed „game script“. For example, magic ring can be wield as a weapon, or thrown like a projectile, or when player polymorphs into type of monster that has no hands, weapon fell to the floor (and if player happens to levitate over water at that moment, fallen objects sink). This orthogonality if often referred to as „Dev Team thought about everything“. This makes nethack similar to the real world where there are laws rather than scripts.

Below is an account of my last (yet uncompleted) nethack game as nikita-Wiz-hum-neu-mal.

The Beginning

I got rather standard initial abilities, but initial inventory contained two extremely valuable items: a ring of invisibility and a ring of slow digestion. The latter is very useful in the early stages of the game, where starvation if one of the commonest causes of death.

By falling through two trapdoors I quickly descended deep into the dungeon. This is usually a fatal experience, but luckily, while trying to climb back to the safer levels, I got a wish by drinking from a fountain. It would be silly to waste it to anything less than the best armor in the game:

With the ring of invisibility and the dragon scale mail I was well-prepared to go forward.

The Gnomish Mines

Even with the ring of slow digestion, exploring the Gnomish Mines is reasonable first step, as there is plenty of food there. Also, I hoped to get a luck stone and a bag of holding there.

Our dungeon happened to have rather rare form of Minetown („Grotto Town“):

Unfortunately there was no bag of holding anywhere, which turned to be constant annoyance: I was short on inventory space all the time and had to create multiple intermediate storage spots.

At the Mines End (The Mimic of the Mines), there was a box with Schroedinger's Cat inside:

I wonder what statistics an ensemble of all nethack cats follows?

Sokoban

At the dlvl 10 there was a stairway up leading to the Sokoban branch of the dungeon. This branch extends upward, so the level numbers decrease. As passing this maze is one of the most tedious parts of the same, I took numerous shots, to record required sequence of moves:

After returning from the sokoban, I descended through several ordinary levels...

... before reaching Rogue level at dlvl 15:

There was Kenneth Arnold's ghost there with the usual funny stuff:

Quest

Magic portal to the Quest home level was on the rogue level...

... but after cleaning quest home up, I decided to first descend a bit more through the main dungeon first:

Then I returned to the quest...

And reached the Dark One's lore, where I found a wand of wishing:

I wished for the ring of teleport control, because I had intrinsic teleport by that time.

The Dark One proved to be not that much of a challenge, albeit full of amusing curses:

While immune to the magical attacks, he could do nothing against the old trusty potion of paralysis....

By returning by quest artefact (the Eye of the Aethiopica) to the Neferet the Gree, I completed the quest, and...

Medusa's Island and the Castle

... went downward through the main dungeon, to Medusa's Island.

I spent a *lot* of time on this level, first because there was a couple of demiliches that were busy creating monsters, but mainly because few groups of giants appeared there and I decided that I won't lose any opportunity to improve my strength (strength is improved by eating giants). There are few tricks there: first giant corpse is too heavy to be carried away to the safe place, which means that monster is better to be killed in a place where it can be eaten safely without its cogeni attacking you all the time. Second, after eating a giant corpse one has to wait a long time to digest it. This is where ring of hunger would be very useful. Welladay, I don't have one.

Nikita, meet Jabberwocky. Jabberwocky, meet Nikita.

After clearing Medusa's Island somewhat I went to the Castle. As I had a ring of levitation, there was no need to muck with the drawbridge.

The Castle always has a wand of wishing.

As I am strong enough already, gauntlets of dexterity are reasonable choice.

Now I have standard ascension kit.

Back to the Medusa's Island.

Watch gremlins fun...

Gehennom

And through the Castle, down to the Valley of the Dead, first level of the Gehennom

Lot of ghosts here...

Gee... even my owns.

Below the Valley of the Dead are few normal Gehennom style mazes, followed by Juiblex' Swamp, where we find another Schroedinger's Cat... this time alive!

Got a glimpse at my attributes...

Now to the Asmodeus' Lair

Oops... got a hit from the green slime.

Time to resort to the extreme measures.

Aha, Wizard of Yendor is sitting in his tower. Wait for me, I am coming.

Entering the Vlad's Tower

Passing through it upward...

Killing Vlad The Impaler...

And returning back to cozy Gehennom.

Peaceful mind flyer: a rare sight.

Attacked by a shade...

and by a wraith.

Wizard

Now I can enter Wizard's Tower.

Ascending through it...

Only to find out that Wizard of Yendor is little more than a vulgar thief.

Killed him. For the first time. There will be more to come, I know.

Orcus-Town.

See? Wizard of Yendor resurrected and attacked me here. Little did he know how handy nearby cockatrice can be. Attack of the clones.

To Be Continued

--Tags:-[Nethack]-----------

you have a strange forbidding feeling...

2005-06-26T09:20:00.000Z

A scary thing happened to me: my first thought, while looking at

linux-2.6.5-7.151/lib/vsprintf.c

if (*fmt == 'h' || *fmt == 'l' || *fmt == 'L' ||
    *fmt == 'Z' || *fmt == 'z') {
    qualifier = *fmt;
    fmt++;
}

was something like Hmm... I should be careful about that master lich here.... I should throttle down.

--Tags:-[Hacking]-[Linux]-[Kernel]-[Nethack]-----------

kernel patches for 2.6.12-rc6

2005-06-11T12:18:00.000Z

After long delay I updated my kernel patches to 2.6.12-rc6. This required installing git and cogito, but it turned out that time wasn't wasted: these tools beat bitkeeper hands down CPU-wise.

New version of patches is uploaded here.

This series include:

vm_01-zoneinfo.patch
Add /proc/zoneinfo file to display information about memory zones. Useful to analyze VM behaviour. This was merged into -mm.: vm_02-skip-writepage.patch
Don't call ->writepage from VM scanner when page is met for the first time during scan. New page flag PG_skipped is used for this. This flag is TestSet-ed just before calling ->writepage and is cleaned when page enters inactive list. One can see this as „second chance“ algorithm for the dirty pages on the inactive list. BSD does the same: src/sys/vm/vm_pageout.c:vm_pageout_scan(), PG_WINATCFLS flag. Reason behind this is that ->writepages() will perform more efficient writeout than ->writepage(). Skipping of page can be conditioned on zone->pressure. On the other hand, avoiding ->writepage() increases amount of scanning performed by kswapd. (Possible drawback: executable text pages are evicted earlier.): vm_03-dont-rotate-active-list.patch
Currently, if zone is short on free pages, refill_inactive_zone() starts moving pages from active_list to inactive_list, rotating active_list as it goes. That is, pages from the tail of active_list are transferred to its head, thus destroying lru ordering, exactly when we need it most --- when system is low on free memory and page replacement has to be performed. This patch modifies refill_inactive_zone() so that it scans active_list without rotating it. To achieve this, special dummy page zone->scan_page is maintained for each zone. This page marks a place in the active_list reached during scanning. As an additional bonus, if memory pressure is not so big as to start swapping mapped pages (reclaim_mapped == 0 in refill_inactive_zone()), then not referenced mapped pages can be left behind zone->scan_page instead of moving them to the head of active_list. When reclaim_mapped mode is activated, zone->scan_page is reset back to the tail of active_list so that these pages can be re-scanned.: vm_04-__alloc_pages-inject-failure.patch
Force artificial failures in page allocator. I used this to harden some kernel code.: vm_05-page_referenced-move-dirty.patch
transfer dirtiness from pte to the struct page in page_referenced(). This makes pages dirtied through mmap „visible“ to the file system, that can write them out through ->writepages() (otherwise pages are written from ->writepage() from tail of the inactive list).: vm_06-cluster-pageout.patch
Implement pageout clustering at the VM level. With this patch VM scanner calls pageout_cluster() instead of ->writepage(). pageout_cluster() tries to find a group of dirty pages around target page, called „pivot“ page of the cluster. If group of suitable size is found, ->writepages() is called for it, otherwise, page_cluster() falls back to ->writepage(). This is supposed to help in work-loads with significant page-out of file-system pages from tail of the inactive list (for example, heavy dirtying through mmap), because file system usually writes multiple pages more efficiently. Should also be advantageous for file-systems doing delayed allocation, as in this case they will allocate whole extents at once. Few points: swap-cache pages are not clustered (although they can be, but by page->private rather than page->index) only kswapd do clustering, because direct reclaim path should be low latency. this patch adds new fields to struct writeback_control and expects ->writepages() to interpret them. This is needed, because pageout_cluster() calls ->writepages() with pivot page already locked, so that ->writepages() is allowed to only trylock other pages in the cluster. Besides, rather rough plumbing (wbc->pivot_ret field) is added to check whether ->writepages() failed to write pivot page for any reason (in latter case page_cluster() falls back to ->writepage()). Only mpage_writepages() was updated to honor these new fields, but all in-tree ->writepages() implementations seem to call mpage_writepages(). (Except reiser4, of course, for which I'll send a (trivial) patch, if necessary).: vm_07-proc-stack.patch
Export kernel backtrace in /proc/<pid>/task/<tid>/stack. Useful when debugging deadlocks. This somewhat duplicates functionality of SysRq-T, but is less intrusive to the system operation and can be used in the scripts. Exporting kernel stack of a thread is probably unsound security-wise. Use with care. Instead of adding yet another architecture specific function to output thread stack through seq_file API, it introduces „iterator“ void do_with_stack(struct task_struct *tsk, int (*actor)(int, void *, void *, void *), void *opaque) that has to be implemented by each architecture, so that generic code can iterate over stack frames in architecture-independent way. lib/do_with_stack.c is provided for archituctures that don't implement their own. It is based on __builtin_{frame,return}_address().: vm_08-proc-sleep.patch
export per-process blocking statistics in /proc/<pid>/task/<tid>/sleep and global sleeping statistics in /proc/sleep. Statistics collection for given file is activated on the first read of corresponding /proc file. When statistics collection is on on each context switch current back-trace is built (through __builtin_return_address()). For each monitored process there is a LRU list of such back-traces. Useful when trying to understand where elapsed time is spent.: vm_09-ll_merge_requests_fn-cleanup.patch
ll_merge_requests_fn() assigns total_{phys,hw}_segments twice. Fix this and a typo. Merged into -mm.: vm_0a-deadline-iosched.c-cleanup.patch
Small cleanup.

rmap-cleanup.patch and WRITEPAGE_ACTIVATE-doc-fix.patch were merged into Linus tree.

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

names

2005-06-08T12:51:00.000Z

If you do not know the names, the knowledge of things will be lost, too.

Carolus Linnaeus

Если бы я знал, что такое электричество...

2005-05-26T08:16:00.000Z

(Posted at Борис Борисович™ LJ community)

Одним душным предгрозовым вечером 24-го мая Борис Борисович™ прогуливался по Капотне. Наскучив разглядыванием индустриальных пейзажей, он решительно направился к белевшему в сумраке зданию, позади которого проглядывали электрического вида конструкции. Сотрудники подстанции выглядели озабоченными и внимания на Бориса Борисовича™ не обращали. Лишь один из них, страшно возбуждённый, спросил: „Кто клал этот кабель?!“. „Я не знаю“ --- пожал плечами Борис Борисович™ и, пройдя дальше, очутился в коротком, тускло освещенном тупичке. На дальней стене виднелся пыльный рубильник, рядом надпись: „Проверено. Гаврилов, 1964.“. Положив на рубильник руку, и ощутив холод металла, Борис Борисович™ прошептал: „Если бы я знал, что такое электричество...“, решительно дернул вниз, развернулся на левом каблуке, сделал шаг и вышел на улицу.

Порывшись в карманах он нашёл телефон, поморщил лоб, вспоминая номер и, не обращая внимания на раздавшийся позади шум, набрал: 2-12-85-06. Телефон молчал.

SuSE owns YOU.

2005-05-23T12:28:00.000Z

SuSE Yast2 online update (YOU) is a disaster. Yesterday, after downloading more than hundred megabytes of updates from SuSE FTP site, it „updated“ kernel and NVidia dirvers so that they stopped working together. It also silently changed /etc/X11/XF86Config, corrupted /etc/dictd.conf, and installed a bunch of libraries with wrong permissions. It took me about 4 hours to fix all that.

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

The Cook, The Thief, His Wife and Her Lover go to the masses.

2005-04-22T17:41:00.000Z

Yesterday, Russian nation-wide TV Channel Россия, broadcast Peter Greenway's The Cook, The Thief, His Wife and Her Lover. Isn't there is something very Greenwayish in the image of 40 million people turning their TV sets on to relax after a hard day only to be confronted with what can be only viewed, but not described?

--Tags:-[Cinema]-----------

S. MacLane dies

2005-04-17T16:19:00.000Z

Saunders MacLane passed away on the morning of April 14.

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

gcc error message

2005-04-12T18:58:00.000Z

Quite some time ago (in the previous century), gcc greeted me with the following self-explanatory message.

My feelings toward C++ only increased since then.

[Corrected 2005.06.08 to include message by reference and avoid damaging layout.]

--Tags:-[Programming]-[C++]-----------

Inaccessible Cardinals

2005-04-12T10:31:00.000Z

„On the Consistency of Choice for Strongly Inaccessible Cardinals“.
„О непротиворечивости выбора сильно недостижимых кардиналов“.
In this from CNN or from Seminaire Bourbaki Novembre 1974 56`eme annee?

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

purelisp: object types

2005-04-11T17:32:00.000Z

As was noted in the previous post, objects in purelisp are partitioned into disjoint types.

types of objects

Some LISP object types have read syntax, which is a way to generate string representation of a given object. Built-in function (read) builds object given its string representation. Read syntax is given together with description of object types below.

Number. Represent arbitrary range integers (implemented in local.purelisp.eval.LInt by java.math.BigInteger). Number evaluates to itself, cannot be applied to anything, supports basic arithmetic operations.

read syntax for integers

10
0o12
0xa
0t1010

all represent number 10

String. Evaluates to itself, cannot be applied. Implemented on top of java.lang.String.

Environment. Environment is used to evaluate objects of type symbol. Specifically, each environment contains bindings from symbols to objects. Binding can be thought of as a pair (s, o), where s is a symbol, and o is an object s is bound to. Environment, therefore, is a partial function from symbols to objects. New bindings can be installed and value symbol is bound to can be changed.

Environments are arranged into tree-like hierarchy: each environment (except the root of the tree) has parent environment, and if symbol binding is not found in the environment, search is repeated in the parent recursively. Environment is said to extend its parent. At the top of the tree is global environment that contains bindings for standard LISP symbols. Interactive interpreter maintains its own environment where user adds new or modifies existing symbol bindings. There is second environment hierarchy, not affected by LAMBDA evaluation, used to implement traditional LISP dynamic scoping, but it is not current used in the language. Dynamic parent environment can be accessed through (env-dynamic env) built-in function.

During computation there always is so-called current environment. Initially it is environment of interactive interpreter, later it can be replaced when applying LAMBDA functions (see below) or evaluating (eval-in env o) built-in function (see below). Evaluation is always performed in the current environment, and, therefore, there is no need to explicitly mention evaluation environment.

Environments have no read syntax.

Symbol. Symbol is a LISP object with unique name. Name is the only identity and state that symbol has. Symbols are used to point to other objects. It has to be stressed that while superficially similar to variables in other languages, symbols are quite different:

symbol has NO value attached to it. It can be used as a key to look up value in environment, but in different environments it can have different values.
symbol is first-class object itself: it can be stored in data-structures including environments (so that value of symbol can be another symbol).

Symbols cannot be applied and their evaluation was described above (see Environment).

Read syntax for a symbol is just its name. If unknown yet valid identifier is read, new symbol is created.

Symbols, integers, and strings are collectively known as atoms.

Cons cell. Cons cell is a pair of references to other LISP objects. First and seconds references are idiosyncratically known as CAR and CDR, and are accessed through (car c) and (cdr c) built-in functions respectively. Cons cells are used to build linked lists: CAR of the first cell in a list points to the first object in the list, CDR point to the second cell in the list, whose CAR points to the second object in the list, and CDR points to... List it terminated by the pointer to NIL (see below).

Obviously, much more general possibly cyclic data-structures, can be built from cons cells. We shall call NIL terminated lists described above well-formed lists. If list is terminated by reference to an object that is neither cons cell nor NIL, it will be called dotted list, otherwise data-structure rooted at the cons cell is called improper list

read syntax for well-formed lists

(1 2 3)
(1 (1 2 "foo") "bar")

read syntax for dotted lists

(1 2 . 3)

Note that dotted list notation can be used to represent any cons cell whose CAR and CDR have read syntax: (A . B) builds cons cell with A as CAR, and B as CDR.

Cons cell cannot be applied, and has peculiar and very important evaluation rule. To evaluate cons cell following is done in order:

if CDR of cell it not well-formed list, abort evaluation;
cell's CAR is evaluated, let's call resulting object F;
create copy of CDR list, i.e., create new well-formed list containing pointers to the same objects and in the same order as CDR of cell being evaluated. Call first cons cell of resulting list A0;
if F is built-in function or LAMBDA function, evaluate all objects in A0 and create a list of evaluation results called A1. Otherwise let A1 be A0;
apply F to A1.

This obviously accounts for neither concurrency nor re-entrancy issues (i.e., structure of argument list could change while evaluated, either as result of said evaluation, or due to some concurrent activity).

Basically, to evaluate well-formed list, its CAR is evaluated and applied to the remaining elements of list as arguments. Arguments are evaluated if CAR evaluates to function (either built-in or LAMBDA), and are not evaluated otherwise (which leaves us with CAR evaluating to special form).

NIL. NIL is a special object the denotes empty list. It is used to define well-formed lists above. NIL object is bound to symbol "nil" in the global environment. Cannot be applied, evaluates to itself. As a special exception, built-in functions (car) and (cdr) can be applied to NIL and return NIL in this case.

read syntax for NIL

nil

LAMBDA. LAMBDA a is LISP object (special form) used to create lambda-functions. First, the notion of lambda-form is needed. Lambda form is a cons cell at which following well-formed list is rooted:

LAMBDA form

(lambda (P1 ... PM) E1 ... EN)

First element of lambda form can be anything that evaluates to LAMBDA (e.g., "lambda" symbol). Note that this makes notion of lambda-form dependent on the environment in which form is evaluated.
Second element of lambda-form is well-formed list called list of parameters. Elements of this list are called parameters. In traditional LISP, parameters have to be symbols. Purelisp has some extension (to be described later.) Parameters list may be empty.
Remaining elements of lambda-form are said to constitute its body. Body may be empty.

LAMBDA form examples

(lambda (x y) y)
(lambda (f) ((lambda (x) (f (x x))) (lambda (y) (f (y y)))))
(lambda nil 3)

Lambda-form is not treated in any special way by the interpreter. Instead its evaluation is done as for any cons cell (see above), and results in application of LAMBDA to the list ((P1 ... PM) E1 ... EN). As LAMBDA is special form, elements of this list are not evaluated. Result of this application is new LISP object: lambda-function.

Lambda-function. Lambda-function can be thought as a pair (ENV, ((P1 ... PM) E1 ... EN)), where env is an environment in which lambda-form was evaluated. Lambda-function evaluates to itself. Its importance stems from its application rule. To apply lambda-function (ENV, ((P1 ... PM) E1 ... EN)) to the list of arguments (A1 ... AK) do the following:

if K != M abort application;
create new environment ELOCAL extending ENV;
for each i: 1 <= i <= M, bind Pi to Ai in ELOCAL;
for each i: 1 <= i <= N, evaluate Ei in ELOCAL;
result of application is the result of EN evaluation, or NIL if body is empty.

Again, this doesn't account for pathological cases where structure of lambda-form recorded in lambda-function changes during evaluation.

As one can see lambda-functions allow programmer to construct objects with arbitrary application rules, and, therefore (through lists of the form (lambda-function A1 ... AM)), objects with arbitrary evaluation rules. Lambda-functions are main computation-structuring mechanism in LISP.

[in next installation: what makes purelisp different?]

--Tags:-[Programming]-[LISP]-----------

purelisp: introduction

2005-04-11T16:45:00.000Z

Some time ago (I just re-checked and... Good Lord it was in October of 2003, time moves fast indeed) I wrote simple LISP interpreter (purelisp) in Java. This, otherwise seemingly pointless activity could be justified as an exercise in SableCC usage.

SableCC

SableCC is a nice compiler building toolkit with pretty standard (by nowaday standards) set of features: on input it takes a description of the language, and produces Java classes with lexer and skeleton parser. Language is defined by a grammar and terminals are defined by regular expressions. Our simple version of LISP uses lisp.grammar as the definition, note that larger fraction of language definition is a table indicating what unicode characters are "letters" in the sense of being acceptable as part of an identifier.

From language definition SableCC generates:

Java classes corresponding to tokens of the grammar.
Lexer class that transforms input stream into sequence of tokens (optionally omitting some tokens, e.g., white-spaces).
Parser class that constructs typed AST (abstract syntax tree) from the sequence of tokens.
Set of tree-walker base classes. Tree-walkers traverse tree in specific order, calling certain methods of tree node object when entering and leaving it. This is called "visitor pattern" by the people in dire need of names.

The only thing left to do to finish simple interpreter is to subclass suitable tree-walker with the class that interprets program while traversing its AST. LISP program (as LISP fans will never cease to remind us) is but a LISP data, hence, natural choice for our interpreter is to build LISP object as a result of tree traversal. And building such an object is indeed simple: local.purelisp.eval.TreeBuilder.

purelisp introduction

Computational universe of purelisp consists of objects, partitioned into disjoint types. Objects can be evaluated. Evaluation takes as input an object to be evaluated and auxiliary object of type environment that affects evaluation. Result of evaluation is an object again. This can be the same object that is being evaluated, some already existing object, or new object. Ultimately, evaluation can result in error, and no result is produced in this case. Rules of evaluation for some objects are hard-wired into interpreter. For other objects, evaluation is multi-step process defined in terms of some actions performed on other objects.

In particular, one important type of objects, viz. cons cells have evaluation defined in terms of application of an object to a sequence of objects (referred to as arguments of application). Rules of application are again type-dependent: hard-wired into interpreter (e.g. for built-in functions), or defined through combination of evaluation and application.

Evaluation and application are fundamental mutually-recursive operations on top of which computation is implemented in LISP.

LISP program is actually nothing more than description of object according to some standard syntax. LISP interpreter reads this description, build corresponding objects and evaluates it in some "current" environment.

[in next installation: object types in purelisp.]

--Tags:-[Programming]-[LISP]-----------

page tickets

2005-04-05T14:45:00.000Z

MACH VM had (or still has if Mac OS X counts) an interesting detail in its VM scanner implementation:

osfmk/vm/vm_page.h

/*
* Each page entered on the inactive queue obtains a ticket from a
* particular ticket roll. Pages granted tickets from a particular
* roll generally flow through the queue as a group. In this way when a
* page with a ticket from a particular roll is pulled from the top of the
* queue it is extremely likely that the pages near the top will have tickets
* from the same or adjacent rolls. In this way the proximity to the top
* of the queue can be loosely ascertained by determining the identity of
* the roll the pages ticket came from.
*/

--Tags:-[OS]-[Kernel]-----------

the power of gdb

2005-03-31T10:31:00.000Z

Yesterday I was running long file system stress test (fsx if you want to know) when X server on my workstation locked up completely (because it ran on a heavily patched kernel as turned out later). One consequence of this was that xterm which fsx output was going to, went, together with X server, to the land of Eternal GoodDrawable and stopped caring about silly clients sending frantic write(2)s to it.

fsx stopped which was unfortunate. So I logged to the test box and did

Session

$ gdb fsx $(pgrep fsx) # attach to the fsx
(gdb) bt
#0 0x90010760 in write ()
#1 0x90026104 in _swrite ()
#2 0x90020c80 in __sflush ()
#3 0x90031e00 in __fflush ()
#4 0x90006e4c in __sfvwrite ()
#5 0x90006ef0 in __sprint ()
#6 0x90006a48 in __vfprintf ()
#7 0x9000c76c in vfprintf ()
#8 0x000025a0 in prt ()
#9 0x00004a0c in dotruncate ()
#10 0x000051c0 in test ()
#11 0x0000659c in main ()
#12 0x0000220c in _start (argc=2, argv=0xbffffa14, envp=0xbffffa20) at /SourceCache/Csu/Csu-46/crt.c:267
#13 0x00002080 in start ()
(gdb) # yes it really stuck doing write to the stdout. And yes, this is Mac OS X.
(gdb) # now fun part begins
(gdb) call (int)close(1) # close standard output
$1 = 0
(gdb) # it worked! Leave fsx in piece...
(gdb) detach
(gdb) quit

and test was running further happily.
The moral: gdb can save your day.

--Tags:-[Hacking]-[OSX]-----------

RSX

2005-03-24T20:27:00.001Z

[expanded. 2004.03.25]
Lately, I looked through sources of RSX executive at bitsavers.org. RSX (which stands for Realtime System eXecutive or Resource Sharing eXecitive) is a collective name for the series of operating systems DEC developed for its PDP processors. Initial version was RSX-15 developed for PDP-15 processor (a member of 18b family of DEC processors---poorer and ultimately abandoned cousins of another branch that got us PDP-11) by Sam Reese, Dan Brevik, Hank Krejci and Bernard LaCroute. See: a bit of history, original design, official DEC reference manual. Later on, RSX was ported to PDP-11 (yes, version numbers can very well go down), resulting in succession of RSX-11A, RSX-11B, RSX-11C, and RSX-11D, the latter being full-blown operating system, multi-user and multi-tasking. You think it's quite an achievement for a platform with 32K bytes of primary storage? Obviously David Cutler wasn't impressed, as he re-wrote it from scratch to consume less resources giving birth to RSX-11M (and later to VAX VMS, and Windows NT). Unfortunately, no RSX-11 kernel sources seem available (neither A-D, nor M and beyond versions), except for little witty pieces here and there (bitsavers, however sports materials from DEC's classes on RSX-11 internals). XVM/RSX-15 sources are available at bitsavers:

Executive proper: P1 and P2, and
MCR (Monitor Console Routine)

Why would one waste time looking through the obscure non-portable kernel that ran on a hardware decommissioned quarter of century ago? A lot of reasons:

It is radically different from UNIX, which is, basically, the only publicly available kernel source base to-day.
It was written at the times when computing was still young and engineers didn't take a lot of things for granted, so one can see how and why they come to their designs.
It's rather small by nowadays standards and easy to understand.
It has surprisingly good comments.
It was one of the first and probably (for quite a long time) largest open-source projects: hundreds of megabytes of software for RSX were available in the source form (DECUS tapes)
I agree with the sentiments R. Pike, esq. expressed in Systems Software Research is Irrelevant article (also see Rik van Riel's note): modern operating system research revolves around (or, rather, inside of) a cluster of well-known old ideas. By looking at the roots of operating system development, one sees that these ideas are but choices.
Nostalgia, of course. At the end of 80s I worked on some PDP clones: Электроника-100/25, СМ-4.

At the center of RSX-15 is its executive, also known as monitor or kernel. This is small program written in PDP-15 assembly language, that maintains following abstractions:

memory partitioning: rudimentary memory management scheme. Memory is partitioned during system generation into partitions and common blocks.
task and scheduling.: Task is a machine code that can be executed under control of executive. Task is installed when it is known to the executive (specifically, registered in STL---global System Task List). Tasks are created by task builder---special task that builds task by linking relocatable code with libraries and storing task on disk in the same format it will be stored in the primary storage (i.e., task loading is just copying it from disk to the core, which is important for real-time operating system). Some tasks are resident, which means they are always in core. Installed task may be requested for execution (placed into ATL---Active Task List), and get its share of processor cycles subject to priority and memory constraints. Simple fixed priority scheme is used. Memory is managed on partition granularity: each task has a partition assigned to it during build, and will be loaded into core when said partition is free. Partition can be used for one task only.
interrupt management: executive itself handles clock interrupt only. All other interrupts are handled by special IO Handler Tasks (IOHTs), any installed task may become IOHT by connecting to interrupt line.
device management.: list of physical devices and mapping between physical and logical units (LUNs). Per-device prioritized IO queues. Asynchronous IO as a default mechanism. LUNs are global.
interface to space management for disks: bitmap of free blocks. Implemented by IO handler task, not executive.
interface to simple flat file system.: Implemented by IO handler task.

[...To be continued...]
Here are some interesting features:

usage of API (Automatic Priority Interrupts) to implement concurrency control.
In RSX-11M this was replaced with FORK processing: interrupts never directly access kernel tables, hence, no synchronization is required on the uniprocessor. Similar to soft interrupts.
separation of STL (system task list) and ATL (active task list)---a form of two level scheduling: long level scheduling decisions are made by installing task into STL, and assigning resources (devices and core partitions) to it. Short term scheduling is done by scanning ATL which is sorted by task priority.
interrupt is viewed (and used) more like asynchronous goto, rather than asynchronous procedure call. For example, there is a procedure that scans ATL (active task list, sorted by task priority). Interrupt may add task to the ATL, and so scan has to be restarted if interrupt happens during it. To achieve this, interrupt handlers do a jump to the address stored in L6TV ("Level Six Transfer Vector"). When normal task runs, L6TV points to the routine that saves registers in the task's "core partition". When ATL scan is started, L6TV is modified to point to the ATL scan procedure itself. As a result, if interrupt happens, scan will be restarted automatically. Note, that interrupt handlers do _not_ save registers in the stack (they do not create stack frame).
"pseudo partitions" that overlay IO memory used to control devices from non-privileged tasks.
RSX is a radical micro-kernel: the only thing executive handles is processor scheduling. Everything else (including processing of interrupts other than clock) is handled by tasks. One consequence of this is that executive interface is fundamentally asynchronous: most calls take event variable as an argument, and calling task may wait for call completion by doing
```
        WAITFOR eventvar
```
This is impossible to do in UNIX where system calls are served on the kernel stack permanently attached to the process. In UNIX, kernel is a library executing in protected mode, while RSX is a collection of autonomous tasks each running with its own stack (this architecture, of course, requires very fast context switches).
file system as special device driver layered on top of driver for underlying stable storage device: file oriented device. Note, that this also unifies the notion of file and device, but... other way around.
SEEK call is used to open particular file on a devcie. After that LUN is effectively narrowed (in EMACS sense) to mean opened file.
all executables are known to the executive (listed in STL).
system image can be stored on the permanent storage (by SAVE) and booted from (warm start), like in Smalltalk or LISP system.
instead of having separate run-queues and wait-queues, tasks are kept in single ATL. As the only synchronization mechanism available is event variable, "scheduler" simply checks whether waiting tasks can be run while scanning ATL.
tasks are so light-weight that clock queue (callouts in UNIX terms) is a list of tasks rather than functions.
each task provides its own procedure to save its context on preempt
no security of any sort. Give them enough rope.

--Tags:-[OS]-[Kernel]-----------

adaptive replacement

2003-12-23T16:04:00.000Z

„adaptive replacement better than Working Set?“ has (an implicit) idea: VM page replacement should keep a „spectrum“ of accesses to a given page. Too high and too low frequences should be filtered out, because they:

represent correlated references, and
irrelevant,

respectively

--Tags:-[OS]-[Kernel]-----------

	\(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\)