nta.5

实现linux平台下零拷贝技术的软件包。

+	panic("Failed to initialize network allocator.\n");
+
+	return -ENOMEM;
+}
diff --git a/net/core/alloc/avl.h b/net/core/alloc/avl.h
new file mode 100644
index 0000000..2a72b9f
--- /dev/null
+++ b/net/core/alloc/avl.h
@@ -0,0 +1,224 @@
+/*
+ * 	avl.h
+ * 
+ * 2006 Copyright (c) Evgeniy Polyakov <[e-mail]>
+ * All rights reserved.
+ * 
+ * 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 of the License, 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
+ * MERCHAAVLBILITY 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef __AVL_H
+#define __AVL_H
+
+/*
+ * Zero-copy allocation control block.
+ * @ptr - pointer to allocated data.
+ * @off - offset inside given @avl_node_entry pages (absolute number of bytes)
+ * @size - size of the appropriate object
+ * @entry - number of @avl_node_entry which holds allocated object
+ * @number - number of @order-order pages in given @avl_node_entry
+ */
+
+struct zc_data
+{
+	union {
+		__u32		data[2];
+		void		*ptr;
+	} data;
+
+	__u32			off;
+	__u32			size;
+
+	__u32			entry;
+	__u32			cpu;
+};
+
+#define ZC_MAX_ENTRY_NUM	170
+
+/*
+ * Zero-copy allocation request.
+ * @type - type of the message - ipv4/ipv6/...
+ * @res_len - length of reserved area at the beginning.
+ * @data - allocation control block.
+ */
+struct zc_alloc_ctl
+{
+	__u16		type;
+	__u16		res_len;
+	struct zc_data	zc;
+};
+
+struct zc_entry_status
+{
+	__u16		node_order, node_num;
+};
+
+struct zc_status
+{
+	unsigned int	entry_num;
+	struct zc_entry_status	entry[ZC_MAX_ENTRY_NUM];
+};
+
+#define ZC_ALLOC	_IOWR('Z', 1, struct zc_alloc_ctl)
+#define ZC_COMMIT	_IOR('Z', 2, struct zc_alloc_ctl)
+#define ZC_SET_CPU	_IOR('Z', 3, int)
+#define ZC_STATUS	_IOWR('Z', 4, struct zc_status)
+
+#define AVL_ORDER		2	/* Maximum allocation order */
+#define AVL_BITS		7	/* Must cover maximum number of pages used for allocation pools */
+
+#ifdef __KERNEL__
+#include <linux/kernel.h>
+#include <linux/types.h>
+#include <linux/wait.h>
+#include <linux/spinlock.h>
+#include <asm/page.h>
+
+//#define AVL_DEBUG
+
+#ifdef AVL_DEBUG
+#define ulog(f, a...) printk(f, ##a)
+#else
+#define ulog(f, a...)
+#endif
+
+/*
+ * Network tree allocator variables.
+ */
+
+#define AVL_CANARY		0xc0d0e0f0
+
+#define AVL_ALIGN_SIZE		L1_CACHE_BYTES
+#define AVL_ALIGN(x) 		ALIGN(x, AVL_ALIGN_SIZE)
+
+#define AVL_NODES_ON_PAGE	(PAGE_SIZE/sizeof(struct avl_node))
+#define AVL_NODE_NUM		(1UL<<AVL_BITS)
+#define AVL_NODE_PAGES		((AVL_NODE_NUM+AVL_NODES_ON_PAGE-1)/AVL_NODES_ON_PAGE)
+
+#define AVL_MIN_SIZE		AVL_ALIGN_SIZE
+#define AVL_MAX_SIZE		((1<<AVL_ORDER) << PAGE_SHIFT)
+
+#define AVL_CONTAINER_ARRAY_SIZE	(AVL_MAX_SIZE/AVL_MIN_SIZE)
+
+struct avl_node_entry;
+
+/*
+ * Meta-information container for each contiguous block used in allocation.
+ * @value - start address of the contiguous block.
+ * @mask - bitmask of free and empty chunks [1 - free, 0 - used].
+ * @entry - pointer to parent node entry.
+ */
+struct avl_node
+{
+	unsigned long		value;
+	DECLARE_BITMAP(mask, AVL_MAX_SIZE/AVL_MIN_SIZE);
+	struct avl_node_entry	*entry;
+};
+
+/*
+ * Free chunks are dereferenced into this structure and placed into LIFO list.
+ */
+
+struct avl_container
+{
+	void			*ptr;
+	struct list_head	centry;
+};
+
+/*
+ * When freeing happens on different than allocation CPU,
+ * chunk is dereferenced into this structure and placed into
+ * single-linked list in allocation CPU private area.
+ */
+
+struct avl_free_list
+{
+	struct avl_free_list		*next;
+	unsigned int			size;
+	unsigned int			cpu;
+};
+
+/*
+ * This structure is placed after each allocated chunk and contains
+ * @canary - used to check memory overflow and reference counter for
+ * given memory region, which is used for example for zero-copy access.
+ * @size - used to check that freeing size is exactly the size of the object.
+ */
+
+struct avl_chunk
+{
+	unsigned int			canary, size;
+	atomic_t			refcnt;
+};
+
+/*
+ * Each array of nodes is places into dynamically grown list.
+ * @avl_node_array - array of nodes (linked into pages)
+ * @node_entry - entry in avl_allocator_data.avl_node_list.
+ * @avl_node_order - allocation order for each node in @avl_node_array
+ * @avl_node_num - number of nodes in @avl_node_array
+ * @avl_entry_num - number of this entry inside allocator
+ */
+
+struct avl_node_entry
+{
+	struct avl_node 	**avl_node_array;
+	struct list_head	node_entry;
+	u32			avl_entry_num;
+	u16 			avl_node_order, avl_node_num;
+};
+
+/*
+ * Main per-cpu allocator structure.
+ * @avl_container_array - array of lists of free chunks indexed by size of the elements
+ * @avl_free_list_head - single-linked list of objects, which were started to be freed on different CPU
+ * @avl_free_list_map_head - single-linked list of objects, which map update was started on different CPU
+ * @avl_free_lock - lock protecting avl_free_list_head
+ * @avl_node_list - list of avl_node_entry'es
+ * @avl_node_lock - lock used to protect avl_node_list from access from zero-copy devices.
+ * @entry_num - number of entries inside allocator.
+ */
+struct avl_allocator_data
+{
+	struct list_head 	*avl_container_array;
+	struct avl_free_list 	*avl_free_list_head;
+	struct avl_free_list 	*avl_free_map_list_head;
+	spinlock_t 		avl_free_lock;
+	struct list_head 	avl_node_list;
+	spinlock_t 		avl_node_lock;
+	u32			avl_entry_num;
+};
+
+void *avl_alloc(unsigned int size, gfp_t gfp_mask);
+void avl_free(void *ptr, unsigned int size);
+void avl_free_no_zc(void *ptr, unsigned int size);
+
+int avl_init_zc(void);
+int avl_init(void);
+void avl_fill_zc(struct zc_data *zc, void *ptr, unsigned int size);
+
+struct zc_control
+{
+	struct zc_data		*zcb;
+	unsigned int		zc_num, zc_used, zc_pos;
+	spinlock_t		zc_lock;
+	wait_queue_head_t	zc_wait;
+};
+
+extern struct zc_control zc_sniffer;
+extern struct avl_allocator_data avl_allocator[NR_CPUS];
+
+#endif /* __KERNEL__ */
+#endif /* __AVL_H */
diff --git a/net/core/alloc/zc.c b/net/core/alloc/zc.c
new file mode 100644
index 0000000..f321218
--- /dev/null
+++ b/net/core/alloc/zc.c
@@ -0,0 +1,483 @@
+/*
+ * 	zc.c
+ * 
+ * 2006 Copyright (c) Evgeniy Polyakov <[e-mail]>
+ * All rights reserved.
+ * 
+ * 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 of the License, 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/types.h>
+#include <linux/string.h>
+#include <linux/errno.h>
+#include <linux/slab.h>
+#include <linux/spinlock.h>
+#include <linux/percpu.h>
+#include <linux/list.h>
+#include <linux/mm.h>
+#include <linux/fs.h>
+#include <linux/poll.h>
+#include <linux/ioctl.h>
+#include <linux/skbuff.h>
+#include <linux/netfilter.h>
+#include <linux/netfilter_ipv4.h>
+#include <linux/ip.h>
+#include <net/flow.h>
+#include <net/dst.h>
+#include <net/route.h>
+#include <asm/uaccess.h>
+
+#include "avl.h"
+
+struct zc_private
+{
+	struct zc_data	*zcb;
+	struct mutex	lock;
+	int		cpu;
+};
+
+static char zc_name[] = "zc";
+static int zc_major;
+struct zc_control zc_sniffer;
+
+static int zc_release(struct inode *inode, struct file *file)
+{
+	struct zc_private *priv = file->private_data;
+
+	kfree(priv);
+	return 0;
+}
+
+static int zc_open(struct inode *inode, struct file *file)
+{
+	struct zc_private *priv;
+	struct zc_control *ctl = &zc_sniffer;
+
+	priv = kzalloc(sizeof(struct zc_private) + ctl->zc_num * sizeof(struct zc_data), GFP_KERNEL);
+	if (!priv)
+		return -ENOMEM;
+	priv->zcb = (struct zc_data *)(priv+1);
+	priv->cpu = 0; /* Use CPU0 by default */
+	mutex_init(&priv->lock);
+
+	file->private_data = priv;
+
+	return 0;
+}
+
+static int zc_mmap(struct file *file, struct vm_area_struct *vma)
+{
+	struct zc_private *priv = file->private_data;
+	struct avl_allocator_data *alloc = &avl_allocator[priv->cpu];
+	struct avl_node_entry *e;
+	unsigned long flags, start = vma->vm_start;
+	int err = 0, idx, off;
+	unsigned int i, j, st, num, total_num;
+
+	st = vma->vm_pgoff;
+	total_num = (vma->vm_end - vma->vm_start)/PAGE_SIZE;
+
+	printk("%s: start: %lx, end: %lx, total_num: %u, st: %u.\n", __func__, start, vma->vm_end, total_num, st);
+
+	vma->vm_page_prot = pgprot_noncached(vma->vm_page_prot);
+	vma->vm_flags |= VM_RESERVED;
+	vma->vm_file = file;
+
+	spin_lock_irqsave(&alloc->avl_node_lock, flags);
+	list_for_each_entry(e, &alloc->avl_node_list, node_entry) {
+		if (st >= e->avl_node_num*(1U<<e->avl_node_order)) {
+#if 0
+			printk("%s: continue on cpu: %d, e: %p, total_num: %u, node_num: %u, node_order: %u, pages_in_node: %u, st: %u.\n", 
+					__func__, priv->cpu, e, total_num, e->avl_node_num, e->avl_node_order, 
+					e->avl_node_num*(1U<<e->avl_node_order), st);
+#endif
+			st -= e->avl_node_num*(1U<<e->avl_node_order);
+			continue;
+		}
+		num = min_t(unsigned int, total_num, e->avl_node_num*(1<<e->avl_node_order));
+
+		printk("%s: cpu: %d, e: %p, total_num: %u, node_num: %u, node_order: %u, st: %u, num: %u.\n", 
+				__func__, priv->cpu, e, total_num, e->avl_node_num, e->avl_node_order, st, num);
+
+		idx = 0;
+		off = st;
+		for (i=st; i<num;) {
+			struct avl_node *node = &e->avl_node_array[idx][off];
+
+			if (++off >= AVL_NODES_ON_PAGE) {
+				idx++;
+				off = 0;
+			}
+
+			for (j=0; (j<(1<<e->avl_node_order)) && (i<num); ++j, ++i) {
+				unsigned long virt = node->value + (j<<PAGE_SHIFT);
+				err = vm_insert_page(vma, start, virt_to_page(virt));
+				if (err) {
+					printk("\n%s: Failed to insert page for addr %lx into %lx, err: %d.\n",
+							__func__, virt, start, err);
+					break;
+				}
+				start += PAGE_SIZE;
+			}
+		}
+		if (err)
+			break;
+		total_num -= num;
+
+		if (total_num == 0)
+			break;
+	}
+	spin_unlock_irqrestore(&alloc->avl_node_lock, flags);
+
+	return err;
+}
+
+static ssize_t zc_write(struct file *file, const char __user *buf, size_t size, loff_t *off)
+{
+	ssize_t sz = 0;
+	struct zc_private *priv = file->private_data;
+	unsigned long flags;
+	unsigned int req_num = size/sizeof(struct zc_data), cnum, csize, i;
+	struct zc_control *ctl = &zc_sniffer;
+
+	while (size) {
+		cnum = min_t(unsigned int, req_num, ctl->zc_num);
+		csize = cnum*sizeof(struct zc_data);
+
+		if (copy_from_user(priv->zcb, buf, csize)) {
+			printk("%s: copy_from_user() failed.\n", __func__);
+			break;
+		}
+
+		spin_lock_irqsave(&ctl->zc_lock, flags);
+		for (i=0; i<cnum; ++i)
+			avl_free_no_zc(priv->zcb[i].data.ptr, priv->zcb[i].size);
+		ctl->zc_used -= cnum;
+		spin_unlock_irqrestore(&ctl->zc_lock, flags);
+
+		sz += csize;
+		size -= csize;
+		buf += csize;
+	}
+
+	return sz;
+}
+
+static ssize_t zc_read(struct file *file, char __user *buf, size_t size, loff_t *off)
+{
+	ssize_t sz = 0;
+	struct zc_private *priv = file->private_data;
+	unsigned long flags;
+	unsigned int pos, req_num = size/sizeof(struct zc_data), cnum, csize;
+	struct zc_control *ctl = &zc_sniffer;
+
+	wait_event_interruptible(ctl->zc_wait, ctl->zc_used > 0);
+
+	spin_lock_irqsave(&ctl->zc_lock, flags);
+	cnum = min_t(unsigned int, req_num, ctl->zc_used);
+	csize = cnum*sizeof(struct zc_data);
+	if (ctl->zc_used) {
+		if (ctl->zc_pos >= ctl->zc_used) {
+			pos = ctl->zc_pos - ctl->zc_used;
+			memcpy(priv->zcb, &ctl->zcb[pos], csize);
+		} else {
+			memcpy(priv->zcb, &ctl->zcb[0], csize);
+			pos = ctl->zc_num - (ctl->zc_used - ctl->zc_pos);
+			memcpy(&priv->zcb[ctl->zc_pos], &ctl->zcb[pos], 
+					(ctl->zc_used - ctl->zc_pos)*sizeof(struct zc_data));
+		}
+	}
+	spin_unlock_irqrestore(&ctl->zc_lock, flags);
+
+	sz = csize;
+
+	if (copy_to_user(buf, priv->zcb, cnum*sizeof(struct zc_data)))
+		sz = -EFAULT;
+
+	return sz;