Locking technique for control and synchronization

• US 6,973,549 B1
• Filed: 08/13/2002
• Issued: 12/06/2005
• Est. Priority Date: 12/10/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Incipient Inc.
• Inventors: Testardi, Richard
• Primary Examiner(s): Ellis, Kevin L.
• Application Number:
  US10/218,186
• Time in Patent Office: 1,211 Days
• Field of Search: 711/147, 711/148, 711/150, 711/151, 711/141
• US Class Current: 711/150
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Described are techniques used in a computer system for handling data operations to storage devices. A switching fabric includes one or more fast paths for handling lightweight, common data operations and at least one control path for handling other data operations. A control path manages one or more fast paths. The fast path and the control path are utilized in mapping virtual to physical addresses using mapping tables. The mapping tables include an extent table of one or more entries corresponding to varying address ranges. The size of an extent may be changed dynamically in accordance with a corresponding state change of physical storage. The fast path may cache only portions of the extent table as needed in accordance with a caching technique. The fast path may cache a subset of the extent table stored within the control path. A set of primitives may be used in performing data operations. A locking mechanism is described for controlling access to data shared by the control paths.

Claims

1. A method for controlling access to shared data comprising:

sending a message requesting exclusive access to said shared data from a requester to any other users of said shared data included in a list associated with said shared data indicating users currently accessing said shared data for non-exclusive read access, wherein a user is added to said list after receiving approval messages from any users included in a second list associated with said shared data, said second list indicating users interested in accesses to said shared data;

said requester receiving approval messages from the other users of said shared data included in said list;

said requester obtaining a lock on a first copy of said shared data included in a global storage location upon receiving said approval messages; and

said requester, in response to obtaining said lock, modifying said first copy of shared data, wherein said requester releases said lock when said requester has completed said modifying.

2. The method of claim 1, further comprising:

prior to each of said other users sending an approval message, each of said other users invalidating all local copies of said shared data.

5. The method of claim 2, further comprising:

a user sending a non-approval message to said requester such that said requester is not granted permission to obtain said lock.

6. The method of claim 2, wherein said requester is a first requester and the method further comprising:

a second requester sending a message for exclusive access to said shared data to at least one user requesting permission to obtain said lock after said first requester has obtained said lock; and

said first requester sending a message to said second requester granting permission to obtain said lock, said first requester being an owner of said lock until said first requester has completed said modifying.

9. The method of claim 1, further comprising performing a snapshot operation.

11. The method of claim 1, further comprising:

updating at least one of said list and said second list in accordance with a change in users associated with said shared data.

23. The method of claim 1, wherein said shared data is a first one of a plurality of resources that can be accessed by a plurality of users, each of said plurality of resources being associated with a reader list indicating which of said plurality of users are currently accessing said each resource for nonexclusive read access, said list being a reader list of said shared data.

24. The method of claim 23, wherein each of said plurality of resources is associated with an interest list indicating which of said plurality of users are currently interested in accesses to said each resource, said second list being an interest list of said shared data.

25. The method of claim 24, wherein only users included in said interest list of a first resource can be granted nonexclusive read access for said first resource.

26. The method of claim 25, wherein only users included in said reader list of said first resource can be granted exclusive access to said first resource.

27. The method of claim 26, wherein each of said plurality of users included in said interest list of said first resource has a local copy of said interest list of said first resource and said reader list of said first resource.

28. The method of claim 1, wherein, after said requester obtains said lock on said shared data, said shared data having an unrestrictive update policy, said requester notifies all users included in said list of current readers of a data modification by said requester to said shared data producing modified shared data, each of said users included in said list of current readers updating a local copy of said shared data without synchronization with I/O operations, currently outstanding I/O operations being allowed to proceed using either said shared data or said modified shared data.

29. The method of claim 28, wherein said shared data is a first one of a plurality of resources that can be accessed by a plurality of users, a second of said plurality of resources having a restrictive update policy wherein an update to said second resource requires synchronization with I/O operations, currently outstanding I/O operations completing prior to performing said update to a local copy of said second resource.

30. The method of claim 28, wherein said modified shared data indicates a superset of said shared data.

31. The method of claim 1, wherein, if said list is empty, said requester does not send any messages and said requester does not receive any approval messages.

32. The method of claim 1, wherein a plurality of users are connected to each other by a network, a first portion of said plurality of users included in said list of users accessing said shared data for nonexclusive read access and able to communicate with each other, a second portion of said plurality of users not included in said list are able to communicate with each other and not able to communicate with others in said first portion, and wherein a first of said users is evicted when a message is expected from said first user and not received, said requester expecting approval messages from users included in said first portion and not said second portion, a user in said second portion not being evicted as a result of said requester obtaining said lock.

3. A method for controlling access to shared data comprising:

sending a message from a requester to at least one other user of said shared data accessing said shared data for read access;

said requester receiving approval messages from each of said at least one other user;

said requester obtaining a lock on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another;

said requester, in response to obtaining said lock, modifying said first copy of shared data, and

wherein a local copy of said shared data is divided into varying size portions and said first copy is a global copy that is divided into corresponding fixed size portions, the method further comprising;

determining at least one lock of a fixed size portion corresponding to at least one portion of varying size; and

obtaining said at least one lock of a fixed size portion to obtain a lock on a corresponding varying size portion.

4. The method of claim 3, wherein said fixed size portions are included a mapping table used in determining a physical address location corresponding to a virtual address.

7. A method for controlling access to shared data comprising:

sending a message from a requester to at least one other user of said shared data accessing said shared data for read access;

said requester receiving approval messages from each of said at least one other user;

said requester obtaining a lock on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another;

said requester, in response to obtaining said lock, modifying said first copy of shared data;

prior to each of said other users sending an approval message, each of said other users invalidating all local copies of said shared data, and

wherein said requester is a first requester and the method further comprising;

a second requester sending a message to at least one user requesting permission to obtain said lock after said first requester has obtained said lock; and

said first requester sending a message to said second requester granting permission to obtain said lock, said first requester being an owner of said lock until said second requester obtains permission to obtain said lock, wherein said second requester is unavailable after obtaining said lock.

8. The method of claim 7, wherein said first requester performs clean-up operations of said second requester, and the method further comprising:

said first requester acquiring said lock to perform said clean-up operations.

10. A method for controlling access to shared data comprising:

sending a message from a requester to at least one other user of said shared data accessing said shared data for read access;

said requester receiving approval messages from each of said at least one other user;

said requester obtaining a lock on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another;

said requester, in response to obtaining said lock, modifying said first copy of shared

performing a snapshot operation, wherein, said snapshot operation pushes data from a first device to a second snapshot device, included in said shared data is metadata used in accessing a physical data location for a data operation, the method comprising;

acquiring at least one lock for a portion of metadata associated with said first device;

acquiring at least one lock on said second device corresponding to those of said first device;

determining if data has already been copied from said first to said second device;

if said data has not been copied, copying said data;

updating said metadata to indicate a state change in said second device that data has been copied from said first device;

waiting for read operations to said first device to complete; and

updating said metadata to indicate a state change in said first device that data has been copied from said first device.

12. A computer program product that controls access to shared data comprising:

machine executable code that sends a message requesting exclusive access to said shared data from a requester to any other users of said shared data included in a list associated with said shared data indicating users currently accessing said shared data for non-exclusive read access, wherein a user is added to said list after receiving approval messages from any users included in a second list associated with said shared data, said second list indicating users interested in accesses to said shared data;

machine executable code that receives approval messages for said requester from the other users of said shared data included in said list;

machine executable code that obtains a lock for said requester on a first copy of said shared data included in a global storage location upon receiving said approval messages; and

machine executable code that, in response to obtaining said lock, causes said requester to modify said first copy of shared data, wherein said requester releases said lock when modification by said requester is complete.

13. The computer program product of claim 12, further comprising:

machine executable code that, prior to each of said other users sending an approval message, causes each of said other users to invalidate all local copies of said shared data.

17. The computer program product of claim 13, wherein said requester is a first requester and the computer program product further comprising:

machine executable code that causes a second requester to send a message for exclusive access to said shared data to at least one user requesting permission to obtain said lock after said first requester has obtained lock; and

machine executable code that causes said first requester to send a message to said second requester granting permission to obtain said lock, said first requester being an owner of said lock until modification by said first requester has completed.

20. The computer program product of claim 12, further comprising:

machine executable code that performs a snapshot operation.

22. The computer program product of claim 12, further comprising:

machine executable code that updates at least one of said list and said second list in accordance with a change in users associated with said shared data.

37. The computer program product of claim 12, wherein said shared data is a first one of a plurality of resources that can be accessed by a plurality of users, each of said plurality of resources being associated with a reader list indicating which of said plurality of users are currently accessing said each resource for nonexclusive read access, said list being a reader list of said shared data.

38. The computer program product of claim 37, wherein each of said plurality of resources is associated with an interest list indicating which of said plurality of users are currently interested in accesses to said each resource, said second list being an interest list of said shared data.

39. The computer program product of claim 38, wherein only users included in said interest list of a first resource can be granted nonexclusive read access for said first resource.

40. The computer program product of claim 39, wherein only users included in said reader list of said first resource can be granted exclusive access to said first resource.

41. The computer program product of claim 40, wherein each of said plurality of users included in said interest list of said first resource has a local copy of said interest list of said first resource and said reader list of said first resource.

42. The computer program product of claim 12, wherein, after said requester obtains said lock on said shared data, said shared data having an unrestrictive update policy, said requester notifies all users included in said list of current readers of a data modification by said requester to said shared data producing modified shared data, each of said users included in said list of current readers updating a local copy of said shared data without synchronization with I/O operations, currently outstanding I/O operations being allowed to proceed using either said shared data or said modified shared data.

43. The computer program product of claim 42, wherein said shared data is a first one of a plurality of resources that can be accessed by a plurality of users, a second of said plurality of resources having a restrictive update policy wherein an update to said second resource requires synchronization with I/O operations, currently outstanding I/O operations completing prior to performing said update to a local copy of said second resource.

44. The computer program product of claim 42, wherein said modified shared data indicates a superset of said shared data.

45. The computer program product of claim 12, wherein, if said list is empty, said requester does not send any messages and said requester does not receive any approval messages.

46. The computer program product of claim 12, wherein a plurality of users are connected to each other by a network, a first portion of said plurality of users included in said list of users accessing said shared data for nonexclusive read access and able to communicate with each other, a second portion of said plurality of users not included in said list are able to communicate with each other and not able to communicate with others in said first portion, and wherein a first of said users is evicted when a message is expected from said first user and not received, said requester expecting approval messages from users included in said first portion and not said second portion, a user in said second portion not being evicted as a result of said requester obtaining said lock.

14. A computer program product that controls access to shared data comprising:

machine executable code that sends a message from a requester to at least one other user of said shared data accessing said shared data for read access;

machine executable code that receives approval messages for said requester from each of said at least one other user;

machine executable code that obtains a lock for said requester on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another; and

machine executable code that, in response to obtaining said lock, causes said requester to modify said first copy of shared data; and

wherein a local copy of said shared data is divided into varying size portions and said first copy is a global copy that is divided into corresponding fixed size portions, the computer program product further comprising;

machine executable code that determines at least one lock of a fixed size portion corresponding to at least one portion of varying size; and

machine executable code that obtains said at least one lock of a fixed size portion to obtain a lock on a corresponding varying size portion.

15. The computer program product of claim 14, wherein said fixed size portions are included a mapping table used in determining a physical address location corresponding to a virtual address.

16. A computer program product that controls access to shared data comprising:

machine executable code that sends a message from a requester to at least one other user of said shared data accessing said shared data for read access;

machine executable code that receives approval messages for said requester from each of said at least one other user;

machine executable code that obtains a lock for said requester on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another;

machine executable code that, in response to obtaining said lock, causes said requester to modify said first copy of shared data;

machine executable code that, prior to each of said other users sending an approval message, causes each of said other users to invalidate all local copies of said shared data; and

machine executable code that causes a user to send a non-approval message to said requester such that said requester is not granted permission to obtain said lock.

18. A computer program product that controls access to shared data comprising:

machine executable code that sends a message from a requester to at least one other user of said shared data accessing said shared data for read access;

machine executable code that receives approval messages for said requester from each of said at least one other user;

machine executable code that obtains a lock for said requester on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another;

machine executable code that, in response to obtaining said lock, causes said requester to modify said first copy of shared data;

machine executable code that, prior to each of said other users sending an approval message, causes each of said other users to invalidate all local copies of said shared data; and

wherein said requester is a first requester and the computer program product further comprising;

machine executable code that causes a second requester to send a message to at least one user requesting permission to obtain said lock after said first requester has obtained said lock; and

machine executable code that causes said first requester to send a message to said second requester granting permission to obtain said lock said first requester being an owner of said lock until said second requester obtains permission to obtain said lock, wherein said second requester is unavailable after obtaining said lock.

19. The computer program product of claim 18, wherein said first requester performs clean-up operations of said second requester, and the computer program product further comprising:

machine executable code that acquires a lock for said first requester to perform said clean-up operations.

21. A computer program product that controls access to shared data comprising:

machine executable code that sends a message from a requester to at least one other user of said shared data accessing said shared data for read access;

machine executable code that receives approval messages for said requester from each of said at least one other user;

machine executable code that obtains a lock for said requester on a first copy of said shared data included in a global storage location upon receiving said approval messages wherein said requester releases said lock when said lock is requested by another; and

machine executable code that, in response to obtaining said lock, causes said requester to modify said first copy of shared data;

machine executable code that performs a snapshot operation; and

wherein, said snapshot operation pushes data from a first device to a second snapshot device, included in said shared data is metadata used in accessing a physical data location for a data operation, the computer program product comprising;

machine executable code that acquires at least one lock for a portion of metadata associated with said first device;

machine executable code that acquires at least one lock on said second device corresponding to those of said first device;

machine executable code that determines if data has already been copied from said first to said second device;

machine executable code that, if said data has not been copied, copies said data;

machine executable code that updates said metadata to indicate a state change in said second device that data has been copied from said first device;

machine executable code that waits for read operations to said first device to complete; and

machine executable code that updates said metadata to indicate a state change in said first device that data has been copied from said first device.

33. A method for controlling access to a shared resource comprising:

sending a message from a requester to any other users included in a list for a requested access state to a shared resource, said list being determined in accordance with said requested access state included in said message;

said requester receiving approval messages from the other users; and

said requester obtaining said requested access state in response to receiving said approval messages; and

wherein said list is an interest list if said requested access state is a nonexclusive read access state indicating nonexclusive read access to said shared resource, said interest list including any users in an interested state indicating an interest in accesses to said shared resource, and wherein said list is a reader list if said requested access state is an exclusive access state for exclusive access to said shared resource, said reader list including any users currently in said nonexclusive read access state.

34. The method of claim 33, wherein a user transitions from said exclusive access state to said nonexclusive read access state after completing a modification to said shared resource.

35. The method of claim 34, wherein a user transitions from said nonexclusive read access state to said interested state after completing a read of said shared resource.

36. The method of claim 35, wherein a user transitions from said interested state to an uninterested state when said user will not be accessing said shared resource.

47. A method for controlling access to a shared resource comprising:

sending a message from a requester to any other users included in a list for a requested access state to a shared resource, said list being determined in accordance with said requested access state included in said message;

said requester receiving approval messages from the other users; and

said requester obtaining said requested access state in response to receiving said approval messages; and

wherein said list is an interest list if said requested access state is a nonexclusive read access state indicating nonexclusive read access to said shared resource, said interest list including any users in an interested state indicating an interest in accesses to said shared resource, and wherein said list is a reader list if said requested access state is an exclusive access state for exclusive access to said shared resource, said reader list including any users currently in said nonexclusive read access state.

48. The computer program product of claim 47, wherein a user transitions from said exclusive access state to said nonexclusive read access state after completing a modification to said shared resource.

49. The computer program product of claim 48, wherein a user transitions from said nonexclusive read access state to said interested state after completing a read of said shared resource.

50. The computer program product of claim 49, wherein a user transitions from said interested state to an uninterested state when said user will not be accessing said shared resource.

51. A method of updating a shared resource having an unrestrictive update policy comprising:

a requester receiving a lock on said shared resource to modify said shared resource;

modifying said shared resource producing a modified version of said shared resource;

said requester sending a message to other users included in a list of current readers associated with said shared resource; and

in resource to receiving said message, each of said other users updating a local copy of said shared resource without synchronization with I/O operations for said shared resource, currently outstanding I/O operations being allowed to proceed using either said shared resource or said modified shared resource.

52. The method of claim 51, wherein said modified shared data indicates a superset of said shared data.

53. A computer program product for updating a shared resource having an unrestrictive update policy comprising:

code that receives a lock on said shared resource to modify said shared resource by a requester of said lock;

code that modifies said shared resource producing a modified version of said shared resource;

code that sends a message from said requester to other users included in a list of current readers associated with said shared resource; and

code that, in response to receiving said message, updates a local copy of said shared resource in each of said users without synchronization with I/O operations for said shared resource, currently outstanding I/O operations being allowed to proceed using either said shared resource or said modified shared resource.

54. The computer program product of claim 53, wherein said modified shared data indicates a superset of said shared data.