Method for dynamically and efficiently caching objects by subdividing cache memory blocks into equally-sized sub-blocks

• US 6,016,535 A
• Filed: 10/11/1995
• Issued: 01/18/2000
• Est. Priority Date: 10/11/1995
• Status: Expired due to Term

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Luu, Thanh, Krantz, Jeffrey Isaac, Bloomfield, Marc Alan
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US08/541,128
• Time in Patent Office: 1,560 Days
• Field of Search: 395/497.4, 395/497.3, 395/497.2, 395/456, 395/463, 711/129, 711/136, 711/170, 711/171, 711/172, 711/173, 711/209, 711/206, 711/207, 711/160
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack

Abstract

A method for dynamically caching data objects in a logical cache memory begins by organizing the logical cache memory into a set of maximally equally-sized, contiguous pages that begin at a logical cache base address. Any one of the maximal size logical cache pages may be dynamically subdivided into a set of smaller pages of equal size. The smaller size pages cache data objects having a smaller size than the maximum possible data object size. Each subdivided page stores only those smaller size data objects. The logical address for a page is mapped to at least a maximal size page index identifying the position of the maximal size logical page in the cache and, if the page is a smaller size page, the page location is also mapped to a smaller size page index which identifies a particular one of the smaller size pages located within a maximal size page. Pages are dynamically reconfigured based on a least-recently-used policy. A maximal size page may be reconfigured to provide for storage of multiple smaller sized pages and a set of smaller sized pages may be reconfigured to provide storage for a maximal size page. In one aspect, maximally sized pages may be chained together to provide for storage of data objects which exceed the size of the pages. Chained pages may be contiguous or non-contiguous.

Claims

1. In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of:

(a) receiving a data object to be cached having a size smaller than the maximal size;

(b) determining whether one of a plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object;

(c) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal logical cache memory pages; and

(d) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.

2. The method of claim 1 wherein step (a) comprises:

(a-a) receiving a data object to be cached, having a size smaller than the maximal size; and

(a-b) assigning the data object a quantized size by rounding the size of the received data object up to a predetermined quanta.

3. The method of claim 1 wherein step (a) comprises:

(a-a) receiving a data object to be cached; and

(a-b) assigning the data object a quantized size selected from the set consisting of 128 bytes, 512 bytes, and 2 kilobytes, wherein the quantized size is assigned by rounding the size of the received data object up to the next predetermined size.

4. The method of claim 1 wherein step (a) comprises receiving a graphical user interface data object to be cached the object having a size smaller than the maximal size.

5. The method of claim 1 wherein step (b) comprises determining more than one of a plurality of logical cache memory pages that is configured to store data objects having the smaller size of the received data object.

6. The method of claim 1 wherein step (c) comprises selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of a plurality of logical cache memory pages on least recently used (LRU) basis.

7. The method of claim 2 wherein step (d) comprises subdividing the selected cache page into a plurality of equally-sized smaller pages, each equally-sized smaller page configured to store data objects of the quantized size and identified as storing data objects of the quantized size.

8. The method of claim 7, further comprising the step of mapping a logical address for the data object relative to the logical cache base memory address by:

(i) mapping a logical address for the data object to a maximal-size page index corresponding to the page location of the maximal-size logical cache memory page relative to the logical cache memory base address; and

(ii) mapping the logical address for the data object to a smaller page index that describes which of the plurality of smaller pages is being addressed within the maximal-size page designated by the maximal-size page index.

9. The method of claim 8 further comprising the step of generating a logical address for the data object by forming a product of the maximal-size page index of the maximal-size page that contains the data object and a value corresponding to the maximum number of objects of the smaller size that can be contained within the maximal-size page, forming a sum of the product and the smaller page index, and multiplying the sum by the quantized size of the data object.

10. The method of claim 8, further comprising the step of providing the mapped logical address for the data object as a single handle.

11. In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of:

(a) receiving a data object to be cached having a size greater than the maximal size;

(b) subdividing the data object into first and second data chunks;

(c) assigning a first chunk index to the first data chunk and a second chunk index to the second data chunk, each index representing the maximal-size page in which the respective data chunk is stored; and

(d) storing the second chunk index at a location in a control store that corresponds to the first chunk index for use in identifying the location of the second data chunk.

12. The method of claim 11 wherein step (d) comprises storing the second chunk index at a location in a control store that corresponds to the first chunk index for use in identifying the location of the first and second data chunks.

13. The method of claim 11 further comprising the steps of:

(e) accessing the control store using the first page index corresponding to the first chunk index;

(f) recovering an index stored in the control store starting at a location corresponding to the first chunk index; and

(g) reading a maximal-size logical cache page corresponding to the first chunk index.

14. A method for efficiently caching data objects in a logical cache memory including a plurality of maximal-size pages beginning at a logical base memory address, the logical cache memory using prescribed portions of a plurality of heterogeneous physical memory units for storage of data, the method comprising:

(a) labeling each of the plurality of physical memory units with a unique rank index, the rank index indicative of the relative memory speed of the physical memory unit;

(b) allocating a portion of each physical memory unit for use by the logical cache memory;

(c) forming a continuous, addressable logical address space for the logical cache memory that encompasses the allocated portions of the physical memory units by ordering the allocated portions of the physical memory units based on the rank indices the logical cache memory beginning at a logical cache memory base address, each maximal-size page configured to store data objects of a maximal size and identified as storing data objects of a maximal-size,

(d) receiving a data object to be cached having a size smaller than the maximal size;

(e) determining whether one of the plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object;

(f) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal-size logical cache memory pages; and

(g) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.

15. The method of claim 14 wherein step (d) comprises:

(d-a) receiving a data object to be cached having a size smaller than the maximal-size; and

(d-b) assigning the data object a quantized size by rounding the size of the received data object up to a predetermined quanta.

16. The method of claim 14 wherein step (d) comprises:

(d-a) receiving a data object to be cached; and

(d-b) assigning the data object a quantized size selected from the set consisting of 128 bytes, 512 bytes and 2 kilobytes;

wherein the quantized size is assigned by rounding the size of the reviewed data object up to the next predetermined size.

17. The method of claim 14 wherein step (d) comprises receiving a graphical user interface data object to be cached, the object having a size smaller than the maximal size.

18. The method of claim 14 wherein step (e) comprises determining more than one of a plurality of logical cache memory pages that is configured to store data objects having the smaller size of the received data object.

19. The method of claim 14 wherein step (f) comprises selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the logical cache memory pages for reconfiguring on a least recently used (LRU) basis.

20. The method of claim 15 wherein step (g) comprises subdividing the selected cache page into a plurality of equally-sized smaller pages, each equally-sized smaller page configured to store data objects of the quantized size and identified as storing data objects of the quantized size.

21. The method of claim 20, further comprising the step of mapping a logical address for the data object relative to the logical cache base memory address by:

(i) mapping a logical address for the data object to a maximal-size page index corresponding to the page location of the maximal-size logical cache memory page relative to the logical cache memory base address; and

(ii) mapping the logical address for the data object to a smaller page index that describes which of the plurality of smaller pages is being addressed within the maximal-size page designated by the maximal-size page index.

22. The method of claim 21 further comprising the step of generating a logical address for the data object by forming a product of the maximal-size page index of the maximal-size page that contains the data object and a value corresponding to the maximum number of objects of the smaller size that can be contained within the maximal-size page, forming a sum of the product and the smaller page index, and multiplying the sum by the quantized size of the data object.

23. The method of claim 21, further comprising the step of providing the mapped logical address for the data object as a single handle.