Managing a region cache

A system or computer usable program product for managing a cache region including receiving a new region to be stored within the cache, the cache including multiple regions defined by one or more ranges having a starting index and an ending index, and storing the new region in the cache in accordance with a cache invariant, the cache invariant ensuring that regions in the cache are not overlapping and that the regions are stored in a specified order.

BACKGROUND

1. Technical Field

The present invention relates generally to managing computer data, and in particular, to a computer implemented method and system for efficiently managing a region cache.

2. Description of Related Art

Many computing environments utilize a variety of techniques for managing the storage and distribution of data. Often this data may be transparently stored in a portion of memory referred to as a cache for future high speed access. There are many kinds of caches that are useful in a variety of situations.

One type of cache is a region cache. A region cache is a software structure that resides in memory and includes one or more regions of data, each region having a starting index and an ending index. A region cache may be stored anywhere in memory accessible by the software that manages or uses the region cache. A region cache may be implemented, managed or used by an operating system, a web browser, an application, or any other type of software.

SUMMARY

The illustrative embodiments provide a system and computer usable program product for managing a cache region including receiving a new region to be stored within the cache, the cache including multiple regions defined by one or more ranges having a starting index and an ending index, and storing the new region in the cache in accordance with a cache invariant, the cache invariant ensuring that regions in the cache are not overlapping and that the regions are stored in a specified order.

DETAILED DESCRIPTION

Steps may be taken to efficiently manage a region cache. These steps may be taken as will be explained with reference to the various embodiments below.

FIG. 1is a block diagram of a data processing system in which various embodiments may be implemented. Data processing system100is only one example of a suitable data processing system and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein. Regardless, data processing system100is capable of being implemented and/or performing any of the functionality set forth herein.

As shown inFIG. 1, computer system/server112in data processing system100is shown in the form of a general-purpose computing device. The components of computer system/server112may include, but are not limited to, one or more processors or processing units116, a system memory128, and a bus118that couples various system components including system memory128to processor116.

Computer system/server112typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server112, and it includes both volatile and non-volatile media, removable and non-removable media.

Memory128may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the invention. Memory128may also include data that will be processed by a program product. This data may be organized in a variety of ways to allow efficient storage, management and retrieval of that data by one or more software applications, whether local or remote to the data processing system. One example would be a software cache such as a region cache to provide efficient access to data to multiple software applications. Such a region cache may be managed by an application also stored in memory referred to herein as a region cache manager.

Program/utility140, having a set (at least one) of program modules142, may be stored in memory128by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules142generally carry out the functions and/or methodologies of embodiments of the invention.

Computer system/server112may also communicate with one or more external devices114such as a keyboard, a pointing device, a display124, etc.; one or more devices that enable a user to interact with computer system/server112; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server112to communicate with one or more other computing devices. Such communication can occur via I/O interfaces122. Still yet, computer system/server112can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter120. As depicted, network adapter120communicates with the other components of computer system/server112via bus118. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server112. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

FIG. 2is a block diagram of a network of data processing systems in which various embodiments may be implemented. Data processing environment200is a network of data processing systems such as described above with reference toFIG. 1. Software applications may execute on any computer or other type of data processing system in data processing environment200. Data processing environment200includes network210. Network210is the medium used to provide communications links between various devices and computers connected together within data processing environment200. Network210may include connections such as wire, wireless communication links, or fiber optic cables.

Server220and client240are coupled to network210along with storage unit230. In addition, laptop250and facility280(such as a home or business) are coupled to network210including wirelessly such as through a network router253. A mobile phone260may be coupled to network210through a mobile phone tower262. Data processing systems, such as server120, client140, laptop150, mobile phone160and facility180contain data and have software applications including software tools executing thereon. Other types of data processing systems such as personal digital assistants (PDAs), smartphones, tablets and netbooks may be coupled to network210.

Server220may include software application224such as for storing, managing or accessing data such as in a region cache. Storage230may contain software application234and a content source such as a region cache236for storing data accessible by a variety of applications across processing environment200. Application224may serve as the region cache manager for region cache236. Region cache236is shown in an enlarged view237. The region cache includes multiple regions, each region including a starting index and an ending index. These indexes may represent memory addresses or other types of data depending on the use of the region cache. Additional information may also be stored in the region cache including additional information about each region.

Other software and content may be stored on storage230for sharing among various computer or other data processing devices. Client240may include software application244and region cache246. Laptop250and mobile phone260may also include software applications254and264and region caches256and266. Facility280may include software application284and region cache286. Other types of data processing systems coupled to network210may also include software applications and region caches. Any of these software applications may serve as a region cache manager for any other region cache depending on security and access requirements. In addition, any of these software applications may access any other region cache depending on security and access requirements. Software applications could include a web browser, email, or other software application that can process sensor and maintenance information of an environmental control unit or other type of information to be processed. Region caches could be in any location in memory or distributed across multiple locations within data processing environment200. Depending on security requirements and interfacing capabilities, region caches may also be accessible by software applications across data processing environment200.

Server220, storage unit230, client240, laptop250, mobile phone260, and facility280and other data processing devices may couple to network210using wired connections, wireless communication protocols, or other suitable data connectivity. Client240may be, for example, a personal computer or a network computer.

In the depicted example, server220may provide data, such as boot files, operating system images, and applications to client240and laptop250. Client240and laptop250may be clients to server220in this example. Client240, laptop250, mobile phone260and facility280or some combination thereof, may include their own data, boot files, operating system images, and applications. Data processing environment200may include additional servers, clients, and other devices that are not shown.

Among other uses, data processing environment200may be used for implementing a client server environment in which the embodiments may be implemented. A client server environment enables software applications and data to be distributed across a network such that an application functions by using the interactivity between a client data processing system and a server data processing system. Data processing environment100may also employ a service oriented architecture where interoperable software components distributed across a network may be packaged together as coherent business applications.

FIGS. 3A and 3Billustrate inserting a region into a region cache in which various embodiments may be implemented. This region caching model can be used in any dimensional space. For the sake of simplicity, the following description relates to a one dimensional space. However, this is only an example and the present invention is not so limited.

A region cache is utilized for memory registration. It is not used as a form of memory allocation in the embodiments described herein, although it could be used to implement a form of memory allocation. That is, it is a bookkeeping of the registration state of the memory regions, whether previously registered or not. Inserting a new region onto existing regions will not cause a memory violation. For example, remote direct memory access (RDMA) can be directly performed on user buffers without intervention of the operating system. RDMA requires pinning and registration of user buffers to hardware prior to a data transfer to prevent the physical memory from being swapped out. If any portion of the user buffer being accessed by RDMA has not been previously registered, then that portion of the user buffer needs to be registered by modifying the region entry into the region cache.

In these embodiments, a cache invariant is enforced where no region overlaps another region at any time. That is, no region has a starting index value less than the starting index of another region and an ending index greater than or equal to the starting index of the other region. In addition, the cache invariant is enforced where no region should be contiguous to another region. That is, no region should have a starting index that is only one address higher than the ending index of another region. In such a case, the contiguous regions should be coalesced into a single region. The cache invariant may also be enforced where all regions in the region cache are stored in a specified order. This may be by starting index of each region or by ending index of each region. This cache invariant provides for certain efficiencies when the indexes of a request region are checked against the indexes of the cache regions. An example of this usage would be memory registration on a host fabric interface (HFI) in anticipation of a remote direct memory access (RDMA).

FIG. 3Aillustrates an existing set of regions300and a region to be inserted305. The existing regions include R1with starting index of A1and an ending index of A3(e.g. R1(A1, A3)), region R2(A4, A5), region R3(A6, A7) and region R4(A8and A9). The region to be inserted includes region R5(A2, A9). As described above, overlapping regions are not allowed in accordance with the cache invariant. First R5is split into chunks310in two categories. The first set of chunks includes those that overlap existing regions (C1, C3, C5and C7). As these chunks are already in existing regions, they do not have to be processed as they have already been registered. The second set of chunks includes those that do not overlap existing regions (C2, C4and C6), referred to herein as gaps. As those are not in existing regions, they will need to be processed. The result of that processing would pre-coalesced regions R1, C2, R2, C4, R3, C6and R4. Once processed, then all contiguous regions would need to be coalesced, resulting in region315shown as R6.

FIG. 3Billustrates an existing set of regions350and a region to be inserted355. The existing regions include R11(A11, A12), R12(A13, A14), R13(A16, A17) and R14(A19, A20). The region to be inserted includes R14(A15, A18). These regions could be in the same region cache shown inFIG. 3A. First R14is split into chunks360in two categories. The first set of chunks includes those that overlap existing regions (C12). As these chunks are already in existing regions, they do not have to be processed. The second set of chunks includes those that do not overlap existing regions (C11and C13) referred to herein as gaps. As this chunk is not in an existing region, it will need to be processed. The result of that processing would pre-coalesced regions R11, R12, C11, R13, C13and R14. Once processed, then all contiguous regions would need to be coalesced, resulting in regions370shown as R11, R12, R15and R14.

If the cache invariant was not enforced in the above two examples, then then there may be more regions than shown. For example, if the regions were allowed to overlap or adjoin each other, then R2ofFIG. 3Amay be composed of multiple overlapping regions. As a result, inserting R5may involve comparing the range of that region against more preexisting regions than currently shown inFIG. 3A, thereby requiring more processing time.

FIG. 4is a flowchart of inserting a new region into a region cache in accordance with a first embodiment. In a first step400the region cache manager receives a request to insert a new region into the region cache. This request may be received from a software application that is local or across a network. The request should include a starting index and an ending index of the requested region to be inserted. In step410, the region cache manager performs a binary search on the current region cache to find the position of insertion. In this embodiment, the current regions are sorted by starting index, so the binary search is performed using that starting index. Alternative embodiments may use alternative types of searches or the regions may be sorted by ending index. If sorted by ending index, then steps410and430may be reversed so that the ending index of the current region cache is searched first.

The binary search does not search for an exact match, but returns results based on criteria and assumptions that are guaranteed by the cache invariant. The binary search takes the starting index of the region to be inserted as input, and returns a position. More specifically, in this one dimensional case, the regions are sorted by the starting index in increasing order in the cache, and the binary search returns the position of the region whose starting index is greatest but smaller than the starting index of the region to be inserted. In an embodiment where the binary search is on the ending index of the region to be inserted, the binary search returns the region whose index is smallest but greater than the ending index of the region to be inserted. Because the region cache manager ensures that the cache invariant holds true, the cache is guaranteed to be free of regions that are entirely contained within another region. Therefore, the simple binary search criteria always return positive results, even though an exact match is not always returned.

Based on the binary search results, the position of insertion is determined in step420. However, if the starting index of the region being inserted is less than the starting index of the identified current region (i.e. there is no current region with a lower starting index), then the starting index of the region being inserted is used as the starting insertion index. This starting position for insertion is referred to herein as the first marked position. In the above described examples, the result of this initial search would be A1of region R1in the example ofFIG. 3Aand A13of region R12in the example ofFIG. 3B.

The region cache manager then performs a second binary search on the ending index of the new region in step430. In step440, the region cache manager determines the last region in the cache that is at least partially contained within the region to be inserted. In this example, the search returns the ending index of a current region in the cache with the greatest starting index that is smaller than the ending index of the new region requested to be inserted. However, if the ending index of the region being inserted is greater than the ending index of the identified current region, then the ending index of the region being inserted is used as the ending insertion index. This ending index for insertion is referred to herein as the second marked position. In the above described examples, the result of this second search would be A10of region R4in the example ofFIG. 3Aand A17of region R12in the example ofFIG. 3B.

In step450, the area between the first marking position and the second marking position is scanned linearly to identify gaps within that are not currently occupied by existing regions. In the above described examples, the result of this identification would be C2, C4and C5in the example ofFIG. 3Aand C11and C12in the example ofFIG. 3B. These gaps are processed in step460to register those gaps. The type of processing or registration would depend on the use of the region cache. For example, if the region cache is used for RDMA data transfers, the registration would be for pinning memory to prevent the physical memory from being swapped out. Areas already occupied by existing regions do not need to be processed because those areas are already registered. This processing of gaps results in the new region being inserted into the region cache, albeit piecemeal.

Finally, in step470, a coalescing operation is performed as shown in eitherFIG. 5Aor5B. This removes all continuous regions and reduces the number of regions to be searched in additional region insertion operations or future cache lookup operations.

FIG. 5is a flowchart of coalescing regions that do not meet the cache invariant into a single region in which various embodiments may be implemented. This reduces the number of regions in the region cache and reduces the amount of searching needed to look up or insert a region. In a first step500the region cache manager receives a request for coalescing regions in the cache. This request may be an internal call from the region cache manager such as at the end of an insertion process. The request may include a range to search including the starting index and the ending index as described above with reference toFIG. 4. In this example, the regions in the cache are sorted by the starting index of each region, as shown in the examples ofFIGS. 3A and 3Babove.

The region cache manager then performs binary searches in step505using the starting index and the ending index to identify the starting of the first potential region to be combined and the ending index of the last potential region to be combined. In the above described examples, the result of this identification would be R1and R4in the example ofFIG. 3Aand R12and C13in the example ofFIG. 3B. The region cache manager then identifies the adjoin regions to be combined in step510. In the above described examples, the result of this identification would be R1, C2, R2, C4, R3, C6and R4in the example ofFIG. 3Aand C11, R13and C13in the example ofFIG. 3B. The region cache manager then combines these adjoining regions in step515. Alternative methods of coalescing regions may be used including a full linear scan of the region cache for adjoining regions.

FIG. 6is a flowchart of performing a lookup operation in which various embodiments may be implemented. This lookup operation assumes a cache invariant is in effect whereby no regions are overlapping or continuous to each other. In a first step600the region cache manager receives a request for a cache lookup. This request may be received from a software application that is local or across a network. In this example, the regions in the cache are sorted by the starting index of each region, as shown in the examples ofFIGS. 3A and 3Bdescribed above.

In step605, the region cache manager then searches the region cache for the position of the region corresponding to the request using a binary search, as explained above. In step610, the requested region is returned. Because the cache invariant is guaranteed, a single lookup using the binary search described above yields the region of interest. Also, because the regions are sorted by starting index, the search returns the position of the region with a starting index that is closest to the starting index of the request, but still smaller than the starting index of the request.

The region cache manager then determines if the returned region can contain the requested region in step615. If the result of this determination is positive, then in step620the region cache manager determines that a cache hit occurred. Subsequently, in step625, the region cache manager returns the requested region to the requesting application. If the result of the determination in step615is negative, then the region cache manager determines that a cache miss has occurred in step630. The region cache manager then notifies the requesting application of the cache miss in step635. Next, the region cache manager will receive an allocation request from the requesting application in step640. The region cache manager then stores this resource into the region cache as a region using the insertion operation described above with reference toFIG. 4.

FIG. 7is a flowchart of inserting a new region into a region cache in accordance with a second embodiment. In a first step700the region cache manager receives a request to insert a new region into the region cache. This request may be received from a software application that is local or across a network. The request should include a starting index and an ending index of the requested region to be inserted. In step710, the region cache manager performs a binary search on the current region cache to find the position of insertion. In this embodiment, the current regions are sorted by starting index, so the binary search is performed using that starting index. Alternative embodiments may use alternative types of searches or the regions may be sorted by ending index. If sorted by ending index, then steps710and730may be reversed so that the ending index of the current region cache is searched first.

The binary search does not search for an exact match, but returns results based on criteria and assumptions that are guaranteed by the cache invariant. The binary search takes the starting index of the region to be inserted as input, and returns a position. More specifically, in this one dimensional case, the regions are sorted by the starting index in increasing order in the cache, and the binary search returns the position of the region whose starting index is greatest but smaller than the starting index of the region to be inserted. In an embodiment where the binary search is on the ending index of the region to be inserted, the binary search returns the region whose index is smallest but greater than the ending index of the region to be inserted. Because the region cache manager ensures that the cache invariant holds true, the cache is guaranteed to be free of regions that are entirely contained within another region. Therefore, the simple binary search criteria always return positive results, even though an exact match is not always returned.

Based on the binary search results, the position of insertion is determined in step720. However, if the starting index of the region being inserted is less than the starting index of the identified current region (i.e. there is no current region with a lower starting index), then the starting index of the region being inserted is used as the starting insertion index. This starting position for insertion is referred to herein as the first marked position. In the above described examples, the result of this initial search would be A1of region R1in the example ofFIG. 3Aand A13of region R12in the example ofFIG. 3B.

The region cache manager then performs a second binary search on the ending index of the new region in step730. In step740, the region cache manager determines the last region in the cache that is at least partially contained within the region to be inserted. In this example, the search returns the ending index of a current region in the cache with the greatest starting index that is smaller than the ending index of the new region requested to be inserted. However, if the ending index of the region being inserted is greater than the ending index of the identified current region, then the ending index of the region being inserted is used as the ending insertion index. This ending index for insertion is referred to herein as the second marked position. In the above described examples, the result of this second search would be A10of region R4in the example ofFIG. 3Aand A17of region R12in the example ofFIG. 3B.

In step750, the area between the first marking position and the second marking position is scanned linearly to identify a first gap not currently occupied by existing regions. In the above described examples, the result of this identification would be C2in the example ofFIG. 3Aand C11in the example ofFIG. 3B. This gap is then processed in step760to register that gap. The type of processing or registration would depend on the use of the region cache. For example, if the region cache is used for RDMA data transfers, the registration would be for pinning memory to prevent the physical memory from being swapped out. Areas already occupied by existing regions do not need to be processed because those areas are already registered. This processing of gaps results in the new region being inserted into the region cache, albeit piecemeal. In step770, a coalescing operation is performed as shown in eitherFIG. 5Aor5B to coalesce the processed gap region with the prior current region(s) if they are adjoining. This can be up to two prior regions to be coalesced with the processed gap if this is the second or third gap to be processed for the region being inserted. This removes the gap as a separate region and reduces the number of regions to be searched in additional region insertion operations or future cache lookup operations.

In step780, the area between the first marking position and the second marking position is continued to be scanned linearly to identify another gap not currently occupied by existing regions. If no further gap is found them processing can cease for this region insertion. If a gap is found, then processing can continue to step760described above.

Although the above embodiments illustrate managing a one dimensional region caching model, region caches with two or more dimensions may be similarly managed with the same cache invariant.

The invention can take the form of an entirely software embodiment, or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software or program code, which includes but is not limited to firmware, resident software, and microcode.

Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing. Further, a computer storage medium may contain or store a computer-readable program code such that when the computer-readable program code is executed on a computer, the execution of this computer-readable program code causes the computer to transmit another computer-readable program code over a communications link. This communications link may use a medium that is, for example without limitation, physical or wireless.

A data processing system may act as a server data processing system or a client data processing system. Server and client data processing systems may include data storage media that are computer usable, such as being computer readable. A data storage medium associated with a server data processing system may contain computer usable code such as a region cache manager. A client data processing system may download that computer usable code, such as for storing on a data storage medium associated with the client data processing system, or for using in the client data processing system. The server data processing system may similarly upload computer usable code from the client data processing system such as a content source. The computer usable code resulting from a computer usable program product embodiment of the illustrative embodiments may be uploaded or downloaded using server and client data processing systems in this manner.