二叉树中累加和为指定值的最长路径

发表于 2017-02-27 | 分类于面试算法 |

问题

给定一棵二叉树的头节点head和一个32位整数sum,二叉树节点值类型为整型，求累加和为sum的最长路径长度.  
路径是指从某个节点往下,每次最多选择一个孩子节点或者不选所形成的节点链

阅读全文 »

二叉树后序非递归遍历

发表于 2017-02-26 | 分类于面试算法 |

问题

二叉树后序非递归遍历实现
后序遍历

阅读全文 »

bootloader加载kernel

发表于 2017-02-22 | 分类于 JOS操作系统 |

bootloader实际做了两件事：进入保护模式和加载内核程序。这篇文章将介绍bootloader加载内核程序的过程

内核的装入过程

对 ELF 文件有了基础地认识后,我们再来研究一下 Boot Loadr 具体是如何将 kernel 的可执行 ELF 文件加载到内存中的。boot/main.c 就是从硬盘读取 kernel,下面我们就分块来分析一下这个C程序

void bootmain(void)
{
    struct Proghdr *ph, *eph;

    // read 1st page off disk
    // 把操作系统映像文件的elf头部读取出来放入内存中,把内核的第一个页
    //的内容读取到内存地址ELFHDR(0x10000)处

    // 程序就将文件的前 4KB 读入内 存,这其中包括 ELF 文件头以及程序头表
    // 这样就可以找到文件的每一段
    readseg((uint32_t) ELFHDR, SECTSIZE*8, 0);

    // is this a valid ELF?
    // elf文件的头部就是用来描述这个elf文件如何在存储器中存储,文件是可链
    // 接文件还是可执行文件，会有不同的elf头部格式.对于一个可执行程序，通
    // 常包含存放代码的文本段(text section)，存放全局变量的data段，存放
    // 字符串常量的rodata段
    if (ELFHDR->e_magic != ELF_MAGIC)
        goto bad;

    // load each program segment (ignores ph flags)
    // 部中一定包含Program Header Table。这个表格存放着程序中所有段的信息。
    // 通过这个表我们才能找到要执行的代码段，数据段等等。所以我们先获得这个表
    ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);
    eph = ph + ELFHDR->e_phnum; //表尾

    //把操作系统内核的各个段从外存读入内存中
    for (; ph < eph; ph++)
        // p_pa is the load address of this segment (as well
        // as the physical address)
        readseg(ph->p_pa, ph->p_memsz, ph->p_offset);

    // call the entry point from the ELF header
    // note: does not return!
    // 跳转到操作系统内核程序的起始指令处.把控制权从boot loader转交给了操作
    // 系统的内核
    ((void (*)(void)) (ELFHDR->e_entry))();

bad:
    outw(0x8A00, 0x8A00);
    outw(0x8A00, 0x8E00);
    while (1)
        /* do nothing */;
}

可以看到 SECTSIZE*8 代表 4KB,这就是说在一开始 ,程序就将文件的前4KB 读入内存,这其中包括 ELF文件头以及程序头表, 根据这些信息，我们可以找到文件的每一段。于是紧接着程序利用 readseg函数将内核文件的每一段依次读入内存然后转到内核入口地址执行。实际上我们可以通过“objdump –f 可执行文件”命令来查看 ELF 文件的入口地址。

通过实验可以看到 kernel 的入口地址是 0xf010000c,然而在程序跳转的时候,却
将 0xf010000c 与 0xFFFFFF 相与以后的值作为入口地址,这是因为 kernel 程序的链接地址是 0xf0100000,而由于实际的物理内存没有那么大,在 0xf0100000 地址处并没有物理内存, 所以真正的加载地址实际上是 0x100000,相应的入口地址也就是 0x10000c,即是 0xf010000c 与 0xFFFFFF 相与以后的值。

内核程序的分析

当我们查看内存的中的 ELF 文件头的相应信息后,我们发现 kernel 可执行文件实际上是分为两段
第一段在文件中的偏移是 0x1000,而在内存中占据的字节数是 0x6daa,链接地址 0xf0100000;
第二段在文件中的偏移是 0x8000,而在内存中占据的字节数是 0x8bc0,链接地址 0xf0107000

Kernel的分段和分节

在上图中可以看到kernel可执行文件的第一段包含了 ELF 文件的.test 节、.rodata 节、.stab节以及.stabstr 节,而文件的第二段包含了.data 节以及在硬盘上不占用空间但在内存中占据 660 字节的.bss 节,在这里程序头表的第二项会用 p_filesz 成员变量标注该段在文件占用的字节数(磁盘)并且同时用 p_memsz 标注在内存中占用的字节数,这样 Boot Loader 便会在从硬盘读入第二段的同时为.bss节在内存中分配空间。.comment 节没有被包含在任意一段中,这表明它没有被装入内存

完全二叉树节点个数

发表于 2017-02-21 | 分类于面试算法 |

问题

给定一棵完全二叉树的头节点 head,求其中的节点个数。
时间复杂度不超过O(n)

完全二叉树与满二叉树

阅读全文 »

JOS操作系统

发表于 2017-02-20 | 分类于 JOS操作系统 |

操作系统，江湖流传着计算机三大浪漫之一。在学习这门课时，如果仅仅把目光停留在课本上一些关于操作系统概念上的叙述，并不能对操作系统有着深层次的理解。当然也
体会不到其中的浪漫。

MIT的操作系统课程6.828是大家口中的OS神课。麻雀虽小，五脏俱全。它能够
帮助我们真正的了解操作系统在做什么以及一个小型OS具体到代码是如何实现的。开始折腾吧，它值得你付出时间和精力。

我将该项目的目前完成Lab的代码实现托管在github上，传送们.欢迎star

虽然之前读过《深入理解计算机系统》，读完之后对很多OS的概念和实现细节都是只见树木不见森林。然后从寒假回家就窝家里开始刷Lab。目前对OS的理解清楚了很多，
从书本概念到0距离接触代码这一过程，将很多之前学习过的知识点都串了起来。比如elf文件的理解，函数调用的底层机制实现。当然汇编代码的阅读能力，没有了之前对它的恐惧感，算是得到质的提升吧。

不可否认的是有些Exercise真的非常让人头痛、一个bug可能会调很久甚至几天没有进展。一
个概念查阅大量的资料，反复的理解，一遍又一遍地认识。

具体每个Lab所完成的工作(目前只刷到lab4)

Lab1是熟悉的过程，需要学习QEMU模拟器的使用、开机启动流程、调试工具、bootloader、以及整个加载kernel的流程。做完这个lab会具备基本的内核调试能力，以及掌握开机到通电，
bootloader是如何加载kernel的。

Lab2要完成
JOS的的内存管理模块，需要学习一些计算机基础知识，如虚拟地址系统是如何工作的，地址空间是如何切分的，物理页面是如何管理的。做完这个lab将会给JOS添加最基本的内存管理功能，即
Kernel其余模块需要物理页，这个模块可以分配出来。

Lab3为
JOS添加进程的支持、异常/中断的支持、系统调用和页中断的支持。这个lab内容比较多，但收获也比较大，做完后会对从用户态陷入内核态，执行系统调用，然后返回这整个流程都非常清楚（不是泛泛的清楚，而是代码级别的清楚，这是和学概念不同的地方）。

由于考研，准备实习，该项目也就暂时搁浅了。Lab4为
JOS添加多核支持、RR调度、COW的fork、抢占式内核、时钟中断和最基本的IPC机制。Lab6为
JOS添加网络的支持。这两个Lab对我来说，还是有很大的吸引力。日后一定会抠出时间，将它们完成。至于Lab5的文件系统，本人不太感冒。
PS：想想之后
将Dartnet协议栈移植到JOS就激动，先在这挖个大坑吧。

归根结底这只一个课程OS，JOS还有很大的提升空间，离工业级使用还差很多，以下是一些改进点：

JOS和xv6的内存管理方式都是空闲链表，这导致
如果内核想要连续的物理内存，将十分困难，所以linux采用了buddy system来解决碎片问题。

JOS和xv6的进程调度是最简单的RR方式，这使得它们
无法应用在某些特殊的场景下，而且父进程很容易fork子进程把CPU时间全抢了。

打算之后再读读《Linux内核设计与实现》，
发现JOS到底哪里做得不好以及Linux是如何解决的。
最后
感谢开源，在刷Lab的过程中遇到不少的坑，总能从前辈的经验中学习，帮助自己更有方向性的解决问题

参考链接
推荐一门课：6.828

只含1最大的子矩阵

发表于 2017-02-19 | 分类于面试算法 |

问题

定一个无序矩阵,其中只有1和0两种值,求只含有1的最大的子矩阵大小,矩阵的大小用其中的元素个数来表示

阅读全文 »

简单可靠传输协议(SRT)

发表于 2017-02-18 | 分类于 DartNet网络协议栈 |

本篇文章主要介绍简单可靠传输的原理实现，我们只考虑由连接管理使用的控制，其它部分将在另外几篇博文中介绍。为了完成SRT的测试，我们需要编写一个客户端和一个服务器。

就像TCP一样，SRT提供按顺序字节流的可靠传递。这里SRT做出了一些假设，以简化协议的设计和实现。

单向传输，即DATA段从客户端流向接受端

连接管理：客户端发起和断开连接

不支持流量控制或拥塞控制

SRT拥有以下机制

连接管理：连接和断开

校验和用于检测接受的数据是否被破坏

回退N步用于在接收端可靠地传送数据，序列号用于检测丢失的数据和将数据重新排序

重传：客户端使用超时和ACK来重传丢失的数据和控制分组（例如SYN）

API：SRT，SNP和覆盖控制

上一篇博文中，我们看到在DartNet协议栈的不同层之间有许多API。在实现SRT过程中，我们不使用SNP层转发，专注于客户端和服务器的实现与SRT API相关联的一组有限功能。只考虑客户端和服务器之间的连接相关的函数调用。SRT像TCP一样能够支持多个同时连接。我们将讨论数据结构和有限状态机(FSM)需要在本文后面支持这一点。

没有SNP时，SRT直接位于覆盖层上。在这种情况下，覆盖层简单地实现客户端和服务器SRT传输协议之间的TCP连接。我们的覆盖层也只包含客户端和服务器之间的直接TCP连接。

overlay_start（）和 overlay_stop（）函数创建客户端和服务器之间的TCP直接连接。overlay_start（）返回TCP套接字描述符。overlay_stop（）关闭TCP连接。

首先需要实现的是snp _sendseg()和 snp_recvseg（）函数，以使用覆盖层的TCP连接发送和接段
。在TCP数据作为字节流发送的情况下。为了通过覆盖层TCP连接发送数据段，我们需要在字节流中添加分隔符。

在SRT中，使用特殊字符“！＆”表示段的开始，特殊字符“！＃”表示段的结束。这些分隔符不应该出现在客户端和服务之间发送的数据中。这是一个限制（并且如果“！＆”或“！＃”发生在客户端的字节流中，协议将不正确地操作，因此应该确保数据不包括这些特殊控制字符对)。分隔符是必要的，因为STR分组的接收侧（即STR标头+ STR段）需要知道它何时成功接收到SRT分组，这是一种方法。
可能是最简单的方法。

因为覆盖层是从TCP构建的，而不是说UDP，我们没有任何损失。为了允许覆盖看起来像在有损链路上运行，并且分组可以在因特网中丢失，我们在接收到SRT分组时在snp _recvseg()中调用丢失 loss()函数，以丢弃具有概率PROBABILITY_LOSS的分段来模拟分组丢失以迫使SRT恢复丢失的分段，其可以是SRT DATA分组，SYN， SYNACK，FIN和FINACK。 SRT协议必须能够正确地从任何这些数据包的丢失中恢复。

图3：这些是DartNet API函数调用的子集
Lab4 API

功能的流程如下
app_client.c和app_server.c，应用程序层代码首先通过在overlay_start()中的客户端和服务器之间创建一个直接TCP链接来启动覆盖层。在app _client和 app _server中实现overlay_start()。服务器通过调用srt _svr _init()初始化SRT服务器，客户机通过调用srt _client _init()初始化 SRT客户机。

然后服务器调用srt _svr _sock()创建服务器端套接字，srt _svr _accept()接受来自客户端的连接请求（SRT层的控制消息SYN）客户端创建一个套接字，并分别通过调用srt _client _sock() 和 srt _client _connect()连接到服务器套接字。

客户端和服务器在不同端口上建立两个连接，所以SRT可以处理多个连接：服务器创建另一个套接字并等待传入连接，客户端创建另一个套接字并连接到新的服务器套接字。通过这样做，SRT可以同时有多个连接。

客户端在等待时间之后通过为每个连接调用srt _client _disconnect()断开与服务器的连接。最后，服务器通过调用srt _svr _close()关闭套接字，客户端通过调用srt _client _close()关闭套接字。

该app_client和app_server通过调用终止其进程之前停止叠加层over_end()在客户端和服务器。实现了overlay_stop()，而且还实现了srt˙client.c和 srt_server.c中使用的所有SRT 函数。

数据结构

SRT定义了实现将数据控制和分组成段的多个重要数据结构。
SRT分组包括SRT头（参见下面的srt_hdr_t）和SRT段（参见seg_t-数据字节流在这里）。SRT分组被封装到SNP分组中，当我们进入SNP时我们将讨论该SNP分组。注意，SRT报头包括与分组相关联的重要信息，包括例如无符号短整型类型; 。

报头中的type字段定义数据包的类型：

#define  SYN  0 
#define  SYNACK  1 
#define  FIN  2 
#define  FINACK  3 
#define  DATA  4 
#define  DATAACK  5

SRT协议以段为单位发送和接收数据。
图4：段头格式
SRT Segment Header

它在seg.h中定义：

typedef struct srt_hdr {
  unsigned int src_port;        //source port number
  unsigned int dest_port;       //destination port number
  unsigned int seq_num;         //sequence number
  unsigned short int length;    //segment data length
  unsigned short int  type;     //segment type
  unsigned short int  rcv_win;  //currently not used
  unsigned short int checksum;  //currently not used
} srt_hdr_t;
typedef struct segment {
  srt_hdr_t header;
  char data[MAX_SEG_LEN];
} seg_t;

SRT使用传输控制块（TCB）维护与连接相关联的所有状态。对于每个连接，客户端和服务器端初始化并维护TCB。当连接关闭时，TCB返回到未使用的TCB池。下图显示了为每个连接维护的服务器端TCB。当srt _svr _init()和 srt _client _init()分别由server_App 和client_App 调用时，TCB表在启动时在客户端和服务器上初始化。在编码SRT时，始终对数据结构和数据结构表使用malloc()/ free()。

typedef struct svr_tcb {
  unsigned int svr_nodeID;        //node ID of server, similar as IP address
  unsigned int svr_portNum;       //port number of server
  unsigned int client_nodeID;     //node ID of client, similar as IP address
  unsigned int client_portNum;    //port number of client
  unsigned int state;             //state of server
  unsigned int expect_seqNum;     //sequence number of the data seg server is expecting
  char* recvBuf;                  //a pointer pointing to a receive Buffer
  unsigned int  usedBufLen;       //size of received data in receiver buffer
  pthread_mutex_t* bufMutex;      //a pointer pointing to a mutex for receive buffer access
} 
svr_tcb_t;

对于每个连接，SRT客户端维护客户端和服务器TCB

typedef struct client_tcb {
  unsigned int svr_nodeID;        //node ID of server, similar as IP address
  unsigned int svr_portNum;       //port number of server
  unsigned int client_nodeID;     //node ID of client, similar as IP address
  unsigned int client_portNum;    //port number of client
  unsigned int  state;            //state of client
  unsigned int next_seqNum;       //next sequence number
  pthread_mutex_t* bufMutex;      //a pointer pointing to a mutex for send buffer access
  segBuf_t* sendBufHead;          //used by send buffer
  segBuf_t* sendBufunSent;        //used by send buffer
  segBuf_t* sendBufTail;          //used by send buffer
  unsigned int unAck_segNum;      //number of unAcked segments
} client_tcb_t;

连接管理

SRT具有与TCP类似的连接设置和断开。SRT只是使用两次握手。

连接设置
当客户端发送SYN并且服务器用SYNACK响应时建立连接

图5：SRT连接设置
SRT Connection Setup

But life is not that simple: corruption and loss of control messages get in the way

设置和断开时可能发生的以下问题：在SYN中发生丢失或损坏；客户端已经发送，服务器却不知道。这个问题如何解决？如果服务器接收到SYN，在发送SYNACK过程中丢失，会发生什么？

这些异常的解决方案如下：在丢失SYN的情况下，str_client需要设置SYN_TIMEOUT，如果在该周期内没有收到SYN ACK，则它会发送另一个SYN并再次设置定时器。它重复此操作，直到它获得SYNACK或超过SYN_MAX_RETRY。在该状态下，它很可能接收SYN。

SRT连接断开
当客户端发送FIN并且服务器相应地使用FINACK进行响应时，采取（断开）连接

图6：SRT连接断开
SRT SRT Connection Teardown

但是我们可以在这里丢包。在FIN中发生了什么？客户端需要在FIN_TIMEOUT之后发送另一个FIN，直到FIN_MAX_RETRY。如果FINACK丢失会发生什么？客户端必须等待重传FIN_MAX_RETRY以尝试获得FINACK。如果它没有得到FINACK，它在等待期后转换到CLOSE状态，并假定连接有时间以有序的方式关闭。

有限状态机(FSM）

客户端和服务器端实现FSM。
FSM由有限数量的状态组成。状态转换由状态机和EVENT / ACTION控制。基本上,在例如在客户端 FSM上的状态下，例如，假设其处于状态 = SYNSENT并且发生事件 SYN_TIMEOUT,则适当的ACTION 发送SYN。检查客户端FSM，看看是否是这种情况。

客户端FSM
在客户端TCB中在结构的“状态”元素中维护的状态如下：

//states of client
#define CLOSED 1
#define SYNSENT 2
#define CONNECTED 3
#define FINWAIT 4

当实现协议时，您将需要咨询这里所示的状态机，以确定客户端和服务器的状态转换，因为在连接建立和拆除期间交换段。这里SRT服务器状态机如图2所示。8。SRT客户端状态机如图1所示。
SRT客户端FSM
SRT Client FSM

在服务器TCB中在结构的“状态”元素中维护的状态如下：

//states of server
#define CLOSED 1
#define LISTENING 2
#define CONNECTED 3
#define CLOSEWAIT 4

服务器端FSM
SRT Server FSM

DartNet网络协议栈

发表于 2017-02-17 | 分类于 DartNet网络协议栈 |

起因

要想弄懂一个技术，我一贯的学习路线，就去读它的源码，再动手实现它。自己动手主动学习，一点一点地将它搭建起来。一来满足自己的好奇欲，二来本质的深刻理解使我能够更放心地使用它。于是上知乎搜索如何更好的学习TCP/IP协议，就淘到了达特茅斯的lab DartNet，该实验有框架代码。省去很多琐碎的工作。正合我意，撸起袖子开启了网络协议栈的不归路。

我将该项目的所有代码实现托管在github上，传送门 .欢迎start

DartNet介绍

DartNet是一个类TCP/IP协议栈。它的核心是简单可靠传输(SRT)层和简单网络协议 (SNP)层。
Simple Reliable Transport(SRT)实现了运输层TCP的功能，保证数据流的可靠传输。Simple Network Protocol (SNP)实现了网络层IP的功能，完成网络层的两个重要功能：转发和选路。

DartNet整个实验运行起来的框架
DartNet

由于DartNet不能在互联网的路由器上运行我们的代码，为了绕过不能更改路由器代码的限制，于是设计了覆盖网络层(overlap)，在终端系统中构建网络节点作为路由。最终DartNet的简单可靠传输(SRT)层和简单网络协议(SNP)层在构建的覆盖网络层(overlap)上运行，完成DartNet协议栈的测试与实验。

下图所示的DartNet协议栈，客户端和服务器创建套接字来完成两个主机间的数据传输。DartNet是一个自顶向下的分层架构。第n-1层为第n层提供服务和API。SRT为应用程序提供字节流的可靠传送，SNP提供类似于IP的端系统之间的转发和选路。覆盖层运行DartNet堆栈的端主机网络。

DartNet的通信协议栈
DartNet Communications Stack

在DartNet中，每对相邻节点之间存在TCP连接。在每个节点上，存在覆盖网络(overlap)层，简单网络协议(SNP)层，简单可靠传输(SRT)层和应用层

DartNet API函数调用
DartNet API

小结

接下来的几篇文章，会对每一层的功能原理，以及数据结构进行相关的介绍。上图中的API函数将在对应层一一实现。

DartNet网络协议栈

发表于 2017-02-17 | 分类于 DartNet网络协议栈 |

起因

我将该项目的所有代码实现托管在github上，传送门 .欢迎start

DartNet介绍

DartNet整个实验运行起来的框架
DartNet

DartNet的通信协议栈
DartNet Communications Stack

在DartNet中，每对相邻节点之间存在TCP连接。在每个节点上，存在覆盖网络(overlap)层，简单网络协议(SNP)层，简单可靠传输(SRT)层和应用层

DartNet API函数调用
DartNet API

小结

接下来的几篇文章，会对每一层的功能原理，以及数据结构进行相关的介绍。上图中的API函数将在对应层一一实现。

子矩阵的最大和

发表于 2017-02-12 | 分类于面试算法 |

问题

给定一个无序矩阵,其中有正,有负,有 0,求子矩阵的最大和

阅读全文 »

Shaojie Li

学习总结思考感悟知识管理

107 日志

15 分类

15 标签

RSS