object c 里面有一个非常有趣的设计，如果之前了解过c++的家伙们，对object c 中的把传统的调用函数变成了向这个类发送消息，这个过程总是令人琢磨不透，在实际过程中遇到的crash也很难调试清楚。这篇就要详细的解释消息这个家伙。当然，消息这个涉及的东西实在是太多了。这篇先简单介绍一下。

上一篇，我们了解了什么是类《Objcclass》。同理这一篇，我们首先需要了解什么是message。

message（消息）：message的具体定义很难说，因为并没有真正的代码描述，简单的讲message 是一种抽象，包括了函数名+参数列表，他并没有实际的实体存在。

method（方法）：method是真正的存在的代码。如：- (int)meaning { return 42; }

selector:selector 通过SEL类型存在，描述一个特定的method or message。在实际编程中，可以通过selector来检索函数等操作。

我不知道上面这种描述有多少人可以明白，因为我觉得这3个每个人都可以有自己的看法，在了解object c message 的整个过程之后。

让我们从一个简单的例子开始。当我们写好如下的代码时

- (int)foo:(NSString *)str { ...}

　　

编译器事实上转成了下面的样子

int XXXX_XXXX_foo_(SomeClass *self, SEL _cmd, NSString *str) { ...}

　　

当我们写下发送消息的代码如

int result = [obj foo:@"hello"];

　　

实际上变成了

int result = ((int (*)(id, SEL, NSString *))objc_msgSend)(obj, @selector(foo:), @"hello");

　　

而 objc_msgSend 是一个我们非常熟悉的C函数定义 id objc_msgSend(id self, SEL _cmd,...);

那么，object c 发送消息就变成了一个表面上看似容易理解的C函数调用了，这里有必要解释一下几个名词

id：很多地方说id是一个void *的指针。事实上，id 其实是这样子的
typedef struct objc_object {
    Class isa;
} *id;

　　

也就是说。id其实是一个可以指向任何一个object指针（只要结构体中包含isa 指针） 。

SEL：SEL 如果很粗鲁（我不知道改用什么其他词汇更容易描述）的讲，就是一个char * 的指针。因为你可以这样简单粗暴的测试

SEL selector = @selector(message); //@selector不是函数调用，只是给这个坑爹的编译器的一个提示
NSLog (@"%s", (char *)selector);  //print message 

　　

不知道有没有人惊呼这个问题。特别是如果之前从事C++的家伙们。传统的C++ 编译器在处理函数上，为了支持函数重载。使用了一种函数别名的方式如

int foo（int a）；

　　

变成了 XXX_1_foo_int （具体的形式没有意义，核心在于，编译器生成的函数签名包括函数名，参数类型，参数个数）。

但我们的SEL 仅仅是函数名而已。

有了这些知识做铺垫，原谅我在把这个东东再搬出来

int result = ((int (*)(id, SEL, NSString *))objc_msgSend)(obj, @selector(foo:), @"hello");

　　

那么，作为程序员，我们就为这个而疯狂了，因为编译器无法根据id 和SEL 获得完整的函数签名，编译器对参数个数和类型，完全不知道。那么他如何能过做到识别这些并找到正确的代码呢？

事实上这个头痛的问题，编译器做了一个非常坑爹的事情，就是“ it cheats” ，他假装能够通过函数名，就能确定正确的代码。通过扫描之前的函数声明来做，如果没有找到，编译器就认为这是一个运行时（runtime）的函数而直接略过。而这也就导致了object c 在处理有相同函数名和参数个数但类型不同的函数时，非常的弱。如

-(void)setWidth:(int)width；

-(void)setWidth:(double)width；

　　

这样的函数则被认为是一种编译错误，而这最终导致了一个非常非常奇怪的object c 特色的函数命名

-(void)setWidthIntValue:(int)width；

-(void)setWidthDoubleValue:(double)width；

　　

popup our brain stack

objc_msgSend 这里传入了 class 指针 self 函数名SEL 已经后面通过C的不定参数传入的参数。通过这些条件。就像之前的C++函数那样，需要查表，并找到相应函数的位置，然后call xxxxx。那么。object c 是如何找到这些函数的真实地址呢？ 之前有篇简单描述C++类函数布局的，有兴趣的可以对比的看。

为了解释这些这个过程，我们有需要介入一些名词了。

object c 2 的

typedef struct method_list_t {
    uint32_t entsize_NEVER_USE;  // low 2 bits used for fixup markers
    uint32_t count;
    struct method_t first;
} method_list_t;

typedef struct method_t {
    SEL name;
    const char *types;
    IMP imp;
} method_t;

　　

method就是这么简单， 一个函数名SEL 一个包括的参数类型和返回类型的type 最后加一个IMP 而IMP 就是一个函数指针，指向我们真正的代码位置

typedef id             (*IMP)(id, SEL, ...); 

　　

那么objc_msgSend 做的事情，就是通过我们传入的self 指针，找到class 的method_list 然后根据SEL 做比较，没有的话，就在super class 找，如此往复。直到找到匹配的SEL，然后，call imp。

那么，我们就发现了。如果object c 这样设计，调用函数的成本实在是太高了，相对传统的C函数调用。那么编译器和runtime又做了那些优化呢？有意思的事情开始了。

1、字符串比较

我们发现了SEL 就是简单的一个char* 字符串。那么，光是比较这一串字符，就可以让object-c 慢的让人作呕了。那么我们就需要再认识一下我们的SEL了。

runtime 在实现selector是，实现了一个很大的Set，简单的说就是一个经过了杠杠优化过的hash表。而Set的特点就是唯一，也就是SEL是唯一的。那么对于字符串的比较仅仅需要比较他们的地址就可以了。犀利，速度上无语伦比，但是，有一个问题，就是数量增多会增大hash冲突而导致的性能下降（或是没有冲突，因为也可能用的是perfect hash）。但是不管使用什么样的方法加速，如果能够将总量减少，那将是最犀利的方法。那么，我们就不难理解，为什么SEL仅仅是函数名了。这样如

class A 有一个这样的method -(void)setWidth:(int)width；

而 classB 有一个这样的method -(void)setWidth:(double)width；

那么的selector 将指向同一个地方，使用同一个selector，如果真的需要在类中定义类似重载时，只能使用不同的函数名了。

但是，这样的优化，依然不能让人满意，因为，根据二八原则，我们真正执行的只是少数代码。那么。就有

2、cache

cache的原则就是缓存那些可能要执行的函数地址，那么下次调用的时候，速度就可以快速很多。这个和CPU的各种缓存原理相通。好吧，说了这么多了，再来认识几个名词

struct objc_cache {
    uintptr_t mask;            /* total = mask + 1 */
    uintptr_t occupied;        
    cache_entry *buckets[1];
};

typedef struct {
    SEL name;     // same layout as struct old_method
    void *unused;
    IMP imp;  // same layout as struct old_method
} cache_entry;

　　

看这个结构，有没有搞错又是hash table。

objc_msgSend 首先在cache list 中找SEL 没有找到就在class 找，super class 找（当然super class 也有cache list）。

而cache的机制则非常复杂了，由于object c 是动态语言。所以，这里面还有很多的多线程同步问题，而这些锁又是效率的大敌，相关的内容已经远远超过本文讨论的范围。

popup our brain stack

有了上面的粗略的介绍，是时候让我们看看objc_msgSend 的真面目了，当然，对于这个家伙是和性能息息相关的东西，没有任何缘由的是用汇编来写的。这里面贴出x86的，原谅我已经把arm汇编忘记了（主要原因是arm汇编是老师教得，x86是自学的，没有听学校老师的 ：P）。

/********************************************************************
 *
 * id objc_msgSend(id self, SEL    _cmd,...);
 *
 ********************************************************************/

    ENTRY    _objc_msgSend
    CALL_MCOUNTER    LP0

    movl    self(%esp), %eax

// check whether receiver is nil 
    testl    %eax, %eax
    je    LMsgSendNilSelf

// receiver is non-nil: search the cache
    CacheLookup WORD_RETURN, MSG_SEND, LMsgSendCacheMiss
    movl    $kFwdMsgSend, %edx    // flag word-return for _objc_msgForward
    jmp    *%eax            // goto *imp

// cache miss: go search the method lists
LMsgSendCacheMiss:
    MethodTableLookup WORD_RETURN, MSG_SEND
    movl    $kFwdMsgSend, %edx    // flag word-return for _objc_msgForward
    jmp    *%eax            // goto *imp

// message sent to nil object: call optional handler and return nil
LMsgSendNilSelf:
    EXTERN_TO_REG(__objc_msgNil,%eax)
    movl    0(%eax), %eax        // load nil message handler
    testl    %eax, %eax
    je    LMsgSendDone        // if NULL just return and don't do anything
    call    *%eax            // call __objc_msgNil
    xorl    %eax, %eax        // Rezero $eax just in case
LMsgSendDone:
    ret

LMsgSendExit:
    END_ENTRY    _objc_msgSend

　　

注释非常的详细+代码本身自解释，不做赘述，汇编的可读性都比我写的强，牛到不需要解释的代码。

MethodTableLookup 跳到__class_lookupMethodAndLoadCache

/***********************************************************************
* lookUpMethod.
* The standard method lookup. 
* initialize==NO tries to avoid +initialize (but sometimes fails)
* cache==NO skips optimistic unlocked lookup (but uses cache elsewhere)
* Most callers should use initialize==YES and cache==YES.
* May return _objc_msgForward_internal. IMPs destined for external use 
*   must be converted to _objc_msgForward or _objc_msgForward_stret.
**********************************************************************/
__private_extern__ IMP lookUpMethod(Class cls, SEL sel, 
                                    BOOL initialize, BOOL cache)
{
    Class curClass;
    IMP methodPC = NULL;
    Method meth;
    BOOL triedResolver = NO;

    // Optimistic cache lookup
    if (cache) {
        methodPC = _cache_getImp(cls, sel);
        if (methodPC) return methodPC;    
    }

    // realize, +initialize, and any special early exit
    methodPC = prepareForMethodLookup(cls, sel, initialize);
    if (methodPC) return methodPC;


    // The lock is held to make method-lookup + cache-fill atomic 
    // with respect to method addition. Otherwise, a category could 
    // be added but ignored indefinitely because the cache was re-filled 
    // with the old value after the cache flush on behalf of the category.
 retry:
    lockForMethodLookup();

    // Try this class's cache.

    //// self note 这里再次查找cache 是因为有可能cache真的又有了，因为锁的原因
    methodPC = _cache_getImp(cls, sel);
    if (methodPC) goto done;

    // Try this class's method lists.

     //self note 这个就是简单的在method 一个线性查找，因为我们仅仅是一个地址比较
    meth = _class_getMethodNoSuper_nolock(cls, sel); 
    if (meth) {
        //我们找到了函数地址，那么添加到cachelist中
        log_and_fill_cache(cls, cls, meth, sel);
        methodPC = method_getImplementation(meth);
        goto done;
    }

    // Try superclass caches and method lists.

    curClass = cls;
    while ((curClass = _class_getSuperclass(curClass))) {
        // Superclass cache.
        meth = _cache_getMethod(curClass, sel, &_objc_msgForward_internal);
        if (meth) {
            if (meth != (Method)1) {
                // Found the method in a superclass. Cache it in this class.
                log_and_fill_cache(cls, curClass, meth, sel);
                methodPC = method_getImplementation(meth);
                goto done;
            }
            else {
                // Found a forward:: entry in a superclass.
                // Stop searching, but don't cache yet; call method 
                // resolver for this class first.
                break;
            }
        }

        // Superclass method list.
        meth = _class_getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            log_and_fill_cache(cls, curClass, meth, sel);
            methodPC = method_getImplementation(meth);
            goto done;
        }
    }

    // No implementation found. Try method resolver once.

    if (!triedResolver) {
        unlockForMethodLookup();
        _class_resolveMethod(cls, sel);
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

    // No implementation found, and method resolver didn't help. 
    // Use forwarding.

    _cache_addForwardEntry(cls, sel);
    methodPC = &_objc_msgForward_internal;

 done:
    unlockForMethodLookup();

    // paranoia: look for ignored selectors with non-ignored implementations
    assert(!(sel == (SEL)kIgnore  &&  methodPC != (IMP)&_objc_ignored_method));

    return methodPC;
}

之前一直做C++开发，最近2个多月转 Objective-C， 入门的时候，遇到了很多的困惑。现在过节，正是解决他们的好时机。

主要参考来自link

Objective-C 也是面向对象的语言，那么，首先需要知道的就是什么是class。

C++ 的class相对 Objective-C 中的class，就简单明了很多了。C++ 中class简单的说，就是一个大的struct， 绝大部分的class可以在编译时决定好class的布局（通过虚继承来的class成员变量只能动态确定）。当然，最关键的是，你不可能在运行时创建一个class，因为所有的class在运行之前已经确定下来，并保存在二进制文件中。

但是， Objective-C 确不同， Objective-C 可以在运行中创建class，修改class等等。那么，改如何定义 Objective-C 中的class呢。

在这之前，我们先看一个简单的，class的实例对象。

@interface Object 
{

    //typedef struct objc_class *Class; 
    Class isa;    /* A pointer to the instance's class structure */ 
}

对象包含一个指向class的指针，而这也就意味着，任何包含class 的指针都可以被看做是对象（object）。

struct objc_class {            
    struct objc_class *isa;    //这里也有isa指针 
    struct objc_class *super_class;    //这里还有一个指向基类的指针 
    const char *name;        
    long version; 
    long info; 
    long instance_size; 
    struct objc_ivar_list *ivars;

    struct objc_method_list **methodLists;

    struct objc_cache *cache; 
     struct objc_protocol_list *protocols; 
};

//新的定义
typedef struct class_t {

    struct class_t *isa;

    struct class_t *superclass;

    Cache cache;

    IMP *vtable;

    class_rw_t *data;

} class_t;

显然，在 Objective-C 眼中，一切都是对象，甚至包括我们的class。而对象就是class的实例，那么，class是什么的实例呢，metaclass。

事实上，我们并没有解决问题。metaclass 事实上又是root metaclass 的实例，而root metaclass 自己又是 root metaclass 的实例，一图胜千言，不做赘述。

在应用程序中，常常需要将一个集合U（键值集合）和另一个集合T（数据集合）建立关系构造dictionary结构，来达到增删查改的需求。如果键值集合很小，那么可以直接采用Direct-address tables的方式实现。

假如我们的集合 U = {0, 1, …, m - 1}, 而且m并不大。如果我们的键和值对应唯一，那么我们可以通过构造一个大的数组来保存集合U，如下结构。

显然，当集合U增大，那么直接存储集合U变的不那么明智起来，而且，如果使用键的集合K变小是，我们浪费的空间也越来越大。当集合K比集合U小很多的时候，就是hash粉墨登场的时候了。hash将保存空间压缩到集合K的大小，并且控制查找元素的时间仍在O(1) 在平均情况下。

hash 通过hash函数h，将集合U 映射到hash表T[0,…, m-1]中， 即 h : U → {0, 1, …, m - 1}。显然，由于集合大小的限制，很可能造成有相同的key 指向了hash表中的同一项，如图。

我们将这一情况称为碰撞（Collision），解决碰撞的方法很多，最容易想到的是通过链表来保存碰撞的key。

一个简单的例子，linux2.4 在处理进程中，需要一个通过pid找到进程的要求，而具体实现则是利用了hash。在处理冲突时，采用的是链表的方法。不过由于是操作系统的代码，所以这里并不是通常意义的双向链表，pidhash_next 指向后一个进程，但是pidhash_pprev指向的是前一个进程的pidhash_next的地址。虽然不长，但是理解这段还是需要稍微动下脑筋，系统之所以这么实现，似乎是能够提高增加和删除时链表的效率。

/* PID hashing. (shouldnt this be dynamic?) */ 
#define PIDHASH_SZ (4096 >> 2) 
extern struct task_struct *pidhash[PIDHASH_SZ]; 
#define pid_hashfn(x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1)) 

static inline void hash_pid(struct task_struct *p) 
{ 
    struct task_struct **htable = &pidhash[pid_hashfn(p->pid)]; 
    if((p->pidhash_next = *htable) != NULL)//如果发生的冲突 
        (*htable)->pidhash_pprev = &p->pidhash_next;//这里可以看出，pprev是上一个进程的next指针的地址 
    *htable = p; 
    p->pidhash_pprev = htable;//新的进程的pprev是指向了hash表项中的自己的地址 
} 
static inline void unhash_pid(struct task_struct *p) 
{ 
    if(p->pidhash_next)//如果有冲突 
        p->pidhash_next->pidhash_pprev = p->pidhash_pprev; 
    *p->pidhash_pprev = p->pidhash_next;//当没有冲突时，就会置NULL 
} 
static inline struct task_struct *find_task_by_pid(int pid) 
{ 
    struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)]; 
    for(p = *htable; p && p->pid != pid; p = p->pidhash_next); 
    return p; 
}

SGI STL的例子 hash

SGI STL中的hashtable 同样采用的是开链法设计，这里就是hashtable中节点的样子

template <class _Val> 
struct _Hashtable_node 
{ 
    _Hashtable_node* _M_next; 
    _Val _M_val; 
};

这里可以看出，hashtable并没有利用现有的list等容器，而是自己简单的创建一个单向链表并维护。由于hashtable中的每一项元素都是一连串的数据（处理冲突而在一个链表中），所以将hashtable中的元素成为bucket，表示这个元素其实可能有“一桶子”东西，最后hashtable通过vector管理bucket，实现动态增长。

同之前一样，首先从iterator开始了解。下面是hashtable的iterator实现。

template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {
  typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
          _Hashtable;
  typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 
                              _ExtractKey, _EqualKey, _Alloc>
          iterator;
  typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 
                                    _ExtractKey, _EqualKey, _Alloc>
          const_iterator;
  typedef _Hashtable_node<_Val> _Node;
  typedef forward_iterator_tag iterator_category; 
  typedef _Val value_type;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef _Val& reference;
  typedef _Val* pointer;
  _Node* _M_cur;         //指向当前的节点
  _Hashtable* _M_ht;     //指向hashtable容器
  _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
    : _M_cur(__n), _M_ht(__tab) {}
  _Hashtable_iterator() {}
  reference operator*() const { return _M_cur->_M_val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
  iterator& operator++();
  iterator operator++(int);
  bool operator==(const iterator& __it) const
    { return _M_cur == __it._M_cur; }
  bool operator!=(const iterator& __it) const
    { return _M_cur != __it._M_cur; }
};

可以看出，这里的迭代器设计成只能向后移动，在operator ++ 中，我们可以看到迭代器的移动。

template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
class _All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
{
    const _Node* __old = _M_cur;
    _M_cur = _M_cur->_M_next;
    if (!_M_cur) {
        size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
        while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
           _M_cur = _M_ht->_M_buckets[__bucket];
     }
     return *this;
}

首先在链表（一个bucket）中寻找下一个节点，如果是链表中的最后一个节点，那么寻找下一个链表（bucket）中的节点。了解迭代器之后，开始了解容器本身。

之前可以看出，SGI STL 虽然采用的是开链法，但是在分配空间大小时，依然采用的是质数，这一点和.net framework 中的dictionary一样。大小差不多是2倍

static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul, 
  1610612741ul, 3221225473ul, 4294967291ul
};
//找到下一个大于n的质数，lower_bound是一个二分法查找。
inline unsigned long __stl_next_prime(unsigned long __n)
{
  const unsigned long* __first = __stl_prime_list;
  const unsigned long* __last = __stl_prime_list + __stl_num_primes;
  const unsigned long* pos = lower_bound(__first, __last, __n);
  return pos == __last ? *(__last - 1) : *pos;
}

hashTable 中最重要的部分是扩容。那么，我们看看，SGI STL是怎么做的

pair<iterator, bool> insert_unique(const value_type& __obj) 
{ 
  resize(_M_num_elements + 1); 
  return insert_unique_noresize(__obj); 
}

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::resize(size_type __num_elements_hint)
{
  const size_type __old_n = _M_buckets.size();
  if (__num_elements_hint > __old_n) {
    //如果需要扩容，我们找到下一个质数
    const size_type __n = _M_next_size(__num_elements_hint);
    if (__n > __old_n) {
      //搞一个新的buckets
      vector<_Node*, _All> __tmp(__n, (_Node*)(0),
                                 _M_buckets.get_allocator());
      __STL_TRY {
        for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
          //遍历之旧的buckets
          _Node* __first = _M_buckets[__bucket];
          while (__first) {
            //遍历旧的bucket，这里，我们根据新的大小找到了新的位置
            size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
            //将旧的bucket数据改为 我们正在处理的item的下一个 
            _M_buckets[__bucket] = __first->_M_next;
            //把我们现在处理的item 插入到新的buckets中。
            __first->_M_next = __tmp[__new_bucket];
            __tmp[__new_bucket] = __first;
            //将我们当前处理的item，修改为旧数据的下一个
            __first = _M_buckets[__bucket];          
          }
        }
        //都搞定了，我们将buckets更换。
        _M_buckets.swap(__tmp);
      }
#ifdef __STL_USE_EXCEPTIONS
      catch(...) {
        for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
          while (__tmp[__bucket]) {
            _Node* __next = __tmp[__bucket]->_M_next;
            _M_delete_node(__tmp[__bucket]);
            __tmp[__bucket] = __next;
          }
        }
        throw;
      }
#endif /* __STL_USE_EXCEPTIONS */
    }
  }
}

当然，这个只是insert_unique ，insert_equal 类似，这里不做描述。

除了resize，hashtable中还有一个吸引我们的就是hash func。但是，一般我们并不会指定hash func， 那么，我们看看SGI STL 是如何选择hash 函数的。

#ifndef __SGI_STL_HASH_FUN_H
#define __SGI_STL_HASH_FUN_H
#include <stddef.h>
__STL_BEGIN_NAMESPACE
template <class _Key> struct hash { };
//字符串这里看来稍微有了一些操作
inline size_t __stl_hash_string(const char* __s)
{
  unsigned long __h = 0; 
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;

  return size_t(__h);
}
//这些东西，通过c++ 模板偏特化实现，我们看到，这些东西，啥都没做，只是返回而已。所以，如果
//希望获得最佳的性能，实现仿函数。是非常必要的。
__STL_TEMPLATE_NULL struct hash<char*>
{
  size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
__STL_TEMPLATE_NULL struct hash<const char*>
{
  size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
__STL_TEMPLATE_NULL struct hash<char> {
  size_t operator()(char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned char> {
  size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<signed char> {
  size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
  size_t operator()(short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
  size_t operator()(unsigned short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
  size_t operator()(int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
  size_t operator()(unsigned int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
  size_t operator()(long __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
  size_t operator()(unsigned long __x) const { return __x; }
};

SQLite 的hash表。

SQLite是在移动设备上普遍的一个家伙， 他用到了2种HASH， 一种和上面的SGI STL 类似，在PC端，在做增加的时候，判断了数据量大小（一般10个），如果小于，则采用双向链表的方式，不是则采用hash存储。只是，在移动分支中我没有找到，PC端的确有这样的设计，也许在mobile上做了精简。这种hash，用于SQLite底层的内存管理，缓存部分，SQLite采用的是LRU的方式缓存。

另一种Hash是叫做perfect hash。这是一种在最坏情况下，依然能够达到O(1) 的能力，听上去似乎挺吓人的，但是大多数是指固定的表，当然，似乎有些能够做到动态保证，不过，不管他了，我可不是科学家。

SQLite 的前端是需要做词法语法分析的。这部分就涉及到了关键字的保存，这里SQLite 通过perfect hash来达到快速查找。具体的策略了解编译原理的都比较明白，但是，这个的确比较有意思。

构造关键字是通过一个起始位置和长度来获取的。如 “REINDEX 、 INDEXED 、 INDEX 、 DESC”；将保存成“REINDEXEDESC”。那么 REINDEX = （0， 7）。而剩下的工作可以交给一些程序，他们会帮助我们生成perfect hash。

大数据量下，hash信息指纹的应用。可以参考 google黑板报 http://www.google.com.hk/ggblog/googlechinablog/2006/08/blog-post_8115.html

最近忙公司的项目（或是毕设吧），发现很长时间没有总结了。是该换换脑子了。

“为什么没有SendThreadMessage呢？”这个问题，就来自自己平时实现的一些程序逻辑中。在一些具体的场景中，对像我这样的初学者来说，往往喜欢通过windwos的消息机制来完成UI线程和worker线程之间的同步，而不是去通过信号量或其他的去做。所以，这个问题一直困惑了自己很久。而现在，就来搞明白这个、

google一下，这个问题，在一个大牛（Raymond Chen）http://blogs.msdn.com/b/oldnewthing/archive/2008/12/23/9248851.aspx）的博客中提到了，而且也引发了很多讨论。我这里简单的”翻译”一下Raymond Chen自己的看法。

”想象中的SendThreadMessage是如何工作的呢？调用SendMessage 把消息直接分发给窗口过程？但是我们没有看到消息泵，想象中的SendThreadMessage将会把消息分发给谁呢？因为我们没有‘thread window procedure’这样的东东去处理我们的消息。

是的，我们可以自己在我们的线程中做一个消息泵，但是，想象中的SendThreadMessage，需要等待这个消息处理完毕。但是，我们怎么能够知道这个消息处理完毕了？因为我们不可能等待DispatchMessage返回，而DispatchMessage失败则是因为我们并不知道应该往哪一个窗口分发消息。window manager给线程发送一个消息，仅此而已。

你可能会认为，我们可以等待知道下一个GetMessage or PeekMessage，这样我们可以确定这个消息解决了。但是，我们却不能保证下一个消息检索函数(GetMessage PeekMessage)，是来自我们之前的消息泵。比如，我们这个线程消息，启动了一个模态窗口，是的。当我们的消息检索函数告诉我们这个消息已经处理完毕了。但是，事实上那个模态窗口还在，因为他自己又创建了一个消息泵。“

这段虽然不长，但是却另我头大无比。GetMessage ， DispatchMessage。这2个基本的函数，天天用，但是却对他们的行为知之甚少，算上第一次写HelloWorld 到现在，至少也有1年了，依然朦胧，感到十分惭愧。而这也就是这篇总结要做的。而这的确是一个庞大的工程，因为要了解这2个函数，需要把握windows的消息机制。而windwos 并没有给我们源代码参考，这里参考ReactOS的实现，虽然不是windows正统，但是，应该差不远，至少是和win2003的相似。开始步入正题。

我们首先需要了解的是，UI线程 和我们的普通的Worker线程之间的区别是什么。

msdn http://msdn.microsoft.com/en-us/library/ms644927提到：

”To avoid the overhead of creating a message queue for non–GUI threads, all threads are created initially without a message queue. The system creates a thread-specific message queue only when the thread makes its first call to one of the specific user functions; no GUI function calls result in the creation of a message queue.“

既然，系统创建每一个线程时都是普通的non–GUI thread，直到GDI， User函数调用，才为线程创建消息队列，那么我们就从这些函数调用开始。

windwos在开始时，和linux一样 图形这部分是在用户空间中的进程负责，后面为了减少进程之间的环境切换，而放入了内核中。那么在系统调用这层，我们就看到了有2种情况。一种调用是原来的”内核”的调用，而另一种是新加进来的原来在用户空间的调用，这部分被称为扩充系统调用，这部分代码被放在了可以动态安装的模块win32k.sys。与之对应，系统的调用表就有了2个，一个是只包括之前的”来自内核的系统调用“，另一个则在之前的基础上，增加了图形图像的系统调用。当我们的系统调用被发现是扩充系统调用时，也就是，原来的的表不能满足我们的要求。windwos会将会扩充系统调用表。并装载win32k.sys模块。那么，我们的普普通通的线程就开始变为GUI线程了。

激动人心的旅程就从这里开始了。

开源代码就是好，随意都能够贴出来。

NTSTATUS
NTAPI
PsConvertToGuiThread(VOID)
{
    ULONG_PTR NewStack;
    PVOID OldStack;
    PETHREAD Thread = PsGetCurrentThread();
    PEPROCESS Process = PsGetCurrentProcess();
    NTSTATUS Status;
    PAGED_CODE();

    /* Validate the previous mode */
    if (KeGetPreviousMode() == KernelMode) return STATUS_INVALID_PARAMETER;

    /* If no win32k, crashes later */
    ASSERT(PspW32ProcessCallout != NULL);

    /* Make sure win32k is here */
    if (!PspW32ProcessCallout) return STATUS_ACCESS_DENIED;

    /* Make sure it's not already win32 */
    if (Thread->Tcb.ServiceTable != KeServiceDescriptorTable)
    {
        /* We're already a win32 thread */
        return STATUS_ALREADY_WIN32;
    }

    /* Check if we don't already have a kernel-mode stack */
    if (!Thread->Tcb.LargeStack)
    {
        /* We don't create one */
        NewStack = (ULONG_PTR)MmCreateKernelStack(TRUE, 0);
        if (!NewStack)
        {
            /* Panic in user-mode */
            NtCurrentTeb()->LastErrorValue = ERROR_NOT_ENOUGH_MEMORY;
            return STATUS_NO_MEMORY;
        }

        /* We're about to switch stacks. Enter a guarded region */
        KeEnterGuardedRegion();

        /* Switch stacks */
        OldStack = KeSwitchKernelStack((PVOID)NewStack,
                                       (PVOID)(NewStack - KERNEL_STACK_SIZE));

        /* Leave the guarded region */
        KeLeaveGuardedRegion();

        /* Delete the old stack */
        MmDeleteKernelStack(OldStack, FALSE);
    }

    /* This check is bizare. Check out win32k later */
    if (!Process->Win32Process)
    {
        /* Now tell win32k about us */
        Status = PspW32ProcessCallout(Process, TRUE);
        if (!NT_SUCCESS(Status)) return Status;
    }

    /* Set the new service table */
    Thread->Tcb.ServiceTable = KeServiceDescriptorTableShadow;
    ASSERT(Thread->Tcb.Win32Thread == 0);

    /* Tell Win32k about our thread */
    Status = PspW32ThreadCallout(Thread, PsW32ThreadCalloutInitialize);
    if (!NT_SUCCESS(Status))
    {
        /* Revert our table */
        Thread->Tcb.ServiceTable = KeServiceDescriptorTable;
    }

    /* Return status */
    return Status;
}

之前没有提到的是，这里判断了一下线程system stack的大小，因为GUI线程要比普通的线程增加了更多的嵌套调用，从而需要更多的system stack。MmCreateKernelStack就是分配空间的函数。这里只是分配了64K的大小，普通的thread system stack大小为12K。当然，按照惯例，这里64K的堆栈，只是提交了其中12K的大小。并设置好guard page。超过12K则产生异常然后再分配空间。一个进程，如果有一个线程是GUI线程，那么这个进程就是GUI 进程，那么，如果不是GUI进程，我们当然先得把进程转过来。PspW32ProcessCallout是一个函数指针，指向Win32kProcessCallback。这里就是干这个了，会初始化一系列的结构体，键盘格式，GDI 句柄表等等。我们这里略过这些细节。

我们看到，系统的ServiceTable换成了大的表。而PspW32ThreadCallout指向Win32kThreadCallback，这里就完成了把普通线程转换成GUI线程的过程。对于操作系统这么复杂的东东来说，要初始化的结构体真是茫茫的多。我们这里关注一点，在Win32kThreadCallback中，我们找到了创建消息队列的入口。Win32Thread->MessageQueue = MsqCreateMessageQueue(Thread);

系统有了消息队列，但是，并不能构成真正的win32应用程序。我们开发者，还需要在自己的窗口程序中构造一个简单的Message Dump，让我们看看这个GetMessage，到底做了什么。

GetMessage，最后会调用NtUserGetMessage。

BOOL APIENTRY
NtUserGetMessage(PMSG pMsg,
                  HWND hWnd,
                  UINT MsgFilterMin,
                  UINT MsgFilterMax )
{
    MSG Msg;
    BOOL Ret;

    if ( (MsgFilterMin|MsgFilterMax) & ~WM_MAXIMUM )
    {
        EngSetLastError(ERROR_INVALID_PARAMETER);
        return FALSE;
    }

    UserEnterExclusive();

    RtlZeroMemory(&Msg, sizeof(MSG));

    Ret = co_IntGetPeekMessage(&Msg, hWnd, MsgFilterMin, MsgFilterMax, PM_REMOVE, TRUE);

    UserLeave();

    if (Ret)
    {
        _SEH2_TRY
        {
            ProbeForWrite(pMsg, sizeof(MSG), 1);
            RtlCopyMemory(pMsg, &Msg, sizeof(MSG));
        }
        _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
        {
            SetLastNtError(_SEH2_GetExceptionCode());
            Ret = FALSE;
        }
        _SEH2_END;
    }

    return Ret;
}

原谅我略过一些茫茫多的细节。

BOOL FASTCALL
co_IntGetPeekMessage( PMSG pMsg,
                      HWND hWnd,
                      UINT MsgFilterMin,
                      UINT MsgFilterMax,
                      UINT RemoveMsg,
                      BOOL bGMSG )
{
    //.......
    do
    {
        Present = co_IntPeekMessage( pMsg,
                                     Window,
                                     MsgFilterMin,
                                     MsgFilterMax,
                                     RemoveMsg,
                                     bGMSG );
        if (Present)
        {
           /* GetMessage or PostMessage must never get messages that contain pointers */
           ASSERT(FindMsgMemory(pMsg->message) == NULL);

           if (pMsg->message != WM_PAINT && pMsg->message != WM_QUIT)
           {
              pti->timeLast = pMsg->time;
              pti->ptLast   = pMsg->pt;
           }

           // The WH_GETMESSAGE hook enables an application to monitor messages about to
           // be returned by the GetMessage or PeekMessage function.

           co_HOOK_CallHooks( WH_GETMESSAGE, HC_ACTION, RemoveMsg & PM_REMOVE, (LPARAM)pMsg);

           if ( bGMSG )
           {
              Present = (WM_QUIT != pMsg->message);
              break;
           }
        }

        if ( bGMSG )
        {
           if ( !co_IntWaitMessage(Window, MsgFilterMin, MsgFilterMax) )
           {
              Present = -1;
              break;
           }
        }
        else
        {
           if (!(RemoveMsg & PM_NOYIELD))
           {
              IdlePing();
              // Yield this thread!
              UserLeave();
              ZwYieldExecution();
              UserEnterExclusive();
              // Fall through to exit.
              IdlePong();
           }
           break;
        }
    }
    while( bGMSG && !Present );

    // Been spinning, time to swap vinyl...
    if (pti->pClientInfo->cSpins >= 100)
    {
       // Clear the spin cycle to fix the mix.
       pti->pClientInfo->cSpins = 0;
       //if (!(pti->TIF_flags & TIF_SPINNING)) FIXME need to swap vinyl..
    }
    return Present;
}

IntGetPeekMessage，就是一个循环，不断的调用co_IntPeekMessage 从消息队列中取出消息，如果没有消息，那么我们就调用co_IntWaitMessage等待消息，然后往复，除非我们遇到了WM_QUIT。

co_IntPeekMessage 看来是实现的关键,而他也是PeekMessage的关键部分。同样,略过那些繁琐的细节。当然，这并不是指那些不重要，而是实在是太多了。这个函数是整个消息机制的核心部分。需要慢慢来。

说了这么多，我们还不知道消息队列是啥模样了。

typedef struct _USER_MESSAGE_QUEUE
{
  /* Reference counter, only access this variable with interlocked functions! */
  LONG References;

  /* Owner of the message queue */
  struct _ETHREAD *Thread;
  /* Queue of messages sent to the queue. */
  LIST_ENTRY SentMessagesListHead;                          //被“发送”的消息队列
  /* Queue of messages posted to the queue. */
  LIST_ENTRY PostedMessagesListHead;                        //被"Post"的消息队列
  /* Queue for hardware messages for the queue. */
  LIST_ENTRY HardwareMessagesListHead;                      //来自硬件的消息队列

  //.........

  /* messages that are currently dispatched by other threads */
  LIST_ENTRY DispatchingMessagesHead;                           //  已经发送而对方尚未处理的消息队列
  /* messages that are currently dispatched by this message queue, required for cleanup */
  LIST_ENTRY LocalDispatchingMessagesHead;                     // 本地正在分发的消息队列

  //........

} USER_MESSAGE_QUEUE, *PUSER_MESSAGE_QUEUE;

SentMessagesListHead 这个队列的东西是发送到我们这个消息队列的消息。 也就是，当其他地方调用SendMessage到我们这个消息队列时，那个消息会放在这个队列中。

PostedMessagesListHead 同理，是其他地方调用PostMessage，然后把他那个消息放在了这个队列中。

PostMessage这个函数比较容易实现，我们只需要挂在目标的PostedMessagesListHead队列中就可以了。但是SendMessage就要复杂很多了。

如果发送方和接收方是在一个线程中，那么SendMessage会直接调用本窗口的窗口过程函数来处理这个消息。

如果发送方和接收方不在一个线程中，那么发送方就必须要等待接收方的运行结果之后，才能继续执行。而这个，就形成了一个感觉上是同步的一个过程。感觉上这个似乎也不是很复杂。但也不是一个很简单的线程同步问题。

想一下这个问题，当GUI线程A向GUI线程B发送一个消息时，线程B处理A这个消息时，又需要向线程A发送一个消息。那么，这2个线程会死锁么？ 当然不会。要知道，windwos搞这一套为的就是构造一个完整的消息驱动机制，更抽象的讲，这个消息机制也算的上是一个线程通信机制。而这一套东东，最复杂的是在于，这些东东需要用户程序结合到一起，才能真正的运行起来。也就是说，我们的应用程序，必须符合windwos程序的规范，才能和windwos消息机制参与起来。而这个参与中最重要的东东就是我们之前提到的GetMessage，DispatchingMessagesHead 和 LocalDispatchingMessagesHead 则是实现这一套机制中非常重要的部分。

DispatchingMessagesHead 当我们自己SendMessage到其他地方时，我们的消息是需要等待对面的结果，那么这个需要等待的消息就被放置到这里。这里可能会对一些windwos菜鸟觉得困惑，困惑这个为什么能够形成一个队列呢？这里先把问题留下来。

让我们站在接受者的消息队列的角度来看，当有人给我们SendMessage了，我们需要在这里处理，也就是Message Dispatch，当我们搞出这个消息的返回值时，我们接受方，还必须等待对面的人把我们的这个消息的返回值拿走，这个消息才算是搞定了。这里由于可能是不同线程，甚至是不同进程之间数据传递。所以这些东西必须要考虑在内，而这些消息放在哪里呢？LocalDispatchingMessagesHead 就跳出来解决这个问题。

总的说一下，当我们SendMessage一个消息时，会挂在接收方的SentMessagesListHead队列中，并挂在发送方的DispatchingMessagesHead。

接受方先查看SentMessagesListHead 是否有消息，有的话，则从SendMessageListHead中删除掉，并添加到LocalDispatchingMessagesHead队列中，等我们把这个消息处理完毕，从LocalDispatchingMessagesHead将这个消息删除。

我们首先关注这4个队列。那个硬件的队列主要是鼠标和键盘的东东。

第一次看这个可能有点晕，不急。有一个笼统的概念之后，我们在来看细节。这部分还不是非常复杂。

/*
 * Internal version of PeekMessage() doing all the work
 */
BOOL FASTCALL
co_IntPeekMessage( PMSG Msg,
                   PWND Window,
                   UINT MsgFilterMin,
                   UINT MsgFilterMax,
                   UINT RemoveMsg,
                   BOOL bGMSG )
{
    //...
    do
    {
        //..
        /* Dispatch sent messages here. */
        while ( co_MsqDispatchOneSentMessage(ThreadQueue) )
        {
           //...
        }

        //...

        /* Now check for normal messages. */
        if ((ProcessMask & QS_POSTMESSAGE) &&
            MsqPeekMessage( ThreadQueue,
                            RemoveMessages,
                            Window,
                            MsgFilterMin,
                            MsgFilterMax,
                            ProcessMask,
                            Msg ))
        {
               return TRUE;
        }

        /* Now look for a quit message. */
        if (ThreadQueue->QuitPosted)
        {
            /* According to the PSDK, WM_QUIT messages are always returned, regardless
               of the filter specified */
            Msg->hwnd = NULL;
            Msg->message = WM_QUIT;
            Msg->wParam = ThreadQueue->QuitExitCode;
            Msg->lParam = 0;
            if (RemoveMessages)
            {
                ThreadQueue->QuitPosted = FALSE;
                ClearMsgBitsMask(ThreadQueue, QS_POSTMESSAGE);
                pti->pcti->fsWakeBits &= ~QS_ALLPOSTMESSAGE;
                pti->pcti->fsChangeBits &= ~QS_ALLPOSTMESSAGE;
            }
            return TRUE;
        }

        /* Check for hardware events. */
        if ((ProcessMask & QS_MOUSE) &&
            co_MsqPeekMouseMove( ThreadQueue,
                                 RemoveMessages,
                                 Window,
                                 MsgFilterMin,
                                 MsgFilterMax,
                                 Msg ))
        {
            return TRUE;
        }

        if ((ProcessMask & QS_INPUT) &&
            co_MsqPeekHardwareMessage( ThreadQueue,
                                       RemoveMessages,
                                       Window,
                                       MsgFilterMin,
                                       MsgFilterMax,
                                       ProcessMask,
                                       Msg))
        {
            return TRUE;
        }

        /* Check for sent messages again. */
        while ( co_MsqDispatchOneSentMessage(ThreadQueue) )
        {
           if (HIWORD(RemoveMsg) && !bGMSG) Hit = TRUE;
        }
        if (Hit) return FALSE;

        /* Check for paint messages. */
        if ((ProcessMask & QS_PAINT) &&
            pti->cPaintsReady &&
            IntGetPaintMessage( Window,
                                MsgFilterMin,
                                MsgFilterMax,
                                pti,
                                Msg,
                                RemoveMessages))
        {
            return TRUE;
        }

       /* This is correct, check for the current threads timers waiting to be
          posted to this threads message queue. If any we loop again.
        */
        if ((ProcessMask & QS_TIMER) &&
            PostTimerMessages(Window))
        {
            continue;
        }

        return FALSE;
    }
    while (TRUE);

    return TRUE;
}

co_MsqDispatchOneSentMessage 这里做的就是从SendMessageListHead 中取出一个别人SendMessage到我们这里的一个消息。 当我们把这些别人SendMessage给我们的消息处理完，就跳出那个循环，MsqPeekMessage 则去搞定别人PostMessage给我们的消息，最后再次检查一次co_MsqDispatchOneSentMessage，有没有人给我们发送了SendMessage消息，因为这之间的间隔是有可能有新的SendMessage消息。然后是IntGetPaintMessage 和PostTimerMessages这个名字就很容易理解了。而且，这里我们也看出了消息的优先级，为了提高Paint的效率，Paint是统一处理的。而且我们也看到了Timer消息，事实上我们看出他的优先级低于Paint，这样，我们就可以在timer中绘制函数，因为，我们每一次处理timer之前，我们能够保证我们的Paint消息已经被处理了。而且，我们也看出timer的确不准，在他前面有太多的东西要做了。

我们还需要了解下，我们的消息结构。是的，这个Post消息是要挂在队列中的。

typedef struct _USER_MESSAGE
{
  LIST_ENTRY ListEntry;
  MSG Msg;
  DWORD QS_Flags;
} USER_MESSAGE, *PUSER_MESSAGE;

Send的消息这里就要麻烦很多了。

typedef struct _USER_SENT_MESSAGE
{
  LIST_ENTRY ListEntry;                            //接受方的队列
  MSG Msg;
  DWORD QS_Flags;  // Original QS bits used to create this message.
  PKEVENT CompletionEvent;                    //这个用来做线程的唤醒操作
  LRESULT* Result;
  LRESULT lResult;
  struct _USER_MESSAGE_QUEUE* SenderQueue;
  struct _USER_MESSAGE_QUEUE* CallBackSenderQueue;
  SENDASYNCPROC CompletionCallback;
  ULONG_PTR CompletionCallbackContext;
  /* entry in the dispatching list of the sender's message queue */
  LIST_ENTRY DispatchingListEntry;                //发送方的DispatchingMessageList
  INT HookMessage;
  BOOL HasPackedLParam;
} USER_SENT_MESSAGE, *PUSER_SENT_MESSAGE;

这个家伙，才是真正挂在发送队列中的数据结构，我们的MSG只是其中的一个数据成员。这里，就和我们之前提到的，这个消息，是在2个队列中存在，一边在发送方的DispatchingMessageList，表示这个消息正在分发，一边在接受方的SentMessagesListHead，表示这个消息被发送过来。等待处理。

让我们一看co_MsqDispatchOneSentMessage的究竟。

BOOLEAN FASTCALL
co_MsqDispatchOneSentMessage(PUSER_MESSAGE_QUEUE MessageQueue)
{
   PUSER_SENT_MESSAGE SaveMsg, Message;
   PLIST_ENTRY Entry;
   LRESULT Result;
   PTHREADINFO pti;

   if (IsListEmpty(&MessageQueue->SentMessagesListHead))
   {
      return(FALSE);
   }

   /* remove it from the list of pending messages */
   Entry = RemoveHeadList(&MessageQueue->SentMessagesListHead);
   Message = CONTAINING_RECORD(Entry, USER_SENT_MESSAGE, ListEntry);

   pti = MessageQueue->Thread->Tcb.Win32Thread;

   SaveMsg = pti->pusmCurrent;
   pti->pusmCurrent = Message;

   // Processing a message sent to it from another thread.
   if ( ( Message->SenderQueue && MessageQueue != Message->SenderQueue) ||
        ( Message->CallBackSenderQueue && MessageQueue != Message->CallBackSenderQueue ))
   {  // most likely, but, to be sure.
      pti->pcti->CTI_flags |= CTI_INSENDMESSAGE; // Let the user know...
   }

   /* insert it to the list of messages that are currently dispatched by this
      message queue */
   InsertTailList(&MessageQueue->LocalDispatchingMessagesHead,
                  &Message->ListEntry);

   ClearMsgBitsMask(MessageQueue, Message->QS_Flags);

   if (Message->HookMessage == MSQ_ISHOOK)
   {  // Direct Hook Call processor
      Result = co_CallHook( Message->Msg.message,     // HookId
                           (INT)(INT_PTR)Message->Msg.hwnd, // Code
                            Message->Msg.wParam,
                            Message->Msg.lParam);
   }
   else if (Message->HookMessage == MSQ_ISEVENT)
   {  // Direct Event Call processor
      Result = co_EVENT_CallEvents( Message->Msg.message,
                                    Message->Msg.hwnd,
                                    Message->Msg.wParam,
                                    Message->Msg.lParam);
   }
   else
   {  /* Call the window procedure. */
      Result = co_IntSendMessage( Message->Msg.hwnd,
                                  Message->Msg.message,
                                  Message->Msg.wParam,
                                  Message->Msg.lParam);
   }

   /* remove the message from the local dispatching list, because it doesn't need
      to be cleaned up on thread termination anymore */
   RemoveEntryList(&Message->ListEntry);

   /* remove the message from the dispatching list if needed, so lock the sender's message queue */
   if (!(Message->HookMessage & MSQ_SENTNOWAIT))
   {
      if (Message->DispatchingListEntry.Flink != NULL)
      {
         /* only remove it from the dispatching list if not already removed by a timeout */
         RemoveEntryList(&Message->DispatchingListEntry);
      }
   }
   /* still keep the sender's message queue locked, so the sender can't exit the
      MsqSendMessage() function (if timed out) */

   if (Message->QS_Flags & QS_SMRESULT)
   {
      Result = Message->lResult;
   }

   /* Let the sender know the result. */
   if (Message->Result != NULL)
   {
      *Message->Result = Result;
   }

   if (Message->HasPackedLParam == TRUE)
   {
      if (Message->Msg.lParam)
         ExFreePool((PVOID)Message->Msg.lParam);
   }

   /* Notify the sender. */
   if (Message->CompletionEvent != NULL)
   {
      KeSetEvent(Message->CompletionEvent, IO_NO_INCREMENT, FALSE);
   }

   /* Call the callback if the message was sent with SendMessageCallback */
   if (Message->CompletionCallback != NULL)
   {
      co_IntCallSentMessageCallback(Message->CompletionCallback,
                                    Message->Msg.hwnd,
                                    Message->Msg.message,
                                    Message->CompletionCallbackContext,
                                    Result);
   }

   /* Only if it is not a no wait message */
   if (!(Message->HookMessage & MSQ_SENTNOWAIT))
   {
      IntDereferenceMessageQueue(Message->SenderQueue);
      IntDereferenceMessageQueue(MessageQueue);
   }

   /* free the message */
   ExFreePoolWithTag(Message, TAG_USRMSG);

   /* do not hangup on the user if this is reentering */
   if (!SaveMsg) pti->pcti->CTI_flags &= ~CTI_INSENDMESSAGE;
   pti->pusmCurrent = SaveMsg;

   return(TRUE);
}

我们首先从SentMessagesListHead把消息移动到LocalDispatchingMessagesHead，让我们略掉那些细节的标志位和hook的部分。co_IntSendMessage，则把这个消息发送出去，然后把结果给我们，然后我们把消息从接收方的LocalDispatchingMessagesHead，删掉。如果发送方还在等我们的消息，我们就把他从发送方的DispatchingMessagesHead中删掉这条消息，（因为有些消息，是有时间限制的，可能已经早就被从DispatchingMessagesHead删掉了）。然后把返回结果保存起来。当然，有些消息还是有附件的，一些资源需要释放。这里是那些消息就不在这里赘述了，而且我们也不关心这些。然后，我们通过Message->CompletionEvent来通知发送方，该醒过来了。最后，我们看到，如果这个消息有回调函数，这里并没有直接调用回调函数，而是又通过了消息机制发送了一个消息给自己（在自己的Post队列中）。有了这个，的确很容易去理解MSDN的相关意思了。有时候，真的。MS的文档为什么那么全，因为他不给我们看源代码，有源代码还需要那么多的详细文档么？而且，那些文档真的不能彻底说清楚。

转了这么远，问题又被迭代到co_IntSendMessage 上了。co_IntSendMessage 其实是co_IntSendMessageTimeout 的一个特殊调用。

LRESULT FASTCALL
co_IntSendMessageTimeout( HWND hWnd,
                          UINT Msg,
                          WPARAM wParam,
                          LPARAM lParam,
                          UINT uFlags,
                          UINT uTimeout,
                          ULONG_PTR *uResult )
{
    PWND DesktopWindow;
    HWND *Children;
    HWND *Child;

    if (HWND_BROADCAST != hWnd)
    {
        return co_IntSendMessageTimeoutSingle(hWnd, Msg, wParam, lParam, uFlags, uTimeout, uResult);
    }

    DesktopWindow = UserGetWindowObject(IntGetDesktopWindow());
    if (NULL == DesktopWindow)
    {
        EngSetLastError(ERROR_INTERNAL_ERROR);
        return 0;
    }

    /* Send message to the desktop window too! */
    co_IntSendMessageTimeoutSingle(DesktopWindow->head.h, Msg, wParam, lParam, uFlags, uTimeout, uResult);

    Children = IntWinListChildren(DesktopWindow);
    if (NULL == Children)
    {
        return 0;
    }

    for (Child = Children; NULL != *Child; Child++)
    {
        co_IntSendMessageTimeoutSingle(*Child, Msg, wParam, lParam, uFlags, uTimeout, uResult);
    }

    ExFreePool(Children);

    return (LRESULT) TRUE;
}

我们不考虑广播的情况，看简单的给单个窗口发送消息的co_IntSendMessageTimeoutSingle

static LRESULT FASTCALL
co_IntSendMessageTimeoutSingle( HWND hWnd,
                                UINT Msg,
                                WPARAM wParam,
                                LPARAM lParam,
                                UINT uFlags,
                                UINT uTimeout,
                                ULONG_PTR *uResult )
{
    NTSTATUS Status;
    PWND Window = NULL;
    PMSGMEMORY MsgMemoryEntry;
    INT lParamBufferSize;
    LPARAM lParamPacked;
    PTHREADINFO Win32Thread;
    ULONG_PTR Result = 0;
    DECLARE_RETURN(LRESULT);
    USER_REFERENCE_ENTRY Ref;

    if (!(Window = UserGetWindowObject(hWnd)))
    {
        RETURN( FALSE);
    }

    UserRefObjectCo(Window, &Ref);

    Win32Thread = PsGetCurrentThreadWin32Thread();

    IntCallWndProc( Window, hWnd, Msg, wParam, lParam);

    if ( NULL != Win32Thread &&
         Window->head.pti->MessageQueue == Win32Thread->MessageQueue)
    {
        //本线程的消息，我们直接调用用户的窗口回调函数，终于要结束了。
        Result = (ULONG_PTR)co_IntCallWindowProc( Window->lpfnWndProc,
                                                  !Window->Unicode,
                                                  hWnd,
                                                  Msg,
                                                  wParam,
                                                  lParamPacked,
                                                  lParamBufferSize );
        if(uResult)
        {
            *uResult = Result;
        }

        ObDereferenceObject(Win32Thread->pEThread);

        IntCallWndProcRet( Window, hWnd, Msg, wParam, lParam, (LRESULT *)uResult);

        if (! NT_SUCCESS(UnpackParam(lParamPacked, Msg, wParam, lParam, FALSE)))
        {
            DPRINT1("Failed to unpack message parameters\n");
            RETURN( TRUE);
        }

        RETURN( TRUE);
    }

    //不是本线程，我们只能去转发这个消息了。

    do
    {
        Status = co_MsqSendMessage( Window->head.pti->MessageQueue,
                                    hWnd,
                                    Msg,
                                    wParam,
                                    lParam,
                                    uTimeout,
                                    (uFlags & SMTO_BLOCK),
                                    MSQ_NORMAL,
                                    uResult );
    }
    while ((STATUS_TIMEOUT == Status) &&
           (uFlags & SMTO_NOTIMEOUTIFNOTHUNG) &&
           !MsqIsHung(Window->head.pti->MessageQueue));

    IntCallWndProcRet( Window, hWnd, Msg, wParam, lParam, (LRESULT *)uResult);

    if (STATUS_TIMEOUT == Status)
    {
        /*
MSDN says:
    Microsoft Windows 2000: If GetLastError returns zero, then the function
    timed out.
    XP+ : If the function fails or times out, the return value is zero.
    To get extended error information, call GetLastError. If GetLastError
    returns ERROR_TIMEOUT, then the function timed out.
*/
        EngSetLastError(ERROR_TIMEOUT);
        RETURN( FALSE);
    }
    else if (! NT_SUCCESS(Status))
    {
        SetLastNtError(Status);
        RETURN( FALSE);
    }

    RETURN( TRUE);

CLEANUP:
    if (Window) UserDerefObjectCo(Window);
    END_CLEANUP;
}

这里我们终于看到结果了。当然，这里又给我们带出一个问题”系统是如何调用我们写的函数呢？是在什么时候调用？是通过什么方式？”这同样是，特别是第一次写windwos程序的菜鸟们遇到的第一个问题。这个问题说清楚还是挺麻烦的。这部分这里先留下。

让我们把大脑堆栈弹到开始。

还是这个问题”系统是如何调用我们写的函数呢？是在什么时候调用？是通过什么方式？”现在我们还不能回答所有问题，但是却可以回答”系统什么时候调用我们的窗口过程函数”。

我们调用系统的代码，或是说是调用系统服务，API等什么的，是通过中断机制完成的。并通过查找系统调用表来找到相对应的系统函数。也就是，我们可以随时随地利用中断机制去执行系统代码（当然是在限制下）。那么，系统可以随时随地的去执行我们用户空间的代码么？有点难，我们不去思考那么复杂的，因为还有一些其他的机制做这些类似的工作。我们只是去思考其中的一种，如何调用我们的窗口过程函数。

很容易想到，随时随地执行用户的代码很难。因为没有硬件的支持去让我们完成类似中断的机制。那系统只能在一些特定的地方才能有机会去执行我们的窗口过程函数。显然，GetMessage就是这个执行用户窗口过程函数的地方。而当用户程序在处理一个消息时，系统是没有办法有任何作为的。只能等待用户下一次调用GetMessage类似的函数，才能重新获得代码的控制。我们在co_IntPeekMessage中看出些端倪。如果消息队列中，没有任何消息，那么GetMessage并不会退出，也就是不将执行权给用户的代码，而是进入等待状态。如果这时来的一些SendMessage的消息，线程会唤醒并执行这些代码。除非有一个Post或是其他消息，才会从GetMessage返回给用户空间。

换句话就是，如果我们的Sendmessage是发给不同的线程，只能在GetMessage这个函数内部执行。如果那个接收方的线程阻塞了，那么我们的SendMessage就不会返回，因为他并没有执行GetMessage。

在去思考另一个问题，当我们Sendmessage到另一个线程，而另一个线程并没有执行我们的GetMessage，在执行他的代码，而我们的线程看起来显然是被挂起等待了，是么？并不是，因为他还是可以接受其他线程发送过来的消息。这显然是处理在处理我们之前讨论过的一种情况。的确很有意思。因为从windwos的角度看，需要实现这种强壮的消息机制。那么这是一个什么过程呢？清楚一点。其实就是需要一种机制，也就是在等待对方线程处理完毕之前，可以处理别人发给我们的消息。哈哈。WaitForMultipleObjects等待2个event一个是要等待处理完毕的消息，一个是要等待sendmessage过来的新消息。当醒来时判断是什么让我们清醒过来，如果对面的线程不给力，我们只能继续循环等待。而这个也就是sendmessage的过程。

NTSTATUS FASTCALL
co_MsqSendMessage(PUSER_MESSAGE_QUEUE MessageQueue,
                  HWND Wnd, UINT Msg, WPARAM wParam, LPARAM lParam,
                  UINT uTimeout, BOOL Block, INT HookMessage,
                  ULONG_PTR *uResult)
{
   PTHREADINFO pti;
   PUSER_SENT_MESSAGE Message;
   KEVENT CompletionEvent;
   NTSTATUS WaitStatus;
   PUSER_MESSAGE_QUEUE ThreadQueue;
   LARGE_INTEGER Timeout;
   PLIST_ENTRY Entry;
   LRESULT Result = 0;   //// Result could be trashed. ////

   if(!(Message = ExAllocatePoolWithTag(PagedPool, sizeof(USER_SENT_MESSAGE), TAG_USRMSG)))
   {
      DPRINT1("MsqSendMessage(): Not enough memory to allocate a message");
      return STATUS_INSUFFICIENT_RESOURCES;
   }

   KeInitializeEvent(&CompletionEvent, NotificationEvent, FALSE);

   pti = PsGetCurrentThreadWin32Thread();
   ThreadQueue = pti->MessageQueue;
   ASSERT(ThreadQueue != MessageQueue);

   Timeout.QuadPart = (LONGLONG) uTimeout * (LONGLONG) -10000;

   /* FIXME - increase reference counter of sender's message queue here */

   Message->Msg.hwnd = Wnd;
   Message->Msg.message = Msg;
   Message->Msg.wParam = wParam;
   Message->Msg.lParam = lParam;
   Message->CompletionEvent = &CompletionEvent;
   Message->Result = &Result;
   Message->lResult = 0;
   Message->QS_Flags = 0;
   Message->SenderQueue = ThreadQueue;
   Message->CallBackSenderQueue = NULL;
   IntReferenceMessageQueue(ThreadQueue);
   Message->CompletionCallback = NULL;
   Message->CompletionCallbackContext = 0;
   Message->HookMessage = HookMessage;
   Message->HasPackedLParam = FALSE;

   IntReferenceMessageQueue(MessageQueue);

   /* add it to the list of pending messages */
   InsertTailList(&ThreadQueue->DispatchingMessagesHead, &Message->DispatchingListEntry);

   /* queue it in the destination's message queue */
   InsertTailList(&MessageQueue->SentMessagesListHead, &Message->ListEntry);

   Message->QS_Flags = QS_SENDMESSAGE;
   MsqWakeQueue(MessageQueue, QS_SENDMESSAGE, TRUE);

   /* we can't access the Message anymore since it could have already been deleted! */

   if(Block)
   {
      //我们绝大部分都是不阻塞的。
   }
   else
   {
      PVOID WaitObjects[2];

      WaitObjects[0] = &CompletionEvent;
      WaitObjects[1] = ThreadQueue->NewMessages;
      do
      {
         UserLeaveCo();

         WaitStatus = KeWaitForMultipleObjects(2, WaitObjects, WaitAny, UserRequest,
                                               UserMode, FALSE, (uTimeout ? &Timeout : NULL), NULL);

         UserEnterCo();

         if(WaitStatus == STATUS_TIMEOUT)
         {
            //...
         }
         while (co_MsqDispatchOneSentMessage(ThreadQueue))
            ;
      }
      while (NT_SUCCESS(WaitStatus) && STATUS_WAIT_0 != WaitStatus);
   }

   if(WaitStatus != STATUS_TIMEOUT)
      *uResult = (STATUS_WAIT_0 == WaitStatus ? Result : -1);

   return WaitStatus;
}

GetMessage返回了，一般是跑2个函数。

TranslateMessage(&msg); DispatchMessage(&msg);

这里我们不讨论TranslateMessage，这个主要是辅助一些硬件消息相关。

DispatchMessage的事情，就是做这个调用相对用的窗口过程部分。这部分主要是从系统调用我们的代码，目前对这个还没有什么兴趣。

类似的还有模态窗口，产生模态窗口的窗口，会阻塞一些消息，但是却不是阻塞所有的消息，别的线程依然可以给发SendMessage。为什么呢？他们之间会有联系么？

中断和异常处理是OS中非常重要的组成部分，当然windows也不例外，他们是我们理解OS一些概念、机制的基础。

中断和异常简单的来说，就是在程序正常执行流程中，突发一个事件，导致程序的执行流程转向另外的执行流程中。而我们绝大多数编写的程序都是顺序执行的，我们的确体会不到这样的机制能够给我们带来多少好处。但是这个在OS的设计中，确实深入到各个方面，以至于没有中断异常处理，现代OS根本无法构建。为了简单理解，我们可以看看这个例子。

比如我们准备带我们的宠物狗狗出去散步，但是由于狗狗非常淘气，经常单独行动（这里，我们是无法预知狗狗会在什么时候跑掉的），在没有任何其他道具的帮助下，我们只能每隔一段时间去看看狗狗是否跟着我们。那么用code来模仿这个行为，那么就是这个样子。

while(living) //人的行为简单说其实就是不断的重复重复...
{
    //do something
    ...
    if(!VerifyDog())//看看狗狗还跟的没有
    {
        //狗丢了....    
    }
    ...    
}

如果我们这个while循环中，没有其他事情，仅仅是和狗狗在一起，那么狗狗不会丢，但是如果我们突然遇到一个美女，驻足观赏了一会之后…狗狗不见了。

是的，我们通过轮询这种方式，不可能保证狗狗一定会在我们身边。那么如何才能保证狗狗一定在我们身边呢？无论我们走到哪里都会紧紧跟着呢？生活常识告诉我们，只需要给狗狗戴上链子，这样狗狗就会“听话”的跟在我们左右。那么我们就可以通过这样的code来展示我们的行为。

while(living)
{
    leash(FuncProc); 
    while(bOutSide)
    {
       //doSomeThing 
    }
    UnLeash();    
}

FuncProc()
{
    狗狗想跑,抓紧链子。：）
}

好了，在我们带狗狗出去玩之前，我们给狗狗栓了链子，那么我们在外出的时候，就可以随行所欲的“看美女了”。一旦狗狗有不轨行为，我们只是需要下意识的抓紧便能保证狗狗不会跑丢。而这，要比隔一段时间查看狗狗在不在要简单多了，我们可以完全从这个事情上解脱出来。做更重要的事情。而这一切，其实就是默默跑了一个异常处理的过程。

我们通过leash(FuncProc); 注册了一个callback函数 我们可以做我们想做的事情，而不在我们的while循环中体现任何有关狗狗的信息。 当狗狗有不轨行为时，链子第一时间通知我们狗狗的行为，然后我们能够在第一时间制止狗狗。 然后我们继续while中的事情。 当然，回家了要把狗狗放出来（大部分的狗狗都不喜欢狗链子….）。 从某种角度上来看，OS相当于人，而我们写的一些应用层的程序则相当于宠物狗狗。而异常处理，就是这条链子。对操作系统来说，他希望找到一条能够应对所有狗狗的超级链子。而在这么多狗狗中，总有那些不听话的，希望能够摆脱这条链子的狗狗。而这条链子也在这2端的发展下，变得越来越强壮。

这篇文章的角度就是站在OS的角度，希望找到这条能够应对各种狗狗（主要是不听话的狗狗）的链子。也就是初步学习windows 的SEH的整体设计和思路（这个帽子的确很大）。下一篇则站在狗狗的角度来学习我们如何能够摆脱这条链子（这个帽子也挺大的），也就是SEH的相关安全机制。当然这篇是理解后面的基础。

当然，OS本身的实现和人狗链子的关系也是微妙的。现代操作系统的整个设计是分层的。有些时候是人是狗已经不再重要了。就像真实世界的我们，我们无法从那些枷锁中挣脱，真的。我们有时候真不知道我们是人？是狗？

闲话扯得太多了。为了更清楚的了解异常，我们需要进一步了解我们的计算机。类似的这种程序控制流的变化，还有中断(interrupt)，陷阱(trap)，错误(fault)，终止（abort）而中断，我们通常又分为软中断，和硬中断（这个又通常省略硬字）。是的，我相信对于绝大多数的和我一个水平的菜鸟来说，这些概念都是可以令人抓狂的。而造成这样的原因主要是在于计算机的发展是在是太快速了，所以，有些概念在这个过程中得到了扩展，而这些概念又和计算机体系结构密切相关，所以我们经常看到甚至是一些权威书籍之间有概念的冲突，是的。这个当然不是人家的错误，只是处在了不同的时空，而这也就是语言的悲剧。他永远不可能给我们准确的答案，除非数学。所以这里我们需要先搞清楚这些概念。把那些恼人的语言上的细枝末节过滤掉之后，整个东东也不复杂了。当然整个学习都在我们最“熟悉”的x86下，其他平台也不不难掌握了。

为了减少中英文的差异，在一些概念描述上，这里就不再一次引入另一门语言，虽然他是伟大的语言。为了能够较为清晰的了解他们之间的区别。我们不得不扯一些硬件相关的知识，事实上，也许这些“旁敲侧击”让你回想到了学校的那些认为不重要的课程《机组》《模电》《计算机体系结构》《微机原理接口》等。

在8086下，原谅我再次重复，有2种这样的机制。interrupt、exception。interrupt分为可屏蔽中断和不可屏蔽中断。exception分为 fault、trap、abort。概念有点多，慢慢来。

经过上一篇的胡扯，我们知道了CPU眼中，把这些硬件当成逻辑存储器，最后和存储器构成一个地址空间。但是有些笼统，这里稍微再了解一点。和CPU通过总线相连的芯片除了各种存储器外，还有3种芯片

• 各种接口卡（显卡，网卡）上的接口芯片，它们控制接口卡
• 主板上的接口芯片，CPU通过它们对一些外设访问
• 其他芯片，存储相关的系统信息或对输入输出处理

而这些芯片都有一组可以由CPU读写的寄存器。这些寄存器有2点相同。

• 和CPU总线相连。
• CPU对它们进行读写是通过控制些向他们所在的芯片发出端口读写命令

所以，在CPU看来，这些外部的寄存器相当于端口，并对他们一起编址，从而又搞了一个端口地址空间，或是叫做IO端口空间。这里再扯的远一点，事实上，在x86下，我们现在知道有2个地址空间，一个是存储器的地址空间还有一个是IO地址空间，为什么不把IO地址空间也映射到存储器地址空间中呢？这样我们就可以再弄一些逻辑存储器了。是的这样设计的确简单，但是却浪费了一些CPU的地址空间，所以当时intel考虑到为了不浪费而又搞了一个IO地址空间，所以我们访问这些端口的时候，也就必须通过另外的指令来做。我们把这种IO编址称为独立编址。x86一共有64K个8bit的IO端口。事实上还有另一种思路和我们之前的想法一致，将这些IO的空间跑到了存储器地址空间，而这个又叫做统一编址。也就是说，这些IO寄存器与存储器单元一样看待。这样的设计在ARM中则比较常见。呵呵，有点乱，让我们看个例子。

那就用我们最熟悉的键盘来说。当我们在键盘上操作时，CPU是如何知道的呢？

键盘中有专门的芯片用于监视键盘上每一个键的状态，当我们按下一个键时，接通电路，这个芯片就会产生一个成为扫描码的东东，来表示键的位置，当键弹起的时候，同样产生一个扫描码。扫描码就保存在了键盘接口芯片的寄存器中（CPU来看这就是一个端口）。那么当键盘的输入到到端口时，我们这篇文章的主角终于来了。芯片向CPU发出中断信息。到这里，键盘的事情OK了。

那么芯片是如何给CPU发送中断呢？我们可以通过线将CPU和芯片连接起来，但是这样会遇到一个无法回避的问题，可以和CPU连接的线是有限的，但是CPU外部的这些设备确是非常多的，所以必须管理这些设备，让其中一些设备共享一条线。而这也就是中断控制器的作用之一，所以，真实的情况是类似如下的。

inter x86通过2片中断控制器8259A来响应外部中断源（就是指产生中断的设备，比如键盘）。和中断控制器相连的每条线被称为中断线。我们看出如果想发送中断给CPU，那么必须得获得这条线的控制权。那么我们申请中断线的这个动作，叫做IRQ（Interrupt ReQuirement）。当然“申请中断线”这也有一个更加专业的叫法申请IRQ或是申请中断号。

而这个8259A做的事情就是

• 监视中断线，检查产生的IRQ信号

• 如果中断线上产生了一个IRQ信号

  把IRQ信号转换成对应的中断向量 这个向量存放在中断控制器的一个IO端口，CPU从而可以通过数据总线访问向量 这个信号则发送到CPU的INTR引脚，也即是触发一个中断 等待CPU确认中断之后，写入PIC(可编程中断控制器)的IO端口，并清INTR

但是事实上还没有完，我们知道CPU在一个时刻只能处理一个事情。我们有那么多的外围设备，当他们都要CPU时间时，这里就有一个先后问题了。也就是需要对这些中断分级别。而且在有些特殊的中断下，是不可以被其他中断打断的。呵呵，这里就引入了可屏蔽中断和不可屏蔽中断。那么我们就可以有选择的处理一些中断，而放弃另一些中断在一些极端情况下。而且有些中断处理过程中是不可以再处理中断的。可屏蔽中断IRQ信号通常是通过CPU的INTR引脚发给CPU的。而不可屏蔽中断信号通常是通过NMI引脚发给CPU。呵呵，这就是可屏蔽中断和不可屏蔽中断区别之一。

那么我们再来搞定异常。

为了能够稍微再了解一点，我们需要知道一些CPU内部是如何执行一条指令的。原谅我这里就不赘述了。只是搞一个例子。

当CPU执行汇编指令IDIV。首先会检查源操作数（除数）是否为0，如果为0，则CPU在执行这条指令中，就会产生一个除零异常（在CPU眼里，汇编也成高级语言了）。通过中断的例子，我们看出，中断是CPU外部告诉CPU的执行流程需要转变。那么异常和中断最大的不同就是异常是CPU自己本身执行时发现的。中断的来源通常是外部设备，异常的来源则有3种。

• 程序错误，当CPU在执行程序指令时遇到操作数错误或是指令非法。前者的例子就是除零，后者的例子可以是在用户模式下执行特权指令
• 某些特殊指令。这些指令的本身就是产生异常。
• intel在P6引入了机器检查异常（Machine Check Exception）。当CPU执行指令期间检测到CPU内部或是外部硬件错误。

可见，对CPU来说，中断是异步的，因为CPU完全是被动的指望外部硬件给他一个信号。而异常，则是CPU自己发起，从CPU来看则是同步的。

我们之前已经了解了CPU是如何获知异常，中断。那么CPU接下来的动作又是什么呢？首先需要区分出这些不同的异常，中断。具体则是需要区分出产生中断的来源，8086使用被称为中断类型码的数据来表示中断源。中断类型码为一个字节数据。8086最多可以表示256种中断源。那么接受到各种中断或是异常时，接下来需要做不同处理，那么分别处理中断或是异常的程序入口，叫做中断向量（这里可没有异常向量一回事，这里被统一看待）。而这些中断向量组成一张线性表被称为中断向量表。由于是线性表，我们可以很容易的构造一个类型码到中断向量的映射。

这里还需要强调一点。之前我们提到的异常的分类，那么这些异常的区别是什么呢？既然是控制流的转变，那么就有如何恢复和如何报告控制流转变这2种情况需要我们考虑，而事实上，fault abort trap 就是按照这样划分的。

• 错误类（fault）异常是在产生这个异常指令的指令之前发起。fault通常在执行指令或是执行指令之中被CPU检测到。如果检测到，那么异常将机器的状态恢复到这条指令开始的地方，这样。指令就可以继续执行。可见错误类异常可以无缝继续执行，但是如果没有解决，则会陷入死循环。
• 陷阱（trap）异常是在产生这个异常指令完成之后，立即产生。那么异常之后的恢复就是引起这条指令的下一个指令（这个是逻辑上的，可不是空间上的）。 可见trap也是可以无缝继续执行。
• 终止（abort）异常用来报告严重的错误，而这种错误已经严重到不可恢复的地步，也可以说，我们已经不知道该如何恢复了。整个都乱了。比如一些硬件错误。

当然到了80386之后，由于保护模式的引入，这部分又引入了各种门，中断们，陷阱门等等，恢复的过程也分了内核态和用户态。而这些个过程，绝大多数书籍都有相关详细的说明，这里不做赘述。有兴趣的同学可以自己翻阅。这里引入这些概念是为了对硬件处理中断有一个笼统的概念，这样会对我们理解OS是如何模拟这个异常过程提供一些帮助。

这里还需要再强调一点，我们可以通过一些指令来屏蔽 可屏蔽中断，事实上，大多数的外接设备都是可屏蔽中断。但是我们的异常确是不可以被屏蔽的。有了之前的基础，我们可以从硬件本身的搭建思考这个原因，也可以从整体设计去思考这样设计的原因。这里算是留个问题吧。我已经觉得我是在是太罗嗦了。

当然这些划分也不是非常精确，有一些错误类异常也是不能恢复执行的。哎，没办法，谁让这计算机是人造的呢。事实上，计算机的世界中充斥着“差不多”，“懒惰”这类思想，如果非要钻严谨的牛角尖只会增加自己的痛苦。因为我们不是在搞数学，有些东西可能背负着我们现在的视野所不能企及的历史问题。所以还是那句话，存在即是道理。我们没有资格对他们评头论足，在我们彻底搞出一个自认为更加合理的东西之前。当然这也是人造科学最让一些喜欢追求完美的家伙们郁闷的地方。呵呵，如果真的有可能，真的应该去拥抱数学。当然人造科学也有好处，是的。他和我们大多数的思维一致，甚至是我们现实经验的抽象，看看计算机的那些最基本的核心概念，stack queue。

差点忘了，还有一个软中断的概念，这里通常指的是INT n这样的指令。如果站在CPU的角度，这个明显是异常，因为这个控制流的转变是CPU内部检测到的。

让我们从茫茫的硬件跳出来。别忘了我们是要了解OS的异常处理。我们可对CPU的世界没有兴趣。是的。正是因为这些硬件太过于底层，而且不同的硬件结构都有不同的地方。那么操作系统如何来保证自己可以在多个这样的硬件平台上执行呢？一个最常见，最通俗的就是OS自己再抽象一个异常，中断。自己定义一个。是的，再没有比自己推倒旧体制，重建新秩序让人更兴奋的了。这样上层的应用就不需要考虑这些细枝末节了。事实上，OS是将这些异常，中断打包在一起管理的。因为他们本质上都是程序执行流程的转换。我们只能看到这是一种“跳转，恢复”而已。所以，现在我们可以忽略掉上面所讲的所有东西。（这里可能会有一种误解，所以我这里叫胡言乱语，要想完全真实的了解这些过程，intel手册，当然如果想要吃下这东西，《机组》《体系结构》….）。

庄子也讲，计人之所知，不若其所不知；其生之时，不若未生之时；以其至小求穷其至大之域，是故迷乱而不能自得也。这些东西还是因人而异。我这里可没有给大家传递必须要学那些硬件知识，或是鼓励大家怎么怎么做。事实上我也没有这个能力，退一步，即使我有这个能力，也没有这个资格。用自己的特例来推广到大家这本身就是一个本末倒置的问题。其实，哎，再加一句废话。存在即是理由，技术本身没有错，错的只是人的角度而已。而这也就是人造科学的悲剧，它不可能让所有人都满意，相反那些只有神才能理解的东西–数学，不以人类意志为转移。

让我们扯开那些鸡毛蒜皮的东西，静下心来。站在OS的角度来观察异常。那就拿我们最“熟悉”的windows。好吧。windows自己搞了一个异常处理机制。而这里面最熟悉的就是SEH了。当然这不是windows中唯一的异常处理机制。等我们了解SEH之后，再了解他。因为他并不是NT设计之初就存在的。这里可能又要绕绕了。MS真正的操作系统是NT。而95 98 只是dos的一层皮，并不真正算我们想象中的操作系统。

当然NT也搞了自己的一套中断的概念，只是这里。我觉得我们应该暂时放下。在OS，IO处理那部分在来讲述。我觉得这次的硬件有些多了。涉及的太多，反而不能讲述清楚了。

既然我们要弄一个抽象的中间值，那么我们显然只能从异常被CPU识别，然后经过各种机制之后，扔给我们来看的就是NT给我们定义的异常，也是给他自己定义的异常。

typedef struct _EXCEPTION_RECORD { 
    DWORD ExceptionCode; 
    DWORD ExceptionFlags; 
    struct _EXCEPTION_RECORD *ExceptionRecord; 
    PVOID ExceptionAddress; 
    DWORD NumberParameters; 
    DWORD ExceptionInformation[EXCEPTION_MAXIMUM_PARAMETERS]; 
}  EXCEPTION_RECORD;

EXCEPTION_RECORD 定义异常，更多的可以参考msdn，http://msdn.microsoft.com/en-us/library/aa363082(VS.85).aspx这里只是简单提几点。

ExceptionCode 是NT分配给异常的编码，用来表示是一个什么样的异常。比如我们最熟悉的 0xC0000005 STATUS_ACCESS_VIOLATION。

ExceptionAddress 则表示异常产生的地方。（这里其实是不准确的，如果我们从硬件的角度去看，因为有些地方windows替我们做了一些额外的事情。后面会提到一个例子。）

既然要模拟实现这种程序控制流的转换，那么我们需要提供系统一个函数执行的入口，说白了就是一个函数指针。那么就是下面的这个样子。

EXCEPTION_DISPOSITION 
__cdecl _except_handler( 
     struct _EXCEPTION_RECORD *ExceptionRecord, 
     void * EstablisherFrame, 
     struct _CONTEXT *ContextRecord, 
     void * DispatcherContext 
     );

让我们先略过这些参数。思考一些问题。我们应该如何注册我们的函数入口，何时解除我们的回调函数。如果站在NT的角度，这些函数入口又该记录在哪里？

最直观的想法就是模仿硬件那种线性设计，搞一张表，来存储这些函数入口。但是我们这种直接想到的，往往都不是真实的设计。我这里只能猜想，由于这些设计都是20年前的东西，过多的访问外部的表，可能会冲击缓存性能。

那么我们怎么做才能在少影响缓存性能的情况下，还能触发程序执行流程转换？而且我们并不知道哪里会出现程序流程的转换。而且由于我们需要模拟这个流程，也就是要支持底层中的中断来让我们普通程序捕获的同时，我们还想要扩展，自定义一些异常来抛出，使得程序流程转换。这个的确是一个复杂的问题。事实上，在我们的程序中已经给我们提供了一个实现这个机制的空间。他就是计算机中里程碑的东东，堆栈。

堆栈是什么时候出现的，这个已经不清楚了。但是可以确定的是现在已经几乎没有能够脱离堆栈而运行的程序。堆栈给我们提供了非常出色的环境。

记录子程序调用轨迹，使得嵌套子程序调用成为可能 通过堆栈传递子程序调用参数，从而简化程序设计。因为寄存器的数目很可能是不够用的。 基于堆栈的程序局部变量的概念得以出现，使得模块化程序设计和结构化程序设计成为可能，也最后导致了进程，线程。 程序执行的轨迹和局部变量结合一起成为“脉络”即上下文。这给我们恢复程序执行，跳转程序执行提供了保障，甚至后面的调度。 我猜想，正是因为SEH的设计和堆栈密不可分，所以才叫“结构化异常处理”吧。

回想一开始的那个带狗狗出去玩的例子，栓链子和解开链子，构成了一段受保护的空间。事实上，编译器在给我们构造可以支持SEH的环境时，也是这样的。进入try block之前，加保护，在当前程序的堆栈空间中构造一些结构，也就是我们的回调函数入口等其他一些必要的结构。而当我们离开try block 之后，则就像释放普通的临时变量一样释放掉这些结构体。而且堆栈还有其他的好处，由于我们可以根据堆栈去构造类似printf的不定参数的功能，所以，编译器在支持NT的SEH机制时，可以加入其他一些结构，这样比较方便的扩展和优化这些基本的机制，从而提高效率。减少支持异常的开销。而且事实上，对于异常的开销，如果没有触发异常，现代的编译器已经几乎做到零开销，只是当真正的触发异常时，效率会大幅下降。当然。异常提供了非常强大的转换程序流程的能力，而这也是那些病毒，木马最喜欢的事情。更不说这些相关的SEH结构体就构造在程序的堆栈中，这种没有任何保护的地方。所以需要非常多的安全机制协同保护。而这些问题，大概直到vista后win7才基本上做到了完美，或是那些牛人还没有找到漏洞。

所以说，我们自定义的异常，一般都是程序执行流程中的极端情况，万万不能像理解硬件中断那种思想去理解，也就是异常是不能用来控制程序中大多数流程转变。只能用于极端情况，作为最后的手段。当然，这个可能并不是20年前的那些牛人都能想到的。相关的有关SEH编译器级实现可以参考

Matt Pietrek的文章

http://www.microsoft.com/msj/0197/exception/exception.aspx，

还有我自己写的2篇。

http://www.cnblogs.com/studentdeng/archive/2010/12/15/1907232.html

http://www.cnblogs.com/studentdeng/archive/2010/12/21/1912991.html

原谅我把我的文章和Matt Pietrek的放到一起。当然，这些东西都是最最基础的。

但是这篇可不是去学习具体的实现机制，要明白这个，还是需要一定的汇编基础和多一些的耐心，其实，怎么说呢，对于c的反汇编，主要还是靠耐心吧，没有太多的技术（纯个人感觉，我觉得c++的需要更多些技术）。而且如果再稍微了解一点SEH的安全机制，就会发现，我们似乎又回到了最开始的想法。构造一个表来保存这些回调函数的一些信息。呵呵，事物的发展似乎又回到了原点，但是我们的认识却不在一个层面上了。螺旋发展，也增加了我们学习这些古老东东的难度。真的，有时候真不知道为什么自己会处在这个时代。20年前的操作系统还有人敢说能够比较全面地了解。对于现在的千万级，有的linux甚至是亿级代码量来说。呼呼。穷极一生也仅仅皮毛而已，不过对于计算机这种新科学来说，还能搞个皮毛。而物理，数学那就是还没了解就over了。。。。。。

对比之前的硬件结构，我们已经了解了我们自定义的“异常信号”，“异常向量”。那么我们又是如何根据“异常信号”找到这些“异常向量”呢？那么我们就必须要了解NT的异常触发的模型了。当异常跳出来时，NT的顺序是这样的。（准确说异常在用户态下，关于内核态的我们不管他）

• 调试器 first chance
• 堆栈上的那些回调函数
• 调试器 second chance
• 环境子系统 怎么说呢，我觉得这篇真的好长，环境子系统还是放在OS进程线程那部分了解吧。现在可以把它想象成NT进程的妈吧。反正只要是要创建一个进程都要告她一下。当异常最后也没找到属于他的回调函数，那么就给他妈管教了。当然，NT之所以这样设计异常，就是要构建一个非常强壮的设计。能够将问题层层分类解决。是的，当问题复杂到一定程度之后，虽然我们通常的理解是一步到位会快些，但是事实往往分层更容易开发，维护，管理和甚至是优化。如果不分层，那么想象，搞这么多信息，还需要能支持用户扩展，而且，这个异常处理充斥整个系统本身设计。MS如何能够协同那么多人开发，即使都是天才？

整个NT处理异常就是这样的，异常来了，OS先找debugger，debugger不管，那就在程序堆栈上找人，也不管，唉，debugger你还不管？ 好吧，subsystem你搞定吧。对于这种谁都不管的异常，正式一点的叫法是未处理异常，这个也其实是比较复杂的，因为2K， XP，vista的策略都不同。策略本身不复杂但为什么不同？ 有机会的话，需要再深入一点学习一点。

这里面对大多数同学，如果不了解汇编的话，可能无法理解这个调试器为什么要跑2次？要知道我们现在可是在和效率赛跑，而且为什么调试器首先要捕获异常？而不是我们本身的程序？

我们想一个问题。在我们使用debugger调试程序的时候，我们的程序凭什么能够加入断点，然后停下来？CPU执行可是老老实实的按照一条条的指令跑的，没有那些花花肠子。当我们单步调试的时候，为什么程序执行一条指令（我这里指调试汇编代码，调试c，c++这些还需要稍微麻烦一点）就要停下来呢？当我们有了中断的概念就不难理解这个问题了。是的。就是发生了中断。导致CPU暂停了当前被调试进程，而把控制流转向到了debugger。那么怎么暂停？为什么能够暂停？这个还是交给OS的调度和同步那里再学习吧。

事实上，这个断点（我说的这种）就是指令INT 3。他可以说是我们非常熟悉，但又陌生的。不知道大家在一开始用c编程的时候，至少是我自己，在辛苦了半天之后，一运行发现屏幕上跑出一大堆烫烫烫烫。事实上，他就是INT 3。

INT 3的机器码是1100 1100b（0xCC）。一个字节长。编译器在debug下会给我们创建额外的栈空间并填上INT 3，至于为什么这样，我这里就不啰嗦了。这种纯菜鸟错误，通常是没把指针玩明白。有点远，呵呵，为什么扯这么远，是因为在有了之前的硬件知识，这里很可能产生疑问。看这个指令的样子，我们发现他是个软中断，或称为trap。那么根据之前所讲的，这里的异常地址应该是这条指令的下一条。但是我们这里看到的却是我们打断点的这条指令。那么要搞清楚这个，又要稍微绕绕下。当我们加入一个断点的时候，vc会自动记录下我们这个断点的位置信息。当调试的时候，vc会把这些断点位置处的指令换成我们的INT 3。也就是替换掉一个字节。当然，替换之前要保存原来的。这个过程叫做落实断点（resolve break point）。那么当CPU执行到INT 3指令时。是的。这时我们就明白了，为什么要先让调试器捕获异常了。这些东西要是先给了我们做，那么调试器就没法子实现功能了。然后就是一系列的硬件，OS的事情。vc把之前我们的代码再恢复过来。所以这也就是RtlRaiseException产生的软件异常并不会先扔给debugger first chance。因为我们自己搞得东西是不可能和debugger有任何关系的。

我们这里需要特别关注下NT干的事。

对于NT来说，INT 3 会导致CPU执行KiTrap03程序。（为什么执行这个，我们在IO那里再了解）。在WRK中，我们可以看到这部分的源代码。这里不得不提MS，不知道哪个脑子别了改锥的人想出了一个这么限定，代码不能超过50行。无语。

mov     esi, ecx                ; ExceptionInfo 2
mov     edi, edx                ; ExceptionInfo 3
mov     edx, eax                ; ExceptionInfo 1

mov     ebx, [ebp]+TsEip
dec     ebx                     ; (ebx)-> int3 instruction
mov     ecx, 3
mov     eax, STATUS_BREAKPOINT
call    CommonDispatchException ; Never return

不管怎么说，人家总是做出贡献了。我们看到了dec ebx。是的。在处理异常的时候，nt这里修正了一下，而那个1，就是INT 3这条指令的长度。现在我们就明白为什么我们能正确看到我们的代码了。也验证了trap的流程。

绕了很远，把思路拉回来。

让我们再思考一个问题，程序流程突然转变了，甚至可能永远回不来了，而且我们现在的代码是看不出这个状态。也就是我们随时都可能被别人抢了。哎，可惜啊，咱们处在最底层。人为刀俎，我为鱼肉。但是NT还是比较有人性的。而且这也是很有必要的。在程序流程突然转变了。在保护的这段代码中，可能有一些关键的操作没有做。比如内存释放，一些同步的锁等。但是由于某种未知原因，我们只能放弃这部分操作。那么我们的这部分被动代码什么时候执行呢？而且，由于这些保护的代码很可能由于函数调用，在形式上或是非形式上，都可以形成一个嵌套的关系。这些释放的顺序，从那里开始释放，释放到哪里？这都是NT需要给我们规划好的。

不要被我复杂的言论迷惑，实际上整个过程很简单。因为我们程序的执行流程信息都在堆栈上。我们根据堆栈信息我们可以很容易找到起点和终点。那么从问题出发点，到结束点。我们便走了2次。第一次从出发点到结束点，这是为了找到处理程序。第二次则是叫做stack unwind，栈展开。 从出发点到结束点。当然这个过程中，依然有很多更复杂的问题。异常查找时很可能产生死循环。unwind的过程也可以被随时中断或是走到其他地方。而导致我们写的那些备用代码无法执行。事实上NT给了我们非常多的选择。vc只是披了一层皮。

SEH就像ReactOS上写的一样，“SEH is a game which is played between OS and Compiler (Keywords: try, except, __finally)。

写在最后

我发现我越来越罗嗦了。絮叨絮叨的像个大妈。 后面的部分依然有点穿越。在不谈具体实现的细节下去说清楚SEH的基本过程，对我还是太复杂了，应该是我还没有理解透彻，慢慢来吧。具体过程可以参考我推荐的3篇文章，当然。最好的方法是自己推导。 我真的不知道这篇文章是写给自己还是写给别人看的。是的。如果我是读者，当我看到这篇文章的时候，我真想向这个作者扔砖头。