Algebraic addressing

Algebraic addressing is the property of a composite entity that the addresses of its components are numerically dense and obey the rules of ordinary arithmetic.

Of program objects

The memory layout, and hence internal addressing, of data objects is defined by the programming language. Thus an 10x10 matrix in FORTRAN is contiguous and dense, and the address of the last element is (100*element size) greater than the address of the first element. Hence FORTRAN provides algebraic addressing for matrix elements. By contrast, in the C language a matrix is an array of arrays, where each row is contiguous and dense but the whole matrix will generally not be, and the addresses of the first and last element bear no relation to each other.

Of file mappings

Files may be mapped to memory using the mmap() system call. This call causes an identified portion of the file to appear in the virtual address space of the mapping application, where it can be referenced by ordinary memory operations rather than I/O. Multiple calls to mmap may map disjoint or overlapping portions of the same underlying file. If the portions are disjoint then the mapped virtual spaces will also be disjoint even though the underlying file is contiguous. However, though the virtual spaces are disjoint in memory the addresses within each space will in general be algebraic. In addition, addressing between spaces may also be algebraic. For example, if pages are 4k bytes each and an application independently maps pages 1 and 3 of a file then each mapping will occupy 4k bytes of virtual space. If the two spaces are themselves mapped 4k apart in memory then they are algebraic even though disjoint. That is, a given offset from one address in the file will address the same byte as will the same offset applied to the corresponding address in mapped memory, even if the offset hops over the unmapped page.

The POSIX standard leaves undefined whether multiple partial file mappings will be allocated so as to preserve algebraic addressing, and in general algebraic addressing cannot be guaranteed on any machine or operating system for sufficiently complex patterns of mapping. However, most mmap implementations on conventional machines do not preserve algebraic addressing for any partial mappings. On the Mill the shared virtual address space makes it easy to preserve algebraic addressing in all uses of mmap, with two exceptions. The first exception occurs when the underlying file is larger than the maximum amount of contiguous virtual memory available for allocation. The second exception occurs when the underlying file dynamically increases its extent, and the program adds new partial mappings to the increased portion after other mappings to the original file were created. These exceptions are rare, so the recommended OS policy on the Mill is to preserve algebraic addressing where possible. Programmers should be aware that Mill programs which depend on algebraic addressing among pieces of mapped files may not port to other systems.