Abstract:
The present invention is directed to a method and system of memory management that features dual buffer rings, each of which includes descriptors identifying addresses of a memory space, referred to as buffers, in which portions of data packets are stored. Typically, the header segment of each data packet is stored at a first set of a plurality of buffers, and the portion of the payload segment that does not fit among the buffers of the first set is stored in the buffers of a second set. In this manner, the size of the individual buffers associated with the first buffer rings may be kept to the smallest size of useable storage space, and the buffers corresponding to the second buffer ring may be arbitrary in size.

Description:
BACKGROUND OF THE INVENTION 
     A substantial portion of computer systems communicate over networks using transmission of data in packetized format at very high data rates. A common network communication protocol is known as the Ethernet and transmits data packets between different computer systems at rates of 1 Gbit/second or more. 
     Upon receipt of a data packet a computer system typically stores the data in a packet buffer before the data is provided to the computer processes for which the data is intended. Once the data is provided to the intended processes, the packet buffer in which the data was stored are freed to accept additional data. Often, the rate at which data is received is different from the rate at which the computer system frees packet buffers to accept additional data, which may result in buffer overflow. Many attempts have been undertaken to avoid buffer overflow while avoiding use of excessive amounts of buffer memory. 
     In one attempt, a packet receiving-transmitting method for use on a packet-switching network, such as the Ethernet, stores each received packet in a packet buffer of a fixed size and associated with a single descriptor. Based on a threshold logical segmentation size determined by the network protocol, each packet buffer is partitioned into a plurality of segments, each having an ending point linked to an Early Receive/Transmit interrupt signal with the ending point of the packet buffer being linked to an OK interrupt signal. In response to each Early Receive/Transmit interrupt signal, the packet data stored are retrieved and forwarded; and in response to the OK interrupt signal, all the remaining packet data in the packet buffer are retrieved and forwarded. After this, a write-back operation is performed on the associated descriptor so as to reset the descriptor to unused status. 
     Thus, there is a need to improve management of memory used to receive data packets. 
     SUMMARY 
     A method and system of memory management includes dual buffer rings, each of which has descriptors identifying addresses of a memory space, referred to as buffers, in which portions of data packets are stored. The header segment of each data packet is stored in a first set of a plurality of buffers, and the portion of the payload segment that does not fit among the buffers of the first set is stored in the buffers of a second set of the plurality of buffers. To that end, the method includes defining a plurality of buffers; establishing a first buffer ring having a plurality of descriptors identifying a first set of the plurality of buffers, with the buffers of the first set having a first size; and defining a second buffer ring having a plurality of identifiers identifying a second set of buffers, with the buffers of the second set having a second size that is different from the first size. The system includes a memory space having first and second buffer rings with a plurality of descriptors, a first sub-group of which is contained in the first buffer ring and identifies a first set of the plurality of buffers, and a second sub-group of which is contained in the second buffer ring and identifies a second set of buffers; and a communication driver to associate the first and second sets of buffers with the first and second buffer rings so that each of the buffers of the first set has a size that is different from the size of each of the buffers of the second set. A network interface is in data communication with the communication driver; the network interface is connected to receive a data packet having a header segment and a payload segment and records, in a first descriptor of the second buffer ring, a location of the payload segment and records, in a first descriptor of the first ring, a location of the header segment and information corresponding to the first descriptor of the second buffer ring. These and other embodiments are described more fully below. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a computer network in which the present invention may be practiced; 
         FIG. 2  is a block diagram of an example of a computing system employed in the computer network shown in  FIG. 1 , in accordance with the present invention; 
         FIG. 3  illustrates a simplified plan view of an Ethernet frame in accordance with the present invention; 
         FIG. 4  is a simplified plan view of a mapping of memory space, shown in  FIG. 2 , in accordance with the present invention; 
         FIG. 5  is a simplified plan view of an example of a descriptor used in memory space, shown in  FIG. 2 , in accordance with the present invention; 
         FIG. 6  is a flow diagram showing a process of initializing the mapping, shown in  FIG. 4 , of the memory space, shown in  FIG. 2 , in accordance with the present invention; 
         FIG. 7  is a flow diagram showing the operation of receiving the Ethernet frame, shown in  FIG. 3 , into the memory space, shown in  FIG. 2 , mapped, as shown in  FIG. 4 , in accordance with the present invention; and 
         FIG. 8  is a flow diagram showing the operation of receiving the Ethernet frame shown in  FIG. 3 , into the memory space, shown in  FIG. 2 , mapped, as shown in  FIG. 4 , in accordance with an alternate embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Referring to  FIG. 1 , a network is shown that includes a plurality of networked computer systems, for example data terminal equipment  10 , in data communication over one or more nodes  12 . In one embodiment, node  12  comprises data communications equipment (DCE), which may be, for example, routers associated with a network. The network may be any configuration, such as a local area network (LAN), a publicly accessible network, such as a public switched telephone network over ASDL telephone lines or large bandwidth trunks, such as T1 or OC3 service more commonly associated with a wide area network, such as the Internet. 
     Referring to  FIG. 2 , one or more of the computer systems  10  has a system unit  20  with one or more system buses  22  placing various components of the system in data communication. For example, a microprocessor  24  is placed in data communication with a memory space  26  of system unit  20  that may include read only memory (ROM), random access memory (RAM) and various register memory via the system bus  22 . To that end, memory space  26  contains, among other code, an operating system  52  for controlling basic hardware operation including disk drives  30  and  32 , as well as keyboard  34  and other input/output devices. In addition, application programs such as browser  54  are also loaded into memory space  26  so that a microprocessor  24  may operate upon the same. 
     Memory management device  36  is in data communication with the system bus  22  to control direct memory access (DMA) operations. DMA operations include passing data among memory space  26  and hard disk drive  30  and floppy disk drive  32  and network interfaces. Also in data communication with system bus  22  are various I/O controllers: a keyboard controller  38 , a mouse controller  40 , a video controller  42 , and an audio controller  44 . Keyboard controller  38  provides a hardware interface for the keyboard  34 , the mouse controller  40  provides the hardware interface for a mouse  46 , or other point and click device, and video controller  40  provides a hardware interface for a display  48 . Operating system  52  may be a commodity operating system such as WINDOWS® XP®, or other known operating system. Browser  54  may be any of a differing number of Internet access tools, including an HTTP-compliant web browser having a JavaScript interpreter, such as FIREFOX®, NETSCAPE NAVIGATOR®, INTERNET EXPLORER® and the like. 
     Referring to both  FIGS. 1 and 2 , a network interface  50  enables data communication over the network facilitating data transmission speeds that are dependent upon the network protocol employed. Although network interface  50  may facilitate communication using any known protocol, such as TCP/IP, in the present example, network interface  50  facilitates communication between computer systems  10  using the Ethernet protocol, with node  12  being referred to as data communication equipment (DCE)  12  and computer systems  10  being referred to as data terminal equipment (DTE)  10 . To that end, DCE  12  communicates by sending data packets, in a frame  56 , shown more clearly in  FIG. 3 . 
     Referring to both  FIGS. 2 and 3 , an Ethernet frame  56  is shown including four segments of information,  57 - 60 . Ethernet header segment  57  provides information to facilitate handling of frame  56  by network interface  50 . Internet Protocol (IP) header segment  58  includes information to facilitate routing of frame  56  over a network. TCP header segment  59  includes information to facilitate delivery of the entire frame  56  to a destination of the network. Segments  57 - 59  are commonly referred to as a header segment  64  of frame  56 , and segment  60  is referred to as a payload segment  65  of frame  56 . 
     Control of communication between system unit  20  with other DTEs  10  through network interface  50  is achieved employing specialized software code, referred to as a communication driver  70 . Communication driver  70  is loaded into memory space  26  upon initialization of system unit  20  and generates in memory space  26  two receive rings  72  and  74  that are populated with information concerning first and second sets of buffers  76  and  78 . 
     Referring to both  FIGS. 2 and 4 , each of receive rings  72  and  74  include a plurality of descriptors  80 - 85  and  90 - 95 , respectively. Each of descriptors  80 - 85  identifies individual buffers  100 - 105  of first set  76 , and descriptors  90 - 95  identify individual buffers  110 - 115  of second set  78 . In the present example, descriptor  80  identifies buffer  100 , descriptor  81  identifies buffer  101 , descriptor  82  identifies buffer  102 , descriptor  83  identifies buffer  103 , descriptor  84  identifies buffer  104  and descriptor  85  identifies buffer  105 . Descriptor  90  identifies buffer  110 , descriptor  91  identifies buffer  111 , descriptor  92  identifies buffer  112 , descriptor  93  identifies buffer  113 , descriptor  94  identifies buffer  114  and descriptor  95  identifies buffer  115 . The size of each of buffers  100 - 105  and  110 - 115  is a function of the operating system  52  and operating efficiency desired. Although each receive ring  72  and  74  includes six descriptors each having a corresponding buffer, it should be noted that this is for illustration purposes only, and an actual receive ring may have any number of descriptors, and in one embodiment, each receive ring has any number of descriptors desired, dependent upon the application and computing resources available. 
     Referring to both  FIGS. 3 and 4 , for example, it is desired that the entire frame  56  be stored among buffers  100 - 105  and  110 - 115 . However, it has proved advantageous to store header segment  64  in a buffer different from the buffer in which some or all of payload segment  65  is stored, because payload segment  65  may vary in size such that the same may be substantially larger than header segment  64 . Header segment  64  typically maintains a size of a couple of hundred bytes of information. As a result, it is useful to provide some of buffers  100 - 105  and  110 - 115  with a size capable of storing the anticipated size of the entire payload segment  65  included in frame  56 , as well as header segment  64 . However, it is also desired to maximize the number of different frames  56  that may be stored in the memory available by first and second sets  76  and  78  while avoiding buffer overflow. This is achieved with the presence of the first and second buffer rings  72  and  74 . 
     Buffers  100 - 105  of buffer set  76  identified by descriptors  80 - 85  of first buffer ring  72  may have a common size of approximately 1.5 kilobytes. Buffers  110 - 115  of buffer set  78  identified by descriptors  90 - 95  of second buffer ring  74  may have a common size that is larger than the size of buffers  100 - 105 . In one example, the size of buffers  110 - 115  is the maximum allotted by the operating system, e.g., 4 kilobytes. However, the size of buffers  110 - 115  may be established to be no greater than the anticipated size of payload segment  65 . In this manner, descriptors  80 - 85  of first buffer ring  72  are employed for header segments  64  and payload segments  65  of frame  56 . Descriptors  90 - 95  are employed for payload segments  65  that may not be properly placed in buffers  100 - 105 . 
     Referring to  FIGS. 2, 3 and 4 , typically, descriptors  80 - 85  define, between adjacent buffers  100 - 105  in which information of header segment  64  is stored, a predetermined number of buffers  100 - 105  for storage of information of payload segment  65  corresponding to header segment  64 . For example, in one embodiment, buffers  100  and  103  may be reserved for storage of the information in header segment  64  for two different frames  56 , as well as the payload segment  65  of respective frames  56  that do not exceed the storage capacity of buffers  100  and  103 . In this fashion, buffers  100  and  103  define a first chunk of set  76 . Buffers  101 and  102  are reserved for the storage of the portion of payload segment  65  that could not be stored by buffer  100 , and buffers  104  and  105  are reserved for the storage of the portion of payload segment  65  that could not be stored by buffer  103 . Buffers  101 ,  102 ,  104  and  105  define a second chunk of set  76 , which may be the same size as, as larger as or smaller than either of buffers  100  and  103 . For example, buffers  100  and  103  may be sized so as to be just slightly larger than anticipated header segments  64 . Buffers  101 ,  102 ,  104  and  105 , for example, may be 1.5K in size or larger. As a result, descriptors  80  and  83  identify sequential addresses of memory space  26 , with the understanding that sequential addresses are addresses that arranged in ascending or descending order. In one embodiment, the sequential addresses may be regularly spaced from one another so that each address identifies a block of memory of uniform size. Descriptors  81 ,  82 ,  84  and  85  identify fragmented addresses in memory space, with the understanding that fragmented addresses are addresses that do not designate contiguous memory segments. Thus, in one embodiment, buffers  100 - 105  may be discontinuous or scattered in memory space  26 , although each buffer individually identifies a contiguous block of memory. Assuming a frame  56  is received at network interface  50  with the aggregate size of both header segment  64  and payload segment  65  being no greater than 1.5 kilobytes, then the entire frame  56  may be recorded in first buffer set  76 , i.e., in buffer  100  or  103 . However, were the aggregate size of both header segment  64  and payload segment  65  greater than 1.5 kilobytes, then header segment  64  and a portion of payload segment  65  would be stored in either buffer  100  or buffer  103 , with the remaining portion of payload segment  65  being in either buffers  101 - 102  or buffers  104 - 105 , respectively. If the remaining payload segment  65  were greater than  3  kilobytes, the portion of payload segment  65  beyond the storage capacity of the aggregate storage capacity of either buffers  101 - 102  or  104 - 105  may be stored among one or more buffers  110 - 115  of second buffer set  78 . The descriptor  82  or  85  pointing to the buffer  102  or  105  having the last portion of payload segment  65  in buffer set  76  would set NEXT_RING flag  124  to indicate that the rest of payload segment  65  is located in descriptor  90 - 95 . As described below with reference to  FIG. 5 , NEXT_RING flag  124  is information corresponding to one of descriptors  90 - 95  of second ring  74 . 
       FIG. 5  shows, by way of example, a block of information  116  for descriptors  80 - 85 . In this embodiment, block of information  116  includes data address information  118  such as the address of memory space  26  corresponding to one of buffers  100 - 105  in which portions of header  64  and/or payload segment  65  are stored, the end of packet flag  120  that identifies one of descriptors  80 - 85  as being the last descriptor for frame  56 , a dataLength field  122  that defines the length of data store, and a NEXT_RING flag  124 , indicating that a descriptor  90 - 95  points to a portion of payload segment  65  corresponding to frame  56 . It should be understood that the block of information for descriptors  90 - 95  would be substantially identical to the block of information  116 , except for the presence of NEXT_RING flag  124  being omitted and would include data address information corresponding to one of buffers  110 - 115 . 
     Referring to  FIGS. 2-4 and 6 , during initialization of system unit  20 , communication driver  70  defines first and second sets  76  and  78  of buffers  100 - 105  and  110 - 115 , respectively at function  200 . At function  202 , communication driver  70  establishes buffer ring  72  by including a plurality of descriptors  80 - 85  identifying first set  76  of the plurality of buffers  100 - 105 , with the buffers of the first set  76  having a first size. At function  204 , communication driver  70  establishes buffer ring  74  by including a plurality of descriptors  90 - 95  identifying second set  78  of plurality of buffers  110 - 115 , with the buffers of second set  76  having a second size, which may be larger than or the same size as buffers  100 - 105 . It is also contemplated that the first size is different among the different buffers  100 - 105  of first set  76 . For example, buffers in which the addresses of memory space are linear may comprise a first chunk of the first size, and the buffers  100 - 105  of fragmented memory addresses may comprise a second chunk of a different size which may be the same as or larger than the size of each of the buffers of the first chunk. 
     Referring to  FIGS. 2-4 and 7 , after initialization of buffer rings  72  and  74 , as described above with reference to  FIG. 6 , operation of system unit  20  in response to receiving frame  56  at network interface  50  at function  300 , results in network interface  50  determining whether sufficient memory is available among first set  76  to record frame  56 , at function  302 . This determination is efficiently ascertained by identifying whether any linear portions of first set  76  are available in which to store header segment  64  of frame  56 . To that end, start and end data pointers may be compared so that were the start data pointer to identify the next descriptor after the end-data, it may be ascertained that all the descriptors are full. Writing to the next descriptor will over-right the first “read from” descriptor. If sufficient space is not available in first set  76 , network interface  50  drops frame  56  at function  304 . Following function  304 , the process proceeds to function  318 , discussed more fully below. 
     Were it determined at function  302  that sufficient memory is available to store frame  56 , then at function  308 , network interface  50  determines whether the entire payload segment  65  may be stored in first buffer set  76 . If so, at function  310  appropriate descriptors  80 - 81  of first receive ring  72  are updated to identify where among buffers  100 - 105  header segment  64  and payload segment  65  are stored. No descriptors  90 - 95  of second ring  74  are allocated to frame  56 , which has a size such that the entire payload segment  65  may be stored among memory buffers  100 - 105  of first set  76  of memory buffers. Were it determined at function  308  that only a portion of payload segment  65  may be stored among buffers  100 - 105  of first set  76 , then header segment  64 , along with a portion of payload segment  65 , is stored in one of buffers  110 - 115  having sequential addresses at function  312 . At function  314 , a first portion of payload segment  65  is stored among buffers of first set  76 . The remaining portions of payload segment  65 , i.e., a second portion, is stored among buffers  110 - 115  of second set  78  at function  316 . To that end, one of descriptors  80 - 85  associated with the buffer  100 - 105  in which the end of the portion of payload segment  65  recorded in first set  76  is recorded includes NEXT_RING flag descriptor information  124 . Thereafter, it would be determined whether there exist any additional frames  56  for recording among first and second buffer sets  76  and  78  at function  318 . If there were, the process would return to function  300 ; otherwise, function  318  repeats. Function  318  is also undertaken following function  310 . 
     Referring to  FIGS. 2-4 and 8 , in accordance with another embodiment, only header segment  64  is stored in buffers  100 - 105  of first set  76 . Each payload segment  65  of each frame  56  is stored in buffers  110 - 115  of second set  78 . As a result, descriptors  80 - 85  of first ring  72  identify only header segment  64  information, and descriptors  90 - 95  of second ring  74  identify only payload segment  65  information. In response to receiving frame  56  at network interface  50  at function  400 , network interface  50  determines whether sufficient memory is available among first set  76  to record header segment  64  of frame  56 , at function  402 , as discussed above. If sufficient space is not available in first set  76 , network interface  50  drops frame  56  at function  404 . Following function  404 , the process proceeds to function  412 , discussed more fully below. Were it determined at function  402  that sufficient memory is available to store frame  56 , then at function  408 , network interface  50  identifies the appropriate descriptors  80 - 85  of first receive ring  72  in order to identify where among buffers  100 - 105  header segment  64  is stored. At function  410 , network interface  50  identifies the appropriate descriptors  90 - 95  of second receive ring  74  in order to identify where among buffers  110 - 115  header segment  64  is stored. Thereafter, it would be determined whether there exist any additional frames  56  for recording among first and second buffer sets  76  and  78  at function  412 . If there were, the process would return to function  400 ; otherwise, function  412  repeats. 
     It should be understood that buffers  110 - 115  may be established to have a size that is the same as, as small as, or larger than buffers  100 - 105 . However, it is also conceivable that the size of buffers  110 - 115  may be arbitrarily determined based upon the size of payload segment  65 . As a result, during function  410 , network interface  50  may establish a single descriptor  90 - 95  to identify memory addresses among second set  78  that are different from the memory addresses established in the same descriptor upon initialization of system unit  20 . While it is conceivable that the entire address space associated with second set  78  may be used to store a single payload segment  65 , typically, the size of the address space identified by one of descriptors  90 - 95  is delimited by operating system  52 . As a result, it is possible that a single payload segment  65  may be stored among two or more buffers  110 - 115  of different sizes, one of which may be the maximum size permitted by operating system  52 , with the remaining buffers  110 - 115  being smaller than the maximum size permitted by operating system  52 . 
     The embodiments of the present invention described above are exemplary. Many changes and modifications may be made to the disclosure recited above while remaining within the scope of the invention. For example, the present examples discuss two receive rings. However, receive rings in addition to the two receive rings discussed above may be included. Additionally, the present invention may be implemented in software, firmware or as an abstract of a physical computer system known in the art as a virtual machine or a combination of software, firmware and a virtual machine. With respect to implementing the present invention as a virtual machine, expression of the invention may be either as virtual system hardware, guest system software of the virtual machine or a combination thereof. The scope of the invention should, therefore, be limited not to the above description, but instead should be determined with reference to the appended claims along with their full scope of equivalents.