CA project Atomic control
coconutnut
 2021-12-15 17:37:29      

Project中为了标识transactional memory中每一个align的状态，需要一个control structure，这里用了一个64bit的atomic interger来存这些信息。

通过一次CAS完成对状态的判断和修改，避免加锁。

Control设计

占用bit 32 20 9 1 1 1
名称 Owner Epoch 留空 Other Written Valid
描述 本轮第一个read或write成功的transaction的id 当前轮数 是否有其它transaction访问 是否被写 A或B哪个有效

Control masks

1
2
3
4
static const size_t VALID_MASK = 0x1;         // 0: A is valid    1: B is valid
static const size_t WRITE_MASK = 0x1 << 1;    // 0: not written   1: written
static const size_t OTHER_MASK = 0x1 << 2;    // 0: no other read 1: has other read
static const size_t EPOCH_MASK = 0xFFFFF000;

Control macros

有时需要直接读atomic interger。其他时候，先读一次，然后直接对读到的值进行操作，可以减少atomic_load()次数。

1
2
3
4
5
6
#define GET_FLAG_SIGN(control, flag) ((atomic_load(control) & flag) != 0)
#define GET_FLAG_SIGN_LOADED(load_control, flag) ((load_control & flag) != 0)
#define GET_FLAG_LOADED(load_control, flag) (load_control & flag)
#define GET_EPOCH_LOADED(load_control) (load_control & EPOCH_FLAG)
#define GET_OWNER(control) ((atomic_load(control)) >> 32)
#define GET_OWNER_LOADED(load_control) (load_control >> 32)

read_align逻辑

  1. If 已经被写过，只有owner可以读（且Other应该为空，因为Other和Written不肯能同时为1）

    1
    Expected: Owner==id; Epoch==epoch; Other==0; Written==1; Valid==valid

  2. If 没有被写过

    1. If owner==0，尝试抢占（可能会出现竞争而失败）

      1
      2
      Expected: Owner==0;  Epoch==epoch; Other==0; Written==0; Valid==valid
      Desired:  Owner==id; Epoch==epoch; Other==0; Written==0; Valid==valid

    2. Else if owner==自己，直接读（owner不会被修改，也只有自己可能写）

    3. Else if owner==别人

      1. If 尝试设Other

        1
        2
        Expected: Owner==owner; Epoch==epoch; Other==0; Written==0; Valid==valid
        Desired:  Owner==owner; Epoch==epoch; Other==1; Written==0; Valid==valid

      2. Else if 读到已经被设了Other

        1
        Expected: Owner==owner; Epoch==epoch; Other==1; Written==0; Valid==valid

        如果读到Other为1，owner也不能再写这个align了，所以可以放心读。

write_align逻辑

  1. If 已经被写过，只有owner可以写，且不能有other

    1
    Expected: Owner==id; Epoch==epoch; Other==0; Written==1; Valid==valid

  2. If 没有被写过

    1. 已经是owner可以写

      1
      2
      Expected: Owner==id; Epoch==epoch; Other==0; Written==0; Valid==valid
      Desired:  Owner==id; Epoch==epoch; Other==0; Written==1; Valid==valid

    2. 抢到owner可以写

      1
      2
      Expected: Owner==0;  Epoch==epoch; Other==0; Written==0; Valid==valid
      Desired:  Owner==id; Epoch==epoch; Other==0; Written==1; Valid==valid

Note：如果写成功了，本轮中control的值将不会再发生改变