TWI220032B - Data processing system and method for performing address translation - Google Patents

Description

1220032 A7 B7 經 濟 部 智 慧 財 產 局 員 工 消 費 合 作 社 印 製 五、發明說明（ 發明領域： 本發明概有關於電腦記憶體，並且特別是有關於電腦 記憶體定址技術。而更特別是本發明係有關於具有防護性 檢查功能之改良式記憶體位址轉換系統。

發明背景Z 今日的電腦系統中，系統記憶體係由所作業系統掌 管，並且按照需要而配置予不同的軟體應用程式。虛擬記 憶體為一種可將相當少量的實體記憶體，製作成似乎為較 大並且可以由多個程序所分享共用之技術。因此各個軟體 應用程式即係面對「有效的」虛擬記憶體空間上之位址， 當有所需要時可讓該應用程式進行讀取、寫入與執行，而 不必在意其作業進行於實體記憶體或是於磁碟記憶體上 的真貫位置。該應用程式仰賴該作業系統以執行該自有效 位址至實體位址的對映作業。 位址轉換 位址轉換為一種機制，藉.此而將由cpu產生可供存取 到虚擬記憶體的有效位址，轉換成實際記憶體上的位址。 位址轉換為-種複雜程序’如果未以適當方式實作之，則 或將涉及到決定處理器時鐘週期的重要途徑。對所有架構 而T該點均為事實，尤其是對需要兩 呵增式程序以轉換位址 的架構來說更是如此。 現參考第4圖，其中係顯示一傳 得統兩階式位址轉換程 第2頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） --^----I I--II 丨-丨丨 — 丨 I _ 丨訂----- - - I - --AWI (請先閱讀背面之注意事項再填寫本頁) 1220032 A7

經濟部智慧財產局員工消費合作社印製 五、發明說明（） 序之流私圖。為轉換某一使用兩階式位址轉換的位址，首 先需使用到區段資訊來將有效位址轉換為臨時虛擬位 址，然後由分頁列表資訊而將其轉換為實體位址。這兩項 轉換階段會需要去檢查防護位元，而該等位元指示出可允 許之存取型態（如讀取、寫入、讀寫、隱藏）。 在該圖裡，當C P u提出一項有效位址之請求時（步驟 400)，該系統首先會檢查「區段暫存器（SR)」以及「區段 側視緩衝器（SLB)」，以決定對映於該有效位址的虛擬位址 (步驟4 10)。為此，系統也必須要執行防護檢查，以確定 該程序所請求之存取型態係屬所允許的項目（步驟4 2 0)。 注意到在此所列之各式快取架構將於後文詳述之。如果通 過〃亥防遵檢查’則該心序可產生一虛擬位址，若否即返還 一錯誤訊息。 接著利用該虛擬位址以存取到該區段側視緩衝器，藉 此決定其正確的分頁表，以及對映到該虛擬位址的實體位 址（並且因而對映到該有效位址）（步驟430)。再次地，該 系統也必須執行防護檢查，以確定該程序所請求之存取型 悲係屬所允許的項目（步驟4 4 0)。最後，如果通過該防護 檢查，則回覆一有效實體位址給該CPU程序（步驟450)。 現參考第5圖’此為一作為位址轉換用分頁表之使用 範例。該圖中，虛擬記憶體5 1 5/525兩者，以及實體記憶 體5 00被分割成多的「分頁」，而各個分頁上一般為相同 大小。給予彼等各袖分頁一特定之「分頁碼框編號（pFN)」 (該PFN係指實體記憶體的分頁碼框編號，而vpFN係指 第3頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） I ϋ n H ϋ ϋ n ϋ· n n ϋ ί I ϋ l_1 an I— fl— ϋ n 一ej· am— a— n n n n ϋ I ϋ (請先閱讀背面之注意事項再填寫本頁) 1220032 A7

經濟部智慧財產局員工消費合作社印製 虛擬記憶體的分頁碼框編號 例如將記憶體内某一位置上的内=式中母-個指令’ ⑽即執行-個由虛擬位：广暫存器中1

時，如果該指令本身會參考 ^ ^ R β己隐體，則亦將針對兮炎 而執行一轉換作業。 听紂對泛參， 該虛擬與實體記憶體之間 '罝轉換，是由cpn获 其中包含有該CPU需要之所f # 田CPU精由 W 所有資訊的分頁表所完成。1 通說來，對於系統内的各個程 均 斤都會有一個分頁表。第, 圖顯示一利用程序X 525與程庠v ^ k ' ”钕序Y515的分頁表而進行 擬位址與實體位址之間的簡易對映圖示。

在該例中，顯示於該程序X ^八 < 虛擬圮憶體525内的程 序X虛擬PFNO,會藉由程序χ的分頁表52()而對映 體記憶體PFN卜而顯示於該程序χ之虛擬記憶禮515 : 的程序Υ虛擬PFN1，則會藉由程序Υ的分頁表51〇而對 映到實體記憶體PFN 4。 刀頁表510/520的各個項目均包括下列資訊： 虛擬PFN， 其所對映到的實體PFN，，以及 該分頁所用之防護（存取控制）資訊。 為將虛擬位址轉換成實體位址，該CPU首先必須移除 該虛擬PFN以及其在該虛擬分頁範圍之内的位移量的位 址。然後該CPU搜尋該程序的分頁表，以找出一可符合 該虛擬PFN的項目'。如此即可獲得所欲尋得之實體pfn。 接著該CPU取出該實體PFN並且將其乘以分頁大小 第4頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ： . -------^---------- f請先閱讀背面之注意事項再填寫本頁} 1220032 五 ΘΙ fi. 、發明説明（） 值’藉以求出該分頁在實體記憶體中的基底位址。最後， 該CPU將一位移值加到其所需要之指令或資料。 藉由依此而將虛擬位址對映實體位址的方法，該虛擬 記憶體515/525即可按任何次序而對映到系統的實體分頁 5〇〇。譬如說，在第5圖内，程序X的VPFN 0係對映至實 體PFN 1，然而VPFN 7則是對映到實體PFN 0，即使其在 虛擬記憶體中卻高於虛擬PFN 0。因此，虛擬記憶體之諸 为頁並不需要以任何特定順序來出現於實體記憶體内。 與一般的使用者層級之應用程式不同，執行於伺服器 以及PC伺服器環境下的資料庫和交易處理應用程式，係 擁有大量的記憶體需求。資料庫的工作負載會觸及大量的 各式記憶體分頁’在此即極度需要該位址轉換機制以便斜 其存取。 取技術 為增強系統效能，特別是有關於記憶體方面，故可 用多種不同型態的記憶體快取技術。該等技術包括可用以 加速位於磁碟上之虛擬記憶體影像與資料存取的分頁快 取。當分頁由磁碟而被讀入記憶體内時，彼等即被排入其 分頁快取之中。如果已將彼等拋棄而如今又需要時，則。' 迅速地再度將其擷取至該快取内。 各分頁中可包含資料緩衝器提供給系統核心、奘 π夏德 動程式等使用。該緩衝器快取為一緩衝器之側視清單。 巧干0例 第5頁 本紙張尺度適用中國國家標準(CNS)A4規格(210Χ 297公釐) " '^ (請先閲讀背面之注意事項再塡寫本頁> Γ 經濟部智慧財產局員工消費合作社印製 1220032 A7 B7 經濟部智慧財產局員工消費合作社印製 五、發明說明（ 如，假設某一裝置驅動程式需要256位元組的緩衝器，則 自該緩衝器快取中取出一緩衝器，比起配置— 且賞體分頁然 後將其切割成2 5 6位元組緩衝器來說會較快。 當系統使用到一磁碟為基礎的虛擬記憶體宭 n 蔹言己憶 體一般係存放在「代換檔案」處。然為節省將資料儲存於 該代換檔案内的時間（比起存放在RAM裡會緩慢得多） 許多系統均採用「代換快取」，而僅將經覆窝（或是不淨的） 之分頁儲存到該代換檔案處。倘彼等分頁在被寫入至該代 換標案處之後未經任何修改，則下次當該頁被代換出來 時，即無須再寫入該代換檔案，因為該頁已然存在於該代 換檔案内。相反地，僅僅將該頁拋棄即可^在某代換作業 繁重的系統中，如此可節省許多不必要且昂貴的磁碟作 一種經常實作之快取硬體係位於CPU之内：分頁表項 目快取。在本例中，該CPU並不直接讀取該分頁表，而 是當需要時已快取獲得該分頁之轉換。這些為轉換侧視緩 衝器’其中並包含保存於作業系統分頁表内的資訊拷貝。 當參考到該虛擬位址實，該.CPU會試圖找出相符的TLB 項目。如果找到了一個，則即可直接將虛擬位址轉換成實 體位址，並對該資料執行正確的作業。如果該CPU找不 到一相符的TLB項目，則必須向作業系統求助。為此， 可提出一例外事件。本質上，這意味著向該作業系統發出 訊號’說明發生了 TLB誤失。 其他可增強效能之硬體特性，包括有區段暫存器 第6頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ,111;— — II— --till!--^ I —^wi (請先閱讀背面之注音？事項再填寫本頁) !22〇〇32 ；··, ；Λ； Ά7 ^ _______ B7__ 五、發明説明（） (SRs)，以及高速快取所叫用之區段侧視緩衝器（SLBs)。 該SRs與SLBs會握持最近使用過的段落列表項目，然後 被搜尋而以提供用於有效性虛擬位址轉換程序方面的必要 資訊。 該等機制可增強位址轉換程序之效能。唯彼等快取， 無論是否為硬體方式，其缺點係該系統必須使用較多的時 間與空間來維持該快取，並且如果彼等快取因故毀損，則 該系統亦將崩潰。除此之外，這些型態的快取並無法消除 防護檢查的需要。 防護檢查 防δ蔓檢查乃為對於所請求之記憶體存取型態為可允許 之確認程序。每一個項目均可被標示為例如「可執行」、「不 可執行」或是「唯讀」。該作業系統必須對該位址之防護 k訊而檢查其記憶體存取型態，以便確定可允許存取該記 憶體（無論是讀、寫或是執行）。由於這種存取必須接受檢 查，因此任何數量的傳統快取技術，僅能在記憶體存取時 間方面提供有限的改良結果，造成防護檢查反變成一項瓶 頸。故亟需要一種具備改良式防護檢查系統的有效性虛擬 記憶體存取與位址轉換裝置。 發明概沭： 本發明之一目的即在於提供一種改良式電腦記憶體。 而本發明之另一目的，即在於提供一種改良式電腦記 第7頁 本紙張尺度適用中國國家標準(CNS)A4規格(210X297公釐) .............1 裝-· (請先閲讀背面之注意事項再填寫本頁) 訂· 經濟部智慧財產局員工消費合作社印製 經濟部智慧財產局員工消費合作社印製 1220032 A7 ____B7_____ 五、發明說明（） 憶體定址系統。 而本發明又另一目的，即在於提供一種具有防護檢查 之改良式用以記憶體位址轉換的系統與方法。 上述諸項目的之達成如下所述。 本發明可提供一種記憶體轉換系統，其中包括一種「位 址快取（addcache)」。該位址快取包含最近經參考之位址的 轉換資訊，並且會在傳統性兩階式位址轉換程序進行之前 被加以存取。如果在位址快取中產生有一「命中」結果， 而且該結果並不需要防護檢查，則傳統式位址轉換程序會 將此略除。該位址快取根據各個位址的防護狀態而存放其 記憶體位址，因此並不是以單獨步驟的方式來執行該防護 檢查。 本發明前揭以及他項目的、特性與優點，經後續描述 之細部書面說明即可成為顯而易知。 圖示簡單說明 ： 本發明之新且可信的技術特徵係參照於隨附之申請專 利範圍内。然藉參酌下列範例性具體實施例之詳細說明並 連同本附圖，即可輕易明瞭本發明以及其較佳之使用模 式，以及目的及其優點，而其中： 第1圖說明符合本發明一較佳之具體實施例的資料處理 系統， 第2圖說明符合本發明一較佳之具體實施例的位址轉換 系統區塊圖； 第8頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公爱） (請先閱讀背面之注意事項再填寫本頁) Φ-----——訂ί 線·φ. 1220032 經濟部智慧財產局員工消費合作社印製 A7 B7 五、發明說明（） 第3圖為符合本發明一較佳之具體實施例的位址轉換程 序流程圖； 第4圖為傳統兩階式位址轉換程序之流程圖；以及 第5圖為適於位址轉換作業的分頁表應用之範例性區塊 圖。 圖號對照說明： 100 資料處理系統 101,102 處理器 103, 104 第二階快取 106 系統匯流排 108 系統記憶體 112 I/O匯流排 114 非揮發性儲存裝置 116 鍵盤/指示裝置 118 圖形介面卡 120 顯示器 121 ISA橋接 122 主機橋接 124 PCI插槽 200 程序 210 位址快取 220 SR/SLB 230 TLB 240 實體記憶體 500 實體記憶體 510 分頁表 5 1 5,525 虛擬記憶體 520 分頁表 發明詳細說明： 現參考各隨附圖示’特別是由第1圖裡一種資料處理 系統之區塊圖’其中可實作一本發明之較佳具體實施例。 該資料處理系統100可為例如像是可由紐約Armonk市的 IBM公司購得之電腦。該資料處理系統1〇〇内包括處理器 第9頁 本紙張尺度適用中國國家標準（CNS)A4規格(210 X 297公釐） ---— IT---:----------------訂---------線— (請先閱讀背面之注意事項再填寫本頁) 1220032 A7 ______ B7 五、發明說明（） I 0 1和1 02，二者在範例性具體實施例中個別連接至第二 階（L2)快取1 〇3與1 〇4，然後彼等快取再連接到系統匯流 m 1〇6 。 同樣連接到系統匯流排丨06處者尚包括系統記憶體 108與第一主機橋接（phB)122。該PHB 122將I/O匯流排 II 2搞接到系統匯流排1 〇 6處，將資料由某一匯流排中繼 及/或轉換至另一匯流排。在本範例性具體實施例中，該 資料處理系統1 〇〇包括連接至1/0匯流排i丨2的圖形介面 卡11 8，用以接收提供給顯示器丨2〇的使用者介面資訊。 例如像可為硬碟機的非揮發性儲存裝置丨丨4，以及可為傳 統滑鼠、軌跡球等鍵盤/指示裝置11 6等等的週邊裝置， 均經由ISA橋接121而連接至I/O匯流排112。該PHB 122 亦經由I/O匯流排112而連接到PCI插槽124。 第1圖裡範例性具體實施例中僅係提供作為解釋本發 明之用，對於熟捻本項技藝人士而言，當即知悉足以不同 形式與功能而實作之。例如，該資料處理系統1 〇〇亦可包 含一 CD-ROM或DVD光碟機，音效卡以及喇叭，與無數 其他選用元件。所有這種變化深信仍屬本發明精神與範圍 之内。該資料處理系統1 00與下述之範例性流程圖係提供 作為說明之用，而並不意味著其屬架構性限制。 本較佳之具體實施例包括一「位址快取」（addcache)。 如同上述之傳統快取（SCBs、TLBs)，該位址快取内包含有 最近參考位址的轉換資訊。不過，本較佳具體實施例之不 同處，係駐放於該兩階式位址轉換程序之前，並且儘可能 第10頁 本紙張尺度適用中國國家標準（CNS)A4規格（21〇 X 297公釐） (請先閱讀背面之注意事項再填寫本頁) # 訂---------線！ 經濟部智慧財產局員工消費合作社印製 1220032 A7 經濟部智慧財產局員工消費合作社印製 五、發明說明（ 地略過該項機制以及其防護檢查之開銷負擔。 現參考第2圖’此為上揭位址快取系統之區塊圖。當 程序200提出一位址請求時，該所請求之虛擬位址及必須 轉換成實體位址。該系統首先向位址快取21〇請求該位址 轉換。如果該請求在此「命中」，則由位址快取21〇回應 一有效位址予程序200,並且完成了到實體記憶體24〇的 存取作業。 如果並未在位址快取210中查得該所請求有效位址的 轉換貝訊，則執行一般性的兩階式位址轉換程序，附帶進 行所需之防護檢查。首先，檢查該SR/SLB 22〇的區段資 訊，以及檢查記憶體防護資訊。接著，檢查該TLB 23〇 的分頁表資訊，並且再度檢查記憶體防護資訊。最後，當 轉換完成並且返回至程序2〇〇時，將轉換資訊存放於位址 快取2 1 0内，俾加速下一次的轉換作業。 根據本較佳之具體實施例，除非已斷定為「安全」狀 態而不會遭受潛在之防護侵犯，否則並不會將該轉換資訊 置入於位址快取2 1 0内。因此，上揭之快取技術不僅可藉 略過冗長的兩階式轉換程序而獲致一效能增益，同時尚可 藉略過該防護檢查要求，以消除肇因於防護檢查成本而生 之效能損耗。 根據本較佳之程序，如果指令參考項係屬可讀取，而 且並非駐放於標示為「不可執行」的記憶體區域内，或者 是如果該資料參考凟同時為可讀取及可寫入，則將某一位 址快取候選者視為不會遭受潛在之防護侵犯的安全狀 第11頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公爱 (請先閱讀背面之注意事項再填寫本頁) I I----""丨訂 *--I----- 1220032 A7 B7 經濟部智慧財產局員工消費合作社印製 五、發明說明（） 態。 更進一步，該指令與資料之位址快取係屬分隔狀態， 以有效率地容納對於各項指令與資料不同的「安全」要 求。該資料位址快取更可依照載入與儲存而予以切割，因 為只有儲存請求才會需要該存取狀態需同時為可讀且可 寫。 可藉一般常用以實作直接對應搜尋功能之雜湊函數， 而迅速地對該位址快取陣列搜尋其所需之真實位址資 訊。該位址快取之元件包括： 虛擬分頁資訊（VSID +分頁）以確認已尋得正確的 -I 虛擬分頁； VirtualPage 係由 VSID一unshifted 與 Pagelndex 所組 成 真實分頁編號（RPN)，用以快速存取/計算實體位址 分頁列表項目（P T E)之指標，以便快速修改其變更 與參考位元。 為避免程式之執行與系統錯誤，當TLBs及SLBs在傳 統系統中以一般方式沖除時，亦可將該位址快取適當地沖 除。 在本較佳之具體實施例裡，該位址快取包含個別的指 令與資料快取，各自具有5 1 2個項目。彼等快取各自包括 有其取近參考位址之轉換資訊。 可根據本發明較佳具體實施例而由下列虛擬程式碼定 第12頁 (請先閱讀背面之注意事項再填寫本頁) #

訂-I 線—命 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 1220032 A7 __B7__五、發明說明（） 義其資料結構。 /* structures for address translation "caches'* for simulation speedup -separate I/D array of pointers to recently used "safe" PTEs ★/ 一、 struct { struct { /* Virtual Page * VSID + PAGE ♦/ uint64 VSID_unshiftedL； uintl6 Pagelndex 一shifted; } VirtualPage; uint64 RPN; PA ptep; } iaddrcache[512]; struct { struct { /* Virtual Page = VSID + PAGE ★/ uint64 VSID一 unshifted; uintl6 PageIndex—shifted; } VirtualPage； uint64 RPN； PA ptep; } daddrcache[512 】； (請先閱讀背面之注意事項再填寫本頁) ϋ «1 βϋ H ί ί emmam ^ ^ I n n tmw n tmmm Λβββ —B_i I ϋ 經濟部智慧財產局員工消費合作社印製 利用任何該項技藝所廣為眾知且熟捻之有效雜湊函 數，來對這些陣列搜尋所請求之PTE。藉範例所示，該雜 湊函數可採行直接對應式雜湊法，而對於5 1 2陣列即需要 9個位元的addr ·· hash 一 addr 一 9bit = [EA(36:39) xor EA(43:36)] cat 第13頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐）

經濟部智慧財產局員工消費合作社印製 1220032 五、發明說明（） EA(47:51) 現參考第3圖，其中顧+ — _ 顯不—付合本發明較佳具體實施 例的電腦系統内位址快取血刑虛 %八翌應用万式之解釋性流程 圖。該程序開始時，正在勃料立仏产 社m仃某些應用程序的cpu對所 請求之指令或資料（步驟3〇〇)違生 七 ·— μυ)產生一有效位址。接著蔹 cpu請求所需要的位址轉換作業（步驟3〇5)。 根據該有效位址而來搜尋（步驟31〇)該位址快取 (addr㈣he)，以尋得指向—有效pTE之指標。該項搜尋動 作會利用傳統的雜湊函數，根據所需要的位址型態而在各 個資料/指令快取中分別進行。 如未尋獲有效PTE(步驟315)，而且該相符之指標並未 被指足成（「2白」），則會利用一般傳統的兩階式位址轉 換序以查核該位址（步驟340)。所獲結果項目如果經斷 定此為安全之項目（如前文所定義），則會被加入到該 addrcache以供下一次使用（步驟345)，以避免所需要進行 的兩階式位址轉換和防護檢查之支出。 然本圖中應注意到該兩階式轉換雖在此顯示為單一程 序’不過該敘述僅係為便於說明。該步驟3 4 0的位址轉換 程序係一高度成本、多重步驟之程序，詳如第4圖所繪 示。 另外，倘若一有效PTE係經尋獲（該指標並未被指定 成空白），則該系統會檢查所請求之虛擬分頁（VSID +分 頁），是否相符於該addrcache項目（即屬於目前程序）（步驟 3 2 0)。如果VSID無法立即由SR或SLB所取得，則採行 第Η頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） f請先閱讀背面之注意事項再填寫本頁) 訂----- 線 — 經濟部智慧財產局員工消費合作社印製 1220032 A7 --- 圓· 一· _—一· _ R7 _ 五、發明說明（） 兩階式位址轉換程序（步驟340)。如果可取得VSID，則完 成該虛擬分頁合配/檢查作業。 當執行過該查核程序，此即意味著該系統接著應計算 該實體位址（步驟325)，並且去由該記憶體子系統處擷取 所請求之資訊（步驟33〇)。該系統記憶體等待下一個位址 請求，並重覆進行前述作業（步驟335)。 應加以注意之重點為本發明雖係描述於一全功能資料 處理系統即/或網路之環境内，然對熟捻本項技藝之人士 而言，應即知悉本發明的快取機制可為各種形態之電腦可 用指令媒體方式而配發，並且無論是採用哪一種訊號荷載 媒體特定型式以便實際執行該配送作業，均可一致地應用 本發明。該電腦可用之媒體可例如像是··非揮發性，硬式 編碼型態媒體如唯讀記憶體（R〇Ms)、或是可拭去電子性 可程式化的唯讀記憶體（EEPR0Ms)、例如像是軟碟、硬碟 機與CD-ROM的可紀錄性媒體，以及例如像是數位與類 比通訊鏈結的傳輸式媒體。較佳之快取系統亦可由與處理 益或έ己憶體關係密切的專屬性快取系統記憶體，或是傳統 式系統記憶體的動態定址表方式來實作。 本發明雖係以較佳具體實施例的方式以圖緣及說明， 然對熟捻本項技藝之人士而言，應知悉可對各型式與細節 施予諸項變化，而仍不會悖離本發明之精神及範轉。 第15頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） -1 ^----：----------------訂---------線丨 (請先閱讀背面之注意事項再填寫本頁)

Claims (1)

1220032 A8 B8 C8 D8 六、申請專利範圍 存於位址快取之内。 (請先閱讀背面之注意事項再填寫本頁) 8. 如申請專利範圍第7項所述之方法，其中如果在位址快 取中尋得該項目，則比起若該項目僅係存放於轉換快取 内時，將以較少的時間來回返該實體位址。 9. 如申請專利範圍第7項所述之方法，其中上述之位址快 取内所有項目均具有先前既存之防護檢查功能。 經濟部智慧財產局員工消費合作社印製 第18頁 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐）