Deallocation of computer data in a multithreaded computer

• US 7,328,438 B2
• Filed: 03/27/2003
• Issued: 02/05/2008
• Est. Priority Date: 03/27/2003
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Armstrong, Willaim Joseph, Nayar, Naresh, Heyrman, Peter Joseph
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Vo; Lilian
• Application Number:
  US10/400,702
• Publication Number:
  US 20040194096A1
• Time in Patent Office: 1,776 Days
• Field of Search: 718/104, 718/100, 718/102, 711/1, 711/100, 710/5, 710/19, 710/20, 707/206
• US Class Current: 718/100
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

An apparatus, program product and method support the deallocation of a data structure in a multithreaded computer without requiring the use of computationally expensive semaphores or spin locks. Specifically, access to a data structure is governed by a shared pointer that, when a request is received to deallocate the data structure, is initially set to a value that indicates to any thread that later accesses the pointer that the data structure is not available. In addition, to address any thread that already holds a copy of the shared pointer, and thus is capable of accessing the data structure via the shared pointer after the initiation of the request, all such threads are monitored to determine whether any thread is still using the shared pointer by determining whether any thread is executing program code that is capable of using the shared pointer to access the data structure. Once this condition is met, it is ensured that no thread can potentially access the data structure via the shared pointer, and as such, the data structure may then be deallocated.

Claims

1. A method of deleting a partition from a logically-partitioned computer of the type including a plurality of logical partitions managed by a partition manager, the logically-partitioned computer further including a plurality of threads executing thereon, and the partition manager having access to a partition control block associated with the partition being deleted, the method comprising:

incrementing a sequence number associated with a first thread among the plurality of threads to one of an odd and an even value whenever the first thread enters program code for the partition manager;

incrementing the sequence number from the other of an odd and an even value whenever the first thread exits the program code; and

deallocating the partition control block by;

setting a shared pointer to the partition control block to a null value to indicate that the partition control block is not available;

capturing a value of the sequence number;

waiting until each of the plurality of threads is no longer using the shared pointer by monitoring each thread to determine whether said each thread is executing program code that uses the shared pointer, including determining that said each thread is no longer using the shared pointer in response to meeting at least one of a plurality of conditions that includes a first condition where said each thread is inactive, a second condition where said thread is executing in an idle loop in the partition manager, a third condition where said each thread is currently executing program code other than program code for the partition manager, and a fourth condition where the sequence number has changed from the captured value; and

deallocating the partition control block after setting the shared pointer to the null value and waiting until each of the plurality of threads is no longer using the shared pointer.

2. A method of deallocating a data structure accessible by a plurality of threads executing in a computer, the method comprising, in response to a request to deallocate the data structure:

setting a shared pointer to the data structure to a predetermined value that indicates to a thread thereafter attempting to use the pointer that the data structure is not available;

waiting until each of the plurality of threads is no longer using the shared pointer by monitoring said each thread to determine whether said each thread is executing program code that is capable of using the shared pointer to access the data structure; and

deallocating the data structure after setting the shared pointer to the predetermined value and waiting until said each of the plurality of threads is no longer using the shared pointer;

wherein determining whether said each thread is executing program code that is capable of using the shared pointer to access the data structure includes determining that said each thread among the plurality of threads is no longer using the shared pointer in response to meeting at least one of a plurality of conditions that includes a first condition where said each thread is inactive, a second condition where said each thread is executing in an idle loop, a third condition where said each thread is currently executing program code other than that which is capable of using the shared pointer, and a fourth condition where the first thread has exited the program code that is capable of using the shared pointer.

3. The method of claim 2, wherein the idle loop is a partition manager idle loop.

4. The method of claim 2, wherein determining whether said each thread is executing program code that is capable of using the shared pointer to access the data structure includes determining whether an indicator associated with said each thread indicates that said each thread is currently executing other program code.

5. The method of claim 2, wherein determining whether said each thread is executing program code that is capable of using the shared pointer to access the data structure further includes determining whether an indicator associated with said each thread indicates that said each thread has exited the program code.

6. The method of claim 2, wherein determining whether said each thread is executing program code that is capable of using the shared pointer to access the data structure includes determining whether an indicator associated with said each thread indicates that said each thread is currently executing the program code or that said each thread has exited the program code, wherein the indicator comprises a sequence number that is updated from a first value to a second value whenever said each thread enters the program code, and that is updated from the second value to a third value whenever said each thread exits the program code, and wherein determining whether the indicator associated with said each thread indicates that the first thread has exited the program code includes comparing the indicator with an earlier value thereof.

7. The method of claim 2, further comprising:

incrementing a sequence number associated with said each thread from a first value selected from a first set of values to a second value selected from a second set of values whenever said each thread enters the program code; and

incrementing the sequence number from the second value to a third value selected from the first set of values whenever said each thread exits the program code;

wherein waiting until said each of the plurality of threads is no longer using the shared pointer includes capturing a value of the sequence number prior to monitoring said each thread, and wherein determining whether said each thread is executing program code that is capable of using the shared pointer to access the data structure includes determining whether the sequence number associated with said each first thread has a value selected from the second set of values, and determining whether the sequence number has a value that differs from the captured value.

8. The method of claim 7, wherein the first set of values consists of odd numbers, and the second set of values consists of even numbers.

9. The method of claim 2, wherein the computer is a logically-partitioned computer, and wherein the program code comprises a partition manager accessible to a plurality of logical partitions in the computer.

10. The method of claim 9, wherein the program code comprises a non-dispatchable portion of the partition manager.

11. The method of claim 9, wherein the data structure comprises a partition control block used by the partition manager.

12. The method of claim 2, wherein setting the shared pointer to the predetermined value comprises setting the shared pointer to a null value.

13. The method of claim 2, wherein at least one of the plurality of threads executes on a single-threaded processor.

14. The method of claim 2, wherein at least one of the plurality of threads execute on a multithreaded processor.