Zero overhead resource locks with attributes

• US 7,290,105 B1
• Filed: 12/16/2002
• Issued: 10/30/2007
• Est. Priority Date: 12/16/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kerr, Darren, Marshall, John W., Jeter, Robert E. Jr., Potter, Kenneth H., Changela, Manish
• Primary Examiner(s): Kim; Matthew
• Assistant Examiner(s): TSAI, SHENG JEN
• Application Number:
  US10/320,120
• Time in Patent Office: 1,779 Days
• Field of Search: 711/163, 711/150, 711/159, 711/165
• US Class Current: 711/163
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique efficiently accesses locks associated with resources in a computer system. A processor accesses (e.g., acquires or releases) a lock by specifying and issuing a request to a resource controller, the request containing attribute and resource location information associated with the lock. In response, the resource controller applies the information contained in the request to an outstanding lock data structure to determine if the request should be blocked, blocked as a pending writer, allowed or an error condition. If the request is blocked, it remains blocked until the outstanding lock blocking the request is released. If the request is allowed, operations associated with the request are performed.

Claims

1. A method for accessing a lock associated with a resource in a computer system, the method comprising the steps of:

generating, at a particular entity, a request comprising attribute and resource information associated with the lock, the attribute information denoting a type of lock operation;

enqueuing the request on a request queue that is associated with the particular entity at resource controller, the request queue associated with the particular entity being one of a plurality of request queues at the resource controller;

enqueuing at least one second request on a second request queue of the plurality of request queues at the resource controller, the second request associated with a second entity;

tracking the order in which requests reach the head of the request queue that is associated with the particular entity and the second request queue that is associated with the second entity;

when the request reaches the head of the request queue that is associated with the particular entity, applying, by a resource controller, the attribute and resource information to an outstanding lock data structure to determine if the request is allowed; and

if the request is allowed, performing a lock operation contained in the information; and

if the request is blocked, holding the request in the request queue associated with the particular entity at the resource controller, and subsequently selecting the request to be executed in response to the request being the oldest request in any of the plurality of request queues that is becoming allowed.

2. A method as defined in claim 1 wherein the resource is a memory.

3. A method as defined in claim 1 wherein the information comprises a memory address.

4. A method as defined in claim 3 wherein the information comprises a lock size.

5. A method as defined in claim 4 wherein the step of generating comprises the steps of:

selecting a memory lock register containing a lock operation value and a lock size value; and

generating the lock operation and the lock size contained in the request from the lock operation value and the lock size value contained in the memory lock register, respectively.

6. A method as defined in claim 3 wherein the step of generating comprises the steps of:

decoding an instruction wherein the instruction specifies a memory address value and a lock operation value;

generating the memory address and the lock operation contained in the request from the memory address value and the lock operation value specified by the instruction, respectively.

7. A method as defined in claim 6 wherein the memory address value and lock operation value are contained in the instruction.

8. A method as defined in claim 6 comprising the step of:

generating a memory operation contained in the request from an operation code (opcode) contained in the instruction.

9. A method as defined in claim 1 wherein the outstanding lock data structure is a table comprising one or more outstanding lock data structure entries.

10. A method as defined in claim 1 wherein the entity is a processor.

11. A method as defined in claim 1 wherein the entity is a thread.

12. A method as defined in claim 9 wherein each outstanding lock data structure entry comprises a lock address, a lock type, and a lock segment size.

22. The method as defined in claim 1 wherein the lock operation is selected from the group consisting of:

a lock clear operation, a get exclusive lock operation, a get shared-reader lock operation, and a get exclusive-writer lock operation.

23. The method as defined in claim 1 wherein the attribute information is associated with a type of lock selected from the group consisting of:

an exclusive lock, a shared-reader lock, and an exclusive-writer lock.

24. The method as defined in claim 1 wherein the computer system is a programmable processing engine of a router.

25. The method as defined in claim 4 wherein the lock size specifies one of a plurality of different sizes of memory segment that may be locked, the memory segment to include the memory address associated with the lock request.

13. A method for accessing a lock associated with a resource in a computer system, the method comprising the steps of:

generating, at a particular entity, a request comprising attribute and resource information associated with the lock;

enqueuing the request on a request queue that is associated with the particular entity, the request queue associated with the particular entity being one of a plurality of request queues;

enqueuing at least one second request on a second request queue of the plurality of request queues, the second request associated with a second entity;

tracking the order in which requests reach the head of the request queue that is associated with the particular entity and the second request queue that is associated with the second entity;

applying the attribute and resource information to an outstanding lock data structure to determine if the request is allowed, wherein the outstanding lock data structure is a table comprising one or more outstanding lock data structure entries;

determining if a first entity associated with the request is the same entity as a second entity associated with an outstanding lock data structure entry;

if so, determining if a memory operation contained in the request indicates a write operation;

if so, determining if a lock type contained in the outstanding lock data structure entry indicates a shared reader lock;

if not, concluding the request is allowed; and

if the request is allowed, performing a lock operation contained in the information, and if the request is blocked, holding the request in a request queue that is associated with the particular entity at a resource controller, the request queue associated with the particular entity being one of a plurality of request queues, and subsequently, selecting the request to be executed in response to the request being the oldest request in any of the plurality of request queues that is becoming allowed.

14. A method for accessing a lock associated with a resource in a computer system, the method comprising the steps of:

generating, at a particular entity, a request comprising attribute and resource information associated with the lock;

enqueuing the request on a request queue that is associated with the particular entity, the request queue associated with the particular entity being one of a plurality of request queues;

enqueuing at least one second request on a second request queue of the plurality of request queues, the second request associated with a second entity;

tracking the order in which requests reach the head of the request queue that is associated with the particular entity and the second request queue that is associated with the second entity;

applying the attribute and resource information to an outstanding lock data structure to determine if the request is allowed, wherein the outstanding lock data structure is a table comprising one or more outstanding lock data structure entries;

determining if a first entity associated with the request is the same entity as a second entity associated with an outstanding lock data structure entry;

if not, determining if a memory operation contained in the request indicates a read operation;

if so, determining if a lock type contained in the outstanding lock data structure entry indicates an exclusive writer lock;

if so, concluding the request is allowed; and

if the request is allowed, performing a lock operation contained in the information, and if the request is blocked, holding the request in a request queue that is associated with the particular entity at a resource controller, the request queue associated with the particular entity being one of a plurality of request queues, and subsequently, selecting the request to be executed in response to the request being the oldest request in any of the plurality of request queues that is becoming allowed.

15. A method for accessing a lock associated with a resource in a computer system, the method comprising the steps of:

generating, at a particular entity, a request comprising attribute and resource information associated with the lock;

enqueuing the request on a request queue that is associated with the particular entity, the request queue associated with the particular entity being one of a plurality of request queues;

enqueuing at least one second request on a second request queue of the plurality of request queues, the second request associated with a second entity;

tracking the order in which requests reach the head of the request queue that is associated with the particular entity and the second request queue that is associated with the second entity;

applying the attribute and resource information to an outstanding lock data structure to determine if the request is allowed, wherein the outstanding lock data structure is a table comprising one or more outstanding lock data structure entries;

determining if a first entity associated with the request is the same entity as a second entity associated with an outstanding lock data structure entry;

if not, determining if a memory operation contained in the request indicates a read operation;

if so, determining if a lock type contained in the outstanding lock data structure entry indicates a shared reader lock;

if so, determining if a second request is an older pending writer;

if not, concluding the request is allowed; and

if the request is allowed, performing a lock operation contained in the information, and if the request is blocked, holding the request in a request queue that is associated with the particular entity at a resource controller, the request queue associated with the particular entity being one of a plurality of request queues, and subsequently, selecting the request to be executed in response to the request being the oldest request in any of the plurality of request queues that is becoming allowed.

16. A system adapted to access a lock associated with a resource in a computer system, the system comprising:

a processor configured to generate a request comprising attribute and lock information associated with the lock, the attribute information denoting a type of lock operation;

a resource controller coupled to the processor and configured to enqueue the request on a request queue that is associated with the processor, the request queue associated with the processor being one of a plurality of request queues, the plurality of request queues including at least one second request queue associated with a second processor;

an order bitmap configured to track the order in which requests reach the head of the request queue associated with the processor and the head of the second request queue associated with the second processor; and

the resource controller further configured to, when the request reaches the head of the request queue associated with the processor, apply the attribute and lock information to an outstanding lock data structure to determine if the request is allowed and if so, perform a lock operation contained in the information, and if the request is blocked, hold the request in the request queue associated with the processor and select the request to be executed in response to the request being the oldest request in the plurality of request queues that is becoming allowed.

17. A system as defined in claim 16 comprising:

an order bitmap configured to track the order in which the request was seen by the resource controller.

18. A system as defined in claim 16 wherein the resource controller is a memory controller.

19. A system as defined in claim 18 comprising:

a memory coupled to the memory controller.

20. A system as defined in claim 19 comprising:

an eligible bitmap configured to indicate requests that are eligible to be issued to the memory.

21. A computer readable medium containing computer executable instructions for accessing a lock associated with a resource in a computer system, the executable program instructions comprising computer executable instructions for:

generating, at a particular entity, a request comprising attribute and resource information associated with the lock, the attribute information denoting a type of lock operation;

enqueuing the request on a request queue that is associated with the particular entity;

enqueuing at least one second request on a second request queue, the second request associated with a second entity;

tracking the order in which requests reach the head of the request queue that is associated with the particular entity and the second request queue that is associated with the second entity;

applying, by a resource controller, the attribute and resource information to an outstanding lock data structure to determine if the request is allowed;

performing a lock operation contained in the information if the request is allowed; and

if the request is blocked, holding the request in the request queue that is associated with the particular entity at a resource controller and subsequently, selecting the request to be executed in response to the request being the oldest request in any request queue that is becoming allowed.

26. An apparatus comprising:

a processor configured to generate a request including a lock address, a lock operation and a lock size, the lock operation including one of a get exclusive lock operation, a get shared-reader lock operation, or a get exclusive-writer lock operation, the lock size to indicate a size of a memory segment associated with the request;

an outstanding lock data structure configured to hold entries descriptive of active locks, the entries each including a lock address of an active lock, a lock type of the active lock, and a lock segment size of the active lock, the lock type including one of an exclusive lock, a shared-reader lock, or an exclusive-writer lock;

at least one request queue associated with the processor and configured to store the request;

at least one second request queue associated with a second processor;

an order bitmap configured to track the order in which requests reach the head of the at least one request queue associated with the processor and the head of the at least one second request queue associated with the second processor;

a resource controller coupled to the processor and configured to, upon the request reaching the head of the at least one request queue associated with the processor, apply the lock address, the lock operation, and the lock size of the request to each of the entries in the outstanding lock data structure, the resource controller to determine in response thereto if the lock address and the lock operation of the request indicate a memory segment that overlaps that of one of the entries in the outstanding lock data structure, and, if there is overlap, to determine whether the lock operation of the request conflicts with the lock type of that entry in the outstanding lock data structure, and, if there is conflict, to block the request, and if there is no conflict, to allow the request.

27. The apparatus of claim 26, wherein the request further includes a memory operation to be performed at an address in the memory segment associated with the request.

28. The apparatus of claim 26, wherein the resource controller is further configured to determine if there is conflict based in part upon whether each active lock was generated by the processor, or by a different processor.

29. The apparatus of claim 26, wherein the order bitmap is further configured to track any requests that have been previously blocked and held in the request queue or in the second request queue, and wherein the resource controller is further configured give preference to any requests that have been previously blocked over requests that have not been previously blocked.

30. A method comprising:

generating a request including a lock address, a lock operation, and a lock size, the lock operation including one of a get exclusive lock operation, a get shared-reader lock operation, or a get exclusive-writer lock operation, the lock size to indicate a size of a memory segment associated with the request;

storing entries descriptive of active locks in a data structure, the entries each including a lock address of an active lock, a lock type of the active lock, and a lock segment size of the active lock, the lock type including one of an exclusive lock, a shared-reader lock, or an exclusive-writer lock;

queuing the request in at least one request queue associated with a processor;

queuing at least one second request in at least one second request queue associated with a second processor;

tracking the order in which requests reach the head of the at least one request queue associated with the processor and the head of the at least one second request queue associated with the second processor;

upon the request reaching the head of the at least one request queue associated with the processor, applying the lock address, the lock operation, and the lock size of the request to each of the entries in the outstanding lock data structure;

determining if the lock address and the lock operation of the request indicate a memory segment that overlaps that of one of the entries in the outstanding lock data structure;

if there is overlap, determining whether the lock operation of the request conflicts with the lock type of that entry in the outstanding lock data structure, by comparing the lock operation in the request with the lock type of that entry;

if there is conflict, blocking the request;

if there is no conflict, allowing the request.

31. The method of claim 30, wherein the request further includes a memory operation to be performed at an address in the memory segment associated with the request, and the step of allowing further comprises:

performing the memory operation.

32. The method of claim 30, wherein the step of generating is performed by a processor and the method further comprises:

determining if there is conflict based in part upon whether each active lock was generated by the processor or by a different processor.

33. The method of claim 30, further comprising:

tracking any requests that have been previously blocked and held in the request queue or the second request queue and giving preference to any requests that have been previously blocked over requests that have not been previously blocked.