A Layered Kernel: Proposal

A Layered Kernel: Proposal

[Grigor Gatchev]

A Layered Kernel
Proposal

The idea is to structure logically the kernel into two (or more) layers,
with explicitly defined interfaces between them.

Not a Microkernel

Some of my friends decided that this is actually a (partial) microkernel
idea. Not so:

- a microkernel is _physically_ divided into separate modules, while
logically it may consist of one or more layers;
- a layered kernel is _logically_ divided into layers, while physically
it may consist of one or more modules.

A microkernel may be (and often is) logically single-layered. A
many-layered kernel may be compiled as a big kernel.

Comparison

Both models have advantages. Single layer provides for better
integration, and apparently saving some work. Multi-layer provides for
better security, abstraction, code, and eventually quality.

Traditionally, Unixes use a layered approach - its assets have proven to
give more than the single-block. So, a layered kernel may be more natural
to a Unix-rooted system, and may give better results.

Details

Currently, it seems reasonable to form two layers: Resources and
Personality.

The Resources layer is the natural place for the low-level stuff - device
drivers, basic sheduler, basic memory management and protection, etc.

The Personality layer is the place for the Linux API and ABI, etc.

Some parts, eg. filesystems, TCP/IP stack etc, may bear a discussion over
their exact place. If need, an intermediate layer may be defined.

Each layer draws resources from the lower one, adds functionality on its
top, and possibly changes or hides some of its functionalities,
class-like. It runs the upper layer in encapsulation, eg. protected mode,
and works on top of the lower layer (Resources - over the physical
hardware). Possibly a lower layer can run simultaneously two or more
upper layers, in a multi-tasking way.

If a layer is a separate file, can be called like a program. If part of a
"big kernel", can be called directly, or through exported hooks. Other
models are possible, too.

A layer may be emulated by a layer interface emulator. For example, you
may run a Resources emulator as a program, and a standard Personality
over it, achieving "kernel over kernel". Configuring the emulator, you
pass to the child kernel, and its users and software, a virtual machine
of your choice.

Advantages

Improved source: A well defined inter-layer interface separates logically
the kernel source into more easily manageable parts. It makes the testing
easier. A simple and logical lower layer interface makes learning the
base and writing the code easier; a simple and logical upper layer
interface enforces and helps clarity in design and implementation. This
may attract more developers, ease the work of the current ones, and
increase the kernel quality while decreasing the writing efforts. The
earlier this happens, the better for us all.

Anti-malware protection: Sources of potentially dangerous content can be
filtered between the kernel layers by hooked or compiled-in modules. As
with most other advantages, this is achievable in a non-layered kernel
too, but is more natural in a layered one. Also, propagation of malware
between layers is mode difficult.

Security: A layer, eg. Personality, if properly written, is eventually a
sandbox. Most exploits that would otherwise allow a user to gain
superuser access, will give them control over only this layer, not over
the entire machine. More layers will have to be broken.

Sandboxing: A layer interface emulator of a lower, eg. Resources layer
can pass a configurable "virtual machine" to an upper, eg. Personality
layer. You may run a user or software inside it, passing them any
resources, real or emulated, or any part of your resources. All
advantages of a sandbox apply.

User nesting: The traditional Unix user management model has two levels:
superuser (root) and subusers (ordinary users). Subusers cannot create
and administrate their subusers, install system-level resources, etc.
Running, however, a subuser in their own virtual machine and Personality
layer as its root, will allow tree-like management of users and resources
usage/access. (Imagine a much enhanced chroot.)

Platforming: It is much easier to write only a Personality layer than an
entire kernel, esp. if you have a layer interface open standard as a
base. Respectively, it's easier to write only a Resources layer, adding a
new hardware to the "Supported by Linux" list. This will help increasing
supported both hardware and platforms. Also, thus you may run any
platform on any hardware, or many platforms concurrently on the same
hardware.

Heterogeneous distributed resources usage: Under this security model,
networks of possibly different hardware may share and redistribute
resources, giving to the users resource pools. Pools may be dynamical,
thus redistributing the resources flexibly. This mechanism is potentially
very powerful, and is inherently consistent with the open source spirit
of cooperativity and freedom.

Disadvantages:

More work to start: Initially the model change will take more effort.
(Most will be spent on clarifying and improving the code; most of the
layered model requirements are actually code quality requirements.
Without the new model, the bad design/code correction can be left for a
later stage.)

Performance: Badly designed and/or implemented inter-layer interfaces may
slow down the kernel speed, decreasing the system performance.

Compatibility: Even if the new model is 100% compatible with old
upper-level software, in practice it will surface better the advantages
of some newer stuff, eg. sysfs, and will increase the stress on them,
thus obsoleting sooner some old software. With the old model, the change
may be delayed further.

Other issues:

Need for it: Without any consideration for a layered model, the kernel
source is already structured in a way convenient for going with it; in a
sense, most of the work is already done. Which shows that the need for a
layered model is inherent to the kernel, even if not explicitly defined
and noticed. This way we just follow the system logic.

Authority: If not approved by the top developers, the restructuring may
fork the kernel development. As a result, the layered model may not be
able to gain sufficient resources to survive. The standard model will
probably survive, but may also suffer a loss of developers.

The right moment: The best moment for starting the change is when a new
kernel is declared stable version, and the tree for the next development
version is to be formed. This doesn't happen often, and the change will
be more difficult in another time. (That is why this proposal is made
now.)

Why all this?

Like the mutations, radical ideas are most often bad. Banning them as a
principle, however, may eventually doom Linux to a dinosaur fate. (And we
tend to do it - lately big improvements come to Linux only from outside.
The ELF format, sysfs, NUMA support... However, BSD, Solaris and IRIX
seem to fade; soon we will have only Windows to rely on for new
kernel-level things.)

The advantages of the idea above seems to overweight the disadvantages;
even its disadvantages have strong positive traits. Is it possible that a
discussion may prove it good?


Grigor Gatchev

Re: A Layered Kernel: Proposal

[Carlos Silva]

>
> A Layered Kernel
> Proposal
>
> (...)


i really like the idea. maybe it will be in the 2.7 branch of the kernel...

Re: A Layered Kernel: Proposal

[Rik van Riel]

On Tue, 24 Feb 2004, Grigor Gatchev wrote:

> A Layered Kernel
> Proposal

Sounds like a reasonable description of how Linux already
works, with the exception of badly written code that has
layering violations.

I'm all for cleaning up the badly written code so it fits
in better with the rest of the kernel ;)

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> Advantages
> 
> Improved source: A well defined inter-layer interface separates logically
> the kernel source into more easily manageable parts. It makes the testing
> easier. A simple and logical lower layer interface makes learning the
> base and writing the code easier; a simple and logical upper layer
> interface enforces and helps clarity in design and implementation. This
> may attract more developers, ease the work of the current ones, and
> increase the kernel quality while decreasing the writing efforts. The
> earlier this happens, the better for us all.
> 

There is already a lot of layering in the kernel.  It seems to be doing 
what you propose to some extent.

> Anti-malware protection: Sources of potentially dangerous content can be
> filtered between the kernel layers by hooked or compiled-in modules. As
> with most other advantages, this is achievable in a non-layered kernel
> too, but is more natural in a layered one. Also, propagation of malware
> between layers is mode difficult.
> 
> Security: A layer, eg. Personality, if properly written, is eventually a
> sandbox. Most exploits that would otherwise allow a user to gain
> superuser access, will give them control over only this layer, not over
> the entire machine. More layers will have to be broken.
> 
> Sandboxing: A layer interface emulator of a lower, eg. Resources layer
> can pass a configurable "virtual machine" to an upper, eg. Personality
> layer. You may run a user or software inside it, passing them any
> resources, real or emulated, or any part of your resources. All
> advantages of a sandbox apply.

Not true.  What you are asking for is userspace protection to kernel 
modules.  You won't get that unless you use a micro-kernel approach, or 
run different parts of the kernel on different (to be i386 arch 
specific) ring in the processor.  Once you get there, you have to deal 
with the various processor errata since not many OSes use rings besides 
0 and 3 (maybe ring 1?).

> User nesting: The traditional Unix user management model has two levels:
> superuser (root) and subusers (ordinary users). Subusers cannot create
> and administrate their subusers, install system-level resources, etc.
> Running, however, a subuser in their own virtual machine and Personality
> layer as its root, will allow tree-like management of users and resources
> usage/access. (Imagine a much enhanced chroot.)
> 

That is differing security models, and it's being worked on with (I 
forget the term) the security module framework.

> Platforming: It is much easier to write only a Personality layer than an
> entire kernel, esp. if you have a layer interface open standard as a
> base. Respectively, it's easier to write only a Resources layer, adding a
> new hardware to the "Supported by Linux" list. This will help increasing
> supported both hardware and platforms. Also, thus you may run any
> platform on any hardware, or many platforms concurrently on the same
> hardware.
> 

There is arch specific, and generic setions of the kernel source tree 
already.  How do you want to improve upon that?

> Heterogeneous distributed resources usage: Under this security model,
> networks of possibly different hardware may share and redistribute
> resources, giving to the users resource pools. Pools may be dynamical,
> thus redistributing the resources flexibly. This mechanism is potentially
> very powerful, and is inherently consistent with the open source spirit
> of cooperativity and freedom.

Single system image clusters are hard enough where each node is the same 
  arch, and very hard, or almost impossible when dealing with mixed 
processor arch or 32/64 bit processors.

See OpenSSI and OpenMosix.

Mike

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Tue, 24 Feb 2004, Rik van Riel wrote:

> On Tue, 24 Feb 2004, Grigor Gatchev wrote:
>
> > A Layered Kernel
> > Proposal
>
> Sounds like a reasonable description of how Linux already
> works, with the exception of badly written code that has
> layering violations.

It's not about how Linux works, but about how the kernel should work. But
you are right, the kernel is already structured in a way convenient to go
for it.

> I'm all for cleaning up the badly written code so it fits
> in better with the rest of the kernel ;)

Unhappily, cleaning up would not be enough. A separation of the kernel
layers, to the extent that one may be able to use them independently, and
to plug modules between them (having the appropriate access) may be
better.

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Tue, 24 Feb 2004, Mike Fedyk wrote:

> There is already a lot of layering in the kernel.  It seems to be doing
> what you propose to some extent.

Yes. And even if this proposal is not accepted, there inevitably will be more
and more of layering. This is the logic of the kernel usage and development.
Eventually the kernel will come to a full layered model anyway.

If so, then... the sooner, the better.

> > Sandboxing: A layer interface emulator of a lower, eg. Resources layer
> > can pass a configurable "virtual machine" to an upper, eg. Personality
> > layer. You may run a user or software inside it, passing them any
> > resources, real or emulated, or any part of your resources. All
> > advantages of a sandbox apply.
>
> Not true.  What you are asking for is userspace protection to kernel
> modules.  You won't get that unless you use a micro-kernel approach, or
> run different parts of the kernel on different (to be i386 arch
> specific) ring in the processor.  Once you get there, you have to deal
> with the various processor errata since not many OSes use rings besides
> 0 and 3 (maybe ring 1?).

These are two possible approaches. Still another is to have the lowest
layer export functions for memory handling - thus only the lowest layer
will have to run in ring 0 (almost all arch that support Linux have a
corresponding ability), and will handle the protection requests from the
upper layers... Other approaches exist, too. A discussion may help to
clarify which is the best.

> > User nesting: The traditional Unix user management model has two levels:
> > superuser (root) and subusers (ordinary users). Subusers cannot create
> > and administrate their subusers, install system-level resources, etc.
> > Running, however, a subuser in their own virtual machine and Personality
> > layer as its root, will allow tree-like management of users and resources
> > usage/access. (Imagine a much enhanced chroot.)
>
> That is differing security models, and it's being worked on with (I
> forget the term) the security module framework.

Within a layered kernel scheme, this tree-like model is very natural and
simple: all protection is provided by the standard kernel mechanisms. Of
course, it maybe can be improved; that is what the discussion is for.

> > Platforming: It is much easier to write only a Personality layer than an
> > entire kernel, esp. if you have a layer interface open standard as a
> > base. Respectively, it's easier to write only a Resources layer, adding a
> > new hardware to the "Supported by Linux" list. This will help increasing
> > supported both hardware and platforms. Also, thus you may run any
> > platform on any hardware, or many platforms concurrently on the same
> > hardware.
>
> There is arch specific, and generic setions of the kernel source tree
> already.  How do you want to improve upon that?

Currently, Linux supports (actually, is) only one, Unix-descended
platform. With a layered model, an emulator, eg. Wine, could be easily
rewritten as a Personality layer, and this would turn it instantly into
a free Windows. A modification of the Linux sofware and tools could
produce a free Solaris. Some people may like a free OS/2, QNX, VxWorks
etc. Other platforms will became easier to create and test, thus helping
the free software evolution. On most architectures, you will be able to
emulate another processor right in the kernel, either directly, or by a
code emulator: all other will go then much easier. Much more advantages
exist...

Now, to the point. When you have -one- platform over -many- hardwares, it
is easy to compile a version for your hardware - and that is as much as
you can get. However, when you have -many- platforms over -many-
hardwares, you lose in this way additional options. You can still compile
a specific platform for a specific hardware, but cannot anymore produce a
multi-platform system over a single hardware, with the ability for many
platforms to run concurrently, to have flexible distribution of resources
between them, etc. (Of course, you may rewrite the source as to be able to
compile such one, but this will effectively amount to the proposal
discussed.)

> > Heterogeneous distributed resources usage: Under this security model,
> > networks of possibly different hardware may share and redistribute
> > resources, giving to the users resource pools. Pools may be dynamical,
> > thus redistributing the resources flexibly. This mechanism is potentially
> > very powerful, and is inherently consistent with the open source spirit
> > of cooperativity and freedom.
>
> Single system image clusters are hard enough where each node is the same
>   arch, and very hard, or almost impossible when dealing with mixed
> processor arch or 32/64 bit processors.
>
> See OpenSSI and OpenMosix.

Yes, not all of the road would be taken. But an important part will be
(see the discussion above). The rest will be already easier.

As a whole, the model seems to be:

a) logically consistent with the proven kernel development logic
b) solving naturally at once several current problems, and laying the
ground for solving more

That is what makes me wary about it - it seems like a "brilliant" idea.
However, it also seems rather logical, and worth considering and
discussing.


Grigor

Re: A Layered Kernel: Proposal

[Rik van Riel]

On Wed, 25 Feb 2004, Grigor Gatchev wrote:

> > I'm all for cleaning up the badly written code so it fits
> > in better with the rest of the kernel ;)
> 
> Unhappily, cleaning up would not be enough. A separation of the kernel
> layers, to the extent that one may be able to use them independently,
> and to plug modules between them (having the appropriate access) may be
> better.

Some parts of the kernel (eg. the VFS or the device driver
layers) can already do that, while others still have layering
violations.

I suspect that the least destabilising way of moving to a
more modular model would be to gradually clean up the layering
violations in the rest of the code, until things are modular.

Yes, I know it's a lot of work ...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: A Layered Kernel: Proposal

[Richard B. Johnson]

On Wed, 25 Feb 2004, Rik van Riel wrote:

> On Wed, 25 Feb 2004, Grigor Gatchev wrote:
>
> > > I'm all for cleaning up the badly written code so it fits
> > > in better with the rest of the kernel ;)
> >
> > Unhappily, cleaning up would not be enough. A separation of the kernel
> > layers, to the extent that one may be able to use them independently,
> > and to plug modules between them (having the appropriate access) may be
> > better.
>
> Some parts of the kernel (eg. the VFS or the device driver
> layers) can already do that, while others still have layering
> violations.
>
> I suspect that the least destabilising way of moving to a
> more modular model would be to gradually clean up the layering
> violations in the rest of the code, until things are modular.
>
> Yes, I know it's a lot of work ...

But the idea that the kernel should exist as a kind of onion,
depicted by child college professors in their children's coloring
books is wrong. The optimum operating system will always be the
one that performs its functions in the most expedient way, not
the one that is the "prettiest" or easiest to understand. There
can't be any such thing as a "layering violation".

Layering is wrong. However modularizing, although it may
have some negative effects, has many redeeming values. It
allows for the removal of dead code, code that will never
function in a particular system.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.24 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Wed, 25 Feb 2004, Rik van Riel wrote:

> On Wed, 25 Feb 2004, Grigor Gatchev wrote:
>
> > > I'm all for cleaning up the badly written code so it fits
> > > in better with the rest of the kernel ;)
> >
> > Unhappily, cleaning up would not be enough. A separation of the kernel
> > layers, to the extent that one may be able to use them independently,
> > and to plug modules between them (having the appropriate access) may be
> > better.
>
> Some parts of the kernel (eg. the VFS or the device driver
> layers) can already do that, while others still have layering
> violations.
>
> I suspect that the least destabilising way of moving to a
> more modular model would be to gradually clean up the layering
> violations in the rest of the code, until things are modular.

Definitely.

I believe that, a layered model mandated or not, kernel development will
go generally the same way. A clear goal may improve much the process, but
will not change the things to be done. Even if that model is mandated,
most probably first production versions will not be completely compliant
with it.

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

> But the idea that the kernel should exist as a kind of onion,
> depicted by child college professors in their children's coloring
> books is wrong. The optimum operating system will always be the
> one that performs its functions in the most expedient way, not
> the one that is the "prettiest" or easiest to understand. There
> can't be any such thing as a "layering violation".

Hm.

I won't agree. In my 25 years of programming, I am yet to see a case whe
ugly, "write-only" code performed well. And the cases when "pretty"
code has performed badly were rather rare.

Isolation and layering have already proved themselves a lot. If not so,
Unix would be dead, and we would be using now Multics or another similar
OS. Also, Windows would be immesurably superior to any Unix in existence,
especially in performance...

> Layering is wrong. However modularizing, although it may
> have some negative effects, has many redeeming values. It
> allows for the removal of dead code, code that will never
> function in a particular system.

I won't agree here, too. Dead code can be removed perfectly well from a
big kernel, too - maybe even easier. With a modular approach, you may
exclude certain module from your modules list, but I won't call that
removal of dead code.

Also, (logical) layering and modularizing do not contradict - they are
practically independent. I apologize for not being able to see the point
here.

Re: A Layered Kernel: Proposal

[Richard B. Johnson]

On Wed, 25 Feb 2004, Grigor Gatchev wrote:

>
> > But the idea that the kernel should exist as a kind of onion,
> > depicted by child college professors in their children's coloring
> > books is wrong. The optimum operating system will always be the
> > one that performs its functions in the most expedient way, not
> > the one that is the "prettiest" or easiest to understand. There
> > can't be any such thing as a "layering violation".
>
> Hm.
>
> I won't agree. In my 25 years of programming, I am yet to see a case whe
> ugly, "write-only" code performed well. And the cases when "pretty"
> code has performed badly were rather rare.
>
> Isolation and layering have already proved themselves a lot. If not so,
> Unix would be dead, and we would be using now Multics or another similar
> OS. Also, Windows would be immesurably superior to any Unix in existence,
> especially in performance...
>

Not correct. Layering has isolated the designer (coder) of a
function from the required understanding of its ultimate goal.
This construct started with the idea of 'objects' wherein
the coder didn't need to understand the underlying goal, only
the immediate logic of the function. The result is, _always_,
bloat where one function simply converts its data to that
required by another. The other function converts its data,
etc. Everybody wants to deal will objects and then can claim
that they have done their work.

Ultimately somebody in the coding food-chain needs to do
actual work, i.e., communicate with the hardware to get
the work done. If you get rid of the layers and layers
of absolute repetitive junk and do the work at hand, you
end up with a lean-and-mean kernel that outperforms
the ones that were written in the "layered" construct.

Early on, I wrote code in assembly. Everybody who wrote
code understood the ultimate goal. Later on, I had to
write in Pascal because it was "understandable" and,
therefore documentable. But ultimately I had to write
drivers in assembly to do the actual work. Then along
came 'C'. I had to write code in 'C'. Ultimately, I
had to do the actual work with drivers or runtime
libraries written in assembly. Then there came C++.
Nobody was able to do any actual work anymore. Instead,
with a coding staff of hundreds, only a few actually
understand what the code does. They make the ultimate
"objects" that talk to the hardware. You could throw
away 90 percent or more of the code, improving its
performance considerably in the process, by getting
rid of the ^$(^##)) layers and directly performing
the required function at the upper-most level.

So don't claim that layering does anything useful except
to create jobs. It is a make-work technique that creates
jobs for inadequate or incompetent programmers.

> > Layering is wrong. However modularizing, although it may
> > have some negative effects, has many redeeming values. It
> > allows for the removal of dead code, code that will never
> > function in a particular system.
>
> I won't agree here, too. Dead code can be removed perfectly well from a
> big kernel, too - maybe even easier. With a modular approach, you may
> exclude certain module from your modules list, but I won't call that
> removal of dead code.
>
> Also, (logical) layering and modularizing do not contradict - they are
> practically independent. I apologize for not being able to see the point
> here.
>

Cheers,
Dick Johnson
Penguin : Linux version 2.4.24 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: A Layered Kernel: Proposal

[Nikita Danilov]

Richard B. Johnson writes:

[...]

 > 
 > So don't claim that layering does anything useful except
 > to create jobs. It is a make-work technique that creates
 > jobs for inadequate or incompetent programmers.

Interesting that whole notion of layering and separation of concerns was
invented exactly during the design of "THE" OS kernel. By very competent
and adequate programmer.

http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD196.PDF

 > 

Nikita.

Re: A Layered Kernel: Proposal

[Christer Weinigel]

Nikita Danilov <Nikita@Namesys.COM> writes:

> Richard B. Johnson writes:
> 
> [...]
> 
>  > 
>  > So don't claim that layering does anything useful except
>  > to create jobs. It is a make-work technique that creates
>  > jobs for inadequate or incompetent programmers.
> 
> Interesting that whole notion of layering and separation of concerns was
> invented exactly during the design of "THE" OS kernel. By very competent
> and adequate programmer.
> 
> http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD196.PDF

Just because there's an academic paper written about something doesn't
mean that its right.  For once Richard is partially right, unneccesary
layering can really ruin a system.  Grigor said that in 25 years he
has seen few cases of pretty code performing badly, but look at the
failure of SysV streams, it's a really pretty layering model, but in
practice it turns out to be too slow for most anything useful.  

It's not too uncommon with drivers that breaks just because the actual
hardware won't fit into the model that is exposed via a layer.  For
example, look at the error recovery of the old Linux SCSI code: it's
hard to do proper error recovery, and it is much slower than it needs
to because first the low level driver tries to do error recovery and
later on the higher layers try to do error recovery too.  Multiply a
couple of retries in the SCSI middle layer with another couple of
retries after a timeout a few seconds at the SCSI controller layer and
you have a model where it takes a minute to do figure out that
something is wrong, for something that ought to take just a few
seconds.

Additionally, because of the strict layering it's not always possible
to hand up a meaningful error status from the lower layers to the
higher layers, it gets lost in the middle just because it didn't fit
into the layers model of the world.  It can also mean that it's not
possible to use the intelligent features of a smart SCSI controller
that can do complex error recovery on its own since most layers end up
exposing only the "least common denominator".

In the linux kernel I think that one of the most important things I've
learned from it: middle layers are usually wrong.  Instead of hiding a
device driver behind a middle layer, expose the low level device
driver, but give it a library of common functions to build upon.  That
way the driver is in control all the time and can use all the neat
features of the hardware if it wants to, but for all the common tasks
that have to be done, hand them over to the library.

  /Christer

-- 
"Just how much can I get away with and still go to heaven?"

Freelance consultant specializing in device driver programming for Linux 
Christer Weinigel <christer@weinigel.se>  http://www.weinigel.se

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On 25 Feb 2004, Christer Weinigel wrote:

> Just because there's an academic paper written about something doesn't
> mean that its right.  For once Richard is partially right, unneccesary
> layering can really ruin a system.  Grigor said that in 25 years he
> has seen few cases of pretty code performing badly, but look at the
> failure of SysV streams, it's a really pretty layering model, but in
> practice it turns out to be too slow for most anything useful.
>
> It's not too uncommon with drivers that breaks just because the actual
> hardware won't fit into the model that is exposed via a layer.  For
> example, look at the error recovery of the old Linux SCSI code: it's
> hard to do proper error recovery, and it is much slower than it needs
> to because first the low level driver tries to do error recovery and
> later on the higher layers try to do error recovery too.  Multiply a
> couple of retries in the SCSI middle layer with another couple of
> retries after a timeout a few seconds at the SCSI controller layer and
> you have a model where it takes a minute to do figure out that
> something is wrong, for something that ought to take just a few
> seconds.
>
> Additionally, because of the strict layering it's not always possible
> to hand up a meaningful error status from the lower layers to the
> higher layers, it gets lost in the middle just because it didn't fit
> into the layers model of the world.  It can also mean that it's not
> possible to use the intelligent features of a smart SCSI controller
> that can do complex error recovery on its own since most layers end up
> exposing only the "least common denominator".

I may be wrong, but this description seems to me more like an example for
bad design and implementation rather than for a bad general idea.

> In the linux kernel I think that one of the most important things I've
> learned from it: middle layers are usually wrong.  Instead of hiding a
> device driver behind a middle layer, expose the low level device
> driver, but give it a library of common functions to build upon.  That
> way the driver is in control all the time and can use all the neat
> features of the hardware if it wants to, but for all the common tasks
> that have to be done, hand them over to the library.

By principle, the "least common denominator" type container layers are
bad, because of not being extendable; you are completely right here. A
class-like driver object model seems better to me. And the class-like
model is not the only one that is nicely extendable. You seem to be
knowledgeable on the topic - what driver object model would you suggest
for a driver layer model?


Grigor

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> 
> On Tue, 24 Feb 2004, Mike Fedyk wrote:
>>Not true.  What you are asking for is userspace protection to kernel
>>modules.  You won't get that unless you use a micro-kernel approach, or
>>run different parts of the kernel on different (to be i386 arch
>>specific) ring in the processor.  Once you get there, you have to deal
>>with the various processor errata since not many OSes use rings besides
>>0 and 3 (maybe ring 1?).
> 
> 
> These are two possible approaches. Still another is to have the lowest
> layer export functions for memory handling - thus only the lowest layer
> will have to run in ring 0 (almost all arch that support Linux have a
> corresponding ability), and will handle the protection requests from the
> upper layers... Other approaches exist, too. A discussion may help to
> clarify which is the best.
> 

And you get an effective "context switch" even if you're not crossing 
process boundaries.  (it could be argued that different layers on 
seperate rings are effectively now a "process"...)

> 
>>>User nesting: The traditional Unix user management model has two levels:
>>>superuser (root) and subusers (ordinary users). Subusers cannot create
>>>and administrate their subusers, install system-level resources, etc.
>>>Running, however, a subuser in their own virtual machine and Personality
>>>layer as its root, will allow tree-like management of users and resources
>>>usage/access. (Imagine a much enhanced chroot.)
>>
>>That is differing security models, and it's being worked on with (I
>>forget the term) the security module framework.
> 
> 
> Within a layered kernel scheme, this tree-like model is very natural and
> simple: all protection is provided by the standard kernel mechanisms. Of
> course, it maybe can be improved; that is what the discussion is for.
> 
> 
>>>Platforming: It is much easier to write only a Personality layer than an
>>>entire kernel, esp. if you have a layer interface open standard as a
>>>base. Respectively, it's easier to write only a Resources layer, adding a
>>>new hardware to the "Supported by Linux" list. This will help increasing
>>>supported both hardware and platforms. Also, thus you may run any
>>>platform on any hardware, or many platforms concurrently on the same
>>>hardware.
>>
>>There is arch specific, and generic setions of the kernel source tree
>>already.  How do you want to improve upon that?
> 
> 
> Currently, Linux supports (actually, is) only one, Unix-descended
> platform. With a layered model, an emulator, eg. Wine, could be easily
> rewritten as a Personality layer, and this would turn it instantly into
> a free Windows. A modification of the Linux sofware and tools could
> produce a free Solaris. Some people may like a free OS/2, QNX, VxWorks
> etc. Other platforms will became easier to create and test, thus helping
> the free software evolution. On most architectures, you will be able to
> emulate another processor right in the kernel, either directly, or by a
> code emulator: all other will go then much easier. Much more advantages
> exist...
> 

One way or another, you'd have to have a "personality".  With Linux 
there is one in the kernel, and possibly many in userspace.  You won't 
find many here that will agree it should be any other way.

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Wed, 25 Feb 2004, Mike Fedyk wrote:

> Grigor Gatchev wrote:
> >
> > On Tue, 24 Feb 2004, Mike Fedyk wrote:
> >>Not true.  What you are asking for is userspace protection to kernel
> >>modules.  You won't get that unless you use a micro-kernel approach, or
> >>run different parts of the kernel on different (to be i386 arch
> >>specific) ring in the processor.  Once you get there, you have to deal
> >>with the various processor errata since not many OSes use rings besides
> >>0 and 3 (maybe ring 1?).
> >
> >
> > These are two possible approaches. Still another is to have the lowest
> > layer export functions for memory handling - thus only the lowest layer
> > will have to run in ring 0 (almost all arch that support Linux have a
> > corresponding ability), and will handle the protection requests from the
> > upper layers... Other approaches exist, too. A discussion may help to
> > clarify which is the best.
> >
>
> And you get an effective "context switch" even if you're not crossing
> process boundaries.  (it could be argued that different layers on
> seperate rings are effectively now a "process"...)

Yes. However, you won't have to do this switch often. Request for
allocating a protected memory, or deallocating it, usually happens once
when you run a process, and once when you close it. Even if a poorly
written program requests byte-by-byte additional memory, grouping these
requests is rather trivial for a memory manager. Memory protection
violations are also rare in the reality, so one can afford the load.

In addition, this scheme solves one more problem: the fixed two-level
memory management - "kernelspace and userspace". Like the "root and users"
notion, it is good to some extent, but limits the system. The layered
kernel memory management scheme would have to allow tree-like memory
management, as a part of the tree-like resources management, thus allowing
both more flexibility and more control at the same time.

>
> > Currently, Linux supports (actually, is) only one, Unix-descended
> > platform. With a layered model, an emulator, eg. Wine, could be easily
> > rewritten as a Personality layer, and this would turn it instantly into
> > a free Windows. A modification of the Linux sofware and tools could
> > produce a free Solaris. Some people may like a free OS/2, QNX, VxWorks
> > etc. Other platforms will became easier to create and test, thus helping
> > the free software evolution. On most architectures, you will be able to
> > emulate another processor right in the kernel, either directly, or by a
> > code emulator: all other will go then much easier. Much more advantages
> > exist...
> >
>
> One way or another, you'd have to have a "personality".  With Linux
> there is one in the kernel, and possibly many in userspace.  You won't
> find many here that will agree it should be any other way.

Yes. But if you have one hardcoded in the kernel, you run it every time,
even if you don't need it. Then, you run some other personality on top of
it, and possibly more libraries and programs to support and compensate
for the difference. All this is a platform burden. If you can use a more
lightweight approach, this will both increase productivity and simplify
things. Not speaking about all other advantages (see the original post).


Grigor

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> 
> On Wed, 25 Feb 2004, Mike Fedyk wrote:
> 
> 
>>Grigor Gatchev wrote:
>>
>>>On Tue, 24 Feb 2004, Mike Fedyk wrote:
>>>
>>>>Not true.  What you are asking for is userspace protection to kernel
>>>>modules.  You won't get that unless you use a micro-kernel approach, or
>>>>run different parts of the kernel on different (to be i386 arch
>>>>specific) ring in the processor.  Once you get there, you have to deal
>>>>with the various processor errata since not many OSes use rings besides
>>>>0 and 3 (maybe ring 1?).
>>>
>>>
>>>These are two possible approaches. Still another is to have the lowest
>>>layer export functions for memory handling - thus only the lowest layer
>>>will have to run in ring 0 (almost all arch that support Linux have a
>>>corresponding ability), and will handle the protection requests from the
>>>upper layers... Other approaches exist, too. A discussion may help to
>>>clarify which is the best.
>>>
>>
>>And you get an effective "context switch" even if you're not crossing
>>process boundaries.  (it could be argued that different layers on
>>seperate rings are effectively now a "process"...)
> 
> 
> Yes. However, you won't have to do this switch often. Request for
> allocating a protected memory, or deallocating it, usually happens once
> when you run a process, and once when you close it. Even if a poorly
> written program requests byte-by-byte additional memory, grouping these
> requests is rather trivial for a memory manager. Memory protection
> violations are also rare in the reality, so one can afford the load.
> 
> In addition, this scheme solves one more problem: the fixed two-level
> memory management - "kernelspace and userspace". Like the "root and users"
> notion, it is good to some extent, but limits the system. The layered
> kernel memory management scheme would have to allow tree-like memory
> management, as a part of the tree-like resources management, thus allowing
> both more flexibility and more control at the same time.
> 
> 

That is a micro-kernel.  While there is a possibility micro-kernel based 
systems can be as efficient as monolithic, it is harder, and walking in 
the direction of "we can take the load" won't get you there.

>>>Currently, Linux supports (actually, is) only one, Unix-descended
>>>platform. With a layered model, an emulator, eg. Wine, could be easily
>>>rewritten as a Personality layer, and this would turn it instantly into
>>>a free Windows. A modification of the Linux sofware and tools could
>>>produce a free Solaris. Some people may like a free OS/2, QNX, VxWorks
>>>etc. Other platforms will became easier to create and test, thus helping
>>>the free software evolution. On most architectures, you will be able to
>>>emulate another processor right in the kernel, either directly, or by a
>>>code emulator: all other will go then much easier. Much more advantages
>>>exist...
>>>
>>
>>One way or another, you'd have to have a "personality".  With Linux
>>there is one in the kernel, and possibly many in userspace.  You won't
>>find many here that will agree it should be any other way.
> 
> 
> Yes. But if you have one hardcoded in the kernel, you run it every time,
> even if you don't need it. Then, you run some other personality on top of
> it, and possibly more libraries and programs to support and compensate
> for the difference. All this is a platform burden. If you can use a more
> lightweight approach, this will both increase productivity and simplify
> things. Not speaking about all other advantages (see the original post).

That is why you have the source to most of the user space programs you 
run, right?

Running windows, or anything in Linux with a different personality won't 
  give you the same as the native platform.  There *will* be differences 
that programs depend upon.  Moving that into the kernel will *not* help 
you in this area.

WINE or not, that is why ports of apps to Linux is encouraged more than 
getting Wine to work bug for bug like windows.

I can see little purpose in this thread, since little will come out of 
it unless you are willing to start a project yourself, contribute code, 
and eventually recruit a community to work on it.

Re: A Layered Kernel: Proposal

[Timothy Miller]

I think TOE (TCP/IP stack on the ethernet card) might be one of those 
things which doesn't fit cleanly into the layered model.

Re: A Layered Kernel: Proposal

[Rik van Riel]

On Wed, 25 Feb 2004, Timothy Miller wrote:

> I think TOE (TCP/IP stack on the ethernet card) might be one of those 
> things which doesn't fit cleanly into the layered model.

That's not a big problem though, as long as the Linux network
stack keeps outperforming TOE adapters ;)

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: A Layered Kernel: Proposal

[jw schultz]

On Wed, Feb 25, 2004 at 09:46:59PM +0200, Grigor Gatchev wrote:
> 
> 
> On 25 Feb 2004, Christer Weinigel wrote:
> 
> > Just because there's an academic paper written about something doesn't
> > mean that its right.  For once Richard is partially right, unneccesary
> > layering can really ruin a system.  Grigor said that in 25 years he
> > has seen few cases of pretty code performing badly, but look at the
> > failure of SysV streams, it's a really pretty layering model, but in
> > practice it turns out to be too slow for most anything useful.
> >
> > It's not too uncommon with drivers that breaks just because the actual
> > hardware won't fit into the model that is exposed via a layer.  For
> > example, look at the error recovery of the old Linux SCSI code: it's
> > hard to do proper error recovery, and it is much slower than it needs
> > to because first the low level driver tries to do error recovery and
> > later on the higher layers try to do error recovery too.  Multiply a
> > couple of retries in the SCSI middle layer with another couple of
> > retries after a timeout a few seconds at the SCSI controller layer and
> > you have a model where it takes a minute to do figure out that
> > something is wrong, for something that ought to take just a few
> > seconds.
> >
> > Additionally, because of the strict layering it's not always possible
> > to hand up a meaningful error status from the lower layers to the
> > higher layers, it gets lost in the middle just because it didn't fit
> > into the layers model of the world.  It can also mean that it's not
> > possible to use the intelligent features of a smart SCSI controller
> > that can do complex error recovery on its own since most layers end up
> > exposing only the "least common denominator".
> 
> I may be wrong, but this description seems to me more like an example for
> bad design and implementation rather than for a bad general idea.

It may be both.  I don't think the resistance is to layering
as a general idea.  The resistance is to rigidly (read
explicitly) defined layers.

The 7 (if my memory serves) layer ISO networking definition is
perhaps a better example.  I can't recall hearing of any
implementation with decent performance that conforms to the
ISO definition of the layer boundaries.

What seems a good boundary at one time will likely prove a
poor one later.  Or what may be good in the general can slow
down the whole system because of one specific subsection
where it is suboptimal.

The best is to keep layering in mind (which is already the
case) but to remain flexible, functional specific and
mutable. 


-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Wed, 25 Feb 2004, Timothy Miller wrote:

>
> I think TOE (TCP/IP stack on the ethernet card) might be one of those
> things which doesn't fit cleanly into the layered model.

Yes. More such things exist. That is why it is hard to design a good
layered model...

And I keep thinking that the right place of a TCP/IP stack is not inside
the NIC. If God designed the man this way, where he would put our brains?
;-)

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Wed, 25 Feb 2004, Mike Fedyk wrote:

> > Yes. However, you won't have to do this switch often. Request for
> > allocating a protected memory, or deallocating it, usually happens once
> > when you run a process, and once when you close it. Even if a poorly
> > written program requests byte-by-byte additional memory, grouping these
> > requests is rather trivial for a memory manager. Memory protection
> > violations are also rare in the reality, so one can afford the load.
> >
> > In addition, this scheme solves one more problem: the fixed two-level
> > memory management - "kernelspace and userspace". Like the "root and users"
> > notion, it is good to some extent, but limits the system. The layered
> > kernel memory management scheme would have to allow tree-like memory
> > management, as a part of the tree-like resources management, thus allowing
> > both more flexibility and more control at the same time.
>
> That is a micro-kernel.  While there is a possibility micro-kernel based
> systems can be as efficient as monolithic, it is harder, and walking in
> the direction of "we can take the load" won't get you there.

I just wrote a message about why it is not microkernel, and were is the
difference. And walking in the direction "while it is possible, it is
hard" will take us nowhere. Imagine Linux Torwalds thinking this way
before starting to write Linux...

> >>One way or another, you'd have to have a "personality".  With Linux
> >>there is one in the kernel, and possibly many in userspace.  You won't
> >>find many here that will agree it should be any other way.
> >
> >
> > Yes. But if you have one hardcoded in the kernel, you run it every time,
> > even if you don't need it. Then, you run some other personality on top of
> > it, and possibly more libraries and programs to support and compensate
> > for the difference. All this is a platform burden. If you can use a more
> > lightweight approach, this will both increase productivity and simplify
> > things. Not speaking about all other advantages (see the original post).
>
> That is why you have the source to most of the user space programs you
> run, right?
>
> Running windows, or anything in Linux with a different personality won't
>   give you the same as the native platform.  There *will* be differences
> that programs depend upon.  Moving that into the kernel will *not* help
> you in this area.

It will. As pointed out above, it will save me the need to roll on an
excess personality and possibly more programs. This will simplify the
system, will decrease the resources needed , and will increase the
productivity.

> WINE or not, that is why ports of apps to Linux is encouraged more than
> getting Wine to work bug for bug like windows.

I agree that Windows could do better, for all resources drained into it.
However, the amout of Windows software that will have to be ported to
Linux, as a work, will be magnitudes over the work needed to implement not
only a full layering model, with a complete support for all Windows
versions that exist and will ever exist, but also a good dozen other
platforms.

And while porting applications may be problem of their vendors, making
Linux kernel better is our problem. I believe that this is what the
discussion is about.

> I can see little purpose in this thread, since little will come out of
> it unless you are willing to start a project yourself, contribute code,
> and eventually recruit a community to work on it.

I don't see the need for starting a project.

First, if unsuccssful, no reason to start it. And if successful, it will
fork the kernel development, with all negative implications following.
I see no sense in doing what eventually will damage the kernel
development, instead of improving it.

Second, the development of the kernel is already going this way,
regardless of our discussion. This is its logic. You can see no use of the
discussion, but you cannot see no use in following the kernel development
logic.

What I offer is merely to see where the road that we tread now goes, and
can't we avoid some of the sideswings and the muddy parts.


Grigor

Re: A Layered Kernel: Proposal

[Jens Axboe]

On Thu, Feb 26 2004, Grigor Gatchev wrote:
> I don't see the need for starting a project.
> 
> First, if unsuccssful, no reason to start it. And if successful, it will
> fork the kernel development, with all negative implications following.
> I see no sense in doing what eventually will damage the kernel
> development, instead of improving it.
> 
> Second, the development of the kernel is already going this way,
> regardless of our discussion. This is its logic. You can see no use of the
> discussion, but you cannot see no use in following the kernel development
> logic.
> 
> What I offer is merely to see where the road that we tread now goes, and
> can't we avoid some of the sideswings and the muddy parts.

I love people saying 'we' even though they never contributed a single
line of code to the project! Thanks a lot for your offer, I think I'll
have to turn it down and get my insights elsewhere.

There are plenty other places to troll.

-- 
Jens Axboe

Re: A Layered Kernel: Proposal

[Jesse Pollard]

On Wednesday 25 February 2004 18:55, Rik van Riel wrote:
> On Wed, 25 Feb 2004, Timothy Miller wrote:
> > I think TOE (TCP/IP stack on the ethernet card) might be one of those
> > things which doesn't fit cleanly into the layered model.
>
> That's not a big problem though, as long as the Linux network
> stack keeps outperforming TOE adapters ;)

Until you add IPSEC...

Unless the TOE has the same security support (encrypt some packets, not
others, require verification from some networks, not others,...), and
flexibility that the Linux network stack has, and ...

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Thu, 26 Feb 2004, Jens Axboe wrote:

> > What I offer is merely to see where the road that we tread now goes, and
> > can't we avoid some of the sideswings and the muddy parts.
>
> I love people saying 'we' even though they never contributed a single
> line of code to the project! Thanks a lot for your offer, I think I'll
> have to turn it down and get my insights elsewhere.

Developers and users are tied together by the software, Jens. By saving
you, The Developer, parts of the useless wandering, I save them to myself,
the user. Hence "we".

And if it turns out that the model proposed is good, this may be a larger
contribution to the project than, say, a couple of lines of code.

>
> There are plenty other places to troll.
>
> --
> Jens Axboe
>

Re: A Layered Kernel: Proposal

[Rik van Riel]

On Thu, 26 Feb 2004, Jesse Pollard wrote:

> Until you add IPSEC...
> 
> Unless the TOE has the same security support (encrypt some packets, not
> others, require verification from some networks, not others,...), and
> flexibility that the Linux network stack has, and ...

Exactly.  I just don't see TOE as a viable option for
networking, so I'm not too worried about not supporting
it.

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: A Layered Kernel: Proposal

[Christoph Hellwig]

On Thu, Feb 26, 2004 at 06:37:46PM +0200, Grigor Gatchev wrote:
> Developers and users are tied together by the software, Jens. By saving
> you, The Developer, parts of the useless wandering, I save them to myself,
> the user. Hence "we".
> 
> And if it turns out that the model proposed is good, this may be a larger
> contribution to the project than, say, a couple of lines of code.

Huh?  I fail how writing up a tiny essasy without the slightest
understanding of what you're talking about should help us at all.

Really, fixing up a few drivers would be a much greater help than this
blah blah.  Or in short (to quote Linus):  "talk is cheap, show me the
code"

back to work now..

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> I don't see the need for starting a project.
> 
> First, if unsuccssful, no reason to start it. And if successful, it will
> fork the kernel development, with all negative implications following.
> I see no sense in doing what eventually will damage the kernel
> development, instead of improving it.

If you start a project, that doesn't mean the "fork" is bad as long as 
the intention is to integrate the work back into the base.

What you are asking for is for people to add to their list of things to 
code.  You should be adding code yourself.

> Second, the development of the kernel is already going this way,
> regardless of our discussion. This is its logic. You can see no use of the
> discussion, but you cannot see no use in following the kernel development
> logic.

Linux has many groups of people pushing and pulling it in numerous 
directions.  Very rarely does a direction succeed if the people who want 
that specific direction don't submit code.

Useful discussion would be asking for implementation suggestions to get 
to your goal.  Oh wait, I think there are already some of those in this 
thread.

Mike

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Thu, 26 Feb 2004, Rik van Riel wrote:

> On Thu, 26 Feb 2004, Jesse Pollard wrote:
>
> > Until you add IPSEC...
> >
> > Unless the TOE has the same security support (encrypt some packets, not
> > others, require verification from some networks, not others,...), and
> > flexibility that the Linux network stack has, and ...
>
> Exactly.  I just don't see TOE as a viable option for
> networking, so I'm not too worried about not supporting
> it.

It depends. Some of these integrated gadgets aren't very successful;
others, however, are. Compare true modems to winmodems, or modern
videocards with built-in rendering etc to bare ones. Also, on embedded
systems with very tight memory and speed requirements, a TOE card may be a
bad, but the only available solution.

So, IMO, a proposed kernel model must have the means to support similar
devices. Some will be bad, but some may be good.

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Thu, 26 Feb 2004, Mike Fedyk wrote:

> Grigor Gatchev wrote:
> > I don't see the need for starting a project.
> >
> > First, if unsuccssful, no reason to start it. And if successful, it will
> > fork the kernel development, with all negative implications following.
> > I see no sense in doing what eventually will damage the kernel
> > development, instead of improving it.
>
> If you start a project, that doesn't mean the "fork" is bad as long as
> the intention is to integrate the work back into the base.

Typically, yes. But what I am trying to discuss is a kernel model
improvement. Such a project, when taken to the point where it works well,
will be very hard, if possible at all, to integrate into the base. If it
wasn't so,I would be the happiest man around, being able to test all
doubts in practice, without meddling in other people's work.

> What you are asking for is for people to add to their list of things to
> code.  You should be adding code yourself.

Not true. I would be doing that if I was thoroughly convinced that the
layered model is good, and that it is exactly the kernel model needed.

Currenly, it seems to me a good idea. That is why, after some months of
gnawing at it, I dared to post here. However, I have also seen a lot of
"great" ideas that are actually bad - and am afraid that this may turn one
of these. My judgement is not subscribed for the eternal truth, after all.

Currently we talk not already coding, but still designing. And what I am
asking for is people to add to _my_ list to work on. If they would like to
contribute some design work, that will be nice, but a simple "It is weak
here, see to improve it" will be already excellent help.

> Linux has many groups of people pushing and pulling it in numerous
> directions.  Very rarely does a direction succeed if the people who want
> that specific direction don't submit code.
>
> Useful discussion would be asking for implementation suggestions to get
> to your goal.  Oh wait, I think there are already some of those in this
> thread.

Wait, wait a bit :-) I am still trying to see if that attractively looking
model is really good. After (rather, _if_) it is proven good, I would be
asking for implementation suggestions. But let's see first if it is worth
implementing.

As for directions and adding code: Nobody ever, AFAIK, has intentionally
pushed the kernel towards this layered model. And the kernel source is
already structured in a way convenient to go with it, and for the last
three years was going exactly in this direction! That is why it seems
to me that this is the internal logic of the kernel development.


Grigor

Re: A Layered Kernel: Proposal

[Tim Hockin]

On Fri, Feb 27, 2004 at 01:18:12PM +0200, Grigor Gatchev wrote:
> As for directions and adding code: Nobody ever, AFAIK, has intentionally
> pushed the kernel towards this layered model. And the kernel source is
> already structured in a way convenient to go with it, and for the last
> three years was going exactly in this direction! That is why it seems
> to me that this is the internal logic of the kernel development.

See STREAMS and how well it worked.

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> 
> On Thu, 26 Feb 2004, Mike Fedyk wrote:
>>Useful discussion would be asking for implementation suggestions to get
>>to your goal.  Oh wait, I think there are already some of those in this
>>thread.
> 
> 
> Wait, wait a bit :-) I am still trying to see if that attractively looking
> model is really good. After (rather, _if_) it is proven good, I would be
> asking for implementation suggestions. But let's see first if it is worth
> implementing.

OK, you need to state that in simple terms at the very begining of your 
proposal in the future.  Otherwise many people won't understand you're 
asking for design help, and are just asking others to do what you want.

Also, fill in more details.  Take all of the ideas against your proposal 
in this thread, and write how they can be overcome.  You have to give 
enough detail so it will not be seen as a dismissal of said problem, and 
enough flexability for a design document.

Frankly, it might be better if you wrote an RFC with implementation details.

HTH,

Mike

Re: A Layered Kernel: Proposal

[Richard B. Johnson]

On Fri, 27 Feb 2004, Tim Hockin wrote:

> On Fri, Feb 27, 2004 at 01:18:12PM +0200, Grigor Gatchev wrote:
> > As for directions and adding code: Nobody ever, AFAIK, has intentionally
> > pushed the kernel towards this layered model. And the kernel source is
> > already structured in a way convenient to go with it, and for the last
> > three years was going exactly in this direction! That is why it seems
> > to me that this is the internal logic of the kernel development.
>
> See STREAMS and how well it worked.

This has already been wacked around quite a bit, but the fact remains
that every so-often, some college student (who never worked a day
in her life) or her instructor (who never worked a day in his life)
publish some hair-brained idea that a lot of folks believe must
have some merit because it came from MIT or Berkeley, etc.  Anybody
who's in the IEEE Computer Society can get monthly unworkable or
unusable dissertations from the college community about new ways
to do things. Once every 10 or so years, one of these writings
ends up having some merit. The "layered" model is way too old.
You want to use the new gene-splicing techiques for software
development. Basically, you build a filter that completely
defines the end product required. Then you set the monkeys loose...

Cheers,
Dick Johnson
Penguin : Linux version 2.4.24 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: A Layered Kernel: Proposal

[Rik van Riel]

On Fri, 27 Feb 2004, Grigor Gatchev wrote:

> Currently we talk not already coding, but still designing. And what I am
> asking for is people to add to _my_ list to work on. If they would like to
> contribute some design work, that will be nice, but a simple "It is weak
> here, see to improve it" will be already excellent help.

The kernel janitors project could be a good starting point.

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: A Layered Kernel: Proposal

[Christer Weinigel]

Grigor Gatchev <grigor@zadnik.org> writes:

> > In the linux kernel I think that one of the most important things I've
> > learned from it: middle layers are usually wrong.  Instead of hiding a
> > device driver behind a middle layer, expose the low level device
> > driver, but give it a library of common functions to build upon.  That
> > way the driver is in control all the time and can use all the neat
> > features of the hardware if it wants to, but for all the common tasks
> > that have to be done, hand them over to the library.
> 
> By principle, the "least common denominator" type container layers are
> bad, because of not being extendable; you are completely right here. A
> class-like driver object model seems better to me. And the class-like
> model is not the only one that is nicely extendable. 

> You seem to be knowledgeable on the topic - what driver object model
> would you suggest for a driver layer model?

Thanks for the confidence, bur I really don't know, it's much easier
to criticize someone elses design than to come up with a good one
myself. :-)

With that said, I think that they way the Linux kernel is moving
regarding to IDE/SCSI devices is a good idea.  Linux has been around
for a while now and the Linux people have tried lots of things that
turned out not to be such a good idea after all.  Many things are
still there in the kernel, but if it's important enough, it gets
cleaned up after a while.

  /Christer

-- 
"Just how much can I get away with and still go to heaven?"

Freelance consultant specializing in device driver programming for Linux 
Christer Weinigel <christer@weinigel.se>  http://www.weinigel.se

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On 29 Feb 2004, Christer Weinigel wrote:

> Grigor Gatchev <grigor@zadnik.org> writes:
>
> > > In the linux kernel I think that one of the most important things I've
> > > learned from it: middle layers are usually wrong.  Instead of hiding a
> > > device driver behind a middle layer, expose the low level device
> > > driver, but give it a library of common functions to build upon.  That
> > > way the driver is in control all the time and can use all the neat
> > > features of the hardware if it wants to, but for all the common tasks
> > > that have to be done, hand them over to the library.
> >
> > By principle, the "least common denominator" type container layers are
> > bad, because of not being extendable; you are completely right here. A
> > class-like driver object model seems better to me. And the class-like
> > model is not the only one that is nicely extendable.
>
> > You seem to be knowledgeable on the topic - what driver object model
> > would you suggest for a driver layer model?
>
> Thanks for the confidence, bur I really don't know, it's much easier
> to criticize someone elses design than to come up with a good one
> myself. :-)

Okay. I will try (hope I'll have the time for all!) to outline the major
driver layer models, with simple lists of advantages and disadvantages,
and to present it as a base for further discussion. (Please keep in mind
that this outline will certainly be not the best ever to exist - maybe a
lot of people around will be able to make it much better. But, anyway,
they will be given the full opportunity to criticize and improve. :-)

> With that said, I think that they way the Linux kernel is moving
> regarding to IDE/SCSI devices is a good idea.  Linux has been around
> for a while now and the Linux people have tried lots of things that
> turned out not to be such a good idea after all.  Many things are
> still there in the kernel, but if it's important enough, it gets
> cleaned up after a while.

If you mean the abandoning of the SCSI emulation, I couldn't agree more.
Though I haven't digged into the code of this driver group, the move seems
only logical from design viewpoint.

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> Okay. I will try (hope I'll have the time for all!) to outline the major
> driver layer models, with simple lists of advantages and disadvantages,
> and to present it as a base for further discussion. (Please keep in mind
> that this outline will certainly be not the best ever to exist - maybe a
> lot of people around will be able to make it much better. But, anyway,
> they will be given the full opportunity to criticize and improve. :-)

I'll be looking forward to that.  It should be an interesting read.

Mike

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

Here it is. Get your axe ready! :-)

---

Driver Model Types: A Short Description.

(Note:  This is NOT a complete description of a layer,
according to the kernel layered model I dared to offer.  It
concerns only the hardware drivers in a kernel.)


Direct binding models:

In these models, kernel layers that use drivers bind to
their functions more or less directly.  (The degree of
directness and the specific methods depend much on the
specific implementation.)  This is as opposed to the
indirect binding models, where driver is expected to provide
first a description what it can do, and binding is done
after that, depending on the description provided.


Chaotic Model

This is not a specific model, but rather a lack of any model
that is designed in advance.  Self-made OS most often start
with it, and add a model on a later stage, when more drivers
appear.

Advantages:

The model itself requires no design efforts at all.

No fixed sets of functions to conform to.  Every coder is
free to implement whatever they like.

Unlimited upgradeability - a new super-hardware driver is
not bound by a lower common denominator.

Gives theoretically the best performance possible, as no
driver is bound to conform to anything but to the specific
hadrware abilities.

Disadvantages:

Upper layers can rely on nothing with it.  As more than one
driver for similar devices (eg.  sound cards) adds, upper
layers must check the present drivers for every single
function - which is actually implementing an in-built driver
model.  (Where its place is not, and therefore in a rather
clumsy way.)

Summary:

Good for homebrewn OS alikes, and for specific hardware that
is not subject to differencies, eg.  some mainframe that may
have only one type of NIC, VDC etc.  Otherwise, practically
unusable - the lack of driver systematics severely limits
the kernel internal flexibility.  Often upgraded with
functions that identify for each driver what it is capable
of, or requiring some (typically low) common denominator.


Common Denominator Model

With it, hardware drivers are separated in groups - eg.  NIC
drivers, sound drivers, IDE drivers.  Within a group, all
drivers export the same set of functions.

This set sometimes covers only the minimal set of
functionalities, shared by all hardware in the group - in
this case it acts as a smallest common denominator.  Other
possibility is a largest common denominator - to include
functions for all functionalities possible for the group,
and if the specific hardware doesn't support them directly,
to either emulate them, or to signal for an invalid
function.  Intermediate denominator levels are possible,
too.

The larger the common denominator, and the less emulation
("bad function" signal instead), the closer the model goes
to the chaotic model.

Advantages:

It requires little model design (esp.  the smallest common
denominator types), and as little driver design as possible.
(You may create an excellent design, of course, but you are
not required to.)  You can often re-use most of the design
of the other drivers in the group.

It practically doesn't require a plan, or coordination.  The
coder just tries either to give the functionality that is
logical (if this is the first driver in a new group), or
tries to give the same functionality that the other drivers
in the group give.

Coupling the driver to the upper levels that use it is very
simple and easy.  You practically don't need to check what
driver actually is down there.  You know what it can offer,
no matter the hardware, and don't need to check what the
denominator level ac ually is, unlike the chaotic model.

It encapsulates well the hardware groups, and fixes them to
a certain level of development.  This decreases the
frequency of the knowledge refresh for the programmers, and
to some extent the need for upper levels rewrite.

Disadvantages:

The common denominator denies to the upper level the exact
access to underlaying hardware functionality, and thus
decreases the performance.  With hardware that is below the
denominator line, you risk getting a lot of emulation, which
you potentially could avoid to a large degree on the upper
level (it is often better informed what exactly is desired).
With hardware above the denominator line, you may be denied
access to built-in, hardware-accelerated higher level
functions, that would increase performance and save you
doing everything in your code.

Once the denominator level is fixed, it is hard to move
without seriously impairing the backwards compatibility.
The hardware, however, advances, and offers built-in
upper-level functions and new abilities.  Thus, this model
quickly obsoletes its denominator levels (read:
performance and usability).

The larger the common denominator, the more design work the
model requires.  (And the quicker it obsoletes, given the
need to keep with the front.)

Summary:

This model is the opposite of the chaotic model.  It is
canned and predictable, but non-flexible and with generally
bad performance.  Model upgrades are often needed (and done
more rarely, at the expense of losing efficiency), and often
carry major rewrites of other code with them.


Discussion:

These two models are the opposites of the scale.  They are
rarely, if ever, used in clear form.  Most often, a driver
model will combine them to some extent, falling somewhere in
the middle.

The simplest combination is defining a (typically low)
common denominator, and going chaotic above.  While it
theoretically provides both full access to the hardware
abilities and something granted to base on, the granted is
little, and the full access is determinable like with the
chaotic model, in a complex way.

This combination also has some advantages:

Where more flexibility and performance is needed, you may go
closer to the chaotic model.  And where more replaceability
and predictability is needed, you may go closer to the CD
model.  The result will be a driver model that gives more
assets where they are really needed, and also has more
negatives, but in an area where they aren't that important.

If the optimum for a specific element, eg.  driver group,
shifts, you may always make the shift obvious.  Then, moving
the model balance for this element will be more readily
accepted by all affected by it.

Another way to combine the models is to break the big
denominator levels into multiple sublevels, and to provide a
way to describe the driver's sublevel, turning this model
into indirect binding type.

All this group of models, however, has a big drawback:
really good replaceability is provided only very close to
the common denominator end of the scale, where flexibiility,
performance, upgradeability and usability already tend to
suffer.  Skillful tuning may postpone the negatives to a
degree, but not forever.  Attempts to solve this problem are
made by developing driver models with indirect binding.


Indirect binding models:

With this model, drivers are expected to provide first a
description what they can do, and what they cannot.  Then,
the code that uses the driver binds to it, using the
description.

Most of these models take the many assets of the chaotic
model as a base, and try to add the good replaceability and
function set predictability of the common denominator model.


Class-like model

In it, the sets of functions that drivers offer are
organized in a class-like manner.  Every class has a defined
set of functions.  Classes create a hierarchy, like the
classes of OOP languages.  (Drivers do not necessarily have
to be written in an OO language, or to be accessed only
from such one.)  A class typically implements all functions
found in its predecessor, and adds more (but, unlike OOP
classes, rarely reuses predecessor code).

Classes and their sets of functions are pre-defined, but the
overall model is extendable without changing what is
present.  When a new type of device appears, or a new device
offers functionality above the current classes appropriate
for it, a new class may be defined.  The description of the
class is created, approved and registered (earlier stages
may be made by a driver writer, later - by a central body),
and is made available to the concerned.

Every driver has a mandatory set of functions that report
the driver class identification.  Using them, an upper layer
can quickly define what functionality is present.  After
this, the upper layer binds to the driver much like in the
direct binding models.

Advantages:

If properly implemented, gives practically the same
performance as the chaotic model.  Additional checking is
performed only once, when the driver is loaded.  Class
defining may be fine-grained enough to allow for practically
exact covering of the hardware functionality.

The upgradeability and usability of the specific drivers are
practically the same as those of the chaotic model.  And the
model global extendability and upgradeability, if properly
designed, are practically limitless.

If properly designed, gives nearly the same replaceability
as the CD model.  (The things to check are more, but much
less than with the chaotic model.  What you will find in
each of them is usually well documented.  And the check
procedure is standard and simple.)

Disadvantages:

The model itself requires more design and maintenance work
than the direct binding models (except the larger CD
models).  (Actually, the amount of maintenance work is the
same as with any CD model, but the work comes before the
need for it is felt by everybody.)

Discussion:

This is probably the best of all driver models I have
examined more carefully.  Unhappily, most implementations I
have seen are rather clumsy, to say the least.


Function map model

This model is actually a largest common denominator model,
extended with the ability to provide a map of the
implemented functions.  In the simplest case, the map is a
bitspace, where every bit marks whether its function is
implemented.  In other cases, the map is a space of accesses
(eg.  function pointers).

Advantages:

In some architectures and platforms, this is a very
convenient way to describe a function array.

The model is simple, and therefore easy to use.

Disadvantages:

The model has all disadvantages of a LCD model.

Discussion:

The advantages of the model are relatively little, while the
disadvantages are big.  For this reason, it is used mostly
as an addition to another model - eg.  to the class-like
model.


Global discussion:

The models list provided here is rather global, This is
intentional:  while designing, one must clarify one level at
a time, much like with coding.

The list also is incomplete.  For example, I never had the
time to look properly for ideas into the OS/2 SOM, and it is
said to work very well, and provide excellent performance.
Of interest might be also more details of the QNX driver
model.  Someone with in-depth knowledge of these might be
able to enhance this list.

----

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> Here it is. Get your axe ready! :-)
> 
> ---
> 
> Driver Model Types: A Short Description.
> 
> (Note:  This is NOT a complete description of a layer,
> according to the kernel layered model I dared to offer.  It
> concerns only the hardware drivers in a kernel.)
> 

Looks like you're going to need to get a little deeper to keep it from 
being OT on this list.

What is the driver designs of say, solaris, OS/2, Win32 (NT & 9x trees) 
and how are they good and how are they bad?

What specific (think API changes, nothing generalized here *at all*) 
changes could benefit linux, and why and how?  Nobody will listen to 
hand waving, so you need a tight case for each change.

HTH,

Mike

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Sun, 7 Mar 2004, Mike Fedyk wrote:

> Grigor Gatchev wrote:
> > Here it is. Get your axe ready! :-)
> >
> > ---
> >
> > Driver Model Types: A Short Description.
> >
> > (Note:  This is NOT a complete description of a layer,
> > according to the kernel layered model I dared to offer.  It
> > concerns only the hardware drivers in a kernel.)
> >
>
> Looks like you're going to need to get a little deeper to keep it from
> being OT on this list.
>
> What is the driver designs of say, solaris, OS/2, Win32 (NT & 9x trees)
> and how are they good and how are they bad?
>
> What specific (think API changes, nothing generalized here *at all*)
> changes could benefit linux, and why and how?  Nobody will listen to
> hand waving, so you need a tight case for each change.
>
> HTH,
>
> Mike

Dear Mike,

An year ago, I was teaching a course on UNIX security. After the
first hour, a student - military man with experience of commanding PC-DOS
users - interrupted me: "What is all that mumbo-jumbo about? Users,
groups, permissions - all this is empty words, noise! Don't you at least
classify your terminal, and issue orders on who uses it? Man, either talk
some real stuff, or I am not wasting anymore my time on you!"

Of course, I was happy to let him "stop wasting his time on me".

Reading some of the posts here, I get this deja vu. I know the driver
designs of some OS, and don't know others. I may waste a month or two of
work, and post a huge description of all big OS driver models that I
know, or waste an year of work, and give you a description of all big OS
driver models. Will this give you anything more than what was already
posted? Wouldn't you read my hundreds of pages, then try to summarise all,
and eventually come to the same?

Or you will try to pick this from one model, that from another, and end up
assembling a creature with eagle wings, dinosaur teeth, anthelope legs and
shark fins, and wondering why it can neither fly nor run nor swim really
well, why it has bad performance? This can't be, I must have misunderstood
you.

Also, does "think API changes, nothing generalised *at all*" mean anything
different from "think code, no design *at all*"? If this is some practical
joke, it is not funny. (I can't believe that a kernel programmer will not
know why design is needed, where is its place in the production of a
software, and how it should and how it should not be done.)

OK. Let's try explain it once more:

While coding, think coding. While designing, think designing. Design comes
before coding; otherwise you design while coding, and produce a mess.
Enough of such an experience, and you start believing that design without
coding is empty words, noise. Hand waving.

What I gave is more than enough to start designing a good driver model.
After the design is OKed, details of implementation, eg. API changes, may
be developed. Developing them now, however, is the wrong time, for the
reasons explained just above. Let's not put the cart ahead of the horse.

Or I am wrong?

Re: A Layered Kernel: Proposal

[Theodore Ts'o]

On Mon, Mar 08, 2004 at 02:23:43PM +0200, Grigor Gatchev wrote:
> 
> Also, does "think API changes, nothing generalised *at all*" mean anything
> different from "think code, no design *at all*"? If this is some practical
> joke, it is not funny. (I can't believe that a kernel programmer will not
> know why design is needed, where is its place in the production of a
> software, and how it should and how it should not be done.)

So give us a design.  Make a concrete proposal.  Tell us what the
API's --- with C function prototypes --- should look like, and how we
should migrate what we have to your new beautiful nirvana.

Engineering is the task of trading off various different principals;
in general it is impossible to satisfy all of them 100%.  For example,
Mach tried to be highly layered, with strict memory protections to
protect one part of the kernel from another --- all good things, in a
generic sense.  Streams tried to be extremely layered as well, and had
a design that a computer science professor would love.  Both turned
out to be spectacular failures because their performance sucked like
you wouldn't believe.

Saying "layered programming good" is useless.  Sure, we agree.  But
it's not the only consideration we have to take into account.
Furthermore, the Linux kernel has a decent amount of layering already,
although it is a pragmatist's sort of layering, where we use it when
it is useful and ignore when it gets in the way.  Given your
high-level descriptions, perhaps the best description of what we
currently have in Linux is that it uses a C-based (because no one has
ever bothered to create a C++ obfuscated contest --- it's too easy),
multiple-inheritance model, where each device driver can use
common-denominator code as necessary (from the PCI sublayer, the tty
layer, the SCSI layer, the network layer, etc.), but it is always
possible for each driver to provide specific overrides as necessary
for the hardware.

Is my description of Linux's device model accurate?  Sure.  Is it
useful in terms of telling us what we ought to do in order to improve
our architecture?  Not really.  It's just a buzzword-compliant,
high-level description which is great for getting great grades from
clueless C.S. professors that are more in love with theory than
practice.  But that's about all it's good for.

In order for it to be at all useful, it has to go to the next level.
So if you would like to tell us how we can do a better job, please
submit a proposal.  But it will have to be a detailed one, not one
that is filled with high-level buzzwords and hand-waving.

					- Ted

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Hi Grigor.

Theodore Ts'o pretty much summed it up, but let me add a couple things...

Grigor Gatchev wrote:
> 
> On Sun, 7 Mar 2004, Mike Fedyk wrote:
> 
> 
>>Grigor Gatchev wrote:
>>
>>>Here it is. Get your axe ready! :-)
>>>
>>>---
>>>
>>>Driver Model Types: A Short Description.
>>>
>>>(Note:  This is NOT a complete description of a layer,
>>>according to the kernel layered model I dared to offer.  It
>>>concerns only the hardware drivers in a kernel.)
>>>
>>
>>Looks like you're going to need to get a little deeper to keep it from
>>being OT on this list.
>>
>>What is the driver designs of say, solaris, OS/2, Win32 (NT & 9x trees)
>>and how are they good and how are they bad?
>>
>>What specific (think API changes, nothing generalized here *at all*)
>>changes could benefit linux, and why and how?  Nobody will listen to
>>hand waving, so you need a tight case for each change.
>>
>>HTH,
>>
>>Mike
> 
> 
> Dear Mike,
> 
> An year ago, I was teaching a course on UNIX security. After the
> first hour, a student - military man with experience of commanding PC-DOS
> users - interrupted me: "What is all that mumbo-jumbo about? Users,
> groups, permissions - all this is empty words, noise! Don't you at least
> classify your terminal, and issue orders on who uses it? Man, either talk
> some real stuff, or I am not wasting anymore my time on you!"
> 
> Of course, I was happy to let him "stop wasting his time on me".
> 

Yes, I can understand.  Dealing with users as a sysadmin isn't much 
different.

> Reading some of the posts here, I get this deja vu. I know the driver
> designs of some OS, and don't know others. I may waste a month or two of
> work, and post a huge description of all big OS driver models that I
> know, or waste an year of work, and give you a description of all big OS
> driver models. Will this give you anything more than what was already
> posted? Wouldn't you read my hundreds of pages, then try to summarise all,
> and eventually come to the same?

The descriptions were for my benefit, as whenever you were asked for 
specific, you were a little more specific in *design* terms, not code terms.

> Or you will try to pick this from one model, that from another, and end up
> assembling a creature with eagle wings, dinosaur teeth, anthelope legs and
> shark fins, and wondering why it can neither fly nor run nor swim really
> well, why it has bad performance? This can't be, I must have misunderstood
> you.
> 
> Also, does "think API changes, nothing generalised *at all*" mean anything
> different from "think code, no design *at all*"? If this is some practical
> joke, it is not funny. (I can't believe that a kernel programmer will not
> know why design is needed, where is its place in the production of a
> software, and how it should and how it should not be done.)
> 

No.  The designs you are talking about are *far* too generalized. 
Meaning, every proposal on this list that gets anywhere is for code 
modifications.  You need to have your *design* proposal in *code* speak. 
  Anything else will just be called hand waving.

> OK. Let's try explain it once more:
> 
> While coding, think coding. While designing, think designing. Design comes
> before coding; otherwise you design while coding, and produce a mess.
> Enough of such an experience, and you start believing that design without
> coding is empty words, noise. Hand waving.
> 
> What I gave is more than enough to start designing a good driver model.
> After the design is OKed, details of implementation, eg. API changes, may
> be developed. Developing them now, however, is the wrong time, for the
> reasons explained just above. Let's not put the cart ahead of the horse.
> 

I'm not a kernel programmer.

> Or I am wrong?

Maybe.  If you can have you design describe the current linux model as 
"in order to write to this SCSI disk I need to call foo(),..." and 
describe your new change as "if foo() called bar() I could do...".

Basically, you need to describe everything in programming terms.  A 
great example is the BIO design document from Jens Axboe.  That's an 
example of a design before code project (but I only happened to hear 
about it when 2.5.1 came out, and the code was ready to be merged...) .

Mike

Re: A Layered Kernel: Proposal

[viro]

On Mon, Mar 08, 2004 at 12:39:40PM -0500, Theodore Ts'o wrote:
 
> So give us a design.  Make a concrete proposal.  Tell us what the
> API's --- with C function prototypes --- should look like, and how we
> should migrate what we have to your new beautiful nirvana.

But... but... that requires *work*!  How can you demand that?!?

To original toss^Wposter: it's an old observation that in order to be
useful hypothesis has to be falsifiable.  Similar principle applies
to design proposals - to be worth of any attention they have to be
detailed enough to allow meaningful criticism.

What you have done so far is equivalent to coming to a hospital and
saying "aseptic good, infection bad".  That would get pretty much
the same reactions, varying from "yes, we know" to "do you have any
specific suggestions?" and "stop wasting our time"[1].

In short: get lost and do not come back until you have something less
vague.

[1]  If you are insistent enough, you might also earn a free referral
to psychiatrist.  You would have to work harder than you have done
so far, though...

Re: A Layered Kernel: Proposal

[Paul Jackson]

> While coding, think coding. While designing, think designing. Design comes
> before coding; otherwise you design while coding, and produce a mess.

You are describing, roughly, the waterfall model of software development.

Linux kernel work is closer to something resembling the prototype
and/or spiral model.

See further explanations of these terms, for instance, at:

  http://model.mercuryinteractive.com/references/models/

But, in any case, Linux kernel work _does_ have a rather extensively
articulated development model which we find is working rather well,
thank-you.  For all I know, this methodology was defined by some
traumatic event at the birth of Linus - whatever - seems to work.

When in Rome, do as the Romans.  And especially don't be surprised
at being pushed aside if you protest that we aren't behaving as the
French.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: A Layered Kernel: Proposal

[Grigor Gatchev]

On Mon, 8 Mar 2004, Theodore Ts'o wrote:

> On Mon, Mar 08, 2004 at 02:23:43PM +0200, Grigor Gatchev wrote:
> >
> > Also, does "think API changes, nothing generalised *at all*" mean anything
> > different from "think code, no design *at all*"? If this is some practical
> > joke, it is not funny. (I can't believe that a kernel programmer will not
> > know why design is needed, where is its place in the production of a
> > software, and how it should and how it should not be done.)
>
> So give us a design.  Make a concrete proposal.  Tell us what the
> API's --- with C function prototypes --- should look like, and how we
> should migrate what we have to your new beautiful nirvana.

Aside from the beautiful nirvana irony, that is what I am trying not to
do. For the following reason:

When you have to produce a large software, you first design it at a global
level. Then you design the subsystems. After that, their subsystems. And
so on, level after level. At last, you design the code itself. Only then
you write the code actually.

This is opposed to the model where you start with the code. You write a
piece, then you see it's not quite mathing the whole. You design the
group, then rewrite your code, and a dozen of other pieces to match the
design. That's nice, but on the upper level it's still not quite matching.
And so on, to the top. (Actually, a coder with some sense of design would
start as up the chain as he can - but with this design model that is never
very high. And the higher the level, the fewer go to it.)

The Linux kernel is the best example I have ever seen for the second
approach, as a result. It has good code implementation, often excellent.
On lowest level, its design is good. But the higher you go, the more mucky
the design becomes. On the topmost levels, there is only as much design as
absolutely needed by the whole not to fall apart.

This has a reason - the origin and appearance of Linux. This is the way
most fan-initiated and supported systems go. And this cannot be really
changed completely - neither it needs to be. However, a little more design
on the more global levels would be of good use, I think.

The problem is, that the current culture of kernel writing favors the
"code proof". This is also understandable and natural, given the way Linux
has developed. If you can't supply a real code to beat in performance the
current one, you will get enough only of doubters.

However, the more global a conception, the larger is the amount of coding
needed to prove it in code. For example, designing a drivers group would
need only a driver or two written, or even ported, to show its actual
assets. A complete kernel driver model would need at least a dozen of
drivers (re)written, and a lot of other code changes made. A complete
layered model of the kernel, what I dared to offer initially, would
require rewriting of at least 10% of the kernel code - that is over 200
000 lines, AFAIK, to supply a working system to prove anything. This is
very clearly over the abilities of a single programmer (or, at least,
well over mine.)

Well, kernel coders are not idiots. Don't write all the code, you say,
just show me the function prototypes, that's enough. For designing a
group of drivers, that's not that hard. For an entire driver model it may
also be well over a single programmer's abilities. (BTW, what if this
programmer doesn't know C? He is by definition a bad software designer?)

In short: that is why people sometimes talk design without talking code.
Human emotions are essentially brain chemistry, which is essentially
nuclear physics - but no sane person would try to evaluate the emotions
level by asking for examples in nuclear physics level. And any
mathematician that tries to explain Kantorian numbers in apples and pears
would be ridiculed (and must be a genius to succeed at all).

I understand well that, given the kernel history, this may look like a
hand waving for you. I have seen a building worker who sincerely believed
that architects are empty talkers who have never laid a brick over brick,
and dumping all of them would be the best thing to do. However, if you
continue being convinced in that, the kernel will remain underdesigned in
more global levels. I may be a brainless twit, troll, useless C.S.
professor, anything like - but the problem is real. I may go, but unless
properly addressed, the problem will stay.

> Engineering is the task of trading off various different principals;
> in general it is impossible to satisfy all of them 100%.  For example,
> Mach tried to be highly layered, with strict memory protections to
> protect one part of the kernel from another --- all good things, in a
> generic sense.  Streams tried to be extremely layered as well, and had
> a design that a computer science professor would love.  Both turned
> out to be spectacular failures because their performance sucked like
> you wouldn't believe.

I would believe it very well - have tested on my own PC some code from the
STREAMS project. :-) It really was overlayered, and I remember vaguely
something like that they were doing almost the same (resource-expensive)
check in _every_ possible layer to some request I tracked, maybe nearly a
dozen of times. In a sense, STREAMS was exactly the opposite of Linux -
well-designed on global level, but the more concrete the level, the worse
the design. No wonder at all its performance sucked... However, I do
believe that Linux could also have a design that a computer science
professor would love, not at the price of performance.

> Saying "layered programming good" is useless.  Sure, we agree.

Really? I see a lot of disagreement around on this.

> But it's not the only consideration we have to take into account.
> Furthermore, the Linux kernel has a decent amount of layering already,
> although it is a pragmatist's sort of layering, where we use it when
> it is useful and ignore when it gets in the way.  Given your
> high-level descriptions, perhaps the best description of what we
> currently have in Linux is that it uses a C-based (because no one has
> ever bothered to create a C++ obfuscated contest --- it's too easy),
> multiple-inheritance model, where each device driver can use
> common-denominator code as necessary (from the PCI sublayer, the tty
> layer, the SCSI layer, the network layer, etc.), but it is always
> possible for each driver to provide specific overrides as necessary
> for the hardware.
>
> Is my description of Linux's device model accurate?  Sure.  Is it
> useful in terms of telling us what we ought to do in order to improve
> our architecture?  Not really.  It's just a buzzword-compliant,
> high-level description which is great for getting great grades from
> clueless C.S. professors that are more in love with theory than
> practice.  But that's about all it's good for.

You mean that, for example, drawing house elements on paper, and tossing
some numbers here and back is useless in deciding how to build a house,
and only getting hands to the real bricks gives you whether this wall
should be here, and whether that column is thick enough to survive through
a quake?

Thanks, Ted. I think I am getting it, finally.

Unhappily, what I am getting is the clear idea that you are a team of
geniuses. Or that I am a hopeless idiot, or maybe both. In any way, I
am nowhere near you, and only waste your time now.

Sorry.

> In order for it to be at all useful, it has to go to the next level.
> So if you would like to tell us how we can do a better job, please
> submit a proposal.  But it will have to be a detailed one, not one
> that is filled with high-level buzzwords and hand-waving.
>
> 					- Ted

Re: A Layered Kernel: Proposal

[Timothy Miller]

Grigor Gatchev wrote:
> 
> On Mon, 8 Mar 2004, Theodore Ts'o wrote:
> 
> 
>>On Mon, Mar 08, 2004 at 02:23:43PM +0200, Grigor Gatchev wrote:
>>
>>>Also, does "think API changes, nothing generalised *at all*" mean anything
>>>different from "think code, no design *at all*"? If this is some practical
>>>joke, it is not funny. (I can't believe that a kernel programmer will not
>>>know why design is needed, where is its place in the production of a
>>>software, and how it should and how it should not be done.)
>>
>>So give us a design.  Make a concrete proposal.  Tell us what the
>>API's --- with C function prototypes --- should look like, and how we
>>should migrate what we have to your new beautiful nirvana.
> 
> 
> Aside from the beautiful nirvana irony, that is what I am trying not to
> do. For the following reason:
> 
> When you have to produce a large software, you first design it at a global
> level. Then you design the subsystems. After that, their subsystems. And
> so on, level after level. At last, you design the code itself. Only then
> you write the code actually.
> 
[snip]

As one of the people who has been told "show me the code" before, let me 
try to help you understand what the kernel developers are asking of you.

First of all, they are NOT asking you to do the bottom-up approach that 
you seem to think they're asking for.  They're not asking you to show 
them code which was not the result of careful design.  No.  Indeed, they 
all agree with you that careful planning is always a good idea, in fact 
critical.

Rather, what they are asking you to do is to create the complete 
top-down design _yourself_ and then show it to them.  If you do a 
complete design that is well-though-out and complete, then code (ie. 
function prototypes) will naturally and easily fall out from that. 
Present your design and the resultant code for evaluation.

Only then can kernel developers give you meaningful feedback.  You'll 
notice that the major arguments aren't about your design but rather 
about there being a lack of anything to critique.  If you want feedback, 
you must produce something which CAN be critiqued.

Follow the scientific method:
1) Construct a hypothesis (the document you have already written plus 
more detail).
2) Develop a means to test your hypothesis (write the code that your 
design implies).
3) Test your hypothesis (present your code and design for criticism).
4) If your hypothesis is proven wrong (someone has a valid criticism), 
adjust the hypothesis and then goto step (2).

Perhaps you have not done this because you feel that your "high level" 
design (which you have presented) is not complete.  The problem is that, 
based on what you have presented, no one can help you complete it. 
Therefore, the thing to do is to complete it yourself, right or wrong. 
Only when you have actually done something which is wrong can you 
actually go about doing things correctly.  Actually wrong is better than 
hypothetically correct.

Then, you may be thinking that this will result in more work, because 
you'll create a design and write come code just to find out that it 
needs to be rewritten.  But this would be poor reasoning.  It would be 
extremely unrealistic to think that you could create a design a priori 
that was good and correct, before you've ever done anything to test its 
implications.

Mostly likely, you would go through several iterations of your spec and 
the implied code before it's acceptable to anyone, regardless of how 
good it is to begin with.  Just think about how many iterations Con and 
Nick have gone through for their interativity schedulers; they've had 
countless good ideas, but only experimentation and user criticism could 
tell them what really worked and what didn't.  And these are just the 
schedulers -- you're talking about the architecture of the whole kernel!

Re: A Layered Kernel: Proposal

[Mike Fedyk]

Grigor Gatchev wrote:
> 
> On Mon, 8 Mar 2004, Theodore Ts'o wrote:
>>Is my description of Linux's device model accurate?  Sure.  Is it
>>useful in terms of telling us what we ought to do in order to improve
>>our architecture?  Not really.  It's just a buzzword-compliant,
>>high-level description which is great for getting great grades from
>>clueless C.S. professors that are more in love with theory than
>>practice.  But that's about all it's good for.
> 
> 
> You mean that, for example, drawing house elements on paper, and tossing
> some numbers here and back is useless in deciding how to build a house,
> and only getting hands to the real bricks gives you whether this wall
> should be here, and whether that column is thick enough to survive through
> a quake?

You are saying you should build a house with walls.  They're asking for 
a schematic (function prototypes), not to build the house yourself (not 
to code it all yourself).

Oh yeah and what Timothy Miller said! :-D

Mike