Kernel Space

实况足球是我认为做得最好的足球游戏。以前在游戏厅里那种手柄的感觉一直没有在电脑上找回来。电脑城的USB手柄不是质量问题就是手感不好。最近看到了这个在radioshack卖的东东（12大洋），确实填补了我心中的一片空白。

 http://www.radioshack.com/sm-usb-adapter-for-playstation-2-controller–pi-2348187.html

 这个Playstation-to-USB adapter可以用PS或者PS2手柄上（radioshack的clerk居然理解成了PS/2接口到USB的转换器，分特）。拿到这个adapter以后就可以立刻去amazon寻找Sony标配的dualshock2的手柄了。这个可是如假包换的原配手柄（20大洋）。

http://www.amazon.com/Sony-Playstation-Dualshock-Controller-Black/dp/B00004YRQ9/ref=pd_bbs_sr_1/104-2495826-5862344?ie=UTF8&s=videogames&qid=1177967710&sr=8-1

 好了，Go and enjoy your PES/WE game!!

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

既然说到了内存管理，就顺带说一下内存分配。内存的管理细节以及实现可以看mm部分的源码。暴露给内核程序员的基本内存分配函数是经常要用到的东东。
简单说来，有三种分配内存的方法：

• kmalloc：这个用到很多。这个函数将会分配一片连续的物理内存。通常分配连续物理内存的好处就是构造页表的时候开销很低（通常线性地址加上一个偏移就是物理地址），同时访问起来效率也高。当然连续的物理内存也是很宝贵的资源。内核中使用的buddy algorithm和slab机制都是为了尽量减少内存碎片，增加连续内存分配成功的几率。kmalloc有很多mode，比如说GFP_KERNEL， GFP_ATOMIC。这些mode其实是一些更细节的flag的组合，比如说 GFP_KERNEL 就是 __GFP_WAIT | __GFP_IO | __GFP_FS ； 而 GFP_ATOMIC 就是 __GFP_HIGH。在一些中断处理中需要内存分配立刻返回，这样就需要不同的kmalloc 模式。这些flag具体的意思可以参考LDD3的第八章。

• kmem_cache：这个是Linux内核Slab机制提供的特殊的内存分配函数。“slab”直译过来就是“水泥预制板”:) 其实这个名字非常的形象。内核中经常要分配一些常用的struct，比如说filp, task_struct, file等等。Slab是一个lookaside cache机制，在内存中会创建一个memory pool。这个pool里面当然就是这些指定大小的object。这样分配或者释放起来都很高效（省去了内存分配和初始化的过程）。

•  __get_free_pages：是直接获取整页的内存（页数是2的幂）。其实kmalloc在实现的时候也调用了这个函数。当需要分配大量的内存的时候，使用这个函数能够提高效率。

• vmalloc：这个函数分配一片连续的“虚拟内存”。也就是说返回的线性地址虽然是连续的，但是映射到的物理内存是不连续的，而且跟物理地址可能不是一一对应的（不同于kmalloc和__get_free_pages）。所以在使用分配到的内存时，页表的查询比较频繁，所以效率相对较低。但是LDD3中提到了Linux内核在create_module的时候，采用的就是vmalloc。我看了看/proc/kallsyms，我load的module里面的symbol确实都分布在不同的内存区域。

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

接触Linux内核也有一段时间了，在开发kernel module的时候，其实有几样东西是需要牢牢掌握的。

• 内核基本的struct：其实读Understanding the Linux Kernel (ULK3)的时候很困惑，如果一章一章地读下去，没有什么感觉。其实在读第一遍的时候先掌握内核中重要的struct。这些struct在内核编程中将会频繁用到。
• 内核同步机制： user mode里面的semaphore和mutex是编程必备的工具。在内核里面，同步不仅是线程间的，而且还要考虑SMP的问题。
• 内存管理机制： 无论做什么开发，内存管理都是程序的“循环系统”，如果血液不通畅，整个module的性能肯定上不去。内核内存是很宝贵的资源。下面就简要分析一下具体Linux是如何管理内核内存的（其实是读ULK3和LDD3的读书笔记）

Linux采用的是段页式内存模型，也就是既使用了段（segment）又使用了分页（paging）技术。分段技术是历史遗留的产物，它出现的主要原因就是寄存器存储位数和地址空间位数不匹配的结果。分页和分段都是虚拟内存实现的机制。分段技术利用段基址把内存划分成很多互相重叠的内存空间。当进程在自己的段里运行的时候，自己能够访问的就是整个段空间。但是这样的后果就是进程的内存缺乏必要的保护。所以随着保护模式的引入，分页技术得到了使用。在分页技术的优势下，分段技术显得没有什么必要了，但是程序的分段结构依然保留了下来（数据段、代码段、堆栈段等等）。在程序运行的时候，依然需要配备相应的段。所以Linux采用了这种混合的段页式内存。在Linux中，只有几个固定的段可供使用：内核数据/代码段、用户数据/代码段。在所有内核进程中，段寄存器里载入的始终是内核数据/代码段的段基址，而且这个基址是固定的（当然这个基址还不是真实的物理地址）。同样在用户进程中，段寄存器里载入的始终是用户数据/代码段基址。

所有的虚拟内存实现的机制最关键的是内存虚拟地址到物理地址的映射。Linux的段页式内存模型使用了两级地址映射：虚拟地址-〉线性地址-〉物理地址（ULK3和LDD3的命名有所不同）。逻辑地址就是在程序中使用的地址，这个地址首先要经过分段处理，也就是读入相应的用户/内核段基址（已经是常量了，而且就是0×00000000）。随后就得到了一个地址值没有变化的线性地址。这个地址是32位的（这里讨论的是i386 32bit架构）。这个线性地址需要经过分页处理才能得到真正的物理地址。可以看出这里虚拟内存地址实际上在数值上都等于线性地址，只是段寄存器的内容反映了这个地址是属于用户还是内核，数据还是代码。

在Linux中，有一个著名的3Gb界限，也就是在线性地址中0~3GB的地址是留给用户空间的，3GB~4GB的地址是内核使用的。所以当你在程序中看到一个大于等于0xc0000000的地址，这个地址一定是映射到内核的内存中。Linux采用了多级页表技术来实现从线性地址到物理地址的映射。32位的地址的前10位是Page Directory的index（显然这个表最多有1024个entry）。中间10位是Page Table的index。剩下的12位是页内偏移（在这种实现下，每一个内存页的大小是4KB）。使用这种分页技术的好处是节省进程的空间，因为每一个进程都有一个页表。

Linux使用的是4KB的内存页面大小（CPU有4KB或者4MB两种设置）。实际的物理内存被划分成一个一个4KB的内存页帧，每一个页帧在内存中都对应有相应的一个32字节大小的page struct。在Linux看来，一个page struct实际上就代表了一个实际的物理页帧。每个有效的（mapped）线性地址都映射到一个相应的page struct上。但是内核的线性地址空间只有1GB，而真正的物理地址可以大到4GB，所以没有办法做到线性地址和实际的物理地址的一一对应。所以在内核的1GB线性地址空间中有一部分（896MB， Low Memory）是直接映射到物理地址上的，这部分内存叫做内核逻辑地址（根据LDD3的命名）。内核线性空间还剩下128MB （内核虚拟地址）提供给映射896MB以上的内存（High Memory）之用。内核通过三种不同的办法将896MB以上的物理内存映射到这128MB的线性地址空间中（permanent kernel mapping, temporary kernel mapping, and noncontiguous memory allocation），具体的实现方法可以参考ULK3的第八章。

在Linux处理内存的时候，定义了很多逻辑的概念，比如说page，zone, virtual memory area (VMA), mm_struct等等。每一个逻辑的概念都有对应的struct来支持。作为一个kernel module的开发者，最常用的就是在内核中申请/释放/使用内存空间，以及提供设备中的mmap实现以便让设备内存可以被映射。除了这些，还有一些底层的细节，比如说Linux的内存分配释放缓冲的机制（Buddy System, Slab）。这些底层实现是读Linux源码或者进行Linux裁减时必须要了解的东西，所以以后再来分析这些机制。

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

    最后我们来看看这个被容器类广泛include的bits/allocator.h文件。
    这个文件定义了allocator这个模板类。回想一下上次在new_allocator中看到的：这个类主要定义了几个模板类型的别名，还有重要的函数（allocate, deallocate, construct, destruct）。实际上，这个类没有任何的数据成员，纯粹是一个utility类。现在要分析的类allocator就是从这个类继承来的。下面是代码：

template<typename _Tp>
class allocator: public ___glibcxx_base_allocator<_Tp>
{
   //一些类型别名的定义，与new_allocator里的定义一致
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
typedef _Tp value_type;

      //功能未知的部分。定义了另一个类型的模板结构，唯一的成员就是另外一个类型allocator的typedef。
template<typename _Tp1>
struct rebind
{ typedef allocator<_Tp1> other; };

      //默认构造函数
allocator() throw() { }

      //拷贝构造函数，调用父类的构造函数
allocator(const allocator& a) throw()
: ___glibcxx_base_allocator<_Tp>(a) { }
  
      //参数为另外一个类型allocator的拷贝构造函数
template<typename _Tp1>
allocator(const allocator<_Tp1>&) throw() { }

      //析构函数
~allocator() throw() { }

      //继承其他所有的定义
    };

    同时在这个类的声明的后面，也同样将==和!=两个操作符定义为永远相等。

  //==操作符永真
template<typename _T1, typename _T2>
inline bool
operator==(const allocator<_T1>&, const allocator<_T2>&)
{ return true; }

  //!=操作符永假
template<typename _T1, typename _T2>
inline bool
operator!=(const allocator<_T1>&, const allocator<_T2>&)
{ return false; }

    在这个allocator的真正声明前面有一个specialization定义：

  //前向定义
template<typename _Tp>
class allocator;

  //对于void类型做特殊处理
template<>
class allocator<void>
{
    //定义几个别名，pointer类型为void*。最重要的区别就是去掉了reference类型，因为void&是没有意义的。当然这个void的value_type我也得想想是什么意思:)
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef void* pointer;
typedef const void* const_pointer;
typedef void value_type;

    //同样神秘的rebind，应该会在以后知道它的用途。这里我被迫卖个关子。
template<typename _Tp1>
struct rebind
{ typedef allocator<_Tp1> other; };
};


   好了，其实allocator也挺简单的，至少现在看来是这样。整个这个allocator最重要的allocate和deallocate只是调用了全局的operator new和operator delete。construct和destruct函数调用了全局的new expression和对象的析构函数。根据现在所看到的代码，可以想象的allocator在容器中的用法就是：声明一个allocator对象作为容器的成员，然后任何内存分配的任务都由这个allocator对象来实现。其实经常看到的一个容器声明就是（一般出现在错误中），template<typename _Tp, typename _Alloc = allocator<_Tp> > 。我还没有自己写过自己的allocator，所以一般都用的是系统默认的allocator。

   到现在，分析过的代码有auto_ptr，iterator和allocator。接下来就可以正式看看这些基本的STL元素是如何使用的。下次就打算挑一个non-associative的容器来看看，其他的non-associative的容器依此类推。然后再下次就找个associative的容器来研究研究，尽量达到举一反三的作用。

很难想象钢琴家不用聆听大师的作品；诗人不用揣摩传世的经典；画家不用体会前辈的佳作；拳手不用参详高人的示范。那我们怎么能想象程序员不用仔细学习性感的代码？可惜的是，美妙的代码往往有如像Shrek，乍一看也就是面目丑陋的庞然大物。没有Fionna的聪慧，我们也难欣赏Shrek洋葱一般层次丰富的心灵。再说，代码一旦写成，我们看到的也就是一段神来之笔。再难体会到作者在难题前内心有如困兽般地冲撞，面临多种选择时精神的激荡。我们也再难追溯每个数据结构背后的理念，每段算法成型过程中每一步的由来(顺便说一句。这也是为什么Knuth的书引人入胜的原因。每段算法怎么从无到有，自粗而细，由慢转快，通通脉络清晰)。就算是理解代码本身，想来每人的体会也有深有浅。不知道多少老大因为这些困难没能体会到阅读代码时心头肿胀（乱用冯唐语）的快感？除非，除非有高手引领我们入门，给我们细述经典代码如何玲珑浮屠，如何眼波婉转。

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

    allocator是STL里面的无名英雄，几乎所有的container都要包含它，但是很少有用户直接包含这个文件。事实上所有的容器都需要内存管理，所以它们都包含了包含了 bits/allocator.h 。而这个文件又包含了bits/c++allocator.h。所以寻根溯源，我们来看看 c++allocator.h。这个文件放在了i386-redhat-linux/bits/下面，看似平台相关。打开这个文件一看，结果发现最终包含的文件是ext/new_allocator.h。这还没完，这个文件一开始包含了<new>。终于这个是终点开始看代码。总结一下，基本的include stack是：

new
ext/new_allocator.h
i386-redhat-linux/bits/c++allocator.h
bits/allocator.h

    在std的namespace中，首先定义了bad_alloc()类，作为内存分配失败时返回的对象。

class bad_alloc : public exception
{
public:
bad_alloc() throw() { }
virtual ~bad_alloc() throw();
};

    这个类继承了exception，同时有一个虚析构函数，表示这个类会被用来继承。

struct nothrow_t { };
extern const nothrow_t nothrow;

    这个空结构nothrow被声明成全局的变量，具体用处还不得而知。    

typedef void (*new_handler)();
new_handler set_new_handler(new_handler) throw();

    这个就是大家熟知的new_handler了，这里定义了这个函数指针的类型。随后就定义了set_new_handler函数，输入一个新的handler，然后返回旧的handler。

    随后，声明了各个版本的new和delete操作符，包括分配/释放单个对象和对象数组的版本，以及不抛出任何异常的版本：

void* operator new(std::size_t) throw (std::bad_alloc);
void* operator new[](std::size_t) throw (std::bad_alloc);
void operator delete(void*) throw();
void operator delete[](void*) throw();
void* operator new(std::size_t, const std::nothrow_t&) throw();
void* operator new[](std::size_t, const std::nothrow_t&) throw();
void operator delete(void*, const std::nothrow_t&) throw();
void operator delete[](void*, const std::nothrow_t&) throw();

    从上面可以看到，刚才定义的nothrow_t类型被用作不抛出异常版本的第二个参数用以在signature上区分两种operator。

    最后，文件定义了两个默认的new/delete placement。new操作符直接返回了传入的第二个参数指向的内存。

inline void* operator new(std::size_t, void* __p) throw() { return __p; }
inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
inline void operator delete (void*, void*) throw() { }
inline void operator delete[](void*, void*) throw() { }

    这些operator和placement都是定义在std namespace之外的，所以是全局的内存分配操作符。（操作符只是做了声明，没有具体的实现）

    接下来，我们看看ext/new_allocator.h。这个函数是定义在__gnu_cxx namespace里面的，所以是generic的c++实现。这个文件主要定义了一个类 new_allocator。代码为：

template<typename _Tp>
class new_allocator
{
public:
//定义一些类型
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
typedef _Tp value_type;

template<typename _Tp1>
struct rebind
{ typedef new_allocator<_Tp1> other; };
      new_allocator() throw() { }

new_allocator(const new_allocator&) throw() { }

      //拷贝构造函数，实现为空
template<typename _Tp1>
new_allocator(const new_allocator<_Tp1>&) throw() { }

~new_allocator() throw() { }

      //返回参数对象的地址     
pointer
address(reference __x) const { return &__x; }

const_pointer
address(const_reference __x) const { return &__x; }

      //调用全局的new操作符分配__n个_Tp对象大小的内存，当__n为0的时候，行为取决于全局操作符的行为
pointer
allocate(size_type __n, const void* = 0)
{ return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); }

      //释放内存，如果__p为空，由全局delete操作符handle
void
deallocate(pointer __p, size_type)
{ ::operator delete(__p); }

      //返回一次最多可以用allocate分配的_Tp对象的个数
size_type
max_size() const throw()
{ return size_t(-1) / sizeof(_Tp); }

      //调用全局的new expression构造一个_Tp对象，然后用__val做拷贝构造
void
construct(pointer __p, const _Tp& __val)
{ ::new(__p) _Tp(__val); }

      //调用析构函数释放__Tp对象
void
destroy(pointer __p) { __p->~_Tp(); }
};

    在i386-redhat-linux/bits/c++allocator.h中只有两行。首先是包含了ext/new_allocator.h, 然后是将在这个文件里面定义的__gnu_cxx::new_allocator typedef 成为___glibcxx_base_allocator，在bits/allocator.h里面使用。

    到现在为止，一个基本的内存分配类定义好了（new_allocator，含有allocate,deallocate,construct,destroy几个基本函数），虽然都是调用底层默认的operator new或者new expression。今天太晚了就先写到这里，下次我们分析一下bits/allocator.h。

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

    这次分析的是bits/stl_iterator.h。这个文件其实只是定义了一些iterator的adaptor，也就是进一步的包装了一下iterator这种类型。reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator, __normal_iterator是这个文件中定义的几种iterator。他们的基本作用是：给定一个已有的iterator，将这个iterator的行为做一下修改（实际上是复制一个iterator，然后重新定义几个基本的operator）。
    reverse_iterator顾名思义就是将原有iterator的操作方向反过来（当然原来的iterator必须是bidirectional或者random_access的）。下面就是这个adaptor类的定义：

  template<typename _Iterator>
  class reverse_iterator
  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
  typename iterator_traits<_Iterator>::value_type,
  typename iterator_traits<_Iterator>::difference_type,
  typename iterator_traits<_Iterator>::pointer,
  typename iterator_traits<_Iterator>::reference>
  {

    // 这个类的模板参数是一个iterator的类型，然后这个iterator的几个基本特征作为它父类iterator的模板参数。iterator_traits的用处在这里体现了出来，它轻松的提取了这个类型的基本特征。而iterator的作用就是把提取出来的基本特征存储下来。

// 这个protected的成员就是原有iterator的拷贝。这是一个基本的Object Adaptor Pattern（相对于Class Adaptor Pattern）。
protected:
  _Iterator current;

// 把原有的iterator的类型特征作为reverse_iterator的类型特征，原有的iterator的类型赋给别名iterator_type
public:
  typedef _Iterator iterator_type;
  typedef typename iterator_traits<_Iterator>::difference_type
  difference_type;
  typedef typename iterator_traits<_Iterator>::reference reference;
  typedef typename iterator_traits<_Iterator>::pointer pointer;

public:

//默认的构造函数，如果_Iterator是指针类型，那么执行的将是一个空初始化
reverse_iterator() : current() { }

//参数为原有iterator的构造函数
explicit reverse_iterator(iterator_type __x) : current(__x) { }

 //拷贝构造函数，实际上就是复制两个对象的current成员变量
reverse_iterator(const reverse_iterator& __x) : current(__x.current) { }

// 从其他类型的reverse_iterator拷贝的拷贝构造函数，因为current是reverse_iterator的protected的对象，所以提供了一个base函数返回这个值
template<typename _Iter>
  reverse_iterator(const reverse_iterator<_Iter>& __x)
 : current(__x.base()) { }

// 返回current（current本身是protected）
iterator_type base() const
  { return current; }

//dereference操作符，因为reverse_iterator一开始是指向最后一个元素后面一个位置的，所以*操作符需要返回当前位置前面一个元素（很可能一开始current是一个container的rbegin()）。reverse_iterator返回这个位置前面一个位置的值
reference
  operator*() const
  {
 _Iterator __tmp = current;
 return *--__tmp;
  }

//成员操作符，利用dereference操作符实现
pointer
  operator->() const
  { return &(operator*()); }

// 前缀增量操作符，返回current移动后的对象引用
reverse_iterator&
  operator++()
  {
 --current;
 return *this;
  }

// 后缀增量操作符，返回一个current没有修改过的对象的拷贝
reverse_iterator
  operator++(int)
  {
 reverse_iterator __tmp = *this;
 --current;
 return __tmp;
  }
 
// 前缀减量操作符
reverse_iterator&
  operator--()
  {
 ++current;
 return *this;
  }

// 后缀减量操作符
reverse_iterator operator--(int)
  {
 reverse_iterator __tmp = *this;
 ++current;
 return __tmp;
  }

// +操作符，返回一个current减去n步的reverse_iterator的拷贝（这里current需要有 “-” 操作符的重载实现）
reverse_iterator
  operator+(difference_type __n) const
  { return reverse_iterator(current - __n); }

// +=操作符，返回当前对象的引用
reverse_iterator&
  operator+=(difference_type __n)
  {
 current -= __n;
 return *this;
  }

// -操作符，返回一个拷贝（最可能的原因是防止作为lvalue）。同+操作符一样，current需要有”+”操作符的重载实现
reverse_iterator
  operator-(difference_type __n) const
  { return reverse_iterator(current + __n); }

// -=操作符，返回当前对象的引用
reverse_iterator&
  operator-=(difference_type __n)
  {
 current += __n;
 return *this;
  }

// 下标操作符。下标的index表示本reverse_iterator“前进” index步，然后返回dereference以后的值
reference
  operator[](difference_type __n) const
  { return *(*this + __n); }
  };

    随后，文件中定义了8个两个reverse_iterator之间比较的模板函数，这里不一一分析了，举一个例子足够：

template<typename _Iterator>
  inline bool
  operator==(const reverse_iterator<_Iterator>& __x,
  const reverse_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

    这个内联函数重载了相等操作符，参数是两个具有相同underlying iterator类型的reverse_iterator对象。真正的实现是通过比较两个reverse_iterator的base函数返回的current的值来实现的。所以这个实现依赖于_Iterator类型的==操作符。8个函数当中最后一个也值得提及一下：

template<typename _Iterator>
  inline reverse_iterator<_Iterator>
  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
  const reverse_iterator<_Iterator>& __x)
  { return reverse_iterator<_Iterator>(__x.base() - __n); }

    这个函数也是实现了加法操作符，但是跟reverse_iterator的成员函数operator+不一样。成员函数只负责 (reverse_iterator+n) 的情况，但是(n+reverse_iterator)的情况没有cover。这个函数只是使实现更为全面。

    接下来看看另外一个Adaptor模板－－back_insert_iterator。这个模板和前面的reverse_iterator不一样，这个模板的参数不是另外一个iterator，而是一个container。而这个container是必须符合一定要求的。这个要求就是”back_insert”，简单来说就是支持push_back函数的容器，比如说deque、list和vector。下面就是这个模板类的定义：
  //可以看出，这个Adaptor以一个容器类型作为模板参数，同时它也是output_iterator类型的，也就是只能写，不能读
template<typename _Container>
  class back_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
//保存这个容器的指针
protected:
 _Container* container;
     
// 定义_Container类型为container_type，方便引用
public:
 typedef _Container container_type;

// 唯一的一个构造函数，创建这个iterator的唯一方法就是传入一个容器的对象
explicit
  back_insert_iterator(_Container& __x) : container(&__x) { }

// 最重要的一个操作符：赋值操作符。给定一个新的容器包含元素的类型的对象，然后利用容器的push_back将这个元素插入到容器的尾部
back_insert_iterator&
  operator=(typename _Container::const_reference __value)
  {
 container->push_back(__value);
 return *this;
  }

// 因为是一个output_iterator，所以所有读相关的操作都是返回iterator本身（iterator本身没有任何数据）
back_insert_iterator&
  operator*()
  { return *this; }

// 同时不支持前缀增量运算符，因为push_back的同时相当于向后移动了
back_insert_iterator&
  operator++()
  { return *this; }

// 同理不支持后缀增量运算符
back_insert_iterator
  operator++(int)
  { return *this; }
  };
 
    这个模板类的问题就是：假如说我要声明一个back_insert_iterator的实例针对list，我需要这样写：

back_insert_iterator<list> it(list_instance);

    我有一个list的实例list_instance，但是我还是需要知道这个实例的准确类型list，因为这个iterator只提供了一个构造函数。因此STL的设计者加入了下面这个模板函数back_inserter：

template<typename _Container>
  inline back_insert_iterator<_Container>
  back_inserter(_Container& __x)
  { return back_insert_iterator<_Container>(__x); }

    这个函数只需要一个模板实例作为参数，在调用这个函数的同时，容器的类型也隐式地传给了模板，减轻了用户的负担。这确实是一个“贴心”的设计。

    随后的front_insert_iterator这个Adaptor和back_insert_iterator的实现相同，这里就不再鳌述了。之后定义的insert_iterator的实现也大抵相同，就留作家庭作业了：）

    最后，这个文件定义了一个__normal_iterator模板类，这个类不在std的namespace中，而是在__gnu_cxx中。这个模板类有两个参数，一个是_Iterator，另外一个是_Container。从代码的注释中可以了解到这个模板类是把不是iterator类但是具有iterator特性的类型（比如说指针）转换为iterator类型；而后面的_Container类型纯粹是作为一个区分的参数，这样不同的_Container就可以生成不同的__normal_iterator模板类的实例。举个简单的例子，比如说我有两个容器，list<int> 和 vector<int>，我可以用 __gnu_cxx::__normal_iterator<int*, std::list<int> > 和 __gnu_cxx::__normal_iterator<int*, std::vector<int> >生成两个iterator，分别对两个容器里面的int指针进行包装。事实上在我们以后要研究的vector容器中，vector::iterator就是用__normal_iterator生成的。

   结语：Whewwwww，iterator基本上就能介绍这么多了，也许有机会再介绍一下另外两个包含在<iterator>中的ostream和istream。纵观介绍的三个头文件，可以看出：

• bits/stl_iterator_base_types.h真正定义了iterator，但是没有定义任何真正的操作，因为真正的操作是容器相关的，比如说vector可以用__normal_iterator这个Adaptor来生成iterator，但是list就要考虑到底层的链表结构来实现iterator。bits/stl_iterator_base_types.h最重要的是定义了几种iterator的继承关系，iterator必须的一些类型特征信息，可以说只是定义了iterator的元信息，每个容器的iterator是在每个容器自己的头文件中实现的，包含<iterator>只是提供一些元数据。
• bits/stl_iterator_base_funcs.h定义了advance和distance两个函数，到现在为止没有看到在哪里用（奇怪。。），估计以后研究容器的时候会发现。
• 今天讨论的bits/stl_iterator.h定义几个重要的iterator相关的Adaptor。因为有了这些Adaptor，容器只需要关心实现最基本的iterator，这些变种iterator可以通过这些Adaptor来实现，这是一个典型的高效和高封装性的设计。
     

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

    这次着重分析一下第二个头文件： bits/stl_iterator_base_funcs.h

    这个文件主要定义了两个重要的函数，distance和advance。distance主要是得到两个iterator之间的步数（距离）；而advance则是将iterator前进n步的函数。当然，根据iterator的类型不同，分别有不同的实现。下面就来看看：

template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last)
{
++__first;
++__n;
}
return __n;
}

    这个是input_iterator的版本，给定指定的first和last两个iterator，移动first直到last，然后返回走过的步数。因为是input_iterator，所以只能一步一步地走。再来看看random_access_iterator的版本：

template<typename _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
return __last - __first;
}

    这个模板直接使用了减法来得到两个iterator之间的距离。很显然，这个减法的运算是被重载过的，稍后我们再来看看这个减法的重载。random_access_iterator只使用了一个减法就得到了距离，显示了它的“强大”。注意看下面这个模板函数：

template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
// concept requirements -- taken care of in __distance
return std::__distance(__first, __last,
std::__iterator_category(__first));
}

    这个distance是对上面两个函数的包装。因为如果只有第一个函数，random_access_iterator也可以使用（random_access_iterator是从input_iterator继承来的），但是为了给这种iterator提供更好的支持，我们有了第二个函数。这两个模板函数都有第三个参数是iterator的类型。但是在真正使用这两个函数时候如果还是需要提供这个类型信息就显得有些冗余，所以这第三个distance就包装了一下－－主动提取了first的iterator类型作为参数传入。当然，代码里的注释明确说明last是从first必须可达的（否则第一个函数里面的循环将不知何时会中止）。

    下面就是advance函数了：

template<typename _InputIterator, typename _Distance>
inline void
__advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
while (__n--)
++__i;
}

template<typename _BidirectionalIterator, typename _Distance>
inline void
__advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
if (__n > 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}

template<typename _RandomAccessIterator, typename _Distance>
inline void
__advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__i += __n;
}

    跟distance不同的是，advance需要区别对待bidirectional_iterator因为advance可以forward也可以backward。所以有了上面三个版本，每个函数的第一个参数都是iterator的引用，需要走的偏移以及Iterator的类型。对于bidirectional_iterator，走的方向是根据n的正负来判断。而input_iterator的n传入是就应该是正数或者零。对应的，advance函数也有自己的封装：

template<typename _InputIterator, typename _Distance>
inline void
advance(_InputIterator& __i, _Distance __n)
{
// concept requirements -- taken care of in __advance
std::__advance(__i, __n, std::__iterator_category(__i));
}

    iterator的类型作为第三个参数传入，调用相应的advance函数。

    注意上面所有的模板函数，typename后面的_InputIterator和_BidirectionalIterator其实只是个名字。template本身不会检查传入的类型是否是input_iterator或者bidirectional_iterator。首先响应相应的函数调用是通过第三个参数来判断的。只有category的类型符合，相应的函数就会被调用。比如一个random_access_iterator作为参数，那么传入的第三个参数类型为random_access_iterator_tag，所以相应的random access的版本会被调用。这个是STL里面实现基本函数匹配的方法，这也是几乎所有的STL元素本身都含有类型信息的原因。同时还应该注意到 “  __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>) ” 这样的glibc的宏来做真正的传入模板参数的类型判断。

    好了，下次我们将正式进入iterator的源码讨论。（To be continued）

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

    研究STL，有些基本的要素是一定要看的。container都会用到iterator和allocator，前者实现了指针式的元素遍历，后者提供了必要的内存分配机制。所以我准备先研究一下这两个东东（iterator和allocator）。先从iterator说起。

    当刚开始接触iterator的时候，基本上只使用vector，然后发现iterator这个东东确实不怎么好用，明明可以用下标就解决的问题却要写很多begin或者end之类的东西，使code突然变得很复杂。后来发现这个iterator确实是一个精妙的设计（让我设计这个STL估计就不会想到这个通用的东西）。实际上iterator对container实现了很好的封装，无论是vector还是map（tree），iterator可以遍历所有的元素，而且用户并不需要知道container的具体实现。所以下次有人让你说出一个design pattern出来，iterator这个模式应该脱口而出。singleton也许没怎么用到，但是这个iterator确是近在手边的。iterator也许可以设计成一个有很多forward或者backward这样函数的类。但是正好在c++里面有一个很“酷”的东东，那就是指针。STL的设计者就正好利用了指针的特性，让iterator模仿了指针的特性和用法，让C++的程序员用得更舒服更顺手更。。。。

    那么STL是怎么实现这个重要的模板类的呢？STL是如何在不知道任何container的情况下，设计这个通用的iterator的？Here we go！

    iterator首先包含了bits/stl_iterator_base_types.h，这里定义了几个基本的iterator类型：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
  struct random_access_iterator_tag : public bidirectional_iterator_tag {};

    可以看到一个基本的继承关系。input_iterator和output_iterator是基本的类型，他们只能向前移动，只能读或者写，而且每个位置只能读/写一次。forward_iterator则是增强版的input_iterator，事实上它既能同时读写，又能多次读写。bidirectional_iterator是双向的，random_access_iterator则突破了一次只能移动一步的限制，可以向前后移动任意多步，是功能最强大的一种iterator。

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};

template<typename _Iterator>
struct iterator_traits
{
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};

    struct iterator指定了在一个iterator里面应该包含的必要的类型信息（特征），包括iterator本身的类型，值类型和指针/引用类型等等。这些类型都可以通过模板参数传入。接着，马上定义了iterator_traits。这个类的模板参数只有一个（希望的类型是某个iterator类型，这个iterator_traits里面的几个fields就保存了这个传入类型iterator的基本特征。

    随后的两个定义，立刻做了模板的specialization：

template<typename _Tp>
struct iterator_traits<_Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};

template<typename _Tp>
struct iterator_traits<const _Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};

    这两个特殊模板定义了iterator应该如何处理指针类型。从定义可以看出，如果是指针类型的iterator，那么这个iterator就是random_access类型的（这个很容易理解）。然后值类型是指针所指的类型，指针类型是本身，引用类型是underlying的数据类型的引用。

    在文件的最后，定义了一个inline函数：

template<typename _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{ return typename iterator_traits<_Iter>::iterator_category(); }

    给定一个iterator，这个函数返回iterator本身的特征里面的类型（input,output,forward….）。这里就可以看到这个traits的用法：对于任意一个iterator实例，如果要取得这个iterator的特征信息，就把这个类型放到一个iterator_traits的模板类中，然后访问里面几个typedef好的成员获得类型信息。这个是trait模板类的基本用法，也是STL里面储存一个特征（包括类型，limit某些跟具体数据类型相关的信息）的基本方法。

    好，这次先说到这里。另外两个重要的文件 bits/stl_iterator_base_funcs.h 和 bits/stl_iterator.h 周末再来分解。（To be continued）

本文作者:campos 本文出处:http://www.mykernelspace.com  (转载请保留此行，谢谢)

   这次的确是个“货真价实”的牛角尖，几乎没有人会这样写程序。代码如下：

#include <stdio.h>

char* func()
{
char *x="hello world";
return x;
}
int main()
{
char *y = func();
printf(y);
}

      乍一看肯定觉得这个代码会打印出一些junk，因为返回了一个在func里面声明的指针，而且指针没有指向一个动态分配的内存。事实上，这段代码总能打印出著名的hello world来，无论什么编译器什么平台。不信可以试试。但是如果把char *x改成char x[]，打印出来的就确实是junk了。具体背后发生了什么，还是请出我们的汇编代码。当用char *x的时候，代码是：
    
.LC0:
.string "hello world"
.text
.globl func
.type func, @function
func:
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl $.LC0, -4(%ebp)
movl -4(%ebp), %eax
leave
ret

注意这里使用的是$.LC0。如果换成char x[]，代码则变成了：
     
func:
pushl %ebp
movl %esp, %ebp
subl $24, %esp
movl .LC0, %eax
movl %eax, -24(%ebp)
movl .LC0+4, %eax
movl %eax, -20(%ebp)
movl .LC0+8, %eax
movl %eax, -16(%ebp)
leal -24(%ebp), %eax
leave
ret

    注意看，这里没有了$，而是直接使用了.LC0 这个data segment名字。这就是唯一的区别了。$表示是取segment的偏移，所以在第一种情况下func返回的是这个偏移，相当于返回的是指向data segment里面的那个字符串的指针。而第二种情况，返回的则是func本地stack的栈指针，这个栈在函数返回后就销毁了，所以最后打印出来一段junk。
    确实估计每人会写这么古怪的代码，而且乍一看还是错的。但是这段代码却说明了一个问题，那就是程序中的指针可能指向什么地方。可能拍拍脑袋就能想到栈和堆。但是唯一忽略的一点就是程序本身的数据段（data segment）。仔细看第二段代码可以发现，实际上，这个声明的数组实际上是按字节从数据段里面拷贝过来的，相当于有了第二份copy。
    更有趣的是，如果在main函数里面企图修改y指向的字符串会得到segmentation fault （比如 y[0]=’a'）。可能的原因是数据段是受保护的，这个”hello world”相当于一个const的字符串，如果企图修改将导致run-time错误（看来这个const还挺厉害）：）