1. 基本介紹

tensorflow設備內存管理模塊實現了一個best-fit with coalescing算法（后文簡稱bfc算法）。

bfc算法是Doung Lea's malloc(dlmalloc)的一個非常簡單的版本。

它具有內存分配、釋放、碎片管理等基本功能。

2. bfc基本算法思想

1. 數據結構

整個內存空間由一個按基址升序排列的Chunk雙向鏈表來表示，它們的直接前趨和后繼必須在地址連續的內存空間。Chunk結構體里含有實際大小、請求大小、是否被占用、基址、直接前趨、直接后繼、Bin索引等信息。

2. 申請

用戶申請一個內存塊（malloc)。根據chunk雙鏈表找到一個合適的內存塊，如果該內存塊的大小是用戶申請的大小的二倍以上，那么就將該內存塊切分成兩塊，這就是split操作。

返回其中一塊給用戶，并將該內存塊標識為占用

Spilt操作會新增一個chunk，所以需要修改chunk雙鏈表以維持前驅和后繼關系

如果用戶申請512的空間，正好有一塊1024的chunk2是空閑的，由于1024/512 =2，所以chunk2 被split為2塊：chunk2_1和chunk2_2。返回chunk2_1給用戶并將其標志位占用狀態。

3. 釋放

用戶釋放一個內存塊（free）。先將該塊標記為空閑。然后根據chunk數據結構中的信息找到其前驅和后繼內存塊。如果前驅和后繼塊中有空閑的塊，那么將剛釋放的塊和空閑的塊合并成一個更大的chunk（這就是merge操作，合并當前塊和其前后的空閑塊）。再修改雙鏈表結構以維持前驅后繼關系。這就做到了內存碎片的回收。

如果用戶要free chunk3，由于chunk3的前驅chunk2也是空閑的，所以將chunk2和chunk3合并得到一個新的chunk2'，大小為chunk2和chunk3之和。

3. bins

1. bins數據結構

bfc算法采取的是被動分塊的策略。最開始整個內存是一個chunk，隨著用戶申請空間的次數增加，最開始的大chunk會被不斷的split開來，從而產生越來越多的小chunk。當chunk數量很大時，為了尋找一個合適的內存塊而遍歷雙鏈表無疑是一筆巨大的開銷。為了實現對空閑塊的高效管理，bfc算法設計了bin這個抽象數據結構。

每個bin都有一個size屬性，一個bin是一個擁有chunk size >= binsize的空閑chunk的集合。集合中的chunk按照chunk size的升序組織成單鏈表。bfc算法維護了一個bin的集合：bins。它由多個bin以及從屬于每個bin的chunks組成。內存中所有的空閑chunk都由bins管理。

圖中每一列表示一個bin，列首方格中的數字表示bin的size。bin size的大小都是256的2^n的倍。每個bin下面掛載了一系列的空閑chunk，每個chunk的chunk size都大于等于所屬的bin的bin size，按照chunk size的升序掛載成單鏈表。