0

Basically can you have assembly code that is constantly writing new code after the end of the last line so that it can keep running in a straight line forever despite starting with finite amounts of code? No loops allowed.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • Sure, just figure out the appropriate bytes of machine code and the address. Of course, assuming your system supports this kind of self-modifying code in the first place. – Nate Eldredge Aug 07 '21 at 23:55
  • It would have to be assembly for some kind of machine with an infinite tape (like a Turing machine), otherwise you'd eventually get to the end of address space. Unless you have well-defined wrap-around semantics for the instruction pointer. You'd need a machine without any gaps in its usable address-space (so not x86-64), but with PC-relative addressing (so not i386). – Peter Cordes Aug 08 '21 at 00:50
  • It doesn't need to write itself continuously in order to run forever: as Peter says, use a processor that wraps around and has no memory gaps, (like a PDP-8) and fill memory with 0's or some other kind of `nop`. – Erik Eidt Aug 08 '21 at 00:57
  • @PeterCordes I remember one comment from many years ago on Google Groups (before SO era). A guy claimed that he once had to implement a programme that 1) did not use any conditional branches (this was a requirement, not a whim) and 2) upon reaching the end of the address space, it would trigger a Reset and the execution would start from the beginning. I also remember him saying: "If I made a mistake in that code some heavy objects would start falling from the sky...". [Nothing to do with self-modifying code, of course - the comment is on the "wrap-around" topic]. – tum_ Aug 08 '21 at 06:34
  • you mean machine code not assembly program? assembly requires an assembler to be running to turn the code into something executable. – old_timer Aug 08 '21 at 11:30
  • as mentioned elsewhere you would have to have a memory space that wraps around which is not typical. and completely populated with ram. very rare in fact. but technically possible – old_timer Aug 08 '21 at 12:37
  • PDP-8's 4k 12-bit core memory bank has no gaps in the 12-bit address space (fully populated, and no memory mapped I/O) and it will wrap the program counter from 7777 to 0000. – Erik Eidt Aug 08 '21 at 14:05

1 Answers1

2

It would have to be assembly for some kind of machine with an infinite tape (like a Turing machine), otherwise you'd eventually get to the end of address space.

Unless you have well-defined non-faulting wrap-around semantics for the instruction pointer. You'd need a machine without any gaps in its usable address-space (so not x86-64), but with PC-relative addressing (so not i386).

Probably a RISC with instructions the same width as registers, like ARM. You'd start with a couple instructions to get the encoding for a PC-relative store into a register, then run it.

Except ARM doesn't have coherent I-cache, neither do most RISCs. Perhaps a "simple" ARM, but actual Cortex-M0 wouldn't support 4GiB of RAM. Or a full core with L1i/d-cache disabled.

Or the repeating pattern could be 8 bytes, stp (store pair)/memory barrier. Or even stm (store-multiple) to allow storing many words with a single instruction, making room for the pattern to include multiple flush/barrier instructions.

It doesn't matter how many instructions of setup it takes before the repeating pattern and disable interrupts. After the first wrap-around, those instruction bytes will be overwritten.

You'd need to disable interrupts because you'll be overwriting every byte of memory including interrupt vector tables. Unless you do this in a user-space process with virtual memory, e.g. a 32-bit process under a 64-bit kernel, specially modified not to reserve any user-space pages. However, on most ISAs, kernel / system stuff like the interrupt table needs to be in the current address-space, so maybe that wouldn't be feasible. Page tables use physical addresses so don't have to be part of the current virtual address space.

Virtual memory would let you map many virtual pages to the same physical page (so you'd actually be wrapping around the same 4k page), so you could pull this off with much less than 4G of physical RAM on a 32-bit machine if it has an MMU. (But like I said, you'd probably still need to disable interrupts.)

Certainly you could imagine a simple toy ISA designed to make this possible, which didn't need any part of address-space reserved for anything.

Memory segmentation does make this easier: you can get wrap-around within one segment, e.g. 64kiB for 16-bit x86. But without a PC-relative store, you can't easily make a 1-instruction pattern that actually stores right ahead of where you're executing.

Fun fact: 8086 didn't have instruction-length limits and could actually loop forever decoding a 64k code segment full of prefixes, with no opcode. (https://retrocomputing.stackexchange.com/questions/15050/what-s-the-last-x86-cpu-that-didn-t-place-a-limit-on-the-size-of-a-single-instru)

I don't know a specific example of a machine with segmentation and PC-relative stores.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • 2
    What about `ADD SP,SI / PUSH AX / PUSH BX / PUSH CX / NOP` on classic 16-bit 8086? – supercat Aug 08 '21 at 01:51
  • @supercat: Oh right, keep the store address in sync with IP by dead reckoning. Yeah that could work. Your sequence is 5 bytes long, and stores 6 bytes, so you could pad with a NOP or a prefix, or a 2-byte encoding of one of the push instructions. – Peter Cordes Aug 08 '21 at 01:53
  • 1
    I edited the comment within the 5-minute window, and think the edited version is 6 bytes unless I've miscounted. I think on the 8088 and 8086 having the code be a multiple of 5 bytes wouldn't be a problem since I think a push with SP=1 would write to offsets 0 and 0xFFFF, and I'd guess that would be true on 80286. I don't think the 80386 has 16-byte wrap-around on push, or pop; I'm not sure about sequential code execution. Certainly if a branch +0x6000 is executed in 16-bit mode from offset 0x0000C000, it would go to 0x00002000 rather than 0x00012000, but I don't know whether... – supercat Aug 08 '21 at 19:53
  • ...IP is truncated on all instructions, or just near branches. – supercat Aug 08 '21 at 19:53
  • 1
    @supercat: [How to wraparound in the 64KB code segment in a program that stitches itself to its own tail, ad infinitum?](https://stackoverflow.com/q/68704917) is a practical attempt to do something like this on 8086, presumably inspired by this. – Peter Cordes Aug 08 '21 at 21:40