Return to rtmalloc.c CVS log

Up to [Apple XNU] / XNU / osfmk / kern

Annotation of XNU/osfmk/kern/rtmalloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2000 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:  * @OSF_COPYRIGHT@
        !            24:  */
        !            25: /*
        !            26:  * HISTORY
        !            27:  * $Log: rtmalloc.c,v $
        !            28:  * Revision 1.1.1.1  2000/03/25 21:02:59  wsanchez
        !            29:  * Import of xnu-68.4
        !            30:  *
        !            31:  * Revision 1.3  2000/01/26 05:57:35  wsanchez
        !            32:  * Add APSL
        !            33:  *
        !            34:  * Revision 1.2  1998/10/20 03:35:27  wsanchez
        !            35:  * Merged in Bill's mother-of-all-diffs.
        !            36:  *
        !            37:  * Revision 1.1.2.1  1998/10/20 02:52:22  angell
        !            38:  * Changed PTE handling.  Added SMP and RT. Improved context saving.
        !            39:  *
        !            40:  * Revision 1.1.1.1  1998/09/22 21:05:33  wsanchez
        !            41:  * Import of Mac OS X kernel (~semeria)
        !            42:  *
        !            43:  * Revision 1.1.1.1  1998/03/07 02:25:56  wsanchez
        !            44:  * Import of OSF Mach kernel (~mburg)
        !            45:  *
        !            46:  * Revision 1.1.4.4  1995/10/09  17:16:24  devrcs
        !            47:  *     Merge RT IPC
        !            48:  *     [1995/09/21  23:10:26  widyono]
        !            49:  *
        !            50:  * Revision 1.1.4.3  1995/01/10  05:13:37  devrcs
        !            51:  *     mk6 CR801 - copyright marker not FREE_
        !            52:  *     [1994/12/01  19:24:57  dwm]
        !            53:  * 
        !            54:  *     mk6 CR668 - 1.3b26 merge
        !            55:  *     zchange to zone_change
        !            56:  *     [1994/11/04  09:29:18  dwm]
        !            57:  * 
        !            58:  * Revision 1.1.4.1  1994/08/18  23:12:56  widyono
        !            59:  *     RT IPC from RT2_SHARED
        !            60:  *     [1994/08/18  15:50:06  widyono]
        !            61:  * 
        !            62:  * Revision 1.1.2.1  1994/07/29  07:34:38  widyono
        !            63:  *     Explicitly make RT zones non-collectable, non-expandable
        !            64:  *     [1994/07/29  06:26:39  widyono]
        !            65:  * 
        !            66:  *     Update to rt2_shared: zchange -> zone_change
        !            67:  *     [1994/07/29  05:07:59  widyono]
        !            68:  * 
        !            69:  *     RT zone allocation routines, new module
        !            70:  *     [1994/07/28  22:31:19  widyono]
        !            71:  * 
        !            72:  * $EndLog$
        !            73:  */
        !            74: /* CMU_HIST */
        !            75: /*
        !            76:  * Revision 2.9  91/05/14  16:43:17  mrt
        !            77:  *     Correcting copyright
        !            78:  * 
        !            79:  * Revision 2.8  91/03/16  14:50:37  rpd
        !            80:  *     Updated for new kmem_alloc interface.
        !            81:  *     [91/03/03            rpd]
        !            82:  * 
        !            83:  * Revision 2.7  91/02/05  17:27:22  mrt
        !            84:  *     Changed to new Mach copyright
        !            85:  *     [91/02/01  16:14:12  mrt]
        !            86:  * 
        !            87:  * Revision 2.6  90/06/19  22:59:06  rpd
        !            88:  *     Made the big kalloc zones collectable.
        !            89:  *     [90/06/05            rpd]
        !            90:  * 
        !            91:  * Revision 2.5  90/06/02  14:54:47  rpd
        !            92:  *     Added kalloc_max, kalloc_map_size.
        !            93:  *     [90/03/26  22:06:39  rpd]
        !            94:  * 
        !            95:  * Revision 2.4  90/01/11  11:43:13  dbg
        !            96:  *     De-lint.
        !            97:  *     [89/12/06            dbg]
        !            98:  * 
        !            99:  * Revision 2.3  89/09/08  11:25:51  dbg
        !           100:  *     MACH_KERNEL: remove non-MACH data types.
        !           101:  *     [89/07/11            dbg]
        !           102:  * 
        !           103:  * Revision 2.2  89/08/31  16:18:59  rwd
        !           104:  *     First Checkin
        !           105:  *     [89/08/23  15:41:37  rwd]
        !           106:  * 
        !           107:  * Revision 2.6  89/08/02  08:03:28  jsb
        !           108:  *     Make all kalloc zones 8 MB big. (No more kalloc panics!)
        !           109:  *     [89/08/01  14:10:17  jsb]
        !           110:  * 
        !           111:  * Revision 2.4  89/04/05  13:03:10  rvb
        !           112:  *     Guarantee a zone max of at least 100 elements or 10 pages
        !           113:  *     which ever is greater.  Afs (AllocDouble()) puts a great demand
        !           114:  *     on the 2048 zone and used to blow away.
        !           115:  *     [89/03/09            rvb]
        !           116:  * 
        !           117:  * Revision 2.3  89/02/25  18:04:39  gm0w
        !           118:  *     Changes for cleanup.
        !           119:  * 
        !           120:  * Revision 2.2  89/01/18  02:07:04  jsb
        !           121:  *     Give each kalloc zone a meaningful name (for panics);
        !           122:  *     create a zone for each power of 2 between MINSIZE
        !           123:  *     and PAGE_SIZE, instead of using (obsoleted) NQUEUES.
        !           124:  *     [89/01/17  10:16:33  jsb]
        !           125:  * 
        !           126:  *
        !           127:  * 13-Feb-88  John Seamons (jks) at NeXT
        !           128:  *     Updated to use kmem routines instead of vmem routines.
        !           129:  *
        !           130:  * 21-Jun-85  Avadis Tevanian (avie) at Carnegie-Mellon University
        !           131:  *     Created.
        !           132:  */
        !           133: /* CMU_ENDHIST */
        !           134: /* 
        !           135:  * Mach Operating System
        !           136:  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
        !           137:  * All Rights Reserved.
        !           138:  * 
        !           139:  * Permission to use, copy, modify and distribute this software and its
        !           140:  * documentation is hereby granted, provided that both the copyright
        !           141:  * notice and this permission notice appear in all copies of the
        !           142:  * software, derivative works or modified versions, and any portions
        !           143:  * thereof, and that both notices appear in supporting documentation.
        !           144:  * 
        !           145:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !           146:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !           147:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !           148:  * 
        !           149:  * Carnegie Mellon requests users of this software to return to
        !           150:  * 
        !           151:  *  Software Distribution Coordinator  or  [email protected]
        !           152:  *  School of Computer Science
        !           153:  *  Carnegie Mellon University
        !           154:  *  Pittsburgh PA 15213-3890
        !           155:  * 
        !           156:  * any improvements or extensions that they make and grant Carnegie Mellon
        !           157:  * the rights to redistribute these changes.
        !           158:  */
        !           159: /*
        !           160:  */
        !           161: /*
        !           162:  *     File:   kern/rtmalloc.c
        !           163:  *     Author: Ron Widyono
        !           164:  *     Date:   1994
        !           165:  *
        !           166:  *     General real-time kernel memory allocator.  This allocator is designed
        !           167:  *     to be used by the kernel to manage dynamic memory fast, but exclusively
        !           168:  *      for real-time purposes.  In fact, only real-time IPC users compete for
        !           169:  *      these resources.
        !           170:  *
        !           171:  *      This is a dirty implementation--a clone of kalloc.  A cleaner imple-
        !           172:  *      mentation is to have both k_zones and rt_zones use common code.
        !           173:  */
        !           174: 
        !           175: #include <mach/boolean.h>
        !           176: #include <mach/machine/vm_types.h>
        !           177: #include <mach/vm_param.h>
        !           178: #include <kern/misc_protos.h>
        !           179: #include <kern/zalloc.h>
        !           180: #include <kern/rtmalloc.h>
        !           181: #include <vm/vm_kern.h>
        !           182: #include <vm/vm_object.h>
        !           183: #include <vm/vm_map.h>
        !           184: 
        !           185: extern void    Debugger(const char *);
        !           186: 
        !           187: vm_map_t rtmalloc_map;
        !           188: vm_size_t rtmalloc_map_size = 8 * 1024 * 1024;
        !           189: vm_size_t rtmalloc_max;
        !           190: vm_size_t rtmalloc_max_prerounded;
        !           191: 
        !           192: /*
        !           193:  *     All allocations of size less than rtmalloc_max are rounded to the
        !           194:  *     next highest power of 2.  This allocator is built on top of
        !           195:  *     the zone allocator.  A zone is created for each potential size
        !           196:  *     that we are willing to get in small blocks.
        !           197:  *
        !           198:  *     We assume that rtmalloc_max is not greater than 64K;
        !           199:  *     thus 16 is a safe array size for rt_zone and rt_zone_name.
        !           200:  *
        !           201:  *     Note that rtmalloc_max is somewhat confusingly named.
        !           202:  *     It represents the first power of two for which no zone exists.
        !           203:  *     rtmalloc_max_prerounded is the smallest allocation size, before
        !           204:  *     rounding, for which no zone exists.
        !           205:  */
        !           206: 
        !           207: int first_rt_zone = -1;
        !           208: struct zone *rt_zone[16];
        !           209: static char *rt_zone_name[16] = {
        !           210:        "rtmalloc.1",           "rtmalloc.2",
        !           211:        "rtmalloc.4",           "rtmalloc.8",
        !           212:        "rtmalloc.16",          "rtmalloc.32",
        !           213:        "rtmalloc.64",          "rtmalloc.128",
        !           214:        "rtmalloc.256",         "rtmalloc.512",
        !           215:        "rtmalloc.1024",                "rtmalloc.2048",
        !           216:        "rtmalloc.4096",                "rtmalloc.8192",
        !           217:        "rtmalloc.16384",       "rtmalloc.32768"
        !           218: };
        !           219: 
        !           220: /*
        !           221:  *  Max number of elements per zone.  zinit rounds things up correctly
        !           222:  *  Doing things this way permits each zone to have a different maximum size
        !           223:  *  based on need, rather than just guessing; it also
        !           224:  *  means its patchable in case you're wrong!
        !           225:  */
        !           226: unsigned long rt_zone_max[16] = {
        !           227:       RT_ZONE_MAX_1,   
        !           228:       RT_ZONE_MAX_2,   
        !           229:       RT_ZONE_MAX_4,   
        !           230:       RT_ZONE_MAX_8,   
        !           231:       RT_ZONE_MAX_16,  
        !           232:       RT_ZONE_MAX_32,  
        !           233:       RT_ZONE_MAX_64,  
        !           234:       RT_ZONE_MAX_128, 
        !           235:       RT_ZONE_MAX_256, 
        !           236:       RT_ZONE_MAX_512, 
        !           237:       RT_ZONE_MAX_1024,        
        !           238:       RT_ZONE_MAX_2048,        
        !           239:       RT_ZONE_MAX_4096,        
        !           240:       RT_ZONE_MAX_8192,        
        !           241:       RT_ZONE_MAX_16384,
        !           242:       RT_ZONE_MAX_32768
        !           243: };
        !           244: 
        !           245: /*
        !           246:  *     Initialize the memory allocator.  This should be called only
        !           247:  *     once on a system wide basis (i.e. first processor to get here
        !           248:  *     does the initialization).
        !           249:  *
        !           250:  *     This initializes all of the zones.
        !           251:  */
        !           252: 
        !           253: void
        !           254: rtmalloc_init(
        !           255:        void)
        !           256: {
        !           257:        kern_return_t retval;
        !           258:        vm_offset_t min, addr;
        !           259:        vm_size_t size;
        !           260:        register int i;
        !           261: 
        !           262:        retval = kmem_suballoc(kernel_map, &min, rtmalloc_map_size,
        !           263:                               FALSE, TRUE, &rtmalloc_map);
        !           264:        if (retval != KERN_SUCCESS)
        !           265:                panic("rtmalloc_init: kmem_suballoc failed");
        !           266: 
        !           267:        /*
        !           268:         *      Ensure that zones up to size 8192 bytes exist.
        !           269:         *      This is desirable because messages are allocated
        !           270:         *      with rtmalloc, and messages up through size 8192 are common.
        !           271:         */
        !           272: 
        !           273:        rtmalloc_max = 16 * 1024;
        !           274:        rtmalloc_max_prerounded = rtmalloc_max / 2 + 1;
        !           275: 
        !           276:        /*
        !           277:         *      Allocate a zone for each size we are going to handle.
        !           278:         *      We specify non-paged memory.  Make zone exhaustible.
        !           279:         */
        !           280:        for (i = 0, size = 1; size < rtmalloc_max; i++, size <<= 1) {
        !           281:                if (size < rtmalloc_MINSIZE) {
        !           282:                        rt_zone[i] = 0;
        !           283:                        continue;
        !           284:                }
        !           285:                if (size == rtmalloc_MINSIZE) {
        !           286:                        first_rt_zone = i;
        !           287:                }
        !           288:                rt_zone[i] = zinit(size, rt_zone_max[i] * size, size,
        !           289:                                  rt_zone_name[i]);
        !           290:                zone_change(rt_zone[i], Z_EXHAUST, TRUE);
        !           291:                zone_change(rt_zone[i], Z_COLLECT, FALSE);
        !           292:                zone_change(rt_zone[i], Z_EXPAND, FALSE);
        !           293: 
        !           294:                /*
        !           295:                 * Get space from the zone_map.  Since these zones are
        !           296:                 * not collectable, no pages containing elements from these
        !           297:                 * zones will ever be reclaimed by the garbage collection
        !           298:                 * scheme below.
        !           299:                 */
        !           300: 
        !           301:                zprealloc(rt_zone[i], rt_zone_max[i] * size);
        !           302:        }
        !           303: }
        !           304: 
        !           305: vm_offset_t
        !           306: rtmalloc(
        !           307:        vm_size_t       size)
        !           308: {
        !           309:        register int zindex;
        !           310:        register vm_size_t allocsize;
        !           311: 
        !           312:        /*
        !           313:         * If size is too large for a zone, return error (0)
        !           314:         */
        !           315: 
        !           316:        if (size >= rtmalloc_max_prerounded) {
        !           317:                return(0);
        !           318:        }
        !           319: 
        !           320:        /* compute the size of the block that we will actually allocate */
        !           321: 
        !           322:        allocsize = rtmalloc_MINSIZE;
        !           323:        zindex = first_rt_zone;
        !           324:        while (allocsize < size) {
        !           325:                allocsize <<= 1;
        !           326:                zindex++;
        !           327:        }
        !           328: 
        !           329:        /* allocate from the appropriate zone */
        !           330: 
        !           331:        assert(allocsize < rtmalloc_max);
        !           332:        return(zalloc(rt_zone[zindex]));
        !           333: }
        !           334: 
        !           335: vm_offset_t
        !           336: rtget(
        !           337:        vm_size_t       size)
        !           338: {
        !           339:        register int zindex;
        !           340:        register vm_size_t allocsize;
        !           341: 
        !           342:        /* size must not be too large for a zone */
        !           343: 
        !           344:        if (size >= rtmalloc_max_prerounded) {
        !           345:                /* This will never work, so we might as well panic */
        !           346:                panic("rtget");
        !           347:        }
        !           348: 
        !           349:        /* compute the size of the block that we will actually allocate */
        !           350: 
        !           351:        allocsize = rtmalloc_MINSIZE;
        !           352:        zindex = first_rt_zone;
        !           353:        while (allocsize < size) {
        !           354:                allocsize <<= 1;
        !           355:                zindex++;
        !           356:        }
        !           357: 
        !           358:        /* allocate from the appropriate zone */
        !           359: 
        !           360:        assert(allocsize < rtmalloc_max);
        !           361:        return(zget(rt_zone[zindex]));
        !           362: }
        !           363: 
        !           364: void
        !           365: rtmfree(
        !           366:        vm_offset_t     data,
        !           367:        vm_size_t       size)
        !           368: {
        !           369:        register int zindex;
        !           370:        register vm_size_t freesize;
        !           371: 
        !           372:        /*
        !           373:         * if size was too large for a RT zone, this is impossible;
        !           374:         * just return
        !           375:         */
        !           376: 
        !           377:        assert(size < rtmalloc_max_prerounded);
        !           378:        if (size >= rtmalloc_max_prerounded) {
        !           379:                return;
        !           380:        }
        !           381: 
        !           382:        /* compute the size of the block that we actually allocated from */
        !           383: 
        !           384:        freesize = rtmalloc_MINSIZE;
        !           385:        zindex = first_rt_zone;
        !           386:        while (freesize < size) {
        !           387:                freesize <<= 1;
        !           388:                zindex++;
        !           389:        }
        !           390: 
        !           391:        /* free to the appropriate zone */
        !           392: 
        !           393:        assert(freesize < rtmalloc_max);
        !           394:        zfree(rt_zone[zindex], data);
        !           395: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.