XFRM lookup

As you know, I divide xfrm-flow into four parts. Here is the point A stuff:xfrm_lookup.
Before go thru the code, I'll give my syllabus. Also I hope that you have read RFC2401 or RFC4301. And if you understand all of them, wow congradulation! They're:
1. Where is the policy(struct xfrm_policy) comes from?
2. How to find the policy, during sending or recving packet?
3. How to find sa bundle?
4. How to resolve a sa(struct xfrm_state) if step 3 failed?
5. How to create a sa bundle and attached to policy->bundle?
6. How xfrm do ah,esp,etc?
Now, let's go through the code, and solve the questions above(during reading, I skip over code about socket).

Where is the policy(struct xfrm_policy) comes from?
  Before reading code, we should know that 'xfrm_nr' and 'xfrm_vec', which are both in 'struct xfrm_policy', are always initiated before using and they're user-defined. Here is the way:
+sendmsg->netlink_unicast->
 +xfrm_user_rcv_msg->xfrm_dispatch[].xfrm_add_policy->
  +xfrm_policy_construct->...

How to find the policy, during sending or recving packet?
  The first step to find policy is to search 'flowi cache', which accelerates the procedure. If cannot find one from the cache, it will lookup the global-hash-table, and if have one, it will create a corresponding flowi-cache for later searching. Finally, if policy is found ,everyting goes okay, othervise it returns error.The code:
+flow_cache_lookup->
 .xfrm_policy_lookup
  If you've used Cisco IPsec device, you can think the global-hash-table as acl, and so the flowi-cache as acl-cache.
  By the way, we find xfrm support sub-policy, but I don't know how vendors use it(maybe they support sub acl?), so I cannot help you understand it.

How to find sa bundle?
  After finding out the xfrm_policy and policy says 'allow', then what to do next is to extrac sa-bundles from xfrm_policy.That's the key work of xfrm_lookup to do. If find the stuff, it returns directly, or there will be some other work left to resolve one. The code:
+xfrm_find_bundle->
 __xfrm4_find_bundle->xfrm_bundle_ok
 As the function-call chain says: if found a bundle, it has to check the bundle by xfrm_bundle_ok.So what does the function do?First of all, Lets walk the structure 'xfrm_dst->dst'(you can see the diagram in xfrm.h, I just modified something):
 dst -. xfrm .-> xfrm_state #1
    |-.next<---. child .-> dst -. xfrm .-> xfrm_state #2
                     |-.next<---. child .-> dst -. xfrm .-> xfrm_state #3
                            |-.next<---. child .-> NULL
  Generally, the key part of the check is the 'xfrm_dst list' ,formed as the above, and meanwhile it checks whether the mtu in each child, including his "father", has changed or not, if changed, re-calculated 'dst->metrics[RTAX_MTU-1]' and update route_cache_mtu/child_cache_mtu.

How to resolve a sa(struct xfrm_state) if step 3 failed?
  If cannot find any bundle, it should resolve sa by the xfrm_tmpl, which is configured during the construction of xfrm_policy. And xfrm_nr(in xfrm_policy) is the number of sa(xfrm_state).Here is the code:
+xfrm_tmpl_resolve->
 +xfrm_tmpl_resolve_one->
  -xfrm_state_find
  All here should we know that to find a sa is based on xfrm_tmpl info and a few hash tables who contains all the inserted sa.Meanwhile, if there is no sa corresponding to the xfrm_tmpl(not a optional one),we should drop the packet, as it's unsafe to transmit.But there is a exception that if the error code is EAGAIN,it means xfrm requiring sa from(by netlink/pfkey) sadb-engine, so xfrm should wait(shedule()) until wake up.If no sa, xfrm try to require one:
xfrm_state_find->
 .km_query(x, tmpl, pol)
And after that xfrm should sleep:
 +xfrm_lookup->
  .set_current_state(TASK_INTERRUPTIBLE);
  .schedule();

How to create a sa bundle and attached to policy->bundle?
  If we're luck so that we found a number of sa, we put all the sa in the 'xfrm_state' arrary for later use.The really creating work does in __xfrm4_bundle_create:
 +xfrm_bundle_create->
  -__xfrm4_bundle_create
  Result is what we see just above(yeah, it's 'xfrm_dst->dst').During linking each dst, it initiates route and pmut information: if xfrm_state is in tunnel/beet mode, it calculates route infomation of the encapsulating(outer) ip, or it just use the one it already has, and at the end, it calculates pmtu in each dst(dst father's mtu should always shorter than his child, do you know why?).
  Finially, it bind the dst-list to policy->bundles and set policy->bundles->next to itself(what a smart stuff!).

How xfrm do ah,esp,etc?
  Once xfrm has bundles, in each dst there is an output handler(xfrm_output) registered by xfrm_state. During packet walking through the ip stack it will do ah, esp, and etc.In the futher(Point B) i will try to give you a clear description, not this time.