Lines Matching refs:is
36 * The basic idea is that each mapping is on one or more singly-linked lists, sorted
37 * in increasing order by virtual address. The number of lists a mapping is on is an
38 * invariant property determined when the mapping is created, using an exponentially-
39 * distributed random number. Every mapping is on the first list. Ideally, each
40 * successive list has only 1/F as many nodes on it as the previous, where F is the
44 * Because the first skip-list is just a sorted list of all mappings, it is also
51 * pages, which is 64GB of resident physical memory per pmap. Pmaps can be larger than
54 * The major problem with skip-lists is that we could waste a lot of space with 12
57 * (4**4)==256 mappings requires the larger node, so the average size is 64.25 bytes.
58 * In practice, the additional complexity of the variable node size is entirely
61 * The other, mostly theoretic problem with skip-lists is that they have worst cases
63 * is no practical way to prevent them.
86 * This is the fast call, that does not set up the previous-ptr vector or make
88 * the pmap is locked (shared or exclusive)
89 * translation is off, interrupts masked
90 * 64-bit mode is enabled (if on a 64-bit machine)
91 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
98 * Except for cr6 (which is global), we trash nonvolatile regs. Called both on 32- and 64-bit
105 lbz r7,pmapCurLists(r3) ; get largest #lists any mapping is on
138 blt cr1,mapSrch64d ; key is less, try next list
141 beq-- cr1,mapSrch64Found ; this is the correct mapping
152 ; If not, or if our address is not covered by the block or nested map, return 0.
160 ld r4,pmapSkipLists(r6) ; assume prev ptr null... so next is first
226 blt cr1,mapSrch32d ; key is less, try next list
229 beq- cr1,mapSrch32Found ; this is the correct mapping
240 ; If not, or if our address is not covered by the block or nested map, return 0.
248 lwz r4,pmapSkipLists+4(r6) ; assume prev ptr null... so next is first
299 ; Here when the pmap is empty (ie, pmapCurLists==0), both in 32 and 64-bit mode,
321 * This is the "full" call, that sets up a vector of ptrs to the previous node
322 * (or to the pmap, if there is no previous node) for each list that the mapping
324 * the pmap is locked (shared or exclusive)
325 * translation is off, interrupts masked
326 * 64-bit mode is enabled (if on a 64-bit machine)
327 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
333 * Except for cr6 (which is global), we trash nonvolatile regs. Called both on 32- and 64-bit
340 lbz r7,pmapCurLists(r3) ; get largest #lists any mapping is on
393 blt cr1,mapSrchFull64d ; key is less, try next list
394 beq cr1,mapSrchFull64Found ; this is the correct mapping
423 bgt mapSrchFull64b ; no, try next mapping (r4 is advanced to end of range)
476 blt cr1,mapSrchFull32d ; key is less than this va, try next list
477 beq cr1,mapSrchFull32Found ; this is the correct mapping
535 * of calling mapSearchFull, the per-proc skipListPrev array is set up with a vector of the
537 * the pmap is locked (exclusive)
538 * translation is off, interrupts masked
539 * 64-bit mode is enabled (if on a 64-bit machine)
541 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
545 * There is no return value. Except for cr6 (which is global), we trash nonvolatile regs.
552 lbz r7,pmapCurLists(r3) ; get current max# lists any mapping is on
556 andi. r9,r8,mpLists ; get #lists this mapping is on (1<=n<=27)
558 sub. r6,r9,r7 ; is this mapping on more lists than any other?
577 bgt-- mapSkipListPanic ; choke if this mapping is on too many lists
587 ; 64-bit processor: loop over each list this mapping is on
606 ; Handle 32-bit processor. First, increase pmapCurLists if necessary; cr0 is bgt
618 bgt- mapSkipListPanic ; choke if this mapping is on too many lists
628 ; 32-bit processor: loop over each list this mapping is on
656 * the pmap is locked (exclusive)
657 * translation is off, interrupts masked
658 * 64-bit mode is enabled (if on a 64-bit machine)
660 * cr6 is loaded with the corresponding feature flags (in particular, pf64Bit)
664 * There is no return value. Except for cr6 (which is global), we trash nonvolatile regs.
674 andi. r9,r8,mpLists ; get #lists this mapping is on (1<=n<=27)
679 subi r8,r8,8 ; get offset to topmast (last) list this mapping is in
685 ; 64-bit processor: loop over each list this mapping is on
719 ; 32-bit processor: loop over each list this mapping is on
760 * next number is generated by rotating the old value left by 1 and XORing with a
762 * The simple (unclamped) number of lists a mapping is on is the number of trailing 0s
775 * doing copy-on-write etc, it is common to have the pmap's "random number" (ie, the
805 srwi r11,r10,kSkipListFanoutShift ; shift by 1 if fanout is 4, 2 if 8, etc
806 addi r3,r11,1 ; every mapping is on at least one list
816 * consistency checks. It is typically called (from hw_exceptions.s) from debug or
817 * instrumented builds. It is probably not a good idea to call this in production builds,
821 * Called on a bl, with the pmap ptr in r20. We assume the pmap is locked (shared) and
825 * You will notice we make little attempt to schedule the code; clarity is deemed more
831 * mapSkipListVerifyC is a version that is callable from C.
865 bt++ pf64Bitb,mslvc64a ; This is 64-bit...
1007 bgtl-- mapVerifyDie ; pmapCurLists is too big
1010 ; Since we walk each list this is the max number of mappings we could visit.
1024 ; the list is empty (ie, if the pmapSlipLists ptr is null.) All lists above
1037 cmpdi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1038 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1040 beql-- mapVerifyDie ; die if this list is null when it should not be, etc
1058 andi. r27,r29,mpLists ; get #lists this mapping is supposed to be on
1059 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1060 bltl-- cr1,mapVerifyDie ; mappings mpLists is too low
1064 bne++ cr1,mapVer64f ; jump if this is not highest list for this node
1066 ; This is the "highest" (last) list this mapping is on.
1079 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1084 andi. r27,r27,mpLists ; get #lists this mapping is on (1<=n<=27)
1087 ble+ mapVer64c ; It is...
1099 beq mapVer64d ; link null, which is always OK
1115 mr. r26,r26 ; is there one?
1117 subic. r22,r22,1 ; is there another list?
1136 ; the list is empty. All lists above pmapCurLists should be empty, and no list
1150 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1151 cmpwi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1153 beql- mapVerifyDie ; die if this list is null when it should not be, etc
1174 andi. r27,r29,mpLists ; get #lists this mapping is supposed to be on
1175 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1176 bltl- cr1,mapVerifyDie ; mappings mpLists is too low
1180 bne+ cr1,mapVer32f ; jump if this is not highest list for this node
1182 ; This is the "highest" (last) list this mapping is on.
1200 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1205 andi. r27,r27,mpLists ; get #lists this mapping is on (1<=n<=27)
1208 ble+ mapVer32c ; It is...
1220 beq mapVer32d ; link null, which is always OK
1238 mr. r26,r26 ; is there one?
1240 subic. r22,r22,1 ; is there another list?