xref: /freebsd/sys/powerpc/aim/slb.c (revision e28a4053) 
1 /*-
2  * Copyright (c) 2010 Nathan Whitehorn
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *
26  * $FreeBSD$
27  */
28 
29 #include <sys/param.h>
30 #include <sys/kernel.h>
31 #include <sys/lock.h>
32 #include <sys/mutex.h>
33 #include <sys/proc.h>
34 #include <sys/systm.h>
35 
36 #include <vm/vm.h>
37 #include <vm/pmap.h>
38 #include <vm/uma.h>
39 #include <vm/vm_map.h>
40 
41 #include <machine/md_var.h>
42 #include <machine/pmap.h>
43 #include <machine/vmparam.h>
44 
45 uintptr_t moea64_get_unique_vsid(void);
46 void moea64_release_vsid(uint64_t vsid);
47 static void slb_zone_init(void *);
48 
49 uma_zone_t slbt_zone;
50 uma_zone_t slb_cache_zone;
51 
52 SYSINIT(slb_zone_init, SI_SUB_KMEM, SI_ORDER_ANY, slb_zone_init, NULL);
53 
54 struct slbtnode {
55 	uint16_t	ua_alloc;
56 	uint8_t		ua_level;
57 	/* Only 36 bits needed for full 64-bit address space. */
58 	uint64_t	ua_base;
59 	union {
60 		struct slbtnode	*ua_child[16];
61 		struct slb	slb_entries[16];
62 	} u;
63 };
64 
65 /*
66  * For a full 64-bit address space, there are 36 bits in play in an
67  * esid, so 8 levels, with the leaf being at level 0.
68  *
69  * |3333|3322|2222|2222|1111|1111|11  |    |    |  esid
70  * |5432|1098|7654|3210|9876|5432|1098|7654|3210|  bits
71  * +----+----+----+----+----+----+----+----+----+--------
72  * | 8  | 7  | 6  | 5  | 4  | 3  | 2  | 1  | 0  | level
73  */
74 #define UAD_ROOT_LEVEL  8
75 #define UAD_LEAF_LEVEL  0
76 
77 static inline int
78 esid2idx(uint64_t esid, int level)
79 {
80 	int shift;
81 
82 	shift = level * 4;
83 	return ((esid >> shift) & 0xF);
84 }
85 
86 /*
87  * The ua_base field should have 0 bits after the first 4*(level+1)
88  * bits; i.e. only
89  */
90 #define uad_baseok(ua)                          \
91 	(esid2base(ua->ua_base, ua->ua_level) == ua->ua_base)
92 
93 
94 static inline uint64_t
95 esid2base(uint64_t esid, int level)
96 {
97 	uint64_t mask;
98 	int shift;
99 
100 	shift = (level + 1) * 4;
101 	mask = ~((1ULL << shift) - 1);
102 	return (esid & mask);
103 }
104 
105 /*
106  * Allocate a new leaf node for the specified esid/vmhandle from the
107  * parent node.
108  */
109 static struct slb *
110 make_new_leaf(uint64_t esid, uint64_t slbv, struct slbtnode *parent)
111 {
112 	struct slbtnode *child;
113 	struct slb *retval;
114 	int idx;
115 
116 	idx = esid2idx(esid, parent->ua_level);
117 	KASSERT(parent->u.ua_child[idx] == NULL, ("Child already exists!"));
118 
119 	/* unlock and M_WAITOK and loop? */
120 	child = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
121 	KASSERT(child != NULL, ("unhandled NULL case"));
122 
123 	child->ua_level = UAD_LEAF_LEVEL;
124 	child->ua_base = esid2base(esid, child->ua_level);
125 	idx = esid2idx(esid, child->ua_level);
126 	child->u.slb_entries[idx].slbv = slbv;
127 	child->u.slb_entries[idx].slbe = (esid << SLBE_ESID_SHIFT) | SLBE_VALID;
128 	setbit(&child->ua_alloc, idx);
129 
130 	retval = &child->u.slb_entries[idx];
131 
132 	/*
133 	 * The above stores must be visible before the next one, so
134 	 * that a lockless searcher always sees a valid path through
135 	 * the tree.
136 	 */
137 	powerpc_sync();
138 
139 	idx = esid2idx(esid, parent->ua_level);
140 	parent->u.ua_child[idx] = child;
141 	setbit(&parent->ua_alloc, idx);
142 
143 	return (retval);
144 }
145 
146 /*
147  * Allocate a new intermediate node to fit between the parent and
148  * esid.
149  */
150 static struct slbtnode*
151 make_intermediate(uint64_t esid, struct slbtnode *parent)
152 {
153 	struct slbtnode *child, *inter;
154 	int idx, level;
155 
156 	idx = esid2idx(esid, parent->ua_level);
157 	child = parent->u.ua_child[idx];
158 	KASSERT(esid2base(esid, child->ua_level) != child->ua_base,
159 	    ("No need for an intermediate node?"));
160 
161 	/*
162 	 * Find the level where the existing child and our new esid
163 	 * meet.  It must be lower than parent->ua_level or we would
164 	 * have chosen a different index in parent.
165 	 */
166 	level = child->ua_level + 1;
167 	while (esid2base(esid, level) !=
168 	    esid2base(child->ua_base, level))
169 		level++;
170 	KASSERT(level < parent->ua_level,
171 	    ("Found splitting level %d for %09jx and %09jx, "
172 	    "but it's the same as %p's",
173 	    level, esid, child->ua_base, parent));
174 
175 	/* unlock and M_WAITOK and loop? */
176 	inter = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
177 	KASSERT(inter != NULL, ("unhandled NULL case"));
178 
179 	/* Set up intermediate node to point to child ... */
180 	inter->ua_level = level;
181 	inter->ua_base = esid2base(esid, inter->ua_level);
182 	idx = esid2idx(child->ua_base, inter->ua_level);
183 	inter->u.ua_child[idx] = child;
184 	setbit(&inter->ua_alloc, idx);
185 	powerpc_sync();
186 
187 	/* Set up parent to point to intermediate node ... */
188 	idx = esid2idx(inter->ua_base, parent->ua_level);
189 	parent->u.ua_child[idx] = inter;
190 	setbit(&parent->ua_alloc, idx);
191 
192 	return (inter);
193 }
194 
195 uint64_t
196 kernel_va_to_slbv(vm_offset_t va)
197 {
198 	uint64_t esid, slbv;
199 
200 	esid = (uintptr_t)va >> ADDR_SR_SHFT;
201 
202 	/* Set kernel VSID to deterministic value */
203 	slbv = (KERNEL_VSID((uintptr_t)va >> ADDR_SR_SHFT)) << SLBV_VSID_SHIFT;
204 
205 	/* Figure out if this is a large-page mapping */
206 	if (hw_direct_map && va < VM_MIN_KERNEL_ADDRESS) {
207 		/*
208 		 * XXX: If we have set up a direct map, assumes
209 		 * all physical memory is mapped with large pages.
210 		 */
211 		if (mem_valid(va, 0) == 0)
212 			slbv |= SLBV_L;
213 	}
214 
215 	return (slbv);
216 }
217 
218 struct slb *
219 user_va_to_slb_entry(pmap_t pm, vm_offset_t va)
220 {
221 	uint64_t esid = va >> ADDR_SR_SHFT;
222 	struct slbtnode *ua;
223 	int idx;
224 
225 	ua = pm->pm_slb_tree_root;
226 
227 	for (;;) {
228 		KASSERT(uad_baseok(ua), ("uad base %016jx level %d bad!",
229 		    ua->ua_base, ua->ua_level));
230 		idx = esid2idx(esid, ua->ua_level);
231 
232 		/*
233 		 * This code is specific to ppc64 where a load is
234 		 * atomic, so no need for atomic_load macro.
235 		 */
236 		if (ua->ua_level == UAD_LEAF_LEVEL)
237 			return ((ua->u.slb_entries[idx].slbe & SLBE_VALID) ?
238 			    &ua->u.slb_entries[idx] : NULL);
239 
240 		ua = ua->u.ua_child[idx];
241 		if (ua == NULL ||
242 		    esid2base(esid, ua->ua_level) != ua->ua_base)
243 			return (NULL);
244 	}
245 
246 	return (NULL);
247 }
248 
249 uint64_t
250 va_to_vsid(pmap_t pm, vm_offset_t va)
251 {
252 	struct slb *entry;
253 
254 	/* Shortcut kernel case */
255 	if (pm == kernel_pmap)
256 		return (KERNEL_VSID((uintptr_t)va >> ADDR_SR_SHFT));
257 
258 	/*
259 	 * If there is no vsid for this VA, we need to add a new entry
260 	 * to the PMAP's segment table.
261 	 */
262 
263 	entry = user_va_to_slb_entry(pm, va);
264 
265 	if (entry == NULL)
266 		return (allocate_user_vsid(pm,
267 		    (uintptr_t)va >> ADDR_SR_SHFT, 0));
268 
269 	return ((entry->slbv & SLBV_VSID_MASK) >> SLBV_VSID_SHIFT);
270 }
271 
272 uint64_t
273 allocate_user_vsid(pmap_t pm, uint64_t esid, int large)
274 {
275 	uint64_t vsid, slbv;
276 	struct slbtnode *ua, *next, *inter;
277 	struct slb *slb;
278 	int idx;
279 
280 	KASSERT(pm != kernel_pmap, ("Attempting to allocate a kernel VSID"));
281 
282 	PMAP_LOCK_ASSERT(pm, MA_OWNED);
283 	vsid = moea64_get_unique_vsid();
284 
285 	slbv = vsid << SLBV_VSID_SHIFT;
286 	if (large)
287 		slbv |= SLBV_L;
288 
289 	ua = pm->pm_slb_tree_root;
290 
291 	/* Descend to the correct leaf or NULL pointer. */
292 	for (;;) {
293 		KASSERT(uad_baseok(ua),
294 		   ("uad base %09jx level %d bad!", ua->ua_base, ua->ua_level));
295 		idx = esid2idx(esid, ua->ua_level);
296 
297 		if (ua->ua_level == UAD_LEAF_LEVEL) {
298 			ua->u.slb_entries[idx].slbv = slbv;
299 			eieio();
300 			ua->u.slb_entries[idx].slbe = (esid << SLBE_ESID_SHIFT)
301 			    | SLBE_VALID;
302 			setbit(&ua->ua_alloc, idx);
303 			slb = &ua->u.slb_entries[idx];
304 			break;
305 		}
306 
307 		next = ua->u.ua_child[idx];
308 		if (next == NULL) {
309 			slb = make_new_leaf(esid, slbv, ua);
310 			break;
311                 }
312 
313 		/*
314 		 * Check if the next item down has an okay ua_base.
315 		 * If not, we need to allocate an intermediate node.
316 		 */
317 		if (esid2base(esid, next->ua_level) != next->ua_base) {
318 			inter = make_intermediate(esid, ua);
319 			slb = make_new_leaf(esid, slbv, inter);
320 			break;
321 		}
322 
323 		ua = next;
324 	}
325 
326 	/*
327 	 * Someone probably wants this soon, and it may be a wired
328 	 * SLB mapping, so pre-spill this entry.
329 	 */
330 	eieio();
331 	slb_insert_user(pm, slb);
332 
333 	return (vsid);
334 }
335 
336 void
337 free_vsid(pmap_t pm, uint64_t esid, int large)
338 {
339 	struct slbtnode *ua;
340 	int idx;
341 
342 	PMAP_LOCK_ASSERT(pm, MA_OWNED);
343 
344 	ua = pm->pm_slb_tree_root;
345 	/* Descend to the correct leaf. */
346 	for (;;) {
347 		KASSERT(uad_baseok(ua),
348 		   ("uad base %09jx level %d bad!", ua->ua_base, ua->ua_level));
349 
350 		idx = esid2idx(esid, ua->ua_level);
351 		if (ua->ua_level == UAD_LEAF_LEVEL) {
352 			ua->u.slb_entries[idx].slbv = 0;
353 			eieio();
354 			ua->u.slb_entries[idx].slbe = 0;
355 			clrbit(&ua->ua_alloc, idx);
356 			return;
357 		}
358 
359 		ua = ua->u.ua_child[idx];
360 		if (ua == NULL ||
361 		    esid2base(esid, ua->ua_level) != ua->ua_base) {
362 			/* Perhaps just return instead of assert? */
363 			KASSERT(0,
364 			    ("Asked to remove an entry that was never inserted!"));
365 			return;
366 		}
367 	}
368 }
369 
370 static void
371 free_slb_tree_node(struct slbtnode *ua)
372 {
373 	int idx;
374 
375 	for (idx = 0; idx < 16; idx++) {
376 		if (ua->ua_level != UAD_LEAF_LEVEL) {
377 			if (ua->u.ua_child[idx] != NULL)
378 				free_slb_tree_node(ua->u.ua_child[idx]);
379 		} else {
380 			if (ua->u.slb_entries[idx].slbv != 0)
381 				moea64_release_vsid(ua->u.slb_entries[idx].slbv
382 				    >> SLBV_VSID_SHIFT);
383 		}
384 	}
385 
386 	uma_zfree(slbt_zone, ua);
387 }
388 
389 void
390 slb_free_tree(pmap_t pm)
391 {
392 
393 	free_slb_tree_node(pm->pm_slb_tree_root);
394 }
395 
396 struct slbtnode *
397 slb_alloc_tree(void)
398 {
399 	struct slbtnode *root;
400 
401 	root = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
402 	root->ua_level = UAD_ROOT_LEVEL;
403 
404 	return (root);
405 }
406 
407 /* Lock entries mapping kernel text and stacks */
408 
409 #define SLB_SPILLABLE(slbe) \
410 	(((slbe & SLBE_ESID_MASK) < VM_MIN_KERNEL_ADDRESS && \
411 	    (slbe & SLBE_ESID_MASK) > 16*SEGMENT_LENGTH) || \
412 	    (slbe & SLBE_ESID_MASK) > VM_MAX_KERNEL_ADDRESS)
413 void
414 slb_insert_kernel(uint64_t slbe, uint64_t slbv)
415 {
416 	struct slb *slbcache;
417 	int i, j;
418 
419 	/* We don't want to be preempted while modifying the kernel map */
420 	critical_enter();
421 
422 	slbcache = PCPU_GET(slb);
423 
424 	/* Check for an unused slot, abusing the user slot as a full flag */
425 	if (slbcache[USER_SLB_SLOT].slbe == 0) {
426 		for (i = 0; i < USER_SLB_SLOT; i++) {
427 			if (!(slbcache[i].slbe & SLBE_VALID))
428 				goto fillkernslb;
429 		}
430 
431 		if (i == USER_SLB_SLOT)
432 			slbcache[USER_SLB_SLOT].slbe = 1;
433 	}
434 
435 	for (i = mftb() % 64, j = 0; j < 64; j++, i = (i+1) % 64) {
436 		if (i == USER_SLB_SLOT)
437 			continue;
438 
439 		if (SLB_SPILLABLE(slbcache[i].slbe))
440 			break;
441 	}
442 
443 	KASSERT(j < 64, ("All kernel SLB slots locked!"));
444 
445 fillkernslb:
446 	slbcache[i].slbv = slbv;
447 	slbcache[i].slbe = slbe | (uint64_t)i;
448 
449 	/* If it is for this CPU, put it in the SLB right away */
450 	if (pmap_bootstrapped) {
451 		/* slbie not required */
452 		__asm __volatile ("slbmte %0, %1" ::
453 		    "r"(slbcache[i].slbv), "r"(slbcache[i].slbe));
454 	}
455 
456 	critical_exit();
457 }
458 
459 void
460 slb_insert_user(pmap_t pm, struct slb *slb)
461 {
462 	int i;
463 
464 	PMAP_LOCK_ASSERT(pm, MA_OWNED);
465 
466 	if (pm->pm_slb_len < 64) {
467 		i = pm->pm_slb_len;
468 		pm->pm_slb_len++;
469 	} else {
470 		i = mftb() % 64;
471 	}
472 
473 	/* Note that this replacement is atomic with respect to trap_subr */
474 	pm->pm_slb[i] = slb;
475 }
476 
477 static void
478 slb_zone_init(void *dummy)
479 {
480 
481 	slbt_zone = uma_zcreate("SLB tree node", sizeof(struct slbtnode),
482 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);
483 	slb_cache_zone = uma_zcreate("SLB cache", 64*sizeof(struct slb *),
484 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);
485 }
486 
487 struct slb **
488 slb_alloc_user_cache(void)
489 {
490 	return (uma_zalloc(slb_cache_zone, M_ZERO));
491 }
492 
493 void
494 slb_free_user_cache(struct slb **slb)
495 {
496 	uma_zfree(slb_cache_zone, slb);
497 }
498