共享链表管理方法、装置及设备

本发明涉及数据存储技术领域，尤其涉及一种共享链表管理方法、装置及设备。

当系统缓存规模较大时，采用降低缓存颗粒度的方式，可以有效提高缓存利用率。所谓缓存颗粒度，即将整个缓存空间划分为若干个基本缓存单元，每个缓存单元的大小就代表了缓存颗粒度，每个数据包占用一个或者多个缓存单元。缓存颗粒度越小，表示缓存空间被划分的越精细，则能够被浪费的缓存空间也越小。

但随着缓存颗粒度的变小，在相同的缓存容量下，需要进行管理的缓存单元就会增多，另外，当一个数据包占用多个缓存单元时，为保持整包的完整性，需要对该数据包的所有缓存单元进行关联处理，即采用包链表的方式来实现。

目前，缓存单元管理和包链表管理采用独立的设计，随着缓存规模的增加，缓存单元管理和包链表管理会消耗大量的管理资源。

本发明的主要目的在于提供一种共享链表管理方法、装置及设备，旨在解决现有技术中缓存单元管理和包链表管理消耗大量管理资源的技术问题。

第一方面，本发明提供一种共享链表管理方法，所述共享链表管理方法包括：

配置缓存单元管理链表，其中，缓存单元管理链表中尾节点的内容为无效值，其他节点的内容为本节点对应的缓存单元的下一个缓存单元的地址；

当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；

当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。

可选的，所述当写入数据包时，为所述数据包申请缓存单元的步骤包括：

当写入数据包时，检测缓存单元管理链表中的首节点的内容是否为无效值，若不为无效值，则申请所述首节点对应的缓存单元，以供写入数据包的包数据，并更新缓存单元管理链表中的首节点为所述首节点的内容对应的节点；

检测数据包的包尾是否已写入；

若未写入，则返回所述检测缓存单元管理链表中的首节点的内容是否为无效值的步骤，直至数据包的包尾已写入。

可选的，所述数据包的包管理链表中除最后一个节点外的其他节点的内容为各自的后一个申请的缓存单元的地址。

可选的，在所述根据取出的节点构建所述数据包的包管理链表的步骤之后，还包括：

生成并存储所述数据包的包描述信息，所述包描述信息包括为所述数据包申请的第一个缓存单元的地址以及所述数据包的字节长度。

可选的，所述当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表的步骤包括：

当读取数据包时，获取所述数据包的包描述信息；

根据所述包描述信息，从为所述数据包申请的第一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的第一个缓存单元对应的节点；

检测数据包的包尾是否已读取；

若未读取，则从为所述数据包申请的后一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的后一个缓存单元对应的节点，其中，后一个申请的缓存单元根据前一个申请的缓存单元对应的节点的内容确定；

返回所述检测数据包的包尾是否已读取的步骤，直至数据包的包尾已读取。

可选的，所述数据包的包管理链表中最后一个节点的内容为所述数据包的校验值，所述校验值基于对为所述数据包申请的所有缓存单元的地址进行预设运算得到。

可选的，在所述直至数据包的包尾已读取的步骤之后，还包括：

对读取的所有缓存单元的地址进行预设运算得到待验证校验值；

检测所述待验证校验值与最后一次读取的缓存单元对应的节点的内容是否一致；

若一致，则确定数据包读取正确。

可选的，所述共享链表管理方法还包括：

将初始缓存单元管理链表中各个节点的状态设置为空闲状态，将被申请的缓存单元对应的节点的状态设置为占用状态，将被释放的缓存单元对应的节点的状态设置为空闲状态；

当待申请的缓存单元对应的节点的状态为占用状态时，确定释放存在错误；

当待释放的缓存单元对应的节点的状态为空闲状态时，确定申请存在错误。

第二方面，本发明还提供一种共享链表管理装置，所述共享链表管理装置包括：

配置模块，用于配置缓存单元管理链表；

申请模块，用于当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；

释放模块，用于当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。

第三方面，本发明还提供一种共享链表管理设备，所述共享链表管理设备包括处理器、存储器、以及存储在所述存储器上并可被所述处理器执行的共享链表管理程序，其中所述共享链表管理程序被所述处理器执行时，实现如上所述的共享链表管理方法的步骤。

本发明中，配置缓存单元管理链表，其中，缓存单元管理链表中尾节点的内容为无效值，其他节点的内容为本节点对应的缓存单元的下一个缓存单元的地址；当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。通过本发明，当有数据包写入缓存单元时，被申请的缓存单元对应的节点构成该数据包的包管理链表，当缓存单元被释放，则被释放的缓存单元对应的节点还原至缓存单元管理链表，即实现了节点被缓存单元管理链表和包管理链表共享，大大减少了对缓存单元进行管理以及对包链表进行管理所需要的管理资源。

图1为本发明共享链表管理方法一实施例的流程示意图；

图2为本发明共享链表管理方法一实施例中缓存单元管理链表的示意图；

图3为本发明共享链表管理方法一实施例中申请缓存单元的流程示意图；

图4为本发明共享链表管理方法一实施例中缓存单元管理链表与包管理链表共存的示意图；

图5为图1中步骤S30的细化流程示意图；

图6为本发明共享链表管理方法另一实施例中缓存单元管理链表的示意图；

图7为本发明共享链表管理装置一实施例的功能模块示意图。

本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。

应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

第一方面，本发明实施例提供一种共享链表管理设备，共享链表管理设备包括处理器、存储器、以及存储在存储器上并可被处理器执行的共享链表管理程序，其中，处理器可以调用存储器中存储的共享链表管理程序，并执行本发明实施例提供的共享链表管理方法。

第二方面，本发明实施例提供了一种共享链表管理方法。

一实施例中，参照图1，图1为本发明共享链表管理方法一实施例的流程示意图。如图1所示，共享链表管理方法包括：

步骤S10，配置缓存单元管理链表，其中，缓存单元管理链表中尾节点的内容为无效值，其他节点的内容为本节点对应的缓存单元的下一个缓存单元的地址；

本实施例中，根据缓存空间的颗粒度划分情况，配置对应的缓存单元管理链表。例如，缓存空间被划分为缓存单元A～缓存单元G，7个缓存单元的地址分别为ADDR_A、ADDR_B、ADDR_C、ADDR_D、ADDR_E、ADDR_F、ADDR_G；7个缓存单元间的存储顺序为缓存单元A、缓存单元B、缓存单元C、缓存单元D、缓存单元F、缓存单元G、缓存单元E。则配置得到的缓存单元管理链表如图2所示，参照图2，图2为本发明共享链表管理方法一实施例中缓存单元管理链表的示意图，如图2所示，基于7个缓存单元间的存储顺序，节点A的内容为节点A对应的缓存单元A的下一个缓存单元，即缓存单元B的地址ADDR_B；节点B的内容为节点B对应的缓存单元B的下一个缓存单元，即缓存单元C的地址ADDR_C；节点C的内容为节点C对应的缓存单元C的下一个缓存单元，即缓存单元D的地址ADDR_D；节点D的内容为节点D对应的缓存单元D的下一个缓存单元，即缓存单元F的地址ADDR_F；节点F的内容为节点F对应的缓存单元F的下一个缓存单元，即缓存单元G的地址ADDR_G；节点G的内容为节点G对应的缓存单元G的下一个缓存单元，即缓存单元E的地址ADDR_E；节点E即为缓存单元管理链表中尾节点，则节点E的内容为无效值。

可见，当缓存单元管理链表对应的缓存单元中均未写入数据时，共享链表即为缓存单元管理链表。

容易理解的是，此处以7个缓存单元进行说明，是为了方便描述，实际上缓存空间包含的缓存单元数量是很多的，但配置缓存单元管理链表的方式与上述实施例一致，在此不做赘述。

步骤S20，当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；

本实施例中，以图2为例，当写入数据包1时，为该数据包申请缓存单元，例如，先申请缓存单元A，并将数据包1的包数据写入缓存单元A，然后判断数据包1是否写入完成；若未完成，则再申请缓存单元B，并将数据包1剩余的包数据写入缓存单元B，然后判断数据包1是否写入完成；若写入完成，则将申请的缓存单元A和B对应的节点A和节点B从缓存单元管理链表中取出，并根据节点A和节点B构建数据包1的包管理链表1。即在缓存单元A和缓存单元B中未写入数据时，节点A和节点B归属于缓存单元管理链表；在缓存单元A和缓存单元B中写入数据时，节点A和节点B归属于数据包1的包管理链表1，即实现了节点A和节点B被缓存单元管理链表和包管理链表1共享，而无需分别为缓存单元管理链表和包管理链表1设置对应的节点A和节点B。

进一步地，一实施例中，参照图3，图3为本发明共享链表管理方法一实施例中申请缓存单元的流程示意图。如图3所示，所述当写入数据包时，为所述数据包申请缓存单元的步骤包括：

当写入数据包时，检测缓存单元管理链表中的首节点的内容是否为无效值，若不为无效值，则申请所述首节点对应的缓存单元，以供写入数据包的包数据，并更新缓存单元管理链表中的首节点为所述首节点的内容对应的节点；检测数据包的包尾是否已写入；若未写入，则返回所述检测缓存单元管理链表中的首节点的内容是否为无效值的步骤，直至数据包的包尾已写入。

本实施例中，以图2为例，当写入数据包时，缓存单元管理链表中的首节点(即节点A)的内容为ADDR_B，则申请节点A对应的缓存单元A，以供写入数据包的包数据，并更新缓存单元管理链表中的首节点为首节点的内容ADDR_B对应的节点B。

判断数据包的包尾是否已写入，若未写入，则返回所述检测缓存单元管理链表中的首节点的内容是否为无效值的步骤，容易理解的是，此时缓存单元管理链表中的首节点为节点B，则申请节点B对应的缓存单元B，以供写入数据包的包数据并更新缓存单元管理链表中的首节点为首节点的内容ADDR_C对应的节点C。

判断数据包的包尾是否已写入，若未写入，则返回所述检测缓存单元管理链表中的首节点的内容是否为无效值的步骤，直至数据包的包尾已写入。

容易理解的是，若缓存单元管理链表中的首节点的内容为无效值，则说明缓存单元已耗尽。

进一步地，一实施例中，数据包的包管理链表中除最后一个节点外的其他节点的内容为各自的后一个申请的缓存单元的地址。

本实施例中，假设在更新缓存单元管理链表中的首节点为首节点C后，检测到数据包的包尾已写入，则将申请的缓存单元A和缓存单元B对应的节点A和节点B从缓存单元管理链表中取出，并根据取出的节点A和节点B构建数据包的包管理链表，其中，包管理链表中除最后一个节点外的其他节点的内容为各自的后一个申请的缓存单元的地址。参照图4，图4为本发明共享链表管理方法一实施例中缓存单元管理链表与包管理链表共存的示意图。包管理链表中最后一个节点的内容根据实际需要进行设置，例如设置为无效值或校验值或为空。如图4所示，当缓存单元管理链表对应的缓存单元中写入数据时，共享链表包括缓存单元管理链表以及包管理链表。

需要说明的是，当后续继续写入新的数据包时，则以最新的缓存单元管理链表为基础，按照上述实施例对应的方式，为新的数据包申请缓存单元，以及构建新的数据包对应的包管理链表，此处不再赘述。

步骤S30，当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。

本实施例中，结合上述实施例，当此时读取的数据包为上述写入的数据包时，则释放该数据包对应的缓存单元A和B，并将释放的缓存单元A和B对应的节点A和B还原到缓存单元管理链表。

容易理解的是，当缓存单元被申请后，对应的节点在缓存单元管理链表中随即失效，已失效的节点将一直保持为闲置状态，直到对应的缓存单元被释放。已失效的节点处于闲置状态的期间，对已失效的节点分配的管理资源便被浪费了。而在本申请中，当缓存单元被申请后，对应的节点用于构建被申请的缓存单元对应的数据包的包管理链表，避免了管理资源的浪费。

本实施例中，配置缓存单元管理链表；当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。通过本实施例，当有数据包写入缓存单元时，被申请的缓存单元对应的节点构成该数据包的包管理链表，当缓存单元被释放，则被释放的缓存单元对应的节点还原至缓存单元管理链表，即实现了节点被缓存单元管理链表和包管理链表共享，大大减少了对缓存单元进行管理以及对包链表进行管理所需要的管理资源。

进一步地，一实施例中，在步骤S20之后，还包括：

生成并存储所述数据包的包描述信息，所述包描述信息包括为所述数据包申请的第一个缓存单元的地址以及所述数据包的字节长度。

本实施例中，根据为数据包申请的第一个缓存单元的地址以及数据包的字节长度生成数据包的包描述信息，并存储于预设的存储区域。

进一步地，一实施例中，参照图5，图5为图1中步骤S30的细化流程示意图。如图5所示，步骤S30包括：

当读取数据包时，获取所述数据包的包描述信息；根据所述包描述信息，从为所述数据包申请的第一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的第一个缓存单元对应的节点；检测数据包的包尾是否已读取；若未读取，则从为所述数据包申请的后一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的后一个缓存单元对应的节点，其中，后一个申请的缓存单元根据前一个申请的缓存单元对应的节点的内容确定；返回所述检测数据包的包尾是否已读取的步骤，直至数据包的包尾已读取。

本实施例中，当读取的数据包为上述实施例中写入的数据包时，根据其包描述信息，即可确定为数据包申请的第一个缓存单元为缓存单元A，从而从缓存单元A中读取包数据，并更新缓存单元管理链表的尾节点由节点E变为节点A，则节点E的内容更新为缓存单元A的地址，节点A的内容更新为无效值。

检测数据包的包尾是否已读取；若未读取，则从为数据包申请的后一个缓存单元(即缓存单元B)中读取包数据，并更新缓存单元管理链表的尾节点由节点A变为节点B，则节点A的内容更新为缓存单元B的地址，节点B的内容更新为无效值，此时的缓存单元管理链表便如图6所示，参照图6，图6为本发明共享链表管理方法另一实施例中缓存单元管理链表的示意图。

进一步地，一实施例中，所述数据包的包管理链表中最后一个节点的内容为所述数据包的校验值，所述校验值基于对为所述数据包申请的所有缓存单元的地址进行预设运算得到。

本实施例中，数据包的包管理链表中最后一个节点的内容为数据包的校验值，即图4中节点B的内容为数据包的校验值。校验值基于对为数据包申请的所有缓存单元的地址进行预设运算得到，以图4为例，即校验值基于对缓存单元A的地址以及缓存单元B的地址进行预设运算得到。其中，预设运算可以是校验和运算、哈希运算等等，此处不对预设运算进行限制，具体根据实际需要选择。

进一步地，一实施例中，在所述直至数据包的包尾已读取的步骤之后，还包括：

对读取的所有缓存单元的地址进行预设运算得到待验证校验值；检测所述待验证校验值与最后一次读取的缓存单元对应的节点的内容是否一致；若一致，则确定数据包读取正确。

本实施例中，例如将一数据包写入了缓存单元D、缓存单元F和缓存单元G，则节点G中的内容为基于对ADDR_D、ADDR_F以及ADDR_G进行预设运算得到，为了校验读取该数据包是否正确，需要对读取该数据包时读取的所有缓存单元的地址进行预设运算得到待验证校验值，然后将待验证校验值与最后一次读取的缓存单元对应的节点的内容进行对比，若一致，则说明是从缓存单元D、缓存单元F和缓存单元G中读取，则说明数据包读取正确。

需要说明的是，若不一致，则说明数据包读取错误，则将读取的数据包丢弃。通过本实施例，实现了对数据读取动作进行检错。

进一步地，一实施例中，共享链表管理方法还包括：

将初始缓存单元管理链表中各个节点的状态设置为空闲状态，将被申请的缓存单元对应的节点的状态设置为占用状态，将被释放的缓存单元对应的节点的状态设置为空闲状态；

当待申请的缓存单元对应的节点的状态为占用状态时，确定释放存在错误；

当待释放的缓存单元对应的节点的状态为空闲状态时，确定申请存在错误。

本实施例中，初始缓存单元管理链表为处于初始状态的缓存单元管理链表，此时由于对应的缓存单元均未被占用，则将初始缓存单元管理链表中各个节点的状态设置为空闲状态，即未写入数据的缓存单元对应的节点状态应该为空闲状态。

在写入数据时，对待申请的缓存单元对应的节点的状态进行检测，若其状态为占用状态，则说明在释放该缓存单元时存在错误，因此确定释放存在错误。

将被申请的缓存单元对应的节点的状态设置为占用状态，即写入了数据的缓存单元对应的节点状态应该为占用状态，在读取数据时，对待释放的缓存单元对应的节点的状态进行检测，若其状态为空闲状态，则说明在申请该缓存单元时存在错误，因此确定申请存在错误。

另外，被释放的缓存单元对应的节点会被还原到缓存单元管理链表，则将被释放的缓存单元对应的节点的状态设置为空闲状态。

其中，节点状态可以通过添加状态标志位实现，通过本实施例实现了共享链表的校验功能。

第三方面，本发明实施例还提供一种共享链表管理装置。

一实施例中，参照图7，图7为本发明共享链表管理装置一实施例的功能模块示意图。如图7所示，共享链表管理装置包括：

配置模块10，用于配置缓存单元管理链表；

申请模块20，用于当写入数据包时，为所述数据包申请缓存单元，将申请的缓存单元对应的节点从缓存单元管理链表中取出，并根据取出的节点构建所述数据包的包管理链表；

释放模块30，用于当读取数据包时，释放所述数据包对应的缓存单元，将释放的缓存单元对应的节点还原至缓存单元管理链表。

进一步地，一实施例中，申请模块20，用于：

当写入数据包时，检测缓存单元管理链表中的首节点的内容是否为无效值，若不为无效值，则申请所述首节点对应的缓存单元，以供写入数据包的包数据，并更新缓存单元管理链表中的首节点为所述首节点的内容对应的节点；

检测数据包的包尾是否已写入；

若未写入，则返回所述检测缓存单元管理链表中的首节点的内容是否为无效值的步骤，直至数据包的包尾已写入。

进一步地，一实施例中，所述数据包的包管理链表中除最后一个节点外的其他节点的内容为各自的后一个申请的缓存单元的地址。

进一步地，一实施例中，共享链表管理装置还包括存储模块，用于：

生成并存储所述数据包的包描述信息，所述包描述信息包括为所述数据包申请的第一个缓存单元的地址以及所述数据包的字节长度。

进一步地，一实施例中，释放模块30，用于：

当读取数据包时，获取所述数据包的包描述信息；

根据所述包描述信息，从为所述数据包申请的第一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的第一个缓存单元对应的节点；

检测数据包的包尾是否已读取；

若未读取，则从为所述数据包申请的后一个缓存单元中读取包数据，并更新缓存单元管理链表的尾节点是为所述数据包申请的后一个缓存单元对应的节点，其中，后一个申请的缓存单元根据前一个申请的缓存单元对应的节点的内容确定；

返回所述检测数据包的包尾是否已读取的步骤，直至数据包的包尾已读取。

进一步地，一实施例中，所述数据包的包管理链表中最后一个节点的内容为所述数据包的校验值，所述校验值基于对为所述数据包申请的所有缓存单元的地址进行预设运算得到。

进一步地，一实施例中，共享链表管理装置还包括校验模块，用于：

对读取的所有缓存单元的地址进行预设运算得到待验证校验值；

检测所述待验证校验值与最后一次读取的缓存单元对应的节点的内容是否一致；

若一致，则确定数据包读取正确。

进一步地，一实施例中，共享链表管理装置还包括状态管理模块，用于：

将初始缓存单元管理链表中各个节点的状态设置为空闲状态，将被申请的缓存单元对应的节点的状态设置为占用状态，将被释放的缓存单元对应的节点的状态设置为空闲状态；

当待申请的缓存单元对应的节点的状态为占用状态时，确定释放存在错误；

当待释放的缓存单元对应的节点的状态为空闲状态时，确定申请存在错误。

其中，上述共享链表管理装置中各个模块的功能实现与上述共享链表管理方法实施例中各步骤相对应，其功能和实现过程在此处不再一一赘述。

需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者系统不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者系统所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括该要素的过程、方法、物品或者系统中还存在另外的相同要素。

上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。

以上仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。