Return to htab.c CVS log

Up to [Apple Darwin 0.x] / kernel / machdep / ppc

Annotation of kernel/machdep/ppc/htab.c, revision 1.1

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.