GNAT cross-compiler: my various questions

[Ethin]

Write an address to the goto_address member and the AP will begin executing at that address. The AP will set its stack pointer to target_stack when it begins executing.

You have to perform the write to goto_address in a manner that guarantees memory consistency. For example, in C, you would use atomic_store_explicit with memory_order_release. I'm sure Ada has an equivalent, but I don't know what it would be.

Do you mean this? (I have never understood atomic compare and exchange, myself; the description of it - "evaluates the value of Item; compares the value of Item with the value of Prior; if equal, assigns Item the value of Desired; otherwise, makes no change to the value of Item" - definitely seems like it would just be a no-op, every time, but maybe there's something I'm missing. I mean, your essentially doing

Code: Select all

if item = prior then
   item := desired;
end if;

It would make better sense to check to see if the item and what it should be right now are (not) equal.) I'm also a bit concerned that the subprograms in that package do not allow for the specification of the atomic ordering. I'm unsure if its safe, then, to assume that everything is ordered as sequentially consistant. (There is a function, in every child package of System.Atomic_Operations, called Is_Lock_Free that is designed to tell you if the operations of that child package are lock-free, which is defined, in the specification, as "if the subprogram is guaranteed to return from the call while keeping the processor of the logical thread of control busy for the duration of the call".)

Pointer arithmetic is supported in Ada via the System.Storage_Elements package. Here's a completely useless example that demonstrates pointer arithmetic (and how unsafe it is as it allows access beyond the bounds of the array!):

Code: Select all

with System;
with System.Storage_Elements; use System.Storage_Elements;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

   type IntegerAccess is access Integer;
   type IntegerArray is array (1 .. 4) of Integer;
   arr : IntegerArray := (1, 2, 3, 4);
   i   : System.Address;

begin
   i := arr'Address;
   for j in 1 .. 5 loop
      declare
         int : Integer;
         for int'Address use i;
      begin
         Put_Line (int'Image);
      end;
      i := i + Integer'Size /8;
   end loop;

end Main;

with output

Code: Select all

1
2
3
4
0

Uhm. Wow. I don't know if I should be amazed or horrified that it lets you just casually do that as though it weren't something possibly dangerous. Frankly I'm amazed that the runtime didn't go "Hey WTF" or something. And I'm unsure why the "Programming in Ada 2012" book doesn't mention being able to do that; it explicitly states that Ada does not allow for pointer arithmetic, but maybe Barnes was explicitly talking about "safe" Ada.

[iansjack]

I think that to be useful for OS development a language has to let you do just about anything. After all, allowing inline assembler - or linking with foreign routines - is about as unsafe as you can get. Like Rust, Ada makes you jump through hoops to perform unsafe operations to ensure that you really want to do what you are doing. It's just that those hoops are rather more difficult to get through in Rust.

[Octocontrabass]

Do you mean this?

If it provides an appropriate memory barrier, then yes, that would work. It seems a bit excessive, though - most architectures provide simpler atomic operations for when you don't need a whole compare-and-swap.

I have never understood atomic compare and exchange, myself

You can implement just about any other atomic operation on top of it if you use it like this:

1. Read a shared variable from memory.
2. Decide on a new value for that variable (which may or may not depend on its current value).
3. Perform the compare/exchange: if the variable has been changed by another thread, read it again and go to step 2. Otherwise, write the new value to memory and return the previous value.

[davmac314]

I have never understood atomic compare and exchange, myself; the description of it - "evaluates the value of Item; compares the value of Item with the value of Prior; if equal, assigns Item the value of Desired; otherwise, makes no change to the value of Item" - definitely seems like it would just be a no-op, every time, but maybe there's something I'm missing.
...
It would make better sense to check to see if the item and what it should be right now are (not) equal.)

What you are missing, I think, is that you can use it to change from a guaranteed specific value that no other processor has changed in the meantime, but also to detect if a value has changed in the meantime.

Consider if you want to implement a spinlock (only one thread can lock it at a time). Let's say you use value 0 to mean "unlocked" and value 1 to mean "locked". Then your lock operation looks like:

Code: Select all

lockval = 1;
while (lockval == 1) {
    compare_and_swap(&lock /* value to compare */, 0 /* what to compare with */, &lockval /* what to swap with, if equal */);
}

You only want it do the swap (the lock operation) if it has the value 0 (unlocked). You can't just wait until the lock is available and then lock it, because there is always a moment between checking the value and performing the locking where another thread might also claim the lock (and you wouldn't notice).

Another example: suppose you want to atomically add a node to the head of a linked list. You make a new head node and link the current head as its "next" node. Now you would set the head to the new head node. But - you want to do this only if it hasn't changed in the meantime, since that means you have to re-set your "next" node before you switch in your new list. Again, compare-and-swap can do this.

[klange]

Atomic compare-and-exchange is like the opening scene from Raiders of the Lost Ark where Indy swaps the bag of sand for the golden idol.

The lock is the pedestal, and owning the lock is holding the golden idol. Everyone brings their own bag of sand.

In true "compare and exchange" (more often called compare and swap), the process is:
- Look at the pedestal. Does it have the idol?
- If yes, swap the idol and your bag of sand. You have the idol!
- If no, keep your bag of sand and mutter something about museums or snakes. Try again later.

If that sounds like it would be hard to make atomic, it kinda is and not all architectures have supported this whole process as an atomic instruction. But the good news is, if you set some ground rules, all you really need is atomic exchange - the comparison can happen afterwards, and need not be atomic. The process with just an atomic exchange looks like this:

- Swap your bag of sand for whatever is on the pedestal.
- Now look at what's in your hand, is it the idol?
- If yes, you're done. You have the idol!
- If no, same as before, mutter something about museums or snakes. Try again later, with your newly acquired bag of sand.

Full compare-and-exchange has some advantages, though, especially if you're doing more than just simple locks. Note how in the just-atomic-exchange scenario, you end up with someone else's bag of sand and yours ends up on the pedestal if you failed to acquire the idol/lock, while in the full compare-and-exchange process you keep your bag of sand, and the bag of sand on the pedestal is always the one belonging to the lock owner. The ability to compare atomically beforehand means the thing on the pedestal always has relevant meaning. One thing this can be used to implement that isn't a simple lock is atomic arithmetic:

- Examine the value on the pedestal.
- Perform an operation on the examined value.
- Do an atomic compare-and-exchange: Check for the value you examined, and if that's what's still there, replace it with your newly calculated value.
- If the comparison fails, go back to the beginning. Repeat until the comparison (and swap) succeeds.

[Ethin]

Interesting comparisons and thanks for the explanation. I just found most (if not all) the descriptions of CAS quite confusing (and just outright illogical). E.g. The Intel manual describes cmpxchg as:

Compares the value in the AL, AX, EAX, or RAX register with the first operand (destination operand). If the two values are equal, the second operand (source operand) is loaded into the destination operand. Otherwise, the destination operand is loaded into the AL, AX, EAX or RAX register. RAX register is available only in 64-bit mode.

This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically. To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)

In 64-bit mode, the instruction’s default operation size is 32 bits. Use of the REX.R prefix permits access to additional registers (R8-R15). Use of the REX.W prefix promotes operation to 64 bits. See the summary chart at the beginning of this section for encoding data and limits.

So the operation just seemed silly to me. But your explanations (and... interesting comparisons) helped.

[nullplan]

Another wonderful example of a CAS being useful is a pthread_once variable. What it's supposed to do is indicate whether some initialization has happened, but logically, it can be in three states: Either the initialization has not yet happened, or it has happened, or it is currently happening. By interface, the initialization function only runs once. So how about we define pthread_once_t to be an integer type, and then 0 means not initialized, 1 means initialization is running, and 2 means initialization has concluded.

What you can do to implement pthread_once() is that, in a first step, you try to CAS the variable given from 0 to 1. Even with multiple threads attempting it, only one of them will ever be able to do it. So that thread then runs the initialization function and then sets the variable to 2. All other threads spin in a loop, waiting for the variable to turn from 1 to 2. Linux futexes help a lot here, since you can just make them all sleep on the once variable if it is 1. Add in some logic to handle thread cancellation and you pretty much have a production-ready implementation of pthread_once():

Code: Select all

typedef atomic_int pthread_once_t;
#define PTHREAD_ONCE_INIT 0
static void cleanup(void *o) {
  atomic_store_explicit((pthread_once_t*)o, 0, memory_order_release);
}

int pthread_once(pthread_once_t *o, void (*init)(void)) {
  for (;;) {
    int e = 0;
    if (atomic_compare_exchange_weak_explicit(o, &e, 1, memory_order_acq_rel, memory_order_acquire)) {
      pthread_cleanup_push(cleanup, o);
      init();
      pthread_cleanup_pop(0);
      atomic_store_explicit(o, 2, memory_order_release);
      futex_wake(o, INT_MAX); /* wake as many threads as are waiting on the variable. */
      return 0;
    } else if (e == 1) {
      futex_wait(o, 1, 0); /* wait indefinitely if *o still has value 1 */
    } else if (e == 2) /* the CAS above is weak, so can fail spuriously, so could fail with e == 0 */
      return 0;
  }
}

Boy, I hope I have those memory orders correct, because they confuse the hell out of me. But the release stores ought to pair with the acquire loads in case of failing comparison, so each thread seeing a variable of value 2 ought to see the effects of the initialization functions.

Anyway, point is, only one thread can change the variable from 0 to 1. Many can see it being 0, or being 1, but only one can actually affect the change successfully.

[Ethin]

The memory ordering is what concerns me. The Ada atomic operations package does not allow you to specify memory ordering; hell, the entire section (C.6) says nothing about them. So I don't know if that means "enforced sequential consistency" or not. Though if it does I can't imagine that harming anything.

[Octocontrabass]

From what I've been able to gather, Ada supports one memory order: all atomic and volatile accesses occur in program-sequential order, and everything else is unordered.

This means you can declare target_stack as volatile and goto_address as atomic, then simply assign values to them. You don't need the atomic operations package because simple assignment to an atomic variable is atomic.

[Ethin]

I'm struggling to build the cross-compiler -- I'm using NixOS and they want me to build a custom stdenv (but they won't tell me how ). Would it be worth it to just set up a Linux container and do my development in there? I'd either need to use sshfs to bridge the container and my host FS (I'm not sure how to do volumes on LXD) or use VScode (which has accessibility problems on Linux). Ideas? I suppose I could just use Vagrant...

[Ethin]

So, I've built the toolchain, but how do I define flexible arrays in Ada? Like this:

Code: Select all

struct stivale2_struct_tag_pmrs {
    struct stivale2_tag tag;
    uint64_t entries;
    struct stivale2_pmr pmrs[];
};

My idea was to try something like:

Code: Select all

type Protected_Memory_Region_List is record
Tag : Stivale2_Tag;
Entries : Unsigned_64;
Regions : array(0 .. Entries) of Protected_Memory_Region;
end record Protected_Memory_Region_List
with Convention => C, Packed, Atomic, Volatile;

With the Protected_memory_Region record defined as:

Code: Select all

type Protected_Memory_Region_Permissions is record
Read, Write, Execute : Boolean;
end record Protected_Memory_Region_Permissions
with Convention => C, Packed, Volatile, Atomic, Size => 3;
for PMR_Permissions use record
Read at 0 range 0 .. 0;
Write at 0 range 1 .. 1;
Execute at 0 range 2..2;
end record Protected_Memory_Region_Permissions;

type Protected_Memory_Region is record
Base : Unsigned_64;
Length : Unsigned_64;
Permissions : Protected_Memory_Region_Permissions;
end record Protected_Memory_Region
with Convention => C, Packed, Volatile, Atomic;

But I'm not sure if that'll work or not, given that Entries is dynamic, a record component, and not a variant component. How should I handle this?I know that this can be done via something like:

Code: Select all

type Protected_Memory_Region_List (Entries : Unsigned_64) is record
...
Regions : array(0 .. Entries) of Protected_Memory_Region;
end record Protected_Memory_Region_List;

But entries isn't the first component in the record, so I'm pretty sure this won't work as expected. This is made even trickier since this info is not data I'm passing in but data that's given to me externally so...

[iansjack]

I'm not sure why you think your proposed solution wouldn't work. Note that you wouldn't declare a field "Entries" in the record, its existent is implicit in the fact that you are using a discriminant.

Unless I have mistaken your problem, this seems to be the sort of case that records with discriminants were designed for.

(I may be misunderstanding your problem as I can't see what you mean by: "This is made even trickier since this info is not data I'm passing in but data that's given to me externally so...".)

[Ethin]

I'm not sure why you think your proposed solution wouldn't work. Note that you wouldn't declare a field "Entries" in the record, its existent is implicit in the fact that you are using a discriminant.

Unless I have mistaken your problem, this seems to be the sort of case that records with discriminants were designed for.

(I may be misunderstanding your problem as I can't see what you mean by: "This is made even trickier since this info is not data I'm passing in but data that's given to me externally so...".)

I'm just worried that if I do do it the way I suggested, Limine would pass in the data incorrectly. I have no idea what the layout of discriminant record types is in memory, particularly when I export them, and the tag is supposed to come first in the record, and then the entry count, and then the list. But if the entry count comes first, then the tag and list, that's going to mess things up pretty nicely. I could try it, though; I could always change it later. What i meant by this being trickier is that Limine is writing the data to memory, and I'm just reinterpreting it, not manually parsing it into components/discriminants, so I can all to imagine me doing something wrong and then later going "what the hell, why does it say I have 30 billion PMRs?" for example.

[iansjack]

If you are reading it into memory, can’t you just make the array as large as the maximum possible value (no problem if it’s the last field of the record), then set the address of a variable of the record type to the memory location where you have loaded the data. Much the same as you would do it in C. Obviously that means you have to manually ensure that you don’t exceed the array bounds rather than letting the compiler check this for you.

[Ethin]

If you are reading it into memory, can’t you just make the array as large as the maximum possible value (no problem if it’s the last field of the record), then set the address of a variable of the record type to the memory location where you have loaded the data. Much the same as you would do it in C. Obviously that means you have to manually ensure that you don’t exceed the array bounds rather than letting the compiler check this for you.

Pretty sure that for things like a PMR list or CPU list there isn't an upper limit, other than 2^64. Which is ridiculous.