Date: Thu, 15 Jul 2010 01:13:49 +0000 (UTC) From: Jeff Roberson <jeff@FreeBSD.org> To: src-committers@freebsd.org, svn-src-projects@freebsd.org Subject: svn commit: r210090 - projects/ofed/head/sys/ofed/include/linux Message-ID: <201007150113.o6F1Dnkp035314@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: jeff Date: Thu Jul 15 01:13:49 2010 New Revision: 210090 URL: http://svn.freebsd.org/changeset/base/210090 Log: - Add a linux compatible radix tree implementation. This only implements a subset of the linux features required by ofed drivers. Sponsored by: Isilon Systems, iX Systems, and Panasas. Added: projects/ofed/head/sys/ofed/include/linux/linux_radix.c Modified: projects/ofed/head/sys/ofed/include/linux/radix-tree.h Added: projects/ofed/head/sys/ofed/include/linux/linux_radix.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ projects/ofed/head/sys/ofed/include/linux/linux_radix.c Thu Jul 15 01:13:49 2010 (r210090) @@ -0,0 +1,170 @@ +/*- + * Copyright (c) 2010 Isilon Systems, Inc. + * Copyright (c) 2010 iX Systems, Inc. + * Copyright (c) 2010 Panasas, Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice unmodified, this list of conditions, and the following + * disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <sys/param.h> +#include <sys/systm.h> +#include <sys/malloc.h> +#include <sys/kernel.h> +#include <sys/sysctl.h> + +#include <linux/slab.h> +#include <linux/kernel.h> +#include <linux/radix-tree.h> +#include <linux/err.h> + +MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); + +static inline int +radix_max(struct radix_tree_root *root) +{ + return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1; +} + +static inline int +radix_pos(long id, int height) +{ + return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK; +} + +void * +radix_tree_lookup(struct radix_tree_root *root, unsigned long index) +{ + struct radix_tree_node *node; + void *item; + int height; + + item = NULL; + node = root->rnode; + height = root->height - 1; + if (index > radix_max(root)) + goto out; + while (height && node) + node = node->slots[radix_pos(index, height--)]; + if (node) + item = node->slots[radix_pos(index, 0)]; + +out: + return (item); +} + +void * +radix_tree_delete(struct radix_tree_root *root, unsigned long index) +{ + struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT]; + struct radix_tree_node *node; + void *item; + int height; + int idx; + + item = NULL; + node = root->rnode; + height = root->height - 1; + if (index > radix_max(root)) + goto out; + /* + * Find the node and record the path in stack. + */ + while (height && node) { + stack[height] = node; + node = node->slots[radix_pos(index, height--)]; + } + idx = radix_pos(index, 0); + if (node) + item = node->slots[idx]; + /* + * If we removed something reduce the height of the tree. + */ + if (item) + for (;;) { + node->slots[idx] = NULL; + node->count--; + if (node->count > 0) + break; + free(node, M_RADIX); + if (node == root->rnode) { + root->rnode = NULL; + root->height = 0; + break; + } + height++; + node = stack[height]; + idx = radix_pos(index, height); + } +out: + return (item); +} + +int +radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) +{ + struct radix_tree_node *node; + int height; + int idx; + + /* + * Expand the tree to fit indexes as big as requested. + */ + while (root->rnode == NULL || radix_max(root) < index) { + node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); + if (node == NULL) + return (-ENOMEM); + node->slots[0] = root->rnode; + if (root->rnode) + node->count++; + root->rnode = node; + root->height++; + } + node = root->rnode; + height = root->height - 1; + /* + * Walk down the tree finding the correct node and allocating any + * missing nodes along the way. + */ + while (height) { + idx = radix_pos(index, height); + if (node->slots[idx] == NULL) { + node->slots[idx] = malloc(sizeof(*node), M_RADIX, + root->gfp_mask | M_ZERO); + if (node->slots[idx] == NULL) + return (-ENOMEM); + node->count++; + } + node = node->slots[idx]; + height--; + } + /* + * Insert and adjust count if the item does not already exist. + */ + idx = radix_pos(index, 0); + if (node->slots[idx]) + return (-EEXIST); + node->slots[idx] = item; + node->count++; + + return (0); +} Modified: projects/ofed/head/sys/ofed/include/linux/radix-tree.h ============================================================================== --- projects/ofed/head/sys/ofed/include/linux/radix-tree.h Thu Jul 15 00:16:04 2010 (r210089) +++ projects/ofed/head/sys/ofed/include/linux/radix-tree.h Thu Jul 15 01:13:49 2010 (r210090) @@ -29,10 +29,29 @@ #ifndef _LINUX_RADIX_TREE_H_ #define _LINUX_RADIX_TREE_H_ +#define RADIX_TREE_MAP_SHIFT 6 +#define RADIX_TREE_MAP_SIZE (1 << RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE - 1) +#define RADIX_TREE_MAX_HEIGHT \ + DIV_ROUND_UP((sizeof(long) * NBBY), RADIX_TREE_MAP_SHIFT) + +struct radix_tree_node { + void *slots[RADIX_TREE_MAP_SIZE]; + int count; +}; + struct radix_tree_root { + struct radix_tree_node *rnode; + gfp_t gfp_mask; + int height; }; -#define RADIX_TREE_INIT(root) +#define RADIX_TREE_INIT(mask) \ + { .rnode = NULL, .gfp_mask = mask, .height = 0 }; +#define INIT_RADIX_TREE(root, mask) \ + { (root)->rnode = NULL; (root)->gfp_mask = mask; (root)->height = 0; } +#define RADIX_TREE(name, mask) \ + struct radix_tree_root name = RADIX_TREE_INIT(mask) void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void *radix_tree_delete(struct radix_tree_root *, unsigned long);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201007150113.o6F1Dnkp035314>