9

The CPU being able to tell code and data apart to prevent inadvertent or malicious execution of data as instructions by trapping (even if the bit pattern of the data can be interpreted as a valid instruction) is a helpful debugging mechanism. What was the first conventional architecture that had this feature?

This could be implemented as an execution permission bit in a page or segment descriptor, or even as a hidden bit per memory word.

By "conventional" I mean a non-tagged architecture (like Burroughs large systems or LISP machines), and, obviously, a von Neumann architecture rather than a Harvard-like one.

  • By "convential non-tagged", you mean e.g. with segment/base registers like on IBM machines or the PDP10? Or what exactly did you have in mind? – dirkt Feb 25 '17 at 7:48
  • @dirkt Whichever way it is implemented. To put the question another way, what was the first non-tagged architecture that would trap at an attempt to execute data? – Leo B. Feb 25 '17 at 16:49
  • presumably there was something earlier than the Itanium which used NX-style protection. – peter ferrie Feb 26 '17 at 0:03
  • @peter The BESM-6 had a hidden execution permission flag per memory word. The current value of the flag, utilized by the store instruction, was kept in a privileged register, modifiable only by the kernel. After loading the executable image, the store mode was switched to "data", achieving "NX stack". The flag was transferred by DMA to/from external storage media except in interchange mode with IBM tapes. Also, the location 0 was hardwired to "data 0". If I'm not mistaken, this was not filed as an invention, and I'm looking for a Western prototype. – Leo B. Feb 26 '17 at 0:36
  • If you are looking for a Western prototype for "flag per memory word", why are you ruling out tagged memory? That's e.g. exactly what the Burroughs B5000 does. I'm sorry, your question makes less and less sense. And if you are looking for equivalents, why don't you include it in the question right away instead of having us guess? – dirkt Feb 26 '17 at 6:52
5

For the condition "trap if data is accessed as code": I know of three ways to do that, (1) tagging memory words, (2) using base and limit registers, and (3) as part of the MMU for virtual memory.

(3) came comparatively late, so we don't need to look at it. I think most architectural families gained (2) under various names (descriptor, segment, address space, base & bound, codewords), at some stage (some late, like x86), and it would be interesting to make list. Note that (2) is primarily used for timesharing/multiprocessing, and not necessarily to distinguish between code and data. For example, the CDC 6000 only had a single pair (RA "reference address" and FL "field length").

(1) grew naturally out of various error detection schemes for memory (e.g. parity), which already did trap, so it was an obvious extension. There were also variants in early machines which had no tags on memory words, but mark or sentinel words, e.g. to describe the end of an array, which also would trap on access (but weren't really a code/data distinction, or general protection scheme).

This article has a bit of historical overview of tagged systems in the section II "Previous Work" on page 3.

Let's look at some early systems in detail:

Bourrough B5000 (1961): The B5000 implemented both (1) and (2). In the original B5000 and B5500 implementation (see manual), not all memory words were tagged (p. 2-5): (Packed) character words didn't have a tag, but control words and numerical words had a visible flag bit as part of the normal data bits. Descriptors were used extensively, even for single arrays, and the trap for out-of-bound descriptor access was identical to the trap for control-word-instead-of-numeric-word access.

The B5000 was unconventional in the sense that the instruction set and principles of operation were aimed at implementing a high level language. But it did not implement the principle of Lisp machines and later variants like the B6500 that the tag bits also described data types. So in that sense the B5000 does exactly what the BESM-6 does (descriptors aside).

One of the principal engineers of the B5000 also worked on the

Rice computer (R1) (built 1958-1961, partly operational in 1959): The Rice Computer again implemented both (1) and (2). I couldn't find a manual, but this page describes some details. The instruction set of the Rice Computer was more conventional than the B5000, though still a bit odd. Memory was initially CRT storage tubes of 8192 bits each. Word length was 63 bits: 54 bits of data, 7 bits of Hamming error-correction code, and 2 tag bits. The error correction was needed because the storage tubes were very unreliable (bits would gets weaker when read, tight loops would cause read errors). One can see how tag bits come natural when there's already that many error correction bits.

The archtectural roots of the Rice Computer were described as the MANIAC II at Los Alamos, and the Brookhaven computer at Brookhaven National Laboratory. I couldn't find anything on the latter. Details on the former are also hard to find. It used an additional 49th bit on top of the 48 data bits in storage, but that was probably parity. The Maniac III included a tag bit at least in the opcode.

9

(This answers the question "Early architecture that distinguished code from data, here by having differing bank switching for code and data". I'm leaving this here because it's interesting, even if it doesn't meet the criteria of the modified question.)

The PDP-1 had a Memory Field Control (Type 14) that was capable of distinguishing between an instruction field and a data field. This page dates this module as having been available in 1961. The PDP-1 itself was designed in 1959.

A field is a section of memory, in this case 4096 words of 18 bits. As described in the manual, the Type 14 Memory Field Control allowed for 8 modules of 4096 words, so it had presumable two 3-bit registers (one octal digit), one of which would select the memory module to fetch instructions from, and the other the one for data access (so basically banking). Other PDP models, e.g. the PDP-8, use a similar scheme to extend their address space.

Note that the main purpose of these field registers were to extend the address range, not to prevent against inadvertent or malicious execution. It was just convenient to distinguish between data and code to make the address range extension easier to handle, as it was possible to use the full internal 12-bit address range of 4096 words both for code and data.

Though it could be used to implement time-sharing concepts (the TSS-8 operating system on the PDP-8, 1967), but there was no foolproof way to stop a user program from switching fields if it wanted to (previliged/supervisor modes didn't exist, and weren't considered necessary).

Also note that the Type 13 Memory Field Control used a different scheme of mapping two smaller independent fields of 2048 words into the address range, with no distinction between code and data, so clearly they were still experimenting with these features at that stage.

  • Type 14 introduces split address spaces and makes the system Harvard-like. – Leo B. Feb 25 '17 at 16:45
  • No, Harvard-like means separate physical busses for code/data, and sometimes separate storage. If I understand the manual correctly, and by analogy with the PDP-8, these are just banking registers (or segment registers, if you want: CS and DS in the x86). You can still access code as data - after all, it would be difficult to load code from external storage otherwise. So it's definitely not Harvard-like. – dirkt Feb 25 '17 at 18:01
  • The split address space makes it a modified Harvard architecture. – Leo B. Feb 26 '17 at 0:19
  • But it doesn't have a split address space. That's the point. (The Type 15 apparently had a split address space, if I understand some other document correctly, but that's not what I'm talking about) – dirkt Feb 26 '17 at 6:48
4

The other answers to this question ignore the fact that the "separate program/data" architecture, aka the Harvard architecture, was described and implemented one year before the "shared program/data" architecture (aka Von Neumann architecture).

The first example was the Harvard Mark I in 1944, while the EDVAC was written up in 1945.

If you want to go back further I believe you could argue that Babbage's unfinished Analytical Engine embodied the separate program/data architecture.

  • Welcome to Retrocomputing. Thanks for the answer; it's interesting to see that the Harvard architecture predates the Von Neumann architecture. Remember to read the tour for another badge, and keep up the good work! :-) – wizzwizz4 Feb 26 '17 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.