如何评价 mimalloc？ 第1页

实时系统（RTOS）上用过mimalloc，看了一些mimalloc代码，还调试过一些相关的bug，说点感受：

mimalloc用原子操作而不是锁来做关键数据的保护，原子操作的开销比锁要小很多，所以性能会好很多。在X86上，一个原子操作最糟糕的情况也就是100个cycle左右（SMP），优化的足够好的话30个cycle就可以搞定，而如果使用操作系统自带的锁操作，涉及到函数调用以后开销至少是几百上千cycle。所以精心设计的原子操作性能会比用锁实现的库要快很多倍。

但原子操作也有一个很大的问题：死锁，尤其是在RTOS上，非RT的系统里，不同优先级的任务都可能会得到调度，但RTOS里，调度器会优先调度高优先级的任务，而原子操作本身不具备检测优先级翻转的机制，一旦某个低优先级任务持有了原子操作的某些数值（可以理解为锁），那么高优先级任务可能会被阻塞，并有可能死锁。

性能和实时性在某些场景中是会有冲突的，为了实时性有时候需要牺牲一部分性能。比如mimalloc这个库，如果要考虑到RTOS中的死锁问题，那么就可能需要增加一些延迟、把原子操作改成锁，通过牺牲性能来换取RTOS中的实时性调度。

有人可能不理解为什么在RTOS里会死锁，我还是拿代码来描述一下（顺便说一句，这个问题，正好就是我前一段debug时候遇到的），版本是1.6.7：

任务A正在free内存，调用栈：
mi_free -> mi_free_generic -> _mi_free_block -> _mi_free_block_mt

在函数_mi_free_block_mt中会有一个原子操作：
tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING);

代码链接：https://github.com/microsoft/mimalloc/blob/master/src/alloc.c#L367

         do {     use_delayed = (mi_tf_delayed(tfree) == MI_USE_DELAYED_FREE);     if (mi_unlikely(use_delayed)) {       // unlikely: this only happens on the first concurrent free in a page that is in the full list       tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING);     }     else {       // usual: directly add to page thread_free list       mi_block_set_next(page, block, mi_tf_block(tfree));       tfreex = mi_tf_set_block(tfree,block);     }   } while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));     

此时如果一个高优先级任务B触发并调度，在RTOS中，高优先级任务持续运行的情况下，低优先级任务A是不会被调度的。

B的调用栈：
_mi_heap_malloc_zero -> _mi_malloc_generic -> mi_heap_delayed_free -> _mi_free_delayed_block -> _mi_page_use_delayed_free

注意_mi_page_use_delayed_free这里有一个do while的循环，这个循环的核心操作就是等待tfree不等于MI_DELAYED_FREEING，非RTOS里，这么做没问题。

代码链接：https://github.com/microsoft/mimalloc/blob/master/src/page.c#L128

       void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) {   mi_thread_free_t tfreex;   mi_delayed_t     old_delay;   mi_thread_free_t tfree;     do {     tfree = mi_atomic_load_acquire(&page->xthread_free); // note: must acquire as we can break/repeat this loop and not do a CAS;     tfreex = mi_tf_set_delayed(tfree, delay);     old_delay = mi_tf_delayed(tfree);     if (mi_unlikely(old_delay == MI_DELAYED_FREEING)) {       mi_atomic_yield(); // delay until outstanding MI_DELAYED_FREEING are done.       // tfree = mi_tf_set_delayed(tfree, MI_NO_DELAYED_FREE); // will cause CAS to busy fail     }     else if (delay == old_delay) {       break; // avoid atomic operation if already equal     }     else if (!override_never && old_delay == MI_NEVER_DELAYED_FREE) {       break; // leave never-delayed flag set     }   } while ((old_delay == MI_DELAYED_FREEING) ||            !mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex)); }     

问题出在RTOS上，在RTOS里，任务B会一直卡在_mi_page_use_delayed_free函数的while循环里，而任务A又因为得不到调度，没办法把_mi_free_block_mt跑完，这就意味着tfree的值一直无法改变。

然后就死锁了，实际上CPU此时一直在任务B里忙着跑while循环，然而无济于事。非RTOS里，即使任务B比任务A优先级高，任务A仍然有一定机会可以跑，但到了RTOS里，任务A没有任何机会。

所以回到我前面的结论，mimalloc的有些代码没有考虑RTOS的使用场景。

注：核心问题是RTOS里delay并不一定能真的触发低优先级调度，很多时候只会造成reschedule，当然，也可以用类似sleep的方法，但这样有可能会造成恶劣的性能影响。

原子操作很快，比锁快，但无法检测优先级翻转。

有人会说操作系统的锁的实现就是用原子操作，这种说法是对的，锁的操作是要使用原子操作，但并不代表锁的操作只用到了原子操作。一个典型的操作系统级别的锁，在SMP的环境里，首先要判断当前的状态（是否在中断上下文），然后发起一个多核的锁的广播，这里会有多个CAS的原子操作，因为多个核心上可能有多个任务同时发起锁的请求。通过精心设计的CAS可以让某个核最终获得所有的核心（具体去看RTOS代码吧），这样所有核心的状态一致了，再用一个原子操作去调整锁的状态，同时检查其他核心上的任务优先级，以及锁本身的优先级等待，把任务重新排队，一切就绪以后，才释放多核的锁。

而对于普通的原子操作，硬件上只有一条CAS指令。

锁要比原子操作复杂的多，但也能监测并解决更多的问题（比如优先级翻转等）。