作者
Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
狀態
草案
類型
標準追蹤
建立日期
2008-08-05
Erlang 版本
OTP_R12B-4

EEP 20:分割原子! #

摘要 #

一個來自 Flat Concurrent Prolog 的 Logix 實作的想法可以被應用於 Erlang:對於使用者來說,可以有兩種「原子」的實作方式,這將修復一個主要的系統完整性問題,並移除為了繞過這個問題而扭曲資料結構設計的需求。

規範 #

Erlang 語言或函式庫沒有使用者可見的變更。Erlang 和其他語言(如 C)之間的介面可能需要變更。

我們將原子分為兩類:「全域」原子是指那些出現在某些已載入模組的後處理文字中的原子,或是任何程序的已註冊名稱;「區域」原子是指程序建立的所有其他原子。

一個區域原子由一個資料結構表示,例如

+----------+
| size+tag |    boxed object header; see below
+----------+
| hashcode |    a 32-bit hash code
+----------+
| equivrep |    points to Union/Find representative
+----------+
| bytes of |
| name ... |
+----------+

像平常一樣,大小+標籤包含一個 2 位元的標籤表示它是一個 IMMED2 物件,一個 4 位元的子標籤表示它的類型(我建議使用 1011),以及一個 26 位元的 arity。然而,arity 欄位被分成兩個子欄位

+--------------+------------+----+--+
|  byte count  | char count |LATM|BX|
+--------------+------------+----+--+
             14           12    4   2   size in bits

字元計數表示名稱中有多少個 Unicode 字元。位元組計數表示這些字元儲存在多少個位元組中。為了緊湊性和向後相容性,名稱僅由 Latin-1 字元組成的原子,其位元組計數 = 字元計數,並且名稱以 Latin-1 表示;名稱超出該範圍的原子以其他形式保存,例如 UTF-8、SCSU、BOCU 或其他。這個提案並非特別針對編碼方案;我在此要說的是,它應該對所有原子都相同,並且應該至少與 UTF-8 一樣好。

雜湊碼欄位是一個 32 位元的雜湊碼。同樣,我對原子雜湊本身沒有任何要說的,除了要說該方法應該對節點上所有程序中的所有原子都相同,並且應該是一個好的雜湊方法。關於好的雜湊函式的建議很難找到。hashpjw() 可以改進。我衷心推薦 Valloud 的書

equivrep 欄位是一個指標。它總是指向一個原子,該原子可以是全域原子或區域原子。最初,它指向區域原子本身。當一個區域原子與另一個區域原子比較時,

  • 首先,檢查標頭欄位以查看它們是否匹配
  • 其次,檢查雜湊碼以查看它們是否匹配
  • 最後,檢查名稱的位元組。

但這也與 Union/Find 結合使用,非常像 Prolog 中的綁定變數。因此,我們在第二步之後「解除引用」(追蹤 equivrep 欄位),如果我們最終到達同一個地方,則兩個區域原子相等。如果兩個物理上不同的區域原子確實相等,我們讓較新的(最近建立的)原子指向較舊的原子。

全域原子應具有相似的表示形式;我建議將區域原子的表示形式嵌入全域原子的表示形式中,以便可以像比較兩個區域原子一樣比較區域原子和全域原子。

list_to_existing_atom/1 返回的原子始終是全域原子。由 list_to_atom/1binary_to_term/1 返回的原子,如果它們已經是現有的全域原子,則為全域原子,否則為區域原子。

提供給其他語言(如 C 或 Java)的介面應保留現有的原子建立操作,使其返回全域原子,並應新增用於建立區域原子 Operations。

當程序進行垃圾回收時,指向區域原子的指標會被該區域原子的 equivrep 替換,以便曾經注意到它們有重複區域原子的程序不會永遠保留它們。

動機 #

有一些問題限制了 Erlang 原子的可用性。

第一個是原子大小被限制為 255 個位元組,這使得 Erlang 原子在檔案名稱方面幾乎沒有用處,因為現在 C 的 FILENAME_MAX 通常為 1024。

第二個是原子被限制為 Latin-1 字元。我們確實希望它們完全支援 Unicode,這不僅僅是為了讓程式設計師在原始碼中使用奇怪的腳本編寫原子,而是為了允許資訊以原子的形式流經 Erlang 系統。

這兩個是次要問題。

主要問題是原子表。

它是一個全域資源,這意味著在 SMP 系統上,必須進行大量的鎖定和解鎖。這個提案不包含一個新的「總是返回區域原子」的操作,但它為需要鎖定的新操作創造了可能性。

在 atom.c 中,原子表被限制為 ATOM_LIMIT=1024*1024 個條目。即使在 32 位元的系統上,這也小於一台機器可以支援的大小;這是一個任意的限制,而這樣的限制始終是一個問題。

原子表不會被垃圾回收。一旦建立了一個原子,它就會被建立。像 Quintus Prolog 這樣的歷史 Prolog 系統也做了同樣的事情。早在 1984 年,這就被認為是一個問題,尤其是對於想要存取大量儲存資料的程式而言。像 SWI Prolog 這樣的現代 Prolog 系統會收集原子;如果不是這樣,SWI Prolog 對於操作大量 RDF 資料來說就不會那麼有用。這個提案沒有為原子表新增垃圾回收;它所做的是阻止大多數會被收集的原子首先進入該表。

填滿原子表會導致整個節點崩潰或掛起。

這意味著通過提供過多的原子來崩潰或雜湊 Erlang 軟體太容易了。

意味著想要在資料結構中使用原子(例如,作為字典中的鍵)的 Erlang 程式設計師會改用二元檔案:二元檔案的大小或數量不受限制,如果您需要,它們可以保存 UTF-8,它們可以被垃圾回收,並且使用起來通常更安全。

雖然這個提案讓原子使用起來更方便(它們可以更長、更多,並且可以包含 Unicode),但真正的重點是讓原子使用起來更安全。如果您可以通過 Erlang 程序從來源串流資料,將外部「字串」對應到二元檔案,那麼您將能夠以同樣安全的方式將它們對應到原子。

原理 #

Erlang 並非第一個面臨這些問題的語言。它甚至不是第一個面臨這些問題的並行語言。Flat Concurrent Prolog 早在那裡,雖然我沒有看過 Logix 原始碼,但這個想法在多年前的 Logix 文件中進行了解釋。我知道這個可以工作,因為它確實工作了。

Logix 對所有原子都使用了這種方法;最終,我相信 Erlang 也需要這樣做,以便在沒有大量鎖定的情況下處理數千個處理器。目前,繼續對相當「靜態」的原子使用舊的表示形式是有意義的。特別是,我們希望模組和函式名稱(以及當我們有時的框架鍵)保持現在的樣子。如果在建立區域原子之後載入應用程式,我們可能會發現它畢竟是一個模組名稱或函式名稱;這也是使用 equivrep 欄位的原因之一。一旦注意到,重複項就不會在另一次垃圾回收中倖存下來。

當前的「全域原子」表示形式有一個 hack 來加速項目的比較。為了簡單起見,我上面沒有描述它,因為這與這個 EEP 所關心的問題是正交的。我注意到 (a) 為了讓 ord0 欄位繼續以目前的形式存在,編碼最好是 UTF-8 或 BOCU,並且 (b) 為了保持 Latin-1 原子的緊湊性,ord0 欄位應該是如果原子已儲存在所選的 UTF-8 或 BOCU 中,則會儲存的前 31 位元。我也注意到 (c) 如果您不允許「原生」位元組順序決定原子名稱位元組的儲存順序,則您不需要特殊的 ord0 欄位。

我應該承認,這個提案並不能完全避免崩潰和掛起的問題。如果可以說服 Erlang 系統從不可信的來源載入模組,仍然可以讓它嘗試建立足夠多的原子而陷入麻煩。這是我認為 Erlang 最終必須放棄全域原子表的原因之一。但是,任何載入模組的人

從不可信來源載入,應該知道他們正在這樣做;這是一個明顯危險的事情。list_to_atom/1 並非明顯危險的函式,而且它不應該比 list_to_binary/1 更危險。

向後相容性 #

任何現有程式碼(在 Erlang 實作之外)都不應受到絲毫影響。

參考實作 #

無。這個變更在概念上很簡單,但會影響系統核心中的幾個原子。

版權 #

本文件已置於公共領域。