Scalable rundown protection for object lifetime management

• US 7,571,288 B2
• Filed: 07/03/2006
• Issued: 08/04/2009
• Est. Priority Date: 06/13/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Christiansen, Neal R., Pudipeddi, Ravisankar, Clift, Neill
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US11/480,799
• Publication Number:
  US 20060253655A1
• Time in Patent Office: 1,128 Days
• Field of Search: 711/133, 711/145, 711/147, 711/148, 711/152, 711/156, 709/248, 713/375
• US Class Current: 711/152
• CPC Class Codes: G06F 12/0261 using reference counting

Abstract

Object rundown protection that scales with the number of processors in a shared-memory computer system is disclosed. Prior to object rundown, a cache-aware reference count data structure is used to prevent cache-pinging that would otherwise result from data sharing across processors in a multiprocessor computer system. In this data structure, a counter of positive references and negative dereferences, aligned on a particular cache line, is maintained for each processor. When an object is to be destroyed, a rundown wait process is begun, during which new references on the object are prohibited, and the total number of outstanding references is added to an on-stack global counter. Destruction is delayed until the global reference count is reduced to zero. In an implementation on non-uniform memory access multiprocessor machines, each processor'"'"'s reference count is additionally allocated in a region of main memory that is physically close to that processor.

Claims

1. A computer memory device including a data structure stored therein, wherein the data structure is arranged to represent a cache-aware per-processor rundown reference count in a shared-memory multiprocessor computer system, the data structure comprising at least a first data field representing an integer count of positive references and negative dereferences taken on an object for preventing the object from being destroyed or otherwise rendered inaccessible in a multiprocessor environment with a shared memory while at least one reference on the object exists, wherein requests for new references on the object and releases of existing references on the object are managed based on the integer count and a global reference count, wherein a least significant bit of the first data field is used to indicate whether a rundown wait is in progress, and wherein the requests for the new references are managed by:

refusing to grant a new reference if a rundown wait is in progress; and

updating the integer count associated with the processor by atomically replacing the integer count with a new integer count reflecting an addition of the at least one new reference if a rundown wait is not in progress and a processor executes a request for at least one new reference.

2. The computer memory device of claim 1, wherein the first data field has a width capable of holding a main memory address.

3. The computer memory device of claim 1, wherein the most significant bit of the first data field is used as a sign bit, and wherein the data structure is maintained in a portion of a main memory that is physically proximate to a corresponding processor.

4. The computer memory device of claim 1, further comprising a second data field having a size large enough to ensure that the data structure is the size of a cache line on the corresponding processor.

10. The computer memory device of claim 1, wherein the integer count is a per-processor count.

11. The computer memory device of claim 1, wherein the least significant bit being 0 in the integer count indicates that a rundown wait is not in progress, and the least significant bit being 1 indicates that a rundown wait is in progress, and wherein the least significant bit of each integer count is initialized to 0.

12. The computer memory device of claim 1, wherein the least significant bit is utilized for executing a rundown wait routine that establishes the global reference count when the object is to be destroyed or otherwise rendered inaccessible.

13. The computer memory device of claim 1, wherein the computer memory is part of a centralized shared memory multiprocessor system.

14. The computer memory device of claim 13, wherein each integer count is stored in a region of main memory to which the processor associated with the count has fast access.

15. The computer memory device of claim 1, wherein the object is one of a process, a thread and a loaded driver.

5. A computer-readable medium having stored thereon a data structure comprising:

a first data field storing a count of processors in a shared-memory multiprocessor computer system;

a second data field having size large enough to ensure that a third data field begins at a point aligned on a cache line boundary for the processors in the system; and

the third data field containing at least one pointer to a plurality of per-processor reference count objects, wherein each object represents at least an integer count of positive references and negative dereferences taken on an object pursuant to requests executed by a particular processor in the system, and there are at least as many objects as there are processors.

6. The computer-readable medium of claim 5, wherein the third data field comprises a pointer to an array, and wherein the per-processor reference count objects are the elements of the array.

7. The computer-readable medium of claim 5, wherein the third data field comprises a pointer to an array of pointers, and wherein each pointer in the array of pointers points to a respective per-processor reference count object.

8. A computer-readable medium representing a rundown wait block, having stored thereon a data structure comprising at least a first data field storing a global count of outstanding references taken on an object by processors in a shared-memory multiprocessor computer system, further comprising a second data field storing a synchronization primitive permitting a rundown wait process to block indefinitely until the process is signaled to wake up.

9. The computer-readable medium of claim 8, wherein the synchronization primitive is provided by an operating system executed on the computer system.