Crusoe Exposed:
Reverse Engineering the Transmeta TM5xxx Architecture II

Introduction

This report is the second installment in the Crusoe Exposed series. It describes in detail the instruction set, binary encodings, functional unit specifics and more for the Transmeta TM5xxx microprocessors. Source code for a full disassembler and analysis toolset is provided. The first part can be found here.

Based on the response to the first report, I have decided to release substantially more details of my reverse engineering effort here. Fortunately, high level technical people at Transmeta have indicated that they have no legal intent to prevent the release of this information, but obviously cannot confirm nor deny its accuracy.

This is not the final report in this series, however hopefully the information provided here will be enough for other interested parties with more time on their hands to carry on my research into the dynamic behavior of CMS and the TM5xxx architecture while running x86 code.

As with all reports in this series, absolutely no proprietary trade secrets were used in this research. All the information presented here is strictly the result of clean room reverse engineering

This report is organized into three main sections. The first focuses on describing the TM5xxx architecture and microarchitecture, and the second is primarily observations, notes and critical analysis of Transmeta's work in the field of binary translation and dynamic optimization. The last section is the appendix, which includes source code for disassembling and analyzing CMS memory images, plus opcode maps, statistics and more.

Detailed Analysis of the TM5800 Microarchitecture and Instruction Set:
CMS Boot Procedure and Memory Map

At power up, the processor begins executing boot code from an internal ROM. After doing basic POST operations, the OEM configuration data (part of the flash ROM) is read via the processor's 4-pin flash ROM serial interface. This data tells the processor how to configure the system RAM and prepare for copying the main CMS image.

After the on-chip DRAM controller and caches are configured, the main CMS image in flash ROM is streamed into the core, decompressed and copied out to RAM. It will reside at physical address (total system RAM - 16MB). At this point, control is transferred to the main CMS image for further boot.

There are actually two copies of the CMS image in flash ROM. This is a failsafe mechanism: should the first copy fail to boot the processor (for instance, because it was corrupted by a power failure during an update), the second copy, called a "recovery ROM", is used on the next reboot. It is assumed that if CMS fails to set some internal watchdog register within a few million cycles after bootup, the primary ROM is assumed to be corrupted so the recovery ROM is used.

The decompressed CMS code image is actually mapped to offset 0x8e000 in CMS DRAM space, and takes up around 1.7 MB:

      0x00000 to 0x8e000: occupied by CMS loader, etc. (not in CMS image)
      0x8e000 to 0x1823f0: 1.0 MB CMS image
      0x1823f0 to 0x1b2261: 196 KB CMS data
      Above 0x1b2261 (~1.7 MB - 16 MB): uninitialized data, stack, heap and translation cache      
    

CMS Image Format and Modification Techniques

The main CMS flash ROM image format, as found in cms4.4.03raptor.cru, consists of the following parts:

      Header (192 bytes) with version information and other data
      ROM image itself, compressed with the standard gzip deflate algorithm
      DSA signature applied by Transmeta
    

The trailing signature is used to ensure only authenticated CMS updates are accepted by the update mechanism (accessible from x86 mode via various MSRs) before being written to the flash ROM. The DSA public key is contained in CMS around address 0x182654, while the private key is known only to Transmeta. This makes it impossible to load unsigned updates, at least if the normal update mechanism is used.

However, there is a back door: if we can alter the running CMS image in RAM, we can simply overwrite the public key with our own, or just patch the signature checking code to skip the verification step. Since the CMS private RAM is not accessible via x86 generated physical addresses, there are two methods of accessing it:

Using dedicated hardware (i.e., DRAM analyzer) or specialized system board with front side bus redirection circuitry. This is obviously not practical without physical access to the machine and appropriate hardware equipment.

Certain common peripheral chipsets (e.g., ethernet DMA controllers or IDE controllers) can be tricked into DMAing directly to/from CMS physical memory due to implementation bugs in the chipsets and the TM58xx processor. Again, this is not practical or possible on all Crusoe-based boards. It can also be very dangerous to wildly redirect DMAs to arbitrary bus addresses, unless you're an experienced hardware hacker.

Fortunately for Transmeta and its end users, this backdoor is difficult to exploit without the consent of the user, since it does require both x86 kernel level access and in some cases physical access to the machine. However, if you are experienced enough to be reading this, such limitations are unlikely to be a problem.

Processor Core Pipeline

The TM5xxx pipeline is mostly revealed in [4], but here are further notes:

CrusoeReport-Part2-fig1.gif - 10937 Bytes
Figure 1 - Crusoe Pipeline Diagram

The top row of the diagram indicates the pipeline for an ALU instruction, with the other rows representing the two other types of logical units. The pipeline is a fairly typical RISC design:

      Fetch0: The first 64 bits of a 64-bit or 128-bit bundle are fetched
      Fetch1: The second 64 bits are fetched (for 128-bit bundles only)
      Regs:   Read source registers and decode/disperse instructions>
      ALU:    Execute single cycle operations in ALU0 and ALU1
      Except: Complete two-cycle ALU0/ALU1 ops and detect exceptions
      Cache0: Initiate L1 data cache access based on register address
      Cache1: Complete L1 data cache access, TLB access and alias checks
      Write:  Write results back to GPRs or store buffer
      Commit: Optionally latch the lower 48 GPRs into the shadow registers
    

Register Set

The processor has 64 GPRs, with the following specialized semantics:

The lower 48 of these GPRs are backed by shadowed GPRs: whenever a bundle has its commit bit set, the Commit stage latches the current values of the GPRs into the 'known good' shadow GPRs.

The processor also includes 32 80-bit floating point registers and 16 FP shadow registers; these are not discussed in this report.

There are also a wide variety of special purpose registers (SPRs), including the condition codes, profiling registers, power control settings and so on.

Instruction Encoding

Instructions are encoded in little endian byte and word order as shown in the following diagram:

CrusoeReport-Part2-fig2.gif - 15636 Bytes
Figure 2 - Instruction Encoding for Crusoe

Instructions in both the ALU0 and ALU1 slots may have an 8-bit signed immediate instead of register rb; the ALU1 slot may optionally use a 32-bit immediate, but only in appropriate bundle types. All instructions (except branches) have a 9-bit opcode field. All opcodes share a common mapping into this 9-bit space, even though not all instructions can execute on all functional units.

The hardware is designed to interlock all operations through scoreboarding, however as described in the observations section, design flaws sometimes prevent the microprocessor from taking full advantage of these features.

The ALU0|imm32 and ALU0|ALU1 bundle types share the same format code (10) but the ALU1 slot is interpreted as an imm32 depending on the opcode:

11xxxx011: 32-bit immediate in place of ALU1

All others: execute ALU1 as instruction

If the 11xxxx011 pattern appears in an ALU1 slot, an 8-bit immediate is used instead. It is not clear why this encoding is sometimes used instead of the normal 8-bit immediate form.

ALUs

Two ALUs are provided in Crusoe. It appears that ALU1 executes a superset of the operations available on ALU0. In particular, shifts are available only on ALU1 (a rather bizarre decision given the amount of bit manipulation CMS does). It is unknown if ALU0 also implements simpler bit extraction operations. Figure 3 below shows the formatting for instructions to the two ALUs.

CrusoeReport-Part2-fig3.gif - 16087 Bytes
Figure 3 - Crusoe ALU Instruction Format

Both ALUs may have an 8-bit signed immediate instead of register rb; this is determined by the opcode (see the opcode map). The ALU0 slot may optionally use a 32-bit immediate, but only in appropriate bundle types, and only when the opcode matches the pattern 11xxxx011.

Condition codes exactly mirror the x86 semantics, right down to their encodings (see the branch unit section). Any instruction in either ALU0 or ALU1 can optionally latch the resulting condition codes if specified by the opcode (see opcode map). However, obviously only one of the two ALU0|ALU1 slots per bundle can write the condition codes in a single cycle. Condition codes cannot be generated on the same cycle as a dependent branch (unlike as in IA-64), but must be ready the cycle before.

There appears to be a facility for combining the existing condition codes with a comparison result, a la the PowerPC crand/cror instructions. This may be used via the cmpand (opcode 000100000) instruction et al.

The ALU1 slot is also used for all floating point and MMX operations, as indicated by ALU1's type select bits being something other than '00'. Since FP and MMX are obviously not used by the core CMS code, little is known about the FP/MMX unit at this point.

Load/Store Unit (LSU)

The single load/store unit performs all loads and stores, alias operations and various other memory related tasks. The instruction format is shown below in Figure 4.

CrusoeReport-Part2-fig4.gif - 13953 Bytes
Figure 4 - Crusoe Load/Store Unit Instruction Format

All LSU operations take a fully calculated address in register ra; as with most VLIW architectures, no ra+offset or ra+rb addressing modes are provided.

Two kinds of loads and stores are possible: operations on physical CMS space addresses (as used in CMS itself), and operations as user code sees memory; i.e., addresses are translated by the TLB and can never access the protected CMS space.

The processor has two special 8KB SRAMs: the local program memory (LPM) and local data memory (LDM). The LPM holds often executed assist code for x86 page table lookups, alignment fixups, low level exception handling, interrupt handling, etc. This avoids having to bring such critical code into the L1 instruction cache on demand. The LDM contains data used by the LPM functions; i.e., copies of key x86 MSRs, native code stack, etc.

Branch Unit

Branches (both conditional and unconditional) within CMS use a 23 bit absolute target address aligned to a 64-bit boundary (i.e., abstarget is shifted left 3 bits). Interestingly, with 23 bits, 1 << (23+3) only allows up to 64 MB to be dedicated to CMS; this is probably one reason why larger translation caches have not been used.

CrusoeReport-Part2-fig5.gif - 18436 Bytes
Figure 5 - Crusoe Branch Instruction Format

It appears that the CMS address space is the only region from which code can be executed; the processor is physically incapable of executing code directly from user space. This makes sense considering that all x86 code must be translated (and thus copied to CMS space) before native execution.

Conditional branches use the exact same condition code set (cc bits) as the x86 encoding in jump instructions (see the Intel manuals). Unconditional branches can optionally write the return address to the %link register (%r58) if the L bit (bit 0 of the cc field) is set.

Indirect branches occur through a general purpose register. It appears that special instructions are provided to prepare for an indirect branch when the target address is known in advance; this avoids the three-cycle branch penalty. In addition, special instructions may provide a branch with link functionality.

Observations, Notes and Critical Analysis of Transmeta's Work

Performance Issues

The scarcity of ALUs (only 2 are provided) appears to be a major impediment to the performance of both CMS itself and the generated code. Since all address generation is performed in these ALUs prior to forwarding the final virtual address to the LSU, the TM5xxx is at a clear disadvantage to the P6 and K7 microarchitectures (which have dedicated AGUs for each LSU). This appears to have been remedied in the just released TM8000 design, however.

Transmeta clearly also made major performance sacrifices in exchange for low power. For instance, as described in the ALU section, apparently only ALU1 can do shift operations. This can seriously impact some x86 code, not to mention the CMS translation code itself.

The instruction encoding also incurs a large number of wasted no-op slots: out of the roughly 231313 instructions in the CMS version examined, 70363 (over 30%) were nops. This could easily be remedied by using a stop bit based format as in TI DSPs or IA-64; I suspect the TM8000 has switched to such a format.

Programming Model

Most of the non time critical parts of CMS itself appear to be written in C, and compiled with a version of gcc and binutils hacked to generate TM5xxx code. This is evident from the relatively poor scheduling of certain code sequences, compared to what a good trace scheduler or programmer could do.

The released CMS image also appears to contain external debugger support, possibly accessible through the JTAG port. It is known that major hardware vendors have been given the appropriate debugging kits, so it may be possible to activate the CMS debug code externally.

Hardware Oddities

Even though the processor is fully interlocked via register operand score-boarding, there are many instances where delay slots were present in the disassembled code even though they are not strictly necessary nor present in other places. This is most likely the result of hardware bugs in the pipeline logic, which Transmeta has in fact admitted are masked by CMS in shipping hardware.

There are also a number of cases where instructions which could normally be paired together are not scheduled this way. It has been documented that CMS uses a different instruction mix at different clock speeds such that none of the critical circuit timing paths used by a given bundle will exceed the clock period.

The processor is typically clocked at the maximum frequency while running code within CMS itself, since this is infrequent yet obviously must be done as fast as possible. However, this does appear to limit the valid instruction combinations found in the CMS image to a subset of those possible when running at slower clock speeds.

Porting OS Kernels and Applications to the Underlying Hardware

Many insiders, including Linus Torvalds himself, have stated that it would be impossible to port an operating system kernel like Linux to the bare TM5xxx hardware, let alone user programs. The information learned from this reverse engineering effort does indeed seem to support this claim.

First of all, as discussed in the Branch Unit section, there is absolutely no hardware support for executing code directly from user memory. There is also no instruction TLB, and the L1 i-cache is physically mapped and tagged. Since all modern OS kernels (including Linux) assume that their own code pages are translated by the virtual memory mechanism, it would be impossible to port Linux to the bare Crusoe hardware without this capability.

There is also the issue of privileged instructions. As discussed in the Load Store Unit section, the TM58xx appears to support three main kinds of loads and stores: x86 in user mode, x86 in kernel mode and CMS physical space. The x86 protection scheme would fall apart if user applications are allowed to execute kernel context loads/stores and other privileged operations from user space, yet the underlying hardware provides no checking of this.

It appears that when CMS translates an x86 instruction trace, it will do so according to the context in which execution of the block was attempted (i.e., user mode or kernel mode). This may result in two separate versions of a given code block if executed from both the kernel and user space. Consequently, the translator will never generate privileged instructions in user code.

There is also the frequency scaling problem described in the Hardware Oddities section. User code targeting the native hardware ISA would have very restrictive scheduling of certain instructions without runtime awareness of the processor's unusual critical path restrictions.

Finally, it would be impossible to aggressively schedule loads and stores in native code without any corresponding sequentially ordered representation, i.e., x86 code, to fall back on in case of an exception. Without this, the exception handler would be unable to resolve the faulting instruction's dependency chain, since the hardware assumes CMS will interpret the block sequentially until the exception is found and resolved.

Origins

It should be noted that many of the ideas and internal implementations used in the TM32xx and TM5xxx chips were not even invented by Transmeta, despite what their patents appear to claim.

While I will not give a full analysis here, it appears that much of Transmeta's work was actually invented by IBM Research in the early 1990s. IBM's Daisy (Dynamically Architected Instruction Set from Yorktown) project [6] is essentially CMS for the PowerPC architecture, and uses a strikingly similar design and implementation, including:

Even more similarities between CMS and IBM's work can be found in [8] and [9], which details BOA, a high clock speed VLIW successor to Daisy specifically intended for runtime binary translation of PowerPC systems.

Of course, Transmeta was still unquestionably the first to fully solve the thorny problem of transparent x86 binary translation in a commercially successful manner. With that in mind, many of the basic ideas expressed in Transmeta's patents appear to have substantial prior art in Daisy, and its successor, BOA [8], [9].

However, since BOA is a newer effort, it is not clear where the initial ideas came from. The current situation is that both IBM and Transmeta appear to have conflicting patents on the same technology, with the only difference being the x86 versus PowerPC specific aspects.

The similarities between Transmeta's and IBM's work is easy to prove, since the Daisy firmware has been released as open source [6]. IBM even acknowledges this apparent similarity in [7], but notes that Transmeta has failed to provide any internal details to verify this claim [7], [8], [9]. Perhaps this report will shed some light on this mystery.

References

[1] Klaiber, A. "The Technology Behind Crusoe Processors," http://www.transmeta.com/pdfs/paper_aklaiber_19jan00.pdf

[2] Halfhill, T. "Transmeta Breaks x86 Low-Power Barrier," Microprocessor Report, 14(2):9--18, February 2000.

[3] TM5800 BIOS Programmer's Guide: http://www.transmeta.com/crusoe_docs/TM5800_BIOSGuide_6-14-02.pdf

[4] Linux Kernel Mailing List: "Re: Crusoe's persistent translation on linux?", by Linus Torvalds, June 19, 2003. http://www.ussg.iu.edu/hypermail/linux/kernel/0306.2/1091.html http://www.ussg.iu.edu/hypermail/linux/kernel/0306.2/1221.html

[5] Code Morphing Software 4.4.03 Persistent Translation Technology Update for HP Tablet PCs.

[6] Daisy: Dynamically Architected Instruction Set from Yorktown, IBM Research. http://www.research.ibm.com/daisy/

[7] "How similar is DAISY to Transmeta?" http://www-124.ibm.com/developerworks/opensource/daisy/faq.html#transmeta

[8] Sathaye, S. et al. "BOA: Targeting Multi-Gigahertz with Binary Translation," IBM Research. http://www.research.ibm.com/vliw/Pdf/bt99.pdf

[9] Gschwind, M., Altman, E. "Inherently Lower Complexity Architectures using Dynamic Optimization," IBM Research. http://www.research.ibm.com/people/m/mikeg/papers/2002_wced.pdf

[10] Transmeta Patents

http://patft.uspto.gov, search for Transmeta under assignee name
http://appft.uspto.gov also has recent patent applications

Appendix A

Obtaining CMS Memory Images

The majority of the information in this report was derived from a static analysis of a CMS 4.4.03 binary image derived from [5]. If you download and extract all files from the Windows installer archive in [5], there will be a cms4.4.03raptor.cru file. Use the following Linux commands to prepare this file according to the CMS Image Format section:

      dd if=cms4.4.03raptor.cru of=cms4.4.03raptor.gz bs=192 skip=1
      zcat cms4.4.03raptor.gz > cms4.4.03raptor.tmp
      dd if=cms4.4.03raptor.tmp of=cms4.4.03raptor bs=1024 seek=568

The last command inserts 0x8e000 zero bytes before the final image to match its native logical base address, as described in the Memory Map section.

This gives the CMS binary image file cms4.4.03raptor that is used for all further static analysis.

Alternately, CMS can be dumped from a running Crusoe system as described in the CMS Image Format section; however, that method is much more difficult unless runtime analysis is required.

TM58xx Disassembler and Analysis Software

A full disassembler and analysis toolset for TM58xx CMS images is provided in source form as CrusoeReport-Part2-Disasm.cpp. This program was designed and tested under Linux only. It will take an appropriately decompressed and padded CMS binary image (see previous section) and disassemble it, complete with basic block analysis and statistical report generation. Both of these features are useful for further reverse engineering.

Sample Code Sequences

To present some idea of the nature of Crusoe native code, the included file CrusoeReport-Part2-Samples.S contains disassembled and commented listings of a few key CMS functions. Each instruction is given in both binary and symbolic form, along with comments to demonstrate understanding of the actual high level meaning the corresponding source code expressed.

Appendix B

Statistics for CMS image cms4.4.03raptor


CrusoeReport-Part2-fig6.gif - 16810 Bytes
Figure 6 - Bundle Issue Chart

Total Instructions

231313

Total Nops

70363

0.304189561

Bundles

Count

Percentage

LSU|ALU1|ALU0|imm32

13386

0.13154869

LSU|ALU1|ALU0|brU

9911

0.097398705

LSU|ALU1

25401

0.249624104

ALU0|imm32

5409

0.053156048

ALU0|ALU1

31625

0.31078943

ALU0|brU

16025

0.157483023

Total

101757


Chart 1 - Bundle Frequency and nop Count

IPC figures are not provided since this obviously depends on the dynamic behavior of the code. With that in mind, most bundles appear to contain only two instructions; the quad-issue format is possible in only 22% of the code, primarily due to the limitations previously identified in the hardware.

Opcode Map and Instruction Descriptions

See the insn_name_table structure in CrusoeReport-Part2-Disasm.cpp for a map of the most common instruction opcodes and mnemonics. These instructions make up the vast majority of the CMS code.

Detailed Per-Unit Opcode Usage Statistics

The frequency of 9-bit opcodes used with different functional units is useful for determining the meaning and operation of the corresponding instructions.

The included CrusoeReport-Part2-histograms.txt file contains this data for each functional unit and bundle slot. The high 6 bits of the 9 bit opcode are in the rows, while the low 3 bits are in the columns.


  Copyright © 1996-2001, Real World Technologies - All Rights Reserved