]> git.saurik.com Git - apple/xnu.git/blame - osfmk/ppc/skiplists.s
projects / apple / xnu.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
xnu-792.tar.gz
[apple/xnu.git] / osfmk / ppc / skiplists.s
CommitLineData
55e303ae 1/*
91447636 2 * Copyright (c) 2002-2004 Apple Computer, Inc. All rights reserved.
55e303ae
A		 3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
e5568f75
A		 6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
55e303ae 11 *
e5568f75
A		 12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
55e303ae
A		 14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
e5568f75
A		 16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
55e303ae
A		 19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22
23/* skiplists.s
24 *
25 * These are the subroutines that manage the skip-list data structures used for the
26 * resident mappings for each pmap. We used to use a much simpler hash-based scheme,
27 * but it didn't scale well for 64-bit address spaces and multi-GB real memories.
28 * Here's a brief tutorial on skip-lists:
29 *
30 * The basic idea is that each mapping is on one or more singly-linked lists, sorted
31 * in increasing order by virtual address. The number of lists a mapping is on is an
32 * invariant property determined when the mapping is created, using an exponentially-
33 * distributed random number. Every mapping is on the first list. Ideally, each
34 * successive list has only 1/F as many nodes on it as the previous, where F is the
35 * "fanout." With a max of n lists, up to F**n nodes can be handled optimally.
36 *
37 * Searching, adding, and deleting from a skip-list can all be done in O(ln(n)) time.
38 * Because the first skip-list is just a sorted list of all mappings, it is also
39 * efficient to purge a sparsely populated pmap of all the mappings in a large range,
40 * for example when tearing down an address space. Large-range deletes are the
41 * primary advantage of skip-lists over a hash, btw.
42 *
43 * We currently use a fanout of 4 and a maximum of 12 lists (cf kSkipListFanoutShift
44 * and kSkipListMaxLists.) Thus, we can optimally handle pmaps with as many as 4**12
45 * pages, which is 64GB of resident physical memory per pmap. Pmaps can be larger than
46 * this, albeit with diminishing efficiency.
47 *
48 * The major problem with skip-lists is that we could waste a lot of space with 12
49 * 64-bit link fields in every mapping. So we currently have two sizes of mappings:
50 * 64-byte nodes with 4 list links, and 128-byte nodes with 12. Only one in every
51 * (4**4)==256 mappings requires the larger node, so the average size is 64.25 bytes.
52 * In practice, the additional complexity of the variable node size is entirely
53 * contained in the allocate and free routines.
54 *
55 * The other, mostly theoretic problem with skip-lists is that they have worst cases
56 * where performance becomes nearly linear. These worst-cases are quite rare but there
57 * is no practical way to prevent them.
58 */
59
60
61; set nonzero to accumulate skip-list stats on a per-map basis:
62#define SKIPLISTSTATS 1
63
64; cr7 bit set when mapSearchFull() finds a match on a high list:
65#define bFullFound 28
66
67#include <assym.s>
68#include <debug.h>
69#include <ppc/asm.h>
70#include <ppc/proc_reg.h>
71#include <ppc/exception.h>
72
73
74/*
75 * *********************
76 * * m a p S e a r c h *
77 * *********************
78 *
79 * Given a pmap and a virtual address (VA), find the mapping for that address.
80 * This is the fast call, that does not set up the previous-ptr vector or make
81 * consistency checks. When called:
82 * the pmap is locked (shared or exclusive)
83 * translation is off, interrupts masked
84 * 64-bit mode is enabled (if on a 64-bit machine)
85 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
86 * r3 = pmap ptr
87 * r4 = high 32 bits of key to search for (0 if a 32-bit processor)
88 * r5 = low 32 bits of key (low 12 bits may be nonzero garbage)
89 * r7 = mpFlags field if found. Undefined if not
90 *
91 * We return the mapping ptr (or 0) in r3, and the next VA (or 0 if no more) in r4 and r5.
92 * Except for cr6 (which is global), we trash nonvolatile regs. Called both on 32- and 64-bit
93 * machines, though we quickly branch into parallel code paths.
94 */
95 .text
96 .align 5
97 .globl EXT(mapSearch)
98LEXT(mapSearch)
99 lbz r7,pmapCurLists(r3) ; get largest #lists any mapping is on
100 la r8,pmapSkipLists+4(r3) ; point to lists in pmap, assuming 32-bit machine
101 rlwinm r5,r5,0,0,19 ; zero low 12 bits of key
102 mr r6,r3 ; save pmap ptr here so we can accumulate statistics
103 li r9,0 ; initialize prev ptr
104 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
105 li r2,0 ; initialize count of mappings visited
106 slwi r7,r7,3 ; get offset of last list in use
107 blt-- mapSrchPmapEmpty ; pmapCurLists==0 (ie, no mappings)
108 lwzx r3,r8,r7 ; get 32-bit ptr to 1st mapping in highest list
109 bf-- pf64Bitb,mapSrch32c ; skip if 32-bit processor
110 subi r8,r8,4 ; we use all 64 bits of ptrs
111 rldimi r5,r4,32,0 ; r5 <- 64-bit va
112 ldx r3,r8,r7 ; get 64-bit ptr to 1st mapping in highest list
113 b mapSrch64c ; enter 64-bit search loop
114
115
116 ; 64-bit processors. Check next mapping.
117 ; r2 = count of mappings visited so far
118 ; r3 = current mapping ptr
119 ; r4 = va of current mapping (ie, of r3)
120 ; r5 = va to search for (the "key") (low 12 bits are 0)
121 ; r6 = pmap ptr
122 ; r7 = current skip list number * 8
123 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
124 ; r9 = prev ptr, or 0 if none
125
126 .align 5
127mapSrch64a: ; loop over each mapping
128 ld r4,mpVAddr(r3) ; get va for this mapping (plus flags in low 12 bits)
129 addi r2,r2,1 ; count mappings visited
130 rldicr r4,r4,0,51 ; zero low 12 bits of mapping va
131 cmpld cr1,r5,r4 ; compare the vas
132 blt cr1,mapSrch64d ; key is less, try next list
133 la r8,mpList0(r3) ; point to skip list vector in this mapping
134 mr r9,r3 ; remember prev ptr
135 beq-- cr1,mapSrch64Found ; this is the correct mapping
136 ldx r3,r7,r8 ; get ptr to next mapping in current list
137mapSrch64c:
138 mr. r3,r3 ; was there another mapping on current list?
139 bne++ mapSrch64a ; was another, so loop
140mapSrch64d:
141 subic. r7,r7,8 ; move on to next list offset
142 ldx r3,r7,r8 ; get next mapping on next list (if any)
143 bge++ mapSrch64c ; loop to try next list
144
145 ; Mapping not found, check to see if prev node was a block mapping or nested pmap.
146 ; If not, or if our address is not covered by the block or nested map, return 0.
147 ; Note the advantage of keeping the check for block mappings (and nested pmaps)
148 ; out of the inner loop; we do the special case work at most once per search, and
149 ; never for the most-common case of finding a scalar mapping. The full searches
150 ; must check _in_ the inner loop, to get the prev ptrs right.
151
152 mr. r9,r9 ; was there a prev ptr?
153 li r3,0 ; assume we are going to return null
154 ld r4,pmapSkipLists(r6) ; assume prev ptr null... so next is first
155 beq-- mapSrch64Exit ; prev ptr was null, search failed
156 lwz r0,mpFlags(r9) ; get flag bits from prev mapping
157 ld r10,mpVAddr(r9) ; re-fetch base address of prev ptr
158 ld r4,mpList0(r9) ; get 64-bit ptr to next mapping, if any
55e303ae 159 lhz r11,mpBSize(r9) ; get #pages/#segments in block/submap mapping
91447636
A		 160
161 rlwinm r0,r0,0,mpType ; isolate mapping type code
162 cmplwi cr1,r0,mpBlock ; cr1_eq <- block type?
163 cmplwi r0,mpNest ; cr0_eq <- nested type?
164 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- block or nested type?
165 cmplwi cr5,r0,mpLinkage ; cr5_eq <- linkage type?
166 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
167
55e303ae 168 rldicr r10,r10,0,51 ; zero low 12 bits of mapping va
91447636 169 bne mapSrch64Exit ; prev mapping was just a scalar page, search failed
55e303ae 170 sldi r0,r11,12 ; assume block mapping, get size in bytes - 4k
91447636 171 beq cr1,mapSrch64f ; we guessed right, it was a block mapping
55e303ae
A		 172 addi r11,r11,1 ; mpBSize is 1 too low
173 sldi r11,r11,28 ; in a nested pmap, mpBSize is in units of segments
174 subi r0,r11,4096 ; get address of last page in submap
175mapSrch64f:
176 add r10,r10,r0 ; r10 <- last page in this mapping
177 cmpld r5,r10 ; does this mapping cover our page?
178 bgt mapSrch64Exit ; no, search failed
179 mr r3,r9 ; yes, we found it
180
181 ; found the mapping
182 ; r2 = count of nodes visited
183 ; r3 = the mapping
184 ; r6 = pmap ptr
185
186mapSrch64Found: ; WARNING: can drop down to here
187 ld r4,mpList0(r3) ; get ptr to next mapping
188 lwz r7,mpFlags(r3) ; Get the flags for our caller
189
190 ; r2 = count of nodes visited
191 ; r3 = return value (ie, found mapping or 0)
192 ; r4 = next mapping (or 0 if none)
193 ; r6 = pmap ptr
194 ; r7 = mpFlags
195
196mapSrch64Exit: ; WARNING: can drop down to here
197 mr. r5,r4 ; next ptr null?
198#if SKIPLISTSTATS
199 lwz r10,pmapSearchCnt(r6) ; prepare to accumulate statistics
200 ld r8,pmapSearchVisits(r6)
201 addi r10,r10,1 ; count searches
202 add r8,r8,r2 ; count nodes visited
203 stw r10,pmapSearchCnt(r6)
204 std r8,pmapSearchVisits(r6)
205#endif
206 beqlr- ; next ptr was null, so return 0 in r4 and r5
207 lwz r5,mpVAddr+4(r4) ; get VA of next node
208 lwz r4,mpVAddr+0(r4)
209 blr
210
211
212 ; 32-bit processors. Check next mapping.
213 ; r2 = count of mappings visited so far
214 ; r3 = current mapping ptr
215 ; r4 = va of current mapping (ie, of r3)
216 ; r5 = va to search for (the "key") (low 12 bits are 0)
217 ; r6 = pmap ptr
218 ; r7 = current skip list number * 8
219 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
220 ; r9 = prev ptr, or 0 if none
221
222 .align 4
223mapSrch32a: ; loop over each mapping
224 lwz r4,mpVAddr+4(r3) ; get va for this mapping (plus flags in low 12 bits)
225 addi r2,r2,1 ; count mappings visited
226 rlwinm r4,r4,0,0,19 ; zero low 12 bits of mapping va
227 cmplw cr1,r5,r4 ; compare the vas
228 blt cr1,mapSrch32d ; key is less, try next list
229 la r8,mpList0+4(r3) ; point to skip list vector in this mapping
230 mr r9,r3 ; remember prev ptr
231 beq- cr1,mapSrch32Found ; this is the correct mapping
232 lwzx r3,r7,r8 ; get ptr to next mapping in current list
233mapSrch32c:
234 mr. r3,r3 ; was there another mapping on current list?
235 bne+ mapSrch32a ; was another, so loop
236mapSrch32d:
237 subic. r7,r7,8 ; move on to next list offset
238 lwzx r3,r7,r8 ; get next mapping on next list (if any)
239 bge+ mapSrch32c ; loop to try next list
240
241 ; Mapping not found, check to see if prev node was a block mapping or nested pmap.
242 ; If not, or if our address is not covered by the block or nested map, return 0.
243 ; Note the advantage of keeping the check for block mappings (and nested pmaps)
244 ; out of the inner loop; we do the special case work at most once per search, and
245 ; never for the most-common case of finding a scalar mapping. The full searches
246 ; must check _in_ the inner loop, to get the prev ptrs right.
247
248 mr. r9,r9 ; was there a prev ptr?
249 li r3,0 ; assume we are going to return null
250 lwz r4,pmapSkipLists+4(r6) ; assume prev ptr null... so next is first
251 beq- mapSrch32Exit ; prev ptr was null, search failed
252 lwz r0,mpFlags(r9) ; get flag bits from prev mapping
253 lwz r10,mpVAddr+4(r9) ; re-fetch base address of prev ptr
55e303ae 254 lwz r4,mpList0+4(r9) ; get ptr to next mapping, if any
91447636
A		 255
256 rlwinm r0,r0,0,mpType ; isolate mapping type code
257 cmplwi cr1,r0,mpBlock ; cr1_eq <- block type?
258 cmplwi r0,mpNest ; cr0_eq <- nested type?
259 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- block or nested type?
260 cmplwi cr5,r0,mpLinkage ; cr5_eq <- linkage type?
261 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
262
263 bne mapSrch32Exit ; prev mapping was just a scalar page, search failed
55e303ae 264 lhz r11,mpBSize(r9) ; get #pages/#segments in block/submap mapping
55e303ae
A		 265 rlwinm r10,r10,0,0,19 ; zero low 12 bits of block mapping va
266 slwi r0,r11,12 ; assume block mapping, get size in bytes - 4k
91447636 267 beq cr1,mapSrch32f ; we guessed right, it was a block mapping
55e303ae
A		 268 addi r11,r11,1 ; mpBSize is 1 too low
269 slwi r11,r11,28 ; in a nested pmap, mpBSize is in units of segments
270 subi r0,r11,4096 ; get address of last page in submap
271mapSrch32f:
272 add r10,r10,r0 ; r10 <- last page in this mapping
273 cmplw r5,r10 ; does this mapping cover our page?
274 bgt mapSrch32Exit ; no, search failed
275 mr r3,r9 ; yes, we found it
276
277 ; found the mapping
278 ; r2 = count of nodes visited
279 ; r3 = the mapping
280 ; r6 = pmap ptr
281
282mapSrch32Found: ; WARNING: can drop down to here
283 lwz r4,mpList0+4(r3) ; get ptr to next mapping
284 lwz r7,mpFlags(r3) ; Get mpFlags for our caller
285 ; r2 = count of nodes visited
286 ; r3 = return value (ie, found mapping or 0)
287 ; r4 = next mapping (or 0 if none)
288 ; r6 = pmap ptr
289 ; r7 = mpFlags
290
291mapSrch32Exit:
292 mr. r5,r4 ; next ptr null?
293#if SKIPLISTSTATS
294 lwz r10,pmapSearchCnt(r6) ; prepare to accumulate statistics
295 lwz r8,pmapSearchVisits(r6)
296 lwz r9,pmapSearchVisits+4(r6)
297 addi r10,r10,1 ; count searches
298 addc r9,r9,r2 ; count nodes visited
299 addze r8,r8
300 stw r10,pmapSearchCnt(r6)
301 stw r8,pmapSearchVisits(r6)
302 stw r9,pmapSearchVisits+4(r6)
303#endif
304 beqlr- ; next ptr was null, so return 0 in r4 and r5
305 lwz r5,mpVAddr+4(r4) ; get VA of next node
306 lwz r4,mpVAddr+0(r4)
307 blr
308
309 ; Here when the pmap is empty (ie, pmapCurLists==0), both in 32 and 64-bit mode,
310 ; and from both mapSearch and mapSearchFull.
311 ; r6 = pmap ptr
312
313mapSrchPmapEmpty:
314 li r3,0 ; return null
315 li r4,0 ; return 0 as virtual address of next node
316 li r5,0
317#if SKIPLISTSTATS
318 lwz r7,pmapSearchCnt(r6) ; prepare to accumulate statistics
319 addi r7,r7,1 ; count searches
320 stw r7,pmapSearchCnt(r6)
321#endif
322 blr
323
324
325/*
326 * *****************************
327 * * m a p S e a r c h F u l l *
328 * *****************************
329 *
330 * Given a pmap and a virtual address (VA), find the mapping for that address.
331 * This is the "full" call, that sets up a vector of ptrs to the previous node
332 * (or to the pmap, if there is no previous node) for each list that the mapping
333 * in on. We also make consistency checks on the skip-lists. When called:
334 * the pmap is locked (shared or exclusive)
335 * translation is off, interrupts masked
336 * 64-bit mode is enabled (if on a 64-bit machine)
337 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
338 * r3 = pmap ptr
339 * r4 = high 32 bits of key to search for (0 if a 32-bit processor)
340 * r5 = low 32 bits of key (low 12 bits may be nonzero garbage)
341 *
342 * We return the mapping ptr (or 0) in r3, and the next VA (or 0 if no more) in r4 and r5.
343 * Except for cr6 (which is global), we trash nonvolatile regs. Called both on 32- and 64-bit
344 * machines, though we quickly branch into parallel code paths.
345 */
346 .text
347 .align 5
348 .globl EXT(mapSearchFull)
349LEXT(mapSearchFull)
350 lbz r7,pmapCurLists(r3) ; get largest #lists any mapping is on
351 la r8,pmapSkipLists+4(r3) ; point to lists in pmap, assuming 32-bit machine
352 rlwinm r5,r5,0,0,19 ; zero low 12 bits of key
353 mr r6,r3 ; save pmap ptr here so we can accumulate statistics
354 li r2,0 ; initialize count of mappings visited
355 mfsprg r12,0 ; get the per-proc data ptr
356 crclr bFullFound ; we have not found the mapping yet
357 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
358 subi r9,r8,mpList0+4 ; initialize prev ptr to be a fake mapping
359 slwi r7,r7,3 ; get (offset*8) of last list
360 la r12,skipListPrev+4(r12) ; point to vector of prev ptrs, assuming 32-bit machine
361 blt-- mapSrchPmapEmpty ; pmapCurLists==0 (ie, no mappings)
362 lwzx r3,r8,r7 ; get 32-bit ptr to 1st mapping in highest list
363 li r10,0 ; initialize prev ptrs VA to 0 too
364 bf-- pf64Bitb,mapSrchFull32c ; skip if 32-bit processor
365 subi r8,r8,4 ; we use all 64 bits of ptrs
366 subi r12,r12,4
367 rldimi r5,r4,32,0 ; r5 <- 64-bit va
368 ldx r3,r8,r7 ; get 64-bit ptr to 1st mapping in highest list
369 b mapSrchFull64c ; enter 64-bit search loop
370
371
372 ; 64-bit processors. Check next mapping.
373 ; r2 = count of mappings visited so far
374 ; r3 = current mapping ptr
375 ; r4 = va of current mapping (ie, of r3)
376 ; r5 = va to search for (the "key") (low 12 bits are 0)
377 ; r6 = pmap ptr
378 ; r7 = current skip list number * 8
379 ; r8 = ptr to skip list vector of mapping pointed to by r9
380 ; r9 = prev ptr, ie highest mapping that comes before search target (initially the pmap)
381 ; r10 = prev mappings va, or 0 if r9==pmap
382 ; r12 = ptr to the skipListPrev vector in the per-proc
383
384 .align 5
385mapSrchFull64a: ; loop over each mapping
386 ld r4,mpVAddr(r3) ; get va for this mapping (plus flags in low 12 bits)
387 addi r2,r2,1 ; count mappings visited
388 lwz r0,mpFlags(r3) ; get mapping flag bits
91447636 389
55e303ae
A		 390 cmpld cr0,r10,r4 ; make sure VAs come in strictly ascending order
391 rldicr r4,r4,0,51 ; zero low 12 bits of mapping va
392 cmpld cr1,r5,r4 ; compare the vas
393 bge-- cr0,mapSkipListPanic ; die if keys are out of order
91447636
A		 394
395 rlwinm r0,r0,0,mpType ; isolate mapping type code
396 cmplwi r0,mpNest ; cr0_eq <- nested type?
397 cmplwi cr5,r0,mpLinkage ; cr5_eq <- linkage type?
398 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- nested type or linkage type?
399 cmplwi cr5,r0,mpBlock ; cr5_eq <- block type?
400 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
401
55e303ae
A		 402 blt cr1,mapSrchFull64d ; key is less, try next list
403 beq cr1,mapSrchFull64Found ; this is the correct mapping
91447636 404 beq-- cr0,mapSrchFull64e ; handle block mapping or nested pmap
55e303ae
A		 405mapSrchFull64b:
406 la r8,mpList0(r3) ; point to skip list vector in this mapping
407 mr r9,r3 ; current becomes previous
408 ldx r3,r7,r8 ; get ptr to next mapping in current list
409 mr r10,r4 ; remember prev ptrs VA
410mapSrchFull64c:
411 mr. r3,r3 ; was there another mapping on current list?
412 bne++ mapSrchFull64a ; was another, so loop
413mapSrchFull64d:
414 stdx r9,r7,r12 ; save prev ptr in per-proc vector
415 subic. r7,r7,8 ; move on to next list offset
416 ldx r3,r7,r8 ; get next mapping on next list (if any)
417 bge++ mapSrchFull64c ; loop to try next list
418
419 ; Mapping not found, return 0 and next higher key
420
421 li r3,0 ; return null
422 bt-- bFullFound,mapSkipListPanic ; panic if it was on earlier list
423 ld r4,mpList0(r9) ; get 64-bit ptr to next mapping, if any
424 b mapSrch64Exit
425
426 ; Block mapping or nested pmap, and key > base. We must compute the va of
427 ; the end of the block to see if key fits within it.
428
429mapSrchFull64e:
430 lhz r11,mpBSize(r3) ; get #pages/#segments in block/submap mapping (if nonscalar)
55e303ae 431 sldi r0,r11,12 ; assume block mapping, get size in bytes - 4k
91447636 432 beq cr5,mapSrchFull64f ; we guessed right, it was a block mapping
55e303ae
A		 433 addi r11,r11,1 ; mpBSize is 1 too low
434 sldi r11,r11,28 ; in a nested pmap, mpBSize is in units of segments
435 subi r0,r11,4096 ; get address of last page in submap
436mapSrchFull64f:
437 add r4,r4,r0 ; r4 <- last page in this mapping
438 cmpld r5,r4 ; does this mapping cover our page?
439 bgt mapSrchFull64b ; no, try next mapping (r4 is advanced to end of range)
440
441
442 ; found the mapping
443 ; r2 = count of nodes visited
444 ; r3 = the mapping
445 ; r6 = pmap ptr
446 ; r7 = current skip list number * 8
447 ; r8 = ptr to prev mappings (ie, r9) skip-list vector
448 ; r9 = prev ptr, ie highest mapping that comes before search target
449 ; r10 = prev mappings va
450 ; r12 = ptr to the skipListPrev vector in the per-proc
451
452mapSrchFull64Found: ; WARNING: can drop down to here
453 cmpwi r7,0 ; are we in the last skip-list?
454 crset bFullFound ; remember that we found the mapping
455 bne mapSrchFull64d ; mapSearchFull must search all lists to get prev ptrs
456 ld r4,mpList0(r3) ; get ptr to next mapping
457 stdx r9,r7,r12 ; save prev ptr in last list
458 lwz r7,mpFlags(r3) ; Get the flags for our caller
459 b mapSrch64Exit
460
461
462 ; 32-bit processors. Check next mapping.
463 ; r2 = count of nodes visited
464 ; r3 = ptr to next mapping in current list
465 ; r5 = va to search for (the "key") (low 12 bits are 0)
466 ; r6 = pmap ptr
467 ; r7 = current skip list number * 8
468 ; r8 = ptr to skip list vector of mapping pointed to by r9
469 ; r9 = prev ptr, ie highest mapping that comes before search target (initially the pmap)
470 ; r10 = prev mappings va, or 0 if r9==pmap
471 ; r12 = ptr to the skipListPrev vector in the per-proc
472
473 .align 4
474mapSrchFull32a: ; loop over each mapping
475 lwz r4,mpVAddr+4(r3) ; get va for this mapping (plus flags in low 12 bits)
476 addi r2,r2,1 ; count mappings visited
477 lwz r0,mpFlags(r3) ; get mapping flag bits
91447636 478
55e303ae
A		 479 cmplw cr0,r10,r4 ; make sure VAs come in strictly ascending order
480 rlwinm r4,r4,0,0,19 ; zero low 12 bits of mapping va
481 cmplw cr1,r5,r4 ; compare the vas
482 bge- cr0,mapSkipListPanic ; die if keys are out of order
91447636
A		 483
484 rlwinm r0,r0,0,mpType ; isolate mapping type code
485 cmplwi cr5,r0,mpLinkage ; cr5_eq <- linkage type?
486 cmplwi r0,mpNest ; cr0_eq <- nested type?
487 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- linkage type or nested type?
488 cmplwi cr5,r0,mpBlock ; cr5_eq <- block type?
489 cror cr0_eq,cr5_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
490
55e303ae
A		 491 blt cr1,mapSrchFull32d ; key is less than this va, try next list
492 beq- cr1,mapSrchFull32Found ; this is the correct mapping
91447636 493 beq- cr0,mapSrchFull32e ; handle block mapping or nested pmap
55e303ae
A		 494mapSrchFull32b:
495 la r8,mpList0+4(r3) ; point to skip list vector in this mapping
496 mr r9,r3 ; current becomes previous
497 lwzx r3,r7,r8 ; get ptr to next mapping in current list
498 mr r10,r4 ; remember prev ptrs VA
499mapSrchFull32c:
500 mr. r3,r3 ; next becomes current
501 bne+ mapSrchFull32a ; was another, so loop
502mapSrchFull32d:
503 stwx r9,r7,r12 ; save prev ptr in per-proc vector
504 subic. r7,r7,8 ; move on to next list offset
505 lwzx r3,r7,r8 ; get next mapping on lower list (if any)
506 bge+ mapSrchFull32c ; loop to try next list
507
508 ; mapping not found, return 0 and next-key
509
510 li r3,0 ; return null
511 bt- bFullFound,mapSkipListPanic ; panic if it was on an earlier list
512 lwz r4,mpList0+4(r9) ; get ptr to next mapping
513 b mapSrch32Exit
514
515 ; Block mapping or nested pmap, and key > base. We must compute the va of
516 ; the end of the block to see if our key fits within it.
517
518mapSrchFull32e:
519 lhz r11,mpBSize(r3) ; get #pages/#segments in block/submap mapping (if nonscalar)
55e303ae 520 slwi r0,r11,12 ; assume block mapping, get size in bytes - 4k
91447636 521 beq cr5,mapSrchFull32f ; we guessed right, it was a block mapping
55e303ae
A		 522 addi r11,r11,1 ; mpBSize is 1 too low
523 slwi r11,r11,28 ; in a nested pmap, mpBSize is in units of segments
524 subi r0,r11,4096 ; get address of last page in submap
525mapSrchFull32f:
526 add r4,r4,r0 ; r4 <- last page in this mapping
527 cmplw r5,r4 ; does this mapping cover our page?
528 bgt mapSrchFull32b ; no, try next mapping
529
530
531 ; found the mapping
532 ; r2 = count of nodes visited
533 ; r3 = the mapping
534 ; r6 = pmap ptr
535 ; r7 = current skip list number * 8
536 ; r9 = prev ptr, ie highest mapping that comes before search target, or 0
537 ; r10 = prev mappings va
538 ; r12 = ptr to the skipListPrev vector in the per-proc
539
540mapSrchFull32Found: ; WARNING: can drop down to here
541 cmpwi r7,0 ; are we in the last skip-list?
542 crset bFullFound ; remember that we found the mapping
543 bne mapSrchFull32d ; mapSearchFull must search all lists to get prev ptrs
544 lwz r4,mpList0+4(r3) ; get ptr to next mapping
545 stwx r9,r7,r12 ; save prev ptr in last list
546 lwz r7,mpFlags(r3) ; Get mpFlags for our caller
547 b mapSrch32Exit
548
549
550/*
551 * *********************
552 * * m a p I n s e r t *
553 * *********************
554 *
555 * Insert a mapping into pmap skip-lists. The caller has already called mapSearchFull to
556 * determine that this mapping does not overlap other mappings in the pmap. As a side effect
557 * of calling mapSearchFull, the per-proc skipListPrev array is set up with a vector of the
558 * previous ptrs for each skip list. When called:
559 * the pmap is locked (exclusive)
560 * translation is off, interrupts masked
561 * 64-bit mode is enabled (if on a 64-bit machine)
562 * mapSearchFull has just been called for this mappings key
563 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
564 * r3 = pmap ptr
565 * r4 = mapping ptr
566 *
567 * There is no return value. Except for cr6 (which is global), we trash nonvolatile regs.
568 */
569
570 .align 5
571 .globl EXT(mapInsert)
572LEXT(mapInsert)
573 lwz r8,mpFlags(r4) ; get this mappings flags
574 lbz r7,pmapCurLists(r3) ; get current max# lists any mapping is on
575 la r10,pmapSkipLists+4(r3) ; r10 <-- base of pmap list headers, assuming 32-bit machine
576 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
577 mfsprg r12,0 ; get ptr to our per-proc
578 andi. r9,r8,mpLists ; get #lists this mapping is on (1<=n<=27)
579 la r12,skipListPrev+4(r12) ; r12 <-- base of prev ptr vector
580 sub. r6,r9,r7 ; is this mapping on more lists than any other?
581 slwi r8,r9,3 ; get #lists * 8
582 subi r8,r8,8 ; get offset to topmost (last) list in use
583 bf-- pf64Bitb,mapIns32 ; handle 32-bit processor
584 subi r10,r10,4 ; we use all 8 bytes of the ptr fields
585 subi r11,r11,4
586 subi r12,r12,4
587 ble++ mapIns64a ; not new max #lists
588
589 ; 64-bit processor: We must increase pmapCurLists. Since mapSearchFull() only
590 ; sets up the first pmapCurLists prev ptrs, we must initialize the new ones to
591 ; point to the pmap. While we are at it, we verify that the unused list hdrs in
592 ; the pmap are 0.
593
594 cmpwi r9,kSkipListMaxLists ; in range?
595 stb r9,pmapCurLists(r3) ; remember new max
596 mtctr r6 ; set up count of new lists
597 mr r5,r8 ; copy offset to last list
598 subi r0,r10,mpList0 ; r0 <-- fake mapping ptr (to pmap) for null prev ptrs
599 bgt-- mapSkipListPanic ; choke if this mapping is on too many lists
600mapIns64NewList:
601 ldx r6,r5,r10 ; get pmap list head
602 stdx r0,r5,r12 ; initialize prev ptr
603 subi r5,r5,8 ; get next list offset
604 cmpdi r6,0 ; was list hdr null?
605 bdnzt cr0_eq,mapIns64NewList ; loop if more lists to initialize and list hdr was 0
606 bne-- mapSkipListPanic ; die if pmap list hdr was not null
607 b mapIns64a
608
609 ; 64-bit processor: loop over each list this mapping is on
610 ; r4 = mapping
611 ; r8 = next list offset
612 ; r10 = ptr to base of pmap list header vector
613 ; r11 = ptr to base of new mappings list vector
614 ; r12 = ptr to base of prev ptr vector in per-proc
615
616 .align 5
617mapIns64a:
618 ldx r5,r8,r12 ; get prev ptr from per-proc vector
619 cmpwi cr1,r8,0 ; more to go?
620 la r7,mpList0(r5) ; get base of prev mappings list vector
621 ldx r9,r8,r7 ; ***
622 stdx r4,r8,r7 ; * insert new mapping in middle of this list
623 stdx r9,r8,r11 ; ***
624 subi r8,r8,8 ; get next list offset
625 bne++ cr1,mapIns64a ; more lists to go
626 blr ; done
627
628 ; Handle 32-bit processor. First, increase pmapCurLists if necessary; cr0 is bgt
629 ; iff the new mapping has more lists. Since mapSearchFull() only sets up the first
630 ; pmapCurLists prev ptrs, we must initialize any new ones to point to the pmap.
631 ; While we are at it, we verify that the unused list hdrs in the pmap are 0.
632
633mapIns32:
634 ble+ mapIns32a ; skip if new mapping does not use extra lists
635 cmpwi r9,kSkipListMaxLists ; in range?
636 stb r9,pmapCurLists(r3) ; remember new max
637 mtctr r6 ; set up count of new lists
638 mr r5,r8 ; copy offset to last list
639 subi r0,r10,mpList0+4 ; r0 <-- fake mapping ptr (to pmap) for null prev ptrs
640 bgt- mapSkipListPanic ; choke if this mapping is on too many lists
641mapIns32NewList:
642 lwzx r6,r5,r10 ; get pmap list head
643 stwx r0,r5,r12 ; initialize prev ptr
644 subi r5,r5,8 ; get next list offset
645 cmpwi r6,0 ; was list hdr null?
646 bdnzt cr0_eq,mapIns32NewList ; loop if more lists to initialize and list hdr was 0
647 bne- mapSkipListPanic ; die if pmap list hdr was not null
648 b mapIns32a
649
650 ; 32-bit processor: loop over each list this mapping is on
651 ; r4 = mapping
652 ; r8 = next list offset
653 ; r10 = ptr to base of pmap list header vector
654 ; r11 = ptr to base of new mappings list vector
655 ; r12 = ptr to base of prev ptr vector
656
657 .align 4
658mapIns32a:
659 lwzx r5,r8,r12 ; get prev ptr from per-proc vector
660 cmpwi cr1,r8,0 ; more to go?
661 la r7,mpList0+4(r5) ; get base of prev mappings list vector
662 lwzx r9,r8,r7 ; ***
663 stwx r4,r8,r7 ; * insert new mapping in middle of this list
664 stwx r9,r8,r11 ; ***
665 subi r8,r8,8 ; get next list offset
666 bne+ cr1,mapIns32a ; more lists to go
667 blr ; done
668
669
670/*
671 * *********************
672 * * m a p R e m o v e *
673 * *********************
674 *
675 * Remove a mapping from pmap skip-lists. The caller has already called mapSearchFull to
676 * find the mapping, which sets up the skipListPrev array with a vector of the previous
677 * ptrs for each skip list. When called:
678 * the pmap is locked (exclusive)
679 * translation is off, interrupts masked
680 * 64-bit mode is enabled (if on a 64-bit machine)
681 * mapSearchFull has just been called for this mappings key
682 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
683 * r3 = pmap ptr
684 * r4 = mapping ptr
685 *
686 * There is no return value. Except for cr6 (which is global), we trash nonvolatile regs.
687 */
688
689 .align 5
690 .globl EXT(mapRemove)
691LEXT(mapRemove)
692 lwz r8,mpFlags(r4) ; get this mappings flags
693 lbz r10,pmapCurLists(r3) ; get current #lists in use
694 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
695 mfsprg r12,0 ; get ptr to our per-proc
696 andi. r9,r8,mpLists ; get #lists this mapping is on (1<=n<=27)
697 slwi r8,r9,3 ; get #lists * 8
698 cmpw cr5,r9,r10 ; compare mpLists to pmapCurLists
699 la r12,skipListPrev+4(r12) ; r12 <-- base of prev ptr vector
700 bgt-- cr5,mapSkipListPanic ; die if mpLists > pmapCurLists
701 subi r8,r8,8 ; get offset to topmast (last) list this mapping is in
702 bf-- pf64Bitb,mapRem32a ; skip if 32-bit processor
703 subi r11,r11,4 ; we use all 64 bits of list links on 64-bit machines
704 subi r12,r12,4
705 b mapRem64a
706
707 ; 64-bit processor: loop over each list this mapping is on
708 ; r3 = pmap
709 ; r4 = mapping
710 ; r8 = offset to next list
711 ; r10 = pmapCurLists
712 ; r11 = ptr to base of mapping list vector
713 ; r12 = ptr to base of prev ptr vector in per-proc
714 ; cr5 = beq if (mpLists == pmapCurLists)
715
716 .align 5
717mapRem64a:
718 ldx r5,r8,r12 ; get prev ptr from per-proc vector
719 ldx r9,r8,r11 ; get next ptr from mapping
720 cmpwi cr1,r8,0 ; more to go?
721 la r7,mpList0(r5) ; get base of prev mappings list vector
722 stdx r9,r8,r7 ; point to next from prev
723 subi r8,r8,8 ; get next list offset
724 bne++ cr1,mapRem64a ; loop if another list to unlink from
725
726 ; Did we reduce #lists in use by removing last mapping in last list?
727
728 bnelr++ cr5 ; if (mpLists!=pmapCurLists) cannot have removed last map
729 la r5,pmapSkipLists(r3) ; point to vector of list hdrs
730mapRem64b:
731 subic. r10,r10,1 ; get base-0 list#
732 slwi r8,r10,3 ; get offset to last list
733 ldx r0,r8,r5 ; get last list ptr
734 cmpdi cr1,r0,0 ; null?
735 bnelr cr1 ; not null, so we are done
736 stb r10,pmapCurLists(r3) ; was null, so decrement pmapCurLists
737 bgt mapRem64b ; loop to see if more than one list was emptied
738 blr
739
740
741 ; 32-bit processor: loop over each list this mapping is on
742 ; r3 = pmap
743 ; r4 = mapping
744 ; r8 = offset to next list
745 ; r10 = pmapCurLists
746 ; r11 = ptr to base of mapping list vector
747 ; r12 = ptr to base of prev ptr vector in per-proc
748 ; cr5 = beq if (mpLists == pmapCurLists)
749
750 .align 4
751mapRem32a:
752 lwzx r5,r8,r12 ; get prev ptr from per-proc vector
753 lwzx r9,r8,r11 ; get next ptr from mapping
754 cmpwi cr1,r8,0 ; more to go?
755 la r7,mpList0+4(r5) ; get base of prev mappings list vector
756 stwx r9,r8,r7 ; point to next from prev
757 subi r8,r8,8 ; get next list offset
758 bne+ cr1,mapRem32a ; loop if another list to unlink from
759
760 ; Did we reduce #lists in use by removing last mapping in last list?
761
762 bnelr+ cr5 ; if (mpLists!=pmapCurLists) cannot have removed last map
763 la r5,pmapSkipLists+4(r3) ; point to vector of list hdrs
764mapRem32b:
765 subic. r10,r10,1 ; get base-0 list#
766 slwi r8,r10,3 ; get offset to last list
767 lwzx r0,r8,r5 ; get last list ptr
768 cmpwi cr1,r0,0 ; null?
769 bnelr cr1 ; not null, so we are done
770 stb r10,pmapCurLists(r3) ; was null, so decrement pmapCurLists
771 bgt mapRem32b ; loop to see if more than one list was emptied
772 blr
773
774
775/*
776 * *************************
777 * * m a p S e t L i s t s *
778 * *************************
779 *
780 * Called to decide how many skip-lists the next mapping will be on. For each pmap,
781 * we maintain a psuedo-random sequence based on a linear feedback shift register. The
782 * next number is generated by rotating the old value left by 1 and XORing with a
783 * polynomial (actually 4 8-bit polynomials concatanated) and adding 1.
784 * The simple (unclamped) number of lists a mapping is on is the number of trailing 0s
785 * in the pseudo-random sequence, shifted by the (log2-1) of the fanout F, plus one.
786 * This seems to give us a near perfect distribution, in the sense that about F times more nodes
787 * are allocated on n lists, as are on (n+1) lists.
788 *
789 * At one point we used a simple counter to assign lists. While this gave perfect
790 * distribution, there were certain access pattern that would drive a worst case
791 * distribution (e.g., insert low, then high, then low, etc.). Unfortunately,
792 * these patterns were not too uncommon. We changed to a less-than-perfect assignment,
793 * but one that works consistently across all known access patterns.
794 *
795 * Also, we modify the "simple" trailing-0-based list count, to account for an important
796 * observation: because VM does a lot of removing and restoring of mappings in the process of
797 * doing copy-on-write etc, it is common to have the pmap's "random number" (ie, the
798 * count of created mappings) be much larger than the number of mappings currently in the
799 * pmap. This means the simple list count will often be larger than justified by the number of
800 * mappings in the pmap. To avoid this common situation, we clamp the list count to be no more
801 * than ceil(logBaseF(pmapResidentCnt)).
802 *
803 * Finally, we also clamp the list count to kSkipListMaxLists.
804 *
805 * We are passed the pmap ptr in r3. Called with translation on, interrupts enabled,
806 * and in 32-bit mode.
807 */
808 .align 5
809 .globl EXT(mapSetLists)
810LEXT(mapSetLists)
811 lwz r5,pmapRandNum(r3) ; get the per-pmap counter of mapping creates
812 lwz r4,pmapResidentCnt(r3) ; get number of mappings in this pmap
813 lis r11,hi16(0xA7CBF5B9) ; Get polynomial (I just made this up...)
814 li r0,-1 ; get a mask of 1s
815 ori r11,r11,lo16(0xA7CBF5B9) ; Get polynomial (I just made this up...)
816 rlwinm r5,r5,1,0,31 ; Rotate
817 cntlzw r7,r4 ; get magnitude of pmapResidentCnt
818 xor r5,r5,r11 ; Munge with poly
819 srw r7,r0,r7 ; r7 <- mask for magnitude of pmapResidentCnt
820 addi r6,r5,1 ; increment pmapRandNum non-atomically
821 andc r8,r5,r6 ; get a mask for trailing zeroes in pmapRandNum
822 stw r6,pmapRandNum(r3) ; update "random number"
823 and r8,r8,r7 ; clamp trailing 0s to magnitude of pmapResidentCnt
824 rlwinm r8,r8,0,32-(kSkipListMaxLists*(kSkipListFanoutShift+1))+1,31 ; clamp to kSkipListMaxLists
825 cntlzw r9,r8 ; count leading 0s in the mask
826 subfic r10,r9,32 ; r10 <- trailing zero count
827 srwi r11,r10,kSkipListFanoutShift ; shift by 1 if fanout is 4, 2 if 8, etc
828 addi r3,r11,1 ; every mapping is on at least one list
829 blr
830
831
832/*
833 * *************************************
834 * * m a p S k i p L i s t V e r i f y *
835 * *************************************
836 *
837 * This does a fairly thorough sweep through a pmaps skip-list data structure, doing
838 * consistency checks. It is typically called (from hw_exceptions.s) from debug or
839 * instrumented builds. It is probably not a good idea to call this in production builds,
840 * as it must run with exceptions disabled and can take a long time to verify a big pmap.
841 * It runs in O(n*ln(n)).
842 *
843 * Called on a bl, with the pmap ptr in r20. We assume the pmap is locked (shared) and
844 * that EE and DR are off. We check all 64 bits of ptrs even on 32-bit machines.
845 * We use r20-r31, cr0, cr1, and cr7. If we return, no inconsistencies were found.
846 *
847 * You will notice we make little attempt to schedule the code; clarity is deemed more
848 * important than speed.
849 */
850
851
852 /*
853 * mapSkipListVerifyC is a version that is callable from C.
854 * This should be called only from the debugger, IT DOES NOT LOCK THE PMAP!!!!
855 */
856
857 .globl EXT(mapSkipListVerifyC)
858LEXT(mapSkipListVerifyC)
859
860 stwu r1,-(FM_ALIGN((31-13+1)*4)+FM_SIZE)(r1) ; Make some space on the stack
861 mflr r0 ; Save the link register
862 stmw r13,FM_ARG0(r1) ; Save all registers
863 stw r0,(FM_ALIGN((31-13+1)*4)+FM_SIZE+FM_LR_SAVE)(r1) ; Save the return
864
865 lwz r15,pmapvr(r3) ; Get the V to R translation
866 lwz r16,pmapvr+4(r3) ; Get the V to R translation
867 mr r19,r4 ; Save register dump area
868
869 bl EXT(mapSetUp) ; Get set up
870
871 mr r17,r11
872 xor r20,r3,r16 ; Translate 32-bit portion
873 bf-- pf64Bitb,mslvc32a ; Skip if 32-bit...
874
875 rldimi r20,r15,32,0 ; Shift the fixed upper part of the physical over and cram in top
876
877mslvc32a: lis r18,hi16(EXT(DebugWork))
878 ori r18,r18,lo16(EXT(DebugWork))
879 li r0,0x4262
880 stw r0,4(r18) ; Make sure the test knows to run
881
882 bl EXT(mapSkipListVerify) ; Run the test
883
884 li r0,0
885 stw r0,4(r18) ; Remove explicit call flag
886
887 bt++ pf64Bitb,mslvc64a ; This is 64-bit...
888
889 mtmsr r17 ; Restore enables/translation/etc.
890 isync
891
892 li r0,0
893 stw r0,0x000+0(r19)
894 stw r0,0x000+4(r19)
895 stw r0,0x008+0(r19)
896 stw r1,0x008+4(r19)
897 stw r0,0x010+0(r19)
898 stw r2,0x010+4(r19)
899 stw r0,0x018+0(r19)
900 stw r3,0x018+4(r19)
901 stw r0,0x020+0(r19)
902 stw r4,0x020+4(r19)
903 stw r0,0x028+0(r19)
904 stw r5,0x028+4(r19)
905 stw r0,0x030+0(r19)
906 stw r6,0x030+4(r19)
907 stw r0,0x038+0(r19)
908 stw r7,0x038+4(r19)
909 stw r0,0x040+0(r19)
910 stw r8,0x040+4(r19)
911 stw r0,0x048+0(r19)
912 stw r9,0x048+4(r19)
913 stw r0,0x050+0(r19)
914 stw r10,0x050+4(r19)
915 stw r0,0x058+0(r19)
916 stw r11,0x058+4(r19)
917 stw r0,0x060+0(r19)
918 stw r12,0x060+4(r19)
919 stw r0,0x068+0(r19)
920 stw r13,0x068+4(r19)
921 stw r0,0x070+0(r19)
922 stw r14,0x070+4(r19)
923 stw r0,0x078+0(r19)
924 stw r15,0x078+4(r19)
925 stw r0,0x080+0(r19)
926 stw r16,0x080+4(r19)
927 stw r0,0x088+0(r19)
928 stw r17,0x088+4(r19)
929 stw r0,0x090+0(r19)
930 stw r18,0x090+4(r19)
931 stw r0,0x098+0(r19)
932 stw r19,0x098+4(r19)
933 stw r0,0x0A0+0(r19)
934 stw r20,0x0A0+4(r19)
935 stw r0,0x0A8+0(r19)
936 stw r21,0x0A8+4(r19)
937 stw r0,0x0B0+0(r19)
938 stw r22,0x0B0+4(r19)
939 stw r0,0x0B8+0(r19)
940 stw r23,0x0B8+4(r19)
941 stw r0,0x0C0+0(r19)
942 stw r24,0x0C0+4(r19)
943 stw r0,0x0C8+0(r19)
944 stw r25,0x0C8+4(r19)
945 stw r0,0x0D0+0(r19)
946 stw r26,0x0D0+4(r19)
947 stw r0,0x0D8+0(r19)
948 stw r27,0x0D8+4(r19)
949 stw r0,0x0E0+0(r19)
950 stw r28,0x0E0+4(r19)
951 stw r0,0x0E8+0(r19)
952 stw r29,0x0E8+4(r19)
953 stw r0,0x0F0+0(r19)
954 stw r30,0x0F0+4(r19)
955 stw r0,0x0F8+0(r19)
956 stw r31,0x0F8+4(r19)
957
958 b mslvcreturn ; Join common...
959
960mslvc64a: mtmsrd r17 ; Restore enables/translation/etc.
961 isync
962
963 std r0,0x000(r19)
964 std r1,0x008(r19)
965 std r2,0x010(r19)
966 std r3,0x018(r19)
967 std r4,0x020(r19)
968 std r5,0x028(r19)
969 std r6,0x030(r19)
970 std r7,0x038(r19)
971 std r8,0x040(r19)
972 std r9,0x048(r19)
973 std r10,0x050(r19)
974 std r11,0x058(r19)
975 std r12,0x060(r19)
976 std r13,0x068(r19)
977 std r14,0x070(r19)
978 std r15,0x078(r19)
979 std r16,0x080(r19)
980 std r17,0x088(r19)
981 std r18,0x090(r19)
982 std r19,0x098(r19)
983 std r20,0x0A0(r19)
984 std r21,0x0A8(r19)
985 std r22,0x0B0(r19)
986 std r23,0x0B8(r19)
987 std r24,0x0C0(r19)
988 std r25,0x0C8(r19)
989 std r26,0x0D0(r19)
990 std r27,0x0D8(r19)
991 std r28,0x0E0(r19)
992 std r29,0x0E8(r19)
993 std r30,0x0F0(r19)
994 std r31,0x0F8(r19)
995
996
997mslvcreturn:
998 lwz r0,(FM_ALIGN((31-13+1)*4)+FM_SIZE+FM_LR_SAVE)(r1) ; Get the return
999 lmw r13,FM_ARG0(r1) ; Get the registers
1000 mtlr r0 ; Restore the return
1001 lwz r1,0(r1) ; Pop the stack
1002 blr
1003
1004
1005 .globl EXT(mapSkipListVerify)
1006LEXT(mapSkipListVerify)
1007 mflr r31 ; save LR so we can bl to mapVerifyDie
1008
1009 ; If we have already found an inconsistency and died, don not do so again, to
1010 ; avoid a loop.
1011
1012 lis r27,hi16(EXT(DebugWork))
1013 ori r27,r27,lo16(EXT(DebugWork))
1014 lwz r0,4(r27) ; Get the explicit entry flag
1015 lwz r27,0(r27) ; Get lockout
1016 cmplwi r0,0x4262 ; Should we run anyway?
1017 beq-- mslvAnyway ; Yes...
1018 cmpwi r27,0 ; have we already found an error?
1019 bnelr-- ; yes, just return wo checking again
1020
1021mslvAnyway:
1022 ; Not recursive call, so initialize.
1023
1024 mfsprg r23,2 ; get the feature flags
1025 mtcrf 0x02,r23 ; put pf64Bit where we can test it
1026 lbz r26,pmapCurLists(r20) ; get #lists that are in use
1027 lwz r21,pmapResidentCnt(r20); get #mappings in this pmap
1028 cmpwi r26,kSkipListMaxLists ; in range?
1029 bgtl-- mapVerifyDie ; pmapCurLists is too big
1030
1031 ; To prevent infinite loops, set limit of (pmapCurLists*pmapResidentCnt) iterations.
1032 ; Since we walk each list this is the max number of mappings we could visit.
1033
1034 li r23,0 ; initialize count
1035mapVer0:
1036 subic. r26,r26,1 ; loop pmapCurLists times (but at least once)
1037 add r23,r23,r21 ; compute (pmapCurLists*pmapResidentCnt)
1038 bgt mapVer0 ; this will be a 64-bit qty on 64-bit machines
1039
1040 li r22,kSkipListMaxLists ; initialize list#
1041 bf-- pf64Bitb,mapVer32 ; go handle a 32-bit processor
1042
1043 ; 64-bit machine.
1044 ;
1045 ; Loop over each list, counting mappings in each. We first check whether or not
1046 ; the list is empty (ie, if the pmapSlipLists ptr is null.) All lists above
1047 ; pmapCurLists should be empty, and no list at or below pmapCurLists should be.
1048 ; r20 = pmap ptr
1049 ; r21 = decrementing counter of mappings in this pmap
1050 ; r22 = next list# (1...kSkipListMaxLists)
1051 ; r23 = decrementing counter for infinite loop check
1052
1053mapVer64:
1054 slwi r25,r22,3 ; get offset to next skiplist
1055 la r26,pmapSkipLists(r20) ; get ptr to base of skiplist vector
1056 subi r25,r25,8
1057 ldx r26,r25,r26 ; get 1st mapping on this list, if any
1058 lbz r28,pmapCurLists(r20) ; get #lists in use
1059 cmpdi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1060 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1061 crxor cr0_eq,cr6_eq,cr7_gt ; cr0_eq <-- (null & !high) | (!null & high)
1062 beql-- mapVerifyDie ; die if this list is null when it should not be, etc
1063 b mapVer64g
1064
1065 ; Loop over each node in the list.
1066 ; r20 = pmap ptr
1067 ; r21 = decrementing counter of mappings in this pmap
1068 ; r22 = this list# (1...kSkipListMaxLists)
1069 ; r23 = decrementing counter for infinite loop check
1070 ; r25 = offset to this skiplist (ie, ((r22<<3)-8))
1071 ; r26 = mapping
1072
1073mapVer64a:
1074 lwz r29,mpFlags(r26) ; get bits for this mapping
1075 ld r28,mpVAddr(r26) ; get key
1076 subic. r23,r23,1 ; check for loops
1077 bltl-- mapVerifyDie ; we have visited > (pmapCurLists*pmapResidentCnt) nodes
1078 andi. r30,r26,mpBasicSize-1 ; test address for alignment
1079 bnel-- mapVerifyDie ; not aligned
1080 andi. r27,r29,mpLists ; get #lists this mapping is supposed to be on
1081 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1082 bltl-- cr1,mapVerifyDie ; mappings mpLists is too low
1083 cmpwi r27,kSkipListMaxLists ; too big?
1084 bgtl-- mapVerifyDie ; mappings mpLists > max
1085 rldicr r28,r28,0,51 ; clear low 12 bits of va
1086 bne++ cr1,mapVer64f ; jump if this is not highest list for this node
1087
1088 ; This is the "highest" (last) list this mapping is on.
1089 ; Do some additional checks (so we only do them once per mapping.)
1090 ; First, if a block mapping or nested pmap, compute block end.
1091
91447636
A		 1092 rlwinm r29,r29,0,mpType ; isolate mapping type code
1093 cmplwi r29,mpNest ; cr0_eq <- nested type?
1094 cmplwi cr1,r29,mpLinkage ; cr1_eq <- linkage type?
1095 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- linkage type or nested type?
1096 cmplwi cr1,r29,mpBlock ; cr1_eq <- block type?
1097 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
1098
55e303ae 1099 subi r21,r21,1 ; count mappings in this pmap
91447636 1100 bne++ mapVer64b ; not nested or pmap
55e303ae 1101 lhz r27,mpBSize(r26) ; get #pages or #segments
55e303ae 1102 sldi r29,r27,12 ; assume block mapping, units are (pages-1)
91447636 1103 beq cr1,mapVer64b ; guessed correctly
55e303ae
A		 1104 addi r27,r27,1 ; units of nested pmap are (#segs-1)
1105 sldi r29,r27,28 ; convert to #bytes
1106 subi r29,r29,4096 ; get offset to last byte in nested pmap
1107
1108 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1109
1110mapVer64b:
1111 add r24,r28,r29 ; r24 <- address of last valid page in this mapping
1112 la r28,mpList0(r26) ; get base of this mappings vector
1113 lwz r27,mpFlags(r26) ; Get the number of lists
1114 andi. r27,r27,mpLists ; get #lists this mapping is on (1<=n<=27)
1115 cmplwi r27,mpBasicLists ; Into bigger mapping?
1116 li r27,mpBasicLists*8-8 ; Assume normal
1117 ble+ mapVer64c ; It is...
1118 li r27,kSkipListMaxLists*8-8 ; initialize list offset for inner loop
1119
1120 ; Inner loop over each list link in this mappingss mpList vector.
1121 ; r24 = address of last valid page in this mapping
1122 ; r27 = offset for next list in inner loop
1123 ; r28 = base of this mappings list links
1124
1125mapVer64c:
1126 cmpw cr1,r27,r25 ; higher, lower, or same?
1127 ldx r29,r27,r28 ; get link to next mapping at this level
1128 mr. r29,r29 ; null?
1129 beq mapVer64d ; link null, which is always OK
1130 bgtl-- cr1,mapVerifyDie ; a mapping has a non-null list higher than its mpLists
1131 ld r30,mpVAddr(r29) ; get next mappings va
1132 rldicr r30,r30,0,51 ; zero low 12 bits
1133 cmpld r30,r24 ; compare next key with ours
1134 blel-- mapVerifyDie ; a next node has key <= to ours
1135mapVer64d:
1136 subic. r27,r27,8 ; move on to next list
1137 bne++ mapVer64c ; loop if more to go
1138
1139 ; Next node on current list, or next list if current done, or return if no more lists.
1140
1141mapVer64f:
1142 la r28,mpList0(r26) ; get base of this mappings vector
1143 ldx r26,r25,r28 ; get next mapping on this list
1144mapVer64g:
1145 mr. r26,r26 ; is there one?
1146 bne++ mapVer64a ; yes, handle
1147 subic. r22,r22,1 ; is there another list?
1148 bgt++ mapVer64 ; loop if so
1149
1150 cmpwi r21,0 ; did we find all the mappings in the pmap?
1151 bnel-- mapVerifyDie ; no
1152 mtlr r31 ; restore return address
1153 li r3,0
1154 blr
1155
1156
1157 ; Handle 32-bit machine.
1158
1159mapVer32:
1160 lwz r24,mpFlags(r20) ; Get number of lists
1161 la r30,pmapSkipLists(r20) ; first, check the pmap list hdrs
1162 andi. r24,r24,mpLists ; Clean the number of lists
1163 bl mapVerUpperWordsAre0 ; are the upper words of each list all 0?
1164
1165 ; Loop over each list, counting mappings in each. We first check whether or not
1166 ; the list is empty. All lists above pmapCurLists should be empty, and no list
1167 ; at or below pmapCurLists should be.
1168 ;
1169 ; r20 = pmap ptr
1170 ; r21 = decrementing counter of mappings in this pmap
1171 ; r22 = next list# (1...kSkipListMaxLists)
1172 ; r23 = decrementing counter for infinite loop check
1173
1174mapVer32NextList:
1175 lbz r28,pmapCurLists(r20) ; get #lists in use
1176 slwi r25,r22,3 ; get offset to next skiplist
1177 la r26,pmapSkipLists+4(r20) ; get ptr to base of skiplist vector
1178 subi r25,r25,8
1179 lwzx r26,r25,r26 ; get the 1st mapping on this list, or 0
1180 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1181 cmpwi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1182 crxor cr0_eq,cr6_eq,cr7_gt ; cr0_eq <-- (null & !high) | (!null & high)
1183 beql- mapVerifyDie ; die if this list is null when it should not be, etc
1184 b mapVer32g
1185
1186 ; Loop over each node in the list.
1187 ; r20 = pmap ptr
1188 ; r21 = decrementing counter of mappings in this pmap
1189 ; r22 = this list# (1...kSkipListMaxLists)
1190 ; r23 = decrementing counter for infinite loop check
1191 ; r25 = offset to this skiplist (ie, ((r22<<3)-8))
1192 ; r26 = mapping
1193
1194mapVer32a:
1195 lwz r29,mpFlags(r26) ; get bits for this mapping
1196 andi. r30,r26,mpBasicSize-1 ; test address for alignment
1197 lwz r24,mpVAddr+0(r26) ; get upper word of key
1198 bnel- mapVerifyDie ; mapping address not 64-byte aligned
1199 lwz r28,mpVAddr+4(r26) ; get lower word of key
1200 subic. r23,r23,1 ; check for loops
1201 bltl- mapVerifyDie ; we have visited > (pmapCurLists*pmapResidentCnt) nodes
1202 cmpwi r24,0 ; upper word of key (ie, va) should be 0
1203 bnel- mapVerifyDie ; was not
1204 andi. r27,r29,mpLists ; get #lists this mapping is supposed to be on
1205 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1206 bltl- cr1,mapVerifyDie ; mappings mpLists is too low
1207 cmpwi r27,kSkipListMaxLists ; too big?
1208 bgtl- mapVerifyDie ; mappings mpLists > max
1209 rlwinm r28,r28,0,0,19 ; clear low 12 bits of va
1210 bne+ cr1,mapVer32f ; jump if this is not highest list for this node
1211
1212 ; This is the "highest" (last) list this mapping is on.
1213 ; Do some additional checks (so we only do them once per mapping.)
1214 ; First, make sure upper words of the mpList vector are 0.
1215
1216 subi r21,r21,1 ; count mappings in this pmap
1217 lwz r24,mpFlags(r26) ; Get number of lists
1218 la r30,mpList0(r26) ; point to base of skiplist vector
1219 andi. r24,r24,mpLists ; Clean the number of lists
1220 bl mapVerUpperWordsAre0 ; make sure upper words are all 0 (uses r24 and r27)
1221
1222 ; Then, if a block mapping or nested pmap, compute block end.
1223
91447636
A		 1224 rlwinm r29,r29,0,mpType ; isolate mapping type code
1225 cmplwi cr1,r29,mpLinkage ; cr1_eq <- linkage type?
1226 cmplwi r29,mpNest ; cr0_eq <- nested type?
1227 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- linkage type or nested type?
1228 cmplwi cr1,r29,mpBlock ; cr1_eq <- block type?
1229 cror cr0_eq,cr1_eq,cr0_eq ; cr0_eq <- block or nested or linkage type?
1230
1231 bne+ mapVer32b ; not block or nested type
55e303ae 1232 lhz r27,mpBSize(r26) ; get #pages or #segments
55e303ae 1233 slwi r29,r27,12 ; assume block mapping, units are pages
91447636 1234 beq cr1,mapVer32b ; guessed correctly
55e303ae
A		 1235 addi r27,r27,1 ; units of nested pmap are (#segs-1)
1236 slwi r29,r27,28 ; convert to #bytes
1237 subi r29,r29,4096 ; get offset to last byte in nested pmap
1238
1239 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1240
1241mapVer32b:
1242 add r24,r28,r29 ; r24 <- address of last valid page in this mapping
1243 la r28,mpList0+4(r26) ; get base of this mappings vector
1244 lwz r27,mpFlags(r26) ; Get the number of lists
1245 andi. r27,r27,mpLists ; get #lists this mapping is on (1<=n<=27)
1246 cmplwi r27,mpBasicLists ; Into bigger mapping?
1247 li r27,mpBasicLists*8-8 ; Assume normal
1248 ble+ mapVer32c ; It is...
1249 li r27,kSkipListMaxLists*8-8 ; initialize list offset for inner loop
1250
1251 ; Inner loop over each list in this mappings mpList vector.
1252 ; r24 = address of last valid page in this mapping
1253 ; r27 = offset for next list in inner loop
1254 ; r28 = base of this mappings list links
1255
1256mapVer32c:
1257 cmpw cr1,r27,r25 ; higher, lower, or same?
1258 lwzx r29,r27,r28 ; get link to next mapping at this level
1259 mr. r29,r29 ; null?
1260 beq mapVer32d ; link null, which is always OK
1261
1262
1263 bgtl- cr1,mapVerifyDie ; a mapping has a non-null list higher than its mpLists
1264 lwz r30,mpVAddr+4(r29) ; get next mappings va
1265 rlwinm r30,r30,0,0,19 ; zero low 12 bits
1266 cmplw r30,r24 ; compare next key with ours
1267 blel- mapVerifyDie ; a next node has key <= to ours
1268mapVer32d:
1269 subic. r27,r27,8 ; move on to next list
1270 bne+ mapVer32c ; loop if more to go
1271
1272 ; Next node on current list, or next list if current done, or return if no more lists.
1273
1274mapVer32f:
1275 la r28,mpList0+4(r26) ; get base of this mappings vector again
1276 lwzx r26,r25,r28 ; get next mapping on this list
1277mapVer32g:
1278 mr. r26,r26 ; is there one?
1279 bne+ mapVer32a ; yes, handle
1280 subic. r22,r22,1 ; is there another list?
1281 bgt+ mapVer32NextList ; loop if so
1282
1283 cmpwi r21,0 ; did we find all the mappings in the pmap?
1284 bnel- mapVerifyDie ; no
1285 mtlr r31 ; restore return address
1286 li r3,0
1287 blr
1288
1289 ; Subroutine to verify that the upper words of a vector of kSkipListMaxLists
1290 ; doublewords are 0.
1291 ; r30 = ptr to base of vector
1292 ; Uses r24 and r27.
1293
1294mapVerUpperWordsAre0:
1295 cmplwi r24,mpBasicLists ; Do we have more than basic?
1296 li r24,mpBasicLists*8 ; Assume basic
1297 ble++ mapVerUpper1 ; We have the basic size
1298 li r24,kSkipListMaxLists*8 ; Use max size
1299
1300mapVerUpper1:
1301 subic. r24,r24,8 ; get offset to next doubleword
1302 lwzx r27,r24,r30 ; get upper word
1303 cmpwi cr1,r27,0 ; 0 ?
1304 bne- cr1,mapVerifyDie ; die if not, passing callers LR
1305 bgt+ mapVerUpper1 ; loop if more to go
1306 blr
1307
1308 ; bl here if mapSkipListVerify detects an inconsistency.
1309
1310mapVerifyDie:
1311 mflr r3
1312 mtlr r31 ; Restore return
1313 lis r31,hi16(EXT(DebugWork))
1314 ori r31,r31,lo16(EXT(DebugWork))
1315 lwz r0,4(r31) ; Get the explicit entry flag
1316 cmplwi r0,0x4262 ; Should we run anyway?
1317 beqlr-- ; Explicit call, return...
1318
1319 li r0,1
1320 stw r0,0(r31) ; Lock out further calls
1321 BREAKPOINT_TRAP ; hopefully, enter debugger
1322 b .-4
1323
1324
1325/*
1326 * Panic (choke, to be exact) because of messed up skip lists. The LR points back
1327 * to the original caller of the skip-list function.
1328 */
1329
1330mapSkipListPanic: ; skip-lists are screwed up
1331 lis r0,hi16(Choke)
1332 ori r0,r0,lo16(Choke)
1333 li r3,failSkipLists ; get choke code
1334 sc ; choke
1335 b .-4
1336
1337
mirror of XNU