代码编织梦想

有限状态机

  • 相关来源及参考-部分在具体模块有指明
  • 《Linux高性能服务器编程》-游双

定义

  • 维基百科:

image-20221003121825834

  • 在编程中有限状态机(finite state)是服务器程序逻辑单元内部的一种高效编程方法。
    • 个人理解为控制程序执行的一个变量或是一段程序,根据这个变量或是程序的有限结果进行对应的操作。
  • 有的应用层协议头部包含数据包类型字段,每种类型可以映射为逻辑单元的一种执行状态,服务器可以根据它来编写相应的处理逻辑,如下所示代码:
STATE_MACHINE(Package _pack){
    PackageType _type = _pack.GetType();
    switch(_type){
        case type_A:
            process_package_A(_pack);
            break;
        case tyoe_B:
            process_package_A(_pack);
            break;
    }
}
  • 如上所示,一个简单的有限状态机,只不过其中的每种状态都是相互独立的 ,状态之前没有相互转移,状态转移需要状态机内部驱动。
  • 如下所示一个带状态转移的有限状态机示例:
STATE_MACHINE(Package _pack){
    State cur_State = type_A;
    while(cur_State != type_c){
     	PackageType _type = _pack.GetType();   
        switch(cur_State){
            case type_A:
                process_package_state_A(_pack);
                cur_State = type_B;
                break;
            case type_B:
                process_package_state_B(_pack);
                cur_State = type_c;
                break;
            default:
                break;
        }
    } 
}
  • 解释:
  • 状态机先通过getNewPackage方法获得一个新的数据包,然后根据cur_State变量的值判断如何处理该数据包,处理完整后cur_State将被赋予新的值来实现状态转移,当状态机进入下一趟循环后,它会执行新的状态对应的处理逻辑

示例

  • 有限状态机的一个应用实例——HTTP请求的读取和分析
  • HTTP协议并未提供头部长度字段,并且头部长度的变化也很大。
    • 根据协议规定(如下图所示),我们判断HTTP头部结束的依据是遇到一个空行,该空行仅包含一对回车换行符,如果一次读操作没有读入HTTP请求的整个头部,即没有遇到空行,那么我们需要继续等待数据发送并读入。
    • 每完成一次读操作,就要判断有没空行(空行前面是请求行和头部域),同时可以完成对整个HTTP请求头部的分析。
  • 如下代码中,我们使用主从两个状态机来实现简单的HTTP请求的读取与分析。
  • 我们称一行HTTP请求报文为一行。

image-20221003105255512


主状态机

  • 主状态机负责进行请求行与头部字段的的判断,调用相关函数进行处理。
  • 在处理完请求行后,状态转移,进行处理头部字段。
  • 主状态机使用checkstate来记录当前状态,初识状态为CHECK_STATE_REQUESTLINE(分析请求行),调用parse_line先获取请求行的数据,然后调用parse_requestline进行分析,之后将状态改为(状态转义)CHECK_STATE_HEADER(头部字段分析),调用parse_line获取行数据,调用parse_headers进行解析。
  • 即,可以理解为,在调用parse_line解析一行数据之前,我们已经知道这行数据是什么类型的了(请求行数据or头部字段数据)。
// 主状态机-分析http请求的入口函数
HTTP_CODE parse_content( char* buffer, int& checked_index, CHECK_STATE& checkstate, int& read_index, int& start_line ){

    LINE_STATUS linestatus = LINE_OK;// 从状态机状态
    HTTP_CODE retcode = NO_REQUEST;
    // 如果没读到头,就继续处理。
    while( ( linestatus = parse_line( buffer, checked_index, read_index ) ) == LINE_OK ){// 一行一行开始解析

        // 成功读全了一行, 进入到这里
        char* szTemp = buffer + start_line;// start_index是在buffer中的起始位置
        start_line = checked_index;// 更新下标,下一行的起始位置。
        switch ( checkstate ){// 主状态机的当前状态
            case CHECK_STATE_REQUESTLINE:{// 分析请求行-get/post...
                retcode = parse_requestline( szTemp, checkstate );// 处理http请求的结果
                if ( retcode == BAD_REQUEST ){
                    return BAD_REQUEST;
                }
                break;
            }
            case CHECK_STATE_HEADER:{// 分析头部字段
                retcode = parse_headers( szTemp );// 每次读取到的数据是会更新的。
                if ( retcode == BAD_REQUEST ){
                    return BAD_REQUEST;
                }
                else if ( retcode == GET_REQUEST )
                {
                    return GET_REQUEST;
                }
                break;
            }
            default:    // 报错
            {
                return INTERNAL_ERROR;
            }
        }
    }
    if( linestatus == LINE_OPEN ){// 没有读取到完整的一行
        return NO_REQUEST;  // 返回请求不完整
    }
    else{
        return BAD_REQUEST;// 客户请求有语法错误
    }
}

从状态机

  • 从状态机负责解析出一行的内容。
// 从状态机,用于解析出一行的内容。
LINE_STATUS parse_line( char* buffer, int& checked_index, int& read_index )
{
    // read_index指向buffer中当前分析数据的下一个字节
    // checked_index指向buffer中当前分析数据中正在分析的字节
    // 也就是说这里分析的是checked_index~read_index中的数据
    // 逐字节分析
    char temp;
    for ( ; checked_index < read_index; ++checked_index )
    {
        temp = buffer[ checked_index ];// 拿到当前要分析的字节(字符)
        if ( temp == '\r' ){// 当前为\r说明可能读取到一个完整的行
        /*
            如果\r是当前已经读到的数据的最后一个,说明当前还没有读取到一个完整行,
            需要继续读取客户端数据才能进一步分析。
        */
            if ( ( checked_index + 1 ) == read_index ){
                return LINE_OPEN;// 返回数据不完整
            }
            // 下一个就是\n,说明我们读取到了一个完整的行。
            else if ( buffer[ checked_index + 1 ] == '\n' ){
                buffer[ checked_index++ ] = '\0';// 添加字符串结束符
                buffer[ checked_index++ ] = '\0';
                // 读取到完整的一行,准备交给主状态机进行处理
                return LINE_OK;// 读取到完整的一行
            }
            return LINE_BAD;// 否则返回当前行数据出错
        }
        else if( temp == '\n' ){//当前的字符是\n,说明也可能读到一个完整的行
            // 进一步判断
            if( ( checked_index > 1 ) &&  buffer[ checked_index - 1 ] == '\r' ){
                buffer[ checked_index-1 ] = '\0';
                buffer[ checked_index++ ] = '\0';
                return LINE_OK; // 是完整行
            }
            return LINE_BAD;// 行出错
        }
    }
    return LINE_OPEN;// 行数据不完整
}

完整代码

#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <fcntl.h>

#define BUFFER_SIZE 4096 // 读缓冲区大小

// 主状态机的2种可能状态
enum CHECK_STATE { 
    CHECK_STATE_REQUESTLINE = 0,  // 分析请求行
    CHECK_STATE_HEADER,           // 分析头部字段
   //CHECK_STATE_CONTENT          
};

// 从状态机的3种可能状态——行的读取状态
enum LINE_STATUS { 
    LINE_OK = 0,      // 读取到一个完整的行
    LINE_BAD,         // 行出错
    LINE_OPEN         // 行的数据尚不完整,就是还没到/r/n的/n
};

// 服务器处理http请求的结果,
enum HTTP_CODE {
    NO_REQUEST,       // 请求不完整,需要继续读取客户数据
    GET_REQUEST,      // 获得了一个完整的客户请求
    BAD_REQUEST,      // 客户请求有语法错误
    FORBIDDEN_REQUEST,// 客户对资源没有足够的权限访问
    INTERNAL_ERROR,   // 服务器内部错误
    CLOSED_CONNECTION // 客户端已经关闭连接
};

// 为了简化问题,本代码没有给客户端发送一个完整的HTTP应答报文,而只是根据服务器的处理结果发送如下成功or失败信息。
static const char* szret[] = { 
    "I get a correct result\n", 
    "Something wrong\n" 
};


// 从状态机,用于解析出一行的内容。
LINE_STATUS parse_line( char* buffer, int& checked_index, int& read_index )
{
    // read_index指向buffer中当前分析数据的下一个字节
    // checked_index指向buffer中当前分析数据中正在分析的字节
    // 也就是说这里分析的是checked_index~read_index中的数据
    // 逐字节分析
    char temp;
    for ( ; checked_index < read_index; ++checked_index )
    {
        temp = buffer[ checked_index ];// 拿到当前要分析的字节(字符)
        if ( temp == '\r' ){// 当前为\r说明可能读取到一个完整的行
        /*
            如果\r是当前已经读到的数据的最后一个,说明当前还没有读取到一个完整行,
            需要继续读取客户端数据才能进一步分析。
        */
            if ( ( checked_index + 1 ) == read_index ){
                return LINE_OPEN;// 返回数据不完整
            }
            // 下一个就是\n,说明我们读取到了一个完整的行。
            else if ( buffer[ checked_index + 1 ] == '\n' ){
                buffer[ checked_index++ ] = '\0';// 添加字符串结束符
                buffer[ checked_index++ ] = '\0';
                // 读取到完整的一行,准备交给主状态机进行处理
                return LINE_OK;// 读取到完整的一行
            }
            return LINE_BAD;// 否则返回当前行数据出错
        }
        else if( temp == '\n' ){//当前的字符是\n,说明也可能读到一个完整的行
            // 进一步判断
            if( ( checked_index > 1 ) &&  buffer[ checked_index - 1 ] == '\r' ){
                buffer[ checked_index-1 ] = '\0';
                buffer[ checked_index++ ] = '\0';
                return LINE_OK; // 是完整行
            }
            return LINE_BAD;// 行出错
        }
    }
    return LINE_OPEN;// 行数据不完整
}

// 分析请求行-格式: GET /index.html HTTP/1.1
HTTP_CODE parse_requestline( char* szTemp, CHECK_STATE& checkstate ){

    // szTemp = 
    // printf("test: %s\n",szTemp);
    // szTemp中搜索\t,找到返回所在位置的指针
    /*
        一开始没有想好这个\t是什么意思,详见http请求报文。
        \t就是空格
    */ 
    char* szURL = strpbrk( szTemp, " \t" );

    if ( ! szURL ){ // 请求行中没有空白字符或\t字符,则HTTP请求必有问题。
        return BAD_REQUEST;// 请求中有语法错误
    }
    *szURL++ = '\0';// 将\t用\0覆盖,然后++指针,指向后面的内容。
    // 此时szURL内容为/index.html HTTP/1.1

    char* szMethod = szTemp;// 保存请求的方法,到\0会被截断。
    if ( strcasecmp( szMethod, "GET" ) == 0 ){// 判断get请求
        printf( "The request method is: GET\n" );
    }else{
        return BAD_REQUEST; // 返回请求错误
    }
    
    // 下一条请求头
    // 跳过下一部分数据前面多余的空格
    szURL += strspn( szURL, " \t" );
    // 先拿到http版本,跳过了/index.html
    char* szVersion = strpbrk( szURL, " \t" );
    if ( ! szVersion ){
        return BAD_REQUEST;
    }
    *szVersion++ = '\0';// 将\t替换为\0,

    // 跳过下一部分数据前面多余的空格
    // 此时szVersion = HTTP/1.1
    
    //跳过http/1.1信息前面多余的空格
    szVersion += strspn( szVersion, " \t" );
    // 为什么这里没有长度限制了,因为请求行最后一段就是http版本
    // 是否为http/1.1
    if ( strcasecmp( szVersion, "HTTP/1.1" ) != 0 ){
        return BAD_REQUEST;
    }
    // 回头来检查url是否合法
    if ( strncasecmp( szURL, "http://", 7 ) == 0 ){
        szURL += 7;
        szURL = strchr( szURL, '/' );
    }

    if ( ! szURL || szURL[ 0 ] != '/' ){
        return BAD_REQUEST;
    }

    //URLDecode( szURL );
    printf( "The request URL is: %s\n", szURL );

    // http请求行处理完毕,状态转移到头部字段分析。
    checkstate = CHECK_STATE_HEADER;
    return NO_REQUEST;// 当前返回NO_REQUEST无意义。
}

// 分析头部字段
HTTP_CODE parse_headers( char* szTemp ){
    if ( szTemp[ 0 ] == '\0' ){// 遇到空行说明我们得到了一个正确的http请求,在头部最后,还有一个空行。
        printf("test\n");
        return GET_REQUEST;
    }
    else if ( strncasecmp( szTemp, "Host:", 5 ) == 0 ){
        szTemp += 5;
        szTemp += strspn( szTemp, " \t" );
        printf( "the request host is: %s\n", szTemp );
    }
    else{// 其它头部信息
        //printf( "I can not handle this header\n" );
        printf("%s\n",szTemp);
    }

    return NO_REQUEST;
}


// 分析http请求的入口函数-从这里开始进行处理
/*

        接收缓冲区
        当前已经分析完了多少字节的数据
        主状态机的初始状态
        当前已经读取了多少字节的数据
        接收缓冲区中的起始位置

*/

// 主状态机-分析http请求的入口函数
HTTP_CODE parse_content( char* buffer, int& checked_index, CHECK_STATE& checkstate, int& read_index, int& start_line ){

    LINE_STATUS linestatus = LINE_OK;// 从状态机状态
    HTTP_CODE retcode = NO_REQUEST;
    // 如果没读到头,就继续处理。
    while( ( linestatus = parse_line( buffer, checked_index, read_index ) ) == LINE_OK ){// 一行一行开始解析

        // 成功读全了一行, 进入到这里
        char* szTemp = buffer + start_line;// start_index是在buffer中的起始位置
        start_line = checked_index;// 更新下标,下一行的起始位置。
        switch ( checkstate ){// 主状态机的当前状态
            case CHECK_STATE_REQUESTLINE:{// 分析请求行-get/post...
                retcode = parse_requestline( szTemp, checkstate );// 处理http请求的结果
                if ( retcode == BAD_REQUEST ){
                    return BAD_REQUEST;
                }
                break;
            }
            case CHECK_STATE_HEADER:{// 分析头部字段
                retcode = parse_headers( szTemp );// 每次读取到的数据是会更新的。
                if ( retcode == BAD_REQUEST ){
                    return BAD_REQUEST;
                }
                else if ( retcode == GET_REQUEST )
                {
                    return GET_REQUEST;
                }
                break;
            }
            default:    // 报错
            {
                return INTERNAL_ERROR;
            }
        }
    }
    if( linestatus == LINE_OPEN ){// 没有读取到完整的一行
        return NO_REQUEST;  // 返回请求不完整
    }
    else{
        return BAD_REQUEST;// 客户请求有语法错误
    }
}

int main( int argc, char* argv[] ){

    if( argc <= 2 ){
        printf( "usage: %s ip_address port_number\n", basename( argv[0] ) );
        return 1;
    }

    const char* ip = argv[1];   
    int port = atoi( argv[2] );
    
    struct sockaddr_in address;
    bzero( &address, sizeof( address ) );
    address.sin_family = AF_INET;
    inet_pton( AF_INET, ip, &address.sin_addr );
    address.sin_port = htons( port );
    
    int listenfd = socket( PF_INET, SOCK_STREAM, 0 );
    assert( listenfd >= 0 );
    
    int ret = bind( listenfd, ( struct sockaddr* )&address, sizeof( address ) );
    assert( ret != -1 );
    
    ret = listen( listenfd, 5 );
    assert( ret != -1 );
    
    struct sockaddr_in client_address;
    socklen_t client_addrlength = sizeof( client_address );
    int fd = accept( listenfd, ( struct sockaddr* )&client_address, &client_addrlength );
    if( fd < 0 ){
        printf( "errno is: %d\n", errno );
    }
    else{
        char buffer[ BUFFER_SIZE ];             // 接收缓冲区
        memset( buffer, '\0', BUFFER_SIZE );
        int data_read = 0;                    
        int read_index = 0;                     // 当前已经读取了多少字节的客户数据
        int checked_index = 0;                  // 当前已经分析完了多少字节的客户数据
        int start_line = 0;                     // 在接收缓冲区中的起始位置

        CHECK_STATE checkstate = CHECK_STATE_REQUESTLINE;   // 设置主状态机的初识状态-分析请求行
        while( 1 ){// 循环读取数据并进行分析

            data_read = recv( fd, buffer + read_index, BUFFER_SIZE - read_index, 0 );
            if ( data_read == -1 ){
                printf( "reading failed\n" );
                break;
            }
            else if ( data_read == 0 ){
                printf( "remote client has closed the connection\n" );
                break;
            }
    
            read_index += data_read;// 更新当前读取数据的数量
            HTTP_CODE result = parse_content( buffer, checked_index, checkstate, read_index, start_line );// 
            if( result == NO_REQUEST ){// 继续读取数据
                continue;
            }else if( result == GET_REQUEST ){// 获得了一个完整的客户请求
                send( fd, szret[0], strlen( szret[0] ), 0 );
                break;
            }else{// 错误
                send( fd, szret[1], strlen( szret[1] ), 0 );
                break;
            }
        }
        close( fd );
    }
    
    close( listenfd );
    return 0;
}


补充与解释

  • 我们在主状态机内部调用从状态机,使用从状态机解析一行数据,其可能的状态与状态转移如下图所示:

image-20221003113025361

  • 使用read_index、checked_index、start_line、data_read来控制buffer中的数据读取范围。详见代码中的注释。
  • 主状态机可能的状态以及状态转义如下图所示:

image-20221003113630471

  • 大致执行流程如下图所示,循环判断等详细信息并未体现。

image-20221003113747616


相关函数补充

strpbrk

  • 功能: 查找字符串s中第一个出现的指定字符串accept。
  • 函数原型:
#include <string.h>
char *strpbrk(const char *s, const char *accept);

strcasecmp

  • 功能: 比较两个字符串(忽略大小写),
  • 函数原型:
#include <string.h>
int strcasecmp (const char *s1, const char *s2);
  • 返回值:
  • 相等: 返回0.
  • 不等: s1大于s2返回大于0,s1小于s2返回小于0。
  • 相关参考: 百度百科

strspn

  • 作用: 检索str1中第一个不在str2中出现的字符下标。
  • 函数原型:
size_t strspn(const char *str1, const char *str2)
  • 返回值: 返回str1中第一个不在字符串str2中出现的字符下标。
  • 相关参考: 菜鸟教程

补充

char* test = "abcdefg";
*test = 'z'; // 是错误的,默认为字符串常量,理解为只读。

// 实际上被编译器解析为常量指针,const  char* test;
// 为什么本代码中的就可以修改,因为szTemp是指向buffer的!

// 按照书写的顺序方便记忆
// const type* xx常量指针(指向常量的指针)指向的内容无法修改,但是指向的地址可以改变。
// type* const xx指针常量(指针是个常量),指向的内容可以修改,指向的地址不能改变。
/*
直接用char*创建的字符串,其实是常量指针,例如char* c1 = "test";实际上是const char* c1 = "test";无法修改其中指向的内容,要是用指针修改字符串,实际上应该为char c1[],即char类型数组,或char*指向一个char类型数组。
*/
  • 通过使用指针,‘\0’进行字符串截断。
// szTemp: GET /index.html HTTP/1.1
// szTemp中搜索\t,找到返回所在位置的指针
char* szURL = strpbrk( szTemp, " \t" );
if (!szURL )return BAD_REQUEST;
*szURL++ = '\0';// 将\t用\0覆盖,然后++指针,指向后面的内容。
char* szMethod = szTemp;// 保存请求的方法,到\0会被截断。
// szMethod: GET

由于多平台发布,发布后如果出现错误或是修改,可能无法及时更新所有平台内容,可在我的个人博客获取最新文章——半生瓜のblog

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_51604330/article/details/127151012

tcp有限状态机转换-爱代码爱编程

注:主动、被动与服务器、客户端没有明确的对应关系。 每个连接均开始于CLOSED状态。当一方执行了被动的连接原语(LISTEN)或主动的连接原语(CONNECT)时,它便会脱离CLOSED状态。如果此时另一方执行了相对

socket 返回状态码_sstnba的博客-爱代码爱编程_socket状态码

#define EPERM 1 // Operation not permitted 操作不允许 #define ENOENT 2 // No such file or directory 文件/路径不存在 #define

tcp的有限状态机--【全面解析】-爱代码爱编程

了解Tcp的有限状态机,有助于我们理解Tcp的3次握手与四次挥手 CLOSED:表示初始状态LISTEN:表示服务器端的某个socket处于监听状态,可以接受连接SYN_SENT:在服务端监听后,客户端soc

Web服务器——HTTP状态机解析-爱代码爱编程

Web服务器——HTTP状态机解析 程序说明 主要练习HTTP解析的状态机的使用。接收一个客户端请求,判断是否是一个正确的GET请求,并解析出相应字段。   主要练习HTTP解析的状态机的使用。接收一个客户端请求,判断是否是一个正确的GET请求,并解析出相应字段。   有两个状态机,主状态机和从状态机,分别解析出相关字段。   注意一个地方,每次rec

Flutter Socket实战-爱代码爱编程

FlutterSocket实战,跟着走下来,保证你也会写一个简单的聊天 欢迎加入Flutter技术交流群:723609732 前言 首先上面的功能特点读者可以看到了,由于我还没有解决如何裁剪视频第一帧这个问题,所以有点小瑕疵,但是其他功能是可以的。其中包含了: 文字聊天图片发送(查看)选取图片录视频选取视频发送语音接下来就步入正题开始从头给读者介绍

TCP状态机详解-爱代码爱编程

一、TCP状态机是TCP连接的变化过程。 Tcp在三次握手和四次挥手的过程,就是一个tcp的状态说明,由于tcp是一个面向连接的,可靠的传输,每一次的传输都会经历连接,传输,关闭的过程,无论是哪个方向的传输,必须建立连接才行,在双方通信的过程中,tcp 的状态是不一样的。 下面介绍一下,在三次握手和四次挥手的过程中的几种状态,如下图所示,是tcp状态的

python怎么连接socket_python之socket连接-爱代码爱编程

一、套接字 套接字是为特定网络协议(例如TCP/IP,ICMP/IP,UDP/IP等)套件对上的网络应用程序提供者提供当前可移植标准的对象。它们允许程序接受并进行连接,如发送和接受数据。为了建立通信通道,网络通信的每个端点拥有一个套接字对象极为重要。 套接字为BSD UNIX系统核心的一部分,而且他们也被许多其他类似UNIX的操作系统包括Linu

python tcp连接状态判断_Socket套接字连接状态判断,接收数据笔记-爱代码爱编程

最近工作中涉汲到一些Socket 方面应用 ,如断线重连,连接状态判断等,今天做了一些总结。 1.判断Socket 连接状态 通过 Poll 与 Connected 结合使用 ,重点关注 SelectRead  模式 方法名: Socket.Poll (int microSeconds, System.Net.Sockets.SelectMod

python实现socket简单通信-爱代码爱编程

python实现socket简单通信 首先先来简单介绍下socket: (具体更详细介绍的可以在网上找找,都讲得非常详细),这里主要是我自己的一些理解。 socket是在应用层与传输层之间的一个抽象层,它的本质是编程接口,通过socket,才能实现TCP/IP协议。 它就是一个底层套件,用来处理最底层消息的接受和发送。socket翻译为套接字,可以把TC

Socket通信-爱代码爱编程

什么是 socket? socket 的原意是“插座”,在计算机通信领域,socket 被翻译为“套接字”,它是计算机之间进行通信的一种约定或一种方式。 通过 socket 这种约定,一台计算机可以接收其他计算机的数据,也可以向其他计算机发送数据。就像把插头插向插座能通电一样,socket就是这个通信的媒介。 套接字类型 使用TCP/IP协议的流

网络编程 socket详解 TCP socket和UDP socket-爱代码爱编程

概述         我们在网络编程时,通常是让我们本地的应用程序和远程的应用程序进行通信,也就是分布式的进程之间的通信,比如我写的程序A和小明的程序B进行通信,我的程序运行时在本机就是一个进程,是有pid号的,小明的也是。那这两个程序是怎么通信的呢?         这就要理解网络分层的概念了,网络层实现的是主机到主机之间的通信,网络层的实现是ip协

shortsighted(线段树维护2次函数)_一条小小yu的博客-爱代码爱编程

While practicing for The 2019 ICPC Asia Jakarta Regional Contest, Budi stumbled upon an interesting problem on data structure topic. Unfortunately, he misread the problem, but he