Deleted Added
sdiff udiff text old ( 247233 ) new ( 247742 )
full compact
vm_radix.c (247233) vm_radix.c (247742)
1/*
2 * Copyright (c) 2013 EMC Corp.
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
4 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions

--- 31 unchanged lines hidden (view full) ---

40 * and vice-versa.
41 * - In average there are not many complete levels, than level
42 * compression may just complicate things.
43 */
44
45#include <sys/cdefs.h>
46
47#include "opt_ddb.h"
1/*
2 * Copyright (c) 2013 EMC Corp.
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
4 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions

--- 31 unchanged lines hidden (view full) ---

40 * and vice-versa.
41 * - In average there are not many complete levels, than level
42 * compression may just complicate things.
43 */
44
45#include <sys/cdefs.h>
46
47#include "opt_ddb.h"
48#include "opt_vm.h"
49
50#include <sys/param.h>
51#include <sys/systm.h>
52#include <sys/kernel.h>
53#include <sys/vmmeter.h>
54
55#include <vm/uma.h>
56#include <vm/vm.h>
57#include <vm/vm_param.h>
58#include <vm/vm_page.h>
59#include <vm/vm_radix.h>
60
61#ifdef DDB
62#include <ddb/ddb.h>
63#endif
64
48
49#include <sys/param.h>
50#include <sys/systm.h>
51#include <sys/kernel.h>
52#include <sys/vmmeter.h>
53
54#include <vm/uma.h>
55#include <vm/vm.h>
56#include <vm/vm_param.h>
57#include <vm/vm_page.h>
58#include <vm/vm_radix.h>
59
60#ifdef DDB
61#include <ddb/ddb.h>
62#endif
63
65#ifndef VM_RADIX_BOOT_CACHE
66#define VM_RADIX_BOOT_CACHE 150
67#endif
68
69/*
70 * Such sizes should permit to keep node children contained into a single
71 * cache-line, or to at least not span many of those.
72 * In particular, sparse tries should however be compressed properly and
73 * then make some extra-levels not a big deal.
74 */
75#ifdef __LP64__
76#define VM_RADIX_WIDTH 4

--- 20 unchanged lines hidden (view full) ---

97 vm_pindex_t rn_owner; /* Owner of record. */
98 uint16_t rn_count; /* Valid children. */
99 uint16_t rn_clev; /* Current level. */
100};
101
102static uma_zone_t vm_radix_node_zone;
103
104/*
64/*
65 * Such sizes should permit to keep node children contained into a single
66 * cache-line, or to at least not span many of those.
67 * In particular, sparse tries should however be compressed properly and
68 * then make some extra-levels not a big deal.
69 */
70#ifdef __LP64__
71#define VM_RADIX_WIDTH 4

--- 20 unchanged lines hidden (view full) ---

92 vm_pindex_t rn_owner; /* Owner of record. */
93 uint16_t rn_count; /* Valid children. */
94 uint16_t rn_clev; /* Current level. */
95};
96
97static uma_zone_t vm_radix_node_zone;
98
99/*
105 * Boot-time cache of struct vm_radix_node objects.
106 * This cache is used to cater page allocations before the UMA zone is
107 * actually setup and pre-allocated (ie. pmap_init()).
108 */
109static u_int boot_cache_cnt;
110static struct vm_radix_node boot_cache[VM_RADIX_BOOT_CACHE];
111
112static struct vm_radix_node *
113vm_radix_carve_bootcache(void)
114{
115 struct vm_radix_node *rnode;
116
117 if (boot_cache_cnt == VM_RADIX_BOOT_CACHE)
118 panic("%s: Increase VM_RADIX_BOOT_CACHE (%u)", __func__,
119 VM_RADIX_BOOT_CACHE);
120 rnode = &boot_cache[boot_cache_cnt];
121 boot_cache_cnt++;
122 return (rnode);
123}
124
125/*
126 * Allocate a radix node. Pre-allocation ensures that the request will be
127 * always successfully satisfied.
128 */
129static __inline struct vm_radix_node *
130vm_radix_node_get(vm_pindex_t owner, uint16_t count, uint16_t clevel)
131{
132 struct vm_radix_node *rnode;
133
100 * Allocate a radix node. Pre-allocation ensures that the request will be
101 * always successfully satisfied.
102 */
103static __inline struct vm_radix_node *
104vm_radix_node_get(vm_pindex_t owner, uint16_t count, uint16_t clevel)
105{
106 struct vm_radix_node *rnode;
107
134 if (__predict_false(boot_cache_cnt <= VM_RADIX_BOOT_CACHE))
135 rnode = vm_radix_carve_bootcache();
136 else {
137 rnode = uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO);
108 rnode = uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO);
138
109
139 /*
140 * The required number of nodes might be already correctly
141 * pre-allocated in vm_radix_init(). However, UMA can reserve
142 * few nodes on per-cpu specific buckets, which will not be
143 * accessible from the curcpu. The allocation could then
144 * return NULL when the pre-allocation pool is close to be
145 * exhausted. Anyway, in practice this should never be a
146 * problem because a new node is not always required for
147 * insert, thus the pre-allocation pool should already have
148 * some extra-pages that indirectly deal with this situation.
149 */
150 if (rnode == NULL)
151 panic("%s: uma_zalloc() returned NULL for a new node",
152 __func__);
153 }
110 /*
111 * The required number of nodes might be already correctly
112 * pre-allocated in vm_radix_init(). However, UMA can reserve
113 * few nodes on per-cpu specific buckets, which will not be
114 * accessible from the curcpu. The allocation could then
115 * return NULL when the pre-allocation pool is close to be
116 * exhausted. Anyway, in practice this should never be a
117 * problem because a new node is not always required for
118 * insert, thus the pre-allocation pool should already have
119 * some extra-pages that indirectly deal with this situation.
120 */
121 if (rnode == NULL)
122 panic("%s: uma_zalloc() returned NULL for a new node",
123 __func__);
154 rnode->rn_owner = owner;
155 rnode->rn_count = count;
156 rnode->rn_clev = clevel;
157 return (rnode);
158}
159
160/*
161 * Free radix node.
162 */
163static __inline void
164vm_radix_node_put(struct vm_radix_node *rnode)
165{
166
124 rnode->rn_owner = owner;
125 rnode->rn_count = count;
126 rnode->rn_clev = clevel;
127 return (rnode);
128}
129
130/*
131 * Free radix node.
132 */
133static __inline void
134vm_radix_node_put(struct vm_radix_node *rnode)
135{
136
167 if (__predict_false(rnode > boot_cache &&
168 rnode <= &boot_cache[VM_RADIX_BOOT_CACHE]))
169 return;
170 uma_zfree(vm_radix_node_zone, rnode);
171}
172
173/*
174 * Return the position in the array for a given level.
175 */
176static __inline int
177vm_radix_slot(vm_pindex_t index, uint16_t level)

--- 184 unchanged lines hidden (view full) ---

362 rnode->rn_count));
363}
364#endif
365
366/*
367 * Pre-allocate intermediate nodes from the UMA slab zone.
368 */
369static void
137 uma_zfree(vm_radix_node_zone, rnode);
138}
139
140/*
141 * Return the position in the array for a given level.
142 */
143static __inline int
144vm_radix_slot(vm_pindex_t index, uint16_t level)

--- 184 unchanged lines hidden (view full) ---

329 rnode->rn_count));
330}
331#endif
332
333/*
334 * Pre-allocate intermediate nodes from the UMA slab zone.
335 */
336static void
370vm_radix_init(void *arg __unused)
337vm_radix_prealloc(void *arg __unused)
371{
372
338{
339
340 if (!uma_zone_reserve_kva(vm_radix_node_zone, cnt.v_page_count))
341 panic("%s: unable to create new zone", __func__);
342 uma_prealloc(vm_radix_node_zone, cnt.v_page_count);
343}
344SYSINIT(vm_radix_prealloc, SI_SUB_KMEM, SI_ORDER_SECOND, vm_radix_prealloc,
345 NULL);
346
347/*
348 * Initialize the UMA slab zone.
349 * Until vm_radix_prealloc() is called, the zone will be served by the
350 * UMA boot-time pre-allocated pool of pages.
351 */
352void
353vm_radix_init(void)
354{
355
373 vm_radix_node_zone = uma_zcreate("RADIX NODE",
374 sizeof(struct vm_radix_node), NULL,
375#ifdef INVARIANTS
376 vm_radix_node_zone_dtor,
377#else
378 NULL,
379#endif
380 NULL, NULL, VM_RADIX_PAD, UMA_ZONE_VM | UMA_ZONE_NOFREE);
356 vm_radix_node_zone = uma_zcreate("RADIX NODE",
357 sizeof(struct vm_radix_node), NULL,
358#ifdef INVARIANTS
359 vm_radix_node_zone_dtor,
360#else
361 NULL,
362#endif
363 NULL, NULL, VM_RADIX_PAD, UMA_ZONE_VM | UMA_ZONE_NOFREE);
381 if (!uma_zone_reserve_kva(vm_radix_node_zone, cnt.v_page_count))
382 panic("%s: unable to create new zone", __func__);
383 uma_prealloc(vm_radix_node_zone, cnt.v_page_count);
384 boot_cache_cnt = VM_RADIX_BOOT_CACHE + 1;
385}
364}
386SYSINIT(vm_radix_init, SI_SUB_KMEM, SI_ORDER_SECOND, vm_radix_init, NULL);
387
388/*
389 * Inserts the key-value pair in to the trie.
390 * Panics if the key already exists.
391 */
392void
393vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, vm_page_t page)
394{

--- 378 unchanged lines hidden --- 		365
366/*
367 * Inserts the key-value pair in to the trie.
368 * Panics if the key already exists.
369 */
370void
371vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, vm_page_t page)
372{

--- 378 unchanged lines hidden ---