BACKGROUND

Memory allocation systems assign blocks of memory on request. A memory allocation system employs an allocator to receive relatively large blocks of memory from an operating system and allocate that memory to satisfy memory requests. Upon receipt of a request for a relatively small block of memory, a standard and/or conventional allocator satisfies the request by dividing one of the large blocks of memory into multiple smaller blocks.

A known, standard, and/or conventional memory allocation system is the buddy system. The buddy system divides allocatable blocks of memory into pairs of contiguous equally-sized blocks, for example, buddies. The buddy system employs a buddy system memory allocator that allocates memory blocks of certain permitted sizes. The permitted sizes may be powers of two, such as 4 KB (kilobytes), 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc. In another example, the permitted sizes form a Fibonacci sequence, such as 16 KB, 32 KB, 48 KB, 80 KB, 128 KB, etc. Therefore, each memory block in the buddy system except the smallest allowable memory block can be divided into two smaller blocks of permitted sizes.

The buddy system memory allocator also maintains many free block lists, for example, memory buckets. The buddy system memory allocator maintains one free block list for each of the permitted memory block sizes. Where the permitted memory block sizes are 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc., the buddy system memory allocator may maintain a free block list for available 4 KB memory blocks, a free block list for available 8 KB memory blocks, a free block list for available 16 KB memory blocks, a free block list for available 32 KB memory blocks, a free block list for available 64 KB memory blocks, a free block list for available 128 KB memory blocks, etc. The free block lists comprise all the available blocks of a particular size. For example, the free block list for 16 KB memory blocks comprises all of the available 16 KB memory blocks.

When the buddy system memory allocator receives a request for a size of memory, the buddy system memory allocator rounds the requested size up to the size permitted in the buddy system, and returns the first block from the free block list for memory blocks of that permitted size. If the free list for memory blocks of that permitted size is empty, then the buddy system memory allocator splits a larger permitted size memory block and allocates one of the split pieces of memory to satisfy the original memory request. The buddy system memory allocator adds the other split pieces remaining from the satisfied memory request, to the appropriate lists of free blocks of permitted memory sizes in that buddy system.

When memory blocks are released, the buddy system memory allocator may attempt to join, merge, or coalesce two contiguous equally-sized memory blocks or buddies into a single memory block of a larger permitted size. For example, if two 16 KB memory blocks are available and contiguous, the buddy system memory allocator may attempt to coalesce the two 16 KB memory blocks into one 32 KB memory block. The coalescence requires the memory blocks to be contiguous.

In a known, standard, and/or conventional buddy system, the following requirements apply for two blocks of memory to qualify as buddies: 1) the two blocks of memory must be contiguous, 2) the two blocks of memory must be of equal size, and 3) the starting address of the combined block must be aligned to the size of the combined size. For example, if two 16 KB size blocks are to be combined into a 32 KB size, the starting address of the 32 KB size block should at least be 32 KB size aligned; that is, the 32 KB sized block needs to have a starting address that is a multiple of 32 KB to be aligned in the buddy system.

DETAILED DESCRIPTION

As described in the BACKGROUND section above, known, standard, and/or conventional buddy systems, as an exemplary shortcoming, create relatively large amounts of external memory fragmentation. External memory fragmentation occurs when the buddy system memory allocator divides large memory blocks to satisfy memory requests and leaves many smaller memory blocks unallocated. The small blocks may be too small to satisfy most memory requests, and the small blocks will therefore accumulate over time. When large amounts of external memory fragmentation occur, the system may run out of memory available to satisfy larger memory requests.

An exemplary known, standard, and/or conventional strategy to reduce external memory fragmentation in the buddy system is to allocate blocks that are only the permitted sizes. However, this strategy increases the amount of internal memory fragmentation. Internal memory fragmentation occurs when the buddy system memory allocator allocates more memory than is actually requested. Another exemplary known, standard, and/or conventional strategy to reduce external memory fragmentation in the buddy system is to classify memory requests based on the length of time that the memory will be needed. This strategy classifies all memory requests as either short-term allocations or long-term allocations. In an attempt to increase coalescing opportunities, this strategy groups together the short-term allocations and separately groups together the long-term allocations. However, this strategy requires multiple buddy system allocators for the multiple groups and may not improve external fragmentation in the long-term allocation group.

So, exemplary known, standard, and/or conventional buddy system memory allocators create relatively large amounts of external memory fragmentation. For example, exemplary known, standard, and/or conventional buddy system memory allocators result in many available memory blocks that may not be able to be coalesced and are also too small to satisfy a larger memory request. Thus, a need exists for an enhanced and/or modified buddy system memory allocator that determines whether the available memory blocks comprise a plurality of contiguous, differently-sized memory blocks that collectively add up to a size that would satisfy the larger memory request. By employing a plurality of contiguous, differently-sized memory blocks to satisfy a memory request, the enhanced and/or modified buddy system memory allocator in an example leads to better utilization of memory and reduces memory pressure on the system. Also, the use of the plurality of contiguous, differently-sized memory blocks to satisfy a memory request in an example reduces memory fragmentation.

Turning to FIG. 1, an implementation of an apparatus?100?in an example comprises one or more memory management sub-systems?101?and one or more client applications. An exemplary memory management sub-system?101?comprises one or more modified buddy system memory allocators?102, one or more indexers and/or fast search mechanisms?103, and one or more lower level memory allocators?104. Exemplary client applications comprise client applications?106,?108. The memory management sub-system?101?and the client applications?106?and?108?in an example operate on different levels of the apparatus?100. Within an exemplary memory management sub-system, the modified buddy system memory allocator?102?and the lower level memory allocator?104?operate at different levels. For example, the lower level memory allocator?104?operates on a first level?110?and the modified buddy system memory allocator?102?operates on a second level?112?which are within the memory management sub-system?101. The memory management sub-system?101?in an example operates at a different level?114?than the client applications?106?and?108, which operate on another level116. An exemplary modified buddy system memory allocator?102?comprises one or more recordable data storage media?150. An exemplary implementation of the index and/or fast search mechanism?103?comprises an algorithm, procedure, program, mechanism, coordinator, module, application, code, and/or logic.

The lower level memory allocator?104?allocates memory to the modified buddy system memory allocator?102?for potential allocation to the client applications?106?and?108. When the client applications?106?and?108?require memory, the client applications?106?and?108?make requests to the modified buddy system memory allocator?102. The modified buddy system memory allocator?102?attempts to satisfy the requests with memory that the modified buddy system memory allocator?102?controls at the time of the request. If the modified buddy system memory allocator?102?does not have sufficient memory to satisfy the request, then the modified buddy system memory allocator?102?requests additional memory from the lower level memory allocator104?to satisfy the request.

The memory management sub-system?101?in an example is responsible for memory related tasks on the apparatus?100?that comprise memory related tasks of the modified buddy system allocator?102?and the lower level memory allocator?104. For example, the memory management sub-system?101?is responsible for memory related tasks that include and are not limited to the memory related tasks of the modified buddy system allocator?102?and the lower level memory allocator?104. In a further example, the memory management sub-system?101?is also responsible for maintaining state information on different memory objects in the apparatus?100. The memory management sub-system?101?also provides the fast search mechanism?103, for example, to look up the state information of different memory objects within the memory management sub-system?101.

The modified buddy system memory allocator?102?allocates memory blocks of certain permitted sizes. In an example, the permitted sizes are powers of two, such as 4 KB (kilobytes), 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc. In another example, the permitted sizes form a Fibonacci sequence, such as 16 KB, 32 KB, 48 KB, 80 KB, 128 KB, etc. Therefore, each memory block in the modified buddy system except the smallest allowable memory block can be divided into two smaller blocks of permitted sizes. Each of these two smaller blocks can be further divided until the smallest allowable memory block size is reached. For example, a programmer can set the smallest allowable memory block size. The programmer in an example sets the smallest allowable memory block size to be one of 1 KB, 2 KB, 4 KB, or the like. In an example, referring to FIG. 2, the smallest allowable memory block size is set to 4 KB.

To satisfy a memory request, the modified buddy system memory allocator?102?in an example divides a memory block into two equally-sized blocks, for example, buddies. The modified buddy system memory allocator?102?may allocate one of the buddies to satisfy the memory request and add the other one of the buddies to a free block list. Once the allocated one of the buddies is released and both of the buddies are available, the modified buddy system memory allocator?102?may attempt to join, merge, or coalesce the two buddies into a single larger memory block. Coalescing involves the joining or merging of two contiguous equally-sized memory blocks.

Referring to FIGS. 1-2, the modified buddy system memory allocator?102?organizes available memory blocks into a plurality of free block lists?202, for example, memory buckets. The modified buddy system memory allocator?102?in an example maintains one free block list for each of the permitted memory block sizes. For example, where the permitted memory block sizes are 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, 256 KB, 512 KB, and 1 MB (megabyte), the modified buddy system memory allocator?102?maintains a free block list?204?for available 1 MB memory blocks, a free block list?206?for available 512 KB memory blocks, a free block list?208?for available 256 KB memory blocks, a free block list?210?for available 128 KB memory blocks, a free block list?212?for available 64 KB memory blocks, a free block list?214?for available 32 KB memory blocks, a free block list?216?for available 16 KB memory blocks, a free block list?218?for available 8 KB memory blocks, and a free block list?220?for available 4 KB memory blocks. The modified buddy system memory allocator?102?in an example may also organize available memory blocks of other sizes into additional free block lists, as will be appreciated by those skilled in the art. Each of the free block lists?202?in an example comprises all the available memory blocks controlled by the modified buddy system memory allocator?102?that are of a particular size. For example, the free block list?216?comprises all of the available 16 KB memory blocks that the modified buddy system memory allocator?102?controls.

Each of the free block lists?202?comprises zero or more memory blocks. In an example, referring to FIG. 2, the free block lists?204,?206,?208,?210,?212, and?214?comprise no memory blocks. The free block list?216?in an example comprises memory blocks?222,?224, and?226. The memory blocks?222,?224, and?226?are each 16 KB. The free block list?218?in an example comprises memory blocks?228,?230, and?232. The memory blocks?228,?230, and?232are each 8 KB. The free block list?220?in an example comprises memory blocks?234,?236, and?238. The memory blocks?234,?236, and?238?are each 4 KB.

When the modified buddy system memory allocator?102?allocates a memory block, the modified buddy system memory allocator?102?removes that memory block from the free block list?202?that corresponds to the size of the memory block. As additional memory blocks become available, the modified buddy system memory allocator?102?in an example may add the additional memory blocks to the appropriate ones of the free block lists?202.

The free block lists?202?in an example comprise circular linked lists of memory blocks. In an example, the free block lists?202?use pointers to connect the memory blocks, as will be appreciated by those skilled in the art. For example, each of the memory blocks?222,?224, and?226?in the free block list216?comprise head pointers and tail pointers to the other memory blocks?222,?224, and?226?in the free block list?216. When adding or removing a memory block to one of the free block lists?202, the modified buddy system memory allocator?102?modifies one or more pointers in the free block list202?to successfully add or remove the memory block. To add the memory block, the modified buddy system memory allocator?102?selects a location in the free block list?202?for addition of the memory block and modifies the pointers of the adjacent memory blocks in the free block list?202. To remove the memory block, the modified buddy system memory allocator?102?modifies the pointers of the adjacent memory blocks in the free block list?202?so that the adjacent memory blocks point to each other rather than the removed memory block.

Referring to FIGS. 1-3, an illustrative description of an exemplary operation of an implementation of the apparatus?100?is presented, for explanatory purposes. In exemplary logic?302, the modified buddy system memory allocator?102?attempts to satisfy a request for a size of memory made by one of the client applications?106?and?108. The requested size of memory is represented in the exemplary logic?302?by the variable X. The requested size (X) of memory may be any value, as will be appreciated by those skilled in the art. In an example, the requested size (X) of memory is a multiple of the smallest allowable memory block size and, referring to FIG. 2, the smallest allowable memory block size is set to 4 KB. For example, the requested size (X) of memory in the exemplary logic?302?is 28 KB.

At STEP?304, the modified buddy system memory allocator?102?receives a request for a size (X) of memory from one of the client applications?106?and108, for example, the client application?106. After the modified buddy system memory allocator?102?receives the request for the size (X) of memory from the client application?106, STEP?304?proceeds to STEP?306. At STEP?306, the modified buddy system memory allocator?102?rounds the requested size (X) of memory up to the nearest permitted size of a free block list?202?that is greater than or equal to the requested size (X). The nearest permitted size greater than the requested size (X) is represented in the exemplary logic?302?by the variable Y. The free block lists?202?in an example are organized as powers of two. For example, the modified buddy system memory allocator?102?has access to the free block lists?202?that hold memory blocks with sizes of 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc. Where the requested size (X) is 28 KB, the nearest power of two above 28 KB is 32 KB. Therefore, the modified buddy system memory allocator?102?rounds the requested size (X) of memory up to 32 KB, and STEP?306?proceeds to STEP?308.

At STEP?308, the modified buddy system memory allocator?102?attempts to locate an available memory block that has a size that is greater than or equal to the size (Y), which in this illustration is 32 KB. First, the modified buddy system memory allocator?102?checks the free block list?214?for an available memory block of size 32 KB. If the modified buddy system memory allocator?102?locates a memory block in the free block list?214, then STEP308?proceeds to STEP?310. If the free block list?214?is empty, then the modified buddy system memory allocator?102?in an example continues to check the other free block lists?202?for an available memory block of a size larger than 32 KB. For example, the modified buddy system memory allocator?102checks the free block list?212, followed by the free block list?210, etc. If the modified buddy system memory allocator?102?does locate an available memory block in the free block lists?202?that is at least as large as the size (Y), then STEP?308?proceeds to STEP?310. If the modified buddy system memory allocator?102?does not locate an available memory block in the free block lists?202?that is at least as large as the size (Y), then STEP?308proceeds to STEP?404?(FIG. 4), as described herein.

At STEP?310, the modified buddy system memory allocator?102?allocates a memory block of the requested size (X) to the client application?106?that requested the memory, as will be appreciated by those skilled in the art. Once the modified buddy system memory allocator?102?has allocated the memory, STEP?310?proceeds to STEP?312. At STEP?312, if the available memory block chosen to satisfy the request is larger than the requested size (X), then the modified buddy system memory allocator?102?returns the remainder from the memory allocation to the appropriate ones of the free block lists?202. In an example, the remainder may be returned to the free block lists?202?since the requested size (X) is a multiple of the smallest allowable memory block size. For example, if the modified buddy system memory allocator?102?located a 32 KB memory block to satisfy the request for 28 KB of memory, then the modified buddy system memory allocator?102?will allocate 28 KB to the client application?106?and add a 4 KB block of memory to the free block list?220. If the modified buddy system memory allocator?102?located a 64 KB memory block to satisfy the request for 28 KB of memory, then the modified buddy system memory allocator?102?will allocate 28 KB to the client application?106, add a 32 KB block of memory to the free block list214, and add a 4 KB block of memory to the free block list?220.

Referring to FIGS. 1-2 and?4, exemplary logic?402?serves to illustrate an attempt by the modified buddy system memory allocator?102?to satisfy the memory request received at STEP?304?(FIG. 3) with a plurality of contiguous, differently-sized memory blocks that are each smaller than the requested size (X) of memory. As noted above, if at STEP?308?(FIG. 3) the modified buddy system memory allocator?102?does not locate an available memory block in the free block lists?202?that is at least as large as the size (Y), then STEP?308?proceeds to STEP?404.

At STEP?404, the modified buddy system memory allocator?102?rounds the requested size (X) of memory down to the nearest permitted size of a free block list?202?that is less than the requested size (X). The nearest permitted size below the requested size (X) is represented in the exemplary logic?402by the variable Z. The free block lists?202?in an example are organized as powers of two. For example, the modified buddy system memory allocator102?has access to the free block lists?202?that hold memory blocks with sizes of 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc. Where the requested size (X) is 28 KB, the nearest power of two below 28 KB is 16 KB. Therefore, the modified buddy system memory allocator?102?rounds the requested size (X) of memory down to 16 KB, and STEP?404?proceeds to STEP?406. At STEP?406, the modified buddy system memory allocator?102?checks the free block list?216?for an available memory block of size 16 KB.

If at STEP?406?the modified buddy system memory allocator?102?determines that the free block list?216?is empty, then STEP?406?proceeds to STEP408. At STEP?408, the modified buddy system memory allocator?102?determines whether additional memory is available in the lower level memory allocator?104. If the lower level memory allocator?104?does not have available memory, then STEP?408?proceeds to STEP?410. At STEP?410, the modified buddy system memory allocator?102?determines that sufficient memory is not available to satisfy the request for the size of memory made by the client application?106. Therefore, the modified buddy system memory allocator?102?returns a Null or Fail result to the client application?106.

If at STEP?408?the lower level memory allocator?104?does have available memory, then STEP?408?proceeds to STEP?412. At STEP?412, memory is allocated from the lower level memory allocator?104?to the modified buddy system memory allocator?102. For example, a memory block large enough to satisfy the request is added to one of the free block lists?202. The lower level allocator?104?in an example allocates to the modified buddy system memory allocator?102?either: a memory block of a default refill size (R), or a memory block of the size (Y). If the size (Y) is smaller than the default refill size (R), then the lower level memory allocator?104?in an example allocates a memory block of the default refill size (R) to the modified buddy system memory allocator?102. If the size (Y) is larger than the default refill size (R), then the lower level memory allocator?104?in an example allocates a memory block of the size (Y) to the modified buddy system memory allocator?102.

The default refill size (R) in an example may be set to any value. For example, the default refill size (R) is set to 64 KB. In this illustration the size (Y) is 32 KB, which is smaller than the 64 KB of the default refill size (R), so the lower level memory allocator?104?allocates the 64 KB of the default refill size (R) of memory to the modified buddy system memory allocator for subsequent allocation to client applications?106?and?108. The modified buddy system memory allocator?102?in an example adds the 64 KB memory block to the free block list?212?for the 64 KB memory blocks.

After allocation of the newly received memory, the modified buddy system memory allocator?102?will allocate a memory block from the newly received memory to satisfy the memory request. For example, the modified buddy system memory allocator will perform STEPS?308,?310, and?312?(FIG. 3) to satisfy the memory request with the newly received memory.

If at STEP?406?the modified buddy system memory allocator?102?locates an available memory block in the free block list?216, then STEP?406?proceeds to STEP?414. For example, the modified buddy system memory allocator?102?locates the memory block?222?in the free block list?216. The modified buddy system memory allocator?102?in an example begins with the memory block?222?on the search for a plurality of contiguous, differently-sized memory blocks that are each smaller than the requested size (X) of memory, but collectively are at least as large as the requested size (X) of memory. The modified buddy system memory allocator?102?is able to proceed regardless whether the address of the memory block?222?is aligned or nonaligned to the rounded up to the next power of 2 value of the requested size (X) of memory; that is, the address of a first memory block or any other memory block to be combined in the plurality of contiguous, differently-sized memory blocks need not be a multiple of the rounded up to the next power of 2 value of the requested size (X) of memory.

At STEP?414, the modified buddy system memory allocator?102?calculates the address (Z_n) of a memory block that would be contiguous to the memory block?222. In an example, referring to FIG. 2, the address (Z₀) of the memory block?222?is 0x71604000. The memory block that is contiguous to the memory block?222?begins where the memory block?222?ends. Therefore, that contiguous memory block would have an address (Z_n) that is 16 KB greater than 0x71604000, specifically, 0x71608000. After the modified buddy system memory allocator?102?calculates that the address (Z_n) of the memory block that would be contiguous to the memory block?222?is 0x71608000, STEP?414?proceeds to STEP?416. The modified buddy system memory allocator?102?is able to proceed regardless whether the address (Z₀) of the memory block?222?0x71604000 is aligned or nonaligned to the rounded up to the next power of 2 value of the requested size (X) of 28 KB. For the requested size (X) of 28 KB, the next power of 2 value is 32 KB. This alignment or nonalignment non-requirement means the address (Z₀) of a first memory block or any other memory block to be combined in the plurality of contiguous, differently-sized memory blocks need not be a multiple of the rounded up to the next power of 2 value of the requested size (X) of 28 KB. So, for the requested size (X) of 28 KB, the address (Z₀) of the first memory block or any other memory block to be combined in the plurality of contiguous, differently-sized memory blocks need not be a multiple 32 KB, which is the next power of 2 value after 28 KB.

Referring to FIGS. 4 and 5, the modified buddy system memory allocator?102?at STEP?416?determines if the memory block that starts at 0x71608000 is available in one of the free block lists?202. STEP?502?obtains the state information of the page that corresponds to the memory block that starts at 0x71608000. In an example, state information is maintained for each page of memory by the memory management sub-system?101. The state information in an example is updated to indicate all the relevant state changes of that page of memory. For example, the state information field in an example is marked as "In use by buddy allocator" by the memory management sub-system?101, if the page is located in one of the free block lists?202. In a further example, the state information field is marked as "In use by client application" by the memory management sub-system?101, if the page is allocated to one of the client applications?106?and?108. In a still further example, the state information field is marked as "Free" by the memory management sub-system?101, if the page is located in the lower level memory allocator?104.

If the modified buddy system memory allocator?102?allocates a block of memory from the lower level memory allocator?104, then the state information field is changed from "Free" to "In use by buddy allocator" by the memory management sub-system?101. The state is changed back to "Free" by the memory management sub-system?101, if the block is freed back to lower level memory allocator?104. Similarly, if the client application?106?or?108allocates memory from the modified buddy system memory allocator?102, the memory management sub-system?101?changes the state information field from "In use by buddy allocator" to "In use by client". The state information field is changed back to "In use by buddy allocator" from "In use by client" by the memory management sub-system?101, if the client application?106?or?108?returns the memory block back to the modified buddy system memory allocator?102.

An exemplary implementation of the modified buddy system memory allocator?102?comprises and/or employs a feature such as an exemplary search mechanism. Exemplary search mechanisms comprise a fast search mechanism and/or an indexer?103. The search mechanism in an example employs an exemplary data structure that serves to allow fast access to state information associated with an address. Exemplary addresses in the data structure comprise: a) addresses for memory blocks in use by the modified buddy system memory allocator?102?such as represented in FIG. 2; b) addresses for memory blocks on free block lists available for use by the modified buddy system memory allocator?102; and c) addresses for memory blocks in use by the client application?106?and/or?108. An exemplary implementation of the exemplary data structure comprises an exemplary array as follows.