{"id":106109,"date":"2022-01-03T07:00:00","date_gmt":"2022-01-03T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106109"},"modified":"2022-01-02T18:26:12","modified_gmt":"2022-01-03T02:26:12","slug":"2022013-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220103-00\/?p=106109","title":{"rendered":"Speculation on the design decisions that led to the common ABI for C++ coroutines"},"content":{"rendered":"

A little while ago, I discussed the common ABI for C++20 coroutine handles<\/a>. Recall that the common ABI is<\/p>\n

struct coroutine_frame_abi\r\n{\r\n    void (*resume)(coroutine_frame_abi*);\r\n    void (*destroy)(coroutine_frame_abi*);\r\n};\r\n<\/pre>\n
and that in practice, the implementations set themselves up like this:<\/p>\n
struct coroutine_frame\r\n{\r\n    void (*resume)(coroutine_frame*);\r\n    void (*destroy)(coroutine_frame*);\r\n    uint16_t index;\r\n    \/* other stuff *\/\r\n};\r\n<\/pre>\n
The index<\/code> represents the point inside the coroutine at which execution was suspended. Each time the coroutine suspends, the index<\/code> is updated, and when the coroutine resumes, the resume<\/code> function switches on the index<\/code> to decode where to resume execution.<\/p>\n
What other designs could have been used?<\/p>\n
One counter-proposal was that instead of updating the index, the code could update the resume<\/code> and destroy<\/code> pointers to point to where to resume next (or what to do if the coroutine is destroyed).<\/p>\n
Updating the function pointers would speed up resumption, since it could just jump directly to the resumption point instead of having to execute a switch<\/code> statement.<\/p>\n
However, it also comes with a cost.<\/p>\n
For one thing,  Control Flow Guard<\/a> is most effective when function pointers are multiples of 16, and the Microsoft compiler will arrange for all function pointer jump targets to be placed on 16-byte boundaries.  The clang compiler also supports Control Flow Guard<\/a>, but I don’t know whether it puts jump targets on 16-byte boundaries.<\/p>\n
Putting all resumption and destruction points on 16-byte boundaries would on average insert eight bytes for each potential entry point. The destruction entry points can often be quite small, destructing one object and then falling through to another case where the remainder of the objects are destructed.<\/p>\n
For example:<\/p>\n
winrt::IAsyncAction MyCoroutine()\r\n{\r\n    auto p1 = std::make_unique(1);\r\n    co_await Something1();\r\n    {\r\n        auto p2 = std::make_unique(2);\r\n        co_await Something2();\r\n    }\r\n    auto p3 = std::make_unique(3);\r\n    co_return;\r\n}\r\n<\/pre>\n
There are four suspension points in this coroutine, once we add the two extra suspension points provided by the promise.<\/p>\n
winrt::IAsyncAction MyCoroutine()\r\n{\r\n    promise p;\r\n    co_await p.initial_suspend();\r\n    \/\/ 1<\/span>\r\n\r\n    auto p1 = std::make_unique(1);\r\n    co_await Something1();\r\n    \/\/ 2<\/span>\r\n\r\n    {\r\n        auto p2 = std::make_unique(2);\r\n        co_await Something2();\r\n        \/\/ 3<\/span>\r\n    }\r\n\r\n    auto p3 = std::make_unique(3);\r\n    p.return_void();\r\n\r\n    co_await p.final_suspend();\r\n    \/\/ 4<\/span>\r\n}\r\n<\/pre>\n\n\n\n\n\n\n\n
Resume<\/th>\nDestroy<\/th>\n<\/tr>\n
goto 1<\/td>\ndestruct p<\/td>\n<\/tr>\n
goto 2<\/td>\ndestruct p1 and p<\/td>\n<\/tr>\n
goto 3<\/td>\ndestruct p2, p1, and p<\/td>\n<\/tr>\n
goto 4<\/td>\ndestruct p3, p1, and p<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In practice, the four destroy<\/code> functions are going to fall through to each other or at least jump to each other.<\/p>\n
destroy4:\r\n    lea     rcx, [p3]\r\n    call    std::unique_ptr<int>::~unique_ptr<int>\r\n    jmp     destroy2\r\ndestroy3:\r\n    lea     rcx, [p2]\r\n    call    std::unique_ptr<int>::~unique_ptr<int>\r\ndestroy2:\r\n    lea     rcx, [p1]\r\n    call    std::unique_ptr<int>::~unique_ptr<int>\r\ndestroy1:\r\n    lea     rcx, [p]\r\n    call    promise::~promise\r\n<\/pre>\n
If each of these destruction entry points were a runtime function pointer, there would have to be a lot of padding between them to get the start-addresses to align on 16-byte boundaries.<\/p>\n
On the other hand, if it’s a switch statement or jump table, no such padding is required because the jump targets are kept in the code segment or the read-only data segment, so they are safe from corruption via buffer overflow, use-after-free, or type confusion.<\/p>\n
In addition to the instruction padding requirements, replacing the function pointers on suspension is significantly more code:<\/p>\n
    ; index-based\r\n    mov word ptr [rbx].index, 42 ; update the index\r\n\r\n    ; function-pointer-based\r\n    mov rcx, offset resume2\r\n    mov qword ptr [rbx].resume, rcx\r\n    mov rcx, offset destroy2\r\n    mov qword ptr [rbx].destroy, rcx\r\n<\/pre>\n
Instead of writing a 16-bit constant, we are writing two 64-bit constants. But the x86-64 cannot write a 64-bit constant directly to memory. You have to pass the value through a register first.<\/p>\n
And that constant isn’t a constant. It’s a relocatable address, which means that you also have to add a relocation record for each of those addresses.\u00b9<\/p>\n
Furthermore, other 64-bit processors cannot load 64-bit immediate constants. If the function isn’t too large, you can use instruction-pointer-relative instructions:<\/p>\n
    ; index-based\r\n    movz    r0, #42\r\n    str     r0, [r1, #index]\r\n\r\n    ; function-pointer-based for small functions\r\n    adr     x0, resume2\r\n    str     x0, [r1, #resume]\r\n    adr     x0, destroy2\r\n    str     x0, [r1, #destroy]\r\n\r\n    ; function-pointer-based for large functions\r\n    adrp    x0, resume2\r\n    add     x0, x0, #PageOffset(resume2)\r\n    str     x0, [r1, #resume]\r\n    adrp    x0, destroy2\r\n    add     x0, x0, #PageOffset(destroy2)\r\n    str     x0, [r1, #destroy]\r\n\r\n    ; alternate version with constants in memory\r\n    ; (two pointers = size of four instructions)\r\n    ldr     x0, [pc, #...]  ; load constant from memory\r\n    str     x0, [r1, #resume]\r\n    ldr     x0, [pc, #...]  ; load constant from memory\r\n    str     x0, [r1, #destroy]\r\n<\/pre>\n
You don’t need a switch statement in the resume<\/code> function, but you pay more at each suspension point to set up the function pointers. This is trading a fixed cost for a variable cost. The size of the coroutine switch statement is 34 bytes:<\/p>\n
0f b7 43 xx             movzx eax, word ptr [rbx+xx]\r\nff c0                   inc   eax\r\n83 f8 08                cmp   eax, 8\r\n0f 87 xx xx xx xx       ja    fatal_error\r\n48 8d 15 xx xx xx xx    lea   rdx, [__ImageBase]\r\n8b 8c 82 xx xx xx xx    mov   ecx, dword ptr [rdx+rax*4+xxxxxxxx]\r\n48 03 ca                add   rcx, edx\r\nff e1                   jmp   rcx\r\n<\/pre>\n
The index update is six bytes:<\/p>\n
66 c7 43 xx yy yy       mov  word ptr [rbx+xx], yyyy\r\n<\/pre>\n
The double-address update is 27 bytes:<\/p>\n
48 b9 xx xx xx xx       mov  rcx, xxxxxxxxxxxxxxxx\r\n      xx xx xx xx\r\n48 89 0b                mov  [rbx], rcx\r\n48 b9 xx xx xx xx       mov  rcx, xxxxxxxxxxxxxxxx\r\n      xx xx xx xx\r\n48 89 4b 08             mov  [rbx+8], rcx\r\n<\/pre>\n
You save a 34-byte fixed overhead, but each suspension point costs 21 bytes more. This means that once you have a second suspension point, you’re at net loss in code size.<\/p>\n
A similar calculation plays out for AArch64: The standard resumption dispatcher is eight instructions:<\/p>\n
        ldrh    x0, [x1, #index]\r\n        add     w0, w0, #1\r\n        cmp     w0, #8\r\n        bhi     fatal_error\r\n        adr     x9, switch_table\r\n        ldrsw   x8, [x9, w0 uxtw #2]\r\n        add     x9, x9, x8, lsl #2\r\n        br      x9\r\n<\/pre>\n
Updating the index is two instructions, but updating the two pointers is four instructions for small functions, and six instructions for large functions.\u00b2 Even if you take the smallest extra cost of two instructions, it means that once your coroutine has four suspension points, updating function pointers is going to have a larger net code size.<\/p>\n
For all but the simplest coroutines, the index-based version ends up a net win in terms of code size.<\/p>\n
\u00b9 I guess you could be sneaky and if you know that only one suspension point precedes the one you are about to reach, you could add the delta to the two addresses. But that works only for straight-line code, and if anything goes slightly wrong, the results can get quite wild.<\/p>\n
\u00b2 If you store the addresses as in-memory constants, then it will cost you eight instructions plus two relocations.<\/p>\n","protected":false},"excerpt":{"rendered":"
Considering some alternatives.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-106109","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Considering some alternatives.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106109"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106109\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}