# US 2014/0195761 A1 · Logical volume space sharing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195761 A1 - Document ID: US20140195761A1 - Status: Published application - Kind: A1 - Application number: 13/737,929 - Filed: 2013-01-09 - Published: 2014-07-10 - Earliest claimed: 2013-01-09 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Deric S. HORN; David A. MAJNEMER; Wenguang WANG - Web page: https://patentgrep.com/patent/US20140195761A1 ## CPC - G06F 3/0631: {by allocating resources to storage systems} - G06F 3/0607: {by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device} - G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools} - G06F 3/0683: {Plurality of storage devices} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Space sharing between logical volumes is achieved through a technique that enables available storage space to be flexibly consumed and released by the logical volumes. Each logical volume is associated with an address tree that defines how available storage space is consumed by the logical volume. The technique involves receiving an input/output (I/O) operation that specifies a logical address within an address tree associated with the logical volume, parsing the address tree to identify an entry therein, if any, that is associated with the logical address, where the entry stores physical address information that is associated with the logical address. If it is determined that the entry exists, then one or more translated I/O operations are generated based on the physical address information and forwarded to a physical device manager to carry out the translated one or more I/O operations. ## Claims ### Claim 1 A computer-implemented method for carrying out an input/output (I/O) operation issued to a logical volume, comprising: receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume; parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and if the entry exists: generating one or more translated I/O operations based on the physical address information; and forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations. ### Claim 2 (depends on 1) The method of claim 1, further comprising: if the entry does not exist, and the I/O operation specifies a read request: returning zero-filled data. ### Claim 3 (depends on 1) The method of claim 1, further comprising: if the entry does not exist, and the I/O operation specifies a write request: issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation; receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks; generating one or more entries within the address tree that is associated with the logical address; storing the generated physical address information in the one or more generated entries; translating the I/O operation into one or more write operations based on the generated physical address information; and forwarding the write operations to the physical device manager to carry out the write operations. ### Claim 4 (depends on 1) The method of claim 1, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises: generating one or more delete operations based on parameters of the trim request as well as the physical address information; and forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations. ### Claim 5 (depends on 4) The method of claim 4, further comprising: determining that the trim request invalidates the entry in the address tree; and replacing the entry with generated one or more new entries that reflect effects of the trim request. ### Claim 6 (depends on 1) The method of claim 1, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size. ### Claim 7 (depends on 1) The method of claim 1, wherein the address tree is implemented using a B-Tree or a log-structured merge (LSM) tree. ### Claim 8 A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to implement a method for carrying out an input/output (I/O) operation issued to a logical volume, the method comprising: receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume; parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and if the entry exists: generating one or more translated I/O operations based on the physical address information; and forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations. ### Claim 9 (depends on 8) The non-transitory computer-readable storage medium of claim 8, further comprising: if the entry does not exist, and the I/O operation specifies a read request: returning zero-filled data. ### Claim 10 (depends on 8) The non-transitory computer-readable storage medium of claim 8, further comprising: if the entry does not exist, and the I/O operation specifies a write request: issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation; receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks; generating one or more entries within the address tree that is associated with the logical address; storing the generated physical address information in the one or more generated entries; translating the I/O operation into one or more write operations based on the generated physical address information; and forwarding the write operations to the physical device manager to carry out the write operations. ### Claim 11 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises: generating one or more delete operations based on parameters of the trim request as well as the physical address information; and forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations. ### Claim 12 (depends on 11) The non-transitory computer-readable storage medium of claim 11, further comprising: determining that the trim request invalidates the entry in the address tree; and replacing the entry with generated one or more new entries that reflect effects of the trim request. ### Claim 13 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size. ### Claim 14 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the address tree is implemented using a B-Tree or a log-structured merge (LSM) tree. ### Claim 15 A system, comprising: one or more storage devices; and a processor, configured to implement a method for carrying out an input/output (I/O) operation issued to a logical volume, the method comprising: receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume; parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and if the entry exists: generating one or more translated I/O operations based on the physical address information; and forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations. ### Claim 16 (depends on 15) The system of claim 15, further comprising: if the entry does not exist, and the I/O operation specifies a read request: returning zero-filled data. ### Claim 17 (depends on 15) The system of claim 15, further comprising: if the entry does not exist, and the I/O operation specifies a write request: issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation; receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks; generating one or more entries within the address tree that is associated with the logical address; storing the generated physical address information in the one or more generated entries; translating the I/O operation into one or more write operations based on the generated physical address information; and forwarding the write operations to the physical device manager to carry out the write operations. ### Claim 18 (depends on 15) The system of claim 15, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises: generating one or more delete operations based on parameters of the trim request as well as the physical address information; and forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations. ### Claim 19 (depends on 18) The system of claim 18, further comprising: determining that the trim request invalidates the entry in the address tree; and replacing the entry with generated one or more new entries that reflect effects of the trim request. ### Claim 20 (depends on 15) The system of claim 15, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size.