Eliminating memory corruption when performing tree functions on multiple threads

• US 7,036,125 B2
• Filed: 08/13/2002
• Issued: 04/25/2006
• Est. Priority Date: 08/13/2002
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco, Basso, Claude, Verrilli, Colin Beaton, Davis, Gordon Taylor, Patel, Piyush Chunilal, Randall, Grayson Warren, Rovner, Sonia Kiang, Brown, Matthew William Kilpatrick
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US10/217,529
• Publication Number:
  US 20040032867A1
• Time in Patent Office: 1,351 Days
• Field of Search: 718/100, 718/102, 718/104, 718/107, 718/101, 718/103, 709/201, 709/203, 709/223, 709/224, 709/204, 709/217, 709/219, 709/220, 711/152, 711/155, 711/163, 711/104, 711/105, 711/154
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method, system and computer program product for eliminating memory corruption when performing multi-threaded tree operations. A network processor may receive a command to perform a tree operation on a tree on one or more of multiple threads. Upon performing the requested tree operation, the network processor may lock one or more resources during a portion of the execution of the requested tree operation using one or more semaphores. A semaphore may refer to a flag used to indicate whether to “lock” or make available the resource associated with the semaphore. Locking may refer to preventing the resource from being available to other threads. Hence, by locking one or more resources during a portion of the tree operation, memory corruption may be eliminated in a multiple thread system while preventing these resources from being used by other threads for a minimal amount of time.

Claims

1. A method for eliminating memory corruption comprising the steps of:

receiving a command to perform a tree operation on a tree associated with a thread; and

locking one or more resources associated with said requested tree operation during an execution of said requested tree operation using a first and a second semaphore, wherein said one or more resources are associated with said first semaphore and said second semaphore, wherein the step of locking further comprises the steps of;

indicating whether a resource associated with said first semaphore is locked or is available to be accessed by other threads based on a value of said first semaphore; and

indicating whether a resource associated with said second semaphore during a portion of said execution of said requested tree operation is locked or is available to be accessed by other threads based on a value of said second semaphore;

wherein said resource associated with said second semaphore is locked during a portion of said execution of said requested tree operation, wherein said resource associated with said second semaphore is made available during a remaining portion of said execution of said requested tree operation.

2. The method as recited in claim 1, wherein said one or more resources comprises at least one of the following:

direct table, list of available leaves to be used, a list of available Pattern Search Control Block'"'"'s (PSCB'"'"'s) to be used, address of a leaf, and a list of active leaves in a particular tree, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB.

3. The method as recited in claim 1, wherein said requested tree operation is at least one of the following:

insert leaf, update leaf, read leaf and delete leaf.

4. The method as recited in claim 3, wherein during said insert leaf operation the method further comprises the steps of:

locking a direct table during said insert leaf operation, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB; and

locking a list of available leaves during a portion of said insert leaf operation.

5. The method as recited in claim 4, wherein said second semaphore is associated with an address of said list of available leaves during said insert leaf operation, wherein a first value of said second semaphore indicates to lock said list of available leaves, wherein a second value of said second semaphore indicates to make available said list of available leaves to other threads, wherein said list of available leaves is locked and made available at different times during said insert leaf operation.

6. The method as recited in claim 3, wherein during said read leaf operation the method further comprises the step of:

locking an address of a leaf to be read during a portion of said read leaf operation.

7. The method as recited in claim 6, wherein said second semaphore is associated with said address of said leaf to be read during said read leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.

8. The method as recited in claim 3, wherein during said update leaf operation the method further comprises the step of:

locking an address of a leaf to be updated during a portion of said update leaf operation.

9. The method as recited in claim 8, wherein said second semaphore is associated with said address of said leaf to be updated during said update leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.

10. A computer program product embodied in a machine readable medium for eliminating memory corruption comprising the programming steps of:

receiving a command to perform a tree operation on a tree associated with a thread; and

locking one or more resources associated with said requested tree operation during an execution of said requested tree operation using a first and a second semaphore, wherein said one or more resources are associated with said first semaphore and said second semaphore, wherein the programming step of locking further comprises the programming steps of;

indicating whether a resource associated with said first semaphore is locked or is available to be accessed by other threads based on a value of said first semaphore; and

indicating whether a resource associated with said second semaphore during a portion of said execution of said requested tree operation is locked or is available to be accessed by other threads based on a value of said second semaphore;

wherein said resource associated with said second semaphore is locked during a portion of said execution of said requested tree operation, wherein said resource associated with said second semaphore is made available during a remaining portion of said execution of said requested tree operation.

11. The computer program product as recited in claim 10, wherein said one or more resources comprises at least one of the following:

direct table, list of available leaves to be used, a list of available Pattern Search Control Block'"'"'s (PSCB'"'"'s) to be used, address of a leaf, and a list of active leaves in a particular tree, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB.

12. The computer program product as recited in claim 10, wherein said requested tree operation is at least one of the following:

insert leaf, update leaf, read leaf and delete leaf.

13. The computer program product as recited in claim 12, wherein during said insert leaf operation the computer program product further comprises the programming steps of:

locking a direct table during said insert leaf operation, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB; and

locking a list of available leaves during a portion of said insert leaf operation.

14. The computer program product as recited in claim 13, wherein said second semaphore is associated with an address of said list of available leaves during said insert leaf operation, wherein a first value of said second semaphore indicates to lock said list of available leaves, wherein a second value of said second semaphore indicates to make available said list of available leaves to other threads, wherein said list of available leaves is locked and made available at different times during said insert leaf operation.

15. The computer program product as recited in claim 12, wherein during said read leaf operation the computer program product further comprises the programming step of:

locking an address of a leaf to be read during a portion of said read leaf operation.

16. The computer program product as recited in claim 15, wherein said second semaphore is associated with said address of said leaf to be read during said read leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.

17. The computer program product as recited in claim 12, wherein during said update leaf operation the computer program product further comprises the programming step of:

locking an address of a leaf to be updated during a portion of said update leaf operation.

18. The computer program product as recited in claim 17, wherein said second semaphore is associated with said address of said leaf to be updated during said update leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.

19. A network processor, comprising:

a memory unit operable for storing a computer program for eliminating memory corruption; and

a processor coupled to said memory unit, wherein said processor, responsive to said computer program, comprises;

circuitry operable for receiving a command to perform a tree operation on a tree associated with a thread; and

circuitry operable for locking one or more resources associated with said requested tree operation during an execution of said requested tree operation using a first and a second semaphore, wherein said one or more resources are associated with said first semaphore and said second semaphore, wherein said circuitry operable for locking further comprises;

circuitry operable for indicating whether a resource associated with said first semaphore is locked or is available to be accessed by other threads based oh a value of said first semaphore; and

circuitry operable for indicating whether a resource associated with said second semaphore during a portion of said execution of said requested tree operation is locked or is available to be accessed by other threads based on a value of said second semaphore;

wherein said resource associated with said second semaphore is locked during a portion of said execution of said requested tree operation, wherein said resource associated with said second semaphore is made available during a remaining portion of said execution of said requested tree operation.

20. The system as recited in claim 19, wherein said one or more resources comprises at least one of the following:

direct table, list of available leaves to be used, a list of available Pattern Search Control Block'"'"'s (PSCB'"'"'s) to be used, address of a leaf, and a list of active leaves in a particular tree, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB.

21. The system as recited in claim 19, wherein said requested tree operation is at least one of the following:

insert leaf, update leaf, read leaf and delete leaf.

22. The system as recited in claim 21, wherein during said insert leaf operation said processor further comprises:

circuitry operable for locking a direct table during said insert leaf operation, wherein said direct table is a table storing one or more of the following;

an address of a leaf and an address of a PSCB; and

circuitry operable for locking a list of available leaves during a portion of said insert leaf operation.

23. The system as recited in claim 22, wherein said second semaphore is associated with an address of said list of available leaves during said insert leaf operation, wherein a first value of said second semaphore indicates to lock said list of available leaves, wherein a second value of said second semaphore indicates to make available said list of available leaves to other threads, wherein said list of available leaves is locked and made available at different times during said insert leaf operation.

24. The system as recited in claim 21, wherein during said update leaf operation said processor further comprises:

circuitry operable for locking an address of a leaf to be updated during a portion of said update leaf operation.

25. The system as recited in claim 24, wherein said second semaphore is associated with said address of said leaf to be updated during said update leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.

26. The system as recited in claim 21, wherein during said read leaf operation said processor further comprises:

circuitry operable for locking an address of a leaf to be read during a portion of said read leaf operation.

27. The system as recited in claim 26, wherein said second semaphore is associated with said address of said leaf to be read during said read leaf operation, wherein a first value of said second semaphore indicates to lock said address of said leaf, wherein a second value of said second semaphore indicates to make available said address of said leaf to other threads, wherein said address of said leaf is locked and made available at different times during said update leaf operation.