Clang Static Analyzer內存模型(一)：MemRegion.iii

02-10

緊接《Clang Static Analyzer內存模型(一)：MemRegion.ii》

1.5 MemRegion - BaseRegion and Cluster

前面我們介紹了MemRegion中的SubRegion和SuperRegion，Clang Static Analyzer還有一個概念就是BaseRegion，SubRegion與SuperRegiong共同表示了Region之間的層次關係，而BaseRegion是用來組織語義上位於同一塊MemRegion中Regions。

註：關於BaseRegion，Clang Static Analyzer沒有一個完整的定義，上面我給出的描述可能不太準確，下面我會給出例子進行說明

關於MemRegion，Clang Static Analyzer只有有限的描述，該描述位於getBaseRegion()方法中，下面是該方法的注釋與定義。

// getBaseRegion strips away all elements and fields, and get the base region// of them.const MemRegion *MemRegion::getBaseRegion() const { const MemRegion *R = this; while (true) { switch(R->getKind()) { case MemRegion::ElementRegionKind: case MemRegion::FieldRegionKind: case MemRegion::ObjCIvarRegionKind: case MemRegion::CXXBaseObjectRegionKind: R = cast<SubRegion>(R)->getSuperRegion(); continue; default: break; } break; } return R;}

從getBaseRegion()方法的源碼可以看到，獲取一個Region的BaseRegion就是通過Super Region鏈找到第一個不是ElementRegion，也不是FieldRegion，ObjCIvarRegionKind和CXXBaseObjectRegionKind的Region，該Region就是其BaseRegion。按照函數定義，VarRegioin和AllocaRegion等的BaseRegion就是其本身。下面我們給出一段代碼示例進行說明。

// test.cstruct Students{ int mathScore; int engScore;};struct Class{ struct Students students[20]; int classNum; struct Class *next;};int main(){ struct Class one; one.classNum = 4; one.students[0].mathScore = 100; one.students[0].engScore = 85; one.students[10].mathScore = 99; one.students[10].engScore = 90; return 0;}

當analyzer執行完"one.students[10].engScore = 90;"語句時的內存層次圖如下所示：

上圖中所有綠色方框Region對應的BaseRegion都是one(VarRegion)，這也符合程序語義，如果main()方法中還有另一個局部變數或者局部對象，它又是另一塊BaseRegion。對應於BaseRegion，Clang Static Analyzer內存模型還有一個Cluster的概念，Cluster用於組織關係相鄰也就是相近的Region，只要是處於同一個BaseRegion下的Regions都位於同一個Cluster中，關於Cluster，RegionStore.txt有相關描述。

Regions are grouped into "clusters", which roughly correspond to "regions with the same base region". This allows certain operations to be more efficient, such as invalidation. -RegionStore.txt

Clang Static Analyzer針對Cluster提供了Cluster Analysis，可以將一個Cluster看做一個整體，並以該整體為基礎進行額外的分析，這就是上面提到的Cluster可以使某些操作更高效的原因。關於Cluster Analysis，我會在Loc -> Value : RegionStore 中進行介紹，這裡我先提一下關於如何使用Cluster Analysis進行invalidation。如下代碼示例。

// test.cstruct Students{ int mathScore; int engScore;};struct Class{ struct Students students[20]; int classNum; struct Class *next;};void func(int *);int main(){ struct Class one; one.classNum = 4; one.students[0].mathScore = 100; one.students[0].engScore = 85; one.students[10].mathScore = 99; one.students[10].engScore = 90; // one.next = ... ;有可能one指向了下一個Class對象 // 無法獲知func()函數的函數體，所以這裡進行conservative call evaluation。 // 由於將對象one的數據成員classNum的地址作為參數傳遞給func()，那麼func()就 // 有可能使one對象以及與one對象關聯的Region失效。 func(&one.classNum); return 0;}

在Clang Static Analyzer在分析到func(int*)函數調用時，只能通過conservative eval call（參見方法conservativeEvalCall()），來進行過程間的分析，其中conservative eval call中很重要的一步就是invalidate regions（參見方法invalidateRegions()），此時就會用到Cluster及其相關的Cluster Analysis。如下圖所示：

上圖中的橘黃色Region作為參數傳遞給func(int *)函數，而由於整個Cluster都有可能被func(int *)訪問到，所有都需要被invalidate，而由於對象one.next與one.classNum處於同一個Cluster中，所以one.next指向的Cluster也有可能被func(int *)訪問到從而失效，所以one.next指向的Cluster也要參與到Cluster Analysis的遞歸過程中。如下圖所示：

另一個涉及到Cluster Analysis的場景就是使用mark-sweep演算法進行remove dead bindings，其中使用Cluster Analysis找到live regions。

1.6 MemRegion - Region Casts

前面我們介紹了Clang Static Analyzer大致將Region分為幾類，並且介紹了表示這些Region類型的繼承關係，還有一個重要的主題沒有涉及就是MemRegion是如何表示Region Casts的，C語言中有很多指針類型轉換的場景，如果內存模型不能對Region Casts進行模擬的話，分析過程就會變得很不精確。這裡我將《A Memory Model for Static Analysis of C Programs》中的代碼示例摘抄過來，如下。

int main(){ void *p = malloc(10); char *buf1 = (char *)p; buf1[0] = a; int *buf2 = (int *)p; buf2[0] = 0; char c = buf1[0];}

上述代碼中，buf1和buf2其實指向的是同一塊內存，只是對同一塊內存有不同的解釋，一個將其解釋成char類型Region，一個將其解釋成int類型Region。Clang Static Analyzer使用前面介紹過的ElementRegion來表示Region Casts。Clang中用於處理Region Casts的方法是castRegion(const MemRegion *R, QualType CastToTy)，該方法最終會創建一個index為0的ElementRegion，該ElementRegion就表示轉換後的Region，Region的類型由Element Type表示，針對上面的代碼，對應的內存圖如下所示：

上圖展示了在分析前三條語句時的內存狀態，其中我們能夠看到在處理"char *buf1 = (char *)p"時，創建了一個type為char，index為0的ElementRegion。由於ElementRegion創建的lazy機制，在分析"buf1[0] = a;"時，Clang Static Analyzer才會去創建buf1中index為0的ElementRegion，此時發現相同的ElementRegion已經創建過，從而沒有創建。

上面這張圖與第一張圖類似，針對到buf2指針類型轉換，創建了一個type為int，index為0的ElementRegion，這兩張圖可以說和給出的代碼示例能夠完美的契合。針對普通的類型轉換，也是同樣的做法，創建一個新的特定類型的ElementRegion。

只是現在還有一個疑問，沒有解釋清楚，就是如果Region Casts是一條轉換鏈，例如"double *p = (double*)(int*)(char*)p;"這條程序語句，內存模型又該如何建模呢？Clang Static Analyzer針對這種情形，做了一些特殊處理，源碼中有所體現，我先將對應的注釋信息摘抄過來，然後再進行分析。

If we are casting from an ElementRegion to another type, the algorithm is as follows:

Compute the "raw offset" of the ElementRegion from the base region. This is done by calling getAsRawOffset().
If we get a RegionRawOffset after calling getAsRawOffset(), determine if the absolute offset can be exactly divided into chunks of the size of the casted-pointee type. If so, create a new ElementRegion with the pointee-cast type as the new ElementType and the index being the offset divded by the chunk size. If not, create a new ElementRegion at offset 0 off the raw offset region.
If we dont a get a RegionOffset after calling getAsRawOffset(), it means that we are at offset 0.

註：注釋信息有誤，現在getAsRawOffset()介面已經沒有了，對應的是getAsArrayOffset()。另外注釋中也有一些單詞拼寫錯誤。

源碼將Source Region為ElementRegion的RegionCast分為三種情況，我分別給出對應這三種情況的源碼示例：

extern void *p;int main(){ // (1) 情況1：如果Source Region(ElementRegion)對應的index為0. double *buf = (double*)(int*)(char*)p; // (2) 情況2：如果Source Region(ElementRegion)對應的index - idx不為0，且此 // 時offset(idx * sizeof(ElementType))可以被欲轉換的類型的長度 // sizeof(CastToTy)整除。 char array[12]; int *Iptr = (int*)&array[8]; // (3) 情況3：如果Source Region(ElementRegion)對應的index - idx不為0，且此 // 時offset(idx * sizeof(ElementType))不能被欲轉換的類型的長度 // sizeof(CastToTy)整除。 double *Dptr = (double*)&array[7];}

針對第一種情況，Clang Static Analyzer會以Source Region（ElementRegion）的SuperRegion為SuperRegion，創建一個type為CastToTy，index為0的ElementRegion，也就是說創建一個與Source Region同級的ElementRegion。第一種情況的內存模型如下所示：

在符號執行完"(double*)(int*)(char*)p"以後，會創建三個index都為0，但是類型不同的三個ElementRegion。

第二種情況，同樣會基於Source Region(ElementRegion)對應的SuperRegion創建一個新的ElementRegion，新創建的ElementRegion - index會基於source index計算得到。計算方法如下所示：

new_index = (source_index * sizeof(source_elementty)) / sizeof(castToTy)

針對第二種情況此時的new_index = (8 * 1) / 4 = 2，而新創建的ElementRegion對應的Type是int，此時內存圖如下所示：

上圖中arry(VarRegion)也是在"int *Iptr = (int*)array[8];"分析完成之後創建的，同時arry[8]對應的ElementRegion被創建，然後在調用castRegion()時，以arry為SuperRegion創建了另一個ElementRegion。

第三種情況與前兩種情況略有不同，此時Source Region的offset（以char為單位計數）不能被sizeof(castToTy)整除，此時就會以當前ElementRegion為SuperRegion，創建一個offset為0，type為castToTy的ElementRegion。第三種情況對應的內存如下圖所示。

使用ElementRegion表示Region Casts的前提是，相同index但是不同ElementType的ElementRegion不會被視為同一Region。這裡可以參照ElementRegion::Profile()方法，該方法會將SuperRegion，index和ElementType一起參與到計算FoldingSetID的過程中。

至此MemRegion大致介紹完了，主要是圍繞著MemRegionManager中主要的內存區域類型展開的。洋洋洒洒幾萬字，但是還沒有觸及到Clang Static Analyzer內存模型的核心，內存模型是如何參與到Clang Static Analyzer靜態分析過程中，並如何模擬存儲的，這些內容還沒有涉及。在後面的兩小節中，我會盡量精簡。後面兩小節會分別介紹內存模型是如何參與到符號執行過程中以及內存模型如何進行數據存儲。