# US 8,788,749 B2 · Implementing enhanced deterministic memory allocation for indirection tables for persistent media > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,749 B2 - Document ID: US8788749B2 - Status: Granted - Kind: B2 - Application number: 13/207,740 - Filed: 2011-08-11 - Published: 2012-11-29 - Granted: 2014-07-22 - Earliest claimed: 2011-05-23 - Assignees: HGST Netherlands B.V. - Applicants: David Robison Hall - Inventors: David Robison Hall - Web page: https://patentgrep.com/patent/US8788749B2 ## CPC - G11B 5/012: Recording on, or reproducing or erasing from, magnetic disks (G11B17/00, G11B19/00 take precedence) - G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R) ## Abstract A method and a storage system are provided for implementing deterministic memory allocation for indirection tables for persistent media or disk drives, such as, shingled perpendicular magnetic recording (SMR) indirection tables. A plurality of fixed-size memory pools are used to store indirection data. The distribution of pool allocate sizes is fixed. A pool allocate size is selected based upon an indirection system request size. ## Claims ### Claim 1 A method for implementing deterministic memory allocation for indirection tables for persistent media comprising: using a plurality of fixed-size memory pools to store indirection data; a distribution of pool allocate sizes being fixed; initializing each of the plurality of fixed-size memory pools with a head pointer and a plurality of next pointers, each next pointer using a first word for building each free allocation in each respective fixed-size memory pool, and selecting a pool allocate size using an index to the plurality of fixed-size memory pools based upon an indirection system request size and the fixed distribution of pool allocate sizes for the plurality of fixed-size memory pools. ### Claim 2 (depends on 1) The method as recited in claim 1 wherein the persistent media includes a Shingled Disk Drive. ### Claim 3 (depends on 1) The method as recited in claim 1 wherein using a plurality of fixed-size memory pools to store indirection data includes providing indirection tables memory allocation control logic coupled to a controller to control storing of the indirection data. ### Claim 4 (depends on 1) The method as recited in claim 1 wherein using a plurality of fixed-size memory pools to store indirection data includes providing the head pointer to identify a memory pool target address. ### Claim 5 (depends on 4) The method as recited in claim 4 includes providing the next pointers using the first word of each free allocation. ### Claim 6 (depends on 1) The method as recited in claim 1 wherein selecting a pool allocate size based upon an indirection system request size includes providing a pool manager for returning an allocation using the index for the distribution of pool allocate sizes. ### Claim 7 (depends on 6) The method as recited in claim 6 includes identifying the index equal to said request size divided by an allocation value. ### Claim 8 (depends on 6) The method as recited in claim 6 includes using the index for the distribution of pool allocate sizes includes identifying the index and using direct addressing for returning the allocation. ### Claim 9 (depends on 6) The method as recited in claim 6 wherein using the index for the distribution of pool allocate sizes includes identifying an index and using indirect addressing for returning the allocation, with an entry equal to a biggest allocation divided by an allocation granularity. ### Claim 10 (depends on 1) The method as recited in claim 1 wherein using a plurality of fixed-size memory pools to store indirection data further includes using one of said fixed-size memory pools to define a plurality of mini-pools with predefined bytes used as a chain pointer between the plurality of mini-pools. ### Claim 11 An apparatus for implementing deterministic memory allocation for indirection tables for persistent media comprising: a plurality of fixed-size memory pools for storing indirection data; a distribution of pool allocate sizes being fixed; each of the plurality of fixed-size memory pools being initialized with a head pointer and a plurality of next pointers, each next pointer using a first word for building each free allocation in each respective fixed-size memory pool, and a pool manager selecting a pool allocate size using an index to the plurality of fixed-size memory pools based upon an indirection system request size and the fixed distribution of pool allocate sizes for the plurality of fixed-size memory pools. ### Claim 12 (depends on 11) The apparatus as recited in claim 11 wherein the persistent media includes a Shingled Disk Drive. ### Claim 13 (depends on 11) The apparatus as recited in claim 11 includes a controller, and indirection tables memory allocation control logic coupled to said controller to control storing of the indirection data in said plurality of fixed-size memory pools. ### Claim 14 (depends on 13) The apparatus as recited in claim 13 wherein said indirection tables memory allocation control logic coupled to said controller to control storing of the indirection data includes said indirection tables memory allocation control logic providing the head pointer to identify a memory pool target address of each of said plurality of fixed-size memory pools. ### Claim 15 (depends on 14) The apparatus as recited in claim 14 includes said indirection tables memory allocation control logic providing the next pointers using the first word of each free allocation of each of said plurality of fixed-size memory pools. ### Claim 16 (depends on 11) The apparatus as recited in claim 11 wherein said pool manager selecting a pool allocate size based upon an indirection system request size returns an allocation using the index for the distribution of pool allocate sizes. ### Claim 17 (depends on 16) The apparatus as recited in claim 16 wherein said pool manager identifies the index equal to said request size divided by an allocation value. ### Claim 18 A data storage system comprising: a persistent media; a controller, and indirection tables memory allocation control logic coupled to said controller for implementing deterministic memory allocation for indirection tables; said controller and indirection tables memory allocation control logic using a plurality of fixed-size memory pools for storing indirection data; a distribution of pool allocate sizes being fixed; each of the plurality of fixed-size memory pools being initialized with a head pointer and a plurality of next pointers, each next pointer using a first word for building each free allocation in each respective fixed-size memory pool; and a pool manager selecting a pool allocate size using an index to the plurality of fixed-size memory pools based upon an indirection system request size and the fixed distribution of pool allocate sizes for the plurality of fixed-size memory pools. ### Claim 19 (depends on 18) The data storage system as recited in claim 18 wherein said controller and SMR indirection tables memory allocation control logic using a plurality of fixed-size memory pools for storing indirection data includes said controller and indirection tables memory allocation control logic providing the head pointer to identify a memory pool target address and providing the next pointers using the first word of each free allocation of each of said plurality of fixed-size memory pools. ### Claim 20 (depends on 18) The data storage system as recited in claim 18 wherein pool manager selecting a pool allocate size based upon an indirection system request size returns an allocation using the index for the distribution of pool allocate sizes; said index equal to said request size divided by an allocation value.