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
70static uma_zone_t vm_radix_node_zone;
71smr_t vm_radix_smr;
72
73void *
74vm_radix_node_alloc(struct pctrie *ptree)
75{
76	return (uma_zalloc_smr(vm_radix_node_zone, M_NOWAIT));
77}
78
79void
80vm_radix_node_free(struct pctrie *ptree, void *node)
81{
82	uma_zfree_smr(vm_radix_node_zone, node);
83}
84
85#ifndef UMA_USE_DMAP
86void 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 */
94void
95vm_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 */
112void
113vm_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
122void
123vm_radix_wait(void)
124{
125	uma_zwait(vm_radix_node_zone);
126}
127