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 *
vm_radix_node_alloc(struct pctrie * ptree)74 vm_radix_node_alloc(struct pctrie *ptree)
75 {
76 return (uma_zalloc_smr(vm_radix_node_zone, M_NOWAIT));
77 }
78
79 void
vm_radix_node_free(struct pctrie * ptree,void * node)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
vm_radix_reserve_kva(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
vm_radix_zinit(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
vm_radix_wait(void)123 vm_radix_wait(void)
124 {
125 uma_zwait(vm_radix_node_zone);
126 }
127