Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/osfmk/ppc/skiplists.s
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * Copyright (c) 2002-2004 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 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. 11 * 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 14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 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. 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) 98 LEXT(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 127 mapSrch64a: ; 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 137 mapSrch64c: 138 mr. r3,r3 ; was there another mapping on current list? 139 bne++ mapSrch64a ; was another, so loop 140 mapSrch64d: 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 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 172 173 ; found the mapping 174 ; r2 = count of nodes visited 175 ; r3 = the mapping 176 ; r6 = pmap ptr 177 178 mapSrch64Found: ; 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 188 mapSrch64Exit: ; 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 215 mapSrch32a: ; 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 225 mapSrch32c: 226 mr. r3,r3 ; was there another mapping on current list? 227 bne+ mapSrch32a ; was another, so loop 228 mapSrch32d: 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 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 260 261 ; found the mapping 262 ; r2 = count of nodes visited 263 ; r3 = the mapping 264 ; r6 = pmap ptr 265 266 mapSrch32Found: ; 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 275 mapSrch32Exit: 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 297 mapSrchPmapEmpty: 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) 333 LEXT(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) 365 ; r10 = lowest expected next va, 0 at the beginning of the search 366 ; r12 = ptr to the skipListPrev vector in the per-proc 367 368 .align 5 369 mapSrchFull64a: ; loop over each mapping 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 380 rldicr r4,r4,0,51 ; zero low 12 bits of mapping va 381 addic. r0,r11,-4096 ; get offset last page in mapping (set cr0_eq if 1 page) 382 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 386 387 blt cr1,mapSrchFull64d ; key is less, try next list 388 beq cr1,mapSrchFull64Found ; this is the correct mapping 389 bne-- cr0,mapSrchFull64e ; handle mapping larger than one page 390 mapSrchFull64b: 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 394 addi r10,r4,0x1000 ; Get the lowest VA we can get next 395 mapSrchFull64c: 396 mr. r3,r3 ; was there another mapping on current list? 397 bne++ mapSrchFull64a ; was another, so loop 398 mapSrchFull64d: 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 414 mapSrchFull64e: 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 430 mapSrchFull64Found: ; 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) 448 ; r10 = lowest expected next va, 0 at the beginning of the search 449 ; r12 = ptr to the skipListPrev vector in the per-proc 450 451 .align 4 452 mapSrchFull32a: ; loop over each mapping 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) 465 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 473 mapSrchFull32b: 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 477 addi r10,r4,0x1000 ; Get the lowest VA we can get next 478 mapSrchFull32c: 479 mr. r3,r3 ; next becomes current 480 bne+ mapSrchFull32a ; was another, so loop 481 mapSrchFull32d: 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 497 mapSrchFull32e: 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 512 mapSrchFull32Found: ; 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) 544 LEXT(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 572 mapIns64NewList: 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 589 mapIns64a: 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 605 mapIns32: 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 613 mapIns32NewList: 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 630 mapIns32a: 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) 663 LEXT(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 689 mapRem64a: 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 702 mapRem64b: 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 723 mapRem32a: 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 736 mapRem32b: 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) 782 LEXT(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) 830 LEXT(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 849 mslvc32a: 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 932 mslvc64a: 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 969 mslvcreturn: 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) 978 LEXT(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 993 mslvAnyway: 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 1007 mapVer0: 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 1025 mapVer64: 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 1045 mapVer64a: 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 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 1072 1073 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page. 1074 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 1089 mapVer64c: 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 1099 mapVer64d: 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 1105 mapVer64f: 1106 la r28,mpList0(r26) ; get base of this mappings vector 1107 ldx r26,r25,r28 ; get next mapping on this list 1108 mapVer64g: 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 1123 mapVer32: 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 1138 mapVer32NextList: 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 1158 mapVer32a: 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 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 1189 lwz r24,mpFlags(r26) ; Get number of lists 1190 la r30,mpList0(r26) ; point to base of skiplist vector 1191 andi. r24,r24,mpLists ; Clean the number of lists 1192 bl mapVerUpperWordsAre0 ; make sure upper words are all 0 (uses r24 and r27) 1193 1194 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page. 1195 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 1210 mapVer32c: 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 1222 mapVer32d: 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 1228 mapVer32f: 1229 la r28,mpList0+4(r26) ; get base of this mappings vector again 1230 lwzx r26,r25,r28 ; get next mapping on this list 1231 mapVer32g: 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 1248 mapVerUpperWordsAre0: 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 1254 mapVerUpper1: 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 1264 mapVerifyDie: 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 1284 mapSkipListPanic: ; 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
Cache object: 9781b48c4ddf15668315ca6aca832f6b
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]