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