Using data in elements of a singly linked list without a lock in a multithreaded environment

• US 8,141,086 B2
• Filed: 06/06/2008
• Issued: 03/20/2012
• Est. Priority Date: 06/06/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cocks, Martin William John, Merrison, Felicity Jane
• Primary Examiner(s): To, Jennifer
• Assistant Examiner(s): WAI, ERIC CHARLES
• Application Number:
  US12/134,288
• Publication Number:
  US 20090307694A1
• Time in Patent Office: 1,383 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and system for validating a scan of a chain in a multithreaded environment. A modification counter and an anchor address are atomically copied from the chain'"'"'s header into a first variable (browse counter) and second variable, respectively. The second variable is set to a next address stored in a current element of the chain. The next address references a next element of the chain. The browse counter is incremented. If the browse counter is greater than a current value of the modification counter (M.Counter) and if the second variable includes a valid address, then the scan is valid up to the current element, the scan continues with the next element as the current element, and the process repeats starting with setting the second variable to the next address. Otherwise, if the browse counter is less than or equal to M.Counter, then the scan is invalid.

Claims

1. A computer-implemented method for validating a scan of an unused element chain in a multithreaded computing environment, said method comprising:

executing, by a computing system, a first thread and a second thread in said multithreaded computing environment;

atomically copying, by a computing system, using said first thread, and from a header of said unused element chain (chain), a modification counter into a first variable and an anchor address into a second variable, wherein said atomically copying includes initially setting a browse counter in said first variable to said modification counter, and wherein said chain is a singly linked list data structure;

setting, by said computing system, using said first thread and subsequent to said atomically copying, said second variable to a next address stored in a current element of said chain, wherein said next address references a next element of said chain, wherein said current element is initially a first element of said chain, and wherein said first element is referenced by said anchor address;

incrementing, by said computing system, using said first thread and subsequent to said atomically copying, said browse counter stored in said first variable to indicate an advance of said scan;

determining, by said computing system and subsequent to said setting and said incrementing, that said browse counter is greater than a current value of said modification counter, wherein said current value of said modification counter indicates any modification made to said chain by said second thread;

determining, by said computing system and in response to said determining that said browse counter is greater than said current value of said modification counter, that said scan of said chain is valid up to said current element of said chain;

concluding, by said computing system, said scan of said chain; and

storing, by said computing system and in response to said concluding said scan, an indication of a result of said scan, wherein said indication of said result is selected from the group consisting of an indication that said scan is valid and an indication that said next address is an invalid address, and wherein said storing said indication of said result includes storing said indication of said result in a first computer data storage unit coupled to said computing system or in a second computer data storage unit coupled to another computing system.

2. The method of claim 1, wherein said concluding said scan comprises completing, by said computing system, said scan of said chain while said browse counter is greater than said current value of said modification counter, and wherein said indication of said result of said scan is said indication that said scan is valid.

3. The method of claim 1, further comprising storing said chain in a computer data storage area that is not freed while said chain exists.

4. The method of claim 1, further comprising:

locating, by said computing system and prior to said atomically copying, said header of said chain, wherein said header and said chain are stored in a computer data storage unit;

determining, by said computing system, subsequent to said atomically copying, and prior to said setting said second variable, that said anchor address in said second variable is valid based on a predefined criterion;

determining, by said computing system and subsequent to said setting said second variable to said next address, that said next address is valid based on said predefined criterion; and

continuing said scan with a next element in said chain in response to said determining that said next address is valid.

5. The method of claim 1, further comprising:

locating, by said computing system and prior to said atomically copying, said header of said chain, wherein said header and said chain are stored in a computer data storage unit;

determining, by said computing system, subsequent to said atomically copying, and prior to said setting said second variable, that said anchor address in said second variable is valid based on a predefined condition being false;

determining, by said computing system and subsequent to said setting said second variable, that said next address is not valid based on said predefined condition being true; and

determining, by said computing system and subsequent to said determining that said next address is not valid, that said next address is not a null pointer,

wherein said concluding said scan comprises stopping said scan by said computing system and in response to said determining that said next address is not valid and in response to said determining that said next address is not said null pointer, and

wherein said indication of said result of said scan is said indication that said next address is an invalid address.

6. The method of claim 5, wherein said predefined condition is a most significant bit of said second variable is set.

7. The method of claim 1, wherein said first variable and said second variable are stored in a first computer data storage unit coupled to said computing system or in a second computer data storage unit coupled to another computing system, and wherein said chain is stored in said first computer data storage unit or said second computer data storage unit.

8. The method of claim 1, wherein said modification counter is a running count of one or more actions performed on said chain by said second thread, and wherein each action of said one or more actions is an action selected from the group of an addition of a new element as a new first element of said chain and a removal of said first element from said chain.

9. A computing system comprising a processor coupled to a computer-readable memory unit, said memory unit comprising a software application, said software application comprising instructions that when executed by said processor implement the method of claim 1.

10. A computer program product, comprising:

a tangible, computer-readable storage device having a computer-readable program code stored therein, said computer-readable program code containing instructions that when executed by a processor of a computing system implement a method of validating a scan of an unused element chain in a multithreaded computing environment, said method comprising;

executing a first thread and a second thread in said multithreaded computing environment;

atomically copying, using said first thread and from a header of said unused element chain (chain), a modification counter into a first variable and an anchor address into a second variable, wherein a result of said atomically copying is initially setting a browse counter in said first variable to said modification counter, and wherein said chain is a singly linked list data structure;

setting, using said first thread and subsequent to said atomically copying, said second variable to a next address stored in a current element of said chain, wherein said next address references a next element of said chain, wherein said current element is initially a first element of said chain, and wherein said first element is referenced by said anchor address;

incrementing, using said first thread and subsequent to said atomically copying, said browse counter stored in said first variable to indicate an advance of said scan to said next element of said chain;

determining, subsequent to said setting and said incrementing, that said browse counter is greater than a current value of said modification counter, wherein said current value of said modification counter indicates any modification made to said chain by said second thread;

determining, in response to said determining that said browse counter is greater than said current value of said modification counter, that said scan of said chain is valid up to said next element of said chain;

concluding said scan of said chain; and

storing, in response to said concluding said scan, an indication of a result of said scan, wherein said indication of said result is selected from the group consisting of an indication that said scan is valid and an indication that said next address is an invalid address, and wherein said storing said indication of said result includes storing said indication of said result in a first computer data storage unit coupled to said computing system or in a second computer data storage unit coupled to another computing system.

11. The program product of claim 10, wherein said concluding said scan comprises completing said scan of said chain while said browse counter is greater than said current value of said modification counter, and wherein said indication of said result of said scan is said indication that said scan is valid.

12. The program product of claim 10, wherein said method further comprises storing said chain in a computer data storage area that is not freed while said chain exists.

13. The program product of claim 10, wherein said method further comprises:

locating, prior to said atomically copying, said header of said chain, wherein said header and said chain are stored in a computer data storage unit;

determining, subsequent to said atomically copying and prior to said setting said second variable, that said anchor address in said second variable is valid based on a predefined criterion;

determining, subsequent to said setting said second variable to said next address, that said next address is valid based on said predefined criterion; and

continuing said scan with said next element of said chain in response to said determining that said next address is valid.

14. The program product of claim 10, wherein said method further comprises:

locating, prior to said atomically copying, said header of said chain, wherein said header and said chain are stored in a computer data storage unit;

determining, subsequent to said atomically copying and prior to said setting said second variable, that said anchor address in said second variable is valid based on a predefined condition being false;

determining, subsequent to said setting said second variable, that said next address is not valid based on said predefined condition being true; and

determining, subsequent to said determining that said next address is not valid, that said next address is not a null pointer,

wherein said concluding said scan comprises stopping said scan in response to said determining that said next address is not valid and in response to said determining that said next address is not said null pointer, and

wherein said indication of said result of said scan is said indication that said next address is an invalid address.

15. A computer-implemented method for detecting an invalid scan of an unused element chain in a multithreaded computing environment, said method comprising:

executing, by a computing system, a first thread and a second thread in said multithreaded computing environment;

atomically copying, by a computing system, using said first thread, and from a header of said unused element chain (chain), a modification counter into a first variable and an anchor address into a second variable, wherein said atomically copying includes initially setting a browse counter in said first variable to said modification counter, wherein said anchor address references a first element of a plurality of elements included in said chain, and wherein said chain is a singly linked list data structure;

initially setting a current element of said chain as said first element;

determining, by said computing system, using said first thread, and subsequent to said atomically copying, that said anchor address in said second variable is valid based on a predefined criterion;

setting, by said computing system, using said first thread, and subsequent to said determining that said anchor address is valid, said second variable to a next address included in said current element of said chain, wherein said next address references a next element of said chain;

incrementing, by said computing system, using said first thread, and subsequent to said determining that said anchor address is valid, said browse counter stored in said first variable;

comparing, by said computing system and subsequent to said incrementing, said browse counter stored in said first variable to a current value of said modification counter, wherein said current value of said modification counter indicates any modification made to said chain by said second thread;

updating said current element to be said next element;

updating, subsequent to said updating said current element, said next element to be an element of said plurality of elements that is referenced by an address included in said current element;

repeating said setting, said incrementing, said comparing, said updating said current element, and said updating said next element until a result of said comparing is that said browse counter is less than or equal to said current value of said modification counter;

determining, by said computing system and in response to said comparing, that said browse counter is less than or equal to said current value of said modification counter;

determining, by said computing system and in response to said determining that said browse counter is less than or equal to said current value of said modification counter, that said scan of said chain is invalid; and

storing, in response to said determining that said scan is invalid, an indication that said scan is invalid, wherein said storing is performed in a first computer data storage unit coupled to said computing system or in a second computer data storage unit coupled to another computing system.

16. The method of claim 15, further comprising displaying, in response to said determining that said scan is invalid, said indication that said scan is invalid, wherein said displaying is performed at a first display device coupled to said computing system or at a second display device coupled to another computing system.

17. The method of claim 15, further comprising re-scanning said chain, wherein said re-scanning includes performing a second scan of said chain starting at an element referenced by said anchor address.

18. The method of claim 15, further comprising removing, using said second thread, said first element from said chain, wherein said removing is performed concurrently with at least one action performed by said first thread.

19. The method of claim 15, further comprising adding, using said second thread, an element as a new first element of said chain, wherein said adding is performed concurrently with at least one action performed by said first thread.