summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorZheng Da <zhengda1936@gmail.com>2016-11-02 17:52:35 +0100
committerJustus Winter <justus@gnupg.org>2016-11-04 15:40:17 +0100
commit50e14fce11f2bebb4faad220f8f610a55f4110c5 (patch)
treea23f2e0a2639cf35ec546b77c77b63fc9fc571cb
parent0bc74163d5406e305b84f8f51dbce097bb46fa90 (diff)
libbpf: Merge the Berkeley Packet Filter library.
* Makefile (lib-subdirs): Add new library. * NEWS: Update. * libbpf/Makefile: New file. * libbpf/bpf_impl.c: Likewise. * libbpf/bpf_impl.h: Likewise. * libbpf/queue.c: Likewise. * libbpf/queue.h: Likewise. * libbpf/util.h: Likewise. The Berkeley Packet Filter implementation has been extracted from the Mach kernel by Zheng Da. This merges his work into the main repository.
-rw-r--r--Makefile3
-rw-r--r--NEWS3
-rw-r--r--libbpf/Makefile33
-rw-r--r--libbpf/bpf_impl.c868
-rw-r--r--libbpf/bpf_impl.h161
-rw-r--r--libbpf/queue.c131
-rw-r--r--libbpf/queue.h329
-rw-r--r--libbpf/util.h91
8 files changed, 1618 insertions, 1 deletions
diff --git a/Makefile b/Makefile
index d48baaac..f5940a11 100644
--- a/Makefile
+++ b/Makefile
@@ -29,7 +29,8 @@ include ./Makeconf
lib-subdirs = libshouldbeinlibc libihash libiohelp libports libthreads \
libpager libfshelp libdiskfs libtrivfs libps \
libnetfs libpipe libstore libhurdbugaddr libftpconn libcons \
- libhurd-slab
+ libhurd-slab \
+ libbpf \
# Hurd programs
prog-subdirs = auth proc exec term \
diff --git a/NEWS b/NEWS
index 486cb2d5..cfb76d2b 100644
--- a/NEWS
+++ b/NEWS
@@ -3,6 +3,9 @@ Version 0.9 (2016-11-XX)
The 'boot' program can now be run as unprivileged user, allowing any
user to create unprivileged Subhurds.
+The Berkeley Packet Filter library has been merged into this
+repository.
+
Version 0.8 (2016-05-18)
The netfs library is using the lockless reference-counting primitives
diff --git a/libbpf/Makefile b/libbpf/Makefile
new file mode 100644
index 00000000..0a7ba90f
--- /dev/null
+++ b/libbpf/Makefile
@@ -0,0 +1,33 @@
+#
+# Copyright (C) 1994,95,96,97,98,99,2000,01,02,2005 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License as
+# published by the Free Software Foundation; either version 2, or (at
+# your option) any later version.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+
+dir := libbpf
+makemode := library
+
+libname = libbpf
+SRCS= bpf_impl.c queue.c
+LCLHDRS = bpf_impl.h queue.h
+installhdrs = bpf_impl.h queue.h
+
+MIGSTUBS =
+OBJS = $(sort $(SRCS:.c=.o) $(MIGSTUBS))
+
+LDLIBS = -lpthread
+
+MIGCOMSFLAGS =
+
+include ../Makeconf
diff --git a/libbpf/bpf_impl.c b/libbpf/bpf_impl.c
new file mode 100644
index 00000000..03a2a531
--- /dev/null
+++ b/libbpf/bpf_impl.c
@@ -0,0 +1,868 @@
+ /*
+ * Mach Operating System
+ * Copyright (c) 1993-1989 Carnegie Mellon University
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify and distribute this software and its
+ * documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ *
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ *
+ * Carnegie Mellon requests users of this software to return to
+ *
+ * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
+ * School of Computer Science
+ * Carnegie Mellon University
+ * Pittsburgh PA 15213-3890
+ *
+ * any improvements or extensions that they make and grant Carnegie Mellon
+ * the rights to redistribute these changes.
+ */
+/*
+ * Author: David B. Golub, Carnegie Mellon University
+ * Date: 3/98
+ *
+ * Network IO.
+ *
+ * Packet filter code taken from vaxif/enet.c written
+ * CMU and Stanford.
+ */
+
+/* the code copied from device/net_io.c in Mach */
+
+#include <arpa/inet.h>
+#include <string.h>
+
+#include <mach.h>
+#include <hurd.h>
+
+#include "bpf_impl.h"
+#include "queue.h"
+#include "util.h"
+
+static struct net_hash_header filter_hash_header[N_NET_HASH];
+
+/*
+ * Execute the filter program starting at pc on the packet p
+ * wirelen is the length of the original packet
+ * buflen is the amount of data present
+ *
+ * @p: packet data.
+ * @wirelen: data_count (in bytes)
+ * @hlen: header len (in bytes)
+ */
+
+int
+bpf_do_filter(net_rcv_port_t infp, char *p, unsigned int wirelen,
+ char *header, unsigned int hlen, net_hash_entry_t **hash_headpp,
+ net_hash_entry_t *entpp)
+{
+ register bpf_insn_t pc, pc_end;
+ register unsigned int buflen;
+
+ register unsigned long A, X;
+ register int k;
+ unsigned int mem[BPF_MEMWORDS];
+
+ /* Generic pointer to either HEADER or P according to the specified offset. */
+ char *data = NULL;
+
+ pc = ((bpf_insn_t) infp->filter) + 1;
+ /* filter[0].code is (NETF_BPF | flags) */
+ pc_end = (bpf_insn_t)infp->filter_end;
+ buflen = NET_RCV_MAX;
+ *entpp = 0; /* default */
+
+ A = 0;
+ X = 0;
+ for (; pc < pc_end; ++pc) {
+ switch (pc->code) {
+
+ default:
+ abort();
+ case BPF_RET|BPF_K:
+ if (infp->rcv_port == MACH_PORT_NULL &&
+ *entpp == 0) {
+ return 0;
+ }
+ return ((u_int)pc->k <= wirelen) ?
+ pc->k : wirelen;
+
+ case BPF_RET|BPF_A:
+ if (infp->rcv_port == MACH_PORT_NULL &&
+ *entpp == 0) {
+ return 0;
+ }
+ return ((u_int)A <= wirelen) ?
+ A : wirelen;
+
+ case BPF_RET|BPF_MATCH_IMM:
+ if (bpf_match ((net_hash_header_t)infp, pc->jt, mem,
+ hash_headpp, entpp)) {
+ return ((u_int)pc->k <= wirelen) ?
+ pc->k : wirelen;
+ }
+ return 0;
+
+ case BPF_LD|BPF_W|BPF_ABS:
+ k = pc->k;
+
+load_word:
+ if ((u_int)k + sizeof(long) <= hlen)
+ data = header;
+ else if ((u_int)k + sizeof(long) <= buflen) {
+ k -= hlen;
+ data = p;
+ } else
+ return 0;
+
+#ifdef BPF_ALIGN
+ if (((int)(data + k) & 3) != 0)
+ A = EXTRACT_LONG(&data[k]);
+ else
+#endif
+ A = ntohl(*(long *)(data + k));
+ continue;
+
+ case BPF_LD|BPF_H|BPF_ABS:
+ k = pc->k;
+
+load_half:
+ if ((u_int)k + sizeof(short) <= hlen)
+ data = header;
+ else if ((u_int)k + sizeof(short) <= buflen) {
+ k -= hlen;
+ data = p;
+ } else
+ return 0;
+
+ A = EXTRACT_SHORT(&data[k]);
+ continue;
+
+ case BPF_LD|BPF_B|BPF_ABS:
+ k = pc->k;
+
+load_byte:
+ if ((u_int)k < hlen)
+ data = header;
+ else if ((u_int)k < buflen) {
+ data = p;
+ k -= hlen;
+ } else
+ return 0;
+
+ A = data[k];
+ continue;
+
+ case BPF_LD|BPF_W|BPF_LEN:
+ A = wirelen;
+ continue;
+
+ case BPF_LDX|BPF_W|BPF_LEN:
+ X = wirelen;
+ continue;
+
+ case BPF_LD|BPF_W|BPF_IND:
+ k = X + pc->k;
+ goto load_word;
+
+ case BPF_LD|BPF_H|BPF_IND:
+ k = X + pc->k;
+ goto load_half;
+
+ case BPF_LD|BPF_B|BPF_IND:
+ k = X + pc->k;
+ goto load_byte;
+
+ case BPF_LDX|BPF_MSH|BPF_B:
+ k = pc->k;
+ if (k < hlen)
+ data = header;
+ else if (k < buflen) {
+ data = p;
+ k -= hlen;
+ } else
+ return 0;
+
+ X = (data[k] & 0xf) << 2;
+ continue;
+
+ case BPF_LD|BPF_IMM:
+ A = pc->k;
+ continue;
+
+ case BPF_LDX|BPF_IMM:
+ X = pc->k;
+ continue;
+
+ case BPF_LD|BPF_MEM:
+ A = mem[pc->k];
+ continue;
+
+ case BPF_LDX|BPF_MEM:
+ X = mem[pc->k];
+ continue;
+
+ case BPF_ST:
+ mem[pc->k] = A;
+ continue;
+
+ case BPF_STX:
+ mem[pc->k] = X;
+ continue;
+
+ case BPF_JMP|BPF_JA:
+ pc += pc->k;
+ continue;
+
+ case BPF_JMP|BPF_JGT|BPF_K:
+ pc += (A > pc->k) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JGE|BPF_K:
+ pc += (A >= pc->k) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JEQ|BPF_K:
+ pc += (A == pc->k) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JSET|BPF_K:
+ pc += (A & pc->k) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JGT|BPF_X:
+ pc += (A > X) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JGE|BPF_X:
+ pc += (A >= X) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JEQ|BPF_X:
+ pc += (A == X) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_JMP|BPF_JSET|BPF_X:
+ pc += (A & X) ? pc->jt : pc->jf;
+ continue;
+
+ case BPF_ALU|BPF_ADD|BPF_X:
+ A += X;
+ continue;
+
+ case BPF_ALU|BPF_SUB|BPF_X:
+ A -= X;
+ continue;
+
+ case BPF_ALU|BPF_MUL|BPF_X:
+ A *= X;
+ continue;
+
+ case BPF_ALU|BPF_DIV|BPF_X:
+ if (X == 0)
+ return 0;
+ A /= X;
+ continue;
+
+ case BPF_ALU|BPF_AND|BPF_X:
+ A &= X;
+ continue;
+
+ case BPF_ALU|BPF_OR|BPF_X:
+ A |= X;
+ continue;
+
+ case BPF_ALU|BPF_LSH|BPF_X:
+ A <<= X;
+ continue;
+
+ case BPF_ALU|BPF_RSH|BPF_X:
+ A >>= X;
+ continue;
+
+ case BPF_ALU|BPF_ADD|BPF_K:
+ A += pc->k;
+ continue;
+
+ case BPF_ALU|BPF_SUB|BPF_K:
+ A -= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_MUL|BPF_K:
+ A *= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_DIV|BPF_K:
+ A /= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_AND|BPF_K:
+ A &= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_OR|BPF_K:
+ A |= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_LSH|BPF_K:
+ A <<= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_RSH|BPF_K:
+ A >>= pc->k;
+ continue;
+
+ case BPF_ALU|BPF_NEG:
+ A = -A;
+ continue;
+
+ case BPF_MISC|BPF_TAX:
+ X = A;
+ continue;
+
+ case BPF_MISC|BPF_TXA:
+ A = X;
+ continue;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * Return 1 if the 'f' is a valid filter program without a MATCH
+ * instruction. Return 2 if it is a valid filter program with a MATCH
+ * instruction. Otherwise, return 0.
+ * The constraints are that each jump be forward and to a valid
+ * code. The code must terminate with either an accept or reject.
+ * 'valid' is an array for use by the routine (it must be at least
+ * 'len' bytes long).
+ *
+ * The kernel needs to be able to verify an application's filter code.
+ * Otherwise, a bogus program could easily crash the system.
+ */
+int
+bpf_validate(bpf_insn_t f, int bytes, bpf_insn_t *match)
+{
+ register int i, j, len;
+ register bpf_insn_t p;
+
+ len = BPF_BYTES2LEN(bytes);
+
+ /*
+ * f[0].code is already checked to be (NETF_BPF | flags).
+ * So skip f[0].
+ */
+
+ for (i = 1; i < len; ++i) {
+ /*
+ * Check that that jumps are forward, and within
+ * the code block.
+ */
+ p = &f[i];
+ if (BPF_CLASS(p->code) == BPF_JMP) {
+ register int from = i + 1;
+
+ if (BPF_OP(p->code) == BPF_JA) {
+ if (from + p->k >= len)
+ return 0;
+ }
+ else if (from + p->jt >= len || from + p->jf >= len)
+ return 0;
+ }
+ /*
+ * Check that memory operations use valid addresses.
+ */
+ if ((BPF_CLASS(p->code) == BPF_ST ||
+ (BPF_CLASS(p->code) == BPF_LD &&
+ (p->code & 0xe0) == BPF_MEM)) &&
+ (p->k >= BPF_MEMWORDS || p->k < 0)) {
+ return 0;
+ }
+ /*
+ * Check for constant division by 0.
+ */
+ if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0) {
+ return 0;
+ }
+ /*
+ * Check for match instruction.
+ * Only one match instruction per filter is allowed.
+ */
+ if (p->code == (BPF_RET|BPF_MATCH_IMM)) {
+ if (*match != 0 ||
+ p->jt == 0 ||
+ p->jt > N_NET_HASH_KEYS)
+ return 0;
+ i += p->jt; /* skip keys */
+ if (i + 1 > len)
+ return 0;
+
+ for (j = 1; j <= p->jt; j++) {
+ if (p[j].code != (BPF_MISC|BPF_KEY))
+ return 0;
+ }
+
+ *match = p;
+ }
+ }
+ if (BPF_CLASS(f[len - 1].code) == BPF_RET)
+ return ((*match == 0) ? 1 : 2);
+ else
+ return 0;
+}
+
+int
+bpf_eq (bpf_insn_t f1, bpf_insn_t f2, int bytes)
+{
+ register int count;
+
+ count = BPF_BYTES2LEN(bytes);
+ for (; count--; f1++, f2++) {
+ if (!BPF_INSN_EQ(f1, f2)) {
+ if ( f1->code == (BPF_MISC|BPF_KEY) &&
+ f2->code == (BPF_MISC|BPF_KEY) )
+ continue;
+ return FALSE;
+ }
+ };
+ return TRUE;
+}
+
+unsigned int
+bpf_hash (int n, unsigned int *keys)
+{
+ register unsigned int hval = 0;
+
+ while (n--) {
+ hval += *keys++;
+ }
+ return (hval % NET_HASH_SIZE);
+}
+
+
+int
+bpf_match (net_hash_header_t hash, int n_keys, unsigned int *keys,
+ net_hash_entry_t **hash_headpp, net_hash_entry_t *entpp)
+{
+ register net_hash_entry_t head, entp;
+ register int i;
+
+ if (n_keys != hash->n_keys)
+ return FALSE;
+
+ *hash_headpp = &hash->table[bpf_hash(n_keys, keys)];
+ head = **hash_headpp;
+
+ if (head == 0)
+ return FALSE;
+
+ HASH_ITERATE (head, entp)
+ {
+ for (i = 0; i < n_keys; i++) {
+ if (keys[i] != entp->keys[i])
+ break;
+ }
+ if (i == n_keys) {
+ *entpp = entp;
+ return TRUE;
+ }
+ }
+ HASH_ITERATE_END (head, entp)
+ return FALSE;
+}
+
+/*
+ * Removes a hash entry (ENTP) from its queue (HEAD).
+ * If the reference count of filter (HP) becomes zero and not USED,
+ * HP is removed from the corresponding port lists and is freed.
+ */
+
+int
+hash_ent_remove (if_filter_list_t *ifp, net_hash_header_t hp, int used,
+ net_hash_entry_t *head, net_hash_entry_t entp, queue_entry_t *dead_p)
+{
+ hp->ref_count--;
+
+ if (*head == entp) {
+ if (queue_empty((queue_t) entp)) {
+ *head = 0;
+ ENQUEUE_DEAD(*dead_p, entp, chain);
+ if (hp->ref_count == 0 && !used) {
+ if (((net_rcv_port_t)hp)->filter[0] & NETF_IN)
+ queue_remove(&ifp->if_rcv_port_list,
+ (net_rcv_port_t)hp,
+ net_rcv_port_t, input);
+ if (((net_rcv_port_t)hp)->filter[0] & NETF_OUT)
+ queue_remove(&ifp->if_snd_port_list,
+ (net_rcv_port_t)hp,
+ net_rcv_port_t, output);
+ hp->n_keys = 0;
+ return TRUE;
+ }
+ return FALSE;
+ } else {
+ *head = (net_hash_entry_t)queue_next((queue_t) entp);
+ }
+ }
+
+ remqueue((queue_t)*head, (queue_entry_t)entp);
+ ENQUEUE_DEAD(*dead_p, entp, chain);
+ return FALSE;
+}
+
+/*
+ * net_free_dead_infp (dead_infp)
+ * queue_entry_t dead_infp; list of dead net_rcv_port_t.
+ *
+ * Deallocates dead net_rcv_port_t.
+ * No locks should be held when called.
+ */
+void
+net_free_dead_infp (queue_entry_t dead_infp)
+{
+ register net_rcv_port_t infp, nextfp;
+
+ for (infp = (net_rcv_port_t) dead_infp; infp != 0; infp = nextfp) {
+ nextfp = (net_rcv_port_t) queue_next(&infp->input);
+ mach_port_deallocate(mach_task_self(), infp->rcv_port);
+ free(infp);
+ debug ("a dead infp is freed\n");
+ }
+}
+
+/*
+ * net_free_dead_entp (dead_entp)
+ * queue_entry_t dead_entp; list of dead net_hash_entry_t.
+ *
+ * Deallocates dead net_hash_entry_t.
+ * No locks should be held when called.
+ */
+void
+net_free_dead_entp (queue_entry_t dead_entp)
+{
+ register net_hash_entry_t entp, nextentp;
+
+ for (entp = (net_hash_entry_t)dead_entp; entp != 0; entp = nextentp) {
+ nextentp = (net_hash_entry_t) queue_next(&entp->chain);
+
+ mach_port_deallocate(mach_task_self(), entp->rcv_port);
+ free(entp);
+ debug ("a dead entp is freed\n");
+ }
+}
+
+/*
+ * Set a filter for a network interface.
+ *
+ * We are given a naked send right for the rcv_port.
+ * If we are successful, we must consume that right.
+ */
+io_return_t
+net_set_filter(if_filter_list_t *ifp, mach_port_t rcv_port, int priority,
+ filter_t *filter, unsigned int filter_count)
+{
+ int filter_bytes;
+ bpf_insn_t match;
+ register net_rcv_port_t infp, my_infp;
+ net_rcv_port_t nextfp;
+ net_hash_header_t hhp;
+ register net_hash_entry_t entp, hash_entp=NULL;
+ net_hash_entry_t *head, nextentp;
+ queue_entry_t dead_infp, dead_entp;
+ int i;
+ int ret, is_new_infp;
+ io_return_t rval;
+ boolean_t in, out;
+
+ /* Check the filter syntax. */
+
+ debug ("filter_count: %d, filter[0]: %d\n", filter_count, filter[0]);
+
+ filter_bytes = CSPF_BYTES (filter_count);
+ match = (bpf_insn_t) 0;
+
+ if (filter_count == 0) {
+ return (D_INVALID_OPERATION);
+ } else if (!((filter[0] & NETF_IN) || (filter[0] & NETF_OUT))) {
+ return (D_INVALID_OPERATION); /* NETF_IN or NETF_OUT required */
+ } else if ((filter[0] & NETF_TYPE_MASK) == NETF_BPF) {
+ ret = bpf_validate((bpf_insn_t)filter, filter_bytes, &match);
+ if (!ret)
+ return (D_INVALID_OPERATION);
+ } else {
+ return (D_INVALID_OPERATION);
+ }
+ debug ("net_set_filter: check over\n");
+
+ rval = D_SUCCESS; /* default return value */
+ dead_infp = dead_entp = 0;
+
+ if (match == (bpf_insn_t) 0) {
+ /*
+ * If there is no match instruction, we allocate
+ * a normal packet filter structure.
+ */
+ my_infp = (net_rcv_port_t) calloc(1, sizeof(struct net_rcv_port));
+ my_infp->rcv_port = rcv_port;
+ is_new_infp = TRUE;
+ } else {
+ /*
+ * If there is a match instruction, we assume there will be
+ * multiple sessions with a common substructure and allocate
+ * a hash table to deal with them.
+ */
+ my_infp = 0;
+ hash_entp = (net_hash_entry_t) calloc(1, sizeof(struct net_hash_entry));
+ is_new_infp = FALSE;
+ }
+
+ /*
+ * Look for an existing filter on the same reply port.
+ * Look for filters with dead ports (for GC).
+ * Look for a filter with the same code except KEY insns.
+ */
+ void check_filter_list(queue_head_t *if_port_list)
+ {
+ FILTER_ITERATE(if_port_list, infp, nextfp,
+ (if_port_list == &ifp->if_rcv_port_list)
+ ? &infp->input : &infp->output)
+ {
+ if (infp->rcv_port == MACH_PORT_NULL) {
+ if (match != 0
+ && infp->priority == priority
+ && my_infp == 0
+ && (infp->filter_end - infp->filter) == filter_count
+ && bpf_eq((bpf_insn_t)infp->filter,
+ (bpf_insn_t)filter, filter_bytes))
+ my_infp = infp;
+
+ for (i = 0; i < NET_HASH_SIZE; i++) {
+ head = &((net_hash_header_t) infp)->table[i];
+ if (*head == 0)
+ continue;
+
+ /*
+ * Check each hash entry to make sure the
+ * destination port is still valid. Remove
+ * any invalid entries.
+ */
+ entp = *head;
+ do {
+ nextentp = (net_hash_entry_t) entp->he_next;
+
+ /* checked without
+ ip_lock(entp->rcv_port) */
+ if (entp->rcv_port == rcv_port) {
+ ret = hash_ent_remove (ifp,
+ (net_hash_header_t)infp,
+ (my_infp == infp),
+ head,
+ entp,
+ &dead_entp);
+ if (ret)
+ goto hash_loop_end;
+ }
+
+ entp = nextentp;
+ /* While test checks head since hash_ent_remove
+ * might modify it.
+ */
+ } while (*head != 0 && entp != *head);
+ }
+
+hash_loop_end:
+ ;
+ } else if (infp->rcv_port == rcv_port) {
+
+ /* Remove the old filter from lists */
+ if (infp->filter[0] & NETF_IN)
+ queue_remove(&ifp->if_rcv_port_list, infp,
+ net_rcv_port_t, input);
+ if (infp->filter[0] & NETF_OUT)
+ queue_remove(&ifp->if_snd_port_list, infp,
+ net_rcv_port_t, output);
+
+ ENQUEUE_DEAD(dead_infp, infp, input);
+ }
+ }
+ FILTER_ITERATE_END
+ }
+
+ in = (filter[0] & NETF_IN) != 0;
+ out = (filter[0] & NETF_OUT) != 0;
+
+ if (in)
+ check_filter_list(&ifp->if_rcv_port_list);
+ if (out)
+ check_filter_list(&ifp->if_snd_port_list);
+
+ if (my_infp == 0) {
+ /* Allocate a dummy infp */
+ for (i = 0; i < N_NET_HASH; i++) {
+ if (filter_hash_header[i].n_keys == 0)
+ break;
+ }
+ if (i == N_NET_HASH) {
+ mach_port_deallocate(mach_task_self() , rcv_port);
+ if (match != 0)
+ free(hash_entp);
+
+ rval = D_NO_MEMORY;
+ goto clean_and_return;
+ }
+
+ hhp = &filter_hash_header[i];
+ hhp->n_keys = match->jt;
+
+ hhp->ref_count = 0;
+ for (i = 0; i < NET_HASH_SIZE; i++)
+ hhp->table[i] = 0;
+
+ my_infp = (net_rcv_port_t)hhp;
+ my_infp->rcv_port = MACH_PORT_NULL; /* indication of dummy */
+ is_new_infp = TRUE;
+ }
+
+ if (is_new_infp) {
+ my_infp->priority = priority;
+ my_infp->rcv_count = 0;
+
+ /* Copy filter program. */
+ memcpy (my_infp->filter, filter, filter_bytes);
+ my_infp->filter_end =
+ (filter_t *)((char *)my_infp->filter + filter_bytes);
+
+ /* Insert my_infp according to priority */
+ if (in) {
+ queue_iterate(&ifp->if_rcv_port_list, infp, net_rcv_port_t, input)
+ if (priority > infp->priority)
+ break;
+
+ queue_enter(&ifp->if_rcv_port_list, my_infp, net_rcv_port_t, input);
+ }
+
+ if (out) {
+ queue_iterate(&ifp->if_snd_port_list, infp, net_rcv_port_t, output)
+ if (priority > infp->priority)
+ break;
+
+ queue_enter(&ifp->if_snd_port_list, my_infp, net_rcv_port_t, output);
+ }
+ }
+
+ if (match != 0)
+ {
+ /* Insert to hash list */
+ net_hash_entry_t *p;
+
+ hash_entp->rcv_port = rcv_port;
+ for (i = 0; i < match->jt; i++) /* match->jt is n_keys */
+ hash_entp->keys[i] = match[i+1].k;
+ p = &((net_hash_header_t)my_infp)->
+ table[bpf_hash(match->jt, hash_entp->keys)];
+
+ /* Not checking for the same key values */
+ if (*p == 0) {
+ queue_init ((queue_t) hash_entp);
+ *p = hash_entp;
+ } else {
+ enqueue_tail((queue_t)*p, (queue_entry_t)hash_entp);
+ }
+
+ ((net_hash_header_t)my_infp)->ref_count++;
+ }
+
+clean_and_return:
+ /* No locks are held at this point. */
+
+ if (dead_infp != 0)
+ net_free_dead_infp(dead_infp);
+ if (dead_entp != 0)
+ net_free_dead_entp(dead_entp);
+
+ return (rval);
+}
+
+void
+destroy_filters (if_filter_list_t *ifp)
+{
+}
+
+void
+remove_dead_filter (if_filter_list_t *ifp, queue_head_t *if_port_list,
+ mach_port_t dead_port)
+{
+ net_rcv_port_t infp;
+ net_rcv_port_t nextfp;
+ net_hash_entry_t *head, nextentp;
+ queue_entry_t dead_infp, dead_entp;
+ net_hash_entry_t entp = NULL;
+ int i, ret;
+
+ dead_infp = dead_entp = 0;
+ FILTER_ITERATE (if_port_list, infp, nextfp,
+ (if_port_list == &ifp->if_rcv_port_list)
+ ? &infp->input : &infp->output) {
+ if (infp->rcv_port == MACH_PORT_NULL) {
+ for (i = 0; i < NET_HASH_SIZE; i++) {
+ head = &((net_hash_header_t) infp)->table[i];
+ if (*head == 0)
+ continue;
+
+ /*
+ * Check each hash entry to make sure the
+ * destination port is still valid. Remove
+ * any invalid entries.
+ */
+ entp = *head;
+ do {
+ nextentp = (net_hash_entry_t) entp->he_next;
+
+ /* checked without
+ ip_lock(entp->rcv_port) */
+ if (entp->rcv_port == dead_port) {
+ ret = hash_ent_remove (ifp,
+ (net_hash_header_t) infp,
+ 0,
+ head,
+ entp,
+ &dead_entp);
+ if (ret)
+ goto hash_loop_end;
+ }
+
+ entp = nextentp;
+ /* While test checks head since hash_ent_remove
+ * might modify it.
+ */
+ } while (*head != 0 && entp != *head);
+ }
+
+hash_loop_end:
+ ;
+ } else if (infp->rcv_port == dead_port) {
+ /* Remove the old filter from lists */
+ if (infp->filter[0] & NETF_IN)
+ queue_remove(&ifp->if_rcv_port_list, infp,
+ net_rcv_port_t, input);
+ if (infp->filter[0] & NETF_OUT)
+ queue_remove(&ifp->if_snd_port_list, infp,
+ net_rcv_port_t, output);
+
+ ENQUEUE_DEAD(dead_infp, infp, input);
+ }
+ }
+ FILTER_ITERATE_END
+
+ if (dead_infp != 0)
+ net_free_dead_infp(dead_infp);
+ if (dead_entp != 0)
+ net_free_dead_entp(dead_entp);
+}
diff --git a/libbpf/bpf_impl.h b/libbpf/bpf_impl.h
new file mode 100644
index 00000000..2b092b7e
--- /dev/null
+++ b/libbpf/bpf_impl.h
@@ -0,0 +1,161 @@
+ /*
+ * Mach Operating System
+ * Copyright (c) 1993-1989 Carnegie Mellon University
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify and distribute this software and its
+ * documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ *
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ *
+ * Carnegie Mellon requests users of this software to return to
+ *
+ * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
+ * School of Computer Science
+ * Carnegie Mellon University
+ * Pittsburgh PA 15213-3890
+ *
+ * any improvements or extensions that they make and grant Carnegie Mellon
+ * the rights to redistribute these changes.
+ */
+/*
+ * Author: David B. Golub, Carnegie Mellon University
+ * Date: 3/98
+ *
+ * Network IO.
+ *
+ * Packet filter code taken from vaxif/enet.c written
+ * CMU and Stanford.
+ */
+
+/* the code copied from device/net_io.c in Mach */
+
+#ifndef BPF_IMPL_H
+#define BPF_IMPL_H
+
+#include <device/bpf.h>
+
+#include "queue.h"
+
+typedef struct
+{
+ queue_head_t if_rcv_port_list; /* input filter list */
+ queue_head_t if_snd_port_list; /* output filter list */
+}if_filter_list_t;
+
+typedef unsigned short filter_t;
+typedef filter_t *filter_array_t;
+
+#define NET_MAX_FILTER 128 /* was 64, bpf programs are big */
+
+#define NET_HASH_SIZE 256
+#define N_NET_HASH 4
+#define N_NET_HASH_KEYS 4
+
+#ifndef BPF_ALIGN
+#define EXTRACT_SHORT(p) ((u_short)ntohs(*(u_short *)p))
+#define EXTRACT_LONG(p) (ntohl(*(u_long *)p))
+#else
+#define EXTRACT_SHORT(p)\
+ ((u_short)\
+ ((u_short)*((u_char *)p+0)<<8|\
+ (u_short)*((u_char *)p+1)<<0))
+#define EXTRACT_LONG(p)\
+ ((u_long)*((u_char *)p+0)<<24|\
+ (u_long)*((u_char *)p+1)<<16|\
+ (u_long)*((u_char *)p+2)<<8|\
+ (u_long)*((u_char *)p+3)<<0)
+#endif
+
+#define HASH_ITERATE(head, elt) (elt) = (net_hash_entry_t) (head); do {
+#define HASH_ITERATE_END(head, elt) \
+ (elt) = (net_hash_entry_t) queue_next((queue_entry_t) (elt)); \
+} while ((elt) != (head));
+
+#define FILTER_ITERATE(if_port_list, fp, nextfp, chain) \
+ for ((fp) = (net_rcv_port_t) queue_first(if_port_list); \
+ !queue_end(if_port_list, (queue_entry_t)(fp)); \
+ (fp) = (nextfp)) { \
+ (nextfp) = (net_rcv_port_t) queue_next(chain);
+#define FILTER_ITERATE_END }
+
+/* entry_p must be net_rcv_port_t or net_hash_entry_t */
+#define ENQUEUE_DEAD(dead, entry_p, chain) { \
+ queue_next(&(entry_p)->chain) = (queue_entry_t) (dead); \
+ (dead) = (queue_entry_t)(entry_p); \
+}
+
+#define CSPF_BYTES(n) ((n) * sizeof (filter_t))
+
+/*
+ * Receive port for net, with packet filter.
+ * This data structure by itself represents a packet
+ * filter for a single session.
+ */
+struct net_rcv_port {
+ queue_chain_t input; /* list of input open_descriptors */
+ queue_chain_t output; /* list of output open_descriptors */
+ mach_port_t rcv_port; /* port to send packet to */
+ int rcv_count; /* number of packets received */
+ int priority; /* priority for filter */
+ filter_t *filter_end; /* pointer to end of filter */
+ filter_t filter[NET_MAX_FILTER];
+ /* filter operations */
+};
+typedef struct net_rcv_port *net_rcv_port_t;
+
+/*
+ * A single hash entry.
+ */
+struct net_hash_entry {
+ queue_chain_t chain; /* list of entries with same hval */
+#define he_next chain.next
+#define he_prev chain.prev
+ mach_port_t rcv_port; /* destination port */
+ unsigned int keys[N_NET_HASH_KEYS];
+};
+typedef struct net_hash_entry *net_hash_entry_t;
+
+/*
+ * This structure represents a packet filter with multiple sessions.
+ *
+ * For example, all application level TCP sessions might be
+ * represented by one of these structures. It looks like a
+ * net_rcv_port struct so that both types can live on the
+ * same packet filter queues.
+ */
+struct net_hash_header {
+ struct net_rcv_port rcv;
+ int n_keys; /* zero if not used */
+ int ref_count; /* reference count */
+ net_hash_entry_t table[NET_HASH_SIZE];
+};
+
+typedef struct net_hash_header *net_hash_header_t;
+
+int bpf_do_filter(net_rcv_port_t infp, char *p, unsigned int wirelen,
+ char *header, unsigned int hlen, net_hash_entry_t **hash_headpp,
+ net_hash_entry_t *entpp);
+io_return_t net_set_filter(if_filter_list_t *ifp, mach_port_t rcv_port,
+ int priority, filter_t *filter, unsigned int filter_count);
+
+int bpf_validate(bpf_insn_t f, int bytes, bpf_insn_t *match);
+int bpf_eq (bpf_insn_t f1, bpf_insn_t f2, int bytes);
+unsigned int bpf_hash (int n, unsigned int *keys);
+int bpf_match (net_hash_header_t hash, int n_keys, unsigned int *keys,
+ net_hash_entry_t **hash_headpp, net_hash_entry_t *entpp);
+
+int hash_ent_remove (if_filter_list_t *ifp, net_hash_header_t hp, int used,
+ net_hash_entry_t *head, net_hash_entry_t entp, queue_entry_t *dead_p);
+void net_free_dead_infp (queue_entry_t dead_infp);
+void net_free_dead_entp (queue_entry_t dead_entp);
+void remove_dead_filter (if_filter_list_t *ifp,
+ queue_head_t *if_port_list, mach_port_t dead_port);
+void destroy_filters (if_filter_list_t *ifp);
+
+#endif /* _DEVICE_BPF_H_ */
diff --git a/libbpf/queue.c b/libbpf/queue.c
new file mode 100644
index 00000000..33234344
--- /dev/null
+++ b/libbpf/queue.c
@@ -0,0 +1,131 @@
+/*
+ * Mach Operating System
+ * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify and distribute this software and its
+ * documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ *
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ *
+ * Carnegie Mellon requests users of this software to return to
+ *
+ * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
+ * School of Computer Science
+ * Carnegie Mellon University
+ * Pittsburgh PA 15213-3890
+ *
+ * any improvements or extensions that they make and grant Carnegie Mellon
+ * the rights to redistribute these changes.
+ */
+/*
+ * Routines to implement queue package.
+ */
+
+#include "queue.h"
+
+
+
+/*
+ * Insert element at head of queue.
+ */
+void enqueue_head(
+ register queue_t que,
+ register queue_entry_t elt)
+{
+ elt->next = que->next;
+ elt->prev = que;
+ elt->next->prev = elt;
+ que->next = elt;
+}
+
+/*
+ * Insert element at tail of queue.
+ */
+void enqueue_tail(
+ register queue_t que,
+ register queue_entry_t elt)
+{
+ elt->next = que;
+ elt->prev = que->prev;
+ elt->prev->next = elt;
+ que->prev = elt;
+}
+
+/*
+ * Remove and return element at head of queue.
+ */
+queue_entry_t dequeue_head(
+ register queue_t que)
+{
+ register queue_entry_t elt;
+
+ if (que->next == que)
+ return((queue_entry_t)0);
+
+ elt = que->next;
+ elt->next->prev = que;
+ que->next = elt->next;
+ return(elt);
+}
+
+/*
+ * Remove and return element at tail of queue.
+ */
+queue_entry_t dequeue_tail(
+ register queue_t que)
+{
+ register queue_entry_t elt;
+
+ if (que->prev == que)
+ return((queue_entry_t)0);
+
+ elt = que->prev;
+ elt->prev->next = que;
+ que->prev = elt->prev;
+ return(elt);
+}
+
+/*
+ * Remove arbitrary element from queue.
+ * Does not check whether element is on queue - the world
+ * will go haywire if it isn't.
+ */
+
+/*ARGSUSED*/
+void remqueue(
+ queue_t que,
+ register queue_entry_t elt)
+{
+ elt->next->prev = elt->prev;
+ elt->prev->next = elt->next;
+}
+
+/*
+ * Routines to directly imitate the VAX hardware queue
+ * package.
+ */
+void insque(
+ register struct queue_entry *entry,
+ register struct queue_entry *pred)
+{
+ entry->next = pred->next;
+ entry->prev = pred;
+ (pred->next)->prev = entry;
+ pred->next = entry;
+}
+
+struct queue_entry
+*remque(
+ register struct queue_entry *elt)
+{
+ (elt->next)->prev = elt->prev;
+ (elt->prev)->next = elt->next;
+ return(elt);
+}
+
diff --git a/libbpf/queue.h b/libbpf/queue.h
new file mode 100644
index 00000000..f067f557
--- /dev/null
+++ b/libbpf/queue.h
@@ -0,0 +1,329 @@
+/*
+ * Mach Operating System
+ * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify and distribute this software and its
+ * documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ *
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ *
+ * Carnegie Mellon requests users of this software to return to
+ *
+ * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
+ * School of Computer Science
+ * Carnegie Mellon University
+ * Pittsburgh PA 15213-3890
+ *
+ * any improvements or extensions that they make and grant Carnegie Mellon rights
+ * to redistribute these changes.
+ */
+/*
+ * File: queue.h
+ * Author: Avadis Tevanian, Jr.
+ * Date: 1985
+ *
+ * Type definitions for generic queues.
+ *
+ */
+
+#ifndef _KERN_QUEUE_H_
+#define _KERN_QUEUE_H_
+
+/*
+ * Queue of abstract objects. Queue is maintained
+ * within that object.
+ *
+ * Supports fast removal from within the queue.
+ *
+ * How to declare a queue of elements of type "foo_t":
+ * In the "*foo_t" type, you must have a field of
+ * type "queue_chain_t" to hold together this queue.
+ * There may be more than one chain through a
+ * "foo_t", for use by different queues.
+ *
+ * Declare the queue as a "queue_t" type.
+ *
+ * Elements of the queue (of type "foo_t", that is)
+ * are referred to by reference, and cast to type
+ * "queue_entry_t" within this module.
+ */
+
+/*
+ * A generic doubly-linked list (queue).
+ */
+
+struct queue_entry {
+ struct queue_entry *next; /* next element */
+ struct queue_entry *prev; /* previous element */
+};
+
+typedef struct queue_entry *queue_t;
+typedef struct queue_entry queue_head_t;
+typedef struct queue_entry queue_chain_t;
+typedef struct queue_entry *queue_entry_t;
+
+/*
+ * enqueue puts "elt" on the "queue".
+ * dequeue returns the first element in the "queue".
+ * remqueue removes the specified "elt" from the specified "queue".
+ */
+
+#define enqueue(queue,elt) enqueue_tail(queue, elt)
+#define dequeue(queue) dequeue_head(queue)
+
+void enqueue_head(queue_t, queue_entry_t);
+void enqueue_tail(queue_t, queue_entry_t);
+queue_entry_t dequeue_head(queue_t);
+queue_entry_t dequeue_tail(queue_t);
+void remqueue(queue_t, queue_entry_t);
+
+/*
+ * Macro: queue_init
+ * Function:
+ * Initialize the given queue.
+ * Header:
+ * void queue_init(q)
+ * queue_t q; *MODIFIED*
+ */
+#define queue_init(q) ((q)->next = (q)->prev = q)
+
+/*
+ * Macro: queue_first
+ * Function:
+ * Returns the first entry in the queue,
+ * Header:
+ * queue_entry_t queue_first(q)
+ * queue_t q; *IN*
+ */
+#define queue_first(q) ((q)->next)
+
+/*
+ * Macro: queue_next
+ * Function:
+ * Returns the entry after an item in the queue.
+ * Header:
+ * queue_entry_t queue_next(qc)
+ * queue_t qc;
+ */
+#define queue_next(qc) ((qc)->next)
+
+/*
+ * Macro: queue_last
+ * Function:
+ * Returns the last entry in the queue.
+ * Header:
+ * queue_entry_t queue_last(q)
+ * queue_t q; *IN*
+ */
+#define queue_last(q) ((q)->prev)
+
+/*
+ * Macro: queue_prev
+ * Function:
+ * Returns the entry before an item in the queue.
+ * Header:
+ * queue_entry_t queue_prev(qc)
+ * queue_t qc;
+ */
+#define queue_prev(qc) ((qc)->prev)
+
+/*
+ * Macro: queue_end
+ * Function:
+ * Tests whether a new entry is really the end of
+ * the queue.
+ * Header:
+ * boolean_t queue_end(q, qe)
+ * queue_t q;
+ * queue_entry_t qe;
+ */
+#define queue_end(q, qe) ((q) == (qe))
+
+/*
+ * Macro: queue_empty
+ * Function:
+ * Tests whether a queue is empty.
+ * Header:
+ * boolean_t queue_empty(q)
+ * queue_t q;
+ */
+#define queue_empty(q) queue_end((q), queue_first(q))
+
+
+/*----------------------------------------------------------------*/
+/*
+ * Macros that operate on generic structures. The queue
+ * chain may be at any location within the structure, and there
+ * may be more than one chain.
+ */
+
+/*
+ * Macro: queue_enter
+ * Function:
+ * Insert a new element at the tail of the queue.
+ * Header:
+ * void queue_enter(q, elt, type, field)
+ * queue_t q;
+ * <type> elt;
+ * <type> is what's in our queue
+ * <field> is the chain field in (*<type>)
+ */
+#define queue_enter(head, elt, type, field) \
+{ \
+ register queue_entry_t prev; \
+ \
+ prev = (head)->prev; \
+ if ((head) == prev) { \
+ (head)->next = (queue_entry_t) (elt); \
+ } \
+ else { \
+ ((type)prev)->field.next = (queue_entry_t)(elt);\
+ } \
+ (elt)->field.prev = prev; \
+ (elt)->field.next = head; \
+ (head)->prev = (queue_entry_t) elt; \
+}
+
+/*
+ * Macro: queue_enter_first
+ * Function:
+ * Insert a new element at the head of the queue.
+ * Header:
+ * void queue_enter_first(q, elt, type, field)
+ * queue_t q;
+ * <type> elt;
+ * <type> is what's in our queue
+ * <field> is the chain field in (*<type>)
+ */
+#define queue_enter_first(head, elt, type, field) \
+{ \
+ register queue_entry_t next; \
+ \
+ next = (head)->next; \
+ if ((head) == next) { \
+ (head)->prev = (queue_entry_t) (elt); \
+ } \
+ else { \
+ ((type)next)->field.prev = (queue_entry_t)(elt);\
+ } \
+ (elt)->field.next = next; \
+ (elt)->field.prev = head; \
+ (head)->next = (queue_entry_t) elt; \
+}
+
+/*
+ * Macro: queue_field [internal use only]
+ * Function:
+ * Find the queue_chain_t (or queue_t) for the
+ * given element (thing) in the given queue (head)
+ */
+#define queue_field(head, thing, type, field) \
+ (((head) == (thing)) ? (head) : &((type)(thing))->field)
+
+/*
+ * Macro: queue_remove
+ * Function:
+ * Remove an arbitrary item from the queue.
+ * Header:
+ * void queue_remove(q, qe, type, field)
+ * arguments as in queue_enter
+ */
+#define queue_remove(head, elt, type, field) \
+{ \
+ register queue_entry_t next, prev; \
+ \
+ next = (elt)->field.next; \
+ prev = (elt)->field.prev; \
+ \
+ if ((head) == next) \
+ (head)->prev = prev; \
+ else \
+ ((type)next)->field.prev = prev; \
+ \
+ if ((head) == prev) \
+ (head)->next = next; \
+ else \
+ ((type)prev)->field.next = next; \
+}
+
+/*
+ * Macro: queue_remove_first
+ * Function:
+ * Remove and return the entry at the head of
+ * the queue.
+ * Header:
+ * queue_remove_first(head, entry, type, field)
+ * entry is returned by reference
+ */
+#define queue_remove_first(head, entry, type, field) \
+{ \
+ register queue_entry_t next; \
+ \
+ (entry) = (type) ((head)->next); \
+ next = (entry)->field.next; \
+ \
+ if ((head) == next) \
+ (head)->prev = (head); \
+ else \
+ ((type)(next))->field.prev = (head); \
+ (head)->next = next; \
+}
+
+/*
+ * Macro: queue_remove_last
+ * Function:
+ * Remove and return the entry at the tail of
+ * the queue.
+ * Header:
+ * queue_remove_last(head, entry, type, field)
+ * entry is returned by reference
+ */
+#define queue_remove_last(head, entry, type, field) \
+{ \
+ register queue_entry_t prev; \
+ \
+ (entry) = (type) ((head)->prev); \
+ prev = (entry)->field.prev; \
+ \
+ if ((head) == prev) \
+ (head)->next = (head); \
+ else \
+ ((type)(prev))->field.next = (head); \
+ (head)->prev = prev; \
+}
+
+/*
+ * Macro: queue_assign
+ */
+#define queue_assign(to, from, type, field) \
+{ \
+ ((type)((from)->prev))->field.next = (to); \
+ ((type)((from)->next))->field.prev = (to); \
+ *to = *from; \
+}
+
+/*
+ * Macro: queue_iterate
+ * Function:
+ * iterate over each item in the queue.
+ * Generates a 'for' loop, setting elt to
+ * each item in turn (by reference).
+ * Header:
+ * queue_iterate(q, elt, type, field)
+ * queue_t q;
+ * <type> elt;
+ * <type> is what's in our queue
+ * <field> is the chain field in (*<type>)
+ */
+#define queue_iterate(head, elt, type, field) \
+ for ((elt) = (type) queue_first(head); \
+ !queue_end((head), (queue_entry_t)(elt)); \
+ (elt) = (type) queue_next(&(elt)->field))
+
+#endif /* _KERN_QUEUE_H_ */
diff --git a/libbpf/util.h b/libbpf/util.h
new file mode 100644
index 00000000..b062638d
--- /dev/null
+++ b/libbpf/util.h
@@ -0,0 +1,91 @@
+/*
+ Copyright (C) 2008 Free Software Foundation, Inc.
+ Written by Zheng Da.
+
+ This file is part of the GNU Hurd.
+
+ The GNU Hurd is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ The GNU Hurd is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with the GNU Hurd; see the file COPYING. If not, write to
+ the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+
+#ifndef UTIL_H
+#define UTIL_H
+
+#include <stdio.h>
+#include <execinfo.h>
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <arpa/inet.h>
+#include <netinet/ip.h>
+
+#include <mach.h>
+
+#ifdef DEBUG
+
+#define debug(format, ...) do \
+{ \
+ char buf[1024]; \
+ snprintf (buf, 1024, "multiplexer: %s: %s\n", __func__, format); \
+ fprintf (stderr , buf, ## __VA_ARGS__); \
+ fflush (stderr); \
+} while (0)
+
+#else
+
+#define debug(format, ...) do {} while (0)
+
+#endif
+
+#define print_backtrace() do \
+{ \
+ size_t size; \
+ void *array[30]; \
+ size = backtrace (array, sizeof (array)); \
+ debug ("the depth of the stack: %d", size); \
+ backtrace_symbols_fd(array, size, fileno (stderr)); \
+} while (0)
+
+#define ETH_ALEN 6 /* Octets in one ethernet addr */
+
+struct ethhdr
+{
+ unsigned char h_dest[ETH_ALEN]; /* destination eth addr */
+ unsigned char h_source[ETH_ALEN]; /* source ether addr */
+ unsigned short h_proto; /* packet type ID field */
+};
+
+static inline void
+print_pack (char *packet, int len)
+{
+#ifdef DEBUG
+#define ETH_P_IP 0x0800
+ struct ethhdr *ethh = (struct ethhdr *) packet;
+ struct iphdr *iph = (struct iphdr *)(ethh + 1);
+ char src_str[INET_ADDRSTRLEN];
+ char dst_str[INET_ADDRSTRLEN];
+ if (ntohs (ethh->h_proto) == ETH_P_IP
+ && len >= sizeof (struct ethhdr) + sizeof (struct iphdr))
+ {
+ debug ("multiplexer: get a IP packet from %s to %s\n",
+ inet_ntop (AF_INET, &iph->saddr, src_str, INET_ADDRSTRLEN),
+ inet_ntop (AF_INET, &iph->daddr, dst_str, INET_ADDRSTRLEN));
+ }
+ else
+ {
+ debug ("multiplexer: get a non-IP packet\n");
+ }
+#endif
+}
+
+#endif