Easily coalesced, sub-allocating, hierarchical, multi-bit bitmap-based memory manager

• US 6,640,290 B1
• Filed: 11/28/2000
• Issued: 10/28/2003
• Est. Priority Date: 02/09/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Helander, Johannes, Forin, Alessandro
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US09/724,704
• Time in Patent Office: 1,064 Days
• Field of Search: 711/156, 711/170, 711/172, 711/171, 711/144, 711/145, 710/56, 707/205, 707/206
• US Class Current: 711/156
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A hierarchical bitmap-based memory manager maintains a hierarchical bitmap having an entry for each memory block in a memory heap. Each bitmap entry contains a multi-bit value that represents an allocation state of the corresponding memory block. The memory manager manages allocation, deallocation, and reallocation of the memory blocks, and tracks the changes in allocation state via the hierarchical bitmap. Using a-two-bit value, the bitmap can represent at most four different allocation states of the corresponding memory block, including a “free” state, a “sub-allocated” state in which the corresponding memory block is itself an allocated set of smaller memory blocks, a “continue” state in which the corresponding memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “last” state in which the corresponding memory block is allocated and last in an allocation of one or more memory blocks.

Claims

1. A core memory management system for multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the core memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation.

2. A core memory management system as recited in claim 1, wherein the manager, in response to a change in allocation state of a particular core memory block, is configured to change the multi-bit value in the hierarchical bitmap that corresponds to the particular core memory block to reflect the change in allocation state of the particular core memory block.

3. A core memory management system as recited in claim 1, wherein the individual bitmap entries contain two-bit values to represent at most four different allocation states of the corresponding core memory block.

4. A core memory management system as recited in claim 1, wherein the hierarchical bitmap comprises multiple partial bitmaps that are distributed throughout the multiple core memory blocks.

5. A core memory management system as recited in claim 1, wherein the hierarchical bitmap comprises multiple partial bitmaps that describe allocation states of corresponding sets of plural core memory blocks.

6. A core memory management system as recited in claim 1, wherein the manager, in response to a request to allocate one or more free core memory blocks in the multiple core memory blocks, is configured to scan the hierarchical bitmap for one or more bitmap entries having a multi-bit value that indicates the corresponding core memory block is free for allocation.

7. A core memory management system as recited in claim 1, wherein the manager is configured to deallocate a particular core memory block by changing the corresponding bitmap entry in the hierarchical bitmap from a multi-bit value indicating that the particular core memory block is allocated to a multi-bit value indicating that the particular core memory block is free.

8. A core memory management system as recited in claim 1, wherein the manager is configured to consider adjoining core memory blocks, which are indicated by multi-bit values in the corresponding bitmap entries as free, as a coalesced grouping of core memory blocks that are free for joint allocation.

9. A core memory management system as recited in claim 1, wherein the manager is configured to enlarge a particular allocation of core memory blocks by examining a bitmap entry in the hierarchical bitmap for a next core memory block following the core memory blocks in the particular allocation, the core memory manager determining that enlargement is possible if the bitmap entry has a multi-bit value indicating that next core memory block is free.

10. A core memory management system as recited in claim 1, wherein the manager is configured to reduce a particular allocation of core memory blocks by changing the bitmap entry for a core memory block in the particular allocation from a multi-bit value indicating that the core memory block is allocated to a multi-bit value indicating that the core memory block is free.

11. A core memory management system for multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the core memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block; and

a manager to manage the core memory blocks via the hierarchical bitmap;

wherein the individual bitmap entries contain two-bit values to represent at least three different allocation states, the three allocation states including a “

free”

state in which the corresponding core memory block is not allocated, a “

continue”

state in which the corresponding memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “

last”

state in which the corresponding core memory block is allocated and last in an allocation of one or more core memory blocks.

12. A core memory management system for multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the core memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block; and

a manager to manage the core memory blocks via the hierarchical bitmap;

wherein the individual bitmap entries contain two-bit values to represent four different allocation states, the allocation states including a “

free”

state in which the corresponding core memory block is not allocated, a “

sub-allocated”

state in which the corresponding core memory block is itself an allocated set of smaller core memory blocks, a “

continue”

state in which the corresponding core memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “

last”

state in which the corresponding core memory block is allocated and last in an allocation of one or more core memory blocks.

13. A computer-readable medium storing an operating system comprising a core memory management system for multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the core memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and further configured to allocate contiguous memory blocks for an allocation.

14. A computer-readable medium storing an application program comprising a core memory management system for multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the core memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and further configured to allocate contiguous memory blocks for an allocation.

15. A hierarchical bitmap memory manager for managing multiple core memory blocks, core memory being directly addressable by a central processing unit (CPU) of a computer, the hierarchical bitmap memory manager is configured to maintain a hierarchical bitmap with entries for directly corresponding ones of the core memory blocks, the hierarchical bitmap memory manager being configured to allocate different size core memory blocks by sub-allocating a single core memory block of one size into multiple smaller size blocks, the memory manager tracking the smaller size blocks with the hierarchical bitmap by having one entry designate the sub-allocated core memory block and additional entries for each of the smaller size blocks.

16. A hierarchical bitmap memory manager as recited in claim 15, wherein the individual bitmap entries have two-bit values, in which one of the two-bit values identifies the single core memory block as being sub-allocated.

17. A computer-readable medium storing an operating system comprising a hierarchical bitmap memory manager for managing multiple core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the hierarchical bitmap memory manager is configured to maintain a hierarchical bitmap with entries for directly corresponding ones of the core memory blocks, the hierarchical bitmap memory manager being configured to allocate different size core memory blocks by sub-allocating a single core memory block of one size into multiple smaller size blocks, the memory manager tracking the smaller size blocks with the hierarchical bitmap by having one entry designate the sub-allocated core memory block and additional entries for each of the smaller size blocks.

18. An operating system embodied on a computer-readable medium, the operating system comprising a hierarchical bitmap memory manager for managing plural core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory manager being configured to allocate contiguous memory blocks for an allocation and to maintain a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block.

19. An operating system as recited in claim 18, wherein the hierarchical bitmap comprises multiple partial bitmaps that are distributed throughout the multiple core memory blocks.

20. An operating system as recited in claim 18, wherein the hierarchical bitmap comprises multiple partial bitmaps that describe allocation states of corresponding sets of plural core memory blocks.

21. An operating system embodied on a computer-readable medium, the operating system comprising a hierarchical bitmap memory manager configured to manage plural core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory manager maintaining a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block;

wherein the individual bitmap entries contain two-bit values to represent at least three different allocation states, the three allocation states including a “

free”

state in which the corresponding core memory block is not allocated, a “

continue”

state in which the corresponding core memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “

last”

state in which the corresponding core memory block is allocated and last in an allocation of one or more core memory blocks.

22. An operating system embodied on a computer-readable medium, the operating system comprising a hierarchical bitmap memory manager being configured to manage plural core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory manager maintaining a hierarchical bitmap having entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block;

wherein the individual bitmap entries contain two-bit values to represent four different allocation states, the allocation states including a “

free”

state in which the corresponding core memory block is not allocated, a “

sub-allocated”

state in which the corresponding core memory block is itself an allocated set of smaller core memory blocks, a “

continue”

state in which the corresponding core memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “

last”

state in which the corresponding core memory block is allocated and last in an allocation of one or more core memory blocks.

23. A hierarchical bitmap data structure embodied on a computer-readable medium for use with a memory manager that manages core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the manager being configured to allocate contiguous memory blocks for an allocation, the hierarchical bitmap data structure comprising a plurality of entries for directly corresponding ones of the core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block.

24. A hierarchical bitmap data structure as recited in claim 23, wherein the individual bitmap entries contain two-bit values to represent at most four different allocation states of the corresponding core memory block.

25. A hierarchical bitmap data structure as recited in claim 23, wherein the bitmap entries are distributed throughout the core memory blocks.

26. A hierarchical bitmap data structure as recited in claim 23, wherein the bitmap entries are stored in selected ones of the core memory blocks.

27. A hierarchical bitmap data structure embodied on a computer-readable medium for use with a memory manager that manages core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the manager being configured to allocate contiguous memory blocks for an allocation, the hierarchical bitmap data structure comprising multiple partial bitmaps that is describe allocation states of directly corresponding sets of plural core memory blocks.

28. A method for managing core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, comprising the following steps:

allocating contiguous memory blocks for an allocation;

associating entries in a bitmap with the directly corresponding core memory blocks, individual bitmap entries containing a multi-bit value; and

tracking allocation states of the core memory blocks by changing the multi-bit value in the bitmap entries.

29. A method as recited in claim 28, further comprising the following steps:

changing the allocation state of a particular core memory block; and

changing a multi-bit value in a particular bitmap entry that corresponds to the particular core memory block to reflect the change in allocation state of the particular core memory block.

30. A method as recited in claim 28, wherein adjoining free core memory blocks are automatically coalesced.

31. A method as recited in claim 28, wherein the individual bitmap entries contain two-bit values, and the tracking step comprises the step of tracking at most four different allocation states of the corresponding core memory block.

32. A method as recited in claim 28, further comprising the step of distributing the bitmap entries throughout the core memory blocks.

33. A method as recited in claim 28, further comprising the step of storing the bitmap entries in ones of the core memory blocks.

34. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 28.

35. In a system for managing core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block, a method for allocating free core memory blocks comprising the following steps:

scanning the hierarchical bitmap to locate contiguous bitmap entries where each have a multi-bit value that indicates their corresponding contiguous core memory block is free for allocation;

allocating the contiguous core memory blocks corresponding to the located contiguous bitmap entries; and

changing the multi-bit values of the located bitmap entries to indicate that the corresponding core memory blocks are no longer free.

36. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 35.

37. In a system for managing core memory blocks in a memory using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block, a method for deallocating a core memory block comprising the following steps:

receiving a pointer to the core memory block;

scanning the bitmap to locate a bitmap entry that corresponds to the core memory block, or multiple bitmap entries that correspond to contiguous core memory blocks if the allocation was of a plurality of memory blocks, the bitmap entry having a multi-bit value that indicates that the core memory block is allocated; and

changing the multi-bit value in the bitmap entry to indicate that the core memory block is free, wherein adjoining free core memory blocks are automatically coalesced.

38. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 37.

39. In a system for managing core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block, a method for reallocating to enlarge a previous allocation of contiguous core memory blocks, comprising the following steps:

scanning the hierarchical bitmap to locate a bitmap entry corresponding to a next core memory block following the contiguous core memory blocks of the previous allocation;

determining whether the located bitmap entry has a multi-bit value indicating that the next core memory block is free; and

enlarging the allocation to include the next contiguous core memory block in the event that the multi-bit value indicates that the next contiguous core memory block is free.

40. A method as recited in claim 39, further comprising the step of changing the multi-bit value to indicate that the next core memory block is no longer free.

41. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 39.

42. In a system for managing core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding core memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block, a method for reallocating to reduce a previous allocation of contiguous core memory blocks, comprising the following steps:

scanning the hierarchical bitmap to locate a bitmap entry corresponding to a core memory block that is last of the contiguous core memory blocks in the previous allocation; and

changing a multi-bit value in the located bitmap entry to indicate that the last core memory block is free.

43. A method as recited in claim 42, further comprising the step of changing a multi-bit value in a bitmap entry corresponding to a next-to-last core memory block in the previous allocation to indicate that the next-to-last core memory block is now last in the allocation.

44. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 42.

45. In a system for managing core memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding core memory blocks, the memory blocks being contiguous for an allocation requiring a plurality of memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding core memory block, a method comprising the following steps:

loading data from the bitmap into a cache;

executing the bitmap data in a first line of the cache at a first execution period; and

pre-fetching the bitmap data in a second line of the cache at a time prior to completion of the first execution period.

46. A memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to consider adjoining memory blocks, which are indicated by multi-bit values in the corresponding bitmap entries as free, as a coalesced grouping of memory blocks that are free for joint allocation.

47. A memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to enlarge a particular allocation of memory blocks by examining a bitmap entry in the hierarchical bitmap for a next memory block following the memory blocks in the particular allocation, the memory manager determining that enlargement is possible if the bitmap entry has a multi-bit value indicating that next memory block is free.

48. A memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to reduce a particular allocation of memory blocks by changing the bitmap entry for a memory block in the particular allocation from a multi-bit value indicating that the memory block is allocated to a multi-bit value indicating that the memory block is free.

49. A computer-readable medium storing an operating system comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to consider adjoining memory blocks, which are indicated by multi-bit values in the corresponding bitmap entries as free, as a coalesced grouping of memory blocks that are free for joint allocation.

50. A computer-readable medium storing an operating system comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to enlarge a particular allocation of memory blocks by examining a bitmap entry in the hierarchical bitmap for a next memory block following the memory blocks in the particular allocation, the memory manager determining that enlargement is possible if the bitmap entry has a multi-bit value indicating that next memory block is free.

51. A computer-readable medium storing an operating system comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to reduce a particular allocation of memory blocks by changing the bitmap entry for a memory block in the particular allocation from a multi-bit value indicating that the memory block is allocated to a multi-bit value indicating that the memory block is free.

52. A computer-readable medium storing an application program comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the core memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to consider adjoining memory blocks, which are indicated by multi-bit values in the corresponding bitmap entries as free, as a coalesced grouping of memory blocks that are free for joint allocation.

53. A computer-readable medium storing an application program comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to enlarge a particular allocation of memory blocks by examining a bitmap entry in the hierarchical bitmap for a next memory block following the memory blocks in the particular allocation, the memory manager determining that enlargement is possible if the bitmap entry has a multi-bit value indicating that next memory block is free.

54. A computer-readable medium storing an application program comprising a memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager configured to manage the memory blocks via the hierarchical bitmap and to allocate contiguous memory blocks for an allocation;

the manager being further configured to reduce a particular allocation of memory blocks by changing the bitmap entry for a memory block in the particular allocation from a multi-bit value indicating that the memory block is allocated to a multi-bit value indicating that the memory block is free.

55. A method for managing memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the method comprising:

allocating contiguous memory blocks for an allocation;

associating entries in a bitmap with directly corresponding memory blocks, individual bitmap entries containing a multi-bit value;

tracking allocation states of the memory blocks by changing the multi-bit value in the bitmap entries; and

automatically coalescing adjoining free memory blocks.

56. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 55.

57. In a system for managing memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding memory blocks, each block having a starting location, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block, a method for deallocating a memory block comprising:

receiving a pointer that points to a location within the memory block other than the starting location of the memory block;

scanning the bitmap to locate a bitmap entry that corresponds to the memory block, the bitmap entry having a multi-bit value that indicates that the memory block is allocated; and

changing the multi-bit value in the bitmap entry to indicate that the memory block is free.

58. A method as recited in claim 57, wherein adjoining free memory blocks are automatically coalesced.

59. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 57.

60. A memory management system for multiple memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, the memory management system comprising:

a hierarchical bitmap having entries for directly corresponding ones of the memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block; and

a manager to manage the memory blocks via the hierarchical bitmap;

wherein the manager, in response to a request to deallocate a memory block, such request having a pointer that points to a location within the memory block other than a starting location of the memory block, is configured to;

scan the bitmap to locate a bitmap entry that corresponds to the memory block, the bitmap entry having a multi-bit value that indicates that the memory block is allocated; and

change the multi-bit value in the bitmap entry to indicate that the memory block is free.

61. In a system for managing memory blocks of a core memory, the core memory being directly addressable by a central processing unit (CPU) of a computer, using a hierarchical bitmap, the hierarchical bitmap having entries for directly corresponding memory blocks, individual bitmap entries containing a multi-bit value that represents an allocation state of the corresponding memory block, a method for reallocating to enlarge a previous allocation of contiguous memory blocks, comprising:

scanning the hierarchical bitmap to locate a bitmap entry corresponding to a next memory block following the contiguous memory blocks of the previous allocation;

determining whether the located bitmap entry has a multi-bit value indicating that the next memory block is free; and

enlarging the allocation to include the next memory block in the event that the multi-bit value indicates that the next memory block is free.

62. A method as recited in claim 61, further comprising changing the multi-bit value to indicate that the next memory block is no longer free.

63. A computer-readable medium having one or more computer executable instructions for performing the steps in the method as recited in claim 61.