Making read-copy update free-running grace period counters safe against lengthy low power state sojourns

• US 8,407,503 B2
• Filed: 09/27/2010
• Issued: 03/26/2013
• Est. Priority Date: 09/27/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): CASSITY, ROBERT A
• Application Number:
  US12/891,196
• Publication Number:
  US 20120079301A1
• Time in Patent Office: 911 Days
• Field of Search: 713/321, 713/322, 713/323
• US Class Current: 713/321
• CPC Class Codes: G06F 1/32 Means for saving power

Abstract

A technique for making a free-running grace period counter safe against lengthy low power state processor sojourns. The grace period counter tracks grace periods that determine when processors that are capable executing read operations have passed through a quiescent state that guarantees the readers will no longer maintain references to shared data. Periodically, one or more processors may be placed in a low power state in which the processors discontinue performing grace period detection operations. Such processors may remain in the low power state for a complete cycle of the grace period counter. This scenario can potentially disrupt grace period detection operations if the processors awaken to see the same grace period counter value. To rectify this situation, processors in a low power state may be periodically awakened at a predetermined point selected prevent the low power state from extending for an entire roll over of the grace period counter.

Claims

1. In a computing system having at least two processors operatively coupled to a memory, a method for making a free-running grace period counter safe against lengthy low power state processor sojourns, comprising:

periodically executing read operations on said processors to reference shared data in said memory;

periodically executing update operations on said processors to update said shared data in said memory;

periodically executing grace period detection operations on said processors in order to reclaim memory by removing stale data elements or to perform other operations;

said grace period detection operations using a grace period counter to track grace periods, said grace periods determining when said processors executing said read operations have passed through a quiescent state that guarantees said read operations can no longer maintain references to said shared data;

said grace period counter being a free-running counter having an initial count value that is incremented to start a new grace period until a maximum count value is reached and said counter rolls over to said initial count value;

said grace period detection operations further including said processors periodically referencing said grace period counter, storing a per-processor copy of said grace period counter'"'"'s current grace period count value, and performing quiescent state detection processing for each new grace period;

periodically placing one or more of said processors in a low power state in which said processors discontinue referencing said grace period counter and do not perform quiescent state detection processing;

said processors being capable of experiencing an operational scenario in which said processors remain in said low power state for a complete cycle of said grace period counter, and in which said processors enter said low power state at a first grace period count value and return to a full power state after said grace period counter has rolled over and returned to a rollover grace period count value that is the same as said first grace period count value;

said operational scenario causing potential disruption of said grace period detection operations if said processors assume from their stored grace period count value being the same as said rollover grace period count that a grace period associated with said first grace period count value is still in force; and

preventing said potential disruption by periodically waking said processors in said low power state at a predetermined point that is selected prevent said low power state from extending for a time that allows said grace period counter to roll over.

2. A method in accordance with claim 1, wherein said preventing includes periodically checking said processors to determine whether a differential between a current count value of said grace period counter and said stored grace period value of said processors has reached a predetermined threshold, and awakening said processors if said threshold has been reached.

3. A method in accordance with claim 2, wherein said checking is performed at a predetermined check interval and said threshold is selected according to said check interval to ensure that said threshold will be reached and said one or more processors will be checked and awakened within one cycle of said grace period counter.

4. A method in accordance with claim 3, wherein said threshold is not more than one half of said grace period counter maximum count value.

5. A method in accordance with claim 4, wherein said checking is performed each grace period with respect to one or more processors, and said check interval is determined by the number of said processors that are checked per grace period.

6. A method in accordance with claim 1, wherein said preventing includes waking up all of said processors that are in a low power state during a single grace period after a predetermined grace period count interval has been reached.

7. A method in accordance with claim 1, wherein said preventing includes maintaining a fixed timeout period for each of said processors that enter said low power state, and waking up said processors from said low power state when said fixed timeout period has been reached.

8. A system, comprising:

one or more processors;

a memory coupled to said one or more processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processor to perform operations for making a free-running grace period counter safe against lengthy low power state processor sojourns, said operations comprising;

periodically executing read operations on said processors to reference shared data in said memory;

periodically executing update operations on said processors to update said shared data in said memory;

periodically executing grace period detection operations on said processors in order to reclaim memory by removing stale data elements or to perform other operations;

said grace period detection operations using a grace period counter to track grace periods, said grace periods determining when said processors executing said read operations have passed through a quiescent state that guarantees said read operations can no longer maintain references to said shared data;

said grace period counter being a free-running counter having an initial count value that is incremented to start a new grace period until a maximum count value is reached and said counter rolls over to said initial count value;

said grace period detection operations further including said processors periodically referencing said grace period counter, storing a per-processor copy of said grace period counter'"'"'s current grace period count value, and performing quiescent state detection processing for each new grace period;

periodically placing one or more of said processors in a low power state in which said processors discontinue referencing said grace period counter and do not perform quiescent state detection processing;

said processors being capable of experiencing an operational scenario in which said processors remain in said low power state for a complete cycle of said grace period counter, and in which said processors enter said low power state at a first grace period count value and return to a full power state after said grace period counter has rolled over and returned to a rollover grace period count value that is the same as said first grace period count value;

said operational scenario causing potential disruption of said grace period detection operations if said processors assume from their stored grace period count value being the same as said rollover grace period count that a grace period associated with said first grace period count value is still in force; and

preventing said potential disruption by periodically waking said processors in said low power state at a predetermined point that is selected prevent said low power state from extending for a time that allows said grace period counter to roll over.

9. A system in accordance with claim 8, wherein said preventing includes periodically checking said processors to determine whether a differential between a current count value of said grace period counter and said stored grace period value of said processors has reached a predetermined threshold, and awakening said processors if said threshold has been reached.

10. A system in accordance with claim 9, wherein said checking is performed at a predetermined check interval and said threshold is selected according to said check interval to ensure that said threshold will be reached and said one or more processors will be checked and awakened within one cycle of said grace period counter.

11. A system in accordance with claim 10, wherein said threshold is not more than one half of said grace period counter maximum count value.

12. A system in accordance with claim 11, wherein said checking is performed each grace period with respect to one or more processors, and said check interval is determined by the number of said processors that are checked per grace period.

13. A system in accordance with claim 8, wherein said preventing includes waking up all of said processors that are in a low power state during a single grace period after a predetermined grace period count interval has been reached.

14. A system in accordance with claim 8, wherein said preventing includes maintaining a fixed timeout period for each of said processors that enter said low power state, and waking up said processors from said low power state when said fixed timeout period has been reached.

15. A computer program product, comprising:

one or more machine-useable storage media;

program instructions provided by said one or more media for programming a data processing platform to perform operations for making a free-running grace period counter safe against lengthy low power state processor sojourns, said operations comprising;

periodically executing read operations on said processors to reference said shared data in said memory;

periodically executing update operations on said processors to update said shared data in said memory;

periodically executing grace period detection operations on said processors in order to reclaim memory by removing stale data elements or to perform other operations;

said grace period detection operations using a grace period counter to track grace periods, said grace periods determining when said processors executing said read operations have passed through a quiescent state that guarantees said read operations can no longer maintain references to said shared data;

said grace period counter being a free-running counter having an initial count value that is incremented to start a new grace period until a maximum count value is reached and said counter rolls over to said initial count value;

said grace period detection operations further including said processors periodically referencing said grace period counter, storing a per-processor copy of said grace period counter'"'"'s current grace period count value, and performing quiescent state detection processing for each new grace period;

periodically placing one or more of said processors in a low power state in which said processors discontinue referencing said grace period counter and do not perform quiescent state detection processing;

said processors being capable of experiencing an operational scenario in which said processors remain in said low power state for a complete cycle of said grace period counter, and in which said processors enter said low power state at a first grace period count value and return to a full power state after said grace period counter has rolled over and returned to a rollover grace period count value that is the same as said first grace period count value;

said operational scenario causing potential disruption of said grace period detection operations if said processors assume from their stored grace period count value being the same as said rollover grace period count that a grace period associated with said first grace period count value is still in force; and

preventing said potential disruption by periodically waking said processors in said low power state at a predetermined point that is selected prevent said low power state from extending for a time that allows said grace period counter to roll over.

16. A computer program product in accordance with claim 15, wherein said preventing includes periodically checking said processors to determine whether a differential between a current count value of said grace period counter and said stored grace period value of said processors has reached a predetermined threshold, and awakening said processors if said threshold has been reached.

17. A computer program product in accordance with claim 16, wherein said checking is performed at a predetermined check interval and said threshold is selected according to said check interval to ensure that said threshold will be reached and said one or more processors will be checked and awakened within one cycle of said grace period counter.

18. A computer program product in accordance with claim 17, wherein said checking is performed each grace period with respect to one or more processors, and said check interval is determined by the number of said processors that are checked per grace period.

19. A computer program product in accordance with claim 15, wherein said preventing includes waking up all of said processors that are in a low power state during a single grace period after a predetermined grace period count interval has been reached.

20. A computer program product in accordance with claim 15, wherein said preventing includes maintaining a fixed timeout period for each of said processors that enter said low power state, and waking up said processors from said low power state when said fixed timeout period has been reached.