/* $NetBSD: linux_idr.c,v 1.15 2021/12/19 12:21:02 riastradh Exp $ */ /*- * Copyright (c) 2013 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Taylor R. Campbell. * * 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, 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 NETBSD FOUNDATION, INC. AND CONTRIBUTORS * ``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 FOUNDATION OR CONTRIBUTORS * 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 __KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.15 2021/12/19 12:21:02 riastradh Exp $"); #include #include #include #include #include #include #include #ifdef _KERNEL_OPT #include "opt_ddb.h" #endif #ifdef DDB #include #endif struct idr_node { rb_node_t in_rb_node; int in_index; void *in_data; }; struct idr_cache { struct idr_node *ic_node; void *ic_where; }; SDT_PROBE_DEFINE0(sdt, linux, idr, leak); SDT_PROBE_DEFINE1(sdt, linux, idr, init, "struct idr *"/*idr*/); SDT_PROBE_DEFINE1(sdt, linux, idr, destroy, "struct idr *"/*idr*/); SDT_PROBE_DEFINE4(sdt, linux, idr, replace, "struct idr *"/*idr*/, "int"/*id*/, "void *"/*odata*/, "void *"/*ndata*/); SDT_PROBE_DEFINE3(sdt, linux, idr, remove, "struct idr *"/*idr*/, "int"/*id*/, "void *"/*data*/); SDT_PROBE_DEFINE0(sdt, linux, idr, preload); SDT_PROBE_DEFINE0(sdt, linux, idr, preload__end); SDT_PROBE_DEFINE3(sdt, linux, idr, alloc, "struct idr *"/*idr*/, "int"/*id*/, "void *"/*data*/); static specificdata_key_t idr_cache_key __read_mostly; static void idr_cache_warning(struct idr_cache *cache) { #ifdef DDB const char *name; db_expr_t offset; #endif KASSERT(cache->ic_node != NULL); #ifdef DDB db_find_sym_and_offset((db_addr_t)(uintptr_t)cache->ic_where, &name, &offset); if (name) { printf("WARNING: idr preload at %s+%#"DDB_EXPR_FMT"x" " leaked in lwp %s @ %p\n", name, offset, curlwp->l_name, curlwp); } else #endif { printf("WARNING: idr preload at %p leaked in lwp %s @ %p\n", cache->ic_where, curlwp->l_name, curlwp); } } static void idr_cache_dtor(void *cookie) { struct idr_cache *cache = cookie; if (cache->ic_node) { SDT_PROBE0(sdt, linux, idr, leak); idr_cache_warning(cache); kmem_free(cache->ic_node, sizeof(*cache->ic_node)); } kmem_free(cache, sizeof(*cache)); } int linux_idr_module_init(void) { int error; error = lwp_specific_key_create(&idr_cache_key, &idr_cache_dtor); if (error) return error; return 0; } void linux_idr_module_fini(void) { lwp_specific_key_delete(idr_cache_key); } static signed int idr_tree_compare_nodes(void *, const void *, const void *); static signed int idr_tree_compare_key(void *, const void *, const void *); static const rb_tree_ops_t idr_rb_ops = { .rbto_compare_nodes = &idr_tree_compare_nodes, .rbto_compare_key = &idr_tree_compare_key, .rbto_node_offset = offsetof(struct idr_node, in_rb_node), .rbto_context = NULL, }; static signed int idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb) { const int a = ((const struct idr_node *)na)->in_index; const int b = ((const struct idr_node *)nb)->in_index; if (a < b) return -1; else if (b < a) return +1; else return 0; } static signed int idr_tree_compare_key(void *ctx __unused, const void *n, const void *key) { const int a = ((const struct idr_node *)n)->in_index; const int b = *(const int *)key; if (a < b) return -1; else if (b < a) return +1; else return 0; } void idr_init(struct idr *idr) { idr_init_base(idr, 0); } void idr_init_base(struct idr *idr, int base) { mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM); rb_tree_init(&idr->idr_tree, &idr_rb_ops); idr->idr_base = base; SDT_PROBE1(sdt, linux, idr, init, idr); } void idr_destroy(struct idr *idr) { SDT_PROBE1(sdt, linux, idr, destroy, idr); #if 0 /* XXX No rb_tree_destroy? */ rb_tree_destroy(&idr->idr_tree); #endif mutex_destroy(&idr->idr_lock); } bool idr_is_empty(struct idr *idr) { return (RB_TREE_MIN(&idr->idr_tree) == NULL); } void * idr_find(struct idr *idr, int id) { const struct idr_node *node; void *data; mutex_spin_enter(&idr->idr_lock); node = rb_tree_find_node(&idr->idr_tree, &id); data = (node == NULL? NULL : node->in_data); mutex_spin_exit(&idr->idr_lock); return data; } void * idr_get_next(struct idr *idr, int *idp) { const struct idr_node *node; void *data; mutex_spin_enter(&idr->idr_lock); node = rb_tree_find_node_geq(&idr->idr_tree, idp); if (node == NULL) { data = NULL; } else { data = node->in_data; *idp = node->in_index; } mutex_spin_exit(&idr->idr_lock); return data; } void * idr_replace(struct idr *idr, void *replacement, int id) { struct idr_node *node; void *result; mutex_spin_enter(&idr->idr_lock); node = rb_tree_find_node(&idr->idr_tree, &id); if (node == NULL) { result = ERR_PTR(-ENOENT); } else { result = node->in_data; node->in_data = replacement; SDT_PROBE4(sdt, linux, idr, replace, idr, id, result, replacement); } mutex_spin_exit(&idr->idr_lock); return result; } void * idr_remove(struct idr *idr, int id) { struct idr_node *node; void *data; mutex_spin_enter(&idr->idr_lock); node = rb_tree_find_node(&idr->idr_tree, &id); if (node == NULL) { data = NULL; } else { data = node->in_data; SDT_PROBE3(sdt, linux, idr, remove, idr, id, data); rb_tree_remove_node(&idr->idr_tree, node); } mutex_spin_exit(&idr->idr_lock); kmem_free(node, sizeof(*node)); return data; } void idr_preload(gfp_t gfp) { struct idr_cache *cache; struct idr_node *node; km_flag_t kmflag = ISSET(gfp, __GFP_WAIT) ? KM_SLEEP : KM_NOSLEEP; SDT_PROBE0(sdt, linux, idr, preload); /* If caller asked to wait, we had better be sleepable. */ if (ISSET(gfp, __GFP_WAIT)) ASSERT_SLEEPABLE(); /* * Get the current lwp's private idr cache. */ cache = lwp_getspecific(idr_cache_key); if (cache == NULL) { /* lwp_setspecific must be sleepable. */ if (!ISSET(gfp, __GFP_WAIT)) return; cache = kmem_zalloc(sizeof(*cache), kmflag); if (cache == NULL) return; lwp_setspecific(idr_cache_key, cache); } /* * If there already is a node, a prior call to idr_preload must * not have been matched by idr_preload_end. Print a warning, * claim the node, and record our return address for where this * node came from so the next leak is attributed to us. */ if (cache->ic_node) { idr_cache_warning(cache); goto out; } /* * No cached node. Allocate a new one, store it in the cache, * and record our return address for where this node came from * so the next leak is attributed to us. */ node = kmem_alloc(sizeof(*node), kmflag); KASSERT(node != NULL || !ISSET(gfp, __GFP_WAIT)); if (node == NULL) return; cache->ic_node = node; out: cache->ic_where = __builtin_return_address(0); } int idr_alloc(struct idr *idr, void *data, int start, int end, gfp_t gfp) { int maximum = (end <= 0? INT_MAX : (end - 1)); struct idr_cache *cache; struct idr_node *node, *search, *collision __diagused; int id = start; /* Sanity-check inputs. */ if (ISSET(gfp, __GFP_WAIT)) ASSERT_SLEEPABLE(); if (__predict_false(start < 0)) return -EINVAL; if (__predict_false(maximum < start)) return -ENOSPC; /* * Grab a node allocated by idr_preload, if we have a cache and * it is populated. */ cache = lwp_getspecific(idr_cache_key); if (cache == NULL || cache->ic_node == NULL) return -ENOMEM; node = cache->ic_node; cache->ic_node = NULL; /* Find an id. */ mutex_spin_enter(&idr->idr_lock); search = rb_tree_find_node_geq(&idr->idr_tree, &start); while ((search != NULL) && (search->in_index == id)) { if (maximum <= id) { id = -ENOSPC; goto out; } search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT); id++; } node->in_index = id; node->in_data = data; collision = rb_tree_insert_node(&idr->idr_tree, node); KASSERT(collision == node); out: mutex_spin_exit(&idr->idr_lock); /* Discard the node on failure. */ if (id < 0) { cache->ic_node = node; } else { SDT_PROBE3(sdt, linux, idr, alloc, idr, id, data); } return id; } void idr_preload_end(void) { struct idr_cache *cache; SDT_PROBE0(sdt, linux, idr, preload__end); /* Get the cache, or bail if it's not there. */ cache = lwp_getspecific(idr_cache_key); if (cache == NULL) return; /* * If there is a node, either because we didn't idr_alloc or * because idr_alloc failed, chuck it. * * XXX If we are not sleepable, then while the caller may have * used idr_preload(GFP_ATOMIC), kmem_free may still sleep. * What to do? */ if (cache->ic_node) { struct idr_node *node; node = cache->ic_node; cache->ic_node = NULL; cache->ic_where = NULL; kmem_free(node, sizeof(*node)); } } int idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg) { struct idr_node *node; int error = 0; /* XXX Caller must exclude modifications. */ RB_TREE_FOREACH(node, &idr->idr_tree) { error = (*proc)(node->in_index, node->in_data, arg); if (error) break; } return error; }