Distributed data cache with memory allocation model

• US 6,453,404 B1
• Filed: 05/27/1999
• Issued: 09/17/2002
• Est. Priority Date: 05/27/1999
• Status: Expired due to Term

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Katariya, Sanjeev, Bereznyi, Alexandre
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/321,300
• Time in Patent Office: 1,209 Days
• Field of Search: 711/170, 711/171, 711/172, 711/173, 711/129, 711/119, 711/130, 709/104
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

A cache system allocates memory for storage of data items by defining a series of small blocks that are uniform in size. The system allocates one or more blocks from memory and assigns them for storage of a data item. If the data item exceeds the predetermined block size, more blocks are assigned for storage. If a residual portion of the data item less than the predetermined the block size remains, the operating system may allocate an additional small storage block to store the residual portion of the data item. The operating system allocates a large number of small blocks with a plurality of blocks having different sizes where a first plurality of blocks has one block size and a second plurality of blocks has a different block size. The large number of blocks allocated by the operating system avoid contention from multiple users requesting access to the data cache. The predetermined blocks are allocated by the data cache software itself and are not allocated by the operating system. In an exemplary embodiment, the blocks allocated by the data cache software need not be contiguous within the memory. Rather, each block contains a pointer to the start of the next block for a particular data item and the last block of the predetermined size blocks contains a pointer to the residual portion. A status list contains data indicating whether the particular blocks are free or used. When allocating blocks for storage of a data item, the system will use the status list to determine which blocks are free. The status list is updated to indicate the blocks have been allocated when a data item is stored within the cache. When a data item is removed from the cache, the status list is again updated to indicate that the availability of the blocks.

Claims

1. A memory allocation system for data caching comprising:

a computer platform containing a computer software operating system capable of memory allocation;

a memory associated with the computer platform to store data; and

a cache controller associated with the memory to allocate memory portions independently of the operating system for storage of data, the cache controller receiving a first allocation request to allocate a first amount of memory to store a first data item and allocating one or more blocks of the memory, each having a predetermined block size, wherein the memory allocated in the one or more blocks of memory is approximately equal to the first amount of memory, the cache controller requesting a memory allocation from the operating system if the amount of memory allocated in the one or more blocks of memory is smaller than the first amount of memory, wherein the total memory allocated in the one or more blocks of memory and allocated by the operating system is sufficient to meet the first allocation request.

2. The system of claim 1 wherein the size of the operating system memory allocation is smaller than the predetermined block size for each of the allocated blocks of memory.

3. The system of claim 1 wherein the predetermined block sizes for each of the allocated blocks of memory are equal.

4. The system of claim 1 wherein the predetermined block sizes for each of the allocated blocks of memory are each smaller than one Kbyte.

5. The system of claim 1 wherein the memory portions comprise a plurality of blocks and the predetermined block size for all of the plurality of blocks of memory are equal in size.

6. The system of claim 1 wherein each of the allocated blocks of memory consists of a contiguous portion of the memory.

7. The system of claim 1 wherein at least some of the allocated blocks of memory are stored discontinuously in the memory.

8. The system of claim 1 wherein a first of the allocated blocks of memory includes a link to a second subsequent allocated block of memory.

9. The system of claim 8 wherein the cache controller retrieves the first data item from the allocated blocks of memory using the link to the second subsequent allocated block of memory.

10. The system of claim 1, further comprising a status indicator for each of the blocks of memory to indicate whether each block of memory is allocated or is free and available for allocation, the cache controller using the status indicator to select the one or more blocks of memory from blocks of memory indicated as free and available for allocation.

11. The system of claim 1 wherein the operating system allocates a plurality of portions of memory smaller than the predetermined sizes.

12. The system of claim 1 wherein the operating system allocates a plurality of sets of memory portions smaller than the predetermined sizes with a first set of memory portions having a first uniform size and a second set of memory portions having a second uniform size different from the first uniform size.

13. A computer-readable media containing computer instructions that cause a computer containing a computer software operating system capable of memory allocation to:

designate a portion of a memory associated with the computer platform to store data;

receive a first allocation request for a first amount of the memory to store a first data item;

allocate one or more blocks of the memory independently of the operating system, each having a predetermined block size, wherein the memory allocated in the one or more blocks of memory is approximately equal to the first amount of memory; and

request a memory allocation from the operating system if the amount of memory allocated in the one or more blocks of memory is smaller than the first amount of memory wherein the total memory allocated in the one or more blocks of memory and allocated by the operating system is sufficient to meet the first allocation request.

14. The computer-readable media of claim 13, further containing computer instructions to delete the first data item from the memory, thereby rendering the one or more blocks of memory allocated in response to the first allocation request available for allocation in response to another allocation request.

15. The computer-readable media of claim 13 wherein the size of the operating system memory allocation is smaller than the predetermined block size for each of the allocated blocks of memory.

16. The computer-readable media of claim 13 wherein the predetermined block sizes for each of the allocated blocks of memory are equal.

17. The computer-readable media of claim 13 wherein the predetermined block sizes for each of the allocated blocks of memory are each smaller than one Kbyte.

18. The computer-readable media of claim 13 wherein at least some of the allocated blocks of memory are stored discontiguously in the memory.

19. The computer-readable media of claim 13 wherein a first of the allocated blocks of memory includes a link to a second subsequent allocated block of memory.

20. The computer-readable media of claim 19, further comprising computer instructions that cause the computer to retrieve the first data item from the allocated memory blocks using the link to the second subsequent allocated block of memory.

21. The computer-readable media of claim 13, further comprising computer instructions that cause the computer to use a status indicator for each of the blocks of memory to indicate whether each block of memory is allocated or is free and available for allocation and using the status indicator to select the one or more blocks of memory from blocks of memory indicated as free and available for allocation.

22. The computer-readable media of claim 13 wherein the operating system allocates a plurality of portions of memory smaller than the predetermined sizes, the computer-readable media containing computer instructions to request a memory allocation from the operating system.

23. The computer-readable media of claim 13 wherein the operating system allocates a plurality of sets of memory portions smaller than the predetermined sizes with a first set of memory portions having a first uniform size and a second set of memory portions having a second uniform size different from the first uniform size, the computer-readable media containing computer instructions to request a memory allocation from the operating system to allocate one or more of the sets of memory portions.

24. The computer-readable media of claim 13 wherein the computer-readable media further contains computer instructions to:

receive a second allocation request for a second amount of the memory to store a second data item;

allocate one or more unallocated blocks of the memory independently of the operating system, each having a predetermined block size, wherein the memory allocated in the one or more blocks of memory is approximately equal to the second amount of memory; and

request a memory allocation from the operating system if the memory allocated in the one or more blocks of memory is smaller than the second amount of memory, wherein the total memory allocated in the one or more blocks of memory and allocated by the operating system is sufficient to meet the second allocation request.

25. The computer-readable media of claim 13, further comprising computer instructions to delete the first data item from the memory, thereby rendering the one or more blocks of memory allocated in response to the first allocation request available for allocation in response to another allocation request whereby further allocation acts may allocate the one or more blocks allocated for the first allocation request.

26. A method of allocating memory in a computer containing a computer software operating system capable of memory allocation, the method comprising:

designating a portion of a memory associated with the computer platform to store data;

receiving a first allocation request for a first amount of the memory to store a first data item;

allocating one or more blocks of the memory independently of the operating system, each having a predetermined block size, wherein the memory allocated in the one or more blocks of memory is approximately equal to the first amount of memory; and

requesting a memory allocation from the operating system if the memory allocated in the one or more blocks of memory is smaller than the first amount of memory, wherein the total memory allocated in the one or more blocks of memory and allocated by the operating system is sufficient to meet the first allocation request.

27. The method of claim 26 wherein the operating system memory allocation is smaller than the predetermined block sizes for each of the allocated blocks of memory.

28. The method of claim 26 wherein the predetermined block sizes for each of the allocated blocks of memory are equal.

29. The method of claim 26 wherein the predetermined block sizes for each of the allocated blocks of memory are each smaller than one Kbyte.

30. The method of claim 26 wherein at least some of the allocated blocks of memory are stored discontiguously in the memory.

31. The method of claim 26 wherein a first of the allocated blocks of memory includes a link to a second subsequent allocated block of memory.

32. The method of claim 31, further comprising retrieving the first data item from the allocated memory blocks using the link to the second subsequent allocated block of memory.

33. The method of claim 26, further comprising using a status indicator for each of the blocks of memory to indicate whether each block of memory is allocated or is free and available for allocation and using the status indicator to select the one or more blocks of memory from blocks of memory indicated as free and available for allocation.

34. The method of claim 26 wherein the operating system allocates a plurality of portions of memory smaller than the predetermined sizes, and wherein said act of requesting a memory allocation from the operating system comprises requesting an allocation of a first one of the memory portions less than the predetermined sizes.

35. The method of claim 26 wherein the operating system allocates a plurality of sets of memory portions smaller than the predetermined sizes with a first set of memory portions having a first uniform size and a second set of memory portions having a second uniform size different from the first uniform size, the method further comprising requesting a memory allocation from the operating system to allocate one or more of the sets of memory portions.

36. A computer-readable medium having computer-executable instructions to perform a method of operating a computer, the computer having a memory, the computer further having an operating system that performs at least the function of allocating portions of the memory, the method comprising:

receiving a request for memory;

allocating one or more blocks of memory without requesting memory from the operating system, each of the blocks having a predetermined block size, said one or more blocks containing a first amount of memory;

determining that said first amount of memory is insufficient to meet said request; and

issuing a call to the operating system to allocate a second amount of memory, said first and second amounts of memory together being sufficient to meet said first request.

37. The computer-readable medium of claim 36, wherein said second amount of memory is smaller than the predetermined block size for each of said one or more blocks.

38. The computer-readable medium of claim 36, wherein said act of allocating one or more blocks comprises allocating blocks of equal sizes.

39. The computer-readable medium of claim 36, wherein each of said one or more blocks is associated with a status indicator which indicates whether each of the blocks is free or available, and wherein the method further comprises:

examining the status indicators associated with said one or more blocks to determine that said one or more blocks are free.