nta.1

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

diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index 19c96d4..ded8b31 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -311,7 +311,7 @@ #endif
 
 
 	/* These elements must be at the end, see alloc_skb() for details.  */
-	unsigned int		truesize;
+	unsigned int		truesize, __tsize;
 	atomic_t		users;
 	unsigned char		*head,
 				*data,
@@ -327,6 +327,10 @@ #include <linux/slab.h>
 
 #include <asm/system.h>
 
+extern void *avl_alloc(unsigned int size, gfp_t gfp_mask);
+extern void avl_free(void *ptr, unsigned int size);
+extern int avl_init(void);
+
 extern void kfree_skb(struct sk_buff *skb);
 extern void	       __kfree_skb(struct sk_buff *skb);
 extern struct sk_buff *__alloc_skb(unsigned int size,
diff --git a/net/core/Makefile b/net/core/Makefile
index 2645ba4..d86d468 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-y += alloc/
+
 obj-$(CONFIG_XFRM) += flow.o
 obj-$(CONFIG_SYSFS) += net-sysfs.o
 obj-$(CONFIG_NET_DIVERT) += dv.o
diff --git a/net/core/alloc/Makefile b/net/core/alloc/Makefile
new file mode 100644
index 0000000..a98ee88
--- /dev/null
+++ b/net/core/alloc/Makefile
@@ -0,0 +1,3 @@
+obj-y		:= allocator.o
+
+allocator-y	:= avl.o
diff --git a/net/core/alloc/avl.c b/net/core/alloc/avl.c
new file mode 100644
index 0000000..ff85519
--- /dev/null
+++ b/net/core/alloc/avl.c
@@ -0,0 +1,882 @@
+/*
+ * 	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>
+#include <linux/mm.h>
+#include <linux/skbuff.h>
+
+#include "avl.h"
+
+#define AVL_CONTAINER_ARRAY_SIZE	(AVL_MAX_SIZE/AVL_MIN_SIZE)
+#define AVL_NODES_ON_PAGE		(PAGE_SIZE/sizeof(struct avl_node))
+#define AVL_NODE_PAGES			((AVL_NODE_NUM+AVL_NODES_ON_PAGE-1)/AVL_NODES_ON_PAGE)
+
+struct avl_free_list
+{
+	struct avl_free_list		*next;
+	unsigned int			size;
+	unsigned int			cpu;
+};
+
+static avl_t avl_node_id[NR_CPUS];
+static struct avl_node **avl_node_array[NR_CPUS];
+static struct list_head *avl_container_array[NR_CPUS];
+static struct avl_node *avl_root[NR_CPUS];
+static struct avl_free_list *avl_free_list_head[NR_CPUS];
+static spinlock_t avl_free_lock[NR_CPUS];
+
+static inline struct avl_node *avl_get_node(avl_t id, int cpu)
+{
+	avl_t idx, off;
+
+	if (id >= AVL_NODE_NUM)
+		return NULL;
+	
+	idx = id/AVL_NODES_ON_PAGE;
+	off = id%AVL_NODES_ON_PAGE;
+
+	return &(avl_node_array[cpu][idx][off]);
+}
+
+static inline struct avl_node *avl_get_node_ptr(unsigned long ptr)
+{
+	struct page *page = virt_to_page(ptr);
+	struct avl_node *node = (struct avl_node *)(page->lru.next);
+
+	return node;
+}
+
+static inline void avl_set_node_ptr(unsigned long ptr, struct avl_node *node, int order)
+{
+	int nr_pages = 1<<order, i;
+	struct page *page = virt_to_page(ptr);
+	
+	for (i=0; i<nr_pages; ++i) {
+		page->lru.next = (void *)node;
+		page++;
+	}
+}
+
+static inline int avl_get_cpu_ptr(unsigned long ptr)
+{
+	struct page *page = virt_to_page(ptr);
+	int cpu = (int)(unsigned long)(page->lru.prev);
+
+	return cpu;
+}
+
+static inline void avl_set_cpu_ptr(unsigned long ptr, int cpu, int order)
+{
+	int nr_pages = 1<<order, i;
+	struct page *page = virt_to_page(ptr);
+			
+	for (i=0; i<nr_pages; ++i) {
+		page->lru.prev = (void *)(unsigned long)cpu;
+		page++;
+	}
+}
+
+static inline enum avl_balance avl_compare(struct avl_node *a, struct avl_node *b)
+{
+	if (a->value == b->value)
+		return AVL_BALANCED;
+	else if (a->value > b->value)
+		return AVL_RIGHT;
+	else
+		return AVL_LEFT;
+}
+
+static inline void avl_set_left(struct avl_node *node, avl_t val)
+{
+	node->left = val;
+}
+
+static inline void avl_set_right(struct avl_node *node, avl_t val)
+{
+	node->right = val;
+}
+
+static inline void avl_set_parent(struct avl_node *node, avl_t val)
+{
+	node->parent = val;
+}
+
+static inline void avl_rotate_complete(struct avl_node *parent, struct avl_node *node, int cpu)
+{
+	avl_set_parent(node, parent->parent);
+	if (parent->parent != AVL_NODE_EMPTY) {
+		if (parent->pos == AVL_RIGHT)
+			avl_set_right(avl_get_node(parent->parent, cpu), node->id);
+		else
+			avl_set_left(avl_get_node(parent->parent, cpu), node->id);
+	}
+	avl_set_parent(parent, node->id);
+}
+
+static inline void avl_ll(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *left = avl_get_node(node->left, cpu);
+	
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_left(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_LEFT;
+	if (!left) {
+		avl_set_right(parent, AVL_NODE_EMPTY);
+	} else {
+		avl_set_parent(left, parent->id);
+		left->pos = AVL_RIGHT;
+		avl_set_right(parent, left->id);
+	}
+}
+
+static inline void avl_rr(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *right = avl_get_node(node->right, cpu);
+
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_right(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_RIGHT;
+	if (!right)
+		avl_set_left(parent, AVL_NODE_EMPTY);
+	else {
+		avl_set_parent(right, parent->id);
+		right->pos = AVL_LEFT;
+		avl_set_left(parent, right->id);
+	}
+}
+
+static inline void avl_rl_balance(struct avl_node *node, int cpu)
+{
+	avl_rr(node, cpu);
+	avl_ll(node, cpu);
+}
+
+static inline void avl_lr_balance(struct avl_node *node, int cpu)
+{
+	avl_ll(node, cpu);
+	avl_rr(node, cpu);
+}
+
+static inline void avl_balance_single(struct avl_node *node, struct avl_node *parent)
+{
+	node->balance = parent->balance = AVL_BALANCED;
+}
+
+static inline void avl_ll_balance(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+
+	avl_ll(node, cpu);
+	avl_balance_single(node, parent);
+}
+
+static inline void avl_rr_balance(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+
+	avl_rr(node, cpu);
+	avl_balance_single(node, parent);
+}
+
+static void avl_calc_balance_insert(struct avl_node *a, struct avl_node *b, struct avl_node *x, int cpu)
+{
+	int ao;
+
+	if (!a || !b || !x)
+		goto out;
+
+	ao = (a->balance == avl_compare(x, a));
+
+	if (ao) {
+		if (a->balance == AVL_LEFT) {
+			if (b->balance == AVL_LEFT) {
+				avl_rr_balance(b, cpu);
+			} else if (b->balance == AVL_RIGHT) {
+				avl_lr_balance(x, cpu);
+				switch (x->balance) {
+					case AVL_LEFT:
+						a->balance = AVL_RIGHT;
+						b->balance = AVL_BALANCED;
+						break;
+					case AVL_RIGHT:
+						a->balance = AVL_BALANCED;
+						b->balance = AVL_LEFT;
+						break;
+					case AVL_BALANCED:
+						a->balance = b->balance = AVL_BALANCED;
+						break;
+				}
+				x->balance = AVL_BALANCED;
+			}
+		} else if (a->balance == AVL_RIGHT){
+			if (b->balance == AVL_RIGHT) {
+				avl_ll_balance(b, cpu);
+			} else if (b->balance == AVL_LEFT) {
+				avl_rl_balance(x, cpu);
+				switch (x->balance) {
+					case AVL_LEFT:
+						a->balance = AVL_BALANCED;
+						b->balance = AVL_RIGHT;
+						break;
+					case AVL_RIGHT:
+						a->balance = AVL_LEFT;
+						b->balance = AVL_BALANCED;
+						break;
+					case AVL_BALANCED:
+						a->balance = b->balance = AVL_BALANCED;
+						break;
+				}
+				x->balance = AVL_BALANCED;
+			}
+		}
+	}
+out:
+	return;
+}
+
+static void avl_combine_nodes(struct avl_node *root, struct avl_node *node)
+{
+}
+
+static struct avl_node *__avl_set_balance(struct avl_node *node, enum avl_balance type)
+{
+	if (node->balance == AVL_BALANCED)
+		node->balance = type;
+	else if (node->balance != type)
+		node->balance = AVL_BALANCED;
+	else
+		return node;
+
+	return NULL;
+}
+
+static struct avl_node *avl_set_balance(struct avl_node *node, enum avl_balance type, int cpu)
+{
+	struct avl_node *root = avl_root[cpu];
+
+	if (__avl_set_balance(node, type))
+		return node;
+		
+	if (node->balance == AVL_BALANCED)
+		return NULL;
+
+	type = node->pos;
+	while ((node = avl_get_node(node->parent, cpu)) && node != root) {
+		if (__avl_set_balance(node, type))
+			break;
+		if (node->balance == AVL_BALANCED) {
+			node = NULL;
+			break;
+		}
+		type = node->pos;
+	}
+
+	if (node == root)
+		node = NULL;
+
+	return node;
+}
+
+static struct avl_node *avl_try_insert(struct avl_node *r, struct avl_node *root, 
+		struct avl_node *node, enum avl_balance type, int cpu)
+{
+	struct avl_node *s = NULL, *c = NULL, *R;
+	enum avl_balance t;
+
+	if (type == AVL_BALANCED) {
+		avl_combine_nodes(root, node);
+		return NULL;
+	}
+
+	if (type == AVL_RIGHT && root->right != AVL_NODE_EMPTY)
+		return avl_get_node(root->right, cpu);
+	if (type == AVL_LEFT && root->left != AVL_NODE_EMPTY)
+		return avl_get_node(root->left, cpu);
+
+	R = avl_set_balance(root, type, cpu);
+	if (type == AVL_RIGHT)
+		avl_set_right(root, node->id);
+	else
+		avl_set_left(root, node->id);
+	avl_set_parent(node, root->id);
+	node->pos = type;
+
+	if (!R)
+		return NULL;
+
+	t = avl_compare(node, r);
+	if (t == AVL_RIGHT)
+		s = avl_get_node(r->right, cpu);
+	else if (t == AVL_LEFT)
+		s = avl_get_node(r->left, cpu);
+
+	if (s) {
+		t = avl_compare(node, s);
+
+		if (t == AVL_RIGHT)
+			c = avl_get_node(s->right, cpu);
+		else if (t == AVL_LEFT)
+			c = avl_get_node(s->left, cpu);
+	}
+
+	avl_calc_balance_insert(r, s, c, cpu);
+
+	return NULL;
+}
+
+static void avl_insert(struct avl_node *root, struct avl_node *node, int cpu)
+{
+	struct avl_node *r, *s;
+
+	r = s = root;
+
+	while (root) {
+		enum avl_balance type = avl_compare(node, root);
+
+		s = avl_try_insert(r, root, node, type, cpu);
+
+		if (!s)
+			break;
+		if (type != AVL_BALANCED && root->balance == type)
+			r = root;
+		root = s;
+	}
+}
+
+static struct avl_node *avl_node_alloc(value_t value, int cpu)
+{
+	struct avl_node *node = avl_get_node(avl_node_id[cpu], cpu);
+
+	if (!node) {
+		avl_t idx, off;
+
+		idx = avl_node_id[cpu]/AVL_NODES_ON_PAGE;
+		off = avl_node_id[cpu]%AVL_NODES_ON_PAGE;
+		printk("%s: value: %lx, id: %u, max: %lu, cpu: %d, idx: %u, off: %u, on_page: %lu, node: %zu, pages: %lu.\n", 
+				__func__, value, avl_node_id[cpu], AVL_NODE_NUM, cpu, idx, off, 
+				AVL_NODES_ON_PAGE, sizeof(struct avl_node), AVL_NODE_PAGES);
+	}
+	BUG_ON(!node);
+
+	node->value = value;
+	node->balance = AVL_BALANCED;
+	node->left = node->right = node->parent = AVL_NODE_EMPTY;
+	node->id = avl_node_id[cpu]++;
+	memset(node->mask, 0xff, sizeof(node->mask));
+
+	return node;
+}
+
+static struct avl_node *avl_search(value_t value, int cpu)
+{
+	struct avl_node *node = avl_root[cpu];
+
+	while (node) {
+		if (value < node->value)
+			node = avl_get_node(node->left, cpu);
+		else if (value > node->value)
+			node = avl_get_node(node->right, cpu);
+		else
+			break;
+	}
+
+	return node;
+}
+
+static struct avl_node *avl_node_search_alloc(value_t value, int cpu)
+{
+	struct avl_node *node;
+
+	node = avl_search(value, cpu);
+	if (!node) {
+		node = avl_node_alloc(value, cpu);
+		if (node) {
+			avl_set_cpu_ptr(value, cpu, AVL_ORDER);
+			avl_set_node_ptr(value, node, AVL_ORDER);
+			avl_insert(avl_get_node(avl_root[cpu]->right, cpu), node, cpu);
+		}
+	}
+
+	return node;
+}
+
+static inline value_t avl_ptr_to_value(void *ptr)
+{
+	struct avl_node *node = avl_get_node_ptr((unsigned long)ptr);
+	return node->value;
+}
+
+static inline int avl_ptr_to_offset(void *ptr)
+{
+	return ((value_t)ptr - avl_ptr_to_value(ptr))/AVL_MIN_SIZE;
+}
+
+unsigned int avl_count_set_down(unsigned long *mask, unsigned int pos)
+{
+	unsigned int stop, bits = 0;
+	int idx;
+	unsigned long p, m;
+
+	idx = pos/BITS_PER_LONG;
+	pos = pos%BITS_PER_LONG;
+
+	while (idx >= 0) {
+		m = (~0UL>>pos)<<pos;
+		p = mask[idx] | m;
+
+		if (!(mask[idx] & m))
+			break;
+
+		stop = fls(~p);
+
+		if (!stop) {
+			bits += pos + 1;
+			pos = BITS_PER_LONG - 1;
+			idx--;
+		} else {
+			bits += pos - stop + 1;
+			break;
+		}
+	}
+
+	return bits;
+}
+
+unsigned int avl_count_set_up(unsigned long *mask, unsigned int mask_num, 
+		unsigned int pos)
+{
+	unsigned int idx, stop, bits = 0;
+	unsigned long p, m;
+
+	idx = pos/BITS_PER_LONG;
+	pos = pos%BITS_PER_LONG;
+
+	while (idx < mask_num) {
+		if (!pos)
+			m = 0;
+		else
+			m = (~0UL<<(BITS_PER_LONG-pos))>>(BITS_PER_LONG-pos);
+		p = mask[idx] | m;
+
+		if (!(mask[idx] & ~m))
+			break;
+
+		stop = ffs(~p);
+
+		if (!stop) {
+			bits += BITS_PER_LONG - pos;
+			pos = 0;
+			idx++;
+		} else {
+			bits += stop - pos - 1;
+			break;
+		}