/* * Copyright (c) 1987, 1991 The Regents of the University of California. * All rights reserved. * * %sccs.include.redist.c% * * @(#)kern_malloc.c 7.27 (Berkeley) 08/29/91 */ #include "param.h" #include "proc.h" #include "map.h" #include "kernel.h" #include "malloc.h" #include "vm/vm.h" #include "vm/vm_kern.h" struct kmembuckets bucket[MINBUCKET + 16]; struct kmemstats kmemstats[M_LAST]; struct kmemusage *kmemusage; char *kmembase, *kmemlimit; char *memname[] = INITKMEMNAMES; #ifdef DIAGNOSTIC /* * This structure serves two purposes. * The first is to provide a set of masks to catch unaligned frees. * The second is to provide known text to copy into free objects so * that modifications after frees can be detected. */ #define WEIRD_ADDR 0xdeadbeef long addrmask[] = { WEIRD_ADDR, 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, }; /* * Normally the first word of the structure is used to hold the list * pointer for free objects. However, when running with diagnostics, * we use the third and fourth fields, so as to catch modifications * in the most commonly trashed first two words. */ struct freelist { long spare0; long spare1; short type; short spare2; caddr_t next; }; #else /* !DIAGNOSTIC */ struct freelist { caddr_t next; }; #endif /* DIAGNOSTIC */ /* * Allocate a block of memory */ void * malloc(size, type, flags) unsigned long size; int type, flags; { register struct kmembuckets *kbp; register struct kmemusage *kup; register struct freelist *freep; long indx, npg, alloc, allocsize; int s; caddr_t va, cp, savedlist; #ifdef DIAGNOSTIC int i, copysize; short savedtype; #endif #ifdef KMEMSTATS register struct kmemstats *ksp = &kmemstats[type]; if (((unsigned long)type) > M_LAST) panic("malloc - bogus type"); #endif indx = BUCKETINDX(size); kbp = &bucket[indx]; s = splimp(); #ifdef KMEMSTATS while (ksp->ks_memuse >= ksp->ks_limit) { if (flags & M_NOWAIT) { splx(s); return ((void *) NULL); } if (ksp->ks_limblocks < 65535) ksp->ks_limblocks++; tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); } #endif #ifdef DIAGNOSTIC copysize = 1 << indx < sizeof addrmask ? 1 << indx : sizeof addrmask; #endif if (kbp->kb_next == NULL) { if (size > MAXALLOCSAVE) allocsize = roundup(size, CLBYTES); else allocsize = 1 << indx; npg = clrnd(btoc(allocsize)); va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), !(flags & M_NOWAIT)); if (va == NULL) { splx(s); return ((void *) NULL); } #ifdef KMEMSTATS kbp->kb_total += kbp->kb_elmpercl; #endif kup = btokup(va); kup->ku_indx = indx; if (allocsize > MAXALLOCSAVE) { if (npg > 65535) panic("malloc: allocation too large"); kup->ku_pagecnt = npg; #ifdef KMEMSTATS ksp->ks_memuse += allocsize; #endif goto out; } #ifdef KMEMSTATS kup->ku_freecnt = kbp->kb_elmpercl; kbp->kb_totalfree += kbp->kb_elmpercl; #endif /* * Just in case we blocked while allocating memory, * and someone else also allocated memory for this * bucket, don't assume the list is still empty. */ savedlist = kbp->kb_next; kbp->kb_next = va + (npg * NBPG) - allocsize; for (cp = kbp->kb_next; ; cp -= allocsize) { freep = (struct freelist *)cp; #ifdef DIAGNOSTIC /* * Copy in known text to detect modification * after freeing. */ bcopy(addrmask, cp, copysize); freep->type = M_FREE; #endif /* DIAGNOSTIC */ if (cp <= va) break; freep->next = cp - allocsize; } freep->next = savedlist; } va = kbp->kb_next; kbp->kb_next = ((struct freelist *)va)->next; #ifdef DIAGNOSTIC freep = (struct freelist *)va; savedtype = freep->type; freep->type = ((struct freelist *)addrmask)->type; freep->next = ((struct freelist *)addrmask)->next; if (bcmp(addrmask, va, copysize)) { copysize >>= 2; for (i = 0; i < copysize && addrmask[i] == ((int *)va)[i]; i++) /* void */; printf("%s %d of object 0x%x size %d %s %s (0x%x != 0x%x)\n", "Data modified on freelist: word", i, va, size, "previous type", memname[savedtype], ((int *)va)[i], addrmask[i]); panic("malloc: data modified on freelist"); } freep->spare0 = 0; #endif /* DIAGNOSTIC */ #ifdef KMEMSTATS kup = btokup(va); if (kup->ku_indx != indx) panic("malloc: wrong bucket"); if (kup->ku_freecnt == 0) panic("malloc: lost data"); kup->ku_freecnt--; kbp->kb_totalfree--; ksp->ks_memuse += 1 << indx; out: kbp->kb_calls++; ksp->ks_inuse++; ksp->ks_calls++; if (ksp->ks_memuse > ksp->ks_maxused) ksp->ks_maxused = ksp->ks_memuse; #else out: #endif splx(s); return ((void *) va); } /* * Free a block of memory allocated by malloc. */ void free(addr, type) void *addr; int type; { register struct kmembuckets *kbp; register struct kmemusage *kup; register struct freelist *freep; long size; int s; #ifdef DIAGNOSTIC caddr_t cp; long alloc, copysize; #endif #ifdef KMEMSTATS register struct kmemstats *ksp = &kmemstats[type]; #endif kup = btokup(addr); size = 1 << kup->ku_indx; kbp = &bucket[kup->ku_indx]; s = splimp(); #ifdef DIAGNOSTIC /* * Check for returns of data that do not point to the * beginning of the allocation. */ if (size > NBPG * CLSIZE) alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; else alloc = addrmask[kup->ku_indx]; if (((u_long)addr & alloc) != 0) { printf("free: unaligned addr 0x%x, size %d, type %d, mask %d\n", addr, size, type, alloc); panic("free: unaligned addr"); } #endif /* DIAGNOSTIC */ if (size > MAXALLOCSAVE) { kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); #ifdef KMEMSTATS size = kup->ku_pagecnt << PGSHIFT; ksp->ks_memuse -= size; kup->ku_indx = 0; kup->ku_pagecnt = 0; if (ksp->ks_memuse + size >= ksp->ks_limit && ksp->ks_memuse < ksp->ks_limit) wakeup((caddr_t)ksp); ksp->ks_inuse--; kbp->kb_total -= 1; #endif splx(s); return; } freep = (struct freelist *)addr; #ifdef DIAGNOSTIC /* * Check for multiple frees. Use a quick check to see if * it looks free before laboriously searching the freelist. */ copysize = size < sizeof addrmask ? size : sizeof addrmask; if (freep->spare0 == WEIRD_ADDR) { freep->type = ((struct freelist *)addrmask)->type; freep->next = ((struct freelist *)addrmask)->next; if (!bcmp(addrmask, addr, copysize)) { for (cp = kbp->kb_next; cp; cp = *(caddr_t *)cp) { if (addr == cp) { printf("multiply freed item 0x%x\n", addr); panic("free: duplicated free"); } } } } /* * Copy in known text to detect modification after freeing * and to make it look free. Also, save the type being freed * so we can list likely culprit if modification is detected * when the object is reallocated. */ bcopy(addrmask, addr, copysize); freep->type = type; #endif /* DIAGNOSTIC */ #ifdef KMEMSTATS kup->ku_freecnt++; if (kup->ku_freecnt >= kbp->kb_elmpercl) if (kup->ku_freecnt > kbp->kb_elmpercl) panic("free: multiple frees"); else if (kbp->kb_totalfree > kbp->kb_highwat) kbp->kb_couldfree++; kbp->kb_totalfree++; ksp->ks_memuse -= size; if (ksp->ks_memuse + size >= ksp->ks_limit && ksp->ks_memuse < ksp->ks_limit) wakeup((caddr_t)ksp); ksp->ks_inuse--; #endif freep->next = kbp->kb_next; kbp->kb_next = addr; splx(s); } /* * Initialize the kernel memory allocator */ kmeminit() { register long indx; int npg; #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 #endif #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) ERROR!_kmeminit:_MAXALLOCSAVE_too_big #endif #if (MAXALLOCSAVE < CLBYTES) ERROR!_kmeminit:_MAXALLOCSAVE_too_small #endif npg = VM_KMEM_SIZE/ NBPG; kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, (vm_size_t)(npg * sizeof(struct kmemusage))); kmem_map = kmem_suballoc(kernel_map, (vm_offset_t)&kmembase, (vm_offset_t)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); #ifdef KMEMSTATS for (indx = 0; indx < MINBUCKET + 16; indx++) { if (1 << indx >= CLBYTES) bucket[indx].kb_elmpercl = 1; else bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; } for (indx = 0; indx < M_LAST; indx++) kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; #endif }