关于有限状态机的一点应用

有限状态机，一种抽象的理论模型。

有限状态机**(Finite State Machine)**通过可构造、可验证的方式来呈现有限个变量所描述的状态变化过程。比如，封闭的有向图。它可以通过if-else, switch-case和函数指针来实现，从软件工程角度看，主要是为了封装逻辑。

带有状态转移的有限状态机示例:

STATE_MACHINE() {
    State cur_State = type_A;
    while (cur_State != type_C) {
        Package _pack = getNewPackage();
        switch() {
            case type_A:
                process_pkg_state_A(_pack);
                cur_State = type_B;
                break;
            case type_B:
                process_pkg_state_B(_pack);
                cur_State = type_C;
                break;
        }
    }
}

该状态机包含三种状态：type_A，type_B和type_C。其中，type_A是初始状态，type_C是结束状态。状态机的当前状态记录在cur_State变量中，逻辑处理时，状态机先通过getNewPackage获取数据包，然后根据当前状态对数据进行处理，处理完后，状态机通过改变cur_State完成状态转移。

有限状态机是一种逻辑单元内部的高效编程方法，在服务器编程中，服务器可以根据不同状态或者消息类型进行相应的处理逻辑，使得程序逻辑清晰易懂。

基于状态机来处理webserver http报文

http报文处理流程：

• 浏览器端发出http连接请求，主线程创建http对象接收请求并将所有数据读入对应buffer，将该对象插入任务队列，工作线程从任务队列中取出一个任务进行处理。
• 工作线程取出任务后，调用process_read函数，通过主、从状态机对请求报文进行解析。
• 解析完之后，跳转do_request函数生成响应报文，通过process_write写入buffer，返回给浏览器端。

定义http类

class http_conn {
    public:
        // 设置读取文件的名称m_real_file大小
        static const int FILENAME_LEN=200;
        // 设置读缓冲区m_read_buf大小
        static const int READ_BUFFER_SIZE=2048;
        // 设置写缓冲区m_write_buf大小
        static const int WRITE_BUFFER_SIZE=1024;
        // 报文的请求方法
        enum METHOD{GET=0, POST, HEAD, PUT, DELETE, TRACE, OPTIONS, CONNECT, PATH};
        // 主状态机的状态
        enum CHECK_STATE{CHECK_STATE_REQUESTLINE=0, CHECK_STATE_HEADER, CHECK_STATE_CONTENT};
        // 报文解析的结果
        enum HTTP_CODE {NO_REQUEST, GET_REQUEST, BAD_REQUEST, NO_RESOURCE, FORBIDDEN_REQUEST, FILE_REQUEST, INTERNAL_ERROR, CLOSED_CONNECTION};
        //从状态机的状态
        enum LINE_STATUS{LINE_OK=0, LINE_BAD, LINE_OPEN};

    public:
        http_conn(){}
        ~http_conn(){}

    public:
        // 初始化套接字地址，函数内部会调用私有方法init
        void init(int sockfd, const sockaddr_in &addr);
        // 关闭http连接
        void close_conn(bool real_close = true);
        void process();
        // 读取浏览器端发来的全部数据
        bool read_once();
        // 响应报文写入函数
        bool write();
        sockaddr_in *get_address() {
            return &m_address;  
        }
        // 同步线程初始化数据库读取表
        void initmysql_result();
        // CGI使用线程池初始化数据库表
        void initresultFile(connection_pool *connPool);

    private:
        void init();
        // 从m_read_buf读取，并处理请求报文
        HTTP_CODE process_read();
        // 向m_write_buf写入响应报文数据
        bool process_write(HTTP_CODE ret);
        // 主状态机解析报文中的请求行数据
        HTTP_CODE parse_request_line(char *text);
        // 主状态机解析报文中的请求头数据
        HTTP_CODE parse_headers(char *text);
        // 主状态机解析报文中的请求内容
        HTTP_CODE parse_content(char *text);
        // 生成响应报文
        HTTP_CODE do_request();

        // m_start_line是已经解析的字符
        // get_line用于将指针向后偏移，指向未处理的字符
        char* get_line() { return m_read_buf + m_start_line; };

        // 从状态机读取一行，分析是请求报文的哪一部分
        LINE_STATUS parse_line();

        void unmap();

        // 根据响应报文格式，生成对应8个部分，以下函数均由do_request调用
        bool add_response(const char* format, ...);
        bool add_content(const char* content);
        bool add_status_line(int status, const char* title);
        bool add_headers(int content_length);
        bool add_content_type();
        bool add_content_length(int content_length);
        bool add_linger();
        bool add_blank_line();

    public:
        static int m_epollfd;
        static int m_user_count;
        MYSQL *mysql;

    private:
        int m_sockfd;
        sockaddr_in m_address;

        // 存储读取的请求报文数据
        char m_read_buf[READ_BUFFER_SIZE];
        // 缓冲区中m_read_buf中数据的最后一个字节的下一个位置
        int m_read_idx;
        // m_read_buf读取的位置m_checked_idx
        int m_checked_idx;
        // m_read_buf中已经解析的字符个数
        int m_start_line;

        // 存储发出的响应报文数据
        char m_write_buf[WRITE_BUFFER_SIZE];
        // 指示buffer中的长度
        int m_write_idx;

        // 主状态机的状态
        CHECK_STATE m_check_state;
        // 请求方法
        METHOD m_method;

        // 以下为解析请求报文中对应的6个变量
        // 存储读取文件的名称
        char m_real_file[FILENAME_LEN];
        char *m_url;
        char *m_version;
        char *m_host;
        int m_content_length;
        bool m_linger;

        char *m_file_address;        // 读取服务器上的文件地址
        struct stat m_file_stat;
        struct iovec m_iv[2];        // io向量机制iovec
        int m_iv_count;
        int cgi;                     // 是否启用的POST
        char *m_string;              // 存储请求头数据
        int bytes_to_send;           // 剩余发送字节数
        int bytes_have_send;         // 已发送字节数
};

报文解析流程

void http_conn::process() {
    HTTP_CODE read_ret = process_read();

    // NO_REQUEST，表示请求不完整，需要继续接收请求数据
    if (read_ret == NO_REQUEST) {
        // 注册并监听读事件
        modfd(m_epollfd, m_sockfd, EPOLLIN);
        return;
    }

    // 调用process_write完成报文响应
    bool write_ret=process_write(read_ret);
    if (!write_ret) {
        close_conn();
    }
    // 注册并监听写事件
    modfd(m_epollfd, m_sockfd, EPOLLOUT);
}

process_read通过while循环，将主从状态机进行封装，对报文的每一行进行循环处理。

• 判断条件

  • 主状态机转移到CHECK_STATE_CONTENT，该条件涉及解析消息体
  • 从状态机转移到LINE_OK，该条件涉及解析请求行和请求头部
  • 两者为或关系，当条件为真则继续循环，否则退出

• 循环体

  • 从状态机读取数据
  • 调用get_line函数，通过m_start_line将从状态机读取数据间接赋给text
  • 主状态机解析text

// m_start_line是行在buffer中的起始位置，将该位置后面的数据赋给text
// 此时从状态机已提前将一行的末尾字符\r\n变为\0\0，所以text可以直接取出完整的行进行解析
char* get_line() {
    return m_read_buf + m_start_line;
}


http_conn::HTTP_CODE http_conn::process_read() {
    // 初始化从状态机状态、HTTP请求解析结果
    LINE_STATUS line_status = LINE_OK;
    HTTP_CODE ret = NO_REQUEST;
    char* text=0;

    // 这里为什么要写两个判断条件？第一个判断条件为什么这样写？
    // 具体的在主状态机逻辑中会讲解。

    // parse_line为从状态机的具体实现
    while ((m_check_state == CHECK_STATE_CONTENT && line_status == LINE_OK) || ((line_status = parse_line()) == LINE_OK)) {
        text = get_line();

        // m_start_line是每一个数据行在m_read_buf中的起始位置
        // m_checked_idx表示从状态机在m_read_buf中读取的位置
        m_start_line = m_checked_idx;

        // 主状态机的三种状态转移逻辑
        switch (m_check_state) {
            case CHECK_STATE_REQUESTLINE: {
                //解析请求行
                ret = parse_request_line(text);
                if (ret == BAD_REQUEST)
                    return BAD_REQUEST;
                break;
            }
            case CHECK_STATE_HEADER: {
                // 解析请求头
                ret = parse_headers(text);
                if (ret == BAD_REQUEST)
                    return BAD_REQUEST;

                // 完整解析GET请求后，跳转到报文响应函数
                else if (ret == GET_REQUEST) {
                    return do_request();
                }
                break;
            }
            case CHECK_STATE_CONTENT: {
                // 解析消息体
                ret = parse_content(text);

                // 完整解析POST请求后，跳转到报文响应函数
                if (ret == GET_REQUEST)
                    return do_request();

                // 解析完消息体即完成报文解析，避免再次进入循环，更新line_status
                line_status = LINE_OPEN;
                break;
            }
            default:
            return INTERNAL_ERROR;
        }
    }
    return NO_REQUEST;
}

从状态机逻辑：

在HTTP报文中，每一行的数据由\r\n作为结束字符，空行则是仅仅是字符\r\n。因此，可以通过查找\r\n将报文拆解成单独的行进行解析。从状态机负责读取buffer中的数据，将每行数据末尾的\r\n置为\0\0，并更新从状态机在buffer中读取的位置m_checked_idx，以此来驱动主状态机解析。

• 从状态机从m_read_buf中逐字节读取，判断当前字节是否为\r

  • 接下来的字符是\n，将\r\n修改成\0\0，将m_checked_idx指向下一行的开头，则返回LINE_OK
  • 接下来达到了buffer末尾，表示buffer还需要继续接收，返回LINE_OPEN
  • 否则，表示语法错误，返回LINE_BAD

• 当前字节不是\r，判断是否是\n（一般是上次读取到\r就到了buffer末尾，没有接收完整，再次接收时会出现这种情况）

  • 如果前一个字符是\r，则将\r\n修改成\0\0，将m_checked_idx指向下一行的开头，则返回LINE_OK

• 当前字节既不是\r，也不是\n

  • 表示接收不完整，需要继续接收，返回LINE_OPEN

// 从状态机，用于分析出一行内容
// 返回值为行的读取状态，有LINE_OK,LINE_BAD,LINE_OPEN

// m_read_idx指向缓冲区m_read_buf的数据末尾的下一个字节
// m_checked_idx指向从状态机当前正在分析的字节
http_conn::LINE_STATUS http_conn::parse_line() {
    char temp;
    for (; m_checked_idx < m_read_idx; ++m_checked_idx) {
        //temp为将要分析的字节
        temp = m_read_buf[m_checked_idx];

        // 如果当前是\r字符，则有可能会读取到完整行
        if (temp == '\r') {

            // 下一个字符达到了buffer结尾，则接收不完整，需要继续接收
            if ((m_checked_idx + 1) == m_read_idx)
                return LINE_OPEN;
            // 下一个字符是\n，将\r\n改为\0\0
            else if (m_read_buf[m_checked_idx + 1] == '\n') {
                m_read_buf[m_checked_idx++] = '\0';
                m_read_buf[m_checked_idx++] = '\0';
                return LINE_OK;
            }
            // 如果都不符合，则返回语法错误
            return LINE_BAD;
        }

        // 如果当前字符是\n，也有可能读取到完整行
        // 一般是上次读取到\r就到buffer末尾了，没有接收完整，再次接收时会出现这种情况
        else if (temp == '\n') {
            // 前一个字符是\r，则接收完整
            if (m_checked_idx > 1 && m_read_buf[m_checked_idx - 1] == '\r') {
                m_read_buf[m_checked_idx-1] = '\0';
                m_read_buf[m_checked_idx++] = '\0';
                return LINE_OK;
            }
            return LINE_BAD;
        }
    }

    // 并没有找到\r\n，需要继续接收
    return LINE_OPEN;
}

主状态机逻辑

主状态机初始状态是CHECK_STATE_REQUESTLINE，通过调用从状态机来驱动主状态机，在主状态机进行解析前，从状态机已经将每一行的末尾\r\n符号改为\0\0，以便于主状态机直接取出对应字符串进行处理。

• CHECK_STATE_REQUESTLINE
  • 主状态机的初始状态，调用parse_request_line函数解析请求行
  • 解析函数从m_read_buf中解析HTTP请求行，获得请求方法、目标URL及HTTP版本号
  • 解析完成后主状态机的状态变为CHECK_STATE_HEADER

// 解析http请求行，获得请求方法，目标url及http版本号
http_conn::HTTP_CODE http_conn::parse_request_line(char *text) {
    // 在HTTP报文中，请求行用来说明请求类型,要访问的资源以及所使用的HTTP版本，其中各个部分之间通过\t或空格分隔。
    // 请求行中最先含有空格和\t任一字符的位置并返回
    m_url = strpbrk(text," \t");

    // 如果没有空格或\t，则报文格式有误
    if (!m_url) {
        return BAD_REQUEST;
    }

    // 将该位置改为\0，用于将前面数据取出
    *m_url++ = '\0';

    // 取出数据，并通过与GET和POST比较，以确定请求方式
    char *method = text;
    if (strcasecmp(method, "GET") == 0)
        m_method = GET;
    else if (strcasecmp(method, "POST") == 0) {
        m_method = POST;
        cgi = 1;
    }
    else
        return BAD_REQUEST;

    // m_url此时跳过了第一个空格或\t字符，但不知道之后是否还有
    // 将m_url向后偏移，通过查找，继续跳过空格和\t字符，指向请求资源的第一个字符
    m_url += strspn(m_url, " \t");

    // 使用与判断请求方式的相同逻辑，判断HTTP版本号
    m_version = strpbrk(m_url, " \t");
    if (!m_version)
        return BAD_REQUEST;
    *m_version++ = '\0';
    m_version += strspn(m_version, " \t");

    // 仅支持HTTP/1.1
    if (strcasecmp(m_version, "HTTP/1.1") != 0)
        return BAD_REQUEST;

    // 对请求资源前7个字符进行判断
    // 这里主要是有些报文的请求资源中会带有http://，这里需要对这种情况进行单独处理
    if (strncasecmp(m_url, "http://",7) == 0) {
        m_url += 7;
        m_url = strchr(m_url, '/');
    }

    // 同样增加https情况
    if (strncasecmp(m_url, "https://", 8) == 0) {
        m_url += 8;
        m_url = strchr(m_url, '/');
    }

    // 一般的不会带有上述两种符号，直接是单独的/或/后面带访问资源
    if (!m_url || m_url[0] != '/')
        return BAD_REQUEST;

    // 当url为/时，显示欢迎界面
    if (strlen(m_url) == 1)
        strcat(m_url, "judge.html");

    // 请求行处理完毕，将主状态机转移处理请求头
    m_check_state = CHECK_STATE_HEADER;
    return NO_REQUEST;
}

解析请求头

// 解析http请求的一个头部信息
http_conn::HTTP_CODE http_conn::parse_headers(char *text) {
    // 判断是空行还是请求头
    if (text[0] == '\0') {
        // 判断是GET还是POST请求
        if (m_content_length != 0) {
            // POST需要跳转到消息体处理状态
            m_check_state = CHECK_STATE_CONTENT;
            return NO_REQUEST;
        }
        return GET_REQUEST;
    }
    // 解析请求头部连接字段
    else if (strncasecmp(text, "Connection:", 11) == 0) {
        text += 11;

        // 跳过空格和\t字符
        text += strspn(text, " \t");
        if (strcasecmp(text, "keep-alive") == 0) {
            // 如果是长连接，则将linger标志设置为true
            m_linger = true;
        }
    }
    // 解析请求头部内容长度字段
    else if (strncasecmp(text, "Content-length:", 15) == 0) {
        text += 15;
        text += strspn(text," \t");
        m_content_length = atol(text);
    }
    // 解析请求头部HOST字段
    else if (strncasecmp(text, "Host:", 5) == 0) {
        text += 5;
        text += strspn(text, " \t");
        m_host = text;
    } else {
        printf("oop!unknow header: %s\n", text);
    }
    return NO_REQUEST;
}

解析消息体

// 判断http请求是否被完整读入
http_conn::HTTP_CODE http_conn::parse_content(char *text) {
    // 判断buffer中是否读取了消息体
    if (m_read_idx >= (m_content_length + m_checked_idx)) {

        text[m_content_length]='\0';

        // POST请求中最后为输入的用户名和密码
        m_string = text;

        return GET_REQUEST;
    }
    return NO_REQUEST;
}