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