狠狠色婷婷久久一区二区,国产视频久久,久久99久国产麻精品66

2015年7月4日 #

寫了一個分布式名字服務JCM

之前在公司里維護了一個名字服務，這個名字服務日常管理了近4000臺機器，有4000個左右的客戶端連接上來獲取機器信息，由于其基本是一個單點服務，所以某些模塊接近瓶頸。后來倒是有重構計劃，詳細設計做了，代碼都寫了一部分，結果由于某些原因重構就被終止了。

JCM是我業余時間用Java重寫的一個版本，功能上目前只實現了基礎功能。由于它是個完全分布式的架構，所以理論上可以橫向擴展，大大增強系統的服務能力。

名字服務

在分布式系統中，某個服務為了提升整體服務能力，通常部署了很多實例。這里我把這些提供相同服務的實例統稱為集群(cluster)，每個實例稱為一個節點(Node)。一個應用可能會使用很多cluster，每次訪問一個cluster時，就通過名字服務獲取該cluster下一個可用的node。那么，名字服務至少需要包含的功能：

根據cluster名字獲取可用的node
對管理的所有cluster下的所有node進行健康度的檢測，以保證始終返回可用的node

有些名字服務僅對node管理，不參與應用與node間的通信，而有些則可能作為應用與node間的通信轉發器。雖然名字服務功能簡單，但是要做一個分布式的名字服務還是比較復雜的，因為數據一旦分布式了，就會存在同步、一致性問題的考慮等。

What’s JCM

JCM圍繞前面說的名字服務基礎功能實現。包含的功能：

管理cluster到node的映射
分布式架構，可水平擴展以實現管理10,000個node的能力，足以管理一般公司的后臺服務集群
對每個node進行健康檢查，健康檢查可基于HTTP協議層的檢測或TCP連接檢測
持久化cluster/node數據，通過zookeeper保證數據一致性
提供JSON HTTP API管理cluster/node數據，后續可提供Web管理系統
以庫的形式提供與server的交互，庫本身提供各種負載均衡策略，保證對一個cluster下node的訪問達到負載均衡

項目地址git jcm

JCM主要包含兩部分：

jcm.server，JCM名字服務，需要連接zookeeper以持久化數據
jcm.subscriber，客戶端庫，負責與jcm.server交互，提供包裝了負載均衡的API給應用使用

架構

基于JCM的系統整體架構如下：

cluster本身是不需要依賴JCM的，要通過JCM使用這些cluster，只需要通過JCM HTTP API注冊這些cluster到jcm.server上。要通過jcm.server使用這些cluster，則是通過jcm.subscriber來完成。

使用

可參考git READMe.md

需要jre1.7+

啟動zookeeper
下載jcm.server git jcm.server-0.1.0.jar
在jcm.server-0.1.0.jar目錄下建立config/application.properties文件進行配置，參考config/application.properties
啟動jcm.server
```
 java -jar jcm.server-0.1.0.jar
```

注冊需要管理的集群，參考cluster描述：doc/cluster_sample.json，通過HTTP API注冊：

 curl -i -X POST http://10.181.97.106:8080/c -H "Content-Type:application/json" --data-binary @./doc/cluster_sample.json

部署好了jcm.server，并注冊了cluster后，就可以通過jcm.subscriber使用：

// 傳入需要使用的集群名hello9/hello，以及傳入jcm.server地址，可以多個：127.0.0.1:8080
Subscriber subscriber = new Subscriber( Arrays.asList("127.0.0.1:8080"), Arrays.asList("hello9", "hello"));
// 使用輪詢負載均衡策略
RRAllocator rr = new RRAllocator();
subscriber.addListener(rr);
subscriber.startup();
for (int i = 0; i < 2; ++i) {
  // rr.alloc 根據cluster名字獲取可用的node
  System.out.println(rr.alloc("hello9", ProtoType.HTTP));
}
subscriber.shutdown();

JCM實現

JCM目前的實現比較簡單，參考模塊圖：

impl-module

model，即cluster/node這些數據結構的描述，同時被jcm.server和jcm.subscriber依賴
storage，持久化數據到zookeeper，同時包含jcm.server實例之間的數據同步
health check，健康檢查模塊，對各個node進行健康檢查

以上模塊都不依賴Spring，基于以上模塊又有：

http api，使用spring-mvc，包裝了一些JSON HTTP API
Application，基于spring-boot，將各個基礎模塊組裝起來，提供standalone的模式啟動，不用部署到tomcat之類的servlet容器中

jcm.subscriber的實現更簡單，主要是負責與jcm.server進行通信，以更新自己當前的model層數據，同時提供各種負載均衡策略接口：

subscriber，與jcm.server通信，定期增量拉取數據
node allocator，通過listener方式從subscriber中獲取數據，同時實現各種負載均衡策略，對外統一提供alloc node的接口

接下來看看關鍵功能的實現

數據同步

既然jcm.server是分布式的，每一個jcm.server instance(實例)都是支持數據讀和寫的，那么當jcm.server管理著一堆cluster上萬個node時，每一個instance是如何進行數據同步的？jcm.server中的數據主要有兩類：

cluster本身的數據，包括cluster/node的描述，例如cluster name、node IP、及其他附屬數據
node健康檢查的數據

對于cluster數據，因為cluster對node的管理是一個兩層的樹狀結構，而對cluster有增刪node的操作，所以并不能在每一個instance上都提供真正的數據寫入，這樣會導致數據丟失。假設同一時刻在instance A和instance B上同時對cluster c1添加節點N1和N2，那么instance A寫入c1(N1)，而instance B還沒等到數據同步就寫入c1(N2)，那么c1(N1)就被覆蓋為c1(N2)，從而導致添加的節點N1丟失。

所以，jcm.server instance是分為leader和follower的，真正的寫入操作只有leader進行，follower收到寫操作請求時轉發給leader。leader寫數據優先更新內存中的數據再寫入zookeeper，內存中的數據更新當然是需要加鎖互斥的，從而保證數據的正確性。

leader和follower是如何確定角色的？這個很簡單，標準的利用zookeeper來進行主從選舉的實現。

jcm.server instance數據間的同步是基于zookeeper watch機制的。這個可以算做是一個JCM的一個瓶頸，每一個instance都會作為一個watch，使得實際上jcm.server并不能無限水平擴展，擴展到一定程度后，watch的效率就可能不足以滿足性能了，參考zookeeper節點數與watch的性能測試 (那個時候我就在考慮對我們系統的重構了) 。

jcm.server中對node健康檢查的數據采用同樣的同步機制，但node健康檢查數據是每一個instance都會寫入的，下面看看jcm.server是如何通過分布式架構來分擔壓力的。

健康檢查

jcm.server的另一個主要功能的是對node的健康檢查，jcm.server集群可以管理幾萬的node，既然已經是分布式了，那么顯然是要把node均分到多個instance的。這里我是以cluster來分配的，方法就是簡單的使用一致性哈希。通過一致性哈希，決定一個cluster是否屬于某個instance負責。每個instance都有一個server spec，也就是該instance對外提供服務的地址(IP+port)，這樣在任何一個instance上，它看到的所有instance server spec都是相同的，從而保證在每一個instance上計算cluster的分配得到的結果都是一致的。

健康檢查按cluster劃分，可以簡化數據的寫沖突問題，在正常情況下，每個instance寫入的健康檢查結果都是不同的。

健康檢查一般以1秒的頻率進行，jcm.server做了優化，當檢查結果和上一次一樣時，并不寫入zookeeper。寫入的數據包含了node的完整key (IP+Port+Spec)，這樣可以簡化很多地方的數據同步問題，但會增加寫入數據的大小，寫入數據的大小是會影響zookeeper的性能的，所以這里簡單地對數據進行了壓縮。

健康檢查是可以支持多種檢查實現的，目前只實現了HTTP協議層的檢查。健康檢查自身是單個線程，在該線程中基于異步HTTP庫，發起異步請求，實際的請求在其他線程中發出。

jcm.subscriber通信

jcm.subscriber與jcm.server通信，主要是為了獲取最新的cluster數據。subscriber初始化時會拿到一個jcm.server instance的地址列表，訪問時使用輪詢策略以平衡jcm.server在處理請求時的負載。subscriber每秒都會請求一次數據，請求中描述了本次請求想獲取哪些cluster數據，同時攜帶一個cluster的version。每次cluster在server變更時，version就變更（時間戳）。server回復請求時，如果version已最新，只需要回復node的狀態。

subscriber可以拿到所有狀態的node，后面可以考慮只拿正常狀態的node，進一步減少數據大小。

壓力測試

目前只對健康檢查部分做了壓測，詳細參考test/benchmark.md。在A7服務器上測試，發現寫zookeeper及zookeeper的watch足以滿足要求，jcm.server發起的HTTP請求是主要的性能熱點，單jcm.server instance大概可以承載20000個node的健康監測。

網絡帶寬：

Time              ---------------------traffic--------------------
Time               bytin  bytout   pktin  pktout  pkterr  pktdrp
01/07/15-21:30:48   3.2M    4.1M   33.5K   34.4K    0.00    0.00
01/07/15-21:30:50   3.3M    4.2M   33.7K   35.9K    0.00    0.00
01/07/15-21:30:52   2.8M    4.1M   32.6K   41.6K    0.00    0.00

CPU，通過jstack查看主要的CPU消耗在HTTP庫實現層，以及健康檢查線程：

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
admin     20   0 13.1g 1.1g  12m R 76.6  2.3   2:40.74 java         httpchecker
admin     20   0 13.1g 1.1g  12m S 72.9  2.3   0:48.31 java
admin     20   0 13.1g 1.1g  12m S 20.1  2.3   0:18.49 java

代碼中增加了些狀態監控：

checker HttpChecker stat count 20 avg check cost(ms) 542.05, avg flush cost(ms) 41.35

表示平均每次檢查耗時542毫秒，寫數據因為開啟了cache沒有參考價值。

雖然還可以從我自己的代碼中做不少優化，但既然單機可以承載20000個節點的檢測，一般的應用遠遠足夠了。

總結

名字服務在分布式系統中雖然是基礎服務，但往往承擔了非常重要的角色，數據同步出現錯誤、節點狀態出現瞬時的錯誤，都可能對整套系統造成較大影響，業務上出現較大故障。所以名字服務的健壯性、可用性非常重要。實現中需要考慮很多異常情況，包括網絡不穩定、應用層的錯誤等。為了提高足夠的可用性，一般還會加多層的數據cache，例如subscriber端的本地cache，server端的本地cache，以保證在任何情況下都不會影響應用層的服務。

posted @ 2015-07-04 17:50 Kevin Lynx 閱讀(1743) | 評論 (0) | 編輯收藏

2015年5月5日 #

無鎖有序鏈表的實現

無鎖有序鏈表可以保證元素的唯一性，使其可用于哈希表的桶，甚至直接作為一個效率不那么高的map。普通鏈表的無鎖實現相對簡單點，因為插入元素可以在表頭插，而有序鏈表的插入則是任意位置。

本文主要基于論文High Performance Dynamic Lock-Free Hash Tables實現。

主要問題

鏈表的主要操作包含insert和remove，先簡單實現一個版本，就會看到問題所在，以下代碼只用作示例：

struct node_t {
        key_t key;
        value_t val;
        node_t *next;
    };

    int l_find(node_t **pred_ptr, node_t **item_ptr, node_t *head, key_t key) {
        node_t *pred = head;
        node_t *item = head->next;
        while (item) {
            int d = KEY_CMP(item->key, key);
            if (d >= 0) {
                *pred_ptr = pred;
                *item_ptr = item;
                return d == 0 ? TRUE : FALSE;
            }
            pred = item;
            item = item->next;
        } 
        *pred_ptr = pred;
        *item_ptr = NULL;
        return FALSE;
    }

    int l_insert(node_t *head, key_t key, value_t val) {
        node_t *pred, *item, *new_item;
        while (TRUE) {
            if (l_find(&pred, &item, head, key)) {
                return FALSE;
            }
            new_item = (node_t*) malloc(sizeof(node_t));
            new_item->key = key;
            new_item->val = val;
            new_item->next = item;
            // A. 如果pred本身被移除了
            if (CAS(&pred->next, item, new_item)) {
                return TRUE;
            }
            free(new_item);
        }
    }

    int l_remove(node_t *head, key_t key) {
        node_t *pred, *item;
        while (TRUE) {
            if (!l_find(&pred, &item, head, key)) {
                return TRUE;
            }
            // B. 如果pred被移除；如果item也被移除
            if (CAS(&pred->next, item, item->next)) {
                haz_free(item);
                return TRUE;
            }
        }
    }

l_find函數返回查找到的前序元素和元素本身，代碼A和B雖然拿到了pred和item，但在CAS的時候，其可能被其他線程移除。甚至，在l_find過程中，其每一個元素都可能被移除。問題在于，任何時候拿到一個元素時，都不確定其是否還有效。元素的有效性包括其是否還在鏈表中，其指向的內存是否還有效。

解決方案

通過為元素指針增加一個有效性標志位，配合CAS操作的互斥性，就可以解決元素有效性判定問題。

因為node_t放在內存中是會對齊的，所以指向node_t的指針值低幾位是不會用到的，從而可以在低幾位里設置標志，這樣在做CAS的時候，就實現了DCAS的效果，相當于將兩個邏輯上的操作變成了一個原子操作。想象下引用計數對象的線程安全性，其內包裝的指針是線程安全的，但對象本身不是。

CAS的互斥性，在若干個線程CAS相同的對象時，只有一個線程會成功，失敗的線程就可以以此判定目標對象發生了變更。改進后的代碼（代碼僅做示例用，不保證正確）：

typedef size_t markable_t;
    // 最低位置1，表示元素被刪除
    #define HAS_MARK(p) ((markable_t)p & 0x01)
    #define MARK(p) ((markable_t)p | 0x01)
    #define STRIP_MARK(p) ((markable_t)p & ~0x01)

    int l_insert(node_t *head, key_t key, value_t val) {
        node_t *pred, *item, *new_item;
        while (TRUE) {
            if (l_find(&pred, &item, head, key)) { 
                return FALSE;
            }
            new_item = (node_t*) malloc(sizeof(node_t));
            new_item->key = key;
            new_item->val = val;
            new_item->next = item;
            // A. 雖然find拿到了合法的pred，但是在以下代碼之前pred可能被刪除，此時pred->next被標記
            //    pred->next != item，該CAS會失敗，失敗后重試
            if (CAS(&pred->next, item, new_item)) {
                return TRUE;
            }
            free(new_item);
        }
        return FALSE;
    }

    int l_remove(node_t *head, key_t key) {
        node_t *pred, *item;
        while (TRUE) {
            if (!l_find(&pred, &item, head, key)) {
                return FALSE;
            }
            node_t *inext = item->next;
            // B. 刪除item前先標記item->next，如果CAS失敗，那么情況同insert一樣，有其他線程在find之后
            //    刪除了item，失敗后重試
            if (!CAS(&item->next, inext, MARK(inext))) {
                continue;
            }
            // C. 對同一個元素item刪除時，只會有一個線程成功走到這里
            if (CAS(&pred->next, item, STRIP_MARK(item->next))) {
                haz_defer_free(item);
                return TRUE;
            }
        }
        return FALSE;
    }

    int l_find(node_t **pred_ptr, node_t **item_ptr, node_t *head, key_t key) {
        node_t *pred = head;
        node_t *item = head->next;
        hazard_t *hp1 = haz_get(0);
        hazard_t *hp2 = haz_get(1);
        while (item) {
            haz_set_ptr(hp1, pred);
            haz_set_ptr(hp2, item);
            /* 
             如果已被標記，那么緊接著item可能被移除鏈表甚至釋放，所以需要重頭查找
            */
            if (HAS_MARK(item->next)) { 
                return l_find(pred_ptr, item_ptr, head, key);
            }
            int d = KEY_CMP(item->key, key);
            if (d >= 0) {
                *pred_ptr = pred;
                *item_ptr = item;
                return d == 0 ? TRUE : FALSE;
            }
            pred = item;
            item = item->next;
        } 
        *pred_ptr = pred;
        *item_ptr = NULL;
        return FALSE;
    }

haz_get、haz_set_ptr之類的函數是一個hazard pointer實現，用于支持多線程下內存的GC。上面的代碼中，要刪除一個元素item時，會標記item->next，從而使得insert時中那個CAS不需要做任何調整。總結下這里的線程競爭情況：

insert中find到正常的pred及item，pred->next == item，然后在CAS前有線程刪除了pred，此時pred->next == MARK(item)，CAS失敗，重試；刪除分為2種情況：a) 從鏈表移除，得到標記，pred可繼續訪問；b) pred可能被釋放內存，此時再使用pred會錯誤。為了處理情況b，所以引入了類似hazard pointer的機制，可以有效保障任意一個指針p只要還有線程在使用它，它的內存就不會被真正釋放
insert中有多個線程在pred后插入元素，此時同樣由insert中的CAS保證，這個不多說
remove中情況同insert，find拿到了有效的pred和next，但在CAS的時候pred被其他線程刪除，此時情況同insert，CAS失敗，重試
任何時候改變鏈表結構時，無論是remove還是insert，都需要重試該操作
find中遍歷時，可能會遇到被標記刪除的item，此時item根據remove的實現很可能被刪除，所以需要重頭開始遍歷

ABA問題

ABA問題還是存在的，insert中：

if (CAS(&pred->next, item, new_item)) {
        return TRUE;
    }

如果CAS之前，pred后的item被移除，又以相同的地址值加進來，但其value變了，此時CAS會成功，但鏈表可能就不是有序的了。pred->val < new_item->val > item->val

為了解決這個問題，可以利用指針值地址對齊的其他位來存儲一個計數，用于表示pred->next的改變次數。當insert拿到pred時，pred->next中存儲的計數假設是0，CAS之前其他線程移除了pred->next又新增回了item，此時pred->next中的計數增加，從而導致insert中CAS失敗。

// 最低位留作刪除標志
    #define MASK ((sizeof(node_t) - 1) & ~0x01)

    #define GET_TAG(p) ((markable_t)p & MASK)
    #define TAG(p, tag) ((markable_t)p | (tag))
    #define MARK(p) ((markable_t)p | 0x01)
    #define HAS_MARK(p) ((markable_t)p & 0x01)
    #define STRIP_MARK(p) ((node_t*)((markable_t)p & ~(MASK | 0x01)))

remove的實現：

/* 先標記再刪除 */
    if (!CAS(&sitem->next, inext, MARK(inext))) {
        continue;
    }
    int tag = GET_TAG(pred->next) + 1;
    if (CAS(&pred->next, item, TAG(STRIP_MARK(sitem->next), tag))) {
        haz_defer_free(sitem);
        return TRUE;
    }

insert中也可以更新pred->next的計數。

總結

無鎖的實現，本質上都會依賴于CAS的互斥性。從頭實現一個lock free的數據結構，可以深刻感受到lock free實現的tricky。最終代碼可以從這里github獲取。代碼中為了簡單，實現了一個不是很強大的hazard pointer，可以參考之前的博文。

posted @ 2015-05-05 19:47 Kevin Lynx 閱讀(22648) | 評論 (0) | 編輯收藏

2015年5月3日 #

并行編程中的內存回收Hazard Pointer

接上篇使用RCU技術實現讀寫線程無鎖，在沒有GC機制的語言中，要實現Lock free的算法，就免不了要自己處理內存回收的問題。

Hazard Pointer是另一種處理這個問題的算法，而且相比起來不但簡單，功能也很強大。鎖無關的數據結構與Hazard指針中講得很好，Wikipedia Hazard pointer也描述得比較清楚，所以我這里就不講那么細了。

一個簡單的實現可以參考我的github haz_ptr.c

原理

基本原理無非也是讀線程對指針進行標識，指針(指向的內存)要釋放時都會緩存起來延遲到確認沒有讀線程了才對其真正釋放。

<Lock-Free Data Structures with Hazard Pointers>中的描述：

Each reader thread owns a single-writer/multi-reader shared pointer called “hazard pointer.” When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), “I am reading this map. You can replace it if you want, but don’t change its contents and certainly keep your deleteing hands off it.”

關鍵的結構包括：Hazard pointer、Thread Free list

Hazard pointer：一個讀線程要使用一個指針時，就會創建一個Hazard pointer包裝這個指針。一個Hazard pointer會被一個線程寫，多個線程讀。

struct HazardPointer {
        void *real_ptr; // 包裝的指針
        ... // 不同的實現有不同的成員
    };

    void func() {
        HazardPointer *hp = accquire(_real_ptr);
        ... // use _real_ptr
        release(hp);
    }

Thread Free List：每個線程都有一個這樣的列表，保存著將要釋放的指針列表，這個列表僅對應的線程讀寫

void defer_free(void *ptr) {
        _free_list.push_back(ptr);
    }

當某個線程要嘗試釋放Free List中的指針時，例如指針ptr，就檢查所有其他線程使用的Hazard pointer，檢查是否存在包裝了ptr的Hazard pointer，如果沒有則說明沒有讀線程正在使用ptr，可以安全釋放ptr。

void gc() {
        for(ptr in _free_list) {
            conflict = false
            for (hp in _all_hazard_pointers) {
                if (hp->_real_ptr == ptr) {
                    confilict = true
                    break
                }
            }
            if (!conflict)
                delete ptr
        }
    }

以上，其實就是Hazard Pointer的主要內容。

Hazard Pointer的管理

上面的代碼中沒有提到_all_hazard_pointers及accquire的具體實現，這就是Hazard Pointer的管理問題。

《鎖無關的數據結構與Hazard指針》文中創建了一個Lock free的鏈表來表示這個全局的Hazard Pointer List。每個Hazard Pointer有一個成員標識其是否可用。這個List中也就保存了已經被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合，當所有Hazard Pointer都被使用時，就會新分配一個加進這個List。當讀線程不使用指針時，需要歸還Hazard Pointer，直接設置可用成員標識即可。要gc()時，就直接遍歷這個List。

要實現一個Lock free的鏈表，并且僅需要實現頭插入，還是非常簡單的。本身Hazard Pointer標識某個指針時，都是用了后立即標識，所以這個實現直接支持了動態線程，支持線程的掛起等。

在nbds項目中也有一個Hazard Pointer的實現，相對要弱一點。它為每個線程都設置了自己的Hazard Pointer池，寫線程要釋放指針時，就訪問所有其他線程的Hazard Pointer池。

typedef struct haz_local {
        // Free List
        pending_t *pending; // to be freed
        int pending_size;
        int pending_count;

        // Hazard Pointer 池，動態和靜態兩種
        haz_t static_haz[STATIC_HAZ_PER_THREAD];

        haz_t **dynamic;
        int dynamic_size;
        int dynamic_count;

    } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;

    static haz_local_t haz_local_[MAX_NUM_THREADS] = {};

每個線程當然就涉及到haz_local_索引(ID)的分配，就像使用RCU技術實現讀寫線程無鎖中的一樣。這個實現為了支持線程動態創建，就需要一套線程ID的重用機制，相對復雜多了。

附錄

最后，附上一些并行編程中的一些概念。

Lock Free & Wait Free

常常看到Lock Free和Wait Free的概念，這些概念用于衡量一個系統或者說一段代碼的并行級別，并行級別可參考并行編程——并發級別。總之Wait Free是一個比Lock Free更牛逼的級別。

我自己的理解，例如《鎖無關的數據結構與Hazard指針》中實現的Hazard Pointer鏈表就可以說是Lock Free的，注意它在插入新元素到鏈表頭時，因為使用CAS，總免不了一個busy loop，有這個特征的情況下就算是Lock Free，雖然沒鎖，但某個線程的執行情況也受其他線程的影響。

相對而言，Wait Free則是每個線程的執行都是獨立的，例如《鎖無關的數據結構與Hazard指針》中的Scan函數。“每個線程的執行時間都不依賴于其它任何線程的行為”

鎖無關(Lock-Free)意味著系統中總存在某個線程能夠得以繼續執行；而等待無關(Wait-Free)則是一個更強的條件，它意味著所有線程都能往下進行。

ABA問題

在實現Lock Free算法的過程中，總是要使用CAS原語的，而CAS就會帶來ABA問題。

在進行CAS操作的時候，因為在更改V之前，CAS主要詢問“V的值是否仍然為A”，所以在第一次讀取V之后以及對V執行CAS操作之前，如果將值從A改為B，然后再改回A，會使基于CAS的算法混亂。在這種情況下，CAS操作會成功。這類問題稱為ABA問題。

Wiki Hazard Pointer提到了一個ABA問題的好例子：在一個Lock free的棧實現中，現在要出棧，棧里的元素是[A, B, C]，head指向棧頂，那么就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在這個操作中，其他線程把A B都出棧，且刪除了B，又把A壓入棧中，即[A, C]。那么前一個線程的compare_and_swap能夠成功，此時head指向了一個已經被刪除的B。stackoverflow上也有個例子 Real-world examples for ABA in multithreading

對于CAS產生的這個ABA問題，通常的解決方案是采用CAS的一個變種DCAS。DCAS，是對于每一個V增加一個引用的表示修改次數的標記符。對于每個V，如果引用修改了一次，這個計數器就加1。然后再這個變量需要update的時候，就同時檢查變量的值和計數器的值。

但也早有人提出DCAS也不是ABA problem 的銀彈。

posted @ 2015-05-03 20:46 Kevin Lynx 閱讀(20014) | 評論 (0) | 編輯收藏

2015年4月19日 #

使用RCU技術實現讀寫線程無鎖

在一個系統中有一個寫線程和若干個讀線程，讀寫線程通過一個指針共用了一個數據結構，寫線程改寫這個結構，讀線程讀取該結構。在寫線程改寫這個數據結構的過程中，加鎖情況下讀線程由于等待鎖耗時會增加。

可以利用RCU (Read Copy Update What is rcu)的思想來去除這個鎖。本文提到的主要實現代碼：gist

RCU

RCU可以說是一種替代讀寫鎖的方法。其基于一個事實：當寫線程在改變一個指針時，讀線程獲取這個指針，要么獲取到老的值，要么獲取到新的值。RCU的基本思想其實很簡單，參考What is RCU中Toy implementation可以很容易理解。一種簡單的RCU流程可以描述為：

寫線程：

old_ptr = _ptr
tmp_ptr = copy(_ptr)     // copy
change(tmp_ptr)          // change 
_ptr = tmp_ptr           // update
synchroize(tmp_ptr)

寫線程要更新_ptr指向的內容時，先復制一份新的，基于新的進行改變，更新_ptr指針，最后同步釋放老的內存。

讀線程：

tmp_ptr = _ptr
use(tmp_ptr)
dereference(tmp_ptr)

讀線程直接使用_ptr，使用完后需要告訴寫線程自己不再使用_ptr。讀線程獲取_ptr時，可能會獲取到老的也可能獲取到新的，無論哪種RCU都需要保證這塊內存是有效的。重點在synchroize和dereference。synchroize會等待所有使用老的_ptr的線程dereference，對于新的_ptr使用者其不需要等待。這個問題說白了就是寫線程如何知道old_ptr沒有任何讀線程在使用，可以安全地釋放。

這個問題實際上在wait-free的各種實現中有好些解法，how-when-to-release-memory-in-wait-free-algorithms這里有人總結了幾種方法，例如Hazard pointers、Quiescence period based reclamation。

簡單地使用引用計數智能指針是無法解決這個問題的，因為智能指針自己不是線程安全的，例如：

tmp_ptr = _ptr      // 1
tmp_ptr->addRef()   // 2
use
tmp_ptr->release()

代碼1/2行不是原子的，所以當取得tmp_ptr準備addRef時，tmp_ptr可能剛好被釋放了。

Quiescence period based reclamation方法指的是讀線程需要聲明自己處于Quiescence period，也就是不使用_ptr的時候，當其使用_ptr的時候實際是進入了一個邏輯上的臨界區，當所有讀線程都不再使用_ptr的時候，寫線程就可以對內存進行安全地釋放。

本文正是描述了一種Quiescence period based reclamation實現。這個實現可以用于有一個寫線程和多個讀線程共用若干個數據的場景。

實現

該方法本質上把數據同步分解為基本的內存單元讀寫。使用方式上可描述為：

讀線程：

tmp_ptr = _ptr
use
update() // 標識自己不再使用任何共享數據

寫線程：

old_ptr = _ptr
tmp_ptr = copy(_ptr)
change(tmp_ptr)
_ptr = tmp_ptr
gc()
defer_free(old_ptr)

以下具體描述讀寫線程的實現。

寫線程

寫線程負責標識內存需要被釋放，以及檢查何時可以真正釋放內存。其維護了一個釋放內存隊列：

void *_pending[8]
    uint64_t _head, _tail

    void defer_free(void *p) {
        _head ++
        _pending[PENDING_POS(_head)] = p
    }

    gc() {
        for (_tail -> find_free_pos())
            free(_pending[_tail])
    }

find_free_pos找到一個可釋放內存位置，在[_tail, find_free_pos())這個區間內所有內存是可以安全被釋放的。

隊列位置_head/_tail一直增大，PENDING_POS就是對這個位置取模，限定在隊列大小范圍內也是可行的，無論哪種方式，_head從邏輯上說一直>=_tail，但在實際中可能小于_tail，所以實現時不使用大小判定，而是：

gc() {
        pos = find_free_pos()
        while (_tail != pos) {
            free(_pending[PENDING_POS(_tail)])
            _tail ++
        }
    }

讀線程

讀線程不再使用共享內存時，就標識自己：

update() {
        static __thread int tid
        _tmark[tid] = _head
    }

讀線程的狀態會影響寫線程的回收邏輯，其狀態分為：

初始
活躍，會調用到update
暫停，其他地方同步，或被掛起
退出

讀線程處于活躍狀態時，它會不斷地更新自己可釋放內存位置(_tmark[tid])。寫線程檢查所有讀線程的_tmark[tid]，[_tail, min(_tmark[]))是所有讀線程都不再使用的內存區間，可以被安全釋放。

find_free_pos() {
        min = MAX_INTEGER
        pos = 0
        for (tid = 0; tid < max_threads; ++tid) {
            tpos = _tmark[tid]
            offset = tpos - tail
            if (offset < min) {
                min = offset
                pos = tpos
            }
        }
        return pos
    }

當讀線程暫停時，其_tmark[tid]可能會在很長一段時間里得不到更新，此時會阻礙寫線程釋放內存。所以需要方法來標識讀線程是否進入暫停狀態。通過設置一個上次釋放內存位置_tfreeds[tid]，標識每個線程當前內存釋放到的位置。如果一個線程處于暫停狀態了，那么在一定時間后，_tfreeds[tid] == _tmark[tid]。在查找可釋放位置時，就需要忽略暫停狀態的讀線程：

find_free_pos() {
        min = MAX_INTEGER
        pos = _head
        for (tid = 0; tid < max_threads; ++tid) {
            tpos = _tmark[tid]
            if (tpos == _tfreeds[tid]) continue
            offset = tpos - tail
            if (offset < min) {
                min = offset
                pos = tpos
            }
        }
        for (tid = 0; tid < max_threads; ++tid) {
            if (_tfreeds[tid] != _tmark[tid]) 
                _tfreeds[tid] = pos
        }
        return pos
    }

但是當所有線程都處于暫停狀態時，寫線程可能還在工作，上面的實現就會返回_head，此時寫線程依然可以正常釋放內存。

小結，該方法原理可用下圖表示：

線程動態增加/減少

如果讀線程可能中途退出，中途動態增加，那么_tmark[]就需要被復用，此時線程tid的分配調整為動態的即可：

class ThreadIdPool {
    public:
        // 動態獲取一個線程tid，某線程每次調用該接口返回相同的值
        int get()
        // 線程退出時回收該tid
        void put(int id)
    }

ThreadIdPool的實現無非就是利用TLS，以及在線程退出時得到通知以回收tid。那么對于讀線程的update實現變為：

update() {
        tid = _idPool->get()
        _tmark[tid] = _head
    }

當某個線程退出時，_tmark[tid]和_tfreeds[tid]不需要做任何處理，當新創建的線程復用了該tid時，可以立即復用_tmark[tid]和_tfreeds[tid]，此時這2個值必然是相等的。

以上，就是整個方法的實現。

線程可讀可寫

以上方法適用場景還是不夠通用。在nbds項目（實現了一些無鎖數據結構的toy project）中有一份雖然簡單但也有啟發的實現(rcu.c)。該實現支持任意線程defer_free，所有線程update。update除了聲明不再使用任何共享內存外，還可能回收內存。任意線程都可能維護一些待釋放的內存，任意一塊內存可能被任意其他線程使用。那么它是如何內存回收的？

本文描述的方法是所有讀線程自己聲明自己，然后由寫線程主動來檢查。不同于此方法， nbds的實現，基于一種通知擴散的方式。該方式以這樣一種方式工作：

當某個線程嘗試內存回收時，它需要知道所有其他線程的空閑位置（相當于_tmark[tid]），它通知下一個線程我需要釋放的范圍。當下一個線程update時（離開臨界區），它會將上個線程的通知繼續告訴下一個線程，直到最后這個通知回到發起線程。那么對于發起線程而言，這個釋放請求在所有線程中走了一遍，得到了大家的認可，可以安全釋放。每個線程都以這樣的方式工作。

void rcu_defer_free (void *x) {
        ...
        rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = pending_[tid_]->head;
        ...
    }

    void rcu_update (void) {
        ...
        for (i = 0; i < num_threads_; ++i) {
            ...     
            uint64_t x = rcu_[tid_][i]; // 其它線程發給自己的通知
            rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x; // 擴散出去
            ...
        }
        ...
        while (q->tail != rcu_[tid_][tid_]) {
            free
        }     
        ...
    }

這個實現相對簡單，不支持線程暫停，以及線程動態增加和減少。

posted @ 2015-04-19 19:10 Kevin Lynx 閱讀(11452) | 評論 (3) | 編輯收藏

2015年4月6日 #

記一次tcmalloc分配內存引起的coredump

現象

線上的服務出現coredump，堆棧為：

#0  0x000000000045d145 in GetStackTrace(void**, int, int) ()
#1  0x000000000045ec22 in tcmalloc::PageHeap::GrowHeap(unsigned long) ()
#2  0x000000000045eeb3 in tcmalloc::PageHeap::New(unsigned long) ()
#3  0x0000000000459ee8 in tcmalloc::CentralFreeList::Populate() ()
#4  0x000000000045a088 in tcmalloc::CentralFreeList::FetchFromSpansSafe() ()
#5  0x000000000045a10a in tcmalloc::CentralFreeList::RemoveRange(void**, void**, int) ()
#6  0x000000000045c282 in tcmalloc::ThreadCache::FetchFromCentralCache(unsigned long, unsigned long) ()
#7  0x0000000000470766 in tc_malloc ()
#8  0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
        at build/release64/cm_sub/conhash/conhash_inter.c:88
#9  0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
        at build/release64/cm_sub/conhash/conhash_inter.c:45
#10 0x00007f75532cd1fa in conhash_add_node (conhash=0x24fbc7e0, iden=0) at build/release64/cm_sub/conhash/conhash.c:72
#11 0x00007f75532c651b in cm_sub::TopoCluster::initLBPolicyInfo (this=0x2593a400)
        at build/release64/cm_sub/topo_cluster.cpp:114
#12 0x00007f75532cad73 in cm_sub::TopoClusterManager::processClusterMapTable (this=0xa219e0, ref=0x267ea8c0)
        at build/release64/cm_sub/topo_cluster_manager.cpp:396
#13 0x00007f75532c5a93 in cm_sub::SubRespMsgProcess::reinitCluster (this=0x9c2f00, msg=0x4e738ed0)
        at build/release64/cm_sub/sub_resp_msg_process.cpp:157
...

查看了應用層相關數據結構，基本數據都是沒有問題的。所以最初懷疑是tcmalloc內部維護了錯誤的內存，在分配內存時出錯，這個堆棧只是問題的表象。幾天后，線上的另一個服務，基于同樣的庫，也core了，堆棧還是一樣的。

最初定位問題都是從最近更新的東西入手，包括依賴的server環境，但都沒有明顯的問題，所以最后只能從core的直接原因入手。

分析GetStackTrace

確認core的詳細位置：

# core在該指令
0x000000000045d145 <_Z13GetStackTracePPvii+21>: mov    0x8(%rax),%r9

(gdb) p/x $rip              # core 的指令位置
$9 = 0x45d145
(gdb) p/x $rax              
$10 = 0x4e73aa58
(gdb) x/1a $rax+0x8         # rax + 8 = 0x4e73aa60
0x4e73aa60:     0x0

該指令嘗試從[0x4e73aa60]處讀取內容，然后出錯，這個內存單元不可讀。但是具體這個指令在代碼中是什么意思，需要將這個指令對應到代碼中。獲取tcmalloc的源碼，發現GetStackTrace根據編譯選項有很多實現，所以這里選擇最可能的實現，然后對比匯編以確認代碼是否匹配。最初選擇的是stacktrace_x86-64-inl.h，后來發現完全不匹配，又選擇了stacktrace_x86-inl.h。這個實現版本里也有對64位平臺的支持。

stacktrace_x86-inl.h里使用了一些宏來生成函數名和參數，精簡后代碼大概為：

int GET_STACK_TRACE_OR_FRAMES {
      void **sp;
      unsigned long rbp;
      __asm__ volatile ("mov %%rbp, %0" : "=r" (rbp));
      sp = (void **) rbp;

      int n = 0;
      while (sp && n < max_depth) {
        if (*(sp+1) == reinterpret_cast<void *>(0)) {
          break;
        }
        void **next_sp = NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(sp, ucp);
        if (skip_count > 0) {
          skip_count--;
        } else {
          result[n] = *(sp+1);
          n++;
        }
        sp = next_sp;
      }
      return n;
    }

NextStackFrame是一個模板函數，包含一大堆代碼，精簡后非常簡單：

template<bool STRICT_UNWINDING, bool WITH_CONTEXT>
    static void **NextStackFrame(void **old_sp, const void *uc) {
      void **new_sp = (void **) *old_sp;
      if (STRICT_UNWINDING) {
        if (new_sp <= old_sp) return NULL;
        if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL;
      } else {
        if (new_sp == old_sp) return NULL;
        if ((new_sp > old_sp)
            && ((uintptr_t)new_sp - (uintptr_t)old_sp > 1000000)) return NULL;
      }
      if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL;

      return new_sp;
    }

上面這個代碼到匯編的對比過程還是花了些時間，其中匯編中出現的一些常量可以大大縮短對比時間，例如上面出現了100000，匯編中就有：

0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp    $0x186a0,%rbx  # 100000=0x186a0

注意NextStackFrame中的 if (STRICT_UNWINDING)使用的是模板參數，這導致生成的代碼中根本沒有else部分，也就沒有1000000這個常量

在對比代碼的過程中，可以知道關鍵的幾個寄存器、內存位置對應到代碼中的變量，從而可以還原core時的現場環境。分析過程中不一定要從第一行匯編讀，可以從較明顯的位置讀，從而還原整個代碼，函數返回指令、跳轉指令、比較指令、讀內存指令、參數寄存器等都是比較明顯對應的地方。

另外注意GetStackTrace在RecordGrowth中調用，傳入了3個參數：

GetStackTrace(t->stack, kMaxStackDepth-1, 3); // kMaxStackDepth = 31

以下是我分析的簡單注解：

(gdb) disassemble
Dump of assembler code for function _Z13GetStackTracePPvii:
0x000000000045d130 <_Z13GetStackTracePPvii+0>:  push   %rbp
0x000000000045d131 <_Z13GetStackTracePPvii+1>:  mov    %rsp,%rbp
0x000000000045d134 <_Z13GetStackTracePPvii+4>:  push   %rbx
0x000000000045d135 <_Z13GetStackTracePPvii+5>:  mov    %rbp,%rax
0x000000000045d138 <_Z13GetStackTracePPvii+8>:  xor    %r8d,%r8d
0x000000000045d13b <_Z13GetStackTracePPvii+11>: test   %rax,%rax
0x000000000045d13e <_Z13GetStackTracePPvii+14>: je     0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d140 <_Z13GetStackTracePPvii+16>: cmp    %esi,%r8d        # while ( .. max_depth > n ?
0x000000000045d143 <_Z13GetStackTracePPvii+19>: jge    0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d145 <_Z13GetStackTracePPvii+21>: mov    0x8(%rax),%r9    # 關鍵位置：*(sp+1) -> r9, rax 對應 sp變量
0x000000000045d149 <_Z13GetStackTracePPvii+25>: test   %r9,%r9          # *(sp+1) == 0 ?
0x000000000045d14c <_Z13GetStackTracePPvii+28>: je     0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d14e <_Z13GetStackTracePPvii+30>: mov    (%rax),%rcx      # new_sp = *old_sp，這里已經是NextStackFrame的代碼
0x000000000045d151 <_Z13GetStackTracePPvii+33>: cmp    %rcx,%rax        # new_sp <= old_sp ? 
0x000000000045d154 <_Z13GetStackTracePPvii+36>: jb     0x45d170 <_Z13GetStackTracePPvii+64>  # new_sp > old_sp 跳轉
0x000000000045d156 <_Z13GetStackTracePPvii+38>: xor    %ecx,%ecx
0x000000000045d158 <_Z13GetStackTracePPvii+40>: test   %edx,%edx        # skip_count > 0 ?
0x000000000045d15a <_Z13GetStackTracePPvii+42>: jle    0x45d186 <_Z13GetStackTracePPvii+86>
0x000000000045d15c <_Z13GetStackTracePPvii+44>: sub    $0x1,%edx        # skip_count--
0x000000000045d15f <_Z13GetStackTracePPvii+47>: mov    %rcx,%rax        
0x000000000045d162 <_Z13GetStackTracePPvii+50>: test   %rax,%rax        # while (sp ?
0x000000000045d165 <_Z13GetStackTracePPvii+53>: jne    0x45d140 <_Z13GetStackTracePPvii+16>
0x000000000045d167 <_Z13GetStackTracePPvii+55>: pop    %rbx
0x000000000045d168 <_Z13GetStackTracePPvii+56>: leaveq 
0x000000000045d169 <_Z13GetStackTracePPvii+57>: mov    %r8d,%eax        # r8 存儲了返回值，r8=n
0x000000000045d16c <_Z13GetStackTracePPvii+60>: retq                    # return n
0x000000000045d16d <_Z13GetStackTracePPvii+61>: nopl   (%rax)
0x000000000045d170 <_Z13GetStackTracePPvii+64>: mov    %rcx,%rbx        
0x000000000045d173 <_Z13GetStackTracePPvii+67>: sub    %rax,%rbx        # offset = new_sp - old_sp
0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp    $0x186a0,%rbx    # offset > 100000 ?
0x000000000045d17d <_Z13GetStackTracePPvii+77>: ja     0x45d156 <_Z13GetStackTracePPvii+38> # return NULL
0x000000000045d17f <_Z13GetStackTracePPvii+79>: test   $0x7,%cl         # new_sp & (sizeof(void*) - 1)
0x000000000045d182 <_Z13GetStackTracePPvii+82>: je     0x45d158 <_Z13GetStackTracePPvii+40>
0x000000000045d184 <_Z13GetStackTracePPvii+84>: jmp    0x45d156 <_Z13GetStackTracePPvii+38>
0x000000000045d186 <_Z13GetStackTracePPvii+86>: movslq %r8d,%rax        # rax = n
0x000000000045d189 <_Z13GetStackTracePPvii+89>: add    $0x1,%r8d        # n++
0x000000000045d18d <_Z13GetStackTracePPvii+93>: mov    %r9,(%rdi,%rax,8)# 關鍵位置：result[n] = *(sp+1)
0x000000000045d191 <_Z13GetStackTracePPvii+97>: jmp    0x45d15f <_Z13GetStackTracePPvii+47>

分析過程比較耗時，同時還可以分析下GetStackTrace函數的實現原理，其實就是利用RBP寄存器不斷回溯，從而得到整個調用堆棧各個函數的地址（嚴格來說是返回地址）。簡單示意下函數調用中RBP的情況：

   ...
saved registers          # i.e push rbx
local variabes           # i.e sub 0x10, rsp
return address           # call xxx
last func RBP            # push rbp; mov rsp, rbp
saved registers
local variables 
return address
last func RBP
...                      # rsp

總之，一般情況下，任何一個函數中，RBP寄存器指向了當前函數的棧基址，該棧基址中又存儲了調用者的棧基址，同時該棧基址前面還存儲了調用者的返回地址。所以，GetStackTrace的實現，簡單來說大概就是：

sp = rbp  // 取得當前函數GetStackTrace的棧基址
    while (n < max_depth) {
        new_sp = *sp
        result[n] = *(new_sp+1)
        n++
    }

以上，最終就知道了以下關鍵信息：

r8 對應變量 n，表示當前取到第幾個棧幀了
rax 對應變量 sp，代碼core在 *(sp+1)
rdi 對應變量 result，用于存儲取得的各個地址

然后可以看看現場是怎樣的：

(gdb) x/10a $rdi
0x1ffc9b98:     0x45a088 <_ZN8tcmalloc15CentralFreeList18FetchFromSpansSafeEv+40>       0x45a10a <_ZN8tcmalloc15CentralFreeList11RemoveRangeEPPvS2_i+106>
0x1ffc9ba8:     0x45c282 <_ZN8tcmalloc11ThreadCache21FetchFromCentralCacheEmm+114>      0x470766 <tc_malloc+790>
0x1ffc9bb8:     0x7f75532cd4c2 <__conhash_get_rbnode+34>        0x0
0x1ffc9bc8:     0x0     0x0
0x1ffc9bd8:     0x0     0x0

(gdb) p/x $r8
$3 = 0x5

(gdb) p/x $rax
$4 = 0x4e73aa58

小結：

GetStackTrace在取調用__conhash_get_rbnode的函數時出錯，取得了5個函數地址。當前使用的RBP為0x4e73aa58。

錯誤的RBP

RBP也是從堆棧中取出來的，既然這個地址有問題，首先想到的就是有代碼局部變量/數組寫越界。例如sprintf的使用。而且，一般寫越界破壞堆棧，都可能是把調用者的堆棧破壞了，例如：

char s[32];
memcpy(s, p, 1024);

因為寫入都是從低地址往高地址寫，而調用者的堆棧在高地址。當然，也會遇到寫壞調用者的調用者的堆棧，也就是跨棧幀越界寫，例如以前遇到的：

len = vsnprintf(buf, sizeof(buf), fmt, wtf-long-string);
buf[len] = 0;

__conhash_get_rbnode的RBP是在tcmalloc的堆棧中取的：

(gdb) f 7
#7  0x0000000000470766 in tc_malloc ()
(gdb) x/10a $rsp
0x4e738b80:     0x4e73aa58      0x22c86870
0x4e738b90:     0x4e738bd0      0x85
0x4e738ba0:     0x4e73aa58      0x7f75532cd4c2 <__conhash_get_rbnode+34>   # 0x4e73aa58

所以這里就會懷疑是tcmalloc這個函數里有把堆棧破壞，這個時候就是讀代碼，看看有沒有疑似危險的地方，未果。這里就陷入了僵局，懷疑又遇到了跨棧幀破壞的情況，這個時候就只能__conhash_get_rbnode調用棧中周圍的函數翻翻，例如調用__conhash_get_rbnode的函數__conhash_add_replicas中恰好有字符串操作：

void __conhash_add_replicas(conhash_t *conhash, int32_t iden)
    {
        node_t* node = __conhash_create_node(iden, conhash->replica);
        ...
        char buf[buf_len]; // buf_len = 64
        ...
        snprintf(buf, buf_len, VIRT_NODE_HASH_FMT, node->iden, i);
        uint32_t hash = conhash->cb_hashfunc(buf);
        if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
        {
            util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash);
            ...

這段代碼最終發現是沒有問題的，這里又耗費了不少時間。后來發現若干個函數里的RBP都有點奇怪，這個調用棧比較正常的范圍是：0x4e738c90

(gdb) f 8
#8  0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
(gdb) p/x $rbp
$6 = 0x4e73aa58     # 這個還不算特別可疑
(gdb) f 9
#9  0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
(gdb) p/x $rbp
$7 = 0x4e738c60     # 這個也不算特別可疑
(gdb) f 10
#10 0x00007f75532cd1fa in conhash_add_node (conhash=0x24fbc7e0, iden=0) at build/release64/cm_sub/conhash/conhash.c:72
(gdb) p/x $rbp      # 可疑
$8 = 0x0
(gdb) f 11
#11 0x00007f75532c651b in cm_sub::TopoCluster::initLBPolicyInfo (this=0x2593a400)
(gdb) p/x $rbp      # 可疑
$9 = 0x2598fef0

為什么很多函數中RBP都看起來不正常？ 想了想真要是代碼里把堆棧破壞了，這錯誤得發生得多巧妙？

錯誤RBP的來源

然后轉機來了，腦海中突然閃出-fomit-frame-pointer。編譯器生成的代碼中是可以不需要棧基址指針的，也就是RBP寄存器不作為棧基址寄存器。大部分函數或者說開啟了frame-pointer的函數，其函數頭都會有以下指令：

push   %rbp
mov    %rsp,%rbp
...

表示保存調用者的棧基址到棧中，以及設置自己的棧基址。看下__conhash系列函數；

Dump of assembler code for function __conhash_get_rbnode:
0x00007f75532cd4a0 <__conhash_get_rbnode+0>:    mov    %rbx,-0x18(%rsp)
0x00007f75532cd4a5 <__conhash_get_rbnode+5>:    mov    %rbp,-0x10(%rsp)
...

這個庫是單獨編譯的，沒有顯示指定-fno-omit-frame-pointer，查閱gcc手冊，o2優化是開啟了omit-frame-pinter 的。

在沒有RBP的情況下，tcmalloc的GetStackTrace嘗試讀RBP取獲取調用返回地址，自然是有問題的。但是，如果整個調用棧中的函數，要么有RBP，要么沒有RBP，那么GetStackTrace取出的結果最多就是跳過一些棧幀，不會出錯。 除非，這中間的某個函數把RBP寄存器另作他用（編譯器省出這個寄存器肯定是要另作他用的）。所以這里繼續追查這個錯誤地址0x4e73aa58的來源。

來源已經比較明顯，肯定是__conhash_get_rbnode中設置的，因為這個函數的RBP是在被調用者tcmalloc中保存的。

Dump of assembler code for function __conhash_get_rbnode:
0x00007f75532cd4a0 <__conhash_get_rbnode+0>:    mov    %rbx,-0x18(%rsp)
0x00007f75532cd4a5 <__conhash_get_rbnode+5>:    mov    %rbp,-0x10(%rsp)
0x00007f75532cd4aa <__conhash_get_rbnode+10>:   mov    %esi,%ebp                    # 改寫了RBP
0x00007f75532cd4ac <__conhash_get_rbnode+12>:   mov    %r12,-0x8(%rsp)
0x00007f75532cd4b1 <__conhash_get_rbnode+17>:   sub    $0x18,%rsp
0x00007f75532cd4b5 <__conhash_get_rbnode+21>:   mov    %rdi,%r12
0x00007f75532cd4b8 <__conhash_get_rbnode+24>:   mov    $0x30,%edi
0x00007f75532cd4bd <__conhash_get_rbnode+29>:   callq  0x7f75532b98c8 <malloc@plt>  # 調用tcmalloc，匯編到這里即可

這里打印RSI寄存器的值可能會被誤導，因為任何時候打印寄存器的值可能都是錯的，除非它有被顯示保存。不過這里可以看出RSI的值來源于參數(RSI對應第二個參數)：

void __conhash_add_replicas(conhash_t *conhash, int32_t iden)
    {
        node_t* node = __conhash_create_node(iden, conhash->replica);
        ...
        char buf[buf_len]; // buf_len = 64
        ...
        snprintf(buf, buf_len, VIRT_NODE_HASH_FMT, node->iden, i);
        uint32_t hash = conhash->cb_hashfunc(buf); // hash值由一個字符串哈希函數計算
        if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
        {
            util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash);  // hash值
            ...

追到__conhash_add_replicas：

0x00007f75532cd764 <__conhash_add_replicas+164>:        mov    %ebx,%esi    # 來源于rbx
0x00007f75532cd766 <__conhash_add_replicas+166>:        mov    %r15,%rdi
0x00007f75532cd769 <__conhash_add_replicas+169>:        callq  0x7f75532b9e48 <__conhash_get_rbnode@plt>

(gdb) p/x $rbx
$11 = 0x4e73aa58
(gdb) p/x hash
$12 = 0x4e73aa58      # 0x4e73aa58

找到了0x4e73aa58的來源。這個地址值竟然是一個字符串哈希算法算出來的！這里還可以看看這個字符串的內容：

(gdb) x/1s $rsp
0x4e738bd0:      "conhash-00000-00133"

這個碉堡的哈希函數是conhash_hash_def。

coredump的條件

以上，既然只要某個庫omit-frame-pointer，那tcmalloc就可能出錯，為什么發生的頻率并不高呢？這個可以回到GetStackTrace尤其是NextStackFrame的實現，其中包含了幾個合法RBP的判定：

if (new_sp <= old_sp) return NULL;  // 上一個棧幀的RBP肯定比當前的大
        if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL; // 指針值范圍還必須在100000內
        ...
    if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL; // 由于本身保存的是指針，所以還必須是sizeof(void*)的整數倍，對齊

有了以上條件，才使得這個core幾率變得很低。

總結

最后，如果你很熟悉tcmalloc，整個問題估計就被秒解了：tcmalloc INSTALL

附

另外附上另一個有意思的東西。

在分析__conhash_add_replicas時，其內定義了一個64字節的字符數組，查看其堆棧：

(gdb) x/20a $rsp
0x4e738bd0:     0x2d687361686e6f63      0x30302d3030303030          # 這些是字符串conhash-00000-00133
0x4e738be0:     0x333331        0x0
0x4e738bf0:     0x0     0x7f75532cd69e <__conhash_create_node+78>
0x4e738c00:     0x24fbc7e0      0x4e738c60
0x4e738c10:     0x24fbc7e0      0x7f75532cd6e3 <__conhash_add_replicas+35>
0x4e738c20:     0x0     0x24fbc7e8
0x4e738c30:     0x4e738c20      0x24fbc7e0
0x4e738c40:     0x22324360      0x246632c0
0x4e738c50:     0x0     0x0
0x4e738c60:     0x0     0x7f75532cd1fa <conhash_add_node+74>

最開始我覺得buf占64字節，也就是整個[0x4e738bd0, 0x4e738c10)內存，但是這塊內存里居然有函數地址，這一度使我懷疑這里有問題。后來醒悟這些地址是定義buf前調用__conhash_create_node產生的，調用過程中寫到堆棧里，調用完后棧指針改變，但并不需要清空棧中的內容。

posted @ 2015-04-06 18:33 Kevin Lynx 閱讀(8085) | 評論 (2) | 編輯收藏

2014年12月3日 #

基于內存查看STL常用容器內容

有時候在線上使用gdb調試程序core問題時，可能沒有符號文件，拿到的僅是一個內存地址，如果這個指向的是一個STL對象，那么如何查看這個對象的內容呢？

只需要知道STL各個容器的數據結構實現，就可以查看其內容。本文描述了SGI STL實現中常用容器的數據結構，以及如何在gdb中查看其內容。

string

string，即basic_string bits/basic_string.h：

mutable _Alloc_hider  _M_dataplus;
    ... 
      const _CharT*
      c_str() const
      { return _M_data(); }
    ...    
      _CharT*
      _M_data() const 
      { return  _M_dataplus._M_p; }

    ...
      struct _Alloc_hider : _Alloc
      {
    _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    : _Alloc(__a), _M_p(__dat) { }

    _CharT* _M_p; // The actual data.
      };
   
      size_type
      length() const
      { return _M_rep()->_M_length; }

      _Rep*
      _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      ...
       struct _Rep_base
      {
    size_type       _M_length;
    size_type       _M_capacity;
    _Atomic_word        _M_refcount;
      };

      struct _Rep : _Rep_base

即，string內有一個指針，指向實際的字符串位置，這個位置前面有一個_Rep結構，其內保存了字符串的長度、可用內存以及引用計數。當我們拿到一個string對象的地址時，可以通過以下代碼獲取相關值：

void ds_str_i(void *p) {
        char **raw = (char**)p;
        char *s = *raw;
        size_t len = *(size_t*)(s - sizeof(size_t) * 3);
        printf("str: %s (%zd)\n", s, len);
    }

    size_t ds_str() {
        std::string s = "hello";
        ds_str_i(&s);
        return s.size();
    }

在gdb中拿到一個string的地址時，可以以下打印出該字符串及長度：

(gdb) x/1a p
0x7fffffffe3a0: 0x606028
(gdb) p (char*)0x606028
$2 = 0x606028 "hello"
(gdb) x/1dg 0x606028-24
0x606010:       5

vector

眾所周知vector實現就是一塊連續的內存，bits/stl_vector.h。

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>

    ...
    template<typename _Tp, typename _Alloc>
    struct _Vector_base
    {
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

      struct _Vector_impl
      : public _Tp_alloc_type
      {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl(_Tp_alloc_type const& __a)
    : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };


      _Vector_impl _M_impl;

可以看出sizeof(vector<xxx>)=24，其內也就是3個指針，_M_start指向首元素地址，_M_finish指向最后一個節點+1，_M_end_of_storage是可用空間最后的位置。

iterator
      end()
      { return iterator (this->_M_impl._M_finish); }
      const_iterator
      ...
      begin() const
      { return const_iterator (this->_M_impl._M_start); }
      ...
      size_type
      capacity() const
      { return size_type(const_iterator(this->_M_impl._M_end_of_storage)
             - begin()); }

可以通過代碼從一個vector對象地址輸出其信息：

template <typename T>
    void ds_vec_i(void *p) {
        T *start = *(T**)p;
        T *finish = *(T**)((char*)p + sizeof(void*));
        T *end_storage = *(T**)((char*)p + 2 * sizeof(void*));
        printf("vec size: %ld, avaiable size: %ld\n", finish - start, end_storage - start); 
    }

    size_t ds_vec() {
        std::vector<int> vec;
        vec.push_back(0x11);
        vec.push_back(0x22);
        vec.push_back(0x33);
        ds_vec_i<int>(&vec);
        return vec.size();
    }

使用gdb輸出一個vector中的內容：

(gdb) p p
$3 = (void *) 0x7fffffffe380
(gdb) x/1a p
0x7fffffffe380: 0x606080
(gdb) x/3xw 0x606080
0x606080:       0x00000011      0x00000022      0x00000033

list

眾所周知list被實現為一個鏈表。準確來說是一個雙向鏈表。list本身是一個特殊節點，其代表end，其指向的下一個元素才是list真正的第一個節點：

bits/stl_list.h

bool
      empty() const
      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

      const_iterator
      begin() const
      { return const_iterator(this->_M_impl._M_node._M_next); }

      iterator
      end()
      { return iterator(&this->_M_impl._M_node); }

      ...

    struct _List_node_base
    {
        _List_node_base* _M_next;   ///< Self-explanatory
        _List_node_base* _M_prev;   ///< Self-explanatory
        ...
    };
         
    template<typename _Tp>
    struct _List_node : public _List_node_base
    {
      _Tp _M_data;                ///< User's data.
    };
      
    template<typename _Tp, typename _Alloc>
    class _List_base
    {
        ...
      struct _List_impl
      : public _Node_alloc_type
      {
    _List_node_base _M_node;
        ...
      };

      _List_impl _M_impl;

          
    template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class list : protected _List_base<_Tp, _Alloc>

所以sizeof(list<xx>)=16，兩個指針。每一個真正的節點首先是包含兩個指針，然后是元素內容(_List_node)。

通過代碼輸出list的內容：

#define NEXT(ptr, T) do { \
        void *n = *(char**)ptr; \
        T val = *(T*)((char**)ptr + 2); \
        printf("list item %p val: 0x%x\n", ptr, val); \
        ptr = n; \
    } while (0)

    template <typename T>
    void ds_list_i(void *p) {
        void *ptr = *(char**)p;

        NEXT(ptr, T);
        NEXT(ptr, T);
        NEXT(ptr, T);
    }

    size_t ds_list() {
        std::list<int> lst;
        lst.push_back(0x11);
        lst.push_back(0x22);
        lst.push_back(0x33);
        ds_list_i<int>(&lst);
        return lst.size();
    }

在gdb中可以以下方式遍歷該list：

(gdb) p p
$4 = (void *) 0x7fffffffe390
(gdb) x/1a p
0x7fffffffe390: 0x606080
(gdb) x/1xw 0x606080+16         # 元素1 
0x606090:       0x00000011
(gdb) x/1a 0x606080
0x606080:       0x6060a0
(gdb) x/1xw 0x6060a0+16         # 元素2
0x6060b0:       0x00000022

map

map使用的是紅黑樹實現，實際使用的是stl_tree.h實現：

bits/stl_map.h

typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
               key_compare, _Pair_alloc_type> _Rep_type;
    ...
     _Rep_type _M_t;
    ... 

      iterator
      begin()
      { return _M_t.begin(); }

bits/stl_tree.h

struct _Rb_tree_node_base
      {
        typedef _Rb_tree_node_base* _Base_ptr;
        typedef const _Rb_tree_node_base* _Const_Base_ptr;

        _Rb_tree_color  _M_color;
        _Base_ptr       _M_parent;
        _Base_ptr       _M_left;
        _Base_ptr       _M_right;
        
        ...
      };

    template<typename _Val>
    struct _Rb_tree_node : public _Rb_tree_node_base
    {
      typedef _Rb_tree_node<_Val>* _Link_type;
      _Val _M_value_field;
    };


    template<typename _Key_compare,
           bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
        struct _Rb_tree_impl : public _Node_allocator
        {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.
      ...
        }
    
    _Rb_tree_impl<_Compare> _M_impl;
    ...

      iterator
      begin()
      {
    return iterator(static_cast<_Link_type>
            (this->_M_impl._M_header._M_left));
      }

所以可以看出，大部分時候(取決于_M_key_compare) sizeof(map<xx>)=48，主要的元素是：

_Rb_tree_color  _M_color; // 節點顏色
        _Base_ptr       _M_parent; // 父節點
        _Base_ptr       _M_left; // 左節點
        _Base_ptr       _M_right; // 右節點
        _Val            _M_value_field // 同list中節點技巧一致，后面是實際的元素

同list中的實現一致，map本身作為一個節點，其不是一個存儲數據的節點，

_Rb_tree::end

iterator
      end()
      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }

由于節點值在_Rb_tree_node_base后，所以任意時候拿到節點就可以偏移這個結構體拿到節點值，節點的值是一個pair，包含了key和value。

在gdb中打印以下map的內容：

size_t ds_map() {
        std::map<std::string, int> imap;
        imap["abc"] = 0xbbb;
        return imap.size();
    }

(gdb) p/x &imap
$7 = 0x7fffffffe370
(gdb) x/1a (char*)&imap+24       # _M_left 真正的節點
0x7fffffffe388: 0x606040          
(gdb) x/1xw 0x606040+32+8        # 偏移32字節是節點值的地址，再偏移8則是value的地址
0x606068:       0x00000bbb
(gdb) p *(char**)(0x606040+32)   # 偏移32字節是string的地址
$8 = 0x606028 "abc"

或者很多時候沒有必要這么裝逼+蛋疼：

(gdb) p *(char**)(imap._M_t._M_impl._M_header._M_left+1)
$9 = 0x606028 "abc"
(gdb) x/1xw (char*)(imap._M_t._M_impl._M_header._M_left+1)+8
0x606068:       0x00000bbb

完

posted @ 2014-12-03 22:08 Kevin Lynx 閱讀(3835) | 評論 (2) | 編輯收藏

2014年11月4日 #

linux動態庫的種種要點

linux下使用動態庫，基本用起來還是很容易。但如果我們的程序中大量使用動態庫來實現各種框架/插件，那么就會遇到一些坑，掌握這些坑才有利于程序更穩健地運行。

本篇先談談動態庫符號方面的問題。

測試代碼可以在github上找到

符號查找

一個應用程序test會鏈接一個動態庫libdy.so，如果一個符號，例如函數callfn定義于libdy.so中，test要使用該函數，簡單地聲明即可：

// dy.cpp libdy.so
void callfn() {
    ...
}

// main.cpp test
extern void callfn();

callfn();

在鏈接test的時候，鏈接器會統一進行檢查。

同樣，在libdy.so中有相同的規則，它可以使用一個外部的符號，在它被鏈接/載入進一個可執行程序時才會進行符號存在與否的檢查。這個符號甚至可以定義在test中，形成一種雙向依賴，或定義在其他動態庫中：

// dy.cpp libdy.so
extern void mfunc();

mfunc();

// main.cpp test
void mfunc() {
    ...
}

在生成libdy.so時mfunc可以找不到，此時mfunc為未定義：

$ nm libdy.so | grep mfun
U _Z5mfuncv

但在libdy.so被鏈接進test時則會進行檢查，試著把mfunc函數的定義去掉，就會得到一個鏈接錯誤：

./libdy.so: undefined reference to `mfunc()'

同樣，如果我們動態載入libdy.so，此時當然可以鏈接通過，但是在載入時同樣得到找不到符號的錯誤：

#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    dlclose(dp);
#else
    callfn();
#endif

得到錯誤：

./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

結論：基于以上，我們知道，如果一個動態庫依賴了一些外部符號，這些外部符號可以位于其他動態庫甚至應用程序中。我們可以再鏈接這個動態庫的時候就把依賴的其他庫也鏈接上，或者推遲到鏈接應用程序時再鏈接。而動態加載的庫，則要保證在加載該庫時，進程中加載的其他動態庫里已經存在該符號。

例如，通過LD_PRELOAD環境變量可以讓一個進程先加載指定的動態庫，上面那個動態加載啟動失敗的例子，可以通過預先加載包含mfunc符號的動態庫解決：

$ LD_PRELOAD=libmfun.so ./test
...

但是如果這個符號存在于可執行程序中則不行：

$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ ./test
...
./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

符號覆蓋

前面主要講的是符號缺少的情況，如果同一個符號存在多分，則更能引發問題。這里談到的符號都是全局符號，一個進程中某個全局符號始終是全局唯一的。為了保證這一點，在鏈接或動態載入動態庫時，就會出現忽略重復符號的情況。

這里就不提同一個鏈接單位（如可執行程序、動態庫）里符號重復的問題了

函數

當動態庫和libdy.so可執行程序test中包含同名的函數時會怎樣？根據是否動態加載情況還有所不同。

當直接鏈接動態庫時，libdy.so和test都會鏈接包含func函數的fun.o，為了區分，我把func按照條件編譯得到不同的版本：

// fun.cpp
#ifdef V2
extern "C" void func() {
    printf("func v2\n");
}
#else
extern "C" void func() {
    printf("func v1\n");
}
#endif

// Makefile
test: libdy obj.o mainfn
    g++ -g -Wall -c fun.cpp -o fun.o # 編譯為fun.o
    g++ -g -Wall -c main.cpp #-DDY_LOAD
    g++ -g -Wall -o test main.o obj.o fun.o -ldl mfun.o -ldy -L.

libdy: obj
    g++ -Wall -fPIC -c fun.cpp -DV2 -o fun-dy.o  # 定義V2宏，編譯為fun-dy.o
    g++ -Wall -fPIC -shared -o libdy.so dy.cpp -g obj.o fun-dy.o

這樣，test中的func就會輸出func v1；libdy.so中的func就會輸出func v2。test和libdy.o確實都有func符號：

$ nm libdy.so | grep func
0000000000000a60 T func

$nm test | grep func
0000000000400a80 T func

在test和libdy.so中都會調用func函數：

// main.cpp test
int main(int argc, char **argv) {
    func();
    ...
    callfn(); // 調用libdy.so中的函數
    ...
}

// dy.cpp libdy.so
extern "C" void callfn() {
    ... 
    printf("callfn\n");
    func();
    ...
}

運行后發現，都調用的是同一個func：

$ ./test
...
func v1
...
callfn
func v1

結論，直接鏈接動態庫時，整個程序運行的時候符號會發生覆蓋，只有一個符號被使用。在實踐中，如果程序和鏈接的動態庫都依賴了一個靜態庫，而后他們鏈接的這個靜態庫版本不同，則很有可能因為符號發生了覆蓋而導致問題。(靜態庫同普通的.o性質一樣，參考淺析靜態庫鏈接原理)

更復雜的情況中，多個動態庫和程序都有相同的符號，情況也是一樣，會發生符號覆蓋。如果程序里沒有這個符號，而多個動態庫里有相同的符號，也會覆蓋。

但是對于動態載入的情況則不同，同樣的libdy.so我們在test中不鏈接，而是動態載入：

int main(int argc, char **argv) {
    func();
#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    func();
    dlclose(dp);
#else
    callfn();
#endif
    return 0;
}

運行得到：

$ ./test
func v1
...
callfn
func v2
func v1

都正確地調用到各自鏈接的func。

結論，實踐中，動態載入的動態庫一般會作為插件使用，那么其同程序鏈接不同版本的靜態庫（相同符號不同實現），是沒有問題的。

變量

變量本質上也是符號(symbol)，但其處理規則和函數還有點不一樣(是不是有點想吐槽了)。

// object.h
class Object {
public:
    Object() {
#ifdef DF
        s = malloc(32);
        printf("s addr %p\n", s);
#endif
        printf("ctor %p\n", this);
    }

    ~Object() {
        printf("dtor %p\n", this);
#ifdef DF
        printf("s addr %p\n", s);
        free(s);
#endif
    }

    void *s;
};

extern Object g_obj;

我們的程序test和動態庫libdy.so都會鏈接object.o。首先測試test鏈接libdy.so，test和libdy.so中都會有g_obj這個符號：

// B g_obj 表示g_obj位于BSS段，未初始化段

$ nm test | grep g_obj
0000000000400a14 t _GLOBAL__I_g_obj
00000000006012c8 B g_obj
$ nm libdy.so | grep g_obj
000000000000097c t _GLOBAL__I_g_obj
0000000000200f30 B g_obj

運行：

$ ./test
ctor 0x6012c8
ctor 0x6012c8
...
dtor 0x6012c8
dtor 0x6012c8

g_obj被構造了兩次，但地址一樣。全局變量只有一個實例，似乎在情理之中。

動態載入libdy.so，變量地址還是相同的：

$ ./test
ctor 0x6012a8
...
ctor 0x6012a8
...
dtor 0x6012a8
dtor 0x6012a8

結論，不同于函數，全局變量符號重復時，不論動態庫是動態載入還是直接鏈接，變量始終只有一個。

但詭異的情況是，對象被構造和析構了兩次。構造兩次倒無所謂，浪費點空間，但是析構兩次就有問題。因為析構時都操作的是同一個對象，那么如果這個對象內部有分配的內存，那就會對這塊內存造成double free，因為指針相同。打開DF宏實驗下：

$ ./test
s addr 0x20de010
ctor 0x6012b8
s addr 0x20de040
ctor 0x6012b8
...
dtor 0x6012b8
s addr 0x20de040
dtor 0x6012b8
s addr 0x20de040

因為析構的兩次都是同一個對象，所以其成員s指向的內存被釋放了兩次，從而產生了double free，讓程序coredump了。

總結，全局變量符號重復時，始終會只使用一個，并且會被初始化/釋放兩次，是一種較危險的情況，應當避免在使用動態庫的過程中使用全局變量。

完

posted @ 2014-11-04 00:55 Kevin Lynx 閱讀(7960) | 評論 (1) | 編輯收藏

2014年10月19日 #

圖解zookeeper FastLeader選舉算法

zookeeper配置為集群模式時，在啟動或異常情況時會選舉出一個實例作為Leader。其默認選舉算法為FastLeaderElection。

不知道zookeeper的可以考慮這樣一個問題：某個服務可以配置為多個實例共同構成一個集群對外提供服務。其每一個實例本地都存有冗余數據，每一個實例都可以直接對外提供讀寫服務。在這個集群中為了保證數據的一致性，需要有一個Leader來協調一些事務。那么問題來了：如何確定哪一個實例是Leader呢？

問題的難點在于：

沒有一個仲裁者來選定Leader
每一個實例本地可能已經存在數據，不確定哪個實例上的數據是最新的

分布式選舉算法正是用來解決這個問題的。

本文基于zookeeper 3.4.6 的源碼進行分析。FastLeaderElection算法的源碼全部位于FastLeaderElection.java文件中，其對外接口為FastLeaderElection.lookForLeader，該接口是一個同步接口，直到選舉結束才會返回。同樣由于網上已有類似文章，所以我就從圖示的角度來闡述。閱讀一些其他文章有利于獲得初步印象：

深入淺出Zookeeper之五 Leader選舉，代碼導讀
zookeeper3.3.3源碼分析(二)FastLeader選舉算法，文字描述較細

主要流程

閱讀代碼和以上推薦文章可以把整個流程梳理清楚。實現上，包括了一個消息處理主循環，也是選舉的主要邏輯，以及一個消息發送隊列處理線程和消息解碼線程。主要流程可概括為下圖：

推薦對照著推薦的文章及代碼理解，不贅述。

我們從感性上來理解這個算法。

每一個節點，相當于一個選民，他們都有自己的推薦人，最開始他們都推薦自己。誰更適合成為Leader有一個簡單的規則，例如sid夠大（配置）、持有的數據夠新(zxid夠大)。每個選民都告訴其他選民自己目前的推薦人是誰，類似于出去搞宣傳拉攏其他選民。每一個選民發現有比自己更適合的人時就轉而推薦這個更適合的人。最后，大部分人意見一致時，就可以結束選舉。

就這么簡單。總體上有一種不斷演化逼近結果的感覺。

當然，會有些特殊情況的處理。例如總共3個選民，1和2已經確定3是Leader，但3還不知情，此時就走入LEADING/FOLLOWING的分支，選民3只是接收結果。

代碼中不是所有邏輯都在這個大流程中完成的。在接收消息線程中，還可能單獨地回應某個節點(WorkerReceiver.run)：

從這里可以看出，當某個節點已經確定選舉結果不再處于LOOKING狀態時，其收到LOOKING消息時都會直接回應選舉的最終結果。結合上面那個比方，相當于某次選舉結束了，這個時候來了選民4又發起一次新的選舉，那么其他選民就直接告訴它當前的Leader情況。相當于，在這個集群主從已經就緒的情況下，又開啟了一個實例，這個實例就會直接使用當前的選舉結果。

狀態轉換

每個節點上有一些關鍵的數據結構：

當前推薦人，初始推薦自己，每次收到其他更好的推薦人時就更新
其他人的投票集合，用于確定何時選舉結束

每次推薦人更新時就會進行廣播，正是這個不斷地廣播驅動整個算法趨向于結果。假設有3個節點A/B/C，其都還沒有數據，按照sid關系為C>B>A，那么按照規則，C更可能成為Leader，其各個節點的狀態轉換為：

圖中，v(A)表示當前推薦人為A；r[]表示收到的投票集合。

可以看看當其他節點已經確定投票結果時，即不再是LOOKING時的狀態：

代碼中有一個特殊的投票集合outofelection，我理解為選舉已結束的那些投票，這些投票僅用于表征選舉結果。

當一個新啟動的節點加入集群時，它對集群內其他節點發出投票請求，而其他節點已不處于LOOKING狀態，此時其他節點回應選舉結果，該節點收集這些結果到outofelection中，最終在收到合法LEADER消息且這些選票也構成選舉結束條件時，該節點就結束自己的選舉行為。注意到代碼中會logicalclock = n.electionEpoch;更新選舉輪數

完

posted @ 2014-10-19 15:58 Kevin Lynx 閱讀(4487) | 評論 (0) | 編輯收藏

2014年10月15日 #

圖解分布式一致性協議Paxos

Paxos協議/算法是分布式系統中比較重要的協議，它有多重要呢？

<分布式系統的事務處理>：

Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

<大規模分布式存儲系統>：

理解了這兩個分布式協議之后(Paxos/2PC)，學習其他分布式協議會變得相當容易。

學習Paxos算法有兩部分：a) 算法的原理/證明；b) 算法的理解/運作。

理解這個算法的運作過程其實基本就可以用于工程實踐。而且理解這個過程相對來說也容易得多。

網上我覺得講Paxos講的好的屬于這篇：paxos圖解及Paxos算法詳解，我這里就結合wiki上的實例進一步闡述。一些paxos基礎通過這里提到的兩篇文章，以及wiki上的內容基本可以理解。

算法內容

Paxos在原作者的《Paxos Made Simple》中內容是比較精簡的：

Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

借用paxos圖解文中的流程圖可概括為：

實例及詳解

Paxos中有三類角色Proposer、Acceptor及Learner，主要交互過程在Proposer和Acceptor之間。

Proposer與Acceptor之間的交互主要有4類消息通信，如下圖：

這4類消息對應于paxos算法的兩個階段4個過程：

phase 1
- a) proposer向網絡內超過半數的acceptor發送prepare消息
- b) acceptor正常情況下回復promise消息
phase 2
- a) 在有足夠多acceptor回復promise消息時，proposer發送accept消息
- b) 正常情況下acceptor回復accepted消息

因為在整個過程中可能有其他proposer針對同一件事情發出以上請求，所以在每個過程中都會有些特殊情況處理，這也是為了達成一致性所做的事情。如果在整個過程中沒有其他proposer來競爭，那么這個操作的結果就是確定無異議的。但是如果有其他proposer的話，情況就不一樣了。

以paxos中文wiki上的例子為例。簡單來說該例子以若干個議員提議稅收，確定最終通過的法案稅收比例。

以下圖中基本只畫出proposer與一個acceptor的交互。時間標志T2總是在T1后面。propose number簡稱N。

情況之一如下圖：

A3在T1發出accepted給A1，然后在T2收到A5的prepare，在T3的時候A1才通知A5最終結果(稅率10%)。這里會有兩種情況：

A5發來的N5小于A1發出去的N1，那么A3直接拒絕(reject)A5
A5發來的N5大于A1發出去的N1，那么A3回復promise，但帶上A1的(N1, 10%)

這里可以與paxos流程圖對應起來，更好理解。acceptor會記錄(MaxN, AcceptN, AcceptV)。

A5在收到promise后，后續的流程可以順利進行。但是發出accept時，因為收到了(AcceptN, AcceptV)，所以會取最大的AcceptN對應的AcceptV，例子中也就是A1的10%作為AcceptV。如果在收到promise時沒有發現有其他已記錄的AcceptV，則其值可以由自己決定。

針對以上A1和A5沖突的情況，最終A1和A5都會廣播接受的值為10%。

其實4個過程中對于acceptor而言，在回復promise和accepted時由于都可能因為其他proposer的介入而導致特殊處理。所以基本上看在這兩個時間點收到其他proposer的請求時就可以了解整個算法了。例如在回復promise時則可能因為proposer發來的N不夠大而reject：

如果在發accepted消息時，對其他更大N的proposer發出過promise，那么也會reject該proposer發出的accept，如圖：

這個對應于Phase 2 b)：

it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

總結

Leslie Lamport沒有用數學描述Paxos，但是他用英文闡述得很清晰。將Paxos的兩個Phase的內容理解清楚，整個算法過程還是不復雜的。

至于Paxos中一直提到的一個全局唯一且遞增的proposer number，其如何實現，引用如下：

如何產生唯一的編號呢？在《Paxos made simple》中提到的是讓所有的Proposer都從不相交的數據集合中進行選擇，例如系統有5個Proposer，則可為每一個Proposer分配一個標識j(0~4)，則每一個proposer每次提出決議的編號可以為5*i + j(i可以用來表示提出議案的次數)

參考文檔

paxos圖解, http://coderxy.com/archives/121
Paxos算法詳解, http://coderxy.com/archives/136
Paxos算法 wiki, http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95#.E5.AE.9E.E4.BE.8B

posted @ 2014-10-15 22:45 Kevin Lynx 閱讀(10342) | 評論 (6) | 編輯收藏

2014年10月12日 #

淘寶分布式配置管理服務Diamond

在一個分布式環境中，同類型的服務往往會部署很多實例。這些實例使用了一些配置，為了更好地維護這些配置就產生了配置管理服務。通過這個服務可以輕松地管理這些應用服務的配置問題。應用場景可概括為：

zookeeper的一種應用就是分布式配置管理(基于ZooKeeper的配置信息存儲方案的設計與實現)。百度也有類似的實現：disconf。

Diamond則是淘寶開源的一種分布式配置管理服務的實現。Diamond本質上是一個Java寫的Web應用，其對外提供接口都是基于HTTP協議的，在閱讀代碼時可以從實現各個接口的controller入手。

分布式配置管理

分布式配置管理的本質基本上就是一種推送-訂閱模式的運用。配置的應用方是訂閱者，配置管理服務則是推送方。概括為下圖：

其中，客戶端包括管理人員publish數據到配置管理服務，可以理解為添加/更新數據；配置管理服務notify數據到訂閱者，可以理解為推送。

配置管理服務往往會封裝一個客戶端庫，應用方則是基于該庫與配置管理服務進行交互。在實際實現時，客戶端庫可能是主動拉取(pull)數據，但對于應用方而言，一般是一種事件通知方式。

Diamond中的數據是簡單的key-value結構。應用方訂閱數據則是基于key來訂閱，未訂閱的數據當然不會被推送。數據從類型上又劃分為聚合和非聚合。因為數據推送者可能很多，在整個分布式環境中，可能有多個推送者在推送相同key的數據，這些數據如果是聚合的，那么所有這些推送者推送的數據會被合并在一起；反之如果是非聚合的，則會出現覆蓋。

數據的來源可能是人工通過管理端錄入，也可能是其他服務通過配置管理服務的推送接口自動錄入。

架構及實現

Diamond服務是一個集群，是一個去除了單點的協作集群。如圖：

圖中可分為以下部分講解：

服務之間同步

Diamond服務集群每一個實例都可以對外完整地提供服務，那么意味著每個實例上都有整個集群維護的數據。Diamond有兩種方式保證這一點：

任何一個實例都有其他實例的地址；任何一個實例上的數據變更時，都會將改變的數據同步到mysql上，然后通知其他所有實例從mysql上進行一次數據拉取(DumpService::dump)，這個過程只拉取改變了的數據
任何一個實例啟動后都會以較長的時間間隔（幾小時），從mysql進行一次全量的數據拉取(DumpAllProcessor)

實現上為了一致性，通知其他實例實際上也包含自己。以服務器收到添加聚合數據為例，處理過程大致為：

DatumController::addDatum // /datum.do?method=addDatum
    PersistService::addAggrConfigInfo 
    MergeDatumService::addMergeTask // 添加一個MergeDataTask，異步處理

MergeTaskProcessor::process
    PersistService::insertOrUpdate
        EventDispatcher.fireEvent(new ConfigDataChangeEvent // 派發一個ConfigDataChangeEvent事件

NotifyService::onEvent // 接收事件并處理
    TaskManager::addTask(..., new NotifyTask // 由此，當數據發生變動，則最終創建了一個NoticyTask

// NotifyTask同樣異步處理
NotifyTaskProcessor::process
    foreach server in serverList // 包含自己
        notifyToDump // 調用 /notify.do?method=notifyConfigInfo 從mysql更新變動的數據

雖然Diamond去除了單點問題，不過問題都下降到了mysql上。但由于其作為配置管理的定位，其數據量就mysql的應用而言算小的了，所以可以一定程度上保證整個服務的可用性。

數據一致性

由于Diamond服務器沒有master，任何一個實例都可以讀寫數據，那么針對同一個key的數據則可能面臨沖突。這里應該是通過mysql來保證數據的一致性。每一次客戶端請求寫數據時，Diamond都將寫請求投遞給mysql，然后通知集群內所有Diamond實例（包括自己）從mysql拉取數據。當然，拉取數據則可能不是每一次寫入都能拉出來，也就是最終一致性。

Diamond中沒有把數據放入內存，但會放到本地文件。對于客戶端的讀操作而言，則是直接返回本地文件里的數據。

服務實例列表

Diamond服務實例列表是一份靜態數據，直接將每個實例的地址存放在一個web server上。無論是Diamond服務還是客戶端都從該web server上取出實例列表。

對于客戶端而言，當其取出了該列表后，則是隨機選擇一個節點(ServerListManager.java)，以后的請求都會發往該節點。

數據同步

客戶端庫中以固定時間間隔從服務器拉取數據(ClientWorker::ClientWorker，ClientWorker::checkServerConfigInfo)。只有應用方關心的數據才可能被拉取。另外，為了數據推送的及時，Diamond還使用了一種long polling的技術，其實也是為了突破HTTP協議的局限性。如果整個服務是基于TCP的自定義協議，客戶端與服務器保持長連接則沒有這些問題。

數據的變更

Diamond中很多操作都會檢查數據是否發生了變化。標識數據變化則是基于數據對應的MD5值來實現的。

容災

在整個Diamond系統中，幾個角色為了提高容災性，都有自己的緩存，概括為下圖：

每一個角色出問題時，都可以盡量保證客戶端對應用層提供服務。

posted @ 2014-10-12 12:57 Kevin Lynx 閱讀(2716) | 評論 (4) | 編輯收藏

僅列出標題下一頁

導航

統計

公告

常用鏈接

留言簿(52)

隨筆分類

隨筆檔案

收藏夾

C++

關注的開源項目

其他關注

網絡編程

我的項目

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

名字服務

What’s JCM

架構

使用

JCM實現

數據同步

健康檢查

jcm.subscriber通信

壓力測試

總結

主要問題

解決方案

ABA問題

總結

原理

Hazard Pointer的管理

附錄

Lock Free & Wait Free

ABA問題

RCU

實現

寫線程

讀線程

線程動態增加/減少

線程可讀可寫

現象

分析GetStackTrace

錯誤的RBP

錯誤RBP的來源

coredump的條件

總結

附

string

vector

list

map

符號查找

符號覆蓋

函數

變量

主要流程

狀態轉換

算法內容

實例及詳解

總結

參考文檔

分布式配置管理

架構及實現

服務之間同步

數據一致性

服務實例列表

數據同步

數據的變更

容災

參考文檔