Abstract:
An embodiment relates generally to a method of preventing resource access conflicts in a software component. The method includes intercepting a lock operation in the software component and testing an associated lock type of the lock operation against a set of rules. The method also includes determining an action based on the associated lock type conflicting one of the rules of the set of rules.

Description:
FIELD 
     This invention relates generally to locks, more particularly to methods and systems for a kernel lock validator to manage locks. 
     DESCRIPTION OF THE RELATED ART 
     Locks are a primitive utilized by the kernel to manage the resources of a computing system. Without locks, different parts of a computer system can collide when trying to access the same resources, leading to data corruption and general chaos. However, managing locks is a challenging programming task because the number of instances of locks, the type of locks and the cost of not resolving deadlocks. 
     The fundamental issue surrounding locking is the need to provide synchronization in certain code paths in the kernel. These code paths, called critical sections, require some combination of concurrency or re-entrancy protection and proper ordering with respect to other events. The typical result without proper locking is called a race condition. As a simple example, consider two locks L 1  and L 2 . Any code which requires both locks must tale care to acquire the locks in the right order. If one function acquires L 1  before L 2 , but another function acquires them in the opposite order, eventually the system will find itself in a situation where each function has acquired one lock and is blocked waiting for the other—a deadlock. 
     This is not to say that the only locking issues arise from SMP (symmetric multiprocessing). Interrupt handlers create locking issues and any code can block (go to sleep). Of these, only SMP is considered true concurrency, i.e., only with SMP can two things actually occur at the exact same time. The other situations—interrupt handlers, preempt-kernel and blocking methods—provide pseudo concurrency as code is not actually executed concurrently, but separate code can mangle one another&#39;s data. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various features of the embodiments can be more fully appreciated, as the same become better understood with reference to the following detailed description of the embodiments when considered in connection with the accompanying figures, in which: 
         FIG. 1  depicts a software environment in accordance with an embodiment; 
         FIG. 2  illustrates a block diagram of the kernel lock validator in accordance with another embodiment; 
         FIG. 3  depicts data structure in accordance with yet another embodiment; 
         FIG. 4  depicts a flow diagram in accordance with yet another embodiment; and 
         FIG. 5  illustrates a computing platform the software environment depicted in  FIG. 1 . 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     For simplicity and illustrative purposes, the principles of the present invention are described by referring mainly to exemplary embodiments thereof. However, one of ordinary skill in the art would readily recognize that the same principles are equally applicable to, and can be implemented in, all types of operating systems, and that any such variations do not depart from the true spirit and scope of the present invention. Moreover, in the following detailed description, references are made to the accompanying figures, which illustrate specific embodiments. Electrical, mechanical, logical and structural changes may be made to the embodiments without departing from the spirit and scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense and the scope of the present invention is defined by the appended claims and their equivalents. 
     Embodiments relate generally to systems, methods and apparatus for a lock validator to prevent resource access conflicts in a software component such as users-pace or a kernel. More particularly, the lock validator can be configured to track the state of locks-types and it maintains dependencies between the different lock-types. The lock validator can also be configured to maintain a rolling proof that the state of the lock-types and the dependencies are correct. 
     Embodiments of the lock validator can be configured to track lock-types as opposed to tracking each individual instance of the lock-type. Unlike a lock instantiation, the lock-type is registered when it used for the first time after bootup and all subsequent uses of the registered lock-type will be attached to this lock-type. Accordingly, each lock type is assigned a specific key based on the registration of the lock-type. The lock validator can be configured to create a static variable (e.g., (_key)) for statically declared locks and uses the address of the statically declared lock as the key. 
     The lock validator can also be configured to track lock-type usage by using five separate state bits: (1) ever held in hard interrupt context (hardirq-safe); (2) ever held in soft interrupt context (softirg-safe); (3) ever held in hard interrupt with interrupts enabled (hardirq-unsafe); (4) ever held with soft interrupts and hard interrupts enabled (softirq-unsafe); and (5) ever used (!unused). With these state bits, the lock validator can be configured to test each locking operation. More particularly, the lock validator tests each locking operation against a number of rules. A softirq-unsafe is automatically a hardirq-unsafe is an example of one rule. Another rule is that following states are exclusive, i.e., can only be set for any lock type: (1) hardirq-safe and hardirq-unsafe; and (2) softirq-safe and softirq-unsafe. Yet another rule is that the same lock-type cannot be acquired twice as well as two locks cannot be acquired in different order. Yet another rule is that the following lock dependencies are not permitted: (1) hardirq-safe to hardirq-unsafe; and (2) softirq-safe to softirq-unsafe. Accordingly, the above rules are enforced for any locking sequence that occurs in the kernel: when acquiring a new lock, the lock validator checks whether there is any rule violation between the new lock and any of the held locks. 
     When a lock-type changes state, the following additional rules are tested: (1) if a new hardirq-safe lock is discovered, the lock validator determines whether it took any hardirq-unsafe lock in the past; (2) if a new softirq-safe lock is discovered, the lock validator determines whether it took any softirq-unsafe lock in the past; (3) if a new hardirq-unsafe lock is discovered, the lock validator determines whether any hardirq-safe lock took it in the past; and (4) if a new softirq-unsafe lock is discovered, the lock validator determines whether any softirq-safe lock took it in the past. Accordingly, the lock validator can be configured to report the rule violation where it can be used to modify the behavior of the software component (e.g., kernel or application) to mitigate the effect of the lock violation. 
     The above rules require massive amounts of runtime checking. If this checking were done for every lock taken and for every interrupt (“irqs”)-enabled event, it would render the system practically unusably slow. The complexity of checking is O(N 2 ). Accordingly, tens of thousand of check would be performed for every event even with just a few hundred lock-types. Embodiments of the present invention resolve this issue by checking any given ‘locking scenario’ (unique sequence of locks taken after each other) only once. A simple stack of held locks is maintained, and a lightweight 64-bit hash value is calculated when the sequence (or chain) is validated for the first time. This hash value, which is unique for every lock chain. The hash value is then put into a hash table, which can be checked in a lock-free manner. If the locking chain occurs again later on, the hash table can notify the lock validator not to validate the chain again. 
       FIG. 1  illustrates an exemplary environment  100  configured to implement a kernel lock validator. It should be readily obvious to one of skilled in that art that the environment  100  depicted in  FIG. 1  is a schematic illustration and additional components can be added and existing components can be modified or removed. 
     As shown in  FIG. 1 , the environment  100  can include an operating system  105 . The operating system  105  may be a version of a Linux™, UNIX™, Windows™, or similar multi-tasking operating system. The operating system  105  can also comprise a kernel  120 . The kernel  120  can be configured to mange the resources of the environment  100  and the communication between hardware and software components. The kernel  120  can also provide the lowest level abstraction layer for the resources (especially memory, processors, and input/output devices) that applications must control to perform their function. 
     A run-time environment  110  can be configured to execute on the operating system  105 . The run-time environment  110  can provide a set of software tools that supports the execution of applications/programs. The run-time environment  110  can include an application program interface (“API”, not shown) and a complementary API (not shown) within an application  115 . The API can be configured to provide a set of routines that the application  115  uses to request lower level services performed by the kernel  120 . 
     The run-time environment  110  can also be configured to provide for userspace  125  for a user. In some multi-user operating systems, such as Linux, can support multiple users. The userspace  125  can be configured to provide space for a user to execute applications through appropriate software tools known to those skilled in the art. As part of the software tools, the user space  125  can be provided with locks. A lock is a synchronization mechanism for enforcing limits on access to a resource managed by the operating system  105 . 
     The kernel  120  can also be configured to implement a kernel lock validator  130  to manage the locks being used by the applications, processes, tasks executing in the userspace  125 . The kernel lock validator  130  can be configured to track the state of locks-types and maintain dependencies between the different lock-types. The kernel lock validator  130  can also be configured to maintain a rolling proof that the state of the lock-types and the dependencies are correct. 
     The kernel lock validator  130  can further be track lock-types. Unlike a lock instantiation, the lock-type is registered when it used for the first time after bootup and all subsequent uses of the registered lock-type will be attached to this lock-type, Accordingly, each lock type is assigned a specific key based on the registration of the lock-type. The kernel lock validator  130  can be configured to create a static variable (e.g., (_key)) for statically declared locks and uses the address of the statically declared lock as the key. 
       FIG. 2  illustrates a more detailed diagram of the kernel lock validator  130  in accordance with another embodiment. It should be readily obvious to one of skilled in that art that the kernel lock validator  130  depicted in  FIG. 2  is a schematic illustration and additional components can be added and existing components can be modified or removed. 
     As shown in  FIG. 2 , the kernel lock validator  130  can comprise a control module  205 , a lock status module  210 , a rules module  215  and a hash table  220 . The control module  205  can be configured to manage and provide the functionality of the kernel lock validator  130 . The control module  205 , as with the other noted modules, can be implemented as a software routine (applet, program, etc.), a hardware component (ASIC, FPGA, etc.) or a combinations thereof. 
     The control module  205  can also be configured to track lock-types as opposed to tracking each individual instance of the lock-type. The lock-type is registered when it used for the first time after bootup and all subsequent uses of the registered lock-type will be attached to this lock-type. Accordingly, each lock type is assigned a specific key based on the registration of the lock-type. The control module  205  can be configured to create a static variable (e.g., (_key)) for statically declared locks and uses the address of the statically declared lock as the key. The control module  205  can maintain the information regarding the lock types and associated keys in the lock status module  210 . 
     The control module  205  can be further configured to track lock-type usage by using a series of state bits: (1) ever held in hard interrupt context (hardirq-safe); (2) ever held in soft interrupt context (softirg-safe); (3) ever held in hard interrupt with interrupts enabled (hardirq-unsafe); (4) ever held with soft interrupts and hard interrupts enabled (softirq-unsafe); and (5) ever used (!unused). With these state bits, the control module  205  can be configured to test each locking operation with the predetermined rules stored in the rules module  215 . 
     The rules module  215  can be configured to store the rules that the control module  205  uses to check each lock operation. The rules module  215  can be configured to stores rules such as a softirq-unsafe is automatically a hardirq-unsafe. Another rule is that following states are exclusive, i.e., can only be set for any lock type: (1) hardirq-safe and hardirq-unsafe; and (2) softirq-safe and softirq-unsafe. Yet another rule is that the same lock-type cannot be acquired twice as well as two locks cannot be acquired in different order. Yet another rule is that the following lock dependencies are not permitted: (1) hardirq-safe to hardirq-unsafe; and (2) softirq-safe to softirq-unsafe. Accordingly, the above rules are enforced for any locking sequence that occurs in the kernel  120 : when acquiring a new lock, the control module  205  checks whether there is any rule violation between the new lock and any of the held locks. 
     There are additional rules for when a lock type changes state. One rule is if a new hardirq-safe lock is discovered, the lock validator determines whether it took any hardirq-unsafe lock in the past. A second change of state rule is if a new softirq-safe lock is discovered, the control module  205  determines whether it took any softirq-unsafe lock in the past. A third change of state rule is if a new hardirq-unsafe lock is discovered, the lock validator determines whether any hardirq-safe lock took it in the past. A fourth change of state rule is if a new softirq-unsafe lock is discovered, the lock validator determines whether any softirq-safe lock took it in the past. It should be readily that the list of rules for exemplary and new rules or existing rules modified without departing from the scope of the claimed invention. 
     As there are multiple rules, the ordering of the rules as they are tested is an additional requirement. Accordingly, the control module  205  can be configured to maintain two lists. A first list, a “before” list contains all locks which have ever been held when the lock of interest (referred to a L) is acquired. As a result, the before list contains the keys of all locks acquired before the L, the lock of interest. The second list, an “after” list, holds all locks acquired while the lock of interest is held. The before and after lists can be implemented using data structures such as a buffer, linked lists, and other similar referencing structures. 
       FIG. 3  depicts a block diagram of a first and second data structure  305 ,  310 , respectively for implementing storing the before list and the after list. As shown in  FIG. 3 , first data structure  305  and second data structure  310  can be implemented as a series of memory spaces  315 . The size of the memory space  315  can be dependent on the type of processor. More particularly, a 32-bit processor may indicate that the size of the memory space  315  is a 32-bit word as an example. In other embodiments, a user can alter the size of the memory space  315 . 
     Returning to  FIG. 2 , the control module  205  can be configured to check whether any locks on the “after” list associated with the lock of interest, L, is already held. The control module  205  should not find any lock being held. However, if a lock is found, the control module  205  can signal an error. 
     The control module  205  can also be configured to link the after list of L with the before lists of the other currently held locks to determine any ordering or interrupt violations anywhere within that chain. If the control module  205  determines that the tests are passed, the control module  205  updates the various “before” and “after” lists. 
     Since all this checking can impose a large amount of processor time, the control module  205  can be configured to maintain a third data structure, a list of currently held locks. The third data structure can be implemented as a simple buffer, a linked list or other similar searchable reference structure. From the sequence of the list of currently held locks, the control module  205  can be configured to generate a 64-bit hash value when the sequence of locks has been validated, i.e., cleared of any conflicts. The control module  205  then stores this 64-bit hash value into the hash table  220 . Subsequently, when the control module  205  encounters the same sequence, of locks, the control module  205  can generate a second 64-bit hash value to compare against the values stored in the hash table  220 . If the control module  205  determines there is match, the control module  205  knows the second sequence has been checked against the rules stored in the rules module  215 . 
       FIG. 4  illustrates a flow diagram  400  executed by the control module  205  of the kernel lock validator  135  in accordance with another embodiment. It should be readily obvious to one of skilled in that art that the flow diagram  400  depicted in  FIG. 4  is a schematic illustration and additional steps can be added and existing steps can be modified or removed. 
     As shown in  FIG. 4 , the control module  205  can receive notification of an acquisition of a lock, L, by a process, thread, etc., in step  405 . Alternatively, the control module  205  can also receive notification that a lock is changing state, e.g., being released. 
     In step  410 , the control module  205  can be configured to generate a 64-bit hash value of the sequence with the lock, L, as a temporary last entry into the data structure that holds the list of currently held locks. The hash value can be regarded as a ‘frontside cache’ so as to avoid testing of all held locks against the set of rules. The control module  205  can be configured to keep a ‘rolling’ 64-bit hash of the current ‘stack of locks’, which is updated when a lock in the stack is released or when a new lock is acquired. The update of the update 64-bit hash does not need to be recalculate the full has of all held locks because the hash generation step is reversible. 
     In step  415 , the control module  205  can be configured to search the hash table  220  with the generated 64-bit hash value. If there is match, in step  420 , the control module  205  knows that this sequence had previously been validated and the lock, L, is entered into the data structure that holds the list of currently held locks, in step  425 . The control module  205  also updates the after-lists of each currently held lock with the acquisition of lock, L, in step  430 . 
     Otherwise, if there is not a match, in step  420 , the control module  205  can be configured to test the lock, Lt, against the rules stored in the rules module  220 , in step  435 . More particularly, the control module  205  can be configured to validate a new dependency against all existing dependencies. For example, if L 2  has been taken after L 1  in the past, and a L 2 =&gt;L 1  dependency is added, this condition is determined to be a violation. In essence, new dependencies are only added when they do not conflict with existing rules (or dependencies). Accordingly, the control module  205  can set the state of the lock, L, being acquired. Subsequently, the control module  205  can apply the rules stored in the rules module  215 . 
     Alternatively, if the lock, L, is changing state, the control module  205  can test the lock, L, against the rules for lock changing state. 
     If the lock, L, did not pass the rules, in step  440 , the acquiring entity is informed of the error and is disallowed from acquiring the lock, in step  445 . Otherwise, in step  450 , the control module  205  can be configured to create data structures for the before list  305  and after list  310 . The control module  205  can also store the lock, L, in the data structure for storing currently held locks. 
     In step  450 , the control module  205  can generate a 64-bit hash value on the current sequence of the list of currently held locks and subsequently stored in the hash table  220 . 
       FIG. 5  depicts an exemplary computing platform  500  configured to execute the kernel lock validator  130  in accordance with yet another embodiment. The functions of the kernel lock validator  130  may be implemented in program code and executed by the computing platform  500 . The kernel lock validator  130  can be implemented in computer languages such as PASCAL, C, C++, JAVA, etc. 
     As shown in  FIG. 5 , the computer system  500  includes one or more processors, such as processor  502  that provide an execution platform for embodiments of the kernel lock validator  130 . Commands and data from the processor  502  are communicated over a communication bus  504 . The computer system  500  also includes a main memory  506 , such as a Random Access Memory (RAM), where the kernel lock validator  130  can be executed during runtime, and a secondary memory  508 . The secondary memory  508  includes, for example, a hard disk drive  510  and/or a removable storage drive  512 , representing a floppy diskette drive, a magnetic tape drive, a compact disk drive, etc., where a copy of a computer program embodiment for the kernel lock validator  130  can be stored. The removable storage drive  512  reads from and/or writes to a removable storage unit  514  in a well-known manner. A user interfaces with the kernel lock validator  130  with a keyboard  516 , a mouse  518 , and a display  520 . A display adapter  522  interfaces with the communication bus  504  and the display  520 . The display adapter  522  also receives display data from the processor  502  and converts the display data into display commands for the display  520 . 
     Certain embodiments may be performed as a computer program. The computer program may exist in a variety of forms both active and inactive. For example, the computer program can exist as software program(s) comprised of program instructions in source code, object code, executable code or other formats; firmware program(s); or hardware description language (HDL) files. Any of the above can be embodied on a computer readable medium, which include storage devices and signals, in compressed or uncompressed form. Exemplary computer readable storage devices include conventional computer system RAM (random access memory), ROM (read-only memory), EPROM (erasable, programmable ROM), EEPROM (electrically erasable, programmable ROM), and magnetic or optical disks or tapes. Exemplary computer readable signals, whether modulated using a carrier or not, are signals that a computer system hosting or running the present invention can be configured to access, including signals downloaded through the Internet or other networks. Concrete examples of the foregoing include distribution of executable software program(s) of the computer program on a CD-ROM or via Internet download. In a sense, the Internet itself, as an abstract entity, is a computer readable medium. The same is true of computer networks in general. 
     While the invention has been described with reference to the exemplary embodiments thereof, those skilled in the art will be able to make various modifications to the described embodiments without departing from the true spirit and scope. The terms and descriptions used herein are set forth by way of illustration only and are not meant as limitations. In particular, although the method has been described by examples, the steps of the method may be performed in a different order than illustrated or simultaneously. Those skilled in the art will recognize that these and other variations are possible within the spirit and scope as defined in the following claims and their equivalents.