Burroughs large systems descriptors

Descriptors describe storage areas, I/O requests and I/O results. They contain fields indicating, e.g. the type of descriptor, the address, the length, whether the data are present in storage. The details differ depending on the product line and the type of descriptor. The following text numbers the leftmost (most significant) bit as 0, in accordance with the Burroughs documentation.

Program and data descriptors have a bit called the "presence bit" or "p-bit"; it indicates whether the object referred to by the descriptor is currently in memory or in secondary storage. This bit is used to implements virtual memory.

Virtual memory was originally developed for the Atlas project at the University of Manchester in the late 1950s. Keen to see this used in commercial applications, they invited engineers from several computer companies to a seminar, including those from Burroughs and IBM. The B5000, released in 1961, was the first commercial computer to provide virtual memory. In the mid-1960s, other vendors, including IBM, RCA, and General Electric developed machines that supported virtual memory, with operating systems oriented towards time-sharing; IBM didn't support virtual memory in machines intended for general data processing use until 1972.

When a descriptor is referenced, the hardware checks the p-bit. If it is 1, the data is present in memory at the location indicated in the address field. If the p-bit is 0, the data block is not present and an interrupt (p-bit interrupt) is raised and MCP code entered to make the block present. In this case, if the address field is 0, the data block has not been allocated (init p-bit) and the MCP searches for a free block the size of which is given in the length field.

The last p-bit scenario is when the p-bit is 0, indicating that the data is not in memory, but the address is non-zero, indicating that the data has been allocated and in this case the address represents a disk address in the virtual memory area on disk. In this case a p-bit interrupt is raised and it is noted as an "other" p-bit.

In ALGOL, the bounds of an array are completely dynamic, can be taken from values computed at run time, unlike in Pascal where the size of arrays is fixed at compile time. This is the main weakness of Pascal as defined in its standard, but which has been removed in many commercial implementations of Pascal, notably the Burroughs implementations (both the University of Tasmania version by Arthur Sale and Roy Freak, and the implementation on Burroughs Slice by Matt Miller et al.)

In a program in the Burroughs environment, an array is not allocated when it is declared, but only when it is touched for the first time – thus arrays can be declared and the overhead of allocating them avoided if they are not used.

Also, low-level memory allocation system calls such as the malloc class of calls of C and Unix are not needed – arrays are automatically allocated as used. This saves the programmer the great burden of filling programs with the error-prone activity of memory management, which is crucial in mainframe applications.

When porting programs in lower-level languages such as C, the C memory structure is dealt with by doing its own memory allocation within a large allocated B5000 block – thus the security of the rest of the B5000 system cannot be compromised by errant C programs. In fact, many buffer overruns in apparently otherwise correctly running C programs have been caught when ported to the B5000 architecture. C, like Pascal, was also implemented using the Slice compiler system (which, like LLVM, uses a common code generator and optimizer for all languages). The C compiler, run-time system, POSIX interfaces, as well as a port of many Unix tools was done by Steve Bartels. An Eiffel compiler was also developed using Slice.

For object-oriented programs which require more dynamic creation of objects than the B5000 architecture, objects are best allocated within a single B5000 block. Such object allocation is higher level than C's malloc and is best implemented with a modern efficient garbage collector.

The address field in the B5000 is only 15 bits, which means that only 32K words (192KB) of memory can be addressed by descriptors. The B6500 extended this to 20 bits or 1 Meg words(6MB). By the mid seventies this was still a significant restriction of the architecture. To overcome this, two solutions were implemented:

1. Swapper – this solution actually implements another layer on top of memory management, moving large clusters of related data in and out of memory at once.
2. ASN – this solution allows physically more memory to be configured in a system, divided into separately addressable chunks. This architecture became known as ASN (Address Space Number) memory. Memory is logically divided into two areas, allocating low memory addresses to a Global address space for the operating system and support software and high memory addresses to several parallel Local address spaces for individual programs. Address spaces are numbered, zero indicating Global, 1..n indicating the local address spaces. Programs sharing data are automatically placed in the same address space.

No program code modifications were necessary for these features to be utilized. Both solutions can even be combined, but eventually the MCP memory requirements and program data sharing requirements outgrew the maximum size of the address spaces itself.

With the advent of the A Series in the early 1980s, the meaning of this field was changed to contain the address of a master descriptor, which means that 1 megabyte data blocks can be allocated, but that the machine memory could be greatly expanded to gigabytes or perhaps terabytes. This architecture was named ASD (Advanced Segment Descriptors) memory. This required a new common microcode specification, referred to as Beta. The main visionary behind ASD memory is John McClintock. Later the 3-bit memory tag was increased to a 4-bit specification, allowing the segment descriptor to grow from 20 to 23 bits in size, allowing even more memory to be addressed simultaneously. This microcode specification became known as level Gamma.

Another significant advantage was realized for virtual memory. In the B5000 design, if a data block were rolled out, all descriptors referencing that block needed to be found in order to update the presence bit and address. With the master descriptor, only the presence bit in the master descriptor needs changing. Also the MCP can move blocks around in memory for compaction and only needs to change the address in the master descriptor.

A difference between the B5000 and most other systems is that other systems mainly used paged virtual memory, that is pages are swapped out in fixed-sized chunks regardless of the structure of the information in them. B5000 virtual memory works with varying-size segments as described by the descriptors.

When the memory is filled to a certain capacity, an OS process called the "Working Set Sheriff" is invoked to either compact memory or start moving segments out of memory. It chooses code segments first, since these cannot change and can be reloaded from the original in the code file, so do not need writing out, and then data segments which are written out to the virtual memory file.

P-bit interrupts are also useful to measure system performance. For first-time allocations, 'init p-bits' indicate a potential performance problem in a program, for example if a procedure allocating an array is continually called. Reloading blocks from virtual memory on disk can significantly degrade system performance and is not the fault of any specific task. This is why many of today's computers may gain increased system performance by adding memory. On B5000 machines, 'other p-bits' indicate a system problem, which can be solved either by better balancing the computing load across the day, or by adding more memory.

Thus the Burroughs large systems architecture helps optimization of both individual tasks and the system as a whole.

The last and maybe most important point to note about descriptors is how they affect the complementary notions of system security and program correctness. One of the best tools a hacker has to compromise operating systems of today is the buffer overflow. C, in particular, uses the most primitive and error-prone way to mark the end of strings, using a null byte as an end-of-string sentinel in the data stream itself.

Pointers are implemented on the B5000 by indexed descriptors. During indexing operations, pointers are checked at each increment to make sure that neither the source nor the destination blocks are out of bound. During a scan or replace operation, the mechanisms used to read or copy large blocks of memory, both source and destination are checked at each word increment for a valid memory tag. Each memory segment is bounded by tag 3 words, which would make such an operation fail. Each memory segment containing integrity sensitive data, such as program code, is stored in tag 3 words, making an uncontrolled read – let alone modification – impossible. Thus a significant source of program errors can be detected early before software goes into production, and a more significant class of attacks on system security is not possible.