From owner-svn-src-all@freebsd.org Wed Aug 19 12:25:35 2020 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 5FD283BCF6E; Wed, 19 Aug 2020 12:25:35 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4BWn731v2zz3Syf; Wed, 19 Aug 2020 12:25:35 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 1FEE922D51; Wed, 19 Aug 2020 12:25:35 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 07JCPYSP021418; Wed, 19 Aug 2020 12:25:34 GMT (envelope-from hselasky@FreeBSD.org) Received: (from hselasky@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 07JCPYR6021416; Wed, 19 Aug 2020 12:25:34 GMT (envelope-from hselasky@FreeBSD.org) Message-Id: <202008191225.07JCPYR6021416@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: hselasky set sender to hselasky@FreeBSD.org using -f From: Hans Petter Selasky Date: Wed, 19 Aug 2020 12:25:34 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-12@freebsd.org Subject: svn commit: r364382 - in stable/12/sys/compat/linuxkpi/common: include/linux src X-SVN-Group: stable-12 X-SVN-Commit-Author: hselasky X-SVN-Commit-Paths: in stable/12/sys/compat/linuxkpi/common: include/linux src X-SVN-Commit-Revision: 364382 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 19 Aug 2020 12:25:35 -0000 Author: hselasky Date: Wed Aug 19 12:25:34 2020 New Revision: 364382 URL: https://svnweb.freebsd.org/changeset/base/364382 Log: MFC r364028: Implement radix_tree_store() in the LinuxKPI for use with the coming extensible arrays implementation. While at it add some more comments explaining the current radix_tree_insert() function and make sure to clean the root node when the radix tree reaches the maximum height. This can happen if the index passed is too big when the tree is empty. The radix_tree_store() function is basically a copy of the radix_tree_insert() function with some added functionality. The radix_tree_store() function is local to FreeBSD and does not yet exist in Linux. Reviewed by: kib Sponsored by: Mellanox Technologies Modified: stable/12/sys/compat/linuxkpi/common/include/linux/radix-tree.h stable/12/sys/compat/linuxkpi/common/src/linux_radix.c Directory Properties: stable/12/ (props changed) Modified: stable/12/sys/compat/linuxkpi/common/include/linux/radix-tree.h ============================================================================== --- stable/12/sys/compat/linuxkpi/common/include/linux/radix-tree.h Wed Aug 19 12:23:05 2020 (r364381) +++ stable/12/sys/compat/linuxkpi/common/include/linux/radix-tree.h Wed Aug 19 12:25:34 2020 (r364382) @@ -78,6 +78,7 @@ radix_tree_exception(void *arg) 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 *); +int radix_tree_store(struct radix_tree_root *, unsigned long, void **); bool radix_tree_iter_find(struct radix_tree_root *, struct radix_tree_iter *, void ***); void radix_tree_iter_delete(struct radix_tree_root *, struct radix_tree_iter *, void **); Modified: stable/12/sys/compat/linuxkpi/common/src/linux_radix.c ============================================================================== --- stable/12/sys/compat/linuxkpi/common/src/linux_radix.c Wed Aug 19 12:23:05 2020 (r364381) +++ stable/12/sys/compat/linuxkpi/common/src/linux_radix.c Wed Aug 19 12:25:34 2020 (r364382) @@ -2,7 +2,7 @@ * Copyright (c) 2010 Isilon Systems, Inc. * Copyright (c) 2010 iX Systems, Inc. * Copyright (c) 2010 Panasas, Inc. - * Copyright (c) 2013-2018 Mellanox Technologies, Ltd. + * Copyright (c) 2013-2020 Mellanox Technologies, Ltd. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -55,6 +55,17 @@ radix_pos(long id, int height) return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK; } +static void +radix_tree_clean_root_node(struct radix_tree_root *root) +{ + /* Check if the root node should be freed */ + if (root->rnode->count == 0) { + free(root->rnode, M_RADIX); + root->rnode = NULL; + root->height = 0; + } +} + void * radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { @@ -197,8 +208,10 @@ radix_tree_insert(struct radix_tree_root *root, unsign while (radix_max(root) < index) { /* check if the radix tree is getting too big */ - if (root->height == RADIX_TREE_MAX_HEIGHT) + if (root->height == RADIX_TREE_MAX_HEIGHT) { + radix_tree_clean_root_node(root); return (-E2BIG); + } /* * If the root radix level is not empty, we need to @@ -206,8 +219,16 @@ radix_tree_insert(struct radix_tree_root *root, unsign */ if (node->count != 0) { node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); - if (node == NULL) + if (node == NULL) { + /* + * Freeing the already allocated radix + * levels, if any, will be handled by + * the radix_tree_delete() function. + * This code path can only happen when + * the tree is not empty. + */ return (-ENOMEM); + } node->slots[0] = root->rnode; node->count++; root->rnode = node; @@ -231,14 +252,9 @@ radix_tree_insert(struct radix_tree_root *root, unsign temp[idx] = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); if (temp[idx] == NULL) { - while(idx--) + while (idx--) free(temp[idx], M_RADIX); - /* Check if we should free the root node as well. */ - if (root->rnode->count == 0) { - free(root->rnode, M_RADIX); - root->rnode = NULL; - root->height = 0; - } + radix_tree_clean_root_node(root); return (-ENOMEM); } } @@ -260,5 +276,112 @@ radix_tree_insert(struct radix_tree_root *root, unsign node->slots[idx] = item; node->count++; + return (0); +} + +int +radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem) +{ + struct radix_tree_node *node; + struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; + void *pitem; + int height; + int idx; + + /* + * Inserting a NULL item means delete it. The old pointer is + * stored at the location pointed to by "ppitem". + */ + if (*ppitem == NULL) { + *ppitem = radix_tree_delete(root, index); + return (0); + } + + /* get root node, if any */ + node = root->rnode; + + /* allocate root node, if any */ + if (node == NULL) { + node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); + if (node == NULL) + return (-ENOMEM); + root->rnode = node; + root->height++; + } + + /* expand radix tree as needed */ + while (radix_max(root) < index) { + + /* check if the radix tree is getting too big */ + if (root->height == RADIX_TREE_MAX_HEIGHT) { + radix_tree_clean_root_node(root); + return (-E2BIG); + } + + /* + * If the root radix level is not empty, we need to + * allocate a new radix level: + */ + if (node->count != 0) { + node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); + if (node == NULL) { + /* + * Freeing the already allocated radix + * levels, if any, will be handled by + * the radix_tree_delete() function. + * This code path can only happen when + * the tree is not empty. + */ + return (-ENOMEM); + } + node->slots[0] = root->rnode; + node->count++; + root->rnode = node; + } + root->height++; + } + + /* get radix tree height index */ + height = root->height - 1; + + /* walk down the tree until the first missing node, if any */ + for ( ; height != 0; height--) { + idx = radix_pos(index, height); + if (node->slots[idx] == NULL) + break; + node = node->slots[idx]; + } + + /* allocate the missing radix levels, if any */ + for (idx = 0; idx != height; idx++) { + temp[idx] = malloc(sizeof(*node), M_RADIX, + root->gfp_mask | M_ZERO); + if (temp[idx] == NULL) { + while (idx--) + free(temp[idx], M_RADIX); + radix_tree_clean_root_node(root); + return (-ENOMEM); + } + } + + /* setup new radix levels, if any */ + for ( ; height != 0; height--) { + idx = radix_pos(index, height); + node->slots[idx] = temp[height - 1]; + node->count++; + node = node->slots[idx]; + } + + /* + * Insert and adjust count if the item does not already exist. + */ + idx = radix_pos(index, 0); + /* swap */ + pitem = node->slots[idx]; + node->slots[idx] = *ppitem; + *ppitem = pitem; + + if (pitem == NULL) + node->count++; return (0); }