arm linux启动流程二

3790阅读　0评论2014-08-18　wangbaolin719
分类：LINUX


  1. 一、概述
  2. 在Linux系统里，假设有两处代码（比如不同线程的两个函数F1和F2）都要获取两个锁（分别为L1和L2），如果F1持有L1后再去获取L2，而此时恰好由F2持有L2且它也正在尝试获取L1，那么此时就是处于死锁的状态，这是一个最简单的死锁例子，也即所谓的AB-BA死锁。

  4. 死锁导致的最终结果无需多说，关于如何避免死锁在教科书上也有提到，最简单直观的做法就是按顺序上锁，以破坏死锁的环形等待条件。但对于拥有成千上万个锁的整个系统来说，完全定义它们之间的顺序是非常困难的，所以一种更可行的办法就是尽量提前发现这其中潜在的死锁风险，而不是等到最后真正出现死锁时给用户带来切实的困惑。
  5. 已有很多工具用于发现可能的死锁风险，而本文介绍的调试/检测模块lockdep，即是属于这一类工具的一种。调试模块lockdep从2006年引入内核，经过实践验证，其对提前发现死锁起到了巨大的效果

  7. 官方文档有介绍调试模块lockdep的设计原理，这里按照我自己的理解描述一下。
  8. 1，lockdep操作的基本单元并非单个的锁实例，而是锁类（lock-class）。比如，struct inode结构体中的自旋锁i_lock字段就代表了这一类锁，而具体每个inode节点的锁只是该类锁中的一个实例。对所有这些实例，lockdep会把它们当作一个整体做处理，即把判断粒度放大，否则对可能有成千上万个的实例进行逐一判断，那处理难度可想而知，而且也没有必要。当然，在具体的处理中，可能会记录某些特性情况下的实例的部分相关信息，以便提供事后问题排查。
  9. 2，lockdep跟踪每个锁类的自身状态，也跟踪各个锁类之间的依赖关系，通过一系列的验证规则，以确保锁类状态和锁类之间的依赖总是正确的。另外，锁类一旦在初次使用时被注册，那么后续就会一直存在，所有它的具体实例都会关联到它。

  11. lockdep是linux内核的一个调试模块，用来检查内核互斥机制尤其是自旋锁潜在的死锁问题。自旋锁由于是查询方式等待，不释放处理器，比一般的互斥机制更容易死锁，故引入lockdep检查以下几种情况可能的死锁。
  12. 1.同一个进程递归地加锁同一把锁.
  13. 2.一把锁既在中断（或中断下半部）使能的情况下执行过加锁操作，又在中断（或中断下半部）里执行过加锁操作。这样该锁有可能在锁定时由于中断发生又试图在同一处理器上加锁,加锁后导致依赖图产生成闭环，这是典型的死锁现象。

  15. 二、 lockdep验证规则
  16. (1)单锁状态规则（Single-lock state rules）
  17. 1，一个软中断不安全（softirq-unsafe）的锁类同样也是硬中断不安全（hardirq-unsafe）的。
  18. 2，对于任何一个锁类，它不可能同时是hardirq-safe和hardirq-unsafe，也不可能同时是softirq-safe和softirq-unsafe，即这两对对应状态是互斥的。
  19. 上面这两条就是lockdep判断单锁是否会发生死锁的检测规则。
  20. (2)多锁依赖规则（Multi-lock dependency rules）
  21. 1，同一个锁类不能被获取两次，因为这会导致递归死锁。
  22. 2，不能以不同的顺序获取两个锁类，即如此这样：
  23. <L1> -> <L2>
  24. <L2> -> <L1>
  25. 是不行的。因为这会非常容易的导致本文最先提到的AB-BA死锁。当然，下面这样的情况也不行：    
  26. <L1> -> <L3> -> <L4> -> <L2>
  27. <L2> -> <L3> -> <L4> -> <L1>
  28. 即在中间插入了其它正常顺序的锁也能被lockdep检测出来。
  29. 3，同一个锁实例在任何两个锁类之间不能出现这样的情况：    
  30. <hardirq-safe> -> <hardirq-unsafe>
  31. <softirq-safe> -> <softirq-unsafe>
  32. 这意味着，如果同一个锁实例，在某些地方是hardirq-safe（即采用spin_lock_irqsave(…)），而在某些地方又是hardirq-unsafe（即采用spin_lock(…)），那么就存在死锁的风险。这应该容易理解，比如在进程上下文中持有锁A，并且锁A是hardirq-unsafe，如果此时触发硬中断，而硬中断处理函数又要去获取锁A，那么就导致了死锁。
  33. 在锁类状态发生变化时，进行如下几个规则检测，判断是否存在潜在死锁。比较简单，就是判断hardirq-safe和hardirq-unsafe以及softirq-safe和softirq-unsafe是否发生了碰撞.

  35. 三、相关结构体
  36. 1.struct held_lock
  37. 在每个进程的task_struct结构体中定义了struct held_lock held_locks[MAX_LOCK_DEPTH]成员，用来记录锁。
  38. struct held_lock {
  39. 215 /*
  40. 216 * One-way hash of the dependency chain up to this point. We
  41. 217 * hash the hashes step by step as the dependency chain grows.
  42. 218 *
  43. 219 * We use it for dependency-caching and we skip detection
  44. 220 * passes and dependency-updates if there is a cache-hit, so
  45. 221 * it is absolutely critical for 100% coverage of the validator
  46. 222 * to have a unique key value for every unique dependency path
  47. 223 * that can occur in the system, to make a unique hash value
  48. 224 * as likely as possible - hence the 64-bit width.
  49. 225 *
  50. 226 * The task struct holds the current hash value (initialized
  51. 227 * with zero), here we store the previous hash value:
  52. 228 */
  53.     u64 prev_chain_key;
  54.     unsigned long acquire_ip;
  55.     struct lockdep_map *instance;
  56.     struct lockdep_map *nest_lock;
  57. #ifdef CONFIG_LOCK_STAT
  58.     u64 waittime_stamp;
  59.     u64 holdtime_stamp;
  60. #endif
  61.     unsigned int class_idx:MAX_LOCKDEP_KEYS_BITS;
  62. 238 /*
  63. 239 * The lock-stack is unified in that the lock chains of interrupt
  64. 240 * contexts nest ontop of process context chains, but we 'separate'
  65. 241 * the hashes by starting with 0 if we cross into an interrupt
  66. 242 * context, and we also keep do not add cross-context lock
  67. 243 * dependencies - the lock usage graph walking covers that area
  68. 244 * anyway, and we'd just unnecessarily increase the number of
  69. 245 * dependencies otherwise. [Note: hardirq and softirq contexts
  70. 246 * are separated from each other too.]
  71. 247 *
  72. 248 * The following field is used to detect when we cross into an
  73. 249 * interrupt context:
  74. 250 */
  75.     unsigned int irq_context:2; /* bit 0 - soft, bit 1 - hard */
  76.     unsigned int trylock:1; /* 16 bits */
  77.     
  78.     unsigned int read:2; /* see lock_acquire() comment */
  79.     unsigned int check:2; /* see lock_acquire() comment */
  80.     unsigned int hardirqs_off:1;
  81.     unsigned int references:11; /* 32 bits */
  82. };

  84. 2.lockdep_map
  85. 各种锁结构体中如mutex、rawspinlock、semaphore内嵌该结构体，用于对锁检测。
  86. struct lockdep_map {
  87.     struct lock_class_key *key;
  88.     struct lock_class *class_cache[NR_LOCKDEP_CACHING_CLASSES];
  89.     const char *name;
  90. #ifdef CONFIG_LOCK_STAT
  91.     int cpu;    //对结构体初始化时所在的cpu号
  92.     unsigned long ip;
  93. #endif
  94. };

  96. 3.lock_class
  97. struct lock_class {
  98.     struct list_head hash_entry;
  99.     struct list_head lock_entry;
  100.     
  101.     struct lockdep_subclass_key *key;
  102.     unsigned int subclass;
  103.     unsigned int dep_gen_id;

  105.     unsigned long usage_mask;
  106.     struct stack_trace usage_traces[XXX_LOCK_USAGE_STATES];

  108.     struct list_head locks_after, locks_before;
  109.     unsigned int version;
  110.     unsigned long ops;
  111.         
  112.     const char *name;
  113.     int name_version;

  115. #ifdef CONFIG_LOCK_STAT
  116.     unsigned long contention_point[LOCKSTAT_POINTS];
  117.     unsigned long contending_point[LOCKSTAT_POINTS];
  118. #endif
  119. };

  121. 4.lock_class_key
  122. struct lock_class_key {
  123.     struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES];
  124. };

  126. 5.lockdep_subclass_key
  127. struct lockdep_subclass_key {
  128.     char __one_byte;
  129. } __attribute__ ((__packed__));


  132. 三、lockdep初始化
  133. 建立两个散列表calsshash_table和chainhash_table，并初始化全局变量lockdep_initialized，标志已初始化完成。
  134. static struct list_head classhash_table[CLASSHASH_SIZE];
  135. static struct list_head chainhash_table[CHAINHASH_SIZE];
  136. void lockdep_init(void)
  137. {
  138.     int i;

  140.     if (lockdep_initialized)
  141.         return;
  142.     
  143.     for (i = 0; i < CLASSHASH_SIZE; i++)
  144.         INIT_LIST_HEAD(classhash_table + i);
  145.     
  146.     for (i = 0; i < CHAINHASH_SIZE; i++)
  147.         INIT_LIST_HEAD(chainhash_table + i);
  148.     
  149.     lockdep_initialized = 1;
  150. }

  152. 四、提供接口
  153. 1. lockdep_init_map
  154. 用于初始化锁内嵌的lockdep_map结构体
  155. static inline void sema_init(struct semaphore *sem, int val)
  156. {
  157.     static struct lock_class_key __key;
  158.     *sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val);
  159.     lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0);
  160. }

  162. void lockdep_init_map(struct lockdep_map *lock, const char *name,struct lock_class_key *key, int subclass)
  163. {
  164.     int i;
  165.     
  166.     //arm上是空函数    
  167.     kmemcheck_mark_initialized(lock, sizeof(*lock));
  168.     
  169.     //初始化lock_class结构体的class_cache成员
  170.     for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
  171.         lock->class_cache[i] = NULL;

  173. #ifdef CONFIG_LOCK_STAT
  174.     lock->cpu = raw_smp_processor_id();
  175. #endif    
  176.     //name不能为空
  177.     if (DEBUG_LOCKS_WARN_ON(!name)) {
  178.         lock->name = "NULL";
  179.         return;
  180.     }
  181.     //设置name
  182.     lock->name = name;

  184.     //key不能为空
  185.     if (DEBUG_LOCKS_WARN_ON(!key))
  186.         return;
  187.     
  188.     //对key的地址进行健康检查，确保在内核.data地址空间,percpu空间或者module空间
  189.     if (!static_obj(key)) {
  190.         printk("BUG: key %p not in .data!\n", key);
  191.         DEBUG_LOCKS_WARN_ON(1);
  192.         return;
  193.     }
  194.     //设置key
  195.     lock->key = key;
  196.  
  197.     if (unlikely(!debug_locks))
  198.         return;
  199.     
  200.     //subclass不为0，将lockdep_map注册到类中
  201.     if (subclass)
  202.         register_lock_class(lock, subclass, 1);
  203. }

  205. 2.
  206. void lock_acquire(struct lockdep_map *lock, unsigned int subclass,int trylock, int read, int check,struct lockdep_map *nest_lock, unsigned long ip)
  207. {
  208.     unsigned long flags;
  209.         
  210.     if (unlikely(current->lockdep_recursion))
  211.         return;
  212.         
  213.     raw_local_irq_save(flags);
  214.     check_flags(flags);
  215.         
  216.     current->lockdep_recursion = 1;
  217.     //空函数
  218.     trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
  219.     __lock_acquire(lock, subclass, trylock, read, check,irqs_disabled_flags(flags), nest_lock, ip, 0);
  220.     current->lockdep_recursion = 0;
  221.     raw_local_irq_restore(flags);
  222. }

  224. 2. debug_check_no_locks_freed
  225. 用于检测一个锁是不是被多次初始化，或者一块内存在释放时还持有锁。
  226. void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
  227. {
  228.     struct task_struct *curr = current;
  229.     struct held_lock *hlock;
  230.     unsigned long flags;
  231.     int i;
  232.         
  233.     if (unlikely(!debug_locks))
  234.         return;
  235.     
  236.     local_irq_save(flags);
  237.     //遍历当前进程所拥有的held_lock
  238.     for (i = 0; i < curr->lockdep_depth; i++) {
  239.         hlock = curr->held_locks + i;
  240.     
  241.         //检查hlock是否在(mem_from,mem_from+mem_len)区间里，不在此区间则继续循环
  242.         if (not_in_range(mem_from, mem_len, hlock->instance,sizeof(*hlock->instance)))
  243.             continue;
  244.     
  245.         print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock);
  246.         break;
  247.     }
  248.     local_irq_restore(flags);
  249. }

  251. static inline int not_in_range(const void* mem_from, unsigned long mem_len,
  252.                                 const void* lock_from, unsigned long lock_len)
  253. {
  254.     return lock_from + lock_len <= mem_from || mem_from + mem_len <= lock_from;
  255. }

  257. static void print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
  258.                                 const void *mem_to, struct held_lock *hlock)
  259. {
  260.     //如果关闭所有lock-debugging，则退出
  261.     if (!debug_locks_off())
  262.         return;
  263.     //
  264.     if (debug_locks_silent)
  265.         return;
  266.     
  267.     printk("\n");
  268.     printk("=========================\n");
  269.     printk("[ BUG: held lock freed! ]\n");
  270.     print_kernel_ident();
  271.     printk("-------------------------\n");
  272.     printk("%s/%d is freeing memory %p-%p, with a lock still held there!\n",
  273.         curr->comm, task_pid_nr(curr), mem_from, mem_to-1);
  274.     print_lock(hlock);//打印锁信息
  275.     lockdep_print_held_locks(curr);
  276.  
  277.     printk("\nstack backtrace:\n");
  278.     dump_stack();//打印堆栈信息
  279. }

  281. //Generic 'turn off all lock debugging' function:
  282. int debug_locks_off(void)
  283. {
  284.     if (__debug_locks_off()) {
  285.         if (!debug_locks_silent) {
  286.             console_verbose();
  287.             return 1;
  288.         }
  289.     }
  290.     return 0;
  291. }

  293. //debug_locks为1表示打开lock-debugging，为0表示关闭所有lock-debugging
  294. static inline int __debug_locks_off(void)
  295. {
  296.     return xchg(&debug_locks, 0);
  297. }

  299. static void print_kernel_ident(void)
  300. {
  301.     printk("%s %.*s %s\n", init_utsname()->release,
  302.         (int)strcspn(init_utsname()->version, " "),
  303.         init_utsname()->version,
  304.         print_tainted());
  305. }

  307. static void print_lock(struct held_lock *hlock)
  308. {
  309.     print_lock_name(hlock_class(hlock));
  310.     printk(", at: ");
  311.     print_ip_sym(hlock->acquire_ip);
  312. }

  314. static inline struct lock_class *hlock_class(struct held_lock *hlock)
  315. {
  316.     if (!hlock->class_idx) {
  317.         DEBUG_LOCKS_WARN_ON(1);
  318.         return NULL;
  319.     }
  320.     return lock_classes + hlock->class_idx - 1;
  321. }

  323. static void print_lock_name(struct lock_class *class)
  324. {
  325. 529 char usage[LOCK_USAGE_CHARS];
  326. 530
  327. 531 get_usage_chars(class, usage);
  328. 532
  329. 533 printk(" (");
  330. 534 __print_lock_name(class);
  331. 535 printk("){%s}", usage);
  332. }

  334. static void __print_lock_name(struct lock_class *class)
  335. {
  336. 511 char str[KSYM_NAME_LEN];
  337. 512 const char *name;
  338. 513
  339. 514 name = class->name;
  340. 515 if (!name) {
  341. 516 name = __get_key_name(class->key, str);
  342. 517 printk("%s", name);
  343. 518 } else {
  344. 519 printk("%s", name);
  345. 520 if (class->name_version > 1)
  346. 521 printk("#%d", class->name_version);
  347. 522 if (class->subclass)
  348. 523 printk("/%d", class->subclass);
  349. 524 }
  350. }

  352. static inline void print_ip_sym(unsigned long ip)
  353. {
  354.     printk("[<%p>] %pS\n", (void *) ip, (void *) ip);
  355. }

  357. static void lockdep_print_held_locks(struct task_struct *curr)
  358. {
  359.     int i, depth = curr->lockdep_depth;
  360.     
  361.     if (!depth) {
  362.         printk("no locks held by %s/%d.\n", curr->comm, task_pid_nr(curr));
  363.         return;
  364.     }
  365.     printk("%d lock%s held by %s/%d:\n",
  366.         depth, depth > 1 ? "s" : "", curr->comm, task_pid_nr(curr));
  367.     
  368.     for (i = 0; i < depth; i++) {
  369.         printk(" #%d: ", i);
  370.         print_lock(curr->held_locks + i);
  371.     }
  372. }

  374. 2.


  377. 参考http://www.lenky.info/archives/2013/04/2253

上一篇：scatterlist分析
下一篇：arm linux启动流程三