7 ms·

Inline assembly in Linux

158 points by 0xAX 10y ago

alvaroma94 10y ago
qu tal
sillysaurus3 10y ago
I'm trying to add call/cc to node, or to lua. Recap: call/cc is the ability to save the current state of a running thread, then revert to that state at a later point in time. In other words, at any point in your program, you can say "Save the current stack." It's saved as a function. Later, whenever you call that function, the current stack is thrown out, and replaced with the saved stack. This is very useful for a number of reasons. It's also a very rare feature to have in your language. Neither node nor lua has support for this. The closest I've found is a Lua extension which adds coroutine.clone(). In principle, this is the solution. In practice, it has a number of limitations, such as restrictions on when you're allowed to call coroutine.clone(). (For example, if your stack looks like Lua -> C -> Lua, then it won't work.) I tried to channel my inner Mike Pall and solve this problem once and for all, but I'm not Mike Pall, and this is really hard. I was hoping you might know of any possible solution which is (a) practical, (b) cross-platform, and (c) works in all cases. Why post this here? Because this post happens to attract exactly the kind of people that might know a way forward. There must be a way. Apologies for the off-topic comment.
- loeg 10y ago
  getcontext(3) / setcontext(3). Not standard, but exists in both Linux and FreeBSD.
- kenOfYugen 10y ago
  James Long is currently playing with call/cc in JavaScript [1]. He mentioned a paper titled "Exceptional Continuations in JavaScript" [2], that describes the method he used in his implementation. Maybe you should get in touch? [1] https://twitter.com/jlongster/status/726259468405751808 https://twitter.com/jlongster/status/726259468405751808 [2] http://www.schemeworkshop.org/2007/procPaper4.pdf http://www.schemeworkshop.org/2007/procPaper4.pdf
- sitkack 10y ago
  I assume you have read http://okmij.org/ftp/continuations/against-callcc.html http://okmij.org/ftp/continuations/against-callcc.html
- haberman 10y ago
  > if your stack looks like Lua -> C -> Lua, then it won't work. I don't think you can safely solve this in the general case. There is a key problem I don't think you can work around. Say your stack looks like C(1) -> Lua -> C -> Lua. The outermost C frames might not know anything about Lua (they just use some library that uses Lua as a library). Say you try to take a snapshot of this stack to create a continuation. You probably just want to snapshot the Lua -> C -> Lua part, since that is the portion of the stack representing the execution of the Lua program. Now say all these frames return. Then the main program calls Lua again, through through a slightly different code-path, and now you have C(2) -> Lua. Say the embedded Lua program decides to resume the continuation. Now keep in mind that the C stack is not position-independent. The C stack can contain pointers to the C stack, so when you resume, you need your resumed stack to live at exactly the same address as last time it ran. But what if C(1) and C(2) are not exactly the same size? What if we called one extra function before calling Lua the second time? It is impossible to copy the continuation's C stack back into its original position. So it's impossible to resume the continuation. You could try to snapshot the entire C stack to get around this, including the outermost C frames. But this would be most unexpected for the C program that is using the Lua interpreter. Lua is supposed to just be a regular C library: you call a function, it does things, and then returns. It wouldn't be acceptable that calling a Lua interpreter function like lua_call() backs your entire C program to a previous state just because the embedded Lua program used a fancy feature called continuations! There are many other things that would make this tricky at best to get working, but I think the problem above really tanks the idea completely.
  - sillysaurus3 10y ago
    But what if C(1) and C(2) are not exactly the same size? Say you want to resume continuation K, which has a stack of some size N. The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack. If M < N, recurse until M >= N. You could try to snapshot the entire C stack to get around this, including the outermost C frames. Indeed! This is a solution. It wouldn't be acceptable... I like doing unacceptable things in my programs. It's the best part of programming, really. There are a lot of solid arguments against call/cc. I think the most persuasive argument in favor of call/cc is that you become more powerful. Whatever metric you use to measure power, call/cc will improve it: Smaller code, less time spent writing code, and you can even write algorithms that you otherwise would not be able to. Personally, I want call/cc in order to be able to use choose and fail. It's the ability to write programs that are guaranteed to never call fail(). pg explains it well: "For example, this is a perfectly legitimate nondeterministic algorithm for discovering whether you have a known ancestor called Igor: Function Ig(n) if name(n) = ‘Igor’ return n if parents(n) return Ig(choose(parents(n))) fail The fail operator is used to influence the value returned by choose. If we ever encounter a fail, choose would have chosen incorrectly. By definition choose guesses correctly." Call/cc makes this possible. There are a lot of fun things to do. The last few chapters of On Lisp show some particularly interesting sketches.
- aktau 10y ago
  I'm sure you aware you can implement call/1cc with Lua's coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf. But maybe you want the full power of call/cc :).
- to3m 10y ago
  If you want to actually clone the stack, you're probably stuck. If you want to use this to do something that takes multiple invocations of lua_resume to complete without the calling Lua code being aware, you might be able to use lua_yieldk.
nkurz 10y ago
I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "vpand %[MASK], %[VEC], %[VEC]\n" \ "vpand %[MASK], %[SUM], %[SUM]\n" \ "vpshufb %[VEC], %[SHUF], %[VEC]\n" \ "vpshufb %[SUM], %[SHUF], %[SUM]\n" \ "vpaddb %[VEC], %[SUM], %[SUM]\n" : \ /* rd/wr ymm */ [VEC] "+&x" (vec), \ /* write ymm */ [SUM] "=&x" (sum) : \ /* read ymm */ [MASK] "x" (mask), \ /* read ymm */ [SHUF] "x" (shuf)) 1) Try to use the %[symbolic] syntax rather than %[n] numeric. It's slightly longer to write, but usually clearer to read. Use upper case for the symbolic name. Put your inputs one per line, with a preceding comment. 2) If you are using the same assembly more than once in your program, declare your assembly within a #define macro, then use the macro in your code. 3) Use "__asm volatile". Declaring "volatile" is not required, but once you are writing inline assembly you usually know more than the compiler about where the block should go. 5) If you have multiple lines of assembly and output registers, you are almost always safer to use "+&" and "=&" for your constraint rather than just "+" or "=". Search for "early clobber" for details. 6) Strongly prefer single type constraints. The more flexibility you give the compiler, the more likely it will defeat your efforts at optimization. Use explicit memory addressing modes rather than "m". The modifier "c" is needed for the offset. #define ASM_VEC_LOAD_OFFSET_MEM(off, mem, vec) \ __asm volatile ("vmovdqu %c[OFF](%[MEM]), %[VEC]\n" : \ /* destination */ [VEC] "=x" (vec) : \ /* byte offset */ [OFF] "i" (off), \ /* mem address */ [MEM] "r" (mem)) 7) The register constraints for vectors are tricky, because the "x" constraint is used for both XMM and YMM vectors. There is no way to specify that one wants only one or the other. This sort of makes sense, since in hardware they share the same register. You can use the "q" modifier when you need to specify XMM syntax in the output when you need both forms of the same vector.
ndesaulniers 10y ago
Is it ever the case that inline assembly is required over separate object sources just in assembly? I would have thought it would be preferred to not use inline assembly, and simply link in object files of what you need. It would seem simpler syntax-wise, too. Why prefer inline assembly?
- cyphar 10y ago
  There's several macros in the kernel which contain inline assembly, and you can't use code written in assembly because it would require using the stack to call the function (the case I'm thinking of is the switch_to macro which switches between tasks in the kernel).
- rwmj 10y ago
  One reason is that you just want to call a single instruction, and the overhead of making a function call to another file would be too much. Picking an example from the Linux kernel pretty much at random: #define mb() asm volatile("mfence":::"memory") #define rmb() asm volatile("lfence":::"memory") #define wmb() asm volatile("sfence" ::: "memory") Those are memory barriers, so they essentially must be inline (they'd be too slow and possibly even change their meaning if they were located in a separate source file and you had to call them).
Ameo 10y ago
Having lived my development life so far removed from the actual physical CPU/memory, thinking about implementing this kind of low-level stuff into actual code is mind-boggling to me.
TwoBit 10y ago
GCC inline assembly is one of the most terrible things I've ever had to work with. Somebody seriously need to redesign it or replace it. Aside from that,a decent reference manual for the existing version would be welcome.
- AndyKelley 10y ago
  I'm working on a new language that has inline assembly and I pretty much just copied GCC's syntax[1]. Do you have any specific suggestions on how to do better? [1]: https://github.com/andrewrk/zig/blob/master/std/linux_x86_64.zig#L60 https://github.com/andrewrk/zig/blob/master/std/linux_x86_64...

158 points by 0xAX 10y ago

qu tal

I'm trying to add call/cc to node, or to lua. Recap: call/cc is the ability to save the current state of a running thread, then revert to that state at a later point in time. In other words, at any point in your program, you can say "Save the current stack." It's saved as a function. Later, whenever you call that function, the current stack is thrown out, and replaced with the saved stack. This is very useful for a number of reasons. It's also a very rare feature to have in your language. Neither node nor lua has support for this. The closest I've found is a Lua extension which adds coroutine.clone(). In principle, this is the solution. In practice, it has a number of limitations, such as restrictions on when you're allowed to call coroutine.clone(). (For example, if your stack looks like Lua -> C -> Lua, then it won't work.) I tried to channel my inner Mike Pall and solve this problem once and for all, but I'm not Mike Pall, and this is really hard. I was hoping you might know of any possible solution which is (a) practical, (b) cross-platform, and (c) works in all cases. Why post this here? Because this post happens to attract exactly the kind of people that might know a way forward. There must be a way. Apologies for the off-topic comment.

loeg 10y ago
getcontext(3) / setcontext(3). Not standard, but exists in both Linux and FreeBSD.
kenOfYugen 10y ago
James Long is currently playing with call/cc in JavaScript [1]. He mentioned a paper titled "Exceptional Continuations in JavaScript" [2], that describes the method he used in his implementation. Maybe you should get in touch? [1] https://twitter.com/jlongster/status/726259468405751808 https://twitter.com/jlongster/status/726259468405751808 [2] http://www.schemeworkshop.org/2007/procPaper4.pdf http://www.schemeworkshop.org/2007/procPaper4.pdf
sitkack 10y ago
I assume you have read http://okmij.org/ftp/continuations/against-callcc.html http://okmij.org/ftp/continuations/against-callcc.html
haberman 10y ago
> if your stack looks like Lua -> C -> Lua, then it won't work. I don't think you can safely solve this in the general case. There is a key problem I don't think you can work around. Say your stack looks like C(1) -> Lua -> C -> Lua. The outermost C frames might not know anything about Lua (they just use some library that uses Lua as a library). Say you try to take a snapshot of this stack to create a continuation. You probably just want to snapshot the Lua -> C -> Lua part, since that is the portion of the stack representing the execution of the Lua program. Now say all these frames return. Then the main program calls Lua again, through through a slightly different code-path, and now you have C(2) -> Lua. Say the embedded Lua program decides to resume the continuation. Now keep in mind that the C stack is not position-independent. The C stack can contain pointers to the C stack, so when you resume, you need your resumed stack to live at exactly the same address as last time it ran. But what if C(1) and C(2) are not exactly the same size? What if we called one extra function before calling Lua the second time? It is impossible to copy the continuation's C stack back into its original position. So it's impossible to resume the continuation. You could try to snapshot the entire C stack to get around this, including the outermost C frames. But this would be most unexpected for the C program that is using the Lua interpreter. Lua is supposed to just be a regular C library: you call a function, it does things, and then returns. It wouldn't be acceptable that calling a Lua interpreter function like lua_call() backs your entire C program to a previous state just because the embedded Lua program used a fancy feature called continuations! There are many other things that would make this tricky at best to get working, but I think the problem above really tanks the idea completely.
- sillysaurus3 10y ago
  But what if C(1) and C(2) are not exactly the same size? Say you want to resume continuation K, which has a stack of some size N. The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack. If M < N, recurse until M >= N. You could try to snapshot the entire C stack to get around this, including the outermost C frames. Indeed! This is a solution. It wouldn't be acceptable... I like doing unacceptable things in my programs. It's the best part of programming, really. There are a lot of solid arguments against call/cc. I think the most persuasive argument in favor of call/cc is that you become more powerful. Whatever metric you use to measure power, call/cc will improve it: Smaller code, less time spent writing code, and you can even write algorithms that you otherwise would not be able to. Personally, I want call/cc in order to be able to use choose and fail. It's the ability to write programs that are guaranteed to never call fail(). pg explains it well: "For example, this is a perfectly legitimate nondeterministic algorithm for discovering whether you have a known ancestor called Igor: Function Ig(n) if name(n) = ‘Igor’ return n if parents(n) return Ig(choose(parents(n))) fail The fail operator is used to influence the value returned by choose. If we ever encounter a fail, choose would have chosen incorrectly. By definition choose guesses correctly." Call/cc makes this possible. There are a lot of fun things to do. The last few chapters of On Lisp show some particularly interesting sketches.
aktau 10y ago
I'm sure you aware you can implement call/1cc with Lua's coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf. But maybe you want the full power of call/cc :).
to3m 10y ago
If you want to actually clone the stack, you're probably stuck. If you want to use this to do something that takes multiple invocations of lua_resume to complete without the calling Lua code being aware, you might be able to use lua_yieldk.

nkurz 10y ago

I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "vpand %[MASK], %[VEC], %[VEC]\n" \ "vpand %[MASK], %[SUM], %[SUM]\n" \ "vpshufb %[VEC], %[SHUF], %[VEC]\n" \ "vpshufb %[SUM], %[SHUF], %[SUM]\n" \ "vpaddb %[VEC], %[SUM], %[SUM]\n" : \ /* rd/wr ymm */ [VEC] "+&x" (vec), \ /* write ymm */ [SUM] "=&x" (sum) : \ /* read ymm */ [MASK] "x" (mask), \ /* read ymm */ [SHUF] "x" (shuf)) 1) Try to use the %[symbolic] syntax rather than %[n] numeric. It's slightly longer to write, but usually clearer to read. Use upper case for the symbolic name. Put your inputs one per line, with a preceding comment. 2) If you are using the same assembly more than once in your program, declare your assembly within a #define macro, then use the macro in your code. 3) Use "__asm volatile". Declaring "volatile" is not required, but once you are writing inline assembly you usually know more than the compiler about where the block should go. 5) If you have multiple lines of assembly and output registers, you are almost always safer to use "+&" and "=&" for your constraint rather than just "+" or "=". Search for "early clobber" for details. 6) Strongly prefer single type constraints. The more flexibility you give the compiler, the more likely it will defeat your efforts at optimization. Use explicit memory addressing modes rather than "m". The modifier "c" is needed for the offset. #define ASM_VEC_LOAD_OFFSET_MEM(off, mem, vec) \ __asm volatile ("vmovdqu %c[OFF](%[MEM]), %[VEC]\n" : \ /* destination */ [VEC] "=x" (vec) : \ /* byte offset */ [OFF] "i" (off), \ /* mem address */ [MEM] "r" (mem)) 7) The register constraints for vectors are tricky, because the "x" constraint is used for both XMM and YMM vectors. There is no way to specify that one wants only one or the other. This sort of makes sense, since in hardware they share the same register. You can use the "q" modifier when you need to specify XMM syntax in the output when you need both forms of the same vector.

ndesaulniers 10y ago

Is it ever the case that inline assembly is required over separate object sources just in assembly? I would have thought it would be preferred to not use inline assembly, and simply link in object files of what you need. It would seem simpler syntax-wise, too. Why prefer inline assembly?

cyphar 10y ago
There's several macros in the kernel which contain inline assembly, and you can't use code written in assembly because it would require using the stack to call the function (the case I'm thinking of is the switch_to macro which switches between tasks in the kernel).
rwmj 10y ago
One reason is that you just want to call a single instruction, and the overhead of making a function call to another file would be too much. Picking an example from the Linux kernel pretty much at random: #define mb() asm volatile("mfence":::"memory") #define rmb() asm volatile("lfence":::"memory") #define wmb() asm volatile("sfence" ::: "memory") Those are memory barriers, so they essentially must be inline (they'd be too slow and possibly even change their meaning if they were located in a separate source file and you had to call them).

Ameo 10y ago

Having lived my development life so far removed from the actual physical CPU/memory, thinking about implementing this kind of low-level stuff into actual code is mind-boggling to me.

TwoBit 10y ago

GCC inline assembly is one of the most terrible things I've ever had to work with. Somebody seriously need to redesign it or replace it. Aside from that,a decent reference manual for the existing version would be welcome.

AndyKelley 10y ago
I'm working on a new language that has inline assembly and I pretty much just copied GCC's syntax[1]. Do you have any specific suggestions on how to do better? [1]: https://github.com/andrewrk/zig/blob/master/std/linux_x86_64.zig#L60 https://github.com/andrewrk/zig/blob/master/std/linux_x86_64...