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