# Hungry Birds
contribute by <`kobeyu`>

[github](https://github.com/kobe0308/hungry-birds.git)

>>github連結以幫忙更新在分組頁面
>>[color=red][name=課程助教]
## 作業目標
- [ ] 解析原始碼
- [ ]
---

## 解析程式碼

### 目錄結構
>> directory 翻譯是「目錄」，不是「檔案夾」(folder) [name=jserv]

.
├── LICENSE
├── Makefile
├── pc-test.c
├── queue.c
├── queue.h
└── README.md

0 directories, 6 files

#### Makefile
* C11

CFLAGS = -std=c11 -Wall -g

---
>>中英文關鍵字中間請以空白區隔
>>[color=red][name=課程助教]
#### queue
queue是透過link list把物件連接起來,所以在push的時候會malloc宣告一個記憶體空間,[這篇文章]((http://www.fi.muni.cz/~xbarnat/IV112/fifos.pdf))提到優點是容易實現以及記憶體空間允許的情況下是沒有數量限制的,但缺點是速度較慢(malloc不是lock free),比較差的data locality以及需要額外的空間儲存資料.

#### queue.h
.h檔中宣告了queue_p的結構以及__QUEUE_API__介面,queue_p作為內部使用,所以宣告在.h檔,定義則是在.c檔之中.
__QUEUE_API__則是提供了操作queue的function:

* queue_p (*create)(size_t size);
* QueueResult (*push)(queue_p, void *data);
* QueueResult (*hasFront)(queue_p);
* QueueResult (*front)(queue_p, void *data);
* QueueResult (*pop)(queue_p);
* QueueResult (*clear)(queue_p);
* QueueResult (*destroy)(queue_p);

透過extern的關鍵字,可以在.c中定義:

/* API gateway */
struct __QUEUE_API__ Queue = {
    .create = queue_create,
    .hasFront = queue_has_front,
    .front = queue_front,
    .pop = queue_pop,
    .push = queue_push,
    .clear = queue_clear,
    .destroy = queue_destroy,
};

---
#### queue.c

* alignment
alignment是為了sentinel所宣告的,只有一個地方有用到,我是認為可以拿掉alignment用sizeof(size_t)取代.

static const size_t sentinel = 0xdeadc0de;
static const size_t alignment = sizeof(size_t);

why 0xdeadc0de [Hexspeak](https://en.wikipedia.org/wiki/Hexspeak)

* 記憶體空間的守衛

size_t *ptr = calloc(sizeof(struct __QueueInternal) + alignment, 1);
ptr[0] = sentinel;
queue_p q = (queue_p)(ptr + 1);

size_t *ptr = (size_t*)q - 1;
    assert(ptr[0] == sentinel);
    free(ptr);

* syntax sugar
第24行可以用這行取代：

queue_p q = (queue_p)&ptr[1];

Swift把這一點發揮的淋漓盡致,可以自定義subscript取值的方式 [link](subscript)

---
#### pc-test.c
程式中有一個queue的物件,在stress test中,有一個消費者,有許多的生產者,透過queue做task的緩衝與排程.

---
#### #include <stdatomic.h>
程式中atomic operation是使用[C11](https://en.wikipedia.org/wiki/C11_(C_standard_revision))的標準函式庫,在規格書中的7.17節中有詳細的描述,為了要了解在程式中為什麼用怎麼用,所以這邊跳開程式先閱讀c語言規格書的說明.

##### Atomic Data Type

* atomic_uintptr_t

##### Atomic API

* atomic_init
* atomic_load
* atomic_store
* atomic_exchange
* atomic_compare_exchange_strong

---
#### 執行結果
$ make
cc -std=c11 -Wall -g -c -MMD -MF .pc-test.o.d -o pc-test.o pc-test.c
cc -std=c11 -Wall -g -c -MMD -MF .queue.o.d -o queue.o queue.c
cc -o pc-test pc-test.o queue.o -lpthread

$ ./pc-test
** Basic operations **
Verified OK!

** Stress test **
Verified OK!

---

### 分析重點

* 如何驗證在各種情況下queue都能夠正常運作
* 列出可能的使用情境
* 不同的執行環境(cpu)
* 分析malloc的影響(C makes no guarantees that malloc() is lock-free)及其對策
* Circular Buffer(bounded queue) 但wirter可能因為buffer size的限制被block
* 對於queue能否有更好的封裝,具體目標是拿掉pc-test.c中的#include <stdatomic.h>
* atomic operation是否還會有與cache coherence的問題?atomic operation存取的是虛擬記憶體,對應到實體是在哪個level的cache?L1/L2/L3/MM/Disk?
* 效能指標
* lantency : queue ops at
* different cpu
* the same cpu, different core
* the same core, different contex
* Scalability : when many queues are used

### bugs

## 參考資料

#### lock-free stack
* C makes no guarantees that malloc() is lock-free, so being truly lock-free means not calling malloc()
note: although malloc is thread safety function.

##### Hazard pointer
* Each thread keeps track of what nodes it’s currently accessing and other threads aren’t allowed to free nodes on this list. This is messy and complicated.

##### strong vs weak
* The “weak” part means it will sometimes spuriously fail where the “strong” version would otherwise succeed. In exchange for more failures, calling the weak version is faster. Use the weak version when the body of your do ... while loop is fast and the strong version when it’s slow (when trying again is expensive), or if you don’t need a loop at all. You usually want to use weak.

[ref](http://stackoverflow.com/questions/17914630/when-should-stdatomic-compare-exchange-strong-be-used)

##### memory ordering

[ref](http://wilburding.github.io/blog/2013/04/07/c-plus-plus-11-atomic-and-memory-model/)

#### ABA Problem

#### memory barrier

---
ATOMIC OPERATION [WilburDing's Blog](http://wilburding.github.io/blog/2013/04/07/c-plus-plus-11-atomic-and-memory-model/)

C++11 CH29 關於Atomic Operation [spec.](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf)

[Shared-Memory Synchronization](https://books.google.com.tw/books?id=7a9dAQAAQBAJ)

[lock-free stack](http://nullprogram.com/blog/2014/09/02/)

[Scalable Lock-Free Dynamic Memory Allocation - pdf](http://www.research.ibm.com/people/m/michael/pldi-2004.pdf)

[IBM atomic function](https://www.ibm.com/support/knowledgecenter/SSLTBW_2.1.0/com.ibm.zos.v2r1.cbclx01/atomic_func.htm)

[anothe queue(also implement by c11 atomic)](https://github.com/skeeto/lqueue.git)

[level of parallel programming](http://www.cnblogs.com/jiayy/p/3246167.html)

[atomic weapons](https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2)

[FIFO](http://www.fi.muni.cz/~xbarnat/IV112/fifos.pdf)

[An efficient Unbounded Lock-Free Queue for Multi-Core Systems](http://calvados.di.unipi.it/storage/talks/2012_SPSC_Europar.pdf)

[Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation](http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf)

[memory barrier](http://www.wowotech.net/kernel_synchronization/memory-barrier.html)

[memory barrier in lock api](http://reborn2266.blogspot.tw/2013/03/memory-barrier-in-lock-api.html)

>> fast multi-producer, multi-consumer lock-free concurrent queue: https://github.com/cameron314/concurrentqueue [name=jserv]