Date: Sun, 18 Feb 2018 12:54:22 +0000 (UTC) From: Hans Petter Selasky <hselasky@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r329519 - in head/sys/compat/linuxkpi/common: include/linux src Message-ID: <201802181254.w1ICsMvE038895@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: hselasky Date: Sun Feb 18 12:54:21 2018 New Revision: 329519 URL: https://svnweb.freebsd.org/changeset/base/329519 Log: Implement support for radix_tree_for_each_slot() and radix_tree_exception() in the LinuxKPI and use unsigned long type for the radix tree index. MFC after: 1 week Sponsored by: Mellanox Technologies Modified: head/sys/compat/linuxkpi/common/include/linux/radix-tree.h head/sys/compat/linuxkpi/common/src/linux_radix.c Modified: head/sys/compat/linuxkpi/common/include/linux/radix-tree.h ============================================================================== --- head/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 18 11:36:46 2018 (r329518) +++ head/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 18 12:54:21 2018 (r329519) @@ -2,7 +2,7 @@ * Copyright (c) 2010 Isilon Systems, Inc. * Copyright (c) 2010 iX Systems, Inc. * Copyright (c) 2010 Panasas, Inc. - * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. + * Copyright (c) 2013-2018 Mellanox Technologies, Ltd. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -34,11 +34,15 @@ #include <linux/types.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) +#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE - 1UL) +#define RADIX_TREE_MAX_HEIGHT \ + howmany(sizeof(long) * NBBY, RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_ENTRY_MASK 3UL +#define RADIX_TREE_EXCEPTIONAL_ENTRY 2UL +#define RADIX_TREE_EXCEPTIONAL_SHIFT 2 + struct radix_tree_node { void *slots[RADIX_TREE_MAP_SIZE]; int count; @@ -50,6 +54,10 @@ struct radix_tree_root { int height; }; +struct radix_tree_iter { + unsigned long index; +}; + #define RADIX_TREE_INIT(mask) \ { .rnode = NULL, .gfp_mask = mask, .height = 0 }; #define INIT_RADIX_TREE(root, mask) \ @@ -57,8 +65,19 @@ struct radix_tree_root { #define RADIX_TREE(name, mask) \ struct radix_tree_root name = RADIX_TREE_INIT(mask) +#define radix_tree_for_each_slot(slot, root, iter, start) \ + for ((iter)->index = (start); \ + radix_tree_iter_find(root, iter, &(slot)); (iter)->index++) + +static inline int +radix_tree_exception(void *arg) +{ + return ((uintptr_t)arg & RADIX_TREE_ENTRY_MASK); +} + void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void *radix_tree_delete(struct radix_tree_root *, unsigned long); int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); +bool radix_tree_iter_find(struct radix_tree_root *, struct radix_tree_iter *, void ***); #endif /* _LINUX_RADIX_TREE_H_ */ Modified: head/sys/compat/linuxkpi/common/src/linux_radix.c ============================================================================== --- head/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 18 11:36:46 2018 (r329518) +++ head/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 18 12:54:21 2018 (r329519) @@ -2,7 +2,7 @@ * Copyright (c) 2010 Isilon Systems, Inc. * Copyright (c) 2010 iX Systems, Inc. * Copyright (c) 2010 Panasas, Inc. - * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. + * Copyright (c) 2013-2018 Mellanox Technologies, Ltd. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -43,10 +43,10 @@ __FBSDID("$FreeBSD$"); static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); -static inline int +static inline unsigned long radix_max(struct radix_tree_root *root) { - return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1; + return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL); } static inline int @@ -74,6 +74,44 @@ radix_tree_lookup(struct radix_tree_root *root, unsign out: return (item); +} + +bool +radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter, + void ***pppslot) +{ + struct radix_tree_node *node; + unsigned long index = iter->index; + int height; + +restart: + node = root->rnode; + if (node == NULL) + return (false); + height = root->height - 1; + if (height == -1 || index > radix_max(root)) + return (false); + do { + unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height); + unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height); + int pos = radix_pos(index, height); + struct radix_tree_node *next; + + /* track last slot */ + *pppslot = node->slots + pos; + + next = node->slots[pos]; + if (next == NULL) { + index += step; + if ((index & mask) == 0) + goto restart; + } else { + node = next; + height--; + } + } while (height != -1); + iter->index = index; + return (true); } void *
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201802181254.w1ICsMvE038895>