• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            loop_in_codes

            低調(diào)做技術(shù)__歡迎移步我的獨(dú)立博客 codemaro.com 微博 kevinlynx

            2015年7月4日 #

            寫(xiě)了一個(gè)分布式名字服務(wù)JCM

            之前在公司里維護(hù)了一個(gè)名字服務(wù),這個(gè)名字服務(wù)日常管理了近4000臺(tái)機(jī)器,有4000個(gè)左右的客戶(hù)端連接上來(lái)獲取機(jī)器信息,由于其基本是一個(gè)單點(diǎn)服務(wù),所以某些模塊接近瓶頸。后來(lái)倒是有重構(gòu)計(jì)劃,詳細(xì)設(shè)計(jì)做了,代碼都寫(xiě)了一部分,結(jié)果由于某些原因重構(gòu)就被終止了。

            JCM是我業(yè)余時(shí)間用Java重寫(xiě)的一個(gè)版本,功能上目前只實(shí)現(xiàn)了基礎(chǔ)功能。由于它是個(gè)完全分布式的架構(gòu),所以理論上可以橫向擴(kuò)展,大大增強(qiáng)系統(tǒng)的服務(wù)能力。

            名字服務(wù)

            在分布式系統(tǒng)中,某個(gè)服務(wù)為了提升整體服務(wù)能力,通常部署了很多實(shí)例。這里我把這些提供相同服務(wù)的實(shí)例統(tǒng)稱(chēng)為集群(cluster),每個(gè)實(shí)例稱(chēng)為一個(gè)節(jié)點(diǎn)(Node)。一個(gè)應(yīng)用可能會(huì)使用很多cluster,每次訪問(wèn)一個(gè)cluster時(shí),就通過(guò)名字服務(wù)獲取該cluster下一個(gè)可用的node。那么,名字服務(wù)至少需要包含的功能:

            • 根據(jù)cluster名字獲取可用的node
            • 對(duì)管理的所有cluster下的所有node進(jìn)行健康度的檢測(cè),以保證始終返回可用的node

            有些名字服務(wù)僅對(duì)node管理,不參與應(yīng)用與node間的通信,而有些則可能作為應(yīng)用與node間的通信轉(zhuǎn)發(fā)器。雖然名字服務(wù)功能簡(jiǎn)單,但是要做一個(gè)分布式的名字服務(wù)還是比較復(fù)雜的,因?yàn)閿?shù)據(jù)一旦分布式了,就會(huì)存在同步、一致性問(wèn)題的考慮等。

            What’s JCM

            JCM圍繞前面說(shuō)的名字服務(wù)基礎(chǔ)功能實(shí)現(xiàn)。包含的功能:

            • 管理cluster到node的映射
            • 分布式架構(gòu),可水平擴(kuò)展以實(shí)現(xiàn)管理10,000個(gè)node的能力,足以管理一般公司的后臺(tái)服務(wù)集群
            • 對(duì)每個(gè)node進(jìn)行健康檢查,健康檢查可基于HTTP協(xié)議層的檢測(cè)或TCP連接檢測(cè)
            • 持久化cluster/node數(shù)據(jù),通過(guò)zookeeper保證數(shù)據(jù)一致性
            • 提供JSON HTTP API管理cluster/node數(shù)據(jù),后續(xù)可提供Web管理系統(tǒng)
            • 以庫(kù)的形式提供與server的交互,庫(kù)本身提供各種負(fù)載均衡策略,保證對(duì)一個(gè)cluster下node的訪問(wèn)達(dá)到負(fù)載均衡

            項(xiàng)目地址git jcm

            JCM主要包含兩部分:

            • jcm.server,JCM名字服務(wù),需要連接zookeeper以持久化數(shù)據(jù)
            • jcm.subscriber,客戶(hù)端庫(kù),負(fù)責(zé)與jcm.server交互,提供包裝了負(fù)載均衡的API給應(yīng)用使用

            架構(gòu)

            基于JCM的系統(tǒng)整體架構(gòu)如下:

            simple-arch.jpg

            cluster本身是不需要依賴(lài)JCM的,要通過(guò)JCM使用這些cluster,只需要通過(guò)JCM HTTP API注冊(cè)這些cluster到j(luò)cm.server上。要通過(guò)jcm.server使用這些cluster,則是通過(guò)jcm.subscriber來(lái)完成。

            使用

            可參考git READMe.md

            需要jre1.7+

            1. 啟動(dòng)zookeeper
            2. 下載jcm.server git jcm.server-0.1.0.jar
            3. jcm.server-0.1.0.jar目錄下建立config/application.properties文件進(jìn)行配置,參考config/application.properties
            4. 啟動(dòng)jcm.server

               java -jar jcm.server-0.1.0.jar
              
            5. 注冊(cè)需要管理的集群,參考cluster描述:doc/cluster_sample.json,通過(guò)HTTP API注冊(cè):

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

            部署好了jcm.server,并注冊(cè)了cluster后,就可以通過(guò)jcm.subscriber使用:

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

            JCM實(shí)現(xiàn)

            JCM目前的實(shí)現(xiàn)比較簡(jiǎn)單,參考模塊圖:

            impl-module

            • model,即cluster/node這些數(shù)據(jù)結(jié)構(gòu)的描述,同時(shí)被jcm.server和jcm.subscriber依賴(lài)
            • storage,持久化數(shù)據(jù)到zookeeper,同時(shí)包含jcm.server實(shí)例之間的數(shù)據(jù)同步
            • health check,健康檢查模塊,對(duì)各個(gè)node進(jìn)行健康檢查

            以上模塊都不依賴(lài)Spring,基于以上模塊又有:

            • http api,使用spring-mvc,包裝了一些JSON HTTP API
            • Application,基于spring-boot,將各個(gè)基礎(chǔ)模塊組裝起來(lái),提供standalone的模式啟動(dòng),不用部署到tomcat之類(lèi)的servlet容器中

            jcm.subscriber的實(shí)現(xiàn)更簡(jiǎn)單,主要是負(fù)責(zé)與jcm.server進(jìn)行通信,以更新自己當(dāng)前的model層數(shù)據(jù),同時(shí)提供各種負(fù)載均衡策略接口:

            • subscriber,與jcm.server通信,定期增量拉取數(shù)據(jù)
            • node allocator,通過(guò)listener方式從subscriber中獲取數(shù)據(jù),同時(shí)實(shí)現(xiàn)各種負(fù)載均衡策略,對(duì)外統(tǒng)一提供alloc node的接口

            接下來(lái)看看關(guān)鍵功能的實(shí)現(xiàn)

            數(shù)據(jù)同步

            既然jcm.server是分布式的,每一個(gè)jcm.server instance(實(shí)例)都是支持?jǐn)?shù)據(jù)讀和寫(xiě)的,那么當(dāng)jcm.server管理著一堆cluster上萬(wàn)個(gè)node時(shí),每一個(gè)instance是如何進(jìn)行數(shù)據(jù)同步的?jcm.server中的數(shù)據(jù)主要有兩類(lèi):

            • cluster本身的數(shù)據(jù),包括cluster/node的描述,例如cluster name、node IP、及其他附屬數(shù)據(jù)
            • node健康檢查的數(shù)據(jù)

            對(duì)于cluster數(shù)據(jù),因?yàn)閏luster對(duì)node的管理是一個(gè)兩層的樹(shù)狀結(jié)構(gòu),而對(duì)cluster有增刪node的操作,所以并不能在每一個(gè)instance上都提供真正的數(shù)據(jù)寫(xiě)入,這樣會(huì)導(dǎo)致數(shù)據(jù)丟失。假設(shè)同一時(shí)刻在instance A和instance B上同時(shí)對(duì)cluster c1添加節(jié)點(diǎn)N1和N2,那么instance A寫(xiě)入c1(N1),而instance B還沒(méi)等到數(shù)據(jù)同步就寫(xiě)入c1(N2),那么c1(N1)就被覆蓋為c1(N2),從而導(dǎo)致添加的節(jié)點(diǎn)N1丟失。

            所以,jcm.server instance是分為leaderfollower的,真正的寫(xiě)入操作只有l(wèi)eader進(jìn)行,follower收到寫(xiě)操作請(qǐng)求時(shí)轉(zhuǎn)發(fā)給leader。leader寫(xiě)數(shù)據(jù)優(yōu)先更新內(nèi)存中的數(shù)據(jù)再寫(xiě)入zookeeper,內(nèi)存中的數(shù)據(jù)更新當(dāng)然是需要加鎖互斥的,從而保證數(shù)據(jù)的正確性。

            write-watch.jpg

            leader和follower是如何確定角色的?這個(gè)很簡(jiǎn)單,標(biāo)準(zhǔn)的利用zookeeper來(lái)進(jìn)行主從選舉的實(shí)現(xiàn)

            jcm.server instance數(shù)據(jù)間的同步是基于zookeeper watch機(jī)制的。這個(gè)可以算做是一個(gè)JCM的一個(gè)瓶頸,每一個(gè)instance都會(huì)作為一個(gè)watch,使得實(shí)際上jcm.server并不能無(wú)限水平擴(kuò)展,擴(kuò)展到一定程度后,watch的效率就可能不足以滿(mǎn)足性能了,參考zookeeper節(jié)點(diǎn)數(shù)與watch的性能測(cè)試 (那個(gè)時(shí)候我就在考慮對(duì)我們系統(tǒng)的重構(gòu)了) 。

            jcm.server中對(duì)node健康檢查的數(shù)據(jù)采用同樣的同步機(jī)制,但node健康檢查數(shù)據(jù)是每一個(gè)instance都會(huì)寫(xiě)入的,下面看看jcm.server是如何通過(guò)分布式架構(gòu)來(lái)分擔(dān)壓力的。

            健康檢查

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

            健康檢查按cluster劃分,可以簡(jiǎn)化數(shù)據(jù)的寫(xiě)沖突問(wèn)題,在正常情況下,每個(gè)instance寫(xiě)入的健康檢查結(jié)果都是不同的。

            health-check.jpg

            健康檢查一般以1秒的頻率進(jìn)行,jcm.server做了優(yōu)化,當(dāng)檢查結(jié)果和上一次一樣時(shí),并不寫(xiě)入zookeeper。寫(xiě)入的數(shù)據(jù)包含了node的完整key (IP+Port+Spec),這樣可以簡(jiǎn)化很多地方的數(shù)據(jù)同步問(wèn)題,但會(huì)增加寫(xiě)入數(shù)據(jù)的大小,寫(xiě)入數(shù)據(jù)的大小是會(huì)影響zookeeper的性能的,所以這里簡(jiǎn)單地對(duì)數(shù)據(jù)進(jìn)行了壓縮。

            健康檢查是可以支持多種檢查實(shí)現(xiàn)的,目前只實(shí)現(xiàn)了HTTP協(xié)議層的檢查。健康檢查自身是單個(gè)線程,在該線程中基于異步HTTP庫(kù),發(fā)起異步請(qǐng)求,實(shí)際的請(qǐng)求在其他線程中發(fā)出。

            jcm.subscriber通信

            jcm.subscriber與jcm.server通信,主要是為了獲取最新的cluster數(shù)據(jù)。subscriber初始化時(shí)會(huì)拿到一個(gè)jcm.server instance的地址列表,訪問(wèn)時(shí)使用輪詢(xún)策略以平衡jcm.server在處理請(qǐng)求時(shí)的負(fù)載。subscriber每秒都會(huì)請(qǐng)求一次數(shù)據(jù),請(qǐng)求中描述了本次請(qǐng)求想獲取哪些cluster數(shù)據(jù),同時(shí)攜帶一個(gè)cluster的version。每次cluster在server變更時(shí),version就變更(時(shí)間戳)。server回復(fù)請(qǐng)求時(shí),如果version已最新,只需要回復(fù)node的狀態(tài)。

            subscriber可以拿到所有狀態(tài)的node,后面可以考慮只拿正常狀態(tài)的node,進(jìn)一步減少數(shù)據(jù)大小。

            壓力測(cè)試

            目前只對(duì)健康檢查部分做了壓測(cè),詳細(xì)參考test/benchmark.md。在A7服務(wù)器上測(cè)試,發(fā)現(xiàn)寫(xiě)zookeeper及zookeeper的watch足以滿(mǎn)足要求,jcm.server發(fā)起的HTTP請(qǐng)求是主要的性能熱點(diǎn),單jcm.server instance大概可以承載20000個(gè)node的健康監(jiān)測(cè)。

            網(wǎng)絡(luò)帶寬:

            1
            2
            3
            4
            5
            
            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,通過(guò)jstack查看主要的CPU消耗在HTTP庫(kù)實(shí)現(xiàn)層,以及健康檢查線程:

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

            代碼中增加了些狀態(tài)監(jiān)控:

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

            表示平均每次檢查耗時(shí)542毫秒,寫(xiě)數(shù)據(jù)因?yàn)殚_(kāi)啟了cache沒(méi)有參考價(jià)值。

            雖然還可以從我自己的代碼中做不少優(yōu)化,但既然單機(jī)可以承載20000個(gè)節(jié)點(diǎn)的檢測(cè),一般的應(yīng)用遠(yuǎn)遠(yuǎn)足夠了。

            總結(jié)

            名字服務(wù)在分布式系統(tǒng)中雖然是基礎(chǔ)服務(wù),但往往承擔(dān)了非常重要的角色,數(shù)據(jù)同步出現(xiàn)錯(cuò)誤、節(jié)點(diǎn)狀態(tài)出現(xiàn)瞬時(shí)的錯(cuò)誤,都可能對(duì)整套系統(tǒng)造成較大影響,業(yè)務(wù)上出現(xiàn)較大故障。所以名字服務(wù)的健壯性、可用性非常重要。實(shí)現(xiàn)中需要考慮很多異常情況,包括網(wǎng)絡(luò)不穩(wěn)定、應(yīng)用層的錯(cuò)誤等。為了提高足夠的可用性,一般還會(huì)加多層的數(shù)據(jù)cache,例如subscriber端的本地cache,server端的本地cache,以保證在任何情況下都不會(huì)影響應(yīng)用層的服務(wù)。

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

            2015年5月5日 #

            無(wú)鎖有序鏈表的實(shí)現(xiàn)

            無(wú)鎖有序鏈表可以保證元素的唯一性,使其可用于哈希表的桶,甚至直接作為一個(gè)效率不那么高的map。普通鏈表的無(wú)鎖實(shí)現(xiàn)相對(duì)簡(jiǎn)單點(diǎn),因?yàn)椴迦朐乜梢栽诒眍^插,而有序鏈表的插入則是任意位置。

            本文主要基于論文High Performance Dynamic Lock-Free Hash Tables實(shí)現(xiàn)。

            主要問(wèn)題

            鏈表的主要操作包含insertremove,先簡(jiǎn)單實(shí)現(xiàn)一個(gè)版本,就會(huì)看到問(wèn)題所在,以下代碼只用作示例:

            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函數(shù)返回查找到的前序元素和元素本身,代碼A和B雖然拿到了preditem,但在CAS的時(shí)候,其可能被其他線程移除。甚至,在l_find過(guò)程中,其每一個(gè)元素都可能被移除。問(wèn)題在于,任何時(shí)候拿到一個(gè)元素時(shí),都不確定其是否還有效。元素的有效性包括其是否還在鏈表中,其指向的內(nèi)存是否還有效。

            解決方案

            通過(guò)為元素指針增加一個(gè)有效性標(biāo)志位,配合CAS操作的互斥性,就可以解決元素有效性判定問(wèn)題。

            因?yàn)?code>node_t放在內(nèi)存中是會(huì)對(duì)齊的,所以指向node_t的指針值低幾位是不會(huì)用到的,從而可以在低幾位里設(shè)置標(biāo)志,這樣在做CAS的時(shí)候,就實(shí)現(xiàn)了DCAS的效果,相當(dāng)于將兩個(gè)邏輯上的操作變成了一個(gè)原子操作。想象下引用計(jì)數(shù)對(duì)象的線程安全性,其內(nèi)包裝的指針是線程安全的,但對(duì)象本身不是。

            CAS的互斥性,在若干個(gè)線程CAS相同的對(duì)象時(shí),只有一個(gè)線程會(huì)成功,失敗的線程就可以以此判定目標(biāo)對(duì)象發(fā)生了變更。改進(jìn)后的代碼(代碼僅做示例用,不保證正確):

            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可能被刪除,此時(shí)pred->next被標(biāo)記
                        //    pred->next != item,該CAS會(huì)失敗,失敗后重試
                        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前先標(biāo)記item->next,如果CAS失敗,那么情況同insert一樣,有其他線程在find之后
                        //    刪除了item,失敗后重試
                        if (!CAS(&item->next, inext, MARK(inext))) {
                            continue;
                        }
                        // C. 對(duì)同一個(gè)元素item刪除時(shí),只會(huì)有一個(gè)線程成功走到這里
                        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);
                        /* 
                         如果已被標(biāo)記,那么緊接著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_gethaz_set_ptr之類(lèi)的函數(shù)是一個(gè)hazard pointer實(shí)現(xiàn),用于支持多線程下內(nèi)存的GC。上面的代碼中,要?jiǎng)h除一個(gè)元素item時(shí),會(huì)標(biāo)記item->next,從而使得insert時(shí)中那個(gè)CAS不需要做任何調(diào)整。總結(jié)下這里的線程競(jìng)爭(zhēng)情況:

            • insertfind到正常的preditempred->next == item,然后在CAS前有線程刪除了pred,此時(shí)pred->next == MARK(item)CAS失敗,重試;刪除分為2種情況:a) 從鏈表移除,得到標(biāo)記,pred可繼續(xù)訪問(wèn);b) pred可能被釋放內(nèi)存,此時(shí)再使用pred會(huì)錯(cuò)誤。為了處理情況b,所以引入了類(lèi)似hazard pointer的機(jī)制,可以有效保障任意一個(gè)指針p只要還有線程在使用它,它的內(nèi)存就不會(huì)被真正釋放
            • insert中有多個(gè)線程在pred后插入元素,此時(shí)同樣由insert中的CAS保證,這個(gè)不多說(shuō)
            • remove中情況同insertfind拿到了有效的prednext,但在CAS的時(shí)候pred被其他線程刪除,此時(shí)情況同insertCAS失敗,重試
            • 任何時(shí)候改變鏈表結(jié)構(gòu)時(shí),無(wú)論是remove還是insert,都需要重試該操作
            • find中遍歷時(shí),可能會(huì)遇到被標(biāo)記刪除的item,此時(shí)item根據(jù)remove的實(shí)現(xiàn)很可能被刪除,所以需要重頭開(kāi)始遍歷

            ABA問(wèn)題

            ABA問(wèn)題還是存在的,insert中:

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

            如果CAS之前,pred后的item被移除,又以相同的地址值加進(jìn)來(lái),但其value變了,此時(shí)CAS會(huì)成功,但鏈表可能就不是有序的了。pred->val < new_item->val > item->val

            為了解決這個(gè)問(wèn)題,可以利用指針值地址對(duì)齊的其他位來(lái)存儲(chǔ)一個(gè)計(jì)數(shù),用于表示pred->next的改變次數(shù)。當(dāng)insert拿到pred時(shí),pred->next中存儲(chǔ)的計(jì)數(shù)假設(shè)是0,CAS之前其他線程移除了pred->next又新增回了item,此時(shí)pred->next中的計(jì)數(shù)增加,從而導(dǎo)致insertCAS失敗。

            // 最低位留作刪除標(biāo)志
                #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的實(shí)現(xiàn):

            /* 先標(biāo)記再刪除 */
                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的計(jì)數(shù)。

            總結(jié)

            無(wú)鎖的實(shí)現(xiàn),本質(zhì)上都會(huì)依賴(lài)于CAS的互斥性。從頭實(shí)現(xiàn)一個(gè)lock free的數(shù)據(jù)結(jié)構(gòu),可以深刻感受到lock free實(shí)現(xiàn)的tricky。最終代碼可以從這里github獲取。代碼中為了簡(jiǎn)單,實(shí)現(xiàn)了一個(gè)不是很強(qiáng)大的hazard pointer,可以參考之前的博文

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

            2015年5月3日 #

            并行編程中的內(nèi)存回收Hazard Pointer

            接上篇使用RCU技術(shù)實(shí)現(xiàn)讀寫(xiě)線程無(wú)鎖,在沒(méi)有GC機(jī)制的語(yǔ)言中,要實(shí)現(xiàn)Lock free的算法,就免不了要自己處理內(nèi)存回收的問(wèn)題。

            Hazard Pointer是另一種處理這個(gè)問(wèn)題的算法,而且相比起來(lái)不但簡(jiǎn)單,功能也很強(qiáng)大。鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針中講得很好,Wikipedia Hazard pointer也描述得比較清楚,所以我這里就不講那么細(xì)了。

            一個(gè)簡(jiǎn)單的實(shí)現(xiàn)可以參考我的github haz_ptr.c

            原理

            基本原理無(wú)非也是讀線程對(duì)指針進(jìn)行標(biāo)識(shí),指針(指向的內(nèi)存)要釋放時(shí)都會(huì)緩存起來(lái)延遲到確認(rèn)沒(méi)有讀線程了才對(duì)其真正釋放。

            <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.”

            關(guān)鍵的結(jié)構(gòu)包括:Hazard pointerThread Free list

            Hazard pointer:一個(gè)讀線程要使用一個(gè)指針時(shí),就會(huì)創(chuàng)建一個(gè)Hazard pointer包裝這個(gè)指針。一個(gè)Hazard pointer會(huì)被一個(gè)線程寫(xiě),多個(gè)線程讀。

            struct HazardPointer {
                    void *real_ptr; // 包裝的指針
                    ... // 不同的實(shí)現(xiàn)有不同的成員
                };
            
                void func() {
                    HazardPointer *hp = accquire(_real_ptr);
                    ... // use _real_ptr
                    release(hp);
                }

            Thread Free List:每個(gè)線程都有一個(gè)這樣的列表,保存著將要釋放的指針列表,這個(gè)列表僅對(duì)應(yīng)的線程讀寫(xiě)

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

            當(dāng)某個(gè)線程要嘗試釋放Free List中的指針時(shí),例如指針ptr,就檢查所有其他線程使用的Hazard pointer,檢查是否存在包裝了ptr的Hazard pointer,如果沒(méi)有則說(shuō)明沒(méi)有讀線程正在使用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
                    }
                }

            以上,其實(shí)就是Hazard Pointer的主要內(nèi)容。

            Hazard Pointer的管理

            上面的代碼中沒(méi)有提到_all_hazard_pointersaccquire的具體實(shí)現(xiàn),這就是Hazard Pointer的管理問(wèn)題。

            《鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》文中創(chuàng)建了一個(gè)Lock free的鏈表來(lái)表示這個(gè)全局的Hazard Pointer List。每個(gè)Hazard Pointer有一個(gè)成員標(biāo)識(shí)其是否可用。這個(gè)List中也就保存了已經(jīng)被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合,當(dāng)所有Hazard Pointer都被使用時(shí),就會(huì)新分配一個(gè)加進(jìn)這個(gè)List。當(dāng)讀線程不使用指針時(shí),需要?dú)w還Hazard Pointer,直接設(shè)置可用成員標(biāo)識(shí)即可。要gc()時(shí),就直接遍歷這個(gè)List。

            要實(shí)現(xiàn)一個(gè)Lock free的鏈表,并且僅需要實(shí)現(xiàn)頭插入,還是非常簡(jiǎn)單的。本身Hazard Pointer標(biāo)識(shí)某個(gè)指針時(shí),都是用了后立即標(biāo)識(shí),所以這個(gè)實(shí)現(xiàn)直接支持了動(dòng)態(tài)線程,支持線程的掛起等。

            nbds項(xiàng)目中也有一個(gè)Hazard Pointer的實(shí)現(xiàn),相對(duì)要弱一點(diǎn)。它為每個(gè)線程都設(shè)置了自己的Hazard Pointer池,寫(xiě)線程要釋放指針時(shí),就訪問(wèn)所有其他線程的Hazard Pointer池。

            typedef struct haz_local {
                    // Free List
                    pending_t *pending; // to be freed
                    int pending_size;
                    int pending_count;
            
                    // Hazard Pointer 池,動(dòng)態(tài)和靜態(tài)兩種
                    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] = {};

            每個(gè)線程當(dāng)然就涉及到haz_local_索引(ID)的分配,就像使用RCU技術(shù)實(shí)現(xiàn)讀寫(xiě)線程無(wú)鎖中的一樣。這個(gè)實(shí)現(xiàn)為了支持線程動(dòng)態(tài)創(chuàng)建,就需要一套線程ID的重用機(jī)制,相對(duì)復(fù)雜多了。

            附錄

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

            Lock Free & Wait Free

            常常看到Lock FreeWait Free的概念,這些概念用于衡量一個(gè)系統(tǒng)或者說(shuō)一段代碼的并行級(jí)別,并行級(jí)別可參考并行編程——并發(fā)級(jí)別。總之Wait Free是一個(gè)比Lock Free更牛逼的級(jí)別。

            我自己的理解,例如《鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》中實(shí)現(xiàn)的Hazard Pointer鏈表就可以說(shuō)是Lock Free的,注意它在插入新元素到鏈表頭時(shí),因?yàn)槭褂?code>CAS,總免不了一個(gè)busy loop,有這個(gè)特征的情況下就算是Lock Free,雖然沒(méi)鎖,但某個(gè)線程的執(zhí)行情況也受其他線程的影響。

            相對(duì)而言,Wait Free則是每個(gè)線程的執(zhí)行都是獨(dú)立的,例如《鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》中的Scan函數(shù)。“每個(gè)線程的執(zhí)行時(shí)間都不依賴(lài)于其它任何線程的行為”

            鎖無(wú)關(guān)(Lock-Free)意味著系統(tǒng)中總存在某個(gè)線程能夠得以繼續(xù)執(zhí)行;而等待無(wú)關(guān)(Wait-Free)則是一個(gè)更強(qiáng)的條件,它意味著所有線程都能往下進(jìn)行。

            ABA問(wèn)題

            在實(shí)現(xiàn)Lock Free算法的過(guò)程中,總是要使用CAS原語(yǔ)的,而CAS就會(huì)帶來(lái)ABA問(wèn)題。

            在進(jìn)行CAS操作的時(shí)候,因?yàn)樵诟腣之前,CAS主要詢(xún)問(wèn)“V的值是否仍然為A”,所以在第一次讀取V之后以及對(duì)V執(zhí)行CAS操作之前,如果將值從A改為B,然后再改回A,會(huì)使基于CAS的算法混亂。在這種情況下,CAS操作會(huì)成功。這類(lèi)問(wèn)題稱(chēng)為ABA問(wèn)題。

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

            對(duì)于CAS產(chǎn)生的這個(gè)ABA問(wèn)題,通常的解決方案是采用CAS的一個(gè)變種DCAS。DCAS,是對(duì)于每一個(gè)V增加一個(gè)引用的表示修改次數(shù)的標(biāo)記符。對(duì)于每個(gè)V,如果引用修改了一次,這個(gè)計(jì)數(shù)器就加1。然后再這個(gè)變量需要update的時(shí)候,就同時(shí)檢查變量的值和計(jì)數(shù)器的值。

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

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

            2015年4月19日 #

            使用RCU技術(shù)實(shí)現(xiàn)讀寫(xiě)線程無(wú)鎖

            在一個(gè)系統(tǒng)中有一個(gè)寫(xiě)線程和若干個(gè)讀線程,讀寫(xiě)線程通過(guò)一個(gè)指針共用了一個(gè)數(shù)據(jù)結(jié)構(gòu),寫(xiě)線程改寫(xiě)這個(gè)結(jié)構(gòu),讀線程讀取該結(jié)構(gòu)。在寫(xiě)線程改寫(xiě)這個(gè)數(shù)據(jù)結(jié)構(gòu)的過(guò)程中,加鎖情況下讀線程由于等待鎖耗時(shí)會(huì)增加。

            可以利用RCU (Read Copy Update What is rcu)的思想來(lái)去除這個(gè)鎖。本文提到的主要實(shí)現(xiàn)代碼:gist

            RCU

            RCU可以說(shuō)是一種替代讀寫(xiě)鎖的方法。其基于一個(gè)事實(shí):當(dāng)寫(xiě)線程在改變一個(gè)指針時(shí),讀線程獲取這個(gè)指針,要么獲取到老的值,要么獲取到新的值。RCU的基本思想其實(shí)很簡(jiǎn)單,參考What is RCU中Toy implementation可以很容易理解。一種簡(jiǎn)單的RCU流程可以描述為:

            寫(xiě)線程:

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

            寫(xiě)線程要更新_ptr指向的內(nèi)容時(shí),先復(fù)制一份新的,基于新的進(jìn)行改變,更新_ptr指針,最后同步釋放老的內(nèi)存。

            讀線程:

            tmp_ptr = _ptr
            use(tmp_ptr)
            dereference(tmp_ptr)
            

            讀線程直接使用_ptr,使用完后需要告訴寫(xiě)線程自己不再使用_ptr。讀線程獲取_ptr時(shí),可能會(huì)獲取到老的也可能獲取到新的,無(wú)論哪種RCU都需要保證這塊內(nèi)存是有效的。重點(diǎn)在synchroizedereferencesynchroize會(huì)等待所有使用老的_ptr的線程dereference,對(duì)于新的_ptr使用者其不需要等待。這個(gè)問(wèn)題說(shuō)白了就是寫(xiě)線程如何知道old_ptr沒(méi)有任何讀線程在使用,可以安全地釋放。

            這個(gè)問(wèn)題實(shí)際上在wait-free的各種實(shí)現(xiàn)中有好些解法,how-when-to-release-memory-in-wait-free-algorithms這里有人總結(jié)了幾種方法,例如Hazard pointersQuiescence period based reclamation

            簡(jiǎn)單地使用引用計(jì)數(shù)智能指針是無(wú)法解決這個(gè)問(wèn)題的,因?yàn)橹悄苤羔樧约翰皇蔷€程安全的,例如:

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

            代碼1/2行不是原子的,所以當(dāng)取得tmp_ptr準(zhǔn)備addRef時(shí),tmp_ptr可能剛好被釋放了。

            Quiescence period based reclamation方法指的是讀線程需要聲明自己處于Quiescence period,也就是不使用_ptr的時(shí)候,當(dāng)其使用_ptr的時(shí)候?qū)嶋H是進(jìn)入了一個(gè)邏輯上的臨界區(qū),當(dāng)所有讀線程都不再使用_ptr的時(shí)候,寫(xiě)線程就可以對(duì)內(nèi)存進(jìn)行安全地釋放。

            本文正是描述了一種Quiescence period based reclamation實(shí)現(xiàn)。這個(gè)實(shí)現(xiàn)可以用于有一個(gè)寫(xiě)線程和多個(gè)讀線程共用若干個(gè)數(shù)據(jù)的場(chǎng)景。

            實(shí)現(xiàn)

            該方法本質(zhì)上把數(shù)據(jù)同步分解為基本的內(nèi)存單元讀寫(xiě)。使用方式上可描述為:

            讀線程:

            tmp_ptr = _ptr
            use
            update() // 標(biāo)識(shí)自己不再使用任何共享數(shù)據(jù)
            

            寫(xiě)線程:

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

            以下具體描述讀寫(xiě)線程的實(shí)現(xiàn)。

            寫(xiě)線程

            寫(xiě)線程負(fù)責(zé)標(biāo)識(shí)內(nèi)存需要被釋放,以及檢查何時(shí)可以真正釋放內(nèi)存。其維護(hù)了一個(gè)釋放內(nèi)存隊(duì)列:

            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找到一個(gè)可釋放內(nèi)存位置,在[_tail, find_free_pos())這個(gè)區(qū)間內(nèi)所有內(nèi)存是可以安全被釋放的。

            隊(duì)列位置_head/_tail一直增大,PENDING_POS就是對(duì)這個(gè)位置取模,限定在隊(duì)列大小范圍內(nèi)也是可行的,無(wú)論哪種方式,_head從邏輯上說(shuō)一直>=_tail,但在實(shí)際中可能小于_tail,所以實(shí)現(xiàn)時(shí)不使用大小判定,而是:

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

            讀線程

            讀線程不再使用共享內(nèi)存時(shí),就標(biāo)識(shí)自己:

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

            讀線程的狀態(tài)會(huì)影響寫(xiě)線程的回收邏輯,其狀態(tài)分為:

            • 初始
            • 活躍,會(huì)調(diào)用到update
            • 暫停,其他地方同步,或被掛起
            • 退出

            讀線程處于活躍狀態(tài)時(shí),它會(huì)不斷地更新自己可釋放內(nèi)存位置(_tmark[tid])。寫(xiě)線程檢查所有讀線程的_tmark[tid][_tail, min(_tmark[]))是所有讀線程都不再使用的內(nèi)存區(qū)間,可以被安全釋放。

            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
                }

            當(dāng)讀線程暫停時(shí),其_tmark[tid]可能會(huì)在很長(zhǎng)一段時(shí)間里得不到更新,此時(shí)會(huì)阻礙寫(xiě)線程釋放內(nèi)存。所以需要方法來(lái)標(biāo)識(shí)讀線程是否進(jìn)入暫停狀態(tài)。通過(guò)設(shè)置一個(gè)上次釋放內(nèi)存位置_tfreeds[tid],標(biāo)識(shí)每個(gè)線程當(dāng)前內(nèi)存釋放到的位置。如果一個(gè)線程處于暫停狀態(tài)了,那么在一定時(shí)間后,_tfreeds[tid] == _tmark[tid]。在查找可釋放位置時(shí),就需要忽略暫停狀態(tài)的讀線程:

            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
                }

            但是當(dāng)所有線程都處于暫停狀態(tài)時(shí),寫(xiě)線程可能還在工作,上面的實(shí)現(xiàn)就會(huì)返回_head,此時(shí)寫(xiě)線程依然可以正常釋放內(nèi)存。

            小結(jié),該方法原理可用下圖表示:

            線程動(dòng)態(tài)增加/減少

            如果讀線程可能中途退出,中途動(dòng)態(tài)增加,那么_tmark[]就需要被復(fù)用,此時(shí)線程tid的分配調(diào)整為動(dòng)態(tài)的即可:

            class ThreadIdPool {
                public:
                    // 動(dòng)態(tài)獲取一個(gè)線程tid,某線程每次調(diào)用該接口返回相同的值
                    int get()
                    // 線程退出時(shí)回收該tid
                    void put(int id)
                }

            ThreadIdPool的實(shí)現(xiàn)無(wú)非就是利用TLS,以及在線程退出時(shí)得到通知以回收tid。那么對(duì)于讀線程的update實(shí)現(xiàn)變?yōu)椋?/p>

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

            當(dāng)某個(gè)線程退出時(shí),_tmark[tid]_tfreeds[tid]不需要做任何處理,當(dāng)新創(chuàng)建的線程復(fù)用了該tid時(shí),可以立即復(fù)用_tmark[tid]_tfreeds[tid],此時(shí)這2個(gè)值必然是相等的。

            以上,就是整個(gè)方法的實(shí)現(xiàn)。

            線程可讀可寫(xiě)

            以上方法適用場(chǎng)景還是不夠通用。在nbds項(xiàng)目(實(shí)現(xiàn)了一些無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的toy project)中有一份雖然簡(jiǎn)單但也有啟發(fā)的實(shí)現(xiàn)(rcu.c)。該實(shí)現(xiàn)支持任意線程defer_free,所有線程updateupdate除了聲明不再使用任何共享內(nèi)存外,還可能回收內(nèi)存。任意線程都可能維護(hù)一些待釋放的內(nèi)存,任意一塊內(nèi)存可能被任意其他線程使用。那么它是如何內(nèi)存回收的?

            本文描述的方法是所有讀線程自己聲明自己,然后由寫(xiě)線程主動(dòng)來(lái)檢查。不同于此方法, nbds的實(shí)現(xiàn),基于一種通知擴(kuò)散的方式。該方式以這樣一種方式工作:

            當(dāng)某個(gè)線程嘗試內(nèi)存回收時(shí),它需要知道所有其他線程的空閑位置(相當(dāng)于_tmark[tid]),它通知下一個(gè)線程我需要釋放的范圍。當(dāng)下一個(gè)線程update時(shí)(離開(kāi)臨界區(qū)),它會(huì)將上個(gè)線程的通知繼續(xù)告訴下一個(gè)線程,直到最后這個(gè)通知回到發(fā)起線程。那么對(duì)于發(fā)起線程而言,這個(gè)釋放請(qǐng)求在所有線程中走了一遍,得到了大家的認(rèn)可,可以安全釋放。每個(gè)線程都以這樣的方式工作。

            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]; // 其它線程發(fā)給自己的通知
                        rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x; // 擴(kuò)散出去
                        ...
                    }
                    ...
                    while (q->tail != rcu_[tid_][tid_]) {
                        free
                    }     
                    ...
                }

            這個(gè)實(shí)現(xiàn)相對(duì)簡(jiǎn)單,不支持線程暫停,以及線程動(dòng)態(tài)增加和減少。

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

            2015年4月6日 #

            記一次tcmalloc分配內(nèi)存引起的coredump

            現(xiàn)象

            線上的服務(wù)出現(xiàn)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
            ...
            

            查看了應(yīng)用層相關(guān)數(shù)據(jù)結(jié)構(gòu),基本數(shù)據(jù)都是沒(méi)有問(wèn)題的。所以最初懷疑是tcmalloc內(nèi)部維護(hù)了錯(cuò)誤的內(nèi)存,在分配內(nèi)存時(shí)出錯(cuò),這個(gè)堆棧只是問(wèn)題的表象。幾天后,線上的另一個(gè)服務(wù),基于同樣的庫(kù),也core了,堆棧還是一樣的。

            最初定位問(wèn)題都是從最近更新的東西入手,包括依賴(lài)的server環(huán)境,但都沒(méi)有明顯的問(wèn)題,所以最后只能從core的直接原因入手。

            分析GetStackTrace

            確認(rèn)core的詳細(xì)位置:

            # 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]處讀取內(nèi)容,然后出錯(cuò),這個(gè)內(nèi)存單元不可讀。但是具體這個(gè)指令在代碼中是什么意思,需要將這個(gè)指令對(duì)應(yīng)到代碼中。獲取tcmalloc的源碼,發(fā)現(xiàn)GetStackTrace根據(jù)編譯選項(xiàng)有很多實(shí)現(xiàn),所以這里選擇最可能的實(shí)現(xiàn),然后對(duì)比匯編以確認(rèn)代碼是否匹配。最初選擇的是stacktrace_x86-64-inl.h,后來(lái)發(fā)現(xiàn)完全不匹配,又選擇了stacktrace_x86-inl.h。這個(gè)實(shí)現(xiàn)版本里也有對(duì)64位平臺(tái)的支持。

            stacktrace_x86-inl.h里使用了一些宏來(lái)生成函數(shù)名和參數(shù),精簡(jiǎn)后代碼大概為:

            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是一個(gè)模板函數(shù),包含一大堆代碼,精簡(jiǎn)后非常簡(jiǎn)單:

            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;
                }

            上面這個(gè)代碼到匯編的對(duì)比過(guò)程還是花了些時(shí)間,其中匯編中出現(xiàn)的一些常量可以大大縮短對(duì)比時(shí)間,例如上面出現(xiàn)了100000,匯編中就有:

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

            注意NextStackFrame中的 if (STRICT_UNWINDING)使用的是模板參數(shù),這導(dǎo)致生成的代碼中根本沒(méi)有else部分,也就沒(méi)有1000000這個(gè)常量

            在對(duì)比代碼的過(guò)程中,可以知道關(guān)鍵的幾個(gè)寄存器、內(nèi)存位置對(duì)應(yīng)到代碼中的變量,從而可以還原core時(shí)的現(xiàn)場(chǎng)環(huán)境。分析過(guò)程中不一定要從第一行匯編讀,可以從較明顯的位置讀,從而還原整個(gè)代碼,函數(shù)返回指令、跳轉(zhuǎn)指令、比較指令、讀內(nèi)存指令、參數(shù)寄存器等都是比較明顯對(duì)應(yīng)的地方。

            另外注意GetStackTraceRecordGrowth中調(diào)用,傳入了3個(gè)參數(shù):

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

            以下是我分析的簡(jiǎn)單注解:

            (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    # 關(guān)鍵位置:*(sp+1) -> r9, rax 對(duì)應(yīng) 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,這里已經(jīng)是NextStackFrame的代碼
            0x000000000045d151 <_Z13GetStackTracePPvii+33>: cmp    %rcx,%rax        # new_sp <= old_sp ? 
            0x000000000045d154 <_Z13GetStackTracePPvii+36>: jb     0x45d170 <_Z13GetStackTracePPvii+64>  # new_sp > old_sp 跳轉(zhuǎn)
            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 存儲(chǔ)了返回值,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)# 關(guān)鍵位置:result[n] = *(sp+1)
            0x000000000045d191 <_Z13GetStackTracePPvii+97>: jmp    0x45d15f <_Z13GetStackTracePPvii+47>
            

            分析過(guò)程比較耗時(shí),同時(shí)還可以分析下GetStackTrace函數(shù)的實(shí)現(xiàn)原理,其實(shí)就是利用RBP寄存器不斷回溯,從而得到整個(gè)調(diào)用堆棧各個(gè)函數(shù)的地址(嚴(yán)格來(lái)說(shuō)是返回地址)。簡(jiǎn)單示意下函數(shù)調(diào)用中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
            

            總之,一般情況下,任何一個(gè)函數(shù)中,RBP寄存器指向了當(dāng)前函數(shù)的棧基址,該棧基址中又存儲(chǔ)了調(diào)用者的棧基址,同時(shí)該棧基址前面還存儲(chǔ)了調(diào)用者的返回地址。所以,GetStackTrace的實(shí)現(xiàn),簡(jiǎn)單來(lái)說(shuō)大概就是:

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

            以上,最終就知道了以下關(guān)鍵信息:

            • r8 對(duì)應(yīng)變量 n,表示當(dāng)前取到第幾個(gè)棧幀了
            • rax 對(duì)應(yīng)變量 sp,代碼core在 *(sp+1)
            • rdi 對(duì)應(yīng)變量 result,用于存儲(chǔ)取得的各個(gè)地址

            然后可以看看現(xiàn)場(chǎng)是怎樣的:

            (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
            

            小結(jié):

            GetStackTrace在取調(diào)用__conhash_get_rbnode的函數(shù)時(shí)出錯(cuò),取得了5個(gè)函數(shù)地址。當(dāng)前使用的RBP為0x4e73aa58

            錯(cuò)誤的RBP

            RBP也是從堆棧中取出來(lái)的,既然這個(gè)地址有問(wèn)題,首先想到的就是有代碼局部變量/數(shù)組寫(xiě)越界。例如sprintf的使用。而且,一般寫(xiě)越界破壞堆棧,都可能是把調(diào)用者的堆棧破壞了,例如:

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

            因?yàn)閷?xiě)入都是從低地址往高地址寫(xiě),而調(diào)用者的堆棧在高地址。當(dāng)然,也會(huì)遇到寫(xiě)壞調(diào)用者的調(diào)用者的堆棧,也就是跨棧幀越界寫(xiě),例如以前遇到的:

            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
            

            所以這里就會(huì)懷疑是tcmalloc這個(gè)函數(shù)里有把堆棧破壞,這個(gè)時(shí)候就是讀代碼,看看有沒(méi)有疑似危險(xiǎn)的地方,未果。這里就陷入了僵局,懷疑又遇到了跨棧幀破壞的情況,這個(gè)時(shí)候就只能__conhash_get_rbnode調(diào)用棧中周?chē)暮瘮?shù)翻翻,例如調(diào)用__conhash_get_rbnode的函數(shù)__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);
                        ...

            這段代碼最終發(fā)現(xiàn)是沒(méi)有問(wèn)題的,這里又耗費(fèi)了不少時(shí)間。后來(lái)發(fā)現(xiàn)若干個(gè)函數(shù)里的RBP都有點(diǎn)奇怪,這個(gè)調(diào)用棧比較正常的范圍是:0x4e738c90

            (gdb) f 8
            #8  0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
            (gdb) p/x $rbp
            $6 = 0x4e73aa58     # 這個(gè)還不算特別可疑
            (gdb) f 9
            #9  0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
            (gdb) p/x $rbp
            $7 = 0x4e738c60     # 這個(gè)也不算特別可疑
            (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
            

            為什么很多函數(shù)中RBP都看起來(lái)不正常? 想了想真要是代碼里把堆棧破壞了,這錯(cuò)誤得發(fā)生得多巧妙?

            錯(cuò)誤RBP的來(lái)源

            然后轉(zhuǎn)機(jī)來(lái)了,腦海中突然閃出-fomit-frame-pointer。編譯器生成的代碼中是可以不需要棧基址指針的,也就是RBP寄存器不作為棧基址寄存器。大部分函數(shù)或者說(shuō)開(kāi)啟了frame-pointer的函數(shù),其函數(shù)頭都會(huì)有以下指令:

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

            表示保存調(diào)用者的棧基址到棧中,以及設(shè)置自己的棧基址。看下__conhash系列函數(shù);

            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)
            ...
            

            這個(gè)庫(kù)是單獨(dú)編譯的,沒(méi)有顯示指定-fno-omit-frame-pointer,查閱gcc手冊(cè),o2優(yōu)化是開(kāi)啟了omit-frame-pinter 的。

            在沒(méi)有RBP的情況下,tcmalloc的GetStackTrace嘗試讀RBP取獲取調(diào)用返回地址,自然是有問(wèn)題的。但是,如果整個(gè)調(diào)用棧中的函數(shù),要么有RBP,要么沒(méi)有RBP,那么GetStackTrace取出的結(jié)果最多就是跳過(guò)一些棧幀,不會(huì)出錯(cuò)。 除非,這中間的某個(gè)函數(shù)把RBP寄存器另作他用(編譯器省出這個(gè)寄存器肯定是要另作他用的)。所以這里繼續(xù)追查這個(gè)錯(cuò)誤地址0x4e73aa58的來(lái)源。

            來(lái)源已經(jīng)比較明顯,肯定是__conhash_get_rbnode中設(shè)置的,因?yàn)檫@個(gè)函數(shù)的RBP是在被調(diào)用者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                    # 改寫(xiě)了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>  # 調(diào)用tcmalloc,匯編到這里即可
            

            這里打印RSI寄存器的值可能會(huì)被誤導(dǎo),因?yàn)槿魏螘r(shí)候打印寄存器的值可能都是錯(cuò)的,除非它有被顯示保存。不過(guò)這里可以看出RSI的值來(lái)源于參數(shù)(RSI對(duì)應(yīng)第二個(gè)參數(shù)):

            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值由一個(gè)字符串哈希函數(shù)計(jì)算
                    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    # 來(lái)源于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的來(lái)源。這個(gè)地址值竟然是一個(gè)字符串哈希算法算出來(lái)的!這里還可以看看這個(gè)字符串的內(nèi)容:

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

            這個(gè)碉堡的哈希函數(shù)是conhash_hash_def

            coredump的條件

            以上,既然只要某個(gè)庫(kù)omit-frame-pointer,那tcmalloc就可能出錯(cuò),為什么發(fā)生的頻率并不高呢?這個(gè)可以回到GetStackTrace尤其是NextStackFrame的實(shí)現(xiàn),其中包含了幾個(gè)合法RBP的判定:

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

            有了以上條件,才使得這個(gè)core幾率變得很低。

            總結(jié)

            最后,如果你很熟悉tcmalloc,整個(gè)問(wèn)題估計(jì)就被秒解了:tcmalloc INSTALL

            另外附上另一個(gè)有意思的東西。

            在分析__conhash_add_replicas時(shí),其內(nèi)定義了一個(gè)64字節(jié)的字符數(shù)組,查看其堆棧:

            (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>
            

            最開(kāi)始我覺(jué)得buf占64字節(jié),也就是整個(gè)[0x4e738bd0, 0x4e738c10)內(nèi)存,但是這塊內(nèi)存里居然有函數(shù)地址,這一度使我懷疑這里有問(wèn)題。后來(lái)醒悟這些地址是定義buf前調(diào)用__conhash_create_node產(chǎn)生的,調(diào)用過(guò)程中寫(xiě)到堆棧里,調(diào)用完后棧指針改變,但并不需要清空棧中的內(nèi)容。

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

            2014年12月3日 #

            基于內(nèi)存查看STL常用容器內(nèi)容

            有時(shí)候在線上使用gdb調(diào)試程序core問(wèn)題時(shí),可能沒(méi)有符號(hào)文件,拿到的僅是一個(gè)內(nèi)存地址,如果這個(gè)指向的是一個(gè)STL對(duì)象,那么如何查看這個(gè)對(duì)象的內(nèi)容呢?

            只需要知道STL各個(gè)容器的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),就可以查看其內(nèi)容。本文描述了SGI STL實(shí)現(xiàn)中常用容器的數(shù)據(jù)結(jié)構(gòu),以及如何在gdb中查看其內(nèi)容。

            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內(nèi)有一個(gè)指針,指向?qū)嶋H的字符串位置,這個(gè)位置前面有一個(gè)_Rep結(jié)構(gòu),其內(nèi)保存了字符串的長(zhǎng)度、可用內(nèi)存以及引用計(jì)數(shù)。當(dāng)我們拿到一個(gè)string對(duì)象的地址時(shí),可以通過(guò)以下代碼獲取相關(guān)值:

            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中拿到一個(gè)string的地址時(shí),可以以下打印出該字符串及長(zhǎng)度:

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

            vector

            眾所周知vector實(shí)現(xiàn)就是一塊連續(xù)的內(nèi)存,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,其內(nèi)也就是3個(gè)指針,_M_start指向首元素地址,_M_finish指向最后一個(gè)節(jié)點(diǎn)+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()); }

            可以通過(guò)代碼從一個(gè)vector對(duì)象地址輸出其信息:

            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輸出一個(gè)vector中的內(nèi)容:

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

            list

            眾所周知list被實(shí)現(xiàn)為一個(gè)鏈表。準(zhǔn)確來(lái)說(shuō)是一個(gè)雙向鏈表。list本身是一個(gè)特殊節(jié)點(diǎn),其代表end,其指向的下一個(gè)元素才是list真正的第一個(gè)節(jié)點(diǎn):

            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,兩個(gè)指針。每一個(gè)真正的節(jié)點(diǎn)首先是包含兩個(gè)指針,然后是元素內(nèi)容(_List_node)。

            通過(guò)代碼輸出list的內(nèi)容:

            #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使用的是紅黑樹(shù)實(shí)現(xiàn),實(shí)際使用的是stl_tree.h實(shí)現(xiàn):

            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));
                  }

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

            _Rb_tree_color  _M_color; // 節(jié)點(diǎn)顏色
                    _Base_ptr       _M_parent; // 父節(jié)點(diǎn)
                    _Base_ptr       _M_left; // 左節(jié)點(diǎn)
                    _Base_ptr       _M_right; // 右節(jié)點(diǎn)
                    _Val            _M_value_field // 同list中節(jié)點(diǎn)技巧一致,后面是實(shí)際的元素

            同list中的實(shí)現(xiàn)一致,map本身作為一個(gè)節(jié)點(diǎn),其不是一個(gè)存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn),

            _Rb_tree::end

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

            由于節(jié)點(diǎn)值在_Rb_tree_node_base后,所以任意時(shí)候拿到節(jié)點(diǎn)就可以偏移這個(gè)結(jié)構(gòu)體拿到節(jié)點(diǎn)值,節(jié)點(diǎn)的值是一個(gè)pair,包含了key和value。

            在gdb中打印以下map的內(nèi)容:

            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 真正的節(jié)點(diǎn)
            0x7fffffffe388: 0x606040          
            (gdb) x/1xw 0x606040+32+8        # 偏移32字節(jié)是節(jié)點(diǎn)值的地址,再偏移8則是value的地址
            0x606068:       0x00000bbb
            (gdb) p *(char**)(0x606040+32)   # 偏移32字節(jié)是string的地址
            $8 = 0x606028 "abc"
            

            或者很多時(shí)候沒(méi)有必要這么裝逼+蛋疼:

            (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 閱讀(3849) | 評(píng)論 (2)編輯 收藏

            2014年11月4日 #

            linux動(dòng)態(tài)庫(kù)的種種要點(diǎn)

            linux下使用動(dòng)態(tài)庫(kù),基本用起來(lái)還是很容易。但如果我們的程序中大量使用動(dòng)態(tài)庫(kù)來(lái)實(shí)現(xiàn)各種框架/插件,那么就會(huì)遇到一些坑,掌握這些坑才有利于程序更穩(wěn)健地運(yùn)行。

            本篇先談?wù)剟?dòng)態(tài)庫(kù)符號(hào)方面的問(wèn)題。

            測(cè)試代碼可以在github上找到

            符號(hào)查找

            一個(gè)應(yīng)用程序test會(huì)鏈接一個(gè)動(dòng)態(tài)庫(kù)libdy.so,如果一個(gè)符號(hào),例如函數(shù)callfn定義于libdy.so中,test要使用該函數(shù),簡(jiǎn)單地聲明即可:

            // dy.cpp libdy.so
            void callfn() {
                ...
            }
            
            // main.cpp test
            extern void callfn();
            
            callfn();

            在鏈接test的時(shí)候,鏈接器會(huì)統(tǒng)一進(jìn)行檢查。

            同樣,在libdy.so中有相同的規(guī)則,它可以使用一個(gè)外部的符號(hào),在它被鏈接/載入進(jìn)一個(gè)可執(zhí)行程序時(shí)才會(huì)進(jìn)行符號(hào)存在與否的檢查。這個(gè)符號(hào)甚至可以定義在test中,形成一種雙向依賴(lài),或定義在其他動(dòng)態(tài)庫(kù)中:

            // dy.cpp libdy.so
            extern void mfunc();
            
            mfunc();
            
            // main.cpp test
            void mfunc() {
                ...
            }

            在生成libdy.so時(shí)mfunc可以找不到,此時(shí)mfunc為未定義:

            $ nm libdy.so | grep mfun
            U _Z5mfuncv
            

            但在libdy.so被鏈接進(jìn)test時(shí)則會(huì)進(jìn)行檢查,試著把mfunc函數(shù)的定義去掉,就會(huì)得到一個(gè)鏈接錯(cuò)誤:

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

            同樣,如果我們動(dòng)態(tài)載入libdy.so,此時(shí)當(dāng)然可以鏈接通過(guò),但是在載入時(shí)同樣得到找不到符號(hào)的錯(cuò)誤:

            #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

            得到錯(cuò)誤:

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

            結(jié)論:基于以上,我們知道,如果一個(gè)動(dòng)態(tài)庫(kù)依賴(lài)了一些外部符號(hào),這些外部符號(hào)可以位于其他動(dòng)態(tài)庫(kù)甚至應(yīng)用程序中。我們可以再鏈接這個(gè)動(dòng)態(tài)庫(kù)的時(shí)候就把依賴(lài)的其他庫(kù)也鏈接上,或者推遲到鏈接應(yīng)用程序時(shí)再鏈接。而動(dòng)態(tài)加載的庫(kù),則要保證在加載該庫(kù)時(shí),進(jìn)程中加載的其他動(dòng)態(tài)庫(kù)里已經(jīng)存在該符號(hào)。

            例如,通過(guò)LD_PRELOAD環(huán)境變量可以讓一個(gè)進(jìn)程先加載指定的動(dòng)態(tài)庫(kù),上面那個(gè)動(dòng)態(tài)加載啟動(dòng)失敗的例子,可以通過(guò)預(yù)先加載包含mfunc符號(hào)的動(dòng)態(tài)庫(kù)解決:

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

            但是如果這個(gè)符號(hào)存在于可執(zhí)行程序中則不行:

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

            符號(hào)覆蓋

            前面主要講的是符號(hào)缺少的情況,如果同一個(gè)符號(hào)存在多分,則更能引發(fā)問(wèn)題。這里談到的符號(hào)都是全局符號(hào),一個(gè)進(jìn)程中某個(gè)全局符號(hào)始終是全局唯一的。為了保證這一點(diǎn),在鏈接或動(dòng)態(tài)載入動(dòng)態(tài)庫(kù)時(shí),就會(huì)出現(xiàn)忽略重復(fù)符號(hào)的情況。

            這里就不提同一個(gè)鏈接單位(如可執(zhí)行程序、動(dòng)態(tài)庫(kù))里符號(hào)重復(fù)的問(wèn)題了

            函數(shù)

            當(dāng)動(dòng)態(tài)庫(kù)和libdy.so可執(zhí)行程序test中包含同名的函數(shù)時(shí)會(huì)怎樣?根據(jù)是否動(dòng)態(tài)加載情況還有所不同。

            當(dāng)直接鏈接動(dòng)態(tài)庫(kù)時(shí),libdy.so和test都會(huì)鏈接包含func函數(shù)的fun.o,為了區(qū)分,我把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就會(huì)輸出func v1;libdy.so中的func就會(huì)輸出func v2。test和libdy.o確實(shí)都有func符號(hào):

            $ nm libdy.so | grep func
            0000000000000a60 T func
            
            $nm test | grep func
            0000000000400a80 T func
            

            在test和libdy.so中都會(huì)調(diào)用func函數(shù):

            // main.cpp test
            int main(int argc, char **argv) {
                func();
                ...
                callfn(); // 調(diào)用libdy.so中的函數(shù)
                ...
            }
            
            // dy.cpp libdy.so
            extern "C" void callfn() {
                ... 
                printf("callfn\n");
                func();
                ...
            }

            運(yùn)行后發(fā)現(xiàn),都調(diào)用的是同一個(gè)func

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

            結(jié)論,直接鏈接動(dòng)態(tài)庫(kù)時(shí),整個(gè)程序運(yùn)行的時(shí)候符號(hào)會(huì)發(fā)生覆蓋,只有一個(gè)符號(hào)被使用。在實(shí)踐中,如果程序和鏈接的動(dòng)態(tài)庫(kù)都依賴(lài)了一個(gè)靜態(tài)庫(kù),而后他們鏈接的這個(gè)靜態(tài)庫(kù)版本不同,則很有可能因?yàn)榉?hào)發(fā)生了覆蓋而導(dǎo)致問(wèn)題。(靜態(tài)庫(kù)同普通的.o性質(zhì)一樣,參考淺析靜態(tài)庫(kù)鏈接原理)

            更復(fù)雜的情況中,多個(gè)動(dòng)態(tài)庫(kù)和程序都有相同的符號(hào),情況也是一樣,會(huì)發(fā)生符號(hào)覆蓋。如果程序里沒(méi)有這個(gè)符號(hào),而多個(gè)動(dòng)態(tài)庫(kù)里有相同的符號(hào),也會(huì)覆蓋。

            但是對(duì)于動(dòng)態(tài)載入的情況則不同,同樣的libdy.so我們?cè)趖est中不鏈接,而是動(dòng)態(tài)載入:

            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;
            }

            運(yùn)行得到:

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

            都正確地調(diào)用到各自鏈接的func

            結(jié)論,實(shí)踐中,動(dòng)態(tài)載入的動(dòng)態(tài)庫(kù)一般會(huì)作為插件使用,那么其同程序鏈接不同版本的靜態(tài)庫(kù)(相同符號(hào)不同實(shí)現(xiàn)),是沒(méi)有問(wèn)題的。

            變量

            變量本質(zhì)上也是符號(hào)(symbol),但其處理規(guī)則和函數(shù)還有點(diǎn)不一樣(是不是有點(diǎn)想吐槽了)。

            // 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和動(dòng)態(tài)庫(kù)libdy.so都會(huì)鏈接object.o。首先測(cè)試test鏈接libdy.so,test和libdy.so中都會(huì)有g_obj這個(gè)符號(hào):

            // 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
            

            運(yùn)行:

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

            g_obj被構(gòu)造了兩次,但地址一樣。全局變量只有一個(gè)實(shí)例,似乎在情理之中。

            動(dòng)態(tài)載入libdy.so,變量地址還是相同的:

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

            結(jié)論,不同于函數(shù),全局變量符號(hào)重復(fù)時(shí),不論動(dòng)態(tài)庫(kù)是動(dòng)態(tài)載入還是直接鏈接,變量始終只有一個(gè)。

            但詭異的情況是,對(duì)象被構(gòu)造和析構(gòu)了兩次。構(gòu)造兩次倒無(wú)所謂,浪費(fèi)點(diǎn)空間,但是析構(gòu)兩次就有問(wèn)題。因?yàn)槲鰳?gòu)時(shí)都操作的是同一個(gè)對(duì)象,那么如果這個(gè)對(duì)象內(nèi)部有分配的內(nèi)存,那就會(huì)對(duì)這塊內(nèi)存造成double free,因?yàn)橹羔樝嗤4蜷_(kāi)DF宏實(shí)驗(yàn)下:

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

            因?yàn)槲鰳?gòu)的兩次都是同一個(gè)對(duì)象,所以其成員s指向的內(nèi)存被釋放了兩次,從而產(chǎn)生了double free,讓程序coredump了。

            總結(jié),全局變量符號(hào)重復(fù)時(shí),始終會(huì)只使用一個(gè),并且會(huì)被初始化/釋放兩次,是一種較危險(xiǎn)的情況,應(yīng)當(dāng)避免在使用動(dòng)態(tài)庫(kù)的過(guò)程中使用全局變量。

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

            2014年10月19日 #

            圖解zookeeper FastLeader選舉算法

            zookeeper配置為集群模式時(shí),在啟動(dòng)或異常情況時(shí)會(huì)選舉出一個(gè)實(shí)例作為L(zhǎng)eader。其默認(rèn)選舉算法為FastLeaderElection

            不知道zookeeper的可以考慮這樣一個(gè)問(wèn)題:某個(gè)服務(wù)可以配置為多個(gè)實(shí)例共同構(gòu)成一個(gè)集群對(duì)外提供服務(wù)。其每一個(gè)實(shí)例本地都存有冗余數(shù)據(jù),每一個(gè)實(shí)例都可以直接對(duì)外提供讀寫(xiě)服務(wù)。在這個(gè)集群中為了保證數(shù)據(jù)的一致性,需要有一個(gè)Leader來(lái)協(xié)調(diào)一些事務(wù)。那么問(wèn)題來(lái)了:如何確定哪一個(gè)實(shí)例是Leader呢?

            問(wèn)題的難點(diǎn)在于:

            • 沒(méi)有一個(gè)仲裁者來(lái)選定Leader
            • 每一個(gè)實(shí)例本地可能已經(jīng)存在數(shù)據(jù),不確定哪個(gè)實(shí)例上的數(shù)據(jù)是最新的

            分布式選舉算法正是用來(lái)解決這個(gè)問(wèn)題的。

            本文基于zookeeper 3.4.6 的源碼進(jìn)行分析。FastLeaderElection算法的源碼全部位于FastLeaderElection.java文件中,其對(duì)外接口為FastLeaderElection.lookForLeader,該接口是一個(gè)同步接口,直到選舉結(jié)束才會(huì)返回。同樣由于網(wǎng)上已有類(lèi)似文章,所以我就從圖示的角度來(lái)闡述。閱讀一些其他文章有利于獲得初步印象:

            主要流程

            閱讀代碼和以上推薦文章可以把整個(gè)流程梳理清楚。實(shí)現(xiàn)上,包括了一個(gè)消息處理主循環(huán),也是選舉的主要邏輯,以及一個(gè)消息發(fā)送隊(duì)列處理線程和消息解碼線程。主要流程可概括為下圖:

            fle-flow.png

            推薦對(duì)照著推薦的文章及代碼理解,不贅述。

            我們從感性上來(lái)理解這個(gè)算法。

            每一個(gè)節(jié)點(diǎn),相當(dāng)于一個(gè)選民,他們都有自己的推薦人,最開(kāi)始他們都推薦自己。誰(shuí)更適合成為L(zhǎng)eader有一個(gè)簡(jiǎn)單的規(guī)則,例如sid夠大(配置)、持有的數(shù)據(jù)夠新(zxid夠大)。每個(gè)選民都告訴其他選民自己目前的推薦人是誰(shuí),類(lèi)似于出去搞宣傳拉攏其他選民。每一個(gè)選民發(fā)現(xiàn)有比自己更適合的人時(shí)就轉(zhuǎn)而推薦這個(gè)更適合的人。最后,大部分人意見(jiàn)一致時(shí),就可以結(jié)束選舉。

            就這么簡(jiǎn)單。總體上有一種不斷演化逼近結(jié)果的感覺(jué)。

            當(dāng)然,會(huì)有些特殊情況的處理。例如總共3個(gè)選民,1和2已經(jīng)確定3是Leader,但3還不知情,此時(shí)就走入LEADING/FOLLOWING的分支,選民3只是接收結(jié)果。

            代碼中不是所有邏輯都在這個(gè)大流程中完成的。在接收消息線程中,還可能單獨(dú)地回應(yīng)某個(gè)節(jié)點(diǎn)(WorkerReceiver.run):

            recv.png

            從這里可以看出,當(dāng)某個(gè)節(jié)點(diǎn)已經(jīng)確定選舉結(jié)果不再處于LOOKING狀態(tài)時(shí),其收到LOOKING消息時(shí)都會(huì)直接回應(yīng)選舉的最終結(jié)果。結(jié)合上面那個(gè)比方,相當(dāng)于某次選舉結(jié)束了,這個(gè)時(shí)候來(lái)了選民4又發(fā)起一次新的選舉,那么其他選民就直接告訴它當(dāng)前的Leader情況。相當(dāng)于,在這個(gè)集群主從已經(jīng)就緒的情況下,又開(kāi)啟了一個(gè)實(shí)例,這個(gè)實(shí)例就會(huì)直接使用當(dāng)前的選舉結(jié)果。

            狀態(tài)轉(zhuǎn)換

            每個(gè)節(jié)點(diǎn)上有一些關(guān)鍵的數(shù)據(jù)結(jié)構(gòu):

            • 當(dāng)前推薦人,初始推薦自己,每次收到其他更好的推薦人時(shí)就更新
            • 其他人的投票集合,用于確定何時(shí)選舉結(jié)束

            每次推薦人更新時(shí)就會(huì)進(jìn)行廣播,正是這個(gè)不斷地廣播驅(qū)動(dòng)整個(gè)算法趨向于結(jié)果。假設(shè)有3個(gè)節(jié)點(diǎn)A/B/C,其都還沒(méi)有數(shù)據(jù),按照sid關(guān)系為C>B>A,那么按照規(guī)則,C更可能成為L(zhǎng)eader,其各個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換為:

            state.png

            圖中,v(A)表示當(dāng)前推薦人為A;r[]表示收到的投票集合。

            可以看看當(dāng)其他節(jié)點(diǎn)已經(jīng)確定投票結(jié)果時(shí),即不再是LOOKING時(shí)的狀態(tài):

            state-ret.png

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

            當(dāng)一個(gè)新啟動(dòng)的節(jié)點(diǎn)加入集群時(shí),它對(duì)集群內(nèi)其他節(jié)點(diǎn)發(fā)出投票請(qǐng)求,而其他節(jié)點(diǎn)已不處于LOOKING狀態(tài),此時(shí)其他節(jié)點(diǎn)回應(yīng)選舉結(jié)果,該節(jié)點(diǎn)收集這些結(jié)果到outofelection中,最終在收到合法LEADER消息且這些選票也構(gòu)成選舉結(jié)束條件時(shí),該節(jié)點(diǎn)就結(jié)束自己的選舉行為。注意到代碼中會(huì)logicalclock = n.electionEpoch;更新選舉輪數(shù)

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

            2014年10月15日 #

            圖解分布式一致性協(xié)議Paxos

            Paxos協(xié)議/算法是分布式系統(tǒng)中比較重要的協(xié)議,它有多重要呢?

            <分布式系統(tǒng)的事務(wù)處理>

            Google Chubby的作者M(jìn)ike Burrows說(shuō)過(guò)這個(gè)世界上只有一種一致性算法,那就是Paxos,其它的算法都是殘次品。

            <大規(guī)模分布式存儲(chǔ)系統(tǒng)>

            理解了這兩個(gè)分布式協(xié)議之后(Paxos/2PC),學(xué)習(xí)其他分布式協(xié)議會(huì)變得相當(dāng)容易。

            學(xué)習(xí)Paxos算法有兩部分:a) 算法的原理/證明;b) 算法的理解/運(yùn)作。

            理解這個(gè)算法的運(yùn)作過(guò)程其實(shí)基本就可以用于工程實(shí)踐。而且理解這個(gè)過(guò)程相對(duì)來(lái)說(shuō)也容易得多。

            網(wǎng)上我覺(jué)得講Paxos講的好的屬于這篇:paxos圖解Paxos算法詳解,我這里就結(jié)合wiki上的實(shí)例進(jìn)一步闡述。一些paxos基礎(chǔ)通過(guò)這里提到的兩篇文章,以及wiki上的內(nèi)容基本可以理解。

            算法內(nèi)容

            Paxos在原作者的《Paxos Made Simple》中內(nèi)容是比較精簡(jiǎn)的:

            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圖解文中的流程圖可概括為:

            實(shí)例及詳解

            Paxos中有三類(lèi)角色ProposerAcceptorLearner,主要交互過(guò)程在ProposerAcceptor之間。

            ProposerAcceptor之間的交互主要有4類(lèi)消息通信,如下圖:

            這4類(lèi)消息對(duì)應(yīng)于paxos算法的兩個(gè)階段4個(gè)過(guò)程:

            • phase 1
              • a) proposer向網(wǎng)絡(luò)內(nèi)超過(guò)半數(shù)的acceptor發(fā)送prepare消息
              • b) acceptor正常情況下回復(fù)promise消息
            • phase 2
              • a) 在有足夠多acceptor回復(fù)promise消息時(shí),proposer發(fā)送accept消息
              • b) 正常情況下acceptor回復(fù)accepted消息

            因?yàn)樵谡麄€(gè)過(guò)程中可能有其他proposer針對(duì)同一件事情發(fā)出以上請(qǐng)求,所以在每個(gè)過(guò)程中都會(huì)有些特殊情況處理,這也是為了達(dá)成一致性所做的事情。如果在整個(gè)過(guò)程中沒(méi)有其他proposer來(lái)競(jìng)爭(zhēng),那么這個(gè)操作的結(jié)果就是確定無(wú)異議的。但是如果有其他proposer的話,情況就不一樣了。

            paxos中文wiki上的例子為例。簡(jiǎn)單來(lái)說(shuō)該例子以若干個(gè)議員提議稅收,確定最終通過(guò)的法案稅收比例。

            以下圖中基本只畫(huà)出proposer與一個(gè)acceptor的交互。時(shí)間標(biāo)志T2總是在T1后面。propose number簡(jiǎn)稱(chēng)N。

            情況之一如下圖:

            A3在T1發(fā)出accepted給A1,然后在T2收到A5的prepare,在T3的時(shí)候A1才通知A5最終結(jié)果(稅率10%)。這里會(huì)有兩種情況:

            • A5發(fā)來(lái)的N5小于A1發(fā)出去的N1,那么A3直接拒絕(reject)A5
            • A5發(fā)來(lái)的N5大于A1發(fā)出去的N1,那么A3回復(fù)promise,但帶上A1的(N1, 10%)

            這里可以與paxos流程圖對(duì)應(yīng)起來(lái),更好理解。acceptor會(huì)記錄(MaxN, AcceptN, AcceptV)

            A5在收到promise后,后續(xù)的流程可以順利進(jìn)行。但是發(fā)出accept時(shí),因?yàn)槭盏搅?AcceptN, AcceptV),所以會(huì)取最大的AcceptN對(duì)應(yīng)的AcceptV,例子中也就是A1的10%作為AcceptV。如果在收到promise時(shí)沒(méi)有發(fā)現(xiàn)有其他已記錄的AcceptV,則其值可以由自己決定。

            針對(duì)以上A1和A5沖突的情況,最終A1和A5都會(huì)廣播接受的值為10%。

            其實(shí)4個(gè)過(guò)程中對(duì)于acceptor而言,在回復(fù)promise和accepted時(shí)由于都可能因?yàn)槠渌鹥roposer的介入而導(dǎo)致特殊處理。所以基本上看在這兩個(gè)時(shí)間點(diǎn)收到其他proposer的請(qǐng)求時(shí)就可以了解整個(gè)算法了。例如在回復(fù)promise時(shí)則可能因?yàn)閜roposer發(fā)來(lái)的N不夠大而reject:

            如果在發(fā)accepted消息時(shí),對(duì)其他更大N的proposer發(fā)出過(guò)promise,那么也會(huì)reject該proposer發(fā)出的accept,如圖:

            這個(gè)對(duì)應(yīng)于Phase 2 b):

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

            總結(jié)

            Leslie Lamport沒(méi)有用數(shù)學(xué)描述Paxos,但是他用英文闡述得很清晰。將Paxos的兩個(gè)Phase的內(nèi)容理解清楚,整個(gè)算法過(guò)程還是不復(fù)雜的。

            至于Paxos中一直提到的一個(gè)全局唯一且遞增的proposer number,其如何實(shí)現(xiàn),引用如下:

            如何產(chǎn)生唯一的編號(hào)呢?在《Paxos made simple》中提到的是讓所有的Proposer都從不相交的數(shù)據(jù)集合中進(jìn)行選擇,例如系統(tǒng)有5個(gè)Proposer,則可為每一個(gè)Proposer分配一個(gè)標(biāo)識(shí)j(0~4),則每一個(gè)proposer每次提出決議的編號(hào)可以為5*i + j(i可以用來(lái)表示提出議案的次數(shù))

            參考文檔

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

            2014年10月12日 #

            淘寶分布式配置管理服務(wù)Diamond

            在一個(gè)分布式環(huán)境中,同類(lèi)型的服務(wù)往往會(huì)部署很多實(shí)例。這些實(shí)例使用了一些配置,為了更好地維護(hù)這些配置就產(chǎn)生了配置管理服務(wù)。通過(guò)這個(gè)服務(wù)可以輕松地管理這些應(yīng)用服務(wù)的配置問(wèn)題。應(yīng)用場(chǎng)景可概括為:

            zookeeper的一種應(yīng)用就是分布式配置管理(基于ZooKeeper的配置信息存儲(chǔ)方案的設(shè)計(jì)與實(shí)現(xiàn))。百度也有類(lèi)似的實(shí)現(xiàn):disconf

            Diamond則是淘寶開(kāi)源的一種分布式配置管理服務(wù)的實(shí)現(xiàn)。Diamond本質(zhì)上是一個(gè)Java寫(xiě)的Web應(yīng)用,其對(duì)外提供接口都是基于HTTP協(xié)議的,在閱讀代碼時(shí)可以從實(shí)現(xiàn)各個(gè)接口的controller入手。

            分布式配置管理

            分布式配置管理的本質(zhì)基本上就是一種推送-訂閱模式的運(yùn)用。配置的應(yīng)用方是訂閱者,配置管理服務(wù)則是推送方。概括為下圖:

            其中,客戶(hù)端包括管理人員publish數(shù)據(jù)到配置管理服務(wù),可以理解為添加/更新數(shù)據(jù);配置管理服務(wù)notify數(shù)據(jù)到訂閱者,可以理解為推送。

            配置管理服務(wù)往往會(huì)封裝一個(gè)客戶(hù)端庫(kù),應(yīng)用方則是基于該庫(kù)與配置管理服務(wù)進(jìn)行交互。在實(shí)際實(shí)現(xiàn)時(shí),客戶(hù)端庫(kù)可能是主動(dòng)拉取(pull)數(shù)據(jù),但對(duì)于應(yīng)用方而言,一般是一種事件通知方式。

            Diamond中的數(shù)據(jù)是簡(jiǎn)單的key-value結(jié)構(gòu)。應(yīng)用方訂閱數(shù)據(jù)則是基于key來(lái)訂閱,未訂閱的數(shù)據(jù)當(dāng)然不會(huì)被推送。數(shù)據(jù)從類(lèi)型上又劃分為聚合和非聚合。因?yàn)閿?shù)據(jù)推送者可能很多,在整個(gè)分布式環(huán)境中,可能有多個(gè)推送者在推送相同key的數(shù)據(jù),這些數(shù)據(jù)如果是聚合的,那么所有這些推送者推送的數(shù)據(jù)會(huì)被合并在一起;反之如果是非聚合的,則會(huì)出現(xiàn)覆蓋。

            數(shù)據(jù)的來(lái)源可能是人工通過(guò)管理端錄入,也可能是其他服務(wù)通過(guò)配置管理服務(wù)的推送接口自動(dòng)錄入。

            架構(gòu)及實(shí)現(xiàn)

            Diamond服務(wù)是一個(gè)集群,是一個(gè)去除了單點(diǎn)的協(xié)作集群。如圖:

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

            服務(wù)之間同步

            Diamond服務(wù)集群每一個(gè)實(shí)例都可以對(duì)外完整地提供服務(wù),那么意味著每個(gè)實(shí)例上都有整個(gè)集群維護(hù)的數(shù)據(jù)。Diamond有兩種方式保證這一點(diǎn):

            • 任何一個(gè)實(shí)例都有其他實(shí)例的地址;任何一個(gè)實(shí)例上的數(shù)據(jù)變更時(shí),都會(huì)將改變的數(shù)據(jù)同步到mysql上,然后通知其他所有實(shí)例從mysql上進(jìn)行一次數(shù)據(jù)拉取(DumpService::dump),這個(gè)過(guò)程只拉取改變了的數(shù)據(jù)
            • 任何一個(gè)實(shí)例啟動(dòng)后都會(huì)以較長(zhǎng)的時(shí)間間隔(幾小時(shí)),從mysql進(jìn)行一次全量的數(shù)據(jù)拉取(DumpAllProcessor)

            實(shí)現(xiàn)上為了一致性,通知其他實(shí)例實(shí)際上也包含自己。以服務(wù)器收到添加聚合數(shù)據(jù)為例,處理過(guò)程大致為:

            DatumController::addDatum // /datum.do?method=addDatum
                PersistService::addAggrConfigInfo 
                MergeDatumService::addMergeTask // 添加一個(gè)MergeDataTask,異步處理
            
            MergeTaskProcessor::process
                PersistService::insertOrUpdate
                    EventDispatcher.fireEvent(new ConfigDataChangeEvent // 派發(fā)一個(gè)ConfigDataChangeEvent事件
            
            NotifyService::onEvent // 接收事件并處理
                TaskManager::addTask(..., new NotifyTask // 由此,當(dāng)數(shù)據(jù)發(fā)生變動(dòng),則最終創(chuàng)建了一個(gè)NoticyTask
            
            // NotifyTask同樣異步處理
            NotifyTaskProcessor::process
                foreach server in serverList // 包含自己
                    notifyToDump // 調(diào)用 /notify.do?method=notifyConfigInfo 從mysql更新變動(dòng)的數(shù)據(jù)
            

            雖然Diamond去除了單點(diǎn)問(wèn)題,不過(guò)問(wèn)題都下降到了mysql上。但由于其作為配置管理的定位,其數(shù)據(jù)量就mysql的應(yīng)用而言算小的了,所以可以一定程度上保證整個(gè)服務(wù)的可用性。

            數(shù)據(jù)一致性

            由于Diamond服務(wù)器沒(méi)有master,任何一個(gè)實(shí)例都可以讀寫(xiě)數(shù)據(jù),那么針對(duì)同一個(gè)key的數(shù)據(jù)則可能面臨沖突。這里應(yīng)該是通過(guò)mysql來(lái)保證數(shù)據(jù)的一致性。每一次客戶(hù)端請(qǐng)求寫(xiě)數(shù)據(jù)時(shí),Diamond都將寫(xiě)請(qǐng)求投遞給mysql,然后通知集群內(nèi)所有Diamond實(shí)例(包括自己)從mysql拉取數(shù)據(jù)。當(dāng)然,拉取數(shù)據(jù)則可能不是每一次寫(xiě)入都能拉出來(lái),也就是最終一致性。

            Diamond中沒(méi)有把數(shù)據(jù)放入內(nèi)存,但會(huì)放到本地文件。對(duì)于客戶(hù)端的讀操作而言,則是直接返回本地文件里的數(shù)據(jù)。

            服務(wù)實(shí)例列表

            Diamond服務(wù)實(shí)例列表是一份靜態(tài)數(shù)據(jù),直接將每個(gè)實(shí)例的地址存放在一個(gè)web server上。無(wú)論是Diamond服務(wù)還是客戶(hù)端都從該web server上取出實(shí)例列表。

            對(duì)于客戶(hù)端而言,當(dāng)其取出了該列表后,則是隨機(jī)選擇一個(gè)節(jié)點(diǎn)(ServerListManager.java),以后的請(qǐng)求都會(huì)發(fā)往該節(jié)點(diǎn)。

            數(shù)據(jù)同步

            客戶(hù)端庫(kù)中以固定時(shí)間間隔從服務(wù)器拉取數(shù)據(jù)(ClientWorker::ClientWorkerClientWorker::checkServerConfigInfo)。只有應(yīng)用方關(guān)心的數(shù)據(jù)才可能被拉取。另外,為了數(shù)據(jù)推送的及時(shí),Diamond還使用了一種long polling的技術(shù),其實(shí)也是為了突破HTTP協(xié)議的局限性。如果整個(gè)服務(wù)是基于TCP的自定義協(xié)議,客戶(hù)端與服務(wù)器保持長(zhǎng)連接則沒(méi)有這些問(wèn)題

            數(shù)據(jù)的變更

            Diamond中很多操作都會(huì)檢查數(shù)據(jù)是否發(fā)生了變化。標(biāo)識(shí)數(shù)據(jù)變化則是基于數(shù)據(jù)對(duì)應(yīng)的MD5值來(lái)實(shí)現(xiàn)的。

            容災(zāi)

            在整個(gè)Diamond系統(tǒng)中,幾個(gè)角色為了提高容災(zāi)性,都有自己的緩存,概括為下圖:

            每一個(gè)角色出問(wèn)題時(shí),都可以盡量保證客戶(hù)端對(duì)應(yīng)用層提供服務(wù)。

            參考文檔

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

            僅列出標(biāo)題  下一頁(yè)
            久久久久一区二区三区| 亚洲一区二区三区日本久久九| 欧美777精品久久久久网| 久久精品中文字幕久久| 99久久国产主播综合精品| 欧美久久天天综合香蕉伊| 久久综合九色综合欧美就去吻| 97香蕉久久夜色精品国产 | 伊色综合久久之综合久久| 蜜臀av性久久久久蜜臀aⅴ| 久久精品国产99国产电影网| 人妻系列无码专区久久五月天| 午夜精品久久久久久99热| 狠狠精品久久久无码中文字幕| 久久精品国产99国产精品亚洲| 久久综合狠狠色综合伊人| 一本一道久久a久久精品综合| 久久婷婷五月综合国产尤物app| 久久99精品国产麻豆不卡| 久久国产精品成人影院| 2021国产精品午夜久久| 国内精品久久久久久久久| 国产91色综合久久免费| 7777久久久国产精品消防器材| 久久精品国产国产精品四凭| 99久久精品国内| 久久精品亚洲中文字幕无码麻豆| 亚洲乱码日产精品a级毛片久久| 色综合色天天久久婷婷基地| 久久人人爽人人爽人人AV| 四虎国产精品成人免费久久| 香港aa三级久久三级老师2021国产三级精品三级在 | 午夜精品久久久久久| 国产成人精品久久亚洲高清不卡 | 青草国产精品久久久久久| 亚洲国产一成久久精品国产成人综合| 中文字幕久久欲求不满| 99久久精品免费| 久久se精品一区精品二区国产| 亚洲国产精品久久久久网站| 久久久久一区二区三区|