6 ms·

The Design of Scalar AES Instruction Set Extensions for RISC-V

58 points by gbrown_ 6y ago

BooneJS 6y ago
What’s the strategy for operating systems, compilers, and/or language runtimes to figure out what a RISC-V chip supports? It used to be one thing checking which SIMD units an x86 had, but the nature of an open source processor lends itself to a near infinite listing of /proc/cpuinfo flags.
- microcolonel 6y ago
  > It used to be one thing checking which SIMD units an x86 had, but the nature of an open source processor lends itself to a near infinite listing of /proc/cpuinfo flags. I mean, x86 sets a very high bar for the sheer number of feature flags. Most ISA extensions of interest to compilers are standardized with the RISC-V Foundation †. The mechanism is similar to other chips, and the situation so far seems to be about the same, except a couple orders of magnitude difference in the current number of flags. † Seems it's now RISC-V International
  - fuoqi 6y ago
    So is there a CPUID-like instruction in the base RISC-V instruction set? After a cursory search I couldn't find anything like it. If there is indeed no such instruction, it will be a real shame. Why would you not include it into a such extensible ISA?
    - microcolonel 6y ago
      Your system's device tree describes the CPU to the kernel. The riscv,isa string contains the list of extensions in the standard format (a string of single-character standard extensions, and Z-delimited extensions). To clarify I did not mean that this information was accessed through specialized CPU instructions directly, but that it is available through cpuinfo on Linux and such like usual. Here's an example device tree for the HiFive Unleashed board, which describes the embedded controller as rv64imac, and the application processor cores as rv64imafdc (same as the embedded controller, but with floats and doubles): https://github.com/riscv/riscv-device-tree-doc/blob/master/examples/sifive-hifive_unleashed-microsemi.dts https://github.com/riscv/riscv-device-tree-doc/blob/master/e... If your system is application-specific enough, you won't even bother with that. You'll know what extensions your SoC supports when you make your purchasing decision, and you'll know when you compile your software.
      - formerly_proven 6y ago
        How does the OS <discover/gain access to/build/enumerate> the device tree? Edit: Apparently the device tree is handled by the firmware (UEFI?), so that a RISC-V OS asks the firmware to provide the device tree and I suppose if it ever gets to desktops, it'd be firmware's job to figure out what CPU is plugged into the board. The current state seems to only cater to integrated systems, though?
        microcolonel 6y ago
        The firmware or the bootloader leaves it in memory somewhere. Re: the added question on "integrated systems": your VM hypervisor will map a device tree for VM guests as well, this is how QEMU and other hypervisors expose virtio devices to guests as well.
        formerly_proven 6y ago
        Yeah, but that sort of punts the question of "how does the [firmware] code figure out what CPU is being used", unless that's backed into the firmware at build time.
        monocasa 6y ago
        Yep, it's baked into the firmware somehow. Sometimes it'll actually be linked in, sometimes the firmware knows where in flash or whatever to grab it from before loading the kernel, sometimes the firmware knows how to interrogate hardware and generate a new one. Sometimes it's a combo of all three.
        cmrx64 6y ago
        yeah, it usually is, that's how those device trees work. it's generally bundled with the "bootloader" (chain loader component of the firmware). you can even bake them into your kernel if you want, i believe. RISC-V is a processor ISA, not a platform spec. you may be interested in the SBI: https://github.com/riscv/riscv-sbi-doc/blob/v0.2.0/riscv-sbi.adoc https://github.com/riscv/riscv-sbi-doc/blob/v0.2.0/riscv-sbi... the details of how all this stuff works at a human-collaboration level has changed a bit since 1993. there's a higher level of collaboration expected. vs intel and ms bossing people around. edit: you may also be interested in https://doc.coreboot.org/arch/riscv/index.html https://doc.coreboot.org/arch/riscv/index.html and https://lkml.org/lkml/2020/2/25/1209 https://lkml.org/lkml/2020/2/25/1209 and https://lists.gnu.org/archive/html/grub-devel/2019-02/msg00021.html https://lists.gnu.org/archive/html/grub-devel/2019-02/msg000... not exactly "desktop" yet, but hopefully you can see how that might look, given the existing linux infrastructure :)
    - loeg 6y ago
      > So is there a CPUID-like instruction in the base RISC-V instruction set? Yes. > After a cursory search I couldn't find anything like it. This was the first google result for "riscv cpuid feature instruction" for me (RISC-V Instruction Set Manual v1.7): > The mcpuid register is an XLEN-bit read-only register containing information regarding the capabilities of the CPU implementation. This register must be readable in any implementation
      - microcolonel 6y ago
        Oh right, I tried looking for it and it's not in the current specification AFAIK. What there is, though, is the misa CSR, which accomplishes something similar described in 3.1.1 of the Privileged spec. The misa register is a bitfield of the supported standard extensions. Not sure but I think it's not readable in U-mode, or it's undefined.
      - fuoqi 6y ago
        Thank you! I was looking at the Volume 1 only. But IIUC it will not be accessible at user-level, so capability detection will be significantly less convenient for cross-platform library authors compared to x86.
        Narishma 6y ago
        Why does it need to be accessible from user-space? Applications can just ask the OS what extensions are available before using them.
        fuoqi 6y ago
        It does not need to be, but it makes things significantly easier for library authors. Asking OS is a more involved process than calling an instruction (for starters you should learn which OS your code is running on) and you may not have OS in the first place (e.g. for bare-metal programming).
        roca 6y ago
- jepler 6y ago
  > The misa CSR is a WARL read-write register reporting the ISA supported by the hart [hart is a hardware thread] - from the Privileged Architecture manual However, I didn't see how a nonstandard extension such as this would be represented; this is concerned with representing up to 26 or so extensions, the ones with single letters assigned to them.
- fluffything 6y ago
  > What’s the strategy for operating systems, compilers, and/or language runtimes to figure out what a RISC-V chip supports? Same as for x86, Power, ARM, MIPS, systemz, sparc, ... ISAs: there is a flag register that the OS can query to test whether the hardware supports something. I only know one ISA that works in a completely different way (WebAssembly), by requiring the user to attempt to perform an operation, and if that faults, then the operation is not supported. The reason WASM can do this is because it is a virtual ISA. This approach does not work well for real hardware because it makes instruction decoders larger and slower, since it prevents them from assuming that they will only be fed instructions they do know.
  - orra 6y ago
    You sound knowledgeable, but this I don't understand: > This approach does not work well for real hardware because it makes instruction decoders larger and slower, since it prevents them from assuming that they will only be fed instructions they do know. But what if you fail to do the runtime checks? And for example just feed an SSE4 binary/instructions to a processor that only supports SSE3? Then won't it segfault?
    - fluffything 6y ago
      Hardware undefined behavior. The hardware can do anything. That includes trapping on an illegal instruction or something, but there is no guarantee that some CPU that was designed and built before SSE4 existed will do anything meaningful when fed with machine code that it was never intended to see. You are basically hopping for the instruction decoder to be "really good", and not "really fast". Eg. suppose that there is only one instruction in SSE3 which has the 7th bit set. A fast instruction decoder tests that bit, and if its true, it knows exactly what instruction that is. Years later, SSE4 is designed and implemented, and it adds another instruction that also has that bit set. You are required to check whether the CPU supports SSE4, and the SSE3-only CPU will tell you that it does not. If you then go ahead and feed it a SSE4 instruction, the CPU can do really anything, including executing some other completely different instruction.
      - 6y ago
microcolonel 6y ago
I'm interested in if there's a simple design for a ChaCha/Poly1305 accelerating ISA extension for RISC-V (outside the general crypto extension, not sure even as a member of that where it is going). I feel like it is a lot simpler, if for no other reason than there being effectively a single mode for the ChaCha primitive rather than three or more. The whole operation is composed of bitwise rotations and adders that can be arranged in a static network, and (as far as I know) is more or less not a source of timing sidechannel information one way or another. Maybe I could try banging my head against the XCrypto repository this weekend.
- brandmeyer 6y ago
  ARX ciphers suffer somewhat on vanilla RISC-V due to the lack of native rotations. You have to synthesize rotations from shifting and logical ops. Prime field algorithms suffer somewhat on vanilla RISC-V due to the lack of good bignum support. For example, there is no add-with-carry, nor a convenient way to get the carry-out at a low level. You have to use the set-if-less-than instruction after an addition to separately compute the carry bit.
  - a1369209993 6y ago
    > For example, there is no add-with-carry, nor a convenient way to get the carry-out at a low level. IIUC, you're supposed to break the bignum up into (say) 56-bit chunks, and use the upper bits of the register as the carry. I'm sceptical that that works as well as it should for practical bignum applications, though. (I haven't had occasion to try it out.)
    - microcolonel 6y ago
      I think this becomes less terrible the wider your bignum is.
  - dependenttypes 6y ago
    microcolonel was interested for an ISA extension rather than software implementation.
anonymousDan 6y ago
Slightly off topic, but can anyone tell me if the RISCV ISA makes static disassembly easier than x86-64?
- brandmeyer 6y ago
  Some of the operand fields in the 16-bit instructions are positioned in weird places in the instructions, but otherwise the process is pretty mechanical.
- TomVDB 6y ago
  RISC-V instructions are either 32 or 16 bits, and the size of the instruction is determined by 2 bits in a fixed place (the LSBs of the instruction word IIRC.) Much easier than x86-64.
userbinator 6y ago
Making RISC-V not so RISCy... it turns out that complex instructions are actually useful in practice, and ISAs which don't have them will eventually develop them in order to remain competitive.
- zozbot234 6y ago
  RISC itself has nothing to do with the number of instructions. It's about the load-store principle, separating instructions that access memory wrt. those that compute on registers.
  - Someone 6y ago
    It’s hard to define RISC, but separating load and stores from computations is a side effect of the desire to have uniform, low instruction execution times in order to simplify pipelining, not a goal of RISC. AES would be non-RISCy because it won’t execute in a single clock cycle, either stopping the pipeline or necessitating complex logic. Having said that, I don’t think RISC-V implementations are 100% RISC in that respect (is any CPU?)
- segfaultbuserr 6y ago
  My understanding is that the primary motivation of pushing RISC-V is always about creating (or at least attempting to create) an open ISA and hopefully bringing greater transparency to CPU architectures, arguing whether it's RISC, is not an irrelevant issue to many. In a parallel universe, I would be happy to use a "CISC-V" chip if it exists.
- simias 6y ago
  I'm not sure if it's very unRISC-y. CISC is all about these sort-of-generic-but-slightly-high-level methods such as SCASB (find a byte in a string), LOOPD (loop while equal) and all the in-memory operations, prefix instructions etc... All that with a lot of redundancy in the ISA. A RISC CPU will "emulate" this instruction with a couple of more primitive instructions, favoring speed and simplicity. Of course the line is blurry, but to me things like SIMD, floating point or AES are more like "coprocessor" extensions, it's not something that can decently be emulated using a handful of CISC opcodes. Making a quasi-religious point that CISC shouldn't support high-level instructions will doom these CPUs to irrelevance. A CISC CPU is no less CISC if you put in on a board next to a hardware video decoder module for instance, so why should an on-die AES extension be a game changer? The original PlayStation's CPU had a coprocessor dealing with 3D transformations (the part of the pipeline that would be handled by a vertex shader these days) so it actually supported opcodes such as "MVMVA: Multiply vector by matrix and add vector". I don't think anybody would consider that unRISC-y.
cordite 6y ago
Secure constant time primitive computation is important. Outside of symmetric encryption with AES, other primitive operations could be beneficial. Avoiding side channels and valuing small code size can result in some really funky work arounds. For example, using a whole ECDH key exchange in a JavaCard co-processor in order to do EC point calculations. As seen in [1] slide 30. [1]: https://www.blackhat.com/docs/us-17/thursday/us-17-Mavroudis-Opencrypto-Unchaining-The-JavaCard-Ecosystem.pdf https://www.blackhat.com/docs/us-17/thursday/us-17-Mavroudis...

58 points by gbrown_ 6y ago

What’s the strategy for operating systems, compilers, and/or language runtimes to figure out what a RISC-V chip supports? It used to be one thing checking which SIMD units an x86 had, but the nature of an open source processor lends itself to a near infinite listing of /proc/cpuinfo flags.

microcolonel 6y ago
> It used to be one thing checking which SIMD units an x86 had, but the nature of an open source processor lends itself to a near infinite listing of /proc/cpuinfo flags. I mean, x86 sets a very high bar for the sheer number of feature flags. Most ISA extensions of interest to compilers are standardized with the RISC-V Foundation †. The mechanism is similar to other chips, and the situation so far seems to be about the same, except a couple orders of magnitude difference in the current number of flags. † Seems it's now RISC-V International
- fuoqi 6y ago
  So is there a CPUID-like instruction in the base RISC-V instruction set? After a cursory search I couldn't find anything like it. If there is indeed no such instruction, it will be a real shame. Why would you not include it into a such extensible ISA?
  - microcolonel 6y ago
    Your system's device tree describes the CPU to the kernel. The riscv,isa string contains the list of extensions in the standard format (a string of single-character standard extensions, and Z-delimited extensions). To clarify I did not mean that this information was accessed through specialized CPU instructions directly, but that it is available through cpuinfo on Linux and such like usual. Here's an example device tree for the HiFive Unleashed board, which describes the embedded controller as rv64imac, and the application processor cores as rv64imafdc (same as the embedded controller, but with floats and doubles): https://github.com/riscv/riscv-device-tree-doc/blob/master/examples/sifive-hifive_unleashed-microsemi.dts https://github.com/riscv/riscv-device-tree-doc/blob/master/e... If your system is application-specific enough, you won't even bother with that. You'll know what extensions your SoC supports when you make your purchasing decision, and you'll know when you compile your software.
    - formerly_proven 6y ago
      How does the OS <discover/gain access to/build/enumerate> the device tree? Edit: Apparently the device tree is handled by the firmware (UEFI?), so that a RISC-V OS asks the firmware to provide the device tree and I suppose if it ever gets to desktops, it'd be firmware's job to figure out what CPU is plugged into the board. The current state seems to only cater to integrated systems, though?
      - microcolonel 6y ago
        The firmware or the bootloader leaves it in memory somewhere. Re: the added question on "integrated systems": your VM hypervisor will map a device tree for VM guests as well, this is how QEMU and other hypervisors expose virtio devices to guests as well.
        formerly_proven 6y ago
        Yeah, but that sort of punts the question of "how does the [firmware] code figure out what CPU is being used", unless that's backed into the firmware at build time.
        monocasa 6y ago
        Yep, it's baked into the firmware somehow. Sometimes it'll actually be linked in, sometimes the firmware knows where in flash or whatever to grab it from before loading the kernel, sometimes the firmware knows how to interrogate hardware and generate a new one. Sometimes it's a combo of all three.
        cmrx64 6y ago
        yeah, it usually is, that's how those device trees work. it's generally bundled with the "bootloader" (chain loader component of the firmware). you can even bake them into your kernel if you want, i believe. RISC-V is a processor ISA, not a platform spec. you may be interested in the SBI: https://github.com/riscv/riscv-sbi-doc/blob/v0.2.0/riscv-sbi.adoc https://github.com/riscv/riscv-sbi-doc/blob/v0.2.0/riscv-sbi... the details of how all this stuff works at a human-collaboration level has changed a bit since 1993. there's a higher level of collaboration expected. vs intel and ms bossing people around. edit: you may also be interested in https://doc.coreboot.org/arch/riscv/index.html https://doc.coreboot.org/arch/riscv/index.html and https://lkml.org/lkml/2020/2/25/1209 https://lkml.org/lkml/2020/2/25/1209 and https://lists.gnu.org/archive/html/grub-devel/2019-02/msg00021.html https://lists.gnu.org/archive/html/grub-devel/2019-02/msg000... not exactly "desktop" yet, but hopefully you can see how that might look, given the existing linux infrastructure :)
  - loeg 6y ago
    > So is there a CPUID-like instruction in the base RISC-V instruction set? Yes. > After a cursory search I couldn't find anything like it. This was the first google result for "riscv cpuid feature instruction" for me (RISC-V Instruction Set Manual v1.7): > The mcpuid register is an XLEN-bit read-only register containing information regarding the capabilities of the CPU implementation. This register must be readable in any implementation
    - microcolonel 6y ago
      Oh right, I tried looking for it and it's not in the current specification AFAIK. What there is, though, is the misa CSR, which accomplishes something similar described in 3.1.1 of the Privileged spec. The misa register is a bitfield of the supported standard extensions. Not sure but I think it's not readable in U-mode, or it's undefined.
    - fuoqi 6y ago
      Thank you! I was looking at the Volume 1 only. But IIUC it will not be accessible at user-level, so capability detection will be significantly less convenient for cross-platform library authors compared to x86.
      - Narishma 6y ago
        Why does it need to be accessible from user-space? Applications can just ask the OS what extensions are available before using them.
        fuoqi 6y ago
        It does not need to be, but it makes things significantly easier for library authors. Asking OS is a more involved process than calling an instruction (for starters you should learn which OS your code is running on) and you may not have OS in the first place (e.g. for bare-metal programming).
        roca 6y ago
jepler 6y ago
> The misa CSR is a WARL read-write register reporting the ISA supported by the hart [hart is a hardware thread] - from the Privileged Architecture manual However, I didn't see how a nonstandard extension such as this would be represented; this is concerned with representing up to 26 or so extensions, the ones with single letters assigned to them.
fluffything 6y ago
> What’s the strategy for operating systems, compilers, and/or language runtimes to figure out what a RISC-V chip supports? Same as for x86, Power, ARM, MIPS, systemz, sparc, ... ISAs: there is a flag register that the OS can query to test whether the hardware supports something. I only know one ISA that works in a completely different way (WebAssembly), by requiring the user to attempt to perform an operation, and if that faults, then the operation is not supported. The reason WASM can do this is because it is a virtual ISA. This approach does not work well for real hardware because it makes instruction decoders larger and slower, since it prevents them from assuming that they will only be fed instructions they do know.
- orra 6y ago
  You sound knowledgeable, but this I don't understand: > This approach does not work well for real hardware because it makes instruction decoders larger and slower, since it prevents them from assuming that they will only be fed instructions they do know. But what if you fail to do the runtime checks? And for example just feed an SSE4 binary/instructions to a processor that only supports SSE3? Then won't it segfault?
  - fluffything 6y ago
    Hardware undefined behavior. The hardware can do anything. That includes trapping on an illegal instruction or something, but there is no guarantee that some CPU that was designed and built before SSE4 existed will do anything meaningful when fed with machine code that it was never intended to see. You are basically hopping for the instruction decoder to be "really good", and not "really fast". Eg. suppose that there is only one instruction in SSE3 which has the 7th bit set. A fast instruction decoder tests that bit, and if its true, it knows exactly what instruction that is. Years later, SSE4 is designed and implemented, and it adds another instruction that also has that bit set. You are required to check whether the CPU supports SSE4, and the SSE3-only CPU will tell you that it does not. If you then go ahead and feed it a SSE4 instruction, the CPU can do really anything, including executing some other completely different instruction.
    - 6y ago

microcolonel 6y ago

I'm interested in if there's a simple design for a ChaCha/Poly1305 accelerating ISA extension for RISC-V (outside the general crypto extension, not sure even as a member of that where it is going). I feel like it is a lot simpler, if for no other reason than there being effectively a single mode for the ChaCha primitive rather than three or more. The whole operation is composed of bitwise rotations and adders that can be arranged in a static network, and (as far as I know) is more or less not a source of timing sidechannel information one way or another. Maybe I could try banging my head against the XCrypto repository this weekend.

brandmeyer 6y ago
ARX ciphers suffer somewhat on vanilla RISC-V due to the lack of native rotations. You have to synthesize rotations from shifting and logical ops. Prime field algorithms suffer somewhat on vanilla RISC-V due to the lack of good bignum support. For example, there is no add-with-carry, nor a convenient way to get the carry-out at a low level. You have to use the set-if-less-than instruction after an addition to separately compute the carry bit.
- a1369209993 6y ago
  > For example, there is no add-with-carry, nor a convenient way to get the carry-out at a low level. IIUC, you're supposed to break the bignum up into (say) 56-bit chunks, and use the upper bits of the register as the carry. I'm sceptical that that works as well as it should for practical bignum applications, though. (I haven't had occasion to try it out.)
  - microcolonel 6y ago
    I think this becomes less terrible the wider your bignum is.
- dependenttypes 6y ago
  microcolonel was interested for an ISA extension rather than software implementation.

anonymousDan 6y ago

Slightly off topic, but can anyone tell me if the RISCV ISA makes static disassembly easier than x86-64?

brandmeyer 6y ago
Some of the operand fields in the 16-bit instructions are positioned in weird places in the instructions, but otherwise the process is pretty mechanical.
TomVDB 6y ago
RISC-V instructions are either 32 or 16 bits, and the size of the instruction is determined by 2 bits in a fixed place (the LSBs of the instruction word IIRC.) Much easier than x86-64.

userbinator 6y ago

Making RISC-V not so RISCy... it turns out that complex instructions are actually useful in practice, and ISAs which don't have them will eventually develop them in order to remain competitive.

zozbot234 6y ago
RISC itself has nothing to do with the number of instructions. It's about the load-store principle, separating instructions that access memory wrt. those that compute on registers.
- Someone 6y ago
  It’s hard to define RISC, but separating load and stores from computations is a side effect of the desire to have uniform, low instruction execution times in order to simplify pipelining, not a goal of RISC. AES would be non-RISCy because it won’t execute in a single clock cycle, either stopping the pipeline or necessitating complex logic. Having said that, I don’t think RISC-V implementations are 100% RISC in that respect (is any CPU?)
segfaultbuserr 6y ago
My understanding is that the primary motivation of pushing RISC-V is always about creating (or at least attempting to create) an open ISA and hopefully bringing greater transparency to CPU architectures, arguing whether it's RISC, is not an irrelevant issue to many. In a parallel universe, I would be happy to use a "CISC-V" chip if it exists.
simias 6y ago
I'm not sure if it's very unRISC-y. CISC is all about these sort-of-generic-but-slightly-high-level methods such as SCASB (find a byte in a string), LOOPD (loop while equal) and all the in-memory operations, prefix instructions etc... All that with a lot of redundancy in the ISA. A RISC CPU will "emulate" this instruction with a couple of more primitive instructions, favoring speed and simplicity. Of course the line is blurry, but to me things like SIMD, floating point or AES are more like "coprocessor" extensions, it's not something that can decently be emulated using a handful of CISC opcodes. Making a quasi-religious point that CISC shouldn't support high-level instructions will doom these CPUs to irrelevance. A CISC CPU is no less CISC if you put in on a board next to a hardware video decoder module for instance, so why should an on-die AES extension be a game changer? The original PlayStation's CPU had a coprocessor dealing with 3D transformations (the part of the pipeline that would be handled by a vertex shader these days) so it actually supported opcodes such as "MVMVA: Multiply vector by matrix and add vector". I don't think anybody would consider that unRISC-y.

cordite 6y ago

Secure constant time primitive computation is important. Outside of symmetric encryption with AES, other primitive operations could be beneficial. Avoiding side channels and valuing small code size can result in some really funky work arounds. For example, using a whole ECDH key exchange in a JavaCard co-processor in order to do EC point calculations. As seen in [1] slide 30. [1]: https://www.blackhat.com/docs/us-17/thursday/us-17-Mavroudis-Opencrypto-Unchaining-The-JavaCard-Ecosystem.pdf https://www.blackhat.com/docs/us-17/thursday/us-17-Mavroudis...