1 /* 2 * Copyright (c) 1987, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)kern_malloc.c 7.33 (Berkeley) 05/20/92 8 */ 9 10 #include "param.h" 11 #include "proc.h" 12 #include "map.h" 13 #include "kernel.h" 14 #include "malloc.h" 15 #include "vm/vm.h" 16 #include "vm/vm_kern.h" 17 18 struct kmembuckets bucket[MINBUCKET + 16]; 19 struct kmemstats kmemstats[M_LAST]; 20 struct kmemusage *kmemusage; 21 char *kmembase, *kmemlimit; 22 char *memname[] = INITKMEMNAMES; 23 24 #ifdef DIAGNOSTIC 25 /* 26 * This structure provides a set of masks to catch unaligned frees. 27 */ 28 long addrmask[] = { 0, 29 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 30 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 31 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 32 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 33 }; 34 35 /* 36 * The WEIRD_ADDR is used as known text to copy into free objects so 37 * that modifications after frees can be detected. 38 */ 39 #define WEIRD_ADDR 0xdeadbeef 40 #define MAX_COPY 32 41 42 /* 43 * Normally the first word of the structure is used to hold the list 44 * pointer for free objects. However, when running with diagnostics, 45 * we use the third and fourth fields, so as to catch modifications 46 * in the most commonly trashed first two words. 47 */ 48 struct freelist { 49 long spare0; 50 short type; 51 long spare1; 52 caddr_t next; 53 }; 54 #else /* !DIAGNOSTIC */ 55 struct freelist { 56 caddr_t next; 57 }; 58 #endif /* DIAGNOSTIC */ 59 60 /* 61 * Allocate a block of memory 62 */ 63 void * 64 malloc(size, type, flags) 65 unsigned long size; 66 int type, flags; 67 { 68 register struct kmembuckets *kbp; 69 register struct kmemusage *kup; 70 register struct freelist *freep; 71 long indx, npg, alloc, allocsize; 72 int s; 73 caddr_t va, cp, savedlist; 74 #ifdef DIAGNOSTIC 75 long *end, *lp; 76 int copysize; 77 char *savedtype; 78 #endif 79 #ifdef KMEMSTATS 80 register struct kmemstats *ksp = &kmemstats[type]; 81 82 if (((unsigned long)type) > M_LAST) 83 panic("malloc - bogus type"); 84 #endif 85 indx = BUCKETINDX(size); 86 kbp = &bucket[indx]; 87 s = splimp(); 88 #ifdef KMEMSTATS 89 while (ksp->ks_memuse >= ksp->ks_limit) { 90 if (flags & M_NOWAIT) { 91 splx(s); 92 return ((void *) NULL); 93 } 94 if (ksp->ks_limblocks < 65535) 95 ksp->ks_limblocks++; 96 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 97 } 98 #endif 99 #ifdef DIAGNOSTIC 100 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 101 #endif 102 if (kbp->kb_next == NULL) { 103 if (size > MAXALLOCSAVE) 104 allocsize = roundup(size, CLBYTES); 105 else 106 allocsize = 1 << indx; 107 npg = clrnd(btoc(allocsize)); 108 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), 109 !(flags & M_NOWAIT)); 110 if (va == NULL) { 111 splx(s); 112 return ((void *) NULL); 113 } 114 #ifdef KMEMSTATS 115 kbp->kb_total += kbp->kb_elmpercl; 116 #endif 117 kup = btokup(va); 118 kup->ku_indx = indx; 119 if (allocsize > MAXALLOCSAVE) { 120 if (npg > 65535) 121 panic("malloc: allocation too large"); 122 kup->ku_pagecnt = npg; 123 #ifdef KMEMSTATS 124 ksp->ks_memuse += allocsize; 125 #endif 126 goto out; 127 } 128 #ifdef KMEMSTATS 129 kup->ku_freecnt = kbp->kb_elmpercl; 130 kbp->kb_totalfree += kbp->kb_elmpercl; 131 #endif 132 /* 133 * Just in case we blocked while allocating memory, 134 * and someone else also allocated memory for this 135 * bucket, don't assume the list is still empty. 136 */ 137 savedlist = kbp->kb_next; 138 kbp->kb_next = cp = va + (npg * NBPG) - allocsize; 139 for (;;) { 140 freep = (struct freelist *)cp; 141 #ifdef DIAGNOSTIC 142 /* 143 * Copy in known text to detect modification 144 * after freeing. 145 */ 146 end = (long *)&cp[copysize]; 147 for (lp = (long *)cp; lp < end; lp++) 148 *lp = WEIRD_ADDR; 149 freep->type = M_FREE; 150 #endif /* DIAGNOSTIC */ 151 if (cp <= va) 152 break; 153 cp -= allocsize; 154 freep->next = cp; 155 } 156 freep->next = savedlist; 157 } 158 va = kbp->kb_next; 159 kbp->kb_next = ((struct freelist *)va)->next; 160 #ifdef DIAGNOSTIC 161 freep = (struct freelist *)va; 162 savedtype = (unsigned)freep->type < M_LAST ? 163 memname[freep->type] : "???"; 164 #if BYTE_ORDER == BIG_ENDIAN 165 freep->type = WEIRD_ADDR >> 16; 166 #endif 167 #if BYTE_ORDER == LITTLE_ENDIAN 168 freep->type = WEIRD_ADDR; 169 #endif 170 if (((long)(&freep->next)) & 0x2) 171 freep->next = (caddr_t)((WEIRD_ADDR >> 16)|(WEIRD_ADDR << 16)); 172 else 173 freep->next = (caddr_t)WEIRD_ADDR; 174 end = (long *)&va[copysize]; 175 for (lp = (long *)va; lp < end; lp++) { 176 if (*lp == WEIRD_ADDR) 177 continue; 178 printf("%s %d of object 0x%x size %d %s %s (0x%x != 0x%x)\n", 179 "Data modified on freelist: word", lp - (long *)va, 180 va, size, "previous type", savedtype, *lp, WEIRD_ADDR); 181 break; 182 } 183 freep->spare0 = 0; 184 #endif /* DIAGNOSTIC */ 185 #ifdef KMEMSTATS 186 kup = btokup(va); 187 if (kup->ku_indx != indx) 188 panic("malloc: wrong bucket"); 189 if (kup->ku_freecnt == 0) 190 panic("malloc: lost data"); 191 kup->ku_freecnt--; 192 kbp->kb_totalfree--; 193 ksp->ks_memuse += 1 << indx; 194 out: 195 kbp->kb_calls++; 196 ksp->ks_inuse++; 197 ksp->ks_calls++; 198 if (ksp->ks_memuse > ksp->ks_maxused) 199 ksp->ks_maxused = ksp->ks_memuse; 200 #else 201 out: 202 #endif 203 splx(s); 204 return ((void *) va); 205 } 206 207 /* 208 * Free a block of memory allocated by malloc. 209 */ 210 void 211 free(addr, type) 212 void *addr; 213 int type; 214 { 215 register struct kmembuckets *kbp; 216 register struct kmemusage *kup; 217 register struct freelist *freep; 218 long size; 219 int s; 220 #ifdef DIAGNOSTIC 221 caddr_t cp; 222 long *end, *lp, alloc, copysize; 223 #endif 224 #ifdef KMEMSTATS 225 register struct kmemstats *ksp = &kmemstats[type]; 226 #endif 227 228 kup = btokup(addr); 229 size = 1 << kup->ku_indx; 230 kbp = &bucket[kup->ku_indx]; 231 s = splimp(); 232 #ifdef DIAGNOSTIC 233 /* 234 * Check for returns of data that do not point to the 235 * beginning of the allocation. 236 */ 237 if (size > NBPG * CLSIZE) 238 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 239 else 240 alloc = addrmask[kup->ku_indx]; 241 if (((u_long)addr & alloc) != 0) 242 panic("free: unaligned addr 0x%x, size %d, type %s, mask %d\n", 243 addr, size, memname[type], alloc); 244 #endif /* DIAGNOSTIC */ 245 if (size > MAXALLOCSAVE) { 246 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 247 #ifdef KMEMSTATS 248 size = kup->ku_pagecnt << PGSHIFT; 249 ksp->ks_memuse -= size; 250 kup->ku_indx = 0; 251 kup->ku_pagecnt = 0; 252 if (ksp->ks_memuse + size >= ksp->ks_limit && 253 ksp->ks_memuse < ksp->ks_limit) 254 wakeup((caddr_t)ksp); 255 ksp->ks_inuse--; 256 kbp->kb_total -= 1; 257 #endif 258 splx(s); 259 return; 260 } 261 freep = (struct freelist *)addr; 262 #ifdef DIAGNOSTIC 263 /* 264 * Check for multiple frees. Use a quick check to see if 265 * it looks free before laboriously searching the freelist. 266 */ 267 if (freep->spare0 == WEIRD_ADDR) { 268 for (cp = kbp->kb_next; cp; cp = *(caddr_t *)cp) { 269 if (addr != cp) 270 continue; 271 printf("multiply freed item 0x%x\n", addr); 272 panic("free: duplicated free"); 273 } 274 } 275 /* 276 * Copy in known text to detect modification after freeing 277 * and to make it look free. Also, save the type being freed 278 * so we can list likely culprit if modification is detected 279 * when the object is reallocated. 280 */ 281 copysize = size < MAX_COPY ? size : MAX_COPY; 282 end = (long *)&((caddr_t)addr)[copysize]; 283 for (lp = (long *)addr; lp < end; lp++) 284 *lp = WEIRD_ADDR; 285 freep->type = type; 286 #endif /* DIAGNOSTIC */ 287 #ifdef KMEMSTATS 288 kup->ku_freecnt++; 289 if (kup->ku_freecnt >= kbp->kb_elmpercl) 290 if (kup->ku_freecnt > kbp->kb_elmpercl) 291 panic("free: multiple frees"); 292 else if (kbp->kb_totalfree > kbp->kb_highwat) 293 kbp->kb_couldfree++; 294 kbp->kb_totalfree++; 295 ksp->ks_memuse -= size; 296 if (ksp->ks_memuse + size >= ksp->ks_limit && 297 ksp->ks_memuse < ksp->ks_limit) 298 wakeup((caddr_t)ksp); 299 ksp->ks_inuse--; 300 #endif 301 freep->next = kbp->kb_next; 302 kbp->kb_next = addr; 303 splx(s); 304 } 305 306 /* 307 * Initialize the kernel memory allocator 308 */ 309 kmeminit() 310 { 311 register long indx; 312 int npg; 313 314 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 315 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 316 #endif 317 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 318 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 319 #endif 320 #if (MAXALLOCSAVE < CLBYTES) 321 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 322 #endif 323 npg = VM_KMEM_SIZE/ NBPG; 324 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 325 (vm_size_t)(npg * sizeof(struct kmemusage))); 326 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 327 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); 328 #ifdef KMEMSTATS 329 for (indx = 0; indx < MINBUCKET + 16; indx++) { 330 if (1 << indx >= CLBYTES) 331 bucket[indx].kb_elmpercl = 1; 332 else 333 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 334 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 335 } 336 for (indx = 0; indx < M_LAST; indx++) 337 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 338 #endif 339 } 340