| 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.7 (Berkeley) %G% |
| 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 | long type, flags; |
| 38 | { |
| 39 | register struct kmembuckets *kbp; |
| 40 | register struct kmemusage *kup; |
| 41 | long indx, npg, alloc, allocsize, s; |
| 42 | caddr_t va, cp; |
| 43 | #ifdef KMEMSTATS |
| 44 | register struct kmemstats *ksp = &kmemstats[type]; |
| 45 | #endif |
| 46 | |
| 47 | indx = BUCKETINDX(size); |
| 48 | kbp = &bucket[indx]; |
| 49 | s = splimp(); |
| 50 | again: |
| 51 | #ifdef KMEMSTATS |
| 52 | while (ksp->ks_inuse >= ksp->ks_limit) { |
| 53 | if (flags & M_NOWAIT) { |
| 54 | splx(s); |
| 55 | return (0); |
| 56 | } |
| 57 | if (ksp->ks_limblocks < 65535) |
| 58 | ksp->ks_limblocks++; |
| 59 | sleep((caddr_t)ksp, PSWP+2); |
| 60 | } |
| 61 | #endif |
| 62 | if (kbp->kb_next == NULL) { |
| 63 | if (size > MAXALLOCSAVE) |
| 64 | allocsize = roundup(size, CLBYTES); |
| 65 | else |
| 66 | allocsize = 1 << indx; |
| 67 | npg = clrnd(btoc(allocsize)); |
| 68 | if ((flags & M_NOWAIT) && freemem < npg) { |
| 69 | splx(s); |
| 70 | return (0); |
| 71 | } |
| 72 | alloc = rmalloc(kmemmap, npg); |
| 73 | if (alloc == 0) { |
| 74 | if (flags & M_NOWAIT) { |
| 75 | splx(s); |
| 76 | return (0); |
| 77 | } |
| 78 | #ifdef KMEMSTATS |
| 79 | if (ksp->ks_mapblocks < 65535) |
| 80 | ksp->ks_mapblocks++; |
| 81 | #endif |
| 82 | wantkmemmap++; |
| 83 | sleep((caddr_t)&wantkmemmap, PSWP+2); |
| 84 | goto again; |
| 85 | } |
| 86 | alloc -= CLSIZE; /* convert to base 0 */ |
| 87 | (void) vmemall(&kmempt[alloc], npg, &proc[0], CSYS); |
| 88 | va = (caddr_t) kmemxtob(alloc); |
| 89 | vmaccess(&kmempt[alloc], va, npg); |
| 90 | #ifdef KMEMSTATS |
| 91 | kbp->kb_total += kbp->kb_elmpercl; |
| 92 | #endif |
| 93 | kup = btokup(va); |
| 94 | kup->ku_indx = indx; |
| 95 | if (allocsize > MAXALLOCSAVE) { |
| 96 | if (npg > 65535) |
| 97 | panic("malloc: allocation too large"); |
| 98 | kup->ku_pagecnt = npg; |
| 99 | #ifdef KMEMSTATS |
| 100 | ksp->ks_memuse += allocsize; |
| 101 | #endif |
| 102 | goto out; |
| 103 | } |
| 104 | #ifdef KMEMSTATS |
| 105 | kup->ku_freecnt = kbp->kb_elmpercl; |
| 106 | kbp->kb_totalfree += kbp->kb_elmpercl; |
| 107 | #endif |
| 108 | kbp->kb_next = va + (npg * NBPG) - allocsize; |
| 109 | for (cp = kbp->kb_next; cp > va; cp -= allocsize) |
| 110 | *(caddr_t *)cp = cp - allocsize; |
| 111 | *(caddr_t *)cp = NULL; |
| 112 | } |
| 113 | va = kbp->kb_next; |
| 114 | kbp->kb_next = *(caddr_t *)va; |
| 115 | #ifdef KMEMSTATS |
| 116 | kup = btokup(va); |
| 117 | if (kup->ku_indx != indx) |
| 118 | panic("malloc: wrong bucket"); |
| 119 | if (kup->ku_freecnt == 0) |
| 120 | panic("malloc: lost data"); |
| 121 | kup->ku_freecnt--; |
| 122 | kbp->kb_totalfree--; |
| 123 | ksp->ks_memuse += 1 << indx; |
| 124 | out: |
| 125 | kbp->kb_calls++; |
| 126 | ksp->ks_inuse++; |
| 127 | ksp->ks_calls++; |
| 128 | if (ksp->ks_inuse > ksp->ks_maxused) |
| 129 | ksp->ks_maxused = ksp->ks_inuse; |
| 130 | #else |
| 131 | out: |
| 132 | #endif |
| 133 | splx(s); |
| 134 | return ((qaddr_t)va); |
| 135 | } |
| 136 | |
| 137 | /* |
| 138 | * Free a block of memory allocated by malloc. |
| 139 | */ |
| 140 | void |
| 141 | free(addr, type) |
| 142 | caddr_t addr; |
| 143 | long type; |
| 144 | { |
| 145 | register struct kmembuckets *kbp; |
| 146 | register struct kmemusage *kup; |
| 147 | long alloc, s; |
| 148 | #ifdef KMEMSTATS |
| 149 | register struct kmemstats *ksp = &kmemstats[type]; |
| 150 | #endif |
| 151 | |
| 152 | kup = btokup(addr); |
| 153 | kbp = &bucket[kup->ku_indx]; |
| 154 | s = splimp(); |
| 155 | if (1 << kup->ku_indx > MAXALLOCSAVE) { |
| 156 | alloc = btokmemx(addr); |
| 157 | (void) memfree(&kmempt[alloc], kup->ku_pagecnt, 0); |
| 158 | rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE); |
| 159 | if (wantkmemmap) { |
| 160 | wakeup((caddr_t)&wantkmemmap); |
| 161 | wantkmemmap = 0; |
| 162 | } |
| 163 | #ifdef KMEMSTATS |
| 164 | ksp->ks_memuse -= kup->ku_pagecnt << PGSHIFT; |
| 165 | kup->ku_indx = 0; |
| 166 | kup->ku_pagecnt = 0; |
| 167 | if (ksp->ks_inuse == ksp->ks_limit) |
| 168 | wakeup((caddr_t)ksp); |
| 169 | ksp->ks_inuse--; |
| 170 | kbp->kb_total -= 1; |
| 171 | #endif |
| 172 | splx(s); |
| 173 | return; |
| 174 | } |
| 175 | #ifdef KMEMSTATS |
| 176 | kup->ku_freecnt++; |
| 177 | if (kup->ku_freecnt >= kbp->kb_elmpercl) |
| 178 | if (kup->ku_freecnt > kbp->kb_elmpercl) |
| 179 | panic("free: multiple frees"); |
| 180 | else if (kbp->kb_totalfree > kbp->kb_highwat) |
| 181 | kbp->kb_couldfree++; |
| 182 | kbp->kb_totalfree++; |
| 183 | if (ksp->ks_inuse == ksp->ks_limit) |
| 184 | wakeup((caddr_t)ksp); |
| 185 | ksp->ks_inuse--; |
| 186 | ksp->ks_memuse -= 1 << kup->ku_indx; |
| 187 | #endif |
| 188 | *(caddr_t *)addr = kbp->kb_next; |
| 189 | kbp->kb_next = addr; |
| 190 | splx(s); |
| 191 | } |
| 192 | |
| 193 | /* |
| 194 | * Initialize the kernel memory allocator |
| 195 | */ |
| 196 | kmeminit() |
| 197 | { |
| 198 | register long indx; |
| 199 | int npg; |
| 200 | |
| 201 | if (!powerof2(MAXALLOCSAVE)) |
| 202 | panic("kmeminit: MAXALLOCSAVE not power of 2"); |
| 203 | if (MAXALLOCSAVE > MINALLOCSIZE * 32768) |
| 204 | panic("kmeminit: MAXALLOCSAVE too big"); |
| 205 | if (MAXALLOCSAVE < CLBYTES) |
| 206 | panic("kmeminit: MAXALLOCSAVE too small"); |
| 207 | npg = ekmempt - kmempt; |
| 208 | rminit(kmemmap, npg, (long)CLSIZE, "malloc map", npg); |
| 209 | #ifdef KMEMSTATS |
| 210 | for (indx = 0; indx < MINBUCKET + 16; indx++) { |
| 211 | if (1 << indx >= CLBYTES) |
| 212 | bucket[indx].kb_elmpercl = 1; |
| 213 | else |
| 214 | bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); |
| 215 | bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; |
| 216 | } |
| 217 | for (indx = 0; indx < M_LAST; indx++) |
| 218 | kmemstats[indx].ks_limit = npg * CLBYTES * 8 / 10; |
| 219 | #endif |
| 220 | } |