Bucket based memory allocation

Abstract

Managing memory includes subdividing the memory into a first set of blocks corresponding to a first size and a second set of blocks corresponding to a second size that is greater than said first size, in response to a request for an amount of memory that is less than or equal to the first size, providing one of the first set of blocks, and, in response to a request for an amount of memory that is greater than the first size and less than or equal to the second size, providing one of the second set of blocks. Subdividing the memory may also include subdividing the memory into a plurality of sets of blocks, where each particular set contains blocks corresponding to one size that is different from that of blocks not in the particular set. Each set of blocks may correspond to a size that is a multiple of a predetermined value. Managing memory may also include providing a table containing an entry for each set of blocks. The entry for each set of blocks may be a pointer to one of: an unused block and null. Unused blocks of a set may be linked together to form a linked list where the pointer for each entry in the table points to the first block in the list.

1 - 42 . (canceled) 
   
   
       43 . A method of managing memory, comprising:
 subdividing a first volatile memory into at least a first linked list of blocks corresponding to a first size and at least a second linked list of blocks corresponding to a second size that is greater than said first size, wherein user data stored by each linked list of blocks is provided entirely in the first volatile memory;   providing, in a second volatile memory different from said first memory, a table that includes pointers that point directly to a first block of each of said linked lists, wherein the second volatile memory does not contain any linked lists of blocks provided in the first volatile memory;   in response to a request for an amount of memory that is less than or equal to the first size, providing a pointer to said first block of said first linked list of blocks and modifying said table to point to a remaining portion of said first linked list of blocks that does not include said first block; and   in response to a request for an amount of memory that is greater than the first size and less than or equal to the second size, providing a pointer to said first block of said second linked list of blocks and modifying said table to point to a remaining portion of said second linked list of blocks that does not include said first block of said second linked list of blocks.   
   
   
       44 . A method, according to  claim 43 , wherein subdividing said first memory further includes subdividing said first memory into a plurality of linked lists of blocks, wherein each particular linked list contains blocks corresponding to one size that is different from that of blocks not in the particular linked list. 
   
   
       45 . A method, according to  claim 44 , wherein each set of blocks corresponds to a size that is a multiple of a predetermined value. 
   
   
       46 . A method, according to  claim 45 , wherein the predetermined value is 2 n , where n is an integer. 
   
   
       47 . A method, according to  claim 46 , wherein the predetermined value is eight. 
   
   
       48 . A method, according to  claim 46 , wherein the table includes one entry for each multiple of corresponding block sizes. 
   
   
       49 . A method, according to  claim 43 , wherein the first and second memories have different access rates. 
   
   
       50 . A method, according to  claim 43 , wherein the entry for each linked list of blocks is a pointer to one of: said first block and null. 
   
   
       51 . A method, according to  claim 43 , wherein the blocks contain a section in which user data is stored. 
   
   
       52 . A method, according to  claim 43 , further comprising:
 in response to a request for an amount of memory corresponding to a particular linked list of blocks for which there are no unused blocks, requesting a block of memory from a heap.   
   
   
       53 . A method, according to  claim 52 , further comprising:
 in response to there being no block of memory from the heap corresponding to the request, returning all unused blocks of memory to the heap.   
   
   
       54 . A method, according to  claim 53 , further comprising:
 following returning all unused blocks to the heap, rerequesting a block of memory from the heap.   
   
   
       55 . A computer program product, contained on a tangible computer-readable medium, comprising:
 executable code that, when executed by a computer, subdivides a first volatile memory into at least a first linked list of blocks corresponding to a first size and at least a second linked list of blocks corresponding to a second size that is greater than said first size, wherein user data stored by each linked list of blocks is provided entirely in the first volatile memory;   executable code that, when executed by a computer, provides, in a second volatile memory different from said first memory, a table that includes pointers that point directly to a first block of each of said linked lists, wherein the second volatile memory does not contain any linked lists of blocks provided in the first volatile memory;   executable code that, when executed by a computer, provides a pointer to said first block of said first linked list of blocks and modifies said table to point to a remaining portion of said first linked list of blocks that does not include said first block in response to a request for an amount of memory that is less than or equal to the first size; and   executable code that, when executed by a computer, provides a pointer to said first block of said second linked list of blocks and modifies said table to point to a remaining portion of said second linked list of blocks that does not include said first block of said second linked list of blocks in response to a request for an amount of memory that is greater than the first size and less than or equal to the second size.   
   
   
       56 . A computer program product, according to  claim 55 , wherein the executable code that subdivides the first memory subdivides the first memory into a plurality of linked lists of blocks, wherein each particular linked list contains blocks corresponding to one size that is different from that of blocks not in the particular linked list. 
   
   
       57 . A computer program product, according to  claim 56 , wherein each linked list of blocks corresponds to a size that is a multiple of a predetermined value. 
   
   
       58 . A computer program product, according to  claim 57 , wherein the predetermined value is 2 n , where n is an integer. 
   
   
       59 . A computer program product, according to  claim 58 , wherein the predetermined value is eight. 
   
   
       60 . A computer program product, according to  claim 55 , further comprising:
 executable code that, when executed by a computer, requests a block of memory from a heap in response to a request for an amount of memory corresponding to a particular set of blocks for which there are no unused blocks.   
   
   
       61 . A computer program product, according to  claim 59 , further comprising:
 executable code that, when executed by a computer, returns all unused blocks of memory to the heap in response to there being no block of memory from the heap corresponding to the request.