Lines Matching refs:of
6 * This file contains Original Code and/or Modifications of Original Code
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
15 * Please obtain a copy of the License at
37 * in increasing order by virtual address. The number of lists a mapping is on is an
41 * "fanout." With a max of n lists, up to F**n nodes can be handled optimally.
44 * Because the first skip-list is just a sorted list of all mappings, it is also
45 * efficient to purge a sparsely populated pmap of all the mappings in a large range,
47 * primary advantage of skip-lists over a hash, btw.
49 * We currently use a fanout of 4 and a maximum of 12 lists (cf kSkipListFanoutShift
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
55 * 64-bit link fields in every mapping. So we currently have two sizes of mappings:
58 * In practice, the additional complexity of the variable node size is entirely
93 * r4 = high 32 bits of key to search for (0 if a 32-bit processor)
94 * r5 = low 32 bits of key (low 12 bits may be nonzero garbage)
107 rlwinm r5,r5,0,0,19 ; zero low 12 bits of key
110 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
111 li r2,0 ; initialize count of mappings visited
112 slwi r7,r7,3 ; get offset of last list in use
116 subi r8,r8,4 ; we use all 64 bits of ptrs
123 ; r2 = count of mappings visited so far
125 ; r4 = va of current mapping (ie, of r3)
129 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
136 rldicr r4,r4,0,51 ; zero low 12 bits of mapping va
153 ; Note the advantage of keeping the check for block mappings (and nested pmaps)
154 ; out of the inner loop; we do the special case work at most once per search, and
155 ; never for the most-common case of finding a scalar mapping. The full searches
166 ld r10,mpVAddr(r9) ; re-fetch base address of prev ptr
167 ori r0,r0,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
172 rldicr r10,r10,0,51 ; zero low 12 bits of mapping va
180 ; r2 = count of nodes visited
188 ; r2 = count of nodes visited
205 lwz r5,mpVAddr+4(r4) ; get VA of next node
211 ; r2 = count of mappings visited so far
213 ; r4 = va of current mapping (ie, of r3)
217 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
224 rlwinm r4,r4,0,0,19 ; zero low 12 bits of mapping va
241 ; Note the advantage of keeping the check for block mappings (and nested pmaps)
242 ; out of the inner loop; we do the special case work at most once per search, and
243 ; never for the most-common case of finding a scalar mapping. The full searches
252 lwz r10,mpVAddr+4(r9) ; re-fetch base address of prev ptr
256 ori r0,r0,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
260 rlwinm r10,r10,0,0,19 ; zero low 12 bits of block mapping va
261 subi r0,r11,4096 ; get address of last page in submap
268 ; r2 = count of nodes visited
275 ; r2 = count of nodes visited
295 lwz r5,mpVAddr+4(r4) ; get VA of next node
305 li r4,0 ; return 0 as virtual address of next node
321 * This is the "full" call, that sets up a vector of ptrs to the previous node
329 * r4 = high 32 bits of key to search for (0 if a 32-bit processor)
330 * r5 = low 32 bits of key (low 12 bits may be nonzero garbage)
342 rlwinm r5,r5,0,0,19 ; zero low 12 bits of key
344 li r2,0 ; initialize count of mappings visited
347 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
349 slwi r7,r7,3 ; get (offset*8) of last list
350 la r12,skipListPrev+4(r12) ; point to vector of prev ptrs, assuming 32-bit machine
355 subi r8,r8,4 ; we use all 64 bits of ptrs
363 ; r2 = count of mappings visited so far
365 ; r4 = va of current mapping (ie, of r3)
369 ; r8 = ptr to skip list vector of mapping pointed to by r9
371 ; r10 = lowest expected next va, 0 at the beginning of the search
383 ori r0,r0,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
386 rldicr r4,r4,0,51 ; zero low 12 bits of mapping va
391 bgt-- cr5,mapSkipListPanic ; die if keys are out of order
417 ; Block mapping or nested pmap, and key > base. We must compute the va of
418 ; the end of the block to see if key fits within it.
423 bgt mapSrchFull64b ; no, try next mapping (r4 is advanced to end of range)
427 ; r2 = count of nodes visited
447 ; r2 = count of nodes visited
452 ; r8 = ptr to skip list vector of mapping pointed to by r9
454 ; r10 = lowest expected next va, 0 at the beginning of the search
466 ori r0,r0,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
469 rlwinm r4,r4,0,0,19 ; zero low 12 bits of mapping va
474 bgt- cr0,mapSkipListPanic ; die if keys are out of order
500 ; Block mapping or nested pmap, and key > base. We must compute the va of
501 ; the end of the block to see if our key fits within it.
510 ; r2 = count of nodes visited
535 * of calling mapSearchFull, the per-proc skipListPrev array is set up with a vector of the
553 la r10,pmapSkipLists+4(r3) ; r10 <-- base of pmap list headers, assuming 32-bit machine
554 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
557 la r12,skipListPrev+4(r12) ; r12 <-- base of prev ptr vector
562 subi r10,r10,4 ; we use all 8 bytes of the ptr fields
574 mtctr r6 ; set up count of new lists
590 ; r10 = ptr to base of pmap list header vector
591 ; r11 = ptr to base of new mappings list vector
592 ; r12 = ptr to base of prev ptr vector in per-proc
598 la r7,mpList0(r5) ; get base of prev mappings list vector
600 stdx r4,r8,r7 ; * insert new mapping in middle of this list
615 mtctr r6 ; set up count of new lists
631 ; r10 = ptr to base of pmap list header vector
632 ; r11 = ptr to base of new mappings list vector
633 ; r12 = ptr to base of prev ptr vector
639 la r7,mpList0+4(r5) ; get base of prev mappings list vector
641 stwx r4,r8,r7 ; * insert new mapping in middle of this list
654 * find the mapping, which sets up the skipListPrev array with a vector of the previous
672 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
677 la r12,skipListPrev+4(r12) ; r12 <-- base of prev ptr vector
681 subi r11,r11,4 ; we use all 64 bits of list links on 64-bit machines
690 ; r11 = ptr to base of mapping list vector
691 ; r12 = ptr to base of prev ptr vector in per-proc
699 la r7,mpList0(r5) ; get base of prev mappings list vector
707 la r5,pmapSkipLists(r3) ; point to vector of list hdrs
724 ; r11 = ptr to base of mapping list vector
725 ; r12 = ptr to base of prev ptr vector in per-proc
733 la r7,mpList0+4(r5) ; get base of prev mappings list vector
741 la r5,pmapSkipLists+4(r3) ; point to vector of list hdrs
762 * The simple (unclamped) number of lists a mapping is on is the number of trailing 0s
763 * in the pseudo-random sequence, shifted by the (log2-1) of the fanout F, plus one.
774 * observation: because VM does a lot of removing and restoring of mappings in the process of
776 * count of created mappings) be much larger than the number of mappings currently in the
777 * pmap. This means the simple list count will often be larger than justified by the number of
789 lwz r5,pmapRandNum(r3) ; get the per-pmap counter of mapping creates
790 lwz r4,pmapResidentCnt(r3) ; get number of mappings in this pmap
792 li r0,-1 ; get a mask of 1s
795 cntlzw r7,r4 ; get magnitude of pmapResidentCnt
797 srw r7,r0,r7 ; r7 <- mask for magnitude of pmapResidentCnt
801 and r8,r8,r7 ; clamp trailing 0s to magnitude of pmapResidentCnt
822 * that EE and DR are off. We check all 64 bits of ptrs even on 32-bit machines.
853 rldimi r20,r15,32,0 ; Shift the fixed upper part of the physical over and cram in top
1009 ; To prevent infinite loops, set limit of (pmapCurLists*pmapResidentCnt) iterations.
1010 ; Since we walk each list this is the max number of mappings we could visit.
1027 ; r21 = decrementing counter of mappings in this pmap
1033 la r26,pmapSkipLists(r20) ; get ptr to base of skiplist vector
1045 ; r21 = decrementing counter of mappings in this pmap
1063 rldicr r28,r28,0,51 ; clear low 12 bits of va
1072 addi r27,r27,1 ; units of nested pmap are (#segs-1)
1073 ori r29,r29,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
1079 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1081 add r24,r28,r29 ; r24 <- address of last valid page in this mapping
1082 la r28,mpList0(r26) ; get base of this mappings vector
1083 lwz r27,mpFlags(r26) ; Get the number of lists
1091 ; r24 = address of last valid page in this mapping
1093 ; r28 = base of this mappings list links
1112 la r28,mpList0(r26) ; get base of this mappings vector
1130 lwz r24,mpFlags(r20) ; Get number of lists
1132 andi. r24,r24,mpLists ; Clean the number of lists
1133 bl mapVerUpperWordsAre0 ; are the upper words of each list all 0?
1140 ; r21 = decrementing counter of mappings in this pmap
1147 la r26,pmapSkipLists+4(r20) ; get ptr to base of skiplist vector
1158 ; r21 = decrementing counter of mappings in this pmap
1167 lwz r24,mpVAddr+0(r26) ; get upper word of key
1169 lwz r28,mpVAddr+4(r26) ; get lower word of key
1172 cmpwi r24,0 ; upper word of key (ie, va) should be 0
1179 rlwinm r28,r28,0,0,19 ; clear low 12 bits of va
1184 ; First, make sure upper words of the mpList vector are 0.
1188 addi r27,r27,1 ; units of nested pmap are (#segs-1)
1189 ori r29,r29,0x3216 ; OR in 0x00003216 (0x3200 and a base rotate of 22)
1195 lwz r24,mpFlags(r26) ; Get number of lists
1196 la r30,mpList0(r26) ; point to base of skiplist vector
1197 andi. r24,r24,mpLists ; Clean the number of lists
1200 ; Here with r29 = size of block - 4k, or 0 if mapping is a scalar page.
1202 add r24,r28,r29 ; r24 <- address of last valid page in this mapping
1203 la r28,mpList0+4(r26) ; get base of this mappings vector
1204 lwz r27,mpFlags(r26) ; Get the number of lists
1212 ; r24 = address of last valid page in this mapping
1214 ; r28 = base of this mappings list links
1235 la r28,mpList0+4(r26) ; get base of this mappings vector again
1249 ; Subroutine to verify that the upper words of a vector of kSkipListMaxLists
1251 ; r30 = ptr to base of vector
1286 * Panic (choke, to be exact) because of messed up skip lists. The LR points back
1287 * to the original caller of the skip-list function.