nta.6

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

diff --git a/drivers/net/3c59x.c b/drivers/net/3c59x.c
index 80e8ca0..4aba97b 100644
--- a/drivers/net/3c59x.c
+++ b/drivers/net/3c59x.c
@@ -1680,7 +1680,7 @@ vortex_open(struct net_device *dev)
 			vp->rx_ring[i].next = cpu_to_le32(vp->rx_ring_dma + sizeof(struct boom_rx_desc) * (i+1));
 			vp->rx_ring[i].status = 0;	/* Clear complete bit. */
 			vp->rx_ring[i].length = cpu_to_le32(PKT_BUF_SZ | LAST_FRAG);
-			skb = dev_alloc_skb(PKT_BUF_SZ);
+			skb = netdev_alloc_skb(dev, PKT_BUF_SZ);
 			vp->rx_skbuff[i] = skb;
 			if (skb == NULL)
 				break;			/* Bad news!  */
@@ -2405,7 +2405,7 @@ static int vortex_rx(struct net_device *
 			int pkt_len = rx_status & 0x1fff;
 			struct sk_buff *skb;
 
-			skb = dev_alloc_skb(pkt_len + 5);
+			skb = netdev_alloc_skb(dev, pkt_len + 5);
 			if (vortex_debug > 4)
 				printk(KERN_DEBUG "Receiving packet size %d status %4.4x.\n",
 					   pkt_len, rx_status);
@@ -2486,7 +2486,7 @@ boomerang_rx(struct net_device *dev)
 
 			/* Check if the packet is long enough to just accept without
 			   copying to a properly sized skbuff. */
-			if (pkt_len < rx_copybreak && (skb = dev_alloc_skb(pkt_len + 2)) != 0) {
+			if (pkt_len < rx_copybreak && (skb = netdev_alloc_skb(dev, pkt_len + 2)) != 0) {
 				skb->dev = dev;
 				skb_reserve(skb, 2);	/* Align IP on 16 byte boundaries */
 				pci_dma_sync_single_for_cpu(VORTEX_PCI(vp), dma, PKT_BUF_SZ, PCI_DMA_FROMDEVICE);
@@ -2525,7 +2525,7 @@ boomerang_rx(struct net_device *dev)
 		struct sk_buff *skb;
 		entry = vp->dirty_rx % RX_RING_SIZE;
 		if (vp->rx_skbuff[entry] == NULL) {
-			skb = dev_alloc_skb(PKT_BUF_SZ);
+			skb = netdev_alloc_skb(dev, PKT_BUF_SZ);
 			if (skb == NULL) {
 				static unsigned long last_jif;
 				if (time_after(jiffies, last_jif + 10 * HZ)) {
diff --git a/include/linux/avl.h b/include/linux/avl.h
new file mode 100644
index 0000000..2c715bb
--- /dev/null
+++ b/include/linux/avl.h
@@ -0,0 +1,249 @@
+/*
+ * 	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);
+#ifdef CONFIG_ZCSNIFF
+	struct avl_node_entry	*entry;
+#endif
+};
+
+/*
+ * 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;
+};
+
+#ifdef CONFIG_NETALLOC
+void *avl_alloc(unsigned int size, gfp_t gfp_mask);
+void avl_free(void *ptr, unsigned int size);
+int avl_init(void);
+#else
+static inline void *avl_alloc(unsigned int size, gfp_t gfp_mask)
+{
+	return kmalloc(size, gfp_mask);
+}
+static inline void avl_free(void *ptr, unsigned int size)
+{
+	kfree(ptr);
+}
+static inline int avl_init(void)
+{
+	return 0;
+}
+#endif
+void avl_free_no_zc(void *ptr, unsigned int size);
+
+#ifdef CONFIG_ZCSNIFF
+int avl_init_zc(void);
+#else
+static inline int avl_init_zc(void)
+{
+	return 0;
+}
+#endif
+
+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/include/linux/skbuff.h b/include/linux/skbuff.h
index 19c96d4..c7c6cc1 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -29,6 +29,7 @@ #include <linux/net.h>
 #include <linux/textsearch.h>
 #include <net/checksum.h>
 #include <linux/dmaengine.h>
+#include <linux/avl.h>
 
 #define HAVE_ALLOC_SKB		/* For the drivers to know */
 #define HAVE_ALIGNABLE_SKB	/* Ditto 8)		   */
@@ -282,7 +283,8 @@ struct sk_buff {
 				nfctinfo:3;
 	__u8			pkt_type:3,
 				fclone:2,
-				ipvs_property:1;
+				ipvs_property:1,
+				nta:1;
 	__be16			protocol;
 
 	void			(*destructor)(struct sk_buff *skb);
@@ -331,18 +333,35 @@ extern void kfree_skb(struct sk_buff *sk
 extern void	       __kfree_skb(struct sk_buff *skb);
 extern struct sk_buff *__alloc_skb(unsigned int size,
 				   gfp_t priority, int fclone);
+extern struct sk_buff *__alloc_skb_emtpy(unsigned int size,
+				   gfp_t priority);
+extern struct sk_buff *__alloc_skb_nta(unsigned int size, gfp_t gfp_mask,
+			    int fclone);
+
 static inline struct sk_buff *alloc_skb(unsigned int size,
 					gfp_t priority)
 {
 	return __alloc_skb(size, priority, 0);
 }
 
+static inline struct sk_buff *alloc_skb_empty(unsigned int size,
+					gfp_t priority)
+{
+	return __alloc_skb_emtpy(size, priority);
+}
+
 static inline struct sk_buff *alloc_skb_fclone(unsigned int size,
 					       gfp_t priority)
 {
 	return __alloc_skb(size, priority, 1);
 }
 
+static inline struct sk_buff *alloc_skb_nta(unsigned int size,
+					gfp_t priority, int fclone)
+{
+	return __alloc_skb_nta(size, priority, fclone);
+}
+
 extern struct sk_buff *alloc_skb_from_cache(kmem_cache_t *cp,
 					    unsigned int size,
 					    gfp_t priority);
diff --git a/include/net/sock.h b/include/net/sock.h
index 324b3ea..6af3198 100644
--- a/include/net/sock.h
+++ b/include/net/sock.h
@@ -1178,7 +1178,7 @@ static inline struct sk_buff *sk_stream_
 	int hdr_len;
 
 	hdr_len = SKB_DATA_ALIGN(sk->sk_prot->max_header);
-	skb = alloc_skb_fclone(size + hdr_len, gfp);
+	skb = alloc_skb_nta(size + hdr_len, gfp, 1);
 	if (skb) {
 		skb->truesize += mem;
 		if (sk_stream_wmem_schedule(sk, skb->truesize)) {
diff --git a/net/Kconfig b/net/Kconfig
index c6cec5a..4ceb992 100644
--- a/net/Kconfig
+++ b/net/Kconfig
@@ -205,6 +205,8 @@ source "net/econet/Kconfig"
 source "net/wanrouter/Kconfig"
 source "net/sched/Kconfig"
 
+source "net/core/alloc/Kconfig"
+
 menu "Network testing"
 
 config NET_PKTGEN
diff --git a/net/core/Makefile b/net/core/Makefile
index 2645ba4..2c1f594 100644
--- a/net/core/Makefile
+++ b/net/core/Makefile
@@ -10,6 +10,8 @@ obj-$(CONFIG_SYSCTL) += sysctl_net_core.
 obj-y		     += dev.o ethtool.o dev_mcast.o dst.o netevent.o \
 			neighbour.o rtnetlink.o utils.o link_watch.o filter.o
 
+obj-$(CONFIG_NETALLOC) += alloc/
+
 obj-$(CONFIG_XFRM) += flow.o
 obj-$(CONFIG_SYSFS) += net-sysfs.o
 obj-$(CONFIG_NET_DIVERT) += dv.o
diff --git a/net/core/alloc/Kconfig b/net/core/alloc/Kconfig
new file mode 100644
index 0000000..4bcca31
--- /dev/null
+++ b/net/core/alloc/Kconfig
@@ -0,0 +1,29 @@
+config NETALLOC
+	bool "Network allocator"
+	---help---
+	  Very fast network allocator which is not based on power-of-two design.
+	  Main features:
+		* reduced fragmentation (self defragmentation)
+		* possibility to create zero-copy sending and receiving
+		* greater than SLAB speed
+		* full per CPU allocation and freeing (objects are never freed on different CPU)
+		* dynamically grown cache
+		* separate network allocations from main system's ones
+
+config ZCSNIFF
+	depends on NETALLOC
+	bool "Zero-copy sniffer"
+	---help---
+	  This allows to create special zero-copy sniffer char device.
+	  It is based on network allocator and reads special commands
+	  from this device which allow to find where in network allocator's
+	  mapped area appropriate packets live. Read commands must be written
+	  back to kernel when userspace completed with packet. Mmap configuration
+	  can be obtained through ioctl over sniffer char device.
+
+	  This option also allows to create zero-copy sending mechanism, which
+	  contains of two phases:
+	    * allocation of free area, pointer to which is accessed through similar 
+		to above steps
+	    * commiting of new packet, where special skb is attached to allocated
+		above area, route selected and packets is sent to the wire.
diff --git a/net/core/alloc/Makefile b/net/core/alloc/Makefile
new file mode 100644
index 0000000..06362f8
--- /dev/null
+++ b/net/core/alloc/Makefile
@@ -0,0 +1,4 @@
+obj-$(CONFIG_NETALLOC)		:= allocator.o
+
+allocator-y	:= avl.o
+allocator-$(CONFIG_ZCSNIFF)	+= zc.o
diff --git a/net/core/alloc/avl.c b/net/core/alloc/avl.c
new file mode 100644
index 0000000..b2ca95c
--- /dev/null
+++ b/net/core/alloc/avl.c
@@ -0,0 +1,772 @@
+/*
+ * 	avl.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/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>