Unix has become synonymous with high quality networking
and today's Unix users depend on having reliable, responsive
network access. Unfortunately, this dependence means that
network trouble can make it impossible to get useful work
done and increasingly users and system administrators find
that a large part of their time is spent isolating and fixing
network problems. Problem solving requires appropriate diagnostic
and analysis tools and, ideally, these tools should
be available where the problems are-on Unix workstations.
To allow such tools to be constructed, a kernel must contain
some facility that gives user-level programs access to raw,
unprocessed network traffic.[7] Most of today's workstation
operating systems contain such a facility, e.g., NIT[10] in
SunOS, the Ultrix Packet Filter[2] in DEC's Ultrix and Snoop
in SGI's IRIX.
Unixは高品質ネットワーキングと同義になりました。
また、今日のUnixユーザは信頼できて反応する
ネットワーク・アクセスを持っていることを当てにします。
不運にも、この依存は、ネットワーク問題が有用な仕事を行うのを
不可能にすることができることを意味します。
また、ますます、ユーザとシステム管理者は、
それらの時間の大部分が費やされた分離し
固定ネットワーク問題であることを知ります。
問題解決は適切な診断と分析ツールを要求します。
また、理想的に、その問題がUnixワークステーションであるオン場合、
これらのツールは利用可能であるべきです。
構築されるそのようなツールを許可するために、
核は、ユーザレベル・プログラムに生で加工されていない
ネットワーク交通へのアクセスを与えるある
設備を含んでいなければなりません。[7]
今日のワークステーション・オペレーティング・システムのうちの
ほとんどはSunOSにそのような設備(例えばNIT[10])を含んでいます、
DECのUltrixの中のUltrixパケットフィルター[2]
またSGIのIRIXの中でスヌープします。
These kernel facilities derive from pioneering work done at
CMU and Stanford to adapt the Xerox Alto `packet filter' to a
Unix kernel[8]. When completed in 1980, the CMU/Stanford
Packet Filter, CSPF, provided a much needed and widely used
facility. However on today's machines its performance, and
the performance of its descendents, leave much to be de-
sired - a design that was entirely appropriate for a 64KB
PDP-11 is simply not a good match to a 16MB Sparcstation
2. This paper describes the BSD Packet Filter, BPF, a new
kernel architecture for packet capture. BPF offers substan-
tial performance improvement over existing packet capture
facilities-10 to 150 times faster than Sun's NIT and 1.5 to 20
times faster than CSPF on the same hardware and traffic mix.
The performance increase is the result of two architectural
improvements:
これらの核設備は、Unix核[8]にゼロックス・アルト「パケットフィルター」を
適応させるためにCMUとスタンフォードで終わった仕事の開拓に由来します。
1980年に完成した時、CMU/スタンフォードのパケットフィルター(CSPF)は
非常に必要とされ、広く用いられている設備を提供しました。
今日の機械上で(しかしながら)その業績およびその子孫の業績、
あるために多くを望むおく―64KB PDP-11に完全に適切だった設計は
単に16MBのSparcstation 2への良縁ではありません。
この論文はBSDパケットフィルター、
BPF(パケット捕獲用の新しい核アーキテクチャー)について記述します。
BPFは、既存のパケット上の実質的履行改良を提示します、
設備-10を捕らえる、に、サンのNITおよび1.5より150倍速く、に、
同じハードウェアおよび交通上のCSPFより20倍速く、
混合します。実行増加は2つの建築上の改良の結果です:
In this paper, we present the design of BPF, outline how it
interfaces with the rest of the system, and describe the new
approach to the filtering mechanism. Finally, we present
performance measurements of BPF, NIT, and CSPF which
show why BPF performs better than the other approaches.
この論文では、私たちが、BPFのデザインを示します、
概説する、どのように、それ、システムの残りとのインターフェース、
またろ過するメカニズムへの新しいアプローチについて記述します。
最後に、私たちは、なぜBPFが他のアプローチよりよく
実行するか示すBPF、NITおよびCSPFの性能測定を示します。
BPF has two main components: the network tap and the
packet filter. The network tap collects copies of packets from
the network device drivers and delivers them to listening applications.
The filter decides if a packet should be accepted
and, if so, how much of it to copy to the listening application.
Figure 1 illustrates BPF's interface with the rest of the system.
When a packet arrives at a network interface the link
level device driver normally sends it up the system protocol
stack. But when BPF is listening on this interface, the driver
first calls BPF. BPF feeds the packet to each participating process'
filter. This user-defined filter decides whether a packet
is to be accepted and how many bytes of each packet should
be saved. For each filter that accepts the packet, BPF copies
the requested amount of data to the buffer associated with that
filter. The device driver then regains control. If the packet
was not addressed to the local host, the driver returns from the
interrupt. Otherwise, normal protocol processing proceeds.
BPFは2つの主要なコンポーネントを持っています:
ネットワーク・タップおよびパケットフィルター。
ネットワーク・タップはネットワーク・デバイス・ドライバから
部のパケットを集めて、聞く適用にそれらを配達します。
フィルタは、パケットが受理されるべきかどうか決定します、
そして、そうならば、どのように、聞く適用にコピーするためにそれに非常に。
図1はBPFのインターフェースをシステムの残りで例証します。
パケットがネットワークインターフェイスに到着する場合、
リンク・レベル・デバイス・ドライバは
通常システム・プロトコル・スタックを上へそれを送ります。
しかし、BPFがこのインターフェース上で聞いている場合、
ドライバーは最初にBPFを呼びます。
BPFは各参加するプロセスのフィルタにパケットを与えます。
このユーザに定義されたフィルタは、
パケットが受理されることになっているかどうか
各パケットのどれだけのバイトを保存しなければならないか、決定します。
パケットを受理するフィルタごとについては、
BPFがそのフィルタに関連したバッファーに要求された量の
データをコピーします。
その後、デバイス・ドライバはコントロールを回復します。
パケットが地方のホストに出されなかった場合、
ドライバーは割り込みから戻ります。
そうでなければ、正常なプロトコル処理は進みます。
| Figure 1: | BPF Overview |
Since a process might want to look at every packet on a
network and the time between packets can be only a few
microseconds, it is not possible to do a read system call per
packet and BPF must collect the data from several packets
and return it as a unit when the monitoring application does
a read. To maintain packet boundaries, BPF encapsulates the
captured data from each packet with a header that includes a
time stamp, length, and offsets for data alignment.
プロセスがネットワーク上のすべてのパケットを見たいかもしれないし、
パケット間の時間が数マイクロセカンドだけでありえるので、
1つのパケット当たり読み取りシステムコールを行うことは可能ではありません。
また、BPFはいくつかのパケットからデータを集めるに違いないし、
モニタリング適用が読み取りを行う場合、
1ユニットとしてそれを返すに違いありません。
パケット境界を維持するために、
BPFは、タイムスタンプ、
長さおよびデータ整列のためのオフセットを含んでいる
ヘッダーを備えた各パケットからの捕らえられたデータをカプセルに入れます。
Because network monitors often want only a small subset of
network traffic, a dramatic performance gain is realized by
filtering out unwanted packets in interrupt context. To minimize
memory traffic, the major bottleneck in most modern
workstations, the packet should be filtered `in place' (e.g.,
where the network interface DMA engine put it) rather than
copied to some other kernel buffer before filtering. Thus, if
the packet is not accepted, only those bytes that were needed
by the filtering process are referenced by the host.
ネットワーク・モニターがネットワーク交通の小さな部分集合だけを
しばしば望むので、劇的な実行利得は、
割り込み情況中の望まれないパケットをろ過することにより実現されます。
メモリ交通(最も現代のワークステーション中の主なボトルネック)を
最小限にするために、フィルタリングの前に他のある
核バッファーにコピーされたのではなく
(例えばネットワークインターフェイスDMAエンジンがそれを置いたところで)、
パケットは適所にろ過されるべきです。
したがって、パケットが受理されない場合、
参照がホストによってろ過するプロセスによって
必要だったバイトだけに付けられます。
In contrast, SunOS's STREAMS NIT [10] copies the packets
before filtering and as a result suffers a performance degradation.
The STREAMS packet filter module (
nit_pf(4M)
) sits
on top of the packet capture module (
nit_if(4M)
). Each packet
received is copied to an mbuf, and passed off to NIT, which
then allocates a STREAMS message buffer and copies in
the packet. The message buffer is then sent upstream to the
packet filter, which may decide to discard the packet. Thus,
a copy of each packet is always made, and many CPU cycles
will be wasted copying unwanted packets.
対照的に、SunOSのSTREAMS NIT[10]はフィルタリングの前にパケットをコピーし、
その結果実行低下を受けます。
STREAMSパケットフィルター・モジュール(
nit_pf(4M)
)パケット捕獲モジュール
(受け取られた各パケットがコピーされる
nit_if(4M)
).
、mbuf、
またNIT
(その後、それはSTREAMSメッセージ・バッファーおよび
パケット中のコピーを割り付ける)に離れて通過した。
その後、メッセージ・バッファーは、
パケットフィルター
(それはパケットを廃棄することを決定してもよい)へ上流に送られます。
したがって、1部の各パケットは常に作られます、
また、多くのCPUサイクルが衰弱した複写になるでしょう、
望まれないパケット)の上に座る。
Before discussing the details of the packet filter, we present
some measurements which compare the the relative costs of
the BPF and SunOS STREAMS buffering models. This performance
is independent of the packet filtering machinery.
パケットフィルターの詳細について議論する前に、
私たちは、匹敵するいくつかの測定を示します、
その(モデル)バッファーを用いたBPFとSunOSのSTREAMSの相対的なコスト。
この実行はパケットフィルタリング機械類に依存しません。
We configured both BPF and NIT into the same SunOS
4.1.1 kernel, and took our measurements on a Sparcstation 2.
The measurements reflect the overhead incurred during the
interrupt processing - i.e., how long it takes each system to
stash the packet into a buffer. For BPF we simply measured
the before and after times of the tap call,
bpf_tap()
, using the
Sparcstation's microsecond clock. For NIT we measured the
time of the tap call
snit_intr()
plus the additional overhead of
copying promiscuous packets to mbufs. (Promiscuous pack-
ets are those packets which were not addressed to the local
host, and are present only because the packet filter is run-
ning.) In other words, we included the performance hit that
NIT takes for not filtering packets in place. To obtain accurate
timings, interrupts were locked out during the instrumented
code segments.
私たちは同じSunOS 4.1.1核へBPFおよびNITの両方を形成し、
Sparcstation 2の上で私たちの測定をとりました。
その測定は、割り込み処理中に招かれたオーバーヘッドを反映します。
つまり、バッファーへパケットをしまっておくことは、
どれくらいの時間各システムに必要とするか。
BPFについては、私たちが単に測定しました、
その、タップ呼び出し、bpf_tap()の回の前に、
およびtimeの後にSparcstationのマイクロセカンド時計の使用。
NITについては、私たちが、タップ呼び出しsnit_intr()の時間を測定しました。
mbufsに乱雑なパケットをコピーする補足オーバーヘッドを増してください。
(乱雑なパケットは地方のホストに出されず、
ただパケットフィルターが走っているので、存在するパケットです。)
言いかえれば、私たちは、
NITが適所にパケットをろ過しないために受ける実行打撃を含みました。
正確なタイミングを得るために、割り込みは、
機器を備えたコードセグメント中にロックされました。
The data sets were taken as a histogram of processing time
versus packet length. We plotted the mean processing per
packet versus packet size, for two configurations: an "accept
all" filter, and a "reject all" filter.
データセットは、
時間対パケット長さを処理するヒストグラムとして得られました。
私たちは、2つの配置のために、
パケット対パケット・サイズについて中間の処理を計画しました:
1つの「すべてを受理します」フィルタ、
そして1つの「すべてを拒絶します」フィルタ。
In the first case, the STREAMS NIT buffering module
(
nit_buf(4M)
) was pushed on the NIT stream with its
chunk-size
parameter set to the 16K bytes. Similarly, BPF was
configured to use 16K buffers. The packet filtering module
which usually sits between the NIT interface and NIT buffering
modules was omitted to effect "accept all" semantics. In
both cases, no truncation limits were specified. This data is
shown in Figure 2. Both BPF and NIT show a linear growth
with captured packet size reflecting the cost of packet-to-filter
buffer copies. However the different slopes of the BPF and
NIT lines show that BPF does its copies at memory speed
(148ns/byte) while NIT runs 45% slower (216ns/byte).
The y-intercept gives the fixed per-packet processing overhead:
The overhead of a BPF call is about 6us while NIT is 15 times
worse at 89us per packet. Much of this huge disparity
appears to be due to the cost of allocating and initializing a
buffer under the remarkably baroque AT&T STREAM I/O
system.
第1のケース、STREAMS NITバッファーを用いたモジュール(
nit_buf(4M)
)にその塊サイズを備えたNIT流れに押しつけられました。
16Kバイトまでパラメーター・セット。
同様に、BPFは16Kのバッファーを使用するために形成されました。
(モジュール)バッファーを用いたNITインターフェース
およびNITの間に通常座るパケットフィルタリング・モジュールは
達成するために省略されました「すべてを受理します」意味論。
両方の場合では、切断範囲が指定されませんでした。
このデータは図2の中で示されます。BPFおよびNITの両方は、
ろ過するパケットバッファー・コピーのコストを反映する、
捕らえられたパケット・サイズを備えた線形の成長を示します。
しかしながら、BPFとNITのラインの異なる傾斜は、
NITが45%遅く(216ns/バイト)なっている一方
メモリ速度(148ns/バイト)でBPFがそのコピーを?sうことを示します。
その、y-遮る、パケットごとの固定処理オーバーヘッドを与える:
NITが1つのパケット当たり89usで15倍悪い間、
BPF呼び出しのオーバーヘッドは6usに関係しています。
非常に、これに、巨大な不均衡は、
著しくバロック式のAT&T STREAM I/Oシステムの下の
バッファーを割り付けて初期化するコストによるように見えます。
| Figure 2: | NIT versus BPF: "accept all" |
Figure 3 shows the results for the "reject all" configuration.
Herethe STREAMS packet filter module was configured with
a "reject all" filter and pushed directly on top of the NIT
interface module (the NIT buffering module was not used). Since
the filter discards all packets, the processing time should be
constant, independent of the packet size. For BPF this is true
- we see essentially the same fixed cost as last time (5s
instead of 6 since rejecting avoids a call to the BPF copy
routine) and no effect due to packet size. However, as explained
earlier, NIT doesn't filter packets in place but instead
copies packets then runs the filter over the copies.
Thus the
cost of running NIT increases with packet size
even when the packet is discarded by the filter
. For large packets, this
gratuitous copy makes NIT almost two orders of magnitude
more expensive than BPF (450us vs. 5s).
The major lesson here is that filtering packets early and
in place pays off. While a STREAMS-like design might ap-
pear to be modular and elegant, the performance implications
of module partitioning need to be considered in the design.
We claim that even a STREAMS-based network tap should
include the packet filtering and buffering functionality in its
lowest layer. There is very little design advantage in factor-
ing the packet filter into a separate streams module, but great
performance advantage in integrating the packet filter and the
tap into a single unit.
図3は結果を示します、のために、その「すべてを拒絶します」配置。
Herethe STREAMSパケットフィルター・モジュールは形成されました、
1つの「すべてを拒絶します」フィルタ、
またNITインターフェース・モジュール
((モジュール)バッファーを用いたNITは使用されませんでした)
の上に直接押されました。
フィルタがパケットをすべて廃棄するので、
処理時間はパケット・サイズと無関係に一定に違いありません。
BPFについては、これが真実です―私たちは同じ固定費を本質的に見ます、
として、時に
(拒絶以来の6の代わりに5sは、BPFコピー・ルーチンへの呼び出しを回避します)
またパケット・サイズによる効力はない。
以前に説明されるように、(しかしながら)、
NITは、適所にしかし代わりにパケットをろ過しません、
コピー、パケット、その後、コピー上でフィルタを実行します。
したがってパケットがフィルタによって廃棄される場合にさえ
パケット・サイズを備えたNIT増加を実行するコスト。
大きなパケットについては、この無料のコピーが
NITをBPF(450us対5s)より高価なほとんど2つの桁にします。
主なレッスンはここで、パケットを初期に適所にろ過することが
成果をあげるということです。
STREAMSのような設計がモジュールで上品に見えているかもしれない一方、
モジュールを分割する実行含意を設計の中で
考慮する必要があります。
私たちは、その最低の層にSTREAMSに基づいた
ネットワーク・タップさえがパケットフィルタリング
およびバッファーを用いた機能性を含むべきであると主張します。
個別の流れモジュールへパケットフィル?^ーを
因数分解することでの設計利点だが単一のユニットへ
パケットフィルターおよびタップを統合することでの
大きな実行利点はほとんどありません。
| Figure 3: | NIT versus BPF: "reject all" |
Assuming one uses reasonable care in the design of the buffering model,
it will be the dominant cost of packets you accept
while the packet filter computation will be the dominant cost
of packets you reject. Most applications of a packet capture
facility reject far more packets than they accept and, thus,
good performance of the packet filter is critical to good over-
all performance.
1つの仮定はバッファーを用いたモデルのデザインの中で合理的な注意を使用します。
それは、パケットフィルター計算が拒絶するパケットの
支配的なコストになっているかもしれない一方、
受理するパケットの支配的なコストになるでしょう。
パケット捕獲設備のほとんどの適用は
それらが受理するよりはるかに多くのパケットを拒絶します。
また、したがって、パケットフィルターの
よいパフォーマンスはよい全面的なパフォーマンスに重大です。
A packet filter is simply a boolean valued function on a
packet. If the value of the function is
true
the kernel copies the
packet for the application; if it is
false
the packet is ignored.
Historically there have been two approaches to the fil-
ter abstraction: a boolean expression tree (used by CSPF)
and a directed acyclic control flow graph or CFG (first used
by NNStat[1] and used by BPF). For example, Figure 4 illustrates
the two models with a filter that recognizes either
IP or ARP packets on an Ethernet. In the tree model each
node represents a boolean operation while the leaves represent
test predicates on packet fields. The edges represent
operator-operand relationships. In the CFG model each node
represents a packet field predicate while the edges represent
control transfers. The righthand branch is traversed if the
predicate is true, the lefthand branch if false. There are two
terminating leaves which represent
true
and
false
for the entire filter.
パケットフィルターは単にパケット上のブールの価値のある機能です。
機能の値が真実の場合核は、適用用のパケットをコピーします;
それが誤りの場合パケットが無視されます。
歴史上、フィルタ抽象への2つのアプローチがありました:
ブールの表現木(CSPFによって使用された)
および指図された非有輪のコントロール・フロー・グラフか、
CFG(最初にNNStat[1]によって使用され、BPFによって使用された)。
例えば、図4は2つのモデルをイーサネット上の
IPあるいはARPのパケットのいずれかを認識するフィルタで例証します。
木モデルでは、葉がパケット競技場でテスト述語を表わしている一方、
各ノードはブールのオペレーションを表わします。
端はオペレーターオペランド関係を表わします。
CFGモデルでは、コントロールが移ると端が言っている一方、
各ノードはパケット・フィールド述語を表わします。
述語が真実の場合、右手枝は横断されます(誤りの場合左手枝)。
言う2枚の終了する葉があります、真実そして全フィルタには誤りです。
These two models of filtering are computationally equivalent.
I.e., any filter that can be expressed in one can be
expressed in the other. However, in implementation they are
very different: The tree model maps naturally into code for a
stack machine while the CFG model maps naturally into code
for a register machine. Since most modern machines are register
based, we will argue that the CFG approach lends itself
to a more efficient implementation.
フィルタリングのこれらの2つのモデルは計算上等価です。
つまり、一つの中で表現することができるどんなフィルタは
他方の中で表現することができます。
しかしながら、インプリメンテーションでは、
それらは非常に異なります:CFGモデルが登録機械のためのコードへ
当然写像している一方、木モデルは、スタック機械のためのコードへ当然写像します。
最も現代の機械が基づいた登録であるので、
私たちはCFGアプローチがより効率的なインプリメンテーションに
向いていると主張するでしょう。
The CSPF filter engine is based on an operand stack. In structions
either push constants or packet data on the stack,
or perform a binary boolean or bitwise operation on the top
two elements. A filter program is a sequentially executed list
of instructions. After evaluating a program, if the top of stack
has a non-zero value or the stack is empty then the packet is
accepted, otherwise it is rejected.
CSPFフィルタ・エンジンはオペランド・スタックに基づきます。
structionsの中で、スタック上の押し定数あるいはパケット・データ、
あるいは実行する、1つの、2進法、ブール、あるいはトップ2つの要素に対する
ビット的にオペレーション。
フィルタ・プログラムは指示の連続して実行されたリストです。
スタックのトップが0でない値あるいはスタックを持っている場合、
プログラムの評価が空の後、その後、パケットはそうでなければ受理されます、
それが拒絶されます。
There are two implementation shortcomings of the expression
tree approach:
表現木アプローチの2つのインプリメンテーション欠点があります:
| Figure 4: | Filter Function Representations. |
Another problem with CSPF, recognized by the designers,
is its inability to parse variable length packet headers, e.g.,
TCP headers encapsulated in a variable length IP header.
Because the CSPF instruction set didn't include an indirection
operator, only packet data at fixed offsets is accessible. Also,
the CSPF model is restricted to a single sixteen bit data type
which results in a doubling of the number of operations to
manipulate 32 bit data such as Internet addresses or
TCP sequence numbers. Finally, the design does not permit access
to the last byte of an odd-length packet.
デザイナーによって認識されたCSPFに関する別の問題は
可変長さパケット・ヘッダー
(例えば可変長さIPヘッダーの中でカプセルに入れられたTCPヘッダー)
を解析するその無力です。
CSPF指示セットが間接オペレーターを含んでいなかったので、
固定オフセットのパケット・データだけがアクセス可能です。
さらに、CSPFモデ??aモデル、オペレーションの番号の
インターネット・アドレスあるいはTCPシーケンス番号のような
32ビットのデータを操作するために2倍になることに帰着する
単一の16ビットのデータ・タイプに制限されます。
最後に、設計は、奇妙な長さのパケットの
最後のバイトへのアクセスを許しません。
While the CSPF model has shortcomings, it offers a novel
generalization of packet filtering: The idea of putting a
pseudo-machine language interpreter in the kernel provides a
nice abstraction for describing and implementing the filtering
mechanism. And, since CSPF treats a packet as a simple array
of bytes, the filtering model is completely protocol indepen-
dent. (The application that specifies the filter is responsible
for encoding the filter appropriately for the underlying network
media and protocols.)
CSPFモデルが欠点を持っている一方、
それはパケットフィルタリングの斬新な一般化を提示します:
核に偽りの機械語のインタープリターを入れる考えは、
ろ過するメカニズムについて記述しインプリメントするために
よい抽象的概念を提供します。
また、CSPFがバイトの単純な配列としてパケットを扱うので、
ろ過?キるモデルは完全にプロトコルです、
独立した
(フィルタが根本的なネットワーク・メディア
およびプロトコル用にフィルタを適切にコード化すること原因であることを
明示する適用。)
The BPF model, described in the next section, is an attempt
to maintain the strengths of CSPF while addressing its limitations
and the performance shortcomings of the stack-based filter machine.
次のセクションに記述されたBPFモデルはその制限に取り組む間の
CSPFの強さおよびスタックに基づいたフィルタ機械の実行欠点を維持する試みです。
BPF uses the CFG filter model since it has a significant
performance advantage over the expression tree model. While
the tree model may need to redundantly parse a packet many
times, the CFG model allows parse information to be `built
into' the flow graph. I.e., packet parse state is `remembered'
in the graph since you know what paths you must have traversed
to reach to a particular node and once a subexpression
is evaluated it need not be recomputed since the control flow
graph can always be (re-)organized so the value is only used
at nodes that follow the original computation.
それが表現木モデルに関する重要な実行長所を持つので、
BPFはCFGフィルタ・モデルを使用します。
木モデルがパケットを余分に何度も解析している必要があるかもしれない一方、
CFGモデルは許可します「構築される情報を解析する」フロー・グラフ。
つまり、パケット、状態を解析する、中へ「記憶される」グラフ、
特別のノードにどのパスに達するために、
横断したに違いないかあなたが知っており、
一度、subexpressionが評価されるので、
コントロール・フロー・グラフが常にそうでありうる(re)ので、
それを再計算する必要がありません、
値がオリジナルの計算に続くノードで単に使用されるように、
組織しました。
| Figure 5: | CFG Filter Function for "host foo". |
For example, Figure 5 shows a CFG filter function that ac-
cepts all packets with an Internet address
foo
. We consider a
scenario where the network layer protocols are IP, ARP, and
Reverse ARP, all of which contain source and destination
Internet addresses. The filter should catch all cases. Accord-
ingly, the link layer type field is tested first. In the case of
IP packets, the IP host address fields are queried, while in
the case of ARP packets, the ARP address fields are used.
Note that once we learn that the packet is IP, we do not need
to check that it might be ARP or RARP. In the expression
tree model, shown in figure 6, seven comparison predicates
and six boolean operations are required to traverse the entire
tree. The longest path through the CFG has five comparison
operations, and the average number of comparisons is three.
例えば、図5は、インターネット・アドレスfooを備えたパケットを
すべて受理するCFGフィルタ機能を示します。
.ネットワーク層プロトコルがIP、ARPおよび逆のARP
(それらのすべては出所と目的地のインターネット・アドレスを含んでいる)
である場合、私たちはシナリオを考慮します。
フィルタはすべてのケースをつかむべきです。
従って、リンク層タイプ・フィールドは最初にテストされます。
IPパケットの場合には、ARPのパケットの場合には、
ARPアドレス・フィールドが使用されている一方、
IPホスト・アドレス・フィールドは尋ねられます。
一旦パケットがIPであることを知れば
私たちが、それがARPまたはRARPかもしれないことを
チェックする必要がないことに注意してください。
図6の中で示される表現木モデルでは、7つの比較が断定します。
また、6つのブールのオペレーションが全木を
横断するために要求されます。
CFGを通る最長のパスは5つの比較オペレーションを持っています。
また、比較の平均数は3です。
| Figure 6: | Tree Filter Function for "host foo". |
The use of a control flow graph rather than an expression tree
as the theoretical underpinnings of the filter pseudo-machine
is a necessary step towards an efficient implementation but it
is not sufficient. Even after leveraging off the experience and
pseudo-machine models of CSPF and NNStat[1], the BPF
model underwent several generations (and several years) of
design and test. We believe the current model offers sufficient
generality with no sacrifice in performance. Its evolution was
guided by the following design constraints:
フィルタの偽りの機械の理論的な土台としての表現木ではなく
コントロール・フロー・グラフの使用は、
効率的なインプリメンテーションに向けての必要なステップです。
しかし、?サれは十分ではありません。
さえ、CSPFおよびNNStat[1]の経験および偽りの機械のモデルからてこ入れした後に、
BPFモデルは、設計とテストのいくつかの世代(また数年)を経験しました。
私たちは、現在のモデルが実行での犠牲のない
十分な一般法則を提示すると信じます。
その発展は次の設計制約によってガイドされました:
Like CSPF, constraint 1 is adhered to simply by not
mentioning any protocols in the model. Packets are viewed
simply as byte arrays.
CSPFのように、
強制1は、単にモデル中のどんなプロトコルにも言及しますことにより付着します。
パケットは単にバイト配列として見られます。
Constraint 2 means that we must provide a fairly general
computational model, with control flow, sufficient ALU
operations, and conventional addressing modes.
コントロール・フロー、
十分なALUオペレーションおよび従来のアドレッシングモードと共に、
私たちがかなり一般的な計算上のモデルを供給しなければならない強制2手段。
Constraint3 requires that we only ever touch a given packet
word once. It is common for a filter to compare a given packet
fieldagainst a set of values, then compare another field against
another set of values, and so on. For example, a filter might
match packets addressed to a set of machines, or a set of TCP
ports. Ideally, we would like to cache the packet field in a
register and compare it across the set of values. If the field is
encapsulated in a variable length header, we must parse the
outer headers to reach the data. Furthermore, on alignment
restricted machines, accessing multi-byte data can involve an
expensive byte-by-byte load. Also, for packets in
mbufs
, a
field access may involve traversing an
mbuf
chain. After we
have done this work once, we should not do it again.
Constraint3は、
私たちが与えられたパケット単語に単に常にかつて触れることを必要とします。
フィルタが与えられたパケットfieldagainstを比較することは一般的です、
1セットの値、その後、値の別のセットに対する別のフィールドなどを比較します。
例えば、フィルタは、1セットの機械に出されたパケット、
あるいは1セットのTCPポートと一致するかもしれません。
理想的には、私たちは、登録中のパケット・フィールドを貯えて、
値のセットを横切ってそれを比較したい。
フィールドが可変長さヘッダーの中でカプセルに入れられる場合、
私たちは、データに達するために外部のヘッダーを解析しなければなりません。
更に、整列を制限された機械においては、多重バイトデータへのアクセスは、
バイトごとの高価なロードを含んでいるかもしれません。
さらに、mbufsの中のパケットのために
フィールド・アクセスはmbufを横断することを含んでいるかもしれません。
チェーン。この仕事を以前行ったことがある後、
私たちはそれを再び行ってはなりません。
Constraint 4 means that we will have an efficient instruction
decoding step but it precludes an orthogonal addressing
mode design unless we are willing to accommodate a combinatorial
explosion of switch cases. For example, while three
address instructions make sense for a real processor (where
much work is done in parallel) the sequential execution model
of an interpreter means that each address descriptor would
have to be decoded serially. A single address instruction
format minimizes the decode, while maintaining sufficient
generality.
強制4は、私たちが効率的な指示をデコードする
ステップを行うだろうが、もし私たちが喜んで
スイッチの場合の組み合わせの爆発を提供しなければ
それが直角のアドレッシングモード設計を排除するということを意味します。
例えば、3つのアドレス命令がインタープリターの
連続する実行モデルが意味する、
実際のプロセッサー(多くの仕事が平行中で終わる場合)用に
各アドレス・ディスクリプタが連続的にデコードされなければ
ならないだろうという意味をなしている一方、
十分な一般法則を維持している間、
単一のアドレス指示フォーマットはdecodeを最小限にします。
Finally, Constraint 5 is a straightforward performance consideration.
Along with constraint 4, it enforces the notion that
the pseudo-machine register set should be small.
最後に、強制5は真直ぐな実行考察です。
強制4に加えて、それは、偽りの機械の登録セットが
小さくあるべきであるという概念を強化します。
These constraints prompted the adoption of an accumulator
machine model. Under this model, each node in the
flowgraph computes its corresponding predicate by computing
a value into the accumulator and branching based on that
value. Figure 7 shows the filter function of Figure 5 using
the BPF instruction set.
これらの制約は、アキュムレーター機械モデルの採用を刺激しました。
このモデルの下では、flowgraphの中の各ノードが、
その値に基づいたアキュムレーターおよび分岐へ値を計算することにより、
その対応する述語を計算します。
図7は、BPF指示セットを使用して、図5のフィルタ機能を示します。
The BPF machine abstraction consists of an accumulator, an
index register (
x
), a scratch memory store, and an implicit
program counter. The operations on these elements can be
categorized into the following groups:
BPF機械抽象はアキュムレーター、
インデックス登録(x)から成ります。
雑記用のメモリ店、また暗黙のプログラム・カウンター。
これらの要素に対するオペレーションは次のグループへ分類することができます:
The fixed-length instruction format is defined by as follows:
固定長指示フォーマットはそばに以下のように定義されます:
| opcode:16 | jt:8 | jf:8 |
| k:32 | ||
The
opcode
field indicates the instruction type and addressing modes.
The
jt
and
jf
fields are used by the conditional
jump instructions and are the offsets from the next instruction
to the true and false targets. The
k
field is a generic field used
for various purposes.
そのopcodeフィールドは指示タイプおよびアドレッシングモードを示します。
そのjtそしてjfフィールドは条件付きの跳躍命令によって使用され、
次の指示から真実と誤りの目標までオフセットです。
kフィールドは様々な目的のために使用された総括的なフィールドです。
Table 1 shows the entire BPF instruction set. We have
adopted this "assembler syntax" as a means of illustrating
BPF filters and for debugging output. The actual encodings
are defined with C macros, the details of which we omit here
(see [6] for full details). The column labelled
addr modes
lists
the addressing modes allowed for each instruction listed in
the
opcode
column. The semantics of the addressing modes
are listed in Table 2.
テーブル1はBPF指示セット全体を示します。
私たちは、BPFフィルタを例証する手段として、
および出力のデバッグのためにこの「アセンブラー・シンタックス」を採用しました。
実際の符号づけは、Cマクロ
(私たちがどれをここで省略するかの詳細)
で定義されます(十分な詳細に関しては[6]を参照)。
カラムはaddrモードにラベルを付けました。
リストリストされた各指示のために許可されたアドレッシングモード、
そのopcodeカラム。
アドレッシングモードの意味論、
テーブル2にリストされます。
| opcodes | addr modes | |||||
|---|---|---|---|---|---|---|
| ldb |
|
|||||
| ldh |
|
|||||
| ld |
|
|||||
| ldx |
|
|||||
| st |
|
|||||
| stx |
|
|||||
| jmp |
|
|||||
| jeq |
|
|||||
| jgt |
|
|||||
| jge |
|
|||||
| jset |
|
|||||
| add |
|
|||||
| sub |
|
|||||
| mul |
|
|||||
| div |
|
|||||
| and |
|
|||||
| or |
|
|||||
| lsh |
|
|||||
| rsh |
|
|||||
| ret |
|
|||||
| tax | ||||||
| txa |
| Table 1: | BPF Instruction Set |
| #k | the literal value stored in k |
| #len | the length of the packet |
| M[k] | the word at offset k in the scratch memory store |
| [k] | the byte, halfword, or word at byte offset k in the packet |
| [x+k] | the byte, halfword, or word at offset x+k in the packet |
| L | an offset from the current instruction to L |
| #k, Lt, Lf | the offset to Lt if the predicate is true, otherwise the offset to Lf |
| x | the index register |
| 4*([k]&0xf) | four times the value of the low four bits of the byte at offset k in the packet |
| Table 2: | BPF Addressing Modes |
The load instructions simply copy the indicated value into
the accumulator (
ld
,
ldh
,
ldb
) or index register (
ldx
).
The index register cannot use the packet addressing modes.
Instead, a packet value must be loaded into the accumulator
and transferred to the index register, via
tax
. This is not a
common occurrence, as the index register is used primarily
to parse the variable length IP header, which can be loaded
directly via the
4*([k]&0xf)
addressing mode. All values
are 32 bit words, except packet data can be loaded into the
accumulator as unsigned bytes (
ldb
) or unsigned halfwords (
ldh
). Similarly, the scratch memory store is addressed as
an array of 32 bit words. The instruction fields are all in host
byte order, and the load instructions convert packet data from
network order to host order. Any reference to data beyond
the end of the packet terminates the filter with a return value
of zero (i.e., the packet is discarded).
ロード指示は、
単にアキュムレーター(ld、ldh、ldb)に示された値をコピーします。
あるいはインデックス登録 (インデックス登録が使用することができないldx).、
パケット・アドレッシングモード)代わりに、
パケット価値をアキュムレーターにロードし、
税によってインデックス登録に転送されるに違いありません。
インデックス登録が第1に可変長さIPヘッダー
(それは4*([k]&0xf)アドレッシングモードによって直接ロードすることができる)
を解析するために使用されるので、
これは共通の発生ではありません。
値はすべて、符号なしのバイト(ldb)としてアキュムレーターに
パケット・データをロードすることができる以外は、
32ビットの言葉です。
あるいは符号なしのhalfwords (ldh).、同様に、雑記用のメモリ店は
多くの32ビットの言葉としてアドレスされます。
指示フィールドは、ホスト・バイトオーダーおよびロード命令の中にすべてあります、
パケット・データをネットワーク・オーダーからホスト・オーダーに変換する。
パケットの終了を越えたデータへのどんな言及も、
0(つまり、パケットは廃棄されます)の返り値を備えたフィルタを終了します)
The ALU operations (
add
,
sub
, etc.) perform the indicated
operation using the accumulator and operand, and store
the result back into the accumulator. Division by zero
terminates the filter.
ALUオペレーション(加える(sub))など、
アキュムレーターおよびオペランドを使用して、
示されたオペレーションを?タ行し、
アキュムレーターへ結果を後ろに格納する。
0による区分はフィルタを終了します。
The jump instructions compare the value in the accumulator
with a constant (
jset
performs a "bitwise and" - useful
for conditional bit tests). If the result is true (or non-zero),
the true branch is taken, otherwise the false branch is taken.
Arbitrary comparisons, which are less common, can be done
by subtracting and comparing to 0. Note that there are no
jlt
,
jle
or
jne
opcodes since these can be built from the
codes above by reversing the branches. Since jump offsets
are encoded in eight bits, the longest jump is 256 instructions.
Jumps longer than this are conceivable, so a
jump always
opcode is provided (
jmp
) that uses the 32 bit operand field for
the offset.
跳躍指示は、アキュムレーター中の値を比較します、
で、1つの、一定(jsetは実行します、
1つの「ビット的に、そして"―条件付きのビット・テストに役立つ)。
結果が真実の(あるいは0でない)場合、
真実の枝はそうでなければ得られます、
誤りの枝が得られます。
任意の比較(それらはそれほど一般的でない)は
0まで引き算をするおよび匹敵することにより行うことができます。
それにそこに注意する、jltでない。、
jleあるいはjneこれら以来のopcodesは枝を逆にすることにより
コードから上に構築することができます。
跳躍オフセットが8ビットでコード化されるので、
最長の跳躍は256の指示です。これより長くジャンプする、
考えられる、したがって、跳躍、常に、opcodeは提供されます(jmp)。
それはオフセットのために32ビットのオペランド・フィールドを使用します。
The return instructions terminate the program and indicate
how many bytes of the packet to accept. If that amount is
0, the packet will be rejected entirely. The actual amount
accepted will be the minimum of the length of the packet and
the amount indicated by the filter.
####
Wenow present some examples to illustrate how packet filters
can be expressed using the BPF instruction set. (In all the
examples that follow, we assume Ethernet format for the link
level headers.)
This filter accepts all IP packets:
ldh [12] jeq #ETHERTYPE IP, L1, L2 L1: ret #TRUE L2: ret #0
The first instruction loads the Ethernet type field. We compare
this to type IP. If the comparison fails, zero is returned
and the packet is rejected. If it is successful, TRUE is
returned and the packet is accepted. (TRUE is some non-zero
value that represents the number of bytes to save.)
This next filter accepts all IP packets which did not originate
from two particular IP networks, 128.3.112 or 128.3.254.
If the Ethernet type is IP, the IP source address is loaded and
the high 24 bits are masked off. This value is compared with
the two network addresses:
ldh [12] jeq #ETHERTYPE IP, L1, L4 L1: ld [26] and #0xffffff00 jeq #0x80037000, L4, L2 L2: jeq #0x8003fe00, L4, L3 L3: ret #TRUE L4: ret #0
The previous examples assume that the data of interest lie at
fixed offsets in the packet. This is not the case, for example,
with TCP packets, which are encapsulated in a variable length
IP header. The start of TCP header must be computed from
the length given in the IP header.
The IP header length is given by the low four bits of the
first byte in the IP section (byte 14 on an Ethernet). This
value is a word offset, and must be scaled by four to get the
corresponding byte offset. The instructions below will load
this offset into the accumulator:
ldb [14] and #0xf lsh #2
Once the IP header length is computed, data in the TCP
section can be accessed using indirect loads. Note that the
effective offset has three components:
For example, an Ethernet header is 14 bytes and the
destination port in a TCP packet is at byte two. Thus, adding 16
to the IP header length gives the offset to the TCP destination
port. The previous code segment is shown below, augmented
to test the TCP destination port against some value
N
:
ldb [14] and #0xf lsh #2 tax ldh [x+16] jeq #N, L1, L2 L1: ret #TRUE L2: ret #0
Because the IP header length calculation is a common operation, the
4*([k]&0xf)
addressing mode was introduced.
Substituting in the
ldx
instruction simplifies the filter into:
ldx 4*([14]&0xf) ldh [x+16] jeq #N, L1, L2 L1: ret #TRUE L2: ret #0
However, the above filter is valid only if the data we are
looking at is really a TCP/IP header. Hence, the filter must
also check that link layer type is IP, and that the IP protocol
type is TCP. Also, the IP layer might fragment a TCP packet,
in which case the TCP header is present only in the first fragment.
Hence, any packets with a non-zero fragment offset
should be rejected. The final filter is shown below:
ldh [12] jeq #ETHERPROTO IP, L1, L5 L1: ldb [23] jeq #IPPROTO TCP, L2, L5 L2: ldh [20] jset #0x1fff, L5, L3 L3: ldx 4*([14]&0xf) ldh [x+16] jeq #N, L4, L5 L4: ret #TRUE L5: ret #0
We profiled the BPF and CSPF filtering models outside the
kernel using
iprof
[9], an instruction count profiler. To fully
compare the two models, an indirection operator was added
to CSPF so it could parse IP headers. The change was minor
anddid not adversely affectthe original filtering performance.
Tests were run on large packet trace files gathered from a busy
UC Berkeley campus network. Figure 8 shows the results for
four fairly typical filters.
Filter 1 is trivial. It tests whether one 16 bit word in the
packet is a given value. The two models are fairly comparable,
with BPF faster by about 50%.
Filter 2 looks for a particular IP host (source or destination)
and shows more of a disparity-a performance gap of
240%. The larger difference here is due mostly to the fact that
CSPF operates only on 16 bit words and needs two comparison
operations to determine the equality of a 32 bit Internet
address.
Filter 3 is an example of packet parsing (required to locate
the TCP destination port field) and illustrates a yet greater
performance gap. The BPF filter parses the packet once,
loading the port field into the accumulator then simply does a
comparison cascade of the interesting ports. The CSPF filter
must re-do the parse and relocate the TCP header for each
port to be tested.
Finally, filter 5 demonstrates the effect of the unnecessary
computations done by CSPF for a filter similar to the one
described in figures 6 and 5.
BPF is now about two years old and has been put to work in
several applications. The most widely used is
tcpdump
[4],
a network monitoring and data acquisition tool. Tcpdump
performs three primary tasks: filter translation, packet ac-
quisition, and packet display. Of interest here is the filter
translation mechanism. A filter is specified with a user-
friendly, high level description language. Tcpdump has a
built in compiler (and optimizer) which translates the high
level filters into BPF programs. Of course, this translation
process is transparent to the user.
Arpwatch
[5] is a passive monitoring program that tracks
Ethernet to IP address mappings. It notifies the system
administrator, via email, when new mappings are established
or abnormal behavior is noted. A common administrative
nuisance is the use of a single IP address by more than one
physical host, which arpwatch dutifully detects and reports.
A very different application of BPF has been its incorporation
into a variant of the Icon Programming Language
[3]. Two new data types, a
packet
and a
packet generator
have been built into the Icon interpreter. Packets appear as
first class record objects, allowing convenient "dot operator"
access to packet headers. A packet generator can be instanti-
ated directly off the network, or from a previously collected
file of trace data. Icon is an interpreted, dynamically typed
language with high level string scanning primitives and rich
data structures. With the BPF extensions, it is well suited for
the rapid prototyping of networking analysis tools.
Netload
and
histo
are two network visualization tools
which produce real time network statistics on an X dis-
play. Netload graphs utilization data in real time, using
tcpdump style filter specifications. Histo produces a dynamic
interarrival-time histogram of timestamped multimedia net-
work packets.
The Reverse ARP daemon uses the BPF interface to read
and write Reverse ARP requests and replies directly to the
local network. (We developed this program to allow us to
entirely replace NIT by BPF in our SunOS 4 systems. Each of
the Sun NIT-based applications (etherfind, traffic, and rarpd)
now has a BPF analog.)
Finally, recent versions of NNStat[1] and nfswatch can be
configured to run over BPF (in addition to running over NIT).
BPF has proven to be an efficient, extensible, and portable
interface for network monitoring. Our comparison studies
have shown that it outperforms NIT in its buffer manage-
ment and CSPF in its filtering mechanism. Its programmable
pseudo-machine model has demonstrated excellent general-
ity and extensibility (all knowledge of particular protocols is
factored out of the kernel). Finally, the system is portable
and runs on most BSD and BSD-derivative systems
and can interact with various data link layers.
| Figure 8: | BPF/CSPF Filter Performance |
BPF is available via anonymous ftp from host
ftp.ee.lbl.gov
as part of the tcpdump distribution,
currently in the file
tcpdump-2.2.1.tar.Z
. Eventually
we plan to factor BPF out into its own distribution so look
for
bpf-*.tar.Z
in the future. Arpwatch and netload are
also available from this site.
This paper would never have been published without the
encouragement of Jeffrey Mogul. Jeff ported
tcpdump
to Ultrix
and added little-endian support, uncovering dozens of our
byte-ordering bugs. He also inspired the
jset
instruction
by forcing us to consider the arduous task of parsing DECNET
packet headers. Mike Karels suggested that the filter
should decide not only whether to accept a packet, but also
how much of it to keep. Craig Leres was the first major user of
BPF/tcpdump and is responsible for finding and fixing many
bugs in both. Chris Torek helped with the packet processing
performance measurements and provided insight on various
BSD peculiarities. Finally, we are grateful to the many users
and extenders of BPF/tcpdump across the Internet for their
suggestions, bug fixes, source code, and the many questions
that have, over the years, greatly broadened our view of the
networking world and BPF's place in it.
Finally, we would like to thank Vern Paxson, Craig Leres,
Jeff Mogul, Sugih Jamin, and the referees for their helpful
comments on drafts of this paper.