Low overhead memory space management

1. A method comprising:

managing an allocation data structure for a memory, wherein the allocation data structure indicates groupings of memory space, each of the groupings having a different associated integer, and each of the groupings serving memory space in portions equal to a unit of memory space allocation times the associated integer for that grouping;

receiving a request for allocation within the memory, wherein the request has an associated number of the unit of memory space allocation; and

selecting one of the groupings from which to serve the request for allocation within the memory based on the associated number in comparison with values obtained using the different associated integers as an exponent.

2. The method of claim 1 , wherein the values are powers of two, the portions are contiguous chunks of the memory, and the unit of memory space allocation is a predetermined chunk size.

3. The method of claim 2 , comprising:

allocating memory space in amounts equal to the associated integer, for respective ones of the groupings, times the predetermined chunk size; and

freeing memory space in an amount equal to the predetermined chunk size, for all of the groupings.

4. The method of claim 1 , wherein each of the groupings comprises one or more groups, each of the groups uses a first bitmap and a second bitmap to represent memory allocations for a contiguous space inside the memory, and the method comprises:

on an allocation using at least one of the groups, changing a bit in the first bitmap to represent two or more units of memory space allocation, and changing two or more bits in the second bitmap to represent the two or more units of memory space allocation; and

on a free request, changing one or more bits in the second bitmap, and when this results in creation of a set of two or more free and aligned units of memory space, changing a corresponding bit in the first bitmap.

5. The method of claim 4 , wherein the selecting comprises:

checking for a partially occupied group in a grouping whose smallest served memory space portion is closest to, without exceeding, a requested amount of memory space;

checking for a new group when no partially occupied group is found; and

serving the request from another grouping, which serves in an even smaller memory space portion, when no new group is found.

6. The method of claim 4 , wherein each of the groups has an identifier that indicates a range of cache pages mapped by the group.

7. The method of claim 4 , wherein the first bitmap is 128 bits, the second bitmap is 128 bits, and the first bitmap and the second bitmap are stored in 32 bytes.

8. A non-transitory computer-readable medium embodying a program operable to cause one or more data processing apparatus to perform operations comprising:

managing an allocation data structure for a memory, wherein the allocation data structure indicates groupings of memory space, each of the groupings having a different associated integer, and each of the groupings serving memory space in portions equal to a unit of memory space allocation times the associated integer for that grouping;

receiving a request for allocation within the memory, wherein the request has an associated number of the unit of memory space allocation; and

selecting one of the groupings from which to serve the request for allocation within the memory based on the associated number in comparison with values obtained using the different associated integers as an exponent.

9. The non-transitory computer-readable medium of claim 8 , wherein the values are powers of two, the portions are contiguous chunks of the memory, and the unit of memory space allocation is a predetermined chunk size.

10. The non-transitory computer-readable medium of claim 9 , wherein the operations comprise:

allocating memory space in amounts equal to the associated integer, for respective ones of the groupings, times the predetermined chunk size; and

freeing memory space in an amount equal to the predetermined chunk size, for all of the groupings.

11. The non-transitory computer-readable medium of claim 8 , wherein each of the groupings comprises one or more groups, each of the groups uses a first bitmap and a second bitmap to represent memory allocations for a contiguous space inside the memory, and the operations comprise:

on an allocation using at least one of the groups, changing a bit in the first bitmap to represent two or more units of memory space allocation, and changing two or more bits in the second bitmap to represent the two or more units of memory space allocation; and

on a free request, changing one or more bits in the second bitmap, and when this results in creation of a set of two or more free and aligned units of memory space, changing a corresponding bit in the first bitmap.

12. A system comprising:

a memory; and

a controller configured to manage requests for allocations of space within the memory in accordance with a management structure and selection rules;

wherein the management structure indicates allocation slabs for the memory, each of the allocation slabs having a different order, with the order corresponding to an amount of memory space allocation; and

wherein the selection rules indicate that, in response to a request having an associated size, an available highest order slab that is closest to the associated size is selected to fulfill the request.

13. The system of claim 12 , wherein the order for each of the allocation slabs is an integer greater than zero, the amount of memory space allocation is a fixed number of contiguous chunks of the memory, each of the chunks has a predetermined size, and the selection rules check that two to the power of the integer of the available highest order slab is less than or equal to a number of requested chunks.

14. The system of claim 13 , wherein the controller is configured to allocate memory space in amounts equal to the respective fixed numbers for the allocation slabs times the predetermined size of the chunks, and free memory space in an amount equal to the predetermined size of the chunks for all of the allocation slabs.

15. The system of claim 12 , wherein each of the allocation slabs comprises one or more allocation groups, each of the allocation groups having an order equal to the order of its corresponding allocation slab, each of the allocation groups providing memory allocations that are greater than or equal to the amount of memory space allocation of its corresponding allocation slab, and each of the allocation groups comprising a current order bitmap and a zero order bitmap.

16. The system of claim 15 , wherein each of the allocation slabs comprises a list of occupied allocation groups and a list of partially occupied allocation groups, and wherein the controller is configured to serve the request from a highest order slab having at least one partially occupied allocation group or from an allocation group taken from a free pool of allocation groups, else if the free pool is empty, then serve the request from a next highest order slab having at least one partially occupied allocation group.

17. The system of claim 15 , wherein each of the allocation groups has an identifier that indicates a range of pages mapped by the allocation group.

18. The system of claim 15 , wherein the current order bitmap is 128 bits, the zero order bitmap is 128 bits, and the current order bitmap and the zero order bitmap are stored in 32 bytes.

19. The system of claim 18 , wherein the current order bitmap and the zero order bitmap are stored are stored using a 32 byte aligned cache.

20. The system of claim 12 , wherein the memory comprises a block based solid state disk (SSD) cache for a storage system.

21. A method comprising:

receiving requests for allocations of space within a memory; and

managing the requests in accordance with a management structure and selection rules;

wherein the management structure indicates allocation slabs for the memory, each of the allocation slabs having a different order, with the order corresponding to an amount of memory space allocation; and

wherein the selection rules indicate that, in response to a request having an associated size, an available highest order slab that is closest to the associated size is selected to fulfill the request.

22. The method of claim 21 , wherein the order for each of the allocation slabs is an integer greater than zero, the amount of memory space allocation is a fixed number of contiguous chunks of the memory, each of the chunks has a predetermined size, and the selection rules cause checking that two to the power of the integer of the available highest order slab is less than or equal to a number of requested chunks.

23. The method of claim 22 , comprising allocating memory space in amounts equal to the respective fixed numbers for the allocation slabs times the predetermined size of the chunks, and free memory space in an amount equal to the predetermined size of the chunks for all of the allocation slabs.

24. The method of claim 21 , wherein each of the allocation slabs comprises one or more allocation groups, each of the allocation groups having an order equal to the order of its corresponding allocation slab, each of the allocation groups providing memory allocations that are greater than or equal to the amount of memory space allocation of its corresponding allocation slab, and each of the allocation groups comprising a current order bitmap and a zero order bitmap.

25. The method of claim 24 , wherein each of the allocation slabs comprises a list of occupied allocation groups and a list of partially occupied allocation groups, and the method comprises:

serving the request from a highest order slab having at least one partially occupied allocation group or from an allocation group taken from a free pool of allocation groups; else if the free pool is empty, then serving the request from a next highest order slab having at least one partially occupied allocation group.