Adapting RCU for real-time operating system usage

• US 20060090104A1
• Filed: 09/29/2004
• Published: 04/27/2006
• Est. Priority Date: 09/29/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Sarma, Dipankar
• Granted Patent: US 7,287,135 B2
• Time in Patent Office: Days
• US Class Current: 714/718
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

A system and method is provided to support immediate freeing of a designated element from memory. Following a process of designating an element for removal from a data-structure, conditional limitations are used to determine if immediate freeing of the element from memory is available. The conditional limitations include determining that the instruction originates from a uniprocessor computer system. In addition, the conditional limitations include a determination as to whether a call_rcu primitive or synchronize_kernel primitive may be omitted, or whether the computer implemented instruction is operating in an interrupt handler. If the conditional limitations are met, the designated element may be immediately freed from memory.

Claims

1. A method for operating a single CPU computer system comprising:

traversing an RCU protected data structure by a first function without other processes being made aware of said traversal;

removing an element from said data structure;

determining if said element can be immediately freed from memory; and

immediately freeing said element from memory in response to a positive determination.

2. The method of claim 1, wherein the step of conditionally determining if said element can be immediately freed from memory includes determining if said element can be removed from said data structure and freed from memory by a second function operating in said data structure concurrently with said first function.

3. The method of claim 1, wherein the step of conditionally determining if said element can be immediately freed from memory includes determining if an interrupt handler can operate concurrently with said first function.

4. The method of claim 2, further comprising distinguishing between a uniprocessor and a multiprocessor computer system, and deferring freeing of said element in a uniprocessor computer system if said element can be removed from said data structure and freed from memory by a second function operating in said data structure concurrently with said first function.

5. The method of claim 2, further comprising said second function passing a flag to said first function to approve immediate freeing of said element from memory in response to an ability of a second function operating in said data structure to remove said element from said data structure and free said element from memory.

6. The method of claim 3, further comprising deferring freeing from memory of said element if said second function is operating in an interrupt handler and said interrupt handler is able to operate concurrently with said first function.

7. The method of claim 4, further comprising said second function passing a flag to said first function to determine immediate freeing of said element from memory in response to an ability of a second function concurrently operating in an interrupt handler to remove said element from said data structure and free said element from memory wherein said interrupt handler is unable to operate concurrently with said first function and remove said element from said traversed data structure.

10. The system of claim 1, wherein said memory manager is adapted to determine if an interrupt handler can operate concurrently with said first function.

13. The system of claim 10, further comprising a deferral manager adapted to delay immediate freeing of said element from memory if said second function is in an interrupt handler and said interrupt handler is able to operate concurrently with said first function.

14. The system of claim 1, further comprising a flag adapted to be passed from said second function to said first function to determine immediate freeing of said element from memory in response to an ability of a second function concurrently operating in an interrupt handler to remove said element from said data structure and free said element from memory, wherein said interrupt handler is unable to operate concurrently with said first function and remove said element from said traversed data structure.

8. A single CPU computer system comprising:

a first function adapted to traverse an RCU protected data structure without awareness by other processes of said traversal;

an element adapted to be removed from said data structure;

a memory manager adapted to determine if said element can be immediately freed from memory; and

a removal manager adapted to immediately free said element from memory in response to receipt of a positive determination from said memory manager.

9. The system of claim 8, wherein said memory manager is adapted to determine if said element can be removed from said data structure and freed from memory by a second function adapted to operate concurrently in said data structure with said first function.

11. The system of claim 9, further comprising a system manager adapted to defer freeing of said element in a uniprocessor computer system if said element can be removed from said data structure and freed from memory by a second function operating in said data structure concurrently with said first function.

12. The system of claim 9, further comprising a flag adapted to be passed from said second function to said first function for approval of immediate freeing of said element from memory in response to an ability of a second function operating in said data structure to remove said element from said data structure and free said element from memory.

15. An article comprising:

a computer-readable signal-bearing medium;

means in the medium for traversing an RCU protected data structure by a first function without awareness by other processes of said traversal;

means in the medium for removing an element from said data structure;

means in the medium for determining if said element can be immediately freed from memory; and

means in the medium for immediately freeing said element from memory in response to a positive determination.

16. The article of claim 15, wherein said medium is selected from a group consisting of:

a recordable data storage medium and a modulated carrier signal.

17. The article of claim 15, wherein said means for conditionally determining if said element can be immediately freed from memory includes means for determining if said element can be removed from said data structure and freed from memory by a second function concurrently operating in said data structure with said first function.

18. The article of claim 15, wherein said means for conditionally determining if said element can be immediately freed from memory includes means for determining if an interrupt handler can concurrently operate with said first function.

19. The article of claim 17, further comprising means in the medium for distinguishing between a uniprocessor and a multiprocessor computer system, and means for deferring freeing of said element in a uniprocessor computer system if said element can be removed from said data structure and freed from memory by a second function concurrently operating in said data structure with said first function.

20. The article of claim 17, further comprising means in the medium for said second function approving immediate freeing of said element from memory in response to an ability of said second function to remove said element from said data structure and free said element from memory.

21. The article of claim 18, further comprising means in the medium for deferring freeing of said element from said data structure in response to a determination of said second function operating within an interrupt handler and an ability of said interrupt handler to concurrently operate with said first function.

22. The article of claim 19, further comprising means in the medium for said second function determining immediate freeing of said element from memory in response to an ability of said second operating concurrently in an interrupt handler to remove said element from sand data structure and free said element from memory, wherein said interrupt handler is unable to operate concurrently with said first function and remove said element from said traversed data structure.