Raven's Blog

这是stl源码阅读系列的第二篇，这一篇来看看stl中迭代器traits的实现。

在stl中，有三个彼此关联的组件：

Containers(即我们常用的vector, list, deque等)装载数据结构，Algorithms装载数据操作，两者相互独立，Iterator作为中间人，将两者联系起来。iterator提供访问容器数据成员的接口，隐藏了每个容器的具体存储实现（即迭代器设计模式）。每个容量都会提供一份iterator实现，所以在分析容器前，先看看iterator。

另外，整个stl可以看做泛型编程的最佳实践，所以在本篇中也会介绍一些泛型（模板）编程的概念。

接近一年未更新博文，忙着适应工作环境，当然自己也变懒了不少。感觉还是得多抽时间充实自己，本文开始分析stl源码。

本系列分析的stl 版本为 sgi v3.3。

首先分析内存分配器，因为容器需要依赖内存分配器来实现。如最常用容器的定义:

1
2
3
4
5

// alloc 是 SGI STL 的空间配置器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
  // requirements:

这里的 __STL_DEFAULT_ALLOCATOR 定义为：

1
2
3
4
5
6
7

# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
#   else
#     define __STL_DEFAULT_ALLOCATOR(T) alloc
#   endif
# endif

allocator 内部实现也为 alloc, 所以本文分析的对象为 alloc。

关于 alloc 的实现，文件目录为 allocator/stl_alloc.h

关于alloc的定义有两种：(通过宏来开关是哪一种)：

1. 第一级配置器：

1
2

typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;  // 令 alloc 为第一级配置器

此时实际类为 __malloc_alloc_template

2. 第二级配置器:

1

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;  // 令 alloc 为第二级配置器

此时实际类为 : __default_alloc_template

0. 前言·

本实验为MIT6.s8081的第十一个实验，也是最后一个实验，主题为 网卡驱动 相关。实验要求实现网卡驱动的收发过程核心逻辑。

本实验的前置知识较多，上来就是E1000网卡手册，但实际上需要阅读和理解的部分很少，实现的代码也只是几十行。

0. 前言·

本实验为MIT6.s8081的第十个实验，主题为 mmap 相关。实验要求实现简化版本的 mmap/munmap 。

0. 前言·

本实验为MIT6.s8081的第九个实验，主题和 文件系统 相关。实验任务有两个：

1. 增大xv6的最大文件size限制
2. 实现软链接

整体来看，实验相对简单。

0. 前言·

本实验为MIT6.s8081的第八个实验，主题和 锁 相关。实验任务有两个：

1. 增加内核内存分配器的并发性
2. 增加文件系统buffer cache的并发性

本实验是第二个难度较大的实验。很值得一做。

0. 前言·

本实验为MIT 6.s081的第七个实验，主题和 多线程 相关。实验任务有三个：

1. 实现user level的thread switch
2. 完善并发hash table
3. 实现一个Barrier，类似Java的CyclicBarrier

听完MIT6.S081的中断课，感觉仍不是很理解，本文摘抄自这篇文章，做些整理写给自己，部分内容可能有错，看原文会更好。

0. 前言·

本实验为MIT 6.s081的第六个实验，主题为 copy-on-write(cow, 写时复制)相关。实现进程在fork时的cow机制。

要求：

更改xv6内核 fork 机制，实现延迟分配物理page给子进程。具体而言，在fork时，只用创建子进程的页表，但无需拷贝实际的物理页，并同时更新父子进程对应页的PTE为 not writable。 当父或子进程对物理页进行实际更新时，CPU产生page fault, 内核此时才分配新物理页，执行拷贝和页表项重映射。

0. 前言·

本实验为MIT 6.s081的第五个实验，主题和内存的lazy allocation相关，是page table的应用之一。其余应用包括不限于(copy on write, zero fill on demand, demand paging)。

本实验分为三个task:

1. 取消sbrk系统调用中的内存分配。即准备从eagerly分配变为lazy分配。
2. 实现lazy allocation，然后通过echo hi测试。
3. 继续完善lazy allocation，完成所有测试。包括lazytests和usertests。