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