A memory buffer system and a method for operating a memory buffer system for fast data exchange

The invention relates to a memory buffer system and a method for operating a memory buffer system for fast data exchange in a multi-thread environment.

Background of the invention

In high-performance network attached computer systems the implementation of data transport protocols is usually or ^¬ ganized in a multi-threaded fashion. Hereby, the tasks of handling sending user data as well as signaling data, handling receiving data and control information and the communication with a user application are delivered to different program threads or processes within the system.

Fig. 1 shows a block diagram of a common data transport protocol implementation. Hereby, when an application starts data communication over a network system, it needs at least one thread for sending (send handler 2), one thread for receiving (receive handler 3) and an applica ^¬ tion thread 1 (API-thread) that transports data between the user application and a protocol stack. The send handler 2 is used to send data packets and control informa ^¬ tion to the network system. As soon as packet loss is de ^¬ tected, the send handler 2 retransmits lost packets. A send buffer 4 temporarily stores unacknowledged data, till an acknowledgment is delivered to the sender thread.

Receive handler 3 receives data from the network system and stores them into a receive buffer 5. In case of a packet loss detection, the receive handler 3 informs the

send handler 2, so it can send a control packet with loss data information to the sender thread of the communica ^¬ tion pair. Since different tasks according to Fig. 1 ac ^¬ cess shared data structures, those accesses must be syn- chronized. Conventionally, such synchronization is imple ^¬ mented by mutexes or semaphores.

While the send handler 2 and the receive handler 3 are function components, the send buffer 4 and the receive buffer 5 may be referred to as data components.

When the API-thread 1 has to write data into the send buffer 4, it applies a mutex or a semaphore to block the simultaneously reading access from the send handler 2. If the send handler 2 tries to read data from the send buffer 4 for sending, it also applies a mutex or sema ^¬ phore to prevent a simultaneous access attempt from the API-thread. The access from receive handler 3 to receive buffer 5 is similar to that of the send handler 2.

The intensive use of mutexes and semaphores for thread synchronization decreases stack performance rapidly, since simultaneous access to the data, leads to waits for process threads. Moreover, it leads to a rapid increase of the number of necessary system calls for thread synchronization .

The invention

It is the object of the invention to provide a more effi ^¬ cient memory buffer system and a method for operating a memory buffer system for fast data exchange in a multi- thread environment for more efficiently managing data ex-

change. Especially, the efficiency of data exchange be ^¬ tween several threads shall be improved, i.e. when imple ^¬ menting a network transport protocol stack.

According to one aspect of the invention, a memory buffer system is provided, which is connected to a computer net ^¬ work system, and a network data transport protocol pro ^¬ vided for data transport in the computer network system, comprising: a send memory ring buffer, configured to re- ceive send data from the user application and submit the send data via a thread-implemented send handler, a re ^¬ ceiving memory ring buffer, configured to receive receive data via a thread-implemented receive handler and pass data to the user application, and a send token ring buffer, configured to manage access to the sent data for the send handler and the receive handler.

According to another aspect of the invention, a method for operating a memory buffer system in a multi-thread environment for managing data exchange between a user ap ^¬ plication implemented on a computer, which is connected to a computer network system, and a network data transport protocol provided for data transport in the computer network system is provided, the method comprising steps of: in a send memory ring buffer, receiving send data from the user application and submitting the send data via a thread-implemented send handler, in a receiving memory ring buffer, receiving receive data via a thread- implemented receive handler and passing the receive data to the user application, and in a send token ring buffer, managing access to the sent data for the send handler and the receive handler.

The proposed memory buffer system and the method for op ^¬ erating the buffer system lead to a significant reduction of data copy operations within the computer network sys ^¬ tem and to a rapid reduction of synchronization opera- tions. Such efficient buffer management, for example, is vital in order to implement data transfers of uncom ^¬ pressed 4k video data over 10 Gbit/s networks.

Since each of the proposed memory buffers is accessed at least from one execution thread for reading and at least from one execution thread for writing, those threads, that perform read access to the memory are referred to as reader thread, threads, performing writing access to the associated memory are referred to as writer threads.

In a preferred embodiment of the invention, at least one of the send memory ring buffer, the receiving memory ring buffer, and the send token ring buffer is comprising at least two pointers selected from the following group of pointers: a read pointer, configured to point at the be ^¬ ginning of a occupied memory area occupied by stored data readable by a reader thread, a write pointer, configured to point at the beginning of a still free memory area ca ^¬ pable of receiving new stored data in a writer thread, and a filled pointer, configured to point at the begin ^¬ ning of a filled memory area at least partially filled with stored data, wherein the occupied memory area is lo ^¬ cated between the filled pointer and the read pointer, wherein still free memory area is located between the write pointer and the read pointer, and wherein the filled memory area is located between the write pointer and the filled pointer. In a further embodiment, all three of the pointers are provided in at least one of the

ring buffers. In still a further embodiment, depending on the use of the memory ring buffer the filled pointer can be omitted, e.g. if no acknowledgement from a remote site is necessary.

According to a preferred embodiment of the invention, the read pointer is configured to move forward by an amount of read data which are read from the occupied memory area. The amount of free space is increased by the amount of read data.

In a further preferred embodiment of the invention, the write pointer is configured to move forward by an amount of written data which are written into the still free memory area. When data are written into a free region, the write pointer is moved forward by the amount of writ ^¬ ten data.

According to a further preferred embodiment of the inven- tion, at least one of the read pointer and the filled pointer is configured to be exclusively moved by the reader thread.

In still a further preferred embodiment of the invention, a read pointer of the send memory ring buffer is configured to be exclusively moved by the send handler.

According to still a preferred embodiment of the inven ^¬ tion, a filled pointer of the send memory ring buffer is configured to be exclusively moved by the receive han ^¬ dler .

In a preferred embodiment of the invention, the receiving memory ring buffer is comprising a further read pointer and a further write pointer. For example, such additional pointers may be provided in the receive memory ring buffer.

According to a preferred embodiment of the invention, the write pointer is configured to be exclusively moved by the writer thread.

In a further preferred embodiment of the invention, the send token ring buffer is configured to have the send handler recorded data packet information in the send to ^¬ ken ring buffer.

According to a further preferred embodiment of the inven ^¬ tion, the send token ring buffer is configured to provide data packet retransmission information to the send handler for a data packet retransmission.

In still a further preferred embodiment of the invention, the send memory ring buffer, the receiving memory ring buffer, and the send token ring buffer are implemented by an implementation selected from the following group of implementations: hardware implementation, embedded soft ^¬ ware implementation, and application layer process implementation .

Description of preferred embodiments of the invention

Following preferred embodiments of the invention are de ^¬ scribed in detail by referring to Figures. In the Figures show :

Fig. 1 a block diagram of a common data transport protocol implementation,

Fig. 2 a schematic representation of an asynchronous read/write ring buffers (subsequently abbrevi- ated as ARWRB) buffer management system,

Fig. 3 a schematic representation for a process of a synchronization-free access to memory ring buffer,

Fig. 4 a schematic representation of methods which can be implemented in the send token ring buffer,

Fig. 5 a schematic representation of an interaction of the methods depicted in Fig. 4 with reader and writer threads,

Fig. 6 a schematic representation of three methods which can be implemented in the send token ring buffer,

Fig. 7 a schematic representation of an interaction of the methods depicted in Fig. 6,

Fig. 8 shows a schematic representation of an interac- tion of send memory ring buffer- and send token ring buffer-methods within receive and send han ^¬ dler,

Fig. 9 a schematic representation of five methods which can be implemented in the receive memory ring buffer, and

Fig. 10 a schematic representation of an interaction of the methods depicted in Fig. 9.

The present invention, in a preferred embodiment, pro- poses to use an interconnected system of different kinds of memory buffers, implemented as asynchronous read/write ring buffers. The ring buffers are organized in a way, in which data can be stored into the ring buffer or fetched

from the ring buffer essentially avoiding synchronization means like mutexes or semaphores.

Admittedly, one mutex may still be used within a receive ring buffer in case of a transmission of irregular packets, the occurrence of irregular packets can, however, be kept rarely.

The term of irregular packets implies a presumption, that mostly, data are transmitted in constant-size chunks, so called regular packets. Only in cases of some exceptions, data packets, smaller than regular packets are transmit ^¬ ted over the network. Such short packets are called ir ^¬ regular packets, i.e. when there are not enough data to assemble a regular packet.

Fig. 2 a schematic representation of a basic ARWRB buffer management system.

In contrast to the conventional buffer management system (see Fig. 1), three memory ring buffers, namely a send memory ring buffer (SRB) 100, a send token ring buffer (STRB) 101 and a receive memory ring buffer (RRB) 102, are used within a data transport protocol stack.

Necessary memory space for the SRB 100, the STRB 101 and the RRB 102 is preferably allocated at the initialization phase of the transmission system. So, during ring buffer operation, no buffer growth or shrinking should be performed. Besides a main application thread 1, in which API calls can be processed, one sending and one receiving threads are also started during the initialization phase. When a receive handler 103 of a data sender receives a data acknowledgement, it releases the corresponding space

of buffer within the SRB 100. It also deletes the corre ^¬ spondent token from the STRB 101. The send handler 104, besides, records all transmitted packet information within the STRB 101. So, in case of packet retransmis- sion, the sender thread (send handler 104) can directly refer to the buffer address, associated with retransmit ^¬ ted sequence number.

While the send handler 104 and the receive handler 103 are function components, the SRB 100, the STRB 101 and the RRB 102 may referred to as data components.

A reader thread of the SRB 100 (send handler 104) can access the SRB 100 without requesting system calls, e.g. mutex, to stop a writer thread (API-thread 1) which tries to write simultaneously data into the SRB 100, or vice versa .

The data processing within the RRB 102 is basically simi- lar to the processing within the SRB 100. The receive handler 103 can write received data simultaneously to the RRB 102 while the API-thread tries to read data from it. However, in case of the occurrence of an irregular data packet, some special synchronization means between the API-thread send and the receive handler 103 are neces ^¬ sary .

For the sake of simplicity of the proposed buffer manage ^¬ ment system, it is assumed, that the API send call blocks, when the SRB 100 has not enough space, to store data from the send call and respectively, the receive API call blocks, when no data are stored within the RRB 102 while the receive call is raised.

Fig. 3 shows a schematic representation for a process of a synchronization-free access to a memory ring buffer 200 which may provide for the send memory ring buffer (SRB) 100, the send token ring buffer (STRB) 101 or the receive ring buffer (RRB) 102.

Provided that one thread is only storing data into the ring buffer 200 and another independent thread is only reading data from the ring buffer 200, it can be possible to access the ring buffer 200 without any synchronization mechanism. For that, in general three pointers are pro ^¬ vided for buffer access. A read pointer (RP) 201 marks the beginning of data stored within the ring buffer 200. A write pointer (WP) 202 denotes the beginning of an area, which is still free and can be used to store new data. A filled pointer (FP) 203 denotes begin of a buffer area that is already partially filled with data. However, the data between the FP 203 and the WP 202 should not be read by the reader thread, e.g. because these data are not yet acknowledged by the remote site. The region be ^¬ tween the FP 203 and the RP 201 denotes data that can be read by the reader thread.

The region between the WP 202 and the RP 201 denotes the free space of the ring buffer 200 and can be used to store new data into the ring buffer 200. The region be ^¬ tween the WP 202 and the FP 203 is the region with partly written data. However this data are not yet released for reading.

Following, movement of the individual pointers during the operations is described. When data are read (fetched)

from the ring buffer 200, the RP 201 is moved forward by the amount of read data, so after the read operation it points again to the beginning of the unread area. The amount of the free area is increased by this amount. When data are written into the free region, the WP 202 is moved forward by the amount of written data. The area of partially written data is increased by this amount. In general, these data must be released for reading on spe ^¬ cial events, e.g. on data acknowledge. Such events, that move the FP 203 forward, can be generated by the reader thread using a method FreeChunk . So, the WP 202 is always driven by the writer thread, the RP 201 and the FP 203 are driven exclusively by the reader thread. Using the ring buffer 200 in this way, operations can be performed simultaneously by the reader and writer thread without any thread synchronization means.

Depending on a special usage of the ring buffer 200, the FP 203 can be omitted, e.g. when no acknowledge from a remote site is necessary. However, depending on a special acknowledgement implementation, also more than one in ^¬ stance of the WP 202 may be provided.

Referring to Fig. 4 to 10, further details are described. A proposed implementation buffer is described in an object-oriented semantics. It can be implemented in hard ^¬ ware, embedded software or as an application layer proc ^¬ ess. In Fig. 4 to 10, the same features are referred to by the same reference numerals used in Fig. 2 and 3.

Fig. 4 shows a schematic representation of methods which can be implemented in the send memory ring buffer (SRB) 100.

The SRB 100 is accessed through three pointers - a read pointer (SRB-RP) 300, write pointer (SRB-WP) 301 and filled pointer (SRB-FP) 302, which indicate access points to the SRB 100. Hereby the:

- The SRB-WP 301 can only be used by writer thread (API- Thread) . The SRB-WP 301 points to the actual buffer ad ^¬ dress with enough free space, in which the data should be temporarily stored. If a data chunk has been suc- cessfully stored, the WP 202 should be moved ahead by the amount of stored data.

- The SRB-RP 300 can only be used by reader thread (send handler) . The SRB-RP 300 points to the first byte, that is not yet read by the send handler 104. If a data chunk has been read successfully from the SRB 100, the SRB-RP 300 should be moved ahead by the amount of read data .

- The SRB-FP 302 is moved forwards by another reader thread (receive handler) in case of an acknowledge re- ception.

If a pointer points to the end of allocated space, a wrap around of the pointer is performed.

In general, a non-synchronized access to the SRB 100 is only possible, when just one writer thread (API-thread) writes into the SRB 100 and at most one reader thread

(send handler 104) reads from it. This condition is not fulfilled in the described scenario, since besides the send handler 104 the receive handler 103 also accesses the SRB 100.

However, the SRB-RP 300 can only be moved by the send handler 104 (reader thread) for data (re-) transmission, and the SRB-FP 302 can only be moved by the receive han ^¬ dler (another reader thread) on condition that the trans- mitted packet is acknowledged by remote side application. That's why there is no collision between the SRB-RP 300 and SRB-FP 302, so thread synchronization is not needed. The SRB 100 on the sender side has four major methods to meet the needs for data temporal storage into ring buffer, for packet sending, for packet loss handling, and for releasing acknowledged data.

Fig. 5 shows a schematic representation of an interaction of the methods depicted in Fig. 4 with reader and writer threads.

The Store () -method in writer thread is used to store data temporarily into the SRB 100 and move the SRB-WP 301 correspondingly. In order to send new data, the GetNex- tChunk () -method is used to get the read position and the number of stored bytes from the reader thread (send han ^¬ dler) . The RP is moved ahead as appropriated. If packet loss is detected, GetPrevChunk () -method is called to give the reader thread (send handler) the read position of the corresponding data packet and the length of the respec ^¬ tive data chunk. If an acknowledgement (ACK) from the re ^¬ mote side is received, another reader thread (receive handler) calls the FreeChunk () -method to move the FP in SRB. The STRB has to be used while using GetNextChunk () - , GetPrevChunk () - and FreeChunk () -methods .

Referring to Fig. 6 and 7, the functionality of the send token ring buffer (STRB) 101 is described in further de-

tail. Fig. 6 shows a schematic representation of three methods which can be implemented in the send token ring buffer (STRB) 101. Fig. 7 shows a schematic representa ^¬ tion of an interaction of the methods depicted in Fig. 6.

While the send handler 104 fetches data from the SRB 100 in order to send it over the network, the STRB 101 is used to record the corresponding buffer positions and packet sizes in conjunction with the particular sequence number. As soon as packet loss is detected at the sender side, the send handler 104 can quickly resolve corre ^¬ sponding information of the puffer position of the lost data from the STRB 101 in order to retransmit the data.

Following prerequisites for the STRB 101 must be ful ^¬ filled:

- A data structure to record the information of a packet, including: sequence number, position of the first byte of data packet within the SRB, and packet size. - An array with sufficient length to record sent packets must be allocated. Each element comprises of an array, described above.

The STRB 101 has only a STRB-FP 800 and a STRB-WP 801, not a RP:

- The STRB-FP 800 indicates the actual released position in the STRB 101, all packets with sequence numbers less than the sequence number on the STRB-FP 800 are already acknowledged by remote side application. The STRB-FP 800 should only be moved by reader thread.

- The STRB-WP 801 indicates the actual write position in the STRB 101, the packet with the sequence number on

STRB-WP 801 is the recent transmitted packet. The STRB- WP 801 should only be moved by writer thread.

Fig. 8 shows a schematic representation of an interaction of the SRB- and STRB-methods within the receive handler 103 and the send handler 104.

Each time the send handler 104 sends a new data packet, which is fetched from the SRB 100, AddToken () -method is called to record corresponding packet information within the STRB 101. Once an ACK is received, the receive han ^¬ dler 103 processes it and calls Del Token () -method to move the STRB-FP 800 of the STRB 101 correspondingly; if Del- Token () successfully implemented, the FreeChunk () -method is called to release acknowledged data from the SRB 100.

If a packet retransmission must be performed, the receive handler 103 passes only the sequence number to the send handler 104, so the send handler 104 calls GetToken ()- method to get corresponding packet information from the STRB 101 in order to call the GetPrevChunk () -method to retransmit it.

Referring to Fig. 9 and 10, the functionality of the re- ceive memory ring buffer (RRB) 102 is described in further detail. Fig. 9 shows a schematic representation of five methods which can be implemented in the receive mem ^¬ ory ring buffer (RRB) 102. Fig. 10 shows a schematic representation of an interaction of the methods depicted in Fig. 9.

The RRB 102 is used in order to receive data and store them at the right position. The basic functionality of

the RRB 102 is similar to those of the SRB 100. However, it must be extended by some more means, since packet loss and the corresponding retransmission always has to be taken into account.

Besides the pointers RP , WP, and FP, which are referred to as RPl, WPl, and FPl, additional pointers, namely RP2 and WP2, are introduced within the RRB 102:

- A write pointer (WPl) can only be used by writer thread, to indicate the actual write position. If a data chunk has been stored successfully into the RRB 102, the WPl should be moved ahead by the length of the stored chunk. When the sequence number of the received packet is not the consecutive one, a packet loss has been detected and the stored chunk has to be moved ahead to the proper position for that sequence number. So a gap in the buffer is arisen, in which retransmit ^¬ ted packets must be stored. When retransmitted packets arrive, the WPl will be moved backwards, to fill the gap.

- In contrast to the WPl, a additional write pointer WP2 is never moved back, and so it depicts the outer bound of the RRB 102. So, it records the position of received packet with currently largest sequence number. - A read pointer (RPl) has the same functionality as the SRB-RP 300 within the SRB 100.

- An additional read pointer (RP2) marks the upper bound of the consecutive data chunks for reading, and it can only be moved by writer thread. Once packet loss is de- tected, the RP2 points at the position of the last in- order and consecutive received data packet. It moves forwards only if all data packets are received in-order and consecutive, or if the first gap within the buffer

- I l ^¬

ls filled. Therefore the reader thread can read the stored data between the RPl and RP2.

- A FP has the same functionality as the SRB-FP 302 in the SRB 100.

Referring now to Fig. 9, the RRB 102 provides five major methods to provide receiver buffer operations. Prerequi ^¬ sites for the RRB 102 methods:

- One additional data structure - here called loss map - must be defined. This map is introduced in order to re ^¬ cord all the information about lost packets - (the first lost packet sequence number, the number of lost packets, the retransmission begin position in the RRB 102, the reserved free space for these packets, etc.) . Since it is not known if there are any irregular packets during retransmission, free space is reserved for packet retransmission as <number of total lost packets> * maxPayloadsize . The maxPayloadSize is the maximal predefined data packet size transmitted over the net- work.

- Another data structure - here called irregular map - for recording the begin position and the length of a buffer hole, due to special cases of irregular packet loss. Since this irregular map data structure is ac- cessed from a reader thread as well as from writer thread, its access has to be synchronized with a mutex. However, in well configured networks, transmission of irregular packets should happen quite seldom (< 1 % packet loss) .

Referring to Fig. 10, three out of the five methods de ^¬ scribed above can be used from within the writer thread

(receive handler 103), namely GetNextWritePos () - , Move- WritePos () - , and RcvStore () -methods .

GetNextWritePos () returns the position, at which next data packet should be stored. This could be an in-order and consecutive data packet, but also could be an incom ^¬ ing retransmitted packet.

If a data packet is successfully received into the posi- tion provided by GetNextWritePos (), MoveWritePos () is called to move the WPl. After moving WPl MoveWritePos () has to test if this is a retransmitted one packet, in which case it has to also test whether any irregular packets cause a hole in reserved buffer space and update irregular map if a hole does exist. If the recently re ^¬ ceived data packet is in-order and consecutive, RP2 is also moved equal to WPl by MoveWritePos () . But if the re ^¬ cently received data packet is stored consecutive into RRB after packet loss, only the WP2 should be moved equal to WPl by MoveWritePos () to mark the currently received packet with largest sequence number.

If a packet loss is detected in receive handler, RcvStore () is used to insert the corresponding lost in- formation into loss map. The RcvGetNextChunk () -method is used by the API-Thread in order to fetch received data. The RPl is moved, when data are fetched.

RcvFreeChunk () -method is called by API-thread to move FP after successful return from RcvGetNextChunk () _r in order to free this space for further data packet reception.

The features of the invention as disclosed in the above description, in the claims and in the drawing may be of importance for the implementation of the various embodi ^¬ ments of the invention both individually and in any de- sired combination.