Locking memory locations

• US 20040068607A1
• Filed: 10/07/2002
• Published: 04/08/2004
• Est. Priority Date: 10/07/2002
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Narad, Charles E.
• Application Number:
  US10/268,052
• Publication Number:
  US 20040068607A1
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A mechanism for implementing CAM-based implicit mutual exclusion locks, with a RAM array being dynamically allocated to provide waitlists on elements in the CAM.

Claims

1. A method comprising:

searching a content addressable memory (CAM) having a number of entries usable to identify locked memory locations to determine if a read-lock memory reference request is requesting access to a memory location that matches one of the locked memory locations; and

placing the read-lock memory reference request in a waitlist for an entry identifying a matched one of the locked memory locations if a match is found.

2. The method of claim 1, wherein placing comprises reading information in the entry to locate a waitlist entry at the end of the waitlist.

3. The method of claim 1 wherein the waitlist is indexed by requester ID values.

4. The method of claim 1 wherein each CAM entry is defined to include a tag field to indicate an address of a memory location that has a lock, an owner ID field to store an owner ID corresponding to a requester that currently owns the lock and a tail ID field to store tail ID corresponding to a most recent requester of the lock.

5. The method of claim 4 wherein the owner ID points to the head of the waitlist and the tail ID points to the tail of the waitlist.

6. The method of claim 4 wherein placing further comprises setting the tail ID to an ID of the requester of the read-lock memory reference request.

7. The method of claim 6 wherein the validity of the tail ID is indicated with a tail ID valid bit.

8. The method of claim 6 wherein the validity of the tail ID is detected when tail ID is not equal to owner ID.

9. The method of claim 1 further comprising allocating one of the content addressable memory entries to the read-lock memory reference request if no match is found.

10. The method of claim 9 further comprising associating a waitlist with the allocated entry.

11. The method of claim 9 further comprising storing in the allocated entry an address of the memory location to which the read-lock memory reference request requests access, and a requester ID for the read-lock memory reference request in a owner ID field and a tail ID field.

12. The method of claim 4 further comprising searching the entries to find a content addressable memory entry storing in the tag field therein a locked location specified in an unlock memory reference request

13. The method of claim 1 further comprising:

determining if there are one or more entries on a waitlist associated with the content addressable memory entry; and

if there are not one or more entries on the waitlist, indicating in the content addressable memory entry that the content addressable memory entry is available for allocation to a new read-lock memory reference request.

14. The method of claim 1 further comprising:

if there are one or more entries on the waitlist, changing an owner of the content addressable memory entry to a requester in the waitlist.

15. The method of claim 13 wherein determining if there are one or more entries in the waitlist comprises reading information stored in the content addressable memory entry.

16. The method of claim 1 wherein each entry storing a locked location is associated with a waitlist array from which a waitlist is constructed, and memory for each waitlist array is allocated from a single waitlist array.

17. The method of claim 16 wherein the waitlist array for an entry contains a number of entries based on a number of agents that may execute the read-lock memory reference requests.

18. The method of claim 1 wherein the number of content addressable memory entries is as great as the number of possible requesters of read-lock memory reference requests.

19. An article comprising:

a storage medium having stored thereon instructions that when executed by a machine result in the following;

searching a content addressable memory having a number of entries usable to identify locked memory locations, to determine if a read-lock memory reference request is requesting access to a memory location that matches one of the locked memory locations; and

placing the read-lock memory reference request on a waitlist for a matched one of the locked memory locations if a match is found.

20. The article of claim 19 wherein each entry includes a tag field to indicate an address of a memory location that has a lock, an owner ID field to store an owner ID corresponding to a requester that currently owns the lock and a tail ID field to store a tail ID corresponding to a most recent requester of the lock.

21. The article of claim 19 wherein the storage medium further stores instructions that when executed by the machine result in:

determining if there are one or more entries on a waitlist associated with the content addressable memory entry; and

if there are not one or more entries on the waitlist, indicating in the content addressable memory entry that the content addressable memory entry is available for allocation to a new read-lock memory reference request.

22. The article of claim 19 wherein the storage medium further stores instructions that when executed by the machine result in:

if there are one or more entries on the waitlist, changing an owner of the content addressable memory entry to a requester in the waitlist.

23. A controller comprising:

a content addressable memory lock unit having an array of entries usable to identify locked memory locations; and

control logic to associate the entries with waitlists that list read-lock memory reference requests that await access to the memory locations to which the entries correspond.

24. The controller of claim 23 wherein each entry is defined to include a tag field to indicate an address of a memory location that has a lock, an owner ID field to store an owner ID corresponding to a requester that currently owns the lock and a tail ID field to store a tail ID corresponding to a most recent requester of the lock.

25. The controller of claim 23, wherein the control logic comprises logic to assign ownership of an entry to an owner identified in a waitlist for the entry.