CA project 状态分析&debug
coconutnut
 2021-12-16 20:49:38      

上次CA project 思路笔记分析一个位置是否可以读写的状态：

但是在project测试过程中发现有问题。

问题

按照Atomic control的逻辑写了read_align()和write_align()。

read_align中判断Written==0时，如果没有owner、或者owner是自己，可以写。

1
2
3
4
5
6
7
8
9
if(owner==0 || owner==tr->id){
  uint_least64_t not_written = owner << 32 | epoch | valid;
  if(atomic_compare_exchange_strong(cur_control, &not_written, written_and_is_owner)){
    // write the content at source into the writable copy;
    write_writable_copy(source, segment, index);
    // return the transaction can continue;
    flag = true;
  }
}

但是测试时，transaction量一两千还能过，10000就过不了了。

反而↓这样可以过：

1
2
3
4
5
6
if(atomic_compare_exchange_strong(cur_control, &load_control, written_and_is_owner)){
  // write the content at source into the writable copy;
  write_writable_copy(source, segment, index);
  // return the transaction can continue;
  flag = true;
}

但是它并不符合原本的思路，因为可能会将第一个读成功的owner覆盖。就很奇怪。

重读

感觉会有问题的很可能是access set，上次分析只用记录第一个读或写成功的id，但是为什么实际中即使写覆盖了读也可以成功呢？

假设在某一个align，tr1、tr2读了旧值，此时如果tr3写了新值，tr1、tr2以及任何除tr3以外的transaction都不能再读。也就是说，写过的位置，只有写者可读。这其实是符合read_word()伪代码的。并且，如果tr1、tr2后面不再读这个值，可以提交并linearize到tr3开始之前；反之，如果它们后面还要读这个值，就会读失败，进而被abort。所以也是符合linearizable的。

难道access set只用记录第一个写成功的？上次跟TA确认了一下，access set只用记一个id，似乎确实没仔细问是第一个读成功、还是写成功。

那么按照新的逻辑分析，第一个读或写成功，还是都记入owner，只不过读成功的owner可以被覆盖。

可如果能够覆盖，read owner和other还有什么用呢？（其实现在这版代码里面也压根没用到other）如果直接把read_align中设置owner和other的代码注释掉，还能跑吗？

1
2
3
4
5
⎪ #worker threads:     4
⎪ #TX per worker:      10000
⎪ #repetitions:        7
⎪ Initial #accounts:   128
⎪ Expected #accounts:  1024

…用↑参数测了几次，多数能过，少数Violated isolation or atomicity。也就是说other还是有用的。

再看下project description中对access set的描述：

The “access set” of read-write transaction(s) which have accessed the word in the current epoch. Do not implement an actual set in any (optimized) implementation: this set will only be used to tell whether a transaction can write to the word. Namely, if at least one other transaction has accessed (i.e. read or written) this word in the same epoch, the write cannot happen. Said differently, if two transactions are in the access set, it doesn’t matter which one they are.

现在迷惑的点就是：

  1. 如果有另一个transaction也访问过，还能不能写？
  2. 现在的代码里到底判断了other没？

2应该是没有的，加个输出可以发现，即使有other还是有时写成功了。那为什么可以过呢？难道是意外？多测几次还真偶尔有Violated isolation or atomicity！

好吧，虽然project又变成了未完成状态，但至少没有逻辑错的代码能跑对、逻辑(以为)对的代码跑不通的尴尬情况了。

那么接下来的问题就是，为什么逻辑(以为)对的代码跑不通？更准确的是，为什么在transaction量较大时跑不通？

Debug

CAS fail when equal

打印了一些tm_begin和tm_end的信息，发现当transaction进行了很多、id很大之后，只有tm_begin没有tm_end了，也就是说后面的都没有commit。并且都是一些read/write transaction，它们的write都没有成功。

1
2
3
4
5
6
7
8
9
...
[304850 write align] seg_id=8 index=1 flag=0
[304851 tm_begin] is_ro=0
[304821 write align] seg_id=8 index=1 flag=0
[304852 tm_begin] is_ro=0
[304833 write align] seg_id=8 index=1 flag=0
[304853 tm_begin] is_ro=0
[304836 write align] seg_id=8 index=1 flag=0
...

发现有一个CAS中，明明expected值和control中的值是一样的，但是没有换成功。

1
atomic_compare_exchange_strong(cur_control, &not_written, written_and_is_owner)
1
not_written=5e0cb00000005 load_control=5e0cb00000005 cur_control=5e0cb00000005 equal=1

这可就太离谱了！

compare_exchange_strong failing despite data matching expected value

Why does compare_exchange_strong fail with std::atomic, std::atomic in C++?

可能是由padding导致的。这就很尴尬了。

尝试1

1
uint_least64_t not_written = owner << 32 | valid;

改成

1
uint_least64_t not_written = load_control & 0xFFFFFFFFFFFFFFF9;

不行

尝试2

这是真的很离谱啊！打印出来的判断就是相等啊！这换不了能怎么办啊？？？

1
printf("DEBUG4 not_written=%lx load_control=%lx cur_control=%lx equal=%d test=%d\n", not_written, load_control, load, not_written==load, atomic_load(cur_control)==not_written);
1
2
3
4
5
6
7
DEBUG4 not_written=3e1a300000005 load_control=3e1a300000005 cur_control=3e1a300000005 equal=1 test=1
[254371 write align] seg_id=8 index=1 flag=0 cond=4
[254373 tm_begin] is_ro=0
DEBUG4 not_written=3e1a400000005 load_control=3e1a400000005 cur_control=3e1a400000005 equal=1 test=1
[254372 write align] seg_id=8 index=1 flag=0 cond=4
[254374 tm_begin] is_ro=0
DEBUG4 not_written=3e1a500000005 load_control=3e1a500000005 cur_control=3e1a500000005 equal=1 test=1

难道是uint_least64_t的问题？它和memcpy的比较方法不一样？

1
size_t a = (size_t)not_written;

强制转成size_t然后比就好了？？？那之前担心位数不对，还特地搞个uint_least64_t，简直是离了个大谱。

too long

改好上面这个离谱的bug之后，当transaction太多还是会跑不完。打印输出看还是write_align不成功。

1
2
3
4
5
6
7
8
9
10
[370371 tm_begin] is_ro=0
[370371 write align] seg_id=8 index=1 flag=0 cond=4 lc=5a6c300000005, cc=5a6c300000005
[370372 tm_begin] is_ro=0
[370372 write align] seg_id=8 index=1 flag=0 cond=4 lc=5a6c400000005, cc=5a6c400000005
[370373 tm_begin] is_ro=0
[370373 write align] seg_id=8 index=1 flag=0 cond=4 lc=5a6c500000005, cc=5a6c500000005
[370374 tm_begin] is_ro=0
[370374 write align] seg_id=8 index=1 flag=0 cond=4 lc=5a6c600000005, cc=5a6c600000005
[370375 tm_begin] is_ro=0
[370375 write align] seg_id=8 index=1 flag=0 cond=4 lc=5a6c700000005, cc=5a6c700000005

全部都是有other read冲突

1
2
3
4
5
6
7
8
9
[215647 read align] seg_id=7 index=0 lc=0 cc=34a5f00000000
[215647 read align] seg_id=7 index=1 lc=1 cc=34a5f00000001
[215647 read align] seg_id=8 index=0 lc=0 cc=34a5f00000000
[215647 read align] seg_id=8 index=1 lc=1 cc=34a5f00000001
[215647 read align] seg_id=9 index=0 lc=1 cc=34a5f00000001
[215647 read align] seg_id=9 index=1 lc=0 cc=34a5f00000000
[215647 read align] seg_id=9 index=2 lc=0 cc=34a5f00000000
[215647 read align] seg_id=9 index=3 lc=1 cc=34a5f00000001
[215647 read align] seg_id=8 index=1 lc=34a5f00000001 cc=34a5f00000005

发现一个逻辑错误，owner是自己时仍设了other。

这下算是修了一个逻辑上的大bug，再上服务器测测。

成功！虽然没有变快，但至少逻辑上合理了，不像之前那么虚了。

所以之前那么大一个bug是怎么过的测试啊就离谱，今天真是满头问号。而且之前逻辑都没对就写优化，那可不是写了个寂寞。幸亏优化的思路现在是很清晰了，毕竟revert、重写都搞了好几遍了。虽然不知道这些优化到底能不能正向优化，但还是想试试，就是很好奇，而且毕竟都花了这么多时间了。

顺便把Atomic control更新一下。

总结

  1. reference的逻辑还是很正确的
  2. bug确实是自己写的bug
  3. 除了c的atomic_compare_exchange_strong，值较大时，期望值和实际值一样但换不成功，是真的离谱