嵌入式或無線通信系統中用於存儲器分配的系統和方法

2023-05-18 10:52:36

專利名稱：嵌入式或無線通信系統中用於存儲器分配的系統和方法
嵌入式或無線通信系統中用於存儲器分配的系統和方法相關申請的交叉引用 本申請要求於2008年4月2日提交的題為MEMORY ALLOCATION SCHEME FOR EMBEDDED OR WIRELESS COMMUNICATION SYSTEMS (用於嵌入式或無線通信系統的存儲器分 配方案)的美國臨時專利申請S/N. 61/041，878的權益。該申請的全部內容通過援引納入 於此。背景 發明領域本領域一般涉及存儲器分配，尤其涉及嵌入式或無線通信系統中的存儲器分配。
背景技術：
存儲器分配服務利用存儲器項池。在一些情形中，存儲器項基於存儲器項的大小 被分序到不同的池中。例如，一個池可能包括許多小存儲器項，而另一個池可能包括相對 少的大存儲器項。響應於存儲器分配請求，可從特定池中選擇恰適數據項並將其返回給請 求方實體。該系統導致顯著的存儲器和處理器資源浪費。例如，在小存儲器項的情況下，頭 部與有效載荷之比較高，導致低效率的存儲器使用。進一步，當整個存儲器項被分配時，任 何特定數據項的顯著數據部分可能處於未使用。另外，在這些分配服務中，沒有統計復用可 用。處理器資源也因多個小存儲器項的連結而被消耗。在無線通信系統中，分組常常被分段成較小的固定大小——例如40位元組——的 「無線電鏈路」分組，以確保可靠的無線電傳輸。為了高效率地使用存儲器，一種辦法是創建 各保持40位元組塊的相對小存儲器項的大池，這些存儲器項最終在較高層上被連結在一起 以形成較大的數據塊(例如，1500位元組的IP分組)。此服務的一個缺點在於一些空間可能 被浪費，因為這些存儲器項可能必須對準高速緩存行(32或64位元組)，這可能不適合小的無 線電鏈路分組大小。另外，不同技術可能共享相同的存儲器項池以減小整個存儲器，在這種 情形中必須將存儲器項有效載荷大小選取為適合最大的無線電鏈路分組大小，其會進一步 增加浪費。發明概述在一個實施例中，提供了一種提供存儲器管理的系統。該系統包括處理器和可在 該處理器上執行的存儲器管理服務。該存儲器管理服務可配置成生成第一存儲器項，其中 第一存儲器項中的每一者包括頭部和有效載荷，有效載荷可配置成存儲多個可獨立分配的 存儲器大塊，第一存儲器項的頭部引用有效載荷中的可分配空間；生成第二存儲器項，其中 第二存儲器項中的每一者包括引用第一存儲器項的有效載荷中的一個或多個存儲器大塊 的頭部；以及響應於存儲器分配請求返回來自或者第一或者第二存儲器項的頭部的引用。在另一個實施例中，提供了一種用於存儲器管理的方法。該方法包括分配第一存 儲器項，第一存儲器項各自包括第一頭部和有效載荷，有效載荷包括可獨立分配的存儲器 大塊，第一頭部包括對有效載荷中未分配存儲器的引用；分配第二存儲器項，第二存儲器項各自包括第二頭部，第二頭部包括對第一存儲器項的有效載荷中獲分配存儲器大塊的引 用；接收對存儲器分配的請求；以及通過返回來自第一或者第二存儲器項的頭部的引用來 響應對存儲器分配的請求在另一個實施例中，提供了一種存儲器管理系統。該系統包括用於分配第一存儲 器項的裝置，第一存儲器項各自包括第一頭部和有效載荷，有效載荷包括可獨立分配的存 儲器大塊，第一頭部包括對有效載荷中未分配存儲器的引用；用於分配第二存儲器項的裝 置，第二存儲器項各自包括第二頭部，第二頭部包括對第一存儲器項的有效載荷中獲分配 存儲器大塊的引用；用於接收對存儲器分配的請求的裝置；以及用於通過返回來自第一或 者第二存儲器項的頭部的引用來響應對存儲器分配的請求的裝置。在另一個實施例中，提供了編碼有計算機指令的計算機可讀介質。這些指令在被 執行時使得處理器分配第一存儲器項，第一存儲器項各自包括第一頭部和有效載荷，有效 載荷包括可獨立分配的存儲器大塊，第一頭部包括對有效載荷中未分配存儲器的引用；分 配第二存儲器項，第二存儲器項各自包括第二頭部，第二頭部包括對第一存儲器項的有效 載荷中獲分配存儲器大塊的引用；接收對存儲器分配的請求；以及通過返回來自第一或者 第二存儲器項的頭部的引用來響應對存儲器分配的請求。附圖簡要描述

圖1是圖解行動裝置的示例的框圖。圖2是圖解存儲器項的示例的框圖。圖3是圖解存儲器項的另一個示例的框圖。圖4A和4B是圖解用於分配存儲器的方法的示例的框圖。圖5是圖解存儲器分配服務的執行的各種示例的框圖。圖6是圖解用於分配存儲器的方法的另一個示例的框圖。優選實施例的詳細描述以下詳細描述涉及本發明的某些具體實施例。然而，本發明可用眾多不同方式來 體現。應顯然的是，本文中的各方面可用各種各樣的形式來體現並且本文中所公開的任何 具體結構、功能或這兩者僅僅是代表性的。基於本文中的教示，本領域技術人員應領會，本 文中所公開的一方面可獨立於任何其他方面來實現，以及這些方面中的兩個或多個可按各 種方式被組合。例如，使用本文中闡述的任何數目的方面，可實現裝置或可實踐方法。此外， 可使用其他結構、功能性或使用除本文中所闡述的方面中的一個或多個之外的或與之不同 的結構、功能性來實現這樣的裝置或實踐這樣的方法。行動裝置典型地利用存儲器分配服務來進行操作。本文中描述用以降低行動裝置 中各種子系統所需的存儲器的總量以及用以減少行動裝置所消耗的處理資源的方法和設 備。以下闡述的是可聯合所描述的方法和設備使用的一些架構。圖1是圖解行動裝置102的示例的框圖。設備102包括與存儲器204通信的處理 器202以及用於經由無線鏈路106通信的網絡接口 206。可任選地，設備102還可以包括 以下各項中的一者或多者顯示器210 ；諸如按鍵、觸控螢幕、或其他合適的觸覺型輸入設備 之類的用戶輸入設備212 ；包括適於基於在無線鏈路106上接收到的信號提供音頻輸出的 換能器的擴音器214 ；和/或包括適於提供可在無線鏈路106上傳送的信號的音頻輸入的 換能器的話筒216。例如，電話可包括適於提供圖形用戶界面(GUI)的視覺輸出的顯示器210。網絡接口 206可包括任何合適的天線(未圖示)、接收機220、和發射機222，以使 得示例性設備102可在無線鏈路106上與一個或多個設備通信。可任選地，網絡接口 206 還可以具有用以減少處理器202的處理需求的處理能力。可任選地，設備102可包括經由鏈路108在網絡110上通信的第二網絡接口 208。 例如，設備102可經由有線或無線通信鏈路來提供與其他網絡110(例如，諸如網際網路之類 的廣域網)的 連通性。因此，設備102可使得其他設備102(例如，Wi-Fi站)能接入其他網絡 110。此外應領會，設備102中的一個或多個可以是可攜式的，或者在一些情形中為相對非 可攜式的。第二網絡接口 208可傳送和接收根據IEEE 802. 11標準(包括IEEE 802.11(a)、 (b)、或(g))、藍牙標準的RF信號、和/或CDMA、GSM、AMPS信號或用於在無線蜂窩電話網絡 中通信的其他已知信號。此外，第二網絡接口 208可包括任何合適的有線網絡接口，諸如以 太網(IEEE802. 3)、USB、或 MDDI。設備102可包括用以向設備102的一個或多個組件供電的電池231。設備102可 包括電話、智慧型電話、個人數字助理(PDA)、超級移動個人計算機(UMPC)、移動網際網路設備 (MID)、或任何其他行動裝置中的至少之一。具體而言，本文中的教示可被納入多種設備102 中(例如，實現在其中或由其執行)。本文中所描述的組件可用多種方式來實現。參考圖1，設備或裝置102被表示為一 系列互相關的功能性塊，這些功能性塊可代表由例如處理器202、軟體、其某種組合、或以如 本文中教示的其他某種方式來實現的功能。例如，處理器202可便於用戶經由輸入設備212 輸入。進一步，發射機222可包括用於傳送的處理器，該處理器提供與向另一個設備102傳 送信息有關的各種功能性。接收機220可包括用於接收的處理器，該處理器提供與如本文 中所教示地接收來自另一個設備102的信息有關的各種功能性。處理器202還與存儲器分配服務203通信。在一個實施例中，存儲器分配服務203 在處理器202上運行。存儲器分配服務203響應於來自在設備102中操作的一個或多個子 系統的對存儲器的請求。存儲器分配服務203的方法和操作將在以下更詳細地描述。如以上所注意到的，圖1圖解了在一些方面中，這些組件可經由恰適的處理器組 件來實現。這些處理器組件在一些方面中可至少部分地使用如本文中所教示的結構來實 現。在一些方面中，處理器可適於實現這些組件中的一個或多個的功能性的一部分或全部。 在一些方面中，由虛線框所表示的組件中的一個或多個是可任選的。在一個或多個示例性實施例中，所描述的功能可以在硬體、軟體、固件、或其任何 組合中實現。如果在軟體中實現，則這些功能可以作為一條或多條指令或代碼存儲在計算 機可讀介質上或在其上傳送。計算機可讀介質包括計算機存儲介質和通信介質兩者，後者 包括便於將電腦程式從一處轉移到另一處的任何介質。存儲介質可以是可被通用或專用 計算機訪問的任何可用介質。作為示例而非限定，這樣的計算機可讀介質可包括RAM、R0M、 EEPR0M、CD_R0M或其它光碟存儲、磁碟存儲或其它磁存儲設備、或可用來攜帶或存儲指令或 數據結構形式的合需程序代碼手段且能可通用或專用計算機、或者通用或專用處理器訪問 的任何其它介質。任何連接也被正當地稱為計算機可讀介質。例如，如果軟體使用同軸電 纜、光纖電纜、雙絞線、數字訂戶線(DSL)、或諸如紅外、無線電、以及微波之類的無線技術從 web網站、伺服器、或其它遠程源傳送而來，則該同軸電纜、光纖電纜、雙絞線、DSL、或諸如紅夕卜、無線電、以及微波之類的無線技術就被包括在介質的定義之中。本文中所使用的盤和碟 包括壓縮碟(CD)、雷射碟、光碟、數字多用碟(DVD)、軟盤和藍光碟，其中盤通常磁性地再現 數據，而碟用雷射來光學地再現數據。以上的組合也應被包括在計算機可讀介質的範圍之 內。根據存儲器分配服務的一方面，小存儲器塊被包裝成較大的固定大小的單元(稱 為「DSM項」)。使用「DUP」(複製)項來保持對這些較小塊中的每一者的跟蹤，DUP項指向 DSM內的有效載荷。由於DSM項的大小有限，並且可假定DSM內的所有塊具有近似的有限壽 命，因此沒有必要處理每一個DSM內的自由存儲器的碎片。這樣的益處在於存儲器利用率 可被極大地減少，因為每個DSM內 僅很少的存儲器被浪費掉，但複雜度卻是具有高包裝效 率的其他存儲器分配技術的分數。考慮這方面的另一種途徑是這是固定大小和靈活大小分 配服務的混合，其中整個存儲器按固定大小塊被分配，但在這些塊內允許靈活大小分配，因 為預期這些靈活分配具有較短的壽命。在一方面，基礎存儲器塊被稱為DSM項。其包括頭部和有效載荷部分。當有數據 塊必須被存儲在存儲器中時，分配新的DSM項並且該數據被複製到DSM的有效載荷部分中。 因此，頭部被更新以反映該數據的開始和長度。如果該數據的長度超過有效載荷部分的大 小，則多個DSM項可被連結在一起成為鍊表。進一步，定義了特殊類型的DSM項，記為DUP (「複製」)。DUP使用與常規DSM相同 的頭部結構，但沒有其自己的有效載荷部分。作為代替，其可指向其它地方的數據部分，例 如正常DSM內部的數據部分。為了跟蹤有多少DUP指向同一 DSM項中的數據，存在被記為 "ref_count (引用_計數)」的頭部欄位，其計數對該DSM項的引用的數目並且在原始DSM 首次被分配時被設為1。每次創建指向該DSM項內部的新DUP時，該DSM項的ref_COunt遞 增。同樣，當DUP被釋放時，原始DSM項的ref_COimt遞減。這樣，分配算法可知曉該DSM 項何時可實際被釋放，這僅在沒有其他DUP指向該分組的有效載荷部分時發生，即在ref_ count已變回0時發生。DUP可被用於拆分分組、重新排序數據、移除頭部等，而不必觸及原始數據。所有這 些僅通過操縱DSM和DUP頭部就能達成。根據另一方面，允許將數據包裝成相同的DSM項以提高存儲器效率的技術可解決 先前所提及的缺點中的一些。根據這方面，定義了較大DSM項的池。大DSM大小將允許來 自多個無線電鏈路分組的數據被級聯到同一 DSM項中。圖2是圖解用於存儲器分配服務的存儲器項的框圖。存儲器分配服務可包括應用 編程接口(「API」)。此API可供諸如設備102中存在的子系統之類的子系統訪問用。此 存儲器分配服務可整體或部分地由處理器202或其他類似處理設備來執行。進一步，API可 構成諸如設備102之類的移動或無線設備的作業系統的一部分。或者，API可構成軟體庫 的一部分。在圖2中，示出第一類存儲器項610。此第一類存儲器項610可被稱為數據服務 管理(「DSM」)項。或者，它可被稱為容器項。這些容器類存儲器項610被組織成存儲器項 池605。雖然圖解了單個池605，但是應領會也可以使用多個DSM項池。每個池可由諸如項 大小或該池所服務的子系統之類的一個或多個公共特性來表徵。圖2中還提供了存儲器項610的展開圖。如該展開圖中可見，這些容器類項610 包括多個部分。存儲器項的第一部分可被稱為頭部615。頭部615既可包含關於存儲器項610的其餘部分的信息，也可包含其他信息。存儲器項610的第二部分可被稱為有效載荷。 有效載荷自身可具有若干獲分配存儲器部分或塊620。此外，有效載荷可具有未分配或未 使用空間625。在一個實施例中，有效載荷包括大致1500位元組，約為存儲IP分組所需的大存儲器項610的頭部615可包括諸如對存儲器項610中未分配空間625的引用之 類的信息。在一個示例中，此引用採取指針的形式來指示存儲器項610中未分配空間625 的開始地址。對數據項610中未分配空間625的此引用也可被稱為「data_ptr (數據_指 針)」。頭部還可以包含指示已分配存儲器620的大小的欄位。此已分配空間的量可被稱為 有效載荷中的「已使用」空間。頭部還可以包含指示標識與存儲器項610相關聯的存儲器 池605的標識符的欄位。此標識符可被稱為「pool_id (池_id)」。頭部還可以包含指示對 存儲器項610的引用的數目的欄位。例如，如以下所描述的，存儲器項610可被其他存儲器 項引用。例如，有效載荷的已分配大塊620中的每一個被不同的存儲器項引用。進一步，存 儲器項610的頭部615引用有效載荷的未分配部分625。這些引用的計數尤其可用於確定 存儲器項610何時可被釋放完並返回池605中以供後續再分配。此引用計數可被稱為「引 用」。頭部615還可以包含對其他存儲器項的一個或多個引用。例如，如果所請求的存儲器 大塊太大而不適合單個存儲器項610，則頭部中的引用可被用於指示可被連結在一起以滿 足該請求的一個或多個附加存儲器項。取決於被引用的存儲器項的類型，這些引用可被稱 為「pkt_ptr (分組_指針)」或「dup_ptr」。例如，pkt_ptr可引用0個或多個DSM或容器 項，而dup_ptr可引用0個或多個DUP項。除所標識出的欄位以外，頭部615可包括諸如用 戶定義欄位或用於測試目的的欄位之類的附加欄位。此外，頭部615可省略所標識出的字 段中的一個或多個。圖2還圖解了第二類存儲器項630。此第二類存儲器項可被稱為複製或「DUP」存 儲器項。這些DUP項630包括與容器存儲器項610的頭部615相類似的頭部。例如，DUP 項可具有與DSM項頭部615相同的欄位。或者，DUP項可具有更多或更少欄位。然而，這些 DUP項不具有其自己的有效載荷。相反，DUP項頭部630包含對容器存儲器項的引用。在一 個特定示例中，DUP項630包含指示存儲器項610的已分配部分620中的第一個分配存儲 器塊的指針。這些DUP項630也可以被安排成一個或多個池640。像容器項的池605那樣， 可以使用多個DUP項池。例如，圖2圖解了兩個DUP項池640和650。在一個示例中，嵌入 式設備或無線通信設備中的每個子系統具有其自己的DUP項池。在本實施例中，池640可 對應於一個特定子系統，而池650可對應於另一個子系統。如圖2中可見的，一個實施例提 供了來自分開的諸池的DUP項可引用單個DSM項610中的存儲器塊620。圖3示出了圖2中所圖解的存儲器項的替換實施例。像之前的那樣，可使用單個 DSM項池715。然而這次，每個DUP項池730和735分別引用不同DSM項725和720的已分 配部分。如上所述，一旦對該有效載荷的全部引用都已被釋放，DSM項就可返回DSM池715 中以供再分配。然而，當允許多個子系統使DUP引用到同一 DSM項中時，可能出現碎片。例 如，特定DSM中被分配給第一子系統的所有存儲器可能已被釋放。然而，如果有小塊仍被來 自另一個子系統的DUP引用，則該有效載荷中的其餘存儲器可能在第二子系統釋放其小存 儲器塊之前都必須等待被釋放。為使此問題最小化，每個子系統可使其自己的DUP引用到 其自己的DSM中。這樣，特定DSM中已分配存儲器部分的壽命更可能相同。壽命的近似性導致碎片減少。圖4A和4B圖解用於分配存儲器的方法780的實施例。此方法780可作為在諸如 處理器202之類的處理器上運行的服務來執行。方法780便於接收存儲器分配請求以及返 回對已分配存儲器的引用。如以下所描述的，所指派的特定引用可以是請求方子系統的當 前存儲器分配境況和所請求存儲器塊的大小的函數。注意，這些步驟中的一些可被省略以 滿足特定應用的要求或規範。還應注意，本文中所描述的這些步驟中的一些是優化且由此 可按照系統設計者的決定被選擇性地使用或省略。方法780在存儲器分配服務在步驟785處接收到存儲器請求時開始。作為存儲器 請求的一部分，請求方子系統可指定所請求的存儲器大小。請求方子系統還可以提供子系 統ID以使得存儲器分配服務可為該子系統選擇恰適的DSM項。在接收到存儲器請求之後， 存儲器分配服務如判定步驟790中所示地確定所請求大小是否小於當前DSM容器項中未分 配存儲器的大小。如參照圖2和3所討論的，DSM項在有效載荷部分中可具有未分配空間。 判定步驟790可通過將未分配部分的大小與所請求大小作比較來執行。或者，由於有效載 荷的總大小是已知的，因此可以將所請求量與有效載荷的已分配部分的大小作比較。在另 一個實施例中，並非使用所請求的存儲器大小來作比較，而是存儲器分配系統可增大請求 的大小以使得擴增後的請求與高速緩存邊界對準。例如，可增大實際請求以使得結果所得 請求是諸如16、32、64、或128位元組之類的特定高速緩存行大小的倍數。無論是所請求的存 儲器大小還是擴增後的對準版本適合未分配部分，該方法都前進至步驟800。繼續到判定步驟800，存儲器分配系統確定所請求大小加上當前DSM項的先前已 分配部分的大小是否大於第一閾值。例如，如果DSM有效載荷是大致1500位元組長，則閾值 可為1200位元組。因此，存儲器分配系統將確定已分配存儲器的大小加上所請求存儲器的大 小是否超過1200位元組極限。在一個實施例中，閾值可被選為DSM項的有效載荷大小的特定 百分比。例如，閾值可為有效載荷大小的大致70%-80%。在另一個實施例中，閾值大小可 被選取成反映諸如對用以存儲IP分組的存儲器的請求之類的公共請求的大小特性。在另 一個實施例中，並非將已分配存儲器的大小與閾值作比較，而是可將剩餘未分配存儲器的 大小與閾值作比較。在本實施例中，如果分配了所請求或經調整的存儲器大小，則該服務將 計算有效載荷中將保持未分配的部分。剩餘未分配存儲器與此閾值的比較隨後將以與先前 所討論的已分配存儲器與閾值的比較類似的方式來使用。通過執行判定步驟800，如果標識出的總和大於閾值，則該方法前進至步驟805。 在步驟805處繼續，存儲器分配系統向請求方子系統返回引用。在一個實施例中，所返回的 引用是來自當前DSM項的頭部的data_ptr。有利地，通過返回來自DSM項的頭部的引用，存 儲器分配系統節省了在創建DUP項和返回來自DUP頭部的引用時所涉及的開銷和資源。進 一步，分配DSM有效載荷的剩餘部分而非僅僅所請求的大小使得存儲器分配服務能避免在 有效載荷的尾部的小塊，否則這些小塊若被使用將會導致連結。返回到判定步驟800，如果所請求存儲器大小加上已分配存儲器大小並未大於閾 值，則該方法前進至步驟810。在步驟810中，存儲器分配服務創建DUP項，分配所請求的存 儲器，並且向請求方子系統返回DUP中的引用。有利地，在多次迭代下，本方法允許存儲器 分配服務能將多個分配包裝成單個DSM項。此包裝允許存儲器資源的高效率使用並且在存 儲器使用和處理使用兩者中皆提供增益。
返回到步驟790，若所請求的存儲器大小大於當前DSM項中的未分配空間，則該方 法繼續到圖4B的判定步驟845。在判定步驟845中，存儲器分配服務確定所請求大小是否 大於第二閾值。此第二閾值像第一閾值一樣可被設為固定數目的字節。例如，如果DSM項 有效載荷的大小為1600位元組，則第二閾值可為1200位元組。或者，第二閾值也可為被確定為 有效載荷大小的百分比。例如，第二閾值可為有效載荷大小的65%-75%。在另一實施例 中，該閾值可被動態地確定。例如，該閾值可被設為等於DSM項中已分配存儲器的總量。在 本實施例中，當所請求大小超過DSM中的已分配空間時，所請求大小將超過該閾值。不管如 何確定該閾值，如果所請求大小大於此閾值，則存儲器分配服務就將如步驟850中所示地 分配新DSM項並且向請求方子系統返回來自新DSM項頭部的data_ptr。類似於步驟805， 返回來自新DSM項的頭部的引用的此過程節省了創建新DUP項的開銷。請求方子系統被給 予多於其要求的——即整個DSM項，並且此分配允許後續分配請求能用當前DSM項中剩餘 的未分配存儲器來滿足。返回到步驟845，如果所請求大小小於此第二閾值，則該方法前進至步驟855。在 步驟855中，刪除對DSM有效載荷的未分配部分的DSM項頭部引用。實際上，這釋放完DSM 項中的剩餘部分。此外，創建新DSM項。分配該新DSM項中的存儲器塊並且創建相應的DUP。 新DUP中對新DSM項的引用隨後被返回給請求方子系統。出於解釋目的，在圖5中圖解了前述方法的示例。在情形1中，圖解了當前DSM項 910。當前DSM具有已分配部分915和未分配部分920。所請求分組大小925被示為在第一 閾值930中。如圖所示，已分配部分915的大小加上所請求部分925的大小小於第一閾值 930。因此，如圖所示，DSM項935的大塊被分配，以及新DUP項被創建且其引用被返回給調 用方子系統。該新DUP項包括指向新分配數據的開始的對DSM 935中的引用。在情形2中，聯合另一個所請求分組960示出當前DSM 955。如圖所示，DSM955 的已分配部分的大小加上所請求分組的大小超過第一閾值，但總和並未超過總有效載荷長 度。因此，對DSM項965的未分配部分的引用被返回給請求方子系統。結果是除了獲得所 請求存儲器大小或甚至是稍大的經調整行分配之外，請求方子系統將獲得DSM 965中的所 有剩餘未分配空間980。再次，返回來自DSM項頭部的引用節省了創建DUP的開銷並且消除 了否則將會留下的殘端980所創建的連結可能性。在情形3中，與另一個所請求存儲器塊990 —起示出當前DSM 985。如圖所示，所 請求分組太大而不適合當前DSM的未分配部分。此外，所請求大小小於第二閾值995。因 此，刪除當前DSM 1000的頭部中對有效載荷的未分配部分的引用。創建新DSM 1005。分配 來自該DSM的存儲器塊並且創建引用該新DSM中獲分配塊的新DUP項。來自該新DUP項的 引用隨後被返回給請求方子系統。再次將領會，雖然第二閾值995被示為靜態的，但該閾值 可諸如通過將其設為等於初始已分配存儲器的大小來動態地確定。在情形4中，連同所請求存儲器塊1015—起示出當前DSM 1010。如同情形3那 樣，所請求大小太大而不適合當前DSM項1010的未分配部分。此外，所請求塊大小1015大 於第二閾值995。結果是當前DSM 1020被保留在其當前狀態。同時，創建新DSM 1025並且 返回該新DSM頭部中對有效載荷的未分配部分的引用。圖6類似於圖4A和4B中所圖解的方法。然而，圖6提供相對於用於分配存儲器 的服務的一個實施例中所使用的特定參數的變型。圖6中所圖解的方法1080為存儲器分配請求提供API。在一個特定實施例中，方法1080為子系統提供可用於請求存儲器分配的 函數調用。如圖所示，該函數可以採取所請求的存儲器分配大小作為參數。此外，該函數可 採取諸如標識請求方子系統的子系統ID之類的其他參數。圖6所代表的服務可被配置成 在諸如設備102的處理器202之類的處理器上運行。響應於分配請求，該服務如以下所討 論地準備指向大小大於或等於所請求大小的獲分配存儲器塊的指針。因此，使用該服務的 API的子系統被返回指向獲分配存儲器的指針。在一個特定實施例中，圖6中所圖解的方法 在其操作期間使用以下值中的一些或全部current_dsm_item_ptr[](當前_(1細_項_指針[])這是每個子系統的指向當前 DSM項的指針集。aligned_pkt_size (經對準_分組_大小)這是所請求的存儲器塊的大小，其被 調整成與諸如16、32、64、或128之類的大小的高速緩存行對準。pkt_ptr (分組_指針)即將被返回的指向獲分配存儲器的指針。DSMI_MEM_THRESHOLD_TO_FREE_DSM (DSMI_ 存儲器 _ 閾值 _ 用以-釋放 _DSM)用 於確定應返回DUP還是DSM引用的第一閾值。如果在分配存儲器塊之後，剩餘未分配存儲 器將小於此閾值，則返回DSM引用，從而有效地分配該DSM項中的所有剩餘未分配存儲器。DSMI_THRESH0LD_F0R_C0MPLETE_ITEM_ALL0CATI0N (DSMI_ 閾值 _ 用以-完整 _ 項 _分配)用於確定應返回DUP還是DSM引用的第二閾值。如果所請求分組大小大於此閾 值，則創建新DSM項並返回來自新DSM的頭部的引用。當前DSM被保留。圖6中所圖解的方法始於1085處所示的函數調用。作為該請求的參數，分配服務 接收所請求的分組大小「pkt_size」。此外，在一些實施例中，還將向函數調用傳遞另一個參 數，即子系統ID。前進至步驟1100，該方法鎖定特定DSM項池以避免並發訪問問題。在鎖 定池之後，該方法前進到判定步驟1105。在判定步驟1105處，該服務確定pkt_ptr是否為 空。如果針對該請求尚未分配存儲器，則該指針可為空。然而，如果該指針具有非空值，則 服務前進至解鎖池(1140)並返回指針(1145)。然而，如果指針為空，則服務前進至判定步 驟 1110。在判定步驟1110處繼續，服務確定Current_dSm_item_ptr是否為空。如果先前 迭代已導致不存在當前DSM項，則服務前進至創建一個DSM項(1115)，並且若這樣的創建失 敗則退出(1120、1140、1145)。一旦確認存在或創建了有效的當前DSM，該方法前進至判定 步驟1125。在判定步驟1125處，服務確定經對準的所請求大小是否小於當前DSM中未分配 空間的大小。如果是，則服務隨後在步驟1130處確定DSM中在分配所請求存儲器之後將剩 餘的未分配空間是否小於第一閾值。若如此，則服務創建DUP並且在當前DSM中分配經對 準的所請求存儲器(1135)，解鎖池(1140)，並返回DUP指針(1145)。若否，則服務創建全新 的DSM(1150)，解鎖池(1140)，並返回來自該新DSM的頭部的指針(1145)返回到步驟1125，如果所請求大小大於剩餘未分配空間，則該方法前進至判定步 驟1155。在步驟1155處，該服務確定所請求大小是否大於或等於第二閾值。若如此，則服 務創建全新的DSM(1165)，解鎖池(1140)，並返回來自該新DSM的頭部的指針(1145)若否， 則該服務釋放當前DSM中的剩餘存儲器並前進至在步驟1105處再次開始該方法。結果是 新DSM被創建，引用該新DSM的主體的DUP被創建，並且DUP指針被返回給請求方子系統。本存儲器分配服務的附加特徵和實施例也在本文中呈現
用於不同用戶的多DSM指針為了處置其中期望數據塊的壽命對於不同用戶實質地不同的情形，該算法可維護 多個DSM指針，並且僅將具有近似壽命的數據塊包裝成相同的DSM。例如，用戶專用ID可連 同分配請求一起被傳遞，以使得僅來自此用戶的數據將會被包裝成相同的DSM項。來自其 他用戶的請求將會被包裝成其他DSM。此處，「用戶」可以是用以將一組用戶簡檔與其他的 區別開來的一組任務或子任務或層或函數，或這些的任何其他組合。支持在DSM的前部(或後部)添加數據為了高效率地處置在現有DSM或DUP項的前部中添加數據(即，添加協議頭部) 而不必分配新DSM項和執行連結，建議允許分配在前部中具有自由空間的DSM。通過「偏移 量」頭部來保持對該自由空間的跟蹤。這樣，DUP或DSM可被分配給定偏移量，並且以後若 有更多數據需要被插入DSM的前部中，這可以不進行新DSM分配及隨後的連結就能完成。可 允許用於在DSM的尾部中添加數據的類似服務。多個池該服務允許多個DSM池，從而允許為特定用戶預留給定數目的項。這樣，該用戶將 不必擔憂因為另一個用戶已分配到全部DSM項而突然沒有更多自由DSM項。另外，這提供 了更好的存儲器超支問題(其中一個用戶超馳分配的邊界)的調試能力，因為該問題被局 限在僅此用戶的代碼庫中。作為多個池的替換方案的配額服務達成相同目的的另一種途徑是具有一個池，但每個用戶具有他可分配的DSM項的 最大配額(字節)。一旦他已達到其配額，他為了分配新項就必須釋放一些項，以避免其他 用戶的存儲器匱乏。其勝於多池辦法的一項益處在於仍可達成共享。例如，如果有4個用 戶，其自己的池為X項，則可能需要存儲器有4X項。然而由於極不可能所有4個用戶將同 時分配所有項，因此配額服務可允許將總存儲器減少到比方說3X，假定如果一個用戶取得 其所有存儲器=X，則其餘3個用戶將能夠共享剩餘存儲器=2X。用於不同大小的多DSM指針在這方面，可基於所請求的存儲器空間來劃分DSM分配(與使用以上的子系統ID 相反)。本提議並非使用跨多個層/子系統共享的多種大小的池的常規途徑來滿足所有任 務/側面的需要，而是可存在支持多個DSM指針的規定，根據該規定每個DSM指針可分配僅 特定大小的塊。例如，我們可具有用於128、256、512、768、1024、1536位元組塊大小等的05皿 指針。每當任何層/模塊請求特定大小的存儲器時，算法可確定最合適的DSM指針並在 所請求的大小可用的情況下提供dup。如果所請求大小不可用，則釋放該大小的DSM指針 (若非空)並分配來自較大項的全局池的較大項(例如，大於預定字節數目的項，在一個示 例中為大於或等於768位元組的項)，以及隨後複製(DUP)該最合適塊大小並將該DUP返回給
調用者。本分配還具有勝於現有技術的若干截然不同的優點。本服務的實施例減少了存儲 器佔用量。較少池的使用允許更好的統計復用。該服務助益更好的包裝效率。DSM項即使 帶有用於DUP的增添開銷也具有更少的開銷。CPU處理開銷(MIPS)因較少的連結而被減 少。該服務允許使用較大的DSM項來避免長分組鏈(尤其是有較大分組大小時)，從而減少DSM分配/釋放操作的次數。各實施例簡化了與涉及多個存儲器池的更常規辦法相關聯的 維護。該服務可被實現為具有用於進行處置的中央API，這避免了每子系統必須實現這樣的 功能性，從而避免了複製代碼。避免了每目標對單獨的池大小和項大小的需要。在沒有本 文中所勾勒的技術的情況下，任何人可能需要在許多地方(例如，諸如分組服務模塊(PS)、 高速USB(HS-USB)模塊等堆棧中的各種或多個層)分開實現代碼，這更傾向於出錯等。可 例如通過在低等待時間存儲器(例如，內部隨機存取存儲器(IRAM))中定義DUP池來在高 速存儲器中定義DUP池以進一步改進性能(例如，有益於高速緩存)。若此應用編程接口 (API)僅使用一個池，則可獲得DSM檢查的減少。當前DSM基於作為參數來傳遞的池ID (標 識)執行一些檢查。
權利要求
一種存儲器管理系統，包括處理器；以及可在所述處理器上執行的存儲器管理服務，所述存儲器管理服務可配置成生成第一存儲器項，其中所述第一存儲器項中的每一者包括頭部和有效載荷，所述有效載荷可配置成存儲多個可獨立分配的存儲器大塊，所述第一存儲器項的所述頭部引用所述有效載荷中的可分配空間；生成第二存儲器項，其中所述第二存儲器項中的每一者包括引用所述第一存儲器項的所述有效載荷中的一個或多個存儲器大塊的頭部；以及響應於存儲器分配請求返回來自或者第一或者第二存儲器項的所述頭部的引用。
2.如權利要求1所述的存儲器管理系統，其特徵在於，所述第一存儲器項的所述頭部 維持對所述第一存儲器項的引用的計數。
3.如權利要求1所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成為多個子系統中的每一個生成單獨的第一存儲器項。
4.如權利要求1所述的存儲器管理系統，其特徵在於，所述存儲器分配請求包括所請 求存儲器大小。
5.如權利要求4所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成確定特定第一存儲器項的有效載荷中已分配存儲器的大小與所述所請求存儲器大 小的總和，並且將所述總和與閾值作比較。
6.如權利要求5所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成當所述總和小於所述閾值時生成特定第二存儲器項並返回來自所述特定第二存儲 器項的頭部的引用。
7.如權利要求6所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成在所述總和大於所述閾值時返回來自所述特定第一存儲器項的所述頭部的引用。
8.如權利要求4所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成確定特定第一存儲器項的有效載荷中已分配存儲器的大小與所述所請求存儲器大 小的總和，將所述總和與所述特定第一存儲器項的所述有效載荷的大小作比較，以及將所 述所請求存儲器大小與閾值作比較。
9.如權利要求8所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成在所述總和大於所述特定第一存儲器項的所述有效載荷的所述大小並且所述所請 求存儲器大小小於所述閾值時生成另一個特定第一存儲器項，生成引用所述另一個特定第 一存儲器項的有效載荷的特定第二存儲器項，並返回來自所述特定第二存儲器項的頭部的 引用。
10.如權利要求8所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步 配置成在所述總和大於所述特定第一存儲器項的所述有效載荷的所述大小並且所述所請 求存儲器大小大於所述閾值時生成另一個特定第一存儲器項，並返回來自所述另一個特定 第一存儲器項的頭部的引用。
11.如權利要求8所述的存儲器管理系統，其特徵在於，所述閾值是所述特定第一存儲 器項中已分配存儲器的大小。
12.如權利要求4所述的存儲器管理系統，其特徵在於，所述存儲器管理服務可進一步配置成增大所述所請求存儲器大小以使所述所請求存儲器大小與高速緩存線邊界對準。
13.一種存儲器管理方法，所述方法包括分配第一存儲器項，所述第一存儲器項各自包括第一頭部和有效載荷，所述有效載荷 包括可獨立分配的存儲器大塊，所述第一頭部包括對所述有效載荷中未分配存儲器的引 用；分配第二存儲器項，所述第二存儲器項各自包括第二頭部，所述第二頭部包括對第一 存儲器項的所述有效載荷中獲分配存儲器大塊的引用； 接收對存儲器分配的請求；以及通過返回來自第一或者第二存儲器項的所述頭部的引用來響應對存儲器分配的請求。
14.如權利要求13所述的方法，其特徵在於，所述第一頭部還包括對所述第一存儲器 項的引用的計數。
15.如權利要求13所述的方法，其特徵在於，所述分配第一存儲器項進一步包括為多 個子系統中的每一個分配單獨的第一存儲器項。
16.如權利要求13所述的方法，其特徵在於，所述存儲器分配請求包括所請求存儲器大小。
17.如權利要求16所述的方法，其特徵在於，還包括確定特定第一存儲器項的有效載 荷中已分配存儲器的大小與所述所請求存儲器大小的總和，並且將所述總和與閾值作比較。
18.如權利要求17所述的方法，其特徵在於，還包括在所述總和小於所述閾值時分配 特定第二存儲器項並返回來自所述特定第二存儲器項的頭部的引用。
19.如權利要求18所述的方法，其特徵在於，還包括在所述總和大於所述閾值時返回 來自所述特定第一存儲器項的所述頭部的引用。
20.如權利要求16所述的方法，其特徵在於，還包括確定特定第一存儲器項的有效載荷中已分配存儲器的大小與所述所請求存儲器大小 的總和；將所述總和與所述特定第一存儲器項的所述有效載荷的大小作比較；以及 將所述所請求存儲器大小與閾值作比較。
21.如權利要求20所述的方法，其特徵在於，還包括 生成另一個特定第一存儲器項；生成引用所述另一個特定第一存儲器項的有效載荷的特定第二存儲器項；以及 當所述總和大於所述特定第一存儲器項的所述有效載荷的所述大小並且所述所請求 存儲器大小小於所述閾值時返回來自所述特定第二存儲器項的頭部的引用。
22.如權利要求20所述的方法，其特徵在於，還包括 生成另一個特定第一存儲器項；以及當所述總和大於所述特定第一存儲器項的所述有效載荷的所述大小並且所述所請求 存儲器大小大於所述閾值時返回來自所述另一個特定第一存儲器項的頭部的引用。
23.如權利要求20所述的方法，其特徵在於，所述閾值是所述特定第一存儲器項中已 分配存儲器的大小。
24.如權利要求16所述的方法，其特徵在於，還包括增大所述所請求存儲器大小以使所述所請求存儲器大小與高速緩存線邊界對準。
25.一種存儲器管理系統，包括用於分配第一存儲器項的裝置，所述第一存儲器項各自包括第一頭部和有效載荷，所 述有效載荷包括可獨立分配的存儲器大塊，所述第一頭部包括對所述有效載荷中未分配存 儲器的引用；用於分配第二存儲器項的裝置，所述第二存儲器項各自包括第二頭部，所述第二頭部 包括對第一存儲器項的所述有效載荷中獲分配存儲器大塊的引用；用於接收對存儲器分配的請求的裝置；以及 用於通過返回來自第一或者第二存儲器項的所述頭部的引用來響應對存儲器分配的 請求的裝置。
26.—種編碼有計算機指令的計算機可讀介質，所述指令在被執行時使得處理器分配第一存儲器項，所述第一存儲器項各自包括第一頭部和有效載荷，所述有效載荷 包括可獨立分配的存儲器大塊，所述第一頭部包括對所述有效載荷中未分配存儲器的引 用；分配第二存儲器項，所述第二存儲器項各自包括第二頭部，所述第二頭部包括對第一 存儲器項的所述有效載荷中獲分配存儲器大塊的引用；接收對存儲器分配的請求；以及通過返回來自第一或者第二存儲器項的所述頭部的引用來響應對存儲器分配的請求。
全文摘要
嵌入式或無線設備中用於改進的存儲器分配服務的系統和方法。使用容器存儲器項的組合併引用存儲器項來分配存儲器。
文檔編號H04L12/56GK101971581SQ200980109315
公開日2011年2月9日 申請日期2009年4月2日 優先權日2008年4月2日
發明者S·馬赫施瓦瑞, T·克林根伯恩, V·A·庫瑪 申請人:高通股份有限公司