lockdep: Improve implementation of BFS

[firefly-linux-kernel-4.4.55.git] / kernel / lockdep_internals.h

diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
index 699a2ac3a0d71c53476f5f0ba60436f40da8c58c..c2f6594966f32c25355cff19634bfe7f596acffd 100644 (file)
--- a/kernel/lockdep_internals.h
+++ b/kernel/lockdep_internals.h
@@ -136,3 +136,97 @@ extern atomic_t nr_find_usage_backwards_recursions;
 # define debug_atomic_dec(ptr)         do { } while (0)
 # define debug_atomic_read(ptr)                0
 #endif
+
+
+extern unsigned long nr_list_entries;
+extern struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
+extern unsigned long bfs_accessed[];
+
+/*For good efficiency of modular, we use power of 2*/
+#define  MAX_CIRCULAR_QUE_SIZE     4096UL
+
+/* The circular_queue and helpers is used to implement the
+ * breadth-first search(BFS)algorithem, by which we can build
+ * the shortest path from the next lock to be acquired to the
+ * previous held lock if there is a circular between them.
+ * */
+struct circular_queue{
+       unsigned long element[MAX_CIRCULAR_QUE_SIZE];
+       unsigned int  front, rear;
+};
+
+static inline void __cq_init(struct circular_queue *cq)
+{
+       cq->front = cq->rear = 0;
+       bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
+}
+
+static inline int __cq_empty(struct circular_queue *cq)
+{
+       return (cq->front == cq->rear);
+}
+
+static inline int __cq_full(struct circular_queue *cq)
+{
+       return ((cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1))  == cq->front;
+}
+
+static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
+{
+       if (__cq_full(cq))
+               return -1;
+
+       cq->element[cq->rear] = elem;
+       cq->rear = (cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1);
+       return 0;
+}
+
+static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem)
+{
+       if (__cq_empty(cq))
+               return -1;
+
+       *elem = cq->element[cq->front];
+       cq->front = (cq->front + 1)&(MAX_CIRCULAR_QUE_SIZE-1);
+       return 0;
+}
+
+static inline int __cq_get_elem_count(struct circular_queue *cq)
+{
+       return (cq->rear - cq->front)&(MAX_CIRCULAR_QUE_SIZE-1);
+}
+
+static inline void mark_lock_accessed(struct lock_list *lock,
+                                       struct lock_list *parent)
+{
+       unsigned long nr;
+       nr = lock - list_entries;
+       WARN_ON(nr >= nr_list_entries);
+       lock->parent = parent;
+       set_bit(nr, bfs_accessed);
+}
+
+static inline unsigned long lock_accessed(struct lock_list *lock)
+{
+       unsigned long nr;
+       nr = lock - list_entries;
+       WARN_ON(nr >= nr_list_entries);
+       return test_bit(nr, bfs_accessed);
+}
+
+static inline struct lock_list *get_lock_parent(struct lock_list *child)
+{
+       return child->parent;
+}
+
+static inline unsigned long get_lock_depth(struct lock_list *child)
+{
+       unsigned long depth = 0;
+       struct lock_list *parent;
+
+       while ((parent = get_lock_parent(child))) {
+               child = parent;
+               depth++;
+       }
+       return depth;
+}