1 /* 2 * Copyright (c) 1987 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that this notice is preserved and that due credit is given 7 * to the University of California at Berkeley. The name of the University 8 * may not be used to endorse or promote products derived from this 9 * software without specific prior written permission. This software 10 * is provided ``as is'' without express or implied warranty. 11 * 12 * @(#)kern_malloc.c 7.9 (Berkeley) 05/27/88 13 */ 14 15 #include "param.h" 16 #include "vm.h" 17 #include "cmap.h" 18 #include "time.h" 19 #include "proc.h" 20 #include "map.h" 21 #include "kernel.h" 22 #include "malloc.h" 23 24 #include "../machine/pte.h" 25 26 struct kmembuckets bucket[MINBUCKET + 16]; 27 struct kmemstats kmemstats[M_LAST]; 28 struct kmemusage *kmemusage; 29 long wantkmemmap; 30 31 /* 32 * Allocate a block of memory 33 */ 34 qaddr_t 35 malloc(size, type, flags) 36 unsigned long size; 37 int type, flags; 38 { 39 register struct kmembuckets *kbp; 40 register struct kmemusage *kup; 41 long indx, npg, alloc, allocsize; 42 int s; 43 caddr_t va, cp; 44 #ifdef KMEMSTATS 45 register struct kmemstats *ksp = &kmemstats[type]; 46 #endif 47 48 indx = BUCKETINDX(size); 49 kbp = &bucket[indx]; 50 s = splimp(); 51 again: 52 #ifdef KMEMSTATS 53 while (ksp->ks_memuse >= ksp->ks_limit) { 54 if (flags & M_NOWAIT) { 55 splx(s); 56 return (0); 57 } 58 if (ksp->ks_limblocks < 65535) 59 ksp->ks_limblocks++; 60 sleep((caddr_t)ksp, PSWP+2); 61 } 62 #endif 63 if (kbp->kb_next == NULL) { 64 if (size > MAXALLOCSAVE) 65 allocsize = roundup(size, CLBYTES); 66 else 67 allocsize = 1 << indx; 68 npg = clrnd(btoc(allocsize)); 69 if ((flags & M_NOWAIT) && freemem < npg) { 70 splx(s); 71 return (0); 72 } 73 alloc = rmalloc(kmemmap, npg); 74 if (alloc == 0) { 75 if (flags & M_NOWAIT) { 76 splx(s); 77 return (0); 78 } 79 #ifdef KMEMSTATS 80 if (ksp->ks_mapblocks < 65535) 81 ksp->ks_mapblocks++; 82 #endif 83 wantkmemmap++; 84 sleep((caddr_t)&wantkmemmap, PSWP+2); 85 goto again; 86 } 87 alloc -= CLSIZE; /* convert to base 0 */ 88 (void) vmemall(&kmempt[alloc], (int)npg, &proc[0], CSYS); 89 va = (caddr_t) kmemxtob(alloc); 90 vmaccess(&kmempt[alloc], va, (int)npg); 91 #ifdef KMEMSTATS 92 kbp->kb_total += kbp->kb_elmpercl; 93 #endif 94 kup = btokup(va); 95 kup->ku_indx = indx; 96 if (allocsize > MAXALLOCSAVE) { 97 if (npg > 65535) 98 panic("malloc: allocation too large"); 99 kup->ku_pagecnt = npg; 100 #ifdef KMEMSTATS 101 ksp->ks_memuse += allocsize; 102 #endif 103 goto out; 104 } 105 #ifdef KMEMSTATS 106 kup->ku_freecnt = kbp->kb_elmpercl; 107 kbp->kb_totalfree += kbp->kb_elmpercl; 108 #endif 109 kbp->kb_next = va + (npg * NBPG) - allocsize; 110 for (cp = kbp->kb_next; cp > va; cp -= allocsize) 111 *(caddr_t *)cp = cp - allocsize; 112 *(caddr_t *)cp = NULL; 113 } 114 va = kbp->kb_next; 115 kbp->kb_next = *(caddr_t *)va; 116 #ifdef KMEMSTATS 117 kup = btokup(va); 118 if (kup->ku_indx != indx) 119 panic("malloc: wrong bucket"); 120 if (kup->ku_freecnt == 0) 121 panic("malloc: lost data"); 122 kup->ku_freecnt--; 123 kbp->kb_totalfree--; 124 ksp->ks_memuse += 1 << indx; 125 out: 126 kbp->kb_calls++; 127 ksp->ks_inuse++; 128 ksp->ks_calls++; 129 if (ksp->ks_memuse > ksp->ks_maxused) 130 ksp->ks_maxused = ksp->ks_memuse; 131 #else 132 out: 133 #endif 134 splx(s); 135 return ((qaddr_t)va); 136 } 137 138 /* 139 * Free a block of memory allocated by malloc. 140 */ 141 void 142 free(addr, type) 143 caddr_t addr; 144 int type; 145 { 146 register struct kmembuckets *kbp; 147 register struct kmemusage *kup; 148 long alloc, size; 149 int s; 150 #ifdef KMEMSTATS 151 register struct kmemstats *ksp = &kmemstats[type]; 152 #endif 153 154 kup = btokup(addr); 155 kbp = &bucket[kup->ku_indx]; 156 s = splimp(); 157 size = 1 << kup->ku_indx; 158 if (size > MAXALLOCSAVE) { 159 alloc = btokmemx(addr); 160 (void) memfree(&kmempt[alloc], (int)kup->ku_pagecnt, 0); 161 rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE); 162 if (wantkmemmap) { 163 wakeup((caddr_t)&wantkmemmap); 164 wantkmemmap = 0; 165 } 166 #ifdef KMEMSTATS 167 size = kup->ku_pagecnt << PGSHIFT; 168 ksp->ks_memuse -= size; 169 kup->ku_indx = 0; 170 kup->ku_pagecnt = 0; 171 if (ksp->ks_memuse + size >= ksp->ks_limit && 172 ksp->ks_memuse < ksp->ks_limit) 173 wakeup((caddr_t)ksp); 174 ksp->ks_inuse--; 175 kbp->kb_total -= 1; 176 #endif 177 splx(s); 178 return; 179 } 180 #ifdef KMEMSTATS 181 kup->ku_freecnt++; 182 if (kup->ku_freecnt >= kbp->kb_elmpercl) 183 if (kup->ku_freecnt > kbp->kb_elmpercl) 184 panic("free: multiple frees"); 185 else if (kbp->kb_totalfree > kbp->kb_highwat) 186 kbp->kb_couldfree++; 187 kbp->kb_totalfree++; 188 ksp->ks_memuse -= size; 189 if (ksp->ks_memuse + size >= ksp->ks_limit && 190 ksp->ks_memuse < ksp->ks_limit) 191 wakeup((caddr_t)ksp); 192 ksp->ks_inuse--; 193 #endif 194 *(caddr_t *)addr = kbp->kb_next; 195 kbp->kb_next = addr; 196 splx(s); 197 } 198 199 /* 200 * Initialize the kernel memory allocator 201 */ 202 kmeminit() 203 { 204 register long indx; 205 int npg; 206 207 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 208 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 209 #endif 210 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 211 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 212 #endif 213 #if (MAXALLOCSAVE < CLBYTES) 214 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 215 #endif 216 npg = ekmempt - kmempt; 217 rminit(kmemmap, (long)npg, (long)CLSIZE, "malloc map", npg); 218 #ifdef KMEMSTATS 219 for (indx = 0; indx < MINBUCKET + 16; indx++) { 220 if (1 << indx >= CLBYTES) 221 bucket[indx].kb_elmpercl = 1; 222 else 223 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 224 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 225 } 226 for (indx = 0; indx < M_LAST; indx++) 227 kmemstats[indx].ks_limit = npg * CLBYTES * 8 / 10; 228 #endif 229 } 230