From owner-svn-src-projects@FreeBSD.ORG Thu Jul 15 01:13:50 2010 Return-Path: Delivered-To: svn-src-projects@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 01F33106564A; Thu, 15 Jul 2010 01:13:50 +0000 (UTC) (envelope-from jeff@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id E485F8FC17; Thu, 15 Jul 2010 01:13:49 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id o6F1DnIl035317; Thu, 15 Jul 2010 01:13:49 GMT (envelope-from jeff@svn.freebsd.org) Received: (from jeff@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o6F1Dnkp035314; Thu, 15 Jul 2010 01:13:49 GMT (envelope-from jeff@svn.freebsd.org) Message-Id: <201007150113.o6F1Dnkp035314@svn.freebsd.org> From: Jeff Roberson Date: Thu, 15 Jul 2010 01:13:49 +0000 (UTC) To: src-committers@freebsd.org, svn-src-projects@freebsd.org X-SVN-Group: projects MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r210090 - projects/ofed/head/sys/ofed/include/linux X-BeenThere: svn-src-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the src " projects" tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Jul 2010 01:13:50 -0000 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 +#include +#include +#include +#include + +#include +#include +#include +#include + +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);