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