| |||||||||||||
This code is there not for performanceThis code is there not for performancePosted Feb 12, 2008 7:32 UTC (Tue) by khim (subscriber, #9252)In reply to: vmsplice(): the making of a local root exploit by dw Parent article: vmsplice(): the making of a local root exploit
It's easy to say in userspace code: we'll just never use structures as big as 2GiB or larger - then we can safely use signed offsets. Of you can use 64bit offsets if you want 4GB so badly. The problem with kernel is that both solutions are inadequate: 64bit offsets will require full-sized locking on many architectures - and that's sometimes can cost you 100-150% slowdown (or even more in rare cases), 2GB limit will make the system unusable (ask HURD guys who had such limit for partition size few years ago). Thus kernel code is full is strange arithmetic where you try to calculate something in range of terabytes (think disk) with just 32bit integers. Of course it's not "clean and easy to read" but it's necessary if you want production kernel and not a toy.
(Log in to post comments)
This code is there not for performance Posted Feb 12, 2008 12:44 UTC (Tue) by michaeljt (subscriber, #39183) [Link] Perhaps I misunderstood here, but I think that the original poster was saying something else - not that you do not do all these things (strange arithmetic and suchlike), but that you keep the code in one place (i.e. a set of macros) instead of duplicating it in lots of places. Not that it would have helped much here, since the problem was a failure to validate user input.
This code is there not for performance Posted Feb 12, 2008 13:50 UTC (Tue) by ms (subscriber, #41272) [Link] I'm obviously going to sound like a broken record again. The problem is validating incoming data. Now you next need to ask, "why should we validate user input?" to which the answer is "because the user can supply silly values" to which the next question is "well why can the user to supply silly values?" to which the answer is "because the type of the values the user is supplying are too wide". So basically, you're using the wrong types. Users should not be allowed to present "bad" input: the type system should prevent it. In an ideal world...
This code is there not for performance Posted Feb 12, 2008 14:38 UTC (Tue) by nix (subscriber, #2304) [Link] That's nice in theory, but I'm not sure it's entirely practical to require the users to provide a different pointer type for every possible VM range! (Also, kernel/user boundaries are necessarily special places: typing across the boundary is a matter of consensus as much as enforcement.)
This code is there not for performance Posted Feb 12, 2008 14:49 UTC (Tue) by ms (subscriber, #41272) [Link] Yeah, I don't disagree. It is a hard thing to do - you tend to get into messes with dependently typed languages and so forth - one could easily argue that they're not quite ready for writing kernels in! Typically, you first implement maths in the type system, then you can implement a basic "is smaller than" so then you could effectively arbitrarily refine the int range to be "the value must be an int and must also be smaller than x". That kinda thing. Of course, as soon as you hit "the value must be a function which will terminate", you're in trouble...!
This code is there not for performance Posted Feb 12, 2008 15:05 UTC (Tue) by nix (subscriber, #2304) [Link] There are a good few languages (Cayenne and Qi spring to mind) with type systems that are so powerful that they themselves trip the halting problem: compilation is no longer guaranteed to terminate. :) I suppose a simple ranged length type (length must be >0) would have sufficed here: you wouldn't need separate types for every possible valid pointer range.
Halting problem ? Ha! Posted Feb 12, 2008 20:17 UTC (Tue) by khim (subscriber, #9252) [Link] C++ has them beat: it's type system is not just trigger halting problem, it's turing-complete!
Halting problem ? Ha! Posted Feb 12, 2008 21:00 UTC (Tue) by nix (subscriber, #2304) [Link] C++'s template expander is modelled on ML's pattern matching. Cayenne and Qi are both perhaps two generations beyond that (both type systems being more powerful than Haskell's) in different directions: personally I prefer Qi's, but part of that is probably because it's possible to bootstrap the Qi implementation without being an ultra-guru). Of course, C++ compilers often *appear* to not halt when compiling anyway ;}
Halting problem ? Ha! Posted Feb 14, 2008 22:01 UTC (Thu) by lysse (guest, #3190) [Link] I don't know if you're joking about C++, but one of the notable things about Qi is that its type system *is* Turing-complete, by intent and proof (someone implemented SK combinators in it).
Halting problem ? Ha! Posted Feb 15, 2008 0:06 UTC (Fri) by ms (subscriber, #41272) [Link] No, nix wasn't joking. If you use C++ templates and limit yourself to numbers then it really is turing complete. Haskell, with the right flags (undecidable instances and overlapping instances) is also Turing complete. Cayenne is deliberately so and many people are now really thinking that it's just better to permit Turing completeness and let the programmer take responsibility. The alternative is more like what Epigram is looking at (amongst others) where you limit recursion to on the structure of terms and prevent infinite structures. That way, you can still guarantee termination. I fear we may now be some way from the original issue though ;)
Halting problem ? Ha! Posted Feb 15, 2008 21:48 UTC (Fri) by nix (subscriber, #2304) [Link] I used the wrong terms, really. What Haskell, Cayenne and Qi provide over C++ is (radically) greater *expressiveness*. The syntax of Qi type definitions is especially strange, but it's a hell of a lot saner than trying to define anything complicated using C++ templates.
This code is there not for performance Posted Feb 13, 2008 15:45 UTC (Wed) by werth1 (subscriber, #48435) [Link] The answer to the second question "why can the user supply silly values?" is more like: Because he can. The user is free to chose any language he wants to interface with the kernel. In particular the user is free to chose a language without or limited type checks. So any range checks on system functions have to be in the kernel itself.
This code is there not for performance Posted Feb 16, 2008 11:28 UTC (Sat) by ernest (subscriber, #2355) [Link] It is unfortunate that the CPU cannot enforce signedness and size types. Anybody programming in assembly can bypass any higher level language type checks you have in mind. This is true even if the users has the best intentions. Ernest.
This code is there not for performance Posted Feb 17, 2008 19:50 UTC (Sun) by giraffedata (subscriber, #1954) [Link] It is unfortunate that the CPU cannot enforce signedness and size types. The unfortunateness is at a lower level than that. It's unfortunate that a CPU can't do ordinary integer math, where 2 + 2 = 4. I understand why the very first CPUs wrapped around integers -- it happens naturally with the simplest implementations. But I don't get why no CPU today provides even the option of trapping on an arithmetic overflow instead of wrapping around silently. They do it for floating point, but not for integers.
Trapping on overflow Posted Feb 23, 2008 21:45 UTC (Sat) by anton (guest, #25547) [Link] But I don't get why no CPU today provides even the option of trapping on an arithmetic overflow.MIPS and Alpha have separate arithmetic instructions that trap on signed overflow (e.g., ADD on MIPS and ADDV on Alpha). IA-32 has INTO which traps if OF is set. Apparently this instruction was so rarely used by programmers, that AMD64 removed it in order to free up some opcode space, and did not even bother to allocate another (multi-byte) opcode for it; but you can still implement the functionality by combining JO (or JNO) with INT. The existence of INTO has not helped against this security hole, though.
Trapping on overflow Posted Feb 23, 2008 22:24 UTC (Sat) by giraffedata (subscriber, #1954) [Link] MIPS and Alpha have separate arithmetic instructions that trap on signed overflow ... Nice. Do you know if there is any way to make GCC (or any other C compiler) generate such instructions? I can understand people resisting adding instructions to handle overflow, but if I could declare in my C program "no arithmetic in here is supposed to wrap around" and get signalled to death if it does, I'd do it a lot.
Trapping on overflow Posted Feb 28, 2008 21:23 UTC (Thu) by anton (guest, #25547) [Link] Apart from asm statements and modifying gcc I don't know of a way to get gcc or other compilers to use the trapping instructions for C code.Concerning "no arithmetic in here is supposed to wrap around", unsigned arithmetic is supposed to wrap around in standard C, only signed arithmetic is allowed to trap (or do anything else) on overflow.
Magic exists by necessity alone Posted Feb 13, 2008 0:19 UTC (Wed) by jd (guest, #26381) [Link] Well, yes, but ideally you'd have some kind of abstraction. Since the numbers and arithmetic are "magic", they must also be impermanent and subject to continual experimentation. Possibly by a coder, possibly by the person compiling, possibly by the OS itself. As such, those need to be the components that are most easily identified and changed in a consistant way - in terms of calculations and type ranges.Making this "pure" beyond a certain level is, agreed, problematic. You don't have infinite CPU cycles and although the compiler can do some optimization, it can't turn an abstract, general solution into something tuned to a considerably narrower range of special cases that are usable in practice that are further constrained by the implementation details of a given architecture, which is all any real-world physical computer can ever be. A way round this would be to have some sort of hypothetical generic architecture, which implemented the formal "pure" solution but was never - and could never - actually used in practice. As all usable architectures would necessarily be perfect subsets of the "pure" solution, it no longer matters if it is easy to read, you know it's just a re-arranged and contracted form. However, here you run into a problem. This assumes a totally generic "pure" solution even exists, wholly independent of any architecture. Since you can't use such a solution, test-run such a solution or in many cases reverse-map onto such a solution, it's not obvious you could ever show a pure solution was indeed generic or was the solution the specific implementations were specific implementations of.
Magic exists by necessity alone Posted Feb 15, 2008 23:23 UTC (Fri) by vonbrand (subscriber, #4458) [Link] Even if a "perfect architecture" existed such that "real machines" are "perfect subsets" (real architectures are very different, sometimes in very weird ways), one of the problems writing a kernel is that real hardware is as buggy (or more!) as the next software (in the end, it is algorithms implemented in silicon, with the added burden that bugs can rarely patched and the rebuilt package distributed to the users).
|
|||||||||||||