1 /* 2 * Copyright (c) 1987, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * from: @(#)kern_malloc.c 7.25 (Berkeley) 5/8/91 34 * $Id: kern_malloc.c,v 1.4 1993/05/27 14:35:22 deraadt Exp $ 35 */ 36 37 #include "param.h" 38 #include "proc.h" 39 #include "kernel.h" 40 #include "malloc.h" 41 #include "vm/vm.h" 42 #include "vm/vm_kern.h" 43 44 struct kmembuckets bucket[MINBUCKET + 16]; 45 struct kmemstats kmemstats[M_LAST + 1]; 46 struct kmemusage *kmemusage; 47 char *kmembase, *kmemlimit; 48 char *memname[] = INITKMEMNAMES; 49 50 /* 51 * Allocate a block of memory 52 */ 53 void * 54 malloc(size, type, flags) 55 unsigned long size; 56 int type, flags; 57 { 58 register struct kmembuckets *kbp; 59 register struct kmemusage *kup; 60 long indx, npg, alloc, allocsize; 61 int s; 62 caddr_t va, cp, savedlist; 63 #ifdef KMEMSTATS 64 register struct kmemstats *ksp = &kmemstats[type]; 65 66 if (((unsigned long)type) > M_LAST) 67 panic("malloc - bogus type"); 68 #endif 69 70 indx = BUCKETINDX(size); 71 kbp = &bucket[indx]; 72 s = splimp(); 73 74 retrymalloc: 75 #ifdef KMEMSTATS 76 while (ksp->ks_memuse >= ksp->ks_limit) { 77 if (flags & M_NOWAIT) { 78 splx(s); 79 return ((void *) NULL); 80 } 81 if (ksp->ks_limblocks < 65535) 82 ksp->ks_limblocks++; 83 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 84 } 85 #endif 86 if (kbp->kb_next == NULL) { 87 if (size > MAXALLOCSAVE) 88 allocsize = roundup(size, CLBYTES); 89 else 90 allocsize = 1 << indx; 91 npg = clrnd(btoc(allocsize)); 92 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), 93 !(flags & M_NOWAIT)); 94 if (va == NULL) { 95 if (flags & M_NOWAIT) { 96 splx(s); 97 return ((void *) NULL); 98 } 99 #ifdef KMEMSTATS 100 if (ksp->ks_mapblocks < 65535) 101 ksp->ks_mapblocks++; 102 #endif 103 tsleep((caddr_t)kmem_map, PSWP+2, "kern_malloc", 0); 104 goto retrymalloc; 105 } 106 #ifdef KMEMSTATS 107 kbp->kb_total += kbp->kb_elmpercl; 108 #endif 109 kup = btokup(va); 110 kup->ku_indx = indx; 111 if (allocsize > MAXALLOCSAVE) { 112 if (npg > 65535) 113 panic("malloc: allocation too large"); 114 kup->ku_pagecnt = npg; 115 #ifdef KMEMSTATS 116 ksp->ks_memuse += allocsize; 117 #endif 118 goto out; 119 } 120 #ifdef KMEMSTATS 121 kup->ku_freecnt = kbp->kb_elmpercl; 122 kbp->kb_totalfree += kbp->kb_elmpercl; 123 #endif 124 /* 125 * Just in case we blocked while allocating memory, 126 * and someone else also allocated memory for this 127 * bucket, don't assume the list is still empty. 128 */ 129 savedlist = kbp->kb_next; 130 kbp->kb_next = va + (npg * NBPG) - allocsize; 131 for (cp = kbp->kb_next; cp > va; cp -= allocsize) 132 *(caddr_t *)cp = cp - allocsize; 133 *(caddr_t *)cp = savedlist; 134 } 135 va = kbp->kb_next; 136 kbp->kb_next = *(caddr_t *)va; 137 #ifdef KMEMSTATS 138 kup = btokup(va); 139 if (kup->ku_indx != indx) 140 panic("malloc: wrong bucket"); 141 if (kup->ku_freecnt == 0) 142 panic("malloc: lost data"); 143 kup->ku_freecnt--; 144 kbp->kb_totalfree--; 145 ksp->ks_memuse += 1 << indx; 146 out: 147 kbp->kb_calls++; 148 ksp->ks_inuse++; 149 ksp->ks_calls++; 150 if (ksp->ks_memuse > ksp->ks_maxused) 151 ksp->ks_maxused = ksp->ks_memuse; 152 #else 153 out: 154 #endif 155 splx(s); 156 return ((void *) va); 157 } 158 159 #ifdef DIAGNOSTIC 160 long addrmask[] = { 0x00000000, 161 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 162 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 163 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 164 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 165 }; 166 #endif /* DIAGNOSTIC */ 167 168 /* 169 * Free a block of memory allocated by malloc. 170 */ 171 void 172 free(addr, type) 173 void *addr; 174 int type; 175 { 176 register struct kmembuckets *kbp; 177 register struct kmemusage *kup; 178 long alloc, size; 179 int s; 180 #ifdef KMEMSTATS 181 register struct kmemstats *ksp = &kmemstats[type]; 182 #endif 183 184 kup = btokup(addr); 185 size = 1 << kup->ku_indx; 186 #ifdef DIAGNOSTIC 187 if (size > NBPG * CLSIZE) 188 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 189 else 190 alloc = addrmask[kup->ku_indx]; 191 if (((u_long)addr & alloc) != 0) { 192 printf("free: unaligned addr 0x%x, size %d, type %d, mask %d\n", 193 addr, size, type, alloc); 194 panic("free: unaligned addr"); 195 } 196 #endif /* DIAGNOSTIC */ 197 kbp = &bucket[kup->ku_indx]; 198 s = splimp(); 199 if (size > MAXALLOCSAVE) { 200 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 201 #ifdef KMEMSTATS 202 size = kup->ku_pagecnt << PGSHIFT; 203 ksp->ks_memuse -= size; 204 kup->ku_indx = 0; 205 kup->ku_pagecnt = 0; 206 if (ksp->ks_memuse + size >= ksp->ks_limit && 207 ksp->ks_memuse < ksp->ks_limit) 208 wakeup((caddr_t)ksp); 209 ksp->ks_inuse--; 210 kbp->kb_total -= 1; 211 #endif 212 wakeup((caddr_t)kmem_map); 213 splx(s); 214 return; 215 } 216 #ifdef KMEMSTATS 217 kup->ku_freecnt++; 218 if (kup->ku_freecnt >= kbp->kb_elmpercl) 219 if (kup->ku_freecnt > kbp->kb_elmpercl) 220 panic("free: multiple frees"); 221 else if (kbp->kb_totalfree > kbp->kb_highwat) 222 kbp->kb_couldfree++; 223 kbp->kb_totalfree++; 224 ksp->ks_memuse -= size; 225 if (ksp->ks_memuse + size >= ksp->ks_limit && 226 ksp->ks_memuse < ksp->ks_limit) 227 wakeup((caddr_t)ksp); 228 ksp->ks_inuse--; 229 #endif 230 *(caddr_t *)addr = kbp->kb_next; 231 kbp->kb_next = addr; 232 wakeup((caddr_t)kmem_map); 233 splx(s); 234 } 235 236 /* 237 * Initialize the kernel memory allocator 238 */ 239 kmeminit() 240 { 241 register long indx; 242 int npg; 243 244 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 245 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 246 #endif 247 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 248 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 249 #endif 250 #if (MAXALLOCSAVE < CLBYTES) 251 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 252 #endif 253 npg = VM_KMEM_SIZE/ NBPG; 254 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 255 (vm_size_t)(npg * sizeof(struct kmemusage))); 256 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 257 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); 258 #ifdef KMEMSTATS 259 for (indx = 0; indx < MINBUCKET + 16; indx++) { 260 if (1 << indx >= CLBYTES) 261 bucket[indx].kb_elmpercl = 1; 262 else 263 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 264 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 265 } 266 for (indx = 0; indx <= M_LAST; indx++) 267 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 268 #endif 269 } 270