I made a mini example in C.

It's awkward to do get right because you need an indirect pointer whose address remains fixed, but points to another pointer which can change (and is volatile).

While it might be possible to make something like this lockless - it's much simpler to stick a mutex in the array header. When we access the array_segment we can take a lock to prevent some other thread reallocating mid-way through accessing.

There's probably a few improvements that could be made. In particular it doesn't handle use-after-free, so it's not thread safe w.r.t cleanup.

https://godbolt.org/z/rYzn5KGre

I think parent was after base+offset+index rather than just base+index.

Examples would be eg, `string_view` or `ArraySegment`. They hold some offset relative to a base allocation, and when we index the string_view or ArraySegment we're indexing relative to that offset.

That is called pointer arithmetic on the base

Presumably `string_view` is referring to C++ std::string_view ?

It's not holding an "offset", it's a fat pointer, (ptr,len) or possibly (start,end)

You're imagining this as (string_ptr,offset,len) but that's 50% bigger for no practical benefit, you cannot unwind a std::string_view to get the string it's a view into, indeed there may never have been such a string.

Far pointers are for accessing memory in different segments. They're basically obsolete now. They were necessary in older machines with limited sized pointers or address spaces.

GCC still supports `__seg_fs` and `__seg_gs`, which behave similar to `far` in the example on the wiki page, as the FS and GS segment registers are still valid in x86-64 and used for TLS. Clang uses attributes `address_space(257)` and `address_space(256)` for the same thing.

The `__based` pointer in MSVC exploits the addressing modes by pinning the base in eg: `[base+index*scale+displacement]`. It's unrelated to segmentation.

> Far pointers are for accessing memory in different segments. They're basically obsolete now.

Project CHERI would like to disagree.

That's Fat pointers, not Far pointers. A fat pointer is a pointer with some other associated data which is stored in the pointer itself - typically by widening the number of bits used to hold a pointer value. The addressable bits usually remain unchanged - the added bits contain the auxiliary data.

Segmentation isn't used. There's no separate registers to hold the bounds information in CHERI - the bounds are held in the pointer value, unlike for example, the now obsolete Intel MPX, which held bounds information in separate registers.

There's some similarity to segmentation because the CHERI pointer restricts which addresses can be accessed, but I wouldn't compare them to far pointers.

Most modern processors have a single linear virtual address space and don't use segmentation, and even where segment registers exist (eg, FS and GS on x86-64), they're only superficial "address spaces" - allocated sections of the process's linear virtual address space which could be accessed without segmentation registers if you knew the base address held in FS or GS.

The poorest in society are the lowest CO2 emitters - they don't fly often, many don't own a car and use public transport - they can't afford meat in every meal - can't afford air con in summer or heating in winter.

Conversely, the wealthiest are frequent flyers, are chauffeured about in SUVs and rarely walk. They have everything they'll ever need and don't concern themselves about running the AC or heating.

They're preaching to the poor guy about what he needs to do to stop climate change.

Even if the poor guy wanted to care, he can't do much, but the people who claim to care could do a lot more, if they really did care.

The media circus tries to put the blame on the poor, while ignoring the emissions of the celebrities and treating them as royalty. Is it any wonder most people simply don't care?

If the media cared, they would be making villains of the celebrities and idols of the poor.

The FS and GS segment selectors are still used in x86-64, typically for `thread_local` storage, but they can be repurposed.

`thread_local` is an example of a "relative pointer" though. Instructions to access the thread local are prefixed with `fs:` or `gs:`, and point relative to the address in the respective segment register.

That's the same as any other index or member access. It's myThreadLocalBlock->myVariable.

thread_local is an example of something else unusual though - a struct linker as seen in https://yosefk.com/blog/i-want-a-struct-linker.html and it even supports dynamic loading.

That's not entirely true, but it's a valid reason to prefer using musttail.

`register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it.

    noinline void bar() 
    {
        register void *parent __asm__("r10");
        ...
    }

You can also use GCCs extended asm syntax to clobber a register for specific portions of code - such as the start of a function where you expect a register to have been given a value from the caller just before the call. Use `volatile` to prevent the compiler from making certain assumptions that might remove or reorder the instruction - as long as it is at the top it should execute immediately after the function prelude and before any of the function body.

    noinline void bar() 
    {
        void *volatile parent;
        // set parent = %r10 before anything else.
        asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10");
        ...
    }

Note that this will probably be less efficient than the former example, but maybe useful where you want to limit the scope in which `r10` is clobbered.

In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it.

    void foo()
    {
        struct foo_frame {
            int x;
        } locals = { 
            .x = 999
        };

        // Set `r10` to our function's local frame
        asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10")
        
        bar();
    }

That's pretty ugly but we can write a few macros to implement it more tersely - we can use this to have efficient closures in C without requiring an executable stack. (There's also `__builtin_call_with_static_chain`, but I've found it more troublesome to use than the manual way).

Demo: https://godbolt.org/z/cM9d8e1r5

For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.

> What practical patterns are enabled by TCO in C?

Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.

The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.

[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...

That may be true, but it may also mean you utilize more memory than you need to. If you aren't shrinking the array when you no longer need previously allocated capacity then you're wasting memory. You could end up with an array of 10 elements and an allocation of 2^10.

The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).

If you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.

In C23 this approach is nice, but in older versions of C we end up with awful macros where we need to define the structure before we use it.

    #define Array(T) struct array_##T
    #define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
    
    DEFINE_ARRAY(int);
    Array(int) foo;
    Array(int) bar;

C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front.

    #define Array(T) struct array_##T { size_t len; T *elems; }

    Array(int) foo;
    Array(int) bar;