1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2013 EMC Corp. 5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 * 30 */ 31 32 /* 33 * Path-compressed radix trie implementation. 34 * The following code is not generalized into a general purpose library 35 * because there are way too many parameters embedded that should really 36 * be decided by the library consumers. At the same time, consumers 37 * of this code must achieve highest possible performance. 38 * 39 * The implementation takes into account the following rationale: 40 * - Size of the nodes should be as small as possible but still big enough 41 * to avoid a large maximum depth for the trie. This is a balance 42 * between the necessity to not wire too much physical memory for the nodes 43 * and the necessity to avoid too much cache pollution during the trie 44 * operations. 45 * - There is not a huge bias toward the number of lookup operations over 46 * the number of insert and remove operations. This basically implies 47 * that optimizations supposedly helping one operation but hurting the 48 * other might be carefully evaluated. 49 * - On average not many nodes are expected to be fully populated, hence 50 * level compression may just complicate things. 51 */ 52 53 #include <sys/cdefs.h> 54 #include "opt_ddb.h" 55 56 #include <sys/param.h> 57 #include <sys/systm.h> 58 #include <sys/kernel.h> 59 #include <sys/libkern.h> 60 #include <sys/pctrie.h> 61 #include <sys/proc.h> 62 #include <sys/vmmeter.h> 63 #include <sys/smr.h> 64 #include <sys/smr_types.h> 65 66 #include <vm/uma.h> 67 #include <vm/vm.h> 68 #include <vm/vm_radix.h> 69 70 static uma_zone_t vm_radix_node_zone; 71 smr_t vm_radix_smr; 72 73 void * 74 vm_radix_node_alloc(struct pctrie *ptree) 75 { 76 return (uma_zalloc_smr(vm_radix_node_zone, M_NOWAIT)); 77 } 78 79 void 80 vm_radix_node_free(struct pctrie *ptree, void *node) 81 { 82 uma_zfree_smr(vm_radix_node_zone, node); 83 } 84 85 #ifndef UMA_MD_SMALL_ALLOC 86 void vm_radix_reserve_kva(void); 87 /* 88 * Reserve the KVA necessary to satisfy the node allocation. 89 * This is mandatory in architectures not supporting direct 90 * mapping as they will need otherwise to carve into the kernel maps for 91 * every node allocation, resulting into deadlocks for consumers already 92 * working with kernel maps. 93 */ 94 void 95 vm_radix_reserve_kva(void) 96 { 97 98 /* 99 * Calculate the number of reserved nodes, discounting the pages that 100 * are needed to store them. 101 */ 102 if (!uma_zone_reserve_kva(vm_radix_node_zone, 103 ((vm_paddr_t)vm_cnt.v_page_count * PAGE_SIZE) / (PAGE_SIZE + 104 pctrie_node_size()))) 105 panic("%s: unable to reserve KVA", __func__); 106 } 107 #endif 108 109 /* 110 * Initialize the UMA slab zone. 111 */ 112 void 113 vm_radix_zinit(void) 114 { 115 116 vm_radix_node_zone = uma_zcreate("RADIX NODE", pctrie_node_size(), 117 NULL, NULL, pctrie_zone_init, NULL, 118 PCTRIE_PAD, UMA_ZONE_VM | UMA_ZONE_SMR); 119 vm_radix_smr = uma_zone_get_smr(vm_radix_node_zone); 120 } 121 122 void 123 vm_radix_wait(void) 124 { 125 uma_zwait(vm_radix_node_zone); 126 } 127