Abstract:
Methods of monitoring a computer system. The methods may comprise the steps of calculating a first checksum of a data location and receiving a request from an operation running on the computer system for a lock corresponding to the data location. The methods may also comprise the steps of calculating a second checksum of the data location, and generating an indication if the first checksum and the second checksum are not equivalent. Also, methods of detecting a lock ranking violation in a computer system. The methods may comprise the steps of receiving a request from an operation for a first lock associated with a first data storage location and reviewing a list of locks issued to the operation. The methods may also comprise the step of determining whether the operation possesses a lock ranked higher than the first lock.

Description:
This application is a continuation of U.S. patent application Ser. No. 11/505,582 filed on Aug. 17, 2006 now U.S. Pat. No. 7,512,748, which is incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     For years, various software applications have included multiple discrete operations that are executed at the same time. Often these operations need to access and manipulate common data at a single memory and/or disk location. If software is not carefully designed, then multiple operations may try to write to a single data location at the same time. This may be referred to as a race condition. Race conditions often result in corrupt data and can cause software applications to generate incorrect results. 
     Mechanisms called locks have been implemented to prevent race conditions. According to common locking schemes, operations request a “lock” before accessing a data location. If the data location is available, then the lock is granted and the operation is cleared to access the data location. If another operation is accessing the data location, (e.g., another operation has the lock) then the lock request may be denied. The requesting operation may then either terminate, or wait until the lock becomes available. 
     Although properly implemented locking schemes may prevent many race conditions, they have the capability to create their own problems. For example, an operation A and an operation B may both need to perform tasks that require access to two data locations, X and Y, at the same time. If A holds the lock for X and B holds the lock for Y, then neither application may be able to perform its task. In that case, A and B may each wait indefinitely for both locks to become available, causing the software application to stop or hang-up. This problem, called deadlock, is commonly avoided by using a lock ranking or lock hierarchy. According to a lock ranking, each concurrently executed operation is required to request locks in a particular order. For example, both A and B could be required to request the lock for X before requesting the lock for Y. Accordingly, the situation where both applications hold one, but not both, of the locks can be avoided. 
     As with all programming methods, specific implementations of locks and lock ranking systems often include bugs. These bugs can be particularly difficult to debug because their symptoms, race and deadlock conditions, are not deterministic and cannot be easily reproduced. For example, a program having a race or deadlock related defect may run flawlessly four times in a row, and then crash on the fifth execution. Adding to the difficulty of finding and correcting for race and deadlock problems is the fact that they are highly dependent on execution timing. For example, latent race or deadlock related problems in an application developed and tested on a first system type may not manifest themselves until the application is run on a faster system. 
     SUMMARY 
     In one general aspect, embodiments of the invention are directed to methods of monitoring a computer system. The methods may comprise the steps of calculating a first checksum of a data location and receiving a request from an operation running on the computer system for a lock corresponding to the data location. The methods may also comprise the steps of calculating a second checksum of the data location, and generating an indication if the first checksum and the second checksum are not equivalent. 
     In another general aspect, embodiments of the invention are directed to methods of detecting a lock ranking violation in a computer system. The methods may comprise the steps of receiving a request from an operation for a first lock associated with a first data storage location and reviewing a list of locks issued to the operation. The methods may also comprise the step of determining whether the operation possesses a lock ranked higher than the first lock. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
       Embodiments of the present invention are described herein, by way of example, in conjunction with the following figures, wherein: 
         FIG. 1  shows a diagram of a system architecture according to various embodiments of the present invention; 
         FIG. 2  shows a process flow for detecting potential race conditions according to various embodiments of the present invention; 
         FIGS. 3-5  show process flows for detecting lock rank violations according to various embodiments of the present invention; and 
         FIG. 6  shows a diagram of a computer system according to various embodiments of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     As used herein, the term “operation” refers to a series of instructions that may be executed by a processor or processors to carry out a specific purpose or purposes (e.g., a thread, a process, a fiber, a task, a job, a transaction, etc.). Also, as used herein, the term “application” may refer to a piece of software that may include one or more operations. For example, an application may be a user application, an operating system component or service, etc. 
     Various embodiments of the present invention are directed to lock utility functionality that may be used to detect lock-related defects in software applications. After lock-related defects are detected, they may be documented for debug purposes. In various embodiments, detected defects may be handled at run-time. 
       FIG. 1  shows a system architecture  100 , according to various embodiments, that may be used to implement lock utility functionality. The system architecture  100  may include one or more examples of a lock utility  102 , an operation  104 , an operating system  106 , and data storage  108 . In various embodiments, some of the operations  104  may be associated with an application or applications  105 . For example, the operations  104  may be configured to perform one or more discrete tasks for the application  105 . It will be appreciated that the architecture  100  may be implemented across one or more components of a computer system, such as computer system  600  described below with reference to  FIG. 6 . 
     In various embodiments, the operations  104  may access various system resources, such as data storage locations, external hardware devices, etc., via operating system  106 . The operating system  106  may be any suitable operating system. For example, in various non-limiting embodiments, the operating system  106  may be any version of MICROSOFT WINDOWS, any UNIX operating system, any Linux operating system, OS/2, any version of Mac OS, etc. For example, the operating system  106  may allow the operations  104  to access and manipulate data stored at data storage  108 . 
     Data storage  108  may include any kind of storage drive or memory capable of storing data in an electronic or other suitable computer-readable format. In certain non-limiting embodiments, data storage  108  may include a single fixed disk drive, an array of disk drives, an array of disk drives combined to provide the appearance of a larger, single disk drive, a solid state drive, etc. The physical components making up data storage  108  may be located at a single location, or multiple locations. Data storage  108  may include one or more discrete data locations  109  where data may be stored. In various embodiments, data locations  109  may include a single addressable location, or a range of addressable locations.  FIG. 1  shows a lock  111  associated with each of the data storage locations  109 . As described in more detail below, an operation  104  wishing to access a data location  109  should first hold the lock  111  associated with that data location. It will be appreciated that the locks  111  may be implemented in any suitable way. For example, in various embodiments, the locks  111  may be implemented as software abstractions handled by the operating system  106  and/or the lock utility  102 . Also, in various embodiment, the locks  111  may be hardware-implemented. 
     It will be appreciated that the lock utility functionality described herein may be implemented by various pieces of the system architecture  100 . For example, in various embodiments, all of the functionality may be implemented by the lock utility  102 . In that case, the lock utility may receive requests to access data locations  109 , determine whether locks should be issued, issue locks, etc., for example, as described below. In various embodiments, the lock utility  102  may implement its functionality in conjunction with the operating system  106  and/or a component thereof. For example, in various embodiments, the lock utility may receive requests to access data locations  109 , and may determine whether a lock should issue, etc., but the actual issuance of locks and access to data locations  109  may be handled by the operating system  106 . It will be appreciated that in other various embodiments, all lock functionality may be implemented by the operating system  106  or a component thereof. 
       FIG. 2  shows a process flow  200  for detecting a race condition according to various embodiments. At step  202 , a lock may be associated with a particular location  109  at data storage  108 . A checksum for the data value at data location  109  may be found at step  204  (e.g., by the lock utility  102 , the operating system  106 , etc.). In various embodiments, the checksum at step  204  may be taken immediately after the lock  111  associated with the data location  109  has been released by an operation  104 . In this way, the checksum may take into account all authorized modifications to the data at location  109 . At step  206 , a request for the lock  111  may be received. The request may originate from an operation  104 . The checksum may be verified at step  208 . A valid checksum may indicate that it is unlikely that the data at location  109  has been modified since the lock  111  was most recently released. Accordingly, the lock  111  may be issued to the requesting operation at step  210 . When the operation  210  has completed its use of the data, it may release the lock  111  at step  211 . At that point, an additional checksum may be calculated at step  204  and the process may continue. 
     Referring back to decision step  208 , if the checksum is not valid, it may indicate that the data at location  109  has been modified by a system entity that did not follow the proper locking procedure (e.g., a locking violation may have occurred). As a result, the data at location  109  may be corrupted and may cause an error if the operation  104 , or even the application  105  associated with the operation  104 , is allowed to continue. Accordingly, the operation  104  or application  105  may be aborted at step  212  to avoid or minimize errors due to potentially corrupted data. A report describing the circumstances of the abort may be generated at step  214 . The report may identify the data location  109  at issue, operations  104  that have recently held the lock  111 , the operation  104  that made the request, the various checksums, etc. The report may be used by quality assurance personnel or other debuggers to identify and/or isolate underlying problems in the application  105  or operating system  106  that caused the unauthorized access. 
       FIG. 3  shows a process flow  300  for detecting potential deadlock situations. In various embodiments, the process flow  300  may be implemented with a predetermined lock ranking. The predetermined lock ranking may be a relative ranking of locks that define a common sequence in which all operations  104  should request and acquire locks. The lock ranking may be developed according to any suitable method. For example, in various embodiments, the lock ranking may be determined by a developer at the time that an application  105  or operation  104  is developed. 
     Referring back to  FIG. 3 , at step  302 , a lock request may be received from one of the operations  104 . At step  304 , the rank of the requested lock  111  may be compared to the ranks of other locks currently held by the requesting operation  104 . The lock utility  102  and/or the operating system  106  may facilitate this comparison by keeping a lock list for each of the operations  104 , or at least for each of the operations  104  that possess a lock at any given time. The lock list for an operation  104  may include various information about the specific nature of the locks  111  issued to the operation  104 . For example, for each lock  111 , the lock list may indicate the rank of the lock  111 , the type of the lock  111 , whether the operation  104  has shared or exclusive ownership of the lock  111 , whether there are any OS-enforced locking rules relating to the lock  111 , whether the lock  111  may be reacquired by the operation  104 , etc. 
     After comparing the rank of the requested lock  111  to those locks already held&#39; by the operation  104 , it may be determined, at step  304 , whether a lock rank violation will occur if the requested lock  111  is issued to the operation  104 . For example, a lock rank violation may occur if the operation  104  already possesses one or more locks that are ranked higher than the requested lock  111  in the predetermined lock ranking (e.g. if the operation  104  already possesses a lock that should be obtained after the requested lock). If this is the case, then issuing the lock  111  to the operation  104  may cause a lock rank violation. If no potential lock rank violation is found, then the lock  111  may be issued to the operation at step  310 . 
     If issuing the requested lock  111  to the operation  104  will cause a rank violation, then various steps may be taken. For example, as shown in  FIG. 3 , the offending operation  104  and/or the application  105  corresponding to the offending operation  104  may be aborted at step  312  to prevent a potential deadlock condition. A report detailing the potential lock ranking violation may then be generated at step  314 . The report may include various information including, for example: the lock lists of some or all of the operations  104  that were active at the time of the abort, including the operation  104  that made the offending lock request. It will be appreciated that this report may be used by software debuggers to locate and pinpoint a defect or defects in the operation  104  or application  105  that caused the attempted lock rank violation. For example, the operation  104  that made the offending lock request may be modified to request locks  111  in the correct rank order. 
     In various embodiments, as shown by process flow  400  in  FIG. 4 , if a potential lock rank violation is found at step  308 , the report may be generated at step  316 . The report may be used as described above. The process  400  may proceed to step  310 , where the requested lock may be issued to the operation  104 , even though doing so is a violation of the lock ranking. It will be appreciated that not all lock ranking violations will result in a deadlock condition. Accordingly, it may be desirable to allow the operations  104  to continue executing, even after a lock ranking violation is detected. In this way, if no deadlock condition does occur, the system will continue to run. In a debug environment, this may allow additional observations of the system to be made and additional bugs or defects may to be isolated. Also, in various embodiments, methods according to the process flow  400  could be implemented in production software. In this way, software in the field could be reviewed or monitored without inconveniencing software users with potentially unnecessary aborts. 
     In other various embodiments, potential lock ranking violations may be corrected, for example, as shown by process flow  500  of  FIG. 5 . According to the process flow  500 , if a potential lock ranking violation is detected at step  308 , then the requesting operation  104  may be directed to release all of its locks at step  318 . The operation  104  may be further instructed to restart, or to otherwise reacquire its locks at step  320 . It will be appreciated that when the operation  104  releases and then reacquires all of its locks, its timing relative to other active operations  104  may be altered. In many cases, this alteration may be enough to prevent the potential lock rank violation from occurring again. In various embodiments, a report may also be generated, for example, as described above. Accordingly the process flow  500  may be used as a debugging tool, as described above, or may be used in production software to remedy potential lock ranking violations and prevent deadlock conditions. 
       FIG. 6  shows a computer system  600  that may be used in the implementation of various embodiments. The computer system  600  may include various computing devices and/or constructs. For example, the computer system  600  may include one or more user devices  602 , one or more servers  604 , one or more databases  606 , etc. A network  610  may provide connectivity between the devices  602 ,  604 ,  606  according to any suitable wired or wireless method. 
     The various devices  602 ,  604 ,  606  of the computer system  600  may generally store resources and/or execute software that may allow users (not shown) of the system  600  to perform various tasks, (e.g., use and/or manipulate the resources). User devices  602  may include any kind of device that allows a user to execute software, or access another device that may execute software (e.g., server  604 ). Example user devices  602  include a desktop computer, a laptop computer, a handheld computer, a personal digital assistant (PDA), etc. The user devices  602  may be used to monitor and/or manipulate software running on other components of the system  600  (e.g., the server  604 ), or access resources stored on other components of the system  600  (e.g., database  606 ). In various embodiments, however, user devices  602  may also store resources and/or execute software. 
     It is to be understood that the figures and descriptions of the present invention have been simplified to illustrate elements that are relevant for a clear understanding of the present invention, while eliminating other elements, for purposes of clarity. Those of ordinary skill in the art will recognize that these and other elements may be desirable. However, because such elements are well known in the art and because they do not facilitate a better understanding of the present invention, a discussion of such elements is not provided herein. 
     As used herein, a “computer,” “computer system,” and the like, may be, for example and without limitation, either alone or in combination, a personal computer (PC), server-based computer, main frame, server, microcomputer, minicomputer, laptop, personal data assistant (PDA), cellular phone, pager, processor, including wireless and/or wireline varieties thereof, a virtual computer system and/or any other computerized device or construct capable of configuration for processing data for standalone application and/or over a networked medium or media. Computers and computer systems disclosed herein may include operatively associated memory for storing certain software applications used in obtaining, processing, storing and/or communicating data. It can be appreciated that such memory can be internal, external, remote or local with respect to its operatively associated computer or computer system. Memory may also include any means for storing software or other instructions including, for example and without limitation, a hard disk, an optical disk, floppy disk, ROM (read only memory), RAM (random access memory), PROM (programmable ROM), EEPROM (extended erasable PROM), and/or other like computer-readable media. 
     The described systems may include various modules and/or components implemented as software code to be executed by a processor(s) of the systems or any other computer system using any type of suitable computer instruction type. The software code may be stored as a series of instructions or commands on a computer readable medium. The term “computer-readable medium” as used herein may include, for example, magnetic and optical memory devices such as diskettes, compact discs of both read-only and writeable varieties, optical disk drives, and hard disk drives. A computer-readable medium may also include memory storage that can be physical, virtual, permanent, temporary, semi-permanent and/or semi-temporary. A computer-readable medium may further include one or more data signals transmitted on one or more carrier waves. 
     While several embodiments of the invention have been described, it should be apparent that various modifications, alterations and adaptations to those embodiments may occur to persons skilled in the art with the attainment of some or all of the advantages of the present invention. It is therefore intended to cover all such modifications, alterations and adaptations without departing from the scope and spirit of the present invention.