Systems and methods for S-list partitioning

• US 9,652,289 B2
• Filed: 04/27/2012
• Issued: 05/16/2017
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Dixit, Amol Dilip, Waters, Bradley Michael
• Primary Examiner(s): Giardino, Jr., Mark
• Assistant Examiner(s): WOOLWINE, SHANE D
• Application Number:
  US13/458,355
• Publication Number:
  US 20130290667A1
• Time in Patent Office: 1,845 Days
• Field of Search: 711 3, 711113, 711117, 711130, 711150-153, 711170, 711173, 707790-812
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Systems and techniques of the management of the allocation of a plurality of memory elements stored within a plurality of lockless list structures are presented. These lockless list structures (such as Slists) may be made accessible within an operating system environment of a multicore processor—and may be partitioned within the system. Memory elements may also be partitioned among these lockless list structures. When a core processor (or other processing element) makes a request for allocating a memory element to itself, the system and/or method may search among the lockless list structures for an available memory element. When a suitable and/or available memory element is found, the system may allocate the available memory element to requesting core processor. Dynamically balancing of memory elements may occur according to a suitable balancing metric, such as maintain substantial numerical equality of memory elements or avoid over-allocation of resources.

Claims

1. A method of memory allocation for memory that is accessible within an operating system environment of a multicore processor, the method including controlling the allocation of the memory to memory-requesting portions of the multicore processor by:

obtaining a plurality of partitioned lockless list structures, each of the partitioned lockless list structures including a respective plurality of list elements, each of the respective list elements corresponding to a respective portion of the memory that is currently eligible for allocation, the plurality of partitioned lockless list structures being partitioned by application of an adaptive hash to each of a plurality of key values that correspond to elements of a topology of an architecture of the multicore processor;

upon a request for allocating one or more of the respective portions of the memory to a core processor for use as allocated memory, searching said plurality of partitioned lockless list structures for an available list element that corresponds to an available respective portion of the memory that is currently eligible for allocation for use as allocated memory, the searching performed using an adaptive hash that is keyed to respectively hash to each of the plurality of partitioned lockless list structures;

upon finding said available list element, allocating said available respective portion of the memory to said core processor for use as allocated memory; and

dynamically balancing said available list elements among said plurality of said lockless list structures according to a balancing metric that is configured to optimize the allocation of the memory.

2. The method of claim 1, wherein said respective portions of the memory comprise one or more of:

fixed size buffers, or

variable size buffers.

3. The method of claim 2, wherein said partitioned lockless list structures comprise Slist structures.

4. The method of claim 1, wherein obtaining said plurality of partitioned lockless list structures includes:

obtaining an initial lockless list structure that includes an initial plurality of list elements, each of the initial list elements corresponding to an initial respective portion of the memory that is currently eligible for allocation; and

partitioning the initial lockless list structure into the partitioned lockless list structures by applying the adaptive hash to the each of the plurality of key values that correspond to elements of the topology of the architecture of the multicore processor.

5. The method of claim 1, wherein said adaptive hash is keyed according to the multicore processor architecture.

6. The method of claim 1, wherein said adaptive hash is keyed according to processor index.

7. The method of claim 1, wherein said adaptive hash is keyed according to Non Uniform Memory Access (NUMA) node number.

8. The method of claim 1, wherein said balancing metric is configured to balance memory resources.

9. The method of claim 1, wherein said balancing metric is configured to maintain substantially numerical equality of memory elements among the lockless list structures.

10. The method of claim 1, wherein said balancing metric is configured to avoid over-allocation of memory resources.

11. The method of claim 1, wherein said adaptive hash is configured to accommodate a plurality of respective list headers that each reference corresponding respective ones of the partitioned lockless list structures.

12. A system for controlling memory allocation for memory that is accessible within an operating system environment of a multicore processor by controlling the allocation of the memory to memory-requesting portions of the multicore processor, the system comprising:

a first processor that initially partitions an initial lockless list structure into a plurality of partitioned lockless list structures, using an adaptive hash that is keyed according to an architecture of the multicore processor;

a second processor that initially partitions a plurality of list elements among said plurality of partitioned lockless list structures, each of the respective list elements corresponding to a respective portion of the memory that is currently eligible for allocation;

a third processor that, upon a request for allocating memory to a memory-requesting core processor, searches said plurality of partitioned lockless list structures for an available one of the respective list elements, and

upon finding said available one of the respective list elements, allocates, to the memory-requesting core processor, said respective portion of the memory that is currently eligible for allocation that corresponds to the found said available one of the respective list elements; and

a fourth processor that dynamically balances said list elements among said plurality of said partitioned lockless list structures according to a balancing metric, said balancing metric applied to distribute the list elements among said partitioned lockless list structures.

13. The system of claim 12, wherein:

said respective portions of the memory comprise one or more of;

fixed size buffers or variable sized buffers; and

wherein said initial lockless list structure comprises an Slist structure.

14. The system of claim 12, wherein partitioning said initial lockless list structure includes:

partitioning said initial lockless list structure into the plurality of partitioned lockless list structures, using the adaptive hash that is keyed according to processor index.

15. The system of claim 12, wherein partitioning said initial lockless list structure includes:

partitioning said initial lockless list structure into the plurality of partitioned lockless list structures, using the adaptive hash that is keyed according to NUMA node number.

16. A method comprising:

controlling allocation of memory to memory-requesting portions of a multicore processor by;

obtaining a plurality of partitioned lockless list structures, each of the partitioned lockless list structures including a respective plurality of list elements, each of the respective list elements corresponding to a respective portion of the memory that is currently eligible for allocation, the plurality of partitioned lockless list structures being partitioned using an adaptive hash that is keyed according to an architecture of the multicore processor;

upon a request for allocating one or more of the respective portions of the memory to a core processor for use as allocated memory, searching said plurality of partitioned lockless list structures for an available list element that corresponds to an available respective portion of the memory that is currently eligible for allocation for use as allocated memory, the searching performed using the adaptive hash;

upon finding said available list element, allocating said available respective portion of the memory to said core processor for use as allocated memory; and

dynamically balancing said available list elements among said plurality of said lockless list structures according to a balancing metric that is configured to optimize the allocation of the memory.

17. The method of claim 16, wherein said adaptive hash is keyed according to processor index.

18. The method of claim 16, wherein said adaptive hash is keyed according to Non Uniform Memory Access (NUMA) node number.

19. The method of claim 16, wherein said balancing metric is configured to avoid over-allocation of memory resources.

20. The method of claim 16, wherein said adaptive hash is configured to accommodate a plurality of respective list headers that each reference corresponding respective ones of the partitioned lockless list structures.