![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to htab.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / machdep / ppc|
Return to htab.c CVS log | Up to [Apple Darwin 0.x] / kernel / machdep / ppc |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: * Copyright 1996 1995 by Open Software Foundation, Inc. 1997 1996 1995 1994 1993 1992 1991
27: * All Rights Reserved
28: *
29: * Permission to use, copy, modify, and distribute this software and
30: * its documentation for any purpose and without fee is hereby granted,
31: * provided that the above copyright notice appears in all copies and
32: * that both the copyright notice and this permission notice appear in
33: * supporting documentation.
34: *
35: * OSF DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE
36: * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
37: * FOR A PARTICULAR PURPOSE.
38: *
39: * IN NO EVENT SHALL OSF BE LIABLE FOR ANY SPECIAL, INDIRECT, OR
40: * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
41: * LOSS OF USE, DATA OR PROFITS, WHETHER IN ACTION OF CONTRACT,
42: * NEGLIGENCE, OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
43: * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
44: */
45: /*
46: * MKLINUX-1.0DR2
47: */
48:
49: /* A marvelous selection of support routines for virtual memory */
50:
51:
52: #include <debug.h>
53: #include <mach_vm_debug.h>
54:
55: #include <kern/thread.h>
56: #include <mach/vm_attributes.h>
57: #include <mach/vm_param.h>
58: #include <kernserv/machine/spl.h>
59:
60: /*#include <kern/misc_protos.h>*/
61: /*#include <ppc/misc_protos.h>*/
62: /*#include <ppc/gdb_defs.h> /* for kgdb_kernel_in_pmap used in assert */
63: #include <machdep/ppc/proc_reg.h>
64: #include <machdep/ppc/mem.h>
65: #include <machdep/ppc/pmap.h>
66: #include <machdep/ppc/pmap_internals.h>
67:
68: /* [email protected] 2/12/97 */
69: #define NULL ((void *) 0)
70:
71: /* These refer to physical addresses and are set and referenced elsewhere */
72:
73: unsigned int hash_table_base;
74: unsigned int hash_table_size;
75:
76: unsigned int hash_function_mask;
77:
78: /* Prototypes for static functions */
79:
80: static pte_t *find_pte_in_pteg(pte_t* pte, unsigned int match);
81:
82: #if MACH_VM_DEBUG
83: #define DPRINTF(x) kprintf(x)
84: #else /* MACH_VM_DEBUG */
85: #define DPRINTF(x)
86: #endif /* MACH_VM_DEBUG */
87:
88: /* gather statistics about hash table usage */
89:
90: #if DEBUG
91: #define MEM_STATS 1
92: #else
93: #define MEM_STATS 0
94: #endif /* DEBUG */
95:
96: #if MEM_STATS
97: /* hash table usage information */
98: struct hash_table_stats {
99: int find_pte_in_pteg_calls;
100: int find_pte_in_pteg_not_found;
101: int find_pte_in_pteg_location[8];
102: struct find_or_alloc_calls {
103: int found_primary;
104: int found_secondary;
105: int alloc_primary;
106: int alloc_secondary;
107: int overflow;
108: int not_found;
109: } find_or_alloc_calls[2];
110:
111: } hash_table_stats;
112: #endif /* MEM_STATS */
113:
114: /* Set up the machine registers for the given hash table.
115: * The table has already been zeroed.
116: */
117:
118: void hash_table_init(unsigned int base, unsigned int size)
119: {
120: register pte_t* pte;
121: unsigned int mask;
122: int i;
123:
124: #if MACH_VM_DEBUG
125: if (size % (64*1024)) {
126: DPRINTF(("ERROR! size = 0x%x\n",size));
127: enterDebugger("FATAL");
128: }
129: if (base % size) {
130: DPRINTF(("ERROR! base not multiple of size\n"));
131: DPRINTF(("base = 0x%08x, size=%dK \n",base,size/1024));
132: enterDebugger("FATAL");
133: }
134: #endif
135:
136: #if PTE_EMPTY != 0
137: /* We do not use zero values for marking empty PTE slots. This
138: * initialisation could be sped up, but it's only called once.
139: * the hash table has already been bzeroed.
140: */
141: for (pte = (pte_t *) base; (unsigned int)pte < (base+size); pte++) {
142: pte->pte0.word = PTE_EMPTY;
143: }
144: #endif /* PTE_EMPTY != 0 */
145:
146: mask = 0;
147: for (i = 1; i < (size >> 16); i *= 2)
148: mask = (mask << 1) | 1;
149:
150: mtsdr1(hash_table_base | mask);
151:
152: isync();
153:
154: hash_function_mask = (mask << 16) | 0xFFC0;
155: }
156:
157: /* Given the address of a pteg and the pte0 to match, this returns
158: * the address of the matching pte or PTE_NULL. Can be used to search
159: * for an empty pte by using PTE_EMPTY as the matching parameter.
160: */
161:
162: static __inline__ pte_t *
163: find_pte_in_pteg(pte_t* pte, unsigned int match)
164: {
165: register int i;
166:
167: #if MEM_STATS
168: hash_table_stats.find_pte_in_pteg_calls++;
169: #define INC_STAT(LOC) hash_table_stats.find_pte_in_pteg_location[LOC]++
170: #else /* MEM_STATS */
171: #define INC_STAT(LOC)
172: #endif /* MEM_STATS */
173:
174: /* unrolled for speed */
175: if (pte[0].pte0.word == match) { INC_STAT(0); return &pte[0]; }
176: if (pte[1].pte0.word == match) { INC_STAT(1); return &pte[1]; }
177: if (pte[2].pte0.word == match) { INC_STAT(2); return &pte[2]; }
178: if (pte[3].pte0.word == match) { INC_STAT(3); return &pte[3]; }
179: if (pte[4].pte0.word == match) { INC_STAT(4); return &pte[4]; }
180: if (pte[5].pte0.word == match) { INC_STAT(5); return &pte[5]; }
181: if (pte[6].pte0.word == match) { INC_STAT(6); return &pte[6]; }
182: if (pte[7].pte0.word == match) { INC_STAT(7); return &pte[7]; }
183:
184: #if MEM_STATS
185: hash_table_stats.find_pte_in_pteg_not_found++;
186: #endif /* MEM_STATS */
187: return PTE_NULL;
188: }
189:
190: /* Given a space identifier and a virtual address, this returns the
191: * address of the pte describing this virtual page.
192: *
193: * If allocate is FALSE, the function will return PTE_NULL if not found
194: *
195: * If allocate is TRUE the function will create a new PTE entry marked
196: * as invalid with only pte0 set up (ie no physical info or
197: * protection/change info)
198: */
199:
200: pte_t *
201: find_or_allocate_pte(space_t sid, vm_offset_t v_addr, boolean_t allocate)
202: {
203: register vm_offset_t primary_hash, secondary_hash;
204: register pte0_t primary_match, secondary_match;
205: register pte_t *pte;
206: register unsigned int segment_id;
207:
208: /* Horrible hack "(union *)&var-> " to retype to union */
209: segment_id = (sid << 4) | (v_addr >> 28);
210:
211: primary_hash = segment_id ^ ((va_full_t *)&v_addr)->page_index;
212:
213: primary_hash = hash_table_base +
214: ((primary_hash << 6) & hash_function_mask);
215:
216: /* Firstly check out the primary pteg */
217:
218: #if 0 && MACH_VM_DEBUG
219: if (sid) {
220: DPRINTF(("PRIMARY HASH OF SID 0x%x and addr 0x%x = 0x%x**********\n",
221: sid, v_addr, primary_hash));
222: }
223: #endif
224:
225: /* TODO NMGS could be faster if all put on one line with shifts etc,
226: * does -O2 optimise this?
227: */
228:
229: primary_match.bits.valid = 1;
230: /* virtual segment id = concat of space id + seg reg no */
231: primary_match.bits.segment_id = segment_id;
232: primary_match.bits.hash_id = 0;
233: primary_match.bits.page_index = ((va_abbrev_t *)&v_addr)->page_index;
234:
235:
236: pte = find_pte_in_pteg((pte_t *) primary_hash, primary_match.word);
237:
238: if (pte != PTE_NULL) {
239: #if MEM_STATS
240: hash_table_stats.find_or_alloc_calls[allocate].found_primary++;
241: #endif /* MEM_STATS */
242: assert (pte->pte0.word != PTE_EMPTY);
243: return pte;
244: }
245:
246: #if 0 && MACH_VM_DEBUG
247: DPRINTF(("find_pte : searching secondary hash\n"));
248: #endif
249:
250: /* pte wasn't found in primary hash location, check secondary */
251:
252: secondary_match = primary_match;
253: secondary_match.bits.hash_id = 1; /* Indicate secondary hash */
254:
255: secondary_hash = primary_hash ^ hash_function_mask;
256:
257: pte = find_pte_in_pteg((pte_t *) secondary_hash, secondary_match.word);
258:
259: #if MEM_STATS
260: if (pte != PTE_NULL)
261: hash_table_stats.find_or_alloc_calls[allocate].found_secondary++;
262: if ((pte == PTE_NULL) && !allocate)
263: hash_table_stats.find_or_alloc_calls[allocate].not_found++;
264: #endif /* MEM_STATS */
265:
266: if ((pte == PTE_NULL) && allocate) {
267: /* pte wasn't found - find one ourselves and fill in
268: * the pte0 entry (mark as invalid though?)
269: */
270: pte = find_pte_in_pteg((pte_t *) primary_hash, PTE_EMPTY);
271: if (pte != PTE_NULL) {
272: /* Found in primary location, set up pte0 */
273:
274: primary_match.bits.valid = 0;
275: pte->pte0.word = primary_match.word;
276: #if MEM_STATS
277: hash_table_stats.find_or_alloc_calls[allocate].alloc_primary++;
278: #endif /* MEM_STATS */
279:
280: } else {
281: pte = find_pte_in_pteg((pte_t *) secondary_hash,
282: PTE_EMPTY);
283: if (pte != PTE_NULL) {
284: /* Found in secondary */
285: secondary_match.bits.valid = 0;
286: pte->pte0.word = secondary_match.word;
287: #if MEM_STATS
288: hash_table_stats.find_or_alloc_calls[allocate].alloc_secondary++;
289: #endif /* MEM_STATS */
290: } else {
291: #if MEM_STATS
292: hash_table_stats.find_or_alloc_calls[allocate].overflow++;
293: #endif /* MEM_STATS */
294: /* Both PTEGs are full - we need to upcall
295: * to pmap to free up an entry, it will
296: * return the entry that has been freed up
297: */
298: #if DEBUG
299: /* DPRINTF(("find_or_allocate : BOTH PTEGS ARE FULL\n")); */
300: #endif /* DEBUG */
301: pte = pmap_pteg_overflow(
302: (pte_t *)primary_hash,
303: primary_match,
304: (pte_t *)secondary_hash,
305: secondary_match);
306: assert (pte != PTE_NULL);
307: }
308: }
309: /* Set up the new entry - pmap code assumes:
310: * pte0 contains good translation but valid bit is reset
311: * pte1 has been initialised to zero
312: */
313: assert(pte->pte0.word != PTE_EMPTY);
314: pte->pte1.word = 0;
315:
316: }
317:
318: return pte; /* Either the address or PTE_NULL */
319: }
320:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.