Page fault handler as TSS
Ben_Gainey
tense recommended ;-) that the page fault handler should be a TSS task gate
as aposed to int gate/trap gate.
surely this is bad for performance ?
what does everyone else use?
if i were to use a int gate/trap gate and the pagefault was cause by the
stack stepping on a np-page then surely this will cause the pagefault to
double fault since the errorcode for the fault is pushed on the stack which
is what caused the fault in the first place?
ben
Frank M
I most definitely use a TSS for my page fault handler; the reason you
have suggested above about the double faulting (actually triple
faulting once the double fault handler faults on the NP page) is
exactly why one must use a TSS to handle page faults if one is using
paging. I actually use TSSes for all exceptions because if I didn't,
(and think about this), if a non-critical exception such as a divide
by zero occurred and it had a NP page for its stack, it would cause a
double fault, obviously very messy to clean up. Assuming your double
fault handler was a TSS, this is all that would happen, but if it
wasn't, it's triple fault time ;-P. As to performance, I have seen in
the 80386 Programmer's Reference manual that a TSS switch costs
something like 300 clock cycles, which doesn't seem like much. But
somewhere in a description of the Linux scheduler I saw that when a
TSS switch occurs, the CR3 changes as well if you are using paging,
and the processor's local cache needs to be flushed out to RAM which
can take upwards of 200us which is quite a long time.
Frank Millea
Scott Wood
> I most definitely use a TSS for my page fault handler; the reason you
> have suggested above about the double faulting (actually triple
> faulting once the double fault handler faults on the NP page) is
> exactly why one must use a TSS to handle page faults if one is using
> paging.
Why on earth would the double fault handler even be invoked, much
less take a page fault, during normal operation? If you can't keep
your double fault handler in memory, then you're screwed regardless
of whether you switch tasks to get to it.
> I actually use TSSes for all exceptions because if I didn't,
> (and think about this), if a non-critical exception such as a divide
> by zero occurred and it had a NP page for its stack, it would cause a
> double fault, obviously very messy to clean up.
So don't page out kernel stacks. Is the minor amount of memory
wasted by inactive threads[1] worth the overhead of going through a
task gate on every page fault? Alternatively, you could page out a
kernel stack if the corresponding task is idle for a long time, but
bring it back in before transferring control back to the task when it
wakes up. Or, you could just take the double fault through a task
gate; it can't be that much messier than dealing with a task gate for
ordinary faults.
> Assuming your double fault handler was a TSS, this is all that
> would happen, but if it wasn't, it's triple fault time ;-P.
Obviously, if you expect to have double faults due to a non-present
kernel stack, you need to use a task gate. This certainly doesn't
mean that you need to use one for anything else.
> As to performance, I have seen in the 80386 Programmer's Reference
> manual that a TSS switch costs something like 300 clock cycles,
> which doesn't seem like much.
It does seem like much when it is completely unnecessary.
> But somewhere in a description of the Linux scheduler I saw that
> when a TSS switch occurs, the CR3 changes as well if you are using
> paging, and the processor's local cache needs to be flushed out to
> RAM
No, it doesn't. The *TLB* needs to be invalidated, but the caches on
x86 are physically tagged, and thus can remain.
> which can take upwards of 200us which is quite a long time.
Maybe on a 386, but modern CPUs can switch address spaces much faster
than that.
-Scott
[1] And what about the stacks for the threads on the other side of
the task gates? Are you going to have one per normal thread? If
so, what's the point, since you can't page those stacks out? If
not, forget about sleeping in the fault handler (rather useful
when you need to bring in a page from disk) without going through
a lot of manual state saving.
David A. Caabeiro
I don't remember the intel comments, but I guess nobody uses task gates for
a PF handler (please correct me if I'm wrong).
Just being careful of not having PF in the middle of a stack switch and
having a decent stack size (both while in kernel mode) will suffice.
In user mode you don't care about this of course, as you previously switch
to a safe stack.
Regards,
David.
Reply to: ac AT turdera DOT com DOT ar
--
The nice thing about standards is that there are so many to choose from.
-- Andrew S. Tannenbaum
w m r
> Frank M <fran...@aol.com> wrote:
> > I most definitely use a TSS for my page fault handler; the reason you
> > have suggested above about the double faulting (actually triple
> > faulting once the double fault handler faults on the NP page) is
> > exactly why one must use a TSS to handle page faults if one is using
> > paging.
>
> Why on earth would the double fault handler even be invoked, much
> less take a page fault, during normal operation? If you can't keep
> your double fault handler in memory, then you're screwed regardless
> of whether you switch tasks to get to it.
>
I agree completely. Keep the kernel stacks in memory (I hear it's
very cheap these days). Simplify, simplify... Besides, can one
actually recover from a double fault? How do you know what the CPU
was *trying* to push on the stack when it double faulted? According
to the intel book, double faults are classified as an abort which
cannot be depended on restarting where the exception happened.
Mike
Ben_Gainey
having problems with tss in my kernel)
so do i need to switch to a tss for the kernel starting from the very
begining of my kernel stub, or does only the exception handlers need one.
why? or why not?
if i do, then does that mean that i will need a tss for user mode as well.
could i get away with doing this instead?
have a gaurd page at the bottom of each user stack that is present, but is
marked as a system pager rather than as a user page.
when the user stack accesses this page it will fault, but it will not double
fault right? since the page can be accessses by the ring0 kernel since the
page is present, but privilaged.
the pagefault handler would then just allocate a new page and shift the
guard page down.
do you think this would work?
it would alleiviate the need for a tss.
ben
"Ben_Gainey" <[hotmail] @ [uk_top_geek].com> wrote in message
news:a4epks$722$1...@news5.svr.pol.co.uk...
Tim Robinson
| OK so i need to use TSS for most exceptions ( i was gunna neway, but i
keep
| having problems with tss in my kernel)
| so do i need to switch to a tss for the kernel starting from the very
| begining of my kernel stub, or does only the exception handlers need one.
| why? or why not?
You don't need to. You can have normal ring 0 interrupt gates for your
exception handlers. The processor will, however, use the SS0:ESP0 fields of
the current TSS to find your kernel stack.
| if i do, then does that mean that i will need a tss for user mode as well.
The only reasons you *need* a TSS (assuming you're using software task
switching) are:
* To provide the SS0:ESP0 values for the switch from ring 3 to ring 0
* To provide the CPU with an I/O permissions bitmap (optional)
* To give you a double fault handler (which will definitely need its own
stack and everything else)
| could i get away with doing this instead?
|
| have a gaurd page at the bottom of each user stack that is present, but is
| marked as a system pager rather than as a user page.
| when the user stack accesses this page it will fault, but it will not
double
| fault right? since the page can be accessses by the ring0 kernel since the
| page is present, but privilaged.
| the pagefault handler would then just allocate a new page and shift the
| guard page down.
| do you think this would work?
|
| it would alleiviate the need for a tss.
Yes. It's normal demand allocation and I (and most other people) use it all
the time.
General algorithm:
* User app asks for memory (or code is loaded, or a stack defined)
* Kernel says "OK" but all it does is reserve space in that process's
virtual address space
* Kernel marks all relevant PTEs as non-present
* User app continues and later tries to access the pages 'allocated' before
* CPU invokes a page fault which is handled by the kernel
* Kernel notices that the fault address is inside a range which had been
allocated but not committed (i.e. no physical memory was allocated)
* Kernel commits physical pages and updates the PTEs
* User app is none the wiser
See http://www.themoebius.org.uk/tutes/memory2.html.
--
Tim Robinson
http://www.themoebius.org.uk/
Scott Wood
> have a gaurd page at the bottom of each user stack that is present,
> but is marked as a system pager rather than as a user page. when
> the user stack accesses this page it will fault, but it will not
> double fault right? since the page can be accessses by the ring0
> kernel since the page is present, but privilaged. the pagefault
> handler would then just allocate a new page and shift the guard
> page down. do you think this would work?
You *do* realize that even with a trap gate, the stack will be
switched when you switch privilege levels, right? The user stack has
no bearing on whether a double fault occurs.
Besides, if it *did* work the way you describe, a malicious user task
could just put a random value in ESP and cause a double fault anyway.
-Scott
Frank M
> > I most definitely use a TSS for my page fault handler; the reason you
> > have suggested above about the double faulting (actually triple
> > faulting once the double fault handler faults on the NP page) is
> > exactly why one must use a TSS to handle page faults if one is using
> > paging.
>
> Why on earth would the double fault handler even be invoked, much
> less take a page fault, during normal operation? If you can't keep
> your double fault handler in memory, then you're screwed regardless
> of whether you switch tasks to get to it.
This isn't during normal operation. It would be during an exception of
some kind. Let's say the current thread allocates some memory which it
will now use as its new stack (this is just some odd thing it decides
to do, I can't think of a practical use right now). Now when memory is
allocated, I do what I believe is called demand-mapped paging, where
you only allocate the address space, and upon the first access to that
memory, a page fault occurs and is fixed by simply allocating a page
of physical memory and updating the page table entry. Here we go:
cli ; no IRQs so this demo will work
push dword 4096
call _malloc ; return value will be in eax
add esp, 4
add eax, 4096 ; top of stack
mov esp, eax ; switch to new stack
push dword _hello_msg ; right here there will be a page fault
call _print_console
add esp, 4
_print_console: db "Hello", 0
Now if the page fault handler is a trap gate or interrupt gate,
eflags, eip, and cs will be pushed onto the stack. But wait! The stack
is what caused that fault in the first place. Now there is a double
fault. Same thing. Triple fault. Goodnight Irene.
>
> > I actually use TSSes for all exceptions because if I didn't,
> > (and think about this), if a non-critical exception such as a divide
> > by zero occurred and it had a NP page for its stack, it would cause a
> > double fault, obviously very messy to clean up.
>
> So don't page out kernel stacks. Is the minor amount of memory
> wasted by inactive threads[1] worth the overhead of going through a
> task gate on every page fault? Alternatively, you could page out a
> kernel stack if the corresponding task is idle for a long time, but
> bring it back in before transferring control back to the task when it
> wakes up. Or, you could just take the double fault through a task
> gate; it can't be that much messier than dealing with a task gate for
> ordinary faults.
I don't page kernel stacks. And anyway, why would an application
thread be using a kernel stack? To my knowledge there is no way to
prevent a thread from switching to a different stack as I have
described above. In my kernel, DS=SS so there would be no GPE...
> > Assuming your double fault handler was a TSS, this is all that
> > would happen, but if it wasn't, it's triple fault time ;-P.
>
> Obviously, if you expect to have double faults due to a non-present
> kernel stack, you need to use a task gate. This certainly doesn't
> mean that you need to use one for anything else.
You're right; as long as the double fault handler is a TSS with a task
gate, it would be OK, but I don't like to have my double fault handler
having to figure out what was the first fault.
> > As to performance, I have seen in the 80386 Programmer's Reference
> > manual that a TSS switch costs something like 300 clock cycles,
> > which doesn't seem like much.
>
> It does seem like much when it is completely unnecessary.
Touche.
> > But somewhere in a description of the Linux scheduler I saw that
> > when a TSS switch occurs, the CR3 changes as well if you are using
> > paging, and the processor's local cache needs to be flushed out to
> > RAM
>
> No, it doesn't. The *TLB* needs to be invalidated, but the caches on
> x86 are physically tagged, and thus can remain.
Thanks for clarifying. I knew about the TLB but I thought it was the
local cache too. Oh well...
> > which can take upwards of 200us which is quite a long time.
>
> Maybe on a 386, but modern CPUs can switch address spaces much faster
> than that.
> -Scott
>
> [1] And what about the stacks for the threads on the other side of
> the task gates? Are you going to have one per normal thread? If
> so, what's the point, since you can't page those stacks out? If
> not, forget about sleeping in the fault handler (rather useful
> when you need to bring in a page from disk) without going through
> a lot of manual state saving.
I never page out stacks for kernel fault handlers. I have implemented
sleeping in fault handlers (particularly the page fault handler) but I
do remember it required a *tiny* bit of manual state saving (although
not much); I haven't hacked that part of the kernel since last
November.
Frank Millea
Maxim S. Shatskih
> tense recommended ;-) that the page fault handler should be a TSS task gate
> as aposed to int gate/trap gate.
>
> surely this is bad for performance ?
Surely.
Neither NT nor Linux use it.
No reasons of using it.
Max
Maxim S. Shatskih
> have suggested above about the double faulting (actually triple
Double faults must never occur during normal operation.
The double fault handler must be a TSS (yes, it is so) and just performs the kernel panic.
Page fault can lead to double fault only in case of broken IDT (your bug) or kernel stack overflow (impossible on normal situation).
Max
Ben_Gainey
> Besides, if it *did* work the way you describe, a malicious user task
> could just put a random value in ESP and cause a double fault anyway.
yeah but all my apps for my OS behave ;-)
>
> -Scott
Ben_Gainey
> Yes. It's normal demand allocation and I (and most other people) use it
all
> the time.
i know that, what i was suggesting, (but having read further it is a v bad
idea) is for because i was wondering about the feasability of using a trap
gate for the page fault handler (now you see why it is a crazy idea ;). that
is why the guard page is present, but kernel mode, as apposed to notpress,
so that when the stack overflows ( my OP was about stack overflowing in this
situation ), the cpu can still place the errorcodes etc in the stack since
the kernel is run in kernel mode -> it would just mark the guard page as
usermode then instead of kernel mode and return.
anyway it doesnt matter now since the origional reason i came up with this
idea was because i couldnt get my TSSes to work and i couldnt be bothered to
fix them so i decided to see if i could do it without any TSSes at all.
obviously not!!!
anyway i fixed them so it doesnt matter ;)
David A. Caabeiro
> I don't page kernel stacks. And anyway, why would an application
> thread be using a kernel stack? To my knowledge there is no way to
I suppose your task is at CPL3, so when going to CPL0 (or 1 or 2)
the processor switches stacks. This is the kernel stack, and having
it in memory saves you from using task gates in your handlers.
Regards,
David.
Reply to: ac AT turdera DOT com DOT ar
--
DEC: Do Expect Cuts
David A. Caabeiro
> OK so i need to use TSS for most exceptions ( i was gunna neway, but i keep
> having problems with tss in my kernel)
No, you don't. The only one necessary would be the double fault handler.
And *maybe* the NMI handler... although I still don't understand why this
would be necessary (I saw this used, don't remember where though)
David.
Reply to: ac AT turdera DOT com DOT ar
--
C has its problems, but a language designed from scratch would have some too,
and we know C's problems. --Bjarne Stroustrup
Jerry Coffin
nos...@turdera.com.ar says...
> On Thu, 14 Feb 2002 13:47:38 -0000, Ben_Gainey <[hotmail]@[uk_top_geek].com> wrote:
> > OK so i need to use TSS for most exceptions ( i was gunna neway, but i keep
> > having problems with tss in my kernel)
>
> No, you don't. The only one necessary would be the double fault handler.
> And *maybe* the NMI handler... although I still don't understand why this
> would be necessary (I saw this used, don't remember where though)
I'm not sure it's absolutely necessary for the NMI handler, but it
probably doesn't hurt anything. OTOH, an NMI often signals something
so drastically wrong that it rarely makes much difference exactly HOW
you try to handle it. If, for example, your memory's getting
corrupted so a parity error raises an NMI, it's entirely possible
that the instructions in your NMI handler will also be corrupted, so
it may not do what you want anyway...
--
Later,
Jerry.
The Universe is a figment of its own imagination.
Maxim S. Shatskih
> some kind. Let's say the current thread allocates some memory which it
> will now use as its new stack
Just never do this in kernel.
The trap frame is pushed to _kernel_ stack, not user one. User stack is not necessary for trap handling.
Max
Maxim S. Shatskih
> marked as a system pager rather than as a user page.
> when the user stack accesses this page it will fault, but it will not double
> fault right? since the page can be accessses by the ring0 kernel since the
> page is present, but privilaged.
> the pagefault handler would then just allocate a new page and shift the
> guard page down.
> do you think this would work?
Exactly this works in NT.
Max
Tim Robinson
news:a4grba$2675$2...@gavrilo.mtu.ru...
| Double faults must never occur during normal operation.
| The double fault handler must be a TSS (yes, it is so) and just performs
the kernel panic.
| Page fault can lead to double fault only in case of broken IDT (your bug)
or kernel stack overflow (impossible on normal situation).
I thought I remember you saying that NT could enlarge its kernel stacks via
double faults?
Piotr Wyderski
Tim Robinson wrote:
> I thought I remember you saying that NT could enlarge its kernel stacks
via
> double faults?
Yes, I remember it too. Max... ? :-)
Best regards
Piotr Wyderski
w m r
I don't see how that's possible, as the Intel book classifies a double
fault as an abort, which it says it can't guarantee a clean recovery.
Mike
Piotr Wyderski
w m r wrote:
> I don't see how that's possible, as the Intel book classifies a double
> fault as an abort, which it says it can't guarantee a clean recovery.
But there's a superior rule: Intel's books don't appoint reality :-)
In fact, it really works, however yes, it is a trick :-) And... everybody
(including me) make use of it in their OS-es.
Best regards
Piotr Wyderski
w m r
> w m r wrote:
>
> > I don't see how that's possible, as the Intel book classifies a double
> > fault as an abort, which it says it can't guarantee a clean recovery.
>
> But there's a superior rule: Intel's books don't appoint reality :-)
I wouldn't bet the farm (design) on it, though, future processors may
not behave likewise. Especially since it isn't necessary to do so.
> In fact, it really works,
Are you sure it works under all circumstances (pending interrupts,
floating point exceptions, etc)?
> however yes, it is a trick :-) And... everybody
> (including me) make use of it in their OS-es.
I don't. My double fault handler prints a register and stack dump
then halts. Right now, my kernel stacks are 3 pages with 1 guard. I
haven't see it use over 5K, though (except for bugs).
I believe Linux puts kernel stacks in non-paged pool (at the end of
the thread struct) so it would overwrite the thread struct on
overflow. I don't think it would expand the kernel stack on a double
fault (the thread struct and possibly lots of other stuff would be
wiped out by then), but I haven't looked to see for sure.
I try to stick to the intersection of what the book says is legal and
what I can get to work, rather than the union. But if one has an
alternate plan should that one break, I suppose that's all that
matters.
Mike
Piotr Wyderski
w m r wrote:
> I wouldn't bet the farm (design) on it, though, future processors may
> not behave likewise. Especially since it isn't necessary to do so.
Well, I see no reason the #DF exception can't guarantee a clean
recovery, especially when it is handled via task gate. It has a special
meaning, but it is still an ordinary exception. If Max or Jerry can
confirm that NT implements a recoverable #DF handler, I'll be sure
this feature will be supported by further processors. :-)
> > In fact, it really works,
>
> Are you sure it works under all circumstances (pending interrupts,
> floating point exceptions, etc)?
No, I didn't check that, but why shouldn't it work?
> I believe Linux puts kernel stacks in non-paged pool (at the end of
> the thread struct) so it would overwrite the thread struct on
> overflow.
Linux is weird. I can understand stack overflows, but
underflows can be caused only by a broken compiler.
So they could at least put the stack below the thread
struct. Guard pages are cheap too... I use them heavily
in my OS -- each kernel stack is composed of 1 guard
page and 3 memory pages. Stack underflows are
handled too, but is is a side effect of the stack array
organisation. Thread descriptors are held in a completely
different place, above all stack.
Best regards
Piotr Wyderski
Scott Wood
> Linux is weird. I can understand stack overflows, but
> underflows can be caused only by a broken compiler.
Or by buggy code that overruns buffers on the stack, assuming the
stack grows downward, though hopefully that would be even rarer in
kernel code than excessive stack usage.
> So they could at least put the stack below the thread
> struct.
They could, though I'm guessing that the reason why they don't is
that it would require an extra instruction to get the task struct
base address, all to prevent something that should never happen in
the first place. Besides, unless you use guard pages, you'd just be
corrupting something else (maybe another task's struct), which would
likely be even harder to debug.
> Guard pages are cheap too...
Cheap, but not free. They require the stacks to have individual
entries in the TLB, whereas if you have all physical memory mapped,
you can use larger pages (or even no pages at all, if you're on a
chip or architecture such as MIPS that provides an unmapped physical
memory region for kernel space).
Of course, it could be made an option that can be enabled for
debugging and disabled for normal use.
-Scott
Debs
On Sat, 16 Feb 2002 20:16:42 +0100, Piotr Wyderski spake thus:
>Well, I see no reason the #DF exception can't guarantee a clean
>recovery, especially when it is handled via task gate. It has a special
>meaning, but it is still an ordinary exception. If Max or Jerry can
>confirm that NT implements a recoverable #DF handler, I'll be sure
>this feature will be supported by further processors. :-)
The Intel docs state that for a #DF exception "The saved contents of
CS and EIP registers are undefined." (page 5-33 of 24319202.pdf). As
such, it would be impossible to return to the same position in the
code that caused the exception, and the best that you can expect is to
be able to save the processor state and shut down the application. If
the code that caused the exception is just an exception, then fine, it
could be stopped and restarted (if the OS supports that, of course).
If it's the kernel that causes the exception, then there is no way to
restart it, as you ahve no way of knowing what code to return to.
I guess it must be possible to have a mechanism whereby you always go
to a certain part of the kernel when a #DF is generated, and then
treat it as if it is just time to switch tasks (then if the same code
generates a #DF as soon as it is given control again, you will know
you have no choice but to shut it down), but that would not solve the
problem of what caused the exception, and could do more harm than
good, as the processor state that has to be saved for the task causing
the exception will be the same when you return to it (if you are lucky
enough to be able to determine the values of CS:EIP, that is, which
seems unlikely from what the Intel docs say).
Basically, I would say that a #DF handler can guarantee a clean
recovery, as long as it is an app that causes it and you shut the app
down. It just can't recover the app that caused it.
--
Debs
de...@dwiles.nospam.demon.co.uk
----
Misspelled? Impossible! I have an error correcting modem.
Piotr Wyderski
Debs wrote:
> The Intel docs state that for a #DF exception "The saved contents of
> CS and EIP registers are undefined." (page 5-33 of 24319202.pdf).
Yes, I know that, but I repeat: there's a superior rule. :-) In fact a #DF
exception is handled as an ordinary fault and thus it is recoverable.
CS and EIP are stored in the current process TSS. I checked that
personally, please believe me :-)
> As such, it would be impossible to return to the same position in the
> code that caused the exception, and the best that you can expect is to
> be able to save the processor state and shut down the application. If
> the code that caused the exception is just an exception, then fine, it
> could be stopped and restarted (if the OS supports that, of course).
Yes, due to the documentation, you're right. But IA-32 processors
are not made according to their own specification. :-) I've strong
feelings that their specification has been written much later :->
> If it's the kernel that causes the exception, then there is no way to
> restart it
Well, it's not so simple. Today there are just several systems with
fairly divided kernel parts and user parts. The remaining OS-es use
sth. I would call supervisor mode thread's code, because their
"kernels" work in the context of the current thread, not in the context
of the operating system monitor. The latter can be easily restarted,
just switch to the other process.
> as you ahve no way of knowing what code to return to.
Yes, but IMO it is because of poor CPU design. There
is no reason not to push a previous exception ID and
its error code on the #DF handler's stack.
A #DF exception means "big troubles", but not armageddon :-)
Use NMI for that purpouses.
Best regards
Piotr Wyderski
Piotr Wyderski
Scott Wood wrote:
> > Linux is weird. I can understand stack overflows, but
> > underflows can be caused only by a broken compiler.
>
> Or by buggy code that overruns buffers on the stack, assuming the
> stack grows downward, though hopefully that would be even rarer in
> kernel code than excessive stack usage.
Yes, I hope it is very rare, because I think we may expect
a lot more responsibility from system programmers than
from user-mode ones.
> They could, though I'm guessing that the reason why they don't is
> that it would require an extra instruction to get the task struct
> base address
IMHO it's a pure nonsense.
> > Guard pages are cheap too...
>
> Cheap, but not free. They require the stacks to have individual
> entries in the TLB, whereas if you have all physical memory mapped,
> you can use larger pages
I agree, but I think guarded stacks are a necessary part
of the minimum set of security services that our OS-es
should indispensably provide.
> Of course, it could be made an option that can be enabled for
> debugging and disabled for normal use.
Well, I am not sure, because exceptions and interrupts
are not able to be forecasted. It's like a physical theory
-- you can perform infinitely many positive experiments
(debugging) and you are still not sure it works; only one
negative experiment (normal use) is enough to destroy
your system/theory.
Best regards
Piotr Wyderski
Scott Wood
> Scott Wood wrote:
>> They could, though I'm guessing that the reason why they don't is
>> that it would require an extra instruction to get the task struct
>> base address
>
> IMHO it's a pure nonsense.
Only if you leave out the point that without guard pages, that extra
instruction buys you absolutely nothing. And besides, it's basically
the same reasoning that keeps things like runtime bounds checking out
of languages like C. It'd be nice for debugging, but it shouldn't
slow down correct code.
>> > Guard pages are cheap too...
>>
>> Cheap, but not free. They require the stacks to have individual
>> entries in the TLB, whereas if you have all physical memory mapped,
>> you can use larger pages
>
> I agree, but I think guarded stacks are a necessary part
> of the minimum set of security services that our OS-es
> should indispensably provide.
Guarded *kernel* stacks? Once the code has been debugged? Why?
>> Of course, it could be made an option that can be enabled for
>> debugging and disabled for normal use.
>
> Well, I am not sure, because exceptions and interrupts
> are not able to be forecasted. It's like a physical theory
> -- you can perform infinitely many positive experiments
> (debugging) and you are still not sure it works; only one
> negative experiment (normal use) is enough to destroy
> your system/theory.
Only if you allow unbounded exception/interrupt depth. If you don't
allow nested interrupts (which isn't a problem if you're either using
threaded interrupts or have properly small interrupt handlers), or
put a limit on how deep they'll nest before you stop re-enabling
interrupts, and if you make damned sure that you know what exceptions
can happen where, then you *can* know how deep the stack will grow.
Figure out the deepest it'll get *without* any interrupts or
exceptions, and then add on the longest interrupt/exception path.
Most of the time this is accomplished by sufficiently conservative
guessing, though it ought to be possible (barring really disgusting
tricks being played in the code) to write a tool (integrated with the
compiler, in all likelihood) that will examine the possible call
graph of your code and give you the longest stack path (or tell you
that you've got recursion that it can't figure out).
-Scott
w m r
> Piotr Wyderski <piotr.wyde...@hoga.pl> wrote:
> > Linux is weird. I can understand stack overflows, but
> > underflows can be caused only by a broken compiler.
I don't think I said anything about underflows. That really *would*
be crazy. Putting the stack at the end of the thread struct would
cause that thread struct to get wiped if the stack OVERflowed (at
least on x86 and alpha).
> Of course, it could be made an option that can be enabled for
> debugging and disabled for normal use.
Ya know, I was planning to do that someday. Allocing & filling in
pte's for stack pages and a guard page takes a relatively long time
compared to just doing a bigger malloc for the thread struct. Also,
when the thread exits, you have to invalidate the PTE's (on ALL
CPU's), as well as free the pages off. I want to minimize changes to
system page table entries. Start adding all that up and you'll have
more than a handful of cycles, spread out over several CPU's!
As far as reliability in a 'production' mode, I think the guard thing
is so marginally better, that the time savings outweighs any benefit.
Linux has no guard page and is considered a reliable OS. Certainly
for debugging though, having a guard page catches bugs.
Maybe a compromise would be to have a pool of free stacks that can be
re-used. Then the time savings would apply and you'd have a guard
page. Problem with that is if you have a flurry of threads you'd make
a lot of them, and you'd have wasted physical memory laying around
that might be better used for something else. So then you
could.......
Mike
PS, Seems to me PDP-11's had a stack limit register. D'OH!
Maxim S. Shatskih
> the thread struct) so it would overwrite the thread struct on
> overflow. I don't think it would expand the kernel stack on a double
> fault
It's impossible with Linux design. The process structure will get overwritten first, before MMU will have the chance to notice this,
which will cause panic.
Max
Maxim S. Shatskih
> double faults?
It enlarges the stack only "manually" from 3 pages to 16 pages if the thread does some GUI calls.
Double faults lead to BSOD UNEXPECTED_KERNEL_MODE_TRAP 00000008 immediately and this is a clear sign of kernel stack overflow.
Max
Maxim S. Shatskih
> > stack grows downward, though hopefully that would be even rarer in
> > kernel code than excessive stack usage.
>
> Yes, I hope it is very rare, because I think we may expect
> a lot more responsibility from system programmers than
> from user-mode ones.
Yes, thus guard pages deserve to exist on debugging platform only - either the debug build of the kernel or the usual kernel booted
with some flag.
Max
Piotr Wyderski
Scott Wood wrote:
> > I agree, but I think guarded stacks are a necessary part
> > of the minimum set of security services that our OS-es
> > should indispensably provide.
>
> Guarded *kernel* stacks?
Yes, guarded kernel stacks are indispensable. But not only they...
> Once the code has been debugged?
Please remember that debugging can show you that something
is going wrong, _NEVER_ that something is OK. Until you have
a mathematical proof of your code, it is untrusted and possibly
broken. It's a _fundamental_ rule, at least mine.
> Why?
Robustness, reliability... and because I think I've seen too much
crashes to believe debugging. Debugged code doesn't mean
correct code. Do you think debugging is enough? There was
a toy for 150 megabucks, Mars Climate Orbiter. It's code surely
has been debugged; however now it is splashed on the surface
of Mars. And Ariane 5, just to mention the most spectacular ones.
> Only if you allow unbounded exception/interrupt depth. If you don't
> allow nested interrupts (which isn't a problem if you're either usinsig
> threaded interrupts or have properly small interrupt handlers), or
> put a limit on how deep they'll nest before you stop re-enabling
> interrupts, and if you make damned sure that you know what exceptions
> can happen where, then you *can* know how deep the stack will grow.
> Figure out the deepest it'll get *without* any interrupts or
> exceptions, and then add on the longest interrupt/exception path.
"There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy."
I wish above to be a joke, but it isn't. It's reality :-(
> Most of the time this is accomplished by sufficiently conservative
> guessing, though it ought to be possible (barring really disgusting
> tricks being played in the code) to write a tool (integrated with the
> compiler, in all likelihood) that will examine the possible call
> graph of your code and give you the longest stack path (or tell you
> that you've got recursion that it can't figure out).
As you wrote, those tools can be applied to a small range of code classes.
It's easy to do it with "classical" programs without recursion, but not for
concurrent and distributed ones, self modifiable code, recursive functions,
etc. In fact, I am not sure this problem is decidable in general.
Best regards
Piotr Wyderski
Jerry Coffin
Piotr.W...@student.ii.uni.wroc.pl says...
[ ... ]
> Please remember that debugging can show you that something
> is going wrong, _NEVER_ that something is OK.
The "_NEVER_" there is a bit out of place -- some forms of debugging
(such as single-stepping through code) _can_ be used to verify
correct operation, such as verifying a correspondence between what
was desired and what was really generated.
> Until you have
> a mathematical proof of your code, it is untrusted and possibly
> broken. It's a _fundamental_ rule, at least mine.
Unfortunately, experience indicates that mathematical-style proofs
tend to contain bugs at nearly the same rate as code does. So far,
"proven" code has been substantially slower, more difficult, and more
expensive to develop, but has about as many problems as code
developed by more traditional methods. That's not to say that the
pursuit is necessarily pointless, only that for now there's not
really a lot of difference between the two.
> Robustness, reliability... and because I think I've seen too much
> crashes to believe debugging. Debugged code doesn't mean
> correct code. Do you think debugging is enough? There was
> a toy for 150 megabucks, Mars Climate Orbiter. It's code surely
> has been debugged; however now it is splashed on the surface
> of Mars. And Ariane 5, just to mention the most spectacular ones.
In point of fact, a lot of code like this IS supposed to be "proven".
Proofs, however, contain human reasoning and such, just like code
does, so they're subject to bugs as well (If you look through
mathematical journals, you'll find that it's fairly routine for
somebody to find a fault with somebody else's "proof").
The other problem is that a proof, at best, only shows that some set
of conclusions can logically be drawn from some set of premises -- if
the premises are wrong, the proof becomes meaningless.
w m r
>
> Robustness, reliability... and because I think I've seen too much
> crashes to believe debugging. Debugged code doesn't mean
> correct code. Do you think debugging is enough? There was
> a toy for 150 megabucks, Mars Climate Orbiter. It's code surely
> has been debugged; however now it is splashed on the surface
> of Mars. And Ariane 5, just to mention the most spectacular ones.
Reminds me of my days hanging out in alt.alien.research (pro ETH).
That NG has totally degenerated. But I think
www.disclosureproject.org is the greatest thing to happen.
Now why did it crash? Let's see, as you say, the code was surely
debugged, hmm...
Mike
Øyvind Jægtnes
Wasn't that the one where they used miles istead of kilometers or
something? :)
Debugged code sure doesn't help if the data is 50% off =)
--
Øyvind Jægtnes
Scott Wood
> Yes, guarded kernel stacks are indispensable. But not only they...
They're not literally *indispensable*; I've debugged plenty of kernel
code (including stack overruns) without them. They are convenient,
though.
>> Once the code has been debugged?
>
> Please remember that debugging can show you that something
> is going wrong, _NEVER_ that something is OK. Until you have
> a mathematical proof of your code, it is untrusted and possibly
> broken. It's a _fundamental_ rule, at least mine.
So every sanity check that is ever developed for debugging purposes
should be left in for all time, simply because it *might* still be
broken? Even when those checks slow things down?
Besides, even with guard pages a stack overrun in kernel space is a
fairly catastrophic event; who knows what the kernel was in the
middle of doing at the time?
> Robustness, reliability... and because I think I've seen too much
> crashes to believe debugging. Debugged code doesn't mean
> correct code.
No, but code that runs its stack into a guard page, especially in the
middle of a kernel critical section, is hardly correct either... :-)
>> Most of the time this is accomplished by sufficiently conservative
>> guessing, though it ought to be possible (barring really disgusting
>> tricks being played in the code) to write a tool (integrated with the
>> compiler, in all likelihood) that will examine the possible call
>> graph of your code and give you the longest stack path (or tell you
>> that you've got recursion that it can't figure out).
>
> As you wrote, those tools can be applied to a small range of code
> classes. It's easy to do it with "classical" programs without
> recursion, but not for concurrent and distributed ones, self
> modifiable code, recursive functions, etc. In fact, I am not sure
> this problem is decidable in general.
Self modifying code is bad enough. Self modifying code that
influences stack usage is downright evil. Just Don't Do It.
As for recursion, it should be avoided in limited stack situations
such as in the kernel. If you must use it, make damned sure that you
account for its stack usage manually; this wouldn't invalidate the
tool's results on other code paths.
As for concurrent and distributed code, how would that make it harder
to predict stack usage?
-Scott
Piotr Wyderski
Jerry Coffin wrote:
> The "_NEVER_" there is a bit out of place -- some forms of debugging
> (such as single-stepping through code) _can_ be used to verify
> correct operation, such as verifying a correspondence between what
> was desired and what was really generated.
I maintain my opinion :-), below is what I mean exactly. Single-stepping
through code (or generally: "white box" testing techniques) can verify
only the current execution path under specific circumstances. It can't
verify all execution paths under all circumstances.
> Unfortunately, experience indicates that mathematical-style proofs
> tend to contain bugs at nearly the same rate as code does.
Well, it is possible there are bugs, but it's a minor problem,
I would say it doesn't matter. Probably the only true problem
is how much we may assume. Please remember that proofs
are valid only inside specified models, don't expect a proof
to be true outside its model's context. A simple example:
Let K = {x: x \in N and x mod 6 = 0}. (N = natural numbers (with 0))
Theorem: each x \in K can be divided by 3 without any remainder.
Proof: since the factorization of x is not ambiguous, x may be
written as 2*3*r, where r \in N. Since it's factorization contains 3,
x can de divided by 3.
As you see, this theorem is surely true. But if we change our
assumptions a little, for example K = N, this theorem isn't true.
The same happens with proofs of code. First of all, we must
have a formal model of the machine, only then we can start
to write a proof. But in many situations we can't decide our
model is OK or wrong; in spite of that all proofs in that model
remain true. (please remember that FALSE => TRUE == TRUE).
A model can be unreal, in the worst case, but it's only a model
and the question "Is it true?" can't be applied to it. See, how
the model can change the proof:
{esp == n and eip == k}
pop eax
{esp == n+4 and eip == k+1 and eax == \sigma(n)}
I have assumed that there are no exceptions, so it's true. But
now I'll modify the model: assume we use paging. So:
{esp == n and eip == k}
pop eax
{}
As you see, we can say nothing about the postcondition,
if we use our previous model, or equally, our previous
conclusions are wrong. The model must be explicitely modified:
{esp == n and eip == k}
pop eax
{({present,readable} \incl page[n].attributes and esp == n+4 and eip ==
k+1 and eax == \sigma(n))
or {present,readable} !\incl paga[n].attributes and ...}
How about self-modifiable code:
{esp == n and eip == k}
x: pop eax
{(\sigma(x) == "pop eax" and esp == n+4 and eip == k+1 and eax' ==
\sigma(n)) or
(\sigma(x) == "inc eax" and esp == n and eip == k+1 and eax' == eax+1)
or
(\sigma(x) == "dec eax" and esp == n and eip == k+1 and eax' == eax-1)
or
...}
As you see, I use the same code, but various models and I obtain
completely different results and postconditions.
> So far,
> "proven" code has been substantially slower, more difficult, and more
> expensive to develop, but has about as many problems as code
> developed by more traditional methods.
Err... sorry, I don't understand. Proven code _can't_ be slower
or worse than not proven one (if we mean the same by "proof").
Can a mathematical theorem be worse than not proven one?
No! :-) Because the proof is completely outside the code
(or theorem, doesn't matter). A proof is a sequence of formal
transformations, it's not an extra code.
> That's not to say that the
> pursuit is necessarily pointless, only that for now there's not
> really a lot of difference between the two.
Well, agree, but IMHO it's because we are not able to build a formal,
logically closed models, or they are too complex.
> In point of fact, a lot of code like this IS supposed to be "proven".
And their proofs are true, just the models might be unreal :-)
Ariane 5: wrong model, MCO: garbage in, garbage out.
Both have been debugged and proven... :-P :-)
> Proofs, however, contain human reasoning and such, just like code
> does, so they're subject to bugs as well
Well, there are advanced researchs on an automatical provers
(and also: automatical code generation). Computers are a lot
more reliable than error-prone humans, however even they
are not oracles.
> (If you look through
> mathematical journals, you'll find that it's fairly routine for
> somebody to find a fault with somebody else's "proof").
That's true.
> The other problem is that a proof, at best, only shows that some set
> of conclusions can logically be drawn from some set of premises -- if
> the premises are wrong, the proof becomes meaningless.
This post is excatly about that. :-) But just one comment: not wrong set
of axioms, but rather not complete one. The first one is usually easy to
be found.
Best regards
Piotr Wyderski
Piotr Wyderski
Øyvind Jægtnes wrote:
> Wasn't that the one where they used miles istead of kilometers or
> something? :)
Well, I don't know what the disclossure project is (isn't it
related with Area 51? :-)), but it was Mars Climate Observer.
There was a similar error, when they used both English system
(sorry, I don't remember how do you call that :-)) and SI to
describe dynamical parameters of the engine and it stopped...
one kilometer below the ground's surface. :-) It was Mars
Polar Lander, IIRC. BTW, aren't we off-topic?
> Debugged code sure doesn't help if the data is 50% off =)
It doesn't matter code is debugged or not (wrong code may be
even better :-) ), if you feed it with a wrong data. Just GIGO :-)
Best regards
Piotr Wyderski
Piotr Wyderski
Scott Wood wrote:
> They're not literally *indispensable*; I've debugged plenty of kernel
> code (including stack overruns) without them. They are convenient,
> though.
IMHO we don't think about the same purposes. You would like to use
guarded stacks for debugging -- OK, they are not indispensable.
I need them to be sure my kernel will be stable under all circumstances
and to guarantee my kernel data structures are always valid.
> So every sanity check that is ever developed for debugging purposes
> should be left in for all time, simply because it *might* still be
> broken? Even when those checks slow things down?
Well, yes and no, what exactly are we talking about? About an "operating
system"
for toys? No, they are not necessary. About an operating system for
elevators?
_YES_, I don't think you would like an elevator which is trying to take you
to the the
11-th floor, if the building has only 7 floors :-))). If someone has
disabled sensors
(because they cost time, they are not necessary in most situations and they
deserve to exist in debugging elevators only ;-))) ), a passenger could
take a free,
0-gravity trip :-(( Generally, performance is not always the most important
thing.
> Besides, even with guard pages a stack overrun in kernel space is a
> fairly catastrophic event; who knows what the kernel was in the
> middle of doing at the time?
It is possible to build fault-tolerant kernels :-). Anyway, it depends on
how the kernel is designed. Some of them can't return to interrupted
code, some of them can.
>No, but code that runs its stack into a guard page, especially in the
> middle of a kernel critical section, is hardly correct either... :-)
Agree :-) But please note I haven't written that debugging is
wrong. It's a necessary operation, I think everybody thinks
similarly. Just I've met several people, who think debugging
is like a god -- if it says it can't find any bug, it means their
code is _absolutely_ correct.
> Self modifying code is bad enough. Self modifying code that
> influences stack usage is downright evil. Just Don't Do It.
However it is possible to write such code, so it should
be possible to make a call graph of it too. I don't use
self modifying code at all.
> As for recursion, it should be avoided in limited stack situations
> such as in the kernel. If you must use it, make damned sure that you
> account for its stack usage manually; this wouldn't invalidate the
> tool's results on other code paths.
Exactly. But many programmers don't perform similar checks
at all. Why for? :-) "Bugs can happen to anybody, but not to me."
> As for concurrent and distributed code, how would that make it harder
> to predict stack usage?
Because you can't easily predict a control flow graph (especially with
RPC-s).
Best regards
Piotr Wyderski
Maxim S. Shatskih
> (sorry, I don't remember how do you call that :-)) and SI to
I'm amazed English system is used in spacecrafts.
It is illogical, traditional-based, and English<->metric conversion is a pitchfork you can step on.
Max
Maxim S. Shatskih
> to the the
> 11-th floor, if the building has only 7 floors :-))).
I know a girl which was taught as an elevator techinician.
She told that this is not an usual thing - when the doors are opened to empty silo with no cabin nearby.
Max
Ben_Gainey
> > There was a similar error, when they used both English system
> > (sorry, I don't remember how do you call that :-)) and SI to
>
> I'm amazed English system is used in spacecrafts.
AFAIK USA still us uses totaly the Imperial system of measurements as it is
properly called.
Even in Britain we have some crazy upstarts moaning that the EU has forced
us to make it illegal to sell primarily in Imperial units - metric must be
the primary scale.
Since America makes lots of space ships I spose they would use their system
for measuring and stuff
ben
Debs
On Wed, 20 Feb 2002 00:01:23 -0000, "Ben_Gainey" <[hotmail] @
[uk_top_geek].com> spake thus:
>AFAIK USA still us uses totaly the Imperial system of measurements as it is
>properly called.
Well, they have to get something right :)
>Even in Britain we have some crazy upstarts moaning that the EU has forced
>us to make it illegal to sell primarily in Imperial units - metric must be
>the primary scale.
Bloody Europeans! I want to be able to go down the market and buy a
pound of spuds, I don't want half a kilo! And when I but tobacco, I
always confuse them (even the older shop assistants) because they have
all forgotten what pounds and ounces are, or they can't figure out how
to convert or I get the wrong amount. At least we managed to stay out
of the Euro (maybe when it has settled down a bit it won't be such a
bad idea, but until I am given a chance to vote on it I will always be
against it...)
>Since America makes lots of space ships I spose they would use their system
>for measuring and stuff
No, they are using *OUR* system, just one more thing they took from
the UK and made their own :洞
--
Debs
de...@dwiles.nospam.demon.co.uk
----
If you're not part of the solution, start another problem!
Kovacs Viktor Peter
Just a quick remark: :-))))
-the door problem could be fixed with a mechanical safety pin, activated
by the cabin
-most older (pre WWII) lifts had two halt switches that cut the power on
over and underruns (=> moving beyond the valid floors)
I was suprised that some of these systems were removed because modern
control systems just can't fail.
Viktor
ps:
I'm still using a ~80 years old lift every day...
Tim Robinson
news:0ts57ucimrgmk8qtr...@4ax.com...
| >Since America makes lots of space ships I spose they would use their
system
| >for measuring and stuff
| No, they are using *OUR* system, just one more thing they took from
| the UK and made their own :洞
My impression is that anyone who was at school in the last 10 or so years is
completely familiar with the metric system and finds it easier and more
logical.
This implies that:
* both systems are arbitrary
* as long as our schools keep teaching metric, the Imperial system will
eventually die out
Note that I am not making any implications about the ages of any of the
posters to this group, just a few observations :). Personally I prefer the
metric system -- except for large distances, where I tend to think in miles,
although I'm moving over to kilometres (thanks to the Army).
--
Tim Robinson
http://www.themoebius.org.uk/
Maxim S. Shatskih
> us to make it illegal to sell primarily in Imperial units - metric must be
> the primary scale.
> Since America makes lots of space ships I spose they would use their system
> for measuring and stuff
Well, for _sales_ this is OK. But for hi-tech stuff made in several countries like spacecrafts?
US has no mid-range space launcher - only Russia and France have.
Max
Maxim S. Shatskih
> although I'm moving over to kilometres (thanks to the Army).
Does Royal Army use kms?
Max
Maxim S. Shatskih
> over and underruns (=> moving beyond the valid floors)
You can open a door (to the empty silo) by special crowbar-like thing by pressing some electrical contact there.
Even these elevators have the catchers. Nevertheless, the falling elevator can gain enough kinetic energy that the floor will be
torn away when catchers will block the falling.
Max
Scott Wood
> Scott Wood wrote:
>> So every sanity check that is ever developed for debugging purposes
>> should be left in for all time, simply because it *might* still be
>> broken? Even when those checks slow things down?
>
> Well, yes and no, what exactly are we talking about? About an
> "operating system" for toys? No, they are not necessary. About an
> operating system for elevators? _YES_,
Well, not "every sanity check that is ever developed for debugging
purposes"; sometimes the check does more harm in terms of
reliability, by forcing a failure when otherwise it might have
worked. Now, if you've got a means of recovering from the error
condition without causing more damage, then fine, but somehow I don't
think you'd want something in the control system that logs some data
and freezes when something unusual happens (unless, of course, you can
detect this externally and shut down safely).
In any case, though, a safety-critical system such as an elevator
warrants more redudancy in the safeguards than most systems, and you
can't use failure scenarious from such a system to justify excessive
paranoia in general purpose software.
>> Besides, even with guard pages a stack overrun in kernel space is
>> a fairly catastrophic event; who knows what the kernel was in the
>> middle of doing at the time?
>
> It is possible to build fault-tolerant kernels :-). Anyway, it
> depends on how the kernel is designed. Some of them can't return to
> interrupted code, some of them can.
Wasn't the non-restartability of a double fault recently discussed
here? Taking all page faults through the TSS just to be able to give
emergency stack space to a misbehaving kernel thread seems
inappropriate for most general purpose systems.
>> Self modifying code is bad enough. Self modifying code that
>> influences stack usage is downright evil. Just Don't Do It.
>
> However it is possible to write such code, so it should
> be possible to make a call graph of it too. I don't use
> self modifying code at all.
Sure, it's possible to make a call graph of such code so by hand.
However, it's well outside the scope of what an automated tool could
do (barring AI well in excess of present technology), and it can be
easily avoided. It's kind of like saying a hammer is useless because
it can't turn a screw, when nails will do the job just fine.
>> As for recursion, it should be avoided in limited stack situations
>> such as in the kernel. If you must use it, make damned sure that you
>> account for its stack usage manually; this wouldn't invalidate the
>> tool's results on other code paths.
>
> Exactly. But many programmers don't perform similar checks
> at all. Why for? :-) "Bugs can happen to anybody, but not to me."
All the guard pages in the world aren't going to save the code of
someone who thinks like that. :-)
>> As for concurrent and distributed code, how would that make it harder
>> to predict stack usage?
>
> Because you can't easily predict a control flow graph (especially with
> RPC-s).
I'd think RPCs would generally not nest on the kernel stack... The
call graph as it applies to kernel stack usage would terminate at the
function to send the RPC. Incoming RPCs would get their own stacks.
-Scott
Jerry Coffin
Piotr.W...@student.ii.uni.wroc.pl says...
[ ... ]
> > Unfortunately, experience indicates that mathematical-style proofs
> > tend to contain bugs at nearly the same rate as code does.
>
> Well, it is possible there are bugs, but it's a minor problem,
> I would say it doesn't matter.
I'm a bit confused here: I thought the goal was to prevent bugs, but
when I point out that the method you're advocating seems just as
buggy as what you say it should replace, you say that doesn't matter?
> Probably the only true problem is how much we may assume.
Unfortunately, experience indicates that this isn't true. Even
starting from valid assumptions, it's quite easy for people to make
mistakes in chaining logic together to get from the assumptions to
the final proof.
> > So far,
> > "proven" code has been substantially slower, more difficult, and more
> > expensive to develop, but has about as many problems as code
> > developed by more traditional methods.
>
> Err... sorry, I don't understand. Proven code _can't_ be slower
> or worse than not proven one
The "slower" was a modifier on "to develop" -- I.e. I was saying it
takes longer to develop the code, not that the code runs slower when
you're done. In reality, it often IS slower when you're done, but
that's largely due to the nature of the tools involved -- I.e. most
people don't even attempt proven code in assembly language, and the
compilers that I've seen for producing executables from proven input
optimized _quite_ poorly.
> (if we mean the same by "proof").
> Can a mathematical theorem be worse than not proven one?
> No! :-) Because the proof is completely outside the code
> (or theorem, doesn't matter). A proof is a sequence of formal
> transformations, it's not an extra code.
Proving code written in something like Pascal, C or assembly language
borders on impossible. To prove anything more than really TINY toys
of programs, you have to drastically limit side-effects. The usual
way is to start with something like ML or Scheme. Even versions of
these languages that aren't fully verified generally aren't speed
demons, and the verified versions I've seen were mediocre in speed
compared to the others. Part of that was probably due to spending
time and effort on verification instead of optimization. At least in
some cases, however, it was due to intentionally removing
optimizations because nobody could figure out how to verify that they
always worked correctly.
If you want to look into one project, a search for "VLISP" on Google
(or whatever search engine you prefer) should turn up details of one.
Piotr Wyderski
Debs wrote:
> Well, they have to get something right :)
>
> >Even in Britain we have some crazy upstarts moaning that the EU has
forced
> >us to make it illegal to sell primarily in Imperial units - metric must
be
> >the primary scale.
Excuse me, is it a disadvantage?
> Bloody Europeans! I want to be able to go down the market and buy a
> pound of spuds, I don't want half a kilo!
You always can use any system of measures you wish, as far as
you could let electricians to install you a nine-phase 690V electric
installation in your home -- it's up to you. Just don't expect the rest
of us to use your weird system, we _won't_ :-)
> always confuse them (even the older shop assistants) because they have
> all forgotten what pounds and ounces are,
And that's completely OK -- I don't know how to convert SI units into
the system Poles used in the XII century, but I think I don't care about
that at all :-)))
> to convert or I get the wrong amount. At least we managed to stay out
> of the Euro (maybe when it has settled down a bit it won't be such a
> bad idea, but until I am given a chance to vote on it I will always be
> against it...)
The Euro is not so bad idea, however in fact I think it's your problem :-)
Anyway, I think (and it's not only my oppinion) you've the best standard
of electrical plugs, much better than European is, not to mention about
the American standard.
> >Since America makes lots of space ships I spose they would use their
system
> >for measuring and stuff
They don't make a lot of space ships themselves now, because it's not
economical.
Most of current programs are based on international groups, they also use
Russian
(and ESA) rockets, because they are much better and cheaper (for example,
everybody uses the RD engines now).
> No, they are using *OUR* system, just one more thing they took from
> the UK and made their own :洞
No, IIRC they use *OUR* (European, primarily French) for spacecraft.
I should check it, but I am 95% sure they do that. BTW, Debs, how many
inches is in a mile? :-) But please don't use a calculator, and write the
answer in three seconds :-> Is it the reason you use thousands of feet
in aircraft instead of miles? And: could you show me a repeatable
and constant standard of one foot (inch, mile -- doesn't matter)?
Best regards
Piotr Wyderski
PS. No malice included, I'm just curious.
Tim Robinson
Yes, it's been metric for a while now.
I presume you mean the "British Army" -- today's British Army was started by
Oliver Cromwell, back when Britain was a republic, so there was no royalty
around then. Just an obscure point.
Piotr Wyderski
Jerry Coffin wrote:
> I'm a bit confused here: I thought the goal was to prevent bugs,
Yes, it's our goal. :-)
> but when I point out that the method you're advocating seems just as
> buggy as what you say it should replace, you say that doesn't matter?
No. This is a discussion board, so I'm trying to be as honest as possible.
Because of that I wrote about disadvantages of the formal methods too.
I don't claim that formal methods is the only right way and they will
replace the remaining engineering methods. Formal methods can't
be used instead of debugging, both are somehow complementary.
I just insist that formal methods should be used everywhere they can
provide some profits. They are not for games in Java, web browsers,
mp3 players, etc. But they should be used for: operating system
kernels, realtime and critical software, numerical software, programming
languages compilers and so long. And (probably the most important thing):
formal methods _are not_ for everyone. Many programmers have
problems with them and they simply _are not able_ to make use of them.
The computer programming is now a craft, not a science. This causes
that the majority of programmers _don't have_ a formal, CS education.
Most of them are very proud they understand data structures like
the AVL trees or binomial heaps (of course "to understand" mean here
that they can implement these structures by hand, not that they really
understand proofs related with them). You _can't_ teach them formal
methods. That's sad, but true (at least in Poland, however I thinik it's
not only our problem).
BTW. Proven code is not buggy (i.e. if the proof is correct), just it is
valid
only with specified assumptions, under specified circumstances etc.
> > Probably the only true problem is how much we may assume.
>
> Unfortunately, experience indicates that this isn't true. Even
> starting from valid assumptions, it's quite easy for people to make
> mistakes in chaining logic together to get from the assumptions to
> the final proof.
Well, proving needs much experience. If one can't prove theorems,
computer science departaments of universities will throw him/her
away as fast, as possible. Many first year students can't pass
the course of logic -- about 60% fail and are removed. Computer
science is a kind of math -- sorry.
> The "slower" was a modifier on "to develop"
Sorry, I thought the only modifier was "and more expensive to".
Now it's clear and I have to agree with you.
> Proving code written in something like Pascal, C or assembly language
> borders on impossible.
That's true :-(
> To prove anything more than really TINY toys
> of programs, you have to drastically limit side-effects. The usual
> way is to start with something like ML or Scheme.
There's a nice support for predicates in Eiffel too. Anyway, you
may also prove the algorithm and then prove your implementation
matches it. I prefer this way.
Best regards
Piotr Wyderski
Piotr Wyderski
Scott Wood wrote:
> Well, not "every sanity check that is ever developed for debugging
> purposes"; sometimes the check does more harm in terms of
> reliability, by forcing a failure when otherwise it might have
> worked. Now, if you've got a means of recovering from the error
> condition without causing more damage, then fine, but somehow I don't
> think you'd want something in the control system that logs some data
> and freezes when something unusual happens (unless, of course, you can
> detect this externally and shut down safely).
Why don't you use a watchdog device? :-) More seriously: I mean only
kernels of operaning systems, realtime software, safety-critical software
and similar software. It _must_ be reliable like a hell and completely
fault-tolerant. I don't care about general purpose user-mode applications.
In fact, nobody cares :-)
> and you can't use failure scenarious from such a system to justify
> excessive paranoia in general purpose software.
Hmm... sometimes I make failure scenarios for my apps too,
but it's mainly a numerical stuff. In this context, paranoia can
be a kind of compliment :-)
> Wasn't the non-restartability of a double fault recently discussed
> here?
Of course it was! :-) It's a serious problem.
> Taking all page faults through the TSS just to be able to give
> emergency stack space to a misbehaving kernel thread seems
> inappropriate for most general purpose systems.
Yes, but this way is needed for fault-tolerant kernels IMHO
because of poor CPU design. A small modification of
a double fault handling microcode would simplify stable
kernel designs.
> Sure, it's possible to make a call graph of such code so by hand.
> However, it's well outside the scope of what an automated tool could
> do (barring AI well in excess of present technology), and it can be
> easily avoided. It's kind of like saying a hammer is useless because
> it can't turn a screw, when nails will do the job just fine.
Scott, I don't mean those tools are useless. They are just very limited.
> > Exactly. But many programmers don't perform similar checks
> > at all. Why for? :-) "Bugs can happen to anybody, but not to me."
>
> All the guard pages in the world aren't going to save the code of
> someone who thinks like that. :-)
:-) But they will save the code of the other programmers. They
could tell the system programmer/administrator that something
is going wrong. For example, the Linux code is written by many
people, not all of them are responsible enough. I wouldn't like
the system which works as follows: OK, OK, puff... core dump.
> Incoming RPCs would get their own stacks.
If you'd use this way, it's OK.
Best regards
Piotr Wyderski
Kovacs Viktor Peter
> > -most older (pre WWII) lifts had two halt switches that cut the power on
> > over and underruns (=> moving beyond the valid floors)
> You can open a door (to the empty silo) by special crowbar-like thing by
> pressing some electrical contact there.
You just push in the sensor spike...
> Even these elevators have the catchers. Nevertheless, the falling elevator
> can gain enough kinetic energy that the floor will be
> torn away when catchers will block the falling.
This would be serious error. The floor should be strong enough, and the
breaks must have a miximal slowing rate. (around 10 G)
Viktor
w m r
Look at www.disclosureproject.org -- now *what* don't we have? (Russia
has all that stuff, too, look at www.cheniere.org ;)
Mike
Debs
On Wed, 20 Feb 2002 01:12:50 -0000, Tim Robinson spake thus:
>"Debs" <de...@spamfree.net> wrote in message
>news:0ts57ucimrgmk8qtr...@4ax.com...
>| >Since America makes lots of space ships I spose they would use their
>system
>| >for measuring and stuff
>| No, they are using *OUR* system, just one more thing they took from
>| the UK and made their own :¬}
>
>My impression is that anyone who was at school in the last 10 or so years is
>completely familiar with the metric system and finds it easier and more
>logical.
I think most people find metric easier really. I just like to be the
devil's advocate on issues like this :)
Wouldn't you rather get a litre of beer for £2 instead of a pint? <G>
>
>This implies that:
>* both systems are arbitrary
>* as long as our schools keep teaching metric, the Imperial system will
>eventually die out
Actually, what I was saying (as a joke) was that the Americans stole
our system, and then wouldnt give it back - so we had to change to
metric :)
>
>Note that I am not making any implications about the ages of any of the
>posters to this group, just a few observations :).
hehehe. Good thing too. If you told everyone hold *I* am, they might
start taking me seriously, and we can't have that happen *too* often
:)
>Personally I prefer the
>metric system -- except for large distances, where I tend to think in miles,
>although I'm moving over to kilometres (thanks to the Army).
Metric is easier to work with (I think pretty much every country in
the world that has it's own currecny uses metric for that, because
it's easier to work with). I certainly would be as happy about writing
an app to work with inches, feet, yard, etc as I would with cm,
metres, etc. Far easier :) I still think in feet and inches, but I
almost always convert to metric for others (the only reason I think in
old measuremetns is because I was brought up with them, and as a
hippie I had no reason to learn a new system - now I'm old enough not
to really care). From a programming standpoint, though, I far prefer
metric. Imperial (for me) is just down to being too lazy to train
myself to think metric about most things :)
Daniel Camp
> "Debs" ...
> | No, they are using *OUR* system, just one more thing they took from
> | the UK and made their own :洞
And which we took from the Romans...
> My impression is that anyone who was at school in the last 10 or so years is
> completely familiar with the metric system and finds it easier and more
> logical.
I'm at school now, and I disagree, so there :)
end
The Campster
daniel [motty] camp [cat sat on the mat] bt open world [motty] com
"Sic semper burritus."
"Cavaeat humanus sic tofu tyrannus e toga."
Debs
On Wed, 20 Feb 2002 10:54:42 +0100, Piotr Wyderski spake thus:
>No, IIRC they use *OUR* (European, primarily French) for spacecraft.
>I should check it, but I am 95% sure they do that. BTW, Debs, how many
>inches is in a mile? :-)
That's easy.
44 feet/second = 30 miles/hour
--> 44*120 feet = 5280 feet = 1 mile
--> 12*5280 inches = 63360 inches = 1 mile :)
> But please don't use a calculator, and write the
>answer in three seconds :->
Hmm, it took me about 10 seconds to type out the working (although
doing it in my head took less than 2 seconds).
>Is it the reason you use thousands of feet
>in aircraft instead of miles? And: could you show me a repeatable
>and constant standard of one foot (inch, mile -- doesn't matter)?
I never needed to know a constant measurement which equates to an
inch/foot/whatever. Even the meter is not one most people would
memorise (it's based on something like the number of wavelengths of
the radiation output from a particular ion in one second, IIRC). I can
tell you that a mile is 1.609Km though (and an inch is 2.54 cm, a foot
is 30.48cm.....) <G>
Thank god I don't have to do all my calculations in inches/feet :)
Just because I still think in pounds and ounces doesnt mean I would be
happier to have them for everything, just that I'm old enough to ahve
been brought up with them (hey, over here we still buy weed by the
ounce and beer by the pint...<G>)
Maxim S. Shatskih
I mean Proton- or Ariane- range launcher.
Shuttle is too expensive and too heavy for such.
Max
Maxim S. Shatskih
> kernels, realtime and critical software, numerical software, programming
> languages compilers
I agree on anything except kernels. I don't think any of existing kernels was really proven to be correct.
Numerical - yes, there is an underlying theory, same are compilers.
But sorry, there is always a probability for a typo - like I used the name "Socket" instead of "AcceptSocket" in one code (they were
both valid variables).
No math and logic can deal with _these kinds of bugs_ (which are often main ones - others are from wrong assumptions on surrounding
operating environment), sorry, only debugging can.
The important code is also useful to be given to your colleague to read - thus the Linux stability regardless of their atrocious
coding style (their SCSI stack is the bottom level of the code I can read without HUGE mental efforts).
Max
Maxim S. Shatskih
> metric.
I think metric must be used for all hi-tech.
The correct work there is much more important then what people feel :-)
Max
Maxim S. Shatskih
Yes, metric is invented in France during Robespierre (spelling?)
Russia is metric since communist revolution in 1917.
Nevertheless, inches are used in Russia for:
- railroad width is 60in (1520mm). The rest of the railroad machinery is metric.
- tubes to supply water to apartments. They are measured in inches.
It is a known fact Russia cloned (exactly! one to one! including the bullet holes!) American B-29 just after WWII. The whole factory
which did this was switched to inches and feets, any talks on inches and feets among the engineers were considered "top secret" and
forbidden besides the factory territory.
This was a strange idea of Stalin's, since there were the native planes of matching quality (though never massively produced).
Max
Maxim S. Shatskih
> Oliver Cromwell, back when Britain was a republic, so there was no royalty
Sorry, confused with Royal Navy.
BTW - what is the common opinion on Cromwell in Britain? Liberator or nasty tyrant?
Max
Tim Robinson
I'm not sure there is a general opinion. He has a statue outside the Houses
of Parliament. The main road through Kensington is called "Cromwell Road" (I
live about 100m off it). There have been far more tyrannical kings in
English history... :)
dac
> "Tim Robinson" ...
>> "Debs" ...
>> | No, they are using *OUR* system, just one more thing they took from
>> | the UK and made their own :洞
>
> And which we took from the Romans...
And the romans from the greeks...
And the greeks from the egyptians...
And the egyptians from the babylonians...
:)
Regards,
David.
Reply: replace 'nospam' with my lastname
--
I do not fear computers. I fear the lack of them.
-- Asimov, Isaac
David A. Caabeiro
>> "Debs" ...
>> | No, they are using *OUR* system, just one more thing they took from
>> | the UK and made their own :洞
>
> And which we took from the Romans...
And the romans from the greeks...
Maxim S. Shatskih
> memorise (it's based on something like the number of wavelengths of
> the radiation output from a particular ion in one second, IIRC).
Originally, meter was 1/40.000 of Paris meridian.
Max
Alexei A. Frounze
>
> > Well, they have to get something right :)
> >
> > >Even in Britain we have some crazy upstarts moaning that the EU has
> forced
> > >us to make it illegal to sell primarily in Imperial units - metric must
> be
> > >the primary scale.
For you it looks more like an inconvinience, e.g. you can't operate with
something you used to. However, there's one thing about all of the systems.
Science. Ridiculous conversions from metric (or any system which has been
natural for the given area (like measuring energy in "electron-volts"
instead of just "Joules")) system to what you're used to and back isn't
something good because scientists aren't all of the same natinality and took
the same courses from the same teachers at school. OK, you may argue,
there's not so many scientists around some ordinary shop cashier :), but
again, wouldn't it be easier to use the same sytem for all? I'm not into the
religious issue about the only language on the planet (although that makes
sense as well). What's so bad about this?
I, too, during my first months in the States had a hard time converting
kilograms to pounds and meters/centimeters to miles/foots/inches, liters to
galons, Celsius to Fahrenheit and stuff. What a big deal? Shortly after you
start using the new system you'll be OK. Can't calculate w/o a pocket
calculator? -- go back to school and master your Rithmetics skills (as well
as Reading and Riting ones if need be :).
Good Luck
--
Alexei A. Frounze
http://alexfru.narod.ru
http://www.members.tripod.com/protected_mode/
Piotr Wyderski
Debs wrote:
> That's easy.
>
> 44 feet/second = 30 miles/hour
> --> 44*120 feet = 5280 feet = 1 mile
> --> 12*5280 inches = 63360 inches = 1 mile :)
>
> > But please don't use a calculator, and write the
> >answer in three seconds :->
>
> Hmm, it took me about 10 seconds to type out the working (although
> doing it in my head took less than 2 seconds).
If that's true: congratulations!, you are the first Imperial system user
I asked, who can do it fast. Really, I'm not joking.
Best regards
Piotr Wyderski
Barry Worthington
> "Maxim S. Shatskih" <ma...@storagecraft.com> wrote in message
> news:a51dcs$14in$1...@gavrilo.mtu.ru...
I must confess that I have no idea what this thread and n.g. is
about - I came across it while trawling the usenet groups for 'Oliver
Cromwell', a particular interest of mine. However, I hope you will
forgive me if I correct something and attempt to answer a question.
> | > I presume you mean the "British Army" -- today's British Army was
> started by
> | > Oliver Cromwell, back when Britain was a republic, so there was no
> royalty
As a matter of fact, Cromwell's New Model Army (England's first
proper national standing army) was completely demobilised upon the
restoration in 1660. This was because it could not (politically) be
trusted, and also the result of an aversion by the old former
cavaliers to any form of standing army. This was a bit of a problem,
as they weren't too happy with Charles II having a large military
force either. Charles got round this by raising a number of regiments,
ostensibly for the defence of Tangier in Morocco. (Part of the dowry
of Catherine of Braganza, his wife.) The money to pay them came from a
secret subsidy from Louis XIV. These troops soon found their way to
England, and the oldest regiments in the British Army trace their
descent from these regiments.
> | Sorry, confused with Royal Navy.
> | BTW - what is the common opinion on Cromwell in Britain? Liberator or
> nasty tyrant?
>
> I'm not sure there is a general opinion. He has a statue outside the Houses
> of Parliament. The main road through Kensington is called "Cromwell Road" (I
> live about 100m off it). There have been far more tyrannical kings in
> English history... :)
The Victorians gave Cromwell a very bad press, and this still
lingers (all those dreadful films in which the cavaliers are portrayed
as romantic heroes). But he has always been an important figure
amongst Liberals and on the left. Modern research has shown him to be
a political moderate (he really wanted a constitutional monarchy),
tolerant by the standards of the time (he allowed the jews to be
readmitted), and a strong but fair ruler. His England was a fairly
progressive place.
Regards,
Dr. Barry Worthington
Kovacs Viktor Peter
> Hello cyberfolk!
> On Wed, 20 Feb 2002 10:54:42 +0100, Piotr Wyderski spake thus:
> >No, IIRC they use *OUR* (European, primarily French) for spacecraft.
> >I should check it, but I am 95% sure they do that. BTW, Debs, how many
> >inches is in a mile? :-)
> That's easy.
> 44 feet/second = 30 miles/hour
> --> 44*120 feet = 5280 feet = 1 mile
> --> 12*5280 inches = 63360 inches = 1 mile :)
> > But please don't use a calculator, and write the
> >answer in three seconds :->
> Hmm, it took me about 10 seconds to type out the working (although
> doing it in my head took less than 2 seconds).
> >Is it the reason you use thousands of feet
> >in aircraft instead of miles? And: could you show me a repeatable
> >and constant standard of one foot (inch, mile -- doesn't matter)?
> I never needed to know a constant measurement which equates to an
> inch/foot/whatever. Even the meter is not one most people would
> memorise (it's based on something like the number of wavelengths of
> the radiation output from a particular ion in one second, IIRC). I can
> tell you that a mile is 1.609Km though (and an inch is 2.54 cm, a foot
> is 30.48cm.....) <G>
These are the new definitons of the SI base units.
For example 1 Kg is: (Kg = kilo gramm)
Take 1 liter of water on +4 C tempreture.
(1 liter is a cube with 0.1 meter long sides, the +4 C comes from
the fact that the water has the smallest size on +4 celsius; you have
to use sealevel pressure to get exact results)
This definition is very outdated, but this is how it started.
(The meter had a reference rod made out of platinum, made after some
mesurable size...)
Viktor
ps:
The big advantage of the new metric system is the easy transformation.
(base 10 shifts) We had an old CGS based (non SI) metric system... :-)
Warren W. Gay VE3WWG
> "Debs" <de...@spamfree.net> wrote in message
> news:0ts57ucimrgmk8qtr...@4ax.com...
> | >Since America makes lots of space ships I spose they would use their
> system
> | >for measuring and stuff
> | No, they are using *OUR* system, just one more thing they took from
> | the UK and made their own :洞
>
> My impression is that anyone who was at school in the last 10 or so years is
> completely familiar with the metric system and finds it easier and more
> logical.
Actually this is incorrect. They know *neither* system now. If I
ask my kids how long an item is, they have no idea in either
system (Canada was forced to metric a few decades ago). If I ask
them about temperature, they are just as confused.
The problem is that our system has been forced to teach only
metric, but yet we still have many things in "traditional
units" (for example our electronic thermistat is in Fahrenheit).
We also get a lot of US television.
The end result -- a whole generation that cannot cope in any system!
> This implies that:
> * both systems are arbitrary
> * as long as our schools keep teaching metric, the Imperial system will
> eventually die out
I can only see this being true when the "Imerial system" is no longer
used. Personally, I liked the Imperial system better.
--
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg
Debs
On Tue, 05 Mar 2002 17:57:19 GMT, Warren W. Gay VE3WWG spake thus:
>Actually this is incorrect. They know *neither* system now. If I
>ask my kids how long an item is, they have no idea in either
>system (Canada was forced to metric a few decades ago). If I ask
>them about temperature, they are just as confused.
Blimey! I was at school at the time when we changed from imperial to
metric, and I was fully capable of using both systems when I left
school. Ive had no trouble with either at any stage since then.
I have my preferences for different purposes though (metric is easier
to work with, for calculations, but so much is still done in imperial
that they both have their place...). I say keep the Euro out, bring
back Pounds/Shillings/Pence (LSD)!!! <G>
>
>The problem is that our system has been forced to teach only
>metric, but yet we still have many things in "traditional
>units" (for example our electronic thermistat is in Fahrenheit).
>We also get a lot of US television.
>
>The end result -- a whole generation that cannot cope in any system!
The biggest reason for that (at least, here in the UK) is the same as
the reason why kids can leave school without being able to read, write
or do basic math - the education system today sucks!
>
>I can only see this being true when the "Imerial system" is no longer
>used. Personally, I liked the Imperial system better.
hehehe. You're showing your age :)
--
Debs
de...@dwiles.nospam.demon.co.uk
----
If it's true that we are here to help others, then what exactly are the others here for?