Dynamic memory allocation in a computer using a bit map index

• US 5,784,699 A
• Filed: 05/24/1996
• Issued: 07/21/1998
• Est. Priority Date: 05/24/1996
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Buzsaki, George Albert, McMahon, Douglas James
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US08/653,221
• Time in Patent Office: 788 Days
• Field of Search: 395/497.01, 395/497.02, 395/497.03, 395/497.04, 395/607
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems

Abstract

A dynamic memory allocator in a computer assigns portions of memory into a large number of slots that include zero or more memory blocks of equal size. Free lists identify memory blocks, corresponding to a slot size, not currently in use in the computer. Software programs generate requests, including a size, for a memory block. The size of the requests are rounded up to the nearest slot size. To allocate a memory block, the free lists are searched, using a bit map index or a hierarchical bit map index, to identify an available memory block to accommodate the memory block requested. The dynamic memory allocator handles large block allocations different from small block allocations. A virtual memory allocator stores a plurality of pointers to identify one or more virtual pages of memory for allocation to the dynamic memory allocator.

Claims

1. A method for allocating memory in a computer system, said method comprising the steps of:

assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size;

generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot;

receiving a request, including a size, for a memory block;

searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request; and

assigning a memory block not in use to accommodate said memory block request.

2. The method as set forth in claim 1, wherein:

the step of generating a bit map index comprises the step of generating a hierarchical bit map index including the steps of;

assigning said slots to a plurality of groups;

generating, for each group, a group bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said groups, and each bit flag indicates availability of at least one memory block in a corresponding group;

generating, for each slot, a slot bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots, and each bit flag indicates availability of at least one memory block in a corresponding slot;

the step of searching by examining one or more of said bit flags comprises the steps of;

examining said group bit index to identify an available group of memory blocks that accommodate said memory block requested; and

examining one or more slot bit map indexes based on said bit flags in said group bit index to identify an available memory block to accommodate said memory block requested.

3. The method as set forth in claim 1, wherein the step of searching for available memory in response to said request comprises the steps of:

searching for an available memory block corresponding to said nearest slot rounded up for said memory block requested;

searching, if no memory block of size equal to said nearest slot rounded up for said memory block requested is available, for an available memory block corresponding to a next largest slot; and

searching, if no memory block in a prior slot searched is available, for an available memory block from a slot corresponding to a next largest slot until either an available block is located or until a largest slot has been searched.

4. The method as set forth in claim 1, wherein the step of assigning portions of memory of equal size into one of a plurality of slots comprises the steps of:

assigning said memory into a plurality of slots, in increments of a first size, for small block allocations, wherein small block allocations include allocations of memory blocks smaller than a predefined maximum small block size; and

assigning said memory into a plurality of slots, in increments of a second size, for large block allocations, wherein large block allocations include allocations of memory blocks smaller than a predefined maximum large block size and greater than said predefined maximum small block size.

5. The method as set forth in claim 1, further comprising the steps of:

referencing a special block; and

apportioning said special block into a memory block of a size to accommodate said memory block requested if, as identified by said bit map index, a memory block is not available and if said special block is large enough to accommodate said memory block requested.

6. The method as set forth in claim 5, further comprising the steps of:

discarding, as a reference, said special block if said special block is not large enough to accommodate said memory block requested;

referencing a new special block;

dividing said new special block into a memory block of a size to accommodate said memory block requested; and

allocating said memory block of a size to accommodate said memory block requested.

7. The method as set forth in claim 1, further comprising the steps of:

apportioning a memory block for a large allocation if a memory block located is large enough for division into two large allocation memory blocks; and

generating, for an apportioned memory block, a double linked pointer to identify physically adjacent blocks and a virtual page for each divided memory block portion.

8. The method as set forth in claim 7, further comprising the steps of:

merging, if possible, adjacent and available memory blocks through use of said double linked pointers to generate a new large block;

referencing said new large block from a new slot; and

merging, if possible, adjacent and available memory blocks that constitute a virtual page of memory through use of said double linked pointers to free said virtual page of memory.

9. The method as set forth in claim 1, further comprising the steps of:

generating a plurality of pointers to identify one or more virtual pages of memory;

requesting a virtual page of memory if no memory blocks are available as identified from said bit map index; and

allocating, if possible, a virtual page of memory identified from one of said pointers.

10. The method as set forth in claim 9, further comprising the step of generating a request to an operating system of said computer to obtain a virtual page of memory if a virtual page, as identified by said pointers, is not available.

11. A method for allocating memory in a computer system, said method comprising the steps of:

assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size;

generating a plurality of free lists, one for each slot, such that each free list identifies memory blocks, corresponding to a slot size, not currently in use;

receiving a request, including a size, for a memory block;

rounding up said size of said memory block requested to a nearest slot;

searching one or more of said free lists to identify an available memory block to accommodate said memory block requested; and

assigning a memory block not in use to accommodate said memory block requested.

12. The method as set forth in claim 11, wherein the step of assigning portions of memory of equal size into one of a plurality of slots comprises the step of assigning memory of equal size into at least 32 slots.

13. A computer readable medium having a set of instructions stored therein, which when executed by a computer, causes the computer to perform the steps of:

assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size;

generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot;

receiving a request, including a size, for a memory block;

searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block requested; and

assigning a memory block not in use to accommodate said memory block requested.

14. The computer readable medium as set forth in claim 13, wherein:

the instructions for generating a bit map index comprises instructions for generating a hierarchical bit map index including instructions for;

assigning said slots to a plurality of groups;

generating, for each group, a group bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said groups, and each bit flag indicates availability of at least one memory block in a corresponding group;

generating, for each slot, a slot bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots, and each bit flag indicates availability of at least one memory block in a corresponding slot;

instructions for searching by examining one or more of said bit flags comprises instructions for;

examining said group bit index to identify an available group of memory blocks that accommodate said memory block requested; and

examining one or more slot bit map indexes based on said bit flags in said group bit index to identify an available memory block to accommodate said memory block requested.

15. The computer readable medium as set forth in claim 13, wherein the instructions for searching for available memory in response to said request comprises instructions for:

searching for an available memory block corresponding to said nearest slot rounded up for said memory block requested;

searching, if no memory block of size equal to said nearest slot rounded up for said memory block requested is available, for an available memory block corresponding to a next largest slot; and

searching, if no memory block in a prior slot searched is available, for an available memory block from a slot corresponding to a next largest slot until either an available block is located or until a largest slot has been searched.

16. The computer readable medium as set forth in claim 13, wherein the instructions for assigning portions of memory of equal size into one of a plurality of slots comprises instructions for:

assigning said memory into a plurality of slots, in increments of a first size, for small block allocations, wherein small block allocations include allocations of memory blocks smaller than a predefined maximum small block size; and

assigning said memory into a plurality of slots, in increments of a second size, for large block allocations, wherein large block allocations include allocations of memory blocks smaller than a predefined maximum large block size and greater than said predefined maximum small block size.

17. The computer readable medium as set forth in claim 13, further comprising instructions for:

referencing a special block; and

apportioning said special block into a memory block of a size to accommodate said memory block requested if, as identified by said bit map index, a memory block is not available and if said special block is large enough to accommodate said memory block requested.

18. The computer readable medium as set forth in claim 17, further comprising instructions for:

discarding, as a reference, said special block if said special block is not large enough to accommodate said memory block requested;

referencing a new special block;

dividing said new special block into a memory block of a size to accommodate said memory block requested; and

allocating said memory block of a size to accommodate said memory block requested.

19. The computer readable medium as set forth in claim 13, further comprising instructions for:

apportioning a memory block for a large allocation if a memory block located is large enough for division into two large allocation memory blocks; and

generating, for an apportioned memory block, a double linked pointer to identify physically adjacent blocks and a virtual page for each divided memory block portion.

20. The computer readable medium as set forth in claim 19, further comprising instructions for:

merging, if possible, adjacent and available memory blocks through use of said double linked pointers to generate a new large block;

referencing said new large block from a new slot; and

merging, if possible, adjacent and available memory blocks that constitute a virtual page of memory through use of said double linked pointers to free said virtual page of memory.

21. A computer system comprising:

a central processing unit;

system memory;

a software program resident in said memory and executed by said central processing unit, for a request, including a size, for a memory block; and

a dynamic memory allocator for assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size, said dynamic memory allocator for generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot, for searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request, and for assigning a memory block not in use to accommodate said memory block requested.