kern_malloc.c revision 33109
1/* 2 * Copyright (c) 1987, 1991, 1993 3 * The Regents of the University of California. 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 * @(#)kern_malloc.c 8.3 (Berkeley) 1/4/94 34 * $Id: kern_malloc.c,v 1.40 1998/02/04 22:32:32 eivind Exp $ 35 */ 36 37#include "opt_diagnostic.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/kernel.h> 42#define MALLOC_INSTANTIATE 43#include <sys/malloc.h> 44#include <sys/mbuf.h> 45#include <sys/vmmeter.h> 46#include <sys/lock.h> 47 48#include <vm/vm.h> 49#include <vm/vm_param.h> 50#include <vm/vm_kern.h> 51#include <vm/vm_extern.h> 52#include <vm/pmap.h> 53#include <vm/vm_map.h> 54 55static void kmeminit __P((void *)); 56static void malloc_init __P((struct malloc_type *)); 57SYSINIT(kmem, SI_SUB_KMEM, SI_ORDER_FIRST, kmeminit, NULL) 58 59static MALLOC_DEFINE(M_FREE, "free", "should be on free list"); 60 61struct malloc_type *kmemstatistics = M_FREE; 62static struct kmembuckets bucket[MINBUCKET + 16]; 63static struct kmemusage *kmemusage; 64static char *kmembase; 65static char *kmemlimit; 66 67#ifdef DIAGNOSTIC 68/* 69 * This structure provides a set of masks to catch unaligned frees. 70 */ 71static long addrmask[] = { 0, 72 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 73 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 74 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 75 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 76}; 77 78/* 79 * The WEIRD_ADDR is used as known text to copy into free objects so 80 * that modifications after frees can be detected. 81 */ 82#define WEIRD_ADDR 0xdeadc0de 83#define MAX_COPY 64 84 85/* 86 * Normally the first word of the structure is used to hold the list 87 * pointer for free objects. However, when running with diagnostics, 88 * we use the third and fourth fields, so as to catch modifications 89 * in the most commonly trashed first two words. 90 */ 91struct freelist { 92 long spare0; 93 struct malloc_type *type; 94 long spare1; 95 caddr_t next; 96}; 97#else /* !DIAGNOSTIC */ 98struct freelist { 99 caddr_t next; 100}; 101#endif /* DIAGNOSTIC */ 102 103/* 104 * Allocate a block of memory 105 */ 106void * 107malloc(size, type, flags) 108 unsigned long size; 109 struct malloc_type *type; 110 int flags; 111{ 112 register struct kmembuckets *kbp; 113 register struct kmemusage *kup; 114 register struct freelist *freep; 115 long indx, npg, allocsize; 116 int s; 117 caddr_t va, cp, savedlist; 118#ifdef DIAGNOSTIC 119 long *end, *lp; 120 int copysize; 121 char *savedtype; 122#endif 123 register struct malloc_type *ksp = type; 124 125 if (!type->ks_next) 126 malloc_init(type); 127 128 indx = BUCKETINDX(size); 129 kbp = &bucket[indx]; 130 s = splhigh(); 131 while (ksp->ks_memuse >= ksp->ks_limit) { 132 if (flags & M_NOWAIT) { 133 splx(s); 134 return ((void *) NULL); 135 } 136 if (ksp->ks_limblocks < 65535) 137 ksp->ks_limblocks++; 138 tsleep((caddr_t)ksp, PSWP+2, type->ks_shortdesc, 0); 139 } 140 ksp->ks_size |= 1 << indx; 141#ifdef DIAGNOSTIC 142 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 143#endif 144 if (kbp->kb_next == NULL) { 145 kbp->kb_last = NULL; 146 if (size > MAXALLOCSAVE) 147 allocsize = roundup(size, PAGE_SIZE); 148 else 149 allocsize = 1 << indx; 150 npg = btoc(allocsize); 151 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), flags); 152 if (va == NULL) { 153 splx(s); 154 return ((void *) NULL); 155 } 156 kbp->kb_total += kbp->kb_elmpercl; 157 kup = btokup(va); 158 kup->ku_indx = indx; 159 if (allocsize > MAXALLOCSAVE) { 160 if (npg > 65535) 161 panic("malloc: allocation too large"); 162 kup->ku_pagecnt = npg; 163 ksp->ks_memuse += allocsize; 164 goto out; 165 } 166 kup->ku_freecnt = kbp->kb_elmpercl; 167 kbp->kb_totalfree += kbp->kb_elmpercl; 168 /* 169 * Just in case we blocked while allocating memory, 170 * and someone else also allocated memory for this 171 * bucket, don't assume the list is still empty. 172 */ 173 savedlist = kbp->kb_next; 174 kbp->kb_next = cp = va + (npg * PAGE_SIZE) - allocsize; 175 for (;;) { 176 freep = (struct freelist *)cp; 177#ifdef DIAGNOSTIC 178 /* 179 * Copy in known text to detect modification 180 * after freeing. 181 */ 182 end = (long *)&cp[copysize]; 183 for (lp = (long *)cp; lp < end; lp++) 184 *lp = WEIRD_ADDR; 185 freep->type = M_FREE; 186#endif /* DIAGNOSTIC */ 187 if (cp <= va) 188 break; 189 cp -= allocsize; 190 freep->next = cp; 191 } 192 freep->next = savedlist; 193 if (kbp->kb_last == NULL) 194 kbp->kb_last = (caddr_t)freep; 195 } 196 va = kbp->kb_next; 197 kbp->kb_next = ((struct freelist *)va)->next; 198#ifdef DIAGNOSTIC 199 freep = (struct freelist *)va; 200 savedtype = (char *) type->ks_shortdesc; 201#if BYTE_ORDER == BIG_ENDIAN 202 freep->type = (struct malloc_type *)WEIRD_ADDR >> 16; 203#endif 204#if BYTE_ORDER == LITTLE_ENDIAN 205 freep->type = (struct malloc_type *)WEIRD_ADDR; 206#endif 207 if (((long)(&freep->next)) & 0x2) 208 freep->next = (caddr_t)((WEIRD_ADDR >> 16)|(WEIRD_ADDR << 16)); 209 else 210 freep->next = (caddr_t)WEIRD_ADDR; 211 end = (long *)&va[copysize]; 212 for (lp = (long *)va; lp < end; lp++) { 213 if (*lp == WEIRD_ADDR) 214 continue; 215 printf("%s %d of object %p size %ld %s %s (0x%lx != 0x%x)\n", 216 "Data modified on freelist: word", lp - (long *)va, 217 va, size, "previous type", savedtype, *lp, WEIRD_ADDR); 218 break; 219 } 220 freep->spare0 = 0; 221#endif /* DIAGNOSTIC */ 222 kup = btokup(va); 223 if (kup->ku_indx != indx) 224 panic("malloc: wrong bucket"); 225 if (kup->ku_freecnt == 0) 226 panic("malloc: lost data"); 227 kup->ku_freecnt--; 228 kbp->kb_totalfree--; 229 ksp->ks_memuse += 1 << indx; 230out: 231 kbp->kb_calls++; 232 ksp->ks_inuse++; 233 ksp->ks_calls++; 234 if (ksp->ks_memuse > ksp->ks_maxused) 235 ksp->ks_maxused = ksp->ks_memuse; 236 splx(s); 237 return ((void *) va); 238} 239 240/* 241 * Free a block of memory allocated by malloc. 242 */ 243void 244free(addr, type) 245 void *addr; 246 struct malloc_type *type; 247{ 248 register struct kmembuckets *kbp; 249 register struct kmemusage *kup; 250 register struct freelist *freep; 251 long size; 252 int s; 253#ifdef DIAGNOSTIC 254 struct freelist *fp; 255 long *end, *lp, alloc, copysize; 256#endif 257 register struct malloc_type *ksp = type; 258 259 if (!type->ks_next) 260 panic("freeing with unknown type (%s)", type->ks_shortdesc); 261 262#ifdef DIAGNOSTIC 263 if ((char *)addr < kmembase || (char *)addr >= kmemlimit) { 264 panic("free: address 0x%x out of range", addr); 265 } 266#endif 267 kup = btokup(addr); 268 size = 1 << kup->ku_indx; 269 kbp = &bucket[kup->ku_indx]; 270 s = splhigh(); 271#ifdef DIAGNOSTIC 272 /* 273 * Check for returns of data that do not point to the 274 * beginning of the allocation. 275 */ 276 if (size > PAGE_SIZE) 277 alloc = addrmask[BUCKETINDX(PAGE_SIZE)]; 278 else 279 alloc = addrmask[kup->ku_indx]; 280 if (((u_long)addr & alloc) != 0) 281 panic("free: unaligned addr 0x%x, size %d, type %s, mask %d", 282 addr, size, type->ks_shortdesc, alloc); 283#endif /* DIAGNOSTIC */ 284 if (size > MAXALLOCSAVE) { 285 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 286 size = kup->ku_pagecnt << PAGE_SHIFT; 287 ksp->ks_memuse -= size; 288 kup->ku_indx = 0; 289 kup->ku_pagecnt = 0; 290 if (ksp->ks_memuse + size >= ksp->ks_limit && 291 ksp->ks_memuse < ksp->ks_limit) 292 wakeup((caddr_t)ksp); 293 ksp->ks_inuse--; 294 kbp->kb_total -= 1; 295 splx(s); 296 return; 297 } 298 freep = (struct freelist *)addr; 299#ifdef DIAGNOSTIC 300 /* 301 * Check for multiple frees. Use a quick check to see if 302 * it looks free before laboriously searching the freelist. 303 */ 304 if (freep->spare0 == WEIRD_ADDR) { 305 fp = (struct freelist *)kbp->kb_next; 306 while (fp) { 307 if (fp->spare0 != WEIRD_ADDR) { 308 printf("trashed free item %p\n", fp); 309 panic("free: free item modified"); 310 } else if (addr == (caddr_t)fp) { 311 printf("multiple freed item %p\n", addr); 312 panic("free: multiple free"); 313 } 314 fp = (struct freelist *)fp->next; 315 } 316 } 317 /* 318 * Copy in known text to detect modification after freeing 319 * and to make it look free. Also, save the type being freed 320 * so we can list likely culprit if modification is detected 321 * when the object is reallocated. 322 */ 323 copysize = size < MAX_COPY ? size : MAX_COPY; 324 end = (long *)&((caddr_t)addr)[copysize]; 325 for (lp = (long *)addr; lp < end; lp++) 326 *lp = WEIRD_ADDR; 327 freep->type = type; 328#endif /* DIAGNOSTIC */ 329 kup->ku_freecnt++; 330 if (kup->ku_freecnt >= kbp->kb_elmpercl) 331 if (kup->ku_freecnt > kbp->kb_elmpercl) 332 panic("free: multiple frees"); 333 else if (kbp->kb_totalfree > kbp->kb_highwat) 334 kbp->kb_couldfree++; 335 kbp->kb_totalfree++; 336 ksp->ks_memuse -= size; 337 if (ksp->ks_memuse + size >= ksp->ks_limit && 338 ksp->ks_memuse < ksp->ks_limit) 339 wakeup((caddr_t)ksp); 340 ksp->ks_inuse--; 341#ifdef OLD_MALLOC_MEMORY_POLICY 342 if (kbp->kb_next == NULL) 343 kbp->kb_next = addr; 344 else 345 ((struct freelist *)kbp->kb_last)->next = addr; 346 freep->next = NULL; 347 kbp->kb_last = addr; 348#else 349 /* 350 * Return memory to the head of the queue for quick reuse. This 351 * can improve performance by improving the probability of the 352 * item being in the cache when it is reused. 353 */ 354 if (kbp->kb_next == NULL) { 355 kbp->kb_next = addr; 356 kbp->kb_last = addr; 357 freep->next = NULL; 358 } else { 359 freep->next = kbp->kb_next; 360 kbp->kb_next = addr; 361 } 362#endif 363 splx(s); 364} 365 366/* 367 * Initialize the kernel memory allocator 368 */ 369/* ARGSUSED*/ 370static void 371kmeminit(dummy) 372 void *dummy; 373{ 374 register long indx; 375 int npg; 376 377#if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 378#error "kmeminit: MAXALLOCSAVE not power of 2" 379#endif 380#if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 381#error "kmeminit: MAXALLOCSAVE too big" 382#endif 383#if (MAXALLOCSAVE < PAGE_SIZE) 384#error "kmeminit: MAXALLOCSAVE too small" 385#endif 386 npg = (nmbufs * MSIZE + nmbclusters * MCLBYTES + VM_KMEM_SIZE) 387 / PAGE_SIZE; 388 389 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 390 (vm_size_t)(npg * sizeof(struct kmemusage))); 391 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 392 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * PAGE_SIZE)); 393 kmem_map->system_map = 1; 394 for (indx = 0; indx < MINBUCKET + 16; indx++) { 395 if (1 << indx >= PAGE_SIZE) 396 bucket[indx].kb_elmpercl = 1; 397 else 398 bucket[indx].kb_elmpercl = PAGE_SIZE / (1 << indx); 399 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 400 } 401} 402 403static void 404malloc_init(type) 405 struct malloc_type *type; 406{ 407 int npg; 408 409 if (type->ks_magic != M_MAGIC) 410 panic("malloc type lacks magic"); 411 412 if (cnt.v_page_count == 0) 413 panic("malloc_init not allowed before vm init"); 414 415 /* 416 * Limit maximum memory for each type to 60% of malloc area size or 417 * 60% of physical memory, whichever is smaller. 418 */ 419 npg = (nmbufs * MSIZE + nmbclusters * MCLBYTES + VM_KMEM_SIZE) 420 / PAGE_SIZE; 421 422 type->ks_limit = min(cnt.v_page_count * PAGE_SIZE, 423 (npg * PAGE_SIZE - nmbclusters * MCLBYTES 424 - nmbufs * MSIZE)) * 6 / 10; 425 type->ks_next = kmemstatistics; 426 kmemstatistics = type; 427} 428