реализация легковесных нитей, попытка создать оптимальный аналог Protothreads, FREERTOS Co-routines Опции

[KRS]

Навеяно генераторами Python а (оператор yield)
Просто мысли по поводу оптимальной реализации на С
Обычно (Protothreads, FREERTOS Co-routines)реализуются с помощью макросов которые разворачиваются в примерно такую структуру:

Код

switch(state) {
.....
.....
    state =  __LINE__; return; case __LINE__:
.....
.....
    state =  __LINE__; return; case __LINE__:
}

имеют ограничения на локальные переменные и код неоптимальный получается.

Я хочу попробовать сохранять локальные переменные (которые обычно помещаются в регистрах) и восстанавливать их при след. запуске.

Варианты реализации для несложных функций, у которых локальные переменные помещаются в регистрах ( к тому же в примере сохраняются только регистры R24-R27, R4-R5). Оптимизацию надо ставить максимальную по скорости.
(Вариант 1 можно доделать так что бы не было ограничений на количество регистров и локльных переменных в стеке).

uint8_t generator_next(uint8_t) передает параметр очередному шагу генератора и возвращает значение.
Внутри функции генератора – функция uint8_t yield(uint8_t) принимает аргумент для возврата generator_next (результат очередного шага) и возвращает следующий аргумент вызова generator_next (параметр следующего шага).
Эти параметры могут и не использоваться.

Вариант 1:
Для каждого генератора сохраняем указатель на точку входа и локальные переменные ( регистры). При инициализации сохраняем адрес функции ( локальные регистры мусор).
При вызове next сохраняем в стеке указатель на generator_t, обмениваем локальные регистры с сохраненными и переходим по сохраненной точке. При yield вытаскиваем из стека новую точку входа, указатель на generator_t, обмениваем локальные регистры с сохраненными и дальше обычный ret.

реализация generator_next и yield

Код

//обмен регистров R24-R27, R4-R5
swap_locals     MACRO
                ldd r18, Z+2
                ldd r19, Z+3
                std Z+2, r24
                std Z+3, r25
                movw r24, r18

                ldd r18, Z+4
                ldd r19, Z+5
                std Z+4, r26
                std Z+5, r27
                movw r26, r18

                ldd r18, Z+6
                ldd r19, Z+7
                std Z+6, r4
                std Z+7, r5
                movw r4, r18
                ENDM

        RSEG CODE:CODE:NOROOT(1)
PUBLIC generator_next
generator_next:
                //сохранение указателя на generator_t
                push ZH
                push ZL

                //обмен регистров
                swap_locals

                //переход по сохраненному адресу
                ldd r18, Z+1
                ld  ZL, Z
                mov ZH, r18
                ijmp
                
PUBLIC yield
yield:
                //получение адреса возврата из стека
                pop r19
                pop r18
                //получение сохраненнго указателя на generator_t
                pop ZL
                pop ZH
                //сохранение следующей точки входа
                std Z+0, r18
                std Z+1, r19
                //обмен регистров
                swap_locals
                ret

Небольшой тест

Код

#include <stdint.h>
#include <stdio.h>

typedef void (__task __version_3 *gfunc_ptr_t)(uint8_t c);
typedef struct {
    gfunc_ptr_t entry;
    uint8_t saved_regs[6];
}generator_t;

uint8_t yield(uint8_t ret);
__z uint8_t generator_next(generator_t *g, uint8_t val);

static inline void generator_init1(generator_t *g,  gfunc_ptr_t entry)
{
    g->entry = entry;
}

__task __noreturn
void gen1(uint8_t max)
{
    uint8_t i;
    uint8_t step;
    uint8_t tmp;

    step=1;
    while(1) {
        for(i=0;i<max;i+=step) {
            tmp=yield(i);
            if (tmp)
                step=tmp;
        }
    }
}

void gen1_test(void)
{
    generator_t g;
    generator_init1(&g,gen1);
    //первый вызов функция с самого начала фактически передается max,
    //но возвращает уже 1 значение
    printf("%d ",generator_next(&g,10));
    printf("%d ",generator_next(&g,0));
    printf("%d ",generator_next(&g,6));
    printf("%d ",generator_next(&g,0));
    printf("%d ",generator_next(&g,0));
    printf("%d ",generator_next(&g,3));
    printf("%d ",generator_next(&g,0));
    printf("%d ",generator_next(&g,0));
}

На выходе получаем 0 1 7 0 6 9 0 3

Неудобство в передаче начальных параметров.

Вариант 2.
generator_t хранит те же данные, функции yield и generator_next такие же.
Но теперь объявляем функцию генератора с первым параметром generator_t в регистре Z (__z) и нужным числом аргументов и в начале функции после нужной инициализации вызывается generator_begin. Для старта генератора просто вызывается функция с начальными аргументами, а уже потом generator_next для получения очередного значения.
При инициализации структуры generator_t просто сохраняется младший байт указателя C_STACK. generator_begin определяет сколько регистров сохранила функция и вытаскивает их из C_STACK ( тут используется особенность IAR обычно использует регистры для локальных переменных в таком порядке R24 R25 R26 R27 R4 R5 …., а сохраняет их в стеке в обратном порядке)
Реализация:

Код

PUBLIC generator_begin
PUBLIC generator_init
generator_init:
                //сохраняем текущий C_STACK используется в generator_begin
                //для определения кол-ва сохраненных регистров
                std Z+2, YL
                ret

generator_begin:
                //получение адреса возврата из стека
                pop r19
                pop r18
                //сохранение следующей точки входа
                st Z+, r18
                st Z+, r19
                //r0 = кол-во сохраненных регистров
                mov r18, YL
                ld r0, Z
                sub r0, r18
                // сохраняем локальные регистры генератора
                st Z+, r24
                st Z+, r25
                st Z+, r26
                st Z+, r27
                st Z+, r4
                st Z+, r5
                //восстанавливаем регистры вызвавшей функции (заодно и указатель C_STACK)
                breq _ret
                ld r24, Y+
                dec r0
                breq _ret
                ld r25, Y+
                dec r0
                breq _ret
                ld r26, Y+
                dec r0
                breq _ret
                ld r27, Y+
                dec r0
                breq _ret
                ld r4, Y+
                dec r0
                breq _ret
                ld r5, Y+
_ret:     ret

Небольшой тест

Код

__z uint8_t generator_begin(generator_t *g, uint8_t ret);
__z void generator_init(generator_t *g);
__z uint8_t gen2(generator_t *g, char* buf, uint8_t len)
{
    uint8_t i,tmp;
    tmp = generator_begin(g,0);
    while(1) {
        while(tmp!='$')
            tmp=yield(0);
        i=0;
        while( (i<len) && ((tmp=yield(0))!='#'))
            buf[i++]=tmp;
        tmp = yield(i);
    }
}

char buf1[17];
char buf2[5];

__flash const char test[]="$12345$6789#";
void gen2_test(void)
{
    generator_t g1;
    generator_t g2;
    char __flash const *ptr;
    char c;
    uint8_t len;
    
    generator_init(&g1);
    generator_init(&g2);
    gen2(&g1,buf1,16);
    gen2(&g2,buf2,4);
    
    ptr = test;
    while((c=*ptr++)) {
        len=generator_next(&g1,c);
        if (len) {
            buf1[len]=0;
            printf("*1* %d:%s\n",(int)len,buf1);
        }
        len=generator_next(&g2,c);
        if (len) {
            buf2[len]=0;
            printf("*2* %d:%s\n",(int)len,buf2);
        }
    }
}

На выходе получаем:
*2* 4:1234
*2* 4:6789
*1* 10:12345$6789

Недостаток – очень сильная зависимость от реализации компилятора ( регистры могут использоваться в другом порядке)

[Rst7]

Недостаток – очень сильная зависимость от реализации компилятора ( регистры могут использоваться в другом порядке)

Я так извращался с setjmp/longjmp - выглядело примерно так

Код

#include <setjmp.h>
jmp_buf main_jmp;
jmp_buf process_jmp;

__task void process(void)
{
  for(;;)
  {
    .... step 1 ....
    if (!setjmp(process_jmp))  longjmp(main_jmp,1);
    .... step 2 ....
    if (!setjmp(process_jmp))  longjmp(main_jmp,1);
    .......
    if (!setjmp(process_jmp))  longjmp(main_jmp,1);
    .... step n ....
    if (!setjmp(process_jmp))  longjmp(main_jmp,1);
    .....
  }
}

__task void main(void)
{
   if (!setjmp(main_jmp))
   {
    SP=new_process_rstack;
    Y=new_process_cstack;
    __indirect_jump_to((unsigned long)process);
   }
   for(;;)
   {
     ....
     if (!setjmp(main_jmp)) longjmp(process_jmp,1); //Один шаг процесса
     ....
   }
}

Непереносима только инициализация потока. Остальное - так хоть на ARM

[KRS]

c setjmp нужно стек каждой ните

[Rst7]

Нужен. Но без него с более-менее универсальностью совсем туго...

[KRS]

1 варинат ( без передачи начальных значений как параметров функции). можно легко адаптировать что бы не было ограничений.
функция генератора объявлена как __task __noreturn поэтому в C_STACK сохраняет только локальные переменные (если они не помещаются в регистрах). В начале функции ставим вызов begin(вместо yield, который определит размер сохраняемого контекста как все регистры используемые как локальные переменные + то насколько вырос стек. А функция next ( обменивает регистры + запихивает в стек нужное число сохраненных в конексте данных)....
А инициализацию сделать примерно как в варианте 2 (сохранять указатель стека) + вызвать сразу функцию что бы остановилась в метсе вызова begin

Причем такое можно реализовать для любой архитектуры.
Если функция генератора довольно простая и вызвает функции с большой вложенностью можно здорово сэкономить на стеке ( потому что в контексте сохраняется только локальные переменные самого генератора, а вложенные функции используют обычный стек)

[KRS]

Сделал немного другой вариант, позволяет обойти все ограничения.
В LOCAL_REGS_R надо записать все регистры которые могут быть использованы под локальные переменные.
Причем asm функции не трогают регистры r16-r23 поэтому можно легко переопределить описания параметров и возвращаемых значений ( не модифицируя asm вообще)

Код

// цикл по сохраняемым регистрам
#define LOCAL_REGS_R REPTI _r, r24,r25,r26,r27,r4,r5

//обмен регистров
swap_locals     MACRO
                LOCAL_REGS_R    
                  ld r2, Z
                    st Z+, _r
                    mov _r,r2
                ENDR
                ENDM

        RSEG CODE:CODE:NOROOT(1)

//инициализация структуры generator_t и первый вызов функции для инициализации
PUBLIC generator_init
generator_init:
                //сохранение указателя на generator_t
                push ZH
                push ZL
                adiw ZL, 2 //пропускаем точку входа
                //сохраняем регистры
                LOCAL_REGS_R    
                    st Z+, _r
                ENDR
                
                //сохраняем текущий C_STACK используется в generator_begin
                //для определения размера
                st Z+, YL
                //ЗАПУСКАЕМ ГЕНЕРАТОР
                movw ZL, r16
                mov r16, r18
                ijmp
                
PUBLIC generator_next
generator_next:
                //сохранение указателя на generator_t
                push ZH
                push ZL

                //адрес возврата
                ld r0, Z+
                ld r1, Z+
                
                //обмен регистров
                swap_locals
                
                //размер используемого стека
                ld r2, Z+
                tst r2
                breq _jmp
                //загрузка в стек (обратный порядок)
                clr r3
                add ZL, r2
                adc ZH, r3
_loop:                
                ld r3, -Z
                st -Y, r3
                dec r2
                brne _loop
_jmp:
                //переход по сохраненному адресу
                movw ZL, r0
                ijmp

// generator_begin отличается от yield только тем, что вычисляет размер
// используемого стека
PUBLIC generator_begin
generator_begin:
                //получение адреса возврата из стека
                pop r1
                pop r0
                //получение сохраненнго указателя на generator_t
                pop ZL
                pop ZH

                //сохранение следующей точки входа
                st Z+, r0
                st Z+, r1

                //обмен регистров
                swap_locals

                //раситывам размер использованного стека
                ld r1, Z
              sub r1, YL
                st Z+, r1
                
                rjmp yield_entry

PUBLIC yield
yield:
                //получение адреса возврата из стека
                pop r1
                pop r0
                //получение сохраненнго указателя на generator_t
                pop ZL
                pop ZH
                //сохранение следующей точки входа
                st Z+, r0
                st Z+, r1

                //обмен регистров
                swap_locals
                
                //размер используемого стека
                ld r1, Z+
                tst r1

yield_entry:
                breq _ret
                //загрузка из стека
_loop1:                
                ld r0, Y+
                st Z+, r0
                dec r1
                brne _loop1
_ret:
                ret

                END

Простой тест:
Локальная переменная uint8_t queue[8] находится в стеке!

Код

#include <stdint.h>
#include <stdio.h>

typedef void (__task __version_3 *gfunc_ptr_t)(uint8_t c);
typedef struct {
    uint16_t entry;
    uint8_t saved_regs[6];
    uint8_t stack_len;
    uint8_t stack_data[16];
}generator_t;

uint8_t yield(uint8_t ret);
uint8_t generator_begin(uint8_t ret);

__z uint8_t generator_next(generator_t *g, uint8_t val);

__z void generator_init(generator_t *g,  gfunc_ptr_t entry, uint8_t val);

__task __noreturn
void gen1(uint8_t dummy)
{
    uint8_t queue[8];
    uint8_t i;
    uint16_t sum;
    uint8_t tmp;
    
    tmp = sum=queue[0]=generator_begin(0);
    printf("add data=%d\n",tmp);
    i=1;
    do {
        tmp = yield(0);
        sum+=queue[i]=tmp;
        printf("add data=%d\n",tmp);
    }while((i=(i+1) & 7));
    while(1) {
        tmp = yield(sum>>3);
        printf("add data=%d, remove data=%d\n",tmp,queue[i]);
        sum-=queue[i];
        sum+=queue[i]=tmp;
        i=(i+1) & 7;
    }
}
__flash const uint8_t seq[]={2,1,3,1,3,2,2,2,10,20,0};
void gen1_test(void)
{
    generator_t g;
    uint8_t __flash const *ptr;
    uint8_t c,v,i;
    ptr = seq;
    i=0;
    generator_init(&g,gen1,0);
    while((c=*ptr++)) {
        i++;
        v=generator_next(&g,c);
        if (v) {
            printf("%d %d\n",i,v);
        }
    }
}

__C_task __noreturn
void main(void)
{
    gen1_test();
}

Листинг:

Код

   \                                 In  segment CODE, align 2, keep-with-next
     19          __task __noreturn
     20          void gen1(uint8_t dummy)
   \                     gen1:
     21          {
   \   00000000   9728               SBIW    R29:R28, 8
     22              uint8_t queue[8];
     23              uint8_t i;
     24              uint16_t sum;
     25              uint8_t tmp;
     26              
     27              tmp = sum=queue[0]=generator_begin(0);
   \   00000002   E000               LDI     R16, 0
   \   00000004   ........           CALL    generator_begin
   \   00000008   8308               ST      Y, R16
   \   0000000A   2F80               MOV     R24, R16
   \   0000000C   E090               LDI     R25, 0
     28              printf("add data=%d\n",tmp);
   \   0000000E   939A               ST      -Y, R25
   \   00000010   930A               ST      -Y, R16
   \   00000012   ....               LDI     R16, LOW(`?<Constant "add data=%d\\n">`)
   \   00000014   ....               LDI     R17, (`?<Constant "add data=%d\\n">`) >> 8
   \   00000016   ........           CALL    printf
   \   0000001A   9622               ADIW    R29:R28, 2
     29              i=1;
   \   0000001C   2444               CLR     R4
   \   0000001E   9443               INC     R4
     30              do {
     31                  tmp = yield(0);
   \                     ??gen1_0:
   \   00000020   E000               LDI     R16, 0
   \   00000022   ........           CALL    yield
     32                  sum+=queue[i]=tmp;
   \   00000026   01FE               MOVW    R31:R30, R29:R28
   \   00000028   2455               CLR     R5
   \   0000002A   0DE4               ADD     R30, R4
   \   0000002C   1DF5               ADC     R31, R5
   \   0000002E   8300               ST      Z, R16
   \   00000030   0F80               ADD     R24, R16
   \   00000032   1D95               ADC     R25, R5
     33                  printf("add data=%d\n",tmp);
   \   00000034   925A               ST      -Y, R5
   \   00000036   930A               ST      -Y, R16
   \   00000038   ....               LDI     R16, LOW(`?<Constant "add data=%d\\n">`)
   \   0000003A   ....               LDI     R17, (`?<Constant "add data=%d\\n">`) >> 8
   \   0000003C   ........           CALL    printf
   \   00000040   9622               ADIW    R29:R28, 2
     34              }while((i=(i+1) & 7));
   \   00000042   9443               INC     R4
   \   00000044   E007               LDI     R16, 7
   \   00000046   2240               AND     R4, R16
   \   00000048   F759               BRNE    ??gen1_0
     35              while(1) {
     36                  tmp = yield(sum>>3);
   \                     ??gen1_1:
   \   0000004A   018C               MOVW    R17:R16, R25:R24
   \   0000004C   9516               LSR     R17
   \   0000004E   9507               ROR     R16
   \   00000050   9516               LSR     R17
   \   00000052   9507               ROR     R16
   \   00000054   9516               LSR     R17
   \   00000056   9507               ROR     R16
   \   00000058   ........           CALL    yield
   \   0000005C   2E60               MOV     R6, R16
     37                  printf("add data=%d, remove data=%d\n",tmp,queue[i]);
   \   0000005E   01DE               MOVW    R27:R26, R29:R28
   \   00000060   0DA4               ADD     R26, R4
   \   00000062   1DB5               ADC     R27, R5
   \   00000064   908C               LD      R8, X
   \   00000066   925A               ST      -Y, R5
   \   00000068   928A               ST      -Y, R8
   \   0000006A   925A               ST      -Y, R5
   \   0000006C   930A               ST      -Y, R16
   \   0000006E   ....               LDI     R16, LOW((`?<Constant "add data=%d\\n">` + 13))
   \   00000070   ....               LDI     R17, HIGH((`?<Constant "add data=%d\\n">` + 13))
   \   00000072   ........           CALL    printf
   \   00000076   9624               ADIW    R29:R28, 4
     38                  sum-=queue[i];
   \   00000078   1988               SUB     R24, R8
   \   0000007A   4090               SBCI    R25, 0
     39                  sum+=queue[i]=tmp;
   \   0000007C   926C               ST      X, R6
   \   0000007E   0D86               ADD     R24, R6
   \   00000080   1D95               ADC     R25, R5
     40                  i=(i+1) & 7;
   \   00000082   9443               INC     R4
   \   00000084   E007               LDI     R16, 7
   \   00000086   2240               AND     R4, R16
   \   00000088   CFE0               RJMP    ??gen1_1
     41              }
     42          }

вывод:

Код

add data=2
add data=1
add data=3
add data=1
add data=3
add data=2
add data=2
add data=2
8 2
add data=10, remove data=2
9 3
add data=20, remove data=1
10 5

IMHO если писать генератор так что бы использование стека было минимальным (локальные перменные в регистрах и для сохранения блоков данных использовать указатели…) получается довольно быстрое переключение с минимальным оверхедом.