lwip英文

Design and Implementation of the lwIP TCP/IP Stack Swedish Institute of Computer Science February 20, 2001 Adam Dunkels adam@sics.se Abstract lwIP is an implementation of the TCP/IP protocol stack. The focus of the lwIP stack is to reduce memory usage and code size, making lwIP suitable for use in small clients with very limited resources such as embedded systems. In order to reduce processing and memory demands, lwIP uses a tailor made API that does not require any data copying. This report describes the design and implementation of lwIP. The algorithms and data struc- tures used both in the protocol implementations and in the sub systems such as the memory and bu®er management systems are described. Also included in this report is a reference manual for the lwIP API and some code examples of using lwIP. Contents 1 Introduction 1 2 Protocol layering 1 3 Overview 2 4 Process model 2 5 The operating system emulation layer 3 6 Bu®er and memory management 3 6.1 Packet bu®ers | pbufs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 7 Network interfaces 5 8 IP processing 7 8.1 Receiving packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.2 Sending packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.3 Forwarding packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 8.4 ICMP processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 9 UDP processing 8 10 TCP processing 9 10.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 10.2 Data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 10.3 Sequence number calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10.4 Queuing and transmitting data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10.4.1 Silly window avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.5 Receiving segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.5.1 Demultiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.5.2 Receiving data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.6 Accepting new connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.7 Fast retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.8 Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.9 Round-trip time estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 10.10Congestion control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 11 Interfacing the stack 15 12 Application Program Interface 16 12.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 12.2 Implementation of the API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 13 Statistical code analysis 17 13.1 Lines of code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 13.2 Object code size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 14 Performance analysis 20 15 API reference 21 15.1 Data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 15.1.1 Netbufs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 15.2 Bu®er functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 15.2.1 netbuf new() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 15.2.2 netbuf delete() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 15.2.3 netbuf alloc() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 15.2.4 netbuf free() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 15.2.5 netbuf ref() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 15.2.6 netbuf len() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 15.2.7 netbuf data() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 15.2.8 netbuf next() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 15.2.9 netbuf ¯rst() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 15.2.10netbuf copy() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 15.2.11netbuf chain() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 15.2.12netbuf fromaddr() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 15.2.13netbuf fromport() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16 Network connection functions 25 16.0.14netconn new() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16.0.15netconn delete() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16.0.16netconn type() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16.0.17netconn peer() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16.0.18netconn addr() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 16.0.19netconn bind() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 16.0.20netconn connect() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 16.0.21netconn listen() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 16.0.22netconn accept() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 16.0.23netconn recv() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 16.0.24netconn write() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 16.0.25netconn send() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 16.0.26netconn close() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 17 BSD socket library 30 17.1 The representation of a socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 17.2 Allocating a socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 17.2.1 The socket() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 17.3 Connection setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 17.3.1 The bind() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 17.3.2 The connect() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 17.3.3 The listen() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 17.3.4 The accept() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 17.4 Sending and receiving data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 17.4.1 The send() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 17.4.2 The sendto() and sendmsg() calls . . . . . . . . . . . . . . . . . . . . . . . 34 17.4.3 The write() call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17.4.4 The recv() and read() calls . . . . . . . . . . . . . . . . . . . . . . . . . . 35 17.4.5 The recvfrom() and recvmsg() calls . . . . . . . . . . . . . . . . . . . . . 36 18 Code examples 36 18.1 Using the API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 18.2 Directly interfacing the stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Bibliography 41 2 PROTOCOL LAYERING 1 Introduction Over the last few years, the interest for connecting computers and computer supported devices to wireless networks has steadily increased. Computers are becoming more and more seamlessly integrated with everyday equipment and prices are dropping. At the same time wireless networking technologies, such as Bluetooth [HNI+98] and IEEE 802.11b WLAN [BIG+97], are emerging. This gives rise to many new fascinating scenarios in areas such as health care, safety and security, transportation, and processing industry. Small devices such as sensors can be connected to an existing network infrastructure such as the global Internet, and monitored from anywhere. The Internet technology has proven itself °exible enough to incorporate the changing network environments of the past few decades. While originally developed for low speed networks such as the ARPANET, the Internet technology today runs over a large spectrum of link technologies with vastly di®erent characteristics in terms of bandwidth and bit error rate. It is highly advantageous to use the existing Internet technology in the wireless networks of tomorrow since a large amount of applications using the Internet technology have been developed. Also, the large connectivity of the global Internet is a strong incentive. Since small devices such as sensors are often required to be physically small and inexpensive, an implementation of the Internet protocols will have to deal with having limited computing resources and memory. This report describes the design and implementation of a small TCP/IP stack called lwIP that is small enough to be used in minimal systems. This report is structured as follows. Sections 2, 3, and 4 give an overview of the lwIP stack, Section 5 describes the operating system emulation layer, Section 6 describes the memory and bu®er management. Section 7 introduces the network interface abstraction of lwIP, and Sections 8, 9, and 10 describe the implementation of the IP, UDP and TCP protocols. The Sections 11 and 12 describe how to interface with lwIP and introduce the lwIP API. Sections 13 and 14 analyze the implementation. Finally, Section 15 provides a reference manual for the lwIP API and Sections 17 and 18 show various code examples. 2 Protocol layering The protocols in the TCP/IP suite are designed in a layered fashion, where each protocol layer solves a separate part of the communication problem. This layering can serve as a guide for designing the implementation of the protocols, in that each protocol can be implemented separately from the other. Implementing the protocols in a strictly layered way can however, lead to a situation where the communication overhead between the protocol layers degrades the overall performance [Cla82a]. To overcome these problems, certain internal aspects of a protocol can be made known to other protocols. Care must be taken so that only the important information is shared among the layers. Most TCP/IP implementations keep a strict division between the application layer and the lower protocol layers, whereas the lower layers can be more or less interleaved. In most operating systems, the lower layer protocols are implemented as a part of the operating system kernel with entry points for communication with the application layer process. The application program is presented with an abstract view of the TCP/IP implementation, where network communication di®ers only very little from inter-process communication or ¯le I/O. The implications of this is that since the application program is unaware of the bu®er mechanisms used by the lower layers, it cannot utilize this information to, e.g., reuse bu®ers with frequently used data. Also, when the application sends data, this data has to be copied from the application process' memory space into internal bu®ers before being processed by the network code. The operating systems used in minimal systems such as the target system of lwIP most often do not maintain a strict protection barrier between the kernel and the application processes. This allows using a more relaxed scheme for communication between the application and the lower layer protocols by the means of shared memory. In particular, the application layer can be made aware of the bu®er handling mechanisms used by the lower layers. Therefore, the application can 1 4 PROCESS MODEL more e±ciently reuse bu®ers. Also, since the application process can use the same memory as the networking code the application can read and write directly to the internal bu®ers, thus saving the expense of performing a copy. 3 Overview As in many other TCP/IP implementations, the layered protocol design has served as a guide for the design of the implementation of lwIP. Each protocol is implemented as its own module, with a few functions acting as entry points into each protocol. Even though the protocols are implemented separately, some layer violations are made, as discussed above, in order to improve performance both in terms of processing speed and memory usage. For example, when verifying the checksum of an incoming TCP segment and when demultiplexing a segment, the source and destination IP addresses of the segment has to be known by the TCP module. Instead of passing these addresses to TCP by the means of a function call, the TCP module is aware of the structure of the IP header, and can therefore extract this information by itself. lwIP consists of several modules. Apart from the modules implementing the TCP/IP protocols (IP, ICMP, UDP, and TCP) a number of support modules are implemented. The support modules consists of the operating system emulation layer (described in Section 5), the bu®er and memory management subsystems (described in Section 6), network interface functions (described in Section 7), and functions for computing the Internet checksum. lwIP also includes an abstract API, which is described in Section 12. 4 Process model The process model of a protocol implementation describes in which way the system has been di- vided into di®erent processes. One process model that has been used to implement communication protocols is to let each protocol run as a stand alone process. With this model, a strict protocol layering is enforced, and the communication points between the protocols must be strictly de¯ned. While this approach has its advantages such as protocols can be added at runtime, understanding the code and debugging is generally easier, there are also disadvantages. The strict layering is not, as described earlier, always the best way to implement protocols. Also, and more important, for each layer crossed, a context switch must be made. For an incoming TCP segment this would mean three context switches, from the device driver for the network interface, to the IP process, to the TCP process and ¯nally to the application process. In most operating systems a context switch is fairly expensive. Another common approach is to let the communication protocols reside in the kernel of the operating system. In the case of a kernel implementation of the communication protocols, the application processes communicate with the protocols through system calls. The communication protocols are not strictly divided from each other but may use the techniques of crossing the protocol layering. lwIP uses a process model in which all protocols reside in a single process and are thus sep- arated from the operating system kernel. Application programs may either reside in the lwIP process, or be in separate processes. Communication between the TCP/IP stack and the applica- tion programs are done either by function calls for the case where the application program shares a process with lwIP, or by the means of a more abstract API. Having lwIP implemented as a user space process rather than in the operating system kernel has both its advantages and disadvantages. The main advantage of having lwIP as a process is that is portable across di®erent operating systems. Since lwIP is designed to run in small operating systems that generally do not support neither swapping out processes not virtual memory, the delay caused by having to wait for disk activity if part of the lwIP process is swapped or paged out to disk will not be a problem. The problem of having to wait for a scheduling quantum before getting a chance to service requests still is a problem however, but there is nothing in the design 2 6 BUFFER AND MEMORY MANAGEMENT of lwIP that precludes it from later being implemented in an operating system kernel. 5 The operating system emulation layer In order to make lwIP portable, operating system speci¯c function calls and data structures are not used directly in the code. Instead, when such functions are needed the operating system emulation layer is used. The operating system emulation layer provides a uniform interface to operating system services such as timers, process synchronization, and message passing mechanisms. In principle, when porting lwIP to other operating systems only an implementation of the operating system emulation layer for that particular operating system is needed. The operating system emulation layer provides a timer functionality that is used by TCP. The timers provided by the operating system emulation layer are one-shot timers with a granularity of at least 200 ms that calls a registered function when the time-out occurs. The only process synchronization mechanism provided is semaphores. Even if semaphores are not avaliable in the underlying operating system they can be emulated by other synchronization primitives such as conditional variables or locks. The message passing is done through a simple mechanism which uses an abstraction called mailboxes. A mailbox has two operations: post and fetch. The post operation will not block the process; rather, messages posted to a mailbox are queued by the operating system emulation layer until another process fetches them. Even if the underlying operating system does not have native support for the mailbox mechanism, they are easily implemented using semaphores. 6 Bu®er and memory management The memory and bu®er management system in a communication system must be prepared to accommodate bu®ers of very varying sizes, ranging from bu®ers containing full-sized TCP segments with several hundred bytes worth of data to short ICMP echo replies consisting of only a few bytes. Also, in order to avoid copying it should be possible to let the data content of the bu®ers reside in memory that is not managed by the networking subsystem, such as application memory or ROM. 6.1 Packet bu®ers | pbufs A pbuf is lwIP's internal representation of a packet, and is designed for the special needs of the minimal stack. Pbufs are similar to the mbufs used in the BSD implementations. The pbuf structure has support both for allocating dynamic memory to hold packet contents, and for letting packet data reside in static memory. Pbufs can be linked together in a list, called a pbuf chain so that a packet may span over several pbufs. Pbufs are of three types, PBUF RAM, PBUF ROM, and PBUF POOL. The pbuf shown in Figure 1 represents the PBUF RAM type, and has the packet data stored in memory managed by the pbuf subsystem. The pbuf in Figure 2 is an example of a chained pbuf, where the ¯rst pbuf in the chain is of the PBUF RAM type, and the second is of the PBUF ROM type, which means that it has the data located in memory not managed by the pbuf system. The third type of pbuf, PBUF POOL, is shown in Figure 3 and consists of ¯xed size pbufs allocated from a pool of ¯xed size pbufs. A pbuf chain may consist of multiple types of pbufs. The three types have di®erent uses. Pbufs of type PBUF POOL are mainly used by network device drivers since the operation of allocating a single pbuf is fast and is therefore suitable for use in an interrupt handler. PBUF ROM pbufs are used when an application sends data that is located in memory managed by the application. This data may not be modi¯ed after the pbuf has been handed over to the TCP/IP stack and therefore this pbuf type main use is when the data is located in ROM