more pointer metadata: address spaces

[andrewrk]

GCC has the concept of address spaces, which is useful for embedded programming: https://gcc.gnu.org/onlinedocs/gcc/Named-Address-Spaces.html

In LLVM pointer types have the concept of the "address space" of the pointer: http://llvm.org/docs/LangRef.html#pointer-type

This is easy to support. Just like alignment, global variables can specify the address space that they are in. Just like alignment, pointers can specify their address space, and if it's the default address space, it can be omitted.

We will use a simple integer for the address space. 0 is the default. If an application wants to have a name for an address space, it can assign an integer to a constant. If an application wants to coordinate address spaces with a package it depends on, the package should accept a configuration option to specify the integer mapping for a given address space name, and then both the application's constants and the package's constants will refer to the same integer.

new keyword: addrspace

It can be used to create an address space constant:

const default = addrspace(0);
const mapper_hardware_ram = addrspace(1);

It can be used in the pointer syntax:

&addrspace(mapper_hardware_ram) u32

The type of mapper_hardware_ram is addrspace. The only thing you can do with it is use it in pointer syntax and global variable syntax.

Global variable:

var foo: u32 align(4) addrspace(mapper_hardware_ram) = 10;

Implicit casting and explicit casting does not allow changing address space of a pointer.

However you can use @addrspaceCast(addr_space, ptr) to (unsafely) override the address space of something.

[thejoshwolfe]

how about:

const default = 0;
const mapper_hardware_ram = 1;
var foo: u32 align(4) addrspace(mapper_hardware_ram) = 10;

why do we want an addrspace type? seems like it will cause more problems than it will solve. like, in your example, if we inline mapper_hardware_ram, we get addrspace(addrspace(1)).

[PavelVozenilek]

Nim has it under name "Memory regions" ( https://nim-lang.org/docs/manual.html#types-memory-regions ). AFAIK it is pretty useless, but Nim managed to drop a feature only once.

[Ilariel]

I believe the Nim "Memory regions" are a language level feature used for extra safety when dealing with pointers to possibly semantically different memory areas such as heap, stack, objects from another language and so on. As on they only exists in source but not in the compiled code.

The gcc and llvm address spaces however are a backend specific information required for correct codegen when memory and code exists in different memory.

[PavelVozenilek]

@Ilariel: you are right.

[kyle-github]

A lot of embedded systems use various address spaces. These are usually extremely proprietary and are totally non-portable in C. It would be nice to have some sort of structure in Zig to handle these cases. It would make Zig a LOT nicer than C in this regard.

Examples of address spaces:

• ROM-able code. Read only.
• Flash. Mostly read, writes are painful.
• write-only. Special control registers.
• Fast/slow RAM. The 8051 has a number of these kinds of thing as does PIC. This can be near/far as well. Different addressing modes can be used.
• User/System. Some systems do not have page-based protection.

[andrewrk]

I accepted this, but I'm going to be sure to feel the need for it in my OS project before implementing it.

[shawnl]

This could be used for TLS: (and %gs is unused, so we could use it for per-cpu data (why might we need this?))
[ ] x86 %fs and %gs namesspaces

[layneson]

I would like to voice my support for this feature. I have been experimenting with Zig's AVR support recently, and have experienced some friction due to AVR's separate program and data address spaces. avr-gcc supports a progmem attribute which allows static, read-only data to be placed in flash space, and LLVM supports it via specifying addrspace(1). All that is missing is support in the language itself.

[tgschultz]

The pointer portion of this seems like it is just a variation of #1595.

#5185 may also be related, in regard to different address spaces being potentially different lengths of pointer.

[SpexGuy]

There's potential for this feature to be a bit more powerful than distinct types for pointers. In #4284 (comment), @vegecode describes a use case in embedded where unaligned access is valid in some memory regions but invalid in others. His solution in C was to use volatile on pointers to the aligned-only memory region to prevent the compiler from optimizing his aligned loads into larger unaligned ones. But if the address space could convey information to the optimizer about whether unaligned access is valid it might provide a more targeted solution to this problem.

[layneson]

The pointer portion of this seems like it is just a variation of #1595.

I'm not so sure about that, since the addrspace info is more than just a way to distinguish pointers; it is relevant (and important) to the backend. For example, LLVM's AVR backend will recognize copies from program memory to data memory, and insert the special instruction required to do so. Distinct types would prevent an addrspace(1) pointer from being passed to a function that expects an addrspace(0) pointer, but it doesn't seem like that issue allows for that information to be passed to LLVM.

[ghost]

Are we sure we shouldn't express address spaces with enum variants? That seems like a better option than ints. We could reserve an enum name, and allow the root source file to implement that enum with whatever variants it needed:

// 'Segment' is a reserved name, like 'main' or 'panic'
const Segment = enum {
    .rom,
    .flash,
    .write_only,
    .ram_fast,
    .ram_slow,
    // etc.
}

Then segment pointers would accept enum variants, like var scratch: *segment(.ram_fast) [N]u8 = undefined, and segment-aware libraries would accept however many Segment parameters they wanted to use, like something.init(.ram_slow, .flash, .write_only). We could implement special compiler behaviour for common variants, and allow users to define their own behaviour for custom variants. (Not sure how we would do this. Maybe define a function that returns segment behaviour data (whether it's readable/writable and how fast, whether or not it's volatile etc.), and have the compiler use it? That sounds incredibly cool, but very complicated and maybe at odds with Zig's philosophy of transparency. What we really need is a language-level associative array from Segment variants to behaviour data, but I can't think of an analogue to this in Zig.)

[Aransentin]

Another example where this would be useful is the upcoming multi-memory proposal for WebAssembly.

[kyle-github]

Here's a thought experiment as a driver. I came up with this from @MasterQ32's example of AVR on Discord and my own experience with ugly MCUs. This came out of the discussion in #5185.

• We have an embedded device that has a 16-bit MCU.
• It has programs and fixed configuration (i.e. model number) in ROM. This is accessed via 14-bit addresses. Read-only.
• It has persistent configuration (DHCP last IP address), firmware patches, and per-unit configuration (i.e. WiFi frequency config for 5GHz) in Flash. This is accessed by 24-bit addresses.
• It has 64k of RAM used for ephemeral data storage and computation. Read/write.
• Each of these memory spaces is unique and has overlapping ranges with the others.
• It has memory mapped peripherals.

One approach to supporting this in Zig would be to do something like this:

• all pointers have an address space. May be a default (see below).
• every platform has a list (array of enum) of address spaces that it supports.
• each platform will define two more address spaces (generally, some will have a lot).
• every address space defines:
  • whether the space is read/write, read-only or write-only etc.,
  • the size of a pointer in bits,
  • the number of allowed/valid bits in a pointer,
  • minimal size of an object in the space (8-bit, 12-bit, 16-bit...)
  • maximum size of an object (in units).
  • minimum alignment of access into the space in units above.
  • whether a pointer can point to the whole space or not (think banks)
  • whether the space can contain code or data, only one,
  • other address spaces with which pointers can be compared.

For x86-64, you would have two address spaces, one for code and one for data. They would have almost identical definitions and would allow comparison of pointers between each other. You could have a per-platform setting that designates default address spaces for pointers that are not given an explicit address space. Or that could be a bool in the address space definitions for the platform on each address space, something like is_default.

I am sure that there are more features that I am missing (such as write blocks for Flash).

Then have Zig enforce the following:

• pointers from different address spaces may not be compared unless allowed in the address space definitions.
• when comparing two pointers, make sure only the allowed bits are compared.
• @intToPtr() defaults to address space 1, so there must be a @intToSpacePtr() function that also takes an address space ID.
• there is no such thing as usize that is across all address spaces. If you make one, your code is not portable and that is your problem. For commonly used platforms like x86-64, pointers are the same size and you could come up with a reasonable default.

There is more thought to be done on the handling of banks. It is possible that banks should be their own spaces with some other means to determine which bank is which. EDIT: remove references to banks. That's just muddying the issue at this point. Banks are BSP-specific.

[ghost]

Surely, if we're considering fixing the roles of different address space numbers, we should make addrspace take an enum rather than an integer, like callconv? So the backend would provide an AddressSpace type with universal .fn, .var and .const variants (with different names obviously, but what's important is they're the same names across every architecture), as well as .ram, .rom, .flash and whatever else, and addrspace would take one of these. Pointers would default to different spaces based on their attributes and child type, i.e. function pointers would be implicitly addrspace(.fn) and immutable pointers would be addrspace(.const). usize (and uptr, #5185) would default to the largest applicable value, and we may consider allowing a qualifier like we do with align: @typeOf(p1) == addrspace(.const) usize. Actually, we might consider allowing that for any types and declarations as well.

Re. banks, this may be considered an orthogonal concept, declared separately from address space: *addrspace(.ram) membank(4) u32. We may consider a builtin rather than a keyword for this, as compared to address space it's a relatively niche concept.

[shawnl]

Banks make absolutely no sense. They can always be combined into a linear map of a single address space, perhaps with peculiar alignment rules. As we already have to handle alignment rules, this is nothing new.

[kyle-github]

@shawnl not sure what you are saying here. I was thinking of situations where banks are used for overlays so the address as seen by the CPU of data in one bank is identical to the address in another. I think in general that trying to tackle that along with all the rest is biting off too much, though! I'll edit out the bank stuff.

[kyle-github]

@EleanorNB thanks for the thought on this. I very much like the idea you have with the different AddressSpace subtypes in an enum. Perhaps I misunderstood part of your proposal, but std.builtin.addrspace (just to make up a name) would be an array (or a list or a set, some sort of collection), not a single entry. For instance in the driving example, there are two places that code could be and three where data could be. All with different characteristics. You would have five AddressSpace elements for that platform.

Agreed on banks. I was getting too complicated and those are not address spaces. Both you and @shawnl pointed that out. I edited out the bank stuff from the example and from the rest of the proposal.

One of the goals of this is to make simpler platforms like Aarch64 and x86-64 require no address space annotations at all. Existing code should work without change and there should be no surprises. My internal question was, "how can this be retrofitted into what exists today without breakage but still provide reasonable support for real hardware?"

Only when you want to program AVR-based systems or other weird platforms would you need to care and need to annotate/type your pointers. That's fine because that code is deeply platform specific anyway. It would allow you to check your own code and make sure that Zig (and LLVM) have sufficient data to generate correct code for the platform. You do want Zig to catch it when you try to compare a pointer to data in RAM against a pointer to data in Flash if the address spaces are such that they can overlap (and thus are marked as not comparable). Or when you try to assign a pointer from a function in one space to a pointer to a function in another space that are not compatible. You do want LLVM to generate the correct code to access a function in ROM if that is different from how to access it in Flash.

There are a number of different possible ways to record the address space info. For instance, rather than having separate address space entries for code and data for a single physical medium, perhaps a small enum field with three possible values .code, .data, .both for an address space would be better (less duplication). I did not want to get too bogged down into how this is expressed at this point. Frankly, my ability to use Zig's strengths is not good, so I appreciate any feedback on how these things might best be expressed in Zig!

[BinaryWarlock]

Two useful OS justifications for this:

The Linux kernel (and possibly others) use addressspace to ensure (with the help of a static verifier) that the kernel doesn't dereference userspace pointers unsafely.

This is because if a user program passes a kernel pointer in a system call (say for example read/write/mmap), the kernel must catch that instead of accidentally dereferencing it in kernel space, which would allow the user to access kernel memory.

Linux uses these macros:

# define __user		__attribute__((noderef, address_space(1)))
# define __kernel	__attribute__((address_space(0)))
# define __iomem	__attribute__((noderef, address_space(2)))

Used like this: char __user *buffer

__kernel is obviously kernel-space memory, and __user is user-space. You cannot directly dereference a __user tagged pointer from the kernel. You must use copy_from_user() and copy_to_user() to access user pointers.

Having support for this in Zig would make this safe, statically verifying there are no unverified or accidental user/kernel boundary memory accesses that could lead to nasty security and correctness bugs.

__iomem pointers refer to I/O memory space you get from ioremap(), and you must pass them to corresponding I/O functions. (Overview here).

@andrewrk mentioned "feel[ing] the need for it in my OS project before implementing it" -- I think this is a great use case for it, and something Linux uses extensively in kernel and driver (especially important since it may be third party modules!) code.

[Snektron]

I also ran into the need for this when playing around with Zig and LLVMs AMDGPU target.

[kyle-github]

Thanks for the example use cases @BinaryWarlock and @Snektron.

The key things here are that you want to make sure that you cannot accidentally mix pointers from one domain (user) into another (kernel) or between mappings as seen in one area (main CPU) vs. other hardware (GPU), right?

This may be a bit of an intersection between some ideas I put in this issue and in #7693. You need to be able to control things like comparison and assignment. You also need to be able to implement translation between address spaces (user to kernel for instance). For that the bag-o-bits type would be useful as it has no interpretation.

Take @BinaryWarlock's example. If you are in kernel space, you want the constraints on a user pointer to prevent dereferencing. @Snektron can you give an example of what exact problem you hit?

[BinaryWarlock]

@kyle-github Correct, they're essentially separate namespaces for pointers that you cannot mix.

I was assuming the translation would happen by @ptrCasting between address spaces or something equivalent (like @ptrToInt -> @intToPtr), or even an @addrSpaceCast.

I don't have a particular preference on how it's implemented (as long as the semantics allow for that -- not being able to dereference/mix pointer address spaces), but I'm sure it could be generalized with general pointer metadata/tagging or something.

[kyle-github]

I was assuming the translation would happen by @ptrCasting between address spaces or something equivalent (like @ptrToInt -> @intToPtr), or even an @addrSpaceCast.

One of the offshoots of the bag-o-bits ideas that are floating around would be to take the user pointer, assign it to a bag-o-bits type removing all useful typing. Then do the appropriate hardware/software lookup to translate a user space pointer into kernel space (IIRC due to things like PAE and uneven kernel/user address space splits this can get really funky involving PTE lookups, but it has been a long time since I trawled through kernel code). Then you would @bitCast it back to a kernel pointer.

[tecanec]

Should allowzero be moved to the address space definitions? I have basically no experience with embedded other than a bit of arduino, so this entire comment may be wrong, but I'd assume that the usage of allowzero varies on a per-platform or a per-address-space basis rather than a per-variable basis. Of course, that would affect libraries that no longer know the size of an optional pointer, but I guess they wouldn't know the sizes of pointers in the first place, and this is assuming that libraries are even an option.

If there is no problem with moving allowzero, I guess that that'd mean that yet another viable option would be to define a range of valid pointers (somewhat simmalar to ints in #3806), and null could either be a value outside of that range, a specific value that is also defined by the address space, or it could just work the same way as current allowzero pointers. That could also be further generalized by allowing for what the hardware considers to be a single address space to be split up into multiple "virtual address spaces" within zig, allowing for things like splitting up code and data on modern x86, as suggested earlier by others. The only problem that I see with doing this on x86 is the allocation of memory with different or even changed privileges, such as when using JIT-loaded code.

[Snektron]

between mappings as seen in one area (main CPU) vs. other hardware (GPU), right?

@Snektron can you give an example of what exact problem you hit?

GPUs have a few different types of memory, with different purposes. For example there is general-purpose global memory, but there is often also a per-shader (private) core and per-compute unit (consisting typically of a group of 32 or 64 shader cores) (local) memory which is smaller and a lot faster.

The OpenCL programming model extends and generalizes this to include at least 6 different address spaces, and LLVM's AMDGPU backend uses this model as well. From the LLVM AMDGPU backend docs for example:

Name	LLVM number	Hardware name	Pointer size	Allows zero?
generic	0	flat	64	no
global	1	global	64	no
region	2	GDS	32	?
local	3	LDS	32	yes
constant	4	global	64	no
private	5	scratch	32	yes

Note that the flat address space can be used for both global, local and private data, but this is not supported on every target machine, and requires manual setup. Also note that while the global and constant address spaces in fact refer to the same virtual memory addresses, values specified to lay in the constant address space are assumed to not change for the entire duration of the kernel (as opposed to C's 'constant' pointers which are not really constant), which could improve efficiency.

This also highlights a possible intersection with issue #5185: Address spaces could be indexed with different size pointers, and the actual size of usize is bound to the size of an address space. Perhaps these two issues could be resolved simultaneously by integrating them? I could for example see an annotation to usize to make it the usize of a certain address space (where the plain old case would be the same as not augmenting a pointer with an address space, so it would refer to the default address space).

[Snektron]

I have thought a bit about this, and i think i have a decent concrete idea. To summarize: the core idea is that variables may be placed in different address spaces, which are architecture-specific. Loading values from these address spaces may require different instructions depending on the address space, and so pointers are required to know in which of the available address spaces the value lies.

Semantics

Every variable and pointer will gain a mandatory address space attribute, which may be inferred from the context of the variable declaration or pointee. For example, depending on architecture (in specific: SPIR-V), pointers to locals, globals and parameters may be of different address spaces. If a variable is declared inside a function, its address space should be inferred to the default address space for function locals (in the case of SPIR-V: private).

Casting

Casting between address spaces is typical dangerous behavior, and so i argue that this should only be allowed through the nuclear option of @ptrToInt/@intToPtr. Existing pointer conversion rules apply to pointers of the same address space, including c-pointers.

Syntax

Pointers and global variable declarations will gain another optional attribute, with syntax addrspace(addrspace: AddressSpace). When this attribute is omitted, the address space will be inferred. Contrary to the original proposal, this should be specialized syntax, and i believe that the possible address spaces should be hardcoded depending on machine type, using an enum to clarify naming (see also #9330). This syntax should be similar to align. Examples:

const progmem_i32: i32 addrspace(.progmem) = 10;
const progmem_i32_ptr: *addrspace(.progmem) = &progmem_i32;

C interop

C compilers like clang and GCC support address spaces as compiler-specific attribute. For example, gcc and clang accept the syntax __attribute__((addresspace(address-space-identifier)) int*. Note that in contrast to this proposal, address-space-identifier is an arbitrary integer hardcoded in the compiler. I believe that it is possible for translate-c to translate these arbitrary integers into their properly named address space, which is why casting rules should forbid casting C-pointers of the general address space to pointers of different address spaces. Also note that the first few identifiers (i believe up to 255 point to the generic address space), which allow for user-defined address spaces.

User-defined address spaces

As pointed out by @BinaryWarlock here, the Linux kernel uses this to prevent accidental dereferencing of user-space pointers. I believe that we should not support this case, at it leads to much additional complexity. For example, what if a user-defined address space is required for the non-default address space? I believe that this use case should be handled by opaque types. For example:

fn UserPtr(comptime Child: type) type {
  return *opaque {
    fn deref(self: @This()) Child {
       return ...;
    }
  };
}

Unresolved

• Some address spaces have additional properties not represented by this concrete proposal. For example, as others have noted before, the size of usize may differ per address space. Furthermore, some address spaces have different values for null and allow 0 as valid pointer.

Additional notes

Thread local variables are typically handled by an address space internally. For example, on x86 thread locals are typically implemented using one of the segment registers. While i dont think that it's very ergonomic to use addrspace(.fs) instead of addrspace, i think it can be used for something.

[Snektron]

I did some digging into whats up with the other address space having LLVM back ends:

• On AVR, there is progmem. Turns out that this address space is actually mapped into main memory on some devices, and a separate address space on others. This makes three variants in total:

  • Flash is mapped into ram
  • less than 64 kib flash is supported. In this case, the chip uses lpm to load from flash.
  • more than 64 kib flash is supported. In this case, the chip uses elpm to load from flash. This instruction extends the value passed to lpm with a value in the machine-specific z register, and so makes a 24-bit address. LLVM does not support this type as of yet.
    (Example board: atmega2560)

  For AVR we probably need two address spaces, one for 16 and one for 24-bit addresses. GCC has a whole bunch of weirdness for this, where they support 5 address spaces each with a hardcoded value for z, but i think a runtime approach is better.

• Other back ends are mainly GPU backends: AMDGPU, NVPTX, SPIR, HSAIL, and maybe a few i forgot. I think the LLVM input for these is all SPIR, which seems to be a standardized subset of LLVM IR (including binary representation). This can be loaded into OpenCL using clCreateProgramWithBinary. Note that this does require the frontend to emit some additional information, and so this requires a serious effort of working out what needs to go where.

  • AMDGPU and NVPTX can also compile directly to their related machine architectures as well as to bitcode. In the case of the former, the LLVM AMDGPU page lists that these kernels may be invoked using either of the following methods:

    • Via HSA, part of ROCm. My GPU is not supported so i can't test this.
    • Via Mesa. I think this is mostly internal, i haven't found any public-facing API to launch amdgcn kernels
    • Via amdpal. I haven't looked into this yet.