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