Subversion Repositories Kolibri OS

Rev

Rev 1408 | Rev 2967 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Runtime locking correctness validator
  3.  *
  4.  *  Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  5.  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
  6.  *
  7.  * see Documentation/lockdep-design.txt for more details.
  8.  */
  9. #ifndef __LINUX_LOCKDEP_H
  10. #define __LINUX_LOCKDEP_H
  11.  
  12. struct task_struct;
  13. struct lockdep_map;
  14.  
  15. #ifdef CONFIG_LOCKDEP
  16.  
  17. #include <linux/linkage.h>
  18. #include <linux/list.h>
  19. #include <linux/debug_locks.h>
  20. #include <linux/stacktrace.h>
  21.  
  22. /*
  23.  * We'd rather not expose kernel/lockdep_states.h this wide, but we do need
  24.  * the total number of states... :-(
  25.  */
  26. #define XXX_LOCK_USAGE_STATES           (1+3*4)
  27.  
  28. #define MAX_LOCKDEP_SUBCLASSES          8UL
  29.  
  30. /*
  31.  * NR_LOCKDEP_CACHING_CLASSES ... Number of classes
  32.  * cached in the instance of lockdep_map
  33.  *
  34.  * Currently main class (subclass == 0) and signle depth subclass
  35.  * are cached in lockdep_map. This optimization is mainly targeting
  36.  * on rq->lock. double_rq_lock() acquires this highly competitive with
  37.  * single depth.
  38.  */
  39. #define NR_LOCKDEP_CACHING_CLASSES      2
  40.  
  41. /*
  42.  * Lock-classes are keyed via unique addresses, by embedding the
  43.  * lockclass-key into the kernel (or module) .data section. (For
  44.  * static locks we use the lock address itself as the key.)
  45.  */
  46. struct lockdep_subclass_key {
  47.         char __one_byte;
  48. } __attribute__ ((__packed__));
  49.  
  50. struct lock_class_key {
  51.         struct lockdep_subclass_key     subkeys[MAX_LOCKDEP_SUBCLASSES];
  52. };
  53.  
  54. #define LOCKSTAT_POINTS         4
  55.  
  56. /*
  57.  * The lock-class itself:
  58.  */
  59. struct lock_class {
  60.         /*
  61.          * class-hash:
  62.          */
  63.         struct list_head                hash_entry;
  64.  
  65.         /*
  66.          * global list of all lock-classes:
  67.          */
  68.         struct list_head                lock_entry;
  69.  
  70.         struct lockdep_subclass_key     *key;
  71.         unsigned int                    subclass;
  72.         unsigned int                    dep_gen_id;
  73.  
  74.         /*
  75.          * IRQ/softirq usage tracking bits:
  76.          */
  77.         unsigned long                   usage_mask;
  78.         struct stack_trace              usage_traces[XXX_LOCK_USAGE_STATES];
  79.  
  80.         /*
  81.          * These fields represent a directed graph of lock dependencies,
  82.          * to every node we attach a list of "forward" and a list of
  83.          * "backward" graph nodes.
  84.          */
  85.         struct list_head                locks_after, locks_before;
  86.  
  87.         /*
  88.          * Generation counter, when doing certain classes of graph walking,
  89.          * to ensure that we check one node only once:
  90.          */
  91.         unsigned int                    version;
  92.  
  93.         /*
  94.          * Statistics counter:
  95.          */
  96.         unsigned long                   ops;
  97.  
  98.         const char                      *name;
  99.         int                             name_version;
  100.  
  101. #ifdef CONFIG_LOCK_STAT
  102.         unsigned long                   contention_point[LOCKSTAT_POINTS];
  103.         unsigned long                   contending_point[LOCKSTAT_POINTS];
  104. #endif
  105. };
  106.  
  107. #ifdef CONFIG_LOCK_STAT
  108. struct lock_time {
  109.         s64                             min;
  110.         s64                             max;
  111.         s64                             total;
  112.         unsigned long                   nr;
  113. };
  114.  
  115. enum bounce_type {
  116.         bounce_acquired_write,
  117.         bounce_acquired_read,
  118.         bounce_contended_write,
  119.         bounce_contended_read,
  120.         nr_bounce_types,
  121.  
  122.         bounce_acquired = bounce_acquired_write,
  123.         bounce_contended = bounce_contended_write,
  124. };
  125.  
  126. struct lock_class_stats {
  127.         unsigned long                   contention_point[4];
  128.         unsigned long                   contending_point[4];
  129.         struct lock_time                read_waittime;
  130.         struct lock_time                write_waittime;
  131.         struct lock_time                read_holdtime;
  132.         struct lock_time                write_holdtime;
  133.         unsigned long                   bounces[nr_bounce_types];
  134. };
  135.  
  136. struct lock_class_stats lock_stats(struct lock_class *class);
  137. void clear_lock_stats(struct lock_class *class);
  138. #endif
  139.  
  140. /*
  141.  * Map the lock object (the lock instance) to the lock-class object.
  142.  * This is embedded into specific lock instances:
  143.  */
  144. struct lockdep_map {
  145.         struct lock_class_key           *key;
  146.         struct lock_class               *class_cache[NR_LOCKDEP_CACHING_CLASSES];
  147.         const char                      *name;
  148. #ifdef CONFIG_LOCK_STAT
  149.         int                             cpu;
  150.         unsigned long                   ip;
  151. #endif
  152. };
  153.  
  154. /*
  155.  * Every lock has a list of other locks that were taken after it.
  156.  * We only grow the list, never remove from it:
  157.  */
  158. struct lock_list {
  159.         struct list_head                entry;
  160.         struct lock_class               *class;
  161.         struct stack_trace              trace;
  162.         int                             distance;
  163.  
  164.         /*
  165.          * The parent field is used to implement breadth-first search, and the
  166.          * bit 0 is reused to indicate if the lock has been accessed in BFS.
  167.          */
  168.         struct lock_list                *parent;
  169. };
  170.  
  171. /*
  172.  * We record lock dependency chains, so that we can cache them:
  173.  */
  174. struct lock_chain {
  175.         u8                              irq_context;
  176.         u8                              depth;
  177.         u16                             base;
  178.         struct list_head                entry;
  179.         u64                             chain_key;
  180. };
  181.  
  182. #define MAX_LOCKDEP_KEYS_BITS           13
  183. /*
  184.  * Subtract one because we offset hlock->class_idx by 1 in order
  185.  * to make 0 mean no class. This avoids overflowing the class_idx
  186.  * bitfield and hitting the BUG in hlock_class().
  187.  */
  188. #define MAX_LOCKDEP_KEYS                ((1UL << MAX_LOCKDEP_KEYS_BITS) - 1)
  189.  
  190. struct held_lock {
  191.         /*
  192.          * One-way hash of the dependency chain up to this point. We
  193.          * hash the hashes step by step as the dependency chain grows.
  194.          *
  195.          * We use it for dependency-caching and we skip detection
  196.          * passes and dependency-updates if there is a cache-hit, so
  197.          * it is absolutely critical for 100% coverage of the validator
  198.          * to have a unique key value for every unique dependency path
  199.          * that can occur in the system, to make a unique hash value
  200.          * as likely as possible - hence the 64-bit width.
  201.          *
  202.          * The task struct holds the current hash value (initialized
  203.          * with zero), here we store the previous hash value:
  204.          */
  205.         u64                             prev_chain_key;
  206.         unsigned long                   acquire_ip;
  207.         struct lockdep_map              *instance;
  208.         struct lockdep_map              *nest_lock;
  209. #ifdef CONFIG_LOCK_STAT
  210.         u64                             waittime_stamp;
  211.         u64                             holdtime_stamp;
  212. #endif
  213.         unsigned int                    class_idx:MAX_LOCKDEP_KEYS_BITS;
  214.         /*
  215.          * The lock-stack is unified in that the lock chains of interrupt
  216.          * contexts nest ontop of process context chains, but we 'separate'
  217.          * the hashes by starting with 0 if we cross into an interrupt
  218.          * context, and we also keep do not add cross-context lock
  219.          * dependencies - the lock usage graph walking covers that area
  220.          * anyway, and we'd just unnecessarily increase the number of
  221.          * dependencies otherwise. [Note: hardirq and softirq contexts
  222.          * are separated from each other too.]
  223.          *
  224.          * The following field is used to detect when we cross into an
  225.          * interrupt context:
  226.          */
  227.         unsigned int irq_context:2; /* bit 0 - soft, bit 1 - hard */
  228.         unsigned int trylock:1;                                         /* 16 bits */
  229.  
  230.         unsigned int read:2;        /* see lock_acquire() comment */
  231.         unsigned int check:2;       /* see lock_acquire() comment */
  232.         unsigned int hardirqs_off:1;
  233.         unsigned int references:11;                                     /* 32 bits */
  234. };
  235.  
  236. /*
  237.  * Initialization, self-test and debugging-output methods:
  238.  */
  239. extern void lockdep_init(void);
  240. extern void lockdep_info(void);
  241. extern void lockdep_reset(void);
  242. extern void lockdep_reset_lock(struct lockdep_map *lock);
  243. extern void lockdep_free_key_range(void *start, unsigned long size);
  244. extern void lockdep_sys_exit(void);
  245.  
  246. extern void lockdep_off(void);
  247. extern void lockdep_on(void);
  248.  
  249. /*
  250.  * These methods are used by specific locking variants (spinlocks,
  251.  * rwlocks, mutexes and rwsems) to pass init/acquire/release events
  252.  * to lockdep:
  253.  */
  254.  
  255. extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
  256.                              struct lock_class_key *key, int subclass);
  257.  
  258. /*
  259.  * To initialize a lockdep_map statically use this macro.
  260.  * Note that _name must not be NULL.
  261.  */
  262. #define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
  263.         { .name = (_name), .key = (void *)(_key), }
  264.  
  265. /*
  266.  * Reinitialize a lock key - for cases where there is special locking or
  267.  * special initialization of locks so that the validator gets the scope
  268.  * of dependencies wrong: they are either too broad (they need a class-split)
  269.  * or they are too narrow (they suffer from a false class-split):
  270.  */
  271. #define lockdep_set_class(lock, key) \
  272.                 lockdep_init_map(&(lock)->dep_map, #key, key, 0)
  273. #define lockdep_set_class_and_name(lock, key, name) \
  274.                 lockdep_init_map(&(lock)->dep_map, name, key, 0)
  275. #define lockdep_set_class_and_subclass(lock, key, sub) \
  276.                 lockdep_init_map(&(lock)->dep_map, #key, key, sub)
  277. #define lockdep_set_subclass(lock, sub) \
  278.                 lockdep_init_map(&(lock)->dep_map, #lock, \
  279.                                  (lock)->dep_map.key, sub)
  280.  
  281. #define lockdep_set_novalidate_class(lock) \
  282.         lockdep_set_class(lock, &__lockdep_no_validate__)
  283. /*
  284.  * Compare locking classes
  285.  */
  286. #define lockdep_match_class(lock, key) lockdep_match_key(&(lock)->dep_map, key)
  287.  
  288. static inline int lockdep_match_key(struct lockdep_map *lock,
  289.                                     struct lock_class_key *key)
  290. {
  291.         return lock->key == key;
  292. }
  293.  
  294. /*
  295.  * Acquire a lock.
  296.  *
  297.  * Values for "read":
  298.  *
  299.  *   0: exclusive (write) acquire
  300.  *   1: read-acquire (no recursion allowed)
  301.  *   2: read-acquire with same-instance recursion allowed
  302.  *
  303.  * Values for check:
  304.  *
  305.  *   0: disabled
  306.  *   1: simple checks (freeing, held-at-exit-time, etc.)
  307.  *   2: full validation
  308.  */
  309. extern void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  310.                          int trylock, int read, int check,
  311.                          struct lockdep_map *nest_lock, unsigned long ip);
  312.  
  313. extern void lock_release(struct lockdep_map *lock, int nested,
  314.                          unsigned long ip);
  315.  
  316. #define lockdep_is_held(lock)   lock_is_held(&(lock)->dep_map)
  317.  
  318. extern int lock_is_held(struct lockdep_map *lock);
  319.  
  320. extern void lock_set_class(struct lockdep_map *lock, const char *name,
  321.                            struct lock_class_key *key, unsigned int subclass,
  322.                            unsigned long ip);
  323.  
  324. static inline void lock_set_subclass(struct lockdep_map *lock,
  325.                 unsigned int subclass, unsigned long ip)
  326. {
  327.         lock_set_class(lock, lock->name, lock->key, subclass, ip);
  328. }
  329.  
  330. extern void lockdep_set_current_reclaim_state(gfp_t gfp_mask);
  331. extern void lockdep_clear_current_reclaim_state(void);
  332. extern void lockdep_trace_alloc(gfp_t mask);
  333.  
  334. # define INIT_LOCKDEP                           .lockdep_recursion = 0, .lockdep_reclaim_gfp = 0,
  335.  
  336. #define lockdep_depth(tsk)      (debug_locks ? (tsk)->lockdep_depth : 0)
  337.  
  338. #define lockdep_assert_held(l)  WARN_ON(debug_locks && !lockdep_is_held(l))
  339.  
  340. #else /* !LOCKDEP */
  341.  
  342. static inline void lockdep_off(void)
  343. {
  344. }
  345.  
  346. static inline void lockdep_on(void)
  347. {
  348. }
  349.  
  350. # define lock_acquire(l, s, t, r, c, n, i)      do { } while (0)
  351. # define lock_release(l, n, i)                  do { } while (0)
  352. # define lock_set_class(l, n, k, s, i)          do { } while (0)
  353. # define lock_set_subclass(l, s, i)             do { } while (0)
  354. # define lockdep_set_current_reclaim_state(g)   do { } while (0)
  355. # define lockdep_clear_current_reclaim_state()  do { } while (0)
  356. # define lockdep_trace_alloc(g)                 do { } while (0)
  357. # define lockdep_init()                         do { } while (0)
  358. # define lockdep_info()                         do { } while (0)
  359. # define lockdep_init_map(lock, name, key, sub) \
  360.                 do { (void)(name); (void)(key); } while (0)
  361. # define lockdep_set_class(lock, key)           do { (void)(key); } while (0)
  362. # define lockdep_set_class_and_name(lock, key, name) \
  363.                 do { (void)(key); (void)(name); } while (0)
  364. #define lockdep_set_class_and_subclass(lock, key, sub) \
  365.                 do { (void)(key); } while (0)
  366. #define lockdep_set_subclass(lock, sub)         do { } while (0)
  367.  
  368. #define lockdep_set_novalidate_class(lock) do { } while (0)
  369.  
  370. /*
  371.  * We don't define lockdep_match_class() and lockdep_match_key() for !LOCKDEP
  372.  * case since the result is not well defined and the caller should rather
  373.  * #ifdef the call himself.
  374.  */
  375.  
  376. # define INIT_LOCKDEP
  377. # define lockdep_reset()                do { debug_locks = 1; } while (0)
  378. # define lockdep_free_key_range(start, size)    do { } while (0)
  379. # define lockdep_sys_exit()                     do { } while (0)
  380. /*
  381.  * The class key takes no space if lockdep is disabled:
  382.  */
  383. struct lock_class_key { };
  384.  
  385. #define lockdep_depth(tsk)      (0)
  386.  
  387. #define lockdep_assert_held(l)                  do { } while (0)
  388.  
  389. #endif /* !LOCKDEP */
  390.  
  391. #ifdef CONFIG_LOCK_STAT
  392.  
  393. extern void lock_contended(struct lockdep_map *lock, unsigned long ip);
  394. extern void lock_acquired(struct lockdep_map *lock, unsigned long ip);
  395.  
  396. #define LOCK_CONTENDED(_lock, try, lock)                        \
  397. do {                                                            \
  398.         if (!try(_lock)) {                                      \
  399.                 lock_contended(&(_lock)->dep_map, _RET_IP_);    \
  400.                 lock(_lock);                                    \
  401.         }                                                       \
  402.         lock_acquired(&(_lock)->dep_map, _RET_IP_);                     \
  403. } while (0)
  404.  
  405. #else /* CONFIG_LOCK_STAT */
  406.  
  407. #define lock_contended(lockdep_map, ip) do {} while (0)
  408. #define lock_acquired(lockdep_map, ip) do {} while (0)
  409.  
  410. #define LOCK_CONTENDED(_lock, try, lock) \
  411.         lock(_lock)
  412.  
  413. #endif /* CONFIG_LOCK_STAT */
  414.  
  415. #ifdef CONFIG_LOCKDEP
  416.  
  417. /*
  418.  * On lockdep we dont want the hand-coded irq-enable of
  419.  * _raw_*_lock_flags() code, because lockdep assumes
  420.  * that interrupts are not re-enabled during lock-acquire:
  421.  */
  422. #define LOCK_CONTENDED_FLAGS(_lock, try, lock, lockfl, flags) \
  423.         LOCK_CONTENDED((_lock), (try), (lock))
  424.  
  425. #else /* CONFIG_LOCKDEP */
  426.  
  427. #define LOCK_CONTENDED_FLAGS(_lock, try, lock, lockfl, flags) \
  428.         lockfl((_lock), (flags))
  429.  
  430. #endif /* CONFIG_LOCKDEP */
  431.  
  432. #ifdef CONFIG_TRACE_IRQFLAGS
  433. extern void early_boot_irqs_off(void);
  434. extern void early_boot_irqs_on(void);
  435. extern void print_irqtrace_events(struct task_struct *curr);
  436. #else
  437. static inline void early_boot_irqs_off(void)
  438. {
  439. }
  440. static inline void early_boot_irqs_on(void)
  441. {
  442. }
  443. static inline void print_irqtrace_events(struct task_struct *curr)
  444. {
  445. }
  446. #endif
  447.  
  448. /*
  449.  * For trivial one-depth nesting of a lock-class, the following
  450.  * global define can be used. (Subsystems with multiple levels
  451.  * of nesting should define their own lock-nesting subclasses.)
  452.  */
  453. #define SINGLE_DEPTH_NESTING                    1
  454.  
  455. /*
  456.  * Map the dependency ops to NOP or to real lockdep ops, depending
  457.  * on the per lock-class debug mode:
  458.  */
  459.  
  460. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  461. # ifdef CONFIG_PROVE_LOCKING
  462. #  define spin_acquire(l, s, t, i)              lock_acquire(l, s, t, 0, 2, NULL, i)
  463. #  define spin_acquire_nest(l, s, t, n, i)      lock_acquire(l, s, t, 0, 2, n, i)
  464. # else
  465. #  define spin_acquire(l, s, t, i)              lock_acquire(l, s, t, 0, 1, NULL, i)
  466. #  define spin_acquire_nest(l, s, t, n, i)      lock_acquire(l, s, t, 0, 1, NULL, i)
  467. # endif
  468. # define spin_release(l, n, i)                  lock_release(l, n, i)
  469. #else
  470. # define spin_acquire(l, s, t, i)               do { } while (0)
  471. # define spin_release(l, n, i)                  do { } while (0)
  472. #endif
  473.  
  474. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  475. # ifdef CONFIG_PROVE_LOCKING
  476. #  define rwlock_acquire(l, s, t, i)            lock_acquire(l, s, t, 0, 2, NULL, i)
  477. #  define rwlock_acquire_read(l, s, t, i)       lock_acquire(l, s, t, 2, 2, NULL, i)
  478. # else
  479. #  define rwlock_acquire(l, s, t, i)            lock_acquire(l, s, t, 0, 1, NULL, i)
  480. #  define rwlock_acquire_read(l, s, t, i)       lock_acquire(l, s, t, 2, 1, NULL, i)
  481. # endif
  482. # define rwlock_release(l, n, i)                lock_release(l, n, i)
  483. #else
  484. # define rwlock_acquire(l, s, t, i)             do { } while (0)
  485. # define rwlock_acquire_read(l, s, t, i)        do { } while (0)
  486. # define rwlock_release(l, n, i)                do { } while (0)
  487. #endif
  488.  
  489. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  490. # ifdef CONFIG_PROVE_LOCKING
  491. #  define mutex_acquire(l, s, t, i)             lock_acquire(l, s, t, 0, 2, NULL, i)
  492. # else
  493. #  define mutex_acquire(l, s, t, i)             lock_acquire(l, s, t, 0, 1, NULL, i)
  494. # endif
  495. # define mutex_release(l, n, i)                 lock_release(l, n, i)
  496. #else
  497. # define mutex_acquire(l, s, t, i)              do { } while (0)
  498. # define mutex_release(l, n, i)                 do { } while (0)
  499. #endif
  500.  
  501. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  502. # ifdef CONFIG_PROVE_LOCKING
  503. #  define rwsem_acquire(l, s, t, i)             lock_acquire(l, s, t, 0, 2, NULL, i)
  504. #  define rwsem_acquire_read(l, s, t, i)        lock_acquire(l, s, t, 1, 2, NULL, i)
  505. # else
  506. #  define rwsem_acquire(l, s, t, i)             lock_acquire(l, s, t, 0, 1, NULL, i)
  507. #  define rwsem_acquire_read(l, s, t, i)        lock_acquire(l, s, t, 1, 1, NULL, i)
  508. # endif
  509. # define rwsem_release(l, n, i)                 lock_release(l, n, i)
  510. #else
  511. # define rwsem_acquire(l, s, t, i)              do { } while (0)
  512. # define rwsem_acquire_read(l, s, t, i)         do { } while (0)
  513. # define rwsem_release(l, n, i)                 do { } while (0)
  514. #endif
  515.  
  516. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  517. # ifdef CONFIG_PROVE_LOCKING
  518. #  define lock_map_acquire(l)           lock_acquire(l, 0, 0, 0, 2, NULL, _THIS_IP_)
  519. # else
  520. #  define lock_map_acquire(l)           lock_acquire(l, 0, 0, 0, 1, NULL, _THIS_IP_)
  521. # endif
  522. # define lock_map_release(l)                    lock_release(l, 1, _THIS_IP_)
  523. #else
  524. # define lock_map_acquire(l)                    do { } while (0)
  525. # define lock_map_release(l)                    do { } while (0)
  526. #endif
  527.  
  528. #ifdef CONFIG_PROVE_LOCKING
  529. # define might_lock(lock)                                               \
  530. do {                                                                    \
  531.         typecheck(struct lockdep_map *, &(lock)->dep_map);              \
  532.         lock_acquire(&(lock)->dep_map, 0, 0, 0, 2, NULL, _THIS_IP_);    \
  533.         lock_release(&(lock)->dep_map, 0, _THIS_IP_);                   \
  534. } while (0)
  535. # define might_lock_read(lock)                                          \
  536. do {                                                                    \
  537.         typecheck(struct lockdep_map *, &(lock)->dep_map);              \
  538.         lock_acquire(&(lock)->dep_map, 0, 0, 1, 2, NULL, _THIS_IP_);    \
  539.         lock_release(&(lock)->dep_map, 0, _THIS_IP_);                   \
  540. } while (0)
  541. #else
  542. # define might_lock(lock) do { } while (0)
  543. # define might_lock_read(lock) do { } while (0)
  544. #endif
  545.  
  546. #ifdef CONFIG_PROVE_RCU
  547. extern void lockdep_rcu_dereference(const char *file, const int line);
  548. #endif
  549.  
  550. #endif /* __LINUX_LOCKDEP_H */
  551.